[pseudo] WIP: GSS node refcounting (dumb pointers)

[sammccall]

Summary

This adds a refcount to GSS::Node, and uses a freelist to reuse nodes rather
than reallocating.

The freelist works well (on AST.cpp, 35K nodes created but only 74 allocated),
but it's not the only point here. Tracking the lifetime of GSS nodes is going to
be useful for error handling: when a node dies having never been successfully
reduced, we can capture it to run recovery on it.

This version of the patch continues to use Node*, with calls to GSS::ref() and
GSS::unref() to manipulate the count. I don't think this is workable - it
took me a depressingly long time to track down the bugs, and the code is hard
to reason about.
I think we want a smart pointer here to make the code clearer. Unfortunately
this is a bit tricky: the destructor needs the GSS to do the destruction, but
we don't want to pay the cost of storing an extra pointer to the GSS everywhere.
I can't think of a better alternative than (ick) thread-local storage.

[hokein]

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

118

The freelist works well (on AST.cpp, 35K nodes created but only 74 allocated),

The number of saving is quite promising! But as discussed, it didn't speed up the parser (mostly we're paying extra cost of updating nodes in dead branches, causing ~10% slowdown).

Wanted to explore an alternative (which we discussed briefly) -- for errory-recovery, the key point is that when there is no active head, we'd like to find a recovery state (retrieved from the most-recent live heads) and continue the parsing from there.

This main parsing for-loop can provide a global view of active heads:

• we can assume here the NewHeads is not empty (for-loop body always starts with active heads);
• if all heads die, we can detect it after the glrReduce (on Line130, by checking PendingShift is empty);

So the code is roughly like

for ( ... : Terminals) {
  auto PreviousNewHeads = NewHeads;

  ....
  glrReduce(...);

  if (PendingShift.empty()) {
    // run error-recovery from the PreviousNewHeads
  } else {
    glrShift(...);
  }
}

clang-tools-extra/pseudo/include/clang-pseudo/GLR.h

 // - GLR allows multiple actions (conflicts) on the same head, producing forks
 //   where several nodes have the same parent
 // - The parser merges nodes with the same (state, ForestNode), producing joins
 //   where one node has multiple parents
 //
 // The parser is responsible for creating nodes and keeping track of the set of
 // heads. The GSS class is mostly an arena for them.
 struct GSS {
+  ~GSS();
   // A node represents a partial parse of the input up to some point.
   //
   // It is the equivalent of a frame in an LR parse stack.
   // Like such a frame, it has an LR parse state and a syntax-tree node
   // representing the last parsed symbol (a ForestNode in our case).
   // Unlike a regular LR stack frame, it may have multiple parents.
   //
   // Nodes are not exactly pushed and popped on the stack: pushing is just
   // allocating a new head node with a parent pointer to the old head. Popping
   // is just forgetting about a node and remembering its parent instead.
   struct alignas(struct Node *) Node {
     // LR state describing how parsing should continue from this head.
     LRTable::StateID State;
     // Number of the parents of this node.
     // The parents hold previous parsed symbols, and may resume control after
     // this node is reduced.
-    unsigned ParentCount;
+    uint16_t ParentCount;
+    // Number of references to this node.
+    // Typically this is 1 if the node is a head, plus the number of children.
+    uint16_t RefCount;
     // The parse node for the last parsed symbol.
     // This symbol appears on the left of the dot in the parse state's items.
     // (In the literature, the node is attached to the *edge* to the parent).
     const ForestNode *Payload = nullptr;
 
-    // FIXME: Most nodes live a fairly short time, and are simply discarded.
-    // Is it worth refcounting them (we have empty padding) and returning to a
-    // freelist, to keep the working set small?
-
     llvm::ArrayRef<const Node *> parents() const {
       return llvm::makeArrayRef(reinterpret_cast<const Node *const *>(this + 1),
                                 ParentCount);
     };
     // Parents are stored as a trailing array of Node*.
   };
 
   // Allocates a new node in the graph.
+  // It has a refcount of 1, and should be pased to deref() when done.
   const Node *addNode(LRTable::StateID State, const ForestNode *Symbol,
-                      llvm::ArrayRef<const Node *> Parents) {
-    ++NodeCount;
-    Node *Result = new (Arena.Allocate(
-        sizeof(Node) + Parents.size() * sizeof(Node *), alignof(Node)))
-        Node({State, static_cast<unsigned>(Parents.size())});
-    Result->Payload = Symbol;
-    if (!Parents.empty())
-      llvm::copy(Parents, reinterpret_cast<const Node **>(Result + 1));
-    return Result;
-  }
+                      llvm::ArrayRef<const Node *> Parents);
+  void ref(const Node *N);
+  void unref(const Node *N);
 
   size_t bytes() const { return Arena.getTotalMemory() + sizeof(*this); }
-  size_t nodeCount() const { return NodeCount; }
+  size_t nodeCount() const { return NodesCreated; }
 
 private:
+  // Nodes are recycled using freelists.
+  // They are variable size, so use one free-list per distinct #parents.
+  std::vector<std::vector<Node *>> FreeList;
+
+  Node *allocate(unsigned Parents);
+  void destroy(Node *N);
+
   llvm::BumpPtrAllocator Arena;
-  unsigned NodeCount = 0;
+  unsigned NodesCreated = 0;
+  unsigned NodesDestroyed = 0;
+  unsigned NodesAllocated = 0;
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const GSS::Node &);
 
 // Parameters for the GLR parsing.
 struct ParseParams {
   // The grammar of the language we're going to parse.
   const Grammar &G;
   // The LR table which GLR uses to parse the input, should correspond to the

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

 namespace pseudo {
 
 using StateID = LRTable::StateID;
 
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const GSS::Node &N) {
   std::vector<std::string> ParentStates;
   for (const auto *Parent : N.parents())
     ParentStates.push_back(llvm::formatv("{0}", Parent->State));
-  OS << llvm::formatv("state {0}, parsed symbol {1}, parents {2}", N.State,
-                      N.Payload->symbol(), llvm::join(ParentStates, ", "));
+  OS << llvm::formatv("state {0}, parsed symbol {1}, parents {{{2}}, refcount={3}",
+                      N.State, N.Payload ? N.Payload->symbol() : 0,
+                      llvm::join(ParentStates, ", "), N.RefCount);
   return OS;
 }
 
+#ifndef NDEBUG
+static void checkRefcounts(std::vector<const GSS::Node *> Queue) {
+  llvm::DenseSet<const GSS::Node *> Seen;
+  llvm::DenseMap<const GSS::Node *, unsigned> Expected;
+  for (const auto *N : Queue)
+    ++Expected[N];
+  while (!Queue.empty()) {
+    const GSS::Node *N = Queue.back();
+    Queue.pop_back();
+    if (!Seen.insert(N).second)
+      continue;
+    for (const auto *P : N->parents()) {
+      ++Expected[P];
+      Queue.push_back(P);
+    }
+  }
+  bool AnyWrong = false;
+  llvm::dbgs() << "Checking refcounts:\n";
+  for (const auto& E : Expected) {
+    llvm::dbgs() << E.first << " " << *E.first << "\n";
+    if (E.second != E.first->RefCount) {
+      llvm::dbgs() << "Wrong refcount: actual=" << E.second << " for "
+                   << E.first << " " << *E.first << "\n";
+      AnyWrong = true;
+    }
+  }
+  if (AnyWrong)
+    abort();
+}
+#endif
+
 const ForestNode &glrParse(const TokenStream &Tokens, const ParseParams &Params,
                            SymbolID StartSymbol) {
   llvm::ArrayRef<ForestNode> Terminals = Params.Forest.createTerminals(Tokens);
   auto &G = Params.G;
   (void)G;
   auto &GSS = Params.GSStack;
 
   // Lists of active shift, reduce, accept actions.
   std::vector<ParseStep> PendingShift, PendingReduce, PendingAccept;
   auto AddSteps = [&](const GSS::Node *Head, SymbolID NextTok) {
     for (const auto &Action : Params.Table.getActions(Head->State, NextTok)) {
       switch (Action.kind()) {
       case LRTable::Action::Shift:
+        GSS.ref(Head);
         PendingShift.push_back({Head, Action});
         break;
       case LRTable::Action::Reduce:
+        GSS.ref(Head);
         PendingReduce.push_back({Head, Action});
         break;
       case LRTable::Action::Accept:
+        GSS.ref(Head);
         PendingAccept.push_back({Head, Action});
         break;
       default:
         llvm_unreachable("unexpected action kind!");
       }
     }
   };
   std::vector<const GSS::Node *> NewHeads = {
       GSS.addNode(/*State=*/Params.Table.getStartState(StartSymbol),
                   /*ForestNode=*/nullptr, {})};
+  auto CheckRefcounts = [&] {
+    DEBUG_WITH_TYPE("GSSNode", {
+      std::vector<const GSS::Node *> Roots = NewHeads;
+      for (const auto *Pending :
+           {&PendingShift, &PendingReduce, &PendingAccept})
+        for (const ParseStep &Step : *Pending)
+          Roots.push_back(Step.Head);
+      checkRefcounts(Roots);
+    });
+  };
   for (const ForestNode &Terminal : Terminals) {
     LLVM_DEBUG(llvm::dbgs() << llvm::formatv("Next token {0} (id={1})\n",
                                              G.symbolName(Terminal.symbol()),
                                              Terminal.symbol()));
-    for (const auto *Head : NewHeads)
+    CheckRefcounts();
+    for (const auto *Head : NewHeads) {
       AddSteps(Head, Terminal.symbol());
+      GSS.unref(Head);
+    }
     NewHeads.clear();
+    CheckRefcounts();
+    LLVM_DEBUG(llvm::dbgs() << "  Reduce\n");
     glrReduce(PendingReduce, Params,
               [&](const GSS::Node * NewHead) {
                 // A reduce will enable more steps.
                 AddSteps(NewHead, Terminal.symbol());
               });
+    CheckRefcounts();
 
-    glrShift(PendingShift, Terminal, Params,
-             [&](const GSS::Node *NewHead) { NewHeads.push_back(NewHead); });
+    glrShift(PendingShift, Terminal, Params, [&](const GSS::Node *NewHead) {
+      GSS.ref(NewHead);
+      NewHeads.push_back(NewHead);
+    });
   }
   LLVM_DEBUG(llvm::dbgs() << llvm::formatv("Next is eof\n"));
-  for (const auto *Heads : NewHeads)
-    AddSteps(Heads, tokenSymbol(tok::eof));
+  CheckRefcounts();
+  for (const auto *Head : NewHeads) {
+    AddSteps(Head, tokenSymbol(tok::eof));
+    GSS.unref(Head);
+  }
+  NewHeads.clear();
+  CheckRefcounts();
   glrReduce(PendingReduce, Params,
             [&](const GSS::Node * NewHead) {
               // A reduce will enable more steps.
               AddSteps(NewHead, tokenSymbol(tok::eof));
             });
+  CheckRefcounts();
 
+  assert(PendingShift.empty());
+  assert(PendingReduce.empty());
   if (!PendingAccept.empty()) {
     LLVM_DEBUG({
       llvm::dbgs() << llvm::formatv("Accept: {0} accepted result:\n",
                                              PendingAccept.size());
       for (const auto &Accept : PendingAccept)
         llvm::dbgs() << "  - " << G.symbolName(Accept.Head->Payload->symbol())
                      << "\n";
     });
     assert(PendingAccept.size() == 1);
-    return *PendingAccept.front().Head->Payload;
+    auto *Result = PendingAccept.front().Head->Payload;
+    GSS.unref(PendingAccept.front().Head);
+    return *Result;
   }
   // We failed to parse the input, returning an opaque forest node for recovery.
   return Params.Forest.createOpaque(StartSymbol, /*Token::Index=*/0);
 }
 
 // Apply all pending shift actions.
 // In theory, LR parsing doesn't have shift/shift conflicts on a single head.
 // But we may have multiple active heads, and each head has a shift action.
 //
 // We merge the stack -- if multiple heads will reach the same state after
 // shifting a token, we shift only once by combining these heads.
 //
 // E.g. we have two heads (2, 3) in the GSS, and will shift both to reach 4:
 //   0---1---2
 //       └---3
 // After the shift action, the GSS is:
 //   0---1---2---4
 //       └---3---┘
 void glrShift(std::vector<ParseStep> &PendingShift, const ForestNode &NewTok,
               const ParseParams &Params, NewHeadCallback NewHeadCB) {
+  auto &GSS = Params.GSStack;
   assert(NewTok.kind() == ForestNode::Terminal);
   assert(llvm::all_of(PendingShift,
                       [](const ParseStep &Step) {
                         return Step.Action.kind() == LRTable::Action::Shift;
                       }) &&
          "Pending shift actions must be shift actions");
   LLVM_DEBUG(llvm::dbgs() << llvm::formatv("  Shift {0} ({1} active heads):\n",
                                            Params.G.symbolName(NewTok.symbol()),
while (!Rest.empty()) {
     // Collect the batch of PendingShift that have compatible shift states.
     // Their heads become TempParents, the parents of the new GSS node.
     StateID NextState = Rest.front().Action.getShiftState();
 
     Parents.clear();
     for (const auto &Base : Rest) {
       if (Base.Action.getShiftState() != NextState)
         break;
-      Parents.push_back(Base.Head);
+      Parents.push_back(Base.Head); // safe borrow
     }
     Rest = Rest.drop_front(Parents.size());
 
     LLVM_DEBUG(llvm::dbgs() << llvm::formatv("    --> S{0} ({1} heads)\n",
                                              NextState, Parents.size()));
-    NewHeadCB(Params.GSStack.addNode(NextState, &NewTok, Parents));
+    const auto *NewHead = Params.GSStack.addNode(NextState, &NewTok, Parents);
+    NewHeadCB(NewHead);
+    GSS.unref(NewHead);
   }
+  for (const auto & PS : PendingShift)
+    GSS.unref(PS.Head);
   PendingShift.clear();
 }
 
 namespace {
 // A KeyedQueue yields pairs of keys and values in order of the keys.
 template <typename Key, typename Value>
 using KeyedQueue =
     std::priority_queue<std::pair<Key, Value>,

 //   Before (joining due to same goto state, the same base):
 //     0--1(class-name)--3(STAR)
 //     └--2(enum-name)--4(STAR)
 //   After reducing 3 by `pointer := class-name STAR` and
 //                  2 by`enum-name := class-name STAR`:
 //     0--5(pointer)       // 5 is goto(0, pointer)
 void glrReduce(std::vector<ParseStep> &PendingReduce, const ParseParams &Params,
                NewHeadCallback NewHeadCB) {
+  auto &GSS = Params.GSStack;
   // There are two interacting complications:
   // 1.  Performing one reduce can unlock new reduces on the newly-created head.
   // 2a. The ambiguous ForestNodes must be complete (have all sequence nodes).
   //     This means we must have unlocked all the reduces that contribute to it.
   // 2b. Similarly, the new GSS nodes must be complete (have all parents).
   //
   // We define a "family" of reduces as those that produce the same symbol and
   // cover the same range of tokens. These are exactly the set of reductions
void glrReduce(std::vector<ParseStep> &PendingReduce, const ParseParams &Params,
   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();
+        GSS.ref(N);
         Bases.emplace(F, N);
         LLVM_DEBUG(llvm::dbgs() << "    --> base at S" << N->State << "\n");
         Sequences.emplace(F, 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 (const ParseStep &Pending : PendingReduce)
+    for (const ParseStep &Pending : PendingReduce) {
       Pop(Pending.Head, Pending.Action.getReduceRule());
+      GSS.unref(Pending.Head);
+    }
     PendingReduce.clear();
   };
 
   std::vector<std::pair</*Goto*/ StateID, const GSS::Node *>> FamilyBases;
   std::vector<std::pair<RuleID, Sequence>> FamilySequences;
 
   std::vector<const GSS::Node *> TempGSSNodes;
   std::vector<const ForestNode *> TempForestNodes;
while (!Bases.empty()) {
     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.top().second); // transfer ownership
       Bases.pop();
     } while (!Bases.empty() && Bases.top().first == F);
-    sortAndUnique(FamilyBases);
+    llvm::sort(FamilyBases);
+    // XXX sortAndUnique is not aware of ref/unref, copy for simplicity.
+    std::vector<decltype(FamilyBases)::value_type> UniqueBases;
+    std::unique_copy(FamilyBases.begin(), FamilyBases.end(),
+                     std::back_inserter(UniqueBases));
     // Create a GSS node for each unique goto state.
-    llvm::ArrayRef<decltype(FamilyBases)::value_type> BasesLeft = FamilyBases;
+    llvm::ArrayRef<decltype(FamilyBases)::value_type> BasesLeft = UniqueBases;
     while (!BasesLeft.empty()) {
       StateID NextState = BasesLeft.front().first;
       auto &Parents = TempGSSNodes;
       Parents.clear();
       for (const auto &Base : BasesLeft) {
         if (Base.first != NextState)
           break;
-        Parents.push_back(Base.second);
+        Parents.push_back(Base.second); // safe borrow
       }
       BasesLeft = BasesLeft.drop_front(Parents.size());
 
       // Invoking the callback for new heads, a real GLR parser may add new
       // reduces to the PendingReduce queue!
-      NewHeadCB(Params.GSStack.addNode(NextState, Parsed, Parents));
+      const auto *NewNode = Params.GSStack.addNode(NextState, Parsed, Parents);
+      NewHeadCB(NewNode);
+      GSS.unref(NewNode);
     }
+    for (auto &FB : FamilyBases)
+      GSS.unref(FB.second);
+    FamilyBases.clear();
     PopPending();
   }
   assert(Sequences.empty());
 }
 
+static void logLifetime(llvm::StringRef Sigil, const GSS::Node* N) {
+  DEBUG_WITH_TYPE("GSSNode", llvm::dbgs()
+                                 << Sigil << " " << N << " " << *N << "\n");
+}
+
+const GSS::Node *GSS::addNode(LRTable::StateID State, const ForestNode *Symbol,
+                              llvm::ArrayRef<const Node *> Parents) {
+  ++NodesCreated;
+  Node *Result = new (allocate(Parents.size()))
+      Node({State, static_cast<uint16_t>(Parents.size()), /*RefCount=*/0});
+  Result->Payload = Symbol;
+  auto *ParentArray = reinterpret_cast<const Node **>(Result + 1);
+  for (const auto *Parent : Parents) {
+    ref(Parent);
+    *ParentArray++ = Parent;
+  }
+  logLifetime("*", Result);
+  ref(Result);
+  return Result;
+}
+
+void GSS::ref(const Node *N) {
+  const_cast<Node *>(N)->RefCount++;
+  logLifetime("+", N);
+}
+
+void GSS::unref(const Node *N) {
+  assert(N->RefCount != 0);
+  Node *NN = const_cast<Node *>(N); // I created you, and I can destroy you!
+  --NN->RefCount;
+  logLifetime("-", N);
+  // Node is const from the caller's perspective, but we created it
+  if (0 == NN->RefCount)
+    destroy(NN);
+}
+
+GSS::Node *GSS::allocate(unsigned Parents) {
+  if (FreeList.size() <= Parents)
+    FreeList.resize(Parents + 1);
+  auto &SizedList = FreeList[Parents];
+  if (!SizedList.empty()) {
+    auto *Result = SizedList.back();
+    SizedList.pop_back();
+    return Result;
+  }
+  ++NodesAllocated;
+  return static_cast<Node *>(
+      Arena.Allocate(sizeof(Node) + Parents * sizeof(Node *), alignof(Node)));
+}
+
+void GSS::destroy(Node *N) {
+  logLifetime("~", N);
+  ++NodesDestroyed;
+  for (auto *Parent : N->parents())
+    unref(Parent);
+  unsigned ParentCount = N->ParentCount;
+  N->~Node();
+  assert(FreeList.size() > ParentCount && "established on construction!");
+  FreeList[ParentCount].push_back(N);
+}
+
+GSS::~GSS() { assert(NodesCreated == NodesDestroyed); }
+
 } // namespace pseudo
 } // namespace clang

clang-tools-extra/pseudo/unittests/GLRTest.cpp

RuleID ruleFor(llvm::StringRef NonterminalName) const {
     ADD_FAILURE() << "Expected a single rule for " << NonterminalName
                   << ", but it has " << RuleRange.End - RuleRange.Start
                   << " rule!\n";
     return 0;
   }
 
   NewHeadCallback captureNewHeads() {
     return [this](const GSS::Node *NewHead) {
+      GSStack.ref(NewHead);
       NewHeadResults.push_back(NewHead);
     };
   };
 
 protected:
+  ~GLRTest() {
+    for (auto *N : NewHeadResults)
+      GSStack.unref(N);
+  }
+
   std::unique_ptr<Grammar> G;
   ForestArena Arena;
   GSS GSStack;
   std::vector<const GSS::Node*> NewHeadResults;
 };
 
 TEST_F(GLRTest, ShiftMergingHeads) {
   // Given a test case where we have two heads 1, 2, 3 in the GSS, the heads 1,
TEST_F(GLRTest, ShiftMergingHeads) {
   auto *GSSNode0 =
       GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{});
   auto *GSSNode1 = GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr,
                                    /*Parents=*/{GSSNode0});
   auto *GSSNode2 = GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr,
                                    /*Parents=*/{GSSNode0});
   auto *GSSNode3 = GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr,
                                    /*Parents=*/{GSSNode0});
+  GSStack.unref(GSSNode0);
 
   buildGrammar({}, {}); // Create a fake empty grammar.
   LRTable T = LRTable::buildForTests(G->table(), /*Entries=*/{});
 
   ForestNode &SemiTerminal = Arena.createTerminal(tok::semi, 0);
   std::vector<ParseStep> PendingShift = {
       {GSSNode1, Action::shift(4)},
       {GSSNode3, Action::shift(5)},
TEST_F(GLRTest, ReduceConflictsSplitting) {
   LRTable Table = LRTable::buildForTests(
       G->table(), {{/*State=*/0, id("class-name"), Action::goTo(2)},
                    {/*State=*/0, id("enum-name"), Action::goTo(3)}});
 
   const auto *GSSNode0 =
       GSStack.addNode(/*State=*/0, /*ForestNode=*/nullptr, /*Parents=*/{});
   const auto *GSSNode1 =
       GSStack.addNode(3, &Arena.createTerminal(tok::identifier, 0), {GSSNode0});
+  GSStack.unref(GSSNode0);
+  GSStack.ref(GSSNode1);
 
   std::vector<ParseStep> PendingReduce = {
       {GSSNode1, Action::reduce(ruleFor("class-name"))},
       {GSSNode1, Action::reduce(ruleFor("enum-name"))}};
   glrReduce(PendingReduce, {*G, Table, Arena, GSStack},
             captureNewHeads());
   EXPECT_THAT(NewHeadResults,
               testing::UnorderedElementsAre(
TEST_F(GLRTest, ReduceSplittingDueToMultipleBases) {
 
   const auto *GSSNode2 =
       GSStack.addNode(/*State=*/2, /*ForestNode=*/ClassNameNode, /*Parents=*/{});
   const auto *GSSNode3 =
       GSStack.addNode(/*State=*/3, /*ForestNode=*/EnumNameNode, /*Parents=*/{});
   const auto *GSSNode4 = GSStack.addNode(
       /*State=*/4, &Arena.createTerminal(tok::star, /*TokenIndex=*/1),
       /*Parents=*/{GSSNode2, GSSNode3});
+  GSStack.unref(GSSNode2);
+  GSStack.unref(GSSNode3);
 
   LRTable Table = LRTable::buildForTests(
       G->table(),
       {{/*State=*/2, id("ptr-operator"), Action::goTo(/*NextState=*/5)},
        {/*State=*/3, id("ptr-operator"), Action::goTo(/*NextState=*/6)}});
   std::vector<ParseStep> PendingReduce = {
       {GSSNode4, Action::reduce(ruleFor("ptr-operator"))}};
   glrReduce(PendingReduce, {*G, Table, Arena, GSStack},
TEST_F(GLRTest, ReduceJoiningWithMultipleBases) {
   const auto *GSSNode2 = GSStack.addNode(
       /*State=*/2, /*ForestNode=*/CVQualifierNode, /*Parents=*/{GSSNode0});
   const auto *GSSNode3 =
       GSStack.addNode(/*State=*/3, /*ForestNode=*/ClassNameNode,
                       /*Parents=*/{GSSNode1});
   const auto *GSSNode4 =
       GSStack.addNode(/*State=*/4, /*ForestNode=*/EnumNameNode,
                       /*Parents=*/{GSSNode2});
+  GSStack.unref(GSSNode0);
+  GSStack.unref(GSSNode1);
+  GSStack.unref(GSSNode2);
 
   LRTable Table = LRTable::buildForTests(
       G->table(),
       {{/*State=*/1, id("type-name"), Action::goTo(/*NextState=*/5)},
        {/*State=*/2, id("type-name"), Action::goTo(/*NextState=*/5)}});
   // FIXME: figure out a way to get rid of the hard-coded reduce RuleID!
   std::vector<ParseStep> PendingReduce = {
       {
const auto *GSSNode2 =
       GSStack.addNode(/*State=*/2, /*ForestNode=*/EnumNameNode,
                       /*Parents=*/{GSSNode0});
   const auto *GSSNode3 =
       GSStack.addNode(/*State=*/3, /*ForestNode=*/StartTerminal,
                       /*Parents=*/{GSSNode1});
   const auto *GSSNode4 =
       GSStack.addNode(/*State=*/4, /*ForestNode=*/StartTerminal,
                       /*Parents=*/{GSSNode2});
+  GSStack.unref(GSSNode0);
+  GSStack.unref(GSSNode1);
+  GSStack.unref(GSSNode2);
 
   LRTable Table = LRTable::buildForTests(
       G->table(), {{/*State=*/0, id("pointer"), Action::goTo(5)}});
   // FIXME: figure out a way to get rid of the hard-coded reduce RuleID!
   std::vector<ParseStep> PendingReduce = {
       {
           GSSNode3, Action::reduce(/*RuleID=*/0) // pointer := class-name *
       },