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
211
212
213
214
215
216
217
218
219
|
// SPDX-License-Identifier: GPL-3.0-or-later
#include "rcc/CodeGen/ScheduleHazardRecognizer.h"
#include "rcc/CodeGen/ScheduleDAG.h"
#include "rcc/CodeGen/TargetSchedulingModel.h"
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <optional>
#include <utility>
namespace rcc {
namespace {
[[nodiscard]] std::uint64_t saturatingAdd(std::uint64_t Left, std::uint64_t Right) noexcept {
return std::numeric_limits<std::uint64_t>::max() - Left < Right
? std::numeric_limits<std::uint64_t>::max()
: Left + Right;
}
} // namespace
Expected<ScheduleHazardRecognizer>
ScheduleHazardRecognizer::create(const TargetSchedulingModel &Model, ScheduleDirection Direction) {
ScheduleHazardRecognizer Result(Model, Direction);
Result.TargetHazards = Model.hooks().createHazardRecognizer(Direction);
auto Reset = Result.reset();
if (!Reset)
return std::unexpected(Reset.error());
return Result;
}
ScheduleHazardRecognizer::ScheduleHazardRecognizer(const ScheduleHazardRecognizer &Other)
: Model(Other.Model), Direction(Other.Direction),
TargetHazards(Other.TargetHazards ? Other.TargetHazards->clone() : nullptr),
Resources(Other.Resources), ResourceIndexes(Other.ResourceIndexes),
CurrentCycle(Other.CurrentCycle), DispatchAvailableAt(Other.DispatchAvailableAt),
IssuedMicroOps(Other.IssuedMicroOps), DispatchedUnits(Other.DispatchedUnits) {}
ScheduleHazardRecognizer &
ScheduleHazardRecognizer::operator=(const ScheduleHazardRecognizer &Other) {
if (this == &Other)
return *this;
Model = Other.Model;
Direction = Other.Direction;
TargetHazards = Other.TargetHazards ? Other.TargetHazards->clone() : nullptr;
Resources = Other.Resources;
ResourceIndexes = Other.ResourceIndexes;
CurrentCycle = Other.CurrentCycle;
DispatchAvailableAt = Other.DispatchAvailableAt;
IssuedMicroOps = Other.IssuedMicroOps;
DispatchedUnits = Other.DispatchedUnits;
return *this;
}
Expected<void> ScheduleHazardRecognizer::reset() {
Resources.clear();
ResourceIndexes.clear();
Resources.reserve(Model->processorResources().size());
for (const ProcessorResourceDesc &Resource : Model->processorResources()) {
ResourceIndexes.emplace(Resource.ID, Resources.size());
Resources.push_back({Resource.ID, std::vector<std::uint64_t>(Resource.Units, 0)});
}
CurrentCycle = 0;
DispatchAvailableAt = 0;
IssuedMicroOps = 0;
DispatchedUnits = 0;
if (TargetHazards != nullptr) {
auto Reset = TargetHazards->reset();
if (!Reset)
return std::unexpected(Reset.error());
}
return {};
}
Expected<bool> ScheduleHazardRecognizer::canIssue(const ScheduleUnit &Unit,
std::uint64_t Cycle) const {
ScheduleHazardRecognizer Trial = *this;
auto Issued = Trial.issueImplementation(Unit, Cycle);
if (!Issued) {
if (Issued.error().code() == ErrorCode::SchedulingFailed)
return false;
return std::unexpected(Issued.error());
}
return true;
}
Expected<std::uint64_t> ScheduleHazardRecognizer::earliestIssueCycle(const ScheduleUnit &Unit,
std::uint64_t Earliest) const {
std::uint64_t Candidate = std::max(Earliest, CurrentCycle);
for (;;) {
auto Available = canIssue(Unit, Candidate);
if (!Available)
return std::unexpected(Available.error());
if (*Available)
return Candidate;
if (Candidate == std::numeric_limits<std::uint64_t>::max()) {
return makeUnexpected(ErrorCode::SchedulingFailed,
"scheduler resource timeline is exhausted");
}
++Candidate;
}
}
Expected<void> ScheduleHazardRecognizer::issue(const ScheduleUnit &Unit, std::uint64_t Cycle) {
ScheduleHazardRecognizer Trial = *this;
auto Issued = Trial.issueImplementation(Unit, Cycle);
if (!Issued)
return std::unexpected(Issued.error());
*this = std::move(Trial);
return {};
}
Expected<void> ScheduleHazardRecognizer::issueImplementation(const ScheduleUnit &Unit,
std::uint64_t Cycle) {
if (Cycle < CurrentCycle) {
return makeUnexpected(ErrorCode::InvalidArgument,
"scheduler cannot issue into an earlier cycle");
}
auto Moved = moveToCycle(Cycle);
if (!Moved)
return std::unexpected(Moved.error());
if (Cycle < DispatchAvailableAt) {
return makeUnexpected(ErrorCode::SchedulingFailed, "scheduler dispatch pipeline is occupied");
}
if (TargetHazards != nullptr) {
auto Hazard = TargetHazards->getHazardType(Unit);
if (!Hazard)
return std::unexpected(Hazard.error());
if (*Hazard != ScheduleHazardType::NoHazard) {
return makeUnexpected(ErrorCode::SchedulingFailed,
*Hazard == ScheduleHazardType::NoopHazard
? "target hazard requires an unavailable scheduling noop"
: "target dynamic scheduling hazard prevents issue");
}
}
const std::uint32_t Width = Model->issueWidth();
if (Unit.MicroOps <= Width) {
if (Unit.MicroOps > Width - IssuedMicroOps || DispatchedUnits == Model->dispatchLimit()) {
return makeUnexpected(ErrorCode::SchedulingFailed,
"scheduler issue or dispatch width is exhausted");
}
IssuedMicroOps += Unit.MicroOps;
++DispatchedUnits;
} else {
if (IssuedMicroOps != 0 || DispatchedUnits != 0) {
return makeUnexpected(ErrorCode::SchedulingFailed,
"multi-cycle dispatch requires an empty issue cycle");
}
const std::uint64_t DispatchCycles =
(static_cast<std::uint64_t>(Unit.MicroOps) + Width - 1U) / Width;
DispatchAvailableAt = saturatingAdd(Cycle, DispatchCycles);
IssuedMicroOps = Width;
DispatchedUnits = 1;
}
for (const SchedulingResourceUse &Use : Unit.Resources) {
auto Reserved = reserveResource(Use.Resource, Use.Cycles, Cycle);
if (!Reserved)
return std::unexpected(Reserved.error());
}
if (TargetHazards != nullptr) {
auto Emitted = TargetHazards->emitInstruction(Unit);
if (!Emitted)
return std::unexpected(Emitted.error());
}
return {};
}
Expected<void> ScheduleHazardRecognizer::moveToCycle(std::uint64_t Cycle) {
while (CurrentCycle < Cycle) {
if (TargetHazards != nullptr) {
Expected<void> Advanced = Direction == ScheduleDirection::TopDown
? TargetHazards->advanceCycle()
: TargetHazards->recedeCycle();
if (!Advanced)
return std::unexpected(Advanced.error());
}
++CurrentCycle;
IssuedMicroOps = 0;
DispatchedUnits = 0;
}
return {};
}
Expected<void> ScheduleHazardRecognizer::reserveResource(ProcessorResourceID Resource,
std::uint32_t Cycles,
std::uint64_t Cycle) {
const auto Position = ResourceIndexes.find(Resource);
const ProcessorResourceDesc *Description = Model->processorResource(Resource);
if (Position == ResourceIndexes.end() || Description == nullptr || Cycles == 0) {
return makeUnexpected(ErrorCode::VerificationError,
"schedule unit references an invalid processor resource");
}
ResourceState &State = Resources[Position->second];
std::optional<std::size_t> Selected;
for (std::size_t Index = 0; Index < State.AvailableAt.size(); ++Index) {
if (State.AvailableAt[Index] <= Cycle &&
(!Selected || State.AvailableAt[Index] < State.AvailableAt[*Selected])) {
Selected = Index;
}
}
if (!Selected) {
return makeUnexpected(ErrorCode::SchedulingFailed, "processor resource has no available unit");
}
State.AvailableAt[*Selected] = saturatingAdd(Cycle, Cycles);
if (Description->Parent) {
auto Parent = reserveResource(*Description->Parent, Cycles, Cycle);
if (!Parent)
return std::unexpected(Parent.error());
}
return {};
}
} // namespace rcc
|
