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), NextGroupID(1) {
  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() {}
  43
  44 void LSUnitBase::cycleEvent() {
  45   for (const std::pair<unsigned, std::unique_ptr<MemoryGroup>> &G : Groups)
  46     G.second->cycleEvent();
  47 }
  48
  49 #ifndef NDEBUG
  50 void LSUnitBase::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 InstrDesc &Desc = IR.getInstruction()->getDesc();
  71   unsigned IsMemBarrier = Desc.HasSideEffects;
  72   assert((Desc.MayLoad || Desc.MayStore) && "Not a memory operation!");
  73
  74   if (Desc.MayLoad)
  75     acquireLQSlot();
  76   if (Desc.MayStore)
  77     acquireSQSlot();
  78
  79   if (Desc.MayStore) {
  80     unsigned NewGID = createMemoryGroup();
  81     MemoryGroup &NewGroup = getGroup(NewGID);
  82     NewGroup.addInstruction();
  83
  84     // A store may not pass a previous load or load barrier.
  85     unsigned ImmediateLoadDominator =
  86         std::max(CurrentLoadGroupID, CurrentLoadBarrierGroupID);
  87     if (ImmediateLoadDominator) {
  88       MemoryGroup &IDom = getGroup(ImmediateLoadDominator);
  89       LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << ImmediateLoadDominator
  90                         << ") --> (" << NewGID << ")\n");
  91       IDom.addSuccessor(&NewGroup, !assumeNoAlias());
  92     }
  93
  94     // A store may not pass a previous store barrier.
  95     if (CurrentStoreBarrierGroupID) {
  96       MemoryGroup &StoreGroup = getGroup(CurrentStoreBarrierGroupID);
  97       LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: ("
  98                         << CurrentStoreBarrierGroupID
  99                         << ") --> (" << NewGID << ")\n");
 100       StoreGroup.addSuccessor(&NewGroup, true);
 101     }
 102
 103     // A store may not pass a previous store.
 104     if (CurrentStoreGroupID &&
 105         (CurrentStoreGroupID != CurrentStoreBarrierGroupID)) {
 106       MemoryGroup &StoreGroup = getGroup(CurrentStoreGroupID);
 107       LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << CurrentStoreGroupID
 108                         << ") --> (" << NewGID << ")\n");
 109       StoreGroup.addSuccessor(&NewGroup, !assumeNoAlias());
 110     }
 111
 112
 113     CurrentStoreGroupID = NewGID;
 114     if (IsMemBarrier)
 115       CurrentStoreBarrierGroupID = NewGID;
 116
 117     if (Desc.MayLoad) {
 118       CurrentLoadGroupID = NewGID;
 119       if (IsMemBarrier)
 120         CurrentLoadBarrierGroupID = NewGID;
 121     }
 122
 123     return NewGID;
 124   }
 125
 126   assert(Desc.MayLoad && "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       IsMemBarrier || !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 (IsMemBarrier) {
 165       if (ImmediateLoadDominator) {
 166         MemoryGroup &LoadGroup = getGroup(ImmediateLoadDominator);
 167         LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: ("
 168                           << ImmediateLoadDominator
 169                           << ") --> (" << NewGID << ")\n");
 170         LoadGroup.addSuccessor(&NewGroup, true);
 171       }
 172     } else {
 173       // A younger load cannot pass a older load barrier.
 174       if (CurrentLoadBarrierGroupID) {
 175         MemoryGroup &LoadGroup = getGroup(CurrentLoadBarrierGroupID);
 176         LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: ("
 177                           << CurrentLoadBarrierGroupID
 178                           << ") --> (" << NewGID << ")\n");
 179         LoadGroup.addSuccessor(&NewGroup, true);
 180       }
 181     }
 182
 183     CurrentLoadGroupID = NewGID;
 184     if (IsMemBarrier)
 185       CurrentLoadBarrierGroupID = NewGID;
 186     return NewGID;
 187   }
 188
 189   // A load may pass a previous load.
 190   MemoryGroup &Group = getGroup(CurrentLoadGroupID);
 191   Group.addInstruction();
 192   return CurrentLoadGroupID;
 193 }
 194
 195 LSUnit::Status LSUnit::isAvailable(const InstRef &IR) const {
 196   const InstrDesc &Desc = IR.getInstruction()->getDesc();
 197   if (Desc.MayLoad && isLQFull())
 198     return LSUnit::LSU_LQUEUE_FULL;
 199   if (Desc.MayStore && isSQFull())
 200     return LSUnit::LSU_SQUEUE_FULL;
 201   return LSUnit::LSU_AVAILABLE;
 202 }
 203
 204 void LSUnitBase::onInstructionExecuted(const InstRef &IR) {
 205   unsigned GroupID = IR.getInstruction()->getLSUTokenID();
 206   auto It = Groups.find(GroupID);
 207   assert(It != Groups.end() && "Instruction not dispatched to the LS unit");
 208   It->second->onInstructionExecuted(IR);
 209   if (It->second->isExecuted())
 210     Groups.erase(It);
 211 }
 212
 213 void LSUnitBase::onInstructionRetired(const InstRef &IR) {
 214   const InstrDesc &Desc = IR.getInstruction()->getDesc();
 215   bool IsALoad = Desc.MayLoad;
 216   bool IsAStore = Desc.MayStore;
 217   assert((IsALoad || IsAStore) && "Expected a memory operation!");
 218
 219   if (IsALoad) {
 220     releaseLQSlot();
 221     LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << IR.getSourceIndex()
 222                       << " has been removed from the load queue.\n");
 223   }
 224
 225   if (IsAStore) {
 226     releaseSQSlot();
 227     LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << IR.getSourceIndex()
 228                       << " has been removed from the store queue.\n");
 229   }
 230 }
 231
 232 void LSUnit::onInstructionExecuted(const InstRef &IR) {
 233   const Instruction &IS = *IR.getInstruction();
 234   if (!IS.isMemOp())
 235     return;
 236
 237   LSUnitBase::onInstructionExecuted(IR);
 238   unsigned GroupID = IS.getLSUTokenID();
 239   if (!isValidGroupID(GroupID)) {
 240     if (GroupID == CurrentLoadGroupID)
 241       CurrentLoadGroupID = 0;
 242     if (GroupID == CurrentStoreGroupID)
 243       CurrentStoreGroupID = 0;
 244     if (GroupID == CurrentLoadBarrierGroupID)
 245       CurrentLoadBarrierGroupID = 0;
 246     if (GroupID == CurrentStoreBarrierGroupID)
 247       CurrentStoreBarrierGroupID = 0;
 248   }
 249 }
 250
 251 } // namespace mca
 252 } // namespace llvm