Return address stack: Exercises — Hinglish deep dive

5.3.12 · D4 · Hardware › Advanced Microarchitecture › Return address stack

Yeh page Return Address Stack ke liye ek self-test ladder hai. Har problem ka setup clearly diya gaya hai, phir ek collapsible Solution callout ke andar pura worked solution chhupa hua hai — problem padho, khud try karo, tab reveal karo.

Shuru karne se pehle, ek shared vocabulary reminder taaki koi bhi symbol bina samjhe use na ho:

Definition Woh paanch words jo neeche har exercise mein use honge

RAS — ek chhota sa hardware Last-In-First-Out stack jo guess karta hai ki ek RET (return) instruction kahaan jump karega. Dekho parent note.
Push — ek return address ko RAS ke top par write karna. Predicted CALL par hota hai.
Pop — top address ko remove karke use karna predicted jump target ke roop mein. Predicted RET par hota hai.
TOS (Top-Of-Stack) — ek pointer jo currently top par wale slot ko point karta hai; yeh $N$ slots ke circular buffer par chalta hai.
count — ek alag counter jo batata hai ki RAS mein kitne live entries hain, $0 \leq count \leq N$ . Yahi cheez hame garbage pop karne se rokti hai.

"Return address" simply woh byte address hai jo instruction ke theek baad CALL ke, yaani $P C_{call} + size_{call}$ — yahi woh jagah hai jahan execution resume karni chahiye jab callee done ho jaaye.

Level 1 — Recognition

Exercise 1.1

In instruction types mein se kaunse RAS ko update karni chahiye, aur kis direction mein (push / pop / nothing)? CALL, RET, ADD, JMP (unconditional direct jump), indirect switch jump.

Recall Solution

CALL → push (future matching return ke liye return address write karta hai).
RET → pop (predicted target wapas padhta hai).
ADD → nothing (yeh control-flow instruction nahi hai).
JMP (direct) → RAS ke liye nothing; iska target fixed hai aur decode par pata hota hai, stack ki zaroorat nahi.
switch indirect jump → RAS mein nothing; yeh ek data-dependent target hai jo Branch Target Buffer / Indirect Branch Prediction se handle hota hai, nahi LIFO se.

Ek aasaan litmus test: kya yeh instruction call/return nesting follow karta hai? Sirf CALL/RET karte hain.

Exercise 1.2

Ek RAS mein $N = 8$ slots hain. Maximum number of return addresses jo yeh hold kar sakta hai batao, aur count kya equal hoga jab yeh empty ho vs. full ho.

Recall Solution

Maximum live entries $= N = 8$ .
Empty: $count = 0$ . Full: $count = 8$ .
Dhyan do ki circular buffer mein hamesha 8 physical slots hote hain; count — na ki slot count — batata hai ki kitne valid hain.

Level 2 — Application

Exercise 2.1

Is code ko 4-byte instructions aur empty RAS ( $N = 8$ ) ke saath dekho, har control-flow event ke baad RAS contents list karo (bottom→top).

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

Recall Solution

$P C$ par CALL ke liye return address $P C + 4$ hai.

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

Dono returns sahi predict hue. Dhyan do ki pehle RET ne sabse recent push (0x2004) pop kiya — yahi LIFO hai jo exactly wahi kar raha hai jo call nesting maangti hai.

Exercise 2.2

Ek CALL 0x8040 par hai aur call instruction 6 bytes lambi hai. Kaunsa return address push hoga?

Recall Solution

$P C_{call} + size_{call} = 0x8040 + 6 = 0x8046 .$ Size matter karti hai: har ISA 4-byte instructions use nahi karta, isliye hamesha actual byte length add karo.

Level 3 — Analysis

Exercise 3.1 (Overflow)

RAS depth $N = 4$ , initially empty. Program 5 nested calls karta hai phir unwind karta hai: A→B→C→D→E→F, phir F,E,D,C,B sab order mein return karte hain. Kaunsa return, agar koi, mispredict hota hai, aur kyun?

Recall Solution

Pushed return addresses ko ret_A..ret_E label karo (har call par ek).

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 evict hua
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 ek misprediction: A ko final return. Jab 5th push hua tab oldest entry ret_A overwrite ho gayi. Overflow window ke andar nested sab kuch perfectly predict hota hai; sirf wahi entry lost hoti hai jo window se bahar push ho jaati hai. Correct returns ki count $= 4$ , mispredictions $= 1$ .

Exercise 3.2 (Underflow)

RAS empty ( $count = 0$ ). Program ek stray RET execute karta hai (jaise hand-written assembly stub, ya longjmp-style unwind) bina kisi matching CALL ke. Ek correctly-guarded RAS kya karta hai, aur ek buggy RAS jo bare mod N arithmetic use karta hai woh kya karta?

Recall Solution

Correct RAS: $count = 0$ , toh pop illegal hai. Yeh "no prediction" return karta hai aur Branch Target Buffer par defer karta hai. count $0$ par clamped rehta hai $max (count - 1, 0)$ ke zariye.
Buggy bare-mod RAS: $TOS \leftarrow (0 - 1) mod N = N - 1$ . Yeh slot $N - 1$ padhta hai, jisme kisi earlier program phase ke stale leftover bits hain → ek garbage target → guaranteed pipeline flush, aur isse bhi bura, TOS ab "phantom" data mein point karta hai toh baad ke pushes/pops misaligned ho jaate hain.

Yahi wajah hai ki parent note count ko TOS se alag rakhta hai: TOS position handle karta hai, count validity handle karta hai.

Level 4 — Synthesis

Exercise 4.1 (Speculation + checkpoint)

Predictor speculatively CALL X fetch karta hai phir, wrong path par, RET. Baad mein CALL mispredicted nikla aur pipeline flush ho jaata hai. Describe karo ki RAS ko kya restore karna chahiye, aur kyun sirf TOS restore karna kaafi nahi hai.

Recall Solution

Wrong path par speculative RAS ne kiya: push (CALL X se) phir pop (RET se). Net TOS change zero hai, lekin contents disturb ho gaye — pop ne ek aisi entry consume kar li jisko correct path ko abhi bhi chahiye tha.

Recover karne ke liye, flush ek checkpoint se restore karta hai jo mispredicted CALL se pehle liya gaya tha: $RAS_{spec} \leftarrow snapshot (TOS, count, top entries) .$

Sirf TOS kaafi nahi: push-then-pop ke baad, TOS wapas wahi aa jaata hai jahan tha lekin top-of-stack data speculative push se overwrite ho sakta tha. Tumhe value aur count restore karna hoga, sirf pointer nahi.
Isliye real designs har speculative CALL par TOS aur count (aur aksar actual top entry bhi) snapshot karte hain. Dekho Speculative Execution.

Exercise 4.2 (Design tradeoff)

Neeche di gayi accuracy figures use karte hue, ek team $N = 4$ vs $N = 16$ debate kar rahi hai. Agar returns sab branches ka 12% hain aur har return misprediction 15-cycle flush cost karti hai, toh 1000 branches per $N = 4$ use karne se $N = 16$ ki jagah extra cycles calculate karo.

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

Recall Solution

1000 branches per returns: $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$ .

$N = 4$ choose karne se extra mispredictions: $18 - 3.6 = 14.4$ . Extra cycles: $14.4 \times 15 = 216$ cycles per 1000 branches.

Yeh ek bada, aasaani se hatane wala penalty hai — yahi asli wajah hai ki production chips 16–32 entry RAS ship karte hain.

Level 5 — Mastery

Exercise 5.1 (Full trace with overflow + speculation)

$N = 2$ . Is sequence ko trace karo aur har predicted target aur har misprediction report karo:

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$ , toh zyada se zyada 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 (R1 evict)	[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$ (baz ke caller aur bar ke caller ko returns). Mispredictions $= 1$ (foo ke caller ko return, kyunki R1 overflow se evict ho gaya tha). Final pop correctly "no prediction" report karta hai garbage ki jagah — count guard apna kaam kar raha hai.

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

Ek fixed PC par ek return instruction 4 alag call sites se call hoti hai, har ek equally likely. Ek single-target Branch Target Buffer entry sirf last seen target store karti hai. Is instruction ke liye BTB ki return prediction accuracy estimate karo, aur RAS se contrast karo.

Recall Solution

BTB ek PC par ek target record karta hai. 4 equally-likely, independently-arriving callers ke saath, stored target next actual target se sirf tab match karta hai jab next caller last caller ke barabar ho: $P (hit) = \frac{1}{4} = 25%.$ Toh $\approx 75%$ misprediction — realistic mixes ke liye parent note ke "30–50%+" se match karta hai aur yahan aur bhi bura.

RAS iske badle woh address pop karta hai jo is dynamic caller ke CALL ne push kiya tha, toh yeh sahi hota hai chahe 4 sites mein se koi bhi call kare — near- $100%$ (sirf depth/overflow se limited). Yahi core reason hai ki returns ko unka apna structure milta hai: ek PC, bahut se targets, lekin ek perfectly correlated LIFO signal jo BTB dekh hi nahi sakta. Dekho Indirect Branch Prediction.

Wrap-up recall

Answer chhupao, phir reveal karo.

Kaunsa structure return targets predict karta hai aur kyun LIFO?

Ek Return Address Stack; returns exact reverse order mein calls ko unwind karte hain, toh most-recent-push pehle-pop hona chahiye.

Size

s

aur address

P C

wale CALL par kya push hota hai?

P C + s

, call ke baad wala address.

Empty RAS se pop karne se kya bachaata hai?

count (occupancy) 0 tak pahunch jaata hai aur pop stale data ki jagah "no prediction" return karta hai.

Speculation ko TOS aur count (aur top value) dono snapshot kyun karni chahiye?

Wrong-path push-then-pop TOS ko unchanged chhod deta hai lekin contents corrupt kar deta hai; sirf ek full snapshot correctness restore karta hai.

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