5.3.12 · D5Advanced Microarchitecture
Question bank — Return address stack
This page is a question bank. Each line is a Question ::: Answer reveal. Cover the right side, say your answer out loud with a reason, then check. If your reason is wrong even when your yes/no is right, you don't understand it yet.
Before we start, three plain-word reminders so no symbol is used before it is anchored:
Recall The three moving parts (say them before you answer anything)
- RAS = a tiny hardware stack of return addresses. Think of a stack of plates: you can only touch the top plate.
- TOS = "Top-Of-Stack" pointer — it points at the top plate (the one you'd grab next).
- count = how many plates are actually on the stack right now (0 = empty, = full, where is the number of slots). A CALL pushes one plate (the address to come back to). A RETURN grabs and removes the top plate to know where to jump. This is the parent note in one breath.
True or false — justify
Every answer must give the reason, never a bare "true/false".
A RAS predicts the target of a return instruction, not whether the return is taken.
True — a return is (almost) always taken, so the hard question is "jump to where?"; the RAS answers that, while direction prediction handles taken/not-taken for conditional branches.
A BTB alone could predict returns just as well as a RAS.
False — one return instruction (same PC) returns to many callers over time; a BTB stores one target per PC, so it keeps mispredicting as the caller changes, while the RAS tracks the LIFO nesting instead.
The RAS mirrors the software call stack's return addresses exactly and forever.
False — it mirrors only the most recent return addresses; when the real call depth exceeds , the oldest RAS entries are evicted even though the software stack still holds them.
A RAS with more entries always gives strictly better accuracy on every program.
False in the strict sense — beyond the deepest call chain a program ever reaches, extra entries sit unused; more depth helps only programs whose nesting would otherwise overflow the smaller RAS.
Pushing on a CALL and popping on a RET is enough; a plain mod N pointer needs no extra guard.
False — a bare
mod N pointer underflows silently on a pop-when-empty and hands back stale garbage as a "prediction"; you need an occupancy count (or valid bits) to say "no prediction" instead.The RAS is only useful for recursive programs.
False — ordinary non-recursive call chains (
main → init → parse → open → check) already stack several return addresses; recursion just makes it easier to overflow, but the RAS earns its keep on flat call trees too.If the RAS is empty and a RET is fetched, the safest behaviour is to pop anyway and use whatever the slot holds.
False — popping an empty RAS yields stale data and a near-certain misprediction; the correct behaviour is to signal "no prediction" and fall back to the BTB or stall.
Overflowing the RAS corrupts the currently-returning function immediately.
False — overflow evicts the oldest entry (the outermost caller); the inner returns still predict correctly, and the misprediction only surfaces later when you try to return to the evicted outer frame.
Spot the error
Each item states a claim with a hidden flaw. Name the flaw.
"On a CALL we push the address of the CALL instruction itself."
Wrong — we push , the address of the next instruction; returning to the CALL itself would re-execute the call forever.
"A return pops the bottom of the stack because that's the original caller."
Wrong — a return pops the top (most recent) entry; LIFO means the innermost, latest call is matched first, which is exactly how nested calls unwind.
"The occupancy counter goes up on a pop and down on a push."
Backwards — push adds a plate (count up, capped at ), pop removes one (count down, floored at 0).
"We should use the RAS for a C switch jump table because it's an indirect branch."
Wrong — a
switch target depends on data (x), not on call/return nesting, so it breaks LIFO; that belongs to Indirect Branch Prediction, not the RAS."On a pipeline flush we just clear the RAS to empty and continue."
Wrong — clearing loses correct outer-frame addresses; you must restore the RAS (TOS and count) to the snapshot taken before the mispredicted call, part of speculative recovery.
"An indirect jmp through a function pointer should push onto the RAS."
Wrong — only architectural CALL/RET pairs interact with the RAS; a lone indirect jump has no matching return, so pushing it desynchronises the stack from the real call nesting.
"When the RAS is full, the next push is simply ignored to protect old data."
Wrong — the push is not ignored; TOS still advances and overwrites the oldest slot (intended eviction). Ignoring it would mispredict the inner returns instead of just the outermost.
Why questions
The answers here are the reasoning, not a fact.
Why is a stack (LIFO), not a queue (FIFO), the correct structure for returns?
Because program semantics force returns to happen in reverse order of calls — the last function called is the first to return — so the most-recently-pushed address must be the first popped, which is exactly LIFO.
Why do returns need special treatment at all, when they're just indirect jumps?
Because the same return PC maps to many targets over a program's life (one per caller); ordinary indirect predictors key on the PC and see conflicting targets, whereas the RAS keys on nesting order and sees exactly one right answer.
Why does the occupancy counter saturate at instead of continuing to climb?
Because there are only physical slots; letting count exceed would falsely permit more pops than there are live entries, so it caps at (the wrap already evicted the oldest slot).
Why keep two RASs — a committed one and a speculative one?
Because fetch runs ahead speculatively and may push/pop for calls that never really execute; the committed copy preserves the true architectural state so a flush can restore the speculative copy without corruption.
Why does a 32-entry RAS give near-perfect accuracy despite being tiny?
Because real programs rarely nest deeper than ~16 live frames at once, so 32 slots almost never overflow — the misprediction cost is paid only in rare deep chains or unbalanced recursion.
Why is overflow "graceful" but underflow "dangerous"?
Overflow overwrites the oldest slot — a known, bounded loss that only hurts far-off outer returns; underflow reads a slot that was never written — an unknown garbage target — so the guard treats it as no-prediction.
Why does deep recursion stress the RAS more than an equally long flat call chain?
Both consume depth, but recursion can nest hundreds of frames without any intervening return, quickly exceeding and evicting the base frames whose returns then all mispredict.
Edge cases
Boundary conditions the topic quietly invites.
Call depth exactly equals (RAS full, no overflow yet).
All entries are live, count ; every return still predicts perfectly. The next push is the one that evicts the oldest — being exactly full is fine.
A RET arrives when count .
Underflow: no valid entry exists, so the RAS reports "no prediction"; control falls back to the BTB or the pipeline stalls until the real target is computed.
Tail call / setjmp-longjmp style control flow that returns without a matching CALL.
The RAS desynchronises because a pop has no corresponding push; predictions after that point drift wrong until the stack happens to realign — such patterns are a known RAS-accuracy killer.
A call and its return live entirely on a mispredicted (wrong) speculative path.
The speculative RAS did a push then a pop that never architecturally happened; on flush the speculative RAS is rolled back to the pre-call snapshot, undoing both, so committed state stays clean.
Overflow then a matching number of returns: does the RAS "recover"?
Partly — the evicted outermost entry is gone for good, so its return mispredicts, but every inner return that still has a live slot predicts correctly; the stack self-heals for depths that never overflowed.
Two consecutive CALLs with no instruction between (chained trampolines).
Each CALL still pushes its own ; the RAS just sees two pushes back-to-back, count rises by two, and the LIFO order is preserved — nothing special breaks.