verilog adders (verilog optimization)

On Sep 2, 3:16*pm, jprovide...@yahoo.com wrote:
> On Sep 2, 11:24*am, Mike Treseler <mtrese...@gmail.com> wrote:
>
> > Andy wrote:
> > > 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
>
> 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

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

jprovidenza@yahoo.com wrote:
(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

On Tue, 02 Sep 2008 22:24:17 -0800, glen herrmannsfeldt wrote:

>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

--
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.bromley@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.

On Tue, 2 Sep 2008 08:27:10 -0700 (PDT), jprovidenza@yahoo.com wrote:

> 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.

On Aug 29, 10:38 am, jprovide...@yahoo.com wrote:
> On Aug 29, 7:03 am, Andy <jonesa...@comcast.net> wrote:
>
> > Most synthesis tools will take advantage of associative and
> > commutative properties of expressions in order to produce an optimal
> > implementation. If they don't, I don't use them very long.
>
> > Andy
>
> 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

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