* [PATCH][PR tree-optimization/69196] Improve accounting in backwards (FSM) threader
@ 2016-03-01 21:46 Jeff Law
2016-03-02 10:51 ` Richard Biener
0 siblings, 1 reply; 4+ messages in thread
From: Jeff Law @ 2016-03-01 21:46 UTC (permalink / raw)
To: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 630 bytes --]
Another step along the path to fixing 69196. As I was investigating the
regression, one of the things that became quite clear was that we'd
greatly increased the number of PHIs and many of the PHI arguments were
constants (which in turn never coalesce and thus generate a constant
initialization).
I think this addresses the accounting issues relevant to 69196 in the
backwards (FSM) threader. I don't expect this patch in and of itself to
have any significant impact on the testcase -- it's just preparatory
work for the clamp.
Bootstrapped and regression tested on x86_64-linux-gnu. Installed on
the trunk.
Jeff
[-- Attachment #2: patch --]
[-- Type: text/plain, Size: 4913 bytes --]
commit 5810fc48902c737b3e0ea24bd2a709edbde41ff2
Author: Jeff Law <law@redhat.com>
Date: Tue Mar 1 14:41:35 2016 -0700
PR tree-optimization/69196
* tree-ssa-threadbackward.c (fsm_find_control_statement_thread_paths):
Do count some PHIs in the thread path against the insn count. Decrease
final statement count by one as the control statement in the last
block will get removed. Remove special cased code for handling PHIs in the last block.
PR tree-optimization/69196
* gcc.dg/tree-ssa/vrp46.c: Twiddle threading params to keep it from
duplicating code and spoiling the expected output.
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index b758d42..c1f2557 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,11 @@
+2016-03-01 Jeff Law <law@redhat.com>
+
+ PR tree-optimization/69196
+ * tree-ssa-threadbackward.c (fsm_find_control_statement_thread_paths):
+ Do count some PHIs in the thread path against the insn count. Decrease
+ final statement count by one as the control statement in the last
+ block will get removed. Remove special cased code for handling PHIs in the last block.
+
2016-03-01 Uros Bizjak <ubizjak@gmail.com>
PR target/70027
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 000ece8..ef8a987 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,9 @@
+2016-03-01 Jeff Law <law@redhat.com>
+
+ PR tree-optimization/69196
+ * gcc.dg/tree-ssa/vrp46.c: Twiddle threading params to keep it from
+ duplicating code and spoiling the expected output.
+
2016-03-01 Michael Meissner <meissner@linux.vnet.ibm.com>
PR target/70033
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c
index 8923eb4..d3c9ed1 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-vrp1" } */
+/* { dg-options "-O2 -fdump-tree-vrp1 --param fsm-scale-path-blocks=1" } */
int func_81 (int);
int func_98 (int);
diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index 55dbcad..3028504 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -286,6 +286,37 @@ fsm_find_control_statement_thread_paths (tree name,
break;
}
+ /* PHIs in the path will create degenerate PHIS in the
+ copied path which will then get propagated away, so
+ looking at just the duplicate path the PHIs would
+ seem unimportant.
+
+ But those PHIs, because they're assignments to objects
+ typically with lives that exist outside the thread path,
+ will tend to generate PHIs (or at least new PHI arguments)
+ at points where we leave the thread path and rejoin
+ the original blocks. So we do want to account for them.
+
+ We ignore virtual PHIs. We also ignore cases where BB
+ has a single incoming edge. That's the most common
+ degenerate PHI we'll see here. Finally we ignore PHIs
+ that are associated with the value we're tracking as
+ that object likely dies. */
+ if (EDGE_COUNT (bb->succs) > 1 && EDGE_COUNT (bb->preds) > 1)
+ {
+ for (gphi_iterator gsip = gsi_start_phis (bb);
+ !gsi_end_p (gsip);
+ gsi_next (&gsip))
+ {
+ gphi *phi = gsip.phi ();
+ tree dst = gimple_phi_result (phi);
+
+ if (SSA_NAME_VAR (dst) != SSA_NAME_VAR (name)
+ && !virtual_operand_p (dst))
+ ++n_insns;
+ }
+ }
+
for (gsi = gsi_after_labels (bb);
!gsi_end_p (gsi);
gsi_next_nondebug (&gsi))
@@ -324,6 +355,11 @@ fsm_find_control_statement_thread_paths (tree name,
threaded_through_latch = true;
}
+ /* We are going to remove the control statement at the end of the
+ last block in the threading path. So don't count it against our
+ statement count. */
+ n_insns--;
+
gimple *stmt = get_gimple_control_stmt ((*path)[0]);
gcc_assert (stmt);
/* We have found a constant value for ARG. For GIMPLE_SWITCH
@@ -352,24 +388,6 @@ fsm_find_control_statement_thread_paths (tree name,
== DOMST_NONDOMINATING))
creates_irreducible_loop = true;
- /* PHIs in the final target and only the final target will need
- to be duplicated. So only count those against the number
- of statements. */
- gphi_iterator gsip;
- for (gsip = gsi_start_phis (taken_edge->dest);
- !gsi_end_p (gsip);
- gsi_next (&gsip))
- {
- gphi *phi = gsip.phi ();
- tree dst = gimple_phi_result (phi);
-
- /* We consider any non-virtual PHI as a statement since it
- count result in a constant assignment or copy
- operation. */
- if (!virtual_operand_p (dst))
- ++n_insns;
- }
-
if (path_crosses_loops)
{
if (dump_file && (dump_flags & TDF_DETAILS))
^ permalink raw reply [flat|nested] 4+ messages in thread* Re: [PATCH][PR tree-optimization/69196] Improve accounting in backwards (FSM) threader
2016-03-01 21:46 [PATCH][PR tree-optimization/69196] Improve accounting in backwards (FSM) threader Jeff Law
@ 2016-03-02 10:51 ` Richard Biener
2016-03-02 18:58 ` Jeff Law
0 siblings, 1 reply; 4+ messages in thread
From: Richard Biener @ 2016-03-02 10:51 UTC (permalink / raw)
To: Jeff Law; +Cc: gcc-patches
On Tue, Mar 1, 2016 at 10:46 PM, Jeff Law <law@redhat.com> wrote:
>
>
> Another step along the path to fixing 69196. As I was investigating the
> regression, one of the things that became quite clear was that we'd greatly
> increased the number of PHIs and many of the PHI arguments were constants
> (which in turn never coalesce and thus generate a constant initialization).
>
> I think this addresses the accounting issues relevant to 69196 in the
> backwards (FSM) threader. I don't expect this patch in and of itself to
> have any significant impact on the testcase -- it's just preparatory work
> for the clamp.
>
> Bootstrapped and regression tested on x86_64-linux-gnu. Installed on the
> trunk.
>
> Jeff
>
> commit 5810fc48902c737b3e0ea24bd2a709edbde41ff2
> Author: Jeff Law <law@redhat.com>
> Date: Tue Mar 1 14:41:35 2016 -0700
>
> PR tree-optimization/69196
> * tree-ssa-threadbackward.c
> (fsm_find_control_statement_thread_paths):
> Do count some PHIs in the thread path against the insn count.
> Decrease
> final statement count by one as the control statement in the last
> block will get removed. Remove special cased code for handling PHIs
> in the last block.
>
> PR tree-optimization/69196
> * gcc.dg/tree-ssa/vrp46.c: Twiddle threading params to keep it from
> duplicating code and spoiling the expected output.
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index b758d42..c1f2557 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,11 @@
> +2016-03-01 Jeff Law <law@redhat.com>
> +
> + PR tree-optimization/69196
> + * tree-ssa-threadbackward.c
> (fsm_find_control_statement_thread_paths):
> + Do count some PHIs in the thread path against the insn count.
> Decrease
> + final statement count by one as the control statement in the last
> + block will get removed. Remove special cased code for handling PHIs
> in the last block.
> +
> 2016-03-01 Uros Bizjak <ubizjak@gmail.com>
>
> PR target/70027
> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
> index 000ece8..ef8a987 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,3 +1,9 @@
> +2016-03-01 Jeff Law <law@redhat.com>
> +
> + PR tree-optimization/69196
> + * gcc.dg/tree-ssa/vrp46.c: Twiddle threading params to keep it from
> + duplicating code and spoiling the expected output.
> +
> 2016-03-01 Michael Meissner <meissner@linux.vnet.ibm.com>
>
> PR target/70033
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c
> b/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c
> index 8923eb4..d3c9ed1 100644
> --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c
> @@ -1,5 +1,5 @@
> /* { dg-do compile } */
> -/* { dg-options "-O2 -fdump-tree-vrp1" } */
> +/* { dg-options "-O2 -fdump-tree-vrp1 --param fsm-scale-path-blocks=1" } */
>
> int func_81 (int);
> int func_98 (int);
> diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
> index 55dbcad..3028504 100644
> --- a/gcc/tree-ssa-threadbackward.c
> +++ b/gcc/tree-ssa-threadbackward.c
> @@ -286,6 +286,37 @@ fsm_find_control_statement_thread_paths (tree name,
> break;
> }
>
> + /* PHIs in the path will create degenerate PHIS in the
> + copied path which will then get propagated away, so
> + looking at just the duplicate path the PHIs would
> + seem unimportant.
> +
> + But those PHIs, because they're assignments to objects
> + typically with lives that exist outside the thread
> path,
> + will tend to generate PHIs (or at least new PHI
> arguments)
> + at points where we leave the thread path and rejoin
> + the original blocks. So we do want to account for
> them.
> +
> + We ignore virtual PHIs. We also ignore cases where BB
> + has a single incoming edge. That's the most common
> + degenerate PHI we'll see here. Finally we ignore PHIs
> + that are associated with the value we're tracking as
> + that object likely dies. */
> + if (EDGE_COUNT (bb->succs) > 1 && EDGE_COUNT (bb->preds) >
> 1)
> + {
> + for (gphi_iterator gsip = gsi_start_phis (bb);
> + !gsi_end_p (gsip);
> + gsi_next (&gsip))
> + {
> + gphi *phi = gsip.phi ();
> + tree dst = gimple_phi_result (phi);
> +
> + if (SSA_NAME_VAR (dst) != SSA_NAME_VAR (name)
I think this doesn't quite work, to make it match the comment you'd have to add
a SSA_NAME_VAR (dst) != NULL_TREE check as otherwise all anonymous
SSA names count as "the same value we're tracking". Shouldn't you simply
compare the SSA names themselves but for the operand corresponding to
the edge we are threading instead of the PHI result?
Richard.
> + && !virtual_operand_p (dst))
> + ++n_insns;
> + }
> + }
> +
> for (gsi = gsi_after_labels (bb);
> !gsi_end_p (gsi);
> gsi_next_nondebug (&gsi))
> @@ -324,6 +355,11 @@ fsm_find_control_statement_thread_paths (tree name,
> threaded_through_latch = true;
> }
>
> + /* We are going to remove the control statement at the end of the
> + last block in the threading path. So don't count it against
> our
> + statement count. */
> + n_insns--;
> +
> gimple *stmt = get_gimple_control_stmt ((*path)[0]);
> gcc_assert (stmt);
> /* We have found a constant value for ARG. For GIMPLE_SWITCH
> @@ -352,24 +388,6 @@ fsm_find_control_statement_thread_paths (tree name,
> == DOMST_NONDOMINATING))
> creates_irreducible_loop = true;
>
> - /* PHIs in the final target and only the final target will need
> - to be duplicated. So only count those against the number
> - of statements. */
> - gphi_iterator gsip;
> - for (gsip = gsi_start_phis (taken_edge->dest);
> - !gsi_end_p (gsip);
> - gsi_next (&gsip))
> - {
> - gphi *phi = gsip.phi ();
> - tree dst = gimple_phi_result (phi);
> -
> - /* We consider any non-virtual PHI as a statement since it
> - count result in a constant assignment or copy
> - operation. */
> - if (!virtual_operand_p (dst))
> - ++n_insns;
> - }
> -
> if (path_crosses_loops)
> {
> if (dump_file && (dump_flags & TDF_DETAILS))
>
^ permalink raw reply [flat|nested] 4+ messages in thread* Re: [PATCH][PR tree-optimization/69196] Improve accounting in backwards (FSM) threader
2016-03-02 10:51 ` Richard Biener
@ 2016-03-02 18:58 ` Jeff Law
2016-03-02 21:11 ` Jeff Law
0 siblings, 1 reply; 4+ messages in thread
From: Jeff Law @ 2016-03-02 18:58 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
On 03/02/2016 03:51 AM, Richard Biener wrote:
> On Tue, Mar 1, 2016 at 10:46 PM, Jeff Law <law@redhat.com> wrote:
>>
>>
>> Another step along the path to fixing 69196. As I was investigating the
>> regression, one of the things that became quite clear was that we'd greatly
>> increased the number of PHIs and many of the PHI arguments were constants
>> (which in turn never coalesce and thus generate a constant initialization).
>>
>> I think this addresses the accounting issues relevant to 69196 in the
>> backwards (FSM) threader. I don't expect this patch in and of itself to
>> have any significant impact on the testcase -- it's just preparatory work
>> for the clamp.
>>
>> Bootstrapped and regression tested on x86_64-linux-gnu. Installed on the
>> trunk.
>>
>> Jeff
>>
>> commit 5810fc48902c737b3e0ea24bd2a709edbde41ff2
>> Author: Jeff Law <law@redhat.com>
>> Date: Tue Mar 1 14:41:35 2016 -0700
>>
>> PR tree-optimization/69196
>> * tree-ssa-threadbackward.c
>> (fsm_find_control_statement_thread_paths):
>> Do count some PHIs in the thread path against the insn count.
>> Decrease
>> final statement count by one as the control statement in the last
>> block will get removed. Remove special cased code for handling PHIs
>> in the last block.
>>
>> PR tree-optimization/69196
>> * gcc.dg/tree-ssa/vrp46.c: Twiddle threading params to keep it from
>> duplicating code and spoiling the expected output.
>>
>> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
>> index b758d42..c1f2557 100644
>> --- a/gcc/ChangeLog
>> +++ b/gcc/ChangeLog
>> @@ -1,3 +1,11 @@
>> +2016-03-01 Jeff Law <law@redhat.com>
>> +
>> + PR tree-optimization/69196
>> + * tree-ssa-threadbackward.c
>> (fsm_find_control_statement_thread_paths):
>> + Do count some PHIs in the thread path against the insn count.
>> Decrease
>> + final statement count by one as the control statement in the last
>> + block will get removed. Remove special cased code for handling PHIs
>> in the last block.
>> +
>> 2016-03-01 Uros Bizjak <ubizjak@gmail.com>
>>
>> PR target/70027
>> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
>> index 000ece8..ef8a987 100644
>> --- a/gcc/testsuite/ChangeLog
>> +++ b/gcc/testsuite/ChangeLog
>> @@ -1,3 +1,9 @@
>> +2016-03-01 Jeff Law <law@redhat.com>
>> +
>> + PR tree-optimization/69196
>> + * gcc.dg/tree-ssa/vrp46.c: Twiddle threading params to keep it from
>> + duplicating code and spoiling the expected output.
>> +
>> 2016-03-01 Michael Meissner <meissner@linux.vnet.ibm.com>
>>
>> PR target/70033
>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c
>> b/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c
>> index 8923eb4..d3c9ed1 100644
>> --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c
>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c
>> @@ -1,5 +1,5 @@
>> /* { dg-do compile } */
>> -/* { dg-options "-O2 -fdump-tree-vrp1" } */
>> +/* { dg-options "-O2 -fdump-tree-vrp1 --param fsm-scale-path-blocks=1" } */
>>
>> int func_81 (int);
>> int func_98 (int);
>> diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
>> index 55dbcad..3028504 100644
>> --- a/gcc/tree-ssa-threadbackward.c
>> +++ b/gcc/tree-ssa-threadbackward.c
>> @@ -286,6 +286,37 @@ fsm_find_control_statement_thread_paths (tree name,
>> break;
>> }
>>
>> + /* PHIs in the path will create degenerate PHIS in the
>> + copied path which will then get propagated away, so
>> + looking at just the duplicate path the PHIs would
>> + seem unimportant.
>> +
>> + But those PHIs, because they're assignments to objects
>> + typically with lives that exist outside the thread
>> path,
>> + will tend to generate PHIs (or at least new PHI
>> arguments)
>> + at points where we leave the thread path and rejoin
>> + the original blocks. So we do want to account for
>> them.
>> +
>> + We ignore virtual PHIs. We also ignore cases where BB
>> + has a single incoming edge. That's the most common
>> + degenerate PHI we'll see here. Finally we ignore PHIs
>> + that are associated with the value we're tracking as
>> + that object likely dies. */
>> + if (EDGE_COUNT (bb->succs) > 1 && EDGE_COUNT (bb->preds) >
>> 1)
>> + {
>> + for (gphi_iterator gsip = gsi_start_phis (bb);
>> + !gsi_end_p (gsip);
>> + gsi_next (&gsip))
>> + {
>> + gphi *phi = gsip.phi ();
>> + tree dst = gimple_phi_result (phi);
>> +
>> + if (SSA_NAME_VAR (dst) != SSA_NAME_VAR (name)
>
> I think this doesn't quite work, to make it match the comment you'd have to add
> a SSA_NAME_VAR (dst) != NULL_TREE check as otherwise all anonymous
> SSA names count as "the same value we're tracking". Shouldn't you simply
> compare the SSA names themselves but for the operand corresponding to
> the edge we are threading instead of the PHI result?
Without testing, yea, I think SSA_NAME_VAR != NULL_TREE ought to be
added to handle anonymous names.
Comparing just the SSA_NAMEs won't work as-is. We'd have to do
something like build a set of related names as we process PHI nodes in
the path.
I wouldn't be surprised if this gets revisited during the gcc-7 cycle;
what we're doing with PHI nodes and assignments in general is rather crude.
I can't help but think there's a more accurate test for when we're going
to end up creating a new PHI or PHI arg off the path. We also to be
able to better predict what statements are simply going to disappear
because their only purpose is to feed the conditional that's going to be
removed.
As I continue down the path of dis-entangling threading from VRP/DOM
we're almost certainly going to want to improve this stuff further.
jeff
^ permalink raw reply [flat|nested] 4+ messages in thread* Re: [PATCH][PR tree-optimization/69196] Improve accounting in backwards (FSM) threader
2016-03-02 18:58 ` Jeff Law
@ 2016-03-02 21:11 ` Jeff Law
0 siblings, 0 replies; 4+ messages in thread
From: Jeff Law @ 2016-03-02 21:11 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
On 03/02/2016 11:58 AM, Jeff Law wrote:
>> I think this doesn't quite work, to make it match the comment you'd
>> have to add
>> a SSA_NAME_VAR (dst) != NULL_TREE check as otherwise all anonymous
>> SSA names count as "the same value we're tracking". Shouldn't you simply
>> compare the SSA names themselves but for the operand corresponding to
>> the edge we are threading instead of the PHI result?
> Without testing, yea, I think SSA_NAME_VAR != NULL_TREE ought to be
> added to handle anonymous names.
So some raw data.
66% of the time both objects have an underlying SSA_NAME_VAR and we can
make an accurate guess if they're related or not by looking at the
underlying object.
17% of the time the name we're tracking has an SSA_NAME_VAR, but the
result of the PHI does not. Assuming the names are not related is
probably accurate here too.
3% of the time the name we're tracking is anonymous, but the result of
the PHI is not. Again, assuming names are not related is probably
accurate. Note the low value here is not unexpected.
Leaving the remaining 14% where both names are anonymous. Which is the
case we're getting wrong right now. I think the safe thing to do
without significant further investment is to consider the names
unrelated in this case, which I'm testing now. If we wanted to do
better here we could do things like building partitions similar to what
we do for coalescing. If the objects end up in the same partition, then
consider them related, but that seems like severe overkill here.
Jeff
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2016-03-02 21:11 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-03-01 21:46 [PATCH][PR tree-optimization/69196] Improve accounting in backwards (FSM) threader Jeff Law
2016-03-02 10:51 ` Richard Biener
2016-03-02 18:58 ` Jeff Law
2016-03-02 21:11 ` Jeff Law
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).