Automatic Derivation of Loop Bounds and Infeasible Paths for WCET Analysis Using Abstract Execution
- 1 January 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10528725,p. 57-66
- https://doi.org/10.1109/rtss.2006.12
Abstract
Static worst-case execution time (WCET) analysis is a technique to derive upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. A key component for statically deriving safe and tight WCET bounds is information on the possible program flow through the program. Such flow information can be provided manually by user annotations, or automatically by a flow analysis. To make WCET analysis as simple and safe as possible, it should preferably be automatically derived, with no or very limited user interaction. In this paper we present a method for deriving such flow information called abstract execution. This method can automatically calculate loop bounds, bounds for including nested loops, as well as many types of infeasible paths. Our evaluations show that it can calculate WCET estimates automatically, without any user annotations, for a range of benchmark programs, and that our techniques for nested loops and infeasible paths sometimes can give substantially better WCET estimates than using loop bounds analysis onlyKeywords
This publication has 11 references indexed in Scilit:
- Towards a Flow Analysis for Embedded System C ProgramsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Applying Static WCET Analysis to Automotive Communication SoftwarePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Faster WCET flow analysis by program slicingPublished by Association for Computing Machinery (ACM) ,2006
- Clustered Worst-Case Execution-Time CalculationIEEE Transactions on Computers, 2005
- Tighter timing predictions by automatic detection and exploitation of value-dependent constraintsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Safe and efficient elimination of infeasible execution paths in WCET estimationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On the false path problem in hard real-time programsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Tighten the computation of worst-case execution-time by detecting feasible pathsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Supporting Timing Analysis by Automatic Bounding of Loop IterationsReal-Time Systems, 2000
- Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpointsPublished by Association for Computing Machinery (ACM) ,1977