[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

425

Needs a comment describing what this class is for.

426

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 ↗

(On Diff #58089)

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

 // Itineraries in addition to mapping instructions to ItineraryClasses.
 //===----------------------------------------------------------------------===//
 
 // Include legacy support for instruction itineraries.
 include "llvm/Target/TargetItinerary.td"
 
 class Instruction; // Forward def
 
+class Predicate; // Forward def
+
 // DAG operator that interprets the DAG args as Instruction defs.
 def instrs;
 
 // DAG operator that interprets each DAG arg as a regex pattern for
 // matching Instruction opcode names.
 // The regex must match the beginning of the opcode (as in Python re.match).
 // To avoid matching prefixes, append '$' to the pattern.
 def instregex;
class SchedMachineModel {
   // that have a scheduling class (itinerary class or SchedRW list)
   // and may actually be generated for that subtarget must clear this
   // bit. Otherwise, the scheduler considers an unmodelled opcode to
   // be an error. This should only be set during initial bringup,
   // or there will be no way to catch simple errors in the model
   // resulting from changes to the instruction definitions.
   bit CompleteModel = 1;
 
+  // A processor may only implement part of published ISA, due to either new ISA
+  // extensions, (e.g. Pentium 4 doesn't have AVX) or implementation
+  // (ARM/MIPS/PowerPC/SPARC soft float cores).
+  //
+  // For a processor which doesn't support some feature(s), the schedule model
+  // can use:
+  //
+  // let<Predicate> UnsupportedFeatures = [HaveA,..,HaveY];
+  //
+  // to skip the checks for scheduling information when building LLVM for
+  // instructions which have any of the listed predicates in their Predicates
+  // field.
+  list<Predicate> UnsupportedFeatures = [];
+
   bit NoModel = 0; // Special tag to indicate missing machine model.
 }
 
 def NoSchedModel : SchedMachineModel {
   let NoModel = 1;
   let CompleteModel = 0;
 }
 

 //
 // 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 = ?;
 }
 
 // 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 = ?;
 }

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.
+  // This list is empty if the Processor has no UnsupportedFeatures.
+  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 processor models.
+void CodeGenSchedModels::collectProcUnsupportedFeatures() {
+  for (CodeGenProcModel &ProcModel : ProcModels) {
+    for (Record *Pred : ProcModel.ModelDef->getValueAsListOfDefs("UnsupportedFeatures")) {
+       ProcModel.UnsupportedFeaturesDefs.push_back(Pred);
+    }
+  }
+}
+
 /// 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;
for (const CodeGenProcModel &ProcModel : procModels()) {
     }
     HadCompleteModel = true;
   }
   if (!Complete) {
     errs() << "\n\nIncomplete schedule models found.\n"
       << "- Consider setting 'CompleteModel = 0' while developing new models.\n"
       << "- Pseudo instructions can be marked with 'hasNoSchedulingInfo = 1'.\n"
       << "- Instructions should usually have Sched<[...]> as a superclass, "
-         "you may temporarily use an empty list.\n\n";
+         "you may temporarily use an empty list.\n"
+      << "- Instructions related to unsupported features can be excluded with "
+         "list<Predicate> UnsupportedFeatures = [HasA,..,HasY]; in the "
+         "processor model.\n\n";
     PrintFatalError("Incomplete schedule model");
   }
 }
 
 // Collect itinerary class resources for each processor.
 void CodeGenSchedModels::collectItinProcResources(Record *ItinClassDef) {
   for (unsigned PIdx = 0, PEnd = ProcModels.size(); PIdx != PEnd; ++PIdx) {
     const CodeGenProcModel &PM = ProcModels[PIdx];
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->getName() == 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 {