[Patch] Improving jump-thread pass for PR 54742

[Sebastian Pop]

Jeff Law wrote:
> >PS: I have run some perf analysis with the patch:
> >- on a bootstrap of GCC I see 3209 FSM jump threads
> >- libpng and libjpeg contain FSM jump threads, the perf increase is in the 1%
> >   (measured on simulators and reduced data sets)
> >- coremark gets jump threaded (as expected)
> >- I'm setting up the llvm test-suite and I will report perf differences
> So that's *far* more jump threads than I would expect this to find
> in a bootstrap of GCC -- like 3 orders of magnitude more than I'd
> expect to find.

The second patch attached limits the search for FSM jump threads to loops.  With
that patch, we are now down to 470 jump threads in an x86_64-linux bootstrap
(and 424 jump threads on powerpc64-linux bootstrap.)

> I haven't dug deep, but the first level analysis is not encouraging.
> 
> Basically I used the trunk compiler with and without your patch to
> build gcc-4.7.3's cc1 (4.7.3 simply because that's what I last used
> this testing framework).  So that gives me two cc1s that I then use
> to compile a bunch of .i files under valgrind's (cachegrind)
> control.
> 
> valgrind --tool=cachegrind --cache-sim=no --branch-sim=yes ......
> 
> That gives me two hunks of data for each input file I test.
> Specifically I get the dynamic number of instructions and the
> dynamic number of branches executed.
> 
> For jump threading those values correspond directly to the effect
> we're looking for -- a reduction in dynamic conditional jumps and a
> reduction in dynamic instructions executed.  Typically the change in
> dynamic instructions executed is 2-3X the change in dynamic
> conditional jumps -- which makes sense as removing the conditional
> jump usually means we remove a comparison and possibly some setup
> code as well.
> 
> Consistently with your patch those values get worse.   Across the
> entire set of .i files I get
> 
> For the trunk:
> 
> instructions:1339016494968
> branches:     243568982489
> 
> With your patch:
> 
> instructions:1339739533291
> branches:     243806615986
> 
> 
> So that's 723038323 more instructions and 237633497 more branches
> after installing your patch.  While we're looking a just under .1%
> regression in dynamic branches, that's a terrible result for this
> work.

One of the reasons I think we see more branches is that in sese region copying we
do not use the knowledge of the value of the condition for the last branch in a
jump-thread path: we rely on other propagation passes to remove the branch.  The
last attached patch adds:

  /* Remove the last branch in the jump thread path.  */
  remove_ctrl_stmt_and_useless_edges (region_copy[n_region - 1], exit->dest);

Please let me know if the attached patches are producing better results on gcc.

I rebased the original patch on trunk and all patches bootstrapped together on
x86_64-linux and powerpc64-linux.

Thanks,
Sebastian
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-extend-jump-thread-for-finite-state-automata-PR-5474.patch
Type: text/x-diff
Size: 16089 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20141124/a4bbf33a/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0002-look-for-fsm-threads-only-in-loops.patch
Type: text/x-diff
Size: 3822 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20141124/a4bbf33a/attachment-0001.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0003-add-FSM-debug.patch
Type: text/x-diff
Size: 1065 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20141124/a4bbf33a/attachment-0002.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0004-make-copied-region-single-entry-and-remove-last-cond.patch
Type: text/x-diff
Size: 6779 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20141124/a4bbf33a/attachment-0003.bin>