ScheduleDAG.h revision 208599
1193323Sed//===------- llvm/CodeGen/ScheduleDAG.h - Common Base Class------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements the ScheduleDAG class, which is used as the common 11193323Sed// base class for instruction schedulers. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#ifndef LLVM_CODEGEN_SCHEDULEDAG_H 16193323Sed#define LLVM_CODEGEN_SCHEDULEDAG_H 17193323Sed 18193323Sed#include "llvm/CodeGen/MachineBasicBlock.h" 19208599Srdivacky#include "llvm/Target/TargetMachine.h" 20193323Sed#include "llvm/ADT/DenseMap.h" 21193323Sed#include "llvm/ADT/BitVector.h" 22193323Sed#include "llvm/ADT/GraphTraits.h" 23193323Sed#include "llvm/ADT/SmallVector.h" 24193323Sed#include "llvm/ADT/PointerIntPair.h" 25193323Sed 26193323Sednamespace llvm { 27198090Srdivacky class AliasAnalysis; 28193323Sed class SUnit; 29193323Sed class MachineConstantPool; 30193323Sed class MachineFunction; 31193323Sed class MachineRegisterInfo; 32193323Sed class MachineInstr; 33193323Sed class TargetRegisterInfo; 34193323Sed class ScheduleDAG; 35193323Sed class SDNode; 36193323Sed class TargetInstrInfo; 37193323Sed class TargetInstrDesc; 38193323Sed class TargetMachine; 39193323Sed class TargetRegisterClass; 40193323Sed template<class Graph> class GraphWriter; 41193323Sed 42193323Sed /// SDep - Scheduling dependency. This represents one direction of an 43193323Sed /// edge in the scheduling DAG. 44193323Sed class SDep { 45193323Sed public: 46193323Sed /// Kind - These are the different kinds of scheduling dependencies. 47193323Sed enum Kind { 48193323Sed Data, ///< Regular data dependence (aka true-dependence). 49193323Sed Anti, ///< A register anti-dependedence (aka WAR). 50193323Sed Output, ///< A register output-dependence (aka WAW). 51193323Sed Order ///< Any other ordering dependency. 52193323Sed }; 53193323Sed 54193323Sed private: 55193323Sed /// Dep - A pointer to the depending/depended-on SUnit, and an enum 56193323Sed /// indicating the kind of the dependency. 57193323Sed PointerIntPair<SUnit *, 2, Kind> Dep; 58193323Sed 59193323Sed /// Contents - A union discriminated by the dependence kind. 60193323Sed union { 61193323Sed /// Reg - For Data, Anti, and Output dependencies, the associated 62193323Sed /// register. For Data dependencies that don't currently have a register 63193323Sed /// assigned, this is set to zero. 64193323Sed unsigned Reg; 65193323Sed 66193323Sed /// Order - Additional information about Order dependencies. 67193323Sed struct { 68193323Sed /// isNormalMemory - True if both sides of the dependence 69193323Sed /// access memory in non-volatile and fully modeled ways. 70193323Sed bool isNormalMemory : 1; 71193323Sed 72193323Sed /// isMustAlias - True if both sides of the dependence are known to 73193323Sed /// access the same memory. 74193323Sed bool isMustAlias : 1; 75193323Sed 76193323Sed /// isArtificial - True if this is an artificial dependency, meaning 77193323Sed /// it is not necessary for program correctness, and may be safely 78193323Sed /// deleted if necessary. 79193323Sed bool isArtificial : 1; 80193323Sed } Order; 81193323Sed } Contents; 82193323Sed 83193323Sed /// Latency - The time associated with this edge. Often this is just 84193323Sed /// the value of the Latency field of the predecessor, however advanced 85193323Sed /// models may provide additional information about specific edges. 86193323Sed unsigned Latency; 87193323Sed 88193323Sed public: 89193323Sed /// SDep - Construct a null SDep. This is only for use by container 90193323Sed /// classes which require default constructors. SUnits may not 91193323Sed /// have null SDep edges. 92193323Sed SDep() : Dep(0, Data) {} 93193323Sed 94193323Sed /// SDep - Construct an SDep with the specified values. 95193323Sed SDep(SUnit *S, Kind kind, unsigned latency = 1, unsigned Reg = 0, 96193323Sed bool isNormalMemory = false, bool isMustAlias = false, 97193323Sed bool isArtificial = false) 98193323Sed : Dep(S, kind), Contents(), Latency(latency) { 99193323Sed switch (kind) { 100193323Sed case Anti: 101193323Sed case Output: 102193323Sed assert(Reg != 0 && 103193323Sed "SDep::Anti and SDep::Output must use a non-zero Reg!"); 104193323Sed // fall through 105193323Sed case Data: 106193323Sed assert(!isMustAlias && "isMustAlias only applies with SDep::Order!"); 107193323Sed assert(!isArtificial && "isArtificial only applies with SDep::Order!"); 108193323Sed Contents.Reg = Reg; 109193323Sed break; 110193323Sed case Order: 111193323Sed assert(Reg == 0 && "Reg given for non-register dependence!"); 112193323Sed Contents.Order.isNormalMemory = isNormalMemory; 113193323Sed Contents.Order.isMustAlias = isMustAlias; 114193323Sed Contents.Order.isArtificial = isArtificial; 115193323Sed break; 116193323Sed } 117193323Sed } 118193323Sed 119193323Sed bool operator==(const SDep &Other) const { 120193323Sed if (Dep != Other.Dep || Latency != Other.Latency) return false; 121193323Sed switch (Dep.getInt()) { 122193323Sed case Data: 123193323Sed case Anti: 124193323Sed case Output: 125193323Sed return Contents.Reg == Other.Contents.Reg; 126193323Sed case Order: 127193323Sed return Contents.Order.isNormalMemory == 128193323Sed Other.Contents.Order.isNormalMemory && 129193323Sed Contents.Order.isMustAlias == Other.Contents.Order.isMustAlias && 130193323Sed Contents.Order.isArtificial == Other.Contents.Order.isArtificial; 131193323Sed } 132193323Sed assert(0 && "Invalid dependency kind!"); 133193323Sed return false; 134193323Sed } 135193323Sed 136193323Sed bool operator!=(const SDep &Other) const { 137193323Sed return !operator==(Other); 138193323Sed } 139193323Sed 140193323Sed /// getLatency - Return the latency value for this edge, which roughly 141193323Sed /// means the minimum number of cycles that must elapse between the 142193323Sed /// predecessor and the successor, given that they have this edge 143193323Sed /// between them. 144193323Sed unsigned getLatency() const { 145193323Sed return Latency; 146193323Sed } 147193323Sed 148198090Srdivacky /// setLatency - Set the latency for this edge. 149198090Srdivacky void setLatency(unsigned Lat) { 150198090Srdivacky Latency = Lat; 151198090Srdivacky } 152198090Srdivacky 153193323Sed //// getSUnit - Return the SUnit to which this edge points. 154193323Sed SUnit *getSUnit() const { 155193323Sed return Dep.getPointer(); 156193323Sed } 157193323Sed 158193323Sed //// setSUnit - Assign the SUnit to which this edge points. 159193323Sed void setSUnit(SUnit *SU) { 160193323Sed Dep.setPointer(SU); 161193323Sed } 162193323Sed 163193323Sed /// getKind - Return an enum value representing the kind of the dependence. 164193323Sed Kind getKind() const { 165193323Sed return Dep.getInt(); 166193323Sed } 167193323Sed 168193323Sed /// isCtrl - Shorthand for getKind() != SDep::Data. 169193323Sed bool isCtrl() const { 170193323Sed return getKind() != Data; 171193323Sed } 172193323Sed 173193323Sed /// isNormalMemory - Test if this is an Order dependence between two 174193323Sed /// memory accesses where both sides of the dependence access memory 175193323Sed /// in non-volatile and fully modeled ways. 176193323Sed bool isNormalMemory() const { 177193323Sed return getKind() == Order && Contents.Order.isNormalMemory; 178193323Sed } 179193323Sed 180193323Sed /// isMustAlias - Test if this is an Order dependence that is marked 181193323Sed /// as "must alias", meaning that the SUnits at either end of the edge 182193323Sed /// have a memory dependence on a known memory location. 183193323Sed bool isMustAlias() const { 184193323Sed return getKind() == Order && Contents.Order.isMustAlias; 185193323Sed } 186193323Sed 187193323Sed /// isArtificial - Test if this is an Order dependence that is marked 188193323Sed /// as "artificial", meaning it isn't necessary for correctness. 189193323Sed bool isArtificial() const { 190193323Sed return getKind() == Order && Contents.Order.isArtificial; 191193323Sed } 192193323Sed 193193323Sed /// isAssignedRegDep - Test if this is a Data dependence that is 194193323Sed /// associated with a register. 195193323Sed bool isAssignedRegDep() const { 196193323Sed return getKind() == Data && Contents.Reg != 0; 197193323Sed } 198193323Sed 199193323Sed /// getReg - Return the register associated with this edge. This is 200193323Sed /// only valid on Data, Anti, and Output edges. On Data edges, this 201193323Sed /// value may be zero, meaning there is no associated register. 202193323Sed unsigned getReg() const { 203193323Sed assert((getKind() == Data || getKind() == Anti || getKind() == Output) && 204193323Sed "getReg called on non-register dependence edge!"); 205193323Sed return Contents.Reg; 206193323Sed } 207193323Sed 208193323Sed /// setReg - Assign the associated register for this edge. This is 209193323Sed /// only valid on Data, Anti, and Output edges. On Anti and Output 210193323Sed /// edges, this value must not be zero. On Data edges, the value may 211193323Sed /// be zero, which would mean that no specific register is associated 212193323Sed /// with this edge. 213193323Sed void setReg(unsigned Reg) { 214193323Sed assert((getKind() == Data || getKind() == Anti || getKind() == Output) && 215193323Sed "setReg called on non-register dependence edge!"); 216193323Sed assert((getKind() != Anti || Reg != 0) && 217193323Sed "SDep::Anti edge cannot use the zero register!"); 218193323Sed assert((getKind() != Output || Reg != 0) && 219193323Sed "SDep::Output edge cannot use the zero register!"); 220193323Sed Contents.Reg = Reg; 221193323Sed } 222193323Sed }; 223193323Sed 224193323Sed /// SUnit - Scheduling unit. This is a node in the scheduling DAG. 225193323Sed class SUnit { 226193323Sed private: 227193323Sed SDNode *Node; // Representative node. 228193323Sed MachineInstr *Instr; // Alternatively, a MachineInstr. 229193323Sed public: 230193323Sed SUnit *OrigNode; // If not this, the node from which 231193323Sed // this node was cloned. 232193323Sed 233193323Sed // Preds/Succs - The SUnits before/after us in the graph. The boolean value 234193323Sed // is true if the edge is a token chain edge, false if it is a value edge. 235193323Sed SmallVector<SDep, 4> Preds; // All sunit predecessors. 236193323Sed SmallVector<SDep, 4> Succs; // All sunit successors. 237193323Sed 238193323Sed typedef SmallVector<SDep, 4>::iterator pred_iterator; 239193323Sed typedef SmallVector<SDep, 4>::iterator succ_iterator; 240193323Sed typedef SmallVector<SDep, 4>::const_iterator const_pred_iterator; 241193323Sed typedef SmallVector<SDep, 4>::const_iterator const_succ_iterator; 242208599Srdivacky 243193323Sed unsigned NodeNum; // Entry # of node in the node vector. 244193323Sed unsigned NodeQueueId; // Queue id of node. 245193323Sed unsigned short Latency; // Node latency. 246198090Srdivacky unsigned NumPreds; // # of SDep::Data preds. 247198090Srdivacky unsigned NumSuccs; // # of SDep::Data sucss. 248198090Srdivacky unsigned NumPredsLeft; // # of preds not scheduled. 249198090Srdivacky unsigned NumSuccsLeft; // # of succs not scheduled. 250193323Sed bool isTwoAddress : 1; // Is a two-address instruction. 251193323Sed bool isCommutable : 1; // Is a commutable instruction. 252193323Sed bool hasPhysRegDefs : 1; // Has physreg defs that are being used. 253193323Sed bool hasPhysRegClobbers : 1; // Has any physreg defs, used or not. 254193323Sed bool isPending : 1; // True once pending. 255193323Sed bool isAvailable : 1; // True once available. 256193323Sed bool isScheduled : 1; // True once scheduled. 257193323Sed bool isScheduleHigh : 1; // True if preferable to schedule high. 258193323Sed bool isCloned : 1; // True if this node has been cloned. 259208599Srdivacky Sched::Preference SchedulingPref; // Scheduling preference. 260208599Srdivacky 261208599Srdivacky SmallVector<MachineInstr*, 4> DbgInstrList; // dbg_values referencing this. 262193323Sed private: 263193323Sed bool isDepthCurrent : 1; // True if Depth is current. 264193323Sed bool isHeightCurrent : 1; // True if Height is current. 265193323Sed unsigned Depth; // Node depth. 266193323Sed unsigned Height; // Node height. 267193323Sed public: 268193323Sed const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null. 269193323Sed const TargetRegisterClass *CopySrcRC; 270193323Sed 271193323Sed /// SUnit - Construct an SUnit for pre-regalloc scheduling to represent 272193323Sed /// an SDNode and any nodes flagged to it. 273193323Sed SUnit(SDNode *node, unsigned nodenum) 274208599Srdivacky : Node(node), Instr(0), OrigNode(0), NodeNum(nodenum), 275205218Srdivacky NodeQueueId(0), Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), 276205218Srdivacky NumSuccsLeft(0), isTwoAddress(false), isCommutable(false), 277205218Srdivacky hasPhysRegDefs(false), hasPhysRegClobbers(false), 278193323Sed isPending(false), isAvailable(false), isScheduled(false), 279193323Sed isScheduleHigh(false), isCloned(false), 280208599Srdivacky SchedulingPref(Sched::None), 281193323Sed isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), 282193323Sed CopyDstRC(NULL), CopySrcRC(NULL) {} 283193323Sed 284193323Sed /// SUnit - Construct an SUnit for post-regalloc scheduling to represent 285193323Sed /// a MachineInstr. 286193323Sed SUnit(MachineInstr *instr, unsigned nodenum) 287208599Srdivacky : Node(0), Instr(instr), OrigNode(0), NodeNum(nodenum), 288205218Srdivacky NodeQueueId(0), Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), 289205218Srdivacky NumSuccsLeft(0), isTwoAddress(false), isCommutable(false), 290205218Srdivacky hasPhysRegDefs(false), hasPhysRegClobbers(false), 291193323Sed isPending(false), isAvailable(false), isScheduled(false), 292193323Sed isScheduleHigh(false), isCloned(false), 293208599Srdivacky SchedulingPref(Sched::None), 294193323Sed isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), 295193323Sed CopyDstRC(NULL), CopySrcRC(NULL) {} 296193323Sed 297193323Sed /// SUnit - Construct a placeholder SUnit. 298193323Sed SUnit() 299208599Srdivacky : Node(0), Instr(0), OrigNode(0), NodeNum(~0u), 300205218Srdivacky NodeQueueId(0), Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), 301205218Srdivacky NumSuccsLeft(0), isTwoAddress(false), isCommutable(false), 302205218Srdivacky hasPhysRegDefs(false), hasPhysRegClobbers(false), 303193323Sed isPending(false), isAvailable(false), isScheduled(false), 304193323Sed isScheduleHigh(false), isCloned(false), 305208599Srdivacky SchedulingPref(Sched::None), 306193323Sed isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), 307193323Sed CopyDstRC(NULL), CopySrcRC(NULL) {} 308193323Sed 309193323Sed /// setNode - Assign the representative SDNode for this SUnit. 310193323Sed /// This may be used during pre-regalloc scheduling. 311193323Sed void setNode(SDNode *N) { 312193323Sed assert(!Instr && "Setting SDNode of SUnit with MachineInstr!"); 313193323Sed Node = N; 314193323Sed } 315193323Sed 316193323Sed /// getNode - Return the representative SDNode for this SUnit. 317193323Sed /// This may be used during pre-regalloc scheduling. 318193323Sed SDNode *getNode() const { 319193323Sed assert(!Instr && "Reading SDNode of SUnit with MachineInstr!"); 320193323Sed return Node; 321193323Sed } 322193323Sed 323193323Sed /// setInstr - Assign the instruction for the SUnit. 324193323Sed /// This may be used during post-regalloc scheduling. 325193323Sed void setInstr(MachineInstr *MI) { 326193323Sed assert(!Node && "Setting MachineInstr of SUnit with SDNode!"); 327193323Sed Instr = MI; 328193323Sed } 329193323Sed 330193323Sed /// getInstr - Return the representative MachineInstr for this SUnit. 331193323Sed /// This may be used during post-regalloc scheduling. 332193323Sed MachineInstr *getInstr() const { 333193323Sed assert(!Node && "Reading MachineInstr of SUnit with SDNode!"); 334193323Sed return Instr; 335193323Sed } 336193323Sed 337193323Sed /// addPred - This adds the specified edge as a pred of the current node if 338193323Sed /// not already. It also adds the current node as a successor of the 339193323Sed /// specified node. 340193323Sed void addPred(const SDep &D); 341193323Sed 342193323Sed /// removePred - This removes the specified edge as a pred of the current 343193323Sed /// node if it exists. It also removes the current node as a successor of 344193323Sed /// the specified node. 345193323Sed void removePred(const SDep &D); 346193323Sed 347193323Sed /// getDepth - Return the depth of this node, which is the length of the 348199989Srdivacky /// maximum path up to any node with has no predecessors. 349199989Srdivacky unsigned getDepth() const { 350198892Srdivacky if (!isDepthCurrent) 351199989Srdivacky const_cast<SUnit *>(this)->ComputeDepth(); 352193323Sed return Depth; 353193323Sed } 354193323Sed 355193323Sed /// getHeight - Return the height of this node, which is the length of the 356199989Srdivacky /// maximum path down to any node with has no successors. 357199989Srdivacky unsigned getHeight() const { 358198892Srdivacky if (!isHeightCurrent) 359199989Srdivacky const_cast<SUnit *>(this)->ComputeHeight(); 360193323Sed return Height; 361193323Sed } 362193323Sed 363198892Srdivacky /// setDepthToAtLeast - If NewDepth is greater than this node's 364198892Srdivacky /// depth value, set it to be the new depth value. This also 365199989Srdivacky /// recursively marks successor nodes dirty. 366199989Srdivacky void setDepthToAtLeast(unsigned NewDepth); 367193323Sed 368198892Srdivacky /// setDepthToAtLeast - If NewDepth is greater than this node's 369198892Srdivacky /// depth value, set it to be the new height value. This also 370199989Srdivacky /// recursively marks predecessor nodes dirty. 371199989Srdivacky void setHeightToAtLeast(unsigned NewHeight); 372193323Sed 373193323Sed /// setDepthDirty - Set a flag in this node to indicate that its 374193323Sed /// stored Depth value will require recomputation the next time 375193323Sed /// getDepth() is called. 376193323Sed void setDepthDirty(); 377193323Sed 378193323Sed /// setHeightDirty - Set a flag in this node to indicate that its 379193323Sed /// stored Height value will require recomputation the next time 380193323Sed /// getHeight() is called. 381193323Sed void setHeightDirty(); 382193323Sed 383193323Sed /// isPred - Test if node N is a predecessor of this node. 384193323Sed bool isPred(SUnit *N) { 385193323Sed for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i) 386193323Sed if (Preds[i].getSUnit() == N) 387193323Sed return true; 388193323Sed return false; 389193323Sed } 390193323Sed 391193323Sed /// isSucc - Test if node N is a successor of this node. 392193323Sed bool isSucc(SUnit *N) { 393193323Sed for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i) 394193323Sed if (Succs[i].getSUnit() == N) 395193323Sed return true; 396193323Sed return false; 397193323Sed } 398208599Srdivacky 399193323Sed void dump(const ScheduleDAG *G) const; 400193323Sed void dumpAll(const ScheduleDAG *G) const; 401193323Sed void print(raw_ostream &O, const ScheduleDAG *G) const; 402193323Sed 403193323Sed private: 404199989Srdivacky void ComputeDepth(); 405199989Srdivacky void ComputeHeight(); 406193323Sed }; 407193323Sed 408193323Sed //===--------------------------------------------------------------------===// 409193323Sed /// SchedulingPriorityQueue - This interface is used to plug different 410193323Sed /// priorities computation algorithms into the list scheduler. It implements 411193323Sed /// the interface of a standard priority queue, where nodes are inserted in 412193323Sed /// arbitrary order and returned in priority order. The computation of the 413193323Sed /// priority and the representation of the queue are totally up to the 414193323Sed /// implementation to decide. 415193323Sed /// 416193323Sed class SchedulingPriorityQueue { 417208599Srdivacky unsigned CurCycle; 418193323Sed public: 419208599Srdivacky SchedulingPriorityQueue() : CurCycle(0) {} 420193323Sed virtual ~SchedulingPriorityQueue() {} 421193323Sed 422193323Sed virtual void initNodes(std::vector<SUnit> &SUnits) = 0; 423193323Sed virtual void addNode(const SUnit *SU) = 0; 424193323Sed virtual void updateNode(const SUnit *SU) = 0; 425193323Sed virtual void releaseState() = 0; 426193323Sed 427193323Sed virtual bool empty() const = 0; 428193323Sed virtual void push(SUnit *U) = 0; 429193323Sed 430208599Srdivacky void push_all(const std::vector<SUnit *> &Nodes) { 431208599Srdivacky for (std::vector<SUnit *>::const_iterator I = Nodes.begin(), 432208599Srdivacky E = Nodes.end(); I != E; ++I) 433208599Srdivacky push(*I); 434208599Srdivacky } 435208599Srdivacky 436193323Sed virtual SUnit *pop() = 0; 437193323Sed 438193323Sed virtual void remove(SUnit *SU) = 0; 439193323Sed 440193323Sed /// ScheduledNode - As each node is scheduled, this method is invoked. This 441193323Sed /// allows the priority function to adjust the priority of related 442193323Sed /// unscheduled nodes, for example. 443193323Sed /// 444193323Sed virtual void ScheduledNode(SUnit *) {} 445193323Sed 446193323Sed virtual void UnscheduledNode(SUnit *) {} 447208599Srdivacky 448208599Srdivacky void setCurCycle(unsigned Cycle) { 449208599Srdivacky CurCycle = Cycle; 450208599Srdivacky } 451208599Srdivacky 452208599Srdivacky unsigned getCurCycle() const { 453208599Srdivacky return CurCycle; 454208599Srdivacky } 455193323Sed }; 456193323Sed 457193323Sed class ScheduleDAG { 458193323Sed public: 459198090Srdivacky MachineBasicBlock *BB; // The block in which to insert instructions 460198090Srdivacky MachineBasicBlock::iterator InsertPos;// The position to insert instructions 461193323Sed const TargetMachine &TM; // Target processor 462193323Sed const TargetInstrInfo *TII; // Target instruction information 463193323Sed const TargetRegisterInfo *TRI; // Target processor register info 464193323Sed MachineFunction &MF; // Machine function 465193323Sed MachineRegisterInfo &MRI; // Virtual/real register map 466193323Sed std::vector<SUnit*> Sequence; // The schedule. Null SUnit*'s 467193323Sed // represent noop instructions. 468193323Sed std::vector<SUnit> SUnits; // The scheduling units. 469193323Sed SUnit EntrySU; // Special node for the region entry. 470193323Sed SUnit ExitSU; // Special node for the region exit. 471193323Sed 472193323Sed explicit ScheduleDAG(MachineFunction &mf); 473193323Sed 474193323Sed virtual ~ScheduleDAG(); 475193323Sed 476193323Sed /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered 477193323Sed /// using 'dot'. 478193323Sed /// 479193323Sed void viewGraph(); 480193323Sed 481193323Sed /// EmitSchedule - Insert MachineInstrs into the MachineBasicBlock 482193323Sed /// according to the order specified in Sequence. 483193323Sed /// 484207618Srdivacky virtual MachineBasicBlock *EmitSchedule() = 0; 485193323Sed 486193323Sed void dumpSchedule() const; 487193323Sed 488193323Sed virtual void dumpNode(const SUnit *SU) const = 0; 489193323Sed 490193323Sed /// getGraphNodeLabel - Return a label for an SUnit node in a visualization 491193323Sed /// of the ScheduleDAG. 492193323Sed virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0; 493193323Sed 494193323Sed /// addCustomGraphFeatures - Add custom features for a visualization of 495193323Sed /// the ScheduleDAG. 496193323Sed virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {} 497193323Sed 498193323Sed#ifndef NDEBUG 499193323Sed /// VerifySchedule - Verify that all SUnits were scheduled and that 500193323Sed /// their state is consistent. 501193323Sed void VerifySchedule(bool isBottomUp); 502193323Sed#endif 503193323Sed 504193323Sed protected: 505193323Sed /// Run - perform scheduling. 506193323Sed /// 507193323Sed void Run(MachineBasicBlock *bb, MachineBasicBlock::iterator insertPos); 508193323Sed 509193323Sed /// BuildSchedGraph - Build SUnits and set up their Preds and Succs 510193323Sed /// to form the scheduling dependency graph. 511193323Sed /// 512198090Srdivacky virtual void BuildSchedGraph(AliasAnalysis *AA) = 0; 513193323Sed 514193323Sed /// ComputeLatency - Compute node latency. 515193323Sed /// 516193323Sed virtual void ComputeLatency(SUnit *SU) = 0; 517193323Sed 518198090Srdivacky /// ComputeOperandLatency - Override dependence edge latency using 519198090Srdivacky /// operand use/def information 520198090Srdivacky /// 521198113Srdivacky virtual void ComputeOperandLatency(SUnit *, SUnit *, 522198113Srdivacky SDep&) const { } 523198090Srdivacky 524193323Sed /// Schedule - Order nodes according to selected style, filling 525193323Sed /// in the Sequence member. 526193323Sed /// 527193323Sed virtual void Schedule() = 0; 528193323Sed 529198090Srdivacky /// ForceUnitLatencies - Return true if all scheduling edges should be given 530198090Srdivacky /// a latency value of one. The default is to return false; schedulers may 531193323Sed /// override this as needed. 532193323Sed virtual bool ForceUnitLatencies() const { return false; } 533193323Sed 534193323Sed /// EmitNoop - Emit a noop instruction. 535193323Sed /// 536193323Sed void EmitNoop(); 537193323Sed 538193323Sed void EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap); 539193323Sed }; 540193323Sed 541198090Srdivacky class SUnitIterator : public std::iterator<std::forward_iterator_tag, 542198090Srdivacky SUnit, ptrdiff_t> { 543193323Sed SUnit *Node; 544193323Sed unsigned Operand; 545193323Sed 546193323Sed SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {} 547193323Sed public: 548193323Sed bool operator==(const SUnitIterator& x) const { 549193323Sed return Operand == x.Operand; 550193323Sed } 551193323Sed bool operator!=(const SUnitIterator& x) const { return !operator==(x); } 552193323Sed 553193323Sed const SUnitIterator &operator=(const SUnitIterator &I) { 554198090Srdivacky assert(I.Node==Node && "Cannot assign iterators to two different nodes!"); 555193323Sed Operand = I.Operand; 556193323Sed return *this; 557193323Sed } 558193323Sed 559193323Sed pointer operator*() const { 560193323Sed return Node->Preds[Operand].getSUnit(); 561193323Sed } 562193323Sed pointer operator->() const { return operator*(); } 563193323Sed 564193323Sed SUnitIterator& operator++() { // Preincrement 565193323Sed ++Operand; 566193323Sed return *this; 567193323Sed } 568193323Sed SUnitIterator operator++(int) { // Postincrement 569193323Sed SUnitIterator tmp = *this; ++*this; return tmp; 570193323Sed } 571193323Sed 572193323Sed static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); } 573193323Sed static SUnitIterator end (SUnit *N) { 574193323Sed return SUnitIterator(N, (unsigned)N->Preds.size()); 575193323Sed } 576193323Sed 577193323Sed unsigned getOperand() const { return Operand; } 578193323Sed const SUnit *getNode() const { return Node; } 579193323Sed /// isCtrlDep - Test if this is not an SDep::Data dependence. 580193323Sed bool isCtrlDep() const { 581193323Sed return getSDep().isCtrl(); 582193323Sed } 583193323Sed bool isArtificialDep() const { 584193323Sed return getSDep().isArtificial(); 585193323Sed } 586193323Sed const SDep &getSDep() const { 587193323Sed return Node->Preds[Operand]; 588193323Sed } 589193323Sed }; 590193323Sed 591193323Sed template <> struct GraphTraits<SUnit*> { 592193323Sed typedef SUnit NodeType; 593193323Sed typedef SUnitIterator ChildIteratorType; 594193323Sed static inline NodeType *getEntryNode(SUnit *N) { return N; } 595193323Sed static inline ChildIteratorType child_begin(NodeType *N) { 596193323Sed return SUnitIterator::begin(N); 597193323Sed } 598193323Sed static inline ChildIteratorType child_end(NodeType *N) { 599193323Sed return SUnitIterator::end(N); 600193323Sed } 601193323Sed }; 602193323Sed 603193323Sed template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> { 604193323Sed typedef std::vector<SUnit>::iterator nodes_iterator; 605193323Sed static nodes_iterator nodes_begin(ScheduleDAG *G) { 606193323Sed return G->SUnits.begin(); 607193323Sed } 608193323Sed static nodes_iterator nodes_end(ScheduleDAG *G) { 609193323Sed return G->SUnits.end(); 610193323Sed } 611193323Sed }; 612193323Sed 613193323Sed /// ScheduleDAGTopologicalSort is a class that computes a topological 614193323Sed /// ordering for SUnits and provides methods for dynamically updating 615193323Sed /// the ordering as new edges are added. 616193323Sed /// 617193323Sed /// This allows a very fast implementation of IsReachable, for example. 618193323Sed /// 619193323Sed class ScheduleDAGTopologicalSort { 620193323Sed /// SUnits - A reference to the ScheduleDAG's SUnits. 621193323Sed std::vector<SUnit> &SUnits; 622193323Sed 623193323Sed /// Index2Node - Maps topological index to the node number. 624193323Sed std::vector<int> Index2Node; 625193323Sed /// Node2Index - Maps the node number to its topological index. 626193323Sed std::vector<int> Node2Index; 627193323Sed /// Visited - a set of nodes visited during a DFS traversal. 628193323Sed BitVector Visited; 629193323Sed 630193323Sed /// DFS - make a DFS traversal and mark all nodes affected by the 631193323Sed /// edge insertion. These nodes will later get new topological indexes 632193323Sed /// by means of the Shift method. 633193323Sed void DFS(const SUnit *SU, int UpperBound, bool& HasLoop); 634193323Sed 635193323Sed /// Shift - reassign topological indexes for the nodes in the DAG 636193323Sed /// to preserve the topological ordering. 637193323Sed void Shift(BitVector& Visited, int LowerBound, int UpperBound); 638193323Sed 639193323Sed /// Allocate - assign the topological index to the node n. 640193323Sed void Allocate(int n, int index); 641193323Sed 642193323Sed public: 643193323Sed explicit ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits); 644193323Sed 645193323Sed /// InitDAGTopologicalSorting - create the initial topological 646193323Sed /// ordering from the DAG to be scheduled. 647193323Sed void InitDAGTopologicalSorting(); 648193323Sed 649193323Sed /// IsReachable - Checks if SU is reachable from TargetSU. 650193323Sed bool IsReachable(const SUnit *SU, const SUnit *TargetSU); 651193323Sed 652193323Sed /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU 653193323Sed /// will create a cycle. 654193323Sed bool WillCreateCycle(SUnit *SU, SUnit *TargetSU); 655193323Sed 656193323Sed /// AddPred - Updates the topological ordering to accomodate an edge 657193323Sed /// to be added from SUnit X to SUnit Y. 658193323Sed void AddPred(SUnit *Y, SUnit *X); 659193323Sed 660193323Sed /// RemovePred - Updates the topological ordering to accomodate an 661193323Sed /// an edge to be removed from the specified node N from the predecessors 662193323Sed /// of the current node M. 663193323Sed void RemovePred(SUnit *M, SUnit *N); 664193323Sed 665193323Sed typedef std::vector<int>::iterator iterator; 666193323Sed typedef std::vector<int>::const_iterator const_iterator; 667193323Sed iterator begin() { return Index2Node.begin(); } 668193323Sed const_iterator begin() const { return Index2Node.begin(); } 669193323Sed iterator end() { return Index2Node.end(); } 670193323Sed const_iterator end() const { return Index2Node.end(); } 671193323Sed 672193323Sed typedef std::vector<int>::reverse_iterator reverse_iterator; 673193323Sed typedef std::vector<int>::const_reverse_iterator const_reverse_iterator; 674193323Sed reverse_iterator rbegin() { return Index2Node.rbegin(); } 675193323Sed const_reverse_iterator rbegin() const { return Index2Node.rbegin(); } 676193323Sed reverse_iterator rend() { return Index2Node.rend(); } 677193323Sed const_reverse_iterator rend() const { return Index2Node.rend(); } 678193323Sed }; 679193323Sed} 680193323Sed 681193323Sed#endif 682