Accelerating WCETdriven optimizations by the invariant path paradigm - a case study of loop unswitching

The worst-case execution time (WCET) being the upper bound of the maximum execution time corresponds to the longest path through the program’s control flow graph. Its reduction is the objective of a WCET optimization. Un-like average-case execution time compiler optimizations which consider a static (most frequently executed) path, the longest path is variable since its optimization might result in another path becoming the effective longest path. To keep path information valid, WCET optimizations typ-ically perform a time-consuming static WCET analysis af-ter each code modification to ensure that subsequent op-timization steps operate on the critical path. However, a code modification does not always lead to a path switch, making many WCET analyses superfluous. To cope with this problem, we propose a new paradigm called Invariant Path which eliminates the pessimism by indicating whether a path update is mandatory. To demonstrate the paradigm’s practical use, we developed a novel optimization called WCET-driven Loop Unswitching which exploits the Invari-ant Path information. In a case study, our optimization re-duced the WCET of real-world benchmarks by up to 18.3%, while exploiting the Invariant Path paradigm led to a reduc-tion of the optimization time by 57.5 % on average. 1