optimizing predictable branches on x86

[Nick Piggin]

Hi list,

gcc-4.3 appears to make quite heavy use of cmov to eliminate
conditional branches on x86(-64) architecture, even for those
branches that are determined to be predictable.

The problem with this is that the data dependancy introduced
by the cmov can restrict execution, wheras a predicted branch
will not. The Intel manual says not to use cmov for
predictable branches.

I have a test case which I /believe/ demonstrates that a cond
jump is not a great deal slower in the case where there are
no data dependancy hazards hit, and can be quite a bit faster
in the case where there is a dependancy -- if the branch is
predictable. It also shows that if the branch is unpredictable
then cmov can be a good win (as expected).

Compiled with:
gcc-4.3 -O3 -falign-functions=64 -falign-loops=64 -falign-jumps=64
        -falign-labels=64 -march=core2/opteron

Opteron:
 no deps,   predictable -- C    code took   8.92ns per iteration
 no deps,   predictable -- cmov code took   9.09ns per iteration
 no deps,   predictable -- jmp  code took   9.60ns per iteration[1]
has deps,   predictable -- C    code took  20.04ns per iteration
has deps,   predictable -- cmov code took  18.09ns per iteration
has deps,   predictable -- jmp  code took  14.97ns per iteration[2]
 no deps, unpredictable -- C    code took   8.92ns per iteration
 no deps, unpredictable -- cmov code took   9.09ns per iteration
 no deps, unpredictable -- jmp  code took  15.19ns per iteration[3]
has deps, unpredictable -- C    code took  32.07ns per iteration
has deps, unpredictable -- cmov code took  33.15ns per iteration
has deps, unpredictable -- jmp  code took  69.04ns per iteration[4]

[1] jmp is slightly slower, can it be improved?
[2] nice improvement here
[3] mispredict penalty, cmov is a big win
[4] mispredict which includes load missing cache!

Core2:
 no deps,   predictable -- C    code took   4.24ns per iteration
 no deps,   predictable -- cmov code took   4.27ns per iteration
 no deps,   predictable -- jmp  code took   4.24ns per iteration
has deps,   predictable -- C    code took   6.04ns per iteration
has deps,   predictable -- cmov code took   6.59ns per iteration
has deps,   predictable -- jmp  code took   5.04ns per iteration
 no deps, unpredictable -- C    code took   4.24ns per iteration
 no deps, unpredictable -- cmov code took   4.25ns per iteration
 no deps, unpredictable -- jmp  code took   8.79ns per iteration
has deps, unpredictable -- C    code took  49.78ns per iteration
has deps, unpredictable -- cmov code took  50.28ns per iteration
has deps, unpredictable -- jmp  code took  75.67ns per iteration

Core2 follows a similar pattern, although it's not seeing any
slowdown in the "no deps, predictable, jmp" case like K8 does.

Any comments? (please cc me) Should gcc be using conditional jumps
more often eg. in the case of __builtin_expect())?

Thanks,
Nick
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cmov4.c
Type: text/x-csrc
Size: 4470 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc/attachments/20080226/feee1448/attachment.bin>