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;
37 // Scheduling heuristics
38 enum SchedHeuristics {
39 defaultScheduling, // Let the target specify its preference.
40 noScheduling, // No scheduling, emit breadth first sequence.
41 simpleScheduling, // Two pass, min. critical path, max. utilization.
42 simpleNoItinScheduling, // Same as above exact using generic latency.
43 listSchedulingBURR, // Bottom up reg reduction list scheduling.
44 listSchedulingTD // Top-down list scheduler.
47 /// HazardRecognizer - This determines whether or not an instruction can be
48 /// issued this cycle, and whether or not a noop needs to be inserted to handle
50 class HazardRecognizer {
52 virtual ~HazardRecognizer();
55 NoHazard, // This instruction can be emitted at this cycle.
56 Hazard, // This instruction can't be emitted at this cycle.
57 NoopHazard, // This instruction can't be emitted, and needs noops.
60 /// getHazardType - Return the hazard type of emitting this node. There are
61 /// three possible results. Either:
62 /// * NoHazard: it is legal to issue this instruction on this cycle.
63 /// * Hazard: issuing this instruction would stall the machine. If some
64 /// other instruction is available, issue it first.
65 /// * NoopHazard: issuing this instruction would break the program. If
66 /// some other instruction can be issued, do so, otherwise issue a noop.
67 virtual HazardType getHazardType(SDNode *Node) {
71 /// EmitInstruction - This callback is invoked when an instruction is
72 /// emitted, to advance the hazard state.
73 virtual void EmitInstruction(SDNode *Node) {
76 /// AdvanceCycle - This callback is invoked when no instructions can be
77 /// issued on this cycle without a hazard. This should increment the
78 /// internal state of the hazard recognizer so that previously "Hazard"
79 /// instructions will now not be hazards.
80 virtual void AdvanceCycle() {
83 /// EmitNoop - This callback is invoked when a noop was added to the
84 /// instruction stream.
85 virtual void EmitNoop() {
89 //===--------------------------------------------------------------------===//
91 /// Node group - This struct is used to manage flagged node groups.
97 NIVector Members; // Group member nodes
98 NodeInfo *Dominator; // Node with highest latency
99 unsigned Latency; // Total latency of the group
100 int Pending; // Number of visits pending before
105 NodeGroup() : Next(NULL), Dominator(NULL), Pending(0) {}
108 inline void setDominator(NodeInfo *D) { Dominator = D; }
109 inline NodeInfo *getTop() { return Members.front(); }
110 inline NodeInfo *getBottom() { return Members.back(); }
111 inline NodeInfo *getDominator() { return Dominator; }
112 inline void setLatency(unsigned L) { Latency = L; }
113 inline unsigned getLatency() { return Latency; }
114 inline int getPending() const { return Pending; }
115 inline void setPending(int P) { Pending = P; }
116 inline int addPending(int I) { return Pending += I; }
119 inline bool group_empty() { return Members.empty(); }
120 inline NIIterator group_begin() { return Members.begin(); }
121 inline NIIterator group_end() { return Members.end(); }
122 inline void group_push_back(const NodeInfoPtr &NI) {
123 Members.push_back(NI);
125 inline NIIterator group_insert(NIIterator Pos, const NodeInfoPtr &NI) {
126 return Members.insert(Pos, NI);
128 inline void group_insert(NIIterator Pos, NIIterator First,
130 Members.insert(Pos, First, Last);
133 static void Add(NodeInfo *D, NodeInfo *U);
136 //===--------------------------------------------------------------------===//
138 /// NodeInfo - This struct tracks information used to schedule the a node.
142 int Pending; // Number of visits pending before
145 SDNode *Node; // DAG node
146 InstrStage *StageBegin; // First stage in itinerary
147 InstrStage *StageEnd; // Last+1 stage in itinerary
148 unsigned Latency; // Total cycles to complete instr
149 bool IsCall : 1; // Is function call
150 bool IsLoad : 1; // Is memory load
151 bool IsStore : 1; // Is memory store
152 unsigned Slot; // Node's time slot
153 NodeGroup *Group; // Grouping information
155 unsigned Preorder; // Index before scheduling
159 NodeInfo(SDNode *N = NULL)
174 inline bool isInGroup() const {
175 assert(!Group || !Group->group_empty() && "Group with no members");
176 return Group != NULL;
178 inline bool isGroupDominator() const {
179 return isInGroup() && Group->getDominator() == this;
181 inline int getPending() const {
182 return Group ? Group->getPending() : Pending;
184 inline void setPending(int P) {
185 if (Group) Group->setPending(P);
188 inline int addPending(int I) {
189 if (Group) return Group->addPending(I);
190 else return Pending += I;
194 //===--------------------------------------------------------------------===//
196 /// NodeGroupIterator - Iterates over all the nodes indicated by the node
197 /// info. If the node is in a group then iterate over the members of the
198 /// group, otherwise just the node info.
200 class NodeGroupIterator {
202 NodeInfo *NI; // Node info
203 NIIterator NGI; // Node group iterator
204 NIIterator NGE; // Node group iterator end
208 NodeGroupIterator(NodeInfo *N) : NI(N) {
209 // If the node is in a group then set up the group iterator. Otherwise
210 // the group iterators will trip first time out.
211 if (N->isInGroup()) {
213 NodeGroup *Group = NI->Group;
214 NGI = Group->group_begin();
215 NGE = Group->group_end();
216 // Prevent this node from being used (will be in members list
221 /// next - Return the next node info, otherwise NULL.
225 if (NGI != NGE) return *NGI++;
226 // Use node as the result (may be NULL)
227 NodeInfo *Result = NI;
230 // Return node or NULL
234 //===--------------------------------------------------------------------===//
237 //===--------------------------------------------------------------------===//
239 /// NodeGroupOpIterator - Iterates over all the operands of a node. If the
240 /// node is a member of a group, this iterates over all the operands of all
241 /// the members of the group.
243 class NodeGroupOpIterator {
245 NodeInfo *NI; // Node containing operands
246 NodeGroupIterator GI; // Node group iterator
247 SDNode::op_iterator OI; // Operand iterator
248 SDNode::op_iterator OE; // Operand iterator end
250 /// CheckNode - Test if node has more operands. If not get the next node
251 /// skipping over nodes that have no operands.
253 // Only if operands are exhausted first
255 // Get next node info
256 NodeInfo *NI = GI.next();
257 // Exit if nodes are exhausted
260 SDNode *Node = NI->Node;
261 // Set up the operand iterators
262 OI = Node->op_begin();
269 NodeGroupOpIterator(NodeInfo *N)
270 : NI(N), GI(N), OI(SDNode::op_iterator()), OE(SDNode::op_iterator()) {}
272 /// isEnd - Returns true when not more operands are available.
274 inline bool isEnd() { CheckNode(); return OI == OE; }
276 /// next - Returns the next available operand.
278 inline SDOperand next() {
280 "Not checking for end of NodeGroupOpIterator correctly");
287 SelectionDAG &DAG; // DAG of the current basic block
288 MachineBasicBlock *BB; // Current basic block
289 const TargetMachine &TM; // Target processor
290 const TargetInstrInfo *TII; // Target instruction information
291 const MRegisterInfo *MRI; // Target processor register info
292 SSARegMap *RegMap; // Virtual/real register map
293 MachineConstantPool *ConstPool; // Target constant pool
295 ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb,
296 const TargetMachine &tm)
297 : DAG(dag), BB(bb), TM(tm) {}
299 virtual ~ScheduleDAG() {
302 /// Run - perform scheduling.
304 MachineBasicBlock *Run();
306 /// isPassiveNode - Return true if the node is a non-scheduled leaf.
308 static bool isPassiveNode(SDNode *Node) {
309 if (isa<ConstantSDNode>(Node)) return true;
310 if (isa<RegisterSDNode>(Node)) return true;
311 if (isa<GlobalAddressSDNode>(Node)) return true;
312 if (isa<BasicBlockSDNode>(Node)) return true;
313 if (isa<FrameIndexSDNode>(Node)) return true;
314 if (isa<ConstantPoolSDNode>(Node)) return true;
315 if (isa<ExternalSymbolSDNode>(Node)) return true;
319 /// EmitNode - Generate machine code for an node and needed dependencies.
320 /// VRBaseMap contains, for each already emitted node, the first virtual
321 /// register number for the results of the node.
323 void EmitNode(SDNode *Node, std::map<SDNode*, unsigned> &VRBaseMap);
325 /// EmitNoop - Emit a noop instruction.
330 /// Schedule - Order nodes according to selected style.
332 virtual void Schedule() {}
335 void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum,
336 const TargetInstrDescriptor *II,
337 std::map<SDNode*, unsigned> &VRBaseMap);
340 /// createSimpleDAGScheduler - This creates a simple two pass instruction
342 ScheduleDAG* createSimpleDAGScheduler(SchedHeuristics Heuristic,
344 MachineBasicBlock *BB);
346 /// createBURRListDAGScheduler - This creates a bottom up register usage
347 /// reduction list scheduler.
348 ScheduleDAG* createBURRListDAGScheduler(SelectionDAG &DAG,
349 MachineBasicBlock *BB);
351 /// createTDListDAGScheduler - This creates a top-down list scheduler with
352 /// the specified hazard recognizer. This takes ownership of the hazard
353 /// recognizer and deletes it when done.
354 ScheduleDAG* createTDListDAGScheduler(SelectionDAG &DAG,
355 MachineBasicBlock *BB,
356 HazardRecognizer *HR);