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
LSUnitBase(const MCSchedModel & SM,unsigned LQ,unsigned SQ,bool AssumeNoAlias)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() = default;
43
cycleEvent()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
dump() const50 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
dispatch(const InstRef & IR)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
isAvailable(const InstRef & IR) const196 LSUnit::Status LSUnit::isAvailable(const InstRef &IR) const {
197 const Instruction &IS = *IR.getInstruction();
198 if (IS.getMayLoad() && isLQFull())
199 return LSUnit::LSU_LQUEUE_FULL;
200 if (IS.getMayStore() && isSQFull())
201 return LSUnit::LSU_SQUEUE_FULL;
202 return LSUnit::LSU_AVAILABLE;
203 }
204
onInstructionExecuted(const InstRef & IR)205 void LSUnitBase::onInstructionExecuted(const InstRef &IR) {
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
onInstructionRetired(const InstRef & IR)214 void LSUnitBase::onInstructionRetired(const InstRef &IR) {
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
onInstructionExecuted(const InstRef & IR)233 void LSUnit::onInstructionExecuted(const InstRef &IR) {
234 const Instruction &IS = *IR.getInstruction();
235 if (!IS.isMemOp())
236 return;
237
238 LSUnitBase::onInstructionExecuted(IR);
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
254