Overview on Static Timing Analysis

Nowadays, two different approaches are used to estimate WCET bounds. The first approach is measurement-based WCET analysis. Here, the program under analysis is executed or simulated using some representative set of input values. To the measured execution times, a safety margin of e.g. 20% is added and the resulting value is considered the WCET. However, this approach is highly unsafe since no guarantee can be deduced that the inputs used during measurement really lead to the worst-case behavior of the program.

For this reason, static program analyses are used for WCET estimation if safe guarantees for hard real-time systems are required. The leading WCET analysis software is aiT from AbsInt. The overall workflow of aiT is depicted in the following figure.

aiT needs to be provided with a binary executable of the program to be analyzed as well as with a specification file. To estimate the WCET of the binary executable, several analysis steps are taken:

• The decoder exec2crl reads the executable and reconstructs its control flow graph (CFG). This control flow graph is translated into aiT's intermediate format CRL2. CRL2 is used as exchange format storing the application under analysis as well as analysis results generated by the individual substeps of aiT.
• Value analysis determines potential values in the processor registers for any possible program point. These values are frequently used within aiT. Cache analysis requires predicted values to identify possible addresses of memory accesses. In addition, the predicted values are used to determine infeasible paths resulting from conditions being true or false at any point of the analyzed program. Finally, tight value ranges are required to determine loop bounds. Since a program spends most of its execution time in loops, the iteration counts play an important role for WCET estimation. aiT relies on precise bounds to be able to perform a WCET analysis at all.
• The detection of loop bounds during loop bound analysis succeeds only for simple loops and demands their external annotation outside aiT.
• Cache analysis of aiT statically analyzes the cache behavior of a program using a formal cache model. Accesses to main memory are examined by an algorithm distinguishing between sure cache hits and unclassified accesses. A proper cache analysis relies on the value ranges of processor registers obtained from the value analysis.
• Pipeline analysis models the processor's pipeline behavior and is based on the current state of the pipeline, the resources in use, the contents of prefetch queues and the results obtained during cache analysis. It aims at finding a WCET estimate for each basic block of a program. Each basic block is analyzed by taking possible pipeline states from preceding basic blocks into account. After processing each instruction of the currently analyzed block, the longest time this block takes to execute is computed.
• Using the data provided by the previous analysis steps, path analysis computes a program's global WCET. A path within the control flow graph is a sequence of successive basic blocks starting at the entry point of a program and ending at its end point. For each block on a path, its maximum execution time T can be expressed based on the previous analyses. Using the loop bound information, a block's maximum number of executions C can be determined. The WCET of a path can be expressed as the sum of the products T * C over all edges of a path. A program's global WCET is determined by finding the maximum path WCET for all feasible paths. This maximization problem is expressed and solved using integer linear programming.