#include "llvm/CodeGen/ResourcePriorityQueue.h"
#include "llvm/CodeGen/DFAPacketizer.h"
#include "llvm/CodeGen/SelectionDAGISel.h"
#include "llvm/CodeGen/SelectionDAGNodes.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/Support/CommandLine.h"
using namespace llvm;
#define DEBUG_TYPE "scheduler"
static cl::opt<bool>
DisableDFASched("disable-dfa-sched", cl::Hidden,
cl::desc("Disable use of DFA during scheduling"));
static cl::opt<int> RegPressureThreshold(
"dfa-sched-reg-pressure-threshold", cl::Hidden, cl::init(5),
cl::desc("Track reg pressure and switch priority to in-depth"));
ResourcePriorityQueue::ResourcePriorityQueue(SelectionDAGISel *IS)
: Picker(this), InstrItins(IS->MF->getSubtarget().getInstrItineraryData()) {
const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
TRI = STI.getRegisterInfo();
TLI = IS->TLI;
TII = STI.getInstrInfo();
ResourcesModel.reset(TII->CreateTargetScheduleState(STI));
assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
unsigned NumRC = TRI->getNumRegClasses();
RegLimit.resize(NumRC);
RegPressure.resize(NumRC);
std::fill(RegLimit.begin(), RegLimit.end(), 0);
std::fill(RegPressure.begin(), RegPressure.end(), 0);
for (const TargetRegisterClass *RC : TRI->regclasses())
RegLimit[RC->getID()] = TRI->getRegPressureLimit(RC, *IS->MF);
ParallelLiveRanges = 0;
HorizontalVerticalBalance = 0;
}
unsigned
ResourcePriorityQueue::numberRCValPredInSU(SUnit *SU, unsigned RCId) {
unsigned NumberDeps = 0;
for (SDep &Pred : SU->Preds) {
if (Pred.isCtrl())
continue;
SUnit *PredSU = Pred.getSUnit();
const SDNode *ScegN = PredSU->getNode();
if (!ScegN)
continue;
switch (ScegN->getOpcode()) {
default: break;
case ISD::TokenFactor: break;
case ISD::CopyFromReg: NumberDeps++; break;
case ISD::CopyToReg: break;
case ISD::INLINEASM: break;
case ISD::INLINEASM_BR: break;
}
if (!ScegN->isMachineOpcode())
continue;
for (unsigned i = 0, e = ScegN->getNumValues(); i != e; ++i) {
MVT VT = ScegN->getSimpleValueType(i);
if (TLI->isTypeLegal(VT)
&& (TLI->getRegClassFor(VT)->getID() == RCId)) {
NumberDeps++;
break;
}
}
}
return NumberDeps;
}
unsigned ResourcePriorityQueue::numberRCValSuccInSU(SUnit *SU,
unsigned RCId) {
unsigned NumberDeps = 0;
for (const SDep &Succ : SU->Succs) {
if (Succ.isCtrl())
continue;
SUnit *SuccSU = Succ.getSUnit();
const SDNode *ScegN = SuccSU->getNode();
if (!ScegN)
continue;
switch (ScegN->getOpcode()) {
default: break;
case ISD::TokenFactor: break;
case ISD::CopyFromReg: break;
case ISD::CopyToReg: NumberDeps++; break;
case ISD::INLINEASM: break;
case ISD::INLINEASM_BR: break;
}
if (!ScegN->isMachineOpcode())
continue;
for (unsigned i = 0, e = ScegN->getNumOperands(); i != e; ++i) {
const SDValue &Op = ScegN->getOperand(i);
MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
if (TLI->isTypeLegal(VT)
&& (TLI->getRegClassFor(VT)->getID() == RCId)) {
NumberDeps++;
break;
}
}
}
return NumberDeps;
}
static unsigned numberCtrlDepsInSU(SUnit *SU) {
unsigned NumberDeps = 0;
for (const SDep &Succ : SU->Succs)
if (Succ.isCtrl())
NumberDeps++;
return NumberDeps;
}
static unsigned numberCtrlPredInSU(SUnit *SU) {
unsigned NumberDeps = 0;
for (SDep &Pred : SU->Preds)
if (Pred.isCtrl())
NumberDeps++;
return NumberDeps;
}
void ResourcePriorityQueue::initNodes(std::vector<SUnit> &sunits) {
SUnits = &sunits;
NumNodesSolelyBlocking.resize(SUnits->size(), 0);
for (SUnit &SU : *SUnits) {
initNumRegDefsLeft(&SU);
SU.NodeQueueId = 0;
}
}
bool resource_sort::operator()(const SUnit *LHS, const SUnit *RHS) const {
if (LHS->isScheduleHigh && !RHS->isScheduleHigh)
return false;
if (!LHS->isScheduleHigh && RHS->isScheduleHigh)
return true;
unsigned LHSNum = LHS->NodeNum;
unsigned RHSNum = RHS->NodeNum;
unsigned LHSLatency = PQ->getLatency(LHSNum);
unsigned RHSLatency = PQ->getLatency(RHSNum);
if (LHSLatency < RHSLatency) return true;
if (LHSLatency > RHSLatency) return false;
unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum);
unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum);
if (LHSBlocked < RHSBlocked) return true;
if (LHSBlocked > RHSBlocked) return false;
return LHSNum < RHSNum;
}
SUnit *ResourcePriorityQueue::getSingleUnscheduledPred(SUnit *SU) {
SUnit *OnlyAvailablePred = nullptr;
for (const SDep &Pred : SU->Preds) {
SUnit &PredSU = *Pred.getSUnit();
if (!PredSU.isScheduled) {
if (OnlyAvailablePred && OnlyAvailablePred != &PredSU)
return nullptr;
OnlyAvailablePred = &PredSU;
}
}
return OnlyAvailablePred;
}
void ResourcePriorityQueue::push(SUnit *SU) {
unsigned NumNodesBlocking = 0;
for (const SDep &Succ : SU->Succs)
if (getSingleUnscheduledPred(Succ.getSUnit()) == SU)
++NumNodesBlocking;
NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking;
Queue.push_back(SU);
}
bool ResourcePriorityQueue::isResourceAvailable(SUnit *SU) {
if (!SU || !SU->getNode())
return false;
if (SU->getNode()->getGluedNode())
return true;
if (SU->getNode()->isMachineOpcode())
switch (SU->getNode()->getMachineOpcode()) {
default:
if (!ResourcesModel->canReserveResources(&TII->get(
SU->getNode()->getMachineOpcode())))
return false;
break;
case TargetOpcode::EXTRACT_SUBREG:
case TargetOpcode::INSERT_SUBREG:
case TargetOpcode::SUBREG_TO_REG:
case TargetOpcode::REG_SEQUENCE:
case TargetOpcode::IMPLICIT_DEF:
break;
}
for (const SUnit *S : Packet)
for (const SDep &Succ : S->Succs) {
if (Succ.isCtrl())
continue;
if (Succ.getSUnit() == SU)
return false;
}
return true;
}
void ResourcePriorityQueue::reserveResources(SUnit *SU) {
if (!isResourceAvailable(SU) || SU->getNode()->getGluedNode()) {
ResourcesModel->clearResources();
Packet.clear();
}
if (SU->getNode() && SU->getNode()->isMachineOpcode()) {
switch (SU->getNode()->getMachineOpcode()) {
default:
ResourcesModel->reserveResources(&TII->get(
SU->getNode()->getMachineOpcode()));
break;
case TargetOpcode::EXTRACT_SUBREG:
case TargetOpcode::INSERT_SUBREG:
case TargetOpcode::SUBREG_TO_REG:
case TargetOpcode::REG_SEQUENCE:
case TargetOpcode::IMPLICIT_DEF:
break;
}
Packet.push_back(SU);
}
else {
ResourcesModel->clearResources();
Packet.clear();
}
if (Packet.size() >= InstrItins->SchedModel.IssueWidth) {
ResourcesModel->clearResources();
Packet.clear();
}
}
int ResourcePriorityQueue::rawRegPressureDelta(SUnit *SU, unsigned RCId) {
int RegBalance = 0;
if (!SU || !SU->getNode() || !SU->getNode()->isMachineOpcode())
return RegBalance;
for (unsigned i = 0, e = SU->getNode()->getNumValues(); i != e; ++i) {
MVT VT = SU->getNode()->getSimpleValueType(i);
if (TLI->isTypeLegal(VT)
&& TLI->getRegClassFor(VT)
&& TLI->getRegClassFor(VT)->getID() == RCId)
RegBalance += numberRCValSuccInSU(SU, RCId);
}
for (unsigned i = 0, e = SU->getNode()->getNumOperands(); i != e; ++i) {
const SDValue &Op = SU->getNode()->getOperand(i);
MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
if (isa<ConstantSDNode>(Op.getNode()))
continue;
if (TLI->isTypeLegal(VT) && TLI->getRegClassFor(VT)
&& TLI->getRegClassFor(VT)->getID() == RCId)
RegBalance -= numberRCValPredInSU(SU, RCId);
}
return RegBalance;
}
int ResourcePriorityQueue::regPressureDelta(SUnit *SU, bool RawPressure) {
int RegBalance = 0;
if (!SU || !SU->getNode() || !SU->getNode()->isMachineOpcode())
return RegBalance;
if (RawPressure) {
for (const TargetRegisterClass *RC : TRI->regclasses())
RegBalance += rawRegPressureDelta(SU, RC->getID());
}
else {
for (const TargetRegisterClass *RC : TRI->regclasses()) {
if ((RegPressure[RC->getID()] +
rawRegPressureDelta(SU, RC->getID()) > 0) &&
(RegPressure[RC->getID()] +
rawRegPressureDelta(SU, RC->getID()) >= RegLimit[RC->getID()]))
RegBalance += rawRegPressureDelta(SU, RC->getID());
}
}
return RegBalance;
}
static const unsigned PriorityOne = 200;
static const unsigned PriorityTwo = 50;
static const unsigned PriorityThree = 15;
static const unsigned PriorityFour = 5;
static const unsigned ScaleOne = 20;
static const unsigned ScaleTwo = 10;
static const unsigned ScaleThree = 5;
static const unsigned FactorOne = 2;
int ResourcePriorityQueue::SUSchedulingCost(SUnit *SU) {
int ResCount = 1;
if (SU->isScheduled)
return ResCount;
if (SU->isScheduleHigh)
ResCount += PriorityOne;
if (HorizontalVerticalBalance > RegPressureThreshold) {
ResCount += (SU->getHeight() * ScaleTwo);
if (isResourceAvailable(SU))
ResCount <<= FactorOne;
ResCount -= (regPressureDelta(SU,true) * ScaleOne);
}
else {
ResCount += (SU->getHeight() * ScaleTwo);
ResCount += (NumNodesSolelyBlocking[SU->NodeNum] * ScaleTwo);
if (isResourceAvailable(SU))
ResCount <<= FactorOne;
ResCount -= (regPressureDelta(SU) * ScaleTwo);
}
for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) {
if (N->isMachineOpcode()) {
const MCInstrDesc &TID = TII->get(N->getMachineOpcode());
if (TID.isCall())
ResCount += (PriorityTwo + (ScaleThree*N->getNumValues()));
}
else
switch (N->getOpcode()) {
default: break;
case ISD::TokenFactor:
case ISD::CopyFromReg:
case ISD::CopyToReg:
ResCount += PriorityFour;
break;
case ISD::INLINEASM:
case ISD::INLINEASM_BR:
ResCount += PriorityThree;
break;
}
}
return ResCount;
}
void ResourcePriorityQueue::scheduledNode(SUnit *SU) {
if (!SU) {
ResourcesModel->clearResources();
Packet.clear();
return;
}
const SDNode *ScegN = SU->getNode();
if (ScegN->isMachineOpcode()) {
for (unsigned i = 0, e = ScegN->getNumValues(); i != e; ++i) {
MVT VT = ScegN->getSimpleValueType(i);
if (TLI->isTypeLegal(VT)) {
const TargetRegisterClass *RC = TLI->getRegClassFor(VT);
if (RC)
RegPressure[RC->getID()] += numberRCValSuccInSU(SU, RC->getID());
}
}
for (unsigned i = 0, e = ScegN->getNumOperands(); i != e; ++i) {
const SDValue &Op = ScegN->getOperand(i);
MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
if (TLI->isTypeLegal(VT)) {
const TargetRegisterClass *RC = TLI->getRegClassFor(VT);
if (RC) {
if (RegPressure[RC->getID()] >
(numberRCValPredInSU(SU, RC->getID())))
RegPressure[RC->getID()] -= numberRCValPredInSU(SU, RC->getID());
else RegPressure[RC->getID()] = 0;
}
}
}
for (SDep &Pred : SU->Preds) {
if (Pred.isCtrl() || (Pred.getSUnit()->NumRegDefsLeft == 0))
continue;
--Pred.getSUnit()->NumRegDefsLeft;
}
}
reserveResources(SU);
unsigned NumberNonControlDeps = 0;
for (const SDep &Succ : SU->Succs) {
adjustPriorityOfUnscheduledPreds(Succ.getSUnit());
if (!Succ.isCtrl())
NumberNonControlDeps++;
}
if (!NumberNonControlDeps) {
if (ParallelLiveRanges >= SU->NumPreds)
ParallelLiveRanges -= SU->NumPreds;
else
ParallelLiveRanges = 0;
}
else
ParallelLiveRanges += SU->NumRegDefsLeft;
HorizontalVerticalBalance += (SU->Succs.size() - numberCtrlDepsInSU(SU));
HorizontalVerticalBalance -= (SU->Preds.size() - numberCtrlPredInSU(SU));
}
void ResourcePriorityQueue::initNumRegDefsLeft(SUnit *SU) {
unsigned NodeNumDefs = 0;
for (SDNode *N = SU->getNode(); N; N = N->getGluedNode())
if (N->isMachineOpcode()) {
const MCInstrDesc &TID = TII->get(N->getMachineOpcode());
if (N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF) {
NodeNumDefs = 0;
break;
}
NodeNumDefs = std::min(N->getNumValues(), TID.getNumDefs());
}
else
switch(N->getOpcode()) {
default: break;
case ISD::CopyFromReg:
NodeNumDefs++;
break;
case ISD::INLINEASM:
case ISD::INLINEASM_BR:
NodeNumDefs++;
break;
}
SU->NumRegDefsLeft = NodeNumDefs;
}
void ResourcePriorityQueue::adjustPriorityOfUnscheduledPreds(SUnit *SU) {
if (SU->isAvailable) return;
SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU);
if (!OnlyAvailablePred || !OnlyAvailablePred->isAvailable)
return;
remove(OnlyAvailablePred);
push(OnlyAvailablePred);
}
SUnit *ResourcePriorityQueue::pop() {
if (empty())
return nullptr;
std::vector<SUnit *>::iterator Best = Queue.begin();
if (!DisableDFASched) {
int BestCost = SUSchedulingCost(*Best);
for (auto I = std::next(Queue.begin()), E = Queue.end(); I != E; ++I) {
if (SUSchedulingCost(*I) > BestCost) {
BestCost = SUSchedulingCost(*I);
Best = I;
}
}
}
else {
for (auto I = std::next(Queue.begin()), E = Queue.end(); I != E; ++I)
if (Picker(*Best, *I))
Best = I;
}
SUnit *V = *Best;
if (Best != std::prev(Queue.end()))
std::swap(*Best, Queue.back());
Queue.pop_back();
return V;
}
void ResourcePriorityQueue::remove(SUnit *SU) {
assert(!Queue.empty() && "Queue is empty!");
std::vector<SUnit *>::iterator I = find(Queue, SU);
if (I != std::prev(Queue.end()))
std::swap(*I, Queue.back());
Queue.pop_back();
}