With the increasing importance of just-in-time or dynamic compilation and the use of program analysis as part of software
development environments, there is a need for techniques for demand driven construction of a call graph. We have developed
a technique for demand driven call graph construction which handles dynamic calls due to polymorphism in object-oriented languages.
Our demand driven technique has the same accuracy as the corresponding exhaustive technique. The reduction in the graph construction
time depends upon the ratio of the cardinality of the set of
influencing nodes and the total number of nodes in the entire program.
This paper presents a detailed experimental evaluation of the benefits of the demand driven technique over the exhaustive
one. We consider a number of scenarios, including resolving a single call site, resolving all call sites in a method, resolving
all call sites within all methods in a class, and computing reaching definitions of all actual parameters inside a method.
We compare the analysis time, the number of methods analyzed, and the number of nodes in the working set for the demand driven
and exhaustive analyses.
We use SPECJVM programs as benchmarks for our experiments. Our experiments show for the larger SPECJVM programs, javac, mpegaudio,
and jack, demand driven analysis on the average takes nearly an order of magnitude less time than exhaustive analysis.
This research was supported by NSF CAREER award ACI-9733520an d NSF grant CCR-9808522.