fibonacci
factorial

Example of recursive function call
 

Fibonacci

  many local variables are required

;;  t3 = n
;;  t1 = fib t3 - 1
;;  retv = fib t3 - 2
;;  retv = retv + t1

;;  r1 = input n, r2 = output retv,
;;  r3 = link, r4 = sp,
;;  r5 = t1, r6 = t3,

;;  main() { b = fib(6) }

.s
   b 100

.a 0
.c
:main
   ld r4 #200  ;; init sp
   ld r1 #6
   jal r3 fib  ;; call fib 3
   st b r2
   trap stop r0

:fib
   st @1 r4 r3  ;; push link
   st @2 r4 r5  ;; push t1
   st @3 r4 r6  ;; push t3
   add r4 r4 #3

   sub r0 r1 #2 ;; n < 2
   jmp GE else
:then
   or r2 r1 r0 ;; retv = n
   jmp always ret
:else
   or r6 r1 r0 ;; t3 = n
   sub r1 r6 #1 ;; n - 1
   jal r3 fib
   or r5 r2 r0 ;; t1 = fib n - 1
   sub r1 r6 #2 ;; n - 2
   jal r3 fib  ;; retv = fib n - 2
   add r2 r2 r5

;; restore locals
:ret
   ld r6 @0 r4
   ld r5 @-1 r4
   ld r3 @-2 r4
   sub r4 r4 #3
   jr r3
.e

You can compare this with the code that a simple compiler generated:

   0 .s
   0  rz 0
   0  retv 28
   0  bp 29
   0  rads 30
   0  sp 31
   0  print 1
   0  printch 2
   0 .a 0
   0 .c
   0    ld sp #1000 ;; initialise sp
   1    ld bp #3000 ;; initialise bp
   2    jal  rads label_49  ;; call main
   3    trap  stop rz

   4    ;; ---- Func fib
   4 :label_5
   4    add  bp bp #2
   5    st   @0 bp rads
   6    ;; ---- save regs
   6    st   @1 sp r1
   7    st   @2 sp r2
   8    add  sp sp #2
 
   9    ld   r1 @-1 bp
  10    sub  rz r1 #2
  11    jmp  ge label_27  ;; if(n < 2) return n;
  12    ld   r1 @-1 bp
  13    or   retv r1 rz
  14    ld   rads @0 bp
  15    sub  bp bp #2
 
  16    ;; ---- restore regs
  16    ld   r1 @-1 sp
  17    ld   r2 @0 sp
  18    sub  sp sp #2
  19    jr   rads

  20    jmp always label_49
 
  21 :label_27
  21    ld   r1 @-1 bp
  22    sub  r1 r1 #1
  23    st   @1 bp r1
  24    jal  rads label_5  ;; fib n - 1
  25    or   r1 retv rz
 
  26    ld   r2 @-1 bp
  27    sub  r2 r2 #2
  28    st   @1 bp r2
  29    jal  rads label_5  ;; fib n - 2
  30    or   r2 retv rz
  31    add  r1 r1 r2
  32    or   retv r1 rz
  33    ld   rads @0 bp
  34    sub  bp bp #2
  35    ;; ---- restore regs
  35    ld   r1 @-1 sp
  36    ld   r2 @0 sp
  37    sub  sp sp #2
  38    jr   rads
 
  39    ;; ---- Func main
  39 :label_49
  39    add  bp bp #1
  40    st   @0 bp rads
  41    ;; ---- save regs
  41    st   @1 sp r1
  42    add  sp sp #1
 
  43    ld   r1 #6
  44    st   @1 bp r1
  45    jal  rads label_5  ;; call fib 6
  46    or   r1 retv rz
  47    trap print r1      ;; print
  48    ld   rads @0 bp
  49    sub  bp bp #1

  50    ;; ---- restore regs
  50    ld   r1 @0 sp
  51    sub  sp sp #1
  52    jr   rads
  53 .e

The main different is how the compiler uses the activation record to store local variables.  The first thing a callee does is to buid an activation record.

Another simpler example:

Factorial

 fac n :
    if n <= 0 return 1
    else return n * fac n - 1

;; main :  a = fac 3

;; let r1 = a
;; let r2 = input n, r3 = output retvalue
;; let r4 = link, r5 = sp

.s
  sp 5
  link 4
  a 100
.a 0
.c
:main
  ld sp #200  ;; initialise sp
  ld r2 #3
  jal link fac
  st a r3
  trap stop r0

:fac
  ;; let t1 = n to do
  ;; n * fac n - 1  is
  ;; t1 = n
  ;; n = n - 1
  ;; retvalue = call fac
  ;; retvalue = t1 * retvalue
  ;; save locals : r6 = t1
  st @1 sp link  ;; push link
  st @2 sp r6  ;; push t1
  add sp sp #2
  sub r0 r2 r0 ;; n <= 0 ?
  jmp GT else
  ld r3 #1
  jmp always ret
:else
  or r6 r2 r0 ;; t1 = n
  sub r2 r2 #1 ;; n - 1
  jal link fac
  mul r3 r6 r3 ;; n * fac n - 1
:ret
  ;; restore
  ld r6 @0 sp  ;; pop t1
  ld link @-1 sp ;; pop link
  sub sp sp #2
  jr link
.e
 

last update 1 September 2003