WCET Computation

Reconstruction of the Control Flow from Binary Programs

The starting point of our analysis framework is a binary program and 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 will always result in a cache hit.
always miss	`am`	The memory reference will always result in a cache miss.
persistent	`ps`	The referenced memory block will be loaded at most once.
not classified	`nc`	The memory reference could not be classified as `ah`, `am`, or `ps`.

Next: Pipeline, path and loop analysis | Previous: Timing validation | Contents | Home