From patchwork Thu Oct 13 15:30:08 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 70 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4ac7:0:0:0:0:0 with SMTP id y7csp340503wrs; Thu, 13 Oct 2022 08:31:07 -0700 (PDT) X-Google-Smtp-Source: AMsMyM63uH0sdCXZepa3sMdKXuiS6WPprLF15/jvB1pVjSlKTaGqZO4YbJhs8eCCWKZvTtZZOPty X-Received: by 2002:a17:907:2cd9:b0:78d:9e76:be26 with SMTP id hg25-20020a1709072cd900b0078d9e76be26mr219183ejc.315.1665675067398; Thu, 13 Oct 2022 08:31:07 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1665675067; cv=none; d=google.com; s=arc-20160816; b=ovpxguQgoW3KzhGGLEK+E3JfqSeGvLK/Y2IhbMbW234xW3gsw5PamRN3eQC9TgWwNG gP4ru1jzrJBu/XrB9ndt8ZUnk6sNbtbjXlXNdRrUoCtLtB16KRceuRicQB4cmW9oPPCh dkwVvO0FVG5w/OPPpJIBHUCjOg3pN1GzRkjIzi6ZZQLv8irosnP6Ube0hjdelethgyid bg4abqVajFsIkXuQ8zjH8K09kZRUUBblz2UF5BWW+nzPSutbKTGvoRa2QvsMBFMiTTF1 sAblbmuZ3skGeNa/rtmbr8iMrWA3Eidg1HeabmysqkrUM8MpYDYErk5QRXjoj2rFftIa HmPA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence :content-transfer-encoding:content-language:to:subject:user-agent :mime-version:date:message-id:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=dieeXJpQJKU7RQOz79pETuHXN/vDW0eOSniKbOOI9XE=; b=XAHRS+0UyCyTwBpgxcL2qV1rUlhx+Ckl5+W+WiF/cqn83YacE938ZE5kMUvYtqeN59 zdYoN1gd4vPqd3+F5wMnP0NBggbC9P7ROtCEGmZem6y0aTByH8O1/KvRwSMAnq02sWWs j3HP+yM/TaGWXRjVipQj50uICCTGbw9ufhXRp2UZvy05I/1QrDp8qR+FARCfNwwKdeEl kfnOnA1k3OijL9iVRz3PNO1SGrTXBL1oeFecXkm+kybjV8TavliYhy0QabDrmpZsddDj l7J1LxYtQbhhJ6OtrJDz/xJhyiz65CZ6k3/wBj+pEOmXOV9Ihb5YAhELxMcCaFzHlmui HCfw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=n5jY6TB8; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id i8-20020a05640242c800b0045945eed10asi70576edc.5.2022.10.13.08.31.07 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 13 Oct 2022 08:31:07 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=n5jY6TB8; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id DD7B1385E012 for ; Thu, 13 Oct 2022 15:30:57 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org DD7B1385E012 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1665675057; bh=dieeXJpQJKU7RQOz79pETuHXN/vDW0eOSniKbOOI9XE=; h=Date:Subject:To:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=n5jY6TB8yfG+ApI+w9mX6zWHdutoe7ln1CRQhaE4SgchsNui0GtfpcoTL+5cEIVK8 UbhauBlQGhcbYU1GjIx+Ryehplqzq9jFDupItxHQZ/fO/SlvSSDBsUuliAb40SE72B twZV5B0pvveZFUP/DfSqpoO+gsxzrAkMX7dR0B0o= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org 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 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-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 Subject: [COMMITTED 0/4] Add partial equivalences to the oracle. To: gcc-patches X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US 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 X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1746586899857362459?= X-GMAIL-MSGID: =?utf-8?q?1746586899857362459?= 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.