3 ms·

Anyone know why compilers don't already do this for small branches? Not worth the effort?

lysium 11y ago
I'd say probably too much effort? First, it does an exhaustive search on all possible instruction combinations. Second, it does not _prove_ that the resulting instructions do the same as the original code. It shows it only for some random numbers and border cases.
- TheLoneWolfling 11y ago
  It's fairly easy to extend this to either an exhaustive search afterwards, or to run into a SMT solver to prove that it's correct / incorrect. Though that's probably too much machinery to add on to a compiler.
Guvante 11y ago
There has been talk of using superoptimizers in larger compilers however it is usually not worth the effort unless you know a problem case in particular. Especially since these kinds of transformations could slow down your code if the branch predictor is working well for your code set.
adwf 11y ago
Halting problem perhaps? Even if you put in safeguards, an exhaustive search could still be unacceptably slow. You can never tell when a pathological case might arise.
rdc12 11y ago
Both GCC and Clang can compile to branchless solutions for some conditional statements. The FizzBuzz problem for example both GCC and Clang can turn that into a small lookup table
AReallyGoodName 11y ago
You miss out on branch prediction. There's a bit of a myth that branches are always bad because a branch misprediction is slower than a correctly predicted branch and therefore no branches are better. A bit of code that eliminates branches but has dependant variables (A must be computed before B can be computed) will have pipeline stalls while the computation for A is completed. Yes it might be faster than a branch misprediction but it will never be as fast as a correctly predicted branch (which takes effectively 0 cycles). Notice the one thing missing in this post? Benchmarks!
- duaneb 11y ago
  Among other things, there are branch prediction optimal algorithms that either a) only mispredict the final branch, or b) minimize amortized mispredictions.

I'd say probably too much effort? First, it does an exhaustive search on all possible instruction combinations. Second, it does not _prove_ that the resulting instructions do the same as the original code. It shows it only for some random numbers and border cases.

TheLoneWolfling 11y ago
It's fairly easy to extend this to either an exhaustive search afterwards, or to run into a SMT solver to prove that it's correct / incorrect. Though that's probably too much machinery to add on to a compiler.

Guvante 11y ago

There has been talk of using superoptimizers in larger compilers however it is usually not worth the effort unless you know a problem case in particular. Especially since these kinds of transformations could slow down your code if the branch predictor is working well for your code set.

adwf 11y ago

Halting problem perhaps? Even if you put in safeguards, an exhaustive search could still be unacceptably slow. You can never tell when a pathological case might arise.

rdc12 11y ago

Both GCC and Clang can compile to branchless solutions for some conditional statements. The FizzBuzz problem for example both GCC and Clang can turn that into a small lookup table

AReallyGoodName 11y ago

You miss out on branch prediction. There's a bit of a myth that branches are always bad because a branch misprediction is slower than a correctly predicted branch and therefore no branches are better. A bit of code that eliminates branches but has dependant variables (A must be computed before B can be computed) will have pipeline stalls while the computation for A is completed. Yes it might be faster than a branch misprediction but it will never be as fast as a correctly predicted branch (which takes effectively 0 cycles). Notice the one thing missing in this post? Benchmarks!

duaneb 11y ago
Among other things, there are branch prediction optimal algorithms that either a) only mispredict the final branch, or b) minimize amortized mispredictions.