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 9C0C63857816 for ; Sun, 27 Jun 2021 15:46:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 9C0C63857816 Received: from mail-wm1-f70.google.com (mail-wm1-f70.google.com [209.85.128.70]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-210-AS6UEoRoMECUr3sM_tevaA-1; Sun, 27 Jun 2021 11:46:09 -0400 X-MC-Unique: AS6UEoRoMECUr3sM_tevaA-1 Received: by mail-wm1-f70.google.com with SMTP id h14-20020a05600c350eb02901dfc071c176so5629402wmq.3 for ; Sun, 27 Jun 2021 08:46:08 -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:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=LuFjvnZfZP72sVPLBgKINOi1nkWQs1gUEnHCcDyuXvM=; b=APj/1B2pQx9SdwL1DbMS+JtUh5hNB8mmbSaH12gGf9kzh0+nS0siAgvZKh5VadJx0i Jfv39n6YORzPoa4bz8FTemv3IeKW2lVxGYJtBPtJfhZKOv161zRHyX/XS9wh/Nje3JA0 1J5E+e/UjOA+aeD7xIyTIYjQPsJeJYcnbgqXZVcSffCon5fZNwAxOfy+jvL782tWzrW4 d7znqpdRZxjT8txSzfyIl3iHFHQaH8FrTL8g/Nmhxme5+IpY8o7xNhvp8AlHlkafDVs9 2NI9Zrw4AT7dG9c4x+QVXQmY07wbfb2sHwp8SapcQaplqqNXDzqbklRC8doXQrf8vLDb 8dlg== X-Gm-Message-State: AOAM530Mab/IiOdGHimZO8sm5ZlpFp7oLKXSnrW+a09wWrCYzFY9OqFo POeN6No4kp8vYQ3ELorvKySXF99X7KgFPIfMIwGKZc8euUX1pbvS0KmPD5J+uo623XDsnyuosDC TCpa8jsYpmID5c0ahLQ== X-Received: by 2002:a1c:4cd:: with SMTP id 196mr1975373wme.145.1624808767894; Sun, 27 Jun 2021 08:46:07 -0700 (PDT) X-Google-Smtp-Source: ABdhPJyt190pyEMgheulpKndIut72VY7pQ2Yi2MsqCybCNLuLtBSDJzr1k7h0FoOx0O0H8XQv0y7vA== X-Received: by 2002:a1c:4cd:: with SMTP id 196mr1975356wme.145.1624808767668; Sun, 27 Jun 2021 08:46:07 -0700 (PDT) Received: from abulafia.quesejoda.com ([95.169.237.215]) by smtp.gmail.com with ESMTPSA id t17sm3145016wrs.61.2021.06.27.08.46.06 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sun, 27 Jun 2021 08:46:07 -0700 (PDT) Subject: Re: [PATCH] tree-optimization/101186 - extend FRE with "equivalence map" for condition prediction To: Richard Biener , Andrew MacLeod Cc: Di Zhao , "gcc-patches@gcc.gnu.org" , Jeff Law References: <860299c5-8f2e-2d1f-c7bc-bab4eb25ec8a@redhat.com> From: Aldy Hernandez Message-ID: <69174dc2-450b-2f57-1469-31892b937158@redhat.com> Date: Sun, 27 Jun 2021 17:46:06 +0200 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: X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-US Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-4.9 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, NICE_REPLY_A, RCVD_IN_BARRACUDACENTRAL, 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: Sun, 27 Jun 2021 15:46:14 -0000 On 6/25/21 9:38 AM, Richard Biener wrote: > On Thu, Jun 24, 2021 at 5:01 PM Andrew MacLeod wrote: >> >> 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... > > I guess to fully leverage optimizations for cases like > > if (a != 0) > c = b; > ... > if (a != 0) > { > if (c == b) > ... > } > > one would need to consider the "optimally jump threaded path" to the > program point where the to be optimized stmt resides, making all > originally conditional but on the jump threaded path unconditional > relations and equivalences available. > > For VN that could be done by unwinding to the CFG merge after > the first if (a != 0), treating only one of the predecessor edges > as executable and registering the appropriate a != 0 result and > continue VN up to the desired point, committing to the result > until before the CFG merge after the second if (a != 0). And then > unwinding again for the "else" path. Sounds like a possible > explosion in complexity as well if second-order opportunities > arise. > > That is, we'd do simplifications exposed by jump threading but > without actually doing the jump threading (which will of course > not allow all possible simplifications w/o inserting extra PHIs > for computations we might want to re-use). FWIW, as I mention in the PR, if the upcoming threader work could be taught to use the relation oracle, it could easily solve the conditional flowing through the a!=0 path. However, we wouldn't be able to thread it because in this particular case, the path crosses loop boundaries. I leave it to Jeff/others to pontificate on whether the jump-threader path duplicator could be taught to through loops. ?? Aldy