Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/AMDGPU/GCNIterativeScheduler.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- GCNIterativeScheduler.cpp ------------------------------------------===//
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
9
#include "GCNIterativeScheduler.h"
10
#include "AMDGPUSubtarget.h"
11
#include "GCNRegPressure.h"
12
#include "GCNSchedStrategy.h"
13
#include "SIMachineFunctionInfo.h"
14
#include "llvm/ADT/ArrayRef.h"
15
#include "llvm/ADT/STLExtras.h"
16
#include "llvm/ADT/SmallVector.h"
17
#include "llvm/CodeGen/LiveIntervals.h"
18
#include "llvm/CodeGen/MachineBasicBlock.h"
19
#include "llvm/CodeGen/MachineFunction.h"
20
#include "llvm/CodeGen/RegisterPressure.h"
21
#include "llvm/CodeGen/ScheduleDAG.h"
22
#include "llvm/Config/llvm-config.h"
23
#include "llvm/Support/Compiler.h"
24
#include "llvm/Support/Debug.h"
25
#include "llvm/Support/raw_ostream.h"
26
#include <algorithm>
27
#include <cassert>
28
#include <iterator>
29
#include <limits>
30
#include <memory>
31
#include <type_traits>
32
#include <vector>
33
34
using namespace llvm;
35
36
#define DEBUG_TYPE "machine-scheduler"
37
38
namespace llvm {
39
40
std::vector<const SUnit *> makeMinRegSchedule(ArrayRef<const SUnit *> TopRoots,
41
                                              const ScheduleDAG &DAG);
42
43
  std::vector<const SUnit*> makeGCNILPScheduler(ArrayRef<const SUnit*> BotRoots,
44
    const ScheduleDAG &DAG);
45
}
46
47
// shim accessors for different order containers
48
423
static inline MachineInstr *getMachineInstr(MachineInstr *MI) {
49
423
  return MI;
50
423
}
51
3.86k
static inline MachineInstr *getMachineInstr(const SUnit *SU) {
52
3.86k
  return SU->getInstr();
53
3.86k
}
54
228
static inline MachineInstr *getMachineInstr(const SUnit &SU) {
55
228
  return SU.getInstr();
56
228
}
57
58
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
59
LLVM_DUMP_METHOD
60
static void printRegion(raw_ostream &OS,
61
                        MachineBasicBlock::iterator Begin,
62
                        MachineBasicBlock::iterator End,
63
                        const LiveIntervals *LIS,
64
                        unsigned MaxInstNum =
65
                          std::numeric_limits<unsigned>::max()) {
66
  auto BB = Begin->getParent();
67
  OS << BB->getParent()->getName() << ":" << printMBBReference(*BB) << ' '
68
     << BB->getName() << ":\n";
69
  auto I = Begin;
70
  MaxInstNum = std::max(MaxInstNum, 1u);
71
  for (; I != End && MaxInstNum; ++I, --MaxInstNum) {
72
    if (!I->isDebugInstr() && LIS)
73
      OS << LIS->getInstructionIndex(*I);
74
    OS << '\t' << *I;
75
  }
76
  if (I != End) {
77
    OS << "\t...\n";
78
    I = std::prev(End);
79
    if (!I->isDebugInstr() && LIS)
80
      OS << LIS->getInstructionIndex(*I);
81
    OS << '\t' << *I;
82
  }
83
  if (End != BB->end()) { // print boundary inst if present
84
    OS << "----\n";
85
    if (LIS) OS << LIS->getInstructionIndex(*End) << '\t';
86
    OS << *End;
87
  }
88
}
89
90
LLVM_DUMP_METHOD
91
static void printLivenessInfo(raw_ostream &OS,
92
                              MachineBasicBlock::iterator Begin,
93
                              MachineBasicBlock::iterator End,
94
                              const LiveIntervals *LIS) {
95
  const auto BB = Begin->getParent();
96
  const auto &MRI = BB->getParent()->getRegInfo();
97
98
  const auto LiveIns = getLiveRegsBefore(*Begin, *LIS);
99
  OS << "LIn RP: ";
100
  getRegPressure(MRI, LiveIns).print(OS);
101
102
  const auto BottomMI = End == BB->end() ? std::prev(End) : End;
103
  const auto LiveOuts = getLiveRegsAfter(*BottomMI, *LIS);
104
  OS << "LOt RP: ";
105
  getRegPressure(MRI, LiveOuts).print(OS);
106
}
107
108
LLVM_DUMP_METHOD
109
void GCNIterativeScheduler::printRegions(raw_ostream &OS) const {
110
  const auto &ST = MF.getSubtarget<GCNSubtarget>();
111
  for (const auto R : Regions) {
112
    OS << "Region to schedule ";
113
    printRegion(OS, R->Begin, R->End, LIS, 1);
114
    printLivenessInfo(OS, R->Begin, R->End, LIS);
115
    OS << "Max RP: ";
116
    R->MaxPressure.print(OS, &ST);
117
  }
118
}
119
120
LLVM_DUMP_METHOD
121
void GCNIterativeScheduler::printSchedResult(raw_ostream &OS,
122
                                             const Region *R,
123
                                             const GCNRegPressure &RP) const {
124
  OS << "\nAfter scheduling ";
125
  printRegion(OS, R->Begin, R->End, LIS);
126
  printSchedRP(OS, R->MaxPressure, RP);
127
  OS << '\n';
128
}
129
130
LLVM_DUMP_METHOD
131
void GCNIterativeScheduler::printSchedRP(raw_ostream &OS,
132
                                         const GCNRegPressure &Before,
133
                                         const GCNRegPressure &After) const {
134
  const auto &ST = MF.getSubtarget<GCNSubtarget>();
135
  OS << "RP before: ";
136
  Before.print(OS, &ST);
137
  OS << "RP after:  ";
138
  After.print(OS, &ST);
139
}
140
#endif
141
142
// DAG builder helper
143
class GCNIterativeScheduler::BuildDAG {
144
  GCNIterativeScheduler &Sch;
145
  SmallVector<SUnit *, 8> TopRoots;
146
147
  SmallVector<SUnit*, 8> BotRoots;
148
public:
149
  BuildDAG(const Region &R, GCNIterativeScheduler &_Sch)
150
8
    : Sch(_Sch) {
151
8
    auto BB = R.Begin->getParent();
152
8
    Sch.BaseClass::startBlock(BB);
153
8
    Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
154
8
155
8
    Sch.buildSchedGraph(Sch.AA, nullptr, nullptr, nullptr,
156
8
                        /*TrackLaneMask*/true);
157
8
    Sch.Topo.InitDAGTopologicalSorting();
158
8
    Sch.findRootsAndBiasEdges(TopRoots, BotRoots);
159
8
  }
160
161
8
  ~BuildDAG() {
162
8
    Sch.BaseClass::exitRegion();
163
8
    Sch.BaseClass::finishBlock();
164
8
  }
165
166
6
  ArrayRef<const SUnit *> getTopRoots() const {
167
6
    return TopRoots;
168
6
  }
169
2
  ArrayRef<SUnit*> getBottomRoots() const {
170
2
    return BotRoots;
171
2
  }
172
};
173
174
class GCNIterativeScheduler::OverrideLegacyStrategy {
175
  GCNIterativeScheduler &Sch;
176
  Region &Rgn;
177
  std::unique_ptr<MachineSchedStrategy> SaveSchedImpl;
178
  GCNRegPressure SaveMaxRP;
179
180
public:
181
  OverrideLegacyStrategy(Region &R,
182
                         MachineSchedStrategy &OverrideStrategy,
183
                         GCNIterativeScheduler &_Sch)
184
    : Sch(_Sch)
185
    , Rgn(R)
186
    , SaveSchedImpl(std::move(_Sch.SchedImpl))
187
4
    , SaveMaxRP(R.MaxPressure) {
188
4
    Sch.SchedImpl.reset(&OverrideStrategy);
189
4
    auto BB = R.Begin->getParent();
190
4
    Sch.BaseClass::startBlock(BB);
191
4
    Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
192
4
  }
193
194
4
  ~OverrideLegacyStrategy() {
195
4
    Sch.BaseClass::exitRegion();
196
4
    Sch.BaseClass::finishBlock();
197
4
    Sch.SchedImpl.release();
198
4
    Sch.SchedImpl = std::move(SaveSchedImpl);
199
4
  }
200
201
4
  void schedule() {
202
4
    assert(Sch.RegionBegin == Rgn.Begin && Sch.RegionEnd == Rgn.End);
203
4
    LLVM_DEBUG(dbgs() << "\nScheduling ";
204
4
               printRegion(dbgs(), Rgn.Begin, Rgn.End, Sch.LIS, 2));
205
4
    Sch.BaseClass::schedule();
206
4
207
4
    // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
208
4
    Sch.RegionEnd = Rgn.End;
209
4
    //assert(Rgn.End == Sch.RegionEnd);
210
4
    Rgn.Begin = Sch.RegionBegin;
211
4
    Rgn.MaxPressure.clear();
212
4
  }
213
214
1
  void restoreOrder() {
215
1
    assert(Sch.RegionBegin == Rgn.Begin && Sch.RegionEnd == Rgn.End);
216
1
    // DAG SUnits are stored using original region's order
217
1
    // so just use SUnits as the restoring schedule
218
1
    Sch.scheduleRegion(Rgn, Sch.SUnits, SaveMaxRP);
219
1
  }
220
};
221
222
namespace {
223
224
// just a stub to make base class happy
225
class SchedStrategyStub : public MachineSchedStrategy {
226
public:
227
16
  bool shouldTrackPressure() const override { return false; }
228
16
  bool shouldTrackLaneMasks() const override { return false; }
229
0
  void initialize(ScheduleDAGMI *DAG) override {}
230
0
  SUnit *pickNode(bool &IsTopNode) override { return nullptr; }
231
0
  void schedNode(SUnit *SU, bool IsTopNode) override {}
232
0
  void releaseTopNode(SUnit *SU) override {}
233
0
  void releaseBottomNode(SUnit *SU) override {}
234
};
235
236
} // end anonymous namespace
237
238
GCNIterativeScheduler::GCNIterativeScheduler(MachineSchedContext *C,
239
                                             StrategyKind S)
240
  : BaseClass(C, llvm::make_unique<SchedStrategyStub>())
241
  , Context(C)
242
  , Strategy(S)
243
8
  , UPTracker(*LIS) {
244
8
}
245
246
// returns max pressure for a region
247
GCNRegPressure
248
GCNIterativeScheduler::getRegionPressure(MachineBasicBlock::iterator Begin,
249
                                         MachineBasicBlock::iterator End)
250
12
  const {
251
12
  // For the purpose of pressure tracking bottom inst of the region should
252
12
  // be also processed. End is either BB end, BB terminator inst or sched
253
12
  // boundary inst.
254
12
  auto const BBEnd = Begin->getParent()->end();
255
12
  auto const BottomMI = End == BBEnd ? 
std::prev(End)0
: End;
256
12
257
12
  // scheduleRegions walks bottom to top, so its likely we just get next
258
12
  // instruction to track
259
12
  auto AfterBottomMI = std::next(BottomMI);
260
12
  if (AfterBottomMI == BBEnd ||
261
12
      
&*AfterBottomMI != UPTracker.getLastTrackedMI()0
) {
262
12
    UPTracker.reset(*BottomMI);
263
12
  } else {
264
0
    assert(UPTracker.isValid());
265
0
  }
266
12
267
3.64k
  for (auto I = BottomMI; I != Begin; 
--I3.63k
)
268
3.63k
    UPTracker.recede(*I);
269
12
270
12
  UPTracker.recede(*Begin);
271
12
272
12
  assert(UPTracker.isValid() ||
273
12
         (dbgs() << "Tracked region ",
274
12
          printRegion(dbgs(), Begin, End, LIS), false));
275
12
  return UPTracker.moveMaxPressure();
276
12
}
277
278
// returns max pressure for a tentative schedule
279
template <typename Range> GCNRegPressure
280
GCNIterativeScheduler::getSchedulePressure(const Region &R,
281
8
                                           Range &&Schedule) const {
282
8
  auto const BBEnd = R.Begin->getParent()->end();
283
8
  GCNUpwardRPTracker RPTracker(*LIS);
284
8
  if (R.End != BBEnd) {
285
8
    // R.End points to the boundary instruction but the
286
8
    // schedule doesn't include it
287
8
    RPTracker.reset(*R.End);
288
8
    RPTracker.recede(*R.End);
289
8
  } else {
290
0
    // R.End doesn't point to the boundary instruction
291
0
    RPTracker.reset(*std::prev(BBEnd));
292
0
  }
293
2.43k
  for (auto I = Schedule.end(), B = Schedule.begin(); I != B;) {
294
2.42k
    RPTracker.recede(*getMachineInstr(*--I));
295
2.42k
  }
296
8
  return RPTracker.moveMaxPressure();
297
8
}
298
299
void GCNIterativeScheduler::enterRegion(MachineBasicBlock *BB, // overriden
300
                                        MachineBasicBlock::iterator Begin,
301
                                        MachineBasicBlock::iterator End,
302
8
                                        unsigned NumRegionInstrs) {
303
8
  BaseClass::enterRegion(BB, Begin, End, NumRegionInstrs);
304
8
  if (NumRegionInstrs > 2) {
305
8
    Regions.push_back(
306
8
      new (Alloc.Allocate())
307
8
      Region { Begin, End, NumRegionInstrs,
308
8
               getRegionPressure(Begin, End), nullptr });
309
8
  }
310
8
}
311
312
8
void GCNIterativeScheduler::schedule() { // overriden
313
8
  // do nothing
314
8
  LLVM_DEBUG(printLivenessInfo(dbgs(), RegionBegin, RegionEnd, LIS);
315
8
             if (!Regions.empty() && Regions.back()->Begin == RegionBegin) {
316
8
               dbgs() << "Max RP: ";
317
8
               Regions.back()->MaxPressure.print(
318
8
                   dbgs(), &MF.getSubtarget<GCNSubtarget>());
319
8
             } dbgs()
320
8
             << '\n';);
321
8
}
322
323
8
void GCNIterativeScheduler::finalizeSchedule() { // overriden
324
8
  if (Regions.empty())
325
0
    return;
326
8
  switch (Strategy) {
327
8
  
case SCHEDULE_MINREGONLY: scheduleMinReg(); break0
;
328
8
  
case SCHEDULE_MINREGFORCED: scheduleMinReg(true); break3
;
329
8
  
case SCHEDULE_LEGACYMAXOCCUPANCY: scheduleLegacyMaxOccupancy(); break3
;
330
8
  
case SCHEDULE_ILP: scheduleILP(false); break2
;
331
8
  }
332
8
}
333
334
// Detach schedule from SUnits and interleave it with debug values.
335
// Returned schedule becomes independent of DAG state.
336
std::vector<MachineInstr*>
337
2
GCNIterativeScheduler::detachSchedule(ScheduleRef Schedule) const {
338
2
  std::vector<MachineInstr*> Res;
339
2
  Res.reserve(Schedule.size() * 2);
340
2
341
2
  if (FirstDbgValue)
342
0
    Res.push_back(FirstDbgValue);
343
2
344
2
  const auto DbgB = DbgValues.begin(), DbgE = DbgValues.end();
345
758
  for (auto SU : Schedule) {
346
758
    Res.push_back(SU->getInstr());
347
758
    const auto &D = std::find_if(DbgB, DbgE, [SU](decltype(*DbgB) &P) {
348
0
      return P.second == SU->getInstr();
349
0
    });
350
758
    if (D != DbgE)
351
0
      Res.push_back(D->first);
352
758
  }
353
2
  return Res;
354
2
}
355
356
void GCNIterativeScheduler::setBestSchedule(Region &R,
357
                                            ScheduleRef Schedule,
358
2
                                            const GCNRegPressure &MaxRP) {
359
2
  R.BestSchedule.reset(
360
2
    new TentativeSchedule{ detachSchedule(Schedule), MaxRP });
361
2
}
362
363
1
void GCNIterativeScheduler::scheduleBest(Region &R) {
364
1
  assert(R.BestSchedule.get() && "No schedule specified");
365
1
  scheduleRegion(R, R.BestSchedule->Schedule, R.BestSchedule->MaxPressure);
366
1
  R.BestSchedule.reset();
367
1
}
368
369
// minimal required region scheduler, works for ranges of SUnits*,
370
// SUnits or MachineIntrs*
371
template <typename Range>
372
void GCNIterativeScheduler::scheduleRegion(Region &R, Range &&Schedule,
373
7
                                           const GCNRegPressure &MaxRP) {
374
7
  assert(RegionBegin == R.Begin && RegionEnd == R.End);
375
7
  assert(LIS != nullptr);
376
#ifndef NDEBUG
377
  const auto SchedMaxRP = getSchedulePressure(R, Schedule);
378
#endif
379
  auto BB = R.Begin->getParent();
380
7
  auto Top = R.Begin;
381
2.08k
  for (const auto &I : Schedule) {
382
2.08k
    auto MI = getMachineInstr(I);
383
2.08k
    if (MI != &*Top) {
384
1.62k
      BB->remove(MI);
385
1.62k
      BB->insert(Top, MI);
386
1.62k
      if (!MI->isDebugInstr())
387
1.62k
        LIS->handleMove(*MI, true);
388
1.62k
    }
389
2.08k
    if (!MI->isDebugInstr()) {
390
2.08k
      // Reset read - undef flags and update them later.
391
2.08k
      for (auto &Op : MI->operands())
392
11.0k
        if (Op.isReg() && 
Op.isDef()7.41k
)
393
2.44k
          Op.setIsUndef(false);
394
2.08k
395
2.08k
      RegisterOperands RegOpers;
396
2.08k
      RegOpers.collect(*MI, *TRI, MRI, /*ShouldTrackLaneMasks*/true,
397
2.08k
                                       /*IgnoreDead*/false);
398
2.08k
      // Adjust liveness and add missing dead+read-undef flags.
399
2.08k
      auto SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
400
2.08k
      RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI);
401
2.08k
    }
402
2.08k
    Top = std::next(MI->getIterator());
403
2.08k
  }
404
7
  RegionBegin = getMachineInstr(Schedule.front());
405
7
406
7
  // Schedule consisting of MachineInstr* is considered 'detached'
407
7
  // and already interleaved with debug values
408
7
  if (!std::is_same<decltype(*Schedule.begin()), MachineInstr*>::value) {
409
7
    placeDebugValues();
410
7
    // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
411
7
    //assert(R.End == RegionEnd);
412
7
    RegionEnd = R.End;
413
7
  }
414
7
415
7
  R.Begin = RegionBegin;
416
7
  R.MaxPressure = MaxRP;
417
7
418
#ifndef NDEBUG
419
  const auto RegionMaxRP = getRegionPressure(R);
420
  const auto &ST = MF.getSubtarget<GCNSubtarget>();
421
#endif
422
  assert((SchedMaxRP == RegionMaxRP && (MaxRP.empty() || SchedMaxRP == MaxRP))
423
7
  || (dbgs() << "Max RP mismatch!!!\n"
424
7
                "RP for schedule (calculated): ",
425
7
      SchedMaxRP.print(dbgs(), &ST),
426
7
      dbgs() << "RP for schedule (reported): ",
427
7
      MaxRP.print(dbgs(), &ST),
428
7
      dbgs() << "RP after scheduling: ",
429
7
      RegionMaxRP.print(dbgs(), &ST),
430
7
      false));
431
7
}
void llvm::GCNIterativeScheduler::scheduleRegion<std::__1::vector<llvm::SUnit, std::__1::allocator<llvm::SUnit> >&>(llvm::GCNIterativeScheduler::Region&, std::__1::vector<llvm::SUnit, std::__1::allocator<llvm::SUnit> >&&&, llvm::GCNRegPressure const&)
Line
Count
Source
373
1
                                           const GCNRegPressure &MaxRP) {
374
1
  assert(RegionBegin == R.Begin && RegionEnd == R.End);
375
1
  assert(LIS != nullptr);
376
#ifndef NDEBUG
377
  const auto SchedMaxRP = getSchedulePressure(R, Schedule);
378
#endif
379
  auto BB = R.Begin->getParent();
380
1
  auto Top = R.Begin;
381
227
  for (const auto &I : Schedule) {
382
227
    auto MI = getMachineInstr(I);
383
227
    if (MI != &*Top) {
384
125
      BB->remove(MI);
385
125
      BB->insert(Top, MI);
386
125
      if (!MI->isDebugInstr())
387
125
        LIS->handleMove(*MI, true);
388
125
    }
389
227
    if (!MI->isDebugInstr()) {
390
227
      // Reset read - undef flags and update them later.
391
227
      for (auto &Op : MI->operands())
392
1.46k
        if (Op.isReg() && 
Op.isDef()914
)
393
241
          Op.setIsUndef(false);
394
227
395
227
      RegisterOperands RegOpers;
396
227
      RegOpers.collect(*MI, *TRI, MRI, /*ShouldTrackLaneMasks*/true,
397
227
                                       /*IgnoreDead*/false);
398
227
      // Adjust liveness and add missing dead+read-undef flags.
399
227
      auto SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
400
227
      RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI);
401
227
    }
402
227
    Top = std::next(MI->getIterator());
403
227
  }
404
1
  RegionBegin = getMachineInstr(Schedule.front());
405
1
406
1
  // Schedule consisting of MachineInstr* is considered 'detached'
407
1
  // and already interleaved with debug values
408
1
  if (!std::is_same<decltype(*Schedule.begin()), MachineInstr*>::value) {
409
1
    placeDebugValues();
410
1
    // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
411
1
    //assert(R.End == RegionEnd);
412
1
    RegionEnd = R.End;
413
1
  }
414
1
415
1
  R.Begin = RegionBegin;
416
1
  R.MaxPressure = MaxRP;
417
1
418
#ifndef NDEBUG
419
  const auto RegionMaxRP = getRegionPressure(R);
420
  const auto &ST = MF.getSubtarget<GCNSubtarget>();
421
#endif
422
  assert((SchedMaxRP == RegionMaxRP && (MaxRP.empty() || SchedMaxRP == MaxRP))
423
1
  || (dbgs() << "Max RP mismatch!!!\n"
424
1
                "RP for schedule (calculated): ",
425
1
      SchedMaxRP.print(dbgs(), &ST),
426
1
      dbgs() << "RP for schedule (reported): ",
427
1
      MaxRP.print(dbgs(), &ST),
428
1
      dbgs() << "RP after scheduling: ",
429
1
      RegionMaxRP.print(dbgs(), &ST),
430
1
      false));
431
1
}
void llvm::GCNIterativeScheduler::scheduleRegion<std::__1::vector<llvm::MachineInstr*, std::__1::allocator<llvm::MachineInstr*> >&>(llvm::GCNIterativeScheduler::Region&, std::__1::vector<llvm::MachineInstr*, std::__1::allocator<llvm::MachineInstr*> >&&&, llvm::GCNRegPressure const&)
Line
Count
Source
373
1
                                           const GCNRegPressure &MaxRP) {
374
1
  assert(RegionBegin == R.Begin && RegionEnd == R.End);
375
1
  assert(LIS != nullptr);
376
#ifndef NDEBUG
377
  const auto SchedMaxRP = getSchedulePressure(R, Schedule);
378
#endif
379
  auto BB = R.Begin->getParent();
380
1
  auto Top = R.Begin;
381
422
  for (const auto &I : Schedule) {
382
422
    auto MI = getMachineInstr(I);
383
422
    if (MI != &*Top) {
384
335
      BB->remove(MI);
385
335
      BB->insert(Top, MI);
386
335
      if (!MI->isDebugInstr())
387
335
        LIS->handleMove(*MI, true);
388
335
    }
389
422
    if (!MI->isDebugInstr()) {
390
422
      // Reset read - undef flags and update them later.
391
422
      for (auto &Op : MI->operands())
392
1.80k
        if (Op.isReg() && 
Op.isDef()1.35k
)
393
540
          Op.setIsUndef(false);
394
422
395
422
      RegisterOperands RegOpers;
396
422
      RegOpers.collect(*MI, *TRI, MRI, /*ShouldTrackLaneMasks*/true,
397
422
                                       /*IgnoreDead*/false);
398
422
      // Adjust liveness and add missing dead+read-undef flags.
399
422
      auto SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
400
422
      RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI);
401
422
    }
402
422
    Top = std::next(MI->getIterator());
403
422
  }
404
1
  RegionBegin = getMachineInstr(Schedule.front());
405
1
406
1
  // Schedule consisting of MachineInstr* is considered 'detached'
407
1
  // and already interleaved with debug values
408
1
  if (!std::is_same<decltype(*Schedule.begin()), MachineInstr*>::value) {
409
1
    placeDebugValues();
410
1
    // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
411
1
    //assert(R.End == RegionEnd);
412
1
    RegionEnd = R.End;
413
1
  }
414
1
415
1
  R.Begin = RegionBegin;
416
1
  R.MaxPressure = MaxRP;
417
1
418
#ifndef NDEBUG
419
  const auto RegionMaxRP = getRegionPressure(R);
420
  const auto &ST = MF.getSubtarget<GCNSubtarget>();
421
#endif
422
  assert((SchedMaxRP == RegionMaxRP && (MaxRP.empty() || SchedMaxRP == MaxRP))
423
1
  || (dbgs() << "Max RP mismatch!!!\n"
424
1
                "RP for schedule (calculated): ",
425
1
      SchedMaxRP.print(dbgs(), &ST),
426
1
      dbgs() << "RP for schedule (reported): ",
427
1
      MaxRP.print(dbgs(), &ST),
428
1
      dbgs() << "RP after scheduling: ",
429
1
      RegionMaxRP.print(dbgs(), &ST),
430
1
      false));
431
1
}
void llvm::GCNIterativeScheduler::scheduleRegion<std::__1::vector<llvm::SUnit const*, std::__1::allocator<llvm::SUnit const*> > const&>(llvm::GCNIterativeScheduler::Region&, std::__1::vector<llvm::SUnit const*, std::__1::allocator<llvm::SUnit const*> > const&&&, llvm::GCNRegPressure const&)
Line
Count
Source
373
5
                                           const GCNRegPressure &MaxRP) {
374
5
  assert(RegionBegin == R.Begin && RegionEnd == R.End);
375
5
  assert(LIS != nullptr);
376
#ifndef NDEBUG
377
  const auto SchedMaxRP = getSchedulePressure(R, Schedule);
378
#endif
379
  auto BB = R.Begin->getParent();
380
5
  auto Top = R.Begin;
381
1.43k
  for (const auto &I : Schedule) {
382
1.43k
    auto MI = getMachineInstr(I);
383
1.43k
    if (MI != &*Top) {
384
1.16k
      BB->remove(MI);
385
1.16k
      BB->insert(Top, MI);
386
1.16k
      if (!MI->isDebugInstr())
387
1.16k
        LIS->handleMove(*MI, true);
388
1.16k
    }
389
1.43k
    if (!MI->isDebugInstr()) {
390
1.43k
      // Reset read - undef flags and update them later.
391
1.43k
      for (auto &Op : MI->operands())
392
7.72k
        if (Op.isReg() && 
Op.isDef()5.15k
)
393
1.65k
          Op.setIsUndef(false);
394
1.43k
395
1.43k
      RegisterOperands RegOpers;
396
1.43k
      RegOpers.collect(*MI, *TRI, MRI, /*ShouldTrackLaneMasks*/true,
397
1.43k
                                       /*IgnoreDead*/false);
398
1.43k
      // Adjust liveness and add missing dead+read-undef flags.
399
1.43k
      auto SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
400
1.43k
      RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI);
401
1.43k
    }
402
1.43k
    Top = std::next(MI->getIterator());
403
1.43k
  }
404
5
  RegionBegin = getMachineInstr(Schedule.front());
405
5
406
5
  // Schedule consisting of MachineInstr* is considered 'detached'
407
5
  // and already interleaved with debug values
408
5
  if (!std::is_same<decltype(*Schedule.begin()), MachineInstr*>::value) {
409
5
    placeDebugValues();
410
5
    // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
411
5
    //assert(R.End == RegionEnd);
412
5
    RegionEnd = R.End;
413
5
  }
414
5
415
5
  R.Begin = RegionBegin;
416
5
  R.MaxPressure = MaxRP;
417
5
418
#ifndef NDEBUG
419
  const auto RegionMaxRP = getRegionPressure(R);
420
  const auto &ST = MF.getSubtarget<GCNSubtarget>();
421
#endif
422
  assert((SchedMaxRP == RegionMaxRP && (MaxRP.empty() || SchedMaxRP == MaxRP))
423
5
  || (dbgs() << "Max RP mismatch!!!\n"
424
5
                "RP for schedule (calculated): ",
425
5
      SchedMaxRP.print(dbgs(), &ST),
426
5
      dbgs() << "RP for schedule (reported): ",
427
5
      MaxRP.print(dbgs(), &ST),
428
5
      dbgs() << "RP after scheduling: ",
429
5
      RegionMaxRP.print(dbgs(), &ST),
430
5
      false));
431
5
}
432
433
// Sort recorded regions by pressure - highest at the front
434
8
void GCNIterativeScheduler::sortRegionsByPressure(unsigned TargetOcc) {
435
8
  const auto &ST = MF.getSubtarget<GCNSubtarget>();
436
8
  llvm::sort(Regions, [&ST, TargetOcc](const Region *R1, const Region *R2) {
437
0
    return R2->MaxPressure.less(ST, R1->MaxPressure, TargetOcc);
438
0
  });
439
8
}
440
441
///////////////////////////////////////////////////////////////////////////////
442
// Legacy MaxOccupancy Strategy
443
444
// Tries to increase occupancy applying minreg scheduler for a sequence of
445
// most demanding regions. Obtained schedules are saved as BestSchedule for a
446
// region.
447
// TargetOcc is the best achievable occupancy for a kernel.
448
// Returns better occupancy on success or current occupancy on fail.
449
// BestSchedules aren't deleted on fail.
450
3
unsigned GCNIterativeScheduler::tryMaximizeOccupancy(unsigned TargetOcc) {
451
3
  // TODO: assert Regions are sorted descending by pressure
452
3
  const auto &ST = MF.getSubtarget<GCNSubtarget>();
453
3
  const auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
454
3
  LLVM_DEBUG(dbgs() << "Trying to improve occupancy, target = " << TargetOcc
455
3
                    << ", current = " << Occ << '\n');
456
3
457
3
  auto NewOcc = TargetOcc;
458
3
  for (auto R : Regions) {
459
3
    if (R->MaxPressure.getOccupancy(ST) >= NewOcc)
460
0
      break;
461
3
462
3
    LLVM_DEBUG(printRegion(dbgs(), R->Begin, R->End, LIS, 3);
463
3
               printLivenessInfo(dbgs(), R->Begin, R->End, LIS));
464
3
465
3
    BuildDAG DAG(*R, *this);
466
3
    const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
467
3
    const auto MaxRP = getSchedulePressure(*R, MinSchedule);
468
3
    LLVM_DEBUG(dbgs() << "Occupancy improvement attempt:\n";
469
3
               printSchedRP(dbgs(), R->MaxPressure, MaxRP));
470
3
471
3
    NewOcc = std::min(NewOcc, MaxRP.getOccupancy(ST));
472
3
    if (NewOcc <= Occ)
473
1
      break;
474
2
475
2
    setBestSchedule(*R, MinSchedule, MaxRP);
476
2
  }
477
3
  LLVM_DEBUG(dbgs() << "New occupancy = " << NewOcc
478
3
                    << ", prev occupancy = " << Occ << '\n');
479
3
  if (NewOcc > Occ) {
480
2
    SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
481
2
    MFI->increaseOccupancy(MF, NewOcc);
482
2
  }
483
3
484
3
  return std::max(NewOcc, Occ);
485
3
}
486
487
void GCNIterativeScheduler::scheduleLegacyMaxOccupancy(
488
3
  bool TryMaximizeOccupancy) {
489
3
  const auto &ST = MF.getSubtarget<GCNSubtarget>();
490
3
  SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
491
3
  auto TgtOcc = MFI->getMinAllowedOccupancy();
492
3
493
3
  sortRegionsByPressure(TgtOcc);
494
3
  auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
495
3
496
3
  if (TryMaximizeOccupancy && Occ < TgtOcc)
497
3
    Occ = tryMaximizeOccupancy(TgtOcc);
498
3
499
3
  // This is really weird but for some magic scheduling regions twice
500
3
  // gives performance improvement
501
3
  const int NumPasses = Occ < TgtOcc ? 
21
:
12
;
502
3
503
3
  TgtOcc = std::min(Occ, TgtOcc);
504
3
  LLVM_DEBUG(dbgs() << "Scheduling using default scheduler, "
505
3
                       "target occupancy = "
506
3
                    << TgtOcc << '\n');
507
3
  GCNMaxOccupancySchedStrategy LStrgy(Context);
508
3
  unsigned FinalOccupancy = std::min(Occ, MFI->getOccupancy());
509
3
510
7
  for (int I = 0; I < NumPasses; 
++I4
) {
511
4
    // running first pass with TargetOccupancy = 0 mimics previous scheduling
512
4
    // approach and is a performance magic
513
4
    LStrgy.setTargetOccupancy(I == 0 ? 
03
:
TgtOcc1
);
514
4
    for (auto R : Regions) {
515
4
      OverrideLegacyStrategy Ovr(*R, LStrgy, *this);
516
4
517
4
      Ovr.schedule();
518
4
      const auto RP = getRegionPressure(*R);
519
4
      LLVM_DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
520
4
521
4
      if (RP.getOccupancy(ST) < TgtOcc) {
522
2
        LLVM_DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
523
2
        if (R->BestSchedule.get() &&
524
2
            
R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc1
) {
525
1
          LLVM_DEBUG(dbgs() << ", scheduling minimal register\n");
526
1
          scheduleBest(*R);
527
1
        } else {
528
1
          LLVM_DEBUG(dbgs() << ", restoring\n");
529
1
          Ovr.restoreOrder();
530
1
          assert(R->MaxPressure.getOccupancy(ST) >= TgtOcc);
531
1
        }
532
2
      }
533
4
      FinalOccupancy = std::min(FinalOccupancy, RP.getOccupancy(ST));
534
4
    }
535
4
  }
536
3
  MFI->limitOccupancy(FinalOccupancy);
537
3
}
538
539
///////////////////////////////////////////////////////////////////////////////
540
// Minimal Register Strategy
541
542
3
void GCNIterativeScheduler::scheduleMinReg(bool force) {
543
3
  const auto &ST = MF.getSubtarget<GCNSubtarget>();
544
3
  const SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
545
3
  const auto TgtOcc = MFI->getOccupancy();
546
3
  sortRegionsByPressure(TgtOcc);
547
3
548
3
  auto MaxPressure = Regions.front()->MaxPressure;
549
3
  for (auto R : Regions) {
550
3
    if (!force && 
R->MaxPressure.less(ST, MaxPressure, TgtOcc)0
)
551
0
      break;
552
3
553
3
    BuildDAG DAG(*R, *this);
554
3
    const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
555
3
556
3
    const auto RP = getSchedulePressure(*R, MinSchedule);
557
3
    LLVM_DEBUG(if (R->MaxPressure.less(ST, RP, TgtOcc)) {
558
3
      dbgs() << "\nWarning: Pressure becomes worse after minreg!";
559
3
      printSchedRP(dbgs(), R->MaxPressure, RP);
560
3
    });
561
3
562
3
    if (!force && 
MaxPressure.less(ST, RP, TgtOcc)0
)
563
0
      break;
564
3
565
3
    scheduleRegion(*R, MinSchedule, RP);
566
3
    LLVM_DEBUG(printSchedResult(dbgs(), R, RP));
567
3
568
3
    MaxPressure = RP;
569
3
  }
570
3
}
571
572
///////////////////////////////////////////////////////////////////////////////
573
// ILP scheduler port
574
575
void GCNIterativeScheduler::scheduleILP(
576
2
  bool TryMaximizeOccupancy) {
577
2
  const auto &ST = MF.getSubtarget<GCNSubtarget>();
578
2
  SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
579
2
  auto TgtOcc = MFI->getMinAllowedOccupancy();
580
2
581
2
  sortRegionsByPressure(TgtOcc);
582
2
  auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
583
2
584
2
  if (TryMaximizeOccupancy && 
Occ < TgtOcc0
)
585
0
    Occ = tryMaximizeOccupancy(TgtOcc);
586
2
587
2
  TgtOcc = std::min(Occ, TgtOcc);
588
2
  LLVM_DEBUG(dbgs() << "Scheduling using default scheduler, "
589
2
                       "target occupancy = "
590
2
                    << TgtOcc << '\n');
591
2
592
2
  unsigned FinalOccupancy = std::min(Occ, MFI->getOccupancy());
593
2
  for (auto R : Regions) {
594
2
    BuildDAG DAG(*R, *this);
595
2
    const auto ILPSchedule = makeGCNILPScheduler(DAG.getBottomRoots(), *this);
596
2
597
2
    const auto RP = getSchedulePressure(*R, ILPSchedule);
598
2
    LLVM_DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
599
2
600
2
    if (RP.getOccupancy(ST) < TgtOcc) {
601
0
      LLVM_DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
602
0
      if (R->BestSchedule.get() &&
603
0
        R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
604
0
        LLVM_DEBUG(dbgs() << ", scheduling minimal register\n");
605
0
        scheduleBest(*R);
606
0
      }
607
2
    } else {
608
2
      scheduleRegion(*R, ILPSchedule, RP);
609
2
      LLVM_DEBUG(printSchedResult(dbgs(), R, RP));
610
2
      FinalOccupancy = std::min(FinalOccupancy, RP.getOccupancy(ST));
611
2
    }
612
2
  }
613
2
  MFI->limitOccupancy(FinalOccupancy);
614
2
}