Return address stack: Worked examples — Hinglish deep dive

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

Yeh Return Address Stack (RAS) ka ek worked-examples deep dive hai. Parent note ne machine banai thi: ek chhota sa hardware stack jo har CALL par ek return address push karta hai aur har RET par pop karta hai. Yahan hum us machine ko har us situation se guzarenge jo wo face kar sakti hai aur dekhenge ki har control field ek cycle at a time kya karta hai.

Koi bhi example shuru karne se pehle, un teen numbers ko dobara samjhte hain jo RAS carry karta hai, kyunki neeche har scenario asal mein ek story hai ki ye teen kaise change hote hain.

Scenario matrix

Har woh situation jo RAS face kar sakta hai unhi cells mein se ek hai. Neeche ke examples us cell ke saath tagged hain jo wo cover karte hain, aur mil ke sab ko cover karte hain.

#	Cell (case class)	Ise kya alag banata hai	Covered by
C1	Balanced call/return, no wrap	`count` kabhi $N$ tak nahi pahunchta; textbook LIFO	Ex 1
C2	Interleaved deep + shallow nesting	Multiple pushes phir partial pops phir aur pushes	Ex 2
C3	Overflow (push jab `count = N`)	Oldest live entry evict hoti hai; count saturate hoti hai	Ex 3
C4	Underflow (pop jab `count = 0`)	Degenerate: no-prediction return karna hoga	Ex 4
C5	TOS pointer ka wrap-around	TOS $N - 1 \to 0$ seam cross karta hai jab count healthy ho	Ex 5
C6	Speculation mis-predict → restore	(TOS, count) ka snapshot flush par roll back hota hai	Ex 6
C7	Wrong tool (non-return indirect branch)	RAS ko fire nahi karna chahiye; degenerate misuse	Ex 7
C8	Real-world word problem	Ek C call chain ko RAS depth demand mein convert karo	Ex 8
C9	Exam twist: accuracy from depth	Ek workload ke liye expected hit-rate compute karo	Ex 9

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

Forecast: teen pops reverse order mein → 0x3004, phir 0x2004, phir 0x1004.

Figure 1 neeche same $N = 4$ ring ka teen-panel filmstrip hai. Left panel: teeno pushes ke baad, holes 0,1,2 green (live) hain aur 0x1004,0x2004,0x3004 hold kar rahe hain, aur yellow TOS arrow hole 3 par baithe hai (agla free hole), count=3. Middle panel: pehle pop ke baad, hole 2 dim (dead) ho gaya hai aur arrow peeche us par aa gaya hai — popped value 0x3004 wahin se aayi, count=2. Right panel: sab holes dim, arrow wapas hole 0 par, count=0 — ring empty hai. Dekho yellow arrow push par chadhta hai aur pop par utarta hai; dekho green dim hota jaata hai jab count girta hai.

Push 0x1004 (main ke call ke baad return point). Yeh step kyun? Har CALL record karta hai ki control ko wapas kahan aana hai, jo hai $P C_{call} + size_{call} = 0x1000 + 4 = 0x1004$ . Ab slot[0]=0x1004, TOS=1, count=1.
Push 0x2004. Kyun? Nested call — ring ko foo ki continuation bhi yaad rakhni hai. slot[1]=0x2004, TOS=2, count=2.
Push 0x3004. Kyun? Sabse gehri call. slot[2]=0x3004, TOS=3, count=3. (Yeh Figure 1 ka left panel hai.)
baz RET → pop. Kyun? LIFO: sabse recent pusher (bar ne baz ko call kiya) pehle answer hota hai. TOS: 3→2, read slot[2]=0x3004, count=2. ✔ predicted 0x3004. (Middle panel.)
bar RET → pop. Kyun? Next-most-recent open call aage answer hota hai. TOS: 2→1, read slot[1]=0x2004, count=1. ✔ 0x2004.
foo RET → pop. Kyun? Sabse purana remaining open call last mein answer hota hai. TOS: 1→0, read slot[0]=0x1004, count=0. ✔ 0x1004. Ring dobara empty (right panel).

Verify: har popped value setup mein print kiye return point ke barabar hai; count exactly $0$ par wapas aaya (utne hi pops jitne pushes). Teeno predictions sahi → in returns ke liye zero pipeline flushes.

Example 2 — Interleaved nesting (cell C2)

Forecast: r2, phir r3, phir r1.

push r1 → slot[0]=r1, TOS=1, count=1. Kyun? Pehli call.
push r2 → slot[1]=r2, TOS=2, count=2. Kyun? Pehli ke andar nested call.
POP → TOS:2→1, read slot[1]=r2, count=1. ✔ r2. Kyun? Inner function pehle return hua.
push r3 → slot[1]=r3 (freed hole reuse karta hai!), TOS=2, count=2. Yeh step kyun? r2 se khali hua hole ab free real estate hai — ek naya sibling call use reuse karta hai. slot[0] mein r1 untouched hai.
POP → TOS:2→1, read slot[1]=r3, count=1. ✔ r3. Kyun? Sabse recent live push r3 thi (sibling call), toh LIFO pehle usse answer karta hai — chahe physically woh same hole use kare jo r2 ne pehle use kiya tha.
POP → TOS:1→0, read slot[0]=r1, count=0. ✔ r1. Empty. Kyun? Sirf r1 (original outer call) abhi bhi open hai, toh woh last mein pop hota hai aur ring count=0 par drain ho jaati hai.

Verify: interleaving ne kabhi r1 ko bottom par disturb nahi kiya — woh patiently wait kiya aur last mein pop hua, exactly jaisa LIFO promise karta hai. Reused slot prove karta hai ki ring space recycle karta hai bina corruption ke jab count honor kiya jaata hai.

Example 3 — Overflow (cell C3)

Forecast: last return (A ki taraf) mis-predict karega, kyunki $r_{A}$ evict ho gaya.

Figure 2 neeche eviction ki teen-panel story hai. Left panel: chaar pushes ke baad ring completely green hai (count = N = 4) aur rA,rB,rC,rD hold kar rahi hai, aur yellow TOS arrow wrap karke wapas hole 0 par aa gaya hai. Middle panel: paanchwa push rE hole 0 mein rA ke upar likhta hai (overwrite flag karne ke liye red dikhaya gaya hai); count 4 par pinned rehta hai. Right panel: sab pop hone ke baad sab holes dim hain aur count=0 hai, aur ek red marker dikhata hai A ka return kuch bhi live nahi paata — mispredict. Teaching point: red hole 0 = sacrifice kiya hua oldest entry.

push $r_{A}, r_{B}, r_{C}, r_{D}$ → holes $0, 1, 2, 3$ fill hote hain; 4th push ke baad TOS: 3→0 (wraps $(3 + 1) mod 4 = 0$ se), count=4 = $N$ . Kyun? Chaar pushes ring bilkul fill kar dete hain; TOS wapas hole 0 par land karta hai. (Figure 2 ka left panel.)
push $r_{E}$ → slot[0] \leftarrow r_E $r_{A}$ ko overwrite karta hai, phir TOS: 0→1, count = min(4+1,4)=4. Yeh step kyun? Ring full hai. min(count+1,N) rule count cap karta hai jabki TOS aage badhta rehta hai, toh oldest live entry (hole 0 = $r_{A}$ ) silently sacrifice ho jaati hai. Yeh eviction overflow par intended hai. (Middle panel.)
pop (E ret) → TOS: 1→0 ( $(1 - 1) mod 4$ se), read slot[0]=r_E, count=3. ✔ $r_{E}$ . Arrow 0 par wapas kyun jaata hai? Pop always TOS ko ek hole backward step karta hai sabse recently-written live slot tak pahunchne ke liye.
pop (D ret) → TOS: 0→3 ( $(0 - 1) mod 4 = 3$ se wrap), read slot[3]=r_D, count=2. ✔ $r_{D}$ . Kyun? $0 \to 3$ seam crossing normal ring arithmetic hai; count=3>0 ne slot live prove kiya.
pop (C ret) → TOS: 3→2, read slot[2]=r_C, count=1. ✔ $r_{C}$ . Kyun? Live entries se neeche step karte rehna.
pop (B ret) → TOS: 2→1, read slot[1]=r_B, count=0. ✔ $r_{B}$ . Kyun? Last live entry consume hoti hai; count 0 hit karta hai.
pop (A ret) → count already $0$ hai, toh TOS move nahi hota. Yeh kyun matter karta hai? Referee block karta hai: A ke liye koi live entry exist nahi karti. Prediction = no-prediction / mis-predict → ek fetch redirect penalty. (Figure 2 ka right panel.)

Verify: exactly ek mis-prediction, aur woh A ka return hai (evicted wala). Chaar sahi, ek galat. Push count 5 > $N = 4$ ⇒ overflow guaranteed ek loss.

Example 4 — Underflow (degenerate) (cell C4)

Forecast: "no prediction" — garbage nahi.

Fetch RET, pop attempt. Pehle check kyun? max(count-1, 0) guard aur count==0 test precisely isi moment ke liye exist karte hain.
Count read karo. count = 0. Kyun? Kuch bhi push nahi hua tha.
Pop refuse karo. TOS decremented nahi hota; count $max (0 - 1, 0) = 0$ se $0$ par clamped rehta hai. Output = no valid target. Kyun? Ek badhiya $(TOS - 1) mod N$ hole $N - 1$ par step kar jaata aur jo bhi ancient bits waahan hote woh de deta — ek spurious prediction jo stale data point karta.

Verify: guard ke saath, front end BTB par fallback karta hai ya stall karta hai instead of random address se fetch karne ke. Guard ke bina: (0-1) mod 8 = 7, toh slot[7] read karta — pure garbage. Guard ek galat prediction ko ek honest "I don't know" mein convert karta hai.

Example 5 — TOS ka wrap-around with healthy count (cell C5)

Forecast: w, z, y, x.

push $z$ → slot[0]=z, TOS: 0→1, count=3. Kyun? Next-write hole 0 hai (jahan arrow point kar raha hai), toh naya return address waahan land karta hai aur arrow aage badhta hai.
push $w$ → slot[1]=w, TOS: 1→2, count=4. Yeh step kyun? Hole 1 bhi empty tha, toh w last free hole fill karta hai; count $N = 4$ tak pahuncha hai bina kisi overwrite ke — har push genuinely empty hole mein gaya, toh yeh full-but-not-overflowing ring hai.
pop → TOS: 2→1, read slot[1]=w, count=3. ✔ w. Kyun? w sabse recently pushed live entry thi, toh LIFO pehle usse answer karta hai; arrow usse read karne ke liye hole 1 par wapas step karta hai.
pop → TOS: 1→0, read slot[0]=z, count=2. ✔ z. Kyun? Next-most-recent live push z thi hole 0 mein; arrow ek aur hole peeche step karta hai.
pop → TOS: 0→3 (seam ke across wrap $0 \to N - 1$ via $(0 - 1) mod 4 = 3$ ), read slot[3]=y, count=1. ✔ y. Yeh step kyun? Do newest entries chali gayi hain, toh next live wali y hai hole 3 mein — arrow ko hole 0 se wapas hole 3 par roll karke pahuncha, koi special case nahi.
pop → TOS: 3→2, read slot[2]=x, count=0. ✔ x. Kyun? Sirf x (sabse purani live entry) bachi hai; woh last mein pop hoti hai aur ring count=0 par drain ho jaati hai.

Verify: seam crossing (0 → 3) transparent hai kyunki count (us waqt 2) ne entry live prove ki. Wrap ≠ overflow: yahan count kabhi $N$ se zyada nahi hua jabki overwrite kiya, toh koi data loss nahi. Charon sahi.

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

Forecast: exactly TOS=2, count=2, holes 0,1 = $p, q$ par wapas — jaisa speculation kabhi hua hi nahi.

Snapshot (TOS=2, count=2) speculative branch par. Kyun? Agar branch galat nikla toh hume sab kuch downstream undo karna padega.
Speculative push $s$ ( $RAS_{spec}$ mein) → slot[2]=s, TOS: 2→3, count=3. Kyun trace kiya? Speculation prediction speed ke liye speculative RAS eagerly modify karta hai.
Speculative pop → TOS: 3→2, read slot[2]=s, count=2. Yeh step kyun? Speculative path mein ek RET thi, aur jab hum guess kar rahe hain to front end ko koi target dena hota hai — toh eager RAS dutifully apni most recent entry ( $s$ ) pop karta hai aur usse predict karta hai. Yeh pop utna hi trustworthy hai jitna woh guess jo yahan tak le aaya; agar guess galat tha, toh yeh popped target bhi galat tha.
Flush — dono fields snapshot se restore karo: TOS ← 2, count ← 2. Formally $RAS_{spec} \leftarrow RAS_{committed} [snapshot]$ . DONO kyun restore karo? Sirf TOS restore karne se count desync ho jaata; sirf count restore karne se arrow galat hole point karta. Pair (TOS, count) complete stack identity hai.

Verify: post-flush (TOS, count) = (2, 2), snapshot ke identical. slot[2] mein stray s ab count line ke upar hai, toh woh dead hai — guard usse kabhi hand out nahi karega. Speculation ne koi trace nahi chhoda. Isliye RAS checkpointing pointer+counter pair store karta hai, slot contents nahi.

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

Worked example Ex 7 — ek

switch jump RAS use nahi karna chahiye

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

Yeh ek table ke through ek indirect jump mein compile hota hai — ek PC, bahut saare data-dependent targets. Maan lo kisine galti se is jump ko RAS se pop karne ke liye wire kiya jaisa ki woh ek RET ho. Current RAS: count=1, TOS=1, top = $r$ slot[0] mein (ek genuine return address jo ek real caller abhi bhi wait kar raha hai). Maan lo x = 1, toh true target L1 hai. Damage forecast karo.

Forecast: double disaster — switch mis-predict hoga aur baad ki real return ke liye RAS corrupt ho jaayegi.

Switch execute hoti hai, galti se pop karta hai. TOS: 1→0, read slot[0]=r, count: 1→0, predicted target = $r$ . Yeh galat kyun hai? $r$ ek return address hai; switch ko L0 ya L1 chahiye data value x se chosen, jo call/return nesting se kuch bhi lena dena nahi rakhta. RAS yahan galat sawaal ka jawab de raha hai.
True target compute hua → L1. Ab flush kyun? Predicted $r \neq = L 1$ , toh front end galat path par fetch ho gaya aur use squash karna hoga — ek pipeline flush penalty. Galti yahan tak pahunchi hi kyun? Kyunki RAS ko ek aisa branch ke liye consult kiya gaya jiska target data-dependent hai, stack-structured nahi.
Baad mein real RET aati hai $r$ expect karte hue — lekin step 1 ne use already pop kar liya, ab count=0 hai. Doosra penalty kyun? Pop ne legitimate return address pehle consume kar li, toh real RET underflow case (cell C4) hit karti hai: koi live entry nahi → no-prediction/mispredict. Ek misuse se do mispredicts aaye.

Fix: switch/function-pointer/virtual-call targets ko indirect branch predictor ya BTB ko route karo; RAS sirf architectural CALL/RET ke liye reserve karo. Kyun? Woh predictors branch history aur data patterns par key karte hain — data-dependent jump ke liye sahi sawaal — jabki RAS purely LIFO nesting par key karta hai.

Verify: ek misuse se do mispredicts — proof ki RAS ek specialized predictor hai, general nahi. Yeh exactly ek sawaal answer karta hai ("yeh return kahan jaata hai?"), aur kahin aur use karne se misused branch aur ek future legitimate return dono toot jaate hain.

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

Forecast: arrows gino.

Chain ke bottom par har open call list karo. Har → ek CALL hai jiska RET abhi fire nahi hua hai. Kyun? Max live count = maximum nesting depth reached, kyunki har unreturned call ring par ek live entry rakhta hai.
Arrows gino: main→server_loop→handle_request→parse_http→route→controller→db_query→malloc→memcpy mein 9 named functions hain aur isliye 8 arrows = 8 open calls. Toh peak count = 8. $9 - 1$ kyun? $k$ functions ki ek linear chain $k - 1$ call transitions se judi hoti hai.
$N = 8$ se compare karo. Peak demand 8 exactly depth 8 ke barabar hai → ring full hai lekin overflow nahi (count = N, koi eviction nahi); memcpy ka return abhi bhi fit hota hai. Razor's edge matter kyun karta hai? Ek aur nested call (jaise memcpy ek helper call kare) count = N par push karega, main ka return evict karega → outermost return par mispredict.

Verify: 9 named functions ke beech 8 transitions ( $9 - 1 = 8$ ). $N = 8 \geq 8$ ⇒ exactly sufficient, zero margin. Ek safer design $N = 16$ choose karta hai (parent ki recommendation) library depth absorb karne ke liye bina eviction ke — "16 entries ≈ 97%" data point se match karta hai.

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

$N = 8$ ke liye: correct = returns jo ≤8 chahiye = $70$ . Yeh do bands sum kyun? ≤4 aur 5–8 dono bands 8 entries ke andar fit hoti hain, toh unke returns kabhi evict nahi hote aur hamesha correctly predict hote hain.
$N = 8$ ke liye galat: 9–16 band (8%) aur >16 band (2%) ring se zyada hain → $10$ mispredict. Hit-rate $= 90$ . Yeh miss kyun karte hain? Unki required depth $N = 8$ se zyada hai, toh outermost entries unki returns aane se pehle evict ho jaati hain.
$N = 16$ ke liye: correct = ≤16 bands = $70$ ; sirf >16 band (2%) miss karta hai. Hit-rate $= 98$ . Yeh jump kyun? Ring ko 16 tak enlarge karna poora 9–16 band rescue karta hai jo pehle overflow karta tha.

Verify: $70 + 20 = 90$ aur $70 + 20 + 8 = 98$ . Yeh parent ke quoted curve par land karte hain (8 entries ≈ 92%, 16 entries ≈ 97%) — close, kyunki hamara clean model speculative aur mismatched-call effects omit karta hai jo real silicon mein couple of points shave karte hain.

Recall Quick self-test

Ek RET pop hoti hai jab count = 0 ho. Ek correct RAS kya output karna chahiye? ::: "No prediction" — count guard pop refuse karta hai aur TOS decremented nahi hota, garbage target se bachata hai. Overflow par (push at count = N), kaun si entry lost hoti hai aur kaun si likhti hai? ::: Sabse purani live entry (current TOS slot par) naye return address se overwrite hoti hai; count $N$ par saturate hoti hai. Ek speculative branch flush ke baad, snapshot se kaun se do fields restore hote hain? ::: TOS aur count dono — saath mein woh stack define karte hain; ek akele restore karna ring ko desync karta hai. Ek switch statement RAS use kyun nahi kar sakta? ::: Uske targets data-dependent hain, LIFO-nested nahi; pop karna ek real return address corrupt karta hai aur switch khud bhi mispredict hota hai.

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