[llvm-exegesis] getNonRedundantWriteProcRes - perform basic toplogical sorting (PR58500)

[RKSimon]

Summary

getNonRedundantWriteProcRes was assuming that tblgen topologically sorted the cpu ModelProcResources[] arrays so that resource units were declared before the resource groups that used them, but unfortunately that doesn't appear to be true - in most cases it was just getting lucky based off the alphanumeric sorting that was being performed and the choice of the resource pipe names in most scheduler models (Intel models in particular).

This patch adds an explicit sort, based off llvm-mca's initializeUsedResources, that sorts by resource mask - I'm not sure whether this sorting is really enough, I don't think overlapping groups or Super resources are a problem, but somebody with more experience with this might be able to advise me....

I'd like to take this further in the future and start sharing more code between llvm-mca and llvm-exegesis - while triaging this bug I saw how similar both approaches are, but are just dissimilar enough that any refactor isn't going to be trivial :(

What is the best way to add test coverage here?

[andreadb]

This patch looks like a good first step towards the goal of sharing more code between mca and exegesis (other than solving the issue with the sorting of resources).

@courbet @gchatelet what do you think?

[RKSimon]

ping - any more comments?

[courbet]

Sorry I missed this.

I have not had that much time to work on this recently, but I agree with sharing more code :)

[courbet]

In terms of tests right now we're using the actual model for x86 tests. I can work on adding an analysis unit test with a fake model.

[RKSimon]

In D136351#3878758, @courbet wrote:

In terms of tests right now we're using the actual model for x86 tests. I can work on adding an analysis unit test with a fake model.

Thank you - both the znver* and alderlake models show this in different ways

llvm/tools/llvm-exegesis/lib/CMakeLists.txt

 
 set(LLVM_LINK_COMPONENTS
   Analysis
   CodeGen
   Core
   ExecutionEngine
   GlobalISel
   MC
+  MCA
   MCDisassembler
   MCJIT
   MCParser
   Object
   ObjectYAML
   RuntimeDyld
   Support
   )

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

 //===-- SchedClassResolution.cpp --------------------------------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "SchedClassResolution.h"
 #include "BenchmarkResult.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MCA/Support.h"
 #include "llvm/Support/FormatVariadic.h"
 #include <limits>
 #include <unordered_set>
 #include <vector>
 
 namespace llvm {
 namespace exegesis {
 

 // Eventually we end up with three entries for the WriteProcRes of the
 // instruction:
 //    {ProcResIdx=1,  Cycles=1}  // P0
 //    {ProcResIdx=7,  Cycles=3}  // P06
 //    {ProcResIdx=10, Cycles=3}  // P016
 //
 // Note that in this case, P016 does not contribute any cycles, so it would
 // be removed by this function.
-// FIXME: Move this to MCSubtargetInfo and use it in llvm-mca.
+// FIXME: Merge this with the equivalent in llvm-mca.
 static SmallVector<MCWriteProcResEntry, 8>
 getNonRedundantWriteProcRes(const MCSchedClassDesc &SCDesc,
                             const MCSubtargetInfo &STI) {
   SmallVector<MCWriteProcResEntry, 8> Result;
   const auto &SM = STI.getSchedModel();
   const unsigned NumProcRes = SM.getNumProcResourceKinds();
 
-  // This assumes that the ProcResDescs are sorted in topological order, which
-  // is guaranteed by the tablegen backend.
-  SmallVector<float, 32> ProcResUnitUsage(NumProcRes);
+  // Collect resource masks.
+  SmallVector<uint64_t> ProcResourceMasks(NumProcRes);
+  mca::computeProcResourceMasks(SM, ProcResourceMasks);
+
+  // Sort entries by smaller resources for (basic) topological ordering.
+  using ResourceMaskAndEntry = std::pair<uint64_t, const MCWriteProcResEntry *>;
+  SmallVector<ResourceMaskAndEntry, 8> ResourceMaskAndEntries;
   for (const auto *WPR = STI.getWriteProcResBegin(&SCDesc),
                   *const WPREnd = STI.getWriteProcResEnd(&SCDesc);
        WPR != WPREnd; ++WPR) {
+    uint64_t Mask = ProcResourceMasks[WPR->ProcResourceIdx];
+    ResourceMaskAndEntries.push_back({Mask, WPR});
+  }
+  sort(ResourceMaskAndEntries,
+       [](const ResourceMaskAndEntry &A, const ResourceMaskAndEntry &B) {
+         unsigned popcntA = countPopulation(A.first);
+         unsigned popcntB = countPopulation(B.first);
+         if (popcntA < popcntB)
+           return true;
+         if (popcntA > popcntB)
+           return false;
+         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);
     if (ProcResDesc->SubUnitsIdxBegin == nullptr) {
       // This is a ProcResUnit.
       Result.push_back({WPR->ProcResourceIdx, WPR->Cycles});
       ProcResUnitUsage[WPR->ProcResourceIdx] += WPR->Cycles;
     } else {
       // This is a ProcResGroup. First see if it contributes any cycles or if