Code transformations to augment the scope of loop fusion in a production compiler

Loop fusion is a common optimization technique that takes two loops and combines them into a single large loop. Most of the existing loop fusion techniques focus on heuristics to optimize an objective function such as data reuse within the fused loop or parallelizability of the fused loop. Most programs have only a small number of loops that satisfy all of the conditions necessary for loop fusion to occur. This thesis identifies conditions that prevent loop fusion and focuses on code transformations applied to sets of loops to make these conditions satisfiable. It also presents algorithms to fuse loops in the IBM®XL compiler suite that generates code for the IBM family of PowerPC®processors. This compiler uses a heuristic in the loop distributor to ultimately determine which portions of a loop should remain in the same loop nest and which portions should be moved into a different loop nest. Thus, in order for the loop distributor to make the best possible decisions, maximal loop fusion is performed first to make the loop bodies as large as possible. The large loop bodies created by loop fusion can also benefit other loop optimizations which are run after loop fusion and before loop distribution. All of the algorithms have been implemented in the IBM XL compiler framework and tested on an IBM pSeries™ 630 machine equipped with a POWER4™ processor using the SPEC95 and SPEC2000 benchmark suites.