From 96d75a2c8c3548926dffddfb3b1ce9ce2d51dcfe Mon Sep 17 00:00:00 2001 From: Yufeng Zhang Date: Wed, 4 Dec 2013 08:06:16 +0000 Subject: [PATCH] gimple-ssa-strength-reduction.c: Include tree-affine.h. gcc/ * gimple-ssa-strength-reduction.c: Include tree-affine.h. (name_expansions): New static variable. (alt_base_map): Ditto. (get_alternative_base): New function. (find_basis_for_candidate): For CAND_REF, optionally call find_basis_for_base_expr with the returned value from get_alternative_base. (record_potential_basis): Add new parameter 'base' of type 'tree'; add an assertion of non-NULL base; use base to set node->base_expr. (alloc_cand_and_find_basis): Update; call record_potential_basis for CAND_REF with the returned value from get_alternative_base. (replace_refs): Dump details on the replacing. (execute_strength_reduction): Call pointer_map_create for alt_base_map; call free_affine_expand_cache with &name_expansions. gcc/testsuite/ * gcc.dg/tree-ssa/slsr-39.c: Update. * gcc.dg/tree-ssa/slsr-41.c: New test. From-SVN: r205655 --- gcc/ChangeLog | 17 ++++++ gcc/gimple-ssa-strength-reduction.c | 100 +++++++++++++++++++++++++++++--- gcc/testsuite/ChangeLog | 5 ++ gcc/testsuite/gcc.dg/tree-ssa/slsr-39.c | 4 +- gcc/testsuite/gcc.dg/tree-ssa/slsr-41.c | 24 ++++++++ 5 files changed, 139 insertions(+), 11 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/slsr-41.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 51e1fa0..0e947b7 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,20 @@ +2013-12-04 Yufeng Zhang + + * gimple-ssa-strength-reduction.c: Include tree-affine.h. + (name_expansions): New static variable. + (alt_base_map): Ditto. + (get_alternative_base): New function. + (find_basis_for_candidate): For CAND_REF, optionally call + find_basis_for_base_expr with the returned value from + get_alternative_base. + (record_potential_basis): Add new parameter 'base' of type 'tree'; + add an assertion of non-NULL base; use base to set node->base_expr. + (alloc_cand_and_find_basis): Update; call record_potential_basis + for CAND_REF with the returned value from get_alternative_base. + (replace_refs): Dump details on the replacing. + (execute_strength_reduction): Call pointer_map_create for + alt_base_map; call free_affine_expand_cache with &name_expansions. + 2013-12-03 Wei Mi PR rtl-optimization/59020 diff --git a/gcc/gimple-ssa-strength-reduction.c b/gcc/gimple-ssa-strength-reduction.c index bc2484b..8471812 100644 --- a/gcc/gimple-ssa-strength-reduction.c +++ b/gcc/gimple-ssa-strength-reduction.c @@ -62,6 +62,7 @@ along with GCC; see the file COPYING3. If not see #include "expmed.h" #include "params.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 @@ -429,6 +430,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 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. */ @@ -449,8 +486,9 @@ find_phi_def (tree base) } /* Helper routine for find_basis_for_candidate. May be called twice: - once for the candidate's base expr, and optionally again for the - candidate's phi definition. */ + once for the candidate's base expr, and optionally again either for + the candidate's phi definition or for a CAND_REF's alternative base + expression. */ static slsr_cand_t find_basis_for_base_expr (slsr_cand_t c, tree base_expr) @@ -527,6 +565,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; @@ -537,17 +582,21 @@ 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; + 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); @@ -563,10 +612,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) { @@ -592,7 +649,13 @@ 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) + { + tree alt_base = get_alternative_base (base); + if (alt_base) + record_potential_basis (c, alt_base); + } return c; } @@ -1852,6 +1915,12 @@ replace_ref (tree *expr, slsr_cand_t c) static void replace_refs (slsr_cand_t c) { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fputs ("Replacing reference: ", dump_file); + print_gimple_stmt (dump_file, c->cand_stmt, 0, 0); + } + if (gimple_vdef (c->cand_stmt)) { tree *lhs = gimple_assign_lhs_ptr (c->cand_stmt); @@ -1863,6 +1932,13 @@ replace_refs (slsr_cand_t c) replace_ref (rhs, c); } + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fputs ("With: ", dump_file); + print_gimple_stmt (dump_file, c->cand_stmt, 0, 0); + fputs ("\n", dump_file); + } + if (c->sibling) replace_refs (lookup_cand (c->sibling)); @@ -3533,6 +3609,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); @@ -3548,6 +3627,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/ChangeLog b/gcc/testsuite/ChangeLog index 2fea78d..dcc02b5 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2013-12-04 Yufeng Zhang + + * gcc.dg/tree-ssa/slsr-39.c: Update. + * gcc.dg/tree-ssa/slsr-41.c: New test. + 2013-12-03 Adhemerval Zanella * gcc.target/powerpc/pr57363.c: New test. diff --git a/gcc/testsuite/gcc.dg/tree-ssa/slsr-39.c b/gcc/testsuite/gcc.dg/tree-ssa/slsr-39.c index 8cc2798..c146219 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/slsr-39.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/slsr-39.c @@ -6,7 +6,7 @@ *PINDEX: C1 + (C2 * C3) + C4 */ /* { dg-do compile } */ -/* { dg-options "-O2 -fdump-tree-slsr" } */ +/* { dg-options "-O2 -fdump-tree-slsr-details" } */ typedef int arr_2[50][50]; @@ -22,5 +22,5 @@ void foo (arr_2 a2, int v1) return; } -/* { dg-final { scan-tree-dump-times "MEM" 4 "slsr" } } */ +/* { dg-final { scan-tree-dump-times "Replacing reference: " 4 "slsr" } } */ /* { dg-final { cleanup-tree-dump "slsr" } } */ 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..2c9d908 --- /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-details" } */ + +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 "Replacing reference: " 5 "slsr" } } */ +/* { dg-final { cleanup-tree-dump "slsr" } } */ -- 2.7.4