Skip to content
STIMSMITH

Branch Scenario Generation

Concept WIKI v1 · 6/1/2026

Branch scenario generation is a constrained-random verification technique for processor instruction streams that makes branch behavior both observable and bounded. The evidence describes constraint patterns for forward branches, where operand values are prepared to raise taken probability, and backward branches, where loop-like constraints prevent impractically long or endless execution.

Overview

Branch scenario generation is used in constrained-random processor verification to avoid the low usefulness of pure random instruction streams around branch instructions. Random register contents make branch conditions such as equality very unlikely, so forward branches often fall through and backward branches can remain in loops for a very long time. The solution described in the evidence is to generate branch-related instruction sequences with explicit constraints on surrounding operations and register relationships.

Forward branch generation

For forward branches, the evidence recommends initializing the compared register operands immediately before the branch. A specific pattern is to place an ADDI instruction before the branch, using the same operands and a small immediate value. In the cited example, setting R1 = R2 + {-2:2} raises the probability that R1 == R2 to 20%, making the branch condition much more likely to exercise both taken and not-taken behavior.

In constraint terms, the operation preceding a forward branch should therefore be an ADDI with the same operands as the branch comparison and a small immediate value.

Backward branch generation

Backward branches are treated as loop scenarios. The goal is to avoid absurdly long or endless loops while still exercising branch logic over multiple iterations.

The described constraint pattern is:

  • the operation preceding a backward branch is an ADDI with the same operands and a small negative immediate value;
  • the operand acting as a loop index is incremented by 1 inside the loop, just before the branch;
  • the two registers used by the branch comparison must not be modified elsewhere inside the loop.

This construction causes the compared values to converge and eventually terminate the loop, covering behavior ranging from immediate fall-through to several loop iterations.

Place in the scenario framework

The evidence places branch scenario generation within a broader scenario-based stimulus framework. User-defined scenarios can share reusable methods through a common instruction scenario base class, and constraints between instruction objects can be implemented there. More broadly, a scenario generator can select and randomize scenario objects across constrained-random, directed-random, and directed scenarios until a user-specified stopping condition is reached.

A directed scenario can also be loaded from a pre-assembled program trace file through a class method in the common scenario infrastructure, which complements constrained branch generation when exact behavior must be targeted.

LINKED ENTITIES

2 links
Instruction Scenario PART_OF
common instruction scenario base class IMPLEMENTS

CITATIONS

9 sources
9 citations
[1] Pure random instruction sequences are unlikely to create useful branch programs because random register values rarely satisfy branch conditions; this makes forward branches likely to fall through and backward branches likely to stay in loops for a very long time. Applying constrained-random verification to microprocessors
[2] Backward and forward branches can be handled using constrained scenarios that restrict instruction sequences so forward branches have reasonable probability and backward branches avoid endless loops. Applying constrained-random verification to microprocessors
[3] To increase forward-branch probability, the comparing operands can be initialized just before the branch; the example `R1 = R2 + {-2:2}` makes `R1 == R2` occur with 20 percent probability. Applying constrained-random verification to microprocessors
[4] For forward branches, the operation preceding the branch should be an `ADDI` using the same operands and a small immediate value. Applying constrained-random verification to microprocessors
[5] Backward branches can be modeled as loop scenarios so that the branch is taken for a bounded number of iterations until the compared register values become equal and the branch falls through. Applying constrained-random verification to microprocessors
[6] For backward branches, the preceding operation should be an `ADDI` with the same operands and a small negative value; the loop index is incremented by 1 just before the branch, and the compared registers must not be modified elsewhere inside the loop. Applying constrained-random verification to microprocessors
[7] The common instruction scenario base class can encapsulate useful shared methods and implement relationships between instruction objects as constraints. Applying constrained-random verification to microprocessors
[8] A class method in the common scenario infrastructure can load a directed scenario from a file containing a pre-assembled program trace. Applying constrained-random verification to microprocessors
[9] A scenario generator can randomly select and randomize constrained-random, directed-random, or directed scenarios until a user-specified stopping condition is reached. Applying constrained-random verification to microprocessors