Lesson 20.1 — Call-graph construction: direct calls, CHA, RTA, XTA/VTA and points-to¶

Techniques: direct call graphs (LLVM's CallGraph and LazyCallGraph); class hierarchy analysis, CHA (Dean, Grove & Chambers 1995); rapid type analysis, RTA (Bacon & Sweeney 1996); XTA (Tip & Palsberg 2000) and variable type analysis, VTA (Sundaresan et al. 2000); points-to-based call graphs (Andersen-style, Ch 19) · Pebble implements: print<pebble-callgraph> (exercise E1); CHA and RTA (★ XTA) in the comparison lab labs/ch20-callgraph · Drill: cha-rta · Prerequisites: DFS and SCCs (Ch 15), LLVM IR calls (Ch 9), points-to sets (Ch 19) · Time: 6–8 hours

Every interprocedural technique of this chapter stands on one data structure: the call graph, which says which functions each call site may invoke. For a direct call call @f the answer is written in the instruction. For an indirect call through a function pointer or a virtual call x.m() the compiler must compute it, and every algorithm of this lesson trades precision for cost in a different way. The running example is a small object-oriented program in the lab's class-hierarchy language (labs/ch20-callgraph/inputs/running.oo; the same program in Java is labs/ch20-callgraph/tools/soot/Main.java):

class Shape
class Circle extends Shape
class Square extends Shape
class Cube extends Square
global log: Shape

func main {                     func report {                 method Shape.area { }
  var s: Shape                    var r: Shape                method Shape.draw {
  var t: Shape                    var q: Shape                  s7: this.area()
  s = new Circle                  q = new Square              }
  s1: s.area()                    r = log                     method Circle.area { }
  log = s                         s3: r.draw()                method Square.area { }
  t = s                           s4: q.area()                method Square.draw { }
  s2: t.draw()                    choose {                    method Cube.area { }
  call report                       q = r                     method Cube.draw { }
}                                 } or {
                                    s5: q.draw()              func unused {
                                  }                             var u: Shape
                                }                               u = new Cube
                                                                s6: u.area()
                                                              }

x.m() runs the m of the receiver's run-time class, or of its nearest ancestor that defines one; choose { } or { } runs one of its branches; call f is a direct call. The hierarchy:

flowchart BT
  Circle[Circle: area] --> Shape[Shape: area, draw]
  Square[Square: area, draw] --> Shape
  Cube[Cube: area, draw] --> Square

1. Problem and motivation¶

A call graph has one node per function and an edge from call site \(c\) to every function \(c\) may invoke. Bottom-up traversal (Lesson 20.2), inlining (Lesson 20.3), interprocedural constant propagation (Lesson 20.5), attribute inference (Lesson 20.6) and devirtualization (Lesson 20.7) all read it. Two properties matter. A call graph is sound if it contains every edge some execution takes; an unsound graph makes the optimizer "prove" facts about callers it never looked at. It is precise if it contains few edges no execution takes; each spurious edge weakens every analysis that joins over callees and keeps dead code alive. Grove and Chambers organize all the algorithms below in one framework parameterized by how types and contexts are abstracted [GC01].

Direct call graphs¶

In C and in LLVM IR most calls name their callee. A direct call graph records exactly those edges and treats every indirect call, and every call into code outside the module, as a call to an unknown external node. That is what LLVM's CallGraph (the legacy structure that print-callgraph and scc_iterator use) and its successor LazyCallGraph (which drives the CGSCC pass manager, Lesson 20.2) do [LLVM-CG, LLVM-LCG]. The construction is exact for direct calls and pessimistic for everything else; it needs no whole-program assumption. print<pebble-callgraph> (exercise E1) builds it the way llvm::CallGraph does.

Class hierarchy analysis (CHA)¶

In object-oriented code almost every call is virtual, so a direct call graph knows nothing. Dean, Grove and Chambers observed that the static type of the receiver already bounds the targets: x.m() with x declared as T can only run an m that some subclass of T inherits or defines [DGC95]. CHA needs only the class hierarchy, the whole of it: a class defined in another module that overrides m adds a target. It is the basis of devirtualization in every C++ and Java compiler; LLVM encodes the hierarchy for it in type metadata (Lesson 20.7).

Rapid type analysis (RTA)¶

CHA counts every subclass, including those the program never instantiates. Bacon and Sweeney's RTA adds one fact: an object of class \(C\) can only receive a call if some reachable code executes new C [BS96]. Because "reachable" depends on the call graph and the call graph depends on the instantiated classes, RTA computes both together as a fixed point. It costs little more than CHA and resolved most virtual calls in their C++ benchmarks.

XTA and VTA¶

RTA keeps one global set of instantiated classes. Tip and Palsberg's XTA keeps one set per method (and per field), so a class instantiated in one part of the program does not pollute calls elsewhere [TP00]. Sundaresan et al.'s VTA goes further, to one set per variable, propagated along assignments in a type propagation graph [SHR+00]. Both are flow-insensitive: they ignore the order of statements.

Points-to-based call graphs¶

The most precise practical construction resolves an indirect call through the points-to set of its function pointer or receiver: the allocation sites (or functions, for function pointers) it may point to, computed by Andersen's or Steensgaard's analysis (Ch 19). Because points-to analysis itself needs the call graph to propagate through parameters, production analyses (Soot's Spark [LH03], Doop, SVF) build both on the fly. VTA is the special case where every allocation site of class \(C\) is merged into one abstract object "\(C\)".

2. Definitions and algorithms¶

Definition 20.1.1 (Program, call sites, executions)

A program is a finite set \(F\) of functions (for object-oriented programs: free functions and methods, called bodies) with an entry main, and a finite set \(\mathit{CS}\) of call sites. Each call site \(c\) lies in one body \(\mathrm{body}(c)\) and is direct (it names one callee \(\mathrm{callee}(c)\)) or indirect (a function-pointer call, or a virtual call \(x.m()\)). An execution is a finite run of the program from main; it takes the edge \((c, g)\) if at some point the call at \(c\) transfers control to \(g\). \(\mathrm{Dyn} \subseteq \mathit{CS} \times F\) is the set of edges taken by some execution.

Definition 20.1.2 (Call graph, soundness, precision order)

A call graph is a pair \(G = (R, T)\) of a set \(R \subseteq F\) of reachable bodies and a map \(T : \mathit{CS} \to \mathcal{P}(F)\) of targets, with \(T(c) = \emptyset\) whenever \(\mathrm{body}(c) \notin R\). \(G\) is sound if \((c, g) \in \mathrm{Dyn} \Rightarrow g \in T(c)\) and every body some execution enters is in \(R\). For two call graphs, \(G_1 \sqsubseteq G_2\) (\(G_1\) is at least as precise as \(G_2\)) iff \(R_1 \subseteq R_2\) and \(T_1(c) \subseteq T_2(c)\) for every \(c\). The number of edges is \(\lvert G \rvert = \sum_{c} \lvert T(c) \rvert\).

Soundness and precision on the running example

\(\mathrm{Dyn}\) at s4 is \(\{\mathtt{Square.area}\}\): q holds a Square when s4 runs, in every execution. A call graph with \(T(\mathtt{s4}) = \{\mathtt{Circle.area}\}\) is unsound; one with \(T(\mathtt{s4}) = \{\mathtt{Circle.area}, \mathtt{Square.area}\}\) is sound but has one spurious edge.

Algorithm 20.1.3 (Direct call graph, LLVM style)

Input: a module: functions in module order, each defined or declared, each with or without local (internal) linkage.
Output: nodes = the functions plus two pseudo-nodes, the external calling node \(\mathit{ext}_{in}\) and the calls-external node \(\mathit{ext}_{out}\); one edge per call site.
Precondition: none (no whole-program assumption).
Postcondition: every direct call \(c\) in \(f\) gives the edge \(f \to \mathrm{callee}(c)\); every indirect call gives \(f \to \mathit{ext}_{out}\); \(\mathit{ext}_{in} \to f\) for every \(f\) that code outside the module may call.
Invariant: after processing the first \(k\) functions, their out-edges are exactly as in the postcondition.

function DirectCallGraph(M):
    for f in functions(M), in module order:
        if not hasLocalLinkage(f) or addressTaken(f):
            addEdge(ext_in, f)                    # anything outside may call f
        if isDeclaration(f) and not f.nocallback:
            addEdge(f, ext_out)                   # its body may call anything
        for each call instruction c in f, in order:
            if c is direct: addEdge(f, callee(c))
            else:           addEdge(f, ext_out)

Definition 20.1.4 (Class hierarchy, dispatch)

A class hierarchy is a finite forest \((\mathcal{C}, \mathrm{parent})\); \(C \preceq D\) (\(C\) is a subclass of \(D\)) is its reflexive-transitive closure, and \(\mathrm{sub}(D) \triangleq \{\, C \in \mathcal{C} \mid C \preceq D \,\}\). Each class defines some methods \(C.m\). Dispatch is \(\mathrm{lookup}(C, m) = C.m\) if \(C\) defines \(m\), else \(\mathrm{lookup}(\mathrm{parent}(C), m)\) (undefined at a root without \(m\)). Every variable \(x\) has a declared type \(\mathrm{decl}(x) \in \mathcal{C}\) (for this in \(C.m\): \(C\)); the program is type-correct: x = new C only if \(C \preceq \mathrm{decl}(x)\), x = y only if \(\mathrm{decl}(y) \preceq \mathrm{decl}(x)\).

Algorithm 20.1.5 (Class hierarchy analysis, CHA)

Input: a type-correct program (Definitions 20.1.1, 20.1.4).
Output: a call graph \(G_{\mathrm{CHA}} = (R, T)\).
Precondition: the whole class hierarchy is known (closed world).
Postcondition: \(R\) is the least set containing main and closed under the targets of its call sites; \(T(c) = \{\, \mathrm{lookup}(C, m) \mid C \in \mathrm{sub}(\mathrm{decl}(x)) \,\}\) for every virtual \(c : x.m()\) in a body of \(R\).
Invariant: every body on the worklist or in \(R\) is reachable in \(G_{\mathrm{CHA}}\); \(T(c)\) is final once \(\mathrm{body}(c)\) is processed.

function CHA(P):
    R ← {main};  W ← [main]
    while W ≠ []:
        b ← pop W
        for each call site c in b:
            if c is direct: new ← {callee(c)}
            else (c is x.m()):
                T(c) ← { lookup(C, m) : C ∈ sub(decl(x)), lookup(C, m) defined }
                new ← T(c)
            for g in new, g ∉ R: R ← R ∪ {g}; push g on W
    return (R, T)

Algorithm 20.1.6 (Rapid type analysis, RTA)

Input: a type-correct program.
Output: a call graph \(G_{\mathrm{RTA}} = (R, T)\) and the set \(\mathit{Inst}\) of instantiated classes.
Precondition: closed world; every object is created by a new in the program.
Postcondition: \((R, \mathit{Inst}, T)\) is the least solution of: \(\mathtt{main} \in R\); new C in a body of \(R\) gives \(C \in \mathit{Inst}\); for \(c : x.m()\) in a body of \(R\), \(T(c) = \{\, \mathrm{lookup}(C, m) \mid C \in \mathrm{sub}(\mathrm{decl}(x)) \cap \mathit{Inst} \,\}\); direct callees and all targets of reachable sites are in \(R\).
Invariant: \(R\), \(\mathit{Inst}\) and every \(T(c)\) only grow, and stay below the least solution.

function RTA(P):
    R ← {main};  Inst ← ∅;  T(c) ← ∅ for all c
    repeat
        changed ← false
        for each body b ∈ R (as R was when the round started), in textual order:
            for each statement s of b:
                if s is x = new C and C ∉ Inst:  Inst ← Inst ∪ {C}; changed ← true
                if s is call f and f ∉ R:        R ← R ∪ {f}; changed ← true
                if s is c: x.m():
                    for C ∈ sub(decl(x)) ∩ Inst:
                        g ← lookup(C, m)
                        if g ∉ T(c): T(c) ← T(c) ∪ {g}; changed ← true
                        if g ∉ R:    R ← R ∪ {g};    changed ← true
    until not changed
    return (R, T, Inst)

Definition 20.1.7 (XTA sets)

XTA keeps a set \(S_b \subseteq \mathcal{C}\) for every body \(b\) and \(S_g\) for every global (field) \(g\). Its constraints, for each body \(b \in R\):

x = new C in \(b\): \(C \in S_b\), and \(C \in S_g\) if \(x\) is the global \(g\);
g = x (\(x\) not global): \(S_b \cap \mathrm{sub}(\mathrm{decl}(g)) \subseteq S_g\); x = g: \(S_g \cap \mathrm{sub}(\mathrm{decl}(x)) \subseteq S_b\); a receiver \(g\) in g.m() is read like x = g;
\(c : x.m()\) in \(b\): for each \(C \in S_b \cap \mathrm{sub}(\mathrm{decl}(x))\), the target \(t = \mathrm{lookup}(C, m)\) is in \(T(c)\) and in \(R\), and \(C \in S_t\) (the receiver flows into this);
direct calls make their callee reachable.

XTA is the least \((R, T, S)\) satisfying them.

Algorithm 20.1.8 (XTA, round-robin)

Input: a type-correct program.
Output: the least solution \((R, T, S)\) of Definition 20.1.7.
Precondition: closed world; objects only flow through assignments, globals and receivers (the lab language has no parameters or return values; Tip–Palsberg also propagate along them, in the same way).
Postcondition: as Definition 20.1.7.
Invariant: all sets only grow and stay below the least solution.

function XTA(P):
    R ← {main};  S_b ← ∅, S_g ← ∅, T(c) ← ∅ for all b, g, c
    repeat
        changed ← false
        for each body b ∈ R, each statement s of b:
            apply the constraint of s (Definition 20.1.7, rules 1–4), adding what is missing;
            changed ← true if anything was added
    until not changed
    return (R, T, S)

Definition 20.1.9 (VTA: type propagation graph)

VTA has one node per variable: each local (and this) of each body, and each global. Its sets \(V(n) \subseteq \mathcal{C}\) are the least solution of: x = new C gives \(C \in V(x)\); x = y gives \(V(y) \subseteq V(x)\) (an edge \(y \to x\)); for \(c : x.m()\) in a reachable body and \(C \in V(x)\) with \(t = \mathrm{lookup}(C, m)\): \(t \in T(c)\), \(t \in R\) and \(C \in V(\mathtt{this}_t)\). Sundaresan et al. build the graph from an initial CHA or RTA call graph and then prune [SHR+00]; the on-the-fly version here adds call edges only as receivers acquire types.

Algorithm 20.1.10 (VTA, on the fly)

Input: a type-correct program.
Output: the least \((R, T, V)\) of Definition 20.1.9.
Precondition: closed world.
Postcondition: as Definition 20.1.9.
Invariant: every \(V(n)\) only grows and stays below the least solution.

function VTA(P):
    R ← {main};  V(n) ← ∅, T(c) ← ∅
    repeat
        changed ← false
        for each body b ∈ R, each statement s of b:
            if s is x = new C:  add C to V(x)
            if s is x = y:      add V(y) to V(x)
            if s is call f:     add f to R
            if s is c: x.m():
                for C ∈ V(x):  t ← lookup(C, m); add t to T(c) and R; add C to V(this_t)
            changed ← true if anything was added
    until not changed
    return (R, T, V)

Definition 20.1.11 (Points-to-based resolution)

Given a points-to relation \(\mathrm{pts} : \mathit{Var} \to \mathcal{P}(\mathit{Obj})\) (Ch 19, Andersen's inclusion constraints) whose abstract objects are allocation sites \(o\) with a class \(\mathrm{cls}(o)\), or functions (for function pointers), the targets of \(c : x.m()\) are \(\{\, \mathrm{lookup}(\mathrm{cls}(o), m) \mid o \in \mathrm{pts}(x) \,\}\), and of an indirect call through \(p\) the functions in \(\mathrm{pts}(p)\). On-the-fly construction adds the parameter and return constraints of a call edge only when the edge is discovered, so both the points-to sets and the call graph are the least solution of one system.

3. Worked example¶

The running example, analysis by analysis; ./course drill cha-rta --seed 2 --difficulty hard --solution prints the same kind of trace for a random program, and ch20-cg --algo cha|rta|xta labs/ch20-callgraph/inputs/running.oo (the lab tool) must print the final rows.

Direct call graphs¶

The only direct call is call report in main. A direct call graph has the edge main → report, and every virtual call site goes to the unknown node: s1, s2 (in main), s3, s4, s5 (in report) and s7 all call "anything". Useless for this program: exactly the problem the other four techniques address.

Class hierarchy analysis (CHA)¶

\(\mathrm{sub}(\mathtt{Shape}) = \{\mathtt{Shape}, \mathtt{Circle}, \mathtt{Square}, \mathtt{Cube}\}\) and every receiver is declared Shape, so every area site gets \(\mathrm{lookup}(\cdot, \mathtt{area})\) of all four classes and every draw site gets Shape.draw (for Shape and Circle), Square.draw and Cube.draw. Worklist order (Algorithm 20.1.5):

step	body popped (FIFO)	site	targets	newly reachable, pushed
1	main	s1	Circle.area, Cube.area, Shape.area, Square.area	the same four
1	main	s2	Cube.draw, Shape.draw, Square.draw	the same three
1	main	call report	report	report
2–5	Circle.area, Cube.area, Shape.area, Square.area	—	—	—
6	Cube.draw	—	—	—
7	Shape.draw	s7	Circle.area, Cube.area, Shape.area, Square.area	—
8	Square.draw	—	—	—
9	report	s3, s5 / s4	the three `draw` / the four `area` methods	—

The worklist is empty after step 9. \(\lvert G_{\mathrm{CHA}} \rvert = 4 + 3 + 3 + 4 + 3 + 4 = 21\) edges; unused (and so s6) is not reachable, but Cube.area and Cube.draw are, although no Cube is ever created by reachable code.

Rapid type analysis (RTA)¶

Rounds of Algorithm 20.1.6; each round visits, in textual order, the bodies that were reachable when the round started:

round	bodies visited	Inst after	R after (new in bold)	targets changed
1	main	{Circle}	main, report, Shape.draw, Circle.area	s1 → {Circle.area}; s2 → {Shape.draw}
2	main, report, Shape.draw, Circle.area	{Circle, Square}	…, Square.area, Square.draw	s3, s5 → {Shape.draw, Square.draw}; s4, s7 → {Circle.area, Square.area}
3	the six reachable bodies	{Circle, Square}	(same)	s1 += Square.area; s2 += Square.draw
4	the six reachable bodies	{Circle, Square}	(same)	none: fixed point

Round 1: only main was reachable at the start; it instantiates Circle, so s1 and s2 see only Circle.
Round 2: report instantiates Square, which reaches every site visited after it.
Round 3: main's sites are revisited with the larger \(\mathit{Inst}\) — RTA's answer does not depend on which body comes first, only the number of rounds does.

Final targets: s1, s4, s7 → {Circle.area, Square.area}; s2, s3, s5 → {Shape.draw, Square.draw}: 12 edges. Cube is never instantiated by reachable code, so neither Cube method is reachable, and Shape.area is unreachable because both instantiated classes override area.

XTA and VTA¶

XTA (Algorithm 20.1.8, same round order as RTA), the sets after each round (@log is the global; empty sets not shown):

round	S_main	@log	S_Circle.area	S_Shape.draw	S_report	S_Square.area	S_Square.draw
1	{Circle}	{Circle}	{Circle}	{Circle}	{}	—	—
2	{Circle}	{Circle}	{Circle}	{Circle}	{Circle, Square}	{Square}	{Square}
3	(no change)

Round 1: main creates a Circle (rule 1), copies it into @log (rule 2), and dispatches s1 and s2 on it, which puts Circle into the sets of Circle.area and Shape.draw (rule 3); s7 in Shape.draw then calls Circle.area.
Round 2: report creates a Square and reads @log, so its set is {Circle, Square}; its sites dispatch on both. A Square receiver goes to Square.area/Square.draw, a Circle to Circle.area/Shape.draw.

The per-body sets separate main, which only ever sees Circle, from report: s1 → {Circle.area}, s2 → {Shape.draw} and s7 → {Circle.area} (only a Circle ever reaches Shape.draw), while report's sites keep both classes. 9 edges.

VTA (Algorithm 20.1.10) tracks each variable: \(V(s) = V(t) = V(\mathtt{log}) = V(r) = \{\mathtt{Circle}\}\), \(V(q) = \{\mathtt{Square}, \mathtt{Circle}\}\) (through q = r, flow-insensitively). So s3 → {Shape.draw}, but s4 → {Circle.area, Square.area} and s5 → {Shape.draw, Square.draw}: 8 edges.

Points-to-based call graphs¶

With one abstract object per new (allocation site) the points-to sets of this program coincide with VTA's type sets (each class is allocated at one site), so an Andersen-based graph also has 8 edges. The dynamic call graph (\(\mathrm{Dyn}\), computed by ipo.dynamic, a collecting interpreter that runs both choose branches) has 6: s4 only ever calls Square.area and s5 only Square.draw, because q = r and s5 are in different branches — a fact only a flow-sensitive analysis sees.

site	CHA	RTA	XTA	VTA	dynamic
s1	4	2	1	1	1
s2	3	2	1	1	1
s3	3	2	2	1	1
s4	4	2	2	2	1
s5	3	2	2	2	1
s7	4	2	1	1	1
total	21	12	9	8	6

Try it

./course drill cha-rta --seed 2 --difficulty hard --solution (CHA, RTA and XTA of a random program, with the round tables); ./course drill cha-rta --difficulty easy for CHA alone.

4. Invariants and correctness¶

Lemma 20.1.12 (Type correctness at run time)

In every execution of a type-correct program, whenever a variable \(x\) holds an object of run-time class \(C\), \(C \preceq \mathrm{decl}(x)\); and this in \(D.m\) always holds an object whose class \(C\) satisfies \(C \preceq D\) and \(\mathrm{lookup}(C, m) = D.m\).

Proof

By induction on the number of executed statements. Initially no variable holds an object. x = new C stores class \(C\) with \(C \preceq \mathrm{decl}(x)\) by type correctness. x = y stores what \(y\) holds, whose class \(C \preceq \mathrm{decl}(y) \preceq \mathrm{decl}(x)\) by the induction hypothesis and transitivity. A call \(x.m()\) on an object of class \(C\) runs \(D.m = \mathrm{lookup}(C, m)\), which by Definition 20.1.4 is a definition in \(C\) or an ancestor, so \(C \preceq D\); that object becomes this. No other statement stores.

Theorem 20.1.13 (CHA and RTA are sound)

For a type-correct closed-world program, \(G_{\mathrm{CHA}}\) and \(G_{\mathrm{RTA}}\) are sound (Definition 20.1.2).

Proof

CHA. Take an execution and its \(k\)-th call, by induction on \(k\) show that the body executing it is in \(R_{\mathrm{CHA}}\) and the edge taken is in \(T_{\mathrm{CHA}}\). main \(\in R\). Suppose the call at \(c : x.m()\) in body \(b\) runs; \(b \in R\) by the hypothesis (every body is entered through an earlier call or is main). The receiver has some class \(C\), and \(C \preceq \mathrm{decl}(x)\) by Lemma 20.1.12, i.e. \(C \in \mathrm{sub}(\mathrm{decl}(x))\); the target is \(\mathrm{lookup}(C, m)\), which Algorithm 20.1.5 put into \(T(c)\) and into \(R\). Direct calls are the same with the named callee.

RTA. Add to the induction: every object created so far has a class in \(\mathit{Inst}\). An object of class \(C\) is created by new C in a body that ran, hence (hypothesis) is in \(R\), hence \(C \in \mathit{Inst}\) by the postcondition. At a call, the receiver's class \(C\) is in \(\mathrm{sub}(\mathrm{decl}(x)) \cap \mathit{Inst}\), so \(\mathrm{lookup}(C, m) \in T_{\mathrm{RTA}}(c)\) and is reachable.

Theorem 20.1.14 (Precision chain)

For every type-correct program of the lab language, \(\mathrm{Dyn} \sqsubseteq G_{\mathrm{VTA}} \sqsubseteq G_{\mathrm{XTA}} \sqsubseteq G_{\mathrm{RTA}} \sqsubseteq G_{\mathrm{CHA}}\) (reading \(\mathrm{Dyn}\) as a call graph), and all four are sound. The inclusions can be strict (the running example: 6 < 8 < 9 < 12 < 21 edges).

Proof

Each analysis is a least solution of a monotone system (Definitions 20.1.7, 20.1.9 and the postconditions of Algorithms 20.1.5–20.1.6), so to show \(A \sqsubseteq B\) it suffices to exhibit a solution of \(A\)'s system inside \(B\)'s solution: the least solution of \(A\) is below every solution.

RTA ⊑ CHA. \((R_{\mathrm{CHA}}, T_{\mathrm{CHA}}, \mathcal{C})\) satisfies RTA's constraints: with \(\mathit{Inst} = \mathcal{C}\) the RTA target rule is the CHA rule. Hence the least RTA solution is below it.

XTA ⊑ RTA. Take RTA's \((R, T, \mathit{Inst})\) and set \(S_b = S_g = \mathit{Inst}\) for all bodies and globals. Rule 1 holds (\(C\) is instantiated in a reachable body, so \(C \in \mathit{Inst}\)), rule 2 holds (all sets equal and intersections only shrink), rule 3 holds: for \(C \in \mathit{Inst} \cap \mathrm{sub}(\mathrm{decl}(x))\) the target is in \(T(c)\) and \(R\) by RTA's rule, and \(C \in S_t = \mathit{Inst}\). So this is an XTA solution; the least one is below.

VTA ⊑ XTA. First, in XTA's least solution \(S_g \subseteq \mathrm{sub}(\mathrm{decl}(g))\) for every global \(g\): a class enters \(S_g\) only by rule 1 (g = new C, and \(C \preceq \mathrm{decl}(g)\) by type correctness) or by rule 2 (filtered by \(\mathrm{sub}(\mathrm{decl}(g))\)); induction on the iteration. Now set \(V(n) = S_b \cap \mathrm{sub}(\mathrm{decl}(n))\) for a local or this \(n\) of body \(b\), and \(V(g) = S_g\), and check Definition 20.1.9's rules. x = new C in \(b\): \(C \in S_b\) and \(C \preceq \mathrm{decl}(x)\), so \(C \in V(x)\); for a global \(x\), rule 1 puts \(C \in S_x = V(x)\). x = y, both non-global: \(V(y) \subseteq S_b \cap \mathrm{sub}(\mathrm{decl}(y)) \subseteq S_b \cap \mathrm{sub}(\mathrm{decl}(x)) = V(x)\), since \(\mathrm{decl}(y) \preceq \mathrm{decl}(x)\). g = y: XTA's rule 2 gives \(V(y) \subseteq S_b \cap \mathrm{sub}(\mathrm{decl}(g)) \subseteq S_g\). x = g: \(S_g \subseteq \mathrm{sub}(\mathrm{decl}(g)) \subseteq \mathrm{sub}(\mathrm{decl}(x))\), so rule 2's filter keeps all of \(S_g\) and puts it into \(S_b\); hence \(V(g) \subseteq S_b \cap \mathrm{sub}(\mathrm{decl}(x)) = V(x)\) (two globals: the same argument on \(S\)). A call \(c : x.m()\) in \(b\) with \(C \in V(x)\): then \(C \in S_b \cap \mathrm{sub}(\mathrm{decl}(x))\) (for a global receiver, rule 2's read copies \(C\) into \(S_b\)), so XTA's rule 3 put \(t = \mathrm{lookup}(C, m)\) into \(T(c)\) and \(R\) and \(C\) into \(S_t\); since dispatch found \(t\) in \(C\) or an ancestor, \(C \preceq \mathrm{cls}(t) = \mathrm{decl}(\mathtt{this}_t)\) and \(C \in V(\mathtt{this}_t)\). So this \(V\) with XTA's \(R\) and \(T\) satisfies VTA's system, and VTA's least solution is below it.

Dyn ⊑ VTA. The induction of Theorem 20.1.13, with the invariant "every value a variable \(n\) holds has a class in \(V(n)\)", which new, copies and receiver binding preserve by the three VTA rules.

Soundness of XTA and VTA follows: they contain \(\mathrm{Dyn}\). Strictness: the table of §3.

Closed world is a precondition, not a detail

Theorem 20.1.13 needs the whole hierarchy and every new. A shared library that later loads a new subclass of Shape, reflection (Class.forName), or a C++ class defined in another translation unit adds targets CHA never saw. Compilers therefore run CHA-based devirtualization only when they can prove the closed world — LLVM with -fwhole-program-vtables under LTO and hidden visibility (Lesson 20.7), Java JITs with class-hierarchy dependencies that deoptimize when a new class loads.

Theorem 20.1.15 (Direct call graphs are sound)

Algorithm 20.1.3's graph, reading \(\mathit{ext}_{out}\) as "any function", is sound for any execution of any program that contains the module.

Proof

A call from a module function \(f\) either names its callee (edge \(f \to \mathrm{callee}(c)\) is added) or is indirect (edge to \(\mathit{ext}_{out}\), which stands for every function). A call into \(f\) from outside the module is possible only if \(f\) is visible (not local) or its address escapes; both add \(\mathit{ext}_{in} \to f\). A declaration's body is unknown, so it may call anything (edge to \(\mathit{ext}_{out}\)), unless it is marked nocallback, which by definition promises it never calls back into the module.

5. Complexity¶

Let \(B\) = bodies, \(S\) = call sites and statements, \(\lvert\mathcal{C}\rvert\) = classes, \(h\) = hierarchy height, \(V\) = variables.

Technique	Time (worst)	Time (typical)	Space	Justification
Direct call graph	\(O(S)\)	linear	\(O(S)\)	one pass over the instructions (Algorithm 20.1.3)
CHA	\(O(S \cdot \lvert\mathcal{C}\rvert \cdot h)\)	near-linear: \(\mathrm{sub}\) and dispatch tables precomputed	\(O(S \cdot \lvert\mathcal{C}\rvert)\) edges	each site is resolved once, over at most \(\lvert\mathcal{C}\rvert\) subclasses, each lookup climbs \(\le h\) parents
RTA	\(O(\lvert\mathcal{C}\rvert \cdot B \cdot S \cdot \lvert\mathcal{C}\rvert h)\) round-robin; \(O(S \cdot \lvert\mathcal{C}\rvert h)\) with a worklist	~CHA	\(O(S \cdot \lvert\mathcal{C}\rvert)\)	\(\mathit{Inst}\) and \(R\) grow at most \(\lvert\mathcal{C}\rvert + B\) times; a worklist re-resolves a site only when a new class enters \(\mathit{Inst}\)
XTA	\(O((B + G) \cdot \lvert\mathcal{C}\rvert \cdot S)\)	2–5 rounds	\(O((B + G)\lvert\mathcal{C}\rvert)\)	each of the \(B + G\) sets grows at most \(\lvert\mathcal{C}\rvert\) times; each growth re-examines its body's statements
VTA	\(O(V \cdot \lvert\mathcal{C}\rvert \cdot E)\), \(E\) = graph edges	near-linear after SCC collapsing	\(O(V \lvert\mathcal{C}\rvert)\)	subset propagation: each set grows at most \(\lvert\mathcal{C}\rvert\) times along each edge
Points-to (Andersen)	\(O(V^3)\)	quadratic-ish with cycle elimination (Ch 19)	\(O(V \cdot \mathit{Obj})\)	dynamic transitive closure

Pathological family. Let \(P_n\) have one root class \(A\) with \(n\) subclasses \(D_1, \dots, D_n\), each overriding \(m\), one x = new D_1 in main, and \(n\) call sites x.m() with \(x\) declared \(A\). The program has \(\Theta(n)\) statements. CHA gives every site all \(n + 1\) targets: \(\Theta(n^2)\) edges. RTA gives each site one target (\(\mathit{Inst} = \{D_1\}\)): \(n\) edges. Add to \(P_n\) one reachable function that executes new D_k for every \(k\) (say, a factory used elsewhere): RTA's single global set makes it exactly as bad as CHA again, \(\Theta(n^2)\), while XTA's per-body sets keep the sites in main at one target — the case XTA was designed for [TP00].

At scale. On the lab's 400 random programs (test_ch20.CallGraphs), the five constructions of §3 produce 5 649, 4 869, 4 048, 3 211 and 759 call edges (CHA, RTA, XTA, VTA, dynamic); on the Java running example Soot gives 24, 15, 11 and 9 edges for CHA, RTA, VTA and Spark (the boxes of §7). Published evaluations on real programs report the same ordering with much larger gaps between CHA and the points-to-based graphs [BS96, TP00, GC01].

Declared-type analysis (DTA) [SHR+00]: VTA with one node per declared type instead of per variable — cheaper, between XTA and VTA in precision.
CTA, MTA, FTA [TP00]: the other points of Tip and Palsberg's design space — one set per class, per method-and-field, per field — each trading set count against precision.
Context-sensitive call graphs: \(k\)-CFA and object sensitivity (Ch 19, Lesson on sensitivity) give per-context targets; Grove and Chambers compare them all in one framework [GC01]. Trade-off: precision grows with \(k\), cost exponentially in the worst case.
On-the-fly vs ahead-of-time: building the call graph during points-to analysis [LH03] is more precise than starting from a CHA graph, at the price of a single, harder-to-parallelize fixed point.
Open world: for libraries, treat every externally visible method as an entry and every non-final class as extensible (LLVM's vcall_visibility metadata, Lesson 20.7).
Soundiness: practical Java and JavaScript call graphs deliberately ignore parts of reflection and eval and document it; the result is sound only for programs that avoid them.

7. In real compilers¶

Direct call graphs¶

LLVM: llvm/lib/Analysis/CallGraph.cpp — CallGraph::addToCallGraph and CallGraph::populateCallGraphNode are Algorithm 20.1.3 almost line by line (the hasAddressTaken test ignores callback and assume-like uses) [LLVM-CG]; llvm/lib/Analysis/LazyCallGraph.cpp builds the graph the new pass manager uses, adding ref edges for every function a function merely references (e.g. stores into a table) [LLVM-LCG]. GCC's cgraph_node/cgraph_edge (the "callgraph", cgraph.cc) keeps both direct and indirect edges and refines indirect ones as it learns (see Lesson 20.7).

LLVM's direct call graph and its two external nodes

Reproduce (clang 23.1.2, opt 23.1.2):

cat > cg.c <<'EOF'
static int leaf(int x) { return x * 2; }
static int odd(int n);
static int even(int n) { return n == 0 ? 1 : odd(n - 1); }
static int odd(int n) { return n == 0 ? 0 : even(n - 1); }
int (*fp)(int) = leaf;
int api(int n) { return even(n) + leaf(n) + fp(n); }
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm cg.c -o cg.ll
opt -passes=print-callgraph -disable-output cg.ll

Output (the node addresses differ from run to run):

Call graph node <<null function>><<0x562f6aea7600>>  #uses=0
  CS<None> calls function 'leaf'
  CS<None> calls function 'api'

Call graph node for function: 'api'<<0x562f6aea7770>>  #uses=1
  CS<0x562f6ae38700> calls function 'even'
  CS<0x562f6ae91140> calls function 'leaf'
  CS<0x562f6ae91380> calls external node

Call graph node for function: 'even'<<0x562f6aea77f0>>  #uses=2
  CS<0x562f6ae92230> calls function 'odd'

Call graph node for function: 'leaf'<<0x562f6aea76c0>>  #uses=2

Call graph node for function: 'odd'<<0x562f6aea7d90>>  #uses=1
  CS<0x562f6ae92e00> calls function 'even'

What to notice: the <<null function>> node is \(\mathit{ext}_{in}\) of Algorithm 20.1.3: it calls api (external linkage) and leaf (static, but its address is stored in fp), not even or odd. The indirect call fp(n) "calls external node" (\(\mathit{ext}_{out}\)), so the graph stays sound (Theorem 20.1.15) without knowing that fp only ever holds leaf.

Class hierarchy analysis (CHA)¶

Clang emits the hierarchy for LLVM as type metadata: every vtable carries !type entries naming each class it is compatible with, and every virtual call is guarded by llvm.type.test on the vtable pointer, so "the vtables with !type !"_ZTS5Shape"" is exactly \(\mathrm{sub}(\mathtt{Shape})\) [LLVM-TypeMetadata]; llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp resolves calls from it (Lesson 20.7). GCC's ipa-devirt.cc builds a type inheritance graph and possible_polymorphic_call_targets returns CHA-style target lists [GCC-Devirt]. Soot's soot.jimple.toolkits.callgraph.CHATransformer is textbook CHA [Soot].

Soot's CHA on the running example in Java

Reproduce (Soot 4.6.0 from Maven Central, OpenJDK 21.0.10; Main.java and the small driver CG.java are in labs/ch20-callgraph/tools/soot/):

curl -sSfLO https://repo1.maven.org/maven2/org/soot-oss/soot/4.6.0/soot-4.6.0-jar-with-dependencies.jar
mkdir -p ex && cp labs/ch20-callgraph/tools/soot/Main.java labs/ch20-callgraph/tools/soot/CG.java .
javac -d ex --release 8 -Xlint:-options Main.java
javac -cp soot-4.6.0-jar-with-dependencies.jar CG.java
java -cp soot-4.6.0-jar-with-dependencies.jar:. CG cha ex 2>/dev/null

Output:

draw   line  1 -> Circle.area Cube.area Shape.area Square.area
main   line 11 -> Main.circle
main   line 12 -> Circle.area Cube.area Shape.area Square.area
main   line 15 -> Cube.draw Shape.draw Square.draw
main   line 16 -> Main.report
report line 19 -> Main.square
report line 21 -> Cube.draw Shape.draw Square.draw
report line 22 -> Circle.area Cube.area Shape.area Square.area
report line 23 -> Cube.draw Shape.draw Square.draw
edges into application methods: 24

What to notice: lines 12, 15, 21, 22, 23 and 1 are s1, s2, s3, s4, s5 and s7; their targets are exactly the CHA column of §3 (21 virtual edges; the 3 extra edges are the static calls to circle, square and report, which the Java version uses to create the objects). Cube methods are targets although no reachable code creates a Cube.

Rapid type analysis (RTA)¶

GCC applies the RTA idea inside CHA: type_possibly_instantiated_p in ipa-devirt.cc drops a type whose vtable is never referenced from live code (no constructor ran), so its methods are not polymorphic targets [GCC-Devirt]. Soot implements RTA as Spark with rta:true (one abstract object per class, a CHA-built call graph) [Soot]. LLVM has no RTA pass: whole-program devirtualization reasons about the vtables that exist in the linked program, which removes never-emitted classes in a similar way.

Soot's RTA on the same program

Reproduce (Soot 4.6.0, OpenJDK 21.0.10; after the setup of the CHA box):

java -cp soot-4.6.0-jar-with-dependencies.jar:. CG rta ex 2>/dev/null

Output:

draw   line  1 -> Circle.area Square.area
main   line 11 -> Main.circle
main   line 12 -> Circle.area Square.area
main   line 15 -> Shape.draw Square.draw
main   line 16 -> Main.report
report line 19 -> Main.square
report line 21 -> Shape.draw Square.draw
report line 22 -> Circle.area Square.area
report line 23 -> Shape.draw Square.draw
edges into application methods: 15

What to notice: 12 virtual edges, the RTA column of §3: Cube is only created in unused, which is unreachable, so Cube.area and Cube.draw disappear; Shape.area disappears too, because the only instantiated classes (Circle, Square) both override area.

XTA and VTA¶

Soot's vta:true option runs Spark as a VTA emulation (field-based, one abstract object per type, a call graph computed ahead of time) [Soot, SHR+00]; OPAL and the WALA framework offer XTA-style propagation. In C++ compilers the closest relative is GCC's polymorphic call context (ipa-polymorphic-call.cc), which tracks the dynamic type of an object from its construction through assignments and parameters — flow-sensitive type propagation — before looking up targets [GCC-PolyCall].

Soot's VTA emulation

Reproduce (Soot 4.6.0, OpenJDK 21.0.10; after the setup of the CHA box):

java -cp soot-4.6.0-jar-with-dependencies.jar:. CG vta ex 2>/dev/null
java -cp soot-4.6.0-jar-with-dependencies.jar:. CG spark ex field-based:true on-fly-cg:false 2>/dev/null | grep 'line 21'
java -cp soot-4.6.0-jar-with-dependencies.jar:. CG spark ex field-based:true on-fly-cg:false simplify-sccs:true 2>/dev/null | grep 'line 21'

Output:

draw   line  1 -> Circle.area Square.area
main   line 11 -> Main.circle
main   line 12 -> Circle.area
main   line 15 -> Shape.draw
main   line 16 -> Main.report
report line 19 -> Main.square
report line 21 -> Shape.draw Square.draw
report line 22 -> Square.area
report line 23 -> Square.draw
edges into application methods: 11
report line 21 -> Shape.draw
report line 21 -> Shape.draw Square.draw

What to notice: per-variable sets separate s (only Circle) from q: s1 and s2 get one target, as in §3. Soot is more precise than the lesson's VTA at s4/s5 (lines 22–23) because Jimple splits the variable q into one local per definition (a flow-sensitivity SSA gives for free), and less precise at s3 (line 21) and s7 (line 1): the last two commands show that the extra target comes from simplify-sccs, which merges each cycle of the assignment graph into one node — speed bought with precision (§6).

Points-to-based call graphs¶

Soot's default call graph is Spark's on-the-fly Andersen analysis [LH03]; Doop and SVF do the same for Java and LLVM IR. LLVM itself resolves indirect calls from value information rather than a points-to analysis: IPSCCP and function specialization (Lessons 20.4–20.5) turn a call through a pointer that is a known constant into a direct call, and the Attributor's call-edge analysis uses its potential-values reasoning [LLVM-FuncSpec].

Soot's Spark (on-the-fly points-to) call graph

Reproduce (Soot 4.6.0, OpenJDK 21.0.10; after the setup of the CHA box):

java -cp soot-4.6.0-jar-with-dependencies.jar:. CG spark ex 2>/dev/null

Output:

draw   line  1 -> Circle.area
main   line 11 -> Main.circle
main   line 12 -> Circle.area
main   line 15 -> Shape.draw
main   line 16 -> Main.report
report line 19 -> Main.square
report line 21 -> Shape.draw
report line 22 -> Square.area
report line 23 -> Square.draw
edges into application methods: 9

What to notice: 6 virtual edges — the dynamic call graph of §3. Allocation-site objects, per-variable (and split) locals and an on-the-fly call graph together reach the ground truth on this program: the whole precision chain of Theorem 20.1.14, 24 → 15 → 11 → 9 edges, in one tool.

Find where LLVM does it. Open llvm/lib/Analysis/CallGraph.cpp and find the function that decides whether the external calling node gets an edge to a function. Which two conditions does it test? (Quiz llvm-where-callgraph-root.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Direct call graph	Exact for direct calls; every indirect call goes to "unknown"	\(O(S)\) · one pass	Sound without any whole-program assumption	Low	LLVM `CallGraph`/`LazyCallGraph`, GCC cgraph, every C compiler
CHA	All subclasses of the declared type (21 edges on the example)	\(O(S \lvert\mathcal{C}\rvert h)\) · fastest OO resolution	Sound in a closed world	Low (hierarchy + dispatch)	Devirtualization in C++/Java compilers, LLVM WPD's type metadata, JIT class-hierarchy checks
RTA	CHA ∩ instantiated classes (12)	~CHA · a few rounds	Sound in a closed world; removes never-constructed classes	Low	GCC `type_possibly_instantiated_p`, Soot, whole-program Java tools
XTA / VTA	Per-method (9) / per-variable (8) type sets	\(O(\text{sets} \cdot \lvert\mathcal{C}\rvert \cdot S)\) · seconds on large Java programs	Sound, flow-insensitive	Medium (propagation graph)	Soot `vta`, OPAL, WALA; GCC polymorphic call contexts (flow-sensitive cousin)
Points-to based	Allocation sites, on the fly (6 = dynamic here)	\(O(V^3)\) · the most expensive	Sound; the precision of Ch 19's analysis	High	Soot Spark, Doop, SVF; indirect-call resolution in analyzers

Choose a direct call graph when you compile C-like code or cannot see the whole program: it is the only sound choice without a closed world. Choose CHA when you need cheap devirtualization and the hierarchy is complete. Choose RTA when the program links many classes it never constructs (frameworks, libraries): nearly free on top of CHA. Choose XTA or VTA when you analyze a whole Java-like program and want most virtual calls monomorphic without a full points-to analysis. Choose a points-to-based graph when precision matters more than time (security analyses, refactoring tools) or when function pointers dominate.

The comparison lab measures CHA, RTA and XTA on the two hand-written inputs (ch20-cg --table --xta labs/ch20-callgraph/inputs/*.oo): 36, 20 and 17 call edges, 19, 11 and 11 reachable bodies; on 100 random programs every graph contains the dynamic one (ch20.lab/cg-soundness.test).

9. Assessment¶

Quiz (./course quiz 20): direct-cg-root, llvm-where-callgraph-root (tag direct-cg); cha-targets, cha-closed-world (tag cha); rta-targets, rta-edges (tag rta); xta-sets, vta-precision (tag xta-vta); pta-cg-edges, pta-cg-onthefly (tag pta-cg).
Drill: ./course drill cha-rta (easy: CHA; medium: CHA and RTA; hard: CHA, RTA and XTA). Direct call graphs are practiced by scc-order (Lesson 20.2), whose instances are direct call graphs with LLVM's external nodes; VTA and points-to resolution have no separate drill, because their traces are the XTA trace with finer sets — the quiz questions vta-precision and pta-cg-edges compute them on concrete programs.
Flashcards: tags direct-cg, cha, rta, xta-vta, pta-cg.
Exercises: E1 print<pebble-callgraph>; lab part A (labs/ch20-callgraph/SPEC.md).

References¶

See the chapter references.

Lesson 20.1 — Call-graph construction: direct calls, CHA, RTA, XTA/VTA and points-to¶

1. Problem and motivation¶

Direct call graphs¶

Class hierarchy analysis (CHA)¶

Rapid type analysis (RTA)¶

XTA and VTA¶

Points-to-based call graphs¶

2. Definitions and algorithms¶

3. Worked example¶

Direct call graphs¶

Class hierarchy analysis (CHA)¶

Rapid type analysis (RTA)¶

XTA and VTA¶

Points-to-based call graphs¶

4. Invariants and correctness¶

5. Complexity¶

6. Variants and refinements¶

7. In real compilers¶

Direct call graphs¶

Class hierarchy analysis (CHA)¶

Rapid type analysis (RTA)¶

XTA and VTA¶

Points-to-based call graphs¶

8. Comparison¶

9. Assessment¶

References¶