llvm/lib/MCA/HardwareUnits/LSUnit.cpp

   1 //===----------------------- LSUnit.cpp --------------------------*- C++-*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 /// \file
   9 ///
  10 /// A Load-Store Unit for the llvm-mca tool.
  11 ///
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/MCA/HardwareUnits/LSUnit.h"
  15 #include "llvm/MCA/Instruction.h"
  16 #include "llvm/Support/Debug.h"
  17 #include "llvm/Support/raw_ostream.h"
  18
  19 #define DEBUG_TYPE "llvm-mca"
  20
  21 namespace llvm {
  22 namespace mca {
  23
  24 LSUnitBase::LSUnitBase(const MCSchedModel &SM, unsigned LQ, unsigned SQ,
  25                        bool AssumeNoAlias)
  26     : LQSize(LQ), SQSize(SQ), UsedLQEntries(0), UsedSQEntries(0),
  27       NoAlias(AssumeNoAlias) {
  28   if (SM.hasExtraProcessorInfo()) {
  29     const MCExtraProcessorInfo &EPI = SM.getExtraProcessorInfo();
  30     if (!LQSize && EPI.LoadQueueID) {
  31       const MCProcResourceDesc &LdQDesc = *SM.getProcResource(EPI.LoadQueueID);
  32       LQSize = std::max(0, LdQDesc.BufferSize);
  33     }
  34
  35     if (!SQSize && EPI.StoreQueueID) {
  36       const MCProcResourceDesc &StQDesc = *SM.getProcResource(EPI.StoreQueueID);
  37       SQSize = std::max(0, StQDesc.BufferSize);
  38     }
  39   }
  40 }
  41
  42 LSUnitBase::~LSUnitBase() = default;
  43
  44 void LSUnit::cycleEvent() {
  45   for (const std::pair<unsigned, std::unique_ptr<MemoryGroup>> &G : Groups)
  46     G.second->cycleEvent();
  47 }
  48
  49 #ifndef NDEBUG
  50 void LSUnit::dump() const {
  51   dbgs() << "[LSUnit] LQ_Size = " << getLoadQueueSize() << '\n';
  52   dbgs() << "[LSUnit] SQ_Size = " << getStoreQueueSize() << '\n';
  53   dbgs() << "[LSUnit] NextLQSlotIdx = " << getUsedLQEntries() << '\n';
  54   dbgs() << "[LSUnit] NextSQSlotIdx = " << getUsedSQEntries() << '\n';
  55   dbgs() << "\n";
  56   for (const auto &GroupIt : Groups) {
  57     const MemoryGroup &Group = *GroupIt.second;
  58     dbgs() << "[LSUnit] Group (" << GroupIt.first << "): "
  59            << "[ #Preds = " << Group.getNumPredecessors()
  60            << ", #GIssued = " << Group.getNumExecutingPredecessors()
  61            << ", #GExecuted = " << Group.getNumExecutedPredecessors()
  62            << ", #Inst = " << Group.getNumInstructions()
  63            << ", #IIssued = " << Group.getNumExecuting()
  64            << ", #IExecuted = " << Group.getNumExecuted() << '\n';
  65   }
  66 }
  67 #endif
  68
  69 unsigned LSUnit::dispatch(const InstRef &IR) {
  70   const Instruction &IS = *IR.getInstruction();
  71   bool IsStoreBarrier = IS.isAStoreBarrier();
  72   bool IsLoadBarrier = IS.isALoadBarrier();
  73   assert((IS.getMayLoad() || IS.getMayStore()) && "Not a memory operation!");
  74
  75   if (IS.getMayLoad())
  76     acquireLQSlot();
  77   if (IS.getMayStore())
  78     acquireSQSlot();
  79
  80   if (IS.getMayStore()) {
  81     unsigned NewGID = createMemoryGroup();
  82     MemoryGroup &NewGroup = getGroup(NewGID);
  83     NewGroup.addInstruction();
  84
  85     // A store may not pass a previous load or load barrier.
  86     unsigned ImmediateLoadDominator =
  87         std::max(CurrentLoadGroupID, CurrentLoadBarrierGroupID);
  88     if (ImmediateLoadDominator) {
  89       MemoryGroup &IDom = getGroup(ImmediateLoadDominator);
  90       LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << ImmediateLoadDominator
  91                         << ") --> (" << NewGID << ")\n");
  92       IDom.addSuccessor(&NewGroup, !assumeNoAlias());
  93     }
  94
  95     // A store may not pass a previous store barrier.
  96     if (CurrentStoreBarrierGroupID) {
  97       MemoryGroup &StoreGroup = getGroup(CurrentStoreBarrierGroupID);
  98       LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: ("
  99                         << CurrentStoreBarrierGroupID << ") --> (" << NewGID
 100                         << ")\n");
 101       StoreGroup.addSuccessor(&NewGroup, true);
 102     }
 103
 104     // A store may not pass a previous store.
 105     if (CurrentStoreGroupID &&
 106         (CurrentStoreGroupID != CurrentStoreBarrierGroupID)) {
 107       MemoryGroup &StoreGroup = getGroup(CurrentStoreGroupID);
 108       LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << CurrentStoreGroupID
 109                         << ") --> (" << NewGID << ")\n");
 110       StoreGroup.addSuccessor(&NewGroup, !assumeNoAlias());
 111     }
 112
 113     CurrentStoreGroupID = NewGID;
 114     if (IsStoreBarrier)
 115       CurrentStoreBarrierGroupID = NewGID;
 116
 117     if (IS.getMayLoad()) {
 118       CurrentLoadGroupID = NewGID;
 119       if (IsLoadBarrier)
 120         CurrentLoadBarrierGroupID = NewGID;
 121     }
 122
 123     return NewGID;
 124   }
 125
 126   assert(IS.getMayLoad() && "Expected a load!");
 127
 128   unsigned ImmediateLoadDominator =
 129       std::max(CurrentLoadGroupID, CurrentLoadBarrierGroupID);
 130
 131   // A new load group is created if we are in one of the following situations:
 132   // 1) This is a load barrier (by construction, a load barrier is always
 133   //    assigned to a different memory group).
 134   // 2) There is no load in flight (by construction we always keep loads and
 135   //    stores into separate memory groups).
 136   // 3) There is a load barrier in flight. This load depends on it.
 137   // 4) There is an intervening store between the last load dispatched to the
 138   //    LSU and this load. We always create a new group even if this load
 139   //    does not alias the last dispatched store.
 140   // 5) There is no intervening store and there is an active load group.
 141   //    However that group has already started execution, so we cannot add
 142   //    this load to it.
 143   bool ShouldCreateANewGroup =
 144       IsLoadBarrier || !ImmediateLoadDominator ||
 145       CurrentLoadBarrierGroupID == ImmediateLoadDominator ||
 146       ImmediateLoadDominator <= CurrentStoreGroupID ||
 147       getGroup(ImmediateLoadDominator).isExecuting();
 148
 149   if (ShouldCreateANewGroup) {
 150     unsigned NewGID = createMemoryGroup();
 151     MemoryGroup &NewGroup = getGroup(NewGID);
 152     NewGroup.addInstruction();
 153
 154     // A load may not pass a previous store or store barrier
 155     // unless flag 'NoAlias' is set.
 156     if (!assumeNoAlias() && CurrentStoreGroupID) {
 157       MemoryGroup &StoreGroup = getGroup(CurrentStoreGroupID);
 158       LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << CurrentStoreGroupID
 159                         << ") --> (" << NewGID << ")\n");
 160       StoreGroup.addSuccessor(&NewGroup, true);
 161     }
 162
 163     // A load barrier may not pass a previous load or load barrier.
 164     if (IsLoadBarrier) {
 165       if (ImmediateLoadDominator) {
 166         MemoryGroup &LoadGroup = getGroup(ImmediateLoadDominator);
 167         LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << ImmediateLoadDominator
 168                           << ") --> (" << NewGID << ")\n");
 169         LoadGroup.addSuccessor(&NewGroup, true);
 170       }
 171     } else {
 172       // A younger load cannot pass a older load barrier.
 173       if (CurrentLoadBarrierGroupID) {
 174         MemoryGroup &LoadGroup = getGroup(CurrentLoadBarrierGroupID);
 175         LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: ("
 176                           << CurrentLoadBarrierGroupID << ") --> (" << NewGID
 177                           << ")\n");
 178         LoadGroup.addSuccessor(&NewGroup, true);
 179       }
 180     }
 181
 182     CurrentLoadGroupID = NewGID;
 183     if (IsLoadBarrier)
 184       CurrentLoadBarrierGroupID = NewGID;
 185     return NewGID;
 186   }
 187
 188   // A load may pass a previous load.
 189   MemoryGroup &Group = getGroup(CurrentLoadGroupID);
 190   Group.addInstruction();
 191   return CurrentLoadGroupID;
 192 }
 193
 194 LSUnit::Status LSUnit::isAvailable(const InstRef &IR) const {
 195   const Instruction &IS = *IR.getInstruction();
 196   if (IS.getMayLoad() && isLQFull())
 197     return LSUnit::LSU_LQUEUE_FULL;
 198   if (IS.getMayStore() && isSQFull())
 199     return LSUnit::LSU_SQUEUE_FULL;
 200   return LSUnit::LSU_AVAILABLE;
 201 }
 202
 203 void LSUnit::onInstructionRetired(const InstRef &IR) {
 204   const Instruction &IS = *IR.getInstruction();
 205   bool IsALoad = IS.getMayLoad();
 206   bool IsAStore = IS.getMayStore();
 207   assert((IsALoad || IsAStore) && "Expected a memory operation!");
 208
 209   if (IsALoad) {
 210     releaseLQSlot();
 211     LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << IR.getSourceIndex()
 212                       << " has been removed from the load queue.\n");
 213   }
 214
 215   if (IsAStore) {
 216     releaseSQSlot();
 217     LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << IR.getSourceIndex()
 218                       << " has been removed from the store queue.\n");
 219   }
 220 }
 221
 222 void LSUnit::onInstructionExecuted(const InstRef &IR) {
 223   const Instruction &IS = *IR.getInstruction();
 224   if (!IS.isMemOp())
 225     return;
 226
 227   unsigned GroupID = IS.getLSUTokenID();
 228   auto It = Groups.find(GroupID);
 229   assert(It != Groups.end() && "Instruction not dispatched to the LS unit");
 230   It->second->onInstructionExecuted(IR);
 231   if (It->second->isExecuted())
 232     Groups.erase(It);
 233
 234   if (!isValidGroupID(GroupID)) {
 235     if (GroupID == CurrentLoadGroupID)
 236       CurrentLoadGroupID = 0;
 237     if (GroupID == CurrentStoreGroupID)
 238       CurrentStoreGroupID = 0;
 239     if (GroupID == CurrentLoadBarrierGroupID)
 240       CurrentLoadBarrierGroupID = 0;
 241     if (GroupID == CurrentStoreBarrierGroupID)
 242       CurrentStoreBarrierGroupID = 0;
 243   }
 244 }
 245
 246 } // namespace mca
 247 } // namespace llvm