[COMMITTED] PR c++/106654 - Add assume support to VRP.

[COMMITTED] PR c++/106654 - Add assume support to VRP.

[Andrew MacLeod]

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

This patch adds basic support for ASSUME functions to VRP.

Based on the previous set of patches, Ive cleaned them up, and this 
provides the basic support from rangers generalized model. It does not 
support non-ssa name parameters, I think you might be on your own for that.

I modified Jakubs assumption pass to use GORI to query parameter rangers 
in assumption functions and set the global range for those, and then 
ranger's infer infrastructure is used to inject these rangers at assume 
call locations in VRP.

I also added an optimization testcase that tests the basic functionality 
in VRP2.  For instance it can reduce:

int
f2 (int x, int y, int z)
{
   [[assume (x+12 == 14 && y >= 0 && y + 10 < 13 && z + 4 >= 4 && z - 2 
< 18)]];
   unsigned q = x + y + z;
   if (q*2 > 46)
     return 0;
   return 1;
}

to:

return 1;


Its good to get us going, bt I think theres still lots of room for 
improvement.

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

Andrew


[-- Attachment #2: 0001-Add-assume-support-to-VRP.patch --]
[-- Type: text/x-patch, Size: 15788 bytes --]

From 53e6d7a3102409f0f2a5a9ffbfbeaa62c135d991 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Tue, 18 Oct 2022 16:29:49 -0400
Subject: [PATCH] Add assume support to VRP.

This provides an assume_query class using rangers GORI module to
determine what ranges would be applied to any SSA NAMES in the function
if the return value were [1, 1].  Any parameter ranges are stored in
the SSA_NAME_RANGE_INFO field, and ranger's inferred range machinery is
then used to look these up and match them to assume call parameteres
in the bodies of other functions..

        PR c++/106654
	gcc/
	* gimple-range-gori.h (compute_operand_range): Make public.
	* gimple-range-infer.cc (gimple_infer_range::check_assume_func): New.
	(gimple_infer_range::gimple_infer_range): Check for assume calls.
	* gimple-range-infer.h (check_assume_func): Add prototype.
	* gimple-range.cc (assume_query::assume_range_p): New.
	(assume_query::range_of_expr): New.
	(assume_query::assume_query): New.
	(assume_query::calculate_op): New.
	(assume_query::calculate_phi): New.
	(assume_query::check_taken_edge): New.
	(assume_query::calculate_stmt): New.
	(assume_query::dump): New.
	* gimple-range.h (class assume_query): New.
	* tree-vrp.cc (pass_assumptions::execute): Add processing.

	gcc/testsuite/
	* g++.dg/cpp23/attr-assume-opt.C: New.
---
 gcc/gimple-range-gori.h                      |   6 +-
 gcc/gimple-range-infer.cc                    |  54 ++++++
 gcc/gimple-range-infer.h                     |   1 +
 gcc/gimple-range.cc                          | 190 +++++++++++++++++++
 gcc/gimple-range.h                           |  18 ++
 gcc/testsuite/g++.dg/cpp23/attr-assume-opt.C |  42 ++++
 gcc/tree-vrp.cc                              |  34 ++++
 7 files changed, 342 insertions(+), 3 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/cpp23/attr-assume-opt.C

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..010b34a6bde 100644
--- a/gcc/gimple-range-infer.cc
+++ b/gcc/gimple-range-infer.cc
@@ -35,6 +35,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimple-iterator.h"
 #include "gimple-walk.h"
 #include "cfganal.h"
+#include "tree-dfa.h"
 
 // Adapted from infer_nonnull_range_by_dereference and check_loadstore
 // to process nonnull ssa_name OP in S.  DATA contains a pointer to a
@@ -56,6 +57,54 @@ non_null_loadstore (gimple *, tree op, tree, void *data)
   return false;
 }
 
+// Process an ASSUME call to see if there are any inferred ranges available.
+
+void
+gimple_infer_range::check_assume_func (gcall *call)
+{
+  tree arg;
+  unsigned i;
+  tree assume_id = TREE_OPERAND (gimple_call_arg (call, 0), 0);
+  if (!assume_id)
+    return;
+  struct function *fun = DECL_STRUCT_FUNCTION (assume_id);
+  if (!fun)
+    return;
+  // Loop over arguments, matching them to the assume paramters.
+  for (arg = DECL_ARGUMENTS (assume_id), i = 1;
+       arg && i < gimple_call_num_args (call);
+       i++, arg = DECL_CHAIN (arg))
+    {
+      tree op = gimple_call_arg (call, i);
+      tree type = TREE_TYPE (op);
+      if (gimple_range_ssa_p (op) && Value_Range::supports_type_p (type))
+	{
+	  tree default_def = ssa_default_def (fun, arg);
+	  if (!default_def || type != TREE_TYPE (default_def))
+	    continue;
+	  // Query the global range of the default def in the assume function.
+	  Value_Range assume_range (type);
+	  global_ranges.range_of_expr (assume_range, default_def);
+	  // If there is a non-varying result, add it as an inferred range.
+	  if (!assume_range.varying_p ())
+	    {
+	      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, " (param ");
+		  print_generic_expr (dump_file, arg, TDF_SLIM);
+		  fprintf (dump_file, ") = ");
+		  assume_range.dump (dump_file);
+		  fputc ('\n', dump_file);
+		}
+	    }
+	}
+    }
+}
+
 // Add NAME and RANGE to the range inference summary.
 
 void
@@ -111,6 +160,11 @@ gimple_infer_range::gimple_infer_range (gimple *s)
       // Fallthru and walk load/store ops now.
     }
 
+  // Check for inferred ranges from ASSUME calls.
+  if (is_a<gcall *> (s) && gimple_call_internal_p (s)
+      && gimple_call_internal_fn (s) == IFN_ASSUME)
+    check_assume_func (as_a<gcall *> (s));
+
   // 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-infer.h b/gcc/gimple-range-infer.h
index 468b7d11286..adfe1fd8c69 100644
--- a/gcc/gimple-range-infer.h
+++ b/gcc/gimple-range-infer.h
@@ -40,6 +40,7 @@ public:
   void add_range (tree name, vrange &range);
   void add_nonzero (tree name);
 private:
+  void check_assume_func (gcall *call);
   unsigned num_args;
   static const int size_limit = 10;
   tree m_names[size_limit];
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index d67d6499c78..058439733ee 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -645,3 +645,193 @@ 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 (m_gori.compute_operand_range (op_range, s, lhs, op, src)
+      && !op_range.varying_p ())
+    {
+      Value_Range range (TREE_TYPE (op));
+      if (global.get_global_range (range, op))
+	op_range.intersect (range);
+      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);
+}
+
+// Show everything that was calculated.
+
+void
+assume_query::dump (FILE *f)
+{
+  fprintf (f, "Assumption details calculated:\n");
+  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 (assume_range_p (assume_range, name))
+	{
+	  print_generic_expr (f, name, TDF_SLIM);
+	  fprintf (f, " -> ");
+	  assume_range.dump (f);
+	  fputc ('\n', f);
+	}
+    }
+  fprintf (f, "------------------------------\n");
+}
diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h
index 8b2ff5685e5..4800bfbf890 100644
--- a/gcc/gimple-range.h
+++ b/gcc/gimple-range.h
@@ -80,4 +80,22 @@ 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);
+  void dump (FILE *f);
+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
diff --git a/gcc/testsuite/g++.dg/cpp23/attr-assume-opt.C b/gcc/testsuite/g++.dg/cpp23/attr-assume-opt.C
new file mode 100644
index 00000000000..88d5e78dbba
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp23/attr-assume-opt.C
@@ -0,0 +1,42 @@
+// P1774R8 - Portable assumptions
+// { dg-do compile { target c++11 } }
+// { dg-options "-O2 -fdump-tree-vrp2" }
+// Test the we can optimize based on conditions in assume.
+
+int
+f1 (unsigned x, unsigned y, unsigned z)
+{
+  [[assume (x == 2 && y < 3 && z < 20)]];
+  unsigned q = x + y + z;
+  if (q > 23)
+    return 0;
+  return 1;
+}
+
+
+int
+f2 (int x, int y, int z)
+{
+  [[assume (x+12 == 14 && y >= 0 && y + 10 < 13 && z + 4 >= 4 && z - 2 < 18)]];
+  unsigned q = x + y + z;
+  if (q*2 > 46)
+    return 0;
+  return 1;
+}
+
+int
+f3 (int x, int y, int z)
+{
+  [[assume (x + 12 == 14 && z / 2 > 0)]];
+  [[assume (y >= 0 && z - 2 < 18)]];
+  [[assume (y + 10 < 13 && z + 4 >= 2)]];
+  int q = x + y + z;
+  if (q * 2 > 46)
+    return 0;
+  if (z < 0)
+    return 0;
+  return 1;
+}
+
+/* { dg-final { scan-tree-dump-times "return 0" 0 "vrp2" } } */
+/* { dg-final { scan-tree-dump-times "return 1" 3 "vrp2" } } */
diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc
index 1adb15c9934..e5a292bb875 100644
--- a/gcc/tree-vrp.cc
+++ b/gcc/tree-vrp.cc
@@ -50,6 +50,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimple-range-path.h"
 #include "value-pointer-equiv.h"
 #include "gimple-fold.h"
+#include "tree-dfa.h"
 
 /* Set of SSA names found live during the RPO traversal of the function
    for still active basic-blocks.  */
@@ -4465,6 +4466,39 @@ public:
   bool gate (function *fun) final override { return fun->assume_function; }
   unsigned int execute (function *) final override
     {
+      assume_query query;
+      if (dump_file)
+	fprintf (dump_file, "Assumptions :\n--------------\n");
+
+      for (tree arg = DECL_ARGUMENTS (cfun->decl); arg; arg = DECL_CHAIN (arg))
+	{
+	  tree name = ssa_default_def (cfun, arg);
+	  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 (query.assume_range_p (assume_range, name))
+	    {
+	      // Set the global range of NAME to anything calculated.
+	      set_range_info (name, assume_range);
+	      if (dump_file)
+		{
+		  print_generic_expr (dump_file, name, TDF_SLIM);
+		  fprintf (dump_file, " -> ");
+		  assume_range.dump (dump_file);
+		  fputc ('\n', dump_file);
+		}
+	    }
+	}
+      if (dump_file)
+	{
+	  fputc ('\n', dump_file);
+	  gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
+	  if (dump_flags & TDF_DETAILS)
+	    query.dump (dump_file);
+	}
       return TODO_discard_function;
     }
 
-- 
2.37.3

Re: [COMMITTED] PR c++/106654 - Add assume support to VRP.

[Jakub Jelinek]

On Wed, Oct 19, 2022 at 08:37:57PM -0400, Andrew MacLeod wrote:
> This patch adds basic support for ASSUME functions to VRP.
> 
> Based on the previous set of patches, Ive cleaned them up, and this provides
> the basic support from rangers generalized model. It does not support
> non-ssa name parameters, I think you might be on your own for that.
> 
> I modified Jakubs assumption pass to use GORI to query parameter rangers in
> assumption functions and set the global range for those, and then ranger's
> infer infrastructure is used to inject these rangers at assume call
> locations in VRP.
> 
> I also added an optimization testcase that tests the basic functionality in
> VRP2.  For instance it can reduce:
> 
> int
> f2 (int x, int y, int z)
> {
>   [[assume (x+12 == 14 && y >= 0 && y + 10 < 13 && z + 4 >= 4 && z - 2 <
> 18)]];
>   unsigned q = x + y + z;
>   if (q*2 > 46)
>     return 0;
>   return 1;
> }
> 
> to:
> 
> return 1;
> 
> 
> Its good to get us going, bt I think theres still lots of room for
> improvement.
> 
> Bootstraps on x86_64-pc-linux-gnu with no regressions.  Pushed.

Thanks.

	Jakub