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"
24 class MachineConstantPool;
25 class MachineDebugInfo;
29 class SelectionDAGISel;
31 class TargetInstrInfo;
32 class TargetInstrDescriptor;
35 /// HazardRecognizer - This determines whether or not an instruction can be
36 /// issued this cycle, and whether or not a noop needs to be inserted to handle
38 class HazardRecognizer {
40 virtual ~HazardRecognizer();
43 NoHazard, // This instruction can be emitted at this cycle.
44 Hazard, // This instruction can't be emitted at this cycle.
45 NoopHazard // This instruction can't be emitted, and needs noops.
48 /// getHazardType - Return the hazard type of emitting this node. There are
49 /// three possible results. Either:
50 /// * NoHazard: it is legal to issue this instruction on this cycle.
51 /// * Hazard: issuing this instruction would stall the machine. If some
52 /// other instruction is available, issue it first.
53 /// * NoopHazard: issuing this instruction would break the program. If
54 /// some other instruction can be issued, do so, otherwise issue a noop.
55 virtual HazardType getHazardType(SDNode *Node) {
59 /// EmitInstruction - This callback is invoked when an instruction is
60 /// emitted, to advance the hazard state.
61 virtual void EmitInstruction(SDNode *Node) {
64 /// AdvanceCycle - This callback is invoked when no instructions can be
65 /// issued on this cycle without a hazard. This should increment the
66 /// internal state of the hazard recognizer so that previously "Hazard"
67 /// instructions will now not be hazards.
68 virtual void AdvanceCycle() {
71 /// EmitNoop - This callback is invoked when a noop was added to the
72 /// instruction stream.
73 virtual void EmitNoop() {
77 /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
78 /// a group of nodes flagged together.
80 SDNode *Node; // Representative node.
81 SmallVector<SDNode*,4> FlaggedNodes;// All nodes flagged to Node.
83 // Preds/Succs - The SUnits before/after us in the graph. The boolean value
84 // is true if the edge is a token chain edge, false if it is a value edge.
85 SmallVector<std::pair<SUnit*,bool>, 4> Preds; // All sunit predecessors.
86 SmallVector<std::pair<SUnit*,bool>, 4> Succs; // All sunit successors.
88 typedef SmallVector<std::pair<SUnit*,bool>, 4>::iterator pred_iterator;
89 typedef SmallVector<std::pair<SUnit*,bool>, 4>::iterator succ_iterator;
90 typedef SmallVector<std::pair<SUnit*,bool>, 4>::const_iterator
92 typedef SmallVector<std::pair<SUnit*,bool>, 4>::const_iterator
95 short NumPreds; // # of preds.
96 short NumSuccs; // # of sucss.
97 short NumPredsLeft; // # of preds not scheduled.
98 short NumSuccsLeft; // # of succs not scheduled.
99 short NumChainPredsLeft; // # of chain preds not scheduled.
100 short NumChainSuccsLeft; // # of chain succs not scheduled.
101 bool isTwoAddress : 1; // Is a two-address instruction.
102 bool isCommutable : 1; // Is a commutable instruction.
103 bool isPending : 1; // True once pending.
104 bool isAvailable : 1; // True once available.
105 bool isScheduled : 1; // True once scheduled.
106 unsigned short Latency; // Node latency.
107 unsigned CycleBound; // Upper/lower cycle to be scheduled at.
108 unsigned Cycle; // Once scheduled, the cycle of the op.
109 unsigned Depth; // Node depth;
110 unsigned Height; // Node height;
111 unsigned NodeNum; // Entry # of node in the node vector.
113 SUnit(SDNode *node, unsigned nodenum)
114 : Node(node), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
115 NumChainPredsLeft(0), NumChainSuccsLeft(0),
116 isTwoAddress(false), isCommutable(false),
117 isPending(false), isAvailable(false), isScheduled(false),
118 Latency(0), CycleBound(0), Cycle(0), Depth(0), Height(0),
121 /// addPred - This adds the specified node as a pred of the current node if
122 /// not already. This returns true if this is a new pred.
123 bool addPred(SUnit *N, bool isChain) {
124 for (unsigned i = 0, e = Preds.size(); i != e; ++i)
125 if (Preds[i].first == N && Preds[i].second == isChain)
127 Preds.push_back(std::make_pair(N, isChain));
131 /// addSucc - This adds the specified node as a succ of the current node if
132 /// not already. This returns true if this is a new succ.
133 bool addSucc(SUnit *N, bool isChain) {
134 for (unsigned i = 0, e = Succs.size(); i != e; ++i)
135 if (Succs[i].first == N && Succs[i].second == isChain)
137 Succs.push_back(std::make_pair(N, isChain));
141 void dump(const SelectionDAG *G) const;
142 void dumpAll(const SelectionDAG *G) const;
145 //===--------------------------------------------------------------------===//
146 /// SchedulingPriorityQueue - This interface is used to plug different
147 /// priorities computation algorithms into the list scheduler. It implements
148 /// the interface of a standard priority queue, where nodes are inserted in
149 /// arbitrary order and returned in priority order. The computation of the
150 /// priority and the representation of the queue are totally up to the
151 /// implementation to decide.
153 class SchedulingPriorityQueue {
155 virtual ~SchedulingPriorityQueue() {}
157 virtual void initNodes(std::vector<SUnit> &SUnits) = 0;
158 virtual void releaseState() = 0;
160 virtual bool empty() const = 0;
161 virtual void push(SUnit *U) = 0;
163 virtual void push_all(const std::vector<SUnit *> &Nodes) = 0;
164 virtual SUnit *pop() = 0;
166 /// ScheduledNode - As each node is scheduled, this method is invoked. This
167 /// allows the priority function to adjust the priority of node that have
168 /// already been emitted.
169 virtual void ScheduledNode(SUnit *Node) {}
174 SelectionDAG &DAG; // DAG of the current basic block
175 MachineBasicBlock *BB; // Current basic block
176 const TargetMachine &TM; // Target processor
177 const TargetInstrInfo *TII; // Target instruction information
178 const MRegisterInfo *MRI; // Target processor register info
179 SSARegMap *RegMap; // Virtual/real register map
180 MachineConstantPool *ConstPool; // Target constant pool
181 std::vector<SUnit*> Sequence; // The schedule. Null SUnit*'s
182 // represent noop instructions.
183 std::map<SDNode*, SUnit*> SUnitMap; // SDNode to SUnit mapping (n -> 1).
184 std::vector<SUnit> SUnits; // The scheduling units.
185 std::set<SDNode*> CommuteSet; // Nodes the should be commuted.
187 ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb,
188 const TargetMachine &tm)
189 : DAG(dag), BB(bb), TM(tm) {}
191 virtual ~ScheduleDAG() {}
193 /// Run - perform scheduling.
195 MachineBasicBlock *Run();
197 /// isPassiveNode - Return true if the node is a non-scheduled leaf.
199 static bool isPassiveNode(SDNode *Node) {
200 if (isa<ConstantSDNode>(Node)) return true;
201 if (isa<RegisterSDNode>(Node)) return true;
202 if (isa<GlobalAddressSDNode>(Node)) return true;
203 if (isa<BasicBlockSDNode>(Node)) return true;
204 if (isa<FrameIndexSDNode>(Node)) return true;
205 if (isa<ConstantPoolSDNode>(Node)) return true;
206 if (isa<JumpTableSDNode>(Node)) return true;
207 if (isa<ExternalSymbolSDNode>(Node)) return true;
211 /// NewSUnit - Creates a new SUnit and return a ptr to it.
213 SUnit *NewSUnit(SDNode *N) {
214 SUnits.push_back(SUnit(N, SUnits.size()));
215 return &SUnits.back();
218 /// BuildSchedUnits - Build SUnits from the selection dag that we are input.
219 /// This SUnit graph is similar to the SelectionDAG, but represents flagged
220 /// together nodes with a single SUnit.
221 void BuildSchedUnits();
223 /// CalculateDepths, CalculateHeights - Calculate node depth / height.
225 void CalculateDepths();
226 void CalculateHeights();
228 /// EmitNode - Generate machine code for an node and needed dependencies.
229 /// VRBaseMap contains, for each already emitted node, the first virtual
230 /// register number for the results of the node.
232 void EmitNode(SDNode *Node, std::map<SDNode*, unsigned> &VRBaseMap);
234 /// EmitNoop - Emit a noop instruction.
240 void dumpSchedule() const;
242 /// Schedule - Order nodes according to selected style.
244 virtual void Schedule() {}
247 void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum,
248 const TargetInstrDescriptor *II,
249 std::map<SDNode*, unsigned> &VRBaseMap);
252 /// createBFS_DAGScheduler - This creates a simple breadth first instruction
254 ScheduleDAG *createBFS_DAGScheduler(SelectionDAGISel *IS,
256 MachineBasicBlock *BB);
258 /// createSimpleDAGScheduler - This creates a simple two pass instruction
259 /// scheduler using instruction itinerary.
260 ScheduleDAG* createSimpleDAGScheduler(SelectionDAGISel *IS,
262 MachineBasicBlock *BB);
264 /// createNoItinsDAGScheduler - This creates a simple two pass instruction
265 /// scheduler without using instruction itinerary.
266 ScheduleDAG* createNoItinsDAGScheduler(SelectionDAGISel *IS,
268 MachineBasicBlock *BB);
270 /// createBURRListDAGScheduler - This creates a bottom up register usage
271 /// reduction list scheduler.
272 ScheduleDAG* createBURRListDAGScheduler(SelectionDAGISel *IS,
274 MachineBasicBlock *BB);
276 /// createTDRRListDAGScheduler - This creates a top down register usage
277 /// reduction list scheduler.
278 ScheduleDAG* createTDRRListDAGScheduler(SelectionDAGISel *IS,
280 MachineBasicBlock *BB);
282 /// createTDListDAGScheduler - This creates a top-down list scheduler with
283 /// a hazard recognizer.
284 ScheduleDAG* createTDListDAGScheduler(SelectionDAGISel *IS,
286 MachineBasicBlock *BB);
288 /// createDefaultScheduler - This creates an instruction scheduler appropriate
290 ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS,
292 MachineBasicBlock *BB);