Disclaimer: I am not an expert on the subject, this post is a collection of my reading notes from a bunch of papers. There may be factual errors and the content is subject to change. Just because I can.

In object-oriented languages, constructing a call graph is complicated by the presence of virtual method calls. This is a problem known as the dynamic dispatch problem, and is common in many programming languages and paradigms. The problem can be formulated as follows for Java: if m is a virtual method (i.e. not private or static), then the method that o.m() resolves to depends on the run-time type of o (as opposed to its declaration type). Determining the run-time type of o requires points-to information (what object may o point to?), which in turn requires a call graph to be computed (because what values o may point to depend on what methods get called). This mutual recursion is a fundamental problem, that is not quite trivial to tackle.

A number of static analyses have been proposed to do the job, but since the problem is undecidable no algorithm can return both a precise and correct answer. As a result, we have to decide if we want fast or precise analyses, since they can not be both. Some of the characteristics that affect the precision and cost of the algorithms are:

• flow sensitivity: does the order of statements matter?
• context sensitivity: how to distinguish between two calls of the same procedure in different contexts?
• aggregate structure modeling: how are arrays, lists, and hash tables abstracted?
• heap modeling: how to differentiate the potentially unbounded number of objects that may be created at a given allocation site?

Below are some notes about flow sensitivity and context sensitivity, followed by a discussion of some of the classic algorithms for call graph construction.

Flow sensitivity

• Flow-insensitive analyses are only concerned with what statements are present in the program, not with the order or the reachability of statements. They return properties of variables valid in the whole program.
• Flow-sensitive analyses compute what values may flow to variables by considering valid paths in the program. They return properties of variables valid at certain program points. Therefore, they are more precise but more expensive to compute.

Example (courtesy of smcc): a parity analysis for the following code snippet yields different results depending on the flow sensitivity of the analysis. A flow-insensitive analysis would return that x could be anything, while a flow-sensitive analysis would return that x is even at line 3 and odd at line 4.

void someMethod(int y) {
   int x;
   x = 2 * y;
   x = x + 1;
}

A common way to obtain a form of flow sensitivity is to transform the program in SSA form (thereby encoding control dependencies in variable names) and then to apply flow-insensitive analyses. Algorithms for efficient translation to SSA form are given in Appel, Modern Compiler Implementation in Java. For an implementation that transforms Java bytecode to SSA form, see Soot. In SSA form, the above example would become:

void someMethod(int y) {
    int x_1 = 2 * y;
    int x_2 = x_1 + 1;
}

A flow-insensitive analysis would then be sufficient to return that x_1 is even and x_2 is odd.
Although instances of the standard dataflow frameworks (Kildall, A Unified Approach to Global Program Optimization, POPL 1973) lend themselves particularly well to flow-sensitive analyses, Nielson et al. in Principles of Program Analysis give an example of a flow-insensitive instance, by simply considering empty kill sets in the dataflow equations (i.e., it loses information about which variables are overwritten).

Context sensitivity

Context sensitivity matters for inter-procedural analyses, where a single method may be invoked in different contexts. So, “what is a context?”, you may ask. Well, it is a parameter of the analysis, so the answer is “it depends”. The most common abstractions seem to be:

• call sites, so that the same method invoked from different line numbers would be distinct. However, if a method is invoked multiple times from the same program point (in a loop for example), then all these invocations would look exactly the same to the analysis, because they are all abstracted to come from the same place.
• receiver objects, so that the same method applied to two different (abstract) objects would be distinct. Objects are commonly abstracted by their allocation site (i.e., the place where they are new’ed). The same restriction as above applies, multiple allocations in a loop will be merged. The technique is described in Parameterized Object Sensitivity for Points-to Analysis for Java (ISSTA 2002, 129 citations) by Milanova, Rounev and Ryder.

Call site sensitivity example (from Lhoták’s PhD thesis): A context-insensitive points-to analysis would analyse id() once, and return that both c and d may point to b and a. A context-sensitive analysis using call sites as the context abstraction, on the other hand, would analyze id() in 2 different contexts and would properly return that c points to a and d points to b.

Object id(Object o) {
    return o;
}

void f() {
    Object a = new Object();
    Object b = new Object();
    Object c = id(a);
    Object d = id(b);
}

Object sensitivity example (from Chord’s PLDI tutorial): in the following example, we want to examine whether floors.elems and events.elems may point to the same elements. An object-insensitive points-to analysis would return that they could point to the same objects, because it does not distinguish between different instances of List. An object-sensitive analysis would abstract events and floors using two different allocation sites, and would maintain separate points-to information for evens.elems and floors.elems. Therefore, it would be able to determine that these two arrays have disjoint points-to sets.

class List {
	Object[] elems;

	List() {
		elems = new Object[42];
	}
}

class Bldg {
	List events, floors;

	Bldg() {
		this.events = new List();
		this.floors = new List();
		for (int i=0; i < events.elems.length; i++)
			events.elems[i] = new Object();
		for (int i=0; i < floors.elems.length; i++)
			floors.elems[i] = new Object();
	}
}

In each case (object sensitivity and call site sensitivity), we could get further precision by examining not only the last call site/receiver object, but the list of call sites/receiver objects that lead to the current context (i.e., the call stack is the context). In general, these lists may be infinite, so a common abstraction is to bound them by a parameter k. Hence, we refer to k-object-sensitivity or k-call-site-sensitivity. However, if m in the number of abstract context abstractions (allocation sites or call sites), there are m^k potential abstract contexts to consider. It quickly becomes impractical for values of k greater than 2 or 3.

The added precision of context-sensitivity depends on the client analysis. For instance, context-sensitivity does not add much to the precision of call graph construction and virtual method resolution. In Java, 1-object-sensitivity seems to provide the best tradeoff between performance and precision for most client analyses.

Algorithms

Example:

abstract class Animal {
	public abstract void saySomething();
}

class Cat extends Animal {
	public void saySomething() {
		System.out.println("purr");
	}
}

class Dog extends Animal {
	public void saySomething() {
		System.out.println("woof");
	}
}

class Fish extends Animal {
	public void saySomething() {
		System.out.println("...");
	}
}

class Car {  // not an Animal
	public void saySomething() {
		System.out.println("honk!");
	}
}

public class Main {
	static Animal neverCalled() {
		return new Fish();
	}

	static Animal selectAnimal() {
		return new Cat();
	}

	public static void main(String[] args) {
		Animal animal = selectAnimal();
		animal.saySomething();
	}
}

There are 4 methods called saySomething in this application, and the problem is to find which one(s) may be called at run-time (the correct answer is Cat.saySomething()). A dumb and incorrect analysis would just report that any method called saySomething could be invoked, including the one in the Car class. Many algorithms have been proposed to solve this problem, here are a few examples (they are all flow-insensitive, and n stands for the program size):

• CHA (Class Hierarchy Analysis)
• by Dean, Grove and Chambers in Optimization of object-oriented programs using static class hierarchy analysis (ECOOP 1995, 490 citations)
• complexity: O(n)?
• it does the only trivial thing to do: it first builds the class hierarchy (i.e., it figures that Cat, Fish and Dog are subclasses of Animal) and determines that saySomething() could be applied to any subclass of Animal, thereby eliminating Car.
• RTA (Rapid Type Analysis)
• by Bacon and Sweeney in Fast Static Analysis of C++ Virtual Function Calls (OOPSLA 1996, 387 citations)
• complexity: O(n)?
• simply put, it prunes from the CHA call graph methods that can never be reached because their enclosing class is never instantiated. In our example, it would determine that saySomething() could be applied to a Fish or a Cat but not a Dog, since no instance of Dog is ever created. It is strictly more powerful than CHA and still very fast and simple.
• VTA (Variable Type Analysis)
• by Sundaresan et al. in Practical Virtual Method Call Resolution for Java (OOPSLA 2000, 206 citations)
• complexity: O(n)?
• it can be thought of as a refined version of RTA. When RTA collects all objects that can be created in the whole program and uses that information to prune the call graph, VTA does this for each variable instead, providing more precise information. In our example, VTA would correctly determine that saySomething() can not be applied to a Fish, because there is no corresponding edge in the type propagation graph.
• k-CFA (Control Flow Analysis of order k):
• by Shivers in Control-flow analysis of higher-order languages (1991 PhD thesis, 476 citations)
• complexity: O(n³/log(n)) for 0CFA
• initially formulated for the functional language Scheme, it has apparently evolved to mean different things in the functional and OO communities (I am still looking for a simple formulation for OO languages though). In Resolving and Exploiting the k-CFA Paradox (PLDI 2010), it is described as a “k-call-site-sensitive, field-sensitive points-to analysis algorithm with a context-sensitive heap and with on-the-fly call-graph construction”. It seems that any analysis that uses k-call-strings as contexts could be called a k-CFA analysis.
• in the PLDI paper, Might et al. also note that “[in the OO setting] 1- and 2-CFA analysis is considered heavy but certainly possible”.
• in our example, 0CFA would return that saySomething() at line 40 has to be applied to a Cat, because only a Cat can flow to the animal variable.

• ZCWL
• by Zhu and Calman in Symbolic pointer analysis revisited (PLDI 2004, 69 citations) and Whaley and Lam in Cloning-based context-sensitive pointer alias analysis using binary decision diagrams (PLDI 2004, 327 citations)
• complexity: massive
• essentially a k-CFA analysis where k is the depth of the call graph (plus some fancy-schmancy operations on strongly connected components of the call graph). Requires a context-insensitive call-graph to boot, which it then makes context-sensitive.

Based on this simple example, we see that CHA and RTA return an imprecise call graph, while VTA, 0CFA and ZCWL return a precise call graph. VTA is by far the simplest and most efficient in our case, because we only want a rather coarse-grained call graph, not variable-level points-to information that k-CFA and ZCWL provide.

Further reading

• for a detailed discussion of the different sensitivities/abstractions: Lhoták, Program analysis using binary decision diagrams (PhD thesis, 2006)
• for a theoretical comparison of the relative precision of different algorithms: Grove et al., Call Graph Construction in Object-Oriented Languages (ACM SIGPLAN 1997, 209 citations)
• for an empirical comparison of the relative precision and performance of different algorithms: Lhoták and Hendren, Context-sensitive points-to analysis: is it worth it? (CC 2006, 75 citations)