1 files changed, 304 insertions, 64 deletions

diff --git a/contrib/llvm/utils/TableGen/CodeGenSchedule.h b/contrib/llvm/utils/TableGen/CodeGenSchedule.h
index 9da0145..eed0589 100644
--- a/contrib/llvm/utils/TableGen/CodeGenSchedule.h
+++ b/contrib/llvm/utils/TableGen/CodeGenSchedule.h
@@ -15,6 +15,7 @@
 #ifndef CODEGEN_SCHEDULE_H
 #define CODEGEN_SCHEDULE_H
 
+#include "SetTheory.h"
 #include "llvm/TableGen/Record.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/ADT/DenseMap.h"
@@ -23,21 +24,131 @@
 namespace llvm {
 
 class CodeGenTarget;
+class CodeGenSchedModels;
+class CodeGenInstruction;
 
-// Scheduling class.
-//
-// Each instruction description will be mapped to a scheduling class. It may be
-// an explicitly defined itinerary class, or an inferred class in which case
-// ItinClassDef == NULL.
+typedef std::vector<Record*> RecVec;
+typedef std::vector<Record*>::const_iterator RecIter;
+
+typedef std::vector<unsigned> IdxVec;
+typedef std::vector<unsigned>::const_iterator IdxIter;
+
+void splitSchedReadWrites(const RecVec &RWDefs,
+                          RecVec &WriteDefs, RecVec &ReadDefs);
+
+/// We have two kinds of SchedReadWrites. Explicitly defined and inferred
+/// sequences.  TheDef is nonnull for explicit SchedWrites, but Sequence may or
+/// may not be empty. TheDef is null for inferred sequences, and Sequence must
+/// be nonempty.
+///
+/// IsVariadic controls whether the variants are expanded into multiple operands
+/// or a sequence of writes on one operand.
+struct CodeGenSchedRW {
+  unsigned Index;
+  std::string Name;
+  Record *TheDef;
+  bool IsRead;
+  bool IsAlias;
+  bool HasVariants;
+  bool IsVariadic;
+  bool IsSequence;
+  IdxVec Sequence;
+  RecVec Aliases;
+
+  CodeGenSchedRW(): Index(0), TheDef(0), IsAlias(false), HasVariants(false),
+                    IsVariadic(false), IsSequence(false) {}
+  CodeGenSchedRW(unsigned Idx, Record *Def): Index(Idx), TheDef(Def),
+                                             IsAlias(false), IsVariadic(false) {
+    Name = Def->getName();
+    IsRead = Def->isSubClassOf("SchedRead");
+    HasVariants = Def->isSubClassOf("SchedVariant");
+    if (HasVariants)
+      IsVariadic = Def->getValueAsBit("Variadic");
+
+    // Read records don't currently have sequences, but it can be easily
+    // added. Note that implicit Reads (from ReadVariant) may have a Sequence
+    // (but no record).
+    IsSequence = Def->isSubClassOf("WriteSequence");
+  }
+
+  CodeGenSchedRW(unsigned Idx, bool Read, const IdxVec &Seq,
+                 const std::string &Name):
+    Index(Idx), Name(Name), TheDef(0), IsRead(Read), IsAlias(false),
+    HasVariants(false), IsVariadic(false), IsSequence(true), Sequence(Seq) {
+    assert(Sequence.size() > 1 && "implied sequence needs >1 RWs");
+  }
+
+  bool isValid() const {
+    assert((!HasVariants || TheDef) && "Variant write needs record def");
+    assert((!IsVariadic || HasVariants) && "Variadic write needs variants");
+    assert((!IsSequence || !HasVariants) && "Sequence can't have variant");
+    assert((!IsSequence || !Sequence.empty()) && "Sequence should be nonempty");
+    assert((!IsAlias || Aliases.empty()) && "Alias cannot have aliases");
+    return TheDef || !Sequence.empty();
+  }
+
+#ifndef NDEBUG
+  void dump() const;
+#endif
+};
+
+/// Represent a transition between SchedClasses induced by SchedVariant.
+struct CodeGenSchedTransition {
+  unsigned ToClassIdx;
+  IdxVec ProcIndices;
+  RecVec PredTerm;
+};
+
+/// Scheduling class.
+///
+/// Each instruction description will be mapped to a scheduling class. There are
+/// four types of classes:
+///
+/// 1) An explicitly defined itinerary class with ItinClassDef set.
+/// Writes and ReadDefs are empty. ProcIndices contains 0 for any processor.
+///
+/// 2) An implied class with a list of SchedWrites and SchedReads that are
+/// defined in an instruction definition and which are common across all
+/// subtargets. ProcIndices contains 0 for any processor.
+///
+/// 3) An implied class with a list of InstRW records that map instructions to
+/// SchedWrites and SchedReads per-processor. InstrClassMap should map the same
+/// instructions to this class. ProcIndices contains all the processors that
+/// provided InstrRW records for this class. ItinClassDef or Writes/Reads may
+/// still be defined for processors with no InstRW entry.
+///
+/// 4) An inferred class represents a variant of another class that may be
+/// resolved at runtime. ProcIndices contains the set of processors that may
+/// require the class. ProcIndices are propagated through SchedClasses as
+/// variants are expanded. Multiple SchedClasses may be inferred from an
+/// itinerary class. Each inherits the processor index from the ItinRW record
+/// that mapped the itinerary class to the variant Writes or Reads.
 struct CodeGenSchedClass {
   std::string Name;
-  unsigned Index;
   Record *ItinClassDef;
 
-  CodeGenSchedClass(): Index(0), ItinClassDef(0) {}
-  CodeGenSchedClass(Record *rec): Index(0), ItinClassDef(rec) {
+  IdxVec Writes;
+  IdxVec Reads;
+  // Sorted list of ProcIdx, where ProcIdx==0 implies any processor.
+  IdxVec ProcIndices;
+
+  std::vector<CodeGenSchedTransition> Transitions;
+
+  // InstRW records associated with this class. These records may refer to an
+  // Instruction no longer mapped to this class by InstrClassMap. These
+  // Instructions should be ignored by this class because they have been split
+  // off to join another inferred class.
+  RecVec InstRWs;
+
+  CodeGenSchedClass(): ItinClassDef(0) {}
+  CodeGenSchedClass(Record *rec): ItinClassDef(rec) {
     Name = rec->getName();
+    ProcIndices.push_back(0);
   }
+
+#ifndef NDEBUG
+  void dump(const CodeGenSchedModels *SchedModels) const;
+#endif
 };
 
 // Processor model.
@@ -55,28 +166,69 @@ struct CodeGenSchedClass {
 //
 // ItinDefList orders this processor's InstrItinData records by SchedClass idx.
 struct CodeGenProcModel {
+  unsigned Index;
   std::string ModelName;
   Record *ModelDef;
   Record *ItinsDef;
 
-  // Array of InstrItinData records indexed by CodeGenSchedClass::Index.
-  // The list is empty if the subtarget has no itineraries.
-  std::vector<Record *> ItinDefList;
+  // Derived members...
 
-  CodeGenProcModel(const std::string &Name, Record *MDef, Record *IDef):
-    ModelName(Name), ModelDef(MDef), ItinsDef(IDef) {}
+  // Array of InstrItinData records indexed by a CodeGenSchedClass index.
+  // This list is empty if the Processor has no value for Itineraries.
+  // Initialized by collectProcItins().
+  RecVec ItinDefList;
+
+  // Map itinerary classes to per-operand resources.
+  // This list is empty if no ItinRW refers to this Processor.
+  RecVec ItinRWDefs;
+
+  // All read/write resources associated with this processor.
+  RecVec WriteResDefs;
+  RecVec ReadAdvanceDefs;
+
+  // Per-operand machine model resources associated with this processor.
+  RecVec ProcResourceDefs;
+
+  CodeGenProcModel(unsigned Idx, const std::string &Name, Record *MDef,
+                   Record *IDef) :
+    Index(Idx), ModelName(Name), ModelDef(MDef), ItinsDef(IDef) {}
+
+  bool hasInstrSchedModel() const {
+    return !WriteResDefs.empty() || !ItinRWDefs.empty();
+  }
+
+  unsigned getProcResourceIdx(Record *PRDef) const;
+
+#ifndef NDEBUG
+  void dump() const;
+#endif
 };
 
-// Top level container for machine model data.
+/// Top level container for machine model data.
 class CodeGenSchedModels {
   RecordKeeper &Records;
   const CodeGenTarget &Target;
 
+  // Map dag expressions to Instruction lists.
+  SetTheory Sets;
+
+  // List of unique processor models.
+  std::vector<CodeGenProcModel> ProcModels;
+
+  // Map Processor's MachineModel or ProcItin to a CodeGenProcModel index.
+  typedef DenseMap<Record*, unsigned> ProcModelMapTy;
+  ProcModelMapTy ProcModelMap;
+
+  // Per-operand SchedReadWrite types.
+  std::vector<CodeGenSchedRW> SchedWrites;
+  std::vector<CodeGenSchedRW> SchedReads;
+
   // List of unique SchedClasses.
   std::vector<CodeGenSchedClass> SchedClasses;
 
   // Map SchedClass name to itinerary index.
-  // These are either explicit itinerary classes or inferred classes.
+  // These are either explicit itinerary classes or classes implied by
+  // instruction definitions with SchedReadWrite lists.
   StringMap<unsigned> SchedClassIdxMap;
 
   // SchedClass indices 1 up to and including NumItineraryClasses identify
@@ -84,22 +236,80 @@ class CodeGenSchedModels {
   // definitions. NoItinerary always has index 0 regardless of whether it is
   // explicitly referenced.
   //
-  // Any inferred SchedClass have a index greater than NumItineraryClasses.
+  // Any implied SchedClass has an index greater than NumItineraryClasses.
   unsigned NumItineraryClasses;
 
-  // List of unique processor models.
-  std::vector<CodeGenProcModel> ProcModels;
-
-  // Map Processor's MachineModel + ProcItin fields to a CodeGenProcModel index.
-  typedef DenseMap<std::pair<Record*, Record*>, unsigned> ProcModelMapTy;
-  ProcModelMapTy ProcModelMap;
+  // Any inferred SchedClass has an index greater than NumInstrSchedClassses.
+  unsigned NumInstrSchedClasses;
 
-  // True if any processors have nonempty itineraries.
-  bool HasProcItineraries;
+  // Map Instruction to SchedClass index. Only for Instructions mentioned in
+  // InstRW records.
+  typedef DenseMap<Record*, unsigned> InstClassMapTy;
+  InstClassMapTy InstrClassMap;
 
 public:
   CodeGenSchedModels(RecordKeeper& RK, const CodeGenTarget &TGT);
 
+  Record *getModelOrItinDef(Record *ProcDef) const {
+    Record *ModelDef = ProcDef->getValueAsDef("SchedModel");
+    Record *ItinsDef = ProcDef->getValueAsDef("ProcItin");
+    if (!ItinsDef->getValueAsListOfDefs("IID").empty()) {
+      assert(ModelDef->getValueAsBit("NoModel")
+             && "Itineraries must be defined within SchedMachineModel");
+      return ItinsDef;
+    }
+    return ModelDef;
+  }
+
+  const CodeGenProcModel &getModelForProc(Record *ProcDef) const {
+    Record *ModelDef = getModelOrItinDef(ProcDef);
+    ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
+    assert(I != ProcModelMap.end() && "missing machine model");
+    return ProcModels[I->second];
+  }
+
+  const CodeGenProcModel &getProcModel(Record *ModelDef) const {
+    ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
+    assert(I != ProcModelMap.end() && "missing machine model");
+    return ProcModels[I->second];
+  }
+
+  // Iterate over the unique processor models.
+  typedef std::vector<CodeGenProcModel>::const_iterator ProcIter;
+  ProcIter procModelBegin() const { return ProcModels.begin(); }
+  ProcIter procModelEnd() const { return ProcModels.end(); }
+
+  // Get a SchedWrite from its index.
+  const CodeGenSchedRW &getSchedWrite(unsigned Idx) const {
+    assert(Idx < SchedWrites.size() && "bad SchedWrite index");
+    assert(SchedWrites[Idx].isValid() && "invalid SchedWrite");
+    return SchedWrites[Idx];
+  }
+  // Get a SchedWrite from its index.
+  const CodeGenSchedRW &getSchedRead(unsigned Idx) const {
+    assert(Idx < SchedReads.size() && "bad SchedRead index");
+    assert(SchedReads[Idx].isValid() && "invalid SchedRead");
+    return SchedReads[Idx];
+  }
+
+  const CodeGenSchedRW &getSchedRW(unsigned Idx, bool IsRead) const {
+    return IsRead ? getSchedRead(Idx) : getSchedWrite(Idx);
+  }
+  CodeGenSchedRW &getSchedRW(Record *Def) {
+    bool IsRead = Def->isSubClassOf("SchedRead");
+    unsigned Idx = getSchedRWIdx(Def, IsRead);
+    return const_cast<CodeGenSchedRW&>(
+      IsRead ? getSchedRead(Idx) : getSchedWrite(Idx));
+  }
+  const CodeGenSchedRW &getSchedRW(Record*Def) const {
+    return const_cast<CodeGenSchedModels&>(*this).getSchedRW(Def);
+  }
+
+  unsigned getSchedRWIdx(Record *Def, bool IsRead, unsigned After = 0) const;
+
+  // Return true if the given write record is referenced by a ReadAdvance.
+  bool hasReadOfWrite(Record *WriteDef) const;
+
   // Check if any instructions are assigned to an explicit itinerary class other
   // than NoItinerary.
   bool hasItineraryClasses() const { return NumItineraryClasses > 0; }
@@ -111,60 +321,90 @@ public:
   }
 
   // Get a SchedClass from its index.
-  const CodeGenSchedClass &getSchedClass(unsigned Idx) {
+  CodeGenSchedClass &getSchedClass(unsigned Idx) {
     assert(Idx < SchedClasses.size() && "bad SchedClass index");
     return SchedClasses[Idx];
   }
-
-  // Get an itinerary class's index. Value indices are '0' for NoItinerary up to
-  // and including numItineraryClasses().
-  unsigned getItinClassIdx(Record *ItinDef) const {
-    assert(SchedClassIdxMap.count(ItinDef->getName()) && "missing ItinClass");
-    unsigned Idx = SchedClassIdxMap.lookup(ItinDef->getName());
-    assert(Idx <= NumItineraryClasses && "bad ItinClass index");
-    return Idx;
+  const CodeGenSchedClass &getSchedClass(unsigned Idx) const {
+    assert(Idx < SchedClasses.size() && "bad SchedClass index");
+    return SchedClasses[Idx];
   }
 
-  bool hasProcessorItineraries() const {
-    return HasProcItineraries;
-  }
+  // Get the SchedClass index for an instruction. Instructions with no
+  // itinerary, no SchedReadWrites, and no InstrReadWrites references return 0
+  // for NoItinerary.
+  unsigned getSchedClassIdx(const CodeGenInstruction &Inst) const;
+
+  unsigned getSchedClassIdx(const RecVec &RWDefs) const;
 
-  // Get an existing machine model for a processor definition.
-  const CodeGenProcModel &getProcModel(Record *ProcDef) const {
-    unsigned idx = getProcModelIdx(ProcDef);
-    assert(idx < ProcModels.size() && "missing machine model");
-    return ProcModels[idx];
+  unsigned getSchedClassIdxForItin(const Record *ItinDef) {
+    return SchedClassIdxMap[ItinDef->getName()];
   }
 
-  // Iterate over the unique processor models.
-  typedef std::vector<CodeGenProcModel>::const_iterator ProcIter;
-  ProcIter procModelBegin() const { return ProcModels.begin(); }
-  ProcIter procModelEnd() const { return ProcModels.end(); }
+  typedef std::vector<CodeGenSchedClass>::const_iterator SchedClassIter;
+  SchedClassIter schedClassBegin() const { return SchedClasses.begin(); }
+  SchedClassIter schedClassEnd() const { return SchedClasses.end(); }
 
-private:
-  // Get a key that can uniquely identify a machine model.
-  ProcModelMapTy::key_type getProcModelKey(Record *ProcDef) const {
-    Record *ModelDef = ProcDef->getValueAsDef("SchedModel");
-    Record *ItinsDef = ProcDef->getValueAsDef("ProcItin");
-    return std::make_pair(ModelDef, ItinsDef);
-  }
+  void findRWs(const RecVec &RWDefs, IdxVec &Writes, IdxVec &Reads) const;
+  void findRWs(const RecVec &RWDefs, IdxVec &RWs, bool IsRead) const;
+  void expandRWSequence(unsigned RWIdx, IdxVec &RWSeq, bool IsRead) const;
+  void expandRWSeqForProc(unsigned RWIdx, IdxVec &RWSeq, bool IsRead,
+                          const CodeGenProcModel &ProcModel) const;
 
-  // Get the unique index of a machine model.
-  unsigned getProcModelIdx(Record *ProcDef) const {
-    ProcModelMapTy::const_iterator I =
-      ProcModelMap.find(getProcModelKey(ProcDef));
-    if (I == ProcModelMap.end())
-      return ProcModels.size();
-    return I->second;
-  }
+  unsigned addSchedClass(const IdxVec &OperWrites, const IdxVec &OperReads,
+                         const IdxVec &ProcIndices);
+
+  unsigned findOrInsertRW(ArrayRef<unsigned> Seq, bool IsRead);
+
+  unsigned findSchedClassIdx(const IdxVec &Writes, const IdxVec &Reads) const;
+
+  Record *findProcResUnits(Record *ProcResKind,
+                           const CodeGenProcModel &PM) const;
+
+private:
+  void collectProcModels();
 
   // Initialize a new processor model if it is unique.
   void addProcModel(Record *ProcDef);
 
-  void CollectSchedClasses();
-  void CollectProcModels();
-  void CollectProcItin(CodeGenProcModel &ProcModel,
-                       std::vector<Record*> ItinRecords);
+  void collectSchedRW();
+
+  std::string genRWName(const IdxVec& Seq, bool IsRead);
+  unsigned findRWForSequence(const IdxVec &Seq, bool IsRead);
+
+  void collectSchedClasses();
+
+  std::string createSchedClassName(const IdxVec &OperWrites,
+                                   const IdxVec &OperReads);
+  std::string createSchedClassName(const RecVec &InstDefs);
+  void createInstRWClass(Record *InstRWDef);
+
+  void collectProcItins();
+
+  void collectProcItinRW();
+
+  void inferSchedClasses();
+
+  void inferFromRW(const IdxVec &OperWrites, const IdxVec &OperReads,
+                   unsigned FromClassIdx, const IdxVec &ProcIndices);
+  void inferFromItinClass(Record *ItinClassDef, unsigned FromClassIdx);
+  void inferFromInstRWs(unsigned SCIdx);
+
+  void collectProcResources();
+
+  void collectItinProcResources(Record *ItinClassDef);
+
+  void collectRWResources(unsigned RWIdx, bool IsRead,
+                          const IdxVec &ProcIndices);
+
+  void collectRWResources(const IdxVec &Writes, const IdxVec &Reads,
+                          const IdxVec &ProcIndices);
+
+  void addProcResource(Record *ProcResourceKind, CodeGenProcModel &PM);
+
+  void addWriteRes(Record *ProcWriteResDef, unsigned PIdx);
+
+  void addReadAdvance(Record *ProcReadAdvanceDef, unsigned PIdx);
 };
 
 } // namespace llvm