Daisy chain leads to Combinatorial Loop warning and no bitstream

[sy2002]

Maybe you have a look at issue #47 first, before diving back to work here ;-)

Info about the QNICE interrupt system is in the updated qnice_intro-pdf in branch dev-int, pages 9, 12 and the scheme and timing on pages 23-25.

The QNICE interrupt system is built as a Daisy chain. The more "left" (CPU being the leftmost device) you sit, the more priority you enjoy. This is why it felt very natural for me, to implement the two timers that are specified in sysdef.asm as two Daisy chained timers, as you can see in branch dev-int in the file timer_module.vhd:

   timer0 : timer
   generic map
   (
      CLK_FREQ => CLK_FREQ,
      IS_SIMULATION => IS_SIMULATION
   )
   port map
   (
      clk => clk,
      reset => reset,

      int_n_out => int_n_out,          -- connect with "left" device (e.g. CPU)
      grant_n_in => grant_n_in,        -- ditto
      int_n_in => '1', --t1_int_n_out,        -- build Daisy Chain between timer0 and timer 1
      grant_n_out => open, --t1_grant_n_in,    -- ditto

      en => t0_en,
      we => t0_we,
      reg => t0_reg,
      data => data
   );

As you can also see, I did comment out the Daisy chain signals of the second timer and instead, terminated the Daisy chain by applying a 1 to int_n_in which translates to "there will never be any interrupt coming from "the right side" of the chain.

I did that, because otherwise, currently there is no bitstream written in branch dev-int: Vivado complains about somethinig that I never heard before and I must admit the googling the term and looking at the forums did not really enlighten me, yet.

Do you have any insights in this phenomenon? What it is? Why it occurs here (did I make some bad mistake and I am just missing the obvious)? How to solve it?

So this is the reason, why right now, there is no Daisy chain and just timer0 while timer1 stays disabled.

If this does not ring a bell on your side - don't worry, then just assign this one back to me and I will continue to investigate.

[MJoergen]

A combinatorial loop is when you have two (or more) signals where A depends combinatorially on B, and B depends combinatorially on A. This potentially leads to a race condition.

Consider this example: B <= A and A <= not B. This will generate a single inverter whose input is connected to the output, and it will oscillate unpredictably.

---

I managed to generate a bitstream without problems using Vivado (on the latest dev-int branch, where both timers are implemented). So why does it fail on your machine ? Hmmmm.

I looked at the code, and I did not find anything glaringly obvious. However, In the code in timer.vhd there might just be such a loop:

timer0.grant_n_out depends combinatorially on timer0.int_n_in = timer1.int_n_out timer1.int_n_out depends combinatorially on timer1.grant_n_in = timer0.grant_n_out

Now, the nature of the grant signal in the timer module is that it is only ever asserted high (never asserted low), and therefore Vivado might be able to optimize away the combinatorial loop.

---

Still, we are left with the issue that it doesn't work on your machine.

Vivado caches results from previous runs and sometimes that has caused problems for me. I regularly do git clean -d -f and git reset --hard HEAD to do cleanup, but this does permanently delete any changes not committed yet, so be careful. I speak from painful experience!

Could you perhaps try again with a completely new clone of the repository ?

[sy2002]

Thank you for your thorough feedback. I think there is a misunderstanding on either your or my side.

Also on my machine, the branch dev-int is synthesizing without error.

But as soon as you comment-in in timer_module.vhd the Daisy chain by changing this

int_n_in => '1', --t1_int_n_out,        -- build Daisy Chain between timer0 and timer 1
grant_n_out => open, --t1_grant_n_in,    -- ditto

to this

int_n_in => t1_int_n_out,        -- build Daisy Chain between timer0 and timer 1
grant_n_out => t1_grant_n_in,    -- ditto

Then it fails on my machine.

Does this work on your machine?

[MJoergen]

Yes it builds successfully on my machine with both timers daisy chained.

[MJoergen]

Hmm, let me recheck in a coupke of hours.

[sy2002]

OK. Thanks. Just for being on the safe side, I did what you suggested: I checked out a fresh repo to a new folder, switched to branch dev-int, made the toolchain using tools/make-toolchain.sh(includes the ROMs) and commented-in the above mentioned Daisy chain in timer_module.vhd (not in timer.vhd) bluebetween timer0 and timer1 . So all fresh :-)

It synthesizes OK, while throwing this "critical warnings":

Warning during Synthesis

[Synth 8-295] found timing loop. ["/media/psf/Home/Downloads/QNICE-FPGA/vhdl/hw/nexys4ddr/env1.vhd":22]

Warning during Implementation

[DRC LUTLP-1] Combinatorial Loop Alert: 4 LUT cells form a combinatorial loop. This can create a race condition. Timing analysis may not be accurate. The preferred resolution is to modify the design to remove combinatorial logic loops. If the loop is known and understood, this DRC can be bypassed by acknowledging the condition and setting the following XDC constraint on any one of the nets in the loop: 'set_property ALLOW_COMBINATORIAL_LOOPS TRUE [get_nets <myHier/myNet>]'. One net in the loop is cpu/cpu_state_reg[3]_0. Please evaluate your design. The cells in the loop are: timer_interrupt/timer0/FSM_sequential_State[2]_i_3__0, cpu/FSM_sequential_State[2]_i_5, timer_interrupt/timer0/FSM_sequential_State[2]_i_5__0, and timer_interrupt/timer1/Int_Active_i_4.

Warning during Routing:

[DRC LUTLP-1] Combinatorial Loop Alert: 4 LUT cells form a combinatorial loop. This can create a race condition. Timing analysis may not be accurate. The preferred resolution is to modify the design to remove combinatorial logic loops. If the loop is known and understood, this DRC can be bypassed by acknowledging the condition and setting the following XDC constraint on any one of the nets in the loop: 'set_property ALLOW_COMBINATORIAL_LOOPS TRUE [get_nets <myHier/myNet>]'. One net in the loop is cpu/cpu_state_reg[3]_0. Please evaluate your design. The cells in the loop are: timer_interrupt/timer0/FSM_sequential_State[2]_i_3__0, cpu/FSM_sequential_State[2]_i_5, timer_interrupt/timer0/FSM_sequential_State[2]_i_5__0, and timer_interrupt/timer1/Int_Active_i_4.

But, then, in the generate bitstream phase, it stops with this error:

[DRC LUTLP-1] Combinatorial Loop Alert: 4 LUT cells form a combinatorial loop. This can create a race condition. Timing analysis may not be accurate. The preferred resolution is to modify the design to remove combinatorial logic loops. If the loop is known and understood, this DRC can be bypassed by acknowledging the condition and setting the following XDC constraint on any one of the nets in the loop: 'set_property ALLOW_COMBINATORIAL_LOOPS TRUE [get_nets <myHier/myNet>]'. One net in the loop is cpu/cpu_state_reg[3]_0. Please evaluate your design. The cells in the loop are: timer_interrupt/timer0/FSM_sequential_State[2]_i_3__0, cpu/FSM_sequential_State[2]_i_5, timer_interrupt/timer0/FSM_sequential_State[2]_i_5__0, and timer_interrupt/timer1/Int_Active_i_4.

[Vivado 12-1345] Error(s) found during DRC. Bitgen not run.

I need to admit, that i did not really get, yet, why this is a combinatorial loop due to the way how my state machine in timer.vhd works, this should never "loop".

But I think it would be possible, that I change the Daisy chain outputs to latches (but I would need to think about the semantics again in this case).

[MJoergen]

Ok, I just tried again, and I see the same behaviour as you: When changing the two lines you mention, I can no longer generate a bitstream. I think what I missed is that I forgot to do a "git pull".

The following screen shot shows the combinatorial loop in question. It goes through 4 different LUTs, before returning to itself.

Since one of the signals in the screen shot is t1_grant_n_in, I believe my initial analysis is on the right track.

Assuming my analysis is correct, it begs the question of how to fix the problem? One suggestion is to insert one or more registers somewhere in the loop. Of course, this changes the timing of the signals, so is certainly non-trivial.

What about placing a register on the grant output? This will delay the grant (and therefore the execution) of the interrupt by one clock cycle (maybe two clock cycles for the second timer?), but should not break anything functionally (based on my limited understanding). If this works, then we can later perhaps look into any possible optimizations, although I don't see anything likely at the moment.

Another option is to rethink the functionality on a global level (which is what Vivado does). I don't have anything concrete to offer here, but the combinatorial loop is probably not what we want in the design, so what should replace it?

[sy2002]

Thank you very much for this extremely helpful explanation! I assigned this issue back to me and me next steps will be:

Rethink the logic and the semantics: Then insert one more register at the right place to get rid of the loop.

[sy2002]

What about placing a register on the grant output?

@MJoergen Your idea was golden: After thinking it through, this was indeed the best option. Implemented it like that and as you can read in the latest comment of mine in issue #47 I indeed had fun and a great use for the second timer :-D