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 // Scheduling heuristics
39 enum SchedHeuristics {
40 defaultScheduling, // Let the target specify its preference.
41 noScheduling, // No scheduling, emit breath first sequence.
42 simpleScheduling, // Two pass, min. critical path, max. utilization.
43 simpleNoItinScheduling, // Same as above exact using generic latency.
44 listSchedulingBURR, // Bottom up reg reduction list scheduling.
48 //===--------------------------------------------------------------------===//
50 /// Node group - This struct is used to manage flagged node groups.
54 NIVector Members; // Group member nodes
57 NodeInfo *Dominator; // Node with highest latency
58 unsigned Latency; // Total latency of the group
59 int Pending; // Number of visits pending before
64 NodeGroup() : Top(NULL), Bottom(NULL), Dominator(NULL), Pending(0) {}
67 inline void setDominator(NodeInfo *D) { Dominator = D; }
68 inline NodeInfo *getTop() { return Top; }
69 inline NodeInfo *getBottom() { return Bottom; }
70 inline NodeInfo *getDominator() { return Dominator; }
71 inline void setLatency(unsigned L) { Latency = L; }
72 inline unsigned getLatency() { return Latency; }
73 inline int getPending() const { return Pending; }
74 inline void setPending(int P) { Pending = P; }
75 inline int addPending(int I) { return Pending += I; }
78 inline bool group_empty() { return Members.empty(); }
79 inline NIIterator group_begin() { return Members.begin(); }
80 inline NIIterator group_end() { return Members.end(); }
81 inline void group_push_back(const NodeInfoPtr &NI) {
82 Members.push_back(NI);
84 inline NIIterator group_insert(NIIterator Pos, const NodeInfoPtr &NI) {
85 return Members.insert(Pos, NI);
87 inline void group_insert(NIIterator Pos, NIIterator First,
89 Members.insert(Pos, First, Last);
92 static void Add(NodeInfo *D, NodeInfo *U);
95 //===--------------------------------------------------------------------===//
97 /// NodeInfo - This struct tracks information used to schedule the a node.
101 int Pending; // Number of visits pending before
104 SDNode *Node; // DAG node
105 InstrStage *StageBegin; // First stage in itinerary
106 InstrStage *StageEnd; // Last+1 stage in itinerary
107 unsigned Latency; // Total cycles to complete instr
108 bool IsCall : 1; // Is function call
109 bool IsLoad : 1; // Is memory load
110 bool IsStore : 1; // Is memory store
111 unsigned Slot; // Node's time slot
112 NodeGroup *Group; // Grouping information
113 unsigned VRBase; // Virtual register base
115 unsigned Preorder; // Index before scheduling
119 NodeInfo(SDNode *N = NULL)
135 inline bool isInGroup() const {
136 assert(!Group || !Group->group_empty() && "Group with no members");
137 return Group != NULL;
139 inline bool isGroupDominator() const {
140 return isInGroup() && Group->getDominator() == this;
142 inline int getPending() const {
143 return Group ? Group->getPending() : Pending;
145 inline void setPending(int P) {
146 if (Group) Group->setPending(P);
149 inline int addPending(int I) {
150 if (Group) return Group->addPending(I);
151 else return Pending += I;
155 //===--------------------------------------------------------------------===//
157 /// NodeGroupIterator - Iterates over all the nodes indicated by the node
158 /// info. If the node is in a group then iterate over the members of the
159 /// group, otherwise just the node info.
161 class NodeGroupIterator {
163 NodeInfo *NI; // Node info
164 NIIterator NGI; // Node group iterator
165 NIIterator NGE; // Node group iterator end
169 NodeGroupIterator(NodeInfo *N) : NI(N) {
170 // If the node is in a group then set up the group iterator. Otherwise
171 // the group iterators will trip first time out.
172 if (N->isInGroup()) {
174 NodeGroup *Group = NI->Group;
175 NGI = Group->group_begin();
176 NGE = Group->group_end();
177 // Prevent this node from being used (will be in members list
182 /// next - Return the next node info, otherwise NULL.
186 if (NGI != NGE) return *NGI++;
187 // Use node as the result (may be NULL)
188 NodeInfo *Result = NI;
191 // Return node or NULL
195 //===--------------------------------------------------------------------===//
198 //===--------------------------------------------------------------------===//
200 /// NodeGroupOpIterator - Iterates over all the operands of a node. If the
201 /// node is a member of a group, this iterates over all the operands of all
202 /// the members of the group.
204 class NodeGroupOpIterator {
206 NodeInfo *NI; // Node containing operands
207 NodeGroupIterator GI; // Node group iterator
208 SDNode::op_iterator OI; // Operand iterator
209 SDNode::op_iterator OE; // Operand iterator end
211 /// CheckNode - Test if node has more operands. If not get the next node
212 /// skipping over nodes that have no operands.
214 // Only if operands are exhausted first
216 // Get next node info
217 NodeInfo *NI = GI.next();
218 // Exit if nodes are exhausted
221 SDNode *Node = NI->Node;
222 // Set up the operand iterators
223 OI = Node->op_begin();
230 NodeGroupOpIterator(NodeInfo *N)
231 : NI(N), GI(N), OI(SDNode::op_iterator()), OE(SDNode::op_iterator()) {}
233 /// isEnd - Returns true when not more operands are available.
235 inline bool isEnd() { CheckNode(); return OI == OE; }
237 /// next - Returns the next available operand.
239 inline SDOperand next() {
241 "Not checking for end of NodeGroupOpIterator correctly");
248 SchedHeuristics Heuristic; // Scheduling heuristic
249 SelectionDAG &DAG; // DAG of the current basic block
250 MachineBasicBlock *BB; // Current basic block
251 const TargetMachine &TM; // Target processor
252 const TargetInstrInfo *TII; // Target instruction information
253 const MRegisterInfo *MRI; // Target processor register info
254 SSARegMap *RegMap; // Virtual/real register map
255 MachineConstantPool *ConstPool; // Target constant pool
256 std::map<SDNode *, NodeInfo *> Map; // Map nodes to info
257 unsigned NodeCount; // Number of nodes in DAG
258 bool HasGroups; // True if there are any groups
259 NodeInfo *Info; // Info for nodes being scheduled
260 NIVector Ordering; // Emit ordering of nodes
262 ScheduleDAG(SchedHeuristics hstc, SelectionDAG &dag, MachineBasicBlock *bb,
263 const TargetMachine &tm)
264 : Heuristic(hstc), DAG(dag), BB(bb), TM(tm),
265 NodeCount(0), HasGroups(false), Info(NULL) {}
267 virtual ~ScheduleDAG() {};
269 /// Run - perform scheduling.
271 MachineBasicBlock *Run();
273 /// getNI - Returns the node info for the specified node.
275 NodeInfo *getNI(SDNode *Node) { return Map[Node]; }
277 /// getVR - Returns the virtual register number of the node.
279 unsigned getVR(SDOperand Op) {
280 NodeInfo *NI = getNI(Op.Val);
281 assert(NI->VRBase != 0 && "Node emitted out of order - late");
282 return NI->VRBase + Op.ResNo;
285 /// isPassiveNode - Return true if the node is a non-scheduled leaf.
287 static bool isPassiveNode(SDNode *Node) {
288 if (isa<ConstantSDNode>(Node)) return true;
289 if (isa<RegisterSDNode>(Node)) return true;
290 if (isa<GlobalAddressSDNode>(Node)) return true;
291 if (isa<BasicBlockSDNode>(Node)) return true;
292 if (isa<FrameIndexSDNode>(Node)) return true;
293 if (isa<ConstantPoolSDNode>(Node)) return true;
294 if (isa<ExternalSymbolSDNode>(Node)) return true;
298 /// EmitNode - Generate machine code for an node and needed dependencies.
300 void EmitNode(NodeInfo *NI);
302 /// EmitAll - Emit all nodes in schedule sorted order.
306 /// Schedule - Order nodes according to selected style.
308 virtual void Schedule() {};
310 /// printNI - Print node info.
312 void printNI(std::ostream &O, NodeInfo *NI) const;
314 /// printChanges - Hilight changes in order caused by scheduling.
316 void printChanges(unsigned Index) const;
318 /// print - Print ordering to specified output stream.
320 void print(std::ostream &O) const;
322 void dump(const char *tag) const;
324 virtual void dump() const;
327 /// PrepareNodeInfo - Set up the basic minimum node info for scheduling.
329 void PrepareNodeInfo();
331 /// IdentifyGroups - Put flagged nodes into groups.
333 void IdentifyGroups();
336 /// createSimpleDAGScheduler - This creates a simple two pass instruction
338 ScheduleDAG* createSimpleDAGScheduler(SchedHeuristics Heuristic,
340 MachineBasicBlock *BB);
342 /// createBURRListDAGScheduler - This creates a bottom up register usage
343 /// reduction list scheduler.
344 ScheduleDAG* createBURRListDAGScheduler(SelectionDAG &DAG,
345 MachineBasicBlock *BB);