[RFC] Optimize in VRP loads from constant arrays

Hi!

This patch attempts to implement the optimization mentioned in
http://gcc.gnu.org/ml/gcc-patches/2017-02/msg00945.html
If we know a (relatively small) value range for ARRAY_REF index
in constant array load and the values in the array for all the indexes
in the array are the same (and constant), we can just replace the load
with the constant.

Shall I introduce a param for the size of the range to consider?

2017-04-21  Jakub Jelinek  <jakub@redhat.com>

	* tree-vrp.c: Include gimplify.h.
	(load_index): New variable.
	(simplify_load_valueize, simplify_load_using_ranges): New functions.
	(simplify_stmt_using_ranges): Use simplify_load_using_ranges.

	* gcc.dg/tree-ssa/vrp113.c: New test.


	Jakub

On April 21, 2017 4:06:59 PM GMT+02:00, Jakub Jelinek <jakub@redhat.com> wrote:
>Hi!
>
>This patch attempts to implement the optimization mentioned in
>http://gcc.gnu.org/ml/gcc-patches/2017-02/msg00945.html
>If we know a (relatively small) value range for ARRAY_REF index
>in constant array load and the values in the array for all the indexes
>in the array are the same (and constant), we can just replace the load
>with the constant.

But this should be done during propagation (and thus can even produce a range rather than just a constant).

Also much of the fold_const_aggregate_ref work can be shared for all indices.

>Shall I introduce a param for the size of the range to consider?

I think so.  Eventually we can pre-compute/cache a "range tree" for a
Constant initializer?

That said I'm happy with moving it to propagation time and considering ranges
And leave compile-time optimization for future work (with possibly increasing the number of elements to consider)

Richard.

>2017-04-21  Jakub Jelinek  <jakub@redhat.com>
>
>	* tree-vrp.c: Include gimplify.h.
>	(load_index): New variable.
>	(simplify_load_valueize, simplify_load_using_ranges): New functions.
>	(simplify_stmt_using_ranges): Use simplify_load_using_ranges.
>
>	* gcc.dg/tree-ssa/vrp113.c: New test.
>
>--- gcc/tree-vrp.c.jj	2017-04-20 08:19:27.000000000 +0200
>+++ gcc/tree-vrp.c	2017-04-21 15:35:25.869856659 +0200
>@@ -62,6 +62,7 @@ along with GCC; see the file COPYING3.
> #include "alloc-pool.h"
> #include "domwalk.h"
> #include "tree-cfgcleanup.h"
>+#include "gimplify.h"
> 
> #define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }
> 
>@@ -10442,6 +10443,96 @@ simplify_float_conversion_using_ranges (
>   return true;
> }
> 
>+/* Variables used to communicate index and its current value
>+   between simplify_load_using_ranges and its valueize function.  */
>+static tree load_index[2];
>+
>+/* Valueize callback for simplify_load_using_ranges.  */
>+
>+static tree
>+simplify_load_valueize (tree name)
>+{
>+  if (name == load_index[0])
>+    return load_index[1];
>+  return name;
>+}
>+
>+/* Simplify a constant load if there is a single ARRAY_REF among
>+   handled components, we have a narrow range for the index and
>+   constant loads with all the indexes in the range yield the same
>+   constant.  */
>+
>+static bool
>+simplify_load_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt)
>+{
>+  tree rhs = gimple_assign_rhs1 (stmt);
>+  tree t, *p = NULL;
>+  tree index = NULL_TREE;
>+  value_range *vr = NULL;
>+  for (t = rhs; handled_component_p (t); t = TREE_OPERAND (t, 0))
>+    switch (TREE_CODE (t))
>+      {
>+      case ARRAY_REF:
>+	if (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST)
>+	  break;
>+	if (TREE_CODE (TREE_OPERAND (t, 1)) == SSA_NAME)
>+	  {
>+	    if (index)
>+	      return false;
>+	    index = TREE_OPERAND (t, 1);
>+	    vr = get_value_range (index);
>+	    if (!range_int_cst_p (vr)
>+		|| is_overflow_infinity (vr->min)
>+		|| is_overflow_infinity (vr->max)
>+		|| tree_int_cst_sgn (vr->min) < 0)
>+	      return false;
>+	    wide_int diff = vr->max;
>+	    diff -= vr->min;
>+	    /* As we have to check every index in the range, avoid
>+	       doing it too many times.  */
>+	    if (!wi::ltu_p (diff, 256))
>+	      return false;
>+	  }
>+	break;
>+      case ARRAY_RANGE_REF:
>+	return false;
>+      default:
>+	break;
>+      }
>+  if (index == NULL_TREE)
>+    return false;
>+  load_index[0] = index;
>+  load_index[1] = vr->min;
>+  tree c = fold_const_aggregate_ref_1 (rhs, simplify_load_valueize);
>+  /* fold_const_aggregate_ref_1 can unfortunately only valueize a very
>+     small subset of expressions so far.  */
>+  if (c == NULL_TREE)
>+    {
>+      rhs = unshare_expr (rhs);
>+      for (t = rhs;
>+	   TREE_CODE (t) != ARRAY_REF || TREE_OPERAND (t, 1) != index;
>+	   t = TREE_OPERAND (t, 0))
>+	;
>+      p = &TREE_OPERAND (t, 1);
>+      *p = load_index[1];
>+      c = fold_const_aggregate_ref_1 (rhs, simplify_load_valueize);
>+    }
>+  if (c == NULL_TREE || !is_gimple_min_invariant (c))
>+    return false;
>+  wide_int w = vr->min;
>+  while (wi::ne_p (w, vr->max))
>+    {
>+      load_index[1] = wide_int_to_tree (TREE_TYPE (vr->min), ++w);
>+      if (p)
>+	*p = load_index[1];
>+      tree c2 = fold_const_aggregate_ref_1 (rhs,
>simplify_load_valueize);
>+      if (c2 == NULL_TREE || !operand_equal_p (c, c2, 0))
>+	return false;
>+    }
>+  gimple_assign_set_rhs_from_tree (gsi, c);
>+  return true;
>+}
>+
> /* Simplify an internal fn call using ranges if possible.  */
> 
> static bool
>@@ -10709,6 +10800,8 @@ simplify_stmt_using_ranges (gimple_stmt_
> 	  return simplify_min_or_max_using_ranges (gsi, stmt);
> 
> 	default:
>+	  if (gimple_assign_single_p (stmt) && handled_component_p (rhs1))
>+	    return simplify_load_using_ranges (gsi, stmt);
> 	  break;
> 	}
>     }
>--- gcc/testsuite/gcc.dg/tree-ssa/vrp113.c.jj	2017-04-21
>15:43:36.291436020 +0200
>+++ gcc/testsuite/gcc.dg/tree-ssa/vrp113.c	2017-04-21
>15:50:16.751173243 +0200
>@@ -0,0 +1,15 @@
>+/* { dg-do compile } */
>+/* { dg-options "-O2 -fdump-tree-vrp1-details" } */
>+
>+struct S { int a, b; };
>+const struct S v[16] = { { 1, 2 }, { 1, 2 }, { 1, 2 }, { 1, 2 }, { 2,
>3 }, { 4, 5 } };
>+
>+int
>+foo (int x)
>+{
>+  return v[x & 3].a + v[(x & 1) + 2].b + "abcd\4\4\4\4\4\4\4\4efgh"[(x
>& 7) + 4];
>+}
>+
>+/* { dg-final { scan-tree-dump "Folding statement: \[_a-z0-9\]+ =
>v\\\[\[_a-z0-9\]+\\\]\.a;\[\n\r]Folded into: \[_a-z0-9]+ = 1;" "vrp1" }
>} */
>+/* { dg-final { scan-tree-dump "Folding statement: \[_a-z0-9\]+ =
>v\\\[\[_a-z0-9\]+\\\]\.b;\[\n\r]Folded into: \[_a-z0-9]+ = 2;" "vrp1" }
>} */
>+/* { dg-final { scan-tree-dump "Folding statement: \[_a-z0-9\]+ =
>\"\[^\n\r]*\"\\\[\[_a-z0-9\]+\\\];\[\n\r]Folded into: \[_a-z0-9]+ = 4;"
>"vrp1" } } */
>
>	Jakub