blob: 39072af7d871186eed3beeacabe930f3ccfef6e8 [file] [log] [blame]
//===---------------------------- GCNILPSched.cpp - -----------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/Support/Debug.h"
using namespace llvm;
#define DEBUG_TYPE "machine-scheduler"
namespace {
class GCNILPScheduler {
struct Candidate : ilist_node<Candidate> {
SUnit *SU;
Candidate(SUnit *SU_)
: SU(SU_) {}
};
SpecificBumpPtrAllocator<Candidate> Alloc;
typedef simple_ilist<Candidate> Queue;
Queue PendingQueue;
Queue AvailQueue;
unsigned CurQueueId = 0;
std::vector<unsigned> SUNumbers;
/// CurCycle - The current scheduler state corresponds to this cycle.
unsigned CurCycle = 0;
unsigned getNodePriority(const SUnit *SU) const;
const SUnit *pickBest(const SUnit *left, const SUnit *right);
Candidate* pickCandidate();
void releasePending();
void advanceToCycle(unsigned NextCycle);
void releasePredecessors(const SUnit* SU);
public:
std::vector<const SUnit*> schedule(ArrayRef<const SUnit*> TopRoots,
const ScheduleDAG &DAG);
};
} // namespace
/// CalcNodeSethiUllmanNumber - Compute Sethi Ullman number.
/// Smaller number is the higher priority.
static unsigned
CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector<unsigned> &SUNumbers) {
unsigned &SethiUllmanNumber = SUNumbers[SU->NodeNum];
if (SethiUllmanNumber != 0)
return SethiUllmanNumber;
unsigned Extra = 0;
for (const SDep &Pred : SU->Preds) {
if (Pred.isCtrl()) continue; // ignore chain preds
SUnit *PredSU = Pred.getSUnit();
unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU, SUNumbers);
if (PredSethiUllman > SethiUllmanNumber) {
SethiUllmanNumber = PredSethiUllman;
Extra = 0;
}
else if (PredSethiUllman == SethiUllmanNumber)
++Extra;
}
SethiUllmanNumber += Extra;
if (SethiUllmanNumber == 0)
SethiUllmanNumber = 1;
return SethiUllmanNumber;
}
// Lower priority means schedule further down. For bottom-up scheduling, lower
// priority SUs are scheduled before higher priority SUs.
unsigned GCNILPScheduler::getNodePriority(const SUnit *SU) const {
assert(SU->NodeNum < SUNumbers.size());
if (SU->NumSuccs == 0 && SU->NumPreds != 0)
// If SU does not have a register use, i.e. it doesn't produce a value
// that would be consumed (e.g. store), then it terminates a chain of
// computation. Give it a large SethiUllman number so it will be
// scheduled right before its predecessors that it doesn't lengthen
// their live ranges.
return 0xffff;
if (SU->NumPreds == 0 && SU->NumSuccs != 0)
// If SU does not have a register def, schedule it close to its uses
// because it does not lengthen any live ranges.
return 0;
return SUNumbers[SU->NodeNum];
}
/// closestSucc - Returns the scheduled cycle of the successor which is
/// closest to the current cycle.
static unsigned closestSucc(const SUnit *SU) {
unsigned MaxHeight = 0;
for (const SDep &Succ : SU->Succs) {
if (Succ.isCtrl()) continue; // ignore chain succs
unsigned Height = Succ.getSUnit()->getHeight();
// If there are bunch of CopyToRegs stacked up, they should be considered
// to be at the same position.
if (Height > MaxHeight)
MaxHeight = Height;
}
return MaxHeight;
}
/// calcMaxScratches - Returns an cost estimate of the worse case requirement
/// for scratch registers, i.e. number of data dependencies.
static unsigned calcMaxScratches(const SUnit *SU) {
unsigned Scratches = 0;
for (const SDep &Pred : SU->Preds) {
if (Pred.isCtrl()) continue; // ignore chain preds
Scratches++;
}
return Scratches;
}
// Return -1 if left has higher priority, 1 if right has higher priority.
// Return 0 if latency-based priority is equivalent.
static int BUCompareLatency(const SUnit *left, const SUnit *right) {
// Scheduling an instruction that uses a VReg whose postincrement has not yet
// been scheduled will induce a copy. Model this as an extra cycle of latency.
int LHeight = (int)left->getHeight();
int RHeight = (int)right->getHeight();
// If either node is scheduling for latency, sort them by height/depth
// and latency.
// If neither instruction stalls (!LStall && !RStall) and HazardRecognizer
// is enabled, grouping instructions by cycle, then its height is already
// covered so only its depth matters. We also reach this point if both stall
// but have the same height.
if (LHeight != RHeight)
return LHeight > RHeight ? 1 : -1;
int LDepth = left->getDepth();
int RDepth = right->getDepth();
if (LDepth != RDepth) {
LLVM_DEBUG(dbgs() << " Comparing latency of SU (" << left->NodeNum
<< ") depth " << LDepth << " vs SU (" << right->NodeNum
<< ") depth " << RDepth << "\n");
return LDepth < RDepth ? 1 : -1;
}
if (left->Latency != right->Latency)
return left->Latency > right->Latency ? 1 : -1;
return 0;
}
const SUnit *GCNILPScheduler::pickBest(const SUnit *left, const SUnit *right)
{
// TODO: add register pressure lowering checks
bool const DisableSchedCriticalPath = false;
int MaxReorderWindow = 6;
if (!DisableSchedCriticalPath) {
int spread = (int)left->getDepth() - (int)right->getDepth();
if (std::abs(spread) > MaxReorderWindow) {
LLVM_DEBUG(dbgs() << "Depth of SU(" << left->NodeNum << "): "
<< left->getDepth() << " != SU(" << right->NodeNum
<< "): " << right->getDepth() << "\n");
return left->getDepth() < right->getDepth() ? right : left;
}
}
bool const DisableSchedHeight = false;
if (!DisableSchedHeight && left->getHeight() != right->getHeight()) {
int spread = (int)left->getHeight() - (int)right->getHeight();
if (std::abs(spread) > MaxReorderWindow)
return left->getHeight() > right->getHeight() ? right : left;
}
// Prioritize by Sethi-Ulmann number and push CopyToReg nodes down.
unsigned LPriority = getNodePriority(left);
unsigned RPriority = getNodePriority(right);
if (LPriority != RPriority)
return LPriority > RPriority ? right : left;
// Try schedule def + use closer when Sethi-Ullman numbers are the same.
// e.g.
// t1 = op t2, c1
// t3 = op t4, c2
//
// and the following instructions are both ready.
// t2 = op c3
// t4 = op c4
//
// Then schedule t2 = op first.
// i.e.
// t4 = op c4
// t2 = op c3
// t1 = op t2, c1
// t3 = op t4, c2
//
// This creates more short live intervals.
unsigned LDist = closestSucc(left);
unsigned RDist = closestSucc(right);
if (LDist != RDist)
return LDist < RDist ? right : left;
// How many registers becomes live when the node is scheduled.
unsigned LScratch = calcMaxScratches(left);
unsigned RScratch = calcMaxScratches(right);
if (LScratch != RScratch)
return LScratch > RScratch ? right : left;
bool const DisableSchedCycles = false;
if (!DisableSchedCycles) {
int result = BUCompareLatency(left, right);
if (result != 0)
return result > 0 ? right : left;
return left;
}
else {
if (left->getHeight() != right->getHeight())
return (left->getHeight() > right->getHeight()) ? right : left;
if (left->getDepth() != right->getDepth())
return (left->getDepth() < right->getDepth()) ? right : left;
}
assert(left->NodeQueueId && right->NodeQueueId &&
"NodeQueueId cannot be zero");
return (left->NodeQueueId > right->NodeQueueId) ? right : left;
}
GCNILPScheduler::Candidate* GCNILPScheduler::pickCandidate() {
if (AvailQueue.empty())
return nullptr;
auto Best = AvailQueue.begin();
for (auto I = std::next(AvailQueue.begin()), E = AvailQueue.end(); I != E; ++I) {
auto NewBestSU = pickBest(Best->SU, I->SU);
if (NewBestSU != Best->SU) {
assert(NewBestSU == I->SU);
Best = I;
}
}
return &*Best;
}
void GCNILPScheduler::releasePending() {
// Check to see if any of the pending instructions are ready to issue. If
// so, add them to the available queue.
for(auto I = PendingQueue.begin(), E = PendingQueue.end(); I != E;) {
auto &C = *I++;
if (C.SU->getHeight() <= CurCycle) {
PendingQueue.remove(C);
AvailQueue.push_back(C);
C.SU->NodeQueueId = CurQueueId++;
}
}
}
/// Move the scheduler state forward by the specified number of Cycles.
void GCNILPScheduler::advanceToCycle(unsigned NextCycle) {
if (NextCycle <= CurCycle)
return;
CurCycle = NextCycle;
releasePending();
}
void GCNILPScheduler::releasePredecessors(const SUnit* SU) {
for (const auto &PredEdge : SU->Preds) {
auto PredSU = PredEdge.getSUnit();
if (PredEdge.isWeak())
continue;
assert(PredSU->isBoundaryNode() || PredSU->NumSuccsLeft > 0);
PredSU->setHeightToAtLeast(SU->getHeight() + PredEdge.getLatency());
if (!PredSU->isBoundaryNode() && --PredSU->NumSuccsLeft == 0)
PendingQueue.push_front(*new (Alloc.Allocate()) Candidate(PredSU));
}
}
std::vector<const SUnit*>
GCNILPScheduler::schedule(ArrayRef<const SUnit*> BotRoots,
const ScheduleDAG &DAG) {
auto &SUnits = const_cast<ScheduleDAG&>(DAG).SUnits;
std::vector<SUnit> SUSavedCopy;
SUSavedCopy.resize(SUnits.size());
// we cannot save only those fields we touch: some of them are private
// so save units verbatim: this assumes SUnit should have value semantics
for (const SUnit &SU : SUnits)
SUSavedCopy[SU.NodeNum] = SU;
SUNumbers.assign(SUnits.size(), 0);
for (const SUnit &SU : SUnits)
CalcNodeSethiUllmanNumber(&SU, SUNumbers);
for (auto SU : BotRoots) {
AvailQueue.push_back(
*new (Alloc.Allocate()) Candidate(const_cast<SUnit*>(SU)));
}
releasePredecessors(&DAG.ExitSU);
std::vector<const SUnit*> Schedule;
Schedule.reserve(SUnits.size());
while (true) {
if (AvailQueue.empty() && !PendingQueue.empty()) {
auto EarliestSU = std::min_element(
PendingQueue.begin(), PendingQueue.end(),
[=](const Candidate& C1, const Candidate& C2) {
return C1.SU->getHeight() < C2.SU->getHeight();
})->SU;
advanceToCycle(std::max(CurCycle + 1, EarliestSU->getHeight()));
}
if (AvailQueue.empty())
break;
LLVM_DEBUG(dbgs() << "\n=== Picking candidate\n"
"Ready queue:";
for (auto &C
: AvailQueue) dbgs()
<< ' ' << C.SU->NodeNum;
dbgs() << '\n';);
auto C = pickCandidate();
assert(C);
AvailQueue.remove(*C);
auto SU = C->SU;
LLVM_DEBUG(dbgs() << "Selected "; DAG.dumpNode(*SU));
advanceToCycle(SU->getHeight());
releasePredecessors(SU);
Schedule.push_back(SU);
SU->isScheduled = true;
}
assert(SUnits.size() == Schedule.size());
std::reverse(Schedule.begin(), Schedule.end());
// restore units
for (auto &SU : SUnits)
SU = SUSavedCopy[SU.NodeNum];
return Schedule;
}
namespace llvm {
std::vector<const SUnit*> makeGCNILPScheduler(ArrayRef<const SUnit*> BotRoots,
const ScheduleDAG &DAG) {
GCNILPScheduler S;
return S.schedule(BotRoots, DAG);
}
}