1 //===--------------------- Instruction.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 //
9 // This file defines abstractions used by the Pipeline to model register reads,
10 // register writes and instructions.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/MCA/Instruction.h"
15 #include "llvm/Support/Debug.h"
16 #include "llvm/Support/raw_ostream.h"
17 
18 namespace llvm {
19 namespace mca {
20 
21 void WriteState::writeStartEvent(unsigned IID, MCPhysReg RegID,
22                                  unsigned Cycles) {
23   CRD.IID = IID;
24   CRD.RegID = RegID;
25   CRD.Cycles = Cycles;
26   DependentWriteCyclesLeft = Cycles;
27   DependentWrite = nullptr;
28 }
29 
30 void ReadState::writeStartEvent(unsigned IID, MCPhysReg RegID,
31                                 unsigned Cycles) {
32   assert(DependentWrites);
33   assert(CyclesLeft == UNKNOWN_CYCLES);
34 
35   // This read may be dependent on more than one write. This typically occurs
36   // when a definition is the result of multiple writes where at least one
37   // write does a partial register update.
38   // The HW is forced to do some extra bookkeeping to track of all the
39   // dependent writes, and implement a merging scheme for the partial writes.
40   --DependentWrites;
41   if (TotalCycles < Cycles) {
42     CRD.IID = IID;
43     CRD.RegID = RegID;
44     CRD.Cycles = Cycles;
45     TotalCycles = Cycles;
46   }
47 
48   if (!DependentWrites) {
49     CyclesLeft = TotalCycles;
50     IsReady = !CyclesLeft;
51   }
52 }
53 
54 void WriteState::onInstructionIssued(unsigned IID) {
55   assert(CyclesLeft == UNKNOWN_CYCLES);
56   // Update the number of cycles left based on the WriteDescriptor info.
57   CyclesLeft = getLatency();
58 
59   // Now that the time left before write-back is known, notify
60   // all the users.
61   for (const std::pair<ReadState *, int> &User : Users) {
62     ReadState *RS = User.first;
63     unsigned ReadCycles = std::max(0, CyclesLeft - User.second);
64     RS->writeStartEvent(IID, RegisterID, ReadCycles);
65   }
66 
67   // Notify any writes that are in a false dependency with this write.
68   if (PartialWrite)
69     PartialWrite->writeStartEvent(IID, RegisterID, CyclesLeft);
70 }
71 
72 void WriteState::addUser(unsigned IID, ReadState *User, int ReadAdvance) {
73   // If CyclesLeft is different than -1, then we don't need to
74   // update the list of users. We can just notify the user with
75   // the actual number of cycles left (which may be zero).
76   if (CyclesLeft != UNKNOWN_CYCLES) {
77     unsigned ReadCycles = std::max(0, CyclesLeft - ReadAdvance);
78     User->writeStartEvent(IID, RegisterID, ReadCycles);
79     return;
80   }
81 
82   Users.emplace_back(User, ReadAdvance);
83 }
84 
85 void WriteState::addUser(unsigned IID, WriteState *User) {
86   if (CyclesLeft != UNKNOWN_CYCLES) {
87     User->writeStartEvent(IID, RegisterID, std::max(0, CyclesLeft));
88     return;
89   }
90 
91   assert(!PartialWrite && "PartialWrite already set!");
92   PartialWrite = User;
93   User->setDependentWrite(this);
94 }
95 
96 void WriteState::cycleEvent() {
97   // Note: CyclesLeft can be a negative number. It is an error to
98   // make it an unsigned quantity because users of this write may
99   // specify a negative ReadAdvance.
100   if (CyclesLeft != UNKNOWN_CYCLES)
101     CyclesLeft--;
102 
103   if (DependentWriteCyclesLeft)
104     DependentWriteCyclesLeft--;
105 }
106 
107 void ReadState::cycleEvent() {
108   // Update the total number of cycles.
109   if (DependentWrites && TotalCycles) {
110     --TotalCycles;
111     return;
112   }
113 
114   // Bail out immediately if we don't know how many cycles are left.
115   if (CyclesLeft == UNKNOWN_CYCLES)
116     return;
117 
118   if (CyclesLeft) {
119     --CyclesLeft;
120     IsReady = !CyclesLeft;
121   }
122 }
123 
124 #ifndef NDEBUG
125 void WriteState::dump() const {
126   dbgs() << "{ OpIdx=" << WD->OpIndex << ", Lat=" << getLatency() << ", RegID "
127          << getRegisterID() << ", Cycles Left=" << getCyclesLeft() << " }";
128 }
129 #endif
130 
131 const CriticalDependency &Instruction::computeCriticalRegDep() {
132   if (CriticalRegDep.Cycles)
133     return CriticalRegDep;
134 
135   unsigned MaxLatency = 0;
136   for (const WriteState &WS : getDefs()) {
137     const CriticalDependency &WriteCRD = WS.getCriticalRegDep();
138     if (WriteCRD.Cycles > MaxLatency)
139       CriticalRegDep = WriteCRD;
140   }
141 
142   for (const ReadState &RS : getUses()) {
143     const CriticalDependency &ReadCRD = RS.getCriticalRegDep();
144     if (ReadCRD.Cycles > MaxLatency)
145       CriticalRegDep = ReadCRD;
146   }
147 
148   return CriticalRegDep;
149 }
150 
151 void Instruction::reset() {
152   // Note that this won't clear read/write descriptors
153   // or other non-trivial fields
154   Stage = IS_INVALID;
155   CyclesLeft = UNKNOWN_CYCLES;
156   clearOptimizableMove();
157   RCUTokenID = 0;
158   LSUTokenID = 0;
159   CriticalResourceMask = 0;
160   IsEliminated = false;
161 }
162 
163 void Instruction::dispatch(unsigned RCUToken) {
164   assert(Stage == IS_INVALID);
165   Stage = IS_DISPATCHED;
166   RCUTokenID = RCUToken;
167 
168   // Check if input operands are already available.
169   if (updateDispatched())
170     updatePending();
171 }
172 
173 void Instruction::execute(unsigned IID) {
174   assert(Stage == IS_READY);
175   Stage = IS_EXECUTING;
176 
177   // Set the cycles left before the write-back stage.
178   CyclesLeft = getLatency();
179 
180   for (WriteState &WS : getDefs())
181     WS.onInstructionIssued(IID);
182 
183   // Transition to the "executed" stage if this is a zero-latency instruction.
184   if (!CyclesLeft)
185     Stage = IS_EXECUTED;
186 }
187 
188 void Instruction::forceExecuted() {
189   assert(Stage == IS_READY && "Invalid internal state!");
190   CyclesLeft = 0;
191   Stage = IS_EXECUTED;
192 }
193 
194 bool Instruction::updatePending() {
195   assert(isPending() && "Unexpected instruction stage found!");
196 
197   if (!all_of(getUses(), [](const ReadState &Use) { return Use.isReady(); }))
198     return false;
199 
200   // A partial register write cannot complete before a dependent write.
201   if (!all_of(getDefs(), [](const WriteState &Def) { return Def.isReady(); }))
202     return false;
203 
204   Stage = IS_READY;
205   return true;
206 }
207 
208 bool Instruction::updateDispatched() {
209   assert(isDispatched() && "Unexpected instruction stage found!");
210 
211   if (!all_of(getUses(), [](const ReadState &Use) {
212         return Use.isPending() || Use.isReady();
213       }))
214     return false;
215 
216   // A partial register write cannot complete before a dependent write.
217   if (!all_of(getDefs(),
218               [](const WriteState &Def) { return !Def.getDependentWrite(); }))
219     return false;
220 
221   Stage = IS_PENDING;
222   return true;
223 }
224 
225 void Instruction::update() {
226   if (isDispatched())
227     updateDispatched();
228   if (isPending())
229     updatePending();
230 }
231 
232 void Instruction::cycleEvent() {
233   if (isReady())
234     return;
235 
236   if (isDispatched() || isPending()) {
237     for (ReadState &Use : getUses())
238       Use.cycleEvent();
239 
240     for (WriteState &Def : getDefs())
241       Def.cycleEvent();
242 
243     update();
244     return;
245   }
246 
247   assert(isExecuting() && "Instruction not in-flight?");
248   assert(CyclesLeft && "Instruction already executed?");
249   for (WriteState &Def : getDefs())
250     Def.cycleEvent();
251   CyclesLeft--;
252   if (!CyclesLeft)
253     Stage = IS_EXECUTED;
254 }
255 
256 } // namespace mca
257 } // namespace llvm
258