Lecture 15 Control Dependence Graphs A Compositional Approach to Interprocedural Control Dependence Analysis Judith Stafford Kenneth M Anderson CSCI 5828 Spring 2000 This lecture comes from Software Engineering Research Laboratory Department of Computer Science University of Colorado at Boulder http www cs colorado edu serl The Roadmap My Big Program Doesn t Work Introduction to Dependence Analysis Current State of Affairs and Limitations Judy s Approach A Compositional Model Related Work xoxoxoxoxoxoxoxoxo xoxoxoxoox xoxoxo xoxoxooox xoxoxoo xoxoxo xoxoxo xoxo xoxo xox Why is the printed xoxoxox xoxoxoxoxxoxoxoxox xoxoxox VALUE wrong xoxoxox xoxoxoxoxxoxoxoxox xoxoxox xoxoxo xoxoxxxoooxox xoxoxoxo xoxo xoxox xoxoxoxox xoxoxoxoox xoxoxo xoxoxooox xoxoxoo xoxoxo xoxoxo xoxoxoxox xoxoxox xoxoxo xoxoxxxoooxox xoxoxoxo xoxo xoxox 2000 Judith A Stafford xoxoxoxoxoxoxoxoxo xoxoxoxoox xoxoxo xoxoxooox xoxoxoo xoxoxo xoxoxo xoxo xoxo xox University of Colorado at Boulder 2000 Judith A Stafford xoxoxo xoxoxxxoooxox xoxoxoxo xoxo xoxox xoxoxoxox xoxoxoxoox xoxoxo xoxoxooox xoxoxoo xoxoxo xoxoxo xoxoxoxox xoxoxox xoxoxo xoxoxxxoooxox xoxoxoxo xoxo xoxox xoxoxoxoxoxoxoxoxo xoxoxoxoox xoxoxo xoxoxooox xoxoxoo xoxoxo xoxoxo xoxo xoxo xox xoxoxox xoxoxoxoxxoxoxoxox xoxoxo xoxoxxxoooxox xoxoxoxo xoxoxoxoox print VALUE xoxoxooox xoxoxoo xoxoxo xoxoxo xoxoxoxox xoxoxox xoxoxo xoxoxxxoooxox xoxoxoxo xoxo xoxox University of Colorado at Boulder Simple Bug Tracking Example But Where To Look xoxoxoxoxoxoxoxoxo xoxoxoxoox xoxoxo xoxoxooox xoxoxoo xoxoxo xoxoxo xoxo xoxo xox xoxoxoxoxoxoxoxoxo xoxoxoxoox xoxoxo xoxoxooox xoxoxoo xoxoxo xoxoxo xoxo xoxo xox I wish I knew where to concentrate my search xoxoxox xoxoxox xoxoxoxoxxoxoxoxox xoxoxox xoxoxo xoxoxxxoooxox xoxoxoxo xoxo xoxox xoxoxoxoxxoxoxoxox xoxoxox xoxoxo xoxoxxxoooxox xoxoxoxo xoxo xoxox xoxoxoxox xoxoxoxoox xoxoxo xoxoxooox xoxoxoo xoxoxo xoxoxo xoxoxoxox xoxoxox xoxoxo xoxoxxxoooxox xoxoxoxo xoxo xoxox xoxoxoxox xoxoxoxoox xoxoxo xoxoxooox xoxoxoo xoxoxo xoxoxo xoxoxoxox xoxoxox xoxoxo xoxoxxxoooxox xoxoxoxo xoxo xoxox 2000 Judith A Stafford xoxoxoxoxoxoxoxoxo xoxoxoxoox xoxoxo xoxoxooox xoxoxoo xoxoxo xoxoxo xoxo xoxo xox Best to start your search where the bad value is printed statement 5 It looks like the value used at statement 5 comes from statement 4 2000 Judith A Stafford Question What statements of Simple could contain the bug that causes it to always print 1 Answer 1 2 or 4 How do we find the answer xoxoxox xoxoxoxoxxoxoxoxox xoxxoxoxoxo xoxoxo xoxoxxxoooxox xoxoxoxo xoxxoxoxoxo xoxoxoxoox PRINT VALUE Program Simple 1 read i 2 if i 1 3 print POS else 4 i 1 5 print i 6 end xoxoxooox xoxoxoo xoxoxo xoxoxo xoxoxoxox xoxoxox xoxoxo xoxoxxxoooxox xoxoxoxo xoxo xoxox University of Colorado at Boulder Getting Started 2000 Judith A Stafford University of Colorado at Boulder Conditional Execution Program Simple 1 read i 2 if i 1 3 print POS else 4 i 1 5 print i 6 end University of Colorado at Boulder But then you notice that statement 4 might not even be executed because it depends on the decision made at statement 2 2000 Judith A Stafford Program Simple 1 read i 2 if i 1 3 print POS else 4 i 1 5 print i 6 end University of Colorado at Boulder Variable Assignment The decision made at statement 2 depends on what value is input at statement 1 The value printed at 5 may come directly from statement 1 2000 Judith A Stafford The Answer Program Simple 1 read i 2 if i 1 3 print POS else 4 i 1 5 print i 6 end University of Colorado at Boulder The Big Question So only statements 1 2 and 4 could contain the bug This is helpful Program Simple 1 read i 2 if i 1 3 print POS else 4 i 1 5 print i 6 end University of Colorado at Boulder 2000 Judith A Stafford A Graph Based Model Program Code Program Simple 1 read i 2 if i 1 3 print POS else 4 i 1 5 print i 6 end How do we automatically identify dependencies in REAL program code Control Flow Graph Data Dependence Graph Program Dependence Information 2000 Judith A Stafford University of Colorado at Boulder Forward Dominance Tree Control Dependence Graph Program Dependence Graph 2000 Judith A Stafford University of Colorado at Boulder A Graph Based Model A Control Dependence Representation Program Code Control Flow Graph Data Dependence Graph Represent control dependencies in a control dependence graph CDG Forward Dominance Tree Program Simple 1 read i 2 if i 1 3 print POS else 4 i 1 5 print i 6 end Control Dependence Graph Vertices represent executable statements Arcs represent direct control dependence A distinguished entry vertex representing the start of the program CDG entry 1 2 3 5 6 4 Program Dependence Graph University of Colorado at Boulder 2000 Judith A Stafford A Control Dependence Representation If statement X determines whether statement Y is executed statement Y is control dependent on statement X X Y 2000 Judith A Stafford Program Simple 1 read i 2 if i 1 3 print POS else 4 i 1 5 print i 6 end CDG 1 2 3 A Control Dependence Representation If statement X determines whether statement Y is executed statement Y is control dependent on statement X X entry 5 6 Y 4 University of Colorado at Boulder University of Colorado at Boulder 2000 Judith A Stafford 2000 Judith A Stafford Program Simple 1 read i 2 if i 1 3 print POS else 4 i 1 5 print i 6 end CDG 1 entry 2 3 5 6 4 University of Colorado at Boulder A Control Dependence Representation Program Code Statements that are guaranteed to execute are control dependent on entry to the program Program Simple 1 read i 2 if i 1 3 print POS else 4 i 1 5 print i 6 end CDG 1 2 3 Control Flow Graph Forward Dominance Tree entry 5 Data Dependence Graph 6 4 Control Dependence Graph Program Dependence Graph University of Colorado at Boulder 2000 Judith A Stafford A Graph Representation of Behavior A Graph Based Model University of Colorado at Boulder 2000 Judith A Stafford Calculating Control Dependencies The control flow graph CFG Program Simple 1 read i 2 if i 1 3 print POS else 4 i 1 5 print i 6 end 2000 Judith A Stafford Vertices represent executable statements One entry and one exit Arcs represent potential control flow 1 2 1 2 3 How can we use CFGs to generate CDGs CFG 3 4 5 6 4 CDG 1 5 6 2 3 University of Colorado at Boulder 2000 Judith A Stafford entry 5 6 4 University of Colorado at Boulder Calculating Control Dependencies Calculating Control Dependencies The control dependents come after a decision and before a junction CFG 1 2 3 Use the dominance tree in
View Full Document
Unlocking...