| Message ID | 5277EA58.5020303@arm.com |
|---|---|
| State | New |
| Headers | show |
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 9a5072c..3150046 100644 --- a/gcc/gimple-ssa-strength-reduction.c +++ b/gcc/gimple-ssa-strength-reduction.c @@ -48,6 +48,7 @@ along with GCC; see the file COPYING3. If not see #include "expmed.h" #include "params.h" #include "hash-table.h" +#include "tree-affine.h" /* Information about a strength reduction candidate. Each statement in the candidate table represents an expression of one of the @@ -434,9 +435,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 + passed as the 2nd argument to find_basis_for_candidate. */ static slsr_cand_t find_basis_for_base_expr (slsr_cand_t c, tree base_expr) @@ -477,10 +479,13 @@ find_basis_for_base_expr (slsr_cand_t c, tree base_expr) appear in a block that dominates the candidate statement and have the same stride and type. If more than one possible basis exists, the one with highest index in the vector is chosen; this will be - the most immediately dominating basis. */ + the most immediately dominating basis. + + When ALT_BASE_EXPR is not NULL, it will also be used to look for + possible candidates if all previous attempts have failed. */ static int -find_basis_for_candidate (slsr_cand_t c) +find_basis_for_candidate (slsr_cand_t c, tree alt_base_expr) { slsr_cand_t basis = find_basis_for_base_expr (c, c->base_expr); @@ -513,6 +518,9 @@ find_basis_for_candidate (slsr_cand_t c) } } + if (!basis && alt_base_expr) + basis = find_basis_for_base_expr (c, alt_base_expr); + if (basis) { c->sibling = basis->dependent; @@ -524,16 +532,17 @@ find_basis_for_candidate (slsr_cand_t c) } /* 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. */ + C may potentially serve as a basis using that base expression. Use + ALT_BASE_EXPR as the base expression instead, if it is not NULL. */ static void -record_potential_basis (slsr_cand_t c) +record_potential_basis (slsr_cand_t c, tree alt_base_expr) { cand_chain_t node; cand_chain **slot; node = (cand_chain_t) obstack_alloc (&chain_obstack, sizeof (cand_chain)); - node->base_expr = c->base_expr; + node->base_expr = alt_base_expr ? alt_base_expr : c->base_expr; node->cand = c; node->next = NULL; slot = base_cand_map.find_slot (node, INSERT); @@ -548,14 +557,46 @@ record_potential_basis (slsr_cand_t c) *slot = node; } +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) +{ + 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); + + if (expr == base) + expr = NULL; + + return expr; +} + /* 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) { + tree alt_base_expr = NULL; slsr_cand_t c = (slsr_cand_t) obstack_alloc (&cand_obstack, sizeof (slsr_cand)); c->cand_stmt = gs; @@ -573,12 +614,17 @@ alloc_cand_and_find_basis (enum cand_kind kind, gimple gs, tree base, cand_vec.safe_push (c); + if (kind == CAND_REF) + alt_base_expr = get_alternative_base (base); + if (kind == CAND_PHI) c->basis = 0; else - c->basis = find_basis_for_candidate (c); + c->basis = find_basis_for_candidate (c, alt_base_expr); - record_potential_basis (c); + record_potential_basis (c, NULL); + if (alt_base_expr) + record_potential_basis (c, alt_base_expr); return c; } @@ -3534,6 +3580,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" } } */
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.