The Effect of Call Graph Construction Algorithms for Object-Oriented Programs on Automatic Clustering

Call graphs are commonly used as input for automatic clustering algorithms, the goal of which is to extract the high level structure of the program under study. Determining the call graph for a procedural program is fairly simple. However, this is not the case for programs written in objectoriented languages, due to polymorphism. A number of algorithms for the static construction of an object-oriented program’s call graph have been developed in the compiler optimization literature in recent years. In this study we investigate the effect of three such algorithms on the automatic clustering of the Java Expert System Shell (JESS). Object-oriented programs have an inherently richer structure than those written in procedural languages, and so even medium sized programs such as JESS produce large graphs. Existing tools that we are aware of are not able to process such graphs. Consequently, we have developed our own algorithm for automatic clustering that is scalable to large graphs. This algorithm also supports user specified constraints through the use of ‘weighted ’ arcs.