Demystifying on-the-fly spill code

ABSTRACT

Modulo scheduling is an effective code generation technique that exploits the parallelism in program loops by overlapping iterations. One drawback of this optimization is that register requirements increase significantly because values across different loop iterations can be live concurrently. One possible solution to reduce register pressure is to insert spill code to release registers. Spill code stores values to memory between the producer and consumer instructions.Spilling heuristics can be divided into two classes: 1) a posteriori approaches (spill code is inserted after scheduling the loop) or 2) on-the-fly approaches (spill code is inserted during loop scheduling). Recent studies have reported obtaining better results for spilling on-the-fly. In this work, we study both approaches and propose two new techniques, one for each approach. Our new algorithms try to address the drawbacks observed in previous proposals. We show that the new algorithms outperform previous techniques and, at the same time, reduce compilation time. We also show that, much to our surprise, a posteriori spilling can be in fact slitghtly more effective than on-the-fly spilling.

REFERENCES

• 1: Vikas Agarwal , M. S. Hrishikesh , Stephen W. Keckler , Doug Burger, Clock rate versus IPC: the end of the road for conventional microarchitectures, Proceedings of the 27th annual international symposium on Computer architecture, p.248-259, June 2000, Vancouver, British Columbia, Canada
• 2: Alex Aletà , Josep M. Codina , Jesús Sánchez , Antonio González, Graph-partitioning based instruction scheduling for clustered processors, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 3: Alex Aletà , Josep M. Codina , F. Jesús Sánchez , Antonio González , David R. Kaeli, Exploiting Pseudo-Schedules to Guide Data Dependence Graph Partitioning, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.281-290, September 22-25, 2002
• 4: Gregory Chaitin, Register allocation and spilling via graph coloring, ACM SIGPLAN Notices, v.39 n.4, April 2004 [doi>10.1145/989393.989403]
• 5: Josep M. Codina , Jesús Sánchez , Antonio González, A Unified Modulo Scheduling and Register Allocation Technique for Clustered Processors, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.175-184, September 08-12, 2001
• 6: James C. Dehnert , Peter Y.-T. Hsu , Joseph P. Bratt, Overlapped loop support in the Cydra 5, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.26-38, April 03-06, 1989, Boston, Massachusetts, United States
• 7: Paolo Faraboschi , Geoffrey Brown , Joseph A. Fisher , Giuseppe Desoli , Fred Homewood, Lx: a technology platform for customizable VLIW embedded processing, Proceedings of the 27th annual international symposium on Computer architecture, p.203-213, June 2000, Vancouver, British Columbia, Canada
• 8: Jose Fridman , Zvi Greenfield, The TigerSHARC DSP Architecture, IEEE Micro, v.20 n.1, p.66-76, January 2000 [doi>10.1109/40.820055]
• 9: P. Glaskowsky. Map1000 unfolds at equator. Microprocessor report, 12(16), December 1998.
• 10: R. Ju, S. Chan, T.-F. Ngai, C. Wu, Y. Lu, and J. Zhang. Open research compiler (orc) 2.0 and tuning performance on itanium. Presented at the 35th International Symposium on Microarchitecture, December 2002.
• 11: Josep Llosa, Swing Modulo Scheduling: A Lifetime-Sensitive Approach, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.80, October 20-23, 1996
• 12: Josep Llosa , Mateo Valero , Eduard Ayguadé, Heuristics for register-constrained software pipelining, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.250-261, December 02-04, 1996, Paris, France
• 13: G. G. Pechanek and S. Vassiliadis. The manarray embedded processor architecture. In Proceedings of the 26th Euromicro Conference: Informatics: inventing the future, September 2000.
• 14: B. R. Rau , M. Lee , P. P. Tirumalai , M. S. Schlansker, Register allocation for software pipelined loops, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.283-299, June 15-19, 1992, San Francisco, California, United States
• 15: B. Ramakrishna Rau, Iterative modulo scheduling: an algorithm for software pipelining loops, Proceedings of the 27th annual international symposium on Microarchitecture, p.63-74, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192731]
• 16: John Ruttenberg , G. R. Gao , A. Stoutchinin , W. Lichtenstein, Software pipelining showdown: optimal vs. heuristic methods in a production compiler, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.1-11, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 17: TexasInstrumentsInc. TMS320C62x/67x CPU and instruction set reference guide, 1998.
• 18: Jian Wang , Andreas Krall , M. Anton Ertl , Christine Eisenbeis, Software pipelining with register allocation and spilling, Proceedings of the 27th annual international symposium on Microarchitecture, p.95-99, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192734]
• 19: Javier Zalamea , Josep Llosa , Eduard Ayguadé , Mateo Valero, Improved spill code generation for software pipelined loops, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.134-144, June 18-21, 2000, Vancouver, British Columbia, Canada
• 20: J. Zalamea, J. Llosa, E. Ayguadé, and M. Valero. Mirs: Modulo scheduling with integrated register spilling. In Proceedings of the 14th workshop on languages and compilers for parallel computing, august 2001.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Languages

Keywords:
modulo scheduling, register allocation, spill code