Phase coupling for horizontal microcode generation

ABSTRACT

Microcode for mass produced architectures is still predominantly generated by hand. Yet, as speed dictates the vertical migration of commonly executed functions to microcode, the demand for automated code generation increases.Though considerably more complex than phase-decoupled methods, phase-coupled methods for the generation of horizontal microcode have the potential to produce more highly optimized microcode. Results of the retargetable phase-coupled microcode compiler, Horizon, are presented and directions suggested.

REFERENCES

• 1: Vicki Hurst Allan, A critical analysis of the global optimization problem for horizontal microcode (phase-coupled, compaction, code motion, compilation), 1986
• 2: V. H. Allen , R. A. Mueller, Compaction with General Synchronous Timing, IEEE Transactions on Software Engineering, v.14 n.5, p.595-599, May 1988 [doi>10.1109/32.6137]
• 3: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 4: {BSKT79} U. Banerjee, S. Shen, D. J. Kuck, and R. A. Towle. Time and parallel processor bounds for fortran-like loops. <i>IEEE Transactions on Computers</i>, C-28(9):660--670, September 1979.
• 5: {CAC*81} G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke, M. E. Hopkins, and P. W. Markstein. Register allocation via coloring. <i>Computer Languages</i>, 6, 1981.
• 6: {Das77} S. Dasgupta. Parallelism in Loop-Free Microprograms. In B. Gilchrist, editor, <i>Information Processing 77</i>, North-Holland, Amsterdam, Holland, 1977.
• 7: David Johns Dewitt, A machine independent approach to the production of optimized horizontal microcode., 1976
• 8: {DM85} M. R. Duda and R. A. Mueller. <i>&mu;-C Microprogramming Language (Version 3.1) Reference Manual.</i> Technical Report CS-85-11, Department of Computer Science, Colorado State University, Fort Collins, September 1985.
• 9: Joseph Allen Fisher, The optimization of horizontal microcode within and beyond basic blocks: an application of processor scheduling with resources, 1979
• 10: {FLS81} J. A. Fisher, D. Landskov, and B. D. Shriver, Microcode Compaction: Looking Backward and Looking Forward. In <i>Proceedings of the National Computer Conference</i>, pages 95--102, AFIPS Press, Montvale, NJ, July 1981.
• 11: Matthew S. Hecht, Flow Analysis of Computer P-OP, Elsevier Science Inc., New York, NY, 1977
• 12: {IKI83} S. Isoda, Y. Kobayashi, and T. Ishida. Global Compaction of Horizontal Microprograms Based on the Generalized Data Dependency Graph. <i>IEEE Transactions on Computers</i>, C-32(10):922--933, October 1983.
• 13: {KT76} J. Kim and C. J. Tan. <i>Register Assignment Algorithms for Optimizing Compilers - Part II.</i> Technical Report RC 6262, IBM, Computer Sciences Department, IBM T.J. Watson Research Center, Yorktown Heights, NY, October 1976.
• 14: {KT79} J. Kim and C. J. Tan. <i>Register Assignment Algorithms for Optimizing Micro-code Compilers - Part I.</i> Technical Report RC 7639, IBM, Computer Sciences Department, IBM T.J. Watson Research Center, Yorktown Heights, NY, May 1979.
• 15: {LA83} J. Lah and E. Atkin. Tree compaction of Microprograms. In <i>Proceedings of the 16th Microprogramming Workshop (MICRO-16)</i>, pages 22--23, Downingtown, PA, October 1983.
• 16: Bruce Wallace Leverett, Register allocation in optimizing compilers, 1981
• 17: {Lin83} J. L. Linn. SRDAG Compaction: A Generalization of Trace Scheduling to Increase the Use of Global Context Information. In <i>Proceedings of the 16th Microprogramming Workshop (MICRO-16)</i>, pages 11--22, Downingtown, PA, October 1983.
• 18: Steven S. Muchnick , Neil D. Jones, Program Flow Analysis: Theory and Application, Prentice Hall Professional Technical Reference, 1981
• 19: {MV87} R. A. Mueller and J. Varghese. Fundamental Concepts in Microprogramming. In S. Habib and S. Dasgupta, editors, <i>Handbook of Microprogramming and Firmware Engineering</i>, Van Nostrand, New York, NY, 1987. Forthcoming.
• 20: {RT81} J. H. Reif and R. E. Tarjan. Symbolic program analysis in almost linear time. <i>SIAM Journal of Computing</i>, 11(1):81--93, February 1981.
• 21: B. Su , S. Ding, Some experiments in global microcode compaction, Proceedings of the 18th annual workshop on Microprogramming, p.175-180, December 03-06, 1985, Pacific Grove, California, United States
• 22: Bogong Su , Shiyuan Ding , Lan Jin, An improvement of trace scheduling for global microcode compaction, Proceedings of the 17th annual workshop on Microprogramming, p.78-85, December 1984
• 23: {Tan78} C. J. Tan. Code Optimization Techniques for Microcode Compilers. In <i>Proceedings of the National Computer Conference</i>, pages 649--655, AFIPS Press, Montvale, NJ, June 1978.
• 24: Mario Tokoro , Takashi Takizuka , Eiji Tamura , Ichiro Yamaura, A technique of global optimization of microprograms, Proceedings of the 11th annual workshop on Microprogramming, p.41-50, November 19-22, 1978, Pacific Grove, California, United States
• 25: Steven Roger Vegdahl, Local code generation and compaction in optimizing microcode compilers, 1982