Foundations — Return address stack

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

Isse pehle ki aap the Return Address Stack wala parent note padh sako, har woh symbol jo woh aap par phenkta hai, use zero se build karna padega. Yeh page wahi toolbox hai. Ise upar se neeche padho — har item uske upar wale par rely karta hai.

---

1. "Address" kya hota hai? (number 0x1000)

Parent note addresses ko 0x1000 jaisa likhta hai. Woh chhota 0x matlab hai "mere baad wala number hexadecimal (base-16) mein likha gaya hai" — na ki us base-10 mein jo aap roz use karte ho.

Base-16 kyun, base-10 kyun nahi? Kyunki computers bits ko 4 ke chunks mein group karte hain, aur ek hex digit = exactly 4 bits. Yeh hardware ke saath neatly line up hota hai. 0x1000 plain decimal mein $4096$ hai.

Picture mein memory ko numbered slots ka ek lamba column dikhaya gaya hai. Address simply yeh hai ki aap kis slot ko point kar rahe ho.

---

2. Program Counter, PC

Parent likhta hai $P{C}_{\text{call}}$ — iska matlab bas itna hai "woh address jahan ek particular CALL instruction rehti hai". Har instruction ka ek address hota hai, aur PC ek ungli hai jo unme se kisi ek ko point karti hai.

Is topic ko yeh kyun chahiye? Kyunki ek return ko ek specific address par wapas jump karna hota hai, aur woh address usi jagah ke relative compute hota hai jahan call thi — isliye hume "call kahan thi" ko naam dena aana chahiye, aur woh naam uska PC hai.

---

3. Instruction size, size / instruction_size

Toh return address yeh hai: $\text{return address}=P{C}_{\text{call}}+{\text{size}}_{\text{call}}$

Yahan ${\text{size}}_{\text{call}}$ (jo $\text{instruction\_size}$ bhi likha jaata hai) wo hai ki CALL instruction kitne bytes occupy karti hai. Ise CALL ke address mein add karne par aap exactly next instruction par pahunch jaate ho.

Figure mein amber arrow dekho: yeh CALL instruction ki width ke upar hop karta hai aur next slot par land karta hai. Parent ke Example 1 mein, CALL 0x1000 par baith hai aur next instruction 0x1004 par hai, toh size $4$ bytes hai.

---

4. CALL aur RETURN instructions

Yeh wahi do instructions hain jinki RAS ko parwah hai. Har CALL ek future promise create karti hai; har RET usse nibhaati hai. Yeh Call Stack relationship hai, hardware mein.

---

5. LIFO aur "stack" ka idea

Yahi sab kuch ka dil hai.

Plates ke stack ki soch lo. Aap plates upar se add karte ho aur upar se nikalte ho. Aap beech se plate kabhi nahi khenchte.

Calls aur returns ke liye yeh sahi shape kyun hai? Kyunki calls nest karti hain. Agar A, B ko call kare jo C ko call kare, toh:

• C ko B se pehle khatam hona chahiye,
• B ko A se pehle khatam hona chahiye.

Sabse last enter ki gayi function (C) pehli return karti hai. Yeh literally LIFO rule hai. Toh return addresses ka ek stack, calls ki nesting se zero mehnat mein match karta hai — yahi parent note ka "Proof that Stack is Optimal" hai.

Recall

Return prediction ke liye stack (LIFO) perfect structure kyun hai? ::: Kyunki functions reverse order mein return karte hain jis order mein unhe call kiya gaya tha — sabse recently called function pehle return karta hai, aur yahi "last push ki gayi cheez ko pop karo" wala rule deta hai.

---

6. Operations ke roop mein push() aur pop()

Shabd mein: ek CALL yaad rakhti hai kahan wapas aana hai (push), ek RET stack se poochhti hai kahan jaana hai (pop). Pop jo value wapas deta hai woh CPU ka guess hai return target ke liye — yeh ek prediction hai, jaldi ki gayi taaki pipeline stall na ho.

---

7. TOS — Top-Of-Stack pointer

Real hardware plates ka dher infinitely nahi badha sakta. Yeh $N$ slots ki ek fixed row use karta hai aur ek pointer jo kehta hai "upar yahan hai".

Figure $N$ slots ki row ko ek ring (circular buffer) mein bent dikhaata hai. Jab TOS last slot ke baad chala jaata hai, toh woh slot 0 par wrap around ho jaata hai — yahi hai jo $\mathrm{mod}N$ notation ka matlab hai aage.

---

8. Modulo operation, mod N

Topic ko yeh kyun chahiye? Pointer ko $N$ slots ki ring ke around wrap around karaane ke liye. Jab TOS last slot $N-1$ par ho aur aap push karo: ${\text{TOS}}_{\text{new}}=({\text{TOS}}_{\text{old}}+1)\mathrm{mod}N$ $0$ deta hai ek illegal slot $N$ ki jagah. Modulo ek seedhi row ko ek endless loop mein badal deta hai.

• Push: ${\text{TOS}}_{\text{new}}=({\text{TOS}}_{\text{old}}+1)\mathrm{mod}N$
• Pop: ${\text{TOS}}_{\text{new}}=({\text{TOS}}_{\text{old}}-1)\mathrm{mod}N$

---

9. Occupancy counter, count, aur min/max

Wrapping clever hai lekin dangerous: ek bare ring kabhi nahi jaanti ki woh empty hai ya full. Toh hum ek doosra chhota number rakhte hain.

$\min$ aur $\max$ woh guards hain jo count ko sensible rakhte hain: $\text{count}=\min (\text{count}+1,N)(\text{push, kabhi }N\text{ se zyada nahi})$ $\text{count}=\max (\text{count}-1,0)(\text{pop, kabhi }0\text{ se kam nahi})$

• $\min (a,b)$ = dono mein se chhota. Yeh count ko $N$ par cap karta hai taaki ek full stack full hi rahe.
• $\max (a,b)$ = dono mein se bada. Yeh count ko $0$ par floor karta hai taaki empty stack negative na ho jaaye.

Kyun bother karo? Empty stack (count == 0) par ek pop warna garbage stale data return karta. Counter hardware ko "no prediction" jawab dene deta hai. Yeh parent ka underflow guard hai.

Recall

count == 0 RAS ko RET par kya karne ko kehta hai? ::: Stack empty hai, toh stale garbage pop karne ki jagah "no prediction" report karna chahiye.

---

10. Neeche chupi do baatein: BTB aur speculation

Parent note RAS ka Branch Target Buffer (BTB) se comparison karta hai aur Speculative Execution ka zikr karta hai.

Dono connect karte hain is baat se ki returns kyun Indirect Branch Prediction ka ek special sub-problem hain aur kyun RAS early fetch ke liye Instruction Fetch ko ek target deta hai.

---

Prerequisite map

Har arrow ka matlab hai "target samajhne se pehle aapko source chahiye". Sab kuch Return Address Stack mein funnel ho jaata hai.

---

Equipment checklist

Khud ko test karo — sirf tab reveal karo jab aap zor se jawab de chuke ho.

• Kisi number ke aage 0x ka kya matlab hai? ::: Number hexadecimal (base-16) mein likha hai; ek hex digit 4 bits ke barabar hota hai.
• Program Counter kya hold karta hai? ::: Us instruction ka address jo CPU abhi execute kar raha hai.
• Ek function $PC$ aur size ke terms mein kahan return karta hai? ::: $P{C}_{\text{call}}+{\text{size}}_{\text{call}}$ par — CALL ke bilkul baad wali instruction par.
• LIFO rule ek sentence mein batao. ::: Jo item last push kiya gaya woh pehle pop hota hai.
• Call/return nesting ek stack se exactly kyun match karta hai? ::: Sabse recently called function pehle return karta hai, jo last-in-first-out ko mirror karta hai.
• RAS ke do operations kya hain aur unke triggers kya hain? ::: Predicted CALL par push, predicted RET par pop.
• TOS kya hai aur yeh kaise move karta hai? ::: Top-Of-Stack pointer; push ise aage badhata hai, pop peeche le jaata hai, mod N ke saath wrap karta hai.
• a mod N kya compute karta hai aur yahan kyun use hota hai? ::: $a/N$ ka remainder; yeh pointer ko N slots ki ring ke around wrap karta hai.
• count, min aur max use karke kiske khilaf guard karta hai? ::: min ise N par cap karta hai (full se aage overflow nahi), max ise 0 par floor karta hai (empty stack pop nahi hoti).
• Ek BTB returns achhi tarah predict kyun nahi kar sakta? ::: Ek RET PC bahut saare caller targets par map karta hai, lekin BTB ek PC → ek target assume karta hai.