Optimal register assignment to loops for embedded code generation

ABSTRACT

One of the challenging tasks in code generation for embedded systems is register assignment. When more live variables than registers exist, some variables will necessarily be accessed from data memory. Because loops are typically executed many times and are often time-critical, good register assignment in loops is exceedingly important as accessing data memory can degrade performance. The issue of finding an optimal register assignment to loops has been open for some time. In this article, we present a technique for optimal (i.e., spill minimizing) register assignment to loops. First we present a technique for register assignment to architecture styles that are characterized by a consolidated register file. Then we extend the technique to include architecture styles that are characterized by distributed memories and/or a combination of general- and special-purpose registers. Experimental results demonstrate that although the optimal algorithm may be computationally prohibitive, heuristic versions obtain results with performance better than that of an existing graph coloring approach.

REFERENCES

• 1: AHMED, I. AND CHEN, C. Y.R. 1991. Post-processor for datapath synthesis using multiport memories. In Proceedings of the ACM/IEEE International Conference on CAD. (San Jose, CA, Nov.) 276-279.
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: BALAKRISHNAN, M., ET AL. 1988. Allocation of multiport memories in data path synthesis. IEEE Trans. Comput.-Aided Des., 7, 4 (April), 536-540.
• 4: Preston Briggs, Register allocation via graph coloring, Rice University, Houston, TX, 1992
• 5: 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
• 6: CHAITIN, G., AUSLANDER, M., CHANDRA, A., COOCKE, J., HOPKINS, M., AND MARKSTEIN, P. 1981. Register allocation via coloring. Comput. Lang. 6 (Jan.), 47-57.
• 7: 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]
• 8: H. Feuerhahn, A data-flow driven resource allocation in a retargetable microcode compiler, Proceedings of the 21st annual workshop on Microprogramming and microarchitecture, p.105-107, November 28-December 02, 1988, San Diego, California, United States
• 9: Torbjörn Granlund , Richard Kenner, Eliminating branches using a superoptimizer and the GNU C compiler, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.341-352, June 15-19, 1992, San Francisco, California, United States
• 10: 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
• 11: 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]
• 12: 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]
• 13: KENNEDY, K. 1972. Index register allocation in straight line code and simple loops. In Design and Optimization of Compilers, R. Rustin, Ed. Prentice-Hall, Englewood Cliffs, NJ, 51-63.
• 14: 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]
• 15: 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]
• 16: 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
• 17: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang, Instruction selection using binate covering for code size optimization, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.393-399, November 05-09, 1995, San Jose, California, United States
• 18: 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
• 19: F. Luccio, A comment on index register allocation, Communications of the ACM, v.10 n.9, p.572-574, Sept. 1967 [doi>10.1145/363566.363694]
• 20: Peter Marwedel, The mimola design system: Tools for the design of digital processors, Proceedings of the 21st conference on Design automation, p.587-593, June 25-27, 1984, Albuquerque, New Mexico, United States
• 21: 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
• 22: Peter Marwedel , Gert Goossens, Code Generation for Embedded Processors, Kluwer Academic Publishers, Norwell, MA, 1995
• 23: PARK, C., KIM, T., AND LIU, C. L. 1993. Register allocation for data flow graphs with conditional branches and loops. In Proceedings of European Design Automation Conference (Euro-DAC). (Hamburg, Germany) 232-237.
• 24: PAULIN, P. G. AND KNIGHT, J.P. 1989. Force-directed scheduling for the behavioral synthesis of ASICs. IEEE Trans. Comput.-Aided Des. Integrated Circuits Syst. 8, 6 (June).
• 25: STALLMAN, R.M. 1992. Using and Porting GNU CC. Free Software Foundation.
• 26: L. Stok, Interconnect optimisation during data path allocation, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
• 27: M. Strik , J. van Meerbergen , A. Timmer , J. Jess , S. Note, Efficient code generation for in-house DSP-cores, Proceedings of the 1995 European conference on Design and Test, p.244, March 06-09, 1995
• 28: 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:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

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

General Terms:
Algorithms, Languages

Keywords:
code generation, embedded systems, system design