Lesson 16.5 — Representing the merge: phi nodes, block arguments, upsilon/phi¶

Techniques: phi nodes (LLVM IR, GCC GIMPLE, Go SSA), block arguments (MLIR, Swift SIL, Cranelift), upsilon/phi form (WebKit B3 and DFG; Pizlo) · Pebble uses: phi nodes in LLVM IR; the labs use Chapter 8's block-argument ssa format; lab L2 turns block arguments into copies · Prerequisites: Lesson 8.4 (phi ↔ block arguments, Theorem 8.4.10), Lesson 16.1 · Time: 3–4 hours

A phi is a strange instruction. It sits in a block but executes "on the edge"; all phis of a block execute at once; its operand list must match the predecessor list, so every CFG edit must also edit phis. Three designs answer the question "where does the merge live?" differently. Phi nodes put it in the merge block, keyed by predecessor. Block arguments put the values in the branch and the names in the block header, like a function call. Upsilon/phi splits the merge into a write in each predecessor (Upsilon) and a read in the merge block (Phi), connected by a hidden variable. Chapter 8 proved phis and block arguments equivalent; this lesson adds upsilon/phi, compares the three for construction, transformation and destruction, and shows each in a production compiler.

1. Problem and motivation¶

The problem. Choose the in-memory and textual form of SSA merges so that (a) the semantics of Definition 16.1.2 is expressed exactly, (b) CFG transformations (edge splitting, block merging, jump threading) stay cheap and hard to get wrong, and (c) leaving SSA (Lessons 16.6–16.7) is straightforward. The choice is made once per IR and affects every pass. LLVM made it in 2002, MLIR in 2019.

Phi nodes¶

The original representation of the SSA papers [CFRWZ91]: x3 = phi [x1, P1], [x2, P2] at the top of the merge block, one (value, predecessor) pair per incoming edge. LLVM, GCC and Go use it [LLVM-LangRefPhi]. The predecessor labels make the phi self-describing, but tie it to the CFG: deleting, splitting or redirecting an edge requires updating every phi of the target.

Block arguments¶

A block declares parameters; each branch passes arguments: ^bb1(%a: i32, %b: i32) and cf.br ^bb1(%x, %y : i32, i32). This is Kelsey's correspondence between SSA and continuation-passing style made into syntax [Kel95, App98]: a block is a local function, a branch a tail call. Swift SIL, MLIR and Cranelift use it [SIL-Docs, MLIR-Rationale, CL-IR]. A branch carries its own values, so the "which predecessor" bookkeeping disappears; the parallel-copy semantics is explicit in the syntax.

Upsilon and phi¶

Filip Pizlo's design for WebKit's B3 back end (and its DFG IR) splits the phi in two [WebKit-B3, Piz25]: Upsilon(v, ^x) in a predecessor writes \(v\) into the shadow variable \(\hat{x}\) of phi \(x\), and x = Phi() in the merge block reads it. Blocks know nothing about SSA: there are no block parameters and no predecessor lists in phis, so CFG transformations never touch SSA data. The price is that the representation is less self-evidently SSA: the validator must check that every path to a Phi passes an Upsilon for it.

2. Definitions and algorithms¶

Phi nodes¶

Definition 16.5.1 (Phi-node form)

A block \(B\) with predecessor edges \(e_1, \dots, e_k\) (a multi-edge counts once per edge) begins with phis \(x_\ell = \phi([a_{\ell 1}, P_1], \dots, [a_{\ell k}, P_k])\) and nothing else before them; each has exactly one entry per incoming edge (entries for a multi-edge carry the same value in LLVM); the operand \(a_{\ell j}\) is used at the end of \(P_j\). Semantics: Definition 16.1.2 [LLVM-LangRefPhi].

Block arguments¶

Definition 16.5.2 (Block-argument form)

Chapter 8's Definition 8.4.4: blocks \(B(p_1, \dots, p_k)\) with parameters; terminators name successor blocks with argument lists of matching length; the parameters of \(B\) are defined at \(B\)'s entry, the arguments used at the end of the branching block. Taking the edge \(P \to B(a_1, \dots, a_k)\) performs the parallel copy \((p_1, \dots, p_k) \gets (a_1, \dots, a_k)\).

Upsilon and phi¶

Definition 16.5.3 (Upsilon/phi form)

Every phi \(x\) has an implicit shadow variable \(\hat{x}\). The instruction \(\mathtt{Upsilon}(v, \hat{x})\) performs \(\hat{x} := v\); the instruction \(x = \mathtt{Phi}()\) performs \(x := \hat{x}\). Both are ordinary instructions executed in program order, anywhere in a block. The program is well formed if (i) every name, including every Phi result, has one definition; (ii) every shadow variable is read only by its own Phi (it is static single use); and (iii) every path from the entry to a Phi passes an Upsilon for it after the last execution of that Phi, the property B3's validator checks as "each Phi is dominated by the set of its Upsilons" [WebKit-B3].

Algorithm 16.5.4 (Phi nodes → upsilon/phi)

Input: a function in phi-node form.
Output: the same function in upsilon/phi form.
Precondition: Definition 16.5.1 holds (in particular one entry per edge).
Postcondition: well formed (Definition 16.5.3) and equivalent (Theorem 16.5.6).
Invariant: after processing phi \(x\), every predecessor \(P_j\) of its block ends with Upsilon(a_xj, ^x) just before its terminator, and \(x\)'s phi node is replaced by x = Phi() at the same position.

function PhiToUpsilon(F):
    for each block B, for each phi x = φ([a_1, P_1], ..., [a_k, P_k]) of B:
        for j in 1..k:
            insert "Upsilon(a_j, ^x)" at the end of P_j, before its terminator
        replace the phi by "x = Phi()"

If \(P_j \to B\) is part of a multi-edge whose entries differ, split one edge first (as for block arguments, Lemma 8.4.11). The reverse translation is possible exactly when every Phi is at the top of its block and every predecessor ends with one Upsilon per Phi of the successor it jumps to; otherwise the Upsilons must first be moved there, which is legal only where no Upsilon for the same Phi could be observed on another path.

Algorithm 16.5.5 (Phi nodes ↔ block arguments)

Input: a function in one form.
Output: the function in the other form.
Precondition: no multi-edge carries two different argument lists (split it otherwise).
Postcondition: equivalent (Theorem 8.4.10).
Invariant: the \(\ell\)-th phi of \(B\) corresponds to the \(\ell\)-th parameter of \(B\).

function PhiToArgs(F):
    for each block B with phis x_1..x_m: make x_1..x_m the parameters of B, delete the phis
    for each edge P → B: append (a_1j, ..., a_mj) — the phis' entries for P — to the branch
function ArgsToPhi(F):
    for each block B with parameters p_1..p_m and each edge P → B(a_1..a_m):
        add the entry [a_ℓ, P] to a phi for p_ℓ;  drop the arguments from the branch

This is Chapter 8's Algorithm 8.4.6, repeated here for the comparison.

3. Worked example¶

Phi nodes on the swap loop¶

The loop that rotates two values, the smallest instance of the swap problem, in LLVM IR:

loop:
  %a = phi i32 [ 1, %entry ], [ %b, %loop ]
  %b = phi i32 [ 2, %entry ], [ %a, %loop ]
  %i = phi i32 [ 0, %entry ], [ %i1, %loop ]
  %i1 = add i32 %i, 1
  %c = icmp slt i32 %i1, %n
  br i1 %c, label %loop, label %exit

Executing with \(n = 3\) (Definition 16.1.2): entering from entry, \((a, b, i) = (1, 2, 0)\); after the first back edge \((2, 1, 1)\); after the second \((1, 2, 2)\); then exit computes \(a - b = -1\). The box in §7 runs it with lli.

Block arguments on the swap loop¶

The same loop in the lab's ssa format (and MLIR's, modulo syntax):

H(a, b, i):
  i1 = add i, 1
  t = lt i1, 3
  cbr t, H(b, a, i1), X()

The branch H(b, a, i1) is the parallel copy \((a, b, i) \gets (b, a, i_1)\); no predecessor label is needed because the edge is the branch itself.

Upsilon and phi on the swap loop¶

Algorithm 16.5.4 applied to the LLVM version:

entry:
  Upsilon(1, ^a); Upsilon(2, ^b); Upsilon(0, ^i)
  Jump(loop)
loop:
  a = Phi(); b = Phi(); i = Phi()
  i1 = Add(i, 1)
  c = LessThan(i1, n)
  Upsilon(b, ^a); Upsilon(a, ^b); Upsilon(i1, ^i)
  Branch(c, loop, exit)
exit:
  r = Sub(a, b)

The Upsilons are sequential instructions, yet there is no swap problem: Upsilon(b, ^a) writes the shadow \(\hat{a}\), not \(a\), so Upsilon(a, ^b) still reads the old \(a\). And exit reads \(a\) and \(b\), which the Upsilons in loop do not touch, although they sit before a two-way branch: no lost copy either. Trace with \(n = 3\):

step	executed	\(a, b, i\)	\(\hat{a}, \hat{b}, \hat{i}\)
1	entry's Upsilons	—, —, —	1, 2, 0
2	loop's Phis	1, 2, 0	1, 2, 0
3	loop's Upsilons (\(i_1 = 1\), \(c\) true)	1, 2, 0	2, 1, 1
4	loop's Phis	2, 1, 1	2, 1, 1
5	loop's Upsilons (\(i_1 = 2\), \(c\) true)	2, 1, 1	1, 2, 2
6	loop's Phis	1, 2, 2	1, 2, 2
7	loop's Upsilons (\(i_1 = 3\), \(c\) false)	1, 2, 2	2, 1, 3
8	exit: \(r = a - b\)	1, 2, 2	\(r = -1\)

Step 7 writes the shadows even though the loop exits; nothing reads them afterwards, which is the point of condition (ii) of Definition 16.5.3.

Try it

./course drill lost-copy-swap --seed 3 --solution shows the naive translation of a block-argument loop going wrong; convert its SSA to upsilon/phi by hand and check that the same copies, written to shadow variables, are right.

4. Invariants and correctness¶

Phi nodes¶

Theorem 16.5.6 (The three forms are equivalent)

Algorithms 16.5.4 and 16.5.5 preserve the behavior of every function that satisfies their preconditions.

Proof

Phi ↔ block arguments is Theorem 8.4.10. Phi → upsilon/phi: consider an execution that takes the edge \(P_j \to B\). In phi form, the phis of \(B\) read \(a_{\ell j}\) at the end of \(P_j\) and write all \(x_\ell\) at once. In upsilon form, the Upsilons at the end of \(P_j\) write \(\hat{x}_\ell := a_{\ell j}\); the operands \(a_{\ell j}\) are names other than the shadows (shadows are not names of the program), so no Upsilon changes another's operand, and the writes are effectively parallel. Then control enters \(B\) and the Phis set \(x_\ell := \hat{x}_\ell = a_{\ell j}\) before any other instruction of \(B\) (they replaced the phi nodes at the top). So on entry to \(B\)'s first ordinary instruction every \(x_\ell\) holds the same value in both forms. Upsilons executed on the other successor edge of \(P_j\) write shadows that no Phi reads before they are rewritten: the next Phi of \(x_\ell\) to execute is in \(B\) and is reached only through an edge into \(B\), whose source ends with a fresh Upsilon for \(x_\ell\). Well-formedness (iii) holds because every path into \(B\) ends with such an Upsilon.

Block arguments¶

Proposition 16.5.7 (Block arguments make the parallel copy local)

In block-argument form, the complete parallel copy of an edge is the pair (parameters of the target, arguments of the branch), and it can be read or rewritten without consulting any other block. In phi-node form it is spread over the phis of the target, indexed by the position of the source in the target's predecessor list.

Proof

By Definition 16.5.2 the arguments of an edge are written in the branch that creates the edge, and the parameters in the target's header, which does not depend on the edge. By Definition 16.5.1 the values of an edge are the \(j\)-th entries of all phis of the target, where \(j\) identifies the edge in the target's predecessor order; changing the source's branch (for example splitting the edge) changes that order or label, so all phis of the target must be edited.

Upsilon and phi¶

Theorem 16.5.8 (Upsilon/phi form needs no parallel copies and no edge splitting to leave SSA)

Replace every \(\mathtt{Upsilon}(v, \hat{x})\) by the copy \(\hat{x} := v\) and every \(x = \mathtt{Phi}()\) by \(x := \hat{x}\), with \(\hat{x}\) a fresh variable per phi. The result is a correct non-SSA program, for every well-formed upsilon/phi program, including those obtained from transformed SSA.

Proof

The replacement implements Definition 16.5.3's semantics literally, instruction by instruction, so it is correct whenever the upsilon/phi program is. The two classical failures of naive destruction (Lesson 16.6) cannot occur: a lost copy needs a copy \(x := v\) at the end of a predecessor to overwrite a value of \(x\) that is still live on another path, but Upsilons write only shadow variables, which are live only between an Upsilon and its Phi; a swap needs one copy to read a name another copy of the same edge wrote, but Upsilons read program names and write only shadows. This is Sreedhar's Method I (Lesson 16.6) built into the representation: every phi is isolated by copies on both sides [SJGS99], and the register coalescer then removes most of them.

5. Complexity¶

\(m\) = phis of a block, \(k\) = incoming edges, \(E\) = CFG edges of the function.

Technique	Size	Remove or redirect one edge \(P \to B\)	Split an edge	Leave SSA
Phi nodes	\(m \cdot k\) (value, block) pairs per block	\(O(m)\): find and delete entry \(j\) in every phi (plus \(O(k)\) to find \(j\))	\(O(m)\): relabel \(P\) as the new block in every phi	parallel copies per edge (Lessons 16.6–16.7)
Block arguments	\(m \cdot k\) values in branches + \(m\) parameters	\(O(m)\) to delete the branch's argument list; \(O(m \cdot k)\) to delete a parameter (every branch into \(B\))	\(O(m)\): the new block gets parameters or the branch's arguments move	the same parallel copies, already grouped per edge
Upsilon/phi	\(m \cdot k\) Upsilons + \(m\) Phis	\(O(1)\) for SSA: nothing references the edge; dead Upsilons are removed later by DCE	\(O(1)\) for SSA: Upsilons stay at the end of \(P\)	one copy per Upsilon and Phi (Theorem 16.5.8), then coalescing

Justification. Each cost counts the SSA data structures touched by the CFG edit, from the definitions: phi entries are keyed by predecessor (Definition 16.5.1), arguments live in branches (Definition 16.5.2), Upsilons in blocks with no reference to edges (Definition 16.5.3).

Proposition 16.5.9 (Deleting a block parameter is quadratic in a chain)

Removing all \(m\) parameters of a block with \(k\) predecessors, one at a time, costs \(\Theta(m^2 k)\) with argument lists stored as arrays, but \(\Theta(m k)\) phi entries in phi form.

Proof

Deleting parameter \(\ell\) removes position \(\ell\) from each of \(k\) argument arrays, shifting up to \(m\) elements each: \(O(mk)\) per parameter, \(\Theta(m^2 k)\) for all \(m\) when each deletion is at the front. In phi form each deleted phi is one object with \(k\) entries: \(O(k)\) each, \(\Theta(mk)\) in total. Cranelift's remove_block_param and MLIR's eraseArgument pay the array cost; batching deletions (MLIR's eraseArguments with a bit vector) restores \(\Theta(mk)\).

Phi nodes¶

One entry per edge vs per predecessor block: LLVM requires identical duplicate entries for a multi-edge; the lab's phi view (Chapter 8) forbids multi-edges with different values — trade-off: simpler phis vs a more general CFG.
Gated phis carry the branch predicate that selects the entry (Lesson 16.8) — trade-off: more information, harder to maintain.
Memory phis in a separate namespace (LLVM MemoryPhi, GCC .MEM phis) — Lesson 16.8.

Block arguments¶

Successor operands in the terminator's operand list (MLIR's SuccessorOperands) vs in the branch instruction's own fields (Cranelift's BlockCall) — trade-off: uniform operand handling vs compact storage.
Terminator results as block arguments (SIL's try_apply passes the call result to its normal-successor block as an argument) — trade-off: values defined "on the edge" become expressible.
Region arguments (MLIR scf.for iter_args, the structured form shown in §7) — trade-off: loops keep their structure; lowering to a CFG turns them into block arguments.

Upsilon and phi¶

Pizlo form with Phis anywhere (not only at block tops) — trade-off: CFG passes never fix SSA, but analyses must treat Upsilon and Phi as effects on the shadow variable [Piz25].
DFG's SSA (JavaScriptCore's mid tier) uses the same Upsilon/Phi pair — trade-off: easy conversion between the DFG's CPS form and SSA.
Explicit copies on edges (the output of Sreedhar's Method I) is the same idea after destruction: a variable per phi written in predecessors.

7. In real compilers¶

Phi nodes¶

LLVM enforces the phi rules and executes phis in parallel

Reproduce (opt 23.1.2, lli 23.1.2):

cat > badphi.ll <<'EOF'
define i32 @late(i1 %c) {
entry:
  br i1 %c, label %l, label %r
l:
  br label %j
r:
  br label %j
j:
  %x = add i32 1, 2
  %p = phi i32 [ 1, %l ], [ 2, %r ]
  ret i32 %p
}

define i32 @missing(i1 %c) {
entry:
  br i1 %c, label %l, label %j
l:
  br label %j
j:
  %p = phi i32 [ 1, %l ]
  ret i32 %p
}
EOF
opt -passes=verify -disable-output badphi.ll
cat > swapmain.ll <<'EOF'
define i32 @swap(i32 %n) {
entry:
  br label %loop

loop:
  %a = phi i32 [ 1, %entry ], [ %b, %loop ]
  %b = phi i32 [ 2, %entry ], [ %a, %loop ]
  %i = phi i32 [ 0, %entry ], [ %i1, %loop ]
  %i1 = add i32 %i, 1
  %c = icmp slt i32 %i1, %n
  br i1 %c, label %loop, label %exit

exit:
  %r = sub i32 %a, %b
  ret i32 %r
}

define i32 @main() {
  %r = call i32 @swap(i32 3)
  ret i32 %r
}
EOF
lli swapmain.ll; echo "exit status: $?"

Output (complete; the verifier's messages go to stderr, the last line is the shell's):

PHI nodes not grouped at top of basic block!
  %p = phi i32 [ 1, %l ], [ 2, %r ]
label %j
PHINode should have one entry for each predecessor of its parent basic block!
  %p = phi i32 [ 1, %l ]
opt: badphi.ll: error: input module is broken!
exit status: 255

What to notice: the two verifier messages are the two structural rules of Definition 16.5.1. The exit status 255 is \(-1 \bmod 256\): @swap(3) returned \(a - b = 1 - 2\), the parallel result of §3. Sequential execution of the phis would give \(a = b = 2\) after the first back edge and return 0.

Block arguments¶

MLIR: a structured loop lowered to block arguments

Reproduce (mlir-opt 23.1.2, conda-forge package mlir 23.1.2):

cat > fib.mlir <<'EOF'
func.func @fib(%n: index) -> i32 {
  %c0 = arith.constant 0 : index
  %c1 = arith.constant 1 : index
  %a0 = arith.constant 0 : i32
  %b0 = arith.constant 1 : i32
  %r:2 = scf.for %i = %c0 to %n step %c1 iter_args(%a = %a0, %b = %b0) -> (i32, i32) {
    %s = arith.addi %a, %b : i32
    scf.yield %b, %s : i32, i32
  }
  return %r#0 : i32
}
EOF
mlir-opt fib.mlir --convert-scf-to-cf

Output (complete):

module {
  func.func @fib(%arg0: index) -> i32 {
    %c0 = arith.constant 0 : index
    %c1 = arith.constant 1 : index
    %c0_i32 = arith.constant 0 : i32
    %c1_i32 = arith.constant 1 : i32
    cf.br ^bb1(%c0, %c0_i32, %c1_i32 : index, i32, i32)
  ^bb1(%0: index, %1: i32, %2: i32):  // 2 preds: ^bb0, ^bb2
    %3 = arith.cmpi slt, %0, %arg0 : index
    cf.cond_br %3, ^bb2, ^bb3
  ^bb2:  // pred: ^bb1
    %4 = arith.addi %1, %2 : i32
    %5 = arith.addi %0, %c1 : index
    cf.br ^bb1(%5, %2, %4 : index, i32, i32)
  ^bb3:  // pred: ^bb1
    return %1 : i32
  }
}

What to notice: the iter_args of scf.for (region arguments) become the parameters %0, %1, %2 of the header ^bb1, and scf.yield %b, %s becomes the argument list of the back edge cf.br ^bb1(%5, %2, %4): the parallel copy \((i, a, b) \gets (i + 1, b, a + b)\) is one instruction (Proposition 16.5.7). MLIR's rationale document explains the choice over phi nodes [MLIR-Rationale]; the translation to LLVM IR (connectPHINodes) turns each argument list back into phi entries (Algorithm 16.5.5).

Upsilon and phi¶

B3: Upsilon and Phi opcodes and the validator's path check

Reproduce (curl 8.x on any OS; WebKit source at tag WebKit-7622.2.11.14.6; the files are the actual B3 sources, printed unmodified):

B=https://raw.githubusercontent.com/WebKit/WebKit/WebKit-7622.2.11.14.6/Source/JavaScriptCore/b3
curl -sS "$B/B3Opcode.h" | sed -n '445,447p'
curl -sS "$B/B3Validate.cpp" | grep -n 'cannot reach a Phi without\|dominated by a the set\|Undominated phi'
curl -sS "$B/B3UpsilonValue.h" | sed -n '60,62p'

Output (complete):

    // SSA support, in the style of DFG SSA.
    Upsilon, // This uses the UpsilonValue class.
    Phi,
986:    // A simple backwards analysis to check that we cannot reach a Phi without going through a corresponding Upsilon
987:    // We cannot use the dominator tree, since we are checking that each Phi is dominated by a the set of all of its upsilons, and not by a single node.
1024:                    VALIDATE(undominatedPhis.isEmpty(), ("Undominated phi at top of entry block: ", **undominatedPhis.begin()));
    // Note that passing the Phi during construction is optional. A valid pattern is to first create
    // the Upsilons without the Phi, then create the Phi, then go back and tell the Upsilons about
    // the Phi. This allows you to emit code in its natural order.

What to notice: Upsilon and Phi are ordinary opcodes, next to Jump and Branch in the opcode list. The validator's check is condition (iii) of Definition 16.5.3: a backwards dataflow over blocks collects Phis not yet "covered" by an Upsilon and fails if any reaches the entry. The comment in B3UpsilonValue.h shows the practical benefit for construction: a front end can emit Upsilons before the Phi exists, in program order, without predecessor bookkeeping.

Find where LLVM does it. Open llvm/lib/IR/Verifier.cpp (LLVM 23.1.2) and find the message "PHINode should have one entry for each predecessor of its parent basic block!". Question: in which Verifier member function is it checked? (Quiz llvm-where-phi-verify.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Phi nodes	full SSA; entries keyed by predecessor	edge edits \(O(m)\) per target block · fine in practice	self-describing; the verifier checks placement and arity	predecessor bookkeeping in every CFG pass	LLVM, GCC, Go, V8 TurboFan
Block arguments	full SSA; equivalent to phis (Theorem 8.4.10)	edge edits local to the branch; parameter deletion touches every predecessor	the parallel copy of an edge is one instruction	branch operand lists; natural for CPS/functional front ends	MLIR, Swift SIL, Cranelift
Upsilon/phi	full SSA with SSU shadow variables	CFG edits \(O(1)\) for SSA · validation needs a dataflow pass	Phis are plain instructions; destruction is trivially correct	the simplest CFG passes; effect analysis must know shadows	WebKit B3 and DFG

Choose phi nodes when you inherit LLVM or GCC, or when analyses iterate over "the values merged at this block" more often than transformations edit edges. Choose block arguments when you design a new IR, especially one with structured regions or a functional flavor. Choose upsilon/phi when CFG surgery is frequent and you want destruction to be a local rewrite; accept a validator that must reason about paths.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch16.yaml`)	Drill	Flashcard tag	Exercises
Phi nodes	`phi-parallel`, `llvm-where-phi-verify`	`./course drill phi-to-block-args` (Ch 8)	`phi-nodes`	—
Block arguments	`blockargs-edge-edit`, `phi-parallel`	`./course drill phi-to-block-args`	`block-arguments`	lab L2 (input format)
Upsilon/phi	`upsilon-semantics`, `upsilon-destruction`	`./course drill lost-copy-swap --solution` (compare with the upsilon translation by hand)	`upsilon-phi`	—

Upsilons are not copies into the phi's result

Writing Upsilon(v, ^x) as x := v at the end of the predecessor turns upsilon/phi form back into naive destruction, with its lost-copy and swap problems. The shadow variable \(\hat{x}\) is a different variable from \(x\); only the Phi copies it into \(x\).

References¶

See the chapter references.

Lesson 16.5 — Representing the merge: phi nodes, block arguments, upsilon/phi¶

1. Problem and motivation¶

Phi nodes¶

Block arguments¶

Upsilon and phi¶

2. Definitions and algorithms¶

Phi nodes¶

Block arguments¶

Upsilon and phi¶

3. Worked example¶

Phi nodes on the swap loop¶

Block arguments on the swap loop¶

Upsilon and phi on the swap loop¶

4. Invariants and correctness¶

Phi nodes¶

Block arguments¶

Upsilon and phi¶

5. Complexity¶

6. Variants and refinements¶

Phi nodes¶

Block arguments¶

Upsilon and phi¶

7. In real compilers¶

Phi nodes¶

Block arguments¶

Upsilon and phi¶

8. Comparison¶

9. Assessment¶

References¶