Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Support finitely recursive modules #659

Closed
veripoolbot opened this issue Jun 24, 2013 · 9 comments
Closed

Support finitely recursive modules #659

veripoolbot opened this issue Jun 24, 2013 · 9 comments

Comments

@veripoolbot
Copy link

@veripoolbot veripoolbot commented Jun 24, 2013


Author Name: Sean Moore
Original Redmine Issue: 659 from https://www.veripool.org


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.

@veripoolbot

This comment has been minimized.

Copy link
Author

@veripoolbot veripoolbot commented Jun 24, 2013


Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2013-06-24T02:43:46Z


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.

@veripoolbot

This comment has been minimized.

Copy link
Author

@veripoolbot veripoolbot commented Apr 22, 2014


Original Redmine Comment
Author Name: Igor Lesik
Original Date: 2014-04-22T23:36:49Z


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.

@veripoolbot

This comment has been minimized.

Copy link
Author

@veripoolbot veripoolbot commented Apr 23, 2014


Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2014-04-23T01:44:14Z


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.

@veripoolbot

This comment has been minimized.

Copy link
Author

@veripoolbot veripoolbot commented Apr 23, 2014


Original Redmine Comment
Author Name: Igor Lesik
Original Date: 2014-04-23T19:26:31Z


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.

@veripoolbot

This comment has been minimized.

Copy link
Author

@veripoolbot veripoolbot commented Apr 24, 2014


Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2014-04-24T23:32:57Z


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

@veripoolbot

This comment has been minimized.

Copy link
Author

@veripoolbot veripoolbot commented Apr 26, 2017


Original Redmine Comment
Author Name: Udi Finkelstein
Original Date: 2017-04-26T14:22:46Z


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 :-(

@veripoolbot

This comment has been minimized.

Copy link
Author

@veripoolbot veripoolbot commented Apr 29, 2017


Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2017-04-29T11:47:35Z


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

@veripoolbot

This comment has been minimized.

Copy link
Author

@veripoolbot veripoolbot commented Nov 18, 2017


Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2017-11-18T22:43:50Z


(Finally) fixed in git towards 3.915.

@veripoolbot

This comment has been minimized.

Copy link
Author

@veripoolbot veripoolbot commented Nov 25, 2017


Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2017-11-25T20:48:21Z


In 3.916.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
1 participant
You can’t perform that action at this time.