Mary F. Fernández
ABSTRACT
Modula-3 supports development of modular programs by separating an object's interface from its implementation. This separation induces a runtime overhead in the implementation of objects, because it prevents the compiler from having complete information about a program's type hierarchy. This overhead can be reduced at link time, when the entire type hierarchy becomes available. We describe opportunities for link-time optimization of Modula-3, present two link-time optimizations that reduce the runtime costs of Modula-3's opaque types and methods, and show how link-time optimization could provide C++ which the benefits of opaques types at no additional runtime cost.
Our optimization techniques are implemented in mld, a retargetable linker for the MIPS, SPARC, and Intel 486, mld links a machine-independent intermediate code that is suitable for link-time optimization and code generation. Linking intermediate code simplifies implementation of the optimizations and makes it possible to evaluate them on a wide range of architectures. mld's optimizations are effective: they reduce the total number of instructions executed by up to 14% and convert as many as 79% of indirect calls to direct calls.
- 1.E. Adams. The old man and the C. In Proceedzngs of the Summer USEN{X Conference, pages 15-26, 1984.]] Google Scholar
- 2.A. Aho, R. Sethi, and J. Ullman. Compilers- Prznczples, Technzques and Tools. Addison Wesley, 1986.]] Google ScholarDigital Library
- 3.T. Ball and J. R. Larus, Optimally profiling and tracing programs. In Conference Record of the A CM Symposium on Principles of Programming Languages, pages 59-70, Albuquerque, NM, Jan. 1992.]] Google ScholarDigital Library
- 4.G. Baumgartner and V. Russo. Implementing signatures for C++ In Proceedings of the USENL~ C++ Conference, pages 37-56, April 1994.]] Google ScholarDigital Library
- 5.M. E. Benitez and J. W. Davidson. A portable global optimizer and linker. Proceedzngs of the SICPLAN'83 Conference on Programming Language Design and Impleme~tatzon, SIGPLAN Notices, 23(7):329-338, July 1988.]] Google ScholarDigital Library
- 6.B. Calder and D. Grunwald. Reducing indirect function call overhead in C++ programs. In ACM Symposium on Principles of Programming Languages, pages 397-408, 1994.]] Google ScholarDigital Library
- 7.B. Calder, D. Grunwald, and B. Zorn. Quantifying behavioral differences between C and C++ programs. Journal of Programming Languages, 2(4), ~994.]]Google Scholar
- 8.C. Chambers. The Cecil language Specification and rationale. Technical Report CSE-TR-93-03-05, University of Washington, 1993.]]Google Scholar
- 9.C. Chambers and D Ungar. Making pure objectoriented languages practical. In OOPSLA Conference Proceedings, pages 1-15, 1991. Published as SIGPLAN Notices, 26(}1), 1991.]] Google ScholarDigital Library
- 10.C. S. Collberg. Flexible Encapsulation. PhD thesis, Lurid University, Sweden, 1992.]]Google Scholar
- 11.J. Dean, C. Chambers, and D. Grove. Selective specialization for object-oriented languages. In SIGPLAN Conference on Programming Language Design and Implementation, 1995. To appear.]] Google ScholarDigital Library
- 12.D. Detlefs. Garbage collection and run-time typing as a C++ library. In Proceedings of the USENIX C++ Conference, pages 37-56, August. 1992.]]Google Scholar
- 13.M. Fern~tndez. Simple and effective link-time optimization of Modula-3 programs. Technical Report TR-474- 94, Department of Computer Science, Princeton University, Nov. 1994.]]Google Scholar
- 14.C. W. Fraser and D. R. Hanson. A Retargetable C Compiler: Design and Implementation. Benjamin/Cummings, Redwood City, CA, 1995. ISBN 0-8053-1670-1.]] Google ScholarDigital Library
- 15.C. W. Fraser, D. R. Hanson, and T. A. Proebsting. Engineering a simple, efficient code-generator generator. A UM Letters on Programm~r,g Languages and Systems, 1(3):213-226, Sept. 1992.]] Google ScholarDigital Library
- 16.C. W. Fraser and R. R. Henry. Hard-coding bottomup code generation tables to save time and space. Software--Practice and Experience, 21(t):1-t2, Jan. 1991.]] Google ScholarDigital Library
- 17.C. W. Fraser, R. R. Henry, and T. A. Proebsting. BURG--Fast optimM instruction selection ~nd tree parsing. SIGPLAN Notices, 27(4):68-76, Apr. 1992.]] Google ScholarDigital Library
- 18.M. I. Himelstein, F. C. Chow, and K. Enderby. Crossmodule optimizations: Its implementation and benefits. In Proceedings of the Summer USENIX Technzcal Cor~ferer~ce, pages 347-356, Phoenix, AZ, June 1987.]]Google Scholar
- 19.U. ttolzle. Adaptive optimization for Self: Reconciling H~gh Performance w~th Exploratory Programming. PhD thesis, Stanford University, August 1994.]]Google Scholar
- 20.U. Holzle. Optimizing dynamicMly-dispatched calls with run-time type feedback, tn SIGPLAN Conference on Programming Language Design and Implernerta&on, pages 326-335, 1994.]] Google ScholarDigital Library
- 21.B. Kalsow and E. Muller. SRC Modula-3 Version 2. I1. Digital Equipment Corporation Systems Research Center, January 1992.]]Google Scholar
- 22.D. Lea. Customization in C++ In Proceedings of the]]Google Scholar
- 23.D. Lea. Panel discussion: Run time type information and class design. In Proceedings of the U,_qEN{X C++ Conference, pages 341-347, August 1992.]]Google Scholar
- 24.M. Linton and D. Pan. Interface translation and implementation filtering. In Proceedings of the lrSENLY C++ Conference, pages 227-236, April 1994.]]Google Scholar
- 25.S. McFarling. Procedure merging with instruction caches. In SIGPLAN Conference on Programming Language Deszgn and Implementa&on, pages 71-79, Toronto, Ontario, Canada, June 1991.]] Google ScholarDigital Library
- 26.L. N ackman and J. Barton. Base-class composition with multiple derivation and virtual bases. In Proceedings of the USENIX C++ Conference, pages 57-71, April 1994.]] Google ScholarDigital Library
- 27.G. Nelson, editor. Systems Programmzng wzth Modula- 3. Prentice Hall, 1991.]] Google ScholarDigital Library
- 28.E. Pelegri-Llopart and S. L. Graham. Optimal code generation for expression trees: An application of BURS theory. In Conference Record of the A UAI Symposium or~ Pmnczples of Programmzng La~guc, ges, pages 294-308, San Diego, CA, Jan. 1988.]] Google ScholarDigital Library
- 29.K. Pettis and R. Hansen. Profile guided code positioning. In SIGPLAN Conference on Programming Language Design and {mplementa&on, 1990. Also in SIG- PLAN Notices, \%1. 25, No. 6, June, 1990.]] Google ScholarDigital Library
- 30.N. Ramsey and M. F. FernXndez. The New Jersey machine-code toolkit. In Proceedings of the I'V~nter 1995 USENL~ Conference, pages 289-30'2, New Orleans, LA, Jan. 1995.]] Google ScholarDigital Library
- 31.R L. Sites, editor. Alpha Architecture Reference Manual. Digital Press, 1992.]] Google ScholarDigital Library
- 32.A. Srivastava and D. W. Wall. A practical system for intermodule code optimization at link-time. Journal of Programm,ng Languages, pages 1-18, March 1993.]]Google Scholar
- 33.A. Srivastava and D. W. Wall. Link-time optimization of address calculation on a 64-bit architecture. In SIG- PLAN Conference on Programming Language Design and {mplementatlon, pages 49-60, 1994.]] Google ScholarDigital Library
- 34.J. W. Stamos. Static grouping of small objects to enhance performance of a paged virtual memory. A CM Transactions on Computer Systems, 2(2), t984.]] Google ScholarDigital Library
- 35.B. Stroustrup. The C++ Programming Language. Addison Wesley, second edition, 1991.]] Google ScholarDigital Library
- 36.B. Stroustrup and D. Lenkov. Run time type identification in C++. In Proceedings of the USENIX C++ Conference, pages 313-340, August 1992.]]Google Scholar
- 37.D. Ungar and R. B. Smith. SELF: The power of simplicity. OOPSLA '87 Conference Proceedzngs, SIG- PLAN Notices, 22(12):'2'27-241, Dec. 1987.]] Google ScholarDigital Library
- 38.D. W. Wall. Experience with a software-defined machine architecture. A CM Transactzons on Programruing Languages and Systems, t4(3):299-338, 1992.]] Google ScholarDigital Library
Index Terms
- Simple and effective link-time optimization of Modula-3 programs
Recommendations
Link-time optimization of ARM binaries
LCTES '04: Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systemsThe overhead in terms of code size, power consumption and execution time caused by the use of precompiled libraries and separate compilation is often unacceptable in the embedded world, where real-time constraints, battery life-time and production costs ...
Simple and effective link-time optimization of Modula-3 programs
Modula-3 supports development of modular programs by separating an object's interface from its implementation. This separation induces a runtime overhead in the implementation of objects, because it prevents the compiler from having complete information ...
Simple, effective code-size reduction for functional programs
IFL'04: Proceedings of the 16th international conference on Implementation and Application of Functional LanguagesCode-size reduction is an important area of investigation for computer system developers due to the increasing use of technologies such as communication networks and embedded systems for which program size is an important factor. A new software-based ...
Comments