VLIW compilation techniques in a superscalar environment

ABSTRACT

We describe techniques for converting the intermediate code representation of a given program, as generated by a modern compiler, to another representation which produces the same run-time results, but can run faster on a superscalar machine. The algorithms, based on novel parallelization techniques for Very Long Instruction Word (VLIW) architectures, find and place together independently executable operations that may be far apart in the original code. i.e., they may be separated by many conditional branches or belong to different iterations of a loop. As a result, the functional units in the superscalar are presented with more work that can proceed in parallel, thus achieving higher performance than the approach of using hardware instruction dispatch techniques alone.While general scheduling techniques improve performance by removing idle pipeline cycles, to further improve performance on a superscalar with only a few functional units requires a reduction in the pathlength. We have designed a set of new algorithms for reducing pathlength and removing stalls due to branches, namely speculative load-store motion out of loops, unspeculation, limited combining, basic block expansion, and prolog tailoring. These algorithms were implemented in a prototype version of the IBM RS/6000 xlc compiler and have shown significant improvement in SPEC integer benchmarks on the IBM POWER machines.Also, we describe a new technique to obtain profiling information with low overhead, and some applications of profiling directed feedback, including scheduling heuristics, code reordering and branch reversal.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: Thomas Ball , James R. Larus, Optimally profiling and tracing programs, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.59-70, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143180]
• 4: David Bernstein , Michael Rodeh, Global instruction scheduling for superscalar machines, ACM SIGPLAN Notices, v.26 n.6, p.241-255, June 1991
• 5: David Bernstein , Michael Rodeh , Mooly Sagiv, Proving safety of speculative load instructions at compile-time, Symposium proceedings on 4th European symposium on programming, p.56-72, January 1992, Rennes, France
• 6: Pohua P. Chang , Scott A. Mahlke , William Y. Chen , Nancy J. Warter , Wen-mei W. Hwu, IMPACT: an architectural framework for multiple-instruction-issue processors, Proceedings of the 18th annual international symposium on Computer architecture, p.266-275, May 27-30, 1991, Toronto, Ontario, Canada
• 7: Kemal Ebcioğlu, A compilation technique for software pipelining of loops with conditional jumps, Proceedings of the 20th annual workshop on Microprogramming, p.69-79, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255317]
• 8: K. Ebcioglu, "Global Scheduling," section of a book on compiler optimizations, F. Allen, K. Zadeck, B.K. Rosen (eds.), to appear.
• 9: K. Ebcioğlu , Toshio Nakatani, A new compilation technique for parallelizing loops with unpredictable branches on a VLIW architecture, Selected papers of the second workshop on Languages and compilers for parallel computing, p.213-229, May 1990, Urbana, Illinois, United States
• 10: Kemal Ebcioglu , Alexandru Nicolau, A global resource-constrained parallelization technique, Proceedings of the 3rd international conference on Supercomputing, p.154-163, June 05-09, 1989, Crete, Greece [doi>10.1145/318789.318807]
• 11: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• 12: Lawrence Feigen , David Klappholz , Robert Casazza , Xing Xue, The revival transformation, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.421-434, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.178043]
• 13: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 14: M. C. Golumbic , V. Rainish, Instruction scheduling beyond basic blocks, IBM Journal of Research and Development, v.34 n.1, p.93-97, Jan. 1990
• 15: Rajiv Gupta , Mary Lou Soffa, Region Scheduling: An Approach for Detecting and Redistributing Parallelism, IEEE Transactions on Software Engineering, v.16 n.4, p.421-431, April 1990 [doi>10.1109/32.54294]
• 16: Suneel Jain, Circular scheduling: a new technique to perform software pipelining, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.219-228, June 24-28, 1991, Toronto, Ontario, Canada
• 17: M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
• 18: Soo-Mook Moon , Kemal Ebcioğlu, An efficient resource-constrained global scheduling technique for superscalar and VLIW processors, Proceedings of the 25th annual international symposium on Microarchitecture, p.55-71, December 01-04, 1992, Portland, Oregon, United States
• 19: Frank Mueller , David B. Whalley, Avoiding unconditional jumps by code replication, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.322-330, June 15-19, 1992, San Francisco, California, United States
• 20: T. Nakatani , K. Ebcioğlu, “Combining” as a compilation technique for VLIW architectures, Proceedings of the 22nd annual workshop on Microprogramming and microarchitecture, p.43-55, August 14-16, 1989, Dublin, Ireland
• 21: T. Nakatani , K. Ebcioglu, Making Compaction-Based Parallelization Affordable, IEEE Transactions on Parallel and Distributed Systems, v.4 n.9, p.1014-1029, September 1993 [doi>10.1109/71.243528]
• 22: Gabriel M. Silberman , Kemal Ebcioğlu, An architectural framework for migration from CISC to higher performance platforms, Proceedings of the 6th international conference on Supercomputing, p.198-215, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143410]
• 23: M. D. Smith , M. Johnson , M. A. Horowitz, Limits on multiple instruction issue, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.290-302, April 03-06, 1989, Boston, Massachusetts, United States
• 24: G.J. Sussman and G.L. Steele, "Constraints-- A Language for Expressing Almost Hierarchical Descriptions," Artificial intelligence, Vol. 14, pp. 1-39, 1980.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers

          Nouns: IBM RS/6000

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Experimentation, Performance

Keywords:
VLIW, compiler optimizations, global scheduling, profiling directed feedback, software pipelining, superscalars