Improve DOM's optimization of control statements

Until now DOM has had to be very conservative with handling control 
statements with known conditions.  This as been an unfortunate side 
effect of the interaction between removing edges and recycling names via 
the SSA_NAME manager.

Essentially DOM would have to leave control statements alone.  So you'd 
see stuff like

if (0 == 0)

left around by DOM.  The jump threader would thankfully come along and 
optimize that as a jump thread.  But that's terribly inefficient, not to 
mention it creates unnecessary churn in the CFG and SSA_NAMEs.

By optimizing that directly in DOM, including removing whatever edges 
are not executable, we no longer have to rely on jump threading to 
handle that case.  Less churn in the CFG & SSA_NAMEs.   There's also 
some chance for secondary optimizations with fewer edges left in the CFG 
for DOM to consider.

Unfortunately, the churn caused by jump threading made it excessively 
difficult to analyze before/after dumps.  Sadly, you can have the same 
code, but if the SSA_NAMEs have changed, that impacts coalescing as we 
leave SSA.  Churn in the CFG changes labels/jumps, often without 
changing the actual structure, etc.

I did some tests with valgrind to evaluate branching behaviour 
before/after effects on the resulting code and those effects were tiny, 
in the I doubt you could measure them range.  That was expected since 
what we're really doing here is just capturing the optimization earlier.

I had a couple more tests, but they were lost in a bit of idiocy.  The 
test included is the one I had a second copy of lying around.

Bootstrapped and regression tested on x86_64-linux-gnu.  Installed on 
the trunk.

Jeff
* tree-ssa-dom.c (optimize_stmt): Collapse control flow statements
	with constant conditions.
	* tree-ssa-threadupdate.c (remove_jump_threads_starting_at): New.
	(remove_ctrl_stmt_and_useless_edges): No longer static.
	* tree-ssa-threadupdate.h (remove_jump_threads_starting_at): Prototype.
	(remove_ctrl_stmt_and_useless_edges): Likewise.

	* gcc.dg/tree-ssa/ssa-dom-branch-1.c: New test.

Hi Jeff,

Your patch causes an ICE regression.
The test case is " gcc.c-torture/compile/pr27087.c", I observed it on 
aarch64-none-elf target when compiling the test case with '-Os' flag.

A quick check shows, the cfg has been changed, but the loop information 
is not updated. Thus the information about the number of basic block in 
a loop is not reliable.

Could you please have a look?

Regards,
Renlin

On 30/09/15 21:28, Jeff Law wrote:
> Until now DOM has had to be very conservative with handling control
> statements with known conditions.  This as been an unfortunate side
> effect of the interaction between removing edges and recycling names via
> the SSA_NAME manager.
>
> Essentially DOM would have to leave control statements alone.  So you'd
> see stuff like
>
> if (0 == 0)
>
> left around by DOM.  The jump threader would thankfully come along and
> optimize that as a jump thread.  But that's terribly inefficient, not to
> mention it creates unnecessary churn in the CFG and SSA_NAMEs.
>
> By optimizing that directly in DOM, including removing whatever edges
> are not executable, we no longer have to rely on jump threading to
> handle that case.  Less churn in the CFG & SSA_NAMEs.   There's also
> some chance for secondary optimizations with fewer edges left in the CFG
> for DOM to consider.
>
> Unfortunately, the churn caused by jump threading made it excessively
> difficult to analyze before/after dumps.  Sadly, you can have the same
> code, but if the SSA_NAMEs have changed, that impacts coalescing as we
> leave SSA.  Churn in the CFG changes labels/jumps, often without
> changing the actual structure, etc.
>
> I did some tests with valgrind to evaluate branching behaviour
> before/after effects on the resulting code and those effects were tiny,
> in the I doubt you could measure them range.  That was expected since
> what we're really doing here is just capturing the optimization earlier.
>
> I had a couple more tests, but they were lost in a bit of idiocy.  The
> test included is the one I had a second copy of lying around.
>
> Bootstrapped and regression tested on x86_64-linux-gnu.  Installed on
> the trunk.
>
> Jeff

On 10/02/2015 05:15 AM, Renlin Li wrote:
> Hi Jeff,
>
> Your patch causes an ICE regression.
> The test case is " gcc.c-torture/compile/pr27087.c", I observed it on
> aarch64-none-elf target when compiling the test case with '-Os' flag.
>
> A quick check shows, the cfg has been changed, but the loop information
> is not updated. Thus the information about the number of basic block in
> a loop is not reliable.
>
> Could you please have a look?
Yup.  Will do.   Thanks for letting me know.

jeff

On 10/02/2015 05:15 AM, Renlin Li wrote:
> Hi Jeff,
>
> Your patch causes an ICE regression.
> The test case is " gcc.c-torture/compile/pr27087.c", I observed it on
> aarch64-none-elf target when compiling the test case with '-Os' flag.
>
> A quick check shows, the cfg has been changed, but the loop information
> is not updated. Thus the information about the number of basic block in
> a loop is not reliable.
>
> Could you please have a look?
Appears to be pretty simple.  If we collapse a conditional inside a 
loop, then we need to set the loop state as needing fixups.

In this specific case we have a conditional where one path eventually 
leads back to the loop latch block, the other path exits the loop.  We 
statically determine the conditional will always take us to the loop exit.

That has the side effect of making the block with the collapsed 
conditional no longer part of the loop, it's actually part of the exit 
path.  That changes the number of nodes in the loop, what edge(s) are 
the exit path(s) and possibly other stuff.

I'm running a fix through testing now.

Thanks,
jeff

On powerpc:

FAIL: gcc.c-torture/compile/pr52073.c   -O2  (internal compiler error)

/daten/gcc/gcc-20151006/gcc/testsuite/gcc.c-torture/compile/pr52073.c:6:1: internal compiler error: in duplicate_thread_path, at tree-ssa-threadupdate.c:2446.
0x10874ab7 duplicate_thread_path.
	../../gcc/tree-ssa-threadupdate.c:2445.
0x10874ab7 thread_through_all_blocks(bool).
	../../gcc/tree-ssa-threadupdate.c:2632.
0x107b0ea7 execute.
	../../gcc/tree-ssa-dom.c:622.

Andreas.

On 10/07/2015 04:03 PM, Andreas Schwab wrote:
> On powerpc:
>
> FAIL: gcc.c-torture/compile/pr52073.c   -O2  (internal compiler error)
>
> /daten/gcc/gcc-20151006/gcc/testsuite/gcc.c-torture/compile/pr52073.c:6:1: internal compiler error: in duplicate_thread_path, at tree-ssa-threadupdate.c:2446.
> 0x10874ab7 duplicate_thread_path.
> 	../../gcc/tree-ssa-threadupdate.c:2445.
> 0x10874ab7 thread_through_all_blocks(bool).
> 	../../gcc/tree-ssa-threadupdate.c:2632.
> 0x107b0ea7 execute.
> 	../../gcc/tree-ssa-dom.c:622.
Update your tree.  This should have been fixed by:
2015-10-06  Jeff Law  <law@redhat.com>

         PR tree-optimization/67816

Jeff