[TableGen] CheckSchedClassTables - check for unnecessary scheduler overrides

[RKSimon]

Summary

Pulled out of D47637, which was based off some internal work I did years ago but got lost in the upstreaming process.

This patch adds a SubtargetEmitter::CheckSchedClassTables method to verify the state of the scheduler classes. A command line switch "-check-sched-class-table" is added, which is enabled by default for EXPENSIVE_CHECKS builds.

So far this just adds checks for unnecessary overrides of base classes (which typically end up causing bloat in the generated tables), but future patches will add additional checks similar to earlier versions of D47637 and D48222.

The number of unnecessary overrides that are listed are quite extensive (warnings are currently found in the AMDGPU, ARM, AArch64, PowerPC and X86 targets), I'm not convinced they need to be addressed before this patch is committed, although the spam in EXPENSIVE_CHECKS builds is pretty large, but I'm happy to help create bugs/patches to fix them first if reviewers would prefer it.

[lebedev.ri]

Just how more extra noisy does it become?

[RKSimon]

llvm/include/llvm/MC/MCSchedule.h

158

Sorry - I should have removed the "NumReadAdvanceEntries == 0" entry, it was just an experiment

[RKSimon]

In D138359#3939209, @lebedev.ri wrote:

Just how more extra noisy does it become?

Current warnings:
AMDGPU - 1
AArch64 - 3049
ARM - 992
PowerPC - 244
X86 - 227

Actually its worse than I thought so almost definitely needs addressing before this can land :)

[pengfei]

In D138359#3939221, @RKSimon wrote:

In D138359#3939209, @lebedev.ri wrote:

Just how more extra noisy does it become?

Current warnings:
AMDGPU - 1
AArch64 - 3049
ARM - 992
PowerPC - 244
X86 - 227

Actually its worse than I thought so almost definitely needs addressing before this can land :)

We can only find one overridden pair each time, right?

llvm/include/llvm/MC/MCSchedule.h

158

But the comment mentioned it too?

llvm/utils/TableGen/CodeGenSchedule.cpp

972

Not familiar with it, does the old function returns 0 too when fail to loopup?

llvm/utils/TableGen/SubtargetEmitter.cpp

1378

Do we need to break the loop?

[RKSimon]

In D138359#3939621, @pengfei wrote:

We can only find one overridden pair each time, right?

Yes each warning is per instruction + per model - e.,g. there are usually 2 warnings for the znver1/2 overrides as they are basically copies of each other.

The x86 cases I'm slowly working through as I'm confident about what is going on - but for other targets my concern is that they've ended up with at least some overrides just so each model has the same entries, even though some are redundant.

[RKSimon]

Remove "NumReadAdvanceEntries == 0" test code

[RKSimon]

cleanup comment

[RKSimon]

llvm/utils/TableGen/CodeGenSchedule.cpp

1149

Something we could consider is checking here if the base and override classes COMPLETELY match and just don't bother using the override class? We should probably still warn though.

[HaohaiWen]

llvm/utils/TableGen/CodeGenSchedule.cpp

972

DenseMap returns new constructed value if not existed. In this case, it should be uninitialized unsigned.
Looks like return 0 is better.

SchedClasses.emplace_back(0, "NoInstrModel",
                          Records.getDef("NoItinerary"));

[HaohaiWen]

llvm/utils/TableGen/SubtargetEmitter.cpp

1378

Can we use InstRW to overwrite same instruction on same schedule model twice?
I tried and trigged assertion in CodeGenSchedule.cpp:1088.

[RKSimon]

About to go on PTO - I will try to get these changes applied soon.

[RKSimon]

rebase

[RKSimon]

I'm intending to resurrect this patch soon - most of the X86 warnings have been addressed but there are still a lot of ARM/AArch64/Power warnings that need cleaning up

llvm/include/llvm/MC/MCSchedule.h

#endif
   uint16_t NumReadAdvanceEntries;
 
   bool isValid() const {
     return NumMicroOps != InvalidNumMicroOps;
   }
   bool isVariant() const {
     return NumMicroOps == VariantNumMicroOps;
   }
+  bool equals(const MCSchedClassDesc &RHS,
+              bool IgnoreRHSReadAdvance = false) const {
+    // If IgnoreRHSReadAdvance is set, then ignore any mismatch with RHS
+    // (override class) as overrides are often missing them.
+    return NumMicroOps == RHS.NumMicroOps &&
+           BeginGroup == RHS.BeginGroup &&
+           EndGroup == RHS.EndGroup &&
+           RetireOOO == RHS.RetireOOO &&
+           WriteProcResIdx == RHS.WriteProcResIdx &&
+           NumWriteProcResEntries == RHS.NumWriteProcResEntries &&
+           WriteLatencyIdx == RHS.WriteLatencyIdx &&
+           NumWriteLatencyEntries == RHS.NumWriteLatencyEntries &&
+           (IgnoreRHSReadAdvance ||
+            (ReadAdvanceIdx == RHS.ReadAdvanceIdx &&
+             NumReadAdvanceEntries == RHS.NumReadAdvanceEntries));
+  }
 };
 
 /// Specify the cost of a register definition in terms of number of physical
 /// register allocated at register renaming stage. For example, AMD Jaguar.
 /// natively supports 128-bit data types, and operations on 256-bit registers
 /// (i.e. YMM registers) are internally split into two COPs (complex operations)
 /// and each COP updates a physical register. Basically, on Jaguar, a YMM
 /// register write effectively consumes two physical registers. That means,

llvm/utils/TableGen/CodeGenSchedule.h

class CodeGenSchedModels {
   // Any inferred SchedClass has an index greater than NumInstrSchedClassses.
   unsigned NumInstrSchedClasses;
 
   RecVec ProcResourceDefs;
   RecVec ProcResGroups;
 
   // Map each instruction to its unique SchedClass index considering the
   // combination of it's itinerary class, SchedRW list, and InstRW records.
-  using InstClassMapTy = DenseMap<Record*, unsigned>;
+  // Stores both the original SchedRW class index, and the InstRW override.
+  using InstClassMapTy = DenseMap<Record *, std::pair<unsigned, unsigned>>;
   InstClassMapTy InstrClassMap;
 
   std::vector<STIPredicateFunction> STIPredicates;
   std::vector<unsigned> getAllProcIndices() const;
 
 public:
   CodeGenSchedModels(RecordKeeper& RK, const CodeGenTarget &TGT);
 
const CodeGenSchedClass &getSchedClass(unsigned Idx) const {
     return SchedClasses[Idx];
   }
 
   // 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;
 
+  // Get the SchedClass SchedRW/InstRW indices for an instruction. Instructions
+  // with no itinerary, no SchedReadWrites, and no InstrReadWrites references
+  // return None for NoItinerary.
+  std::optional<std::pair<unsigned, unsigned>>
+  getSchedClassIdxPair(const CodeGenInstruction &Inst) const;
+
   using SchedClassIter = std::vector<CodeGenSchedClass>::const_iterator;
   SchedClassIter schedClassBegin() const { return SchedClasses.begin(); }
   SchedClassIter schedClassEnd() const { return SchedClasses.end(); }
   ArrayRef<CodeGenSchedClass> schedClasses() const { return SchedClasses; }
 
   unsigned numInstrSchedClasses() const { return NumInstrSchedClasses; }
 
   void findRWs(const RecVec &RWDefs, IdxVec &Writes, IdxVec &Reads) const;

llvm/utils/TableGen/CodeGenSchedule.cpp

void CodeGenSchedModels::collectSchedClasses() {
   for (const CodeGenInstruction *Inst : Target.getInstructionsByEnumValue()) {
     Record *ItinDef = Inst->TheDef->getValueAsDef("Itinerary");
     IdxVec Writes, Reads;
     if (!Inst->TheDef->isValueUnset("SchedRW"))
       findRWs(Inst->TheDef->getValueAsListOfDefs("SchedRW"), Writes, Reads);
 
     // ProcIdx == 0 indicates the class applies to all processors.
     unsigned SCIdx = addSchedClass(ItinDef, Writes, Reads, /*ProcIndices*/{0});
-    InstrClassMap[Inst->TheDef] = SCIdx;
+    InstrClassMap[Inst->TheDef] = std::make_pair(SCIdx, SCIdx);
   }
   // Create classes for InstRW defs.
   RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW");
   llvm::sort(InstRWDefs, LessRecord());
   LLVM_DEBUG(dbgs() << "\n+++ SCHED CLASSES (createInstRWClass) +++\n");
   for (Record *RWDef : InstRWDefs)
     createInstRWClass(RWDef);
 
LLVM_DEBUG({
       }
     });
   }
 }
 
 // Get the SchedClass index for an instruction.
 unsigned
 CodeGenSchedModels::getSchedClassIdx(const CodeGenInstruction &Inst) const {
-  return InstrClassMap.lookup(Inst.TheDef);
+  if (auto SchedPair = getSchedClassIdxPair(Inst))
+    return SchedPair->second;
+  return 0;
+}
+
+// Get the SchedClass SchedRW/InstRW pair for an instruction.
+std::optional<std::pair<unsigned, unsigned>>
+CodeGenSchedModels::getSchedClassIdxPair(const CodeGenInstruction &Inst) const {
+  auto It = InstrClassMap.find(Inst.TheDef);
+  if (It != InstrClassMap.end())
+    return It->second;
+  return std::nullopt;
 }
 
 std::string
 CodeGenSchedModels::createSchedClassName(Record *ItinClassDef,
                                          ArrayRef<unsigned> OperWrites,
                                          ArrayRef<unsigned> OperReads) {
 
   std::string Name;
void CodeGenSchedModels::createInstRWClass(Record *InstRWDef) {
   const RecVec *InstDefs = Sets.expand(InstRWDef);
   if (InstDefs->empty())
     PrintFatalError(InstRWDef->getLoc(), "No matching instruction opcodes");
 
   for (Record *InstDef : *InstDefs) {
     InstClassMapTy::const_iterator Pos = InstrClassMap.find(InstDef);
     if (Pos == InstrClassMap.end())
       PrintFatalError(InstDef->getLoc(), "No sched class for instruction.");
-    unsigned SCIdx = Pos->second;
+    unsigned SCIdx = Pos->second.second;
     ClassInstrs[SCIdx].push_back(InstDef);
   }
   // For each set of Instrs, create a new class if necessary, and map or remap
   // the Instrs to it.
   for (auto &Entry : ClassInstrs) {
     unsigned OldSCIdx = Entry.first;
     ArrayRef<Record*> InstDefs = Entry.second;
     // If the all instrs in the current class are accounted for, then leave
     // them mapped to their old class.
     if (OldSCIdx) {
       const RecVec &RWDefs = SchedClasses[OldSCIdx].InstRWs;
       if (!RWDefs.empty()) {
         const RecVec *OrigInstDefs = Sets.expand(RWDefs[0]);
-        unsigned OrigNumInstrs =
-          count_if(*OrigInstDefs, [&](Record *OIDef) {
-                     return InstrClassMap[OIDef] == OldSCIdx;
-                   });
+        unsigned OrigNumInstrs = count_if(*OrigInstDefs, [&](Record *OIDef) {
+          return InstrClassMap[OIDef].second == OldSCIdx;
         if (OrigNumInstrs == InstDefs.size()) {
           assert(SchedClasses[OldSCIdx].ProcIndices[0] == 0 &&
                  "expected a generic SchedClass");
           Record *RWModelDef = InstRWDef->getValueAsDef("SchedModel");
           // Make sure we didn't already have a InstRW containing this
           // instruction on this model.
           for (Record *RWD : RWDefs) {
             if (RWD->getValueAsDef("SchedModel") == RWModelDef &&
if (OldSCIdx) {
         }
         assert(OldRWDef != InstRWDef &&
                "SchedClass has duplicate InstRW def");
         SC.InstRWs.push_back(OldRWDef);
       }
     }
     // Map each Instr to this new class.
     for (Record *InstDef : InstDefs)
-      InstrClassMap[InstDef] = SCIdx;
+      InstrClassMap[InstDef].second = SCIdx;
     SC.InstRWs.push_back(InstRWDef);
   }
 }
 
 // True if collectProcItins found anything.
 bool CodeGenSchedModels::hasItineraries() const {
   for (const CodeGenProcModel &PM : make_range(procModelBegin(),procModelEnd()))
     if (PM.hasItineraries())

 /// Infer classes from per-processor InstReadWrite definitions.
 void CodeGenSchedModels::inferFromInstRWs(unsigned SCIdx) {
   for (unsigned I = 0, E = SchedClasses[SCIdx].InstRWs.size(); I != E; ++I) {
     assert(SchedClasses[SCIdx].InstRWs.size() == E && "InstrRWs was mutated!");
     Record *Rec = SchedClasses[SCIdx].InstRWs[I];
     const RecVec *InstDefs = Sets.expand(Rec);
     RecIter II = InstDefs->begin(), IE = InstDefs->end();
     for (; II != IE; ++II) {
-      if (InstrClassMap[*II] == SCIdx)
+      if (InstrClassMap[*II].second == SCIdx)
         break;
     }
     // If this class no longer has any instructions mapped to it, it has become
     // irrelevant.
     if (II == IE)
       continue;
     IdxVec Writes, Reads;
     findRWs(Rec->getValueAsListOfDefs("OperandReadWrites"), Writes, Reads);

llvm/utils/TableGen/SubtargetEmitter.cpp

 //===- SubtargetEmitter.cpp - Generate subtarget enumerations -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This tablegen backend emits subtarget enumerations.
 //
 //===----------------------------------------------------------------------===//
 
 #include "CodeGenHwModes.h"
+#include "CodeGenInstruction.h"
 #include "CodeGenSchedule.h"
 #include "CodeGenTarget.h"
 #include "PredicateExpander.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/MC/MCInstrItineraries.h"
 #include "llvm/MC/MCSchedule.h"
+#include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/TableGen/Error.h"
 #include "llvm/TableGen/Record.h"
 #include "llvm/TableGen/TableGenBackend.h"
 #include "llvm/TargetParser/SubtargetFeature.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <iterator>
 #include <map>
 #include <string>
 #include <vector>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "subtarget-emitter"
 
+static cl::opt<bool> OptCheckSchedClassTable(
+    "check-sched-class-table",
+#ifdef EXPENSIVE_CHECKS
+    cl::init(true),
+#else
+    cl::init(false),
+#endif
+    cl::Hidden, cl::desc("Check sched class tables for inconsistencies"));
+
 namespace {
 
 /// Sorting predicate to sort record pointers by their
 /// FieldName field.
 struct LessRecordFieldFieldName {
   bool operator()(const Record *Rec1, const Record *Rec2) const {
     return Rec1->getValueAsString("FieldName") <
            Rec2->getValueAsString("FieldName");
Record *FindWriteResources(const CodeGenSchedRW &SchedWrite,
                              const CodeGenProcModel &ProcModel);
   Record *FindReadAdvance(const CodeGenSchedRW &SchedRead,
                           const CodeGenProcModel &ProcModel);
   void ExpandProcResources(RecVec &PRVec, std::vector<int64_t> &Cycles,
                            std::vector<int64_t> &StartAtCycles,
                            const CodeGenProcModel &ProcModel);
   void GenSchedClassTables(const CodeGenProcModel &ProcModel,
                            SchedClassTables &SchedTables);
+  void CheckSchedClassTables(SchedClassTables &SchedTables);
   void EmitSchedClassTables(SchedClassTables &SchedTables, raw_ostream &OS);
   void EmitProcessorModels(raw_ostream &OS);
   void EmitSchedModelHelpers(const std::string &ClassName, raw_ostream &OS);
   void emitSchedModelHelpersImpl(raw_ostream &OS,
                                  bool OnlyExpandMCInstPredicates = false);
   void emitGenMCSubtargetInfo(raw_ostream &OS);
   void EmitMCInstrAnalysisPredicateFunctions(raw_ostream &OS);
 
if (RAPos != SchedTables.ReadAdvanceEntries.end())
       SCDesc.ReadAdvanceIdx = RAPos - SchedTables.ReadAdvanceEntries.begin();
     else {
       SCDesc.ReadAdvanceIdx = SchedTables.ReadAdvanceEntries.size();
       llvm::append_range(SchedTables.ReadAdvanceEntries, ReadAdvanceEntries);
     }
   }
 }
 
+// Check SchedClass tables for unnecessary duplication.
+void SubtargetEmitter::CheckSchedClassTables(SchedClassTables &SchedTables) {
+  ArrayRef<CodeGenSchedClass> SchedClasses = SchedModels.schedClasses();
+
+  for (const CodeGenInstruction *Inst : TGT.getInstructionsByEnumValue()) {
+    std::optional<std::pair<unsigned, unsigned>> ScIdx =
+        SchedModels.getSchedClassIdxPair(*Inst);
+    if (!ScIdx || ScIdx->first == 0 || ScIdx->first == ScIdx->second)
+      continue;
+
+    const CodeGenSchedClass &CgOrig = SchedClasses[ScIdx->first];
+    const CodeGenSchedClass &CgInst = SchedClasses[ScIdx->second];
+
+    for (CodeGenSchedModels::ProcIter PI = SchedModels.procModelBegin(),
+                                      PE = SchedModels.procModelEnd();
+         PI != PE; ++PI) {
+      if (!PI->hasInstrSchedModel())
+        continue;
+
+      // If the schedule has been overridden with values that match the base
+      // class then the override is redundant and could be removed.
+      // NOTE: Ignores missing/incorrect ReadAdvance attributes on the override.
+      const std::vector<MCSchedClassDesc> &SCTab =
+          SchedTables.ProcSchedClasses[1 + (PI - SchedModels.procModelBegin())];
+      const MCSchedClassDesc &ScOrig = SCTab[ScIdx->first];
+      const MCSchedClassDesc &ScInst = SCTab[ScIdx->second];
+      if (ScOrig.equals(ScInst, /*IgnoreReadAdvance*/ true)) {
+        for (const Record *InstrRW : CgInst.InstRWs) {
+          const Record *InstModelDef = InstrRW->getValueAsDef("SchedModel");
+          if (InstModelDef->getName() == PI->ModelName) {
+            dbgs() << "'" << PI->ModelName
+                   << "' unnecessarily overrides instruction '"
+                   << Inst->TheDef->getName() << "' from '" << CgOrig.Name
+                   << "'\n";
+            break;
+          }
+        }
+      }
+    }
+  }
+}
+
 // Emit SchedClass tables for all processors and associated global tables.
 void SubtargetEmitter::EmitSchedClassTables(SchedClassTables &SchedTables,
                                             raw_ostream &OS) {
   // Emit global WriteProcResTable.
   OS << "\n// {ProcResourceIdx, Cycles, StartAtCycle}\n"
      << "extern const llvm::MCWriteProcResEntry " << Target
      << "WriteProcResTable[] = {\n"
      << "  { 0,  0,  0 }, // Invalid\n";
void SubtargetEmitter::EmitSchedModel(raw_ostream &OS) {
   }
   OS << "\n// ===============================================================\n"
      << "// Data tables for the new per-operand machine model.\n";
 
   SchedClassTables SchedTables;
   for (const CodeGenProcModel &ProcModel : SchedModels.procModels()) {
     GenSchedClassTables(ProcModel, SchedTables);
   }
+
+  if (OptCheckSchedClassTable)
+    CheckSchedClassTables(SchedTables);
+
   EmitSchedClassTables(SchedTables, OS);
 
   OS << "\n#undef DBGFIELD\n";
 
   // Emit the processor machine model
   EmitProcessorModels(OS);
 }