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 
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() {}
43 
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
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 
195 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 
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 
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 
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