Skip to content

Lab 20A · Call graphs for virtual calls: CHA vs RTA (★ XTA)

Chapter: 20 · Interprocedural & Whole-Program Optimization · Lessons: 20.1 · Time: 6–10 hours · Tests: ./course test 20 (label ch20, suite ch20.lab, files tests/ch20/lab/cg-*.test)

Goal

Build the call graph of programs in a small class-based language with virtual calls, twice: with class hierarchy analysis (Algorithm 20.1.5), which resolves a call r.m() to every override of m below the declared type of r, and with rapid type analysis (Algorithm 20.1.6), which keeps only the classes instantiated in reachable code. Check both against a Python oracle, against a brute-force dynamic call graph (every call that some execution makes must be in your graph: soundness, Theorem 20.1.13) and against each other (RTA ⊆ CHA: the precision chain, Theorem 20.1.14). Then measure how many call edges and reachable bodies each analysis reports. ★ Add XTA (Algorithm 20.1.8), which keeps one class set per body and per global.

Requirements

  • R1. CHA. buildCHA(P) computes the bodies reachable from main with a worklist: a call f makes f reachable; a virtual call L: r.m() in a reachable body gets the targets \(\{\mathrm{lookup}(C, m) \mid C \le \mathrm{decl}(r)\}\) — for every class \(C\) that is decl(r) or a (transitive) subclass of it, the nearest definition of m in \(C\) or its ancestors (Definition 20.1.4) — and each target becomes reachable.
  • R2. RTA. buildRTA(P) is the least fixed point of: main is reachable; every new C in a reachable body makes \(C\) instantiated (anywhere in the body, including every choose branch, regardless of statement order); a call L: r.m() in a reachable body gets \(\{\mathrm{lookup}(C, m) \mid C \le \mathrm{decl}(r),\ C \text{ instantiated}\}\) and its targets are reachable; call f makes f reachable.
  • R3. Result conventions. Targets maps a site label to its target keys ("Class.method"); a site in a body the analysis never reaches has no targets (an empty set or no entry — the driver prints - either way). Reachable holds the body keys reached, including "main".
  • R4. Agreement with the oracle. ch20-cg --algo cha and --algo rta print exactly what tools/oracle.py dump --algo cha|rta prints, on random programs.
  • R5. Soundness and precision. For every program: every (site, target) the dynamic oracle observes is in your RTA result, every RTA edge and reachable body is in your CHA result.
  • R6. ★ XTA. buildXTA(P) keeps a class set \(S[B]\) per reachable body and \(S[@g]\) per global (Definition 20.1.7), iterated to a fixed point: x = new C adds \(C\) to \(S[B]\) (and to \(S[@x]\) if x is a global); g = x adds the classes of \(S[B]\) that are subclasses of decl(g) to \(S[@g]\); x = g adds the classes of \(S[@g]\) that are subclasses of decl(x) to \(S[B]\); g1 = g2 moves \(S[@g_2]\) into \(S[@g_1]\), filtered the same way; a call r.m() whose receiver is a global first adds \(S[@r]\) (filtered by decl(r)) to \(S[B]\); then for each \(C \in S[B]\) with \(C \le \mathrm{decl}(r)\) the target \(t = \mathrm{lookup}(C, m)\) is added to the site, \(t\) becomes reachable, and \(C\) is added to \(S[t]\) (the receiver flows into the callee's this); call f makes f reachable. XTA equals the oracle and sits between the dynamic graph and RTA.
  • R7. Performance. Each analysis handles the 2000 random programs of oracle.py gen --count 2000 --seed 5 (184,000 lines) in under 2 s on the CI runner (the reference: about 0.4 s each, including parsing and printing). CHA is \(O(\lvert \text{sites} \rvert \cdot \lvert \text{classes} \rvert)\) after the hierarchy is indexed; RTA and XTA iterate at most \(O(\lvert \text{classes} \rvert + \lvert \text{bodies} \rvert)\) (RTA) or \(O(\lvert \text{classes} \rvert \cdot (\lvert \text{bodies} \rvert + \lvert \text{globals} \rvert))\) (XTA) productive rounds.

The contract

// labs/ch20-callgraph/include/lab20/CallGraph.h  (provided; do not change)
namespace lab20 {
struct CallGraphResult {
  /// Every call-site label of the program -> the methods ("Class.method") the
  /// analysis says it may call. A site in a body the analysis never reaches
  /// maps to the empty set.
  std::map<std::string, std::set<std::string>> Targets;
  /// The body keys ("main", "f", "Class.method") the analysis reaches.
  std::set<std::string> Reachable;
};
CallGraphResult buildCHA(const Program &P);   // R1
CallGraphResult buildRTA(const Program &P);   // R2
CallGraphResult buildXTA(const Program &P);   // ★ R6
}

Program (include/lab20/Program.h, provided) is the syntax tree exactly as written: classes with their parents, globals with their declared classes, and bodies (functions and methods, textual order) with their locals and statements (New, Copy, VCall, Call, Choose with branches). The class-hierarchy queries — subclasses, dispatch (lookup), the declared type of a variable — are part of the learning objective and are yours to write.

The driver ch20-cg (provided, tools/CgMain.cpp) calls the contract:

usage: ch20-cg --algo cha|rta|xta FILE...
       ch20-cg --table [--xta] FILE...

Input and output formats

Input (one or more programs per file; === <name> starts a program; a file without such lines holds one program named after the file; # starts a comment):

class <C> [extends <P>]              P must be declared earlier
global <g>: <C>
func <name> { <body> }               `func main` is required
method <C>.<m> { <body> }            defines m in C (an override if an ancestor defines m)
<body>  ::= ( var <x>: <C>           a local, visible in the whole body
            | <x> = new <C>          C must be a subclass of decl(x)
            | <x> = <y>              decl(y) must be a subclass of decl(x)
            | <L>: <r>.<m>()         a virtual call site with a unique label L
            | call <f>               a direct call of a function
            | choose { <body> } or { <body> } ... )*

A variable name means the body's local if the body declares it, otherwise this (in a method; its declared class is the method's class), otherwise the global. Every program is type-correct, and some class at or below decl(r) defines or inherits m at every call site.

Output of ch20-cg --algo A (the targets in the textual order of the bodies; - for none):

=== running
s1: Circle.area Square.area
s2: Shape.draw Square.draw
s3: Shape.draw Square.draw
s4: Circle.area Square.area
s5: Shape.draw Square.draw
s6: -
s7: Circle.area Square.area
reachable: main report Shape.draw Circle.area Square.area Square.draw

(RTA on inputs/running.oo, Lesson 20.1's running example.) ch20-cg --table prints one row per program — call sites, call edges (\(\sum_{\text{sites}} \lvert \text{targets} \rvert\)) and reachable bodies per analysis — and a TOTAL row.

Provided infrastructure

File What it gives you
include/lab20/Program.h, provided/Program.cpp the syntax tree, parsePrograms (errors name the line), callSites
tools/CgMain.cpp the driver ch20-cg (printing and the table)
tools/oracle.py gen (random programs), dump --algo cha\|rta\|xta\|vta\|dyn (the expected output; dyn is the dynamic call graph, vta a reference VTA for comparison), check (soundness and the precision chain for your outputs)
tools/soot/ the running example in Java and a Soot driver that prints Soot's CHA, RTA and VTA call graphs, for the comparison in Lesson 20.1 §7 (needs a Soot jar; optional)
inputs/running.oo, inputs/visitor.oo the lesson's running example and a double-dispatch visitor

What the tests check

Test Checks
cg-oracle.test R4: CHA and RTA output equal the oracle's on 3 × 60 random programs
cg-soundness.test R5 on 100 random programs and on running.oo; exact CHA and RTA lines for running.oo; the dynamic oracle's view of it
cg-table.test the measurement table below for running.oo and visitor.oo (runs in solution builds, since it includes XTA)
cg-xta.test ★ R6: XTA equals the oracle on 60 random programs and satisfies dynamic ⊆ XTA ⊆ RTA ⊆ CHA (runs in solution builds, because XTA is optional; run its RUN: lines by hand on yours)

Milestones

  1. L1 · CHA. Class queries (subclasses, lookup, declared types), then R1. ctest --preset linux -L '^ch20$' -R ch20.lab — cg-oracle.test passes its CHA lines; ch20-cg --algo cha inputs/running.oo matches Lesson 20.1 §3.
  2. L2 · RTA. R2; cg-oracle.test and cg-soundness.test pass.
  3. L3 · Measurement. Fill in the table below with ch20-cg --table inputs/*.oo and for 100 random programs (oracle.py gen --count 100 --seed 7 > r.oo; ch20-cg --table r.oo | tail -1); time R7's corpus.
  4. L4 · ★ XTA. R6; cg-xta.test.
Input sites CHA edges RTA edges XTA edges dynamic edges CHA reachable RTA reachable time CHA / RTA
running.oo 7 21 12 9 9 6
visitor.oo 6 15 8 8 10 5
100 random programs

(The first two rows are the reference solution's; fill in the dynamic edges from oracle.py dump --algo dyn and your own measurements. Explain in one sentence per input where RTA's extra edges over the dynamic graph come from: a class instantiated somewhere reachable but never reaching this receiver — exactly what XTA and VTA refine.)

Hints

Hint 1 — where to start

Index the hierarchy once: children lists (for "all subclasses of T" by DFS) and a map from body key to body. Write lookup(C, m) by walking up the parents. Then CHA is a plain worklist over bodies: nothing depends on statement order.

Hint 2 — the key idea

RTA's two sets — reachable bodies and instantiated classes — grow together: a new reachable body can instantiate a class, which adds targets at already processed call sites, which can make new bodies reachable. Either iterate rounds until nothing changes, or keep, for each class not yet instantiated, the call sites waiting for it. Both give the least fixed point, which is all the tests compare.

Hint 3 — a design sketch

A Hierarchy (parents, children, subclasses(T) cached, lookup), a resolve(body, var) → class for declared types, and one function per analysis that returns CallGraphResult. Give every reachable body's call sites an entry in Targets when you process it. For XTA, keep std::map<std::string, std::set<std::string>> for the sets (key "@g" for a global) and loop until a whole pass over the reachable bodies changes nothing. The common bug cg-soundness.test catches: forgetting the new statements inside choose branches.

Stretch goals

  • ★ XTA (R6, milestone L4).
  • Compare with Soot on tools/soot/Main.java (Lesson 20.1 §7): which of Soot's VTA edges does your XTA also remove, and why does Soot keep one more?
  • Implement VTA (Algorithm 20.1.10) against oracle.py dump --algo vta (there is no driver mode or test for it; add one to your own copy of the driver).