Sumeet Bansal
CSE 131 PA4
fibonacci.boa
(def fib (n : Num) : Num
(if (< n 3)
1
(+ (fib (- n 1)) (fib (- n 2)))
)
)
(fib input)
remainder.boa
(def remainder (a : Num b : Num) : Num
(while (> a 0) (set a (- a b)))
(+ a b)
)
(print (== (remainder 14 2) (0)))
(print (== (remainder 15 2) (1)))
(print (== (remainder 10 4) (2)))
(print (== (remainder 20 1) (0)))
isprime.boa
(def isprime (n : Num) : Bool
(let ((x 2) (norem true))
(while (< x n)
(if (== (remainder n x) 0)
(set norem false)
(set norem norem)
(set x (+ x 1))
)
norem
)
)
(isprime input)
deepstack.boa
(def square (n : Num) : Num (* n n))
(def cube (n : Num) : Num (* n (square n)))
(def factorial (n : Num) : Num
(if (< n 1)
(cube 1)
(* n (factorial (- n 1)))
)
)
(factorial 12)
Calling Convention
- General convention
(a) Beforehand, the caller places the current label and then the current RSP value in the free stack space and RSP is set to the next available address. The caller then compiles and executes the parameter expressions, moves them to RSP-idx where idx is a parameter's respective index, e.g. if si=0 the second parameter would be moved to RSP-16, and updates si according to the number of parameters. Afterwards, the caller sets RSP to the RSP value that was placed in the free stack space (i.e. RSP-16) and expects the return value of the callee to be RAX as usual.
caller
place current label in RSP-si
place current RSP value in RSP-si-16
set RSP to RSP-si-32
compile parameter 1, save to RSP
compile parameter 2, save to RSP-16
set si to 2
call callee (executes, returns to RAX)
set RSP to original value in RSP-16
(b) The callee is responsible for executing normally, with the assumption that the parameter values are in RSP-idx and then placing the return value in RAX.
(c) Improvements could include optimizations for tail recursive functions or maybe using alternate registers for parameters to save on free stack space.
Examples of Calling Convention
Fibonacci is interesting as a recursive function that continuously sets and then resets the stack pointer, as it goes recursively calls itself until the base case once, then returns back to the original caller, and then recursively calls itself again, providing a good self-contained test case.
fib:
# if condition
# if false body
# if true body
ret
mov [rsp-32], rsp
mov rsp, rsp-48
mov rax, rdi
mov rsp, rax
call fib
mov [rsp], rax
ret
Fibonacci has one initial call, and then it continually recurses and calls itself, so only the initial call appears in the assembly, which makes it difficult to compile and debug, since the control flow of the program isn't entirely laid out in order and instead jumps between stack frames.
Remainder is interesting as a function with a while loop that keeps setting a parameter variable's value, since that provides a good test for function memory and verifying that the stack is laid out as expected.
rem:
while_label:
# condition == true
jne while_end
# while body
while_end
# save current RSP and label on free stack space
# set RSP to free stack space
# place parameter 1 (15) directly above RSP
# place parameter 2 (2) directly above RSP
call rem
# reset RSP
ret
Since rem is only a while loop, it's a bit more straightforward in its assembly and only verifies that there exists a function parameter that is directly above the function's RSP value.
IsPrime is interesting as a function that calls another function because that tests a function being both the caller and the callee and provides an addition level of depth to the test suite, since the inner function call should have access to the outer function's parameter (and the outer function's environment).
isprime:
# set local variables
# while loop
# save current RSP and label on free stack space
# set RSP to free stack space
# place parameter (rdi from input) directly above RSP
call isprime
# reset RSP
ret
IsPrime is a while loop with a body that keeps calling another function on each iteration, so the callee should have the exact same addresses for memory every time.