From 73cf73af2392e00917de042a4692f6a0b6329ee8 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
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<gcond *> (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 <x_5(D)(6), 0(7)>
+  // 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

