Bitwidth aware global register allocation

ABSTRACT

Multimedia and network processing applications make extensive use of subword data. Since registers are capable of holding a full data word, when a subword variable is assigned a register, only part of the register is used. New embedded processors have started supporting instruction sets that allow direct referencing of bit sections within registers and therefore multiple subword variables can be made to simultaneously reside in the same register without hindering accesses to these variables. However, a new register allocation algorithm is needed that is aware of the bitwidths of program variables and is capable of packing multiple subword variables into a single register. This paper presents one such algorithm.The algorithm we propose has two key steps. First, a combination of forward and backward data flow analyses are developed to determine the bitwidths of program variables throughout the program. This analysis is required because the declared bitwidths of variables are often larger than their true bitwidths and moreover the minimal bitwidths of a program variable can vary from one program point to another. Second, a novel interference graph representation is designed to enable support for a fast and highly accurate algorithm for packing of subword variables into a single register. Packing is carried out by a node coalescing phase that precedes the conventional graph coloring phase of register allocation. In contrast to traditional node coalescing, packing coalesces a set of interfering nodes. Our experiments show that our bitwidth aware register allocation algorithm reduces the register requirements by 10\% to 50% over a traditional register allocation algorithm that assigns separate registers to simultaneously live subword variables.

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: Mihai Budiu , Majd Sakr , Kip Walker , Seth Copen Goldstein, BitValue Inference: Detecting and Exploiting Narrow Bitwidth Computations, Proceedings from the 6th International Euro-Par Conference on Parallel Processing, p.969-979, August 29-September 01, 2000
• 3: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 4: Jack W. Davidson , Sanjay Jinturkar, Memory access coalescing: a technique for eliminating redundant memory accesses, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.186-195, June 20-24, 1994, Orlando, Florida, United States
• 5: Randall J. Fisher , Henry G. Dietz, Compiling for SIMD Within a Register, Proceedings of the 11th International Workshop on Languages and Compilers for Parallel Computing, p.290-304, August 07-09, 1998
• 6: J. Fridman, "Data Alignment for Sub-Word Parallelism in DSP," IEEE Workshop on Signal Processing Systems (SiPS), pages 251--260, 1999.
• 7: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 8: 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]
• 9: Rajiv Gupta , Eduard Mehofer , Youtao Zhang, A Representation for Bit Section Based Analysis and Optimization, Proceedings of the 11th International Conference on Compiler Construction, p.62-77, April 08-12, 2002
• 10: Akira Koseki , Hideaki Komatsu , Toshio Nakatani, Preference-directed graph coloring, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 11: Samuel Larsen , Saman Amarasinghe, Exploiting superword level parallelism with multimedia instruction sets, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.145-156, June 18-21, 2000, Vancouver, British Columbia, Canada
• 12: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 13: Bengu Li , Rajiv Gupta, Bit section instruction set extension of ARM for embedded applications, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France [doi>10.1145/581630.581642]
• 14: Gokhan Memik , William H. Mangione-Smith , Wendong Hu, NetBench: a benchmarking suite for network processors, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 15: X. Nie, L. Gazsi, F. Engel, and G. Fettweis, "A New Network Processor Architecture for High Speed Communications," IEEE Workshop on Signal Processing Systems (SiPS), pages 548--557, 1999.
• 16: David Seal, ARM Architecture Reference Manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 17: Mark Stephenson , Jonathan Babb , Saman Amarasinghe, Bidwidth analysis with application to silicon compilation, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.108-120, June 18-21, 2000, Vancouver, British Columbia, Canada
• 18: Jens Wagner , Rainer Leupers, C Compiler Design for an Industrial Network Processor, Proceedings of the ACM SIGPLAN workshop on Languages, compilers and tools for embedded systems, p.155-164, August 2001, Snow Bird, Utah, United States
• 19: T. Wolf and M. Franklin, "Commbench - a telecommunications benchmark for network processors," IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), April 2000.
• 20: Youtao Zhang , Rajiv Gupta, Data Compression Transformations for Dynamically Allocated Data Structures, Proceedings of the 11th International Conference on Compiler Construction, p.14-28, April 08-12, 2002

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.0 General

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

General Terms:
Algorithms, Measurement, Performance

Keywords:
embedded applications, minimal bitwidth, packing interfering nodes, subword data