Optimal register assignment to loops for embedded code generation

ABSTRACT

Abstract: One of the challenging tasks in code generation for embedded systems is register assignment. When more live variables than registers exist, some variables are necessarily accessed from data memory. Because loops are typically executed many times and are often time-critical, good register assignment in loops is exceedingly important, since accessing data memory can degrade performance. The issue of finding an optimal register assignment to loops, one which minimizes the number of spills between registers and memory, has been open for some time. In this paper, we address this issue and present an optimal, but exponential, algorithm which assigns registers to loop bodies such that the resulting spill code is minimal. We also show that a heuristic modification performs as well as the exponential approach on typical loops from scientific code.

REFERENCES

• 1: Preston Briggs, Register allocation via graph coloring, Rice University, Houston, TX, 1992
• 2: P. Briggs , K. D. Cooper , K. Kennedy , L. Torczon, Coloring heuristics for register allocation, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.275-284, June 19-23, 1989, Portland, Oregon, United States
• 3: G. Chaitin, M. Auslander, A. Chandra, J. Coocke, M. Hopkins, and P. Markstein. Register Allocation Via Coloring. Computer Languages, 6, January 1981.
• 4: Fred C. Chow , John L. Hennessy, The priority-based coloring approach to register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.4, p.501-536, Oct. 1990 [doi>10.1145/88616.88621]
• 5: M. Balakrishnan et al. Allocation of Multiport Memories in Data Path Synthesis. IEEE Trans. on CAD, 7(4), April 1988.
• 6: Laurie J. Hendren , Guang R. Gao , Erik R. Altman , Chandrika Mukerji, A Register Allocation Framework Based on Hierarchical Cyclic Interval Graphs, Proceedings of the 4th International Conference on Compiler Construction, p.176-191, October 05-07, 1992
• 7: L. P. Horwitz , R. M. Karp , R. E. Miller , S. Winograd, Index Register Allocation, Journal of the ACM (JACM), v.13 n.1, p.43-61, Jan. 1966 [doi>10.1145/321312.321317]
• 8: Wei-Chung Hsu , Charles N. Fisher , James R. Goodman, On the Minimization of Loads/Stores in Local Register Allocation, IEEE Transactions on Software Engineering, v.15 n.10, p.1252-1260, October 1989 [doi>10.1109/TSE.1989.559775]
• 9: K. Kennedy. Index Register Allocation in Straight Line Code and Simple Loops. In 1%. Rustin, editor, Design and Optimization of Compilers. Prentice-Hall, 1972.
• 10: Taewhan Kim , C. L. Liu, Utilization of multiport memories in data path synthesis, Proceedings of the 30th international conference on Design automation, p.298-302, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164900]
• 11: D. J. Kolson, A. Nicolau, and K. Kennedy. An Algorithm for Minimizing Spill Code in Loops. Technical Report 94-43, U.C. Irvine, October 1994. Also available as Rice University Technical Report: CRPC-TR94482.
• 12: F. J. Kurdahi , A. C. Parker, REAL: a program for REgister ALlocation, Proceedings of the 24th ACM/IEEE conference on Design automation, p.210-215, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37920]
• 13: Dirk Lanneer , Marco Cornero , Gert Goossens , Hugo De Man, Data routing: a paradigm for efficient data-path synthesis and code generation, Proceedings of the 7th international symposium on High-level synthesis, p.17-22, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
• 14: Clifford Liem , Trevor May , Pierre Paulin, Register assignment through resource classification for ASIP microcode generation, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.397-402, November 06-10, 1994, San Jose, California, United States
• 15: Peter Marwedel, Tree-based mapping of algorithms to predefined structures, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.586-593, November 07-11, 1993, Santa Clara, California, United States
• 16: C. Park, T. Kim, and C. L. Liu. Register Allocation for Data Flow Graphs with Conditional Branches and Loops. Euro- DAC '93, 1993.
• 17: L. Stok, Interconnect optimisation during data path allocation, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
• 18: Tom Wilson , Gary Grewal , Ben Halley , Dilip Banerji, An integrated approach to retargetable code generation, Proceedings of the 7th international symposium on High-level synthesis, p.70-75, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

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; Code generation

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Experimentation, Languages, Performance

Keywords:
data memory access, embedded code generation, exponential algorithm, heuristic modification, live variables, loops, minimal spill code, optimal register assignment, optimisation, program control structures, real-time systems, scientific code, storage allocation