[Patch] Improving jump-thread pass for PR 54742
Sebastian Pop
sebpop@gmail.com
Mon Nov 24 00:06:00 GMT 2014
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>
More information about the Gcc-patches
mailing list