In this article, the problem of finding a tight estimate on the worst-case execution time (WCET) of a real-time program is addressed. The analysis is focused on straight-line code (i.e. code without loops and recursive function calls) which is quite common

estimated, because this would invalidate subsequent analysis (e.g. schedulability analysis) that are using theestimated WCET values. On the other hand, over-estimation leads to under-utilisation of the hardware, be-cause then the run-time processor load of the system will be much less than predicted.

In the area of embedded real-time systems design, code is often generated by design tools (e.g. [17], [18],

[25], [34]) from high-level specifications, based on e.g. differential equations [35], software-circuits [12],statecharts [13] or petri-nets [20]. The structure of the code is simple: it typically contains no loops, no pro-cedure calls and only static variables (according to C-semantics). Thus, the WCET analysis of this kind ofsynthesised controller code can be done significantly faster and more accurate than in the general case,where nested loops and recursive function calls may occur. This fact is exploited by theProgram Timing An-alyserPTA, which is presented in this article.

Typically, WCET analysis can be divided into High-Level Analysis (HLA) and Low-Level Analysis (LLA).The HLA examines the program at the source code level. It has mainly to deal with functional dependenciesbetween various program parts, which have to be incorporated when searching for the longest executablepath in the control flow. The LLA explores the object code of the program in order to find the precise executiontimes of sequences of machine instructions. Hence the atomic unit for the HLA is thebasic block, i.e. a se-quence of statements that are always executed together (cf. Section 2.3), while the atomic unit for the LLAis a machine instruction. This means that LLA has deep knowledge about the timing behaviour of the targetprocessor but is not aware of the global control flow and data dependencies of the program. In contrast, theHLA has knowledge about the program structure but no knowledge about the underlying hardware, thusHLA and LLA complement each other.

Consequently, accurate WCET analysis must comprise both low level analysis (i.e. caching and pipelininganalysis) and high level analysis (i.e. longest executable path searchLEPS). On one hand, the three aspectsLEPS, caching and pipelining cannot be handled independently: The pipeline performance depends onwhether an instruction and its operands are in the cache or not. Additionally, the LEPS needs exact worst-case execution times for each basic block (i.e. each node of the control flow graph) of the program. On theother hand, these parts should be only loosely coupled for two reasons: First, modularisation helps managingthe complexity of the analysis problem. Second it makes analysis more flexible, e.g. wrt. to changes of theunderlying hardware.

As presented in this article, PTA covers all relevant issues in the context of analysing straight-line code.These are:

Caching: In the past years processor speed has increased more rapidly than the speed of memorychips. As a consequence, processors are often stalled waiting for memory accesses. In order to avoidthis,caching is introduced: A small amount of recently accessed data is stored (cached) directly in theprocessor. This data can be accessed much faster than the main memory (typically by a factor of 10 to100). Blocks of data are moved from main memory to the cache and back as they are needed (cf. Section

2.1).

The dif culty for the WCET analysis is to predict whether a certain memory access will be cached atrun-time (i.e. acache hit) or not (i.e. acache miss). Since accesses to main memory are much slowerthan accesses to the cache, it is important to predict the number of cache misses as tight as possible.Pessimistically assuming that every memory access will result in a cache miss is not appropriate, be-cause this leads to extreme overestimation of the WCET.

The cache analysis in PTA exploits data ow analysis principles that are commonly used in compilerconstruction [1]. In the general case, loops in the control ow graph of a program increase the complex-ity of the data ow analysis. However, since PTA deals with simple programs that consist only ofnested if-then-else constructs, the basic blocks of the program can be processed in topological order.Thus the timing information for each basic block can be collected by inspecting each assembler instruc-tion only once.

– 2 –