Modeling complex flows for worst-case execution time analysis

Knowing the worst-case execution time (WCET) of a program is necessary when designing and verifying real-time systems. The WCET depends both on the program flow (like loop iterations and function calls), and on hardware factors like caches and pipelines. In this paper, we present a method for representing program flow information that is compact while still being strong enough to handle the types of flow previously considered in WCET research. We also extend the set of representable flows compared to previous research. We give an algorithm for converting the flow information to the linear constraints used in calculating a WCET estimate in our WCET analysis tool. We demonstrate the practicality of the representation by modeling the flow of a number of programs, and show that execution time estimates can be made tighter by using flow information.