1 //===---------------------- InOrderIssueStage.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 /// InOrderIssueStage implements an in-order execution pipeline.
11 ///
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/MCA/Stages/InOrderIssueStage.h"
15 #include "llvm/MCA/HardwareUnits/RegisterFile.h"
16 #include "llvm/MCA/HardwareUnits/RetireControlUnit.h"
17 #include "llvm/MCA/Instruction.h"
18 
19 #define DEBUG_TYPE "llvm-mca"
20 namespace llvm {
21 namespace mca {
22 
23 void StallInfo::clear() {
24   IR.invalidate();
25   CyclesLeft = 0;
26   Kind = StallKind::DEFAULT;
27 }
28 
29 void StallInfo::update(const InstRef &Inst, unsigned Cycles, StallKind SK) {
30   IR = Inst;
31   CyclesLeft = Cycles;
32   Kind = SK;
33 }
34 
35 void StallInfo::cycleEnd() {
36   if (!isValid())
37     return;
38 
39   if (!CyclesLeft)
40     return;
41 
42   --CyclesLeft;
43 }
44 
45 InOrderIssueStage::InOrderIssueStage(const MCSubtargetInfo &STI,
46                                      RegisterFile &PRF, CustomBehaviour &CB)
47     : STI(STI), PRF(PRF), RM(STI.getSchedModel()), CB(CB), NumIssued(), SI(),
48       CarryOver(), Bandwidth(), LastWriteBackCycle() {}
49 
50 unsigned InOrderIssueStage::getIssueWidth() const {
51   return STI.getSchedModel().IssueWidth;
52 }
53 
54 bool InOrderIssueStage::hasWorkToComplete() const {
55   return !IssuedInst.empty() || SI.isValid() || CarriedOver;
56 }
57 
58 bool InOrderIssueStage::isAvailable(const InstRef &IR) const {
59   if (SI.isValid() || CarriedOver)
60     return false;
61 
62   const Instruction &Inst = *IR.getInstruction();
63   unsigned NumMicroOps = Inst.getNumMicroOps();
64   const InstrDesc &Desc = Inst.getDesc();
65 
66   bool ShouldCarryOver = NumMicroOps > getIssueWidth();
67   if (Bandwidth < NumMicroOps && !ShouldCarryOver)
68     return false;
69 
70   // Instruction with BeginGroup must be the first instruction to be issued in a
71   // cycle.
72   if (Desc.BeginGroup && NumIssued != 0)
73     return false;
74 
75   return true;
76 }
77 
78 static bool hasResourceHazard(const ResourceManager &RM, const InstRef &IR) {
79   if (RM.checkAvailability(IR.getInstruction()->getDesc())) {
80     LLVM_DEBUG(dbgs() << "[E] Stall #" << IR << '\n');
81     return true;
82   }
83 
84   return false;
85 }
86 
87 static unsigned findFirstWriteBackCycle(const InstRef &IR) {
88   unsigned FirstWBCycle = IR.getInstruction()->getLatency();
89   for (const WriteState &WS : IR.getInstruction()->getDefs()) {
90     int CyclesLeft = WS.getCyclesLeft();
91     if (CyclesLeft == UNKNOWN_CYCLES)
92       CyclesLeft = WS.getLatency();
93     if (CyclesLeft < 0)
94       CyclesLeft = 0;
95     FirstWBCycle = std::min(FirstWBCycle, (unsigned)CyclesLeft);
96   }
97   return FirstWBCycle;
98 }
99 
100 /// Return a number of cycles left until register requirements of the
101 /// instructions are met.
102 static unsigned checkRegisterHazard(const RegisterFile &PRF,
103                                     const MCSubtargetInfo &STI,
104                                     const InstRef &IR) {
105   for (const ReadState &RS : IR.getInstruction()->getUses()) {
106     RegisterFile::RAWHazard Hazard = PRF.checkRAWHazards(STI, RS);
107     if (Hazard.isValid())
108       return Hazard.hasUnknownCycles() ? 1U : Hazard.CyclesLeft;
109   }
110 
111   return 0;
112 }
113 
114 bool InOrderIssueStage::canExecute(const InstRef &IR) {
115   assert(!SI.getCyclesLeft() && "Should not have reached this code!");
116   assert(!SI.isValid() && "Should not have reached this code!");
117 
118   if (unsigned Cycles = checkRegisterHazard(PRF, STI, IR)) {
119     SI.update(IR, Cycles, StallInfo::StallKind::REGISTER_DEPS);
120     return false;
121   }
122 
123   if (hasResourceHazard(RM, IR)) {
124     SI.update(IR, /* delay */ 1, StallInfo::StallKind::DISPATCH);
125     return false;
126   }
127 
128   if (unsigned CustomStallCycles = CB.checkCustomHazard(IssuedInst, IR)) {
129     SI.update(IR, CustomStallCycles, StallInfo::StallKind::CUSTOM_STALL);
130     return false;
131   }
132 
133   if (LastWriteBackCycle) {
134     if (!IR.getInstruction()->getDesc().RetireOOO) {
135       unsigned NextWriteBackCycle = findFirstWriteBackCycle(IR);
136       // Delay the instruction to ensure that writes happen in program order.
137       if (NextWriteBackCycle < LastWriteBackCycle) {
138         SI.update(IR, LastWriteBackCycle - NextWriteBackCycle,
139                   StallInfo::StallKind::DELAY);
140         return false;
141       }
142     }
143   }
144 
145   return true;
146 }
147 
148 static void addRegisterReadWrite(RegisterFile &PRF, Instruction &IS,
149                                  unsigned SourceIndex,
150                                  const MCSubtargetInfo &STI,
151                                  SmallVectorImpl<unsigned> &UsedRegs) {
152   assert(!IS.isEliminated());
153 
154   for (ReadState &RS : IS.getUses())
155     PRF.addRegisterRead(RS, STI);
156 
157   for (WriteState &WS : IS.getDefs())
158     PRF.addRegisterWrite(WriteRef(SourceIndex, &WS), UsedRegs);
159 }
160 
161 void InOrderIssueStage::notifyInstructionIssued(const InstRef &IR,
162                                                 ArrayRef<ResourceUse> UsedRes) {
163   notifyEvent<HWInstructionEvent>(
164       HWInstructionEvent(HWInstructionEvent::Ready, IR));
165   notifyEvent<HWInstructionEvent>(HWInstructionIssuedEvent(IR, UsedRes));
166 
167   LLVM_DEBUG(dbgs() << "[E] Issued #" << IR << "\n");
168 }
169 
170 void InOrderIssueStage::notifyInstructionDispatched(
171     const InstRef &IR, unsigned Ops, ArrayRef<unsigned> UsedRegs) {
172   notifyEvent<HWInstructionEvent>(
173       HWInstructionDispatchedEvent(IR, UsedRegs, Ops));
174 
175   LLVM_DEBUG(dbgs() << "[E] Dispatched #" << IR << "\n");
176 }
177 
178 void InOrderIssueStage::notifyInstructionExecuted(const InstRef &IR) {
179   notifyEvent<HWInstructionEvent>(
180       HWInstructionEvent(HWInstructionEvent::Executed, IR));
181   LLVM_DEBUG(dbgs() << "[E] Instruction #" << IR << " is executed\n");
182 }
183 
184 void InOrderIssueStage::notifyInstructionRetired(const InstRef &IR,
185                                                  ArrayRef<unsigned> FreedRegs) {
186   notifyEvent<HWInstructionEvent>(HWInstructionRetiredEvent(IR, FreedRegs));
187   LLVM_DEBUG(dbgs() << "[E] Retired #" << IR << " \n");
188 }
189 
190 llvm::Error InOrderIssueStage::execute(InstRef &IR) {
191   if (llvm::Error E = tryIssue(IR))
192     return E;
193 
194   if (SI.isValid())
195     notifyStallEvent();
196 
197   return llvm::ErrorSuccess();
198 }
199 
200 llvm::Error InOrderIssueStage::tryIssue(InstRef &IR) {
201   Instruction &IS = *IR.getInstruction();
202   unsigned SourceIndex = IR.getSourceIndex();
203   const InstrDesc &Desc = IS.getDesc();
204 
205   if (!canExecute(IR)) {
206     LLVM_DEBUG(dbgs() << "[N] Stalled #" << SI.getInstruction() << " for "
207                       << SI.getCyclesLeft() << " cycles\n");
208     Bandwidth = 0;
209     return llvm::ErrorSuccess();
210   }
211 
212   unsigned RCUTokenID = RetireControlUnit::UnhandledTokenID;
213   IS.dispatch(RCUTokenID);
214 
215   SmallVector<unsigned, 4> UsedRegs(PRF.getNumRegisterFiles());
216   addRegisterReadWrite(PRF, IS, SourceIndex, STI, UsedRegs);
217 
218   unsigned NumMicroOps = IS.getNumMicroOps();
219   notifyInstructionDispatched(IR, NumMicroOps, UsedRegs);
220 
221   SmallVector<ResourceUse, 4> UsedResources;
222   RM.issueInstruction(Desc, UsedResources);
223   IS.execute(SourceIndex);
224 
225   // Replace resource masks with valid resource processor IDs.
226   for (ResourceUse &Use : UsedResources) {
227     uint64_t Mask = Use.first.first;
228     Use.first.first = RM.resolveResourceMask(Mask);
229   }
230   notifyInstructionIssued(IR, UsedResources);
231 
232   bool ShouldCarryOver = NumMicroOps > Bandwidth;
233   if (ShouldCarryOver) {
234     CarryOver = NumMicroOps - Bandwidth;
235     CarriedOver = IR;
236     Bandwidth = 0;
237     NumIssued += Bandwidth;
238     LLVM_DEBUG(dbgs() << "[N] Carry over #" << IR << " \n");
239   } else {
240     NumIssued += NumMicroOps;
241     Bandwidth = Desc.EndGroup ? 0 : Bandwidth - NumMicroOps;
242   }
243 
244   // If the instruction has a latency of 0, we need to handle
245   // the execution and retirement now.
246   if (IS.isExecuted()) {
247     PRF.onInstructionExecuted(&IS);
248     notifyEvent<HWInstructionEvent>(
249         HWInstructionEvent(HWInstructionEvent::Executed, IR));
250     LLVM_DEBUG(dbgs() << "[E] Instruction #" << IR << " is executed\n");
251 
252     retireInstruction(IR);
253     return llvm::ErrorSuccess();
254   }
255 
256   IssuedInst.push_back(IR);
257 
258   if (!IR.getInstruction()->getDesc().RetireOOO)
259     LastWriteBackCycle = IS.getCyclesLeft();
260 
261   return llvm::ErrorSuccess();
262 }
263 
264 void InOrderIssueStage::updateIssuedInst() {
265   // Update other instructions. Executed instructions will be retired during the
266   // next cycle.
267   unsigned NumExecuted = 0;
268   for (auto I = IssuedInst.begin(), E = IssuedInst.end();
269        I != (E - NumExecuted);) {
270     InstRef &IR = *I;
271     Instruction &IS = *IR.getInstruction();
272 
273     IS.cycleEvent();
274     if (!IS.isExecuted()) {
275       LLVM_DEBUG(dbgs() << "[N] Instruction #" << IR
276                         << " is still executing\n");
277       ++I;
278       continue;
279     }
280 
281     PRF.onInstructionExecuted(&IS);
282     notifyInstructionExecuted(IR);
283     ++NumExecuted;
284 
285     retireInstruction(*I);
286 
287     std::iter_swap(I, E - NumExecuted);
288   }
289 
290   if (NumExecuted)
291     IssuedInst.resize(IssuedInst.size() - NumExecuted);
292 }
293 
294 void InOrderIssueStage::updateCarriedOver() {
295   if (!CarriedOver)
296     return;
297 
298   assert(!SI.isValid() && "A stalled instruction cannot be carried over.");
299 
300   if (CarryOver > Bandwidth) {
301     CarryOver -= Bandwidth;
302     Bandwidth = 0;
303     LLVM_DEBUG(dbgs() << "[N] Carry over (" << CarryOver << "uops left) #"
304                       << CarriedOver << " \n");
305     return;
306   }
307 
308   LLVM_DEBUG(dbgs() << "[N] Carry over (complete) #" << CarriedOver << " \n");
309 
310   if (CarriedOver.getInstruction()->getDesc().EndGroup)
311     Bandwidth = 0;
312   else
313     Bandwidth -= CarryOver;
314 
315   CarriedOver = InstRef();
316   CarryOver = 0;
317 }
318 
319 void InOrderIssueStage::retireInstruction(InstRef &IR) {
320   Instruction &IS = *IR.getInstruction();
321   IS.retire();
322 
323   llvm::SmallVector<unsigned, 4> FreedRegs(PRF.getNumRegisterFiles());
324   for (const WriteState &WS : IS.getDefs())
325     PRF.removeRegisterWrite(WS, FreedRegs);
326 
327   notifyInstructionRetired(IR, FreedRegs);
328 }
329 
330 void InOrderIssueStage::notifyStallEvent() {
331   assert(SI.getCyclesLeft() && "A zero cycles stall?");
332   assert(SI.isValid() && "Invalid stall information found!");
333 
334   const InstRef &IR = SI.getInstruction();
335 
336   switch (SI.getStallKind()) {
337   default:
338     break;
339   case StallInfo::StallKind::REGISTER_DEPS: {
340     notifyEvent<HWStallEvent>(
341         HWStallEvent(HWStallEvent::RegisterFileStall, IR));
342     notifyEvent<HWPressureEvent>(
343         HWPressureEvent(HWPressureEvent::REGISTER_DEPS, IR));
344     break;
345   }
346   case StallInfo::StallKind::DISPATCH: {
347     notifyEvent<HWStallEvent>(
348         HWStallEvent(HWStallEvent::DispatchGroupStall, IR));
349     notifyEvent<HWPressureEvent>(
350         HWPressureEvent(HWPressureEvent::RESOURCES, IR));
351     break;
352   }
353   case StallInfo::StallKind::CUSTOM_STALL: {
354     notifyEvent<HWStallEvent>(
355         HWStallEvent(HWStallEvent::CustomBehaviourStall, IR));
356     break;
357   }
358   }
359 }
360 
361 llvm::Error InOrderIssueStage::cycleStart() {
362   NumIssued = 0;
363   Bandwidth = getIssueWidth();
364 
365   PRF.cycleStart();
366 
367   // Release consumed resources.
368   SmallVector<ResourceRef, 4> Freed;
369   RM.cycleEvent(Freed);
370 
371   updateIssuedInst();
372 
373   // Continue to issue the instruction carried over from the previous cycle
374   updateCarriedOver();
375 
376   // Issue instructions scheduled for this cycle
377   if (SI.isValid()) {
378     if (!SI.getCyclesLeft()) {
379       // Make a copy of the reference, and try issue it again.
380       // Do not take the instruction reference because SI.clear() will
381       // invalidate it.
382       InstRef IR = SI.getInstruction();
383       SI.clear();
384 
385       if (llvm::Error E = tryIssue(IR))
386         return E;
387     }
388 
389     if (SI.getCyclesLeft()) {
390       // The instruction is still stalled, cannot issue any new instructions in
391       // this cycle.
392       notifyStallEvent();
393       Bandwidth = 0;
394       return llvm::ErrorSuccess();
395     }
396   }
397 
398   assert((NumIssued <= getIssueWidth()) && "Overflow.");
399   return llvm::ErrorSuccess();
400 }
401 
402 llvm::Error InOrderIssueStage::cycleEnd() {
403   PRF.cycleEnd();
404   SI.cycleEnd();
405 
406   if (LastWriteBackCycle > 0)
407     --LastWriteBackCycle;
408 
409   return llvm::ErrorSuccess();
410 }
411 
412 } // namespace mca
413 } // namespace llvm
414