Optimizing Timing and Code Size Using Maximum Direct Loop Fusion

In this paper, we develop the technique that combines loop distribution with maximum direct loop fusion (LD_MDF), which performs maximum loop distribution, followed by maximum direct loop fusion to optimize timing and code size simultaneously. We illustrate using examples that dependence cycle is not always a restriction for loop distribution for multi-level loops. We map the maximum direct loop fusion problem to the graph partitioning problem. A polynomial graph partitioning algorithm is developed to compute the fusion partitions. We prove that our maximum direct loop fusion algorithm produces the fewest number of resultant loop nests without violating dependence constraints. We also show that the resultant code size of the fused loops by the technique of loop distribution with maximum direct loop fusion is always smaller than the code size of the original loops.