#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");
STATISTIC(NumStalls, "Number of pipeline stalls");
static RegisterScheduler
- tdListDAGScheduler("list-td", " Top-down list scheduler",
+ tdListDAGScheduler("list-td", "Top-down list scheduler",
createTDListDAGScheduler);
namespace {
// 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();
}
//===----------------------------------------------------------------------===//
/// schedulers.
void ScheduleDAGList::ListScheduleTopDown() {
unsigned CurCycle = 0;
- SUnit *Entry = SUnitMap[DAG.getEntryNode().Val].front();
// 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);
/// 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*, std::vector<SUnit*> > &sumap,
- std::vector<SUnit> &sunits) {
+ void initNodes(std::vector<SUnit> &sunits) {
SUnits = &sunits;
// Calculate node priorities.
CalculatePriorities();
return V;
}
- /// remove - 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 remove(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]);
+ Queue.erase_one(SU);
}
// ScheduledNode - As nodes are scheduled, we look to see if there are any
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.size() == 0)
+ if (SU->Succs.empty())
WorkList.push_back(std::make_pair(SU, 0U));
}
/// 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());