LLVM  15.0.0git
LSUnit.cpp
Go to the documentation of this file.
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 
15 #include "llvm/MCA/Instruction.h"
16 #include "llvm/Support/Debug.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()) {
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 
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 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
100  << ") --> (" << NewGID << ")\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 
114  CurrentStoreGroupID = NewGID;
115  if (IsStoreBarrier)
116  CurrentStoreBarrierGroupID = NewGID;
117 
118  if (IS.getMayLoad()) {
119  CurrentLoadGroupID = NewGID;
120  if (IsLoadBarrier)
121  CurrentLoadBarrierGroupID = NewGID;
122  }
123 
124  return NewGID;
125  }
126 
127  assert(IS.getMayLoad() && "Expected a load!");
128 
129  unsigned ImmediateLoadDominator =
130  std::max(CurrentLoadGroupID, CurrentLoadBarrierGroupID);
131 
132  // A new load group is created if we are in one of the following situations:
133  // 1) This is a load barrier (by construction, a load barrier is always
134  // assigned to a different memory group).
135  // 2) There is no load in flight (by construction we always keep loads and
136  // stores into separate memory groups).
137  // 3) There is a load barrier in flight. This load depends on it.
138  // 4) There is an intervening store between the last load dispatched to the
139  // LSU and this load. We always create a new group even if this load
140  // does not alias the last dispatched store.
141  // 5) There is no intervening store and there is an active load group.
142  // However that group has already started execution, so we cannot add
143  // this load to it.
144  bool ShouldCreateANewGroup =
145  IsLoadBarrier || !ImmediateLoadDominator ||
146  CurrentLoadBarrierGroupID == ImmediateLoadDominator ||
147  ImmediateLoadDominator <= CurrentStoreGroupID ||
148  getGroup(ImmediateLoadDominator).isExecuting();
149 
150  if (ShouldCreateANewGroup) {
151  unsigned NewGID = createMemoryGroup();
152  MemoryGroup &NewGroup = getGroup(NewGID);
153  NewGroup.addInstruction();
154 
155  // A load may not pass a previous store or store barrier
156  // unless flag 'NoAlias' is set.
157  if (!assumeNoAlias() && CurrentStoreGroupID) {
158  MemoryGroup &StoreGroup = getGroup(CurrentStoreGroupID);
159  LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << CurrentStoreGroupID
160  << ") --> (" << NewGID << ")\n");
161  StoreGroup.addSuccessor(&NewGroup, true);
162  }
163 
164  // A load barrier may not pass a previous load or load barrier.
165  if (IsLoadBarrier) {
166  if (ImmediateLoadDominator) {
167  MemoryGroup &LoadGroup = getGroup(ImmediateLoadDominator);
168  LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: ("
169  << ImmediateLoadDominator
170  << ") --> (" << NewGID << ")\n");
171  LoadGroup.addSuccessor(&NewGroup, true);
172  }
173  } else {
174  // A younger load cannot pass a older load barrier.
175  if (CurrentLoadBarrierGroupID) {
176  MemoryGroup &LoadGroup = getGroup(CurrentLoadBarrierGroupID);
177  LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: ("
178  << CurrentLoadBarrierGroupID
179  << ") --> (" << NewGID << ")\n");
180  LoadGroup.addSuccessor(&NewGroup, true);
181  }
182  }
183 
184  CurrentLoadGroupID = NewGID;
185  if (IsLoadBarrier)
186  CurrentLoadBarrierGroupID = NewGID;
187  return NewGID;
188  }
189 
190  // A load may pass a previous load.
191  MemoryGroup &Group = getGroup(CurrentLoadGroupID);
192  Group.addInstruction();
193  return CurrentLoadGroupID;
194 }
195 
197  const Instruction &IS = *IR.getInstruction();
198  if (IS.getMayLoad() && isLQFull())
200  if (IS.getMayStore() && isSQFull())
202  return LSUnit::LSU_AVAILABLE;
203 }
204 
206  unsigned GroupID = IR.getInstruction()->getLSUTokenID();
207  auto It = Groups.find(GroupID);
208  assert(It != Groups.end() && "Instruction not dispatched to the LS unit");
209  It->second->onInstructionExecuted(IR);
210  if (It->second->isExecuted())
211  Groups.erase(It);
212 }
213 
215  const Instruction &IS = *IR.getInstruction();
216  bool IsALoad = IS.getMayLoad();
217  bool IsAStore = IS.getMayStore();
218  assert((IsALoad || IsAStore) && "Expected a memory operation!");
219 
220  if (IsALoad) {
221  releaseLQSlot();
222  LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << IR.getSourceIndex()
223  << " has been removed from the load queue.\n");
224  }
225 
226  if (IsAStore) {
227  releaseSQSlot();
228  LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << IR.getSourceIndex()
229  << " has been removed from the store queue.\n");
230  }
231 }
232 
234  const Instruction &IS = *IR.getInstruction();
235  if (!IS.isMemOp())
236  return;
237 
239  unsigned GroupID = IS.getLSUTokenID();
240  if (!isValidGroupID(GroupID)) {
241  if (GroupID == CurrentLoadGroupID)
242  CurrentLoadGroupID = 0;
243  if (GroupID == CurrentStoreGroupID)
244  CurrentStoreGroupID = 0;
245  if (GroupID == CurrentLoadBarrierGroupID)
246  CurrentLoadBarrierGroupID = 0;
247  if (GroupID == CurrentStoreBarrierGroupID)
248  CurrentStoreBarrierGroupID = 0;
249  }
250 }
251 
252 } // namespace mca
253 } // namespace llvm
llvm::MCProcResourceDesc::BufferSize
int BufferSize
Definition: MCSchedule.h:48
llvm::mca::MemoryGroup::getNumInstructions
unsigned getNumInstructions() const
Definition: LSUnit.h:71
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::mca::LSUnit::isAvailable
Status isAvailable(const InstRef &IR) const override
Returns LSU_AVAILABLE if there are enough load/store queue entries to accomodate instruction IR.
Definition: LSUnit.cpp:196
llvm::mca::LSUnitBase::isSQFull
bool isSQFull() const
Definition: LSUnit.h:268
llvm::mca::LSUnitBase::isLQFull
bool isLQFull() const
Definition: LSUnit.h:269
llvm::mca::LSUnitBase::dump
void dump() const
Definition: LSUnit.cpp:50
llvm::mca::LSUnitBase::~LSUnitBase
virtual ~LSUnitBase()
llvm::mca::Instruction::getLSUTokenID
unsigned getLSUTokenID() const
Definition: Instruction.h:648
llvm::mca::Instruction
An instruction propagated through the simulated instruction pipeline.
Definition: Instruction.h:594
llvm::mca::LSUnitBase::getGroup
const MemoryGroup & getGroup(unsigned Index) const
Definition: LSUnit.h:304
llvm::mca::MemoryGroup::getNumExecutedPredecessors
unsigned getNumExecutedPredecessors() const
Definition: LSUnit.h:68
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
Instruction.h
llvm::mca::MemoryGroup::isExecuting
bool isExecuting() const
Definition: LSUnit.h:110
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::mca::LSUnitBase::getStoreQueueSize
unsigned getStoreQueueSize() const
Returns the total number of entries in the store queue.
Definition: LSUnit.h:234
llvm::mca::MemoryGroup::getNumExecuting
unsigned getNumExecuting() const
Definition: LSUnit.h:72
llvm::MCSchedModel::getExtraProcessorInfo
const MCExtraProcessorInfo & getExtraProcessorInfo() const
Definition: MCSchedule.h:322
llvm::mca::LSUnitBase::onInstructionExecuted
virtual void onInstructionExecuted(const InstRef &IR)
Definition: LSUnit.cpp:205
llvm::mca::MemoryGroup::addSuccessor
void addSuccessor(MemoryGroup *Group, bool IsDataDependent)
Definition: LSUnit.h:82
llvm::mca::LSUnitBase::LSU_AVAILABLE
@ LSU_AVAILABLE
Definition: LSUnit.h:246
IR
Statically lint checks LLVM IR
Definition: Lint.cpp:745
LSUnit.h
llvm::mca::MemoryGroup
A node of a memory dependency graph.
Definition: LSUnit.h:35
llvm::mca::LSUnit::dispatch
unsigned dispatch(const InstRef &IR) override
Allocates LS resources for instruction IR.
Definition: LSUnit.cpp:69
llvm::mca::LSUnitBase::acquireSQSlot
void acquireSQSlot()
Definition: LSUnit.h:239
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
llvm::mca::LSUnitBase::LSUnitBase
LSUnitBase(const MCSchedModel &SM, unsigned LoadQueueSize, unsigned StoreQueueSize, bool AssumeNoAlias)
Definition: LSUnit.cpp:24
llvm::MCProcResourceDesc
Define a kind of processor resource that will be modeled by the scheduler.
Definition: MCSchedule.h:31
llvm::MCExtraProcessorInfo::LoadQueueID
unsigned LoadQueueID
Definition: MCSchedule.h:186
llvm::mca::MemoryGroup::getNumExecutingPredecessors
unsigned getNumExecutingPredecessors() const
Definition: LSUnit.h:65
llvm::mca::LSUnitBase::assumeNoAlias
bool assumeNoAlias() const
Definition: LSUnit.h:243
llvm::mca::LSUnitBase::getUsedLQEntries
unsigned getUsedLQEntries() const
Definition: LSUnit.h:236
llvm::MCSchedModel::hasExtraProcessorInfo
bool hasExtraProcessorInfo() const
Definition: MCSchedule.h:315
llvm::mca::LSUnitBase::getLoadQueueSize
unsigned getLoadQueueSize() const
Returns the total number of entries in the load queue.
Definition: LSUnit.h:231
llvm::mca::LSUnit::onInstructionExecuted
void onInstructionExecuted(const InstRef &IR) override
Definition: LSUnit.cpp:233
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::mca::LSUnitBase::releaseLQSlot
void releaseLQSlot()
Definition: LSUnit.h:240
llvm::mca::InstRef
An InstRef contains both a SourceMgr index and Instruction pair.
Definition: Instruction.h:711
llvm::mca::LSUnitBase::isValidGroupID
bool isValidGroupID(unsigned Index) const
Definition: LSUnit.h:271
llvm::mca::LSUnitBase::onInstructionRetired
virtual void onInstructionRetired(const InstRef &IR)
Definition: LSUnit.cpp:214
llvm::MCExtraProcessorInfo::StoreQueueID
unsigned StoreQueueID
Definition: MCSchedule.h:187
llvm::MCSchedModel::getProcResource
const MCProcResourceDesc * getProcResource(unsigned ProcResourceIdx) const
Definition: MCSchedule.h:339
llvm::mca::LSUnitBase::getUsedSQEntries
unsigned getUsedSQEntries() const
Definition: LSUnit.h:237
llvm::MCSchedModel
Machine model for scheduling, bundling, and heuristics.
Definition: MCSchedule.h:244
llvm::mca::LSUnitBase::acquireLQSlot
void acquireLQSlot()
Definition: LSUnit.h:238
llvm::mca::MemoryGroup::addInstruction
void addInstruction()
Definition: LSUnit.h:181
llvm::mca::LSUnitBase::Status
Status
Definition: LSUnit.h:245
llvm::mca::LSUnitBase::createMemoryGroup
unsigned createMemoryGroup()
Definition: LSUnit.h:314
llvm::mca::InstructionBase::isAStoreBarrier
bool isAStoreBarrier() const
Definition: Instruction.h:540
llvm::mca::InstructionBase::getMayLoad
bool getMayLoad() const
Definition: Instruction.h:582
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::mca::InstructionBase::isALoadBarrier
bool isALoadBarrier() const
Definition: Instruction.h:539
llvm::mca::LSUnitBase::releaseSQSlot
void releaseSQSlot()
Definition: LSUnit.h:241
llvm::mca::MemoryGroup::getNumPredecessors
unsigned getNumPredecessors() const
Definition: LSUnit.h:64
llvm::mca::InstructionBase::isMemOp
bool isMemOp() const
Definition: Instruction.h:572
raw_ostream.h
llvm::mca::LSUnitBase::cycleEvent
virtual void cycleEvent()
Definition: LSUnit.cpp:44
llvm::mca::InstructionBase::getMayStore
bool getMayStore() const
Definition: Instruction.h:583
llvm::mca::LSUnitBase::LSU_LQUEUE_FULL
@ LSU_LQUEUE_FULL
Definition: LSUnit.h:247
llvm::mca::MemoryGroup::getNumExecuted
unsigned getNumExecuted() const
Definition: LSUnit.h:73
Debug.h
llvm::mca::LSUnitBase::LSU_SQUEUE_FULL
@ LSU_SQUEUE_FULL
Definition: LSUnit.h:248
llvm::MCExtraProcessorInfo
Provide extra details about the machine processor.
Definition: MCSchedule.h:177