[P2,PR,tree-optimization/68398] Refine when we allow the FSM threader to create irreducible inner loops

Right now we only allow the FSM threader to create an irreducible inner 
loop when it's able to eliminate a multiway branch.  The theory being 
that the multiway branch is very expensive and potentially outweighs the 
value of loop optimizations.

That was a fine start, but as seen in 68398, further refinement is 
desirable.

Essentially in the 68398 case, we want to thread through the latch to a 
point in the loop that does not dominate the latch -- thus creating an 
irreducible inner loop.  But in the 68398 case, we aren't eliminating a 
multiway branch, just a simple conditional branch.

I stared at the jump threading paths, cfg and overall code for a long 
time over the last few days pondering what characteristics are important 
here.  In the end it seems so simple.

If the path has a high number of blocks relative to the number of 
statements in the path, then the path (and subsequent irreducible loop) 
really isn't likely to be helped by loop optimizations to begin with -- 
essentially the jump thread path is just a series of conditional 
branches where we know the result of the last one -- and there's very 
little computation going on in the path.

So that's what I'm keying on -- the ratio of blocks to statements in the 
path.   The higher that ratio, the more inclined we are to allow 
creation of the irreducible inner loop.

FWIW, I did look at simply allowing irreducible loops after the loop 
optimizers were complete -- that doesn't resolve the issues here. We 
need it to happen early so that the rest of the optimization pipeline 
(including dom, vrp2, dom2) see the jump-threaded code and refine it 
further.

We may still want to make that kind of change, but I'd like to see code 
that benefits from such a change rather than blindly going forward with it.

Going back to that ratio of blocks to statements.  We were counting PHIs 
in the thread path against the statement count.  Except for the final 
block, those PHIs are going to be const/copy propagated away.  So the 
code to count the PHIs was moved out of the loop and just looks at PHIs 
in the final block in the path.

Second we want to be able to compare the number of statements and the 
number of blocks in a jump threading path.  In particular we'd like to 
look at ratios between the two.  So there's two controlling PARAMS to 
scale the raw numbers, which then makes it easier to build ratios.  So 
we can say that once the number of blocks exceeds the number of 
statements by 1.5X, then allow creation of the irreducible loop (that's 
done by scaling the blocks by 3 and statements by 2.

Testing.  For the testcase in 68398, this improves things by another 
percent or two in terms of raw instruction counts.  I get something like 
206k-207k instruction references.

For pr66752-3.c the heuristic fires and we handle all 3 jump threads 
during VRP1 and obviously we continue to collapse away all 3 tests of FLAG.

For vrp46.c, ssa-dom-thread-2{c,d}.c I added statements on the jump 
threading path so that the heuristic wouldn't fire to preserve the 
spirit of those tests.

ssa-dom-thread-2{h,g}.c new tests, copied from the original 
ssa-dom-thread-2{c,d} which show the heuristic firing.

ssa-dom-thread-7.c does more threading early as the heuristic fires 
there.  So its expected output was adjusted.

Bootstrapped and regression tested on x86_64 linux.  Installing on the 
trunk.

This also fixes 3 minor issues Bernd spotted in the last round of changes.

Jeff
commit a5b3ed5d29ceb18b9e257894661f328462f581c8
Author: law <law@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Wed Jan 27 19:19:47 2016 +0000

    	PR tree-optimization/68398
    	* params.def (PARAM_FSM_SCALE_PATH_STMTS): New parameter.
    	(PARAM_FSM_SCALE_PATH_BLOCKS): Likewise.
    	* tree-ssa-threadbackward.c (fsm_find_control_statement_thread_paths):
    	Only count PHIs in the last block in the path.  The others will
    	const/copy propagate away.  Add heuristic to allow more irreducible
    	subloops to be created when it is likely profitable to do so.

    	* tree-ssa-threadbackward.c (fsm_find_control_statement_thread_paths):
    	Fix typo in comment.  Use gsi_after_labels and remove the GIMPLE_LABEL
    	check from within the loop.  Use gsi_next_nondebug rather than gsi_next.

    	PR tree-optimization/68398
    	* gcc.dg/tree-ssa/pr66752-3.c: Update expected output.
    	* gcc.dg/tree-ssa/ssa-dom-thread-2c.c: Add extra statements on thread
    	path to avoid new heuristic allowing more irreducible regions
    	* gcc.dg/tree-ssa/ssa-dom-thread-2d.c: Likewise.
    	* gcc.dg/tree-ssa/vrp46.c: Likewise.
    	* gcc.dg/tree-ssa/ssa-dom-thread-7.c: Update expected output.
    	* gcc.dg/tree-ssa/ssa-dom-thread-2g.c: New test.
    	* gcc.dg/tree-ssa/ssa-dom-thread-2h.c: Likewise.

    git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@232897 138bc75d-0d04-0410-961f-82ee72b054a4

[P2,PR,tree-optimization/68398] Refine when we allow the FSM threader to create irreducible inner loops

Commit Message

Comments

Patch