Download Control Flow Graphs for Real-Time System Analysis

Transcript
Contents
8.1
8.2
8.3
Basic Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
8.1.1
Objective Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
8.1.2
Program Start Constraint . . . . . . . . . . . . . . . . . . . . . . . . 120
8.1.3
Structural Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . 120
Loop Bound Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
8.2.1
Simple Loop Bound Constraints . . . . . . . . . . . . . . . . . . . . 122
8.2.2
Loop Bound Constraints for VIVU x ∞
8.2.3
Loop Bound Constraints for Arbitrary Mappings . . . . . . . . . . 127
. . . . . . . . . . . . . . . . 125
User Added Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
IV Evaluation
135
9 Experimental Results
137
9.1
Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
9.2
Decision Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
9.3
CFG Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
9.4
Path Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
10 Related Work
147
10.1 History of WCET Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
10.1.1 Abstract Interpretation . . . . . . . . . . . . . . . . . . . . . . . . . . 147
10.1.2 Worst-Case Execution Time Analysis . . . . . . . . . . . . . . . . . . 148
10.2 Decision Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
10.3 ICFG Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
10.4 Path Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
11 Conclusion
155
11.1 Decision Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
11.2 CFG Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
21