X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FScheduleDAG.h;h=5dbdd605bc757077991d3bff6a5b28b136224e6d;hb=ad93c4f936d220570535711262e0fff8857f798a;hp=5d85d374338d79502db0b4bb28b7ec26072f898f;hpb=228a18e0f220fb85ee06fd5bfa29304e57047ff1;p=oota-llvm.git diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index 5d85d374338..5dbdd605bc7 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -16,13 +16,15 @@ #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; @@ -31,6 +33,7 @@ namespace llvm { 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 @@ -73,69 +76,125 @@ 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. 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. - SmallVector, 4> Preds; // All sunit predecessors. - SmallVector, 4> Succs; // All sunit successors. - - typedef SmallVector, 4>::iterator pred_iterator; - typedef SmallVector, 4>::iterator succ_iterator; - typedef SmallVector, 4>::const_iterator - const_pred_iterator; - typedef SmallVector, 4>::const_iterator - const_succ_iterator; + 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 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), isCommutable(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 isChain) { + 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].first == N && Preds[i].second == isChain) + if (Preds[i].Dep == N && + Preds[i].isCtrl == isCtrl && Preds[i].isSpecial == isSpecial) return false; - Preds.push_back(std::make_pair(N, isChain)); + 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; } - /// addSucc - This adds the specified node as a succ of the current node if - /// not already. This returns true if this is a new succ. - bool addSucc(SUnit *N, bool isChain) { + 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].first == N && Succs[i].second == isChain) - return false; - Succs.push_back(std::make_pair(N, isChain)); - return true; + if (Succs[i].Dep == N) + return true; + return false; } void dump(const SelectionDAG *G) const; @@ -154,19 +213,27 @@ namespace llvm { public: virtual ~SchedulingPriorityQueue() {} - virtual void initNodes(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 { @@ -180,9 +247,10 @@ namespace llvm { 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). + DenseMap > SUnitMap; + // SDNode to SUnit mapping (n -> n). std::vector SUnits; // The scheduling units. - std::set CommuteSet; // Nodes the should be commuted. + SmallSet CommuteSet; // Nodes the should be commuted. ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb, const TargetMachine &tm) @@ -190,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(); @@ -215,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; @@ -244,29 +348,16 @@ 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); }; - /// createBFS_DAGScheduler - This creates a simple breadth first instruction - /// scheduler. - ScheduleDAG *createBFS_DAGScheduler(SelectionDAGISel *IS, - SelectionDAG *DAG, - MachineBasicBlock *BB); - - /// createSimpleDAGScheduler - This creates a simple two pass instruction - /// scheduler using instruction itinerary. - ScheduleDAG* createSimpleDAGScheduler(SelectionDAGISel *IS, - SelectionDAG *DAG, - MachineBasicBlock *BB); - - /// createNoItinsDAGScheduler - This creates a simple two pass instruction - /// scheduler without using instruction itinerary. - ScheduleDAG* createNoItinsDAGScheduler(SelectionDAGISel *IS, - SelectionDAG *DAG, - MachineBasicBlock *BB); - /// createBURRListDAGScheduler - This creates a bottom up register usage /// reduction list scheduler. ScheduleDAG* createBURRListDAGScheduler(SelectionDAGISel *IS, @@ -290,6 +381,68 @@ namespace llvm { 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