ScheduleDAG.h revision 74d2fd8dd847e0ebccef30e2c5907ff09495d518
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#include "llvm/ADT/DenseMap.h" 20#include "llvm/ADT/GraphTraits.h" 21#include "llvm/ADT/SmallSet.h" 22 23namespace llvm { 24 struct InstrStage; 25 struct SUnit; 26 class MachineConstantPool; 27 class MachineModuleInfo; 28 class MachineInstr; 29 class MRegisterInfo; 30 class SelectionDAG; 31 class SelectionDAGISel; 32 class SSARegMap; 33 class TargetInstrInfo; 34 class TargetInstrDescriptor; 35 class TargetMachine; 36 class TargetRegisterClass; 37 38 /// HazardRecognizer - This determines whether or not an instruction can be 39 /// issued this cycle, and whether or not a noop needs to be inserted to handle 40 /// the hazard. 41 class HazardRecognizer { 42 public: 43 virtual ~HazardRecognizer(); 44 45 enum HazardType { 46 NoHazard, // This instruction can be emitted at this cycle. 47 Hazard, // This instruction can't be emitted at this cycle. 48 NoopHazard // This instruction can't be emitted, and needs noops. 49 }; 50 51 /// getHazardType - Return the hazard type of emitting this node. There are 52 /// three possible results. Either: 53 /// * NoHazard: it is legal to issue this instruction on this cycle. 54 /// * Hazard: issuing this instruction would stall the machine. If some 55 /// other instruction is available, issue it first. 56 /// * NoopHazard: issuing this instruction would break the program. If 57 /// some other instruction can be issued, do so, otherwise issue a noop. 58 virtual HazardType getHazardType(SDNode *Node) { 59 return NoHazard; 60 } 61 62 /// EmitInstruction - This callback is invoked when an instruction is 63 /// emitted, to advance the hazard state. 64 virtual void EmitInstruction(SDNode *Node) { 65 } 66 67 /// AdvanceCycle - This callback is invoked when no instructions can be 68 /// issued on this cycle without a hazard. This should increment the 69 /// internal state of the hazard recognizer so that previously "Hazard" 70 /// instructions will now not be hazards. 71 virtual void AdvanceCycle() { 72 } 73 74 /// EmitNoop - This callback is invoked when a noop was added to the 75 /// instruction stream. 76 virtual void EmitNoop() { 77 } 78 }; 79 80 /// SDep - Scheduling dependency. It keeps track of dependent nodes, 81 /// cost of the depdenency, etc. 82 struct SDep { 83 SUnit *Dep; // Dependent - either a predecessor or a successor. 84 unsigned Reg; // If non-zero, this dep is a phy register dependency. 85 int Cost; // Cost of the dependency. 86 bool isCtrl : 1; // True iff it's a control dependency. 87 bool isSpecial : 1; // True iff it's a special ctrl dep added during sched. 88 SDep(SUnit *d, unsigned r, int t, bool c, bool s) 89 : Dep(d), Reg(r), Cost(t), isCtrl(c), isSpecial(s) {} 90 }; 91 92 /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or 93 /// a group of nodes flagged together. 94 struct SUnit { 95 SDNode *Node; // Representative node. 96 SmallVector<SDNode*,4> FlaggedNodes;// All nodes flagged to Node. 97 unsigned InstanceNo; // Instance#. One SDNode can be multiple 98 // SUnit due to cloning. 99 100 // Preds/Succs - The SUnits before/after us in the graph. The boolean value 101 // is true if the edge is a token chain edge, false if it is a value edge. 102 SmallVector<SDep, 4> Preds; // All sunit predecessors. 103 SmallVector<SDep, 4> Succs; // All sunit successors. 104 105 typedef SmallVector<SDep, 4>::iterator pred_iterator; 106 typedef SmallVector<SDep, 4>::iterator succ_iterator; 107 typedef SmallVector<SDep, 4>::const_iterator const_pred_iterator; 108 typedef SmallVector<SDep, 4>::const_iterator const_succ_iterator; 109 110 unsigned NodeNum; // Entry # of node in the node vector. 111 unsigned short Latency; // Node latency. 112 short NumPreds; // # of preds. 113 short NumSuccs; // # of sucss. 114 short NumPredsLeft; // # of preds not scheduled. 115 short NumSuccsLeft; // # of succs not scheduled. 116 bool isTwoAddress : 1; // Is a two-address instruction. 117 bool isCommutable : 1; // Is a commutable instruction. 118 bool hasImplicitDefs : 1; // Has implicit physical reg defs. 119 bool isPending : 1; // True once pending. 120 bool isAvailable : 1; // True once available. 121 bool isScheduled : 1; // True once scheduled. 122 unsigned CycleBound; // Upper/lower cycle to be scheduled at. 123 unsigned Cycle; // Once scheduled, the cycle of the op. 124 unsigned Depth; // Node depth; 125 unsigned Height; // Node height; 126 const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null. 127 const TargetRegisterClass *CopySrcRC; 128 129 SUnit(SDNode *node, unsigned nodenum) 130 : Node(node), InstanceNo(0), NodeNum(nodenum), Latency(0), 131 NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0), 132 isTwoAddress(false), isCommutable(false), hasImplicitDefs(false), 133 isPending(false), isAvailable(false), isScheduled(false), 134 CycleBound(0), Cycle(0), Depth(0), Height(0), 135 CopyDstRC(NULL), CopySrcRC(NULL) {} 136 137 /// addPred - This adds the specified node as a pred of the current node if 138 /// not already. This returns true if this is a new pred. 139 bool addPred(SUnit *N, bool isCtrl, bool isSpecial, 140 unsigned PhyReg = 0, int Cost = 1) { 141 for (unsigned i = 0, e = Preds.size(); i != e; ++i) 142 if (Preds[i].Dep == N && 143 Preds[i].isCtrl == isCtrl && Preds[i].isSpecial == isSpecial) 144 return false; 145 Preds.push_back(SDep(N, PhyReg, Cost, isCtrl, isSpecial)); 146 N->Succs.push_back(SDep(this, PhyReg, Cost, isCtrl, isSpecial)); 147 if (!isCtrl) { 148 ++NumPreds; 149 ++N->NumSuccs; 150 } 151 if (!N->isScheduled) 152 ++NumPredsLeft; 153 if (!isScheduled) 154 ++N->NumSuccsLeft; 155 return true; 156 } 157 158 bool removePred(SUnit *N, bool isCtrl, bool isSpecial) { 159 for (SmallVector<SDep, 4>::iterator I = Preds.begin(), E = Preds.end(); 160 I != E; ++I) 161 if (I->Dep == N && I->isCtrl == isCtrl && I->isSpecial == isSpecial) { 162 bool FoundSucc = false; 163 for (SmallVector<SDep, 4>::iterator II = N->Succs.begin(), 164 EE = N->Succs.end(); II != EE; ++II) 165 if (II->Dep == this && 166 II->isCtrl == isCtrl && II->isSpecial == isSpecial) { 167 FoundSucc = true; 168 N->Succs.erase(II); 169 break; 170 } 171 assert(FoundSucc && "Mismatching preds / succs lists!"); 172 Preds.erase(I); 173 if (!isCtrl) { 174 --NumPreds; 175 --N->NumSuccs; 176 } 177 if (!N->isScheduled) 178 --NumPredsLeft; 179 if (!isScheduled) 180 --N->NumSuccsLeft; 181 return true; 182 } 183 return false; 184 } 185 186 bool isPred(SUnit *N) { 187 for (unsigned i = 0, e = Preds.size(); i != e; ++i) 188 if (Preds[i].Dep == N) 189 return true; 190 return false; 191 } 192 193 bool isSucc(SUnit *N) { 194 for (unsigned i = 0, e = Succs.size(); i != e; ++i) 195 if (Succs[i].Dep == N) 196 return true; 197 return false; 198 } 199 200 void dump(const SelectionDAG *G) const; 201 void dumpAll(const SelectionDAG *G) const; 202 }; 203 204 //===--------------------------------------------------------------------===// 205 /// SchedulingPriorityQueue - This interface is used to plug different 206 /// priorities computation algorithms into the list scheduler. It implements 207 /// the interface of a standard priority queue, where nodes are inserted in 208 /// arbitrary order and returned in priority order. The computation of the 209 /// priority and the representation of the queue are totally up to the 210 /// implementation to decide. 211 /// 212 class SchedulingPriorityQueue { 213 public: 214 virtual ~SchedulingPriorityQueue() {} 215 216 virtual void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &SUMap, 217 std::vector<SUnit> &SUnits) = 0; 218 virtual void addNode(const SUnit *SU) = 0; 219 virtual void updateNode(const SUnit *SU) = 0; 220 virtual void releaseState() = 0; 221 222 virtual unsigned size() const = 0; 223 virtual bool empty() const = 0; 224 virtual void push(SUnit *U) = 0; 225 226 virtual void push_all(const std::vector<SUnit *> &Nodes) = 0; 227 virtual SUnit *pop() = 0; 228 229 virtual void remove(SUnit *SU) = 0; 230 231 /// ScheduledNode - As each node is scheduled, this method is invoked. This 232 /// allows the priority function to adjust the priority of node that have 233 /// already been emitted. 234 virtual void ScheduledNode(SUnit *Node) {} 235 236 virtual void UnscheduledNode(SUnit *Node) {} 237 }; 238 239 class ScheduleDAG { 240 public: 241 SelectionDAG &DAG; // DAG of the current basic block 242 MachineBasicBlock *BB; // Current basic block 243 const TargetMachine &TM; // Target processor 244 const TargetInstrInfo *TII; // Target instruction information 245 const MRegisterInfo *MRI; // Target processor register info 246 SSARegMap *RegMap; // Virtual/real register map 247 MachineConstantPool *ConstPool; // Target constant pool 248 std::vector<SUnit*> Sequence; // The schedule. Null SUnit*'s 249 // represent noop instructions. 250 DenseMap<SDNode*, std::vector<SUnit*> > SUnitMap; 251 // SDNode to SUnit mapping (n -> n). 252 std::vector<SUnit> SUnits; // The scheduling units. 253 SmallSet<SDNode*, 16> CommuteSet; // Nodes the should be commuted. 254 255 ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb, 256 const TargetMachine &tm) 257 : DAG(dag), BB(bb), TM(tm) {} 258 259 virtual ~ScheduleDAG() {} 260 261 /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered 262 /// using 'dot'. 263 /// 264 void viewGraph(); 265 266 /// Run - perform scheduling. 267 /// 268 MachineBasicBlock *Run(); 269 270 /// isPassiveNode - Return true if the node is a non-scheduled leaf. 271 /// 272 static bool isPassiveNode(SDNode *Node) { 273 if (isa<ConstantSDNode>(Node)) return true; 274 if (isa<RegisterSDNode>(Node)) return true; 275 if (isa<GlobalAddressSDNode>(Node)) return true; 276 if (isa<BasicBlockSDNode>(Node)) return true; 277 if (isa<FrameIndexSDNode>(Node)) return true; 278 if (isa<ConstantPoolSDNode>(Node)) return true; 279 if (isa<JumpTableSDNode>(Node)) return true; 280 if (isa<ExternalSymbolSDNode>(Node)) return true; 281 return false; 282 } 283 284 /// NewSUnit - Creates a new SUnit and return a ptr to it. 285 /// 286 SUnit *NewSUnit(SDNode *N) { 287 SUnits.push_back(SUnit(N, SUnits.size())); 288 return &SUnits.back(); 289 } 290 291 /// Clone - Creates a clone of the specified SUnit. It does not copy the 292 /// predecessors / successors info nor the temporary scheduling states. 293 SUnit *Clone(SUnit *N); 294 295 /// BuildSchedUnits - Build SUnits from the selection dag that we are input. 296 /// This SUnit graph is similar to the SelectionDAG, but represents flagged 297 /// together nodes with a single SUnit. 298 void BuildSchedUnits(); 299 300 /// CalculateDepths, CalculateHeights - Calculate node depth / height. 301 /// 302 void CalculateDepths(); 303 void CalculateHeights(); 304 305 /// CountResults - The results of target nodes have register or immediate 306 /// operands first, then an optional chain, and optional flag operands 307 /// (which do not go into the machine instrs.) 308 static unsigned CountResults(SDNode *Node); 309 310 /// CountOperands The inputs to target nodes have any actual inputs first, 311 /// followed by an optional chain operand, then flag operands. Compute the 312 /// number of actual operands that will go into the machine instr. 313 static unsigned CountOperands(SDNode *Node); 314 315 /// EmitNode - Generate machine code for an node and needed dependencies. 316 /// VRBaseMap contains, for each already emitted node, the first virtual 317 /// register number for the results of the node. 318 /// 319 void EmitNode(SDNode *Node, unsigned InstNo, 320 DenseMap<SDOperand, unsigned> &VRBaseMap); 321 322 /// EmitNoop - Emit a noop instruction. 323 /// 324 void EmitNoop(); 325 326 void EmitCrossRCCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap); 327 328 /// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an 329 /// implicit physical register output. 330 void EmitCopyFromReg(SDNode *Node, unsigned ResNo, unsigned InstNo, 331 unsigned SrcReg, 332 DenseMap<SDOperand, unsigned> &VRBaseMap); 333 334 void CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, 335 const TargetInstrDescriptor &II, 336 DenseMap<SDOperand, unsigned> &VRBaseMap); 337 338 void EmitSchedule(); 339 340 void dumpSchedule() const; 341 342 /// Schedule - Order nodes according to selected style. 343 /// 344 virtual void Schedule() {} 345 346 private: 347 /// EmitSubregNode - Generate machine code for subreg nodes. 348 /// 349 void EmitSubregNode(SDNode *Node, 350 DenseMap<SDOperand, unsigned> &VRBaseMap); 351 352 void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum, 353 const TargetInstrDescriptor *II, 354 DenseMap<SDOperand, unsigned> &VRBaseMap); 355 }; 356 357 /// createBFS_DAGScheduler - This creates a simple breadth first instruction 358 /// scheduler. 359 ScheduleDAG *createBFS_DAGScheduler(SelectionDAGISel *IS, 360 SelectionDAG *DAG, 361 MachineBasicBlock *BB); 362 363 /// createSimpleDAGScheduler - This creates a simple two pass instruction 364 /// scheduler using instruction itinerary. 365 ScheduleDAG* createSimpleDAGScheduler(SelectionDAGISel *IS, 366 SelectionDAG *DAG, 367 MachineBasicBlock *BB); 368 369 /// createNoItinsDAGScheduler - This creates a simple two pass instruction 370 /// scheduler without using instruction itinerary. 371 ScheduleDAG* createNoItinsDAGScheduler(SelectionDAGISel *IS, 372 SelectionDAG *DAG, 373 MachineBasicBlock *BB); 374 375 /// createBURRListDAGScheduler - This creates a bottom up register usage 376 /// reduction list scheduler. 377 ScheduleDAG* createBURRListDAGScheduler(SelectionDAGISel *IS, 378 SelectionDAG *DAG, 379 MachineBasicBlock *BB); 380 381 /// createTDRRListDAGScheduler - This creates a top down register usage 382 /// reduction list scheduler. 383 ScheduleDAG* createTDRRListDAGScheduler(SelectionDAGISel *IS, 384 SelectionDAG *DAG, 385 MachineBasicBlock *BB); 386 387 /// createTDListDAGScheduler - This creates a top-down list scheduler with 388 /// a hazard recognizer. 389 ScheduleDAG* createTDListDAGScheduler(SelectionDAGISel *IS, 390 SelectionDAG *DAG, 391 MachineBasicBlock *BB); 392 393 /// createDefaultScheduler - This creates an instruction scheduler appropriate 394 /// for the target. 395 ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS, 396 SelectionDAG *DAG, 397 MachineBasicBlock *BB); 398 399 class SUnitIterator : public forward_iterator<SUnit, ptrdiff_t> { 400 SUnit *Node; 401 unsigned Operand; 402 403 SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {} 404 public: 405 bool operator==(const SUnitIterator& x) const { 406 return Operand == x.Operand; 407 } 408 bool operator!=(const SUnitIterator& x) const { return !operator==(x); } 409 410 const SUnitIterator &operator=(const SUnitIterator &I) { 411 assert(I.Node == Node && "Cannot assign iterators to two different nodes!"); 412 Operand = I.Operand; 413 return *this; 414 } 415 416 pointer operator*() const { 417 return Node->Preds[Operand].Dep; 418 } 419 pointer operator->() const { return operator*(); } 420 421 SUnitIterator& operator++() { // Preincrement 422 ++Operand; 423 return *this; 424 } 425 SUnitIterator operator++(int) { // Postincrement 426 SUnitIterator tmp = *this; ++*this; return tmp; 427 } 428 429 static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); } 430 static SUnitIterator end (SUnit *N) { 431 return SUnitIterator(N, N->Preds.size()); 432 } 433 434 unsigned getOperand() const { return Operand; } 435 const SUnit *getNode() const { return Node; } 436 bool isCtrlDep() const { return Node->Preds[Operand].isCtrl; } 437 }; 438 439 template <> struct GraphTraits<SUnit*> { 440 typedef SUnit NodeType; 441 typedef SUnitIterator ChildIteratorType; 442 static inline NodeType *getEntryNode(SUnit *N) { return N; } 443 static inline ChildIteratorType child_begin(NodeType *N) { 444 return SUnitIterator::begin(N); 445 } 446 static inline ChildIteratorType child_end(NodeType *N) { 447 return SUnitIterator::end(N); 448 } 449 }; 450 451 template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> { 452 typedef std::vector<SUnit>::iterator nodes_iterator; 453 static nodes_iterator nodes_begin(ScheduleDAG *G) { 454 return G->SUnits.begin(); 455 } 456 static nodes_iterator nodes_end(ScheduleDAG *G) { 457 return G->SUnits.end(); 458 } 459 }; 460} 461 462#endif 463