short NumChainSuccsLeft; // # of chain succs not scheduled.
bool isTwoAddress : 1; // Is a two-address instruction.
bool isDefNUseOperand : 1; // Is a def&use operand.
+ bool isPending : 1; // True once pending.
bool isAvailable : 1; // True once available.
bool isScheduled : 1; // True once scheduled.
unsigned short Latency; // Node latency.
unsigned CycleBound; // Upper/lower cycle to be scheduled at.
+ unsigned Cycle; // Once scheduled, the cycle of the op.
unsigned NodeNum; // Entry # of node in the node vector.
SUnit(SDNode *node, unsigned nodenum)
: Node(node), NumPredsLeft(0), NumSuccsLeft(0),
NumChainPredsLeft(0), NumChainSuccsLeft(0),
isTwoAddress(false), isDefNUseOperand(false),
- isAvailable(false), isScheduled(false),
- Latency(0), CycleBound(0), NodeNum(nodenum) {}
+ isPending(false), isAvailable(false), isScheduled(false),
+ Latency(0), CycleBound(0), Cycle(0), NodeNum(nodenum) {}
void dump(const SelectionDAG *G) const;
void dumpAll(const SelectionDAG *G) const;
std::map<SDNode*, SUnit*> SUnitMap;
// The schedule. Null SUnit*'s represent noop instructions.
std::vector<SUnit*> Sequence;
- // Current scheduling cycle.
- unsigned CurrCycle;
// The scheduling units.
std::vector<SUnit> SUnits;
/// it is top-down.
bool isBottomUp;
- /// PriorityQueue - The priority queue to use.
- SchedulingPriorityQueue *PriorityQueue;
+ /// AvailableQueue - The priority queue to use for the available SUnits.
+ ///
+ SchedulingPriorityQueue *AvailableQueue;
+
+ /// PendingQueue - This contains all of the instructions whose operands have
+ /// been issued, but their results are not ready yet (due to the latency of
+ /// the operation). Once the operands becomes available, the instruction is
+ /// added to the AvailableQueue. This keeps track of each SUnit and the
+ /// number of cycles left to execute before the operation is available.
+ std::vector<std::pair<unsigned, SUnit*> > PendingQueue;
/// HazardRec - The hazard recognizer to use.
HazardRecognizer *HazardRec;
public:
ScheduleDAGList(SelectionDAG &dag, MachineBasicBlock *bb,
const TargetMachine &tm, bool isbottomup,
- SchedulingPriorityQueue *priorityqueue,
+ SchedulingPriorityQueue *availqueue,
HazardRecognizer *HR)
- : ScheduleDAG(dag, bb, tm),
- CurrCycle(0), isBottomUp(isbottomup),
- PriorityQueue(priorityqueue), HazardRec(HR) {
+ : ScheduleDAG(dag, bb, tm), isBottomUp(isbottomup),
+ AvailableQueue(availqueue), HazardRec(HR) {
}
~ScheduleDAGList() {
delete HazardRec;
- delete PriorityQueue;
+ delete AvailableQueue;
}
void Schedule();
private:
SUnit *NewSUnit(SDNode *N);
- void ReleasePred(SUnit *PredSU, bool isChain);
+ void ReleasePred(SUnit *PredSU, bool isChain, unsigned CurCycle);
void ReleaseSucc(SUnit *SuccSU, bool isChain);
- void ScheduleNodeBottomUp(SUnit *SU);
- void ScheduleNodeTopDown(SUnit *SU);
+ void ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle);
+ void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
void ListScheduleTopDown();
void ListScheduleBottomUp();
void BuildSchedUnits();
// Remove MainNode from FlaggedNodes again.
SU->FlaggedNodes.pop_back();
}
+
+ return;
DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
SUnits[su].dumpAll(&DAG));
}
}
/// Schedule - Schedule the DAG using list scheduling.
-/// FIXME: Right now it only supports the burr (bottom up register reducing)
-/// heuristic.
void ScheduleDAGList::Schedule() {
DEBUG(std::cerr << "********** List Scheduling **********\n");
// Build scheduling units.
BuildSchedUnits();
- PriorityQueue->initNodes(SUnits);
+ AvailableQueue->initNodes(SUnits);
// Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate.
if (isBottomUp)
else
ListScheduleTopDown();
- PriorityQueue->releaseState();
+ AvailableQueue->releaseState();
DEBUG(std::cerr << "*** Final schedule ***\n");
DEBUG(dumpSchedule());
/// 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) {
+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,CurrCycle + PredSU->Latency);
+ PredSU->CycleBound = std::max(PredSU->CycleBound, CurCycle + PredSU->Latency);
if (!isChain)
PredSU->NumSuccsLeft--;
// EntryToken has to go last! Special case it here.
if (PredSU->Node->getOpcode() != ISD::EntryToken) {
PredSU->isAvailable = true;
- PriorityQueue->push(PredSU);
+ AvailableQueue->push(PredSU);
}
}
}
/// 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) {
- DEBUG(std::cerr << "*** Scheduling: ");
+void ScheduleDAGList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) {
+ DEBUG(std::cerr << "*** Scheduling [" << CurCycle << "]: ");
DEBUG(SU->dump(&DAG));
+ SU->Cycle = CurCycle;
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);
+ ReleasePred(I->first, I->second, CurCycle);
+ // FIXME: This is something used by the priority function that it should
+ // calculate directly.
if (!I->second)
SU->NumPredsLeft--;
}
- CurrCycle++;
}
/// isReady - True if node's lower cycle bound is less or equal to the current
/// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
/// schedulers.
void ScheduleDAGList::ListScheduleBottomUp() {
+ unsigned CurrCycle = 0;
// Add root to Available queue.
- PriorityQueue->push(SUnitMap[DAG.getRoot().Val]);
+ 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;
- while (!PriorityQueue->empty()) {
- SUnit *CurrNode = PriorityQueue->pop();
+ while (!AvailableQueue->empty()) {
+ SUnit *CurrNode = AvailableQueue->pop();
while (!isReady(CurrNode, CurrCycle)) {
NotReady.push_back(CurrNode);
- CurrNode = PriorityQueue->pop();
+ CurrNode = AvailableQueue->pop();
}
// Add the nodes that aren't ready back onto the available list.
- PriorityQueue->push_all(NotReady);
+ AvailableQueue->push_all(NotReady);
NotReady.clear();
- ScheduleNodeBottomUp(CurrNode);
+ ScheduleNodeBottomUp(CurrNode, CurrCycle);
+ CurrCycle++;
CurrNode->isScheduled = true;
- PriorityQueue->ScheduledNode(CurrNode);
+ AvailableQueue->ScheduledNode(CurrNode);
}
// Add entry node last
//===----------------------------------------------------------------------===//
/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
-/// the Available queue is the count reaches zero. Also update its cycle bound.
+/// the PendingQueue if the count reaches zero.
void ScheduleDAGList::ReleaseSucc(SUnit *SuccSU, bool isChain) {
- // 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).
- SuccSU->CycleBound = std::max(SuccSU->CycleBound,CurrCycle + SuccSU->Latency);
-
if (!isChain)
SuccSU->NumPredsLeft--;
else
SuccSU->NumChainPredsLeft--;
-#ifndef NDEBUG
- if (SuccSU->NumPredsLeft < 0 || SuccSU->NumChainPredsLeft < 0) {
- std::cerr << "*** List scheduling failed! ***\n";
- SuccSU->dump(&DAG);
- std::cerr << " has been released too many times!\n";
- abort();
- }
-#endif
+ assert(SuccSU->NumPredsLeft >= 0 && SuccSU->NumChainPredsLeft >= 0 &&
+ "List scheduling internal error");
if ((SuccSU->NumPredsLeft + SuccSU->NumChainPredsLeft) == 0) {
- SuccSU->isAvailable = true;
- PriorityQueue->push(SuccSU);
+ // Compute how many cycles it will be before this actually becomes
+ // available. This is the max of the start time of all predecessors plus
+ // their latencies.
+ unsigned AvailableCycle = 0;
+ for (std::set<std::pair<SUnit*, bool> >::iterator I = SuccSU->Preds.begin(),
+ E = SuccSU->Preds.end(); I != E; ++I) {
+ // If this is a token edge, we don't need to wait for the latency of the
+ // preceeding instruction (e.g. a long-latency load) unless there is also
+ // some other data dependence.
+ unsigned PredDoneCycle = I->first->Cycle;
+ if (!I->second)
+ PredDoneCycle += I->first->Latency;
+ else if (I->first->Latency)
+ PredDoneCycle += 1;
+
+ AvailableCycle = std::max(AvailableCycle, PredDoneCycle);
+ }
+
+ PendingQueue.push_back(std::make_pair(AvailableCycle, SuccSU));
+ SuccSU->isPending = true;
}
}
/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
/// count of its successors. If a successor pending count is zero, add it to
/// the Available queue.
-void ScheduleDAGList::ScheduleNodeTopDown(SUnit *SU) {
- DEBUG(std::cerr << "*** Scheduling: ");
+void ScheduleDAGList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
+ DEBUG(std::cerr << "*** Scheduling [" << CurCycle << "]: ");
DEBUG(SU->dump(&DAG));
Sequence.push_back(SU);
+ SU->Cycle = CurCycle;
// Bottom up: release successors.
for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Succs.begin(),
- E = SU->Succs.end(); I != E; ++I) {
+ E = SU->Succs.end(); I != E; ++I)
ReleaseSucc(I->first, I->second);
- if (!I->second)
- SU->NumSuccsLeft--;
- }
- CurrCycle++;
}
/// ListScheduleTopDown - The main loop of list scheduling for top-down
/// schedulers.
void ScheduleDAGList::ListScheduleTopDown() {
- // Emit the entry node first.
+ unsigned CurCycle = 0;
SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
- ScheduleNodeTopDown(Entry);
- HazardRec->EmitInstruction(Entry->Node);
-
+
// All leaves to Available queue.
for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
// It is available if it has no predecessors.
- if (SUnits[i].Preds.size() == 0 && &SUnits[i] != Entry)
- PriorityQueue->push(&SUnits[i]);
+ if (SUnits[i].Preds.size() == 0 && &SUnits[i] != Entry) {
+ AvailableQueue->push(&SUnits[i]);
+ SUnits[i].isAvailable = SUnits[i].isPending = true;
+ }
}
+ // Emit the entry node first.
+ ScheduleNodeTopDown(Entry, CurCycle);
+ HazardRec->EmitInstruction(Entry->Node);
+
// 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;
- while (!PriorityQueue->empty()) {
- SUnit *FoundNode = 0;
+ while (!AvailableQueue->empty() || !PendingQueue.empty()) {
+ // Check to see if any of the pending instructions are ready to issue. If
+ // so, add them to the available queue.
+ for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
+ if (PendingQueue[i].first == CurCycle) {
+ AvailableQueue->push(PendingQueue[i].second);
+ PendingQueue[i].second->isAvailable = true;
+ PendingQueue[i] = PendingQueue.back();
+ PendingQueue.pop_back();
+ --i; --e;
+ } else {
+ assert(PendingQueue[i].first > CurCycle && "Negative latency?");
+ }
+ }
+
+ // If there are no instructions available, don't try to issue anything, and
+ // don't advance the hazard recognizer.
+ if (AvailableQueue->empty()) {
+ ++CurCycle;
+ continue;
+ }
+ SUnit *FoundSUnit = 0;
+ SDNode *FoundNode = 0;
+
bool HasNoopHazards = false;
- do {
- SUnit *CurNode = PriorityQueue->pop();
+ while (!AvailableQueue->empty()) {
+ SUnit *CurSUnit = AvailableQueue->pop();
// Get the node represented by this SUnit.
- SDNode *N = CurNode->Node;
+ FoundNode = CurSUnit->Node;
+
// If this is a pseudo op, like copyfromreg, look to see if there is a
// real target node flagged to it. If so, use the target node.
- for (unsigned i = 0, e = CurNode->FlaggedNodes.size();
- N->getOpcode() < ISD::BUILTIN_OP_END && i != e; ++i)
- N = CurNode->FlaggedNodes[i];
+ for (unsigned i = 0, e = CurSUnit->FlaggedNodes.size();
+ FoundNode->getOpcode() < ISD::BUILTIN_OP_END && i != e; ++i)
+ FoundNode = CurSUnit->FlaggedNodes[i];
- HazardRecognizer::HazardType HT = HazardRec->getHazardType(N);
+ HazardRecognizer::HazardType HT = HazardRec->getHazardType(FoundNode);
if (HT == HazardRecognizer::NoHazard) {
- FoundNode = CurNode;
+ FoundSUnit = CurSUnit;
break;
}
// Remember if this is a noop hazard.
HasNoopHazards |= HT == HazardRecognizer::NoopHazard;
- NotReady.push_back(CurNode);
- } while (!PriorityQueue->empty());
+ NotReady.push_back(CurSUnit);
+ }
// Add the nodes that aren't ready back onto the available list.
- PriorityQueue->push_all(NotReady);
- NotReady.clear();
+ if (!NotReady.empty()) {
+ AvailableQueue->push_all(NotReady);
+ NotReady.clear();
+ }
// If we found a node to schedule, do it now.
- if (FoundNode) {
- ScheduleNodeTopDown(FoundNode);
- HazardRec->EmitInstruction(FoundNode->Node);
- FoundNode->isScheduled = true;
- PriorityQueue->ScheduledNode(FoundNode);
+ if (FoundSUnit) {
+ ScheduleNodeTopDown(FoundSUnit, CurCycle);
+ HazardRec->EmitInstruction(FoundNode);
+ FoundSUnit->isScheduled = true;
+ AvailableQueue->ScheduledNode(FoundSUnit);
+
+ // If this is a pseudo-op node, we don't want to increment the current
+ // cycle.
+ if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops!
+ ++CurCycle;
} else if (!HasNoopHazards) {
// Otherwise, we have a pipeline stall, but no other problem, just advance
// the current cycle and try again.
DEBUG(std::cerr << "*** Advancing cycle, no work to do\n");
HazardRec->AdvanceCycle();
++NumStalls;
+ ++CurCycle;
} else {
// Otherwise, we have no instructions to issue and we have instructions
// that will fault if we don't do this right. This is the case for
HazardRec->EmitNoop();
Sequence.push_back(0); // NULL SUnit* -> noop
++NumNoops;
+ ++CurCycle;
}
}
/// scheduled will make this node available, so it is better than some other
/// node of the same priority that will not make a node available.
void LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) {
- if (SU->isAvailable) return; // All preds scheduled.
+ if (SU->isPending) return; // All preds scheduled.
SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU);
if (OnlyAvailablePred == 0 || !OnlyAvailablePred->isAvailable) return;
projects / oota-llvm.git / blobdiff