LC3 assembly STACKS

We want to implement this program in assembly. Unfortunately, it is not trivial. When calling subroutines in assembly, we have to worry about issues such as potential conflicts when using the same registers in both functions and the restoration of the return address. These issues are made more obviuos when implementing recursion.

Because of this, we will be using the stack protocol, a set of rules that allows the program to keep track of function calls. You are already familiar with some of it: every time a function is called, an activation record for that function is pushed into the stack. The activation record keeps track of the data needed to run the function and to return to the calling function after completion. It includes parameters, bookkeeping information, and local variables. In a high-level language such as C, the compiler takes care of generating the code that builds and stores an activation record in the stack. In assembly, we will need to take care of the low-level details for building each activation record.

The stack protocol that we will use for the LC-3 is as follows:

Step 1: the caller pushes the parameters for the callee in reverse order. This step is optional because the callee may be a function that takes no parameters.

Step 2: the caller calls the callee using JSR.

Step 3: the callee allocates space in the stack for the return value. This step is optional because the callee may be a void function.

Step 4: the callee pushes the return address (the current value of R7). This is similar to making a backup of R7 in a label, except that we are storing it in the stack instead of a label.

Step 5: the callee pushes the previous frame pointer. Each activation record has a frame pointer that points to a fixed location within the record. This allows a function to access all the different parts of its activation record by using the frame pointer as a base address. The frame pointer is stored in R5 (by LC-3 conventions). Hence, in this step, we push the value of R5 into the stack. In our convention, the first frame pointer (before any function is called) is x4000.

Step 6: the callee sets up its own frame pointer. It involves updating R5. The convention is to make the frame pointer point to where the first local variable is (or would be).

Step 7: the callee allocates space for local variables. This step is optional since the callee may be a function without local variables.

Step 8: at this point, the activation record for the callee has been fully built. The callee can now execute its body. In this step, the function will need to update the return value in the stack if necessary.

Step 9: it is now time to start popping the activation record out of the stack. In this step the callee pops the local variables.

Step 10: the next thing in the stack is the previous frame pointer. The callee pops it into R5 (to restore the previous frame pointer).

Step 11: the next thing in the stack is the return address. The callee pops it into R7 (to restore the return address).

Step 12: the callee can now return to the caller using RET.

Step 13: the next thing in the stack is the return value (if the callee is a non-void function). The caller can pop it into a register for its own use.

Step 14: the only things left in the activation record are the parameters. The caller pops them out (if any).

In order to keep track of the top of the stack, we will use register R6. This is a convention. Therefore, your function should not modify this register unless you need to change the stack pointer. It represents the address of the element at the top of the stack. Initially, R6 is x4000. Every time something is pushed into the stack, R6 is decreased and the element is stored at the resulting address. Every time something is popped, the element at the top of the stack is retrieved and R6 is increased. You also do not want to mess with R5 since that is the frame pointer. Finally, as usual, you should not mess with R7. Because of these restrictions, you will need to be cheap with registers.

; Description: Computes N! (N-factorial) recursively ;------------------------------------------------------------------------------- ; Begin reserved section: do not change ANYTHING in reserved section!

.ORIG x3000 BR Main ; Parameter and result Param .FILL x0004 Result .BLKW 1

; Constants Stack .FILL x4000 One .FILL #1 MinusOne .FILL #-1

; End reserved section: do not change ANYTHING in reserved section! ;-------------------------------------------------------------------------------

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; ; int Factorial(int N) ; Returns N! (must be a recursive function) ; Factorial ;__________________ ; Step 3: allocate space for return value ;__________________ ; Step 4: push return address ;__________________ ; Step 5: push previous frame pointer ;__________________ ; Step 6: setup new frame pointer ;__________________ ; Step 7: allocate space for local variable ;;;;;;;;;;;;;;;;;;;;; Step 8: body of the function Checkpoint1 LDR R0, R5, #4 ; Load parameter N into a register LD R1, MinusOne ; Calculate N - 1 ADD R2, R0, R1 ; R2 will contain N - 1 ;__________________ ; Store N - 1 in the local variable BRnz BaseCase ; Detect base case (N <= 1) ;;;; Start of the recursive call ;__________________ ; Step 1: push parameter N - 1 ;__________________ ; Step 2: call Factorial(N - 1) ;__________________ ; Step 13: retrieve return value into R2 ;__________________ ; Step 14: remove parameter from stack LDR R0, R5, #4 ; Multiply N * Factorial(N - 1) .ZERO R3 ; R3 will contain the product MultiplyLoop ADD R3, R3, R2 ; Notice that by this point, R0 > 1 ADD R0, R0, #-1 ; BRp MultiplyLoop ; ;__________________ ; Make return value = N * Factorial(N - 1) BR Finish ;;;; End of the recursive call ;;;; Start of the base case BaseCase LD R0, One ; Make return value = 1 STR R0, R5, #3 ; ;;;; End of the base case ;;;;;;;;;;;;;;;;;;;;; End of the body of the function Finish ;__________________ ; Step 9: remove local variable from stack ;__________________ ; Step 10: restore previous frame pointer ;__________________ ; Step 11: restore return address Checkpoint2 RET ; Step 12: return to calling subroutine

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; ; Entry point ; Calls Factorial(Param) and stores the return value in Result ; Main LD R6, Stack ; Initialize stack pointer LD R5, Stack ; Initialize frame pointer LD R0, Param ; Load parameter into a register ;__________________ ; Step 1: push parameter ;__________________ ; Step 2: call Factorial(Param) ;__________________ ; Step 13: retrieve return value ;__________________ ; Step 14: remove parameter from stack ;__________________ ; Store return value in Result TheEnd HALT .END