Static Prediction, BTBs and Return Address Stacks

The simplest branch predictors do not learn at all: they apply one fixed rule to every branch. Those rules are cheap, and on many programs they do surprisingly well. But knowing that a branch will be taken is not enough. The processor must also know where it goes, and it must know this in the fetch stage, before the instruction has been decoded. This article explains the static rules, compares them on real programs, and then explains the two structures that supply target addresses: the branch target buffer and the return address stack.

12 min read | Beginner to Intermediate

What You'll Learn

• Compare the static rules predict not taken, predict taken, and backward taken forward not taken
• Explain how compilers and programmers can give branch hints
• Describe what a branch target buffer stores and how it is used
• Explain how a return address stack predicts returns

Static Prediction

A static predictor gives the same answer every time a given branch is seen. It uses only what is known from the instruction itself. No table remembers what happened before. The opposite is a dynamic predictor, which learns from the branch's history, as Dynamic Predictors: Bimodal and gshare explains.

Predict Not Taken

The simplest rule is to keep fetching in order. It needs no hardware at all, and it also needs no target address, because fetching just continues. This is what a basic five-stage pipeline does. The weakness is that most branches are taken, because loops branch back on almost every pass.

Predict Taken

Always predicting taken is right more often, but it needs the target address in time. The target is the PC plus an offset inside the instruction, so the processor must first read and decode the instruction. Without a stored target, it would still lose a cycle or two, which removes much of the benefit.

Backward Taken, Forward Not Taken

A smarter rule uses the direction of the jump. A branch to a lower address, a backward branch, is usually the bottom of a loop, so it is usually taken. A branch to a higher address, a forward branch, is usually skipping an if block or handling a rare case, so it is more often not taken. This rule is called BTFN, for backward taken, forward not taken. The hardware only has to look at the sign bit of the offset. Compilers arrange code with this in mind, placing the likely path straight after the branch.

The RISC-V specification encourages this: it says software should assume that backward branches will be predicted taken and forward branches not taken, at least the first time they are met.

The Rules on Real Programs

A model of each rule was run on the branch traces of six small programs. The table shows the fraction of conditional branches predicted correctly:

Predicting not taken, the choice of the simplest pipeline, gets the worst possible result on tight loops: it is wrong nearly every time. That explains the large flush costs in Load-Use Stalls and Control Hazards. BTFN never does worse than always predicting taken here, and it is well ahead on the linked-list program, whose code has many forward branches that are rarely taken. For a one-bit look at the instruction, that is a remarkable return. Other programs would give other numbers, but the order of the three rules is typical.

Hints From the Compiler

A compiler can do better than a fixed rule, because it can see the program's structure. It can work out which paths are likely, or use a profile from a test run. Programmers can give a hint too: in GCC, if (__builtin_expect(err, 0)) says the condition is rarely true. On RISC-V, this does not change any bits of the branch. It simply makes the compiler place the likely code straight after the branch, so that BTFN and the instruction cache both work in its favor.

The Target Problem

Suppose the processor correctly predicts "taken". It still needs the address. For a branch or jal, the target is the PC plus an offset, but the instruction is only just being read from memory in the first stage, and the offset's bits are scattered through it. On a five-stage design the target comes from the execute stage. That is two cycles too late to fetch from it next cycle.

The solution is to remember. The processor keeps a small table of branches it has seen recently, together with their targets.

The Branch Target Buffer

A branch target buffer (BTB) is a small cache indexed by the address of the instruction being fetched. Each entry holds a tag, identifying which branch it belongs to, and that branch's target.

Each cycle, while the instruction memory is being read, the PC also indexes the BTB. If the tag matches, the processor knows, without having seen the instruction, that there is a branch or jump at this address, and it knows where it probably goes. If the direction predictor says taken, the next fetch comes from the stored target, with no lost cycle. If the tag does not match, the processor assumes an ordinary instruction and fetches PC + 4.

The BTB answers two of the three questions from Why Branches Hurt: is this a branch, and where does it go. When a branch is executed, the BTB is updated. A branch being seen for the first time misses, costs a normal flush if taken, and is then added to the table.

In a model on the same six programs, a direct-mapped BTB of only 16 entries found the right target for over 97 percent of taken branches and jumps on every program, and 64 entries gave nearly 100 percent. With 4 entries, the result on a matrix program fell to about a third, because several active branches mapped to the same entry and kept pushing each other out. These programs are tiny, with only a handful of branches in their loops. Real software has thousands of active branches, so real BTBs have thousands of entries, often in two levels: a small fast one and a large slower one.

Each entry costs real storage: a tag and a full target. To save bits, designs store only part of the tag, accepting a rare false match, and only the low bits of the target, since most branches stay near their own address.

The Return Address Stack

A function's ret is an unusual case. It is always taken, but its target changes with every caller. A BTB stores one target per branch, so if a function is called from two places in turn, it predicts the wrong return address every time.

Yet returns follow a perfect rule. Calls and returns nest: each return goes back to the instruction after the most recent unfinished call. So the processor keeps a small hardware stack, the return address stack (RAS). When it fetches a call, it pushes the address of the following instruction. When it fetches a return, it pops the top of the stack and uses that as the predicted target.

On RISC-V, the convention is what makes this work. A call writes the return address to ra, and a return is jalr x0,0(ra). The hardware recognizes these patterns, and the RISC-V specification lists exactly which register combinations are hints for a push and a pop. Branches and Jumps covers those instructions.

In the model, a RAS with one entry was right on nearly all returns on these small programs, whose call depth is very low. Most real programs need more. A depth of 16 or so handles almost anything except very deep recursion, and when the stack overflows, the oldest entries are simply lost. Speculation adds a difficulty: a wrong-path call or return would corrupt the stack, so good designs save a pointer to the top of the stack at each branch and restore it on a flush.

Indirect Jumps

A jalr through a register that is not a return is the hardest case. It appears as a function pointer, a virtual method call in C++, or a large switch. The same instruction may jump to many different places. A plain BTB predicts the last target, which is often wrong. Large cores use a dedicated indirect predictor, which chooses among several stored targets using the recent branch history, much as gshare does for direction.

Putting the Pieces Together

In the fetch stage of a real core, these structures all work at once. The PC indexes the BTB to find out whether a branch is here and where it goes. The direction predictor says whether a conditional branch will be taken. If the instruction is a return, the return stack supplies the address instead of the BTB. Later, when the branch is resolved, the result updates all of them. Every structure is only a guess, so the execute stage always checks the outcome against the prediction, and that check is what triggers a flush when they disagree.

Common Mistakes