diff options
Diffstat (limited to 'include/llvm/CodeGen/ScheduleDAG.h')
| -rw-r--r-- | include/llvm/CodeGen/ScheduleDAG.h | 85 |
1 files changed, 61 insertions, 24 deletions
diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index 076268b..3864ffd 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -221,6 +221,9 @@ namespace llvm { } }; + template <> + struct isPodLike<SDep> { static const bool value = true; }; + /// SUnit - Scheduling unit. This is a node in the scheduling DAG. class SUnit { private: @@ -229,9 +232,8 @@ namespace llvm { public: SUnit *OrigNode; // If not this, the node from which // this node was cloned. - - // 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. + + // Preds/Succs - The SUnits before/after us in the graph. SmallVector<SDep, 4> Preds; // All sunit predecessors. SmallVector<SDep, 4> Succs; // All sunit successors. @@ -242,11 +244,13 @@ namespace llvm { unsigned NodeNum; // Entry # of node in the node vector. unsigned NodeQueueId; // Queue id of node. - unsigned short Latency; // Node latency. unsigned NumPreds; // # of SDep::Data preds. unsigned NumSuccs; // # of SDep::Data sucss. unsigned NumPredsLeft; // # of preds not scheduled. unsigned NumSuccsLeft; // # of succs not scheduled. + unsigned short NumRegDefsLeft; // # of reg defs with no scheduled use. + unsigned short Latency; // Node latency. + bool isCall : 1; // Is a function call. 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. @@ -267,13 +271,14 @@ namespace llvm { public: const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null. const TargetRegisterClass *CopySrcRC; - + /// SUnit - Construct an SUnit for pre-regalloc scheduling to represent /// an SDNode and any nodes flagged to it. SUnit(SDNode *node, unsigned nodenum) : Node(node), Instr(0), OrigNode(0), NodeNum(nodenum), - NodeQueueId(0), Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), - NumSuccsLeft(0), isTwoAddress(false), isCommutable(false), + NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), + NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), + isCall(false), isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), isPending(false), isAvailable(false), isScheduled(false), isScheduleHigh(false), isCloned(false), @@ -285,8 +290,9 @@ namespace llvm { /// a MachineInstr. SUnit(MachineInstr *instr, unsigned nodenum) : Node(0), Instr(instr), OrigNode(0), NodeNum(nodenum), - NodeQueueId(0), Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), - NumSuccsLeft(0), isTwoAddress(false), isCommutable(false), + NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), + NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), + isCall(false), isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), isPending(false), isAvailable(false), isScheduled(false), isScheduleHigh(false), isCloned(false), @@ -297,8 +303,9 @@ namespace llvm { /// SUnit - Construct a placeholder SUnit. SUnit() : Node(0), Instr(0), OrigNode(0), NodeNum(~0u), - NodeQueueId(0), Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), - NumSuccsLeft(0), isTwoAddress(false), isCommutable(false), + NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), + NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), + isCall(false), isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), isPending(false), isAvailable(false), isScheduled(false), isScheduleHigh(false), isCloned(false), @@ -320,6 +327,10 @@ namespace llvm { return Node; } + /// isInstr - Return true if this SUnit refers to a machine instruction as + /// opposed to an SDNode. + bool isInstr() const { return Instr; } + /// setInstr - Assign the instruction for the SUnit. /// This may be used during post-regalloc scheduling. void setInstr(MachineInstr *MI) { @@ -337,7 +348,7 @@ namespace llvm { /// addPred - This adds the specified edge as a pred of the current node if /// not already. It also adds the current node as a successor of the /// specified node. - void addPred(const SDep &D); + bool addPred(const SDep &D); /// removePred - This removes the specified edge as a pred of the current /// node if it exists. It also removes the current node as a successor of @@ -347,7 +358,7 @@ namespace llvm { /// getDepth - Return the depth of this node, which is the length of the /// maximum path up to any node with has no predecessors. unsigned getDepth() const { - if (!isDepthCurrent) + if (!isDepthCurrent) const_cast<SUnit *>(this)->ComputeDepth(); return Depth; } @@ -355,7 +366,7 @@ namespace llvm { /// getHeight - Return the height of this node, which is the length of the /// maximum path down to any node with has no successors. unsigned getHeight() const { - if (!isHeightCurrent) + if (!isHeightCurrent) const_cast<SUnit *>(this)->ComputeHeight(); return Height; } @@ -387,7 +398,7 @@ namespace llvm { return true; return false; } - + /// isSucc - Test if node N is a successor of this node. bool isSucc(SUnit *N) { for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i) @@ -408,25 +419,38 @@ namespace llvm { //===--------------------------------------------------------------------===// /// SchedulingPriorityQueue - This interface is used to plug different /// priorities computation algorithms into the list scheduler. It implements - /// the interface of a standard priority queue, where nodes are inserted in + /// the interface of a standard priority queue, where nodes are inserted in /// arbitrary order and returned in priority order. The computation of the /// priority and the representation of the queue are totally up to the /// implementation to decide. - /// + /// class SchedulingPriorityQueue { unsigned CurCycle; + bool HasReadyFilter; public: - SchedulingPriorityQueue() : CurCycle(0) {} + SchedulingPriorityQueue(bool rf = false): + CurCycle(0), HasReadyFilter(rf) {} virtual ~SchedulingPriorityQueue() {} - + + virtual bool isBottomUp() const = 0; + virtual void initNodes(std::vector<SUnit> &SUnits) = 0; virtual void addNode(const SUnit *SU) = 0; virtual void updateNode(const SUnit *SU) = 0; virtual void releaseState() = 0; virtual bool empty() const = 0; + + bool hasReadyFilter() const { return HasReadyFilter; } + + virtual bool tracksRegPressure() const { return false; } + + virtual bool isReady(SUnit *) const { + assert(!HasReadyFilter && "The ready filter must override isReady()"); + return true; + } virtual void push(SUnit *U) = 0; - + void push_all(const std::vector<SUnit *> &Nodes) { for (std::vector<SUnit *>::const_iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) @@ -437,6 +461,8 @@ namespace llvm { virtual void remove(SUnit *SU) = 0; + virtual void dump(ScheduleDAG *) const {} + /// ScheduledNode - As each node is scheduled, this method is invoked. This /// allows the priority function to adjust the priority of related /// unscheduled nodes, for example. @@ -451,7 +477,7 @@ namespace llvm { unsigned getCurCycle() const { return CurCycle; - } + } }; class ScheduleDAG { @@ -473,11 +499,18 @@ namespace llvm { virtual ~ScheduleDAG(); + /// getInstrDesc - Return the TargetInstrDesc of this SUnit. + /// Return NULL for SDNodes without a machine opcode. + const TargetInstrDesc *getInstrDesc(const SUnit *SU) const { + if (SU->isInstr()) return &SU->getInstr()->getDesc(); + return getNodeDesc(SU->getNode()); + } + /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered /// using 'dot'. /// void viewGraph(); - + /// EmitSchedule - Insert MachineInstrs into the MachineBasicBlock /// according to the order specified in Sequence. /// @@ -536,6 +569,10 @@ namespace llvm { void EmitNoop(); void EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap); + + private: + // Return the TargetInstrDesc of this SDNode or NULL. + const TargetInstrDesc *getNodeDesc(const SDNode *Node) const; }; class SUnitIterator : public std::iterator<std::forward_iterator_tag, @@ -627,7 +664,7 @@ namespace llvm { /// Visited - a set of nodes visited during a DFS traversal. BitVector Visited; - /// DFS - make a DFS traversal and mark all nodes affected by the + /// DFS - make a DFS traversal and mark all nodes affected by the /// edge insertion. These nodes will later get new topological indexes /// by means of the Shift method. void DFS(const SUnit *SU, int UpperBound, bool& HasLoop); @@ -642,7 +679,7 @@ namespace llvm { public: explicit ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits); - /// InitDAGTopologicalSorting - create the initial topological + /// InitDAGTopologicalSorting - create the initial topological /// ordering from the DAG to be scheduled. void InitDAGTopologicalSorting(); |
