verilog adders (verilog optimization)
jprov...@yahoo.com
is
always trued/allowed?
If I have something like
reg [7:0] sig1, sig2, sig3;
always @ *
sig3 = 1 + 2 + 3 + sig1 + sig2 + 4;
There must be at least 2 adders. Is Verilog required to produce 3
adders?
The code can easily be collapsed to
sig3 = 6 + sig1 + sig2 + 4;
Verilog evaluates left to right, so this becomes
sig3 = ( (6 + sig1) + sig2) + 4;
This requires 3 adders. Is it legal for Verilog to compile the
original code to:
sig3 = 10 + sig1 + sig2;
Thoughts?
Thanks!
John Providenza
Andy
commutative properties of expressions in order to produce an optimal
implementation. If they don't, I don't use them very long.
Andy
jprov...@yahoo.com
For grins, I created a very simple test case and synthesized it
using the Xilinx XST synthesizer. Here's the code:
module test (
input clk,
input [7:0] a, b,
output reg [7:0] z
);
reg [7:0] a1, b1, z1;
always @(posedge clk)
begin
a1 <= a;
b1 <= b;
z <= z1;
end
always @ *
begin
z1 = 1 + 2 + 3 + a1 + b1 + 4;
end
endmodule
Guess what? 3 adders. If I reorder the arithmetic to be
z1 = 1 + 2 + 3 + 4 + a1 + b1;
then I get 2 adders.
John Providenza
John_H
>
> For grins, I created a very simple test case and synthesized it
> using the Xilinx XST synthesizer. Here's the code:
>
> always @ *
> begin
> z1 = 1 + 2 + 3 + a1 + b1 + 4;
> end
> endmodule
>
> Guess what? 3 adders. If I reorder the arithmetic to be
> z1 = 1 + 2 + 3 + 4 + a1 + b1;
> then I get 2 adders.
>
> John Providenza
Different synthesizers will produce different results. 20 years ago,
you might be hard pressed to find a Verilog synthesizer that wasn't
order-dependent but things are better now. The Xilinx XST has become
a respectable synthesizer but I still wouldn't call it a "world class"
synthesis engine. For a free tool, it's great.
A better synthesizer *might* produce repeatible results with minimal
logic. I don't think algebraic optimization is high on any
synthesizer's feature list, though, such that even exceptional logic
synthesizers might stumble on some simple arithmatic.
I'd personally love to see more work on algebraic optimization but I'm
not holding my breath.
- John_H
Mike Treseler
> Guess what? 3 adders. If I reorder the arithmetic to be
> z1 = 1 + 2 + 3 + 4 + a1 + b1;
> then I get 2 adders.
Try finishing the synthesis and compare LUTs and Flops.
Some reductions happen on the back-end.
-- Mike Treseler
jprov...@yahoo.com
Here's the XST synthesis data for the two cases. It sure looks to
me like there's extra logic.
I agree that XST is not well know as a state-of-the-art, super-duper,
terrific, knock-your-socks-off synthesizer, but it is a data point.
Code:
z1 = 1 + 2 + 3 + a1 + b1 + 4;
Cell Usage :
# BELS : 35
# GND : 1
# LUT1 : 1
# LUT2 : 7
# LUT3 : 1
# LUT4 : 7
# LUT5 : 1
# LUT6 : 1
# MUXCY : 7
# VCC : 1
# XORCY : 8
# FlipFlops/Latches : 24
# FD : 23
# FDR : 1
LUTS 18
XORCY 8
MUXCY 7
Code:
z1 = 1 + 2 + 3 + 4 + a1 + b1;
Cell Usage :
# BELS : 29
# GND : 1
# LUT1 : 1
# LUT2 : 6
# LUT4 : 6
# MUXCY : 7
# XORCY : 8
# FlipFlops/Latches : 24
# FD : 24
LUTS 13
XORCY 8
MUXCY 7
John Providenza
Mike Treseler
> Here's the XST synthesis data for the two cases. It sure looks to
> me like there's extra logic.
Sure enough.
Thanks for trying it, and for reporting results.
Consider submitting the case with Xilinx
since you have all the data.
> I agree that XST is not well know as a state-of-the-art, super-duper,
> terrific, knock-your-socks-off synthesizer, but it is a data point.
Well, you have proven your point.
The synthesis front-end should be
smart enough to collect constants.
On the other hand, most designers
would do something like:
parameter sum = 1+2+3+4;
-- Mike Treseler
Kevin Neilson
That's interesting. The fact that each design has 8 XORCYs leads me to
believe that there are only two adders, but I'm not sure why the LUT
count differs. It seems like there are only 8 LUTs needed--an 8-bit
adder (with truncated 8-bit output) should require only 4 LUTs and 4
XORCYs--so I don't know why there would be 13 and 18 LUTs used. Did you
look at the technology schematic?
-Kevin
jprov...@yahoo.com
I did not look in any detail. At some point, each synthesizer will
"do its own thing",
so I don't really care about the very low level details. The
schematics showed
3 adders, 2 of them had constants as inputs.
I'm curious as to
a) does Verilog some how require this?
b) what do some other synthesizers do?
John Providenza
Mike Treseler
> I'm curious as to
> a) does Verilog some how require this?
I don't see how.
Both cases sim the same.
> b) what do some other synthesizers do?
Quartus does about the same thing.
3 then 2 adders at the rtl level for the same cases
and a few extra LUTs for the 3 counter case.
-- Mike Treseler
Andy
Synplify Pro implements exactly the same thing for both orders (in
vhdl). 12 luts (Xilinx v4). RTL viewer shows three input adder (a1 +
b1 + 10) for both.
As it should be...
Andy
jprov...@yahoo.com
Andy -
My question is specific to Verilog, I don't know what the VHDL
language
spec requires. From a Verilog LRM:
All operators shall associate left to right with the exception of
the
conditional operator, which shall associate right to left.
Associativity
refers to the order in which the operators having the same
precedence
are evaluated.
Thus, in the following example B is added to A and then C is
subtracted
from the result of A+B.
A + B - C
So, if A is constant 3 and C is constant 1, does the language *spec*
prevent
Verilog from combining the two constants?
John Providenza
Jonathan Bromley
>So, if A is constant 3 and C is constant 1, does the language *spec*
>prevent Verilog from combining the two constants?
I don't believe so. Context-dependent operands of an
arithmetic expression (as are all operands of +, - etc)
are first widened to the context width, BEFORE any
arithmetic is done. Consequently, the order in which
addition-like operations are performed is unimportant,
because everything is done in the same bit-width.
I'm pretty sure (though I haven't yet proved it to my
own satisfaction) that multiplication can similarly be
rearranged algebraically, along with addition and
subtraction, without any effect on the results. But
division, with its potential loss of LSBs, will surely
exhibit some order dependences that would mess up
algebraic rearrangement.
--
Jonathan Bromley, Consultant
DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services
Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan...@MYCOMPANY.com
http://www.MYCOMPANY.com
The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
Muzaffer Kal
<jonathan...@MYCOMPANY.com> wrote:
>On Tue, 2 Sep 2008 08:27:10 -0700 (PDT), jprov...@yahoo.com wrote:
>
>>So, if A is constant 3 and C is constant 1, does the language *spec*
>>prevent Verilog from combining the two constants?
>
>I'm pretty sure (though I haven't yet proved it to my
>own satisfaction) that multiplication can similarly be
>rearranged algebraically, along with addition and
>subtraction, without any effect on the results.
I don't think this is true when you say "along with addition and
subtraction". Multiplication (& division) has higher precedence than
addition & subtraction so you can't re-arrange it with them. A + B + C
might give the same result whether you calculate (A+B)+C or even
(A+C)+B but this is certainly not true A + B*C. Because of precedence
rules this has to be implemented as A + (B*C) and can't be done as
(A+B)*C.
Muzaffer Kal
Jonathan Bromley
>On Tue, 02 Sep 2008 17:27:57 +0100, Jonathan Bromley
><jonathan...@MYCOMPANY.com> wrote:
>
>>I'm pretty sure (though I haven't yet proved it to my
>>own satisfaction) that multiplication can similarly be
>>rearranged algebraically, along with addition and
>>subtraction, without any effect on the results.
>
>I don't think this is true when you say "along with addition and
>subtraction". Multiplication (& division) has higher precedence than
>addition & subtraction so you can't re-arrange it with them.
No, for sure; that's why I said "rearranged algebraically".
I was thinking of rearrangements such as
A*B + A*C === A*(B+C)
which can often save hardware - in this case, one
multiplier saved with no other cost.
I don't know how effectively the existing synthesis tools
do that kind of thing, though.
Mike Treseler
> No, for sure; that's why I said "rearranged algebraically".
> I was thinking of rearrangements such as
>
> A*B + A*C === A*(B+C)
>
> which can often save hardware - in this case, one
> multiplier saved with no other cost.
>
> I don't know how effectively the existing synthesis tools
> do that kind of thing, though.
Since brand A+X can't even collect constants,
I would try this experiment on Synplify Pro or Mentor.
-- Mike Treseler
Mike Treseler
> Synplify Pro implements exactly the same thing for both orders (in
> vhdl). 12 luts (Xilinx v4). RTL viewer shows three input adder (a1 +
> b1 + 10) for both.
>
> As it should be...
Indeed. Thanks for posting the results.
-- Mike Treseler
Andy
equal-precedence arithmetic operators IN SIMULATION as Verilog has.
But we are not talking about a simulation, we are talking about
synthesis. With equal precedence arithmetic operators that do not have
"side effects," order of execution is unobservable (has no external
effect), but amongst those that do have side effects (most commonly
encountered with function calls and logical operators), order is
important.
For synthesis, the execution order rules for simulation do not always
have any meaning. If the results are always equivalent between the LRM
execution ordering and the implementation ordering, it is by
definition legal synthesis. In this context, equivalence is evaluated
at register/IO boundaries, not intermediate expressions or even
assignments. That's why they call it Register Transfer Logic (or
Level).
Restraining the synthesized implementation to maintain the same order
of operations, for no other reason than matching the execution order
from simulation, would eliminate a whole host of beneficial
optimizations. We would then be forced to write code that explicitly
describes an optimal (our choice, not the tool's) implementation. And
register re-timing would be absolutely forbidden.
Andy
jprov...@yahoo.com
Yes, thank for posting the info, but I believe it is for VHDL. My
original
question was "does the Verilog language specifically forbid merging
the
constants" as opoosed to "how good is your synthesis tool".
John Providenza
Mike Treseler
> Yes, thank for posting the info, but I believe it is for VHDL.
I synthesized *your* verilog example.
> My original
> question was "does the Verilog language specifically forbid merging
> the constants" as opoosed to "how good is your synthesis tool".
The answers were NO, NO, and NO, before
the discussion strayed.
This happens sometimes on usenet.
-- Mike Treseler
Andy
No language that I am familiar with forbids optimizations (whether in
compilers, simulators or synthesizers) that are externally identical
to the language specification behavior. If there are no external
artifacts of re-ordering the operations, then reordering is permitted
as a viable optimization.
Andy
glen herrmannsfeldt
(snip)
> All operators shall associate left to right
> with the exception of the conditional operator,
> which shall associate right to left.
(snip)
> Thus, in the following example B is added to A
> and then C is subtracted from the result of A+B.
> A + B - C
> So, if A is constant 3 and C is constant 1, does the
> language *spec* prevent
> Verilog from combining the two constants?
Associativity order is needed, for example, for
A - B + C, which is either (A - B) + C, or
A - (B + C), which are very different.
Otherwise, the important thing is that the result
be the same, which has requirements on bit width
and overflow, which might depend on order.
-- glen
Jonathan Bromley
>Otherwise, the important thing is that the result
>be the same, which has requirements on bit width
>and overflow, which might depend on order.
Yes; but, as I've pointed out before, all the operands
will first be widened to the context width, _before_
any arithmetic is done. So _all_ the operations are
done modulo the context width. I think you'll find
that, as a result, order of operations doesn't affect
the way the operations overflow. Information is lost,
but the loss of information is always in MSBs that
will in any case be lost because they fall outside
the context width.
The exception is the division operator / which can
lose information in bits that fall inside the context
width. An obvious example:
A/B + C/B === (A+C)/B ??? Algebra OK
4'd2/4'd3 + 4'd2/4'd3
= 4'd0 + 4'd0
= 4'd0
but
(4'd2 + 4'd2) / 4'd3
= 4'd4 / 4'd3
= 4'd1
Evan Lavelle
> All operators shall associate left to right with the exception of
>the
> conditional operator, which shall associate right to left.
>Associativity
> refers to the order in which the operators having the same
>precedence
> are evaluated.
>
> Thus, in the following example B is added to A and then C is
>subtracted
> from the result of A+B.
> A + B - C
>
>So, if A is constant 3 and C is constant 1, does the language *spec*
>prevent
>Verilog from combining the two constants?
No. In principle, it could be prevented by an "expression evaluation
order" specification (which isn't the same as precedence), but Verilog
doesn't do this.
Java and C#, for example, have a left-to-right evaluation order
specification. Everyone agrees that 'A+B-C' is actually '(A+B)-C', but
the '-' operator has two subexpressions: '(A+B)' and 'C'. In
left-to-right ordering, A+B must be evaluated before C, so you can't
(in general) combine A and C before evaluation(*).
C doesn't have a left-to-right specification, but instead says that
the results must be as expected at any 'sequence points'. There's no
sequence point in 'A+B-C', so C just says that that the result is
undefined during the evaluation of 'A+B-C', but must have the expected
value of '(A+B)-C' when the next sequence point is reached. In C, you
can optimise as you want, with the result that some things are
non-deterministic; the left-to-right rule favours determinism over
optimisation.
Verilog isn't defined to this level of detail, and doesn't require
left-to-right evaluation, and doesn't define sequence points. It seems
that you can do what you want. A more modern HDL would almost
certainly make more effort to ensure deterministic results.
But, as others have pointed out, synthesis is different anyway.
Verilog was defined as a simulation language and synthesis was bolted
on afterwards; the LRM doesn't talk about synthesis results.
-Evan
(*) actually, Java just says that "The left-hand operand of a binary
operator *appears* to be fully evaluated before any part of the
right-hand operand is evaluated" (my emphasis), so in this simple case
Java doesn't prevent re-arrangement. In principle, though, you can't
do it.
gabor
I tried both ways with Synplify for Lattice (ispLever 7.0)
and got exactly the same results in each case:
---------------------------------------
Resource Usage Report
Part: lfe2_12e-5
Register bits: 24 of 12000 (0%)
I/O cells: 25
Details:
CCU2B: 4
IB: 17
IFS1P3DX: 16
OB: 8
OFS1P3DX: 8
ORCALUT4: 5
VHI: 1
VLO: 1
Not sure how this translates to Xilinx resources, but the fact that
nothing changes when I re-arrange the constants seems to prove that
they are always combined regardless of placement.
Regards,
Gabor