myhdl-list

[myhdl-list] arithmetic trouble

[Neal B. <ndb...@gm...>]

I'm still learning verilog.  Anyway, I found the following problem.

------------------------------
from myhdl import Signal, always, intbv, Simulation, delay, toVerilog, 
traceSignals, instance, always_comb

def test1 (a, b, out):
    @always_comb
    def test1_logic():
        out.next = (a * b) >> 16

    return test1_logic

def max_signed (bits):
    return ~(-1 << (bits-1))

def min_signed (bits):
    return (-1 << (bits-1))

a = Signal (intbv(0, min_signed (16), max_signed (16)+1))
b = Signal (intbv(0, min_signed (16), max_signed (16)+1))
out = Signal (intbv(0, min_signed (16), max_signed (16)+1))

toVerilog (test1, a, b, out)

-----------------------------
module test1 (
    a,
    b,
    out
);

input signed [15:0] a;
input signed [15:0] b;
output signed [15:0] out;
wire signed [15:0] out;





assign out = $signed((a * b) >>> 16);

endmodule
-----------------------

The problem is, it seems that (a * b) >>> 16 all in 1 step doesn't work 
correctly.  I'm using cadence (version is 8.1?).  The simulator gives 
strange results.  It seems to act as if it doesn't understand the bitwidth 
of the intermediate result of (a*b), so that when shifted it's not correctly 
handling the sign.

It works correctly if I break into 2 steps, where I use a tmp variable of 
_the correct bit width_ before shifting.

Is this a common issue with verilog simulators, or is mine just broken?

Should my_hdl try to workaround this?

Re: [myhdl-list] arithmetic trouble

[Christopher F. <chr...@gm...>]

>
>
>
> It works correctly if I break into 2 steps, where I use a tmp variable of
> _the correct bit width_ before shifting.
>
> Is this a common issue with verilog simulators, or is mine just broken?
>
> Should my_hdl try to workaround this?
>
>
>
I don't recall the exact rules off the top of my head, either.  But I think
this is correct.  The language doesn't presume to know what the intermediate
bit representation of the operator is (Verilog language).  If you want full
precision for the multiply you have to do it in two steps as you indicated
or have your output be the full range.

BOMK everything is working correctly.  What you notice is a simulation
mismatch?  The MyHDL simulates fine because the * uses full precision
(infinite bits) and the bounds are not checked until the left hand side is
assigned and that is after the shift.   Hmmmm, don't know if this would be a
bug or not.  Not all aspects are convertible and this would fit that
scenario.

Re: [myhdl-list] arithmetic trouble

[Jan D. <ja...@ja...>]

Christopher Felton wrote:
> 
> 
>     It works correctly if I break into 2 steps, where I use a tmp
>     variable of
>     _the correct bit width_ before shifting.
> 
>     Is this a common issue with verilog simulators, or is mine just broken?
> 
>     Should my_hdl try to workaround this?
> 
> 
> 
> I don't recall the exact rules off the top of my head, either.  But I 
> think this is correct.  The language doesn't presume to know what the 
> intermediate bit representation of the operator is (Verilog language). 
>  If you want full precision for the multiply you have to do it in two 
> steps as you indicated or have your output be the full range.
> 
> BOMK everything is working correctly.  What you notice is a simulation 
> mismatch?  The MyHDL simulates fine because the * uses full precision 
> (infinite bits) and the bounds are not checked until the left hand side 
> is assigned and that is after the shift.   Hmmmm, don't know if this 
> would be a bug or not.  Not all aspects are convertible and this would 
> fit that scenario.

My rule is crystal-clear: if MyHDL code simulates fine and converts fine,
simulations should match. Otherwise, there is a bug - either in the
convertor or in the HDL simulator. For this it is not relevant whether
MyHDL does the "right" thing or not.

So it looks like we have a bug here and now we have to find out
what it is. Of course, it may be that something cannot be reliably
converted, in which case the convertor should issue an error.

Jan

-- 
Jan Decaluwe - Resources bvba - http://www.jandecaluwe.com
    Python as a HDL: http://www.myhdl.org
    VHDL development, the modern way: http://www.sigasi.com
    Analog design automation: http://www.mephisto-da.com
    World-class digital design: http://www.easics.com

Re: [myhdl-list] arithmetic trouble

[Neal B. <ndb...@gm...>]

Jan Decaluwe wrote:

> Christopher Felton wrote:
>> 
>> 
>>     It works correctly if I break into 2 steps, where I use a tmp
>>     variable of
>>     _the correct bit width_ before shifting.
>> 
>>     Is this a common issue with verilog simulators, or is mine just
>>     broken?
>> 
>>     Should my_hdl try to workaround this?
>> 
>> 
>> 
>> I don't recall the exact rules off the top of my head, either.  But I
>> think this is correct.  The language doesn't presume to know what the
>> intermediate bit representation of the operator is (Verilog language).
>>  If you want full precision for the multiply you have to do it in two
>> steps as you indicated or have your output be the full range.
>> 
>> BOMK everything is working correctly.  What you notice is a simulation
>> mismatch?  The MyHDL simulates fine because the * uses full precision
>> (infinite bits) and the bounds are not checked until the left hand side
>> is assigned and that is after the shift.   Hmmmm, don't know if this
>> would be a bug or not.  Not all aspects are convertible and this would
>> fit that scenario.
> 
> My rule is crystal-clear: if MyHDL code simulates fine and converts fine,
> simulations should match. Otherwise, there is a bug - either in the
> convertor or in the HDL simulator. For this it is not relevant whether
> MyHDL does the "right" thing or not.
> 
> So it looks like we have a bug here and now we have to find out
> what it is. Of course, it may be that something cannot be reliably
> converted, in which case the convertor should issue an error.
> 
> Jan
> 

I suppose (not tested) that using systemverilog cast on the operands before 
the operation to cast to the wider result type would fix it?

Re: [myhdl-list] arithmetic trouble

[Christopher L. F. <chr...@gm...>]

> Jan Decaluwe wrote:
>
>   
>> Christopher Felton wrote:
>>     
>>>     It works correctly if I break into 2 steps, where I use a tmp
>>>     variable of
>>>     _the correct bit width_ before shifting.
>>>
>>>     Is this a common issue with verilog simulators, or is mine just
>>>     broken?
>>>
>>>     Should my_hdl try to workaround this?
>>>
>>>
>>>
>>> I don't recall the exact rules off the top of my head, either.  But I
>>> think this is correct.  The language doesn't presume to know what the
>>> intermediate bit representation of the operator is (Verilog language).
>>>  If you want full precision for the multiply you have to do it in two
>>> steps as you indicated or have your output be the full range.
>>>
>>> BOMK everything is working correctly.  What you notice is a simulation
>>> mismatch?  The MyHDL simulates fine because the * uses full precision
>>> (infinite bits) and the bounds are not checked until the left hand side
>>> is assigned and that is after the shift.   Hmmmm, don't know if this
>>> would be a bug or not.  Not all aspects are convertible and this would
>>> fit that scenario.
>>>       
>> My rule is crystal-clear: if MyHDL code simulates fine and converts fine,
>> simulations should match. Otherwise, there is a bug - either in the
>> convertor or in the HDL simulator. For this it is not relevant whether
>> MyHDL does the "right" thing or not.
>>
>> So it looks like we have a bug here and now we have to find out
>> what it is. Of course, it may be that something cannot be reliably
>> converted, in which case the convertor should issue an error.
>>
>> Jan
>>
>>     
>
> I suppose (not tested) that using systemverilog cast on the operands before 
> the operation to cast to the wider result type would fix it?
>
>
>   
I don't think this would be a desired solution, because
  1.  Open-Source simulators (cver and icarus) will not support it.  As 
well as many of the synthesis tools.
  2.  In general, I think the converters try to use the lowest common 
denominator.  Meaning it uses the simplest, straight forward constructs 
of the underlying HDL (converting to).

But the questions can be asked, since the operation is broken into 
intermediate steps, could the converter do this?  Could it automagically 
break a complex operation into multiple steps? To enforce (match) the 
expected results of the MyHDL simulation.  I believe MyHDL (Python) has 
no limit on the intermediate value, the value isn't checked, verified 
till the assignment.  This would have to be implemented or restricted.  
Designers would have to realize large intermediate bit value could exist.

I believe you would have to be careful here though.  You do not want 
complication or too much inference from the converter.  You would want a 
very simple rule for Verilog that could be implemented.  There are many 
scenarios where an intermediate result requires a larger bit-value.  
Basically anytime a complex operation (equation) has an increasing and 
decreasing component you can run into this simulation mismatch.  If we 
prevent the operations we would have to prevent all combinations of 
increasing and decreasing, such as:
  (a + b)  - c
  (a + b)  >> c
  (a * b)  - c
  (a * b)  >> c
  (a << b) - c
  (a << b) >> c
etc, etc.

Some of these may not make sense (rarely used) but they are all (BOMK) 
valid statements.  The verilog converter would have to restrict all of 
these or handle all of them.  I don't know which is the best answer, yet.

Re: [myhdl-list] arithmetic trouble

[Jan D. <ja...@ja...>]

Neal Becker wrote:

>>
> 
> I suppose (not tested) that using systemverilog cast on the operands before 
> the operation to cast to the wider result type would fix it?

Probably yes. How does this work, like resize in VHDL?

Jan


-- 
Jan Decaluwe - Resources bvba - http://www.jandecaluwe.com
    Python as a HDL: http://www.myhdl.org
    VHDL development, the modern way: http://www.sigasi.com
    Analog design automation: http://www.mephisto-da.com
    World-class digital design: http://www.easics.com

Re: [myhdl-list] arithmetic trouble

[Christopher F. <chr...@gm...>]

On Sat, May 16, 2009 at 2:16 AM, Jan Decaluwe <ja...@ja...> wrote:

> Christopher L. Felton wrote:
>
> > But the questions can be asked, since the operation is broken into
> > intermediate steps, could the converter do this?  Could it automagically
> > break a complex operation into multiple steps?
>
> It could potentially do this, just as it now does resizes in VHDL.
> Of course it may not worth the trouble.
>
> > I believe you would have to be careful here though.  You do not want
> > complication or too much inference from the converter.  You would want a
> > very simple rule for Verilog that could be implemented.  There are many
> > scenarios where an intermediate result requires a larger bit-value.
> > Basically anytime a complex operation (equation) has an increasing and
> > decreasing component you can run into this simulation mismatch.  If we
> > prevent the operations we would have to prevent all combinations of
> > increasing and decreasing, such as:
> >   (a + b)  - c
> >   (a + b)  >> c
> >   (a * b)  - c
> >   (a * b)  >> c
> >   (a << b) - c
> >   (a << b) >> c
> > etc, etc.
> >
> > Some of these may not make sense (rarely used) but they are all (BOMK)
> > valid statements.  The verilog converter would have to restrict all of
> > these or handle all of them.  I don't know which is the best answer, yet.
>
> Implementing the restriction is probably easy to do: the right operand
> of certain operations (>>>, -) should be a plain name.
>
> I'm inclined to start with this solution. I guess most designers will
> find it acceptable.
>
> A fundamental solution would be easiest with a resize like in VHDL.
> Absent that, we would have to infer intermediate variables etc.,
> which would add all kinds of complexities. Probably not worth the
> effort at this point.
>
> Jan
>

Should we add this to the open task list (
http://www.myhdl.org/doku.php/dev:tasks)<http://www.myhdl.org/doku.php/dev:tasks>?
 As mentioned this is considered a bug because of the simulation mismatch.
 Think we have captured information on the issue.

Verilog will only use the largest "size" that exists in a expression.
 Intermediate results will only be as large as the largest declared reg /
wire.  This doesn't match how python handles the operations.

Since I have been following this issue, some, I can volunteer for this task.
 I just can't promise any fast results.

Chris

Re: [myhdl-list] arithmetic trouble

[Jan D. <ja...@ja...>]

Christopher Felton wrote:
> 
> 
> On Sat, May 16, 2009 at 2:16 AM, Jan Decaluwe <ja...@ja... 
> <mailto:ja...@ja...>> wrote:
> 
>     Christopher L. Felton wrote:
> 
>      > But the questions can be asked, since the operation is broken into
>      > intermediate steps, could the converter do this?  Could it
>     automagically
>      > break a complex operation into multiple steps?
> 
>     It could potentially do this, just as it now does resizes in VHDL.
>     Of course it may not worth the trouble.
> 
>      > I believe you would have to be careful here though.  You do not want
>      > complication or too much inference from the converter.  You would
>     want a
>      > very simple rule for Verilog that could be implemented.  There
>     are many
>      > scenarios where an intermediate result requires a larger bit-value.
>      > Basically anytime a complex operation (equation) has an
>     increasing and
>      > decreasing component you can run into this simulation mismatch.
>      If we
>      > prevent the operations we would have to prevent all combinations of
>      > increasing and decreasing, such as:
>      >   (a + b)  - c
>      >   (a + b)  >> c
>      >   (a * b)  - c
>      >   (a * b)  >> c
>      >   (a << b) - c
>      >   (a << b) >> c
>      > etc, etc.
>      >
>      > Some of these may not make sense (rarely used) but they are all
>     (BOMK)
>      > valid statements.  The verilog converter would have to restrict
>     all of
>      > these or handle all of them.  I don't know which is the best
>     answer, yet.
> 
>     Implementing the restriction is probably easy to do: the right operand
>     of certain operations (>>>, -) should be a plain name.
> 
>     I'm inclined to start with this solution. I guess most designers will
>     find it acceptable.
> 
>     A fundamental solution would be easiest with a resize like in VHDL.
>     Absent that, we would have to infer intermediate variables etc.,
>     which would add all kinds of complexities. Probably not worth the
>     effort at this point.
> 
>     Jan
> 
> 
> Should we add this to the open task list 
> (http://www.myhdl.org/doku.php/dev:tasks) 
> <http://www.myhdl.org/doku.php/dev:tasks>?  As mentioned this is 
> considered a bug because of the simulation mismatch.  Think we have 
> captured information on the issue.  
> 
> Verilog will only use the largest "size" that exists in a expression. 
>  Intermediate results will only be as large as the largest declared reg 
> / wire.  This doesn't match how python handles the operations.  
> 
> Since I have been following this issue, some, I can volunteer for this 
> task.  I just can't promise any fast results. 

Thanks for volunteering! However, after thinking further about it
I believe the problem points to a more fundamental flaw in the
way signedness and sizes are inferred in the Verilog convertor.
I think the VHDL convertor does it right, and it is also more
complex than the Verilog case. I think I need to put something
similar into the Verilog convertor to get it right for the
future. In short, this is not a local change but a major
rewrite - I guess I should clean up my own mess :-)

I think I jumped the original conclusions a little.
If Verilog doesn't have a resize, we can write one or even put
in sign extensions and castings directly. In this way, we can
solve the issues without temporary variables in the same way
as for VHDL conversion. Otherwise, the functionality of
VHDL and Verilog conversion would diverge.

This will take some time. Currently I'm working on solving
the most important remaining flaw in MyHDL: the fact that
sliced signals are not signals, and the problems this creates
occasionally. I think I have a good solution but I need to
work further on it and document it - stay tuned.

Jan


-- 
Jan Decaluwe - Resources bvba - http://www.jandecaluwe.com
    Python as a HDL: http://www.myhdl.org
    VHDL development, the modern way: http://www.sigasi.com
    Analog design automation: http://www.mephisto-da.com
    World-class digital design: http://www.easics.com

Re: [myhdl-list] arithmetic trouble

[Jan D. <ja...@ja...>]

Neal Becker wrote:


> 
> The problem is, it seems that (a * b) >>> 16 all in 1 step doesn't work 
> correctly.  I'm using cadence (version is 8.1?).  The simulator gives 
> strange results.  It seems to act as if it doesn't understand the bitwidth 
> of the intermediate result of (a*b), so that when shifted it's not correctly 
> handling the sign.
> 
> It works correctly if I break into 2 steps, where I use a tmp variable of 
> _the correct bit width_ before shifting.
> 
> Is this a common issue with verilog simulators, or is mine just broken?

Both are possible, though my guess is that your simulator works correctly
in terms of Verilog rules.

My guess is that we are being hit by Verilog's obscure rules for inferring
sizes and signedness. I would start by trying whether the bit width
of the left-hand side makes a difference. Perhaps the bit width of
the expression is reduced before the shift instead of after as it
"should" be.

> 
> Should my_hdl try to workaround this?

Yes - in the worst case it should refuse to convert shifts
of expressions and suggest to use a temporary variable instead.
Not ideal, but much better than simulation mismatches.

I have no time right now to investigate these issues,
I would appreciate if someone seeks this out systematically,
ideally with more than one Verilog simulator (cver and
icarus are free.)

Jan

-- 
Jan Decaluwe - Resources bvba - http://www.jandecaluwe.com
    Python as a HDL: http://www.myhdl.org
    VHDL development, the modern way: http://www.sigasi.com
    Analog design automation: http://www.mephisto-da.com
    World-class digital design: http://www.easics.com

Re: [myhdl-list] arithmetic trouble

[Felton C. <chr...@gm...>]

>
>
>>
>> Should my_hdl try to workaround this?
>
> Yes - in the worst case it should refuse to convert shifts
> of expressions and suggest to use a temporary variable instead.
> Not ideal, but much better than simulation mismatches.
>
> I have no time right now to investigate these issues,
> I would appreciate if someone seeks this out systematically,
> ideally with more than one Verilog simulator (cver and
> icarus are free.)
>
> Jan
>

Well this could be an interesting problem, doing a little searching on  
google found this quote from another newsgroup (take it with a grain  
of salt)

"""
In Verilog, the width of the result of a binary operation is the  
maximum width of the operands. In your case, each operand is 8 bits so  
the result of the multiplication will be 8 bits. When you add the two  
8-bit numbers, the result will also be 8 bits.
"""

That statement agrees with what I recall (without looking up the  
Verilog standard) and the empirical results from your simulation.  The  
quick fix is to extend the result or one of the operands bit-widths  
(or the two step approach).

For the MyHDL fix the same rules could be enforced.  This is somewhat  
related to another thread which the intbv math operators return an  
intbv instead of an int.  I don't have the insight / opinion right now  
if that would be the best approach.  Or to simply restrict shifting.

My time is severely limited right now as well.  If I find some free  
cycles I can try to methodically approach this issue.

Re: [myhdl-list] arithmetic trouble

[Felton C. <chr...@gm...>]

> if that would be the best approach.  Or to simply restrict shifting.
>
> My time is severely limited right now as well.  If I find some free
> cycles I can try to methodically approach this issue.


Ok, I am going to get in trouble for being late to work.  But here is  
a quick cver simulation.  Just posting as FYI and info for others if  
interested.  What it shows, is that the Verilog simulator (at least  
cver, ?? how consistent are other simulators) will use the largest bit- 
width in the assignment, left or right hand side.

This "rule" would be hard to duplicate (if even desired) in MyHDL  
because the math operation doesn't know about the left-hand side. Some  
more thought and investigation is needed but this information might be  
useful for now.

Results
Left hand side is 8-bit (c16 == right hand 16 bit result).
123 = 248 + 255 --   251(c16) --         251(int)
   0 = 248 * 255 --   247(c16) --         247(int)
124 = 249 + 255 --   252(c16) --         252(int)
   0 = 249 * 255 --   248(c16) --         248(int)
124 = 250 + 255 --   252(c16) --         252(int)
   0 = 250 * 255 --   249(c16) --         249(int)
125 = 251 + 255 --   253(c16) --         253(int)
   0 = 251 * 255 --   250(c16) --         250(int)
125 = 252 + 255 --   253(c16) --         253(int)
   0 = 252 * 255 --   251(c16) --         251(int)
126 = 253 + 255 --   254(c16) --         254(int)
   0 = 253 * 255 --   252(c16) --         252(int)
126 = 254 + 255 --   254(c16) --         254(int)
   0 = 254 * 255 --   253(c16) --         253(int)
127 = 255 + 255 --   255(c16) --         255(int)
   0 = 255 * 255 --   254(c16) --         254(int)

Left hand side is 8bit and 'a' (i.e. a + b) is 16 bit
251 = 255 + 255 --   251(c16) --         251(int)
247 = 255 * 255 --   247(c16) --         247(int)
252 = 255 + 255 --   252(c16) --         252(int)
248 = 255 * 255 --   248(c16) --         248(int)
252 = 255 + 255 --   252(c16) --         252(int)
249 = 255 * 255 --   249(c16) --         249(int)
253 = 255 + 255 --   253(c16) --         253(int)
250 = 255 * 255 --   250(c16) --         250(int)
253 = 255 + 255 --   253(c16) --         253(int)
251 = 255 * 255 --   251(c16) --         251(int)
254 = 255 + 255 --   254(c16) --         254(int)
252 = 255 * 255 --   252(c16) --         252(int)
254 = 255 + 255 --   254(c16) --         254(int)
253 = 255 * 255 --   253(c16) --         253(int)
255 = 255 + 255 --   255(c16) --         255(int)
254 = 255 * 255 --   254(c16) --         254(int)
0 simulation events and 0 declarative immediate assigns processed.
242 behavioral statements executed (1 procedural suspends).
   Times (in sec.):  Translate 0.0, load/optimize 0.1, simulation 0.1.
   There were 0 error(s), 0 warning(s), and 1 inform(s).
End of GPLCVER_2.12a at Thu May 14 09:38:00 2009 (elapsed 0.0 seconds).

Simple TestBench
module test;

    integer i,j,x;
    reg [7:0] c;
    reg [15:0] c16;
    reg [7:0] a, b;
    reg [15:0] a16, b16;

    initial begin
       // 8 bit operands
       for(i=248; i<256; i=i+1) begin
	 for(j=255; j<256; j=j+1) begin
	    a = i;
	    b = j;
	    c   = (a + b) >> 1;
	    c16 = (a + b) >> 1;
	    x   = (i + j) >> 1;
	    $display("%d = %d + %d -- %d(c16) -- %d(int) ", c, a, b, c16, x);
	    c   = (a * b) >> 8;
	    c16 = (a * b) >> 8;
	    x   = (i * j) >> 8;
	    $display("%d = %d * %d -- %d(c16) -- %d(int)", c, a, b, c16, x);
	 end
       end // for (i=248; i<256; i=i+1)

       // a = 16 bit operand
       for(i=248; i<256; i=i+1) begin
	 for(j=255; j<256; j=j+1) begin
	    a16 = i;
	    b = j;
	    c   = (a16 + b) >> 1;
	    c16 = (a16 + b) >> 1;
	    x   = (i + j) >> 1;
	    $display("%d = %d + %d -- %d(c16) -- %d(int) ", c, a, b, c16, x);
	    c   = (a16 * b) >> 8;
	    c16 = (a16 * b) >> 8;
	    x   = (i * j) >> 8;
	    $display("%d = %d * %d -- %d(c16) -- %d(int)", c, a, b, c16, x);
	 end
       end
    end


endmodule

Re: [myhdl-list] arithmetic trouble

[Jan D. <ja...@ja...>]

Christopher L. Felton wrote:

> But the questions can be asked, since the operation is broken into 
> intermediate steps, could the converter do this?  Could it automagically 
> break a complex operation into multiple steps? 

It could potentially do this, just as it now does resizes in VHDL.
Of course it may not worth the trouble.

> I believe you would have to be careful here though.  You do not want 
> complication or too much inference from the converter.  You would want a 
> very simple rule for Verilog that could be implemented.  There are many 
> scenarios where an intermediate result requires a larger bit-value.  
> Basically anytime a complex operation (equation) has an increasing and 
> decreasing component you can run into this simulation mismatch.  If we 
> prevent the operations we would have to prevent all combinations of 
> increasing and decreasing, such as:
>   (a + b)  - c
>   (a + b)  >> c
>   (a * b)  - c
>   (a * b)  >> c
>   (a << b) - c
>   (a << b) >> c
> etc, etc.
> 
> Some of these may not make sense (rarely used) but they are all (BOMK) 
> valid statements.  The verilog converter would have to restrict all of 
> these or handle all of them.  I don't know which is the best answer, yet.

Implementing the restriction is probably easy to do: the right operand
of certain operations (>>>, -) should be a plain name.

I'm inclined to start with this solution. I guess most designers will
find it acceptable.

A fundamental solution would be easiest with a resize like in VHDL.
Absent that, we would have to infer intermediate variables etc.,
which would add all kinds of complexities. Probably not worth the
effort at this point.

Jan

-- 
Jan Decaluwe - Resources bvba - http://www.jandecaluwe.com
    Python as a HDL: http://www.myhdl.org
    VHDL development, the modern way: http://www.sigasi.com
    Analog design automation: http://www.mephisto-da.com
    World-class digital design: http://www.easics.com