[gcc r13-3765] Add transitive inferred range processing.

[gcc r13-3765] Add transitive inferred range processing.

[Andrew Macleod]

https://gcc.gnu.org/g:c838119946c9f75f1e42f4320275355822cc86fc

commit r13-3765-gc838119946c9f75f1e42f4320275355822cc86fc
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Mon Nov 7 15:07:35 2022 -0500

    Add transitive inferred range processing.
    
    Rewalk statements at the end of a block to see if any inferred ranges
    affect earlier calculations and register those as inferred ranges.
    
            gcc/
            PR tree-optimization/104530
            * gimple-range-cache.cc (ranger_cache::register_inferred_value):
            New.  Split from:
            (ranger_cache::apply_inferred_ranges): Move setting cache to
            separate function.
            * gimple-range-cache.h (register_inferred_value): New prototype.
            * gimple-range-infer.cc (infer_range_manager::has_range_p): New.
            * gimple-range-infer.h (has_range_p): New prototype.
            * gimple-range.cc (register_transitive_inferred_ranges): New.
            * gimple-range.h (register_transitive_inferred_ranges): New proto.
            * tree-vrp.cc (rvrp_folder::fold_stmt): Check for transitive inferred
            ranges at the end of the block before folding final stmt.
    
            gcc/testsuite/
            * gcc.dg/pr104530.c: New.

Diff:
---
 gcc/gimple-range-cache.cc       | 36 +++++++++++++++++++------------
 gcc/gimple-range-cache.h        |  1 +
 gcc/gimple-range-infer.cc       | 11 ++++++++++
 gcc/gimple-range-infer.h        |  1 +
 gcc/gimple-range.cc             | 48 +++++++++++++++++++++++++++++++++++++++++
 gcc/gimple-range.h              |  1 +
 gcc/testsuite/gcc.dg/pr104530.c | 19 ++++++++++++++++
 gcc/tree-vrp.cc                 |  9 ++++++++
 8 files changed, 112 insertions(+), 14 deletions(-)

diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 89e2403acce..ce5a0c8155e 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -1544,8 +1544,27 @@ ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb,
   return true;
 }
 
-// This routine is used during a block walk to move the state of non-null for
-// any operands on stmt S to nonnull.
+// This routine will register an inferred value in block BB, and possibly
+// update the on-entry cache if appropriate.
+
+void
+ranger_cache::register_inferred_value (const vrange &ir, tree name,
+				       basic_block bb)
+{
+  Value_Range r (TREE_TYPE (name));
+  if (!m_on_entry.get_bb_range (r, name, bb))
+    exit_range (r, name, bb, RFD_READ_ONLY);
+  if (r.intersect (ir))
+    {
+      m_on_entry.set_bb_range (name, bb, r);
+      // If this range was invariant before, remove invariance.
+      if (!m_gori.has_edge_range_p (name))
+	m_gori.set_range_invariant (name, false);
+    }
+}
+
+// This routine is used during a block walk to adjust any inferred ranges
+// of operands on stmt S.
 
 void
 ranger_cache::apply_inferred_ranges (gimple *s)
@@ -1574,17 +1593,6 @@ ranger_cache::apply_inferred_ranges (gimple *s)
       tree name = infer.name (x);
       m_exit.add_range (name, bb, infer.range (x));
       if (update)
-	{
-	  Value_Range r (TREE_TYPE (name));
-	  if (!m_on_entry.get_bb_range (r, name, bb))
-	    exit_range (r, name, bb, RFD_READ_ONLY);
-	  if (r.intersect (infer.range (x)))
-	    {
-	      m_on_entry.set_bb_range (name, bb, r);
-	      // If this range was invariant before, remove invariance.
-	      if (!m_gori.has_edge_range_p (name))
-		m_gori.set_range_invariant (name, false);
-	    }
-	}
+	register_inferred_value (infer.range (x), name, bb);
     }
 }
diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h
index 45053b5873a..8e3ae8f58c6 100644
--- a/gcc/gimple-range-cache.h
+++ b/gcc/gimple-range-cache.h
@@ -87,6 +87,7 @@ public:
 
   void propagate_updated_value (tree name, basic_block bb);
 
+  void register_inferred_value (const vrange &r, tree name, basic_block bb);
   void apply_inferred_ranges (gimple *s);
   gori_compute m_gori;
   infer_range_manager m_exit;
diff --git a/gcc/gimple-range-infer.cc b/gcc/gimple-range-infer.cc
index 010b34a6bde..8714ef2ed41 100644
--- a/gcc/gimple-range-infer.cc
+++ b/gcc/gimple-range-infer.cc
@@ -252,6 +252,17 @@ infer_range_manager::get_nonzero (tree name)
   return *(m_nonzero[v]);
 }
 
+// Return TRUE if there are any range inferences in block BB.
+
+bool
+infer_range_manager::has_range_p (basic_block bb)
+{
+  if (bb->index >= (int)m_on_exit.length ())
+    return false;
+  bitmap b = m_on_exit[bb->index].m_names;
+  return b && !bitmap_empty_p (b);
+}
+
 // Return TRUE if NAME has a range inference in block BB.
 
 bool
diff --git a/gcc/gimple-range-infer.h b/gcc/gimple-range-infer.h
index adfe1fd8c69..10705e046d3 100644
--- a/gcc/gimple-range-infer.h
+++ b/gcc/gimple-range-infer.h
@@ -62,6 +62,7 @@ public:
   void add_range (tree name, basic_block bb, const vrange &r);
   void add_nonzero (tree name, basic_block bb);
   bool has_range_p (tree name, basic_block bb);
+  bool has_range_p (basic_block bb);
   bool maybe_adjust_range (vrange &r, tree name, basic_block bb);
 private:
   class exit_range_head
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index 806386918bd..2885d0fa21e 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -482,6 +482,54 @@ gimple_ranger::register_inferred_ranges (gimple *s)
   m_cache.apply_inferred_ranges (s);
 }
 
+// This function will walk the statements in BB to determine if any
+// discovered inferred ranges in the block have any transitive effects,
+// and if so, register those effects in BB.
+
+void
+gimple_ranger::register_transitive_inferred_ranges (basic_block bb)
+{
+  // Return if there are no inferred ranges in BB.
+  infer_range_manager &infer = m_cache.m_exit;
+  if (!infer.has_range_p (bb))
+    return;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Checking for transitive inferred ranges in BB %d\n",
+	     bb->index);
+
+  for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
+       gsi_next (&si))
+    {
+      gimple *s = gsi_stmt (si);
+      tree lhs = gimple_get_lhs (s);
+      // If the LHS alreayd has an inferred effect, leave it be.
+      if (!gimple_range_ssa_p (lhs) || infer.has_range_p (lhs, bb))
+	continue;
+      // Pick up global value.
+      Value_Range g (TREE_TYPE (lhs));
+      range_of_expr (g, lhs);
+
+      // If either dependency has an inferred range, check if recalculating
+      // the LHS is different than the global value. If so, register it as
+      // an inferred range as well.
+      Value_Range r (TREE_TYPE (lhs));
+      r.set_undefined ();
+      tree name1 = gori ().depend1 (lhs);
+      tree name2 = gori ().depend2 (lhs);
+      if ((name1 && infer.has_range_p (name1, bb))
+	  || (name2 && infer.has_range_p (name2, bb)))
+	{
+	  // Check if folding S produces a different result.
+	  if (fold_range (r, s, this) && g != r)
+	    {
+	      infer.add_range (lhs, bb, r);
+	      m_cache.register_inferred_value (r, lhs, bb);
+	    }
+	}
+    }
+}
+
 // When a statement S has changed since the result was cached, re-evaluate
 // and update the global cache.
 
diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h
index 22e05f645f8..dfe8199b8b0 100644
--- a/gcc/gimple-range.h
+++ b/gcc/gimple-range.h
@@ -62,6 +62,7 @@ public:
   auto_edge_flag non_executable_edge_flag;
   bool fold_stmt (gimple_stmt_iterator *gsi, tree (*) (tree));
   void register_inferred_ranges (gimple *s);
+  void register_transitive_inferred_ranges (basic_block bb);
 protected:
   bool fold_range_internal (vrange &r, gimple *s, tree name);
   void prefill_name (vrange &r, tree name);
diff --git a/gcc/testsuite/gcc.dg/pr104530.c b/gcc/testsuite/gcc.dg/pr104530.c
new file mode 100644
index 00000000000..1ec10154e1b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr104530.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp" } */
+
+void foo(void);
+
+static int a, *b = &a, c, d = 1;
+
+int main() {
+    c = 0 == b;
+    a = *b;
+    if (c % d)
+        for (; d; --d)
+            foo();
+    b = 0;
+}
+
+
+/* { dg-final { scan-tree-dump-not "foo" "evrp" } }  */
+
diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc
index 39f7eb7a75e..3393c73a7db 100644
--- a/gcc/tree-vrp.cc
+++ b/gcc/tree-vrp.cc
@@ -4501,6 +4501,15 @@ public:
 
   bool fold_stmt (gimple_stmt_iterator *gsi) override
   {
+    gimple *s = gsi_stmt (*gsi);
+    // If this is a block ending condition, and there are inferred ranges,
+    // reparse the block to see if there are any transitive inferred ranges.
+    if (is_a<gcond *> (s))
+      {
+	basic_block bb = gimple_bb (s);
+	if (bb && s == gimple_outgoing_range_stmt_p (bb))
+	  m_ranger->register_transitive_inferred_ranges (bb);
+      }
     bool ret = m_simplifier.simplify (gsi);
     if (!ret)
       ret = m_ranger->fold_stmt (gsi, follow_single_use_edges);