Jump Threading
beza1e1.tuxen.de
beza1e1.tuxen.de
Why?
Iterative dataflow problems, in particular, capturing second order effects, etc, are very well known things and often do not require solving the halting problem or anything like it.
Just propagating analysis facts around (IE "i can thread this jump"). In fact, i'm fairly confident standard jump threading (which this isn't quite) can be split into an analysis and optimization path.
This is because you already know what the CFG will look like if you perform a particular jump threading.
This is similar to PRE and other situations where you know what the end result of a given expression being PRE'd will be, and thus, you can figure out whether what the full end state of the transform will be, regardless of whether you do it.
In fact, if you couldn't do this, you couldn't do LCM as two unidirectional dataflow problems.
Jump threading seems much the same. Completely decomposable, regardless of whether you perform a given path of optimizations or not.
The only question is the expense of doing so.
Since it's an optimization, and not required for correct operation of the compiler, one can simply give up instead of risking an infinite loop.
https://en.wikipedia.org/wiki/Jump_threading
is a better description of jump threading.
In what the author describes as jump threading, you have the same problem as loop peeling or any other loop optimization that may get applied to an infinite loop and want to duplicate per-iteration code from that loop.
Yet somehow, as you'll see, we can prove things about the end states of those optimizations. ;-)
...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.
[0] http://pp.ipd.kit.edu/git/libfirm/commit/?id=d1c902c90f627d1...
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.
It's more like: No degradation. And there might be performance degradation by the additional memory use.
A branch predictor can be wrong. A simple jump is like the branch predictor is always right. Thus, the code might run faster.
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.
To really know whether or not this is a win, you need to test this in the context of the whole thing. Microbenchmarks often give a wrong idea. They're not usually run under stress of certain CPU resources such as L1C, L1D, TLB, etc. But in real code the situation is different. Other code also needs those cache entries and may very well perform worse because of a local optimization elsewhere bottlenecking execution by taking up resources.