Optimized Constant Execution Time Code

Abstract

Single-path code aims to make WCET analysis easier by eliminating data-dependent control flow. To completely negate the need for WCET analysis, single-path code must also eliminate execution-time variability from memory accesses. To be practically useful, single-path code must be optimized to be competitive with traditional WCET-analyzed code. This paper summarizes the work in Emad Jacob Maroun's PhD dissertation titled”Compiling for Time-Predictability and Performance“. Memory access compensation ensures that singlepath code exhibits constant execution time. The generated code is optimized using an improved transformation that uses generic allocators for general-purpose and predicate registers. The repetition dominance relation is used to reduce unnecessary code execution. Lastly, a heuristic list scheduler enables single-path code to utilize the second issue slot of a dual-issue processor. In addition to achieving constant execution times on a timepredictable processor, the results show varying but significant improvements of up to 145 % in performance and a reduced code size of up to 28 %. Compared to WCET-analyzed traditional code, single-path code is mostly competitive while outright superior in several cases. However, pathological cases of poor performance are still observed.