Proliferation of Data-flow Problems COMP 512 Rice University Houston, Texas Spring 2009 Copyright 2009, Keith D. Cooper & Linda Torczon, all rights reserved. Students enrolled in Comp 512 at Rice University have explicit permission to make copies of these materials for their personal use. Data-flow Basics: Review from Last Lecture •! Graph, sets, equations, & initial values define a problem >! Sets form a semilattice >! Equations treated as transfer functions >! Properties of semilattice & transfer functions determine termination, and correctness •! Dominator calculation >! One of the simplest forward data-flow problems •! Liveness information >! A typical (backwards) global data-flow problem •! Both DOM and LIVE are well behaved >! Admissible frameworks with unique fixed points •! Postorder, rPostorder, Preorder, & rPreorder COMP 512, Spring 2009! 2!Today’s Lecture •! Framework properties and speed of convergence >! Kam-Ullman rapid condition >! Worklist iterative algorithm •! More data-flow problems >! Available expressions >! Very busy expressions >! Constant propagation (Kildall style, not SCCP) •! Problems that don’t fit the Kam-Ullman model for speed COMP 512, Spring 2009! 3!COMP 512, Spring 2009! 4!Iterative Data-flow Analysis Correctness •! If every fn ! F is monotone, i.e., f(x!y) ! f(x) " f(y), and •! If the lattice is bounded, i.e., every descending chain is finite >! Chain is sequence x1, x2, …, xn where xi ! L, 1 ! i ! n >! xi > xi+1, 1 ! i < n # chain is descending Then •! The round-robin algorithm computes a least fixed-point (LFP) •! The uniqueness of the solution depends on other properties of F •! Unique solution # it finds the one we want •! Multiple solutions # we need to know which one it finds Reference materialCOMP 512, Spring 2009! 5!Iterative Data-flow Analysis Correctness •! Does the iterative algorithm compute the desired answer? Admissible Function Spaces 1.! $ f ! F, $ x,y ! L, f (x "y) = f (x) " f (y) 2. % fi ! F such that $ x ! L, fi(x) = x 3. f,g ! F % h ! F such that h(x ) = f (g(x)) 4. $ x ! L, % a finite subset H & F such that x = "f ! H f (') If F meets these four conditions, then an instance of the problem will have a unique fixed point solution (instance " graph + initial values) # LFP = MFP = MOP # order of evaluation does not matter * Both DOM & LIVE meet all four criteria If meet does not distribute over function application, then the fixed point solution may not be unique. The iterative algorithm will find a LFP. Reference material COMP 512, Spring 2009! 6!Iterative Data-flow Analysis Speed •! For a problem with an admissible function space & a bounded semilattice, •! If the functions all meet the rapid condition, i.e., $f,g ! F, $ x ! L, f (g(')) " g(') " f (x) " x then, a round-robin, reverse-postorder iterative algorithm will halt in d(G)+3 passes over a graph G d(G) is the loop-connectedness of the graph w.r.t a DFST >! Maximal number of back edges in an acyclic path >! Several studies suggest that, in practice, d(G) is small (<3) >! For most CFGs, d(G) is independent of the specific DFST Sets stabilize in two passes around a loop Each pass does O(E ) meets & O(N ) other operations * Both DOM & LIVE are rapid frameworksCOMP 512, Spring 2009! 7!Iterative Data-flow analysis What does this mean? •! Reverse postorder >! Easily computed order that increases propagation per pass •! Round-robin iterative algorithm >! Visit all the nodes in a consistent order (RPO) >! Do it again until the sets stop changing •! Rapid condition >! Most classic global data-flow problems meet this condition These conditions are easily met >! Admissible framework, rapid function space >! Round-robin, reverse-postorder, iterative algorithm #! The analysis runs in (effectively) linear time COMP 512, Spring 2009! 8!The Round-robin Iterative Algorithm LIVEOUT(nf ) ( Ø for all other nodes n LIVEIN(n) ( UEVAR(n) change ( true while (change) change ( false for i ( 0 to N n ( rPreorder(i) TEMP ( )s#succ(n) LIVEIN(s) if LIVEOUT(n) # TEMP then change ( true LIVEOUT(n ) ( TEMP LIVEIN(n) ( UEVAR(x) ) (LIVEOUT(x) $ VARKILL(x)) Meet operation We could, for brevity, fold the transfer function into the computation of LIVEOUTand eliminate the need to represent LIVEIN. We use this formulation for clarity. Transfer functionCOMP 512, Spring 2009! 9!The Worklist Iterative Algorithm Worklist ( { all nodes, ni } LIVEOUT(nf) ( Ø for all other nodes n LIVEIN(n) ( UEVAR(n) while (Worklist *Ø) remove a node n from Worklist TEMP( )s#succ(n) LIVEIN(s) if LIVEOUT(n) # TEMP then LIVEOUT(ni ) ( TEMP LIVEIN(ni) ( UEVAR(x) ) (LIVEOUT(x) $ VARKILL(x)) Worklist ( Worklist ) preds(n) This algorithm avoids re-evaluating LIVEOUT when none of its constituents has changed. Thus, it does fewer set operations on LIVEOUT & LIVEIN than the round-robin algorithm. It does manipulate the Worklist, which is an added cost. Implement the Worklist as a set – no duplicate entries COMP 512, Spring 2009! 10!Round-robin Versus Worklist Algorithm Termination, correctness, & complexity arguments are for the round-robin version •! The worklist algorithm does less work; it visits fewer nodes •! Consider a version with two worklists: current & next >! Draw nodes from current in RPO; add them to next >! Swap the worklists when current becomes empty (1 r-r pass) >! Makes same changes, in same order, as round robin >! Termination & correctness arguments should carry over •! Is this the best order? Maybe not … >! Iterate around a loop until it stabilizes >! Many data structures for worklist, many orders >! Your mileage will vary (measurable effect ) Worklist algorithm is a sparse version of round-robin algorithmCOMP 512, Spring 2009! 11!Iterative Data-flow Analysis How do we use these results? •! Prove that data-flow framework is admissible & rapid >! Its just algebra >! Most (but not all) global data-flow problems are rapid >! This is a property of F •! Code up an iterative algorithm >! World’s simplest data-flow algorithm •! Rely on the results >! Theoretically sound, robust algorithm This lets us ignore most of the other data-flow algorithms in 512 COMP 512, Spring 2009! 12!Live Variables Transformation: Eliminating unneeded stores •!e in a register, have seen last definition, never