Estimating the Run-Time Progress of a Call Graph Construction Algorithm53-62

This work considers static analysis algorithms that are integrated with a development environment. In this context, IDE users can benefit from continuouslyupdated 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 example, the Java IDE in Eclipse achieves this by employing GUI elements such as progress bars. Precise tracking of the run-time progress of an analysis algorithm requires a priori knowledge of the total running time of the analysis. Such knowledge is typically not available, and analysis builders need to employ various heuristics to estimate run-time progress. In this paper we describe our initial work on defining and evaluating such heuristics for a whole-program analysis in Eclipse. The analysis, based on the wellknown 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 heuristic on an large set of Java programs.