General loop fusion technique with improved timing performance and minimal code size

For embedded systems with multiple functional units, loop fusion is one of the most effective techniques to increase the performance of applications with multiple loops. But loop fusion is not always applicable because of fusion-preventing dependences among loops. In this paper, we propose loop-transformation techniques to remove fusion-preventing dependences so that loop fusion can be applied and the code size of the fused loops is minimized. We first propose a general legalizing loop-fusion technique, the ULF IP technique, to legalize loop fusion for multi-level nested loops with fusion-preventing dependences. We also propose a technique to produce the final code of the fused loop and calculate the code size. We then propose a theoretical foundation to determine which dimensions are possible to be retimed to legalize loop fusion. Based on the foundation, we propose an improved legalizing fusion technique, the Select LF technique, to select the best dimension to legalize loop fusion so that the code size of the fused loops is minimized. 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 by our Select LF technique achieve the minimal code size.