[pseudo] Simplify the glrReduce implementation.

[hokein]

Summary

glrReduce maintains two priority queues (one for bases, and the other
for Sequence), these queues are in parallel with each other, corresponding to a
single family. They can be folded into one.

This patch removes the bases priority queue, which improves the glrParse by
10%.

ASTReader.cpp: 2.03M/s (before) vs 2.26M/s (after)

[sammccall]

Very nice! Not sure why I didn't see this before :-)

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

266

This name is a bit vague/abstract.

Maybe RootedSequence, or PushSpec?

267

nit: A base node is the head...
(no reason to talk about them collectively in this context)

268

the second part of this comment belongs below where we decorrelate the two (under "grab the sequences and bases for each family"), not here

[hokein]

address comments

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

bool operator<(const Family &Other) const {
         return Start < Other.Start;
       if (Symbol != Other.Symbol)
         return Rule > Other.Rule;
       assert(*this == Other);
       return false;
     }
   };
 
-  // The base nodes are the heads after popping the GSS nodes we are reducing.
-  // We don't care which rule yielded each base. If Family.Symbol is S, the
-  // base includes an item X := ... • S ... and since the grammar is
-  // context-free, *all* parses of S are valid here.
-  // FIXME: reuse the queues across calls instead of reallocating.
-  KeyedQueue<Family, const GSS::Node *> Bases;
-
   // A sequence is the ForestNode payloads of the GSS nodes we are reducing.
   // These are the RHS of the rule, the RuleID is stored in the Family.
   // They specify a sequence ForestNode we may build (but we dedup first).
   using Sequence = llvm::SmallVector<const ForestNode *, Rule::MaxElements>;
-  KeyedQueue<Family, Sequence> Sequences;
+  struct SeqNodeSpec {
+    // The base nodes are the heads after popping the GSS nodes we are reducing.
+    // We don't care which rule yielded each base. If Family.Symbol is S, the
+    // base includes an item X := ... • S ... and since the grammar is
+    // context-free, *all* parses of S are valid here.
+    const GSS::Node* Base = nullptr;
+    Sequence Seq;
+  };
+  KeyedQueue<Family, SeqNodeSpec> Sequences;
 
   Sequence TempSequence;
   // 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();
-        Bases.emplace(F, N);
         LLVM_DEBUG(llvm::dbgs() << "    --> base at S" << N->State << "\n");
-        Sequences.emplace(F, TempSequence);
+        Sequences.emplace(F, SeqNodeSpec{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);
   };
void glrReduce(std::vector<ParseStep> &PendingReduce, const ParseParams &Params,
   std::vector<const GSS::Node *> TempGSSNodes;
   std::vector<const ForestNode *> TempForestNodes;
 
   // Main reduction loop:
   //  - pop as much as we can
   //  - process one family at a time, forming a forest node
   //  - produces new GSS heads which may enable more pops
   PopPending();
-  while (!Bases.empty()) {
-    // We should always have bases and sequences for the same families.
-    Family F = Bases.top().first;
-    assert(!Sequences.empty());
-    assert(Sequences.top().first == F);
+  while (!Sequences.empty()) {
+    Family F = Sequences.top().first;
 
     LLVM_DEBUG(llvm::dbgs() << "  Push " << Params.G.symbolName(F.Symbol)
                             << " from token " << F.Start << "\n");
 
-    // Grab the sequences for this family.
+    // Grab the sequences and bases for this family.
     FamilySequences.clear();
+    FamilyBases.clear();
     do {
       FamilySequences.emplace_back(Sequences.top().first.Rule,
-                                   Sequences.top().second);
+                                   Sequences.top().second.Seq);
+      FamilyBases.emplace_back(
+          Params.Table.getGoToState(Sequences.top().second.Base->State,
+                                    F.Symbol),
+          Sequences.top().second.Base);
+
       Sequences.pop();
     } while (!Sequences.empty() && Sequences.top().first == F);
     // Build a forest node for each unique sequence.
     sortAndUnique(FamilySequences);
     auto &SequenceNodes = TempForestNodes;
     SequenceNodes.clear();
     for (const auto &SequenceSpec : FamilySequences)
       SequenceNodes.push_back(&Params.Forest.createSequence(
           F.Symbol, SequenceSpec.first, SequenceSpec.second));
     // Wrap in an ambiguous node if needed.
     const ForestNode *Parsed =
         SequenceNodes.size() == 1
             ? SequenceNodes.front()
             : &Params.Forest.createAmbiguous(F.Symbol, SequenceNodes);
     LLVM_DEBUG(llvm::dbgs() << "    --> " << Parsed->dump(Params.G) << "\n");
 
-    // Grab the bases for this family.
-    // As well as deduplicating them, we'll group by the goto state.
-    FamilyBases.clear();
-    do {
-      FamilyBases.emplace_back(
-          Params.Table.getGoToState(Bases.top().second->State, F.Symbol),
-          Bases.top().second);
-      Bases.pop();
-    } while (!Bases.empty() && Bases.top().first == F);
+    // Bases for this family, deduplicate them, and group by the goTo State.
     sortAndUnique(FamilyBases);
     // Create a GSS node for each unique goto state.
     llvm::ArrayRef<decltype(FamilyBases)::value_type> BasesLeft = FamilyBases;
     while (!BasesLeft.empty()) {
       StateID NextState = BasesLeft.front().first;
       auto &Parents = TempGSSNodes;
       Parents.clear();
       for (const auto &Base : BasesLeft) {