Foundations — Return address stack

Before you can read the parent note on the Return Address Stack, every symbol it throws at you needs to be built from nothing. This page is that toolbox. Read it top to bottom — each item leans on the one above it.

---

1. What is an "address"? (the number 0x1000)

The parent note writes addresses like 0x1000. That little 0x means "the number after me is written in hexadecimal (base-16)" instead of the base-10 you use every day.

Why base-16 and not base-10? Because computers group bits into chunks of 4, and one hex digit = exactly 4 bits. It lines up neatly with the hardware. 0x1000 in plain decimal is $4096$.

The picture shows memory as a tall column of numbered slots. An address is simply which slot you point at.

---

2. The Program Counter, PC

The parent writes $P{C}_{\text{call}}$ — that just means "the address where a particular CALL instruction lives". Every instruction has an address, and the PC is a finger pointing at one of them.

Why does the topic need this? Because a return has to jump back to a specific address, and that address is computed relative to where the call was — so we must be able to name "where the call was", and that name is its PC.

---

3. Instruction size, size / instruction_size

So the return address is: $\text{return address}=P{C}_{\text{call}}+{\text{size}}_{\text{call}}$

Here ${\text{size}}_{\text{call}}$ (also written $\text{instruction\_size}$) is how many bytes the CALL instruction occupies. Adding it to the CALL's address lands you exactly on the next instruction.

Look at the amber arrow in the figure: it hops over the CALL instruction's width to land on the next slot. In Example 1 of the parent, the CALL sits at 0x1000 and the next instruction is at 0x1004, so the size is $4$ bytes.

---

4. CALL and RETURN instructions

These two are the only instructions the RAS cares about. Every CALL creates a future promise; every RET keeps it. This is the Call Stack relationship, done in hardware.

---

5. LIFO and the idea of a "stack"

This is the heart of everything.

Think of a stack of plates. You add plates to the top and remove them from the top. You never yank a plate from the middle.

Why is this the right shape for calls and returns? Because calls nest. If A calls B calls C, then:

• C must finish before B,
• B must finish before A.

The last function entered (C) is the first to return. That is literally the LIFO rule. So a stack of return addresses matches the nesting of calls with zero effort — which is exactly the parent note's "Proof that Stack is Optimal".

Recall

Why is a stack (LIFO) the perfect structure for return prediction? ::: Because functions return in the reverse order they were called — the most recently called function returns first, which is exactly what "pop the last thing pushed" gives you.

---

6. push() and pop() as operations

In words: a CALL remembers where to come back (push), a RET asks the stack where to go (pop). The value the pop hands back is the CPU's guess for the return target — this is a prediction, made early so the pipeline doesn't stall.

---

7. TOS — the Top-Of-Stack pointer

Real hardware can't grow a pile of plates infinitely. It uses a fixed row of $N$ slots and a pointer that says "the top is here".

The figure shows the row of $N$ slots bent into a ring (a circular buffer). When TOS walks off the last slot, it wraps around to slot 0 — that is what the notation $\mathrm{mod}N$ means next.

---

8. The modulo operation, mod N

Why does the topic need it? To make the pointer wrap around the ring of $N$ slots. When TOS is at the last slot $N-1$ and you push: ${\text{TOS}}_{\text{new}}=({\text{TOS}}_{\text{old}}+1)\mathrm{mod}N$ gives $0$ instead of an illegal slot $N$. The modulo turns a straight row into an endless loop.

• 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. The occupancy counter, count, and min/max

The wrapping is clever but dangerous: a bare ring never knows if it's empty or full. So we keep a second small number.

$\min$ and $\max$ are the guards that keep count sensible: $\text{count}=\min (\text{count}+1,N)(\text{push, never exceed }N)$ $\text{count}=\max (\text{count}-1,0)(\text{pop, never below }0)$

• $\min (a,b)$ = the smaller of the two. It caps count at $N$ so a full stack stays full.
• $\max (a,b)$ = the larger of the two. It floors count at $0$ so an empty stack can't go negative.

Why bother? A pop on an empty stack (count == 0) would otherwise return garbage stale data. The counter lets the hardware answer "no prediction" instead. This is the parent's underflow guard.

Recall

What does count == 0 tell the RAS to do on a RET? ::: The stack is empty, so it must report "no prediction" rather than pop stale garbage.

---

10. The two words hiding underneath: BTB and speculation

The parent contrasts the RAS with a Branch Target Buffer (BTB) and mentions Speculative Execution.

Both connect to why returns are a special sub-problem of Indirect Branch Prediction and why the RAS feeds Instruction Fetch a target to fetch from early.

---

Prerequisite map

Each arrow means "you need the source before the target makes sense". Everything funnels into the Return Address Stack.

---

Equipment checklist

Test yourself — reveal only after you've answered aloud.

• What does 0x in front of a number mean? ::: The number is written in hexadecimal (base-16); one hex digit equals 4 bits.
• What does the Program Counter hold? ::: The address of the instruction the CPU is currently working on.
• Where does a function return to, in terms of $PC$ and size? ::: To $P{C}_{\text{call}}+{\text{size}}_{\text{call}}$ — the instruction right after the CALL.
• State the LIFO rule in one sentence. ::: The last item pushed is the first item popped.
• Why does call/return nesting match a stack exactly? ::: The most recently called function is the first to return, mirroring last-in-first-out.
• What are the two RAS operations and their triggers? ::: push on a predicted CALL, pop on a predicted RET.
• What is TOS and how does it move? ::: The Top-Of-Stack pointer; push advances it, pop retreats it, wrapping with mod N.
• What does a mod N compute and why is it used here? ::: The remainder of $a/N$; it wraps the pointer around a ring of N slots.
• What does count guard against, using min and max? ::: min caps it at N (no overflow past full), max floors it at 0 (no popping an empty stack).
• Why can't a BTB predict returns well? ::: One RET PC maps to many caller targets, but a BTB assumes one PC → one target.