From patchwork Wed Nov 24 19:50:05 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 48112 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id CE9AE3857C7A for ; Wed, 24 Nov 2021 20:48:51 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org CE9AE3857C7A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1637786931; bh=X06QA68ZAPTdFG4uYvKW0sqqxMGCIHj5iOmBE/h+Ueo=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=LRU9mYRZU+u5hKDFPbeqgh4kFLe6eIdxclR115vR4ZtRgKxpDLiF4GK/oxzWdbwyt 5kLfmS9MNJnGSvRW9SN9qYHnw1rD2kgXIxlXv9RjXyH1nTKwWXOX8C1eC9Yjse1gLR 0D2w6lXFXgFX6Z3f4j4O5aZgW4DA1BSb9gYpyQak= 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.129.124]) by sourceware.org (Postfix) with ESMTPS id 692963858C27 for ; Wed, 24 Nov 2021 19:50:10 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 692963858C27 Received: from mail-qk1-f199.google.com (mail-qk1-f199.google.com [209.85.222.199]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-39-3HnQYQ79OEK7B98WnPMlrQ-1; Wed, 24 Nov 2021 14:50:08 -0500 X-MC-Unique: 3HnQYQ79OEK7B98WnPMlrQ-1 Received: by mail-qk1-f199.google.com with SMTP id bp17-20020a05620a459100b0045e893f2ed8so3130135qkb.11 for ; Wed, 24 Nov 2021 11:50:08 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent :content-language:to:from:subject; bh=IL/P+cCGU6uAb6CGWUBefuqL8pyPIGsLVyL9G+EFbVE=; b=v6NBgbWYUjZ8jF/0zuJKGNS6cLtjImukjApnc3a4YMtcJ930nGZv8E5VhzeKTDohJq un1L2LrRwMFbYnQudE79oXrnvwjuFAWkaRdih7l9+UzV0LyRe1eB8StlqsqEtPJRRrHa jZYJDHxUXlgJCn5TZ2DBBQbfUfFBqp5LEio5Tk7ypXxb4NOLQYo7jSFSaabZrQ+NvBJS 5wCN9hKFOq3eUzXTVc4hlSFdQCNmYRWRVYnOuEAMd1dlgXiNjKFGhyz8X3kkyYnFAk82 5PkBj9bFYoIEiScOz89WY5QotUHrGLu+IBTK6yuefOy3o75ve8RM8QbgCUoClSC37c+O CD9A== X-Gm-Message-State: AOAM532j1WkrohxCJK+y8Cl6+195jH+jW6SozF33aGXVVFUkV7aEa4oS kzX8vD1iPaAWEqiw+iNTJul2IjVN96qQIGaWp3d1/A716bO9UrBsAzWtYjvjn4/2qwlqTlIHPQY 2h7OygSWDO+Tk5gurSVRmgX32EZCwdiH+3d05e0dA1fsr1N9mTXeZaQw8baxZFhaW93srGQ== X-Received: by 2002:a37:bdc7:: with SMTP id n190mr951647qkf.658.1637783407524; Wed, 24 Nov 2021 11:50:07 -0800 (PST) X-Google-Smtp-Source: ABdhPJwq4+WyHAKU9Fqz3vA8h/imMOUXftoM2Grxa/NuY2YlZbE0J8vdSi+IeRwA8QXkPlhhfS/gaw== X-Received: by 2002:a37:bdc7:: with SMTP id n190mr951604qkf.658.1637783407169; Wed, 24 Nov 2021 11:50:07 -0800 (PST) Received: from ?IPV6:2607:fea8:a262:5f00::38cf? ([2607:fea8:a262:5f00::38cf]) by smtp.gmail.com with ESMTPSA id j21sm326415qkk.27.2021.11.24.11.50.06 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 24 Nov 2021 11:50:06 -0800 (PST) Message-ID: Date: Wed, 24 Nov 2021 14:50:05 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.3.2 To: gcc-patches Subject: [PATCH] PR tree-optimization/103359 - Check for equivalences between PHI argument and def. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-12.6 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" PHI nodes frequently feed each other, and this is particularly true of the one/two incoming edge PHIs inserted by some of the loop analysis code which is introduced at the start of the VRP passes. Ranger has a hybrid of optimistic vs pessimistic evaluation, and when it switches to pessimistic, it has to assume VARYING for a range.  PHIs are calculated as the union of all incoming edges, so once we throw a VARYING into the mix, there's not much chance going back.  (mostly true... we can sometimes update the range when inputs change, but we prefer to avoid iterating when possible) We already have code to recognize that if an argument to a PHI is the same as the def, it cannot provide any additional information and is skipped.  ie,   # h_10 = PHI <4(2), h_10(3), h_10(4), 1(7)> We can skip the h_10 arguments, and produce [1,1][4,4] as the range with any additional information/processing. This patch extends that slightly to recognize that if the argument is a known equivalence of the def, it also does not provide any additional information.  This allows us to "ignore" some of the pessimistic VARYING values that come in on back edges when the relation oracle indicates that there is a known equivalence. Take for instance the sequence from the PR testcase:   :   # h_7 = PHI <4(2), 1(4)>   :   # h_18 = PHI   :   # h_22 = PHI   :   # h_20 = PHI  We only fully calculate one range at a time, so when calculating h_18, we need to first resolve the range h_22 on the back edge 3->6. That feeds back to h_18, which isn't fully calculated yet and is pessimistically assumed to be VARYING until we do get a value. With h_22 being varying when resolving h_18 now, we end up makig h_18 varying, and lose the info from h_7. This patch extends the equivalence observation slightly to recognize that if the argument is a known equivalence of the def in predecessor block, it also does not provide any additional information.  This allows us to ignore some of the pessimistic VARYING values that are set when the relation oracle indicates that there is a known equivalence. In the above case, h_22 is known to be equivalent to h_18 in BB3, and so we can ignore the range h_22 provides on any edge coming from bb3. There is a caveat that if *all* the arguments to a PHI are in the equivalence set, then you have to use the range of the equivalence.. otherwise you get UNDEFINED. This will help us to see through some of the artifacts of cycling PHIs in these simple cases, and in the above case, we end up with h_7, h_18, h_22 and h_20 all in the equivalence set with a range of [1, 1][4, 4], and we can remove the code we need to like we did in GCC11. This wont help with more complex PHI cycles, but that seems like something we could be looking at elsewhere, phi-opt maybe, utilizing ranger to set the global range when its complex. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  OK? Andrew From 9cb5bd6c436165a37717d58388950c5c5ecaf35e Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Tue, 23 Nov 2021 14:12:29 -0500 Subject: [PATCH] Check for equivalences between PHI argument and def. If a PHI argument on an edge is equivalent with the DEF, then it doesn't provide any new information, defer processing it unless they are all equivalences. PR tree-optimization/103359 gcc/ * gimple-range-fold.cc (fold_using_range::range_of_phi): If arg is equivalent to def, don't initially include it's range. gcc/testsuite/ * gcc.dg/pr103359.c: New. --- gcc/gimple-range-fold.cc | 16 ++++++++++++++++ gcc/testsuite/gcc.dg/pr103359.c | 21 +++++++++++++++++++++ 2 files changed, 37 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/pr103359.c diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc index ec9690b05e4..d66ada5bb7c 100644 --- a/gcc/gimple-range-fold.cc +++ b/gcc/gimple-range-fold.cc @@ -771,6 +771,7 @@ fold_using_range::range_of_phi (irange &r, gphi *phi, fur_source &src) tree phi_def = gimple_phi_result (phi); tree type = gimple_range_type (phi); int_range_max arg_range; + int_range_max equiv_range; unsigned x; if (!type) @@ -794,6 +795,16 @@ fold_using_range::range_of_phi (irange &r, gphi *phi, fur_source &src) // Get the range of the argument on its edge. src.get_phi_operand (arg_range, arg, e); + // Likewise, if the incoming PHI argument is equivalent to this + // PHI definition, it provides no new info. Accumulate these ranges + // in case all arguments are equivalences. + if (src.query ()->query_relation (e, arg, phi_def, false) == EQ_EXPR) + { + single_arg = arg; + equiv_range.union_(arg_range); + continue; + } + if (!arg_range.undefined_p ()) { // Register potential dependencies for stale value tracking. @@ -816,6 +827,11 @@ fold_using_range::range_of_phi (irange &r, gphi *phi, fur_source &src) break; } + // If all arguments were equivalences, use the equivalence ranges as no + // arguments were processed. + if (!seen_arg) + r = equiv_range; + // If the PHI boils down to a single effective argument, look at it. if (single_arg) { diff --git a/gcc/testsuite/gcc.dg/pr103359.c b/gcc/testsuite/gcc.dg/pr103359.c new file mode 100644 index 00000000000..13406f90d7d --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr103359.c @@ -0,0 +1,21 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fdump-tree-evrp" } */ + +void foo(); +static char a, c; +static int d, e; +static short b(short f, short g) { return f * g; } +int main() { + short h = 4; + for (; d;) + if (h) + if(e) { + if (!b(a & 1 | h, 3)) + c = 0; + h = 1; + } + if (c) + foo(); +} + +/* { dg-final { scan-tree-dump-not "c = 0" "evrp" } } */ -- 2.17.2