Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition)

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

PDF-файл A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition), страница 30, который располагается в категории "книги и методические указания" в предмете "конструирование компиляторов" изседьмого семестра. A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition), страница 30 - СтудИзба 2019-09-18 СтудИзба

Описание файла

PDF-файл из архива "A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition)", который расположен в категории "книги и методические указания". Всё это находится в предмете "конструирование компиляторов" из седьмого семестра, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 30 страницы из PDF

They should be done by afunction in the Frame module:137package Frame;public abstract class Frame {⋮abstract public Tree.Stm procEntryExit1(Tree.Stm body);}The implementation of this function will be discussed on page 251. Translate should applyit to each procedure body (items 5-7) as it is translated.FRAGMENTSGiven a function definition comprising an already-translated body expression, the Translatephase should produce a descriptor for the function containing this necessary information:••frame: The frame descriptor containing machine-specific information about localvariables and parameters;body: The result returned from procEntryExit1.Call this pair a fragment to be translated to assembly language.

It is the second kind offragment we have seen; the other was the assembly-language pseudo-instruction sequence fora string literal. Thus, it is useful to define (in the Translate interface) a frag datatype:package Translate;public abstract class Frag { public Frag next; }public ProcFrag(Tree.Stm body, Frame.Frame frame);public DataFrag(String data);PROGRAM 7.5: A MiniJava program.class Vehicle {int position;int gas;int move (int x) {position = position + x;return position;}int fill (int y) {gas = gas + y;return gas;}}public class Translate {⋮private Frag frags; // linked list of accumulated fragmentspublic void procEntryExit(Exp body);public Frag getResult();}The semantic analysis phase calls upon new Translate.Level(…) in processing a functionheader. Later it calls other methods of Translate to translate the body of the function. Finallythe semantic analyzer calls procEntryExit, which has the side effect of remembering aProcFrag.138All the remembered fragments go into a private fragment list within Translate;thengetResult can be used to extract the fragment list.CLASSES AND OBJECTSFigure 7.5 shows a MiniJava class Vehicle with two instance variables position and gas,and two methods move and fill.

We can create multiple Vehicle objects. Each Vehicleobject will have its own position and gas variables. Two Vehicle objects can have differentvalues in their variables, and in MiniJava, only the methods of an object can access thevariables of that object. The translation of new Vehicle() is much like the translation ofrecord creation and can be done in two steps:1. Generate code for allocating heap space for all the instance variables; in this case weneed to allocate 8 bytes (2 integers, each of size, say, 4).2.

Iterate through the memory locations for those variables and initialize them- in thiscase, they should both be initialized to 0.Methods and the this pointer. Method calls in MiniJava are similar to function calls; butfirst, we must determine the class in which the method is declared and look up the method inthat class. Second, we need to address the following question. Suppose we have multipleVehicle objects and we want to call a method on one of them; how do we ensure that theimplementation knows for which object we are calling the method? The solution is to passthat object as an extra argument to the method; that argument is the this pointer.

For a methodcallVehicle v;...v.move();the Vehicle object in variable v will be the this pointer when calling the move method.The translation of method declarations is much like the translation of functions, but we needto avoid name clashes among methods with the same name that are declared in differentclasses. We can do that by choosing a naming scheme such that the name of the translatedmethod is the concatenation of the class name and the method name. For example, thetranslation of move can be given the name Vehicle move.Accessing variables In MiniJava, variables can be accessed from methods in the same class.Variables are accessed via the this pointer; thus, the translation of a variable reference is likefield selection for records.

The position of the variable in the object can be looked up in thesymbol table for the class.PROGRAM TRANSLATION TO TREESDesign a set of visitors which translate a MiniJava program into intermediate representationtrees.Supporting files in $MINIJAVA/chap7 include:Tree/* Data types for the Tree language.Tree/Print.java Functions to display trees for debugging.139A simpler translator To simplify the implementation of the translator, you may do withoutthe Ex, Nx, Cx constructors.

The entire translation can be done with ordinary valueexpressions. This means that there is only one Exp class (without subclasses); this classcontains one field of type Tree.Exp and only an unEx() method. Instead of Nx(s), useEx(ESEQ(s, CONST 0)). For conditionals, instead of a Cx, use an expression that justevaluates to 1 or 0.The intermediate representation trees produced from this kind of naive translation will bebulkier and slower than a "fancy" translation.

But they will work correctly, and in principle afancy back-end optimizer might be able to clean up the clumsiness. In any case, a clumsy butcorrect translator is better than a fancy one that doesn't work.EXERCISES•••7.1 Suppose a certain compiler translates all statements and expressions into Tree.Exptrees, and does not use the Nx and Cx constructors to represent expressions in differentways. Draw a picture of the IR tree that results from each of the following MiniJavastatements and expressions.a.

a+5b. b[i+1]c. a<b, which should be implemented by making an ESEQ whose left-hand sidemoves a 1 or 0 into some newly defined temporary, and whose right-hand sideis the temporary.d. a = x+y; which should be translated with an EXP node at the top.e. if (a<b) c=a; else c=b; translated using the a<b tree from part (c) above;the whole statement will therefore be rather clumsy and inefficient.f. if (a<b) c=a; else c=b; translated in a less clumsy way.7.2 Translate each of these MiniJava statements and expressions into IR trees, butusing the Ex, Nx, and Cx constructors as appropriate.

In each case, just draw pictures ofthe trees; an Ex tree will be a Tree Exp, an Nx tree will be a Tree Stm, anda Cx tree willbe a Stm with holes labeled trueand falseinto which labels can later be placed.a. a+5;b. b[i+1]=0;c. while (a<0) a=a+1;d. a<b moves a 1 or 0 into some newly defined temporary, and whose right-handside is the temporary.e. a = x+y;f. if (a<b) c=a; else c=b;7.3 Using the C compiler of your choice (or a compiler for another language), translatesome functions to assembly language.

On Unix this is done with the -S option to the Ccompiler.Then identify all the components of the calling sequence (items 1-11), and explainwhat each line of assembly language does (especially the pseudoinstructions thatcomprise items 1 and 11). Try one small function that returns without muchcomputation (a leaffunction), and one that calls another function before eventuallyreturning.•7.4 The Tree intermediate language has no operators for floating-point variables.Show how the language would look with new binops for floating-point arithmetic, andnew relops for floating-point comparisons. You may find it useful to introduce avariant of MEM nodes to describe fetching and storing floating-point values.140•*7.5 The Tree intermediate language has no provision for data values that are notexactly one word long. The C programming language has signed and unsignedintegers of several sizes, with conversion operators among the different sizes.Augment the intermediate language to accommodate several sizes of integers, withconversions among them.Hint: Do not distinguish signed values from unsigned values in the intermediate trees,but do distinguish between signed operators and unsigned operators.

See also Fraserand Hanson [1995], Sections 5.5 and 9.1.141Chapter 8: Basic Blocks and Tracesca-non-i-cal: reduced to the simplest or clearest schema possibleWebster's DictionaryOVERVIEWThe trees generated by the semantic analysis phase must be translated into assembly ormachine language. The operators of the Tree language are chosen carefully to match thecapabilities of most machines. However, there are certain aspects of the tree language that donot correspond exactly with machine languages, and some aspects of the Tree languageinterfere with compiletime optimization analyses.For example, it's useful to be able to evaluate the subexpressions of an expression in anyorder.

But the subexpressions of Tree.exp can contain side effects - ESEQ and CALL nodesthat contain assignment statements and perform input/output. If tree expressions did notcontain ESEQ and CALL nodes, then the order of evaluation would not matter.Some of the mismatches between Trees and machine-language programs are••••The CJUMP instruction can jump to either of two labels, but real machines'conditional jump instructions fall through to the next instruction if the condition isfalse.ESEQ nodes within expressions are inconvenient, because they make different ordersof evaluating subtrees yield different results.CALL nodes within expressions cause the same problem.CALL nodes within the argument-expressions of other CALL nodes will causeproblems when trying to put arguments into a fixed set of formal-parameter registers.Why does the Tree language allow ESEQ and two-way CJUMP, if they are so troublesome?Because they make it much more convenient for the Translate (translation to intermediatecode) phase of the compiler.We can take any tree and rewrite it into an equivalent tree without any of the cases listedabove.

Without these cases, the only possible parent of a SEQ node is another SEQ; all theSEQ nodes will be clustered at the top of the tree. This makes the SEQs entirely uninteresting;we might as well get rid of them and make a linear list of Tree.Stms.The transformation is done in three stages: First, a tree is rewritten into a list of canonicaltrees without SEQ or ESEQ nodes; then this list is grouped into a set of basic blocks, whichcontain no internal jumps or labels; then the basic blocks are ordered into a set of traces inwhich every CJUMP is immediately followed by its false label.Thus the module Canon has these tree-rearrangement functions:package Canon;public class Canon {static public Tree.StmList linearize(Tree.Stm s);}public class BasicBlocks {public StmListList blocks;142public Temp.Label done;public BasicBlocks(Tree.StmList stms);}StmListList(Tree.StmList head, StmListList tail);public class TraceSchedule {public TraceSchedule(BasicBlocks b);public Tree.StmList stms;}Linearize removes the ESEQs and moves the CALLs to top level.

Then BasicBlocksgroups statements into sequences of straight-line code. Finally, TraceSchedule orders theblocks so that every CJUMP is followed by its false label.8.1 CANONICAL TREESLet us define canonical trees as having these properties:1. No SEQ or ESEQ.2. The parent of each CALL is either EXP(…) or MOVE(TEMP t,…).TRANSFORMATIONS ON ESEQHow can the ESEQ nodes be eliminated? The idea is to lift them higher and higher in the tree,until they can become SEQ nodes.Figure 8.1 gives some useful identities on trees.143Figure 8.1: Identities on trees (see also Exercise 8.1).Identity (1) is obvious.

So is identity (2): Statement s is to be evaluated; then e1; then e2; thenthe sum of the expressions is returned. If s has side effects that affect e1 or e2, then either theleft-hand side or the right-hand side of the first equation will execute those side effects beforethe expressions are evaluated.Identity (3) is more complicated, because of the need not to interchange the evaluations of sand e1. For example, if s is MOVE(MEM(x), y) and e1 is BINOP(PLUS, MEM(x), z), then theprogram will compute a different result if s is evaluated before e1 instead of after.

Свежие статьи
Популярно сейчас