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;
30 class TargetInstrInfo;
31 class TargetInstrDescriptor;
34 /// HazardRecognizer - This determines whether or not an instruction can be
35 /// issued this cycle, and whether or not a noop needs to be inserted to handle
37 class HazardRecognizer {
39 virtual ~HazardRecognizer();
42 NoHazard, // This instruction can be emitted at this cycle.
43 Hazard, // This instruction can't be emitted at this cycle.
44 NoopHazard, // This instruction can't be emitted, and needs noops.
47 /// getHazardType - Return the hazard type of emitting this node. There are
48 /// three possible results. Either:
49 /// * NoHazard: it is legal to issue this instruction on this cycle.
50 /// * Hazard: issuing this instruction would stall the machine. If some
51 /// other instruction is available, issue it first.
52 /// * NoopHazard: issuing this instruction would break the program. If
53 /// some other instruction can be issued, do so, otherwise issue a noop.
54 virtual HazardType getHazardType(SDNode *Node) {
58 /// EmitInstruction - This callback is invoked when an instruction is
59 /// emitted, to advance the hazard state.
60 virtual void EmitInstruction(SDNode *Node) {
63 /// AdvanceCycle - This callback is invoked when no instructions can be
64 /// issued on this cycle without a hazard. This should increment the
65 /// internal state of the hazard recognizer so that previously "Hazard"
66 /// instructions will now not be hazards.
67 virtual void AdvanceCycle() {
70 /// EmitNoop - This callback is invoked when a noop was added to the
71 /// instruction stream.
72 virtual void EmitNoop() {
76 /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
77 /// a group of nodes flagged together.
79 SDNode *Node; // Representative node.
80 std::vector<SDNode*> FlaggedNodes; // All nodes flagged to Node.
82 // Preds/Succs - The SUnits before/after us in the graph. The boolean value
83 // is true if the edge is a token chain edge, false if it is a value edge.
84 std::set<std::pair<SUnit*,bool> > Preds; // All sunit predecessors.
85 std::set<std::pair<SUnit*,bool> > Succs; // All sunit successors.
87 short NumPreds; // # of preds.
88 short NumSuccs; // # of sucss.
89 short NumPredsLeft; // # of preds not scheduled.
90 short NumSuccsLeft; // # of succs not scheduled.
91 short NumChainPredsLeft; // # of chain preds not scheduled.
92 short NumChainSuccsLeft; // # of chain succs not scheduled.
93 bool isTwoAddress : 1; // Is a two-address instruction.
94 bool isCommutable : 1; // Is a commutable instruction.
95 bool isPending : 1; // True once pending.
96 bool isAvailable : 1; // True once available.
97 bool isScheduled : 1; // True once scheduled.
98 unsigned short Latency; // Node latency.
99 unsigned CycleBound; // Upper/lower cycle to be scheduled at.
100 unsigned Cycle; // Once scheduled, the cycle of the op.
101 unsigned Depth; // Node depth;
102 unsigned Height; // Node height;
103 unsigned NodeNum; // Entry # of node in the node vector.
105 SUnit(SDNode *node, unsigned nodenum)
106 : Node(node), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
107 NumChainPredsLeft(0), NumChainSuccsLeft(0),
108 isTwoAddress(false), isCommutable(false),
109 isPending(false), isAvailable(false), isScheduled(false),
110 Latency(0), CycleBound(0), Cycle(0), Depth(0), Height(0),
113 void dump(const SelectionDAG *G) const;
114 void dumpAll(const SelectionDAG *G) const;
117 //===--------------------------------------------------------------------===//
118 /// SchedulingPriorityQueue - This interface is used to plug different
119 /// priorities computation algorithms into the list scheduler. It implements
120 /// the interface of a standard priority queue, where nodes are inserted in
121 /// arbitrary order and returned in priority order. The computation of the
122 /// priority and the representation of the queue are totally up to the
123 /// implementation to decide.
125 class SchedulingPriorityQueue {
127 virtual ~SchedulingPriorityQueue() {}
129 virtual void initNodes(const std::vector<SUnit> &SUnits) = 0;
130 virtual void releaseState() = 0;
132 virtual bool empty() const = 0;
133 virtual void push(SUnit *U) = 0;
135 virtual void push_all(const std::vector<SUnit *> &Nodes) = 0;
136 virtual SUnit *pop() = 0;
138 /// ScheduledNode - As each node is scheduled, this method is invoked. This
139 /// allows the priority function to adjust the priority of node that have
140 /// already been emitted.
141 virtual void ScheduledNode(SUnit *Node) {}
147 // Scheduling heuristics
148 enum SchedHeuristics {
149 defaultScheduling, // Let the target specify its preference.
150 noScheduling, // No scheduling, emit breadth first sequence.
151 simpleScheduling, // Two pass, min. critical path, max. utilization.
152 simpleNoItinScheduling, // Same as above exact using generic latency.
153 listSchedulingBURR, // Bottom-up reg reduction list scheduling.
154 listSchedulingTDRR, // Top-down reg reduction list scheduling.
155 listSchedulingTD // Top-down list scheduler.
158 SelectionDAG &DAG; // DAG of the current basic block
159 MachineBasicBlock *BB; // Current basic block
160 const TargetMachine &TM; // Target processor
161 const TargetInstrInfo *TII; // Target instruction information
162 const MRegisterInfo *MRI; // Target processor register info
163 SSARegMap *RegMap; // Virtual/real register map
164 MachineConstantPool *ConstPool; // Target constant pool
165 std::vector<SUnit*> Sequence; // The schedule. Null SUnit*'s
166 // represent noop instructions.
167 std::map<SDNode*, SUnit*> SUnitMap; // SDNode to SUnit mapping (n -> 1).
168 std::vector<SUnit> SUnits; // The scheduling units.
169 std::set<SDNode*> CommuteSet; // Nodes the should be commuted.
171 ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb,
172 const TargetMachine &tm)
173 : DAG(dag), BB(bb), TM(tm) {}
175 virtual ~ScheduleDAG() {}
177 /// Run - perform scheduling.
179 MachineBasicBlock *Run();
181 /// isPassiveNode - Return true if the node is a non-scheduled leaf.
183 static bool isPassiveNode(SDNode *Node) {
184 if (isa<ConstantSDNode>(Node)) return true;
185 if (isa<RegisterSDNode>(Node)) return true;
186 if (isa<GlobalAddressSDNode>(Node)) return true;
187 if (isa<BasicBlockSDNode>(Node)) return true;
188 if (isa<FrameIndexSDNode>(Node)) return true;
189 if (isa<ConstantPoolSDNode>(Node)) return true;
190 if (isa<JumpTableSDNode>(Node)) return true;
191 if (isa<ExternalSymbolSDNode>(Node)) return true;
195 /// NewSUnit - Creates a new SUnit and return a ptr to it.
197 SUnit *NewSUnit(SDNode *N) {
198 SUnits.push_back(SUnit(N, SUnits.size()));
199 return &SUnits.back();
202 /// BuildSchedUnits - Build SUnits from the selection dag that we are input.
203 /// This SUnit graph is similar to the SelectionDAG, but represents flagged
204 /// together nodes with a single SUnit.
205 void BuildSchedUnits();
207 /// CalculateDepths, CalculateHeights - Calculate node depth / height.
209 void CalculateDepths();
210 void CalculateHeights();
212 /// EmitNode - Generate machine code for an node and needed dependencies.
213 /// VRBaseMap contains, for each already emitted node, the first virtual
214 /// register number for the results of the node.
216 void EmitNode(SDNode *Node, std::map<SDNode*, unsigned> &VRBaseMap);
218 /// EmitNoop - Emit a noop instruction.
224 void dumpSchedule() const;
226 /// Schedule - Order nodes according to selected style.
228 virtual void Schedule() {}
231 void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum,
232 const TargetInstrDescriptor *II,
233 std::map<SDNode*, unsigned> &VRBaseMap);
236 ScheduleDAG *createBFS_DAGScheduler(SelectionDAG &DAG, MachineBasicBlock *BB);
238 /// createSimpleDAGScheduler - This creates a simple two pass instruction
240 ScheduleDAG* createSimpleDAGScheduler(bool NoItins, SelectionDAG &DAG,
241 MachineBasicBlock *BB);
243 /// createBURRListDAGScheduler - This creates a bottom up register usage
244 /// reduction list scheduler.
245 ScheduleDAG* createBURRListDAGScheduler(SelectionDAG &DAG,
246 MachineBasicBlock *BB);
248 /// createTDRRListDAGScheduler - This creates a top down register usage
249 /// reduction list scheduler.
250 ScheduleDAG* createTDRRListDAGScheduler(SelectionDAG &DAG,
251 MachineBasicBlock *BB);
253 /// createTDListDAGScheduler - This creates a top-down list scheduler with
254 /// the specified hazard recognizer. This takes ownership of the hazard
255 /// recognizer and deletes it when done.
256 ScheduleDAG* createTDListDAGScheduler(SelectionDAG &DAG,
257 MachineBasicBlock *BB,
258 HazardRecognizer *HR);