Estimating run-time progress of a call graph construction algorithm

This work considers static analysis algorithms that are integrated with a development environment. In this context, IDE users can benefit from continuously-updated information about the run-time progress of the analysis algorithm (i.e., what portion of the analysis work is completed). IDEs can provide the means to convey this information back to the user — for exam-ple, the Java IDE in Eclipse achieves this by employing GUI elements such as progress bars. Precise tracking of the run-time progress of an anal-ysis algorithm requires a priori knowledge of the total running time of the analysis. Such knowledge is typ-ically not available, and analysis builders need to em-ploy various heuristics to estimate run-time progress. In this paper we describe our initial work on defin-ing and evaluating such heuristics for a whole-program analysis in Eclipse. The analysis, based on the well-known Rapid Type Analysis (RTA) approach, builds a call graph for a Java program, for subsequent use in various software tools. We propose multiple heuristics to estimate run-time analysis progress; these heuristics have been implemented in a publicly available Eclipse plug-in. We report the results of evaluating each heuris-tic on an large set of Java programs.