1 //===--------------------- DispatchStage.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 /// This file models the dispatch component of an instruction pipeline.
11 ///
12 /// The DispatchStage is responsible for updating instruction dependencies
13 /// and communicating to the simulated instruction scheduler that an instruction
14 /// is ready to be scheduled for execution.
15 ///
16 //===----------------------------------------------------------------------===//
17 
18 #include "llvm/MCA/Stages/DispatchStage.h"
19 #include "llvm/MCA/HWEventListener.h"
20 #include "llvm/MCA/HardwareUnits/Scheduler.h"
21 #include "llvm/Support/Debug.h"
22 
23 #define DEBUG_TYPE "llvm-mca"
24 
25 namespace llvm {
26 namespace mca {
27 
28 DispatchStage::DispatchStage(const MCSubtargetInfo &Subtarget,
29                              const MCRegisterInfo &MRI,
30                              unsigned MaxDispatchWidth, RetireControlUnit &R,
31                              RegisterFile &F)
32     : DispatchWidth(MaxDispatchWidth), AvailableEntries(MaxDispatchWidth),
33       CarryOver(0U), CarriedOver(), STI(Subtarget), RCU(R), PRF(F) {
34   if (!DispatchWidth)
35     DispatchWidth = Subtarget.getSchedModel().IssueWidth;
36 }
37 
38 void DispatchStage::notifyInstructionDispatched(const InstRef &IR,
39                                                 ArrayRef<unsigned> UsedRegs,
40                                                 unsigned UOps) const {
41   LLVM_DEBUG(dbgs() << "[E] Instruction Dispatched: #" << IR << '\n');
42   notifyEvent<HWInstructionEvent>(
43       HWInstructionDispatchedEvent(IR, UsedRegs, UOps));
44 }
45 
46 bool DispatchStage::checkPRF(const InstRef &IR) const {
47   SmallVector<MCPhysReg, 4> RegDefs;
48   for (const WriteState &RegDef : IR.getInstruction()->getDefs())
49     RegDefs.emplace_back(RegDef.getRegisterID());
50 
51   const unsigned RegisterMask = PRF.isAvailable(RegDefs);
52   // A mask with all zeroes means: register files are available.
53   if (RegisterMask) {
54     notifyEvent<HWStallEvent>(
55         HWStallEvent(HWStallEvent::RegisterFileStall, IR));
56     return false;
57   }
58 
59   return true;
60 }
61 
62 bool DispatchStage::checkRCU(const InstRef &IR) const {
63   const unsigned NumMicroOps = IR.getInstruction()->getNumMicroOps();
64   if (RCU.isAvailable(NumMicroOps))
65     return true;
66   notifyEvent<HWStallEvent>(
67       HWStallEvent(HWStallEvent::RetireControlUnitStall, IR));
68   return false;
69 }
70 
71 bool DispatchStage::canDispatch(const InstRef &IR) const {
72   bool CanDispatch = checkRCU(IR);
73   CanDispatch &= checkPRF(IR);
74   CanDispatch &= checkNextStage(IR);
75   return CanDispatch;
76 }
77 
78 Error DispatchStage::dispatch(InstRef IR) {
79   assert(!CarryOver && "Cannot dispatch another instruction!");
80   Instruction &IS = *IR.getInstruction();
81   const InstrDesc &Desc = IS.getDesc();
82   const unsigned NumMicroOps = IS.getNumMicroOps();
83   if (NumMicroOps > DispatchWidth) {
84     assert(AvailableEntries == DispatchWidth);
85     AvailableEntries = 0;
86     CarryOver = NumMicroOps - DispatchWidth;
87     CarriedOver = IR;
88   } else {
89     assert(AvailableEntries >= NumMicroOps);
90     AvailableEntries -= NumMicroOps;
91   }
92 
93   // Check if this instructions ends the dispatch group.
94   if (Desc.EndGroup)
95     AvailableEntries = 0;
96 
97   // Check if this is an optimizable reg-reg move.
98   if (IS.isOptimizableMove()) {
99     assert(IS.getDefs().size() == 1 && "Expected a single input!");
100     assert(IS.getUses().size() == 1 && "Expected a single output!");
101     if (PRF.tryEliminateMove(IS.getDefs()[0], IS.getUses()[0]))
102       IS.setEliminated();
103   }
104 
105   // A dependency-breaking instruction doesn't have to wait on the register
106   // input operands, and it is often optimized at register renaming stage.
107   // Update RAW dependencies if this instruction is not a dependency-breaking
108   // instruction. A dependency-breaking instruction is a zero-latency
109   // instruction that doesn't consume hardware resources.
110   // An example of dependency-breaking instruction on X86 is a zero-idiom XOR.
111   //
112   // We also don't update data dependencies for instructions that have been
113   // eliminated at register renaming stage.
114   if (!IS.isEliminated()) {
115     for (ReadState &RS : IS.getUses())
116       PRF.addRegisterRead(RS, STI);
117   }
118 
119   // By default, a dependency-breaking zero-idiom is expected to be optimized
120   // at register renaming stage. That means, no physical register is allocated
121   // to the instruction.
122   SmallVector<unsigned, 4> RegisterFiles(PRF.getNumRegisterFiles());
123   for (WriteState &WS : IS.getDefs())
124     PRF.addRegisterWrite(WriteRef(IR.getSourceIndex(), &WS), RegisterFiles);
125 
126   // Reserve entries in the reorder buffer.
127   unsigned RCUTokenID = RCU.dispatch(IR);
128   // Notify the instruction that it has been dispatched.
129   IS.dispatch(RCUTokenID);
130 
131   // Notify listeners of the "instruction dispatched" event,
132   // and move IR to the next stage.
133   notifyInstructionDispatched(IR, RegisterFiles,
134                               std::min(DispatchWidth, NumMicroOps));
135   return moveToTheNextStage(IR);
136 }
137 
138 Error DispatchStage::cycleStart() {
139   PRF.cycleStart();
140 
141   if (!CarryOver) {
142     AvailableEntries = DispatchWidth;
143     return ErrorSuccess();
144   }
145 
146   AvailableEntries = CarryOver >= DispatchWidth ? 0 : DispatchWidth - CarryOver;
147   unsigned DispatchedOpcodes = DispatchWidth - AvailableEntries;
148   CarryOver -= DispatchedOpcodes;
149   assert(CarriedOver && "Invalid dispatched instruction");
150 
151   SmallVector<unsigned, 8> RegisterFiles(PRF.getNumRegisterFiles(), 0U);
152   notifyInstructionDispatched(CarriedOver, RegisterFiles, DispatchedOpcodes);
153   if (!CarryOver)
154     CarriedOver = InstRef();
155   return ErrorSuccess();
156 }
157 
158 bool DispatchStage::isAvailable(const InstRef &IR) const {
159   const Instruction &Inst = *IR.getInstruction();
160   unsigned NumMicroOps = Inst.getNumMicroOps();
161   const InstrDesc &Desc = Inst.getDesc();
162   unsigned Required = std::min(NumMicroOps, DispatchWidth);
163   if (Required > AvailableEntries)
164     return false;
165 
166   if (Desc.BeginGroup && AvailableEntries != DispatchWidth)
167     return false;
168 
169   // The dispatch logic doesn't internally buffer instructions.  It only accepts
170   // instructions that can be successfully moved to the next stage during this
171   // same cycle.
172   return canDispatch(IR);
173 }
174 
175 Error DispatchStage::execute(InstRef &IR) {
176   assert(canDispatch(IR) && "Cannot dispatch another instruction!");
177   return dispatch(IR);
178 }
179 
180 #ifndef NDEBUG
181 void DispatchStage::dump() const {
182   PRF.dump();
183   RCU.dump();
184 }
185 #endif
186 } // namespace mca
187 } // namespace llvm
188