If-Conversion, Predication, and the Limits of Speculation

A branch is a barrier to every optimization that wants to move code. Instructions on the two sides of a branch cannot be interleaved, because only one side executes. A short block ending in a branch has almost no scheduling freedom, and on a machine with a wide issue width or a deep pipeline, that freedom is exactly what the block needs; the block-level bound that the branch prevents the scheduler from reaching is derived in List Scheduling and the Critical Path.

If-conversion removes the barrier by turning control dependence into data dependence. The branch disappears, both sides of the conditional execute, and a predicate selects which results survive. The cost is that the work on the not-taken side is performed even when its result is discarded. Whether that trade is good depends on the ratio of the two sides’ sizes, on the predictability of the branch, and on whether the speculative work can fault.

The Transformation

The canonical input is a diamond: a condition, two blocks, and a join. The condition computes a predicate, and the join uses a value that one block or the other defined.

Without if-conversion, the code has a compare, a branch, two paths, and a join label. With if-conversion, the compare produces a predicate register, both blocks execute with their instructions predicated on the predicate or its complement, and the join’s value is a select between the two definitions.

On a target with architectural predicate registers, the transformation is direct: each instruction in a block is annotated with the predicate, and the hardware squashes it when the predicate is false. On a target without predicate registers, the transformation uses a conditional move for the final selection, and the two sides still execute unconditionally. The second form is weaker: the arithmetic on the not-taken side runs and its side effects, if any, are not undone. It is only legal when the not-taken side is free of side effects and free of faults.

The value at the join is the place where the transformation can fail quietly. If both sides define the same variable and only one definition survives, a conditional move from one definition to the other is enough. If the sides have different shapes — one defines three values, the other defines one — the join needs a phi-like merge, and the code generator must materialize selects for every value that flows out. Each select is an instruction, so a diamond with many outputs costs many selects, and the transformation’s benefit shrinks.

The classical formulation, from the 1983 paper by Allen, Kennedy, Porterfield, and Warren, was framed in terms of the program dependence graph: the branch’s control dependence edges are replaced by data dependence edges from the predicate to the guarded instructions. That framing is still the clearest way to think about what the transformation does, because it makes explicit that the guarded instructions now depend on a value rather than on a position in the control-flow graph.

Profitability

The naive comparison is instruction count: if the two sides together are cheaper than the branch’s expected cost, convert. That comparison is wrong in both directions.

It is too optimistic because it ignores the execution of the not-taken side. A diamond where one side has ten instructions and the other has one, with the ten-instruction side taken one time in twenty, converts into eleven instructions executed every time, where the branch version executed one instruction nineteen times out of twenty. If-conversion is a loss by a factor of eleven on the common path.

It is too pessimistic because it ignores the cost of the branch itself. A mispredicted branch on a deeply pipelined machine flushes the pipeline and costs on the order of ten to twenty cycles, which is comparable to executing a dozen instructions. A branch whose outcome is unpredictable is expensive enough that executing both sides is often cheaper, and the crossover point depends on the misprediction penalty and on the sizes involved.

The practical rule is therefore profile-driven: convert when the branch is unpredictable or when the two sides are comparable in size, and leave the branch when one side is much larger and much less likely. Compilers that lack a profile use static heuristics — loops are taken, error paths are not, && chains short-circuit — and those heuristics are wrong often enough that profile-guided conversion is noticeably better than static conversion on branchy code.

There is a third factor the instruction-count comparison misses: the branch removes scheduling freedom even when it is correctly predicted. A block ending in a branch cannot overlap its work with the successor’s. If the successor is the hot path, the lost overlap may exceed the cost of executing the cold path. This is the argument that made if-conversion standard on VLIW machines, where the hardware does no reordering and the compiler’s schedule is the only overlap available; the bundle structure that makes the argument concrete is described in Bundling Instructions for VLIW Issue Slots.

Faults and the Speculation Contract

The hard constraint is that speculative execution must not introduce faults that the original program would not have taken. A load from a null pointer in the not-taken side of a conditional is not executed in the branch version; after if-conversion it is executed unconditionally, and the program crashes on an input where it previously did not.

Compilers handle this with a safety analysis. A load is safe to speculate if the compiler can prove the address is valid, if the target provides a non-faulting load, or if the load is marked as speculatable by an earlier analysis that established the invariant. The first case is the common one for array accesses inside a loop with a known bound; the second is available on some architectures as an explicit instruction; the third requires a whole-program or range analysis that is expensive and incomplete.

The same reasoning applies to division. A division by zero in the not-taken path traps when executed speculatively. Targets that provide a non-trapping divide, or a divide that returns a defined value for a zero divisor, allow the speculation; targets that trap do not, unless the compiler can prove the divisor nonzero.

Stores are the hardest case. A speculative store cannot be undone, so a store in a predicated block must either be suppressed by the hardware when the predicate is false, or the transformation must be refused. Architectures with predicated stores suppress them; architectures without them force the compiler to keep the branch, or to convert only the computation and leave the store behind a branch. This is why if-conversion on such targets often produces a hybrid: the arithmetic is predicated, the memory writes are not.

Exceptions and calls are the other barrier. A call in a predicated block must not execute when the predicate is false, because the call’s side effects are not reversible. A call that may throw must not execute speculatively for the same reason. The transformation therefore stops at any instruction with an observable side effect that the target cannot suppress.

Predicate Registers and Their Cost

Architectural predicate registers are a finite resource, and they interact with the register allocator in a way that is easy to miss. A nested conditional produces nested predicates, and the inner predicate is the conjunction of the outer predicate and the inner condition. Each conjunction needs a predicate register, and a deeply nested chain of conditionals can exhaust the available predicates, forcing the compiler to materialize the conjunction in a general register and test it, which reintroduces a branch.

Predicates also consume issue bandwidth. On a machine where a predicated instruction still occupies an issue slot even when its predicate is false, the not-taken side’s instructions cost slots. Some architectures skip the execution of false-predicated instructions at the issue stage, which recovers some of the cost, but the fetch and decode bandwidth is still consumed. The benefit of if-conversion on such a machine is the removal of the branch, not the removal of the work.

The register file pressure effect is subtler. Both sides of a converted diamond may define values that are live at the join, and the selects at the join keep both definitions live until the select executes. A diamond that defined one value on each side therefore has two live values where the branch version had one, and the extra live range is charged to the allocator. On a register-tight machine, converting a diamond can trigger spills, which is the same pressure-versus-latency trade that appears in scheduling.

Where It Belongs in the Pipeline

If-conversion has to run before scheduling, because its purpose is to create scheduling freedom, and after the analyses that establish load safety, because those analyses are expensive and should run once. It also has to run before register allocation, because the selects and the extra live ranges it creates are allocation problems.

Running it too early is a mistake for a different reason: if-conversion on the intermediate representation destroys the control-flow structure that loop optimizations and inlining use. A loop with a conditional inside becomes a loop with a predicate computation, and a pass that wanted to unroll it or to version it now has to reason about predicates. Most compilers therefore keep the conditional in the IR and apply if-conversion at the point where the IR is lowered to machine instructions, which is late enough to preserve structure and early enough to feed the scheduler.

The transformation also has to be undone in places. A converted diamond that the scheduler then places badly, or that the allocator spills around, may be worse than the branch it replaced. Compilers that convert aggressively sometimes reconvert — turning a select back into a branch — when the select’s operands turn out to be expensive to keep live. This reversal is rare, because by the time the problem is visible the control-flow structure is gone, which is a good illustration of why transformations that destroy structure are hard to undo.