Lesson 19.7 — Context sensitivity: call strings, cloning and summaries, object and type sensitivity¶

Techniques: call-string context sensitivity (Sharir and Pnueli's call strings, Shivers's k-CFA); cloning (Whaley and Lam's context per acyclic call path) and summary-based analysis (the functional approach; LLVM's bottom-up function attributes); object sensitivity (Milanova, Rountev and Ryder) and type sensitivity (Smaragdakis, Bravenboer and Lhoták) · Pebble implements: nothing (the lab is context-insensitive: "one copy of each function") · Prerequisites: Lesson 19.4; interprocedural analysis basics (Lesson 14.8, IFDS) · Time: 4–5 hours

1. Problem and motivation¶

A context-insensitive analysis analyses each function once, merging what all callers pass in. For helper functions that is disastrous:

int *id(int *v) { return v; }
int *x = id(&a);   /* call site c1 */
int *y = id(&b);   /* call site c2 */

One copy of v receives both &a and &b, and both x and y get \(\{a, b\}\): the return value flows back to every caller (an "unrealizable path" from c1's argument to c2's result). A context-sensitive analysis distinguishes calls by a context, an abstraction of the calling situation. The contexts decide precision and cost; the families differ in what a context is.

Call-string sensitivity (k-CFA)¶

A context is the sequence of the last \(k\) call sites on the stack. Sharir and Pnueli introduced call strings for interprocedural dataflow [SP81]; Shivers's k-CFA used the last \(k\) call sites for higher-order control-flow analysis [Shi88]. With \(k = 1\), id is analysed once for c1 and once for c2, and \(x \mapsto \{a\}\), \(y \mapsto \{b\}\).

Cloning and summaries¶

Cloning analyses a separate copy of a function for every path in the call graph (collapsing recursive cycles). Whaley and Lam made this feasible for Java — \(10^{14}\) contexts — by representing the relations as binary decision diagrams [WL04]. Summaries (Sharir and Pnueli's functional approach [SP81]) analyse each function once, parametrically in its inputs, and apply the summary at every call: the effect of full cloning without copies. LLVM's function attributes (memory(argmem: read), captures(none)) are summaries of this kind, computed bottom-up over the call graph [LLVM-FunctionAttrs].

Object and type sensitivity¶

In object-oriented programs, the receiver object often says more than the call site: two Box objects' set/get should not be mixed, whichever line calls them. Object sensitivity uses the allocation sites of the receiver (and of the receiver's allocator, up to depth \(k\)) as the context [MRR05]. Type sensitivity replaces each allocation site in the context by the class that contains it, a coarser but much cheaper context [SBL11].

2. Definitions and algorithms¶

We extend the constraint language of Definition 19.4.1 with functions: f(v) { … return w; }, calls x = f(y) at call sites \(c\), and (for object sensitivity) allocations v = new h at allocation sites \(h\) and virtual calls x = r.m(y).

Call-string sensitivity (k-CFA)¶

Definition 19.7.1 (Contexts and context-sensitive facts)

A context abstraction is a finite set \(\mathit{Ctx}\) with an initial context \(\epsilon\) and a function \(\mathrm{push}\) that gives the callee's context at a call. A context-sensitive analysis has facts over pairs: \(\mathrm{pts}(c, v)\) for a variable \(v\) of a function analysed in context \(c\), and (with heap contexts) objects \((c, h)\). Projecting forgets contexts: \(\pi(\mathrm{pts})(v) = \bigcup_c \{ h : (\cdot, h) \in \mathrm{pts}(c, v) \}\).

Definition 19.7.2 (k-call-string contexts)

A k-call-string context is a sequence of at most \(k\) call sites; \(\epsilon\) is the empty string, and a call at site \(s\) in context \(c = \langle s_1, \dots, s_j \rangle\) enters the callee in context \(\mathrm{push}_k(c, s)\), the sequence of the last \(k\) elements of \(\langle s_1, \dots, s_j, s \rangle\).

Algorithm 19.7.3 (Context-sensitive Andersen, parameterised by the context abstraction)

Input: a program with functions; a context abstraction (k-call-strings here; objects below).
Output: \(\mathrm{pts}(c, v)\) for every reachable (context, variable) pair.
Precondition: the call graph is known (or discovered on the fly for indirect calls).
Postcondition: the least solution of the rules below; its projection is sound and ⊆ the context-insensitive solution (Theorem 19.7.8).
Invariant: only pairs \((c, f)\) reachable from \((\epsilon, \mathrm{main})\) through the push function are analysed.

Reach ← {(ε, main)}
rules (solved with the worklist of Algorithm 19.4.4 over (context, variable) nodes):
  in (c, f) ∈ Reach:  v = &a        ⇒  a ∈ pts(c, v)
                      v = w         ⇒  pts(c, v) ⊇ pts(c, w)
                      v = *w, *v = w ⇒ as Definition 19.4.1, over objects (heap contexts optional)
                      x = g(y) at s ⇒  c' ← push(c, s);  Reach ∪= {(c', g)}
                                       pts(c', param_g) ⊇ pts(c, y)
                                       pts(c, x)       ⊇ pts(c', ret_g)

Cloning and summaries¶

Definition 19.7.4 (Cloning contexts, summaries)

Cloning uses as contexts the acyclic paths of the call graph from main, after collapsing every strongly connected component (recursion) to one node: calls inside an SCC keep the context. A summary of \(f\) is a relation between the points-to facts on entry to \(f\) (of its parameters and of the memory they reach) and those on exit (its return value and the memory it wrote), expressed in terms of symbolic inputs, so that applying it at a call yields the same facts as analysing a clone of \(f\) for that call.

Algorithm 19.7.5 (Summary-based analysis, bottom-up over the call graph)

Input: a program; its call graph with SCCs in bottom-up order.
Output: a summary per function and the points-to facts in main.
Precondition: direct calls (indirect calls need the call graph from a first, context-insensitive pass).
Postcondition: for non-recursive programs the facts equal those of full cloning (Theorem 19.7.9).
Invariant: when an SCC is processed, every callee outside it has its final summary.

function Summaries(program):
    for each SCC S, callees first:
        for f in S: introduce symbolic objects P1, P2, … for what f's parameters point to
        solve the constraints of S's bodies, where each call x = g(y):
            if g ∈ S: link params/returns directly (context-insensitive inside the SCC)
            else:     instantiate Summary(g): replace g's symbolic Pi by pts(y's targets), add the result to pts(x)
        Summary(f) ← the solved facts of ret_f and of memory reachable from the Pi, in terms of the Pi
    solve main by instantiating the summaries of its callees

For the identity function, \(\mathrm{Summary}(\mathrm{id}) = \{\mathrm{ret} \mapsto P_1\}\): the result points wherever the argument points. At c1 it instantiates to \(\{a\}\), at c2 to \(\{b\}\).

Object and type sensitivity¶

Definition 19.7.6 (Object and type sensitivity)

In k-object sensitivity, a method invoked on a receiver object \((c_h, h)\) — allocation site \(h\) created in heap context \(c_h\) — is analysed in context \(\langle h \rangle \cdot c_h\) truncated to \(k\) elements; allocations inside a method analysed in context \(c\) get heap context \(c\) (truncated to \(k - 1\)). In k-type sensitivity, every allocation site in a context is replaced by \(\mathrm{T}(h)\), the class that contains the method in which \(h\) occurs [SBL11].

Algorithm 19.7.7 (1-object-sensitive analysis for a Java-like core)

Input: v = new h, v = w, v = w.f, v.f = w (field loads and stores), virtual calls x = r.m(y).
Output: \(\mathrm{pts}(c, v) \subseteq \mathit{Heap}\) per context \(c \in \mathit{Heap} \cup \{\epsilon\}\) and field facts \(\mathrm{fld}(h, f)\).
Precondition: each virtual call's targets are determined by the dynamic class of the receiver object.
Postcondition: the least solution; its projection ⊆ context-insensitive (Theorem 19.7.8).
Invariant: method \(m\) is analysed in context \(h\) only if some reachable call has a receiver pointing to \(h\).

rules:
  v = new h in context c           ⇒  h ∈ pts(c, v)                    # heap context dropped (k − 1 = 0)
  x = r.m(y) in c, h ∈ pts(c, r)   ⇒  m' ← dispatch(class(h), m)
                                       h ∈ pts(h, this_m');  pts(h, param_m') ⊇ pts(c, y)
                                       pts(c, x) ⊇ pts(h, ret_m')
  v.f = w in c                     ⇒  for h ∈ pts(c, v): fld(h, f) ⊇ pts(c, w)
  v = w.f in c                     ⇒  for h ∈ pts(c, w): pts(c, v) ⊇ fld(h, f)

3. Worked example¶

Call-string sensitivity (k-CFA)¶

The identity example with allocation-free pointers pa = &a, pb = &b (the first Soufflé box, §7):

analysis	contexts of `id`	\(\mathrm{pts}(v)\)	`x`	`y`
context-insensitive	one	{a, b}	{a, b}	{a, b}
1-call-site (1-CFA)	⟨c1⟩, ⟨c2⟩	⟨c1⟩: {a}; ⟨c2⟩: {b}	{a}	{b}

If id itself called a helper h(v) at one site \(d\), 1-CFA would analyse h in the single context ⟨d⟩ for both outer calls and merge again; 2-CFA keeps ⟨c1, d⟩ and ⟨c2, d⟩ apart. Each extra level of wrapping costs one more \(k\).

Cloning and summaries¶

Cloning the same program creates id@c1 and id@c2, with the same answer as 1-CFA. With a wrapper w(v) { return id(v); } called at c1 and c2, cloning creates w@c1 → id@c1·d and w@c2 → id@c2·d (paths of any length), which 1-CFA cannot separate. The summary approach computes \(\mathrm{Summary}(\mathrm{id}) = \{\mathrm{ret} \mapsto P_1\}\), then \(\mathrm{Summary}(w) = \{\mathrm{ret} \mapsto P_1\}\) by instantiating id's summary inside w, and finally \(x \mapsto \{a\}\), \(y \mapsto \{b\}\) in main: one analysis per function. The second box (§7) shows LLVM computing summaries of this kind for memory effects: sum gets memory(argmem: read) and a captures(none) parameter, fill gets memory(argmem: write), and remember's parameter is not captures(none) because it stores it into a global — so caller's second argument is not either.

Object and type sensitivity¶

The Box program of the third box (§7): b1 = new Box (site h1), b1.set(new A) (hA), x = b1.get(); b2 = new Box (h2), b2.set(new B) (hB), y = b2.get(). Algorithm 19.7.7:

step	rule	new facts
1	allocations in main	pts(ε, b1) = {h1}, pts(ε, b2) = {h2}, pts(ε, a) = {hA}, pts(ε, bb) = {hB}
2	`b1.set(a)`: receiver h1	context h1: this {h1}, v {hA}
3	`b2.set(bb)`: receiver h2	context h2: this {h2}, v {hB}
4	`this.f = v` in contexts h1, h2	fld(h1, f) = {hA}, fld(h2, f) = {hB}
5	`get` in contexts h1, h2: `return this.f`	context h1: ret {hA}; context h2: ret {hB}
6	`x = b1.get()`, `y = b2.get()`	pts(ε, x) = {hA}, pts(ε, y) = {hB}

A context-insensitive analysis has one this with \(\{h1, h2\}\) and one v with \(\{hA, hB\}\), so both fields get both, and x, y both get \(\{hA, hB\}\) — the box's result_ci. Type sensitivity with T(h1) = T(h2) = Main (both allocated in main) would merge the two contexts again and lose the distinction here; it pays off when objects are allocated in different classes (a factory in class Factory vs one in Main).

4. Invariants and correctness¶

Call-string sensitivity (k-CFA)¶

Theorem 19.7.8 (Context-sensitive results project into the context-insensitive ones)

For any context abstraction, the projection \(\pi(\mathrm{pts}_{cs})\) of the least context-sensitive solution of Algorithm 19.7.3 (or 19.7.7) is contained in the least context-insensitive solution \(\mathrm{pts}^*\), and it is sound for every execution.

Proof

Containment. Define \(\hat{\mathrm{pts}}(c, v) = \mathrm{pts}^*(v)\) for every context: every context-sensitive rule, with contexts erased, is a context-insensitive constraint that \(\mathrm{pts}^*\) satisfies, so \(\hat{\mathrm{pts}}\) is a context-sensitive solution; the least one is below it, and projecting gives the claim. Soundness. Map every concrete call stack to its abstract context (the last \(k\) call sites, or the receiver's allocation sites); the concrete value of \(v\) in a frame with abstract context \(c\) is then in \(\mathrm{pts}_{cs}(c, v)\), by induction on the execution as in Theorem 19.4.12: each call transfers the actual's value to the callee frame whose context is exactly \(\mathrm{push}(c, s)\), and each return transfers from that frame back — the rules cover both.

Cloning and summaries¶

Theorem 19.7.9 (Cloning, summaries and inlining agree on non-recursive programs)

For a program without recursion, full cloning, k-CFA with \(k\) at least the depth of the call graph, and summary-based analysis all compute the same points-to sets as context-insensitive analysis of the fully inlined program.

Proof sketch (full treatment: [SP81, §3–4] for call strings vs the functional approach; [WL04, §2] for cloning)

Without recursion every call stack is an acyclic path of the call graph of bounded length, so contexts of all three kinds are in one-to-one correspondence with call paths, which are exactly the copies that inlining creates: each clone (or each context, or each instantiation of a summary) receives the arguments of exactly one path and returns only to it. Summaries are the same computation done symbolically once and instantiated per path; they coincide with the clones as long as the summary is exact (for Andersen-style constraints it is: the solved facts are unions over the symbolic inputs, which distribute over instantiation). With recursion the three differ: cloning merges an SCC into one context, k-CFA truncates, and summaries need a fixed point inside the SCC.

Object and type sensitivity¶

Theorem 19.7.10 (Type sensitivity is coarser than object sensitivity of the same depth)

For the same \(k\) (and the same heap-context depth), the projection of the k-type-sensitive solution contains the projection of the k-object-sensitive solution.

Proof sketch (full proof: [SBL11, §4])

The type-sensitive context is the image of the object-sensitive context under the map \(h \mapsto \mathrm{T}(h)\) applied elementwise. Mapping every object-sensitive fact \((c, v)\) to \((\mathrm{T}(c), v)\) turns the object-sensitive rules into type-sensitive ones, so the type-sensitive least solution is a solution of the mapped object-sensitive system; hence every fact derived with object contexts appears (mapped) with type contexts, and possibly more, because distinct object contexts can map to the same type context. Projection erases the contexts.

5. Complexity¶

Let \(n\) be the size of the program, \(S\) the number of call sites, \(H\) allocation sites, \(T \le H\) classes, \(P\) call-graph paths.

Technique	Contexts per function (worst)	Total time (worst)	Typical
k-CFA (call strings)	\(S^k\)	\(O((n S^k)^3)\) by Andersen over contexted nodes	1- or 2-CFA feasible for Java with good solvers [LH06]
Cloning	\(P\), exponential in call depth (\(10^{14}\) in [WL04]'s largest benchmark)	exponential without sharing; with BDDs, depends on the variable order	practical only with BDDs [WL04, WACL05]
Summaries	1 per function, but summary size can grow with the number of symbolic inputs	exponential in the worst case (summaries of summaries), polynomial for Andersen-style relations	LLVM's function-attrs: linear passes over SCCs
k-object	\(H^k\)	\(O((n H^k)^3)\)	2-object with 1-heap context is the Java sweet spot [SBL11]
k-type	\(T^k\)	\(O((n T^k)^3)\)	much faster than k-object at similar precision [SBL11]

Justification. Each (context, variable) pair is a node of Andersen's graph, so the cubic bound of Proposition 19.4.16 applies with \(N = n \cdot \lvert \mathit{Ctx} \rvert\) nodes. Pathological family for cloning: a chain of \(d\) functions where \(f_i\) calls \(f_{i+1}\) from two call sites has \(2^d\) paths to \(f_d\), so full cloning analyses \(f_d\) \(2^d\) times, while 1-CFA analyses it twice and a summary once.

Call-string sensitivity (k-CFA)¶

Heap cloning (heap contexts: allocation sites qualified by the allocating context); trade-off: separates objects created by the same factory for different callers, at \(H \cdot \lvert \mathit{Ctx} \rvert\) objects.
Selective / introspective context sensitivity: choose \(k\) per method from a cheap pre-analysis; trade-off: analysis heuristics, less predictable cost.

Cloning and summaries¶

IFDS/IDE (Lesson 14.8): exact summaries for distributive problems by graph reachability; trade-off: points-to analysis is not distributive in general, so it is used for clients on top of points-to results.
BDD cloning [WL04]: \(10^{14}\) clones represented symbolically; trade-off: BDD variable ordering dominates performance.
Attribute inference (LLVM function-attrs, Go's parameter tags in escape analysis, Lesson 19.9): cheap, coarse summaries of effects and captures; trade-off: facts, not full points-to relations.

Object and type sensitivity¶

Hybrid contexts (call sites for static methods, objects for virtual calls); trade-off: more rules, better precision on mixed code.
Type sensitivity [SBL11]: \(T \ll H\) contexts; trade-off: merges objects of one class allocated in different methods of another class.

7. In real compilers¶

Call-string sensitivity (k-CFA)¶

Where call strings are used

Production C/C++ compilers do not run context-sensitive points-to analysis: GCC's -fipa-pta is interprocedural but context-insensitive [GCC-StructAlias], and LLVM has none. Call-string sensitivity lives in analysis frameworks: Doop and WALA for Java, SVF's context-sensitive demand-driven analysis for C (Lesson 19.8), and k-CFA-style analyses for functional languages.

1-call-site sensitivity in six Datalog rules

Reproduce (souffle 2.5; any OS):

cat > cs.dl <<'DL'
// Context-insensitive vs 1-call-site-sensitive points-to for an identity function
// called from two sites:  x = id(&a) at c1;  y = id(&b) at c2;  id(v) { return v; }
.decl addr(p:symbol, o:symbol)
.decl call(site:symbol, ret:symbol, arg:symbol)       // ret = id(arg) at site
.decl pts_ci(v:symbol, o:symbol)
.decl pts_cs(ctx:symbol, v:symbol, o:symbol)          // v's value in context ctx
.decl result_cs(v:symbol, o:symbol)
.output pts_ci(IO=stdout)
.output result_cs(IO=stdout)
addr("pa","a"). addr("pb","b").
call("c1","x","pa"). call("c2","y","pb").
// context-insensitive: one copy of id's parameter v and return value
pts_ci(p, o) :- addr(p, o).
pts_ci("v", o) :- call(_, _, arg), pts_ci(arg, o).
pts_ci(ret, o) :- call(_, ret, _), pts_ci("v", o).
// 1-CFA: id's variable v is analysed once per call site (the context)
pts_cs("main", p, o) :- addr(p, o).
pts_cs(site, "v", o) :- call(site, _, arg), pts_cs("main", arg, o).
pts_cs("main", ret, o) :- call(site, ret, _), pts_cs(site, "v", o).
result_cs(v, o) :- pts_cs("main", v, o), (v = "x" ; v = "y").
DL
souffle -D- cs.dl

Output (complete):

---------------
pts_ci
v   o
===============
pa  a
pb  b
x   a
x   b
y   a
y   b
v   a
v   b
===============
---------------
result_cs
v   o
===============
x   a
y   b
===============

What to notice: the context-insensitive relation gives x and y both a and b, and v both; the call-site-sensitive rules keep v per call site (contexts c1, c2), so result_cs has x → a and y → b only — the §3 table.

Cloning and summaries¶

LLVM, Go

LLVM llvm/lib/Transforms/IPO/FunctionAttrs.cpp — addMemoryAttrs and addArgumentAttrs infer memory(...) and captures(none) bottom-up over call-graph SCCs; every later alias query uses them at each call site as a summary [LLVM-FunctionAttrs] (LLVM 23.1.2). Go records per-function "parameter tags" (does a parameter leak to the heap or to a result?) in its escape analysis and applies them at call sites [Go-Escape]. Whaley and Lam's bddbddb implements cloning with BDDs [WACL05].

LLVM infers memory and capture summaries bottom-up

Reproduce (clang 23.1.2, opt 23.1.2; Linux x86-64):

cat > fa.c <<'C'
static int sum(const int *a, int n) { int s = 0; for (int i = 0; i < n; i++) s += a[i]; return s; }
static void fill(int *a, int n, int v) { for (int i = 0; i < n; i++) a[i] = v; }
int *keep;
static void remember(int *a) { keep = a; }
int caller(int *x, int *y, int n) {
  fill(x, n, 1);
  remember(y);
  return sum(x, n);
}
C
clang-23 -O1 -Xclang -disable-llvm-optzns -S -emit-llvm fa.c -o - | opt -passes='sroa' -S -o fa.ll
echo "== summaries inferred bottom-up over the call graph (opt -passes=function-attrs):"
opt -passes='cgscc(function-attrs)' -S fa.ll | grep -E '^define' | sed 's/ #[0-9]* {$//'
opt -passes='cgscc(function-attrs)' -S fa.ll | grep -E '^attributes #[0-9]+ = \{.*memory' | sed 's/ "[^"]*"="[^"]*"//g'

Output (complete):

== summaries inferred bottom-up over the call graph (opt -passes=function-attrs):
define dso_local i32 @caller(ptr nofree noundef captures(none) %0, ptr noundef %1, i32 noundef %2)
define internal void @fill(ptr nofree noundef writeonly captures(none) %0, i32 noundef %1, i32 noundef %2)
define internal void @remember(ptr noundef %0)
define internal i32 @sum(ptr nofree noundef readonly captures(none) %0, i32 noundef %1)
attributes #0 = { nofree norecurse nosync nounwind memory(write, argmem: readwrite, inaccessiblemem: none, target_mem: none) uwtable }
attributes #1 = { nofree norecurse nosync nounwind memory(argmem: write) uwtable }
attributes #2 = { mustprogress nofree norecurse nosync nounwind willreturn memory(write, argmem: none, inaccessiblemem: none, target_mem: none) uwtable }
attributes #3 = { nofree norecurse nosync nounwind memory(argmem: read) uwtable }
attributes #4 = { nocallback nofree nosync nounwind willreturn memory(argmem: readwrite) }

What to notice: sum is memory(argmem: read) with a readonly captures(none) parameter; fill is memory(argmem: write); remember stores its argument into a global, so its parameter has no captures(none) and neither does caller's second parameter, which is passed to it — the summaries compose up the call graph (Algorithm 19.7.5).

Find where LLVM does it. In FunctionAttrs.cpp, which function adds the memory(...) attribute, and over what unit of the call graph does the pass iterate? (Quiz llvm-where-function-attrs.)

Object and type sensitivity¶

Where object sensitivity is used

Doop (Datalog, run with Soufflé) implements call-site, object and type sensitivity for Java [BS09, SBL11]; WALA and Soot/Spark offer object-sensitive variants. Compilers for managed languages do not run them ahead of time; JITs use cheaper, per-compilation-unit escape analysis (Lesson 19.9).

1-object sensitivity versus context-insensitive analysis for two Box objects

Reproduce (souffle 2.5; any OS):

cat > obj.dl <<'DL'
// Java-like program:  class Box { Object f; void set(Object v) { this.f = v; } Object get() { return this.f; } }
//   Box b1 = new Box();  /*h1*/   b1.set(new A()); /*hA*/   x = b1.get();
//   Box b2 = new Box();  /*h2*/   b2.set(new B()); /*hB*/   y = b2.get();
// Object sensitivity (Milanova et al.): methods are analysed per receiver *object*.
.decl alloc(v:symbol, h:symbol)                       // v = new h   (in main)
.decl vcall(recv:symbol, meth:symbol, arg:symbol, ret:symbol)
.decl hpts(ctx:symbol, v:symbol, h:symbol)            // variable v of a method analysed in context ctx
.decl fld(h:symbol, f:symbol, o:symbol)               // field h.f may point to o
.decl result(v:symbol, h:symbol)
.decl result_ci(v:symbol, h:symbol)
.decl ci(v:symbol, h:symbol)
.decl fci(h:symbol, o:symbol)
.output result(IO=stdout)
.output result_ci(IO=stdout)
alloc("b1","h1"). alloc("a","hA"). alloc("b2","h2"). alloc("bb","hB").
vcall("b1","set","a","_"). vcall("b1","get","_","x").
vcall("b2","set","bb","_"). vcall("b2","get","_","y").
hpts("main", v, h) :- alloc(v, h).
// call: the context of the callee is the receiver object h
hpts(h, "this", h) :- vcall(r, _, _, _), hpts("main", r, h).
hpts(h, "v", o) :- vcall(r, "set", a, _), hpts("main", r, h), hpts("main", a, o).
fld(t, "f", o) :- hpts(h, "this", t), hpts(h, "v", o).              // this.f = v  in set
hpts(h, "ret", o) :- hpts(h, "this", t), fld(t, "f", o).            // return this.f in get
hpts("main", x, o) :- vcall(r, "get", _, x), hpts("main", r, h), hpts(h, "ret", o).
result(v, h) :- hpts("main", v, h), (v = "x" ; v = "y").
// context-insensitive: one copy of set/get for all receivers
ci(v, h) :- alloc(v, h).
ci("this", h) :- vcall(r, _, _, _), ci(r, h).
ci("v", o) :- vcall(_, "set", a, _), ci(a, o).
fci(t, o) :- ci("this", t), ci("v", o).
ci("ret", o) :- ci("this", t), fci(t, o).
ci(x, o) :- vcall(_, "get", _, x), ci("ret", o).
result_ci(v, h) :- ci(v, h), (v = "x" ; v = "y").
DL
souffle -D- obj.dl

Output (complete):

---------------
result
v   h
===============
x   hA
y   hB
===============
---------------
result_ci
v   h
===============
x   hA
x   hB
y   hA
y   hB
===============

What to notice: with the receiver object as context, x gets only hA and y only hB (relation result); without contexts, set and get are shared and both variables get both objects (result_ci) — the §3 trace.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Call-string sensitivity (k-CFA)	Separates calls by the last \(k\) call sites; wrappers deeper than \(k\) merge	\(S^k\) contexts · 1–2-CFA feasible	Facts per (context, variable)	Low on top of a solver (a push function)	Functional-language CFA, C analyzers, Doop's call-site variants
Cloning and summaries	Cloning: exact for non-recursive programs; summaries: the same with one analysis per function (Theorem 19.7.9)	cloning exponential (BDDs); summaries linear to exponential in summary size	Per-path facts, or per-function summaries	High (BDDs, or symbolic summaries)	bddbddb; LLVM function-attrs and Go parameter tags (coarse summaries)
Object and type sensitivity	Object: the most useful for OO code; type: coarser (Theorem 19.7.10)	\(H^k\) / \(T^k\) contexts · 2-object+1-heap practical; type much cheaper	Facts per receiver object or class	Medium (heap contexts)	Java analyses (Doop, WALA, Soot)

Choose call strings for procedural code where precision comes from wrappers and helpers, with small \(k\). Choose summaries when every function must be analysed once (compilers: attribute inference) or cloning explodes. Choose object sensitivity (or type sensitivity for speed) for object-oriented programs, where the receiver is the best predictor of behavior.

9. Assessment¶

Quiz: kcfa-wrapper, kcfa-contexts-count (tag call-strings); summary-id, llvm-where-function-attrs (tag cloning-summaries); objsens-box, typesens-merge (tag object-sensitivity).
Drill: none; the context-sensitive rules are the Andersen rules over (context, variable) pairs, so ./course drill points-to-andersen covers the solving, and the quiz asks for contexts and results on concrete programs.
Flashcards: tags call-strings, cloning-summaries, object-sensitivity.
Exercises: none in the Pebble code; modify the Soufflé boxes (2-CFA, 2-object) as self-study.

References¶

See the chapter references.

Lesson 19.7 — Context sensitivity: call strings, cloning and summaries, object and type sensitivity¶

1. Problem and motivation¶

Call-string sensitivity (k-CFA)¶

Cloning and summaries¶

Object and type sensitivity¶

2. Definitions and algorithms¶

Call-string sensitivity (k-CFA)¶

Cloning and summaries¶

Object and type sensitivity¶

3. Worked example¶

Call-string sensitivity (k-CFA)¶

Cloning and summaries¶

Object and type sensitivity¶

4. Invariants and correctness¶

Call-string sensitivity (k-CFA)¶

Cloning and summaries¶

Object and type sensitivity¶

5. Complexity¶

6. Variants and refinements¶

Call-string sensitivity (k-CFA)¶

Cloning and summaries¶

Object and type sensitivity¶

7. In real compilers¶

Call-string sensitivity (k-CFA)¶

Cloning and summaries¶

Object and type sensitivity¶

8. Comparison¶

9. Assessment¶

References¶