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), NoAlias(AssumeNoAlias) {
27   if (SM.hasExtraProcessorInfo()) {
28     const MCExtraProcessorInfo &EPI = SM.getExtraProcessorInfo();
29     if (!LQSize && EPI.LoadQueueID) {
30       const MCProcResourceDesc &LdQDesc = *SM.getProcResource(EPI.LoadQueueID);
31       LQSize = LdQDesc.BufferSize;
32     }
33 
34     if (!SQSize && EPI.StoreQueueID) {
35       const MCProcResourceDesc &StQDesc = *SM.getProcResource(EPI.StoreQueueID);
36       SQSize = StQDesc.BufferSize;
37     }
38   }
39 }
40 
41 LSUnitBase::~LSUnitBase() {}
42 
43 #ifndef NDEBUG
44 void LSUnit::dump() const {
45   dbgs() << "[LSUnit] LQ_Size = " << getLoadQueueSize() << '\n';
46   dbgs() << "[LSUnit] SQ_Size = " << getStoreQueueSize() << '\n';
47   dbgs() << "[LSUnit] NextLQSlotIdx = " << LoadQueue.size() << '\n';
48   dbgs() << "[LSUnit] NextSQSlotIdx = " << StoreQueue.size() << '\n';
49 }
50 #endif
51 
52 void LSUnit::assignLQSlot(const InstRef &IR) {
53   assert(!isLQFull() && "Load Queue is full!");
54 
55   LLVM_DEBUG(dbgs() << "[LSUnit] - AssignLQSlot <Idx=" << IR.getSourceIndex()
56                     << ",slot=" << LoadQueue.size() << ">\n");
57   LoadQueue.insert(IR);
58 }
59 
60 void LSUnit::assignSQSlot(const InstRef &IR) {
61   assert(!isSQFull() && "Store Queue is full!");
62 
63   LLVM_DEBUG(dbgs() << "[LSUnit] - AssignSQSlot <Idx=" << IR.getSourceIndex()
64                     << ",slot=" << StoreQueue.size() << ">\n");
65   StoreQueue.insert(IR);
66 }
67 
68 void LSUnit::dispatch(const InstRef &IR) {
69   const InstrDesc &Desc = IR.getInstruction()->getDesc();
70   unsigned IsMemBarrier = Desc.HasSideEffects;
71   assert((Desc.MayLoad || Desc.MayStore) && "Not a memory operation!");
72 
73   if (Desc.MayLoad) {
74     if (IsMemBarrier)
75       LoadBarriers.insert(IR);
76     assignLQSlot(IR);
77   }
78 
79   if (Desc.MayStore) {
80     if (IsMemBarrier)
81       StoreBarriers.insert(IR);
82     assignSQSlot(IR);
83   }
84 }
85 
86 LSUnit::Status LSUnit::isAvailable(const InstRef &IR) const {
87   const InstrDesc &Desc = IR.getInstruction()->getDesc();
88   if (Desc.MayLoad && isLQFull())
89     return LSUnit::LSU_LQUEUE_FULL;
90   if (Desc.MayStore && isSQFull())
91     return LSUnit::LSU_SQUEUE_FULL;
92   return LSUnit::LSU_AVAILABLE;
93 }
94 
95 const InstRef &LSUnit::isReady(const InstRef &IR) const {
96   const InstrDesc &Desc = IR.getInstruction()->getDesc();
97   const unsigned Index = IR.getSourceIndex();
98   bool IsALoad = Desc.MayLoad;
99   bool IsAStore = Desc.MayStore;
100   assert((IsALoad || IsAStore) && "Not a memory operation!");
101 
102   if (IsALoad && !LoadBarriers.empty()) {
103     const InstRef &LoadBarrier = *LoadBarriers.begin();
104     // A younger load cannot pass a older load barrier.
105     if (Index > LoadBarrier.getSourceIndex())
106       return LoadBarrier;
107     // A load barrier cannot pass a older load.
108     if (Index == LoadBarrier.getSourceIndex()) {
109       const InstRef &Load = *LoadQueue.begin();
110       if (Index != Load.getSourceIndex())
111         return Load;
112     }
113   }
114 
115   if (IsAStore && !StoreBarriers.empty()) {
116     const InstRef &StoreBarrier = *StoreBarriers.begin();
117     // A younger store cannot pass a older store barrier.
118     if (Index > StoreBarrier.getSourceIndex())
119       return StoreBarrier;
120     // A store barrier cannot pass a older store.
121     if (Index == StoreBarrier.getSourceIndex()) {
122       const InstRef &Store = *StoreQueue.begin();
123       if (Index != Store.getSourceIndex())
124         return Store;
125     }
126   }
127 
128   // A load may not pass a previous store unless flag 'NoAlias' is set.
129   // A load may pass a previous load.
130   if (assumeNoAlias() && IsALoad)
131     return IR;
132 
133   if (StoreQueue.size()) {
134     // A load may not pass a previous store.
135     // A store may not pass a previous store.
136     const InstRef &Store = *StoreQueue.begin();
137     if (Index > Store.getSourceIndex())
138       return Store;
139   }
140 
141   // Okay, we are older than the oldest store in the queue.
142   if (isLQEmpty())
143     return IR;
144 
145   // Check if there are no older loads.
146   const InstRef &Load = *LoadQueue.begin();
147   if (Index <= Load.getSourceIndex())
148     return IR;
149 
150   // A load may pass a previous load.
151   if (IsALoad)
152     return IR;
153 
154   // A store may not pass a previous load.
155   return Load;
156 }
157 
158 void LSUnit::onInstructionExecuted(const InstRef &IR) {
159   const InstrDesc &Desc = IR.getInstruction()->getDesc();
160   const unsigned Index = IR.getSourceIndex();
161   bool IsALoad = Desc.MayLoad;
162   bool IsAStore = Desc.MayStore;
163 
164   if (IsALoad) {
165     if (LoadQueue.erase(IR)) {
166       LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << Index
167                         << " has been removed from the load queue.\n");
168     }
169     if (!LoadBarriers.empty()) {
170       const InstRef &LoadBarrier = *LoadBarriers.begin();
171       if (Index == LoadBarrier.getSourceIndex()) {
172         LLVM_DEBUG(
173             dbgs() << "[LSUnit]: Instruction idx=" << Index
174                    << " has been removed from the set of load barriers.\n");
175         LoadBarriers.erase(IR);
176       }
177     }
178   }
179 
180   if (IsAStore) {
181     if (StoreQueue.erase(IR)) {
182       LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << Index
183                         << " has been removed from the store queue.\n");
184     }
185 
186     if (!StoreBarriers.empty()) {
187       const InstRef &StoreBarrier = *StoreBarriers.begin();
188       if (Index == StoreBarrier.getSourceIndex()) {
189         LLVM_DEBUG(
190             dbgs() << "[LSUnit]: Instruction idx=" << Index
191                    << " has been removed from the set of store barriers.\n");
192         StoreBarriers.erase(IR);
193       }
194     }
195   }
196 }
197 
198 } // namespace mca
199 } // namespace llvm
200