[COMMITTED] PR tree-optimization/104530 - Add transitive inferred range processing.

[COMMITTED] PR tree-optimization/104530 - Add transitive inferred range processing.

[Andrew MacLeod]

[-- Attachment #1: Type: text/plain, Size: 2129 bytes --]

During VRP block walk, global ranges are "finalized" during the walk.  
The statement will never be revisited, so the global becomes unchanging.

we add inferred ranges when operands of a statement imply further value 
restrictions.  The most common of these is a de-reference of a pointer 
implies non-null.

These inferred ranges can potentially have transitive effects on values 
which have already been calculated. Its a form of recalculation, but 
only effects things after the inferred range. ie:

   b.0_1 = b;
   _2 = b.0_1 == 0B;  // _2 global range is [0,1]
   _3 = (int) _2;       // _3 global range is [0,1]
   c = _3;
   _5 = *b.0_1;      // b.0_1 is now [1, +INF]
   a = _5;
   d.3_7 = d;
   _8 = _3 % d.3_7;
   if (_8 != 0)

after the assignment to _5, b.0_1 has a inferred range of non-zero.

when we evaluate _8, we only know that _3 is [0,1], therefore _8 is 
[0,1]  and we cannot fold the following condition.

This patch introduces a check before we evaluate the final condition 
where we check if any inferred ranges introduced in the block affect any 
of the global values that were calculated.  If they do, the stateemnt is 
reevalauted using the inferred ranges, and if the result is better, that 
range is also added as a "transitive" inferred range.

In the above case, we register the inferred range for b.0_1:

    on-exit update b.0_1 in BB2 : [irange] int * [1, +INF]

And then before evaluating the final condition, make a pass thru the 
block and add the "transitive" inferred ranges:

Checking for transitive inferred ranges in BB 2
    on-exit update _2 in BB2 : [irange] _Bool [0, 0] NONZERO 0x0
    on-exit update _3 in BB2 : [irange] int [0, 0] NONZERO 0x0
    on-exit update _8 in BB2 : [irange] int [0, 0] NONZERO 0x0

which then allows us to fold the statement without impacting the global 
values.

Inferred ranges are available to all on-exit calculations, and thus will 
feed any following blocks.

Performance is reasonable, with a less than 1% hit to VRP, and 0.03% 
overall.

Bootstrapped on x86_64-pc-linux-gnu with no regeressions. Pushed.

Andrew

[-- Attachment #2: 540.diff --]
[-- Type: text/x-patch, Size: 8302 bytes --]

commit c838119946c9f75f1e42f4320275355822cc86fc
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 --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);