Eval( ) in hardware
lecture 4 Digital systems 2004
The eval function that simulates the execution of
n-code must be
implemented in terms of circuits eventually. This lecture shows
how the eval function is changed step-by-step to model a real
hardware. Once the transformed eval() is close to a register
transfer level (RTL), the design of data path and control unit will
emerge. An implementation of control unit will be
illustrated using microprogramming method.
How eval( ) work?
This will be illustrate using a short example.
(def main () () (+ 1 2))
=> (fun.1.1 (+ lit.1
lit.2))
The above machine program requires three instructions: fun, add,
lit. The eval function showing only those three instructions is
as follows:
exp
eval2(exp e){
. . .
if( e == NIL)
return NIL;
if( !
isAtom(e) ) {
e1 = tail(e); // (arg1 arg2 ...)
e2 = tail(e1); // (arg2...) e2 may be NIL
e = head(e);
}
// it is a dot-pair
decode(e,&op,&arg);
switch(op){
case xLIT:
return arg;
case xGET:
return SS[fp-arg];
. . .
case xADD:
return eval2(arg1(e)) + eval2(arg2(e));
. . .
case xFUN:
arity = arg >> 8;
fs = arg & 0xff;
k = fs-arity+1;
SS[sp+k] = fp; // new frame
fp = sp+k;
sp = fp;
v = eval2(arg1(e));
sp = fp-fs-1; // delete
frame
fp = SS[fp];
return v;
. . .
}
The eval function is evolved towards modeling eval() in hardware with
the following transformation:
- absorb evalAtom(), use only one switch()
- inline arg1() arg2() and reduce local var fs, k
are embeded;
op,arg are embeded so totally only 4 locals: e, e1, e2, v.
- unwind f(g(x)) to a = g(x), f(a)
The final result is eval4() shown below:
exp eval4(exp e){
int
e1, e2, v;
int
op, arg, fs, k;
if(
e == NIL) return NIL;
if(
! isAtom(e) ) {
e1 = tail(e);
// (arg1 arg2 ...)
e2 = tail(e1);
// (arg2...) e2 may be NIL
e = head(e);
}
// it is a dot-pair
decode(e,&op,&arg);
switch(op){
case
xLIT: return arg;
case
xGET:
v = SS[fp-arg];
return v;
. . .
case
xADD:
e1 = head(e1);
e1 = eval4(e1);
e2 = head(e2);
e2 = eval4(e2);
v = e1 + e2;
return v;
. . .
case
xFUN:
// fs, k should be compute by
compiler
// k = (arg & 0xff)-(arg
>> 8)+1
// fs = (arg & 0xff)-1
fs = arg & 0xff;
k = arg >> 8;
// already recode
SS[sp+k] = fp;
// new frame
fp = sp+k;
sp = fp;
e1 = head(e1);
v = eval4(e1);
sp = fp - fs;
// delete frame
fp = SS[fp];
return v;
. . .
}
How
to model recursion
Recusion can be modelled using explicit stack to save
local context and using loop and goto for
control flow. See the following example from recursive factorial()
int fac( int n){
if(
n == 0 ) return 1;
return n * fac(n - 1);
}
fac() is modelled using non-recursive version as follows:
void ent(int n, int st){
usp
+= 2;
ustack[usp] = st;
ustack[usp-1] = n;
}
void leave(int *n, int
*st){
*st
= ustack[usp];
*n =
ustack[usp-1];
usp
-= 2;
}
int retval;
int fac( int n ){
int
state;
state = 1;
ent(0,0);
begin:
switch(state){
case
0: goto at0; break;
case
1: goto at1; break;
case
2: goto at2; break;
}
at1:
if(
n == 0 ){
retval = 1;
leave(&n,&state);
goto begin;
}
ent(n,2);
n =
n-1;
goto
begin;
at2:
retval = n * retval;
leave(&n,&state);
goto
begin;
at0:
return retval;
}
A context stack is used to store the current context (ustack[.]).
Two functions are defined to manipulate the context stack: ent() and
leave(). To enter a recursion, the current context (local var,
return address)
must be saved, the actual parameter is passed (n = n - 1) and go
to the beginning of function to execute. To leave (return) from a
recursion, the return value is passed (to a global variable "retval")
and the previous context is restored. The continuation (which
line of program to be continued) is controlled by the parameter
"state", with is implemented as "goto" in C.
eval4() goes through a similar transformation to render it to be
modelled as a hardware circuit. (see "evalm()" which is partially
transformed for the instructions: fun, add, lit)
recode
fun.a.v
To simplify execution of the control unit for function
call the header
fun.a.v (a is arity, v is formal+local) is recoded into fun.k.fs where
k = v - a + 1, k is the offset of fp from sp for creating a new frame,
fs = v - 1, fs is the offset of sp from fp for deleting the current
frame. This is done by the object code loader. It is
independent from the n-code because this depends on how the activation
record is implemented, hence it is specific to the simulator.
This is the actual sequence of "fun":
case xFUN:
fs = arg & 0xff;
k = arg >> 8;
// already recode
M[sp+k] = fp;
// new frame
fp = sp+k;
sp = fp;
e1 = head(e1);
v = eval4(e1);
sp = fp - fs;
// already recode
return v;
Data
path
registers: e, e1, e2, fp, sp, rv, rt, mar
alu: add, sub, eq, lt, gt, inc, pass1, pass2, isnil, isatom
output of alu is stored in T (tbus)
mux1(mbus,tbus) ->
input of registers
mux2(reg,arg,fs,k,nil) ->
input of alu
register selectors:
xR, yR select registers to alu and mux2
dR select registers to be written, input
from mux1
Microprogram
This is a microprogram implementing evalmp() with 3
instructions: lit,
add, fun. Compare this sequence with eval4().
.m
.. start of microprogram
.. <start>
.. if e = NIL return NIL
:begin
xe isnil jT /exit ;
xe isatom jT /decode ;
.. e1 = tail e
xe inc lmar ;
mR sM de1 ;
.. e2 = tail e1
xe1 inc lmar ;
mR sM de2 ;
.. e = head e
xe pass1 lmar ;
mR sM de ;
.. <decode>
:decode
switchop ;
.. <xlit> retval
= arg
:xlit
sarg pass2 sT drv ret ;
.. <xadd>
e1 = head e1
:xadd
xe1 pass1 lmar ;
mR sM de1 ;
.. e1 = eval e1
save ;
xe1 pass1 sT de recur ;
xrv pass1 sT de1 ;
.. e2 = head e2
xe2 pass1 lmar ;
mR sM de2 ;
.. e2 = eval e2
save ;
xe2 pass1 sT de recur ;
xrv pass1 sT de2 ;
.. retval = e1 +
e2
xe1 ye2 ss2 add sT drv ret ;
.. <xfun>
.. SS[sp+k] =
fp; // new frame
:xfun
xsp sk add lmar ;
xfp
pass1 mW ;
.. fp = sp+k;
xsp
sk add sT dfp ;
.. sp = fp;
xfp
pass1 sT dsp ;
.. e1 = head(e1);
xe1
pass1 lmar ;
mR
sM de1 ;
.. retval = eval4(e1);
save
;
xe1
pass1 sT de recur ;
.. sp = fp -
fs; // delete frame
xfp
sfs sub sT dsp ;
.. fp = SS[fp];
xfp
pass1 lmar ;
mR
sM dfp ret ;
..
<exit> retval = NIL
:exit
snil pass2 sT drv ret ;
.e
29 Nov 2004
P. Chongstitvatana