Loops and Jumps That Synthesize

Read a loop as copies of hardware, and choose loop forms and jumps that every tool in the flow accepts.

You Will Be Able To

  • Explain what a synthesizer builds from a for loop.
  • Predict which iteration wins when several copies write the same variable.
  • Choose a loop form that the simulators and the synthesis flow all accept.
  • Fix a loop whose number of iterations depends on a signal.
Lesson
R11.2
Time
30 min
Runs on
Verilator
Check
5 questions

A lookup block compares a key with four table entries. The brief says the lowest matching entry wins. The table held the same key twice, and the block returned the higher entry.

Two Entries Match, and the Loop Reports the Last OneThe six lookups of the lab bench. Entries 1 and 3 both hold 5a. idx (shipped) is the loop with no break; idx (with break) leaves the loop at the first match.
012345key113c5a775a11valid111111011110hitidx (shipped)023030idx (with break)021030wrong entry
Scroll horizontally ↔
  1. Cycle 0

    Key 11 is in entry 0 only. Both versions report entry 0.

  2. Cycle 2

    Key 5a is in entries 1 and 3. The shipped loop reports 3. The brief asks for 1.

  3. Cycle 4

    Entry 1 is not valid now, so entry 3 is the only match. Both versions agree again.

The loop did what it says. To see why, read it as hardware.

A Loop Is Copies of Hardware

A synthesizer unrolls a loop. It writes the body once for each iteration, with the loop variable replaced by a constant. Nothing in the result counts or repeats.

The Lookup Loop, UnrolledArrows carry data. Each box in the middle column is one copy of the loop body.
  • I/O
  • Datapath
  • Control / FSM
  • Data
  • Control
The lookup loop, unrolledArrows carry data. Each box in the middle column is one copy of the loop body. io key the word to find datapath Copy i = 0 entry 0 == key datapath Copy i = 1 entry 1 == key datapath Copy i = 2 entry 2 == key datapath Copy i = 3 entry 3 == key control Which writecounts a chain of muxes io hit, idx the outputs match 0match 1match 2match 3
  1. io keythe word to find
    • Copy i = 0
    • Copy i = 1
    • Copy i = 2
    • Copy i = 3
  2. datapath Copy i = 0entry 0 == key
    • match 0 → Which write counts
  3. datapath Copy i = 1entry 1 == key
    • match 1 → Which write counts
  4. datapath Copy i = 2entry 2 == key
    • match 2 → Which write counts
  5. datapath Copy i = 3entry 3 == key
    • match 3 → Which write counts
  6. control Which write countsa chain of muxes
    • hit, idx
  7. io hit, idxthe outputs
  1. Four copies

    The body appears four times. All four comparators see key at once.

  2. No break

    Each copy may write idx, in the order 0, 1, 2, 3. A later write replaces an earlier one, so copy 3 has the last word.

  3. With break

    A match in copy 0 switches off every later copy. Copy 0 now has the first word, and the chain has one more level.

Read the diagram as text
  • key: the word to find
  • Copy i = 0: entry 0 == key
  • Copy i = 1: entry 1 == key
  • Copy i = 2: entry 2 == key
  • Copy i = 3: entry 3 == key
  • Which write counts: a chain of muxes
  • hit, idx: the outputs
  • key → Copy i = 0
  • key → Copy i = 1
  • key → Copy i = 2
  • key → Copy i = 3
  • Copy i = 0 → Which write counts: match 0
  • Copy i = 1 → Which write counts: match 1
  • Copy i = 2 → Which write counts: match 2
  • Copy i = 3 → Which write counts: match 3
  • Which write counts → hit, idx

On this flow the shipped loop is 113 cells and 8 levels. With break it is 109 cells and 9 levels.

The loop variable i is not a signal. It exists only while the tool unrolls. That is why its start, end and step must be constants.

Loop bodyIterationsCellsLevels
n = n + 4'(d[i]); (count the 1 bits of a byte)82610
if (i < len) sum = sum + d; (add an 8-bit d into an 8-bit sum up to 15 times)1661354

Measured on this flow. Each iteration that reads the result of the one before adds to the depth.

Leaving a Loop: break and continue

break leaves the loop. continue skips the rest of this iteration. In hardware neither one stops anything: all copies exist. The jump becomes a condition on the copies that come after it.

break: the first match wins

    for (int i = 0; i < 4; i++)
      if (valid[i] && tab[8*i +: 8] == key) begin
        hit = 1'b1;
        idx = 2'(i);
        break;                     // leave the loop at the first match
      end

Key 5a gives idx=1. On this flow: 109 cells, 9 levels. A copy counts only if no lower copy matched.

Count down: the same priority with no jump

    for (int i = 3; i >= 0; i--)   // count down: entry 0 is written last
      if (valid[i] && tab[8*i +: 8] == key) begin
        hit = 1'b1;
        idx = 2'(i);
      end

Key 5a gives idx=1. On this flow: 107 cells, 9 levels.

A continue works the same way. if (!valid[i]) continue; at the top of the body built the same 109 cells as the version with valid[i] && in the test.

Which Loop Forms the Tools Accept

The standard has six ways to write this loop. The three tools on this site do not agree on them.

Form of the lookupIcarus 12Verilator 5.052Synthesize (cells, levels)
for, counted downrunsruns107, 9
for with breakrefused: break statements not supportedruns109, 9
for with continue and breakrefused: syntax errorruns109, 9
foreach (valid[i])runs, with the index going 0 to 3runs, with the index going 3 to 0107, 9
while (i < 4) with a found flagrunsruns95, 9
repeat (4)runsrunsrefused: unsupported language feature
do ... while (i < 4)runsrunsrefused: unsupported language feature
for with disable of a named blockrunsrunsrefused: unsupported language feature

Two forms pass all three tools with the same answer. One is a for loop with a constant bound and no jump. The other is a while loop with a constant bound. Many synthesizers accept repeat with a constant count; this flow does not.

disable is the older way to leave a loop: it ends a block by its name. New RTL uses break.

A Bound the Tool Can Count

To unroll a loop, the tool must know how many copies to build. A loop that runs "until the data is zero" has no such number.

The data decides when to stop

always_comb begin
  logic [7:0] x;
  x = d;
  n = 4'd0;
  while (x != 8'd0) begin
    x = x >> 1;
    n = n + 4'd1;
  end
end

Simulation runs: d=28 gives n=6. Synthesize stops with unroll limit of 4000 exhausted.

Eight copies, each with a test

always_comb begin
  logic [7:0] x;
  x = d;
  n = 4'd0;
  for (int i = 0; i < 8; i++)
    if (x != 8'd0) begin
      x = x >> 1;
      n = n + 4'd1;
    end
end

The same results in simulation. On this flow: 17 cells, 8 levels.

A byte needs at most 8 shifts, so 8 is the constant bound. The test moves inside the body.

Loop headerOn this flowWhat to write
for (int i = 0; i < 8; i++)unrolled 8 timesthis
for (int i = 0; i < N; i++) with a parameter Nunrolled N times for each instancethis
for (int i = 0; i < len; i++) with a 4-bit input lenaccepted: 414 cells, 27 levelsa constant bound and if (i < len)
while (x != 0)refused: unroll limita constant bound and the test inside

This flow unrolled the third row as far as a 4-bit len can reach. Other synthesizers refuse a bound that is a signal.

Named Blocks and the Empty Statement

A begin-end pair groups statements. A name after begin makes it a scope. It can hold its own variables, and tools show the name in the design tree.

On this flow: 26 cells and 10 levels, the same as the loop with no names. A name costs nothing.
always_comb begin : count
  logic [3:0] acc;                 // exists only inside count
  acc = 4'd0;
  for (int i = 0; i < 8; i++) begin : each_bit
    acc = acc + 4'(d[i]);
  end
  n = acc;
end

A semicolon alone is also a statement. It does nothing. After an if header it becomes the whole body of the if.

A stray semicolon

always_comb begin
  y = 4'd0;
  if (a);
    y = d;
end

With d = 9 the bench prints a=0 y=9 and a=1 y=9. Synthesize builds 0 cells: y is wired to d. It warns if statement has empty body. Lint prints nothing.

What was meant

always_comb begin
  y = 4'd0;
  if (a)
    y = d;
end

y is d when a is 1 and 0 when it is not: four AND gates.

The Lab: Make the Lowest Entry Win

Design brief
PortDirectionWidthMeaning
keyinput[7:0]the word to find
tabinput[31:0]four entries; entry i is tab[8*i +: 8]
validinput[3:0]valid[i] is 1 when entry i holds a key
hitoutput11 when a valid entry equals key
idxoutput[1:0]the lowest valid entry that equals key; 0 when there is none
Latency
combinational
Corner cases
the same key in two entries; a match in an entry that is not valid. Done when: Run shows idx=1 for key 5a with all entries valid
  1. Run as shipped

    The third line reads key=5a | hit=1 idx=3. Entries 1 and 3 both match, and copy 3 writes last.

  2. Add the break

    Put break; after idx = 2'(i); and Run. The third line reads idx=1. The other five lines do not change.

  3. Read the gates

    Synthesize: 109 cells and 9 levels, against 113 and 8 as shipped. The priority costs one level of logic.

  4. Try the loop with no jump

    Remove the break and count down from 3 to 0. Run prints the same lines, and Synthesize reports 107 cells and 9 levels.

The two fixes
With break: 109 cells, 9 levels.
    for (int i = 0; i < 4; i++)
      if (valid[i] && tab[8*i +: 8] == key) begin
        hit = 1'b1;
        idx = 2'(i);
        break;                     // leave the loop at the first match
      end
Counted down: 107 cells, 9 levels. This form also runs on Icarus 12.
    for (int i = 3; i >= 0; i--)   // count down: entry 0 is written last
      if (valid[i] && tab[8*i +: 8] == key) begin
        hit = 1'b1;
        idx = 2'(i);
      end
Asked in interviews
  1. What does a synthesizer build from a for loop?

    One copy of the loop body per iteration, all present at once. The loop variable becomes a constant in each copy, so the bounds must be constants.

  2. Can you synthesize while (x != 0)?

    Not as written, because the number of iterations depends on data. Use a loop with a constant bound, sized for the worst case, and test the data inside the body.

  3. How does break become hardware?

    Every copy still exists. Each copy after the break gets an extra condition: no earlier copy took the jump. The result is a priority chain.

Try It

The bench holds the table at 5a 3c 5a 11, entries 3 down to 0. It changes key and valid and prints 1 ns later.

The third line is the bug. Entries 1 and 3 both hold 5a. The loop counts up with no break, so the copy for entry 3 writes idx last.

Synthesize reports 113 cells, 0 flops, 0 latches and 8 levels of logic. Lint prints nothing.

RTLVerilator · simulator service · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: valid=1111 key=11 | hit=1 idx=0 valid=1111 key=3c | hit=1 idx=2 valid=1111 key=5a | hit=1 idx=3 valid=1111 key=77 | hit=0 idx=0 valid=1101 key=5a | hit=1 idx=3 valid=1110 key=11 | hit=0 idx=0

Original design · 113 cells · 0 flip-flops · 0 latches · 8 logic levels. Synthesis uses Yosys; counts depend on the toolchain.

Read included file: tb.sv
module tb;
  logic [7:0]  key = 0;
  logic [31:0] tab = 32'h5a_3c_5a_11;   // entry 3 = 5a, entry 2 = 3c, entry 1 = 5a, entry 0 = 11
  logic [3:0]  valid = 4'b1111;
  logic        hit;
  logic [1:0]  idx;
  key_match dut (.*);
  task automatic look(input logic [7:0] k, input logic [3:0] v);
    key = k; valid = v;
    #1 $display("valid=%b key=%h | hit=%b idx=%0d", valid, key, hit, idx);
  endtask
  initial begin
    look(8'h11, 4'b1111);
    look(8'h3c, 4'b1111);
    look(8'h5a, 4'b1111);       // entries 1 and 3 both hold 5a
    look(8'h77, 4'b1111);
    look(8'h5a, 4'b1101);       // entry 1 is not valid
    look(8'h11, 4'b1110);       // entry 0 is not valid
    $finish(0);
  end
endmodule

Check Yourself

Predict the outputThe loop leaves at the first 1 bit, before the count. d is 8'b0010_1000. What does the bench print?
module tb;
  logic [7:0] d = 8'b0010_1000;
  logic [3:0] n;
  always_comb begin
    n = 4'd0;
    for (int i = 0; i < 8; i++) begin
      if (d[i]) break;
      n = n + 4'd1;
    end
  end
  initial begin
    #1 $display("n=%0d", n);
    $finish(0);
  end
endmodule
Spot the bugEach option is a loop that must set pos to the position of the lowest 1 in d. The bench checks four bytes. Which option fails?
ConceptA block sums eight 16-bit words with for (int i = 0; i < 8; i++) sum = sum + w[i];. What does the synthesizer build?
ConceptWhich loop does the synthesis flow on this site refuse, although both simulators run it?
ConceptSynthesize stops on while (x != 8'd0) with unroll limit of 4000 exhausted. What is the right fix?

Common Mistakes

Wrong Add a break and expect less logic, because the loop "stops early".

Every copy of the body is still built, and each copy after the break gets one more condition.

Fix Judge by Synthesize: the lab went from 113 cells and 8 levels to 109 cells and 9 levels.

Wrong Write foreach and assume the index counts up from 0.

The index runs from the left bound to the right, so [3:0] gives 3, 2, 1, 0. Icarus 12 counts the other way.

Fix When the order decides the result, write a for loop that states its direction.

Wrong End the header of an if or a for with a semicolon.

The semicolon is a complete statement that does nothing, so the next line no longer belongs to the header.

Fix Put the statement, or begin, right after the closing parenthesis.

Before
if (sel);
  y = d;        // always runs
After
if (sel)
  y = d;        // runs when sel is 1

Remember

  • A loop in RTL is one copy of its body per iteration, all present at once. It never takes clock cycles.
  • When several copies write one variable, the last write wins. break, or counting down, turns that into priority.
  • Give every loop a constant bound and test the data inside the body.
  • A for loop with a constant bound passes every tool here. repeat, do-while and disable stop this site's synthesis flow.
  • A semicolon after an if or for header is an empty body. The next line then always runs.

Practice

Report a problem with this page