More Web Proxy on the site http://driver.im/

Article

Free access

Phase coupling and constant generation in an optimizing microcode compiler

Author:

Steven R. VegdahlAuthors Info & Claims

MICRO 15: Proceedings of the 15th annual workshop on Microprogramming

Pages 125 - 133

Published: 05 October 1982 Publication History

Abstract

The designer of an optimizing compiler must concern himself with the order in which optimization phases are performed; a pair of phases may be interdependent in the sense that each phase could benefit from information produced by the other. In a compiler for a horizontal target architecture, one such phase-ordering problem occurs between code-generation and compaction. Presented here is an overview of a research effort at Carnegie-Mellon University which has examined solutions to this problem. One aspect of the code generation problem-that of generating constants “intelligently”-is discussed in detail. A technique, called constant-unfolding, is described that can be used to produce code sequences that generate constants in “unusual” ways during execution; such code sequences can lead to more compact code when the literal field of the microinstruction is a “bottleneck”.

References

[1]

Agerwala, T. Microprogram Optimization: A Survey. IEEE Transactions on Computers C-25(10):962-973, October, 1976.

[2]

Banerjee, U., Shen, S., Kuck, D. J. and Towle, R.A. Time and Parallel Processor Bounds for Fortran-Like Loops. IEEE Transactions on Computers C-28(9):660-670, September, 1979.

[3]

Cattell, R. G. G. Formalization and Automatic Derivation of Code Generators. PhD thesis, Carnegie-Mellon University, April, 1978.

Digital Library

[4]

DeWitt, D. J. A Machine Independent Approach to the Production of Optimized Horizontal Microcode. PhD thesis, University of Michigan, June, 1976.

Digital Library

[5]

Erman, L. D. and Lesser, V. R. The Hearsay-II System: A Tutorial. In Lea, W. A. (editor), Trends in Speech Recognition, chapter 16. Prentice-Hall, Englewood Cliffs, NJ, 1978.

[6]

Fisher, J. A. The Optimization of Horizontal Microcode Within and Beyond Basic Blocks: An Application of Processor Scheduling with Resources. PhD thesis, New York University, October, 1979.

Digital Library

[7]

Fisher, J. A., Landskov, D. and Shriver, B. D. Microcode Compaction: Looking Backward and Forward. In Proc. 1981 National Computer Conference, pages 95-102. AFIPS, 1981.

Digital Library

[8]

Fuller, S. H., Almes, G. T., Broadley, W. H., Forgy, C. L., Karlton, P. L., Lesser, V. R. and Teter, J. R. PDP-11/40E Microprogramming Reference Manual. Technical Report, Carnegie-Mellon University, January, 1976.

[9]

Landskov, D., Davidson, S., Shriver, B. and Mallett, P. W. Local Microcode Compaction Techniques. ACM Computing Surveys 12(3):261-294, September, 1980.

Digital Library

[10]

Leverett, B. W., Cattell, R. G. G., Hobbs, S. O., Newcomer, J. M., Reiner, A. H., Schatz, B. R. and Wulf, W. A. An Overview of the Production Quality Compiler-compiler Project. Technical Report CMU-CS-79-105, Carnegie-Mellon University, February, 1979.

[11]

Ma, P. Y. and Lewis, T. G. A Portable Efficient Microprogramming System for Emulator Development. Technical Report, Oregon State University, 1979.

[12]

Mallett, P. W. Methods of Compacting Microprograms. PhD thesis, University of Southwestern Louisiana, December, 1978.

Digital Library

[13]

Newell, A. Heuristic Programming: III-structured Problems. In Aronofsky, J. (editor), Progress in Operations Research, III, pages 360-414. Wiley, New York, 1969.

[14]

Nilsson, N. Problem Solving Methods in Artificial Intelligence. McGraw-Hill, 1971.

Digital Library

[15]

Ousterhout, J. K. Cm* Kmap Microprogramming Manual and Debugger Manual Carnegie-Mellon University, 1978.

[16]

Poe, M. D. Heuristics for the Global Optimization of Microprograms. In Proc. 13th Annual Workshop on, Microprogramming, pages 13-22. IEEE, December, 1980.

Digital Library

[17]

Poe, M. D., Goodell, R. and Steely, S. Jr. Issues of the Design of a Low Level Microprogramming Language for Global Microcode Compaction. In Proc. 14th Annual Workshop on Microprogramming, pages 88-94. IEEE, October, 1981.

Digital Library

[18]

Sint, M MIDL - A Microinstruction Description Language. In Proc. 14th Annual Workshop on Microprogramming, pages 95-106. IEEE, October, 1981.

Digital Library

[19]

Wood, W. G. The Computer Aided Design of Microprograms. PhD thesis, University of Edinburgh, November, 1979.

Cited By

Jantz MKulkarni PRabbah RRaghunathan A(2013)Exploiting phase inter-dependencies for faster iterative compiler optimization phase order searchesProceedings of the 2013 International Conference on Compilers, Architectures and Synthesis for Embedded Systems10.5555/2555729.2555736(1-10)Online publication date: 29-Sep-2013
https://dl.acm.org/doi/10.5555/2555729.2555736
Jantz MKulkarni PKathail VTatge RBarua R(2010)Eliminating false phase interactions to reduce optimization phase order search spaceProceedings of the 2010 international conference on Compilers, architectures and synthesis for embedded systems10.1145/1878921.1878950(187-196)Online publication date: 24-Oct-2010
https://dl.acm.org/doi/10.1145/1878921.1878950
Kulkarni PJantz MWhalley D(2010)Improving both the performance benefits and speed of optimization phase sequence searchesACM SIGPLAN Notices10.1145/1755951.175590345:4(95-104)Online publication date: 13-Apr-2010
https://dl.acm.org/doi/10.1145/1755951.1755903
Show More Cited By

Index Terms

Phase coupling and constant generation in an optimizing microcode compiler

Recommendations

Phase coupling and constant generation in an optimizing microcode compiler

The designer of an optimizing compiler must concern himself with the order in which optimization phases are performed; a pair of phases may be interdependent in the sense that each phase could benefit from information produced by the other. In a ...
Phase coupling for horizontal microcode generation

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 ...
Phase coupling for horizontal microcode generation
MICRO 20: Proceedings of the 20th annual workshop on Microprogramming

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MICRO 15: Proceedings of the 15th annual workshop on Microprogramming

October 1982

201 pages

ACM SIGMICRO Newsletter Volume 13, Issue 4
Dec. 1982
169 pages
ISSN:1050-916X
DOI:10.1145/1014194
Issue’s Table of Contents

Sponsors

SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing

Publisher

IEEE Press

Publication History

Published: 05 October 1982

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 484 of 2,242 submissions, 22%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
402
Total Downloads

Downloads (Last 12 months)86
Downloads (Last 6 weeks)15

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jantz MKulkarni PRabbah RRaghunathan A(2013)Exploiting phase inter-dependencies for faster iterative compiler optimization phase order searchesProceedings of the 2013 International Conference on Compilers, Architectures and Synthesis for Embedded Systems10.5555/2555729.2555736(1-10)Online publication date: 29-Sep-2013
https://dl.acm.org/doi/10.5555/2555729.2555736
Jantz MKulkarni PKathail VTatge RBarua R(2010)Eliminating false phase interactions to reduce optimization phase order search spaceProceedings of the 2010 international conference on Compilers, architectures and synthesis for embedded systems10.1145/1878921.1878950(187-196)Online publication date: 24-Oct-2010
https://dl.acm.org/doi/10.1145/1878921.1878950
Kulkarni PJantz MWhalley D(2010)Improving both the performance benefits and speed of optimization phase sequence searchesACM SIGPLAN Notices10.1145/1755951.175590345:4(95-104)Online publication date: 13-Apr-2010
https://dl.acm.org/doi/10.1145/1755951.1755903
Kulkarni PJantz MWhalley DLee JChilders B(2010)Improving both the performance benefits and speed of optimization phase sequence searchesProceedings of the ACM SIGPLAN/SIGBED 2010 conference on Languages, compilers, and tools for embedded systems10.1145/1755888.1755903(95-104)Online publication date: 13-Apr-2010
https://dl.acm.org/doi/10.1145/1755888.1755903
Kulkarni PWhalley DTyson G(2007)Evaluating Heuristic Optimization Phase Order Search AlgorithmsProceedings of the International Symposium on Code Generation and Optimization10.1109/CGO.2007.9(157-169)Online publication date: 11-Mar-2007
https://dl.acm.org/doi/10.1109/CGO.2007.9
Kulkarni PWhalley DTyson GDavidson J(2006)In search of near-optimal optimization phase orderingsACM SIGPLAN Notices10.1145/1159974.113466341:7(83-92)Online publication date: 14-Jun-2006
https://dl.acm.org/doi/10.1145/1159974.1134663
Kulkarni PWhalley DTyson GDavidson JIrwin MDe Bosschere K(2006)In search of near-optimal optimization phase orderingsProceedings of the 2006 ACM SIGPLAN/SIGBED conference on Language, compilers, and tool support for embedded systems10.1145/1134650.1134663(83-92)Online publication date: 14-Jun-2006
https://dl.acm.org/doi/10.1145/1134650.1134663
Kulkarni PWhalley DTyson GDavidson J(2006)Exhaustive Optimization Phase Order Space ExplorationProceedings of the International Symposium on Code Generation and Optimization10.1109/CGO.2006.15(306-318)Online publication date: 26-Mar-2006
https://dl.acm.org/doi/10.1109/CGO.2006.15
Hines SKulkarni PWhalley DDavidson JWolf W(2005)Using de-optimization to re-optimize codeProceedings of the 5th ACM international conference on Embedded software10.1145/1086228.1086251(114-123)Online publication date: 18-Sep-2005
https://dl.acm.org/doi/10.1145/1086228.1086251
Kulkarni PHines SHiser JWhalley DDavidson JJones D(2004)Fast searches for effective optimization phase sequencesACM SIGPLAN Notices10.1145/996893.99686339:6(171-182)Online publication date: 9-Jun-2004
https://dl.acm.org/doi/10.1145/996893.996863
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents