7

I'm not asking about things like __builtin_expect. I'm thinking of the case where I don't know that a branch will be usually true or usually false, but I do know that it's predictable (or not).

I would expect the compiler, knowing a branch is predictable, to be more likely to generate branches, and knowing it's unpredictable, to be more likely to generate conditionally-executed instructions with no branches.

Is this possible in major compilers? (Thinking specifically of gcc and clang).

Examples explaining why "predictable" and "likely" are not the same thing

int x = rand()%2;
while (true) {
    if (x) {
        // do something
    }
}

The if statement is neither likely or unlikely, but highly predictable.

while (true) {
    if (rand()%5 > 0) {
        // do something
    }
}

In this case, the opposite is true: the branch is highly likely (taken 80% of the time), but unpredictable.

Brennan Vincent
  • 10,736
  • 9
  • 32
  • 54
  • 1
    This [Q&A](https://stackoverflow.com/questions/7346929/what-is-the-advantage-of-gccs-builtin-expect-in-if-else-statements) suggests `__builtin_expect` is exactly the tool used for this job, with `0` or `1` for arbitrary conditionals. The linux kernel even uses it to define its `likely` and `unlikely` macros – StoryTeller - Unslander Monica Apr 24 '19 at 07:03
  • 5
    clang has `__builtin_unpredictable` : https://clang.llvm.org/docs/LanguageExtensions.html#builtin-unpredictable – m.s. Apr 24 '19 at 07:05
  • 1
    @StoryTeller I'm sorry, but I don't think you understood the question. (Either that, or I don't understand your comment) – Brennan Vincent Apr 24 '19 at 07:05
  • @m.s. thank you! This is exactly what I was looking for. – Brennan Vincent Apr 24 '19 at 07:06
  • In that case, maybe you are due for some inspection and revision of the question for clarity. – StoryTeller - Unslander Monica Apr 24 '19 at 07:06
  • @StoryTeller I thought it was clear in the question that we don't know whether the branch is likely or not. It could be taken exactly 50% of the time. So, what value would I pass to `__builtin_expect` ? – Brennan Vincent Apr 24 '19 at 07:07
  • *"but I do know that it's predictable (or not)"* - So which is it? – StoryTeller - Unslander Monica Apr 24 '19 at 07:08
  • You seem to be confusing "predictable" with likely. There are six separate cases: "Predictable, not likely", "Predictable, likeliness indeterminate", "Predictable, likely", "Unpredictable, unlikely", "Unpredictable, likeliness indeterminate", "Unpredictable, likely" – Brennan Vincent Apr 24 '19 at 07:09
  • To elaborate on this: an example of predictable but of indeterminate likeliness would be generating a random bool (true or false) and then using the same bool in a condition 1000 times in a row. There is a 50% probability a priori of taking or not taking the branch, but it will be the same 1000 times in a row, so perfectly predictable by hardware branch prediction facilities. – Brennan Vincent Apr 24 '19 at 07:12
  • Great! But it belongs in the question, not buried in comments. – StoryTeller - Unslander Monica Apr 24 '19 at 07:15
  • I have added some examples, hopefully it is more comprehensible now. – Brennan Vincent Apr 24 '19 at 07:23
  • To be fair, in the first example here the variable (assuming it isn't changed) will likely be hoisted out of the loop by the optimizer. That's just data flow analysis, and has little to do with "predictability". – You Apr 24 '19 at 12:01

1 Answers1

8

Converting my comment into an answer:

clang has __builtin_unpredictable:

__builtin_unpredictable is used to indicate that a branch condition is unpredictable by hardware mechanisms such as branch prediction logic.

Example of use:

if (__builtin_unpredictable(x > 0)) {
    foo();
}

https://clang.llvm.org/docs/LanguageExtensions.html#builtin-unpredictable

m.s.
  • 16,063
  • 7
  • 53
  • 88