TableGen: Check scheduling models for completeness

[MatzeB]

Summary

For now this is only enabled for subtargets which set CheckCompleteness = 1 in their scheduling model.

[atrick]

This seems 100% redundant with CompleteModel but the inverse meaning. Why don't you correct the flag for incomplete targets and file bugs against them?

[MatzeB]

New version which which does introduce the new CheckCompleteness flag anymore but uses the existing CompleteModel flag. Also sets CompleteModel = 0 on incomplete models (which is all of them).

[atrick]

LGTM; Are they all really incomplete though once you add your hasNoSchedulingInfo flag?

[MatzeB]

In D17747#365534, @atrick wrote:

LGTM; Are they all really incomplete though once you add your hasNoSchedulingInfo flag?

Yes. My guess this is because

1. We currently only test completeness at runtime in assert builds but I don't think we test all the -mcpu=XXX variants that much in assert builds.
2. Things currently used as scheduling barriers are never queried (so don't fail on missing info)
3. Some instructions are not supported on every CPU in a target and have to be explicitely marked as unsupported.

[MatzeB]

In D17747#365552, @MatzeB wrote:

In D17747#365534, @atrick wrote:

LGTM; Are they all really incomplete though once you add your hasNoSchedulingInfo flag?

Yes. My guess this is because

1. We currently only test completeness at runtime in assert builds but I don't think we test all the -mcpu=XXX variants that much in assert builds.
2. Things currently used as scheduling barriers are never queried (so don't fail on missing info)
3. Some instructions are not supported on every CPU in a target and have to be explicitely marked as unsupported.

You can also look here for an example of what was missing in the Cyclone model: http://reviews.llvm.org/D17748

[dsanders]

llvm/trunk/lib/Target/Mips/MipsScheduleP5600.td

16

Hi,

I see you've changed our P5600 model to be incomplete but it is actually complete. We want the compiler to assert if it's asked to schedule an instruction that has no scheduling information since these instructions are not supposed to be possible on the P5600. This assertion will no longer occur with this change.

[llvm-commits]

Static checking should be more robust long-term than relying on the dynamic checks with the assert. This however means that instructions not supported by a CPU should be explicitely marked as unsupported. I just pushed a commit which lets you mark InstRW expressions as unsupported (on top of the existing support to mark scheduling resources as unsupported or whole instructions as not appearing in the scheduler). So it should be easy to get the list from tablegen and exclude the missing instructions with something like:

// Exclude micromips instructions
def : InstRW<[], (instregex ".*_MM$", ".*_MMR[0-9]$")> { let Unsupported = 1; }

Is that okay?

• Matthias

[atrick]

Thanks Matthias. If you mark the model complete, won't tablegen give you a list of all unimplemented opcodes without even passing any debug flags to tablgen?

Can you just wrap the whole list of unsupported instruction like this?

let Unsupported = 1 {

def : InstRW...

You can also provide a comma separated list of opcode names or regexes:

def : InstRW<[], (instrs "A", B", ...)>

You don't need a separate InstRW for each.

I think this is a pretty trivial copy-paste step and agree it's better than the dynamic check.

[dsanders]

I agree that a static check is generally better than a dynamic check. However we have quite a lot of instructions to mark unsupported due to the way things like MIPS16 and microMIPS are implemented. I'll have a quick look into marking instructions unsupported by feature bit. That should allow us to cover the majority of our unsupported instructions concisely.

[dsanders]

I've looked into it and it seems we did have a few holes in our model. In particular, MSA has been overlooked and a few of the rarer instructions are also missing. However, the majority are unsupported on the only processor which currently has a SchedModel.

// Exclude micromips instructions
def : InstRW<[], (instregex ".*_MM$", ".*_MMR[0-9]$")> { let Unsupported = 1; }

Is that okay?

I believe this works by providing an empty list of scheduling information. Won't this disable the dynamic check for these instructions? As far as I can tell, the Unsupported field only serves as documentation.

Another issue is that, some parts of our instruction are difficult to create regexes for. The examples I'm thinking of are:

• Most of the R6 instructions lack the '_R6' suffix. It was only used where it would otherwise conflict with pre-R6 instructions.
• DSP/MSA/etc. don't have 'DSP'/'MSA'/etc. in their name. They just use the mnemonic.
• When we add R6-only processors like the I6400 we'll want to mark the pre-R6 versions of the '*_R6' instructions unsupported.

At the moment, I'm thinking we could add a class that marks all instructions with a specified Predicate as being unsupported. For example:

def : UnsupportedFeatures<"HasMips3">;    // All 64-bit ISA's are unsupported (HasMips3 and any superset are unsupported).
def : UnsupportedFeatures<"HasMips32R6">; // All R6 ISA's are unsupported (HasMips32R6 and any superset are unsupported).
def : UnsupportedFeatures<"HasCnMips">;   // Octeon ASE's are unsupported.
.. etc.

Then CodeGenSchedModels::checkCompleteness() could check for unsupported instructions just after the Inst->hasNoSchedulingInfo check. This suggestion deals with the first two examples, but not the third. I don't have a good solution for that one yet. We could solve it by listing each instruction individually but it would be a shame to have to do that for each and every R6 processor we add in the future.

[atrick]

I think marking the scheduling class as Unsupported will result in invalid scheduling info. It might be good to add a dynamic assert ensuring that all scheduling classes are valid if the model is complete.

llvm/trunk/include/llvm/Target/TargetSchedule.td

class SchedMachineModel {
   // resulting from changes to the instruction definitions.
   bit CompleteModel = 1;
 
   bit NoModel = 0; // Special tag to indicate missing machine model.
 }
 
 def NoSchedModel : SchedMachineModel {
   let NoModel = 1;
+  let CompleteModel = 0;
 }
 
 // Define a kind of processor resource that may be common across
 // similar subtargets.
 class ProcResourceKind;
 
 // Define a number of interchangeable processor resources. NumUnits
 // determines the throughput of instructions that require the resource.

llvm/trunk/lib/Target/AArch64/AArch64SchedA53.td

def CortexA53Model : SchedMachineModel {
   let IssueWidth = 2;        // 2 micro-ops are dispatched per cycle.
   let MinLatency = 1 ;       // OperandCycles are interpreted as MinLatency.
   let LoadLatency = 3;       // Optimistic load latency assuming bypass.
                              // This is overriden by OperandCycles if the
                              // Itineraries are queried instead.
   let MispredictPenalty = 9; // Based on "Cortex-A53 Software Optimisation
                              // Specification - Instruction Timings"
                              // v 1.0 Spreadsheet
+  let CompleteModel = 0;
 }
 
 
 //===----------------------------------------------------------------------===//
 // Define each kind of processor resource and number available.
 
 // Modeling each pipeline as a ProcResource using the BufferSize = 0 since
 // Cortex-A53 is in-order.

llvm/trunk/lib/Target/AArch64/AArch64SchedA57.td

def CortexA57Model : SchedMachineModel {
   let IssueWidth        =   3; // 3-way decode and dispatch
   let MicroOpBufferSize = 128; // 128 micro-op re-order buffer
   let LoadLatency       =   4; // Optimistic load latency
   let MispredictPenalty =  14; // Fetch + Decode/Rename/Dispatch + Branch
 
   // Enable partial & runtime unrolling. The magic number is chosen based on
   // experiments and benchmarking data.
   let LoopMicroOpBufferSize = 16;
+  let CompleteModel = 0;
 }
 
 //===----------------------------------------------------------------------===//
 // Define each kind of processor resource and number available on Cortex-A57.
 // Cortex A-57 has 8 pipelines that each has its own 8-entry queue where
 // micro-ops wait for their operands and then issue out-of-order.
 
 def A57UnitB : ProcResource<1>;  // Type B micro-ops

llvm/trunk/lib/Target/AArch64/AArch64SchedCyclone.td

 //
 //===----------------------------------------------------------------------===//
 
 def CycloneModel : SchedMachineModel {
   let IssueWidth = 6; // 6 micro-ops are dispatched per cycle.
   let MicroOpBufferSize = 192; // Based on the reorder buffer.
   let LoadLatency = 4; // Optimistic load latency.
   let MispredictPenalty = 16; // 14-19 cycles are typical.
+  let CompleteModel = 0;
 }
 
 //===----------------------------------------------------------------------===//
 // Define each kind of processor resource and number available on Cyclone.
 
 // 4 integer pipes
 def CyUnitI : ProcResource<4> {
   let BufferSize = 48;

llvm/trunk/lib/Target/AArch64/AArch64SchedKryo.td

def KryoModel : SchedMachineModel {
   let IssueWidth        =   5; // 5-wide issue for expanded uops
   let MicroOpBufferSize = 128; // Out-of-order with temporary unified issue buffer
   let LoadLatency       =   4; // Optimistic load latency
   let MispredictPenalty =  14; // Fetch + Decode/Rename/Dispatch + Branch
 
   // Enable partial & runtime unrolling. The magic number is chosen based on
   // experiments and benchmarking data.
   let LoopMicroOpBufferSize = 16;
+  let CompleteModel = 0;
 }
 
 //===----------------------------------------------------------------------===//
 // Define each kind of processor resource and number available on Kryo.
 
 let SchedModel = KryoModel in {
   def KryoUnitXA : ProcResource<1>;                   // Type X(A) micro-ops
   def KryoUnitXB : ProcResource<1>;                   // Type X(B) micro-ops

llvm/trunk/lib/Target/AMDGPU/SISchedule.td

 
 // Half rate 64-bit instructions.
 def Write64Bit : SchedWrite;
 
 // FIXME: Should there be a class for instructions which are VALU
 // instructions and have VALU rates, but write to the SALU (i.e. VOPC
 // instructions)
 
-def SIFullSpeedModel : SchedMachineModel;
-def SIQuarterSpeedModel : SchedMachineModel;
+def SIFullSpeedModel : SchedMachineModel {
+  let CompleteModel = 0;
+}
+def SIQuarterSpeedModel : SchedMachineModel {
+  let CompleteModel = 0;
+}
 
 // BufferSize = 0 means the processors are in-order.
 let BufferSize = 0 in {
 
 // XXX: Are the resource counts correct?
 def HWBranch : ProcResource<1>;
 def HWExport : ProcResource<7>;   // Taken from S_WAITCNT
 def HWLGKM   : ProcResource<31>;  // Taken from S_WAITCNT

llvm/trunk/lib/Target/ARM/ARMScheduleA8.td

 // Cortex-A8 machine model for scheduling and other instruction cost heuristics.
 def CortexA8Model : SchedMachineModel {
   let IssueWidth = 2; // 2 micro-ops are dispatched per cycle.
   let MinLatency = -1; // OperandCycles are interpreted as MinLatency.
   let LoadLatency = 2; // Optimistic load latency assuming bypass.
                        // This is overriden by OperandCycles if the
                        // Itineraries are queried instead.
   let MispredictPenalty = 13; // Based on estimate of pipeline depth.
+  let CompleteModel = 0;
 
   let Itineraries = CortexA8Itineraries;
 }

llvm/trunk/lib/Target/Hexagon/HexagonScheduleV4.td

def HexagonItinerariesV4 :
                                 InstrStage<1, [SLOT2, SLOT3]>]>
       ]>;
 
 def HexagonModelV4 : SchedMachineModel {
   // Max issue per cycle == bundle width.
   let IssueWidth = 4;
   let Itineraries = HexagonItinerariesV4;
   let LoadLatency = 1;
+  let CompleteModel = 0;
 }
 
 //===----------------------------------------------------------------------===//
 // Hexagon V4 Resource Definitions -
 //===----------------------------------------------------------------------===//

llvm/trunk/lib/Target/Hexagon/HexagonScheduleV55.td

def HexagonItinerariesV55 :
 
       ]>;
 
 def HexagonModelV55 : SchedMachineModel {
   // Max issue per cycle == bundle width.
   let IssueWidth = 4;
   let Itineraries = HexagonItinerariesV55;
   let LoadLatency = 1;
+  let CompleteModel = 0;
 }
 
 //===----------------------------------------------------------------------===//
 // Hexagon V4 Resource Definitions -
 //===----------------------------------------------------------------------===//

llvm/trunk/lib/Target/Hexagon/HexagonScheduleV60.td

def HexagonItinerariesV60 :
                                     InstrStage<1, [CVI_ALL]>]>
       ]>;
 
 def HexagonModelV60 : SchedMachineModel {
   // Max issue per cycle == bundle width.
   let IssueWidth = 4;
   let Itineraries = HexagonItinerariesV60;
   let LoadLatency = 1;
+  let CompleteModel = 0;
 }
 
 //===----------------------------------------------------------------------===//
 // Hexagon V60 Resource Definitions -
 //===----------------------------------------------------------------------===//

llvm/trunk/lib/Target/Mips/MipsScheduleP5600.td

 //==- MipsScheduleP5600.td - P5600 Scheduling Definitions --*- tablegen -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 def MipsP5600Model : SchedMachineModel {
   int IssueWidth = 2; // 2x dispatched per cycle
   int MicroOpBufferSize = 48; // min(48, 48, 64)
   int LoadLatency = 4;
   int MispredictPenalty = 8; // TODO: Estimated
 
-  let CompleteModel = 1;
+  let CompleteModel = 0;
 }
 
 let SchedModel = MipsP5600Model in {
 
 // ALQ Pipelines
 // =============
 
 def P5600ALQ : ProcResource<1> { let BufferSize = 16; }

llvm/trunk/lib/Target/PowerPC/PPCSchedule440.td

 
 def PPC440Model : SchedMachineModel {
   let IssueWidth = 2;  // 2 instructions are dispatched per cycle.
   let MinLatency = -1; // OperandCycles are interpreted as MinLatency.
   let LoadLatency = 5; // Optimistic load latency assuming bypass.
                        // This is overriden by OperandCycles if the
                        // Itineraries are queried instead.
 
+  let CompleteModel = 0;
+
   let Itineraries = PPC440Itineraries;
 }
 

llvm/trunk/lib/Target/PowerPC/PPCScheduleA2.td

 def PPCA2Model : SchedMachineModel {
   let IssueWidth = 1;  // 1 instruction is dispatched per cycle.
   let MinLatency = -1; // OperandCycles are interpreted as MinLatency.
   let LoadLatency = 6; // Optimistic load latency assuming bypass.
                        // This is overriden by OperandCycles if the
                        // Itineraries are queried instead.
   let MispredictPenalty = 13;
 
+  let CompleteModel = 0;
+
   let Itineraries = PPCA2Itineraries;
 }
 

llvm/trunk/lib/Target/PowerPC/PPCScheduleE500mc.td

 
 def PPCE500mcModel : SchedMachineModel {
   let IssueWidth = 2;  // 2 micro-ops are dispatched per cycle.
   let MinLatency = -1; // OperandCycles are interpreted as MinLatency.
   let LoadLatency = 5; // Optimistic load latency assuming bypass.
                        // This is overriden by OperandCycles if the
                        // Itineraries are queried instead.
 
+  let CompleteModel = 0;
+
   let Itineraries = PPCE500mcItineraries;
 }

llvm/trunk/lib/Target/PowerPC/PPCScheduleE5500.td

 
 def PPCE5500Model : SchedMachineModel {
   let IssueWidth = 2;  // 2 micro-ops are dispatched per cycle.
   let MinLatency = -1; // OperandCycles are interpreted as MinLatency.
   let LoadLatency = 6; // Optimistic load latency assuming bypass.
                        // This is overriden by OperandCycles if the
                        // Itineraries are queried instead.
 
+  let CompleteModel = 0;
+
   let Itineraries = PPCE5500Itineraries;
 }

llvm/trunk/lib/Target/PowerPC/PPCScheduleG5.td

 def G5Model : SchedMachineModel {
   let IssueWidth = 4;  // 4 (non-branch) instructions are dispatched per cycle.
   let MinLatency = 0;  // Out-of-order dispatch.
   let LoadLatency = 3; // Optimistic load latency assuming bypass.
                        // This is overriden by OperandCycles if the
                        // Itineraries are queried instead.
   let MispredictPenalty = 16;
 
+  let CompleteModel = 0;
+
   let Itineraries = G5Itineraries;
 }
 

llvm/trunk/lib/Target/PowerPC/PPCScheduleP7.td

def P7Model : SchedMachineModel {
   let LoadLatency = 3; // Optimistic load latency assuming bypass.
                        // This is overriden by OperandCycles if the
                        // Itineraries are queried instead.
   let MispredictPenalty = 16;
 
   // Try to make sure we have at least 10 dispatch groups in a loop.
   let LoopMicroOpBufferSize = 40;
 
+  let CompleteModel = 0;
+
   let Itineraries = P7Itineraries;
 }
 

llvm/trunk/lib/Target/PowerPC/PPCScheduleP8.td

def P8Model : SchedMachineModel {
   let LoadLatency = 3; // Optimistic load latency assuming bypass.
                        // This is overriden by OperandCycles if the
                        // Itineraries are queried instead.
   let MispredictPenalty = 16;
 
   // Try to make sure we have at least 10 dispatch groups in a loop.
   let LoopMicroOpBufferSize = 60;
 
+  let CompleteModel = 0;
+
   let Itineraries = P8Itineraries;
 }
 

llvm/trunk/lib/Target/X86/X86Schedule.td

 //
 // The GenericModel contains no instruction itineraries.
 def GenericModel : SchedMachineModel {
   let IssueWidth = 4;
   let MicroOpBufferSize = 32;
   let LoadLatency = 4;
   let HighLatency = 10;
   let PostRAScheduler = 0;
+  let CompleteModel = 0;
 }
 
 include "X86ScheduleAtom.td"
 include "X86SchedSandyBridge.td"
 include "X86SchedHaswell.td"
 include "X86ScheduleSLM.td"
 include "X86ScheduleBtVer2.td"
 

llvm/trunk/lib/Target/X86/X86ScheduleAtom.td

def AtomModel : SchedMachineModel {
   let MicroOpBufferSize = 0; // In-order execution, always hide latency.
   let LoadLatency = 3; // Expected cycles, may be overriden by OperandCycles.
   let HighLatency = 30;// Expected, may be overriden by OperandCycles.
 
   // On the Atom, the throughput for taken branches is 2 cycles. For small
   // simple loops, expand by a small factor to hide the backedge cost.
   let LoopMicroOpBufferSize = 10;
   let PostRAScheduler = 1;
+  let CompleteModel = 0;
 
   let Itineraries = AtomItineraries;
 }

llvm/trunk/utils/TableGen/CodeGenSchedule.h

private:
   void createInstRWClass(Record *InstRWDef);
 
   void collectProcItins();
 
   void collectProcItinRW();
 
   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);
 
   bool hasSuperGroup(RecVec &SubUnits, CodeGenProcModel &PM);
   void verifyProcResourceGroups(CodeGenProcModel &PM);
 

llvm/trunk/utils/TableGen/CodeGenSchedule.cpp

CodeGenSchedModels::CodeGenSchedModels(RecordKeeper &RK,
   collectProcItinRW();
 
   // Infer new SchedClasses from SchedVariant.
   inferSchedClasses();
 
   // Populate each CodeGenProcModel's WriteResDefs, ReadAdvanceDefs, and
   // ProcResourceDefs.
   collectProcResources();
+
+  checkCompleteness();
 }
 
 /// Gather all processor models.
 void CodeGenSchedModels::collectProcModels() {
   RecVec ProcRecords = Records.getAllDerivedDefinitions("Processor");
   std::sort(ProcRecords.begin(), ProcRecords.end(), LessRecordFieldName());
 
   // Reserve space because we can. Reallocation would be ok.
DEBUG(
              RE = PM.ProcResourceDefs.end(); RI != RE; ++RI) {
         dbgs() << (*RI)->getName() << " ";
       }
       dbgs() << '\n');
     verifyProcResourceGroups(PM);
   }
 }
 
+void CodeGenSchedModels::checkCompleteness() {
+  bool Complete = true;
+  bool HadCompleteModel = false;
+  for (const CodeGenProcModel &ProcModel : procModels()) {
+    // Note that long-term we should check "CompleteModel", but for now most
+    // models that claim to be complete are actually not so we use a separate
+    // "CheckCompleteness" bit.
+    if (!ProcModel.ModelDef->getValueAsBit("CompleteModel"))
+      continue;
+    for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) {
+      if (Inst->hasNoSchedulingInfo)
+        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;
+      }
+
+      const CodeGenSchedClass &SC = getSchedClass(SCIdx);
+      if (!SC.Writes.empty())
+        continue;
+
+      const RecVec &InstRWs = SC.InstRWs;
+      auto I = std::find_if(InstRWs.begin(), InstRWs.end(),
+                            [&ProcModel] (const Record *R) {
+                              return R->getValueAsDef("SchedModel") == ProcModel.ModelDef;
+                            });
+      if (I == InstRWs.end()) {
+        PrintError("'" + ProcModel.ModelName + "' lacks information for '" +
+                   Inst->TheDef->getName() + "'");
+        Complete = false;
+      }
+    }
+    HadCompleteModel = true;
+  }
+  if (!Complete)
+    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];
     // For all ItinRW entries.
     bool HasMatch = false;
     for (RecIter II = PM.ItinRWDefs.begin(), IE = PM.ItinRWDefs.end();
          II != IE; ++II) {