Scalable propagation-based call graph construction algorithms
Propagation-based call graph construction algorithms
have been studied intensively in the 1990s, and
differ primarily in the number of sets that are used
to approximate run-time values of expressions.
In practice, algorithms such as RTA that use a single set
for the whole program scale well.
The scalability of algorithms such as 0-CFA that use one
set per expression remains doubtful.
In this paper, we investigate the design space between RTA and 0-CFA.
We have implemented various novel algorithms in the context of Jax,
an application extractor for Java, and shown that they all scale to
a 325,000-line program. A key property of these algorithms is that they
do not analyze values on the run-time stack, which makes them efficient
and easy to implement. Surprisingly, for detecting unreachable methods,
the inexpensive RTA algorithm does almost as well as the seemingly more
powerful algorithms.
However, for determining call sites with a single target,
one of our new algorithms
obtains the current best tradeoff between speed and precision.
[ Research home page ]
[ IBM home page |
Order |
Search |
Contact IBM |
Legal ]