1 //===----------------------- LSUnit.cpp --------------------------*- C++-*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 /// \file
10 ///
11 /// A Load-Store Unit for the llvm-mca tool.
12 ///
13 //===----------------------------------------------------------------------===//
14 
15 #include "LSUnit.h"
16 #include "Instruction.h"
17 
18 #include "llvm/Support/Debug.h"
19 #include "llvm/Support/raw_ostream.h"
20 
21 using namespace llvm;
22 
23 #define DEBUG_TYPE "llvm-mca"
24 
25 namespace mca {
26 
27 #ifndef NDEBUG
dump() const28 void LSUnit::dump() const {
29   dbgs() << "[LSUnit] LQ_Size = " << LQ_Size << '\n';
30   dbgs() << "[LSUnit] SQ_Size = " << SQ_Size << '\n';
31   dbgs() << "[LSUnit] NextLQSlotIdx = " << LoadQueue.size() << '\n';
32   dbgs() << "[LSUnit] NextSQSlotIdx = " << StoreQueue.size() << '\n';
33 }
34 #endif
35 
assignLQSlot(unsigned Index)36 void LSUnit::assignLQSlot(unsigned Index) {
37   assert(!isLQFull());
38   assert(LoadQueue.count(Index) == 0);
39 
40   LLVM_DEBUG(dbgs() << "[LSUnit] - AssignLQSlot <Idx=" << Index
41                     << ",slot=" << LoadQueue.size() << ">\n");
42   LoadQueue.insert(Index);
43 }
44 
assignSQSlot(unsigned Index)45 void LSUnit::assignSQSlot(unsigned Index) {
46   assert(!isSQFull());
47   assert(StoreQueue.count(Index) == 0);
48 
49   LLVM_DEBUG(dbgs() << "[LSUnit] - AssignSQSlot <Idx=" << Index
50                     << ",slot=" << StoreQueue.size() << ">\n");
51   StoreQueue.insert(Index);
52 }
53 
reserve(const InstRef & IR)54 bool LSUnit::reserve(const InstRef &IR) {
55   const InstrDesc &Desc = IR.getInstruction()->getDesc();
56   unsigned MayLoad = Desc.MayLoad;
57   unsigned MayStore = Desc.MayStore;
58   unsigned IsMemBarrier = Desc.HasSideEffects;
59   if (!MayLoad && !MayStore)
60     return false;
61 
62   const unsigned Index = IR.getSourceIndex();
63   if (MayLoad) {
64     if (IsMemBarrier)
65       LoadBarriers.insert(Index);
66     assignLQSlot(Index);
67   }
68   if (MayStore) {
69     if (IsMemBarrier)
70       StoreBarriers.insert(Index);
71     assignSQSlot(Index);
72   }
73   return true;
74 }
75 
isReady(const InstRef & IR) const76 bool LSUnit::isReady(const InstRef &IR) const {
77   const unsigned Index = IR.getSourceIndex();
78   bool IsALoad = LoadQueue.count(Index) != 0;
79   bool IsAStore = StoreQueue.count(Index) != 0;
80   assert((IsALoad || IsAStore) && "Instruction is not in queue!");
81 
82   if (IsALoad && !LoadBarriers.empty()) {
83     unsigned LoadBarrierIndex = *LoadBarriers.begin();
84     if (Index > LoadBarrierIndex)
85       return false;
86     if (Index == LoadBarrierIndex && Index != *LoadQueue.begin())
87       return false;
88   }
89 
90   if (IsAStore && !StoreBarriers.empty()) {
91     unsigned StoreBarrierIndex = *StoreBarriers.begin();
92     if (Index > StoreBarrierIndex)
93       return false;
94     if (Index == StoreBarrierIndex && Index != *StoreQueue.begin())
95       return false;
96   }
97 
98   if (NoAlias && IsALoad)
99     return true;
100 
101   if (StoreQueue.size()) {
102     // Check if this memory operation is younger than the older store.
103     if (Index > *StoreQueue.begin())
104       return false;
105   }
106 
107   // Okay, we are older than the oldest store in the queue.
108   // If there are no pending loads, then we can say for sure that this
109   // instruction is ready.
110   if (isLQEmpty())
111     return true;
112 
113   // Check if there are no older loads.
114   if (Index <= *LoadQueue.begin())
115     return true;
116 
117   // There is at least one younger load.
118   return !IsAStore;
119 }
120 
onInstructionExecuted(const InstRef & IR)121 void LSUnit::onInstructionExecuted(const InstRef &IR) {
122   const unsigned Index = IR.getSourceIndex();
123   std::set<unsigned>::iterator it = LoadQueue.find(Index);
124   if (it != LoadQueue.end()) {
125     LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << Index
126                       << " has been removed from the load queue.\n");
127     LoadQueue.erase(it);
128   }
129 
130   it = StoreQueue.find(Index);
131   if (it != StoreQueue.end()) {
132     LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << Index
133                       << " has been removed from the store queue.\n");
134     StoreQueue.erase(it);
135   }
136 
137   if (!StoreBarriers.empty() && Index == *StoreBarriers.begin()) {
138     LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << Index
139                       << " has been removed from the set of store barriers.\n");
140     StoreBarriers.erase(StoreBarriers.begin());
141   }
142   if (!LoadBarriers.empty() && Index == *LoadBarriers.begin()) {
143     LLVM_DEBUG(dbgs() << "[LSUnit]: Instruction idx=" << Index
144                       << " has been removed from the set of load barriers.\n");
145     LoadBarriers.erase(LoadBarriers.begin());
146   }
147 }
148 } // namespace mca
149