Why does this Verilog hog down 30 macrocells and hundreds of product terms?

Question

I have a project that's consuming 34 of a Xilinx Coolrunner II's macrocells. I noticed I had an error and tracked it down to this:

assign rlever = RL[0] ? 3'b000 :
                RL[1] ? 3'b001 :
                RL[2] ? 3'b010 :
                RL[3] ? 3'b011 :
                RL[4] ? 3'b100 :
                RL[5] ? 3'b101 :
                RL[6] ? 3'b110 :
                        3'b111;

assign llever = LL[0] ? 3'b000 :
                LL[1] ? 3'b001 :
                LL[2] ? 3'b010 :
                LL[3] ? 3'b011 :
                LL[4] ? 3'b100 :
                LL[5] ? 3'b101 :
                        3'b110 ;

The error is that rlever and llever are one bit wide, and I need them to be three bits wide. Silly me. I changed the code to be:

wire [2:0] rlever ...
wire [2:0] llever ...

so there were enough bits. However, when I rebuilt the project, this change costed me more than 30 macrocells and hundreds of product terms. Can anyone explain what I have done wrong?

(The good news is that it now simulates correctly... :-P )

EDIT -

I suppose I'm frustrated because about the time I think I start understanding Verilog and the CPLD, something happens which shows I clearly have no understanding.

assign outp[0] = inp[0] | inp[2] | inp[4] | inp[6];
assign outp[1] = inp[1] | inp[2] | inp[5] | inp[6];
assign outp[2] = inp[3] | inp[4] | inp[5] | inp[6];

The logic to implement those three lines occurs twice. That means that each of the 6 lines of Verilog consumes about 6 macrocells and 32 product terms each.

EDIT 2 - As per @ThePhoton's suggestion about the optimization switch, here is information from the summary pages produced by ISE:

Synthesizing Unit <mux1>.
    Related source file is "mux1.v".
    Found 3-bit 1-of-9 priority encoder for signal <code>.
Unit <mux1> synthesized.
(snip!)
# Priority Encoders                                    : 2
 3-bit 1-of-9 priority encoder                         : 2

So clearly the code was recognized as something special. The design is still consuming tremendous resources, however.

EDIT 3 -

I made a new schematic including only the mux that @thePhoton recommended. Synthesis produced insignificant resource usage. I also synthesized the module recommended by @Michael Karas. This also produced insignificant usage. So some sanity is prevailing.

Clearly, my use of the lever values is causing consternation. More To Come.

Final Edit

The design is no longer insane. I am not sure what happened, however. I made a lot of changes in order to implement new algorithms. One contributing factor was a 'ROM' of 111 15-bit elements. This consumed a modest number of macrocells but a lot of product terms - nearly all of those available on the xc2c64a. I look for this but had not noticed it. I believe my error was hidden by optimization. The 'levers' I'm talking about are used to select values from the ROM. I hypothesize that when I implemented the (busted) 1-bit priority encoder, ISE optimized away some of the ROM. That would be quite a trick, but it's the only explanation I can think of. This optimization reduced the resource usage markedly and lulled me into expecting a certain base-line. When I fixed the priority encoder (as per this thread,) I saw the overhead of the priority encoder and the ROM that had previously been optimized away and attributed this to the former exclusively.

After all this, I was good on macrocells but had depleted my product terms. Half of the ROM was a luxury, really, as it was just the 2's comp of the first half. I removed the negative values, replacing them elsewhere them with a simple calculation. This allowed me to trade macrocells for product terms.

For now, this thing fits into the xc2c64a; I've used 81% and 84% of my macrocells and product terms respectively. Of course, now I have to test it to ensure it does what I want...

Thanks to ThePhoton and Michael Karas for the assist. In addition to the moral support they lent to help me solve this, I've learned from the Xilinx document ThePhoton posted, and I implemented the priority encoder suggest by Michael.

Answer 1

The code you show is essentially a priority encoder. That is, it has an input of many signals, and its output indicates which of those signals is set, giving priority to the left-most set signal if more than one is set.

However, I see conflicting definitions of the standard behavior for this circuit in the two places I checked.

According to Wikipedia, the standard priority encoder numbers its inputs from 1. That is, if the least significant input bit is set, it outputs 1, not 0. The Wikipedia priority encoder outputs 0 when none of the input bits are set.

Xilinx's XST User Guide (p. 80), however, defines a priority encoder closer to what you coded. The inputs are numbered from 0, so when the input's lsb is set it gives a 0 output. However, the Xilinx definition gives no spec for the output when all input bits are clear (Your code will output 3'd7).

The Xilinx user guide, of course, will determine what the Xilinx synthesis software is expecting. The main point is that a special directive (*priority_extract ="force"*) is required for XST to recognize this structure and generate optimal synthesis results.

Here's Xilinx's recommended form for an 8-to-3 priority encoder:

(* priority_extract="force" *)
module v_priority_encoder_1 (sel, code);
input [7:0] sel;
output [2:0] code;
reg [2:0] code;
always @(sel)
begin
    if (sel[0]) code = 3’b000;
    else if (sel[1]) code = 3’b001;
    else if (sel[2]) code = 3’b010;
    else if (sel[3]) code = 3’b011;
    else if (sel[4]) code = 3’b100;
    else if (sel[5]) code = 3’b101;
    else if (sel[6]) code = 3’b110;
    else if (sel[7]) code = 3’b111;
    else code = 3’bxxx;
end
endmodule

If you can rearrange your surrounding logic to let you use Xilinx's recommended coding style, that's probably the best way to get a better result.

I think you can get this by instantiating the Xilinx encoder module with

v_priority_encoder_1 pe_inst (.sel({~|{RL[6:0]}, RL[6:0]}), .code(rlever));

I've nor'ed together all bits of RL[6:0] to get an 8th input bit that will trigger the 3'b111 output when all RL bits are low.

For the llever logic, you can probably reduce the resource usage by making a modified encoder module, following the Xilinx template, but requiring only 7 input bits (your 6 bits of LL plus an additional bit that goes high when the other 6 are all low).

Using this template assumes the version of ISE you have is using the XST synthesis engine. It seems like they change synthesis tools on every major rev of ISE, so check that the document I linked actually corresponds to your version of ISE. If not, check the recommended style in your documentation to see what your tool expects.

Answer 2

ThePhoton's answer is an excellent one. I would like to add some additional information here for your consideration. This stems from the fact that even though we have state of the art fancy FPGA and CPLD devices using HDLs and systhesis tools it can be informative to look closely at things designed years ago. Stay with me while I walk through this to my recommendation at the end.

There are discrete logic parts that perform the priority encoding function. The logic implemented by these parts has been around for a long time when it was essential to reduce the number of transistors to a bare minimum. You can search on the web for logic parts with generic part numbers such as 74HC148 or MC14532B to find data sheets that include equivalent logic diagrams for these parts. The diagram below is one example taken from the TI data sheet for the 74HC148 part.

This logic implements the following truth table (taken from the same data sheet):

Note that the above part family uses low active input signals. Another data sheet for the ON Semiconductor MC14532B part shows a truth table for the encoder function using active high input signals similar to your Verilog example.

The same data sheet shows the logic equations for the MC14532B as follows:

You may want to consider coding similar equations directly into your Verilog code to see how it compares with your present example. It is highly likely to result in a much more favorable result.