- aiT
- Features
- Screenshots
- How it works
- Precision
- aiT + SCADE
- Reviews
- Free trial
- Contact
The
WCET determination is composed of several different tasks.
- Reconstruction of the control flow from binary executables
- Value analysis: computation of address ranges for instructions accessing memory
- Cache analysis: classification of memory references as cache misses or hits
- Pipeline analysis: predicting the behavior of the program on the processor pipeline
- Path analysis: determination of the worst-case execution path of the program
- Analysis of loops and recursive procedures
Many of these tasks are quite complex for modern microprocessors and DSPs.
The arrangement of the tasks is described in the picture to the right. The results of the value analysis are used by the cache analysis to predict the behavior of the (data) cache. The results of the cache analysis are fed into the pipeline analysis allowing the prediction of pipeline stalls due to cache misses. The combined results of the cache and pipeline analyses are used to compute the execution time of program paths.
The separation of WCET determination into several phases has the additional effect that different methods tailored to subtasks can be used. In our case, the value analysis, the cache analysis, and the pipeline analysis are done by abstract interpretation, a semantics-based method for static program analysis. Path analysis is done by integer linear programming.
Reconstruction of the control flow from binary programs
The starting point of our analysis framework is a binary program and optional additional user-provided information about numbers of loop iterations, upper bounds for recursion, etc.
In the first step a parser reads the compiler output and reconstructs the control flow. This requires some knowledge about the underlying hardware, e.g., which instructions represent branches or calls. The reconstructed control flow is annotated with the information needed by subsequent analyses and then translated into CRL (Control Flow Representation Language, a human-readable intermediate format designed to simplify analyses and optimizations at the executable/assembly level). This annotated control flow graph serves as the input for microarchitecture analyses.
Value analysis
The value analysis determines ranges for values in registers and by this it can resolve indirect accesses to memory.
Cache analysis
The cache analysis classifies the accesses to main memory, i.e. whether or not the needed data resides in the cache. The categorization of memory references and memory blocks is described in the table below.
| Category | Abbr. | Meaning |
|---|---|---|
| always hit | ah |
The memory reference always results in a cache hit. |
| always miss | am |
The memory reference always results in a cache miss. |
| persistent | ps |
The referenced memory block is loaded once at most. |
| unreachable | un |
The code cannot be reached. |
| not classified | nc |
The memory reference couldn’t be classified as
ah,
am,
ps, or
un. |
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 a loop 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 (virtual inlining, virtual unrolling) approach. Memory references are now considered in different execution contexts, essentially nestings of first and non-first iterations of loops.
