TRANSLATION INTO TREES

Translation of abstract syntax expressions into intermediate trees is reasonably straightforward; but there are many cases to handle. We will cover the translation of various language constructs, including many from MiniJava.

KINDS OF EXPRESSIONS

The MiniJava grammar has clearly distinguished statements and expressions. However, in languages such as C, the distinction is blurred; for example, an assignment in C can be used as an expression. When translating such languages, we will have to ask the following question. What should the representation of an abstract-syntax expression be in the Tree language? At first it seems obvious that it should be Tree.Exp. However, this is true only for certain kinds of expressions, the ones that compute a value. Expressions that return no value are more naturally represented by Tree.Stm. And expressions with boolean values, such as a > b, might best be represented as a conditional jump - a combination of Tree.Stm and a pair of destinations represented by Temp.Labels. It is better instead to ask, "how might the expression be used?" Then we can make the right kind of methods for an object-oriented interface to expressions. Both for MiniJava and other languages, we end up with Translate.Exp, not the same class as Tree.Exp, having three methods: 

package Translate;
public abstract class Exp {
 abstract Tree.Exp unEx();
 abstract Tree.Stm unNx();
 abstract Tree.Stm unCx(Temp.Label t, Temp.Label f);
}

For example, the MiniJava statement 

if (a<b && c<d) {
 // true block
}
else {
 // false block
}

might translate to a Translate.Exp whose unCx method is roughly like 

Tree.Stm unCx(Label t, Label f) {
 Label z = new Label();
 return new SEQ(new CJUMP(CJUMP.LT,a,b,z,f),
 new SEQ(new LABEL(z),
 new CJUMP(CJUMP.LT,c,d,t,f)));
}

The abstract class Translate.Exp can be instantiated by several subclasses: Ex for an ordinary expression that yields a single value, Nx for an expression that yields no value, and Cx for a "conditional" expression that jumps to either t or f : 

class Ex extends Exp {
 Tree.Exp exp;
 Ex(Tree.Exp e) {exp=e;}
 Tree.Exp unEx() {return exp;}
 Tree.Stm unNx() { ... ?... }
 Tree.Stm unCx(Label t, Label f) { ... ?... }
}
class Nx extends Exp {
 Tree.Stm stm;
 Nx(Tree.Stm s) {stm=s;}
 Tree.Exp unEx() { ... ?... }
 Tree.Stm unNx() {return stm;}
 Tree.Stm unCx(Label t, Label f) { ... ?... }
}

But what does the unNx method of an Ex do? We have a simple Tree.Exp that yields a value, and we are asked to produce a Tree.Stm that produces no value. There is a conversion operator Tree.EXP, and unNx must apply it: 

class Ex extends Exp {
 Tree.Exp exp;
 ⋮
 Tree.Stm unNx() {return new Tree.EXP(exp); }
 ⋮
}

Each kind of Translate.Exp class must have similar conversion methods. For example, the MiniJava statement 

flag = (a<b && c<d);

requires the unEx method of a Cx object so that a 1 (for true) or 0 (for false) can be stored into flag. shows the class Cx. The unEx method is of particular interest. To convert a "conditional" into a "value expression", we invent a new temporary r and new labels t and f. Then we make a Tree.Stm that moves the value 1 into r, and a conditional jump unCx(t, f) that implements the conditional. If the condition is false, then 0 is moved into r; if it is true, then execution proceeds at t and the second move is skipped. The result of the whole thing is just the temporary r containing zero or one.The Cx class. 

abstract class Cx extends Exp {
 Tree.Exp unEx() {
 Temp r = new Temp();
 Label t = new Label();
 Label f = new Label();
 return new Tree.ESEQ(
 new Tree.SEQ(new Tree.MOVE(new Tree.TEMP(r),
 new Tree.CONST(1)),
 new Tree.SEQ(unCx(t,f),
 new Tree.SEQ(new Tree.LABEL(f),
 new Tree.SEQ(new Tree.MOVE(new Tree.TEMP(r),
 new Tree.CONST(0)),
 new Tree.LABEL(t))))),
 new Tree.TEMP(r));
}
abstract Tree.Stm unCx(Label t, Label f);
Tree.Stm unNx() { ... }
}

The unCx method is still abstract: We will discuss this later, with the translation of comparison operators. But the unEx and unNx methods can still be implemented in terms of the unCx method. We have shown unEx; we will leave unNx (which is simpler) as an exercise.

The unCx method of class Ex is left as an exercise. It's helpful to have unCx treat the cases of CONST 0and CONST 1 specially, since they have particularly simple and efficient translations. Class Nx's unEx and unCx methods need not be implemented, since these cases should never occur in compiling a well-typed MiniJava program.

SIMPLE VARIABLES

For a simple variable v declared in the current procedure's stack frame, we translate it asJava ScreenShot

where k is the offset of v within the frame and TEMP fp is the frame-pointer register. For the MiniJava compiler we make the simplifying assumption that all variables are the same size - the natural word size of the machine. The Frame class holds all machine-dependent definitions; here we add to it a frame-pointer register FP and a constant whose value is the machine's natural word size: 

package Frame;
public class Frame {
 ⋮
 abstract public Temp FP();
 abstract public int wordSize();
}
public abstract class Access {
 public abstract Tree.Exp exp(Tree.Exp framePtr);
}

In this and later chapters, we will abbreviate BINOP(PLUS, e1, e2) as + (e1, e2), so the tree above would be shown asJava ScreenShot

The exp method of Frame.Access is used by Translate to turn a Frame.Access into the Tree expression. The Tree.Exp argument is the address of the stack frame that the Access lives in. Thus, for an access a such as InFrame(k), we have 

a.exp(new TEMP(frame.FP())) =
 MEM(BINOP(PLUS,TEMP(frame.FP()),CONST(k)))

If a is a register access such as InReg(t832), then the frame-address argument to a.exp() will be discarded, and the result will be simply TEMP t832.

An l-value such as v or a[i] or p:next can appear either on the left side or the right side of an assignment statement - l stands for left, to distinguish from r-values, which can appear only on the right side of an assignment. Fortunately, both MEM and TEMP nodes can appear on the left of a MOVE node.

ARRAY VARIABLES

For the rest of this chapter we will not specify all the interface functions of Translate, as we have done for simpleVar. But the rule of thumb just given applies to all of them: There should be a Translate function to handle array subscripts, one for record fields, one for each kind of expression, and so on. Different coding languages treat array-valued variables differently. In Pascal, an array variable stands for the contents of the array - in this case all 12 integers. The Pascal program 

var a,b : array[1..12] of integer begin
 a:=b end;

copies the contents of array a into array b. In C, there is no such thing as an array variable. There are pointer variables; arrays are like "pointer constants." Thus, this is illegal: 

{int a[12], b[12];
 a=b;
}

but this is quite legal: 

{int a[12], *b;
 b=a;
}

The statement b=a does not copy the elements of a; instead, it means that b now points to the beginning of the array a. In MiniJava (as in Java and ML), array variables behave like pointers. MiniJava has no named array constants as in C, however. Instead, new array values are created (and initialized) by the construct new int[n]; where n is the number of elements, and 0 is the initial value of each element. In the program 

int [] a;
a = new int[12];
b = new int[12];
a = b;

the array variable a ends up pointing to the same 12 zeros as the variable b; the original 12 zeros allocated for a are discarded.

MiniJava objects are also pointers. Object assignment, like array assignment, is pointer assignment and does not copy all the fields (see below). This is also true of other object-oriented and functional coding languages, which try to blur the syntactic distinction between pointers and objects. In C or Pascal, however, a record value is "big" and record assignment means copying all the fields.

STRUCTURED L-VALUES

An l-value is the result of an expression that can occur on the left of an assignment statement, such as x or p.y or a[i+2]. An r-value is one that can only appear on the right of an assignment, such as a+3 or f(x). That is, an l-value denotes a location that can be assigned to, and an r-value does not. Of course, an l-value can occur on the right of an assignment statement; in this case the contents of the location are implicitly taken. We say that an integer or pointer value is a "scalar", since it has only one component. Such a value occupies just one word of memory and can fit in a register. All the variables and l-values in MiniJava are scalar. Even a MiniJava array or object variable is really a pointer (a kind of scalar); the Java Language Reference Manual may not say so explicitly, because it is talking about Java semantics instead of Java implementation. In C or Pascal there are structured l-values - structs in C, arrays and records in Pascal - that are not scalar. To implement a language with "large" variables such as the arrays and records in C or Pascal requires a bit of extra work. In a C compiler, the access type would require information about the size of the variable. Then, the MEM operator of the TREE intermediate language would need to be extended with a notion of size: 

package Tree;
abstract class Exp
MEM(Exp exp, int size)

The translation of a local variable into an IR tree would look like

MEM(+(TEMP fp, CONST kn), S)

where the S indicates the size of the object to be fetched or stored (depending on whether this tree appears on the left or right of a MOVE).

Leaving out the size on MEM nodes makes the MiniJava compiler easier to implement, but limits the generality of its intermediate representation.

SUBSCRIPTING AND FIELD SELECTION

To subscript an array in Pascal or C (to compute a[i]), just calculate the address of the ith element of a: (i −l) × s + a, where l is the lower bound of the index range, s is the size (in bytes) of each array element, and a is the base address of the array elements. If a is global, with a compile-time constant address, then the subtraction a − s × l can be done at compile time. Similarly, to select field f of a record l-value a (to calculate a. f), simply add the constant field offset of f to the address a. An array variable a is an l-value; so is an array subscript expression a[i], even if i is not an l-value. To calculate the l-value a[i] from a, we do arithmetic on the address of a. Thus, in a Pascal compiler, the translation of an l-value (particularly a structured l-value) should not be something likeJava ScreenShot

but should instead be the Tree expression representing the base address of the array:Java ScreenShot

What could happen to this l-value?

In the MiniJava language, there are no structured, or "large", l-values. This is because all object and array values are really pointers to object and array structures. The "base address" of the array is really the contents of a pointer variable, so MEM is required to fetch this base address. Thus, if a is a memory-resident array variable represented as MEM(e), then the contents of address e will be a one-word pointer value p. The contents of addresses p, p + W, p + 2W, … (where W is the word size) will be the elements of the array (all elements are one word long). Thus, a[i] is justJava ScreenShot

l-values and MEM nodes. Technically, an l-value (or assignable variable) should be represented as an address (without the top MEM node in the diagram above). Converting an l-value to an r-value (when it is used in an expression) means fetching from that address; assigning to an l-value means storing to that address. We are attaching the MEM node to the l-value before knowing whether it is to be fetched or stored; this works only because in the Tree intermediate representation, MEM means both store (when used as the left child of a MOVE)and fetch (when used elsewhere).

A SERMON ON SAFETY

Life is too short to spend time chasing down irreproducible bugs, and money is too valuable to waste on the purchase of flaky software. When a program has a bug, it should detect that fact as soon as possible and announce that fact (or take corrective action) before the bug causes any harm. Some bugs are very subtle. But it should not take a genius to detect an outof-bounds array subscript: If the array bounds are L ..H, and the subscript is i, then i < L or i > H is an array bounds error. Furthermore, computers are well-equipped with hardware able to compute the condition i > H. For several decades now, we have known that compilers can automatically emit the code to test this condition. There is no excuse for a compiler that is unable to emit code for checking array bounds. Optimizing compilers can often safely remove the checks by compile-time analysis; see . One might say, by way of excuse, "but the language in which I program has the kind of address arithmetic that makes it impossible to know the bounds of an array." Yes, and the man who shot his mother and father threw himself upon the mercy of the court because he was an orphan. In some rare circumstances, a portion of a program demands blinding speed, and the timing budget does not allow for bounds checking. In such a case, it would be best if the optimizing compiler could analyze the subscript expressions and prove that the index will always be within bounds, so that an explicit bounds check is not necessary. If that is not possible, perhaps it is reasonable in these rare cases to allow the programmer to explicitly specify an unchecked subscript operation. But this does not excuse the compiler from checking all the other subscript expressions in the program.

Needless to say, the compiler should check pointers for nil before dereferencing them, too.[]

ARITHMETIC

Integer arithmetic is easy to translate: Each arithmetic operator corresponds to a Tree operator. The Tree language has no unary arithmetic operators. Unary negation of integers can be implemented as subtraction from zero; unary complement can be implemented as XOR with all ones. Unary floating-point negation cannot be implemented as subtraction from zero, because many floating-point representations allow a negative zero. The negation of negative zero is positive zero, and vice versa. Thus, the Tree language does not support unary negation very well.

Fortunately, the MiniJava language doesn't support floating-point numbers; but in a real compiler, a new operator would have to be added for floating negation.

CONDITIONALS

The result of a comparison operator will be a Cx expression: a statement s that will jump to any true-destination and false-destination you specify. Making "simple" Cx expressions from comparison operators is easy with the CJUMP operator. However, the whole point of the Cx representation is that conditional expressions can be combined easily with the MiniJava operator &&. Therefore, an expression such as x<5 will be translated as Cx(s1), whereJava ScreenShot

for any labels t and f. To do this, we extend the Cx class to make a subclass RelCx that has private fields to hold the left and right expressions (in this case x and 5) and the comparison operator (in this case Tree.CJUMP.LT). Then we override the unCx method to generate the CJUMP from these data. It is not necessary to make unEx and unNx methods, since these will be inherited from the parent Cx class. The most straightforward thing to do with an if-expression

if e1 then e2 else e3

is to treat e1 as a Cx expression, and e2 and e3 as Ex expressions. That is, use the unCx method of e1 and the unEx of e2 and e3. Make two labels t and f to which the conditional will branch. Allocate a temporary r, and after label t, move e2 to r; after label f, move e3 to r. Both branches should finish by jumping to a newly created "join" label. This will produce perfectly correct results. However, the translated code may not be very efficient at all. If e2 and e3 are both "statements" (expressions that return no value), then their representation is likely to be Nx, not Ex. Applying unEx to them will work - a coercion will automatically be applied - but it might be better to recognize this case specially. Even worse, if e2 or e3 is a Cx expression, then applying the unEx coercion to it will yield a horrible tangle of jumps and labels. It is much better to recognize this case specially. For example, consider

if x < 5 then a > b else 0

As shown above, x < 5 translates into Cx(s1); similarly, a > b will be translated as Cx(s2) for some s2. The whole if-statement should come out approximately asJava ScreenShot

for some new label z. Therefore, the translation of an if requires a new subclass of Exp: 

class IfThenElseExp extends Exp {
 Exp cond, a, b;
 Label t = new Label();
 Label f = new Label();
 Label join = new Label();
 IfThenElseExp(Exp cc, Exp aa, Exp bb) {
 cond=cc; a=aa; b=bb;
 }
 Tree.Stm unCx(Label tt, Label ff) { ... }
 Tree.Exp unEx() { ... }
 Tree.Stm unNx() { ... }
}

The labels t and f indicate the beginning of the then-clause and elseclause, respectively. The labels tt and ff are quite different: These are the places to which conditions inside the then-clause (or else-clause) must jump, depending on the truth of those subexpressions.

STRINGS

A string literal is typically implemented as the constant address of a segment of memory initialized to the proper characters. In assembly language, a label is used to refer to this address from the middle of some sequence of instructions. At some other place in the assembly-language program, the definition of that label appears, followed by the assembly-language pseudo-instruction to reserve and initialize a block of memory to the appropriate characters. For each string literal lit, a translator must make a new label lab, and return the tree Tree.NAME(lab). It should also put the assembly-language fragment frame.string(lab,lit) onto a global list of such fragments to be handed to the code emitter. "Fragments" are discussed further on page 157. All string operations are performed in functions provided by the runtime system; these functions heap-allocate space for their results, and return pointers. Thus, the compiler (almost) doesn't need to know what the representation is, as long as it knows that each string pointer is exactly one word long. We say "almost" because string literals must be represented.

In Pascal, strings are fixed-length arrays of characters; literals are padded with blanks to make them fit. This is not very useful. In C, strings are pointers to variable-length, zero-terminated sequences. This is much more useful, though a string containing a zero byte cannot be represented.

RECORD AND ARRAY CREATION

Imagine a language construct {e1, e2, …, en} which creates an n-element record initialized to the values of expressions ei. This is like an object constructor that initializes all the instance variables of the object. Such a record may outlive the procedure activation that creates it, so it cannot be allocated on the stack. Instead, it must be allocated on the heap. If there is no provision for freeing records (or strings), industrial-strength systems should have a garbage collector to reclaim unreachable records (see ). The simplest way to create a record is to call an external memory-allocation function that returns a pointer to an n-word area into a new temporary r. Then a series of MOVE trees can initialize offsets 0, 1W; 2W, …, (n − 1)W from r with the translations of expressions ei. Finally, the result of the whole expression is TEMP(r), as shown in .
Image 7.4: Object initialization.

In an industrial compiler, calling malloc (or its equivalent) on every record creation might be too slow; see . Array creation is very much like record creation, except that all the fields are initialized to the same value. The external initArray function can take the array length and the initializing value as arguments, see later. In MiniJava we can create an array of integers by the construct 

new int [exp]

where exp is an expression that evaluates to an integer. This will create an integer array of a length determined by the value of exp and with each value initialized to zero. To translate array creation, the compiler needs to perform the following steps:

  1. Determine how much space is needed for the array. This can be calculated by:Java ScreenShot

    The reason we add one to the length of the array is that we want to store the length of the array along with the array. This is needed for bounds checking and to determine the length at run time.

  2. Call an external function to get space on the heap. The call will return a pointer to the beginning of the array.
  3. Generate code for saving the length of the array at offset 0.
  4. Generate code for initializing each of the values in the array to zero starting at offset 4.

Calling runtime-system functions. To call an external function named init-Array with arguments a, b, simply generate a CALL such as 

static Label initArray = new Label("initArray");
new CALL(new NAME(initArray),
 new Tree.ExpList(a, new Tree.ExpList(b, null)));

This refers to an external function initArray which is written in a language such as C or assembly language - it cannot be written in MiniJava because MiniJava has no mechanism for manipulating raw memory. But on some operating systems, the C compiler puts an underscore at the beginning of each label; and the calling conventions for C functions may differ from those of MiniJava functions; and C functions don't expect to receive a static link, and so on. All these target-machine-specific details should be encapsulated into a function provided by the Frame structure: 

public abstract class Frame {
 ⋮
 abstract public Tree.Exp externalCall(String func,
 Tree.ExpList args);
}

where externalCall takes the name of the external procedure and the arguments to be passed. The implementation of externalCall depends on the relationship between MiniJava's procedure-call convention and that of the external function. The simplest possible implementation looks like 

Tree.Exp externalCall(String s, Tree.ExpList args) {
 return new Tree.CALL(new Tree.NAME(new Temp.Label(s)),
 args);
}

but may have to be adjusted for static links, or underscores in labels, and so on. Also, calling new Label(s) repeatedly with the same s makes several label objects that all mean the same thing; this may confuse other parts of the compiler, so it might be useful to maintain a string-to-label table to avoid duplication.

WHILE LOOPS

The general layout of a while loop is 

test:
 if not(condition) goto done body
 goto test
done:

If a break statement occurs within the body (and not nested within any interior while statements), the translation is simply a JUMP to done.

Translation of break statements needs to have a new formal parameter break that is the done label of the nearest enclosing loop. In translating a while loop, the translator will be called recursively upon body with the done label passed as the break parameter. When the translator is recursively calling itself in nonloop contexts, it can simply pass down the same break parameter that was passed to it.

FOR LOOPS

A for statement can be expressed using other kinds of statements:Java ScreenShot

A straightforward approach to the translation of for statements is to rewrite the abstract syntax into the abstract syntax of the while statement shown, and then translate the result.

This is almost right, but consider the case where limit=maxint. Then i + 1 will overflow; either a hardware exception will be raised, or i ≤ limit will always be true! The solution is to put the test at the bottom of the loop, where i < limit can be tested before the increment. Then an extra test will be needed before entering the loop to check lo ≤ hi.

FUNCTION CALL

Translating a function call f(a1, …an) is simple:Java ScreenShot

where lf is the label for f. In an object-oriented language, the implicit variable this must be made an explicit argument of the call. That is, p.m(a1, …an) is translated asJava ScreenShot

where p belongs to class c, and c$m is the m method of class c. For a static method, the computation of address lc$m can be done at compile time - it's a simple label, as it is in MiniJava. For dynamic methods, the computation is more complicated, as explained in .

STATIC LINKS

Some coding languages (such as Pascal, Scheme, and ML) support nesting of functions so that the inner functions can refer to variables declared in the outer functions. When building a compiler for such a language, frame representations and variable access are a bit more complicated. When a variable x is declared at an outer level of static scope, static links must be used. The general form isJava ScreenShot

where the k1, …, kn−1 are the various static-link offsets in nested functions, and kn is the offset of x in its own frame. In creating TEMP variables, those temporaries that escape (i.e., are called from within an inner function) must be allocated in the stack frame, not in a register. When accessing such a temporary from either the same function or an inner function, we must pass the appropriate static link. The exp method of Frame.Access would need to calculate the appropriate chain of dereferences. Translating a function call f(a1, …an) using static links requires that the static link must be added as an implicit extra argument:Java ScreenShot

Here lf is the label for f, and sl is the static link, computed as described in . To do this computation, both the level of f and the level of the function calling f are required. A chain of (zero or more) offsets found in successive level descriptors is fetched, starting with the frame pointer TEMP(FP) defined by the Frame module. []A different way of checking for nil is to unmap page 0 in the virtual-memory page tables, so that attempting to fetch/store fields of a nil record results in a page fault.