LLVM  14.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 
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 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 
196  const InstrDesc &Desc = IR.getInstruction()->getDesc();
197  if (Desc.MayLoad && isLQFull())
199  if (Desc.MayStore && isSQFull())
201  return LSUnit::LSU_AVAILABLE;
202 }
203 
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 
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 
233  const Instruction &IS = *IR.getInstruction();
234  if (!IS.isMemOp())
235  return;
236 
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
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: AllocatorList.h:23
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:195
llvm::mca::LSUnitBase::isSQFull
bool isSQFull() const
Definition: LSUnit.h:268
llvm::mca::InstrDesc::MayStore
unsigned MayStore
Definition: Instruction.h:476
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()
Definition: LSUnit.cpp:42
llvm::mca::Instruction::getLSUTokenID
unsigned getLSUTokenID() const
Definition: Instruction.h:623
llvm::mca::Instruction
An instruction propagated through the simulated instruction pipeline.
Definition: Instruction.h:569
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:204
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:746
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:202
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::InstrDesc
An instruction descriptor.
Definition: Instruction.h:447
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:232
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:686
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:213
llvm::mca::InstrDesc::MayLoad
unsigned MayLoad
Definition: Instruction.h:475
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::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
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:562
raw_ostream.h
llvm::mca::LSUnitBase::cycleEvent
virtual void cycleEvent()
Definition: LSUnit.cpp:44
llvm::mca::InstrDesc::HasSideEffects
unsigned HasSideEffects
Definition: Instruction.h:477
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