Constant-Loop Dominators for Single-Path Code Optimization

Emad Jacob Maroun, Martin Schoeberl, Peter Puschner

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

32 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationProceedings of the 21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)
Number of pages13
Volume114
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date2023
Article number7
ISBN (Print)978-3-95977-293-8
DOIs
Publication statusPublished - 2023
Event21st International Workshop on Worst-Case Execution Time Analysis - Vienna, Austria
Duration: 11 Jul 202314 Jul 2023

Conference

Conference21st International Workshop on Worst-Case Execution Time Analysis
Country/TerritoryAustria
CityVienna
Period11/07/202314/07/2023

Keywords

  • Single-parh
  • Dominators
  • Algorithms
  • Optimization
  • Control-flow graph

Fingerprint

Dive into the research topics of 'Constant-Loop Dominators for Single-Path Code Optimization'. Together they form a unique fingerprint.

Cite this