SIMachineScheduler.cpp [plain text]
#include "SIMachineScheduler.h"
#include "AMDGPUSubtarget.h"
#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/MachineScheduler.h"
#include "llvm/CodeGen/RegisterPressure.h"
using namespace llvm;
#define DEBUG_TYPE "misched"
#ifndef NDEBUG
static const char *getReasonStr(SIScheduleCandReason Reason) {
switch (Reason) {
case NoCand: return "NOCAND";
case RegUsage: return "REGUSAGE";
case Latency: return "LATENCY";
case Successor: return "SUCCESSOR";
case Depth: return "DEPTH";
case NodeOrder: return "ORDER";
}
llvm_unreachable("Unknown reason!");
}
#endif
static bool tryLess(int TryVal, int CandVal,
SISchedulerCandidate &TryCand,
SISchedulerCandidate &Cand,
SIScheduleCandReason Reason) {
if (TryVal < CandVal) {
TryCand.Reason = Reason;
return true;
}
if (TryVal > CandVal) {
if (Cand.Reason > Reason)
Cand.Reason = Reason;
return true;
}
Cand.setRepeat(Reason);
return false;
}
static bool tryGreater(int TryVal, int CandVal,
SISchedulerCandidate &TryCand,
SISchedulerCandidate &Cand,
SIScheduleCandReason Reason) {
if (TryVal > CandVal) {
TryCand.Reason = Reason;
return true;
}
if (TryVal < CandVal) {
if (Cand.Reason > Reason)
Cand.Reason = Reason;
return true;
}
Cand.setRepeat(Reason);
return false;
}
void SIScheduleBlock::addUnit(SUnit *SU) {
NodeNum2Index[SU->NodeNum] = SUnits.size();
SUnits.push_back(SU);
}
#ifndef NDEBUG
void SIScheduleBlock::traceCandidate(const SISchedCandidate &Cand) {
dbgs() << " SU(" << Cand.SU->NodeNum << ") " << getReasonStr(Cand.Reason);
dbgs() << '\n';
}
#endif
void SIScheduleBlock::tryCandidateTopDown(SISchedCandidate &Cand,
SISchedCandidate &TryCand) {
if (!Cand.isValid()) {
TryCand.Reason = NodeOrder;
return;
}
if (Cand.SGPRUsage > 60 &&
tryLess(TryCand.SGPRUsage, Cand.SGPRUsage, TryCand, Cand, RegUsage))
return;
if (tryLess(TryCand.HasLowLatencyNonWaitedParent,
Cand.HasLowLatencyNonWaitedParent,
TryCand, Cand, SIScheduleCandReason::Depth))
return;
if (tryGreater(TryCand.IsLowLatency, Cand.IsLowLatency,
TryCand, Cand, SIScheduleCandReason::Depth))
return;
if (TryCand.IsLowLatency &&
tryLess(TryCand.LowLatencyOffset, Cand.LowLatencyOffset,
TryCand, Cand, SIScheduleCandReason::Depth))
return;
if (tryLess(TryCand.VGPRUsage, Cand.VGPRUsage, TryCand, Cand, RegUsage))
return;
if (TryCand.SU->NodeNum < Cand.SU->NodeNum) {
TryCand.Reason = NodeOrder;
}
}
SUnit* SIScheduleBlock::pickNode() {
SISchedCandidate TopCand;
for (SUnit* SU : TopReadySUs) {
SISchedCandidate TryCand;
std::vector<unsigned> pressure;
std::vector<unsigned> MaxPressure;
TryCand.SU = SU;
TopRPTracker.getDownwardPressure(SU->getInstr(), pressure, MaxPressure);
TryCand.SGPRUsage = pressure[DAG->getSGPRSetID()];
TryCand.VGPRUsage = pressure[DAG->getVGPRSetID()];
TryCand.IsLowLatency = DAG->IsLowLatencySU[SU->NodeNum];
TryCand.LowLatencyOffset = DAG->LowLatencyOffset[SU->NodeNum];
TryCand.HasLowLatencyNonWaitedParent =
HasLowLatencyNonWaitedParent[NodeNum2Index[SU->NodeNum]];
tryCandidateTopDown(TopCand, TryCand);
if (TryCand.Reason != NoCand)
TopCand.setBest(TryCand);
}
return TopCand.SU;
}
void SIScheduleBlock::fastSchedule() {
TopReadySUs.clear();
if (Scheduled)
undoSchedule();
for (SUnit* SU : SUnits) {
if (!SU->NumPredsLeft)
TopReadySUs.push_back(SU);
}
while (!TopReadySUs.empty()) {
SUnit *SU = TopReadySUs[0];
ScheduledSUnits.push_back(SU);
nodeScheduled(SU);
}
Scheduled = true;
}
static bool isDefBetween(unsigned Reg,
SlotIndex First, SlotIndex Last,
const MachineRegisterInfo *MRI,
const LiveIntervals *LIS) {
for (MachineRegisterInfo::def_instr_iterator
UI = MRI->def_instr_begin(Reg),
UE = MRI->def_instr_end(); UI != UE; ++UI) {
const MachineInstr* MI = &*UI;
if (MI->isDebugValue())
continue;
SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot();
if (InstSlot >= First && InstSlot <= Last)
return true;
}
return false;
}
void SIScheduleBlock::initRegPressure(MachineBasicBlock::iterator BeginBlock,
MachineBasicBlock::iterator EndBlock) {
IntervalPressure Pressure, BotPressure;
RegPressureTracker RPTracker(Pressure), BotRPTracker(BotPressure);
LiveIntervals *LIS = DAG->getLIS();
MachineRegisterInfo *MRI = DAG->getMRI();
DAG->initRPTracker(TopRPTracker);
DAG->initRPTracker(BotRPTracker);
DAG->initRPTracker(RPTracker);
for (SUnit* SU : ScheduledSUnits) {
RPTracker.setPos(SU->getInstr());
RPTracker.advance();
}
RPTracker.closeRegion();
TopRPTracker.addLiveRegs(RPTracker.getPressure().LiveInRegs);
BotRPTracker.addLiveRegs(RPTracker.getPressure().LiveOutRegs);
for (const auto &RegMaskPair : RPTracker.getPressure().LiveInRegs) {
if (TargetRegisterInfo::isVirtualRegister(RegMaskPair.RegUnit))
LiveInRegs.insert(RegMaskPair.RegUnit);
}
LiveOutRegs.clear();
for (const auto &RegMaskPair : RPTracker.getPressure().LiveOutRegs) {
unsigned Reg = RegMaskPair.RegUnit;
if (TargetRegisterInfo::isVirtualRegister(Reg) &&
isDefBetween(Reg, LIS->getInstructionIndex(BeginBlock).getRegSlot(),
LIS->getInstructionIndex(EndBlock).getRegSlot(),
MRI, LIS)) {
LiveOutRegs.insert(Reg);
}
}
LiveInPressure = TopPressure.MaxSetPressure;
LiveOutPressure = BotPressure.MaxSetPressure;
TopRPTracker.closeTop();
}
void SIScheduleBlock::schedule(MachineBasicBlock::iterator BeginBlock,
MachineBasicBlock::iterator EndBlock) {
if (!Scheduled)
fastSchedule();
initRegPressure(BeginBlock, EndBlock);
undoSchedule();
TopReadySUs.clear();
for (SUnit* SU : SUnits) {
if (!SU->NumPredsLeft)
TopReadySUs.push_back(SU);
}
while (!TopReadySUs.empty()) {
SUnit *SU = pickNode();
ScheduledSUnits.push_back(SU);
TopRPTracker.setPos(SU->getInstr());
TopRPTracker.advance();
nodeScheduled(SU);
}
InternalAdditionnalPressure.resize(TopPressure.MaxSetPressure.size());
#ifndef NDEBUG
assert(SUnits.size() == ScheduledSUnits.size() &&
TopReadySUs.empty());
for (SUnit* SU : SUnits) {
assert(SU->isScheduled &&
SU->NumPredsLeft == 0);
}
#endif
Scheduled = true;
}
void SIScheduleBlock::undoSchedule() {
for (SUnit* SU : SUnits) {
SU->isScheduled = false;
for (SDep& Succ : SU->Succs) {
if (BC->isSUInBlock(Succ.getSUnit(), ID))
undoReleaseSucc(SU, &Succ);
}
}
HasLowLatencyNonWaitedParent.assign(SUnits.size(), 0);
ScheduledSUnits.clear();
Scheduled = false;
}
void SIScheduleBlock::undoReleaseSucc(SUnit *SU, SDep *SuccEdge) {
SUnit *SuccSU = SuccEdge->getSUnit();
if (SuccEdge->isWeak()) {
++SuccSU->WeakPredsLeft;
return;
}
++SuccSU->NumPredsLeft;
}
void SIScheduleBlock::releaseSucc(SUnit *SU, SDep *SuccEdge) {
SUnit *SuccSU = SuccEdge->getSUnit();
if (SuccEdge->isWeak()) {
--SuccSU->WeakPredsLeft;
return;
}
#ifndef NDEBUG
if (SuccSU->NumPredsLeft == 0) {
dbgs() << "*** Scheduling failed! ***\n";
SuccSU->dump(DAG);
dbgs() << " has been released too many times!\n";
llvm_unreachable(nullptr);
}
#endif
--SuccSU->NumPredsLeft;
}
void SIScheduleBlock::releaseSuccessors(SUnit *SU, bool InOrOutBlock) {
for (SDep& Succ : SU->Succs) {
SUnit *SuccSU = Succ.getSUnit();
if (BC->isSUInBlock(SuccSU, ID) != InOrOutBlock)
continue;
releaseSucc(SU, &Succ);
if (SuccSU->NumPredsLeft == 0 && InOrOutBlock)
TopReadySUs.push_back(SuccSU);
}
}
void SIScheduleBlock::nodeScheduled(SUnit *SU) {
assert (!SU->NumPredsLeft);
std::vector<SUnit*>::iterator I =
std::find(TopReadySUs.begin(), TopReadySUs.end(), SU);
if (I == TopReadySUs.end()) {
dbgs() << "Data Structure Bug in SI Scheduler\n";
llvm_unreachable(nullptr);
}
TopReadySUs.erase(I);
releaseSuccessors(SU, true);
if (HasLowLatencyNonWaitedParent[NodeNum2Index[SU->NodeNum]])
HasLowLatencyNonWaitedParent.assign(SUnits.size(), 0);
if (DAG->IsLowLatencySU[SU->NodeNum]) {
for (SDep& Succ : SU->Succs) {
std::map<unsigned, unsigned>::iterator I =
NodeNum2Index.find(Succ.getSUnit()->NodeNum);
if (I != NodeNum2Index.end())
HasLowLatencyNonWaitedParent[I->second] = 1;
}
}
SU->isScheduled = true;
}
void SIScheduleBlock::finalizeUnits() {
for (SUnit* SU : SUnits) {
releaseSuccessors(SU, false);
if (DAG->IsHighLatencySU[SU->NodeNum])
HighLatencyBlock = true;
}
HasLowLatencyNonWaitedParent.resize(SUnits.size(), 0);
}
void SIScheduleBlock::addPred(SIScheduleBlock *Pred) {
unsigned PredID = Pred->getID();
for (SIScheduleBlock* P : Preds) {
if (PredID == P->getID())
return;
}
Preds.push_back(Pred);
#ifndef NDEBUG
for (SIScheduleBlock* S : Succs) {
if (PredID == S->getID())
assert(!"Loop in the Block Graph!\n");
}
#endif
}
void SIScheduleBlock::addSucc(SIScheduleBlock *Succ) {
unsigned SuccID = Succ->getID();
for (SIScheduleBlock* S : Succs) {
if (SuccID == S->getID())
return;
}
if (Succ->isHighLatencyBlock())
++NumHighLatencySuccessors;
Succs.push_back(Succ);
#ifndef NDEBUG
for (SIScheduleBlock* P : Preds) {
if (SuccID == P->getID())
assert("Loop in the Block Graph!\n");
}
#endif
}
#ifndef NDEBUG
void SIScheduleBlock::printDebug(bool full) {
dbgs() << "Block (" << ID << ")\n";
if (!full)
return;
dbgs() << "\nContains High Latency Instruction: "
<< HighLatencyBlock << '\n';
dbgs() << "\nDepends On:\n";
for (SIScheduleBlock* P : Preds) {
P->printDebug(false);
}
dbgs() << "\nSuccessors:\n";
for (SIScheduleBlock* S : Succs) {
S->printDebug(false);
}
if (Scheduled) {
dbgs() << "LiveInPressure " << LiveInPressure[DAG->getSGPRSetID()] << ' '
<< LiveInPressure[DAG->getVGPRSetID()] << '\n';
dbgs() << "LiveOutPressure " << LiveOutPressure[DAG->getSGPRSetID()] << ' '
<< LiveOutPressure[DAG->getVGPRSetID()] << "\n\n";
dbgs() << "LiveIns:\n";
for (unsigned Reg : LiveInRegs)
dbgs() << PrintVRegOrUnit(Reg, DAG->getTRI()) << ' ';
dbgs() << "\nLiveOuts:\n";
for (unsigned Reg : LiveOutRegs)
dbgs() << PrintVRegOrUnit(Reg, DAG->getTRI()) << ' ';
}
dbgs() << "\nInstructions:\n";
if (!Scheduled) {
for (SUnit* SU : SUnits) {
SU->dump(DAG);
}
} else {
for (SUnit* SU : SUnits) {
SU->dump(DAG);
}
}
dbgs() << "///////////////////////\n";
}
#endif
SIScheduleBlockCreator::SIScheduleBlockCreator(SIScheduleDAGMI *DAG) :
DAG(DAG) {
}
SIScheduleBlockCreator::~SIScheduleBlockCreator() {
}
SIScheduleBlocks
SIScheduleBlockCreator::getBlocks(SISchedulerBlockCreatorVariant BlockVariant) {
std::map<SISchedulerBlockCreatorVariant, SIScheduleBlocks>::iterator B =
Blocks.find(BlockVariant);
if (B == Blocks.end()) {
SIScheduleBlocks Res;
createBlocksForVariant(BlockVariant);
topologicalSort();
scheduleInsideBlocks();
fillStats();
Res.Blocks = CurrentBlocks;
Res.TopDownIndex2Block = TopDownIndex2Block;
Res.TopDownBlock2Index = TopDownBlock2Index;
Blocks[BlockVariant] = Res;
return Res;
} else {
return B->second;
}
}
bool SIScheduleBlockCreator::isSUInBlock(SUnit *SU, unsigned ID) {
if (SU->NodeNum >= DAG->SUnits.size())
return false;
return CurrentBlocks[Node2CurrentBlock[SU->NodeNum]]->getID() == ID;
}
void SIScheduleBlockCreator::colorHighLatenciesAlone() {
unsigned DAGSize = DAG->SUnits.size();
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SUnit *SU = &DAG->SUnits[i];
if (DAG->IsHighLatencySU[SU->NodeNum]) {
CurrentColoring[SU->NodeNum] = NextReservedID++;
}
}
}
void SIScheduleBlockCreator::colorHighLatenciesGroups() {
unsigned DAGSize = DAG->SUnits.size();
unsigned NumHighLatencies = 0;
unsigned GroupSize;
unsigned Color = NextReservedID;
unsigned Count = 0;
std::set<unsigned> FormingGroup;
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SUnit *SU = &DAG->SUnits[i];
if (DAG->IsHighLatencySU[SU->NodeNum])
++NumHighLatencies;
}
if (NumHighLatencies == 0)
return;
if (NumHighLatencies <= 6)
GroupSize = 2;
else if (NumHighLatencies <= 12)
GroupSize = 3;
else
GroupSize = 4;
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SUnit *SU = &DAG->SUnits[i];
if (DAG->IsHighLatencySU[SU->NodeNum]) {
unsigned CompatibleGroup = true;
unsigned ProposedColor = Color;
for (unsigned j : FormingGroup) {
if (!DAG->canAddEdge(SU, &DAG->SUnits[j]) ||
!DAG->canAddEdge(&DAG->SUnits[j], SU))
CompatibleGroup = false;
}
if (!CompatibleGroup || ++Count == GroupSize) {
FormingGroup.clear();
Color = ++NextReservedID;
if (!CompatibleGroup) {
ProposedColor = Color;
FormingGroup.insert(SU->NodeNum);
}
Count = 0;
} else {
FormingGroup.insert(SU->NodeNum);
}
CurrentColoring[SU->NodeNum] = ProposedColor;
}
}
}
void SIScheduleBlockCreator::colorComputeReservedDependencies() {
unsigned DAGSize = DAG->SUnits.size();
std::map<std::set<unsigned>, unsigned> ColorCombinations;
CurrentTopDownReservedDependencyColoring.clear();
CurrentBottomUpReservedDependencyColoring.clear();
CurrentTopDownReservedDependencyColoring.resize(DAGSize, 0);
CurrentBottomUpReservedDependencyColoring.resize(DAGSize, 0);
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SUnit *SU = &DAG->SUnits[DAG->TopDownIndex2SU[i]];
std::set<unsigned> SUColors;
if (CurrentColoring[SU->NodeNum]) {
CurrentTopDownReservedDependencyColoring[SU->NodeNum] =
CurrentColoring[SU->NodeNum];
continue;
}
for (SDep& PredDep : SU->Preds) {
SUnit *Pred = PredDep.getSUnit();
if (PredDep.isWeak() || Pred->NodeNum >= DAGSize)
continue;
if (CurrentTopDownReservedDependencyColoring[Pred->NodeNum] > 0)
SUColors.insert(CurrentTopDownReservedDependencyColoring[Pred->NodeNum]);
}
if (SUColors.empty())
continue;
if (SUColors.size() == 1 && *SUColors.begin() > DAGSize)
CurrentTopDownReservedDependencyColoring[SU->NodeNum] =
*SUColors.begin();
else {
std::map<std::set<unsigned>, unsigned>::iterator Pos =
ColorCombinations.find(SUColors);
if (Pos != ColorCombinations.end()) {
CurrentTopDownReservedDependencyColoring[SU->NodeNum] = Pos->second;
} else {
CurrentTopDownReservedDependencyColoring[SU->NodeNum] =
NextNonReservedID;
ColorCombinations[SUColors] = NextNonReservedID++;
}
}
}
ColorCombinations.clear();
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SUnit *SU = &DAG->SUnits[DAG->BottomUpIndex2SU[i]];
std::set<unsigned> SUColors;
if (CurrentColoring[SU->NodeNum]) {
CurrentBottomUpReservedDependencyColoring[SU->NodeNum] =
CurrentColoring[SU->NodeNum];
continue;
}
for (SDep& SuccDep : SU->Succs) {
SUnit *Succ = SuccDep.getSUnit();
if (SuccDep.isWeak() || Succ->NodeNum >= DAGSize)
continue;
if (CurrentBottomUpReservedDependencyColoring[Succ->NodeNum] > 0)
SUColors.insert(CurrentBottomUpReservedDependencyColoring[Succ->NodeNum]);
}
if (SUColors.empty())
continue;
if (SUColors.size() == 1 && *SUColors.begin() > DAGSize)
CurrentBottomUpReservedDependencyColoring[SU->NodeNum] =
*SUColors.begin();
else {
std::map<std::set<unsigned>, unsigned>::iterator Pos =
ColorCombinations.find(SUColors);
if (Pos != ColorCombinations.end()) {
CurrentBottomUpReservedDependencyColoring[SU->NodeNum] = Pos->second;
} else {
CurrentBottomUpReservedDependencyColoring[SU->NodeNum] =
NextNonReservedID;
ColorCombinations[SUColors] = NextNonReservedID++;
}
}
}
}
void SIScheduleBlockCreator::colorAccordingToReservedDependencies() {
unsigned DAGSize = DAG->SUnits.size();
std::map<std::pair<unsigned, unsigned>, unsigned> ColorCombinations;
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SUnit *SU = &DAG->SUnits[i];
std::pair<unsigned, unsigned> SUColors;
if (CurrentColoring[SU->NodeNum])
continue;
SUColors.first = CurrentTopDownReservedDependencyColoring[SU->NodeNum];
SUColors.second = CurrentBottomUpReservedDependencyColoring[SU->NodeNum];
std::map<std::pair<unsigned, unsigned>, unsigned>::iterator Pos =
ColorCombinations.find(SUColors);
if (Pos != ColorCombinations.end()) {
CurrentColoring[SU->NodeNum] = Pos->second;
} else {
CurrentColoring[SU->NodeNum] = NextNonReservedID;
ColorCombinations[SUColors] = NextNonReservedID++;
}
}
}
void SIScheduleBlockCreator::colorEndsAccordingToDependencies() {
unsigned DAGSize = DAG->SUnits.size();
std::vector<int> PendingColoring = CurrentColoring;
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SUnit *SU = &DAG->SUnits[DAG->BottomUpIndex2SU[i]];
std::set<unsigned> SUColors;
std::set<unsigned> SUColorsPending;
if (CurrentColoring[SU->NodeNum] <= (int)DAGSize)
continue;
if (CurrentBottomUpReservedDependencyColoring[SU->NodeNum] > 0 ||
CurrentTopDownReservedDependencyColoring[SU->NodeNum] > 0)
continue;
for (SDep& SuccDep : SU->Succs) {
SUnit *Succ = SuccDep.getSUnit();
if (SuccDep.isWeak() || Succ->NodeNum >= DAGSize)
continue;
if (CurrentBottomUpReservedDependencyColoring[Succ->NodeNum] > 0 ||
CurrentTopDownReservedDependencyColoring[Succ->NodeNum] > 0)
SUColors.insert(CurrentColoring[Succ->NodeNum]);
SUColorsPending.insert(PendingColoring[Succ->NodeNum]);
}
if (SUColors.size() == 1 && SUColorsPending.size() == 1)
PendingColoring[SU->NodeNum] = *SUColors.begin();
else PendingColoring[SU->NodeNum] = NextNonReservedID++;
}
CurrentColoring = PendingColoring;
}
void SIScheduleBlockCreator::colorForceConsecutiveOrderInGroup() {
unsigned DAGSize = DAG->SUnits.size();
unsigned PreviousColor;
std::set<unsigned> SeenColors;
if (DAGSize <= 1)
return;
PreviousColor = CurrentColoring[0];
for (unsigned i = 1, e = DAGSize; i != e; ++i) {
SUnit *SU = &DAG->SUnits[i];
unsigned CurrentColor = CurrentColoring[i];
unsigned PreviousColorSave = PreviousColor;
assert(i == SU->NodeNum);
if (CurrentColor != PreviousColor)
SeenColors.insert(PreviousColor);
PreviousColor = CurrentColor;
if (CurrentColoring[SU->NodeNum] <= (int)DAGSize)
continue;
if (SeenColors.find(CurrentColor) == SeenColors.end())
continue;
if (PreviousColorSave != CurrentColor)
CurrentColoring[i] = NextNonReservedID++;
else
CurrentColoring[i] = CurrentColoring[i-1];
}
}
void SIScheduleBlockCreator::colorMergeConstantLoadsNextGroup() {
unsigned DAGSize = DAG->SUnits.size();
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SUnit *SU = &DAG->SUnits[DAG->BottomUpIndex2SU[i]];
std::set<unsigned> SUColors;
if (CurrentColoring[SU->NodeNum] <= (int)DAGSize)
continue;
if (SU->Preds.size() > 0 && !DAG->IsLowLatencySU[SU->NodeNum])
continue;
for (SDep& SuccDep : SU->Succs) {
SUnit *Succ = SuccDep.getSUnit();
if (SuccDep.isWeak() || Succ->NodeNum >= DAGSize)
continue;
SUColors.insert(CurrentColoring[Succ->NodeNum]);
}
if (SUColors.size() == 1)
CurrentColoring[SU->NodeNum] = *SUColors.begin();
}
}
void SIScheduleBlockCreator::colorMergeIfPossibleNextGroup() {
unsigned DAGSize = DAG->SUnits.size();
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SUnit *SU = &DAG->SUnits[DAG->BottomUpIndex2SU[i]];
std::set<unsigned> SUColors;
if (CurrentColoring[SU->NodeNum] <= (int)DAGSize)
continue;
for (SDep& SuccDep : SU->Succs) {
SUnit *Succ = SuccDep.getSUnit();
if (SuccDep.isWeak() || Succ->NodeNum >= DAGSize)
continue;
SUColors.insert(CurrentColoring[Succ->NodeNum]);
}
if (SUColors.size() == 1)
CurrentColoring[SU->NodeNum] = *SUColors.begin();
}
}
void SIScheduleBlockCreator::colorMergeIfPossibleNextGroupOnlyForReserved() {
unsigned DAGSize = DAG->SUnits.size();
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SUnit *SU = &DAG->SUnits[DAG->BottomUpIndex2SU[i]];
std::set<unsigned> SUColors;
if (CurrentColoring[SU->NodeNum] <= (int)DAGSize)
continue;
for (SDep& SuccDep : SU->Succs) {
SUnit *Succ = SuccDep.getSUnit();
if (SuccDep.isWeak() || Succ->NodeNum >= DAGSize)
continue;
SUColors.insert(CurrentColoring[Succ->NodeNum]);
}
if (SUColors.size() == 1 && *SUColors.begin() <= DAGSize)
CurrentColoring[SU->NodeNum] = *SUColors.begin();
}
}
void SIScheduleBlockCreator::colorMergeIfPossibleSmallGroupsToNextGroup() {
unsigned DAGSize = DAG->SUnits.size();
std::map<unsigned, unsigned> ColorCount;
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SUnit *SU = &DAG->SUnits[DAG->BottomUpIndex2SU[i]];
unsigned color = CurrentColoring[SU->NodeNum];
std::map<unsigned, unsigned>::iterator Pos = ColorCount.find(color);
if (Pos != ColorCount.end()) {
++ColorCount[color];
} else {
ColorCount[color] = 1;
}
}
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SUnit *SU = &DAG->SUnits[DAG->BottomUpIndex2SU[i]];
unsigned color = CurrentColoring[SU->NodeNum];
std::set<unsigned> SUColors;
if (CurrentColoring[SU->NodeNum] <= (int)DAGSize)
continue;
if (ColorCount[color] > 1)
continue;
for (SDep& SuccDep : SU->Succs) {
SUnit *Succ = SuccDep.getSUnit();
if (SuccDep.isWeak() || Succ->NodeNum >= DAGSize)
continue;
SUColors.insert(CurrentColoring[Succ->NodeNum]);
}
if (SUColors.size() == 1 && *SUColors.begin() != color) {
--ColorCount[color];
CurrentColoring[SU->NodeNum] = *SUColors.begin();
++ColorCount[*SUColors.begin()];
}
}
}
void SIScheduleBlockCreator::cutHugeBlocks() {
}
void SIScheduleBlockCreator::regroupNoUserInstructions() {
unsigned DAGSize = DAG->SUnits.size();
int GroupID = NextNonReservedID++;
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SUnit *SU = &DAG->SUnits[DAG->BottomUpIndex2SU[i]];
bool hasSuccessor = false;
if (CurrentColoring[SU->NodeNum] <= (int)DAGSize)
continue;
for (SDep& SuccDep : SU->Succs) {
SUnit *Succ = SuccDep.getSUnit();
if (SuccDep.isWeak() || Succ->NodeNum >= DAGSize)
continue;
hasSuccessor = true;
}
if (!hasSuccessor)
CurrentColoring[SU->NodeNum] = GroupID;
}
}
void SIScheduleBlockCreator::createBlocksForVariant(SISchedulerBlockCreatorVariant BlockVariant) {
unsigned DAGSize = DAG->SUnits.size();
std::map<unsigned,unsigned> RealID;
CurrentBlocks.clear();
CurrentColoring.clear();
CurrentColoring.resize(DAGSize, 0);
Node2CurrentBlock.clear();
DAG->restoreSULinksLeft();
NextReservedID = 1;
NextNonReservedID = DAGSize + 1;
DEBUG(dbgs() << "Coloring the graph\n");
if (BlockVariant == SISchedulerBlockCreatorVariant::LatenciesGrouped)
colorHighLatenciesGroups();
else
colorHighLatenciesAlone();
colorComputeReservedDependencies();
colorAccordingToReservedDependencies();
colorEndsAccordingToDependencies();
if (BlockVariant == SISchedulerBlockCreatorVariant::LatenciesAlonePlusConsecutive)
colorForceConsecutiveOrderInGroup();
regroupNoUserInstructions();
colorMergeConstantLoadsNextGroup();
colorMergeIfPossibleNextGroupOnlyForReserved();
Node2CurrentBlock.resize(DAGSize, -1);
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SUnit *SU = &DAG->SUnits[i];
unsigned Color = CurrentColoring[SU->NodeNum];
if (RealID.find(Color) == RealID.end()) {
int ID = CurrentBlocks.size();
BlockPtrs.push_back(
make_unique<SIScheduleBlock>(DAG, this, ID));
CurrentBlocks.push_back(BlockPtrs.rbegin()->get());
RealID[Color] = ID;
}
CurrentBlocks[RealID[Color]]->addUnit(SU);
Node2CurrentBlock[SU->NodeNum] = RealID[Color];
}
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SUnit *SU = &DAG->SUnits[i];
int SUID = Node2CurrentBlock[i];
for (SDep& SuccDep : SU->Succs) {
SUnit *Succ = SuccDep.getSUnit();
if (SuccDep.isWeak() || Succ->NodeNum >= DAGSize)
continue;
if (Node2CurrentBlock[Succ->NodeNum] != SUID)
CurrentBlocks[SUID]->addSucc(CurrentBlocks[Node2CurrentBlock[Succ->NodeNum]]);
}
for (SDep& PredDep : SU->Preds) {
SUnit *Pred = PredDep.getSUnit();
if (PredDep.isWeak() || Pred->NodeNum >= DAGSize)
continue;
if (Node2CurrentBlock[Pred->NodeNum] != SUID)
CurrentBlocks[SUID]->addPred(CurrentBlocks[Node2CurrentBlock[Pred->NodeNum]]);
}
}
for (unsigned i = 0, e = CurrentBlocks.size(); i != e; ++i) {
SIScheduleBlock *Block = CurrentBlocks[i];
Block->finalizeUnits();
}
DEBUG(
dbgs() << "Blocks created:\n\n";
for (unsigned i = 0, e = CurrentBlocks.size(); i != e; ++i) {
SIScheduleBlock *Block = CurrentBlocks[i];
Block->printDebug(true);
}
);
}
static MachineBasicBlock::const_iterator
nextIfDebug(MachineBasicBlock::const_iterator I,
MachineBasicBlock::const_iterator End) {
for(; I != End; ++I) {
if (!I->isDebugValue())
break;
}
return I;
}
static MachineBasicBlock::iterator
nextIfDebug(MachineBasicBlock::iterator I,
MachineBasicBlock::const_iterator End) {
return MachineBasicBlock::instr_iterator(
const_cast<MachineInstr*>(
&*nextIfDebug(MachineBasicBlock::const_iterator(I), End)));
}
void SIScheduleBlockCreator::topologicalSort() {
unsigned DAGSize = CurrentBlocks.size();
std::vector<int> WorkList;
DEBUG(dbgs() << "Topological Sort\n");
WorkList.reserve(DAGSize);
TopDownIndex2Block.resize(DAGSize);
TopDownBlock2Index.resize(DAGSize);
BottomUpIndex2Block.resize(DAGSize);
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SIScheduleBlock *Block = CurrentBlocks[i];
unsigned Degree = Block->getSuccs().size();
TopDownBlock2Index[i] = Degree;
if (Degree == 0) {
WorkList.push_back(i);
}
}
int Id = DAGSize;
while (!WorkList.empty()) {
int i = WorkList.back();
SIScheduleBlock *Block = CurrentBlocks[i];
WorkList.pop_back();
TopDownBlock2Index[i] = --Id;
TopDownIndex2Block[Id] = i;
for (SIScheduleBlock* Pred : Block->getPreds()) {
if (!--TopDownBlock2Index[Pred->getID()])
WorkList.push_back(Pred->getID());
}
}
#ifndef NDEBUG
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SIScheduleBlock *Block = CurrentBlocks[i];
for (SIScheduleBlock* Pred : Block->getPreds()) {
assert(TopDownBlock2Index[i] > TopDownBlock2Index[Pred->getID()] &&
"Wrong Top Down topological sorting");
}
}
#endif
BottomUpIndex2Block = std::vector<int>(TopDownIndex2Block.rbegin(),
TopDownIndex2Block.rend());
}
void SIScheduleBlockCreator::scheduleInsideBlocks() {
unsigned DAGSize = CurrentBlocks.size();
DEBUG(dbgs() << "\nScheduling Blocks\n\n");
DEBUG(dbgs() << "First phase: Fast scheduling for Reg Liveness\n");
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SIScheduleBlock *Block = CurrentBlocks[i];
Block->fastSchedule();
}
MachineBasicBlock::iterator CurrentTopFastSched = DAG->getCurrentTop();
std::vector<MachineBasicBlock::iterator> PosOld;
std::vector<MachineBasicBlock::iterator> PosNew;
PosOld.reserve(DAG->SUnits.size());
PosNew.reserve(DAG->SUnits.size());
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
int BlockIndice = TopDownIndex2Block[i];
SIScheduleBlock *Block = CurrentBlocks[BlockIndice];
std::vector<SUnit*> SUs = Block->getScheduledUnits();
for (SUnit* SU : SUs) {
MachineInstr *MI = SU->getInstr();
MachineBasicBlock::iterator Pos = MI;
PosOld.push_back(Pos);
if (&*CurrentTopFastSched == MI) {
PosNew.push_back(Pos);
CurrentTopFastSched = nextIfDebug(++CurrentTopFastSched,
DAG->getCurrentBottom());
} else {
DAG->getBB()->splice(CurrentTopFastSched, DAG->getBB(), MI);
DAG->getLIS()->handleMove(MI, true);
PosNew.push_back(CurrentTopFastSched);
}
}
}
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SIScheduleBlock *Block = CurrentBlocks[i];
std::vector<SUnit*> SUs = Block->getScheduledUnits();
Block->schedule((*SUs.begin())->getInstr(), (*SUs.rbegin())->getInstr());
}
DEBUG(dbgs() << "Restoring MI Pos\n");
for (unsigned i = PosOld.size(), e = 0; i != e; --i) {
MachineBasicBlock::iterator POld = PosOld[i-1];
MachineBasicBlock::iterator PNew = PosNew[i-1];
if (PNew != POld) {
DAG->getBB()->splice(POld, DAG->getBB(), PNew);
DAG->getLIS()->handleMove(POld, true);
}
}
DEBUG(
for (unsigned i = 0, e = CurrentBlocks.size(); i != e; ++i) {
SIScheduleBlock *Block = CurrentBlocks[i];
Block->printDebug(true);
}
);
}
void SIScheduleBlockCreator::fillStats() {
unsigned DAGSize = CurrentBlocks.size();
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
int BlockIndice = TopDownIndex2Block[i];
SIScheduleBlock *Block = CurrentBlocks[BlockIndice];
if (Block->getPreds().size() == 0)
Block->Depth = 0;
else {
unsigned Depth = 0;
for (SIScheduleBlock *Pred : Block->getPreds()) {
if (Depth < Pred->Depth + 1)
Depth = Pred->Depth + 1;
}
Block->Depth = Depth;
}
}
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
int BlockIndice = BottomUpIndex2Block[i];
SIScheduleBlock *Block = CurrentBlocks[BlockIndice];
if (Block->getSuccs().size() == 0)
Block->Height = 0;
else {
unsigned Height = 0;
for (SIScheduleBlock *Succ : Block->getSuccs()) {
if (Height < Succ->Height + 1)
Height = Succ->Height + 1;
}
Block->Height = Height;
}
}
}
SIScheduleBlockScheduler::SIScheduleBlockScheduler(SIScheduleDAGMI *DAG,
SISchedulerBlockSchedulerVariant Variant,
SIScheduleBlocks BlocksStruct) :
DAG(DAG), Variant(Variant), Blocks(BlocksStruct.Blocks),
LastPosWaitedHighLatency(0), NumBlockScheduled(0), VregCurrentUsage(0),
SregCurrentUsage(0), maxVregUsage(0), maxSregUsage(0) {
LiveOutRegsNumUsages.resize(Blocks.size());
for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
SIScheduleBlock *Block = Blocks[i];
for (unsigned Reg : Block->getInRegs()) {
bool Found = false;
int topoInd = -1;
for (SIScheduleBlock* Pred: Block->getPreds()) {
std::set<unsigned> PredOutRegs = Pred->getOutRegs();
std::set<unsigned>::iterator RegPos = PredOutRegs.find(Reg);
if (RegPos != PredOutRegs.end()) {
Found = true;
if (topoInd < BlocksStruct.TopDownBlock2Index[Pred->getID()]) {
topoInd = BlocksStruct.TopDownBlock2Index[Pred->getID()];
}
}
}
if (!Found)
continue;
int PredID = BlocksStruct.TopDownIndex2Block[topoInd];
std::map<unsigned, unsigned>::iterator RegPos =
LiveOutRegsNumUsages[PredID].find(Reg);
if (RegPos != LiveOutRegsNumUsages[PredID].end()) {
++LiveOutRegsNumUsages[PredID][Reg];
} else {
LiveOutRegsNumUsages[PredID][Reg] = 1;
}
}
}
LastPosHighLatencyParentScheduled.resize(Blocks.size(), 0);
BlockNumPredsLeft.resize(Blocks.size());
BlockNumSuccsLeft.resize(Blocks.size());
for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
SIScheduleBlock *Block = Blocks[i];
BlockNumPredsLeft[i] = Block->getPreds().size();
BlockNumSuccsLeft[i] = Block->getSuccs().size();
}
#ifndef NDEBUG
for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
SIScheduleBlock *Block = Blocks[i];
assert(Block->getID() == i);
}
#endif
std::set<unsigned> InRegs = DAG->getInRegs();
addLiveRegs(InRegs);
for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
SIScheduleBlock *Block = Blocks[i];
for (unsigned Reg : Block->getInRegs()) {
bool Found = false;
for (SIScheduleBlock* Pred: Block->getPreds()) {
std::set<unsigned> PredOutRegs = Pred->getOutRegs();
std::set<unsigned>::iterator RegPos = PredOutRegs.find(Reg);
if (RegPos != PredOutRegs.end()) {
Found = true;
break;
}
}
if (!Found) {
if (LiveRegsConsumers.find(Reg) == LiveRegsConsumers.end())
LiveRegsConsumers[Reg] = 1;
else
++LiveRegsConsumers[Reg];
}
}
}
for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
SIScheduleBlock *Block = Blocks[i];
if (BlockNumPredsLeft[i] == 0) {
ReadyBlocks.push_back(Block);
}
}
while (SIScheduleBlock *Block = pickBlock()) {
BlocksScheduled.push_back(Block);
blockScheduled(Block);
}
DEBUG(
dbgs() << "Block Order:";
for (SIScheduleBlock* Block : BlocksScheduled) {
dbgs() << ' ' << Block->getID();
}
);
}
bool SIScheduleBlockScheduler::tryCandidateLatency(SIBlockSchedCandidate &Cand,
SIBlockSchedCandidate &TryCand) {
if (!Cand.isValid()) {
TryCand.Reason = NodeOrder;
return true;
}
if (tryLess(TryCand.LastPosHighLatParentScheduled,
Cand.LastPosHighLatParentScheduled, TryCand, Cand, Latency))
return true;
if (tryGreater(TryCand.IsHighLatency, Cand.IsHighLatency,
TryCand, Cand, Latency))
return true;
if (TryCand.IsHighLatency && tryGreater(TryCand.Height, Cand.Height,
TryCand, Cand, Depth))
return true;
if (tryGreater(TryCand.NumHighLatencySuccessors,
Cand.NumHighLatencySuccessors,
TryCand, Cand, Successor))
return true;
return false;
}
bool SIScheduleBlockScheduler::tryCandidateRegUsage(SIBlockSchedCandidate &Cand,
SIBlockSchedCandidate &TryCand) {
if (!Cand.isValid()) {
TryCand.Reason = NodeOrder;
return true;
}
if (tryLess(TryCand.VGPRUsageDiff > 0, Cand.VGPRUsageDiff > 0,
TryCand, Cand, RegUsage))
return true;
if (tryGreater(TryCand.NumSuccessors > 0,
Cand.NumSuccessors > 0,
TryCand, Cand, Successor))
return true;
if (tryGreater(TryCand.Height, Cand.Height, TryCand, Cand, Depth))
return true;
if (tryLess(TryCand.VGPRUsageDiff, Cand.VGPRUsageDiff,
TryCand, Cand, RegUsage))
return true;
return false;
}
SIScheduleBlock *SIScheduleBlockScheduler::pickBlock() {
SIBlockSchedCandidate Cand;
std::vector<SIScheduleBlock*>::iterator Best;
SIScheduleBlock *Block;
if (ReadyBlocks.empty())
return nullptr;
DAG->fillVgprSgprCost(LiveRegs.begin(), LiveRegs.end(),
VregCurrentUsage, SregCurrentUsage);
if (VregCurrentUsage > maxVregUsage)
maxVregUsage = VregCurrentUsage;
if (VregCurrentUsage > maxSregUsage)
maxSregUsage = VregCurrentUsage;
DEBUG(
dbgs() << "Picking New Blocks\n";
dbgs() << "Available: ";
for (SIScheduleBlock* Block : ReadyBlocks)
dbgs() << Block->getID() << ' ';
dbgs() << "\nCurrent Live:\n";
for (unsigned Reg : LiveRegs)
dbgs() << PrintVRegOrUnit(Reg, DAG->getTRI()) << ' ';
dbgs() << '\n';
dbgs() << "Current VGPRs: " << VregCurrentUsage << '\n';
dbgs() << "Current SGPRs: " << SregCurrentUsage << '\n';
);
Cand.Block = nullptr;
for (std::vector<SIScheduleBlock*>::iterator I = ReadyBlocks.begin(),
E = ReadyBlocks.end(); I != E; ++I) {
SIBlockSchedCandidate TryCand;
TryCand.Block = *I;
TryCand.IsHighLatency = TryCand.Block->isHighLatencyBlock();
TryCand.VGPRUsageDiff =
checkRegUsageImpact(TryCand.Block->getInRegs(),
TryCand.Block->getOutRegs())[DAG->getVGPRSetID()];
TryCand.NumSuccessors = TryCand.Block->getSuccs().size();
TryCand.NumHighLatencySuccessors =
TryCand.Block->getNumHighLatencySuccessors();
TryCand.LastPosHighLatParentScheduled =
(unsigned int) std::max<int> (0,
LastPosHighLatencyParentScheduled[TryCand.Block->getID()] -
LastPosWaitedHighLatency);
TryCand.Height = TryCand.Block->Height;
if (VregCurrentUsage > 120 ||
Variant != SISchedulerBlockSchedulerVariant::BlockLatencyRegUsage) {
if (!tryCandidateRegUsage(Cand, TryCand) &&
Variant != SISchedulerBlockSchedulerVariant::BlockRegUsage)
tryCandidateLatency(Cand, TryCand);
} else {
if (!tryCandidateLatency(Cand, TryCand))
tryCandidateRegUsage(Cand, TryCand);
}
if (TryCand.Reason != NoCand) {
Cand.setBest(TryCand);
Best = I;
DEBUG(dbgs() << "Best Current Choice: " << Cand.Block->getID() << ' '
<< getReasonStr(Cand.Reason) << '\n');
}
}
DEBUG(
dbgs() << "Picking: " << Cand.Block->getID() << '\n';
dbgs() << "Is a block with high latency instruction: "
<< (Cand.IsHighLatency ? "yes\n" : "no\n");
dbgs() << "Position of last high latency dependency: "
<< Cand.LastPosHighLatParentScheduled << '\n';
dbgs() << "VGPRUsageDiff: " << Cand.VGPRUsageDiff << '\n';
dbgs() << '\n';
);
Block = Cand.Block;
ReadyBlocks.erase(Best);
return Block;
}
void SIScheduleBlockScheduler::addLiveRegs(std::set<unsigned> &Regs) {
for (unsigned Reg : Regs) {
if (!TargetRegisterInfo::isVirtualRegister(Reg))
continue;
(void) LiveRegs.insert(Reg);
}
}
void SIScheduleBlockScheduler::decreaseLiveRegs(SIScheduleBlock *Block,
std::set<unsigned> &Regs) {
for (unsigned Reg : Regs) {
std::set<unsigned>::iterator Pos = LiveRegs.find(Reg);
assert (Pos != LiveRegs.end() && LiveRegsConsumers.find(Reg) != LiveRegsConsumers.end() &&
LiveRegsConsumers[Reg] >= 1);
--LiveRegsConsumers[Reg];
if (LiveRegsConsumers[Reg] == 0)
LiveRegs.erase(Pos);
}
}
void SIScheduleBlockScheduler::releaseBlockSuccs(SIScheduleBlock *Parent) {
for (SIScheduleBlock* Block : Parent->getSuccs()) {
--BlockNumPredsLeft[Block->getID()];
if (BlockNumPredsLeft[Block->getID()] == 0) {
ReadyBlocks.push_back(Block);
}
if (Parent->isHighLatencyBlock())
LastPosHighLatencyParentScheduled[Block->getID()] = NumBlockScheduled;
}
}
void SIScheduleBlockScheduler::blockScheduled(SIScheduleBlock *Block) {
decreaseLiveRegs(Block, Block->getInRegs());
addLiveRegs(Block->getOutRegs());
releaseBlockSuccs(Block);
for (std::map<unsigned, unsigned>::iterator RegI =
LiveOutRegsNumUsages[Block->getID()].begin(),
E = LiveOutRegsNumUsages[Block->getID()].end(); RegI != E; ++RegI) {
std::pair<unsigned, unsigned> RegP = *RegI;
if (LiveRegsConsumers.find(RegP.first) == LiveRegsConsumers.end())
LiveRegsConsumers[RegP.first] = RegP.second;
else {
assert(LiveRegsConsumers[RegP.first] == 0);
LiveRegsConsumers[RegP.first] += RegP.second;
}
}
if (LastPosHighLatencyParentScheduled[Block->getID()] >
(unsigned)LastPosWaitedHighLatency)
LastPosWaitedHighLatency =
LastPosHighLatencyParentScheduled[Block->getID()];
++NumBlockScheduled;
}
std::vector<int>
SIScheduleBlockScheduler::checkRegUsageImpact(std::set<unsigned> &InRegs,
std::set<unsigned> &OutRegs) {
std::vector<int> DiffSetPressure;
DiffSetPressure.assign(DAG->getTRI()->getNumRegPressureSets(), 0);
for (unsigned Reg : InRegs) {
if (!TargetRegisterInfo::isVirtualRegister(Reg))
continue;
if (LiveRegsConsumers[Reg] > 1)
continue;
PSetIterator PSetI = DAG->getMRI()->getPressureSets(Reg);
for (; PSetI.isValid(); ++PSetI) {
DiffSetPressure[*PSetI] -= PSetI.getWeight();
}
}
for (unsigned Reg : OutRegs) {
if (!TargetRegisterInfo::isVirtualRegister(Reg))
continue;
PSetIterator PSetI = DAG->getMRI()->getPressureSets(Reg);
for (; PSetI.isValid(); ++PSetI) {
DiffSetPressure[*PSetI] += PSetI.getWeight();
}
}
return DiffSetPressure;
}
struct SIScheduleBlockResult
SIScheduler::scheduleVariant(SISchedulerBlockCreatorVariant BlockVariant,
SISchedulerBlockSchedulerVariant ScheduleVariant) {
SIScheduleBlocks Blocks = BlockCreator.getBlocks(BlockVariant);
SIScheduleBlockScheduler Scheduler(DAG, ScheduleVariant, Blocks);
std::vector<SIScheduleBlock*> ScheduledBlocks;
struct SIScheduleBlockResult Res;
ScheduledBlocks = Scheduler.getBlocks();
for (unsigned b = 0; b < ScheduledBlocks.size(); ++b) {
SIScheduleBlock *Block = ScheduledBlocks[b];
std::vector<SUnit*> SUs = Block->getScheduledUnits();
for (SUnit* SU : SUs)
Res.SUs.push_back(SU->NodeNum);
}
Res.MaxSGPRUsage = Scheduler.getSGPRUsage();
Res.MaxVGPRUsage = Scheduler.getVGPRUsage();
return Res;
}
SIScheduleDAGMI::SIScheduleDAGMI(MachineSchedContext *C) :
ScheduleDAGMILive(C, make_unique<GenericScheduler>(C)) {
SITII = static_cast<const SIInstrInfo*>(TII);
SITRI = static_cast<const SIRegisterInfo*>(TRI);
VGPRSetID = SITRI->getVGPR32PressureSet();
SGPRSetID = SITRI->getSGPR32PressureSet();
}
SIScheduleDAGMI::~SIScheduleDAGMI() {
}
ScheduleDAGInstrs *llvm::createSIMachineScheduler(MachineSchedContext *C) {
return new SIScheduleDAGMI(C);
}
void SIScheduleDAGMI::topologicalSort() {
std::vector<int> TopDownSU2Index;
unsigned DAGSize = SUnits.size();
std::vector<SUnit*> WorkList;
DEBUG(dbgs() << "Topological Sort\n");
WorkList.reserve(DAGSize);
TopDownIndex2SU.resize(DAGSize);
TopDownSU2Index.resize(DAGSize);
BottomUpIndex2SU.resize(DAGSize);
WorkList.push_back(&getExitSU());
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SUnit *SU = &SUnits[i];
int NodeNum = SU->NodeNum;
unsigned Degree = SU->Succs.size();
TopDownSU2Index[NodeNum] = Degree;
if (Degree == 0) {
assert(SU->Succs.empty() && "SUnit should have no successors");
WorkList.push_back(SU);
}
}
int Id = DAGSize;
while (!WorkList.empty()) {
SUnit *SU = WorkList.back();
WorkList.pop_back();
if (SU->NodeNum < DAGSize) {
TopDownSU2Index[SU->NodeNum] = --Id;
TopDownIndex2SU[Id] = SU->NodeNum;
}
for (SDep& Pred : SU->Preds) {
SUnit *SU = Pred.getSUnit();
if (SU->NodeNum < DAGSize && !--TopDownSU2Index[SU->NodeNum])
WorkList.push_back(SU);
}
}
BottomUpIndex2SU = std::vector<int>(TopDownIndex2SU.rbegin(),
TopDownIndex2SU.rend());
#ifndef NDEBUG
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SUnit *SU = &SUnits[i];
for (SDep& Pred : SU->Preds) {
if (Pred.getSUnit()->NodeNum >= DAGSize)
continue;
assert(TopDownSU2Index[SU->NodeNum] >
TopDownSU2Index[Pred.getSUnit()->NodeNum] &&
"Wrong Top Down topological sorting");
}
}
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SUnit *SU = &SUnits[i];
for (SDep& Succ : SU->Succs) {
if (Succ.getSUnit()->NodeNum >= DAGSize)
continue;
assert(TopDownSU2Index[SU->NodeNum] <
TopDownSU2Index[Succ.getSUnit()->NodeNum] &&
"Wrong Bottom Up topological sorting");
}
}
#endif
}
void SIScheduleDAGMI::moveLowLatencies() {
unsigned DAGSize = SUnits.size();
int LastLowLatencyUser = -1;
int LastLowLatencyPos = -1;
for (unsigned i = 0, e = ScheduledSUnits.size(); i != e; ++i) {
SUnit *SU = &SUnits[ScheduledSUnits[i]];
bool IsLowLatencyUser = false;
unsigned MinPos = 0;
for (SDep& PredDep : SU->Preds) {
SUnit *Pred = PredDep.getSUnit();
if (SITII->isLowLatencyInstruction(Pred->getInstr())) {
IsLowLatencyUser = true;
}
if (Pred->NodeNum >= DAGSize)
continue;
unsigned PredPos = ScheduledSUnitsInv[Pred->NodeNum];
if (PredPos >= MinPos)
MinPos = PredPos + 1;
}
if (SITII->isLowLatencyInstruction(SU->getInstr())) {
unsigned BestPos = LastLowLatencyUser + 1;
if ((int)BestPos <= LastLowLatencyPos)
BestPos = LastLowLatencyPos + 1;
if (BestPos < MinPos)
BestPos = MinPos;
if (BestPos < i) {
for (unsigned u = i; u > BestPos; --u) {
++ScheduledSUnitsInv[ScheduledSUnits[u-1]];
ScheduledSUnits[u] = ScheduledSUnits[u-1];
}
ScheduledSUnits[BestPos] = SU->NodeNum;
ScheduledSUnitsInv[SU->NodeNum] = BestPos;
}
LastLowLatencyPos = BestPos;
if (IsLowLatencyUser)
LastLowLatencyUser = BestPos;
} else if (IsLowLatencyUser) {
LastLowLatencyUser = i;
} else if (SU->getInstr()->getOpcode() == AMDGPU::COPY) {
bool CopyForLowLat = false;
for (SDep& SuccDep : SU->Succs) {
SUnit *Succ = SuccDep.getSUnit();
if (SITII->isLowLatencyInstruction(Succ->getInstr())) {
CopyForLowLat = true;
}
}
if (!CopyForLowLat)
continue;
if (MinPos < i) {
for (unsigned u = i; u > MinPos; --u) {
++ScheduledSUnitsInv[ScheduledSUnits[u-1]];
ScheduledSUnits[u] = ScheduledSUnits[u-1];
}
ScheduledSUnits[MinPos] = SU->NodeNum;
ScheduledSUnitsInv[SU->NodeNum] = MinPos;
}
}
}
}
void SIScheduleDAGMI::restoreSULinksLeft() {
for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
SUnits[i].isScheduled = false;
SUnits[i].WeakPredsLeft = SUnitsLinksBackup[i].WeakPredsLeft;
SUnits[i].NumPredsLeft = SUnitsLinksBackup[i].NumPredsLeft;
SUnits[i].WeakSuccsLeft = SUnitsLinksBackup[i].WeakSuccsLeft;
SUnits[i].NumSuccsLeft = SUnitsLinksBackup[i].NumSuccsLeft;
}
}
template<typename _Iterator> void
SIScheduleDAGMI::fillVgprSgprCost(_Iterator First, _Iterator End,
unsigned &VgprUsage, unsigned &SgprUsage) {
VgprUsage = 0;
SgprUsage = 0;
for (_Iterator RegI = First; RegI != End; ++RegI) {
unsigned Reg = *RegI;
if (!TargetRegisterInfo::isVirtualRegister(Reg))
continue;
PSetIterator PSetI = MRI.getPressureSets(Reg);
for (; PSetI.isValid(); ++PSetI) {
if (*PSetI == VGPRSetID)
VgprUsage += PSetI.getWeight();
else if (*PSetI == SGPRSetID)
SgprUsage += PSetI.getWeight();
}
}
}
void SIScheduleDAGMI::schedule()
{
SmallVector<SUnit*, 8> TopRoots, BotRoots;
SIScheduleBlockResult Best, Temp;
DEBUG(dbgs() << "Preparing Scheduling\n");
buildDAGWithRegPressure();
DEBUG(
for(SUnit& SU : SUnits)
SU.dumpAll(this)
);
Topo.InitDAGTopologicalSorting();
topologicalSort();
findRootsAndBiasEdges(TopRoots, BotRoots);
SchedImpl->initialize(this);
initQueues(TopRoots, BotRoots);
SUnitsLinksBackup = SUnits;
IsLowLatencySU.clear();
LowLatencyOffset.clear();
IsHighLatencySU.clear();
IsLowLatencySU.resize(SUnits.size(), 0);
LowLatencyOffset.resize(SUnits.size(), 0);
IsHighLatencySU.resize(SUnits.size(), 0);
for (unsigned i = 0, e = (unsigned)SUnits.size(); i != e; ++i) {
SUnit *SU = &SUnits[i];
unsigned BaseLatReg, OffLatReg;
if (SITII->isLowLatencyInstruction(SU->getInstr())) {
IsLowLatencySU[i] = 1;
if (SITII->getMemOpBaseRegImmOfs(SU->getInstr(), BaseLatReg,
OffLatReg, TRI))
LowLatencyOffset[i] = OffLatReg;
} else if (SITII->isHighLatencyInstruction(SU->getInstr()))
IsHighLatencySU[i] = 1;
}
SIScheduler Scheduler(this);
Best = Scheduler.scheduleVariant(SISchedulerBlockCreatorVariant::LatenciesAlone,
SISchedulerBlockSchedulerVariant::BlockLatencyRegUsage);
#if 0 // To enable when handleMove fix lands
if (Best.MaxVGPRUsage > 180) {
std::vector<std::pair<SISchedulerBlockCreatorVariant, SISchedulerBlockSchedulerVariant>> Variants = {
{ LatenciesAlone, BlockRegUsageLatency },
{ LatenciesGrouped, BlockLatencyRegUsage },
{ LatenciesAlonePlusConsecutive, BlockLatencyRegUsage },
};
for (std::pair<SISchedulerBlockCreatorVariant, SISchedulerBlockSchedulerVariant> v : Variants) {
Temp = Scheduler.scheduleVariant(v.first, v.second);
if (Temp.MaxVGPRUsage < Best.MaxVGPRUsage)
Best = Temp;
}
}
if (Best.MaxVGPRUsage > 200) {
std::vector<std::pair<SISchedulerBlockCreatorVariant, SISchedulerBlockSchedulerVariant>> Variants = {
{ LatenciesAlone, BlockRegUsage },
{ LatenciesGrouped, BlockRegUsageLatency },
{ LatenciesGrouped, BlockRegUsage },
{ LatenciesAlonePlusConsecutive, BlockRegUsageLatency },
{ LatenciesAlonePlusConsecutive, BlockRegUsage }
};
for (std::pair<SISchedulerBlockCreatorVariant, SISchedulerBlockSchedulerVariant> v : Variants) {
Temp = Scheduler.scheduleVariant(v.first, v.second);
if (Temp.MaxVGPRUsage < Best.MaxVGPRUsage)
Best = Temp;
}
}
#endif
ScheduledSUnits = Best.SUs;
ScheduledSUnitsInv.resize(SUnits.size());
for (unsigned i = 0, e = (unsigned)SUnits.size(); i != e; ++i) {
ScheduledSUnitsInv[ScheduledSUnits[i]] = i;
}
moveLowLatencies();
assert(TopRPTracker.getPos() == RegionBegin && "bad initial Top tracker");
TopRPTracker.setPos(CurrentTop);
for (std::vector<unsigned>::iterator I = ScheduledSUnits.begin(),
E = ScheduledSUnits.end(); I != E; ++I) {
SUnit *SU = &SUnits[*I];
scheduleMI(SU, true);
DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") "
<< *SU->getInstr());
}
assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
placeDebugValues();
DEBUG({
unsigned BBNum = begin()->getParent()->getNumber();
dbgs() << "*** Final schedule for BB#" << BBNum << " ***\n";
dumpSchedule();
dbgs() << '\n';
});
}