X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FScheduleDAG.h;h=5dbdd605bc757077991d3bff6a5b28b136224e6d;hb=ad93c4f936d220570535711262e0fff8857f798a;hp=fd72aebdb16777133eb28845396e22dbf98ca646;hpb=e24f8f1ec9277dc80ebf38f0d914053f8c31caf1;p=oota-llvm.git diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index fd72aebdb16..5dbdd605bc7 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -17,10 +17,12 @@ #include "llvm/CodeGen/SelectionDAG.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/SmallSet.h" namespace llvm { struct InstrStage; + struct SUnit; class MachineConstantPool; class MachineModuleInfo; class MachineInstr; @@ -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,20 +213,27 @@ namespace llvm { public: virtual ~SchedulingPriorityQueue() {} - virtual void initNodes(DenseMap &SUMap, + 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 { @@ -181,7 +247,8 @@ namespace llvm { MachineConstantPool *ConstPool; // Target constant pool std::vector Sequence; // The schedule. Null SUnit*'s // represent noop instructions. - DenseMap SUnitMap; // SDNode to SUnit mapping (n -> 1). + DenseMap > SUnitMap; + // SDNode to SUnit mapping (n -> n). std::vector SUnits; // The scheduling units. SmallSet CommuteSet; // Nodes the should be commuted. @@ -191,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(); @@ -216,11 +288,19 @@ 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(); @@ -240,12 +320,25 @@ namespace llvm { /// VRBaseMap contains, for each already emitted node, the first virtual /// register number for the results of the node. /// - void EmitNode(SDNode *Node, DenseMap &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; @@ -265,24 +358,6 @@ namespace llvm { 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, @@ -306,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