Cooper_Engineering_a_Compiler(Second Edition) (Rice), страница 61

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.

Since a compiler spends most of its time manipulating the ir form ofthe code, these costs deserve some attention. While this discussion focuseson three-address codes, most of the points apply equally to stack-machinecode (or any other linear form).t1t2t3t4t5←←←←←2bt1 × t2at4 - t3Three-Address CodeThree-address codes are often implemented as a set of quadruples.

Eachquadruple is represented with four fields: an operator, two operands (orsources), and a destination. To form blocks, the compiler needs a mechanismto connect individual quadruples. Compilers implement quadruples in avariety of ways.Figure 5.5 shows three different schemes for implementing the threeaddress code for a - 2 × b, repeated in the margin. The simplest scheme, in5.3 Linear IRs 239TargetOpArg1t1t2t3t4t5←←2bt1at4×←-Arg2(a) Simple Arrayt2t3t1 ← 2t1 ← 2t2 ← bt2 ← bt3 × t1 t2t3 × t1 t2t4 ← at4 ← at5 - t4 t3t5 - t4 t3(b) Array of Pointers(c) Linked Listn FIGURE 5.5 Implementations of Three-Address Code for a - 2 × b.Figure 5.5a, uses a short array to represent each basic block.

Often, the compiler writer places the array inside a node in the cfg. (This may be the mostcommon form of hybrid ir.) The scheme in Figure 5.5b uses an array ofpointers to group quadruples into a block; the pointer array can be containedin a cfg node. The final scheme, in Figure 5.5c, links the quadruples togetherto form a list. It requires less storage in the cfg node, at the cost of restrictingaccesses to sequential traversals.Consider the costs incurred in rearranging the code in this block. The firstoperation loads a constant into a register; on most machines this translatesdirectly into an immediate load operation.

The second and fourth operationsload values from memory, which on most machines might incur a multicycledelay unless the values are already in the primary cache. To hide some of thedelay, the instruction scheduler might move the loads of b and a in front ofthe immediate load of 2.In the simple array scheme, moving the load of b ahead of the immediate load requires saving the four fields of the first operation, copying thecorresponding fields from the second slot into the first slot, and overwriting the fields in the second slot with the saved values for the immediateload. The array of pointers requires the same three-step approach, exceptthat only the pointer values must be changed.

Thus, the compiler saves thepointer to the immediate load, copies the pointer to the load of b intothe first slot in the array, and overwrites the second slot in the array withthe saved pointer to the immediate load. For the linked list, the operationsare similar, except that the complier must save enough state to let it traversethe list.Now, consider what happens in the front end when it generates the initialround of ir. With the simple array form and the array of pointers, the compiler must select a size for the array—in effect, the number of quadruplesthat it expects in a block. As it generates the quadruples, it fills in the array.If the array is too large, it wastes space.

If it is too small, the compiler must240 CHAPTER 5 Intermediate RepresentationsINTERMEDIATE REPRESENTATIONS IN ACTUAL USEIn practice, compilers use a variety of IRs. Legendary FORTRAN compilers ofyore, such as IBM’s FORTRAN H compilers, used a combination of quadruples and control-flow graphs to represent the code for optimization.

SinceFORTRAN H was written in FORTRAN, it held the IR in an array.For a long time, GCC relied on a very low-level IR, called register transfer language (RTL). In recent years, GCC has moved to a series of IRs. Theparsers initially produce a near-source tree; these trees can be languagespecific but are required to implement parts of a common interface. Thatinterface includes a facility for lowering the trees to the second IR, GIMPLE.Conceptually, GIMPLE consists of a language-independent, tree-like structure for control-flow constructs, annotated with three-address code forexpressions and assignments. It is designed, in part, to simplify analysis.Much of GCC’s new optimizer uses GIMPLE; for example, GCC builds staticsingle-assignment form on top of GIMPLE.

Ultimately, GCC translates GIMPLEinto RTL for final optimization and code generation.The LLVM compiler uses a single low-level IR; in fact, the name LLVM standsfor "low-level virtual machine." LLVM’s IR is a linear three-address code. TheIR is fully typed and has explicit support for array and structure addresses. Itprovides support for vector or SIMD data and operations. Scalar values aremaintained in SSA form throughout the compiler.

The LLVM environmentuses GCC front ends, so LLVM IR is produced by a pass that performs GIMPLEto-LLVM translation.The Open64 compiler, an open-source compiler for the IA-64 architecture, uses a family of five related IRs, called WHIRL. The initial translation inthe parser produces a near-source-level WHIRL. Subsequent phases of thecompiler introduce more detail to the WHIRL program, lowering the levelof abstraction toward the actual machine code.

This lets the compiler use asource-level AST for dependence-based transformations on the source textand a low-level IR for the late stages of optimization and code generation.reallocate it to obtain a larger array, copy the contents of the “too small”array into the new, larger array, and deallocate the small array. The linkedlist, however, avoids these problems. Expanding the list just requiresallocating a new quadruple and setting the appropriate pointer in thelist.A multipass compiler may use different implementations to represent their at different points in the compilation process.

In the front end, where thefocus is on generating the ir, a linked list might both simplify the implementation and reduce the overall cost. In an instruction scheduler, with its focuson rearranging the operations, either of the array implementations mightmake more sense.5.3 Linear IRs 241Notice that some information is missing from Figure 5.5. For example, nolabels are shown because labels are a property of the block rather than anyindividual quadruple. Storing a list of labels with the block saves space ineach quadruple; it also makes explicit the property that labels occur only onthe first operation in a basic block.

With labels attached to a block, the compiler can ignore them when reordering operations inside the block, avoidingone more complication.5.3.4 Building a Control-Flow Graphfrom a Linear CodeCompilers often must convert between different irs, often different stylesof irs. One routine conversion is to build a cfg from a linear ir such asiloc.

The essential features of a cfg are that it identifies the beginning andend of each basic block and connects the resulting blocks with edges thatdescribe the possible transfers of control among blocks. Often, the compilermust build a cfg from a simple, linear ir that represents a procedure.As a first step, the compiler must find the beginning and the end of each basicblock in the linear ir. We will call the initial operation of a block a leader.An operation is a leader if it is the first operation in the procedure, or if ithas a label that is, potentially, the target of some branch. The compiler canidentify leaders in a single pass over the ir, shown in Figure 5.6a.