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 ESMTP id 361C53857027 for ; Thu, 24 Jun 2021 15:01:43 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 361C53857027 Received: from mail-qt1-f197.google.com (mail-qt1-f197.google.com [209.85.160.197]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-364-NTWakTD3OeioYnsXhoZ85A-1; Thu, 24 Jun 2021 11:01:39 -0400 X-MC-Unique: NTWakTD3OeioYnsXhoZ85A-1 Received: by mail-qt1-f197.google.com with SMTP id l2-20020ac84cc20000b029024ef0325fd0so5142574qtv.0 for ; Thu, 24 Jun 2021 08:01:39 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:from:to:cc:references:message-id:date :user-agent:mime-version:in-reply-to:content-transfer-encoding :content-language; bh=FYYDju+W+Ku+XXP0OAj6tVneUqIt4TYR1efJ8iDk+s0=; b=pJvE+IO7Vu3Xl5HYQQ999JDtbDZZecXg1yfeK4ak9obuk4DSRF4b8eHc10LUqxipU3 gypUWG5vtgPRadyi4jFTRyp8KreI3tdl5CMT0JK4UPm8r5J6HsYtP/ROGgRyGj3Q5fOj u5ibBDI7d7MRSFEz+uYjPPUVseNpClUsGS5NdSkmDZAmkJWndcc08d5Xh+ZNemK60igT OPXrMHNsV0L5JJoxc/W/+piX48GZlCZGpKoUEb02/I7xgeoQTeWT+4gjD66wee1e4Nbi eb/1Eqto0tKQTaz6EpphAlpuBH6P1Vy6kDbMDs3oaFjd1ATJkgpwEJvNgXytSS8BvSGd wK6A== X-Gm-Message-State: AOAM530/j8tHKwCE8VEW+8v7CxXUSG+ST9sMEAYrNEwWxPsr83/FuRlv rfLbzUyk/NTQToyArtvM/b4gVpn9vAqjSO/f3LNdjMai08Avkj4ttfumtqEPulvJRd868K3q1io SK3JF3aKSl7LBw4FgBA== X-Received: by 2002:a0c:c401:: with SMTP id r1mr5832545qvi.46.1624546898910; Thu, 24 Jun 2021 08:01:38 -0700 (PDT) X-Google-Smtp-Source: ABdhPJxb9aQQe67Uz1TVZHqdWilmwq7wz/enqzOCXK1BEd9mHja27UIdgo1HDuV5+hhSFYNqE6F4aA== X-Received: by 2002:a0c:c401:: with SMTP id r1mr5832523qvi.46.1624546898719; Thu, 24 Jun 2021 08:01:38 -0700 (PDT) Received: from ?IPv6:2607:fea8:a241:4600::58f9? ([2607:fea8:a241:4600::58f9]) by smtp.gmail.com with ESMTPSA id 5sm905540qks.36.2021.06.24.08.01.37 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 24 Jun 2021 08:01:38 -0700 (PDT) Subject: Re: [PATCH] tree-optimization/101186 - extend FRE with "equivalence map" for condition prediction From: Andrew MacLeod To: Richard Biener , Di Zhao Cc: "gcc-patches@gcc.gnu.org" , Aldy Hernandez References: <860299c5-8f2e-2d1f-c7bc-bab4eb25ec8a@redhat.com> Message-ID: Date: Thu, 24 Jun 2021 11:01:36 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.11.0 MIME-Version: 1.0 In-Reply-To: <860299c5-8f2e-2d1f-c7bc-bab4eb25ec8a@redhat.com> X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-Language: en-CA X-Spam-Status: No, score=-4.3 required=5.0 tests=BAYES_00, BODY_8BITS, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, NICE_REPLY_A, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) 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-List-Received-Date: Thu, 24 Jun 2021 15:01:44 -0000 On 6/24/21 9:25 AM, Andrew MacLeod wrote: > On 6/24/21 8:29 AM, Richard Biener wrote: > > > THe original function in EVRP currently looks like: > >  =========== BB 2 ============ >     : >     if (a_5(D) == b_6(D)) >       goto ; [INV] >     else >       goto ; [INV] > > =========== BB 8 ============ > Equivalence set : [a_5(D), b_6(D)]                 edge 2->8 provides > a_5 and b_6 as equivalences >     : >     goto ; [100.00%] > > =========== BB 6 ============ >     : >     # i_1 = PHI <0(8), i_10(5)> >     if (i_1 < a_5(D)) >       goto ; [INV] >     else >       goto ; [INV] > > =========== BB 3 ============ > Relational : (i_1 < a_5(D))                         edge 6->3 provides > this relation >     : >     if (i_1 == b_6(D)) >       goto ; [INV] >     else >       goto ; [INV] > > > So It knows that a_5 and b_6 are equivalence, and it knows that i_1 < > a_5 in BB3 as well.. > > so we should be able to indicate that  i_1 == b_6 as [0,0]..  we > currently aren't.   I think I had turned on equivalence mapping during > relational processing, so should be able to tag that without > transitive relations...  I'll have a look at why. > > And once we get a bit further along, you will be able to access this > without ranger.. if one wants to simply register the relations directly. > > Anyway, I'll get back to you why its currently being missed. > > Andrew > > > As promised.  There was a typo in the equivalency comparisons... so it was getting missed.  With the fix, the oracle identifies the relation and evrp will now fold that expression away and the IL becomes:   :   if (a_5(D) == b_6(D))     goto ; [INV]   else     goto ; [INV]   :   i_10 = i_1 + 1;   :   # i_1 = PHI <0(2), i_10(3)>   if (i_1 < a_5(D))     goto ; [INV]   else     goto ; [INV]   :   return; for the other cases you quote, there are no predictions such that if a != 0 then this equivalency exists... +  if (a != 0) +    { +      c = b; +    } but the oracle would register that in the TRUE block,  c and b are equivalent... so some other pass that was interested in tracking conditions that make a block relevant would be able to compare relations... Andrew