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

[sammccall]

Summary

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%

[hokein]

clang-tools-extra/pseudo/lib/GLR.cpp

273

IMO, it is exactly what the reduction implementation would look like for a linear LR parsing :)

maybe encode the linear in the name?

274

The patch description is really nice document, and help to me to justify the code. I'd suggest adding them in the comment as well.

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)

333–335

This seems very clever -- for trivial case, the main reduce loop is happening here.

337

we could save an extra call of Params.Table.getActions -- we call it at the beginning of the loop body and store the results in a local var, and use it in PopAndPushTrivial and here.

[hokein]

clang-tools-extra/pseudo/lib/GLR.cpp

272

Thinking more about this, this trivial case seems to be triggered more often if we use a more powerful LR parsing algorithm -- a more powerful LR parser means less dead heads, and more linear cases.

[sammccall]

clang-tools-extra/pseudo/lib/GLR.cpp

273

Thanks for making this connection, I hadn't completely realized we're just acting like an LR parser here and fundamentally that's why it's cheap.

I've amended the comment to call this out explicitly.

I'm not sure changing the *name* is better though, because the name has some jobs to do at the callsite:

• convey that we're non just popping but pushing also (which is suprising)
• suggest that this is handling some simple cases, but not the general case

I don't think "linear" actually conveys the second point. It partially describes *which* simple cases are handled.
So it would need to be tacked on like PopAndPushTrivialLinear and to me that's enough concepts that my brain has trouble digesting it.

This would be worth it if it were a critical part of the interface, but I don't think it is - it's rather important to the implementation instead.

274

Done. The new comment is based on the patch descriptions, with amendments to talk about the relationship to LR you pointed out.

333–335

Can't tell if "clever" is a good or bad thing :-)

Added a comment, it's definitely not obvious.

337

Yes, I benchmarked this and was surprised to see no difference at all!

I'd be tempted to do it anyway, but D128318 obsoletes this idea entirely, by making reduce lookup extremely cheap. At that point it's not worth messing up the signatures.

clang-tools-extra/pseudo/lib/GLR.cpp

void glrReduce(std::vector<const GSS::Node *> &Heads, SymbolID Lookahead,
   };
   KeyedQueue<Family, PushSpec> Sequences;
 
   Sequence TempSequence;
 
   // We treat Heads as a queue of Pop operations still to be performed.
   // NextPopHead is our position within it.
   unsigned NextPopHead = 0;
+  // In general we split a reduce into a pop/push, so concurrently-available
+  // reductions can run in the correct order. The data structures are expensive.
+  //
+  // When only one reduction is possible at a time, we can skip this:
+  // we pop and immediately push, as an LR parser (as opposed to GLR) would.
+  // This is valid whenever there's only one concurrent PushSpec.
+  //
+  // This function handles a trivial but common subset of these cases:
+  //  - there must be no pending pushes, and only one poppable head
+  //  - the head must have only one reduction rule
+  //  - the reduction path must be a straight line (no multiple parents)
+  // (Roughly this means there's no local ambiguity, so the LR algorithm works).
+  auto PopAndPushTrivial = [&]() -> bool {
+    if (!Sequences.empty() || Heads.size() != NextPopHead + 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) {
     LLVM_DEBUG(llvm::dbgs() << "  Pop " << Params.G.dumpRule(RID) << "\n");
     const auto &Rule = Params.G.lookupRule(RID);
     Family F{/*Start=*/0, /*Symbol=*/Rule.Target, /*Rule=*/RID};
     TempSequence.resize_for_overwrite(Rule.Size);
     auto DFS = [&](const GSS::Node *N, unsigned I, auto &DFS) {
       if (I == Rule.Size) {
         F.Start = TempSequence.front()->startTokenIndex();
         LLVM_DEBUG(llvm::dbgs() << "    --> base at S" << N->State << "\n");
         Sequences.emplace(F, PushSpec{N, TempSequence});
         return;
       }
       TempSequence[Rule.Size - 1 - I] = N->Payload;
       for (const GSS::Node *Parent : N->parents())
         DFS(Parent, I + 1, DFS);
     };
     DFS(Head, 0, DFS);
   };
   auto PopPending = [&] {
     for (; NextPopHead < Heads.size(); ++NextPopHead) {
-      // 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.
+      // In trivial cases, we perform the complete reduce here!
+      if (PopAndPushTrivial())
+        continue;
       for (const auto &A :
            Params.Table.getActions(Heads[NextPopHead]->State, Lookahead)) {
         if (A.kind() != LRTable::Action::Reduce)
           continue;
         Pop(Heads[NextPopHead], A.getReduceRule());
       }
     }
   };
 
   std::vector<std::pair</*Goto*/ StateID, const GSS::Node *>> FamilyBases;