Gate-level simulation and X-propagation

An accumulator that forgets to reset one register gave the right sum on all 200 cycles of its test under Verilator’s default settings, an unknown sum on all 200 under Icarus Verilog, and a different wrong sum for each of three random seeds. One bug, three verdicts. Unknown values are where simulations of RTL and of gates, and simulators of two states and of four, disagree most, and reset and initialisation bugs hide in those disagreements.

You will simulate a synthesised netlist next to its RTL, see why RTL is optimistic about x and gates can be pessimistic, find a register that lacks its reset, and use Verilator’s random start values as a cross-check. Yosys 0.69 built every netlist, Icarus Verilog 13.0 simulated them all, and Verilator 5.052 ran the reset case.

A netlist runs on the same testbench as its RTL

Gate-level simulationgate-level simulation: Simulating the netlist that synthesis built, its gates and flip-flops, usually on the testbench the RTL already passes, to find where the circuit that was built differs from the one that was simulated. runs the netlistnetlist: A list of the cells a design uses and the wires that connect them, written by synthesis and read by place and route and by timing analysis. More in “How chips are designed and verified” that synthesis built, on the testbench the RTL already passes. Yosys’s write_verilog turns its internal cells into Verilog expressions and always blocks unless told otherwise, so its generic netlist runs on any simulator as it is; a netlist of a real target’s cells needs that target’s simulation models of the cells beside it. acc8.sv is an 8-bit accumulator with a reset. The session synthesises it, renames the netlist’s module to acc8_gates so that both fit in one simulation, and drives both with the 8-bit LFSR of the counters lesson, which gives every simulator the same inputs:

// An 8-bit accumulator: while en_i is 1 it adds d_i at every clock edge; valid_o says the sum has been updated.
module acc8 (
  input  logic       clk_i,
  input  logic       rst_ni,
  input  logic       en_i,
  input  logic [7:0] d_i,
  output logic [7:0] sum_o,
  output logic       valid_o
);
  logic [7:0] acc_q;
  logic       valid_q;
  always_ff @(posedge clk_i or negedge rst_ni) begin
    if (!rst_ni) begin
      acc_q   <= '0;
      valid_q <= 1'b0;
    end else begin
      valid_q <= en_i;
      if (en_i) acc_q <= acc_q + d_i;
    end
  end
  assign sum_o   = acc_q;
  assign valid_o = valid_q;
endmodule

// The RTL of the accumulator and its gate-level netlist on the same inputs, compared after every clock edge.
// The netlist's module is renamed acc8_gates, so both fit in one simulation. Compile it with acc8.sv and the netlist
// of acc8.sv, or with the files of the accumulator that forgets its reset (+define+FORGET).
`ifdef FORGET
  `define RTL forget_reset
  `define GATES forget_reset_gates
`else
  `define RTL acc8
  `define GATES acc8_gates
`endif
module tb_gate_level;
  logic clk = 0, rst_n = 0, en = 0;
  logic [7:0] d = 0, sum_rtl, sum_gates;
  logic valid_rtl, valid_gates;
  logic [7:0] lfsr = 8'h01;     // the stimulus: the 8-bit LFSR of the counters lesson, the same on every simulator
  int differ = 0, unknown = 0;
  `RTL   rtl   (.clk_i(clk), .rst_ni(rst_n), .en_i(en), .d_i(d), .sum_o(sum_rtl),   .valid_o(valid_rtl));
  `GATES gates (.clk_i(clk), .rst_ni(rst_n), .en_i(en), .d_i(d), .sum_o(sum_gates), .valid_o(valid_gates));
  always #5 clk = ~clk;
  initial begin
    #12 rst_n = 1;
    for (int cycle = 1; cycle <= 200; cycle++) begin
      @(negedge clk);
      lfsr = (lfsr >> 1) ^ (lfsr[0] ? 8'hB8 : 8'h00);
      en = lfsr[7:6] != 2'b00;
      d  = lfsr;
      @(posedge clk); #1;
      if (sum_rtl !== sum_gates || valid_rtl !== valid_gates) differ++;
      if ($isunknown(sum_rtl) || $isunknown(sum_gates)) unknown++;
      if (cycle <= 3) $display("cycle %0d: en=%b d=%3d | RTL sum %3d | gates sum %3d", cycle, en, d, sum_rtl, sum_gates);
    end
    $display("200 cycles: %0d with a difference, %0d with an unknown sum", differ, unknown);
    $finish;
  end
endmodule

from session import run

# Synthesise the accumulator, write its netlist with the module renamed, and simulate both on one testbench.
run("""
yosys -q -p "read_verilog -sv acc8.sv; synth -top acc8; rename acc8 acc8_gates; write_verilog -noattr acc8_gates.v"
grep -c assign acc8_gates.v
grep -c always acc8_gates.v
grep -m 1 -A 2 "always" acc8_gates.v
iverilog -g2012 -Wall -o sim.vvp tb_gate_level.sv acc8.sv acc8_gates.v
vvp -n sim.vvp
""")

# Yosys 0.69 · Icarus Verilog 13.0 (stable)
$ yosys -q -p "read_verilog -sv acc8.sv; synth -top acc8; rename acc8 acc8_gates; write_verilog -noattr acc8_gates.v"
$ grep -c assign acc8_gates.v
37
$ grep -c always acc8_gates.v
9
$ grep -m 1 -A 2 "always" acc8_gates.v
  always @(posedge clk_i, negedge rst_ni)
    if (!rst_ni) acc_q[6] <= 1'h0;
    else if (en_i) acc_q[6] <= _27_[6];
$ iverilog -g2012 -Wall -o sim.vvp tb_gate_level.sv acc8.sv acc8_gates.v
$ vvp -n sim.vvp
cycle 1: en=1 d=184 | RTL sum 184 | gates sum 184
cycle 2: en=1 d= 92 | RTL sum  20 | gates sum  20
cycle 3: en=0 d= 46 | RTL sum  20 | gates sum  20
200 cycles: 0 with a difference, 0 with an unknown sum
tb_gate_level.sv:33: $finish called at 2016 (1s)

The netlist is 37 continuous assignments, most of them the adder’s gates, and 9 always blocks, one per flip-flop: acc_q has become eight single-bit registers, each with its asynchronous reset and its enable, beside valid_q. Over 200 cycles the RTL and the netlist agreed on every sum and every valid flag. That is the purpose of the run: a disagreement would mean the netlist is not the circuit the RTL simulation tested, the mismatches of the first lesson of this module, and an x in either column would point at a value that nothing set.

RTL turns an unknown select into a known branch

How an unknown value travels through a design, its X-propagationX-propagation: How an unknown value travels through a design in simulation: an AND with a 0 input gives 0 whatever the other input is, an XOR with an x gives x, and an if or a case may turn an x into a known branch., depends on how each statement and each gate treats it. x_select.sv makes one 4-bit choice between a = 1100 and b = 1010 in three ways, an if, a case and the ?: operator, and the testbench gives it sel = x, as an unreset register would. Silicon would give 1100 or 1010, so bit 3 is surely 1 and bit 0 surely 0, and bits 2 and 1 really are unknown. The same session builds two netlists of the module, which the next section reads:

// One 4-bit choice between a and b, written three ways. With sel unknown, each way gives its own answer.
module x_select (
  input  logic       sel,
  input  logic [3:0] a,
  input  logic [3:0] b,
  output logic [3:0] y_if,
  output logic [3:0] y_case,
  output logic [3:0] y_cond
);
  always_comb begin
    if (sel) y_if = a;
    else     y_if = b;
  end

  always_comb begin
    case (sel)
      1'b1:    y_case = a;
      default: y_case = b;
    endcase
  end

  assign y_cond = sel ? a : b;
endmodule

// x_select with sel = x, a = 1100 and b = 1010: the RTL's three styles, then two netlists of the same module, one
// with multiplexer cells and one built from AND and OR gates only (the files x_select_mux.v and x_select_gates.v).
module tb_x_select;
  logic       sel = 1'bx;
  logic [3:0] a = 4'b1100, b = 4'b1010;
  logic [3:0] if_r, case_r, cond_r, if_m, case_m, cond_m, if_g, case_g, cond_g;
  x_select       rtl (.sel(sel), .a(a), .b(b), .y_if(if_r), .y_case(case_r), .y_cond(cond_r));
  x_select_mux   mux (.sel(sel), .a(a), .b(b), .y_if(if_m), .y_case(case_m), .y_cond(cond_m));
  x_select_gates gat (.sel(sel), .a(a), .b(b), .y_if(if_g), .y_case(case_g), .y_cond(cond_g));
  initial begin
    #1;
    $display("sel = %b, a = %b, b = %b; silicon would give 1100 or 1010", sel, a, b);
    $display("RTL                    if %b  case %b  ?: %b", if_r, case_r, cond_r);
    $display("netlist, mux cells     if %b  case %b  ?: %b", if_m, case_m, cond_m);
    $display("netlist, AND/OR gates  if %b  case %b  ?: %b", if_g, case_g, cond_g);
  end
endmodule

from session import run

# Two netlists of x_select.sv: the usual synth, which keeps multiplexer cells, and one mapped to AND and OR gates
# only. Then the RTL and both netlists with sel = x.
run("""
yosys -q -p "read_verilog -sv x_select.sv; synth -top x_select; rename x_select x_select_mux; write_verilog -noattr x_select_mux.v"
yosys -q -p "read_verilog -sv x_select.sv; synth -top x_select -noabc; abc -g AND,NAND,OR,NOR,XOR,XNOR,ANDNOT,ORNOT; opt_clean; rename x_select x_select_gates; write_verilog -noattr x_select_gates.v"
grep "y_case.3. =" x_select_mux.v
grep -B 2 "y_case.3. =" x_select_gates.v
iverilog -g2012 -Wall -o sim.vvp tb_x_select.sv x_select.sv x_select_mux.v x_select_gates.v
vvp -n sim.vvp
""")

# Yosys 0.69 · Icarus Verilog 13.0 (stable)
$ yosys -q -p "read_verilog -sv x_select.sv; synth -top x_select; rename x_select x_select_mux; write_verilog -noattr x_select_mux.v"
$ yosys -q -p "read_verilog -sv x_select.sv; synth -top x_select -noabc; abc -g AND,NAND,OR,NOR,XOR,XNOR,ANDNOT,ORNOT; opt_clean; rename x_select x_select_gates; write_verilog -noattr x_select_gates.v"
$ grep "y_case.3. =" x_select_mux.v
  assign y_case[3] = sel ? a[3] : b[3];
$ grep -B 2 "y_case.3. =" x_select_gates.v
  assign _06_ = ~(sel & a[3]);
  assign _07_ = sel | ~(b[3]);
  assign y_case[3] = ~(_06_ & _07_);
$ iverilog -g2012 -Wall -o sim.vvp tb_x_select.sv x_select.sv x_select_mux.v x_select_gates.v
$ vvp -n sim.vvp
sel = x, a = 1100, b = 1010; silicon would give 1100 or 1010
RTL                    if 1010  case 1010  ?: 1xx0
netlist, mux cells     if 1xx0  case 1xx0  ?: 1xx0
netlist, AND/OR gates  if xxx0  case xxx0  ?: xxx0

The RTL’s if and case both gave 1010, a clean value. IEEE 1800 runs an if’s else branch when the condition is x, and a case whose selector is x matches no item but the default, so both chose b: that is X-optimismX-optimism: When a simulation turns an unknown value into a known one that the hardware might not produce, for example an if statement that takes its else branch on x. More in “Thinking in hardware: concurrency and 4-state logic”, a confident answer that the hardware gives only half the time. The ?: operator does better: with an unknown condition it gives the bits that a and b share and x for the rest, 1xx0, which is exactly what is known. A test that checks y_if against b passes here, on a design whose select was never set.

Gates can turn known bits into x

The two netlists of x_select.sv compute the same function, and they still disagree. The usual synth keeps multiplexer cells, which write_verilog prints as sel ? a[3] : b[3], and they gave 1xx0, like the RTL’s ?:. Mapped with abc -g to simple gates with no multiplexer among them, the same choice became NAND gates and ORs with an inverted input, and gave xxx0: bit 3, which silicon gives as 1, became x. Step through the gates of bit 3 to see where it is lost:

That is X-pessimismX-pessimism: When a simulation reports x although the hardware would give a known value, for example a gate-level multiplexer whose two inputs are equal. More in “Thinking in hardware: concurrency and 4-state logic”: each gate sees its own inputs, so a pair of signals that are always each other’s inverse in silicon are two independent x values to the simulator. How pessimistic a gate-level run is depends on how the logic was mapped and how its cells are modelled, not on the function the design computes, so a gate-level x is a question to answer, not a verdict. Trace it back to the first signal that became x. When that source is a register without a reset or an input that nothing drives, the unknown is real, and so is every output it reaches through logic that depends on it; the fix goes in the RTL. When an output would be the same for either value of the source, as bit 3 is here, its x is the model’s: force the source to 0 and then to 1, and if the output does not change, it is pessimism.

A missing reset is x in four states and hidden in two

forget_reset.sv is acc8.sv with one line missing: its reset branch sets valid_q and forgets acc_q. The session runs it next to its netlist on Icarus Verilog, which keeps four states, lints it, and then builds the same testbench on Verilator, which, its documentation says, is mostly a two-state simulator:

// The accumulator with one line missing: the reset branch sets valid_q but forgets acc_q.
module forget_reset (
  input  logic       clk_i,
  input  logic       rst_ni,
  input  logic       en_i,
  input  logic [7:0] d_i,
  output logic [7:0] sum_o,
  output logic       valid_o
);
  logic [7:0] acc_q;
  logic       valid_q;
  always_ff @(posedge clk_i or negedge rst_ni) begin
    if (!rst_ni) begin
      valid_q <= 1'b0;
    end else begin
      valid_q <= en_i;
      if (en_i) acc_q <= acc_q + d_i;
    end
  end
  assign sum_o   = acc_q;
  assign valid_o = valid_q;
endmodule

from session import run

# The accumulator that forgets its reset: its RTL and netlist on Icarus Verilog, four-state; its lint; then on
# Verilator, two-state, with the default start values and with random ones from three seeds, the last one twice.
run("""
yosys -q -p "read_verilog -sv forget_reset.sv; synth -top forget_reset; rename forget_reset forget_reset_gates; write_verilog -noattr forget_reset_gates.v"
iverilog -g2012 -Wall -DFORGET -o sim.vvp tb_gate_level.sv forget_reset.sv forget_reset_gates.v
vvp -n sim.vvp
verilator --lint-only -Wall --quiet forget_reset.sv
verilator --binary -j 0 --quiet -DFORGET --top-module tb_gate_level tb_gate_level.sv forget_reset.sv forget_reset_gates.v
obj_dir/Vtb_gate_level +verilator+quiet
obj_dir/Vtb_gate_level +verilator+quiet +verilator+rand+reset+2 +verilator+seed+1
obj_dir/Vtb_gate_level +verilator+quiet +verilator+rand+reset+2 +verilator+seed+2
obj_dir/Vtb_gate_level +verilator+quiet +verilator+rand+reset+2 +verilator+seed+3
obj_dir/Vtb_gate_level +verilator+quiet +verilator+rand+reset+2 +verilator+seed+3
""")

# Yosys 0.69 · Icarus Verilog 13.0 (stable) · Verilator 5.052
$ yosys -q -p "read_verilog -sv forget_reset.sv; synth -top forget_reset; rename forget_reset forget_reset_gates; write_verilog -noattr forget_reset_gates.v"
$ iverilog -g2012 -Wall -DFORGET -o sim.vvp tb_gate_level.sv forget_reset.sv forget_reset_gates.v
$ vvp -n sim.vvp
cycle 1: en=1 d=184 | RTL sum   x | gates sum   x
cycle 2: en=1 d= 92 | RTL sum   x | gates sum   x
cycle 3: en=0 d= 46 | RTL sum   x | gates sum   x
200 cycles: 0 with a difference, 200 with an unknown sum
tb_gate_level.sv:33: $finish called at 2016 (1s)
$ verilator --lint-only -Wall --quiet forget_reset.sv
$ verilator --binary -j 0 --quiet -DFORGET --top-module tb_gate_level tb_gate_level.sv forget_reset.sv forget_reset_gates.v
$ obj_dir/Vtb_gate_level +verilator+quiet
cycle 1: en=1 d=184 | RTL sum 184 | gates sum 184
cycle 2: en=1 d= 92 | RTL sum  20 | gates sum  20
cycle 3: en=0 d= 46 | RTL sum  20 | gates sum  20
200 cycles: 0 with a difference, 0 with an unknown sum
- tb_gate_level.sv:33: Verilog $finish
$ obj_dir/Vtb_gate_level +verilator+quiet +verilator+rand+reset+2 +verilator+seed+1
cycle 1: en=1 d=184 | RTL sum 190 | gates sum 245
cycle 2: en=1 d= 92 | RTL sum  26 | gates sum  81
cycle 3: en=0 d= 46 | RTL sum  26 | gates sum  81
200 cycles: 200 with a difference, 0 with an unknown sum
- tb_gate_level.sv:33: Verilog $finish
$ obj_dir/Vtb_gate_level +verilator+quiet +verilator+rand+reset+2 +verilator+seed+2
cycle 1: en=1 d=184 | RTL sum 242 | gates sum  55
cycle 2: en=1 d= 92 | RTL sum  78 | gates sum 147
cycle 3: en=0 d= 46 | RTL sum  78 | gates sum 147
200 cycles: 200 with a difference, 0 with an unknown sum
- tb_gate_level.sv:33: Verilog $finish
$ obj_dir/Vtb_gate_level +verilator+quiet +verilator+rand+reset+2 +verilator+seed+3
cycle 1: en=1 d=184 | RTL sum  27 | gates sum  17
cycle 2: en=1 d= 92 | RTL sum 119 | gates sum 109
cycle 3: en=0 d= 46 | RTL sum 119 | gates sum 109
200 cycles: 200 with a difference, 0 with an unknown sum
- tb_gate_level.sv:33: Verilog $finish
$ obj_dir/Vtb_gate_level +verilator+quiet +verilator+rand+reset+2 +verilator+seed+3
cycle 1: en=1 d=184 | RTL sum  27 | gates sum  17
cycle 2: en=1 d= 92 | RTL sum 119 | gates sum 109
cycle 3: en=0 d= 46 | RTL sum 119 | gates sum 109
200 cycles: 200 with a difference, 0 with an unknown sum
- tb_gate_level.sv:33: Verilog $finish

Icarus Verilog showed the sum as x in all 200 cycles, in the RTL and in the netlist alike, which is the bug made visible: acc_q starts unknown, and unknown plus anything stays unknown. Lint said nothing, since a register without a reset is legal. Verilator’s first run is the dangerous one. Its sums, 184, 20, 20, are exactly those of the correct acc8.sv, and it reported 0 differences and 0 unknown sums. With its default settings Verilator starts every variable with a value from a function, its default --x-initial unique, and the run-time option that picks those values, +verilator+rand+reset, defaults to 0, all zeros. Zero happens to be the reset value acc_q forgot, so the missing line was invisible.

Random start values with a seed expose reset dependence

The rest of the session runs the same Verilator build with +verilator+rand+reset+2, which makes every start value random, and +verilator+seed+1, 2 and 3. Seed 1 gave sums of 190, 26 and 26 in the first three cycles, seed 2 gave 242, 78, 78 and seed 3 gave 27, 119, 119; the RTL and the netlist, whose flip-flops each drew their own start value, disagreed on all 200 cycles of every seeded run. Seed 3, run twice, printed the same numbers both times. A result that changes with the seed depends on start values that nothing set, which is exactly what a missing reset is, and the seed makes each failing run repeatable.

Verilator’s documentation suggests running with all zeros, then all ones, then random values: when the results agree, the reset works. A regression that does so, prints its seed, and adds an assertion that $isunknown(sum_o) is false once reset is over, for the four-state runs, catches this bug in its first run. The fix is one line in the reset branch, acc_q <= '0;, which turns forget_reset.sv back into acc8.sv, whose RTL and netlist agreed on every cycle.

Practise: follow an unknown value through a netlist

The exercise is the heart of a gate-level simulator for one moment in time: values of 0, 1 and x pushed through NOT, AND, OR, NAND, NOR, XOR and multiplexer gates, judged one gate at a time. Its sample tests build both netlists of bit 3 of x_select.sv, so you can watch the AND and OR version give x where the multiplexer gives 1.

def simulate(gates, inputs):
    """The value, "0", "1" or "x", of every input and gate output, evaluated gate by gate in the order given."""
    values = dict(inputs)
    return values

from xsim import simulate

# Bit 3 of x_select.sv: the netlist built from AND and OR gates, as Yosys wrote it with abc -g, and the mux cell.
GATES = [
    ("nb", "not", "b"),
    ("n06", "nand", "sel", "a"),
    ("n07", "or", "sel", "nb"),
    ("y", "nand", "n06", "n07"),
]
MUX = [("y", "mux", "sel", "a", "b")]


def test_pessimism_bit3():
    """gives x for the AND/OR netlist and 1 for the mux cell, when sel is x and a and b are both 1"""
    assert simulate(GATES, {"sel": "x", "a": "1", "b": "1"})["y"] == "x"
    assert simulate(MUX, {"sel": "x", "a": "1", "b": "1"})["y"] == "1"


def test_known_select():
    """chooses a or b in both netlists when sel is known"""
    for sel, a, b, want in (("1", "1", "0", "1"), ("0", "1", "0", "0"), ("1", "0", "1", "0"), ("0", "0", "1", "1")):
        assert simulate(GATES, {"sel": sel, "a": a, "b": b})["y"] == want
        assert simulate(MUX, {"sel": sel, "a": a, "b": b})["y"] == want


def test_controlling_values():
    """lets a 0 decide an AND and a 1 decide an OR, even next to an x"""
    gates = [("p", "and", "u", "z"), ("q", "or", "u", "o"), ("r", "nand", "u", "z"), ("s", "nor", "u", "o")]
    v = simulate(gates, {"u": "x", "z": "0", "o": "1"})
    assert (v["p"], v["q"], v["r"], v["s"]) == ("0", "1", "1", "0")


def test_x_spreads():
    """turns x into x through NOT and XOR, and through AND or OR without a controlling value"""
    gates = [("n", "not", "u"), ("e", "xor", "u", "o"), ("f", "and", "u", "o"), ("g", "or", "u", "z")]
    v = simulate(gates, {"u": "x", "z": "0", "o": "1"})
    assert (v["n"], v["e"], v["f"], v["g"]) == ("x", "x", "x", "x")


def test_mux_unequal_and_inputs_kept():
    """gives x from a mux whose data differ, and keeps the inputs in the result"""
    v = simulate(MUX, {"sel": "x", "a": "1", "b": "0"})
    assert v == {"sel": "x", "a": "1", "b": "0", "y": "x"}

Last comes a self-check on netlist runs, optimism, pessimism, missing resets and seeds. It adapts as you answer: it begins where you are weakest, steps up after each right answer, and returns to anything you miss:

Interview questions

Warm-up (fresher): what can a gate-level simulation find that an RTL simulation cannot?

It finds where the circuit that was built differs from the one that was simulated. Synthesis drops what only a simulator uses, such as an incomplete sensitivity list or a delay, obeys comments such as full_case that most simulators ignore, and picks its own value for an x default, so the netlist can compute something the RTL never showed; running the netlist on the same testbench and comparing the outputs shows each such mismatch. It also shows unknown values the RTL hid: an if or a case turns an x into a known branch, while the gates pass it on, so a register without a reset can stay invisible in RTL and show as x at the outputs of the netlist. With delays from a timing tool it can check timing paths too, but its everyday use is checking that what was written and what was built agree.

Two harder questions follow, a regression that passed on a two-state simulator and a gate-level plan for a whole chip. Note where you would begin, then see how the first step of each begins:

Key takeaways

• A generic netlist runs on the RTL’s own testbench: the accumulator’s RTL and netlist agreed on all 200 cycles of inputs from an LFSR, which every simulator reproduces.
• If and case turned sel = x into the else branch and the default, 1010, where silicon gives 1100 or 1010; ?: gave 1xx0, exactly the known bits.
• Gates built from AND and OR gave xxx0 where the multiplexer cells gave 1xx0, because each gate sees its own inputs; trace a gate-level x to its source before calling it pessimism.
• The accumulator without its reset was x for 200 cycles on Icarus Verilog and silently right on Verilator’s default zero start values.
• +verilator+rand+reset+2 with seeds 1, 2 and 3 gave three different sums and 200 differences each, and the same seed repeated the same run: start values that change the answer mean a missing reset.