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

Jump to bottom

Bad scaling, if there are nasty forests of generate statements #1314

Open
veripoolbot opened this issue May 31, 2018 · 2 comments
Open

Bad scaling, if there are nasty forests of generate statements #1314

veripoolbot opened this issue May 31, 2018 · 2 comments
Assignees
@jcoiner
Labels
area: performance Issue involves performance issues effort: days Expect this issue to require roughly days of invested effort to resolve

Comments

@veripoolbot
Copy link
Contributor

Author Name: John Coiner (@jcoiner)
Original Redmine Issue: 1314 from https://www.veripool.org

Original Assignee: John Coiner (@jcoiner)

This patch adds two tests:

One is a tree of modules, defined recursively, each of which contains a generate statement with several leaves. Each leaf has a submodule, and only one of the leaves should ever be active at a time. So each module really only has one submodule, post-generate, and the module hierarchy is a simple vine. This test passes.

The other is a tree of modules, defined non-recursively. Otherwise it's very similar. This causes verilator to spin and consume all memory on the host. The reason is, it doesn't appear that verilator can prune its analysis to only the active leaves of the generate statement, instead it fans out exponentially across unreachable generate paths.

I was a little surprised that the basic case is broken, while the "tricky" case of a recursive module works well. I'm also a little surprised that verilator handles recursive modules as a special case internally. I'll dive in and see if it's possible to clean that up and get to a single general case that passes both tests...
@veripoolbot
Copy link
Contributor Author

Original Redmine Comment
Author Name: John Coiner (@jcoiner)
Original Date: 2018-05-31T21:12:31Z

Here's the patch with the tests. It should apply to the develop-v4 branch.

The exponential search explosion happens very early, in V3LinkDot. V3LinkDot also has special cases to delay its resolution of recursive cell instances. That's not called for by the IEEE standard, is it? Assuming this special case handling isn't required by the standard, maybe we can avoid the special cases. I'll look into it.

@veripoolbot
Copy link
Contributor Author

Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2018-05-31T23:25:23Z

The diffs had only a V3Ast dynamic cast fix (which shouldn't go into master and is already fixed in develop-v4).

The handling of generates is currently unfortunately handled very late after much linking, ideally it should be much closer to the parser, as the present approach this causes the recursion and other minor problems and a lot of V3LinkDot mess, but to fix this is beyond the pain I'd like to suffer to fix; we can discuss how to approach that if you're interested.

That general problem said, the fix for this exact failure keeping the existing framework probably is relatively small.

@veripoolbot veripoolbot added area: performance Issue involves performance issues effort: days Expect this issue to require roughly days of invested effort to resolve labels Dec 22, 2019
@wsnyder wsnyder mentioned this issue Oct 26, 2023
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@jcoiner jcoiner

Labels
area: performance Issue involves performance issues effort: days Expect this issue to require roughly days of invested effort to resolve
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@jcoiner @veripoolbot