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) {
28 if (SM.hasExtraProcessorInfo()) {
29 const MCExtraProcessorInfo &EPI = SM.getExtraProcessorInfo();
30 if (!LQSize && EPI.LoadQueueID) {
31 const MCProcResourceDesc &LdQDesc = *SM.getProcResource(ProcResourceIdx: EPI.LoadQueueID);
32 LQSize = std::max(a: 0, b: LdQDesc.BufferSize);
33 }
34
35 if (!SQSize && EPI.StoreQueueID) {
36 const MCProcResourceDesc &StQDesc = *SM.getProcResource(ProcResourceIdx: EPI.StoreQueueID);
37 SQSize = std::max(a: 0, b: StQDesc.BufferSize);
38 }
39 }
40}
41
42LSUnitBase::~LSUnitBase() = default;
43
44void LSUnit::cycleEvent() {
45 for (const std::pair<unsigned, std::unique_ptr<MemoryGroup>> &G : Groups)
46 G.second->cycleEvent();
47}
48
49#ifndef NDEBUG
50void LSUnit::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 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(Index: NewGID);
83 NewGroup.addInstruction();
84
85 // A store may not pass a previous load or load barrier.
86 unsigned ImmediateLoadDominator =
87 std::max(a: CurrentLoadGroupID, b: CurrentLoadBarrierGroupID);
88 if (ImmediateLoadDominator) {
89 MemoryGroup &IDom = getGroup(Index: ImmediateLoadDominator);
90 LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << ImmediateLoadDominator
91 << ") --> (" << NewGID << ")\n");
92 IDom.addSuccessor(Group: &NewGroup, IsDataDependent: !assumeNoAlias());
93 }
94
95 // A store may not pass a previous store barrier.
96 if (CurrentStoreBarrierGroupID) {
97 MemoryGroup &StoreGroup = getGroup(Index: CurrentStoreBarrierGroupID);
98 LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: ("
99 << CurrentStoreBarrierGroupID << ") --> (" << NewGID
100 << ")\n");
101 StoreGroup.addSuccessor(Group: &NewGroup, IsDataDependent: true);
102 }
103
104 // A store may not pass a previous store.
105 if (CurrentStoreGroupID &&
106 (CurrentStoreGroupID != CurrentStoreBarrierGroupID)) {
107 MemoryGroup &StoreGroup = getGroup(Index: CurrentStoreGroupID);
108 LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << CurrentStoreGroupID
109 << ") --> (" << NewGID << ")\n");
110 StoreGroup.addSuccessor(Group: &NewGroup, IsDataDependent: !assumeNoAlias());
111 }
112
113 CurrentStoreGroupID = NewGID;
114 if (IsStoreBarrier)
115 CurrentStoreBarrierGroupID = NewGID;
116
117 if (IS.getMayLoad()) {
118 CurrentLoadGroupID = NewGID;
119 if (IsLoadBarrier)
120 CurrentLoadBarrierGroupID = NewGID;
121 }
122
123 return NewGID;
124 }
125
126 assert(IS.getMayLoad() && "Expected a load!");
127
128 unsigned ImmediateLoadDominator =
129 std::max(a: CurrentLoadGroupID, b: 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 IsLoadBarrier || !ImmediateLoadDominator ||
145 CurrentLoadBarrierGroupID == ImmediateLoadDominator ||
146 ImmediateLoadDominator <= CurrentStoreGroupID ||
147 getGroup(Index: ImmediateLoadDominator).isExecuting();
148
149 if (ShouldCreateANewGroup) {
150 unsigned NewGID = createMemoryGroup();
151 MemoryGroup &NewGroup = getGroup(Index: 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(Index: CurrentStoreGroupID);
158 LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << CurrentStoreGroupID
159 << ") --> (" << NewGID << ")\n");
160 StoreGroup.addSuccessor(Group: &NewGroup, IsDataDependent: true);
161 }
162
163 // A load barrier may not pass a previous load or load barrier.
164 if (IsLoadBarrier) {
165 if (ImmediateLoadDominator) {
166 MemoryGroup &LoadGroup = getGroup(Index: ImmediateLoadDominator);
167 LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: (" << ImmediateLoadDominator
168 << ") --> (" << NewGID << ")\n");
169 LoadGroup.addSuccessor(Group: &NewGroup, IsDataDependent: true);
170 }
171 } else {
172 // A younger load cannot pass a older load barrier.
173 if (CurrentLoadBarrierGroupID) {
174 MemoryGroup &LoadGroup = getGroup(Index: CurrentLoadBarrierGroupID);
175 LLVM_DEBUG(dbgs() << "[LSUnit]: GROUP DEP: ("
176 << CurrentLoadBarrierGroupID << ") --> (" << NewGID
177 << ")\n");
178 LoadGroup.addSuccessor(Group: &NewGroup, IsDataDependent: true);
179 }
180 }
181
182 CurrentLoadGroupID = NewGID;
183 if (IsLoadBarrier)
184 CurrentLoadBarrierGroupID = NewGID;
185 return NewGID;
186 }
187
188 // A load may pass a previous load.
189 MemoryGroup &Group = getGroup(Index: CurrentLoadGroupID);
190 Group.addInstruction();
191 return CurrentLoadGroupID;
192}
193
194LSUnit::Status LSUnit::isAvailable(const InstRef &IR) const {
195 const Instruction &IS = *IR.getInstruction();
196 if (IS.getMayLoad() && isLQFull())
197 return LSUnit::LSU_LQUEUE_FULL;
198 if (IS.getMayStore() && isSQFull())
199 return LSUnit::LSU_SQUEUE_FULL;
200 return LSUnit::LSU_AVAILABLE;
201}
202
203void LSUnit::onInstructionRetired(const InstRef &IR) {
204 const Instruction &IS = *IR.getInstruction();
205 bool IsALoad = IS.getMayLoad();
206 bool IsAStore = IS.getMayStore();
207 assert((IsALoad || IsAStore) && "Expected a memory operation!");
208
209 if (IsALoad) {
210 releaseLQSlot();
211 LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << IR.getSourceIndex()
212 << " has been removed from the load queue.\n");
213 }
214
215 if (IsAStore) {
216 releaseSQSlot();
217 LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << IR.getSourceIndex()
218 << " has been removed from the store queue.\n");
219 }
220}
221
222void LSUnit::onInstructionExecuted(const InstRef &IR) {
223 const Instruction &IS = *IR.getInstruction();
224 if (!IS.isMemOp())
225 return;
226
227 unsigned GroupID = IS.getLSUTokenID();
228 auto It = Groups.find(Val: GroupID);
229 assert(It != Groups.end() && "Instruction not dispatched to the LS unit");
230 It->second->onInstructionExecuted(IR);
231 if (It->second->isExecuted())
232 Groups.erase(I: It);
233
234 if (!isValidGroupID(Index: GroupID)) {
235 if (GroupID == CurrentLoadGroupID)
236 CurrentLoadGroupID = 0;
237 if (GroupID == CurrentStoreGroupID)
238 CurrentStoreGroupID = 0;
239 if (GroupID == CurrentLoadBarrierGroupID)
240 CurrentLoadBarrierGroupID = 0;
241 if (GroupID == CurrentStoreBarrierGroupID)
242 CurrentStoreBarrierGroupID = 0;
243 }
244}
245
246} // namespace mca
247} // namespace llvm
248