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

[Andrew MacLeod <amacleod@redhat.com>]

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


> The assume function can have many arguments (one is created for each
> automatic var referenced or set by the condition), so it would be nice to
> track all of them rather than just hardcoding the first.  And, the argument
> doesn't necessarily have to be a scalar, so perhaps later on we could derive
> ranges even for structure members etc. if needed.  Or just handle
> assume_function in IPA-SRA somehow at least.
>
> The C++23 paper mentions
> [[assume(size > 0)]];
> [[assume(size % 32 == 0)]];
> [[assume(std::isfinite(data[i]))]];
> [[assume(*pn >= 1)]];
> [[assume(i == 42)]];
> [[assume(++i == 43)]];
> [[assume((std::cin >> i, i == 42))]];
> [[assume(++almost_last == last)]];
> among other things, the first and fifth are already handled the
> if (!cond) __builtin_unreachable (); way and so work even without this
> patch, the (std::cin >> i, i == 42) case is not worth bothering for now
> and the rest would be single block assumptions that can be handled easily
> (except the last one which would have record type arguments and so we'd need
> SRA).
>
> 	Jakub
I put together an initial prototype, attached is the 2 patches so far. I 
applied this on top of one of your sets of patches to try it out.     
The first patch has the initial simple version, and the second patch 
hacks VRP to add a loop over all the ssa-names in the function and show 
what assume_range_p would  return for them.

First, I added another routine to ranger:

*bool gimple_ranger::assume_range_p (vrange &r, tree name)*

This is the routine that is called to determine what the range of NAME 
is at the end of the function if the function returns [1,1]. It is 
painfully simple, only working on names in the definition chain of the 
return variable. It returns TRUE if it finds a non-varying result.   I 
will next expand on this to look back in the CFG and be more flexible.

To apply any assumed values, I added a routine to be called

*bool query_assume_call (vrange &r, tree assume_id, tree name);*

This routine would be what is called to lookup if there is any range 
associated with NAME in the assume function ASSUME_ID.    I hacked one 
up to return [42, 42] for any integer query just for POC.  You'd need to 
supply this routine somewhere instead.

As the ASSUME function has no defs, we can't produce results for the 
parameters in normal ways, so I leverage the inferred range code.  When 
doing a stmt walk, when VRP is done processing a stmt, it applies any 
side effects of the statement going forward. The gimple_inferred_range 
constructor now also looks for assume calls, and calls query_assume_call 
() on each argument, and if it gets back TRUE, applies an inferred range 
record for that range at that stmt.  (This also means those ASSUME 
ranges will only show up in a VRP walk.)

These seems like it might be functional enough for you to experiment with.

For the simple

int
bar (int x)
{
   [[assume (++x == 43)]];
   return x;
}

The VRP hack for ther assume function shows :

for an assume function, x_2(D) would have a range of [irange] int [42, 
42] NONZERO 0x2a.

I also tried it for

bool foo1 (int x, int y) { return x < 10 || x > 20 || x == 12; }
or an assume function, x_5(D) would have a range of [irange] int [-INF, 
9][12, 12][21, +INF]


bool foo2 (int x, int y) { return (x >= 10 && x <= 20) || x == 2; }
for an assume function, x_5(D) would have a range of [irange] int [2, 
2][10, 20] NONZERO 0x1f

for:

int
bar (int x)
{
   [[assume (++x == 43)]];
   return x;
}

As for propagating assumed values, the hacked up version returning 42 
shows it propagates into the return:

query_assume_call injection
_Z3bari._assume.0 assume inferred range of x_1(D) to [irange] int [42, 
42] NONZERO 0x2a
int bar (int x)
{
   <bb 2> :
   .ASSUME (_Z3bari._assume.0, x_1(D));
   return 42;

}

So in principle, I think theres enough infrastructure there to get 
going.  You can query parameter ranges by creating a ranger, and 
querying the parameters via *assume_range_p () *.  You can do that 
anywhere, as the hack I put in vrp shows, it creates a new ranger, 
simply queries each SSA_NAME, then disposes of the ranger before 
invoking VRP on a fresh ranger.  The you just wire up a proper 
*query_assume_call(*) to return those ranges.

Thats the basic APi to deal with... call one function, supply another.  
Does this model seem like it would work OK for you?  Or do we need to 
tweak it?

I am planning to extend assume_range_p to handle other basic blocks, as 
well as pick up a few of the extra things that outgoing_edge_range_p does.

Andrew


PS. It also seems to me that the assume_range_p() infrastructure may 
have some other uses when it comes to inlining or LTO or IPA.    This 
particular version works with a return value of [1,1], but that value is 
manually supplied to GORI by the routine.  If any other pass has some 
reason to know that the return value was within a certain range, we 
could use that and query what the incoming ranges of any parameter might 
have to be. Just a thought.



[-- Attachment #2: 0002-Inferred-support-of-ASSUME.patch --]
[-- Type: text/x-patch, Size: 6264 bytes --]

From 0689fa587ed870e886ec5d6a0404ba20771b93c3 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Mon, 17 Oct 2022 10:23:55 -0400
Subject: [PATCH 2/3] Inferred support of ASSUME

---
 gcc/gimple-range-gori.h   |  6 ++---
 gcc/gimple-range-infer.cc | 50 +++++++++++++++++++++++++++++++++++++++
 gcc/gimple-range.cc       | 48 +++++++++++++++++++++++++++++++++++++
 gcc/gimple-range.h        |  1 +
 4 files changed, 102 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-infer.cc b/gcc/gimple-range-infer.cc
index f0d66d047a6..46a781c7826 100644
--- a/gcc/gimple-range-infer.cc
+++ b/gcc/gimple-range-infer.cc
@@ -36,6 +36,29 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimple-walk.h"
 #include "cfganal.h"
 
+
+// This routine should be provided to properly look up any
+// values of NAME that has been determined to have a value specified by
+// the function ASSUME_ID.    Return TRUE if it has a value and is NOT VARYING.
+
+// Given an ASSUME_ID name, return any range evaluated for NAME.
+
+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 && irange::supports_p (TREE_TYPE (name)))
+    {
+      int_range<2> f (build_int_cst (TREE_TYPE (name), 42),
+		      build_int_cst (TREE_TYPE (name), 42));
+      r = f;
+      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 +134,33 @@ gimple_infer_range::gimple_infer_range (gimple *s)
       // Fallthru and walk load/store ops now.
     }
 
+  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))
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index d67d6499c78..f9d6b73e4e8 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -483,6 +483,54 @@ gimple_ranger::register_inferred_ranges (gimple *s)
   m_cache.apply_inferred_ranges (s);
 }
 
+// This function is used to support the ASSUME keyword.  If the current
+// function returns an integral value, it will attempt to determine what
+// the range of NAME is if the funciton returns 1.  It will return TRUE
+// if it finds a non-varying range, otherwise FALSE.
+
+bool
+gimple_ranger::assume_range_p (vrange &r, tree name)
+{
+  bool result_p = false;
+  edge e;
+  edge_iterator ei;
+  basic_block exit_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
+  Value_Range tmp (TREE_TYPE (name));
+  r.set_undefined ();
+
+  FOR_EACH_EDGE (e, ei, exit_bb->preds)
+    {
+      result_p = false;
+      gimple_stmt_iterator gsi = gsi_last_nondebug_bb (e->src);
+      if (gsi_end_p (gsi))
+	break;
+      gimple *s = gsi_stmt (gsi);
+      if (!is_a<greturn *> (s))
+	break;
+      greturn *gret = as_a<greturn *> (s);
+      tree op = gimple_return_retval (gret);
+      if (!gimple_range_ssa_p (op))
+	break;
+      gimple *def = SSA_NAME_DEF_STMT (op);
+      if (!def || gimple_get_lhs (def) != op)
+	break;
+      tree lhs_type = TREE_TYPE (op);
+      if (!irange::supports_p (lhs_type))
+	break;
+      unsigned prec = TYPE_PRECISION (lhs_type);
+      int_range<2> lhs_range (lhs_type, wi::one (prec), wi::one (prec));
+      fur_stmt src (s, this);
+      if (gori ().compute_operand_range (tmp, def, lhs_range, name, src))
+	{
+	  r.union_ (tmp);
+	  result_p = true;
+	}
+    }
+  // If every exit predecessor does not calculate a value, we can
+  // assume nothing.
+  return result_p && !r.varying_p ();
+}
+
 // 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 8b2ff5685e5..3a6fdd9dbe0 100644
--- a/gcc/gimple-range.h
+++ b/gcc/gimple-range.h
@@ -61,6 +61,7 @@ public:
   auto_edge_flag non_executable_edge_flag;
   bool fold_stmt (gimple_stmt_iterator *gsi, tree (*) (tree));
   void register_inferred_ranges (gimple *s);
+  bool assume_range_p (vrange &r, tree name);
 protected:
   bool fold_range_internal (vrange &r, gimple *s, tree name);
   void prefill_name (vrange &r, tree name);
-- 
2.37.3


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

From e55fecddff5154116387e8f5ed678dd4fda81146 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 93482e5d102..120b9611bc7 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);
 
+  gimple_ranger *r2= enable_ranger (fun);
+  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);
+	    }
+	}
+    }
+  disable_ranger (fun);
+
   set_all_edges_as_executable (fun);
   gimple_ranger *ranger = enable_ranger (fun, false);
   rvrp_folder folder (ranger);
-- 
2.37.3