Abstract
The express-lane transformation isolates and duplicates frequently executed program paths, aiming for better data-flow facts along the duplicated paths. An express-lane p is a copy of a frequently executed program path such that p has only one entry point at its beginning; p may have branches back to the original code, but the original code never branches into p. Classical data-flow analysis is likely to find sharper data-flow facts along an express-lane, because there are no join points.
This paper describes several variants of interprocedural express-lane transformations; these duplicate hot interprocedural paths, i.e., paths that may cross procedure boundaries. The paper also reports results from an experimental study of the effects of the express-lane transformation on interprocedural range analysis.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
A. V. Aho, J.E. Hopcroft, and J.D. Ullman. The design and analysis of computer algorithms. Addison-Wesley, 1974.
Alfred V. Aho. Algorithms for finding patterns in strings, chapter 5, pages 255–300. MIT Press, 1994.
G. Ammons and J. Larus. Improving data-flow analysis with path profiles. In PLDI98.
T. Ball and J. Larus. Efficient path profiling. In MICRO 1996, 1996.
R. Bodik, R. Gupta, and M.L. Soffa. Interprocedural conditional branch elimination. In PLDI’97.
Rastislav Bodik. Path-sensitive, value-flow optimizations of programs. PhD thesis, University of Pittsburg, 2000.
P.P. Chang, S.A. Mahlke, and W.W. Hwu. Using profile information to assist classic code optimizations. Software practice and experience, 1(12), Dec. 1991.
J. A. Fisher. Trace scheduling:A technique for global microcode compaction. In IEEE Trans. on Computers, volume C-30, pages 478–490, 1981.
R.E. Hank. Region-Based Compilation. PhD thesis, UIUC, 1996.
D. Melski and T. Reps. Interprocedural path profiling. In CC99.
D.G. Melski. Interprocedural Path Profiling and the Interprocedural Express-Lane Transformation. PhD thesis, University ofWisconsion, 2002.
F. Mueller and D. B. Whalley.Avoiding unconditional jumps by code replication. In PLDI92.
M. Poletto. Path splitting: a technique for improving data flow analysis, 1995.
M.N. Wegman and F.K. Zadeck. Constant propagation with conditional branches. In POPL85.
Reginald Clifford Young. Path-based Compilation. PhD thesis, Harvard University, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Melski, D., Reps, T. (2003). The Interprocedural Express-Lane Transformation. In: Hedin, G. (eds) Compiler Construction. CC 2003. Lecture Notes in Computer Science, vol 2622. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36579-6_15
Download citation
DOI: https://doi.org/10.1007/3-540-36579-6_15
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00904-7
Online ISBN: 978-3-540-36579-2
eBook Packages: Springer Book Archive