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   bool IsStoreBarrier = IR.getInstruction()->isAStoreBarrier();
72   bool IsLoadBarrier = IR.getInstruction()->isALoadBarrier();
73   assert((Desc.MayLoad || Desc.MayStore) && "Not a memory operation!");
74 
75   if (Desc.MayLoad)
76     acquireLQSlot();
77   if (Desc.MayStore)
78     acquireSQSlot();
79 
80   if (Desc.MayStore) {
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 (Desc.MayLoad) {
119       CurrentLoadGroupID = NewGID;
120       if (IsLoadBarrier)
121         CurrentLoadBarrierGroupID = NewGID;
122     }
123 
124     return NewGID;
125   }
126 
127   assert(Desc.MayLoad && "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 
196 LSUnit::Status LSUnit::isAvailable(const InstRef &IR) const {
197   const InstrDesc &Desc = IR.getInstruction()->getDesc();
198   if (Desc.MayLoad && isLQFull())
199     return LSUnit::LSU_LQUEUE_FULL;
200   if (Desc.MayStore && isSQFull())
201     return LSUnit::LSU_SQUEUE_FULL;
202   return LSUnit::LSU_AVAILABLE;
203 }
204 
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 
214 void LSUnitBase::onInstructionRetired(const InstRef &IR) {
215   const InstrDesc &Desc = IR.getInstruction()->getDesc();
216   bool IsALoad = Desc.MayLoad;
217   bool IsAStore = Desc.MayStore;
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 
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