Challenges Imposed to WCET-Aware Compilers

That path within a program's CFG having the maximal WCET is called the worst-case execution path (WCEP). Hence, the WCET of a program corresponds to the length of its WCEP. In order to minimize WCETs by a WCET-aware compiler, compiler optimizations must exclusively focus on those parts of the program lying on the WCEP. Optimization of parts of the program not lying on the WCEP is ineffective, because this does not shorten the WCEP and thus does not reduce the WCET at all. As a consequence, optimization strategies for WCET minimization must have detailed knowledge about the WCEP.

A static WCET analyzer provides detailed information about a program's WCEP, but the sole knowledge of a WCEP is still insufficient for effective WCET minimization as shown in the following

Example

Consider the following C code snippets representing four functions calling each other:

main()
{
if ( ... )
a();
else
d();

return;
}

a()
{
...
b();
...
}

b()
{
...
c();
...
}

d()
{
...
c();
...
}

The call graph of this code is depicted in the following figure.

n addition to the caller-callee relationship, the above figure also shows the WCETs of each function, given in processor cycles. As can be seen, the longest path through this call graph is main, a, b, c. Since this path is the WCEP, it is highlighted in red in the figure and leads to an overall WCET of 205 cycles.

Now, consider additionally that some WCET-aware optimization decides to optimize function b lying on the WCEP. This optimization reduces b's WCET from 80 cycles down to 40 cycles. The call graph with the resulting WCETs and WCEP after the optimization of b is shown in the next figure.

It can be observed that the resulting WCEP after optimization of b is main, d, c. Additionally, reducing b's WCET by 40 cycles does not lead to a reduction of the overall WCET by 40 cycles. Instead, the WCET according to the novel WCEP now amounts to 195 cycles which corresponds to an overall saving of only 10 cycles due to the optimization of b.

The above example has demonstrated that the WCEP is very unstable during optimization: the WCEP can switch from one path within the CFG to a completely different one due to a decision taken by some optimization.

To sum it up, a WCET-aware compiler is faced with the following challenges, turning the development of WCET-aware optimizations into an even more demanding area of research as compared to traditional compiler optimization:

WCET-aware optimizations must have detailed knowledge about the current WCEP at any point in time during the entire optimization process, and
they must be aware of the fact that the WCEP may switch in the course of an optimization and that they thus have to recompute the WCEP whenever necessary.
Additionally, the decision where along the WCEP to apply an optimization should not exclusively be based on local WCET information for a single code block, since local WCET savings for a single block do not translate into global WCET savings of the same order of magnitude.