X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FScheduleDAGFast.cpp;h=b7c47db58e27ac4666559703963370040bf93229;hb=2766a47310b05228e9bbc536d9f3a593fc31cd12;hp=def8868da95460b3232cddd09846836ab7c24e70;hpb=3cc6243ddfdba3ad64035b919c88b09773a60880;p=oota-llvm.git diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp index def8868da95..b7c47db58e2 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp @@ -12,37 +12,43 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "pre-RA-sched" -#include "llvm/CodeGen/ScheduleDAG.h" #include "llvm/CodeGen/SchedulerRegistry.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 "InstrEmitter.h" +#include "ScheduleDAGSDNodes.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/Support/CommandLine.h" +#include "llvm/CodeGen/SelectionDAGISel.h" +#include "llvm/DataLayout.h" +#include "llvm/InlineAsm.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" using namespace llvm; STATISTIC(NumUnfolds, "Number of nodes unfolded"); STATISTIC(NumDups, "Number of duplicated nodes"); -STATISTIC(NumCCCopies, "Number of cross class copies"); +STATISTIC(NumPRCopies, "Number of physical copies"); static RegisterScheduler fastDAGScheduler("fast", "Fast suboptimal list scheduling", createFastDAGScheduler); +static RegisterScheduler + linearizeDAGScheduler("linearize", "Linearize DAG, no scheduling", + createDAGLinearizer); + namespace { /// FastPriorityQueue - A degenerate priority queue that considers /// all nodes to have the same priority. /// - struct VISIBILITY_HIDDEN FastPriorityQueue { + struct FastPriorityQueue { SmallVector Queue; bool empty() const { return Queue.empty(); } - + void push(SUnit *U) { Queue.push_back(U); } @@ -58,7 +64,7 @@ namespace { //===----------------------------------------------------------------------===// /// ScheduleDAGFast - The actual "fast" list scheduler implementation. /// -class VISIBILITY_HIDDEN ScheduleDAGFast : public ScheduleDAG { +class ScheduleDAGFast : public ScheduleDAGSDNodes { private: /// AvailableQueue - The priority queue to use for the available SUnits. FastPriorityQueue AvailableQueue; @@ -71,58 +77,51 @@ private: std::vector LiveRegCycles; public: - ScheduleDAGFast(SelectionDAG *dag, MachineBasicBlock *bb, - const TargetMachine &tm) - : ScheduleDAG(dag, bb, tm) {} + ScheduleDAGFast(MachineFunction &mf) + : ScheduleDAGSDNodes(mf) {} void Schedule(); - /// 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. - bool AddPred(SUnit *Y, SUnit *X, bool isCtrl, bool isSpecial, - unsigned PhyReg = 0, int Cost = 1); + void AddPred(SUnit *SU, const SDep &D) { + SU->addPred(D); + } - /// RemovePred - This removes the specified node N from the predecessors of - /// the current node M. - bool RemovePred(SUnit *M, SUnit *N, bool isCtrl, bool isSpecial); + /// RemovePred - removes a predecessor edge from SUnit SU. + /// This returns true if an edge was removed. + void RemovePred(SUnit *SU, const SDep &D) { + SU->removePred(D); + } private: - void ReleasePred(SUnit *SU, SUnit *PredSU, bool isChain); + void ReleasePred(SUnit *SU, SDep *PredEdge); + void ReleasePredecessors(SUnit *SU, unsigned CurCycle); void ScheduleNodeBottomUp(SUnit*, unsigned); SUnit *CopyAndMoveSuccessors(SUnit*); - void InsertCCCopiesAndMoveSuccs(SUnit*, unsigned, - const TargetRegisterClass*, - const TargetRegisterClass*, - SmallVector&); + void InsertCopiesAndMoveSuccs(SUnit*, unsigned, + const TargetRegisterClass*, + const TargetRegisterClass*, + SmallVector&); bool DelayForLiveRegsBottomUp(SUnit*, SmallVector&); void ListScheduleBottomUp(); - /// CreateNewSUnit - Creates a new SUnit and returns a pointer to it. - SUnit *CreateNewSUnit(SDNode *N) { - SUnit *NewNode = NewSUnit(N); - return NewNode; - } - - /// CreateClone - Creates a new SUnit from an existing one. - SUnit *CreateClone(SUnit *N) { - SUnit *NewNode = Clone(N); - return NewNode; - } + /// forceUnitLatencies - The fast scheduler doesn't care about real latencies. + bool forceUnitLatencies() const { return true; } }; } // end anonymous namespace /// Schedule - Schedule the DAG using list scheduling. void ScheduleDAGFast::Schedule() { - DOUT << "********** List Scheduling **********\n"; + DEBUG(dbgs() << "********** List Scheduling **********\n"); NumLiveRegs = 0; - LiveRegDefs.resize(TRI->getNumRegs(), NULL); + LiveRegDefs.resize(TRI->getNumRegs(), NULL); LiveRegCycles.resize(TRI->getNumRegs(), 0); - // Build scheduling units. - BuildSchedUnits(); + // Build the scheduling graph. + BuildSchedGraph(NULL); DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) SUnits[su].dumpAll(this)); @@ -137,60 +136,70 @@ void ScheduleDAGFast::Schedule() { /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to /// the AvailableQueue if the count reaches zero. Also update its cycle bound. -void ScheduleDAGFast::ReleasePred(SUnit *SU, SUnit *PredSU, bool isChain) { - --PredSU->NumSuccsLeft; - +void ScheduleDAGFast::ReleasePred(SUnit *SU, SDep *PredEdge) { + SUnit *PredSU = PredEdge->getSUnit(); + #ifndef NDEBUG - if (PredSU->NumSuccsLeft < 0) { - cerr << "*** Scheduling failed! ***\n"; + if (PredSU->NumSuccsLeft == 0) { + dbgs() << "*** Scheduling failed! ***\n"; PredSU->dump(this); - cerr << " has been released too many times!\n"; - assert(0); + dbgs() << " has been released too many times!\n"; + llvm_unreachable(0); } #endif - - if (PredSU->NumSuccsLeft == 0) { + --PredSU->NumSuccsLeft; + + // 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 ScheduleDAGFast::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { - DOUT << "*** Scheduling [" << CurCycle << "]: "; - DEBUG(SU->dump(this)); - SU->Cycle = CurCycle; - +void ScheduleDAGFast::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 + // 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 ScheduleDAGFast::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { + DEBUG(dbgs() << "*** 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; } } } @@ -198,23 +207,10 @@ void ScheduleDAGFast::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { SU->isScheduled = true; } -/// AddPred - adds an edge from SUnit X to SUnit Y. -bool ScheduleDAGFast::AddPred(SUnit *Y, SUnit *X, bool isCtrl, bool isSpecial, - unsigned PhyReg, int Cost) { - return Y->addPred(X, isCtrl, isSpecial, PhyReg, Cost); -} - -/// RemovePred - This removes the specified node N from the predecessors of -/// the current node M. -bool ScheduleDAGFast::RemovePred(SUnit *M, SUnit *N, - bool isCtrl, bool isSpecial) { - return M->removePred(N, isCtrl, isSpecial); -} - /// CopyAndMoveSuccessors - Clone the specified node and move its scheduled /// successors to the newly created node. SUnit *ScheduleDAGFast::CopyAndMoveSuccessors(SUnit *SU) { - if (SU->getNode()->getFlaggedNode()) + if (SU->getNode()->getGluedNode()) return NULL; SDNode *N = SU->getNode(); @@ -224,16 +220,16 @@ SUnit *ScheduleDAGFast::CopyAndMoveSuccessors(SUnit *SU) { SUnit *NewSU; bool TryUnfold = false; for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) { - MVT VT = N->getValueType(i); - if (VT == MVT::Flag) + EVT VT = N->getValueType(i); + if (VT == MVT::Glue) return NULL; else if (VT == MVT::Other) TryUnfold = true; } for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { const SDValue &Op = N->getOperand(i); - MVT VT = Op.getNode()->getValueType(Op.getResNo()); - if (VT == MVT::Flag) + EVT VT = Op.getNode()->getValueType(Op.getResNo()); + if (VT == MVT::Glue) return NULL; } @@ -242,7 +238,7 @@ SUnit *ScheduleDAGFast::CopyAndMoveSuccessors(SUnit *SU) { if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes)) return NULL; - DOUT << "Unfolding SU # " << SU->NodeNum << "\n"; + DEBUG(dbgs() << "Unfolding SU # " << SU->NodeNum << "\n"); assert(NewNodes.size() == 2 && "Expected a load folding node!"); N = NewNodes[1]; @@ -254,22 +250,19 @@ SUnit *ScheduleDAGFast::CopyAndMoveSuccessors(SUnit *SU) { DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1), SDValue(LoadNode, 1)); - SUnit *NewSU = CreateNewSUnit(N); + SUnit *NewSU = newSUnit(N); assert(N->getNodeId() == -1 && "Node already inserted!"); N->setNodeId(NewSU->NodeNum); - - const TargetInstrDesc &TID = TII->get(N->getMachineOpcode()); - for (unsigned i = 0; i != TID.getNumOperands(); ++i) { - if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { + + const MCInstrDesc &MCID = TII->get(N->getMachineOpcode()); + for (unsigned i = 0; i != MCID.getNumOperands(); ++i) { + if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) { NewSU->isTwoAddress = true; break; } } - if (TID.isCommutable()) + if (MCID.isCommutable()) NewSU->isCommutable = true; - // FIXME: Calculate height / depth and propagate the changes? - NewSU->Depth = SU->Depth; - NewSU->Height = SU->Height; // LoadNode may already exist. This can happen when there is another // load from the same location and producing the same type of value @@ -280,72 +273,72 @@ SUnit *ScheduleDAGFast::CopyAndMoveSuccessors(SUnit *SU) { LoadSU = &SUnits[LoadNode->getNodeId()]; isNewLoad = false; } else { - LoadSU = CreateNewSUnit(LoadNode); + LoadSU = newSUnit(LoadNode); LoadNode->setNodeId(LoadSU->NodeNum); - - LoadSU->Depth = SU->Depth; - LoadSU->Height = SU->Height; } - SUnit *ChainPred = NULL; + SDep ChainPred; SmallVector ChainSuccs; SmallVector LoadPreds; SmallVector NodePreds; SmallVector 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)); + 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)); + 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->isSpecial)); + if (I->isCtrl()) + ChainSuccs.push_back(*I); else - NodeSuccs.push_back(SDep(I->Dep, I->Reg, I->Cost, - I->isCtrl, I->isSpecial)); + 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->isSpecial); + const SDep &Pred = LoadPreds[i]; + RemovePred(SU, Pred); if (isNewLoad) { - AddPred(LoadSU, Pred->Dep, Pred->isCtrl, Pred->isSpecial, - 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->isSpecial); - AddPred(NewSU, Pred->Dep, Pred->isCtrl, Pred->isSpecial, - 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->isSpecial); - AddPred(Succ->Dep, NewSU, Succ->isCtrl, Succ->isSpecial, - 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->isSpecial); + SDep D = ChainSuccs[i]; + SUnit *SuccDep = D.getSUnit(); + D.setSUnit(SU); + RemovePred(SuccDep, D); if (isNewLoad) { - AddPred(Succ->Dep, LoadSU, Succ->isCtrl, Succ->isSpecial, - Succ->Reg, Succ->Cost); + D.setSUnit(LoadSU); + AddPred(SuccDep, D); } - } + } if (isNewLoad) { - AddPred(NewSU, LoadSU, false, false); + SDep D(LoadSU, SDep::Barrier); + D.setLatency(LoadSU->Latency); + AddPred(NewSU, D); } ++NumUnfolds; @@ -357,90 +350,92 @@ SUnit *ScheduleDAGFast::CopyAndMoveSuccessors(SUnit *SU) { SU = NewSU; } - DOUT << "Duplicating SU # " << SU->NodeNum << "\n"; - NewSU = CreateClone(SU); + DEBUG(dbgs() << "Duplicating SU # " << SU->NodeNum << "\n"); + NewSU = Clone(SU); // New SUnit has the exact same predecessors. for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); I != E; ++I) - if (!I->isSpecial) { - 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, 4> DelDeps; + SmallVector, 4> DelDeps; for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); I != E; ++I) { - if (I->isSpecial) + 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); ++NumDups; return NewSU; } -/// InsertCCCopiesAndMoveSuccs - Insert expensive cross register class copies -/// and move all scheduled successors of the given SUnit to the last copy. -void ScheduleDAGFast::InsertCCCopiesAndMoveSuccs(SUnit *SU, unsigned Reg, +/// InsertCopiesAndMoveSuccs - Insert register copies and move all +/// scheduled successors of the given SUnit to the last copy. +void ScheduleDAGFast::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg, const TargetRegisterClass *DestRC, const TargetRegisterClass *SrcRC, SmallVector &Copies) { - SUnit *CopyFromSU = CreateNewSUnit(NULL); + SUnit *CopyFromSU = newSUnit(static_cast(NULL)); CopyFromSU->CopySrcRC = SrcRC; CopyFromSU->CopyDstRC = DestRC; - SUnit *CopyToSU = CreateNewSUnit(NULL); + SUnit *CopyToSU = newSUnit(static_cast(NULL)); CopyToSU->CopySrcRC = DestRC; CopyToSU->CopyDstRC = SrcRC; // Only copy scheduled successors. Cut them from old node's successor // list and move them over. - SmallVector, 4> DelDeps; + SmallVector, 4> DelDeps; for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); I != E; ++I) { - if (I->isSpecial) + if (I->isArtificial()) continue; - if (I->Dep->isScheduled) { - 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); + RemovePred(DelDeps[i].first, DelDeps[i].second); } - - AddPred(CopyFromSU, SU, false, false, Reg, -1); - AddPred(CopyToSU, CopyFromSU, false, false, Reg, 1); + SDep FromDep(SU, SDep::Data, Reg); + FromDep.setLatency(SU->Latency); + AddPred(CopyFromSU, FromDep); + SDep ToDep(CopyFromSU, SDep::Data, 0); + ToDep.setLatency(CopyFromSU->Latency); + AddPred(CopyToSU, ToDep); Copies.push_back(CopyFromSU); Copies.push_back(CopyToSU); - ++NumCCCopies; + ++NumPRCopies; } /// getPhysicalRegisterVT - Returns the ValueType of the physical register /// definition of the specified node. /// FIXME: Move to SelectionDAG? -static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg, +static EVT getPhysicalRegisterVT(SDNode *N, unsigned Reg, const TargetInstrInfo *TII) { - const TargetInstrDesc &TID = TII->get(N->getMachineOpcode()); - assert(TID.ImplicitDefs && "Physical reg def must be in implicit def list!"); - unsigned NumRes = TID.getNumDefs(); - for (const unsigned *ImpDef = TID.getImplicitDefs(); *ImpDef; ++ImpDef) { + const MCInstrDesc &MCID = TII->get(N->getMachineOpcode()); + assert(MCID.ImplicitDefs && "Physical reg def must be in implicit def list!"); + unsigned NumRes = MCID.getNumDefs(); + for (const uint16_t *ImpDef = MCID.getImplicitDefs(); *ImpDef; ++ImpDef) { if (Reg == *ImpDef) break; ++NumRes; @@ -448,6 +443,25 @@ static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg, return N->getValueType(NumRes); } +/// CheckForLiveRegDef - Return true and update live register vector if the +/// specified register def of the specified SUnit clobbers any "live" registers. +static bool CheckForLiveRegDef(SUnit *SU, unsigned Reg, + std::vector &LiveRegDefs, + SmallSet &RegAdded, + SmallVector &LRegs, + const TargetRegisterInfo *TRI) { + bool Added = false; + for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { + if (LiveRegDefs[*AI] && LiveRegDefs[*AI] != SU) { + if (RegAdded.insert(*AI)) { + LRegs.push_back(*AI); + Added = true; + } + } + } + return Added; +} + /// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay /// scheduling of the given node to satisfy live physical register dependencies. /// If the specific node is the last one that's available to schedule, do @@ -461,38 +475,46 @@ bool ScheduleDAGFast::DelayForLiveRegsBottomUp(SUnit *SU, // 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 (RegAdded.insert(Reg)) - LRegs.push_back(Reg); - } - for (const unsigned *Alias = TRI->getAliasSet(Reg); - *Alias; ++Alias) - if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != I->Dep) { - if (RegAdded.insert(*Alias)) - LRegs.push_back(*Alias); - } + if (I->isAssignedRegDep()) { + CheckForLiveRegDef(I->getSUnit(), I->getReg(), LiveRegDefs, + RegAdded, LRegs, TRI); } } - for (SDNode *Node = SU->getNode(); Node; Node = Node->getFlaggedNode()) { + for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode()) { + if (Node->getOpcode() == ISD::INLINEASM) { + // Inline asm can clobber physical defs. + unsigned NumOps = Node->getNumOperands(); + if (Node->getOperand(NumOps-1).getValueType() == MVT::Glue) + --NumOps; // Ignore the glue operand. + + for (unsigned i = InlineAsm::Op_FirstOperand; i != NumOps;) { + unsigned Flags = + cast(Node->getOperand(i))->getZExtValue(); + unsigned NumVals = InlineAsm::getNumOperandRegisters(Flags); + + ++i; // Skip the ID value. + if (InlineAsm::isRegDefKind(Flags) || + InlineAsm::isRegDefEarlyClobberKind(Flags) || + InlineAsm::isClobberKind(Flags)) { + // Check for def of register or earlyclobber register. + for (; NumVals; --NumVals, ++i) { + unsigned Reg = cast(Node->getOperand(i))->getReg(); + if (TargetRegisterInfo::isPhysicalRegister(Reg)) + CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI); + } + } else + i += NumVals; + } + continue; + } if (!Node->isMachineOpcode()) continue; - const TargetInstrDesc &TID = TII->get(Node->getMachineOpcode()); - if (!TID.ImplicitDefs) + const MCInstrDesc &MCID = TII->get(Node->getMachineOpcode()); + if (!MCID.ImplicitDefs) continue; - for (const unsigned *Reg = TID.ImplicitDefs; *Reg; ++Reg) { - if (LiveRegDefs[*Reg] && LiveRegDefs[*Reg] != SU) { - if (RegAdded.insert(*Reg)) - LRegs.push_back(*Reg); - } - for (const unsigned *Alias = TRI->getAliasSet(*Reg); - *Alias; ++Alias) - if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != SU) { - if (RegAdded.insert(*Alias)) - LRegs.push_back(*Alias); - } + for (const uint16_t *Reg = MCID.getImplicitDefs(); *Reg; ++Reg) { + CheckForLiveRegDef(SU, *Reg, LiveRegDefs, RegAdded, LRegs, TRI); } } return !LRegs.empty(); @@ -503,6 +525,10 @@ bool ScheduleDAGFast::DelayForLiveRegsBottomUp(SUnit *SU, /// schedulers. void ScheduleDAGFast::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()]; @@ -545,36 +571,45 @@ void ScheduleDAGFast::ListScheduleBottomUp() { assert(LRegs.size() == 1 && "Can't handle this yet!"); unsigned Reg = LRegs[0]; SUnit *LRDef = LiveRegDefs[Reg]; - SUnit *NewDef = CopyAndMoveSuccessors(LRDef); + EVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII); + const TargetRegisterClass *RC = + TRI->getMinimalPhysRegClass(Reg, VT); + const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC); + + // If cross copy register class is the same as RC, then it must be + // possible copy the value directly. Do not try duplicate the def. + // If cross copy register class is not the same as RC, then it's + // possible to copy the value but it require cross register class copies + // and it is expensive. + // If cross copy register class is null, then it's not possible to copy + // the value at all. + SUnit *NewDef = 0; + if (DestRC != RC) { + NewDef = CopyAndMoveSuccessors(LRDef); + if (!DestRC && !NewDef) + report_fatal_error("Can't handle live physical " + "register dependency!"); + } 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 Copies; - InsertCCCopiesAndMoveSuccs(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); + InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies); + DEBUG(dbgs() << "Adding an edge from SU # " << TrySU->NodeNum + << " to SU #" << Copies.front()->NodeNum << "\n"); + AddPred(TrySU, SDep(Copies.front(), SDep::Artificial)); NewDef = Copies.back(); } - DOUT << "Adding an edge from SU # " << NewDef->NodeNum - << " to SU #" << TrySU->NodeNum << "\n"; + DEBUG(dbgs() << "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::Artificial)); TrySU->isAvailable = false; CurSU = NewDef; } if (!CurSU) { - assert(false && "Unable to resolve live physical register dependencies!"); - abort(); + llvm_unreachable("Unable to resolve live physical register dependencies!"); } } @@ -587,60 +622,178 @@ void ScheduleDAGFast::ListScheduleBottomUp() { } NotReady.clear(); - if (!CurSU) - Sequence.push_back(0); - else { + if (CurSU) ScheduleNodeBottomUp(CurSU, CurCycle); - Sequence.push_back(CurSU); - } ++CurCycle; } - // Reverse the order if it is bottom up. + // Reverse the order since it is bottom up. std::reverse(Sequence.begin(), Sequence.end()); - - + #ifndef NDEBUG - // Verify that all SUnits were scheduled. - bool AnyNotSched = false; - unsigned DeadNodes = 0; - unsigned Noops = 0; - for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { - if (!SUnits[i].isScheduled) { - if (SUnits[i].NumPreds == 0 && SUnits[i].NumSuccs == 0) { - ++DeadNodes; + VerifyScheduledSequence(/*isBottomUp=*/true); +#endif +} + + +namespace { +//===----------------------------------------------------------------------===// +// ScheduleDAGLinearize - No scheduling scheduler, it simply linearize the +// DAG in topological order. +// IMPORTANT: this may not work for targets with phyreg dependency. +// +class ScheduleDAGLinearize : public ScheduleDAGSDNodes { +public: + ScheduleDAGLinearize(MachineFunction &mf) : ScheduleDAGSDNodes(mf) {} + + void Schedule(); + + MachineBasicBlock *EmitSchedule(MachineBasicBlock::iterator &InsertPos); + +private: + std::vector Sequence; + DenseMap GluedMap; // Cache glue to its user + + void ScheduleNode(SDNode *N); +}; +} // end anonymous namespace + +void ScheduleDAGLinearize::ScheduleNode(SDNode *N) { + if (N->getNodeId() != 0) + llvm_unreachable(0); + + if (!N->isMachineOpcode() && + (N->getOpcode() == ISD::EntryToken || isPassiveNode(N))) + // These nodes do not need to be translated into MIs. + return; + + DEBUG(dbgs() << "\n*** Scheduling: "); + DEBUG(N->dump(DAG)); + Sequence.push_back(N); + + unsigned NumOps = N->getNumOperands(); + if (unsigned NumLeft = NumOps) { + SDNode *GluedOpN = 0; + do { + const SDValue &Op = N->getOperand(NumLeft-1); + SDNode *OpN = Op.getNode(); + + if (NumLeft == NumOps && Op.getValueType() == MVT::Glue) { + // Schedule glue operand right above N. + GluedOpN = OpN; + assert(OpN->getNodeId() != 0 && "Glue operand not ready?"); + OpN->setNodeId(0); + ScheduleNode(OpN); continue; } - if (!AnyNotSched) - cerr << "*** List scheduling failed! ***\n"; - SUnits[i].dump(this); - cerr << "has not been scheduled!\n"; - AnyNotSched = true; - } - if (SUnits[i].NumSuccsLeft != 0) { - if (!AnyNotSched) - cerr << "*** List scheduling failed! ***\n"; - SUnits[i].dump(this); - cerr << "has successors left!\n"; - AnyNotSched = true; + + if (OpN == GluedOpN) + // Glue operand is already scheduled. + continue; + + DenseMap::iterator DI = GluedMap.find(OpN); + if (DI != GluedMap.end() && DI->second != N) + // Users of glues are counted against the glued users. + OpN = DI->second; + + unsigned Degree = OpN->getNodeId(); + assert(Degree > 0 && "Predecessor over-released!"); + OpN->setNodeId(--Degree); + if (Degree == 0) + ScheduleNode(OpN); + } while (--NumLeft); + } +} + +/// findGluedUser - Find the representative use of a glue value by walking +/// the use chain. +static SDNode *findGluedUser(SDNode *N) { + while (SDNode *Glued = N->getGluedUser()) + N = Glued; + return N; +} + +void ScheduleDAGLinearize::Schedule() { + DEBUG(dbgs() << "********** DAG Linearization **********\n"); + + SmallVector Glues; + unsigned DAGSize = 0; + for (SelectionDAG::allnodes_iterator I = DAG->allnodes_begin(), + E = DAG->allnodes_end(); I != E; ++I) { + SDNode *N = I; + + // Use node id to record degree. + unsigned Degree = N->use_size(); + N->setNodeId(Degree); + unsigned NumVals = N->getNumValues(); + if (NumVals && N->getValueType(NumVals-1) == MVT::Glue && + N->hasAnyUseOfValue(NumVals-1)) { + SDNode *User = findGluedUser(N); + if (User) { + Glues.push_back(N); + GluedMap.insert(std::make_pair(N, User)); + } } + + if (N->isMachineOpcode() || + (N->getOpcode() != ISD::EntryToken && !isPassiveNode(N))) + ++DAGSize; } - for (unsigned i = 0, e = Sequence.size(); i != e; ++i) - if (!Sequence[i]) - ++Noops; - assert(!AnyNotSched); - assert(Sequence.size() + DeadNodes - Noops == SUnits.size() && - "The number of nodes scheduled doesn't match the expected number!"); -#endif + + for (unsigned i = 0, e = Glues.size(); i != e; ++i) { + SDNode *Glue = Glues[i]; + SDNode *GUser = GluedMap[Glue]; + unsigned Degree = Glue->getNodeId(); + unsigned UDegree = GUser->getNodeId(); + + // Glue user must be scheduled together with the glue operand. So other + // users of the glue operand must be treated as its users. + SDNode *ImmGUser = Glue->getGluedUser(); + for (SDNode::use_iterator ui = Glue->use_begin(), ue = Glue->use_end(); + ui != ue; ++ui) + if (*ui == ImmGUser) + --Degree; + GUser->setNodeId(UDegree + Degree); + Glue->setNodeId(1); + } + + Sequence.reserve(DAGSize); + ScheduleNode(DAG->getRoot().getNode()); +} + +MachineBasicBlock* +ScheduleDAGLinearize::EmitSchedule(MachineBasicBlock::iterator &InsertPos) { + InstrEmitter Emitter(BB, InsertPos); + DenseMap VRBaseMap; + + DEBUG({ + dbgs() << "\n*** Final schedule ***\n"; + }); + + // FIXME: Handle dbg_values. + unsigned NumNodes = Sequence.size(); + for (unsigned i = 0; i != NumNodes; ++i) { + SDNode *N = Sequence[NumNodes-i-1]; + DEBUG(N->dump(DAG)); + Emitter.EmitNode(N, false, false, VRBaseMap); + } + + DEBUG(dbgs() << '\n'); + + InsertPos = Emitter.getInsertPos(); + return Emitter.getBlock(); } //===----------------------------------------------------------------------===// // Public Constructor Functions //===----------------------------------------------------------------------===// -llvm::ScheduleDAG* llvm::createFastDAGScheduler(SelectionDAGISel *IS, - SelectionDAG *DAG, - const TargetMachine *TM, - MachineBasicBlock *BB, bool) { - return new ScheduleDAGFast(DAG, BB, *TM); +llvm::ScheduleDAGSDNodes * +llvm::createFastDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) { + return new ScheduleDAGFast(*IS->MF); +} + +llvm::ScheduleDAGSDNodes * +llvm::createDAGLinearizer(SelectionDAGISel *IS, CodeGenOpt::Level) { + return new ScheduleDAGLinearize(*IS->MF); }