Efficiency of verinum and vpp_net pow() functions

[cliffordwolf]

Modules such as

module test(y);
  output [5:0] y;
  assign y = 6'd3 ** 123456789;
endmodule

take forever to compile because the verinum pow() function is actually using a loop to evaluate the power:

  for (long idx = 1 ;  idx < pow_count ;  idx += 1)
        result = result * left;

(For exponents that do not fit into a long long this would also return incorrect values, but I think no-one would wait for such a case to finish compiling..)

This should of course be instead calculated using a Power-Modulus Algorithm. See the const_pow() function in Yosys for an example implementation.

The vvp_net pow() function seems to implement a power-modulus algorithm but nevertheless the following code snippet hangs vvp:

module test(a, y);
  input [5:0] a;
  output [5:0] y;
  assign a = 3;
  assign y = a ** 123456789;
endmodule

PS: the examples above should evaluate to

assign y = 6'b110011;

[martinwhitaker]

I've just pushed fixes for these two issues to the git master branch. Note that you will still get long run times if you use an unsized value as the left operand, as Icarus Verilog treats unsized values as having effectively infinite width. You can defeat this by using the gstrict-expr-width compiler option.

[cliffordwolf]

Thanks for all the fixes these last days. Awesome work! I've now also updated the list on my webpage:

http://www.clifford.at/yosys/vloghammer.html

I still have tests that fail. Essentially they are cases that have constructs like the following that temporarily allocate 16 GB of memory (VlogHammer only allows for 1 GB of memory for running the simple test cases):

module test;
  localparam [4:0] p = 1'b1 << ~30'b0;
endmodule

I think it does not make sense to file a new issue as this is related to what you have posted above (unsigned values having an infinite number of bits). Of course according to the verilog standard this is a 5 bit operation and there is no need for infinite width values as all verilog operations are handled in a pre-determined bit width. Are there any plans for fixing this?

Afaics this is the only thing that stops icarus verilog from passing the VlogHammer test suite. (The only other tools I have seen so far that pass it are Yosys (of course) and Modelsim. I've also found bugs in synopsys design compiler and cadance conformal, but they are not on the website yet.)

Btw: the following even triggers an assert: ivl: verinum.cc:370: verinum::V verinum::set(unsigned int, verinum::V): Assertion 'idx < nbits_' failed.

module test;
  localparam [4:0] p = 1'b1 << ~40'b0;
endmodule

[martinwhitaker]

No, it's unsized literals that are treated as having infinite width, not unsigned literals. So the examples you give above should not cause a problem. However, the operators in the verinum class do not follow the sized rules and expand the result vectors to give lossless operations (my recent changes to the power operator make it an exception to this). This is a design decision made by Steve, so he will have to rule on whether or not we fix it.

[cliffordwolf]

Ah, unsized literals. I should read more carefully. ;)

Yeah, they are not standardized very well. Afair IEEE Std 1365-2005 only says that they must be at least 32 bits. In Yosys they are max(32 bits, bits specified in literal). But that is a decision that is made in the front-end when parsing the literal. After that it behaves the same as if the literal would have been specified with that bit width. I guess that is pretty much what iverilog does when called with -gstrict-expr-width.

[martinwhitaker]

Yes, the IEEE standard is not very clear on the subject of unsized literals. If you're interested, there is some useful clarification at http://www.eda.org/sv-bc/hm/11350.html. The Icarus behaviour is documented at http://iverilog.wikia.com/wiki/Verilog_Portability_Notes.

BTW, thanks for the bug reports. It's always good to get feedback, and having nice simple test cases is a real bonus!

[cliffordwolf]

Thanks for the links. That gave me some additional confidence that the way Yosys handles unsized literals is fine.

I'll certainly keep the bug reports coming. Right now it looks like the issue with << I posted above is the only one left. But I still have to make a full run with ~2000 test cases. I am probably going to extend the range of the test cases soon and I guess I will find new oddities then.

On a funny note: icarus verilog prints "0" for $display("%b", ^(-1));. So this is an infinite but even number of bits then? ;)

[martinwhitaker]

"Effectively infinite" is my shorthand for what Icarus does, which is rather more complicated :-( The basic rules are: internally use the minimum number of bits necessary to represent the value; externally behave as at least 32 bits but expand to allow any expression containing an unsized literal to evaluate losslessly. Your example is being treated as if it was 32 bits, as there is nothing to cause the expression width to grow any further.

FWIW, I think your approach with Yosys is the sensible one. I certainly wouldn't recommend anyone follow the Icarus route.

[cliffordwolf]

I've now reported the "shift with large rhs" bug in a separate issue (#13), just so I have something to reference in the vloghammer documentation and and so we do not discuss this in the comments to another issue.

I've also found yet another bug (issue #14) in my full run of VlogHammer.