Hacker News Reader

Comment by userbinator | Hacker News Reader

at the expense of code size. For hardware with branch prediction, speculative execution, and prefetching, this can greatly improve performance

...up to the point when other code starts getting pushed out of the cache. This seems like an odd statement to make, since the transformation appears to be, like loop unrolling, of most benefit to processors which do not have features like branch prediction/OoO and thus very strongly prefer to execute "straight-line" code with as few branches as possible. Examples include early RISCs and the Pentium 4.

Also, the article describes something slightly different from both the GCC manual and the Wikipedia article - these describe an optimisation which rewrites chains of jumps into direct ones and does not involve duplicating code.

View on HN

Originally in libfirm it was called "partial conditional evaluation" and then was renamed [0] into "path-sensitive jump threading".

[0] http://pp.ipd.kit.edu/git/libfirm/commit/?id=d1c902c90f627d1...

If you convert branches into straight jumps, then branch prediction cannot be wrong anymore. Thus improvement.

Without branch prediction and speculative execution, a branch and a jump instruction should be equivalent, hence no improvement. However, it should still yield an improvement because there is no condition to evaluate anymore, hence less code.

>If you convert branches into straight jumps, then branch prediction cannot be wrong anymore. Thus improvement.

It's more like: No degradation. And there might be performance degradation by the additional memory use.

I don't understand what you mean with "no degradation".

A branch predictor can be wrong. A simple jump is like the branch predictor is always right. Thus, the code might run faster.

Yes. But a branch predictor can also be right every time. Or it could be right so often that it is better than the larger memory footprint of the program.

Jump threading can also enables additional optimizations. For instance, if you apply jump threading to

int eight(int a) { int b; if (a) { b = 1; } else { b = a; } b += 3; if (a) { return b + b; } else { return b + 5; } }

you duplicate the "b += 3;" but both branches can be optimized afterwards. In fact, the function always returns 8.

It sounds like it would have been more precise to say "for hardware that relies on branch prediction, speculative execution, and prefetching".

Reply on news.ycombinator.com