[pseudo] Check follow-sets instead of tying reduce actions to lookahead tokens.
authorSam McCall <sam.mccall@gmail.com>
Thu, 23 Jun 2022 21:55:41 +0000 (23:55 +0200)
committerSam McCall <sam.mccall@gmail.com>
Mon, 27 Jun 2022 22:36:16 +0000 (00:36 +0200)
commit85eaecbe8e541924b6f87dd83f169056e74ce237
tree0866b767347e4617678c70623bb2cb53d3757dbe
parentc1b07d617705dfdb3aabbdda51c1a40d99f7cc1a
[pseudo] Check follow-sets instead of tying reduce actions to lookahead tokens.

Previously, the action table stores a reduce action for each lookahead
token it should allow. These tokens are the followSet(action.rule.target).

In practice, the follow sets are large, so we spend a bunch of time binary
searching around all these essentially-duplicates to check whether our lookahead
token is there.
However the number of reduces for a given state is very small, so we're
much better off linear scanning over them and performing a fast check for each.

D128318 was an attempt at this, storing a bitmap for each reduce.
However it's even more compact just to use the follow sets directly, as
there are fewer nonterminals than (state, rule) pairs. It's also faster.

This specialized approach means unbundling Reduce from other actions in
LRTable, so it's no longer useful to support it in Action. I suspect
Action will soon go away, as we store each kind of action separately.

This improves glrParse speed by 42% (3.30 -> 4.69 MB/s).
It also reduces LR table size by 59% (343 -> 142kB).

Differential Revision: https://reviews.llvm.org/D128472
clang-tools-extra/pseudo/include/clang-pseudo/grammar/LRTable.h
clang-tools-extra/pseudo/lib/GLR.cpp
clang-tools-extra/pseudo/lib/grammar/LRTable.cpp
clang-tools-extra/pseudo/lib/grammar/LRTableBuild.cpp
clang-tools-extra/pseudo/test/lr-build-basic.test
clang-tools-extra/pseudo/test/lr-build-conflicts.test
clang-tools-extra/pseudo/unittests/GLRTest.cpp
clang-tools-extra/pseudo/unittests/LRTableTest.cpp