Predication (computer architecture)
Predication is an architectural technique in which execution of an instruction is governed by a Boolean value called a predicate. A predicated instruction produces its normal architectural effects when the predicate is true and produces no architecturally visible effects when the predicate is false. Predication therefore represents a control decision within an instruction rather than exclusively through a conditional branch.
The principal use of predication is the conversion of short regions of control flow into conditionally applied operations. This transformation reduces the number of dynamic branches and can limit the performance cost associated with branch prediction. It also causes instructions from paths whose predicates are false to occupy instruction-fetch, decode, and execution resources. Its performance consequences depend on branch predictability, path length, available instruction-level parallelism, and the treatment of predicated operations within the microarchitecture.
Architectural semantics
A predicated instruction can be represented as
[ P \Rightarrow S, ]
where (P) is a Boolean predicate and (S) is the state transition ordinarily performed by the instruction. If (P) evaluates to true, the processor applies (S). If (P) evaluates to false, the architectural state remains unchanged with respect to that instruction.
For example, an addition guarded by predicate (p) has the abstract form
[ p \Rightarrow r_1 \leftarrow r_2 + r_3. ]
When (p) is false, the previous value of (r_1) is retained. Architectures with precise predication also suppress exceptions and memory effects associated with a false-predicate instruction. An implementation may perform internal work before the predicate is resolved, but it cannot expose a register update, a memory access, or an architectural exception forbidden by the instruction's semantics.
Predicates are represented either by dedicated predicate registers or by conditions derived from a status register. A status-register design commonly evaluates relations expressed through condition flags generated by arithmetic or comparison instructions. A predicate-register design stores Boolean results explicitly and can preserve several independent control conditions at the same time.
Predication differs from speculative execution. A speculatively executed instruction is provisionally treated as belonging to the active control path, with mechanisms provided to discard its effects after an incorrect prediction. A false-predicate instruction is defined by the instruction set architecture as having no architectural effect, irrespective of any prediction made by the implementation.
If-conversion
The compiler transformation most closely associated with predication is if-conversion. It replaces a control-flow region with operations guarded by predicates. A conventional conditional assignment such as
if c:
x = a + b
else:
x = d - e
can be represented by complementary predicates:
c ⇒ x = a + b
not c ⇒ x = d - e
The transformed region has no internal branch, although it retains the data dependence required to obtain (c). Control dependence on the original branch is replaced by predicate dependences attached to the affected instructions. The processor may consequently issue independent operations from both paths before the governing condition has been fully incorporated into the retirement decision.
If-conversion is most directly applicable when the controlled paths are short. Converting a large region can substantially increase the number of instructions fetched and examined because operations belonging to inactive paths remain present in the instruction stream. Predicated execution can also lengthen dependence chains when many operations require the same predicate or when predicates are constructed through several comparisons.
Compiler analyses therefore associate if-conversion with estimated execution frequency, branch predictability, resource pressure, and exception behavior. These factors are combined within the compiler's cost model rather than constituting separate architectural rules. Scott Mahlke and Wen-mei Hwu incorporated predication into the hyperblock model, in which selected control-flow paths are combined into a single-entry region suitable for aggressive scheduling. Joseph A. Fisher's work on trace scheduling supplied an earlier framework for scheduling operations across basic-block boundaries, although trace scheduling itself does not require architectural predicates.
Condition flags and explicit predicates
Condition-code predication derives an instruction's guard from arithmetic flags. In a typical arrangement, a comparison records whether its result was negative, zero, or associated with an unsigned carry. A later instruction contains a condition field that selects a Boolean expression over those flags. This encoding avoids a separate predicate-register specifier but creates dependencies through a shared status register.
Explicit predicate registers separate Boolean control values from general arithmetic flags. Comparisons write one or more predicate registers, and predicated instructions identify the selected register in their encodings. Several conditions can remain live concurrently, which supports nested control regions and software scheduling across multiple decisions. The additional register state requires encoding space and contributes to dependency tracking in an out-of-order execution implementation.
Some architectures provide complementary predicate results from a single comparison. One destination records the comparison result while another records its logical complement. This arrangement directly represents the two successors of a binary branch and reduces the need for a separate logical-negation instruction.
Use in ARM architectures
The original ARM architecture family made broad use of condition-code predication. In the 32-bit A32 instruction set, most instructions contain a condition field interpreted from the N, Z, C, and V flags of the current program status register. Arithmetic instructions, data transfers, and branches can consequently share the same conditional encoding mechanism.
During the definition and evaluation of the early ARM instruction set, Sophie Wilson developed the instruction encoding and its programmer-visible organization, while Steve Furber and You Watanabe participated in the architectural analysis of conditional execution and pipeline behavior. The resulting design associated predication with the regular fixed-width encoding of A32 rather than with a separate class of conditional instructions.
Broad predication allowed short conditional sequences to be represented without branches. The condition field nevertheless consumed instruction-encoding capacity, and long predicated regions caused inactive instructions to pass through much of the pipeline. These trade-offs changed as ARM implementations adopted deeper pipelines, wider issue, and more capable branch predictors.
The compressed Thumb instruction set initially provided substantially less general conditional execution because its narrower encodings had limited space for condition fields. Thumb-2 introduced the IT instruction, which established a condition for a short sequence of following instructions. Later architectural revisions restricted extensive use of IT blocks. AArch64 omitted the universal per-instruction condition field and instead provides conditional branches together with operations such as conditional select and conditional comparison.
Use in IA-64
IA-64 incorporates predication as a central component of its explicitly parallel instruction computing model. The architecture defines a large predicate-register file, with predicate register p0 permanently representing true. Most computational instructions can name a predicate register that determines whether their architectural effects occur.
IA-64 comparisons can produce related predicate values for subsequent control decisions. Predication interacts with instruction grouping, speculative loading, and compiler scheduling, allowing operations from different control-flow paths to coexist within scheduled instruction bundles. The architecture retains branches for larger control transfers because predicate execution does not remove the fetch and execution cost of inactive paths.
John C. Dehnert and Bratin Saha contributed to compiler techniques that organized predicated regions for IA-64 scheduling. Their work treated predicate relations as part of the dependence structure used by the compiler, alongside register and memory dependences. This treatment was necessary because two instructions writing the same architectural register can coexist safely when their predicates are mutually exclusive.
Partial predication and masked execution
An architecture need not make every instruction predicable. Conditional move instructions implement a restricted form in which a register receives a new value only when a condition holds. The x86 CMOVcc family follows this model. It removes a branch around a register assignment but does not provide a general predicate field for arbitrary scalar instructions.
Modern vector processors frequently use mask registers. Each mask bit controls the corresponding vector element, so one instruction can update selected lanes while preserving the others. AVX-512 uses this organization for many vector operations and supports either merging with the old destination or replacing inactive elements with zero. Lane masking extends the semantic principle of predication from one scalar operation to a set of elementwise operations.
Execution masks in single instruction, multiple threads processors are related but operate at the level of active threads or lanes. When threads in a group follow different branches, the machine can execute each path under a different mask. This process preserves the program's control-flow semantics while serializing paths that diverge within the group.
Microarchitectural effects
Predication changes the allocation of work rather than eliminating the underlying conditional computation. A branch-based region fetches one predicted path and pays a recovery cost when the prediction is incorrect. A predicated region exposes operations from multiple paths in the same instruction stream and suppresses the architectural effects of operations whose predicates are false.
The result is a balance between control speculation and unused execution. Predication reduces dependence on branch prediction for the converted region, while branch prediction avoids processing instructions from a path predicted not to execute. The balance shifts with pipeline depth and issue width because these properties influence both misprediction cost and the amount of inactive work that can occupy the machine.
Predicate resolution also affects scheduling. Instructions whose predicates remain unknown can wait until the relevant Boolean value becomes available, or they can begin execution under internal speculation when the microarchitecture can suppress all invalid effects. Memory operations require particular treatment because translation faults, access faults, and externally visible transactions cannot be attributed to an architecturally null instruction.
Predication can simplify the visible control-flow graph while increasing pressure on registers and execution units. Values from multiple paths may need to remain live concurrently, and the compiler must preserve the relation between predicates that guard competing definitions. These effects connect predication with register allocation, instruction scheduling, and static single-assignment form.