[Page 79]
69 9. Example: Compilation of Iterative Factorial Here we shall provide a complete example of the compilation of a simple function IFACT (iterative factorial), to show what quantities are computed in the course of analyzing the code. We shall need some notation for the data structures involved. Every node of the program is represented by a small data structure which has a type and several named components. (In the actual implementation, a node is represented as two such structures; one contains named components common to all program nodes, and the other contains components specific to a given node type. We shall gloss over this detail here.) For example, a LAMBDA-expression is represented by a structure of type LAMBDA with components named UVARS (user variable names), VARS (the alpha-converted names), BODY (the node representing the body). ENV (the environment of the node), and so on. we shall represent a data structure as the name of its type, with the components written below it and indented, with colons after each component name.
For example:
LAMBDA UVARS: (A B) VARS: (VAR-43 VAR-44) BODY: COMBINATION ARGS: VARIABLE VAR: F VARIABLE VAR: VAR-44 VARIABLE VAR: VAR-43 Notice that the value of a component may itself be a structure. These structures are always arranged in a tree, so no notation for cycles will be needed. In the case where a component contains a list of things, we will write the things as a LISP list unless the things are structures, in which case we will simply write
[Page 80]
70 them in a vertical stack, as shown in the example above. To conserve space, in any single diagram we will show only the named components of interest.
Components may seem to appear and then disappear in the series of diagrams, but in practice they all exist simultaneously.
The source code for our example:
(DEFINE IFACT (LAMBDA (N) (LABELS ((F (LAMBDA (M A) (IF (= H 0) A (F N 1)))) (F (- H 1) (* N A)))))) The alpha-conversion process copies the program and produces a tree of structures. All the bound variables are renamed, and VARIABLE nodes refer to these new names. The GLOBALP component in a VARIABLE node is non-NIL iff the reference is to a global variable. The ENV component is simply an a-list relating the user names of variables to the new names; this a-list is computed during the conversion as the new names are created at LAMBDA, LABELS, and CATCH nodes.
LAHBDA ENV: () UVARS: (N) VARS: (VAR-1) BODY:
LABELS Env; ((n VAR-l)) urnvARs: (F) rnvansz (FNVAR-Z) rno£rs= LAMBDA ENV: ((F FNVAR-2) (N VAR-1)) UVARS: (M A) VARS: (VAR-3 VAR-4) BODY: IF . suv; ((A vnu-4) (n VAR-3) (F rnvnn-2) (N van-1)) PRED: COMBINATION ENV: ff* (see below) ARES: VARIABLE
[Page 81]
71 ENV:
VAR:
GLOBALP:
VARIABLE ENV:
VAR:
GLOBALP:
CONSTANT ENV:
VALUE:
CON: VARIABLE ENV: *** VAR: VAR-4 GLOBALP: NIL ALT: COMBINATION ENVI ii* ARGS: VARIABLE ENV:
VAR:
GLOBALP:
COMBINATION ENV:
ARGS:
COMBINATION ENV:
ARGS:
BODY: COMBINATION ENV: ((F FNVAR-2) (N VAR-I)) ARGS: VARIABLE ENV: ((F FNVAR-2) (N VAR VAR: FNVAR-Z GLOBALP: NIL iii I
T can VAR-3 NIL nan 0
- fa FNVAR-2 NIL til VARIABLE ENV:
VAR:
GLOBALP:
VARIABLE ENV:
VAR:
GLOBAL?
CONSTANT ENV:
VALUE:
- aa VARIABLE ENV:
VAR:
GLOBALP VARIABLE ENV:
VAR:
GLOBALP VARIABLE ENV:
VAR:
GLOBALP° l)) iii T iii VAR-NIL ill I iii i T its VAR-NIL aaa VAR-NIL 3
3 4
[Page 82]
72 vAn1AuLe env: ((r FNVAR-2) (n VAR-1)) van; van-1 sLoaALr; nxt cous1ANr env: ((r rnvAn-2) (N VAR-l)) vALu£: 1 The reader is asked to imagine that the expression ((A VAR-4) (M VAR-3) (F FNVAR-2) (N VAR-1)) occurs where *x* appears in the diagram. It should be clear how the ENV components are computed on the basis of variables bound at the LAMBDA and LABELS nodes. The ENV information propagates down the tree to VARIABLE nodes, where it is used to supply the correct new name for the one used by the original code.
The first step in the preliminary analysis is the determination of referenced variables:
LAMBDA Refs: () VARS: (VAR-1) BODY:
Lnsets Refs: (vnu-1) rnvAns: (rnvnu-2) rnocrs:
LAMBDA airs; (ruvnn-2) vAns= (van-a van-4) aoov; IF news: (FNVAR-Z van-3 van-4) Paco: COMBINATION Refs: (VAR-3) Anas: vAnlAsL£ REPS: () VAR: I GLOBALP: T VARIABLE REPS: (VAR-3) VAR: VAR-3 GLOBALP: NIL CONSTANT REFS: ()
[Page 83]
BODY: COMBINATION REFS:
ARGS:
73 VALUE: 0 CON: VARIABLE Refs: (VAR-4) VAR: VAR-4 GLOBALP: NIL ALT: COMBINATION REFS: (FNVAR-Z VAR-3 VAR-4) ARGS: VARIABLE REFS: (FNVAR-2) VAR: FNVAR-2 GLOBALP: NIL COMBINATION REFS: (VAR-3) ARGS: VARIABLE REFS: () VAR: -GLOBALP: T VARIABLE REPS: (VAR-3) VAR: VAR-3 GLOBALP: NIL CONSTANT REFS: () VALUE: 1 COMBINATION REFS: (VAR-3 VAR-4) ARGS: VARIABLE REPS: () VAR: l GLOBALP: T VARIABLE REPS: (VAR-3) VAR: VAR-3 GLOBALP: NIL VARIABLE (FNVAR-2 VAR-1) VARIABLE REPS: (YNVAR-2) VAR: FNVAR-2 GLOBALP1 NIL VARIABLE REFS2 (VAR-1) VAR! VAR-1 GLOBALPZ NIL CONSTANT REFS: () VALUE: 1 REFS: (VAR-4) VAR: VAR-4 GLOBALP: NIL
[Page 84]
74 The REFS component is a list of all local variables referenced at or below the node. Notice that, in general, the REFS component of a node is the union (considering them as sets) of the REFS components of its subnodes. In this way the information sifts up from the VARIABLE nodes. At a LAMBDA, LABELS, or CATCH, the variables bound at that node are filtered out of the REFS sifting up. The REFS for the outer function must always be (), a useful error check. In this example, we see that VAR-l (N) is not referenced by the function FNVAR-2 (F).
This indicates that a closure for this function need not contain the value for VAR-1 in its environment. (we will not actually use the information for this purpose, since later analysis will determine that the function need not have a closure constructed for it.) Another component ASETVARS is computed for each node, which contains the set of variables appearing in an ASET' at or below the node. we have omitted this information from the diagram since the value is the empty set in all cases. Certain properties are placed on the property list of each variable as well, which are not shown here.
The next pass locates trivial subforms:
LAMBDA TR1vP= NIL VARS: (VAR-1) BODY:
LABELS TRIVP: NIL rNvAAs; (FNVAR-Z) rnnersz LAMBDA TRIVP: NIL VARS: (VAR-3 VAR-4) BODY: IF TRIVP: NIL PRED: COMBINATION TRIVP: T ARGS: VARIABLE TRIVP: T VAR: I GLOBALP: T VARIABLE
[Page 85]
75 CON: VARIABLE TRIVP:
VAR:
TRIVP:
VAR:
GLOBALP:
CONSTANT TRIVP:
VALUE:
T VAR-4 GLOBALP: NIL ALT: COMBINATION TRIVP:
ARGS:
BODY: COMBINATION TRIVP: NIL ARGS: VARIABLE TRIVP: T VAR: FNVAR-2 GLOBALP: NIL VARIABLE TRIVP: T VAR: VAR-1 GLOBALP: NIL NIL VARIABLE TRIVP:
VAR:
GLOBALP:
COMBINATION TRIVP:
ARGS:
COMBINATION TRIVP:
ARGS:
T VAR-3 NIL T
0 T
FNVAR-2 NIL T
VARIABLE TRIVP:
VAR:
GLOBALP VARIABLE TRIVP:
VAR:
GLOBALP CONSTANT TRIVP:
VALUE:
T VARIABLE TRIVP:
VAR:
GLOBAL?
VARIABLE TRIVP:
VAR:
GLOBALP:
VARIABLE TRIVP:
VAR:
GLOBALP:
T T
T VAR-3 NIL T
1 T
1 T
T VAR-3 NIL T
VAR-4 NIL
[Page 86]
76 CONSTANT TRIVP: T VALUE: 1 Constants and variables are always trivial, and trivial combinations (involving only MacLISP primitives) are located. As before, in this pass information sifts up from below. One possibility not yet explored in RABBIT is to isolate entire SCHEME functions (for example FNVAR-Z), determine that it is, as a whole, trivial, compile it as a simple MacLISP SUBR, and reference it as a primitive.
This would in turn render trivial the combination (F N 1) in the body of the LABELS, for example.
_ The analysis of side-effects merely determines that no side-effects are present, and is uninteresting for our example. The optimization pass finds no transformations worth making. we will skip over these steps to the conversion to continuation-passing style. As a simple S-expression, this may be rendered as:
(LAMBDA (CONT-5 VAR-1) (LABELS ((FNVAR-2 (LAMBDA (CONT-6 VAR-3 VAR-4) (IF (= VAR-3 0) (CONT-6 VAR-4) (FNVAR-Z CONT-6 (- VAR-3 1) (* VAR-3 VAR-4)))))) (FNVAR-2 CONT-5 VAR-1 l))) '
In rendering this as a tree of data structures, we use structures of type CLAMBDA instead of LAMBDA, etc., in order to prevent confusion. Trivial forms are represented by structures of type TRIVIAL with pointers to the data structures from before. we will not notate such data structures in the following diagrams, but will simply write an S-expression as a reminder of what the trivial form was.
The types RETURN and CONTINUATION are like CCOMBINATION and CLAMBDA, but are distinguished as discussed above for convenience and for purposes of consistency
[Page 87]
77 checking.
CLAMBDA VARS: (CONT-5 VAR-1) BODY: CLABELS FNVARS: (FNVAR-2) FNDEFS: CLAMBDA VARS: (CONT-6 VAR-3 VAR-4) BODY: CIF PRED: TRIVIAL (= VAR-3 0) CON: RETURN CONT: CVARIABLE VAR: CONT-6 VAL: TRIVIAL VAR-4 ALT: CCOHBINATION ARGS: TRIVIAL FNVAR-2 CVARIABLE VAR: CONT-6 TRIVIAL (- VAR-3 1) TRIVIAL (i VAR-3 VAR-4) BODY: CCOMBINATION ARGS: TRIVIAL FNVAR-2 CVARIABLE VAR: CONT-5 TRIVIAL VAR-1 TRIVIAL I
The first post-conversion analysis pass computes ENV and REFS components as before, this time including the variables introduced to represent continuations. The ENV in this case is not an a-list, but simply a list of variables, since no renaming is taking place. The ENV information sifts down from above during the tree walk, and on the way back the REFS information sifts up. For a TRIVIAL node, the REFS information is taken from the pre-conversion node referenced by the TRIVIAL node; this REFS information is shown here as a reminder. As before, the REFS information for a node is always a subset of the
[Page 88]
ENV information.
CLAMBDA ENV:
REFS VARS BODY; 78 1) (CONT-5 VAR-1) (CONT-5 VAR-1) () () (CONT-5 VAR-CLABELS ENV:
REFS:
FNVARSZ FNDEFS:
BODY:
(FNVAR-2) CLAMBDA ENV: (FNVAR-Z CONT-5 VAR-1) R£F$: (FNVAR-2) VARS: (CONT-6 VAR~3 VAR-4) BODY: CIF ENV: ii* REFS: (FNVAR-Z CONT-6 VAR-3 VAR-4) PRED: TRIVIAL REFS: (VAR-3) (= VAR-3 0) CON: RETURN ENV: fi* REPS (CONT-6 VAR~1) CONT: CVARIABLE ENV: *fi REFS: (CONT-6) VAR: CONT-6 VAL: TRIVIAL REFS: (VAR-4) VAR-4 ALT: CCOHBINATION ENV: *ff REFS: (FNVAR-2 CONT-6 VAR-3 VAR-4) ARGS: TRIVIAL REFS: (FNVAR-2) FNVAR-2 CVARlABL€ ENVI *** REFS: (CONT-6) VAR: CONT-6 TRIVIAL REFS: (VAR-3) (- VAR-3 1) TRIVIAL REFS: (VAR-3 VAR-4) (i VAR-3 VAR-4) CCOMBINATION ENV: (FNVAR-2 CONT-5 VAR-1) REPS: (FNVAR-2 CONT-5 VAR-1) ARGS: TRIVIAL REFS: (FNVAR-Z) FNVAR-2
[Page 89]
79 CVARIABLE ENV: (FNVAR-Z CONT-5 VAR-1) REPS! (CONT-5) VAR: CONT-5 TRIVIAL REFS: (VAR-1) VAR-1 TRIVIAL REPS: () 1
The reader is asked to imagine that where *if* occurs the expression (CONT-6 VAR-3 VAR-4 FNVAR-Z CONT-5 VAR-1) had been written instead. An additional operation performed on_this pass is to flag all variables referenced in other than function position. These include VAR-1, VAR-3, etc.; but FNVAR-Z is not among them. This will be of importance below.
The next pass determines all variables referenced by closures at or below each node, and also decides which functions will actually be closed. It is determined that FNVAR-Z need not be closed, because it is referred to only in function position (as determined by the previous pass), and is not referred to by any other closures. As a result, no closures are created at all in this function, and so all the computed sets of variables are empty. This pass also assigns the name F-7 to the outer function, for use later as a tag.
The third pass computes the "depth" of each function, which determines through what registers or other locations arguments will be passed for each function. In this case the outer CLAMBDA is assigned depth 0, and the one labelled FNVAR-Z is assigned depth 2, because it is not closed, and is contained in a depth 0 function of 2 arguments. In this way registers are allocated in a purely stack-like manner; all closed functions are of depth 0, and all unclosed ones are at a depth determined by that of the containing function and its number
[Page 90]
80 of arguments.
One way to think about this trick is as follows. A closure consists of a pointer to a piece of code and a set of values determined at the time of closure. when the closure is invoked, we execute the code, making available to it (a) the set of' values (its environment), and (b) some additional arguments. Slicing these components a different way, we may think of calling the bare code, supplying all the values as arguments; we pass the arguments in some registers, and the environment values in some other registers. Put yet another way, if we can determine that every caller of the closed function can reconstruct the necessary environment at the time of the call (because it will have available the necessary values anyway), then we can avoid constructing the closure at the point where the function should be closed, and instead arrange for each caller to pass the environment through specified registers. As mentioned earlier, the compiler has a completely free hand in determining the format of an environment!
As it happens, the function labelled FNVAR-Z does not reference CONT-5 or VAR-1, and so this argument is of no importance here. It is determined that the following register assignments will apply:_ CONT-5 **CONT** VAR-1 **ONE** FNVAR-2 (none) CONT-6 **TWO** VAR-3 **THREE** VAR-4 **FOUR** (Note Continuation Variable Hack) We will see below that some unnecessary shuffling of values results; a more complicated register assignment technique would be useful here. (One was outlined in [Declarative], but it has not been implemented. See also [Wulf] and [Johnsson].) The fourth post-conversion analysis pass determines the format of
[Page 91]
81 environments for closed functions. Since there are none in this example, this analysis is of little interest here.
Finally, we are ready to generate code. Consider the S-expression form:
(LAMBDA (CONT-5 VAR-1) (LABELS ((FNVAR-Z (LAMBDA (CONT-6 VAR-3 VAR-4) (IF (= VAR-3 0) (CONT-6 VAR-4) (FNVAR-2 CONT-6 (- VAR-3 1) (w VAR-3 VAR-4)))))) (FNVAR-2 CONT-5 VAR-1 l))) The first function encountered is the outer one (named F-7). In analyzing its body we note the LABELS, and place all the labelled functions (that is, FNVAR-2) on the queue of functions yet to be processed. We then analyze the body of the LABELS. This is a combination, and so we analyze each argument, producing code for each. Each argument must be TRIVIAL, a (C)VARIABLE, or a (C)LAMBDA-expression. (We shall refer to this set of possibilities as "meta-trivial", which means what "trivial" did in [Imperative].) The variable FNVAR-2 refers to a known function which is not closed, and so we need not set up **FUN**. The others may be referred to as **CONT**, **ONE**, and the constant 1, respectively.
These are to be passed to FNVAR-Z through the registers **TWO**, **THREE**, and **FOUR** (as determined by the register allocation pass). Thus the code for F-7 looks like this:
F-7 ((LAMBDA (Q-40 Q-41 Q-42) (SETQ **FOUR** Q-42) (SETQ **THREE** Q-41) (SETQ **TWO** Q~40)) **CONT** none" '1) (oo FNVAR-2) The first form sets up the arguments, using a standard "simultaneous assignment'
[Page 92]
82 construction. The second branches to the code for FNVAR-Z. Because a known function is being called, it is not necessary to set up **NARGS**. Because FNVAR-2 requires no closure, it is not necessary to set up **ENV**.
The next function on the queue to process is FNVAR-2. Its body is an IF (actually a CIF); this is compiled into a COND containing the code for the predicate, consequent, and alternative:
(COND (<predicate> <consequent>) (T <alternative>)) The predicate is guaranteed to be meta-trivial. It is, in this example, a trivial combination; this is compiled by changing all the variable references appropriately, producing (= **THREE** '0).
The consequent involves calling an unknown continuation which is in **Two**. The returned value is in **FOUR**. The code produced is:
(SETQ **FUN** **TWO**) (SETQ **ONE** **FOUR**) (RETURN NIL) The (RETURN NIL) exits the module, passing control to the dispatcher in the SCHEME interpreter, which will arrange to invoke the continuation.
The code for the alternative is similar to that for the body of F-7, because we are calling the known function FNVAR-Z. The generated code is:
((LANBDA (Q-43 Q-44) (SETQ **FOUR** Q-44) (SETQ **THREE** Q-43)) (- **THREE** '1) (* **THREE** **FOUR**)) (GO FNVAR-2) The argument setup ought to involve copying **TWO** into **TWO**, but a peephole optimization eliminates that SETQ.
[Page 93]
83 Putting all this together, the code for FNVAR-Z is:
FNVAR-2 (COND ((= **THREE** '0) (SETQ **FUN** **TWO**) (SETQ **ONE** **FOUR**) (RETURN NIL)) (T ((LAMBDA (Q-43 Q-44) (SETQ **FOUR** Q-44) (SETQ **THREE** Q-43)) (- **THREE** '1) (* **THREE** **FOUR*#)) (GO FNVAR-Z))) (We have glossed over the peephole optimizations which eliminate occurrences of PROGN in such places as COND clauses.) There are no more functions to be processed, and so we now create the final module. The final output, with comments inserted by RABBIT for debugging purposes, and declarations supplied by RABBIT for the benefit of the HacLISP compiler, looks like this:
(PROGN 'COMPILE (COMMENT MODULE FOR FUNCTION IFACT) (DEFUN 7-37 () (PROG () (DECLARE (SPECIAL 7-37)) (GO (PROG2 NIL (CAR i*ENV¢¢) (SETO *iENV** (CDR *¢ENVl*)))) F-7 (COMMENT (DEPTH = 0) (FNP I NIL) (VARS = (CONT-5 N))) ((LAMBDA (O-40 O-41 O-42) (SETO **FOUR** O-42) (SETO **THREE*¢ O-41) (ssro »~rwo~~ o-4o)) 1»CONTaa QQONEQQ '1) (connenr (DEPTH = 2) (FNP = NOCLOSE) (VARS = (CONT-6 N A))) (GO FNVAR-2) FNVAR-2 (COMMENT (DEPTH = 2) (FNP = NOCLOSE) (VARS I (CONT-6 H A))) (COND ((= **THREEi* '0) (SETQ ~~FUN~¢ ¢*Tw0¢¢) (SETO **ONE** **FOURl*) (RETURN NIL)) (T ((LAMBDA (O-43 O-44) (SETO **FOUR¢* O-44) (SETO ¢*THREE¢¢ O-43)) (- ¢*THREE** 'l) (w ¢f1HR£E»~ **FOUR*°))
[Page 94]
84 (comment (DEPTH = z) (ruv - NOCLOSE) (VARS = (CONT-6 n A))) (eo FNVAR-2))))) (scro 7-37 (GET 'r-37 'SUBR)) (SETO IrAcr (List 'ca£TA 2-37°F-7)) (o£FPRoP 2-37 IrAc1 USER-FUNCTION)) In the interpolated comments, FNP refers to whether the function being entered or being called is closed or not (the possibilities are NIL, NOCLOSE, and EZCLOSE).
The VARS are the passed variables, expressed as the names from the original source code, except for those introduced by the CPS conversion. The form (SETQ IFACT ...) constructs the closure for the globally defined function IFACT. The DEFPROP form provides debugging information.
The points of interest in this example are the isolation of trivial subforms, and the analysis of the function FNVAR-Z which allows it to be called with GO. Examination of the output code will show that FNVAR-Z is coded as an iterative loop. While the register allocation leaves something to be desired, the inner loop does surprisingly little shuffling. (This should be compared with the code suggested in [Declarative] for this function.) For those who prefer 'real' machine language, we give a plausible transcription of the MacLISP code into our hypothetical machine language:
IFACT: PUSH CONT ;CONT contains the return address PUSH ONE PUSH 1 POP FOUR _ POP THREE POP TWO GOTO FNVARZ .
[Page 95]
85 FNVAR2: JUMP-IF-ZERO THREE,FNVZA MOVE ONE,FOUR RETURN (TWO) ;return to address in TWO FNVZA: MOVE TEMP,THREE ;TEMP is used to evaluate ADD TEMP,1 ; trivial forms PUSH TEMP MOVE TEMP,THREE NUL TEMP,FOUR PUSH TEMP POP FOUR POP THREE GOTO FNVAR2 while this is not the world's most impressively tight code, it again shows the essential iterative structure of the inner loop. The primary problem is the absence of analysis of which registers are used when. Leaving aside the question of allocating registers, one could at least determine when assigning values to registers for argument setup can occur sequentially rather than simultaneously.
There are a few other obvious optimizations which have not been performed, for example the elimination of (GO FNVAR-Z) just before the tag FNVAR-Z. while this would not have been difficult, we knew that the MacLlSP compiler would take care of this for us; since it is not a very interesting issue, we let it slide.