Changes in GLR.cpp

07b7ff98 - [pseudo] Allow opaque nodes to represent terminals

Tue, 26 Jul 2022 07:03:02 +0000

[pseudo] Allow opaque nodes to represent terminalsThis allows incomplete code such as `namespace foo {` to be modeled as anormal sequence with the missing } represented by an empty opaque node.Differential Revision: https://reviews.llvm.org/D130551 List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/GLR.cpp

2a88fb2e - [pseudo] Eliminate the dangling-else syntax ambiguity.

Thu, 21 Jul 2022 08:18:33 +0000

[pseudo] Eliminate the dangling-else syntax ambiguity.- the grammar ambiguity is eliminated by a guard;- modify the guard function signatures, now all parameters are folded in to a single object, avoid a long parameter list (as we will add more parameters in the near future);Reviewed By: sammccallDifferential Revision: https://reviews.llvm.org/D130160 List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/GLR.cpp

3132e9cd - [pseudo] Key guards by RuleID, add guards to literals (and 0).

Tue, 19 Jul 2022 08:54:52 +0000

[pseudo] Key guards by RuleID, add guards to literals (and 0).After this, NUMERIC_CONSTANT and strings should parse only one way.There are 8 types of literals, and 24 valid (literal, TokenKind) pairs.This means adding 8 new named guards (or 24, if we want to assert the token).It seems fairly clear to me at this point that the guard names are unneccesaryindirection: the guards are in fact coupled to the rule signature.(Also add the zero guard I forgot in the previous patch.)Differential Revision: https://reviews.llvm.org/D130066 List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/GLR.cpp

53daa177 - [clang, clang-tools-extra] Use has_value instead of hasValue (NFC)

Wed, 13 Jul 2022 05:47:41 +0000

[clang, clang-tools-extra] Use has_value instead of hasValue (NFC) List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/GLR.cpp

7d8e2742 - [pseudo] Define recovery strategy as grammar extension.

Tue, 05 Jul 2022 20:14:52 +0000

[pseudo] Define recovery strategy as grammar extension.Differential Revision: https://reviews.llvm.org/D129158 List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/GLR.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/GLR.cpp

9ab67cc8 - [pseudo] Implement guard extension.

Fri, 01 Jul 2022 12:50:07 +0000

[pseudo] Implement guard extension.- Extend the GLR parser to allow conditional reduction based on the guard functions;- Implement two simple guards (contextual-override/final) for cxx.bnf;- layering: clangPseudoCXX depends on clangPseudo (as the guard function need to access the TokenStream);Differential Revision: https://reviews.llvm.org/D127448 List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/GLR.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/GLR.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/GLR.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/GLR.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/GLR.cpp

94460f51 - Don't use Optional::hasValue (NFC)

Mon, 27 Jun 2022 02:54:41 +0000

Don't use Optional::hasValue (NFC)This patch replaces x.hasValue() with x where x is contextuallyconvertible to bool. List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/GLR.cpp

3b7c3a65 - Revert "Don't use Optional::hasValue (NFC)"

Sat, 25 Jun 2022 18:56:50 +0000

Revert "Don't use Optional::hasValue (NFC)"This reverts commit aa8feeefd3ac6c78ee8f67bf033976fc7d68bc6d. List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/GLR.cpp

aa8feeef - Don't use Optional::hasValue (NFC)

Sat, 25 Jun 2022 18:55:57 +0000

Don't use Optional::hasValue (NFC) List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/GLR.cpp

768216ca - [pseudo] Handle no-reductions-available on the fastpath. NFC

Thu, 23 Jun 2022 18:33:26 +0000

[pseudo] Handle no-reductions-available on the fastpath. NFCThis is a ~2% speedup. List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/GLR.cpp

466eae6a - [pseudo] Store last node popped in the queue, not its parent(s). NFC

Thu, 23 Jun 2022 18:06:04 +0000

[pseudo] Store last node popped in the queue, not its parent(s). NFCWe have to walk up to the last node to find the start token, but no needto go even one node further.This is one node fewer to store, but more importantly if the last nodehappens to have multiple parents we avoid storing the sequence multiple times.This saves ~5% on glrParse.Based on a comment by hokein@ on https://reviews.llvm.org/D128307 List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/GLR.cpp

7aff663b - [pseudo] Store reduction sequences by pointer in heaps, instead of by value.

Tue, 21 Jun 2022 22:20:38 +0000

[pseudo] Store reduction sequences by pointer in heaps, instead of by value.Copying sequences around as the heap resized is significantly expensive.This speeds up glrParse by ~35% (2.4 => 3.25 MB/s)Differential Revision: https://reviews.llvm.org/D128307 List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/GLR.cpp

3e610f2c - [pseudo] Turn glrReduce into a class, reuse storage across calls.

Tue, 21 Jun 2022 20:19:06 +0000

[pseudo] Turn glrReduce into a class, reuse storage across calls.This is a ~5% speedup, we no longer have to allocate the priority queues andother collections for each reduction step where we use them.It's also IMO easier to understand the structure of a class with methods vs afunction with nested lambdas.Differential Revision: https://reviews.llvm.org/D128301 List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/GLR.cpp

f9710d19 - [pseudo] Add a fast-path to GLR reduce when both pop and push are trivial

Tue, 21 Jun 2022 19:47:14 +0000

[pseudo] Add a fast-path to GLR reduce when both pop and push are trivialIn general we split a reduce into pop/push, so concurrently-available reductionscan run in the correct order. The data structures for this are expensive.When only one reduction is possible at a time, we need not do this: we can popand immediately push instead.Strictly this is correct whenever we yield one concurrent PushSpec.This patch recognizes a trivial but common subset of these cases: - there must be no pending pushes and only one head available to pop - the head must have only one reduction rule - the reduction path must be a straight line (no multiple parents)On my machine this speeds up by 2.12 -> 2.30 MB/s = 8%Differential Revision: https://reviews.llvm.org/D128299 List of files: /llvm-project-15.0.7/clang-tools-extra/pseudo/lib/GLR.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/GLR.cpp