-//===----------------------------------------------------------------------===//
-// Bottom-Up Scheduling
-//===----------------------------------------------------------------------===//
-
-static const TargetRegisterClass *getRegClass(SUnit *SU,
- const TargetInstrInfo *TII,
- const MRegisterInfo *MRI,
- SSARegMap *RegMap) {
- if (SU->Node->isTargetOpcode()) {
- unsigned Opc = SU->Node->getTargetOpcode();
- const TargetInstrDescriptor &II = TII->get(Opc);
- return II.OpInfo->RegClass;
- } else {
- assert(SU->Node->getOpcode() == ISD::CopyFromReg);
- unsigned SrcReg = cast<RegisterSDNode>(SU->Node->getOperand(1))->getReg();
- if (MRegisterInfo::isVirtualRegister(SrcReg))
- return RegMap->getRegClass(SrcReg);
- else {
- for (MRegisterInfo::regclass_iterator I = MRI->regclass_begin(),
- E = MRI->regclass_end(); I != E; ++I)
- if ((*I)->hasType(SU->Node->getValueType(0)) &&
- (*I)->contains(SrcReg))
- return *I;
- assert(false && "Couldn't find register class for reg copy!");
- }
- return NULL;
- }
-}
-
-static unsigned getNumResults(SUnit *SU) {
- unsigned NumResults = 0;
- for (unsigned i = 0, e = SU->Node->getNumValues(); i != e; ++i) {
- MVT::ValueType VT = SU->Node->getValueType(i);
- if (VT != MVT::Other && VT != MVT::Flag)
- NumResults++;
- }
- return NumResults;
-}
-
-/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
-/// the Available queue is the count reaches zero. Also update its cycle bound.
-void ScheduleDAGList::ReleasePred(SUnit *PredSU, bool isChain,
- unsigned CurCycle) {
- // FIXME: the distance between two nodes is not always == the predecessor's
- // latency. For example, the reader can very well read the register written
- // by the predecessor later than the issue cycle. It also depends on the
- // interrupt model (drain vs. freeze).
- PredSU->CycleBound = std::max(PredSU->CycleBound, CurCycle + PredSU->Latency);
-
- if (!isChain)
- PredSU->NumSuccsLeft--;
- else
- PredSU->NumChainSuccsLeft--;
-
-#ifndef NDEBUG
- if (PredSU->NumSuccsLeft < 0 || PredSU->NumChainSuccsLeft < 0) {
- std::cerr << "*** List scheduling failed! ***\n";
- PredSU->dump(&DAG);
- std::cerr << " has been released too many times!\n";
- assert(0);
- }
-#endif
-
- if ((PredSU->NumSuccsLeft + PredSU->NumChainSuccsLeft) == 0) {
- // EntryToken has to go last! Special case it here.
- if (PredSU->Node->getOpcode() != ISD::EntryToken) {
- PredSU->isAvailable = true;
- AvailableQueue->push(PredSU);
- }
- }
-
- if (getNumResults(PredSU) > 0) {
- const TargetRegisterClass *RegClass = getRegClass(PredSU, TII, MRI, RegMap);
- OpenNodes[RegClass].insert(PredSU);
- }
-}
-
-/// SharesOperandWithTwoAddr - Check if there is a unscheduled two-address node
-/// with which SU shares an operand. If so, returns the node.
-static SUnit *SharesOperandWithTwoAddr(SUnit *SU) {
- assert(!SU->isTwoAddress && "Node cannot be two-address op");
- for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
- E = SU->Preds.end(); I != E; ++I) {
- if (I->second) continue;
- SUnit *PredSU = I->first;
- for (std::set<std::pair<SUnit*, bool> >::iterator II =
- PredSU->Succs.begin(), EE = PredSU->Succs.end(); II != EE; ++II) {
- if (II->second) continue;
- SUnit *SSU = II->first;
- if (SSU->isTwoAddress && !SSU->isScheduled) {
- return SSU;
- }
- }
- }
- return NULL;
-}
-
-static bool isFloater(const SUnit *SU) {
- unsigned Opc = SU->Node->getOpcode();
- return (Opc != ISD::CopyFromReg && SU->NumPredsLeft == 0);
-}
-
-static bool isSimpleFloaterUse(const SUnit *SU) {
- unsigned NumOps = 0;
- for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
- E = SU->Preds.end(); I != E; ++I) {
- if (I->second) continue;
- if (++NumOps > 1)
- return false;
- if (!isFloater(I->first))
- return false;
- }
- return true;
-}
-
-/// ScheduleVertically - Schedule vertically. That is, follow up the D&U chain
-/// (of two-address code) and schedule floaters aggressively.
-void ScheduleDAGList::ScheduleVertically(SUnit *SU, unsigned& CurCycle) {
- // Try scheduling Def&Use operand if register pressure is low.
- const TargetRegisterClass *RegClass = getRegClass(SU, TII, MRI, RegMap);
- unsigned Pressure = OpenNodes[RegClass].size();
- unsigned Limit = RegPressureLimits[RegClass];
-
- // See if we can schedule any predecessor that takes no registers.
- for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
- E = SU->Preds.end(); I != E; ++I) {
- if (I->second) continue;
-
- SUnit *PredSU = I->first;
- if (!PredSU->isAvailable || PredSU->isScheduled)
- continue;
-
- if (isFloater(PredSU)) {
- DEBUG(std::cerr<<"*** Scheduling floater\n");
- AvailableQueue->RemoveFromPriorityQueue(PredSU);
- ScheduleNodeBottomUp(PredSU, CurCycle, false);
- }
- }
-
- SUnit *DUSU = NULL;
- if (SU->isTwoAddress && Pressure < Limit) {
- DUSU = SUnitMap[SU->Node->getOperand(0).Val];
- if (!DUSU->isAvailable || DUSU->isScheduled)
- DUSU = NULL;
- else if (!DUSU->isTwoAddress) {
- SUnit *SSU = SharesOperandWithTwoAddr(DUSU);
- if (SSU && SSU->isAvailable) {
- AvailableQueue->RemoveFromPriorityQueue(SSU);
- ScheduleNodeBottomUp(SSU, CurCycle, false);
- Pressure = OpenNodes[RegClass].size();
- if (Pressure >= Limit)
- DUSU = NULL;
- }
- }
- }
-
- if (DUSU) {
- DEBUG(std::cerr<<"*** Low register pressure: scheduling D&U operand\n");
- AvailableQueue->RemoveFromPriorityQueue(DUSU);
- ScheduleNodeBottomUp(DUSU, CurCycle, false);
- Pressure = OpenNodes[RegClass].size();
- ScheduleVertically(DUSU, CurCycle);
- }
-}
-
-/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
-/// count of its predecessors. If a predecessor pending count is zero, add it to
-/// the Available queue.
-void ScheduleDAGList::ScheduleNodeBottomUp(SUnit *SU, unsigned& CurCycle,
- bool Vertical) {
- DEBUG(std::cerr << "*** Scheduling [" << CurCycle << "]: ");
- DEBUG(SU->dump(&DAG));
- SU->Cycle = CurCycle;
-
- AvailableQueue->ScheduledNode(SU);
- Sequence.push_back(SU);
-
- // Bottom up: release predecessors
- for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
- E = SU->Preds.end(); I != E; ++I)
- ReleasePred(I->first, I->second, CurCycle);
- SU->isScheduled = true;
- CurCycle++;
-
- if (getNumResults(SU) != 0) {
- const TargetRegisterClass *RegClass = getRegClass(SU, TII, MRI, RegMap);
- OpenNodes[RegClass].erase(SU);
-
- if (SchedVertically && Vertical)
- ScheduleVertically(SU, CurCycle);
- }
-}
-
-/// isReady - True if node's lower cycle bound is less or equal to the current
-/// scheduling cycle. Always true if all nodes have uniform latency 1.
-static inline bool isReady(SUnit *SU, unsigned CurCycle) {
- return SU->CycleBound <= CurCycle;
-}
-
-/// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
-/// schedulers.
-void ScheduleDAGList::ListScheduleBottomUp() {
- // Determine rough register pressure limit.
- for (MRegisterInfo::regclass_iterator RCI = MRI->regclass_begin(),
- E = MRI->regclass_end(); RCI != E; ++RCI) {
- const TargetRegisterClass *RC = *RCI;
- unsigned Limit = RC->getNumRegs();
- Limit = (Limit > 2) ? Limit - 2 : 0;
- std::map<const TargetRegisterClass*, unsigned>::iterator RPI =
- RegPressureLimits.find(RC);
- if (RPI == RegPressureLimits.end())
- RegPressureLimits[RC] = Limit;
- else {
- unsigned &OldLimit = RegPressureLimits[RC];
- if (Limit < OldLimit)
- OldLimit = Limit;
- }
- }
-
- unsigned CurCycle = 0;
- // Add root to Available queue.
- AvailableQueue->push(SUnitMap[DAG.getRoot().Val]);
-
- // While Available queue is not empty, grab the node with the highest
- // priority. If it is not ready put it back. Schedule the node.
- std::vector<SUnit*> NotReady;
- SUnit *CurNode = NULL;
- while (!AvailableQueue->empty()) {
- SUnit *CurNode = AvailableQueue->pop();
- while (!isReady(CurNode, CurCycle)) {
- NotReady.push_back(CurNode);
- CurNode = AvailableQueue->pop();
- }
-
- // Add the nodes that aren't ready back onto the available list.
- AvailableQueue->push_all(NotReady);
- NotReady.clear();
-
- ScheduleNodeBottomUp(CurNode, CurCycle);
- }
-
- // Add entry node last
- if (DAG.getEntryNode().Val != DAG.getRoot().Val) {
- SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
- Sequence.push_back(Entry);
- }
-
- // Reverse the order if it is bottom up.
- std::reverse(Sequence.begin(), Sequence.end());
-
-
-#ifndef NDEBUG
- // Verify that all SUnits were scheduled.
- bool AnyNotSched = false;
- for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
- if (SUnits[i].NumSuccsLeft != 0 || SUnits[i].NumChainSuccsLeft != 0) {
- if (!AnyNotSched)
- std::cerr << "*** List scheduling failed! ***\n";
- SUnits[i].dump(&DAG);
- std::cerr << "has not been scheduled!\n";
- AnyNotSched = true;
- }
- }
- assert(!AnyNotSched);
-#endif
-}
-