//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "pre-RA-sched"
-#include "llvm/CodeGen/ScheduleDAGSDNodes.h"
+#include "ScheduleDAGSDNodes.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/BitVector.h"
#include "llvm/ADT/PriorityQueue.h"
-#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <climits>
-#include "llvm/Support/CommandLine.h"
using namespace llvm;
STATISTIC(NumBacktracks, "Number of times scheduler backtracked");
STATISTIC(NumUnfolds, "Number of nodes unfolded");
STATISTIC(NumDups, "Number of duplicated nodes");
-STATISTIC(NumCCCopies, "Number of cross class copies");
+STATISTIC(NumPRCopies, "Number of physical register copies");
static RegisterScheduler
burrListDAGScheduler("list-burr",
ScheduleDAGTopologicalSort Topo;
public:
- ScheduleDAGRRList(SelectionDAG *dag, MachineBasicBlock *bb,
- const TargetMachine &tm, bool isbottomup,
+ ScheduleDAGRRList(MachineFunction &mf,
+ bool isbottomup,
SchedulingPriorityQueue *availqueue)
- : ScheduleDAGSDNodes(dag, bb, tm), isBottomUp(isbottomup),
+ : ScheduleDAGSDNodes(mf), isBottomUp(isbottomup),
AvailableQueue(availqueue), Topo(SUnits) {
}
return Topo.IsReachable(SU, TargetSU);
}
- /// willCreateCycle - Returns true if adding an edge from SU to TargetSU will
+ /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will
/// create a cycle.
bool WillCreateCycle(SUnit *SU, SUnit *TargetSU) {
return Topo.WillCreateCycle(SU, TargetSU);
}
- /// AddPred - This adds the specified node X as a predecessor of
- /// the current node Y if not already.
+ /// AddPred - adds a predecessor edge to SUnit SU.
/// This returns true if this is a new predecessor.
/// Updates the topological ordering if required.
- bool AddPred(SUnit *Y, SUnit *X, bool isCtrl, bool isArtificial,
- unsigned PhyReg = 0, int Cost = 1) {
- Topo.AddPred(Y, X);
- return Y->addPred(X, isCtrl, isArtificial, PhyReg, Cost);
+ void AddPred(SUnit *SU, const SDep &D) {
+ Topo.AddPred(SU, D.getSUnit());
+ SU->addPred(D);
}
- /// RemovePred - This removes the specified node N from the predecessors of
- /// the current node M. Updates the topological ordering if required.
- bool RemovePred(SUnit *M, SUnit *N, bool isCtrl, bool isArtificial) {
- Topo.RemovePred(M, N);
- return M->removePred(N, isCtrl, isArtificial, false);
+ /// RemovePred - removes a predecessor edge from SUnit SU.
+ /// This returns true if an edge was removed.
+ /// Updates the topological ordering if required.
+ void RemovePred(SUnit *SU, const SDep &D) {
+ Topo.RemovePred(SU, D.getSUnit());
+ SU->removePred(D);
}
private:
- void ReleasePred(SUnit *SU, SUnit *PredSU, bool isChain);
- void ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain);
- void CapturePred(SUnit*, SUnit*, bool);
+ void ReleasePred(SUnit *SU, const SDep *PredEdge);
+ void ReleasePredecessors(SUnit *SU, unsigned CurCycle);
+ void ReleaseSucc(SUnit *SU, const SDep *SuccEdge);
+ void ReleaseSuccessors(SUnit *SU);
+ void CapturePred(SDep *PredEdge);
void ScheduleNodeBottomUp(SUnit*, unsigned);
void ScheduleNodeTopDown(SUnit*, unsigned);
void UnscheduleNodeBottomUp(SUnit*);
void BacktrackBottomUp(SUnit*, unsigned, unsigned&);
SUnit *CopyAndMoveSuccessors(SUnit*);
- void InsertCCCopiesAndMoveSuccs(SUnit*, unsigned,
- const TargetRegisterClass*,
- const TargetRegisterClass*,
- SmallVector<SUnit*, 2>&);
+ void InsertCopiesAndMoveSuccs(SUnit*, unsigned,
+ const TargetRegisterClass*,
+ const TargetRegisterClass*,
+ SmallVector<SUnit*, 2>&);
bool DelayForLiveRegsBottomUp(SUnit*, SmallVector<unsigned, 4>&);
void ListScheduleTopDown();
void ListScheduleBottomUp();
- void CommuteNodesToReducePressure();
/// CreateNewSUnit - Creates a new SUnit and returns a pointer to it.
Topo.InitDAGTopologicalSorting();
return NewNode;
}
+
+ /// ForceUnitLatencies - Return true, since register-pressure-reducing
+ /// scheduling doesn't need actual latency information.
+ bool ForceUnitLatencies() const { return true; }
};
} // end anonymous namespace
LiveRegDefs.resize(TRI->getNumRegs(), NULL);
LiveRegCycles.resize(TRI->getNumRegs(), 0);
- // Build scheduling units.
- BuildSchedUnits();
+ // Build the scheduling graph.
+ BuildSchedGraph();
DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
SUnits[su].dumpAll(this));
- CalculateDepths();
- CalculateHeights();
Topo.InitDAGTopologicalSorting();
AvailableQueue->initNodes(SUnits);
ListScheduleTopDown();
AvailableQueue->releaseState();
-
- CommuteNodesToReducePressure();
-}
-
-/// CommuteNodesToReducePressure - If a node is two-address and commutable, and
-/// it is not the last use of its first operand, add it to the CommuteSet if
-/// possible. It will be commuted when it is translated to a MI.
-void ScheduleDAGRRList::CommuteNodesToReducePressure() {
- SmallPtrSet<SUnit*, 4> OperandSeen;
- for (unsigned i = Sequence.size(); i != 0; ) {
- --i;
- SUnit *SU = Sequence[i];
- if (!SU || !SU->getNode()) continue;
- if (SU->isCommutable) {
- unsigned Opc = SU->getNode()->getMachineOpcode();
- const TargetInstrDesc &TID = TII->get(Opc);
- unsigned NumRes = TID.getNumDefs();
- unsigned NumOps = TID.getNumOperands() - NumRes;
- for (unsigned j = 0; j != NumOps; ++j) {
- if (TID.getOperandConstraint(j+NumRes, TOI::TIED_TO) == -1)
- continue;
-
- SDNode *OpN = SU->getNode()->getOperand(j).getNode();
- SUnit *OpSU = isPassiveNode(OpN) ? NULL : &SUnits[OpN->getNodeId()];
- if (OpSU && OperandSeen.count(OpSU) == 1) {
- // Ok, so SU is not the last use of OpSU, but SU is two-address so
- // it will clobber OpSU. Try to commute SU if no other source operands
- // are live below.
- bool DoCommute = true;
- for (unsigned k = 0; k < NumOps; ++k) {
- if (k != j) {
- OpN = SU->getNode()->getOperand(k).getNode();
- OpSU = isPassiveNode(OpN) ? NULL : &SUnits[OpN->getNodeId()];
- if (OpSU && OperandSeen.count(OpSU) == 1) {
- DoCommute = false;
- break;
- }
- }
- }
- if (DoCommute)
- CommuteSet.insert(SU->getNode());
- }
-
- // Only look at the first use&def node for now.
- break;
- }
- }
-
- for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
- I != E; ++I) {
- if (!I->isCtrl)
- OperandSeen.insert(I->Dep->OrigNode);
- }
- }
}
//===----------------------------------------------------------------------===//
/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
/// the AvailableQueue if the count reaches zero. Also update its cycle bound.
-void ScheduleDAGRRList::ReleasePred(SUnit *SU, SUnit *PredSU, bool isChain) {
+void ScheduleDAGRRList::ReleasePred(SUnit *SU, const SDep *PredEdge) {
+ SUnit *PredSU = PredEdge->getSUnit();
--PredSU->NumSuccsLeft;
#ifndef NDEBUG
}
#endif
- if (PredSU->NumSuccsLeft == 0) {
+ // If all the node's successors are scheduled, this node is ready
+ // to be scheduled. Ignore the special EntrySU node.
+ if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) {
PredSU->isAvailable = true;
AvailableQueue->push(PredSU);
}
}
-/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
-/// count of its predecessors. If a predecessor pending count is zero, add it to
-/// the Available queue.
-void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) {
- DOUT << "*** Scheduling [" << CurCycle << "]: ";
- DEBUG(SU->dump(this));
-
- SU->Cycle = CurCycle;
- Sequence.push_back(SU);
-
+void ScheduleDAGRRList::ReleasePredecessors(SUnit *SU, unsigned CurCycle) {
// Bottom up: release predecessors
for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- ReleasePred(SU, I->Dep, I->isCtrl);
- if (I->Cost < 0) {
+ ReleasePred(SU, &*I);
+ if (I->isAssignedRegDep()) {
// This is a physical register dependency and it's impossible or
// expensive to copy the register. Make sure nothing that can
// clobber the register is scheduled between the predecessor and
// this node.
- if (!LiveRegDefs[I->Reg]) {
+ if (!LiveRegDefs[I->getReg()]) {
++NumLiveRegs;
- LiveRegDefs[I->Reg] = I->Dep;
- LiveRegCycles[I->Reg] = CurCycle;
+ LiveRegDefs[I->getReg()] = I->getSUnit();
+ LiveRegCycles[I->getReg()] = CurCycle;
}
}
}
+}
+
+/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
+/// count of its predecessors. If a predecessor pending count is zero, add it to
+/// the Available queue.
+void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) {
+ DOUT << "*** Scheduling [" << CurCycle << "]: ";
+ DEBUG(SU->dump(this));
+
+ assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!");
+ SU->setHeightToAtLeast(CurCycle);
+ Sequence.push_back(SU);
+
+ ReleasePredecessors(SU, CurCycle);
// Release all the implicit physical register defs that are live.
for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- if (I->Cost < 0) {
- if (LiveRegCycles[I->Reg] == I->Dep->Cycle) {
+ if (I->isAssignedRegDep()) {
+ if (LiveRegCycles[I->getReg()] == I->getSUnit()->getHeight()) {
assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
- assert(LiveRegDefs[I->Reg] == SU &&
+ assert(LiveRegDefs[I->getReg()] == SU &&
"Physical register dependency violated?");
--NumLiveRegs;
- LiveRegDefs[I->Reg] = NULL;
- LiveRegCycles[I->Reg] = 0;
+ LiveRegDefs[I->getReg()] = NULL;
+ LiveRegCycles[I->getReg()] = 0;
}
}
}
/// CapturePred - This does the opposite of ReleasePred. Since SU is being
/// unscheduled, incrcease the succ left count of its predecessors. Remove
/// them from AvailableQueue if necessary.
-void ScheduleDAGRRList::CapturePred(SUnit *PredSU, SUnit *SU, bool isChain) {
+void ScheduleDAGRRList::CapturePred(SDep *PredEdge) {
+ SUnit *PredSU = PredEdge->getSUnit();
if (PredSU->isAvailable) {
PredSU->isAvailable = false;
if (!PredSU->isPending)
/// UnscheduleNodeBottomUp - Remove the node from the schedule, update its and
/// its predecessor states to reflect the change.
void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) {
- DOUT << "*** Unscheduling [" << SU->Cycle << "]: ";
+ DOUT << "*** Unscheduling [" << SU->getHeight() << "]: ";
DEBUG(SU->dump(this));
AvailableQueue->UnscheduledNode(SU);
for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- CapturePred(I->Dep, SU, I->isCtrl);
- if (I->Cost < 0 && SU->Cycle == LiveRegCycles[I->Reg]) {
+ CapturePred(&*I);
+ if (I->isAssignedRegDep() && SU->getHeight() == LiveRegCycles[I->getReg()]) {
assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
- assert(LiveRegDefs[I->Reg] == I->Dep &&
+ assert(LiveRegDefs[I->getReg()] == I->getSUnit() &&
"Physical register dependency violated?");
--NumLiveRegs;
- LiveRegDefs[I->Reg] = NULL;
- LiveRegCycles[I->Reg] = 0;
+ LiveRegDefs[I->getReg()] = NULL;
+ LiveRegCycles[I->getReg()] = 0;
}
}
for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- if (I->Cost < 0) {
- if (!LiveRegDefs[I->Reg]) {
- LiveRegDefs[I->Reg] = SU;
+ if (I->isAssignedRegDep()) {
+ if (!LiveRegDefs[I->getReg()]) {
+ LiveRegDefs[I->getReg()] = SU;
++NumLiveRegs;
}
- if (I->Dep->Cycle < LiveRegCycles[I->Reg])
- LiveRegCycles[I->Reg] = I->Dep->Cycle;
+ if (I->getSUnit()->getHeight() < LiveRegCycles[I->getReg()])
+ LiveRegCycles[I->getReg()] = I->getSUnit()->getHeight();
}
}
- SU->Cycle = 0;
+ SU->setHeightDirty();
SU->isScheduled = false;
SU->isAvailable = true;
AvailableQueue->push(SU);
}
/// BacktrackBottomUp - Backtrack scheduling to a previous cycle specified in
-/// BTCycle in order to schedule a specific node. Returns the last unscheduled
-/// SUnit. Also returns if a successor is unscheduled in the process.
+/// BTCycle in order to schedule a specific node.
void ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, unsigned BtCycle,
unsigned &CurCycle) {
SUnit *OldSU = NULL;
--CurCycle;
}
-
- if (SU->isSucc(OldSU)) {
- assert(false && "Something is wrong!");
- abort();
- }
+ assert(!SU->isSucc(OldSU) && "Something is wrong!");
++NumBacktracks;
}
} else {
LoadSU = CreateNewSUnit(LoadNode);
LoadNode->setNodeId(LoadSU->NodeNum);
-
- LoadSU->Depth = SU->Depth;
- LoadSU->Height = SU->Height;
ComputeLatency(LoadSU);
}
}
if (TID.isCommutable())
NewSU->isCommutable = true;
- // FIXME: Calculate height / depth and propagate the changes?
- NewSU->Depth = SU->Depth;
- NewSU->Height = SU->Height;
ComputeLatency(NewSU);
- SUnit *ChainPred = NULL;
+ SDep ChainPred;
SmallVector<SDep, 4> ChainSuccs;
SmallVector<SDep, 4> LoadPreds;
SmallVector<SDep, 4> NodePreds;
SmallVector<SDep, 4> NodeSuccs;
for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- if (I->isCtrl)
- ChainPred = I->Dep;
- else if (I->Dep->getNode() && I->Dep->getNode()->isOperandOf(LoadNode))
- LoadPreds.push_back(SDep(I->Dep, I->Reg, I->Cost, false, false, false));
+ if (I->isCtrl())
+ ChainPred = *I;
+ else if (I->getSUnit()->getNode() &&
+ I->getSUnit()->getNode()->isOperandOf(LoadNode))
+ LoadPreds.push_back(*I);
else
- NodePreds.push_back(SDep(I->Dep, I->Reg, I->Cost, false, false, false));
+ NodePreds.push_back(*I);
}
for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- if (I->isCtrl)
- ChainSuccs.push_back(SDep(I->Dep, I->Reg, I->Cost,
- I->isCtrl, I->isArtificial, I->isAntiDep));
+ if (I->isCtrl())
+ ChainSuccs.push_back(*I);
else
- NodeSuccs.push_back(SDep(I->Dep, I->Reg, I->Cost,
- I->isCtrl, I->isArtificial, I->isAntiDep));
+ NodeSuccs.push_back(*I);
}
- if (ChainPred) {
- RemovePred(SU, ChainPred, true, false);
+ if (ChainPred.getSUnit()) {
+ RemovePred(SU, ChainPred);
if (isNewLoad)
- AddPred(LoadSU, ChainPred, true, false);
+ AddPred(LoadSU, ChainPred);
}
for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) {
- SDep *Pred = &LoadPreds[i];
- RemovePred(SU, Pred->Dep, Pred->isCtrl, Pred->isArtificial);
+ const SDep &Pred = LoadPreds[i];
+ RemovePred(SU, Pred);
if (isNewLoad) {
- AddPred(LoadSU, Pred->Dep, Pred->isCtrl, Pred->isArtificial,
- Pred->Reg, Pred->Cost);
+ AddPred(LoadSU, Pred);
}
}
for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) {
- SDep *Pred = &NodePreds[i];
- RemovePred(SU, Pred->Dep, Pred->isCtrl, Pred->isArtificial);
- AddPred(NewSU, Pred->Dep, Pred->isCtrl, Pred->isArtificial,
- Pred->Reg, Pred->Cost);
+ const SDep &Pred = NodePreds[i];
+ RemovePred(SU, Pred);
+ AddPred(NewSU, Pred);
}
for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) {
- SDep *Succ = &NodeSuccs[i];
- RemovePred(Succ->Dep, SU, Succ->isCtrl, Succ->isArtificial);
- AddPred(Succ->Dep, NewSU, Succ->isCtrl, Succ->isArtificial,
- Succ->Reg, Succ->Cost);
+ SDep D = NodeSuccs[i];
+ SUnit *SuccDep = D.getSUnit();
+ D.setSUnit(SU);
+ RemovePred(SuccDep, D);
+ D.setSUnit(NewSU);
+ AddPred(SuccDep, D);
}
for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) {
- SDep *Succ = &ChainSuccs[i];
- RemovePred(Succ->Dep, SU, Succ->isCtrl, Succ->isArtificial);
+ SDep D = ChainSuccs[i];
+ SUnit *SuccDep = D.getSUnit();
+ D.setSUnit(SU);
+ RemovePred(SuccDep, D);
if (isNewLoad) {
- AddPred(Succ->Dep, LoadSU, Succ->isCtrl, Succ->isArtificial,
- Succ->Reg, Succ->Cost);
+ D.setSUnit(LoadSU);
+ AddPred(SuccDep, D);
}
}
if (isNewLoad) {
- AddPred(NewSU, LoadSU, false, false);
+ AddPred(NewSU, SDep(LoadSU, SDep::Order, LoadSU->Latency));
}
if (isNewLoad)
// New SUnit has the exact same predecessors.
for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I)
- if (!I->isArtificial) {
- AddPred(NewSU, I->Dep, I->isCtrl, false, I->Reg, I->Cost);
- NewSU->Depth = std::max(NewSU->Depth, I->Dep->Depth+1);
- }
+ if (!I->isArtificial())
+ AddPred(NewSU, *I);
// Only copy scheduled successors. Cut them from old node's successor
// list and move them over.
- SmallVector<std::pair<SUnit*, bool>, 4> DelDeps;
+ SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- if (I->isArtificial)
+ if (I->isArtificial())
continue;
- if (I->Dep->isScheduled) {
- NewSU->Height = std::max(NewSU->Height, I->Dep->Height+1);
- AddPred(I->Dep, NewSU, I->isCtrl, false, I->Reg, I->Cost);
- DelDeps.push_back(std::make_pair(I->Dep, I->isCtrl));
+ SUnit *SuccSU = I->getSUnit();
+ if (SuccSU->isScheduled) {
+ SDep D = *I;
+ D.setSUnit(NewSU);
+ AddPred(SuccSU, D);
+ D.setSUnit(SU);
+ DelDeps.push_back(std::make_pair(SuccSU, D));
}
}
- for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) {
- SUnit *Succ = DelDeps[i].first;
- bool isCtrl = DelDeps[i].second;
- RemovePred(Succ, SU, isCtrl, false);
- }
+ for (unsigned i = 0, e = DelDeps.size(); i != e; ++i)
+ RemovePred(DelDeps[i].first, DelDeps[i].second);
AvailableQueue->updateNode(SU);
AvailableQueue->addNode(NewSU);
return NewSU;
}
-/// InsertCCCopiesAndMoveSuccs - Insert expensive cross register class copies
-/// and move all scheduled successors of the given SUnit to the last copy.
-void ScheduleDAGRRList::InsertCCCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
- const TargetRegisterClass *DestRC,
- const TargetRegisterClass *SrcRC,
+/// InsertCopiesAndMoveSuccs - Insert register copies and move all
+/// scheduled successors of the given SUnit to the last copy.
+void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
+ const TargetRegisterClass *DestRC,
+ const TargetRegisterClass *SrcRC,
SmallVector<SUnit*, 2> &Copies) {
SUnit *CopyFromSU = CreateNewSUnit(NULL);
CopyFromSU->CopySrcRC = SrcRC;
CopyFromSU->CopyDstRC = DestRC;
- CopyFromSU->Depth = SU->Depth;
- CopyFromSU->Height = SU->Height;
SUnit *CopyToSU = CreateNewSUnit(NULL);
CopyToSU->CopySrcRC = DestRC;
// Only copy scheduled successors. Cut them from old node's successor
// list and move them over.
- SmallVector<std::pair<SUnit*, bool>, 4> DelDeps;
+ SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- if (I->isArtificial)
+ if (I->isArtificial())
continue;
- if (I->Dep->isScheduled) {
- CopyToSU->Height = std::max(CopyToSU->Height, I->Dep->Height+1);
- AddPred(I->Dep, CopyToSU, I->isCtrl, false, I->Reg, I->Cost);
- DelDeps.push_back(std::make_pair(I->Dep, I->isCtrl));
+ SUnit *SuccSU = I->getSUnit();
+ if (SuccSU->isScheduled) {
+ SDep D = *I;
+ D.setSUnit(CopyToSU);
+ AddPred(SuccSU, D);
+ DelDeps.push_back(std::make_pair(SuccSU, *I));
}
}
- for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) {
- SUnit *Succ = DelDeps[i].first;
- bool isCtrl = DelDeps[i].second;
- RemovePred(Succ, SU, isCtrl, false);
- }
+ for (unsigned i = 0, e = DelDeps.size(); i != e; ++i)
+ RemovePred(DelDeps[i].first, DelDeps[i].second);
- AddPred(CopyFromSU, SU, false, false, Reg, -1);
- AddPred(CopyToSU, CopyFromSU, false, false, Reg, 1);
+ AddPred(CopyFromSU, SDep(SU, SDep::Data, SU->Latency, Reg));
+ AddPred(CopyToSU, SDep(CopyFromSU, SDep::Data, CopyFromSU->Latency, 0));
AvailableQueue->updateNode(SU);
AvailableQueue->addNode(CopyFromSU);
Copies.push_back(CopyFromSU);
Copies.push_back(CopyToSU);
- ++NumCCCopies;
+ ++NumPRCopies;
}
/// getPhysicalRegisterVT - Returns the ValueType of the physical register
// If this node would clobber any "live" register, then it's not ready.
for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- if (I->Cost < 0) {
- unsigned Reg = I->Reg;
- if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != I->Dep) {
+ if (I->isAssignedRegDep()) {
+ unsigned Reg = I->getReg();
+ if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != I->getSUnit()) {
if (RegAdded.insert(Reg))
LRegs.push_back(Reg);
}
for (const unsigned *Alias = TRI->getAliasSet(Reg);
*Alias; ++Alias)
- if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != I->Dep) {
+ if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != I->getSUnit()) {
if (RegAdded.insert(*Alias))
LRegs.push_back(*Alias);
}
/// schedulers.
void ScheduleDAGRRList::ListScheduleBottomUp() {
unsigned CurCycle = 0;
+
+ // Release any predecessors of the special Exit node.
+ ReleasePredecessors(&ExitSU, CurCycle);
+
// Add root to Available queue.
if (!SUnits.empty()) {
SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
OldSU->isAvailable = false;
AvailableQueue->remove(OldSU);
}
- AddPred(TrySU, OldSU, true, true);
+ AddPred(TrySU, SDep(OldSU, SDep::Order, /*Latency=*/1,
+ /*Reg=*/0, /*isNormalMemory=*/false,
+ /*isMustAlias=*/false, /*isArtificial=*/true));
// If one or more successors has been unscheduled, then the current
// node is no longer avaialable. Schedule a successor that's now
// available instead.
}
if (!CurSU) {
- // Can't backtrack. Try duplicating the nodes that produces these
- // "expensive to copy" values to break the dependency. In case even
- // that doesn't work, insert cross class copies.
+ // Can't backtrack. If it's too expensive to copy the value, then try
+ // duplicate the nodes that produces these "too expensive to copy"
+ // values to break the dependency. In case even that doesn't work,
+ // insert cross class copies.
+ // If it's not too expensive, i.e. cost != -1, issue copies.
SUnit *TrySU = NotReady[0];
SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU];
assert(LRegs.size() == 1 && "Can't handle this yet!");
unsigned Reg = LRegs[0];
SUnit *LRDef = LiveRegDefs[Reg];
- SUnit *NewDef = CopyAndMoveSuccessors(LRDef);
+ MVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII);
+ const TargetRegisterClass *RC =
+ TRI->getPhysicalRegisterRegClass(Reg, VT);
+ const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
+
+ // If cross copy register class is null, then it must be possible copy
+ // the value directly. Do not try duplicate the def.
+ SUnit *NewDef = 0;
+ if (DestRC)
+ NewDef = CopyAndMoveSuccessors(LRDef);
+ else
+ DestRC = RC;
if (!NewDef) {
- // Issue expensive cross register class copies.
- MVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII);
- const TargetRegisterClass *RC =
- TRI->getPhysicalRegisterRegClass(Reg, VT);
- const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
- if (!DestRC) {
- assert(false && "Don't know how to copy this physical register!");
- abort();
- }
+ // Issue copies, these can be expensive cross register class copies.
SmallVector<SUnit*, 2> Copies;
- InsertCCCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
- DOUT << "Adding an edge from SU # " << TrySU->NodeNum
+ InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
+ DOUT << "Adding an edge from SU #" << TrySU->NodeNum
<< " to SU #" << Copies.front()->NodeNum << "\n";
- AddPred(TrySU, Copies.front(), true, true);
+ AddPred(TrySU, SDep(Copies.front(), SDep::Order, /*Latency=*/1,
+ /*Reg=*/0, /*isNormalMemory=*/false,
+ /*isMustAlias=*/false,
+ /*isArtificial=*/true));
NewDef = Copies.back();
}
- DOUT << "Adding an edge from SU # " << NewDef->NodeNum
+ DOUT << "Adding an edge from SU #" << NewDef->NodeNum
<< " to SU #" << TrySU->NodeNum << "\n";
LiveRegDefs[Reg] = NewDef;
- AddPred(NewDef, TrySU, true, true);
+ AddPred(NewDef, SDep(TrySU, SDep::Order, /*Latency=*/1,
+ /*Reg=*/0, /*isNormalMemory=*/false,
+ /*isMustAlias=*/false,
+ /*isArtificial=*/true));
TrySU->isAvailable = false;
CurSU = NewDef;
}
- if (!CurSU) {
- assert(false && "Unable to resolve live physical register dependencies!");
- abort();
- }
+ assert(CurSU && "Unable to resolve live physical register dependencies!");
}
// Add the nodes that aren't ready back onto the available list.
/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
/// the AvailableQueue if the count reaches zero. Also update its cycle bound.
-void ScheduleDAGRRList::ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain) {
+void ScheduleDAGRRList::ReleaseSucc(SUnit *SU, const SDep *SuccEdge) {
+ SUnit *SuccSU = SuccEdge->getSUnit();
--SuccSU->NumPredsLeft;
#ifndef NDEBUG
}
#endif
- 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) {
SuccSU->isAvailable = true;
AvailableQueue->push(SuccSU);
}
}
+void ScheduleDAGRRList::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-tdrr scheduler doesn't yet support physreg dependencies!");
+
+ ReleaseSucc(SU, &*I);
+ }
+}
+
/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
/// count of its successors. If a successor pending count is zero, add it to
/// the Available queue.
DOUT << "*** Scheduling [" << CurCycle << "]: ";
DEBUG(SU->dump(this));
- SU->Cycle = CurCycle;
+ assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!");
+ SU->setDepthToAtLeast(CurCycle);
Sequence.push_back(SU);
- // 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);
-
+ ReleaseSuccessors(SU);
SU->isScheduled = true;
AvailableQueue->ScheduledNode(SU);
}
void ScheduleDAGRRList::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.
};
} // end anonymous namespace
-static inline bool isCopyFromLiveIn(const SUnit *SU) {
- SDNode *N = SU->getNode();
- return N && N->getOpcode() == ISD::CopyFromReg &&
- N->getOperand(N->getNumOperands()-1).getValueType() != MVT::Flag;
-}
-
/// CalcNodeSethiUllmanNumber - Compute Sethi Ullman number.
/// Smaller number is the higher priority.
static unsigned
unsigned Extra = 0;
for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- if (I->isCtrl) continue; // ignore chain preds
- SUnit *PredSU = I->Dep;
+ if (I->isCtrl()) continue; // ignore chain preds
+ SUnit *PredSU = I->getSUnit();
unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU, SUNumbers);
if (PredSethiUllman > SethiUllmanNumber) {
SethiUllmanNumber = PredSethiUllman;
Extra = 0;
- } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl)
+ } else if (PredSethiUllman == SethiUllmanNumber)
++Extra;
}
unsigned getNodePriority(const SUnit *SU) const {
assert(SU->NodeNum < SethiUllmanNumbers.size());
unsigned Opc = SU->getNode() ? SU->getNode()->getOpcode() : 0;
- if (Opc == ISD::CopyFromReg && !isCopyFromLiveIn(SU))
- // CopyFromReg should be close to its def because it restricts
- // allocation choices. But if it is a livein then perhaps we want it
- // closer to its uses so it can be coalesced.
- return 0xffff;
- else if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
+ if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
// CopyToReg should be close to its uses to facilitate coalescing and
// avoid spilling.
return 0;
- else if (Opc == TargetInstrInfo::EXTRACT_SUBREG ||
- Opc == TargetInstrInfo::INSERT_SUBREG)
+ if (Opc == TargetInstrInfo::EXTRACT_SUBREG ||
+ Opc == TargetInstrInfo::INSERT_SUBREG)
// EXTRACT_SUBREG / INSERT_SUBREG should be close to its use to
// facilitate coalescing.
return 0;
- else if (SU->NumSuccs == 0)
- // If SU does not have a use, i.e. it doesn't produce a value that would
- // be consumed (e.g. store), then it terminates a chain of computation.
- // Give it a large SethiUllman number so it will be scheduled right
- // before its predecessors that it doesn't lengthen their live ranges.
+ if (SU->NumSuccs == 0 && SU->NumPreds != 0)
+ // If SU does not have a register use, i.e. it doesn't produce a value
+ // that would be consumed (e.g. store), then it terminates a chain of
+ // computation. Give it a large SethiUllman number so it will be
+ // scheduled right before its predecessors that it doesn't lengthen
+ // their live ranges.
return 0xffff;
- else if (SU->NumPreds == 0)
- // If SU does not have a def, schedule it close to its uses because it
- // does not lengthen any live ranges.
+ if (SU->NumPreds == 0 && SU->NumSuccs != 0)
+ // If SU does not have a register def, schedule it close to its uses
+ // because it does not lengthen any live ranges.
return 0;
- else
- return SethiUllmanNumbers[SU->NodeNum];
+ return SethiUllmanNumbers[SU->NodeNum];
}
unsigned size() const { return Queue.size(); }
/// closestSucc - Returns the scheduled cycle of the successor which is
/// closet to the current cycle.
static unsigned closestSucc(const SUnit *SU) {
- unsigned MaxCycle = 0;
+ unsigned MaxHeight = 0;
for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- unsigned Cycle = I->Dep->Cycle;
+ if (I->isCtrl()) continue; // ignore chain succs
+ unsigned Height = I->getSUnit()->getHeight();
// If there are bunch of CopyToRegs stacked up, they should be considered
// to be at the same position.
- if (I->Dep->getNode() && I->Dep->getNode()->getOpcode() == ISD::CopyToReg)
- Cycle = closestSucc(I->Dep)+1;
- if (Cycle > MaxCycle)
- MaxCycle = Cycle;
+ if (I->getSUnit()->getNode() &&
+ I->getSUnit()->getNode()->getOpcode() == ISD::CopyToReg)
+ Height = closestSucc(I->getSUnit())+1;
+ if (Height > MaxHeight)
+ MaxHeight = Height;
}
- return MaxCycle;
+ return MaxHeight;
}
/// calcMaxScratches - Returns an cost estimate of the worse case requirement
-/// for scratch registers. Live-in operands and live-out results don't count
-/// since they are "fixed".
+/// for scratch registers, i.e. number of data dependencies.
static unsigned calcMaxScratches(const SUnit *SU) {
unsigned Scratches = 0;
for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
- if (I->isCtrl) continue; // ignore chain preds
- if (!I->Dep->getNode() || I->Dep->getNode()->getOpcode() != ISD::CopyFromReg)
- Scratches++;
- }
- for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
- I != E; ++I) {
- if (I->isCtrl) continue; // ignore chain succs
- if (!I->Dep->getNode() || I->Dep->getNode()->getOpcode() != ISD::CopyToReg)
- Scratches += 10;
+ if (I->isCtrl()) continue; // ignore chain preds
+ Scratches++;
}
return Scratches;
}
if (LDist != RDist)
return LDist < RDist;
- // Intuitively, it's good to push down instructions whose results are
- // liveout so their long live ranges won't conflict with other values
- // which are needed inside the BB. Further prioritize liveout instructions
- // by the number of operands which are calculated within the BB.
+ // How many registers becomes live when the node is scheduled.
unsigned LScratch = calcMaxScratches(left);
unsigned RScratch = calcMaxScratches(right);
if (LScratch != RScratch)
return LScratch > RScratch;
- if (left->Height != right->Height)
- return left->Height > right->Height;
+ if (left->getHeight() != right->getHeight())
+ return left->getHeight() > right->getHeight();
- if (left->Depth != right->Depth)
- return left->Depth < right->Depth;
+ if (left->getDepth() != right->getDepth())
+ return left->getDepth() < right->getDepth();
assert(left->NodeQueueId && right->NodeQueueId &&
"NodeQueueId cannot be zero");
static bool hasCopyToRegUse(const SUnit *SU) {
for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- if (I->isCtrl) continue;
- const SUnit *SuccSU = I->Dep;
+ if (I->isCtrl()) continue;
+ const SUnit *SuccSU = I->getSUnit();
if (SuccSU->getNode() && SuccSU->getNode()->getOpcode() == ISD::CopyToReg)
return true;
}
if (!DUSU) continue;
for (SUnit::const_succ_iterator I = DUSU->Succs.begin(),
E = DUSU->Succs.end(); I != E; ++I) {
- if (I->isCtrl) continue;
- SUnit *SuccSU = I->Dep;
+ if (I->isCtrl()) continue;
+ SUnit *SuccSU = I->getSUnit();
if (SuccSU == SU)
continue;
// Be conservative. Ignore if nodes aren't at roughly the same
// depth and height.
- if (SuccSU->Height < SU->Height && (SU->Height - SuccSU->Height) > 1)
+ if (SuccSU->getHeight() < SU->getHeight() &&
+ (SU->getHeight() - SuccSU->getHeight()) > 1)
continue;
if (!SuccSU->getNode() || !SuccSU->getNode()->isMachineOpcode())
continue;
if (canClobberPhysRegDefs(SuccSU, SU, TII, TRI))
continue;
}
- // Don't constraint extract_subreg / insert_subreg these may be
- // coalesced away. We don't them close to their uses.
+ // Don't constrain extract_subreg / insert_subreg; these may be
+ // coalesced away. We want them close to their uses.
unsigned SuccOpc = SuccSU->getNode()->getMachineOpcode();
if (SuccOpc == TargetInstrInfo::EXTRACT_SUBREG ||
SuccOpc == TargetInstrInfo::INSERT_SUBREG)
!scheduleDAG->IsReachable(SuccSU, SU)) {
DOUT << "Adding a pseudo-two-addr edge from SU # " << SU->NodeNum
<< " to SU #" << SuccSU->NodeNum << "\n";
- scheduleDAG->AddPred(SU, SuccSU, true, true);
+ scheduleDAG->AddPred(SU, SDep(SuccSU, SDep::Order, /*Latency=*/0,
+ /*Reg=*/0, /*isNormalMemory=*/false,
+ /*isMustAlias=*/false,
+ /*isArtificial=*/true));
}
}
}
unsigned Sum = 0;
for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
I != E; ++I) {
- const SUnit *SuccSU = I->Dep;
+ const SUnit *SuccSU = I->getSUnit();
for (SUnit::const_pred_iterator II = SuccSU->Preds.begin(),
EE = SuccSU->Preds.end(); II != EE; ++II) {
- SUnit *PredSU = II->Dep;
+ SUnit *PredSU = II->getSUnit();
if (!PredSU->isScheduled)
if (++Sum > Limit)
return Sum;
if (LPriority+LBonus != RPriority+RBonus)
return LPriority+LBonus < RPriority+RBonus;
- if (left->Depth != right->Depth)
- return left->Depth < right->Depth;
+ if (left->getDepth() != right->getDepth())
+ return left->getDepth() < right->getDepth();
if (left->NumSuccsLeft != right->NumSuccsLeft)
return left->NumSuccsLeft > right->NumSuccsLeft;
// Public Constructor Functions
//===----------------------------------------------------------------------===//
-llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAGISel *IS,
- SelectionDAG *DAG,
- const TargetMachine *TM,
- MachineBasicBlock *BB,
- bool) {
- const TargetInstrInfo *TII = TM->getInstrInfo();
- const TargetRegisterInfo *TRI = TM->getRegisterInfo();
+llvm::ScheduleDAGSDNodes *
+llvm::createBURRListDAGScheduler(SelectionDAGISel *IS, bool) {
+ const TargetMachine &TM = IS->TM;
+ const TargetInstrInfo *TII = TM.getInstrInfo();
+ const TargetRegisterInfo *TRI = TM.getRegisterInfo();
BURegReductionPriorityQueue *PQ = new BURegReductionPriorityQueue(TII, TRI);
ScheduleDAGRRList *SD =
- new ScheduleDAGRRList(DAG, BB, *TM, true, PQ);
+ new ScheduleDAGRRList(*IS->MF, true, PQ);
PQ->setScheduleDAG(SD);
return SD;
}
-llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS,
- SelectionDAG *DAG,
- const TargetMachine *TM,
- MachineBasicBlock *BB,
- bool) {
- const TargetInstrInfo *TII = TM->getInstrInfo();
- const TargetRegisterInfo *TRI = TM->getRegisterInfo();
+llvm::ScheduleDAGSDNodes *
+llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS, bool) {
+ const TargetMachine &TM = IS->TM;
+ const TargetInstrInfo *TII = TM.getInstrInfo();
+ const TargetRegisterInfo *TRI = TM.getRegisterInfo();
TDRegReductionPriorityQueue *PQ = new TDRegReductionPriorityQueue(TII, TRI);
- ScheduleDAGRRList *SD = new ScheduleDAGRRList(DAG, BB, *TM, false, PQ);
+ ScheduleDAGRRList *SD =
+ new ScheduleDAGRRList(*IS->MF, false, PQ);
PQ->setScheduleDAG(SD);
return SD;
}