//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "pre-RA-sched"
-#include "llvm/CodeGen/ScheduleDAG.h"
+#include "ScheduleDAGSDNodes.h"
+#include "llvm/CodeGen/LatencyPriorityQueue.h"
+#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
#include "llvm/CodeGen/SchedulerRegistry.h"
#include "llvm/CodeGen/SelectionDAGISel.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/Support/ErrorHandling.h"
+#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/Statistic.h"
-#include "LatencyPriorityQueue.h"
#include <climits>
using namespace llvm;
/// ScheduleDAGList - The actual list scheduler implementation. This supports
/// top-down scheduling.
///
-class VISIBILITY_HIDDEN ScheduleDAGList : public ScheduleDAG {
+class ScheduleDAGList : public ScheduleDAGSDNodes {
private:
/// AvailableQueue - The priority queue to use for the available SUnits.
///
std::vector<SUnit*> PendingQueue;
/// HazardRec - The hazard recognizer to use.
- HazardRecognizer *HazardRec;
+ ScheduleHazardRecognizer *HazardRec;
public:
- ScheduleDAGList(SelectionDAG *dag, MachineBasicBlock *bb,
- const TargetMachine &tm,
+ ScheduleDAGList(MachineFunction &mf,
SchedulingPriorityQueue *availqueue,
- HazardRecognizer *HR)
- : ScheduleDAG(dag, bb, tm),
+ ScheduleHazardRecognizer *HR)
+ : ScheduleDAGSDNodes(mf),
AvailableQueue(availqueue), HazardRec(HR) {
}
void Schedule();
private:
- void ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain);
+ void ReleaseSucc(SUnit *SU, const SDep &D);
+ void ReleaseSuccessors(SUnit *SU);
void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
void ListScheduleTopDown();
};
} // end anonymous namespace
-HazardRecognizer::~HazardRecognizer() {}
-
-
/// Schedule - Schedule the DAG using list scheduling.
void ScheduleDAGList::Schedule() {
- DOUT << "********** List Scheduling **********\n";
+ DEBUG(dbgs() << "********** List Scheduling **********\n");
- // Build scheduling units.
- BuildSchedUnits();
+ // Build the scheduling graph.
+ BuildSchedGraph(NULL);
AvailableQueue->initNodes(SUnits);
/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
/// the PendingQueue if the count reaches zero. Also update its cycle bound.
-void ScheduleDAGList::ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain) {
- --SuccSU->NumPredsLeft;
-
+void ScheduleDAGList::ReleaseSucc(SUnit *SU, const SDep &D) {
+ SUnit *SuccSU = D.getSUnit();
+
#ifndef NDEBUG
- if (SuccSU->NumPredsLeft < 0) {
- cerr << "*** Scheduling failed! ***\n";
+ if (SuccSU->NumPredsLeft == 0) {
+ dbgs() << "*** Scheduling failed! ***\n";
SuccSU->dump(this);
- cerr << " has been released too many times!\n";
- assert(0);
+ dbgs() << " has been released too many times!\n";
+ llvm_unreachable(0);
}
#endif
+ --SuccSU->NumPredsLeft;
+
+ SuccSU->setDepthToAtLeast(SU->getDepth() + D.getLatency());
- // Compute the cycle when this SUnit 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.
- unsigned PredDoneCycle = SU->Cycle;
- if (!isChain)
- PredDoneCycle += SU->Latency;
- else if (SU->Latency)
- PredDoneCycle += 1;
- SuccSU->CycleBound = std::max(SuccSU->CycleBound, PredDoneCycle);
-
- if (SuccSU->NumPredsLeft == 0) {
+ // If all the node's predecessors are scheduled, this node is ready
+ // to be scheduled. Ignore the special ExitSU node.
+ if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU)
PendingQueue.push_back(SuccSU);
+}
+
+void ScheduleDAGList::ReleaseSuccessors(SUnit *SU) {
+ // Top down: release successors.
+ for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
+ I != E; ++I) {
+ assert(!I->isAssignedRegDep() &&
+ "The list-td scheduler doesn't yet support physreg dependencies!");
+
+ ReleaseSucc(SU, *I);
}
}
/// count of its successors. If a successor pending count is zero, add it to
/// the Available queue.
void ScheduleDAGList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
- DOUT << "*** Scheduling [" << CurCycle << "]: ";
+ DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
DEBUG(SU->dump(this));
Sequence.push_back(SU);
- SU->Cycle = CurCycle;
-
- // Top down: release successors.
- for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
- I != E; ++I)
- ReleaseSucc(SU, I->Dep, I->isCtrl);
+ assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!");
+ SU->setDepthToAtLeast(CurCycle);
+ ReleaseSuccessors(SU);
SU->isScheduled = true;
AvailableQueue->ScheduledNode(SU);
}
void ScheduleDAGList::ListScheduleTopDown() {
unsigned CurCycle = 0;
+ // Release any successors of the special Entry node.
+ ReleaseSuccessors(&EntrySU);
+
// All leaves to Available queue.
for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
// It is available if it has no predecessors.
// 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]->CycleBound == CurCycle) {
+ if (PendingQueue[i]->getDepth() == CurCycle) {
AvailableQueue->push(PendingQueue[i]);
PendingQueue[i]->isAvailable = true;
PendingQueue[i] = PendingQueue.back();
PendingQueue.pop_back();
--i; --e;
} else {
- assert(PendingQueue[i]->CycleBound > CurCycle && "Negative latency?");
+ assert(PendingQueue[i]->getDepth() > CurCycle && "Negative latency?");
}
}
}
SUnit *FoundSUnit = 0;
- SDNode *FoundNode = 0;
bool HasNoopHazards = false;
while (!AvailableQueue->empty()) {
SUnit *CurSUnit = AvailableQueue->pop();
- // Get the node represented by this SUnit.
- FoundNode = CurSUnit->getNode();
-
- // 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.
- while (!FoundNode->isMachineOpcode()) {
- SDNode *N = FoundNode->getFlaggedNode();
- if (!N) break;
- FoundNode = N;
- }
-
- HazardRecognizer::HazardType HT = HazardRec->getHazardType(FoundNode);
- if (HT == HazardRecognizer::NoHazard) {
+ ScheduleHazardRecognizer::HazardType HT =
+ HazardRec->getHazardType(CurSUnit);
+ if (HT == ScheduleHazardRecognizer::NoHazard) {
FoundSUnit = CurSUnit;
break;
}
-
+
// Remember if this is a noop hazard.
- HasNoopHazards |= HT == HazardRecognizer::NoopHazard;
+ HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard;
NotReady.push_back(CurSUnit);
}
// If we found a node to schedule, do it now.
if (FoundSUnit) {
ScheduleNodeTopDown(FoundSUnit, CurCycle);
- HazardRec->EmitInstruction(FoundNode);
+ HazardRec->EmitInstruction(FoundSUnit);
// If this is a pseudo-op node, we don't want to increment the current
// cycle.
} else if (!HasNoopHazards) {
// Otherwise, we have a pipeline stall, but no other problem, just advance
// the current cycle and try again.
- DOUT << "*** Advancing cycle, no work to do\n";
+ DEBUG(dbgs() << "*** Advancing cycle, no work to do\n");
HazardRec->AdvanceCycle();
++NumStalls;
++CurCycle;
// 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
// processors without pipeline interlocks and other cases.
- DOUT << "*** Emitting noop\n";
+ DEBUG(dbgs() << "*** Emitting noop\n");
HazardRec->EmitNoop();
- Sequence.push_back(0); // NULL SUnit* -> noop
+ Sequence.push_back(0); // NULL here means noop
++NumNoops;
++CurCycle;
}
}
#ifndef NDEBUG
- // Verify that all SUnits were scheduled.
- bool AnyNotSched = false;
- for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
- if (SUnits[i].NumPredsLeft != 0) {
- if (!AnyNotSched)
- cerr << "*** List scheduling failed! ***\n";
- SUnits[i].dump(this);
- cerr << "has not been scheduled!\n";
- AnyNotSched = true;
- }
- }
- assert(!AnyNotSched);
+ VerifySchedule(/*isBottomUp=*/false);
#endif
}
/// createTDListDAGScheduler - This creates a top-down list scheduler with a
/// new hazard recognizer. This scheduler takes ownership of the hazard
/// recognizer and deletes it when done.
-ScheduleDAG* llvm::createTDListDAGScheduler(SelectionDAGISel *IS,
- SelectionDAG *DAG,
- const TargetMachine *TM,
- MachineBasicBlock *BB, bool Fast) {
- return new ScheduleDAGList(DAG, BB, *TM,
+ScheduleDAGSDNodes *
+llvm::createTDListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) {
+ return new ScheduleDAGList(*IS->MF,
new LatencyPriorityQueue(),
IS->CreateTargetHazardRecognizer());
}
projects / oota-llvm.git / blobdiff