Changes in LRTableBuild.cpp

aba43035 - Use llvm::sort instead of std::sort where possible

Sat, 23 Jul 2022 13:14:14 +0000

Use llvm::sort instead of std::sort where possiblellvm::sort is beneficial even when we use the iterator-based overload,since it can optionally shuffle the elements (to detectnon-determinism). However llvm::sort is not usable everywhere, forexample, in compiler-rt.Reviewed By: nhaehnleDifferential Revision: https://reviews.llvm.org/D130406 List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/grammar/LRTableBuild.cpp

31211674 - [pseudo] Add error-recovery framework & brace-based recovery

Wed, 29 Jun 2022 11:48:00 +0000

[pseudo] Add error-recovery framework & brace-based recoveryThe idea is:- a parse failure is detected when all heads die when trying to shift the next token- we can recover by choosing a nonterminal we're partway through parsing, and determining where it ends through nonlocal means (e.g. matching brackets)- we can find candidates by walking up the stack from the (ex-)heads- the token range is defined using heuristics attached to grammar rules- the unparsed region is represented in the forest by an Opaque nodeThis patch has the core GLR functionality.It does not allow recovery heuristics to be attached as extensions tothe grammar, but rather infers a brace-based heuristic.Expected followups:- make recovery heuristics grammar extensions (depends on D127448)- add recovery to our grammar for bracketed constructs and sequence nodes- change the structure of our augmented `_ := start` rules to eliminate some special-cases in glrParse.- (if I can work out how): avoid some spurious recovery cases described in comments(Previously mistakenly committed as a0f4c10ae227a62c2a63611e64eba83f0ff0f577)Differential Revision: https://reviews.llvm.org/D128486 List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/grammar/LRTableBuild.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/lib/grammar/LRTableBuild.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/lib/grammar/LRTableBuild.cpp

743971fa - Revert "[pseudo] Add error-recovery framework & brace-based recovery"

Tue, 28 Jun 2022 19:09:15 +0000

Revert "[pseudo] Add error-recovery framework & brace-based recovery"This reverts commit a0f4c10ae227a62c2a63611e64eba83f0ff0f577.This commit hadn't been reviewed yet, and was unintentionally includedon another branch. List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/grammar/LRTableBuild.cpp

a0f4c10a - [pseudo] Add error-recovery framework & brace-based recovery

Wed, 08 Jun 2022 21:27:23 +0000

[pseudo] Add error-recovery framework & brace-based recoveryThe idea is: - a parse failure is detected when all heads die when trying to shift the next token - we can recover by choosing a nonterminal we're partway through parsing, and determining where it ends through nonlocal means (e.g. matching brackets) - we can find candidates by walking up the stack from the (ex-)heads - the token range is defined using heuristics attached to grammar rules - the unparsed region is represented in the forest by an Opaque nodeThis patch has the core GLR functionality.It does not allow recovery heuristics to be attached as extensions tothe grammar, but rather infers a brace-based heuristic.Expected followups: - make recovery heuristics grammar extensions (depends on D127448) - add recover to our grammar for bracketed constructs and sequence nodes - change the structure of our augmented `_ := start` rules to eliminate some special-cases in glrParse. - (if I can work out how): avoid some spurious recovery cases described in comments - grammar changes to eliminate the hard distinction between init-list and designated-init-list shown in the recovery-init-list.cpp testcaseDifferential Revision: https://reviews.llvm.org/D128486 List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/grammar/LRTableBuild.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/lib/grammar/LRTableBuild.cpp

b70ee9d9 - Reland "[pseudo] Track heads as GSS nodes, rather than as "pending actions"."

Thu, 23 Jun 2022 16:16:49 +0000

Reland "[pseudo] Track heads as GSS nodes, rather than as "pending actions"."This reverts commit 2c80b5319870b57fbdbb6c9cef9c86c26c65371d.Fixes LRTable::buildForTest to create states that are referenced buthave no actions. List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/grammar/LRTableBuild.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/lib/grammar/LRTableBuild.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/lib/grammar/LRTableBuild.cpp

93bcff8a - [pseudo] Invert rows/columns of LRTable storage for speedup. NFC

Fri, 03 Jun 2022 21:48:41 +0000

[pseudo] Invert rows/columns of LRTable storage for speedup. NFCThere are more states than symbols.This means first partioning the action list by state leaves us with a smallerrange to binary search over. This improves find() a lot and glrParse() by 7%.The tradeoff is storing more smaller ranges increases the size of the offsetsarray, overall grammar memory is +1% (337->340KB).Before:glrParse 188795975 ns 188778003 ns 77 bytes_per_second=1.98068M/sAfter:glrParse 175936203 ns 175916873 ns 81 bytes_per_second=2.12548M/sDifferential Revision: https://reviews.llvm.org/D127006 List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/grammar/LRTableBuild.cpp

cd2292ef - [pseudo] A basic implementation of compiling cxx grammar at build time.

Tue, 24 May 2022 18:21:45 +0000

[pseudo] A basic implementation of compiling cxx grammar at build time.The main idea is to compile the cxx grammar at build time, and constructthe core pieces (Grammar, LRTable) of the pseudoparse based on the compileddata sources.This is a tiny implementation, which is good for start:- defines how the public API should look like;- integrates the cxx grammar compilation workflow with the cmake system.- onlynonterminal symbols of the C++ grammar are compiled, anything else are still doing the real compilation work at runtime, we can opt-in more bits in the future;- splits the monolithic clangPsuedo library for better layering;Reviewed By: sammccallDifferential Revision: https://reviews.llvm.org/D125667 List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/grammar/LRTableBuild.cpp