5.4 Call Graphs

5.4 Call Graphs

The intraprocedural control flow graph represents possible execution paths through a single procedure or method. interprocedural control flow can also be represented as a directed graph. The most basic model is the call graph, in which nodes represent procedures (methods, C functions, etc.) and edges represent the "calls" relation. For example, a call graph representation of the program that includes the collapseNewlines method above would include a node for StringUtils. collapseNewlines with a directed edge to method String.charAt.

Call graph representations present many more design issues and trade-offs than intraprocedural control flow graphs; consequently, there are many variations on the basic call graph representation. For example, consider that in object-oriented languages, method calls are typically made through object references and may be bound to methods in different subclasses depending on the current binding of the object. A call graph for programs in an object-oriented language might therefore represent the calls relation to each of the possible methods to which a call might be dynamically bound. More often, the call graph will explicitly represent only a call to the method in the declared class of an object, but it will be part of a richer representation that includes inheritance relations. Constructing an abstract model of executions in the course of analysis will involve interpreting this richer structure.

Figure 5.6 illustrates overestimation of the calls relation due to dynamic dispatch. The static call graph includes calls through dynamic bindings that never occur in execution. A.foo() calls b.bar(), and b's declared class is C, and S inherits from C and overrides bar(). The call graph includes a possible call from A.foo() to S.bar(). It might very well include that call even if a more precise analysis could show that b can never actually be bound to an object of subclass S, because in general such analysis is very expensive or even impossible.

Figure 5.6: Overapproximation in a call graph. Although the method A.check() can never actually call C.foo(), a typical call graph construction will include it as a possible call.

If a call graph model represents different behaviors of a procedure depending on where the procedure is called, we call it context-sensitive. For example, a context-sensitive model of collapseNewlines might distinguish between one call in which the argument string cannot possibly be empty, and another in which it could be. Contextsensitive analyses can be more precise than context-insensitive analyses when the model includes some additional information that is shared or passed among procedures. Information not only about the immediate calling context, but about the entire chain of procedure calls may be needed, as illustrated in Figure 5.7. In that case the cost of context-sensitive analysis depends on the number of paths from the root (main program) to each lowest level procedure. The number of paths can be exponentially larger than the number of procedures, as illustrated in Figure 5.8.

Figure 5.7: The Java code above can be represented by the context-insensitive call graph at left. However, to capture the fact that method depends never attempts to store into a nonexistent array element, it is necessary to represent parameter values that differ depending on the context in which depends is called, as in the context-sensitive call graph on the right.

Figure 5.8: The number of paths in a call graph - and therefore the number of calling contexts in a context-sensitive analysis - can be exponentially larger than the number of procedures, even without recursion.

   1  public class C {
   2
   3      public static C cFactory(String kind) {
   4             if (kind == "C") return new C();
   5             if (kind == "S") return new S();
   6             return null;
   7      }
   8
   9      void foo() {
   10         System.out.println("You called the parent's method");
   11     }
   12
   13     public static void main(String args[]) {
   14            (new A()).check();
   15     }
   16  }
   17
   18  class S extends C {
   19        void foo() {
   20            System.out.println("You called the child's method");
   21     }
   22  }
   23
   24  class A {
   25        void check() {
   26         C myC = C.cFactory("S");
   27         myC.foo();
   28    }
   29  }

The Java compiler uses a typical call graph model to enforce the language rule that all checked exceptions are either handled or declared in each method. The throws clauses in a method declaration are provided by the programmer, but if they were not, they would correspond exactly to the information that a context insensitive analysis of exception propagation would associate with each procedure (which is why the compiler can check for completeness and complain if the programmer omits an exception that can be thrown).