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) {}
146 SelectionDAG &DAG; // DAG of the current basic block
147 MachineBasicBlock *BB; // Current basic block
148 const TargetMachine &TM; // Target processor
149 const TargetInstrInfo *TII; // Target instruction information
150 const MRegisterInfo *MRI; // Target processor register info
151 SSARegMap *RegMap; // Virtual/real register map
152 MachineConstantPool *ConstPool; // Target constant pool
153 std::vector<SUnit*> Sequence; // The schedule. Null SUnit*'s
154 // represent noop instructions.
155 std::map<SDNode*, SUnit*> SUnitMap; // SDNode to SUnit mapping (n -> 1).
156 std::vector<SUnit> SUnits; // The scheduling units.
157 std::set<SDNode*> CommuteSet; // Nodes the should be commuted.
159 ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb,
160 const TargetMachine &tm)
161 : DAG(dag), BB(bb), TM(tm) {}
163 virtual ~ScheduleDAG() {}
165 /// Run - perform scheduling.
167 MachineBasicBlock *Run();
169 /// isPassiveNode - Return true if the node is a non-scheduled leaf.
171 static bool isPassiveNode(SDNode *Node) {
172 if (isa<ConstantSDNode>(Node)) return true;
173 if (isa<RegisterSDNode>(Node)) return true;
174 if (isa<GlobalAddressSDNode>(Node)) return true;
175 if (isa<BasicBlockSDNode>(Node)) return true;
176 if (isa<FrameIndexSDNode>(Node)) return true;
177 if (isa<ConstantPoolSDNode>(Node)) return true;
178 if (isa<JumpTableSDNode>(Node)) return true;
179 if (isa<ExternalSymbolSDNode>(Node)) return true;
183 /// NewSUnit - Creates a new SUnit and return a ptr to it.
185 SUnit *NewSUnit(SDNode *N) {
186 SUnits.push_back(SUnit(N, SUnits.size()));
187 return &SUnits.back();
190 /// BuildSchedUnits - Build SUnits from the selection dag that we are input.
191 /// This SUnit graph is similar to the SelectionDAG, but represents flagged
192 /// together nodes with a single SUnit.
193 void BuildSchedUnits();
195 /// CalculateDepths, CalculateHeights - Calculate node depth / height.
197 void CalculateDepths();
198 void CalculateHeights();
200 /// EmitNode - Generate machine code for an node and needed dependencies.
201 /// VRBaseMap contains, for each already emitted node, the first virtual
202 /// register number for the results of the node.
204 void EmitNode(SDNode *Node, std::map<SDNode*, unsigned> &VRBaseMap);
206 /// EmitNoop - Emit a noop instruction.
212 void dumpSchedule() const;
214 /// Schedule - Order nodes according to selected style.
216 virtual void Schedule() {}
219 void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum,
220 const TargetInstrDescriptor *II,
221 std::map<SDNode*, unsigned> &VRBaseMap);
224 ScheduleDAG *createBFS_DAGScheduler(SelectionDAG &DAG, MachineBasicBlock *BB);
226 /// createSimpleDAGScheduler - This creates a simple two pass instruction
228 ScheduleDAG* createSimpleDAGScheduler(bool NoItins, SelectionDAG &DAG,
229 MachineBasicBlock *BB);
231 /// createBURRListDAGScheduler - This creates a bottom up register usage
232 /// reduction list scheduler.
233 ScheduleDAG* createBURRListDAGScheduler(SelectionDAG &DAG,
234 MachineBasicBlock *BB);
236 /// createTDRRListDAGScheduler - This creates a top down register usage
237 /// reduction list scheduler.
238 ScheduleDAG* createTDRRListDAGScheduler(SelectionDAG &DAG,
239 MachineBasicBlock *BB);
241 /// createTDListDAGScheduler - This creates a top-down list scheduler with
242 /// the specified hazard recognizer. This takes ownership of the hazard
243 /// recognizer and deletes it when done.
244 ScheduleDAG* createTDListDAGScheduler(SelectionDAG &DAG,
245 MachineBasicBlock *BB,
246 HazardRecognizer *HR);