ScheduleDAG.h revision 84bc5427d6883f73cfeae3da640acd011d35c006
1//===------- llvm/CodeGen/ScheduleDAG.h - Common Base Class------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// 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 MachineRegisterInfo; 29 class MachineInstr; 30 class MRegisterInfo; 31 class SelectionDAG; 32 class SelectionDAGISel; 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 hasPhysRegDefs : 1; // Has physreg defs that are being used. 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), hasPhysRegDefs(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 MachineRegisterInfo &RegInfo; // 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 258 virtual ~ScheduleDAG() {} 259 260 /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered 261 /// using 'dot'. 262 /// 263 void viewGraph(); 264 265 /// Run - perform scheduling. 266 /// 267 MachineBasicBlock *Run(); 268 269 /// isPassiveNode - Return true if the node is a non-scheduled leaf. 270 /// 271 static bool isPassiveNode(SDNode *Node) { 272 if (isa<ConstantSDNode>(Node)) return true; 273 if (isa<RegisterSDNode>(Node)) return true; 274 if (isa<GlobalAddressSDNode>(Node)) return true; 275 if (isa<BasicBlockSDNode>(Node)) return true; 276 if (isa<FrameIndexSDNode>(Node)) return true; 277 if (isa<ConstantPoolSDNode>(Node)) return true; 278 if (isa<JumpTableSDNode>(Node)) return true; 279 if (isa<ExternalSymbolSDNode>(Node)) return true; 280 return false; 281 } 282 283 /// NewSUnit - Creates a new SUnit and return a ptr to it. 284 /// 285 SUnit *NewSUnit(SDNode *N) { 286 SUnits.push_back(SUnit(N, SUnits.size())); 287 return &SUnits.back(); 288 } 289 290 /// Clone - Creates a clone of the specified SUnit. It does not copy the 291 /// predecessors / successors info nor the temporary scheduling states. 292 SUnit *Clone(SUnit *N); 293 294 /// BuildSchedUnits - Build SUnits from the selection dag that we are input. 295 /// This SUnit graph is similar to the SelectionDAG, but represents flagged 296 /// together nodes with a single SUnit. 297 void BuildSchedUnits(); 298 299 /// ComputeLatency - Compute node latency. 300 /// 301 void ComputeLatency(SUnit *SU); 302 303 /// CalculateDepths, CalculateHeights - Calculate node depth / height. 304 /// 305 void CalculateDepths(); 306 void CalculateHeights(); 307 308 /// CountResults - The results of target nodes have register or immediate 309 /// operands first, then an optional chain, and optional flag operands 310 /// (which do not go into the machine instrs.) 311 static unsigned CountResults(SDNode *Node); 312 313 /// CountOperands The inputs to target nodes have any actual inputs first, 314 /// followed by an optional chain operand, then flag operands. Compute the 315 /// number of actual operands that will go into the machine instr. 316 static unsigned CountOperands(SDNode *Node); 317 318 /// EmitNode - Generate machine code for an node and needed dependencies. 319 /// VRBaseMap contains, for each already emitted node, the first virtual 320 /// register number for the results of the node. 321 /// 322 void EmitNode(SDNode *Node, unsigned InstNo, 323 DenseMap<SDOperand, unsigned> &VRBaseMap); 324 325 /// EmitNoop - Emit a noop instruction. 326 /// 327 void EmitNoop(); 328 329 void EmitCrossRCCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap); 330 331 /// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an 332 /// implicit physical register output. 333 void EmitCopyFromReg(SDNode *Node, unsigned ResNo, unsigned InstNo, 334 unsigned SrcReg, 335 DenseMap<SDOperand, unsigned> &VRBaseMap); 336 337 void CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, 338 const TargetInstrDescriptor &II, 339 DenseMap<SDOperand, unsigned> &VRBaseMap); 340 341 void EmitSchedule(); 342 343 void dumpSchedule() const; 344 345 /// Schedule - Order nodes according to selected style. 346 /// 347 virtual void Schedule() {} 348 349 private: 350 /// EmitSubregNode - Generate machine code for subreg nodes. 351 /// 352 void EmitSubregNode(SDNode *Node, 353 DenseMap<SDOperand, unsigned> &VRBaseMap); 354 355 void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum, 356 const TargetInstrDescriptor *II, 357 DenseMap<SDOperand, unsigned> &VRBaseMap); 358 }; 359 360 /// createBURRListDAGScheduler - This creates a bottom up register usage 361 /// reduction list scheduler. 362 ScheduleDAG* createBURRListDAGScheduler(SelectionDAGISel *IS, 363 SelectionDAG *DAG, 364 MachineBasicBlock *BB); 365 366 /// createTDRRListDAGScheduler - This creates a top down register usage 367 /// reduction list scheduler. 368 ScheduleDAG* createTDRRListDAGScheduler(SelectionDAGISel *IS, 369 SelectionDAG *DAG, 370 MachineBasicBlock *BB); 371 372 /// createTDListDAGScheduler - This creates a top-down list scheduler with 373 /// a hazard recognizer. 374 ScheduleDAG* createTDListDAGScheduler(SelectionDAGISel *IS, 375 SelectionDAG *DAG, 376 MachineBasicBlock *BB); 377 378 /// createDefaultScheduler - This creates an instruction scheduler appropriate 379 /// for the target. 380 ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS, 381 SelectionDAG *DAG, 382 MachineBasicBlock *BB); 383 384 class SUnitIterator : public forward_iterator<SUnit, ptrdiff_t> { 385 SUnit *Node; 386 unsigned Operand; 387 388 SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {} 389 public: 390 bool operator==(const SUnitIterator& x) const { 391 return Operand == x.Operand; 392 } 393 bool operator!=(const SUnitIterator& x) const { return !operator==(x); } 394 395 const SUnitIterator &operator=(const SUnitIterator &I) { 396 assert(I.Node == Node && "Cannot assign iterators to two different nodes!"); 397 Operand = I.Operand; 398 return *this; 399 } 400 401 pointer operator*() const { 402 return Node->Preds[Operand].Dep; 403 } 404 pointer operator->() const { return operator*(); } 405 406 SUnitIterator& operator++() { // Preincrement 407 ++Operand; 408 return *this; 409 } 410 SUnitIterator operator++(int) { // Postincrement 411 SUnitIterator tmp = *this; ++*this; return tmp; 412 } 413 414 static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); } 415 static SUnitIterator end (SUnit *N) { 416 return SUnitIterator(N, N->Preds.size()); 417 } 418 419 unsigned getOperand() const { return Operand; } 420 const SUnit *getNode() const { return Node; } 421 bool isCtrlDep() const { return Node->Preds[Operand].isCtrl; } 422 }; 423 424 template <> struct GraphTraits<SUnit*> { 425 typedef SUnit NodeType; 426 typedef SUnitIterator ChildIteratorType; 427 static inline NodeType *getEntryNode(SUnit *N) { return N; } 428 static inline ChildIteratorType child_begin(NodeType *N) { 429 return SUnitIterator::begin(N); 430 } 431 static inline ChildIteratorType child_end(NodeType *N) { 432 return SUnitIterator::end(N); 433 } 434 }; 435 436 template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> { 437 typedef std::vector<SUnit>::iterator nodes_iterator; 438 static nodes_iterator nodes_begin(ScheduleDAG *G) { 439 return G->SUnits.begin(); 440 } 441 static nodes_iterator nodes_end(ScheduleDAG *G) { 442 return G->SUnits.end(); 443 } 444 }; 445} 446 447#endif 448