1
$\begingroup$

If the branch predictor is placed in the fetch stage then how does it know that the current instruction is actually a branch before trying to predict its outcome? Is some (very little) decoding already done in the fetch stage before going to the actual decode stage?

$\endgroup$
2
$\begingroup$

There is no decoding done in the fetch stage. The fetch stage relies on the Branch Target Buffer (BTB) to tell it which instruction addresses have had taken branches in the past.

The BTB is a small highly associative structure. It performs two functions. First it tells you which instructions are and are not branches. If the current program counter (PC) is in the BTB then the instruction pointed to by the PC is a branch, and the BTB will tell us the target of that branch and the branch predictor will give us a guess about whether the branch is taken or not taken.

If the current program counter in not in the BTB then either (a) the current instruction is not a branch or (b) we have never seen this instruction before (and don't know whether or not it is a branch, but we'll assume it is not or (c) the current instruction is a branch, but we've never seen the branch taken, so we've never put it in the BTB.

This last function (branches that are never taken are never put in the BTB) makes the BTB actually a very effective branch predictor. Branches that have never been taken are unlikely to be taken in the future, and the BTB predicts this correctly. Branches that have been taken at least once in the recent pass are slightly more likely than not to be taken in the future, and the BTB reflects this as well.

The BTB effect was rarely taken into account in academic branch predictor research done at the end of the 1990s (nor is it taken into account in the statistics in most textbooks). For most programs on most architectures the BTB actually filters out a significant number of branches (on the order of 25%) because they are never taken or rarely taken. For those 25% of branches you essentially get a 99% accurate branch prediction for free. The "real" branch predictor needs focus, then, only on the other 75% of branches.

$\endgroup$
  • $\begingroup$ Is the full PC checked if it is in the BTB or only the low-order bits? After some searching I found these contradictions: first article: Indexed by low-order bits of PC of recently-executed branches. second article: the full PC value must be compared to validate that this is a branch instruction before taking any action. I assume that it is the full PC because otherwise we would branch even on non branch instructions? $\endgroup$ – gilianzz Feb 21 '15 at 19:07
  • $\begingroup$ "indexed by low-order bits of PC of recently-executed branches" sounds like a branch predictor indexing scheme. For BTB it probably depends on power, area, timing and workload constraints of a particular design. If the BTB is not fully associative then the some bits are used to index to a set and only the non-index bits would be considered for comparison. But on 64-bit designs I doubt that the tag is ever bigger than about 30 bits. $\endgroup$ – Wandering Logic Feb 21 '15 at 19:17
  • $\begingroup$ What about this situation: in some program a branch occurs so that address gets put in the BTB. Now after self-modifying code the branch is now an ADD instruction: will this execute as a branch and later fix itself saying it wasn't a branch instruction, removing it from the BTB? $\endgroup$ – gilianzz Feb 21 '15 at 19:25
  • $\begingroup$ Yes. The BTB and branch predictor are producing predictions. Every prediction is tested somewhere later in the pipeline. (With your example you could potentially find the misprediction just after decode. Most of the time you would detect the misprediction just after executing the instruction you thought was a branch.) $\endgroup$ – Wandering Logic Feb 21 '15 at 19:28
  • $\begingroup$ If I index using low-order bits and not the full PC, wouldn't this cause performance issues because it will sometimes try to execute non branch instructions as branches because the low-order bits of the PC were the same? $\endgroup$ – gilianzz Feb 21 '15 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.