Compilers and Timing Analysis

Worst-Case Execution Time Analyser

The development and verification of real-time software requires knowledge of the execution time of the critical software functions. The execution time is often variable, depending on the input data and program state; what is then required is an upper bound on the worst-case execution time (WCET). Measuring execution times from test cases or profiling runs usually underestimates the WCET. In contrast, a static WCET analysis adds up the WCETs of the instructions on all possible execution paths and uses mathematical optimization methods to compute an upper bound on the total WCET — the longest execution path.

The Bound-T WCET analyser uses static analysis of machine code to compute bounds on WCET and stack usage. Bound-T is mainly aimed at the smaller 8- and 16-bit microcontrollers but also supports some 32-bit processors such as the ERC32 (SPARC V7).

The steps in the analysis process include:
  • reading and decoding instructions and symbolic (debugging) information from the executable file,
  • analysing the flow of control to connect the instructions into control-flow graphs and call graphs,
  • analysing the data-flow and computations to find bounds on the number of loop iterations, including some inter-procedural analysis for parameter-dependent loop-bounds,
  • modelling the worst-case execution time of each instruction, including pipeline effects and memory accesses but not (at present) cache effects or bus contention effects,
  • applying the implicit path enumeration technique (IPET) to find an upper bound on the total execution time (WCET) that corresponds to the longest path through the control-flow graph.

For complex loops and other complex but important logical constraints on the control-flow Bound-T provides a flexible assertion language by which the user can specify the execution scenarios to be analysed.

As another application of the data-flow analysis Bound-T can compute an upper bound on the stack usage and show the corresponding "deepest" call-path.

Basic limitations on undecidability of course limit the analysis to programs with a suitable form. There are also pragmatic limitations, for example that the program must not be recursive.

The analysis results are presented in textual and graphical form. Control-flow graphs can be annotated with source-line numbers or disassembled instructions.

Further information is available online.

(c) Artist Consortium, All Rights Reserved - 2006, 2007, 2008, 2009

Réalisation Axome - Création de sites Internet