Signal(s) form a combinatorial loop VHDL

Question

I was trying to implement Dual-priority encoder but I get following warnings during synthesize:

WARNING:Xst:2170 - Unit prEnc : the following signal(s) form a combinatorial loop: done, first<3>, req[0]_done_AND_6_o, f.

WARNING:Xst:2170 - Unit prEnc : the following signal(s) form a combinatorial loop: f.

I got no idea how and where my signals form a combinatorial loop.

Here is the code.

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
entity prEnc is
port( req : in std_logic_vector(7 downto 0);
 first : out std_logic_vector(3 downto 0);
 second : out std_logic_vector(3 downto 0)
);
end prEnc;
architecture Behavioral of prEnc is
signal f, done : std_logic ;
begin
process (req,f,done)
begin
 first <= "0000";
 second <= "0000";
 f <= '0';
 done <= '0';
 if req(7) = '1' then
 first <= "1000";
 f <= '1';
 end if ;
 if req(6) = '1' then
 if f = '0' then
 first <= "0111";
 f <= '1';
 else 
 second <= "0111";
 done <= '1';
 end if;
 end if;
 if req(5) = '1' and done = '0' then
 if f = '0' then
 first <= "0110";
 f <= '1';
 else
 second <= "0110";
 done <= '1';
 end if;
 end if;
 if req(4) = '1' and done = '0' then
 if f = '0' then
 first <= "0101";
 f <= '1';
 else 
 second <= "0101";
 done <= '1';
 end if;
 end if;
 if req(3) = '1' and done = '0' then
 if f = '0' then
 first <= "0100";
 f <= '1';
 else 
 second <= "0100";
 done <= '1';
 end if;
 end if;
 if req(2) = '1' and done = '0' then
 if f = '0' then
 first <= "0011";
 f <= '1';
 else 
 second <= "0011";
 done <= '1';
 end if;
 end if;
 if req(1) = '1' and done = '0' then
 if f = '0' then
 first <= "0010";
 f <= '1';
 else 
 second <= "0010";
 done <= '1';
 end if;
 end if;
 if req(0) = '1' and done = '0' then
 if f = '0' then
 first <= "0001";
 f <= '1';
 else 
 second <= "0001";
 done <= '1';
 end if;
 end if;
end process;
end Behavioral;

Answer 1

You are both setting and reading the signals f and done in the same process; this creates the feedback ("combinatorial loop") that the tools are complaining about.

In order to eliminate that kind of feedback, you need to explicitly list every combination of req:

architecture Behavioral2 of prEnc is
begin
 process (req) begin
 if req(7) = '1' then
 first <= "1000";
 if req(6) = '1' then second <= "0111";
 elsif req(5) = '1' then second <= "0110";
 elsif req(4) = '1' then second <= "0101";
 elsif req(3) = '1' then second <= "0100";
 elsif req(2) = '1' then second <= "0011";
 elsif req(1) = '1' then second <= "0010";
 elsif req(0) = '1' then second <= "0001";
 else second <= "0000";
 end if;
 elsif req(6) = '1' then
 first <= "0111";
 if req(5) = '1' then second <= "0110";
 elsif req(4) = '1' then second <= "0101";
 elsif req(3) = '1' then second <= "0100";
 elsif req(2) = '1' then second <= "0011";
 elsif req(1) = '1' then second <= "0010";
 elsif req(0) = '1' then second <= "0001";
 else second <= "0000";
 end if;
 elsif req(5) = '1' then
 first <= "0110";
 if req(4) = '1' then second <= "0101";
 elsif req(3) = '1' then second <= "0100";
 elsif req(2) = '1' then second <= "0011";
 elsif req(1) = '1' then second <= "0010";
 elsif req(0) = '1' then second <= "0001";
 else second <= "0000";
 end if;
 elsif req(4) = '1' then
 first <= "0101";
 if req(3) = '1' then second <= "0100";
 elsif req(2) = '1' then second <= "0011";
 elsif req(1) = '1' then second <= "0010";
 elsif req(0) = '1' then second <= "0001";
 else second <= "0000";
 end if;
 elsif req(3) = '1' then
 first <= "0100";
 if req(2) = '1' then second <= "0011";
 elsif req(1) = '1' then second <= "0010";
 elsif req(0) = '1' then second <= "0001";
 else second <= "0000";
 end if;
 elsif req(2) = '1' then
 first <= "0011";
 if req(1) = '1' then second <= "0010";
 elsif req(0) = '1' then second <= "0001";
 else second <= "0000";
 end if;
 elsif req(1) = '1' then
 first <= "0010";
 if req(0) = '1' then second <= "0001";
 else second <= "0000";
 end if;
 elsif req(0) = '1' then
 first <= "0001";
 second <= "0000";
 else
 first <= "0000";
 second <= "0000";
 end if;
 end process;
end Behavioral2;

EDIT

It might be easier to use two single-level priority encoders, using the the first to select the set of inputs that's presented to the second:

architecture Behavioral3 of prEnc is
 signal mask, req_b : stl_logic_vector (7 downto 0);
begin
 process (req) begin
 if req(7) = '1' then first <= "1000"; mask <= "01111111";
 elsif req(6) = '1' then first <= "0111"; mask <= "00111111";
 elsif req(5) = '1' then first <= "0110"; mask <= "00011111";
 elsif req(4) = '1' then first <= "0101"; mask <= "00001111";
 elsif req(3) = '1' then first <= "0100"; mask <= "00000111";
 elsif req(2) = '1' then first <= "0011"; mask <= "00000011";
 elsif req(1) = '1' then first <= "0010"; mask <= "00000001";
 elsif req(0) = '1' then first <= "0001"; mask <= "00000000";
 else first <= "0000"; mask <= "00000000";
 end if;
 end process;
 req_b <= req and mask;
 process (req_b) begin
 if req_b(7) = '1' then second <= "1000";
 elsif req_b(6) = '1' then second <= "0111";
 elsif req_b(5) = '1' then second <= "0110";
 elsif req_b(4) = '1' then second <= "0101";
 elsif req_b(3) = '1' then second <= "0100";
 elsif req_b(2) = '1' then second <= "0011";
 elsif req_b(1) = '1' then second <= "0010";
 elsif req_b(0) = '1' then second <= "0001";
 else second <= "0000";
 end if;
 end process;
end Behavioral3;

• user16324: +1. Bonus points if you can write a synthesizable pair of for loops to do the same job with much less effort.
• Al Bundy: So, inside process each unrelated if construct occurs concurrently but every related if and elseif occurs sequentially ? Am I right ?
• Dave Tweed: @user3023499: No, everything is concurrent. You can think of if as being a kind of AND gate, and the corresponding else as being AND NOT. Even though the code inside a process looks like sequential (software) code, it is still specifying concurrent (hardware) operation. The syntax simply provides a concise way to describe common behaviors.
• Dave Tweed: @BrianDrummond: I don't think there's any good way to do it with for loops, but using two single-level encoders, as shown in my edit above, seems simple enough.
• user16324: @Dave Tweed : heh, I beg to differ :-) Nonetheless I do like your second answer, but I can't upvote again.

Answer 2

When repetitive operations like this are demanded, often a For loop (within a process) is the answer.

People shy away from loops, and I'm not sure why : possibly some antique synthesis tools had trouble with them, but now they do quite a good job of synthesising loops, functions, procedures, etc - PROVIDED these are all written with a view to hardware generation. (NB the following is only true of processes WITHOUT Wait statements, for simplicity)

And that means bearing in mind how the loop is "executed" by the synthesis tool...

Example: (warning : not tested in simulation!)

use IEEE.STD_LOGIC_1164.ALL;
use IEEE.numeric_std.all;
entity prEnc is
port( req : in std_logic_vector(7 downto 0);
 first : out unsigned(3 downto 0);
 second : out unsigned(3 downto 0)
);
end prEnc;
architecture Loopy of prEnc is
begin
 process (req) begin
 first <= "0000"; -- default assignments
 second <= "0000";
 outer:
 for i in req'range loop -- req range is 7 downto 0
 if req(i) = '1' then
 first <= to_unsigned(i+1,first'length);
 inner:
 for j in req'range loop
 if j < i and req(j) = '1' then
 second <= to_unsigned(j+1, second'length);
 exit inner;
 end if;
 end loop;
 exit outer;
 end if;
 end loop;
 end process;
end Loopy;

You can view it as being executed in sequential fashion, step by step - BUT in an instantaneously short time called a "delta cycle". And if you're not familiar with these, learn them. This Q&A may help. What happens is that the loop is unrolled by the synthesis tool, so every iteration actually executes in parallel, but the effect will be the same as if each step was executed in turn.

Variables (like the loop variables I,J) update their values immediately but signals don't update until the end of the process. Hence the last assignment to signal "first" wins. The default assignment at the top of the process applies ONLY if no other assignments happen.

Couple of simple rules :
1) Make loop bounds static. In the inner loop, instead of 'for j = i downto 0', iterate j over the whole loop, comparing with i to see if we need to execute the test. This will synthesise pretty much down to the mask in David's second version.

2) Bear in mind that - if you're not careful - unrolling the loop can generate a HUGE piece of hardware, and that "instantaneous" execution will be reported by timing analysis as taking far longer than your clock period. So ... be careful. (But you'll see these defects in the synthesis report and that'll tell you if you need to do better)

And a style point : I prefer to use the type system rather than fight it. As first,second are unsigned numbers, I made them unsigned. Clearer, and saves type conversions...

So how big is this thing with two nested loops compared to the originals? Xilinx XST 14.4 gives the following results (for Artix-7)

behavioral2: Slice Logic Utilization:
Number of Slice LUTs: 10 out of 63400 0%
Number used as Logic: 10 out of 63400 0%

behavioral3: Slice Logic Utilization:
Number of Slice LUTs: 11 out of 63400 0%
Number used as Logic: 11 out of 63400 0%

loopy: Slice Logic Utilization:
Number of Slice LUTs: 10 out of 63400 0%
Number used as Logic: 10 out of 63400 0%

So ... because the loop bounds are all static (local constants) the loop structures and additions optimise away to nothing. What's left is the same size as the original.

(EDIT: as Dave points out I should have simulated, I forgot to abort the loop on the first success... the revised version synthesises to 11 LUTs. Whether it's easier to get the simple loop right or the original huge cut'n'paste is up for debate. I think my point that there's a "good" ... but not "foolproof"! ... approach using loops still stands)

• Dave Tweed: That looks like a good approach, but I think it doesn't work. As you say, it's the last assignment in a process that prevails, and that would correspond to the the last iterations of each of the loops. So, ignoring the inner loop for the moment, if more than one bit in req is set, first will end up being assigned the value of the lowest one, not the highest one. You might be able to fix it by reversing the ranges used for the loop indices. But I think this is the reason that many people avoid loops -- it's far too easy to get tripped up on details like these.
• user16324: Good point : a cleaner fix is by "exit" statements, which better match the original semantics (not executing the "else" clause).