Hi,
The gimple-ssa-strength-reduction pass handles CAND_REFs in order to find
different MEM_REFs sharing common part in addressing expression. If such
MEM_REFs are found, the pass rewrites MEM_REFs, and produces more efficient
addressing expression during the RTL passes.
The pass analyzes addressing expression in each MEM_REF to see if it can be
formalized as follows:
base: MEM_REF (T1, C1)
offset: MULT_EXPR (PLUS_EXPR (T2, C2), C3)
bitpos: C4 * BITS_PER_UNIT
Then restructures it into below form:
MEM_REF (POINTER_PLUS_EXPR (T1, MULT_EXPR (T2, C3)),
C1 + (C2 * C3) + C4)
At last, rewrite the MEM_REFs if there are two or more sharing common
(non-constant) part.
The problem is it doesn't back trace T2. If T2 is recorded as a CAND_ADD in
form of "T2' + C5", the MEM_REF should be restructure into:
MEM_REF (POINTER_PLUS_EXPR (T1, MULT_EXPR (T2', C3)),
C1 + (C2 * C3) + C4 + (C5 * C3))
The patch also includes a test case to illustrate the problem.
Bootstrapped and tested on x86/x86_64/arm-a15, is it ok?
Thanks.
bin
2013-09-02 Bin Cheng <bin.ch...@arm.com>
* gimple-ssa-strength-reduction.c (backtrace_base_for_ref): New.
(restructure_reference): Call backtrace_base_for_ref.
gcc/testsuite/ChangeLog
2013-09-02 Bin Cheng <bin.ch...@arm.com>
* gcc.dg/tree-ssa/slsr-39.c: New test.Index: gcc/testsuite/gcc.dg/tree-ssa/slsr-39.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/slsr-39.c (revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/slsr-39.c (revision 0)
@@ -0,0 +1,26 @@
+/* Verify straight-line strength reduction for back-tracing
+ CADN_ADD for T2 in:
+
+ *PBASE: T1
+ *POFFSET: MULT_EXPR (T2, C3)
+ *PINDEX: C1 + (C2 * C3) + C4 */
+
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-slsr" } */
+
+typedef int arr_2[50][50];
+
+void foo (arr_2 a2, int v1)
+{
+ int i, j;
+
+ i = v1 + 5;
+ j = i;
+ a2 [i] [j++] = i;
+ a2 [i] [j++] = i;
+ a2 [i] [i-1] += 1;
+ return;
+}
+
+/* { dg-final { scan-tree-dump-times "MEM" 4 "slsr" } } */
+/* { dg-final { cleanup-tree-dump "slsr" } } */
Index: gcc/gimple-ssa-strength-reduction.c
===================================================================
--- gcc/gimple-ssa-strength-reduction.c (revision 202067)
+++ gcc/gimple-ssa-strength-reduction.c (working copy)
@@ -750,6 +750,57 @@ slsr_process_phi (gimple phi, bool speed)
add_cand_for_stmt (phi, c);
}
+/* Given PBASE which is a pointer to tree, loop up the defining
+ statement for it and check whether the candidate is in the
+ form of:
+
+ X = B + (1 * S), S is integer constant
+ X = B + (i * S), S is integer one
+
+ If so, set PBASE to the candiate's base_expr and return double
+ int (i * S).
+ Otherwise, just return double int zero. */
+
+static double_int
+backtrace_base_for_ref (tree *pbase)
+{
+ tree base_in = *pbase;
+ slsr_cand_t base_cand;
+
+ STRIP_NOPS (base_in);
+ if (TREE_CODE (base_in) != SSA_NAME)
+ return tree_to_double_int (integer_zero_node);
+
+ base_cand = base_cand_from_table (base_in);
+
+ while (base_cand && base_cand->kind != CAND_PHI)
+ {
+ if (base_cand->kind == CAND_ADD
+ && base_cand->index.is_one ()
+ && TREE_CODE (base_cand->stride) == INTEGER_CST)
+ {
+ /* X = B + (1 * S), S is integer constant. */
+ *pbase = base_cand->base_expr;
+ return tree_to_double_int (base_cand->stride);
+ }
+ else if (base_cand->kind == CAND_ADD
+ && TREE_CODE (base_cand->stride) == INTEGER_CST
+ && integer_onep (base_cand->stride))
+ {
+ /* X = B + (i * S), S is integer one. */
+ *pbase = base_cand->base_expr;
+ return base_cand->index;
+ }
+
+ if (base_cand->next_interp)
+ base_cand = lookup_cand (base_cand->next_interp);
+ else
+ base_cand = NULL;
+ }
+
+ return tree_to_double_int (integer_zero_node);
+}
+
/* Look for the following pattern:
*PBASE: MEM_REF (T1, C1)
@@ -767,8 +818,15 @@ slsr_process_phi (gimple phi, bool speed)
*PBASE: T1
*POFFSET: MULT_EXPR (T2, C3)
- *PINDEX: C1 + (C2 * C3) + C4 */
+ *PINDEX: C1 + (C2 * C3) + C4
+ When T2 is recorded by an CAND_ADD in the form of (T2' + C5), It
+ will be further restructured to:
+
+ *PBASE: T1
+ *POFFSET: MULT_EXPR (T2', C3)
+ *PINDEX: C1 + (C2 * C3) + C4 + (C5 * C3) */
+
static bool
restructure_reference (tree *pbase, tree *poffset, double_int *pindex,
tree *ptype)
@@ -777,7 +835,7 @@ restructure_reference (tree *pbase, tree *poffset,
double_int index = *pindex;
double_int bpu = double_int::from_uhwi (BITS_PER_UNIT);
tree mult_op0, mult_op1, t1, t2, type;
- double_int c1, c2, c3, c4;
+ double_int c1, c2, c3, c4, c5;
if (!base
|| !offset
@@ -823,11 +881,12 @@ restructure_reference (tree *pbase, tree *poffset,
}
c4 = index.udiv (bpu, FLOOR_DIV_EXPR);
+ c5 = backtrace_base_for_ref (&t2);
*pbase = t1;
- *poffset = fold_build2 (MULT_EXPR, sizetype, t2,
- double_int_to_tree (sizetype, c3));
- *pindex = c1 + c2 * c3 + c4;
+ *poffset = size_binop (MULT_EXPR, fold_convert (sizetype, t2),
+ double_int_to_tree (sizetype, c3));
+ *pindex = c1 + c2 * c3 + c4 + c5 * c3;
*ptype = type;
return true;
