Trace scheduling optimization in a retargetable microcode compiler

ABSTRACT

We discuss the integration of a trace scheduling optimizer into a retargetable optimizing microcode compiler that handles complex timing relations. The trace scheduler requires no special treatment when retargeting the compiler, being constructed from machine independent algorithms that extract target micro-architecture details from a machine description used by the other compiler processes. We focus on the machine independent basis of the trace scheduler and demonstrate it on a hypothetical micro-architecture.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Vicki Hurst Allan, A critical analysis of the global optimization problem for horizontal microcode (phase-coupled, compaction, code motion, compilation), 1986
• 3: 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]
• 4: T. Baba and H. Hagiwara. The MPG System: A Machine-Independent Efficient Microprogram Generator. IEEE Transactions on Computers, C- 30(6):373-395, June 1981.
• 5: Pin Chen. Software Pipeline: A Code Optimization Technique to Improve the Eficiency of Array Processors. Master's thesis, Institute of North-Western Telecommunication Engineering, China, 1984.
• 6: Werner Damm, An axiomatization of low-level parallelism in microarchitectures, Proceedings of the 17th annual workshop on Microprogramming, p.314-323, December 1984
• 7: W. Damm. Automatic Generation of Simulation Tools: A Case Study in the Design of a Retargetable Firmware Development System. In Advances in Microprocessing and Microprogramming, North- Holland, Amsterdam, Holland, 1984.
• 8: 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.
• 9: 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
• 10: Subrata Dasgupta, Towards a microprogramming language schema, Proceedings of the 11th annual workshop on Microprogramming, p.144-153, November 19-22, 1978, Pacific Grove, California, United States
• 11: S. Dasgupta, P.A. Wilsey, and J. Heinanen. Axiomatic specifications in firmware development systems. IEEE Software, 3(4):49-58, July 1986.
• 12: S. Davidson. A Survey of High-Level Languages for Microprogramming. In S. Habib and S. Dasgupta, editors, Handbook of Microprogramming and Firmware Engineering, Van Nostrand, New York, NY, 1986. Forthcoming.
• 13: Scott Davidson, Design and construction of a virtual machine resource binding language, 1980
• 14: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• 15: J.A. Fisher. Trace Scheduling: A Technique for GIobal Microcode Compaction. IEEE Transactions on Computers, C-30(7):478-490, July 1981.
• 16: Mahadevan Ganapathi, Retargetable code generation and optimization using attribute grammars, 1980
• 17: R.P. Gurd. Experience Developing Microcode Using a High Level Language. In Proceedings of the 16th Microprogramming Workshop (MICRO-16), pages 179-184, Downingtown, PA, Oct 1983.
• 18: S. Isoda, Y. Kobayashi, and T. Ishida. Global Compaction of Horizontal Microprograms Based on the Generalized Data Dependency Graph. IEEE nunsactions on Computers, C-32(10):922-933, October 1983.
• 19: 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]
• 20: J.L. Linn. SRDAG Compaction: A Generalization of Trace Scheduling to Increase the Use of Global Context Information. In Proceedings of the 16th Microprogramming Workshop (MICRO-16), pages 11-22, Downingtown, PA, October 1983.
• 21: Peter Marwedel, A retargetable compiler for a high-level microprogramming language, Proceedings of the 17th annual workshop on Microprogramming, p.267-274, December 1984
• 22: R.A. Mueller and P.H. Sweany. Horizon Code Generator Series-Parallel DDG Coupler/Decoupler (Version 9.1). Technical Report MAD-86-10, Firmware Engineering and Micro-Architecture Design Laboratory, Colorado State University, Fort Collins, CO, September 1986.
• 23: B.L. Plomondon, M.R. Duda, and R.A. Mueller. Horizon Compiler Am29500 FFT Micro-Architecture i. Technical Report MAD-86-16, Firmware Engineering and Micro-Architecture Design Laboratory, Colorado State University, Fort Collins, CO, September 1986.
• 24: 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
• 25: B. Su , S. Ding , J. Xia, URPR—An extension of URCR for software pipelining, Proceedings of the 19th annual workshop on Microprogramming, p.94-103, October 15-17, 1986, New York, New York, United States
• 26: Steven Roger Vegdahl, Local code generation and compaction in optimizing microcode compilers, 1982