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

Imagine a compiler that passes parameters in registers, wastes no spaceproviding "backup storage" for parameters passed in registers, does not usestatic links, and in general makes stack frames as small as possible. How bigshould each stack frame for f be, in words?b. What is the maximum memory use of this program, with such a compiler?c. Using your favorite C compiler, compile this program to assembly languageand report the size of f 's stack frame.d. Calculate the total memory use of this program with the real C compiler.e. Quantitatively and comprehensively explain the discrepancy between (a) and(c).f.

Comment on the likelihood that the designers of this C compiler considereddeeply recursive functions important in real programs.*6.5 Instead of (or in addition to) using static links, there are other ways of gettingaccess to nonlocal variables. One way is just to leave the variable in a register!function f() : int =let var a := 5function g() : int =(a+1)in g()+g()endIf a is left in register r7 (for example) while g is called, then g can just access it fromthere.What properties must a local variable, the function in which it is defined, and thefunctions in which it is used, have for this trick to work?•*6.6 A display is a data structure that may be used as an alternative to static links formaintaining access to nonlocal variables. It is an array of frame pointers, indexed bystatic nesting depth.

Element Di of the display always points to the most recentlycalled function whose static nesting depth is i.The bookkeeping performed by a function f, whose static nesting depth is i, looks like:Copy Di to save locationin stack frameCopy frame pointer to Di... body of f ...Copy save locationback to DiIn Program 6.3, function prettyprint is at depth 1, write and show are at depth 2,and so on.a.

Show the sequence of machine instructions required to fetch the variableoutput into a register at line 14 of Program 6.3, using static links.b. Show the machine instructions required if a display were used instead.119c. When variable x is declared at depth d1 and accessed at depth d2, how manyinstructions does the static-link method require to fetch x?d. How many does the display method require?e.

How many instructions does static-link maintenance require for a procedureentry and exit (combined)?f. How many instructions does display maintenance require for procedure entryand exit?Should we use displays instead of static links? Perhaps; but the issue is morecomplicated. For languages such as Pascal with block structure but no functionvariables, displays work well.But the full expressive power of block structure is obtained when functions can bereturned as results of other functions, as in Scheme and ML.

For such languages, thereare more issues to consider than just variable-access time and procedure entry-exitcost: there is closure-building cost, and the problem of avoiding useless data kept livein closures. Chapter 15 explains some of the issues.120Chapter 7: Translation to IntermediateCodetrans-late: to turn into one's own or another languageWebster's DictionaryOVERVIEWThe semantic analysis phase of a compiler must translate abstract syntax into abstract machinecode. It can do this after type-checking, or at the same time.Though it is possible to translate directly to real machine code, this hinders portability andmodularity. Suppose we want compilers for N different source languages, targeted to Mdifferent machines. In principle this is N · M compilers (Figure 7.1a), a large implementationtask.Figure 7.1: Compilers for five languages and four target machines: (a) without an IR, (b) withan IR.An intermediate representation (IR) is a kind of abstract machine language that can expressthe target-machine operations without committing to too much machine-specific detail.

But itis also independent of the details of the source language. The front end of the compiler doeslexical analysis, parsing, semantic analysis, and translation to intermediate representation. Theback end does optimization of the intermediate representation and translation to machinelanguage.A portable compiler translates the source language into IR and then translates the IR intomachine language, as illustrated in Figure 7.1b. Now only N front ends and M back ends arerequired.

Such an implementation task is more reasonable.Even when only one front end and one back end are being built, a good IR can modularize thetask, so that the front end is not complicated with machine-specific details, and the back endis not bothered with information specific to one source language. Many different kinds of IRare used in compilers; for this compiler we have chosen simple expression trees.1217.1 INTERMEDIATE REPRESENTATION TREESThe intermediate representation tree language is defined by the package Tree, containingabstract classes Stm and Exp and their subclasses, as shown in Figure 7.2.package Tree;abstract class ExpCONST(int value)NAME(Label label)TEMP(Temp.Temp temp)BINOP(int binop, Exp left, Exp right)MEM(Exp exp)CALL(Exp func, ExpList args)ESEQ(Stm stm, Exp exp)abstract class StmMOVE(Exp dst, Exp src)EXP(Exp exp)JUMP(Exp exp, Temp.LabelList targets)CJUMP(int relop, Exp left, Exp right, Label iftrue, Label iffalse)SEQ(Stm left, Stm right)LABEL(Label label)other classes:ExpList(Exp head, ExpList tail)StmList(Stm head, StmList tail)other constants:final static int BINOP.PLUS, BINOP.MINUS, BINOP.MUL, BINOP.DIV, BINOP.AND,BINOP.OR, BINOP.LSHIFT, BINOP.RSHIFT, BINOP.ARSHIFT, BINOP.XOR;final static int CJUMP.EQ, CJUMP.NE, CJUMP.LT, CJUMP.GT, CJUMP.LE,CJUMP.GE, CJUMP.ULT, CJUMP.ULE, CJUMP.UGT, CJUMP.UGE;Figure 7.2: Intermediate representation trees.A good intermediate representation has several qualities:••It must be convenient for the semantic analysis phase to produce.

∊ It must beconvenient to translate into real machine language, for all the desired target machines.Each construct must have a clear and simple meaning, so that optimizingtransformations that rewrite the intermediate representation can easily be specified andimplemented.Individual pieces of abstract syntax can be complicated things, such as array subscripts,procedure calls, and so on. And individual "real machine" instructions can also have acomplicated effect (though this is less true of modern RISC machines than of earlierarchitectures).

Unfortunately, it is not always the case that complex pieces of the abstractsyntax correspond exactly to the complex instructions that a machine can execute.Therefore, the intermediate representation should have individual components that describeonly extremely simple things: a single fetch, store, add, move, or jump. Then any "chunky"piece of abstract syntax can be translated into just the right set of abstract machine122instructions; and groups of abstract machine instructions can be clumped together (perhaps inquite different clumps) to form "real" machine instructions.Here is a description of the meaning of each tree operator. First, the expressions (Exp), whichstand for the computation of some value (possibly with side effects):•••••••CONST(i) The integer constant i.NAME(n) The symbolic constant n (corresponding to an assembly language label).TEMP(t) Temporary t.

A temporary in the abstract machine is similar to a register in areal machine. However, the abstract machine has an infinite number of temporaries.BINOP(o, e1, e2) The application of binary operator o to operands e1, e2.Subexpression e1 is evaluated before e2. The integer arithmetic operators are PLUS,MINUS, MUL, DIV; the integer bitwise logical operators are AND, OR, XOR; theinteger logical shift operators are LSHIFT, RSHIFT; the integer arithmetic right-shiftis ARSHIFT. The MiniJava language has only one logical operator, but theintermediate language is meant to be independent of any source language; also, thelogical operators might be used in implementing other features of MiniJava.MEM(e) The contents of wordSize bytes of memory starting at address e (wherewordSize is defined in the Frame module).

Note that when MEM is used as the leftchild of a MOVE, it means "store", but anywhere else it means "fetch."CALL(f, l) A procedure call: the application of function f to argument list l. Thesubexpression f is evaluated before the arguments which are evaluated left to right.ESEQ(s, e) The statement s is evaluated for side effects, then e is evaluated for aresult.The statements (stm) of the tree language perform side effects and control flow:•••••••MOVE(TEMP t, e) Evaluate e and move it into temporary t.MOVE(MEM(e1) e2) Evaluate e1, yielding address a.

The nevaluate e2, and store theresult into wordSize bytes of memory starting at a.EXP(e) Evaluate e and discard the result.JUMP(e, labs) Transfer control (jump) to address e. The destination e may be a literallabel, as in NAME(lab), or it may be an address calculated by any other kind ofexpression. For example, a C-language switch(i) statement may be implemented bydoing arithmetic on i. The list of labels labs specifies all the possible locations thatthe expression e can evaluate to; this is necessary for dataflow analysis later.