Enhanced modulo scheduling for loops with conditional branches
Nancy J. Warter, Grant E. Haab, Krishna Subramanian, John W. Bockhaus · ACM SIGMICRO newsletter/SIGMICRO newsletter/SIGMICRO, TCMICRO newsletter · 1992
Loops with conditional branches have multiple execution paths which are difficult to software pipeline. The modulo scheduling technique for software pipelining addresses this problem by converting loops with conditional branches into straight-line code before scheduling. In this paper we present an Enhanced Modulo Scheduling (EMS) technique that can achieve a lower minimum Initiation Interval than modulo scheduling techniques that rely on either Hierarchical Reduction or If-conversionwith Predicated Execution.These three modulo scheduling techniques have been implemented in a prototype compiler. We show that for existing architectures which support one bmnch per cycle, EMS performs approximately 18% better than Hierarchical Redwction. We also show that If-conversion with Predicated Execution outperforms EMS assuming one branch per cycle. However, with hardware support for multiple branches per cycle, EMS should perform as well as or better than If-conversion with Predicated Execution.