SMS - Swing Modulo Scheduling in GCC

February 2005

We are pleased to announce that Mostafa Hagog and Ayal Zaks, of IBM Haifa Labs, have contributed Swing Modulo Scheduling (SMS) to GCC 4.0. Their implementation is based on the articles:

• Lifetime--sensitive modulo scheduling in a production environment. IEEE Trans. on Comps., 50(3), March 2001. J. Llosa, A. Gonzalez, E. Ayguade, M. Valero., and J. Eckhardt.
• Josep Llosa,Antonio Gonzalez, Eduard Ayguade, and Mateo Valero. Swing Modulo Scheduling: A Lifetime Sensitive Approach. In Pact96 , pages 80-87, October 1996 (Boston - Massachusetts - USA).

SMS is intended to schedule instructions of loops rather than the traditional scheduler (in GCC) that does not give a special handling for loops. For more information on the theory behind SMS take a look at the 2004 GCC summit proceedings (page 55). This optimization helps in loops where there is a place to run consecutive iterations concurrently but the traditional instruction scheduling is not able to fully utilize the hardware functional units. This optimization is disabled by default because of compile time consumption; -fmodulo-sched activates it. The current implementation of SMS is preliminary and is not effective in the following cases:

• Loops that have stores to memory.
• High register pressure and poor register set.
• Architectures that do not have a BCT (Branch on Count) instructions.
• out-of-order machines; SMS impact is more noticeable on in-order machines (out-of-order machines do this work in hardware).

Improvements to SMS to overcome (but not only) the first three restrictions are expected in the coming releases of GCC.