0

I was wondering if I have a branch

bool condition = x > y; // just an example
if(condition)
{
  // do the thing...
}
else
{
  // do the other thing...
}

It can be optimized to something like this because condition will be either 0 or 1, and rest of the code seems doable.

pseudo code:

1: condition = x > y    // just an example
2: jmp (!!condition)+3  // will either jump to line 3 or 4
3: jmp 5
4: jmp 20 // or any value known at compile time
5: // do the thing
.
.
20: // do the other thing
  1. Are branches optimized like this in common compilers?
  2. in what circumstances this is not possible? (if it's always possible, then why do we need branch prediction?)

Maybe my assumption is wrong and (!!condition) or x > y is already costing a branch?

M.kazem Akhgary
  • 18,645
  • 8
  • 57
  • 118
  • 1
    This has two taken branches on either path of execution, and a 3rd at the end of `do the thing` where you have to unconditionally jump over the code for `do the other thing`. One of them being an indirect branch, generally harder to predict than a conditional branch. Was that the misconception, that you thought indirect branches which could jump anywhere at run-time were cheaper than conditional branches that might jump to one place or fall through? – Peter Cordes Nov 19 '22 at 08:25
  • @PeterCordes Ah, so that's why. yeah I misunderstood. it was called "unconditional" and I thought it must be cheap :) now I realize my question was stupid – M.kazem Akhgary Nov 19 '22 at 08:28
  • 1
    It only sounds stupid when I phrase it in a way that makes the answer obvious :P You're not the first person to ask this, pretty sure there's a duplicate question about the same idea... – Peter Cordes Nov 19 '22 at 08:30
  • 1
    Of course if you were really going to use an indirect branch, you'd do a computed jump directly to either `5` or `20`, like `!!condition*15 + 5` (where `5` is really a code address, not a small integer). But a standard if/else is done with [one conditional branch and a direct unconditional branch](https://stackoverflow.com/questions/37370105/does-the-x86-64-pipeline-stall-on-an-indirect-jump-like-jmp-rax). (So one taken branch for each path, or 0 for one, 2 for the other if you favour one by putting one of the blocks out-of-line at the end of the function.) – Peter Cordes Nov 19 '22 at 08:33
  • 1
    Found the duplicate Q&A I was thinking of: [Why Can't the Compiler Create a Small Jump Table Instead of a Branch?](https://stackoverflow.com/q/70343535) - like this one, it's closed as a duplicate of questions about how indirect branch prediction works, but also had some worse silly mistakes. – Peter Cordes Nov 19 '22 at 08:41
  • Thanks for all the great information @PeterCordes much appreciated. – M.kazem Akhgary Nov 19 '22 at 08:50

0 Answers0