Loop fusion technique with minimal memory cost via retiming

Embedded systems are usually constrained in terms of timing, power, and memory. Many embedded applications, especially in the multi-media and telecom domains, are inherently data dominant. These embedded DSP applications usually exhibit intensive computations in the form of multi-level loops. The performance of these embedded DSP applications mainly depends on the code quality of the loops and the memory hierarchy design. During the design phase of the embedded system, it is important to estimate the overall storage requirement and to design an optimized memory system and take advantage of the memory system by program transformations and loop transformations. Loop fusion is one of the most effective techniques to increase the performance of applications with multiple loops. In this paper, we propose a technique to estimate the memory cost of the original loop and the fused loop based on the data dependence distance. We then propose loop transformation techniques to legalize loop fusion and at the same time to reduce the overall memory cost. The experimental results show that the execution time of the fused loops by our legalizing fusion technique is significantly reduced compared to the execution time of the original loops, and the fused loops achieve the minimal memory cost.