CDCS
Dataflow: Do Not Confuse These
For every dataflow problem, immediately identify:
direction: forward or backward
meet: union or intersection
boundary condition
initial value
transfer function
High-yield table:
Reaching Definitions: forward, union, may analysis
Available Expressions: forward, intersection, must analysis
Liveness: backward, union, may analysis
Very Busy Expressions: backward, intersection, must analysis
Mental rule:
union = may exist on some path
intersection = must exist on all paths
forward = facts move with execution
backward = facts needed by future execution
Dataflow equation skeleton:
Forward:
in[B] = meet out[preds]
out[B] = gen[B] ∪ (in[B] - kill[B])
Backward:
out[B] = meet in[succs]
in[B] = gen/use[B] ∪ (out[B] - kill/def[B])
Convergence reason:
finite lattice + monotone transfer functions => fixpoint
Dominators / Loops
Memorize:
a dominates b iff every path from entry to b goes through a.
idom(b) = closest strict dominator of b.
back edge n -> h iff h dominates n.
natural loop of n -> h = h plus all nodes that can reach n without passing through h.
Dominance frontier intuition:
DF(x) = places where x's dominance stops.
Phi nodes go in dominance frontiers of definition blocks.
SSA Must-Know
SSA gives:
each variable assigned once
each use has exactly one reaching definition
phi nodes merge values at CFG joins
SSA construction:
1. Compute dominators/idoms.
2. Compute dominance frontiers.
3. Insert phi nodes at iterated dominance frontiers of definitions.
4. Rename by DFS over dominator tree using stacks per variable.
Renaming rule:
definition: create new version and push
use: replace by top of stack
phi operands: filled on predecessor edges
exit block: pop versions defined in block
Pruned SSA:
insert phi only where variable is live-in.
Deconstruct SSA:
replace phi with copies in predecessor blocks, then remove phi.
SCCP: Absolute Must Memorize
Lattice:
TOP = unknown / optimistic / unreachable contribution
c = constant
BOT = overdefined / nonconstant
Meet:
TOP ∧ x = x
c ∧ c = c
c ∧ d = BOT if c != d
BOT ∧ x = BOT
SCCP has two simultaneous analyses:
SSAWorkList = value propagation over def-use edges
CFGWorkList = reachability propagation over control-flow edges
Branch rule:
condition TRUE => mark only true successor
condition FALSE => mark only false successor
condition BOT => mark both successors
condition TOP => normally should not occur for real reachable branch
Key exam gotcha:
unreachable block values remain TOP, not BOT
So:
phi(10 from reachable, 20 from unreachable)
= 10 ∧ TOP
= 10
Another gotcha:
TOP * BOT = TOP
because TOP might later become 0, and 0 * BOT = 0.
PRE / Lazy Code Motion
Partial redundancy:
expression is available on some but not all paths.
Goal:
insert expression on missing paths so it becomes fully redundant,
then eliminate duplicate computations.
Loop invariant code motion is a special case of PRE:
inside-loop computation is partially redundant across loop iterations.
LCM intuition:
EARLIEST = highest safe point to insert
LATEST/LATER = push insertion down as far as possible without losing benefit
Exam phrasing:
PRE balances redundancy elimination against avoiding unnecessary code motion.
Value Numbering
Local VN:
assign same value number to equivalent expressions in one basic block.
Remember:
commutative ops sort operands
constant folding happens during lookup
new assignment to variable kills old variable-to-VN binding
Global VN on SSA:
two SSA values equivalent if same constant, same SSA name, or same operator with congruent operands.
SSA makes GVN easier because defs dominate uses and variables do not get reassigned.
Dependence Analysis
Dependence types:
Flow / RAW: write then read
Anti / WAR: read then write
Output / WAW: write then write
Loop dependence exists when two dynamic iterations access same memory and at least one writes.
Distance vector:
d = j - i
Direction vector:
< means later iteration index is greater
= means same iteration index
> means later iteration index is smaller
Loop-carried dependence:
first non-= direction determines carrying loop.
Preserving dependences preserves semantics.
Tests:
ZIV: no loop vars. Dependence iff constants equal.
Strong SIV:
a*i + c1 = a*i' + c2
distance d = (c1 - c2) / a
dependence if integer and within loop bounds.
GCD:
dependence possible only if gcd(coefficients) divides constant difference.
Necessary, not sufficient.
Banerjee:
compute min/max possible value of dependence expression.
if 0 not in [L, U], no dependence.
if 0 in [L, U], possible dependence.
Big distinction:
GCD and Banerjee are conservative.
They may report false dependences, but must not miss real ones.
Loop Transform Legality
Always ask:
Does the transformation reverse any existing dependence?
Quick rules:
Fusion legal if same bounds and no dependence direction becomes invalid.
Fission legal if split respects SCC/order of dependence graph.
Interchange legal if no transformed direction vector has first non-= as >.
Reversal legal if no loop-carried dependence in reversed loop.
Skewing changes iteration space to expose legal interchange/parallelism.
Tiling = strip mining + interchange, legality follows from those.
Peeling is generally legal with guard if needed.
Unswitching legal if condition is loop-invariant.
Most important exam shortcut:
After loop interchange, rewrite direction vectors by swapping components.
Then check lexicographic positivity: first non-= must not be >.
Register Allocation
Pipeline:
1. Compute liveness.
2. Build live ranges/webs.
3. Build interference graph.
4. Color graph with K registers.
5. Spill if coloring fails.
6. Rewrite code and repeat.
Interference:
two values interfere if live ranges overlap.
Graph coloring:
degree < K => trivially colorable, push on stack
all degree >= K => choose spill candidate
pop stack and assign non-conflicting color
failure => actual spill
Spill cost intuition:
spill values with low use frequency and outside deep loops.
Coalescing:
merge copy-related nodes if they do not interfere.
Benefit: removes moves.
Risk: increases graph degree and may cause spills.
Precolored nodes:
fixed machine registers for arguments, return values, special registers.
IR / Codegen Basics
Three-address code patterns:
x = y op z
x = y
if x relop y goto L
goto L
x = a[i]
a[i] = x
Remember:
r-value = value
l-value = address/location
Short-circuit codegen:
A && B: if A false, skip B
A || B: if A true, skip B
Most Likely Hand-Traces
Be ready to execute these fast:
1. Iterative dataflow on a CFG.
2. Dominators + natural loops.
3. SSA phi insertion + renaming.
4. SCCP over a small SSA CFG.
5. Local value numbering table.
6. GVN congruence classes.
7. GCD / Banerjee / SIV dependence test.
8. Loop interchange legality from direction vectors.
9. Liveness + interference graph + coloring.
10. PRE placement on a diamond CFG.
Final Exam Survival Heuristics
When stuck, classify first:
May analysis => union, optimistic about existence.
Must analysis => intersection, conservative across all paths.
SSA problem => think def-use and dominance.
Loop transform problem => inspect dependence direction vectors.
Register allocation problem => liveness first, graph second.
SCCP problem => value lattice plus reachable blocks.
PRE problem => available on some paths, insert on missing paths.
Most common mistakes to avoid:
Using union for available expressions.
Forgetting liveness is backward.
Treating unreachable SCCP inputs as BOT instead of TOP.
Forgetting phi nodes occur at dominance frontiers.
Confusing distance and direction vectors.
Thinking GCD proves dependence; it only proves possible dependence.
Ignoring anti/output dependences in loop transformations.
Coloring interference graph before computing correct live ranges.
Forgetting to rerun allocation after spilling.