000217276 001__ 217276
000217276 005__ 20190317000417.0
000217276 037__ $$aREP_WORK
000217276 245__ $$aCall Graphs for Languages with Parametric Polymorphism
000217276 269__ $$a2016
000217276 260__ $$c2016
000217276 336__ $$aReports
000217276 520__ $$aThe 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.
000217276 6531_ $$acallgraphs
000217276 6531_ $$astatic analysis
000217276 6531_ $$aoptimizations
000217276 6531_ $$aobject oriented
000217276 700__ $$0248093$$g233192$$aPetrashko, Dmytro
000217276 700__ $$0245399$$g200717$$aUreche, Vlad
000217276 700__ $$aLhot\'{a}k, Ond\v{r}ej
000217276 700__ $$aOdersky, Martin$$0241835$$g126003
000217276 8564_ $$uhttps://infoscience.epfl.ch/record/217276/files/paper.pdf$$zPreprint$$s331698$$yPreprint
000217276 909C0 $$xU10409$$0252187$$pLAMP
000217276 909CO $$qGLOBAL_SET$$pIC$$ooai:infoscience.tind.io:217276$$preport
000217276 917Z8 $$x233192
000217276 917Z8 $$x233192
000217276 917Z8 $$x233192
000217276 917Z8 $$x233192
000217276 937__ $$aEPFL-REPORT-217276
000217276 973__ $$aEPFL
000217276 980__ $$aREPORT