aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/libs/llvm12/lib/MCA/HardwareUnits/ResourceManager.cpp
blob: 30c4f14d13ae1994282dc472bcd8f81ef45013a5 (plain) (blame)
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
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
//===--------------------- ResourceManager.cpp ------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
/// \file
///
/// The classes here represent processor resource units and their management
/// strategy.  These classes are managed by the Scheduler.
///
//===----------------------------------------------------------------------===//

#include "llvm/MCA/HardwareUnits/ResourceManager.h"
#include "llvm/MCA/Support.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"

namespace llvm {
namespace mca {

#define DEBUG_TYPE "llvm-mca"
ResourceStrategy::~ResourceStrategy() = default;

static uint64_t selectImpl(uint64_t CandidateMask,
                           uint64_t &NextInSequenceMask) {
  // The upper bit set in CandidateMask identifies our next candidate resource.
  CandidateMask = 1ULL << getResourceStateIndex(CandidateMask);
  NextInSequenceMask &= (CandidateMask | (CandidateMask - 1));
  return CandidateMask;
}

uint64_t DefaultResourceStrategy::select(uint64_t ReadyMask) {
  // This method assumes that ReadyMask cannot be zero.
  uint64_t CandidateMask = ReadyMask & NextInSequenceMask;
  if (CandidateMask)
    return selectImpl(CandidateMask, NextInSequenceMask);

  NextInSequenceMask = ResourceUnitMask ^ RemovedFromNextInSequence;
  RemovedFromNextInSequence = 0;
  CandidateMask = ReadyMask & NextInSequenceMask;
  if (CandidateMask)
    return selectImpl(CandidateMask, NextInSequenceMask);

  NextInSequenceMask = ResourceUnitMask;
  CandidateMask = ReadyMask & NextInSequenceMask;
  return selectImpl(CandidateMask, NextInSequenceMask);
}

void DefaultResourceStrategy::used(uint64_t Mask) {
  if (Mask > NextInSequenceMask) {
    RemovedFromNextInSequence |= Mask;
    return;
  }

  NextInSequenceMask &= (~Mask);
  if (NextInSequenceMask)
    return;

  NextInSequenceMask = ResourceUnitMask ^ RemovedFromNextInSequence;
  RemovedFromNextInSequence = 0;
}

ResourceState::ResourceState(const MCProcResourceDesc &Desc, unsigned Index,
                             uint64_t Mask)
    : ProcResourceDescIndex(Index), ResourceMask(Mask),
      BufferSize(Desc.BufferSize), IsAGroup(countPopulation(ResourceMask) > 1) {
  if (IsAGroup) {
    ResourceSizeMask =
        ResourceMask ^ 1ULL << getResourceStateIndex(ResourceMask);
  } else {
    ResourceSizeMask = (1ULL << Desc.NumUnits) - 1;
  }
  ReadyMask = ResourceSizeMask;
  AvailableSlots = BufferSize == -1 ? 0U : static_cast<unsigned>(BufferSize);
  Unavailable = false;
}

bool ResourceState::isReady(unsigned NumUnits) const {
  return (!isReserved() || isADispatchHazard()) &&
         countPopulation(ReadyMask) >= NumUnits;
}

ResourceStateEvent ResourceState::isBufferAvailable() const {
  if (isADispatchHazard() && isReserved())
    return RS_RESERVED;
  if (!isBuffered() || AvailableSlots)
    return RS_BUFFER_AVAILABLE;
  return RS_BUFFER_UNAVAILABLE;
}

#ifndef NDEBUG
void ResourceState::dump() const {
  dbgs() << "MASK=" << format_hex(ResourceMask, 16)
         << ", SZMASK=" << format_hex(ResourceSizeMask, 16)
         << ", RDYMASK=" << format_hex(ReadyMask, 16)
         << ", BufferSize=" << BufferSize
         << ", AvailableSlots=" << AvailableSlots
         << ", Reserved=" << Unavailable << '\n';
}
#endif

static std::unique_ptr<ResourceStrategy>
getStrategyFor(const ResourceState &RS) {
  if (RS.isAResourceGroup() || RS.getNumUnits() > 1)
    return std::make_unique<DefaultResourceStrategy>(RS.getReadyMask());
  return std::unique_ptr<ResourceStrategy>(nullptr);
}

ResourceManager::ResourceManager(const MCSchedModel &SM)
    : Resources(SM.getNumProcResourceKinds() - 1),
      Strategies(SM.getNumProcResourceKinds() - 1),
      Resource2Groups(SM.getNumProcResourceKinds() - 1, 0),
      ProcResID2Mask(SM.getNumProcResourceKinds(), 0),
      ResIndex2ProcResID(SM.getNumProcResourceKinds() - 1, 0),
      ProcResUnitMask(0), ReservedResourceGroups(0),
      AvailableBuffers(~0ULL), ReservedBuffers(0) {
  computeProcResourceMasks(SM, ProcResID2Mask);

  // initialize vector ResIndex2ProcResID.
  for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
    unsigned Index = getResourceStateIndex(ProcResID2Mask[I]);
    ResIndex2ProcResID[Index] = I;
  }

  for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
    uint64_t Mask = ProcResID2Mask[I];
    unsigned Index = getResourceStateIndex(Mask);
    Resources[Index] =
        std::make_unique<ResourceState>(*SM.getProcResource(I), I, Mask);
    Strategies[Index] = getStrategyFor(*Resources[Index]);
  }

  for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
    uint64_t Mask = ProcResID2Mask[I];
    unsigned Index = getResourceStateIndex(Mask);
    const ResourceState &RS = *Resources[Index];
    if (!RS.isAResourceGroup()) {
      ProcResUnitMask |= Mask;
      continue;
    }

    uint64_t GroupMaskIdx = 1ULL << Index;
    Mask -= GroupMaskIdx;
    while (Mask) {
      // Extract lowest set isolated bit.
      uint64_t Unit = Mask & (-Mask);
      unsigned IndexUnit = getResourceStateIndex(Unit);
      Resource2Groups[IndexUnit] |= GroupMaskIdx;
      Mask ^= Unit;
    }
  }

  AvailableProcResUnits = ProcResUnitMask;
}

void ResourceManager::setCustomStrategyImpl(std::unique_ptr<ResourceStrategy> S,
                                            uint64_t ResourceMask) {
  unsigned Index = getResourceStateIndex(ResourceMask);
  assert(Index < Resources.size() && "Invalid processor resource index!");
  assert(S && "Unexpected null strategy in input!");
  Strategies[Index] = std::move(S);
}

unsigned ResourceManager::resolveResourceMask(uint64_t Mask) const {
  return ResIndex2ProcResID[getResourceStateIndex(Mask)];
}

unsigned ResourceManager::getNumUnits(uint64_t ResourceID) const {
  return Resources[getResourceStateIndex(ResourceID)]->getNumUnits();
}

// Returns the actual resource consumed by this Use.
// First, is the primary resource ID.
// Second, is the specific sub-resource ID.
ResourceRef ResourceManager::selectPipe(uint64_t ResourceID) {
  unsigned Index = getResourceStateIndex(ResourceID);
  assert(Index < Resources.size() && "Invalid resource use!");
  ResourceState &RS = *Resources[Index];
  assert(RS.isReady() && "No available units to select!");

  // Special case where RS is not a group, and it only declares a single
  // resource unit.
  if (!RS.isAResourceGroup() && RS.getNumUnits() == 1)
    return std::make_pair(ResourceID, RS.getReadyMask());

  uint64_t SubResourceID = Strategies[Index]->select(RS.getReadyMask());
  if (RS.isAResourceGroup())
    return selectPipe(SubResourceID);
  return std::make_pair(ResourceID, SubResourceID);
}

void ResourceManager::use(const ResourceRef &RR) {
  // Mark the sub-resource referenced by RR as used.
  unsigned RSID = getResourceStateIndex(RR.first);
  ResourceState &RS = *Resources[RSID];
  RS.markSubResourceAsUsed(RR.second);
  // Remember to update the resource strategy for non-group resources with
  // multiple units.
  if (RS.getNumUnits() > 1)
    Strategies[RSID]->used(RR.second);

  // If there are still available units in RR.first,
  // then we are done.
  if (RS.isReady())
    return;

  AvailableProcResUnits ^= RR.first;

  // Notify groups that RR.first is no longer available.
  uint64_t Users = Resource2Groups[RSID];
  while (Users) {
    // Extract lowest set isolated bit.
    unsigned GroupIndex = getResourceStateIndex(Users & (-Users));
    ResourceState &CurrentUser = *Resources[GroupIndex];
    CurrentUser.markSubResourceAsUsed(RR.first);
    Strategies[GroupIndex]->used(RR.first);
    // Reset lowest set bit.
    Users &= Users - 1;
  }
}

void ResourceManager::release(const ResourceRef &RR) {
  unsigned RSID = getResourceStateIndex(RR.first);
  ResourceState &RS = *Resources[RSID];
  bool WasFullyUsed = !RS.isReady();
  RS.releaseSubResource(RR.second);
  if (!WasFullyUsed)
    return;

  AvailableProcResUnits ^= RR.first;

  // Notify groups that RR.first is now available again.
  uint64_t Users = Resource2Groups[RSID];
  while (Users) {
    unsigned GroupIndex = getResourceStateIndex(Users & (-Users));
    ResourceState &CurrentUser = *Resources[GroupIndex];
    CurrentUser.releaseSubResource(RR.first);
    Users &= Users - 1;
  }
}

ResourceStateEvent
ResourceManager::canBeDispatched(uint64_t ConsumedBuffers) const {
  if (ConsumedBuffers & ReservedBuffers)
    return ResourceStateEvent::RS_RESERVED;
  if (ConsumedBuffers & (~AvailableBuffers))
    return ResourceStateEvent::RS_BUFFER_UNAVAILABLE;
  return ResourceStateEvent::RS_BUFFER_AVAILABLE;
}

void ResourceManager::reserveBuffers(uint64_t ConsumedBuffers) {
  while (ConsumedBuffers) {
    uint64_t CurrentBuffer = ConsumedBuffers & (-ConsumedBuffers);
    ResourceState &RS = *Resources[getResourceStateIndex(CurrentBuffer)];
    ConsumedBuffers ^= CurrentBuffer;
    assert(RS.isBufferAvailable() == ResourceStateEvent::RS_BUFFER_AVAILABLE);
    if (!RS.reserveBuffer())
      AvailableBuffers ^= CurrentBuffer;
    if (RS.isADispatchHazard()) {
      // Reserve this buffer now, and release it once pipeline resources
      // consumed by the instruction become available again.
      // We do this to simulate an in-order dispatch/issue of instructions.
      ReservedBuffers ^= CurrentBuffer;
    }
  }
}

void ResourceManager::releaseBuffers(uint64_t ConsumedBuffers) {
  AvailableBuffers |= ConsumedBuffers;
  while (ConsumedBuffers) {
    uint64_t CurrentBuffer = ConsumedBuffers & (-ConsumedBuffers);
    ResourceState &RS = *Resources[getResourceStateIndex(CurrentBuffer)];
    ConsumedBuffers ^= CurrentBuffer;
    RS.releaseBuffer();
    // Do not unreserve dispatch hazard resource buffers. Wait until all
    // pipeline resources have been freed too.
  }
}

uint64_t ResourceManager::checkAvailability(const InstrDesc &Desc) const {
  uint64_t BusyResourceMask = 0;
  for (const std::pair<uint64_t, ResourceUsage> &E : Desc.Resources) {
    unsigned NumUnits = E.second.isReserved() ? 0U : E.second.NumUnits;
    unsigned Index = getResourceStateIndex(E.first);
    if (!Resources[Index]->isReady(NumUnits))
      BusyResourceMask |= E.first;
  }

  BusyResourceMask &= ProcResUnitMask;
  if (BusyResourceMask)
    return BusyResourceMask;
  return Desc.UsedProcResGroups & ReservedResourceGroups;
}

void ResourceManager::issueInstruction(
    const InstrDesc &Desc,
    SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Pipes) {
  for (const std::pair<uint64_t, ResourceUsage> &R : Desc.Resources) {
    const CycleSegment &CS = R.second.CS;
    if (!CS.size()) {
      releaseResource(R.first);
      continue;
    }

    assert(CS.begin() == 0 && "Invalid {Start, End} cycles!");
    if (!R.second.isReserved()) {
      ResourceRef Pipe = selectPipe(R.first);
      use(Pipe);
      BusyResources[Pipe] += CS.size();
      Pipes.emplace_back(std::pair<ResourceRef, ResourceCycles>(
          Pipe, ResourceCycles(CS.size())));
    } else {
      assert((countPopulation(R.first) > 1) && "Expected a group!");
      // Mark this group as reserved.
      assert(R.second.isReserved());
      reserveResource(R.first);
      BusyResources[ResourceRef(R.first, R.first)] += CS.size();
    }
  }
}

void ResourceManager::cycleEvent(SmallVectorImpl<ResourceRef> &ResourcesFreed) {
  for (std::pair<ResourceRef, unsigned> &BR : BusyResources) {
    if (BR.second)
      BR.second--;
    if (!BR.second) {
      // Release this resource.
      const ResourceRef &RR = BR.first;

      if (countPopulation(RR.first) == 1)
        release(RR);
      releaseResource(RR.first);
      ResourcesFreed.push_back(RR);
    }
  }

  for (const ResourceRef &RF : ResourcesFreed)
    BusyResources.erase(RF);
}

void ResourceManager::reserveResource(uint64_t ResourceID) {
  const unsigned Index = getResourceStateIndex(ResourceID);
  ResourceState &Resource = *Resources[Index];
  assert(Resource.isAResourceGroup() && !Resource.isReserved() &&
         "Unexpected resource state found!");
  Resource.setReserved();
  ReservedResourceGroups ^= 1ULL << Index;
}

void ResourceManager::releaseResource(uint64_t ResourceID) {
  const unsigned Index = getResourceStateIndex(ResourceID);
  ResourceState &Resource = *Resources[Index];
  Resource.clearReserved();
  if (Resource.isAResourceGroup())
    ReservedResourceGroups ^= 1ULL << Index;
  // Now it is safe to release dispatch/issue resources.
  if (Resource.isADispatchHazard())
    ReservedBuffers ^= 1ULL << Index;
}

} // namespace mca
} // namespace llvm