Revert r253790: it breaks all builds for some reason.
authorKrzysztof Parzyszek <kparzysz@codeaurora.org>
Sat, 21 Nov 2015 17:38:33 +0000 (17:38 +0000)
committerKrzysztof Parzyszek <kparzysz@codeaurora.org>
Sat, 21 Nov 2015 17:38:33 +0000 (17:38 +0000)
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@253791 91177308-0d34-0410-b5e6-96231b3b80d8

include/llvm/CodeGen/DFAPacketizer.h
include/llvm/Target/TargetItinerary.td
lib/CodeGen/DFAPacketizer.cpp
lib/Target/Hexagon/HexagonScheduleV60.td
utils/TableGen/DFAPacketizerEmitter.cpp

index 4689a2b..791b66e 100644 (file)
@@ -40,47 +40,22 @@ class InstrItineraryData;
 class DefaultVLIWScheduler;
 class SUnit;
 
-// DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput.
-// This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer.
-//
-// e.g. terms x resource bit combinations that fit in uint32_t:
-//      4 terms x 8  bits = 32 bits
-//      3 terms x 10 bits = 30 bits
-//      2 terms x 16 bits = 32 bits
-//
-// e.g. terms x resource bit combinations that fit in uint64_t:
-//      8 terms x 8  bits = 64 bits
-//      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
-//      3 terms x 21 bits = 63 bits
-//      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.
-
-typedef uint64_t                DFAInput;
-typedef int64_t                 DFAStateInput;
-#define DFA_TBLTYPE             "int64_t" // For generating DFAStateInputTable.
-
 class DFAPacketizer {
 private:
-  typedef std::pair<unsigned, DFAInput> UnsignPair;
-
+  typedef std::pair<unsigned, unsigned> UnsignPair;
   const InstrItineraryData *InstrItins;
   int CurrentState;
-  const DFAStateInput (*DFAStateInputTable)[2];
+  const int (*DFAStateInputTable)[2];
   const unsigned *DFAStateEntryTable;
 
   // CachedTable is a map from <FromState, Input> to ToState.
   DenseMap<UnsignPair, unsigned> CachedTable;
 
   // ReadTable - Read the DFA transition table and update CachedTable.
-  void ReadTable(unsigned state);
+  void ReadTable(unsigned int state);
 
 public:
-  DFAPacketizer(const InstrItineraryData *I, const DFAStateInput (*SIT)[2],
+  DFAPacketizer(const InstrItineraryData *I, const int (*SIT)[2],
                 const unsigned *SET);
 
   // Reset the current state to make all resources available.
@@ -88,21 +63,6 @@ public:
     CurrentState = 0;
   }
 
-  // getInsnInput - Return the DFAInput for an instruction class.
-  DFAInput getInsnInput(unsigned InsnClass);
-
-  // getInsnInput - Return the DFAInput for an instruction class input vector.
-  static DFAInput getInsnInput(const std::vector<unsigned> &InsnClass) {
-    DFAInput InsnInput = 0;
-    unsigned N = InsnClass.size();
-    assert ((N <= DFA_MAX_RESTERMS) && "Exceeded maximum number of DFA terms");
-    for (unsigned i = 0; i < N; i++) {
-      InsnInput <<= DFA_MAX_RESOURCES;  // Shift over any previous AND'ed terms.
-      InsnInput |= InsnClass[i];
-    }
-    return(InsnInput);
-  }
-
   // canReserveResources - Check if the resources occupied by a MCInstrDesc
   // are available in the current state.
   bool canReserveResources(const llvm::MCInstrDesc *MID);
index a37bbf2..cc74006 100644 (file)
@@ -134,19 +134,3 @@ class ProcessorItineraries<list<FuncUnit> fu, list<Bypass> bp,
 // info. Subtargets using NoItineraries can bypass the scheduler's
 // expensive HazardRecognizer because no reservation table is needed.
 def NoItineraries : ProcessorItineraries<[], [], []>;
-
-//===----------------------------------------------------------------------===//
-// Combo Function Unit data - This is a map of combo function unit names to
-// the list of functional units that are included in the combination.
-//
-class ComboFuncData<FuncUnit ComboFunc, list<FuncUnit> funclist> {
-  FuncUnit TheComboFunc = ComboFunc;
-  list<FuncUnit> FuncList = funclist;
-}
-
-//===----------------------------------------------------------------------===//
-// Combo Function Units - This is a list of all combo function unit data.
-class ComboFuncUnits<list<ComboFuncData> cfd> {
-  list<ComboFuncData> CFD = cfd;
-}
-
index 40450b4..ee50f97 100644 (file)
 #include "llvm/Target/TargetInstrInfo.h"
 using namespace llvm;
 
-DFAPacketizer::DFAPacketizer(const InstrItineraryData *I,
-                             const DFAStateInput (*SIT)[2],
+DFAPacketizer::DFAPacketizer(const InstrItineraryData *I, const int (*SIT)[2],
                              const unsigned *SET):
   InstrItins(I), CurrentState(0), DFAStateInputTable(SIT),
-  DFAStateEntryTable(SET) {
-  // Make sure DFA types are large enough for the number of terms & resources.
-  assert((DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <= (8 * sizeof(DFAInput))
-        && "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAInput");
-  assert((DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <= (8 * sizeof(DFAStateInput))
-        && "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAStateInput");
-}
+  DFAStateEntryTable(SET) {}
 
 
 //
@@ -67,40 +60,26 @@ void DFAPacketizer::ReadTable(unsigned int state) {
       DFAStateInputTable[i][1];
 }
 
-//
-// getInsnInput - Return the DFAInput for an instruction class.
-//
-DFAInput DFAPacketizer::getInsnInput(unsigned InsnClass) {
-  // note: this logic must match that in DFAPacketizer.h for input vectors
-  DFAInput InsnInput = 0;
-  unsigned i = 0;
-  for (const InstrStage *IS = InstrItins->beginStage(InsnClass),
-        *IE = InstrItins->endStage(InsnClass); IS != IE; ++IS, ++i) {
-    unsigned FuncUnits = IS->getUnits();
-    InsnInput <<= DFA_MAX_RESOURCES;  // Shift over any previous AND'ed terms.
-    InsnInput |= FuncUnits;
-    assert ((i < DFA_MAX_RESTERMS) && "Exceeded maximum number of DFA inputs");
-  }
-
-  return InsnInput;
-}
 
 // canReserveResources - Check if the resources occupied by a MCInstrDesc
 // are available in the current state.
 bool DFAPacketizer::canReserveResources(const llvm::MCInstrDesc *MID) {
   unsigned InsnClass = MID->getSchedClass();
-  DFAInput InsnInput = getInsnInput(InsnClass);
-  UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput);
+  const llvm::InstrStage *IS = InstrItins->beginStage(InsnClass);
+  unsigned FuncUnits = IS->getUnits();
+  UnsignPair StateTrans = UnsignPair(CurrentState, FuncUnits);
   ReadTable(CurrentState);
   return (CachedTable.count(StateTrans) != 0);
 }
 
+
 // reserveResources - Reserve the resources occupied by a MCInstrDesc and
 // change the current state to reflect that change.
 void DFAPacketizer::reserveResources(const llvm::MCInstrDesc *MID) {
   unsigned InsnClass = MID->getSchedClass();
-  DFAInput InsnInput = getInsnInput(InsnClass);
-  UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput);
+  const llvm::InstrStage *IS = InstrItins->beginStage(InsnClass);
+  unsigned FuncUnits = IS->getUnits();
+  UnsignPair StateTrans = UnsignPair(CurrentState, FuncUnits);
   ReadTable(CurrentState);
   assert(CachedTable.count(StateTrans) != 0);
   CurrentState = CachedTable[StateTrans];
index 2ccff82..7cda4a7 100644 (file)
@@ -20,15 +20,6 @@ def CVI_XLSHF  : FuncUnit;
 def CVI_MPY01  : FuncUnit;
 def CVI_ALL    : FuncUnit;
 
-// Combined functional unit data.
-def HexagonComboFuncsV60 :
-    ComboFuncUnits<[
-      ComboFuncData<CVI_XLSHF    , [CVI_XLANE, CVI_SHIFT]>,
-      ComboFuncData<CVI_MPY01    , [CVI_MPY0, CVI_MPY1]>,
-      ComboFuncData<CVI_ALL      , [CVI_ST, CVI_XLANE, CVI_SHIFT,
-                                    CVI_MPY0, CVI_MPY1, CVI_LD]>
-    ]>;
-
 // Note: When adding additional vector scheduling classes, add the
 // corresponding methods to the class HexagonInstrInfo.
 def CVI_VA           : InstrItinClass;
index 68a4802..5060b6e 100644 (file)
 //
 //===----------------------------------------------------------------------===//
 
-#define DEBUG_TYPE "dfa-emitter"
-
 #include "CodeGenTarget.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
-#include "llvm/ADT/StringExtras.h"
-#include "llvm/CodeGen/DFAPacketizer.h"
 #include "llvm/TableGen/Record.h"
 #include "llvm/TableGen/TableGenBackend.h"
-#include "llvm/Support/Debug.h"
 #include <list>
 #include <map>
 #include <string>
-#include <queue>
 using namespace llvm;
 
-// To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter".
-//
-// dbgsInsnClass - When debugging, print instruction class stages.
-//
-void dbgsInsnClass(const std::vector<unsigned> &InsnClass);
-//
-// dbgsStateInfo - When debugging, print the set of state info.
-//
-void dbgsStateInfo(const std::set<unsigned> &stateInfo);
-//
-// dbgsIndent - When debugging, indent by the specified amount.
-//
-void dbgsIndent(unsigned indent);
-
 //
 // class DFAPacketizerEmitter: class that generates and prints out the DFA
 // for resource tracking.
@@ -57,48 +37,20 @@ private:
   // allInsnClasses is the set of all possible resources consumed by an
   // InstrStage.
   //
-  std::vector<std::vector<unsigned>> allInsnClasses;
+  DenseSet<unsigned> allInsnClasses;
   RecordKeeper &Records;
 
 public:
   DFAPacketizerEmitter(RecordKeeper &R);
 
   //
-  // collectAllFuncUnits - Construct a map of function unit names to bits.
-  //
-  int collectAllFuncUnits(std::vector<Record*> &ProcItinList,
-                           std::map<std::string, unsigned> &FUNameToBitsMap,
-                           int &maxResources,
-                           raw_ostream &OS);
-
-  //
-  // collectAllComboFuncs - Construct a map from a combo function unit bit to
-  //                        the bits of all included functional units.
-  //
-  int collectAllComboFuncs(std::vector<Record*> &ComboFuncList,
-                           std::map<std::string, unsigned> &FUNameToBitsMap,
-                           std::map<unsigned, unsigned> &ComboBitToBitsMap,
-                           raw_ostream &OS);
-
-  //
-  // collectOneInsnClass - Populate allInsnClasses with one instruction class.
-  //
-  int collectOneInsnClass(const std::string &ProcName,
-                           std::vector<Record*> &ProcItinList,
-                           std::map<std::string, unsigned> &FUNameToBitsMap,
-                           Record *ItinData,
-                           raw_ostream &OS);
-
-  //
-  // collectAllInsnClasses - Populate allInsnClasses which is a set of units
+  // collectAllInsnClasses: Populate allInsnClasses which is a set of units
   // used in each stage.
   //
-  int collectAllInsnClasses(const std::string &ProcName,
-                           std::vector<Record*> &ProcItinList,
-                           std::map<std::string, unsigned> &FUNameToBitsMap,
-                           std::vector<Record*> &ItinDataList,
-                           int &maxStages,
-                           raw_ostream &OS);
+  void collectAllInsnClasses(const std::string &Name,
+                             Record *ItinData,
+                             unsigned &NStages,
+                             raw_ostream &OS);
 
   void run(raw_ostream &OS);
 };
@@ -135,7 +87,7 @@ class State {
   const int stateNum;
   mutable bool isInitial;
   mutable std::set<unsigned> stateInfo;
-  typedef std::map<std::vector<unsigned>, const State *> TransitionMap;
+  typedef std::map<unsigned, const State *> TransitionMap;
   mutable TransitionMap Transitions;
 
   State();
@@ -145,47 +97,28 @@ class State {
   }
 
   //
-  // canMaybeAddInsnClass - Quickly verifies if an instruction of type InsnClass
-  // may be a valid transition from this state i.e., can an instruction of type
-  // InsnClass be added to the packet represented by this state.
-  //
-  // Note that for multiple stages, this quick check does not take into account
-  // any possible resource competition between the stages themselves.  That is
-  // enforced in AddInsnClassStages which checks the cross product of all
-  // stages for resource availability (which is a more involved check).
-  //
-  bool canMaybeAddInsnClass(std::vector<unsigned> &InsnClass,
-                        std::map<unsigned, unsigned> &ComboBitToBitsMap) const;
-  //
-  // AddInsnClass - Return all combinations of resource reservation
-  // which are possible from this state (PossibleStates).
+  // canAddInsnClass - Returns true if an instruction of type InsnClass is a
+  // valid transition from this state, i.e., can an instruction of type InsnClass
+  // be added to the packet represented by this state.
   //
   // 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;
+  bool canAddInsnClass(unsigned InsnClass) const;
   //
-  // AddInsnClassStages - Return all combinations of resource reservation
-  // resulting from the cross product of all stages for this InsnClass
+  // AddInsnClass - Return all combinations of resource reservation
   // 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;
-  //
+  void AddInsnClass(unsigned InsnClass, std::set<unsigned> &PossibleStates) const;
+  // 
   // addTransition - Add a transition from this state given the input InsnClass
   //
-  void addTransition(std::vector<unsigned> InsnClass, const State *To) const;
+  void addTransition(unsigned InsnClass, const State *To) const;
   //
   // hasTransition - Returns true if there is a transition from this state
   // given the input InsnClass
   //
-  bool hasTransition(std::vector<unsigned> InsnClass) const;
+  bool hasTransition(unsigned InsnClass) const;
 };
 } // End anonymous namespace.
 
@@ -211,52 +144,10 @@ public:
   //
   // writeTable: Print out a table representing the DFA.
   //
-  void writeTableAndAPI(raw_ostream &OS, const std::string &ClassName,
-                 int numInsnClasses = 0,
-                 int maxResources = 0, int numCombos = 0, int maxStages = 0);
+  void writeTableAndAPI(raw_ostream &OS, const std::string &ClassName);
 };
 } // End anonymous namespace.
 
-// To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter".
-//
-// dbgsInsnClass - When debugging, print instruction class stages.
-//
-void dbgsInsnClass(const std::vector<unsigned> &InsnClass) {
-  DEBUG(dbgs() << "InsnClass: ");
-  for (unsigned i = 0; i < InsnClass.size(); ++i) {
-    if (i > 0) {
-      DEBUG(dbgs() << ", ");
-    }
-    DEBUG(dbgs() << "0x" << utohexstr(InsnClass[i]));
-  }
-  DFAInput InsnInput = DFAPacketizer::getInsnInput(InsnClass);
-  DEBUG(dbgs() << " (input: 0x" << utohexstr(InsnInput) << ")");
-}
-
-//
-// dbgsStateInfo - When debugging, print the set of state info.
-//
-void dbgsStateInfo(const std::set<unsigned> &stateInfo) {
-  DEBUG(dbgs() << "StateInfo: ");
-  unsigned i = 0;
-  for (std::set<unsigned>::iterator SI = stateInfo.begin();
-       SI != stateInfo.end(); ++SI, ++i) {
-    unsigned thisState = *SI;
-    if (i > 0) {
-      DEBUG(dbgs() << ", ");
-    }
-    DEBUG(dbgs() << "0x" << utohexstr(thisState));
-  }
-}
-
-//
-// dbgsIndent - When debugging, indent by the specified amount.
-//
-void dbgsIndent(unsigned indent) {
-  for (unsigned i = 0; i < indent; ++i) {
-    DEBUG(dbgs() << " ");
-  }
-}
 
 //
 // Constructors and destructors for State and DFA
@@ -266,11 +157,10 @@ State::State() :
 
 DFA::DFA(): currentState(nullptr) {}
 
-//
+// 
 // 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(unsigned InsnClass, const State *To) const {
   assert(!Transitions.count(InsnClass) &&
       "Cannot have multiple transitions for the same input");
   Transitions[InsnClass] = To;
@@ -280,7 +170,7 @@ void State::addTransition(std::vector<unsigned> InsnClass, const State *To)
 // hasTransition - Returns true if there is a transition from this state
 // given the input InsnClass
 //
-bool State::hasTransition(std::vector<unsigned> InsnClass) const {
+bool State::hasTransition(unsigned InsnClass) const {
   return Transitions.count(InsnClass) > 0;
 }
 
@@ -288,167 +178,61 @@ bool State::hasTransition(std::vector<unsigned> InsnClass) const {
 // 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(unsigned InsnClass,
+                            std::set<unsigned> &PossibleStates) 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;
 
-    DenseSet<unsigned> VisitedResourceStates;
-
-    DEBUG(dbgs() << "  thisState: 0x" << utohexstr(thisState) << "\n");
-    AddInsnClassStages(InsnClass, ComboBitToBitsMap,
-                                numstages - 1, numstages,
-                                thisState, thisState,
-                                VisitedResourceStates, PossibleStates);
-  }
-}
-
-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 {
-
-  assert((chkstage < numstages) && "AddInsnClassStages: stage out of range");
-  unsigned thisStage = InsnClass[chkstage];
+    //
+    // Iterate over all possible resources used in InsnClass.
+    // For ex: for InsnClass = 0x11, all resources = {0x01, 0x10}.
+    //
 
-  dbgsIndent((1 + numstages - chkstage) << 1);
-  DEBUG(dbgs() << "AddInsnClassStages " << chkstage
-               << " (0x" << utohexstr(thisStage) << ") from ");
-  dbgsInsnClass(InsnClass);
-  DEBUG(dbgs() << "\n");
-
-  //
-  // Iterate over all possible resources used in thisStage.
-  // For ex: for thisStage = 0x11, all resources = {0x01, 0x10}.
-  //
-  for (unsigned int j = 0; j < DFA_MAX_RESOURCES; ++j) {
-    unsigned resourceMask = (0x1 << j);
-    if (resourceMask & thisStage) {
-      unsigned combo = ComboBitToBitsMap[resourceMask];
-      if (combo && ((~prevState & combo) != combo)) {
-        DEBUG(dbgs() << "\tSkipped Add 0x" << utohexstr(prevState)
-                     << " - combo op 0x" << utohexstr(resourceMask)
-                     << " (0x" << utohexstr(combo) <<") cannot be scheduled\n");
-        continue;
-      }
-      //
-      // For each possible resource used in thisStage, generate the
-      // resource state if that resource was used.
-      //
-      unsigned ResultingResourceState = prevState | resourceMask | combo;
-      dbgsIndent((2 + numstages - chkstage) << 1);
-      DEBUG(dbgs() << "0x" << utohexstr(prevState)
-                   << " | 0x" << utohexstr(resourceMask));
-      if (combo) {
-        DEBUG(dbgs() << " | 0x" << utohexstr(combo));
-      }
-      DEBUG(dbgs() << " = 0x" << utohexstr(ResultingResourceState) << " ");
-
-      //
-      // If this is the final stage for this class
-      //
-      if (chkstage == 0) {
+    DenseSet<unsigned> VisitedResourceStates;
+    for (unsigned int j = 0; j < sizeof(InsnClass) * 8; ++j) {
+      if ((0x1 << j) & InsnClass) {
+        //
+        // For each possible resource used in InsnClass, generate the
+        // resource state if that resource was used.
+        //
+        unsigned ResultingResourceState = thisState | (0x1 << j);
         //
         // Check if the resulting resource state can be accommodated in this
         // packet.
-        // We compute resource OR prevState (originally started as origState).
-        // If the result of the OR is different than origState, it implies
+        // We compute ResultingResourceState OR thisState.
+        // If the result of the OR is different than thisState, it implies
         // that there is at least one resource that can be used to schedule
-        // thisStage in the current packet.
+        // InsnClass 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);
-            DEBUG(dbgs() << "\tResultingResourceState: 0x"
-                         << utohexstr(ResultingResourceState) << "\n");
-          } else {
-            DEBUG(dbgs() << "\tSkipped Add - state already seen\n");
-          }
-        } else {
-          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) {
-          DEBUG(dbgs() << "\n");
-          AddInsnClassStages(InsnClass, ComboBitToBitsMap,
-                                chkstage - 1, numstages,
-                                ResultingResourceState, origState,
-                                VisitedResourceStates, PossibleStates);
-        } else {
-          DEBUG(dbgs() << "\tSkipped Add - no resources available\n");
+        if ((ResultingResourceState != thisState) &&
+            (VisitedResourceStates.count(ResultingResourceState) == 0)) {
+          VisitedResourceStates.insert(ResultingResourceState);
+          PossibleStates.insert(ResultingResourceState);
         }
       }
     }
   }
+
 }
 
 
 //
-// canMaybeAddInsnClass - Quickly verifies if an instruction of type InsnClass
-// may be a valid transition from this state i.e., can an instruction of type
-// InsnClass be added to the packet represented by this state.
+// canAddInsnClass - Quickly verifies if an instruction of type InsnClass is a
+// valid transition from this state i.e., can an instruction of type InsnClass
+// be added to the packet represented by this state.
 //
-// Note that this routine is performing conservative checks that can be
-// quickly executed acting as a filter before calling AddInsnClassStages.
-// Any cases allowed through here will be caught later in AddInsnClassStages
-// which performs the more expensive exact check.
-//
-bool State::canMaybeAddInsnClass(std::vector<unsigned> &InsnClass,
-                    std::map<unsigned, unsigned> &ComboBitToBitsMap) const {
+bool State::canAddInsnClass(unsigned InsnClass) const {
   for (std::set<unsigned>::const_iterator SI = stateInfo.begin();
        SI != stateInfo.end(); ++SI) {
-
-    // Check to see if all required resources are available.
-    bool available = true;
-
-    // Inspect each stage independently.
-    // note: This is a conservative check as we aren't checking for
-    //       possible resource competition between the stages themselves
-    //       The full cross product is examined later in AddInsnClass.
-    for (unsigned i = 0; i < InsnClass.size(); ++i) {
-      unsigned resources = *SI;
-      if ((~resources & InsnClass[i]) == 0) {
-        available = false;
-        break;
-      }
-      // Make sure _all_ resources for a combo function are available.
-      // note: This is a quick conservative check as it won't catch an
-      //       unscheduleable combo if this stage is an OR expression
-      //       containing a combo.
-      //       These cases are caught later in AddInsnClass.
-      unsigned combo = ComboBitToBitsMap[InsnClass[i]];
-      if (combo && ((~resources & combo) != combo)) {
-        DEBUG(dbgs() << "\tSkipped canMaybeAdd 0x" << utohexstr(resources)
-                     << " - combo op 0x" << utohexstr(InsnClass[i])
-                     << " (0x" << utohexstr(combo) <<") cannot be scheduled\n");
-        available = false;
-        break;
-      }
-    }
-
-    if (available) {
+    if (~*SI & InsnClass)
       return true;
-    }
   }
   return false;
 }
@@ -460,6 +244,7 @@ const State &DFA::newState() {
   return *IterPair.first;
 }
 
+
 int State::currentStateNum = 0;
 
 DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R):
@@ -478,100 +263,57 @@ DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R):
 //                         the ith state.
 //
 //
-void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName,
-                           int numInsnClasses,
-                           int maxResources, int numCombos, int maxStages) {
-
-  unsigned numStates = states.size();
-
-  DEBUG(dbgs() << "-----------------------------------------------------------------------------\n");
-  DEBUG(dbgs() << "writeTableAndAPI\n");
-  DEBUG(dbgs() << "Total states: " << numStates << "\n");
-
-  OS << "namespace llvm {\n";
-
-  OS << "\n// Input format:\n";
-  OS << "#define DFA_MAX_RESTERMS        " << DFA_MAX_RESTERMS
-     << "\t// maximum AND'ed resource terms\n";
-  OS << "#define DFA_MAX_RESOURCES       " << DFA_MAX_RESOURCES
-     << "\t// maximum resource bits in one term\n";
-
-  OS << "\n// " << TargetName << "DFAStateInputTable[][2] = "
-     << "pairs of <Input, NextState> for all valid\n";
-  OS << "//                           transitions.\n";
-  OS << "// " << numStates << "\tstates\n";
-  OS << "// " << numInsnClasses << "\tinstruction classes\n";
-  OS << "// " << maxResources << "\tresources max\n";
-  OS << "// " << numCombos << "\tcombo resources\n";
-  OS << "// " << maxStages << "\tstages max\n";
-  OS << "const " << DFA_TBLTYPE << " "
-     << TargetName << "DFAStateInputTable[][2] = {\n";
-
+void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName) {
+  static const std::string SentinelEntry = "{-1, -1}";
+  DFA::StateSet::iterator SI = states.begin();
   // 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}";
+  std::vector<int> StateEntry(states.size());
+
+  OS << "namespace llvm {\n\n";
+  OS << "const int " << TargetName << "DFAStateInputTable[][2] = {\n";
 
   // Tracks the total valid transitions encountered so far. It is used
   // to construct the StateEntry table.
   int ValidTransitions = 0;
-  DFA::StateSet::iterator SI = states.begin();
-  for (unsigned i = 0; i < numStates; ++i, ++SI) {
+  for (unsigned i = 0; i < states.size(); ++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" << utohexstr(DFAPacketizer::getInsnInput(II->first)) << ", "
+      OS << "{" << II->first << ", "
          << II->second->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";
+      OS << SentinelEntry << ",";
       ++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 << SentinelEntry << "\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";
-    }
+  for (unsigned i = 0; i < states.size(); ++i)
     OS << StateEntry[i] << ", ";
-  }
 
   // Print out the index to the sentinel entry in StateInputTable
   OS << ValidTransitions << ", ";
-  OS << "   // states " << (lastState+1) << ":" << numStates << "\n";
 
-  OS << "};\n";
+  OS << "\n};\n";
   OS << "} // namespace\n";
 
 
@@ -590,123 +332,40 @@ void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName,
 
 
 //
-// collectAllFuncUnits - Construct a map of function unit names to bits.
+// collectAllInsnClasses - Populate allInsnClasses which is a set of units
+// used in each stage.
 //
-int DFAPacketizerEmitter::collectAllFuncUnits(
-                            std::vector<Record*> &ProcItinList,
-                            std::map<std::string, unsigned> &FUNameToBitsMap,
-                            int &maxFUs,
-                            raw_ostream &OS) {
-  DEBUG(dbgs() << "-----------------------------------------------------------------------------\n");
-  DEBUG(dbgs() << "collectAllFuncUnits");
-  DEBUG(dbgs() << " (" << ProcItinList.size() << " itineraries)\n");
+void DFAPacketizerEmitter::collectAllInsnClasses(const std::string &Name,
+                                  Record *ItinData,
+                                  unsigned &NStages,
+                                  raw_ostream &OS) {
+  // Collect processor itineraries.
+  std::vector<Record*> ProcItinList =
+    Records.getAllDerivedDefinitions("ProcessorItineraries");
+
+  // If just no itinerary then don't bother.
+  if (ProcItinList.size() < 2)
+    return;
+  std::map<std::string, unsigned> NameToBitsMap;
 
-  int totalFUs = 0;
   // Parse functional units for all the itineraries.
   for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) {
     Record *Proc = ProcItinList[i];
-    const std::string &ProcName = Proc->getName();
     std::vector<Record*> FUs = Proc->getValueAsListOfDefs("FU");
 
-    DEBUG(dbgs() << "    FU:" << i
-                 << " (" << FUs.size() << " FUs) "
-                 << ProcName);
-
-
-    // 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");
-      unsigned FuncResources = (unsigned) (1U << j);
-      FUNameToBitsMap[FUs[j]->getName()] = FuncResources;
-      DEBUG(dbgs() << " " << FUs[j]->getName()
-                   << ":0x" << utohexstr(FuncResources));
-    }
-    if (((int) numFUs) > maxFUs) {
-      maxFUs = numFUs;
-    }
-    totalFUs += numFUs;
-    DEBUG(dbgs() << "\n");
-  }
-  return totalFUs;
-}
-
-//
-// collectAllComboFuncs - Construct a map from a combo function unit bit to
-//                        the bits of all included functional units.
-//
-int DFAPacketizerEmitter::collectAllComboFuncs(
-                            std::vector<Record*> &ComboFuncList,
-                            std::map<std::string, unsigned> &FUNameToBitsMap,
-                            std::map<unsigned, unsigned> &ComboBitToBitsMap,
-                            raw_ostream &OS) {
-  DEBUG(dbgs() << "-----------------------------------------------------------------------------\n");
-  DEBUG(dbgs() << "collectAllComboFuncs");
-  DEBUG(dbgs() << " (" << ComboFuncList.size() << " sets)\n");
-
-  int numCombos = 0;
-  for (unsigned i = 0, N = ComboFuncList.size(); i < N; ++i) {
-    Record *Func = ComboFuncList[i];
-    const std::string &ProcName = Func->getName();
-    std::vector<Record*> FUs = Func->getValueAsListOfDefs("CFD");
-
-    DEBUG(dbgs() << "    CFD:" << i
-                 << " (" << FUs.size() << " combo FUs) "
-                 << ProcName << "\n");
-
     // Convert macros to bits for each stage.
-    for (unsigned j = 0, N = FUs.size(); j < N; ++j) {
-      assert ((j < DFA_MAX_RESOURCES) &&
-                      "Exceeded maximum number of DFA resources");
-      Record *FuncData = FUs[j];
-      Record *ComboFunc = FuncData->getValueAsDef("TheComboFunc");
-      const std::vector<Record*> &FuncList =
-                                   FuncData->getValueAsListOfDefs("FuncList");
-      std::string ComboFuncName = ComboFunc->getName();
-      unsigned ComboBit = FUNameToBitsMap[ComboFuncName];
-      unsigned ComboResources = ComboBit;
-      DEBUG(dbgs() << "      combo: " << ComboFuncName
-                   << ":0x" << utohexstr(ComboResources) << "\n");
-      for (unsigned k = 0, M = FuncList.size(); k < M; ++k) {
-        std::string FuncName = FuncList[k]->getName();
-        unsigned FuncResources = FUNameToBitsMap[FuncName];
-        DEBUG(dbgs() << "        " << FuncName
-                     << ":0x" << utohexstr(FuncResources) << "\n");
-        ComboResources |= FuncResources;
-      }
-      ComboBitToBitsMap[ComboBit] = ComboResources;
-      numCombos++;
-      DEBUG(dbgs() << "          => combo bits: " << ComboFuncName << ":0x"
-                   << utohexstr(ComboBit) << " = 0x"
-                   << utohexstr(ComboResources) << "\n");
-    }
+    for (unsigned i = 0, N = FUs.size(); i < N; ++i)
+      NameToBitsMap[FUs[i]->getName()] = (unsigned) (1U << i);
   }
-  return numCombos;
-}
-
-
-//
-// collectOneInsnClass - Populate allInsnClasses with one instruction class
-//
-int DFAPacketizerEmitter::collectOneInsnClass(const std::string &ProcName,
-                        std::vector<Record*> &ProcItinList,
-                        std::map<std::string, unsigned> &FUNameToBitsMap,
-                        Record *ItinData,
-                        raw_ostream &OS) {
-  // Collect instruction classes.
-  Record *ItinDef = ItinData->getValueAsDef("TheClass");
 
   const std::vector<Record*> &StageList =
     ItinData->getValueAsListOfDefs("Stages");
 
   // The number of stages.
-  unsigned NStages = StageList.size();
+  NStages = StageList.size();
 
-  DEBUG(dbgs() << "    " << ItinDef->getName()
-               << "\n");
-
-  std::vector<unsigned> UnitBits;
+  // For each unit.
+  unsigned UnitBitValue = 0;
 
   // Compute the bitwise or of each unit used in this stage.
   for (unsigned i = 0; i < NStages; ++i) {
@@ -716,72 +375,18 @@ int DFAPacketizerEmitter::collectOneInsnClass(const std::string &ProcName,
     const std::vector<Record*> &UnitList =
       Stage->getValueAsListOfDefs("Units");
 
-    DEBUG(dbgs() << "        stage:" << i
-                 << " [" << UnitList.size() << " units]:");
-    unsigned dbglen = 26;  // cursor after stage dbgs
-
-    // Compute the bitwise or of each unit used in this stage.
-    unsigned UnitBitValue = 0;
     for (unsigned j = 0, M = UnitList.size(); j < M; ++j) {
       // Conduct bitwise or.
       std::string UnitName = UnitList[j]->getName();
-      DEBUG(dbgs() << " " << j << ":" << UnitName);
-      dbglen += 3 + UnitName.length();
-      assert(FUNameToBitsMap.count(UnitName));
-      UnitBitValue |= FUNameToBitsMap[UnitName];
+      assert(NameToBitsMap.count(UnitName));
+      UnitBitValue |= NameToBitsMap[UnitName];
     }
 
     if (UnitBitValue != 0)
-      UnitBits.push_back(UnitBitValue);
-
-    while (dbglen <= 64) {   // line up bits dbgs
-        dbglen += 8;
-        DEBUG(dbgs() << "\t");
-    }
-    DEBUG(dbgs() << " (bits: 0x" << utohexstr(UnitBitValue) << ")\n");
+      allInsnClasses.insert(UnitBitValue);
   }
-
-  if (UnitBits.size() > 0)
-    allInsnClasses.push_back(UnitBits);
-
-  DEBUG(dbgs() << "        ");
-  dbgsInsnClass(UnitBits);
-  DEBUG(dbgs() << "\n");
-
-  return NStages;
 }
 
-//
-// collectAllInsnClasses - Populate allInsnClasses which is a set of units
-// used in each stage.
-//
-int DFAPacketizerEmitter::collectAllInsnClasses(const std::string &ProcName,
-                            std::vector<Record*> &ProcItinList,
-                            std::map<std::string, unsigned> &FUNameToBitsMap,
-                            std::vector<Record*> &ItinDataList,
-                            int &maxStages,
-                            raw_ostream &OS) {
-  // Collect all instruction classes.
-  unsigned M = ItinDataList.size();
-
-  int numInsnClasses = 0;
-  DEBUG(dbgs() << "-----------------------------------------------------------------------------\n"
-               << "collectAllInsnClasses "
-               << ProcName
-               << " (" << M << " classes)\n");
-
-  // Collect stages for each instruction class for all itinerary data
-  for (unsigned j = 0; j < M; j++) {
-    Record *ItinData = ItinDataList[j];
-    int NStages = collectOneInsnClass(ProcName, ProcItinList,
-                                      FUNameToBitsMap, ItinData, OS);
-    if (NStages > maxStages) {
-      maxStages = NStages;
-    }
-    numInsnClasses++;
-  }
-  return numInsnClasses;
-}
 
 //
 // Run the worklist algorithm to generate the DFA.
@@ -793,35 +398,16 @@ void DFAPacketizerEmitter::run(raw_ostream &OS) {
     Records.getAllDerivedDefinitions("ProcessorItineraries");
 
   //
-  // Collect the Functional units.
+  // Collect the instruction classes.
   //
-  std::map<std::string, unsigned> FUNameToBitsMap;
-  int maxResources = 0;
-  collectAllFuncUnits(ProcItinList,
-                              FUNameToBitsMap, maxResources, OS);
-
-  //
-  // Collect the Combo Functional units.
-  //
-  std::map<unsigned, unsigned> ComboBitToBitsMap;
-  std::vector<Record*> ComboFuncList =
-    Records.getAllDerivedDefinitions("ComboFuncUnits");
-  int numCombos = collectAllComboFuncs(ComboFuncList,
-                              FUNameToBitsMap, ComboBitToBitsMap, OS);
-
-  //
-  // Collect the itineraries.
-  //
-  int maxStages = 0;
-  int numInsnClasses = 0;
   for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) {
     Record *Proc = ProcItinList[i];
 
     // Get processor itinerary name.
-    const std::string &ProcName = Proc->getName();
+    const std::string &Name = Proc->getName();
 
     // Skip default.
-    if (ProcName == "NoItineraries")
+    if (Name == "NoItineraries")
       continue;
 
     // Sanity check for at least one instruction itinerary class.
@@ -833,11 +419,15 @@ void DFAPacketizerEmitter::run(raw_ostream &OS) {
     // Get itinerary data list.
     std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID");
 
-    // Collect all instruction classes
-    numInsnClasses += collectAllInsnClasses(ProcName, ProcItinList,
-                          FUNameToBitsMap, ItinDataList, maxStages, OS);
+    // Collect instruction classes for all itinerary data.
+    for (unsigned j = 0, M = ItinDataList.size(); j < M; j++) {
+      Record *ItinData = ItinDataList[j];
+      unsigned NStages;
+      collectAllInsnClasses(Name, ItinData, NStages, OS);
+    }
   }
 
+
   //
   // Run a worklist algorithm to generate the DFA.
   //
@@ -846,7 +436,6 @@ void DFAPacketizerEmitter::run(raw_ostream &OS) {
   Initial->isInitial = true;
   Initial->stateInfo.insert(0x0);
   SmallVector<const State*, 32> WorkList;
-//  std::queue<State*> WorkList;
   std::map<std::set<unsigned>, const State*> Visited;
 
   WorkList.push_back(Initial);
@@ -870,15 +459,9 @@ void DFAPacketizerEmitter::run(raw_ostream &OS) {
   //
   while (!WorkList.empty()) {
     const State *current = WorkList.pop_back_val();
-    DEBUG(dbgs() << "---------------------\n");
-    DEBUG(dbgs() << "Processing state: " << current->stateNum << " - ");
-    dbgsStateInfo(current->stateInfo);
-    DEBUG(dbgs() << "\n");
-    for (unsigned i = 0; i < allInsnClasses.size(); i++) {
-      std::vector<unsigned> InsnClass = allInsnClasses[i];
-      DEBUG(dbgs() << i << " ");
-      dbgsInsnClass(InsnClass);
-      DEBUG(dbgs() << "\n");
+    for (DenseSet<unsigned>::iterator CI = allInsnClasses.begin(),
+           CE = allInsnClasses.end(); CI != CE; ++CI) {
+      unsigned InsnClass = *CI;
 
       std::set<unsigned> NewStateResources;
       //
@@ -886,47 +469,32 @@ void DFAPacketizerEmitter::run(raw_ostream &OS) {
       // and the state can accommodate this InsnClass, create a transition.
       //
       if (!current->hasTransition(InsnClass) &&
-          current->canMaybeAddInsnClass(InsnClass, ComboBitToBitsMap)) {
-        const State *NewState = NULL;
-        current->AddInsnClass(InsnClass, ComboBitToBitsMap, NewStateResources);
-        if (NewStateResources.size() == 0) {
-          DEBUG(dbgs() << "  Skipped - no new states generated\n");
-          continue;
-        }
-
-        DEBUG(dbgs() << "\t");
-        dbgsStateInfo(NewStateResources);
-        DEBUG(dbgs() << "\n");
+          current->canAddInsnClass(InsnClass)) {
+        const State *NewState;
+        current->AddInsnClass(InsnClass, NewStateResources);
+        assert(!NewStateResources.empty() && "New states must be generated");
 
         //
         // If we have seen this state before, then do not create a new state.
         //
+        //
         auto VI = Visited.find(NewStateResources);
-        if (VI != Visited.end()) {
+        if (VI != Visited.end())
           NewState = VI->second;
-          DEBUG(dbgs() << "\tFound existing state: "
-                       << NewState->stateNum << " - ");
-          dbgsStateInfo(NewState->stateInfo);
-          DEBUG(dbgs() << "\n");
-        } else {
+        else {
           NewState = &D.newState();
           NewState->stateInfo = NewStateResources;
           Visited[NewStateResources] = NewState;
           WorkList.push_back(NewState);
-          DEBUG(dbgs() << "\tAccepted new state: "
-                       << NewState->stateNum << " - ");
-          dbgsStateInfo(NewState->stateInfo);
-          DEBUG(dbgs() << "\n");
         }
-
+        
         current->addTransition(InsnClass, NewState);
       }
     }
   }
 
   // Print out the table.
-  D.writeTableAndAPI(OS, TargetName,
-               numInsnClasses, maxResources, numCombos, maxStages);
+  D.writeTableAndAPI(OS, TargetName);
 }
 
 namespace llvm {