//===----------------------------------------------------------------------===//
#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/Support/ErrorHandling.h"
+#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/PriorityQueue.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.
///
/// 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;
+ /// the operation). Once the operands become available, the instruction is
+ /// added to the AvailableQueue.
+ 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 *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.
-void ScheduleDAGList::ReleaseSucc(SUnit *SuccSU, bool isChain) {
- SuccSU->NumPredsLeft--;
-
- assert(SuccSU->NumPredsLeft >= 0 &&
- "List scheduling internal error");
-
+/// the PendingQueue if the count reaches zero. Also update its cycle bound.
+void ScheduleDAGList::ReleaseSucc(SUnit *SU, const SDep &D) {
+ SUnit *SuccSU = D.getSUnit();
+
+#ifndef NDEBUG
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.
- unsigned AvailableCycle = 0;
- for (SUnit::pred_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.
- SUnit &Pred = *I->Dep;
- unsigned PredDoneCycle = Pred.Cycle;
- if (!I->isCtrl)
- PredDoneCycle += Pred.Latency;
- else if (Pred.Latency)
- PredDoneCycle += 1;
+ dbgs() << "*** Scheduling failed! ***\n";
+ SuccSU->dump(this);
+ dbgs() << " has been released too many times!\n";
+ llvm_unreachable(0);
+ }
+#endif
+ --SuccSU->NumPredsLeft;
- AvailableCycle = std::max(AvailableCycle, PredDoneCycle);
- }
-
- PendingQueue.push_back(std::make_pair(AvailableCycle, SuccSU));
+ SuccSU->setDepthToAtLeast(SU->getDepth() + D.getLatency());
+
+ // 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(SU->dump(DAG));
+ DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
+ DEBUG(SU->dump(this));
Sequence.push_back(SU);
- SU->Cycle = CurCycle;
-
- // Bottom up: release successors.
- for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
- I != E; ++I)
- ReleaseSucc(I->Dep, I->isCtrl);
+ assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!");
+ SU->setDepthToAtLeast(CurCycle);
+
+ ReleaseSuccessors(SU);
+ SU->isScheduled = true;
+ AvailableQueue->ScheduledNode(SU);
}
/// ListScheduleTopDown - The main loop of list scheduling for top-down
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.
if (SUnits[i].Preds.empty()) {
AvailableQueue->push(&SUnits[i]);
- SUnits[i].isAvailable = SUnits[i].isPending = true;
+ SUnits[i].isAvailable = true;
}
}
// 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;
+ 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].first > 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);
- FoundSUnit->isScheduled = true;
- AvailableQueue->ScheduledNode(FoundSUnit);
+ 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(DAG);
- 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