A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition), страница 27

Thecommon case of jumping to a known label l is written as JUMP(NAME l, newLabelList(l, null)), but the JUMP class has an extra constructor so that this can beabbreviated as JUMP(l).CJUMP(o, e1, e2, t, f) Evaluate e1, e2 in that order, yielding values a, b. Then comparea, b using the relational operator o. If the result is true, jump to t; otherwise jump to f. The relational operators are EQ and NE for integer equality and nonequality (signedor unsigned); signed integer inequalities LT, GT, LE, GE; and unsigned integerinequalities ULT, ULE, UGT, UGE.SEQ(s1, s2) The statement s1 followed by s2.LABEL(n) Define the constant value of name n to be the current machine codeaddress.

This is like a label definition in assembly language. The value NAME(n) maybe the target of jumps, calls, etc.It is almost possible to give a formal semantics to the Tree language. However, there is noprovision in this language for procedure and function definitions - we can specify only the123body of each function. The procedure entry and exit sequences will be added later as special"glue" that is different for each target machine.7.2 TRANSLATION INTO TREESTranslation of abstract syntax expressions into intermediate trees is reasonablystraightforward; but there are many cases to handle. We will cover the translation of variouslanguage constructs, including many from MiniJava.KINDS OF EXPRESSIONSThe MiniJava grammar has clearly distinguished statements and expressions.

However, inlanguages such as C, the distinction is blurred; for example, an assignment in C can be used asan 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? Atfirst it seems obvious that it should be Tree.Exp. However, this is true only for certain kindsof expressions, the ones that compute a value.

Expressions that return no value are morenaturally 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 ofdestinations represented by Temp.Labels.It is better instead to ask, "how might the expression be used?" Then we can make the rightkind of methods for an object-oriented interface to expressions. Both for MiniJava and otherlanguages, we end up with Translate.Exp, not the same class as Tree.Exp, having threemethods:package Translate;public abstract class Exp {abstract Tree.Exp unEx();abstract Tree.Stm unNx();abstract Tree.Stm unCx(Temp.Label t, Temp.Label f);}•••Ex stands for an "expression", represented as a Tree.Exp.Nx stands for "no result", represented as a Tree statement.Cx stands for "conditional", represented as a function from label-pair to statement. Ifyou pass it a true destination and a false destination, it will make a statement thatevaluates some conditionals and then jumps to one of the destinations (the statementwill never "fall through").For example, the MiniJava statementif (a<b && c<d) {// true block}else {// false block}might translate to a Translate.Exp whose unCx method is roughly likeTree.Stm unCx(Label t, Label f) {Label z = new Label();return new SEQ(new CJUMP(CJUMP.LT,a,b,z,f),124new 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 anordinary expression that yields a single value, Nx for an expression that yields no value, andCx 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 conversionoperator 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, theMiniJava statementflag = (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 intoflag.Program 7.3 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 isjust the temporary r containing zero or one.PROGRAM 7.3: The Cx class.abstract class Cx extends Exp {Tree.Exp unEx() {Temp r = new Temp();Label t = new Label();Label f = new Label();125return 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 ofcomparison operators.

But the unEx and unNx methods can still be implemented in terms ofthe 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 ofCONST 0and CONST 1 specially, since they have particularly simple and efficienttranslations. Class Nx's unEx and unCx methods need not be implemented, since these casesshould never occur in compiling a well-typed MiniJava program.SIMPLE VARIABLESFor a simple variable v declared in the current procedure's stack frame, we translate it aswhere k is the offset of v within the frame and TEMP fp is the frame-pointer register.

For theMiniJava 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-pointerregister 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 treeabove would be shown as126The exp method of Frame.Access is used by Translate to turn a Frame.Access into theTree expression. The Tree.Exp argument is the address of the stack frame that the Accesslives in. Thus, for an access a such as InFrame(k), we havea.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() willbe 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 anassignment statement - l stands for left, to distinguish from r-values, which can appear only onthe right side of an assignment.

Fortunately, both MEM and TEMP nodes can appear on theleft of a MOVE node.ARRAY VARIABLESFor the rest of this chapter we will not specify all the interface functions of Translate, as wehave done for simpleVar. But the rule of thumb just given applies to all of them: Thereshould be a Translate function to handle array subscripts, one for record fields, one for eachkind of expression, and so on.Different programming 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 programvar a,b : array[1..12] of integerbegina:=bend;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;}127The statement b=a does not copy the elements of a; instead, it means that b now points to thebeginning of the array a.In MiniJava (as in Java and ML), array variables behave like pointers. MiniJava has no namedarray constants as in C, however. Instead, new array values are created (and initialized) by theconstruct new int[n]; where n is the number of elements, and 0 is the initial value of eachelement.

In the programinta =b =a =[] a;new int[12];new int[12];b;the array variable a ends up pointing to the same 12 zeros as the variable b; the original 12zeros allocated for a are discarded.MiniJava objects are also pointers. Object assignment, like array assignment, is pointerassignment and does not copy all the fields (see below). This is also true of other objectoriented and functional programming languages, which try to blur the syntactic distinctionbetween pointers and objects.

In C or Pascal, however, a record value is "big" and recordassignment means copying all the fields.STRUCTURED L-VALUESAn 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 anassignment, 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 thecontents of the location are implicitly taken.We say that an integer or pointer value is a "scalar", since it has only one component. Such avalue occupies just one word of memory and can fit in a register.