What "thing" enables Speculative Execution to actually work?

Question

I have been learning recently about the inner workings of a CPU, how machine code is executed and how data moves around between registers using the bus. Now I'm reading about Speculative Execution and I can't wrap my brain around what "thing" is actually deciding to process instructions in a different order (ahead of time). It seems like there must exist some type of intermediary component sitting between where the instructions are coming from (in memory) and the CPU that is performing the calculations. This "thing" obviously is reading ahead and deciding to feed commands that may not be needed, and I assume it also somehow knows which results to discard when necessary. What is this "thing" called that actually enables Speculative Execution to function at all? Is it inside the CPU, or outside, for example in the "chipset" (a whole 'nother thing I need to read about).

Answer 1

Speculative execution isn't really about any particular "thing" which is responsible for the speculating, but is a consequence of the core microarchitecture as a whole, with a few pieces of hardware which are necessary, but not sufficient on their own.

Some (but not all) of the other necessary conditions are:

• Superscalar microarchitecture
• Any (even trivial) branch prediction
• A way of deferring visible effects until after the branch is successfully resolved
• A way of discarding speculative instructions resulting from incorrect predictions

Note that these are not just "things" or "behaviors", but really a superposition of both - e.g. "a way of deferring" requires both registers and buffers to record deferred effects, and the behavior to actually store into that buffer and use it to defer those effects.

Let's walk through an example on a hypothetical (vaguely defined) microarchitecture. In some ways, it's inspired by Skylake (there's a great diagram here that you should take a look at), but in other ways I'll handwave away a lot of the components (e.g. the L1I cache/instruction queue/decoder/uOp fusion/microcoder are all bundled together as "decoding an instruction", even though the real Skylake has immense complexity to make decoding work as well as possible).

In a superscalar processor core, multiple instructions are in flight at the same time, even though the actual machine code gives them in a linear order. As long as an instruction's inputs don't depend on still-pending outputs, and there's a free execution unit capable of handling that type of instruction, it can execute freely. If an instruction depends on a not-yet-ready result, it will stall until the inbound dependency can be forwarded, which happens as soon as that result is ready.

In the pseudocode below:

  load [r1] -> r2;
  sub r2, r7 -> r2;

the load operation may take a while (e.g. due to an L1 cache miss, or because r1 is not ready). This means that the result of r2 is delayed. However, a superscalar processor will still decode the subtraction, and assign it to one of the execution ports capable of executing an integer subtraction.

At that point, the execution will stall, until the load is complete and the value of r2 is available. At that point, the load/store unit will transmit the value of r2 (e.g. via the Common Data Bus), and the integer unit assigned to our subtraction can snoop that value after which it can begin executing - that is, the decode, assignment to a functional unit, and fetch of r7 have already been done, and we were only waiting for r2.

In the case of speculative execution, this goes even further - an instruction to branch may depend on a condition which is not yet evaluated. For example, in the following assembly pseudocode, the branch instruction has a dependency on the immediately preceding instructions, and has immediately useful work following it:

  load [r1] -> r2;
  sub r2, r7 -> r2;
  branch-if-zero r2 -> some_label;
  add r4, #4 -> r5;
  store r1 -> [r5];
...
some_label:
  mov #0 -> r0;
  ret; 

Now consider the branch predictor (a piece of hardware, which can be as simple as a hardcoded static prediction¹, an intermediate design like a history buffer, or as complex as a neural branch predictor). Suppose that this predictor decides that the branch is likely not taken. This means that we expect the next instruction after the branch is add r4, #4 -> r5.

As the processor decodes this branch, the value of r2 is not ready yet (the load and sub are still in-flight, and the load could take a long time on a cache miss). Stalling the processor would waste precious time if the branch was indeed not taken, so the next instruction (the add) is issued and allowed to execute (either as part of a single pipeline, or by being mapped to a free execution unit in scoreboarding/Tomasulo Algorithm). The following instruction (the store) can also begin to execute, but cannot be committed yet. The effects of the two speculative instructions may be recorded in a processor-internal buffer, but the store cannot be allowed to hit main memory yet, and the store to r4 cannot overwrite the old value yet.

As soon as r2 is known, the branch outcome is known. If the branch was not taken, as predicted, then we saved some time by executing speculatively. The store (which we placed into the reorder buffer) can now be fully retired and the instructions' visible effects allowed to occur.

Let's suppose that the branch prediction was wrong. In that case, the store to r4 and the store to main memory must be discarded. The effects of the speculative instructions are never made visible², and the processor resumes operation along the desired path, having paid a time penalty for the misprediction since it spent time doing useless work until the branch result was known.

Here's an example considering real x86 assembly.

Supposing I have the following code (also available in this interactive demo) and use gcc 8.4³, -O3:

// use stride to avoid extracting REP MOVSB
void copy_with_stride(char* dst, char* src, long srcStride) {
    do {
        asm volatile("# LLVM-MCA-BEGIN");
        *dst = *src;
        src += srcStride;
        dst++;
    } while (*src);
    asm volatile("# LLVM-MCA-END");
}

I get the following assembly at -O3:

copy_with_stride(char*, char*, long):
.L2:
        movzx   eax, BYTE PTR [rsi]
        add     rsi, rdx
        add     rdi, 1
        mov     BYTE PTR [rdi-1], al
        cmp     BYTE PTR [rsi], 0
        jne     .L2
        ret

and I can pass it to llvm-mca to get the following timeline view showing four iterations of the loop (24 instructions) over 14 clock cycles. Each line is an instruction, and from left to right you can see it be Decoded, wait to start executing (=), execute*, finish Execution, maybe stall waiting for retirement (-), and then be Retired.

llvm-mca -timeline -iterations=4 -instruction-info=false -resource-pressure=true -dispatch-stats=true -mcpu=skylake

// snip 

Timeline view:
                    0123
Index     0123456789    

[0,0]     DeeeeeER  .  .   movzx    eax, byte ptr [rsi]
[0,1]     DeE----R  .  .   add  rsi, rdx
[0,2]     DeE----R  .  .   add  rdi, 1
[0,3]     D=====eER .  .   mov  byte ptr [rdi - 1], al
[0,4]     D=eeeeeeER.  .   cmp  byte ptr [rsi], 0
[0,5]     .D======eER  .   jne  .L2
[1,0]     .DeeeeeE--R  .   movzx    eax, byte ptr [rsi]
[1,1]     .DeE------R  .   add  rsi, rdx
[1,2]     .DeE------R  .   add  rdi, 1
[1,3]     .D=====eE-R  .   mov  byte ptr [rdi - 1], al
[1,4]     . DeeeeeeER  .   cmp  byte ptr [rsi], 0
[1,5]     . D======eER .   jne  .L2
[2,0]     . DeeeeeE--R .   movzx    eax, byte ptr [rsi]
[2,1]     . DeE------R .   add  rsi, rdx
[2,2]     . DeE------R .   add  rdi, 1
[2,3]     .  D====eE-R .   mov  byte ptr [rdi - 1], al
[2,4]     .  DeeeeeeER .   cmp  byte ptr [rsi], 0
[2,5]     .  D======eER.   jne  .L2
[3,0]     .  DeeeeeE--R.   movzx    eax, byte ptr [rsi]
[3,1]     .  DeE------R.   add  rsi, rdx
[3,2]     .   DeE-----R.   add  rdi, 1
[3,3]     .   D====eE-R.   mov  byte ptr [rdi - 1], al
[3,4]     .   DeeeeeeER.   cmp  byte ptr [rsi], 0
[3,5]     .   D======eER   jne  .L2

You can see how deeply speculative and superscalar our real-world CPU actually is; by the time we finish decoding the fourth iteration of our loop, we haven't even retired the first iteration, even if every memory access got a cache hit and finished quickly! This means that we could very well have three or four iterations of our function executing speculatively, with their retirement (and hence visible effects) deferred until the branches ahead of them are resolved.

¹ An example of hardcoded prediction is to assume that branches backwards are taken (since they're likely to be loops that execute a bunch of times), while branches forward are not taken (they may be error handlers or early returns).

² Sometimes, the results are made subtly visible. For example, a mispredicted speculative load might lead to effects in the CPU cache even though the result isn't permitted to update the actual CPU register being speculatively loaded to. Although the program state is still unchanged, the speculative load can still be detected through subtle differences in timing between cache hits and misses or other subtle observations, forming the basis for microarchitectural data sampling attacks like Spectre and Meltdown.

³ Newer versions of GCC and Clang generate separate specializations for stride == 1 (with inc) and stride != 1 (with add), since the stride == 1 case can get slightly better throughput when considered over a long loop. This makes the assembly and llvm-mca output a bit messy, so I use an older version to ensure that a single loop is created instead.