std::vector<SUnit*> LiveRegDefs;
std::vector<SUnit*> LiveRegGens;
+ // Collect interferences between physical register use/defs.
+ // Each interference is an SUnit and set of physical registers.
+ SmallVector<SUnit*, 4> Interferences;
+ typedef DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMapT;
+ LRegsMapT LRegsMap;
+
/// Topo - A topological ordering for SUnits which permits fast IsReachable
/// and similar queries.
ScheduleDAGTopologicalSort Topo;
void InsertCopiesAndMoveSuccs(SUnit*, unsigned,
const TargetRegisterClass*,
const TargetRegisterClass*,
- SmallVector<SUnit*, 2>&);
- bool DelayForLiveRegsBottomUp(SUnit*, SmallVector<unsigned, 4>&);
+ SmallVectorImpl<SUnit*>&);
+ bool DelayForLiveRegsBottomUp(SUnit*, SmallVectorImpl<unsigned>&);
+
+ void releaseInterferences(unsigned Reg = 0);
SUnit *PickNodeToScheduleBottomUp();
void ListScheduleBottomUp();
LiveRegDefs.resize(TRI->getNumRegs() + 1, NULL);
LiveRegGens.resize(TRI->getNumRegs() + 1, NULL);
CallSeqEndForStart.clear();
+ assert(Interferences.empty() && LRegsMap.empty() && "stale Interferences");
// Build the scheduling graph.
BuildSchedGraph(NULL);
// indicate the scheduled cycle.
SU->setHeightToAtLeast(CurCycle);
- // Reserve resources for the scheduled intruction.
+ // Reserve resources for the scheduled instruction.
EmitNode(SU);
Sequence.push_back(SU);
--NumLiveRegs;
LiveRegDefs[I->getReg()] = NULL;
LiveRegGens[I->getReg()] = NULL;
+ releaseInterferences(I->getReg());
}
}
// Release the special call resource dependence, if this is the beginning
--NumLiveRegs;
LiveRegDefs[CallResource] = NULL;
LiveRegGens[CallResource] = NULL;
+ releaseInterferences(CallResource);
}
}
--NumLiveRegs;
LiveRegDefs[I->getReg()] = NULL;
LiveRegGens[I->getReg()] = NULL;
+ releaseInterferences(I->getReg());
}
}
--NumLiveRegs;
LiveRegDefs[CallResource] = NULL;
LiveRegGens[CallResource] = NULL;
+ releaseInterferences(CallResource);
}
}
SUnit *OldSU = Sequence.back();
while (true) {
Sequence.pop_back();
- if (SU->isSucc(OldSU))
- // Don't try to remove SU from AvailableQueue.
- SU->isAvailable = false;
// FIXME: use ready cycle instead of height
CurCycle = OldSU->getHeight();
UnscheduleNodeBottomUp(OldSU);
/// InsertCopiesAndMoveSuccs - Insert register copies and move all
/// scheduled successors of the given SUnit to the last copy.
void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
- const TargetRegisterClass *DestRC,
- const TargetRegisterClass *SrcRC,
- SmallVector<SUnit*, 2> &Copies) {
+ const TargetRegisterClass *DestRC,
+ const TargetRegisterClass *SrcRC,
+ SmallVectorImpl<SUnit*> &Copies) {
SUnit *CopyFromSU = CreateNewSUnit(NULL);
CopyFromSU->CopySrcRC = SrcRC;
CopyFromSU->CopyDstRC = DestRC;
static void CheckForLiveRegDef(SUnit *SU, unsigned Reg,
std::vector<SUnit*> &LiveRegDefs,
SmallSet<unsigned, 4> &RegAdded,
- SmallVector<unsigned, 4> &LRegs,
+ SmallVectorImpl<unsigned> &LRegs,
const TargetRegisterInfo *TRI) {
for (MCRegAliasIterator AliasI(Reg, TRI, true); AliasI.isValid(); ++AliasI) {
static void CheckForLiveRegDefMasked(SUnit *SU, const uint32_t *RegMask,
std::vector<SUnit*> &LiveRegDefs,
SmallSet<unsigned, 4> &RegAdded,
- SmallVector<unsigned, 4> &LRegs) {
+ SmallVectorImpl<unsigned> &LRegs) {
// Look at all live registers. Skip Reg0 and the special CallResource.
for (unsigned i = 1, e = LiveRegDefs.size()-1; i != e; ++i) {
if (!LiveRegDefs[i]) continue;
/// If the specific node is the last one that's available to schedule, do
/// whatever is necessary (i.e. backtracking or cloning) to make it possible.
bool ScheduleDAGRRList::
-DelayForLiveRegsBottomUp(SUnit *SU, SmallVector<unsigned, 4> &LRegs) {
+DelayForLiveRegsBottomUp(SUnit *SU, SmallVectorImpl<unsigned> &LRegs) {
if (NumLiveRegs == 0)
return false;
return !LRegs.empty();
}
+void ScheduleDAGRRList::releaseInterferences(unsigned Reg) {
+ // Add the nodes that aren't ready back onto the available list.
+ for (unsigned i = Interferences.size(); i > 0; --i) {
+ SUnit *SU = Interferences[i-1];
+ LRegsMapT::iterator LRegsPos = LRegsMap.find(SU);
+ if (Reg) {
+ SmallVectorImpl<unsigned> &LRegs = LRegsPos->second;
+ if (std::find(LRegs.begin(), LRegs.end(), Reg) == LRegs.end())
+ continue;
+ }
+ SU->isPending = false;
+ // The interfering node may no longer be available due to backtracking.
+ // Furthermore, it may have been made available again, in which case it is
+ // now already in the AvailableQueue.
+ if (SU->isAvailable && !SU->NodeQueueId) {
+ DEBUG(dbgs() << " Repushing SU #" << SU->NodeNum << '\n');
+ AvailableQueue->push(SU);
+ }
+ if (i < Interferences.size())
+ Interferences[i-1] = Interferences.back();
+ Interferences.pop_back();
+ LRegsMap.erase(LRegsPos);
+ }
+}
+
/// Return a node that can be scheduled in this cycle. Requirements:
/// (1) Ready: latency has been satisfied
/// (2) No Hazards: resources are available
/// (3) No Interferences: may unschedule to break register interferences.
SUnit *ScheduleDAGRRList::PickNodeToScheduleBottomUp() {
- SmallVector<SUnit*, 4> Interferences;
- DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap;
-
- SUnit *CurSU = AvailableQueue->pop();
+ SUnit *CurSU = AvailableQueue->empty() ? 0 : AvailableQueue->pop();
while (CurSU) {
SmallVector<unsigned, 4> LRegs;
if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
break;
- LRegsMap.insert(std::make_pair(CurSU, LRegs));
-
- CurSU->isPending = true; // This SU is not in AvailableQueue right now.
- Interferences.push_back(CurSU);
+ DEBUG(dbgs() << " Interfering reg " <<
+ (LRegs[0] == TRI->getNumRegs() ? "CallResource"
+ : TRI->getName(LRegs[0]))
+ << " SU #" << CurSU->NodeNum << '\n');
+ std::pair<LRegsMapT::iterator, bool> LRegsPair =
+ LRegsMap.insert(std::make_pair(CurSU, LRegs));
+ if (LRegsPair.second) {
+ CurSU->isPending = true; // This SU is not in AvailableQueue right now.
+ Interferences.push_back(CurSU);
+ }
+ else {
+ assert(CurSU->isPending && "Intereferences are pending");
+ // Update the interference with current live regs.
+ LRegsPair.first->second = LRegs;
+ }
CurSU = AvailableQueue->pop();
}
- if (CurSU) {
- // Add the nodes that aren't ready back onto the available list.
- for (unsigned i = 0, e = Interferences.size(); i != e; ++i) {
- Interferences[i]->isPending = false;
- assert(Interferences[i]->isAvailable && "must still be available");
- AvailableQueue->push(Interferences[i]);
- }
+ if (CurSU)
return CurSU;
- }
// All candidates are delayed due to live physical reg dependencies.
// Try backtracking, code duplication, or inserting cross class copies
// to resolve it.
for (unsigned i = 0, e = Interferences.size(); i != e; ++i) {
SUnit *TrySU = Interferences[i];
- SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU];
+ SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
// Try unscheduling up to the point where it's safe to schedule
// this node.
}
}
if (!WillCreateCycle(TrySU, BtSU)) {
+ // BacktrackBottomUp mutates Interferences!
BacktrackBottomUp(TrySU, BtSU);
// Force the current node to be scheduled before the node that
if (!BtSU->isPending)
AvailableQueue->remove(BtSU);
}
+ DEBUG(dbgs() << "ARTIFICIAL edge from SU(" << BtSU->NodeNum << ") to SU("
+ << TrySU->NodeNum << ")\n");
AddPred(TrySU, SDep(BtSU, SDep::Artificial));
// If one or more successors has been unscheduled, then the current
- // node is no longer avaialable. Schedule a successor that's now
- // available instead.
- if (!TrySU->isAvailable) {
+ // node is no longer available.
+ if (!TrySU->isAvailable)
CurSU = AvailableQueue->pop();
- }
else {
+ AvailableQueue->remove(TrySU);
CurSU = TrySU;
- TrySU->isPending = false;
- Interferences.erase(Interferences.begin()+i);
}
+ // Interferences has been mutated. We must break.
break;
}
}
// insert cross class copies.
// If it's not too expensive, i.e. cost != -1, issue copies.
SUnit *TrySU = Interferences[0];
- SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU];
+ SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
assert(LRegs.size() == 1 && "Can't handle this yet!");
unsigned Reg = LRegs[0];
SUnit *LRDef = LiveRegDefs[Reg];
TrySU->isAvailable = false;
CurSU = NewDef;
}
-
assert(CurSU && "Unable to resolve live physical register dependencies!");
-
- // Add the nodes that aren't ready back onto the available list.
- for (unsigned i = 0, e = Interferences.size(); i != e; ++i) {
- Interferences[i]->isPending = false;
- // May no longer be available due to backtracking.
- if (Interferences[i]->isAvailable) {
- AvailableQueue->push(Interferences[i]);
- }
- }
return CurSU;
}
// While Available queue is not empty, grab the node with the highest
// priority. If it is not ready put it back. Schedule the node.
Sequence.reserve(SUnits.size());
- while (!AvailableQueue->empty()) {
+ while (!AvailableQueue->empty() || !Interferences.empty()) {
DEBUG(dbgs() << "\nExamining Available:\n";
AvailableQueue->dump(this));
unsigned getNodeOrdering(const SUnit *SU) const {
if (!SU->getNode()) return 0;
- return scheduleDAG->DAG->GetOrdering(SU->getNode());
+ return SU->getNode()->getIROrder();
}
bool empty() const { return Queue.empty(); }
bool RHasPhysReg = right->hasPhysRegDefs;
if (LHasPhysReg != RHasPhysReg) {
#ifndef NDEBUG
- const char *const PhysRegMsg[] = {" has no physreg"," defines a physreg"};
+ static const char *const PhysRegMsg[] = { " has no physreg",
+ " defines a physreg" };
#endif
DEBUG(dbgs() << " SU (" << left->NodeNum << ") "
<< PhysRegMsg[LHasPhysReg] << " SU(" << right->NodeNum << ") "
const TargetMachine &TM = IS->TM;
const TargetInstrInfo *TII = TM.getInstrInfo();
const TargetRegisterInfo *TRI = TM.getRegisterInfo();
- const TargetLowering *TLI = &IS->getTargetLowering();
+ const TargetLowering *TLI = IS->getTargetLowering();
HybridBURRPriorityQueue *PQ =
new HybridBURRPriorityQueue(*IS->MF, true, false, TII, TRI, TLI);
const TargetMachine &TM = IS->TM;
const TargetInstrInfo *TII = TM.getInstrInfo();
const TargetRegisterInfo *TRI = TM.getRegisterInfo();
- const TargetLowering *TLI = &IS->getTargetLowering();
+ const TargetLowering *TLI = IS->getTargetLowering();
ILPBURRPriorityQueue *PQ =
new ILPBURRPriorityQueue(*IS->MF, true, false, TII, TRI, TLI);
projects / oota-llvm.git / blobdiff