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