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 Nov Times are displayed in time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change
15:40 - 17:20
|Accelerating Program Analyses by Cross-Program Training|
Sulekha KulkarniGeorgia Tech, Ravi MangalGeorgia Institute of Technology, Xin ZhangGeorgia Tech, Mayur NaikGeorgia TechDOI
|An Improved Algorithm for Slicing Machine Code|
Venkatesh SrinivasanUniversity of Wisconsin - Madison, Thomas RepsUniversity of Wisconsin - Madison and Grammatech Inc.DOI Pre-print
|Call Graphs for Languages with Parametric Polymorphism|
Dmytro PetrashkoEPFL, Vlad UrecheEPFL, Switzerland, Ondřej LhotákUniversity of Waterloo, Martin OderskyEPFL, SwitzerlandDOI
Satish ChandraSamsung Research America, Colin GordonDrexel University, Jean-Baptiste JeanninCarnegie Mellon University , Cole SchlesingerSamsung Research America, Manu SridharanSamsung Research America, Frank TipSamsung Research America, Young-il ChoiSamsung ElectronicsDOI Pre-print