LSUnit.cpp revision 360784 
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
21namespace llvm {
22namespace mca {
23
24LSUnitBase::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
42LSUnitBase::~LSUnitBase() {}
43
44void LSUnitBase::cycleEvent() {
45  for (const std::pair<unsigned, std::unique_ptr<MemoryGroup>> &G : Groups)
46    G.second->cycleEvent();
47}
48
49#ifndef NDEBUG
50void 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
69unsigned 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    // Always create a new group for store operations.
81
82    // A store may not pass a previous store or store barrier.
83    unsigned NewGID = createMemoryGroup();
84    MemoryGroup &NewGroup = getGroup(NewGID);
85    NewGroup.addInstruction();
86
87    // A store may not pass a previous load or load barrier.
88    unsigned ImmediateLoadDominator =
89        std::max(CurrentLoadGroupID, CurrentLoadBarrierGroupID);
90    if (ImmediateLoadDominator) {
91      MemoryGroup &IDom = getGroup(ImmediateLoadDominator);
92      LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << ImmediateLoadDominator
93                        << ") --> (" << NewGID << ")\n");
94      IDom.addSuccessor(&NewGroup);
95    }
96    if (CurrentStoreGroupID) {
97      MemoryGroup &StoreGroup = getGroup(CurrentStoreGroupID);
98      LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << CurrentStoreGroupID
99                        << ") --> (" << NewGID << ")\n");
100      StoreGroup.addSuccessor(&NewGroup);
101    }
102
103    CurrentStoreGroupID = NewGID;
104    if (Desc.MayLoad) {
105      CurrentLoadGroupID = NewGID;
106      if (IsMemBarrier)
107        CurrentLoadBarrierGroupID = NewGID;
108    }
109
110    return NewGID;
111  }
112
113  assert(Desc.MayLoad && "Expected a load!");
114
115  // Always create a new memory group if this is the first load of the sequence.
116
117  // A load may not pass a previous store unless flag 'NoAlias' is set.
118  // A load may pass a previous load.
119  // A younger load cannot pass a older load barrier.
120  // A load barrier cannot pass a older load.
121  bool ShouldCreateANewGroup = !CurrentLoadGroupID || IsMemBarrier ||
122                               CurrentLoadGroupID <= CurrentStoreGroupID ||
123                               CurrentLoadGroupID <= CurrentLoadBarrierGroupID;
124  if (ShouldCreateANewGroup) {
125    unsigned NewGID = createMemoryGroup();
126    MemoryGroup &NewGroup = getGroup(NewGID);
127    NewGroup.addInstruction();
128
129    if (!assumeNoAlias() && CurrentStoreGroupID) {
130      MemoryGroup &StGroup = getGroup(CurrentStoreGroupID);
131      LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << CurrentStoreGroupID
132                        << ") --> (" << NewGID << ")\n");
133      StGroup.addSuccessor(&NewGroup);
134    }
135    if (CurrentLoadBarrierGroupID) {
136      MemoryGroup &LdGroup = getGroup(CurrentLoadBarrierGroupID);
137      LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << CurrentLoadBarrierGroupID
138                        << ") --> (" << NewGID << ")\n");
139      LdGroup.addSuccessor(&NewGroup);
140    }
141
142    CurrentLoadGroupID = NewGID;
143    if (IsMemBarrier)
144      CurrentLoadBarrierGroupID = NewGID;
145    return NewGID;
146  }
147
148  MemoryGroup &Group = getGroup(CurrentLoadGroupID);
149  Group.addInstruction();
150  return CurrentLoadGroupID;
151}
152
153LSUnit::Status LSUnit::isAvailable(const InstRef &IR) const {
154  const InstrDesc &Desc = IR.getInstruction()->getDesc();
155  if (Desc.MayLoad && isLQFull())
156    return LSUnit::LSU_LQUEUE_FULL;
157  if (Desc.MayStore && isSQFull())
158    return LSUnit::LSU_SQUEUE_FULL;
159  return LSUnit::LSU_AVAILABLE;
160}
161
162void LSUnitBase::onInstructionExecuted(const InstRef &IR) {
163  unsigned GroupID = IR.getInstruction()->getLSUTokenID();
164  auto It = Groups.find(GroupID);
165  assert(It != Groups.end() && "Instruction not dispatched to the LS unit");
166  It->second->onInstructionExecuted();
167  if (It->second->isExecuted())
168    Groups.erase(It);
169}
170
171void LSUnitBase::onInstructionRetired(const InstRef &IR) {
172  const InstrDesc &Desc = IR.getInstruction()->getDesc();
173  bool IsALoad = Desc.MayLoad;
174  bool IsAStore = Desc.MayStore;
175  assert((IsALoad || IsAStore) && "Expected a memory operation!");
176
177  if (IsALoad) {
178    releaseLQSlot();
179    LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << IR.getSourceIndex()
180                      << " has been removed from the load queue.\n");
181  }
182
183  if (IsAStore) {
184    releaseSQSlot();
185    LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << IR.getSourceIndex()
186                      << " has been removed from the store queue.\n");
187  }
188}
189
190void LSUnit::onInstructionExecuted(const InstRef &IR) {
191  const Instruction &IS = *IR.getInstruction();
192  if (!IS.isMemOp())
193    return;
194
195  LSUnitBase::onInstructionExecuted(IR);
196  unsigned GroupID = IS.getLSUTokenID();
197  if (!isValidGroupID(GroupID)) {
198    if (GroupID == CurrentLoadGroupID)
199      CurrentLoadGroupID = 0;
200    if (GroupID == CurrentStoreGroupID)
201      CurrentStoreGroupID = 0;
202    if (GroupID == CurrentLoadBarrierGroupID)
203      CurrentLoadBarrierGroupID = 0;
204  }
205}
206
207} // namespace mca
208} // namespace llvm
209