[TableGen][SubtargetEmitter] Add the StartAtCycles field in the WriteRes class.

[fpetrogalli]

Summary

Conditions that need to be met:

1. count(StartAtCycles) == count(ReservedCycles);
2. For each i: StartAtCycles[i] < ReservedCycles[i];
3. If left unspecified, the elements are set to 0.

[fpetrogalli]

Please refer to the documentation in https://reviews.llvm.org/D150312.

[andreadb]

Hi Francesco,

Thanks for contributing this patch!

In the past, I always wanted to add the ability to model "delayed resource consumption". However, I never got the time to actually do it.
On x86, we could use StartAtCycle to fix scheduling information for horizontal operations. We could also use it for improving instructions with folded loads (for which, we use read-advance entries).

In the past, the lack of a proper mechanism for describing delayed resource consumption was identified as the main reason why sometimes llvm-mca produced poor quality perf reports.
I remember I discussed this issue with Andrew Trick a couple of times.
Eventually, he suggested that we implemented something very similar to your StartAtCycle (see https://lists.llvm.org/pipermail/llvm-dev/2020-May/141487.html).
I believe that this (and the rest of your patch set) will fix issue: https://github.com/llvm/llvm-project/issues/45218

In future, more work will be needed to teach llvm-mca and exegesis how to correctly handle StartAtCycle information (if available).
However, that would be a separate task :).

Long story short: your approach looks good to me and it similar to what was suggested in the past by others.

Patch looks good to me (modulo a few minor nits - see below).

Cheers,
-Andrea

llvm/include/llvm/MC/MCSchedule.h

62

This code comment should describe (in a sentence or two) what is StartAtCycle used for.

llvm/tools/llvm-exegesis/lib/SchedClassResolution.cpp

86

Is there a ticket for this?

llvm/utils/TableGen/SubtargetEmitter.cpp

1196–1197

Should we also check for negative values? Not that I expect people to use negative delay cycles.

[RKSimon]

llvm/utils/TableGen/SubtargetEmitter.cpp

1327–1328

Updated generated comment: {ProcResourceIdx, Cycles, StartCycles}

[RKSimon]

llvm/tools/llvm-exegesis/lib/SchedClassResolution.cpp

86

I've raised these to discuss future support for llvm-exegesis and llvm-mca
https://github.com/llvm/llvm-project/issues/62680
https://github.com/llvm/llvm-project/issues/62681

[RKSimon]

llvm/utils/TableGen/SubtargetEmitter.cpp

1221

Comment indentation looks wrong?

[fpetrogalli]

Address first round of review. Thank you @RKSimon and @andreadb.

[RKSimon]

llvm/utils/TableGen/SubtargetEmitter.cpp

1166

!size ?

[fpetrogalli]

Fix typos. [NFC]

[fhahn]

This patch is causing multiple warnings when building with assertions.

[3147/3173] Building CXX object unittests/tools/llvm-exegesis/CMakeFiles/LLVMExegesisTests.dir/X86/SchedClassResolutionTest.cpp.o
...//llvm-project/llvm/unittests/tools/llvm-exegesis/X86/SchedClassResolutionTest.cpp:68:70: warning: missing field 'StartAtCycle' initializer [-Wmissing-field-initializers]
      computeIdealizedProcResPressure(STI.getSchedModel(), {{P0Idx, 2}});

It would be great if you could take a look. If it takes longer to fix, please revert the commit in the meantime.

[fpetrogalli]

In D150310#4341950, @fhahn wrote:

This patch is causing multiple warnings when building with assertions.

[3147/3173] Building CXX object unittests/tools/llvm-exegesis/CMakeFiles/LLVMExegesisTests.dir/X86/SchedClassResolutionTest.cpp.o
...//llvm-project/llvm/unittests/tools/llvm-exegesis/X86/SchedClassResolutionTest.cpp:68:70: warning: missing field 'StartAtCycle' initializer [-Wmissing-field-initializers]
      computeIdealizedProcResPressure(STI.getSchedModel(), {{P0Idx, 2}});

It would be great if you could take a look. If it takes longer to fix, please revert the commit in the meantime.

Thank you for the heads up @fhahn - I have created a fix at https://reviews.llvm.org/D150569

Francesco

[fhahn]

llvm/include/llvm/MC/MCSchedule.h

66

This should use /// for doxygen comment?

[michaelmaitland]

llvm/utils/TableGen/SubtargetEmitter.cpp

1198

Do we need this check?

I am trying to model the following case:

I have two resources, ResA and ResB. I'd like it to be the case that ResA models the first of a two stage resource where each stage takes one cycle. When the first stage is not being used, another instruction can enter into the first stage. We can model this by letting ResA represent the first stage, and setting ResourceCycles=1 for ResA and Latency=2+LatencyFromResB (The 2 represents 1 cycle from the first stage and 1 cycle from the second stage).

I'd like to model that ResB is used for one cycle, only after both stages of the resource have finished. In other words, this is two cycles from the start of issuing the instruction. Using StartAtCycles I write something like this:

let ResourceCycles = [1, 1], StartAtCycles =[0, 2] in
  WriteRes<ResourceName, [ResA, ResB]>;

Here, I run into this FatalError. Am I misunderstanding the semantics of StartAtCycle? Is there a better way to accomplish what I'm after?

[michaelmaitland]

llvm/utils/TableGen/SubtargetEmitter.cpp

1198

When I read the comment I now understand:

/// TODO: consider renaming the field `StartAtCycle` and `Cycles` to
/// `AcquireAtCycle` and `ReleaseAtCycle` respectively, to stress the
/// fact that resource allocation is now represented as an interval,
/// relatively to the issue cycle of the instruction.

Maybe it would be a good idea to make this change as it is much easier to understand whats going on when we use this naming. I will prepare a patch.

[fpetrogalli]

llvm/utils/TableGen/SubtargetEmitter.cpp

1198

@michaelmaitland - thank you for addressing the TODO in https://reviews.llvm.org/D158568

llvm/include/llvm/MC/MCSchedule.h

struct MCProcResourceDesc {
 
   bool operator==(const MCProcResourceDesc &Other) const {
     return NumUnits == Other.NumUnits && SuperIdx == Other.SuperIdx
       && BufferSize == Other.BufferSize;
   }
 };
 
 /// Identify one of the processor resource kinds consumed by a particular
 /// scheduling class for the specified number of cycles.
 struct MCWriteProcResEntry {
   uint16_t ProcResourceIdx;
   uint16_t Cycles;
+  // Cycle at which the resource will be grabbed by an instruction,
+  // relatively to the cycle in which the instruction is issued
+  // (assuming no stalls inbetween).
+  uint16_t StartAtCycle;
 
   bool operator==(const MCWriteProcResEntry &Other) const {
-    return ProcResourceIdx == Other.ProcResourceIdx && Cycles == Other.Cycles;
+    return ProcResourceIdx == Other.ProcResourceIdx && Cycles == Other.Cycles &&
+           StartAtCycle == Other.StartAtCycle;
   }
 };
 
 /// Specify the latency in cpu cycles for a particular scheduling class and def
 /// index. -1 indicates an invalid latency. Heuristics would typically consider
 /// an instruction with invalid latency to have infinite latency.  Also identify
 /// the WriteResources of this def. When the operand expands to a sequence of
 /// writes, this ID is the last write in the sequence.

llvm/include/llvm/Target/TargetSchedule.td

 }
 
 // Define values common to WriteRes and SchedWriteRes.
 //
 // SchedModel ties these resources to a processor.
 class ProcWriteResources<list<ProcResourceKind> resources> {
   list<ProcResourceKind> ProcResources = resources;
   list<int> ResourceCycles = [];
+  list<int> StartAtCycles = [];
   int Latency = 1;
   int NumMicroOps = 1;
   bit BeginGroup = false;
   bit EndGroup = false;
   // Allow a processor to mark some scheduling classes as unsupported
   // for stronger verification.
   bit Unsupported = false;
   // Allow a processor to mark some scheduling classes as single-issue.

llvm/test/TableGen/StartAtCycle.td

+// RUN: llvm-tblgen -gen-subtarget -DCORRECT -I %p/../../include %s 2>&1 | \
+// RUN:   FileCheck %s  --check-prefix=CORRECT
+
+// RUN: not llvm-tblgen -gen-subtarget -DWRONG_SIZE -I %p/../../include %s 2>&1 | \
+// RUN:   FileCheck %s --check-prefix=WRONG_SIZE
+
+// RUN: not llvm-tblgen -gen-subtarget -DWRONG_VALUE -I %p/../../include %s 2>&1 | \
+// RUN:   FileCheck %s --check-prefix=WRONG_VALUE
+
+// RUN: not llvm-tblgen -gen-subtarget -DNEGATIVE_INVALID -I %p/../../include %s 2>&1 | \
+// RUN:   FileCheck %s --check-prefix=NEGATIVE_INVALID
+
+// Make sure that StartAtCycle in WriteRes is used to generate the
+// correct data.
+
+include "llvm/Target/Target.td"
+
+def MyTarget : Target;
+
+let BufferSize = 0 in {
+def ResX0 : ProcResource<1>; // X0
+def ResX1 : ProcResource<1>; // X1
+def ResX2 : ProcResource<1>; // X2
+}
+
+let OutOperandList = (outs), InOperandList = (ins) in {
+  def Inst_A : Instruction;
+  def Inst_B : Instruction;
+}
+
+let CompleteModel = 0 in {
+  def SchedModel_A: SchedMachineModel;
+}
+
+def WriteInst_A : SchedWrite;
+def WriteInst_B : SchedWrite;
+
+let SchedModel = SchedModel_A in {
+// Check the generated data when there are no semantic issues.
+#ifdef CORRECT
+// CORRECT-LABEL: llvm::MCWriteProcResEntry MyTargetWriteProcResTable[] = {
+// CORRECT-NEXT: { 0, 0, 0 }, // Invalid
+def : WriteRes<WriteInst_A, [ResX0, ResX1, ResX2]> {
+// CORRECT-NEXT: { 1, 2, 0}, // #1
+// CORRECT-NEXT: { 2, 4, 1}, // #2
+// CORRECT-NEXT: { 3, 3, 2}, // #3
+    let ResourceCycles = [2, 4, 3];
+    let StartAtCycles = [0, 1, 2];
+}
+def : WriteRes<WriteInst_B, [ResX2]> {
+// If unspecified, StartAtCycle is set to 0.
+// CORRECT-NEXT: { 3, 1, 0} // #4
+    let ResourceCycles = [1];
+}
+#endif // CORRECT
+
+#ifdef WRONG_SIZE
+// WRONG_SIZE: StartAtCycle.td:[[@LINE+1]]:1: error: Inconsistent resource cycles: size(StartAtCycles) != size(ProcResources): 2 vs 3
+def : WriteRes<WriteInst_A, [ResX0, ResX1, ResX2]> {
+    let ResourceCycles = [2, 4, 3];
+    let StartAtCycles = [0, 1];
+}
+#endif
+
+#ifdef WRONG_VALUE
+// WRONG_VALUE: StartAtCycle.td:[[@LINE+1]]:1: error: Inconsistent resource cycles: StartAtCycles < Cycles must hold
+def : WriteRes<WriteInst_A, [ResX0, ResX1, ResX2]> {
+    let ResourceCycles = [2, 4, 3];
+    let StartAtCycles = [0, 1, 8];
+}
+#endif
+
+#ifdef NEGATIVE_INVALID
+// NEGATIVE_INVALID: StartAtCycle.td:[[@LINE+1]]:1: error: Invalid value: StartAtCycle must be a non-negative value.
+def : WriteRes<WriteInst_A, [ResX0]> {
+    let ResourceCycles = [2];
+    let StartAtCycles = [-1];
+}
+#endif
+
+def : InstRW<[WriteInst_A], (instrs Inst_A)>;
+def : InstRW<[WriteInst_B], (instrs Inst_B)>;
+}
+
+def ProcessorA: ProcessorModel<"ProcessorA", SchedModel_A, []>;
+

llvm/tools/llvm-exegesis/lib/SchedClassResolution.cpp

sort(ResourceMaskAndEntries,
          return A.first < B.first;
        });
 
   SmallVector<float, 32> ProcResUnitUsage(NumProcRes);
   for (const ResourceMaskAndEntry &Entry : ResourceMaskAndEntries) {
     const MCWriteProcResEntry *WPR = Entry.second;
     const MCProcResourceDesc *const ProcResDesc =
         SM.getProcResource(WPR->ProcResourceIdx);
+    // TODO: Handle StartAtCycle in llvm-exegesis and llvm-mca. See
+    // https://github.com/llvm/llvm-project/issues/62680 and
+    // https://github.com/llvm/llvm-project/issues/62681
+    assert(WPR->StartAtCycle == 0 &&
+           "`llvm-exegesis` does not handle StartAtCycle > 0");
     if (ProcResDesc->SubUnitsIdxBegin == nullptr) {
       // This is a ProcResUnit.
-      Result.push_back({WPR->ProcResourceIdx, WPR->Cycles});
+      Result.push_back({WPR->ProcResourceIdx, WPR->Cycles, WPR->StartAtCycle});
       ProcResUnitUsage[WPR->ProcResourceIdx] += WPR->Cycles;
     } else {
       // This is a ProcResGroup. First see if it contributes any cycles or if
       // it has cycles just from subunits.
       float RemainingCycles = WPR->Cycles;
       for (const auto *SubResIdx = ProcResDesc->SubUnitsIdxBegin;
            SubResIdx != ProcResDesc->SubUnitsIdxBegin + ProcResDesc->NumUnits;
            ++SubResIdx) {
         RemainingCycles -= ProcResUnitUsage[*SubResIdx];
       }
       if (RemainingCycles < 0.01f) {
         // The ProcResGroup contributes no cycles of its own.
         continue;
       }
       // The ProcResGroup contributes `RemainingCycles` cycles of its own.
       Result.push_back({WPR->ProcResourceIdx,
-                        static_cast<uint16_t>(std::round(RemainingCycles))});
+                        static_cast<uint16_t>(std::round(RemainingCycles)),
+                        WPR->StartAtCycle});
       // Spread the remaining cycles over all subunits.
       for (const auto *SubResIdx = ProcResDesc->SubUnitsIdxBegin;
            SubResIdx != ProcResDesc->SubUnitsIdxBegin + ProcResDesc->NumUnits;
            ++SubResIdx) {
         ProcResUnitUsage[*SubResIdx] += RemainingCycles / ProcResDesc->NumUnits;
       }
     }
   }

llvm/utils/TableGen/SubtargetEmitter.cpp

void EmitProcessorResourceSubUnits(const CodeGenProcModel &ProcModel,
                                      raw_ostream &OS);
   void EmitProcessorResources(const CodeGenProcModel &ProcModel,
                               raw_ostream &OS);
   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 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);
Record *SubtargetEmitter::FindReadAdvance(const CodeGenSchedRW &SchedRead,
   }
   return ResDef;
 }
 
 // Expand an explicit list of processor resources into a full list of implied
 // resource groups and super resources that cover them.
 void SubtargetEmitter::ExpandProcResources(RecVec &PRVec,
                                            std::vector<int64_t> &Cycles,
+                                           std::vector<int64_t> &StartAtCycles,
                                            const CodeGenProcModel &PM) {
   assert(PRVec.size() == Cycles.size() && "failed precondition");
   for (unsigned i = 0, e = PRVec.size(); i != e; ++i) {
     Record *PRDef = PRVec[i];
     RecVec SubResources;
     if (PRDef->isSubClassOf("ProcResGroup"))
       SubResources = PRDef->getValueAsListOfDefs("Resources");
     else {
       SubResources.push_back(PRDef);
       PRDef = SchedModels.findProcResUnits(PRDef, PM, PRDef->getLoc());
       for (Record *SubDef = PRDef;
            SubDef->getValueInit("Super")->isComplete();) {
         if (SubDef->isSubClassOf("ProcResGroup")) {
           // Disallow this for simplicitly.
           PrintFatalError(SubDef->getLoc(), "Processor resource group "
                           " cannot be a super resources.");
         }
         Record *SuperDef =
             SchedModels.findProcResUnits(SubDef->getValueAsDef("Super"), PM,
                                          SubDef->getLoc());
         PRVec.push_back(SuperDef);
         Cycles.push_back(Cycles[i]);
+        StartAtCycles.push_back(StartAtCycles[i]);
         SubDef = SuperDef;
       }
     }
     for (Record *PR : PM.ProcResourceDefs) {
       if (PR == PRDef || !PR->isSubClassOf("ProcResGroup"))
         continue;
       RecVec SuperResources = PR->getValueAsListOfDefs("Resources");
       RecIter SubI = SubResources.begin(), SubE = SubResources.end();
       for( ; SubI != SubE; ++SubI) {
         if (!is_contained(SuperResources, *SubI)) {
           break;
         }
       }
       if (SubI == SubE) {
         PRVec.push_back(PR);
         Cycles.push_back(Cycles[i]);
+        StartAtCycles.push_back(StartAtCycles[i]);
       }
     }
   }
 }
 
 // Generate the SchedClass table for this processor and update global
 // tables. Must be called for each processor in order.
 void SubtargetEmitter::GenSchedClassTables(const CodeGenProcModel &ProcModel,
for (unsigned W : Writes) {
         SCDesc.EndGroup |= WriteRes->getValueAsBit("SingleIssue");
         SCDesc.RetireOOO |= WriteRes->getValueAsBit("RetireOOO");
 
         // Create an entry for each ProcResource listed in WriteRes.
         RecVec PRVec = WriteRes->getValueAsListOfDefs("ProcResources");
         std::vector<int64_t> Cycles =
           WriteRes->getValueAsListOfInts("ResourceCycles");
 
-        if (Cycles.empty()) {
-          // If ResourceCycles is not provided, default to one cycle per
-          // resource.
-          Cycles.resize(PRVec.size(), 1);
-        } else if (Cycles.size() != PRVec.size()) {
+        std::vector<int64_t> StartAtCycles =
+            WriteRes->getValueAsListOfInts("StartAtCycles");
+
+        // Check consistency of the two vectors carrying the start and
+        // stop cycles of the resources.
+        if (!Cycles.empty() && Cycles.size() != PRVec.size()) {
           // If ResourceCycles is provided, check consistency.
           PrintFatalError(
               WriteRes->getLoc(),
-              Twine("Inconsistent resource cycles: !size(ResourceCycles) != "
-                    "!size(ProcResources): ")
+              Twine("Inconsistent resource cycles: size(ResourceCycles) != "
+                    "size(ProcResources): ")
                   .concat(Twine(PRVec.size()))
                   .concat(" vs ")
                   .concat(Twine(Cycles.size())));
         }
 
-        ExpandProcResources(PRVec, Cycles, ProcModel);
+        if (!StartAtCycles.empty() && StartAtCycles.size() != PRVec.size()) {
+          PrintFatalError(
+              WriteRes->getLoc(),
+              Twine("Inconsistent resource cycles: size(StartAtCycles) != "
+                    "size(ProcResources): ")
+                  .concat(Twine(StartAtCycles.size()))
+                  .concat(" vs ")
+                  .concat(Twine(PRVec.size())));
+        }
+
+        if (Cycles.empty()) {
+          // If ResourceCycles is not provided, default to one cycle
+          // per resource.
+          Cycles.resize(PRVec.size(), 1);
+        }
+
+        if (StartAtCycles.empty()) {
+          // If StartAtCycles is not provided, reserve the resource
+          // starting from cycle 0.
+          StartAtCycles.resize(PRVec.size(), 0);
+        }
+
+        assert(StartAtCycles.size() == Cycles.size());
+
+        ExpandProcResources(PRVec, Cycles, StartAtCycles, ProcModel);
+        assert(StartAtCycles.size() == Cycles.size());
 
         for (unsigned PRIdx = 0, PREnd = PRVec.size();
              PRIdx != PREnd; ++PRIdx) {
           MCWriteProcResEntry WPREntry;
           WPREntry.ProcResourceIdx = ProcModel.getProcResourceIdx(PRVec[PRIdx]);
           assert(WPREntry.ProcResourceIdx && "Bad ProcResourceIdx");
           WPREntry.Cycles = Cycles[PRIdx];
+          WPREntry.StartAtCycle = StartAtCycles[PRIdx];
+          if (StartAtCycles[PRIdx] > Cycles[PRIdx]) {
+            PrintFatalError(WriteRes->getLoc(),
+                            Twine("Inconsistent resource cycles: StartAtCycles "
+                                  "< Cycles must hold."));
+          }
+          if (StartAtCycles[PRIdx] < 0) {
+            PrintFatalError(WriteRes->getLoc(),
+                            Twine("Invalid value: StartAtCycle "
+                                  "must be a non-negative value."));
+          }
           // If this resource is already used in this sequence, add the current
           // entry's cycles so that the same resource appears to be used
           // serially, rather than multiple parallel uses. This is important for
           // in-order machine where the resource consumption is a hazard.
           unsigned WPRIdx = 0, WPREnd = WriteProcResources.size();
           for( ; WPRIdx != WPREnd; ++WPRIdx) {
             if (WriteProcResources[WPRIdx].ProcResourceIdx
                 == WPREntry.ProcResourceIdx) {
+              // TODO: multiple use of the same resources would
+              // require either 1. thinking of how to handle multiple
+              // intervals for the same resource in
+              // `<Target>WriteProcResTable` (see
+              // `SubtargetEmitter::EmitSchedClassTables`), or
+              // 2. thinking how to merge multiple intervals into a
+              // single interval.
+              assert(WPREntry.StartAtCycle == 0 &&
+                     "multiple use ofthe same resource is not yet handled");
               WriteProcResources[WPRIdx].Cycles += WPREntry.Cycles;
               break;
             }
           }
           if (WPRIdx == WPREnd)
             WriteProcResources.push_back(WPREntry);
         }
       }
else {
       llvm::append_range(SchedTables.ReadAdvanceEntries, ReadAdvanceEntries);
     }
   }
 }
 
 // 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}\n"
-     << "extern const llvm::MCWriteProcResEntry "
-     << Target << "WriteProcResTable[] = {\n"
-     << "  { 0,  0}, // Invalid\n";
+  OS << "\n// {ProcResourceIdx, Cycles, StartAtCycle}\n"
+     << "extern const llvm::MCWriteProcResEntry " << Target
+     << "WriteProcResTable[] = {\n"
+     << "  { 0,  0,  0 }, // Invalid\n";
   for (unsigned WPRIdx = 1, WPREnd = SchedTables.WriteProcResources.size();
        WPRIdx != WPREnd; ++WPRIdx) {
     MCWriteProcResEntry &WPREntry = SchedTables.WriteProcResources[WPRIdx];
     OS << "  {" << format("%2d", WPREntry.ProcResourceIdx) << ", "
-       << format("%2d", WPREntry.Cycles) << "}";
+       << format("%2d", WPREntry.Cycles) << ",  "
+       << format("%2d", WPREntry.StartAtCycle) << "}";
     if (WPRIdx + 1 < WPREnd)
       OS << ',';
     OS << " // #" << WPRIdx << '\n';
   }
   OS << "}; // " << Target << "WriteProcResTable\n";
 
   // Emit global WriteLatencyTable.
   OS << "\n// {Cycles, WriteResourceID}\n"