Faster RTLIL Parser

Developers
1

For some of my work I’m loading very large designs in .rtlil format. One multi-GB file I have takes 76s in read_rtlil. I looked at some profiles and there’s a fair bit of headroom. For example there’s a strdup() for most tokens, everything is char* so we don’t know the lengths of strings, and generally there’s lots of copying. Part of the problem is just using Flex/Bison — they are pretty C-centric and generally difficult to work with. In particular for strings, constants and IDs we have to lex them in one pass and then parse+convert them in a separate pass, which is inherently slow.

So as an experiment I hacked together a new parser from scratch — handwritten recursive descent with integrated lexing and parsing.

With a few performance tweaks, including a few (compatible) changes to RTLIL APIs, I got my multi-GB file down to 30s in read_rtlil_fast (2.5x). The profile is pretty clean now; over 50% is just hashing (and rehashing) strings for the IdString table. End-to-end read+dump of jpeg.synth.il goes from 84ms to 63ms (less of a speedup because it includes Yosys startup and dump).

The overall LoC is about the same as the current parser. It’s a little less readable because we don’t have the grammar as nicely expressed, but I find this style of parser actually a lot easier to understand and debug overall, because it’s just code that any C++ programmer can understand, especially if you’re not already familiar with Flex/Bison.

I’m not sure how important RTLIL parsing performance is in practice and this change might be a bit scary, so I’m not sure how to proceed. I can clean this up and submit a PR that either keeps it as a separate read_rtlil_fast command or replaces read_rtlil. Otherwise I can just use use it locally. Let me know!

(Note that it’s not really tested and probably has some bugs; obviously I’d address that.)

2 Likes
2

I think RTLIL parsing performance can be significant for some real world workflows (I’m primarily thinking of some FV flows). That is in addition to removing friction from debugging and development, so overall I’d say it’s a change worth making.

Personally I am also not too concerned about the readability of the recursive descent parser, I agree with you about the ease of debugging, the RTLIL grammar isn’t too complicated in the first place and we also have a description of it in our documentation RTLIL text representation - YosysHQ Yosys 0.57-dev documentation (however, this would be a good time to double check that there are no known discrepancies between the two parsers and these docs).

I also wouldn’t mind replacing the current read_rtlil with the new parser after it has been sufficiently tested. Most important, but also easiest to test is that it parses everything that write_rtlil produces. An important external producer of RTLIL is Amaranth, so before replacing the default parser we should also make sure that we have no bugs for the RTLIL it produces (see expected RTLIL output from Amaranth’s testsuite and the code for its RTLIL backend).

Since this would be a replacing a component with a functionally equivalent one and that component has a relatively small and well defined interface, I think this is actually one of the less scarier changes to make to core parts of yosys.

I don’t have a strong opinion on whether we should merge it as an alternative read_rtlil_fast command before we’re confident that we can replace the current read_rtlil or wait with merging until we’re ready for that. It would be nice to avoid adding a command that will turn into a deprecated alias after replacing the current parser, but having both around for some time might make testing easier.

3

Sure. Here are some discrepancies between the parser and the docs. Except where noted, I have kept compatilibility with the existing parser. If you want to tighten the behaviour of the parser, that should be done in a separate PR for ease of detecting regressions.

The docs say “An eol is one or more consecutive ASCII newlines (10) and carriage returns (13).”. But the parser only accepts ASCII newline (10).

The docs say an identifier is $ or \ followed by one or more of “any character whose encoding consists solely of bytes above ASCII space (32)”. The parser accepts any characters other than space, \n, \r and \t.

The docs say “Within a string, any character except ASCII NUL (0) may be used.” The current parser doesn’t enforce this… actually it’s just buggy and will truncate the string at the first null. The rest of the string just disappears and parsing carries on. I’ll update the new parser to reject this explicitly because copying the current parser’s behavior here would make me feel sick.

The current parser accepts autoidx anywhere, but the docs say it has to be at the start of the file.

The docs don’t allow for module-level connect statements, which are clearly allowed, so I’ll update the docs for that.

The parser allows attribute statements before a parameter statement, which seems like a bug and is not allowed in the docs. They just carry over to the next module body statement.

The parser allows assign and switch to occur in any order within a process. The docs require assigns to come first.

The docs say that each <case> can have its own attributes, but the parser only allows the first <case> to have attributes. This seems like a bug in the parser. I’ve fixed it in my parser, since there’s no compatiblity issue.

Relatedly, if a <switch> has no <case> the parser will allow attributes declared in the <switch> body to leak out. This seems like a bug. I’ve kept that bug in my parser in case it matters for compatiblity.

The parser doesn’t do anything to stop trailing attributes declared in <case-body> from leaking out. Seems like a bug but I’ll keep it for compatibility.

memwr updates are undocumented. I’ll fix that.

2 Likes
4

Filed Rewrite the RTLIL parser for efficiency by rocallahan · Pull Request #5339 · YosysHQ/yosys · GitHub.

5

Re: the ordering of assigns and switches; this was adjusted in read_rtlil: Warn on assigns after switches in case rules by georgerennie · Pull Request #4765 · YosysHQ/yosys · GitHub . I haven’t actually looked at the code, but from the discussion in that issue it seems like while the (current) parser accepts interspersed assigns and switches, it treats them as though all the assigns came before the switches. The docs are written to reflect the intended behaviour of assigns first even though it’s not (currently) strictly enforced. It seems like the intention was to strictly enforce it, but that doing so would be a breaking change and so was avoided. I think it makes sense to enforce that if we (you) are rewriting the parser.

6

I would prefer to keep the new parser’s behavior as similar as possible to the old parser and make any potentially incompatible behavior changes in separate PRs. That way, if there is a regression, it will be easy to figure out which change is responsible and revert it if necessary.

7

I would prefer to keep the new parser’s behavior as similar as possible to the old parser and make any potentially incompatible behavior changes in separate PRs. That way, if there is a regression, it will be easy to figure out which change is responsible and revert it if necessary.

Fair enough!