MIT 25 Reaching defnitions_ webs_ SSA

CS 4120 Lecture 25Reaching definitions, webs, SSA24 October 2011Lecturer: Andrew Myers1 Reaching definitionsRegister allocation allocates registers to variables. But sometimes allocating just one register to a variable isnot important. For example, consider the following code:int i = 1...i = i + 1...a[i] = 0There are two definitions of i in this code, and two uses. It is defined at the first and second lines shown,and used as the second and third lines. If we refer to these defs and uses as def1 and def2, and use1 anduse2 respectively, and then draw a graph in which each definition (def) is connected to each use that it canaffect, we get a disjoint graph:def1def2use1use2This suggests we can use two different registers to hold i, since the two uses of the variable don’tcommunicate.

Each of these uses has a smaller live range than the whole variable, so it may help us do abetter job of register allocation.Register allocation is one motivation for the analysis known as reaching definitions, though other optimizations also need this analysis. Reaching definitions attempts to determine which definitions may reacheach node in the CFG. A definition reaches a node if there is a path from the definition to the node, alongwhich the defined variable is never redefined.1.1Dataflow analysisWe can set up reaching definitions as a dataflow analysis. Since there is only one definition per node, wecan represent the set of definitions reaching a node as a set of nodes.

A definition reaches a node if it mayreach any incoming edge to the node:[in(n) =out(n0 )n0 ≺nA definition reaches the exiting edges of a node if it reaches the incoming edges and is not overwrittenby the node, or if it is defined by the node:out(n) = gen(n) ∪ (in(n) − kill (n))With defs(x) denoting the set of nodes that define variable x, gen(n) and kill (n) are defined very straighforwardly:gen(n) kill (n)nx=endefs(x)everything else∅∅1du1d1u2u3d2d3uFigure 1: DU-chain and UD-chainViewing this analysis through the lens of dataflow analysis frameworks, we can see that it works correctly and finds the meet-over-paths solution.

It is a forward analysis where the meet operation is ∪, so theordering on lattice values is ⊇ and the top value is ∅. The height of the lattice is the number of definitionsin the CFG, which is bounded by the number of nodes. So we have a finite-height lower semilattice with atop element. The transfer functions have the standard form we have already analyzed, which is monotonicand distributive, so the analysis is guaranteed to converge on the meet-over-paths solution.2 WebsUsing the reaching definitions for a CFG, we can analyze how defs and uses relate for a given variable.Suppose that for a given variable, we construct an undirected graph we will call the DU-graph, in whichthere is a node for each def of that variable and a node for each distinct use (if a CFG node both uses anddefines a variable, the def and the use will be represented as distinct nodes in the DU-graph). In this thereis an edge from a def to a use if the def reaches the node containing the use.

The graph above is an instanceof the DU-graph for the variable i.Any connected component of the DU-graph graph represents a set of defs and uses that ought to agreeon where the variable will be stored. For example, we showed that the DU-graph for variable i had twoconnected components. We refer to these connected components as webs. Webs are the natural unit ofregister allocation; in general, their liveness is less than that of variables, so using them avoids creatingspurious edges in the inference graph. Therefore the graph coloring problem is less constrained and thecompiler can do a better job of allocating registers.A standard way to think about construction of webs is in terms of DU-chains and UD-chains, depictedin Figure 1.

A DU-chain is a subgraph of the DU-graph connecting just one def to all of the uses it reaches.A UD-chain is a subgraph connecting a use to each of the defs that reach it. If a UD-chain and a DUchain intersect, they must be part of the same web. So a web is a maximal union of intersecting DU- andUD-chains.Once reaching definitions have been determined, webs can be computed efficiently using a disjoint-setunion data structure (union-find with path compression).3 Single static assignment formDifferent compiler optimizations can enable each other, and in general we want the compiler to run multiple optimizations repeatedly until no further improvement is possible. However, optimizations can alsoinvalidate analyses needed by other optimizations.

Rerunning these analyses repeatedly makes the compiler more complex and slower. Reaching definitions is a good example of an analysis that ends up beingrun repeatedly.Modern compilers typically use a slightly different CFG representation than the one we have beenstudying.

It is called single static assignment form, or SSA for short. The idea is to avoid nontrivial UDchains: each variable in SSA has exactly one def, and therefore each use does too.For example, consider the following code:2x = 0while (x < 10) {x = x + 1}This code has two definitions of x, so in SSA form it must have at least two distinct variables representingthe original x.

The resulting SSA CFG would be something like this:x1 = 0x3 = ϕ(x1, x2)if x3 < 0x2 = x3 + 1Boxes have been drawn around the basic blocks in this CFG, rather than around nodes. In the SSAliterature it is standard to work with basic blocks as the CFG nodes rather than with individual statementsas we have been doing. However, there is not much difference, and everything we have to say can betranslated to the statement-per-node approach.Note that the variable x has become three variables x1, x2, and x3 in this CFG. Variables x1 and x2correspond to the two definitions in the original program. Variable x3 arises because the use x<0 has anon-trivial UD-chain: both of the other definitions reach it.

To preserve the property that each variablehas just one definition, SSA form introduces a fictitious function φ (phi) that picks among its argumentsaccording to the edge along which control reached the current basic block. All uses of φ must occur atthe beginning of their basic block. Operationally, we can think of φ as implemented by simple assignmentstatements that occur along the incoming edges to the node: in the example, an assignment x2=x1 on theleft incoming edge from the top, and an assignment x2=x3 on the right incoming edge.With the use of the φ-function, every use has exactly one def, and the webs are all disjoint DU-chainsthat can be (and are) given distinct names.3.1Using SSAThe advantage of SSA is that it simplifies analysis and optimization.

For example, consider the followingfour optimizations, which all become simpler in SSA form.• Dead code removal. A definition x=e is dead iff there are no uses of x. We assume that for each def inthe program, we keep track of the set of corresponding uses. If that set is empty, the definition is deadand can be removed.

All use sets for variables in expression e can then be updated correspondinglyto remove this use.• Constant propagation. An assignment x=c, where c is a constant, can be propagated by replacing eachuse of x with c. This works because there is only one definition of x. The assignment is then deadcode and can be removed as described above.• Copy propagation. An assignment x=y can similarly be propagated, just like the copy propagation case.• Unreachable code.

Unreachable code can be removed, updating all use sets for variables used in thecode.3In fact, given code in SSA form and use sets for each variable, all four of these optimizations can beperformed in an interleaved fashion without further analysis. By contrast, performing interleaved optimizations in the original non-SSA form would require redoing dataflow analyses between optimizationpasses.3.2Converting to SSAThis improvement does not come for free, however.

We have to convert our CFG to SSA form, which istricky to do efficiently. The challenge is where to insert φ-functions so that every use has exactly one def.Once this property has been achieved, the resulting webs can be renamed (e.g., by adding subscripts totheir variable name) accordingly.A simple-minded approach is just to insert φ-functions for every variable at the head of every basicblock with more than one predecessor. But this creates a more complex CFG than necessary, with extravariables that slow down optimization.When does basic block z truly need to have the φ-function for a variable a; that is, inserting a = φ(a, a)at its beginning? This question can be answered using the path convergence criterion: the φ(a, a) is neededwhen:• There exist two nodes x and y that define variable a.• There are nonempty paths from x and y to z that are disjoint except at the final z node.