WCET Computation

Pipeline Analysis

   The pipeline analysis models the pipeline behavior to determine execution times for a sequential flow (basic block) of instructions. It takes into account the current pipeline state(s), in particular the resource occupancies, the contents of prefetch queues, the grouping of instructions, and the classification of memory references as cache hits or misses. The result is an execution time for each instruction in each distinguished execution context.

Path Analysis

   Following from the results of the microarchitecture analyses, the path analysis determines a safe estimate of the WCET. The program’s control flow is modeled by an integer linear program, so that the solution to the objective function is the predicted worst-case execution time for the input program. A special mapping of variable names to basic blocks in the integer linear program provides for a computation of execution and traversal counts for every basic block edge.

Analysis of Loops and Recursive Procedures

   Loops and recursive procedures are of special interest, since programs spend most of their runtime there. Treating them naïvely when analyzing programs for their cache and pipeline behavior will result in a high loss of precision.

   Frequently, the following observation can be made: the first execution of the loop body usually loads the cache, and subsequent executions find most of their referenced memory blocks in the cache. Hence, the first iteration of the loop often encounters cache contents quite different from those of later iterations. This has to be taken into account when analyzing the behavior of a loop in the cache. A naïve analysis would combine the abstract cache states from the entry to the loop and from the return from the loop body, thereby losing most of the contents. Therefore, it is useful to distinguish the first iteration of loops from the others.

   A method has been designed and implemented in the program analyzer generator PAG, which virtually unrolls loops once, the so-called VIVU approach (virtual inlining, virtual unrolling). Memory references are now considered in different execution contexts, essentially nestings of first and non-first iterations of loops.

Next: Supported microprocessors | Previous: Reconstruction of the control flow from binaries | Contents | Home