harpoon.Analysis.MetaMethods
Class SmartCallGraph

java.lang.Object
  jpaul.Graphs.DiGraph<HMethod>
      harpoon.Analysis.CallGraph
          harpoon.Analysis.Quads.CallGraph
              harpoon.Analysis.MetaMethods.SmartCallGraph

public class SmartCallGraph
extends CallGraph

SmartCallGraph is an improved call graph produced by compressing a meta call graph, ie, all metamethods are shrinked down to their originating method). Constructing the call graph at the level of meta methods and shrinking it later to method level is more precise than constructing the call graph for methods directly using some RTA-like algorithm.

For a simple program that does just a System.out.println(), the size of the largest group of mutually recursive methods (which corresponds to a strongly connected component in the call graph) decreased from 53 to 8.

Version:

$Id: SmartCallGraph.java,v 1.10 2005/08/17 23:40:52 salcianu Exp $

Author:

Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>

Field Summary

Fields inherited from class harpoon.Analysis.CallGraph

navigator

Fields inherited from class jpaul.Graphs.DiGraph

CACHING

Constructor Summary

SmartCallGraph(CachingCodeFactory hcf, Linker linker, ClassHierarchy ch, Set roots)
Convenient constructor for use in cases when a meta call graph does not already exist.

SmartCallGraph(MetaCallGraph mcg)
Creates a SmartCallGraph.

Method Summary

Set	callableMethods() Returns the set of all the methods that can be called in the execution of the program.
HMethod[]	calls(HMethod hm) Returns an array containing all possible methods called by method m.
HMethod[]	calls(HMethod hm, CALL cs) Returns an array containing all possible methods called by method m at the call site cs.
static Set	constructMRoots(Set roots, ClassHierarchy ch) Constructs the set of method roots for the compiled program.
CALL[]	getCallSites(HMethod hm) Returns a list of all the CALLs quads in the code of hm.
Set	getRunMethods()

Methods inherited from class harpoon.Analysis.CallGraph

getBiDiNavigator, getForwardNavigator, getRoots

Methods inherited from class jpaul.Graphs.DiGraph

constructBiDiNavigator, dfs, dfs2, diGraph, diGraph, findPath, findPath, forAllVertices, getComponentDiGraph, numArcs, numVertices, reverseDiGraph, subDiGraph, toString, transitivePred, transitivePred, transitiveSucc, transitiveSucc, union, vertices

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

SmartCallGraph

public SmartCallGraph(MetaCallGraph mcg)

Creates a SmartCallGraph.

Parameters:

mcg - Meta call graph

SmartCallGraph

public SmartCallGraph(CachingCodeFactory hcf,
                      Linker linker,
                      ClassHierarchy ch,
                      Set roots)

Convenient constructor for use in cases when a meta call graph does not already exist.

Parameters:

hcf - Caching code factory used to produce the code of the methods

linker - Linker to get classes

ch - Class hierarchy

roots - Set of program roots (the same notion of roots as that used by QuadClassHierarchy). The parameters of this constructor are used to construct a meta call graph that is used to create this smart call graph.

Method Detail

calls

public final HMethod[] calls(HMethod hm)

Returns an array containing all possible methods called by method m. If hm doesn't call any method, return an array of length 0.

Specified by:

calls in class CallGraph

calls

public final HMethod[] calls(HMethod hm,
                             CALL cs)

Returns an array containing all possible methods called by method m at the call site cs. If there is no known callee for the call site cs>/code>, or if cs doesn't belong to the code of hm, return an array pof length 0.

Specified by:

calls in class CallGraph

getCallSites

public CALL[] getCallSites(HMethod hm)

Returns a list of all the CALLs quads in the code of hm.

Specified by:

getCallSites in class CallGraph

callableMethods

public Set callableMethods()

Returns the set of all the methods that can be called in the execution of the program.

Specified by:

callableMethods in class CallGraph

getRunMethods

public Set getRunMethods()

Overrides:

getRunMethods in class CallGraph

Returns:

set of all run() methods that may be the bodies of a thread started by the program (optional operation).

constructMRoots

public static Set constructMRoots(Set roots,
                                  ClassHierarchy ch)

Constructs the set of method roots for the compiled program. MetaCallGraphImpl has a different definition of roots than QuadClassHierarchy (SAMain uses that definition). Note: the constructor of SmartCallGraph already calls this; no need to call it externally.

Parameters:

roots - Set of roots from SAMain (this includes both methods and classes)

ch - Class hierarchy for the compiled program.

Returns:

Set of method roots for the compiled program. This set includes: the main method + all methods that may be called by JVM (including all static initializers). TODO: unify the two concepts of roots.