Matthew Arnold
Vivek Sarkar
Peter F. Sweeney
Abstract
In this paper, we present a comparative study of static and profile-based heuristics for inlining. Our motivation for this study is to use the results to design the best inlining algorithm that we can for the Jalapeño dynamic optimizing compiler for Java [6]. We use a well-known approximation algorithm for the KNAPSACK problem as a common “meta-algorithm” for the inlining heuristics studied in this paper. We present performance results for an implementation of these inlining heuristics in the Jalapeño dynamic optimizing compiler. Our performance results show that the inlining heuristics studied in this paper can lead to significant speedups in execution time (up to 1.68x) even with modest limits on code size expansion (at most 10%).
- 1 F. E. Allen and J. Cocke. A catalogue of optimizing transformations. In Design and Optimization of Compilers, pages 1-30. Prentice-Hall, 1972.Google Scholar
- 2 B. Alperu, D. Attanvaio, J. J. Barton, A. Cocchi, S. Flynn Hummel, D. Lieber, T. Ngo, M. Mergen, J. Shepherd, and S. Smith. Implementation of Jalepefio in Java. In AGM Conference on Object. Oriented Programming Systems, Languages, and Applications, November 1999. Google ScholarDigital Library
- 3 B. AJpern, A. Cocchi, D. Lieber, M. Merges, and V. Sarkar. Jalape~fio -- a compiler-supported Java virtual ma~hjne for servers. In ACM SIGPLAN 1999 Workshop on Compiler Support for System SofluJare (WCSSS'99), May 1999. Also available as INRIA report No. 0228, March 1999.Google Scholar
- 4 G. Ammons, T. Ball, and J.R. Larus. Exploiting hardware performance counters with flow and context sensitive profiling. In SIGPLAN '97 Conf. on Programming Language Design and Implementation, 1997. Google ScholarDigital Library
- 5 A. Ayers, R. Gottlieb, and R. Schoolex. Aggressive inlining. In SIGPLAN '97 Conf. on Programming Language Design and Implementation, pages 134- 145, June 1997. Google ScholarDigital Library
- 6 M.G. Burke, J.-D. Choi, S. Fink, D. Grove, M. Hind, V. Sarkar, M.J. Serrano, V.C. Sreedhar, H. Srinivasan, and J. Whaley. The Jalapefio Dynamic Optimizing Compiler for Jaw. In A GM lava Grande Conference, June 1999. Google ScholarDigital Library
- 7 P. P. Chang, S. A. Mabllce, W. Y. Chen, and W.-M. W. Hwu. Profile-guided automatic i,H,e expansion for c programs. Soft~zare - Practice and Ezperience, 22(5):349-369, May 1992. Google ScholarDigital Library
- 8 K. D. Cooper, M. W. Hall, and L. Torczon. Unexpected side effects of inline substitution: A case study. ACM LOPLAS, 1(1):22-32, March 1992. Google ScholarDigital Library
- 9 The Standard Performance Evaluation Corporation. SPEC JVM98 Benchmarks. http://www.spec.org/osg/jvm98/, 1998.Google Scholar
- 10 J. Dean and C. Chambers. Towards better inlining dedsious using inlining trials. In Proc. of the 1994 A CM Conf. on LISP and Functional Programming, 1994. Google ScholarDigital Library
- 11 J. Dean, D. Grove, emd C. Chambers. Optimization of object-oriented programs using static class hierarchy analysis. In the 9th European Conference on Object.Oriented Programming, 1995. Google ScholarDigital Library
- 12 M. R. Garey and D. S. Johnson. Computers and Intractibility: A Guide to the Theory of NP. Completeness. W.H. Freeman and Company, 1979. Google ScholarDigital Library
- 13 D. Grove, J. Dean, C. Gsrrett, and C. Chambers. Profde-guided receiver class prediction. In A CM Conference on Object. Oriented Programming Systems, Languages, and Applications, pages 108--123, October 1995. Google ScholarDigital Library
- 14 S. Jagannathan and A. Wright. Flow-directed inllrtlng. In SIGPLAN '96 Conf. on Programming Language Design and Implementation, pages 193-- 205, May 1996. Google ScholarDigital Library
- 15 O. Kaser and C.R. Ramakrishnan. Evaluating 72, 1998.Google Scholar
- 16 Robert W. Scheifler. An analysis of inline substitution for a structured programming language. GAGM, 20(9), September 1977. Google ScholarDigital Library
- 17 Oscar Wadden and R. Kent Dybvig. Fast and effective procedure ;rdln~ng. In ~th International Symposium on Static Analysis, September 1997. Google ScholarDigital Library
Index Terms
- A comparative study of static and profile-based heuristics for inlining
Recommendations
Automatic construction of inlining heuristics using machine learning
CGO '13: Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)Method inlining is considered to be one of the most important optimizations in a compiler. However, a poor inlining heuristic can lead to significant degradation of a program's running time. Therefore, it is important that an inliner has an effective ...
A comparative study of static and profile-based heuristics for inlining
DYNAMO '00: Proceedings of the ACM SIGPLAN workshop on Dynamic and adaptive compilation and optimizationIn this paper, we present a comparative study of static and profile-based heuristics for inlining. Our motivation for this study is to use the results to design the best inlining algorithm that we can for the Jalapeño dynamic optimizing compiler for ...
A comparative study of static CIA techniques
Internetware '12: Proceedings of the Fourth Asia-Pacific Symposium on InternetwareSoftware Change Impact Analysis (CIA) is an essential technique to identify the unpredicted and potential effects caused by software changes. A rich body of different CIA techniques, especially static CIA techniques, have continuously emerged in recent ...
Comments