[gcc r13-3394] Add assume support to VRP.

[gcc r13-3394] Add assume support to VRP.

[Andrew Macleod]

https://gcc.gnu.org/g:53e6d7a3102409f0f2a5a9ffbfbeaa62c135d991

commit r13-3394-g53e6d7a3102409f0f2a5a9ffbfbeaa62c135d991
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Tue Oct 18 16:29:49 2022 -0400

    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.

Diff:
---
 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(-)

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;
     }