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 11234353Sdim// base class for instruction schedulers. This encapsulates the scheduling DAG, 12234353Sdim// which is shared between SelectionDAG and MachineInstr scheduling. 13193323Sed// 14193323Sed//===----------------------------------------------------------------------===// 15193323Sed 16193323Sed#ifndef LLVM_CODEGEN_SCHEDULEDAG_H 17193323Sed#define LLVM_CODEGEN_SCHEDULEDAG_H 18193323Sed 19193323Sed#include "llvm/ADT/BitVector.h" 20193323Sed#include "llvm/ADT/GraphTraits.h" 21249423Sdim#include "llvm/ADT/PointerIntPair.h" 22193323Sed#include "llvm/ADT/SmallVector.h" 23249423Sdim#include "llvm/CodeGen/MachineInstr.h" 24249423Sdim#include "llvm/Target/TargetLowering.h" 25193323Sed 26193323Sednamespace llvm { 27198090Srdivacky class AliasAnalysis; 28193323Sed class SUnit; 29193323Sed class MachineConstantPool; 30193323Sed class MachineFunction; 31193323Sed class MachineRegisterInfo; 32193323Sed class MachineInstr; 33243830Sdim struct MCSchedClassDesc; 34193323Sed class TargetRegisterInfo; 35193323Sed class ScheduleDAG; 36193323Sed class SDNode; 37193323Sed class TargetInstrInfo; 38224145Sdim class MCInstrDesc; 39193323Sed class TargetMachine; 40193323Sed class TargetRegisterClass; 41193323Sed template<class Graph> class GraphWriter; 42193323Sed 43193323Sed /// SDep - Scheduling dependency. This represents one direction of an 44193323Sed /// edge in the scheduling DAG. 45193323Sed class SDep { 46193323Sed public: 47193323Sed /// Kind - These are the different kinds of scheduling dependencies. 48193323Sed enum Kind { 49193323Sed Data, ///< Regular data dependence (aka true-dependence). 50193323Sed Anti, ///< A register anti-dependedence (aka WAR). 51193323Sed Output, ///< A register output-dependence (aka WAW). 52193323Sed Order ///< Any other ordering dependency. 53193323Sed }; 54193323Sed 55249423Sdim // Strong dependencies must be respected by the scheduler. Artificial 56249423Sdim // dependencies may be removed only if they are redundant with another 57249423Sdim // strong depedence. 58249423Sdim // 59249423Sdim // Weak dependencies may be violated by the scheduling strategy, but only if 60249423Sdim // the strategy can prove it is correct to do so. 61249423Sdim // 62249423Sdim // Strong OrderKinds must occur before "Weak". 63249423Sdim // Weak OrderKinds must occur after "Weak". 64243830Sdim enum OrderKind { 65243830Sdim Barrier, ///< An unknown scheduling barrier. 66243830Sdim MayAliasMem, ///< Nonvolatile load/Store instructions that may alias. 67243830Sdim MustAliasMem, ///< Nonvolatile load/Store instructions that must alias. 68249423Sdim Artificial, ///< Arbitrary strong DAG edge (no real dependence). 69249423Sdim Weak, ///< Arbitrary weak DAG edge. 70249423Sdim Cluster ///< Weak DAG edge linking a chain of clustered instrs. 71243830Sdim }; 72243830Sdim 73193323Sed private: 74193323Sed /// Dep - A pointer to the depending/depended-on SUnit, and an enum 75193323Sed /// indicating the kind of the dependency. 76193323Sed PointerIntPair<SUnit *, 2, Kind> Dep; 77193323Sed 78193323Sed /// Contents - A union discriminated by the dependence kind. 79193323Sed union { 80193323Sed /// Reg - For Data, Anti, and Output dependencies, the associated 81193323Sed /// register. For Data dependencies that don't currently have a register 82193323Sed /// assigned, this is set to zero. 83193323Sed unsigned Reg; 84193323Sed 85193323Sed /// Order - Additional information about Order dependencies. 86243830Sdim unsigned OrdKind; // enum OrderKind 87193323Sed } Contents; 88193323Sed 89193323Sed /// Latency - The time associated with this edge. Often this is just 90193323Sed /// the value of the Latency field of the predecessor, however advanced 91193323Sed /// models may provide additional information about specific edges. 92193323Sed unsigned Latency; 93243830Sdim /// Record MinLatency seperately from "expected" Latency. 94243830Sdim /// 95243830Sdim /// FIXME: this field is not packed on LP64. Convert to 16-bit DAG edge 96243830Sdim /// latency after introducing saturating truncation. 97243830Sdim unsigned MinLatency; 98193323Sed 99193323Sed public: 100193323Sed /// SDep - Construct a null SDep. This is only for use by container 101193323Sed /// classes which require default constructors. SUnits may not 102193323Sed /// have null SDep edges. 103193323Sed SDep() : Dep(0, Data) {} 104193323Sed 105193323Sed /// SDep - Construct an SDep with the specified values. 106243830Sdim SDep(SUnit *S, Kind kind, unsigned Reg) 107243830Sdim : Dep(S, kind), Contents() { 108193323Sed switch (kind) { 109243830Sdim default: 110243830Sdim llvm_unreachable("Reg given for non-register dependence!"); 111193323Sed case Anti: 112193323Sed case Output: 113193323Sed assert(Reg != 0 && 114193323Sed "SDep::Anti and SDep::Output must use a non-zero Reg!"); 115243830Sdim Contents.Reg = Reg; 116243830Sdim Latency = 0; 117243830Sdim break; 118193323Sed case Data: 119193323Sed Contents.Reg = Reg; 120243830Sdim Latency = 1; 121193323Sed break; 122193323Sed } 123243830Sdim MinLatency = Latency; 124193323Sed } 125243830Sdim SDep(SUnit *S, OrderKind kind) 126243830Sdim : Dep(S, Order), Contents(), Latency(0), MinLatency(0) { 127243830Sdim Contents.OrdKind = kind; 128243830Sdim } 129193323Sed 130239462Sdim /// Return true if the specified SDep is equivalent except for latency. 131239462Sdim bool overlaps(const SDep &Other) const { 132239462Sdim if (Dep != Other.Dep) return false; 133193323Sed switch (Dep.getInt()) { 134193323Sed case Data: 135193323Sed case Anti: 136193323Sed case Output: 137193323Sed return Contents.Reg == Other.Contents.Reg; 138193323Sed case Order: 139243830Sdim return Contents.OrdKind == Other.Contents.OrdKind; 140193323Sed } 141234353Sdim llvm_unreachable("Invalid dependency kind!"); 142193323Sed } 143193323Sed 144239462Sdim bool operator==(const SDep &Other) const { 145243830Sdim return overlaps(Other) 146243830Sdim && Latency == Other.Latency && MinLatency == Other.MinLatency; 147239462Sdim } 148239462Sdim 149193323Sed bool operator!=(const SDep &Other) const { 150193323Sed return !operator==(Other); 151193323Sed } 152193323Sed 153193323Sed /// getLatency - Return the latency value for this edge, which roughly 154193323Sed /// means the minimum number of cycles that must elapse between the 155193323Sed /// predecessor and the successor, given that they have this edge 156193323Sed /// between them. 157193323Sed unsigned getLatency() const { 158193323Sed return Latency; 159193323Sed } 160193323Sed 161198090Srdivacky /// setLatency - Set the latency for this edge. 162198090Srdivacky void setLatency(unsigned Lat) { 163198090Srdivacky Latency = Lat; 164198090Srdivacky } 165198090Srdivacky 166243830Sdim /// getMinLatency - Return the minimum latency for this edge. Minimum 167243830Sdim /// latency is used for scheduling groups, while normal (expected) latency 168243830Sdim /// is for instruction cost and critical path. 169243830Sdim unsigned getMinLatency() const { 170243830Sdim return MinLatency; 171243830Sdim } 172243830Sdim 173243830Sdim /// setMinLatency - Set the minimum latency for this edge. 174243830Sdim void setMinLatency(unsigned Lat) { 175243830Sdim MinLatency = Lat; 176243830Sdim } 177243830Sdim 178193323Sed //// getSUnit - Return the SUnit to which this edge points. 179193323Sed SUnit *getSUnit() const { 180193323Sed return Dep.getPointer(); 181193323Sed } 182193323Sed 183193323Sed //// setSUnit - Assign the SUnit to which this edge points. 184193323Sed void setSUnit(SUnit *SU) { 185193323Sed Dep.setPointer(SU); 186193323Sed } 187193323Sed 188193323Sed /// getKind - Return an enum value representing the kind of the dependence. 189193323Sed Kind getKind() const { 190193323Sed return Dep.getInt(); 191193323Sed } 192193323Sed 193193323Sed /// isCtrl - Shorthand for getKind() != SDep::Data. 194193323Sed bool isCtrl() const { 195193323Sed return getKind() != Data; 196193323Sed } 197193323Sed 198193323Sed /// isNormalMemory - Test if this is an Order dependence between two 199193323Sed /// memory accesses where both sides of the dependence access memory 200193323Sed /// in non-volatile and fully modeled ways. 201193323Sed bool isNormalMemory() const { 202243830Sdim return getKind() == Order && (Contents.OrdKind == MayAliasMem 203243830Sdim || Contents.OrdKind == MustAliasMem); 204193323Sed } 205193323Sed 206193323Sed /// isMustAlias - Test if this is an Order dependence that is marked 207193323Sed /// as "must alias", meaning that the SUnits at either end of the edge 208193323Sed /// have a memory dependence on a known memory location. 209193323Sed bool isMustAlias() const { 210243830Sdim return getKind() == Order && Contents.OrdKind == MustAliasMem; 211193323Sed } 212193323Sed 213249423Sdim /// isWeak - Test if this a weak dependence. Weak dependencies are 214249423Sdim /// considered DAG edges for height computation and other heuristics, but do 215249423Sdim /// not force ordering. Breaking a weak edge may require the scheduler to 216249423Sdim /// compensate, for example by inserting a copy. 217249423Sdim bool isWeak() const { 218249423Sdim return getKind() == Order && Contents.OrdKind >= Weak; 219249423Sdim } 220249423Sdim 221193323Sed /// isArtificial - Test if this is an Order dependence that is marked 222193323Sed /// as "artificial", meaning it isn't necessary for correctness. 223193323Sed bool isArtificial() const { 224243830Sdim return getKind() == Order && Contents.OrdKind == Artificial; 225193323Sed } 226193323Sed 227249423Sdim /// isCluster - Test if this is an Order dependence that is marked 228249423Sdim /// as "cluster", meaning it is artificial and wants to be adjacent. 229249423Sdim bool isCluster() const { 230249423Sdim return getKind() == Order && Contents.OrdKind == Cluster; 231249423Sdim } 232249423Sdim 233193323Sed /// isAssignedRegDep - Test if this is a Data dependence that is 234193323Sed /// associated with a register. 235193323Sed bool isAssignedRegDep() const { 236193323Sed return getKind() == Data && Contents.Reg != 0; 237193323Sed } 238193323Sed 239193323Sed /// getReg - Return the register associated with this edge. This is 240193323Sed /// only valid on Data, Anti, and Output edges. On Data edges, this 241193323Sed /// value may be zero, meaning there is no associated register. 242193323Sed unsigned getReg() const { 243193323Sed assert((getKind() == Data || getKind() == Anti || getKind() == Output) && 244193323Sed "getReg called on non-register dependence edge!"); 245193323Sed return Contents.Reg; 246193323Sed } 247193323Sed 248193323Sed /// setReg - Assign the associated register for this edge. This is 249193323Sed /// only valid on Data, Anti, and Output edges. On Anti and Output 250193323Sed /// edges, this value must not be zero. On Data edges, the value may 251193323Sed /// be zero, which would mean that no specific register is associated 252193323Sed /// with this edge. 253193323Sed void setReg(unsigned Reg) { 254193323Sed assert((getKind() == Data || getKind() == Anti || getKind() == Output) && 255193323Sed "setReg called on non-register dependence edge!"); 256193323Sed assert((getKind() != Anti || Reg != 0) && 257193323Sed "SDep::Anti edge cannot use the zero register!"); 258193323Sed assert((getKind() != Output || Reg != 0) && 259193323Sed "SDep::Output edge cannot use the zero register!"); 260193323Sed Contents.Reg = Reg; 261193323Sed } 262193323Sed }; 263193323Sed 264218893Sdim template <> 265218893Sdim struct isPodLike<SDep> { static const bool value = true; }; 266218893Sdim 267193323Sed /// SUnit - Scheduling unit. This is a node in the scheduling DAG. 268193323Sed class SUnit { 269193323Sed private: 270249423Sdim enum { BoundaryID = ~0u }; 271249423Sdim 272193323Sed SDNode *Node; // Representative node. 273193323Sed MachineInstr *Instr; // Alternatively, a MachineInstr. 274193323Sed public: 275193323Sed SUnit *OrigNode; // If not this, the node from which 276193323Sed // this node was cloned. 277234353Sdim // (SD scheduling only) 278218893Sdim 279243830Sdim const MCSchedClassDesc *SchedClass; // NULL or resolved SchedClass. 280243830Sdim 281218893Sdim // Preds/Succs - The SUnits before/after us in the graph. 282193323Sed SmallVector<SDep, 4> Preds; // All sunit predecessors. 283193323Sed SmallVector<SDep, 4> Succs; // All sunit successors. 284193323Sed 285193323Sed typedef SmallVector<SDep, 4>::iterator pred_iterator; 286193323Sed typedef SmallVector<SDep, 4>::iterator succ_iterator; 287193323Sed typedef SmallVector<SDep, 4>::const_iterator const_pred_iterator; 288193323Sed typedef SmallVector<SDep, 4>::const_iterator const_succ_iterator; 289208599Srdivacky 290193323Sed unsigned NodeNum; // Entry # of node in the node vector. 291193323Sed unsigned NodeQueueId; // Queue id of node. 292198090Srdivacky unsigned NumPreds; // # of SDep::Data preds. 293198090Srdivacky unsigned NumSuccs; // # of SDep::Data sucss. 294198090Srdivacky unsigned NumPredsLeft; // # of preds not scheduled. 295198090Srdivacky unsigned NumSuccsLeft; // # of succs not scheduled. 296249423Sdim unsigned WeakPredsLeft; // # of weak preds not scheduled. 297249423Sdim unsigned WeakSuccsLeft; // # of weak succs not scheduled. 298218893Sdim unsigned short NumRegDefsLeft; // # of reg defs with no scheduled use. 299218893Sdim unsigned short Latency; // Node latency. 300221345Sdim bool isVRegCycle : 1; // May use and def the same vreg. 301218893Sdim bool isCall : 1; // Is a function call. 302221345Sdim bool isCallOp : 1; // Is a function call operand. 303193323Sed bool isTwoAddress : 1; // Is a two-address instruction. 304193323Sed bool isCommutable : 1; // Is a commutable instruction. 305251662Sdim bool hasPhysRegUses : 1; // Has physreg uses. 306193323Sed bool hasPhysRegDefs : 1; // Has physreg defs that are being used. 307193323Sed bool hasPhysRegClobbers : 1; // Has any physreg defs, used or not. 308193323Sed bool isPending : 1; // True once pending. 309193323Sed bool isAvailable : 1; // True once available. 310193323Sed bool isScheduled : 1; // True once scheduled. 311193323Sed bool isScheduleHigh : 1; // True if preferable to schedule high. 312221345Sdim bool isScheduleLow : 1; // True if preferable to schedule low. 313193323Sed bool isCloned : 1; // True if this node has been cloned. 314208599Srdivacky Sched::Preference SchedulingPref; // Scheduling preference. 315208599Srdivacky 316193323Sed private: 317193323Sed bool isDepthCurrent : 1; // True if Depth is current. 318193323Sed bool isHeightCurrent : 1; // True if Height is current. 319193323Sed unsigned Depth; // Node depth. 320193323Sed unsigned Height; // Node height. 321193323Sed public: 322239462Sdim unsigned TopReadyCycle; // Cycle relative to start when node is ready. 323239462Sdim unsigned BotReadyCycle; // Cycle relative to end when node is ready. 324239462Sdim 325193323Sed const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null. 326193323Sed const TargetRegisterClass *CopySrcRC; 327218893Sdim 328193323Sed /// SUnit - Construct an SUnit for pre-regalloc scheduling to represent 329193323Sed /// an SDNode and any nodes flagged to it. 330193323Sed SUnit(SDNode *node, unsigned nodenum) 331243830Sdim : Node(node), Instr(0), OrigNode(0), SchedClass(0), NodeNum(nodenum), 332218893Sdim NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), 333249423Sdim NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), NumRegDefsLeft(0), 334249423Sdim Latency(0), isVRegCycle(false), isCall(false), isCallOp(false), 335251662Sdim isTwoAddress(false), isCommutable(false), hasPhysRegUses(false), 336251662Sdim hasPhysRegDefs(false), hasPhysRegClobbers(false), isPending(false), 337251662Sdim isAvailable(false), isScheduled(false), isScheduleHigh(false), 338251662Sdim isScheduleLow(false), isCloned(false), SchedulingPref(Sched::None), 339193323Sed isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), 340239462Sdim TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {} 341193323Sed 342193323Sed /// SUnit - Construct an SUnit for post-regalloc scheduling to represent 343193323Sed /// a MachineInstr. 344193323Sed SUnit(MachineInstr *instr, unsigned nodenum) 345243830Sdim : Node(0), Instr(instr), OrigNode(0), SchedClass(0), NodeNum(nodenum), 346218893Sdim NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), 347249423Sdim NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), NumRegDefsLeft(0), 348249423Sdim Latency(0), isVRegCycle(false), isCall(false), isCallOp(false), 349251662Sdim isTwoAddress(false), isCommutable(false), hasPhysRegUses(false), 350251662Sdim hasPhysRegDefs(false), hasPhysRegClobbers(false), isPending(false), 351251662Sdim isAvailable(false), isScheduled(false), isScheduleHigh(false), 352251662Sdim isScheduleLow(false), isCloned(false), SchedulingPref(Sched::None), 353193323Sed isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), 354239462Sdim TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {} 355193323Sed 356193323Sed /// SUnit - Construct a placeholder SUnit. 357193323Sed SUnit() 358249423Sdim : Node(0), Instr(0), OrigNode(0), SchedClass(0), NodeNum(BoundaryID), 359218893Sdim NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), 360249423Sdim NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), NumRegDefsLeft(0), 361249423Sdim Latency(0), isVRegCycle(false), isCall(false), isCallOp(false), 362251662Sdim isTwoAddress(false), isCommutable(false), hasPhysRegUses(false), 363251662Sdim hasPhysRegDefs(false), hasPhysRegClobbers(false), isPending(false), 364251662Sdim isAvailable(false), isScheduled(false), isScheduleHigh(false), 365251662Sdim isScheduleLow(false), isCloned(false), SchedulingPref(Sched::None), 366193323Sed isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), 367239462Sdim TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {} 368193323Sed 369249423Sdim /// \brief Boundary nodes are placeholders for the boundary of the 370249423Sdim /// scheduling region. 371249423Sdim /// 372249423Sdim /// BoundaryNodes can have DAG edges, including Data edges, but they do not 373249423Sdim /// correspond to schedulable entities (e.g. instructions) and do not have a 374249423Sdim /// valid ID. Consequently, always check for boundary nodes before accessing 375249423Sdim /// an assoicative data structure keyed on node ID. 376249423Sdim bool isBoundaryNode() const { return NodeNum == BoundaryID; }; 377249423Sdim 378193323Sed /// setNode - Assign the representative SDNode for this SUnit. 379193323Sed /// This may be used during pre-regalloc scheduling. 380193323Sed void setNode(SDNode *N) { 381193323Sed assert(!Instr && "Setting SDNode of SUnit with MachineInstr!"); 382193323Sed Node = N; 383193323Sed } 384193323Sed 385193323Sed /// getNode - Return the representative SDNode for this SUnit. 386193323Sed /// This may be used during pre-regalloc scheduling. 387193323Sed SDNode *getNode() const { 388193323Sed assert(!Instr && "Reading SDNode of SUnit with MachineInstr!"); 389193323Sed return Node; 390193323Sed } 391193323Sed 392218893Sdim /// isInstr - Return true if this SUnit refers to a machine instruction as 393218893Sdim /// opposed to an SDNode. 394218893Sdim bool isInstr() const { return Instr; } 395218893Sdim 396193323Sed /// setInstr - Assign the instruction for the SUnit. 397193323Sed /// This may be used during post-regalloc scheduling. 398193323Sed void setInstr(MachineInstr *MI) { 399193323Sed assert(!Node && "Setting MachineInstr of SUnit with SDNode!"); 400193323Sed Instr = MI; 401193323Sed } 402193323Sed 403193323Sed /// getInstr - Return the representative MachineInstr for this SUnit. 404193323Sed /// This may be used during post-regalloc scheduling. 405193323Sed MachineInstr *getInstr() const { 406193323Sed assert(!Node && "Reading MachineInstr of SUnit with SDNode!"); 407193323Sed return Instr; 408193323Sed } 409193323Sed 410193323Sed /// addPred - This adds the specified edge as a pred of the current node if 411193323Sed /// not already. It also adds the current node as a successor of the 412193323Sed /// specified node. 413249423Sdim bool addPred(const SDep &D, bool Required = true); 414193323Sed 415193323Sed /// removePred - This removes the specified edge as a pred of the current 416193323Sed /// node if it exists. It also removes the current node as a successor of 417193323Sed /// the specified node. 418193323Sed void removePred(const SDep &D); 419193323Sed 420193323Sed /// getDepth - Return the depth of this node, which is the length of the 421221345Sdim /// maximum path up to any node which has no predecessors. 422199989Srdivacky unsigned getDepth() const { 423218893Sdim if (!isDepthCurrent) 424199989Srdivacky const_cast<SUnit *>(this)->ComputeDepth(); 425193323Sed return Depth; 426193323Sed } 427193323Sed 428193323Sed /// getHeight - Return the height of this node, which is the length of the 429221345Sdim /// maximum path down to any node which has no successors. 430199989Srdivacky unsigned getHeight() const { 431218893Sdim if (!isHeightCurrent) 432199989Srdivacky const_cast<SUnit *>(this)->ComputeHeight(); 433193323Sed return Height; 434193323Sed } 435193323Sed 436198892Srdivacky /// setDepthToAtLeast - If NewDepth is greater than this node's 437198892Srdivacky /// depth value, set it to be the new depth value. This also 438199989Srdivacky /// recursively marks successor nodes dirty. 439199989Srdivacky void setDepthToAtLeast(unsigned NewDepth); 440193323Sed 441198892Srdivacky /// setDepthToAtLeast - If NewDepth is greater than this node's 442198892Srdivacky /// depth value, set it to be the new height value. This also 443199989Srdivacky /// recursively marks predecessor nodes dirty. 444199989Srdivacky void setHeightToAtLeast(unsigned NewHeight); 445193323Sed 446193323Sed /// setDepthDirty - Set a flag in this node to indicate that its 447193323Sed /// stored Depth value will require recomputation the next time 448193323Sed /// getDepth() is called. 449193323Sed void setDepthDirty(); 450193323Sed 451193323Sed /// setHeightDirty - Set a flag in this node to indicate that its 452193323Sed /// stored Height value will require recomputation the next time 453193323Sed /// getHeight() is called. 454193323Sed void setHeightDirty(); 455193323Sed 456193323Sed /// isPred - Test if node N is a predecessor of this node. 457193323Sed bool isPred(SUnit *N) { 458193323Sed for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i) 459193323Sed if (Preds[i].getSUnit() == N) 460193323Sed return true; 461193323Sed return false; 462193323Sed } 463218893Sdim 464193323Sed /// isSucc - Test if node N is a successor of this node. 465193323Sed bool isSucc(SUnit *N) { 466193323Sed for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i) 467193323Sed if (Succs[i].getSUnit() == N) 468193323Sed return true; 469193323Sed return false; 470193323Sed } 471208599Srdivacky 472234353Sdim bool isTopReady() const { 473234353Sdim return NumPredsLeft == 0; 474234353Sdim } 475234353Sdim bool isBottomReady() const { 476234353Sdim return NumSuccsLeft == 0; 477234353Sdim } 478234353Sdim 479249423Sdim /// \brief Order this node's predecessor edges such that the critical path 480249423Sdim /// edge occurs first. 481249423Sdim void biasCriticalPath(); 482249423Sdim 483193323Sed void dump(const ScheduleDAG *G) const; 484193323Sed void dumpAll(const ScheduleDAG *G) const; 485193323Sed void print(raw_ostream &O, const ScheduleDAG *G) const; 486193323Sed 487193323Sed private: 488199989Srdivacky void ComputeDepth(); 489199989Srdivacky void ComputeHeight(); 490193323Sed }; 491193323Sed 492193323Sed //===--------------------------------------------------------------------===// 493193323Sed /// SchedulingPriorityQueue - This interface is used to plug different 494193323Sed /// priorities computation algorithms into the list scheduler. It implements 495218893Sdim /// the interface of a standard priority queue, where nodes are inserted in 496193323Sed /// arbitrary order and returned in priority order. The computation of the 497193323Sed /// priority and the representation of the queue are totally up to the 498193323Sed /// implementation to decide. 499218893Sdim /// 500193323Sed class SchedulingPriorityQueue { 501234353Sdim virtual void anchor(); 502208599Srdivacky unsigned CurCycle; 503218893Sdim bool HasReadyFilter; 504193323Sed public: 505218893Sdim SchedulingPriorityQueue(bool rf = false): 506218893Sdim CurCycle(0), HasReadyFilter(rf) {} 507193323Sed virtual ~SchedulingPriorityQueue() {} 508218893Sdim 509218893Sdim virtual bool isBottomUp() const = 0; 510218893Sdim 511193323Sed virtual void initNodes(std::vector<SUnit> &SUnits) = 0; 512193323Sed virtual void addNode(const SUnit *SU) = 0; 513193323Sed virtual void updateNode(const SUnit *SU) = 0; 514193323Sed virtual void releaseState() = 0; 515193323Sed 516193323Sed virtual bool empty() const = 0; 517218893Sdim 518218893Sdim bool hasReadyFilter() const { return HasReadyFilter; } 519218893Sdim 520218893Sdim virtual bool tracksRegPressure() const { return false; } 521218893Sdim 522218893Sdim virtual bool isReady(SUnit *) const { 523218893Sdim assert(!HasReadyFilter && "The ready filter must override isReady()"); 524218893Sdim return true; 525218893Sdim } 526193323Sed virtual void push(SUnit *U) = 0; 527218893Sdim 528208599Srdivacky void push_all(const std::vector<SUnit *> &Nodes) { 529208599Srdivacky for (std::vector<SUnit *>::const_iterator I = Nodes.begin(), 530208599Srdivacky E = Nodes.end(); I != E; ++I) 531208599Srdivacky push(*I); 532208599Srdivacky } 533208599Srdivacky 534193323Sed virtual SUnit *pop() = 0; 535193323Sed 536193323Sed virtual void remove(SUnit *SU) = 0; 537193323Sed 538218893Sdim virtual void dump(ScheduleDAG *) const {} 539218893Sdim 540234353Sdim /// scheduledNode - As each node is scheduled, this method is invoked. This 541193323Sed /// allows the priority function to adjust the priority of related 542193323Sed /// unscheduled nodes, for example. 543193323Sed /// 544234353Sdim virtual void scheduledNode(SUnit *) {} 545193323Sed 546234353Sdim virtual void unscheduledNode(SUnit *) {} 547208599Srdivacky 548208599Srdivacky void setCurCycle(unsigned Cycle) { 549208599Srdivacky CurCycle = Cycle; 550208599Srdivacky } 551208599Srdivacky 552208599Srdivacky unsigned getCurCycle() const { 553208599Srdivacky return CurCycle; 554218893Sdim } 555193323Sed }; 556193323Sed 557193323Sed class ScheduleDAG { 558193323Sed public: 559193323Sed const TargetMachine &TM; // Target processor 560193323Sed const TargetInstrInfo *TII; // Target instruction information 561193323Sed const TargetRegisterInfo *TRI; // Target processor register info 562193323Sed MachineFunction &MF; // Machine function 563193323Sed MachineRegisterInfo &MRI; // Virtual/real register map 564193323Sed std::vector<SUnit> SUnits; // The scheduling units. 565193323Sed SUnit EntrySU; // Special node for the region entry. 566193323Sed SUnit ExitSU; // Special node for the region exit. 567193323Sed 568224145Sdim#ifdef NDEBUG 569224145Sdim static const bool StressSched = false; 570224145Sdim#else 571224145Sdim bool StressSched; 572224145Sdim#endif 573224145Sdim 574193323Sed explicit ScheduleDAG(MachineFunction &mf); 575193323Sed 576193323Sed virtual ~ScheduleDAG(); 577193323Sed 578234353Sdim /// clearDAG - clear the DAG state (between regions). 579234353Sdim void clearDAG(); 580234353Sdim 581224145Sdim /// getInstrDesc - Return the MCInstrDesc of this SUnit. 582218893Sdim /// Return NULL for SDNodes without a machine opcode. 583224145Sdim const MCInstrDesc *getInstrDesc(const SUnit *SU) const { 584218893Sdim if (SU->isInstr()) return &SU->getInstr()->getDesc(); 585218893Sdim return getNodeDesc(SU->getNode()); 586218893Sdim } 587218893Sdim 588193323Sed /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered 589193323Sed /// using 'dot'. 590193323Sed /// 591249423Sdim virtual void viewGraph(const Twine &Name, const Twine &Title); 592249423Sdim virtual void viewGraph(); 593218893Sdim 594193323Sed virtual void dumpNode(const SUnit *SU) const = 0; 595193323Sed 596193323Sed /// getGraphNodeLabel - Return a label for an SUnit node in a visualization 597193323Sed /// of the ScheduleDAG. 598193323Sed virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0; 599193323Sed 600234353Sdim /// getDAGLabel - Return a label for the region of code covered by the DAG. 601234353Sdim virtual std::string getDAGName() const = 0; 602234353Sdim 603193323Sed /// addCustomGraphFeatures - Add custom features for a visualization of 604193323Sed /// the ScheduleDAG. 605193323Sed virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {} 606193323Sed 607193323Sed#ifndef NDEBUG 608234353Sdim /// VerifyScheduledDAG - Verify that all SUnits were scheduled and that 609234353Sdim /// their state is consistent. Return the number of scheduled SUnits. 610234353Sdim unsigned VerifyScheduledDAG(bool isBottomUp); 611193323Sed#endif 612193323Sed 613218893Sdim private: 614224145Sdim // Return the MCInstrDesc of this SDNode or NULL. 615224145Sdim const MCInstrDesc *getNodeDesc(const SDNode *Node) const; 616193323Sed }; 617193323Sed 618198090Srdivacky class SUnitIterator : public std::iterator<std::forward_iterator_tag, 619198090Srdivacky SUnit, ptrdiff_t> { 620193323Sed SUnit *Node; 621193323Sed unsigned Operand; 622193323Sed 623193323Sed SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {} 624193323Sed public: 625193323Sed bool operator==(const SUnitIterator& x) const { 626193323Sed return Operand == x.Operand; 627193323Sed } 628193323Sed bool operator!=(const SUnitIterator& x) const { return !operator==(x); } 629193323Sed 630193323Sed const SUnitIterator &operator=(const SUnitIterator &I) { 631198090Srdivacky assert(I.Node==Node && "Cannot assign iterators to two different nodes!"); 632193323Sed Operand = I.Operand; 633193323Sed return *this; 634193323Sed } 635193323Sed 636193323Sed pointer operator*() const { 637193323Sed return Node->Preds[Operand].getSUnit(); 638193323Sed } 639193323Sed pointer operator->() const { return operator*(); } 640193323Sed 641193323Sed SUnitIterator& operator++() { // Preincrement 642193323Sed ++Operand; 643193323Sed return *this; 644193323Sed } 645193323Sed SUnitIterator operator++(int) { // Postincrement 646193323Sed SUnitIterator tmp = *this; ++*this; return tmp; 647193323Sed } 648193323Sed 649193323Sed static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); } 650193323Sed static SUnitIterator end (SUnit *N) { 651193323Sed return SUnitIterator(N, (unsigned)N->Preds.size()); 652193323Sed } 653193323Sed 654193323Sed unsigned getOperand() const { return Operand; } 655193323Sed const SUnit *getNode() const { return Node; } 656193323Sed /// isCtrlDep - Test if this is not an SDep::Data dependence. 657193323Sed bool isCtrlDep() const { 658193323Sed return getSDep().isCtrl(); 659193323Sed } 660193323Sed bool isArtificialDep() const { 661193323Sed return getSDep().isArtificial(); 662193323Sed } 663193323Sed const SDep &getSDep() const { 664193323Sed return Node->Preds[Operand]; 665193323Sed } 666193323Sed }; 667193323Sed 668193323Sed template <> struct GraphTraits<SUnit*> { 669193323Sed typedef SUnit NodeType; 670193323Sed typedef SUnitIterator ChildIteratorType; 671193323Sed static inline NodeType *getEntryNode(SUnit *N) { return N; } 672193323Sed static inline ChildIteratorType child_begin(NodeType *N) { 673193323Sed return SUnitIterator::begin(N); 674193323Sed } 675193323Sed static inline ChildIteratorType child_end(NodeType *N) { 676193323Sed return SUnitIterator::end(N); 677193323Sed } 678193323Sed }; 679193323Sed 680193323Sed template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> { 681193323Sed typedef std::vector<SUnit>::iterator nodes_iterator; 682193323Sed static nodes_iterator nodes_begin(ScheduleDAG *G) { 683193323Sed return G->SUnits.begin(); 684193323Sed } 685193323Sed static nodes_iterator nodes_end(ScheduleDAG *G) { 686193323Sed return G->SUnits.end(); 687193323Sed } 688193323Sed }; 689193323Sed 690193323Sed /// ScheduleDAGTopologicalSort is a class that computes a topological 691193323Sed /// ordering for SUnits and provides methods for dynamically updating 692193323Sed /// the ordering as new edges are added. 693193323Sed /// 694193323Sed /// This allows a very fast implementation of IsReachable, for example. 695193323Sed /// 696193323Sed class ScheduleDAGTopologicalSort { 697193323Sed /// SUnits - A reference to the ScheduleDAG's SUnits. 698193323Sed std::vector<SUnit> &SUnits; 699249423Sdim SUnit *ExitSU; 700193323Sed 701193323Sed /// Index2Node - Maps topological index to the node number. 702193323Sed std::vector<int> Index2Node; 703193323Sed /// Node2Index - Maps the node number to its topological index. 704193323Sed std::vector<int> Node2Index; 705193323Sed /// Visited - a set of nodes visited during a DFS traversal. 706193323Sed BitVector Visited; 707193323Sed 708218893Sdim /// DFS - make a DFS traversal and mark all nodes affected by the 709193323Sed /// edge insertion. These nodes will later get new topological indexes 710193323Sed /// by means of the Shift method. 711193323Sed void DFS(const SUnit *SU, int UpperBound, bool& HasLoop); 712193323Sed 713193323Sed /// Shift - reassign topological indexes for the nodes in the DAG 714193323Sed /// to preserve the topological ordering. 715193323Sed void Shift(BitVector& Visited, int LowerBound, int UpperBound); 716193323Sed 717193323Sed /// Allocate - assign the topological index to the node n. 718193323Sed void Allocate(int n, int index); 719193323Sed 720193323Sed public: 721249423Sdim ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU); 722193323Sed 723218893Sdim /// InitDAGTopologicalSorting - create the initial topological 724193323Sed /// ordering from the DAG to be scheduled. 725193323Sed void InitDAGTopologicalSorting(); 726193323Sed 727193323Sed /// IsReachable - Checks if SU is reachable from TargetSU. 728193323Sed bool IsReachable(const SUnit *SU, const SUnit *TargetSU); 729193323Sed 730251662Sdim /// WillCreateCycle - Return true if addPred(TargetSU, SU) creates a cycle. 731251662Sdim bool WillCreateCycle(SUnit *TargetSU, SUnit *SU); 732193323Sed 733221345Sdim /// AddPred - Updates the topological ordering to accommodate an edge 734193323Sed /// to be added from SUnit X to SUnit Y. 735193323Sed void AddPred(SUnit *Y, SUnit *X); 736193323Sed 737221345Sdim /// RemovePred - Updates the topological ordering to accommodate an 738193323Sed /// an edge to be removed from the specified node N from the predecessors 739193323Sed /// of the current node M. 740193323Sed void RemovePred(SUnit *M, SUnit *N); 741193323Sed 742193323Sed typedef std::vector<int>::iterator iterator; 743193323Sed typedef std::vector<int>::const_iterator const_iterator; 744193323Sed iterator begin() { return Index2Node.begin(); } 745193323Sed const_iterator begin() const { return Index2Node.begin(); } 746193323Sed iterator end() { return Index2Node.end(); } 747193323Sed const_iterator end() const { return Index2Node.end(); } 748193323Sed 749193323Sed typedef std::vector<int>::reverse_iterator reverse_iterator; 750193323Sed typedef std::vector<int>::const_reverse_iterator const_reverse_iterator; 751193323Sed reverse_iterator rbegin() { return Index2Node.rbegin(); } 752193323Sed const_reverse_iterator rbegin() const { return Index2Node.rbegin(); } 753193323Sed reverse_iterator rend() { return Index2Node.rend(); } 754193323Sed const_reverse_iterator rend() const { return Index2Node.rend(); } 755193323Sed }; 756193323Sed} 757193323Sed 758193323Sed#endif 759