[pseudo] prototype: faster data structures for LRTable

[sammccall]

Summary

For shift and goto, use a hashtable for faster lookups. This is ~3x bigger,
but these are not most of the actions (~15% each).

For reduce, the common pattern is that a (state, reduce rule) pair applies to
lots of possible lookahead tokens. So store this as one object with a bitmap for
the valid lookahead tokens. This is very efficient (~4x smaller than before).

Overall we're <20% bigger which seems acceptable.
Before: size of the table (bytes): 401554
After: size of the table (bytes): 470636 (Shift=196608 Reduce=77284 Goto=196608)

This yields a 24% speedup of glrParse on my machine (3.5 -> 4.35 MB/s)

[sammccall]

I'm happy with the data structures at this point, so if you have feedback on those that'd be great.
Otherwise I still need to clean up the interfaces, fix the broken tests, add some more comments etc.

[sammccall]

This is obsoleted by D128485 and D128472

clang-tools-extra/pseudo/include/clang-pseudo/grammar/LRTable.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef CLANG_PSEUDO_GRAMMAR_LRTABLE_H
 #define CLANG_PSEUDO_GRAMMAR_LRTABLE_H
 
 #include "clang-pseudo/grammar/Grammar.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/Support/Capacity.h"
+#include <bitset>
 #include <cstdint>
 #include <vector>
 
 namespace clang {
 namespace pseudo {
 
 // Represents the LR parsing table, which can efficiently the question "what is
 // the next step given the lookahead token and current state on top of the
private:
     static_assert(ValueBits >= RuleBits, "Value must be able to store RuleID");
     static_assert(KindBits + ValueBits <= 16,
                   "Must be able to store kind and value efficiently");
     uint16_t K : KindBits;
     // Either StateID or RuleID, depending on the Kind.
     uint16_t Value : ValueBits;
   };
 
-  // Returns all available actions for the given state on a terminal.
-  // Expected to be called by LR parsers.
-  llvm::ArrayRef<Action> getActions(StateID State, SymbolID Terminal) const;
+  struct Reduce {
+    StateID State;
+    RuleID Rule;
+    std::bitset<tok::NUM_TOKENS> Filter;
+  };
+
+  llvm::ArrayRef<Reduce> getReduces(StateID State) const {
+    unsigned Begin = ReducesLookup[State], End = Begin;
+    while (Reduces[End].State == State)
+      ++End;
+    return llvm::makeArrayRef(&Reduces[Begin], &Reduces[End]);
+  }
+
   // Returns the state after we reduce a nonterminal.
   // Expected to be called by LR parsers.
   StateID getGoToState(StateID State, SymbolID Nonterminal) const;
   llvm::Optional<StateID> getShiftState(StateID State, SymbolID Terminal) const;
 
-  // Looks up available actions.
-  // Returns empty if no available actions in the table.
-  llvm::ArrayRef<Action> find(StateID State, SymbolID Symbol) const;
-
   // Returns the state from which the LR parser should start to parse the input
   // tokens as the given StartSymbol.
   //
   // In LR parsing, the start state of `translation-unit` corresponds to
   // `_ := • translation-unit`.
   //
   // Each start state responds to **a** single grammar rule like `_ := start`.
   // REQUIRE: The given StartSymbol must exist in the grammar (in a form of
   //          `_ := start`).
   StateID getStartState(SymbolID StartSymbol) const;
 
   size_t bytes() const {
-    return sizeof(*this) + Actions.capacity() * sizeof(Action) +
-           Symbols.capacity() * sizeof(SymbolID) +
-           StateOffset.capacity() * sizeof(uint32_t);
+    return sizeof(*this) + llvm::capacity_in_bytes(Shift) +
+           llvm::capacity_in_bytes(Goto) + llvm::capacity_in_bytes(Reduces) +
+           llvm::capacity_in_bytes(ReducesLookup);
   }
 
   std::string dumpStatistics() const;
   std::string dumpForTests(const Grammar &G) const;
 
   // Build a SLR(1) parsing table.
   static LRTable buildSLR(const Grammar &G);
 
   class Builder;
   // Represents an entry in the table, used for building the LRTable.
   struct Entry {
     StateID State;
     SymbolID Symbol;
     Action Act;
   };
   // Build a specifid table for testing purposes.
   static LRTable buildForTests(const GrammarTable &, llvm::ArrayRef<Entry>);
 
 private:
-  // Conceptually the LR table is a multimap from (State, SymbolID) => Action.
-  // Our physical representation is quite different for compactness.
+  unsigned NumShift = 0;
+  unsigned NumGoto = 0;
+  unsigned NumReduce = 0;
+
+  llvm::DenseMap<std::pair<SymbolID, StateID>, StateID> Shift;
+  llvm::DenseMap<std::pair<SymbolID, StateID>, StateID> Goto;
+  std::vector<Reduce> Reduces;
+  std::vector<unsigned> ReducesLookup;
 
-  // Index is StateID, value is the offset into Symbols/Actions
-  // where the entries for this state begin.
-  // Give a state id, the corresponding half-open range of Symbols/Actions is
-  // [StateOffset[id], StateOffset[id+1]).
-  std::vector<uint32_t> StateOffset;
-  // Parallel to Actions, the value is SymbolID (columns of the matrix).
-  // Grouped by the StateID, and only subranges are sorted.
-  std::vector<SymbolID> Symbols;
-  // A flat list of available actions, sorted by (State, SymbolID).
-  std::vector<Action> Actions;
   // A sorted table, storing the start state for each target parsing symbol.
   std::vector<std::pair<SymbolID, StateID>> StartStates;
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const LRTable::Action &);
 
 } // namespace pseudo
 } // namespace clang
 
 #endif // CLANG_PSEUDO_GRAMMAR_LRTABLE_H

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

private:
   }
 
   // popPending pops every available reduction.
   void popPending() {
     for (; PoppedHeads < Heads->size(); ++PoppedHeads) {
       if (popAndPushTrivial())
         continue;
       for (const auto &A :
-           Params.Table.getActions((*Heads)[PoppedHeads]->State, Lookahead)) {
-        if (A.kind() != LRTable::Action::Reduce)
+           Params.Table.getReduces((*Heads)[PoppedHeads]->State)) {
+        if (!A.Filter.test(symbolToToken(Lookahead)))
           continue;
-        pop((*Heads)[PoppedHeads], A.getReduceRule());
+        pop((*Heads)[PoppedHeads], A.Rule);
       }
     }
   }
 
   // Storage reused by each call to pushNext.
   std::vector<std::pair</*Goto*/ StateID, const GSS::Node *>> FamilyBases;
   std::vector<std::pair<RuleID, SequenceRef>> FamilySequences;
   std::vector<const GSS::Node *> Parents;
private:
   // 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.
   bool popAndPushTrivial() {
     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)
+    for (auto &A : Params.Table.getReduces(Head->State)) {
+      if (!A.Filter.test(symbolToToken(Lookahead)))
         continue;
       if (RID.hasValue())
         return false;
-      RID = A.getReduceRule();
+      RID = A.Rule;
     }
     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)

clang-tools-extra/pseudo/lib/grammar/LRTable.cpp

 //===--- LRTable.cpp - Parsing table for LR parsers --------------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang-pseudo/grammar/LRTable.h"
 #include "clang-pseudo/grammar/Grammar.h"
-#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/Capacity.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace clang {
 namespace pseudo {
 
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const LRTable::Action &A) {
llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const LRTable::Action &A) {
   }
   llvm_unreachable("unexpected action kind!");
 }
 
 std::string LRTable::dumpStatistics() const {
   return llvm::formatv(R"(
 Statistics of the LR parsing table:
     number of states: {0}
-    number of actions: {1}
-    size of the table (bytes): {2}
+    number of actions: shift={1} reduce={2} goto={3}
+    size of the table (bytes): {4} (Shift={5} Reduce={6} Goto={7})
 )",
-                       StateOffset.size() - 1, Actions.size(), bytes())
+                       ReducesLookup.size() - 1, NumShift, NumReduce, NumGoto,
+                       bytes(), capacity_in_bytes(Shift),
+                       llvm::capacity_in_bytes(Reduces) +
+                           llvm::capacity_in_bytes(ReducesLookup),
+                       capacity_in_bytes(Goto))
       .str();
 }
 
 std::string LRTable::dumpForTests(const Grammar &G) const {
   std::string Result;
   llvm::raw_string_ostream OS(Result);
   OS << "LRTable:\n";
-  for (StateID S = 0; S < StateOffset.size() - 1; ++S) {
+  for (StateID S = 0; S < ReducesLookup.size() - 1; ++S) {
     OS << llvm::formatv("State {0}\n", S);
     for (uint16_t Terminal = 0; Terminal < NumTerminals; ++Terminal) {
       SymbolID TokID = tokenSymbol(static_cast<tok::TokenKind>(Terminal));
-      for (auto A : find(S, TokID)) {
-        if (A.kind() == LRTable::Action::Shift)
-          OS.indent(4) << llvm::formatv("'{0}': shift state {1}\n",
-                                        G.symbolName(TokID), A.getShiftState());
-        else if (A.kind() == LRTable::Action::Reduce)
+      if (auto NewState = getShiftState(S, TokID)) {
+                                      G.symbolName(TokID), *NewState);
+      }
+      for (auto &R : getReduces(S)) {
+        if (R.Filter.test(TokID))
           OS.indent(4) << llvm::formatv("'{0}': reduce by rule {1} '{2}'\n",
-                                        G.symbolName(TokID), A.getReduceRule(),
-                                        G.dumpRule(A.getReduceRule()));
+                                        G.symbolName(TokID), R.Rule,
+                                        G.dumpRule(R.Rule));
       }
     }
     for (SymbolID NontermID = 0; NontermID < G.table().Nonterminals.size();
          ++NontermID) {
-      if (find(S, NontermID).empty())
-        continue;
+      auto It = Goto.find({NontermID, S});
+      if (It != Goto.end())
         OS.indent(4) << llvm::formatv("'{0}': go to state {1}\n",
-                                    G.symbolName(NontermID),
-                                    getGoToState(S, NontermID));
+                                      G.symbolName(NontermID), It->second);
     }
   }
   return OS.str();
 }
 
 llvm::Optional<LRTable::StateID>
 LRTable::getShiftState(StateID State, SymbolID Terminal) const {
   assert(pseudo::isToken(Terminal) && "expected terminal symbol!");
-  for (const auto &Result : find(State, Terminal))
-    if (Result.kind() == Action::Shift)
-      return Result.getShiftState();
+  auto It = Shift.find({Terminal, State});
+  if (It == Shift.end())
     return llvm::None;
-}
-
-llvm::ArrayRef<LRTable::Action> LRTable::getActions(StateID State,
-                                                    SymbolID Terminal) const {
-  assert(pseudo::isToken(Terminal) && "expect terminal symbol!");
-  return find(State, Terminal);
+  return It->second;
 }
 
 LRTable::StateID LRTable::getGoToState(StateID State,
                                        SymbolID Nonterminal) const {
   assert(pseudo::isNonterminal(Nonterminal) && "expected nonterminal symbol!");
-  auto Result = find(State, Nonterminal);
-  assert(Result.size() == 1 && Result.front().kind() == Action::GoTo);
-  return Result.front().getGoToState();
-}
-
-llvm::ArrayRef<LRTable::Action> LRTable::find(StateID Src, SymbolID ID) const {
-  assert(Src + 1u < StateOffset.size());
-  std::pair<size_t, size_t> Range =
-      std::make_pair(StateOffset[Src], StateOffset[Src + 1]);
-  auto SymbolRange = llvm::makeArrayRef(Symbols.data() + Range.first,
-                                        Symbols.data() + Range.second);
-
-  assert(llvm::is_sorted(SymbolRange) &&
-         "subrange of the Symbols should be sorted!");
-  const LRTable::StateID *Start =
-      llvm::partition_point(SymbolRange, [&ID](SymbolID S) { return S < ID; });
-  if (Start == SymbolRange.end())
-    return {};
-  const LRTable::StateID *End = Start;
-  while (End != SymbolRange.end() && *End == ID)
-    ++End;
-  return llvm::makeArrayRef(&Actions[Start - Symbols.data()],
-                            /*length=*/End - Start);
+  auto It = Goto.find({Nonterminal, State});
+  assert(It != Goto.end());
+  return It->second;
 }
 
 LRTable::StateID LRTable::getStartState(SymbolID Target) const {
   assert(llvm::is_sorted(StartStates) && "StartStates must be sorted!");
   auto It = llvm::partition_point(
       StartStates, [Target](const std::pair<SymbolID, StateID> &X) {
         return X.first < Target;
       });
   assert(It != StartStates.end() && It->first == Target &&
          "target symbol doesn't have a start state!");
   return It->second;
 }
 
 } // namespace pseudo
 } // namespace clang

clang-tools-extra/pseudo/lib/grammar/LRTableBuild.cpp

 //===--- LRTableBuild.cpp - Build a LRTable from LRGraph ---------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang-pseudo/grammar/Grammar.h"
 #include "clang-pseudo/grammar/LRGraph.h"
 #include "clang-pseudo/grammar/LRTable.h"
-#include "clang/Basic/TokenKinds.h"
 #include <cstdint>
 
 namespace llvm {
 template <> struct DenseMapInfo<clang::pseudo::LRTable::Entry> {
   using Entry = clang::pseudo::LRTable::Entry;
   static inline Entry getEmptyKey() {
     static Entry E{static_cast<clang::pseudo::SymbolID>(-1), 0,
                    clang::pseudo::LRTable::Action::sentinel()};

 
 class LRTable::Builder {
 public:
   Builder(llvm::ArrayRef<std::pair<SymbolID, StateID>> StartStates)
       : StartStates(StartStates) {}
 
   bool insert(Entry E) { return Entries.insert(std::move(E)).second; }
   LRTable build(const GrammarTable &GT, unsigned NumStates) && {
-    // E.g. given the following parsing table with 3 states and 3 terminals:
-    //
-    //            a    b     c
-    // +-------+----+-------+-+
-    // |state0 |    | s0,r0 | |
-    // |state1 | acc|       | |
-    // |state2 |    |  r1   | |
-    // +-------+----+-------+-+
-    //
-    // The final LRTable:
-    //  - StateOffset: [s0] = 0, [s1] = 2, [s2] = 3, [sentinel] = 4
-    //  - Symbols:     [ b,   b,   a,  b]
-    //    Actions:     [ s0, r0, acc, r1]
-    //                   ~~~~~~ range for state 0
-    //                           ~~~~ range for state 1
-    //                                ~~ range for state 2
-    // First step, we sort all entries by (State, Symbol, Action).
-    std::vector<Entry> Sorted(Entries.begin(), Entries.end());
-    llvm::sort(Sorted, [](const Entry &L, const Entry &R) {
-      return std::forward_as_tuple(L.State, L.Symbol, L.Act.opaque()) <
-             std::forward_as_tuple(R.State, R.Symbol, R.Act.opaque());
-    });
-
+    llvm::DenseMap<std::pair<StateID, RuleID>, Reduce> Reduces;
     LRTable Table;
-    Table.Actions.reserve(Sorted.size());
-    Table.Symbols.reserve(Sorted.size());
-    // We are good to finalize the States and Actions.
-    for (const auto &E : Sorted) {
-      Table.Actions.push_back(E.Act);
-      Table.Symbols.push_back(E.Symbol);
-    }
-    // Initialize the terminal and nonterminal offset, all ranges are empty by
-    // default.
-    Table.StateOffset = std::vector<uint32_t>(NumStates + 1, 0);
-    size_t SortedIndex = 0;
-    for (StateID State = 0; State < Table.StateOffset.size(); ++State) {
-      Table.StateOffset[State] = SortedIndex;
-      while (SortedIndex < Sorted.size() && Sorted[SortedIndex].State == State)
-        ++SortedIndex;
+    for (const auto &E : Entries) {
+      switch (E.Act.kind()) {
+      case Action::Sentinel:
+        break;
+      case Action::Shift:
+        ++Table.NumShift;
+        Table.Shift.try_emplace(std::make_pair(E.Symbol, E.State),
+                                E.Act.getShiftState());
+        break;
+      case Action::GoTo:
+        ++Table.NumGoto;
+        Table.Goto.try_emplace(std::make_pair(E.Symbol, E.State),
+                               E.Act.getGoToState());
+        break;
+      case Action::Reduce:
+        ++Table.NumReduce;
+        auto &R = Reduces[{E.State, E.Act.getReduceRule()}];
+        R.State = E.State;
+        R.Rule = E.Act.getReduceRule();
+        R.Filter.set(symbolToToken(E.Symbol));
+        break;
+      }
+    }
+
+    Table.Reduces.reserve(Reduces.size());
+    for (const auto &R : Reduces)
+      Table.Reduces.push_back(R.second);
+    llvm::sort(Table.Reduces, [](auto &L, auto &R) {
+      return std::tie(L.State, L.Rule) < std::tie(R.State, R.Rule);
+    });
+    Table.ReducesLookup.resize(NumStates + 1);
+    unsigned ReducesIndex = 0;
+    for (StateID S = 0; S < NumStates; ++S) {
+      Table.ReducesLookup[S] = ReducesIndex;
+      while (ReducesIndex < Reduces.size() &&
+             Table.Reduces[ReducesIndex].State == S)
+        ReducesIndex++;
     }
+    Table.ReducesLookup[NumStates] = ReducesIndex;
     Table.StartStates = std::move(StartStates);
     return Table;
   }
 
 private:
   llvm::DenseSet<Entry> Entries;
   std::vector<std::pair<SymbolID, StateID>> StartStates;
 };