Return address stack: Exercises — Hardware deep dive

This page is a self-test ladder for the Return Address Stack. Each problem states the setup cleanly, then hides a full worked solution inside a collapsible Solution callout — read the problem, try it, then reveal.

Before we start, one shared vocabulary reminder so no symbol is used unearned:

Level 1 — Recognition

Exercise 1.1

Which of these instruction types should update the RAS, and in which direction (push / pop / nothing)? CALL, RET, ADD, JMP (unconditional direct jump), indirect switch jump.

Recall Solution

CALL → push (writes the return address for the future matching return).
RET → pop (reads the predicted target back).
ADD → nothing (not a control-flow instruction).
JMP (direct) → nothing for the RAS; its target is fixed and known at decode, no stack needed.
switch indirect jump → nothing in the RAS; this is a data-dependent target handled by the Branch Target Buffer / Indirect Branch Prediction, not LIFO.

The single litmus test: does this instruction obey call/return nesting? Only CALL/RET do.

Exercise 1.2

A RAS has $N = 8$ slots. State the maximum number of return addresses it can hold, and what count equals when it is empty vs. full.

Recall Solution

Maximum live entries $= N = 8$ .
Empty: $count = 0$ . Full: $count = 8$ .
Note the circular buffer always has 8 physical slots; count — not the slot count — tells you how many are valid.

Level 2 — Application

Exercise 2.1

Given this code with 4-byte instructions and an empty RAS ( $N = 8$ ), list the RAS contents (bottom→top) after each control-flow event.

0x1000: CALL 0x2000
0x2000: CALL 0x3000
0x3000: RET
0x2004: RET

Recall Solution

Return address for a CALL at $P C$ is $P C + 4$ .

Event	Action	RAS (bottom→top)	count
`CALL` @0x1000	push 0x1004	[0x1004]	1
`CALL` @0x2000	push 0x2004	[0x1004, 0x2004]	2
`RET` @0x3000	pop → 0x2004	[0x1004]	1
`RET` @0x2004	pop → 0x1004	[]	0

Both returns predicted correctly. Notice the first RET pops the most recent push (0x2004) — that is LIFO doing exactly what call nesting demands.

Exercise 2.2

A CALL sits at 0x8040 and the call instruction is 6 bytes long. What return address gets pushed?

Recall Solution

$P C_{call} + size_{call} = 0x8040 + 6 = 0x8046 .$ The size matters: not every ISA uses 4-byte instructions, so always add the actual byte length.

Level 3 — Analysis

Exercise 3.1 (Overflow)

RAS depth $N = 4$ , initially empty. The program does 5 nested calls then unwinds: A→B→C→D→E→F, then F,E,D,C,B all return in order. Which return, if any, mispredicts, and why?

Recall Solution

Label the pushed return addresses ret_A..ret_E (one per call).

Event	RAS (bottom→top)	count	Note
A→B	[ret_A]	1
B→C	[ret_A, ret_B]	2
C→D	[ret_A, ret_B, ret_C]	3
D→E	[ret_A, ret_B, ret_C, ret_D]	4	full
E→F	[ret_B, ret_C, ret_D, ret_E]	4	ret_A evicted
F ret	[ret_B, ret_C, ret_D]	3	✓ → E
E ret	[ret_B, ret_C]	2	✓ → D
D ret	[ret_B]	1	✓ → C
C ret	[]	0	✓ → B
B ret	[] (count 0)	0	✗ misprediction

Exactly one misprediction: the final return to A. When the 5th push happened the oldest entry ret_A was overwritten. Everything nested inside the overflow window still predicts perfectly; only the entry pushed out of the window is lost. Count of correct returns $= 4$ , mispredictions $= 1$ .

Exercise 3.2 (Underflow)

RAS empty ( $count = 0$ ). The program executes a stray RET (e.g. a hand-written assembly stub, or a longjmp-style unwind) with no matching CALL. What does a correctly-guarded RAS do, and what would a buggy RAS using bare mod N arithmetic do?

Recall Solution

Correct RAS: $count = 0$ , so the pop is illegal. It returns "no prediction" and defers to the Branch Target Buffer. count stays clamped at $0$ via $max (count - 1, 0)$ .
Buggy bare-mod RAS: $TOS \leftarrow (0 - 1) mod N = N - 1$ . It reads slot $N - 1$ , which holds stale leftover bits from some earlier program phase → a garbage target → guaranteed pipeline flush, and worse, TOS now points into "phantom" data so subsequent pushes/pops are misaligned.

This is precisely why the parent note keeps count separate from TOS: TOS handles position, count handles validity.

Level 4 — Synthesis

Exercise 4.1 (Speculation + checkpoint)

The predictor speculatively fetches CALL X then, on the wrong path, RET. Later the CALL is found to be mispredicted and the pipeline flushes. Describe what the RAS must restore, and why restoring only TOS is insufficient.

Recall Solution

On the wrong path the speculative RAS did: push (from CALL X) then pop (from RET). Net TOS change is zero, but the contents were disturbed — the pop consumed an entry that the correct path still needs.

To recover, the flush restores from a checkpoint taken before the mispredicted CALL: $RAS_{spec} \leftarrow snapshot (TOS, count, top entries) .$

TOS alone is insufficient: after push-then-pop, TOS is back where it started but the top-of-stack data may have been overwritten by the speculative push. You must restore the value and the count, not just the pointer.
This is why real designs snapshot TOS and count (and often the actual top entry) at each speculative CALL. See Speculative Execution.

Exercise 4.2 (Design tradeoff)

Using the accuracy figures below, a team debates $N = 4$ vs $N = 16$ . If returns are 12% of all branches and each return misprediction costs a 15-cycle flush, compute the extra cycles per 1000 branches caused by using $N = 4$ instead of $N = 16$ .

$N = 4$ → return accuracy $85%$
$N = 16$ → return accuracy $97%$

Recall Solution

Returns per 1000 branches: $1000 \times 0.12 = 120$ .

Mispredicted returns:

$N = 4$ : $120 \times (1 - 0.85) = 120 \times 0.15 = 18$ .
$N = 16$ : $120 \times (1 - 0.97) = 120 \times 0.03 = 3.6$ .

Extra mispredictions from choosing $N = 4$ : $18 - 3.6 = 14.4$ . Extra cycles: $14.4 \times 15 = 216$ cycles per 1000 branches.

That is a large, cheap-to-remove penalty — the whole reason production chips ship 16–32 entry RAS.

Level 5 — Mastery

Exercise 5.1 (Full trace with overflow + speculation)

$N = 2$ . Trace this sequence and report every predicted target and every misprediction:

CALL foo        (ret = R1)
  CALL bar      (ret = R2)
    CALL baz    (ret = R3)   <- causes overflow
    RET (from baz)
  RET (from bar)
RET (from foo)

Recall Solution

$N = 2$ , so at most 2 live entries.

Event	Action	RAS (bottom→top)	count	Predicted target
CALL foo	push R1	[R1]	1	—
CALL bar	push R2	[R1, R2]	2	—
CALL baz	push R3 (evict R1)	[R2, R3]	2	—
RET baz	pop → R3	[R2]	1	R3 ✓
RET bar	pop → R2	[]	0	R2 ✓
RET foo	pop, count=0	[]	0	no prediction ✗

Correct predictions $= 2$ (returns to baz's caller and bar's caller). Mispredictions $= 1$ (the return to foo's caller, because R1 was evicted by the overflow). The final pop correctly reports "no prediction" rather than garbage — the count guard doing its job.

Exercise 5.2 (Why not just use a BTB — quantitative)

A return instruction at a fixed PC is called from 4 different call sites, each equally likely. A single-target Branch Target Buffer entry stores only the last seen target. Estimate the BTB's return prediction accuracy for this instruction, and contrast with the RAS.

Recall Solution

The BTB records one target per PC. With 4 equally-likely, independently-arriving callers, the stored target matches the next actual target only when the next caller equals the last caller: $P (hit) = \frac{1}{4} = 25%.$ So $\approx 75%$ misprediction — matching the parent note's "30–50%+" for realistic mixes and worse here.

The RAS instead pops the address pushed by this dynamic caller's CALL, so it is right regardless of which of the 4 sites called — near- $100%$ (limited only by depth/overflow). This is the core reason returns get their own structure: one PC, many targets, but a perfectly correlated LIFO signal the BTB cannot see. See Indirect Branch Prediction.

Wrap-up recall

Cover the answer, then reveal.

What structure predicts return targets and why LIFO?

A Return Address Stack; returns unwind in exact reverse order of calls, so most-recent-push must be first-pop.

On a CALL with size

s

at address

P C

, what is pushed?

P C + s

, the address after the call.

What guards against popping an empty RAS?

The count (occupancy) reaches 0 and the pop returns "no prediction" instead of stale data.

Why must speculation snapshot both TOS and count (and top value)?

A wrong-path push-then-pop leaves TOS unchanged but corrupts contents; only a full snapshot restores correctness.

Related: Branch Prediction Basics · Call Stack · Instruction Fetch · Pipeline Hazards