Hi Yufeng, The second version of your original patch is ok with me with the following changes. Sorry for the little side adventure into the next-interp logic; in the end that's going to hurt more than it helps in this case. Thanks for having a look at it, anyway. Thanks also for cleaning up this version to be less intrusive to common interfaces; I appreciate it.
>diff --git a/gcc/gimple-ssa-strength-reduction.c >b/gcc/gimple-ssa-strength-reduction.c >index 88afc91..d069246 100644 >--- a/gcc/gimple-ssa-strength-reduction.c >+++ b/gcc/gimple-ssa-strength-reduction.c >@@ -53,6 +53,7 @@ along with GCC; see the file COPYING3. If not see > #include "params.h" > #include "hash-table.h" > #include "tree-ssa-address.h" >+#include "tree-affine.h" > > /* Information about a strength reduction candidate. Each statement > in the candidate table represents an expression of one of the >@@ -420,6 +421,42 @@ cand_chain_hasher::equal (const value_type *chain1, const >compare_type *chain2) > /* Hash table embodying a mapping from base exprs to chains of candidates. */ > static hash_table <cand_chain_hasher> base_cand_map; > >+/* Pointer map used by tree_to_aff_combination_expand. */ >+static struct pointer_map_t *name_expansions; >+/* Pointer map embodying a mapping from bases to alternative bases. */ >+static struct pointer_map_t *alt_base_map; >+ >+/* Given BASE, use the tree affine combiniation facilities to >+ find the underlying tree expression for BASE, with any >+ immediate offset excluded. */ >+ >+static tree >+get_alternative_base (tree base) >+{ >+ tree *result = (tree *) pointer_map_contains (alt_base_map, base); >+ >+ if (result == NULL) >+ { >+ tree expr; >+ aff_tree aff; >+ >+ tree_to_aff_combination_expand (base, TREE_TYPE (base), >+ &aff, &name_expansions); >+ aff.offset = tree_to_double_int (integer_zero_node); >+ expr = aff_combination_to_tree (&aff); >+ >+ result = (tree *) pointer_map_insert (alt_base_map, base); >+ gcc_assert (!*result); >+ >+ if (expr == base) >+ *result = NULL; >+ else >+ *result = expr; >+ } >+ >+ return *result; >+} >+ > /* Look in the candidate table for a CAND_PHI that defines BASE and > return it if found; otherwise return NULL. */ > >@@ -439,9 +476,10 @@ find_phi_def (tree base) > return c->cand_num; > } > >-/* Helper routine for find_basis_for_candidate. May be called twice: >+/* Helper routine for find_basis_for_candidate. May be called three times: > once for the candidate's base expr, and optionally again for the >- candidate's phi definition. */ >+ candidate's phi definition, as well as for an alternative base expr >+ in the case of CAND_REF. */ Technically this will never be called three times. It will be called once for the candidate's base expression, and optionally either for the candidate's phi definition or for a CAND_REF's alternative base expression. (There is no phi processing for a CAND_REF.) > > static slsr_cand_t > find_basis_for_base_expr (slsr_cand_t c, tree base_expr) >@@ -518,6 +556,13 @@ find_basis_for_candidate (slsr_cand_t c) > } > } > >+ if (!basis && c->kind == CAND_REF) >+ { >+ tree alt_base_expr = get_alternative_base (c->base_expr); >+ if (alt_base_expr) >+ basis = find_basis_for_base_expr (c, alt_base_expr); >+ } >+ > if (basis) > { > c->sibling = basis->dependent; >@@ -528,17 +573,22 @@ find_basis_for_candidate (slsr_cand_t c) > return 0; > } > >-/* Record a mapping from the base expression of C to C itself, indicating that >- C may potentially serve as a basis using that base expression. */ >+/* Record a mapping from BASE to C, indicating that C may potentially serve >+ as a basis using that base expression. BASE may be the same as >+ C->BASE_EXPR; alternatively BASE can be a different tree that share the >+ underlining expression of C->BASE_EXPR. */ > > static void >-record_potential_basis (slsr_cand_t c) >+record_potential_basis (slsr_cand_t c, tree base) > { > cand_chain_t node; > cand_chain **slot; > >+ if (base == NULL) >+ return; Please do this check outside the common code; it's not necessary except for CAND_REFs. Replace with: gcc_assert (base); >+ > node = (cand_chain_t) obstack_alloc (&chain_obstack, sizeof (cand_chain)); >- node->base_expr = c->base_expr; >+ node->base_expr = base; > node->cand = c; > node->next = NULL; > slot = base_cand_map.find_slot (node, INSERT); >@@ -554,10 +604,18 @@ record_potential_basis (slsr_cand_t c) > } > > /* Allocate storage for a new candidate and initialize its fields. >- Attempt to find a basis for the candidate. */ >+ Attempt to find a basis for the candidate. >+ >+ For CAND_REF, an alternative base may also be recorded and used >+ to find a basis. This helps cases where the expression hidden >+ behind BASE (which is usually an SSA_NAME) has immediate offset, >+ e.g. >+ >+ a2[i][j] = 1; >+ a2[i + 20][j] = 2; */ > > static slsr_cand_t >-alloc_cand_and_find_basis (enum cand_kind kind, gimple gs, tree base, >+alloc_cand_and_find_basis (enum cand_kind kind, gimple gs, tree base, > double_int index, tree stride, tree ctype, > unsigned savings) > { >@@ -583,7 +641,9 @@ alloc_cand_and_find_basis (enum cand_kind kind, gimple gs, >tree base, > else > c->basis = find_basis_for_candidate (c); > >- record_potential_basis (c); >+ record_potential_basis (c, base); >+ if (kind == CAND_REF) >+ record_potential_basis (c, get_alternative_base (base)); Tied to the above change: if (kind == CAND_REF) { tree alt_base = get_alternative_base (base); if (alt_base) record_potential_basis (c, alt_base); } > > return c; > } >@@ -3524,6 +3584,9 @@ execute_strength_reduction (void) > /* Allocate the mapping from base expressions to candidate chains. */ > base_cand_map.create (500); > >+ /* Allocate the mapping from bases to alternative bases. */ >+ alt_base_map = pointer_map_create (); >+ > /* Initialize the loop optimizer. We need to detect flow across > back edges, and this gives us dominator information as well. */ > loop_optimizer_init (AVOID_CFG_MODIFICATIONS); >@@ -3539,6 +3602,9 @@ execute_strength_reduction (void) > dump_cand_chains (); > } > >+ pointer_map_destroy (alt_base_map); >+ free_affine_expand_cache (&name_expansions); >+ > /* Analyze costs and make appropriate replacements. */ > analyze_candidates_and_replace (); > >diff --git a/gcc/testsuite/gcc.dg/tree-ssa/slsr-41.c >b/gcc/testsuite/gcc.dg/tree-ssa/slsr-41.c >new file mode 100644 >index 0000000..870d714 >--- /dev/null >+++ b/gcc/testsuite/gcc.dg/tree-ssa/slsr-41.c >@@ -0,0 +1,24 @@ >+/* Verify straight-line strength reduction in using >+ alternative base expr to record and look for the >+ potential candidate. */ >+ >+/* { 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-10] [j] = 2; >+ a2 [i] [j++] = i; >+ a2 [i+20] [j++] = i; >+ a2 [i-3] [i-1] += 1; >+ return; >+} >+ >+/* { dg-final { scan-tree-dump-times "MEM" 5 "slsr" } } */ >+/* { dg-final { cleanup-tree-dump "slsr" } } */ As mentioned previously, please add the missing newline at EOF. Everything else looks OK to me. Please ask Richard for final approval, as I'm not a maintainer. Thanks, Bill (P.S. I prefer inline patches rather than attachments; it makes it easier to reply with markup.)