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
18namespace llvm {
19namespace mca {
20
21void 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
30void 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
54void 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
72void 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
85void 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
96void 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
107void 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
125void WriteState::dump() const {
126  dbgs() << "{ OpIdx=" << WD->OpIndex << ", Lat=" << getLatency() << ", RegID "
127         << getRegisterID() << ", Cycles Left=" << getCyclesLeft() << " }";
128}
129#endif
130
131const 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
151void 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
163void 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
173void 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
188void Instruction::forceExecuted() {
189  assert(Stage == IS_READY && "Invalid internal state!");
190  CyclesLeft = 0;
191  Stage = IS_EXECUTED;
192}
193
194bool 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
208bool 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
225void Instruction::update() {
226  if (isDispatched())
227    updateDispatched();
228  if (isPending())
229    updatePending();
230}
231
232void 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