diff options
Diffstat (limited to 'llvm/include/llvm/CodeGen/ScheduleDAG.h')
| -rw-r--r-- | llvm/include/llvm/CodeGen/ScheduleDAG.h | 206 |
1 files changed, 22 insertions, 184 deletions
diff --git a/llvm/include/llvm/CodeGen/ScheduleDAG.h b/llvm/include/llvm/CodeGen/ScheduleDAG.h index 49dabe67580..ee252033ada 100644 --- a/llvm/include/llvm/CodeGen/ScheduleDAG.h +++ b/llvm/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; |
