Changes in LRTableTest.cpp

9fbf1107 - [pseudo] Eliminate LRTable::Action. NFC

Mon, 04 Jul 2022 18:35:40 +0000

[pseudo] Eliminate LRTable::Action. NFCThe last remaining uses are in tests/test builders.Replace with a builder struct.Differential Revision: https://reviews.llvm.org/D129093 List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/unittests/LRTableTest.cpp

b37dafd5 - [pseudo] Store shift and goto actions in a compact structure with faster lookup.

Fri, 24 Jun 2022 01:01:45 +0000

[pseudo] Store shift and goto actions in a compact structure with faster lookup.The actions table is very compact but the binary search to find thecorrect action is relatively expensive.A hashtable is faster but pretty large (64 bits per value, plus emptyslots, and lookup is constant time but not trivial due to collisions).The structure in this patch uses 1.25 bits per entry (whether present or absent)plus the size of the values, and lookup is trivial.The Shift table is 119KB = 27KB values + 92KB keys.The Goto table is 86KB = 30KB values + 57KB keys.(Goto has a smaller keyspace as #nonterminals < #terminals, and more entries).This patch improves glrParse speed by 28%: 4.69 => 5.99 MB/sOverall the table grows by 60%: 142 => 228KB.By comparison, DenseMap is "only" 16% faster (5.43 MB/s),and results in a 285% larger table (547 KB) vs the baseline.Differential Revision: https://reviews.llvm.org/D128485 List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/unittests/LRTableTest.cpp

3f028c02 - [pseudo] Grammar::parseBNF returns Grammar not unique_ptr. NFC

Tue, 28 Jun 2022 14:24:38 +0000

[pseudo] Grammar::parseBNF returns Grammar not unique_ptr. NFC List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/unittests/LRTableTest.cpp

85eaecbe - [pseudo] Check follow-sets instead of tying reduce actions to lookahead tokens.

Thu, 23 Jun 2022 21:55:41 +0000

[pseudo] Check follow-sets instead of tying reduce actions to lookahead tokens.Previously, the action table stores a reduce action for each lookaheadtoken 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 binarysearching around all these essentially-duplicates to check whether our lookaheadtoken is there.However the number of reduces for a given state is very small, so we'remuch 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, asthere are fewer nonterminals than (state, rule) pairs. It's also faster.This specialized approach means unbundling Reduce from other actions inLRTable, so it's no longer useful to support it in Action. I suspectAction 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 List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/unittests/LRTableTest.cpp

c70aeaad - [pseudo] Move grammar-related headers to a separate dir, NFC.

Thu, 09 Jun 2022 10:16:14 +0000

[pseudo] Move grammar-related headers to a separate dir, NFC.We did that for .cpp, but forgot the headers.Differential Revision: https://reviews.llvm.org/D127388 List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/unittests/LRTableTest.cpp

7a05942d - [pseudo] Remove the explicit Accept actions.

Wed, 08 Jun 2022 11:26:53 +0000

[pseudo] Remove the explicit Accept actions.As pointed out in the previous review section, having a dedicated acceptaction doesn't seem to be necessary. This patch implements the the same behaviorwithout accept acction, which will save some code complexity.Reviewed By: sammccallDifferential Revision: https://reviews.llvm.org/D125677 List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/unittests/LRTableTest.cpp

89cd86bb - Reapply [pseudo] Move pseudoparser from clang to clang-tools-extra"

Wed, 16 Mar 2022 00:08:02 +0000

Reapply [pseudo] Move pseudoparser from clang to clang-tools-extra"This reverts commit 049f4e4eab19c6e468e029232e94ca71245b0f56.The problem was a stray dependency in CLANG_TEST_DEPS which caused cmaketo fail if clang-pseudo wasn't built. This is now removed. List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/unittests/LRTableTest.cpp

b97856c4 - [pseudo] Move pseudoparser from clang to clang-tools-extra

Tue, 08 Mar 2022 18:31:32 +0000

[pseudo] Move pseudoparser from clang to clang-tools-extraThis should make clearer that: - it's not part of clang proper - there's no expectation to update it along with clang (beyond green tests) - clang should not depend on itThis is intended to be expose a library, so unlike other tools has a splitbetween include/ and lib/.The main renames are: clang/lib/Tooling/Syntax/Pseudo/* => clang-tools-extra/pseudo/lib/* clang/include/clang/Tooling/Syntax/Pseudo/* => clang-tools-extra/pseudo/include/clang-pseudo/* clang/tools/clang/pseudo/* => clang-tools-extra/pseudo/tool/* clang/test/Syntax/* => clang-tools-extra/pseudo/test/* clang/unittests/Tooling/Syntax/Pseudo/* => clang-tools-extra/pseudo/unittests/* #include "clang/Tooling/Syntax/Pseudo/*" => #include "clang-pseudo/*" namespace clang::syntax::pseudo => namespace clang::pseudo check-clang => check-clang-pseudo clangToolingSyntaxPseudo => clangPseudoThe clang-pseudo and ClangPseudoTests binaries are not renamed.See discussion around:https://discourse.llvm.org/t/rfc-a-c-pseudo-parser-for-tooling/59217/50Differential Revision: https://reviews.llvm.org/D121233 List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/unittests/LRTableTest.cpp