Major Tools
Other Tools
General Info

Issue #659

Support finitely recursive modules

Added by Sean Moore over 5 years ago. Updated about 1 year ago.

% Done:



I'm getting an error thrown when trying to create recursively instantiated modules in Verilog.

-Info-Loop: 0x92f9f40 VERTEX=PriorityChoice r2 -Info-Loop: 0x92f9f40 VERTEX=PriorityChoice r2 %Error: PriorityEncoder.v:9: Recursive module (module instantiates itself): PriorityChoice %Error: Exiting due to 1 error(s) %Error: Command Failed /usr/bin/verilator_bin --cc PriorityEncoder.v

I would expect it to fail for modules with non-terminating instantiation (or one which passes some settable threshold due to the halting problem). I've included a test which fails in Verilator but passes in Icarus Verilog.

PriorityEncoder.v - Converts one-hot encoding to binary (1.48 KB) Sean Moore, 06/24/2013 01:45 AM


#1 Updated by Wilson Snyder over 5 years ago

  • Category set to Unsupported
  • Status changed from New to Feature

Interesting, first time I've seen this sort of recursion used for something that isn't just completely silly.

To Verilator this is circular as unfortunately Verilator does several processing steps before the generates are resolved; someday this will be fixed, but this is not a minor undertaking and is unlikely to be within 2013, sorry.

I added the test to the suite marked as unsupported so it isn't lost.

#2 Updated by Igor Lesik over 4 years ago

Is it possible to bump priority of this issue? I failed to use Verilator just because of this feature; in a project I tried to compile with Verilator all floating point (FPU) code is written using recursion.

#3 Updated by Wilson Snyder over 4 years ago

Oh, "feature" just means adding support for something that isn't supported now, as opposed to something broken that was thought to work; there's no argument this is a bug. :)

Unfortunately this changes fundamental assumptions, and there are simply other bugs which are blocking more projects. If you have significant time to invest in fixing this, we'd be very glad to have the help.

#4 Updated by Igor Lesik over 4 years ago

I can trace where check for recursion is made inside GraphAlgRank::vertexIterate, but then it is getting harder to understand fundamental assumptions from the code.

May be you can outline here main steps along with references to the code as a guideline for a person who will undertake this work.

#5 Updated by Wilson Snyder over 4 years ago

At present, verilator sorts the modules from top to bottom (modSortByLevel()) as the later stages require that ordering. In addition the visit routines assume that a module is not re-entered when processing (which is violated by loops). Also any userp()'s that are attached to a module assume that module is not referenced again. V3LinkCells, V3LinkParse, V3LinkDot, V3LinkResolve, V3LinkLValue, V3LinkJump, V3Param now mostly but not completely work on the entire netlist, e.g. all modules are LinkCell'ed, then all modules are LinkParsed, then all are LinkDot'ed, etc... This whole netlist assumption does not work with recursion as recursion is only broken by doing parameterization.

The new algorithm is to do these steps module by module top-to-bottom; which is what the 'design' of the more recent SystemVerilog unfortunately assumes. This solves the problem because the first hit of the recursive module will elaborate (parameterize) which will result in a different version of (what verilator now thinks it a duplicate) recursive module, therefore it really is no longer recursive, and it will all work.

In brief:

  • A first step would be to make V3LinkParse/LinkResolve/LinkLValue/LinkJump clean when working on a single module at once; for example making sure there is no cross-module state by adding user*ClearTree() as each module is iterated.
  • Code from V3LinkCells, V3LinkParse, V3LinkDot, V3LinkResolve, V3LinkLValue, V3LinkJump, V3Param which now mostly work sequentially change to work all on each module, then proceed to the next module. Say this is called V3LinkAll. It would take the highest level module, call what is now a "part" of LinkParse...LinkParam on just that one module, then if needed read in any sub-modules (what V3LinkCells does now), then proceed recursively to the child modules.

This also fixes an outstanding bug related to parsing modules that do not need to really exist due to being "generate if'ed out".

#6 Updated by Udi Finkelstein over 1 year ago

Any news regarding this? I'm trying to write a finitely-recursive tree adder. I first tried this by inputting a wide input vector (N words * W bits) and doing two nested generate loops, the outer being 0 to log2(N)-1 and the inner instantiating a series of two-input W-bit adders. Data is shared data via a common vector. I also handle vector expansion correctly, adding 1 more bit on each stage. I used a temporary wire array with N-1 entries (N/2 for 1st layer, N/4 for 2nd layer, N8/ for 3rd layer, ... 1 entry for last layer). This failed because verilator warned about circular logic (which was not the case), since the vector was hooked to both the inputs and outputs of the adder, even though the indexes were statically generated by the genvars, and different.

I then tried rewriting this as a recursive module, but this also fails due to the bug above :-(

#7 Updated by Wilson Snyder over 1 year ago

Sorry, I don't have any progress on this. You can of course disable the UNOPTFLAT warning.

#8 Updated by Wilson Snyder about 1 year ago

  • Status changed from Feature to Resolved

(Finally) fixed in git towards 3.915.

#9 Updated by Wilson Snyder about 1 year ago

  • Status changed from Resolved to Closed

In 3.916.

Also available in: Atom