[misched] Extend scheduler to handle unsupported features

[sdardis]

Summary

Currently isComplete = 1 requires that every instruction must
be described, declared unsupported or marked as having no
scheduling information for a processor.

For some backends such as MIPS, this requirement entails
long regex lists of instructions that are unsupported.

This patch teaches Tablegen to skip over instructions that
are associated with unsupported feature when checking if the
scheduling model is complete.

Patch by Daniel Sanders

Modification for checking for the existence of the predicate
done by myself.

[sdardis]

Andy, would you be able to take a look at this or suggest someone who could?

Thanks,
Simon

[sdardis]

Ping?

[john.brawn]

This seems like a useful thing to have, but I have some comments.

include/llvm/Target/TargetSchedule.td

409

Needs a comment describing what this class is for.

410

What exactly is Predicates? The name 'Predicates' and the comment for UnsupportedFeaturesDefs which says "unsupported feature combinations" suggests a list of some kind, but isUnsupported looks through each element of the Predicates list of an instruction and compares its name against this Predicates string, which would mean that Predicates is actually just a single predicate name, and collectProcUnsupportedFeatures also looks like it expects it to be a single predicate name.

Either way, perhaps also change to a list<Predicate> or Predicate (depending on if this is meant to be a list or not) instead of a string, as that way you can remove the code in collectProcUnsupportedFeatures that checks if it's a predicate that exists.

[atrick]

Matthias investigated this very recently, I think he should make a decision on the patch.

[MatzeB]

This is a nice addition.

As John Brawn already said the additions to TargetSchedule.td need to be better documented (describe the behaviour and ideally also show a short example). Why wasn't this added as a list<Predicate> UnsupportedPredicates; field to SchedMachineModel? Defining unrelated UnsupportedFeatures entities with a string seems odd.

lib/CodeGen/TargetSchedule.cpp

215

Just commit this unrelated trivial change independently of this patch/review.

utils/TableGen/CodeGenSchedule.cpp

842–844

You can use a range based for here.

[sdardis]

Added documentation.
Reworked UnsupportedFeature class into a list of predicates as a member of SchedMachineModel. This massively simplified collectProcUnsupportedFeatures().
Added a note to checkCompleteness() for this feature.

[MatzeB]

Thanks, LGTM

[sdardis]

Thanks for the review, committed as rL273551.

include/llvm/Target/TargetSchedule.td

 //
 // SchedModel ties this ItineraryClass mapping to a processor.
 class ItinRW<list<SchedReadWrite> rw, list<InstrItinClass> iic> {
   list<InstrItinClass> MatchedItinClasses = iic;
   list<SchedReadWrite> OperandReadWrites = rw;
   SchedMachineModel SchedModel = ?;
 }
 
+class UnsupportedFeatures<string predicates> {
+  string Predicates = predicates;
+  SchedMachineModel SchedModel = ?;
+}
+
 // Alias a target-defined SchedReadWrite to a processor specific
 // SchedReadWrite. This allows a subtarget to easily map a
 // SchedReadWrite type onto a WriteSequence, SchedWriteVariant, or
 // SchedReadVariant.
 //
 // SchedModel will usually be provided by surrounding let statement
 // and ties this SchedAlias mapping to a processor.
 class SchedAlias<SchedReadWrite match, SchedReadWrite alias> {
   SchedReadWrite MatchRW = match;
   SchedReadWrite AliasRW = alias;
   SchedMachineModel SchedModel = ?;
 }

lib/CodeGen/TargetSchedule.cpp

unsigned TargetSchedModel::computeOperandLatency(
   }
   // If DefIdx does not exist in the model (e.g. implicit defs), then return
   // unit latency (defaultDefLatency may be too conservative).
 #ifndef NDEBUG
   if (SCDesc->isValid() && !DefMI->getOperand(DefOperIdx).isImplicit()
       && !DefMI->getDesc().OpInfo[DefOperIdx].isOptionalDef()
       && SchedModel.isComplete()) {
     errs() << "DefIdx " << DefIdx << " exceeds machine model writes for "
-           << *DefMI << " (Try with MCSchedModel.CompleteModel set to false)";
+           << *DefMI << " (Try with MCSchedModel.CompleteModel set to false)\n";
     llvm_unreachable("incomplete machine model");
   }
 #endif
   // FIXME: Automatically giving all implicit defs defaultDefLatency is
   // undesirable. We should only do it for defs that are known to the MC
   // desc like flags. Truly implicit defs should get 1 cycle latency.
   return DefMI->isTransient() ? 0 : TII->defaultDefLatency(SchedModel, DefMI);
 }

utils/TableGen/CodeGenSchedule.h

struct CodeGenProcModel {
   // 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;
 
+  // List of unsupported feature combinations.
+  // This list is empty if no UnsupportedFeature refers to this Processor.
+  RecVec UnsupportedFeaturesDefs;
+
   // All read/write resources associated with this processor.
   RecVec WriteResDefs;
   RecVec ReadAdvanceDefs;
 
   // Per-operand machine model resources associated with this processor.
   RecVec ProcResourceDefs;
   RecVec ProcResGroupDefs;
 
   CodeGenProcModel(unsigned Idx, const std::string &Name, Record *MDef,
                    Record *IDef) :
     Index(Idx), ModelName(Name), ModelDef(MDef), ItinsDef(IDef) {}
 
   bool hasItineraries() const {
     return !ItinsDef->getValueAsListOfDefs("IID").empty();
   }
 
   bool hasInstrSchedModel() const {
     return !WriteResDefs.empty() || !ItinRWDefs.empty();
   }
 
   unsigned getProcResourceIdx(Record *PRDef) const;
 
+  bool isUnsupported(const CodeGenInstruction &Inst) const;
+
 #ifndef NDEBUG
   void dump() const;
 #endif
 };
 
 /// Top level container for machine model data.
 class CodeGenSchedModels {
   RecordKeeper &Records;
std::string createSchedClassName(Record *ItinClassDef,
                                    ArrayRef<unsigned> OperReads);
   std::string createSchedClassName(const RecVec &InstDefs);
   void createInstRWClass(Record *InstRWDef);
 
   void collectProcItins();
 
   void collectProcItinRW();
 
+  void collectProcUnsupportedFeatures();
+
   void inferSchedClasses();
 
   void checkCompleteness();
 
   void inferFromRW(ArrayRef<unsigned> OperWrites, ArrayRef<unsigned> OperReads,
                    unsigned FromClassIdx, ArrayRef<unsigned> ProcIndices);
   void inferFromItinClass(Record *ItinClassDef, unsigned FromClassIdx);
   void inferFromInstRWs(unsigned SCIdx);

utils/TableGen/CodeGenSchedule.cpp

CodeGenSchedModels::CodeGenSchedModels(RecordKeeper &RK,
   // CodeGenProcModel::ItinDefList. (Cycle-to-cycle itineraries). This requires
   // all itinerary classes to be discovered.
   collectProcItins();
 
   // Find ItinRW records for each processor and itinerary class.
   // (For per-operand resources mapped to itinerary classes).
   collectProcItinRW();
 
+  // Find UnsupportedFeatures records for each processor.
+  // (For per-operand resources mapped to itinerary classes).
+  collectProcUnsupportedFeatures();
+
   // Infer new SchedClasses from SchedVariant.
   inferSchedClasses();
 
   // Populate each CodeGenProcModel's WriteResDefs, ReadAdvanceDefs, and
   // ProcResourceDefs.
   collectProcResources();
 
   checkCompleteness();
for (RecIter II = ItinRWDefs.begin(), IE = ItinRWDefs.end(); II != IE; ++II) {
     if (I == ProcModelMap.end()) {
       PrintFatalError((*II)->getLoc(), "Undefined SchedMachineModel "
                     + ModelDef->getName());
     }
     ProcModels[I->second].ItinRWDefs.push_back(*II);
   }
 }
 
+// Gather the unsupported features for a processor model.
+void CodeGenSchedModels::collectProcUnsupportedFeatures() {
+  RecVec UnsupportedFeaturesDefs =
+      Records.getAllDerivedDefinitions("UnsupportedFeatures");
+  std::sort(UnsupportedFeaturesDefs.begin(), UnsupportedFeaturesDefs.end(),
+            LessRecord());
+  for (RecIter II = UnsupportedFeaturesDefs.begin(),
+               IE = UnsupportedFeaturesDefs.end();
+       II != IE; ++II) {
+    if (!(*II)->getValueInit("SchedModel")->isComplete())
+      PrintFatalError((*II)->getLoc(), "SchedModel is undefined");
+    auto InsnPredicate = (*II)->getValue("Predicates")->getValue();
+    if (!Records.getDef(InsnPredicate->getAsUnquotedString()))
+      PrintFatalError((*II)->getLoc(),
+                      "Unknown Predicate: " + InsnPredicate->getAsString());
+    Record *ModelDef = (*II)->getValueAsDef("SchedModel");
+    ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
+    if (I == ProcModelMap.end()) {
+      PrintFatalError((*II)->getLoc(), "Undefined SchedMachineModel "
+                    + ModelDef->getName());
+    }
+    ProcModels[I->second].UnsupportedFeaturesDefs.push_back(*II);
+  }
+}
+
 /// Infer new classes from existing classes. In the process, this may create new
 /// SchedWrites from sequences of existing SchedWrites.
 void CodeGenSchedModels::inferSchedClasses() {
   DEBUG(dbgs() << NumInstrSchedClasses << " instr sched classes.\n");
 
   // Visit all existing classes and newly created classes.
   for (unsigned Idx = 0; Idx != SchedClasses.size(); ++Idx) {
     assert(SchedClasses[Idx].Index == Idx && "bad SCIdx");
void CodeGenSchedModels::checkCompleteness() {
   bool Complete = true;
   bool HadCompleteModel = false;
   for (const CodeGenProcModel &ProcModel : procModels()) {
     if (!ProcModel.ModelDef->getValueAsBit("CompleteModel"))
       continue;
     for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) {
       if (Inst->hasNoSchedulingInfo)
         continue;
+      if (ProcModel.isUnsupported(*Inst))
+        continue;
       unsigned SCIdx = getSchedClassIdx(*Inst);
       if (!SCIdx) {
         if (Inst->TheDef->isValueUnset("SchedRW") && !HadCompleteModel) {
           PrintError("No schedule information for instruction '"
                      + Inst->TheDef->getName() + "'");
           Complete = false;
         }
         continue;
RecIter PRPos = std::find(ProcResourceDefs.begin(), ProcResourceDefs.end(),
                             PRDef);
   if (PRPos == ProcResourceDefs.end())
     PrintFatalError(PRDef->getLoc(), "ProcResource def is not included in "
                     "the ProcResources list for " + ModelName);
   // Idx=0 is reserved for invalid.
   return 1 + (PRPos - ProcResourceDefs.begin());
 }
 
+bool CodeGenProcModel::isUnsupported(const CodeGenInstruction &Inst) const {
+  for (const Record *TheDef : UnsupportedFeaturesDefs) {
+    for (const Record *PredDef : Inst.TheDef->getValueAsListOfDefs("Predicates")) {
+      if (TheDef->getValueAsString("Predicates") == PredDef->getName())
+        return true;
+    }
+  }
+  return false;
+}
+
 #ifndef NDEBUG
 void CodeGenProcModel::dump() const {
   dbgs() << Index << ": " << ModelName << " "
          << (ModelDef ? ModelDef->getName() : "inferred") << " "
          << (ItinsDef ? ItinsDef->getName() : "no itinerary") << '\n';
 }
 
 void CodeGenSchedRW::dump() const {