Alternatives to short unconditional jumps on x86
corsix.org
corsix.org
So "modern" (1980s+) CPUs add a branch predictor[1] to the fetch stage. The job of the branch predictor is to determine two things:
(1) Is this instruction a branch? [2]
(2) If it's a branch, is it taken or not?
For the case of unconditional jumps, we can just focus on (1). Therefore, given that the branch predictor is never 100% accurate, even an unconditional branch can result in garbage instructions fetched into the CPU pipeline. So replacing some key unconditional jumps might in fact improve performance.
[1]: Actually, I was lying. There is also the BTB, collapsing buffer, and trace cache.
[2]: The fetch stage doesn't know what an instruction is; that's the job of the decode stage.
My main concern about trace cache/micro-ops buffer is how it would act when it encounter an instruction boundary change? Would it get flushed? Decoding can be bottleneck for some workload (e.g. SIMD Integer).
But saying that branch mispredictions rarely matter seems a way too strong statement. In a lot of halfway performance critical software a large number of pipeline stalls are caused by wrongly predicted branches, and utilizing the pipeline efficiently is IMO becoming Mir, not less, important.
The first stage is instruction fetch - "get the instruction at this address from memory". The second stage is instruction decode - "figure out what the instruction is (opcode) and its arguments (operands)". The important thing to understand is that all stages execute simultaneously. For example, when the pipeline is fetching instruction #2, it is also decoding instruction #1.
So why not do branch prediction during decode so the CPU knows it's a branch? Well, it could, but then the prediction would only be available to the fetch stage in the next cycle!
Keep reading if you want an illustrative example.
So where does branch prediction come in? Let's take a simple example where your CPU doesn't have a branch predictor.
The instruction stream is A B C D, where B is a branch that is taken and jumps to instruction X.
I'll use this diagram to represent a 4-stage pipeline: [ | | | ]. The stages are: fetch, decode, execute, and write results. Just focus on the first two stages for this example.
Let's walk through it cycle-by-cycle:
* Cycle 1: [ A | | | ] -> A is fetched
* Cycle 2: [ B | A | | ] -> B is fetched, A is decoded
* Cycle 3: [ C | B | A | ] -> C is fetched, B is decoded, A is executed
* Cycle 4: [ D | C | B | A ] -> D is fetched, C is decoded, B is executed, A write its results
Cycle 4 is the moment when the CPU knows the result of B, i.e., taken or not taken. But there's a problem: we just ended up fetching two useless instructions! So the pipeline is flushed, and fetching starts from X.
* Cycle 5: [ X | | | B ] -> X is fetched, B writes its results
In other words, we effectively wasted two cycles. This is where branch prediction comes in. Branch prediction is added to the fetch stage in order to predict whether or not a branch is taken, and if it is taken, fetch the correct instructions.
Let's add a branch predictor and repeat our example. For simplicity, we will assume a 100% accurate branch predictor.
* Cycle 1: [ A | | | ] -> A is fetched
* Cycle 2: [ B | A | | ] -> B is fetched, A is decoded
Now B is in the fetch stage and is passed to the branch predictor. But we have yet to reach the decode stage, so the CPU has no idea if B is a branch!. First, the CPU decides if B is in fact a branch - BTB and trace cache are two options for implementing this - then it decides whether or not the branch will be taken.
* Cycle 3: [ X | B | A | ] -> X is fetched, B is decoded, A is executed
At this point, we have utilized our pipeline fully and have avoided wasting time on incorrect instructions.
It's when modifying instructions that the cache/pipeline will get flushed.
Would be interesting to see benchmarks though.
What is "instruction level polymorphism"? I have heard of instruction level parallelism but I am not familiar with polymorphism at the opcode/machine instruction level. Could you elaborate?
This can't be done on an architecture like, say, MIPS, where instructions are always the same length and always aligned. There's only one way to interpret any given sequence of bytes. But on an architecture like x86, a byte sequence can mean different things if you start reading it at different offsets.
For an interesting example of putting this to use, check out JIT spraying: https://en.wikipedia.org/wiki/JIT_spraying
The idea is that you get a JIT compiler to generate malicious native code for you by making it generate innocent code that can also be interpreted as malicious code if you can find a bug that causes the CPU to jump into the middle of one of the innocent instructions.
/Pedantic
Is there a risk of introducing a false dependency? I think the answer is no, because if the following code depends on a flag value or the exact contents of %rax then it's probably incorrect.
Maybe modern processors wouldn't like seeing the same instruction bytes decoding to two different micro-ops? That might trigger some horrible slow fallback path.
"For example, jmp $+1 encodes as EB 01 ?? where ?? is the one byte to be jumped over. If burning a register is an option, then mov al, imm8 (encoded as B0 ??) might be an alternative (that is, the byte being jumped over becomes the imm8 value)."
Having lots of little jumps in your code can slow things down (well, maybe, depending on CPU, etc., but stipulate that jumps are bad). So at the end of X, you have to have a jump over the length of Y. However, if Y is very short, like 1 or 4 bytes, you don't actually need to use a jump instruction. Instead, pretend the Y instruction is a constant, and load it into a register (and ignore it). The result is the CPU runs X, loads some ignored data into a register, then runs Z. No jumps.