[Packetizer] Increase the size of DFAInput bitfield to allow up to 32 units

[ThomasRaoux]

Summary

For a new backend in progress we need more than 16 functional units. In order to support that we need to make DFAInput 128 bits. I'm using a pair of uint64_t to be able to keep most of the logic unchanged. It could easily be extended to a general larger tuple if needed.

[jmolloy]

LGTM. I had a look at changing this to use APInt instead, because that seems a little nicer, but this turns out to be nontrivial.

I think really this code needs to be able to distinguish between functional units that need packetizing (VLIW slots) and functional units that are just ... functional units (for the purposes of scheduling).

[jmolloy]

llvm/lib/CodeGen/DFAPacketizer.cpp

56

static

llvm/utils/TableGen/DFAPacketizerEmitter.cpp

68

Formatting is off here.

298

Don't you need InsnInput.second here?

[kparzysz]

This seems to hang when compiling HexagonInstrInfo.cpp.

[kparzysz]

To clarify: clang-8 hangs on HexagonInstrInfo.cpp when compiling current master branch with this patch applied.

[ThomasRaoux]

In D65424#1610454, @kparzysz wrote:

This seems to hang when compiling HexagonInstrInfo.cpp.

I noticed that this change makes the static table twice as large and slow downs significantly compilation time when for files including it. I'm looking at an alternative solution. I might just work around the problem on my side as a different solution would be much more invasive.

I'll update the review once I get more data.

llvm/include/llvm/CodeGen/DFAPacketizer.h

 //      7 terms x 9  bits = 63 bits
 //      6 terms x 10 bits = 60 bits
 //      5 terms x 12 bits = 60 bits
-//      4 terms x 16 bits = 64 bits <--- current
+//      4 terms x 16 bits = 64 bits
 //      3 terms x 21 bits = 63 bits
 //      2 terms x 32 bits = 64 bits
 //
+// e.g. terms x resource bit combinations that fit in pair<uint64_t, uint64_t>:
+//      8 terms x 16  bits = 128 bits
+//      7 terms x 18  bits = 126 bits
+//      6 terms x 21 bits =  126 bits
+//      5 terms x 25 bits =  125 bits
+//      4 terms x 32 bits =  128 bits <--- current
+//      3 terms x 42 bits =  126 bits
+//      2 terms x 64 bits =  128 bits
 #define DFA_MAX_RESTERMS        4   // The max # of AND'ed resource terms.
-#define DFA_MAX_RESOURCES       16  // The max # of resource bits in one term.
+#define DFA_MAX_RESOURCES       32  // The max # of resource bits in one term.
 
-using DFAInput = uint64_t;
-using DFAStateInput = int64_t;
+using DFAInput = std::pair<uint64_t, uint64_t>;
+using DFAStateInput = std::pair<DFAInput, int>;
 
-#define DFA_TBLTYPE             "int64_t" // For generating DFAStateInputTable.
+// For generating DFAStateInputTable.
+#define DFA_TBLTYPE "std::pair<std::pair<uint64_t, uint64_t>, int>"
 // --------------------------------------------------------------------
 
 class DFAPacketizer {

 
   const InstrItineraryData *InstrItins;
   int CurrentState = 0;
-  const DFAStateInput (*DFAStateInputTable)[2];
+  const DFAStateInput *DFAStateInputTable;
   const unsigned *DFAStateEntryTable;
 
   // CachedTable is a map from <FromState, Input> to ToState.

   void ReadTable(unsigned state);
 
 public:
-  DFAPacketizer(const InstrItineraryData *I, const DFAStateInput (*SIT)[2],
+  DFAPacketizer(const InstrItineraryData *I, const DFAStateInput *SIT,
                 const unsigned *SET);
 
   // Reset the current state to make all resources available.

llvm/lib/CodeGen/DFAPacketizer.cpp

 // --------------------------------------------------------------------
 // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp
 
-static DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits) {
-  return (Inp << DFA_MAX_RESOURCES) | FuncUnits;
+DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits) {
+  return DFAInput((Inp.first << DFA_MAX_RESOURCES) |
+               (Inp.second >> (sizeof(Inp.first)*8 - DFA_MAX_RESOURCES)),
+           Inp.second << DFA_MAX_RESOURCES | FuncUnits);
 }
 
 /// Return the DFAInput for an instruction class input vector.
 /// This function is used in both DFAPacketizer.cpp and in
 /// DFAPacketizerEmitter.cpp.
 static DFAInput getDFAInsnInput(const std::vector<unsigned> &InsnClass) {
-  DFAInput InsnInput = 0;
+  DFAInput InsnInput = {};
   assert((InsnClass.size() <= DFA_MAX_RESTERMS) &&
          "Exceeded maximum number of DFA terms");
   for (auto U : InsnClass)

 // --------------------------------------------------------------------
 
 DFAPacketizer::DFAPacketizer(const InstrItineraryData *I,
-                             const DFAStateInput (*SIT)[2],
+                             const DFAStateInput *SIT,
                              const unsigned *SET):
   InstrItins(I), DFAStateInputTable(SIT), DFAStateEntryTable(SET) {
   // Make sure DFA types are large enough for the number of terms & resources.

 // Read the DFA transition table and update CachedTable.
 //
 // Format of the transition tables:
-// DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid
+// DFAStateInputTable[]  = pairs of <Input, Transition> for all valid
 //                           transitions
 // DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable
 //                         for the ith state

   unsigned NextStateInTable = DFAStateEntryTable[state+1];
   // Early exit in case CachedTable has already contains this
   // state's transitions.
-  if (CachedTable.count(UnsignPair(state, DFAStateInputTable[ThisState][0])))
+  if (CachedTable.count(UnsignPair(state, DFAStateInputTable[ThisState].first)))
     return;
 
   for (unsigned i = ThisState; i < NextStateInTable; i++)
-    CachedTable[UnsignPair(state, DFAStateInputTable[i][0])] =
-      DFAStateInputTable[i][1];
+    CachedTable[UnsignPair(state, DFAStateInputTable[i].first)] =
+      DFAStateInputTable[i].second;
 }
 
 // Return the DFAInput for an instruction class.
 DFAInput DFAPacketizer::getInsnInput(unsigned InsnClass) {
   // Note: this logic must match that in DFAPacketizerDefs.h for input vectors.
-  DFAInput InsnInput = 0;
+  DFAInput InsnInput = {};
   unsigned i = 0;
   (void)i;
   for (const InstrStage *IS = InstrItins->beginStage(InsnClass),

llvm/utils/TableGen/DFAPacketizerEmitter.cpp

 #include "llvm/TableGen/Record.h"
 #include "llvm/TableGen/TableGenBackend.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cassert>
 #include <cstdint>

 //      2 terms x 32 bits = 64 bits
 //
 #define DFA_MAX_RESTERMS        4   // The max # of AND'ed resource terms.
-#define DFA_MAX_RESOURCES       16  // The max # of resource bits in one term.
+#define DFA_MAX_RESOURCES       32  // The max # of resource bits in one term.
 
-typedef uint64_t                DFAInput;
-typedef int64_t                 DFAStateInput;
-#define DFA_TBLTYPE             "int64_t" // For generating DFAStateInputTable.
+typedef std::pair<uint64_t, uint64_t>  DFAInput;
+typedef std::pair<DFAInput, int>  DFAStateInput;
+
+// For generating DFAStateInputTable.
+#define DFA_TBLTYPE "std::pair<std::pair<uint64_t, uint64_t>, int>"
 
 namespace {
 
-  DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits) {
-    return (Inp << DFA_MAX_RESOURCES) | FuncUnits;
-  }
+  static_assert(DFA_MAX_RESOURCES < sizeof(Inp.first)*8,
+      "this formula assumes the shift amount is smaller than the element size");
+  return DFAInput((Inp.first << DFA_MAX_RESOURCES) |
+               (Inp.second >> (sizeof(Inp.first)*8 - DFA_MAX_RESOURCES)),
+           Inp.second << DFA_MAX_RESOURCES | FuncUnits);
+}
 
   /// Return the DFAInput for an instruction class input vector.
   /// This function is used in both DFAPacketizer.cpp and in
   /// DFAPacketizerEmitter.cpp.
   DFAInput getDFAInsnInput(const std::vector<unsigned> &InsnClass) {
-    DFAInput InsnInput = 0;
+    DFAInput InsnInput = {};
     assert((InsnClass.size() <= DFA_MAX_RESTERMS) &&
            "Exceeded maximum number of DFA terms");
     for (auto U : InsnClass)

     LLVM_DEBUG(dbgs() << "0x" << Twine::utohexstr(InsnClass[i]));
   }
   DFAInput InsnInput = getDFAInsnInput(InsnClass);
-  LLVM_DEBUG(dbgs() << " (input: 0x" << Twine::utohexstr(InsnInput) << ")");
+  LLVM_DEBUG(dbgs() << " (input: 0x"
+                    << llvm::FormattedNumber(InsnInput.first, 0, /*width*/ 8,
+                                             /*Hex*/ true, false, false)
+                    << llvm::FormattedNumber(InsnInput.first, 0, /*width*/ 8,
+                                             /*Hex*/ true, false, false)
+                    << ")");
 }
 
 //

   OS << "// " << numCombos << "\tcombo resources\n";
   OS << "// " << maxStages << "\tstages max\n";
   OS << "const " << DFA_TBLTYPE << " "
-     << TargetName << "DFAStateInputTable[][2] = {\n";
+     << TargetName << "DFAStateInputTable[] = {\n";
 
   // This table provides a map to the beginning of the transitions for State s
   // in DFAStateInputTable.
   std::vector<int> StateEntry(numStates+1);
-  static const std::string SentinelEntry = "{-1, -1}";
+  static const std::string SentinelEntry = "{{-1, -1}, -1}";
 
   // Tracks the total valid transitions encountered so far. It is used
   // to construct the StateEntry table.

   for (unsigned i = 0; i < numStates; ++i, ++SI) {
     assert ((SI->stateNum == (int) i) && "Mismatch in state numbers");
     StateEntry[i] = ValidTransitions;
-    for (State::TransitionMap::iterator
-        II = SI->Transitions.begin(), IE = SI->Transitions.end();
+    for (State::TransitionMap::iterator II = SI->Transitions.begin(),
+                                        IE = SI->Transitions.end();
          II != IE; ++II) {
-      OS << "{0x" << Twine::utohexstr(getDFAInsnInput(II->first)) << ", "
+      OS << "{{0x"
+         << Twine::utohexstr(getDFAInsnInput(II->first).first) << ",0x"
+         << Twine::utohexstr(getDFAInsnInput(II->first).second) << "}, "
          << II->second->stateNum << "},\t";
     }
     ValidTransitions += SI->Transitions.size();

     // Convert macros to bits for each stage.
     unsigned numFUs = FUs.size();
     for (unsigned j = 0; j < numFUs; ++j) {
-      assert ((j < DFA_MAX_RESOURCES) &&
-                      "Exceeded maximum number of representable resources");
+      if (j >= DFA_MAX_RESOURCES)
+        report_fatal_error(
+            "Exceeded maximum number of representable resources");
       unsigned FuncResources = (unsigned) (1U << j);
       FUNameToBitsMap[FUs[j]->getName()] = FuncResources;
       LLVM_DEBUG(dbgs() << " " << FUs[j]->getName() << ":0x"