Post-compaction register assignment in a retargetable compiler

ABSTRACT

We discuss graph-coloring register assignment in a retargetable compiler for Long-Instruction-Word architectures. Of specific concern is when, during the compilation process, should register assignment be performed. We conclude that, for best results, register assignment should follow compaction. We discuss methods of circumventing the implementation problems inherent in such late register assignment.

REFERENCES

• All86: Vicki Hurst Allan, A critical analysis of the global optimization problem for horizontal microcode (phase-coupled, compaction, code motion, compilation), 1986
• All88: V. H. Allan, Data dependency graph bracing, Proceedings of the 21st annual workshop on Microprogramming and microarchitecture, p.91-93, November 28-December 02, 1988, San Diego, California, United States
• ASU86: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• Ban88: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• BC86: Michael Burke , Ron Cytron, Interprocedural dependence analysis and parallelization, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.162-175, June 25-27, 1986, Palo Alto, California, United States
• BDM+88: S.J. Beaty, M.R. Duda., R.A. Mueller, P.H. Sweany, and J. Varghese. "Optimization issues for a retargetable optimizing microcode compiler". IEEE MicroArch, 3(1), December 1988.
• BSKT79: U. Banerjee, S. Shen, D.J. Kuck, and R.A. Towle. "Time and parallel processor bounds for fortra.n-like loops". IEEE Transactions on Computers, C-28(9):660- 670, Sep 1979.
• CAC+81: G.J. Chaitin, M.A. Auslander, A.K. Chandra, J. Cocke, M.E. Hopkins, and P.W. Markstein. "Register allocation via coloring". Computer Languages, 6, 1981.
• Cha82: 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
• Das84: Subrata Dasgupta, A model of clocked micro-architectures for firmware engineering and design automation applications, Proceedings of the 17th annual workshop on Microprogramming, p.298-308, December 1984
• DDMS86: W. Damm, G. Doehmen, K. Merkel, and M. Sichelschmidt. "The AADL/S* Approach to Firmware Design Specification". IEEE Software, 3(4):27-37, July 1986.
• Ell85: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• Hec77: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• HS80: Ellis Horowitz , Sartaj Sahni, Fundamentals of Computer Alori, W. H. Freeman & Co., New York, NY, 1978
• LDSM80: David Landskov , Scott Davidson , Bruce Shriver , Patrick W. Mallett, Local Microcode Compaction Techniques, ACM Computing Surveys (CSUR), v.12 n.3, p.261-294, Sept. 1980 [doi>10.1145/356819.356822]
• MDSW88: R. A. Mueller , M. R. Duda , P. H. Sweany , J. S. Walicki, Horizon: A Retargetable Compiler for Horizontal Microarchitectures, IEEE Transactions on Software Engineering, v.14 n.5, p.575-583, May 1988 [doi>10.1109/32.6135]
• MS86: R.A. Mueller and P.H. Sweany. "Horizon Code Generator Series-Parallel DDG Coupler/Decoupler (Version 3.1)". Technical Report MAD-86-10, Firmware Engineering and MicroArchitecture Design Laboratory, Colorado State University, Fort Collins, CO, September 1986.
• Nic84: Alexandru Nicolau, Parallelism, memory anti-aliasing and correctness for trace scheduling compilers (disambiguation, flow-analysis, compaction), 1984
• PKL80: D.A. Padua, D.J. Kuck, and D.H. Lawrie. "High Speed Multiprocessors and Compilation Techniques". IEEE Transactions on Computers, C-29(9):763-776, Sept 1980.
• PW86: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• Rob79: E.L. Robertson. "Microcode Bit Optimization is NP-complete". IEEE Transactions on Computers, C-28(4):316-319, April 1979.
• Set75: R. Sethi. "Complete register allocation problems". SIAM Journal of Computing, 4(3):226-248, 1975.
• Veg82: Steven Roger Vegdahl, Local code generation and compaction in optimizing microcode compilers, 1982