Re: [Bug tree-optimization/15524] [4.0 Regression] jump threadingon trees is slow with switch statements with large # of cases

[Jeffrey A Law <law at redhat dot com>]

Ho hum.  Another 12% improvement. 

There's two closely related changes in this patch.

First, we can drastically speed up find_edge for code with large
switch statements.  Right now we call find_edge with a src/dst
edge pair.  find_edge walks src->succs to find a successor
with a matching destination block.

That is usually a pretty efficient scheme as most blocks have one
or two successors and thus the search terminates quickly.

However, when handling large switch statements that scheme can 
perform poorly.  Instead it is sometimes better to walk dst->preds
searching for the right src/dst pair.

Previously we had no good way to determine which list to search
through.  However, with the recent work on our pred/succ list
representations we can trivially check which of the two
important lists is shorter.  We (of course) search the shorter list :-)

redirect_edge_succ_nodup actually implements find_edge inline and thus
it does not perform well on blocks with lots of successors.  Clearly
this code can (and does) benefit from calling the significantly 
improved find_edge.

Key timevars before the change:




 cfg cleanup           :   2.80 ( 3%) usr   0.00 ( 0%) sys   2.78 ( 3%)
 tree CFG cleanup      :  34.23 (36%) usr   0.00 ( 0%) sys  34.26 (35%)
 dominator optimization:   5.11 ( 5%) usr   0.02 ( 2%) sys   5.13 ( 5%)
 tree split crit edges :  17.36 (18%) usr   0.00 ( 0%) sys  17.36 (18%)
 TOTAL                 :  96.21             0.82            97.53


Key timevars after the change:

 cfg cleanup           :   0.62 ( 1%) usr   0.00 ( 0%) sys   0.62 ( 1%)
 tree CFG cleanup      :  28.27 (33%) usr   0.00 ( 0%) sys  28.33 (32%)
 dominator optimization:   3.77 ( 4%) usr   0.01 ( 1%) sys   3.80 ( 4%)
 tree split crit edges :  15.58 (18%) usr   0.00 ( 0%) sys  15.57 (18%)
 TOTAL                 :  84.81             0.81            87.92

Bootstrapped and regression tested on i686-pc-linux-gnu.

Attachment: PPP
Description: Text document