License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.WCET.2023.7
URN: urn:nbn:de:0030-drops-184361
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18436/
Maroun, Emad Jacob ;
Schoeberl, Martin ;
Puschner, Peter
Constant-Loop Dominators for Single-Path Code Optimization
Abstract
Single-path code is a code generation technique specifically designed for real-time systems. It guarantees that programs execute the same instruction sequence regardless of runtime conditions. Single-path code uses loop bounds to ensure all loops iterate a fixed number of times equal to their upper loop bound. When the lower and upper bounds are equal, the loop must iterate the same number of times, which we call a constant loop.
In this paper, we present the constant-loop dominance relation on control-flow graphs. It is a variation of the traditional dominance relation that considers constant loops to find basic blocks that are always executed the same number of times. Using this relation, we present an optimization that reduces the code needed to manage single-path code. Our evaluation shows significant performance improvements, with one example of up to 90%, with mostly minor effects on code size.
BibTeX - Entry
@InProceedings{maroun_et_al:OASIcs.WCET.2023.7,
author = {Maroun, Emad Jacob and Schoeberl, Martin and Puschner, Peter},
title = {{Constant-Loop Dominators for Single-Path Code Optimization}},
booktitle = {21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)},
pages = {7:1--7:13},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-293-8},
ISSN = {2190-6807},
year = {2023},
volume = {114},
editor = {W\"{a}gemann, Peter},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18436},
URN = {urn:nbn:de:0030-drops-184361},
doi = {10.4230/OASIcs.WCET.2023.7},
annote = {Keywords: single-path, dominators, algorithms, optimization, control-flow graph}
}
