LatencyPriorityQueue.cpp [plain text]
#define DEBUG_TYPE "scheduler"
#include "llvm/CodeGen/LatencyPriorityQueue.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
bool latency_sort::operator()(const SUnit *LHS, const SUnit *RHS) const {
if (LHS->isScheduleHigh && !RHS->isScheduleHigh)
return false;
if (!LHS->isScheduleHigh && RHS->isScheduleHigh)
return true;
unsigned LHSNum = LHS->NodeNum;
unsigned RHSNum = RHS->NodeNum;
unsigned LHSLatency = PQ->getLatency(LHSNum);
unsigned RHSLatency = PQ->getLatency(RHSNum);
if (LHSLatency < RHSLatency) return true;
if (LHSLatency > RHSLatency) return false;
unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum);
unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum);
if (LHSBlocked < RHSBlocked) return true;
if (LHSBlocked > RHSBlocked) return false;
return LHSNum < RHSNum;
}
SUnit *LatencyPriorityQueue::getSingleUnscheduledPred(SUnit *SU) {
SUnit *OnlyAvailablePred = 0;
for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
SUnit &Pred = *I->getSUnit();
if (!Pred.isScheduled) {
if (OnlyAvailablePred && OnlyAvailablePred != &Pred)
return 0;
OnlyAvailablePred = &Pred;
}
}
return OnlyAvailablePred;
}
void LatencyPriorityQueue::push(SUnit *SU) {
unsigned NumNodesBlocking = 0;
for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
if (getSingleUnscheduledPred(I->getSUnit()) == SU)
++NumNodesBlocking;
}
NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking;
Queue.push_back(SU);
}
void LatencyPriorityQueue::ScheduledNode(SUnit *SU) {
for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
AdjustPriorityOfUnscheduledPreds(I->getSUnit());
}
}
void LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) {
if (SU->isAvailable) return;
SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU);
if (OnlyAvailablePred == 0 || !OnlyAvailablePred->isAvailable) return;
remove(OnlyAvailablePred);
push(OnlyAvailablePred);
}
SUnit *LatencyPriorityQueue::pop() {
if (empty()) return NULL;
std::vector<SUnit *>::iterator Best = Queue.begin();
for (std::vector<SUnit *>::iterator I = llvm::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();
return V;
}
void LatencyPriorityQueue::remove(SUnit *SU) {
assert(!Queue.empty() && "Queue is empty!");
std::vector<SUnit *>::iterator I = std::find(Queue.begin(), Queue.end(), SU);
if (I != prior(Queue.end()))
std::swap(*I, Queue.back());
Queue.pop_back();
}
#ifdef NDEBUG
void LatencyPriorityQueue::dump(ScheduleDAG *DAG) const {}
#else
void LatencyPriorityQueue::dump(ScheduleDAG *DAG) const {
LatencyPriorityQueue q = *this;
while (!q.empty()) {
SUnit *su = q.pop();
dbgs() << "Height " << su->getHeight() << ": ";
su->dump(DAG);
}
}
#endif