\documentclass[11pt]{article}

\title{6.823 Problem Set 1}
\author{Chris Laas}
\date{February 22, 2000}

\pagestyle{myheadings}
\markright{Chris Laas \hfil 6.823 \hfil 2/22/2000}

\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii}}

\begin{document}
\maketitle

\section*{Problem 1-1}
\begin{enumerate}

\item%(a)

The number of registers in the register-memory architecture is not
specified; I'll assume that it is 32, like the load-store
architecture, so register specifiers are 5 bits long.  (Most
register-memory architectures don't seem to have so many, but I'll be
generous.)

In the register-memory architecture, most instructions have two
operands, and are of the form ``op1 $\gets$ op1 $op$ op2''; the
exception is BEZ.  The following table gives the lengths of each type
of instruction (specified by example; \#n represents an immediate, Rn
represents a register, A represents an absolute memory location, (Rn)
represents a register-indirect memory access, and n(Rm) represents a
register-indirect memory access with displacement).

\begin{tabular}{lll}
Example instruction & Length in bits & Length in bytes \\ \hline
ADD R1, \#5    & 8+5+16    = 29 & 4 \\
ADD R1, R2     & 8+5+5     = 18 & 3 \\
ADD R1, A      & 8+5+14    = 27 & 4 \\
ADD R1, (R2)   & 8+5+5     = 18 & 3 \\
ADD R1, 4(R2)  & 8+5+5+14  = 32 & 4 \\
ADD A, \#5     & 8+14+16   = 38 & 5 \\
ADD A, R2      & 8+14+5    = 27 & 4 \\
ADD (R1), \#5  & 8+5+16    = 29 & 4 \\
ADD (R1), R2   & 8+5+5     = 18 & 3 \\
ADD 4(R1), \#5 & 8+5+14+16 = 43 & 6 \\
ADD 4(R1), R2  & 8+5+14+5  = 32 & 4 \\
BEZ R1 {\it label} & 8+5+14 = 27 & 4 \\
\end{tabular}

Likewise, these are the lengths of the various types of instructions
in the load-store architecture.

\begin{tabular}{lll}
Example instruction & Length in bits & Length in bytes \\ \hline
ADD R1, R2, R3  & 8+5+5+5   = 23 & 3 \\
ADD R1, R2, \#5 & 8+5+5+16  = 34 & 5 \\
ADD R1, \#5, R2 & 8+5+16+5  = 34 & 5 \\
ADD R1, \#5, \#6\footnotemark
                & 8+5+16+16 = 45 & 6 \\
LOAD R1, A      & 8+5+14    = 27 & 4 \\
LOAD R1, (R2)   & 8+5+5     = 18 & 3 \\
LOAD R1, 4(R2)  & 8+5+5+14  = 32 & 4 \\
STORE A, R2     & 8+14+5    = 27 & 4 \\
STORE (R1), R2  & 8+5+5     = 18 & 3 \\
STORE 4(R1), R2 & 8+5+14+5  = 32 & 4 \\
BEZ R1 {\it label} & 8+5+14 = 27 & 4 \\
\end{tabular}
\footnotetext{This is a pointless instruction, but seems to
be legal by the specification.}

\item%(b)

I'll note that this code could be more asymptotically efficiently
implemented by using repeated squaring to calculate the closed-form
solution of the sequence defined by $a_n = a_{n-2} - a_{n-1} + (n-2)$,
$$ a_n = A \left(\frac{-1+\sqrt{5}}{2}\right)^n
         + B \left(\frac{-1-\sqrt{5}}{2}\right)^n + n - 3 $$
where
$$ A = \frac{1}{2} \left(a_0 + 3 - \frac{1}{\sqrt{5}}(a_0+3b_0+18)\right) $$
$$ B = \frac{1}{2} \left(a_0 + 3 + \frac{1}{\sqrt{5}}(a_0+3b_0+18)\right) $$
That said, given that the architectures described have no multiply
instructions nor support for floating-point, such an implementation
would probably by less efficient for most ``reasonable'' $n$, and is
probably not what you're looking for anyway.  So I will present a
more-or-less direct translation of the given code.

I'm assuming that ``most memory-efficient'' means ``least bytes
transferred during execution'', as opposed to ``smallest code''.

For the register-memory architecture, the best code is achieved by
using only registers within the loop body, since memory accesses are
expensive (regardless of architecture).
\begin{verbatim}
        SUB R1, R1              ; R1 == i
        MOVE R2, N              ; R2 == n
        MOVE R3, A              ; R3 == a
        MOVE R4, B              ; R4 == b
        SUB R5, R5              ; R5 == 0
        MOVE R6, #1             ; R6 == 1
                                ; R9 == t
                                ; R10+ == scratch
loop:
        MOVE R10, R1
        CMP R10, R2
        BEZ R10 end             ; if (i >= n) goto end
        MOVE R9, R4
        SUB R9, R3              ; t <- b - a
        MOVE R4, R3
        ADD R4, R1              ; b <- a + i
        MOVE R3, R9             ; a <- t
        ADD R1,R6               ; i <- i + 1
        BEZ R5 loop             ; goto loop
end:
        MOVE I, R1
        MOVE A, R3
        MOVE B, R4
        MOVE T, R3
\end{verbatim}

For the register-register architecture, the best code is:
\begin{verbatim}
        SUB R1, R1, R1          ; R1 == i
        LOAD R2, N              ; R2 == n
        LOAD R3, A              ; R3 == a
        LOAD R4, B              ; R4 == b
        SUB R5, R5, R5          ; R5 == 0
        ADD R6, R5, #1          ; R6 == 1
                                ; R7 == a'
loop:
        CMP R8, R1, R2
        BEZ R8 end              ; if (i >= n) goto end
        SUB R7, R4, R3          ; a' <- b - a
        ADD R4, R3, R1          ; b  <- a + i
        ADD R1, R1, R6          ; i  <- i + 1
        CMP R8, R1, R2
        BEZ R8 middleend        ; if (i >= n) goto middleend
        SUB R3, R4, R7          ; a  <- b - a'
        ADD R4, R7, R1          ; b  <- a' + i
        ADD R1, R1, R6          ; i  <- i + 1
        BEZ R5 loop             ; goto loop
middleend:
        ADD R3, R7, R5          ; a <- a'
end:
        STORE I, R1
        STORE A, R3
        STORE T, R3
        STORE B, R4
\end{verbatim}

In this version, the loop is unrolled twice to acheive better register
usage.

In either case, the loop could be unrolled an unbounded number of
times to shave off a little time for each unrolling, but I figured an
infinite amount of paper would be a little too much to hand in.

\item%(c)

The memory bandwidth used by the register-memory architecture comes
out to be $34 + 10(n+1) + 22n + 32 = 76 + 32n$ bytes.  For $n = 10$,
the total memory bandwidth used is 396 bytes.

The memory bandwidth used by the load-store architecture comes out to
be $35 + 7(\lfloor\frac{n}{2}\rfloor + 1) + 16\lceil\frac{n}{2}\rceil
    + 13\lfloor\frac{n}{2}\rfloor
    + 3(\lceil\frac{n}{2}\rceil - \lfloor\frac{n}{2}\rfloor) + 32
  = 74 + 17n + 2\lceil\frac{n}{2}\rceil$ bytes.
For $n = 10$, the total memory bandwidth used is 254 bytes.

As a quick analysis of the results:  both modes have almost the same
constant bandwidth; however, the two-operand instruction format
requires each instruction to destroy the contents of one ``useful''
register.  Hence, more ``useless'' MOVE instructions must be used to
move data from register to register.  Thus, the more flexible
three-operand architecture has a higher ``computation density per
instruction''.

However, I predict that when the number of registers allocated (by a
compiler, or by hand) reaches the number of physical registers in the
machine, the register-register architecture will become more
``destructive'' and the performance gap will close to some degree
(although I doubt it will close entirely).

\item%(d)

\begin{verbatim}
        ldc #0
        istore 1
        goto cmp
loop:
        iload 4
        iload 3
        isub
        iload 3
        iload 1
        iadd
        istore 4
        istore 3
        iload 1
        ldc #1
        iadd
        istore 1
cmp:
        iload 1
        iload 5
        ifcmplt loop
        iload 2
        istore 4
\end{verbatim}

\item%(e)

The macro BEGIN should be placed at the beginning of the procedure,
since it sets up various internal state variables.

I assume that STACK\_BOT points to an empty, allocated memory cell in
the stack, but that STACK\_TOP points above the stack (i.e. to an
unallocated cell).  I'll note that the construct LVn used below is not
legal macroese, but since there isn't a good alternative, I'll use it,
with the obvious meaning.

\begin{verbatim}

; memory bandwidth = 3+5+5+3+8+8+3+3 = 38 bytes
.macro BEGIN
        SUB R1, R1, R1          ; R1 = 0
        ADD R7, R1, #1          ; R7 = 1
        ADD R8, R1, #4          ; R8 = 4
        ADD R9, R8, R8          ; R9 = 8
        LOAD R2, STACK_TOP      ; R2 = STACK_TOP
        LOAD R3, STACK_BOT      ; R3 = STACK_BOT
        ADD R4, R1, R3          ; R4 = sp (points to first free cell)
        ADD R6, R3, R8          ; R6 = STACK_BOT + 4 bytes
                                ; R10+ = scratch
.end macro

; memory bandwidth = 3+4+5+7+3 = 22 bytes
.macro ldc(c)
        CMP R10, R4, R2
        BEZ R10 STACK_OVER
        ADD R10, R1, c
        STORE (R4), R10
        ADD R4, R4, R8
.end macro

; memory bandwidth = 3+4+8+7+3 = 25 bytes
.macro iload(n)
        CMP R10, R4, R2
        BEZ R10 STACK_OVER
        LOAD R10, LVn
        STORE (R4), R10
        ADD R4, R4, R8
.end macro

; memory bandwidth = 3+4+3+7+8 = 25 bytes
.macro istore(n)
        CMP R10, R3, R4
        BEZ R10 STACK_UNDER
        SUB R4, R4, R8
        LOAD R10, (R4)
        STORE LVn, R10
.end macro

; memory bandwidth = 3+4+8+8+8+8 = 39 bytes
.macro swap
        CMP R10, R6, R4
        BEZ R10 STACK_UNDER
        LOAD R10, -4(R4)
        LOAD R11, -8(R4)
        STORE -8(R4), R10
        STORE -4(R4), R11
.end macro

; memory bandwidth = 3+4+3+8+7+3+8 = 36 bytes
.macro iadd
        CMP R10, R6, R4
        BEZ R10 STACK_UNDER
        SUB R4, R4, R8
        LOAD R10, -4(R4)
        LOAD R11,   (R4)
        ADD R10, R10, R11
        STORE -4(R4), R10
.end macro

; memory bandwidth = 3+4+3+8+7+3+8 = 36 bytes
.macro isub
        CMP R10, R6, R4
        BEZ R10 STACK_UNDER
        SUB R4, R4, R8
        LOAD R10, -4(R4)
        LOAD R11,   (R4)
        SUB R10, R10, R11
        STORE -4(R4), R10
.end macro

; memory bandwidth = 3+4+3+7+8+3+3+4 = 35 bytes
.macro ifcmplt(label)
        CMP R10, R6, R4
        BEZ R10 STACK_UNDER
        SUB R4, R4, R9
        LOAD R10,  (R4)
        LOAD R11, 4(R4)
        CMP R10, R10, R11
        SUB R10, R7, R10
        BEZ R10 label
.end macro

; memory bandwidth = 4 bytes
.macro goto(label)
        BEZ R1 label
.end macro
\end{verbatim}

The memory bandwidth used by the expanded java program is
$89 + 330n + 85(n+1) + 50 = 224 + 415n$ bytes.  For $n = 10$, this
gives a total memory bandwidth taken of 4374 bytes.

\item%(f)

The most obvious improvement to generated code performance would be
the elimination of overflow and underflow checks.  The bytecode
verifier must know the exact depth of the stack at any given point of
the code, and so the overflow and underflow checks can be done at
compile time.  Also, the exact stack offset of the operands (top of
the stack) to each bytecode can be determined by the verifier pass and
statically set in the generated code, eliminating the need to
explicitly manage the stack at all.

Another optimization that can be performed is the allocation registers
to local variable slots; in this way, iloads and istores can be
eliminated entirely (so long as the registers are loaded from the
memory slots at the beginning of the code fragment and stored back at
the end).  In addition, if the preceding optimization is implemented,
registers can also be allocated to stack slots, eliminating the need
for an in-memory stack entirely.

Another ``peephole'' optimization, applicable after the previous two
optimizations, would be to determine when registers were simply being
moved to other registers, and perform copy propagation and dead code
elimination to remove some unnecessary register-register moves.  A
similar pass of constant propagation and dead code elimination would
eliminate unnecessary constant loads, making the constants into
immediate operands to the native instructions.

\end{enumerate}
\clearpage



\section*{Problem 1-2}
\begin{enumerate}

\item%(a)

\begin{verbatim}

storedaccum:
        .word 0            ; temporary slot for accumulator


.macro ADDind(n)
        STORE storedaccum  ; keep old accum around
        CLEAR
        ADD n              ; accum <- M[n]
        STORE addlabel     ; M[addlabel] <- 'ADD M[n]'
        CLEAR
        ADD storedaccum    ; accum <- old accum
addlabel:
        ADD 0              ; 'ADD M[n]': accum <- accum + M[M[n]]
.end macro


storetmpl:
        STORE 0

.macro STOREind(n)
        STORE storedaccum  ; keep old accum around
        CLEAR
        ADD storetmpl      ; accum <- 'STORE 0'
        ADD n              ; accum <- 'STORE' + M[n]
        STORE storelabel   ; M[storelabel] <- 'STORE M[n]'
        CLEAR
        ADD storedaccum    ; accum <- old accum
storelabel:
        STORE 0            ; 'STORE M[n]': M[M[n]] <- accum
.end macro


bgetmpl:
        BGE 0

.macro BGEind(n)
        STORE storedaccum  ; keep old accum around
        CLEAR
        ADD bgetmpl        ; accum <- 'BGE 0'
        ADD n              ; accum <- 'BGE' + M[n]
        STORE bgelabel     ; M[bgelabel] <- 'BGE M[n]'
        CLEAR
        ADD storedaccum    ; accum <- old accum
bgelabel:
        BGE 0              ; 'BGE M[n]': If (accum) >= 0 then PC <- M[n]
.end macro


blttmpl:
        BLT 0

.macro BLTind(n)
        STORE storedaccum  ; keep old accum around
        CLEAR
        ADD blttmpl        ; accum <- 'BLT 0'
        ADD n              ; accum <- 'BLT' + M[n]
        STORE bltlabel     ; M[bltlabel] <- 'BLT M[n]'
        CLEAR
        ADD storedaccum    ; accum <- old accum
bltlabel:
        BLT 0              ; 'BLT M[n]': If (accum) >= 0 then PC <- M[n]
.end macro
\end{verbatim}

\item%(b)

For the special case of two arguments and one return value: in
overview, the arguments are placed in the two slots following the jump
instruction; the subroutine reads the arguments from there, and
processes them; the subroutine places the return value in the first
argument slot; and then the subroutine jumps to the return address.

More specifically, the calling code looks like this:
\begin{verbatim}
        ; place first arg in accum
        STORE arg1
        ; place second arg in accum
        STORE arg2
        CLEAR
        ADD return_address
        BGE subroutine
arg1:   .word 0
arg2:   .word 0
return_address:
        ; control returns here, with accumulator cleared to zero
        ADD arg1
        ; return value is now in accumulator
\end{verbatim}

The subroutine template would look like this:
\begin{verbatim}
rastore:
        .word 0         ; storage space for return address
arg1addr:
        .word 0         ; return_address - 2
arg2addr:
        .word 0         ; return_address - 1
one:
        .word 1         ; constant 1
subroutine:
        STORE rastore
        SUB one
        STORE arg2addr
        SUB one
        STORE arg1addr
        ; execute subroutine code here
        ; when arg 1 is needed, add it in to the accumulator like so:
        ADDind arg1addr
        ; when arg 2 is needed, add it in to the accumulator like so:
        ADDind arg2addr
        ; ... etc ...
        ; finish subroutine code; return value is in accum
        STOREind arg1addr
        CLEAR
        BGEind rastore
\end{verbatim}

The fact that subroutines cannot call other subroutines frees us from
the obligation of maintaining a stack, which simplifies the
implementation considerably.  The caller simply places the arguments
in the two words after the jump, places the return address (the
address right {\em after} the two arguments) into the accumulator, and
uses BGE to jump to the subroutine head.  (Since addresses are always
positive, the jump will always happen.)  The subroutine then stores
the return address and calculates and stores the addresses of the two
arguments.  (Alternatively, it could just calculate the addresses
once, and store the values, but then the arg1addr would need to be
recalculated later.)  When the subroutine is finished, it stores the
return value to the location of the first argument, clears the
accumulator, and jumps to the location specified by the (stored)
return address.

I'll note that any given implementation of a subroutine using this
calling convention could be optimized significantly by expanding out
the indirection macros, streamlining various parts of the code, and
using self-modifying code freely (i.e. without using the abstraction
barrier imposed by the indirection macros); I'll refrain from doing
so, on the assumption that readability is more important.

This implementation of {\bf sum(array, n)} would be called by placing
a pointer to {\bf array} in the first argument and {\bf n} in the
second argument.
\begin{verbatim}
rastore:
        .word 0
arg1addr:
        .word 0
arg2addr:
        .word 0
one:
        .word 1
arrayend:
        .word 0
total:
        .word 0

sum:
        STORE rastore
        SUB one
        STORE arg2addr
        SUB one
        STORE arg1addr

        STORE addarrayaddr      ; M[addarrayaddr] <- 'ADD <addr of arg1>'
        CLEAR
addarrayaddr:
        ADD 0                   ; accum <- array (== arg1)
        STORE addarrayval       ; M[addarrayval] <- 'ADD array'

                                ; accum == array
        ADDind arg2addr         ; accum <- array + n
        STORE arrayend

loop:
        CLEAR
        ADD total               ; accum <- M[total]
addarrayval:
        ADD 0                   ; accum <- M[total] + M[array+i]
        STORE total             ; M[total] <- accum
        CLEAR
        ADD addarrayval
        ADD one                 ; accum <- 'ADD array+i' + 1
        STORE addarrayval       ; M[addarrayval] <- accum
        SUB arrayend            ; accum <- (array+i) - (array+n)
        BLT loop                ; if (i < n) goto loop
        ; CLEAR not needed because when the loop terminates, accum == 0
        ADD total
        STOREind arg1addr       ; retval <- M[total]
        CLEAR
        STORE total             ; M[total] <- 0
        BGEind rastore          ; return
\end{verbatim}

This implementation uses explicitly self-modifying code in two places:
first (at addarrayaddr), to get the pointer to the array into the
accumulator, and second (at addarrayval in the loop body), to get the
value at the current index of the array into the accumulator.  The ADD
instruction at addarrayval is incremented once on every iteration
through the loop body; the loop terminates when the instruction is
greater than a pointer to the end of the array.  A total of 10
instructions are executed on each iteration of the loop.

To generalize the calling convention to $n$ arguments and $m$ return
values, reserve $max(m,n)$ words of memory directly after the jump to
the subroutine, and place the return address directly after the
reserved space.  The caller places the arguments into the first $n$
words after the jump, and the subroutine retrieves them from there by
fixed offsets from the return address.  Upon return, the subroutine
places the return values into the first $m$ words reserved, clears the
accumulator, and jumps to the return address.

\item%(c)

Subroutine calls can be made to other subroutines from within a
subroutine, but recursion of any form is not allows.  Thus, a
subroutine {\it foo} would be permitted to call a subroutine {\it
bar}, but only if {\it bar} (and any subroutines {\it bar} calls) does
not call {\it foo}.  Of course, {\it foo} is not permitted to call
itself.

\item%(d)

A recursive mode of operation requires the existence of a stack in
memory.  The easiest way to accomplish this is to have a global stack
pointer variable and a globally allocated ``sufficiently large'' stack
area.  (Of course, this creates the possibility of a stack overflow,
but given limited memory this is always the case.  I will ignore the
case of stack overflow, as is usually done, although it would be
fairly trivial to add checks for it explicitly into the code.)

To call a subroutine, the caller pushes the first argument onto the
stack, pushes the second argument onto the stack, puts the return
address (which is the address of the instruction directly after the
call) into the accumulator, and jumps to the subroutine using the BGE
opcode (which will always cause a jump, since addresses are always
positive).  The subroutine pushes the return address onto the stack;
it may also reserve space on the stack for local variables.  It then
executes its body, using fixed offsets from the stack pointer to use
local variables and arguments.  (Whenever the subroutine calls another
subroutine, all local variables must be stored on the stack and
restored after the call returns.)  When the subroutine is finished, it
deallocates the local variable space, pops the return value (saving it
for use in the return), deallocates the argument space, and pushes the
return value onto the stack.  It then jumps to the return address.
The caller can then retrieve the return value by popping the stack.

The macros for stack manipulation look like this:
\begin{verbatim}

; sp is a global stack pointer, initialized to point at the top of
; memory.  The stack grows downward from the top of memory; sp always
; points to the first unallocated word.
sp:     .word top_of_memory

; one is, as usual, simply a memory cell which contains the number 1.
one:    .word 1

; PUSH pushes the accum onto the stack; accum is destroyed in the process.
.macro PUSH
        STOREind sp     ; M[M[sp]] <- accum
        CLEAR
        ADD sp
        SUB one
        STORE sp        ; M[sp] <- M[sp] - 1
.end macro

; POP pops the top of the stack into accum.
.macro POP
        CLEAR
        ADD sp
        ADD one
        STORE sp        ; M[sp] <- M[sp] + 1
        CLEAR
        ADDind sp       ; accum <- M[M[sp]]
.end macro

; RESERVE(n) reserves n words of stack space for local variables.
.macro RESERVE(n)
valuen:
        ADD n           ; 'ADD n' == '.word n'; would prefer not
                        ; to execute it, but there's no choice in a macro.
                        ; This would fail in a memory-managed architecture.
                        ; It could be bypassed with a jump but it's quicker
                        ; just to throw the result away.
        CLEAR
        ADD sp
        SUB valuen
        STORE sp        ; M[sp] <- M[sp] - n
.end macro

; UNRESERVE(n) pops n words from the stack, discarding their values.
.macro UNRESERVE(n)
valuen:
        ADD n           ; Likewise, useless instruction used as memory slot.
        CLEAR
        ADD sp
        ADD valuen
        STORE sp        ; M[sp] <- M[sp] + n
.end macro

; GETSTACK(n) gets the value on the stack n words from sp.
.macro GETSTACK(n)
addtmpl:
        ADD n           ; Template for add instruction.
                        ; Like in RESERVE, useless to execute, but we
                        ; can't ask this assembler to place it elsewhere.

        CLEAR
        ADD sp
        ADD addtmpl
        STORE addval    ; M[addval] <- 'ADD M[sp]+n'
        CLEAR
addval:
        ADD 0           ; accum <- M[M[sp] + n]
.end macro
\end{verbatim}

The calling code looks like this:
\begin{verbatim}
        ; place first arg in accum
        PUSH
        ; place second arg in accum
        PUSH
        CLEAR
        ADD return_address
        BGE subroutine
return_address:
        ; control returns here
        POP
        ; return value is now in accumulator
\end{verbatim}

The subroutine template would look like this:
\begin{verbatim}
; These words can be shared among subroutines.
bgetmpl:
        BGE 0           ; template for BGE instructions
retval:
        .word 0         ; temp space for storing return val

subroutine:
        ADD bgetmpl
        PUSH            ; put 'BGE <return address>' on stack
        RESERVE n       ; choose n == number of locals

        ; Execute subroutine code here
        ; When local #1, #2, #3, etc are needed, use e.g.
        ; GETSTACK 1    ; put local #1 in accum
        ; To get argument 1, use
        ; GETSTACK n+3  ; where n == number of locals
        ; To get argument 2, use
        ; GETSTACK n+2
        ; ... etc ...
        ; Finish subroutine code; return value is in accum.
        STORE retval

        GETSTACK n+1    ; where n == number of locals
                        ; now accum == 'BGE <return address>'
        STORE returnbge ; creates return instruction
        UNRESERVE n+3   ; remove all locals as well as return addr and args

        CLEAR
        ADD retval
        PUSH            ; push return value onto stack

        CLEAR
returnbge:
        BGE 0
\end{verbatim}

This template can be fairly simply converted into an implementation of
{\bf sum}.  I assume the common variables {\bf bgetmpl}, {\bf retval},
and {\bf one} exist elsewhere.
\begin{verbatim}
; local temp storage (not preserved across calls)
total:
        .word 0
ptr:
        .word 0

sum:
        ADD bgetmpl
        PUSH            ; put 'BGE <return address>' on stack
        ; no locals need be stored over the recursive call,
        ; so no space need be reserved for locals.  Hence nlocals == 0.

        ; first check if n <= 0: if so, return 0.
        GETSTACK 2      ; accum <- n
        SUB one
        BGE recurse

        ; if we've reached here, n <= 0.  Return 0.
        CLEAR
        BGE return

recurse:
        ; if we're here, n > 0.  Recurse and return the computed total.
        GETSTACK 3      ; accum <- array
        PUSH

        ; the stack offset is increased by one due to the preceding PUSH.
        GETSTACK 3      ; accum <- n
        SUB one         ; accum <- n - 1
        PUSH

        CLEAR
        ADD return_addr
        BGE sum         ; recursive call
return_addr:
        POP             ; accum <- sum(array, n-1)
        STORE total     ; M[total] <- accum

        GETSTACK 3      ; accum <- array
        STORE ptr

        GETSTACK 2      ; accum <- n
        SUB one
        ADD ptr         ; accum <- array + n - 1
        STORE ptr       ; M[ptr] <- accum

        CLEAR
        ADDind ptr      ; accum <- M[array + n - 1]
        ADD total       ; accum <- M[array + n - 1] + sum(array, n-1)

return:
        STORE retval
        GETSTACK 1      ; accum <- 'BGE <return address>'
        STORE returnbge
        UNRESERVE 3

        CLEAR
        ADD retval
        PUSH

        CLEAR
returnbge:
        BGE 0
\end{verbatim}

For clarity, this is roughly an implementation of this low-level C code:
\begin{verbatim}
int accum, total, ptr;
int sum(int *array, int n) {
        if (n - 1 < 0) {
                accum = 0;
                goto return_accum;
        }

        total = sum(array, n - 1);
        ptr = array + n - 1;
        accum = *(array + n - 1) + total;

return_accum:
        return accum;
}
\end{verbatim}

To extend this calling convention to an arbitrary number of arguments
and return values, the caller can simply push any number of arguments
onto the stack (although the number of arguments must be fixed for a
given subroutine); the subroutine can push any number of return values
onto the stack before returning.

\end{enumerate}
\newpage



\section*{Problem 1-3}
\begin{enumerate}

\item%(a)

{\bf Load Rule for AX':} \\
Sys(Proc(ia, rf, im), dm)
    \mbox{\it if } im[ia] = r := Load(r$_a$, v$_{offset}$) \\
$\to$ Sys(Proc(ia+1, rf[r := dm[a]], im), dm)
    \mbox{\it where } a = rf[r$_a$] + v$_{offset}$

{\bf Op Rule for AX':} \\
Sys(Proc(ia, rf, im), dm)
    \mbox{\it if } im[ia] = r := Op(r$_{a1}$, c$_a$) \\
$\to$ Sys(Proc(ia+1, rf[r := v], im), dm) \\
    \mbox{\it where } v = \underbar{Op}(dm[a], dm[c$_a$])
    \mbox{\it where } a = rf[r$_{a1}$]

\item%(b)

{\bf Pop Rule, non-empty case:} \\
Proc(ia, rf, Slot(v) ; s, im)
    \mbox{\it if } im[ia] = r := Pop \\
$\to$ Proc(ia+1, rf[r := v], s, im)

{\bf Push Rule:} \\
Proc(ia, rf, s, im)
    \mbox{\it if } im[ia] = Push(r) \\
$\to$ Proc(ia+1, rf, Slot(rf[r]) ; s, im)

\item%(c)

The ultimate problem with implementing a stack in hardware is that a
true stack can grow unboundedly; no matter how much silicon you devote
to holding stack elements, there is always a sequence of instructions
that will overflow the stack.  However, the stack described by the TRS
is, in fact, truly unbounded.  Thus, no bounded physical hardware
system can implement the system {\it exactly} as described by the TRS.

\end{enumerate}
\newpage

\end{document}
