K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 64
Текст из файла (страница 64)
The right column shows the same code in ssa form.Variable names include subscripts to create a distinct name for each definition. φ-functions have been inserted at points where multiple distinct valuescan reach the start of a block. Finally, the while construct has been rewrittenwith two distinct tests, to reflect the fact that the initial test refers to x0 whilethe end-of-loop test refers to x2 .The φ-function’s behavior depends on context. It defines its target ssa namewith the value of its argument that corresponds to the edge along which5.4 Mapping Values to Names 247x0 ← · · ·y0 ← · · ·x ← ···y ← ···while(x < 100)x ← x + 1y ← y + xif (x0 ≥ 100) goto nextloop: x1 ← φ(x0 ,x2 )y1 ← φ(y0 ,y2 )x2 ← x1 + 1y2 ← y1 + x2if (x2 < 100) goto loopnext: x3 ← φ(x0 ,x2 )y3 ← φ(y0 ,y2 )(a) Original Code(b) Code in SSA Formn FIGURE 5.9 A Small Loop in SSA Form.control entered the block. Thus, when control flows into the loop from theblock above the loop, the φ-functions at the top of the loop body copy thevalues of x0 and y0 into x1 and y1 , respectively.
When control flows intothe loop from the test at the loop’s bottom, the φ-functions select their otherarguments, x2 and y2 .On entry to a basic block, all of its φ-functions execute concurrently, beforeany other statement. First, they all read the values of the appropriate arguments, then they all define their target ssa names. Defining their behavior inthis way allows the algorithms that manipulate ssa form to ignore the ordering of φ-functions at the top of a block—an important simplification. It cancomplicate the process of translating ssa form back into executable code, aswe shall see in Section 9.3.5.ssa form was intended for code optimization.
The placement of φ-functionsin ssa form encodes information about both the creation of values and theiruses. The single-assignment property of the name space allows the compiler to sidestep many issues related to the lifetimes of values; for example,because names are never redefined or killed, the value of a name is available along any path that proceeds from that operation. These two propertiessimplify and improve many optimization techniques.The example exposes some oddities of ssa form that bear explanation.
Consider the φ-function that defines x1 . Its first argument, x0 , is defined in theblock that precedes the loop. Its second argument, x2 , is defined later in theblock labelled loop. Thus, when the φ first executes, one of its argumentsis undefined. In many programming-language contexts, this would causeproblems.
Since the φ-function reads only one argument, and that argument248 CHAPTER 5 Intermediate RepresentationsTHE IMPACT OF NAMINGIn the late 1980s, we experimented with naming schemes in a FORTRANcompiler. The first version generated a new temporary register for eachcomputation by bumping a simple counter. It produced large name spaces,for example, 985 names for a 210-line implementation of the singular valuedecomposition (SVD). The name space seemed large for the program size.It caused speed and space problems in the register allocator, where thesize of the name space governs the size of many data structures.
(Today,we have better data structures and faster machines with more memory.)The second version used an allocate/free protocol to manage names. Thefront end allocated temporaries on demand and freed them when theimmediate uses were finished. This scheme used fewer names; for example,SVD used roughly 60 names. It sped up allocation, reducing, for example,the time to find live variables in SVD by 60 percent.Unfortunately, associating multiple expressions with a single temporaryname 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 strongoptimization while mitigating growth in the name space.1.
Each textual expression received a unique name, determined byentering the operator and operands into a hash table. Thus, eachoccurrence of an expression, for example, r17 +r21 , targeted thesame register.2. In hopi ri , rj ⇒ rk , k was chosen so that i,j < k.3. Register copy operations (i2i ri ⇒ rj in ILOC) were allowed to havei > j only if rj corresponded to a scalar program variable. The registersfor such variables were only defined by copy operations.
Expressionsevaluated into their "natural" register and then were moved into theregister for the variable.4. Each store operation (store ri ⇒ rj in ILOC) is followed by a copyfrom ri into the variable’s named register. (Rule 1 ensures that loadsfrom that location always target the same register.
Rule 4 ensures thatthe virtual register and memory location contain the same value.)This name-space scheme used about 90 names for SVD, but exposed all theoptimizations found with the first name-space scheme. The compiler usedthese rules until we adopted SSA form, with its discipline for names.corresponds to the most recently taken edge in the cfg, it can never read theundefined value.φ-functions do not conform to a three-address model.
A φ-function takesan arbitrary number of operands. To fit ssa form into a three-address ir, the5.4 Mapping Values to Names 249BUILDING SSAStatic single-assignment form is the only IR we describe that does not havean obvious construction algorithm. Section 9.3 presents the algorithm indetail. However, a sketch of the construction process will clarify some ofthe issues. Assume that the input program is already in ILOC form. Toconvert it to an equivalent linear form of SSA, the compiler must first insertφ-functions and then rename the ILOC virtual registers.The simplest way to insert φ-functions adds one for each ILOC virtual register at the start of each basic block that has more than one predecessorin the control-flow graph. This inserts many unneeded φ-functions; mostof the complexity in the full algorithm is aimed at reducing the number ofextraneous φ-functions.To rename the ILOC virtual registers, the compiler can process the blocks,in a depth-first order.
For each virtual register, it keeps a counter. Whenthe compiler encounters a definition of ri , it increments the counter forri , say to k, and rewrites the definition with the name ri . As the compilerktraverses the block, it rewrites each use of ri with rik until it encountersanother definition of ri . (That definition bumps the counter to k + 1.) Atthe end of a block, the compiler looks down each control-flow edge andrewrites the appropriate φ-function parameter for ri in each block thathas multiple predecessors.After renaming, the code conforms to the two rules of SSA form.
Eachdefinition creates a unique name. Each use refers to a single definition. Several better SSA construction algorithms exist; they insert fewer φ-functionsthan this simple approach.compiler writer must include a mechanism for representing operations withlonger operand lists. Consider the block at the end of a case statement asshown in the margin.The φ-function for x17 must have an argument for each case.
A φ-operationhas one argument for each entering control-flow path; thus, it does not fitinto the fixed-arity, three-address scheme.In a simple array representation for three-address code, the compiler writermust either use multiple slots for each φ-operation or use a side data structureto hold the φ-operations’ arguments. In the other two schemes for implementing three-address code shown in Figure 5.5, the compiler can inserttuples of varying size. For example, the tuples for load and load immediatemight have space for just two names, while the tuple for a φ-operation couldbe large enough to accommodate all its operands.switch on y0x1← ... x2 ← ...x15 ← ... x16 ← ...x17 ←φ (...)250 CHAPTER 5 Intermediate Representations5.4.3 Memory ModelsJust as the mechanism for naming temporary values affects the information that can be represented in an ir version of a program, so, too, does thecompiler’s choice of a storage location for each value.
The compiler mustdetermine, 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 asregister r13 or 16 bytes from the label L0089. Before the final stages of codegeneration, however, the compiler may use symbolic addresses that encodea level in the memory hierarchy, for example, registers or memory, but nota specific location within that level.Consider the iloc examples used throughout this book.
A symbolic memoryaddress is denoted by prefixing it with the character @. Thus, @x is the offsetof × from the start of the storage area containing it. Since rarp holds theactivation record pointer, an operation that uses @x and rarp to compute anaddress depends, implicitly, on the decision to store the variable x in thememory reserved for the current procedure’s activation record.In general, compilers work from one of two memory models.1. Register-to-Register Model Under this model, the compiler keepsvalues in registers aggressively, ignoring any limitations imposed by thesize of the machine’s physical register set.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
