Lecture Notes in Computer Science, 2001, Volume 2150/2001, 207-220, DOI: 10.1007/3-540-44681-8_32

Handling Irreducible Loops: Optimized Node Splitting vs. DJ-Graphs

Sebastian Unger and Frank Mueller

View Related Documents

Abstract

This paper addresses the question of how to handle irreducible regions during optimization, which has become even more relevant for contemporary processors since recent VLIW-like architectures highly rely on instruction scheduling. The contributions of this paper are twofold. First, a method of optimized node splitting to transform irreducible regions of control flow into reducible regions is derived. This method is superior to approaches previously published since it reduces the number of replicated nodes by comparison. Second, three methods that handle regions of irreducible control flow are evaluated with respect to their impact on compiler optimizations: traditional and optimized node splitting as well as loop analysis through DJ graphs. Measurements show improvements of 1–40% for these methods of handling irreducible loop over the unoptimized case.

Fulltext Preview

Image of the first page of the fulltext document