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
25namespace llvm {
26namespace mca {
27
28DispatchStage::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
38void 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
46bool 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
62bool 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
71bool DispatchStage::canDispatch(const InstRef &IR) const {
72  bool CanDispatch = checkRCU(IR);
73  CanDispatch &= checkPRF(IR);
74  CanDispatch &= checkNextStage(IR);
75  return CanDispatch;
76}
77
78Error 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
138Error 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
158bool 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
175Error DispatchStage::execute(InstRef &IR) {
176  assert(canDispatch(IR) && "Cannot dispatch another instruction!");
177  return dispatch(IR);
178}
179
180#ifndef NDEBUG
181void DispatchStage::dump() const {
182  PRF.dump();
183  RCU.dump();
184}
185#endif
186} // namespace mca
187} // namespace llvm
188