Tool Mentor: UPB Hybrid WCET Analysis
Due to its conservative nature, WCET analysis leads to heavy overestimation whereas simulation models can have inaccuracies and cannot guarantee to cover the overall worst case. Thus, some hybrid approaches combine analysis and simulation.
At UPB, hybrid WCET analysis combines static analysis and simulation in order to estimate upper bounds for software execution times according to a set of test cases. For this, the application source code is instrumented and compiled in order to perform static timing analysis on the level of compiler basic blocks (i.e., linear code segments until a final branch instruction).
Relationships
Main Description

Abstraction level

Design/Implementation

Use Case Tasks

·         UC#0001 Specify Timing Budgets

·         UC#0004 Negotiate Time Budgets

Covered aspect

Worst and best seen cases and statistics

Algorithm

Hybrid WCET analysis

Inputs

C-code

Particular constraints on inputs

Not all levels of target code optimization are supported (e.g. loop/function unrolling).

Preparation of input

1.    Marking: Instrumentation of source code (C code) by preprocessor macros for the identification of the control flow (control flow marks).

2.    Segmentation: Target compilation replacing control flow marks by assembler labels for the segmentation of the target binary code to linear control flow segments.

3.    Analysis: Worst case execution time analysis of linear control flow segments (based on the instrumented target binary code).

4.    Annotation: Back annotation of the worst case timing augmented control flow graph to the marked source code.

5.    Simulation: Native host compilation of the annotated source code in order to accumulate worst case segment timing according to the simulated control flow.

Invocation of the algorithm

Each step requires the invocation of a command line tool.

1.    mark

2.    Target C compiler (e.g. powerpc-gcc, arm-gcc)

3.    Target specific analysis tool (e.g. arm2xml, timest …)

4.    tdxml2h

5.    Host C compiler (e.g. gcc)

Outputs

Worst case timing annotated host simulation code. The simulation output is the accumulation of the “seen” worst case execution time according to the simulation input. In conjunction with an RTOS simulation model (e.g. in SystemC) the annotated code can be used to simulate the “seen” worst case task schedule (including worst case response times).

Visualization of results

Together with SystemC simulation signal traces and schedules can be generated in the Value Change Dump (VCD) format. There exist a variety of open source tools to visualize VCD trace files (e.g. GTKwave).