Lecture 15Control Dependence GraphsKenneth M. AndersonCSCI 5828, Spring 2000This lecture comes from...A Compositional Approach toInterprocedural Control DependenceAnalysisJudith StaffordSoftware Engineering Research LaboratoryDepartment of Computer ScienceUniversity of Colorado at Boulderhttp://www.cs.colorado.edu/serl©2000 Jud ith A. S taffordUniversity of Co lorado at BoulderThe Roadmap➽ Introduction to Dependence Analysis" Current State of Affairs and Limitations" Judy’s Approach -- A Compositional Model" Related Work©2000 Jud ith A. S taffordUniversity of Co lorado at BoulderMy Big Program Doesn’t Workxoxoxoxoxoxoxoxoxoxoxoxoxooxxoxoxoxoxoxoooxxoxoxooxoxoxoxoxoxoxoxoxoxoxoxxoxoxoxxoxoxoxoxxoxoxoxoxxoxoxoxxoxoxoxoxoxxxoooxoxxoxoxoxoxoxoxoxoxxoxoxoxoxxoxoxoxooxxoxoxoxoxoxoooxxoxoxooxoxoxoxoxoxoxoxoxoxoxxoxoxoxxoxoxoxoxoxxxoooxoxxoxoxoxoxoxoxoxoxxoxoxoxoxoxoxoxoxoxoxoxoxooxxoxoxoxoxoxoooxxoxoxooxoxoxoxoxoxoxoxoxoxoxoxxoxoxoxxoxoxoxoxxoxoxoxoxxoxoxoxxoxoxoxoxoxxxoooxoxxoxoxoxoxoxoxoxoxxoxoxoxoxxoxoxoxooxxoxoxoxoxoxoooxxoxoxooxoxoxoxoxoxoxoxoxoxoxxoxoxoxxoxoxoxoxoxxxoooxoxxoxoxoxoxoxoxoxoxxoxoxoxoxoxoxoxoxoxoxoxoxooxxoxoxoxoxoxoooxxoxoxooxoxoxoxoxoxoxoxoxoxoxoxxoxoxoxxoxoxoxoxxoxoxoxoxxoxoxoxoxoxxxoooxoxxoxoxoxoxoxoxoxooxprint VALUExoxoxoooxxoxoxooxoxoxoxoxoxoxoxoxoxoxxoxoxoxxoxoxoxoxoxxxoooxoxxoxoxoxoxoxoxoxoxWhy is the printed VALUE wrong?©2000 Jud ith A. S taffordUniversity of Co lorado at BoulderBut Where To Look?xoxoxoxoxoxoxoxoxoxoxoxoxooxxoxoxoxoxoxoooxxoxoxooxoxoxoxoxoxoxoxoxoxoxoxxoxoxoxxoxoxoxoxxoxoxoxoxxoxoxoxxoxoxoxoxoxxxoooxoxxoxoxoxoxoxoxoxoxxoxoxoxoxxoxoxoxooxxoxoxoxoxoxoooxxoxoxooxoxoxoxoxoxoxoxoxoxoxxoxoxoxxoxoxoxoxoxxxoooxoxxoxoxoxoxoxoxoxoxxoxoxoxoxoxoxoxoxoxoxoxoxooxxoxoxoxoxoxoooxxoxoxooxoxoxoxoxoxoxoxoxoxoxoxxoxoxoxxoxoxoxoxxoxoxoxoxxoxoxoxxoxoxoxoxoxxxoooxoxxoxoxoxoxoxoxoxoxxoxoxoxoxxoxoxoxooxxoxoxoxoxoxoooxxoxoxooxoxoxoxoxoxoxoxoxoxoxxoxoxoxxoxoxoxoxoxxxoooxoxxoxoxoxoxoxoxoxoxxoxoxoxoxoxoxoxoxoxoxoxoxooxxoxoxoxoxoxoooxxoxoxooxoxoxoxoxoxoxoxoxoxoxoxxoxoxoxxoxoxoxoxxoxoxoxoxxoxxoxoxoxoxoxoxoxoxoxxxoooxoxxoxoxoxoxoxxoxoxoxoxoxoxoxooxPRINT VALUExoxoxoooxxoxoxooxoxoxoxoxoxoxoxoxoxoxxoxoxoxxoxoxoxoxoxxxoooxoxxoxoxoxoxoxoxoxoxI wish I knew where to concentrate my search.©2000 Jud ith A. S taffordUniversity of Co lorado at BoulderSimple Bug Tracking Example1: read i2: if ( i == 1)3: print “POS:”else4: i = 15: print i6: endProgram Simple" Question: What statementsof Simple could contain thebug that causes it to alwaysprint “1”?– Answer: 1, 2, or 4– How do we find the answer?©2000 Jud ith A. S taffordUniversity of Co lorado at BoulderGetting Started1: read i2: if ( i == 1)3: print “POS:”else4: i = 15: print i6: endProgram Simple" Best to start your searchwhere the bad value isprinted -- statement 5" It looks like the value usedat statement 5 comes fromstatement 4©2000 Jud ith A. S taffordUniversity of Co lorado at BoulderConditional Execution" But then you notice thatstatement 4 might noteven be executed becauseit depends on the decisionmade at statement 21: read i2: if ( i == 1)3: print “POS:”else4: i = 15: print i6: endProgram Simple©2000 Jud ith A. S taffordUniversity of Co lorado at Boulder" The decision made atstatement 2 depends onwhat value is input atstatement 1" The value printed at 5may come directly fromstatement 11: read i2: if ( i == 1)3: print “POS:”else4: i = 15: print i6: endProgram SimpleVariable Assignment©2000 Jud ith A. S taffordUniversity of Co lorado at BoulderThe Answer" So only statements 1, 2,and 4 could contain thebug…✷ This is helpful1: read i2: if ( i == 1)3: print “POS:”else4: i = 15: print i6: endProgram Simple©2000 Jud ith A. S taffordUniversity of Co lorado at BoulderThe Big QuestionHow do we automaticallyidentify dependenciesin REAL program code?1: read i2: if ( i == 1)3: print “POS:”else4: i = 15: print i6: endProgram SimpleProgramDependenceInformation©2000 Jud ith A. S taffordUniversity of Co lorado at BoulderControl FlowGraphProgram DependenceGraphControl DependenceGraphData DependenceGraphProgram CodeA Graph-Based ModelForward DominanceTree©2000 Jud ith A. S taffordUniversity of Co lorado at BoulderControl FlowGraphProgram DependenceGraphControl DependenceGraphData DependenceGraphProgram CodeA Graph-Based ModelForward DominanceTree©2000 Jud ith A. S taffordUniversity of Co lorado at BoulderA Control Dependence Representation" Represent control dependencies in a control dependencegraph, “CDG”CDG2156entry34• Vertices represent executable statements• Arcs represent direct control dependence• A distinguished entry vertex representingthe start of the program1: read i2: if ( i == 1)3: print “POS:”else4: i = 15: print i6: endProgram Simple©2000 Jud ith A. S taffordUniversity of Co lorado at BoulderA Control Dependence Representation" If statement X determines whether statement Y isexecuted, statement Y is control dependent onstatement XCDG2156entry341: read i2: if ( i == 1)3: print “POS:”else4: i = 15: print i6: endProgram SimpleXY©2000 Jud ith A. S taffordUniversity of Co lorado at BoulderA Control Dependence Representation" If statement X determines whether statement Y isexecuted, statement Y is control dependent onstatement XCDG2156entry341: read i2: if ( i == 1)3: print “POS:”else4: i = 15: print i6: endProgram SimpleXY©2000 Jud ith A. S taffordUniversity of Co lorado at BoulderA Control Dependence Representation" Statements that are guaranteed to execute are controldependent on entry to the programCDG2156entry341: read i2: if ( i == 1)3: print “POS:”else4: i = 15: print i6: endProgram Simple©2000 Jud ith A. S taffordUniversity of Co lorado at BoulderControl FlowGraphProgram DependenceGraphControl DependenceGraphData DependenceGraphForward DominanceTreeProgram CodeA Graph-Based Model©2000 Jud ith A. S taffordUniversity of Co lorado at Boulder625134A Graph Representation of Behavior1: read i2: if ( i == 1 )3: print “POS:”else4: i = 15: print i6: endProgram Simple" The control flow graph, “CFG”• Vertices represent executable statements• One entry and one exit• Arcs represent potential control flow©2000 Jud ith A. S taffordUniversity of Co lorado at BoulderCalculating Control DependenciesCDG2156entry34625134CFGHow can we useCFGs togenerate CDGs?©2000 Jud ith A. S taffordUniversity of Co lorado at BoulderCalculating Control DependenciesCDG2156entry34625134CFGThe control dependentscome after a decision andbefore a junction...©2000
View Full Document
Unlocking...