From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 23A5E385734F for ; Thu, 13 Oct 2022 15:30:14 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 23A5E385734F Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1665675013; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=dieeXJpQJKU7RQOz79pETuHXN/vDW0eOSniKbOOI9XE=; b=aCst+L+H0c4VqNFlbx2QM3N20fVFqZCP7B75jknFrBhZubuJedG7RGAp2HJBP3sbOgJtnW 8dJwidfrlq92aBir7afWqkiwQ3WcINMoW7yyAoaKHXXcbMHIDfoYC65/x4KBOaltdW1rOJ IIgg+mvsNupDjwkIR6G5VT5nMaSg0bg= Received: from mail-qt1-f198.google.com (mail-qt1-f198.google.com [209.85.160.198]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-84-woUG20nPMnua0-Or53uLLA-1; Thu, 13 Oct 2022 11:30:12 -0400 X-MC-Unique: woUG20nPMnua0-Or53uLLA-1 Received: by mail-qt1-f198.google.com with SMTP id a19-20020a05622a02d300b0039a3711179dso1544572qtx.12 for ; Thu, 13 Oct 2022 08:30:12 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:cc:to:subject:from:content-language :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=dieeXJpQJKU7RQOz79pETuHXN/vDW0eOSniKbOOI9XE=; b=aRUgc5/NAjvhyLSnaN5UgfGF+KyIeSk4CC4s13DmTzPkHzPX4RA9Cfy7KDNkor/VJB 8ycNeWZo37mV6xtdwDhahiS3nwBBGNrGjiJkkk/fw3IIZNzfZzB421juKipl1vPQOq+j Gf3NaYiGOeKzz5sUAMm1q8zwKaLMcfs0zgKY0aMYyy6EDe0YJuxmmn4jYUdbq1iW57wZ 9YQIWZG6ww2B9TOVpYsTtqmCPdtNod+2o2H/vheIDRK2jIucKUrlfiEpCesw1FiU2Xvk DqlttGt4e+ePpchRqayeLW/Ij7Ocv9BfbdkLjNKQ2j4Z1hueQaB5FUvbSa/bTQFAp6se 4+3w== X-Gm-Message-State: ACrzQf2dQnQlStKMQzXUJIWMJ9iQ48yaKzl2iOfsOV3lOT2LVCMjwFqj w0HiQduxCw+jXVpj/vMM+kpu45WBZxSCe53EuIKi+7lKeR/tLqUwtFkTafMrsDNEpouhXatSCfe igJPoYQzEsx8jjyc+R3Q8LTLWEaZXvlCFT/4MWZu/04qd40ZJEAMeeDlX5WR9ecKflXe88Q== X-Received: by 2002:ae9:f20c:0:b0:6ce:ce8b:d780 with SMTP id m12-20020ae9f20c000000b006cece8bd780mr371014qkg.316.1665675011545; Thu, 13 Oct 2022 08:30:11 -0700 (PDT) X-Google-Smtp-Source: AMsMyM6vMDTpRQxZHMBVxLK3EBebx8NkybnlymGRUEelREAgY/uYaFF7Y/gMaHc0MIpkFdXx8kxhDw== X-Received: by 2002:ae9:f20c:0:b0:6ce:ce8b:d780 with SMTP id m12-20020ae9f20c000000b006cece8bd780mr370993qkg.316.1665675011212; Thu, 13 Oct 2022 08:30:11 -0700 (PDT) Received: from ?IPV6:2607:fea8:a263:f600::50d4? ([2607:fea8:a263:f600::50d4]) by smtp.gmail.com with ESMTPSA id d14-20020a05620a166e00b006be8713f742sm11281qko.38.2022.10.13.08.30.09 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 13 Oct 2022 08:30:10 -0700 (PDT) Message-ID: <27aee40a-5cb5-d680-e6ca-369839d3580a@redhat.com> Date: Thu, 13 Oct 2022 11:30:08 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.2.1 From: Andrew MacLeod Subject: [COMMITTED 0/4] Add partial equivalences to the oracle. To: gcc-patches Cc: "hernandez, aldy" X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-3.4 required=5.0 tests=BAYES_00,BODY_8BITS,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_NONE,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: This patch implements partial equivalences in the relation oracle. They are tracked much like normal equivalences, in that they all belong to a set.  I refer to them as "slices" of an ssa-name.  A little extra info is maintained for a partial set in class pe_slice. A slice contains the bitmap of other members of the partial equivalence, the root ssa-name that every member is a slice of, along with the relation code indicating if its an 8, 16, 32, or 64 bit slice of that name. 4 new relation kinds are added for these:  VREL_PE8, VREL_PE16, VREL_PE32 and VREL_PE64. The oracle maintains a vector of pe_slices representing one entry for each ssa-name globally. we determine at the def point what the LHS is a slice of. It is either the RHS, or becomes a member of the set the RHS is already in. ie: long b_3 = foo() a_4 = (short) b_3 a_4 is registered as a 16 bit slice of b_3.  and the slice set is {b_3, a_4} c_5 = (char) a_4 a_4 is already in a slice set, so c_5 is registered into the set as a 8 bit slice of b_3, and the set now contains {b_3, a_4, c_5} If we query the relation between c_5 and a_4, it is trivial to check that that are in the same slice set, and therefore share bits.  The number of bits they share is the MIN of the slice size of each, so MIN (16, 8). The relation will be returned as VREL_PE8.   This means you can count on the lower 8 bits to be identical between the 2 ssa-names, and they will be defined as those bits in the root value in b_3. That relation can then be used to determine if there is anything useful to be done with this relation by the caller. In particular, this will fix 2 regressions from last year, PR 102540 and 102872 where we lose the connection between a cast and a bitwise mask of the same size.  ie: static long a; static unsigned b; int test1 () {     long c, e;     c = b = a;     e = c ? 2 / (c + 1) : 0;     if (e && !b)         kill ();     a = 0;   : Equivalence set : [_6, c_10] Partial equiv (_2 pe32 a.0_1) Partial equiv (_6 pe32 a.0_1)   a.0_1 = a;   _2 = (unsigned int) a.0_1;   b = _2;   _6 = a.0_1 & 4294967295;   c_10 = _6;   if (c_10 != 0)     goto ; [INV]   else     goto ; [INV] _6 : [irange] long int [0, 4294967295] NONZERO 0xffffffff c_10 : [irange] long int [0, 4294967295] NONZERO 0xffffffff 2->3  (T) a.0_1 :       [irange] long int [-INF, -1][1, +INF] 2->3  (T) _6 :  [irange] long int [1, 4294967295] NONZERO 0xffffffff 2->3  (T) c_10 :        [irange] long int [1, 4294967295] NONZERO 0xffffffff 2->6  (F) a.0_1 :       [irange] long int [-INF, -4294967296][0, +INF] NONZERO 0xffffffff00000000 2->6  (F) _6 :  [irange] long int [0, 0] NONZERO 0x0 2->6  (F) c_10 :        [irange] long int [0, 0] NONZERO 0x0   :   _4 = c_10 + 1;   iftmp.2_12 = 2 / _4;   if (iftmp.2_12 != 0)     goto ; [INV]   else     goto ; [INV]   :   if (_2 == 0) When we get to _2 == 0, ranger looks for any equivalences (full or partial) of _2 coming into this block. It sees that _6 on the edges 2->3->4 has the range 2->3  (T) _6 :  [irange] long int [1, 4294967295] NONZERO 0xffffffff and shares 32 bits.   Both _6 and _2 are 32 bits, so it casts that range of _6 and determines _2 is _2      [irange] unsigned int [1, +INF] and folds away the condition. Bootstrapped on x86_64-pc-linux-gnu with no regressions.