1 //===------- llvm/CodeGen/ScheduleDAG.h - Common Base Class------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by Evan Cheng and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the ScheduleDAG class, which is used as the common
11 // base class for SelectionDAG-based instruction scheduler.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CODEGEN_SCHEDULEDAG_H
16 #define LLVM_CODEGEN_SCHEDULEDAG_H
18 #include "llvm/CodeGen/SelectionDAG.h"
22 class MachineConstantPool;
23 class MachineDebugInfo;
28 class TargetInstrInfo;
29 class TargetInstrDescriptor;
33 typedef NodeInfo *NodeInfoPtr;
34 typedef std::vector<NodeInfoPtr> NIVector;
35 typedef std::vector<NodeInfoPtr>::iterator NIIterator;
38 //===--------------------------------------------------------------------===//
40 /// Node group - This struct is used to manage flagged node groups.
44 NIVector Members; // Group member nodes
45 NodeInfo *Dominator; // Node with highest latency
46 unsigned Latency; // Total latency of the group
47 int Pending; // Number of visits pending before
52 NodeGroup() : Dominator(NULL), Pending(0) {}
55 inline void setDominator(NodeInfo *D) { Dominator = D; }
56 inline NodeInfo *getDominator() { return Dominator; }
57 inline void setLatency(unsigned L) { Latency = L; }
58 inline unsigned getLatency() { return Latency; }
59 inline int getPending() const { return Pending; }
60 inline void setPending(int P) { Pending = P; }
61 inline int addPending(int I) { return Pending += I; }
64 inline bool group_empty() { return Members.empty(); }
65 inline NIIterator group_begin() { return Members.begin(); }
66 inline NIIterator group_end() { return Members.end(); }
67 inline void group_push_back(const NodeInfoPtr &NI) {
68 Members.push_back(NI);
70 inline NIIterator group_insert(NIIterator Pos, const NodeInfoPtr &NI) {
71 return Members.insert(Pos, NI);
73 inline void group_insert(NIIterator Pos, NIIterator First,
75 Members.insert(Pos, First, Last);
78 static void Add(NodeInfo *D, NodeInfo *U);
79 static unsigned CountInternalUses(NodeInfo *D, NodeInfo *U);
82 //===--------------------------------------------------------------------===//
84 /// NodeInfo - This struct tracks information used to schedule the a node.
88 int Pending; // Number of visits pending before
91 SDNode *Node; // DAG node
92 InstrStage *StageBegin; // First stage in itinerary
93 InstrStage *StageEnd; // Last+1 stage in itinerary
94 unsigned Latency; // Total cycles to complete instr
95 bool IsCall : 1; // Is function call
96 bool IsLoad : 1; // Is memory load
97 bool IsStore : 1; // Is memory store
98 unsigned Slot; // Node's time slot
99 NodeGroup *Group; // Grouping information
100 unsigned VRBase; // Virtual register base
102 unsigned Preorder; // Index before scheduling
106 NodeInfo(SDNode *N = NULL)
122 inline bool isInGroup() const {
123 assert(!Group || !Group->group_empty() && "Group with no members");
124 return Group != NULL;
126 inline bool isGroupDominator() const {
127 return isInGroup() && Group->getDominator() == this;
129 inline int getPending() const {
130 return Group ? Group->getPending() : Pending;
132 inline void setPending(int P) {
133 if (Group) Group->setPending(P);
136 inline int addPending(int I) {
137 if (Group) return Group->addPending(I);
138 else return Pending += I;
142 //===--------------------------------------------------------------------===//
144 /// NodeGroupIterator - Iterates over all the nodes indicated by the node
145 /// info. If the node is in a group then iterate over the members of the
146 /// group, otherwise just the node info.
148 class NodeGroupIterator {
150 NodeInfo *NI; // Node info
151 NIIterator NGI; // Node group iterator
152 NIIterator NGE; // Node group iterator end
156 NodeGroupIterator(NodeInfo *N) : NI(N) {
157 // If the node is in a group then set up the group iterator. Otherwise
158 // the group iterators will trip first time out.
159 if (N->isInGroup()) {
161 NodeGroup *Group = NI->Group;
162 NGI = Group->group_begin();
163 NGE = Group->group_end();
164 // Prevent this node from being used (will be in members list
169 /// next - Return the next node info, otherwise NULL.
173 if (NGI != NGE) return *NGI++;
174 // Use node as the result (may be NULL)
175 NodeInfo *Result = NI;
178 // Return node or NULL
182 //===--------------------------------------------------------------------===//
185 //===--------------------------------------------------------------------===//
187 /// NodeGroupOpIterator - Iterates over all the operands of a node. If the
188 /// node is a member of a group, this iterates over all the operands of all
189 /// the members of the group.
191 class NodeGroupOpIterator {
193 NodeInfo *NI; // Node containing operands
194 NodeGroupIterator GI; // Node group iterator
195 SDNode::op_iterator OI; // Operand iterator
196 SDNode::op_iterator OE; // Operand iterator end
198 /// CheckNode - Test if node has more operands. If not get the next node
199 /// skipping over nodes that have no operands.
201 // Only if operands are exhausted first
203 // Get next node info
204 NodeInfo *NI = GI.next();
205 // Exit if nodes are exhausted
208 SDNode *Node = NI->Node;
209 // Set up the operand iterators
210 OI = Node->op_begin();
217 NodeGroupOpIterator(NodeInfo *N)
218 : NI(N), GI(N), OI(SDNode::op_iterator()), OE(SDNode::op_iterator()) {}
220 /// isEnd - Returns true when not more operands are available.
222 inline bool isEnd() { CheckNode(); return OI == OE; }
224 /// next - Returns the next available operand.
226 inline SDOperand next() {
228 "Not checking for end of NodeGroupOpIterator correctly");
235 SelectionDAG &DAG; // DAG of the current basic block
236 MachineBasicBlock *BB; // Current basic block
237 const TargetMachine &TM; // Target processor
238 const TargetInstrInfo *TII; // Target instruction information
239 const MRegisterInfo *MRI; // Target processor register info
240 SSARegMap *RegMap; // Virtual/real register map
241 MachineConstantPool *ConstPool; // Target constant pool
242 std::map<SDNode *, NodeInfo *> Map; // Map nodes to info
244 ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb,
245 const TargetMachine &tm)
246 : DAG(dag), BB(bb), TM(tm) {}
248 virtual ~ScheduleDAG() {};
250 /// Run - perform scheduling.
252 MachineBasicBlock *Run();
254 /// getNI - Returns the node info for the specified node.
256 NodeInfo *getNI(SDNode *Node) { return Map[Node]; }
258 /// getVR - Returns the virtual register number of the node.
260 unsigned getVR(SDOperand Op) {
261 NodeInfo *NI = getNI(Op.Val);
262 assert(NI->VRBase != 0 && "Node emitted out of order - late");
263 return NI->VRBase + Op.ResNo;
266 void EmitNode(NodeInfo *NI);
268 virtual void Schedule() {};
270 virtual void print(std::ostream &O) const {};
272 void dump(const char *tag) const;
277 unsigned CreateVirtualRegisters(MachineInstr *MI,
279 const TargetInstrDescriptor &II);
282 /// createSimpleDAGScheduler - This creates a simple two pass instruction
284 ScheduleDAG* createSimpleDAGScheduler(SelectionDAG &DAG,
285 MachineBasicBlock *BB);