On April 21, 2017 4:06:59 PM GMT+02:00, Jakub Jelinek <ja...@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 <ja...@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
