Bug Summary

File:llvm/lib/MCA/HardwareUnits/ResourceManager.cpp
Warning:line 369, column 29
The result of the left shift is undefined due to shifting by '4294967295', which is greater or equal to the width of type 'unsigned long long'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name ResourceManager.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/MCA -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/MCA -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/MCA -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include -D NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/MCA -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-09-04-040900-46481-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/MCA/HardwareUnits/ResourceManager.cpp

/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/MCA/HardwareUnits/ResourceManager.cpp

→
1//===--------------------- ResourceManager.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/// The classes here represent processor resource units and their management
11/// strategy. These classes are managed by the Scheduler.
12///
13//===----------------------------------------------------------------------===//
14
15#include "llvm/MCA/HardwareUnits/ResourceManager.h"
16#include "llvm/MCA/Support.h"
17#include "llvm/Support/Debug.h"
18#include "llvm/Support/raw_ostream.h"
19
20namespace llvm {
21namespace mca {
22
23#define DEBUG_TYPE"llvm-mca" "llvm-mca"
24ResourceStrategy::~ResourceStrategy() = default;
25
26static uint64_t selectImpl(uint64_t CandidateMask,
27 uint64_t &NextInSequenceMask) {
28 // The upper bit set in CandidateMask identifies our next candidate resource.
29 CandidateMask = 1ULL << getResourceStateIndex(CandidateMask);
30 NextInSequenceMask &= (CandidateMask | (CandidateMask - 1));
31 return CandidateMask;
32}
33
34uint64_t DefaultResourceStrategy::select(uint64_t ReadyMask) {
35 // This method assumes that ReadyMask cannot be zero.
36 uint64_t CandidateMask = ReadyMask & NextInSequenceMask;
37 if (CandidateMask)
38 return selectImpl(CandidateMask, NextInSequenceMask);
39
40 NextInSequenceMask = ResourceUnitMask ^ RemovedFromNextInSequence;
41 RemovedFromNextInSequence = 0;
42 CandidateMask = ReadyMask & NextInSequenceMask;
43 if (CandidateMask)
44 return selectImpl(CandidateMask, NextInSequenceMask);
45
46 NextInSequenceMask = ResourceUnitMask;
47 CandidateMask = ReadyMask & NextInSequenceMask;
48 return selectImpl(CandidateMask, NextInSequenceMask);
49}
50
51void DefaultResourceStrategy::used(uint64_t Mask) {
52 if (Mask > NextInSequenceMask) {
53 RemovedFromNextInSequence |= Mask;
54 return;
55 }
56
57 NextInSequenceMask &= (~Mask);
58 if (NextInSequenceMask)
59 return;
60
61 NextInSequenceMask = ResourceUnitMask ^ RemovedFromNextInSequence;
62 RemovedFromNextInSequence = 0;
63}
64
65ResourceState::ResourceState(const MCProcResourceDesc &Desc, unsigned Index,
66 uint64_t Mask)
67 : ProcResourceDescIndex(Index), ResourceMask(Mask),
68 BufferSize(Desc.BufferSize), IsAGroup(countPopulation(ResourceMask) > 1) {
69 if (IsAGroup) {
70 ResourceSizeMask =
71 ResourceMask ^ 1ULL << getResourceStateIndex(ResourceMask);
72 } else {
73 ResourceSizeMask = (1ULL << Desc.NumUnits) - 1;
74 }
75 ReadyMask = ResourceSizeMask;
76 AvailableSlots = BufferSize == -1 ? 0U : static_cast<unsigned>(BufferSize);
77 Unavailable = false;
78}
79
80bool ResourceState::isReady(unsigned NumUnits) const {
81 return (!isReserved() || isADispatchHazard()) &&
82 countPopulation(ReadyMask) >= NumUnits;
83}
84
85ResourceStateEvent ResourceState::isBufferAvailable() const {
86 if (isADispatchHazard() && isReserved())
87 return RS_RESERVED;
88 if (!isBuffered() || AvailableSlots)
89 return RS_BUFFER_AVAILABLE;
90 return RS_BUFFER_UNAVAILABLE;
91}
92
93#ifndef NDEBUG1
94void ResourceState::dump() const {
95 dbgs() << "MASK=" << format_hex(ResourceMask, 16)
96 << ", SZMASK=" << format_hex(ResourceSizeMask, 16)
97 << ", RDYMASK=" << format_hex(ReadyMask, 16)
98 << ", BufferSize=" << BufferSize
99 << ", AvailableSlots=" << AvailableSlots
100 << ", Reserved=" << Unavailable << '\n';
101}
102#endif
103
104static std::unique_ptr<ResourceStrategy>
105getStrategyFor(const ResourceState &RS) {
106 if (RS.isAResourceGroup() || RS.getNumUnits() > 1)
107 return std::make_unique<DefaultResourceStrategy>(RS.getReadyMask());
108 return std::unique_ptr<ResourceStrategy>(nullptr);
109}
110
111ResourceManager::ResourceManager(const MCSchedModel &SM)
112 : Resources(SM.getNumProcResourceKinds() - 1),
113 Strategies(SM.getNumProcResourceKinds() - 1),
114 Resource2Groups(SM.getNumProcResourceKinds() - 1, 0),
115 ProcResID2Mask(SM.getNumProcResourceKinds(), 0),
116 ResIndex2ProcResID(SM.getNumProcResourceKinds() - 1, 0),
117 ProcResUnitMask(0), ReservedResourceGroups(0), AvailableBuffers(~0ULL),
118 ReservedBuffers(0) {
119 computeProcResourceMasks(SM, ProcResID2Mask);
120
121 // initialize vector ResIndex2ProcResID.
122 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
123 unsigned Index = getResourceStateIndex(ProcResID2Mask[I]);
124 ResIndex2ProcResID[Index] = I;
125 }
126
127 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
128 uint64_t Mask = ProcResID2Mask[I];
129 unsigned Index = getResourceStateIndex(Mask);
130 Resources[Index] =
131 std::make_unique<ResourceState>(*SM.getProcResource(I), I, Mask);
132 Strategies[Index] = getStrategyFor(*Resources[Index]);
133 }
134
135 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
136 uint64_t Mask = ProcResID2Mask[I];
137 unsigned Index = getResourceStateIndex(Mask);
138 const ResourceState &RS = *Resources[Index];
139 if (!RS.isAResourceGroup()) {
140 ProcResUnitMask |= Mask;
141 continue;
142 }
143
144 uint64_t GroupMaskIdx = 1ULL << Index;
145 Mask -= GroupMaskIdx;
146 while (Mask) {
147 // Extract lowest set isolated bit.
148 uint64_t Unit = Mask & (-Mask);
149 unsigned IndexUnit = getResourceStateIndex(Unit);
150 Resource2Groups[IndexUnit] |= GroupMaskIdx;
151 Mask ^= Unit;
152 }
153 }
154
155 AvailableProcResUnits = ProcResUnitMask;
156}
157
158void ResourceManager::setCustomStrategyImpl(std::unique_ptr<ResourceStrategy> S,
159 uint64_t ResourceMask) {
160 unsigned Index = getResourceStateIndex(ResourceMask);
161 assert(Index < Resources.size() && "Invalid processor resource index!")(static_cast<void> (0));
162 assert(S && "Unexpected null strategy in input!")(static_cast<void> (0));
163 Strategies[Index] = std::move(S);
164}
165
166unsigned ResourceManager::resolveResourceMask(uint64_t Mask) const {
167 return ResIndex2ProcResID[getResourceStateIndex(Mask)];
168}
169
170unsigned ResourceManager::getNumUnits(uint64_t ResourceID) const {
171 return Resources[getResourceStateIndex(ResourceID)]->getNumUnits();
172}
173
174// Returns the actual resource consumed by this Use.
175// First, is the primary resource ID.
176// Second, is the specific sub-resource ID.
177ResourceRef ResourceManager::selectPipe(uint64_t ResourceID) {
178 unsigned Index = getResourceStateIndex(ResourceID);
179 assert(Index < Resources.size() && "Invalid resource use!")(static_cast<void> (0));
180 ResourceState &RS = *Resources[Index];
181 assert(RS.isReady() && "No available units to select!")(static_cast<void> (0));
182
183 // Special case where RS is not a group, and it only declares a single
184 // resource unit.
185 if (!RS.isAResourceGroup() && RS.getNumUnits() == 1)
186 return std::make_pair(ResourceID, RS.getReadyMask());
187
188 uint64_t SubResourceID = Strategies[Index]->select(RS.getReadyMask());
189 if (RS.isAResourceGroup())
190 return selectPipe(SubResourceID);
191 return std::make_pair(ResourceID, SubResourceID);
192}
193
194void ResourceManager::use(const ResourceRef &RR) {
195 // Mark the sub-resource referenced by RR as used.
196 unsigned RSID = getResourceStateIndex(RR.first);
197 ResourceState &RS = *Resources[RSID];
198 RS.markSubResourceAsUsed(RR.second);
199 // Remember to update the resource strategy for non-group resources with
200 // multiple units.
201 if (RS.getNumUnits() > 1)
202 Strategies[RSID]->used(RR.second);
203
204 // If there are still available units in RR.first,
205 // then we are done.
206 if (RS.isReady())
207 return;
208
209 AvailableProcResUnits ^= RR.first;
210
211 // Notify groups that RR.first is no longer available.
212 uint64_t Users = Resource2Groups[RSID];
213 while (Users) {
214 // Extract lowest set isolated bit.
215 unsigned GroupIndex = getResourceStateIndex(Users & (-Users));
216 ResourceState &CurrentUser = *Resources[GroupIndex];
217 CurrentUser.markSubResourceAsUsed(RR.first);
218 Strategies[GroupIndex]->used(RR.first);
219 // Reset lowest set bit.
220 Users &= Users - 1;
221 }
222}
223
224void ResourceManager::release(const ResourceRef &RR) {
225 unsigned RSID = getResourceStateIndex(RR.first);
226 ResourceState &RS = *Resources[RSID];
227 bool WasFullyUsed = !RS.isReady();
228 RS.releaseSubResource(RR.second);
229 if (!WasFullyUsed)
230 return;
231
232 AvailableProcResUnits ^= RR.first;
233
234 // Notify groups that RR.first is now available again.
235 uint64_t Users = Resource2Groups[RSID];
236 while (Users) {
237 unsigned GroupIndex = getResourceStateIndex(Users & (-Users));
238 ResourceState &CurrentUser = *Resources[GroupIndex];
239 CurrentUser.releaseSubResource(RR.first);
240 Users &= Users - 1;
241 }
242}
243
244ResourceStateEvent
245ResourceManager::canBeDispatched(uint64_t ConsumedBuffers) const {
246 if (ConsumedBuffers & ReservedBuffers)
247 return ResourceStateEvent::RS_RESERVED;
248 if (ConsumedBuffers & (~AvailableBuffers))
249 return ResourceStateEvent::RS_BUFFER_UNAVAILABLE;
250 return ResourceStateEvent::RS_BUFFER_AVAILABLE;
251}
252
253void ResourceManager::reserveBuffers(uint64_t ConsumedBuffers) {
254 while (ConsumedBuffers) {
255 uint64_t CurrentBuffer = ConsumedBuffers & (-ConsumedBuffers);
256 ResourceState &RS = *Resources[getResourceStateIndex(CurrentBuffer)];
257 ConsumedBuffers ^= CurrentBuffer;
258 assert(RS.isBufferAvailable() == ResourceStateEvent::RS_BUFFER_AVAILABLE)(static_cast<void> (0));
259 if (!RS.reserveBuffer())
260 AvailableBuffers ^= CurrentBuffer;
261 if (RS.isADispatchHazard()) {
262 // Reserve this buffer now, and release it once pipeline resources
263 // consumed by the instruction become available again.
264 // We do this to simulate an in-order dispatch/issue of instructions.
265 ReservedBuffers ^= CurrentBuffer;
266 }
267 }
268}
269
270void ResourceManager::releaseBuffers(uint64_t ConsumedBuffers) {
271 AvailableBuffers |= ConsumedBuffers;
272 while (ConsumedBuffers) {
273 uint64_t CurrentBuffer = ConsumedBuffers & (-ConsumedBuffers);
274 ResourceState &RS = *Resources[getResourceStateIndex(CurrentBuffer)];
275 ConsumedBuffers ^= CurrentBuffer;
276 RS.releaseBuffer();
277 // Do not unreserve dispatch hazard resource buffers. Wait until all
278 // pipeline resources have been freed too.
279 }
280}
281
282uint64_t ResourceManager::checkAvailability(const InstrDesc &Desc) const {
283 uint64_t BusyResourceMask = 0;
284 for (const std::pair<uint64_t, ResourceUsage> &E : Desc.Resources) {
285 unsigned NumUnits = E.second.isReserved() ? 0U : E.second.NumUnits;
286 unsigned Index = getResourceStateIndex(E.first);
287 if (!Resources[Index]->isReady(NumUnits))
288 BusyResourceMask |= E.first;
289 }
290
291 uint64_t ImplicitUses = Desc.ImplicitlyUsedProcResUnits;
292 while (ImplicitUses) {
293 uint64_t Use = ImplicitUses & -ImplicitUses;
294 ImplicitUses ^= Use;
295 unsigned Index = getResourceStateIndex(Use);
296 if (!Resources[Index]->isReady(/* NumUnits */ 1))
297 BusyResourceMask |= Index;
298 }
299
300 BusyResourceMask &= ProcResUnitMask;
301 if (BusyResourceMask)
302 return BusyResourceMask;
303 return Desc.UsedProcResGroups & ReservedResourceGroups;
304}
305
306void ResourceManager::issueInstruction(
307 const InstrDesc &Desc,
308 SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Pipes) {
309 for (const std::pair<uint64_t, ResourceUsage> &R : Desc.Resources) {
1
Assuming '__begin2' is not equal to '__end2'
→
310 const CycleSegment &CS = R.second.CS;
311 if (!CS.size()) {
2
←
Assuming the condition is true
→
3
←
Taking true branch
→
312 releaseResource(R.first);
4
←
Calling 'ResourceManager::releaseResource'
→
313 continue;
314 }
315
316 assert(CS.begin() == 0 && "Invalid {Start, End} cycles!")(static_cast<void> (0));
317 if (!R.second.isReserved()) {
318 ResourceRef Pipe = selectPipe(R.first);
319 use(Pipe);
320 BusyResources[Pipe] += CS.size();
321 Pipes.emplace_back(std::pair<ResourceRef, ResourceCycles>(
322 Pipe, ResourceCycles(CS.size())));
323 } else {
324 assert((countPopulation(R.first) > 1) && "Expected a group!")(static_cast<void> (0));
325 // Mark this group as reserved.
326 assert(R.second.isReserved())(static_cast<void> (0));
327 reserveResource(R.first);
328 BusyResources[ResourceRef(R.first, R.first)] += CS.size();
329 }
330 }
331}
332
333void ResourceManager::cycleEvent(SmallVectorImpl<ResourceRef> &ResourcesFreed) {
334 for (std::pair<ResourceRef, unsigned> &BR : BusyResources) {
335 if (BR.second)
336 BR.second--;
337 if (!BR.second) {
338 // Release this resource.
339 const ResourceRef &RR = BR.first;
340
341 if (countPopulation(RR.first) == 1)
342 release(RR);
343 releaseResource(RR.first);
344 ResourcesFreed.push_back(RR);
345 }
346 }
347
348 for (const ResourceRef &RF : ResourcesFreed)
349 BusyResources.erase(RF);
350}
351
352void ResourceManager::reserveResource(uint64_t ResourceID) {
353 const unsigned Index = getResourceStateIndex(ResourceID);
354 ResourceState &Resource = *Resources[Index];
355 assert(Resource.isAResourceGroup() && !Resource.isReserved() &&(static_cast<void> (0))
356 "Unexpected resource state found!")(static_cast<void> (0));
357 Resource.setReserved();
358 ReservedResourceGroups ^= 1ULL << Index;
359}
360
361void ResourceManager::releaseResource(uint64_t ResourceID) {
362 const unsigned Index = getResourceStateIndex(ResourceID);
5
←
Calling 'getResourceStateIndex'
→
7
←
Returning from 'getResourceStateIndex'
→
8
←
'Index' initialized to 4294967295
→
363 ResourceState &Resource = *Resources[Index];
364 Resource.clearReserved();
365 if (Resource.isAResourceGroup())
9
←
Assuming the condition is false
→
10
←
Taking false branch
→
366 ReservedResourceGroups ^= 1ULL << Index;
367 // Now it is safe to release dispatch/issue resources.
368 if (Resource.isADispatchHazard())
11
←
Calling 'ResourceState::isADispatchHazard'
→
14
←
Returning from 'ResourceState::isADispatchHazard'
→
15
←
Taking true branch
→
369 ReservedBuffers ^= 1ULL << Index;
16
←
The result of the left shift is undefined due to shifting by '4294967295', which is greater or equal to the width of type 'unsigned long long'
370}
371
372} // namespace mca
373} // namespace llvm
←

/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include/llvm/MCA/Support.h

→
1//===--------------------- Support.h ----------------------------*- 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/// Helper functions used by various pipeline components.
11///
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_MCA_SUPPORT_H
15#define LLVM_MCA_SUPPORT_H
16
17#include "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/MC/MCSchedule.h"
20#include "llvm/Support/Error.h"
21#include "llvm/Support/MathExtras.h"
22
23namespace llvm {
24namespace mca {
25
26template <typename T>
27class InstructionError : public ErrorInfo<InstructionError<T>> {
28public:
29 static char ID;
30 std::string Message;
31 const T &Inst;
32
33 InstructionError(std::string M, const T &MCI)
34 : Message(std::move(M)), Inst(MCI) {}
35
36 void log(raw_ostream &OS) const override { OS << Message; }
37
38 std::error_code convertToErrorCode() const override {
39 return inconvertibleErrorCode();
40 }
41};
42
43template <typename T> char InstructionError<T>::ID;
44
45/// This class represents the number of cycles per resource (fractions of
46/// cycles). That quantity is managed here as a ratio, and accessed via the
47/// double cast-operator below. The two quantities, number of cycles and
48/// number of resources, are kept separate. This is used by the
49/// ResourcePressureView to calculate the average resource cycles
50/// per instruction/iteration.
51class ResourceCycles {
52 unsigned Numerator, Denominator;
53
54public:
55 ResourceCycles() : Numerator(0), Denominator(1) {}
56 ResourceCycles(unsigned Cycles, unsigned ResourceUnits = 1)
57 : Numerator(Cycles), Denominator(ResourceUnits) {}
58
59 operator double() const {
60 assert(Denominator && "Invalid denominator (must be non-zero).")(static_cast<void> (0));
61 return (Denominator == 1) ? Numerator : (double)Numerator / Denominator;
62 }
63
64 unsigned getNumerator() const { return Numerator; }
65 unsigned getDenominator() const { return Denominator; }
66
67 // Add the components of RHS to this instance. Instead of calculating
68 // the final value here, we keep track of the numerator and denominator
69 // separately, to reduce floating point error.
70 ResourceCycles &operator+=(const ResourceCycles &RHS);
71};
72
73/// Populates vector Masks with processor resource masks.
74///
75/// The number of bits set in a mask depends on the processor resource type.
76/// Each processor resource mask has at least one bit set. For groups, the
77/// number of bits set in the mask is equal to the cardinality of the group plus
78/// one. Excluding the most significant bit, the remaining bits in the mask
79/// identify processor resources that are part of the group.
80///
81/// Example:
82///
83/// ResourceA -- Mask: 0b001
84/// ResourceB -- Mask: 0b010
85/// ResourceAB -- Mask: 0b100 U (ResourceA::Mask | ResourceB::Mask) == 0b111
86///
87/// ResourceAB is a processor resource group containing ResourceA and ResourceB.
88/// Each resource mask uniquely identifies a resource; both ResourceA and
89/// ResourceB only have one bit set.
90/// ResourceAB is a group; excluding the most significant bit in the mask, the
91/// remaining bits identify the composition of the group.
92///
93/// Resource masks are used by the ResourceManager to solve set membership
94/// problems with simple bit manipulation operations.
95void computeProcResourceMasks(const MCSchedModel &SM,
96 MutableArrayRef<uint64_t> Masks);
97
98// Returns the index of the highest bit set. For resource masks, the position of
99// the highest bit set can be used to construct a resource mask identifier.
100inline unsigned getResourceStateIndex(uint64_t Mask) {
101 assert(Mask && "Processor Resource Mask cannot be zero!")(static_cast<void> (0));
102 return (std::numeric_limits<uint64_t>::digits - countLeadingZeros(Mask)) - 1;
6
←
Returning the value 4294967295
→
103}
104
105/// Compute the reciprocal block throughput from a set of processor resource
106/// cycles. The reciprocal block throughput is computed as the MAX between:
107/// - NumMicroOps / DispatchWidth
108/// - ProcResourceCycles / #ProcResourceUnits (for every consumed resource).
109double computeBlockRThroughput(const MCSchedModel &SM, unsigned DispatchWidth,
110 unsigned NumMicroOps,
111 ArrayRef<unsigned> ProcResourceUsage);
112} // namespace mca
113} // namespace llvm
114
115#endif // LLVM_MCA_SUPPORT_H
←

/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include/llvm/MCA/HardwareUnits/ResourceManager.h

1//===--------------------- ResourceManager.h --------------------*- 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/// The classes here represent processor resource units and their management
11/// strategy. These classes are managed by the Scheduler.
12///
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_MCA_HARDWAREUNITS_RESOURCEMANAGER_H
16#define LLVM_MCA_HARDWAREUNITS_RESOURCEMANAGER_H
17
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/MC/MCSchedule.h"
21#include "llvm/MCA/Instruction.h"
22#include "llvm/MCA/Support.h"
23
24namespace llvm {
25namespace mca {
26
27/// Used to notify the internal state of a processor resource.
28///
29/// A processor resource is available if it is not reserved, and there are
30/// available slots in the buffer. A processor resource is unavailable if it
31/// is either reserved, or the associated buffer is full. A processor resource
32/// with a buffer size of -1 is always available if it is not reserved.
33///
34/// Values of type ResourceStateEvent are returned by method
35/// ResourceManager::canBeDispatched()
36///
37/// The naming convention for resource state events is:
38/// * Event names start with prefix RS_
39/// * Prefix RS_ is followed by a string describing the actual resource state.
40enum ResourceStateEvent {
41 RS_BUFFER_AVAILABLE,
42 RS_BUFFER_UNAVAILABLE,
43 RS_RESERVED
44};
45
46/// Resource allocation strategy used by hardware scheduler resources.
47class ResourceStrategy {
48 ResourceStrategy(const ResourceStrategy &) = delete;
49 ResourceStrategy &operator=(const ResourceStrategy &) = delete;
50
51public:
52 ResourceStrategy() {}
53 virtual ~ResourceStrategy();
54
55 /// Selects a processor resource unit from a ReadyMask.
56 virtual uint64_t select(uint64_t ReadyMask) = 0;
57
58 /// Called by the ResourceManager when a processor resource group, or a
59 /// processor resource with multiple units has become unavailable.
60 ///
61 /// The default strategy uses this information to bias its selection logic.
62 virtual void used(uint64_t ResourceMask) {}
63};
64
65/// Default resource allocation strategy used by processor resource groups and
66/// processor resources with multiple units.
67class DefaultResourceStrategy final : public ResourceStrategy {
68 /// A Mask of resource unit identifiers.
69 ///
70 /// There is one bit set for every available resource unit.
71 /// It defaults to the value of field ResourceSizeMask in ResourceState.
72 const uint64_t ResourceUnitMask;
73
74 /// A simple round-robin selector for processor resource units.
75 /// Each bit of this mask identifies a sub resource within a group.
76 ///
77 /// As an example, lets assume that this is a default policy for a
78 /// processor resource group composed by the following three units:
79 /// ResourceA -- 0b001
80 /// ResourceB -- 0b010
81 /// ResourceC -- 0b100
82 ///
83 /// Field NextInSequenceMask is used to select the next unit from the set of
84 /// resource units. It defaults to the value of field `ResourceUnitMasks` (in
85 /// this example, it defaults to mask '0b111').
86 ///
87 /// The round-robin selector would firstly select 'ResourceC', then
88 /// 'ResourceB', and eventually 'ResourceA'. When a resource R is used, the
89 /// corresponding bit in NextInSequenceMask is cleared. For example, if
90 /// 'ResourceC' is selected, then the new value of NextInSequenceMask becomes
91 /// 0xb011.
92 ///
93 /// When NextInSequenceMask becomes zero, it is automatically reset to the
94 /// default value (i.e. ResourceUnitMask).
95 uint64_t NextInSequenceMask;
96
97 /// This field is used to track resource units that are used (i.e. selected)
98 /// by other groups other than the one associated with this strategy object.
99 ///
100 /// In LLVM processor resource groups are allowed to partially (or fully)
101 /// overlap. That means, a same unit may be visible to multiple groups.
102 /// This field keeps track of uses that have originated from outside of
103 /// this group. The idea is to bias the selection strategy, so that resources
104 /// that haven't been used by other groups get prioritized.
105 ///
106 /// The end goal is to (try to) keep the resource distribution as much uniform
107 /// as possible. By construction, this mask only tracks one-level of resource
108 /// usage. Therefore, this strategy is expected to be less accurate when same
109 /// units are used multiple times by other groups within a single round of
110 /// select.
111 ///
112 /// Note: an LRU selector would have a better accuracy at the cost of being
113 /// slightly more expensive (mostly in terms of runtime cost). Methods
114 /// 'select' and 'used', are always in the hot execution path of llvm-mca.
115 /// Therefore, a slow implementation of 'select' would have a negative impact
116 /// on the overall performance of the tool.
117 uint64_t RemovedFromNextInSequence;
118
119public:
120 DefaultResourceStrategy(uint64_t UnitMask)
121 : ResourceStrategy(), ResourceUnitMask(UnitMask),
122 NextInSequenceMask(UnitMask), RemovedFromNextInSequence(0) {}
123 virtual ~DefaultResourceStrategy() = default;
124
125 uint64_t select(uint64_t ReadyMask) override;
126 void used(uint64_t Mask) override;
127};
128
129/// A processor resource descriptor.
130///
131/// There is an instance of this class for every processor resource defined by
132/// the machine scheduling model.
133/// Objects of class ResourceState dynamically track the usage of processor
134/// resource units.
135class ResourceState {
136 /// An index to the MCProcResourceDesc entry in the processor model.
137 const unsigned ProcResourceDescIndex;
138 /// A resource mask. This is generated by the tool with the help of
139 /// function `mca::computeProcResourceMasks' (see Support.h).
140 ///
141 /// Field ResourceMask only has one bit set if this resource state describes a
142 /// processor resource unit (i.e. this is not a group). That means, we can
143 /// quickly check if a resource is a group by simply counting the number of
144 /// bits that are set in the mask.
145 ///
146 /// The most significant bit of a mask (MSB) uniquely identifies a resource.
147 /// Remaining bits are used to describe the composition of a group (Group).
148 ///
149 /// Example (little endian):
150 /// Resource | Mask | MSB | Group
151 /// ---------+------------+------------+------------
152 /// A | 0b000001 | 0b000001 | 0b000000
153 /// | | |
154 /// B | 0b000010 | 0b000010 | 0b000000
155 /// | | |
156 /// C | 0b010000 | 0b010000 | 0b000000
157 /// | | |
158 /// D | 0b110010 | 0b100000 | 0b010010
159 ///
160 /// In this example, resources A, B and C are processor resource units.
161 /// Only resource D is a group resource, and it contains resources B and C.
162 /// That is because MSB(B) and MSB(C) are both contained within Group(D).
163 const uint64_t ResourceMask;
164
165 /// A ProcResource can have multiple units.
166 ///
167 /// For processor resource groups this field is a mask of contained resource
168 /// units. It is obtained from ResourceMask by clearing the highest set bit.
169 /// The number of resource units in a group can be simply computed as the
170 /// population count of this field.
171 ///
172 /// For normal (i.e. non-group) resources, the number of bits set in this mask
173 /// is equivalent to the number of units declared by the processor model (see
174 /// field 'NumUnits' in 'ProcResourceUnits').
175 uint64_t ResourceSizeMask;
176
177 /// A mask of ready units.
178 uint64_t ReadyMask;
179
180 /// Buffered resources will have this field set to a positive number different
181 /// than zero. A buffered resource behaves like a reservation station
182 /// implementing its own buffer for out-of-order execution.
183 ///
184 /// A BufferSize of 1 is used by scheduler resources that force in-order
185 /// execution.
186 ///
187 /// A BufferSize of 0 is used to model in-order issue/dispatch resources.
188 /// Since in-order issue/dispatch resources don't implement buffers, dispatch
189 /// events coincide with issue events.
190 /// Also, no other instruction ca be dispatched/issue while this resource is
191 /// in use. Only when all the "resource cycles" are consumed (after the issue
192 /// event), a new instruction ca be dispatched.
193 const int BufferSize;
194
195 /// Available slots in the buffer (zero, if this is not a buffered resource).
196 unsigned AvailableSlots;
197
198 /// This field is set if this resource is currently reserved.
199 ///
200 /// Resources can be reserved for a number of cycles.
201 /// Instructions can still be dispatched to reserved resources. However,
202 /// istructions dispatched to a reserved resource cannot be issued to the
203 /// underlying units (i.e. pipelines) until the resource is released.
204 bool Unavailable;
205
206 const bool IsAGroup;
207
208 /// Checks for the availability of unit 'SubResMask' in the group.
209 bool isSubResourceReady(uint64_t SubResMask) const {
210 return ReadyMask & SubResMask;
211 }
212
213public:
214 ResourceState(const MCProcResourceDesc &Desc, unsigned Index, uint64_t Mask);
215
216 unsigned getProcResourceID() const { return ProcResourceDescIndex; }
217 uint64_t getResourceMask() const { return ResourceMask; }
218 uint64_t getReadyMask() const { return ReadyMask; }
219 int getBufferSize() const { return BufferSize; }
220
221 bool isBuffered() const { return BufferSize > 0; }
222 bool isInOrder() const { return BufferSize == 1; }
223
224 /// Returns true if this is an in-order dispatch/issue resource.
225 bool isADispatchHazard() const { return BufferSize == 0; }
12
←
Assuming field 'BufferSize' is equal to 0
→
13
←
Returning the value 1, which participates in a condition later
→
226 bool isReserved() const { return Unavailable; }
227
228 void setReserved() { Unavailable = true; }
229 void clearReserved() { Unavailable = false; }
230
231 /// Returs true if this resource is not reserved, and if there are at least
232 /// `NumUnits` available units.
233 bool isReady(unsigned NumUnits = 1) const;
234
235 bool isAResourceGroup() const { return IsAGroup; }
236
237 bool containsResource(uint64_t ID) const { return ResourceMask & ID; }
238
239 void markSubResourceAsUsed(uint64_t ID) {
240 assert(isSubResourceReady(ID))(static_cast<void> (0));
241 ReadyMask ^= ID;
242 }
243
244 void releaseSubResource(uint64_t ID) {
245 assert(!isSubResourceReady(ID))(static_cast<void> (0));
246 ReadyMask ^= ID;
247 }
248
249 unsigned getNumUnits() const {
250 return isAResourceGroup() ? 1U : countPopulation(ResourceSizeMask);
251 }
252
253 /// Checks if there is an available slot in the resource buffer.
254 ///
255 /// Returns RS_BUFFER_AVAILABLE if this is not a buffered resource, or if
256 /// there is a slot available.
257 ///
258 /// Returns RS_RESERVED if this buffered resource is a dispatch hazard, and it
259 /// is reserved.
260 ///
261 /// Returns RS_BUFFER_UNAVAILABLE if there are no available slots.
262 ResourceStateEvent isBufferAvailable() const;
263
264 /// Reserve a buffer slot.
265 ///
266 /// Returns true if the buffer is not full.
267 /// It always returns true if BufferSize is set to zero.
268 bool reserveBuffer() {
269 if (BufferSize <= 0)
270 return true;
271
272 --AvailableSlots;
273 assert(AvailableSlots <= static_cast<unsigned>(BufferSize))(static_cast<void> (0));
274 return AvailableSlots;
275 }
276
277 /// Releases a slot in the buffer.
278 void releaseBuffer() {
279 // Ignore dispatch hazards or invalid buffer sizes.
280 if (BufferSize <= 0)
281 return;
282
283 ++AvailableSlots;
284 assert(AvailableSlots <= static_cast<unsigned>(BufferSize))(static_cast<void> (0));
285 }
286
287#ifndef NDEBUG1
288 void dump() const;
289#endif
290};
291
292/// A resource unit identifier.
293///
294/// This is used to identify a specific processor resource unit using a pair
295/// of indices where the 'first' index is a processor resource mask, and the
296/// 'second' index is an index for a "sub-resource" (i.e. unit).
297typedef std::pair<uint64_t, uint64_t> ResourceRef;
298
299// First: a MCProcResourceDesc index identifying a buffered resource.
300// Second: max number of buffer entries used in this resource.
301typedef std::pair<unsigned, unsigned> BufferUsageEntry;
302
303/// A resource manager for processor resource units and groups.
304///
305/// This class owns all the ResourceState objects, and it is responsible for
306/// acting on requests from a Scheduler by updating the internal state of
307/// ResourceState objects.
308/// This class doesn't know about instruction itineraries and functional units.
309/// In future, it can be extended to support itineraries too through the same
310/// public interface.
311class ResourceManager {
312 // Set of resources available on the subtarget.
313 //
314 // There is an instance of ResourceState for every resource declared by the
315 // target scheduling model.
316 //
317 // Elements of this vector are ordered by resource kind. In particular,
318 // resource units take precedence over resource groups.
319 //
320 // The index of a processor resource in this vector depends on the value of
321 // its mask (see the description of field ResourceState::ResourceMask). In
322 // particular, it is computed as the position of the most significant bit set
323 // (MSB) in the mask plus one (since we want to ignore the invalid resource
324 // descriptor at index zero).
325 //
326 // Example (little endian):
327 //
328 // Resource | Mask | MSB | Index
329 // ---------+---------+---------+-------
330 // A | 0b00001 | 0b00001 | 1
331 // | | |
332 // B | 0b00100 | 0b00100 | 3
333 // | | |
334 // C | 0b10010 | 0b10000 | 5
335 //
336 //
337 // The same index is also used to address elements within vector `Strategies`
338 // and vector `Resource2Groups`.
339 std::vector<std::unique_ptr<ResourceState>> Resources;
340 std::vector<std::unique_ptr<ResourceStrategy>> Strategies;
341
342 // Used to quickly identify groups that own a particular resource unit.
343 std::vector<uint64_t> Resource2Groups;
344
345 // A table that maps processor resource IDs to processor resource masks.
346 SmallVector<uint64_t, 8> ProcResID2Mask;
347
348 // A table that maps resource indices to actual processor resource IDs in the
349 // scheduling model.
350 SmallVector<unsigned, 8> ResIndex2ProcResID;
351
352 // Keeps track of which resources are busy, and how many cycles are left
353 // before those become usable again.
354 SmallDenseMap<ResourceRef, unsigned> BusyResources;
355
356 // Set of processor resource units available on the target.
357 uint64_t ProcResUnitMask;
358
359 // Set of processor resource units that are available during this cycle.
360 uint64_t AvailableProcResUnits;
361
362 // Set of processor resources that are currently reserved.
363 uint64_t ReservedResourceGroups;
364
365 // Set of unavailable scheduler buffer resources. This is used internally to
366 // speedup `canBeDispatched()` queries.
367 uint64_t AvailableBuffers;
368
369 // Set of dispatch hazard buffer resources that are currently unavailable.
370 uint64_t ReservedBuffers;
371
372 // Returns the actual resource unit that will be used.
373 ResourceRef selectPipe(uint64_t ResourceID);
374
375 void use(const ResourceRef &RR);
376 void release(const ResourceRef &RR);
377
378 unsigned getNumUnits(uint64_t ResourceID) const;
379
380 // Overrides the selection strategy for the processor resource with the given
381 // mask.
382 void setCustomStrategyImpl(std::unique_ptr<ResourceStrategy> S,
383 uint64_t ResourceMask);
384
385public:
386 ResourceManager(const MCSchedModel &SM);
387 virtual ~ResourceManager() = default;
388
389 // Overrides the selection strategy for the resource at index ResourceID in
390 // the MCProcResourceDesc table.
391 void setCustomStrategy(std::unique_ptr<ResourceStrategy> S,
392 unsigned ResourceID) {
393 assert(ResourceID < ProcResID2Mask.size() &&(static_cast<void> (0))
394 "Invalid resource index in input!")(static_cast<void> (0));
395 return setCustomStrategyImpl(std::move(S), ProcResID2Mask[ResourceID]);
396 }
397
398 // Returns RS_BUFFER_AVAILABLE if buffered resources are not reserved, and if
399 // there are enough available slots in the buffers.
400 ResourceStateEvent canBeDispatched(uint64_t ConsumedBuffers) const;
401
402 // Return the processor resource identifier associated to this Mask.
403 unsigned resolveResourceMask(uint64_t Mask) const;
404
405 // Acquires a slot from every buffered resource in mask `ConsumedBuffers`.
406 // Units that are dispatch hazards (i.e. BufferSize=0) are marked as reserved.
407 void reserveBuffers(uint64_t ConsumedBuffers);
408
409 // Releases a slot from every buffered resource in mask `ConsumedBuffers`.
410 // ConsumedBuffers is a bitmask of previously acquired buffers (using method
411 // `reserveBuffers`). Units that are dispatch hazards (i.e. BufferSize=0) are
412 // not automatically unreserved by this method.
413 void releaseBuffers(uint64_t ConsumedBuffers);
414
415 // Reserve a processor resource. A reserved resource is not available for
416 // instruction issue until it is released.
417 void reserveResource(uint64_t ResourceID);
418
419 // Release a previously reserved processor resource.
420 void releaseResource(uint64_t ResourceID);
421
422 // Returns a zero mask if resources requested by Desc are all available during
423 // this cycle. It returns a non-zero mask value only if there are unavailable
424 // processor resources; each bit set in the mask represents a busy processor
425 // resource unit or a reserved processor resource group.
426 uint64_t checkAvailability(const InstrDesc &Desc) const;
427
428 uint64_t getProcResUnitMask() const { return ProcResUnitMask; }
429 uint64_t getAvailableProcResUnits() const { return AvailableProcResUnits; }
430
431 void issueInstruction(
432 const InstrDesc &Desc,
433 SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Pipes);
434
435 void cycleEvent(SmallVectorImpl<ResourceRef> &ResourcesFreed);
436
437#ifndef NDEBUG1
438 void dump() const {
439 for (const std::unique_ptr<ResourceState> &Resource : Resources)
440 Resource->dump();
441 }
442#endif
443};
444} // namespace mca
445} // namespace llvm
446
447#endif // LLVM_MCA_HARDWAREUNITS_RESOURCEMANAGER_H