MachineScheduler.cpp [plain text]
#include "llvm/CodeGen/MachineScheduler.h"
#include "llvm/ADT/PriorityQueue.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/ScheduleDFS.h"
#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/GraphWriter.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include <queue>
using namespace llvm;
#define DEBUG_TYPE "misched"
namespace llvm {
cl::opt<bool> ForceTopDown("misched-topdown", cl::Hidden,
cl::desc("Force top-down list scheduling"));
cl::opt<bool> ForceBottomUp("misched-bottomup", cl::Hidden,
cl::desc("Force bottom-up list scheduling"));
cl::opt<bool>
DumpCriticalPathLength("misched-dcpl", cl::Hidden,
cl::desc("Print critical path length to stdout"));
}
#ifndef NDEBUG
static cl::opt<bool> ViewMISchedDAGs("view-misched-dags", cl::Hidden,
cl::desc("Pop up a window to show MISched dags after they are processed"));
static cl::opt<unsigned> ViewMISchedCutoff("view-misched-cutoff", cl::Hidden,
cl::desc("Hide nodes with more predecessor/successor than cutoff"));
static cl::opt<unsigned> MISchedCutoff("misched-cutoff", cl::Hidden,
cl::desc("Stop scheduling after N instructions"), cl::init(~0U));
static cl::opt<std::string> SchedOnlyFunc("misched-only-func", cl::Hidden,
cl::desc("Only schedule this function"));
static cl::opt<unsigned> SchedOnlyBlock("misched-only-block", cl::Hidden,
cl::desc("Only schedule this MBB#"));
#else
static bool ViewMISchedDAGs = false;
#endif // NDEBUG
static cl::opt<bool> EnableRegPressure("misched-regpressure", cl::Hidden,
cl::desc("Enable register pressure scheduling."), cl::init(true));
static cl::opt<bool> EnableCyclicPath("misched-cyclicpath", cl::Hidden,
cl::desc("Enable cyclic critical path analysis."), cl::init(true));
static cl::opt<bool> EnableLoadCluster("misched-cluster", cl::Hidden,
cl::desc("Enable load clustering."), cl::init(true));
static cl::opt<bool> EnableMacroFusion("misched-fusion", cl::Hidden,
cl::desc("Enable scheduling for macro fusion."), cl::init(true));
static cl::opt<bool> VerifyScheduling("verify-misched", cl::Hidden,
cl::desc("Verify machine instrs before and after machine scheduling"));
static const unsigned MinSubtreeSize = 8;
void MachineSchedStrategy::anchor() {}
void ScheduleDAGMutation::anchor() {}
MachineSchedContext::MachineSchedContext():
MF(nullptr), MLI(nullptr), MDT(nullptr), PassConfig(nullptr), AA(nullptr), LIS(nullptr) {
RegClassInfo = new RegisterClassInfo();
}
MachineSchedContext::~MachineSchedContext() {
delete RegClassInfo;
}
namespace {
class MachineSchedulerBase : public MachineSchedContext,
public MachineFunctionPass {
public:
MachineSchedulerBase(char &ID): MachineFunctionPass(ID) {}
void print(raw_ostream &O, const Module* = nullptr) const override;
protected:
void scheduleRegions(ScheduleDAGInstrs &Scheduler, bool FixKillFlags);
};
class MachineScheduler : public MachineSchedulerBase {
public:
MachineScheduler();
void getAnalysisUsage(AnalysisUsage &AU) const override;
bool runOnMachineFunction(MachineFunction&) override;
static char ID;
protected:
ScheduleDAGInstrs *createMachineScheduler();
};
class PostMachineScheduler : public MachineSchedulerBase {
public:
PostMachineScheduler();
void getAnalysisUsage(AnalysisUsage &AU) const override;
bool runOnMachineFunction(MachineFunction&) override;
static char ID;
protected:
ScheduleDAGInstrs *createPostMachineScheduler();
};
}
char MachineScheduler::ID = 0;
char &llvm::MachineSchedulerID = MachineScheduler::ID;
INITIALIZE_PASS_BEGIN(MachineScheduler, "machine-scheduler",
"Machine Instruction Scheduler", false, false)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
INITIALIZE_PASS_END(MachineScheduler, "machine-scheduler",
"Machine Instruction Scheduler", false, false)
MachineScheduler::MachineScheduler()
: MachineSchedulerBase(ID) {
initializeMachineSchedulerPass(*PassRegistry::getPassRegistry());
}
void MachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
AU.addRequiredID(MachineDominatorsID);
AU.addRequired<MachineLoopInfo>();
AU.addRequired<AAResultsWrapperPass>();
AU.addRequired<TargetPassConfig>();
AU.addRequired<SlotIndexes>();
AU.addPreserved<SlotIndexes>();
AU.addRequired<LiveIntervals>();
AU.addPreserved<LiveIntervals>();
MachineFunctionPass::getAnalysisUsage(AU);
}
char PostMachineScheduler::ID = 0;
char &llvm::PostMachineSchedulerID = PostMachineScheduler::ID;
INITIALIZE_PASS(PostMachineScheduler, "postmisched",
"PostRA Machine Instruction Scheduler", false, false)
PostMachineScheduler::PostMachineScheduler()
: MachineSchedulerBase(ID) {
initializePostMachineSchedulerPass(*PassRegistry::getPassRegistry());
}
void PostMachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
AU.addRequiredID(MachineDominatorsID);
AU.addRequired<MachineLoopInfo>();
AU.addRequired<TargetPassConfig>();
MachineFunctionPass::getAnalysisUsage(AU);
}
MachinePassRegistry MachineSchedRegistry::Registry;
static ScheduleDAGInstrs *useDefaultMachineSched(MachineSchedContext *C) {
return nullptr;
}
static cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false,
RegisterPassParser<MachineSchedRegistry> >
MachineSchedOpt("misched",
cl::init(&useDefaultMachineSched), cl::Hidden,
cl::desc("Machine instruction scheduler to use"));
static MachineSchedRegistry
DefaultSchedRegistry("default", "Use the target's default scheduler choice.",
useDefaultMachineSched);
static cl::opt<bool> EnableMachineSched(
"enable-misched",
cl::desc("Enable the machine instruction scheduling pass."), cl::init(true),
cl::Hidden);
static ScheduleDAGInstrs *createGenericSchedLive(MachineSchedContext *C);
static ScheduleDAGInstrs *createGenericSchedPostRA(MachineSchedContext *C);
static MachineBasicBlock::const_iterator
priorNonDebug(MachineBasicBlock::const_iterator I,
MachineBasicBlock::const_iterator Beg) {
assert(I != Beg && "reached the top of the region, cannot decrement");
while (--I != Beg) {
if (!I->isDebugValue())
break;
}
return I;
}
static MachineBasicBlock::iterator
priorNonDebug(MachineBasicBlock::iterator I,
MachineBasicBlock::const_iterator Beg) {
return const_cast<MachineInstr*>(
&*priorNonDebug(MachineBasicBlock::const_iterator(I), Beg));
}
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)));
}
ScheduleDAGInstrs *MachineScheduler::createMachineScheduler() {
MachineSchedRegistry::ScheduleDAGCtor Ctor = MachineSchedOpt;
if (Ctor != useDefaultMachineSched)
return Ctor(this);
ScheduleDAGInstrs *Scheduler = PassConfig->createMachineScheduler(this);
if (Scheduler)
return Scheduler;
return createGenericSchedLive(this);
}
ScheduleDAGInstrs *PostMachineScheduler::createPostMachineScheduler() {
ScheduleDAGInstrs *Scheduler = PassConfig->createPostMachineScheduler(this);
if (Scheduler)
return Scheduler;
return createGenericSchedPostRA(this);
}
bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) {
if (EnableMachineSched.getNumOccurrences()) {
if (!EnableMachineSched)
return false;
} else if (!mf.getSubtarget().enableMachineScheduler())
return false;
DEBUG(dbgs() << "Before MISched:\n"; mf.print(dbgs()));
MF = &mf;
MLI = &getAnalysis<MachineLoopInfo>();
MDT = &getAnalysis<MachineDominatorTree>();
PassConfig = &getAnalysis<TargetPassConfig>();
AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
LIS = &getAnalysis<LiveIntervals>();
if (VerifyScheduling) {
DEBUG(LIS->dump());
MF->verify(this, "Before machine scheduling.");
}
RegClassInfo->runOnMachineFunction(*MF);
std::unique_ptr<ScheduleDAGInstrs> Scheduler(createMachineScheduler());
scheduleRegions(*Scheduler, false);
DEBUG(LIS->dump());
if (VerifyScheduling)
MF->verify(this, "After machine scheduling.");
return true;
}
bool PostMachineScheduler::runOnMachineFunction(MachineFunction &mf) {
if (skipOptnoneFunction(*mf.getFunction()))
return false;
if (!mf.getSubtarget().enablePostRAScheduler()) {
DEBUG(dbgs() << "Subtarget disables post-MI-sched.\n");
return false;
}
DEBUG(dbgs() << "Before post-MI-sched:\n"; mf.print(dbgs()));
MF = &mf;
PassConfig = &getAnalysis<TargetPassConfig>();
if (VerifyScheduling)
MF->verify(this, "Before post machine scheduling.");
std::unique_ptr<ScheduleDAGInstrs> Scheduler(createPostMachineScheduler());
scheduleRegions(*Scheduler, true);
if (VerifyScheduling)
MF->verify(this, "After post machine scheduling.");
return true;
}
static bool isSchedBoundary(MachineBasicBlock::iterator MI,
MachineBasicBlock *MBB,
MachineFunction *MF,
const TargetInstrInfo *TII) {
return MI->isCall() || TII->isSchedulingBoundary(MI, MBB, *MF);
}
void MachineSchedulerBase::scheduleRegions(ScheduleDAGInstrs &Scheduler,
bool FixKillFlags) {
const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end();
MBB != MBBEnd; ++MBB) {
Scheduler.startBlock(&*MBB);
#ifndef NDEBUG
if (SchedOnlyFunc.getNumOccurrences() && SchedOnlyFunc != MF->getName())
continue;
if (SchedOnlyBlock.getNumOccurrences()
&& (int)SchedOnlyBlock != MBB->getNumber())
continue;
#endif
unsigned RemainingInstrs = std::distance(MBB->begin(), MBB->end());
for(MachineBasicBlock::iterator RegionEnd = MBB->end();
RegionEnd != MBB->begin(); RegionEnd = Scheduler.begin()) {
if (RegionEnd != MBB->end() ||
isSchedBoundary(&*std::prev(RegionEnd), &*MBB, MF, TII)) {
--RegionEnd;
--RemainingInstrs;
}
unsigned NumRegionInstrs = 0;
MachineBasicBlock::iterator I = RegionEnd;
for(;I != MBB->begin(); --I, --RemainingInstrs) {
if (isSchedBoundary(&*std::prev(I), &*MBB, MF, TII))
break;
if (!I->isDebugValue())
++NumRegionInstrs;
}
Scheduler.enterRegion(&*MBB, I, RegionEnd, NumRegionInstrs);
if (I == RegionEnd || I == std::prev(RegionEnd)) {
Scheduler.exitRegion();
continue;
}
DEBUG(dbgs() << "********** MI Scheduling **********\n");
DEBUG(dbgs() << MF->getName()
<< ":BB#" << MBB->getNumber() << " " << MBB->getName()
<< "\n From: " << *I << " To: ";
if (RegionEnd != MBB->end()) dbgs() << *RegionEnd;
else dbgs() << "End";
dbgs() << " RegionInstrs: " << NumRegionInstrs
<< " Remaining: " << RemainingInstrs << "\n");
if (DumpCriticalPathLength) {
errs() << MF->getName();
errs() << ":BB# " << MBB->getNumber();
errs() << " " << MBB->getName() << " \n";
}
Scheduler.schedule();
Scheduler.exitRegion();
RegionEnd = Scheduler.begin();
}
assert(RemainingInstrs == 0 && "Instruction count mismatch!");
Scheduler.finishBlock();
if (FixKillFlags)
Scheduler.fixupKills(&*MBB);
}
Scheduler.finalizeSchedule();
}
void MachineSchedulerBase::print(raw_ostream &O, const Module* m) const {
}
LLVM_DUMP_METHOD
void ReadyQueue::dump() {
dbgs() << "Queue " << Name << ": ";
for (unsigned i = 0, e = Queue.size(); i < e; ++i)
dbgs() << Queue[i]->NodeNum << " ";
dbgs() << "\n";
}
ScheduleDAGMI::~ScheduleDAGMI() {
}
bool ScheduleDAGMI::canAddEdge(SUnit *SuccSU, SUnit *PredSU) {
return SuccSU == &ExitSU || !Topo.IsReachable(PredSU, SuccSU);
}
bool ScheduleDAGMI::addEdge(SUnit *SuccSU, const SDep &PredDep) {
if (SuccSU != &ExitSU) {
if (Topo.IsReachable(PredDep.getSUnit(), SuccSU))
return false;
Topo.AddPred(SuccSU, PredDep.getSUnit());
}
SuccSU->addPred(PredDep, !PredDep.isArtificial());
return true;
}
void ScheduleDAGMI::releaseSucc(SUnit *SU, SDep *SuccEdge) {
SUnit *SuccSU = SuccEdge->getSUnit();
if (SuccEdge->isWeak()) {
--SuccSU->WeakPredsLeft;
if (SuccEdge->isCluster())
NextClusterSucc = SuccSU;
return;
}
#ifndef NDEBUG
if (SuccSU->NumPredsLeft == 0) {
dbgs() << "*** Scheduling failed! ***\n";
SuccSU->dump(this);
dbgs() << " has been released too many times!\n";
llvm_unreachable(nullptr);
}
#endif
if (SuccSU->TopReadyCycle < SU->TopReadyCycle + SuccEdge->getLatency())
SuccSU->TopReadyCycle = SU->TopReadyCycle + SuccEdge->getLatency();
--SuccSU->NumPredsLeft;
if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU)
SchedImpl->releaseTopNode(SuccSU);
}
void ScheduleDAGMI::releaseSuccessors(SUnit *SU) {
for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
releaseSucc(SU, &*I);
}
}
void ScheduleDAGMI::releasePred(SUnit *SU, SDep *PredEdge) {
SUnit *PredSU = PredEdge->getSUnit();
if (PredEdge->isWeak()) {
--PredSU->WeakSuccsLeft;
if (PredEdge->isCluster())
NextClusterPred = PredSU;
return;
}
#ifndef NDEBUG
if (PredSU->NumSuccsLeft == 0) {
dbgs() << "*** Scheduling failed! ***\n";
PredSU->dump(this);
dbgs() << " has been released too many times!\n";
llvm_unreachable(nullptr);
}
#endif
if (PredSU->BotReadyCycle < SU->BotReadyCycle + PredEdge->getLatency())
PredSU->BotReadyCycle = SU->BotReadyCycle + PredEdge->getLatency();
--PredSU->NumSuccsLeft;
if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU)
SchedImpl->releaseBottomNode(PredSU);
}
void ScheduleDAGMI::releasePredecessors(SUnit *SU) {
for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
releasePred(SU, &*I);
}
}
void ScheduleDAGMI::enterRegion(MachineBasicBlock *bb,
MachineBasicBlock::iterator begin,
MachineBasicBlock::iterator end,
unsigned regioninstrs)
{
ScheduleDAGInstrs::enterRegion(bb, begin, end, regioninstrs);
SchedImpl->initPolicy(begin, end, regioninstrs);
}
void ScheduleDAGMI::moveInstruction(
MachineInstr *MI, MachineBasicBlock::iterator InsertPos) {
if (&*RegionBegin == MI)
++RegionBegin;
BB->splice(InsertPos, BB, MI);
if (LIS)
LIS->handleMove(MI, true);
if (RegionBegin == InsertPos)
RegionBegin = MI;
}
bool ScheduleDAGMI::checkSchedLimit() {
#ifndef NDEBUG
if (NumInstrsScheduled == MISchedCutoff && MISchedCutoff != ~0U) {
CurrentTop = CurrentBottom;
return false;
}
++NumInstrsScheduled;
#endif
return true;
}
void ScheduleDAGMI::schedule() {
DEBUG(dbgs() << "ScheduleDAGMI::schedule starting\n");
DEBUG(SchedImpl->dumpPolicy());
buildSchedGraph(AA);
Topo.InitDAGTopologicalSorting();
postprocessDAG();
SmallVector<SUnit*, 8> TopRoots, BotRoots;
findRootsAndBiasEdges(TopRoots, BotRoots);
SchedImpl->initialize(this);
DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
SUnits[su].dumpAll(this));
if (ViewMISchedDAGs) viewGraph();
initQueues(TopRoots, BotRoots);
bool IsTopNode = false;
while (true) {
DEBUG(dbgs() << "** ScheduleDAGMI::schedule picking next node\n");
SUnit *SU = SchedImpl->pickNode(IsTopNode);
if (!SU) break;
assert(!SU->isScheduled && "Node already scheduled");
if (!checkSchedLimit())
break;
MachineInstr *MI = SU->getInstr();
if (IsTopNode) {
assert(SU->isTopReady() && "node still has unscheduled dependencies");
if (&*CurrentTop == MI)
CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom);
else
moveInstruction(MI, CurrentTop);
}
else {
assert(SU->isBottomReady() && "node still has unscheduled dependencies");
MachineBasicBlock::iterator priorII =
priorNonDebug(CurrentBottom, CurrentTop);
if (&*priorII == MI)
CurrentBottom = priorII;
else {
if (&*CurrentTop == MI)
CurrentTop = nextIfDebug(++CurrentTop, priorII);
moveInstruction(MI, CurrentBottom);
CurrentBottom = MI;
}
}
SchedImpl->schedNode(SU, IsTopNode);
updateQueues(SU, IsTopNode);
}
assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
placeDebugValues();
DEBUG({
unsigned BBNum = begin()->getParent()->getNumber();
dbgs() << "*** Final schedule for BB#" << BBNum << " ***\n";
dumpSchedule();
dbgs() << '\n';
});
}
void ScheduleDAGMI::postprocessDAG() {
for (unsigned i = 0, e = Mutations.size(); i < e; ++i) {
Mutations[i]->apply(this);
}
}
void ScheduleDAGMI::
findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots,
SmallVectorImpl<SUnit*> &BotRoots) {
for (std::vector<SUnit>::iterator
I = SUnits.begin(), E = SUnits.end(); I != E; ++I) {
SUnit *SU = &(*I);
assert(!SU->isBoundaryNode() && "Boundary node should not be in SUnits");
SU->biasCriticalPath();
if (!I->NumPredsLeft)
TopRoots.push_back(SU);
if (!I->NumSuccsLeft)
BotRoots.push_back(SU);
}
ExitSU.biasCriticalPath();
}
void ScheduleDAGMI::initQueues(ArrayRef<SUnit*> TopRoots,
ArrayRef<SUnit*> BotRoots) {
NextClusterSucc = nullptr;
NextClusterPred = nullptr;
for (SmallVectorImpl<SUnit*>::const_iterator
I = TopRoots.begin(), E = TopRoots.end(); I != E; ++I) {
SchedImpl->releaseTopNode(*I);
}
for (SmallVectorImpl<SUnit*>::const_reverse_iterator
I = BotRoots.rbegin(), E = BotRoots.rend(); I != E; ++I) {
SchedImpl->releaseBottomNode(*I);
}
releaseSuccessors(&EntrySU);
releasePredecessors(&ExitSU);
SchedImpl->registerRoots();
CurrentTop = nextIfDebug(RegionBegin, RegionEnd);
CurrentBottom = RegionEnd;
}
void ScheduleDAGMI::updateQueues(SUnit *SU, bool IsTopNode) {
if (IsTopNode)
releaseSuccessors(SU);
else
releasePredecessors(SU);
SU->isScheduled = true;
}
void ScheduleDAGMI::placeDebugValues() {
if (FirstDbgValue) {
BB->splice(RegionBegin, BB, FirstDbgValue);
RegionBegin = FirstDbgValue;
}
for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator
DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) {
std::pair<MachineInstr *, MachineInstr *> P = *std::prev(DI);
MachineInstr *DbgValue = P.first;
MachineBasicBlock::iterator OrigPrevMI = P.second;
if (&*RegionBegin == DbgValue)
++RegionBegin;
BB->splice(++OrigPrevMI, BB, DbgValue);
if (OrigPrevMI == std::prev(RegionEnd))
RegionEnd = DbgValue;
}
DbgValues.clear();
FirstDbgValue = nullptr;
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void ScheduleDAGMI::dumpSchedule() const {
for (MachineBasicBlock::iterator MI = begin(), ME = end(); MI != ME; ++MI) {
if (SUnit *SU = getSUnit(&(*MI)))
SU->dump(this);
else
dbgs() << "Missing SUnit\n";
}
}
#endif
ScheduleDAGMILive::~ScheduleDAGMILive() {
delete DFSResult;
}
void ScheduleDAGMILive::enterRegion(MachineBasicBlock *bb,
MachineBasicBlock::iterator begin,
MachineBasicBlock::iterator end,
unsigned regioninstrs)
{
ScheduleDAGMI::enterRegion(bb, begin, end, regioninstrs);
LiveRegionEnd = (RegionEnd == bb->end()) ? RegionEnd : std::next(RegionEnd);
SUPressureDiffs.clear();
ShouldTrackPressure = SchedImpl->shouldTrackPressure();
}
void ScheduleDAGMILive::initRegPressure() {
TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin);
BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd);
RPTracker.closeRegion();
DEBUG(RPTracker.dump());
TopRPTracker.addLiveRegs(RPTracker.getPressure().LiveInRegs);
BotRPTracker.addLiveRegs(RPTracker.getPressure().LiveOutRegs);
TopRPTracker.closeTop();
BotRPTracker.closeBottom();
BotRPTracker.initLiveThru(RPTracker);
if (!BotRPTracker.getLiveThru().empty()) {
TopRPTracker.initLiveThru(BotRPTracker.getLiveThru());
DEBUG(dbgs() << "Live Thru: ";
dumpRegSetPressure(BotRPTracker.getLiveThru(), TRI));
};
updatePressureDiffs(RPTracker.getPressure().LiveOutRegs);
if (LiveRegionEnd != RegionEnd) {
SmallVector<unsigned, 8> LiveUses;
BotRPTracker.recede(&LiveUses);
updatePressureDiffs(LiveUses);
}
assert(BotRPTracker.getPos() == RegionEnd && "Can't find the region bottom");
RegionCriticalPSets.clear();
const std::vector<unsigned> &RegionPressure =
RPTracker.getPressure().MaxSetPressure;
for (unsigned i = 0, e = RegionPressure.size(); i < e; ++i) {
unsigned Limit = RegClassInfo->getRegPressureSetLimit(i);
if (RegionPressure[i] > Limit) {
DEBUG(dbgs() << TRI->getRegPressureSetName(i)
<< " Limit " << Limit
<< " Actual " << RegionPressure[i] << "\n");
RegionCriticalPSets.push_back(PressureChange(i));
}
}
DEBUG(dbgs() << "Excess PSets: ";
for (unsigned i = 0, e = RegionCriticalPSets.size(); i != e; ++i)
dbgs() << TRI->getRegPressureSetName(
RegionCriticalPSets[i].getPSet()) << " ";
dbgs() << "\n");
}
void ScheduleDAGMILive::
updateScheduledPressure(const SUnit *SU,
const std::vector<unsigned> &NewMaxPressure) {
const PressureDiff &PDiff = getPressureDiff(SU);
unsigned CritIdx = 0, CritEnd = RegionCriticalPSets.size();
for (PressureDiff::const_iterator I = PDiff.begin(), E = PDiff.end();
I != E; ++I) {
if (!I->isValid())
break;
unsigned ID = I->getPSet();
while (CritIdx != CritEnd && RegionCriticalPSets[CritIdx].getPSet() < ID)
++CritIdx;
if (CritIdx != CritEnd && RegionCriticalPSets[CritIdx].getPSet() == ID) {
if ((int)NewMaxPressure[ID] > RegionCriticalPSets[CritIdx].getUnitInc()
&& NewMaxPressure[ID] <= INT16_MAX)
RegionCriticalPSets[CritIdx].setUnitInc(NewMaxPressure[ID]);
}
unsigned Limit = RegClassInfo->getRegPressureSetLimit(ID);
if (NewMaxPressure[ID] >= Limit - 2) {
DEBUG(dbgs() << " " << TRI->getRegPressureSetName(ID) << ": "
<< NewMaxPressure[ID]
<< ((NewMaxPressure[ID] > Limit) ? " > " : " <= ") << Limit
<< "(+ " << BotRPTracker.getLiveThru()[ID] << " livethru)\n");
}
}
}
void ScheduleDAGMILive::updatePressureDiffs(ArrayRef<unsigned> LiveUses) {
for (unsigned LUIdx = 0, LUEnd = LiveUses.size(); LUIdx != LUEnd; ++LUIdx) {
unsigned Reg = LiveUses[LUIdx];
DEBUG(dbgs() << " LiveReg: " << PrintVRegOrUnit(Reg, TRI) << "\n");
if (!TRI->isVirtualRegister(Reg))
continue;
const LiveInterval &LI = LIS->getInterval(Reg);
VNInfo *VNI;
MachineBasicBlock::const_iterator I =
nextIfDebug(BotRPTracker.getPos(), BB->end());
if (I == BB->end())
VNI = LI.getVNInfoBefore(LIS->getMBBEndIdx(BB));
else {
LiveQueryResult LRQ = LI.Query(LIS->getInstructionIndex(I));
VNI = LRQ.valueIn();
}
assert(VNI && "No live value at use.");
for (const VReg2SUnit &V2SU
: make_range(VRegUses.find(Reg), VRegUses.end())) {
SUnit *SU = V2SU.SU;
if (!SU->isScheduled && SU != &ExitSU) {
LiveQueryResult LRQ
= LI.Query(LIS->getInstructionIndex(SU->getInstr()));
if (LRQ.valueIn() == VNI) {
PressureDiff &PDiff = getPressureDiff(SU);
PDiff.addPressureChange(Reg, true, &MRI);
DEBUG(
dbgs() << " UpdateRegP: SU(" << SU->NodeNum << ") "
<< *SU->getInstr();
dbgs() << " to ";
PDiff.dump(*TRI);
);
}
}
}
}
}
void ScheduleDAGMILive::schedule() {
DEBUG(dbgs() << "ScheduleDAGMILive::schedule starting\n");
DEBUG(SchedImpl->dumpPolicy());
buildDAGWithRegPressure();
Topo.InitDAGTopologicalSorting();
postprocessDAG();
SmallVector<SUnit*, 8> TopRoots, BotRoots;
findRootsAndBiasEdges(TopRoots, BotRoots);
SchedImpl->initialize(this);
DEBUG(
for (const SUnit &SU : SUnits) {
SU.dumpAll(this);
if (ShouldTrackPressure) {
dbgs() << " Pressure Diff : ";
getPressureDiff(&SU).dump(*TRI);
}
dbgs() << '\n';
}
);
if (ViewMISchedDAGs) viewGraph();
initQueues(TopRoots, BotRoots);
if (ShouldTrackPressure) {
assert(TopRPTracker.getPos() == RegionBegin && "bad initial Top tracker");
TopRPTracker.setPos(CurrentTop);
}
bool IsTopNode = false;
while (true) {
DEBUG(dbgs() << "** ScheduleDAGMILive::schedule picking next node\n");
SUnit *SU = SchedImpl->pickNode(IsTopNode);
if (!SU) break;
assert(!SU->isScheduled && "Node already scheduled");
if (!checkSchedLimit())
break;
scheduleMI(SU, IsTopNode);
if (DFSResult) {
unsigned SubtreeID = DFSResult->getSubtreeID(SU);
if (!ScheduledTrees.test(SubtreeID)) {
ScheduledTrees.set(SubtreeID);
DFSResult->scheduleTree(SubtreeID);
SchedImpl->scheduleTree(SubtreeID);
}
}
SchedImpl->schedNode(SU, IsTopNode);
updateQueues(SU, IsTopNode);
}
assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
placeDebugValues();
DEBUG({
unsigned BBNum = begin()->getParent()->getNumber();
dbgs() << "*** Final schedule for BB#" << BBNum << " ***\n";
dumpSchedule();
dbgs() << '\n';
});
}
void ScheduleDAGMILive::buildDAGWithRegPressure() {
if (!ShouldTrackPressure) {
RPTracker.reset();
RegionCriticalPSets.clear();
buildSchedGraph(AA);
return;
}
RPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd,
true);
if (LiveRegionEnd != RegionEnd)
RPTracker.recede();
buildSchedGraph(AA, &RPTracker, &SUPressureDiffs);
initRegPressure();
}
void ScheduleDAGMILive::computeDFSResult() {
if (!DFSResult)
DFSResult = new SchedDFSResult(true, MinSubtreeSize);
DFSResult->clear();
ScheduledTrees.clear();
DFSResult->resize(SUnits.size());
DFSResult->compute(SUnits);
ScheduledTrees.resize(DFSResult->getNumSubtrees());
}
unsigned ScheduleDAGMILive::computeCyclicCriticalPath() {
if (!BB->isSuccessor(BB))
return 0;
unsigned MaxCyclicLatency = 0;
ArrayRef<unsigned> LiveOuts = RPTracker.getPressure().LiveOutRegs;
for (ArrayRef<unsigned>::iterator RI = LiveOuts.begin(), RE = LiveOuts.end();
RI != RE; ++RI) {
unsigned Reg = *RI;
if (!TRI->isVirtualRegister(Reg))
continue;
const LiveInterval &LI = LIS->getInterval(Reg);
const VNInfo *DefVNI = LI.getVNInfoBefore(LIS->getMBBEndIdx(BB));
if (!DefVNI)
continue;
MachineInstr *DefMI = LIS->getInstructionFromIndex(DefVNI->def);
const SUnit *DefSU = getSUnit(DefMI);
if (!DefSU)
continue;
unsigned LiveOutHeight = DefSU->getHeight();
unsigned LiveOutDepth = DefSU->getDepth() + DefSU->Latency;
for (const VReg2SUnit &V2SU
: make_range(VRegUses.find(Reg), VRegUses.end())) {
SUnit *SU = V2SU.SU;
if (SU == &ExitSU)
continue;
LiveQueryResult LRQ =
LI.Query(LIS->getInstructionIndex(SU->getInstr()));
if (!LRQ.valueIn()->isPHIDef())
continue;
unsigned CyclicLatency = 0;
if (LiveOutDepth > SU->getDepth())
CyclicLatency = LiveOutDepth - SU->getDepth();
unsigned LiveInHeight = SU->getHeight() + DefSU->Latency;
if (LiveInHeight > LiveOutHeight) {
if (LiveInHeight - LiveOutHeight < CyclicLatency)
CyclicLatency = LiveInHeight - LiveOutHeight;
}
else
CyclicLatency = 0;
DEBUG(dbgs() << "Cyclic Path: SU(" << DefSU->NodeNum << ") -> SU("
<< SU->NodeNum << ") = " << CyclicLatency << "c\n");
if (CyclicLatency > MaxCyclicLatency)
MaxCyclicLatency = CyclicLatency;
}
}
DEBUG(dbgs() << "Cyclic Critical Path: " << MaxCyclicLatency << "c\n");
return MaxCyclicLatency;
}
void ScheduleDAGMILive::scheduleMI(SUnit *SU, bool IsTopNode) {
MachineInstr *MI = SU->getInstr();
if (IsTopNode) {
assert(SU->isTopReady() && "node still has unscheduled dependencies");
if (&*CurrentTop == MI)
CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom);
else {
moveInstruction(MI, CurrentTop);
TopRPTracker.setPos(MI);
}
if (ShouldTrackPressure) {
TopRPTracker.advance();
assert(TopRPTracker.getPos() == CurrentTop && "out of sync");
DEBUG(
dbgs() << "Top Pressure:\n";
dumpRegSetPressure(TopRPTracker.getRegSetPressureAtPos(), TRI);
);
updateScheduledPressure(SU, TopRPTracker.getPressure().MaxSetPressure);
}
}
else {
assert(SU->isBottomReady() && "node still has unscheduled dependencies");
MachineBasicBlock::iterator priorII =
priorNonDebug(CurrentBottom, CurrentTop);
if (&*priorII == MI)
CurrentBottom = priorII;
else {
if (&*CurrentTop == MI) {
CurrentTop = nextIfDebug(++CurrentTop, priorII);
TopRPTracker.setPos(CurrentTop);
}
moveInstruction(MI, CurrentBottom);
CurrentBottom = MI;
}
if (ShouldTrackPressure) {
SmallVector<unsigned, 8> LiveUses;
BotRPTracker.recede(&LiveUses);
assert(BotRPTracker.getPos() == CurrentBottom && "out of sync");
DEBUG(
dbgs() << "Bottom Pressure:\n";
dumpRegSetPressure(BotRPTracker.getRegSetPressureAtPos(), TRI);
);
updateScheduledPressure(SU, BotRPTracker.getPressure().MaxSetPressure);
updatePressureDiffs(LiveUses);
}
}
}
namespace {
class LoadClusterMutation : public ScheduleDAGMutation {
struct LoadInfo {
SUnit *SU;
unsigned BaseReg;
unsigned Offset;
LoadInfo(SUnit *su, unsigned reg, unsigned ofs)
: SU(su), BaseReg(reg), Offset(ofs) {}
bool operator<(const LoadInfo &RHS) const {
return std::tie(BaseReg, Offset) < std::tie(RHS.BaseReg, RHS.Offset);
}
};
const TargetInstrInfo *TII;
const TargetRegisterInfo *TRI;
public:
LoadClusterMutation(const TargetInstrInfo *tii,
const TargetRegisterInfo *tri)
: TII(tii), TRI(tri) {}
void apply(ScheduleDAGMI *DAG) override;
protected:
void clusterNeighboringLoads(ArrayRef<SUnit*> Loads, ScheduleDAGMI *DAG);
};
}
void LoadClusterMutation::clusterNeighboringLoads(ArrayRef<SUnit*> Loads,
ScheduleDAGMI *DAG) {
SmallVector<LoadClusterMutation::LoadInfo,32> LoadRecords;
for (unsigned Idx = 0, End = Loads.size(); Idx != End; ++Idx) {
SUnit *SU = Loads[Idx];
unsigned BaseReg;
unsigned Offset;
if (TII->getMemOpBaseRegImmOfs(SU->getInstr(), BaseReg, Offset, TRI))
LoadRecords.push_back(LoadInfo(SU, BaseReg, Offset));
}
if (LoadRecords.size() < 2)
return;
std::sort(LoadRecords.begin(), LoadRecords.end());
unsigned ClusterLength = 1;
for (unsigned Idx = 0, End = LoadRecords.size(); Idx < (End - 1); ++Idx) {
if (LoadRecords[Idx].BaseReg != LoadRecords[Idx+1].BaseReg) {
ClusterLength = 1;
continue;
}
SUnit *SUa = LoadRecords[Idx].SU;
SUnit *SUb = LoadRecords[Idx+1].SU;
if (TII->shouldClusterLoads(SUa->getInstr(), SUb->getInstr(), ClusterLength)
&& DAG->addEdge(SUb, SDep(SUa, SDep::Cluster))) {
DEBUG(dbgs() << "Cluster loads SU(" << SUa->NodeNum << ") - SU("
<< SUb->NodeNum << ")\n");
for (SUnit::const_succ_iterator
SI = SUa->Succs.begin(), SE = SUa->Succs.end(); SI != SE; ++SI) {
if (SI->getSUnit() == SUb)
continue;
DEBUG(dbgs() << " Copy Succ SU(" << SI->getSUnit()->NodeNum << ")\n");
DAG->addEdge(SI->getSUnit(), SDep(SUb, SDep::Artificial));
}
++ClusterLength;
}
else
ClusterLength = 1;
}
}
void LoadClusterMutation::apply(ScheduleDAGMI *DAG) {
DenseMap<unsigned, unsigned> StoreChainIDs;
SmallVector<SmallVector<SUnit*,4>, 32> StoreChainDependents;
for (unsigned Idx = 0, End = DAG->SUnits.size(); Idx != End; ++Idx) {
SUnit *SU = &DAG->SUnits[Idx];
if (!SU->getInstr()->mayLoad())
continue;
unsigned ChainPredID = DAG->SUnits.size();
for (SUnit::const_pred_iterator
PI = SU->Preds.begin(), PE = SU->Preds.end(); PI != PE; ++PI) {
if (PI->isCtrl()) {
ChainPredID = PI->getSUnit()->NodeNum;
break;
}
}
unsigned NumChains = StoreChainDependents.size();
std::pair<DenseMap<unsigned, unsigned>::iterator, bool> Result =
StoreChainIDs.insert(std::make_pair(ChainPredID, NumChains));
if (Result.second)
StoreChainDependents.resize(NumChains + 1);
StoreChainDependents[Result.first->second].push_back(SU);
}
for (unsigned Idx = 0, End = StoreChainDependents.size(); Idx != End; ++Idx)
clusterNeighboringLoads(StoreChainDependents[Idx], DAG);
}
namespace {
class MacroFusion : public ScheduleDAGMutation {
const TargetInstrInfo &TII;
const TargetRegisterInfo &TRI;
public:
MacroFusion(const TargetInstrInfo &TII, const TargetRegisterInfo &TRI)
: TII(TII), TRI(TRI) {}
void apply(ScheduleDAGMI *DAG) override;
};
}
static bool HasDataDep(const TargetRegisterInfo &TRI, const MachineInstr &MI,
const MachineInstr &Other) {
for (const MachineOperand &MO : MI.uses()) {
if (!MO.isReg() || !MO.readsReg())
continue;
unsigned Reg = MO.getReg();
if (Other.modifiesRegister(Reg, &TRI))
return true;
}
return false;
}
void MacroFusion::apply(ScheduleDAGMI *DAG) {
SUnit &ExitSU = DAG->ExitSU;
MachineInstr *Branch = ExitSU.getInstr();
if (!Branch)
return;
for (SUnit &SU : DAG->SUnits) {
if (!SU.Succs.empty())
continue;
MachineInstr *Pred = SU.getInstr();
if (!HasDataDep(TRI, *Branch, *Pred))
continue;
if (!TII.shouldScheduleAdjacent(Pred, Branch))
continue;
bool Success = DAG->addEdge(&ExitSU, SDep(&SU, SDep::Cluster));
(void)Success;
assert(Success && "No DAG nodes should be reachable from ExitSU");
DEBUG(dbgs() << "Macro Fuse SU(" << SU.NodeNum << ")\n");
break;
}
}
namespace {
class CopyConstrain : public ScheduleDAGMutation {
SlotIndex RegionBeginIdx;
SlotIndex RegionEndIdx;
public:
CopyConstrain(const TargetInstrInfo *, const TargetRegisterInfo *) {}
void apply(ScheduleDAGMI *DAG) override;
protected:
void constrainLocalCopy(SUnit *CopySU, ScheduleDAGMILive *DAG);
};
}
void CopyConstrain::constrainLocalCopy(SUnit *CopySU, ScheduleDAGMILive *DAG) {
LiveIntervals *LIS = DAG->getLIS();
MachineInstr *Copy = CopySU->getInstr();
unsigned SrcReg = Copy->getOperand(1).getReg();
if (!TargetRegisterInfo::isVirtualRegister(SrcReg))
return;
unsigned DstReg = Copy->getOperand(0).getReg();
if (!TargetRegisterInfo::isVirtualRegister(DstReg))
return;
unsigned LocalReg = SrcReg;
unsigned GlobalReg = DstReg;
LiveInterval *LocalLI = &LIS->getInterval(LocalReg);
if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx)) {
LocalReg = DstReg;
GlobalReg = SrcReg;
LocalLI = &LIS->getInterval(LocalReg);
if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx))
return;
}
LiveInterval *GlobalLI = &LIS->getInterval(GlobalReg);
LiveInterval::iterator GlobalSegment = GlobalLI->find(LocalLI->beginIndex());
if (GlobalSegment == GlobalLI->end())
return;
if (GlobalSegment->contains(LocalLI->beginIndex()))
++GlobalSegment;
if (GlobalSegment == GlobalLI->end())
return;
if (GlobalSegment != GlobalLI->begin()) {
if (SlotIndex::isSameInstr(std::prev(GlobalSegment)->end,
GlobalSegment->start)) {
return;
}
if (SlotIndex::isSameInstr(std::prev(GlobalSegment)->start,
LocalLI->beginIndex())) {
return;
}
assert(std::prev(GlobalSegment)->start < LocalLI->beginIndex() &&
"Disconnected LRG within the scheduling region.");
}
MachineInstr *GlobalDef = LIS->getInstructionFromIndex(GlobalSegment->start);
if (!GlobalDef)
return;
SUnit *GlobalSU = DAG->getSUnit(GlobalDef);
if (!GlobalSU)
return;
SmallVector<SUnit*,8> LocalUses;
const VNInfo *LastLocalVN = LocalLI->getVNInfoBefore(LocalLI->endIndex());
MachineInstr *LastLocalDef = LIS->getInstructionFromIndex(LastLocalVN->def);
SUnit *LastLocalSU = DAG->getSUnit(LastLocalDef);
for (SUnit::const_succ_iterator
I = LastLocalSU->Succs.begin(), E = LastLocalSU->Succs.end();
I != E; ++I) {
if (I->getKind() != SDep::Data || I->getReg() != LocalReg)
continue;
if (I->getSUnit() == GlobalSU)
continue;
if (!DAG->canAddEdge(GlobalSU, I->getSUnit()))
return;
LocalUses.push_back(I->getSUnit());
}
SmallVector<SUnit*,8> GlobalUses;
MachineInstr *FirstLocalDef =
LIS->getInstructionFromIndex(LocalLI->beginIndex());
SUnit *FirstLocalSU = DAG->getSUnit(FirstLocalDef);
for (SUnit::const_pred_iterator
I = GlobalSU->Preds.begin(), E = GlobalSU->Preds.end(); I != E; ++I) {
if (I->getKind() != SDep::Anti || I->getReg() != GlobalReg)
continue;
if (I->getSUnit() == FirstLocalSU)
continue;
if (!DAG->canAddEdge(FirstLocalSU, I->getSUnit()))
return;
GlobalUses.push_back(I->getSUnit());
}
DEBUG(dbgs() << "Constraining copy SU(" << CopySU->NodeNum << ")\n");
for (SmallVectorImpl<SUnit*>::const_iterator
I = LocalUses.begin(), E = LocalUses.end(); I != E; ++I) {
DEBUG(dbgs() << " Local use SU(" << (*I)->NodeNum << ") -> SU("
<< GlobalSU->NodeNum << ")\n");
DAG->addEdge(GlobalSU, SDep(*I, SDep::Weak));
}
for (SmallVectorImpl<SUnit*>::const_iterator
I = GlobalUses.begin(), E = GlobalUses.end(); I != E; ++I) {
DEBUG(dbgs() << " Global use SU(" << (*I)->NodeNum << ") -> SU("
<< FirstLocalSU->NodeNum << ")\n");
DAG->addEdge(FirstLocalSU, SDep(*I, SDep::Weak));
}
}
void CopyConstrain::apply(ScheduleDAGMI *DAG) {
assert(DAG->hasVRegLiveness() && "Expect VRegs with LiveIntervals");
MachineBasicBlock::iterator FirstPos = nextIfDebug(DAG->begin(), DAG->end());
if (FirstPos == DAG->end())
return;
RegionBeginIdx = DAG->getLIS()->getInstructionIndex(&*FirstPos);
RegionEndIdx = DAG->getLIS()->getInstructionIndex(
&*priorNonDebug(DAG->end(), DAG->begin()));
for (unsigned Idx = 0, End = DAG->SUnits.size(); Idx != End; ++Idx) {
SUnit *SU = &DAG->SUnits[Idx];
if (!SU->getInstr()->isCopy())
continue;
constrainLocalCopy(SU, static_cast<ScheduleDAGMILive*>(DAG));
}
}
static const unsigned InvalidCycle = ~0U;
SchedBoundary::~SchedBoundary() { delete HazardRec; }
void SchedBoundary::reset() {
if (HazardRec && HazardRec->isEnabled()) {
delete HazardRec;
HazardRec = nullptr;
}
Available.clear();
Pending.clear();
CheckPending = false;
NextSUs.clear();
CurrCycle = 0;
CurrMOps = 0;
MinReadyCycle = UINT_MAX;
ExpectedLatency = 0;
DependentLatency = 0;
RetiredMOps = 0;
MaxExecutedResCount = 0;
ZoneCritResIdx = 0;
IsResourceLimited = false;
ReservedCycles.clear();
#ifndef NDEBUG
MaxObservedStall = 0;
#endif
ExecutedResCounts.resize(1);
assert(!ExecutedResCounts[0] && "nonzero count for bad resource");
}
void SchedRemainder::
init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel) {
reset();
if (!SchedModel->hasInstrSchedModel())
return;
RemainingCounts.resize(SchedModel->getNumProcResourceKinds());
for (std::vector<SUnit>::iterator
I = DAG->SUnits.begin(), E = DAG->SUnits.end(); I != E; ++I) {
const MCSchedClassDesc *SC = DAG->getSchedClass(&*I);
RemIssueCount += SchedModel->getNumMicroOps(I->getInstr(), SC)
* SchedModel->getMicroOpFactor();
for (TargetSchedModel::ProcResIter
PI = SchedModel->getWriteProcResBegin(SC),
PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
unsigned PIdx = PI->ProcResourceIdx;
unsigned Factor = SchedModel->getResourceFactor(PIdx);
RemainingCounts[PIdx] += (Factor * PI->Cycles);
}
}
}
void SchedBoundary::
init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, SchedRemainder *rem) {
reset();
DAG = dag;
SchedModel = smodel;
Rem = rem;
if (SchedModel->hasInstrSchedModel()) {
ExecutedResCounts.resize(SchedModel->getNumProcResourceKinds());
ReservedCycles.resize(SchedModel->getNumProcResourceKinds(), InvalidCycle);
}
}
unsigned SchedBoundary::getLatencyStallCycles(SUnit *SU) {
if (!SU->isUnbuffered)
return 0;
unsigned ReadyCycle = (isTop() ? SU->TopReadyCycle : SU->BotReadyCycle);
if (ReadyCycle > CurrCycle)
return ReadyCycle - CurrCycle;
return 0;
}
unsigned SchedBoundary::
getNextResourceCycle(unsigned PIdx, unsigned Cycles) {
unsigned NextUnreserved = ReservedCycles[PIdx];
if (NextUnreserved == InvalidCycle)
return 0;
if (!isTop())
NextUnreserved += Cycles;
return NextUnreserved;
}
bool SchedBoundary::checkHazard(SUnit *SU) {
if (HazardRec->isEnabled()
&& HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard) {
return true;
}
unsigned uops = SchedModel->getNumMicroOps(SU->getInstr());
if ((CurrMOps > 0) && (CurrMOps + uops > SchedModel->getIssueWidth())) {
DEBUG(dbgs() << " SU(" << SU->NodeNum << ") uops="
<< SchedModel->getNumMicroOps(SU->getInstr()) << '\n');
return true;
}
if (SchedModel->hasInstrSchedModel() && SU->hasReservedResource) {
const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
for (TargetSchedModel::ProcResIter
PI = SchedModel->getWriteProcResBegin(SC),
PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
unsigned NRCycle = getNextResourceCycle(PI->ProcResourceIdx, PI->Cycles);
if (NRCycle > CurrCycle) {
#ifndef NDEBUG
MaxObservedStall = std::max(PI->Cycles, MaxObservedStall);
#endif
DEBUG(dbgs() << " SU(" << SU->NodeNum << ") "
<< SchedModel->getResourceName(PI->ProcResourceIdx)
<< "=" << NRCycle << "c\n");
return true;
}
}
}
return false;
}
unsigned SchedBoundary::
findMaxLatency(ArrayRef<SUnit*> ReadySUs) {
SUnit *LateSU = nullptr;
unsigned RemLatency = 0;
for (ArrayRef<SUnit*>::iterator I = ReadySUs.begin(), E = ReadySUs.end();
I != E; ++I) {
unsigned L = getUnscheduledLatency(*I);
if (L > RemLatency) {
RemLatency = L;
LateSU = *I;
}
}
if (LateSU) {
DEBUG(dbgs() << Available.getName() << " RemLatency SU("
<< LateSU->NodeNum << ") " << RemLatency << "c\n");
}
return RemLatency;
}
unsigned SchedBoundary::
getOtherResourceCount(unsigned &OtherCritIdx) {
OtherCritIdx = 0;
if (!SchedModel->hasInstrSchedModel())
return 0;
unsigned OtherCritCount = Rem->RemIssueCount
+ (RetiredMOps * SchedModel->getMicroOpFactor());
DEBUG(dbgs() << " " << Available.getName() << " + Remain MOps: "
<< OtherCritCount / SchedModel->getMicroOpFactor() << '\n');
for (unsigned PIdx = 1, PEnd = SchedModel->getNumProcResourceKinds();
PIdx != PEnd; ++PIdx) {
unsigned OtherCount = getResourceCount(PIdx) + Rem->RemainingCounts[PIdx];
if (OtherCount > OtherCritCount) {
OtherCritCount = OtherCount;
OtherCritIdx = PIdx;
}
}
if (OtherCritIdx) {
DEBUG(dbgs() << " " << Available.getName() << " + Remain CritRes: "
<< OtherCritCount / SchedModel->getResourceFactor(OtherCritIdx)
<< " " << SchedModel->getResourceName(OtherCritIdx) << "\n");
}
return OtherCritCount;
}
void SchedBoundary::releaseNode(SUnit *SU, unsigned ReadyCycle) {
assert(SU->getInstr() && "Scheduled SUnit must have instr");
#ifndef NDEBUG
if (ReadyCycle > CurrCycle)
MaxObservedStall = std::max(ReadyCycle - CurrCycle, MaxObservedStall);
#endif
if (ReadyCycle < MinReadyCycle)
MinReadyCycle = ReadyCycle;
bool IsBuffered = SchedModel->getMicroOpBufferSize() != 0;
if ((!IsBuffered && ReadyCycle > CurrCycle) || checkHazard(SU))
Pending.push(SU);
else
Available.push(SU);
NextSUs.insert(SU);
}
void SchedBoundary::releaseTopNode(SUnit *SU) {
if (SU->isScheduled)
return;
releaseNode(SU, SU->TopReadyCycle);
}
void SchedBoundary::releaseBottomNode(SUnit *SU) {
if (SU->isScheduled)
return;
releaseNode(SU, SU->BotReadyCycle);
}
void SchedBoundary::bumpCycle(unsigned NextCycle) {
if (SchedModel->getMicroOpBufferSize() == 0) {
assert(MinReadyCycle < UINT_MAX && "MinReadyCycle uninitialized");
if (MinReadyCycle > NextCycle)
NextCycle = MinReadyCycle;
}
unsigned DecMOps = SchedModel->getIssueWidth() * (NextCycle - CurrCycle);
CurrMOps = (CurrMOps <= DecMOps) ? 0 : CurrMOps - DecMOps;
if ((NextCycle - CurrCycle) > DependentLatency)
DependentLatency = 0;
else
DependentLatency -= (NextCycle - CurrCycle);
if (!HazardRec->isEnabled()) {
CurrCycle = NextCycle;
}
else {
for (; CurrCycle != NextCycle; ++CurrCycle) {
if (isTop())
HazardRec->AdvanceCycle();
else
HazardRec->RecedeCycle();
}
}
CheckPending = true;
unsigned LFactor = SchedModel->getLatencyFactor();
IsResourceLimited =
(int)(getCriticalCount() - (getScheduledLatency() * LFactor))
> (int)LFactor;
DEBUG(dbgs() << "Cycle: " << CurrCycle << ' ' << Available.getName() << '\n');
}
void SchedBoundary::incExecutedResources(unsigned PIdx, unsigned Count) {
ExecutedResCounts[PIdx] += Count;
if (ExecutedResCounts[PIdx] > MaxExecutedResCount)
MaxExecutedResCount = ExecutedResCounts[PIdx];
}
unsigned SchedBoundary::
countResource(unsigned PIdx, unsigned Cycles, unsigned NextCycle) {
unsigned Factor = SchedModel->getResourceFactor(PIdx);
unsigned Count = Factor * Cycles;
DEBUG(dbgs() << " " << SchedModel->getResourceName(PIdx)
<< " +" << Cycles << "x" << Factor << "u\n");
incExecutedResources(PIdx, Count);
assert(Rem->RemainingCounts[PIdx] >= Count && "resource double counted");
Rem->RemainingCounts[PIdx] -= Count;
if (ZoneCritResIdx != PIdx && (getResourceCount(PIdx) > getCriticalCount())) {
ZoneCritResIdx = PIdx;
DEBUG(dbgs() << " *** Critical resource "
<< SchedModel->getResourceName(PIdx) << ": "
<< getResourceCount(PIdx) / SchedModel->getLatencyFactor() << "c\n");
}
unsigned NextAvailable = getNextResourceCycle(PIdx, Cycles);
if (NextAvailable > CurrCycle) {
DEBUG(dbgs() << " Resource conflict: "
<< SchedModel->getProcResource(PIdx)->Name << " reserved until @"
<< NextAvailable << "\n");
}
return NextAvailable;
}
void SchedBoundary::bumpNode(SUnit *SU) {
if (HazardRec->isEnabled()) {
if (!isTop() && SU->isCall) {
HazardRec->Reset();
}
HazardRec->EmitInstruction(SU);
}
const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
unsigned IncMOps = SchedModel->getNumMicroOps(SU->getInstr());
assert(
(CurrMOps == 0 || (CurrMOps + IncMOps) <= SchedModel->getIssueWidth()) &&
"Cannot schedule this instruction's MicroOps in the current cycle.");
unsigned ReadyCycle = (isTop() ? SU->TopReadyCycle : SU->BotReadyCycle);
DEBUG(dbgs() << " Ready @" << ReadyCycle << "c\n");
unsigned NextCycle = CurrCycle;
switch (SchedModel->getMicroOpBufferSize()) {
case 0:
assert(ReadyCycle <= CurrCycle && "Broken PendingQueue");
break;
case 1:
if (ReadyCycle > NextCycle) {
NextCycle = ReadyCycle;
DEBUG(dbgs() << " *** Stall until: " << ReadyCycle << "\n");
}
break;
default:
if (SU->isUnbuffered && ReadyCycle > NextCycle)
NextCycle = ReadyCycle;
break;
}
RetiredMOps += IncMOps;
if (SchedModel->hasInstrSchedModel()) {
unsigned DecRemIssue = IncMOps * SchedModel->getMicroOpFactor();
assert(Rem->RemIssueCount >= DecRemIssue && "MOps double counted");
Rem->RemIssueCount -= DecRemIssue;
if (ZoneCritResIdx) {
unsigned ScaledMOps =
RetiredMOps * SchedModel->getMicroOpFactor();
if ((int)(ScaledMOps - getResourceCount(ZoneCritResIdx))
>= (int)SchedModel->getLatencyFactor()) {
ZoneCritResIdx = 0;
DEBUG(dbgs() << " *** Critical resource NumMicroOps: "
<< ScaledMOps / SchedModel->getLatencyFactor() << "c\n");
}
}
for (TargetSchedModel::ProcResIter
PI = SchedModel->getWriteProcResBegin(SC),
PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
unsigned RCycle =
countResource(PI->ProcResourceIdx, PI->Cycles, NextCycle);
if (RCycle > NextCycle)
NextCycle = RCycle;
}
if (SU->hasReservedResource) {
for (TargetSchedModel::ProcResIter
PI = SchedModel->getWriteProcResBegin(SC),
PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
unsigned PIdx = PI->ProcResourceIdx;
if (SchedModel->getProcResource(PIdx)->BufferSize == 0) {
if (isTop()) {
ReservedCycles[PIdx] =
std::max(getNextResourceCycle(PIdx, 0), NextCycle + PI->Cycles);
}
else
ReservedCycles[PIdx] = NextCycle;
}
}
}
}
unsigned &TopLatency = isTop() ? ExpectedLatency : DependentLatency;
unsigned &BotLatency = isTop() ? DependentLatency : ExpectedLatency;
if (SU->getDepth() > TopLatency) {
TopLatency = SU->getDepth();
DEBUG(dbgs() << " " << Available.getName()
<< " TopLatency SU(" << SU->NodeNum << ") " << TopLatency << "c\n");
}
if (SU->getHeight() > BotLatency) {
BotLatency = SU->getHeight();
DEBUG(dbgs() << " " << Available.getName()
<< " BotLatency SU(" << SU->NodeNum << ") " << BotLatency << "c\n");
}
if (NextCycle > CurrCycle) {
bumpCycle(NextCycle);
}
else {
unsigned LFactor = SchedModel->getLatencyFactor();
IsResourceLimited =
(int)(getCriticalCount() - (getScheduledLatency() * LFactor))
> (int)LFactor;
}
CurrMOps += IncMOps;
while (CurrMOps >= SchedModel->getIssueWidth()) {
DEBUG(dbgs() << " *** Max MOps " << CurrMOps
<< " at cycle " << CurrCycle << '\n');
bumpCycle(++NextCycle);
}
DEBUG(dumpScheduledState());
}
void SchedBoundary::releasePending() {
if (Available.empty())
MinReadyCycle = UINT_MAX;
bool IsBuffered = SchedModel->getMicroOpBufferSize() != 0;
for (unsigned i = 0, e = Pending.size(); i != e; ++i) {
SUnit *SU = *(Pending.begin()+i);
unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle;
if (ReadyCycle < MinReadyCycle)
MinReadyCycle = ReadyCycle;
if (!IsBuffered && ReadyCycle > CurrCycle)
continue;
if (checkHazard(SU))
continue;
Available.push(SU);
Pending.remove(Pending.begin()+i);
--i; --e;
}
DEBUG(if (!Pending.empty()) Pending.dump());
CheckPending = false;
}
void SchedBoundary::removeReady(SUnit *SU) {
if (Available.isInQueue(SU))
Available.remove(Available.find(SU));
else {
assert(Pending.isInQueue(SU) && "bad ready count");
Pending.remove(Pending.find(SU));
}
}
SUnit *SchedBoundary::pickOnlyChoice() {
if (CheckPending)
releasePending();
if (CurrMOps > 0) {
for (ReadyQueue::iterator I = Available.begin(); I != Available.end();) {
if (checkHazard(*I)) {
Pending.push(*I);
I = Available.remove(I);
continue;
}
++I;
}
}
for (unsigned i = 0; Available.empty(); ++i) {
(void)i;
bumpCycle(CurrCycle + 1);
releasePending();
}
if (Available.size() == 1)
return *Available.begin();
return nullptr;
}
#ifndef NDEBUG
void SchedBoundary::dumpScheduledState() {
unsigned ResFactor;
unsigned ResCount;
if (ZoneCritResIdx) {
ResFactor = SchedModel->getResourceFactor(ZoneCritResIdx);
ResCount = getResourceCount(ZoneCritResIdx);
}
else {
ResFactor = SchedModel->getMicroOpFactor();
ResCount = RetiredMOps * SchedModel->getMicroOpFactor();
}
unsigned LFactor = SchedModel->getLatencyFactor();
dbgs() << Available.getName() << " @" << CurrCycle << "c\n"
<< " Retired: " << RetiredMOps;
dbgs() << "\n Executed: " << getExecutedCount() / LFactor << "c";
dbgs() << "\n Critical: " << ResCount / LFactor << "c, "
<< ResCount / ResFactor << " "
<< SchedModel->getResourceName(ZoneCritResIdx)
<< "\n ExpectedLatency: " << ExpectedLatency << "c\n"
<< (IsResourceLimited ? " - Resource" : " - Latency")
<< " limited.\n";
}
#endif
void GenericSchedulerBase::SchedCandidate::
initResourceDelta(const ScheduleDAGMI *DAG,
const TargetSchedModel *SchedModel) {
if (!Policy.ReduceResIdx && !Policy.DemandResIdx)
return;
const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
for (TargetSchedModel::ProcResIter
PI = SchedModel->getWriteProcResBegin(SC),
PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
if (PI->ProcResourceIdx == Policy.ReduceResIdx)
ResDelta.CritResources += PI->Cycles;
if (PI->ProcResourceIdx == Policy.DemandResIdx)
ResDelta.DemandedResources += PI->Cycles;
}
}
void GenericSchedulerBase::setPolicy(CandPolicy &Policy,
bool IsPostRA,
SchedBoundary &CurrZone,
SchedBoundary *OtherZone) {
unsigned RemLatency = CurrZone.getDependentLatency();
RemLatency = std::max(RemLatency,
CurrZone.findMaxLatency(CurrZone.Available.elements()));
RemLatency = std::max(RemLatency,
CurrZone.findMaxLatency(CurrZone.Pending.elements()));
unsigned OtherCritIdx = 0;
unsigned OtherCount =
OtherZone ? OtherZone->getOtherResourceCount(OtherCritIdx) : 0;
bool OtherResLimited = false;
if (SchedModel->hasInstrSchedModel()) {
unsigned LFactor = SchedModel->getLatencyFactor();
OtherResLimited = (int)(OtherCount - (RemLatency * LFactor)) > (int)LFactor;
}
if (!OtherResLimited) {
if (IsPostRA || (RemLatency + CurrZone.getCurrCycle() > Rem.CriticalPath)) {
Policy.ReduceLatency |= true;
DEBUG(dbgs() << " " << CurrZone.Available.getName()
<< " RemainingLatency " << RemLatency << " + "
<< CurrZone.getCurrCycle() << "c > CritPath "
<< Rem.CriticalPath << "\n");
}
}
if (CurrZone.getZoneCritResIdx() == OtherCritIdx)
return;
DEBUG(
if (CurrZone.isResourceLimited()) {
dbgs() << " " << CurrZone.Available.getName() << " ResourceLimited: "
<< SchedModel->getResourceName(CurrZone.getZoneCritResIdx())
<< "\n";
}
if (OtherResLimited)
dbgs() << " RemainingLimit: "
<< SchedModel->getResourceName(OtherCritIdx) << "\n";
if (!CurrZone.isResourceLimited() && !OtherResLimited)
dbgs() << " Latency limited both directions.\n");
if (CurrZone.isResourceLimited() && !Policy.ReduceResIdx)
Policy.ReduceResIdx = CurrZone.getZoneCritResIdx();
if (OtherResLimited)
Policy.DemandResIdx = OtherCritIdx;
}
#ifndef NDEBUG
const char *GenericSchedulerBase::getReasonStr(
GenericSchedulerBase::CandReason Reason) {
switch (Reason) {
case NoCand: return "NOCAND ";
case PhysRegCopy: return "PREG-COPY";
case RegExcess: return "REG-EXCESS";
case RegCritical: return "REG-CRIT ";
case Stall: return "STALL ";
case Cluster: return "CLUSTER ";
case Weak: return "WEAK ";
case RegMax: return "REG-MAX ";
case ResourceReduce: return "RES-REDUCE";
case ResourceDemand: return "RES-DEMAND";
case TopDepthReduce: return "TOP-DEPTH ";
case TopPathReduce: return "TOP-PATH ";
case BotHeightReduce:return "BOT-HEIGHT";
case BotPathReduce: return "BOT-PATH ";
case NextDefUse: return "DEF-USE ";
case NodeOrder: return "ORDER ";
};
llvm_unreachable("Unknown reason!");
}
void GenericSchedulerBase::traceCandidate(const SchedCandidate &Cand) {
PressureChange P;
unsigned ResIdx = 0;
unsigned Latency = 0;
switch (Cand.Reason) {
default:
break;
case RegExcess:
P = Cand.RPDelta.Excess;
break;
case RegCritical:
P = Cand.RPDelta.CriticalMax;
break;
case RegMax:
P = Cand.RPDelta.CurrentMax;
break;
case ResourceReduce:
ResIdx = Cand.Policy.ReduceResIdx;
break;
case ResourceDemand:
ResIdx = Cand.Policy.DemandResIdx;
break;
case TopDepthReduce:
Latency = Cand.SU->getDepth();
break;
case TopPathReduce:
Latency = Cand.SU->getHeight();
break;
case BotHeightReduce:
Latency = Cand.SU->getHeight();
break;
case BotPathReduce:
Latency = Cand.SU->getDepth();
break;
}
dbgs() << " Cand SU(" << Cand.SU->NodeNum << ") " << getReasonStr(Cand.Reason);
if (P.isValid())
dbgs() << " " << TRI->getRegPressureSetName(P.getPSet())
<< ":" << P.getUnitInc() << " ";
else
dbgs() << " ";
if (ResIdx)
dbgs() << " " << SchedModel->getProcResource(ResIdx)->Name << " ";
else
dbgs() << " ";
if (Latency)
dbgs() << " " << Latency << " cycles ";
else
dbgs() << " ";
dbgs() << '\n';
}
#endif
static bool tryLess(int TryVal, int CandVal,
GenericSchedulerBase::SchedCandidate &TryCand,
GenericSchedulerBase::SchedCandidate &Cand,
GenericSchedulerBase::CandReason 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,
GenericSchedulerBase::SchedCandidate &TryCand,
GenericSchedulerBase::SchedCandidate &Cand,
GenericSchedulerBase::CandReason 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 tryLatency(GenericSchedulerBase::SchedCandidate &TryCand,
GenericSchedulerBase::SchedCandidate &Cand,
SchedBoundary &Zone) {
if (Zone.isTop()) {
if (Cand.SU->getDepth() > Zone.getScheduledLatency()) {
if (tryLess(TryCand.SU->getDepth(), Cand.SU->getDepth(),
TryCand, Cand, GenericSchedulerBase::TopDepthReduce))
return true;
}
if (tryGreater(TryCand.SU->getHeight(), Cand.SU->getHeight(),
TryCand, Cand, GenericSchedulerBase::TopPathReduce))
return true;
}
else {
if (Cand.SU->getHeight() > Zone.getScheduledLatency()) {
if (tryLess(TryCand.SU->getHeight(), Cand.SU->getHeight(),
TryCand, Cand, GenericSchedulerBase::BotHeightReduce))
return true;
}
if (tryGreater(TryCand.SU->getDepth(), Cand.SU->getDepth(),
TryCand, Cand, GenericSchedulerBase::BotPathReduce))
return true;
}
return false;
}
static void tracePick(const GenericSchedulerBase::SchedCandidate &Cand,
bool IsTop) {
DEBUG(dbgs() << "Pick " << (IsTop ? "Top " : "Bot ")
<< GenericSchedulerBase::getReasonStr(Cand.Reason) << '\n');
}
void GenericScheduler::initialize(ScheduleDAGMI *dag) {
assert(dag->hasVRegLiveness() &&
"(PreRA)GenericScheduler needs vreg liveness");
DAG = static_cast<ScheduleDAGMILive*>(dag);
SchedModel = DAG->getSchedModel();
TRI = DAG->TRI;
Rem.init(DAG, SchedModel);
Top.init(DAG, SchedModel, &Rem);
Bot.init(DAG, SchedModel, &Rem);
const InstrItineraryData *Itin = SchedModel->getInstrItineraries();
if (!Top.HazardRec) {
Top.HazardRec =
DAG->MF.getSubtarget().getInstrInfo()->CreateTargetMIHazardRecognizer(
Itin, DAG);
}
if (!Bot.HazardRec) {
Bot.HazardRec =
DAG->MF.getSubtarget().getInstrInfo()->CreateTargetMIHazardRecognizer(
Itin, DAG);
}
}
void GenericScheduler::initPolicy(MachineBasicBlock::iterator Begin,
MachineBasicBlock::iterator End,
unsigned NumRegionInstrs) {
const MachineFunction &MF = *Begin->getParent()->getParent();
const TargetLowering *TLI = MF.getSubtarget().getTargetLowering();
RegionPolicy.ShouldTrackPressure = true;
for (unsigned VT = MVT::i32; VT > (unsigned)MVT::i1; --VT) {
MVT::SimpleValueType LegalIntVT = (MVT::SimpleValueType)VT;
if (TLI->isTypeLegal(LegalIntVT)) {
unsigned NIntRegs = Context->RegClassInfo->getNumAllocatableRegs(
TLI->getRegClassFor(LegalIntVT));
RegionPolicy.ShouldTrackPressure = NumRegionInstrs > (NIntRegs / 2);
}
}
RegionPolicy.OnlyBottomUp = true;
MF.getSubtarget().overrideSchedPolicy(RegionPolicy, Begin, End,
NumRegionInstrs);
if (!EnableRegPressure)
RegionPolicy.ShouldTrackPressure = false;
assert((!ForceTopDown || !ForceBottomUp) &&
"-misched-topdown incompatible with -misched-bottomup");
if (ForceBottomUp.getNumOccurrences() > 0) {
RegionPolicy.OnlyBottomUp = ForceBottomUp;
if (RegionPolicy.OnlyBottomUp)
RegionPolicy.OnlyTopDown = false;
}
if (ForceTopDown.getNumOccurrences() > 0) {
RegionPolicy.OnlyTopDown = ForceTopDown;
if (RegionPolicy.OnlyTopDown)
RegionPolicy.OnlyBottomUp = false;
}
}
void GenericScheduler::dumpPolicy() {
dbgs() << "GenericScheduler RegionPolicy: "
<< " ShouldTrackPressure=" << RegionPolicy.ShouldTrackPressure
<< " OnlyTopDown=" << RegionPolicy.OnlyTopDown
<< " OnlyBottomUp=" << RegionPolicy.OnlyBottomUp
<< "\n";
}
void GenericScheduler::checkAcyclicLatency() {
if (Rem.CyclicCritPath == 0 || Rem.CyclicCritPath >= Rem.CriticalPath)
return;
unsigned IterCount =
std::max(Rem.CyclicCritPath * SchedModel->getLatencyFactor(),
Rem.RemIssueCount);
unsigned AcyclicCount = Rem.CriticalPath * SchedModel->getLatencyFactor();
unsigned InFlightCount =
(AcyclicCount * Rem.RemIssueCount + IterCount-1) / IterCount;
unsigned BufferLimit =
SchedModel->getMicroOpBufferSize() * SchedModel->getMicroOpFactor();
Rem.IsAcyclicLatencyLimited = InFlightCount > BufferLimit;
DEBUG(dbgs() << "IssueCycles="
<< Rem.RemIssueCount / SchedModel->getLatencyFactor() << "c "
<< "IterCycles=" << IterCount / SchedModel->getLatencyFactor()
<< "c NumIters=" << (AcyclicCount + IterCount-1) / IterCount
<< " InFlight=" << InFlightCount / SchedModel->getMicroOpFactor()
<< "m BufferLim=" << SchedModel->getMicroOpBufferSize() << "m\n";
if (Rem.IsAcyclicLatencyLimited)
dbgs() << " ACYCLIC LATENCY LIMIT\n");
}
void GenericScheduler::registerRoots() {
Rem.CriticalPath = DAG->ExitSU.getDepth();
for (std::vector<SUnit*>::const_iterator
I = Bot.Available.begin(), E = Bot.Available.end(); I != E; ++I) {
if ((*I)->getDepth() > Rem.CriticalPath)
Rem.CriticalPath = (*I)->getDepth();
}
DEBUG(dbgs() << "Critical Path(GS-RR ): " << Rem.CriticalPath << '\n');
if (DumpCriticalPathLength) {
errs() << "Critical Path(GS-RR ): " << Rem.CriticalPath << " \n";
}
if (EnableCyclicPath) {
Rem.CyclicCritPath = DAG->computeCyclicCriticalPath();
checkAcyclicLatency();
}
}
static bool tryPressure(const PressureChange &TryP,
const PressureChange &CandP,
GenericSchedulerBase::SchedCandidate &TryCand,
GenericSchedulerBase::SchedCandidate &Cand,
GenericSchedulerBase::CandReason Reason) {
int TryRank = TryP.getPSetOrMax();
int CandRank = CandP.getPSetOrMax();
if (TryRank == CandRank) {
return tryLess(TryP.getUnitInc(), CandP.getUnitInc(), TryCand, Cand,
Reason);
}
if (tryGreater(TryP.getUnitInc() < 0, CandP.getUnitInc() < 0, TryCand, Cand,
Reason)) {
return true;
}
if (TryP.getUnitInc() < 0)
std::swap(TryRank, CandRank);
return tryGreater(TryRank, CandRank, TryCand, Cand, Reason);
}
static unsigned getWeakLeft(const SUnit *SU, bool isTop) {
return (isTop) ? SU->WeakPredsLeft : SU->WeakSuccsLeft;
}
static int biasPhysRegCopy(const SUnit *SU, bool isTop) {
const MachineInstr *MI = SU->getInstr();
if (!MI->isCopy())
return 0;
unsigned ScheduledOper = isTop ? 1 : 0;
unsigned UnscheduledOper = isTop ? 0 : 1;
if (TargetRegisterInfo::isPhysicalRegister(
MI->getOperand(ScheduledOper).getReg()))
return 1;
bool AtBoundary = isTop ? !SU->NumSuccsLeft : !SU->NumPredsLeft;
if (TargetRegisterInfo::isPhysicalRegister(
MI->getOperand(UnscheduledOper).getReg()))
return AtBoundary ? -1 : 1;
return 0;
}
void GenericScheduler::tryCandidate(SchedCandidate &Cand,
SchedCandidate &TryCand,
SchedBoundary &Zone,
const RegPressureTracker &RPTracker,
RegPressureTracker &TempTracker) {
if (DAG->isTrackingPressure()) {
if (Zone.isTop()) {
TempTracker.getMaxDownwardPressureDelta(
TryCand.SU->getInstr(),
TryCand.RPDelta,
DAG->getRegionCriticalPSets(),
DAG->getRegPressure().MaxSetPressure);
}
else {
if (VerifyScheduling) {
TempTracker.getMaxUpwardPressureDelta(
TryCand.SU->getInstr(),
&DAG->getPressureDiff(TryCand.SU),
TryCand.RPDelta,
DAG->getRegionCriticalPSets(),
DAG->getRegPressure().MaxSetPressure);
}
else {
RPTracker.getUpwardPressureDelta(
TryCand.SU->getInstr(),
DAG->getPressureDiff(TryCand.SU),
TryCand.RPDelta,
DAG->getRegionCriticalPSets(),
DAG->getRegPressure().MaxSetPressure);
}
}
}
DEBUG(if (TryCand.RPDelta.Excess.isValid())
dbgs() << " Try SU(" << TryCand.SU->NodeNum << ") "
<< TRI->getRegPressureSetName(TryCand.RPDelta.Excess.getPSet())
<< ":" << TryCand.RPDelta.Excess.getUnitInc() << "\n");
if (!Cand.isValid()) {
TryCand.Reason = NodeOrder;
return;
}
if (tryGreater(biasPhysRegCopy(TryCand.SU, Zone.isTop()),
biasPhysRegCopy(Cand.SU, Zone.isTop()),
TryCand, Cand, PhysRegCopy))
return;
if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.Excess,
Cand.RPDelta.Excess,
TryCand, Cand, RegExcess))
return;
if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.CriticalMax,
Cand.RPDelta.CriticalMax,
TryCand, Cand, RegCritical))
return;
if (Rem.IsAcyclicLatencyLimited && !Zone.getCurrMOps()
&& tryLatency(TryCand, Cand, Zone))
return;
if (tryLess(Zone.getLatencyStallCycles(TryCand.SU),
Zone.getLatencyStallCycles(Cand.SU), TryCand, Cand, Stall))
return;
const SUnit *NextClusterSU =
Zone.isTop() ? DAG->getNextClusterSucc() : DAG->getNextClusterPred();
if (tryGreater(TryCand.SU == NextClusterSU, Cand.SU == NextClusterSU,
TryCand, Cand, Cluster))
return;
if (tryLess(getWeakLeft(TryCand.SU, Zone.isTop()),
getWeakLeft(Cand.SU, Zone.isTop()),
TryCand, Cand, Weak)) {
return;
}
if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.CurrentMax,
Cand.RPDelta.CurrentMax,
TryCand, Cand, RegMax))
return;
TryCand.initResourceDelta(DAG, SchedModel);
if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources,
TryCand, Cand, ResourceReduce))
return;
if (tryGreater(TryCand.ResDelta.DemandedResources,
Cand.ResDelta.DemandedResources,
TryCand, Cand, ResourceDemand))
return;
if (!RegionPolicy.DisableLatencyHeuristic && Cand.Policy.ReduceLatency &&
!Rem.IsAcyclicLatencyLimited && tryLatency(TryCand, Cand, Zone)) {
return;
}
if (tryGreater(Zone.isNextSU(TryCand.SU), Zone.isNextSU(Cand.SU),
TryCand, Cand, NextDefUse))
return;
if ((Zone.isTop() && TryCand.SU->NodeNum < Cand.SU->NodeNum)
|| (!Zone.isTop() && TryCand.SU->NodeNum > Cand.SU->NodeNum)) {
TryCand.Reason = NodeOrder;
}
}
void GenericScheduler::pickNodeFromQueue(SchedBoundary &Zone,
const RegPressureTracker &RPTracker,
SchedCandidate &Cand) {
ReadyQueue &Q = Zone.Available;
DEBUG(Q.dump());
RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
SchedCandidate TryCand(Cand.Policy);
TryCand.SU = *I;
tryCandidate(Cand, TryCand, Zone, RPTracker, TempTracker);
if (TryCand.Reason != NoCand) {
if (TryCand.ResDelta == SchedResourceDelta())
TryCand.initResourceDelta(DAG, SchedModel);
Cand.setBest(TryCand);
DEBUG(traceCandidate(Cand));
}
}
}
SUnit *GenericScheduler::pickNodeBidirectional(bool &IsTopNode) {
if (SUnit *SU = Bot.pickOnlyChoice()) {
IsTopNode = false;
DEBUG(dbgs() << "Pick Bot NOCAND\n");
return SU;
}
if (SUnit *SU = Top.pickOnlyChoice()) {
IsTopNode = true;
DEBUG(dbgs() << "Pick Top NOCAND\n");
return SU;
}
CandPolicy NoPolicy;
SchedCandidate BotCand(NoPolicy);
SchedCandidate TopCand(NoPolicy);
setPolicy(BotCand.Policy, false, Bot, &Top);
setPolicy(TopCand.Policy, false, Top, &Bot);
pickNodeFromQueue(Bot, DAG->getBotRPTracker(), BotCand);
assert(BotCand.Reason != NoCand && "failed to find the first candidate");
if ((BotCand.Reason == RegExcess && !BotCand.isRepeat(RegExcess))
|| (BotCand.Reason == RegCritical
&& !BotCand.isRepeat(RegCritical)))
{
IsTopNode = false;
tracePick(BotCand, IsTopNode);
return BotCand.SU;
}
pickNodeFromQueue(Top, DAG->getTopRPTracker(), TopCand);
assert(TopCand.Reason != NoCand && "failed to find the first candidate");
if (TopCand.Reason < BotCand.Reason) {
IsTopNode = true;
tracePick(TopCand, IsTopNode);
return TopCand.SU;
}
IsTopNode = false;
tracePick(BotCand, IsTopNode);
return BotCand.SU;
}
SUnit *GenericScheduler::pickNode(bool &IsTopNode) {
if (DAG->top() == DAG->bottom()) {
assert(Top.Available.empty() && Top.Pending.empty() &&
Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
return nullptr;
}
SUnit *SU;
do {
if (RegionPolicy.OnlyTopDown) {
SU = Top.pickOnlyChoice();
if (!SU) {
CandPolicy NoPolicy;
SchedCandidate TopCand(NoPolicy);
pickNodeFromQueue(Top, DAG->getTopRPTracker(), TopCand);
assert(TopCand.Reason != NoCand && "failed to find a candidate");
tracePick(TopCand, true);
SU = TopCand.SU;
}
IsTopNode = true;
}
else if (RegionPolicy.OnlyBottomUp) {
SU = Bot.pickOnlyChoice();
if (!SU) {
CandPolicy NoPolicy;
SchedCandidate BotCand(NoPolicy);
pickNodeFromQueue(Bot, DAG->getBotRPTracker(), BotCand);
assert(BotCand.Reason != NoCand && "failed to find a candidate");
tracePick(BotCand, false);
SU = BotCand.SU;
}
IsTopNode = false;
}
else {
SU = pickNodeBidirectional(IsTopNode);
}
} while (SU->isScheduled);
if (SU->isTopReady())
Top.removeReady(SU);
if (SU->isBottomReady())
Bot.removeReady(SU);
DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") " << *SU->getInstr());
return SU;
}
void GenericScheduler::reschedulePhysRegCopies(SUnit *SU, bool isTop) {
MachineBasicBlock::iterator InsertPos = SU->getInstr();
if (!isTop)
++InsertPos;
SmallVectorImpl<SDep> &Deps = isTop ? SU->Preds : SU->Succs;
for (SmallVectorImpl<SDep>::iterator I = Deps.begin(), E = Deps.end();
I != E; ++I) {
if (I->getKind() != SDep::Data || !TRI->isPhysicalRegister(I->getReg()))
continue;
SUnit *DepSU = I->getSUnit();
if (isTop ? DepSU->Succs.size() > 1 : DepSU->Preds.size() > 1)
continue;
MachineInstr *Copy = DepSU->getInstr();
if (!Copy->isCopy())
continue;
DEBUG(dbgs() << " Rescheduling physreg copy ";
I->getSUnit()->dump(DAG));
DAG->moveInstruction(Copy, InsertPos);
}
}
void GenericScheduler::schedNode(SUnit *SU, bool IsTopNode) {
if (IsTopNode) {
SU->TopReadyCycle = std::max(SU->TopReadyCycle, Top.getCurrCycle());
Top.bumpNode(SU);
if (SU->hasPhysRegUses)
reschedulePhysRegCopies(SU, true);
}
else {
SU->BotReadyCycle = std::max(SU->BotReadyCycle, Bot.getCurrCycle());
Bot.bumpNode(SU);
if (SU->hasPhysRegDefs)
reschedulePhysRegCopies(SU, false);
}
}
static ScheduleDAGInstrs *createGenericSchedLive(MachineSchedContext *C) {
ScheduleDAGMILive *DAG = new ScheduleDAGMILive(C, make_unique<GenericScheduler>(C));
DAG->addMutation(make_unique<CopyConstrain>(DAG->TII, DAG->TRI));
if (EnableLoadCluster && DAG->TII->enableClusterLoads())
DAG->addMutation(make_unique<LoadClusterMutation>(DAG->TII, DAG->TRI));
if (EnableMacroFusion)
DAG->addMutation(make_unique<MacroFusion>(*DAG->TII, *DAG->TRI));
return DAG;
}
static MachineSchedRegistry
GenericSchedRegistry("converge", "Standard converging scheduler.",
createGenericSchedLive);
void PostGenericScheduler::initialize(ScheduleDAGMI *Dag) {
DAG = Dag;
SchedModel = DAG->getSchedModel();
TRI = DAG->TRI;
Rem.init(DAG, SchedModel);
Top.init(DAG, SchedModel, &Rem);
BotRoots.clear();
const InstrItineraryData *Itin = SchedModel->getInstrItineraries();
if (!Top.HazardRec) {
Top.HazardRec =
DAG->MF.getSubtarget().getInstrInfo()->CreateTargetMIHazardRecognizer(
Itin, DAG);
}
}
void PostGenericScheduler::registerRoots() {
Rem.CriticalPath = DAG->ExitSU.getDepth();
for (SmallVectorImpl<SUnit*>::const_iterator
I = BotRoots.begin(), E = BotRoots.end(); I != E; ++I) {
if ((*I)->getDepth() > Rem.CriticalPath)
Rem.CriticalPath = (*I)->getDepth();
}
DEBUG(dbgs() << "Critical Path: (PGS-RR) " << Rem.CriticalPath << '\n');
if (DumpCriticalPathLength) {
errs() << "Critical Path(PGS-RR ): " << Rem.CriticalPath << " \n";
}
}
void PostGenericScheduler::tryCandidate(SchedCandidate &Cand,
SchedCandidate &TryCand) {
if (!Cand.isValid()) {
TryCand.Reason = NodeOrder;
return;
}
if (tryLess(Top.getLatencyStallCycles(TryCand.SU),
Top.getLatencyStallCycles(Cand.SU), TryCand, Cand, Stall))
return;
if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources,
TryCand, Cand, ResourceReduce))
return;
if (tryGreater(TryCand.ResDelta.DemandedResources,
Cand.ResDelta.DemandedResources,
TryCand, Cand, ResourceDemand))
return;
if (Cand.Policy.ReduceLatency && tryLatency(TryCand, Cand, Top)) {
return;
}
if (TryCand.SU->NodeNum < Cand.SU->NodeNum)
TryCand.Reason = NodeOrder;
}
void PostGenericScheduler::pickNodeFromQueue(SchedCandidate &Cand) {
ReadyQueue &Q = Top.Available;
DEBUG(Q.dump());
for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
SchedCandidate TryCand(Cand.Policy);
TryCand.SU = *I;
TryCand.initResourceDelta(DAG, SchedModel);
tryCandidate(Cand, TryCand);
if (TryCand.Reason != NoCand) {
Cand.setBest(TryCand);
DEBUG(traceCandidate(Cand));
}
}
}
SUnit *PostGenericScheduler::pickNode(bool &IsTopNode) {
if (DAG->top() == DAG->bottom()) {
assert(Top.Available.empty() && Top.Pending.empty() && "ReadyQ garbage");
return nullptr;
}
SUnit *SU;
do {
SU = Top.pickOnlyChoice();
if (!SU) {
CandPolicy NoPolicy;
SchedCandidate TopCand(NoPolicy);
setPolicy(TopCand.Policy, true, Top, nullptr);
pickNodeFromQueue(TopCand);
assert(TopCand.Reason != NoCand && "failed to find a candidate");
tracePick(TopCand, true);
SU = TopCand.SU;
}
} while (SU->isScheduled);
IsTopNode = true;
Top.removeReady(SU);
DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") " << *SU->getInstr());
return SU;
}
void PostGenericScheduler::schedNode(SUnit *SU, bool IsTopNode) {
SU->TopReadyCycle = std::max(SU->TopReadyCycle, Top.getCurrCycle());
Top.bumpNode(SU);
}
static ScheduleDAGInstrs *createGenericSchedPostRA(MachineSchedContext *C) {
return new ScheduleDAGMI(C, make_unique<PostGenericScheduler>(C), true);
}
namespace {
struct ILPOrder {
const SchedDFSResult *DFSResult;
const BitVector *ScheduledTrees;
bool MaximizeILP;
ILPOrder(bool MaxILP)
: DFSResult(nullptr), ScheduledTrees(nullptr), MaximizeILP(MaxILP) {}
bool operator()(const SUnit *A, const SUnit *B) const {
unsigned SchedTreeA = DFSResult->getSubtreeID(A);
unsigned SchedTreeB = DFSResult->getSubtreeID(B);
if (SchedTreeA != SchedTreeB) {
if (ScheduledTrees->test(SchedTreeA) != ScheduledTrees->test(SchedTreeB))
return ScheduledTrees->test(SchedTreeB);
if (DFSResult->getSubtreeLevel(SchedTreeA)
!= DFSResult->getSubtreeLevel(SchedTreeB)) {
return DFSResult->getSubtreeLevel(SchedTreeA)
< DFSResult->getSubtreeLevel(SchedTreeB);
}
}
if (MaximizeILP)
return DFSResult->getILP(A) < DFSResult->getILP(B);
else
return DFSResult->getILP(A) > DFSResult->getILP(B);
}
};
class ILPScheduler : public MachineSchedStrategy {
ScheduleDAGMILive *DAG;
ILPOrder Cmp;
std::vector<SUnit*> ReadyQ;
public:
ILPScheduler(bool MaximizeILP): DAG(nullptr), Cmp(MaximizeILP) {}
void initialize(ScheduleDAGMI *dag) override {
assert(dag->hasVRegLiveness() && "ILPScheduler needs vreg liveness");
DAG = static_cast<ScheduleDAGMILive*>(dag);
DAG->computeDFSResult();
Cmp.DFSResult = DAG->getDFSResult();
Cmp.ScheduledTrees = &DAG->getScheduledTrees();
ReadyQ.clear();
}
void registerRoots() override {
std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
}
SUnit *pickNode(bool &IsTopNode) override {
if (ReadyQ.empty()) return nullptr;
std::pop_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
SUnit *SU = ReadyQ.back();
ReadyQ.pop_back();
IsTopNode = false;
DEBUG(dbgs() << "Pick node " << "SU(" << SU->NodeNum << ") "
<< " ILP: " << DAG->getDFSResult()->getILP(SU)
<< " Tree: " << DAG->getDFSResult()->getSubtreeID(SU) << " @"
<< DAG->getDFSResult()->getSubtreeLevel(
DAG->getDFSResult()->getSubtreeID(SU)) << '\n'
<< "Scheduling " << *SU->getInstr());
return SU;
}
void scheduleTree(unsigned SubtreeID) override {
std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
}
void schedNode(SUnit *SU, bool IsTopNode) override {
assert(!IsTopNode && "SchedDFSResult needs bottom-up");
}
void releaseTopNode(SUnit *) override { }
void releaseBottomNode(SUnit *SU) override {
ReadyQ.push_back(SU);
std::push_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
}
};
}
static ScheduleDAGInstrs *createILPMaxScheduler(MachineSchedContext *C) {
return new ScheduleDAGMILive(C, make_unique<ILPScheduler>(true));
}
static ScheduleDAGInstrs *createILPMinScheduler(MachineSchedContext *C) {
return new ScheduleDAGMILive(C, make_unique<ILPScheduler>(false));
}
static MachineSchedRegistry ILPMaxRegistry(
"ilpmax", "Schedule bottom-up for max ILP", createILPMaxScheduler);
static MachineSchedRegistry ILPMinRegistry(
"ilpmin", "Schedule bottom-up for min ILP", createILPMinScheduler);
#ifndef NDEBUG
namespace {
template<bool IsReverse>
struct SUnitOrder {
bool operator()(SUnit *A, SUnit *B) const {
if (IsReverse)
return A->NodeNum > B->NodeNum;
else
return A->NodeNum < B->NodeNum;
}
};
class InstructionShuffler : public MachineSchedStrategy {
bool IsAlternating;
bool IsTopDown;
PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<false> >
TopQ;
PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<true> >
BottomQ;
public:
InstructionShuffler(bool alternate, bool topdown)
: IsAlternating(alternate), IsTopDown(topdown) {}
void initialize(ScheduleDAGMI*) override {
TopQ.clear();
BottomQ.clear();
}
SUnit *pickNode(bool &IsTopNode) override {
SUnit *SU;
if (IsTopDown) {
do {
if (TopQ.empty()) return nullptr;
SU = TopQ.top();
TopQ.pop();
} while (SU->isScheduled);
IsTopNode = true;
}
else {
do {
if (BottomQ.empty()) return nullptr;
SU = BottomQ.top();
BottomQ.pop();
} while (SU->isScheduled);
IsTopNode = false;
}
if (IsAlternating)
IsTopDown = !IsTopDown;
return SU;
}
void schedNode(SUnit *SU, bool IsTopNode) override {}
void releaseTopNode(SUnit *SU) override {
TopQ.push(SU);
}
void releaseBottomNode(SUnit *SU) override {
BottomQ.push(SU);
}
};
}
static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedContext *C) {
bool Alternate = !ForceTopDown && !ForceBottomUp;
bool TopDown = !ForceBottomUp;
assert((TopDown || !ForceTopDown) &&
"-misched-topdown incompatible with -misched-bottomup");
return new ScheduleDAGMILive(C, make_unique<InstructionShuffler>(Alternate, TopDown));
}
static MachineSchedRegistry ShufflerRegistry(
"shuffle", "Shuffle machine instructions alternating directions",
createInstructionShuffler);
#endif // !NDEBUG
#ifndef NDEBUG
namespace llvm {
template<> struct GraphTraits<
ScheduleDAGMI*> : public GraphTraits<ScheduleDAG*> {};
template<>
struct DOTGraphTraits<ScheduleDAGMI*> : public DefaultDOTGraphTraits {
DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
static std::string getGraphName(const ScheduleDAG *G) {
return G->MF.getName();
}
static bool renderGraphFromBottomUp() {
return true;
}
static bool isNodeHidden(const SUnit *Node) {
if (ViewMISchedCutoff == 0)
return false;
return (Node->Preds.size() > ViewMISchedCutoff
|| Node->Succs.size() > ViewMISchedCutoff);
}
static std::string getEdgeAttributes(const SUnit *Node,
SUnitIterator EI,
const ScheduleDAG *Graph) {
if (EI.isArtificialDep())
return "color=cyan,style=dashed";
if (EI.isCtrlDep())
return "color=blue,style=dashed";
return "";
}
static std::string getNodeLabel(const SUnit *SU, const ScheduleDAG *G) {
std::string Str;
raw_string_ostream SS(Str);
const ScheduleDAGMI *DAG = static_cast<const ScheduleDAGMI*>(G);
const SchedDFSResult *DFS = DAG->hasVRegLiveness() ?
static_cast<const ScheduleDAGMILive*>(G)->getDFSResult() : nullptr;
SS << "SU:" << SU->NodeNum;
if (DFS)
SS << " I:" << DFS->getNumInstrs(SU);
return SS.str();
}
static std::string getNodeDescription(const SUnit *SU, const ScheduleDAG *G) {
return G->getGraphNodeLabel(SU);
}
static std::string getNodeAttributes(const SUnit *N, const ScheduleDAG *G) {
std::string Str("shape=Mrecord");
const ScheduleDAGMI *DAG = static_cast<const ScheduleDAGMI*>(G);
const SchedDFSResult *DFS = DAG->hasVRegLiveness() ?
static_cast<const ScheduleDAGMILive*>(G)->getDFSResult() : nullptr;
if (DFS) {
Str += ",style=filled,fillcolor=\"#";
Str += DOT::getColorString(DFS->getSubtreeID(N));
Str += '"';
}
return Str;
}
};
} #endif // NDEBUG
void ScheduleDAGMI::viewGraph(const Twine &Name, const Twine &Title) {
#ifndef NDEBUG
ViewGraph(this, Name, false, Title);
#else
errs() << "ScheduleDAGMI::viewGraph is only available in debug builds on "
<< "systems with Graphviz or gv!\n";
#endif // NDEBUG
}
void ScheduleDAGMI::viewGraph() {
viewGraph(getDAGName(), "Scheduling-Units Graph for " + getDAGName());
}