Abstract
The effectiveness of an inlining algorithm is determined not only by its ability to recognize inlining opportunities but also by its discretion in exercising those opportunities. This paper presents a new inlining algorithm for higher-order languages that combines simple analysis techniques with demand-driven online transformation to achieve consistent and often dramatic performance gains in fast linear time. The algorithm is shown to be as effective as and significantly faster than offline, analysis-intensive algorithms recently described in the literature.
This material is based on work supported in part by the National Science Foundation under grant number CDA-9312614.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
Andrew W. Appel. Compiling with Continuations. Cambridge University Press, 1992.
Andrew W. Appel and Trevor Jim. Shrinking lambda expressions in linear time. To appear in Journal of Functional Programming.
J. Michael Ashley. A practical and flexible flow analysis for higher-order languages. In Proceedings of the ACM Symposium on Principles of Programming Languages, pages 184–194, 1996.
J. Michael Ashley. The effectiveness of flow analysis for inlining. In Proceedings of the 1997 ACM SIGPLAN International Conference on Functional Programming, 1997. To appear.
J. Eugene Ball. Predicting the effects of optimization on a procedure body. SIGPLAN Notices, 14(8):214–220, August 1979. Proceedings of the ACM SIGPLAN '79 Symposium on Compiler Construction.
R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K Zadeck. Efficiently computing static single assignment form and the control dependence graph. Technical Report RC 14756, IBM, 1991.
Jeffrey Dean and Craig Chambers. Towards better inlining decisions using inlining trials. In Proceedings of the 199/ ACM Conference on LISP and Functional Programming, pages 273–282, 1994.
Suresh Jagannathan and Andrew Wright. Flow-directed inlining. In Proceedings of the ACM SIGPLAN '96 Conference on Programming Language Design and Implementation, pages 193–205, 1996.
Oscar Waddell and R. Kent Dybvig. Fast and effective procedure inlining. Technical Report 484, Indiana University Computer Science Department, Lindley Hall 101, Bloomington Indiana, 47405, 1997.
M. N. Wegman and F. K. Zadeck. Constant propagation with conditional branches. ACM Transactions on Programming Languages and Systems, 3(2):181–210, 1991. *** DIRECT SUPPORT *** A0008C44 00002
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Waddell, O., Dybvig, R.K. (1997). Fast and effective procedure inlining. In: Van Hentenryck, P. (eds) Static Analysis. SAS 1997. Lecture Notes in Computer Science, vol 1302. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0032732
Download citation
DOI: https://doi.org/10.1007/BFb0032732
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63468-3
Online ISBN: 978-3-540-69576-9
eBook Packages: Springer Book Archive