Return address stack

5.3.12 · Hardware › Advanced Microarchitecture

Overview

Ek Return Address Stack (RAS) ek specialized hardware structure hai jo modern processors mein function return instructions ke target addresses predict karne ke liye use hota hai. Yeh subroutines ki Last-In-First-Out (LIFO) calling convention ko exploit karke returns ke liye near-perfect prediction accuracy achieve karta hai.

The Problem: Why Returns Are Special

WHY this matters: Typical programs mein, saare branches ka 10-15% returns hote hain. RAS ke bina, returns ke liye misprediction rates 30-50% hoti, jo pipeline performance ko devastate kar deti. RAS ke saath, accuracy 95-98% se zyada hoti hai.

How RAS Works: The Mechanism

Derivation: Why LIFO Structure Is Optimal

Chaliye first principles se derive karte hain ki stack kyun sahi data structure hai.

Observation 1: Function call pattern strict nesting follow karta hai.

• Jab function A, B ko call karta hai, B ko A ke paas return karna hoga pehle, phir A apne caller ko return kar sakta hai.
• Mathematically: Agar call sequence $C_1,C_2,..,C_n$ hai, toh return sequence ZAROOR $R_n,R_{n-1},..,R_1$ hogi.

Observation 2: Return address binding.

• Address $P{C}_i$ par har call $C_i$ exactly ek future return $R_i$ create karta hai address $P{C}_i+\text{instruction\_size}$ par.
• $C_i$ ka return address us pehle subsequent return se consume hota hai jo pehle se match nahi hua.

Proof that Stack is Optimal: Maano $S$ ek data structure hai jo return addresses track karta hai. Call par $\text{push}(addr)$ define karo, return par $\text{pop}()$.

1. Constraint: $k$-ween unmatched call ko $k$-ween future return ke saath pair hona chahiye.
2. Ordering: Returns, calls ke reverse order mein hote hain (program semantics ke anusaar).
3. Therefore: Humein ek aisi structure chahiye jahan MOST RECENT insertion FIRST retrieve ho.
4. Definition: Yahi precisely LIFO (stack) property hai: $\text{pop}()$ last $\text{push}(addr)$ retrieve karta hai.
5. QED: Push-on-call, pop-on-return wala stack optimal prediction deta hai.∎

On RETURN prediction: $\text{predicted\_target}=\text{RAS.pop}()$

RAS Pointer Update (with saturation/count guarding): TOS pointer $N$ slots ke circular buffer mein move karta hai, lekin ek alag occupancy counter (ya valid bits) govern karta hai ki kya ek push live data overwrite karta hai aur kya ek pop legal hai: ${\text{TOS}}_{\text{new}}=({\text{TOS}}_{\text{old}}+1)\mathrm{mod}N,\text{count}=\min (\text{count}+1,N)\text{(push)}$ ${\text{TOS}}_{\text{new}}=({\text{TOS}}_{\text{old}}-1)\mathrm{mod}N,\text{count}=\max (\text{count}-1,0)\text{(pop)}$ jahan $N$ RAS depth hai, TOS = Top-Of-Stack pointer.

WHY the count/valid guard? Raw mod N arithmetic dono ends par wrap karta hai. Overflow par (push when full) yeh intended hai—yeh oldest entry overwrite karta hai (Example 2 dekho). Lekin underflow par (pop when empty), bare mod N ek spurious entry produce karega jo stale data point karta hai. Occupancy counter (ya per-entry valid bits) isko prevent karta hai: count == 0 ke saath pop "no prediction" return karta hai garbage ki jagah, aur count == N se aage pushes counter ko cap karte hain jabki TOS ko oldest slot evict karne ke liye advance karte hain.

Worked Examples

Execution with RAS:

| Cycle | PC | Instruction | RAS Action | RAS Contents (bottom→top) | |-------|---|------------|---------------------------| | 1 | 0x1000 | CALL 0x2000 | Push 0x1004 | [0x1004] | | 2 | 0x2000 | CALL 0x3000 | Push 0x2004 | [0x1004, 0x2004] | | 3 | 0x3004 | RET | Pop → 0x2004 | [0x1004] | | 4 | 0x2004 | SUB r3, r4 | (no action) | [0x1004] | | 5 | 0x2008 | RET | Pop → 0x1004 | [] | | 6 | 0x1004 | ADD r1, r2 | (no action) | []

WHY each step?

• Cycle 1: CALL return address push karta hai (call ke baad wali next instruction). WHY? Return ko yahaan jump karna hoga.
• Cycle 2: Nested call doosra address push karta hai. WHY? Stack nested context track karta hai.
• Cycle 3: Pehla return MOST RECENT address pop karta hai (0x2004). WHY? LIFO call/return nesting se match karta hai.
• Cycle 5: Doosra return remaining address pop karta hai. Stack ab empty hai (count = 0), main context par wapas.

Result: Dono returns correctly predict hue. Koi pipeline flush nahi.

A calls B calls C calls D calls E calls F

RAS State:

WHY the overflow happens?

• RAS finite hota hai (silicon area cost). Jab depth exceed ho jaati hai, oldest entry overwrite ho jaati hai.
• 5ween push TOS ko circular buffer ke around advance karta hai (entry 0 evict karte hue); occupancy counter $N$ par saturate ho jaata hai double-counting ki jagah.

Performance impact: Deep recursion ya lambi call chains misses cause karti hain. Typical mitigation: 16-32 entry RAS 99%+ real call depths handle karta hai.

Common Mistakes

Why it's WRONG: RAS specifically calls/returns ke LIFO pattern ke liye design kiya gaya hai. Doosre indirect branches (switch statements, function pointers, virtual method calls) LIFO follow nahi karte—woh history-based ya data-dependent hote hain.

Example of failure:

switch(x) {
    case 0: goto label_A;
    case 1: goto label_B;
}

Yeh computed branch x ke basis par different targets par jaata hai, call/return nesting par nahi. RAS stale data pop kar deta.

The FIX: RAS SIRF architectural return instructions ke liye use karo. Doosre indirect branches ke liye BTB, indirect branch predictors, ya tagged target caches use karo.

Why it's WRONG: Non-recursive programs mein bhi call chains hote hain. Ek typical path ho sakta hai:

main → init → parse_config → open_file → validate_path → check_permissions

Yeh kisi bhi return se pehle 5 calls hain. Library calls (malloc, printf) add karo, aur 8-12 entries easily consume ho jaati hain.

Quantitative impact:

• 4 entries: ~85% accuracy
• 8 entries: ~92% accuracy
• 16 entries: ~97% accuracy
• 32 entries: ~98.5% accuracy

The FIX: Modern processors 16-32 entry RAS use karte hain. Area cost tiny hai lekin performance gain significant hai.

Implementation Details

RAS and Speculative Execution

Critical challenge: Agar ek speculatively executed call/return baad mein flush ho jaaye toh?

Instruction $I_{\text{flush}}$ par misprediction flush par: ${\text{RAS}}_{\text{spec}}\leftarrow {\text{RAS}}_{\text{committed}}[\text{snapshot at }{I}_{\text{flush}}]$

Derivation: Humein checkpointing kyun chahiye:

• Speculative path predict kar sakta hai: call A → call B → return (B pop karta hai).
• Agar call A mispredicted tha, toh return pop galat tha.
• RAS (dono TOS pointer AUR occupancy counter) ko call A se PEHLE wali state par restore karna padega.

Implementation: Branch points par RAS snapshots ka circular buffer maintain karo, ya ek repair mechanism use karo jo speculative pushes/pops ko "un-do" kare.

RAS Entry Composition

Har RAS entry ek return address plus ek valid bit store karta hai. Address field width implemented virtual address bits ki sankhya ke barabar hoti hai, jo architecture-dependent hai:

[W-1:0]  Return Address (W = implemented VA width, e.g. 48 bits on x86-64)
[W]      Valid bit

WHY sirf implemented VA bits (e.g. 48), full 64 nahi? x86-64 aur AArch64 architecturally 64-bit pointers define karte hain, lekin current implementations sirf lower ~48 bits (canonical addresses) decode karte hain; upper bits bit 47 ka sign-extension hain aur store karne ki zaroorat nahi. Toh ek practical RAS entry ~48 address bits + 1 valid bit store karta hai.

Area estimate (48-bit entries ke saath consistent): $32\text{ entries}\times (48+1)\text{ bits}=32\times 49=1568\text{ bits}\approx 196\text{ bytes}.$ (Agar koi design full 64-bit addresses store karta hai, toh cost $32\times 65=2080$ bits $\approx 260$ bytes hai — phir bhi tiny.)

WHY valid bit? Agar RAS mein active calls uski depth se kam hain, toh bottom se aage pop karna garbage predict nahi karna chahiye. Valid bit (occupancy counter ke saath milkar) indicate karta hai "is entry mein ek live return address hai"; empty RAS par pop ek spurious address ki jagah "no prediction" return karta hai.

Performance Impact

WHY itna bada impact? Har mispredicted return:

1. Pipeline se 15-30 instructions flush karta hai.
2. ~10 cycles ke liye fetch stall karta hai (I-cache + branch target resolution).
3. Prefetcher momentum kho deta hai.

10 instructions mein 1 return ke saath, 3% misprediction rate bhi = 0.3% instructions 15-cycle stalls cause karte hain ≈ 4.5% IPC loss.

Advanced: Link Register vs RAS

Kuch architectures (ARM, RISC-V) memory stack par return addresses push karne ki jagah ek link register (LR) use karte hain.

Trade-off analysis:

Key insight: Link register ISA ke saath bhi, processor internally prediction ke liye RAS use karta hai. LR ek architectural mechanism hai; RAS ek microarchitectural optimization hai.

Ab imagine karo tum ek chain follow kar rahe ho: page 20 kehta hai "go to page 75," phir page 75 kehta hai "go to page 100." Tum bookmarks ka ek STACK bana rahe ho: pehla bookmark page 20 par, doosra page 75 par. Jab tum page 100 se khatam ho jaate ho, tum TOP bookmark (page 75) remove karte ho aur wahaan wapas jaate ho. Phir jab page 75 ka section khatam ho, tum AGLA bookmark (page 20) remove karte ho aur wahan return karte ho.

Return Address Stack exactly yahi hai: tumhare computer ke brain mein bookmarks ki ek chhoti si pile. Jab program ek function call karta hai (kisi naye page par jaane ki tarah), computer stack par ek bookmark rakh deta hai. Jab function khatam hota hai (us page ka section khatam karne ki tarah), computer TOP bookmark dekhta hai yeh jaanne ke liye ki aage kahan jaana hai. Kyunki functions hamesha us ULTE order mein khatam hote hain jis order mein shuru hue the (nested parentheses band karne ki tarah), ek stack—jahan tum hamesha top se lete ho—perfect hai!

Iske bina, computer ko randomly guess karna padta ki wapas kahan jaana hai, aur aadhe time galat hota. Stack ke saath, yeh 98% time sahi hota hai. Woh 2% ka fark is wajah se hai ki tumhare video games aur apps smooth lagte hain stuttering ki jagah!

Russian nesting dolls ki picture karo: tum unhe ek order mein kholta ho (calls), ULTE order mein band karte ho (returns). RAS computer ka woh tarika hai jisse woh us reverse order ko automatically yaad rakhta hai.

Connections

• Branch Prediction Basics: RAS branch prediction system ka ek component hai.
• Branch Target Buffer: BTB direct aur conditional branches handle karta hai; RAS returns mein specialize karta hai.
• Pipeline Hazards: Mispredicted returns control hazards aur pipeline flushes cause karte hain.
• Call Stack: Software call stack (memory mein) vs hardware RAS (on-chip predictor).
• Speculative Execution: Speculation rollback par RAS restore karna padta hai.
• Indirect Branch Prediction: Returns indirect branches ka ek special case hain.
• Instruction Fetch: RAS return targets early predict karke continuous fetch stream enable karta hai.

#flashcards/hardware

Return Address Stack kya hai? :: Ek hardware stack (typically 8-32 entries) jo return instruction targets predict karta hai calls par return addresses push karke aur returns par pop karke, function calls ke LIFO pattern ko exploit karte hue.

Concept Map