[PATCH 3/4 v2] Enhance SCEV to follow copies of SSA_NAMEs.
(Previous message: https://gcc.gnu.org/ml/gcc-patches/2015-12/msg02159.html)
On Sat, Dec 26, 2015 at 18:58 PM, Richard Biener
wrote:
>> I'm not sure whether adding a pass_copy_prop is the right thing here, but
>> since
>> loop-header-copying can create such opportunities, it seems good to take
>> them!
>
> Aww. I'd rather have general infrastructure (like SCEV) deal with
> those non-propagated copies.
>
> There are likely other missed propagation / folding opportunities
> caused from partial peeling.
>
> Richard.
I take your second point, but I am concerned that this leads to duplication of
copy-propagation code throughout the compiler?
However, this patch does that. Making analyze_initial_condition (alone) follow
copies, is enough to solve my case of missed vectorization of pr65947-2.c;
but I also used the routine in analyze_scalar_evolution_1, as it found copies
to follow in both bootstrap and a significant number of testcases:
c-c++-common/gomp/pr58472.c
gcc.c-torture/execute/2422-1.c
gcc.c-torture/execute/20041213-2.c
gcc.c-torture/execute/20100430-1.c
gcc.c-torture/execute/pr49712.c
gcc.c-torture/execute/pr58640.c
gcc.dg/Warray-bounds-13.c
gcc.dg/graphite/block-{1,5,6}.c
gcc.dg/graphite/interchange-12.c
gcc.dg/graphite/interchange-mvt.c
gcc.dg/graphite/pr19910.c
gcc.dg/graphite/uns-block-1.c
gcc.dg/loop-unswitch-{2,4}.c
gcc.dg/pr59670.c
gcc.dg/torture/matrix-{1,2,3,4,5,6}.c
gcc.dg/torture/pr24750-1.c
gcc.dg/torture/transpose-{1,2,3,4,5,6}.c
...some of which were resolved to constants.
(Of course, this approach is not as thorough as adding a pass_copy_prop. E.g. it
does *not* enable vectorization of the inlined copy in pr65947-9.c.)
Bootstrapped + check-gcc + check-g++ on ARM, AArch64, x86_64.
gcc/ChangeLog:
* tree-scalar-evolution.c (follow_copies): New.
(analyze_initial_condition, analyze_scalar_evolution_1): Call previous.
---
gcc/tree-scalar-evolution.c | 53 ++---
1 file changed, 36 insertions(+), 17 deletions(-)
diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
index 9b33693..357eb8f 100644
--- a/gcc/tree-scalar-evolution.c
+++ b/gcc/tree-scalar-evolution.c
@@ -1522,6 +1522,37 @@ analyze_evolution_in_loop (gphi *loop_phi_node,
return evolution_function;
}
+/* While VAR is an SSA_NAME whose definition is a straight copy of another
name,
+ or (perhaps via a degenerate phi) a constant, follows that definition.
+ Returns the constant, or the earliest SSA_NAME whose definition is neither
+ constant nor copy. */
+
+static tree
+follow_copies (tree var)
+{
+ while (TREE_CODE (var) == SSA_NAME)
+{
+ gimple *def = SSA_NAME_DEF_STMT (var);
+ if (gphi *phi = dyn_cast (def))
+ {
+ tree rhs = degenerate_phi_result (phi);
+ /* Don't follow degenerate phi's of SSA_NAMES, that can break
+loop-closed SSA form. */
+ if (rhs && is_gimple_min_invariant (rhs))
+ var = rhs;
+ break;
+ }
+ else if (gimple_assign_single_p (def)
+ && !gimple_vuse (def)
+ && (gimple_assign_rhs_code (def) == SSA_NAME
+ || is_gimple_min_invariant (gimple_assign_rhs1 (def
+ var = gimple_assign_rhs1 (def);
+ else
+ break;
+}
+ return var;
+}
+
/* Given a loop-phi-node, return the initial conditions of the
variable on entry of the loop. When the CCP has propagated
constants into the loop-phi-node, the initial condition is
@@ -1574,21 +1605,9 @@ analyze_initial_condition (gphi *loop_phi_node)
if (init_cond == chrec_not_analyzed_yet)
init_cond = chrec_dont_know;
- /* During early loop unrolling we do not have fully constant propagated IL.
- Handle degenerate PHIs here to not miss important unrollings. */
- if (TREE_CODE (init_cond) == SSA_NAME)
-{
- gimple *def = SSA_NAME_DEF_STMT (init_cond);
- if (gphi *phi = dyn_cast (def))
- {
- tree res = degenerate_phi_result (phi);
- if (res != NULL_TREE
- /* Only allow invariants here, otherwise we may break
-loop-closed SSA form. */
- && is_gimple_min_invariant (res))
- init_cond = res;
- }
-}
+ /* We may not have fully constant propagated IL. Handle degenerate PHIs here
+ to not miss important early loop unrollings. */
+ init_cond = follow_copies (init_cond);
if (dump_file && (dump_flags & TDF_SCEV))
{
@@ -1968,8 +1987,8 @@ analyze_scalar_evolution_1 (struct loop *loop, tree var,
tree res)
if (bb == NULL
|| !flow_bb_inside_loop_p (loop, bb))
{
- /* Keep the symbolic form. */
- res = var;
+ /* Keep symbolic form, but look through obvious copies for constants. */
+ res = follow_copies (var);
goto set_and_end;
}
--
1.9.1
Re: [PATCH 3/4 v2] Enhance SCEV to follow copies of SSA_NAMEs.
On Thu, Jan 14, 2016 at 11:29 AM, Alan Lawrence wrote:
> (Previous message: https://gcc.gnu.org/ml/gcc-patches/2015-12/msg02159.html)
> On Sat, Dec 26, 2015 at 18:58 PM, Richard Biener
> wrote:
>
>>> I'm not sure whether adding a pass_copy_prop is the right thing here, but
>>> since
>>> loop-header-copying can create such opportunities, it seems good to take
>>> them!
>>
>> Aww. I'd rather have general infrastructure (like SCEV) deal with
>> those non-propagated copies.
>>
>> There are likely other missed propagation / folding opportunities
>> caused from partial peeling.
>>
>> Richard.
>
> I take your second point, but I am concerned that this leads to duplication of
> copy-propagation code throughout the compiler?
>
> However, this patch does that. Making analyze_initial_condition (alone) follow
> copies, is enough to solve my case of missed vectorization of pr65947-2.c;
> but I also used the routine in analyze_scalar_evolution_1, as it found copies
> to follow in both bootstrap and a significant number of testcases:
>
> c-c++-common/gomp/pr58472.c
> gcc.c-torture/execute/2422-1.c
> gcc.c-torture/execute/20041213-2.c
> gcc.c-torture/execute/20100430-1.c
> gcc.c-torture/execute/pr49712.c
> gcc.c-torture/execute/pr58640.c
> gcc.dg/Warray-bounds-13.c
> gcc.dg/graphite/block-{1,5,6}.c
> gcc.dg/graphite/interchange-12.c
> gcc.dg/graphite/interchange-mvt.c
> gcc.dg/graphite/pr19910.c
> gcc.dg/graphite/uns-block-1.c
> gcc.dg/loop-unswitch-{2,4}.c
> gcc.dg/pr59670.c
> gcc.dg/torture/matrix-{1,2,3,4,5,6}.c
> gcc.dg/torture/pr24750-1.c
> gcc.dg/torture/transpose-{1,2,3,4,5,6}.c
>
> ...some of which were resolved to constants.
>
> (Of course, this approach is not as thorough as adding a pass_copy_prop. E.g.
> it
> does *not* enable vectorization of the inlined copy in pr65947-9.c.)
>
> Bootstrapped + check-gcc + check-g++ on ARM, AArch64, x86_64.
>
> gcc/ChangeLog:
>
> * tree-scalar-evolution.c (follow_copies): New.
> (analyze_initial_condition, analyze_scalar_evolution_1): Call
> previous.
> ---
> gcc/tree-scalar-evolution.c | 53
> ++---
> 1 file changed, 36 insertions(+), 17 deletions(-)
>
> diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
> index 9b33693..357eb8f 100644
> --- a/gcc/tree-scalar-evolution.c
> +++ b/gcc/tree-scalar-evolution.c
> @@ -1522,6 +1522,37 @@ analyze_evolution_in_loop (gphi *loop_phi_node,
>return evolution_function;
> }
>
> +/* While VAR is an SSA_NAME whose definition is a straight copy of another
> name,
> + or (perhaps via a degenerate phi) a constant, follows that definition.
> + Returns the constant, or the earliest SSA_NAME whose definition is neither
> + constant nor copy. */
> +
> +static tree
> +follow_copies (tree var)
> +{
> + while (TREE_CODE (var) == SSA_NAME)
> +{
> + gimple *def = SSA_NAME_DEF_STMT (var);
> + if (gphi *phi = dyn_cast (def))
> + {
> + tree rhs = degenerate_phi_result (phi);
> + /* Don't follow degenerate phi's of SSA_NAMES, that can break
> +loop-closed SSA form. */
> + if (rhs && is_gimple_min_invariant (rhs))
> + var = rhs;
> + break;
> + }
> + else if (gimple_assign_single_p (def)
> + && !gimple_vuse (def)
The vuse test is not necessary
> + && (gimple_assign_rhs_code (def) == SSA_NAME
> + || is_gimple_min_invariant (gimple_assign_rhs1 (def
and the is_gimple_min_invariant (rhs1) test is not sufficient if you
consider - (-INT_MIN) with -ftrapv for example.
I'd say you should do
else if (gassign *ass = dyn_cast (def))
{
tree_code code = gimple_assign_rhs_code (ass);
if (code == SSA_NAME
|| CONSTANT_CLASS_P (code))
var = gimple_assign_rhs1 (ass);
else
break;
}
> + var = gimple_assign_rhs1 (def);
> + else
> + break;
> +}
> + return var;
> +}
> +
> /* Given a loop-phi-node, return the initial conditions of the
> variable on entry of the loop. When the CCP has propagated
> constants into the loop-phi-node, the initial condition is
> @@ -1574,21 +1605,9 @@ analyze_initial_condition (gphi *loop_phi_node)
>if (init_cond == chrec_not_analyzed_yet)
> init_cond = chrec_dont_know;
>
> - /* During early loop unrolling we do not have fully constant propagated IL.
> - Handle degenerate PHIs here to not miss important unrollings. */
> - if (TREE_CODE (init_cond) == SSA_NAME)
> -{
> - gimple *def = SSA_NAME_DEF_STMT (init_cond);
> - if (gphi *phi = dyn_cast (def))
> - {
> - tree res = degenerate_phi_result (phi);
> - if (res != NULL_TREE
> - /* Only allow invariants here, otherwise we may break
> -loop-closed SSA form. */
> - && is_gimple_min_invariant (res))
> - init_cond = res;
> - }
> -}
> + /* We may not have fully constant
Re: [PATCH 3/4 v2] Enhance SCEV to follow copies of SSA_NAMEs.
On Thu, Jan 14, 2016 at 12:30 PM, Richard Biener
wrote:
>
> The vuse test is not necessary
>
>> + && (gimple_assign_rhs_code (def) == SSA_NAME
>> + || is_gimple_min_invariant (gimple_assign_rhs1 (def
>
> and the is_gimple_min_invariant (rhs1) test is not sufficient if you
> consider - (-INT_MIN) with -ftrapv for example.
Thanks, I didn't realize gimple_min_invariant would allow such cases.
>> + /* Keep symbolic form, but look through obvious copies for constants.
>> */
>
> You're also looing for SSA names copied so the comment is sligntly wrong.
So it occurs to me that we do only need to look for constants: picking one SSA
name instead of another (when both are outside the loop) doesn't really help
SCEV; and it seems safer/less change to avoid fiddling around with which names
are used. Moreover, given we are in LC _SSA_, I think we can look through
degenerate phi's even of SSA_NAMES, without violating loop-closed-ness,
so long as we only use cases where we eventually reach a constant.
Therefore, how about this version?
(Bootstrapped + check-gcc + check-g++ on x86_64, AArch64, ARM; again, fixing
vectorization of pr65947-2.c).
If this is OK - that leaves only the first patch to SRA,
https://gcc.gnu.org/ml/gcc-patches/2015-12/msg02117.html (the "extra" fixes
I claimed in the guality testsuite were a testing mistake, but this
version still fixes the regressions in guality pr54970.c from the original
"ok with the comment added and a testcase (or two)"
https://gcc.gnu.org/ml/gcc-patches/2015-11/msg01948.html, as well as the
comment + 2*testcase). I think I'd still like to propose these as a stage 3/4
fix (with --param sra-max-scalarization-size-Ospeed=32) of PR/63679, a
regression against gcc 4.9.
Thanks, Alan
gcc/ChangeLog:
* tree-scalar-evolution.c (follow_copies_to_constant): New.
(analyze_initial_condition, analyze_scalar_evolution_1): Call previous.
---
gcc/tree-scalar-evolution.c | 50 ++---
1 file changed, 33 insertions(+), 17 deletions(-)
diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
index 9b33693..470c3ea 100644
--- a/gcc/tree-scalar-evolution.c
+++ b/gcc/tree-scalar-evolution.c
@@ -1522,6 +1522,34 @@ analyze_evolution_in_loop (gphi *loop_phi_node,
return evolution_function;
}
+/* Looks to see if VAR is a copy of a constant (via straightforward assignments
+ or degenerate phi's). If so, returns the constant; else, returns VAR. */
+
+static tree
+follow_copies_to_constant (tree var)
+{
+ tree res = var;
+ while (TREE_CODE (res) == SSA_NAME)
+{
+ gimple *def = SSA_NAME_DEF_STMT (res);
+ if (gphi *phi = dyn_cast (def))
+ {
+ if (tree rhs = degenerate_phi_result (phi))
+ res = rhs;
+ else
+ break;
+ }
+ else if (gimple_assign_single_p (def))
+ /* Will exit loop if not an SSA_NAME. */
+ res = gimple_assign_rhs1 (def);
+ else
+ break;
+}
+ if (CONSTANT_CLASS_P (res))
+return res;
+ return var;
+}
+
/* Given a loop-phi-node, return the initial conditions of the
variable on entry of the loop. When the CCP has propagated
constants into the loop-phi-node, the initial condition is
@@ -1574,21 +1602,9 @@ analyze_initial_condition (gphi *loop_phi_node)
if (init_cond == chrec_not_analyzed_yet)
init_cond = chrec_dont_know;
- /* During early loop unrolling we do not have fully constant propagated IL.
- Handle degenerate PHIs here to not miss important unrollings. */
- if (TREE_CODE (init_cond) == SSA_NAME)
-{
- gimple *def = SSA_NAME_DEF_STMT (init_cond);
- if (gphi *phi = dyn_cast (def))
- {
- tree res = degenerate_phi_result (phi);
- if (res != NULL_TREE
- /* Only allow invariants here, otherwise we may break
-loop-closed SSA form. */
- && is_gimple_min_invariant (res))
- init_cond = res;
- }
-}
+ /* We may not have fully constant propagated IL. Handle degenerate PHIs here
+ to not miss important early loop unrollings. */
+ init_cond = follow_copies_to_constant (init_cond);
if (dump_file && (dump_flags & TDF_SCEV))
{
@@ -1968,8 +1984,8 @@ analyze_scalar_evolution_1 (struct loop *loop, tree var,
tree res)
if (bb == NULL
|| !flow_bb_inside_loop_p (loop, bb))
{
- /* Keep the symbolic form. */
- res = var;
+ /* Keep symbolic form, but look through obvious copies for constants. */
+ res = follow_copies_to_constant (var);
goto set_and_end;
}
--
1.9.1
Re: [PATCH 3/4 v2] Enhance SCEV to follow copies of SSA_NAMEs.
On Fri, Jan 15, 2016 at 10:47 AM, Alan Lawrence wrote:
> On Thu, Jan 14, 2016 at 12:30 PM, Richard Biener
> wrote:
>
>>
>> The vuse test is not necessary
>>
>>> + && (gimple_assign_rhs_code (def) == SSA_NAME
>>> + || is_gimple_min_invariant (gimple_assign_rhs1 (def
>>
>> and the is_gimple_min_invariant (rhs1) test is not sufficient if you
>> consider - (-INT_MIN) with -ftrapv for example.
>
> Thanks, I didn't realize gimple_min_invariant would allow such cases.
Well, the invariant would be -INT_MIN but gimple_assign_rhs_code (def) would
be NEGATE_EXPR. Basically you forgot about unary operators.
>>> + /* Keep symbolic form, but look through obvious copies for
>>> constants. */
>>
>> You're also looing for SSA names copied so the comment is sligntly wrong.
>
> So it occurs to me that we do only need to look for constants: picking one SSA
> name instead of another (when both are outside the loop) doesn't really help
> SCEV; and it seems safer/less change to avoid fiddling around with which names
> are used. Moreover, given we are in LC _SSA_, I think we can look through
> degenerate phi's even of SSA_NAMES, without violating loop-closed-ness,
> so long as we only use cases where we eventually reach a constant.
True.
> Therefore, how about this version?
>
> (Bootstrapped + check-gcc + check-g++ on x86_64, AArch64, ARM; again, fixing
> vectorization of pr65947-2.c).
This version is ok. I wonder if you have a testcase (maybe it comes with the
still pending patches)
> If this is OK - that leaves only the first patch to SRA,
> https://gcc.gnu.org/ml/gcc-patches/2015-12/msg02117.html (the "extra" fixes
> I claimed in the guality testsuite were a testing mistake, but this
> version still fixes the regressions in guality pr54970.c from the original
> "ok with the comment added and a testcase (or two)"
> https://gcc.gnu.org/ml/gcc-patches/2015-11/msg01948.html, as well as the
> comment + 2*testcase). I think I'd still like to propose these as a stage 3/4
> fix (with --param sra-max-scalarization-size-Ospeed=32) of PR/63679, a
> regression against gcc 4.9.
Can you ping the specific patches?
Thanks,
Richard.
> Thanks, Alan
>
> gcc/ChangeLog:
>
> * tree-scalar-evolution.c (follow_copies_to_constant): New.
> (analyze_initial_condition, analyze_scalar_evolution_1): Call
> previous.
> ---
> gcc/tree-scalar-evolution.c | 50
> ++---
> 1 file changed, 33 insertions(+), 17 deletions(-)
>
> diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
> index 9b33693..470c3ea 100644
> --- a/gcc/tree-scalar-evolution.c
> +++ b/gcc/tree-scalar-evolution.c
> @@ -1522,6 +1522,34 @@ analyze_evolution_in_loop (gphi *loop_phi_node,
>return evolution_function;
> }
>
> +/* Looks to see if VAR is a copy of a constant (via straightforward
> assignments
> + or degenerate phi's). If so, returns the constant; else, returns VAR. */
> +
> +static tree
> +follow_copies_to_constant (tree var)
> +{
> + tree res = var;
> + while (TREE_CODE (res) == SSA_NAME)
> +{
> + gimple *def = SSA_NAME_DEF_STMT (res);
> + if (gphi *phi = dyn_cast (def))
> + {
> + if (tree rhs = degenerate_phi_result (phi))
> + res = rhs;
> + else
> + break;
> + }
> + else if (gimple_assign_single_p (def))
> + /* Will exit loop if not an SSA_NAME. */
> + res = gimple_assign_rhs1 (def);
> + else
> + break;
> +}
> + if (CONSTANT_CLASS_P (res))
> +return res;
> + return var;
> +}
> +
> /* Given a loop-phi-node, return the initial conditions of the
> variable on entry of the loop. When the CCP has propagated
> constants into the loop-phi-node, the initial condition is
> @@ -1574,21 +1602,9 @@ analyze_initial_condition (gphi *loop_phi_node)
>if (init_cond == chrec_not_analyzed_yet)
> init_cond = chrec_dont_know;
>
> - /* During early loop unrolling we do not have fully constant propagated IL.
> - Handle degenerate PHIs here to not miss important unrollings. */
> - if (TREE_CODE (init_cond) == SSA_NAME)
> -{
> - gimple *def = SSA_NAME_DEF_STMT (init_cond);
> - if (gphi *phi = dyn_cast (def))
> - {
> - tree res = degenerate_phi_result (phi);
> - if (res != NULL_TREE
> - /* Only allow invariants here, otherwise we may break
> -loop-closed SSA form. */
> - && is_gimple_min_invariant (res))
> - init_cond = res;
> - }
> -}
> + /* We may not have fully constant propagated IL. Handle degenerate PHIs
> here
> + to not miss important early loop unrollings. */
> + init_cond = follow_copies_to_constant (init_cond);
>
>if (dump_file && (dump_flags & TDF_SCEV))
> {
> @@ -1968,8 +1984,8 @@ analyze_scalar_evolution_1 (struct loop *loop, tree
> var, tree res)
>if (bb == NULL
>|| !flow_bb_inside_loop_p (loop, bb))
Re: [PATCH 3/4 v2] Enhance SCEV to follow copies of SSA_NAMEs.
On 15/01/16 10:07, Richard Biener wrote: On Fri, Jan 15, 2016 at 10:47 AM, Alan Lawrence wrote: On Thu, Jan 14, 2016 at 12:30 PM, Richard Biener wrote: The vuse test is not necessary + && (gimple_assign_rhs_code (def) == SSA_NAME + || is_gimple_min_invariant (gimple_assign_rhs1 (def and the is_gimple_min_invariant (rhs1) test is not sufficient if you consider - (-INT_MIN) with -ftrapv for example. Thanks, I didn't realize gimple_min_invariant would allow such cases. Well, the invariant would be -INT_MIN but gimple_assign_rhs_code (def) would be NEGATE_EXPR. Basically you forgot about unary operators. Hmm, shouldn't those have get_gimple_rhs_class(gimple_assign_rhs_code(stmt)) == GIMPLE_UNARY_RHS, rather than GIMPLE_SINGLE_RHS as checked for by gimple_assign_single_p? If SINGLE_RHS includes unary operators, the new version of the patch is as flawed as the previous, in that it drops the unary operator altogether. --Alan
Re: [PATCH 3/4 v2] Enhance SCEV to follow copies of SSA_NAMEs.
On Fri, Jan 15, 2016 at 11:38 AM, Alan Lawrence wrote: > On 15/01/16 10:07, Richard Biener wrote: >> >> On Fri, Jan 15, 2016 at 10:47 AM, Alan Lawrence >> wrote: >>> >>> On Thu, Jan 14, 2016 at 12:30 PM, Richard Biener >>> wrote: >>> The vuse test is not necessary > + && (gimple_assign_rhs_code (def) == SSA_NAME > + || is_gimple_min_invariant (gimple_assign_rhs1 > (def and the is_gimple_min_invariant (rhs1) test is not sufficient if you consider - (-INT_MIN) with -ftrapv for example. >>> >>> >>> Thanks, I didn't realize gimple_min_invariant would allow such cases. >> >> >> Well, the invariant would be -INT_MIN but gimple_assign_rhs_code (def) >> would >> be NEGATE_EXPR. Basically you forgot about unary operators. > > > Hmm, shouldn't those have get_gimple_rhs_class(gimple_assign_rhs_code(stmt)) > == GIMPLE_UNARY_RHS, rather than GIMPLE_SINGLE_RHS as checked for by > gimple_assign_single_p? Doh, of course. > If SINGLE_RHS includes unary operators, the new version of the patch is as > flawed as the previous, in that it drops the unary operator altogether. > > --Alan
