diff options
23 files changed, 1341 insertions, 889 deletions
diff --git a/lib/CodeGen/SelectionDAG/LatencyPriorityQueue.h b/include/llvm/CodeGen/LatencyPriorityQueue.h index 5b2b02b..f04d2ed 100644 --- a/lib/CodeGen/SelectionDAG/LatencyPriorityQueue.h +++ b/include/llvm/CodeGen/LatencyPriorityQueue.h @@ -45,7 +45,7 @@ namespace llvm { std::vector<unsigned> NumNodesSolelyBlocking; PriorityQueue<SUnit*, std::vector<SUnit*>, latency_sort> Queue; - public: +public: LatencyPriorityQueue() : Queue(latency_sort(this)) { } @@ -113,7 +113,7 @@ namespace llvm { // the node available. void ScheduledNode(SUnit *Node); - private: +private: void CalculatePriorities(); int CalcLatency(const SUnit &SU); void AdjustPriorityOfUnscheduledPreds(SUnit *SU); diff --git a/include/llvm/CodeGen/LinkAllCodegenComponents.h b/include/llvm/CodeGen/LinkAllCodegenComponents.h index 2853500..610d66b 100644 --- a/include/llvm/CodeGen/LinkAllCodegenComponents.h +++ b/include/llvm/CodeGen/LinkAllCodegenComponents.h @@ -16,7 +16,7 @@ #define LLVM_CODEGEN_LINKALLCODEGENCOMPONENTS_H #include "llvm/CodeGen/Passes.h" -#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/ScheduleDAGSDNodes.h" #include "llvm/CodeGen/GCs.h" namespace { diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index 49dabe6..ee25203 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -8,7 +8,7 @@ //===----------------------------------------------------------------------===// // // This file implements the ScheduleDAG class, which is used as the common -// base class for SelectionDAG-based instruction scheduler. +// base class for instruction schedulers. // //===----------------------------------------------------------------------===// @@ -16,10 +16,9 @@ #define LLVM_CODEGEN_SCHEDULEDAG_H #include "llvm/CodeGen/MachineBasicBlock.h" -#include "llvm/CodeGen/SelectionDAG.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/SmallVector.h" namespace llvm { struct SUnit; @@ -31,51 +30,13 @@ namespace llvm { class TargetRegisterInfo; class ScheduleDAG; class SelectionDAG; - class SelectionDAGISel; + class SDNode; class TargetInstrInfo; class TargetInstrDesc; class TargetLowering; class TargetMachine; class TargetRegisterClass; - - /// HazardRecognizer - This determines whether or not an instruction can be - /// issued this cycle, and whether or not a noop needs to be inserted to handle - /// the hazard. - class HazardRecognizer { - public: - virtual ~HazardRecognizer(); - - enum HazardType { - NoHazard, // This instruction can be emitted at this cycle. - Hazard, // This instruction can't be emitted at this cycle. - NoopHazard // This instruction can't be emitted, and needs noops. - }; - - /// getHazardType - Return the hazard type of emitting this node. There are - /// three possible results. Either: - /// * NoHazard: it is legal to issue this instruction on this cycle. - /// * Hazard: issuing this instruction would stall the machine. If some - /// other instruction is available, issue it first. - /// * NoopHazard: issuing this instruction would break the program. If - /// some other instruction can be issued, do so, otherwise issue a noop. - virtual HazardType getHazardType(SDNode *) { - return NoHazard; - } - - /// EmitInstruction - This callback is invoked when an instruction is - /// emitted, to advance the hazard state. - virtual void EmitInstruction(SDNode *) {} - - /// AdvanceCycle - This callback is invoked when no instructions can be - /// issued on this cycle without a hazard. This should increment the - /// internal state of the hazard recognizer so that previously "Hazard" - /// instructions will now not be hazards. - virtual void AdvanceCycle() {} - - /// EmitNoop - This callback is invoked when a noop was added to the - /// instruction stream. - virtual void EmitNoop() {} - }; + template<class Graph> class GraphWriter; /// SDep - Scheduling dependency. It keeps track of dependent nodes, /// cost of the depdenency, etc. @@ -89,8 +50,7 @@ namespace llvm { : Dep(d), Reg(r), Cost(t), isCtrl(c), isSpecial(s) {} }; - /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or - /// a group of nodes flagged together. + /// SUnit - Scheduling unit. This is a node in the scheduling DAG. struct SUnit { private: SDNode *Node; // Representative node. @@ -294,12 +254,11 @@ namespace llvm { std::vector<SUnit*> Sequence; // The schedule. Null SUnit*'s // represent noop instructions. std::vector<SUnit> SUnits; // The scheduling units. - SmallSet<SDNode*, 16> CommuteSet; // Nodes that should be commuted. ScheduleDAG(SelectionDAG *dag, MachineBasicBlock *bb, const TargetMachine &tm); - virtual ~ScheduleDAG() {} + virtual ~ScheduleDAG(); /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered /// using 'dot'. @@ -310,84 +269,27 @@ namespace llvm { /// void Run(); - /// isPassiveNode - Return true if the node is a non-scheduled leaf. + /// BuildSchedUnits - Build SUnits and set up their Preds and Succs + /// to form the scheduling dependency graph. /// - static bool isPassiveNode(SDNode *Node) { - if (isa<ConstantSDNode>(Node)) return true; - if (isa<ConstantFPSDNode>(Node)) return true; - if (isa<RegisterSDNode>(Node)) return true; - if (isa<GlobalAddressSDNode>(Node)) return true; - if (isa<BasicBlockSDNode>(Node)) return true; - if (isa<FrameIndexSDNode>(Node)) return true; - if (isa<ConstantPoolSDNode>(Node)) return true; - if (isa<JumpTableSDNode>(Node)) return true; - if (isa<ExternalSymbolSDNode>(Node)) return true; - if (isa<MemOperandSDNode>(Node)) return true; - if (Node->getOpcode() == ISD::EntryToken) return true; - return false; - } - - /// NewSUnit - Creates a new SUnit and return a ptr to it. - /// - SUnit *NewSUnit(SDNode *N) { - SUnits.push_back(SUnit(N, (unsigned)SUnits.size())); - SUnits.back().OrigNode = &SUnits.back(); - return &SUnits.back(); - } - - /// NewSUnit - Creates a new SUnit and return a ptr to it. - /// - SUnit *NewSUnit(MachineInstr *MI) { - SUnits.push_back(SUnit(MI, (unsigned)SUnits.size())); - SUnits.back().OrigNode = &SUnits.back(); - return &SUnits.back(); - } - - /// Clone - Creates a clone of the specified SUnit. It does not copy the - /// predecessors / successors info nor the temporary scheduling states. - SUnit *Clone(SUnit *N); - - /// 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 BuildSchedUnits(); + virtual void BuildSchedUnits() = 0; /// ComputeLatency - Compute node latency. /// - void ComputeLatency(SUnit *SU); + virtual void ComputeLatency(SUnit *SU) { SU->Latency = 1; } /// CalculateDepths, CalculateHeights - Calculate node depth / height. /// void CalculateDepths(); void CalculateHeights(); - /// 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 machine instrs.) - static unsigned CountResults(SDNode *Node); - - /// 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 flag operands. Compute the number of - /// actual operands that will go into the resulting MachineInstr. - static unsigned CountOperands(SDNode *Node); - - /// ComputeMemOperandsEnd - Find the index one past the last - /// MemOperandSDNode operand - static unsigned ComputeMemOperandsEnd(SDNode *Node); - - /// EmitNode - Generate machine code for an node and needed dependencies. - /// VRBaseMap contains, for each already emitted node, the first virtual - /// register number for the results of the node. - /// - void EmitNode(SDNode *Node, bool IsClone, - DenseMap<SDValue, unsigned> &VRBaseMap); - + protected: /// EmitNoop - Emit a noop instruction. /// void EmitNoop(); - MachineBasicBlock *EmitSchedule(); + public: + virtual MachineBasicBlock *EmitSchedule() = 0; void dumpSchedule() const; @@ -396,41 +298,22 @@ namespace llvm { /// virtual void Schedule() = 0; - /// getGraphpNodeLabel - Return a label for an SUnit node in a Graphviz or similar - /// graph visualization. - virtual std::string getGraphNodeLabel(const SUnit *SU) const; + virtual void dumpNode(const SUnit *SU) const = 0; - private: - /// EmitSubregNode - Generate machine code for subreg nodes. - /// - void EmitSubregNode(SDNode *Node, - DenseMap<SDValue, unsigned> &VRBaseMap); + /// getGraphNodeLabel - Return a label for an SUnit node in a visualization + /// of the ScheduleDAG. + virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0; - /// getVR - Return the virtual register corresponding to the specified result - /// of the specified node. - unsigned getVR(SDValue Op, DenseMap<SDValue, unsigned> &VRBaseMap); - - /// getDstOfCopyToRegUse - If the only use of the specified result number of - /// node is a CopyToReg, return its destination register. Return 0 otherwise. - unsigned getDstOfOnlyCopyToRegUse(SDNode *Node, unsigned ResNo) const; + /// addCustomGraphFeatures - Add custom features for a visualization of + /// the ScheduleDAG. + virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const {} - void AddOperand(MachineInstr *MI, SDValue Op, unsigned IIOpNum, - const TargetInstrDesc *II, - DenseMap<SDValue, unsigned> &VRBaseMap); + protected: void AddMemOperand(MachineInstr *MI, const MachineMemOperand &MO); void EmitCrossRCCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap); - /// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an - /// implicit physical register output. - void EmitCopyFromReg(SDNode *Node, unsigned ResNo, bool IsClone, - unsigned SrcReg, - DenseMap<SDValue, unsigned> &VRBaseMap); - - void CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, - const TargetInstrDesc &II, - DenseMap<SDValue, unsigned> &VRBaseMap); - + private: /// EmitLiveInCopy - Emit a copy for a live in physical register. If the /// physical register has only a single copy use, then coalesced the copy /// if possible. @@ -444,53 +327,8 @@ namespace llvm { /// and if it has live ins that need to be copied into vregs, emit the /// copies into the top of the block. void EmitLiveInCopies(MachineBasicBlock *MBB); - - /// BuildSchedUnitsFromMBB - Build SUnits from the MachineBasicBlock. - /// This SUnit graph is similar to the pre-regalloc SUnit graph, but represents - /// MachineInstrs directly instead of SDNodes. - void BuildSchedUnitsFromMBB(); }; - /// createBURRListDAGScheduler - This creates a bottom up register usage - /// reduction list scheduler. - ScheduleDAG* createBURRListDAGScheduler(SelectionDAGISel *IS, - SelectionDAG *DAG, - const TargetMachine *TM, - MachineBasicBlock *BB, - bool Fast); - - /// createTDRRListDAGScheduler - This creates a top down register usage - /// reduction list scheduler. - ScheduleDAG* createTDRRListDAGScheduler(SelectionDAGISel *IS, - SelectionDAG *DAG, - const TargetMachine *TM, - MachineBasicBlock *BB, - bool Fast); - - /// createTDListDAGScheduler - This creates a top-down list scheduler with - /// a hazard recognizer. - ScheduleDAG* createTDListDAGScheduler(SelectionDAGISel *IS, - SelectionDAG *DAG, - const TargetMachine *TM, - MachineBasicBlock *BB, - bool Fast); - - /// createFastDAGScheduler - This creates a "fast" scheduler. - /// - ScheduleDAG *createFastDAGScheduler(SelectionDAGISel *IS, - SelectionDAG *DAG, - const TargetMachine *TM, - MachineBasicBlock *BB, - bool Fast); - - /// createDefaultScheduler - This creates an instruction scheduler appropriate - /// for the target. - ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS, - SelectionDAG *DAG, - const TargetMachine *TM, - MachineBasicBlock *BB, - bool Fast); - class SUnitIterator : public forward_iterator<SUnit, ptrdiff_t> { SUnit *Node; unsigned Operand; diff --git a/include/llvm/CodeGen/ScheduleDAGInstrs.h b/include/llvm/CodeGen/ScheduleDAGInstrs.h new file mode 100644 index 0000000..703c5b0 --- /dev/null +++ b/include/llvm/CodeGen/ScheduleDAGInstrs.h @@ -0,0 +1,69 @@ +//==- llvm/CodeGen/ScheduleDAGInstrs.h - MachineInstr Scheduling -*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the ScheduleDAGInstrs class, which implements +// scheduling for a MachineInstr-based dependency graph. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_SCHEDULEDAGINSTRS_H +#define LLVM_CODEGEN_SCHEDULEDAGINSTRS_H + +#include "llvm/CodeGen/ScheduleDAG.h" + +namespace llvm { + struct SUnit; + class MachineConstantPool; + class MachineFunction; + class MachineModuleInfo; + class MachineRegisterInfo; + class MachineInstr; + class TargetRegisterInfo; + class ScheduleDAG; + class SelectionDAG; + class SelectionDAGISel; + class TargetInstrInfo; + class TargetInstrDesc; + class TargetLowering; + class TargetMachine; + class TargetRegisterClass; + + class ScheduleDAGInstrs : public ScheduleDAG { + public: + ScheduleDAGInstrs(MachineBasicBlock *bb, + const TargetMachine &tm); + + virtual ~ScheduleDAGInstrs() {} + + /// NewSUnit - Creates a new SUnit and return a ptr to it. + /// + SUnit *NewSUnit(MachineInstr *MI) { + SUnits.push_back(SUnit(MI, (unsigned)SUnits.size())); + SUnits.back().OrigNode = &SUnits.back(); + return &SUnits.back(); + } + + /// BuildSchedUnits - Build SUnits from the MachineBasicBlock that we are + /// input. + virtual void BuildSchedUnits(); + + virtual MachineBasicBlock *EmitSchedule(); + + /// Schedule - Order nodes according to selected style, filling + /// in the Sequence member. + /// + virtual void Schedule() = 0; + + virtual void dumpNode(const SUnit *SU) const; + + virtual std::string getGraphNodeLabel(const SUnit *SU) const; + }; +} + +#endif diff --git a/include/llvm/CodeGen/ScheduleDAGSDNodes.h b/include/llvm/CodeGen/ScheduleDAGSDNodes.h new file mode 100644 index 0000000..caa1d0a --- /dev/null +++ b/include/llvm/CodeGen/ScheduleDAGSDNodes.h @@ -0,0 +1,233 @@ +//===---- llvm/CodeGen/ScheduleDAGSDNodes.h - SDNode Scheduling -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the ScheduleDAGSDNodes class, which implements +// scheduling for an SDNode-based dependency graph. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_SCHEDULEDAGSDNODES_H +#define LLVM_CODEGEN_SCHEDULEDAGSDNODES_H + +#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/SelectionDAG.h" +#include "llvm/ADT/SmallSet.h" + +namespace llvm { + struct SUnit; + class MachineConstantPool; + class MachineFunction; + class MachineModuleInfo; + class MachineRegisterInfo; + class MachineInstr; + class TargetRegisterInfo; + class ScheduleDAG; + class SelectionDAG; + class SelectionDAGISel; + class TargetInstrInfo; + class TargetInstrDesc; + class TargetLowering; + class TargetMachine; + class TargetRegisterClass; + + /// HazardRecognizer - This determines whether or not an instruction can be + /// issued this cycle, and whether or not a noop needs to be inserted to handle + /// the hazard. + class HazardRecognizer { + public: + virtual ~HazardRecognizer(); + + enum HazardType { + NoHazard, // This instruction can be emitted at this cycle. + Hazard, // This instruction can't be emitted at this cycle. + NoopHazard // This instruction can't be emitted, and needs noops. + }; + + /// getHazardType - Return the hazard type of emitting this node. There are + /// three possible results. Either: + /// * NoHazard: it is legal to issue this instruction on this cycle. + /// * Hazard: issuing this instruction would stall the machine. If some + /// other instruction is available, issue it first. + /// * NoopHazard: issuing this instruction would break the program. If + /// some other instruction can be issued, do so, otherwise issue a noop. + virtual HazardType getHazardType(SDNode *) { + return NoHazard; + } + + /// EmitInstruction - This callback is invoked when an instruction is + /// emitted, to advance the hazard state. + virtual void EmitInstruction(SDNode *) {} + + /// AdvanceCycle - This callback is invoked when no instructions can be + /// issued on this cycle without a hazard. This should increment the + /// internal state of the hazard recognizer so that previously "Hazard" + /// instructions will now not be hazards. + virtual void AdvanceCycle() {} + + /// EmitNoop - This callback is invoked when a noop was added to the + /// instruction stream. + virtual void EmitNoop() {} + }; + + class ScheduleDAGSDNodes : public ScheduleDAG { + public: + SmallSet<SDNode*, 16> CommuteSet; // Nodes that should be commuted. + + ScheduleDAGSDNodes(SelectionDAG *dag, MachineBasicBlock *bb, + const TargetMachine &tm); + + virtual ~ScheduleDAGSDNodes() {} + + /// isPassiveNode - Return true if the node is a non-scheduled leaf. + /// + static bool isPassiveNode(SDNode *Node) { + if (isa<ConstantSDNode>(Node)) return true; + if (isa<ConstantFPSDNode>(Node)) return true; + if (isa<RegisterSDNode>(Node)) return true; + if (isa<GlobalAddressSDNode>(Node)) return true; + if (isa<BasicBlockSDNode>(Node)) return true; + if (isa<FrameIndexSDNode>(Node)) return true; + if (isa<ConstantPoolSDNode>(Node)) return true; + if (isa<JumpTableSDNode>(Node)) return true; + if (isa<ExternalSymbolSDNode>(Node)) return true; + if (isa<MemOperandSDNode>(Node)) return true; + if (Node->getOpcode() == ISD::EntryToken) return true; + return false; + } + + /// NewSUnit - Creates a new SUnit and return a ptr to it. + /// + SUnit *NewSUnit(SDNode *N) { + SUnits.push_back(SUnit(N, (unsigned)SUnits.size())); + SUnits.back().OrigNode = &SUnits.back(); + return &SUnits.back(); + } + + /// Clone - Creates a clone of the specified SUnit. It does not copy the + /// predecessors / successors info nor the temporary scheduling states. + /// + SUnit *Clone(SUnit *N); + + virtual SelectionDAG *getDAG() { return DAG; } + + /// 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. + virtual void BuildSchedUnits(); + + /// ComputeLatency - Compute node latency. + /// + virtual void ComputeLatency(SUnit *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 machine instrs.) + static unsigned CountResults(SDNode *Node); + + /// 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 flag operands. Compute the number of + /// actual operands that will go into the resulting MachineInstr. + static unsigned CountOperands(SDNode *Node); + + /// ComputeMemOperandsEnd - Find the index one past the last + /// MemOperandSDNode operand + static unsigned ComputeMemOperandsEnd(SDNode *Node); + + /// EmitNode - Generate machine code for an node and needed dependencies. + /// VRBaseMap contains, for each already emitted node, the first virtual + /// register number for the results of the node. + /// + void EmitNode(SDNode *Node, bool IsClone, + DenseMap<SDValue, unsigned> &VRBaseMap); + + virtual MachineBasicBlock *EmitSchedule(); + + /// Schedule - Order nodes according to selected style, filling + /// in the Sequence member. + /// + virtual void Schedule() = 0; + + virtual void dumpNode(const SUnit *SU) const; + + virtual std::string getGraphNodeLabel(const SUnit *SU) const; + + virtual void getCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const; + + private: + /// EmitSubregNode - Generate machine code for subreg nodes. + /// + void EmitSubregNode(SDNode *Node, + DenseMap<SDValue, unsigned> &VRBaseMap); + + /// getVR - Return the virtual register corresponding to the specified result + /// of the specified node. + unsigned getVR(SDValue Op, DenseMap<SDValue, unsigned> &VRBaseMap); + + /// getDstOfCopyToRegUse - If the only use of the specified result number of + /// node is a CopyToReg, return its destination register. Return 0 otherwise. + unsigned getDstOfOnlyCopyToRegUse(SDNode *Node, unsigned ResNo) const; + + void AddOperand(MachineInstr *MI, SDValue Op, unsigned IIOpNum, + const TargetInstrDesc *II, + DenseMap<SDValue, unsigned> &VRBaseMap); + + /// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an + /// implicit physical register output. + void EmitCopyFromReg(SDNode *Node, unsigned ResNo, bool IsClone, + unsigned SrcReg, + DenseMap<SDValue, unsigned> &VRBaseMap); + + void CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, + const TargetInstrDesc &II, + DenseMap<SDValue, unsigned> &VRBaseMap); + }; + + /// createBURRListDAGScheduler - This creates a bottom up register usage + /// reduction list scheduler. + ScheduleDAG* createBURRListDAGScheduler(SelectionDAGISel *IS, + SelectionDAG *DAG, + const TargetMachine *TM, + MachineBasicBlock *BB, + bool Fast); + + /// createTDRRListDAGScheduler - This creates a top down register usage + /// reduction list scheduler. + ScheduleDAG* createTDRRListDAGScheduler(SelectionDAGISel *IS, + SelectionDAG *DAG, + const TargetMachine *TM, + MachineBasicBlock *BB, + bool Fast); + + /// createTDListDAGScheduler - This creates a top-down list scheduler with + /// a hazard recognizer. + ScheduleDAG* createTDListDAGScheduler(SelectionDAGISel *IS, + SelectionDAG *DAG, + const TargetMachine *TM, + MachineBasicBlock *BB, + bool Fast); + + /// createFastDAGScheduler - This creates a "fast" scheduler. + /// + ScheduleDAG *createFastDAGScheduler(SelectionDAGISel *IS, + SelectionDAG *DAG, + const TargetMachine *TM, + MachineBasicBlock *BB, + bool Fast); + + /// createDefaultScheduler - This creates an instruction scheduler appropriate + /// for the target. + ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS, + SelectionDAG *DAG, + const TargetMachine *TM, + MachineBasicBlock *BB, + bool Fast); +} + +#endif 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/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 { |