Re: [PATCH] middle-end, v4: IFN_ASSUME support [PR106654]

[Andrew MacLeod <amacleod@redhat.com>]

[-- Attachment #1.1: Type: text/plain, Size: 6575 bytes --]

On 10/17/22 11:44, Jakub Jelinek via Gcc-patches wrote:
>
> Added 2 tests for nested assumptions (one with a simple assumption
> nested in complex one, one with side-effects one nested in complex one).
>
> So far lightly tested, will test fully overnight.
>
> 2022-10-17  Jakub Jelinek<jakub@redhat.com>
>
OK, new prototype update.  I have moved the code to a new "class 
assume_query" which is still in gimple-range.h

We don't need all the heavy lifting of a full on ranger, just an 
ssa-name table and a gori_compute module.  GORI requires a range_query 
class, so assume_query derived form that.

patch1 is the same/similar infer processing that looks for assume calls 
and adds any ranges as a side effect. I removed the hack and now its 
simply returns whetever the global value is, so its no net effect.

patch2 is the assume_query class.  When created, it will "process" the 
current function up front. It currently only works on function with a 
single integral return statement.  It should never fail, it'll simpy 
return VARYING for anything it cant determine a value for, or if its an 
inappropriate function.

When its create, you can then query using

   bool assume_range_p (vrange &r, tree name);

the value of any ssa-name in the function.   They are all 
pre-calculated, so this is simply picking up any value that was saved.

So the good stuff! *Whats now supported?*  It begins with the return 
statement having a value of [1,1] and begins going back to defs, and 
evaluating any operands on that statement.

PHIs are now processed.
   - If an argument is symbolic, we try substituting the LHS for the 
argument, and go to its def.  continuing the process.
   - If an argument is a constant, we check if its compatible with the LHS.
       - If the intersection is undefined, then that edge cannot be 
executed, and it is ignored
       - if the is defined, then we examine the predecessor block to see 
if the exit condition which took this edge provides any useful into.

And finally, when the def chain terminates and we cant go any further, 
it also checks to see if this block has a single predecessor, and if so, 
if taking the edge to get here was the result of a condition that 
supplies yet more range info.

Caveats.  Im not doing a lot of error checking. If I encounter the 
definition of an ssa-name a second time, I simply stop.  This avoid 
infinite loops, and re-doing the same work.  Its unclear to me in a 
complex case if we might need to do some value merging at merge points, 
but at this point, we make no attempt.  I'd need to find a case where 
this was problematic, and I see none yet.

*What can you expect? *Using a testcase sample attr-assume-7.C  (and 
patch 3 which hacks VRP to spit out what values it would find)  it 
provides the following values:

bar()
   <bb 2> :
   x_3 = x_2(D) + 1;
   _4 = x_2(D) <= 41;
   return _4;
for an assume function, x_2(D) would have a range of [irange] int [-INF, 41]
for an assume function, _4 would have a range of [irange] bool [1, 1]

baz()
|<bb 2> :
   x_4 = x_3(D) + 1;
   w.0_7 = w;
   w.1_8 = w.0_7 + 1;
   w = w.1_8;
   if (x_4 == 51)
     goto <bb 3>; [INV]
   else
     goto <bb 4>; [INV]

   <bb 3> :
   // predicted unlikely by early return (on trees) predictor.
   goto <bb 9>; [INV]

   <bb 4> :
   if (x_4 == 53)
     goto <bb 5>; [INV]
   else
     goto <bb 6>; [INV]

   <bb 5> :
   // predicted unlikely by goto predictor.
   goto <bb 9>; [INV]

   <bb 6> :
   if (x_4 == 64)
     goto <bb 7>; [INV]
   else
     goto <bb 8>; [INV]

   <bb 7> :
   _12 = __cxa_allocate_exception (4);
   MEM[(int *)_12] = 1;
   __cxa_throw (_12, &_ZTIi, 0B);

   <bb 8> :
   _10 = x_4 == 43;

   <bb 9> :
   # _1 = PHI <0(3), _10(8), 0(5)>
   return _1;
for an assume function, _1 would have a range of [irange] bool [1, 1]
for an assume function, x_3(D) would have a range of [irange] int [42, 
42] NONZERO 0x2a
for an assume function, x_4 would have a range of [irange] int [43, 43] 
NONZERO 0x2b
for an assume function, _10 would have a range of [irange] bool [1, 1]

qux()
   <bb 2> :
   _4 = s.a;
   if (_4 == 42)
     goto <bb 3>; [INV]
   else
     goto <bb 4>; [INV]

   <bb 3> :
   _5 = s.b;
   if (_5 == 43)
     goto <bb 5>; [INV]
   else
     goto <bb 4>; [INV]

   <bb 4> :

   <bb 5> :
   # iftmp.2_1 = PHI <1(3), 0(4)>
   return iftmp.2_1;
for an assume function, iftmp.2_1 would have a range of [irange] bool [1, 1]
for an assume function, _4 would have a range of [irange] int [42, 42] 
NONZERO 0x2a
for an assume function, _5 would have a range of [irange] int [43, 43] 
NONZERO 0x2b

S::foo()
   <bb 2> :
   _5 = this_4(D)->a;
   if (_5 == 42)
     goto <bb 3>; [INV]
   else
     goto <bb 4>; [INV]

   <bb 3> :
   _6 = this_4(D)->b;
   if (_6 == 43)
     goto <bb 5>; [INV]
   else
     goto <bb 4>; [INV]

   <bb 4> :

   <bb 5> :
   # iftmp.3_1 = PHI <1(3), 0(4)>
   return iftmp.3_1;
for an assume function, iftmp.3_1 would have a range of [irange] bool [1, 1]
for an assume function, _5 would have a range of [irange] int [42, 42] 
NONZERO 0x2a
for an assume function, _6 would have a range of [irange] int [43, 43] 
NONZERO 0x2b

corge()
   <bb 2> :
   if (x_2(D) <= 41)
     goto <bb 4>; [INV]
   else
     goto <bb 3>; [INV]

   <bb 3> :
   __builtin_unreachable ();

   <bb 4> :
   _3 = x_2(D) >= -41;
   return _3;

for an assume function, x_2(D) would have a range of [irange] int [-41, 
+INF]
for an assume function, _3 would have a range of [irange] bool [1, 1]

---------------------------------------------------------------------------------------------------------

THis seems to provide a reasonable amount of functionality.  As you can 
see by the qux() and S:foo() cases, if you can figure out how to map 
structures and pointers as parameters, we can produce the ranges 
"produced" when they are loaded.  ie we know _4 is [42,42] and that it 
was loaded from s.a:
   _4 = s.a;

Presumably what is needed is a pass (which can be anywhere you want) 
which invokes an assume_query, and then tries to map the parameter 
values to ssa-names.

Anyway, gives you something to experiement with.   If you would find a 
different interface useful, let me know, or if there are limitations or 
other expansions we might need.   This seems like something reasonable 
for you to start working with?

Let me know what you think.   This all bootstraps fine, I could check it 
into the code base if it helps.

Andrew

[-- Attachment #2: 0001-Infer-support.patch --]
[-- Type: text/x-patch, Size: 2531 bytes --]

From 20805fb54aee0d0e337d53facf77a5c66f9f0c9c Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Tue, 18 Oct 2022 16:29:49 -0400
Subject: [PATCH 1/3] Infer support

---
 gcc/gimple-range-infer.cc | 48 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 48 insertions(+)

diff --git a/gcc/gimple-range-infer.cc b/gcc/gimple-range-infer.cc
index f0d66d047a6..95839445155 100644
--- a/gcc/gimple-range-infer.cc
+++ b/gcc/gimple-range-infer.cc
@@ -36,6 +36,25 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimple-walk.h"
 #include "cfganal.h"
 
+
+// This routine needs to be provided to look up any ASSUME values
+// for name in ASSUME_ID.    Return TRUE if it has a value.
+
+bool
+query_assume_call (vrange &r, tree assume_id, tree name)
+{
+  if (dump_file)
+    fprintf (dump_file, "query_assume_call injection\n");
+  if (assume_id != NULL_TREE)
+    {
+      // Just return the global value until this can be provided.
+      gimple_range_global (r, name);
+      return true;
+    }
+  return false;
+}
+
+
 // Adapted from infer_nonnull_range_by_dereference and check_loadstore
 // to process nonnull ssa_name OP in S.  DATA contains a pointer to a
 // stmt range inference instance.
@@ -111,6 +130,35 @@ gimple_infer_range::gimple_infer_range (gimple *s)
       // Fallthru and walk load/store ops now.
     }
 
+  // Look for ASSUME calls, and call query_assume_call for each argument
+  // to determine if there is any inferred range to be had.
+  if (is_a<gcall *> (s) && gimple_call_internal_p (s)
+      && gimple_call_internal_fn (s) == IFN_ASSUME)
+    {
+      tree assume_id = gimple_call_arg (s, 0);
+      for (unsigned i = 1; i < gimple_call_num_args (s); i++)
+	{
+	  tree op = gimple_call_arg (s, i);
+	  tree type = TREE_TYPE (op);
+	  if (gimple_range_ssa_p (op) && Value_Range::supports_type_p (type))
+	    {
+	      Value_Range assume_range (type);
+	      if (query_assume_call (assume_range, assume_id, op))
+		{
+		  add_range (op, assume_range);
+		  if (dump_file)
+		    {
+		      print_generic_expr (dump_file, assume_id, TDF_SLIM);
+		      fprintf (dump_file, " assume inferred range of ");
+		      print_generic_expr (dump_file, op, TDF_SLIM);
+		      fprintf (dump_file, " to ");
+		      assume_range.dump (dump_file);
+		      fputc ('\n', dump_file);
+		    }
+		}
+	    }
+	}
+    }
   // Look for possible non-null values.
   if (flag_delete_null_pointer_checks && gimple_code (s) != GIMPLE_ASM
       && !gimple_clobber_p (s))
-- 
2.37.3


[-- Attachment #3: 0002-assume_query-support.patch --]
[-- Type: text/x-patch, Size: 7704 bytes --]

From 3f3246d5f3297f61e96998a6bc87ec1e409238e5 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Tue, 18 Oct 2022 16:30:04 -0400
Subject: [PATCH 2/3] assume_query support

---
 gcc/gimple-range-gori.h |   6 +-
 gcc/gimple-range.cc     | 164 ++++++++++++++++++++++++++++++++++++++++
 gcc/gimple-range.h      |  17 +++++
 3 files changed, 184 insertions(+), 3 deletions(-)

diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h
index c7a32162a1b..6cc533b58b2 100644
--- a/gcc/gimple-range-gori.h
+++ b/gcc/gimple-range-gori.h
@@ -165,15 +165,15 @@ public:
   bool has_edge_range_p (tree name, basic_block bb = NULL);
   bool has_edge_range_p (tree name, edge e);
   void dump (FILE *f);
+  bool compute_operand_range (vrange &r, gimple *stmt, const vrange &lhs,
+			      tree name, class fur_source &src,
+			      value_relation *rel = NULL);
 private:
   bool refine_using_relation (tree op1, vrange &op1_range,
 			      tree op2, vrange &op2_range,
 			      fur_source &src, relation_kind k);
   bool may_recompute_p (tree name, edge e);
   bool may_recompute_p (tree name, basic_block bb = NULL);
-  bool compute_operand_range (vrange &r, gimple *stmt, const vrange &lhs,
-			      tree name, class fur_source &src,
-			      value_relation *rel = NULL);
   bool compute_operand_range_switch (vrange &r, gswitch *s, const vrange &lhs,
 				     tree name, fur_source &src);
   bool compute_operand1_range (vrange &r, gimple_range_op_handler &handler,
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index d67d6499c78..4befe724e38 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -645,3 +645,167 @@ disable_ranger (struct function *fun)
   delete fun->x_range_query;
   fun->x_range_query = NULL;
 }
+
+// ------------------------------------------------------------------------
+
+// If there is a non-varying value associated with NAME, return true and the
+// range in R.
+
+bool
+assume_query::assume_range_p (vrange &r, tree name)
+{
+  if (global.get_global_range (r, name))
+    return !r.varying_p ();
+  return false;
+}
+
+// Query used by GORI to pick up any known value on entry to a block.
+
+bool
+assume_query::range_of_expr (vrange &r, tree expr, gimple *stmt)
+{
+  if (!gimple_range_ssa_p (expr))
+    return get_tree_range (r, expr, stmt);
+
+  if (!global.get_global_range (r, expr))
+    r.set_varying (TREE_TYPE (expr));
+  return true;
+}
+
+// If the current function returns an integral value, and has a single return
+// statement, it will calculate any SSA_NAMES is can determine ranges forr
+// assuming the function returns 1.
+
+assume_query::assume_query ()
+{
+  basic_block exit_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
+  if (single_pred_p (exit_bb))
+    {
+      basic_block bb = single_pred (exit_bb);
+      gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
+      if (gsi_end_p (gsi))
+	return;
+      gimple *s = gsi_stmt (gsi);
+      if (!is_a<greturn *> (s))
+	return;
+      greturn *gret = as_a<greturn *> (s);
+      tree op = gimple_return_retval (gret);
+      if (!gimple_range_ssa_p (op))
+	return;
+      tree lhs_type = TREE_TYPE (op);
+      if (!irange::supports_p (lhs_type))
+	return;
+
+      unsigned prec = TYPE_PRECISION (lhs_type);
+      int_range<2> lhs_range (lhs_type, wi::one (prec), wi::one (prec));
+      global.set_global_range (op, lhs_range);
+
+      gimple *def = SSA_NAME_DEF_STMT (op);
+      if (!def || gimple_get_lhs (def) != op)
+	return;
+      fur_stmt src (gret, this);
+      calculate_stmt (def, lhs_range, src);
+    }
+}
+
+// Evaluate operand OP on statement S, using the provided LHS range.
+// If successful, set the range in the global table, then visit OP's def stmt.
+
+void
+assume_query::calculate_op (tree op, gimple *s, vrange &lhs, fur_source &src)
+{
+  Value_Range op_range (TREE_TYPE (op));
+  if (!global.get_global_range (op_range, op)
+      && m_gori.compute_operand_range (op_range, s, lhs, op, src)
+      && !op_range.varying_p ())
+    {
+      global.set_global_range (op, op_range);
+      gimple *def_stmt = SSA_NAME_DEF_STMT (op);
+      if (def_stmt && gimple_get_lhs (def_stmt) == op)
+	calculate_stmt (def_stmt, op_range, src);
+    }
+}
+
+// Evaluate PHI statement, using the provided LHS range.
+// Check each constant argument predecessor if it can be taken
+// provide LHS to any symbolic argmeuents, and process their def statements.
+
+void
+assume_query::calculate_phi (gphi *phi, vrange &lhs_range, fur_source &src)
+{
+  for (unsigned  x= 0; x < gimple_phi_num_args (phi); x++)
+    {
+      tree arg = gimple_phi_arg_def (phi, x);
+      Value_Range arg_range (TREE_TYPE (arg));
+      if (gimple_range_ssa_p (arg))
+	{
+	  // A symbol arg will be the LHS value.
+	  arg_range = lhs_range;
+	  range_cast (arg_range, TREE_TYPE (arg));
+	  if (!global.get_global_range (arg_range, arg))
+	    {
+	      global.set_global_range (arg, arg_range);
+	      gimple *def_stmt = SSA_NAME_DEF_STMT (arg);
+	      if (def_stmt && gimple_get_lhs (def_stmt) == arg)
+		calculate_stmt (def_stmt, arg_range, src);
+	    }
+	}
+      else
+	{
+	  if (get_tree_range (arg_range, arg, NULL))
+	    {
+	      // If this is a constant value that differs from LHS, this
+	      // edge cannot be taken.
+	      arg_range.intersect (lhs_range);
+	      if (arg_range.undefined_p ())
+		continue;
+	      // Otherwise Check the condition feeding this edge
+	      edge e = gimple_phi_arg_edge (phi, x);
+	      check_taken_edge (e, src);
+	    }
+	}
+    }
+}
+
+// If an edge is known to be taken, examine the outgoing edge to see
+// if it carries any range information that can also be evaluated.
+
+void
+assume_query::check_taken_edge (edge e, fur_source &src)
+{
+  gimple *stmt = gimple_outgoing_range_stmt_p (e->src);
+  if (stmt && is_a<gcond *> (stmt))
+    {
+      int_range<2> cond;
+      gcond_edge_range (cond, e);
+      calculate_stmt (stmt, cond, src);
+    }
+}
+
+// Evaluate statement S which produces range LHS_RANGE.
+
+void
+assume_query::calculate_stmt (gimple *s, vrange &lhs_range, fur_source &src)
+{
+  gimple_range_op_handler handler (s);
+  if (handler)
+    {
+      tree op = gimple_range_ssa_p (handler.operand1 ());
+      if (op)
+	calculate_op (op, s, lhs_range, src);
+      op = gimple_range_ssa_p (handler.operand2 ());
+      if (op)
+	calculate_op (op, s, lhs_range, src);
+    }
+  else if (is_a<gphi *> (s))
+    {
+      calculate_phi (as_a<gphi *> (s), lhs_range, src);
+      // Don't further check predecessors of blocks with PHIs.
+      return;
+    }
+
+  // Even if the walk back terminates before the top, if this is a single
+  // predecessor block, see if the predecessor provided any ranges to get here.
+  if (single_pred_p (gimple_bb (s)))
+    check_taken_edge (single_pred_edge (gimple_bb (s)), src);
+}
diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h
index 8b2ff5685e5..4dc7bc33c5f 100644
--- a/gcc/gimple-range.h
+++ b/gcc/gimple-range.h
@@ -80,4 +80,21 @@ extern gimple_ranger *enable_ranger (struct function *m,
 				     bool use_imm_uses = true);
 extern void disable_ranger (struct function *);
 
+class assume_query : public range_query
+{
+public:
+  assume_query ();
+  bool assume_range_p (vrange &r, tree name);
+  virtual bool range_of_expr (vrange &r, tree expr, gimple * = NULL);
+protected:
+  void calculate_stmt (gimple *s, vrange &lhs_range, fur_source &src);
+  void calculate_op (tree op, gimple *s, vrange &lhs, fur_source &src);
+  void calculate_phi (gphi *phi, vrange &lhs_range, fur_source &src);
+  void check_taken_edge (edge e, fur_source &src);
+
+  ssa_global_cache global;
+  gori_compute m_gori;
+};
+
+
 #endif // GCC_GIMPLE_RANGE_H
-- 
2.37.3


[-- Attachment #4: 0003-Show-output.patch --]
[-- Type: text/x-patch, Size: 1388 bytes --]

From 4d920bd7ae68f04cb387875f71695503f4db86ae Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Mon, 17 Oct 2022 12:28:21 -0400
Subject: [PATCH 3/3] Show output

---
 gcc/tree-vrp.cc | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)

diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc
index 1adb15c9934..3c0d5c43215 100644
--- a/gcc/tree-vrp.cc
+++ b/gcc/tree-vrp.cc
@@ -4345,6 +4345,30 @@ execute_ranger_vrp (struct function *fun, bool warn_array_bounds_p)
   scev_initialize ();
   calculate_dominance_info (CDI_DOMINATORS);
 
+  assume_query *r2 = new assume_query ();
+  for (unsigned i = 0; i < num_ssa_names; i++)
+    {
+      tree name = ssa_name (i);
+      if (!name || !gimple_range_ssa_p (name))
+	continue;
+      tree type = TREE_TYPE (name);
+      if (!Value_Range::supports_type_p (type))
+	continue;
+      Value_Range assume_range (type);
+      if (r2->assume_range_p (assume_range, name))
+	{
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "for an assume function, ");
+	      print_generic_expr (dump_file, name, TDF_SLIM);
+	      fprintf (dump_file, " would have a range of ");
+	      assume_range.dump (dump_file);
+	      fputc ('\n', dump_file);
+	    }
+	}
+    }
+  delete r2;
+
   set_all_edges_as_executable (fun);
   gimple_ranger *ranger = enable_ranger (fun, false);
   rvrp_folder folder (ranger);
-- 
2.37.3