What branch misprediction does the Branch Target Buffer detect?

by

This is a good question! I think the confusion that it’s causing is due to Intel’s strange naming schemes which often overload terms standard in academia. I will try to both answer your question and also clear up the confusion I see in the comments.

First of all. I agree that in standard computer science terminology a branch target buffer isn’t synonymous with branch predictor. However in Intel terminology the Branch Target Buffer (BTB) [in capitals] is something specific and contains both a predictor and a Branch Target Buffer Cache (BTBC) which is just a table of branch instructions and their targets on a taken outcome. This BTBC is what most people understand as a branch target buffer [lower case]. So what is the Branch Address Calculator (BAC) and why do we need it if we have a BTB?

So, you understand that modern processors are split into pipelines with multiple stages. Whether this is a simple pipelined processor or an out of order supersclar processor, the first stages are typically fetch then decode. In the fetch stage all we have is the address of the current instruction contained in the program counter (PC). We use the PC to load bytes from memory and send them to the decode stage. In most cases we increment the PC in order to load the subsequent instruction(s) but in other cases we process a control flow instruction which can modify the contents of the PC completely.

The purpose of the BTB is to guess if the address in the PC points to a branch instruction, and if so, what should the next address in the PC be? That’s fine, we can use a predictor for conditional branches and the BTBC for the next address. If the prediction was right, that’s great! If the prediction was wrong, what then? If the BTB is the only unit we have then we would have to wait until the branch reaches the issue/execute stage of the pipeline. We would have to flush the pipeline and start again. But not every situation needs to be resolved so late. This is where the Branch Address Calculator (BAC) comes in.

The BTB is used in the fetch stage of the pipeline but the BAC resides in the decode stage. Once the instruction we fetched is decoded, we actually have a lot more information which can be useful. The first new piece of information we know is: “is the instruction I fetched actually a branch?” In the fetch stage we have no idea and the BTB can only guess, but in the decode stage we know it for sure. It is possible that the BTB predicts a branch when in fact the instruction is not a branch; in this case the BAC will halt the fetch unit, fix the BTB, and reinitiate fetching correctly.

What about branches like unconditional relative and call? These can be validated at the decode stage. The BAC will check the BTB, see if there are entries in the BTBC and set the predictor to always predict taken. For conditional branches, the BAC cannot confirm if they are taken/not-taken yet, but it can at least validate the predicted address and correct the BTB in the event of a bad address prediction. Sometimes the BTB won’t identify/predict a branch at all. The BAC needs to correct this and give the BTB new information about this instruction. Since the BAC doesn’t have a conditional predictor of its own, it uses a simple mechanism (backwards branches taken, forward branches not taken).

Somebody will need to confirm my understanding of these hardware counters, but I believe they mean the following:

  • BACLEAR.CLEAR is incremented when the BTB in fetch does a bad
    job and the BAC in decode can fix it.
  • BPU_CLEARS.EARLY is
    incremented when fetch decides (incorrectly) to load the next
    instruction before the BTB predicts that it should actually load from
    the taken path instead. This is because the BTB requires multiple cycles and fetch uses that time to speculatively load a consecutive block of instructions. This can be due to Intel using two BTBs, one quick and the other slower but more accurate. It takes more cycles to get a better prediction.

This explains why the penalty of a detecting a misprediction in the BTB is 2/3 cycles whereas the detecting a misprediction in the BAC is 8 cycles.

More Related Contents:

  1. What Every Programmer Should Know About Memory?
  2. How are x86 uops scheduled, exactly?
  3. SIMD instructions lowering CPU frequency
  4. Deoptimizing a program for the pipeline in Intel Sandybridge-family CPUs
  5. How much of ‘What Every Programmer Should Know About Memory’ is still valid?
  6. What exactly happens when a skylake CPU mispredicts a branch?
  7. Slow jmp-instruction
  8. Why is a conditional move not vulnerable to Branch Prediction Failure?
  9. Why did Intel change the static branch prediction mechanism over these years?
  10. Why is the loop instruction slow? Couldn’t Intel have implemented it efficiently?
  11. How exactly do partial registers on Haswell/Skylake perform? Writing AL seems to have a false dependency on RAX, and AH is inconsistent
  12. When is optimisation premature?
  13. What is a Partial Flag Stall?
  14. What setup does REP do?
  15. Size of store buffers on Intel hardware? What exactly is a store buffer?
  16. Avoid stalling pipeline by calculating conditional early
  17. Time complexity of memory allocation
  18. Deflate compression browser compatibility and advantages over GZIP
  19. Is the inequality operator faster than the equality operator?
  20. If I don’t use fences, how long could it take a core to see another core’s writes?
  21. foldl is tail recursive, so how come foldr runs faster than foldl?
  22. Is LFENCE serializing on AMD processors?
  23. Why is x86 little endian?
  24. How has CPU architecture evolution affected virtual function call performance?
  25. Why does Intel hide internal RISC core in their processors?
  26. What is Big O notation? Do you use it? [duplicate]
  27. Can I use the “null pointer optimization” for my own non-pointer types?
  28. Why does this code execute more slowly after strength-reducing multiplications to loop-carried additions?
  29. Can the simple decoders in recent Intel microarchitectures handle all 1-µop instructions?
  30. What is the maximum possible IPC can be achieved by Intel Nehalem Microarchitecture?

Leave a Comment