1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
|
//===---------------------- ExecuteStage.cpp --------------------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
/// \file
///
/// This file defines the execution stage of an instruction pipeline.
///
/// The ExecuteStage is responsible for managing the hardware scheduler
/// and issuing notifications that an instruction has been executed.
///
//===----------------------------------------------------------------------===//
#include "ExecuteStage.h"
#include "Scheduler.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Debug.h"
#define DEBUG_TYPE "llvm-mca"
namespace mca {
using namespace llvm;
// Reclaim the simulated resources used by the scheduler.
void ExecuteStage::reclaimSchedulerResources() {
SmallVector<ResourceRef, 8> ResourcesFreed;
HWS.reclaimSimulatedResources(ResourcesFreed);
for (const ResourceRef &RR : ResourcesFreed)
notifyResourceAvailable(RR);
}
// Update the scheduler's instruction queues.
void ExecuteStage::updateSchedulerQueues() {
SmallVector<InstRef, 4> InstructionIDs;
HWS.updateIssuedQueue(InstructionIDs);
for (const InstRef &IR : InstructionIDs)
notifyInstructionExecuted(IR);
InstructionIDs.clear();
HWS.updatePendingQueue(InstructionIDs);
for (const InstRef &IR : InstructionIDs)
notifyInstructionReady(IR);
}
// Issue instructions that are waiting in the scheduler's ready queue.
void ExecuteStage::issueReadyInstructions() {
SmallVector<InstRef, 4> InstructionIDs;
InstRef IR = HWS.select();
while (IR.isValid()) {
SmallVector<std::pair<ResourceRef, double>, 4> Used;
HWS.issueInstruction(IR, Used);
// Reclaim instruction resources and perform notifications.
const InstrDesc &Desc = IR.getInstruction()->getDesc();
notifyReleasedBuffers(Desc.Buffers);
notifyInstructionIssued(IR, Used);
if (IR.getInstruction()->isExecuted())
notifyInstructionExecuted(IR);
// Instructions that have been issued during this cycle might have unblocked
// other dependent instructions. Dependent instructions may be issued during
// this same cycle if operands have ReadAdvance entries. Promote those
// instructions to the ReadyQueue and tell to the caller that we need
// another round of 'issue()'.
HWS.promoteToReadyQueue(InstructionIDs);
for (const InstRef &I : InstructionIDs)
notifyInstructionReady(I);
InstructionIDs.clear();
// Select the next instruction to issue.
IR = HWS.select();
}
}
// The following routine is the maintenance routine of the ExecuteStage.
// It is responsible for updating the hardware scheduler (HWS), including
// reclaiming the HWS's simulated hardware resources, as well as updating the
// HWS's queues.
//
// This routine also processes the instructions that are ready for issuance.
// These instructions are managed by the HWS's ready queue and can be accessed
// via the Scheduler::select() routine.
//
// Notifications are issued to this stage's listeners when instructions are
// moved between the HWS's queues. In particular, when an instruction becomes
// ready or executed.
void ExecuteStage::cycleStart() {
reclaimSchedulerResources();
updateSchedulerQueues();
issueReadyInstructions();
}
// Schedule the instruction for execution on the hardware.
bool ExecuteStage::execute(InstRef &IR) {
#ifndef NDEBUG
// Ensure that the HWS has not stored this instruction in its queues.
HWS.sanityCheck(IR);
#endif
// Reserve a slot in each buffered resource. Also, mark units with
// BufferSize=0 as reserved. Resources with a buffer size of zero will only
// be released after MCIS is issued, and all the ResourceCycles for those
// units have been consumed.
const InstrDesc &Desc = IR.getInstruction()->getDesc();
HWS.reserveBuffers(Desc.Buffers);
notifyReservedBuffers(Desc.Buffers);
// Obtain a slot in the LSU. If we cannot reserve resources, return true, so
// that succeeding stages can make progress.
if (!HWS.reserveResources(IR))
return true;
// If we did not return early, then the scheduler is ready for execution.
notifyInstructionReady(IR);
// Don't add a zero-latency instruction to the Wait or Ready queue.
// A zero-latency instruction doesn't consume any scheduler resources. That is
// because it doesn't need to be executed, and it is often removed at register
// renaming stage. For example, register-register moves are often optimized at
// register renaming stage by simply updating register aliases. On some
// targets, zero-idiom instructions (for example: a xor that clears the value
// of a register) are treated specially, and are often eliminated at register
// renaming stage.
//
// Instructions that use an in-order dispatch/issue processor resource must be
// issued immediately to the pipeline(s). Any other in-order buffered
// resources (i.e. BufferSize=1) is consumed.
//
// If we cannot issue immediately, the HWS will add IR to its ready queue for
// execution later, so we must return early here.
if (!HWS.issueImmediately(IR))
return true;
LLVM_DEBUG(dbgs() << "[SCHEDULER] Instruction #" << IR
<< " issued immediately\n");
// Issue IR. The resources for this issuance will be placed in 'Used.'
SmallVector<std::pair<ResourceRef, double>, 4> Used;
HWS.issueInstruction(IR, Used);
// Perform notifications.
notifyReleasedBuffers(Desc.Buffers);
notifyInstructionIssued(IR, Used);
if (IR.getInstruction()->isExecuted())
notifyInstructionExecuted(IR);
return true;
}
void ExecuteStage::notifyInstructionExecuted(const InstRef &IR) {
HWS.onInstructionExecuted(IR);
LLVM_DEBUG(dbgs() << "[E] Instruction Executed: #" << IR << '\n');
notifyEvent<HWInstructionEvent>(
HWInstructionEvent(HWInstructionEvent::Executed, IR));
RCU.onInstructionExecuted(IR.getInstruction()->getRCUTokenID());
}
void ExecuteStage::notifyInstructionReady(const InstRef &IR) {
LLVM_DEBUG(dbgs() << "[E] Instruction Ready: #" << IR << '\n');
notifyEvent<HWInstructionEvent>(
HWInstructionEvent(HWInstructionEvent::Ready, IR));
}
void ExecuteStage::notifyResourceAvailable(const ResourceRef &RR) {
LLVM_DEBUG(dbgs() << "[E] Resource Available: [" << RR.first << '.'
<< RR.second << "]\n");
for (HWEventListener *Listener : getListeners())
Listener->onResourceAvailable(RR);
}
void ExecuteStage::notifyInstructionIssued(
const InstRef &IR, ArrayRef<std::pair<ResourceRef, double>> Used) {
LLVM_DEBUG({
dbgs() << "[E] Instruction Issued: #" << IR << '\n';
for (const std::pair<ResourceRef, unsigned> &Resource : Used) {
dbgs() << "[E] Resource Used: [" << Resource.first.first << '.'
<< Resource.first.second << "], ";
dbgs() << "cycles: " << Resource.second << '\n';
}
});
notifyEvent<HWInstructionEvent>(HWInstructionIssuedEvent(IR, Used));
}
void ExecuteStage::notifyReservedBuffers(ArrayRef<uint64_t> Buffers) {
if (Buffers.empty())
return;
SmallVector<unsigned, 4> BufferIDs(Buffers.begin(), Buffers.end());
std::transform(Buffers.begin(), Buffers.end(), BufferIDs.begin(),
[&](uint64_t Op) { return HWS.getResourceID(Op); });
for (HWEventListener *Listener : getListeners())
Listener->onReservedBuffers(BufferIDs);
}
void ExecuteStage::notifyReleasedBuffers(ArrayRef<uint64_t> Buffers) {
if (Buffers.empty())
return;
SmallVector<unsigned, 4> BufferIDs(Buffers.begin(), Buffers.end());
std::transform(Buffers.begin(), Buffers.end(), BufferIDs.begin(),
[&](uint64_t Op) { return HWS.getResourceID(Op); });
for (HWEventListener *Listener : getListeners())
Listener->onReleasedBuffers(BufferIDs);
}
} // namespace mca
|
