HyperLink   Enhanced Modulo Scheduling for Loops with Conditional Branches.
Paper of IMPACT - Cited Greater Than 100 Times
Publication Year:
  Nancy J. Warter, Grant E. Haab, Krishna Subramanian, John W. Bockhaus
  Proceedings of 25th Annual ACM/IEEE Int'l Symposium on Microarchitecture, pp. 170-179, Dec. 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 of If-conversion with Predicated Execution. These three modulo scheduling techniques have been implemented in a prototype compiler. We show that for existing architectures which support one branch per cycle, EMS performs approximately 18% better than Hierarchical Reduction. 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.