RFA: Improve tree-ssa-sink block selection

[Jeff Law <law at redhat dot com>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


tree-ssa-sink.c could benefit from a little TLC in its code to select
statement's final location.

For those not familiar with tree-ssa-sink, it attempts to sink
statements down in the CFG to points where they're less likely to
execute.  Ideally we move into lower loop nests and more control
dependent paths.

tree-ssa-sink has some code to avoid sinking in certain cases.  For
example, if the selected block is at a deeper loop nest or if the
selected block post-dominates the statement's original block.  These
are (of course) good things, but both could use some improvement.

First, the selected block might be at a deeper loop nest, but we can
safely move up the dominator tree from the selected block to the
statement's original block looking for a better location.   This
allows more sinking.  We should think of the selected block as the
latest valid block -- we're then free to select any block between the
statement's original block and the latest valid block on the dominator
tree.

Second, while we avoid sinking to a post-dominator of the statement's
original block, the more general heuristic should be to avoid sinking
if the target block does not have a frequency significantly smaller
than the statement's original block.  ie, sinking past conditionals
which will never trigger (checking abort paths for example) is not
profitable.  Furthermore, it appears that gratutious sinking tends to
actually generate worse code.  A new PARAM is introduced to control
the aggressiveness of sinking.

I've done a fair number of experiments with valgrind and the sweet
spot for sinking non-memory referencing statements seems to be the new
block having a frequency less than 75% of the original block's
frequency. Statements which hit memory should be moved somewhat more
aggressively, so they're adjusted slightly.

According to valgrind this patch reduces the amount of instructions
executed by just over 1.15%.  Not huge, but nothing to sneeze out
given we're just changing the target block selector.

Bootstrapped and regression tested on x86_64-unknown-linux-gnu.  OK
for trunk?







-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOnQpFAAoJEBRtltQi2kC72GAIAKIHiG/QmV9cc2k6tyMQXXB9
o3ell9hAQJXD5fXm5VfzBK+NbkrYusMb1SsOe5CPpdL9LCnUt2obhCaOlZpH3GWC
TdrAkv96m24Y23oVnn7c2cWWjHflTBOCfNzYddG1W2GWwZx7t1Jz1uM4HJd334F4
aijyksbYxEWUs3vCmaeJ1/7oHS71QrgpUqPKrcw4oV97CtszgPiZfgdV24fzuGsb
WsPUGXH93pqJm04E6EQ1jI5dr2nfpazhuSkEhOR+9gZiNYR9Dt4sFpjwgX1o0NVH
UbS4p43RpPQHEGoBxEYnvLVnhVa1n6ywdnNvGAXHcGyDGMOuo6E5GGvFm9Kj7QI=
=9a+g
-----END PGP SIGNATURE-----

Attachment: patch
Description: Text document