[ppc] Highly predictable ISEL should be changed to cmp/br

[weiguozhi]

Bugzilla Link	32971
Version	trunk
OS	Linux
CC	@echristo,@hfinkel

Extended Description

On power, use ISEL or cmp/br is a general hard problem. But if we can point out the branch is highly predictable (either through runtime profiling or static estimate), we should use cmp/br.

Following is a test case simplified from real world code.

include

typedef std::vector MyVec; int foo(int iters, MyVec* vec) { MyVec::const_iterator it = vec->begin();

for (int i = 0; i < iters; ++i, ++it) { if (it == vec->end()) { it = vec->begin(); }
if (*it >= iters) return 1; } return 0; }

The iterator "it" is incremented in each iteration, and it is compared to the same value vec->end(), so we can expect the condition is false for most times, and then it is true, and then false again ... So this branch is highly predictable. In our code, cmp/br is 2x faster than isel.

LLVM generates following code, which uses ISEL

BB#0: # %entry

    cmpwi    3, 1
    blt      0, .LBB0_4

BB#1: # %for.body.lr.ph

    addi 6, 3, -1
    ld 5, 0(4)
    ld 4, 8(4)
    clrldi   6, 6, 32
    addi 6, 6, 1
    mr 7, 5
    mtctr 6
    li 6, 0
    .p2align        5

.LBB0_2: # %for.body

=>This Inner Loop Header: Depth=1

    cmpld    4, 7
    isel 7, 5, 7, 2
    lwz 8, 0(7)
    cmpw     8, 3
    bge 0, .LBB0_5

BB#3: # %for.inc

                                    #   in Loop: Header=BB0_2 Depth=1
    addi 6, 6, 1
    addi 7, 7, 4
    bdnz .LBB0_2

.LBB0_4: li 3, 0 clrldi 3, 3, 32 blr .LBB0_5: li 3, 1 clrldi 3, 3, 32 blr

[llvmbot]

We're doing some experiments to see how this example behaves on P9.

[hfinkel]

The iterator "it" is incremented in each iteration, and it is compared to the same value vec->end(), so we can expect the condition is false for most times, and then it is true, and then false again ... So this branch is highly predictable.

This is a good point. We should be able to come up with a reasonable set of 'predictibility' heuristics (just like we have for branch probabilities).