Re: RFA: Avoiding unprofitable speculation

[Richard Guenther <richard.guenther@gmail.com>]

On Tue, Aug 16, 2011 at 11:14 PM, Jeff Law <law@redhat.com> wrote:
> -----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?

We don't have a way to distinguish branch-taken vs. branch-not-take
costs, right?
I would expect that for non-pipelined archs the branch does have the same cost
all the time, so ifcvt would be correct, no? Do you happen to know how valgrind
counts branches here?

The patch itself looks sensible, though I am surprised ifcvt doesn't run in
cfglayout mode (so you have to use reg notes to find probabilities ...)

Thanks,
Richard.

>
>
> -----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-----
>