Theory test — Chapter 15¶

30 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 15                                   # interactive
./course quiz template 15 -o answers/ch15.yaml  # or fill in a file ...
./course quiz grade 15                             # ... and grade it

Question 1 dom-definitions · multi · 1 pt · 01-dominator-algorithms

Which statements hold for every flowgraph with entry r (all nodes reachable, w ≠ r,
sdom = the Lengauer–Tarjan semidominator for a DFS from r)?

If d dom n and e dom n, then d dom e or e dom d.
idom(n) is always a predecessor of n.
Dom is the greatest solution of Dom(r) = {r}, Dom(n) = {n} ∪ ⋂ Dom(p) over the predecessors p, which is why the iterative algorithm starts every other set at ⊤ (all nodes).
sdom(w) is a proper ancestor of w in the DFS tree, and idom(w) is an ancestor-or-self of sdom(w) in the DFS tree.
idom(w) is the nearest common ancestor, in the dominator tree, of w's DFS parent and sdom(w).
In Cooper–Harvey–Kennedy's intersect, the finger with the larger postorder number moves up.
At every moment of a pass, the node set on CHK's doms[] chain from b equals the Dom set the iterative algorithm, run in lockstep, holds for b.

Answer format: letters, e.g. a, c

Question 2 iterative-passes · number · 1 pt · 01-dominator-algorithms

CFG (successors in listed order):

R  -> X1, X4
X1 -> X2
X2 -> X3, X1
X3 -> X4, X2
X4 -> X3

The iterative Dom-set algorithm and Cooper–Harvey–Kennedy both iterate in reverse
postorder (R X1 X2 X3 X4) until a pass changes nothing. How many passes does CHK make,
counting the final pass that changes nothing?

Answer format: a number

Question 3 chk-intersect-walk · sequence · 1 pt · 01-dominator-algorithms

CFG:

A -> B
B -> C, F
C -> D
D -> E, B
E -> G
F -> G
G -> H, C
H ->

RPO is A B F C D E G H; postorder numbers are H=0, G=1, E=2, D=3, C=4, F=5, B=6, A=7.
In pass 1, when CHK processes G, its processed predecessors are F (first) and E, and
doms[] currently holds B→A, F→B, C→B, D→C, E→D. CHK computes intersect(E, F).
Give the sequence of nodes finger1 visits, starting with E, until the two fingers meet.

Answer format: items in order, e.g. A B C

Question 4 lt-semidominators · mapping · 1 pt · 01-dominator-algorithms

CFG (DFS preorder A B C D E F G H, i.e. numbers 1–8 in alphabetical order):

A -> B
B -> C, F
C -> D, G
D -> E, B
E -> F, H
F -> G, H
G -> H, B
H ->

Give the semidominator sdom(w) of every node except A.

Keys: B, C, D, E, F, G, H

Answer format: one value per key

Question 5 lt-sdom-vs-idom · set · 1 pt · 01-dominator-algorithms

Same CFG as the previous question:

A -> B
B -> C, F
C -> D, G
D -> E, B
E -> F, H
F -> G, H
G -> H, B
H ->

For which nodes w is sdom(w) ≠ idom(w)? Write {} if none.

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 6 llvm-where-seminca · text · 1 pt · 01-dominator-algorithms

In LLVM 23, open llvm/include/llvm/Support/GenericDomTreeConstruction.h. Which member
function of SemiNCAInfo computes the semidominators and then the immediate
dominators ("Explicitly define the immediate dominator of each vertex")? Give its name.

Answer format: a short answer

Question 7 dbs-insert-affected · set · 1 pt · 02-incremental-dominators

CFG and its immediate dominators:

A -> B          idom: B=A C=B D=C E=D F=B G=B H=B
B -> C, F
C -> D, G
D -> E, B
E -> F, H
F -> G, H
G -> H, B
H ->

The edge A -> G is inserted. Which nodes change their immediate dominator?
Write {} if none.

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 8 dbs-delete-idoms · mapping · 1 pt · 02-incremental-dominators

Same CFG and idoms as before (B=A C=B D=C E=D F=B G=B H=B):

A -> B
B -> C, F
C -> D, G
D -> E, B
E -> F, H
F -> G, H
G -> H, B
H ->

The edge B -> F is deleted. Give the new immediate dominators of F, G and H.

Keys: F, G, H

Answer format: one value per key

Question 9 incremental-lemmas · multi · 1 pt · 02-incremental-dominators

Which statements about incremental dominator updates are true? (Nodes are reachable
before and after the update unless stated; NCA is taken in the old dominator tree.)

Inserting an edge can only shrink dominator sets (idoms move up the tree); deleting one can only grow them.
After inserting u → v with u reachable, every node whose idom changes gets the same new idom, NCA(u, v).
After deleting u → v with v still reachable, a node outside the dominator subtree of NCA(u, v) can get a new idom.
Deleting an edge u → v where v dominates u never changes the dominator tree.
A lazy DomTreeUpdater that receives {Insert, A, E} and later {Delete, A, E} for an edge absent at the last flush drops both before touching the tree.
If idom(v) = u and the edge u → v is deleted, v always becomes unreachable.

Answer format: letters, e.g. a, c

Question 10 llvm-where-insert · text · 1 pt · 02-incremental-dominators

In LLVM 23's llvm/include/llvm/Support/GenericDomTreeConstruction.h, which static
function of SemiNCAInfo handles an inserted edge whose endpoints were both already in
the dominator tree (the depth-based search)? Give its name.

Answer format: a short answer

Question 11 df-sets · mapping · 1 pt · 03-dominance-frontiers

CFG (idoms: B=A C=B D=C E=D F=B G=B H=B):

A -> B
B -> C, F
C -> D, G
D -> E, B
E -> F, H
F -> G, H
G -> H, B
H ->

Give the dominance frontier DF(n) of every node. Write {} for an empty frontier.

Keys: A, B, C, D, E, F, G, H

Answer format: one value per key (a set: {x, y})

Question 12 frontier-theorems · multi · 1 pt · 03-dominance-frontiers

Which statements about dominance frontiers hold for every flowgraph with entry r?

Y ∈ DF(X) iff X lies on the dominator-tree path from some predecessor of Y up to, but excluding, idom(Y).
A node is never in its own dominance frontier.
DF(X) = DF_local(X) ∪ the DF_up(Z) of X's dominator-tree children Z, so all frontiers can be computed in one children-first walk of the dominator tree.
DF⁺(S ∪ {r}) = DF⁺(S) for every set S, because DF(r) is empty.
The total size Σ|DF(X)| is O(n + m) for every CFG with n nodes and m edges.
In Sreedhar–Gao's DF⁺, a J edge z → y met while walking below the root x adds y to the result only if level(y) ≤ level(x).

Answer format: letters, e.g. a, c

Question 13 df-runner · set · 1 pt · 03-dominance-frontiers

Same CFG and idoms (B=A C=B D=C E=D F=B G=B H=B). In the CHK frontier algorithm, the
join node H has predecessors E, F and G. Into which nodes' frontiers does the runner
that starts at E add H?

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 14 idf-phis · set · 1 pt · 03-dominance-frontiers

Same CFG (DF: A {}, B {B}, C {B,F,G,H}, D {B,F,H}, E {F,H}, F {G,H}, G {B,H}, H {}).
A variable x is assigned only in block E. Where does minimal SSA place phi nodes for x,
i.e. what is DF⁺({E})?

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 15 llvm-where-idf · text · 1 pt · 03-dominance-frontiers

In LLVM 23's llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h,
IDFCalculatorBase::calculate keeps a priority queue of dominator-tree nodes keyed by a
pair. Which property of a dominator-tree node is the first component of that key?

Answer format: a short answer

Question 16 ipdom-trace · mapping · 1 pt · 04-post-dominance-and-control-dependence

CFG:

S -> A, B
A -> C, X
B -> C, D
C -> E
D -> E, L
E ->
X ->
L -> M
M -> L, N
N -> L

X and E are exits; L, M, N form an infinite loop. LLVM connects the virtual exit EXIT to
the roots X, E and N. Give ipdom(n) for S, A, B, C, D, L and M (write EXIT for the
virtual exit).

Keys: S, A, B, C, D, L, M

Answer format: one value per key

Question 17 cd-sets · mapping · 1 pt · 04-post-dominance-and-control-dependence

Same CFG and roots (X, E, N) as the previous question:

S -> A, B
A -> C, X
B -> C, D
C -> E
D -> E, L
E ->
X ->
L -> M
M -> L, N
N -> L

Give CD(n) = { X : n is control dependent on X } for n = C, E and L.

Keys: C, E, L

Answer format: one value per key (a set: {x, y})

Question 18 llvm-where-cd · single · 1 pt · 04-post-dominance-and-control-dependence

LLVM 23's ADCE (llvm/lib/Transforms/Scalar/ADCE.cpp) marks branches live through control
dependence in markLiveBranchesFromControlDependences. What does it use to find the
blocks whose terminators become live?

A DominanceFrontier analysis computed on the forward CFG.
A ReverseIDFCalculator over the post-dominator tree, seeded with the newly live blocks.
A ForwardIDFCalculator over the dominator tree.
An explicit program dependence graph built by ControlDependenceGraph.

Answer format: one letter

Question 19 dfs-edge-kinds · mapping · 1 pt · 05-loop-nesting-forests

CFG (DFS from A, successors in listed order; preorder A B C D F G E):

A -> B, E
B -> C
C -> D, B
D -> F
E -> D, F
F -> C, G
G ->

Classify the non-tree edges C→B, F→C, E→D and E→F as back (retreating), forward or
cross. Write one line per edge, e.g. C-B: back.

Keys: C-B, F-C, E-D, E-F

Answer format: C-B: kind (one of tree, back, forward, cross)

Question 20 natural-loop-body · mapping · 1 pt · 05-loop-nesting-forests

CFG:

A -> B
B -> C, H
C -> D
D -> E, F
E -> D
F -> B, G
G -> C, H
H ->

Its back edges are F→B, G→C and E→D. Give the body of the natural loop of each header.

Keys: B, C, D

Answer format: one value per key (a set: {x, y})

Question 21 havlak-irreducible · mapping · 1 pt · 05-loop-nesting-forests

Same CFG as the edge-classification question (preorder A B C D F G E):

A -> B, E
B -> C
C -> D, B
D -> F
E -> D, F
F -> C, G
G ->

Havlak's algorithm with this DFS creates loops with headers B and C. Classify each as
reducible or irreducible.

Keys: B, C

Answer format: one value per key

Question 22 steensgaard-vs-havlak · set · 1 pt · 05-loop-nesting-forests

Same CFG:

A -> B, E
B -> C
C -> D, B
D -> F
E -> D, F
F -> C, G
G ->

Steensgaard's forest has a single loop, the SCC {B, C, D, F}. Which nodes are its
headers?

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 23 llvm-where-loops · text · 1 pt · 05-loop-nesting-forests

In LLVM 23's llvm/include/llvm/Support/GenericLoopInfoImpl.h, LoopInfoBase::analyze
collects the back edges into a header and then calls a function that performs the
backward CFG traversal to discover the loop's blocks (skipping already discovered
subloops). What is that function's name?

Answer format: a short answer

Question 24 t1t2-limit · number · 1 pt · 06-reducibility

CFG:

A -> B, E
B -> C
C -> D, B
D -> F
E -> D, F
F -> C, G
G ->

Apply T1 (delete a self loop) and T2 (merge a non-entry node with a unique predecessor
into it) until neither applies. How many nodes does the limit graph have?

Answer format: a number

Question 25 derived-sequence · sequence · 1 pt · 06-reducibility

CFG (the one from the natural-loop question):

A -> B
B -> C, H
C -> D
D -> E, F
E -> D
F -> B, G
G -> C, H
H ->

Give the number of nodes of each graph in its derived sequence G, I(G), I(I(G)), …
up to and including the limit, e.g. 9 5 3 1.

Answer format: items in order, e.g. A B C

Question 26 node-splitting-copies · number · 1 pt · 06-reducibility

CFG (a cycle X → Y → Z → X with an entry edge into each of its nodes):

S -> X, Y, Z
X -> Y
Y -> Z
Z -> X, O
O ->

Apply the lesson's node-splitting procedure: T1/T2-reduce; if the limit graph has more
than one node, split the smallest non-entry region with ≥ 2 predecessors, giving each
extra predecessor region its own copy; repeat. How many node copies are created in total
before the graph becomes reducible?

Answer format: a number

Question 27 reducibility-facts · multi · 1 pt · 06-reducibility

Which statements are true?

A CFG is reducible iff, for a depth-first search from the entry, every retreating edge u → v has v dom u.
The limit graph of T1/T2 depends on the order in which the rules are applied.
Tarjan's loop-nesting algorithm can report that a CFG is irreducible without computing dominators.
On a reducible CFG, Steensgaard's forest has the same loops and headers as the natural-loop forest.
LLVM's containsIrreducibleCFG needs LoopInfo in addition to a reverse-postorder traversal.
Node splitting never increases code size by more than a constant factor.
Every cross edge of a DFS closes a cycle.

Answer format: letters, e.g. a, c

Question 28 loop-simplify-shape · mapping · 1 pt · 07-canonical-loop-forms

CFG (natural loops with headers B, C and D):

A -> B
B -> C, H
C -> D
D -> E, F
E -> D
F -> B, G
G -> C, H
H ->

For each header give its preheader (the unique out-of-loop predecessor whose only
successor is the header), or none if LoopSimplify would have to insert one.

Keys: B, C, D

Answer format: one value per key

Question 29 lcssa-phis · set · 1 pt · 07-canonical-loop-forms

CFG, with one loop {H, B, C} (header H, latch C):

A  -> H
H  -> B, X1
B  -> C, X2
C  -> H, X3
X1 ->
X2 ->
X3 ->

A value %v is defined in B and used after the loop. Into which exit blocks does LLVM's
formLCSSA insert a %v.lcssa phi?

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 30 llvm-where-lcssa · text · 1 pt · 07-canonical-loop-forms

In LLVM 23's llvm/lib/Transforms/Utils/LCSSA.cpp, which function inserts the exit-block
phis for a worklist of instructions (and is called by formLCSSA)? Give its name.

Answer format: a short answer