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
~LSUnitBase()42 LSUnitBase::~LSUnitBase() {}
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 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
isAvailable(const InstRef & IR) const195 LSUnit::Status LSUnit::isAvailable(const InstRef &IR) const {
196 const InstrDesc &Desc = IR.getInstruction()->getDesc();
197 if (Desc.MayLoad && isLQFull())
198 return LSUnit::LSU_LQUEUE_FULL;
199 if (Desc.MayStore && isSQFull())
200 return LSUnit::LSU_SQUEUE_FULL;
201 return LSUnit::LSU_AVAILABLE;
202 }
203
onInstructionExecuted(const InstRef & IR)204 void LSUnitBase::onInstructionExecuted(const InstRef &IR) {
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
onInstructionRetired(const InstRef & IR)213 void LSUnitBase::onInstructionRetired(const InstRef &IR) {
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
onInstructionExecuted(const InstRef & IR)232 void LSUnit::onInstructionExecuted(const InstRef &IR) {
233 const Instruction &IS = *IR.getInstruction();
234 if (!IS.isMemOp())
235 return;
236
237 LSUnitBase::onInstructionExecuted(IR);
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
253