Lesson 23.5 — If-conversion, predication and hyperblocks¶

Techniques: if-conversion and predicate assignment (Allen–Kennedy–Porterfield–Warren; Park–Schlansker); hyperblock formation (Mahlke et al.); LLVM's machine if-converters (EarlyIfConversion to selects and cmov, IfConverter to predicated instructions) · Drill: ifconvert · Prerequisites: Lesson 23.4 (regions, tail duplication), Ch 15 Lesson 15.4 (post-dominance and control dependence) · Time: 3–4 hours

Region schedulers move instructions across branches but keep the branches. If-conversion removes them: every instruction is guarded by a predicate, a boolean that is true exactly when the instruction's block would have executed, and the region becomes one straight-line block. The scheduler can then interleave both arms of an if freely, and the processor never mispredicts the removed branch. The price is that it executes (or at least issues) the instructions of both arms. So if-conversion pays off only when the arms are short, the branch is hard to predict, or the machine is wide enough to absorb the extra work. The same transformation appears at three scales: vectorizers use it to handle if inside loops (Ch 18), GPUs execute divergent branches with execution masks, and CPU back ends turn small diamonds into select, cmov or predicated instructions.

The running example is this acyclic region (drill format: br cX, T, F goes to T when the condition cX of block X is true):

A: br cA, B, C
B: br cB, D, E
C: br cC, E, F
D: jmp F
E: jmp F
F: exit

flowchart TD
  A([A]) -->|cA| B[B]
  A -->|!cA| C[C]
  B -->|cB| D[D]
  B -->|!cB| E[E]
  C -->|cC| E
  C -->|!cC| F[F]
  D --> F
  E --> F

1. Problem and motivation¶

If-conversion and predicate assignment¶

Allen, Kennedy, Porterfield and Warren introduced if-conversion to vectorize loops containing conditionals: a vectorizer handles data dependences, so they converted control dependences into data dependences on boolean guards [AKPW83]. The Cydra 5 and later the Itanium (IA-64) architecture gave every instruction a predicate operand. Park and Schlansker's RK algorithm assigns predicates with as few predicate registers as possible, using control dependence [PS91]. In pebblec's pipeline you meet if-conversion three times: SimplifyCFG's speculation into select (Ch 17), the loop vectorizer's masking (Ch 18), and the machine-level passes of this lesson.

Hyperblock formation¶

Converting a whole region can do more harm than good: a rarely executed arm with a long latency or a call lengthens every execution. Mahlke and his colleagues defined the hyperblock: a single-entry region of selected blocks, chosen by execution frequency, size and hazards, made single-entry by tail duplication and then if-converted [MLC+92]. Hyperblocks combine the superblock idea (follow the likely paths, Lesson 23.4) with predication (keep several likely paths). IMPACT and the Itanium compilers used them, and GPU compilers produce hyperblock-shaped code for every divergent region.

LLVM's machine if-converters¶

Most CPUs have no general predication. x86 and AArch64 have conditional moves and selects (cmov, csel), and 32-bit ARM predicates almost every instruction. LLVM has two machine passes. EarlyIfConversion runs on SSA machine code and turns small diamonds and triangles into selects when a trace-based cost model says the resulting critical path is not much longer than the shorter arm's [LLVM-EarlyIfCvt]. IfConverter runs after register allocation on targets with predication (ARM, Thumb-2, Hexagon, PowerPC for some patterns) and predicates entire blocks [LLVM-IfCvt].

2. Definitions and algorithms¶

Definition 23.5.1 (Branch conditions, path assignments)

Let \(R\) be an acyclic single-entry region whose blocks with two successors end in \(\mathtt{br}\ c_X, T, F\). An assignment \(\alpha\) gives every condition \(c_X\) a truth value; it determines one path \(\mathrm{path}(\alpha)\) from the entry to the exit (follow \(T\) when \(\alpha(c_X)\), else \(F\)). Block \(B\) executes under \(\alpha\) if \(B \in \mathrm{path}(\alpha)\).

Definition 23.5.2 (Predicate of a block, predicated code)

A predicate is a boolean formula over the conditions. \(p(B)\) is exact if \(\alpha \models p(B) \iff B \in \mathrm{path}(\alpha)\) for every \(\alpha\). Predicated code for \(R\) is the sequence of \(R\)'s operations, blocks in a topological order, each operation of \(B\) guarded by \(p(B)\): a guarded operation whose predicate is false has no effect (it is nullified). A branch condition \(c_X\) is computed by the guarded code of \(X\), and branches are removed.

If-conversion and predicate assignment¶

Algorithm 23.5.3 (Predicate assignment by predecessors)

Input: an acyclic single-entry region in topological order.
Output: an exact predicate \(p(B)\) for every block.
Precondition: every condition \(c_X\) is computed in \(X\) and not redefined in the region.
Postcondition: each \(p(B)\) is exact (Lemma 23.5.8).
Invariant: when \(B\) is processed, \(p(P)\) is final and exact for every predecessor \(P\).

function AssignPredicates(R):
    p(entry) ← true
    for B in topological order, B ≠ entry:
        p(B) ← false
        for each predecessor P of B:
            p(B) ← p(B) ∨ (p(P) ∧ EdgeCond(P, B))
    return p

function EdgeCond(P, B):
    if P ends in br c_P, B, _: return c_P
    if P ends in br c_P, _, B: return ¬c_P
    return true                                  # jmp

The formula grows with the number of paths. Real if-converters share predicates between blocks that always execute together, and they compute each predicate with one compare into a predicate register. Control dependence (Ch 15, Lesson 15.4) tells you which blocks those are.

Definition 23.5.4 (Control dependence, predicate classes)

\(B\) is control dependent on the edge \((X, o)\) (branch \(X\) with outcome \(o\)) if \(B\) post-dominates the \(o\)-successor of \(X\) but not \(X\) itself. \(\mathrm{CD}(B)\) is the set of such edges. Blocks with equal \(\mathrm{CD}\) sets form a predicate class. The RK assignment gives each class one predicate \(p = \bigvee_{(X, o) \in \mathrm{CD}(B)} p(X) \wedge \mathrm{lit}(X, o)\), where \(\mathrm{lit}(X, \mathrm{true}) = c_X\) and \(\mathrm{lit}(X, \mathrm{false}) = \neg c_X\), and \(\mathrm{CD}(B) = \emptyset\) means \(p = \mathrm{true}\).

Hyperblock formation¶

Definition 23.5.5 (Hyperblock)

A hyperblock is a single-entry set of blocks \(H\) of a region, containing the entry, that is if-converted into one predicated block; edges leaving \(H\) become predicated branches (exits).

Algorithm 23.5.6 (Hyperblock formation, simplified from Mahlke et al.)

Input: a profiled acyclic region (counts as in Definition 23.4.1); thresholds \(\theta_f\) (minimum relative frequency) and \(\theta_s\) (maximum size ratio); a set of hazards (calls, unsafe memory operations).
Output: a hyperblock \(H\) and the transformed region.
Precondition: acyclic region; the main path (the first trace, Algorithm 23.4.3) is hazard-free.
Postcondition: \(H\) is single-entry and each block of \(H\) is hazard-free, frequent and small enough.
Invariant: \(H\) contains the entry and is closed under "every selected block has a selected path from the entry".

function FormHyperblock(R):
    main ← SelectTraces(R)[0]                          # Algorithm 23.4.3
    H ← set(main)
    for B in topological order, B ∉ H:
        if cnt(B) / cnt(entry) ≥ θ_f and size(B) ≤ θ_s · size(main) and B has no hazard
           and some predecessor of B is in H:
            H ← H ∪ {B}
    for B in H, B ≠ entry, with a predecessor outside H:   # side entrances
        TailDuplicate from B (Algorithm 23.4.6, applied to the blocks of H reachable from B)
    p ← AssignPredicates(H)                              # Algorithm 23.5.3 on H
    emit H's operations guarded by p, blocks in topological order;
    for every edge B → Y leaving H: emit "if (p(B) ∧ EdgeCond(B, Y)) jump Y"

LLVM's machine if-converters¶

Algorithm 23.5.7 (EarlyIfConversion: diamonds and triangles to selects)

Input: SSA machine code; a head block \(H\) ending in a conditional branch to \(T\) and \(F\) that meet at a tail \(J\), directly or through one side (triangle).
Output: \(H\), \(T\), \(F\) merged into one block ending in a jump to \(J\), with each phi of \(J\) over \((T, F)\) replaced by a select.
Precondition: \(T\) and \(F\) have one predecessor, contain no side effects (stores, calls) and at most -early-ifcvt-limit instructions (default 30); every instruction can be speculated.
Postcondition: the function is equivalent (Theorem 23.5.9); the cost check below held.
Invariant: SSA form is preserved (selects define the values the phis used to).

function TryConvert(H):
    if not CanConvertIf(H): return false            # shape, speculability, size
    if condition looks predictable (loop-invariant operands): return false
    minCrit ← min(critical path through T, through F)          # MachineTraceMetrics
    limit ← MispredictPenalty / 2 (or the full penalty for data-dependent conditions)
    if ResourceLength(trace with both arms) > minCrit + limit: return false
    if the select's depth after conversion exceeds the branch's depth by more than limit,
       along the condition, the short arm or the long arm: return false
    hoist T's and F's instructions into H; replace phis of J by selects on the condition;
    replace the branch by a jump to J
    return true

IfConverter works after register allocation on the same shapes (simple, triangle, diamond and their reversed forms), plus forked diamonds. It does not create selects: it asks the target to predicate each instruction (TII->PredicateInstruction), and it decides profitability with TargetInstrInfo::isProfitableToIfCvt using the branch probability and the instruction counts.

3. Worked examples¶

If-conversion and predicate assignment¶

Algorithm 23.5.3 on the running region, in topological order A, B, C, D, E, F:

block	predecessors	\(p\) (as computed)	simplified
A	—	true	true
B	A (T)	\(\mathrm{true} \wedge c_A\)	\(c_A\)
C	A (F)	\(\mathrm{true} \wedge \neg c_A\)	\(\neg c_A\)
D	B (T)	\(c_A \wedge c_B\)	\(c_A \wedge c_B\)
E	B (F), C (T)	\((c_A \wedge \neg c_B) \vee (\neg c_A \wedge c_C)\)	same
F	C (F), D, E	\((\neg c_A \wedge \neg c_C) \vee (c_A \wedge c_B) \vee (c_A \wedge \neg c_B) \vee (\neg c_A \wedge c_C)\)	true

Check E against Definition 23.5.2 by enumerating the \(2^3\) assignments of \((c_A, c_B, c_C)\): E executes on the paths A B E (when \(c_A \wedge \neg c_B\), any \(c_C\)) and A C E (when \(\neg c_A \wedge c_C\), any \(c_B\)). That is four of the eight assignments, and exactly those satisfy the formula.

Control dependence gives the same result with fewer operations: \(\mathrm{CD}(B) = \{(A, T)\}\), \(\mathrm{CD}(C) = \{(A, F)\}\), \(\mathrm{CD}(D) = \{(B, T)\}\), \(\mathrm{CD}(E) = \{(B, F), (C, T)\}\), \(\mathrm{CD}(A) = \mathrm{CD}(F) = \emptyset\). So F needs no predicate at all (it post-dominates the entry), and four predicate registers suffice: \(p_B = c_A\), \(p_C = \neg c_A\), \(p_D = p_B \wedge c_B\), \(p_E = (p_B \wedge \neg c_B) \vee (p_C \wedge c_C)\). On a machine with two-target compares (IA-64 cmp.unc p1, p2 = …) each line is one compare that writes the true and the false predicate at once.

The predicated code, in topological order:

          compute cA                       # A
(cA)      compute cB; pB ← cA              # B
(!cA)     compute cC; pC ← !cA             # C
          pD ← pB ∧ cB;  pE ← (pB ∧ ¬cB) ∨ (pC ∧ cC)
(pD)      ... operations of D ...
(pE)      ... operations of E ...
          ... operations of F ...           # unguarded

Try it

./course drill ifconvert --seed 7 --solution generates a region (hard: with an unstructured edge like C → E) and asks for every block's predicate and the number of predicates needed; any formula with the right truth table is accepted.

Hyperblock formation¶

Take the profiled region of Lesson 23.4 (counts A 100, B 70, C 30, D 90, E 10, F 60, G 40, H 100) with \(\theta_f = 0.25\) and \(\theta_s = 2\), and suppose E contains a call (a hazard). The main trace is A B D F H. Considering the other blocks in topological order: C (30 % ≥ 25 %, small, predecessor A ∈ H) is selected; E (10 %) is rejected; G (40 %, predecessor D ∈ H) is selected. So \(H = \{A, B, C, D, F, G, H\}\). Its only side entrance is E → G, so G and its successor H are tail-duplicated: E jumps to the copies G′ → H′ outside the hyperblock. The hyperblock is if-converted with \(p_A = p_D = p_H = \mathrm{true}\), \(p_B = c_A\), \(p_C = \neg c_A\), \(p_F = c_D\), \(p_G = \neg c_D\), plus one exit branch if (pC ∧ ¬cC) jump E.

LLVM's machine if-converters¶

EarlyIfConversion on a diamond whose arms are imul; add (4 cycles on Skylake) and sub (1 cycle). With MispredictPenalty = 14 in the Skylake model (Lesson 23.1), the limit is 7 cycles. The pass computes how much the condition, the short arm and the long arm would extend the critical path to the select (2, 2 and 5 cycles in the §7 box). All three stay under 7, so it converts: both arms run unconditionally and a cmov picks the result.

4. Invariants and correctness¶

If-conversion and predicate assignment¶

Lemma 23.5.8 (Exact predicates)

Under the precondition of Algorithm 23.5.3, every computed \(p(B)\) is exact.

Proof

By induction in topological order. The entry executes under every assignment and \(p = \mathrm{true}\). For \(B \ne\) entry: \(B \in \mathrm{path}(\alpha)\) iff \(\mathrm{path}(\alpha)\) reaches some predecessor \(P\) and then takes the edge \(P \to B\). By the induction hypothesis the first part is \(\alpha \models p(P)\). The path takes \(P \to B\) exactly when \(\alpha \models \mathrm{EdgeCond}(P, B)\) (for a branch, by Definition 23.5.1; for a jump, always). A path visits at most one predecessor of \(B\) immediately before \(B\), so the disjunction over predecessors is exactly "some predecessor reached and its edge taken". Conditions are not redefined, so \(\alpha(c_P)\) is the value \(P\)'s branch sees.

Theorem 23.5.9 (If-conversion is an equivalence)

For every assignment \(\alpha\), executing the predicated code of \(R\) (Definition 23.5.2, exact predicates) performs exactly the operations of \(\mathrm{path}(\alpha)\), in the same relative order, and so produces the same final state as the branching code.

Proof

By Lemma 23.5.8, an operation of \(B\) has effect iff \(B \in \mathrm{path}(\alpha)\), and nullified operations have no effect. The blocks of \(\mathrm{path}(\alpha)\) occur in the chosen topological order in path order, because each edge of the path goes forward in that order, and operations inside a block keep their order. So the effective operations form exactly the sequence executed by the branching code, and by induction over that sequence every operation reads the same values and the final state agrees. The predicates read the conditions, and each condition is computed in its block before any predicate that uses it (topological order).

Proposition 23.5.10 (Control-equivalent blocks share a predicate)

For an acyclic single-entry, single-exit region, the formula of Definition 23.5.4 is exact, and blocks with the same \(\mathrm{CD}\) set have the same exact predicate.

Proof sketch (full proof: [PS91], with control dependence from [FOW87])

\(B\) executes iff the path takes some edge \((X, o)\) with \(B\) post-dominating the \(o\)-successor of \(X\) and \(X\) executes: from that edge on, every path to the exit passes through \(B\). Conversely, if \(B\) executes, let \((X, o)\) be the last branch edge on the path before \(B\) that "commits" to \(B\). Its target is post-dominated by \(B\) and \(X\) is not (otherwise an earlier edge would commit), so \((X, o) \in \mathrm{CD}(B)\). Hence \(p(B) = \bigvee_{(X, o) \in \mathrm{CD}(B)} p(X) \wedge \mathrm{lit}(X, o)\) is exact by induction on the nesting of control dependence, and it depends only on \(\mathrm{CD}(B)\).

Nullified does not mean free, or harmless

A nullified load still occupies an issue slot. A speculated load (executed unguarded, the way EarlyIfConversion executes both arms) can fault on an address that is only valid on the other path. That is why Algorithm 23.5.7 requires every hoisted instruction to be speculatable and refuses stores, and why vectorizers use masked loads. It is also why the predicate of Definition 23.5.2 has to guard every side effect.

Hyperblock formation¶

A hyperblock is correct by composition. Tail duplication preserves semantics (Theorem 23.4.11) and makes \(H\) single-entry. If-conversion of \(H\) is an equivalence (Theorem 23.5.9), where each exit branch is guarded by the predicate of the edge it replaces, so a path leaves \(H\) at the same edge as before. The heuristic selection only affects performance.

LLVM's machine if-converters¶

For EarlyIfConversion, Theorem 23.5.9 applies with the select as a data-flow form of predication. Both arms execute unconditionally, which is legal because they have no side effects and cannot trap (the precondition). A phi of the tail that chose between the arms' values now reads a select on the same condition, which yields the same value on every path. For IfConverter, the predicated instructions are exactly Definition 23.5.2's guarded operations, with the machine's condition flags as the predicate.

5. Complexity¶

Let \(n\) be the blocks, \(e\) the edges and \(k\) the branch conditions of the region.

Technique	Time	Space / code size	Notes
Predicate assignment by predecessors (Alg. 23.5.3)	\(O(n + e)\) formula nodes if predicates are shared as DAG nodes	formulas can double per level if expanded	one guarded op per original op
RK assignment via control dependence	\(O(n + e)\) after post-dominators (\(O(e\,\alpha(e, n))\))	one predicate per predicate class	fewest predicate definitions
Hyperblock formation (Alg. 23.5.6)	\(O(n + e)\) plus tail duplication	growth: duplicated tails	selection heuristics are linear
EarlyIfConversion (Alg. 23.5.7)	per diamond: trace metrics, amortized \(O(\text{size})\)	none (merges blocks)	limit 30 instructions per arm

Justification. Algorithm 23.5.3 visits every edge once. Sharing \(p(P)\) as a node, each block's predicate is one OR of \(\lvert \mathrm{preds} \rvert\) ANDs. Control dependence comes from post-dominators and the dominance-frontier construction on the reverse CFG (Lesson 15.4).

Pathological family (work). A chain of \(k\) diamonds whose left arms have \(a\) instructions and right arms 1 instruction, where the left arm is almost never taken: if-conversion makes every execution issue \(k(a + 1)\) instructions instead of about \(k\). For a 4-wide machine and \(a = 20\), the converted chain takes at least \(21k/4 \approx 5k\) cycles against about \(k\) cycles plus rare mispredictions. That is why every if-converter bounds arm sizes (-early-ifcvt-limit) and compares against the misprediction penalty. Predicate formulas. Written out without sharing, \(p(B)\) is a disjunction over all paths to \(B\). A ladder of \(k\) join-split pairs has \(2^k\) paths, so the expanded formulas grow exponentially, while the shared or control-dependence forms stay linear.

If-conversion and predicate assignment¶

Partial predication (select/cmov only, [MHM+95]): only moves are conditional; everything else is speculated. Works on any ISA, but it cannot guard stores or trapping operations.
Predicate promotion (IMPACT): remove the guard from an operation whose result is dead when the predicate is false, which shortens dependence chains.
Reverse if-conversion (Warter et al.): turn predicated code back into branches after scheduling, for machines without predication.

Hyperblock formation¶

Profile-driven block selection value [MLC+92]: rank blocks by frequency relative to size and include the best ones, instead of fixed thresholds.
Dynamic predication / wish branches (hardware proposals): let the processor decide at run time whether to predicate. It needs microarchitectural support.
GPU structurization (LLVM StructurizeCFG, AMDGPU SIAnnotateControlFlow): make every region structured, then run both arms under execution masks. This is if-conversion of whole regions, forced by the SIMT execution model.

LLVM's machine if-converters¶

Data-dependent branch analysis (-enable-early-ifcvt-data-dependent): a condition that comes from a load is harder to predict, so the pass allows the full misprediction penalty instead of half.
MachineCombiner-style cost models: use MachineTraceMetrics for critical-path and resource-length estimates. This is the same machinery as EarlyIfConversion.
Target-specific converters (HexagonEarlyIfConv, the x86 X86CmovConversion pass that turns cmov back into branches when a branch would be better).

7. In real compilers¶

If-conversion and predicate assignment¶

Full predication survives today mostly on GPUs, where a SIMD "thread" runs both arms of a divergent branch with a lane mask. LLVM's AMDGPU back end computes the masks in SIAnnotateControlFlow and SILowerControlFlow (llvm/lib/Target/AMDGPU/) [LLVM-AMDGPU-CF]. GCC's if-converter for loops is tree-if-conv.cc, and its RTL if-converter is gcc/ifcvt.cc (noce_process_if_block for selects, cond_exec_process_if_block for predication) [GCC-ifcvt].

Predicate assignment as an execution mask (AMDGPU)

Reproduce (llc 23.1.2):

cat > gpu.ll <<'EOF'
define amdgpu_kernel void @k(ptr addrspace(1) %out, i32 %x) {
entry:
  %id = call i32 @llvm.amdgcn.workitem.id.x()
  %cA = icmp sgt i32 %id, %x
  br i1 %cA, label %B, label %C
B:
  %b = mul i32 %id, 3
  br label %F
C:
  %c = add i32 %id, 7
  br label %F
F:
  %v = phi i32 [ %b, %B ], [ %c, %C ]
  %p = getelementptr i32, ptr addrspace(1) %out, i32 %id
  store i32 %v, ptr addrspace(1) %p
  ret void
}
declare i32 @llvm.amdgcn.workitem.id.x()
EOF
llc -O2 -mtriple=amdgcn-amd-amdhsa -mcpu=gfx900 gpu.ll -o - \
  | sed -n '/^k:/,/s_endpgm/p' | grep -v '^\s*;\|^\s*$'

Output (complete):

k:                                      ; @k
    s_load_dword s0, s[8:9], 0x8
    s_waitcnt lgkmcnt(0)
    v_cmp_ge_i32_e32 vcc, s0, v0
    s_and_saveexec_b64 s[0:1], vcc
    s_xor_b64 s[0:1], exec, s[0:1]
    v_add_u32_e32 v1, 7, v0
    s_andn2_saveexec_b64 s[0:1], s[0:1]
    v_mul_u32_u24_e32 v1, 3, v0
    s_or_b64 exec, exec, s[0:1]
    s_load_dwordx2 s[0:1], s[8:9], 0x0
    v_lshlrev_b32_e32 v0, 2, v0
    s_waitcnt lgkmcnt(0)
    global_store_dword v0, v1, s[0:1]
    s_endpgm

What to notice: there is no branch. exec is the predicate register of 64 lanes. v_cmp_ge computes \(\neg c_A\) per lane (the compiler emitted the else arm first). s_and_saveexec sets exec to the old mask AND \(\neg c_A\), which is \(p(C)\), and saves the old mask. The add of block C runs under it. s_andn2_saveexec switches exec to the saved mask minus those lanes, which is \(p(B)\), for the mul. s_or_b64 restores the mask at the join, where \(p(F) = \mathrm{true}\) (Algorithm 23.5.3 and Theorem 23.5.9, one lane at a time).

Hyperblock formation¶

No mainstream CPU compiler forms hyperblocks by that name today. The idea survives in partial form in if-converters that merge nested diamonds into one predicated block. Hexagon's HexagonEarlyIfConv (llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp) predicates across multiple blocks of a region with a cost limit (-eif-limit) [LLVM-HexEIF].

A predicated inner region on Hexagon

Reproduce (clang 23.1.2, llc 23.1.2):

cat > hb.c <<'EOF'
int hb(int *a, int n, int x) {
  int s = 0;
  for (int i = 0; i < n; i++) {
    int v = a[i];
    if (v > x) {
      if (v & 1) s += v;
      else s -= v;
    } else {
      s ^= v;
    }
  }
  return s;
}
EOF
clang-23 --target=hexagon -mcpu=hexagonv68 -O2 -fno-unroll-loops -S -emit-llvm hb.c -o hb.ll
llc -O2 -mtriple=hexagon -mcpu=hexagonv68 hb.ll -o - \
  | sed -n '/^.LBB0_2:/,/^.LBB0_5:/p' | grep -v '^\s*\.p2align\|^\s*$'

Output (complete):

.LBB0_2:                                //   in Loop: Header=BB0_3 Depth=1
    {
        p0 = tstbit(r1,#0)
        if (!p0.new) r0 = sub(r0,r1)
        if (p0.new) r0 = add(r1,r0)
        r3 = add(r3,#4)
    } :endloop0
    {
        jump .LBB0_5
    }
.LBB0_3:                                // Block address taken
                                        // %.preheader
                                        // =>This Inner Loop Header: Depth=1
    {
        r1 = memw(r3+#0)
        if (cmp.gt(r1.new,r2)) jump:t .LBB0_2
    }
// %bb.4:                               //   in Loop: Header=BB0_3 Depth=1
    {
        r0 = xor(r1,r0)
        r3 = add(r3,#4)
    } :endloop0
.LBB0_5:                                // %.loopexit

What to notice: the inner if (v & 1) diamond, its test and the increment of the loop pointer are one predicated packet: p0 holds \(c = (v \mathbin{\&} 1)\) and the two arms run under p0 and !p0 (Definition 23.5.2). The outer branch v > x stays a branch, with the xor arm as a separate block. The converted region is a hyperblock of two of the three paths, the shape Algorithm 23.5.6 produces when one arm is not selected.

LLVM's machine if-converters¶

EarlyIfConverter::shouldConvertIf and SSAIfConv::convertIf in llvm/lib/CodeGen/EarlyIfConversion.cpp implement Algorithm 23.5.7 (it is enabled per target: on by default for AArch64, behind -x86-early-ifcvt on x86) [LLVM-EarlyIfCvt]. IfConverter in llvm/lib/CodeGen/IfConversion.cpp (AnalyzeBlock, IfConvertSimple, IfConvertTriangle, IfConvertDiamond) runs post-RA on ARM, Thumb-2 and others [LLVM-IfCvt].

EarlyIfConversion's cost model decides on x86

Reproduce (llc 23.1.2):

cat > br.ll <<'EOF'
define i64 @pick(i64 %a, i64 %b, i64 %c, i64 %d) {
entry:
  %cmp = icmp slt i64 %a, %b
  br i1 %cmp, label %then, label %else
then:
  %m = mul i64 %c, %d
  %t = add i64 %m, %a
  br label %join
else:
  %e = sub i64 %c, %d
  br label %join
join:
  %r = phi i64 [ %t, %then ], [ %e, %else ]
  ret i64 %r
}
EOF
for f in "" "-x86-early-ifcvt"; do echo "== default $f"
  llc -O2 -mtriple=x86_64-linux-gnu -mcpu=skylake $f -pass-remarks=early-ifcvt br.ll -o - 2>&1 \
    | grep -v '^\s*\.\|^#\|^$\|cfi\|^pick:'
done

Output (complete):

== default 
    movq    %rdx, %rax
    cmpq    %rsi, %rdi
    jge .LBB0_2
    imulq   %rcx, %rax
    addq    %rdi, %rax
    retq
    subq    %rcx, %rax
    retq
                                        # -- End function
== default -x86-early-ifcvt
remark: <unknown>:0:0: performing if-conversion on branch: the condition adds 2 cycles to the critical path, and the short leg adds another 2 cycles, and the long leg adds another 5 cycles, each staying under the threshold of 7 cycles.
    movq    %rdx, %r8
    subq    %rcx, %r8
    imulq   %rcx, %rdx
    leaq    (%rdx,%rdi), %rax
    cmpq    %rsi, %rdi
    cmovgeq %r8, %rax
    retq
                                        # -- End function

What to notice: by default x86 keeps the branch (and tail-duplicates the ret into both arms). With the pass enabled, both arms run and cmovge selects, and the remark shows Algorithm 23.5.7's test: 7 cycles is half of Skylake's MispredictPenalty of 14 (Lesson 23.1), and the extensions of 2, 2 and 5 cycles are all below it.

IfConverter predicates a block on 32-bit ARM

Reproduce (llc 23.1.2):

cat > arm2.ll <<'EOF'
define void @put(i32 %a, i32 %b, i32 %c, ptr %p, ptr %q) {
entry:
  %cmp = icmp slt i32 %a, %b
  br i1 %cmp, label %then, label %else
then:
  %t = add i32 %a, %c
  store i32 %t, ptr %p, align 4
  br label %join
else:
  %e = sub i32 %b, %c
  store i32 %e, ptr %q, align 4
  br label %join
join:
  ret void
}
EOF
for f in "" "-disable-ifcvt-simple"; do echo "== $f"
  llc -O2 -mtriple=armv7-linux-gnueabihf $f arm2.ll -o - \
    | grep -v '^\s*\.\|^$\|^put:\|End function\|@ %bb.0'
done

Output (complete):

== 
    cmp r0, r1
    ldrge   r0, [sp]
    subge   r1, r1, r2
    strge   r1, [r0]
    bxge    lr
    add r0, r0, r2
    str r0, [r3]
    bx  lr
== -disable-ifcvt-simple
    cmp r0, r1
    bge .LBB0_2
@ %bb.1:                                @ %then
    add r0, r0, r2
    str r0, [r3]
    bx  lr
    ldr r0, [sp]
    sub r1, r1, r2
    str r1, [r0]
    bx  lr

What to notice: the else block (load the stack argument q, subtract, store, return) becomes four instructions predicated on ge, including a conditional return bxge. The store is guarded, so this is true predication, which EarlyIfConversion could not do (it refuses stores). With the "simple" pattern disabled, the branch bge .LBB0_2 stays (the label line itself is filtered).

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
If-conversion and predicate assignment	removes all branches of an acyclic region, exactly (Theorem 23.5.9)	\(O(n + e)\)	no mispredictions; issues both arms; guards every side effect	moderate: predicates, control dependence, register pressure on predicates	vectorizers, GPUs (execution masks), IA-64
Hyperblock formation	converts only frequent, safe blocks; single entry by tail duplication	linear plus duplication	keeps the benefit, avoids the rare long arm	high: selection heuristics plus tail duplication plus predication	IMPACT, Itanium compilers; partial forms in Hexagon, GPU structurizers
LLVM's machine if-converters	small diamonds and triangles; selects (Early) or full predication (post-RA)	per-diamond trace metrics	converts only when the critical path grows by less than half the mispredict penalty	moderate; target hooks	AArch64 `csel` (Early, default on), x86 `cmov` (opt-in), ARM/Thumb-2 predication (IfConverter)

Choose full if-conversion when the hardware predicates cheaply (GPU masks, IA-64) or a vectorizer needs straight-line code. Choose hyperblocks when some paths are cold or unsafe: convert the hot ones and branch to the rest. Choose select-based conversion on out-of-order CPUs only for small, unpredictable diamonds, and let the cost model compare against the misprediction penalty. That is what LLVM does.

9. Assessment¶

Quiz: pred-running (mapping: block → size of its truth set), pred-count (number), cd-sets (mapping), ifcvt-threshold (number), hyperblock-set (set), nullify-vs-speculate (single), find-shouldconvert (text: shouldConvertIf). Tags if-conversion, hyperblock, llvm-ifcvt.
Drills: ./course drill ifconvert (predicates by truth table; medium: + number of predicate classes; hard: unstructured regions). Hyperblock selection and LLVM's cost model are covered by the worked examples and the quiz; they depend on profile thresholds and machine traces that a drill would have to invent.
Flashcards: tags if-conversion, hyperblock, llvm-ifcvt.

References¶

See the chapter references.

Lesson 23.5 — If-conversion, predication and hyperblocks¶

1. Problem and motivation¶

If-conversion and predicate assignment¶

Hyperblock formation¶

LLVM's machine if-converters¶

2. Definitions and algorithms¶

If-conversion and predicate assignment¶

Hyperblock formation¶

LLVM's machine if-converters¶

3. Worked examples¶

If-conversion and predicate assignment¶

Hyperblock formation¶

LLVM's machine if-converters¶

4. Invariants and correctness¶

If-conversion and predicate assignment¶

Hyperblock formation¶

LLVM's machine if-converters¶

5. Complexity¶

6. Variants and refinements¶

If-conversion and predicate assignment¶

Hyperblock formation¶

LLVM's machine if-converters¶

7. In real compilers¶

If-conversion and predicate assignment¶

Hyperblock formation¶

LLVM's machine if-converters¶

8. Comparison¶

9. Assessment¶

References¶