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.

Please send FSF & GNU inquiries & questions to gnu@gnu.org. There are also other ways to contact the FSF.

These pages are maintained by the GCC team.

For questions related to the use of GCC, please consult these web pages and the GCC manuals. If that fails, the gcc-help@gcc.gnu.org mailing list might help.
Please send comments on these web pages and the development of GCC to our developer mailing list at gcc@gnu.org or gcc@gcc.gnu.org. All of our lists have public archives.

Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.

Last modified 2006-06-21