Unroll-based register coalescing

ABSTRACT

Aggressive instruction scheduling leaves behind many renaming copy instructions that cannot be coalesced due to interferences. These copies take resources, and more seriously, they may cause a stall if they are generated for renaming of multi-latency instructions. This paper proposes a code transformation technique based on loop unrolling which makes those copies coalescible. Two unique features of the technique are its method of determining the precise unroll amount based on an idea of extended live range, and its insertion of special bookkeeping copies at loop exits. In fact, the technique provides a more general and simpler solution for the cross-iteration register overwrite problem in software pipelining which works for loops with control flows as well as for straight-line loops. In addition, it is applicable to other optimizations including path length reduction and redundant subscripted reference elimination.Our empirical study performed on a 16-ALU VLIW testbed with a two-cycle load latency shows that 86% of the otherwise uncoalescible copies in innermost loops become coalescible when unrolled 2.2 times on average. In addition, it is demonstrated that the unroll amount obtained is precise and the most efficient. The unrolled version of the VLIW code includes fewer no-op VLIWs caused by stalls, improving the performance by a geometric mean of 18%.

REFERENCES

• 1: Preston Briggs , Keith D. Cooper , Linda Torczon, Improvements to graph coloring register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.428-455, May 1994 [doi>10.1145/177492.177575]
• 2: David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.53-65, June 1990, White Plains, New York, United States
• 3: 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
• 4: Lal George , Andrew W. Appel, Iterated register coalescing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.300-324, May 1996 [doi>10.1145/229542.229546]
• 5: Suhyun Kim , Soo-Mook Moon , Jinpyo Park , HanSaem Yun, Unroll-Based Copy Elimination for Enhanced Pipeline Scheduling, Proceedings of the 12th International Workshop on Languages and Compilers for Parallel Computing, p.85-99, August 04-06, 1999
• 6: 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
• 7: Soo-Mook Moon , Kemal Ebcioğlu, Parallelizing nonnumerical code with selective scheduling and software pipelining, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.6, p.853-898, Nov. 1997 [doi>10.1145/267959.269966]
• 8: Seongbae Park , SangMin Shim , Soo-Mook Moon, Evaluation of scheduling techniques on a SPARC-based VLIW testbed, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.104-113, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 9: B. Ramakrishna Rau, Data Flow and Dependence Analysis for Instruction Level Parallelism, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.236-250, August 07-09, 1991
• 10: B. R. Rau , C. D. Glaeser, Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing, Proceedings of the 14th annual workshop on Microprogramming, p.183-198, December 01-01, 1981, Chatham, Massachusetts, United States

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Design, Languages, Measurement, Performance, Theory, Verification