Technical Report 2001-012

Efficient Longest Executable Path Search for Programs with Complex Flows and Pipeline Effects

Friedhelm Stappert, Andreas Ermedahl, and Jakob Engblom

June 2001


Knowing the Worst-Case Execution Time (WCET) of a program is necessary when designing and verifying real-time systems. A correct WCET calculation method must take into account the possible program flow, like loop iterations and function calls, as well as effects of hardware features, like caches and pipelines.

In this paper we describe our work on calculating the WCET of programs with complex flow information using a path-based approach, and on how pipeline information can be efficiently included in the calculation. The result is a set of algorithms that allows for efficient and precise calculation of the WCET of programs with more complex flows and pipeline effects than was previously possible.

This technical report is an extended version of the conference submission.

Available as compressed Postscript (4.24 MB, no cover) and PDF (443 kB, no cover)

Download BibTeX entry.