Branch target buffer (BTB): Question bank — Hardware deep dive

Vocabulary reminders before we start, so no symbol is unearned. Look at Figure 1 while you read these — it draws the whole lookup:

PC = program counter = the address of the instruction we are about to fetch.
PC+4 = the next sequential address (instructions are 4 bytes apart here), i.e. "keep going straight."
Index = the lower bits of the PC used to pick which row (slot) of the BTB to look in — a fast, direct address into the table (see the amber arrow in Figure 1).
Tag = the upper bits of the PC stored inside that row, compared against the current PC's upper bits to confirm "this row really belongs to my branch, not a different one that landed in the same row."
Aliasing = two different branch PCs whose lower bits (index) are identical, so they fight over the same row — one overwrites the other. The tag comparison catches this and reports a miss instead of a wrong jump.
I-Cache = the Instruction Cache, the fast memory the fetch stage reads the actual instruction bytes from. It is read in parallel with the BTB: while the I-Cache fetches the bytes, the BTB decides what address to fetch next.
Hit / Miss = whether the row's tag matched (hit) or not (miss).
Flush = throwing away wrongly-fetched instructions from the pipeline, a control hazard penalty.
Direction = the yes/no answer "is this branch taken?" — owned by the branch predictor.
Target = the address to jump to if taken — owned by the BTB.

Figure 2 shows the two units (BTB and predictor) as separate boxes both fed by the PC, and Figure 3 is the fetch-cycle timeline that most of the timing traps below refer to.

True or false — justify

Keep the split "direction vs target" in mind — most traps live on that seam.

The BTB decides whether a branch is taken.

False. The BTB only stores the target (where to jump if taken); the taken/not-taken direction comes from the branch predictor. They are two cooperating units (Figure 2), not one.

A BTB miss is always harmless.

False. It is harmless only if the instruction really wasn't a taken branch. On a miss we assume PC+4; if it was a taken branch, decode later corrects us and we eat a flush penalty.

Tag matching in the BTB affects correctness, not just speed.

False for correctness, true for speed. The tag check guarantees correctness by rejecting the wrong branch on an alias; without it we'd jump to a stale target. It only ever costs us performance (a miss), never correctness.

If the branch predictor says "not taken," the BTB target is ignored this cycle.

True. Even on a BTB hit, a "not taken" prediction means we fetch PC+4; the stored target sits unused until a future "taken" prediction.

The BTB and branch prediction happen sequentially, prediction first.

False. They run in parallel during the same fetch cycle (Figure 3) — that parallelism is exactly what buys same-cycle redirection.

A correctly-predicted taken branch with a BTB hit costs zero penalty cycles.

True (ideal case). Target is available in the fetch cycle, so the very next fetch comes from the target with no bubble.

The BTB stores whether the instruction is even a branch at all.

Effectively true, implicitly. A BTB hit means "we've seen a taken branch here before," so presence in the BTB is itself the "this is a branch" signal — one reason it can be looked up before decode.

Doubling the BTB size always improves performance.

False. A bigger table has more rows, so the address decoder that selects a row and the wires that carry data out are physically longer, and the tag-compare must wait for a slower array read — that extra propagation delay can push the lookup past the single-cycle window the fetch stage allows (Figure 3). Beyond the working set, extra capacity gives diminishing hit-rate returns while still paying that latency.

The BTB removes the need to decode branches entirely.

False. Decode still verifies the branch and computes the real target for updating and for BTB misses/mispredictions; the BTB just lets us speculate the target earlier via speculation.

An unconditional jump still needs the branch predictor.

Mostly false for direction. It's always taken, so direction is trivial — but it still needs the BTB (or decode) to know where it goes, and indirect jumps need target prediction too.

Spot the error

Each statement contains one flaw. Name it and show the reasoning that exposes it.

"On a BTB hit we can skip the tag comparison since indexing already found the entry."

The index only narrows down a slot. Why it's wrong: the index is just the PC's lower bits, and many different PCs share those same lower bits (aliasing, Figure 1), so a row can currently hold a different branch's target — the tag (upper bits) is the only thing that proves it's this branch. Skip it and you jump to a stale target.

"Because the BTB caches the target, function returns are handled perfectly by it."

A return goes to a different caller each time. Why it's wrong: the BTB stores one fixed target per branch, but a subroutine called from many sites returns to many addresses, so last time's cached target is almost always wrong. A stack-shaped structure, the RAS, pops the matching caller instead.

"A BTB miss means the instruction is definitely not a branch."

Why it's wrong: a miss only says "no matching row is stored right now" — the branch may be brand-new (never inserted) or evicted by aliasing. We assume not-a-branch for speed, but decode can later reveal it was a branch and force a flush.

"Aliasing produces a wrong jump, so the BTB is unsafe."

Why it's wrong: aliasing changes only the lower index bits collision, but the stored upper tag bits still differ, so the tag comparison fails → a miss, not a wrong jump. The cost is a lost speed opportunity, never a correctness bug.

"With a 95%-accurate BTB, branch penalties are basically gone."

Why it's wrong: zero penalty needs three things to all succeed — BTB hit, no aliasing eviction, and a correct direction prediction. These are independent failure modes, so their combined miss probability is larger than any single 5% figure; penalties persist.

"Since the BTB feeds the next PC, it must be read after the I-Cache."

Why it's wrong: the BTB and I-Cache both take the same PC and start in the same cycle (Figure 3). The I-Cache fetches the instruction bytes while the BTB independently computes the next PC — serializing them would reintroduce exactly the stall the BTB exists to remove.

"The BTB stores the branch's own PC as its payload."

Why it's wrong: the PC is the key — its lower bits form the index and its upper bits form the tag. The payload must be new information we couldn't otherwise get early, namely the target address. Storing the PC we already hold would tell us nothing.

Why questions

Give the reason, not just the fact.

Why can the BTB predict a target before the instruction is decoded?

Because it's indexed by the fetch PC alone (Figure 1), and a prior hit already encodes "a taken branch lived here going there" — no opcode bits (which need decode) are required to look it up.

Why is optimizing the BTB miss case as "assume PC+4" a good design?

The common case is non-branch instructions running sequentially, so defaulting to PC+4 is right most of the time; only the rarer real-branch misses pay a penalty.

Why does a larger BTB not scale performance indefinitely?

Once it covers the program's branch working set, extra rows mostly sit idle, while the longer decoder/word-lines add propagation delay that can push the lookup past the single-cycle budget (Figure 3).

Why are indirect branches harder for a plain BTB?

Their target varies at runtime (e.g., a pointer call), so a single cached target is often stale — they need specialized indirect-target predictors rather than one fixed entry.

Why keep direction prediction separate from the BTB?

They answer different questions (whether vs. where). What fusing would force: one merged table would have to store, per row, both a direction counter and a target address, and update them on different events — the direction bits change every time the branch resolves taken/not-taken, while the target changes only when the jump destination itself changes (rare). Bundling two things with different update rates and widths into one row wastes bits on entries that only need one field, and complicates the write logic that now must know which field an update touches. Keeping them separate (Figure 2) lets each table be sized and updated on its own clock of events, though some designs still fuse them deliberately.

Why does a BTB pair naturally with delay slots's historical goal?

Both attack the same control-hazard bubble — delay slots hide it in the ISA, the BTB removes it in hardware, so modern designs prefer the BTB and drop the slot.

Why is same-cycle prediction the headline feature?

Without it, even a correct "taken" prediction stalls until decode computes the target; the BTB supplies the target in the fetch cycle (Figure 3), collapsing that 1–2 cycle wait to zero.

Edge cases

Boundary and degenerate scenarios — the ones exams love.

First-ever execution of a branch (cold BTB).

Guaranteed miss → fetch PC+4 → decode corrects → flush + penalty, then the BTB entry is written so later runs hit.

Two branches whose PCs collide in the same BTB index.

The second overwrites the first (same row in Figure 1); re-running the first now sees a tag mismatch → miss → penalty. Correctness holds, speed drops (classic aliasing).

BTB hit but predictor says "not taken."

We correctly fetch PC+4 and ignore the stored target; if the branch actually was taken, that's a predictor misprediction, not a BTB fault.

BTB hit + correct target + wrong direction prediction.

We may fetch the wrong path → flush. Having the right target doesn't save us because direction was wrong — both must be right for zero penalty.

Non-branch instruction that happens to alias a branch's BTB slot.

On a hit the tag mismatch (different PC) yields a miss → PC+4, which is correct for a non-branch anyway; no harm done.

A branch that is almost never taken.

The predictor keeps saying "not taken," so the BTB entry, even if present, is rarely consulted — the target being cached costs nothing but buys little.

Return instruction with a deep call stack.

A single BTB target is usually wrong because the return site changes; the RAS pops the correct caller, so returns bypass BTB target prediction.

Self-modifying or freshly loaded code region.

Old BTB entries may point to stale targets; the entries must be invalidated/re-learned, otherwise speculation follows dead addresses (later squashed at commit).

Recall One-line summary of the whole trap set

The BTB answers where (target), the predictor answers whether (direction), the tag guarantees correctness even under aliasing, and a miss just means "assume straight-line PC+4."