blob: 192d534bb9cfd739c1f91e94f8f5edd6ef66bb0f [file] [log] [blame]
//===- GCNMinRegStrategy.cpp ----------------------------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/ilist_node.h"
#include "llvm/ADT/simple_ilist.h"
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <cstdint>
#include <limits>
#include <vector>
using namespace llvm;
#define DEBUG_TYPE "machine-scheduler"
namespace {
class GCNMinRegScheduler {
struct Candidate : ilist_node<Candidate> {
const SUnit *SU;
int Priority;
Candidate(const SUnit *SU_, int Priority_ = 0)
: SU(SU_), Priority(Priority_) {}
};
SpecificBumpPtrAllocator<Candidate> Alloc;
using Queue = simple_ilist<Candidate>;
Queue RQ; // Ready queue
std::vector<unsigned> NumPreds;
bool isScheduled(const SUnit *SU) const {
assert(!SU->isBoundaryNode());
return NumPreds[SU->NodeNum] == std::numeric_limits<unsigned>::max();
}
void setIsScheduled(const SUnit *SU) {
assert(!SU->isBoundaryNode());
NumPreds[SU->NodeNum] = std::numeric_limits<unsigned>::max();
}
unsigned getNumPreds(const SUnit *SU) const {
assert(!SU->isBoundaryNode());
assert(NumPreds[SU->NodeNum] != std::numeric_limits<unsigned>::max());
return NumPreds[SU->NodeNum];
}
unsigned decNumPreds(const SUnit *SU) {
assert(!SU->isBoundaryNode());
assert(NumPreds[SU->NodeNum] != std::numeric_limits<unsigned>::max());
return --NumPreds[SU->NodeNum];
}
void initNumPreds(const decltype(ScheduleDAG::SUnits) &SUnits);
int getReadySuccessors(const SUnit *SU) const;
int getNotReadySuccessors(const SUnit *SU) const;
template <typename Calc>
unsigned findMax(unsigned Num, Calc C);
Candidate* pickCandidate();
void bumpPredsPriority(const SUnit *SchedSU, int Priority);
void releaseSuccessors(const SUnit* SU, int Priority);
public:
std::vector<const SUnit*> schedule(ArrayRef<const SUnit*> TopRoots,
const ScheduleDAG &DAG);
};
} // end anonymous namespace
void GCNMinRegScheduler::initNumPreds(const decltype(ScheduleDAG::SUnits) &SUnits) {
NumPreds.resize(SUnits.size());
for (unsigned I = 0; I < SUnits.size(); ++I)
NumPreds[I] = SUnits[I].NumPredsLeft;
}
int GCNMinRegScheduler::getReadySuccessors(const SUnit *SU) const {
unsigned NumSchedSuccs = 0;
for (auto SDep : SU->Succs) {
bool wouldBeScheduled = true;
for (auto PDep : SDep.getSUnit()->Preds) {
auto PSU = PDep.getSUnit();
assert(!PSU->isBoundaryNode());
if (PSU != SU && !isScheduled(PSU)) {
wouldBeScheduled = false;
break;
}
}
NumSchedSuccs += wouldBeScheduled ? 1 : 0;
}
return NumSchedSuccs;
}
int GCNMinRegScheduler::getNotReadySuccessors(const SUnit *SU) const {
return SU->Succs.size() - getReadySuccessors(SU);
}
template <typename Calc>
unsigned GCNMinRegScheduler::findMax(unsigned Num, Calc C) {
assert(!RQ.empty() && Num <= RQ.size());
using T = decltype(C(*RQ.begin())) ;
T Max = std::numeric_limits<T>::min();
unsigned NumMax = 0;
for (auto I = RQ.begin(); Num; --Num) {
T Cur = C(*I);
if (Cur >= Max) {
if (Cur > Max) {
Max = Cur;
NumMax = 1;
} else
++NumMax;
auto &Cand = *I++;
RQ.remove(Cand);
RQ.push_front(Cand);
continue;
}
++I;
}
return NumMax;
}
GCNMinRegScheduler::Candidate* GCNMinRegScheduler::pickCandidate() {
do {
unsigned Num = RQ.size();
if (Num == 1) break;
LLVM_DEBUG(dbgs() << "\nSelecting max priority candidates among " << Num
<< '\n');
Num = findMax(Num, [=](const Candidate &C) { return C.Priority; });
if (Num == 1) break;
LLVM_DEBUG(dbgs() << "\nSelecting min non-ready producing candidate among "
<< Num << '\n');
Num = findMax(Num, [=](const Candidate &C) {
auto SU = C.SU;
int Res = getNotReadySuccessors(SU);
LLVM_DEBUG(dbgs() << "SU(" << SU->NodeNum << ") would left non-ready "
<< Res << " successors, metric = " << -Res << '\n');
return -Res;
});
if (Num == 1) break;
LLVM_DEBUG(dbgs() << "\nSelecting most producing candidate among " << Num
<< '\n');
Num = findMax(Num, [=](const Candidate &C) {
auto SU = C.SU;
auto Res = getReadySuccessors(SU);
LLVM_DEBUG(dbgs() << "SU(" << SU->NodeNum << ") would make ready " << Res
<< " successors, metric = " << Res << '\n');
return Res;
});
if (Num == 1) break;
Num = Num ? Num : RQ.size();
LLVM_DEBUG(
dbgs()
<< "\nCan't find best candidate, selecting in program order among "
<< Num << '\n');
Num = findMax(Num, [=](const Candidate &C) { return -(int64_t)C.SU->NodeNum; });
assert(Num == 1);
} while (false);
return &RQ.front();
}
void GCNMinRegScheduler::bumpPredsPriority(const SUnit *SchedSU, int Priority) {
SmallPtrSet<const SUnit*, 32> Set;
for (const auto &S : SchedSU->Succs) {
if (S.getSUnit()->isBoundaryNode() || isScheduled(S.getSUnit()) ||
S.getKind() != SDep::Data)
continue;
for (const auto &P : S.getSUnit()->Preds) {
auto PSU = P.getSUnit();
assert(!PSU->isBoundaryNode());
if (PSU != SchedSU && !isScheduled(PSU)) {
Set.insert(PSU);
}
}
}
SmallVector<const SUnit*, 32> Worklist(Set.begin(), Set.end());
while (!Worklist.empty()) {
auto SU = Worklist.pop_back_val();
assert(!SU->isBoundaryNode());
for (const auto &P : SU->Preds) {
if (!P.getSUnit()->isBoundaryNode() && !isScheduled(P.getSUnit()) &&
Set.insert(P.getSUnit()).second)
Worklist.push_back(P.getSUnit());
}
}
LLVM_DEBUG(dbgs() << "Make the predecessors of SU(" << SchedSU->NodeNum
<< ")'s non-ready successors of " << Priority
<< " priority in ready queue: ");
const auto SetEnd = Set.end();
for (auto &C : RQ) {
if (Set.find(C.SU) != SetEnd) {
C.Priority = Priority;
LLVM_DEBUG(dbgs() << " SU(" << C.SU->NodeNum << ')');
}
}
LLVM_DEBUG(dbgs() << '\n');
}
void GCNMinRegScheduler::releaseSuccessors(const SUnit* SU, int Priority) {
for (const auto &S : SU->Succs) {
auto SuccSU = S.getSUnit();
if (S.isWeak())
continue;
assert(SuccSU->isBoundaryNode() || getNumPreds(SuccSU) > 0);
if (!SuccSU->isBoundaryNode() && decNumPreds(SuccSU) == 0)
RQ.push_front(*new (Alloc.Allocate()) Candidate(SuccSU, Priority));
}
}
std::vector<const SUnit*>
GCNMinRegScheduler::schedule(ArrayRef<const SUnit*> TopRoots,
const ScheduleDAG &DAG) {
const auto &SUnits = DAG.SUnits;
std::vector<const SUnit*> Schedule;
Schedule.reserve(SUnits.size());
initNumPreds(SUnits);
int StepNo = 0;
for (auto SU : TopRoots) {
RQ.push_back(*new (Alloc.Allocate()) Candidate(SU, StepNo));
}
releaseSuccessors(&DAG.EntrySU, StepNo);
while (!RQ.empty()) {
LLVM_DEBUG(dbgs() << "\n=== Picking candidate, Step = " << StepNo
<< "\n"
"Ready queue:";
for (auto &C
: RQ) dbgs()
<< ' ' << C.SU->NodeNum << "(P" << C.Priority << ')';
dbgs() << '\n';);
auto C = pickCandidate();
assert(C);
RQ.remove(*C);
auto SU = C->SU;
LLVM_DEBUG(dbgs() << "Selected "; SU->dump(&DAG));
releaseSuccessors(SU, StepNo);
Schedule.push_back(SU);
setIsScheduled(SU);
if (getReadySuccessors(SU) == 0)
bumpPredsPriority(SU, StepNo);
++StepNo;
}
assert(SUnits.size() == Schedule.size());
return Schedule;
}
namespace llvm {
std::vector<const SUnit*> makeMinRegSchedule(ArrayRef<const SUnit*> TopRoots,
const ScheduleDAG &DAG) {
GCNMinRegScheduler S;
return S.schedule(TopRoots, DAG);
}
} // end namespace llvm