[PATCH 1/2] Implement generic expression evaluator for range_query.

[PATCH 1/2] Implement generic expression evaluator for range_query.

[Aldy Hernandez]

Right now, range_of_expr only works with constants, SSA names, and
pointers.  Anything else gets returned as VARYING.  This patch adds the
capability to deal with arbitrary expressions, inasmuch as these
tree codes are implemented in range-ops.cc.

This will give us the ability to ask for the range of any tree expression,
not just constants and SSA names, with range_of_expr().

This is a more generic implementation of determine_value_range in VRP.
A follow-up patch will remove all uses of it in favor of the
range_query API.

Tested on x86-64 Linux.

OK?

gcc/ChangeLog:

	* function-tests.c (test_ranges): Call gimple_range_tests.
	* gimple-range-gori.cc (gori_compute::expr_range_at_stmt): Use
	get_global_range_query instead of get_tree_range.
	* gimple-range.cc (fur_source::get_operand): Add argument to
	get_tree_range.
	(get_arith_expr_range): New.
	(get_tree_range): Add gimple and range_query arguments.
	Call get_arith_expr_range.
	(gimple_ranger::range_of_expr): Add argument to get_tree_range.
	Include gimple-range-tests.cc.
	* gimple-range.h (get_tree_range): Add argument.
	* selftest.h (gimple_range_tests): New.
	* value-query.cc (global_range_query::range_of_expr): Add
	argument to get_tree_range.
	* vr-values.c (vr_values::range_of_expr): Same.
	* gimple-range-tests.cc: New file.
---
 gcc/function-tests.c      |  5 +++
 gcc/gimple-range-gori.cc  |  2 +-
 gcc/gimple-range-tests.cc | 72 +++++++++++++++++++++++++++++++++++++++
 gcc/gimple-range.cc       | 50 ++++++++++++++++++++++++---
 gcc/gimple-range.h        |  2 +-
 gcc/selftest.h            |  1 +
 gcc/value-query.cc        |  4 +--
 gcc/vr-values.c           |  2 +-
 8 files changed, 129 insertions(+), 9 deletions(-)
 create mode 100644 gcc/gimple-range-tests.cc

diff --git a/gcc/function-tests.c b/gcc/function-tests.c
index 1b8f665cde1..0ac1d37f8ff 100644
--- a/gcc/function-tests.c
+++ b/gcc/function-tests.c
@@ -581,6 +581,11 @@ test_ranges ()
   push_cfun (fun);
   range_tests ();
   range_op_tests ();
+
+  build_cfg (fndecl);
+  convert_to_ssa (fndecl);
+  gimple_range_tests ();
+
   pop_cfun ();
 }
 
diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc
index c51e6ce0697..12178e2ed90 100644
--- a/gcc/gimple-range-gori.cc
+++ b/gcc/gimple-range-gori.cc
@@ -589,7 +589,7 @@ gori_compute::expr_range_at_stmt (irange &r, tree expr, gimple *s)
   if (gimple_range_ssa_p (expr))
     ssa_range_in_bb (r, expr, gimple_bb (s));
   else
-    get_tree_range (r, expr);
+    get_global_range_query ()->range_of_expr (r, expr);
 }
 
 // Calculate the range for NAME if the lhs of statement S has the
diff --git a/gcc/gimple-range-tests.cc b/gcc/gimple-range-tests.cc
new file mode 100644
index 00000000000..9ee4c5aa6cd
--- /dev/null
+++ b/gcc/gimple-range-tests.cc
@@ -0,0 +1,72 @@
+/* Unit tests for GIMPLE range related routines.
+   Copyright (C) 2021 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#if CHECKING_P
+
+#include "selftest.h"
+
+namespace selftest {
+
+// Test ranges of tree expressions.
+class test_expr_eval : public gimple_ranger
+{
+public:
+  test_expr_eval ()
+  {
+    type = integer_type_node;
+    op0 = make_ssa_name (type);
+    op1 = make_ssa_name (type);
+
+    // [5,10] + [15,20] => [20, 30]
+    tree expr = fold_build2 (PLUS_EXPR, type, op0, op1);
+    int_range<2> expect (build_int_cst (type, 20), build_int_cst (type, 30));
+    int_range_max r;
+
+    ASSERT_TRUE (range_of_expr (r, expr));
+    ASSERT_TRUE (r == expect);
+  }
+
+  virtual bool range_of_expr (irange &r, tree expr, gimple * = NULL) OVERRIDE
+  {
+    if (expr == op0)
+      {
+	r.set (build_int_cst (type, 5), build_int_cst (type, 10));
+	return true;
+      }
+    if (expr == op1)
+      {
+	r.set (build_int_cst (type, 15), build_int_cst (type, 20));
+	return true;
+      }
+    return gimple_ranger::range_of_expr (r, expr);
+  }
+
+private:
+  tree op0, op1, type;
+};
+
+void
+gimple_range_tests ()
+{
+  test_expr_eval e;
+}
+
+} // namespace selftest
+
+#endif // CHECKING_P
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index b4dfaa92168..434b82b63b6 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -55,7 +55,7 @@ bool
 fur_source::get_operand (irange &r, tree expr)
 {
   if (!gimple_range_ssa_p (expr))
-    return get_tree_range (r, expr);
+    return get_tree_range (r, expr, /*stmt=*/NULL, m_query);
 
   // If no query engine is present, simply get the global value.
   if (!m_query)
@@ -168,11 +168,49 @@ gimple_range_adjustment (irange &res, const gimple *stmt)
     }
 }
 
+// Return a range for a binary or unary expression EXPR.  Return true if
+// a range is found.
+
+static bool
+get_arith_expr_range (irange &r, tree expr, gimple *stmt, range_query *query)
+{
+  tree type = TREE_TYPE (expr);
+
+  gcc_checking_assert (irange::supports_type_p (type));
+
+  if (BINARY_CLASS_P (expr))
+    {
+      int_range_max r0, r1;
+      range_operator *op = range_op_handler (TREE_CODE (expr), type);
+      if (!op)
+	return false;
+      query->range_of_expr (r0, TREE_OPERAND (expr, 0), stmt);
+      query->range_of_expr (r1, TREE_OPERAND (expr, 1), stmt);
+      op->fold_range (r, type, r0, r1);
+    }
+  else if (UNARY_CLASS_P (expr))
+    {
+      int_range_max r0;
+      range_operator *op = range_op_handler (TREE_CODE (expr), type);
+      if (!op)
+	return false;
+      query->range_of_expr (r0, TREE_OPERAND (expr, 0), stmt);
+      op->fold_range (r, type, r0, int_range<1> (type));
+    }
+  else
+    return false;
+
+  if (r.undefined_p ())
+    r.set_varying (type);
+
+  return true;
+}
+
 // Return a range in R for the tree EXPR.  Return true if a range is
 // representable, and UNDEFINED/false if not.
 
 bool
-get_tree_range (irange &r, tree expr)
+get_tree_range (irange &r, tree expr, gimple *stmt, range_query *query)
 {
   tree type;
   if (TYPE_P (expr))
@@ -212,7 +250,9 @@ get_tree_range (irange &r, tree expr)
 	}
 
       default:
-        break;
+	if (get_arith_expr_range (r, expr, stmt, query))
+	  return true;
+	break;
     }
   r.set_varying (type);
   return true;
@@ -961,7 +1001,7 @@ bool
 gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt)
 {
   if (!gimple_range_ssa_p (expr))
-    return get_tree_range (r, expr);
+    return get_tree_range (r, expr, stmt, this);
 
   // If there is no statement, just get the global value.
   if (!stmt)
@@ -1463,3 +1503,5 @@ disable_ranger (struct function *fun)
 
   fun->x_range_query = &global_ranges;
 }
+
+#include "gimple-range-tests.cc"
diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h
index ecd332a3c54..22445f8215d 100644
--- a/gcc/gimple-range.h
+++ b/gcc/gimple-range.h
@@ -173,7 +173,7 @@ fold_range (irange &r, gimple *s, edge on_edge, range_query *q = NULL)
 }
 
 // Calculate a basic range for a tree node expression.
-extern bool get_tree_range (irange &r, tree expr);
+extern bool get_tree_range (irange &r, tree expr, gimple *s, range_query *);
 
 // These routines provide a GIMPLE interface to the range-ops code.
 extern tree gimple_range_operand1 (const gimple *s);
diff --git a/gcc/selftest.h b/gcc/selftest.h
index e609117ec2b..80459d63a39 100644
--- a/gcc/selftest.h
+++ b/gcc/selftest.h
@@ -249,6 +249,7 @@ extern void predict_c_tests ();
 extern void pretty_print_c_tests ();
 extern void range_tests ();
 extern void range_op_tests ();
+extern void gimple_range_tests ();
 extern void read_rtl_function_c_tests ();
 extern void rtl_tests_c_tests ();
 extern void sbitmap_c_tests ();
diff --git a/gcc/value-query.cc b/gcc/value-query.cc
index f8b457d362c..58938b1ce14 100644
--- a/gcc/value-query.cc
+++ b/gcc/value-query.cc
@@ -316,12 +316,12 @@ get_global_range_query ()
 }
 
 bool
-global_range_query::range_of_expr (irange &r, tree expr, gimple *)
+global_range_query::range_of_expr (irange &r, tree expr, gimple *stmt)
 {
   tree type = TREE_TYPE (expr);
 
   if (!irange::supports_type_p (type) || !gimple_range_ssa_p (expr))
-    return get_tree_range (r, expr);
+    return get_tree_range (r, expr, stmt, this);
 
   get_range_global (r, expr);
 
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index 3d0be8edb3b..5e7e51e00c3 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -180,7 +180,7 @@ bool
 vr_values::range_of_expr (irange &r, tree expr, gimple *stmt)
 {
   if (!gimple_range_ssa_p (expr))
-    return get_tree_range (r, expr);
+    return get_tree_range (r, expr, stmt, this);
 
   if (const value_range *vr = get_value_range (expr, stmt))
     {
-- 
2.31.1

[PATCH 2/2] Replace uses of determine_value_range with range_of_expr.

[Aldy Hernandez]

The expression evaluator changes to the range_query API provide
everything determine_value_range does.  This patch replaces all uses
with calls into the range_query API.

Tested on x86-64 Linux.

OK?

gcc/ChangeLog:

	* calls.c (get_size_range): Use range_of_expr instead of
	determine_value_range.
	* tree-affine.c (expr_to_aff_combination): Same.
	* tree-data-ref.c (split_constant_offset): Same.
	* tree-vrp.c (determine_value_range_1): Remove.
	(determine_value_range): Remove.
	* tree-vrp.h (determine_value_range): Remove.
---
 gcc/calls.c         | 21 +++++++++--------
 gcc/tree-affine.c   |  7 +++++-
 gcc/tree-data-ref.c | 12 +++++-----
 gcc/tree-vrp.c      | 56 ---------------------------------------------
 gcc/tree-vrp.h      |  1 -
 5 files changed, 23 insertions(+), 74 deletions(-)

diff --git a/gcc/calls.c b/gcc/calls.c
index dd8ff2aa7cb..a7c78ed9c16 100644
--- a/gcc/calls.c
+++ b/gcc/calls.c
@@ -1276,19 +1276,20 @@ get_size_range (range_query *query, tree exp, gimple *stmt, tree range[2],
   wide_int min, max;
   enum value_range_kind range_type;
 
+  if (!query)
+    query = get_global_range_query ();
+
   if (integral)
     {
       value_range vr;
-      if (query && query->range_of_expr (vr, exp, stmt))
-	{
-	  if (vr.undefined_p ())
-	    vr.set_varying (TREE_TYPE (exp));
-	  range_type = vr.kind ();
-	  min = wi::to_wide (vr.min ());
-	  max = wi::to_wide (vr.max ());
-	}
-      else
-	range_type = determine_value_range (exp, &min, &max);
+
+      query->range_of_expr (vr, exp, stmt);
+
+      if (vr.undefined_p ())
+	vr.set_varying (TREE_TYPE (exp));
+      range_type = vr.kind ();
+      min = wi::to_wide (vr.min ());
+      max = wi::to_wide (vr.max ());
     }
   else
     range_type = VR_VARYING;
diff --git a/gcc/tree-affine.c b/gcc/tree-affine.c
index b273adb173d..a65719def23 100644
--- a/gcc/tree-affine.c
+++ b/gcc/tree-affine.c
@@ -31,6 +31,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimplify.h"
 #include "dumpfile.h"
 #include "cfgexpand.h"
+#include "value-query.h"
 
 /* Extends CST as appropriate for the affine combinations COMB.  */
 
@@ -345,11 +346,15 @@ expr_to_aff_combination (aff_tree *comb, tree_code code, tree type,
 	       for below case:
 		 (T1)(X *+- CST) -> (T1)X *+- (T1)CST
 	       if X *+- CST doesn't overflow by range information.  */
+	    value_range vr;
 	    if (TYPE_UNSIGNED (itype)
 		&& TYPE_OVERFLOW_WRAPS (itype)
 		&& TREE_CODE (op1) == INTEGER_CST
-		&& determine_value_range (op0, &minv, &maxv) == VR_RANGE)
+		&& get_range_query (cfun)->range_of_expr (vr, op0)
+		&& vr.kind () == VR_RANGE)
 	      {
+		wide_int minv = vr.lower_bound ();
+		wide_int maxv = vr.upper_bound ();
 		wi::overflow_type overflow = wi::OVF_NONE;
 		signop sign = UNSIGNED;
 		if (icode == PLUS_EXPR)
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index 09d46671565..b1f64684840 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -1069,12 +1069,12 @@ split_constant_offset (tree exp, tree *var, tree *off, value_range *exp_range,
   if (INTEGRAL_TYPE_P (type))
     *var = fold_convert (sizetype, *var);
   *off = ssize_int (0);
-  if (exp_range && code != SSA_NAME)
-    {
-      wide_int var_min, var_max;
-      if (determine_value_range (exp, &var_min, &var_max) == VR_RANGE)
-	*exp_range = value_range (type, var_min, var_max);
-    }
+
+  value_range r;
+  if (exp_range && code != SSA_NAME
+      && get_range_query (cfun)->range_of_expr (r, exp)
+      && !r.undefined_p ())
+    *exp_range = r;
 }
 
 /* Expresses EXP as VAR + OFF, where OFF is a constant.  VAR has the same
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 450926d5f9b..b9c0e65bd98 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -4606,59 +4606,3 @@ make_pass_vrp (gcc::context *ctxt)
 {
   return new pass_vrp (ctxt);
 }
-
-
-/* Worker for determine_value_range.  */
-
-static void
-determine_value_range_1 (value_range *vr, tree expr)
-{
-  if (BINARY_CLASS_P (expr))
-    {
-      value_range vr0, vr1;
-      determine_value_range_1 (&vr0, TREE_OPERAND (expr, 0));
-      determine_value_range_1 (&vr1, TREE_OPERAND (expr, 1));
-      range_fold_binary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr),
-			      &vr0, &vr1);
-    }
-  else if (UNARY_CLASS_P (expr))
-    {
-      value_range vr0;
-      determine_value_range_1 (&vr0, TREE_OPERAND (expr, 0));
-      range_fold_unary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr),
-			     &vr0, TREE_TYPE (TREE_OPERAND (expr, 0)));
-    }
-  else if (TREE_CODE (expr) == INTEGER_CST)
-    vr->set (expr);
-  else
-    {
-      value_range r;
-      /* For SSA names try to extract range info computed by VRP.  Otherwise
-	 fall back to varying.  */
-      if (TREE_CODE (expr) == SSA_NAME
-	  && INTEGRAL_TYPE_P (TREE_TYPE (expr))
-	  && get_range_query (cfun)->range_of_expr (r, expr)
-	  && !r.undefined_p ())
-	*vr = r;
-      else
-	vr->set_varying (TREE_TYPE (expr));
-    }
-}
-
-/* Compute a value-range for EXPR and set it in *MIN and *MAX.  Return
-   the determined range type.  */
-
-value_range_kind
-determine_value_range (tree expr, wide_int *min, wide_int *max)
-{
-  value_range vr;
-  determine_value_range_1 (&vr, expr);
-  if (!vr.varying_p () && vr.constant_p ())
-    {
-      *min = wi::to_wide (vr.min ());
-      *max = wi::to_wide (vr.max ());
-      return vr.kind ();
-    }
-
-  return VR_VARYING;
-}
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
index 989d8430c98..3392ecc7b23 100644
--- a/gcc/tree-vrp.h
+++ b/gcc/tree-vrp.h
@@ -62,7 +62,6 @@ extern bool find_case_label_index (gswitch *, size_t, tree, size_t *);
 extern bool overflow_comparison_p (tree_code, tree, tree, bool, tree *);
 extern tree get_single_symbol (tree, bool *, tree *);
 extern void maybe_set_nonzero_bits (edge, tree);
-extern value_range_kind determine_value_range (tree, wide_int *, wide_int *);
 extern wide_int masked_increment (const wide_int &val_in, const wide_int &mask,
 				  const wide_int &sgnbit, unsigned int prec);
 
-- 
2.31.1

Re: [PATCH 1/2] Implement generic expression evaluator for range_query.

[Jeff Law]

On 5/27/2021 2:55 AM, Aldy Hernandez via Gcc-patches wrote:
> Right now, range_of_expr only works with constants, SSA names, and
> pointers.  Anything else gets returned as VARYING.  This patch adds the
> capability to deal with arbitrary expressions, inasmuch as these
> tree codes are implemented in range-ops.cc.
>
> This will give us the ability to ask for the range of any tree expression,
> not just constants and SSA names, with range_of_expr().
>
> This is a more generic implementation of determine_value_range in VRP.
> A follow-up patch will remove all uses of it in favor of the
> range_query API.
>
> Tested on x86-64 Linux.
>
> OK?
>
> gcc/ChangeLog:
>
> 	* function-tests.c (test_ranges): Call gimple_range_tests.
> 	* gimple-range-gori.cc (gori_compute::expr_range_at_stmt): Use
> 	get_global_range_query instead of get_tree_range.
> 	* gimple-range.cc (fur_source::get_operand): Add argument to
> 	get_tree_range.
> 	(get_arith_expr_range): New.
> 	(get_tree_range): Add gimple and range_query arguments.
> 	Call get_arith_expr_range.
> 	(gimple_ranger::range_of_expr): Add argument to get_tree_range.
> 	Include gimple-range-tests.cc.
> 	* gimple-range.h (get_tree_range): Add argument.
> 	* selftest.h (gimple_range_tests): New.
> 	* value-query.cc (global_range_query::range_of_expr): Add
> 	argument to get_tree_range.
> 	* vr-values.c (vr_values::range_of_expr): Same.
> 	* gimple-range-tests.cc: New file.
Both patches in this series are fine.

Thanks,
Jeff

Re: [PATCH 1/2] Implement generic expression evaluator for range_query.

[Aldy Hernandez]

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

Andrew had some minor suggestions and cleanups after I posted this.

Andrew, is this what you had in mind?

Aldy

On Sat, May 29, 2021 at 6:06 AM Jeff Law <jeffreyalaw@gmail.com> wrote:
>
>
>
> On 5/27/2021 2:55 AM, Aldy Hernandez via Gcc-patches wrote:
> > Right now, range_of_expr only works with constants, SSA names, and
> > pointers.  Anything else gets returned as VARYING.  This patch adds the
> > capability to deal with arbitrary expressions, inasmuch as these
> > tree codes are implemented in range-ops.cc.
> >
> > This will give us the ability to ask for the range of any tree expression,
> > not just constants and SSA names, with range_of_expr().
> >
> > This is a more generic implementation of determine_value_range in VRP.
> > A follow-up patch will remove all uses of it in favor of the
> > range_query API.
> >
> > Tested on x86-64 Linux.
> >
> > OK?
> >
> > gcc/ChangeLog:
> >
> >       * function-tests.c (test_ranges): Call gimple_range_tests.
> >       * gimple-range-gori.cc (gori_compute::expr_range_at_stmt): Use
> >       get_global_range_query instead of get_tree_range.
> >       * gimple-range.cc (fur_source::get_operand): Add argument to
> >       get_tree_range.
> >       (get_arith_expr_range): New.
> >       (get_tree_range): Add gimple and range_query arguments.
> >       Call get_arith_expr_range.
> >       (gimple_ranger::range_of_expr): Add argument to get_tree_range.
> >       Include gimple-range-tests.cc.
> >       * gimple-range.h (get_tree_range): Add argument.
> >       * selftest.h (gimple_range_tests): New.
> >       * value-query.cc (global_range_query::range_of_expr): Add
> >       argument to get_tree_range.
> >       * vr-values.c (vr_values::range_of_expr): Same.
> >       * gimple-range-tests.cc: New file.
> Both patches in this series are fine.
>
> Thanks,
> Jeff
>

[-- Attachment #2: 0001-Implement-generic-expression-evaluator-for-range_que.patch --]
[-- Type: text/x-patch, Size: 12077 bytes --]

From fe8f95d2baf92fc5fa967c5d183c5480f003e15d Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <aldyh@redhat.com>
Date: Wed, 26 May 2021 08:40:17 +0200
Subject: [PATCH 1/2] Implement generic expression evaluator for range_query.

Right now, range_of_expr only works with constants, SSA names, and
pointers.  Anything else gets returned as VARYING.  This patch adds the
capability to deal with arbitrary expressions, inasmuch as these
tree codes are implemented in range-ops.cc.

This will give us the ability to ask for the range of any tree expression,
not just constants and SSA names, with range_of_expr().

This is a more generic implementation of determine_value_range in VRP.
A follow-up patch will remove all uses of it in favor of the
range_query API.

gcc/ChangeLog:

	* function-tests.c (test_ranges): Call gimple_range_tests.
	* gimple-range-cache.cc (ranger_cache::range_of_expr): Pass stmt
	to get_tree_range.
	* gimple-range-gori.cc (gori_compute::expr_range_at_stmt): Use
	get_global_range_query instead of get_tree_range.
	* gimple-range.cc (fur_source::get_operand): Add argument to
	get_tree_range.
	(get_tree_range): Move to value-query.cc.
	Call get_arith_expr_range.
	(gimple_ranger::range_of_expr): Add argument to get_tree_range.
	Include gimple-range-tests.cc.
	* gimple-range.h (fold_range): Add argument.
	(get_tree_range): Remove.
	* selftest.h (gimple_range_tests): New.
	* value-query.cc (global_range_query::range_of_expr): Add
	stmt argument.
	(range_query::get_tree_range): Move from gimple-range.cc.
	* value-query.h (class range_query): Add get_tree_range and
	get_arith_expr_range.  Make fur_source a friend.
	* vr-values.c (vr_values::range_of_expr): Pass stmt to
	get_tree_range.
	* gimple-range-tests.cc: New file.
---
 gcc/function-tests.c      |  5 +++
 gcc/gimple-range-cache.cc |  4 +-
 gcc/gimple-range-tests.cc | 72 +++++++++++++++++++++++++++++++++
 gcc/gimple-range.cc       | 64 ++---------------------------
 gcc/gimple-range.h        |  7 ++--
 gcc/selftest.h            |  1 +
 gcc/value-query.cc        | 84 ++++++++++++++++++++++++++++++++++++++-
 gcc/value-query.h         |  2 +
 gcc/vr-values.c           |  2 +-
 9 files changed, 172 insertions(+), 69 deletions(-)
 create mode 100644 gcc/gimple-range-tests.cc

diff --git a/gcc/function-tests.c b/gcc/function-tests.c
index 1b8f665cde1..0ac1d37f8ff 100644
--- a/gcc/function-tests.c
+++ b/gcc/function-tests.c
@@ -581,6 +581,11 @@ test_ranges ()
   push_cfun (fun);
   range_tests ();
   range_op_tests ();
+
+  build_cfg (fndecl);
+  convert_to_ssa (fndecl);
+  gimple_range_tests ();
+
   pop_cfun ();
 }
 
diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index cc27574b7b4..c58acf48dfb 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -827,7 +827,7 @@ ranger_cache::range_of_expr (irange &r, tree name, gimple *stmt)
 {
   if (!gimple_range_ssa_p (name))
     {
-      get_tree_range (r, name);
+      get_tree_range (r, name, stmt);
       return true;
     }
 
@@ -860,7 +860,7 @@ ranger_cache::range_of_expr (irange &r, tree name, gimple *stmt)
 	}
     }
   else
-    get_tree_range (r, expr);
+    get_tree_range (r, expr, NULL);
   return false;
 }
 
diff --git a/gcc/gimple-range-tests.cc b/gcc/gimple-range-tests.cc
new file mode 100644
index 00000000000..9ee4c5aa6cd
--- /dev/null
+++ b/gcc/gimple-range-tests.cc
@@ -0,0 +1,72 @@
+/* Unit tests for GIMPLE range related routines.
+   Copyright (C) 2021 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#if CHECKING_P
+
+#include "selftest.h"
+
+namespace selftest {
+
+// Test ranges of tree expressions.
+class test_expr_eval : public gimple_ranger
+{
+public:
+  test_expr_eval ()
+  {
+    type = integer_type_node;
+    op0 = make_ssa_name (type);
+    op1 = make_ssa_name (type);
+
+    // [5,10] + [15,20] => [20, 30]
+    tree expr = fold_build2 (PLUS_EXPR, type, op0, op1);
+    int_range<2> expect (build_int_cst (type, 20), build_int_cst (type, 30));
+    int_range_max r;
+
+    ASSERT_TRUE (range_of_expr (r, expr));
+    ASSERT_TRUE (r == expect);
+  }
+
+  virtual bool range_of_expr (irange &r, tree expr, gimple * = NULL) OVERRIDE
+  {
+    if (expr == op0)
+      {
+	r.set (build_int_cst (type, 5), build_int_cst (type, 10));
+	return true;
+      }
+    if (expr == op1)
+      {
+	r.set (build_int_cst (type, 15), build_int_cst (type, 20));
+	return true;
+      }
+    return gimple_ranger::range_of_expr (r, expr);
+  }
+
+private:
+  tree op0, op1, type;
+};
+
+void
+gimple_range_tests ()
+{
+  test_expr_eval e;
+}
+
+} // namespace selftest
+
+#endif // CHECKING_P
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index af426207092..db8419bc4c6 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -54,16 +54,6 @@ along with GCC; see the file COPYING3.  If not see
 bool
 fur_source::get_operand (irange &r, tree expr)
 {
-  if (!gimple_range_ssa_p (expr))
-    return get_tree_range (r, expr);
-
-  // If no query engine is present, simply get the global value.
-  if (!m_query)
-    {
-       r = gimple_range_global (expr);
-       return true;
-    }
-
   // First look for a stmt.
   if (m_stmt)
     return m_query->range_of_expr (r, expr, m_stmt);
@@ -168,56 +158,6 @@ gimple_range_adjustment (irange &res, const gimple *stmt)
     }
 }
 
-// Return a range in R for the tree EXPR.  Return true if a range is
-// representable, and UNDEFINED/false if not.
-
-bool
-get_tree_range (irange &r, tree expr)
-{
-  tree type;
-  if (TYPE_P (expr))
-    type = expr;
-  else
-    type = TREE_TYPE (expr);
-
-  // Return false if the type isn't suported.
-  if (!irange::supports_type_p (type))
-    {
-      r.set_undefined ();
-      return false;
-    }
-
-  switch (TREE_CODE (expr))
-    {
-      case INTEGER_CST:
-	if (TREE_OVERFLOW_P (expr))
-	  expr = drop_tree_overflow (expr);
-	r.set (expr, expr);
-	return true;
-
-      case SSA_NAME:
-	r = gimple_range_global (expr);
-	return true;
-
-      case ADDR_EXPR:
-        {
-	  // Handle &var which can show up in phi arguments.
-	  bool ov;
-	  if (tree_single_nonzero_warnv_p (expr, &ov))
-	    {
-	      r = range_nonzero (type);
-	      return true;
-	    }
-	  break;
-	}
-
-      default:
-        break;
-    }
-  r.set_varying (type);
-  return true;
-}
-
 // Return the base of the RHS of an assignment.
 
 static tree
@@ -961,7 +901,7 @@ bool
 gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt)
 {
   if (!gimple_range_ssa_p (expr))
-    return get_tree_range (r, expr);
+    return get_tree_range (r, expr, stmt);
 
   // If there is no statement, just get the global value.
   if (!stmt)
@@ -1466,3 +1406,5 @@ disable_ranger (struct function *fun)
 
   fun->x_range_query = &global_ranges;
 }
+
+#include "gimple-range-tests.cc"
diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h
index 65f62e4ba9b..02b891fad69 100644
--- a/gcc/gimple-range.h
+++ b/gcc/gimple-range.h
@@ -159,6 +159,8 @@ inline bool
 fold_range (irange &r, gimple *s, range_query *q = NULL)
 {
   fold_using_range f;
+  if (q == NULL)
+    q = get_global_range_query ();
   fur_source src (q, s);
   return f.fold_stmt (r, s, src);
 }
@@ -169,13 +171,12 @@ inline bool
 fold_range (irange &r, gimple *s, edge on_edge, range_query *q = NULL)
 {
   fold_using_range f;
+  if (q == NULL)
+    q = get_global_range_query ();
   fur_source src (q, on_edge);
   return f.fold_stmt (r, s, src);
 }
 
-// Calculate a basic range for a tree node expression.
-extern bool get_tree_range (irange &r, tree expr);
-
 // These routines provide a GIMPLE interface to the range-ops code.
 extern tree gimple_range_operand1 (const gimple *s);
 extern tree gimple_range_operand2 (const gimple *s);
diff --git a/gcc/selftest.h b/gcc/selftest.h
index e609117ec2b..80459d63a39 100644
--- a/gcc/selftest.h
+++ b/gcc/selftest.h
@@ -249,6 +249,7 @@ extern void predict_c_tests ();
 extern void pretty_print_c_tests ();
 extern void range_tests ();
 extern void range_op_tests ();
+extern void gimple_range_tests ();
 extern void read_rtl_function_c_tests ();
 extern void rtl_tests_c_tests ();
 extern void sbitmap_c_tests ();
diff --git a/gcc/value-query.cc b/gcc/value-query.cc
index 070d706166e..821f224d4ab 100644
--- a/gcc/value-query.cc
+++ b/gcc/value-query.cc
@@ -182,6 +182,86 @@ range_query::~range_query ()
   delete equiv_alloc;
 }
 
+// Return a range in R for the tree EXPR.  Return true if a range is
+// representable, and UNDEFINED/false if not.
+
+bool
+range_query::get_tree_range (irange &r, tree expr, gimple *stmt)
+{
+  tree type;
+  if (TYPE_P (expr))
+    type = expr;
+  else
+    type = TREE_TYPE (expr);
+
+  if (!irange::supports_type_p (type))
+    {
+      r.set_undefined ();
+      return false;
+    }
+  if (expr == type)
+    {
+      r.set_varying (type);
+      return true;
+    }
+  switch (TREE_CODE (expr))
+    {
+    case INTEGER_CST:
+      if (TREE_OVERFLOW_P (expr))
+	expr = drop_tree_overflow (expr);
+      r.set (expr, expr);
+      return true;
+
+    case SSA_NAME:
+      r = gimple_range_global (expr);
+      return true;
+
+    case ADDR_EXPR:
+      {
+	// Handle &var which can show up in phi arguments.
+	bool ov;
+	if (tree_single_nonzero_warnv_p (expr, &ov))
+	  {
+	    r = range_nonzero (type);
+	    return true;
+	  }
+	break;
+      }
+
+    default:
+      break;
+    }
+  if (BINARY_CLASS_P (expr))
+    {
+      range_operator *op = range_op_handler (TREE_CODE (expr), type);
+      if (op)
+	{
+	  int_range_max r0, r1;
+	  range_of_expr (r0, TREE_OPERAND (expr, 0), stmt);
+	  range_of_expr (r1, TREE_OPERAND (expr, 1), stmt);
+	  op->fold_range (r, type, r0, r1);
+	}
+      else
+	r.set_varying (type);
+      return true;
+    }
+  if (UNARY_CLASS_P (expr))
+    {
+      range_operator *op = range_op_handler (TREE_CODE (expr), type);
+      if (op)
+	{
+	  int_range_max r0;
+	  range_of_expr (r0, TREE_OPERAND (expr, 0), stmt);
+	  op->fold_range (r, type, r0, int_range<1> (type));
+	}
+      else
+	r.set_varying (type);
+      return true;
+    }
+  r.set_varying (type);
+  return true;
+}
+
 // Return the range for NAME from SSA_NAME_RANGE_INFO.
 
 static inline void
@@ -355,12 +435,12 @@ get_global_range_query ()
 }
 
 bool
-global_range_query::range_of_expr (irange &r, tree expr, gimple *)
+global_range_query::range_of_expr (irange &r, tree expr, gimple *stmt)
 {
   tree type = TREE_TYPE (expr);
 
   if (!irange::supports_type_p (type) || !gimple_range_ssa_p (expr))
-    return get_tree_range (r, expr);
+    return get_tree_range (r, expr, stmt);
 
   get_range_global (r, expr);
 
diff --git a/gcc/value-query.h b/gcc/value-query.h
index d0512e40c5a..77e49e9a906 100644
--- a/gcc/value-query.h
+++ b/gcc/value-query.h
@@ -100,6 +100,8 @@ public:
 protected:
   class value_range_equiv *allocate_value_range_equiv ();
   void free_value_range_equiv (class value_range_equiv *);
+  bool get_tree_range (irange &r, tree expr, gimple *stmt);
+  bool get_arith_expr_range (irange &r, tree expr, gimple *stmt);
 
 private:
   class equiv_allocator *equiv_alloc;
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index 3d0be8edb3b..509c8b093c5 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -180,7 +180,7 @@ bool
 vr_values::range_of_expr (irange &r, tree expr, gimple *stmt)
 {
   if (!gimple_range_ssa_p (expr))
-    return get_tree_range (r, expr);
+    return get_tree_range (r, expr, stmt);
 
   if (const value_range *vr = get_value_range (expr, stmt))
     {
-- 
2.31.1

Re: [PATCH 1/2] Implement generic expression evaluator for range_query.

[Andrew MacLeod]

On 6/3/21 11:39 AM, Aldy Hernandez via Gcc-patches wrote:
> Andrew had some minor suggestions and cleanups after I posted this.
>
> Andrew, is this what you had in mind?
>
> Aldy
>
> On Sat, May 29, 2021 at 6:06 AM Jeff Law <jeffreyalaw@gmail.com> wrote:
>>
>>
>> On 5/27/2021 2:55 AM, Aldy Hernandez via Gcc-patches wrote:
>>> Right now, range_of_expr only works with constants, SSA names, and
>>> pointers.  Anything else gets returned as VARYING.  This patch adds the
>>> capability to deal with arbitrary expressions, inasmuch as these
>>> tree codes are implemented in range-ops.cc.
>>>
>>> This will give us the ability to ask for the range of any tree expression,
>>> not just constants and SSA names, with range_of_expr().
>>>
>>> This is a more generic implementation of determine_value_range in VRP.
>>> A follow-up patch will remove all uses of it in favor of the
>>> range_query API.
>>>
>>> Tested on x86-64 Linux.
>>>
>>> OK?
>>>
>>> gcc/ChangeLog:
>>>
>>>        * function-tests.c (test_ranges): Call gimple_range_tests.
>>>        * gimple-range-gori.cc (gori_compute::expr_range_at_stmt): Use
>>>        get_global_range_query instead of get_tree_range.
>>>        * gimple-range.cc (fur_source::get_operand): Add argument to
>>>        get_tree_range.
>>>        (get_arith_expr_range): New.
>>>        (get_tree_range): Add gimple and range_query arguments.
>>>        Call get_arith_expr_range.
>>>        (gimple_ranger::range_of_expr): Add argument to get_tree_range.
>>>        Include gimple-range-tests.cc.
>>>        * gimple-range.h (get_tree_range): Add argument.
>>>        * selftest.h (gimple_range_tests): New.
>>>        * value-query.cc (global_range_query::range_of_expr): Add
>>>        argument to get_tree_range.
>>>        * vr-values.c (vr_values::range_of_expr): Same.
>>>        * gimple-range-tests.cc: New file.
>> Both patches in this series are fine.
>>
>> Thanks,
>> Jeff
>>
yeah, OK.

Andrew