//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "pre-RA-sched"
#include "llvm/CodeGen/SchedulerRegistry.h"
#include "ScheduleDAGSDNodes.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetLowering.h"
-#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"
+#include "llvm/Target/TargetSubtargetInfo.h"
#include <climits>
using namespace llvm;
+#define DEBUG_TYPE "pre-RA-sched"
+
STATISTIC(NumBacktracks, "Number of times scheduler backtracked");
STATISTIC(NumUnfolds, "Number of nodes unfolded");
STATISTIC(NumDups, "Number of duplicated nodes");
CodeGenOpt::Level OptLevel)
: ScheduleDAGSDNodes(mf),
NeedLatency(needlatency), AvailableQueue(availqueue), CurCycle(0),
- Topo(SUnits, NULL) {
+ Topo(SUnits, nullptr) {
- const TargetMachine &tm = mf.getTarget();
+ const TargetSubtargetInfo &STI = mf.getSubtarget();
if (DisableSchedCycles || !NeedLatency)
HazardRec = new ScheduleHazardRecognizer();
else
- HazardRec = tm.getInstrInfo()->CreateTargetHazardRecognizer(&tm, this);
+ HazardRec = STI.getInstrInfo()->CreateTargetHazardRecognizer(&STI, this);
}
- ~ScheduleDAGRRList() {
+ ~ScheduleDAGRRList() override {
delete HazardRec;
delete AvailableQueue;
}
- void Schedule();
+ void Schedule() override;
ScheduleHazardRecognizer *getHazardRec() { return HazardRec; }
/// forceUnitLatencies - Register-pressure-reducing scheduling doesn't
/// need actual latency information but the hybrid scheduler does.
- bool forceUnitLatencies() const {
+ bool forceUnitLatencies() const override {
return !NeedLatency;
}
};
NumLiveRegs = 0;
// Allocate slots for each physical register, plus one for a special register
// to track the virtual resource of a calling sequence.
- LiveRegDefs.resize(TRI->getNumRegs() + 1, NULL);
- LiveRegGens.resize(TRI->getNumRegs() + 1, NULL);
+ LiveRegDefs.resize(TRI->getNumRegs() + 1, nullptr);
+ LiveRegGens.resize(TRI->getNumRegs() + 1, nullptr);
CallSeqEndForStart.clear();
assert(Interferences.empty() && LRegsMap.empty() && "stale Interferences");
// Build the scheduling graph.
- BuildSchedGraph(NULL);
+ BuildSchedGraph(nullptr);
DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
SUnits[su].dumpAll(this));
dbgs() << "*** Scheduling failed! ***\n";
PredSU->dump(this);
dbgs() << " has been released too many times!\n";
- llvm_unreachable(0);
+ llvm_unreachable(nullptr);
}
#endif
--PredSU->NumSuccsLeft;
// to get to the CALLSEQ_BEGIN, but we need to find the path with the
// most nesting in order to ensure that we find the corresponding match.
if (N->getOpcode() == ISD::TokenFactor) {
- SDNode *Best = 0;
+ SDNode *Best = nullptr;
unsigned BestMaxNest = MaxNest;
for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
unsigned MyNestLevel = NestLevel;
N = N->getOperand(i).getNode();
goto found_chain_operand;
}
- return 0;
+ return nullptr;
found_chain_operand:;
if (N->getOpcode() == ISD::EntryToken)
- return 0;
+ return nullptr;
}
}
if (I->isAssignedRegDep() && LiveRegDefs[I->getReg()] == SU) {
assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
--NumLiveRegs;
- LiveRegDefs[I->getReg()] = NULL;
- LiveRegGens[I->getReg()] = NULL;
+ LiveRegDefs[I->getReg()] = nullptr;
+ LiveRegGens[I->getReg()] = nullptr;
releaseInterferences(I->getReg());
}
}
SUNode->getMachineOpcode() == (unsigned)TII->getCallFrameSetupOpcode()) {
assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
--NumLiveRegs;
- LiveRegDefs[CallResource] = NULL;
- LiveRegGens[CallResource] = NULL;
+ LiveRegDefs[CallResource] = nullptr;
+ LiveRegGens[CallResource] = nullptr;
releaseInterferences(CallResource);
}
}
assert(LiveRegDefs[I->getReg()] == I->getSUnit() &&
"Physical register dependency violated?");
--NumLiveRegs;
- LiveRegDefs[I->getReg()] = NULL;
- LiveRegGens[I->getReg()] = NULL;
+ LiveRegDefs[I->getReg()] = nullptr;
+ LiveRegGens[I->getReg()] = nullptr;
releaseInterferences(I->getReg());
}
}
SUNode->getMachineOpcode() == (unsigned)TII->getCallFrameDestroyOpcode()) {
assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
--NumLiveRegs;
- LiveRegDefs[CallResource] = NULL;
- LiveRegGens[CallResource] = NULL;
+ LiveRegDefs[CallResource] = nullptr;
+ LiveRegGens[CallResource] = nullptr;
releaseInterferences(CallResource);
}
}
// This becomes the nearest def. Note that an earlier def may still be
// pending if this is a two-address node.
LiveRegDefs[I->getReg()] = SU;
- if (LiveRegGens[I->getReg()] == NULL ||
+ if (LiveRegGens[I->getReg()] == nullptr ||
I->getSUnit()->getHeight() < LiveRegGens[I->getReg()]->getHeight())
LiveRegGens[I->getReg()] = I->getSUnit();
}
SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) {
SDNode *N = SU->getNode();
if (!N)
- return NULL;
+ return nullptr;
if (SU->getNode()->getGluedNode())
- return NULL;
+ return nullptr;
SUnit *NewSU;
bool TryUnfold = false;
for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
- EVT VT = N->getValueType(i);
+ MVT VT = N->getSimpleValueType(i);
if (VT == MVT::Glue)
- return NULL;
+ return nullptr;
else if (VT == MVT::Other)
TryUnfold = true;
}
for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
const SDValue &Op = N->getOperand(i);
- EVT VT = Op.getNode()->getValueType(Op.getResNo());
+ MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
if (VT == MVT::Glue)
- return NULL;
+ return nullptr;
}
if (TryUnfold) {
SmallVector<SDNode*, 2> NewNodes;
if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes))
- return NULL;
+ return nullptr;
// unfolding an x86 DEC64m operation results in store, dec, load which
// can't be handled here so quit
if (NewNodes.size() == 3)
- return NULL;
+ return nullptr;
DEBUG(dbgs() << "Unfolding SU #" << SU->NodeNum << "\n");
assert(NewNodes.size() == 2 && "Expected a load folding node!");
const TargetRegisterClass *DestRC,
const TargetRegisterClass *SrcRC,
SmallVectorImpl<SUnit*> &Copies) {
- SUnit *CopyFromSU = CreateNewSUnit(NULL);
+ SUnit *CopyFromSU = CreateNewSUnit(nullptr);
CopyFromSU->CopySrcRC = SrcRC;
CopyFromSU->CopyDstRC = DestRC;
- SUnit *CopyToSU = CreateNewSUnit(NULL);
+ SUnit *CopyToSU = CreateNewSUnit(nullptr);
CopyToSU->CopySrcRC = DestRC;
CopyToSU->CopyDstRC = SrcRC;
/// getPhysicalRegisterVT - Returns the ValueType of the physical register
/// definition of the specified node.
/// FIXME: Move to SelectionDAG?
-static EVT getPhysicalRegisterVT(SDNode *N, unsigned Reg,
+static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg,
const TargetInstrInfo *TII) {
- const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
- assert(MCID.ImplicitDefs && "Physical reg def must be in implicit def list!");
- unsigned NumRes = MCID.getNumDefs();
- for (const uint16_t *ImpDef = MCID.getImplicitDefs(); *ImpDef; ++ImpDef) {
- if (Reg == *ImpDef)
- break;
- ++NumRes;
+ unsigned NumRes;
+ if (N->getOpcode() == ISD::CopyFromReg) {
+ // CopyFromReg has: "chain, Val, glue" so operand 1 gives the type.
+ NumRes = 1;
+ } else {
+ const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
+ assert(MCID.ImplicitDefs && "Physical reg def must be in implicit def list!");
+ NumRes = MCID.getNumDefs();
+ for (const uint16_t *ImpDef = MCID.getImplicitDefs(); *ImpDef; ++ImpDef) {
+ if (Reg == *ImpDef)
+ break;
+ ++NumRes;
+ }
}
- return N->getValueType(NumRes);
+ return N->getSimpleValueType(NumRes);
}
/// CheckForLiveRegDef - Return true and update live register vector if the
if (LiveRegDefs[*AliasI] == SU) continue;
// Add Reg to the set of interfering live regs.
- if (RegAdded.insert(*AliasI)) {
+ if (RegAdded.insert(*AliasI).second) {
LRegs.push_back(*AliasI);
}
}
if (!LiveRegDefs[i]) continue;
if (LiveRegDefs[i] == SU) continue;
if (!MachineOperand::clobbersPhysReg(RegMask, i)) continue;
- if (RegAdded.insert(i))
+ if (RegAdded.insert(i).second)
LRegs.push_back(i);
}
}
if (const RegisterMaskSDNode *Op =
dyn_cast<RegisterMaskSDNode>(N->getOperand(i).getNode()))
return Op->getRegMask();
- return NULL;
+ return nullptr;
}
/// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
SDNode *Gen = LiveRegGens[CallResource]->getNode();
while (SDNode *Glued = Gen->getGluedNode())
Gen = Glued;
- if (!IsChainDependent(Gen, Node, 0, TII) && RegAdded.insert(CallResource))
+ if (!IsChainDependent(Gen, Node, 0, TII) &&
+ RegAdded.insert(CallResource).second)
LRegs.push_back(CallResource);
}
}
/// (2) No Hazards: resources are available
/// (3) No Interferences: may unschedule to break register interferences.
SUnit *ScheduleDAGRRList::PickNodeToScheduleBottomUp() {
- SUnit *CurSU = AvailableQueue->empty() ? 0 : AvailableQueue->pop();
+ SUnit *CurSU = AvailableQueue->empty() ? nullptr : AvailableQueue->pop();
while (CurSU) {
SmallVector<unsigned, 4> LRegs;
if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
Interferences.push_back(CurSU);
}
else {
- assert(CurSU->isPending && "Intereferences are pending");
+ assert(CurSU->isPending && "Interferences are pending");
// Update the interference with current live regs.
LRegsPair.first->second = LRegs;
}
// Try unscheduling up to the point where it's safe to schedule
// this node.
- SUnit *BtSU = NULL;
+ SUnit *BtSU = nullptr;
unsigned LiveCycle = UINT_MAX;
for (unsigned j = 0, ee = LRegs.size(); j != ee; ++j) {
unsigned Reg = LRegs[j];
// If one or more successors has been unscheduled, then the current
// node is no longer available.
- if (!TrySU->isAvailable)
+ if (!TrySU->isAvailable || !TrySU->NodeQueueId)
CurSU = AvailableQueue->pop();
else {
+ // Available and in AvailableQueue
AvailableQueue->remove(TrySU);
CurSU = TrySU;
}
assert(LRegs.size() == 1 && "Can't handle this yet!");
unsigned Reg = LRegs[0];
SUnit *LRDef = LiveRegDefs[Reg];
- EVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII);
+ MVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII);
const TargetRegisterClass *RC =
TRI->getMinimalPhysRegClass(Reg, VT);
const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
// expensive.
// If cross copy register class is null, then it's not possible to copy
// the value at all.
- SUnit *NewDef = 0;
+ SUnit *NewDef = nullptr;
if (DestRC != RC) {
NewDef = CopyAndMoveSuccessors(LRDef);
if (!DestRC && !NewDef)
struct reverse_sort : public queue_sort {
SF &SortFunc;
reverse_sort(SF &sf) : SortFunc(sf) {}
- reverse_sort(const reverse_sort &RHS) : SortFunc(RHS.SortFunc) {}
bool operator()(SUnit* left, SUnit* right) const {
// reverse left/right rather than simply !SortFunc(left, right)
RegReductionPQBase *SPQ;
bu_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
- bu_ls_rr_sort(const bu_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
bool operator()(SUnit* left, SUnit* right) const;
};
RegReductionPQBase *SPQ;
src_ls_rr_sort(RegReductionPQBase *spq)
: SPQ(spq) {}
- src_ls_rr_sort(const src_ls_rr_sort &RHS)
- : SPQ(RHS.SPQ) {}
bool operator()(SUnit* left, SUnit* right) const;
};
RegReductionPQBase *SPQ;
hybrid_ls_rr_sort(RegReductionPQBase *spq)
: SPQ(spq) {}
- hybrid_ls_rr_sort(const hybrid_ls_rr_sort &RHS)
- : SPQ(RHS.SPQ) {}
bool isReady(SUnit *SU, unsigned CurCycle) const;
RegReductionPQBase *SPQ;
ilp_ls_rr_sort(RegReductionPQBase *spq)
: SPQ(spq) {}
- ilp_ls_rr_sort(const ilp_ls_rr_sort &RHS)
- : SPQ(RHS.SPQ) {}
bool isReady(SUnit *SU, unsigned CurCycle) const;
const TargetLowering *tli)
: SchedulingPriorityQueue(hasReadyFilter),
CurQueueId(0), TracksRegPressure(tracksrp), SrcOrder(srcorder),
- MF(mf), TII(tii), TRI(tri), TLI(tli), scheduleDAG(NULL) {
+ MF(mf), TII(tii), TRI(tri), TLI(tli), scheduleDAG(nullptr) {
if (TracksRegPressure) {
unsigned NumRC = TRI->getNumRegClasses();
RegLimit.resize(NumRC);
return scheduleDAG->getHazardRec();
}
- void initNodes(std::vector<SUnit> &sunits);
+ void initNodes(std::vector<SUnit> &sunits) override;
- void addNode(const SUnit *SU);
+ void addNode(const SUnit *SU) override;
- void updateNode(const SUnit *SU);
+ void updateNode(const SUnit *SU) override;
- void releaseState() {
- SUnits = 0;
+ void releaseState() override {
+ SUnits = nullptr;
SethiUllmanNumbers.clear();
std::fill(RegPressure.begin(), RegPressure.end(), 0);
}
return SU->getNode()->getIROrder();
}
- bool empty() const { return Queue.empty(); }
+ bool empty() const override { return Queue.empty(); }
- void push(SUnit *U) {
+ void push(SUnit *U) override {
assert(!U->NodeQueueId && "Node in the queue already");
U->NodeQueueId = ++CurQueueId;
Queue.push_back(U);
}
- void remove(SUnit *SU) {
+ void remove(SUnit *SU) override {
assert(!Queue.empty() && "Queue is empty!");
assert(SU->NodeQueueId != 0 && "Not in queue!");
std::vector<SUnit *>::iterator I = std::find(Queue.begin(), Queue.end(),
SU);
- if (I != prior(Queue.end()))
+ if (I != std::prev(Queue.end()))
std::swap(*I, Queue.back());
Queue.pop_back();
SU->NodeQueueId = 0;
}
- bool tracksRegPressure() const { return TracksRegPressure; }
+ bool tracksRegPressure() const override { return TracksRegPressure; }
void dumpRegPressure() const;
int RegPressureDiff(SUnit *SU, unsigned &LiveUses) const;
- void scheduledNode(SUnit *SU);
+ void scheduledNode(SUnit *SU) override;
- void unscheduledNode(SUnit *SU);
+ void unscheduledNode(SUnit *SU) override;
protected:
bool canClobber(const SUnit *SU, const SUnit *Op);
template<class SF>
static SUnit *popFromQueueImpl(std::vector<SUnit*> &Q, SF &Picker) {
std::vector<SUnit *>::iterator Best = Q.begin();
- for (std::vector<SUnit *>::iterator I = llvm::next(Q.begin()),
+ for (std::vector<SUnit *>::iterator I = std::next(Q.begin()),
E = Q.end(); I != E; ++I)
if (Picker(*Best, *I))
Best = I;
SUnit *V = *Best;
- if (Best != prior(Q.end()))
+ if (Best != std::prev(Q.end()))
std::swap(*Best, Q.back());
Q.pop_back();
return V;
tii, tri, tli),
Picker(this) {}
- bool isBottomUp() const { return SF::IsBottomUp; }
+ bool isBottomUp() const override { return SF::IsBottomUp; }
- bool isReady(SUnit *U) const {
+ bool isReady(SUnit *U) const override {
return Picker.HasReadyFilter && Picker.isReady(U, getCurCycle());
}
- SUnit *pop() {
- if (Queue.empty()) return NULL;
+ SUnit *pop() override {
+ if (Queue.empty()) return nullptr;
SUnit *V = popFromQueue(Queue, Picker, scheduleDAG);
V->NodeQueueId = 0;
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
- void dump(ScheduleDAG *DAG) const {
+ void dump(ScheduleDAG *DAG) const override {
// Emulate pop() without clobbering NodeQueueIds.
std::vector<SUnit*> DumpQueue = Queue;
SF DumpPicker = Picker;
unsigned Id = RC->getID();
unsigned RP = RegPressure[Id];
if (!RP) continue;
- DEBUG(dbgs() << RC->getName() << ": " << RP << " / " << RegLimit[Id]
- << '\n');
+ DEBUG(dbgs() << TRI->getRegClassName(RC) << ": " << RP << " / "
+ << RegLimit[Id] << '\n');
}
#endif
}
if (!SUImpDefs && !SURegMask)
continue;
for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) {
- EVT VT = N->getValueType(i);
+ MVT VT = N->getSimpleValueType(i);
if (VT == MVT::Glue || VT == MVT::Other)
continue;
if (!N->hasAnyUseOfValue(i))
continue;
// Locate the single data predecessor.
- SUnit *PredSU = 0;
+ SUnit *PredSU = nullptr;
for (SUnit::const_pred_iterator II = SU->Preds.begin(),
EE = SU->Preds.end(); II != EE; ++II)
if (!II->isCtrl()) {
llvm::ScheduleDAGSDNodes *
llvm::createBURRListDAGScheduler(SelectionDAGISel *IS,
CodeGenOpt::Level OptLevel) {
- const TargetMachine &TM = IS->TM;
- const TargetInstrInfo *TII = TM.getInstrInfo();
- const TargetRegisterInfo *TRI = TM.getRegisterInfo();
+ const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
+ const TargetInstrInfo *TII = STI.getInstrInfo();
+ const TargetRegisterInfo *TRI = STI.getRegisterInfo();
BURegReductionPriorityQueue *PQ =
- new BURegReductionPriorityQueue(*IS->MF, false, false, TII, TRI, 0);
+ new BURegReductionPriorityQueue(*IS->MF, false, false, TII, TRI, nullptr);
ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, false, PQ, OptLevel);
PQ->setScheduleDAG(SD);
return SD;
llvm::ScheduleDAGSDNodes *
llvm::createSourceListDAGScheduler(SelectionDAGISel *IS,
CodeGenOpt::Level OptLevel) {
- const TargetMachine &TM = IS->TM;
- const TargetInstrInfo *TII = TM.getInstrInfo();
- const TargetRegisterInfo *TRI = TM.getRegisterInfo();
+ const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
+ const TargetInstrInfo *TII = STI.getInstrInfo();
+ const TargetRegisterInfo *TRI = STI.getRegisterInfo();
SrcRegReductionPriorityQueue *PQ =
- new SrcRegReductionPriorityQueue(*IS->MF, false, true, TII, TRI, 0);
+ new SrcRegReductionPriorityQueue(*IS->MF, false, true, TII, TRI, nullptr);
ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, false, PQ, OptLevel);
PQ->setScheduleDAG(SD);
return SD;
llvm::ScheduleDAGSDNodes *
llvm::createHybridListDAGScheduler(SelectionDAGISel *IS,
CodeGenOpt::Level OptLevel) {
- const TargetMachine &TM = IS->TM;
- const TargetInstrInfo *TII = TM.getInstrInfo();
- const TargetRegisterInfo *TRI = TM.getRegisterInfo();
- const TargetLowering *TLI = IS->getTargetLowering();
+ const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
+ const TargetInstrInfo *TII = STI.getInstrInfo();
+ const TargetRegisterInfo *TRI = STI.getRegisterInfo();
+ const TargetLowering *TLI = IS->TLI;
HybridBURRPriorityQueue *PQ =
new HybridBURRPriorityQueue(*IS->MF, true, false, TII, TRI, TLI);
llvm::ScheduleDAGSDNodes *
llvm::createILPListDAGScheduler(SelectionDAGISel *IS,
CodeGenOpt::Level OptLevel) {
- const TargetMachine &TM = IS->TM;
- const TargetInstrInfo *TII = TM.getInstrInfo();
- const TargetRegisterInfo *TRI = TM.getRegisterInfo();
- const TargetLowering *TLI = IS->getTargetLowering();
+ const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
+ const TargetInstrInfo *TII = STI.getInstrInfo();
+ const TargetRegisterInfo *TRI = STI.getRegisterInfo();
+ const TargetLowering *TLI = IS->TLI;
ILPBURRPriorityQueue *PQ =
new ILPBURRPriorityQueue(*IS->MF, true, false, TII, TRI, TLI);