RFA: Avoiding unprofitable speculation

[Jeff Law]

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


ifcvt.c is sometimes over-aggressive in speculating instructions from a
not-predicted path.

Given:

        if (test) goto E; // x not live
        x = big();
        goto L;
        E:
        x = b;
        goto M;


ifcvt wants to turn it into:

        x = b;
        if (test) goto M;
        x = big();
        goto L;

ie, we speculate x = b and remove a branch.

Similarly:

        if (test) goto over; // x not live
        x = a;
        goto label;
        over:

   becomes

        x = a;
        if (! test) goto label;


where again we speculate x = a and eliminate a branch.


ifcvt has tests to see if the code to speculate is cheap relative to the
cost of the branch we get to remove.  Unfortunately, that only takes
into account a static RTX cost.   We need to be looking at the branch
prediction too -- often the branch we're going to eliminate isn't going
to be executed at all!

Specifically, we should take the cost of the branch we want to eliminate
and scale that by how often we expect to reach that branch at runtime.
That allows us to compare the runtime cost of the speculative code vs
the runtime benefit of eliminating the branch.

Looking at branch & insn counts before/after that change is quite
interesting.   I've got gcc-4.6 built with/without the attached change.
 I then use that gcc-4.6 to compile a bunch of .i files under the
watchful eye of valgrind.

Using this data we can see the actual costs...  For every dynamic branch
eliminated, we had to execute an additional 300 instructions!
Again, remember these are dynamic counts, so we may have only speculated
one static instruction to eliminate one branch, but we hit that
speculated instruction far more often dynamically than the branch we
ultimately eliminated.



instructions w/o patch:1267286482371
instructions w   patch:1264140292731

branches w/o     patch: 231180206508
branches w       patch: 231190636813

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/

iQEcBAEBAgAGBQJOSt2sAAoJEBRtltQi2kC7UZUIAJ7fthVsCXxU3JOtIVbUSX5t
grCG73peQnBB7FhB58/jW1GJWc011mExLIJf74FDrNU+gMp3gn01L0zdjcaytmY6
sNjso7dLjW42a/wByzNlHNUy2KRMUqhobEhHYWgC0tMJFz8/ekCulI7h98pVISmT
np9G/1zRXn3uD7F3pKw7lLDS994nSUmjObPFIyFxTfVGhBTWZYY8JjKP7NsOCNli
Dr2BXFF4rahoSDUlcLHwPPBJPABLvxwvMo0dsmNkB3HEiajj7qVPGUYaGrTJ5M1g
Bvww+ozzJRT96qQ/smjVZutD2Cu/U74Ix6EX8Yj54Zp2HeX8tCJ3kXWPFI6cBpk=
=3BEA
-----END PGP SIGNATURE-----
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: Q
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20110816/db208be6/attachment.ksh>