Procedures and the Stack

Procedures and The Stack

Procedures (Functions)

So far, we haven't seen how to implement a function in assembly language. First, we need to define the characteristics of functions, and then we'll see how to implement all these features. Features:

  1. Jump to a specific location.

  2. At the end of the function, return to the place from which we jumped (actually one line after).

  3. A way to pass parameters to the function and receive a result from the function.

  4. Any changes made to variables (registers) inside the function will not affect the variables outside the function. No side effects.

1. Jump to a Specific Location

  • To jump to the address of the beginning of the function, we will use jal rd, label.

  • Remember: Register rd will receive the value of PC + 4 so that we can return to the place from which we jumped after the function is completed.

  • label specifies the address of the beginning of our function, and we will jump there!

  • Why not use beq to jump to the function? Because then there will be no way to return to the place from which we jumped, because the return address is not stored anywhere.

2. At the End of the Function, Return to the Place From Which We Jumped

  • There is an instruction jalr that allows jumping to a location stored in a register that we specify to return.

  • Since we jumped to the function using jal and saved PC + 4 in rd, we will use jalr rd, offset(rs1). This is how the instruction looks.

  • Its operation: rd=PC+4rd = PC + 4 and PC=rs1+offsetPC = rs1 + offset

  • Therefore, we will use jalr zero, 0(register used in previous jal). Since the address after the procedure does not interest us, we will "save" it in zero.

Example

.text
# function example
jal ra, myFunc
jal zero, end
myFunc:
# do something
jalr zero, 0(ra)
end:

Important Note: In the jal instruction, we will always use the ra register to save the return address.

Implementing Function Feature 3

  • There is no special instruction for passing parameters to the function.

  • It is customary to put parameters in registers a0, a1, a2, …, a7.

  • That is, the function expects to find the parameters in these registers. If there is only one parameter, register a0 is used. If there is a second parameter, register a1 is used, and so on.

  • It is the programmer's responsibility to work according to the standard.

  • The same registers are used to return the output of the function.

  • That is, if there is only one output, it is returned in register a0. If there is a second output, it is returned in register a1, and so on.

How to Implement Feature 4: No Side Effects?

  • We want a situation where it is possible to use all (32 or slightly less) registers inside the function without affecting operations that occur after the function is completed.

  • That is, the caller should not be disturbed by the callee's operations.

  • To do this, at the beginning of the function, we will save in the main memory (RAM) all the registers that the function will change during its operation.

  • Before the end of the function, we will restore the original values to their registers.

  • There is a specific place in memory designated for saving the values temporarily, and it is called the stack.

  • Register sp points to the top of the stack.

Stack

In data structure studies, a stack has two operations:

  • PUSH: Adding an element

  • POP: Returning the last element and deleting it from the stack

LIFO (Last In First Out) order of operations.

The sp register should contain the address of the top of the stack, which is usually a high address like 0x7FFFEFFC (usually there is a memory allocation for the stack even before the main program is called).

In RISC-V, there are no special commands to manage the stack (like push and pop). Therefore, we need to manage it manually. There are agreed-upon procedures on how to manage it so that we can connect source code from different languages. We will work with the lw and sw commands we have already learned, but in addition, we will update sp to allocate space. Example in the next slide.

RISC-V Stack Alignment

According to RISC-V guidelines, on entry and exit from a function, the sp must be on a 16-byte boundary. This is necessary to maintain coordination with other systems.

Inside the procedure, memory can be allocated in multiples of 8 bytes for a 32-bit processor, and in multiples of 16 bytes for a 64-bit processor.

In the example, we will save the value of register s0 in the stack and then retrieve it:

addi sp, sp, -16
sw s0, 4(sp)
lw s0, 4(sp)
addi sp, sp, 16

Saving Registers

Usually, the sp is moved once at the beginning of the function, and then all the registers that we must preserve are saved. The standard order is:

  • Move the sp at the beginning of the procedure in multiples of 16.

  • Save the ra (if there is another jump to a function inside the function).

  • Save s0 to s11 in the stack if they are changed inside the function.

  • Move s0 (fp) to the top of the stack (optional). Will be explained on the next slide.

At the end of the function, perform all these operations in reverse order.

Frame Pointer (fp)

  • What do we do if inside a function we want to declare a local array or struct?

  • For this, we use the same memory area that the sp register points to.

  • In effect, we will use addresses lower than where the sp points to.

  • Therefore, we need to decrease the value of sp as needed to allocate space (multiples of 8 bytes on a 32-bit processor, 16 bytes on a 64-bit processor).

  • It is advisable to save the original value of sp before we change it when allocating space for local arrays.

  • We will copy the value of sp to the fp register (synonyms for register s0). This copy will prevent some problems.

Typical Frame Example

example_function:
  addi sp, sp, -16  # Allocate 16 bytes on the stack (ensures alignment)
  sw ra, 12(sp)   # Save return address (only if calling another function)
  sw s0, 8(sp)   # Save previous frame pointer
  sw s1, 4(sp)   # Save s1, example of register the function intended to modify
  sw s2, 0(sp)   # Save s2, etc,
  addi fp, sp, 16  # Set up frame pointer equal to original top of stack
  # Function body here...
  lw ra, 12(sp)   # Restore return address
  lw s0, 8(sp)   # Restore frame pointer
  lw s1, 4(sp)   # restore s1
  lw s2, 0(sp)   # restore s2
  addi sp, sp, 16  # Deallocate stack space
  jalr zero, 0(ra)  # Return to caller

Why Do We Want to Use a Frame (FP)?

  • There may be a problem if we do not use a frame.

  • For example, if inside the function there is a need to store data in the stack (because we need to free a register, for example), we will want to retrieve the data according to the same offset we stored it. If between storage and retrieval, the sp changes, the original offset will not be correct.

  • Moreover, if there were several movements of sp, the assembler would have to sum all the movements, a rather complex operation.

# function body
addi sp, sp, -8  # Allocate 8 bytes (for local variable)
sw t0, 0(sp)  # Store local variable in stack
addi sp, sp, -64  # Allocate array of 16 integers
lw t0, 0(sp)  # Attempt to retrieve t0 fails because sp has changed

Example of Using fp – Code in C

int helper(int x) {
  return x * 3;
}

int example(int a, int b) {
  int c = a + b;
  int d = helper(c);
  return d * 2;
}

RISC-V Code Example

# Prologue — set up stack frame
addi sp, sp, -16  # allocate 16 bytes
sw ra, 12(sp)  # save return address
sw s0, 8(sp)  # save old frame pointer
addi fp, sp, 16  # fp = old sp (frame base)
add t0, a0, a1  # c = a + b
sw t0, -12(fp)  # store c at (fp-12), same as original 4(sp)
addi sp, sp, -8  # temporarily allocate 8 more bytes
addi t0, t0, 1  # change t0 to c+1
sw t0, 4(sp)
sw t1, 0(sp)
lw a0, -12(fp)  # load c into a0 (helper arg), 4(sp) is not valid!
# Nested call — sp moves again
jal helper  # d = helper(c)
sw a0, -16(fp)  # store d at (fp-16), same as original 0(sp)
lw t0, 4(sp)
lw t1, 0(sp)
addi sp, sp, 8
lw t1 -16(fp)  # load d into t1
slli a0, t1, 1  # a0 = d * 2 (return value)
# Epilogue — restore stack and return
lw ra, 12(sp)  # restore return address
lw s0, 8(sp)  # restore old frame pointer
addi sp, sp, 16  # deallocate stack frame
ret

helper:
addi sp, sp, -16  # allocate stack space
sw ra, 12(sp)  # save return address
slli t0, a0, 1  # a0 = x * 2
add a0, a0, t0  # a0 = x * 3
lw ra, 12(sp)  # restore return address
addi sp, sp, 16  # free stack
ret

Explanation of the Solution

  • fp is constant throughout the procedure. Therefore, even if sp moves dynamically, we can restore registers that we saved in the stack and we can also restore sp to its original state.

  • Advantages:

    • Local variables are offset from fp.

    • It is easier to debug procedures.

Standard Entry

addi sp, sp, -16 # Allocate 16 bytes
sw ra, 12(sp) # Save return address
sw s0, 8(sp)  # Save old frame pointer
addi s0, sp, 16 # Set new frame pointer (to old sp value)

# Stack Visualization
s0 → ┌───────────────┐ (sp+16 — top of frame)
  │ — │
s0-4  │ ra (saved) │ (sp+12)
s0-8  │ s0 (saved) │ (sp+8)
s0-12 │ c (local) │ (sp+4)
s0-16 │ d (local) │ (sp+0 — current sp)
  └───────────────┘
sp → (sp)

Procedure Call

  • Hardware Instructions:
    jal rd, offset # rd=PC+4rd = PC + 4, PC=PC+offsetPC = PC + offset
    jalr rd, offset(rs1) # rd=PC+4rd = PC + 4, PC=rs1+offsetPC = rs1 + offset

  • Pseudo Instructions:
    jr rs1 # same as jalr zero, rs1, 0. Jump to address in rs1.
    ret # same as jalr zero, ra, 0. Return to address saved in RA.
    jalr rd # same as jalr ra, rd, 0. Jump to address in rd, save PC + 4 to RA.
    j offset # same as jal zero, offset. Unconditional jump without saving ra.
    jal offset # same as jal ra, offset.Unconditional jump with saving ra.

Function Call Process

  • Call to jal or jalr, with saving of PC + 4 inside rd, usually register ra.

  • The PC jumps to offset + PC (or offset + rs1 in the case of jalr) to continue executing instructions.

  • Return to the calling code by calling jr ra, ret, or jalr zero, ra, 0.

When the jump is to a nearby address, jal can reach the destination address. When the call is to a remote function, we will use the pseudo command call. The call command divides the jump into two real commands - auipc and jalr.

CALL Instruction

call rd, myfunc # jump to myfunc and store PC+4 in rd , usually ra
call foo # jump to myfunc and store PC+4 in ra

In the simulator, this will be translated to auipc and jalr.

In the GNU assembler of the processor, the command is translated to:

1: auipc ra,%pcrel_hi(myfunc)
jalr ra, ra, %pcrel_lo(1b)

%pcrel_hi(symbol) is a macro that equals the 20 high bits of the symbol.
%pcrel_lo(symbol) is a macro that equals the 12 low bits of the symbol.

The first instruction copies the 20 high bits of the destination relative to the PC.
The second instruction adds the 12 bits of the address relative to the line of the auipc, i.e., label 1.

Numeric Labels

  • What is the meaning of label 1 and the reference to it as 1b?

  • The GNU assembler allows calling numeric labels in a special way.

  • The notation 1b means, jump backward to the first label called 1.

  • Similarly, the notation 1f means jump forward to the first label called 1.
    b=backward
    f=forward

  • This method allows using the same labels more than once without thinking about a new name for the label each time.

  • The code %pcrel_lo(1b) must point to the line of the auipc.

Example in Simulator

.text
call myfunc
li a7, 10
ecall

.text 0x500128
myfunc:
li a0, 1
ret

Explanation

The simulator will overwrite t1 (register number 6!). This is a bug in the simulator (should overwrite x1).
In the first line, t1 will be equal to x0 + 0x400000 + (12 >> 100) or x0 + 0x100000 * x0, total x0 + 0x500000.
In the second line, add the 12 low bits x,0 + 128 and jump to x0 + 0x500128. In RA will be the value x0 + 0x400008.

Passing Parameters Through the Stack

For example, when there are more than eight parameters, or passing something by value.

.text
li t0, 10
li t1, 11
addi sp, sp, -16
sw t0, 0(sp) #param a
sw t1, 4(sp) #param b
jal mystackfun
addi sp, sp, -16
li a7, 16
ecall

mystackfun:
addi sp, sp, -16 # allocate stack space for two registers and two local words
sw ra, 12(sp) # save ra
sw s0, 8(sp) # save s0/fp
addi s0, sp, 16 # set fp to original stack
li t0, 12
sw t0, 4(sp) #write to stack using sp
li t0, 13
sw t0, -16(fp) #write to stack using fp
lw t2, 0(fp) #read param a from caller
lw t3, 4(fp) #read param b from caller
lw ra, 12(sp) # restore ra
lw s0, 8(sp) # restore s0/fp
addi sp, sp, 16 # restore sp
ret

Local variables are in a negative offset relative to fp. Variables from the caller are in a positive offset relative to fp.