diff options
Diffstat (limited to 'gcc/gimple-ssa-strength-reduction.c')
| -rw-r--r-- | gcc/gimple-ssa-strength-reduction.c | 105 |
1 files changed, 95 insertions, 10 deletions
diff --git a/gcc/gimple-ssa-strength-reduction.c b/gcc/gimple-ssa-strength-reduction.c index bc2484b5b13..9320b51cb5d 100644 --- a/gcc/gimple-ssa-strength-reduction.c +++ b/gcc/gimple-ssa-strength-reduction.c @@ -1,5 +1,5 @@ /* Straight-line strength reduction. - Copyright (C) 2012-2013 Free Software Foundation, Inc. + Copyright (C) 2012-2014 Free Software Foundation, Inc. Contributed by Bill Schmidt, IBM <wschmidt@linux.ibm.com> This file is part of GCC. @@ -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,45 @@ 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. + + N.B. we should eliminate this backtracking with better forward + analysis in a future release. */ + +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 +489,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 +568,13 @@ find_basis_for_candidate (slsr_cand_t c) } } + if (flag_expensive_optimizations && !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 +585,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 +615,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 +652,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 (flag_expensive_optimizations && kind == CAND_REF) + { + tree alt_base = get_alternative_base (base); + if (alt_base) + record_potential_basis (c, alt_base); + } return c; } @@ -1852,6 +1918,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 +1935,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 +3612,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 +3630,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 (); |