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
Go to the corresponding OASIcs Volume Portal

Maroun, Emad Jacob ; Schoeberl, Martin ; Puschner, Peter

Constant-Loop Dominators for Single-Path Code Optimization

OASIcs-WCET-2023-7.pdf (0.6 MB)


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

  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 =		{},
  URN =		{urn:nbn:de:0030-drops-184361},
  doi =		{10.4230/OASIcs.WCET.2023.7},
  annote =	{Keywords: single-path, dominators, algorithms, optimization, control-flow graph}

Keywords: single-path, dominators, algorithms, optimization, control-flow graph
Collection: 21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)
Issue Date: 2023
Date of publication: 26.07.2023
Supplementary Material: Software (Source Code): archived at:

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI