From 1e3dec662ea18131c495db50caccc57f77b7a5fe Mon Sep 17 00:00:00 2001 From: rdivacky Date: Thu, 27 May 2010 15:15:58 +0000 Subject: Update LLVM to r104832. --- lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp | 147 ++++++++++++++++++------- 1 file changed, 110 insertions(+), 37 deletions(-) (limited to 'lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp') diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp index da02850..820ba66 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp @@ -24,7 +24,6 @@ #include "llvm/Target/TargetData.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetInstrInfo.h" -#include "llvm/ADT/PriorityQueue.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/STLExtras.h" @@ -53,6 +52,12 @@ static RegisterScheduler "order when possible", createSourceListDAGScheduler); +static RegisterScheduler + hybridListDAGScheduler("list-hybrid", + "Bottom-up rr list scheduling which avoid stalls for " + "long latency instructions", + createHybridListDAGScheduler); + namespace { //===----------------------------------------------------------------------===// /// ScheduleDAGRRList - The actual register reduction list scheduler @@ -64,6 +69,10 @@ private: /// it is top-down. bool isBottomUp; + /// NeedLatency - True if the scheduler will make use of latency information. + /// + bool NeedLatency; + /// AvailableQueue - The priority queue to use for the available SUnits. SchedulingPriorityQueue *AvailableQueue; @@ -80,9 +89,9 @@ private: public: ScheduleDAGRRList(MachineFunction &mf, - bool isbottomup, + bool isbottomup, bool needlatency, SchedulingPriorityQueue *availqueue) - : ScheduleDAGSDNodes(mf), isBottomUp(isbottomup), + : ScheduleDAGSDNodes(mf), isBottomUp(isbottomup), NeedLatency(needlatency), AvailableQueue(availqueue), Topo(SUnits) { } @@ -161,9 +170,11 @@ private: return NewNode; } - /// ForceUnitLatencies - Return true, since register-pressure-reducing - /// scheduling doesn't need actual latency information. - bool ForceUnitLatencies() const { return true; } + /// ForceUnitLatencies - Register-pressure-reducing scheduling doesn't + /// need actual latency information but the hybrid scheduler does. + bool ForceUnitLatencies() const { + return !NeedLatency; + } }; } // end anonymous namespace @@ -213,6 +224,12 @@ void ScheduleDAGRRList::ReleasePred(SUnit *SU, const SDep *PredEdge) { #endif --PredSU->NumSuccsLeft; + if (!ForceUnitLatencies()) { + // Updating predecessor's height. This is now the cycle when the + // predecessor can be scheduled without causing a pipeline stall. + PredSU->setHeightToAtLeast(SU->getHeight() + PredEdge->getLatency()); + } + // If all the node's successors are scheduled, this node is ready // to be scheduled. Ignore the special EntrySU node. if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) { @@ -244,10 +261,15 @@ void ScheduleDAGRRList::ReleasePredecessors(SUnit *SU, unsigned CurCycle) { /// count of its predecessors. If a predecessor pending count is zero, add it to /// the Available queue. void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { - DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); + DEBUG(dbgs() << "\n*** Scheduling [" << CurCycle << "]: "); DEBUG(SU->dump(this)); - assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!"); +#ifndef NDEBUG + if (CurCycle < SU->getHeight()) + DEBUG(dbgs() << " Height [" << SU->getHeight() << "] pipeline stall!\n"); +#endif + + // FIXME: Handle noop hazard. SU->setHeightToAtLeast(CurCycle); Sequence.push_back(SU); @@ -339,6 +361,7 @@ void ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, unsigned BtCycle, SU->isAvailable = false; UnscheduleNodeBottomUp(OldSU); --CurCycle; + AvailableQueue->setCurCycle(CurCycle); } assert(!SU->isSucc(OldSU) && "Something is wrong!"); @@ -386,7 +409,7 @@ SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) { if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes)) return NULL; - DEBUG(dbgs() << "Unfolding SU # " << SU->NodeNum << "\n"); + DEBUG(dbgs() << "Unfolding SU #" << SU->NodeNum << "\n"); assert(NewNodes.size() == 2 && "Expected a load folding node!"); N = NewNodes[1]; @@ -504,7 +527,7 @@ SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) { SU = NewSU; } - DEBUG(dbgs() << "Duplicating SU # " << SU->NodeNum << "\n"); + DEBUG(dbgs() << " Duplicating SU #" << SU->NodeNum << "\n"); NewSU = CreateClone(SU); // New SUnit has the exact same predecessors. @@ -786,7 +809,7 @@ void ScheduleDAGRRList::ListScheduleBottomUp() { // Issue copies, these can be expensive cross register class copies. SmallVector Copies; InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies); - DEBUG(dbgs() << "Adding an edge from SU #" << TrySU->NodeNum + DEBUG(dbgs() << " Adding an edge from SU #" << TrySU->NodeNum << " to SU #" << Copies.front()->NodeNum << "\n"); AddPred(TrySU, SDep(Copies.front(), SDep::Order, /*Latency=*/1, /*Reg=*/0, /*isNormalMemory=*/false, @@ -795,7 +818,7 @@ void ScheduleDAGRRList::ListScheduleBottomUp() { NewDef = Copies.back(); } - DEBUG(dbgs() << "Adding an edge from SU #" << NewDef->NodeNum + DEBUG(dbgs() << " Adding an edge from SU #" << NewDef->NodeNum << " to SU #" << TrySU->NodeNum << "\n"); LiveRegDefs[Reg] = NewDef; AddPred(NewDef, SDep(TrySU, SDep::Order, /*Latency=*/1, @@ -821,6 +844,7 @@ void ScheduleDAGRRList::ListScheduleBottomUp() { if (CurSU) ScheduleNodeBottomUp(CurSU, CurCycle); ++CurCycle; + AvailableQueue->setCurCycle(CurCycle); } // Reverse the order if it is bottom up. @@ -889,6 +913,7 @@ void ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { /// schedulers. void ScheduleDAGRRList::ListScheduleTopDown() { unsigned CurCycle = 0; + AvailableQueue->setCurCycle(CurCycle); // Release any successors of the special Entry node. ReleaseSuccessors(&EntrySU); @@ -911,6 +936,7 @@ void ScheduleDAGRRList::ListScheduleTopDown() { if (CurSU) ScheduleNodeTopDown(CurSU, CurCycle); ++CurCycle; + AvailableQueue->setCurCycle(CurCycle); } #ifndef NDEBUG @@ -956,6 +982,16 @@ namespace { bool operator()(const SUnit* left, const SUnit* right) const; }; + + struct hybrid_ls_rr_sort : public std::binary_function { + RegReductionPriorityQueue *SPQ; + hybrid_ls_rr_sort(RegReductionPriorityQueue *spq) + : SPQ(spq) {} + hybrid_ls_rr_sort(const hybrid_ls_rr_sort &RHS) + : SPQ(RHS.SPQ) {} + + bool operator()(const SUnit* left, const SUnit* right) const; + }; } // end anonymous namespace /// CalcNodeSethiUllmanNumber - Compute Sethi Ullman number. @@ -990,8 +1026,9 @@ CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector &SUNumbers) { namespace { template class RegReductionPriorityQueue : public SchedulingPriorityQueue { - PriorityQueue, SF> Queue; - unsigned currentQueueId; + std::vector Queue; + SF Picker; + unsigned CurQueueId; protected: // SUnits - The SUnits for the current graph. @@ -1007,7 +1044,7 @@ namespace { public: RegReductionPriorityQueue(const TargetInstrInfo *tii, const TargetRegisterInfo *tri) - : Queue(SF(this)), currentQueueId(0), + : Picker(this), CurQueueId(0), TII(tii), TRI(tri), scheduleDAG(NULL) {} void initNodes(std::vector &sunits) { @@ -1067,26 +1104,26 @@ namespace { unsigned getNodeOrdering(const SUnit *SU) const { return scheduleDAG->DAG->GetOrdering(SU->getNode()); } - - unsigned size() const { return Queue.size(); } bool empty() const { return Queue.empty(); } void push(SUnit *U) { assert(!U->NodeQueueId && "Node in the queue already"); - U->NodeQueueId = ++currentQueueId; - Queue.push(U); + U->NodeQueueId = ++CurQueueId; + Queue.push_back(U); } - void push_all(const std::vector &Nodes) { - for (unsigned i = 0, e = Nodes.size(); i != e; ++i) - push(Nodes[i]); - } - SUnit *pop() { if (empty()) return NULL; - SUnit *V = Queue.top(); - Queue.pop(); + std::vector::iterator Best = Queue.begin(); + for (std::vector::iterator I = next(Queue.begin()), + E = Queue.end(); I != E; ++I) + if (Picker(*Best, *I)) + Best = I; + SUnit *V = *Best; + if (Best != prior(Queue.end())) + std::swap(*Best, Queue.back()); + Queue.pop_back(); V->NodeQueueId = 0; return V; } @@ -1094,7 +1131,11 @@ namespace { void remove(SUnit *SU) { assert(!Queue.empty() && "Queue is empty!"); assert(SU->NodeQueueId != 0 && "Not in queue!"); - Queue.erase_one(SU); + std::vector::iterator I = std::find(Queue.begin(), Queue.end(), + SU); + if (I != prior(Queue.end())) + std::swap(*I, Queue.back()); + Queue.pop_back(); SU->NodeQueueId = 0; } @@ -1117,6 +1158,9 @@ namespace { typedef RegReductionPriorityQueue SrcRegReductionPriorityQueue; + + typedef RegReductionPriorityQueue + HybridBURRPriorityQueue; } /// closestSucc - Returns the scheduled cycle of the successor which is @@ -1203,7 +1247,7 @@ bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { } // Source order, otherwise bottom up. -bool src_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const{ +bool src_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { unsigned LOrder = SPQ->getNodeOrdering(left); unsigned ROrder = SPQ->getNodeOrdering(right); @@ -1215,6 +1259,25 @@ bool src_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const{ return BURRSort(left, right, SPQ); } +bool hybrid_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const{ + bool LStall = left->SchedulingPref == Sched::Latency && + SPQ->getCurCycle() < left->getHeight(); + bool RStall = right->SchedulingPref == Sched::Latency && + SPQ->getCurCycle() < right->getHeight(); + // If scheduling one of the node will cause a pipeline stall, delay it. + // If scheduling either one of the node will cause a pipeline stall, sort them + // according to their height. + // If neither will cause a pipeline stall, try to reduce register pressure. + if (LStall) { + if (!RStall) + return true; + if (left->getHeight() != right->getHeight()) + return left->getHeight() > right->getHeight(); + } else if (RStall) + return false; + return BURRSort(left, right, SPQ); +} + template bool RegReductionPriorityQueue::canClobber(const SUnit *SU, const SUnit *Op) { @@ -1379,8 +1442,8 @@ void RegReductionPriorityQueue::PrescheduleNodesWithMultipleUses() { // Ok, the transformation is safe and the heuristics suggest it is // profitable. Update the graph. - DEBUG(dbgs() << "Prescheduling SU # " << SU->NodeNum - << " next to PredSU # " << PredSU->NodeNum + DEBUG(dbgs() << " Prescheduling SU #" << SU->NodeNum + << " next to PredSU #" << PredSU->NodeNum << " to guide scheduling in the presence of multiple uses\n"); for (unsigned i = 0; i != PredSU->Succs.size(); ++i) { SDep Edge = PredSU->Succs[i]; @@ -1469,7 +1532,7 @@ void RegReductionPriorityQueue::AddPseudoTwoAddrDeps() { (hasCopyToRegUse(SU) && !hasCopyToRegUse(SuccSU)) || (!SU->isCommutable && SuccSU->isCommutable)) && !scheduleDAG->IsReachable(SuccSU, SU)) { - DEBUG(dbgs() << "Adding a pseudo-two-addr edge from SU # " + DEBUG(dbgs() << " Adding a pseudo-two-addr edge from SU #" << SU->NodeNum << " to SU #" << SuccSU->NodeNum << "\n"); scheduleDAG->AddPred(SU, SDep(SuccSU, SDep::Order, /*Latency=*/0, /*Reg=*/0, /*isNormalMemory=*/false, @@ -1563,8 +1626,7 @@ llvm::createBURRListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) { BURegReductionPriorityQueue *PQ = new BURegReductionPriorityQueue(TII, TRI); - ScheduleDAGRRList *SD = - new ScheduleDAGRRList(*IS->MF, true, PQ); + ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, true, false, PQ); PQ->setScheduleDAG(SD); return SD; } @@ -1577,8 +1639,7 @@ llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) { TDRegReductionPriorityQueue *PQ = new TDRegReductionPriorityQueue(TII, TRI); - ScheduleDAGRRList *SD = - new ScheduleDAGRRList(*IS->MF, false, PQ); + ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, false, false, PQ); PQ->setScheduleDAG(SD); return SD; } @@ -1591,8 +1652,20 @@ llvm::createSourceListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) { SrcRegReductionPriorityQueue *PQ = new SrcRegReductionPriorityQueue(TII, TRI); - ScheduleDAGRRList *SD = - new ScheduleDAGRRList(*IS->MF, true, PQ); + ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, true, false, PQ); + PQ->setScheduleDAG(SD); + return SD; +} + +llvm::ScheduleDAGSDNodes * +llvm::createHybridListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) { + const TargetMachine &TM = IS->TM; + const TargetInstrInfo *TII = TM.getInstrInfo(); + const TargetRegisterInfo *TRI = TM.getRegisterInfo(); + + HybridBURRPriorityQueue *PQ = new HybridBURRPriorityQueue(TII, TRI); + + ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, true, true, PQ); PQ->setScheduleDAG(SD); return SD; } -- cgit v1.1