From patchwork Mon Sep 20 22:00:15 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1530415 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=aeWAdPmE; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4HCz5v59jwz9sW8 for ; Tue, 21 Sep 2021 08:01:07 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 6B918385840F for ; Mon, 20 Sep 2021 22:01:05 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 6B918385840F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1632175265; bh=btyiZTZjzs6p7ZsoPzcOr3E/bcCbWFFzYspK9YZHIkQ=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=aeWAdPmEqXJe2KMS/2IftVxSbHtquHeElwSImMNQ/oL6aU7f6AGcvcABz3ANOncaE eS49ey/WWkgBWA0pOjyceDmMEQ7jwINVwDBrEi1o53/ToLluf0kmMwTsk9uD9HvGpm lGniX3tyEG2Hrjm/UnZVSw3gqesnfXS6+Szc1u0w= 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 [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id A3CD13858403 for ; Mon, 20 Sep 2021 22:00:20 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org A3CD13858403 Received: from mail-ot1-f72.google.com (mail-ot1-f72.google.com [209.85.210.72]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-339-SWSTOoWJP6WS4rmVQUVKqA-1; Mon, 20 Sep 2021 18:00:18 -0400 X-MC-Unique: SWSTOoWJP6WS4rmVQUVKqA-1 Received: by mail-ot1-f72.google.com with SMTP id a8-20020a9d4708000000b0054718779c33so1670931otf.5 for ; Mon, 20 Sep 2021 15:00:18 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:to:cc:from:subject:message-id:date:user-agent :mime-version:content-language; bh=btyiZTZjzs6p7ZsoPzcOr3E/bcCbWFFzYspK9YZHIkQ=; b=7W0y31BUYTmJXsfwdX8Yt76SDL8HvKvXUVrYm7gqn8HZoQbug1RPS/CqXfvcekbw/P OU2Ez8QbBJS09N3XnCyH3P1EEhQ2GpI8eDwXGW0gWQqgzHxRB8aPglkhB79BTi0vMDbz 7jlsv8vPf8/ZFkmpoyzPPwglqG92rMPAkbethpf5+E4RoxRzhMLc5swJlpoIQw9yWb0h hWdROMhdj/6GSYiHn6b5df9P7rQjO+M+jp9eSe5QCh7cX8DmCFtfEkBfIRhZjiNipjSr RiasD0GI4nKkVoZYIv36xP79OapUGAS7YCA4uIErv2XVIDE7Sj/qSd90YO+j9YJZwLPD SyRw== X-Gm-Message-State: AOAM530oLh0T8n5vrD5avstLw29VsqiQiU1a9msW0+SpIUMx1HO0pDcz s8NQxVjideElivYVxf73dvjaRkihW2jaKqo4hLap005mf/1cuKI96tXVy7LC32CkaXXlGj4MI/I ftVkvknuey+kKqmtd+A== X-Received: by 2002:a9d:6142:: with SMTP id c2mr16066310otk.118.1632175217850; Mon, 20 Sep 2021 15:00:17 -0700 (PDT) X-Google-Smtp-Source: ABdhPJx3ymGRBDSg3jLsQ6Xo1CA0v1hvhSGEHAy8ELGnK8nBFFc84dLslrsxn4nywZqK3Cxnsxsy7Q== X-Received: by 2002:a9d:6142:: with SMTP id c2mr16066290otk.118.1632175217544; Mon, 20 Sep 2021 15:00:17 -0700 (PDT) Received: from ?IPv6:2607:fea8:a261:d400::5989? ([2607:fea8:a261:d400::5989]) by smtp.gmail.com with ESMTPSA id r31sm3739869otv.45.2021.09.20.15.00.16 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 20 Sep 2021 15:00:16 -0700 (PDT) To: gcc-patches Subject: [COMMITTED] Use EDGE_EXECUTABLE in ranger and return UNDEFINED for those edges. Message-ID: Date: Mon, 20 Sep 2021 18:00:15 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.13.0 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-13.7 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_H2, 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+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" The patch sets the EXECUTABLE property on edges like VRP does, and then removes that flag when an edge is determined to be un-executable. This information is then used to return UNDEFINED for any requests on un-executable edges, and to register equivalencies if all executable edges of a PHI node are the same SSA_NAME. This catches up a number of the cases VRP gets that ranger was missing, and reduces the EVRP discrepancies to almost 0. On a side note,  is there any interest/value in reversing the meaning of that flag?  It seems to me that we could assume edges are EXECUTABLE by default, then set a NON_EXECUTABLE flag when a pass determines the edge cannot be executed.  This would rpevent a number fo passes from having to loop through all the edges and set the EXECUTABLE property...   It just seems backwards to me. Anyway, bootstrapped on x86_64-pc-linux-gnu with no regressions. pushed. Andrew From 73cf73af2392e00917de042a4692f6a0b6329ee8 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Tue, 24 Aug 2021 12:13:24 -0400 Subject: [PATCH 2/2] Use EDGE_EXECUTABLE in ranger and return UNDEFINED for those edges. If an incoming edge is UNDEFINED, don't process it. Track if other edges equate to a single value, and add an equivalence if appropriate. gcc/ * gimple-range-fold.cc (fold_using_range::range_of_phi): Ignore undefined edges, apply an equivalence if appropriate. * gimple-range-gori.cc (gori_compute::outgoing_edge_range_p): Return UNDEFINED if EDGE_EXECUTABLE is not set. * gimple-range.cc (gimple_ranger::gimple_ranger): Set all edges as EXECUTABLE upon startup. (gimple_ranger::range_on_edge): Return UNDEFINED for edges without EDGE_EXECUTABLE set. * vr-values.c (set_and_propagate_unexecutable): New. (simplify_using_ranges::fold_cond): Call set_and_propagate. (simplify_using_ranges::simplify_switch_using_ranges): Ditto. * vr-values.h: Add prototype. gcc/testsuite/ * gcc.dg/tree-ssa/evrp-ignore.c: New. --- gcc/gimple-range-fold.cc | 47 ++++++++++++++++++--- gcc/gimple-range-gori.cc | 25 ++++------- gcc/gimple-range.cc | 36 +++++++++++----- gcc/testsuite/gcc.dg/tree-ssa/evrp-ignore.c | 28 ++++++++++++ gcc/vr-values.c | 39 ++++++++++++++++- gcc/vr-values.h | 1 + 6 files changed, 140 insertions(+), 36 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/evrp-ignore.c diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc index 997d02dd4b9..80cc5c0dc0c 100644 --- a/gcc/gimple-range-fold.cc +++ b/gcc/gimple-range-fold.cc @@ -760,6 +760,10 @@ fold_using_range::range_of_phi (irange &r, gphi *phi, fur_source &src) if (!type) return false; + // Track if all executable arguments are the same. + tree single_arg = NULL_TREE; + bool seen_arg = false; + // Start with an empty range, unioning in each argument's range. r.set_undefined (); for (x = 0; x < gimple_phi_num_args (phi); x++) @@ -767,19 +771,48 @@ fold_using_range::range_of_phi (irange &r, gphi *phi, fur_source &src) tree arg = gimple_phi_arg_def (phi, x); edge e = gimple_phi_arg_edge (phi, x); - // Register potential dependencies for stale value tracking. - if (gimple_range_ssa_p (arg) && src.gori ()) - src.gori ()->register_dependency (phi_def, arg); - // Get the range of the argument on its edge. src.get_phi_operand (arg_range, arg, e); - // If we're recomputing the argument elsewhere, try to refine it. - r.union_ (arg_range); + + if (!arg_range.undefined_p ()) + { + // Register potential dependencies for stale value tracking. + r.union_ (arg_range); + if (gimple_range_ssa_p (arg) && src.gori ()) + src.gori ()->register_dependency (phi_def, arg); + + // Track if all arguments are the same. + if (!seen_arg) + { + seen_arg = true; + single_arg = arg; + } + else if (single_arg != arg) + single_arg = NULL_TREE; + } + // Once the value reaches varying, stop looking. - if (r.varying_p ()) + if (r.varying_p () && single_arg == NULL_TREE) break; } + // If the PHI boils down to a single effective argument, look at it. + if (single_arg) + { + // Symbolic arguments are equivalences. + if (gimple_range_ssa_p (single_arg)) + src.register_relation (phi, EQ_EXPR, phi_def, single_arg); + else if (src.get_operand (arg_range, single_arg) + && arg_range.singleton_p ()) + { + // Numerical arguments that are a constant can be returned as + // the constant. This can help fold later cases where even this + // constant might have been UNDEFINED via an unreachable edge. + r = arg_range; + return true; + } + } + // If SCEV is available, query if this PHI has any knonwn values. if (scev_initialized_p () && !POINTER_TYPE_P (TREE_TYPE (phi_def))) { diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc index f78829595dc..f5a35287bed 100644 --- a/gcc/gimple-range-gori.cc +++ b/gcc/gimple-range-gori.cc @@ -1214,6 +1214,15 @@ gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name, int_range_max lhs; unsigned idx; + if ((e->flags & EDGE_EXECUTABLE) == 0) + { + r.set_undefined (); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Outgoing edge %d->%d unexecutable.\n", + e->src->index, e->dest->index); + return true; + } + gcc_checking_assert (gimple_range_ssa_p (name)); // Determine if there is an outgoing edge. gimple *stmt = outgoing.edge_range_p (lhs, e); @@ -1221,22 +1230,6 @@ gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name, return false; fur_stmt src (stmt, &q); - - // If this edge is never taken, return undefined. - gcond *gc = dyn_cast (stmt); - if (gc) - { - if (((e->flags & EDGE_TRUE_VALUE) && gimple_cond_false_p (gc)) - || ((e->flags & EDGE_FALSE_VALUE) && gimple_cond_true_p (gc))) - { - r.set_undefined (); - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Outgoing edge %d->%d unexecutable.\n", - e->src->index, e->dest->index); - return true; - } - } - // If NAME can be calculated on the edge, use that. if (is_export_p (name, e->src)) { diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index d74cea3451e..625d13647f7 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -34,6 +34,7 @@ along with GCC; see the file COPYING3. If not see #include "cfgloop.h" #include "tree-scalar-evolution.h" #include "gimple-range.h" +#include "domwalk.h" gimple_ranger::gimple_ranger () : tracer ("") { @@ -41,6 +42,7 @@ gimple_ranger::gimple_ranger () : tracer ("") m_oracle = m_cache.oracle (); if (dump_file && (param_evrp_mode & EVRP_MODE_TRACE)) tracer.enable_trace (); + set_all_edges_as_executable (cfun); } bool @@ -164,10 +166,6 @@ gimple_ranger::range_on_edge (irange &r, edge e, tree name) int_range_max edge_range; gcc_checking_assert (irange::supports_type_p (TREE_TYPE (name))); - // PHI arguments can be constants, catch these here. - if (!gimple_range_ssa_p (name)) - return range_of_expr (r, name); - unsigned idx; if ((idx = tracer.header ("range_on_edge ("))) { @@ -175,16 +173,32 @@ gimple_ranger::range_on_edge (irange &r, edge e, tree name) fprintf (dump_file, ") on edge %d->%d\n", e->src->index, e->dest->index); } - range_on_exit (r, e->src, name); - gcc_checking_assert (r.undefined_p () - || range_compatible_p (r.type(), TREE_TYPE (name))); + // Check to see if the edge is executable. + if ((e->flags & EDGE_EXECUTABLE) == 0) + { + r.set_undefined (); + if (idx) + tracer.trailer (idx, "range_on_edge [Unexecutable] ", true, + name, r); + return true; + } - // Check to see if NAME is defined on edge e. - if (m_cache.range_on_edge (edge_range, e, name)) - r.intersect (edge_range); + bool res = true; + if (!gimple_range_ssa_p (name)) + res = range_of_expr (r, name); + else + { + range_on_exit (r, e->src, name); + gcc_checking_assert (r.undefined_p () + || range_compatible_p (r.type(), TREE_TYPE (name))); + + // Check to see if NAME is defined on edge e. + if (m_cache.range_on_edge (edge_range, e, name)) + r.intersect (edge_range); + } if (idx) - tracer.trailer (idx, "range_on_edge", true, name, r); + tracer.trailer (idx, "range_on_edge", res, name, r); return true; } diff --git a/gcc/testsuite/gcc.dg/tree-ssa/evrp-ignore.c b/gcc/testsuite/gcc.dg/tree-ssa/evrp-ignore.c new file mode 100644 index 00000000000..9bfaed6a50a --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/evrp-ignore.c @@ -0,0 +1,28 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp -fno-tree-fre -fdisable-tree-ethread" } */ + +void kill(void); + +void foo (int x, int y, int z) +{ + // Establish y = [-INF, 54] + if (y < 55) + return; + + // Establish z == x + if (z != x) + return; + + // EVRP should transform this to if (0 != 0) + if (y < 30) + x = 0; + + // # x_1 = PHI + // The earlier transformation should make the edge from bb7 + // unexecutable, allowing x_1 == x_5 to be registered, and + // then fold away this condition as well. + if (x != z) + kill(); + +} +/* { dg-final { scan-tree-dump-not "kill" "evrp" } } */ diff --git a/gcc/vr-values.c b/gcc/vr-values.c index c999ca80f03..3b8d0674471 100644 --- a/gcc/vr-values.c +++ b/gcc/vr-values.c @@ -3454,6 +3454,32 @@ range_fits_type_p (const value_range *vr, return true; } +// Clear edge E of EDGE_EXECUTABLE (it is unexecutable). If it wasn't +// previously clear, propagate to successor blocks if appropriate. + +void +simplify_using_ranges::set_and_propagate_unexecutable (edge e) +{ + // If EXECUUTABLE is already clear, we're done. + if ((e->flags & EDGE_EXECUTABLE) == 0) + return; + + e->flags &= ~EDGE_EXECUTABLE; + + // Check if the destination block needs to propagate the property. + basic_block bb = e->dest; + + // If any entry edge is marked EXECUTABLE, we are done. + edge_iterator ei; + FOR_EACH_EDGE (e, ei, bb->preds) + if (e->flags & EDGE_EXECUTABLE) + return; + + // This block is also unexecutable, propagate to all exit edges as well. + FOR_EACH_EDGE (e, ei, bb->succs) + set_and_propagate_unexecutable (e); +} + /* If COND can be folded entirely as TRUE or FALSE, rewrite the conditional as such, and return TRUE. */ @@ -3467,18 +3493,27 @@ simplify_using_ranges::fold_cond (gcond *cond) if (TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME && TREE_CODE (gimple_cond_rhs (cond)) != SSA_NAME) return false; - + edge e0 = EDGE_SUCC (gimple_bb (cond), 0); + edge e1 = EDGE_SUCC (gimple_bb (cond), 1); if (r.zero_p ()) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "\nPredicate evaluates to: 0\n"); gimple_cond_make_false (cond); + if (e0->flags & EDGE_TRUE_VALUE) + set_and_propagate_unexecutable (e0); + else + set_and_propagate_unexecutable (e1); } else { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "\nPredicate evaluates to: 1\n"); gimple_cond_make_true (cond); + if (e0->flags & EDGE_FALSE_VALUE) + set_and_propagate_unexecutable (e0); + else + set_and_propagate_unexecutable (e1); } update_stmt (cond); return true; @@ -3769,7 +3804,7 @@ simplify_using_ranges::simplify_switch_using_ranges (gswitch *stmt) fprintf (dump_file, "removing unreachable case label\n"); } to_remove_edges.safe_push (e); - e->flags &= ~EDGE_EXECUTABLE; + set_and_propagate_unexecutable (e); e->flags |= EDGE_IGNORE; } diff --git a/gcc/vr-values.h b/gcc/vr-values.h index 7fdefef2fdf..46939081c61 100644 --- a/gcc/vr-values.h +++ b/gcc/vr-values.h @@ -66,6 +66,7 @@ private: tree vrp_evaluate_conditional_warnv_with_ops_using_ranges (enum tree_code, tree, tree, bool *, gimple *s); + void set_and_propagate_unexecutable (edge e); void cleanup_edges_and_switches (void); /* Vectors of edges that need removing and switch statements that -- 2.17.2