1 //===--------------------- Instruction.cpp ----------------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines abstractions used by the Pipeline to model register reads,
11 // register writes and instructions.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "llvm/MCA/Instruction.h"
16 #include "llvm/Support/Debug.h"
17 #include "llvm/Support/raw_ostream.h"
18 
19 namespace llvm {
20 namespace mca {
21 
22 void ReadState::writeStartEvent(unsigned Cycles) {
23   assert(DependentWrites);
24   assert(CyclesLeft == UNKNOWN_CYCLES);
25 
26   // This read may be dependent on more than one write. This typically occurs
27   // when a definition is the result of multiple writes where at least one
28   // write does a partial register update.
29   // The HW is forced to do some extra bookkeeping to track of all the
30   // dependent writes, and implement a merging scheme for the partial writes.
31   --DependentWrites;
32   TotalCycles = std::max(TotalCycles, Cycles);
33 
34   if (!DependentWrites) {
35     CyclesLeft = TotalCycles;
36     IsReady = !CyclesLeft;
37   }
38 }
39 
40 void WriteState::onInstructionIssued() {
41   assert(CyclesLeft == UNKNOWN_CYCLES);
42   // Update the number of cycles left based on the WriteDescriptor info.
43   CyclesLeft = getLatency();
44 
45   // Now that the time left before write-back is known, notify
46   // all the users.
47   for (const std::pair<ReadState *, int> &User : Users) {
48     ReadState *RS = User.first;
49     unsigned ReadCycles = std::max(0, CyclesLeft - User.second);
50     RS->writeStartEvent(ReadCycles);
51   }
52 
53   // Notify any writes that are in a false dependency with this write.
54   if (PartialWrite)
55     PartialWrite->writeStartEvent(CyclesLeft);
56 }
57 
58 void WriteState::addUser(ReadState *User, int ReadAdvance) {
59   // If CyclesLeft is different than -1, then we don't need to
60   // update the list of users. We can just notify the user with
61   // the actual number of cycles left (which may be zero).
62   if (CyclesLeft != UNKNOWN_CYCLES) {
63     unsigned ReadCycles = std::max(0, CyclesLeft - ReadAdvance);
64     User->writeStartEvent(ReadCycles);
65     return;
66   }
67 
68   if (llvm::find_if(Users, [&User](const std::pair<ReadState *, int> &Use) {
69         return Use.first == User;
70       }) == Users.end()) {
71     Users.emplace_back(User, ReadAdvance);
72   }
73 }
74 
75 void WriteState::addUser(WriteState *User) {
76   if (CyclesLeft != UNKNOWN_CYCLES) {
77     User->writeStartEvent(std::max(0, CyclesLeft));
78     return;
79   }
80 
81   assert(!PartialWrite && "PartialWrite already set!");
82   PartialWrite = User;
83   User->setDependentWrite(this);
84 }
85 
86 void WriteState::cycleEvent() {
87   // Note: CyclesLeft can be a negative number. It is an error to
88   // make it an unsigned quantity because users of this write may
89   // specify a negative ReadAdvance.
90   if (CyclesLeft != UNKNOWN_CYCLES)
91     CyclesLeft--;
92 
93   if (DependentWriteCyclesLeft)
94     DependentWriteCyclesLeft--;
95 }
96 
97 void ReadState::cycleEvent() {
98   // Update the total number of cycles.
99   if (DependentWrites && TotalCycles) {
100     --TotalCycles;
101     return;
102   }
103 
104   // Bail out immediately if we don't know how many cycles are left.
105   if (CyclesLeft == UNKNOWN_CYCLES)
106     return;
107 
108   if (CyclesLeft) {
109     --CyclesLeft;
110     IsReady = !CyclesLeft;
111   }
112 }
113 
114 #ifndef NDEBUG
115 void WriteState::dump() const {
116   dbgs() << "{ OpIdx=" << WD->OpIndex << ", Lat=" << getLatency() << ", RegID "
117          << getRegisterID() << ", Cycles Left=" << getCyclesLeft() << " }";
118 }
119 
120 void WriteRef::dump() const {
121   dbgs() << "IID=" << getSourceIndex() << ' ';
122   if (isValid())
123     getWriteState()->dump();
124   else
125     dbgs() << "(null)";
126 }
127 #endif
128 
129 void Instruction::dispatch(unsigned RCUToken) {
130   assert(Stage == IS_INVALID);
131   Stage = IS_AVAILABLE;
132   RCUTokenID = RCUToken;
133 
134   // Check if input operands are already available.
135   update();
136 }
137 
138 void Instruction::execute() {
139   assert(Stage == IS_READY);
140   Stage = IS_EXECUTING;
141 
142   // Set the cycles left before the write-back stage.
143   CyclesLeft = getLatency();
144 
145   for (WriteState &WS : getDefs())
146     WS.onInstructionIssued();
147 
148   // Transition to the "executed" stage if this is a zero-latency instruction.
149   if (!CyclesLeft)
150     Stage = IS_EXECUTED;
151 }
152 
153 void Instruction::forceExecuted() {
154   assert(Stage == IS_READY && "Invalid internal state!");
155   CyclesLeft = 0;
156   Stage = IS_EXECUTED;
157 }
158 
159 void Instruction::update() {
160   assert(isDispatched() && "Unexpected instruction stage found!");
161 
162   if (!all_of(getUses(), [](const ReadState &Use) { return Use.isReady(); }))
163     return;
164 
165   // A partial register write cannot complete before a dependent write.
166   auto IsDefReady = [&](const WriteState &Def) {
167     if (!Def.getDependentWrite()) {
168       unsigned CyclesLeft = Def.getDependentWriteCyclesLeft();
169       return !CyclesLeft || CyclesLeft < getLatency();
170     }
171     return false;
172   };
173 
174   if (all_of(getDefs(), IsDefReady))
175     Stage = IS_READY;
176 }
177 
178 void Instruction::cycleEvent() {
179   if (isReady())
180     return;
181 
182   if (isDispatched()) {
183     for (ReadState &Use : getUses())
184       Use.cycleEvent();
185 
186     for (WriteState &Def : getDefs())
187       Def.cycleEvent();
188 
189     update();
190     return;
191   }
192 
193   assert(isExecuting() && "Instruction not in-flight?");
194   assert(CyclesLeft && "Instruction already executed?");
195   for (WriteState &Def : getDefs())
196     Def.cycleEvent();
197   CyclesLeft--;
198   if (!CyclesLeft)
199     Stage = IS_EXECUTED;
200 }
201 
202 const unsigned WriteRef::INVALID_IID = std::numeric_limits<unsigned>::max();
203 
204 } // namespace mca
205 } // namespace llvm
206