1321369Sdim//===- llvm/CodeGen/ScheduleDAG.h - Common Base Class -----------*- C++ -*-===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed// 9321369Sdim/// \file Implements the ScheduleDAG class, which is used as the common base 10321369Sdim/// class for instruction schedulers. This encapsulates the scheduling DAG, 11321369Sdim/// which is shared between SelectionDAG and MachineInstr scheduling. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#ifndef LLVM_CODEGEN_SCHEDULEDAG_H 16193323Sed#define LLVM_CODEGEN_SCHEDULEDAG_H 17193323Sed 18193323Sed#include "llvm/ADT/BitVector.h" 19193323Sed#include "llvm/ADT/GraphTraits.h" 20249423Sdim#include "llvm/ADT/PointerIntPair.h" 21193323Sed#include "llvm/ADT/SmallVector.h" 22321369Sdim#include "llvm/ADT/iterator.h" 23249423Sdim#include "llvm/CodeGen/MachineInstr.h" 24327952Sdim#include "llvm/CodeGen/TargetLowering.h" 25321369Sdim#include "llvm/Support/ErrorHandling.h" 26321369Sdim#include <cassert> 27321369Sdim#include <cstddef> 28321369Sdim#include <iterator> 29321369Sdim#include <string> 30321369Sdim#include <vector> 31193323Sed 32193323Sednamespace llvm { 33193323Sed 34321369Sdimtemplate<class Graph> class GraphWriter; 35344779Sdimclass LLVMTargetMachine; 36321369Sdimclass MachineFunction; 37321369Sdimclass MachineRegisterInfo; 38321369Sdimclass MCInstrDesc; 39321369Sdimstruct MCSchedClassDesc; 40321369Sdimclass SDNode; 41321369Sdimclass SUnit; 42344779Sdimclass ScheduleDAG; 43321369Sdimclass TargetInstrInfo; 44321369Sdimclass TargetRegisterClass; 45321369Sdimclass TargetRegisterInfo; 46321369Sdim 47321369Sdim /// Scheduling dependency. This represents one direction of an edge in the 48321369Sdim /// scheduling DAG. 49193323Sed class SDep { 50193323Sed public: 51321369Sdim /// These are the different kinds of scheduling dependencies. 52193323Sed enum Kind { 53193323Sed Data, ///< Regular data dependence (aka true-dependence). 54321369Sdim Anti, ///< A register anti-dependence (aka WAR). 55193323Sed Output, ///< A register output-dependence (aka WAW). 56193323Sed Order ///< Any other ordering dependency. 57193323Sed }; 58193323Sed 59249423Sdim // Strong dependencies must be respected by the scheduler. Artificial 60249423Sdim // dependencies may be removed only if they are redundant with another 61321369Sdim // strong dependence. 62249423Sdim // 63249423Sdim // Weak dependencies may be violated by the scheduling strategy, but only if 64249423Sdim // the strategy can prove it is correct to do so. 65249423Sdim // 66249423Sdim // Strong OrderKinds must occur before "Weak". 67249423Sdim // Weak OrderKinds must occur after "Weak". 68243830Sdim enum OrderKind { 69243830Sdim Barrier, ///< An unknown scheduling barrier. 70243830Sdim MayAliasMem, ///< Nonvolatile load/Store instructions that may alias. 71243830Sdim MustAliasMem, ///< Nonvolatile load/Store instructions that must alias. 72249423Sdim Artificial, ///< Arbitrary strong DAG edge (no real dependence). 73249423Sdim Weak, ///< Arbitrary weak DAG edge. 74249423Sdim Cluster ///< Weak DAG edge linking a chain of clustered instrs. 75243830Sdim }; 76243830Sdim 77193323Sed private: 78341825Sdim /// A pointer to the depending/depended-on SUnit, and an enum 79193323Sed /// indicating the kind of the dependency. 80193323Sed PointerIntPair<SUnit *, 2, Kind> Dep; 81193323Sed 82321369Sdim /// A union discriminated by the dependence kind. 83193323Sed union { 84321369Sdim /// For Data, Anti, and Output dependencies, the associated register. For 85321369Sdim /// Data dependencies that don't currently have a register/ assigned, this 86321369Sdim /// is set to zero. 87193323Sed unsigned Reg; 88193323Sed 89321369Sdim /// Additional information about Order dependencies. 90243830Sdim unsigned OrdKind; // enum OrderKind 91193323Sed } Contents; 92193323Sed 93321369Sdim /// The time associated with this edge. Often this is just the value of the 94321369Sdim /// Latency field of the predecessor, however advanced models may provide 95321369Sdim /// additional information about specific edges. 96193323Sed unsigned Latency; 97193323Sed 98193323Sed public: 99321369Sdim /// Constructs a null SDep. This is only for use by container classes which 100321369Sdim /// require default constructors. SUnits may not/ have null SDep edges. 101276479Sdim SDep() : Dep(nullptr, Data) {} 102193323Sed 103321369Sdim /// Constructs an SDep with the specified values. 104243830Sdim SDep(SUnit *S, Kind kind, unsigned Reg) 105243830Sdim : Dep(S, kind), Contents() { 106193323Sed switch (kind) { 107243830Sdim default: 108243830Sdim llvm_unreachable("Reg given for non-register dependence!"); 109193323Sed case Anti: 110193323Sed case Output: 111193323Sed assert(Reg != 0 && 112193323Sed "SDep::Anti and SDep::Output must use a non-zero Reg!"); 113243830Sdim Contents.Reg = Reg; 114243830Sdim Latency = 0; 115243830Sdim break; 116193323Sed case Data: 117193323Sed Contents.Reg = Reg; 118243830Sdim Latency = 1; 119193323Sed break; 120193323Sed } 121193323Sed } 122321369Sdim 123243830Sdim SDep(SUnit *S, OrderKind kind) 124261991Sdim : Dep(S, Order), Contents(), Latency(0) { 125243830Sdim Contents.OrdKind = kind; 126243830Sdim } 127193323Sed 128321369Sdim /// Returns true if the specified SDep is equivalent except for latency. 129296417Sdim bool overlaps(const SDep &Other) const; 130193323Sed 131239462Sdim bool operator==(const SDep &Other) const { 132261991Sdim return overlaps(Other) && Latency == Other.Latency; 133239462Sdim } 134239462Sdim 135193323Sed bool operator!=(const SDep &Other) const { 136193323Sed return !operator==(Other); 137193323Sed } 138193323Sed 139341825Sdim /// Returns the latency value for this edge, which roughly means the 140321369Sdim /// minimum number of cycles that must elapse between the predecessor and 141321369Sdim /// the successor, given that they have this edge between them. 142193323Sed unsigned getLatency() const { 143193323Sed return Latency; 144193323Sed } 145193323Sed 146321369Sdim /// Sets the latency for this edge. 147198090Srdivacky void setLatency(unsigned Lat) { 148198090Srdivacky Latency = Lat; 149198090Srdivacky } 150198090Srdivacky 151321369Sdim //// Returns the SUnit to which this edge points. 152296417Sdim SUnit *getSUnit() const; 153193323Sed 154321369Sdim //// Assigns the SUnit to which this edge points. 155296417Sdim void setSUnit(SUnit *SU); 156193323Sed 157321369Sdim /// Returns an enum value representing the kind of the dependence. 158296417Sdim Kind getKind() const; 159193323Sed 160321369Sdim /// Shorthand for getKind() != SDep::Data. 161193323Sed bool isCtrl() const { 162193323Sed return getKind() != Data; 163193323Sed } 164193323Sed 165341825Sdim /// Tests if this is an Order dependence between two memory accesses 166321369Sdim /// where both sides of the dependence access memory in non-volatile and 167321369Sdim /// fully modeled ways. 168193323Sed bool isNormalMemory() const { 169243830Sdim return getKind() == Order && (Contents.OrdKind == MayAliasMem 170243830Sdim || Contents.OrdKind == MustAliasMem); 171193323Sed } 172193323Sed 173321369Sdim /// Tests if this is an Order dependence that is marked as a barrier. 174276479Sdim bool isBarrier() const { 175276479Sdim return getKind() == Order && Contents.OrdKind == Barrier; 176276479Sdim } 177276479Sdim 178321369Sdim /// Tests if this is could be any kind of memory dependence. 179280031Sdim bool isNormalMemoryOrBarrier() const { 180280031Sdim return (isNormalMemory() || isBarrier()); 181280031Sdim } 182280031Sdim 183341825Sdim /// Tests if this is an Order dependence that is marked as 184321369Sdim /// "must alias", meaning that the SUnits at either end of the edge have a 185321369Sdim /// memory dependence on a known memory location. 186193323Sed bool isMustAlias() const { 187243830Sdim return getKind() == Order && Contents.OrdKind == MustAliasMem; 188193323Sed } 189193323Sed 190321369Sdim /// Tests if this a weak dependence. Weak dependencies are considered DAG 191321369Sdim /// edges for height computation and other heuristics, but do not force 192321369Sdim /// ordering. Breaking a weak edge may require the scheduler to compensate, 193321369Sdim /// for example by inserting a copy. 194249423Sdim bool isWeak() const { 195249423Sdim return getKind() == Order && Contents.OrdKind >= Weak; 196249423Sdim } 197249423Sdim 198341825Sdim /// Tests if this is an Order dependence that is marked as 199321369Sdim /// "artificial", meaning it isn't necessary for correctness. 200193323Sed bool isArtificial() const { 201243830Sdim return getKind() == Order && Contents.OrdKind == Artificial; 202193323Sed } 203193323Sed 204341825Sdim /// Tests if this is an Order dependence that is marked as "cluster", 205321369Sdim /// meaning it is artificial and wants to be adjacent. 206249423Sdim bool isCluster() const { 207249423Sdim return getKind() == Order && Contents.OrdKind == Cluster; 208249423Sdim } 209249423Sdim 210321369Sdim /// Tests if this is a Data dependence that is associated with a register. 211193323Sed bool isAssignedRegDep() const { 212193323Sed return getKind() == Data && Contents.Reg != 0; 213193323Sed } 214193323Sed 215321369Sdim /// Returns the register associated with this edge. This is only valid on 216321369Sdim /// Data, Anti, and Output edges. On Data edges, this value may be zero, 217321369Sdim /// meaning there is no associated register. 218193323Sed unsigned getReg() const { 219193323Sed assert((getKind() == Data || getKind() == Anti || getKind() == Output) && 220193323Sed "getReg called on non-register dependence edge!"); 221193323Sed return Contents.Reg; 222193323Sed } 223193323Sed 224321369Sdim /// Assigns the associated register for this edge. This is only valid on 225321369Sdim /// Data, Anti, and Output edges. On Anti and Output edges, this value must 226321369Sdim /// not be zero. On Data edges, the value may be zero, which would mean that 227321369Sdim /// no specific register is associated with this edge. 228193323Sed void setReg(unsigned Reg) { 229193323Sed assert((getKind() == Data || getKind() == Anti || getKind() == Output) && 230193323Sed "setReg called on non-register dependence edge!"); 231193323Sed assert((getKind() != Anti || Reg != 0) && 232193323Sed "SDep::Anti edge cannot use the zero register!"); 233193323Sed assert((getKind() != Output || Reg != 0) && 234193323Sed "SDep::Output edge cannot use the zero register!"); 235193323Sed Contents.Reg = Reg; 236193323Sed } 237321369Sdim 238344779Sdim void dump(const TargetRegisterInfo *TRI = nullptr) const; 239193323Sed }; 240193323Sed 241321369Sdim /// Scheduling unit. This is a node in the scheduling DAG. 242193323Sed class SUnit { 243193323Sed private: 244276479Sdim enum : unsigned { BoundaryID = ~0u }; 245249423Sdim 246321369Sdim SDNode *Node = nullptr; ///< Representative node. 247321369Sdim MachineInstr *Instr = nullptr; ///< Alternatively, a MachineInstr. 248321369Sdim 249193323Sed public: 250341825Sdim SUnit *OrigNode = nullptr; ///< If not this, the node from which this node 251321369Sdim /// was cloned. (SD scheduling only) 252218893Sdim 253321369Sdim const MCSchedClassDesc *SchedClass = 254321369Sdim nullptr; ///< nullptr or resolved SchedClass. 255243830Sdim 256321369Sdim SmallVector<SDep, 4> Preds; ///< All sunit predecessors. 257321369Sdim SmallVector<SDep, 4> Succs; ///< All sunit successors. 258193323Sed 259261991Sdim typedef SmallVectorImpl<SDep>::iterator pred_iterator; 260261991Sdim typedef SmallVectorImpl<SDep>::iterator succ_iterator; 261261991Sdim typedef SmallVectorImpl<SDep>::const_iterator const_pred_iterator; 262261991Sdim typedef SmallVectorImpl<SDep>::const_iterator const_succ_iterator; 263208599Srdivacky 264321369Sdim unsigned NodeNum = BoundaryID; ///< Entry # of node in the node vector. 265321369Sdim unsigned NodeQueueId = 0; ///< Queue id of node. 266321369Sdim unsigned NumPreds = 0; ///< # of SDep::Data preds. 267321369Sdim unsigned NumSuccs = 0; ///< # of SDep::Data sucss. 268321369Sdim unsigned NumPredsLeft = 0; ///< # of preds not scheduled. 269321369Sdim unsigned NumSuccsLeft = 0; ///< # of succs not scheduled. 270321369Sdim unsigned WeakPredsLeft = 0; ///< # of weak preds not scheduled. 271321369Sdim unsigned WeakSuccsLeft = 0; ///< # of weak succs not scheduled. 272321369Sdim unsigned short NumRegDefsLeft = 0; ///< # of reg defs with no scheduled use. 273321369Sdim unsigned short Latency = 0; ///< Node latency. 274321369Sdim bool isVRegCycle : 1; ///< May use and def the same vreg. 275321369Sdim bool isCall : 1; ///< Is a function call. 276321369Sdim bool isCallOp : 1; ///< Is a function call operand. 277321369Sdim bool isTwoAddress : 1; ///< Is a two-address instruction. 278321369Sdim bool isCommutable : 1; ///< Is a commutable instruction. 279321369Sdim bool hasPhysRegUses : 1; ///< Has physreg uses. 280321369Sdim bool hasPhysRegDefs : 1; ///< Has physreg defs that are being used. 281321369Sdim bool hasPhysRegClobbers : 1; ///< Has any physreg defs, used or not. 282321369Sdim bool isPending : 1; ///< True once pending. 283321369Sdim bool isAvailable : 1; ///< True once available. 284321369Sdim bool isScheduled : 1; ///< True once scheduled. 285321369Sdim bool isScheduleHigh : 1; ///< True if preferable to schedule high. 286321369Sdim bool isScheduleLow : 1; ///< True if preferable to schedule low. 287321369Sdim bool isCloned : 1; ///< True if this node has been cloned. 288321369Sdim bool isUnbuffered : 1; ///< Uses an unbuffered resource. 289321369Sdim bool hasReservedResource : 1; ///< Uses a reserved resource. 290321369Sdim Sched::Preference SchedulingPref = Sched::None; ///< Scheduling preference. 291208599Srdivacky 292193323Sed private: 293321369Sdim bool isDepthCurrent : 1; ///< True if Depth is current. 294321369Sdim bool isHeightCurrent : 1; ///< True if Height is current. 295321369Sdim unsigned Depth = 0; ///< Node depth. 296321369Sdim unsigned Height = 0; ///< Node height. 297321369Sdim 298193323Sed public: 299321369Sdim unsigned TopReadyCycle = 0; ///< Cycle relative to start when node is ready. 300321369Sdim unsigned BotReadyCycle = 0; ///< Cycle relative to end when node is ready. 301239462Sdim 302321369Sdim const TargetRegisterClass *CopyDstRC = 303321369Sdim nullptr; ///< Is a special copy node if != nullptr. 304321369Sdim const TargetRegisterClass *CopySrcRC = nullptr; 305218893Sdim 306341825Sdim /// Constructs an SUnit for pre-regalloc scheduling to represent an 307321369Sdim /// SDNode and any nodes flagged to it. 308193323Sed SUnit(SDNode *node, unsigned nodenum) 309321369Sdim : Node(node), NodeNum(nodenum), isVRegCycle(false), isCall(false), 310276479Sdim isCallOp(false), isTwoAddress(false), isCommutable(false), 311276479Sdim hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), 312276479Sdim isPending(false), isAvailable(false), isScheduled(false), 313276479Sdim isScheduleHigh(false), isScheduleLow(false), isCloned(false), 314321369Sdim isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false), 315321369Sdim isHeightCurrent(false) {} 316193323Sed 317341825Sdim /// Constructs an SUnit for post-regalloc scheduling to represent a 318321369Sdim /// MachineInstr. 319193323Sed SUnit(MachineInstr *instr, unsigned nodenum) 320321369Sdim : Instr(instr), NodeNum(nodenum), isVRegCycle(false), isCall(false), 321276479Sdim isCallOp(false), isTwoAddress(false), isCommutable(false), 322276479Sdim hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), 323276479Sdim isPending(false), isAvailable(false), isScheduled(false), 324276479Sdim isScheduleHigh(false), isScheduleLow(false), isCloned(false), 325321369Sdim isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false), 326321369Sdim isHeightCurrent(false) {} 327193323Sed 328341825Sdim /// Constructs a placeholder SUnit. 329193323Sed SUnit() 330321369Sdim : isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false), 331321369Sdim isCommutable(false), hasPhysRegUses(false), hasPhysRegDefs(false), 332321369Sdim hasPhysRegClobbers(false), isPending(false), isAvailable(false), 333321369Sdim isScheduled(false), isScheduleHigh(false), isScheduleLow(false), 334321369Sdim isCloned(false), isUnbuffered(false), hasReservedResource(false), 335321369Sdim isDepthCurrent(false), isHeightCurrent(false) {} 336193323Sed 337341825Sdim /// Boundary nodes are placeholders for the boundary of the 338249423Sdim /// scheduling region. 339249423Sdim /// 340249423Sdim /// BoundaryNodes can have DAG edges, including Data edges, but they do not 341249423Sdim /// correspond to schedulable entities (e.g. instructions) and do not have a 342249423Sdim /// valid ID. Consequently, always check for boundary nodes before accessing 343321369Sdim /// an associative data structure keyed on node ID. 344296417Sdim bool isBoundaryNode() const { return NodeNum == BoundaryID; } 345249423Sdim 346321369Sdim /// Assigns the representative SDNode for this SUnit. This may be used 347321369Sdim /// during pre-regalloc scheduling. 348193323Sed void setNode(SDNode *N) { 349193323Sed assert(!Instr && "Setting SDNode of SUnit with MachineInstr!"); 350193323Sed Node = N; 351193323Sed } 352193323Sed 353321369Sdim /// Returns the representative SDNode for this SUnit. This may be used 354321369Sdim /// during pre-regalloc scheduling. 355193323Sed SDNode *getNode() const { 356193323Sed assert(!Instr && "Reading SDNode of SUnit with MachineInstr!"); 357193323Sed return Node; 358193323Sed } 359193323Sed 360341825Sdim /// Returns true if this SUnit refers to a machine instruction as 361218893Sdim /// opposed to an SDNode. 362218893Sdim bool isInstr() const { return Instr; } 363218893Sdim 364321369Sdim /// Assigns the instruction for the SUnit. This may be used during 365321369Sdim /// post-regalloc scheduling. 366193323Sed void setInstr(MachineInstr *MI) { 367193323Sed assert(!Node && "Setting MachineInstr of SUnit with SDNode!"); 368193323Sed Instr = MI; 369193323Sed } 370193323Sed 371321369Sdim /// Returns the representative MachineInstr for this SUnit. This may be used 372321369Sdim /// during post-regalloc scheduling. 373193323Sed MachineInstr *getInstr() const { 374193323Sed assert(!Node && "Reading MachineInstr of SUnit with SDNode!"); 375193323Sed return Instr; 376193323Sed } 377193323Sed 378321369Sdim /// Adds the specified edge as a pred of the current node if not already. 379321369Sdim /// It also adds the current node as a successor of the specified node. 380249423Sdim bool addPred(const SDep &D, bool Required = true); 381193323Sed 382341825Sdim /// Adds a barrier edge to SU by calling addPred(), with latency 0 383321369Sdim /// generally or latency 1 for a store followed by a load. 384309124Sdim bool addPredBarrier(SUnit *SU) { 385309124Sdim SDep Dep(SU, SDep::Barrier); 386309124Sdim unsigned TrueMemOrderLatency = 387309124Sdim ((SU->getInstr()->mayStore() && this->getInstr()->mayLoad()) ? 1 : 0); 388309124Sdim Dep.setLatency(TrueMemOrderLatency); 389309124Sdim return addPred(Dep); 390309124Sdim } 391309124Sdim 392321369Sdim /// Removes the specified edge as a pred of the current node if it exists. 393321369Sdim /// It also removes the current node as a successor of the specified node. 394193323Sed void removePred(const SDep &D); 395193323Sed 396321369Sdim /// Returns the depth of this node, which is the length of the maximum path 397321369Sdim /// up to any node which has no predecessors. 398199989Srdivacky unsigned getDepth() const { 399218893Sdim if (!isDepthCurrent) 400199989Srdivacky const_cast<SUnit *>(this)->ComputeDepth(); 401193323Sed return Depth; 402193323Sed } 403193323Sed 404341825Sdim /// Returns the height of this node, which is the length of the 405221345Sdim /// maximum path down to any node which has no successors. 406199989Srdivacky unsigned getHeight() const { 407218893Sdim if (!isHeightCurrent) 408199989Srdivacky const_cast<SUnit *>(this)->ComputeHeight(); 409193323Sed return Height; 410193323Sed } 411193323Sed 412341825Sdim /// If NewDepth is greater than this node's depth value, sets it to 413321369Sdim /// be the new depth value. This also recursively marks successor nodes 414321369Sdim /// dirty. 415199989Srdivacky void setDepthToAtLeast(unsigned NewDepth); 416193323Sed 417353358Sdim /// If NewHeight is greater than this node's height value, set it to be 418321369Sdim /// the new height value. This also recursively marks predecessor nodes 419321369Sdim /// dirty. 420199989Srdivacky void setHeightToAtLeast(unsigned NewHeight); 421193323Sed 422341825Sdim /// Sets a flag in this node to indicate that its stored Depth value 423321369Sdim /// will require recomputation the next time getDepth() is called. 424193323Sed void setDepthDirty(); 425193323Sed 426341825Sdim /// Sets a flag in this node to indicate that its stored Height value 427321369Sdim /// will require recomputation the next time getHeight() is called. 428193323Sed void setHeightDirty(); 429193323Sed 430321369Sdim /// Tests if node N is a predecessor of this node. 431321369Sdim bool isPred(const SUnit *N) const { 432321369Sdim for (const SDep &Pred : Preds) 433321369Sdim if (Pred.getSUnit() == N) 434193323Sed return true; 435193323Sed return false; 436193323Sed } 437218893Sdim 438321369Sdim /// Tests if node N is a successor of this node. 439321369Sdim bool isSucc(const SUnit *N) const { 440321369Sdim for (const SDep &Succ : Succs) 441321369Sdim if (Succ.getSUnit() == N) 442193323Sed return true; 443193323Sed return false; 444193323Sed } 445208599Srdivacky 446234353Sdim bool isTopReady() const { 447234353Sdim return NumPredsLeft == 0; 448234353Sdim } 449234353Sdim bool isBottomReady() const { 450234353Sdim return NumSuccsLeft == 0; 451234353Sdim } 452234353Sdim 453341825Sdim /// Orders this node's predecessor edges such that the critical path 454249423Sdim /// edge occurs first. 455249423Sdim void biasCriticalPath(); 456249423Sdim 457344779Sdim void dumpAttributes() const; 458193323Sed 459193323Sed private: 460199989Srdivacky void ComputeDepth(); 461199989Srdivacky void ComputeHeight(); 462193323Sed }; 463193323Sed 464321369Sdim /// Returns true if the specified SDep is equivalent except for latency. 465296417Sdim inline bool SDep::overlaps(const SDep &Other) const { 466296417Sdim if (Dep != Other.Dep) 467296417Sdim return false; 468296417Sdim switch (Dep.getInt()) { 469296417Sdim case Data: 470296417Sdim case Anti: 471296417Sdim case Output: 472296417Sdim return Contents.Reg == Other.Contents.Reg; 473296417Sdim case Order: 474296417Sdim return Contents.OrdKind == Other.Contents.OrdKind; 475296417Sdim } 476296417Sdim llvm_unreachable("Invalid dependency kind!"); 477296417Sdim } 478296417Sdim 479321369Sdim //// Returns the SUnit to which this edge points. 480296417Sdim inline SUnit *SDep::getSUnit() const { return Dep.getPointer(); } 481296417Sdim 482321369Sdim //// Assigns the SUnit to which this edge points. 483296417Sdim inline void SDep::setSUnit(SUnit *SU) { Dep.setPointer(SU); } 484296417Sdim 485321369Sdim /// Returns an enum value representing the kind of the dependence. 486296417Sdim inline SDep::Kind SDep::getKind() const { return Dep.getInt(); } 487296417Sdim 488193323Sed //===--------------------------------------------------------------------===// 489321369Sdim 490341825Sdim /// This interface is used to plug different priorities computation 491321369Sdim /// algorithms into the list scheduler. It implements the interface of a 492321369Sdim /// standard priority queue, where nodes are inserted in arbitrary order and 493321369Sdim /// returned in priority order. The computation of the priority and the 494321369Sdim /// representation of the queue are totally up to the implementation to 495321369Sdim /// decide. 496193323Sed class SchedulingPriorityQueue { 497234353Sdim virtual void anchor(); 498321369Sdim 499321369Sdim unsigned CurCycle = 0; 500218893Sdim bool HasReadyFilter; 501321369Sdim 502193323Sed public: 503321369Sdim SchedulingPriorityQueue(bool rf = false) : HasReadyFilter(rf) {} 504218893Sdim 505321369Sdim virtual ~SchedulingPriorityQueue() = default; 506321369Sdim 507218893Sdim virtual bool isBottomUp() const = 0; 508218893Sdim 509193323Sed virtual void initNodes(std::vector<SUnit> &SUnits) = 0; 510193323Sed virtual void addNode(const SUnit *SU) = 0; 511193323Sed virtual void updateNode(const SUnit *SU) = 0; 512193323Sed virtual void releaseState() = 0; 513193323Sed 514193323Sed virtual bool empty() const = 0; 515218893Sdim 516218893Sdim bool hasReadyFilter() const { return HasReadyFilter; } 517218893Sdim 518218893Sdim virtual bool tracksRegPressure() const { return false; } 519218893Sdim 520218893Sdim virtual bool isReady(SUnit *) const { 521218893Sdim assert(!HasReadyFilter && "The ready filter must override isReady()"); 522218893Sdim return true; 523218893Sdim } 524321369Sdim 525193323Sed virtual void push(SUnit *U) = 0; 526218893Sdim 527208599Srdivacky void push_all(const std::vector<SUnit *> &Nodes) { 528208599Srdivacky for (std::vector<SUnit *>::const_iterator I = Nodes.begin(), 529208599Srdivacky E = Nodes.end(); I != E; ++I) 530208599Srdivacky push(*I); 531208599Srdivacky } 532208599Srdivacky 533193323Sed virtual SUnit *pop() = 0; 534193323Sed 535193323Sed virtual void remove(SUnit *SU) = 0; 536193323Sed 537218893Sdim virtual void dump(ScheduleDAG *) const {} 538218893Sdim 539321369Sdim /// As each node is scheduled, this method is invoked. This allows the 540321369Sdim /// priority function to adjust the priority of related unscheduled nodes, 541321369Sdim /// for example. 542234353Sdim virtual void scheduledNode(SUnit *) {} 543193323Sed 544234353Sdim virtual void unscheduledNode(SUnit *) {} 545208599Srdivacky 546208599Srdivacky void setCurCycle(unsigned Cycle) { 547208599Srdivacky CurCycle = Cycle; 548208599Srdivacky } 549208599Srdivacky 550208599Srdivacky unsigned getCurCycle() const { 551208599Srdivacky return CurCycle; 552218893Sdim } 553193323Sed }; 554193323Sed 555193323Sed class ScheduleDAG { 556193323Sed public: 557344779Sdim const LLVMTargetMachine &TM; ///< Target processor 558321369Sdim const TargetInstrInfo *TII; ///< Target instruction information 559321369Sdim const TargetRegisterInfo *TRI; ///< Target processor register info 560321369Sdim MachineFunction &MF; ///< Machine function 561321369Sdim MachineRegisterInfo &MRI; ///< Virtual/real register map 562321369Sdim std::vector<SUnit> SUnits; ///< The scheduling units. 563321369Sdim SUnit EntrySU; ///< Special node for the region entry. 564321369Sdim SUnit ExitSU; ///< Special node for the region exit. 565193323Sed 566224145Sdim#ifdef NDEBUG 567224145Sdim static const bool StressSched = false; 568224145Sdim#else 569224145Sdim bool StressSched; 570224145Sdim#endif 571224145Sdim 572193323Sed explicit ScheduleDAG(MachineFunction &mf); 573193323Sed 574193323Sed virtual ~ScheduleDAG(); 575193323Sed 576321369Sdim /// Clears the DAG state (between regions). 577234353Sdim void clearDAG(); 578234353Sdim 579321369Sdim /// Returns the MCInstrDesc of this SUnit. 580321369Sdim /// Returns NULL for SDNodes without a machine opcode. 581224145Sdim const MCInstrDesc *getInstrDesc(const SUnit *SU) const { 582218893Sdim if (SU->isInstr()) return &SU->getInstr()->getDesc(); 583218893Sdim return getNodeDesc(SU->getNode()); 584218893Sdim } 585218893Sdim 586321369Sdim /// Pops up a GraphViz/gv window with the ScheduleDAG rendered using 'dot'. 587249423Sdim virtual void viewGraph(const Twine &Name, const Twine &Title); 588249423Sdim virtual void viewGraph(); 589218893Sdim 590344779Sdim virtual void dumpNode(const SUnit &SU) const = 0; 591344779Sdim virtual void dump() const = 0; 592344779Sdim void dumpNodeName(const SUnit &SU) const; 593193323Sed 594321369Sdim /// Returns a label for an SUnit node in a visualization of the ScheduleDAG. 595193323Sed virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0; 596193323Sed 597321369Sdim /// Returns a label for the region of code covered by the DAG. 598234353Sdim virtual std::string getDAGName() const = 0; 599234353Sdim 600321369Sdim /// Adds custom features for a visualization of the ScheduleDAG. 601193323Sed virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {} 602193323Sed 603193323Sed#ifndef NDEBUG 604341825Sdim /// Verifies that all SUnits were scheduled and that their state is 605321369Sdim /// consistent. Returns the number of scheduled SUnits. 606234353Sdim unsigned VerifyScheduledDAG(bool isBottomUp); 607193323Sed#endif 608193323Sed 609344779Sdim protected: 610344779Sdim void dumpNodeAll(const SUnit &SU) const; 611344779Sdim 612218893Sdim private: 613321369Sdim /// Returns the MCInstrDesc of this SDNode or NULL. 614224145Sdim const MCInstrDesc *getNodeDesc(const SDNode *Node) const; 615193323Sed }; 616193323Sed 617198090Srdivacky class SUnitIterator : public std::iterator<std::forward_iterator_tag, 618198090Srdivacky SUnit, ptrdiff_t> { 619193323Sed SUnit *Node; 620193323Sed unsigned Operand; 621193323Sed 622193323Sed SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {} 623321369Sdim 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 pointer operator*() const { 631193323Sed return Node->Preds[Operand].getSUnit(); 632193323Sed } 633193323Sed pointer operator->() const { return operator*(); } 634193323Sed 635193323Sed SUnitIterator& operator++() { // Preincrement 636193323Sed ++Operand; 637193323Sed return *this; 638193323Sed } 639193323Sed SUnitIterator operator++(int) { // Postincrement 640193323Sed SUnitIterator tmp = *this; ++*this; return tmp; 641193323Sed } 642193323Sed 643193323Sed static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); } 644193323Sed static SUnitIterator end (SUnit *N) { 645193323Sed return SUnitIterator(N, (unsigned)N->Preds.size()); 646193323Sed } 647193323Sed 648193323Sed unsigned getOperand() const { return Operand; } 649193323Sed const SUnit *getNode() const { return Node; } 650321369Sdim 651321369Sdim /// Tests if this is not an SDep::Data dependence. 652193323Sed bool isCtrlDep() const { 653193323Sed return getSDep().isCtrl(); 654193323Sed } 655193323Sed bool isArtificialDep() const { 656193323Sed return getSDep().isArtificial(); 657193323Sed } 658193323Sed const SDep &getSDep() const { 659193323Sed return Node->Preds[Operand]; 660193323Sed } 661193323Sed }; 662193323Sed 663193323Sed template <> struct GraphTraits<SUnit*> { 664314564Sdim typedef SUnit *NodeRef; 665193323Sed typedef SUnitIterator ChildIteratorType; 666314564Sdim static NodeRef getEntryNode(SUnit *N) { return N; } 667314564Sdim static ChildIteratorType child_begin(NodeRef N) { 668193323Sed return SUnitIterator::begin(N); 669193323Sed } 670314564Sdim static ChildIteratorType child_end(NodeRef N) { 671193323Sed return SUnitIterator::end(N); 672193323Sed } 673193323Sed }; 674193323Sed 675193323Sed template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> { 676314564Sdim typedef pointer_iterator<std::vector<SUnit>::iterator> nodes_iterator; 677193323Sed static nodes_iterator nodes_begin(ScheduleDAG *G) { 678314564Sdim return nodes_iterator(G->SUnits.begin()); 679193323Sed } 680193323Sed static nodes_iterator nodes_end(ScheduleDAG *G) { 681314564Sdim return nodes_iterator(G->SUnits.end()); 682193323Sed } 683193323Sed }; 684193323Sed 685321369Sdim /// This class can compute a topological ordering for SUnits and provides 686321369Sdim /// methods for dynamically updating the ordering as new edges are added. 687193323Sed /// 688193323Sed /// This allows a very fast implementation of IsReachable, for example. 689193323Sed class ScheduleDAGTopologicalSort { 690321369Sdim /// A reference to the ScheduleDAG's SUnits. 691193323Sed std::vector<SUnit> &SUnits; 692249423Sdim SUnit *ExitSU; 693193323Sed 694353358Sdim // Have any new nodes been added? 695353358Sdim bool Dirty = false; 696353358Sdim 697353358Sdim // Outstanding added edges, that have not been applied to the ordering. 698353358Sdim SmallVector<std::pair<SUnit *, SUnit *>, 16> Updates; 699353358Sdim 700321369Sdim /// Maps topological index to the node number. 701193323Sed std::vector<int> Index2Node; 702321369Sdim /// Maps the node number to its topological index. 703193323Sed std::vector<int> Node2Index; 704321369Sdim /// a set of nodes visited during a DFS traversal. 705193323Sed BitVector Visited; 706193323Sed 707321369Sdim /// Makes a DFS traversal and mark all nodes affected by the edge insertion. 708321369Sdim /// These nodes will later get new topological indexes by means of the Shift 709321369Sdim /// method. 710193323Sed void DFS(const SUnit *SU, int UpperBound, bool& HasLoop); 711193323Sed 712341825Sdim /// Reassigns topological indexes for the nodes in the DAG to 713321369Sdim /// preserve the topological ordering. 714193323Sed void Shift(BitVector& Visited, int LowerBound, int UpperBound); 715193323Sed 716321369Sdim /// Assigns the topological index to the node n. 717193323Sed void Allocate(int n, int index); 718193323Sed 719353358Sdim /// Fix the ordering, by either recomputing from scratch or by applying 720353358Sdim /// any outstanding updates. Uses a heuristic to estimate what will be 721353358Sdim /// cheaper. 722353358Sdim void FixOrder(); 723353358Sdim 724193323Sed public: 725249423Sdim ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU); 726193323Sed 727321369Sdim /// Creates the initial topological ordering from the DAG to be scheduled. 728193323Sed void InitDAGTopologicalSorting(); 729193323Sed 730321369Sdim /// Returns an array of SUs that are both in the successor 731321369Sdim /// subtree of StartSU and in the predecessor subtree of TargetSU. 732321369Sdim /// StartSU and TargetSU are not in the array. 733321369Sdim /// Success is false if TargetSU is not in the successor subtree of 734321369Sdim /// StartSU, else it is true. 735321369Sdim std::vector<int> GetSubGraph(const SUnit &StartSU, const SUnit &TargetSU, 736321369Sdim bool &Success); 737321369Sdim 738321369Sdim /// Checks if \p SU is reachable from \p TargetSU. 739193323Sed bool IsReachable(const SUnit *SU, const SUnit *TargetSU); 740193323Sed 741321369Sdim /// Returns true if addPred(TargetSU, SU) creates a cycle. 742251662Sdim bool WillCreateCycle(SUnit *TargetSU, SUnit *SU); 743193323Sed 744341825Sdim /// Updates the topological ordering to accommodate an edge to be 745321369Sdim /// added from SUnit \p X to SUnit \p Y. 746193323Sed void AddPred(SUnit *Y, SUnit *X); 747193323Sed 748353358Sdim /// Queues an update to the topological ordering to accommodate an edge to 749353358Sdim /// be added from SUnit \p X to SUnit \p Y. 750353358Sdim void AddPredQueued(SUnit *Y, SUnit *X); 751353358Sdim 752341825Sdim /// Updates the topological ordering to accommodate an an edge to be 753321369Sdim /// removed from the specified node \p N from the predecessors of the 754321369Sdim /// current node \p M. 755193323Sed void RemovePred(SUnit *M, SUnit *N); 756193323Sed 757353358Sdim /// Mark the ordering as temporarily broken, after a new node has been 758353358Sdim /// added. 759353358Sdim void MarkDirty() { Dirty = true; } 760353358Sdim 761193323Sed typedef std::vector<int>::iterator iterator; 762193323Sed typedef std::vector<int>::const_iterator const_iterator; 763193323Sed iterator begin() { return Index2Node.begin(); } 764193323Sed const_iterator begin() const { return Index2Node.begin(); } 765193323Sed iterator end() { return Index2Node.end(); } 766193323Sed const_iterator end() const { return Index2Node.end(); } 767193323Sed 768193323Sed typedef std::vector<int>::reverse_iterator reverse_iterator; 769193323Sed typedef std::vector<int>::const_reverse_iterator const_reverse_iterator; 770193323Sed reverse_iterator rbegin() { return Index2Node.rbegin(); } 771193323Sed const_reverse_iterator rbegin() const { return Index2Node.rbegin(); } 772193323Sed reverse_iterator rend() { return Index2Node.rend(); } 773193323Sed const_reverse_iterator rend() const { return Index2Node.rend(); } 774193323Sed }; 775193323Sed 776321369Sdim} // end namespace llvm 777321369Sdim 778321369Sdim#endif // LLVM_CODEGEN_SCHEDULEDAG_H 779