Basic Block (BB)

Definition

A basic block (BB) is a maximal straight-line sequence of statements with a single entry point and a single exit point, terminated by a branch, jump, or other control-flow transfer. Basic blocks are the atomic nodes from which a Control Flow Graph (CFG) is constructed: edges between BBs represent possible transfers of control.

In the hardware / RTL setting used by Fine-Grained Code Analysis for Processor Fuzzing, basic blocks are derived from the HDL source. Conditional constructs such as if (...) ... else if (...) ... else ... give rise to multiple BBs, while continuous-assignment statements form their own BB kind.

Basic-Block Variants in HDL

The paper distinguishes two categories of BBs visible in the example snippet:

The instrumentation step of the paper "create[s] several registers, each with a width of 500, to store whether each basic block has been accessed (excluding 'assign' type BBs). A basic block that has been accessed will have the corresponding bit in the register set to 1."

Dependency Analysis Between Basic Blocks

In cycle-based hardware, the value used in a statement in one cycle may have been produced in a statement several cycles earlier. The paper formalizes a dependency analysis whose goal is to make the CFG precisely reflect those temporal / data-flow predecessor relationships.

Algorithm (paraphrased from the paper):

1. Iterate over all guard conditions of branches in the design, G = {g1, g2, ...}.

2. For each guard g, identify every assignment statement e that writes a variable used in g.

3. Convert each e to Single Static Assignment (SSA) form and check the satisfiability of

   $$Q(i) = \neg g_{i_0} \land e \land g_{i_1}$$

4. If satisfiable, the BB containing e is recorded as a predecessor of the BB guarded by g.

5. If e is itself an assignment, recursively identify the right-hand-side variables of e and add predecessor links to the BBs that define them.

6. Repeat until a fixed point is reached (no new predecessor relationships can be added).

This produces a "refined CFG" that captures, for example, that a1 is a predecessor of a2 (because a1 writes status_isa, read by a2), and that b4 is connected to a3 (because of the illegal_insn assignment).

Worked Example (Rocket processor, illegal-instruction handling)

The paper's Figure 2 illustrates a simplified snippet with BBs b1–b5 and a1–a3:

• Left CFG (without dependency analysis): shows only the syntactic control flow from the if/else if/else chain.
• Right CFG (after dependency analysis): additionally draws b4 → a3 via the illegal_insn assignment, and a1 → a2 and a1 → b2 via the assign of status_isa / reg_misa. The result "provides a more accurate representation of the dependencies between basic blocks."

Role in the Processor-Fuzzing Pipeline

Basic blocks are the granularity at which:

• Branch-coverage instrumentation records accessed BBs in a hardware register (one bit per BB, up to 500 BBs in the described setup).
• Static analysis builds the CFG and the predecessor graph used downstream.
• The Fuzz Loop consumes coverage feedback and distance heuristics derived from the CFG to drive mutation selection in the fuzz engine.

See Also

• Static Analysis — the technique that constructs CFGs and predecessor relations from BBs.
• Branch Coverage Instrumentation — the technique that records which BBs have been hit during simulation.
• Fine-Grained Code Analysis for Processor Fuzzing — the paper that operationalizes BB-level static analysis to drive processor RTL fuzzing.