Cooper K.Engineering a compiler

Figure 6.4: The data-dependence graph

extensive analysis of array subscript values to determine when references to the same array can overlap.

6.3.6Static Single Assignment Graph

The static single assignment graph (ssa) directly represents the flow of values in a manner similar to the data-dependence graph. Ssa form was designed to help in analyzing and improving code in a compiler. It lacks the clear relationship to original syntax found in a syntax tree or an ast. Similarly, it does not cleanly encode the flow of control; deriving control-flow relationships from the ssa graph may take some analysis, just as it would from the ast. However, its orientation toward analysis and optimization can pay o in an optimizing compiler (see Chapters 13 and 14).

In the ssa graph, the nodes are individual statements in the code. An edge runs from each reference to a value (a use) back to the node where the value was created (a definition). In a direct implementation of this notion, each reference has one or more edges that lead back to definitions. Ssa simplifies this picture with the addition of two simple rules.

1.Each definition has a unique name.

2.Each use refers to a single definition.

These two constraints simplify both the ssa graph and any code that manipulates it. However, to reconcile these two rules with the reality of imperative programs, the compiler must modify the code. It must create a new name space and insert some novel instructions into the code to preserve its meaning under this new name space.

SSA Names To construct ssa form, the compiler must make a pass over the code to rename each definition and each use. To make the relationship between ssa-names and original names explicit, all the literature on ssa creates new names by adding subscripts to the original names. Thus, the first definition of x becomes x0, while the second becomes x1. Renaming can be done in a linear pass over the code.

Digression: Building SSA

Static single assignment form is the only ir we describe that does not have an obvious construction algorithm. While the e cient algorithm is complex enough to merit its own section in Chapter 13, a sketch of the construction process will clarify some of the mysteries surrounding ssa.

Assume that the input program is already in iloc form. To convert it to an equivalent linear form of ssa, the compiler must:

1.insert φ-functions

2.rename iloc-virtual registers

The di cult parts of the algorithm involve determining where φ-functions are needed and managing the renaming process to work e ciently. The simplest ssa-construction algorithm would insert a φ-function for each iloc-virtual register at the start of each basic block that has more than one predecessor in the control-flow graph. (This inserts many unneeded φ-functions.)

To rename variables, the compiler can process the blocks, in a depthfirst order. When a definition of ri is encountered, it increments the current subscript for ri. At the end of a block, it looks down each control-flow edge and rewrites the appropriate φ-function parameter in each block that has multiple predecessors.

Of course, many bookkeeping details must be handled to make this work. The resulting ssa form has extraneous φ-functions. Some of these could be eliminated by noticing that a φ-function has identical arguments for each entering edge. For example, the operation x17 ← φ(x7,x7,x7) serves no useful purpose. More precise algorithms for ssa construction eliminate most of the unneeded φ-functions.

φ-functions To reconcile the conflict that arises when distinct values flow along di erent paths into a single basic block, the ssa construction introduces new statements, called φ-functions. A φ-function takes as arguments the ssa-names for the value on each control-flow edge entering the block. It defines a new ssa name for use in subsequent references. When control enters a block, all of its φ-functions execute concurrently. Each one defines its output ssa-name with the value of its argument that corresponds to the most recently traversed control-flow edge.

These properties make ssa-form a powerful tool. The name space eliminates any issues related to the lifetime of a value. Since each value is defined in exactly one instruction, it is available along any path that proceeds from that instruction. The placement of φ-functions provides the compiler with information about the flow of values; it can use this information to improve the quality of code that it generates. The combination of these properties creates a representation that allows for accurate and e cient analysis.

We have described ssa as a graphical form. Many implementations embed this graphical form into a linear ir by introducing a new ir operator for the

following sequence of assignments:

x1 ← φ(x0, x2) y1 ← φ(x1, y2)

Since the two φ-functions are defined to execute concurrently, they read their arguments, then define their outputs. If the first entry was along the path corresponding to the second argument, the meaning is well defined. However, along the other path, y1 receives the uninitialized versions of x1, even though the clear intent is that it receive the value of x1 after execution of the φ-function. While this example seems contrived, it is a simplified version of a problem that can arise if the compiler applies transformations to the ssa-form that rewrite names. In the translation from ssa-form back into executable code, the compiler must take care to recognize situations like this and generate code that serializes the assignments in the appropriate order.

6.4Linear IRs

The alternative to structural irs is, quite naturally, a linear form of ir. Some of the earliest compilers used linear forms; this was a natural notation for the authors, since they had previously programmed in assembly code.

The logic behind using linear forms is simple; the compiler must eventually emit a stream of instructions for the code being translated. That target machine code is almost always a linear form. Linear irs impose a clear and useful ordering on the sequence of operations; for example, contrast the linear form of ssa with the graphical form, both shown in Figure 6.5.

When a linear form is used as the definitive representation, it must include a mechanism to encode transfers of control between di erent points in the program. This is usually done with branch and conditional branch operations. The code in a linear representation can be divided into basic blocks, or maximal length sequences of straight-line code, and the control-flow related operations that begin and end basic blocks. For our current purposes, every basic block begins with a label and ends with a branch. We include the branch at the end of the block, even if it is not strictly necessary. This makes it easier to manipulate the blocks; it eliminates implicit ordering between blocks that might otherwise exist.

6.4.1One-Address Code

One-address code, also called stack machine code, assumes the presence of an operand stack. Most operations manipulate the stack; for example, an integer subtract operation would remove the top two elements from the stack and push their di erence onto the stack (push(pop() - pop()), assuming left to right evaluation). The stack discipline creates a need for some new operations; for example, stack irs usually include a swap operation that interchanges the top two elements of the stack. Several stack-based computers have been built; oneaddress code seems to have appeared in response to the demands of compiling for these machines. The left column of Figure 6.6 shows an example.

6.4.3Three-Address Code

The term three-address code is used to describe many di erent representations. In practice, they all have a common feature; they admit statements of the form x op y z with a single operator and, at most, three names. Practical forms of three-address code have operators that take fewer operands; load immediate is a common example. If ssa is being encoded into the three-address ir, the compiler writer may add a mechanism for representing arbitrary arity φ-functions. Threeaddress code can include forms of prefix or postfix code. The rightmost column of Figure 6.6 shows an expression translated into three-address code.

Three-address code is attractive for several reasons. The code is compact, relative to most graphical representations. It introduces a new set of names for values; a properly chosen name space can reveal opportunities for generating better code. It resembles many actual computers, particularly risc microprocessors.

Within three-address codes, there exists a wide variation on the specific operators and their level of abstraction. Often, a single ir will contain low-level operations, such as branches, loads, and stores with no addressing modes, along with relatively high-level operations like mvcl, copy, max, or min. The critical distinction is that operations involving internal control flow are encoded in a single high-level operation. This allows the compiler to analyze, transform, and move them without respect to their internal control flow. At a later stage in compilation, the compiler expands these high-level operations into lower level operations for final optimization and code generation.

Quadruples Quadruples are a straight forward implementation of three-address code. A quadruple has four fields, one operator, two operands, or sources, and a destination operand. The set of quadruples that represents a program is held in a k × 4 array of small integers. All names are explicit. This data structure is easy to manipulate.

The iloc code used throughout this book is an example of quadruples. The example code from Figure 6.6 would be represented as follows:

The primary advantage of quadruples is simplicity; this leads to fast implementations, since most compilers generate good code for simple array accesses.

Triples Triples are a more compact form of three-address code. In a triples representation, the index of the operation in the linear array of instructions is used as an implicit name. This eliminates one fourth of the space required by quadruples. The strength of this notation is its introduction of a unique and implicit name space for values created by operations. Unfortunately, the name

space is directly related to instruction placement, so that reordering instructions is di cult. (The compiler must update all references with the new location.) Here is the short example in a triples form:

Using the implicit name space has reduced the necessary storage.

Indirect Triples Indirect triples address the primary shortcoming of triples— the di culty of reordering statements. In the indirect triple representation, operations are represented in a table of triples. Additionally, the compiler keeps a list of “statements” that specifies the order in which the triples occur. This makes the implicit names in the triple array permanent; to reorder operations, the compiler simply moves pointers in the statement list.

Indirect triples have two advantages over quadruples. First, reordering statements involves moving a single pointer; in the quadruple representation it involved moving all four fields. Second, if the same statement occurs multiple times, it can be represented once and referenced several places in the statement list. (The equivalent savings can be obtained in a dag or by hash-consing).

Static Single Assignment Form In Section 6.3.6, we described ssa as a graphical ir. An alternate way to use ssa is to embed it into a linear ir, such as a threeaddress code. In this scheme, the compiler writer simply adds a φ instruction to the ir and has the compiler modify the code appropriately. This requires insertion of φ instructions at the appropriate control-flow merge-points and renaming variables and values to reflect the ssa name space.

The linear form of ssa is an attractive alternative to a graphical representation. It can be interpreted as the graph when desired; it can be treated as a linear ir when that approach is preferable. If the compiler maintains some correspondence between names and instructions in the ir, either through a naming discipline or a lookaside table, the linear ssa can be interpreted as providing pointers from references back to the definitions whose values they use. Such pointers are useful in optimization; they are called use-definition chains.

The primary complication introduced by adding φ-instructions to iloc is the fact that the φ-instruction needs an arbitrary number of operands. Consider the

end of a case statement. The control-flow graph has an edge flowing from each individual case into the block immediately following the case statement. Thus, the φ-functions in that block need an argument position for each individual case in the preceding case statement.

Choosing Between Them Quadruples are simple, but they require the most space. Triples achieve a space savings of twenty-five percent by making it expensive to reorder operations. Indirect triples make reordering better and have the possibility of saving space by eliminating duplication. The real cost of indirect triples lies in the extra memory operations required to reach each statement; as memory latencies rise, this tradeo becomes less desirable. Ssa can be implemented in any of these schemes.

6.5Mapping Values to Names

The irs described in Sections 6.3 and 6.4 represent the various operations that form the source program. The choice of specific operations to represent the code determines, to a large extent, how the compiler can translate and optimize the code. The mapping of values to names also has a strong influence on the code that the compiler can generate. If the name space hides the relationship between values, the compiler may be unable to rediscover those connections. Similarly, by implicitly encoding information about values in the name space, the compiler can expose selected facts to subsequent analysis and optimization.

6.5.1Naming Temporary Values

In translating source code into an ir, the compiler must invent names for many of the intermediate stages in the compiler. We refer to the set of names used to express a computation as the name space of the computation. The choice of name spaces has a surprisingly strong impact on the behavior of the compiler. The strategy for mapping names onto values will determine, to a large extent, which computations can be analyzed and optimized.

Consider again the example of an array reference A[i,j] shown in Section 6.2. The two ir fragments represent the same computation. The low-level ir exposes more details to the compiler. These details can be inferred from the ast and code can be generated. In a straight forward translation from the ast, each reference to A[i,j] will produce the same code in the executable, independent of context.

With the low-level ir, each intermediate step has its own name. This exposes those results to analysis and to transformation. In practice, most of the improvement that compilers can achieve in optimization arises from capitalizing on context. As an alternative to the linear code, the compiler could use a lowerlevel ast that exposed the entire address computation. This would probably use more space, but it would allow the compiler to examine the component parts of the address computation.

Naming is a critical part of ssa-form. Ssa imposes a strict discipline that generates names for every value computed by the code—program variable or

Digression: The Impact of Naming

In the late 1980s, we built an optimizing compiler for Fortran. We tried several di erent naming schemes in the front-end. The first version generated a new temporary for each computation by bumping a “next register” counter. This produced large name spaces, i.e., 985 names for the 210 line Singular Value Decomposition (svd) routine from Forsythe, Malcolm, and Moler’s book on numerical methods [32]. The large name space caused problems with both space and speed. The data-flow analyzer allocated several sets for each basic block. Each set was the size of the name space.

The second version used a simple allocate/free protocol to conserve names. The front end allocated temporaries on demand and freed them when the immediate uses were finished. This produced smaller name spaces, i.e., svd used 60 names. This sped up compilation. For example, it reduced the time to compute Live variables for svd by sixty percent.

Unfortunately, associating multiple expressions with a single temporary name obscured the flow of data and degraded the quality of optimization. The decline in code quality overshadowed any compile-time benefits.

Further experimentation led to a short set of rules that yielded strong optimization while mitigating growth in the name space.

1.Each textual expression received a unique name, determined by entering the operator and operands into a hash table. This ensured that each occurrence of r17 + r21 targets the same register.

2. In op ri, rj rk, k is chosen so that i < k and j < k.

3.Move operations, ri rj , are allowed to have i > j, unless j represents a scalar program variable.. The virtual register corresponding to such a variable is only set by move operations. Expressions evaluate into their “natural” register, then are moved to a variable.

4.Whenever a store to memory occurs, like store ri rj , it is immediately followed by a copy from ri into the variable’s virtual register.

This scheme space used about 90 names for svd, but exposed all the optimizations found with the first name space. The compiler used these rules until we adopted ssa-form, with its own naming discipline.

transitory intermediate value. This uniform treatment exposes many details to the scrutiny of analysis and improvement. It encodes information about where the value was generated. It provides a “permanent” name for the value, even if the corresponding program variable gets redefined. This can improve the results of analysis and optimization.

6.5.2Memory Models

Just as the mechanism for naming temporary values a ects the information that can be represented in an ir version of a program, so, too, does the compiler’s

method of choosing storage locations for each value. The compiler must determine, for each value computed in the code, where that value will reside. For the code to execute, the compiler must assign a specific location such as register r13 or sixteen bytes from the label L0089. Before the final stages of code generation, however, the compiler may use symbolic addresses that encode a level in the memory hierarchy, i.e. registers or memory, but not a specific location within that level.

As an example, consider the iloc examples used throughout the book. A symbolic memory address is denoted by prefixing it with the character @. Thus, @x is the o set of x from the start of its storage area. Since r0 holds the activation record pointer, an operation that uses @x and r0 to compute an address depends, implicitly, on the decision to store the variable x in the memory reserved for the current procedure’s activation record.

In general, compilers work from one of two memory models.

Register-to-register model: Under this model, the compiler keeps values in registers aggressively, ignoring any limitations imposed by the size of the machine’s physical register set. Any value that can legally be kept in a register is kept in a register. Values are stored to memory only when the semantics of the program require it—for example, at a procedure call, any local variable whose address is passed as a parameter to the called procedure must be stored back to memory. A value that cannot be kept in a register is stored in memory. The compiler generates code to store its value each time it is computed and to load its value at each use.

Memory-to-memory model: Under this model, the compiler assumes that all values are kept in memory locations. Values move from memory to a register just before they are used. Values move from a register to memory just after they are defined. The number of register names used in the ir version of the code is small compared to the register-to-register model. In a memory-to-memory model, the designer may find it worthwhile to include memory-to-memory forms of the basic operations, such as a memory-to- memory add.

The choice of memory model is mostly orthogonal to the choice of ir. The compiler writer can build a memory-to-memory ast or a memory-to-memory version of iloc just easily as register-to-register versions of these irs. (Oneaddress code might be an exception; it contains its own unique memory model— the stack. A one-address format makes much less sense without the implicit naming scheme of stack-based computation.)

The choice of memory model has an impact on the rest of the compiler. For example, with a register-to-register model, the compiler must perform register allocation as part of preparing the code for execution. The allocator must map the set of virtual registers onto the physical registers; this often requires insertion of extra load, store, and copy operations. Under a register-to-register model, the allocator adds instructions to make the program behave correctly on the target machine. Under a memory-to-memory model, however, the pre-allocation code