This is the mail archive of the
`gcc-patches@gcc.gnu.org`
mailing list for the GCC project.

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |

Other format: | [Raw text] |

*From*: Yufeng Zhang <Yufeng dot Zhang at arm dot com>*To*: Bill Schmidt <wschmidt at linux dot vnet dot ibm dot com>*Cc*: "gcc-patches at gcc dot gnu dot org" <gcc-patches at gcc dot gnu dot org>, Richard Biener <richard dot guenther at gmail dot com>*Date*: Tue, 12 Nov 2013 22:34:13 +0000*Subject*: Re: [PATCH] Optional alternative base_expr in finding basis for CAND_REFs*Authentication-results*: sourceware.org; auth=none*References*: <5277EA58 dot 5020303 at arm dot com> <1384189786 dot 8213 dot 28 dot camel at gnopaine>

Hi Bill, Many thanks for the review.

There are two implications in this approach though:

i1: a2 [i] [j] = 1; i2: a2 [i] [j+1] = 2; i3: a2 [i+20] [j] = i;

i1 --> i2 (base expr is an SSA_NAME defined as (a2 + i * 200)) i1 --> i3 (base expr is a tree expression of (a2 + i * 200))

i1 --> i2 (base expr is an SSA_NAME defined as (a2 + i * 200)) i1 --> i2 --> i3 (base expr is a tree expression of (a2 + i * 200))

- leal 5(%rsi), %edx + leal 5(%rsi), %eax movslq %esi, %rsi - salq $2, %rsi - movslq %edx, %rax - leaq (%rax,%rax,4), %rax - leaq (%rax,%rax,4), %rcx - salq $3, %rcx - leaq (%rdi,%rcx), %rax - addq %rsi, %rax - movl $2, -1980(%rax) - movl %edx, 20(%rax) - movl %edx, 4024(%rax) - leaq -600(%rdi,%rcx), %rax - addl $1, 16(%rsi,%rax) + imulq $204, %rsi, %rsi + addq %rsi, %rdi + movl $2, -980(%rdi) + movl %eax, 1020(%rdi) + movl %eax, 5024(%rdi) + addl $1, 416(%rdi) ret

movw r2, #5024 str r3, [r0, r2]

Here is the changelog: gcc/ * gimple-ssa-strength-reduction.c: Include tree-affine.h. (name_expansions): New static variable. (get_alternative_base): New function. (restructure_reference): Add new local variables 'alt_base' and 'delta'; call get_alternative_base and alloc_cand_and_find_basis to create an alternative interpretation. (num_of_dependents): New function. (preferred_ref_cand): Ditto. (analyze_candidates_and_replace): Call preferred_ref_cand for

(execute_strength_reduction): call free_affine_expand_cache with &name_expansions. gcc/testsuite/ * gcc.dg/tree-ssa/slsr-41.c: New test.

i1 --> i2 (base expr is an SSA_NAME defined as (a2 + i * 200)) i1 --> i2 --> i3 (base expr is a tree expression of (a2 + i * 200))

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'; return if base == NULL; use base to set node->base_expr.

CAND_REF with the returned value from get_alternative_base.

call free_affine_expand_cache with &name_expansions. gcc/testsuite/ * gcc.dg/tree-ssa/slsr-41.c: New test. Which patch do you like more? If you have any question on either of the patch, please let me know. Regards, Yufeng On 11/11/13 17:09, Bill Schmidt wrote:

Hi Yufeng, The idea is a good one but I don't like your implementation of adding an extra expression parameter to look at on the find_basis_for_candidate lookup. This goes against the design of the pass and may not be sufficiently general (might there be situations where a third possible basis could exist?). The overall design is set up to have alternate interpretations of candidates in the candidate table to handle this sort of ambiguity. The goal for your example is create a second candidate (chained to the first one by way of the next_interp field) so that the candidate table looks like this: 8 [2] *_10[j_7(D)] = 2; REF : _10 + ((sizetype) j_7(D) * 4) + 0 : int[20] * basis: 0 dependent: 0 sibling: 0 next-interp: 9 dead-savings: 0 9 [2] *_10[j_7(D)] = 2; REF : _5 + ((sizetype) j_7(D) * 4) + 800 : int[20] * basis: 5 dependent: 0 sibling: 0 next-interp: 0 dead-savings: 0 This will in turn allow subsequent candidates to be seen in terms of either _5 or _10, which may be necessary to avoid missed opportunities. There may be a subsequent REF _15 +... that can be an affine expression of either of these, for example. If you fail to find a basis for a candidate with its first interpretation, you can then follow the next-interp chain to look for a basis for the next one, without the messy passing of extra possibilities to the find-basis routine. I haven't read the patch in detail, but I think this should give you enough to work with to re-design the idea to fit better with the existing framework. Please let me know if you need more information, or if you feel I've misunderstood something. Thanks, Bill On Mon, 2013-11-04 at 18:41 +0000, Yufeng Zhang wrote:Hi, This patch extends the slsr pass to optionally use an alternative base expression in finding basis for CAND_REFs. Currently the pass uses hash-based algorithm to match the base_expr in a candidate. Given a test case like the following, slsr will not be able to recognize the two CAND_REFs have the same basis, as their base_expr are of different SSA_NAMEs: typedef int arr_2[20][20]; void foo (arr_2 a2, int i, int j) { a2[i][j] = 1; a2[i + 10][j] = 2; } The gimple dump before slsr is like the following (using an arm-none-eabi gcc): i.0_2 = (unsigned int) i_1(D); _3 = i.0_2 * 80; _5 = a2_4(D) + _3; *_5[j_7(D)] = 1;<---- _9 = _3 + 800; _10 = a2_4(D) + _9; *_10[j_7(D)] = 2;<---- Here are the dumps for the two CAND_REFs generated for the two statements pointed by the arrows: 4 [2] _5 = a2_4(D) + _3; ADD : a2_4(D) + (80 * i_1(D)) : int[20] * basis: 0 dependent: 0 sibling: 0 next-interp: 0 dead-savings: 0 8 [2] *_10[j_7(D)] = 2; REF : _10 + ((sizetype) j_7(D) * 4) + 0 : int[20] * basis: 5 dependent: 0 sibling: 0 next-interp: 0 dead-savings: 0 As mentioned previously, slsr cannot establish that candidate 4 is the basis for the candidate 8, as they have different base_exprs: a2_4(D) and _10, respectively. However, the two references actually only differ by an immediate offset (800). This patch uses the tree affine combination facilities to create an optional alternative base expression to be used in finding (as well as recording) the basis. It calls tree_to_aff_combination_expand on base_expr, reset the offset field of the generated aff_tree to 0 and generate a tree from it by calling aff_combination_to_tree. The new tree is recorded as a potential basis, and when find_basis_for_candidate fails to find a basis for a CAND_REF in its normal approach, it searches again using a tree expanded in such way. Such an expanded tree usually discloses the expression behind an SSA_NAME. In the example above, instead of seeing the strength reduction candidate chains like this: _5 -> 5 _10 -> 8 we are now having: _5 -> 5 _10 -> 8 a2_4(D) + (sizetype) i_1(D) * 80 -> 5 -> 8 With the candidates 5 and 8 linked to the same tree expression (a2_4(D) + (sizetype) i_1(D) * 80), slsr is now able to establish that 5 is the basis of 8. The patch doesn't attempt to change the content of any CAND_REF though. It only enables CAND_REFs which (1) have the same stride and (2) have the underlying expressions of their base_expr only differ in immediate offsets, to be recognized to have the same basis. The statements with such CAND_REFs will be lowered to MEM_REFs, and later on the RTL expander shall be able to fold and re-associate the immediate offsets to the rightmost side of the addressing expression, and therefore exposes the common sub-expression successfully. The code-gen difference of the example code on arm with -O2 -mcpu=cortex-15 is: mov r3, r1, asl #6 - add ip, r0, r2, asl #2 str lr, [sp, #-4]! + mov ip, #1 + mov lr, #2 add r1, r3, r1, asl #4 - mov lr, #1 - mov r3, #2 add r0, r0, r1 - add r0, r0, #800 - str lr, [ip, r1] - str r3, [r0, r2, asl #2] + add r3, r0, r2, asl #2 + str ip, [r0, r2, asl #2] + str lr, [r3, #800] ldr pc, [sp], #4 One fewer instruction in this simple case. The example used in illustration is too simple to show code-gen difference on x86_64, but the included test case will show the benefit of the patch quite obviously. The patch has passed * bootstrapping on arm and x86_64 * regtest on arm-none-eabi, aarch64-none-elf and x86_64 There is no regression in SPEC2K on arm or x86_64. OK to commit to the trunk? Any comment is welcomed! Thanks, Yufeng gcc/ * gimple-ssa-strength-reduction.c: Include tree-affine.h. (find_basis_for_base_expr): Update comment. (find_basis_for_candidate): Add new parameter 'alt_base_expr' of type 'tree'. Optionally call find_basis_for_base_expr with 'alt_base_expr'. (record_potential_basis): Add new parameter 'alt_base_expr' of type 'tree'; set node->base_expr with 'alt_base_expr' if it is not NULL. (name_expansions): New static variable. (get_alternative_base): New function. (alloc_cand_and_find_basis): Call get_alternative_base for CAND_REF. Update calls to find_basis_for_candidate and record_potential_basis. (execute_strength_reduction): Call free_affine_expand_cache with &name_expansions. gcc/testsuite/ * gcc.dg/tree-ssa/slsr-41.c: New test.

diff --git a/gcc/gimple-ssa-strength-reduction.c b/gcc/gimple-ssa-strength-reduction.c index 88afc91..30e3763 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,31 @@ 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; + +/* 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, double_int *offset) +{ + tree expr; + aff_tree aff; + + tree_to_aff_combination_expand (base, TREE_TYPE (base), + &aff, &name_expansions); + *offset = aff.offset; + aff.offset = tree_to_double_int (integer_zero_node); + expr = aff_combination_to_tree (&aff); + + if (expr == base) + return NULL; + else + return expr; +} + /* Look in the candidate table for a CAND_PHI that defines BASE and return it if found; otherwise return NULL. */ @@ -912,11 +938,11 @@ restructure_reference (tree *pbase, tree *poffset, double_int *pindex, static void slsr_process_ref (gimple gs) { - tree ref_expr, base, offset, type; + tree ref_expr, base, offset, type, alt_base; HOST_WIDE_INT bitsize, bitpos; enum machine_mode mode; int unsignedp, volatilep; - double_int index; + double_int index, delta; slsr_cand_t c; if (gimple_vdef (gs)) @@ -942,6 +968,16 @@ slsr_process_ref (gimple gs) /* Add the candidate to the statement-candidate mapping. */ add_cand_for_stmt (gs, c); + + /* Add alternate interpretation. */ + if ((alt_base = get_alternative_base (base, &delta))) + { + slsr_cand_t c2 = + alloc_cand_and_find_basis (CAND_REF, gs, alt_base, index + delta, + offset, type, 0); + + c->next_interp = c2->cand_num; + } } /* Create a candidate entry for a statement GS, where GS multiplies @@ -1802,6 +1838,80 @@ dump_incr_vec (void) } } +/* Helper routine for preferred_ref_cand. Given C which is a CAND_REF, + recursively count and return the number of dependents, including + itself. */ + +static int +num_of_dependents (slsr_cand_t c) +{ + int n = 1; + + if (c->sibling) + n += num_of_dependents (lookup_cand (c->sibling)); + + if (c->dependent) + n += num_of_dependents (lookup_cand (c->dependent)); + + return n; +} + +/* Some of the memory accessing gimple statements have two CAND_REF + candidates as a result of an optional backtracing into the base + expr. The routine checks and compares the two candidates, if both + exist; the candidate with a more dominating basis or the one + whose dependency graph has more nodes is returned. In the case of + a draw, the candidate with the original base expr (primary) is + preferred to the backtraced one (secondary). C is the CAND_REF + to be checked. + + The whole idea is to avoid these gimple statements to be + replace_ref 'ed twice, and in a random order. */ + +static slsr_cand_t +preferred_ref_cand (slsr_cand_t c) +{ + slsr_cand_t primary, secondary, theother; + slsr_cand_t *result + = (slsr_cand_t *) pointer_map_contains (stmt_cand_map, + c->cand_stmt); + gcc_assert (result); + + primary = *result; + if (primary->next_interp) + secondary = lookup_cand (primary->next_interp); + else + secondary = NULL; + + gcc_assert (c == primary || c == secondary); + theother = c == primary ? secondary : primary; + + if (theother) + { + /* An earlier basis exists! The replacement may have + already happened. */ + if (theother->basis != 0) + return theother; + + if (theother->dependent != 0) + { + int num_c = num_of_dependents (c); + int num_t = num_of_dependents (theother); + + /* Fewer dependents, lower priority. */ + if (num_c < num_t) + return theother; + + /* When the numbers are the same, the primary candiate + is preferred. */ + if (num_c == num_t && theother == primary) + return theother; + } + } + + return c; +} + /* Replace *EXPR in candidate C with an equivalent strength-reduced data reference. */ @@ -3453,7 +3563,20 @@ analyze_candidates_and_replace (void) /* If this is a chain of CAND_REFs, unconditionally replace each of them with a strength-reduced data reference. */ if (c->kind == CAND_REF) - replace_refs (c); + { + slsr_cand_t t = preferred_ref_cand (c); + + if (t != c) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "\tProcessing skipped: " + "higher-priority dependency tree is detected, " + "where %d is chained.\n", t->cand_num); + continue; + } + + replace_refs (c); + } /* If the common stride of all related candidates is a known constant, each candidate without a phi-dependence can be @@ -3539,6 +3662,8 @@ execute_strength_reduction (void) dump_cand_chains (); } + 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" } } */

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. */ 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; + 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)); 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" } } */

**Follow-Ups**:**Re: [PATCH] Optional alternative base_expr in finding basis for CAND_REFs***From:*Bill Schmidt

**References**:**[PATCH] Optional alternative base_expr in finding basis for CAND_REFs***From:*Yufeng Zhang

**Re: [PATCH] Optional alternative base_expr in finding basis for CAND_REFs***From:*Bill Schmidt

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |