15-745 Lecture 2Dataflow AnalysisA sample programSimple Constant PropagationReaching DefinitionsReaching Definitions (ex)Slide 7Calculating Reaching DefinitionsGen and kill for each stmtComputing in[n] and out[n]What is pred[n]?What order to eval nodes?Example:Example (pass 1)Example (pass 2)An Improvement: Basic BlocksBB setsSlide 18Slide 19Forward DataflowHow to implement?Implementing RDRD Worklist algorithmStoring Rd informationDef-use chains are valuable tooUsing RD for Simple Const. Prop.Better Constant PropagationSlide 28Loop Invariant Code MotionSlide 30Liveness (def-use chains)Liveness as a dataflow problemDead Code EliminationSlide 34When can we do CSE?Available ExpressionsComputing Available ExpressionsSlide 38Slide 39Constructing Gen & KillSlide 41ExampleSlide 43Slide 44Slide 45Slide 46Slide 47Slide 48CSESlide 50Calculating RESlide 52Dataflow SummaryDataflow FrameworkDef-Use chains are expensiveSlide 56Slide 57Advantages of SSASSAStraight-line SSASlide 61Slide 62Merging at JoinsSlide 64Slide 65The function“Implementing” Trivial SSAMinimal SSAAnother ExampleSlide 71Lets optimize the following:First, turn into SSAProperties of SSAConstant PropagationOther stuff we can do?Slide 77Slide 78Slide 79Slide 80SummaryConditional Constant PropagationCCPLecture 2 15-745 © Seth Copen Goldstein 2005-8 115-745 Lecture 2Dataflow AnalysisBasic BlocksRelated OptimizationsSSACopyright © Seth Copen Goldstein 2005-8Lecture 2 15-745 © Seth Copen Goldstein 2005-8 2Dataflow Analysis•Last time we looked at code transformations–Constant propagation–Copy propagation–Common sub-expression elimination–…•Today, dataflow analysis:–How to determine if it is legal to perform such an optimization–(Not doing analysis to determine if it is beneficial)Lecture 2 15-745 © Seth Copen Goldstein 2005-8 3A sample programint fib10(void) {int n = 10;int older = 0;int old = 1;int result = 0;int i;if (n <= 1) return n;for (i = 2; i<n; i++) {result = old + older;older = old;old = result;}return result;}1: n <- 102: older <- 03: old <- 14: result <- 05: if n <= 1 goto 146: i <- 27: if i > n goto 138: result <- old + older9: older <- old10: old <- result11: i <- i + 112: JUMP 713: return result14: return nWhat are those numbers?Lecture 2 15-745 © Seth Copen Goldstein 2005-8 4Simple Constant Propagation1: n <- 102: older <- 03: old <- 14: result <- 05: if n <= 1 goto 146: i <- 27: if i > n goto 138: result <- old + older9: older <- old10: old <- result11: i <- i + 112: JUMP 713: return result14: return n•Can we do SCP?•How do we recognize it?•What aren’t we doing?•Metanote:–keep opts simple!–Use combined powerLecture 2 15-745 © Seth Copen Goldstein 2005-8 5Reaching Definitions•A definition of variable v at program point d reaches program point u if there exists a path of control flow edges from d to u that does not contain a definition of v.1: n <- 102: older <- 03: old <- 14: result <- 05: if n <= 1 goto 146: i <- 27: if i > n goto 138: result <- old + older9: older <- old10: old <- result11: i <- i + 112: JUMP 713: return result14: return n1234567814910111213Lecture 2 15-745 © Seth Copen Goldstein 2005-8 6Reaching Definitions (ex)•1 reaches 5, 7, and 14•2 reaches 8•Older in 8 is reached by–2–9•Tells us which definitions reach a particular use (ud-info)1: n <- 102: older <- 03: old <- 14: result <- 05: if n <= 1 goto 146: i <- 27: if i > n goto 138: result <- old + older9: older <- old10: old <- result11: i <- i + 112: JUMP 713: return result14: return nLecture 2 15-745 © Seth Copen Goldstein 2005-8 7Reaching Definitions (ex)•1 reaches 5, 7, and 14•2 reaches 8•Older in 8 is reached by–2–9•Tells us which definitions reach a particular use (ud-info)1: n <- 102: older <- 03: old <- 14: result <- 05: if n <= 1 goto 146: i <- 27: if i > n goto 138: result <- old + older9: older <- old10: old <- result11: i <- i + 112: JUMP 713: return result14: return n14, Really? Meta-notes:•(almost) always conservative•only know what we know•Keep it simple:•What opt(s), if run before this would help•What about:1: x <- 02: if (false) x<-13: … x …•Does 1 reach 3?•What opt changes this?Lecture 2 15-745 © Seth Copen Goldstein 2005-8 8Calculating Reaching Definitions•A definition of variable v at program point d reaches program point u if there exists a path of control flow edges from d to u that does not contain a definition of v.•Build up RD stmt by stmt•Stmt s, “d: v <- x op y”, generates d•Stmt s, “d: v <- x op y”, kills all other defs(v)Or,•Gen[s] = { d }•Kill[s] = defs(v) – { d }Lecture 2 15-745 © Seth Copen Goldstein 2005-8 9Gen and kill for each stmt1: n <- 10 12: older <- 0 2 93: old <- 1 3 104: result <- 0 4 85: if n <= 1 goto 146: i <- 2 6 117: if i > n goto 138: result <- old + older 8 49: older <- old 9 210: old <- result 10 311: i <- i + 1 11 612: JUMP 713: return result14: return nGen killHow can we determine the defs that reach a node?We can use:• control flow information• gen and kill infoLecture 2 15-745 © Seth Copen Goldstein 2005-8 10Computing in[n] and out[n]•In[n]: the set of defs that reach thebeginning of node n•Out[n]: the set of defs that reach theend of node nin[n] =out[n] = •Initialize in[n]=out[n]={} for all n•Solve iteratively][][poutnpredp])[][(][ nkillninngen Lecture 2 15-745 © Seth Copen Goldstein 2005-8 11What is pred[n]?•Pred[n] are all nodes that can reach n in the control flow graph.•E.g., pred[7] = { 6, 12 }1: n <- 102: older <- 03: old <- 14: result <- 05: if n <= 1 goto 146: i <- 27: if i > n goto 138: result <- old + older9: older <- old10: old <- result11: i <- i + 112: JUMP 713: return result14: return n1234567814910111213Lecture 2 15-745 © Seth Copen Goldstein 2005-8 12What order to eval nodes?•Does it matter?•Lets do: 1,2,3,4,5,14,6,7,13,8,9,10,11,121: n <- 102: older <- 03: old <- 14: result <- 05: if n <= 1 goto 146: i <- 27: if i > n goto 138: result <- old + older9: older <- old10: old <- result11: i <- i + 112: JUMP 713: return result14: return n1234567814910111213Lecture 2 15-745 © Seth Copen Goldstein 2005-8 13Example:•Order: 1,2,3,4,5,14,6,7,13,8,9,10,11,12][][][poutninnpredp])[][(][][ nkillninngennout 1: n <- 10 1 12: older <- 0 2 9 1 1,23: old <- 1 3 10 1,2 1-34: result <- 0 4 85: if n <= 1 goto 146: i <- 2 6 117: if i > n goto 138: result <- old + older 8 49: older <- old 9 210: old <- result 10
View Full Document