diff options
Diffstat (limited to 'lib')
19 files changed, 1014 insertions, 826 deletions
diff --git a/lib/CodeGen/CMakeLists.txt b/lib/CodeGen/CMakeLists.txt index a7aad33..fed3237 100644 --- a/lib/CodeGen/CMakeLists.txt +++ b/lib/CodeGen/CMakeLists.txt @@ -8,6 +8,7 @@ add_llvm_library(LLVMCodeGen IfConversion.cpp IntrinsicLowering.cpp LLVMTargetMachine.cpp + LatencyPriorityQueue.cpp LiveInterval.cpp LiveIntervalAnalysis.cpp LiveStackAnalysis.cpp @@ -40,6 +41,10 @@ add_llvm_library(LLVMCodeGen RegAllocSimple.cpp RegisterCoalescer.cpp RegisterScavenging.cpp + ScheduleDAG.cpp + ScheduleDAGEmit.cpp + ScheduleDAGInstrs.cpp + ScheduleDAGPrinter.cpp ShadowStackGC.cpp SimpleRegisterCoalescing.cpp StackProtector.cpp diff --git a/lib/CodeGen/SelectionDAG/LatencyPriorityQueue.cpp b/lib/CodeGen/LatencyPriorityQueue.cpp index ae73f20..70b6574 100644 --- a/lib/CodeGen/SelectionDAG/LatencyPriorityQueue.cpp +++ b/lib/CodeGen/LatencyPriorityQueue.cpp @@ -14,7 +14,7 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "scheduler" -#include "LatencyPriorityQueue.h" +#include "llvm/CodeGen/LatencyPriorityQueue.h" #include "llvm/Support/Debug.h" using namespace llvm; diff --git a/lib/CodeGen/PostRASchedulerList.cpp b/lib/CodeGen/PostRASchedulerList.cpp index 41981d3..3a31eaa 100644 --- a/lib/CodeGen/PostRASchedulerList.cpp +++ b/lib/CodeGen/PostRASchedulerList.cpp @@ -20,47 +20,234 @@ #define DEBUG_TYPE "post-RA-sched" #include "llvm/CodeGen/Passes.h" +#include "llvm/CodeGen/ScheduleDAGInstrs.h" +#include "llvm/CodeGen/LatencyPriorityQueue.h" +#include "llvm/CodeGen/SchedulerRegistry.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" +#include "llvm/ADT/Statistic.h" using namespace llvm; +STATISTIC(NumStalls, "Number of pipeline stalls"); + namespace { - class VISIBILITY_HIDDEN SchedulePostRATDList : public MachineFunctionPass { + class VISIBILITY_HIDDEN PostRAScheduler : public MachineFunctionPass { public: static char ID; - SchedulePostRATDList() : MachineFunctionPass(&ID) {} + PostRAScheduler() : MachineFunctionPass(&ID) {} + private: + MachineFunction *MF; + const TargetMachine *TM; + public: + const char *getPassName() const { + return "Post RA top-down list latency scheduler (STUB)"; + } + + bool runOnMachineFunction(MachineFunction &Fn); + }; + char PostRAScheduler::ID = 0; + + class VISIBILITY_HIDDEN SchedulePostRATDList : public ScheduleDAGInstrs { + public: + SchedulePostRATDList(MachineBasicBlock *mbb, const TargetMachine &tm) + : ScheduleDAGInstrs(mbb, tm) {} private: MachineFunction *MF; const TargetMachine *TM; + + /// AvailableQueue - The priority queue to use for the available SUnits. + /// + LatencyPriorityQueue AvailableQueue; + + /// 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. + std::vector<SUnit*> PendingQueue; + public: const char *getPassName() const { return "Post RA top-down list latency scheduler (STUB)"; } bool runOnMachineFunction(MachineFunction &Fn); + + void Schedule(); + + private: + void ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain); + void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle); + void ListScheduleTopDown(); }; - char SchedulePostRATDList::ID = 0; } -bool SchedulePostRATDList::runOnMachineFunction(MachineFunction &Fn) { - DOUT << "SchedulePostRATDList\n"; +bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { + DOUT << "PostRAScheduler\n"; MF = &Fn; TM = &MF->getTarget(); // Loop over all of the basic blocks for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); - MBB != MBBe; ++MBB) - ; + MBB != MBBe; ++MBB) { + + SchedulePostRATDList Scheduler(MBB, *TM); + + Scheduler.Run(); + + Scheduler.EmitSchedule(); + } return true; } +/// Schedule - Schedule the DAG using list scheduling. +void SchedulePostRATDList::Schedule() { + DOUT << "********** List Scheduling **********\n"; + + // Build scheduling units. + BuildSchedUnits(); + + AvailableQueue.initNodes(SUnits); + + ListScheduleTopDown(); + + AvailableQueue.releaseState(); +} + +//===----------------------------------------------------------------------===// +// Top-Down Scheduling +//===----------------------------------------------------------------------===// + +/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to +/// the PendingQueue if the count reaches zero. Also update its cycle bound. +void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain) { + --SuccSU->NumPredsLeft; + +#ifndef NDEBUG + if (SuccSU->NumPredsLeft < 0) { + cerr << "*** Scheduling failed! ***\n"; + SuccSU->dump(this); + cerr << " has been released too many times!\n"; + assert(0); + } +#endif + + // 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. + // 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) { + PendingQueue.push_back(SuccSU); + } +} + +/// 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. +void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { + DOUT << "*** 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); + + SU->isScheduled = true; + AvailableQueue.ScheduledNode(SU); +} + +/// ListScheduleTopDown - The main loop of list scheduling for top-down +/// schedulers. +void SchedulePostRATDList::ListScheduleTopDown() { + unsigned CurCycle = 0; + + // 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 = true; + } + } + + // While Available queue is not empty, grab the node with the highest + // priority. If it is not ready put it back. Schedule the node. + 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. + for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) { + if (PendingQueue[i]->CycleBound == 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?"); + } + } + + // If there are no instructions available, don't try to issue anything, and + // don't advance the hazard recognizer. + if (AvailableQueue.empty()) { + ++CurCycle; + continue; + } + + SUnit *FoundSUnit = AvailableQueue.pop(); + + // If we found a node to schedule, do it now. + if (FoundSUnit) { + ScheduleNodeTopDown(FoundSUnit, CurCycle); + + // If this is a pseudo-op node, we don't want to increment the current + // cycle. + if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops! + ++CurCycle; + } else { + // 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"; + ++NumStalls; + ++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); +#endif +} //===----------------------------------------------------------------------===// // Public Constructor Functions //===----------------------------------------------------------------------===// FunctionPass *llvm::createPostRAScheduler() { - return new SchedulePostRATDList(); + return new PostRAScheduler(); } diff --git a/lib/CodeGen/ScheduleDAG.cpp b/lib/CodeGen/ScheduleDAG.cpp new file mode 100644 index 0000000..e6a8d13 --- /dev/null +++ b/lib/CodeGen/ScheduleDAG.cpp @@ -0,0 +1,210 @@ +//===---- ScheduleDAG.cpp - Implement the ScheduleDAG class ---------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This implements the ScheduleDAG class, which is a base class used by +// scheduling implementation classes. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "pre-RA-sched" +#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Support/Debug.h" +using namespace llvm; + +ScheduleDAG::ScheduleDAG(SelectionDAG *dag, MachineBasicBlock *bb, + const TargetMachine &tm) + : DAG(dag), BB(bb), TM(tm), MRI(BB->getParent()->getRegInfo()) { + TII = TM.getInstrInfo(); + MF = BB->getParent(); + TRI = TM.getRegisterInfo(); + TLI = TM.getTargetLowering(); + ConstPool = MF->getConstantPool(); +} + +ScheduleDAG::~ScheduleDAG() {} + +/// CalculateDepths - compute depths using algorithms for the longest +/// paths in the DAG +void ScheduleDAG::CalculateDepths() { + unsigned DAGSize = SUnits.size(); + std::vector<SUnit*> WorkList; + WorkList.reserve(DAGSize); + + // Initialize the data structures + for (unsigned i = 0, e = DAGSize; i != e; ++i) { + SUnit *SU = &SUnits[i]; + unsigned Degree = SU->Preds.size(); + // Temporarily use the Depth field as scratch space for the degree count. + SU->Depth = Degree; + + // Is it a node without dependencies? + if (Degree == 0) { + assert(SU->Preds.empty() && "SUnit should have no predecessors"); + // Collect leaf nodes + WorkList.push_back(SU); + } + } + + // Process nodes in the topological order + while (!WorkList.empty()) { + SUnit *SU = WorkList.back(); + WorkList.pop_back(); + unsigned SUDepth = 0; + + // Use dynamic programming: + // When current node is being processed, all of its dependencies + // are already processed. + // So, just iterate over all predecessors and take the longest path + for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); + I != E; ++I) { + unsigned PredDepth = I->Dep->Depth; + if (PredDepth+1 > SUDepth) { + SUDepth = PredDepth + 1; + } + } + + SU->Depth = SUDepth; + + // Update degrees of all nodes depending on current SUnit + for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); + I != E; ++I) { + SUnit *SU = I->Dep; + if (!--SU->Depth) + // If all dependencies of the node are processed already, + // then the longest path for the node can be computed now + WorkList.push_back(SU); + } + } +} + +/// CalculateHeights - compute heights using algorithms for the longest +/// paths in the DAG +void ScheduleDAG::CalculateHeights() { + unsigned DAGSize = SUnits.size(); + std::vector<SUnit*> WorkList; + WorkList.reserve(DAGSize); + + // Initialize the data structures + for (unsigned i = 0, e = DAGSize; i != e; ++i) { + SUnit *SU = &SUnits[i]; + unsigned Degree = SU->Succs.size(); + // Temporarily use the Height field as scratch space for the degree count. + SU->Height = Degree; + + // Is it a node without dependencies? + if (Degree == 0) { + assert(SU->Succs.empty() && "Something wrong"); + assert(WorkList.empty() && "Should be empty"); + // Collect leaf nodes + WorkList.push_back(SU); + } + } + + // Process nodes in the topological order + while (!WorkList.empty()) { + SUnit *SU = WorkList.back(); + WorkList.pop_back(); + unsigned SUHeight = 0; + + // Use dynamic programming: + // When current node is being processed, all of its dependencies + // are already processed. + // So, just iterate over all successors and take the longest path + for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); + I != E; ++I) { + unsigned SuccHeight = I->Dep->Height; + if (SuccHeight+1 > SUHeight) { + SUHeight = SuccHeight + 1; + } + } + + SU->Height = SUHeight; + + // Update degrees of all nodes depending on current SUnit + for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); + I != E; ++I) { + SUnit *SU = I->Dep; + if (!--SU->Height) + // If all dependencies of the node are processed already, + // then the longest path for the node can be computed now + WorkList.push_back(SU); + } + } +} + +/// dump - dump the schedule. +void ScheduleDAG::dumpSchedule() const { + for (unsigned i = 0, e = Sequence.size(); i != e; i++) { + if (SUnit *SU = Sequence[i]) + SU->dump(this); + else + cerr << "**** NOOP ****\n"; + } +} + + +/// Run - perform scheduling. +/// +void ScheduleDAG::Run() { + Schedule(); + + DOUT << "*** Final schedule ***\n"; + DEBUG(dumpSchedule()); + DOUT << "\n"; +} + +/// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or +/// a group of nodes flagged together. +void SUnit::dump(const ScheduleDAG *G) const { + cerr << "SU(" << NodeNum << "): "; + G->dumpNode(this); +} + +void SUnit::dumpAll(const ScheduleDAG *G) const { + dump(G); + + cerr << " # preds left : " << NumPredsLeft << "\n"; + cerr << " # succs left : " << NumSuccsLeft << "\n"; + cerr << " Latency : " << Latency << "\n"; + cerr << " Depth : " << Depth << "\n"; + cerr << " Height : " << Height << "\n"; + + if (Preds.size() != 0) { + cerr << " Predecessors:\n"; + for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end(); + I != E; ++I) { + if (I->isCtrl) + cerr << " ch #"; + else + cerr << " val #"; + cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")"; + if (I->isSpecial) + cerr << " *"; + cerr << "\n"; + } + } + if (Succs.size() != 0) { + cerr << " Successors:\n"; + for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end(); + I != E; ++I) { + if (I->isCtrl) + cerr << " ch #"; + else + cerr << " val #"; + cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")"; + if (I->isSpecial) + cerr << " *"; + cerr << "\n"; + } + } + cerr << "\n"; +} diff --git a/lib/CodeGen/ScheduleDAGEmit.cpp b/lib/CodeGen/ScheduleDAGEmit.cpp new file mode 100644 index 0000000..ce3283d --- /dev/null +++ b/lib/CodeGen/ScheduleDAGEmit.cpp @@ -0,0 +1,72 @@ +//===---- ScheduleDAGEmit.cpp - Emit routines for the ScheduleDAG class ---===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This implements the Emit routines for the ScheduleDAG class, which creates +// MachineInstrs according to the computed schedule. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "pre-RA-sched" +#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/MachineConstantPool.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/Target/TargetData.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetLowering.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/MathExtras.h" +using namespace llvm; + +void ScheduleDAG::AddMemOperand(MachineInstr *MI, const MachineMemOperand &MO) { + MI->addMemOperand(*MF, MO); +} + +void ScheduleDAG::EmitNoop() { + TII->insertNoop(*BB, BB->end()); +} + +void ScheduleDAG::EmitCrossRCCopy(SUnit *SU, + DenseMap<SUnit*, unsigned> &VRBaseMap) { + 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->CopyDstRC) { + // Copy to physical register. + DenseMap<SUnit*, unsigned>::iterator VRI = VRBaseMap.find(I->Dep); + assert(VRI != VRBaseMap.end() && "Node emitted out of order - late"); + // Find the destination physical register. + unsigned Reg = 0; + for (SUnit::const_succ_iterator II = SU->Succs.begin(), + EE = SU->Succs.end(); II != EE; ++II) { + if (I->Reg) { + Reg = I->Reg; + break; + } + } + assert(I->Reg && "Unknown physical register!"); + TII->copyRegToReg(*BB, BB->end(), Reg, VRI->second, + SU->CopyDstRC, SU->CopySrcRC); + } else { + // Copy from physical register. + assert(I->Reg && "Unknown physical register!"); + unsigned VRBase = MRI.createVirtualRegister(SU->CopyDstRC); + bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase)).second; + isNew = isNew; // Silence compiler warning. + assert(isNew && "Node emitted out of order - early"); + TII->copyRegToReg(*BB, BB->end(), VRBase, I->Reg, + SU->CopyDstRC, SU->CopySrcRC); + } + break; + } +} diff --git a/lib/CodeGen/ScheduleDAGInstrs.cpp b/lib/CodeGen/ScheduleDAGInstrs.cpp new file mode 100644 index 0000000..72008c9 --- /dev/null +++ b/lib/CodeGen/ScheduleDAGInstrs.cpp @@ -0,0 +1,135 @@ +//===---- ScheduleDAG.cpp - Implement the ScheduleDAG class ---------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This implements the ScheduleDAG class, which is a base class used by +// scheduling implementation classes. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "sched-instrs" +#include "llvm/CodeGen/ScheduleDAGInstrs.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +using namespace llvm; + +ScheduleDAGInstrs::ScheduleDAGInstrs(MachineBasicBlock *bb, + const TargetMachine &tm) + : ScheduleDAG(0, bb, tm) {} + +void ScheduleDAGInstrs::BuildSchedUnits() { + SUnits.clear(); + SUnits.reserve(BB->size()); + + std::vector<SUnit *> PendingLoads; + SUnit *Terminator = 0; + SUnit *Chain = 0; + SUnit *Defs[TargetRegisterInfo::FirstVirtualRegister] = {}; + std::vector<SUnit *> Uses[TargetRegisterInfo::FirstVirtualRegister] = {}; + int Cost = 1; // FIXME + + for (MachineBasicBlock::iterator MII = BB->end(), MIE = BB->begin(); + MII != MIE; --MII) { + MachineInstr *MI = prior(MII); + SUnit *SU = NewSUnit(MI); + + for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) { + const MachineOperand &MO = MI->getOperand(j); + if (!MO.isReg()) continue; + unsigned Reg = MO.getReg(); + if (Reg == 0) continue; + + assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!"); + std::vector<SUnit *> &UseList = Uses[Reg]; + SUnit *&Def = Defs[Reg]; + // Optionally add output and anti dependences + if (Def && Def != SU) + Def->addPred(SU, /*isCtrl=*/true, /*isSpecial=*/false, + /*PhyReg=*/Reg, Cost); + for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { + SUnit *&Def = Defs[*Alias]; + if (Def && Def != SU) + Def->addPred(SU, /*isCtrl=*/true, /*isSpecial=*/false, + /*PhyReg=*/*Alias, Cost); + } + + if (MO.isDef()) { + // Add any data dependencies. + for (unsigned i = 0, e = UseList.size(); i != e; ++i) + if (UseList[i] != SU) + UseList[i]->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false, + /*PhysReg=*/Reg, Cost); + for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { + std::vector<SUnit *> &UseList = Uses[*Alias]; + for (unsigned i = 0, e = UseList.size(); i != e; ++i) + if (UseList[i] != SU) + UseList[i]->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false, + /*PhysReg=*/*Alias, Cost); + } + + UseList.clear(); + Def = SU; + } else { + UseList.push_back(SU); + } + } + bool False = false; + bool True = true; + if (!MI->isSafeToMove(TII, False)) { + if (Chain) + Chain->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false); + for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) + PendingLoads[k]->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false); + PendingLoads.clear(); + Chain = SU; + } else if (!MI->isSafeToMove(TII, True)) { + if (Chain) + Chain->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false); + PendingLoads.push_back(SU); + } + if (Terminator && SU->Succs.empty()) + Terminator->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false); + if (MI->getDesc().isTerminator()) + Terminator = SU; + } +} + +void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const { + SU->getInstr()->dump(); +} + +std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const { + std::string s; + raw_string_ostream oss(s); + SU->getInstr()->print(oss); + return oss.str(); +} + +// EmitSchedule - Emit the machine code in scheduled order. +MachineBasicBlock *ScheduleDAGInstrs::EmitSchedule() { + // For MachineInstr-based scheduling, we're rescheduling the instructions in + // the block, so start by removing them from the block. + while (!BB->empty()) + BB->remove(BB->begin()); + + for (unsigned i = 0, e = Sequence.size(); i != e; i++) { + SUnit *SU = Sequence[i]; + if (!SU) { + // Null SUnit* is a noop. + EmitNoop(); + continue; + } + + BB->push_back(SU->getInstr()); + } + + return BB; +} diff --git a/lib/CodeGen/ScheduleDAGPrinter.cpp b/lib/CodeGen/ScheduleDAGPrinter.cpp new file mode 100644 index 0000000..b5d030c --- /dev/null +++ b/lib/CodeGen/ScheduleDAGPrinter.cpp @@ -0,0 +1,93 @@ +//===-- ScheduleDAGPrinter.cpp - Implement ScheduleDAG::viewGraph() -------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This implements the ScheduleDAG::viewGraph method. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Constants.h" +#include "llvm/Function.h" +#include "llvm/Assembly/Writer.h" +#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/MachineConstantPool.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineModuleInfo.h" +#include "llvm/CodeGen/PseudoSourceValue.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/GraphWriter.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/StringExtras.h" +#include "llvm/Config/config.h" +#include <fstream> +using namespace llvm; + +namespace llvm { + template<> + struct DOTGraphTraits<ScheduleDAG*> : public DefaultDOTGraphTraits { + static std::string getGraphName(const ScheduleDAG *G) { + return G->MF->getFunction()->getName(); + } + + static bool renderGraphFromBottomUp() { + return true; + } + + static bool hasNodeAddressLabel(const SUnit *Node, + const ScheduleDAG *Graph) { + return true; + } + + /// If you want to override the dot attributes printed for a particular + /// edge, override this method. + template<typename EdgeIter> + static std::string getEdgeAttributes(const void *Node, EdgeIter EI) { + if (EI.isSpecialDep()) + return "color=cyan,style=dashed"; + if (EI.isCtrlDep()) + return "color=blue,style=dashed"; + return ""; + } + + + static std::string getNodeLabel(const SUnit *Node, + const ScheduleDAG *Graph); + static std::string getNodeAttributes(const SUnit *N, + const ScheduleDAG *Graph) { + return "shape=Mrecord"; + } + + static void addCustomGraphFeatures(ScheduleDAG *G, + GraphWriter<ScheduleDAG*> &GW) { + return G->addCustomGraphFeatures(GW); + } + }; +} + +std::string DOTGraphTraits<ScheduleDAG*>::getNodeLabel(const SUnit *SU, + const ScheduleDAG *G) { + return G->getGraphNodeLabel(SU); +} + +/// viewGraph - Pop up a ghostview window with the reachable parts of the DAG +/// rendered using 'dot'. +/// +void ScheduleDAG::viewGraph() { +// This code is only for debugging! +#ifndef NDEBUG + ViewGraph(this, "dag." + MF->getFunction()->getName(), + "Scheduling-Units Graph for " + MF->getFunction()->getName() + ':' + + BB->getBasicBlock()->getName()); +#else + cerr << "ScheduleDAG::viewGraph is only available in debug builds on " + << "systems with Graphviz or gv!\n"; +#endif // NDEBUG +} diff --git a/lib/CodeGen/SelectionDAG/CMakeLists.txt b/lib/CodeGen/SelectionDAG/CMakeLists.txt index a3654c2..186e3d1 100644 --- a/lib/CodeGen/SelectionDAG/CMakeLists.txt +++ b/lib/CodeGen/SelectionDAG/CMakeLists.txt @@ -2,15 +2,14 @@ add_llvm_library(LLVMSelectionDAG CallingConvLower.cpp DAGCombiner.cpp FastISel.cpp - LatencyPriorityQueue.cpp LegalizeDAG.cpp LegalizeFloatTypes.cpp LegalizeIntegerTypes.cpp LegalizeTypes.cpp LegalizeTypesGeneric.cpp LegalizeVectorTypes.cpp - ScheduleDAG.cpp - ScheduleDAGEmit.cpp + ScheduleDAGSDNodes.cpp + ScheduleDAGSDNodesEmit.cpp ScheduleDAGFast.cpp ScheduleDAGList.cpp ScheduleDAGRRList.cpp diff --git a/lib/CodeGen/SelectionDAG/LatencyPriorityQueue.h b/lib/CodeGen/SelectionDAG/LatencyPriorityQueue.h deleted file mode 100644 index 5b2b02b..0000000 --- a/lib/CodeGen/SelectionDAG/LatencyPriorityQueue.h +++ /dev/null @@ -1,124 +0,0 @@ -//===---- LatencyPriorityQueue.h - A latency-oriented priority queue ------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file declares the LatencyPriorityQueue class, which is a -// SchedulingPriorityQueue that schedules using latency information to -// reduce the length of the critical path through the basic block. -// -//===----------------------------------------------------------------------===// - -#ifndef LATENCY_PRIORITY_QUEUE_H -#define LATENCY_PRIORITY_QUEUE_H - -#include "llvm/CodeGen/ScheduleDAG.h" -#include "llvm/ADT/PriorityQueue.h" - -namespace llvm { - class LatencyPriorityQueue; - - /// Sorting functions for the Available queue. - struct latency_sort : public std::binary_function<SUnit*, SUnit*, bool> { - LatencyPriorityQueue *PQ; - explicit latency_sort(LatencyPriorityQueue *pq) : PQ(pq) {} - - bool operator()(const SUnit* left, const SUnit* right) const; - }; - - class LatencyPriorityQueue : public SchedulingPriorityQueue { - // SUnits - The SUnits for the current graph. - std::vector<SUnit> *SUnits; - - // Latencies - The latency (max of latency from this node to the bb exit) - // for each node. - std::vector<int> Latencies; - - /// NumNodesSolelyBlocking - This vector contains, for every node in the - /// Queue, the number of nodes that the node is the sole unscheduled - /// predecessor for. This is used as a tie-breaker heuristic for better - /// mobility. - std::vector<unsigned> NumNodesSolelyBlocking; - - PriorityQueue<SUnit*, std::vector<SUnit*>, latency_sort> Queue; - public: - LatencyPriorityQueue() : Queue(latency_sort(this)) { - } - - void initNodes(std::vector<SUnit> &sunits) { - SUnits = &sunits; - // Calculate node priorities. - CalculatePriorities(); - } - - void addNode(const SUnit *SU) { - Latencies.resize(SUnits->size(), -1); - NumNodesSolelyBlocking.resize(SUnits->size(), 0); - CalcLatency(*SU); - } - - void updateNode(const SUnit *SU) { - Latencies[SU->NodeNum] = -1; - CalcLatency(*SU); - } - - void releaseState() { - SUnits = 0; - Latencies.clear(); - } - - unsigned getLatency(unsigned NodeNum) const { - assert(NodeNum < Latencies.size()); - return Latencies[NodeNum]; - } - - unsigned getNumSolelyBlockNodes(unsigned NodeNum) const { - assert(NodeNum < NumNodesSolelyBlocking.size()); - return NumNodesSolelyBlocking[NodeNum]; - } - - unsigned size() const { return Queue.size(); } - - bool empty() const { return Queue.empty(); } - - virtual void push(SUnit *U) { - push_impl(U); - } - void push_impl(SUnit *U); - - void push_all(const std::vector<SUnit *> &Nodes) { - for (unsigned i = 0, e = Nodes.size(); i != e; ++i) - push_impl(Nodes[i]); - } - - SUnit *pop() { - if (empty()) return NULL; - SUnit *V = Queue.top(); - Queue.pop(); - return V; - } - - void remove(SUnit *SU) { - assert(!Queue.empty() && "Not in queue!"); - Queue.erase_one(SU); - } - - // ScheduledNode - As nodes are scheduled, we look to see if there are any - // successor nodes that have a single unscheduled predecessor. If so, that - // single predecessor has a higher priority, since scheduling it will make - // the node available. - void ScheduledNode(SUnit *Node); - - private: - void CalculatePriorities(); - int CalcLatency(const SUnit &SU); - void AdjustPriorityOfUnscheduledPreds(SUnit *SU); - SUnit *getSingleUnscheduledPred(SUnit *SU); - }; -} - -#endif diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp deleted file mode 100644 index c2e2175..0000000 --- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp +++ /dev/null @@ -1,522 +0,0 @@ -//===---- ScheduleDAG.cpp - Implement the ScheduleDAG class ---------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This implements the ScheduleDAG class, which is a base class used by -// scheduling implementation classes. -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "pre-RA-sched" -#include "llvm/CodeGen/ScheduleDAG.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" -using namespace llvm; - -ScheduleDAG::ScheduleDAG(SelectionDAG *dag, MachineBasicBlock *bb, - const TargetMachine &tm) - : DAG(dag), BB(bb), TM(tm), MRI(BB->getParent()->getRegInfo()) { - TII = TM.getInstrInfo(); - MF = BB->getParent(); - TRI = TM.getRegisterInfo(); - TLI = TM.getTargetLowering(); - ConstPool = MF->getConstantPool(); -} - -/// CheckForPhysRegDependency - Check if the dependency between def and use of -/// a specified operand is a physical register dependency. If so, returns the -/// register and the cost of copying the register. -static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, - const TargetRegisterInfo *TRI, - const TargetInstrInfo *TII, - unsigned &PhysReg, int &Cost) { - if (Op != 2 || User->getOpcode() != ISD::CopyToReg) - return; - - unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); - if (TargetRegisterInfo::isVirtualRegister(Reg)) - return; - - unsigned ResNo = User->getOperand(2).getResNo(); - if (Def->isMachineOpcode()) { - const TargetInstrDesc &II = TII->get(Def->getMachineOpcode()); - if (ResNo >= II.getNumDefs() && - II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) { - PhysReg = Reg; - const TargetRegisterClass *RC = - TRI->getPhysicalRegisterRegClass(Reg, Def->getValueType(ResNo)); - Cost = RC->getCopyCost(); - } - } -} - -SUnit *ScheduleDAG::Clone(SUnit *Old) { - SUnit *SU = NewSUnit(Old->getNode()); - SU->OrigNode = Old->OrigNode; - SU->Latency = Old->Latency; - SU->isTwoAddress = Old->isTwoAddress; - SU->isCommutable = Old->isCommutable; - SU->hasPhysRegDefs = Old->hasPhysRegDefs; - return SU; -} - - -/// BuildSchedUnits - Build SUnits from the selection dag that we are input. -/// This SUnit graph is similar to the SelectionDAG, but represents flagged -/// together nodes with a single SUnit. -void ScheduleDAG::BuildSchedUnits() { - // For post-regalloc scheduling, build the SUnits from the MachineInstrs - // in the MachineBasicBlock. - if (!DAG) { - BuildSchedUnitsFromMBB(); - return; - } - - // Reserve entries in the vector for each of the SUnits we are creating. This - // ensure that reallocation of the vector won't happen, so SUnit*'s won't get - // invalidated. - SUnits.reserve(DAG->allnodes_size()); - - // During scheduling, the NodeId field of SDNode is used to map SDNodes - // to their associated SUnits by holding SUnits table indices. A value - // of -1 means the SDNode does not yet have an associated SUnit. - for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), - E = DAG->allnodes_end(); NI != E; ++NI) - NI->setNodeId(-1); - - for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), - E = DAG->allnodes_end(); NI != E; ++NI) { - if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. - continue; - - // If this node has already been processed, stop now. - if (NI->getNodeId() != -1) continue; - - SUnit *NodeSUnit = NewSUnit(NI); - - // See if anything is flagged to this node, if so, add them to flagged - // nodes. Nodes can have at most one flag input and one flag output. Flags - // are required the be the last operand and result of a node. - - // Scan up to find flagged preds. - SDNode *N = NI; - if (N->getNumOperands() && - N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) { - do { - N = N->getOperand(N->getNumOperands()-1).getNode(); - assert(N->getNodeId() == -1 && "Node already inserted!"); - N->setNodeId(NodeSUnit->NodeNum); - } while (N->getNumOperands() && - N->getOperand(N->getNumOperands()-1).getValueType()== MVT::Flag); - } - - // Scan down to find any flagged succs. - N = NI; - while (N->getValueType(N->getNumValues()-1) == MVT::Flag) { - SDValue FlagVal(N, N->getNumValues()-1); - - // There are either zero or one users of the Flag result. - bool HasFlagUse = false; - for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); - UI != E; ++UI) - if (FlagVal.isOperandOf(*UI)) { - HasFlagUse = true; - assert(N->getNodeId() == -1 && "Node already inserted!"); - N->setNodeId(NodeSUnit->NodeNum); - N = *UI; - break; - } - if (!HasFlagUse) break; - } - - // If there are flag operands involved, N is now the bottom-most node - // of the sequence of nodes that are flagged together. - // Update the SUnit. - NodeSUnit->setNode(N); - assert(N->getNodeId() == -1 && "Node already inserted!"); - N->setNodeId(NodeSUnit->NodeNum); - - ComputeLatency(NodeSUnit); - } - - // Pass 2: add the preds, succs, etc. - for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { - SUnit *SU = &SUnits[su]; - SDNode *MainNode = SU->getNode(); - - if (MainNode->isMachineOpcode()) { - unsigned Opc = MainNode->getMachineOpcode(); - const TargetInstrDesc &TID = TII->get(Opc); - for (unsigned i = 0; i != TID.getNumOperands(); ++i) { - if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { - SU->isTwoAddress = true; - break; - } - } - if (TID.isCommutable()) - SU->isCommutable = true; - } - - // Find all predecessors and successors of the group. - for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) { - if (N->isMachineOpcode() && - TII->get(N->getMachineOpcode()).getImplicitDefs() && - CountResults(N) > TII->get(N->getMachineOpcode()).getNumDefs()) - SU->hasPhysRegDefs = true; - - for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { - SDNode *OpN = N->getOperand(i).getNode(); - if (isPassiveNode(OpN)) continue; // Not scheduled. - SUnit *OpSU = &SUnits[OpN->getNodeId()]; - assert(OpSU && "Node has no SUnit!"); - if (OpSU == SU) continue; // In the same group. - - MVT OpVT = N->getOperand(i).getValueType(); - assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!"); - bool isChain = OpVT == MVT::Other; - - unsigned PhysReg = 0; - int Cost = 1; - // Determine if this is a physical register dependency. - CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost); - SU->addPred(OpSU, isChain, false, PhysReg, Cost); - } - } - } -} - -void ScheduleDAG::BuildSchedUnitsFromMBB() { - SUnits.clear(); - SUnits.reserve(BB->size()); - - std::vector<SUnit *> PendingLoads; - SUnit *Terminator = 0; - SUnit *Chain = 0; - SUnit *Defs[TargetRegisterInfo::FirstVirtualRegister] = {}; - std::vector<SUnit *> Uses[TargetRegisterInfo::FirstVirtualRegister] = {}; - int Cost = 1; // FIXME - - for (MachineBasicBlock::iterator MII = BB->end(), MIE = BB->begin(); - MII != MIE; --MII) { - MachineInstr *MI = prior(MII); - SUnit *SU = NewSUnit(MI); - - for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) { - const MachineOperand &MO = MI->getOperand(j); - if (!MO.isReg()) continue; - unsigned Reg = MO.getReg(); - if (Reg == 0) continue; - - assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!"); - std::vector<SUnit *> &UseList = Uses[Reg]; - SUnit *&Def = Defs[Reg]; - // Optionally add output and anti dependences - if (Def && Def != SU) - Def->addPred(SU, /*isCtrl=*/true, /*isSpecial=*/false, - /*PhyReg=*/Reg, Cost); - for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { - SUnit *&Def = Defs[*Alias]; - if (Def && Def != SU) - Def->addPred(SU, /*isCtrl=*/true, /*isSpecial=*/false, - /*PhyReg=*/*Alias, Cost); - } - - if (MO.isDef()) { - // Add any data dependencies. - for (unsigned i = 0, e = UseList.size(); i != e; ++i) - if (UseList[i] != SU) - UseList[i]->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false, - /*PhysReg=*/Reg, Cost); - for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { - std::vector<SUnit *> &UseList = Uses[*Alias]; - for (unsigned i = 0, e = UseList.size(); i != e; ++i) - if (UseList[i] != SU) - UseList[i]->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false, - /*PhysReg=*/*Alias, Cost); - } - - UseList.clear(); - Def = SU; - } else { - UseList.push_back(SU); - } - } - bool False = false; - bool True = true; - if (!MI->isSafeToMove(TII, False)) { - if (Chain) - Chain->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false); - for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k) - PendingLoads[k]->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false); - PendingLoads.clear(); - Chain = SU; - } else if (!MI->isSafeToMove(TII, True)) { - if (Chain) - Chain->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false); - PendingLoads.push_back(SU); - } - if (Terminator && SU->Succs.empty()) - Terminator->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false); - if (MI->getDesc().isTerminator()) - Terminator = SU; - } -} - -void ScheduleDAG::ComputeLatency(SUnit *SU) { - const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); - - // Compute the latency for the node. We use the sum of the latencies for - // all nodes flagged together into this SUnit. - if (InstrItins.isEmpty()) { - // No latency information. - SU->Latency = 1; - return; - } - - SU->Latency = 0; - for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) { - if (N->isMachineOpcode()) { - unsigned SchedClass = TII->get(N->getMachineOpcode()).getSchedClass(); - const InstrStage *S = InstrItins.begin(SchedClass); - const InstrStage *E = InstrItins.end(SchedClass); - for (; S != E; ++S) - SU->Latency += S->Cycles; - } - } -} - -/// CalculateDepths - compute depths using algorithms for the longest -/// paths in the DAG -void ScheduleDAG::CalculateDepths() { - unsigned DAGSize = SUnits.size(); - std::vector<SUnit*> WorkList; - WorkList.reserve(DAGSize); - - // Initialize the data structures - for (unsigned i = 0, e = DAGSize; i != e; ++i) { - SUnit *SU = &SUnits[i]; - unsigned Degree = SU->Preds.size(); - // Temporarily use the Depth field as scratch space for the degree count. - SU->Depth = Degree; - - // Is it a node without dependencies? - if (Degree == 0) { - assert(SU->Preds.empty() && "SUnit should have no predecessors"); - // Collect leaf nodes - WorkList.push_back(SU); - } - } - - // Process nodes in the topological order - while (!WorkList.empty()) { - SUnit *SU = WorkList.back(); - WorkList.pop_back(); - unsigned SUDepth = 0; - - // Use dynamic programming: - // When current node is being processed, all of its dependencies - // are already processed. - // So, just iterate over all predecessors and take the longest path - for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); - I != E; ++I) { - unsigned PredDepth = I->Dep->Depth; - if (PredDepth+1 > SUDepth) { - SUDepth = PredDepth + 1; - } - } - - SU->Depth = SUDepth; - - // Update degrees of all nodes depending on current SUnit - for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); - I != E; ++I) { - SUnit *SU = I->Dep; - if (!--SU->Depth) - // If all dependencies of the node are processed already, - // then the longest path for the node can be computed now - WorkList.push_back(SU); - } - } -} - -/// CalculateHeights - compute heights using algorithms for the longest -/// paths in the DAG -void ScheduleDAG::CalculateHeights() { - unsigned DAGSize = SUnits.size(); - std::vector<SUnit*> WorkList; - WorkList.reserve(DAGSize); - - // Initialize the data structures - for (unsigned i = 0, e = DAGSize; i != e; ++i) { - SUnit *SU = &SUnits[i]; - unsigned Degree = SU->Succs.size(); - // Temporarily use the Height field as scratch space for the degree count. - SU->Height = Degree; - - // Is it a node without dependencies? - if (Degree == 0) { - assert(SU->Succs.empty() && "Something wrong"); - assert(WorkList.empty() && "Should be empty"); - // Collect leaf nodes - WorkList.push_back(SU); - } - } - - // Process nodes in the topological order - while (!WorkList.empty()) { - SUnit *SU = WorkList.back(); - WorkList.pop_back(); - unsigned SUHeight = 0; - - // Use dynamic programming: - // When current node is being processed, all of its dependencies - // are already processed. - // So, just iterate over all successors and take the longest path - for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); - I != E; ++I) { - unsigned SuccHeight = I->Dep->Height; - if (SuccHeight+1 > SUHeight) { - SUHeight = SuccHeight + 1; - } - } - - SU->Height = SUHeight; - - // Update degrees of all nodes depending on current SUnit - for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); - I != E; ++I) { - SUnit *SU = I->Dep; - if (!--SU->Height) - // If all dependencies of the node are processed already, - // then the longest path for the node can be computed now - WorkList.push_back(SU); - } - } -} - -/// CountResults - The results of target nodes have register or immediate -/// operands first, then an optional chain, and optional flag operands (which do -/// not go into the resulting MachineInstr). -unsigned ScheduleDAG::CountResults(SDNode *Node) { - unsigned N = Node->getNumValues(); - while (N && Node->getValueType(N - 1) == MVT::Flag) - --N; - if (N && Node->getValueType(N - 1) == MVT::Other) - --N; // Skip over chain result. - return N; -} - -/// CountOperands - The inputs to target nodes have any actual inputs first, -/// followed by special operands that describe memory references, then an -/// optional chain operand, then an optional flag operand. Compute the number -/// of actual operands that will go into the resulting MachineInstr. -unsigned ScheduleDAG::CountOperands(SDNode *Node) { - unsigned N = ComputeMemOperandsEnd(Node); - while (N && isa<MemOperandSDNode>(Node->getOperand(N - 1).getNode())) - --N; // Ignore MEMOPERAND nodes - return N; -} - -/// ComputeMemOperandsEnd - Find the index one past the last MemOperandSDNode -/// operand -unsigned ScheduleDAG::ComputeMemOperandsEnd(SDNode *Node) { - unsigned N = Node->getNumOperands(); - while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag) - --N; - if (N && Node->getOperand(N - 1).getValueType() == MVT::Other) - --N; // Ignore chain if it exists. - return N; -} - - -/// dump - dump the schedule. -void ScheduleDAG::dumpSchedule() const { - for (unsigned i = 0, e = Sequence.size(); i != e; i++) { - if (SUnit *SU = Sequence[i]) - SU->dump(this); - else - cerr << "**** NOOP ****\n"; - } -} - - -/// Run - perform scheduling. -/// -void ScheduleDAG::Run() { - Schedule(); - - DOUT << "*** Final schedule ***\n"; - DEBUG(dumpSchedule()); - DOUT << "\n"; -} - -/// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or -/// a group of nodes flagged together. -void SUnit::print(raw_ostream &O, const ScheduleDAG *G) const { - O << "SU(" << NodeNum << "): "; - if (getNode()) { - SmallVector<SDNode *, 4> FlaggedNodes; - for (SDNode *N = getNode(); N; N = N->getFlaggedNode()) - FlaggedNodes.push_back(N); - while (!FlaggedNodes.empty()) { - O << " "; - FlaggedNodes.back()->print(O, G->DAG); - O << "\n"; - FlaggedNodes.pop_back(); - } - } else { - O << "CROSS RC COPY\n"; - } -} - -void SUnit::dump(const ScheduleDAG *G) const { - print(errs(), G); -} - -void SUnit::dumpAll(const ScheduleDAG *G) const { - dump(G); - - cerr << " # preds left : " << NumPredsLeft << "\n"; - cerr << " # succs left : " << NumSuccsLeft << "\n"; - cerr << " Latency : " << Latency << "\n"; - cerr << " Depth : " << Depth << "\n"; - cerr << " Height : " << Height << "\n"; - - if (Preds.size() != 0) { - cerr << " Predecessors:\n"; - for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end(); - I != E; ++I) { - if (I->isCtrl) - cerr << " ch #"; - else - cerr << " val #"; - cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")"; - if (I->isSpecial) - cerr << " *"; - cerr << "\n"; - } - } - if (Succs.size() != 0) { - cerr << " Successors:\n"; - for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end(); - I != E; ++I) { - if (I->isCtrl) - cerr << " ch #"; - else - cerr << " val #"; - cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")"; - if (I->isSpecial) - cerr << " *"; - cerr << "\n"; - } - } - cerr << "\n"; -} diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp index 0af0358..8f3198e 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp @@ -12,7 +12,7 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "pre-RA-sched" -#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/ScheduleDAGSDNodes.h" #include "llvm/CodeGen/SchedulerRegistry.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetData.h" @@ -58,7 +58,7 @@ namespace { //===----------------------------------------------------------------------===// /// ScheduleDAGFast - The actual "fast" list scheduler implementation. /// -class VISIBILITY_HIDDEN ScheduleDAGFast : public ScheduleDAG { +class VISIBILITY_HIDDEN ScheduleDAGFast : public ScheduleDAGSDNodes { private: /// AvailableQueue - The priority queue to use for the available SUnits. FastPriorityQueue AvailableQueue; @@ -73,7 +73,7 @@ private: public: ScheduleDAGFast(SelectionDAG *dag, MachineBasicBlock *bb, const TargetMachine &tm) - : ScheduleDAG(dag, bb, tm) {} + : ScheduleDAGSDNodes(dag, bb, tm) {} void Schedule(); diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp index c2c9110..e1a24a1 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp @@ -19,7 +19,8 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "pre-RA-sched" -#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/LatencyPriorityQueue.h" +#include "llvm/CodeGen/ScheduleDAGSDNodes.h" #include "llvm/CodeGen/SchedulerRegistry.h" #include "llvm/CodeGen/SelectionDAGISel.h" #include "llvm/Target/TargetRegisterInfo.h" @@ -30,7 +31,6 @@ #include "llvm/Support/Compiler.h" #include "llvm/ADT/PriorityQueue.h" #include "llvm/ADT/Statistic.h" -#include "LatencyPriorityQueue.h" #include <climits> using namespace llvm; @@ -46,7 +46,7 @@ namespace { /// ScheduleDAGList - The actual list scheduler implementation. This supports /// top-down scheduling. /// -class VISIBILITY_HIDDEN ScheduleDAGList : public ScheduleDAG { +class VISIBILITY_HIDDEN ScheduleDAGList : public ScheduleDAGSDNodes { private: /// AvailableQueue - The priority queue to use for the available SUnits. /// @@ -66,7 +66,7 @@ public: const TargetMachine &tm, SchedulingPriorityQueue *availqueue, HazardRecognizer *HR) - : ScheduleDAG(dag, bb, tm), + : ScheduleDAGSDNodes(dag, bb, tm), AvailableQueue(availqueue), HazardRec(HR) { } @@ -212,13 +212,13 @@ void ScheduleDAGList::ListScheduleTopDown() { if (!N) break; FoundNode = N; } - + HazardRecognizer::HazardType HT = HazardRec->getHazardType(FoundNode); if (HT == HazardRecognizer::NoHazard) { FoundSUnit = CurSUnit; break; } - + // Remember if this is a noop hazard. HasNoopHazards |= HT == HazardRecognizer::NoopHazard; diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp index 7c3f6bb..45a1ca0 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp @@ -16,7 +16,7 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "pre-RA-sched" -#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/ScheduleDAGSDNodes.h" #include "llvm/CodeGen/SchedulerRegistry.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetData.h" @@ -53,7 +53,7 @@ namespace { /// ScheduleDAGRRList - The actual register reduction list scheduler /// implementation. This supports both top-down and bottom-up scheduling. /// -class VISIBILITY_HIDDEN ScheduleDAGRRList : public ScheduleDAG { +class VISIBILITY_HIDDEN ScheduleDAGRRList : public ScheduleDAGSDNodes { private: /// isBottomUp - This is true if the scheduling problem is bottom-up, false if /// it is top-down. @@ -77,7 +77,7 @@ public: ScheduleDAGRRList(SelectionDAG *dag, MachineBasicBlock *bb, const TargetMachine &tm, bool isbottomup, bool f, SchedulingPriorityQueue *availqueue) - : ScheduleDAG(dag, bb, tm), isBottomUp(isbottomup), Fast(f), + : ScheduleDAGSDNodes(dag, bb, tm), isBottomUp(isbottomup), Fast(f), AvailableQueue(availqueue) { } diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp new file mode 100644 index 0000000..9d32d9a --- /dev/null +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp @@ -0,0 +1,257 @@ +//===--- ScheduleDAGSDNodes.cpp - Implement the ScheduleDAGSDNodes class --===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This implements the ScheduleDAG class, which is a base class used by +// scheduling implementation classes. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "pre-RA-sched" +#include "llvm/CodeGen/ScheduleDAGSDNodes.h" +#include "llvm/CodeGen/SelectionDAG.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +using namespace llvm; + +ScheduleDAGSDNodes::ScheduleDAGSDNodes(SelectionDAG *dag, MachineBasicBlock *bb, + const TargetMachine &tm) + : ScheduleDAG(dag, bb, tm) { +} + +SUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) { + SUnit *SU = NewSUnit(Old->getNode()); + SU->OrigNode = Old->OrigNode; + SU->Latency = Old->Latency; + SU->isTwoAddress = Old->isTwoAddress; + SU->isCommutable = Old->isCommutable; + SU->hasPhysRegDefs = Old->hasPhysRegDefs; + return SU; +} + +/// CheckForPhysRegDependency - Check if the dependency between def and use of +/// a specified operand is a physical register dependency. If so, returns the +/// register and the cost of copying the register. +static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, + const TargetRegisterInfo *TRI, + const TargetInstrInfo *TII, + unsigned &PhysReg, int &Cost) { + if (Op != 2 || User->getOpcode() != ISD::CopyToReg) + return; + + unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); + if (TargetRegisterInfo::isVirtualRegister(Reg)) + return; + + unsigned ResNo = User->getOperand(2).getResNo(); + if (Def->isMachineOpcode()) { + const TargetInstrDesc &II = TII->get(Def->getMachineOpcode()); + if (ResNo >= II.getNumDefs() && + II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) { + PhysReg = Reg; + const TargetRegisterClass *RC = + TRI->getPhysicalRegisterRegClass(Reg, Def->getValueType(ResNo)); + Cost = RC->getCopyCost(); + } + } +} + +/// BuildSchedUnits - Build SUnits from the selection dag that we are input. +/// This SUnit graph is similar to the SelectionDAG, but represents flagged +/// together nodes with a single SUnit. +void ScheduleDAGSDNodes::BuildSchedUnits() { + // Reserve entries in the vector for each of the SUnits we are creating. This + // ensure that reallocation of the vector won't happen, so SUnit*'s won't get + // invalidated. + SUnits.reserve(DAG->allnodes_size()); + + // During scheduling, the NodeId field of SDNode is used to map SDNodes + // to their associated SUnits by holding SUnits table indices. A value + // of -1 means the SDNode does not yet have an associated SUnit. + for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), + E = DAG->allnodes_end(); NI != E; ++NI) + NI->setNodeId(-1); + + for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), + E = DAG->allnodes_end(); NI != E; ++NI) { + if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. + continue; + + // If this node has already been processed, stop now. + if (NI->getNodeId() != -1) continue; + + SUnit *NodeSUnit = NewSUnit(NI); + + // See if anything is flagged to this node, if so, add them to flagged + // nodes. Nodes can have at most one flag input and one flag output. Flags + // are required the be the last operand and result of a node. + + // Scan up to find flagged preds. + SDNode *N = NI; + if (N->getNumOperands() && + N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) { + do { + N = N->getOperand(N->getNumOperands()-1).getNode(); + assert(N->getNodeId() == -1 && "Node already inserted!"); + N->setNodeId(NodeSUnit->NodeNum); + } while (N->getNumOperands() && + N->getOperand(N->getNumOperands()-1).getValueType()== MVT::Flag); + } + + // Scan down to find any flagged succs. + N = NI; + while (N->getValueType(N->getNumValues()-1) == MVT::Flag) { + SDValue FlagVal(N, N->getNumValues()-1); + + // There are either zero or one users of the Flag result. + bool HasFlagUse = false; + for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); + UI != E; ++UI) + if (FlagVal.isOperandOf(*UI)) { + HasFlagUse = true; + assert(N->getNodeId() == -1 && "Node already inserted!"); + N->setNodeId(NodeSUnit->NodeNum); + N = *UI; + break; + } + if (!HasFlagUse) break; + } + + // If there are flag operands involved, N is now the bottom-most node + // of the sequence of nodes that are flagged together. + // Update the SUnit. + NodeSUnit->setNode(N); + assert(N->getNodeId() == -1 && "Node already inserted!"); + N->setNodeId(NodeSUnit->NodeNum); + + ComputeLatency(NodeSUnit); + } + + // Pass 2: add the preds, succs, etc. + for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { + SUnit *SU = &SUnits[su]; + SDNode *MainNode = SU->getNode(); + + if (MainNode->isMachineOpcode()) { + unsigned Opc = MainNode->getMachineOpcode(); + const TargetInstrDesc &TID = TII->get(Opc); + for (unsigned i = 0; i != TID.getNumOperands(); ++i) { + if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { + SU->isTwoAddress = true; + break; + } + } + if (TID.isCommutable()) + SU->isCommutable = true; + } + + // Find all predecessors and successors of the group. + for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) { + if (N->isMachineOpcode() && + TII->get(N->getMachineOpcode()).getImplicitDefs() && + CountResults(N) > TII->get(N->getMachineOpcode()).getNumDefs()) + SU->hasPhysRegDefs = true; + + for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { + SDNode *OpN = N->getOperand(i).getNode(); + if (isPassiveNode(OpN)) continue; // Not scheduled. + SUnit *OpSU = &SUnits[OpN->getNodeId()]; + assert(OpSU && "Node has no SUnit!"); + if (OpSU == SU) continue; // In the same group. + + MVT OpVT = N->getOperand(i).getValueType(); + assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!"); + bool isChain = OpVT == MVT::Other; + + unsigned PhysReg = 0; + int Cost = 1; + // Determine if this is a physical register dependency. + CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost); + SU->addPred(OpSU, isChain, false, PhysReg, Cost); + } + } + } +} + +void ScheduleDAGSDNodes::ComputeLatency(SUnit *SU) { + const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); + + // Compute the latency for the node. We use the sum of the latencies for + // all nodes flagged together into this SUnit. + if (InstrItins.isEmpty()) { + // No latency information. + SU->Latency = 1; + return; + } + + SU->Latency = 0; + for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) { + if (N->isMachineOpcode()) { + unsigned SchedClass = TII->get(N->getMachineOpcode()).getSchedClass(); + const InstrStage *S = InstrItins.begin(SchedClass); + const InstrStage *E = InstrItins.end(SchedClass); + for (; S != E; ++S) + SU->Latency += S->Cycles; + } + } +} + +/// CountResults - The results of target nodes have register or immediate +/// operands first, then an optional chain, and optional flag operands (which do +/// not go into the resulting MachineInstr). +unsigned ScheduleDAGSDNodes::CountResults(SDNode *Node) { + unsigned N = Node->getNumValues(); + while (N && Node->getValueType(N - 1) == MVT::Flag) + --N; + if (N && Node->getValueType(N - 1) == MVT::Other) + --N; // Skip over chain result. + return N; +} + +/// CountOperands - The inputs to target nodes have any actual inputs first, +/// followed by special operands that describe memory references, then an +/// optional chain operand, then an optional flag operand. Compute the number +/// of actual operands that will go into the resulting MachineInstr. +unsigned ScheduleDAGSDNodes::CountOperands(SDNode *Node) { + unsigned N = ComputeMemOperandsEnd(Node); + while (N && isa<MemOperandSDNode>(Node->getOperand(N - 1).getNode())) + --N; // Ignore MEMOPERAND nodes + return N; +} + +/// ComputeMemOperandsEnd - Find the index one past the last MemOperandSDNode +/// operand +unsigned ScheduleDAGSDNodes::ComputeMemOperandsEnd(SDNode *Node) { + unsigned N = Node->getNumOperands(); + while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag) + --N; + if (N && Node->getOperand(N - 1).getValueType() == MVT::Other) + --N; // Ignore chain if it exists. + return N; +} + + +void ScheduleDAGSDNodes::dumpNode(const SUnit *SU) const { + if (SU->getNode()) + SU->getNode()->dump(DAG); + else + cerr << "CROSS RC COPY "; + cerr << "\n"; + SmallVector<SDNode *, 4> FlaggedNodes; + for (SDNode *N = SU->getNode()->getFlaggedNode(); N; N = N->getFlaggedNode()) + FlaggedNodes.push_back(N); + while (!FlaggedNodes.empty()) { + cerr << " "; + FlaggedNodes.back()->dump(DAG); + cerr << "\n"; + FlaggedNodes.pop_back(); + } +} diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGEmit.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp index 0c67973..dc9313b 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGEmit.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp @@ -13,7 +13,7 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "pre-RA-sched" -#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/ScheduleDAGSDNodes.h" #include "llvm/CodeGen/MachineConstantPool.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineInstrBuilder.h" @@ -47,9 +47,9 @@ getInstrOperandRegClass(const TargetRegisterInfo *TRI, /// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an /// implicit physical register output. -void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo, - bool IsClone, unsigned SrcReg, - DenseMap<SDValue, unsigned> &VRBaseMap) { +void ScheduleDAGSDNodes::EmitCopyFromReg(SDNode *Node, unsigned ResNo, + bool IsClone, unsigned SrcReg, + DenseMap<SDValue, unsigned> &VRBaseMap) { unsigned VRBase = 0; if (TargetRegisterInfo::isVirtualRegister(SrcReg)) { // Just use the input register directly! @@ -142,8 +142,8 @@ void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo, /// getDstOfCopyToRegUse - If the only use of the specified result number of /// node is a CopyToReg, return its destination register. Return 0 otherwise. -unsigned ScheduleDAG::getDstOfOnlyCopyToRegUse(SDNode *Node, - unsigned ResNo) const { +unsigned ScheduleDAGSDNodes::getDstOfOnlyCopyToRegUse(SDNode *Node, + unsigned ResNo) const { if (!Node->hasOneUse()) return 0; @@ -158,7 +158,7 @@ unsigned ScheduleDAG::getDstOfOnlyCopyToRegUse(SDNode *Node, return 0; } -void ScheduleDAG::CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, +void ScheduleDAGSDNodes::CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, const TargetInstrDesc &II, DenseMap<SDValue, unsigned> &VRBaseMap) { assert(Node->getMachineOpcode() != TargetInstrInfo::IMPLICIT_DEF && @@ -202,8 +202,8 @@ void ScheduleDAG::CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, /// getVR - Return the virtual register corresponding to the specified result /// of the specified node. -unsigned ScheduleDAG::getVR(SDValue Op, - DenseMap<SDValue, unsigned> &VRBaseMap) { +unsigned ScheduleDAGSDNodes::getVR(SDValue Op, + DenseMap<SDValue, unsigned> &VRBaseMap) { if (Op.isMachineOpcode() && Op.getMachineOpcode() == TargetInstrInfo::IMPLICIT_DEF) { // Add an IMPLICIT_DEF instruction before every use. @@ -228,10 +228,10 @@ unsigned ScheduleDAG::getVR(SDValue Op, /// specifies the instruction information for the node, and IIOpNum is the /// operand number (in the II) that we are adding. IIOpNum and II are used for /// assertions only. -void ScheduleDAG::AddOperand(MachineInstr *MI, SDValue Op, - unsigned IIOpNum, - const TargetInstrDesc *II, - DenseMap<SDValue, unsigned> &VRBaseMap) { +void ScheduleDAGSDNodes::AddOperand(MachineInstr *MI, SDValue Op, + unsigned IIOpNum, + const TargetInstrDesc *II, + DenseMap<SDValue, unsigned> &VRBaseMap) { if (Op.isMachineOpcode()) { // Note that this case is redundant with the final else block, but we // include it because it is the most common and it makes the logic @@ -328,10 +328,6 @@ void ScheduleDAG::AddOperand(MachineInstr *MI, SDValue Op, } } -void ScheduleDAG::AddMemOperand(MachineInstr *MI, const MachineMemOperand &MO) { - MI->addMemOperand(*MF, MO); -} - /// getSubRegisterRegClass - Returns the register class of specified register /// class' "SubIdx"'th sub-register class. static const TargetRegisterClass* @@ -361,8 +357,8 @@ getSuperRegisterRegClass(const TargetRegisterClass *TRC, /// EmitSubregNode - Generate machine code for subreg nodes. /// -void ScheduleDAG::EmitSubregNode(SDNode *Node, - DenseMap<SDValue, unsigned> &VRBaseMap) { +void ScheduleDAGSDNodes::EmitSubregNode(SDNode *Node, + DenseMap<SDValue, unsigned> &VRBaseMap) { unsigned VRBase = 0; unsigned Opc = Node->getMachineOpcode(); @@ -456,8 +452,8 @@ void ScheduleDAG::EmitSubregNode(SDNode *Node, /// EmitNode - Generate machine code for an node and needed dependencies. /// -void ScheduleDAG::EmitNode(SDNode *Node, bool IsClone, - DenseMap<SDValue, unsigned> &VRBaseMap) { +void ScheduleDAGSDNodes::EmitNode(SDNode *Node, bool IsClone, + DenseMap<SDValue, unsigned> &VRBaseMap) { // If machine instruction if (Node->isMachineOpcode()) { unsigned Opc = Node->getMachineOpcode(); @@ -634,53 +630,8 @@ void ScheduleDAG::EmitNode(SDNode *Node, bool IsClone, } } -void ScheduleDAG::EmitNoop() { - TII->insertNoop(*BB, BB->end()); -} - -void ScheduleDAG::EmitCrossRCCopy(SUnit *SU, - DenseMap<SUnit*, unsigned> &VRBaseMap) { - 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()) { - // Copy to physical register. - DenseMap<SUnit*, unsigned>::iterator VRI = VRBaseMap.find(I->Dep); - assert(VRI != VRBaseMap.end() && "Node emitted out of order - late"); - // Find the destination physical register. - unsigned Reg = 0; - for (SUnit::const_succ_iterator II = SU->Succs.begin(), - EE = SU->Succs.end(); II != EE; ++II) { - if (I->Reg) { - Reg = I->Reg; - break; - } - } - assert(I->Reg && "Unknown physical register!"); - TII->copyRegToReg(*BB, BB->end(), Reg, VRI->second, - SU->CopyDstRC, SU->CopySrcRC); - } else { - // Copy from physical register. - assert(I->Reg && "Unknown physical register!"); - unsigned VRBase = MRI.createVirtualRegister(SU->CopyDstRC); - bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase)).second; - isNew = isNew; // Silence compiler warning. - assert(isNew && "Node emitted out of order - early"); - TII->copyRegToReg(*BB, BB->end(), VRBase, I->Reg, - SU->CopyDstRC, SU->CopySrcRC); - } - break; - } -} - /// EmitSchedule - Emit the machine code in scheduled order. -MachineBasicBlock *ScheduleDAG::EmitSchedule() { - // For post-regalloc scheduling, we're rescheduling the instructions in the - // block, so start by removing them from the block. - if (!DAG) - while (!BB->empty()) - BB->remove(BB->begin()); - +MachineBasicBlock *ScheduleDAGSDNodes::EmitSchedule() { DenseMap<SDValue, unsigned> VRBaseMap; DenseMap<SUnit*, unsigned> CopyVRBaseMap; for (unsigned i = 0, e = Sequence.size(); i != e; i++) { @@ -691,13 +642,6 @@ MachineBasicBlock *ScheduleDAG::EmitSchedule() { continue; } - // For post-regalloc scheduling, we already have the instruction; - // just append it to the block. - if (!DAG) { - BB->push_back(SU->getInstr()); - continue; - } - // For pre-regalloc scheduling, create instructions corresponding to the // SDNode and any flagged SDNodes and append them to the block. SmallVector<SDNode *, 4> FlaggedNodes; diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index 23822fa..e43b325 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -34,7 +34,7 @@ #include "llvm/CodeGen/MachineJumpTableInfo.h" #include "llvm/CodeGen/MachineModuleInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/ScheduleDAGSDNodes.h" #include "llvm/CodeGen/SchedulerRegistry.h" #include "llvm/CodeGen/SelectionDAG.h" #include "llvm/Target/TargetRegisterInfo.h" diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp index d748108..03b78c3 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp @@ -15,7 +15,7 @@ #include "llvm/Function.h" #include "llvm/Assembly/Writer.h" #include "llvm/CodeGen/SelectionDAG.h" -#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/ScheduleDAGSDNodes.h" #include "llvm/CodeGen/MachineConstantPool.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineModuleInfo.h" @@ -383,71 +383,7 @@ void SelectionDAG::setSubgraphColor(SDNode *N, const char *Color) { #endif } -namespace llvm { - template<> - struct DOTGraphTraits<ScheduleDAG*> : public DefaultDOTGraphTraits { - static std::string getGraphName(const ScheduleDAG *G) { - return G->MF->getFunction()->getName(); - } - - static bool renderGraphFromBottomUp() { - return true; - } - - static bool hasNodeAddressLabel(const SUnit *Node, - const ScheduleDAG *Graph) { - return true; - } - - /// If you want to override the dot attributes printed for a particular - /// edge, override this method. - template<typename EdgeIter> - static std::string getEdgeAttributes(const void *Node, EdgeIter EI) { - if (EI.isSpecialDep()) - return "color=cyan,style=dashed"; - if (EI.isCtrlDep()) - return "color=blue,style=dashed"; - return ""; - } - - - static std::string getNodeLabel(const SUnit *Node, - const ScheduleDAG *Graph); - static std::string getNodeAttributes(const SUnit *N, - const ScheduleDAG *Graph) { - return "shape=Mrecord"; - } - - static void addCustomGraphFeatures(ScheduleDAG *G, - GraphWriter<ScheduleDAG*> &GW) { - // Draw a special "GraphRoot" node to indicate the root of the graph. - GW.emitSimpleNode(0, "plaintext=circle", "GraphRoot"); - if (G->DAG) { - // For an SDNode-based ScheduleDAG, point to the root of the ScheduleDAG. - const SDNode *N = G->DAG->getRoot().getNode(); - if (N && N->getNodeId() != -1) - GW.emitEdge(0, -1, &G->SUnits[N->getNodeId()], -1, - "color=blue,style=dashed"); - } else { - // For a MachineInstr-based ScheduleDAG, find a root to point to. - for (unsigned i = 0, e = G->SUnits.size(); i != e; ++i) { - if (G->SUnits[i].Succs.empty()) { - GW.emitEdge(0, -1, &G->SUnits[i], -1, - "color=blue,style=dashed"); - break; - } - } - } - } - }; -} - -std::string DOTGraphTraits<ScheduleDAG*>::getNodeLabel(const SUnit *SU, - const ScheduleDAG *G) { - return G->getGraphNodeLabel(SU); -} - -std::string ScheduleDAG::getGraphNodeLabel(const SUnit *SU) const { +std::string ScheduleDAGSDNodes::getGraphNodeLabel(const SUnit *SU) const { std::string s; raw_string_ostream O(s); O << "SU(" << SU->NodeNum << "): "; @@ -467,17 +403,13 @@ std::string ScheduleDAG::getGraphNodeLabel(const SUnit *SU) const { return O.str(); } -/// viewGraph - Pop up a ghostview window with the reachable parts of the DAG -/// rendered using 'dot'. -/// -void ScheduleDAG::viewGraph() { -// This code is only for debugging! -#ifndef NDEBUG - ViewGraph(this, "dag." + MF->getFunction()->getName(), - "Scheduling-Units Graph for " + MF->getFunction()->getName() + ':' + - BB->getBasicBlock()->getName()); -#else - cerr << "ScheduleDAG::viewGraph is only available in debug builds on " - << "systems with Graphviz or gv!\n"; -#endif // NDEBUG +void ScheduleDAGSDNodes::getCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const { + if (DAG) { + // Draw a special "GraphRoot" node to indicate the root of the graph. + GW.emitSimpleNode(0, "plaintext=circle", "GraphRoot"); + const SDNode *N = DAG->getRoot().getNode(); + if (N && N->getNodeId() != -1) + GW.emitEdge(0, -1, &SUnits[N->getNodeId()], -1, + "color=blue,style=dashed"); + } } diff --git a/lib/Target/CellSPU/SPUHazardRecognizers.h b/lib/Target/CellSPU/SPUHazardRecognizers.h index 8d74c5c..6b73083 100644 --- a/lib/Target/CellSPU/SPUHazardRecognizers.h +++ b/lib/Target/CellSPU/SPUHazardRecognizers.h @@ -15,7 +15,7 @@ #ifndef SPUHAZRECS_H #define SPUHAZRECS_H -#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/ScheduleDAGSDNodes.h" #include "SPUInstrInfo.h" namespace llvm { diff --git a/lib/Target/PowerPC/PPCHazardRecognizers.h b/lib/Target/PowerPC/PPCHazardRecognizers.h index 7ba2e6e..8957d18 100644 --- a/lib/Target/PowerPC/PPCHazardRecognizers.h +++ b/lib/Target/PowerPC/PPCHazardRecognizers.h @@ -14,7 +14,7 @@ #ifndef PPCHAZRECS_H #define PPCHAZRECS_H -#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/ScheduleDAGSDNodes.h" #include "PPCInstrInfo.h" namespace llvm { |