sammccall created this revision.
sammccall added a reviewer: hokein.
Herald added a project: All.
sammccall requested review of this revision.
Herald added subscribers: cfe-commits, alextsao1999.
Herald added a project: clang-tools-extra.
In general we split a reduce into pop/push, so concurrently-available reductions
can 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 pop
and 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%
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D128299
Files:
clang-tools-extra/pseudo/lib/GLR.cpp
Index: clang-tools-extra/pseudo/lib/GLR.cpp
===================================================================
--- clang-tools-extra/pseudo/lib/GLR.cpp
+++ clang-tools-extra/pseudo/lib/GLR.cpp
@@ -262,6 +262,39 @@
// We treat Heads as a queue of Pop operations still to be performed.
// PoppedHeads is our position within it.
unsigned PoppedHeads = 0;
+ // In general the sequencing is complicated: each pop can yield multiple
+ // pending pushes that might run in a different order than we found them.
+ // However in trivial cases (only pop that yields only one push) we can
+ // bypass all these fancy queues and pop+push directly. This is very common.
+ auto PopAndPushTrivial = [&]() -> bool {
+ if (!Sequences.empty() || Heads.size() != PoppedHeads + 1)
+ return false;
+ const GSS::Node *Head = Heads.back();
+ llvm::Optional<RuleID> RID;
+ for (auto &A : Params.Table.getActions(Head->State, Lookahead)) {
+ if (A.kind() != LRTable::Action::Reduce)
+ continue;
+ if (RID.hasValue())
+ return false;
+ RID = A.getReduceRule();
+ }
+ if (!RID.hasValue())
+ return false;
+ const auto &Rule = Params.G.lookupRule(*RID);
+ const GSS::Node *Base = Head;
+ TempSequence.resize_for_overwrite(Rule.Size);
+ for (unsigned I = 0; I < Rule.Size; ++I) {
+ if (Base->parents().size() != 1)
+ return false;
+ TempSequence[Rule.Size - 1 - I] = Base->Payload;
+ Base = Base->parents().front();
+ }
+ const ForestNode *Parsed =
+ &Params.Forest.createSequence(Rule.Target, *RID, TempSequence);
+ StateID NextState = Params.Table.getGoToState(Base->State, Rule.Target);
+ Heads.push_back(Params.GSStack.addNode(NextState, Parsed, {Base}));
+ return true;
+ };
// Pop walks up the parent chain(s) for a reduction from Head by to Rule.
// Once we reach the end, record the bases and sequences.
auto Pop = [&](const GSS::Node *Head, RuleID RID) {
@@ -284,8 +317,8 @@
};
auto PopPending = [&] {
for (; PoppedHeads < Heads.size(); ++PoppedHeads) {
- // FIXME: if there's exactly one head in the queue, and the pop stage
- // is trivial, we could pop + push without touching the expensive queues.
+ if (PopAndPushTrivial())
+ continue;
for (const auto &A :
Params.Table.getActions(Heads[PoppedHeads]->State, Lookahead)) {
if (A.kind() != LRTable::Action::Reduce)
Index: clang-tools-extra/pseudo/lib/GLR.cpp
===================================================================
--- clang-tools-extra/pseudo/lib/GLR.cpp
+++ clang-tools-extra/pseudo/lib/GLR.cpp
@@ -262,6 +262,39 @@
// We treat Heads as a queue of Pop operations still to be performed.
// PoppedHeads is our position within it.
unsigned PoppedHeads = 0;
+ // In general the sequencing is complicated: each pop can yield multiple
+ // pending pushes that might run in a different order than we found them.
+ // However in trivial cases (only pop that yields only one push) we can
+ // bypass all these fancy queues and pop+push directly. This is very common.
+ auto PopAndPushTrivial = [&]() -> bool {
+ if (!Sequences.empty() || Heads.size() != PoppedHeads + 1)
+ return false;
+ const GSS::Node *Head = Heads.back();
+ llvm::Optional<RuleID> RID;
+ for (auto &A : Params.Table.getActions(Head->State, Lookahead)) {
+ if (A.kind() != LRTable::Action::Reduce)
+ continue;
+ if (RID.hasValue())
+ return false;
+ RID = A.getReduceRule();
+ }
+ if (!RID.hasValue())
+ return false;
+ const auto &Rule = Params.G.lookupRule(*RID);
+ const GSS::Node *Base = Head;
+ TempSequence.resize_for_overwrite(Rule.Size);
+ for (unsigned I = 0; I < Rule.Size; ++I) {
+ if (Base->parents().size() != 1)
+ return false;
+ TempSequence[Rule.Size - 1 - I] = Base->Payload;
+ Base = Base->parents().front();
+ }
+ const ForestNode *Parsed =
+ &Params.Forest.createSequence(Rule.Target, *RID, TempSequence);
+ StateID NextState = Params.Table.getGoToState(Base->State, Rule.Target);
+ Heads.push_back(Params.GSStack.addNode(NextState, Parsed, {Base}));
+ return true;
+ };
// Pop walks up the parent chain(s) for a reduction from Head by to Rule.
// Once we reach the end, record the bases and sequences.
auto Pop = [&](const GSS::Node *Head, RuleID RID) {
@@ -284,8 +317,8 @@
};
auto PopPending = [&] {
for (; PoppedHeads < Heads.size(); ++PoppedHeads) {
- // FIXME: if there's exactly one head in the queue, and the pop stage
- // is trivial, we could pop + push without touching the expensive queues.
+ if (PopAndPushTrivial())
+ continue;
for (const auto &A :
Params.Table.getActions(Heads[PoppedHeads]->State, Lookahead)) {
if (A.kind() != LRTable::Action::Reduce)
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
