ScheduleDAG.h revision 98adea11496400c8385b774b4d9f9acd4c99d254
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 instruction schedulers. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef LLVM_CODEGEN_SCHEDULEDAG_H 16#define LLVM_CODEGEN_SCHEDULEDAG_H 17 18#include "llvm/CodeGen/MachineBasicBlock.h" 19#include "llvm/ADT/DenseMap.h" 20#include "llvm/ADT/GraphTraits.h" 21#include "llvm/ADT/SmallVector.h" 22 23namespace llvm { 24 struct SUnit; 25 class MachineConstantPool; 26 class MachineFunction; 27 class MachineModuleInfo; 28 class MachineRegisterInfo; 29 class MachineInstr; 30 class TargetRegisterInfo; 31 class ScheduleDAG; 32 class SelectionDAG; 33 class SDNode; 34 class TargetInstrInfo; 35 class TargetInstrDesc; 36 class TargetLowering; 37 class TargetMachine; 38 class TargetRegisterClass; 39 template<class Graph> class GraphWriter; 40 41 /// SDep - Scheduling dependency. It keeps track of dependent nodes, 42 /// cost of the depdenency, etc. 43 struct SDep { 44 SUnit *Dep; // Dependent - either a predecessor or a successor. 45 unsigned Reg; // If non-zero, this dep is a physreg dependency. 46 int Cost; // Cost of the dependency. 47 bool isCtrl : 1; // True iff it's a control dependency. 48 bool isArtificial : 1; // True iff it's an artificial ctrl dep added 49 // during sched that may be safely deleted if 50 // necessary. 51 SDep(SUnit *d, unsigned r, int t, bool c, bool a) 52 : Dep(d), Reg(r), Cost(t), isCtrl(c), isArtificial(a) {} 53 }; 54 55 /// SUnit - Scheduling unit. This is a node in the scheduling DAG. 56 struct SUnit { 57 private: 58 SDNode *Node; // Representative node. 59 MachineInstr *Instr; // Alternatively, a MachineInstr. 60 public: 61 SUnit *OrigNode; // If not this, the node from which 62 // this node was cloned. 63 64 // Preds/Succs - The SUnits before/after us in the graph. The boolean value 65 // is true if the edge is a token chain edge, false if it is a value edge. 66 SmallVector<SDep, 4> Preds; // All sunit predecessors. 67 SmallVector<SDep, 4> Succs; // All sunit successors. 68 69 typedef SmallVector<SDep, 4>::iterator pred_iterator; 70 typedef SmallVector<SDep, 4>::iterator succ_iterator; 71 typedef SmallVector<SDep, 4>::const_iterator const_pred_iterator; 72 typedef SmallVector<SDep, 4>::const_iterator const_succ_iterator; 73 74 unsigned NodeNum; // Entry # of node in the node vector. 75 unsigned NodeQueueId; // Queue id of node. 76 unsigned short Latency; // Node latency. 77 short NumPreds; // # of non-control preds. 78 short NumSuccs; // # of non-control sucss. 79 short NumPredsLeft; // # of preds not scheduled. 80 short NumSuccsLeft; // # of succs not scheduled. 81 bool isTwoAddress : 1; // Is a two-address instruction. 82 bool isCommutable : 1; // Is a commutable instruction. 83 bool hasPhysRegDefs : 1; // Has physreg defs that are being used. 84 bool isPending : 1; // True once pending. 85 bool isAvailable : 1; // True once available. 86 bool isScheduled : 1; // True once scheduled. 87 unsigned CycleBound; // Upper/lower cycle to be scheduled at. 88 unsigned Cycle; // Once scheduled, the cycle of the op. 89 unsigned Depth; // Node depth; 90 unsigned Height; // Node height; 91 const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null. 92 const TargetRegisterClass *CopySrcRC; 93 94 /// SUnit - Construct an SUnit for pre-regalloc scheduling to represent 95 /// an SDNode and any nodes flagged to it. 96 SUnit(SDNode *node, unsigned nodenum) 97 : Node(node), Instr(0), OrigNode(0), NodeNum(nodenum), NodeQueueId(0), 98 Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0), 99 isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false), 100 isPending(false), isAvailable(false), isScheduled(false), 101 CycleBound(0), Cycle(~0u), Depth(0), Height(0), 102 CopyDstRC(NULL), CopySrcRC(NULL) {} 103 104 /// SUnit - Construct an SUnit for post-regalloc scheduling to represent 105 /// a MachineInstr. 106 SUnit(MachineInstr *instr, unsigned nodenum) 107 : Node(0), Instr(instr), OrigNode(0), NodeNum(nodenum), NodeQueueId(0), 108 Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0), 109 isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false), 110 isPending(false), isAvailable(false), isScheduled(false), 111 CycleBound(0), Cycle(~0u), Depth(0), Height(0), 112 CopyDstRC(NULL), CopySrcRC(NULL) {} 113 114 /// setNode - Assign the representative SDNode for this SUnit. 115 /// This may be used during pre-regalloc scheduling. 116 void setNode(SDNode *N) { 117 assert(!Instr && "Setting SDNode of SUnit with MachineInstr!"); 118 Node = N; 119 } 120 121 /// getNode - Return the representative SDNode for this SUnit. 122 /// This may be used during pre-regalloc scheduling. 123 SDNode *getNode() const { 124 assert(!Instr && "Reading SDNode of SUnit with MachineInstr!"); 125 return Node; 126 } 127 128 /// setInstr - Assign the instruction for the SUnit. 129 /// This may be used during post-regalloc scheduling. 130 void setInstr(MachineInstr *MI) { 131 assert(!Node && "Setting MachineInstr of SUnit with SDNode!"); 132 Instr = MI; 133 } 134 135 /// getInstr - Return the representative MachineInstr for this SUnit. 136 /// This may be used during post-regalloc scheduling. 137 MachineInstr *getInstr() const { 138 assert(!Node && "Reading MachineInstr of SUnit with SDNode!"); 139 return Instr; 140 } 141 142 /// addPred - This adds the specified node as a pred of the current node if 143 /// not already. This returns true if this is a new pred. 144 bool addPred(SUnit *N, bool isCtrl, bool isArtificial, 145 unsigned PhyReg = 0, int Cost = 1) { 146 for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i) 147 if (Preds[i].Dep == N && 148 Preds[i].isCtrl == isCtrl && Preds[i].isArtificial == isArtificial) 149 return false; 150 Preds.push_back(SDep(N, PhyReg, Cost, isCtrl, isArtificial)); 151 N->Succs.push_back(SDep(this, PhyReg, Cost, isCtrl, isArtificial)); 152 if (!isCtrl) { 153 ++NumPreds; 154 ++N->NumSuccs; 155 } 156 if (!N->isScheduled) 157 ++NumPredsLeft; 158 if (!isScheduled) 159 ++N->NumSuccsLeft; 160 return true; 161 } 162 163 bool removePred(SUnit *N, bool isCtrl, bool isArtificial) { 164 for (SmallVector<SDep, 4>::iterator I = Preds.begin(), E = Preds.end(); 165 I != E; ++I) 166 if (I->Dep == N && I->isCtrl == isCtrl && I->isArtificial == isArtificial) { 167 bool FoundSucc = false; 168 for (SmallVector<SDep, 4>::iterator II = N->Succs.begin(), 169 EE = N->Succs.end(); II != EE; ++II) 170 if (II->Dep == this && 171 II->isCtrl == isCtrl && II->isArtificial == isArtificial) { 172 FoundSucc = true; 173 N->Succs.erase(II); 174 break; 175 } 176 assert(FoundSucc && "Mismatching preds / succs lists!"); 177 Preds.erase(I); 178 if (!isCtrl) { 179 --NumPreds; 180 --N->NumSuccs; 181 } 182 if (!N->isScheduled) 183 --NumPredsLeft; 184 if (!isScheduled) 185 --N->NumSuccsLeft; 186 return true; 187 } 188 return false; 189 } 190 191 bool isPred(SUnit *N) { 192 for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i) 193 if (Preds[i].Dep == N) 194 return true; 195 return false; 196 } 197 198 bool isSucc(SUnit *N) { 199 for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i) 200 if (Succs[i].Dep == N) 201 return true; 202 return false; 203 } 204 205 void dump(const ScheduleDAG *G) const; 206 void dumpAll(const ScheduleDAG *G) const; 207 void print(raw_ostream &O, const ScheduleDAG *G) const; 208 }; 209 210 //===--------------------------------------------------------------------===// 211 /// SchedulingPriorityQueue - This interface is used to plug different 212 /// priorities computation algorithms into the list scheduler. It implements 213 /// the interface of a standard priority queue, where nodes are inserted in 214 /// arbitrary order and returned in priority order. The computation of the 215 /// priority and the representation of the queue are totally up to the 216 /// implementation to decide. 217 /// 218 class SchedulingPriorityQueue { 219 public: 220 virtual ~SchedulingPriorityQueue() {} 221 222 virtual void initNodes(std::vector<SUnit> &SUnits) = 0; 223 virtual void addNode(const SUnit *SU) = 0; 224 virtual void updateNode(const SUnit *SU) = 0; 225 virtual void releaseState() = 0; 226 227 virtual unsigned size() const = 0; 228 virtual bool empty() const = 0; 229 virtual void push(SUnit *U) = 0; 230 231 virtual void push_all(const std::vector<SUnit *> &Nodes) = 0; 232 virtual SUnit *pop() = 0; 233 234 virtual void remove(SUnit *SU) = 0; 235 236 /// ScheduledNode - As each node is scheduled, this method is invoked. This 237 /// allows the priority function to adjust the priority of related 238 /// unscheduled nodes, for example. 239 /// 240 virtual void ScheduledNode(SUnit *) {} 241 242 virtual void UnscheduledNode(SUnit *) {} 243 }; 244 245 class ScheduleDAG { 246 public: 247 SelectionDAG *DAG; // DAG of the current basic block 248 MachineBasicBlock *BB; // Current basic block 249 const TargetMachine &TM; // Target processor 250 const TargetInstrInfo *TII; // Target instruction information 251 const TargetRegisterInfo *TRI; // Target processor register info 252 TargetLowering *TLI; // Target lowering info 253 MachineFunction *MF; // Machine function 254 MachineRegisterInfo &MRI; // Virtual/real register map 255 MachineConstantPool *ConstPool; // Target constant pool 256 std::vector<SUnit*> Sequence; // The schedule. Null SUnit*'s 257 // represent noop instructions. 258 std::vector<SUnit> SUnits; // The scheduling units. 259 260 ScheduleDAG(SelectionDAG *dag, MachineBasicBlock *bb, 261 const TargetMachine &tm); 262 263 virtual ~ScheduleDAG(); 264 265 /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered 266 /// using 'dot'. 267 /// 268 void viewGraph(); 269 270 /// Run - perform scheduling. 271 /// 272 void Run(); 273 274 /// BuildSchedUnits - Build SUnits and set up their Preds and Succs 275 /// to form the scheduling dependency graph. 276 /// 277 virtual void BuildSchedUnits() = 0; 278 279 /// ComputeLatency - Compute node latency. 280 /// 281 virtual void ComputeLatency(SUnit *SU) { SU->Latency = 1; } 282 283 /// CalculateDepths, CalculateHeights - Calculate node depth / height. 284 /// 285 void CalculateDepths(); 286 void CalculateHeights(); 287 288 protected: 289 /// EmitNoop - Emit a noop instruction. 290 /// 291 void EmitNoop(); 292 293 public: 294 virtual MachineBasicBlock *EmitSchedule() = 0; 295 296 void dumpSchedule() const; 297 298 /// Schedule - Order nodes according to selected style, filling 299 /// in the Sequence member. 300 /// 301 virtual void Schedule() = 0; 302 303 virtual void dumpNode(const SUnit *SU) const = 0; 304 305 /// getGraphNodeLabel - Return a label for an SUnit node in a visualization 306 /// of the ScheduleDAG. 307 virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0; 308 309 /// addCustomGraphFeatures - Add custom features for a visualization of 310 /// the ScheduleDAG. 311 virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const {} 312 313#ifndef NDEBUG 314 /// VerifySchedule - Verify that all SUnits were scheduled and that 315 /// their state is consistent. 316 void VerifySchedule(bool isBottomUp); 317#endif 318 319 protected: 320 void AddMemOperand(MachineInstr *MI, const MachineMemOperand &MO); 321 322 void EmitCrossRCCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap); 323 324 private: 325 /// EmitLiveInCopy - Emit a copy for a live in physical register. If the 326 /// physical register has only a single copy use, then coalesced the copy 327 /// if possible. 328 void EmitLiveInCopy(MachineBasicBlock *MBB, 329 MachineBasicBlock::iterator &InsertPos, 330 unsigned VirtReg, unsigned PhysReg, 331 const TargetRegisterClass *RC, 332 DenseMap<MachineInstr*, unsigned> &CopyRegMap); 333 334 /// EmitLiveInCopies - If this is the first basic block in the function, 335 /// and if it has live ins that need to be copied into vregs, emit the 336 /// copies into the top of the block. 337 void EmitLiveInCopies(MachineBasicBlock *MBB); 338 }; 339 340 class SUnitIterator : public forward_iterator<SUnit, ptrdiff_t> { 341 SUnit *Node; 342 unsigned Operand; 343 344 SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {} 345 public: 346 bool operator==(const SUnitIterator& x) const { 347 return Operand == x.Operand; 348 } 349 bool operator!=(const SUnitIterator& x) const { return !operator==(x); } 350 351 const SUnitIterator &operator=(const SUnitIterator &I) { 352 assert(I.Node == Node && "Cannot assign iterators to two different nodes!"); 353 Operand = I.Operand; 354 return *this; 355 } 356 357 pointer operator*() const { 358 return Node->Preds[Operand].Dep; 359 } 360 pointer operator->() const { return operator*(); } 361 362 SUnitIterator& operator++() { // Preincrement 363 ++Operand; 364 return *this; 365 } 366 SUnitIterator operator++(int) { // Postincrement 367 SUnitIterator tmp = *this; ++*this; return tmp; 368 } 369 370 static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); } 371 static SUnitIterator end (SUnit *N) { 372 return SUnitIterator(N, (unsigned)N->Preds.size()); 373 } 374 375 unsigned getOperand() const { return Operand; } 376 const SUnit *getNode() const { return Node; } 377 bool isCtrlDep() const { return Node->Preds[Operand].isCtrl; } 378 bool isArtificialDep() const { return Node->Preds[Operand].isArtificial; } 379 }; 380 381 template <> struct GraphTraits<SUnit*> { 382 typedef SUnit NodeType; 383 typedef SUnitIterator ChildIteratorType; 384 static inline NodeType *getEntryNode(SUnit *N) { return N; } 385 static inline ChildIteratorType child_begin(NodeType *N) { 386 return SUnitIterator::begin(N); 387 } 388 static inline ChildIteratorType child_end(NodeType *N) { 389 return SUnitIterator::end(N); 390 } 391 }; 392 393 template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> { 394 typedef std::vector<SUnit>::iterator nodes_iterator; 395 static nodes_iterator nodes_begin(ScheduleDAG *G) { 396 return G->SUnits.begin(); 397 } 398 static nodes_iterator nodes_end(ScheduleDAG *G) { 399 return G->SUnits.end(); 400 } 401 }; 402} 403 404#endif 405