Timing analysis cannot cope with combinatorial loops

[SolraBizna]

git clone https://github.com/SolraBizna/friedice
cd friedice
make bin/friedup.asc

Somewhere in that spaghetti bowl of unpipelined logic is yet another edge case that ends up triggering this assert:

terminate called after throwing an instance of 'nextpnr_ice40::assertion_failure'
  what():  Assertion failure: port_fanin.empty() (/home/sbizna/nextpnr/common/timing.cc:170)

This code is difficult to gradually reduce to a minimal test case, because it's all so horribly entangled. All I can say for sure is that the problem lies in src/friedice.v or src/register_file.v.

[daveshah1]

The issue here seems to be combinational loops in the design as a result of inferred latches. The topological ordering used in nextpnr's timing analysis isn't capable of handling these in a nice way.

An example of one is result not being assigned a value for all input possibilities in this always block: https://github.com/SolraBizna/friedice/blob/master/src/friedice.v#L361

In general, this should be avoided as it is likely to cause hard-to-analyse timing issues. Nonetheless nextpnr should deal with it better.

If you are willing to accept potentially inaccurate timing results, then it is safe to comment out the assertion (it is merely an attempt to check the topological ordering is working correctly, which naturally fails in the case of loops).

[SolraBizna]

The issue here seems to be combinational loops in the design as a result of inferred latches. The topological ordering used in nextpnr's timing analysis isn't capable of handling these in a nice way.

Ah! That makes perfect sense.

An example of one is result not being assigned a value for all input possibilities in this always block: https://github.com/SolraBizna/friedice/blob/master/src/friedice.v#L361

That block actually wasn't intended to have any inferred latches, though obviously some got through.

Adding a few more assignments-of-X at the top of that block leads to a successful run and working hardware. In the end, nextpnr runs much much faster than arachne-pnr (which takes up to 400 seconds o_o) and gives me valuable diagnostic information. Unfortunately, this solution seems to trigger a bug in iverilog when I re-test the core in simulation...

Is there a good way to lint for unwanted inferred latches? And is there a better way than "assign X at the top" or "assign X on every 'inactive' branch" to prevent inferring a latch, while still allowing me to define complicated combinatorial logic in an always block?

[eddiehung]

What @daveshah1 says is correct. Currently nextpnr does not handle combinational loops at all.
I shall make the assertion sensitive to the --force option so that you can still continue at your own risk.

Broadly speaking, your upstream synthesis tool should detect latches and warn you of them. By the time it gets to nextpnr, we could have no idea that a latch has been inferred (as typically it just looks like combinatorial logic with feedback) until we try to do timing analysis.

[SolraBizna]

My giant combinatorial always (*) block actually should be loop-free. (And, now that I've stopped the unwanted latches from inferring, seems to be.)

[eddiehung]

After #110:
Without --force:
ERROR: timing analysis failed due to presence of combinational loops, incomplete specification of timing ports, etc.
With --force this now demotes to a warning and continues.
I know this doesn't fix the root of this particular issue (which is why I've changed the title) but at least it fixes an itch I've been meaning to scratch!

[SolraBizna]

Excellent. As far as I'm concerned, that resolves this issue.

(I don't know whether it's possible to do a good timing analysis in the presence of a combinatorial loop, in the general case... and I do think it's a good idea to eliminate them from designs anyway...)

[eddiehung]

Thanks @SolraBizna.

Let me leave a note behind for future devs:
This error fires when either (a) there is a combinatorial loop (i.e. user error), or (b) nextpnr does not have complete timing information on each port in the design, and thus will miss some timing paths (thus, nextpnr error). This check is to catch that. In the future, we should differentiate between the two.

[hightowera]

I am experiencing this error and I'm a bit stumped as to why. It's probably my ignorance in Verilog. But my main issue is the lack of trace-ability to the offending net or code. In my overall design, multiple instances of the error pop out after a gazlion lines of timing reduction net info messages. I'm using the latest stable nextpnr.

My specific example has to do with the following module - the transmit side of a simple UART. If I comment out "thr <= data" and "pad_d0 <= tsr[0]", the error goes away. This is a registered block with all assignments registered to a global clock with inferred constraint timing coming from an iCE40up5k's PLL output.

`module ice_uart_tx #(
parameter DIVISOR = 65535)
(
input clk,
input rst,

input  [7:0] data,
input        strobe,
output       pad,
output       ready
);

reg        pad_d0;    // Current presentation bit
reg        strobe_d0; // Delayed strobe - rising edge detect
reg  [7:0] tsr;       // Transmit Shift Register
reg  [7:0] thr;       // Transmit Holding Register
reg        start;     // Start transmittion trigger
reg  [2:0] bitcnt;    // Number of bits shifted out so far
reg  [1:0] state;     // Current FSM state
reg [15:0] counter;   // Bit hold counter - from divisor


always @(posedge clk)
begin
	if (rst)
	begin
		bitcnt    <= 0;
		tsr       <= 0;
		thr       <= 0;
		pad_d0    <= 1'b1;
		state     <= `uart_IDLE;
		counter   <= 16'h0000;
		start     <= 0;
		strobe_d0 <= 0;
	end
	else
	begin

		strobe_d0 <= strobe;

		if (strobe & ~strobe_d0) // rising edge
		begin
			start <= 1'b1;
			thr   <= data;
		end

		case (state)
		`uart_IDLE:
		begin
			pad_d0 <= 1'b1;

			if (start)
			begin
				state   <= `uart_START;
				counter <= DIVISOR - 1;
				tsr     <= thr;
				start   <= 1'b0;
				bitcnt  <= 0;
			end
		end

		`uart_START:
		begin
			pad_d0 <= 1'b0;

			if (counter)
				counter <= counter - 1;
			else
			begin
				counter <= DIVISOR - 1;
				state   <= `uart_SHIFT;
			end
		end

		`uart_SHIFT:
		begin
			pad_d0 <= tsr[0];

			if (counter)
				counter <= counter - 1;
			else
			begin
				counter <= DIVISOR - 1;
				tsr     <= { 1'b0, tsr[7:1] };
				bitcnt  <= bitcnt + 1;

				if (bitcnt == 7)
					state <= `uart_STOP;
			end
		end

		`uart_STOP:
		begin
			pad_d0 <= 1'b1;

			if (counter)
				counter <= counter - 1;
			else
				state   <= `uart_IDLE;
		end
		endcase
	end
end

assign ready = ~start;  // Stretches next write if not done w/ prev
assign pad   = pad_d0;

endmodule

`

[ZipCPU]

@hightowera ,
I'm not convinced this is the same issue.

Can you please open a new issue, and provide a complete and verifiable example? (Preferrably a minimal one as well ... but I can take a look either way.) Right now, I'm not seeing any issues with the little bit of code you've posted, and it's not sufficient to duplicate the issue.

Dan