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 std::vector<SDNode*> 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 std::set<std::pair<SUnit*,bool> > Preds; // All sunit predecessors.
86 std::set<std::pair<SUnit*,bool> > Succs; // All sunit successors.
88 short NumPreds; // # of preds.
89 short NumSuccs; // # of sucss.
90 short NumPredsLeft; // # of preds not scheduled.
91 short NumSuccsLeft; // # of succs not scheduled.
92 short NumChainPredsLeft; // # of chain preds not scheduled.
93 short NumChainSuccsLeft; // # of chain succs not scheduled.
94 bool isTwoAddress : 1; // Is a two-address instruction.
95 bool isCommutable : 1; // Is a commutable instruction.
96 bool isPending : 1; // True once pending.
97 bool isAvailable : 1; // True once available.
98 bool isScheduled : 1; // True once scheduled.
99 unsigned short Latency; // Node latency.
100 unsigned CycleBound; // Upper/lower cycle to be scheduled at.
101 unsigned Cycle; // Once scheduled, the cycle of the op.
102 unsigned Depth; // Node depth;
103 unsigned Height; // Node height;
104 unsigned NodeNum; // Entry # of node in the node vector.
106 SUnit(SDNode *node, unsigned nodenum)
107 : Node(node), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
108 NumChainPredsLeft(0), NumChainSuccsLeft(0),
109 isTwoAddress(false), isCommutable(false),
110 isPending(false), isAvailable(false), isScheduled(false),
111 Latency(0), CycleBound(0), Cycle(0), Depth(0), Height(0),
114 void dump(const SelectionDAG *G) const;
115 void dumpAll(const SelectionDAG *G) const;
118 //===--------------------------------------------------------------------===//
119 /// SchedulingPriorityQueue - This interface is used to plug different
120 /// priorities computation algorithms into the list scheduler. It implements
121 /// the interface of a standard priority queue, where nodes are inserted in
122 /// arbitrary order and returned in priority order. The computation of the
123 /// priority and the representation of the queue are totally up to the
124 /// implementation to decide.
126 class SchedulingPriorityQueue {
128 virtual ~SchedulingPriorityQueue() {}
130 virtual void initNodes(const std::vector<SUnit> &SUnits) = 0;
131 virtual void releaseState() = 0;
133 virtual bool empty() const = 0;
134 virtual void push(SUnit *U) = 0;
136 virtual void push_all(const std::vector<SUnit *> &Nodes) = 0;
137 virtual SUnit *pop() = 0;
139 /// ScheduledNode - As each node is scheduled, this method is invoked. This
140 /// allows the priority function to adjust the priority of node that have
141 /// already been emitted.
142 virtual void ScheduledNode(SUnit *Node) {}
147 SelectionDAG &DAG; // DAG of the current basic block
148 MachineBasicBlock *BB; // Current basic block
149 const TargetMachine &TM; // Target processor
150 const TargetInstrInfo *TII; // Target instruction information
151 const MRegisterInfo *MRI; // Target processor register info
152 SSARegMap *RegMap; // Virtual/real register map
153 MachineConstantPool *ConstPool; // Target constant pool
154 std::vector<SUnit*> Sequence; // The schedule. Null SUnit*'s
155 // represent noop instructions.
156 std::map<SDNode*, SUnit*> SUnitMap; // SDNode to SUnit mapping (n -> 1).
157 std::vector<SUnit> SUnits; // The scheduling units.
158 std::set<SDNode*> CommuteSet; // Nodes the should be commuted.
160 ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb,
161 const TargetMachine &tm)
162 : DAG(dag), BB(bb), TM(tm) {}
164 virtual ~ScheduleDAG() {}
166 /// Run - perform scheduling.
168 MachineBasicBlock *Run();
170 /// isPassiveNode - Return true if the node is a non-scheduled leaf.
172 static bool isPassiveNode(SDNode *Node) {
173 if (isa<ConstantSDNode>(Node)) return true;
174 if (isa<RegisterSDNode>(Node)) return true;
175 if (isa<GlobalAddressSDNode>(Node)) return true;
176 if (isa<BasicBlockSDNode>(Node)) return true;
177 if (isa<FrameIndexSDNode>(Node)) return true;
178 if (isa<ConstantPoolSDNode>(Node)) return true;
179 if (isa<JumpTableSDNode>(Node)) return true;
180 if (isa<ExternalSymbolSDNode>(Node)) return true;
184 /// NewSUnit - Creates a new SUnit and return a ptr to it.
186 SUnit *NewSUnit(SDNode *N) {
187 SUnits.push_back(SUnit(N, SUnits.size()));
188 return &SUnits.back();
191 /// BuildSchedUnits - Build SUnits from the selection dag that we are input.
192 /// This SUnit graph is similar to the SelectionDAG, but represents flagged
193 /// together nodes with a single SUnit.
194 void BuildSchedUnits();
196 /// CalculateDepths, CalculateHeights - Calculate node depth / height.
198 void CalculateDepths();
199 void CalculateHeights();
201 /// EmitNode - Generate machine code for an node and needed dependencies.
202 /// VRBaseMap contains, for each already emitted node, the first virtual
203 /// register number for the results of the node.
205 void EmitNode(SDNode *Node, std::map<SDNode*, unsigned> &VRBaseMap);
207 /// EmitNoop - Emit a noop instruction.
213 void dumpSchedule() const;
215 /// Schedule - Order nodes according to selected style.
217 virtual void Schedule() {}
220 void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum,
221 const TargetInstrDescriptor *II,
222 std::map<SDNode*, unsigned> &VRBaseMap);
225 /// createBFS_DAGScheduler - This creates a simple breadth first instruction
227 ScheduleDAG *createBFS_DAGScheduler(SelectionDAGISel *IS,
229 MachineBasicBlock *BB);
231 /// createSimpleDAGScheduler - This creates a simple two pass instruction
232 /// scheduler using instruction itinerary.
233 ScheduleDAG* createSimpleDAGScheduler(SelectionDAGISel *IS,
235 MachineBasicBlock *BB);
237 /// createNoItinsDAGScheduler - This creates a simple two pass instruction
238 /// scheduler without using instruction itinerary.
239 ScheduleDAG* createNoItinsDAGScheduler(SelectionDAGISel *IS,
241 MachineBasicBlock *BB);
243 /// createBURRListDAGScheduler - This creates a bottom up register usage
244 /// reduction list scheduler.
245 ScheduleDAG* createBURRListDAGScheduler(SelectionDAGISel *IS,
247 MachineBasicBlock *BB);
249 /// createTDRRListDAGScheduler - This creates a top down register usage
250 /// reduction list scheduler.
251 ScheduleDAG* createTDRRListDAGScheduler(SelectionDAGISel *IS,
253 MachineBasicBlock *BB);
255 /// createTDListDAGScheduler - This creates a top-down list scheduler with
256 /// a hazard recognizer.
257 ScheduleDAG* createTDListDAGScheduler(SelectionDAGISel *IS,
259 MachineBasicBlock *BB);
261 /// createDefaultScheduler - This creates an instruction scheduler appropriate
263 ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS,
265 MachineBasicBlock *BB);