DOC PREVIEW
CSU CS 553 - LECTURE NOTES

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1CS553 Lecture Data-Flow Analysis Efficiency 1Speeding Up Data-Flow Analysis Last time– Various optimizations that use data-flow analysis Today– Speeding up data-flow analysisCS553 Lecture Data-Flow Analysis Efficiency 2Solving the Data-flow Equations Algorithm This is iterative data-flow analysis (for liveness analysis)for each node n in CFGin[n] = ∅; out[n] = ∅repeatfor each node n in CFGin’[n] = in[n]out’[n] = out[n]in[n] = use[n] ∪ (out[n] – def[n])out[n] = ∪ in[s]until in’[n]=in[n] and out’[n]=out[n] for all ns ∈ succ[n]initialize solutionssolve data-flow equationstest for convergencesave current resultsCS553 Lecture Data-Flow Analysis Efficiency 3Time Complexity (liveness) Consider a program of size N– Has N nodes in the flow graph and at most N variables– Each live-in or live-out set has at most N elements– Each set-union operation takes O(N) time– The for loop body– constant # of set operations per node– O(N) nodes ⇒ O(N2) time for the loop– Each iteration of the repeat loop can only make the set larger– Each set can contain at most N variables ⇒ 2N2 iterations Worst case: O(N4) Typical case: 2 to 3 iterations with good ordering & separability ⇒ O(N) to O(N2)CS553 Lecture Data-Flow Analysis Efficiency 4Efficiency (from lattice lecture) Parameters– n: Number of nodes in the CFG– k: Height of lattice– t: Time to execute one flow function Complexity– O(nkt) Relation to previous slide– n = N– k = N2 // used as worst-case for repeat loop– t = N2CS553 Lecture Data-Flow Analysis Efficiency 5Ways to improve data-flow analysis efficiency Node ordering– Visit nodes in an ordering that most efficiently propagates change Bitvectors– Use the tuple of lattices concept to implement the data-flow sets as bit-vectors Worklist– Only visit nodes where the input data-flow sets have changed Basic Blocks– Group statements with straight-forward control-flow Others– Structural or interval analysis– Slotwise analysis– SSACS553 Lecture Data-Flow Analysis Efficiency 6 3 bc c 5 a 2 a b 1 anode#use def in out in out in out in out in out in out in out 4 b a 6 c1st 2nd 3rd 4th 5th 6th 7thcaba abcaca bcbc bb aa acacac bcbc bb aac acaccac bcbc bb acac acc accac bcbc bbc acac acc accac bcbc bcbc acac acc accac bcbc bcbc acac acData-flow Equations for Livenessin[n] = use[n] ∪ (out[n] – def[n])out[n] = ∪ in[s]s ∈ succ[n]YesNo2b := a + 13c := c + b1a := 04a := b * 25a < 9?6return cExample (liveness)CS553 Lecture Data-Flow Analysis Efficiency 7Improving PerformanceConsider the (3→4) edge in the graph:out[4] is used to compute in[4]in[4] is used to compute out[3] . . .So we should compute the sets in theorder: out[4], in[4], out[3], in[3], . . .Data-flow Equations for Livenessin[n] = use[n] ∪ (out[n] – def[n])out[n] = ∪ in[s]s ∈ succ[n]The order of computation should follow the direction of flowout[4]in[4]out[3]YesNo2b := a + 13c := c + b1a := 04a := b * 25a < 9?6return cExample (cont)CS553 Lecture Data-Flow Analysis Efficiency 8 4 b a ac bc ac bc ac bc 2 a b bc ac bc ac bc ac 5 a c ac ac ac ac ac 1 a ac c ac c ac c 6 c c c cnode#use def out in out in out in 3 bc c bc bc bc bc bc bc1st 2nd 3rdConverges much faster!YesNo2b := a + 13c := c + b1a := 04a := b * 25a < 9?6return cIterating Through the Flow Graph Backwards3CS553 Lecture Data-Flow Analysis Efficiency 9Solving the Data-flow Equations (reprise) Algorithmfor each node n in CFGin[n] = ∅; out[n] = ∅repeatfor each node n in CFG in reverse post dfs orderin’[n] = in[n]out’[n] = out[n]out[n] = ∪ in[s]in[n] = use[n] ∪ (out[n] – def[n])until in’[n]=in[n] and out’[n]=out[n] for all ns ∈ succ[n]Initialize solutionsSolve data-flow equationsTest for convergenceSave current resultsCS553 Lecture Data-Flow Analysis Efficiency 10Effects on complexity Repeat loop– Conservative upper bound is that each iteration will only make one set larger by oneelement.– A better approximation for separable analyses is height of the lattice (k) times the depth ofthe graph (Knuth 1971, depth is 2.75 on average).– Now repeat loop complexity is k instead of N2. Representation of sets– For dense sets, use a bit vector representation– Use the tuple of lattices concept to implement the data-flow sets as bit-vectors.– Now time to execute one flow function (t) is N/(wordsize).– For sparse sets, use a sorted list (e.g., linked list) Worklist– Only visit nodes where the input data-flow sets have changed.– Does not change complexity, but makes it unnecessary for convergence check iteration inIDFA.CS553 Lecture Data-Flow Analysis Efficiency 11Basic Blocks Basic blocks– Decrease the size of the CFG by merging nodesthat have a single predecessor and a singlesuccessor into basic blocksNo1a := 03return c2b := a + 1c := c + 1a := b * 2 a > 9?Yes23YesNob := a + 1c := c + b4a := b * 25a < 9?6return c1a := 0CS553 Lecture Data-Flow Analysis Efficiency 12Concepts Efficient Data-Flow Analysis– Complexity analysis– Node ordering– Bit vector implementation– Basic blocks4CS553 Lecture Data-Flow Analysis Efficiency 13Next Time Reading– Ch 18.1, 19.5 Lecture– Control dependence– Loops–


View Full Document

CSU CS 553 - LECTURE NOTES

Download LECTURE NOTES
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view LECTURE NOTES and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view LECTURE NOTES 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?