MIT 26 Control-flow analysis

CS 4120 Lecture 26Control-flow analysis28 October 2011Lecturer: Andrew Myers1 Loops, dominators, natural loops, control trees, dominator analysisThese topics are described in these slides.2 Using dominators for SSA conversionWe have seen that SSA form is a convenient form for optimization and analysis of code. However, converting code to SSA poses difficulties. In the previous lecture we observed that conversion could be brokendown into two steps:1.

Insert uses of φ-functions for various variables at the beginnings of basic blocks; that is, for a variablex that needs to use a φ-function, we insert x = φ(x, x).2. When enough uses of φ have been inserted, each use of a variable is reached by just one definition.Therefore, we can give each definition its own unique variable name, and rename all the corresponding uses reached by that definition. Note that the definitions of a variable include the new definitionsusing φ that were inserted in step 1.In Step 1 we don’t want to use φ more often than necessary, because this will create unnecessary variable names and impede optimization. Previously we identified the path convergence criterion as a way todetermine where φ-functions are needed: intuitively, φ is needed at a node when it is the earliest place thattwo paths from different definitions converge.

However, the path convergence criterion does not naturallylead to an efficient algorithm for finding these locations.The notion of dominators can be used to efficiently insert φ exactly where the path convergence criterionsays it should. The intuition is that if a node n defines a variable x, the path convergence criterion will notdemand that φ be used for x at any node dominated by n where the definition reaches. For example, inFigure 1, the nodes inside the colored boundary are all dominated by node n, and φ is not needed. Unlessthere is another definition of x inside the dominated region, the definition at n must be the only one thatreaches the node. Thus, node m does not need a φ-function for x, even though it has two predecessors. Onthe other hand, node n0 does need a φ-function, because it has a predecessor dominated by n, yet it is notitself dominated by n.startnn'mFigure 1: Dominators and SSA1We say that an edge crossing from a node dominated by n to a node not dominated by n lies on thedominance frontier for n.

And we consider the destination node of that edge (such as n0 ) to also lie on thedominance frontier. The nodes lying on the dominance frontier of n are exactly the nodes that to have thenew definition x = φ(x, x) added to them.Notice that adding this definition indeed adds a new definition to the control flow graph. And this newdefinition has its own dominance frontier that may induce additional definitions using φ.

However, thisiterated dominance frontier process will eventually converge on a set of φ definitions such that every node onthe dominance frontier of every definition of a variable x starts with a corresponding definition x = φ(x, x).3 Computing the dominance frontierLet DF (n) denote the dominance frontier of node n: the set of nodes not dominated by n, but with apredecessor dominated by n. Assuming we have computed the dominance relation, we can easily checkwhether any given node lies on the dominance frontier of node n. This observation leads to an obviousquadratic algorithm.However, we can make the computation of dominance frontiers more efficient by observing that everynode on the dominance frontier of n is either:• a direct successor of n• on the dominance frontier of some child c of n in the dominator tree.Thus, to compute the dominance frontier of n, we recursively compute the dominance frontier of eachof n’s children in the dominator tree, then iterate over the childrens’ dominance frontiers and the directsuccessors, checking whether each of these nodes is on the dominance frontier of n.2.