//
// The LLVM Compiler Infrastructure
//
-// This file was developed by Evan Cheng and is distributed under the
-// University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/CodeGen/SchedulerRegistry.h"
#include "llvm/CodeGen/SelectionDAGISel.h"
-#include "llvm/CodeGen/SSARegMap.h"
-#include "llvm/Target/MRegisterInfo.h"
+#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Compiler.h"
+#include "llvm/ADT/PriorityQueue.h"
#include "llvm/ADT/Statistic.h"
#include <climits>
-#include <queue>
using namespace llvm;
STATISTIC(NumNoops , "Number of noops inserted");
// Build scheduling units.
BuildSchedUnits();
- AvailableQueue->initNodes(SUnitMap, SUnits);
+ AvailableQueue->initNodes(SUnits);
ListScheduleTopDown();
AvailableQueue->releaseState();
-
- DOUT << "*** Final schedule ***\n";
- DEBUG(dumpSchedule());
- DOUT << "\n";
-
- // Emit in scheduled order
- EmitSchedule();
}
//===----------------------------------------------------------------------===//
/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
/// the PendingQueue if the count reaches zero.
void ScheduleDAGList::ReleaseSucc(SUnit *SuccSU, bool isChain) {
- if (!isChain)
- SuccSU->NumPredsLeft--;
- else
- SuccSU->NumChainPredsLeft--;
+ SuccSU->NumPredsLeft--;
- assert(SuccSU->NumPredsLeft >= 0 && SuccSU->NumChainPredsLeft >= 0 &&
+ assert(SuccSU->NumPredsLeft >= 0 &&
"List scheduling internal error");
- if ((SuccSU->NumPredsLeft + SuccSU->NumChainPredsLeft) == 0) {
+ if (SuccSU->NumPredsLeft == 0) {
// 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.
// 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.
- SUnit &Pred = *I->first;
+ SUnit &Pred = *I->Dep;
unsigned PredDoneCycle = Pred.Cycle;
- if (!I->second)
+ if (!I->isCtrl)
PredDoneCycle += Pred.Latency;
else if (Pred.Latency)
PredDoneCycle += 1;
// Bottom up: release successors.
for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I)
- ReleaseSucc(I->first, I->second);
+ ReleaseSucc(I->Dep, I->isCtrl);
}
/// ListScheduleTopDown - The main loop of list scheduling for top-down
/// schedulers.
void ScheduleDAGList::ListScheduleTopDown() {
unsigned CurCycle = 0;
- SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
// 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) {
+ if (SUnits[i].Preds.empty()) {
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;
+ Sequence.reserve(SUnits.size());
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.
// 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 = CurSUnit->FlaggedNodes.size();
- FoundNode->getOpcode() < ISD::BUILTIN_OP_END && i != e; ++i)
+ !FoundNode->isMachineOpcode() && i != e; ++i)
FoundNode = CurSUnit->FlaggedNodes[i];
HazardRecognizer::HazardType HT = HazardRec->getHazardType(FoundNode);
// Verify that all SUnits were scheduled.
bool AnyNotSched = false;
for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
- if (SUnits[i].NumPredsLeft != 0 || SUnits[i].NumChainPredsLeft != 0) {
+ if (SUnits[i].NumPredsLeft != 0) {
if (!AnyNotSched)
cerr << "*** List scheduling failed! ***\n";
SUnits[i].dump(&DAG);
/// mobility.
std::vector<unsigned> NumNodesSolelyBlocking;
- std::priority_queue<SUnit*, std::vector<SUnit*>, latency_sort> Queue;
+ PriorityQueue<SUnit*, std::vector<SUnit*>, latency_sort> Queue;
public:
LatencyPriorityQueue() : Queue(latency_sort(this)) {
}
- void initNodes(DenseMap<SDNode*, SUnit*> &sumap,
- std::vector<SUnit> &sunits) {
+ void initNodes(std::vector<SUnit> &sunits) {
SUnits = &sunits;
// Calculate node priorities.
CalculatePriorities();
}
+
+ void addNode(const SUnit *SU) {
+ Latencies.resize(SUnits->size(), -1);
+ NumNodesSolelyBlocking.resize(SUnits->size(), 0);
+ CalcLatency(*SU);
+ }
+
+ void updateNode(const SUnit *SU) {
+ Latencies[SU->NodeNum] = -1;
+ CalcLatency(*SU);
+ }
+
void releaseState() {
SUnits = 0;
Latencies.clear();
return NumNodesSolelyBlocking[NodeNum];
}
+ unsigned size() const { return Queue.size(); }
+
bool empty() const { return Queue.empty(); }
virtual void push(SUnit *U) {
return V;
}
+ void remove(SUnit *SU) {
+ assert(!Queue.empty() && "Not in queue!");
+ Queue.erase_one(SU);
+ }
+
// ScheduledNode - As nodes are scheduled, we look to see if there are any
// successor nodes that have a single unscheduled predecessor. If so, that
// single predecessor has a higher priority, since scheduling it will make
int CalcLatency(const SUnit &SU);
void AdjustPriorityOfUnscheduledPreds(SUnit *SU);
SUnit *getSingleUnscheduledPred(SUnit *SU);
-
- /// RemoveFromPriorityQueue - This is a really inefficient way to remove a
- /// node from a priority queue. We should roll our own heap to make this
- /// better or something.
- void RemoveFromPriorityQueue(SUnit *SU) {
- std::vector<SUnit*> Temp;
-
- assert(!Queue.empty() && "Not in queue!");
- while (Queue.top() != SU) {
- Temp.push_back(Queue.top());
- Queue.pop();
- assert(!Queue.empty() && "Not in queue!");
- }
-
- // Remove the node from the PQ.
- Queue.pop();
-
- // Add all the other nodes back.
- for (unsigned i = 0, e = Temp.size(); i != e; ++i)
- Queue.push(Temp[i]);
- }
};
}
int &Latency = Latencies[SU.NodeNum];
if (Latency != -1)
return Latency;
-
- int MaxSuccLatency = 0;
- for (SUnit::const_succ_iterator I = SU.Succs.begin(), E = SU.Succs.end();
- I != E; ++I)
- MaxSuccLatency = std::max(MaxSuccLatency, CalcLatency(*I->first));
- return Latency = MaxSuccLatency + SU.Latency;
+ std::vector<const SUnit*> WorkList;
+ WorkList.push_back(&SU);
+ while (!WorkList.empty()) {
+ const SUnit *Cur = WorkList.back();
+ bool AllDone = true;
+ int MaxSuccLatency = 0;
+ for (SUnit::const_succ_iterator I = Cur->Succs.begin(),E = Cur->Succs.end();
+ I != E; ++I) {
+ int SuccLatency = Latencies[I->Dep->NodeNum];
+ if (SuccLatency == -1) {
+ AllDone = false;
+ WorkList.push_back(I->Dep);
+ } else {
+ MaxSuccLatency = std::max(MaxSuccLatency, SuccLatency);
+ }
+ }
+ if (AllDone) {
+ Latencies[Cur->NodeNum] = MaxSuccLatency + Cur->Latency;
+ WorkList.pop_back();
+ }
+ }
+
+ return Latency;
}
/// CalculatePriorities - Calculate priorities of all scheduling units.
void LatencyPriorityQueue::CalculatePriorities() {
Latencies.assign(SUnits->size(), -1);
NumNodesSolelyBlocking.assign(SUnits->size(), 0);
-
- for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
- CalcLatency((*SUnits)[i]);
+
+ // For each node, calculate the maximal path from the node to the exit.
+ std::vector<std::pair<const SUnit*, unsigned> > WorkList;
+ for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
+ const SUnit *SU = &(*SUnits)[i];
+ if (SU->Succs.empty())
+ WorkList.push_back(std::make_pair(SU, 0U));
+ }
+
+ while (!WorkList.empty()) {
+ const SUnit *SU = WorkList.back().first;
+ unsigned SuccLat = WorkList.back().second;
+ WorkList.pop_back();
+ int &Latency = Latencies[SU->NodeNum];
+ if (Latency == -1 || (SU->Latency + SuccLat) > (unsigned)Latency) {
+ Latency = SU->Latency + SuccLat;
+ for (SUnit::const_pred_iterator I = SU->Preds.begin(),E = SU->Preds.end();
+ I != E; ++I)
+ WorkList.push_back(std::make_pair(I->Dep, Latency));
+ }
+ }
}
/// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor
SUnit *OnlyAvailablePred = 0;
for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- SUnit &Pred = *I->first;
+ SUnit &Pred = *I->Dep;
if (!Pred.isScheduled) {
// We found an available, but not scheduled, predecessor. If it's the
// only one we have found, keep track of it... otherwise give up.
unsigned NumNodesBlocking = 0;
for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I)
- if (getSingleUnscheduledPred(I->first) == SU)
+ if (getSingleUnscheduledPred(I->Dep) == SU)
++NumNodesBlocking;
NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking;
void LatencyPriorityQueue::ScheduledNode(SUnit *SU) {
for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I)
- AdjustPriorityOfUnscheduledPreds(I->first);
+ AdjustPriorityOfUnscheduledPreds(I->Dep);
}
/// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just
// Okay, we found a single predecessor that is available, but not scheduled.
// Since it is available, it must be in the priority queue. First remove it.
- RemoveFromPriorityQueue(OnlyAvailablePred);
+ remove(OnlyAvailablePred);
// Reinsert the node into the priority queue, which recomputes its
// NumNodesSolelyBlocking value.
/// recognizer and deletes it when done.
ScheduleDAG* llvm::createTDListDAGScheduler(SelectionDAGISel *IS,
SelectionDAG *DAG,
- MachineBasicBlock *BB) {
+ MachineBasicBlock *BB, bool Fast) {
return new ScheduleDAGList(*DAG, BB, DAG->getTarget(),
new LatencyPriorityQueue(),
IS->CreateTargetHazardRecognizer());
projects / oota-llvm.git / blobdiff