ScheduleDAG.h revision 37cb415eec53e20ed77c1c90f86310de217f3e6c
1//===------- llvm/CodeGen/ScheduleDAG.h - Common Base Class------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 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. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the ScheduleDAG class, which is used as the common 11// base class for SelectionDAG-based instruction scheduler. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef LLVM_CODEGEN_SCHEDULEDAG_H 16#define LLVM_CODEGEN_SCHEDULEDAG_H 17 18#include "llvm/CodeGen/SelectionDAG.h" 19 20namespace llvm { 21 struct InstrStage; 22 class MachineConstantPool; 23 class MachineDebugInfo; 24 class MachineInstr; 25 class MRegisterInfo; 26 class SelectionDAG; 27 class SSARegMap; 28 class TargetInstrInfo; 29 class TargetInstrDescriptor; 30 class TargetMachine; 31 32 class NodeInfo; 33 typedef NodeInfo *NodeInfoPtr; 34 typedef std::vector<NodeInfoPtr> NIVector; 35 typedef std::vector<NodeInfoPtr>::iterator NIIterator; 36 37 /// HazardRecognizer - This determines whether or not an instruction can be 38 /// issued this cycle, and whether or not a noop needs to be inserted to handle 39 /// the hazard. 40 class HazardRecognizer { 41 public: 42 virtual ~HazardRecognizer(); 43 44 enum HazardType { 45 NoHazard, // This instruction can be emitted at this cycle. 46 Hazard, // This instruction can't be emitted at this cycle. 47 NoopHazard, // This instruction can't be emitted, and needs noops. 48 }; 49 50 /// getHazardType - Return the hazard type of emitting this node. There are 51 /// three possible results. Either: 52 /// * NoHazard: it is legal to issue this instruction on this cycle. 53 /// * Hazard: issuing this instruction would stall the machine. If some 54 /// other instruction is available, issue it first. 55 /// * NoopHazard: issuing this instruction would break the program. If 56 /// some other instruction can be issued, do so, otherwise issue a noop. 57 virtual HazardType getHazardType(SDNode *Node) { 58 return NoHazard; 59 } 60 61 /// EmitInstruction - This callback is invoked when an instruction is 62 /// emitted, to advance the hazard state. 63 virtual void EmitInstruction(SDNode *Node) { 64 } 65 66 /// AdvanceCycle - This callback is invoked when no instructions can be 67 /// issued on this cycle without a hazard. This should increment the 68 /// internal state of the hazard recognizer so that previously "Hazard" 69 /// instructions will now not be hazards. 70 virtual void AdvanceCycle() { 71 } 72 73 /// EmitNoop - This callback is invoked when a noop was added to the 74 /// instruction stream. 75 virtual void EmitNoop() { 76 } 77 }; 78 79 //===--------------------------------------------------------------------===// 80 /// 81 /// Node group - This struct is used to manage flagged node groups. 82 /// 83 class NodeGroup { 84 public: 85 NodeGroup *Next; 86 private: 87 NIVector Members; // Group member nodes 88 NodeInfo *Dominator; // Node with highest latency 89 unsigned Latency; // Total latency of the group 90 int Pending; // Number of visits pending before 91 // adding to order 92 93 public: 94 // Ctor. 95 NodeGroup() : Next(NULL), Dominator(NULL), Pending(0) {} 96 97 // Accessors 98 inline void setDominator(NodeInfo *D) { Dominator = D; } 99 inline NodeInfo *getTop() { return Members.front(); } 100 inline NodeInfo *getBottom() { return Members.back(); } 101 inline NodeInfo *getDominator() { return Dominator; } 102 inline void setLatency(unsigned L) { Latency = L; } 103 inline unsigned getLatency() { return Latency; } 104 inline int getPending() const { return Pending; } 105 inline void setPending(int P) { Pending = P; } 106 inline int addPending(int I) { return Pending += I; } 107 108 // Pass thru 109 inline bool group_empty() { return Members.empty(); } 110 inline NIIterator group_begin() { return Members.begin(); } 111 inline NIIterator group_end() { return Members.end(); } 112 inline void group_push_back(const NodeInfoPtr &NI) { 113 Members.push_back(NI); 114 } 115 inline NIIterator group_insert(NIIterator Pos, const NodeInfoPtr &NI) { 116 return Members.insert(Pos, NI); 117 } 118 inline void group_insert(NIIterator Pos, NIIterator First, 119 NIIterator Last) { 120 Members.insert(Pos, First, Last); 121 } 122 123 static void Add(NodeInfo *D, NodeInfo *U); 124 }; 125 126 //===--------------------------------------------------------------------===// 127 /// 128 /// NodeInfo - This struct tracks information used to schedule the a node. 129 /// 130 class NodeInfo { 131 private: 132 int Pending; // Number of visits pending before 133 // adding to order 134 public: 135 SDNode *Node; // DAG node 136 InstrStage *StageBegin; // First stage in itinerary 137 InstrStage *StageEnd; // Last+1 stage in itinerary 138 unsigned Latency; // Total cycles to complete instr 139 bool IsCall : 1; // Is function call 140 bool IsLoad : 1; // Is memory load 141 bool IsStore : 1; // Is memory store 142 unsigned Slot; // Node's time slot 143 NodeGroup *Group; // Grouping information 144#ifndef NDEBUG 145 unsigned Preorder; // Index before scheduling 146#endif 147 148 // Ctor. 149 NodeInfo(SDNode *N = NULL) 150 : Pending(0) 151 , Node(N) 152 , StageBegin(NULL) 153 , StageEnd(NULL) 154 , Latency(0) 155 , IsCall(false) 156 , Slot(0) 157 , Group(NULL) 158#ifndef NDEBUG 159 , Preorder(0) 160#endif 161 {} 162 163 // Accessors 164 inline bool isInGroup() const { 165 assert(!Group || !Group->group_empty() && "Group with no members"); 166 return Group != NULL; 167 } 168 inline bool isGroupDominator() const { 169 return isInGroup() && Group->getDominator() == this; 170 } 171 inline int getPending() const { 172 return Group ? Group->getPending() : Pending; 173 } 174 inline void setPending(int P) { 175 if (Group) Group->setPending(P); 176 else Pending = P; 177 } 178 inline int addPending(int I) { 179 if (Group) return Group->addPending(I); 180 else return Pending += I; 181 } 182 }; 183 184 //===--------------------------------------------------------------------===// 185 /// 186 /// NodeGroupIterator - Iterates over all the nodes indicated by the node 187 /// info. If the node is in a group then iterate over the members of the 188 /// group, otherwise just the node info. 189 /// 190 class NodeGroupIterator { 191 private: 192 NodeInfo *NI; // Node info 193 NIIterator NGI; // Node group iterator 194 NIIterator NGE; // Node group iterator end 195 196 public: 197 // Ctor. 198 NodeGroupIterator(NodeInfo *N) : NI(N) { 199 // If the node is in a group then set up the group iterator. Otherwise 200 // the group iterators will trip first time out. 201 if (N->isInGroup()) { 202 // get Group 203 NodeGroup *Group = NI->Group; 204 NGI = Group->group_begin(); 205 NGE = Group->group_end(); 206 // Prevent this node from being used (will be in members list 207 NI = NULL; 208 } 209 } 210 211 /// next - Return the next node info, otherwise NULL. 212 /// 213 NodeInfo *next() { 214 // If members list 215 if (NGI != NGE) return *NGI++; 216 // Use node as the result (may be NULL) 217 NodeInfo *Result = NI; 218 // Only use once 219 NI = NULL; 220 // Return node or NULL 221 return Result; 222 } 223 }; 224 //===--------------------------------------------------------------------===// 225 226 227 //===--------------------------------------------------------------------===// 228 /// 229 /// NodeGroupOpIterator - Iterates over all the operands of a node. If the 230 /// node is a member of a group, this iterates over all the operands of all 231 /// the members of the group. 232 /// 233 class NodeGroupOpIterator { 234 private: 235 NodeInfo *NI; // Node containing operands 236 NodeGroupIterator GI; // Node group iterator 237 SDNode::op_iterator OI; // Operand iterator 238 SDNode::op_iterator OE; // Operand iterator end 239 240 /// CheckNode - Test if node has more operands. If not get the next node 241 /// skipping over nodes that have no operands. 242 void CheckNode() { 243 // Only if operands are exhausted first 244 while (OI == OE) { 245 // Get next node info 246 NodeInfo *NI = GI.next(); 247 // Exit if nodes are exhausted 248 if (!NI) return; 249 // Get node itself 250 SDNode *Node = NI->Node; 251 // Set up the operand iterators 252 OI = Node->op_begin(); 253 OE = Node->op_end(); 254 } 255 } 256 257 public: 258 // Ctor. 259 NodeGroupOpIterator(NodeInfo *N) 260 : NI(N), GI(N), OI(SDNode::op_iterator()), OE(SDNode::op_iterator()) {} 261 262 /// isEnd - Returns true when not more operands are available. 263 /// 264 inline bool isEnd() { CheckNode(); return OI == OE; } 265 266 /// next - Returns the next available operand. 267 /// 268 inline SDOperand next() { 269 assert(OI != OE && 270 "Not checking for end of NodeGroupOpIterator correctly"); 271 return *OI++; 272 } 273 }; 274 275 class ScheduleDAG { 276 public: 277 SelectionDAG &DAG; // DAG of the current basic block 278 MachineBasicBlock *BB; // Current basic block 279 const TargetMachine &TM; // Target processor 280 const TargetInstrInfo *TII; // Target instruction information 281 const MRegisterInfo *MRI; // Target processor register info 282 SSARegMap *RegMap; // Virtual/real register map 283 MachineConstantPool *ConstPool; // Target constant pool 284 285 ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb, 286 const TargetMachine &tm) 287 : DAG(dag), BB(bb), TM(tm) {} 288 289 virtual ~ScheduleDAG() {} 290 291 /// Run - perform scheduling. 292 /// 293 MachineBasicBlock *Run(); 294 295 /// isPassiveNode - Return true if the node is a non-scheduled leaf. 296 /// 297 static bool isPassiveNode(SDNode *Node) { 298 if (isa<ConstantSDNode>(Node)) return true; 299 if (isa<RegisterSDNode>(Node)) return true; 300 if (isa<GlobalAddressSDNode>(Node)) return true; 301 if (isa<BasicBlockSDNode>(Node)) return true; 302 if (isa<FrameIndexSDNode>(Node)) return true; 303 if (isa<ConstantPoolSDNode>(Node)) return true; 304 if (isa<ExternalSymbolSDNode>(Node)) return true; 305 return false; 306 } 307 308 /// EmitNode - Generate machine code for an node and needed dependencies. 309 /// VRBaseMap contains, for each already emitted node, the first virtual 310 /// register number for the results of the node. 311 /// 312 void EmitNode(SDNode *Node, std::map<SDNode*, unsigned> &VRBaseMap); 313 314 /// EmitNoop - Emit a noop instruction. 315 /// 316 void EmitNoop(); 317 318 319 /// Schedule - Order nodes according to selected style. 320 /// 321 virtual void Schedule() {} 322 323 private: 324 void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum, 325 const TargetInstrDescriptor *II, 326 std::map<SDNode*, unsigned> &VRBaseMap); 327 }; 328 329 ScheduleDAG *createBFS_DAGScheduler(SelectionDAG &DAG, MachineBasicBlock *BB); 330 331 /// createSimpleDAGScheduler - This creates a simple two pass instruction 332 /// scheduler. 333 ScheduleDAG* createSimpleDAGScheduler(bool NoItins, SelectionDAG &DAG, 334 MachineBasicBlock *BB); 335 336 /// createBURRListDAGScheduler - This creates a bottom up register usage 337 /// reduction list scheduler. 338 ScheduleDAG* createBURRListDAGScheduler(SelectionDAG &DAG, 339 MachineBasicBlock *BB); 340 341 /// createTDListDAGScheduler - This creates a top-down list scheduler with 342 /// the specified hazard recognizer. This takes ownership of the hazard 343 /// recognizer and deletes it when done. 344 ScheduleDAG* createTDListDAGScheduler(SelectionDAG &DAG, 345 MachineBasicBlock *BB, 346 HazardRecognizer *HR); 347} 348 349#endif 350