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
forloop. - 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.
5a. idx (shipped) is the loop with no break; idx (with break) leaves the loop at the first match.- Cycle 0
Key
11is in entry 0 only. Both versions report entry 0. - Cycle 2
Key
5ais in entries 1 and 3. The shipped loop reports 3. The brief asks for 1. - 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.
- I/O
- Datapath
- Control / FSM
- Data
- Control
- Four copies
The body appears four times. All four comparators see
keyat once. - 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. - 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 body | Iterations | Cells | Levels |
|---|---|---|---|
n = n + 4'(d[i]); (count the 1 bits of a byte) | 8 | 26 | 10 |
if (i < len) sum = sum + d; (add an 8-bit d into an 8-bit sum up to 15 times) | 16 | 613 | 54 |
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 lookup | Icarus 12 | Verilator 5.052 | Synthesize (cells, levels) |
|---|---|---|---|
for, counted down | runs | runs | 107, 9 |
for with break | refused: break statements not supported | runs | 109, 9 |
for with continue and break | refused: syntax error | runs | 109, 9 |
foreach (valid[i]) | runs, with the index going 0 to 3 | runs, with the index going 3 to 0 | 107, 9 |
while (i < 4) with a found flag | runs | runs | 95, 9 |
repeat (4) | runs | runs | refused: unsupported language feature |
do ... while (i < 4) | runs | runs | refused: unsupported language feature |
for with disable of a named block | runs | runs | refused: 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 header | On this flow | What to write |
|---|---|---|
for (int i = 0; i < 8; i++) | unrolled 8 times | this |
for (int i = 0; i < N; i++) with a parameter N | unrolled N times for each instance | this |
for (int i = 0; i < len; i++) with a 4-bit input len | accepted: 414 cells, 27 levels | a constant bound and if (i < len) |
while (x != 0) | refused: unroll limit | a 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.
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;
endA 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
| Port | Direction | Width | Meaning |
|---|---|---|---|
| key | input | [7:0] | the word to find |
| tab | input | [31:0] | four entries; entry i is tab[8*i +: 8] |
| valid | input | [3:0] | valid[i] is 1 when entry i holds a key |
| hit | output | 1 | 1 when a valid entry equals key |
| idx | output | [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=1for key5awith all entries valid
Run as shipped
The third line reads
key=5a | hit=1 idx=3. Entries 1 and 3 both match, and copy 3 writes last.Add the break
Put
break;afteridx = 2'(i);and Run. The third line readsidx=1. The other five lines do not change.Read the gates
Synthesize: 109 cells and 9 levels, against 113 and 8 as shipped. The priority costs one level of logic.
Try the loop with no jump
Remove the
breakand count down from 3 to 0. Run prints the same lines, and Synthesize reports 107 cells and 9 levels.
The two fixes
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 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);
endAsked in interviews
What does a synthesizer build from a
forloop?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.
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.
How does
breakbecome hardware?Every copy still exists. Each copy after the
breakgets 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.
Synthesize the design to measure its cells and inspect the mapped gates.
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=0Original 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
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.
if (sel);
y = d; // always runsif (sel)
y = d; // runs when sel is 1Remember
- 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
forloop with a constant bound passes every tool here.repeat,do-whileanddisablestop this site's synthesis flow. - A semicolon after an
iforforheader is an empty body. The next line then always runs.