[MCA] Refactor class LSUnit. NFCI

This should be the last bit of refactoring in preparation for a patch that would
finally fix PR37494.

This patch introduces the concept of memory dependency groups (class
MemoryGroup) and "Load/Store Unit token" (LSUToken) to track the status of a
memory operation.

A MemoryGroup is a node of a memory dependency graph. It is used internally to
classify memory operations based on the memory operations they depend on.  Let I
and J be two memory operations, we say that I and J equivalent (for the purpose
of mapping instructions to memory dependency groups) if the set of memory
operations they depend depend on is identical.

MemoryGroups are identified by so-called LSUToken (a unique group identifier
assigned by the LSUnit to every group). When an instruction I is dispatched to
the LSUnit, the LSUnit maps I to a group, and then returns a LSUToken.
LSUTokens are used by class Scheduler to track memory dependencies.

This patch simplifies the LSUnit interface and moves most of the implementation
details to its base class (LSUnitBase). There is no user visible change to the
output.

llvm-svn: 361950

2 files changed, 146 insertions, 182 deletions

diff --git a/llvm/lib/MCA/HardwareUnits/LSUnit.cpp b/llvm/lib/MCA/HardwareUnits/LSUnit.cpp
index c3866d6bba7..ac1a6a36547 100644
--- a/llvm/lib/MCA/HardwareUnits/LSUnit.cpp
+++ b/llvm/lib/MCA/HardwareUnits/LSUnit.cpp
@@ -23,7 +23,8 @@ namespace mca {
 
 LSUnitBase::LSUnitBase(const MCSchedModel &SM, unsigned LQ, unsigned SQ,
                        bool AssumeNoAlias)
-    : LQSize(LQ), SQSize(SQ), NoAlias(AssumeNoAlias) {
+    : LQSize(LQ), SQSize(SQ), UsedLQEntries(0), UsedSQEntries(0),
+      NoAlias(AssumeNoAlias), NextGroupID(1) {
   if (SM.hasExtraProcessorInfo()) {
     const MCExtraProcessorInfo &EPI = SM.getExtraProcessorInfo();
     if (!LQSize && EPI.LoadQueueID) {
@@ -40,47 +41,113 @@ LSUnitBase::LSUnitBase(const MCSchedModel &SM, unsigned LQ, unsigned SQ,
 
 LSUnitBase::~LSUnitBase() {}
 
+void LSUnitBase::cycleEvent() {
+  for (const std::pair<unsigned, std::unique_ptr<MemoryGroup>> &G : Groups)
+    G.second->cycleEvent();
+}
+
 #ifndef NDEBUG
-void LSUnit::dump() const {
+void LSUnitBase::dump() const {
   dbgs() << "[LSUnit] LQ_Size = " << getLoadQueueSize() << '\n';
   dbgs() << "[LSUnit] SQ_Size = " << getStoreQueueSize() << '\n';
-  dbgs() << "[LSUnit] NextLQSlotIdx = " << LoadQueue.size() << '\n';
-  dbgs() << "[LSUnit] NextSQSlotIdx = " << StoreQueue.size() << '\n';
+  dbgs() << "[LSUnit] NextLQSlotIdx = " << getUsedLQEntries() << '\n';
+  dbgs() << "[LSUnit] NextSQSlotIdx = " << getUsedSQEntries() << '\n';
+  dbgs() << "\n";
+  for (const auto &GroupIt : Groups) {
+    const MemoryGroup &Group = *GroupIt.second;
+    dbgs() << "[LSUnit] Group (" << GroupIt.first << "): "
+           << "[ #Preds = " << Group.getNumPredecessors()
+           << ", #GIssued = " << Group.getNumExecutingPredecessors()
+           << ", #GExecuted = " << Group.getNumExecutedPredecessors()
+           << ", #Inst = " << Group.getNumInstructions()
+           << ", #IIssued = " << Group.getNumExecuting()
+           << ", #IExecuted = " << Group.getNumExecuted() << '\n';
+  }
 }
 #endif
 
-void LSUnit::assignLQSlot(const InstRef &IR) {
-  assert(!isLQFull() && "Load Queue is full!");
-
-  LLVM_DEBUG(dbgs() << "[LSUnit] - AssignLQSlot <Idx=" << IR.getSourceIndex()
-                    << ",slot=" << LoadQueue.size() << ">\n");
-  LoadQueue.insert(IR);
-}
-
-void LSUnit::assignSQSlot(const InstRef &IR) {
-  assert(!isSQFull() && "Store Queue is full!");
-
-  LLVM_DEBUG(dbgs() << "[LSUnit] - AssignSQSlot <Idx=" << IR.getSourceIndex()
-                    << ",slot=" << StoreQueue.size() << ">\n");
-  StoreQueue.insert(IR);
-}
-
-void LSUnit::dispatch(const InstRef &IR) {
+unsigned LSUnit::dispatch(const InstRef &IR) {
   const InstrDesc &Desc = IR.getInstruction()->getDesc();
   unsigned IsMemBarrier = Desc.HasSideEffects;
   assert((Desc.MayLoad || Desc.MayStore) && "Not a memory operation!");
 
-  if (Desc.MayLoad) {
-    if (IsMemBarrier)
-      LoadBarriers.insert(IR);
-    assignLQSlot(IR);
-  }
+  if (Desc.MayLoad)
+    assignLQSlot();
+  if (Desc.MayStore)
+    assignSQSlot();
 
   if (Desc.MayStore) {
+    // Always create a new group for store operations.
+
+    // A store may not pass a previous store or store barrier.
+    unsigned NewGID = createMemoryGroup();
+    MemoryGroup &NewGroup = getGroup(NewGID);
+    NewGroup.addInstruction();
+
+    // A store may not pass a previous load or load barrier.
+    unsigned ImmediateLoadDominator =
+        std::max(CurrentLoadGroupID, CurrentLoadBarrierGroupID);
+    if (ImmediateLoadDominator) {
+      MemoryGroup &IDom = getGroup(ImmediateLoadDominator);
+      LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << ImmediateLoadDominator
+                        << ") --> (" << NewGID << ")\n");
+      IDom.addSuccessor(&NewGroup);
+    }
+    if (CurrentStoreGroupID) {
+      MemoryGroup &StoreGroup = getGroup(CurrentStoreGroupID);
+      LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << CurrentStoreGroupID
+                        << ") --> (" << NewGID << ")\n");
+      StoreGroup.addSuccessor(&NewGroup);
+    }
+
+    CurrentStoreGroupID = NewGID;
+    if (Desc.MayLoad) {
+      CurrentLoadGroupID = NewGID;
+      if (IsMemBarrier)
+        CurrentLoadBarrierGroupID = NewGID;
+    }
+
+    return NewGID;
+  }
+
+  assert(Desc.MayLoad && "Expected a load!");
+
+  // Always create a new memory group if this is the first load of the sequence.
+
+  // A load may not pass a previous store unless flag 'NoAlias' is set.
+  // A load may pass a previous load.
+  // A younger load cannot pass a older load barrier.
+  // A load barrier cannot pass a older load.
+  bool ShouldCreateANewGroup = !CurrentLoadGroupID || IsMemBarrier ||
+                               CurrentLoadGroupID <= CurrentStoreGroupID ||
+                               CurrentLoadGroupID <= CurrentLoadBarrierGroupID;
+  if (ShouldCreateANewGroup) {
+    unsigned NewGID = createMemoryGroup();
+    MemoryGroup &NewGroup = getGroup(NewGID);
+    NewGroup.addInstruction();
+
+    if (!assumeNoAlias() && CurrentStoreGroupID) {
+      MemoryGroup &StGroup = getGroup(CurrentStoreGroupID);
+      LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << CurrentStoreGroupID
+                        << ") --> (" << NewGID << ")\n");
+      StGroup.addSuccessor(&NewGroup);
+    }
+    if (CurrentLoadBarrierGroupID) {
+      MemoryGroup &LdGroup = getGroup(CurrentLoadBarrierGroupID);
+      LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << CurrentLoadBarrierGroupID
+                        << ") --> (" << NewGID << ")\n");
+      LdGroup.addSuccessor(&NewGroup);
+    }
+
+    CurrentLoadGroupID = NewGID;
     if (IsMemBarrier)
-      StoreBarriers.insert(IR);
-    assignSQSlot(IR);
+      CurrentLoadBarrierGroupID = NewGID;
+    return NewGID;
   }
+
+  MemoryGroup &Group = getGroup(CurrentLoadGroupID);
+  Group.addInstruction();
+  return CurrentLoadGroupID;
 }
 
 LSUnit::Status LSUnit::isAvailable(const InstRef &IR) const {
@@ -92,106 +159,46 @@ LSUnit::Status LSUnit::isAvailable(const InstRef &IR) const {
   return LSUnit::LSU_AVAILABLE;
 }
 
-const InstRef &LSUnit::isReady(const InstRef &IR) const {
+void LSUnitBase::onInstructionExecuted(const InstRef &IR) {
   const InstrDesc &Desc = IR.getInstruction()->getDesc();
-  const unsigned Index = IR.getSourceIndex();
   bool IsALoad = Desc.MayLoad;
   bool IsAStore = Desc.MayStore;
-  assert((IsALoad || IsAStore) && "Not a memory operation!");
-
-  if (IsALoad && !LoadBarriers.empty()) {
-    const InstRef &LoadBarrier = *LoadBarriers.begin();
-    // A younger load cannot pass a older load barrier.
-    if (Index > LoadBarrier.getSourceIndex())
-      return LoadBarrier;
-    // A load barrier cannot pass a older load.
-    if (Index == LoadBarrier.getSourceIndex()) {
-      const InstRef &Load = *LoadQueue.begin();
-      if (Index != Load.getSourceIndex())
-        return Load;
-    }
-  }
+  assert((IsALoad || IsAStore) && "Expected a memory operation!");
 
-  if (IsAStore && !StoreBarriers.empty()) {
-    const InstRef &StoreBarrier = *StoreBarriers.begin();
-    // A younger store cannot pass a older store barrier.
-    if (Index > StoreBarrier.getSourceIndex())
-      return StoreBarrier;
-    // A store barrier cannot pass a older store.
-    if (Index == StoreBarrier.getSourceIndex()) {
-      const InstRef &Store = *StoreQueue.begin();
-      if (Index != Store.getSourceIndex())
-        return Store;
-    }
-  }
-
-  // A load may not pass a previous store unless flag 'NoAlias' is set.
-  // A load may pass a previous load.
-  if (assumeNoAlias() && IsALoad)
-    return IR;
-
-  if (StoreQueue.size()) {
-    // A load may not pass a previous store.
-    // A store may not pass a previous store.
-    const InstRef &Store = *StoreQueue.begin();
-    if (Index > Store.getSourceIndex())
-      return Store;
+  unsigned GroupID = IR.getInstruction()->getLSUTokenID();
+  auto It = Groups.find(GroupID);
+  It->second->onInstructionExecuted();
+  if (It->second->isExecuted()) {
+    Groups.erase(It);
   }
 
-  // Okay, we are older than the oldest store in the queue.
-  if (isLQEmpty())
-    return IR;
-
-  // Check if there are no older loads.
-  const InstRef &Load = *LoadQueue.begin();
-  if (Index <= Load.getSourceIndex())
-    return IR;
-
-  // A load may pass a previous load.
-  if (IsALoad)
-    return IR;
-
-  // A store may not pass a previous load.
-  return Load;
-}
-
-void LSUnit::onInstructionExecuted(const InstRef &IR) {
-  const InstrDesc &Desc = IR.getInstruction()->getDesc();
-  const unsigned Index = IR.getSourceIndex();
-  bool IsALoad = Desc.MayLoad;
-  bool IsAStore = Desc.MayStore;
-
   if (IsALoad) {
-    if (LoadQueue.erase(IR)) {
-      LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << Index
-                        << " has been removed from the load queue.\n");
-    }
-    if (!LoadBarriers.empty()) {
-      const InstRef &LoadBarrier = *LoadBarriers.begin();
-      if (Index == LoadBarrier.getSourceIndex()) {
-        LLVM_DEBUG(
-            dbgs() << "[LSUnit]: Instruction idx=" << Index
-                   << " has been removed from the set of load barriers.\n");
-        LoadBarriers.erase(IR);
-      }
-    }
+    UsedLQEntries--;
+    LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << IR.getSourceIndex()
+                      << " has been removed from the load queue.\n");
   }
 
   if (IsAStore) {
-    if (StoreQueue.erase(IR)) {
-      LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << Index
-                        << " has been removed from the store queue.\n");
-    }
+    UsedSQEntries--;
+    LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << IR.getSourceIndex()
+                      << " has been removed from the store queue.\n");
+  }
+}
 
-    if (!StoreBarriers.empty()) {
-      const InstRef &StoreBarrier = *StoreBarriers.begin();
-      if (Index == StoreBarrier.getSourceIndex()) {
-        LLVM_DEBUG(
-            dbgs() << "[LSUnit]: Instruction idx=" << Index
-                   << " has been removed from the set of store barriers.\n");
-        StoreBarriers.erase(IR);
-      }
-    }
+void LSUnit::onInstructionExecuted(const InstRef &IR) {
+  const Instruction &IS = *IR.getInstruction();
+  if (!IS.isMemOp())
+    return;
+
+  LSUnitBase::onInstructionExecuted(IR);
+  unsigned GroupID = IS.getLSUTokenID();
+  if (!isValidGroupID(GroupID)) {
+    if (GroupID == CurrentLoadGroupID)
+      CurrentLoadGroupID = 0;
+    if (GroupID == CurrentStoreGroupID)
+      CurrentStoreGroupID = 0;
+    if (GroupID == CurrentLoadBarrierGroupID)
+      CurrentLoadBarrierGroupID = 0;
   }
 }
 
diff --git a/llvm/lib/MCA/HardwareUnits/Scheduler.cpp b/llvm/lib/MCA/HardwareUnits/Scheduler.cpp
index 6b3448fbe82..3afc0ac89ef 100644
--- a/llvm/lib/MCA/HardwareUnits/Scheduler.cpp
+++ b/llvm/lib/MCA/HardwareUnits/Scheduler.cpp
@@ -84,6 +84,12 @@ void Scheduler::issueInstructionImpl(
 
   IS->computeCriticalRegDep();
 
+  if (IS->isMemOp()) {
+    LSU.onInstructionIssued(IR);
+    const MemoryGroup &Group = LSU.getGroup(IS->getLSUTokenID());
+    IS->setCriticalMemDep(Group.getCriticalPredecessor());
+  }
+
   if (IS->isExecuting())
     IssuedSet.emplace_back(IR);
   else if (IS->isExecuted())
@@ -115,59 +121,6 @@ void Scheduler::issueInstruction(
     promoteToReadySet(ReadyInstructions);
 }
 
-static bool initializeCriticalMemDepInfo(InstRef &IR, const LSUnit &LSU) {
-  Instruction &IS = *IR.getInstruction();
-  assert(IS.isMemOp() && "Not a memory operation!");
-
-  // Check if this instruction depends on another memory operation.
-  InstRef DependentMemOp = LSU.isReady(IR);
-  const Instruction *MemOp = DependentMemOp.getInstruction();
-  IS.setCurrentMemDep(MemOp);
-
-  // Initialize the CriticalMemDep structure.
-  unsigned Cycles = 0;
-  if (MemOp->isExecuting())
-    Cycles = static_cast<unsigned>(MemOp->getCyclesLeft());
-  IS.setCriticalMemDep(DependentMemOp.getSourceIndex(), Cycles);
-  return IR.getSourceIndex() == DependentMemOp.getSourceIndex();
-}
-
-static bool updateMemoryDependencyInfo(InstRef &IR, const LSUnit &LSU) {
-  Instruction &IS = *IR.getInstruction();
-  assert(IS.isMemOp() && "Not a memory operation!");
-
-  const Instruction *MemOp = IS.getCurrentMemDep();
-  if (!MemOp && initializeCriticalMemDepInfo(IR, LSU))
-    return true;
-
-  MemOp = IS.getCurrentMemDep();
-  if (MemOp == IR.getInstruction())
-    return true;
-
-  const CriticalDependency &CMD = IS.getCriticalMemDep();
-  if (MemOp->isExecuting() && !CMD.Cycles) {
-    // Update the critical memory dependency info.
-    IS.setCriticalMemDep(CMD.IID, MemOp->getCyclesLeft());
-    return false;
-  }
-
-  if (!MemOp->isExecuted() && !MemOp->isRetired())
-    return false;
-
-  // Check if there are still unsolved memory dependencies.
-  InstRef DependentMemOp = LSU.isReady(IR);
-  MemOp = DependentMemOp.getInstruction();
-  IS.setCurrentMemDep(MemOp);
-  if (DependentMemOp == IR)
-    return true;
-
-  unsigned Cycles = 0;
-  if (MemOp->isExecuting())
-    Cycles = static_cast<unsigned>(MemOp->getCyclesLeft());
-  IS.setCriticalMemDep(DependentMemOp.getSourceIndex(), Cycles);
-  return false;
-}
-
 bool Scheduler::promoteToReadySet(SmallVectorImpl<InstRef> &Ready) {
   // Scan the set of waiting instructions and promote them to the
   // ready set if operands are all ready.
@@ -179,7 +132,7 @@ bool Scheduler::promoteToReadySet(SmallVectorImpl<InstRef> &Ready) {
 
     // Check if there are unsolved memory dependencies.
     Instruction &IS = *IR.getInstruction();
-    if (IS.isMemOp() && !updateMemoryDependencyInfo(IR, LSU)) {
+    if (IS.isMemOp() && !LSU.isReady(IR)) {
       ++I;
       continue;
     }
@@ -298,14 +251,16 @@ void Scheduler::analyzeDataDependencies(SmallVectorImpl<InstRef> &RegDeps,
     if (Resources->checkAvailability(IS.getDesc()))
       continue;
 
-    const CriticalDependency &CMD = IS.getCriticalMemDep();
-    if (IS.isMemOp() && IS.getCurrentMemDep() != &IS && !CMD.Cycles)
-      continue;
+    if (IS.isMemOp()) {
+      const MemoryGroup &Group = LSU.getGroup(IS.getLSUTokenID());
+      if (Group.isWaiting())
+        continue;
+      if (Group.isPending())
+        MemDeps.emplace_back(IR);
+    }
 
     if (IS.isPending())
       RegDeps.emplace_back(IR);
-    if (CMD.Cycles)
-      MemDeps.emplace_back(IR);
   }
 }
 
@@ -313,6 +268,8 @@ void Scheduler::cycleEvent(SmallVectorImpl<ResourceRef> &Freed,
                            SmallVectorImpl<InstRef> &Executed,
                            SmallVectorImpl<InstRef> &Pending,
                            SmallVectorImpl<InstRef> &Ready) {
+  LSU.cycleEvent();
+
   // Release consumed resources.
   Resources->cycleEvent(Freed);
 
@@ -343,14 +300,14 @@ bool Scheduler::mustIssueImmediately(const InstRef &IR) const {
   return Desc.MustIssueImmediately;
 }
 
-bool Scheduler::dispatch(const InstRef &IR) {
-  const Instruction &IS = *IR.getInstruction();
+bool Scheduler::dispatch(InstRef &IR) {
+  Instruction &IS = *IR.getInstruction();
   const InstrDesc &Desc = IS.getDesc();
   Resources->reserveBuffers(Desc.Buffers);
 
   // If necessary, reserve queue entries in the load-store unit (LSU).
   if (IS.isMemOp())
-    LSU.dispatch(IR);
+    IS.setLSUTokenID(LSU.dispatch(IR));
 
   if (IS.isPending()) {
     LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR
@@ -360,9 +317,9 @@ bool Scheduler::dispatch(const InstRef &IR) {
     return false;
   }
 
-  // Memory operations that are not in a ready state are initially assigned to
-  // the WaitSet.
-  if (!IS.isReady() || (IS.isMemOp() && LSU.isReady(IR) != IR)) {
+  // Memory operations that still have unsolved memory dependencies are
+  // initially dispatched to the WaitSet.
+  if (!IS.isReady() || (IS.isMemOp() && !LSU.isReady(IR))) {
     LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the WaitSet\n");
     WaitSet.push_back(IR);
     return false;