[RFC PATCH] Optimize in VRP loads from constant arrays

[Jakub Jelinek <jakub at redhat dot com>]

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.

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