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