Loop distribution with multiple exits
Bing Hsieh, Michael Hind, Ron K. Cytron · 1992
We present a loop distribution algorithm that accommodates loops with multiple exits. Our algorithm utilizes and appropriately transforms abstract representations of the program rendering these structures suitable for further program transformations. We present results from implementing this algorithm in the PTRAN system at IBM Research. 1 Introduction The transformation of loop distribution has long been recognized for its role in restructuring programs to increase their concurrency [4, 5, 7, 16] and locality [17, 18]. Unfortunately, loop distribution cannot be counted among the unimodular transformations [6, 20] whose aggregate transformational effects can be summarized by a single transformation. Thus, loop distribution must be performed separately from the unimodular transformations. To accomplish its transformations, a program restructuring system must develop certain analytical information about a program concerning its control and data flow properties, typically represented by...