[DFAPacketizer] Track resources for packetized instructions

[jmolloy]

Summary

This patch allows the DFAPacketizer to be queried after a packet is formed to work out which
resources were allocated to the packetized instructions.

This is particularly important for targets that do their own bundle packing - it's not
sufficient to know simply that instructions can share a packet; which slots are used is
also required for encoding.

This extends the emitter to emit a side-table containing resource usage diffs for each
state transition. The packetizer maintains a set of all possible resource states in its
current state. After packetization is complete, all remaining resource states are
possible packetization strategies.

The sidetable is only ~500K for Hexagon, but the extra tracking is disabled by default
(most uses of the packetizer like MachinePipeliner don't care and don't need the extra
maintained state).

[ThomasRaoux]

Your summary says that the extended tracking is disable by default on hexagon. Which extra tracking is that? I don't see any part disabled for Hexagon?

lib/CodeGen/DFAPacketizer.cpp

269 ↗

(On Diff #217824)

This would assert if tracking is off. Is this done on purpose?

[jmolloy]

Hi Thomas,

Thanks for the review!
You're right, we do actually use this in Hexagon (we dump the output so it can be read by FileCheck). Perhaps we should only do this #ifndef NDEBUG.

James

lib/CodeGen/DFAPacketizer.cpp

269 ↗

(On Diff #217824)

Yes, so that we can FileCheck this output and verify the tracking is working. VLIWPacketizer sets tracking on always in the constructor, above.

[RKSimon]

@jmolloy This is causing "compiler is out of heap space" errors on my VS2017 and VS2019 all targets builds:

e:\llvm\ninja17\lib\target\hexagon\hexagongendfapacketizer.inc(4892) : fatal error C1002: compiler is out of heap space in pass 2

[RKSimon]

In D66936#1662832, @RKSimon wrote:

@jmolloy This is causing "compiler is out of heap space" errors on my VS2017 and VS2019 all targets builds:

e:\llvm\ninja17\lib\target\hexagon\hexagongendfapacketizer.inc(4892) : fatal error C1002: compiler is out of heap space in pass 2

I'm sorry but I had to revert this at rL371393, I didn't get very far in triaging what is the causing the issue but if you have a candidate patch I'm happy to test it.

[RKSimon]

Thanks @jmolloy rL371399 looks OK

llvm/include/llvm/CodeGen/DFAPacketizer.h

 class DFAPacketizer {
 private:
   using UnsignPair = std::pair<unsigned, DFAInput>;
 
   const InstrItineraryData *InstrItins;
   int CurrentState = 0;
   const DFAStateInput (*DFAStateInputTable)[2];
   const unsigned *DFAStateEntryTable;
+  const std::pair<unsigned, unsigned> *DFAResourceTransitionTable;
+  const unsigned *DFAResourceTransitionEntryTable;
 
   // CachedTable is a map from <FromState, Input> to ToState.
   DenseMap<UnsignPair, unsigned> CachedTable;
+  // CachedResourceTransitions is a map from <FromState, Input> to a list of
+  // resource transitions.
+  DenseMap<UnsignPair, ArrayRef<std::pair<unsigned, unsigned>>>
+      CachedResourceTransitions;
 
   // Read the DFA transition table and update CachedTable.
   void ReadTable(unsigned state);
 
+  bool TrackResources = false;
+  // State for the current packet. Every entry is a possible packing of the
+  // bundle, indexed by cumulative resource state. Each entry is a list of the
+  // cumulative resource states after packing each instruction. For example if
+  // we pack I0: [0x4] and I1: [0x2] we will end up with:
+  //   ResourceStates[0x6] = [0x4, 0x6]
+  DenseMap<unsigned, SmallVector<unsigned, 8>> ResourceStates;
+
 public:
   DFAPacketizer(const InstrItineraryData *I, const DFAStateInput (*SIT)[2],
-                const unsigned *SET);
+                const unsigned *SET,
+                const std::pair<unsigned, unsigned> *RTT = nullptr,
+                const unsigned *RTET = nullptr);
 
   // Reset the current state to make all resources available.
   void clearResources() {
     CurrentState = 0;
+    ResourceStates.clear();
+    ResourceStates[0] = {};
+  }
+
+  // Set whether this packetizer should track not just whether instructions
+  // can be packetized, but also which functional units each instruction ends up
+  // using after packetization.
+  void setTrackResources(bool Track) {
+    if (Track != TrackResources) {
+      TrackResources = Track;
+      if (Track) {
+        CachedTable.clear();
+        assert(DFAResourceTransitionEntryTable);
+        assert(DFAResourceTransitionTable);
+      }
+    }
+    assert(CurrentState == 0 && "Can only change TrackResources on an empty packetizer!");
   }
 
   // Return the DFAInput for an instruction class.
   DFAInput getInsnInput(unsigned InsnClass);
 
   // Return the DFAInput for an instruction class input vector.
   static DFAInput getInsnInput(const std::vector<unsigned> &InsnClass);
 
   // Check if the resources occupied by a MCInstrDesc are available in
   // the current state.
   bool canReserveResources(const MCInstrDesc *MID);
 
   // Reserve the resources occupied by a MCInstrDesc and change the current
   // state to reflect that change.
   void reserveResources(const MCInstrDesc *MID);
 
   // Check if the resources occupied by a machine instruction are available
   // in the current state.
   bool canReserveResources(MachineInstr &MI);
 
   // Reserve the resources occupied by a machine instruction and change the
   // current state to reflect that change.
   void reserveResources(MachineInstr &MI);
 
+  // Return the resources used by the InstIdx'th instruction added to this
+  // packet. The resources are returned as a bitvector of functional units.
+  //
+  // Note that a bundle may be packed in multiple valid ways. This function
+  // returns one arbitary valid packing.
+  //
+  // Requires setTrackResources(true) to have been called.
+  unsigned getUsedResources(unsigned InstIdx);
+
   const InstrItineraryData *getInstrItins() const { return InstrItins; }
 };
 
 // VLIWPacketizerList implements a simple VLIW packetizer using DFA. The
 // packetizer works on machine basic blocks. For each instruction I in BB,
 // the packetizer consults the DFA to see if machine resources are available
 // to execute I. If so, the packetizer checks if I depends on any instruction
 // in the current packet. If no dependency is found, I is added to current

llvm/lib/CodeGen/DFAPacketizer.cpp

 // models the addition of an instruction to a packet. In the DFA constructed
 // by this class, if an instruction can be added to a packet, then a valid
 // transition exists from the corresponding state. Invalid transitions
 // indicate that the instruction cannot be added to the current packet.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/DFAPacketizer.h"
+#include "llvm/ADT/StringExtras.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBundle.h"
 #include "llvm/CodeGen/ScheduleDAG.h"
 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/MC/MCInstrDesc.h"
static DFAInput getDFAInsnInput(const std::vector<unsigned> &InsnClass) {
   for (auto U : InsnClass)
     InsnInput = addDFAFuncUnits(InsnInput, U);
   return InsnInput;
 }
 
 // --------------------------------------------------------------------
 
 DFAPacketizer::DFAPacketizer(const InstrItineraryData *I,
-                             const DFAStateInput (*SIT)[2],
-                             const unsigned *SET):
-  InstrItins(I), DFAStateInputTable(SIT), DFAStateEntryTable(SET) {
+                             const DFAStateInput (*SIT)[2], const unsigned *SET,
+                             const std::pair<unsigned, unsigned> *RTT,
+                             const unsigned *RTET)
+    : InstrItins(I), DFAStateInputTable(SIT), DFAStateEntryTable(SET),
+      DFAResourceTransitionTable(RTT), DFAResourceTransitionEntryTable(RTET) {
   // Make sure DFA types are large enough for the number of terms & resources.
   static_assert((DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <=
                     (8 * sizeof(DFAInput)),
                 "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAInput");
   static_assert(
       (DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <= (8 * sizeof(DFAStateInput)),
       "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAStateInput");
+  clearResources();
 }
 
 // Read the DFA transition table and update CachedTable.
 //
 // Format of the transition tables:
 // DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid
 //                           transitions
 // DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable
 //                         for the ith state
 //
 void DFAPacketizer::ReadTable(unsigned int state) {
-  unsigned ThisState = DFAStateEntryTable[state];
-  unsigned NextStateInTable = DFAStateEntryTable[state+1];
+  unsigned ThisStateIdx = DFAStateEntryTable[state];
+  unsigned NextStateIdxInTable = 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[ThisStateIdx][0])))
     return;
 
-  for (unsigned i = ThisState; i < NextStateInTable; i++)
-    CachedTable[UnsignPair(state, DFAStateInputTable[i][0])] =
-      DFAStateInputTable[i][1];
+  for (unsigned TransitionIdx = ThisStateIdx;
+       TransitionIdx < NextStateIdxInTable; TransitionIdx++) {
+    auto TransitionPair =
+        UnsignPair(state, DFAStateInputTable[TransitionIdx][0]);
+    CachedTable[TransitionPair] = DFAStateInputTable[TransitionIdx][1];
+
+    if (TrackResources) {
+      unsigned I = DFAResourceTransitionEntryTable[TransitionIdx];
+      unsigned E = DFAResourceTransitionEntryTable[TransitionIdx + 1];
+      CachedResourceTransitions[TransitionPair] = makeArrayRef(
+          &DFAResourceTransitionTable[I], &DFAResourceTransitionTable[E]);
+    }
+  }
 }
 
 // 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;
   unsigned i = 0;
   (void)i;

 
 // Reserve the resources occupied by a MCInstrDesc and change the current
 // state to reflect that change.
 void DFAPacketizer::reserveResources(const MCInstrDesc *MID) {
   unsigned InsnClass = MID->getSchedClass();
   DFAInput InsnInput = getInsnInput(InsnClass);
   UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput);
   ReadTable(CurrentState);
+
+  if (TrackResources) {
+    DenseMap<unsigned, SmallVector<unsigned, 8>> NewResourceStates;
+    for (const auto &KV : CachedResourceTransitions[StateTrans]) {
+      assert(ResourceStates.count(KV.first));
+      NewResourceStates[KV.second] = ResourceStates[KV.first];
+      NewResourceStates[KV.second].push_back(KV.second);
+    }
+    ResourceStates = NewResourceStates;
+  }
   assert(CachedTable.count(StateTrans) != 0);
   CurrentState = CachedTable[StateTrans];
 }
 
 // Check if the resources occupied by a machine instruction are available
 // in the current state.
 bool DFAPacketizer::canReserveResources(MachineInstr &MI) {
   const MCInstrDesc &MID = MI.getDesc();
   return canReserveResources(&MID);
 }
 
 // Reserve the resources occupied by a machine instruction and change the
 // current state to reflect that change.
 void DFAPacketizer::reserveResources(MachineInstr &MI) {
   const MCInstrDesc &MID = MI.getDesc();
   reserveResources(&MID);
 }
 
+unsigned DFAPacketizer::getUsedResources(unsigned InstIdx) {
+  assert(TrackResources && "getUsedResources requires resource tracking!");
+  // Assert that there is at least one example of a valid bundle format.
+  assert(!ResourceStates.empty() && "Invalid bundle!");
+  SmallVectorImpl<unsigned> &RS = ResourceStates.begin()->second;
+
+  // RS stores the cumulative resources used up to and including the I'th
+  // instruction. The 0th instruction is the base case.
+  if (InstIdx == 0)
+    return RS[0];
+  // Return the difference between the cumulative resources used by InstIdx and
+  // its predecessor.
+  return RS[InstIdx] ^ RS[InstIdx - 1];
+}
+
 namespace llvm {
 
 // This class extends ScheduleDAGInstrs and overrides the schedule method
 // to build the dependence graph.
 class DefaultVLIWScheduler : public ScheduleDAGInstrs {
 private:
   AliasAnalysis *AA;
   /// Ordered list of DAG postprocessing steps.
void DefaultVLIWScheduler::schedule() {
   buildSchedGraph(AA);
   postprocessDAG();
 }
 
 VLIWPacketizerList::VLIWPacketizerList(MachineFunction &mf,
                                        MachineLoopInfo &mli, AliasAnalysis *aa)
     : MF(mf), TII(mf.getSubtarget().getInstrInfo()), AA(aa) {
   ResourceTracker = TII->CreateTargetScheduleState(MF.getSubtarget());
+  ResourceTracker->setTrackResources(true);
   VLIWScheduler = new DefaultVLIWScheduler(MF, mli, AA);
 }
 
 VLIWPacketizerList::~VLIWPacketizerList() {
   delete VLIWScheduler;
   delete ResourceTracker;
 }
 
 // End the current packet, bundle packet instructions and reset DFA state.
 void VLIWPacketizerList::endPacket(MachineBasicBlock *MBB,
                                    MachineBasicBlock::iterator MI) {
   LLVM_DEBUG({
     if (!CurrentPacketMIs.empty()) {
       dbgs() << "Finalizing packet:\n";
-      for (MachineInstr *MI : CurrentPacketMIs)
-        dbgs() << " * " << *MI;
+      unsigned Idx = 0;
+      for (MachineInstr *MI : CurrentPacketMIs) {
+        unsigned R = ResourceTracker->getUsedResources(Idx++);
+        dbgs() << " * [res:0x" << utohexstr(R) << "] " << *MI;
+      }
     }
   });
   if (CurrentPacketMIs.size() > 1) {
     MachineInstr &MIFirst = *CurrentPacketMIs.front();
     finalizeBundle(*MBB, MIFirst.getIterator(), MI.getInstrIterator());
   }
   CurrentPacketMIs.clear();
   ResourceTracker->clearResources();

llvm/lib/Target/Hexagon/HexagonVLIWPacketizer.cpp

 #include "HexagonVLIWPacketizer.h"
 #include "Hexagon.h"
 #include "HexagonInstrInfo.h"
 #include "HexagonRegisterInfo.h"
 #include "HexagonSubtarget.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringExtras.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
HexagonPacketizerList::addToPacket(MachineInstr &MI) {
 
   CurrentPacketMIs.push_back(&MI);
   return MII;
 }
 
 void HexagonPacketizerList::endPacket(MachineBasicBlock *MBB,
                                       MachineBasicBlock::iterator EndMI) {
   // Replace VLIWPacketizerList::endPacket(MBB, EndMI).
+  LLVM_DEBUG({
+    if (!CurrentPacketMIs.empty()) {
+      dbgs() << "Finalizing packet:\n";
+      unsigned Idx = 0;
+      for (MachineInstr *MI : CurrentPacketMIs) {
+        unsigned R = ResourceTracker->getUsedResources(Idx++);
+        dbgs() << " * [res:0x" << utohexstr(R) << "] " << *MI;
+      }
+    }
+  });
 
   bool memShufDisabled = getmemShufDisabled();
   if (memShufDisabled && !foundLSInPacket()) {
     setmemShufDisabled(false);
     LLVM_DEBUG(dbgs() << "  Not added to NoShufPacket\n");
   }
   memShufDisabled = getmemShufDisabled();
 

llvm/test/CodeGen/Hexagon/packetizer-resources.ll

+; RUN: llc -O2 -march=hexagon < %s -debug-only=packets 2>&1 | FileCheck %s
+; REQUIRES: asserts
+
+; CHECK: Finalizing packet:
+; CHECK-NEXT: * [res:0x8] renamable $r1 = S2_vsplatrb renamable $r0
+; CHECK-NEXT: * [res:0x4] renamable $d1 = S2_vsplatrh killed renamable $r0
+
+target triple = "hexagon"
+
+; Function Attrs: nounwind readnone
+define i64 @f0(i64 %a0) #0 {
+b0:
+  %v0 = trunc i64 %a0 to i32
+  %v1 = and i32 %v0, 65535
+  %v2 = tail call i64 @llvm.hexagon.S2.vsplatrh(i32 %v1)
+  %v3 = and i32 %v0, 255
+  %v4 = tail call i32 @llvm.hexagon.S2.vsplatrb(i32 %v3)
+  %v5 = sext i32 %v4 to i64
+  %v6 = add nsw i64 %v5, %v2
+  ret i64 %v6
+}
+
+; Function Attrs: nounwind readnone
+declare i64 @llvm.hexagon.S2.vsplatrh(i32) #0
+
+; Function Attrs: nounwind readnone
+declare i32 @llvm.hexagon.S2.vsplatrb(i32) #0
+
+attributes #0 = { nounwind readnone }

llvm/utils/TableGen/DFAPacketizerEmitter.cpp

 class State {
  public:
   static int currentStateNum;
   // stateNum is the only member used for equality/ordering, all other members
   // can be mutated even in const State objects.
   const int stateNum;
   mutable bool isInitial;
   mutable std::set<unsigned> stateInfo;
-  typedef std::map<std::vector<unsigned>, const State *> TransitionMap;
+
+  struct TransitionInfo {
+    // Maps from a resource bitmask in this state to the equivalent resource
+    // bitmap in the transitioned-to state. This is a 1-to-N mapping.
+    std::vector<std::pair<unsigned, unsigned>> ResourceTransitions;
+    const State *S;
+  };
+  using TransitionMap = std::map<std::vector<unsigned>, TransitionInfo>;
   mutable TransitionMap Transitions;
 
   State();
 
   bool operator<(const State &s) const {
     return stateNum < s.stateNum;
   }
 
public:
 
   //
   // AddInsnClass - Return all combinations of resource reservation
   // which are possible from this state (PossibleStates).
   //
   // PossibleStates is the set of valid resource states that ensue from valid
   // transitions.
   //
-  void AddInsnClass(std::vector<unsigned> &InsnClass,
-                        std::map<unsigned, unsigned> &ComboBitToBitsMap,
-                        std::set<unsigned> &PossibleStates) const;
+  // TransitionInfo maps from a resource bitmask B in this state to a resource
+  // bitmask B' in PossibleStates. This is a one-to-many (or none) mapping.
+  //
+  void AddInsnClass(
+      std::vector<unsigned> &InsnClass,
+      std::set<unsigned> &PossibleStates,
+      std::vector<std::pair<unsigned, unsigned>> &TransitionInfo) const;
 
   //
   // AddInsnClassStages - Return all combinations of resource reservation
   // resulting from the cross product of all stages for this InsnClass
   // which are possible from this state (PossibleStates).
   //
   void AddInsnClassStages(std::vector<unsigned> &InsnClass,
                           std::map<unsigned, unsigned> &ComboBitToBitsMap,
                           unsigned chkstage, unsigned numstages,
                           unsigned prevState, unsigned origState,
-                        DenseSet<unsigned> &VisitedResourceStates,
-                        std::set<unsigned> &PossibleStates) const;
+                          DenseSet<unsigned> &VisitedResourceStates) const;
 
   //
-  // addTransition - Add a transition from this state given the input InsnClass
+  // addTransition - Add a transition from this state given the input InsnClass.
   //
-  void addTransition(std::vector<unsigned> InsnClass, const State *To) const;
+  void addTransition(
+      std::vector<unsigned> InsnClass, const State *To,
+      const std::vector<std::pair<unsigned, unsigned>> &TransitionInfo) const;
 
   //
   // hasTransition - Returns true if there is a transition from this state
   // given the input InsnClass
   //
   bool hasTransition(std::vector<unsigned> InsnClass) const;
 };
 

 // Constructors and destructors for State and DFA
 //
 State::State() :
   stateNum(currentStateNum++), isInitial(false) {}
 
 //
 // addTransition - Add a transition from this state given the input InsnClass
 //
-void State::addTransition(std::vector<unsigned> InsnClass, const State *To)
-      const {
+void State::addTransition(
+    std::vector<unsigned> InsnClass, const State *To,
+    const std::vector<std::pair<unsigned, unsigned>> &TransitionInfo) const {
   assert(!Transitions.count(InsnClass) &&
       "Cannot have multiple transitions for the same input");
-  Transitions[InsnClass] = To;
+  Transitions[InsnClass] = {TransitionInfo, To};
 }
 
 //
 // hasTransition - Returns true if there is a transition from this state
 // given the input InsnClass
 //
 bool State::hasTransition(std::vector<unsigned> InsnClass) const {
   return Transitions.count(InsnClass) > 0;
 }
 
 //
 // AddInsnClass - Return all combinations of resource reservation
 // which are possible from this state (PossibleStates).
 //
 // PossibleStates is the set of valid resource states that ensue from valid
 // transitions.
 //
-void State::AddInsnClass(std::vector<unsigned> &InsnClass,
-                        std::map<unsigned, unsigned> &ComboBitToBitsMap,
-                        std::set<unsigned> &PossibleStates) const {
+void State::AddInsnClass(
+    std::vector<unsigned> &InsnClass,
+    std::set<unsigned> &PossibleStates,
+    std::vector<std::pair<unsigned, unsigned>> &TransitionInfo) const {
   //
   // Iterate over all resource states in currentState.
   //
   unsigned numstages = InsnClass.size();
   assert((numstages > 0) && "InsnClass has no stages");
 
   for (std::set<unsigned>::iterator SI = stateInfo.begin();
        SI != stateInfo.end(); ++SI) {
-    unsigned thisState = *SI;
+    unsigned ThisState = *SI;
 
     DenseSet<unsigned> VisitedResourceStates;
 
-    LLVM_DEBUG(dbgs() << "  thisState: 0x" << Twine::utohexstr(thisState)
+    LLVM_DEBUG(dbgs() << "  thisState: 0x" << Twine::utohexstr(ThisState)
                       << "\n");
-    AddInsnClassStages(InsnClass, ComboBitToBitsMap,
-                                numstages - 1, numstages,
-                                thisState, thisState,
-                                VisitedResourceStates, PossibleStates);
+    AddInsnClassStages(InsnClass, ComboBitToBitsMap, numstages - 1, numstages,
+                       ThisState, ThisState, VisitedResourceStates);
+    for (unsigned NewState : VisitedResourceStates) {
+      PossibleStates.insert(NewState);
+      TransitionInfo.emplace_back(ThisState, NewState);
+    }
   }
 }
 
-void State::AddInsnClassStages(std::vector<unsigned> &InsnClass,
-                        std::map<unsigned, unsigned> &ComboBitToBitsMap,
-                        unsigned chkstage, unsigned numstages,
-                        unsigned prevState, unsigned origState,
-                        DenseSet<unsigned> &VisitedResourceStates,
-                        std::set<unsigned> &PossibleStates) const {
+void State::AddInsnClassStages(
+    std::vector<unsigned> &InsnClass,
+    std::map<unsigned, unsigned> &ComboBitToBitsMap, unsigned chkstage,
+    unsigned numstages, unsigned prevState, unsigned origState,
+    DenseSet<unsigned> &VisitedResourceStates) const {
   assert((chkstage < numstages) && "AddInsnClassStages: stage out of range");
   unsigned thisStage = InsnClass[chkstage];
 
   LLVM_DEBUG({
     dbgsIndent((1 + numstages - chkstage) << 1);
     dbgs() << "AddInsnClassStages " << chkstage << " (0x"
            << Twine::utohexstr(thisStage) << ") from ";
     dbgsInsnClass(InsnClass);
if (resourceMask & thisStage) {
         // that there is at least one resource that can be used to schedule
         // thisStage in the current packet.
         // Insert ResultingResourceState into PossibleStates only if we haven't
         // processed ResultingResourceState before.
         //
         if (ResultingResourceState != prevState) {
           if (VisitedResourceStates.count(ResultingResourceState) == 0) {
             VisitedResourceStates.insert(ResultingResourceState);
-            PossibleStates.insert(ResultingResourceState);
             LLVM_DEBUG(dbgs()
                        << "\tResultingResourceState: 0x"
                        << Twine::utohexstr(ResultingResourceState) << "\n");
           } else {
             LLVM_DEBUG(dbgs() << "\tSkipped Add - state already seen\n");
           }
         } else {
           LLVM_DEBUG(dbgs()
                      << "\tSkipped Add - no final resources available\n");
         }
       } else {
         //
         // If the current resource can be accommodated, check the next
         // stage in InsnClass for available resources.
         //
         if (ResultingResourceState != prevState) {
           LLVM_DEBUG(dbgs() << "\n");
-          AddInsnClassStages(InsnClass, ComboBitToBitsMap,
-                                chkstage - 1, numstages,
-                                ResultingResourceState, origState,
-                                VisitedResourceStates, PossibleStates);
+          AddInsnClassStages(InsnClass, ComboBitToBitsMap, chkstage - 1,
+                             numstages, ResultingResourceState, origState,
+                             VisitedResourceStates);
         } else {
           LLVM_DEBUG(dbgs() << "\tSkipped Add - no resources available\n");
         }
       }
     }
   }
 }
 
void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName,
   DFA::StateSet::iterator SI = states.begin();
   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();
         II != IE; ++II) {
       OS << "{0x" << Twine::utohexstr(getDFAInsnInput(II->first)) << ", "
-         << II->second->stateNum << "},\t";
+         << II->second.S->stateNum << "},\t";
     }
     ValidTransitions += SI->Transitions.size();
 
-    // If there are no valid transitions from this stage, we need a sentinel
-    // transition.
-    if (ValidTransitions == StateEntry[i]) {
-      OS << SentinelEntry << ",\t";
-      ++ValidTransitions;
-    }
-
     OS << " // state " << i << ": " << StateEntry[i];
     if (StateEntry[i] != (ValidTransitions-1)) {   // More than one transition.
        OS << "-" << (ValidTransitions-1);
     }
     OS << "\n";
   }
 
   // Print out a sentinel entry at the end of the StateInputTable. This is
   // needed to iterate over StateInputTable in DFAPacketizer::ReadTable()
   OS << SentinelEntry << "\t";
   OS << " // state " << numStates << ": " << ValidTransitions;
   OS << "\n";
 
   OS << "};\n\n";
   OS << "// " << TargetName << "DFAStateEntryTable[i] = "
      << "Index of the first entry in DFAStateInputTable for\n";
   OS << "//                         "
      << "the ith state.\n";
   OS << "// " << numStates << " states\n";
   OS << "const unsigned int " << TargetName << "DFAStateEntryTable[] = {\n";
 
-  // Multiply i by 2 since each entry in DFAStateInputTable is a set of
-  // two numbers.
   unsigned lastState = 0;
   for (unsigned i = 0; i < numStates; ++i) {
     if (i && ((i % 10) == 0)) {
         lastState = i-1;
         OS << "   // states " << (i-10) << ":" << lastState << "\n";
     }
     OS << StateEntry[i] << ", ";
   }
-
   // Print out the index to the sentinel entry in StateInputTable
   OS << ValidTransitions << ", ";
   OS << "   // states " << (lastState+1) << ":" << numStates << "\n";
   OS << "};\n";
+
+  // Generate the resource transition table.
+  OS << "const std::pair<unsigned, unsigned> " << TargetName
+     << "DFAResourceTransitionTable[] = {  \n";
+  int N = 0;
+  StateEntry.clear();
+  for (const State &S : states) {
+    for (auto &KV : S.Transitions) {
+      StateEntry.push_back(N);
+      for (std::pair<unsigned, unsigned> &T : KV.second.ResourceTransitions) {
+        OS << "{0x" << utohexstr(T.first) << ", 0x" << utohexstr(T.second)
+           << "}, ";
+        ++N;
+      }
+    }
+    OS << "\n  ";
+  }
+  // Add a sentinel entry to terminate the search.
+  StateEntry.push_back(N);
+  OS << "\n  {~0U,~0U}\n};\n\n";
+
+  OS << "// " << TargetName << "DFAResourceTransitionEntryTable[i] = "
+     << "Index of the first entry in DFAResourceTransitionTable for\n";
+  OS << "// the ith transition.\n";
+  OS << "const unsigned int " << TargetName
+     << "DFAResourceTransitionEntryTable[] = {  \n";
+
+  N = 0;
+  for (int S : StateEntry) {
+    OS << S << ",";
+    if (N++ % 10 == 0)
+      OS << "\n  ";
+  }
+  OS << "\n  ~0U\n};\n";
 }
 
 //
 // collectAllFuncUnits - Construct a map of function unit names to bits.
 //
 int DFAPacketizerEmitter::collectAllFuncUnits(
                             std::vector<Record*> &ProcItinList,
                             std::map<std::string, unsigned> &FUNameToBitsMap,
for (unsigned i = 0; i < allInsnClasses.size(); i++) {
       std::set<unsigned> NewStateResources;
       //
       // If we haven't already created a transition for this input
       // and the state can accommodate this InsnClass, create a transition.
       //
       if (!current->hasTransition(InsnClass) &&
           current->canMaybeAddInsnClass(InsnClass, ComboBitToBitsMap)) {
         const State *NewState = nullptr;
-        current->AddInsnClass(InsnClass, ComboBitToBitsMap, NewStateResources);
+        std::vector<std::pair<unsigned, unsigned>> TransitionInfo;
+        current->AddInsnClass(InsnClass, ComboBitToBitsMap, NewStateResources,
+                              TransitionInfo);
         if (NewStateResources.empty()) {
           LLVM_DEBUG(dbgs() << "  Skipped - no new states generated\n");
           continue;
         }
 
         LLVM_DEBUG({
           dbgs() << "\t";
           dbgsStateInfo(NewStateResources);
for (unsigned i = 0; i < allInsnClasses.size(); i++) {
           WorkList.push_back(NewState);
           LLVM_DEBUG({
             dbgs() << "\tAccepted new state: " << NewState->stateNum << " - ";
             dbgsStateInfo(NewState->stateInfo);
             dbgs() << "\n";
           });
         }
 
-        current->addTransition(InsnClass, NewState);
+        current->addTransition(InsnClass, NewState, TransitionInfo);
       }
     }
   }
 
   // Print out the table.
   D.writeTableAndAPI(OS, TargetName + DFAName, numInsnClasses, maxResources,
                      numCombos, maxStages);
 
   OS << "} // end namespace llvm\n";
 
   std::string SubTargetClassName = TargetName + "GenSubtargetInfo";
   OS << "namespace llvm {\n";
   OS << "DFAPacketizer *" << SubTargetClassName << "::"
      << "create" << DFAName
      << "DFAPacketizer(const InstrItineraryData *IID) const {\n"
      << "   return new DFAPacketizer(IID, " << TargetName << DFAName
      << "DFAStateInputTable, " << TargetName << DFAName
-     << "DFAStateEntryTable);\n}\n\n";
+     << "DFAStateEntryTable, " << TargetName << DFAName
+     << "DFAResourceTransitionTable, " << TargetName << DFAName
+     << "DFAResourceTransitionEntryTable"
+     << ");\n}\n\n";
 }
 
 namespace llvm {
 
 void EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) {
   emitSourceFileHeader("Target DFA Packetizer Tables", OS);
   DFAPacketizerEmitter(RK).run(OS);
 }
 
 } // end namespace llvm