From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1011) id 4A42F3858425; Mon, 20 Sep 2021 21:59:33 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 4A42F3858425 MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Andrew Macleod To: gcc-cvs@gcc.gnu.org Subject: [gcc r12-3718] Use EDGE_EXECUTABLE in ranger and return UNDEFINED for those edges. X-Act-Checkin: gcc X-Git-Author: Andrew MacLeod X-Git-Refname: refs/heads/master X-Git-Oldrev: 5d110fe90afcd850ea21aee6429f22edd6b1b592 X-Git-Newrev: 73cf73af2392e00917de042a4692f6a0b6329ee8 Message-Id: <20210920215933.4A42F3858425@sourceware.org> Date: Mon, 20 Sep 2021 21:59:33 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 20 Sep 2021 21:59:33 -0000 https://gcc.gnu.org/g:73cf73af2392e00917de042a4692f6a0b6329ee8 commit r12-3718-g73cf73af2392e00917de042a4692f6a0b6329ee8 Author: Andrew MacLeod Date: Tue Aug 24 12:13:24 2021 -0400 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. Diff: --- 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(-) 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