[COMMITTED] Update range query cache when a statement is updated.

[COMMITTED] Update range query cache when a statement is updated.

[Andrew MacLeod]

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

Whenever the IL changes under ranger, its possible the resulting range 
calculation could be different. Once cached, we don't really recalculate 
ranges unless we can detect an input range has caused the result to go 
stale.

Simplification and folding can both change the IL in such a way that the 
result can be refined, but it is not obvious to ranger. Ive been looking 
at a case from glibc (I finally produced a reduced testcase which I 
included) where the original IL is

  __message_length_90 = __builtin_strlen (iftmp.39_117);

for which which we calculate a range:

   [irange] size_t [0, 9223372036854775805] NONZERO 0x7fffffffffffffff

Then in vrp1, simplification at the last second changes the IL to:

  __message_length_90 = 52;

but range has no way to know this has happened, and continues with the 
original range.  This eventually feeds

_39 = __builtin_constant_p (__message_length_90);

and if we are not aware of the new range, we fold this builtin the wrong 
way.  Then a function with no linkage that should have been removed 
remains in the object, and glibc builds break. doh.


I've been looking at various alternatives, none of which I liked much.  
I tried a final re-evaluation every time we looked at a stmt for the 
last time in VRP, but that was a 20% penalty. yuck.

What I finally settled on is simple and effective for all passes.  ssa 
has an update_stmt() call which is invoked to ensure all the 
ssa-operands are updated properly when the IL changes.  I added an 
update_stmt call to the generic range_query (which does nothing), then 
overload it in ranger to force a recalculation of the statement, and 
update the global value only if it changes as a result.

THis solves the problem elegantly, and will be applicable no matter 
where and how the IL changes.  The overhead of adding the call to 
update_stmt is very minute..  0.01% overall, and the VRP pass itself 
only slows down by 0.3%.

And this should allow glibc to build again.

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

Andrew

[-- Attachment #2: 0001-Update-range-query-cache-when-a-statement-is-updated.patch --]
[-- Type: text/x-patch, Size: 5202 bytes --]

From 6fd485d15c1a2c427c39bcd45e03bed8cde689e6 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Wed, 2 Nov 2022 21:37:49 -0400
Subject: [PATCH] Update range query cache when a statement is updated.

Add an update_stmt interface to range query, and hook into it with the
ssa statement update call.

	gcc/
	* gimple-range.cc (gimple_ranger::update_stmt): New.
	* gimple-range.h (gimple_ranger::update_stmt): New prototype.
	* tree-ssa-operands.cc (update_stmt_operands): Notify range
	query that stmt has changed.
	* value-query.h (range_query::update_stmt): New.

	gcc/testsuite/
	* gcc.dg/tree-ssa/vrp-update.c: New.
---
 gcc/gimple-range.cc                        | 34 ++++++++++++++++++++++
 gcc/gimple-range.h                         |  1 +
 gcc/testsuite/gcc.dg/tree-ssa/vrp-update.c | 21 +++++++++++++
 gcc/tree-ssa-operands.cc                   |  3 ++
 gcc/value-query.h                          |  3 ++
 5 files changed, 62 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp-update.c

diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index 110cf574454..806386918bd 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -482,6 +482,40 @@ gimple_ranger::register_inferred_ranges (gimple *s)
   m_cache.apply_inferred_ranges (s);
 }
 
+// When a statement S has changed since the result was cached, re-evaluate
+// and update the global cache.
+
+void
+gimple_ranger::update_stmt (gimple *s)
+{
+  tree lhs = gimple_get_lhs (s);
+  if (!lhs || !gimple_range_ssa_p (lhs))
+    return;
+  Value_Range r (TREE_TYPE (lhs));
+  // Only update if it already had a value.
+  if (m_cache.get_global_range (r, lhs))
+    {
+      // Re-calculate a new value using just cache values.
+      Value_Range tmp (TREE_TYPE (lhs));
+      fold_using_range f;
+      fur_depend src (s, &(gori ()), &m_cache);
+      f.fold_stmt (tmp, s, src, lhs);
+
+      // Combine the new value with the old value to check for a change.
+      if (r.intersect (tmp))
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      print_generic_expr (dump_file, lhs, TDF_SLIM);
+	      fprintf (dump_file, " : global value re-evaluated to ");
+	      r.dump (dump_file);
+	      fputc ('\n', dump_file);
+	    }
+	  m_cache.set_global_range (lhs, r);
+	}
+    }
+}
+
 // This routine will export whatever global ranges are known to GCC
 // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields.
 
diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h
index 4800bfbf890..22e05f645f8 100644
--- a/gcc/gimple-range.h
+++ b/gcc/gimple-range.h
@@ -51,6 +51,7 @@ public:
   virtual bool range_of_stmt (vrange &r, gimple *, tree name = NULL) override;
   virtual bool range_of_expr (vrange &r, tree name, gimple * = NULL) override;
   virtual bool range_on_edge (vrange &r, edge e, tree name) override;
+  virtual void update_stmt (gimple *) override;
   void range_on_entry (vrange &r, basic_block bb, tree name);
   void range_on_exit (vrange &r, basic_block bb, tree name);
   void export_global_ranges ();
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-update.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp-update.c
new file mode 100644
index 00000000000..9e5da8890c4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-update.c
@@ -0,0 +1,21 @@
+/* { dg-options "-O2 -fdump-tree-vrp1 " } */
+
+/* Tests that calls to update_stmt by the folder will also update ranger's
+   cache value and produce the correct result for the builtin_constant_p
+   function.  */
+
+void dead ();
+
+void foo( void *_thrdescr, int _result)
+{
+  const char *lossage = _result ? "constant string" : 0;
+
+  if (__builtin_expect (lossage != ((void *)0) , 0))
+    {
+    unsigned __message_length = __builtin_strlen (lossage);
+    if (! __builtin_constant_p (__message_length))
+      dead ();
+    }
+}
+
+/* { dg-final { scan-tree-dump-not "dead" "vrp1" } } */
diff --git a/gcc/tree-ssa-operands.cc b/gcc/tree-ssa-operands.cc
index 4915622e163..9e85998b75e 100644
--- a/gcc/tree-ssa-operands.cc
+++ b/gcc/tree-ssa-operands.cc
@@ -30,6 +30,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "stmt.h"
 #include "print-tree.h"
 #include "dumpfile.h"
+#include "value-query.h"
 
 
 /* This file contains the code required to manage the operands cache of the
@@ -1146,6 +1147,8 @@ update_stmt_operands (struct function *fn, gimple *stmt)
   gcc_assert (gimple_modified_p (stmt));
   operands_scanner (fn, stmt).build_ssa_operands ();
   gimple_set_modified (stmt, false);
+  // Inform the active range query an update has happened.
+  get_range_query (fn)->update_stmt (stmt);
 
   timevar_pop (TV_TREE_OPS);
 }
diff --git a/gcc/value-query.h b/gcc/value-query.h
index fc638eb76b1..b8e6fedfb28 100644
--- a/gcc/value-query.h
+++ b/gcc/value-query.h
@@ -93,6 +93,9 @@ public:
   virtual bool range_on_edge (vrange &r, edge, tree expr);
   virtual bool range_of_stmt (vrange &r, gimple *, tree name = NULL);
 
+  // When the IL in a stmt is changed, call this for better results.
+  virtual void update_stmt (gimple *) { }
+
   // Query if there is any relation between SSA1 and SSA2.
   relation_kind query_relation (gimple *s, tree ssa1, tree ssa2,
 				bool get_range = true);
-- 
2.37.3