Is it possible to "skip" the branch predictor when you know the path ahead of time?

user_12936536 0
Viewed 122

Lets say my code is the following. It's a silly nonsense example but the point is there's at least 2 cycles of work before getting to the branch. Maybe more since the multiply depends on previous values.

Is there any chance of this taking the correct path 100% of the time? Is the instruction a different opcode when you know the path ahead of time? Is there instructions I need to use related to prefetching if I want to tell it which path it will be taking?

int test(int v, int*p) {
    for(;;)
    {
        if (v<100)
        {
            auto nextPath = v>50;
            sum+=p[0]
            sum*=p[1]
            memberVar++
            len+=10;
            sum-=p[3]
            sum*=p[4]
            memberVar++
            len+=5
            if (nextPath)
                break;
            else
                v=p[5]
        }
    }
}
branch-prediction x86-64 micro-optimization assembly optimization
1 Answers

Pentium-4 has branch hints (using segment prefixes), but they tended not to be useful in practice so later CPUs silently ignore them. (Intel x86 0x2E/0x3E Prefix Branch Prediction actually used?) This was x86's only experiment with hardware branch hints. (Some other ISAs have also had them and may still support them).

See also Is it possible to tell the branch predictor how likely it is to follow the branch?, including my answer on that question. You can hint the compiler how to lay out if bodies, e.g. so the common case is fall-through instead of taken, which does help. That's what __builtin_expect is for, or the C++20 [[likely]] and [[unlikely]] attribute.

But those compiler hints do not interact with CPU hardware branch prediction. (Except in the sense that they may convince the compiler to use branchy code instead of branchless, so there is a branch that needs predicting at all, instead of a cmov or something for cases where branchless was possible.)

If you have a special iteration with known branching, you can peel it and optimize it specially before entering the actual loop.

Or if your branch is always taken for the first part of a loop, then always not-taken, you can split your loop into two halves: one with the always-true case the other optimized for the always-false case.

Or if the branch direction is totally loop-invariant, then only one of the loop versions ever needs to run. That's kind of a loop-versioning optimization. Optimizing a branch inside a loop into 2 separate loops costs code-size, but can be a win if it runs frequently, especially if you can optimize the now-unconditional code into the surrounding code.

Your case appears to be totally loop-invariant after the first iteration, so peel that first iteration to use the initial v (from the function arg), then later iterations can infinite-loop or do a single iteration. Not really much to gain here; hoisting the p[5] load and using a compare-and-branch on it at the bottom of the loop would appear to do the trick.

Your p isn't modified in the loop, and p[5] is read-only. So after the first iteration, v = p[5] is loop-invariant. (Assuming this is C-like pseudocode (without ;) and thus data-race undefined behaviour can be assumed not to happen, i.e. no async modifications to p.)

len, sum, and memberVar aren't declared, but unless one is a C++ reference to the same int as p[5] there's no possible aliasing.

user_2241320
Related