Multi-level Loop Fusion with Mimimal Code Size

Loop fusion is one of the most effective and common techniques to increase the performance of programs with multiple loops. The code size of the fused loop after loop fusion legalization might be increased due to the generation of the extra prologue and epilogue. Code size should be considered and minimized for embedded system designs. In this paper, we develop the Select_LF technique, which is to select one of the possible dimensions to legalize loop fusion such that the resultant code size of the fused loop is minimized. We propose a theoretical foundation to determine which dimensions are possible to be retimed to legalize loop fusion for any "J + K" model loop with a J-level outer loop and multiple K-level inner loops. The experimental results show that the execution time of the fused loops by our Select_LF technique is reduced by 55.4% on average compared to the original loops, and the code size of the fused loops is reduced by 7.8% on average compared to the previously reported Max_LF algorithm.