Loop Fusion via Retiming for DSP Applications

For DSP applications with multiple sequential loops or nested loops, loop fusion usually can be applied to increase the instruction-level parallelism. Loop fusion, however, is not always applicable because of the existence of fusion-prevention dependencies among loops. In this paper, we present an efficient loop fusion technique based on loop dependency graph model, retiming, and multi-dimensional retiming concepts. We show that any 1-level loop and 2-level nested loop can be legally fused by performing our legalizing fusion technique. Polynomial-time algorithms are developed to solve the loop fusion problem for both 1-level and 2-level loops. The experimental results show that our loop fusion technique always significantly reduces the schedule length.