Skip to content
STIMSMITH

Branch Taken/Not-Taken Probability

Concept WIKI v1 · 6/5/2026

Branch taken/not-taken probability describes the likelihood that a conditional branch instruction resolves to the taken path versus falling through. In constrained-random verification of microprocessors, this probability is a central concern because naïve random instruction sequences almost never produce the register relationships that satisfy branch conditions, causing forward branches to fall through and backward branches to form effectively infinite loops. Verification engineers therefore impose constraints on the operations preceding branches to raise the taken/not-taken probability to a level that exercises the branch logic without producing degenerate execution patterns.

Overview

In constrained-random verification (CRV) of microprocessors, branch taken/not-taken probability refers to the likelihood that a conditional branch resolves as taken (control transfers to the target) rather than as not-taken (execution falls through to the next sequential instruction). Whether a branch is taken depends on the relationship between the values held in its comparing registers at the moment the branch executes. With pure random stimulus, that relationship is almost never what the branch condition requires, so random instruction streams systematically under-exercise branch evaluation logic.

The Problem with Pure Random Stimulus

When stimulus is generated without any awareness of branch conditions, the operands of a branch instruction are essentially random 32-bit register values. The probability of such values satisfying a typical branch relation is vanishingly small:

  • For a forward branch such as BEQ R1, R2, LABEL, the instruction will fall through because R1 almost never equals R2. The branch condition evaluation logic is therefore not exercised.
  • For a backward branch such as BNE R3, R4, LABEL, the loop is almost never exited because R3 and R4 almost never become equal, leaving program execution stuck in the loop for a very large number of iterations.

Both outcomes defeat the purpose of randomized verification: the testbench fails to cover the branch condition logic and, in the case of backward branches, may produce effectively infinite loops that stall the simulation.

Raising the Probability for Forward Branches

A common way to control the taken/not-taken probability of a forward branch is to constrain the operation immediately preceding the branch so that the comparing registers are set up to a known relationship. Specifically, the operation preceding a forward branch can be constrained to be an ADDI (add immediate) operation that uses the same operands as the branch and a small immediate value.

For example, if R1 = R2 + {-2:2} is executed immediately before BEQ R1, R2, LABEL, then R1 equals R2 in roughly one of five cases, giving a taken probability of about 20 percent. Choosing a wider or narrower immediate range lets the verification engineer tune the taken/not-taken probability to a useful value — high enough to traverse the taken path frequently, but not so high that the not-taken path is starved of coverage.

Controlling Backward Branches as Loop Scenarios

Backward branches are handled by treating them as loop scenarios rather than by tuning a single probability. The operation preceding a backward branch is constrained to be an ADDI with the same operands and a small negative immediate value, so that the operand being modified serves as a loop index. Inside the loop, the same operand is incremented by 1 just before the branch, and the two branch-comparing registers are not modified by any other instruction in the loop body.

Under this arrangement:

  • If the initial immediate value is -1, the two comparing registers are already equal when the branch is evaluated, the BNE falls through, and the loop executes exactly once.
  • If the initial immediate value is less than -1, each iteration brings the register values one step closer, so the branch is taken for several iterations and only falls through when the index reaches the comparison value.

This structure avoids absurdly long loops while still producing every condition between a simple fall-through branch and a loop with several iterations, which is the desirable coverage behavior for backward branches.

Boundary Conditions

Even with these constraints, the testbench must guard against corner cases. For example, a backward branch such as BGT R1, R2, LABEL_X is always taken if R2 holds the smallest representable value, so the testbench has to consider such boundary conditions explicitly when setting up the registers that feed the branch.

Relationship to Stimulus Generation

The control of branch taken/not-taken probability is the practical motivation for the broader technique of generating branch stimulus under constraints. By placing restrictions on the operation sequence around a branch, constrained-random and directed-random scenarios can deliver instruction streams in which forward branches are taken with reasonable frequency and backward branches terminate after a controllable number of iterations.

LINKED ENTITIES

1 links
Constraint-Based Branch Stimulus Generation USES

CITATIONS

6 sources
6 citations
[1] Random 32-bit register values are extremely unlikely to satisfy branch conditions, so pure random instruction streams cause forward branches to fall through and backward branches to stall in long loops. Applying Constrained-Random Verification to Microprocessors
[2] Using an ADDI operation of the form R1 = R2 + {-2:2} immediately before a forward branch raises the probability that the branch is taken to roughly 20 percent. Applying Constrained-Random Verification to Microprocessors
[3] The operation preceding a forward branch should be constrained to be an ADDI with the same operands and a small immediate value in order to control the taken/not-taken probability. Applying Constrained-Random Verification to Microprocessors
[4] The operation preceding a backward branch should be an ADDI with the same operands and a small negative value, with the index incremented by 1 inside the loop and the two comparing registers not modified elsewhere in the loop body. Applying Constrained-Random Verification to Microprocessors
[5] Modeling backward branches as loop scenarios avoids absurdly long loops while still producing all conditions from a single fall-through to several loop iterations. Applying Constrained-Random Verification to Microprocessors
[6] Boundary conditions such as a backward BGT branch that is always taken when the comparison register holds the smallest possible value must be considered in the testbench. Applying Constrained-Random Verification to Microprocessors