;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Here is a slim program that computes fibonacci(n)
;;

    allocate-registers n, result, temp, comparison
    allocate-registers sp, continuation
    allocate-registers zero, one
    allocate-registers fibonacci, fibonacci-base
   
    li zero, 0
    li one, 1
    li sp, 0
   
    li fibonacci, fibonacci-label
    li fibonacci-base, fibonacci-base-label
   
    read n
    li continuation, end-label
   
fibonacci-label:
    ;; Computes fib(n) into result and jumps to the address in continuation.
    ;;   The register temp is used to store the intermediate computation.
    ;;   The registers n, temp, and continuation are saved and restored to
    ;;   their original values using stack discipline.
   
    sgt comparison, n, one
    jeqz comparison, fibonacci-base
   
    st n, sp                     ; push n, temp, and continuation
    add sp, sp, one
    st temp, sp
    add sp, sp, one
    st continuation, sp
    add sp, sp, one
   
    li continuation, after-first-invocation-label
    sub n, n, one
    j fibonacci
   
after-first-invocation-label:
    add temp, result, zero       ; store fib(n-1) in temp
    sub n, n, one
    li continuation, after-second-invocation-label
    j fibonacci
   
after-second-invocation-label:
    add result, temp, result     ; fib(n-1) + fib(n-2) into result
   
    sub, sp, sp, one             ; pop continuation, temp, and n
    ld continuation, sp
    sub sp, sp, one
    ld temp, sp
    sub sp, sp, one
    ld n, sp
    j continuation
   
fibonacci-base-label:
    add result, n, zero          ; if n=0 or 1, fib(n) = n
    j continuation
   
end-label:
    write result
    halt