//
//===----------------------------------------------------------------------===//
-#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;
}
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) {
- for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
- if (IsChainDependent(N->getOperand(i).getNode(), Inner, NestLevel, TII))
+ for (const SDValue &Op : N->op_values())
+ if (IsChainDependent(Op.getNode(), Inner, NestLevel, TII))
return true;
return false;
}
}
}
// Otherwise, find the chain and continue climbing.
- for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
- if (N->getOperand(i).getValueType() == MVT::Other) {
- N = N->getOperand(i).getNode();
+ for (const SDValue &Op : N->op_values())
+ if (Op.getValueType() == MVT::Other) {
+ N = Op.getNode();
goto found_chain_operand;
}
return false;
// 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) {
+ for (const SDValue &Op : N->op_values()) {
unsigned MyNestLevel = NestLevel;
unsigned MyMaxNest = MaxNest;
- if (SDNode *New = FindCallSeqStart(N->getOperand(i).getNode(),
+ if (SDNode *New = FindCallSeqStart(Op.getNode(),
MyNestLevel, MyMaxNest, TII))
if (!Best || (MyMaxNest > BestMaxNest)) {
Best = New;
}
}
// Otherwise, find the chain and continue climbing.
- for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
- if (N->getOperand(i).getValueType() == MVT::Other) {
- N = N->getOperand(i).getNode();
+ for (const SDValue &Op : N->op_values())
+ if (Op.getValueType() == MVT::Other) {
+ N = Op.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);
}
}
- for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
- I != E; ++I) {
- if (I->isAssignedRegDep()) {
- if (!LiveRegDefs[I->getReg()])
+ for (auto &Succ : SU->Succs) {
+ if (Succ.isAssignedRegDep()) {
+ auto Reg = Succ.getReg();
+ if (!LiveRegDefs[Reg])
++NumLiveRegs;
// 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 ||
- I->getSUnit()->getHeight() < LiveRegGens[I->getReg()]->getHeight())
- LiveRegGens[I->getReg()] = I->getSUnit();
+ LiveRegDefs[Reg] = SU;
+
+ // Update LiveRegGen only if was empty before this unscheduling.
+ // This is to avoid incorrect updating LiveRegGen set in previous run.
+ if (!LiveRegGens[Reg]) {
+ // Find the successor with the lowest height.
+ LiveRegGens[Reg] = Succ.getSUnit();
+ for (auto &Succ2 : SU->Succs) {
+ if (Succ2.isAssignedRegDep() && Succ2.getReg() == Reg &&
+ Succ2.getSUnit()->getHeight() < LiveRegGens[Reg]->getHeight())
+ LiveRegGens[Reg] = Succ2.getSUnit();
+ }
+ }
}
}
if (SU->getHeight() < MinAvailableCycle)
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());
+ for (const SDValue &Op : N->op_values()) {
+ 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);
}
}
/// getNodeRegMask - Returns the register mask attached to an SDNode, if any.
static const uint32_t *getNodeRegMask(const SDNode *N) {
- for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
- if (const RegisterMaskSDNode *Op =
- dyn_cast<RegisterMaskSDNode>(N->getOperand(i).getNode()))
- return Op->getRegMask();
- return NULL;
+ for (const SDValue &Op : N->op_values())
+ if (const auto *RegOp = dyn_cast<RegisterMaskSDNode>(Op.getNode()))
+ return RegOp->getRegMask();
+ 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)
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);
void updateNode(const SUnit *SU) override;
void releaseState() override {
- SUnits = 0;
+ SUnits = nullptr;
SethiUllmanNumbers.clear();
std::fill(RegPressure.begin(), RegPressure.end(), 0);
}
}
SUnit *pop() override {
- if (Queue.empty()) return NULL;
+ 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);
projects / oota-llvm.git / blobdiff