Lesson 19.6 — Flow sensitivity and field sensitivity¶

Techniques: flow-sensitive points-to analysis with strong updates — dense (one fact per program point) and staged sparse (Hardekopf and Lin's SFS, 2011); field sensitivity — field-insensitive, field-based and field-sensitive object models, Pearce's offset constraints for C with positive-weight-cycle collapse · Pebble implements: nothing (the lab is flow- and field-insensitive; field sensitivity is a ★ stretch goal) · Prerequisites: Lesson 19.4; dataflow frameworks (Ch 14); Memory SSA (Lesson 16.8, and Lesson 19.10) · Time: 4–5 hours

1. Problem and motivation¶

The analyses of Lessons 19.4–19.5 keep one set per variable and one set per object. Two kinds of information are thrown away.

Flow-sensitive points-to (SFS)¶

Order. In

1: s = &o     2: *s = &a     3: x = *s     4: *s = &b     5: y = *s

x can only be &a and y only &b, because the store in 4 overwrites o completely — a strong update. A flow-insensitive analysis gives both {a, b}. Flow-sensitive analysis computes a points-to graph per program point. Done densely (a map from every location to a set at every point, like the dataflow of Ch 14) it is far too slow for large programs. Hardekopf and Lin's staged, sparse flow-sensitive analysis (SFS) first runs a cheap flow-insensitive analysis to learn which store can reach which load, builds def-use chains for memory from it (the same idea as Memory SSA), and then propagates flow-sensitive facts only along those chains [HL11]. In SSA form, top-level variables are already flow-sensitive for free: every SSA value has one definition.

Field sensitivity¶

Structure. With struct pair { int *first; int *second; }, storing &x into s.first and &y into s.second, a field-insensitive analysis (the lab) says both fields point to {x, y}. A field-sensitive analysis keeps one node per (object, field) and answers {x} and {y}. A field-based analysis keeps one node per field name, shared by all objects of the struct type. For C, where pointers to fields are computed by arithmetic and cast, Pearce, Kelly and Hankin model fields as offsets inside objects [PKH07]; GCC's points-to analysis is field-sensitive in the same way [GCC-StructAlias].

2. Definitions and algorithms¶

Flow-sensitive points-to (SFS)¶

Definition 19.6.1 (Flow-sensitive points-to facts, strong update)

A points-to graph is a function \(G : \mathit{Loc} \to \mathcal{P}(\mathit{Obj})\) (locations are variables and objects). A flow-sensitive analysis computes \(G_\ell^{\mathrm{in}}\) and \(G_\ell^{\mathrm{out}}\) for every program point \(\ell\). An object is a singleton if it represents at most one concrete location at a time (a global, or a local not in a recursive function; not a heap allocation site in a loop, which is a summary object). A store \({*}p = q\) performs a strong update if \(G^{\mathrm{in}}(p) = \{o\}\) with \(o\) a singleton: the old contents of \(o\) are replaced. Otherwise it performs weak updates: the new targets are added.

Algorithm 19.6.2 (Dense flow-sensitive points-to analysis)

Input: a CFG whose nodes are the four statement forms of Definition 19.4.1.
Output: \(G_\ell^{\mathrm{in}}\) for every node \(\ell\).
Precondition: none.
Postcondition: the least fixed point of the equations below, which is sound (Theorem 19.6.6).
Invariant: the worklist holds every node whose input changed since it was last processed (Ch 14).

IN[ℓ] = ⊔ { OUT[k] : k ∈ preds(ℓ) }        # pointwise union
OUT[ℓ] = f_ℓ(IN[ℓ]) where, with G = IN[ℓ]:
  p = &a:  G[p ↦ {a}]                         # top-level assignments are strong
  p = q:   G[p ↦ G(q)]
  p = *q:  G[p ↦ ⋃ { G(o) : o ∈ G(q) }]
  *p = q:  if G(p) = {o} and o is a singleton: G[o ↦ G(q)]          # strong update
           else: G[o ↦ G(o) ∪ G(q) for each o ∈ G(p)]              # weak update
solve with the worklist algorithm of Ch 14; the lattice has height |Loc| · |Obj|

Algorithm 19.6.3 (Staged, sparse flow-sensitive analysis, SFS)

Input: the program in SSA form for top-level variables; a sound flow-insensitive analysis \(\mathrm{pts}_A\) (the auxiliary analysis, e.g. Andersen).
Output: flow-sensitive sets for every SSA variable and, per store, for the objects it defines.
Precondition: \(\mathrm{pts}_A\) is sound (Theorem 19.4.12).
Postcondition: the same result as Algorithm 19.6.2 (Theorem 19.6.7, [HL11]).
Invariant: facts flow only along def-use edges; every store–load pair that can communicate through an object in some execution is connected by a chain of such edges.

function SFS(program, ptsA):
    # stage 1: memory SSA per object, using the auxiliary sets
    for each store *p = q:  it defines (χ) every o ∈ ptsA(p)
    for each load  x = *p:  it uses  (μ) every o ∈ ptsA(p)
    place φ's per object at iterated dominance frontiers; rename   # Lesson 19.10
    # the def-use graph: top-level SSA edges + (store → load) / (store → store) edges per object
    # stage 2: sparse propagation
    W ← all nodes;  pts(v) ← ∅, pts(def of o at store s) ← ∅
    while W ≠ ∅:
        n ← pop(W)
        apply the transfer of Algorithm 19.6.2 at n, reading facts only from n's def-use predecessors
        (a strong update at store s for o ignores the incoming definition of o)
        push the def-use successors of every fact that changed
    return pts

Field sensitivity¶

Definition 19.6.4 (Object models for aggregates)

Let objects have fields \(f \in \mathit{Fld}\) (or byte offsets). The field-insensitive model has one abstract location per object \(o\); a field access p->f reads or writes location \(o\) for each \(o \in \mathrm{pts}(p)\). The field-based model has one location per field name \(f\), shared by all objects: p->f accesses location \(f\) regardless of \(\mathrm{pts}(p)\). The field-sensitive model has one location \(o.f\) per object and field; p->f accesses \(o.f\) for each \(o \in \mathrm{pts}(p)\). Pearce's model for C writes field addresses as offsets: p = &q->f becomes the offset constraint \(\mathrm{pts}(p) \supseteq \{ o.(k + \mathrm{off}(f)) : o.k \in \mathrm{pts}(q) \}\), keeping only offsets inside the object.

Algorithm 19.6.5 (Field-sensitive Andersen with offset constraints)

Input: constraints of Definition 19.4.1 over locations \(o.k\), plus offset constraints \(p \supseteq q + d\).
Output: the least solution over field locations.
Precondition: every object has a known number of fields (byte offsets) \(\lvert o \rvert\).
Postcondition: a solution of all constraints; ⊆ the field-insensitive solution under the projection \(o.k \mapsto o\) (Theorem 19.6.8).
Invariant: every location in a set is inside its object (\(0 \le k < \lvert o \rvert\)).

# Algorithm 19.4.4, with one extra edge kind and a guard:
for each offset constraint p ⊇ q + d:   add a weighted edge q →(d) p
when propagating along q →(d) p:  for o.k in Δ(q): if k + d < |o|: pts[p] ∪= {o.(k + d)}
load p = *q (field k of the pointee):  for o.j in pts[q]: add edge o.(j+k) → p
if a cycle of weighted edges has positive total weight (a PWC):
    collapse every object flowing around it to one field-insensitive location   # [PKH07]

3. Worked example¶

Flow-sensitive points-to (SFS)¶

The program of §1 as a straight line (o a singleton global; \(\mathrm{pts}\) shown for x, y and the contents of o):

node	statement	Algorithm 19.6.2 after the node	flow-insensitive (Andersen)
1	`s = &o`	s	s
2	`*s = &a`	strong: o	o
3	`x = *s`	x	x
4	`*s = &b`	strong: o	o
5	`y = *s`	y	y

SFS reaches the same answer with less work. The auxiliary Andersen analysis gives \(\mathrm{pts}_A(s) = \{o\}\), so stores 2 and 4 define \(o\) and loads 3 and 5 use it. Renaming \(o\) over the straight line gives the def-use edges \(2 \to 3\) (version \(o_1\)) and \(4 \to 5\) (version \(o_2\)), and \(2 \to 4\) as the incoming definition of the store at 4. The sparse phase visits node 3 only with the fact from 2 (\(x = \{a\}\)), and the strong update at 4 ignores its incoming \(o_1\), so node 5 sees only \(o_2 = \{b\}\). With a branch around node 4 (if c: *s = &b), a φ for \(o\) merges \(\{a\}\) and \(\{b\}\) and y gets \(\{a, b\}\) — a join, not a strong update.

Field sensitivity¶

The C program of the GCC box (§7): s.first = &x; s.second = &y; ps = &s; if (k) ps->first = ps->second;.

location	field-insensitive	field-based (fields `first`, `second`)	field-sensitive
contents of `s` / `s.first`	{x, y} (one location)	first:	s.first:
`s.second`	(same location)	second:	s.second:
the loaded `*s.second` pointer	{x, y}	{y}	{y}

The store ps->first = ps->second really can put &y into s.first, so s.first is \(\{x, y\}\) in every model; only the field-insensitive model also pollutes s.second with x. GCC's output shows exactly the field-sensitive column: s.0+64 = { x y } and s.64+64 = { y } (fields named by bit offset and size), and { x y } for both when field sensitivity is switched off.

4. Invariants and correctness¶

Flow-sensitive points-to (SFS)¶

Theorem 19.6.6 (Dense flow-sensitive analysis is sound and refines Andersen)

The least fixed point of Algorithm 19.6.2 is sound for every execution that follows the CFG, and \(\bigcup_\ell G^{\mathrm{out}}_\ell(v) \subseteq \mathrm{pts}^*(v)\) for every location \(v\).

Proof

Soundness. By induction on the length of an execution path, the concrete store after node \(\ell\) is described by \(G^{\mathrm{out}}_\ell\): the join at \(\mathrm{IN}\) covers every predecessor, and each transfer is sound. The only non-obvious case is the strong update: if \(G(p) = \{o\}\) with \(o\) a singleton, then in every execution reaching this node \(p\) holds the address of the one concrete location \(o\) represents (or is null, and the store traps), so after the store that location holds exactly the value of \(q\); replacing \(G(o)\) loses nothing. Refinement. \(\mathrm{pts}^*\), taken as the same graph at every point, is a post-fixed point of every transfer function: each transfer produces a graph whose sets are subsets of Andersen's constraints' right-hand sides, and strong updates only produce smaller sets than weak ones. By the least fixed point property (Knaster–Tarski, Ch 14) the dense solution lies below it at every point.

Theorem 19.6.7 (SFS equals dense flow-sensitive analysis)

If the auxiliary analysis is sound, the sparse propagation of Algorithm 19.6.3 computes, for every SSA variable and every load, the same sets as Algorithm 19.6.2.

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

The dense analysis propagates the fact for an object \(o\) through program points where nothing defines \(o\) unchanged; only stores that may write \(o\) change it and only loads that may read \(o\) use it. By soundness of the auxiliary analysis, every store that can write \(o\) in the dense solution (its \(G(p) \ni o\), which is below \(\mathrm{pts}^*\) by Theorem 19.6.6, hence below the auxiliary sets) has a χ for \(o\), and every load that can read \(o\) has a μ. The memory SSA renaming connects each μ/χ to the definitions that reach it along CFG paths, which are exactly the definitions whose facts the dense analysis would join at that point. So both analyses apply the same transfer functions to the same joins, and their least fixed points coincide. The auxiliary analysis affects only which edges exist, not the facts: a spurious χ for an object the store never writes in the dense solution performs a weak update with an empty contribution.

Field sensitivity¶

Theorem 19.6.8 (Field sensitivity refines field insensitivity)

Let \(\pi(o.k) = o\) project field locations to objects. For a program without positive-weight cycles, the least field-sensitive solution \(\mathrm{pts}_F\) satisfies \(\pi(\mathrm{pts}_F(v)) \subseteq \mathrm{pts}^*(v)\) for every variable, and \(\bigcup_k \pi(\mathrm{pts}_F(o.k)) \subseteq \mathrm{pts}^*(o)\) for every object.

Proof

Map the field-insensitive least solution \(\mathrm{pts}^*\) to field locations by \(\hat{\mathrm{pts}}(v) = \{ o.k : o \in \mathrm{pts}^*(v), 0 \le k < \lvert o \rvert \}\) and \(\hat{\mathrm{pts}}(o.k) = \hat{\mathrm{pts}}(o)\). This is a solution of the field-sensitive constraints: every field-sensitive constraint projects (under \(\pi\)) to the field-insensitive constraint of the same statement, which \(\mathrm{pts}^*\) satisfies, and \(\hat{\mathrm{pts}}\) contains all fields of every object it mentions, so offset shifts stay inside it. The least field-sensitive solution is below every solution, in particular below \(\hat{\mathrm{pts}}\); projecting gives the claim.

Field-based is not field-sensitive

The field-based model merges field \(f\) of all objects, so it can be less precise than the field-insensitive one (two unrelated node objects share next), and in C, where a pointer to a field can be produced by arithmetic or a cast from a pointer to another field, it can be unsound: an access through a cast pointer names the wrong field. Field-based analysis is used for Java-like languages, where every field access names its field statically [Hin01].

5. Complexity¶

Let \(n\) be the number of statements (CFG nodes), \(v\) variables, \(k\) objects (field locations for the field-sensitive model), \(F\) the maximum number of fields per object.

Technique	Time (worst)	Time (typical)	Space
Dense flow-sensitive	\(O(n \cdot h)\) transfer applications with lattice height \(h = (v + k) \cdot k\), each \(O((v + k) k)\)	infeasible beyond ~10^5 lines: facts at every point	\(O(n \cdot (v + k) \cdot k)\)
SFS	auxiliary analysis + memory SSA, then sparse propagation: \(O(e_{du} \cdot k)\) set operations along \(e_{du}\) def-use edges	scales to millions of lines of code, as the title of [HL11] says	\(O(e_{du} \cdot k)\)
Field-sensitive (Pearce)	Andersen's \(O(N^3)\) with \(N = v + kF\) locations	slower than field-insensitive by a factor that depends on how much code uses structs [PKH07]	\(O(N^2)\)

Justification. The dense analysis stores a full graph at every point; each point's input can change at most \(h\) times. SFS replaces the \(n\) program points per object by the def-use edges of that object's memory SSA, whose number is linear in practice but can be \(O(n^2)\) per object in the worst case (a store and a load in every branch of a switch). Field sensitivity multiplies the number of locations by the number of fields. Pathological family for field sensitivity: a loop p = p + 1 over a struct pointer creates a positive-weight cycle: without collapse the solver would derive \(o.0, o.1, o.2, \dots\) up to \(\lvert o \rvert\), \(F\) derivations per object per cycle; Pearce et al. collapse such objects to one location [PKH07].

Flow-sensitive points-to (SFS)¶

Semi-sparse flow-sensitive analysis (Hardekopf and Lin, POPL 2009): sparse only for top-level variables (via SSA), dense for memory; trade-off: simpler, slower than SFS.
Strong updates for heap objects via recency abstraction or singleton reasoning; trade-off: extra abstraction per allocation site.
Versioned SFS (in SVF, "VFS"): shares points-to sets between memory versions that must be equal; trade-off: a preprocessing pass for large memory savings.

Field sensitivity¶

Field-based (Definition 19.6.4): cheapest, used for Java call-graph clients; trade-off: merges all objects.
Structure-type unification in Steensgaard-style analyses; trade-off: collapses on type-unsafe accesses.
Byte-offset fields with bit sizes (GCC: s.0+64 is bits 0–63): handles unions and overlapping accesses; trade-off: more locations; the parameter max-fields-for-field-sensitive caps them, and GCC sets it only at -O2 and above (gcc/opts.cc), which is why the field splitting of §7 appears at -O2 but not at -O1.

7. In real compilers¶

Flow-sensitive points-to (SFS)¶

SVF; production compilers

SVF svf/lib/WPA/FlowSensitive.cpp — FlowSensitive::initialize runs the auxiliary Andersen (AndersenWaveDiff) and builds the sparse value-flow graph from memory SSA; processSVFGNode applies the transfer per node kind [SVF-FS, SX16] (SVF 3.3). GCC and LLVM have no flow-sensitive points-to analysis for memory: LLVM gets flow sensitivity for top-level values from SSA and for memory from MemorySSA-based queries (Lesson 19.10) that combine local alias answers with def-use chains — the same staging idea, applied per query.

SVF's staged flow-sensitive analysis

Reproduce (curl 8.5.0; source at tag SVF-3.3):

curl -sL https://raw.githubusercontent.com/SVF-tools/SVF/SVF-3.3/svf/lib/WPA/FlowSensitive.cpp -o FlowSensitive.cpp
sed -n '/^void FlowSensitive::initialize/,/^}/p' FlowSensitive.cpp | grep -nE 'ander|svfg|memSSA'
grep -nE 'dyn_cast<(Addr|Copy|Gep|Load|Store|PHI)SVFGNode>' FlowSensitive.cpp

Output (complete):

9:    ander = AndersenWaveDiff::createAndersenWaveDiff(getPAG());
28:    svfg = memSSA.buildPTROnlySVFG(ander);
30:    setGraph(svfg);
236:    if (AddrSVFGNode* addr = SVFUtil::dyn_cast<AddrSVFGNode>(node))
242:    else if (CopySVFGNode* copy = SVFUtil::dyn_cast<CopySVFGNode>(node))
248:    else if (GepSVFGNode* gep = SVFUtil::dyn_cast<GepSVFGNode>(node))
254:    else if (LoadSVFGNode* load = SVFUtil::dyn_cast<LoadSVFGNode>(node))
260:    else if (StoreSVFGNode* store = SVFUtil::dyn_cast<StoreSVFGNode>(node))
266:    else if (PHISVFGNode* phi = SVFUtil::dyn_cast<PHISVFGNode>(node))
662:    if (const StoreSVFGNode* store = SVFUtil::dyn_cast<StoreSVFGNode>(node))

What to notice: stage 1 is visible in initialize: an Andersen analysis (createAndersenWaveDiff) feeds memSSA.buildPTROnlySVFG, the sparse def-use graph; stage 2 dispatches on the SVFG node kinds — address, copy, GEP, load, store, phi — exactly the transfer functions of Algorithm 19.6.2 applied only at def-use nodes.

Field sensitivity¶

GCC and LLVM

GCC gcc/tree-ssa-structalias.cc — get_constraint_for_component_ref builds offset constraints; variables are split into fields (s.0+64) up to max-fields-for-field-sensitive [GCC-StructAlias] (GCC 14.2). LLVM gets field-level precision without points-to sets: BasicAA's offset reasoning (Lesson 19.2) and TBAA's struct paths (Lesson 19.3) separate fields of the same object.

GCC's field-sensitive points-to sets, and the same program field-insensitively

Reproduce (gcc-14 14.2.0; Linux x86-64):

cat > fs.c <<'C'
struct pair { int *first; int *second; };
int f(int k) {
  int x = 1, y = 2;
  struct pair s;
  s.first = &x;
  s.second = &y;
  struct pair *ps = &s;
  if (k) ps->first = ps->second;
  return *s.first + *s.second;
}
C
for flags in "" "--param=max-fields-for-field-sensitive=0"; do
  echo "== gcc-14 -O2 $flags"
  gcc-14 -O2 -fno-tree-sra -fdump-tree-ealias-details $flags -c fs.c
  d=$(ls fs.c.*t.ealias)
  sed -n '/^Points-to sets/,/^Alias information/p' "$d" | grep -E '^(s[.0-9+]*|_[124]) = '
  rm -f "$d"
done

Output (complete):

== gcc-14 -O2 
s.0+64 = { x y }
s.64+64 = { y }
_1 = { y } same as s.64+64
_2 = { x y } same as s.0+64
_4 = { y } same as s.64+64
== gcc-14 -O2 --param=max-fields-for-field-sensitive=0
s = { x y }
_1 = { x y } same as s
_2 = { x y } same as s
_4 = { x y } same as s

What to notice: with the default -O2 parameters s is split into s.0+64 (the first pointer, bits 0–63) with { x y } and s.64+64 (the second) with { y }: the field-sensitive column of the §3 table. With max-fields-for-field-sensitive=0, GCC keeps one variable s with { x y }, and the pointer loaded from s.second (_1) now may point to x too.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Flow-sensitive points-to (SFS)	Per-point facts with strong updates; ⊆ Andersen (Theorem 19.6.6); SFS = dense (Theorem 19.6.7)	dense: infeasible at scale · SFS: auxiliary + sparse, millions of lines [HL11]	Sets per SSA variable and per memory version	High (memory SSA per object, strong-update rules)	SVF, bug finders (null dereference, use-after-free), security analyses
Field sensitivity	field-sensitive ⊆ field-insensitive (Theorem 19.6.8); field-based incomparable, unsound for C	locations × fields · slower than field-insensitive [PKH07]	Sets per field (`s.0+64`)	Medium (offsets, PWC collapse)	GCC's points-to, SVF, Java analyses (field-based or field-sensitive)

Choose flow sensitivity when a client needs strong updates — null checks, typestate, use-after-free — and use the staged sparse form to afford it; for optimization, SSA plus MemorySSA give most of the benefit. Choose field sensitivity for any language with structs; choose field-based only for type-safe languages and cheap call-graph clients.

9. Assessment¶

Quiz: fs-strong-update, sfs-stages (tag flow-sensitive); field-models-table, field-based-unsound (tag field-sensitivity).
Drill: none: flow-sensitive and field-sensitive analyses reuse the constraint rules of the points-to-andersen drill with more locations, and the quiz asks for them on concrete programs. ./course drill dataflow-table (Ch 14) practises the dense worklist of Algorithm 19.6.2.
Flashcards: tags flow-sensitive, field-sensitivity.
Exercises: lab ★ stretch goal "field sensitivity" (labs/ch19-points-to/SPEC.md).

References¶

See the chapter references.

Lesson 19.6 — Flow sensitivity and field sensitivity¶

1. Problem and motivation¶

Flow-sensitive points-to (SFS)¶

Field sensitivity¶

2. Definitions and algorithms¶

Flow-sensitive points-to (SFS)¶

Field sensitivity¶

3. Worked example¶

Flow-sensitive points-to (SFS)¶

Field sensitivity¶

4. Invariants and correctness¶

Flow-sensitive points-to (SFS)¶

Field sensitivity¶

5. Complexity¶

6. Variants and refinements¶

Flow-sensitive points-to (SFS)¶

Field sensitivity¶

7. In real compilers¶

Flow-sensitive points-to (SFS)¶

Field sensitivity¶

8. Comparison¶

9. Assessment¶

References¶