Return address stack: Worked examples — Hardware deep dive

This is a worked-examples deep dive for the Return Address Stack (RAS). The parent note built the machine: a tiny hardware stack that pushes a return address on every CALL and pops it on every RET. Here we drive that machine through every situation it can meet and watch what each control field does, one cycle at a time.

Before any example, let us re-earn the three numbers the RAS carries, because every scenario below is really a story about how these three change.

The scenario matrix

Every situation the RAS can face is one of these cells. The examples below are tagged with the cell they cover, and together they hit all of them.

#	Cell (case class)	What makes it distinct	Covered by
C1	Balanced call/return, no wrap	`count` never reaches $N$ ; textbook LIFO	Ex 1
C2	Interleaved deep + shallow nesting	Multiple pushes then partial pops then more pushes	Ex 2
C3	Overflow (push when `count = N`)	Oldest live entry evicted; count saturates	Ex 3
C4	Underflow (pop when `count = 0`)	Degenerate: must return no-prediction	Ex 4
C5	Wrap-around of TOS pointer	TOS crosses the $N - 1 \to 0$ seam while count stays healthy	Ex 5
C6	Speculation mis-predict → restore	Snapshot of (TOS, count) rolled back on flush	Ex 6
C7	Wrong tool (non-return indirect branch)	RAS should not fire; degenerate misuse	Ex 7
C8	Real-world word problem	Turn a C call chain into RAS depth demand	Ex 8
C9	Exam twist: accuracy from depth	Compute expected hit-rate for a workload	Ex 9

Example 1 — Balanced chain, no wrap (cell C1)

Forecast: three pops in reverse order → 0x3004, then 0x2004, then 0x1004.

Figure 1 below is a three-panel filmstrip of the same $N = 4$ ring. Left panel: after all three pushes, holes 0,1,2 are green (live) holding 0x1004,0x2004,0x3004, and the yellow TOS arrow sits at hole 3 (the next free hole), count=3. Middle panel: after the first pop, hole 2 has gone dim (dead) and the arrow has stepped back to it — the popped value 0x3004 came from there, count=2. Right panel: all holes dim, arrow back at hole 0, count=0 — the ring is empty. Watch the yellow arrow climb on pushes and descend on pops; watch green fade to dim as count falls.

Push 0x1004 (return point after main's call). Why this step? Every CALL records where control must come back to, which is $P C_{call} + size_{call} = 0x1000 + 4 = 0x1004$ . Now slot[0]=0x1004, TOS=1, count=1.
Push 0x2004. Why? Nested call — the ring must remember foo's continuation too. slot[1]=0x2004, TOS=2, count=2.
Push 0x3004. Why? Deepest call. slot[2]=0x3004, TOS=3, count=3. (This is the left panel of Figure 1.)
baz RET → pop. Why? LIFO: the most recent pusher (bar calling baz) is the first to be answered. TOS: 3→2, read slot[2]=0x3004, count=2. ✔ predicted 0x3004. (Middle panel.)
bar RET → pop. Why? Next-most-recent open call answered next. TOS: 2→1, read slot[1]=0x2004, count=1. ✔ 0x2004.
foo RET → pop. Why? Oldest remaining open call answered last. TOS: 1→0, read slot[0]=0x1004, count=0. ✔ 0x1004. Ring empty again (right panel).

Verify: each popped value equals the return point printed in the setup; count returned exactly to $0$ (as many pops as pushes). All three predictions correct → zero pipeline flushes for these returns.

Example 2 — Interleaved nesting (cell C2)

Forecast: r2, then r3, then r1.

push r1 → slot[0]=r1, TOS=1, count=1. Why? First call.
push r2 → slot[1]=r2, TOS=2, count=2. Why? Nested call while inside first.
POP → TOS:2→1, read slot[1]=r2, count=1. ✔ r2. Why? Inner function returned first.
push r3 → slot[1]=r3 (reuses the freed hole!), TOS=2, count=2. Why this step? The hole vacated by r2 is now free real estate — a new sibling call reuses it. r1 at slot[0] is untouched.
POP → TOS:2→1, read slot[1]=r3, count=1. ✔ r3. Why? The most recent live push was r3 (the sibling call), so LIFO answers it first — even though it physically occupies the same hole r2 used earlier.
POP → TOS:1→0, read slot[0]=r1, count=0. ✔ r1. Empty. Why? Only r1 (the original outer call) is still open, so it pops last and the ring drains to count=0.

Verify: interleaving never disturbed r1 at the bottom — it waited patiently and popped last, exactly as LIFO promises. Reused slot proves the ring recycles space without corruption when count is honored.

Example 3 — Overflow (cell C3)

Forecast: the last return (to A) mis-predicts, because $r_{A}$ got evicted.

Figure 2 below is a three-panel story of the eviction. Left panel: after four pushes the ring is completely green (count = N = 4) holding rA,rB,rC,rD, and the yellow TOS arrow has wrapped all the way around back to hole 0. Middle panel: the fifth push writes rE into hole 0 on top of rA (shown in red to flag the overwrite); count stays pinned at 4. Right panel: after everything is popped, all holes are dim and count=0, and a red marker shows A's return finding nothing live — the mispredict. The teaching point: red hole 0 = the sacrificed oldest entry.

push $r_{A}, r_{B}, r_{C}, r_{D}$ → holes $0, 1, 2, 3$ fill; after the 4th push TOS: 3→0 (wraps via $(3 + 1) mod 4 = 0$ ), count=4 = $N$ . Why? Four pushes exactly fill the ring; TOS lands back at hole 0. (Left panel of Figure 2.)
push $r_{E}$ → slot[0] \leftarrow r_E overwriting $r_{A}$ , then TOS: 0→1, count = min(4+1,4)=4. Why this step? Ring is full. The min(count+1,N) rule caps count while TOS still advances, so the oldest live entry (hole 0 = $r_{A}$ ) is silently sacrificed. This eviction is intended on overflow. (Middle panel.)
pop (E ret) → TOS: 1→0 (via $(1 - 1) mod 4$ ), read slot[0]=r_E, count=3. ✔ $r_{E}$ . Why the arrow moves back to 0? Pop always steps TOS one hole backward to reach the most-recently-written live slot.
pop (D ret) → TOS: 0→3 (wraps via $(0 - 1) mod 4 = 3$ ), read slot[3]=r_D, count=2. ✔ $r_{D}$ . Why? The seam crossing $0 \to 3$ is normal ring arithmetic; count=3>0 proved the slot live.
pop (C ret) → TOS: 3→2, read slot[2]=r_C, count=1. ✔ $r_{C}$ . Why? Continue stepping back down the live entries.
pop (B ret) → TOS: 2→1, read slot[1]=r_B, count=0. ✔ $r_{B}$ . Why? Last live entry consumed; count hits 0.
pop (A ret) → count is already $0$ , so TOS is not moved. Why this matters? The referee blocks it: no live entry exists for A. Prediction = no-prediction / mis-predict → one fetch redirect penalty. (Right panel of Figure 2.)

Verify: exactly one mis-prediction, and it is A's return (the evicted one). Four correct, one wrong. Push count 5 > $N = 4$ ⇒ overflow guaranteed one loss.

Example 4 — Underflow (degenerate) (cell C4)

Forecast: "no prediction" — not garbage.

Fetch RET, attempt pop. Why check first? The max(count-1, 0) guard and the count==0 test exist for precisely this moment.
Read count. count = 0. Why? Nothing was ever pushed.
Refuse the pop. TOS is not decremented; count stays clamped at $0$ by $max (0 - 1, 0) = 0$ . Output = no valid target. Why? A bare $(TOS - 1) mod N$ would step to hole $N - 1$ and hand back whatever ancient bits live there — a spurious prediction pointing at stale data.

Verify: with the guard, the front end falls back to the BTB or stalls rather than fetching from a random address. Without the guard: (0-1) mod 8 = 7, so it would read slot[7] — pure garbage. The guard converts a wrong prediction into an honest "I don't know."

Example 5 — Wrap-around of TOS with healthy count (cell C5)

Forecast: w, z, y, x.

push $z$ → slot[0]=z, TOS: 0→1, count=3. Why? The next-write hole is 0 (where the arrow points), so the new return address lands there and the arrow advances.
push $w$ → slot[1]=w, TOS: 1→2, count=4. Why this step? Hole 1 was also empty, so w fills the last free hole; count reaches $N = 4$ without any overwrite — every push landed in a genuinely empty hole, so this is a full-but-not-overflowing ring.
pop → TOS: 2→1, read slot[1]=w, count=3. ✔ w. Why? w was the most recently pushed live entry, so LIFO answers it first; the arrow steps back to hole 1 to read it.
pop → TOS: 1→0, read slot[0]=z, count=2. ✔ z. Why? Next-most-recent live push was z in hole 0; the arrow steps back one more hole.
pop → TOS: 0→3 (wrap across the seam $0 \to N - 1$ via $(0 - 1) mod 4 = 3$ ), read slot[3]=y, count=1. ✔ y. Why this step? The two newest entries are gone, so the next live one is y in hole 3 — reached by rolling the arrow from hole 0 back to hole 3 with no special case.
pop → TOS: 3→2, read slot[2]=x, count=0. ✔ x. Why? Only x (the oldest live entry) remains; it pops last and drains the ring to count=0.

Verify: the seam crossing (0 → 3) is transparent because count (2 at that moment) proved the entry live. Wrap ≠ overflow: here count never exceeded $N$ while overwriting, so no data lost. All four correct.

Example 6 — Speculative mis-predict, then restore (cell C6)

Forecast: back to exactly TOS=2, count=2, holes 0,1 = $p, q$ — as if the speculation never happened.

Snapshot (TOS=2, count=2) at the speculative branch. Why? We may have to undo everything downstream if the branch was wrong.
Speculative push $s$ (into $RAS_{spec}$ ) → slot[2]=s, TOS: 2→3, count=3. Why traced? Speculation modifies the speculative RAS eagerly for prediction speed.
Speculative pop → TOS: 3→2, read slot[2]=s, count=2. Why this step? The speculative path contained a RET, and while we are guessing we must feed the front end some target — so the eager RAS dutifully pops its most recent entry ( $s$ ) and predicts it. This pop is only as trustworthy as the guess that led here; if the guess was wrong, this popped target was wrong too.
Flush — restore both fields from the snapshot: TOS ← 2, count ← 2. Formally $RAS_{spec} \leftarrow RAS_{committed} [snapshot]$ . Why restore BOTH? Restoring only TOS would leave count desynced; restoring only count would leave the arrow pointing at the wrong hole. The pair (TOS, count) is the complete stack identity.

Verify: post-flush (TOS, count) = (2, 2), identical to the snapshot. The stray s in slot[2] is now above the count line, so it is dead — the guard will never hand it out. Speculation left no trace. This is why RAS checkpointing stores the pointer+counter pair, not the slot contents.

Example 7 — Wrong tool: a non-return indirect branch (cell C7)

Worked example Ex 7 — a

switch jump must NOT use the RAS

switch (x) { case 0: goto L0; case 1: goto L1; }

This compiles to an indirect jump through a table — one PC, many data-dependent targets. Suppose someone wrongly wired this jump to pop the RAS as if it were a RET. Current RAS: count=1, TOS=1, top = $r$ in slot[0] (a genuine return address a real caller is still waiting on). Say x = 1, so the true target is L1. Forecast the damage.

Forecast: double disaster — the switch is mis-predicted and the RAS is corrupted for the real return later.

Switch executes, wrongly pops. TOS: 1→0, read slot[0]=r, count: 1→0, predicted target = $r$ . Why is this wrong? $r$ is a return address; the switch needs L0 or L1 chosen by the data value x, which has nothing to do with call/return nesting. The RAS answers the wrong question here.
True target computed → L1. Why a flush now? The predicted $r \neq = L 1$ , so the front end fetched down the wrong path and must squash it — one pipeline flush penalty. Why did the mistake even reach here? Because the RAS was consulted for a branch whose target is data-dependent, not stack-structured.
Later the real RET arrives expecting $r$ — but step 1 already popped it, so now count=0. Why a second penalty? The pop consumed the legitimate return address early, so the real RET hits the underflow case (cell C4): no live entry → no-prediction/mispredict. One misuse thus caused two mispredicts.

The fix: route switch/function-pointer/virtual-call targets to the indirect branch predictor or BTB; reserve the RAS for architectural CALL/RET only. Why? Those predictors key on branch history and data patterns — the right question for a data-dependent jump — whereas the RAS keys purely on LIFO nesting.

Verify: two mispredicts from one misuse — proof that RAS is a specialized predictor, not a general one. It answers exactly one question ("where does this return go?"), and using it elsewhere breaks both the misused branch and a future legitimate return.

Example 8 — Real-world word problem (cell C8)

Forecast: count the arrows.

List every call still open at the bottom of the chain. Each → is one CALL whose RET hasn't fired yet. Why? Max live count = maximum nesting depth reached, because every unreturned call keeps one live entry on the ring.
Count the arrows: main→server_loop→handle_request→parse_http→route→controller→db_query→malloc→memcpy has 9 named functions and therefore 8 arrows = 8 open calls. So peak count = 8. Why $9 - 1$ ? $k$ functions in a linear chain are joined by $k - 1$ call transitions.
Compare to $N = 8$ . Peak demand 8 exactly equals depth 8 → the ring is full but not overflowing (count = N, no eviction); memcpy's return still fits. Why the razor's edge matters? Any one more nested call (e.g. memcpy calls a helper) would push at count = N, evicting main's return → a mispredict on the outermost return.

Verify: 8 transitions between 9 named functions ( $9 - 1 = 8$ ). $N = 8 \geq 8$ ⇒ exactly sufficient, zero margin. A safer design picks $N = 16$ (the parent's recommendation) to absorb library depth without eviction — matching the "16 entries ≈ 97%" data point.

Example 9 — Exam twist: expected accuracy from depth (cell C9)

For $N = 8$ : correct = returns needing ≤8 = $70$ . Why sum these two bands? Both the ≤4 and 5–8 bands fit within 8 entries, so their returns are never evicted and always predict correctly.
Wrong for $N = 8$ : the 9–16 band (8%) and >16 band (2%) exceed the ring → $10$ mispredict. Hit-rate $= 90$ . Why do these miss? Their required depth is larger than $N = 8$ , so the outermost entries get evicted before their returns arrive.
For $N = 16$ : correct = ≤16 bands = $70$ ; only the >16 band (2%) misses. Hit-rate $= 98$ . Why the jump? Enlarging the ring to 16 rescues the entire 9–16 band that used to overflow.

Verify: $70 + 20 = 90$ and $70 + 20 + 8 = 98$ . These land on the parent's quoted curve (8 entries ≈ 92%, 16 entries ≈ 97%) — close, since our clean model omits speculative and mismatched-call effects that shave a couple of points off in real silicon.

Recall Quick self-test

A RET is popped while count = 0. What must a correct RAS output? ::: "No prediction" — the count guard refuses the pop and TOS is not decremented, avoiding a garbage target. On overflow (push at count = N), which entry is lost and which is written? ::: The oldest live entry (at the current TOS slot) is overwritten by the new return address; count saturates at $N$ . After a speculative branch flush, which two fields are restored from the snapshot? ::: Both TOS and count — together they define the stack; restoring one alone desyncs the ring. Why can a switch statement not use the RAS? ::: Its targets are data-dependent, not LIFO-nested; popping corrupts a real return address and mispredicts the switch itself.

See also: Branch Prediction Basics · Branch Target Buffer · Indirect Branch Prediction · Speculative Execution · Pipeline Hazards · Call Stack · Instruction Fetch