Research WCET-aware Compilation WCET-aware Optimizations Loop Unswitching
As motivated here, WCET-aware optimizations must be aware of WCEP switches in the course of an optimization, and they thus have to recompute the WCEP whenever necessary. In the field of WCET-aware code optimization, this requirement is usually met by pessimistically recomputing the WCEP after each individual code modification. Thus, a time consuming WCET analysis is performed after any code modification. However, this exhaustive WCEP update is not necessary. In most situations, the WCEP provably remains stable during optimization so that many WCEP recomputations can be saved. WCC's concept to model those subpaths of the WCEP that always remain part of the WCEP independent of any code modification is called the invariant path.
Only branches in a program's control flow graph are places where the WCEP can possibly switch (cf. this figure). In usual high-level programming languages, such branches are modeled by if-then- or if-else-statements. The challenge is now to classify each if-then- and if-else-statement as being part of the invariant path or not.
Depending on the conditional expression of an if-then-statement, either the path through the then-part is executed, or the mutually exclusive path bypassing the then-part is taken. For such an if-then-statement, the WCEP either goes along the then-part, or the then-part does not contribute to the WCET. In terms of the invariant path paradigm, a WCEP traversing the then-part is also part of the invariant path since a modification of the code in the then-part can not lead to path switching. This is because the other feasible path of the if-then-statement does not contain any code that might become the new WCEP.
For if-else-statements, a context-sensitive WCET analyzer may determine that the WCEP traverses both the then- and else-part in different execution contexts. In this situation, WCEP switches can not emerge since it is known from static WCET analysis that both parts always contribute to the program's WCET. Thus, such an if-else-statement can entirely be declared as part of the invariant path.
In two possible cases, WCET analysis may detect that one of the two paths through the then- or else-part is infeasible - under all circumstances, the WCEP traverses exactly one of the two mutually exclusive paths. The first case occurs if static WCET analysis is able to compute that the condition of the if-else-statement always evaluates to true or false, respectively. One of the two paths is never executed and is thus dead code. This dead code along an infeasible path can be eliminated and the remaining path is part of the invariant path. The second case occurs if the WCET analyzer is unable to statically analyze the condition of the if-else-statement. In this situation, it conservatively assumes that the longest of both alternative paths is the WCEP which is always taken. This is the only situation where a WCEP path switch can occur. Thus, these types of if-else-statements are not part of the invariant path.
Similar to function inlining and loop unrolling, loop unswitching is a typical ACET optimization where a trade-off between the execution time improvement and the resulting code size increase must be taken into account. If shifts loop-invariant if-then- or if-else-statements out of a loop at the cost of loop body duplications. For this reason, loop unswitching can not be applied exhaustively if strict code size constraints must be met. Rather, potential unswitching candidates should be evaluated beforehand, thus enabling to unswitch only those loops leading to maximal runtime improvement while keeping code size increases minimal. Since the way how loop unswitching is made WCET-aware is very similar to the techniques already used for other WCET-aware optimizations of the WCC compiler and heavily relies on back-annotation of WCET-related data from WCC's back-end into the ICD-C intermediate format, the details of this optimization are omitted here. In contrast to function inlining and loop unrolling, WCET-aware loop unswitching uses the invariant path to avoid superfluous WCEP updates.
An analysis of 42 real-life benchmarks revealed that between 85.4% up to 88.8% of the benchmarks' total WCETs are contributed by pieces of code lying on the invariant path. Thus, only less than 15% of the average benchmarks' WCETs stem from code where WCEP switches may occur.
To show the effectiveness of the invariant path paradigm, the optimization runtimes of WCET-aware loop unswitching were measured for the most interesting of these 42 real-life benchmarks, once with and once without exploiting invariant path information. The 100% line of the above figure corresponds to the optimization time of standard loop unswitching without any WCET heuristics. WCET-aware unswitching without using invariant paths took on average 872% more runtime than standard, WCET-unaware unswitching. Exploiting invariant paths reduces runtimes down to 379% which corresponds to a speed-up by a factor of 2.3.
The next figure above shows the WCET reductions achieved by WCC's loop unswitching. Again, all results are given as a percentage, with 100% corresponding to the WCET of the original benchmark code after dead code elimination. All results are generated assuming an 8 kB I-cache. As can be seen, an average WCET reduction of 10.4% was achieved for all benchmarks. The maximal WCET reduction of 17.3% was achieved for the block benchmark. It contains seven loop-invariant if-then- or if-else-statements executed between 4 and 16 times in the worst case. By unswitching, their execution frequencies could be reduced significantly.