Theory test — Chapter 19¶
59 questions; you pass at 80 %. This page shows the questions only: take the test in the terminal, where every answer is graded and explained.
./course quiz 19 # interactive
./course quiz template 19 -o answers/ch19.yaml # or fill in a file ...
./course quiz grade 19 # ... and grade it
alias-answers-table · mapping · 1 pt · 01-memory-and-alias-queriesIn one function, %p4 = getelementptr i8, ptr %p, i64 4, %p0 = getelementptr i8, ptr %p, i64 0,
%buf = alloca [16 x i8], %b8 = getelementptr i8, ptr %buf, i64 8; %p, %q are ordinary
pointer arguments. Accesses: store i64 to %p (8 bytes), store i32 to %p0, store i32 to %p4,
store i32 to %q, store i64 to %b8. Give the alias answer (no, may, partial or must) for each pair.
p-p0, p-p4, p0-p4, p-q, b8-qalias-partial-offset · number · 1 pt · 01-memory-and-alias-queriesaa-eval prints PartialAlias (off N): i64* %p, i32* %p4 for %p4 = getelementptr i8, ptr %p, i64 4.
What is N?
modref-calls · mapping · 1 pt · 01-memory-and-alias-queries%q is a pointer argument that has already been passed to earlier calls. Give the mod/ref answer
(nomodref, ref, mod or modref) of each call for the location %q:
@pure(i32) declared memory(none); @reader(ptr %q) declared memory(read);
@argwriter(ptr %q) declared memory(argmem: write); @unknown() with no attributes.
pure, reader, argwriter, unknownmodref-lattice-meet · single · 1 pt · 01-memory-and-alias-queriesTwo alias analyses answer Ref and Mod for the same call and location. What does LLVM's AAResults return?
- ModRef, the join of the two answers
- NoModRef, the intersection of the two answers
- Ref, the first member's answer
- Mod, because writes are more important than reads
aa-chain-answers · mapping · 1 pt · 01-memory-and-alias-queriesint f(int *restrict a, float *b, int *c) { *a = 1; *b = 2.0f; *c = 3; return *a; } compiled by clang
with TBAA. With -aa-pipeline=basic-aa,tbaa, which member gives the (NoAlias) answer for each pair of stores?
Write basicaa or tbaa.
a-b, a-c, b-cllvm-where-aa-chain · single · 1 pt · 01-memory-and-alias-queriesIn llvm/lib/Analysis/AliasAnalysis.cpp (LLVM 23.1.2), when does the loop over AAs in AAResults::alias stop early?
- When a member returns NoAlias
- When a member returns anything other than MayAlias
- When a member returns MustAlias
- Never; it intersects all answers
basicaa-kernel-answers · mapping · 1 pt · 02-local-alias-rulesvoid kern(int *a, struct pt *s, int i) { int local[4]; a[i] = 1; a[i + 1] = 2; s->x = 3; s->y = 4; local[i] = 5; g = …; }
with struct pt { int x, y; }, a global int g, and 4-byte accesses. Give BasicAA's answer (no or may) for:
a[i] vs a[i+1] (key ai-ai1), local[i] vs local[0] (li-l0), s->y vs g (sy-g), s->x vs g (sx-g),
a[i] vs s->x (ai-sx).
ai-ai1, li-l0, sy-g, sx-g, ai-sxllvm-where-object-size · text · 1 pt · 02-local-alias-rulesIn BasicAliasAnalysis.cpp (LLVM 23.1.2), which static helper does aliasCheck call to return NoAlias when an access is larger than the entire object on the other side?
capture-uses · set · 1 pt · 02-local-alias-rulesWhich of these uses capture the pointer %x (Definition 19.2.6, with returns counted as captures)?
a) store ptr %x, ptr %p b) store i32 0, ptr %x c) call void @f(ptr captures(none) %x)
d) %i = ptrtoint ptr %x to i64 e) ret ptr %x f) %c = icmp eq ptr %x, null
capture-private-load · single · 1 pt · 02-local-alias-rulesIn int f(void) { int p = 1, l = 2; keep(&l); opaque(); return p + l; }, after clang -O1 which loads remain after the call to opaque()?
- Both p and l are reloaded
- Only l is reloaded; p's value 1 is folded
- Only p is reloaded
- Neither: both values are folded
globalsaa-summary · mapping · 1 pt · 02-local-alias-rulesstatic int counter; int shared; — set_shared(x) writes only shared; bump() does counter++;
log_it(int) is an external function with no attributes. f calls all three. With
-aa-pipeline=globals-aa,basic-aa, give the mod/ref answer (nomodref or modref) for @counter at each call.
set_shared, bump, log_itglobalsaa-callback · single · 1 pt · 02-local-alias-rulesFor an external declaration, which attributes let GlobalsAA assume it cannot access the module's non-address-taken internal globals?
- readonly alone
- nocallback and nosync
- nounwind and willreturn
- noinline
tbaa-pairs · mapping · 1 pt · 03-type-and-scope-rulesstruct A { short s; int i; }; struct B { int k; struct A a; }; (offsets B.k 0, B.a 4, A.s 0, A.i 4), clang TBAA.
Tags: b->a.i = (B, int, 8), b->a.s = (B, short, 4), b->k = (B, int, 0), *p = (int, int, 0) for int *p,
*q = (short, short, 0), a->i = (A, int, 4). Give TBAA's answer (no or may) for the pairs
bai-bk, bai-bas, bai-p, bai-ai, bai-q, bk-ai.
bai-bk, bai-bas, bai-p, bai-ai, bai-q, bk-aitbaa-char-exemption · single · 1 pt · 03-type-and-scope-rulesWhy does TBAA never answer NoAlias for a char access against anything in clang's type tree?
- Because char accesses are always 1 byte
- Because
omnipotent charis an ancestor of every scalar type, so a char tag accesses the whole common type - Because clang does not attach TBAA tags to char accesses
- Because char is in a different type tree
llvm-where-tbaa-lca · text · 1 pt · 03-type-and-scope-rulesIn TypeBasedAliasAnalysis.cpp (LLVM 23.1.2), which function computes the least common ancestor of two access types (and makes matchAccessTags answer MayAlias when it returns null)?
scoped-noalias-query · mapping · 1 pt · 03-type-and-scope-rulesScopes s1, s2 in one domain. Access I: alias.scope {s1}, noalias {s2}. Access J: alias.scope {s2}, no noalias list.
Access K: no alias.scope list, noalias {s1}. Give ScopedNoAliasAA's answer (no or may) for I-J, I-K, J-K.
i-j, i-k, j-krestrict-semantics · single · 1 pt · 03-type-and-scope-rulesWhat does restrict on a parameter int *restrict p promise in C11?
- p is never null
- p points to a fresh heap object
- During the function, an object accessed through p and modified is accessed only through pointers based on p
- No other pointer of the same type exists anywhere in the program
andersen-running-pts · mapping · 1 pt · 04-andersenAndersen's analysis on: p = &a; q = &b; r = &p; s = q; *r = s; t = *r; u = &c; q = u; b = t; q = b.
Give pts(q), pts(u), pts(a), pts(r) (write {} for empty).
q, u, a, randersen-edges-step3 · set · 1 pt · 04-andersenSame program, worklist started with p, q, r, u in that order (FIFO). Which new constraint-graph edges are
added when r is popped (step 3)? Write edges as x->y.
cycle-collapse-online · set · 1 pt · 04-andersenSame program with online cycle detection. Which nodes are collapsed into one when the edge s → p is added?
cycle-lazy-trigger · number · 1 pt · 04-andersenWith lazy cycle detection (and the same FIFO order), at which worklist step is the cycle collapsed — the first step whose propagation along an edge finds two equal non-empty sets?
gcc-where-hcd · text · 1 pt · 04-andersenIn GCC 14's tree-ssa-structalias.cc, which function implements the phase printed as "Finding indirect cycles" (hybrid cycle detection)?
wave-rounds · number · 1 pt · 04-andersenHow many rounds does wave propagation (Algorithm 19.4.9) need on the running example, counting the final round that adds no edge?
wave-topo · single · 1 pt · 04-andersenWhy does one wave in topological order satisfy every edge present at the start of the round?
- Because points-to sets never exceed the number of objects
- Because after collapsing cycles the graph is acyclic, so every node's predecessors are final before it propagates
- Because loads and stores are handled before copies
- Because the worklist is FIFO
steens-running-pts · mapping · 1 pt · 05-unificationSteensgaard's analysis on the same running example. Give pts(u), pts(a), pts(r).
u, a, rsteens-join-step5 · set · 1 pt · 05-unificationWhich program variables are in the class unified at step 5 (*r = s) of Steensgaard's trace (ignore fresh τ cells)?
llvm-where-cfl-steens · single · 1 pt · 05-unificationWhat does the header comment of llvm/lib/Analysis/CFLSteensAliasAnalysis.cpp at llvmorg-15.0.0 compare its precision to?
- Andersen's analysis
- Roughly a one-level context-sensitive Steensgaard's algorithm
- Type-based alias analysis
- Flow-sensitive points-to analysis
das-u · set · 1 pt · 05-unificationDas's one-level flow on the running example. What is pts(u)?
das-between · multi · 1 pt · 05-unificationWhich statements about Das's one-level flow are true?
- Its sets contain Andersen's sets
- Its sets are contained in Steensgaard's sets
- It uses inclusion at every level of indirection
- Every flow edge a → b keeps D(a) = D(b)
fs-strong-update · mapping · 1 pt · 06-flow-and-field-sensitivitys = &o; *s = &a; x = *s; *s = &b; y = *s (o a singleton global). Give pts(x) and pts(y) flow-sensitively
(keys x, y) and flow-insensitively (keys x-fi, y-fi).
x, y, x-fi, y-fisfs-stages · sequence · 1 pt · 06-flow-and-field-sensitivityPut the steps of staged sparse flow-sensitive analysis (SFS) in order:
a) sparse flow-sensitive propagation along def-use edges; b) an auxiliary flow-insensitive analysis;
c) memory SSA (def-use chains) per object from the auxiliary sets.
field-models-table · mapping · 1 pt · 06-flow-and-field-sensitivitystruct pair { int *first; int *second; } s; s.first = &x; s.second = &y; ps = &s; if (k) ps->first = ps->second;
What may the second field (s.second) point to under the field-insensitive (insensitive), field-based (based)
and field-sensitive (sensitive) models?
insensitive, based, sensitivefield-based-unsound · single · 1 pt · 06-flow-and-field-sensitivityWhy can a field-based analysis be unsound for C?
- Because it has too many locations
- Because a pointer to one field can be produced by arithmetic or casts from a pointer to another field, so the accessed field is not always the named one
- Because it ignores allocation sites
- Because it cannot handle recursion
kcfa-wrapper · mapping · 1 pt · 07-context-sensitivityint *id(int *v) { return v; } int *w(int *v) { return id(v); /* site d */ } and in main
x = w(&a); /* c1 */ y = w(&b); /* c2 */. Give pts(x) and pts(y) under 1-CFA (keys x1, y1) and 2-CFA (x2, y2).
x1, y1, x2, y2kcfa-contexts-count · number · 1 pt · 07-context-sensitivityA function h is called only from w (one call site d); w is called from three call sites c1, c2, c3 in main. How many contexts does 2-CFA create for h?
summary-id · set · 1 pt · 07-context-sensitivityWith the summary Summary(id) = {ret ↦ P1} instantiated at y = id(&b), what does y point to?
llvm-where-function-attrs · single · 1 pt · 07-context-sensitivityIn llvm/lib/Transforms/IPO/FunctionAttrs.cpp, over what unit does the pass that adds memory(...) (addMemoryAttrs) work, so that callee summaries are available?
- One basic block at a time
- Strongly connected components of the call graph, bottom-up
- The whole module in one pass, top-down
- Loops of each function
objsens-box · mapping · 1 pt · 07-context-sensitivityb1 = new Box /*h1*/; b1.set(new A /*hA*/); x = b1.get(); b2 = new Box /*h2*/; b2.set(new B /*hB*/); y = b2.get();
with set(v) { this.f = v; }, get() { return this.f; }. Give pts(x), pts(y) under 1-object sensitivity
(keys x, y) and context-insensitively (x-ci, y-ci).
x, y, x-ci, y-citypesens-merge · single · 1 pt · 07-context-sensitivityIn the Box program both Box objects are allocated in class Main. What does 1-type sensitivity give for x?
- {hA}
- {hA, hB}
- {}
- {hB}
datalog-rounds · number · 1 pt · 08-declarative-and-demand-drivenSemi-naive evaluation of the four points-to rules on the running example. After round 0 (the addr facts), how many rounds derive at least one new fact?
datalog-rule-store · single · 1 pt · 08-declarative-and-demand-drivenWhich Datalog rule encodes the store *p = q?
- pts(p, o) :- store(p, q), pts(q, o).
- pts(r, o) :- store(p, q), pts(p, r), pts(q, o).
- pts(q, o) :- store(p, q), pts(p, o).
- pts(p, o) :- store(p, q), pts(q, r), pts(r, o).
demand-relevant-set · set · 1 pt · 08-declarative-and-demand-drivenThe demand-driven query pts(t) on the running example. Which variables end in the relevant set R?
demand-budget · single · 1 pt · 08-declarative-and-demand-drivenWhat does SVF's ContextDDA do when a context-sensitive query exceeds its budget?
- It returns an empty set
- It aborts the analysis
- It downgrades the query to the flow-sensitive answer
- It increases the budget until the query finishes
escape-go-decisions · mapping · 1 pt · 09-escape-and-shapeGo 1.24: sum uses p := &point{1, 2} only locally; leak returns &q for a local q; store assigns
&point{n, n} to a global; slice uses make([]int, 8) only locally. Stack or heap for each allocation?
sum, leak, store, sliceescape-lattice · single · 1 pt · 09-escape-and-shapeAn object allocated in method m is reachable from m's return value but from no global or other thread. Its escape state?
- NoEscape
- ArgEscape
- GlobalEscape
- ThreadEscape
shape-lseg-fixpoint · number · 1 pt · 09-escape-and-shapeSeparation-logic shape analysis of x = null; while (c) { t = malloc(); t->next = x; x = t; } (Lesson 19.9 §3): how many symbolic heaps are in the loop head's set at the fixed point?
shape-vs-pointsto · single · 1 pt · 09-escape-and-shapeWhy can Andersen's analysis not prove that the list built by that loop is acyclic?
- Because it is flow-insensitive only
- Because all nodes come from one allocation site, a single abstract object that points to itself
- Because it does not handle malloc
- Because it is context-insensitive
memssa-phis · set · 1 pt · 10-memory-ssaBlocks (memory ops → successors): A: store a → B; B: none → C, F; C: store b; load a → D, E; D: call → E;
E: load b → B; F: load a; load b → exit. Which blocks get a MemoryPhi?
memssa-clobber-trace · mapping · 1 pt · 10-memory-ssaSame function; a and b never alias; the call may write both. Give the clobbering access of each load
(0 for liveOnEntry, a def number with defs 1 = A.1, 2 = C.1, 3 = D.1, or phi@B / phi@E): C.2, E.1, F.1, F.2.
C.2, E.1, F.1, F.2sroa-partitions · number · 1 pt · 11-memory-optimizationsSROA on struct pair q (8 bytes) with uses memcpy(q, p, 8), load i32 q.hi (bytes 4–7) and load i32 q.lo (bytes 0–3). How many partitions (new allocas) does q become?
sroa-escape · single · 1 pt · 11-memory-optimizationsWhich use prevents SROA from splitting an alloca?
- A memcpy of the whole alloca into another alloca
- A load of an i32 at a constant offset
- Passing the alloca's address to an opaque function
- A lifetime.start marker
dse-table · mapping · 1 pt · 11-memory-optimizations*p = 1; *p = 2; char buf[64]; memset(buf, 0, 64); memcpy(buf, src, 16); *q = 3; consume(buf); *q = 4; buf[0] = 1;
(p, q arguments). What does LLVM 23's dse do to each: store1 (*p = 1), memset, store3 (*q = 3), storebuf (buf[0] = 1)?
Write deleted, shortened or kept.
store1, memset, store3, storebufllvm-where-dse-shorten · text · 1 pt · 11-memory-optimizationsIn DeadStoreElimination.cpp (LLVM 23.1.2), which function shortens a partially overwritten memset or memcpy?
loadpre-insert · number · 1 pt · 11-memory-optimizationsif (c) r = *p + v; else r = v; return r + *p; After GVN's load PRE, how many loads of *p execute on the path
through the then-branch?
forwarding-conditions · multi · 1 pt · 11-memory-optimizationspebble-loadfwd (E2) replaces a load L by the value of a store S when…
- S is L's clobbering access according to the MemorySSA walker
- S dominates L
- S MustAliases L and stores a value of L's type
- S is in the same basic block as L
- S is volatile
memcpyopt-forward · single · 1 pt · 11-memory-optimizationsmemcpy(b, a, 16); memcpy(c, b, 16); with nothing in between. What can MemCpyOpt do?
- Replace the second copy by memcpy(c, a, 16)
- Delete both copies
- Replace both by memmove(c, a, 32)
- Nothing: memcpy is opaque
memcpyopt-memset · number · 1 pt · 11-memory-optimizationsp[0] = 0; p[1] = 0; p[2] = 0; p[3] = 0; with long *p (8-byte longs). MemCpyOpt merges the stores into one memset of how many bytes?
licm-promotion-kind · mapping · 1 pt · 11-memory-optimizationsint total; void acc(const float *a, int n) { for (i) total += (int)a[i]; }. What kind of promotion does
loop-mssa(licm) perform with -aa-pipeline=basic-aa (key basicaa) and basic-aa,tbaa (key basicaa-tbaa)?
Write load-only or full.
basicaa, basicaa-tbaalicm-promotion-safety · multi · 1 pt · 11-memory-optimizationsWhich conditions allow LICM to sink the promoted store to the loop exits?
- A store to the location is guaranteed to execute on every iteration
- The location is a local that is not captured
- The loop contains a call
- No other access in the loop may read or write the location