Previous: Appendix A Idealized RISC Up: Deferred Compilation:
The Automation of Run-Time Code Generation
vm-mult(v, m, a) =
if m = nil then reverse(a, nil)
else let prod = dotprod(v, car m, nil)
in vm-mult(v, cdr m, cons(prod, a))
dotprod(v1, v2, a) =
if v1 = nil then a
else dotprod(cdr v1, cdr v2, a + car v1 * car v2)
The functions are implemented using tail-recursion to reduce
procedure-call overhead; the accumulator can be viewed as an explicit
encoding of call frames, the reversal of which corresponds to a
sequence of procedure returns (The code for reverse has been
omitted). vm-mult computes the dot product of the specified
vector with each row of the given matrix and accumulates the results
in a list. dotprod simply sums the products of corresponding
elements of two vectors.
FABIUS creates memoized code generators for both vm-mult and dotprod; previously generated code for a particular vector is reused rather than regenerated. An inlining code generator is also created for dotprod; it is invoked by the memoized dotprod generator to generate code for its recursive tail-call (comments added):
L9: beq r1, r0, L10 ; if v1 = nil goto L10
ld r2, (r1) ; x1 = car(v1)
ld r1, 4(r1) ; v1 = cdr(v1)
emit ld r3, (r1) ; emit "x2 = car(v2)"
emit ld r1, 4(r1) ; emit "v2 = cdr(v2)"
emit move r4, [r2] ; emit "tmp = [x1]"
emit mul r3, r4, r3 ; emit "prod = tmp * x2"
emit add r2, r2, r3 ; emit "a = a + prod"
jmp L9 ; goto L9
L10: emit move r1, r2 ; emit "result = a"
ret ; return
The first argument vector is supplied in r1. The run-time-generated code expects the second argument vector in r1 and the accumulator in r2. If the first argument vector is [1,2,3], the following code is generated at run time:
ld r3, (r1) ; x2 = car(v2)
ld r1, 4(r1) ; v2 = cdr(v2)
move r4, 1 ; tmp = 1
mul r3, r4, r3 ; prod = tmp * x2
add r2, r2, r3 ; a = a + prod
ld r3, (r1)
ld r1, 4(r1) ; etc.
move r4, 2
mul r3, r4, r3
add r2, r2, r3
ld r3, (r1)
ld r1, 4(r1)
move r4, 3
mul r3, r4, r3
add r2, r2, r3
move r1, r2 ; result = a
