Call Graphs for Languages with Parametric Polymorphism
The performance of contemporary object oriented languages depends on
optimizations such as devirtualization, inlining, and specialization, and these in turn
depend on precise call graph analysis. Existing call graph analyses
do not take advantage of the information provided by the rich type
systems of contemporary languages, in particular generic type arguments.
Many existing approaches analyze Java bytecode, in which generic types
have been erased.
This paper shows that this discarded information is actually very useful
as the context in a context-sensitive analysis, where it
significantly improves precision and keeps
the running time small. Specifically, we propose and evaluate call graph
construction algorithms in which the contexts of a method are (i) the
type arguments passed to its type parameters, and (ii) the static types
of the arguments passed to its term parameters.
The use of static types from the caller as context is effective because it allows more precise dispatch of call sites inside the callee.
Our evaluation indicates that the average number of contexts required per method is small.
We implement the analysis in the Dotty compiler for Scala,
and evaluate it on programs that use the type-parametric Scala
collections library and on the Dotty compiler itself.
The context-sensitive analysis runs 1.4x faster than a context-insensitive
one and discovers 20% more monomorphic call sites at the same time. When applied
to method specialization, the imprecision in a context-insensitive
call graph would require the average method to be cloned 22 times,
whereas the context-sensitive
call graph indicates a much more practical 1.00 to 1.50 clones per method.
We applied the proposed analysis to automatically specialize generic methods.
The resulting automatic transformation achieves the same performance
as state-of-the-art techniques requiring manual annotations,
while reducing the size of the generated bytecode by up to 5$\times$.
Wed 2 NovDisplayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change
15:40 - 17:20
Static AnalysisOOPSLA at Matterhorn 1
Chair(s): Sam Guyer Tufts University
|Accelerating Program Analyses by Cross-Program Training|
Sulekha Kulkarni Georgia Tech, Ravi Mangal Georgia Institute of Technology, Xin Zhang Georgia Tech, Mayur Naik Georgia TechDOI
|An Improved Algorithm for Slicing Machine Code|
Venkatesh Srinivasan University of Wisconsin - Madison, Thomas Reps University of Wisconsin - Madison and Grammatech Inc.DOI Pre-print
|Call Graphs for Languages with Parametric Polymorphism|
Dmytro Petrashko EPFL, Vlad Ureche EPFL, Switzerland, Ondřej Lhoták University of Waterloo, Martin Odersky EPFL, SwitzerlandDOI
Satish Chandra Samsung Research America, Colin Gordon Drexel University, Jean-Baptiste Jeannin Carnegie Mellon University , Cole Schlesinger Samsung Research America, Manu Sridharan Samsung Research America, Frank Tip Samsung Research America, Young-il Choi Samsung ElectronicsDOI Pre-print