X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FScheduleDAG.h;h=5dbdd605bc757077991d3bff6a5b28b136224e6d;hb=ad93c4f936d220570535711262e0fff8857f798a;hp=5f9236d401776e75d3b2ae0d2f85b0d8447a567d;hpb=e165a78551a91d8420cd8f074d97701e8788f8b5;p=oota-llvm.git diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index 5f9236d4017..5dbdd605bc7 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -16,20 +16,24 @@ #define LLVM_CODEGEN_SCHEDULEDAG_H #include "llvm/CodeGen/SelectionDAG.h" - -#include +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/SmallSet.h" namespace llvm { struct InstrStage; + struct SUnit; class MachineConstantPool; - class MachineDebugInfo; + class MachineModuleInfo; class MachineInstr; class MRegisterInfo; class SelectionDAG; + class SelectionDAGISel; class SSARegMap; class TargetInstrInfo; class TargetInstrDescriptor; 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 @@ -41,7 +45,7 @@ namespace llvm { 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. + NoopHazard // This instruction can't be emitted, and needs noops. }; /// getHazardType - Return the hazard type of emitting this node. There are @@ -72,43 +76,126 @@ namespace llvm { virtual void EmitNoop() { } }; - + + /// SDep - Scheduling dependency. It keeps track of dependent nodes, + /// cost of the depdenency, etc. + struct SDep { + SUnit *Dep; // Dependent - either a predecessor or a successor. + unsigned Reg; // If non-zero, this dep is a phy register dependency. + int Cost; // Cost of the dependency. + bool isCtrl : 1; // True iff it's a control dependency. + bool isSpecial : 1; // True iff it's a special ctrl dep added during sched. + SDep(SUnit *d, unsigned r, int t, bool c, bool s) + : 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. struct SUnit { SDNode *Node; // Representative node. - std::vector FlaggedNodes; // All nodes flagged to Node. + SmallVector FlaggedNodes;// All nodes flagged to Node. + unsigned InstanceNo; // Instance#. One SDNode can be multiple + // SUnit due to cloning. // Preds/Succs - The SUnits before/after us in the graph. The boolean value // is true if the edge is a token chain edge, false if it is a value edge. - std::set > Preds; // All sunit predecessors. - std::set > Succs; // All sunit successors. + SmallVector Preds; // All sunit predecessors. + SmallVector Succs; // All sunit successors. + typedef SmallVector::iterator pred_iterator; + typedef SmallVector::iterator succ_iterator; + typedef SmallVector::const_iterator const_pred_iterator; + typedef SmallVector::const_iterator const_succ_iterator; + + unsigned NodeNum; // Entry # of node in the node vector. + unsigned short Latency; // Node latency. short NumPreds; // # of preds. short NumSuccs; // # of sucss. short NumPredsLeft; // # of preds not scheduled. short NumSuccsLeft; // # of succs not scheduled. - short NumChainPredsLeft; // # of chain preds not scheduled. - short NumChainSuccsLeft; // # of chain succs not scheduled. bool isTwoAddress : 1; // Is a two-address instruction. - bool isDefNUseOperand : 1; // Is a def&use operand. + bool isCommutable : 1; // Is a commutable instruction. + bool hasPhysRegDefs : 1; // Has physreg defs that are being used. bool isPending : 1; // True once pending. bool isAvailable : 1; // True once available. bool isScheduled : 1; // True once scheduled. - unsigned short Latency; // Node latency. unsigned CycleBound; // Upper/lower cycle to be scheduled at. unsigned Cycle; // Once scheduled, the cycle of the op. unsigned Depth; // Node depth; unsigned Height; // Node height; - unsigned NodeNum; // Entry # of node in the node vector. + const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null. + const TargetRegisterClass *CopySrcRC; SUnit(SDNode *node, unsigned nodenum) - : Node(node), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0), - NumChainPredsLeft(0), NumChainSuccsLeft(0), - isTwoAddress(false), isDefNUseOperand(false), + : Node(node), InstanceNo(0), NodeNum(nodenum), Latency(0), + NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0), + isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false), isPending(false), isAvailable(false), isScheduled(false), - Latency(0), CycleBound(0), Cycle(0), Depth(0), Height(0), - NodeNum(nodenum) {} + CycleBound(0), Cycle(0), Depth(0), Height(0), + CopyDstRC(NULL), CopySrcRC(NULL) {} + + /// addPred - This adds the specified node as a pred of the current node if + /// not already. This returns true if this is a new pred. + bool addPred(SUnit *N, bool isCtrl, bool isSpecial, + unsigned PhyReg = 0, int Cost = 1) { + for (unsigned i = 0, e = Preds.size(); i != e; ++i) + if (Preds[i].Dep == N && + Preds[i].isCtrl == isCtrl && Preds[i].isSpecial == isSpecial) + return false; + Preds.push_back(SDep(N, PhyReg, Cost, isCtrl, isSpecial)); + N->Succs.push_back(SDep(this, PhyReg, Cost, isCtrl, isSpecial)); + if (!isCtrl) { + ++NumPreds; + ++N->NumSuccs; + } + if (!N->isScheduled) + ++NumPredsLeft; + if (!isScheduled) + ++N->NumSuccsLeft; + return true; + } + + bool removePred(SUnit *N, bool isCtrl, bool isSpecial) { + for (SmallVector::iterator I = Preds.begin(), E = Preds.end(); + I != E; ++I) + if (I->Dep == N && I->isCtrl == isCtrl && I->isSpecial == isSpecial) { + bool FoundSucc = false; + for (SmallVector::iterator II = N->Succs.begin(), + EE = N->Succs.end(); II != EE; ++II) + if (II->Dep == this && + II->isCtrl == isCtrl && II->isSpecial == isSpecial) { + FoundSucc = true; + N->Succs.erase(II); + break; + } + assert(FoundSucc && "Mismatching preds / succs lists!"); + Preds.erase(I); + if (!isCtrl) { + --NumPreds; + --N->NumSuccs; + } + if (!N->isScheduled) + --NumPredsLeft; + if (!isScheduled) + --N->NumSuccsLeft; + return true; + } + return false; + } + + bool isPred(SUnit *N) { + for (unsigned i = 0, e = Preds.size(); i != e; ++i) + if (Preds[i].Dep == N) + return true; + return false; + } + + bool isSucc(SUnit *N) { + for (unsigned i = 0, e = Succs.size(); i != e; ++i) + if (Succs[i].Dep == N) + return true; + return false; + } void dump(const SelectionDAG *G) const; void dumpAll(const SelectionDAG *G) const; @@ -126,35 +213,31 @@ namespace llvm { public: virtual ~SchedulingPriorityQueue() {} - virtual void initNodes(const std::vector &SUnits) = 0; + virtual void initNodes(DenseMap > &SUMap, + std::vector &SUnits) = 0; + virtual void addNode(const SUnit *SU) = 0; + virtual void updateNode(const SUnit *SU) = 0; virtual void releaseState() = 0; - + + virtual unsigned size() const = 0; virtual bool empty() const = 0; virtual void push(SUnit *U) = 0; virtual void push_all(const std::vector &Nodes) = 0; virtual SUnit *pop() = 0; + virtual void remove(SUnit *SU) = 0; + /// ScheduledNode - As each node is scheduled, this method is invoked. This /// allows the priority function to adjust the priority of node that have /// already been emitted. virtual void ScheduledNode(SUnit *Node) {} + + virtual void UnscheduledNode(SUnit *Node) {} }; class ScheduleDAG { public: - - // Scheduling heuristics - enum SchedHeuristics { - defaultScheduling, // Let the target specify its preference. - noScheduling, // No scheduling, emit breadth first sequence. - simpleScheduling, // Two pass, min. critical path, max. utilization. - simpleNoItinScheduling, // Same as above exact using generic latency. - listSchedulingBURR, // Bottom-up reg reduction list scheduling. - listSchedulingTDRR, // Top-down reg reduction list scheduling. - listSchedulingTD // Top-down list scheduler. - }; - SelectionDAG &DAG; // DAG of the current basic block MachineBasicBlock *BB; // Current basic block const TargetMachine &TM; // Target processor @@ -162,10 +245,12 @@ namespace llvm { const MRegisterInfo *MRI; // Target processor register info SSARegMap *RegMap; // Virtual/real register map MachineConstantPool *ConstPool; // Target constant pool - std::vector Sequence; // The schedule. Null SUnit*'s represent - // noop instructions. - std::map SUnitMap; // SDNode to SUnit mapping (n -> 1). + std::vector Sequence; // The schedule. Null SUnit*'s + // represent noop instructions. + DenseMap > SUnitMap; + // SDNode to SUnit mapping (n -> n). std::vector SUnits; // The scheduling units. + SmallSet CommuteSet; // Nodes the should be commuted. ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb, const TargetMachine &tm) @@ -173,6 +258,11 @@ namespace llvm { virtual ~ScheduleDAG() {} + /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered + /// using 'dot'. + /// + void viewGraph(); + /// Run - perform scheduling. /// MachineBasicBlock *Run(); @@ -198,26 +288,57 @@ namespace llvm { 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(); + /// ComputeLatency - Compute node latency. + /// + void ComputeLatency(SUnit *SU); + /// 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 an optional chain operand, then flag operands. Compute the + /// number of actual operands that will go into the machine instr. + static unsigned CountOperands(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, std::map &VRBaseMap); + void EmitNode(SDNode *Node, unsigned InstNo, + DenseMap &VRBaseMap); /// EmitNoop - Emit a noop instruction. /// void EmitNoop(); + + void EmitCrossRCCopy(SUnit *SU, DenseMap &VRBaseMap); + + /// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an + /// implicit physical register output. + void EmitCopyFromReg(SDNode *Node, unsigned ResNo, unsigned InstNo, + unsigned SrcReg, + DenseMap &VRBaseMap); + void CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, + const TargetInstrDescriptor &II, + DenseMap &VRBaseMap); + void EmitSchedule(); void dumpSchedule() const; @@ -227,34 +348,101 @@ namespace llvm { virtual void Schedule() {} private: + /// EmitSubregNode - Generate machine code for subreg nodes. + /// + void EmitSubregNode(SDNode *Node, + DenseMap &VRBaseMap); + void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum, const TargetInstrDescriptor *II, - std::map &VRBaseMap); + DenseMap &VRBaseMap); }; - ScheduleDAG *createBFS_DAGScheduler(SelectionDAG &DAG, MachineBasicBlock *BB); - - /// createSimpleDAGScheduler - This creates a simple two pass instruction - /// scheduler. - ScheduleDAG* createSimpleDAGScheduler(bool NoItins, SelectionDAG &DAG, - MachineBasicBlock *BB); - /// createBURRListDAGScheduler - This creates a bottom up register usage /// reduction list scheduler. - ScheduleDAG* createBURRListDAGScheduler(SelectionDAG &DAG, + ScheduleDAG* createBURRListDAGScheduler(SelectionDAGISel *IS, + SelectionDAG *DAG, MachineBasicBlock *BB); /// createTDRRListDAGScheduler - This creates a top down register usage /// reduction list scheduler. - ScheduleDAG* createTDRRListDAGScheduler(SelectionDAG &DAG, + ScheduleDAG* createTDRRListDAGScheduler(SelectionDAGISel *IS, + SelectionDAG *DAG, MachineBasicBlock *BB); /// createTDListDAGScheduler - This creates a top-down list scheduler with - /// the specified hazard recognizer. This takes ownership of the hazard - /// recognizer and deletes it when done. - ScheduleDAG* createTDListDAGScheduler(SelectionDAG &DAG, - MachineBasicBlock *BB, - HazardRecognizer *HR); + /// a hazard recognizer. + ScheduleDAG* createTDListDAGScheduler(SelectionDAGISel *IS, + SelectionDAG *DAG, + MachineBasicBlock *BB); + + /// createDefaultScheduler - This creates an instruction scheduler appropriate + /// for the target. + ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS, + SelectionDAG *DAG, + MachineBasicBlock *BB); + + class SUnitIterator : public forward_iterator { + SUnit *Node; + unsigned Operand; + + SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {} + public: + bool operator==(const SUnitIterator& x) const { + return Operand == x.Operand; + } + bool operator!=(const SUnitIterator& x) const { return !operator==(x); } + + const SUnitIterator &operator=(const SUnitIterator &I) { + assert(I.Node == Node && "Cannot assign iterators to two different nodes!"); + Operand = I.Operand; + return *this; + } + + pointer operator*() const { + return Node->Preds[Operand].Dep; + } + pointer operator->() const { return operator*(); } + + SUnitIterator& operator++() { // Preincrement + ++Operand; + return *this; + } + SUnitIterator operator++(int) { // Postincrement + SUnitIterator tmp = *this; ++*this; return tmp; + } + + static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); } + static SUnitIterator end (SUnit *N) { + return SUnitIterator(N, N->Preds.size()); + } + + unsigned getOperand() const { return Operand; } + const SUnit *getNode() const { return Node; } + bool isCtrlDep() const { return Node->Preds[Operand].isCtrl; } + }; + + template <> struct GraphTraits { + typedef SUnit NodeType; + typedef SUnitIterator ChildIteratorType; + static inline NodeType *getEntryNode(SUnit *N) { return N; } + static inline ChildIteratorType child_begin(NodeType *N) { + return SUnitIterator::begin(N); + } + static inline ChildIteratorType child_end(NodeType *N) { + return SUnitIterator::end(N); + } + }; + + template <> struct GraphTraits : public GraphTraits { + typedef std::vector::iterator nodes_iterator; + static nodes_iterator nodes_begin(ScheduleDAG *G) { + return G->SUnits.begin(); + } + static nodes_iterator nodes_end(ScheduleDAG *G) { + return G->SUnits.end(); + } + }; } #endif