Code reuse in an optimizing compiler
Abstract
This paper describes how the cmcc compiler reuses code---both internally (reuse between different modules) and externally (reuse between versions for different target machines). The key to reuse are the application frameworks developed for global data-flow analysis, code generation, instruction scheduling, and register allocation.The code produced by cmcc is as good as the code produced by the native compilers for the MIPS and SPARC, although significantly less resources have been spent on cmcc (overall, about 6 man years by 2.5 persons). cmcc is implemented in C++, which allowed for a compact expression of the frameworks as class hierarchies. The results support the claim that suitable frameworks facilitate reuse and thereby significantly improve developer effectiveness.
References
[1]
A. Adl-Tabatabai and T. Gross. Source-level debugging of scalar optimized code. In Proc. ACM SIGPLAN'96 Conf on Prog. Language Design and Implementation, pages 33-43. ACM, May 1996.
[2]
D. Bernstein, D. Q. Goldin, M. C. Golumbic, H. Krawczyk, Y. Mansour, I. Nahshon, and R. Y. Pinter. Spill code minimization techniques for optimizing compilers. In Proc. ACM SIGPLAN '89 Con& on Prog. Language Design and Implementation, pages 258-263. ACM, July 1989.
[3]
P. Briggs. RegisterAllocation via Graph Coloring. PhD thesis, Rice University, April 1992.
[4]
P. Briggs, K. D. Cooper, K. Kennedy, and L. Torczon. Coloring heuristics for register allocation. In Proc. ACM SIGPIAN'89 Conf on Prog. Language Design and Implementation, pages 275-284. ACM, July 1989.
[5]
D. Callahan and B. Koblenz. Register allocation via hierarchical graph coloring. In Proc. ACMSIGPLAN'91 Conf on Prog. Language Design and Implementation, pages 192-203, Toronto, June 1991. ACM.
[6]
G. J. Chaitin. Register allocation and spilling via graph coloring. In Proc. ACM SIGPLAN 1982 Symp. on Compiler Construction, pages 98-105, June 1982. In SIG- PLAN Notices, v. 17, n. 6.
[7]
G. J. Chaitin, M. A. Auslander,A. K. Chandra, J. Cocke, M. E. Hopkins, and P W. Markstein. Register allocation by coloring. Research Report 8395, IBM Watson Research Center, 198 1.
[8]
F. Chow. A Portable, Machine-independent Global Optimizer - Design and Measurements. PhD thesis, Stanford University, 1984.
[9]
F. C. Chow and J. L. Hennessy. A priority-based coloring approach to register allocation. ACM Trans. on Prog. Lang. Syst., 12:501-535, Oct. 1990.
[10]
C. Fraser and D. Hanson. A Retargetable C Compiler: Design and Implementation. Benjamin/Cummings, 1995.
[11]
S. Freudenberger and J. Ruttenberg. Phase ordering of register allocation and instruction scheduling. In R. Giegerich and S. L. Graham, editors, Code Generation - Concepts, Tools, Techniques, pages 146170. Springer Verlag, 1992.
[12]
E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns, Elements of Object-Oriented Sofhyare. Addison Wesley, 1995.
[13]
J. Graver. The evolution of an object-oriented compiler framework. Software: Practice & Experience, 22(7):5 19-535, July 1992.
[14]
H. Huni, R. Johnson, and R. Engel. A framework for networked protocol software. In Proc. OOPSLA'95, pages 358-369. ACM, 1995.
[15]
I. Jacobson, M. Christerson, P. Jonsson, and G. Overgaard. Object-Oriented Sofnyare Engineering. Addison-Wesley, 1992.
[16]
R. Johnson, C. McConnell, and J. Lake. The RTL system: A framework for code optimization. In R. Giegerich and S. L. Graham, editors, Code Generation - Concepts, Tools, Techniques, pages 255-274. Springer Verlag, 1992.
[17]
J. Knoop, 0. Ruthing, and B. Steffen. Lazy code motion. In Proc. ACM SIGPLAN'92 Conf on Prog. Language Design and Implementation, pages 224-234. ACM, June 1992.
[18]
J. Knoop, 0. Ruthing, and B. Steffen. Lazy strength reduction. .I. ofProg. Languages, 1(1):71-91, 1993.
[19]
J. Knoop, 0. Ruthing, and B. Steffen. Optimal code motion: Theory and practice. ACM Trans. on Prog. Lang. Syst., 16(4): 1117-l 155, July 1994.
[20]
J. Knoop, 0. Ruthing, and B. Steffen. Partial dead code elimination. In Proc. ACM SIGPLAN'94 Conf on Prog. Language Design and Implementation, pages 147-158. ACM, June 1994.
[21]
K. Koskimies. Software engineering aspects in language implementation. In Proc. 2nd Intl. Compiler- Compiler and High-Speed Compilation Workshop, Lecture Notes in Computer Science Vol. 371, pages 37-5 1, Berlin, 1989. Springer Verlag.
[22]
B. Lewis, L. Deutsch, and T. Goldstein. Clarity Mcode: A retargetable intermediate representation for compilation. In Proc. ACMBIGPLAN Workshop on Intermediate Representations {IR'95), pages 119-128, San Francisco, Jan 1995. ACM.
[23]
J. Lewis, S. Henry, D. Kafura, and R. Schulman. On the relationship between the object-oriented paradigm and software reuse: An empirical investigation. Journal of Object-Oriented Prog., 5(4):35-41, 1992.
[24]
G. Lueh, T. Gross, and A. Adl-Tabatabai. Global register allocation based on graph fusion. Technical Report 96- 106, Carnegie Mellon University, School of Computer Science, March 1996.
[25]
E. Morel and C. Renvoise. Global optimization by suppression of partial redundancies. Communications of the ACM, 22(2):96-103, Feb 1979.
[26]
S. Naeher et al. Leda, a library for efficient data types and algorithms. Avail. via FTP from sbsvax.cs.unisb.de, 1994.
[27]
C. Norris and L. L. Pollock. Register allocation over the program dependence graph. In Proc. ACM SIGPLAN '94 ConJ': on Prog. Language Design and Implementation, pages 266-277. ACM, June 1994.
[28]
J. Rumbaugh, M. Blaha, W. Premerlani, F. Eddy, and W. Lorensen. Object-Oriented Modeling and Design. Prentice Hall, 199 1.
[29]
J. Ruttenberg, G. Gao, A. Stoutchinin, and W. Lichtenstein. Software pipelining showdown: Optimal vs. heurisitic methods in a production compiler. In Proc. ACM SIGPLAN'96 Con5 on Prog. Language Design and Implementation, pages l-l 1. ACM, May 1996.
[30]
A. Stepanov and M. Lee. The standard template library. Tech. Report HP Lab. HPL-94-34,1994. Available from http://www.cs.rpi.edu/-/ musser/stl.html.
[31]
B. Stroustrup. The C++ Programming Language. Addison-Wesley, 199 1.
[32]
Taligent Inc. Building object-oriented frameworks. http:Nwww.taligent.corn/building-oofw.html, 1994.
Recommendations
Code reuse in an optimizing compiler
OOPSLA '96: Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applicationsThis paper describes how the cmcc compiler reuses code---both internally (reuse between different modules) and externally (reuse between versions for different target machines). The key to reuse are the application frameworks developed for global data-...
Compiler-directed dynamic computation reuse: rationale and initial results
MICRO 32: Proceedings of the 32nd annual ACM/IEEE international symposium on MicroarchitectureRecent studies on value locality reveal that many instructions are frequently executed with a small variety of inputs. This paper proposes an approach that integrates architecture and compiler techniques to exploit value locality for large regions of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Oct. 1996
443 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/236338
- Chairmen:
- Mary Loomis,
- Lougie Anderson,
- James Coplien
Copyright © 1996 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 October 1996
Published in SIGPLAN Volume 31, Issue 10
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations11Total Citations
- 677Total Downloads
- Downloads (Last 12 months)77
- Downloads (Last 6 weeks)12
Reflects downloads up to 21 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in