Loop Rolling for Code Size Reduction

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Code size is critical for resource-constrained devices, where memory and storage are limited. Compilers, therefore, should offer optimizations aimed at code reduction. One such optimization is loop rerolling, which transforms a partially unrolled loop into a fully rolled one. However, existing techniques are limited and rarely applicable to real-world programs. They are incapable of handling partial rerolling or straight-line code. In this paper, we propose RoLAG, a novel code-size optimization that creates loops out of straight-line code. It identifies isomorphic code by aligning SSA graphs in a bottom-up fashion. The aligned code is later rolled into a loop. In addition, we propose several optimizations that increase the amount of aligned code by identifying specific patterns of code. Finally, an analysis is used to estimate the profitability of the rolled loop before deciding which version should be kept in the code.Our evaluation of RoLAG on full programs from MiBench and SPEC 2017 show absolute reductions of up to 88 KB while LLVM’s technique is hardly distinguishable from the baseline with no rerolling. Finally, our results show that RoLAG is highly applicable to real-world code extracted from popular GitHub repositories. RoLAG is triggered several orders of magnitude more often than LLVM’s rerolling, resulting in meaningful reductions on real-world functions.
Original languageEnglish
Title of host publication2022 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)
EditorsJae W. Lee, Sebastian Hack, Tatiana Shpeisman
Number of pages13
ISBN (Electronic)978-1-6654-0584-3
ISBN (Print)978-1-6654-0585-0
Publication statusPublished - 29 Mar 2022
Event2022 International Symposium on Code Generation and Optimization - Virtual Conference
Duration: 2 Apr 20226 Apr 2022


Conference2022 International Symposium on Code Generation and Optimization
Abbreviated titleCGO 2022
Internet address


  • Code-Size Reduction
  • Loop Optimization
  • Loop Rerolling
  • LLVM
  • Compiler Optimization


Dive into the research topics of 'Loop Rolling for Code Size Reduction'. Together they form a unique fingerprint.

Cite this