K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 61
Текст из файла (страница 61)
Compare and contrast the difficulty of writing a prettyprinter for aparse tree, an AST and a DAG. What additional information would beneeded to reproduce the original code’s format precisely?2. How does the number of edges in a dependence graph grow as afunction of the input program’s size?5.3 LINEAR IRSThe alternative to a graphical ir is a linear ir.
An assembly-language program is a form of linear code. It consists of a sequence of instructions thatexecute in their order of appearance (or in an order consistent with thatorder). Instructions may contain more than one operation; if so, those operations execute in parallel. The linear irs used in compilers resemble theassembly code for an abstract machine.Prettyprintera program that walks a syntax tree and writesout the original code236 CHAPTER 5 Intermediate RepresentationsThe logic behind using a linear form is simple. The source code that servesas input to the compiler is a linear form, as is the target-machine code thatit emits.
Several early compilers used linear irs; this was a natural notation for their authors, since they had previously programmed in assemblycode.Linear irs impose a clear and useful ordering on the sequence of operations.For example, in Figure 5.3, contrast the iloc code with the data-dependencegraph. The iloc code has an implicit order; the dependence graph imposes apartial ordering that allows many different execution orders.If a linear ir is used as the definitive representation in a compiler, it mustinclude a mechanism to encode transfers of control among points in theprogram.
Control flow in a linear ir usually models the implementation ofcontrol flow on the target machine. Thus, linear codes usually include conditional branches and jumps. Control flow demarcates the basic blocks in alinear ir; blocks end at branches, at jumps, or just before labelled operations.Taken branchIn most ISAs, conditional branches use one label.Control flows either to the label, called the takenbranch, or to the operation that follows the label,called the not-taken or fall-through branch.In the iloc used throughout this book, we include a branch or jump at theend of every block. In iloc, the branch operations specify a label for boththe taken path and the not-taken path. This eliminates any fall-through pathsat the end of a block.
Together, these stipulations make it easier to find basicblocks and to reorder them.Many kinds of linear irs have been used in compilers.nDestructive operationan operation in which one of the operands isalways redefined with the resultnnOne-address codes model the behavior of accumulator machines andstack machines. These codes expose the machine’s use of implicitnames so that the compiler can tailor the code for it. The resulting codeis quite compact.Two-address codes model a machine that has destructive operations.These codes fell into disuse as memory constraints became lessimportant; a three-address code can model destructive operationsexplicitly.Three-address codes model a machine where most operations take twooperands and produce a result. The rise of risc architectures in the1980s and 1990s made these codes popular, since they resemble asimple risc machine.The remainder of this section describes two linear irs that remain popular:stack-machine code and three-address code.
Stack-machine code offers acompact, storage-efficient representation. In applications where ir size matters, such as a Java applet transmitted over a network before execution,stack-machine code makes sense. Three-address code models the instructionformat of a modern risc machine; it has distinct names for two operands and5.3 Linear IRs 237a result.
You are already familiar with one three-address code: the iloc usedin this book.5.3.1 Stack-Machine CodeStack-machine code, a form of one-address code, assumes the presence ofa stack of operands. Most operations take their operands from the stackand push their results back onto the stack. For example, an integer subtract operation would remove the top two elements from the stack and pushtheir difference onto the stack. The stack discipline creates a need for somenew operations. Stack irs usually include a swap operation that interchangesthe top two elements of the stack. Several stack-based computers have beenbuilt; this ir seems to have appeared in response to the demands of compiling for these machines.
Stack-machine code for the expression a - 2 × bappears in the margin.push 2push bmultiplypush asubtractStack-Machine CodeStack-machine code is compact. The stack creates an implicit name spaceand eliminates many names from the ir. This shrinks the size of a programin ir form. Using the stack, however, means that all results and argumentsare transitory, unless the code explicitly moves them to memory.Stack-machine code is simple to generate and to execute. Smalltalk 80 andJava both use bytecodes, a compact ir similar in concept to stack-machinecode.
The bytecodes either run in an interpreter or are translated into targetmachine code just prior to execution. This creates a system with a compactform of the program for distribution and a reasonably simple scheme forporting the language to a new target machine (implementing the interpreter).Bytecodean IR designed specifically for its compact form;typically code for an abstract stack machineThe name derives from its limited size; opcodesare limited to one byte or less.5.3.2 Three-Address CodeIn three-address code most operations have the form i ← j op k, with anoperator (op), two operands (j and k) and one result (i).
Some operators, such as an immediate load and a jump, will need fewer arguments.Sometimes, an operation with more than three addresses is needed. Threeaddress code for a - 2 × b appears in the margin. iloc is another example ofa three-address code.Three-address code is attractive for several reasons.
First, three-address codeis reasonably compact. Most operations consist of four items: an operation and three names. Both the operation and the names are drawn fromlimited sets. Operations typically require 1 or 2 bytes. Names are typicallyrepresented by integers or table indices; in either case, 4 bytes is usuallyenough. Second, separate names for the operands and the target give thecompiler freedom to control the reuse of names and values; three-addresscode has no destructive operations. Three-address code introduces a new sett1t2t3t4t5←←←←←2bt1 × t2at4 - t3Three-Address Code238 CHAPTER 5 Intermediate Representationsof compiler-generated names—names that hold the results of the variousoperations. A carefully chosen name space can reveal new opportunitiesto improve the code.
Finally, since many modern processors implementthree-address operations, a three-address code models their properties well.Within three-address codes, the set of specific supported operators and theirlevel of abstraction can vary widely. Often, a three-address ir will containmostly low-level operations, such as jumps, branches, and simple memory operations, alongside more complex operations that encapsulate controlflow, such as max or min.
Representing these complex operations directlymakes them easier to analyze and optimize.For example, mvcl (move characters long) takes a source address, a destination address, and a character count. It copies the specified number ofcharacters from memory beginning at the source address to memory beginning at the destination address. Some machines, like the ibm 370, implementthis functionality in a single instruction (mvcl is a 370 opcode). On machinesthat do not implement the operation in hardware, it may require manyoperations to perform such a copy.Adding mvcl to the three-address code lets the compiler use a compact representation for this complex operation.
It allows the compiler to analyze,optimize, and move the operation without concern for its internal workings.If the hardware supports an mvcl-like operation, then code generation willmap the ir construct directly to the hardware operation. If the hardware doesnot, then the compiler can translate mvcl into a sequence of lower-level iroperations or a procedure call before final optimization and code generation.5.3.3 Representing Linear CodesMany data structures have been used to implement linear irs. The choicesthat a compiler writer makes affect the costs of various operations on ircode.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
