Jumps and Stack Frames

Learning Outcomes

• Identify use cases for unconditional jump instructions and pseudoinstructions–in particular, know how to jump to procedures and return from procedures.
• Compare RISC-V stack frames to C stack frames.
• Write RISC-V instructions that allocate and deallocate stack frames.

🎥 Lecture Video

🎥 Lecture Video

9:10 onwards

Jump instructions

Transferring control between procedures simply means unconditional jumps to different program instructions. Notably, if one procedure (caller) calls another (callee), the callee must know how to return to the caller.

Recall that unconditional jumps are instructions that, when executed, set PC to a different instruction. We therefore need jump instructions that keep track of instruction return addresses.

Above, “save the return address” means to save the address of the next instruction, PC + 4, into the named register ra. “Jump to an address” means to update the PC so that on the next cycle, the computer executes a different, out-of-order instruction.

Let’s discuss this in more detail below.

Jump pseudoinstructions vs. real instructions

Unconditional jumps are not particularly tricky to understand (we hope). However, it is important to note that of their many use cases, there are only two real unconditional jump instructions shown in #tab-rv-jumps: jal and jalr. The rest (jr, ret, j, another jal) are pseudoinstructions.

There are two real instructions above.

Jump and Link (jal rd label). Write the address of the next instruction, PC + 4, to register rd. Then perform an unconditional jump to label by setting PC to the address of the instruction with label label. The linking means that we form a link that can be used to return to the caller. (In this respect, jal should really be called “Link and Jump”).

• Pseudoinstruction j label is used to implement conditional statements and loops, as discusssed in an earlier section. jal x0 label effectively discards the link/return addresss, because register x0 is hardwired to zero.
• Pseudoinstruction jal label is expanded to jal ra label, where register name ra is the return address or register number x1. We discuss this reasoning below.

Jump and Link Register (jalr rd rs1 imm). Link the “return address” (PC + 4) to a register rd. Then perform an unconditional jump by setting PC to R[rs1] + imm.

• Pseudoinstruction jr rs1 is instruction jalr x0 rs1 0, meaning that we discard the link and jump directly to the address in register rs1.
• Pseudoinstruction ret is instruction jalr x0 ra 0 and is equivalent to jr ra. Discard the link and jump directly to the return address in named register ra.

Show Explanation

jal specifies a jump target by label. jal supports procedure calls because presumably, you should know the name of the procedure you are calling.

jalr specifies a jump target by register. jalr supports procedure returns because you don’t necessarily know the name of procedure called you (nor should you expect that you were called at the beginning of said procedure); rather you should just know the address to return to. We will see in a later chapter how jalr facilitates jumps with absolute addressing.

leaf Function Example

🎥 Lecture Video

RISC-V Stack Frames

In a previous section we have already seen how we can store and load arrays to and from the stack. In this section we discuss how stack frames get allocated and deallocated between function calls.

When we discussed the C stack, we saw an animation that pushed and popped stack frames between function calls. Importantly:

The stack grows downward. The stack pointer (sp) points to the top of the stack, i.e., the address of the current stack frame.

RISC-V stack frames (mostly) operate like C stack frames. As discussed in an earlier section, the stack pointer holds the address of the top of the stack. By [RV32I register convention], this value is stored in the sp register, which is register number x2.

A RISC-V proedure can choose to use a stack frame by manipulating sp:

• When the callee gains control, set up in the prologue allocate/push the stack frame by decrementing sp (again, the stack grows downward).

• When the callee wraps up in the epilogue, deallocate/pop the stack frame by incrementing sp.

The slidedeck in #fig-rv-stack-anim animates allocation and deallocation on the stack via the stack pointer.

An extended animation of stack memory management in RISC-V.

Explanation of [#fig-rv-stack-anim](#fig-rv-stack-anim)

1. main allocates 12B of space for its stack frame by decrementing sp by 12. This happens in the first line of main, implying that stack frame allocation is part of main’s prologue. From the perspective of main, the stack pointer sp holds 0xFFFFFFD4, which is the bottom of main’s stack frame. At some point, main calls fooA.
2. In fooA’s prologue, fooA allocates 8B of stack space by decrementing sp by 8. From the perspective of fooA, the stack pointer sp holds 0xFFFFFFCC, which is the bottom of foo’s stack frame.
3. In fooA’s epilogue, it deallocates the same 8B of space by incrementing sp by 8. Before returning with jr ra, fooA (as the callee) has restored main’s stack pointer to 0xFFFFFFD4.
4. When main regains “control,” it sees the right stack pointer, 0xFFFFFFD4.

Across function calls, the caller main’s stack pointer is preserved. We discuss this register calling convention in another section.

Like in C, pushing and popping stack frames simply corresponds to decrementing and incrementing the the stack pointer. A previous callee’s data may therefore stay in memory that is marked as “free” for the next callee to scribble over it. Refer to the C stack discussion for potential security issues.