10b57cec5SDimitry Andric //===- llvm/CodeGen/ScheduleDAG.h - Common Base Class -----------*- C++ -*-===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric // 90b57cec5SDimitry Andric /// \file Implements the ScheduleDAG class, which is used as the common base 100b57cec5SDimitry Andric /// class for instruction schedulers. This encapsulates the scheduling DAG, 110b57cec5SDimitry Andric /// which is shared between SelectionDAG and MachineInstr scheduling. 120b57cec5SDimitry Andric // 130b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 140b57cec5SDimitry Andric 150b57cec5SDimitry Andric #ifndef LLVM_CODEGEN_SCHEDULEDAG_H 160b57cec5SDimitry Andric #define LLVM_CODEGEN_SCHEDULEDAG_H 170b57cec5SDimitry Andric 180b57cec5SDimitry Andric #include "llvm/ADT/BitVector.h" 190b57cec5SDimitry Andric #include "llvm/ADT/PointerIntPair.h" 200b57cec5SDimitry Andric #include "llvm/ADT/SmallVector.h" 210b57cec5SDimitry Andric #include "llvm/ADT/iterator.h" 220b57cec5SDimitry Andric #include "llvm/CodeGen/MachineInstr.h" 230b57cec5SDimitry Andric #include "llvm/CodeGen/TargetLowering.h" 240b57cec5SDimitry Andric #include "llvm/Support/ErrorHandling.h" 250b57cec5SDimitry Andric #include <cassert> 260b57cec5SDimitry Andric #include <cstddef> 270b57cec5SDimitry Andric #include <iterator> 280b57cec5SDimitry Andric #include <string> 290b57cec5SDimitry Andric #include <vector> 300b57cec5SDimitry Andric 310b57cec5SDimitry Andric namespace llvm { 320b57cec5SDimitry Andric 3381ad6265SDimitry Andric template <class GraphType> struct GraphTraits; 340b57cec5SDimitry Andric template<class Graph> class GraphWriter; 350b57cec5SDimitry Andric class LLVMTargetMachine; 360b57cec5SDimitry Andric class MachineFunction; 370b57cec5SDimitry Andric class MachineRegisterInfo; 380b57cec5SDimitry Andric class MCInstrDesc; 390b57cec5SDimitry Andric struct MCSchedClassDesc; 400b57cec5SDimitry Andric class SDNode; 410b57cec5SDimitry Andric class SUnit; 420b57cec5SDimitry Andric class ScheduleDAG; 430b57cec5SDimitry Andric class TargetInstrInfo; 440b57cec5SDimitry Andric class TargetRegisterClass; 450b57cec5SDimitry Andric class TargetRegisterInfo; 460b57cec5SDimitry Andric 470b57cec5SDimitry Andric /// Scheduling dependency. This represents one direction of an edge in the 480b57cec5SDimitry Andric /// scheduling DAG. 490b57cec5SDimitry Andric class SDep { 500b57cec5SDimitry Andric public: 510b57cec5SDimitry Andric /// These are the different kinds of scheduling dependencies. 520b57cec5SDimitry Andric enum Kind { 530b57cec5SDimitry Andric Data, ///< Regular data dependence (aka true-dependence). 540b57cec5SDimitry Andric Anti, ///< A register anti-dependence (aka WAR). 550b57cec5SDimitry Andric Output, ///< A register output-dependence (aka WAW). 560b57cec5SDimitry Andric Order ///< Any other ordering dependency. 570b57cec5SDimitry Andric }; 580b57cec5SDimitry Andric 590b57cec5SDimitry Andric // Strong dependencies must be respected by the scheduler. Artificial 600b57cec5SDimitry Andric // dependencies may be removed only if they are redundant with another 610b57cec5SDimitry Andric // strong dependence. 620b57cec5SDimitry Andric // 630b57cec5SDimitry Andric // Weak dependencies may be violated by the scheduling strategy, but only if 640b57cec5SDimitry Andric // the strategy can prove it is correct to do so. 650b57cec5SDimitry Andric // 660b57cec5SDimitry Andric // Strong OrderKinds must occur before "Weak". 670b57cec5SDimitry Andric // Weak OrderKinds must occur after "Weak". 680b57cec5SDimitry Andric enum OrderKind { 690b57cec5SDimitry Andric Barrier, ///< An unknown scheduling barrier. 700b57cec5SDimitry Andric MayAliasMem, ///< Nonvolatile load/Store instructions that may alias. 710b57cec5SDimitry Andric MustAliasMem, ///< Nonvolatile load/Store instructions that must alias. 720b57cec5SDimitry Andric Artificial, ///< Arbitrary strong DAG edge (no real dependence). 730b57cec5SDimitry Andric Weak, ///< Arbitrary weak DAG edge. 740b57cec5SDimitry Andric Cluster ///< Weak DAG edge linking a chain of clustered instrs. 750b57cec5SDimitry Andric }; 760b57cec5SDimitry Andric 770b57cec5SDimitry Andric private: 780b57cec5SDimitry Andric /// A pointer to the depending/depended-on SUnit, and an enum 790b57cec5SDimitry Andric /// indicating the kind of the dependency. 800b57cec5SDimitry Andric PointerIntPair<SUnit *, 2, Kind> Dep; 810b57cec5SDimitry Andric 820b57cec5SDimitry Andric /// A union discriminated by the dependence kind. 830b57cec5SDimitry Andric union { 840b57cec5SDimitry Andric /// For Data, Anti, and Output dependencies, the associated register. For 850b57cec5SDimitry Andric /// Data dependencies that don't currently have a register/ assigned, this 860b57cec5SDimitry Andric /// is set to zero. 870b57cec5SDimitry Andric unsigned Reg; 880b57cec5SDimitry Andric 890b57cec5SDimitry Andric /// Additional information about Order dependencies. 900b57cec5SDimitry Andric unsigned OrdKind; // enum OrderKind 910b57cec5SDimitry Andric } Contents; 920b57cec5SDimitry Andric 930b57cec5SDimitry Andric /// The time associated with this edge. Often this is just the value of the 940b57cec5SDimitry Andric /// Latency field of the predecessor, however advanced models may provide 950b57cec5SDimitry Andric /// additional information about specific edges. 9606c3fb27SDimitry Andric unsigned Latency = 0u; 970b57cec5SDimitry Andric 980b57cec5SDimitry Andric public: 990b57cec5SDimitry Andric /// Constructs a null SDep. This is only for use by container classes which 1000b57cec5SDimitry Andric /// require default constructors. SUnits may not/ have null SDep edges. SDep()1010b57cec5SDimitry Andric SDep() : Dep(nullptr, Data) {} 1020b57cec5SDimitry Andric 1030b57cec5SDimitry Andric /// Constructs an SDep with the specified values. SDep(SUnit * S,Kind kind,unsigned Reg)1040b57cec5SDimitry Andric SDep(SUnit *S, Kind kind, unsigned Reg) 1050b57cec5SDimitry Andric : Dep(S, kind), Contents() { 1060b57cec5SDimitry Andric switch (kind) { 1070b57cec5SDimitry Andric default: 1080b57cec5SDimitry Andric llvm_unreachable("Reg given for non-register dependence!"); 1090b57cec5SDimitry Andric case Anti: 1100b57cec5SDimitry Andric case Output: 1110b57cec5SDimitry Andric assert(Reg != 0 && 1120b57cec5SDimitry Andric "SDep::Anti and SDep::Output must use a non-zero Reg!"); 1130b57cec5SDimitry Andric Contents.Reg = Reg; 1140b57cec5SDimitry Andric Latency = 0; 1150b57cec5SDimitry Andric break; 1160b57cec5SDimitry Andric case Data: 1170b57cec5SDimitry Andric Contents.Reg = Reg; 1180b57cec5SDimitry Andric Latency = 1; 1190b57cec5SDimitry Andric break; 1200b57cec5SDimitry Andric } 1210b57cec5SDimitry Andric } 1220b57cec5SDimitry Andric SDep(SUnit * S,OrderKind kind)1230b57cec5SDimitry Andric SDep(SUnit *S, OrderKind kind) 1240b57cec5SDimitry Andric : Dep(S, Order), Contents(), Latency(0) { 1250b57cec5SDimitry Andric Contents.OrdKind = kind; 1260b57cec5SDimitry Andric } 1270b57cec5SDimitry Andric 1280b57cec5SDimitry Andric /// Returns true if the specified SDep is equivalent except for latency. 1290b57cec5SDimitry Andric bool overlaps(const SDep &Other) const; 1300b57cec5SDimitry Andric 1310b57cec5SDimitry Andric bool operator==(const SDep &Other) const { 1320b57cec5SDimitry Andric return overlaps(Other) && Latency == Other.Latency; 1330b57cec5SDimitry Andric } 1340b57cec5SDimitry Andric 1350b57cec5SDimitry Andric bool operator!=(const SDep &Other) const { 1360b57cec5SDimitry Andric return !operator==(Other); 1370b57cec5SDimitry Andric } 1380b57cec5SDimitry Andric 1390b57cec5SDimitry Andric /// Returns the latency value for this edge, which roughly means the 1400b57cec5SDimitry Andric /// minimum number of cycles that must elapse between the predecessor and 1410b57cec5SDimitry Andric /// the successor, given that they have this edge between them. getLatency()1420b57cec5SDimitry Andric unsigned getLatency() const { 1430b57cec5SDimitry Andric return Latency; 1440b57cec5SDimitry Andric } 1450b57cec5SDimitry Andric 1460b57cec5SDimitry Andric /// Sets the latency for this edge. setLatency(unsigned Lat)1470b57cec5SDimitry Andric void setLatency(unsigned Lat) { 1480b57cec5SDimitry Andric Latency = Lat; 1490b57cec5SDimitry Andric } 1500b57cec5SDimitry Andric 1510b57cec5SDimitry Andric //// Returns the SUnit to which this edge points. 1520b57cec5SDimitry Andric SUnit *getSUnit() const; 1530b57cec5SDimitry Andric 1540b57cec5SDimitry Andric //// Assigns the SUnit to which this edge points. 1550b57cec5SDimitry Andric void setSUnit(SUnit *SU); 1560b57cec5SDimitry Andric 1570b57cec5SDimitry Andric /// Returns an enum value representing the kind of the dependence. 1580b57cec5SDimitry Andric Kind getKind() const; 1590b57cec5SDimitry Andric 1600b57cec5SDimitry Andric /// Shorthand for getKind() != SDep::Data. isCtrl()1610b57cec5SDimitry Andric bool isCtrl() const { 1620b57cec5SDimitry Andric return getKind() != Data; 1630b57cec5SDimitry Andric } 1640b57cec5SDimitry Andric 1650b57cec5SDimitry Andric /// Tests if this is an Order dependence between two memory accesses 1660b57cec5SDimitry Andric /// where both sides of the dependence access memory in non-volatile and 1670b57cec5SDimitry Andric /// fully modeled ways. isNormalMemory()1680b57cec5SDimitry Andric bool isNormalMemory() const { 1690b57cec5SDimitry Andric return getKind() == Order && (Contents.OrdKind == MayAliasMem 1700b57cec5SDimitry Andric || Contents.OrdKind == MustAliasMem); 1710b57cec5SDimitry Andric } 1720b57cec5SDimitry Andric 1730b57cec5SDimitry Andric /// Tests if this is an Order dependence that is marked as a barrier. isBarrier()1740b57cec5SDimitry Andric bool isBarrier() const { 1750b57cec5SDimitry Andric return getKind() == Order && Contents.OrdKind == Barrier; 1760b57cec5SDimitry Andric } 1770b57cec5SDimitry Andric 1780b57cec5SDimitry Andric /// Tests if this is could be any kind of memory dependence. isNormalMemoryOrBarrier()1790b57cec5SDimitry Andric bool isNormalMemoryOrBarrier() const { 1800b57cec5SDimitry Andric return (isNormalMemory() || isBarrier()); 1810b57cec5SDimitry Andric } 1820b57cec5SDimitry Andric 1830b57cec5SDimitry Andric /// Tests if this is an Order dependence that is marked as 1840b57cec5SDimitry Andric /// "must alias", meaning that the SUnits at either end of the edge have a 1850b57cec5SDimitry Andric /// memory dependence on a known memory location. isMustAlias()1860b57cec5SDimitry Andric bool isMustAlias() const { 1870b57cec5SDimitry Andric return getKind() == Order && Contents.OrdKind == MustAliasMem; 1880b57cec5SDimitry Andric } 1890b57cec5SDimitry Andric 1900b57cec5SDimitry Andric /// Tests if this a weak dependence. Weak dependencies are considered DAG 1910b57cec5SDimitry Andric /// edges for height computation and other heuristics, but do not force 1920b57cec5SDimitry Andric /// ordering. Breaking a weak edge may require the scheduler to compensate, 1930b57cec5SDimitry Andric /// for example by inserting a copy. isWeak()1940b57cec5SDimitry Andric bool isWeak() const { 1950b57cec5SDimitry Andric return getKind() == Order && Contents.OrdKind >= Weak; 1960b57cec5SDimitry Andric } 1970b57cec5SDimitry Andric 1980b57cec5SDimitry Andric /// Tests if this is an Order dependence that is marked as 1990b57cec5SDimitry Andric /// "artificial", meaning it isn't necessary for correctness. isArtificial()2000b57cec5SDimitry Andric bool isArtificial() const { 2010b57cec5SDimitry Andric return getKind() == Order && Contents.OrdKind == Artificial; 2020b57cec5SDimitry Andric } 2030b57cec5SDimitry Andric 2040b57cec5SDimitry Andric /// Tests if this is an Order dependence that is marked as "cluster", 2050b57cec5SDimitry Andric /// meaning it is artificial and wants to be adjacent. isCluster()2060b57cec5SDimitry Andric bool isCluster() const { 2070b57cec5SDimitry Andric return getKind() == Order && Contents.OrdKind == Cluster; 2080b57cec5SDimitry Andric } 2090b57cec5SDimitry Andric 2100b57cec5SDimitry Andric /// Tests if this is a Data dependence that is associated with a register. isAssignedRegDep()2110b57cec5SDimitry Andric bool isAssignedRegDep() const { 2120b57cec5SDimitry Andric return getKind() == Data && Contents.Reg != 0; 2130b57cec5SDimitry Andric } 2140b57cec5SDimitry Andric 2150b57cec5SDimitry Andric /// Returns the register associated with this edge. This is only valid on 2160b57cec5SDimitry Andric /// Data, Anti, and Output edges. On Data edges, this value may be zero, 2170b57cec5SDimitry Andric /// meaning there is no associated register. getReg()2180b57cec5SDimitry Andric unsigned getReg() const { 2190b57cec5SDimitry Andric assert((getKind() == Data || getKind() == Anti || getKind() == Output) && 2200b57cec5SDimitry Andric "getReg called on non-register dependence edge!"); 2210b57cec5SDimitry Andric return Contents.Reg; 2220b57cec5SDimitry Andric } 2230b57cec5SDimitry Andric 2240b57cec5SDimitry Andric /// Assigns the associated register for this edge. This is only valid on 2250b57cec5SDimitry Andric /// Data, Anti, and Output edges. On Anti and Output edges, this value must 2260b57cec5SDimitry Andric /// not be zero. On Data edges, the value may be zero, which would mean that 2270b57cec5SDimitry Andric /// no specific register is associated with this edge. setReg(unsigned Reg)2280b57cec5SDimitry Andric void setReg(unsigned Reg) { 2290b57cec5SDimitry Andric assert((getKind() == Data || getKind() == Anti || getKind() == Output) && 2300b57cec5SDimitry Andric "setReg called on non-register dependence edge!"); 2310b57cec5SDimitry Andric assert((getKind() != Anti || Reg != 0) && 2320b57cec5SDimitry Andric "SDep::Anti edge cannot use the zero register!"); 2330b57cec5SDimitry Andric assert((getKind() != Output || Reg != 0) && 2340b57cec5SDimitry Andric "SDep::Output edge cannot use the zero register!"); 2350b57cec5SDimitry Andric Contents.Reg = Reg; 2360b57cec5SDimitry Andric } 2370b57cec5SDimitry Andric 2380b57cec5SDimitry Andric void dump(const TargetRegisterInfo *TRI = nullptr) const; 2390b57cec5SDimitry Andric }; 2400b57cec5SDimitry Andric 2410b57cec5SDimitry Andric /// Scheduling unit. This is a node in the scheduling DAG. 2420b57cec5SDimitry Andric class SUnit { 2430b57cec5SDimitry Andric private: 2440b57cec5SDimitry Andric enum : unsigned { BoundaryID = ~0u }; 2450b57cec5SDimitry Andric 2460b57cec5SDimitry Andric SDNode *Node = nullptr; ///< Representative node. 2470b57cec5SDimitry Andric MachineInstr *Instr = nullptr; ///< Alternatively, a MachineInstr. 2480b57cec5SDimitry Andric 2490b57cec5SDimitry Andric public: 2500b57cec5SDimitry Andric SUnit *OrigNode = nullptr; ///< If not this, the node from which this node 2510b57cec5SDimitry Andric /// was cloned. (SD scheduling only) 2520b57cec5SDimitry Andric 2530b57cec5SDimitry Andric const MCSchedClassDesc *SchedClass = 2540b57cec5SDimitry Andric nullptr; ///< nullptr or resolved SchedClass. 2550b57cec5SDimitry Andric 2560b57cec5SDimitry Andric SmallVector<SDep, 4> Preds; ///< All sunit predecessors. 2570b57cec5SDimitry Andric SmallVector<SDep, 4> Succs; ///< All sunit successors. 2580b57cec5SDimitry Andric 2590b57cec5SDimitry Andric typedef SmallVectorImpl<SDep>::iterator pred_iterator; 2600b57cec5SDimitry Andric typedef SmallVectorImpl<SDep>::iterator succ_iterator; 2610b57cec5SDimitry Andric typedef SmallVectorImpl<SDep>::const_iterator const_pred_iterator; 2620b57cec5SDimitry Andric typedef SmallVectorImpl<SDep>::const_iterator const_succ_iterator; 2630b57cec5SDimitry Andric 2640b57cec5SDimitry Andric unsigned NodeNum = BoundaryID; ///< Entry # of node in the node vector. 2650b57cec5SDimitry Andric unsigned NodeQueueId = 0; ///< Queue id of node. 2660b57cec5SDimitry Andric unsigned NumPreds = 0; ///< # of SDep::Data preds. 2670b57cec5SDimitry Andric unsigned NumSuccs = 0; ///< # of SDep::Data sucss. 2680b57cec5SDimitry Andric unsigned NumPredsLeft = 0; ///< # of preds not scheduled. 2690b57cec5SDimitry Andric unsigned NumSuccsLeft = 0; ///< # of succs not scheduled. 2700b57cec5SDimitry Andric unsigned WeakPredsLeft = 0; ///< # of weak preds not scheduled. 2710b57cec5SDimitry Andric unsigned WeakSuccsLeft = 0; ///< # of weak succs not scheduled. 2720b57cec5SDimitry Andric unsigned short NumRegDefsLeft = 0; ///< # of reg defs with no scheduled use. 2730b57cec5SDimitry Andric unsigned short Latency = 0; ///< Node latency. 2740b57cec5SDimitry Andric bool isVRegCycle : 1; ///< May use and def the same vreg. 2750b57cec5SDimitry Andric bool isCall : 1; ///< Is a function call. 2760b57cec5SDimitry Andric bool isCallOp : 1; ///< Is a function call operand. 2770b57cec5SDimitry Andric bool isTwoAddress : 1; ///< Is a two-address instruction. 2780b57cec5SDimitry Andric bool isCommutable : 1; ///< Is a commutable instruction. 2790b57cec5SDimitry Andric bool hasPhysRegUses : 1; ///< Has physreg uses. 2800b57cec5SDimitry Andric bool hasPhysRegDefs : 1; ///< Has physreg defs that are being used. 2810b57cec5SDimitry Andric bool hasPhysRegClobbers : 1; ///< Has any physreg defs, used or not. 2820b57cec5SDimitry Andric bool isPending : 1; ///< True once pending. 2830b57cec5SDimitry Andric bool isAvailable : 1; ///< True once available. 2840b57cec5SDimitry Andric bool isScheduled : 1; ///< True once scheduled. 2850b57cec5SDimitry Andric bool isScheduleHigh : 1; ///< True if preferable to schedule high. 2860b57cec5SDimitry Andric bool isScheduleLow : 1; ///< True if preferable to schedule low. 2870b57cec5SDimitry Andric bool isCloned : 1; ///< True if this node has been cloned. 2880b57cec5SDimitry Andric bool isUnbuffered : 1; ///< Uses an unbuffered resource. 2890b57cec5SDimitry Andric bool hasReservedResource : 1; ///< Uses a reserved resource. 2900b57cec5SDimitry Andric Sched::Preference SchedulingPref = Sched::None; ///< Scheduling preference. 2910b57cec5SDimitry Andric 2920b57cec5SDimitry Andric private: 2930b57cec5SDimitry Andric bool isDepthCurrent : 1; ///< True if Depth is current. 2940b57cec5SDimitry Andric bool isHeightCurrent : 1; ///< True if Height is current. 2950b57cec5SDimitry Andric unsigned Depth = 0; ///< Node depth. 2960b57cec5SDimitry Andric unsigned Height = 0; ///< Node height. 2970b57cec5SDimitry Andric 2980b57cec5SDimitry Andric public: 2990b57cec5SDimitry Andric unsigned TopReadyCycle = 0; ///< Cycle relative to start when node is ready. 3000b57cec5SDimitry Andric unsigned BotReadyCycle = 0; ///< Cycle relative to end when node is ready. 3010b57cec5SDimitry Andric 3020b57cec5SDimitry Andric const TargetRegisterClass *CopyDstRC = 3030b57cec5SDimitry Andric nullptr; ///< Is a special copy node if != nullptr. 3040b57cec5SDimitry Andric const TargetRegisterClass *CopySrcRC = nullptr; 3050b57cec5SDimitry Andric 3060b57cec5SDimitry Andric /// Constructs an SUnit for pre-regalloc scheduling to represent an 3070b57cec5SDimitry Andric /// SDNode and any nodes flagged to it. SUnit(SDNode * node,unsigned nodenum)3080b57cec5SDimitry Andric SUnit(SDNode *node, unsigned nodenum) 3090b57cec5SDimitry Andric : Node(node), NodeNum(nodenum), isVRegCycle(false), isCall(false), 3100b57cec5SDimitry Andric isCallOp(false), isTwoAddress(false), isCommutable(false), 3110b57cec5SDimitry Andric hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), 3120b57cec5SDimitry Andric isPending(false), isAvailable(false), isScheduled(false), 3130b57cec5SDimitry Andric isScheduleHigh(false), isScheduleLow(false), isCloned(false), 3140b57cec5SDimitry Andric isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false), 3150b57cec5SDimitry Andric isHeightCurrent(false) {} 3160b57cec5SDimitry Andric 3170b57cec5SDimitry Andric /// Constructs an SUnit for post-regalloc scheduling to represent a 3180b57cec5SDimitry Andric /// MachineInstr. SUnit(MachineInstr * instr,unsigned nodenum)3190b57cec5SDimitry Andric SUnit(MachineInstr *instr, unsigned nodenum) 3200b57cec5SDimitry Andric : Instr(instr), NodeNum(nodenum), isVRegCycle(false), isCall(false), 3210b57cec5SDimitry Andric isCallOp(false), isTwoAddress(false), isCommutable(false), 3220b57cec5SDimitry Andric hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), 3230b57cec5SDimitry Andric isPending(false), isAvailable(false), isScheduled(false), 3240b57cec5SDimitry Andric isScheduleHigh(false), isScheduleLow(false), isCloned(false), 3250b57cec5SDimitry Andric isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false), 3260b57cec5SDimitry Andric isHeightCurrent(false) {} 3270b57cec5SDimitry Andric 3280b57cec5SDimitry Andric /// Constructs a placeholder SUnit. SUnit()3290b57cec5SDimitry Andric SUnit() 3300b57cec5SDimitry Andric : isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false), 3310b57cec5SDimitry Andric isCommutable(false), hasPhysRegUses(false), hasPhysRegDefs(false), 3320b57cec5SDimitry Andric hasPhysRegClobbers(false), isPending(false), isAvailable(false), 3330b57cec5SDimitry Andric isScheduled(false), isScheduleHigh(false), isScheduleLow(false), 3340b57cec5SDimitry Andric isCloned(false), isUnbuffered(false), hasReservedResource(false), 3350b57cec5SDimitry Andric isDepthCurrent(false), isHeightCurrent(false) {} 3360b57cec5SDimitry Andric 3370b57cec5SDimitry Andric /// Boundary nodes are placeholders for the boundary of the 3380b57cec5SDimitry Andric /// scheduling region. 3390b57cec5SDimitry Andric /// 3400b57cec5SDimitry Andric /// BoundaryNodes can have DAG edges, including Data edges, but they do not 3410b57cec5SDimitry Andric /// correspond to schedulable entities (e.g. instructions) and do not have a 3420b57cec5SDimitry Andric /// valid ID. Consequently, always check for boundary nodes before accessing 3430b57cec5SDimitry Andric /// an associative data structure keyed on node ID. isBoundaryNode()3440b57cec5SDimitry Andric bool isBoundaryNode() const { return NodeNum == BoundaryID; } 3450b57cec5SDimitry Andric 3460b57cec5SDimitry Andric /// Assigns the representative SDNode for this SUnit. This may be used 3470b57cec5SDimitry Andric /// during pre-regalloc scheduling. setNode(SDNode * N)3480b57cec5SDimitry Andric void setNode(SDNode *N) { 3490b57cec5SDimitry Andric assert(!Instr && "Setting SDNode of SUnit with MachineInstr!"); 3500b57cec5SDimitry Andric Node = N; 3510b57cec5SDimitry Andric } 3520b57cec5SDimitry Andric 3530b57cec5SDimitry Andric /// Returns the representative SDNode for this SUnit. This may be used 3540b57cec5SDimitry Andric /// during pre-regalloc scheduling. getNode()3550b57cec5SDimitry Andric SDNode *getNode() const { 3560b57cec5SDimitry Andric assert(!Instr && "Reading SDNode of SUnit with MachineInstr!"); 3570b57cec5SDimitry Andric return Node; 3580b57cec5SDimitry Andric } 3590b57cec5SDimitry Andric 3600b57cec5SDimitry Andric /// Returns true if this SUnit refers to a machine instruction as 3610b57cec5SDimitry Andric /// opposed to an SDNode. isInstr()3620b57cec5SDimitry Andric bool isInstr() const { return Instr; } 3630b57cec5SDimitry Andric 3640b57cec5SDimitry Andric /// Assigns the instruction for the SUnit. This may be used during 3650b57cec5SDimitry Andric /// post-regalloc scheduling. setInstr(MachineInstr * MI)3660b57cec5SDimitry Andric void setInstr(MachineInstr *MI) { 3670b57cec5SDimitry Andric assert(!Node && "Setting MachineInstr of SUnit with SDNode!"); 3680b57cec5SDimitry Andric Instr = MI; 3690b57cec5SDimitry Andric } 3700b57cec5SDimitry Andric 3710b57cec5SDimitry Andric /// Returns the representative MachineInstr for this SUnit. This may be used 3720b57cec5SDimitry Andric /// during post-regalloc scheduling. getInstr()3730b57cec5SDimitry Andric MachineInstr *getInstr() const { 3740b57cec5SDimitry Andric assert(!Node && "Reading MachineInstr of SUnit with SDNode!"); 3750b57cec5SDimitry Andric return Instr; 3760b57cec5SDimitry Andric } 3770b57cec5SDimitry Andric 3780b57cec5SDimitry Andric /// Adds the specified edge as a pred of the current node if not already. 3790b57cec5SDimitry Andric /// It also adds the current node as a successor of the specified node. 3800b57cec5SDimitry Andric bool addPred(const SDep &D, bool Required = true); 3810b57cec5SDimitry Andric 3820b57cec5SDimitry Andric /// Adds a barrier edge to SU by calling addPred(), with latency 0 3830b57cec5SDimitry Andric /// generally or latency 1 for a store followed by a load. addPredBarrier(SUnit * SU)3840b57cec5SDimitry Andric bool addPredBarrier(SUnit *SU) { 3850b57cec5SDimitry Andric SDep Dep(SU, SDep::Barrier); 3860b57cec5SDimitry Andric unsigned TrueMemOrderLatency = 3870b57cec5SDimitry Andric ((SU->getInstr()->mayStore() && this->getInstr()->mayLoad()) ? 1 : 0); 3880b57cec5SDimitry Andric Dep.setLatency(TrueMemOrderLatency); 3890b57cec5SDimitry Andric return addPred(Dep); 3900b57cec5SDimitry Andric } 3910b57cec5SDimitry Andric 3920b57cec5SDimitry Andric /// Removes the specified edge as a pred of the current node if it exists. 3930b57cec5SDimitry Andric /// It also removes the current node as a successor of the specified node. 3940b57cec5SDimitry Andric void removePred(const SDep &D); 3950b57cec5SDimitry Andric 3960b57cec5SDimitry Andric /// Returns the depth of this node, which is the length of the maximum path 3970b57cec5SDimitry Andric /// up to any node which has no predecessors. getDepth()3980b57cec5SDimitry Andric unsigned getDepth() const { 3990b57cec5SDimitry Andric if (!isDepthCurrent) 4000b57cec5SDimitry Andric const_cast<SUnit *>(this)->ComputeDepth(); 4010b57cec5SDimitry Andric return Depth; 4020b57cec5SDimitry Andric } 4030b57cec5SDimitry Andric 4040b57cec5SDimitry Andric /// Returns the height of this node, which is the length of the 4050b57cec5SDimitry Andric /// maximum path down to any node which has no successors. getHeight()4060b57cec5SDimitry Andric unsigned getHeight() const { 4070b57cec5SDimitry Andric if (!isHeightCurrent) 4080b57cec5SDimitry Andric const_cast<SUnit *>(this)->ComputeHeight(); 4090b57cec5SDimitry Andric return Height; 4100b57cec5SDimitry Andric } 4110b57cec5SDimitry Andric 4120b57cec5SDimitry Andric /// If NewDepth is greater than this node's depth value, sets it to 4130b57cec5SDimitry Andric /// be the new depth value. This also recursively marks successor nodes 4140b57cec5SDimitry Andric /// dirty. 4150b57cec5SDimitry Andric void setDepthToAtLeast(unsigned NewDepth); 4160b57cec5SDimitry Andric 4170b57cec5SDimitry Andric /// If NewHeight is greater than this node's height value, set it to be 4180b57cec5SDimitry Andric /// the new height value. This also recursively marks predecessor nodes 4190b57cec5SDimitry Andric /// dirty. 4200b57cec5SDimitry Andric void setHeightToAtLeast(unsigned NewHeight); 4210b57cec5SDimitry Andric 4220b57cec5SDimitry Andric /// Sets a flag in this node to indicate that its stored Depth value 4230b57cec5SDimitry Andric /// will require recomputation the next time getDepth() is called. 4240b57cec5SDimitry Andric void setDepthDirty(); 4250b57cec5SDimitry Andric 4260b57cec5SDimitry Andric /// Sets a flag in this node to indicate that its stored Height value 4270b57cec5SDimitry Andric /// will require recomputation the next time getHeight() is called. 4280b57cec5SDimitry Andric void setHeightDirty(); 4290b57cec5SDimitry Andric 4300b57cec5SDimitry Andric /// Tests if node N is a predecessor of this node. isPred(const SUnit * N)4310b57cec5SDimitry Andric bool isPred(const SUnit *N) const { 4320b57cec5SDimitry Andric for (const SDep &Pred : Preds) 4330b57cec5SDimitry Andric if (Pred.getSUnit() == N) 4340b57cec5SDimitry Andric return true; 4350b57cec5SDimitry Andric return false; 4360b57cec5SDimitry Andric } 4370b57cec5SDimitry Andric 4380b57cec5SDimitry Andric /// Tests if node N is a successor of this node. isSucc(const SUnit * N)4390b57cec5SDimitry Andric bool isSucc(const SUnit *N) const { 4400b57cec5SDimitry Andric for (const SDep &Succ : Succs) 4410b57cec5SDimitry Andric if (Succ.getSUnit() == N) 4420b57cec5SDimitry Andric return true; 4430b57cec5SDimitry Andric return false; 4440b57cec5SDimitry Andric } 4450b57cec5SDimitry Andric isTopReady()4460b57cec5SDimitry Andric bool isTopReady() const { 4470b57cec5SDimitry Andric return NumPredsLeft == 0; 4480b57cec5SDimitry Andric } isBottomReady()4490b57cec5SDimitry Andric bool isBottomReady() const { 4500b57cec5SDimitry Andric return NumSuccsLeft == 0; 4510b57cec5SDimitry Andric } 4520b57cec5SDimitry Andric 4530b57cec5SDimitry Andric /// Orders this node's predecessor edges such that the critical path 4540b57cec5SDimitry Andric /// edge occurs first. 4550b57cec5SDimitry Andric void biasCriticalPath(); 4560b57cec5SDimitry Andric 4570b57cec5SDimitry Andric void dumpAttributes() const; 4580b57cec5SDimitry Andric 4590b57cec5SDimitry Andric private: 4600b57cec5SDimitry Andric void ComputeDepth(); 4610b57cec5SDimitry Andric void ComputeHeight(); 4620b57cec5SDimitry Andric }; 4630b57cec5SDimitry Andric 4640b57cec5SDimitry Andric /// Returns true if the specified SDep is equivalent except for latency. overlaps(const SDep & Other)4650b57cec5SDimitry Andric inline bool SDep::overlaps(const SDep &Other) const { 4660b57cec5SDimitry Andric if (Dep != Other.Dep) 4670b57cec5SDimitry Andric return false; 4680b57cec5SDimitry Andric switch (Dep.getInt()) { 4690b57cec5SDimitry Andric case Data: 4700b57cec5SDimitry Andric case Anti: 4710b57cec5SDimitry Andric case Output: 4720b57cec5SDimitry Andric return Contents.Reg == Other.Contents.Reg; 4730b57cec5SDimitry Andric case Order: 4740b57cec5SDimitry Andric return Contents.OrdKind == Other.Contents.OrdKind; 4750b57cec5SDimitry Andric } 4760b57cec5SDimitry Andric llvm_unreachable("Invalid dependency kind!"); 4770b57cec5SDimitry Andric } 4780b57cec5SDimitry Andric 4790b57cec5SDimitry Andric //// Returns the SUnit to which this edge points. getSUnit()4800b57cec5SDimitry Andric inline SUnit *SDep::getSUnit() const { return Dep.getPointer(); } 4810b57cec5SDimitry Andric 4820b57cec5SDimitry Andric //// Assigns the SUnit to which this edge points. setSUnit(SUnit * SU)4830b57cec5SDimitry Andric inline void SDep::setSUnit(SUnit *SU) { Dep.setPointer(SU); } 4840b57cec5SDimitry Andric 4850b57cec5SDimitry Andric /// Returns an enum value representing the kind of the dependence. getKind()4860b57cec5SDimitry Andric inline SDep::Kind SDep::getKind() const { return Dep.getInt(); } 4870b57cec5SDimitry Andric 4880b57cec5SDimitry Andric //===--------------------------------------------------------------------===// 4890b57cec5SDimitry Andric 4900b57cec5SDimitry Andric /// This interface is used to plug different priorities computation 4910b57cec5SDimitry Andric /// algorithms into the list scheduler. It implements the interface of a 4920b57cec5SDimitry Andric /// standard priority queue, where nodes are inserted in arbitrary order and 4930b57cec5SDimitry Andric /// returned in priority order. The computation of the priority and the 4940b57cec5SDimitry Andric /// representation of the queue are totally up to the implementation to 4950b57cec5SDimitry Andric /// decide. 4960b57cec5SDimitry Andric class SchedulingPriorityQueue { 4970b57cec5SDimitry Andric virtual void anchor(); 4980b57cec5SDimitry Andric 4990b57cec5SDimitry Andric unsigned CurCycle = 0; 5000b57cec5SDimitry Andric bool HasReadyFilter; 5010b57cec5SDimitry Andric 5020b57cec5SDimitry Andric public: HasReadyFilter(rf)5030b57cec5SDimitry Andric SchedulingPriorityQueue(bool rf = false) : HasReadyFilter(rf) {} 5040b57cec5SDimitry Andric 5050b57cec5SDimitry Andric virtual ~SchedulingPriorityQueue() = default; 5060b57cec5SDimitry Andric 5070b57cec5SDimitry Andric virtual bool isBottomUp() const = 0; 5080b57cec5SDimitry Andric 5090b57cec5SDimitry Andric virtual void initNodes(std::vector<SUnit> &SUnits) = 0; 5100b57cec5SDimitry Andric virtual void addNode(const SUnit *SU) = 0; 5110b57cec5SDimitry Andric virtual void updateNode(const SUnit *SU) = 0; 5120b57cec5SDimitry Andric virtual void releaseState() = 0; 5130b57cec5SDimitry Andric 5140b57cec5SDimitry Andric virtual bool empty() const = 0; 5150b57cec5SDimitry Andric hasReadyFilter()5160b57cec5SDimitry Andric bool hasReadyFilter() const { return HasReadyFilter; } 5170b57cec5SDimitry Andric tracksRegPressure()5180b57cec5SDimitry Andric virtual bool tracksRegPressure() const { return false; } 5190b57cec5SDimitry Andric isReady(SUnit *)5200b57cec5SDimitry Andric virtual bool isReady(SUnit *) const { 5210b57cec5SDimitry Andric assert(!HasReadyFilter && "The ready filter must override isReady()"); 5220b57cec5SDimitry Andric return true; 5230b57cec5SDimitry Andric } 5240b57cec5SDimitry Andric 5250b57cec5SDimitry Andric virtual void push(SUnit *U) = 0; 5260b57cec5SDimitry Andric push_all(const std::vector<SUnit * > & Nodes)5270b57cec5SDimitry Andric void push_all(const std::vector<SUnit *> &Nodes) { 528fcaf7f86SDimitry Andric for (SUnit *SU : Nodes) 529fcaf7f86SDimitry Andric push(SU); 5300b57cec5SDimitry Andric } 5310b57cec5SDimitry Andric 5320b57cec5SDimitry Andric virtual SUnit *pop() = 0; 5330b57cec5SDimitry Andric 5340b57cec5SDimitry Andric virtual void remove(SUnit *SU) = 0; 5350b57cec5SDimitry Andric dump(ScheduleDAG *)5360b57cec5SDimitry Andric virtual void dump(ScheduleDAG *) const {} 5370b57cec5SDimitry Andric 5380b57cec5SDimitry Andric /// As each node is scheduled, this method is invoked. This allows the 5390b57cec5SDimitry Andric /// priority function to adjust the priority of related unscheduled nodes, 5400b57cec5SDimitry Andric /// for example. scheduledNode(SUnit *)5410b57cec5SDimitry Andric virtual void scheduledNode(SUnit *) {} 5420b57cec5SDimitry Andric unscheduledNode(SUnit *)5430b57cec5SDimitry Andric virtual void unscheduledNode(SUnit *) {} 5440b57cec5SDimitry Andric setCurCycle(unsigned Cycle)5450b57cec5SDimitry Andric void setCurCycle(unsigned Cycle) { 5460b57cec5SDimitry Andric CurCycle = Cycle; 5470b57cec5SDimitry Andric } 5480b57cec5SDimitry Andric getCurCycle()5490b57cec5SDimitry Andric unsigned getCurCycle() const { 5500b57cec5SDimitry Andric return CurCycle; 5510b57cec5SDimitry Andric } 5520b57cec5SDimitry Andric }; 5530b57cec5SDimitry Andric 5540b57cec5SDimitry Andric class ScheduleDAG { 5550b57cec5SDimitry Andric public: 5560b57cec5SDimitry Andric const LLVMTargetMachine &TM; ///< Target processor 5570b57cec5SDimitry Andric const TargetInstrInfo *TII; ///< Target instruction information 5580b57cec5SDimitry Andric const TargetRegisterInfo *TRI; ///< Target processor register info 5590b57cec5SDimitry Andric MachineFunction &MF; ///< Machine function 5600b57cec5SDimitry Andric MachineRegisterInfo &MRI; ///< Virtual/real register map 5610b57cec5SDimitry Andric std::vector<SUnit> SUnits; ///< The scheduling units. 5620b57cec5SDimitry Andric SUnit EntrySU; ///< Special node for the region entry. 5630b57cec5SDimitry Andric SUnit ExitSU; ///< Special node for the region exit. 5640b57cec5SDimitry Andric 5650b57cec5SDimitry Andric #ifdef NDEBUG 5660b57cec5SDimitry Andric static const bool StressSched = false; 5670b57cec5SDimitry Andric #else 5680b57cec5SDimitry Andric bool StressSched; 5690b57cec5SDimitry Andric #endif 5700b57cec5SDimitry Andric 57106c3fb27SDimitry Andric // This class is designed to be passed by reference only. Copy constructor 57206c3fb27SDimitry Andric // is declared as deleted here to make the derived classes have deleted 57306c3fb27SDimitry Andric // implicit-declared copy constructor, which suppresses the warnings from 57406c3fb27SDimitry Andric // static analyzer when the derived classes own resources that are freed in 57506c3fb27SDimitry Andric // their destructors, but don't have user-written copy constructors (rule 57606c3fb27SDimitry Andric // of three). 57706c3fb27SDimitry Andric ScheduleDAG(const ScheduleDAG &) = delete; 57806c3fb27SDimitry Andric ScheduleDAG &operator=(const ScheduleDAG &) = delete; 57906c3fb27SDimitry Andric 5800b57cec5SDimitry Andric explicit ScheduleDAG(MachineFunction &mf); 5810b57cec5SDimitry Andric 5820b57cec5SDimitry Andric virtual ~ScheduleDAG(); 5830b57cec5SDimitry Andric 5840b57cec5SDimitry Andric /// Clears the DAG state (between regions). 5850b57cec5SDimitry Andric void clearDAG(); 5860b57cec5SDimitry Andric 5870b57cec5SDimitry Andric /// Returns the MCInstrDesc of this SUnit. 5880b57cec5SDimitry Andric /// Returns NULL for SDNodes without a machine opcode. getInstrDesc(const SUnit * SU)5890b57cec5SDimitry Andric const MCInstrDesc *getInstrDesc(const SUnit *SU) const { 5900b57cec5SDimitry Andric if (SU->isInstr()) return &SU->getInstr()->getDesc(); 5910b57cec5SDimitry Andric return getNodeDesc(SU->getNode()); 5920b57cec5SDimitry Andric } 5930b57cec5SDimitry Andric 5940b57cec5SDimitry Andric /// Pops up a GraphViz/gv window with the ScheduleDAG rendered using 'dot'. 5950b57cec5SDimitry Andric virtual void viewGraph(const Twine &Name, const Twine &Title); 5960b57cec5SDimitry Andric virtual void viewGraph(); 5970b57cec5SDimitry Andric 5980b57cec5SDimitry Andric virtual void dumpNode(const SUnit &SU) const = 0; 5990b57cec5SDimitry Andric virtual void dump() const = 0; 6000b57cec5SDimitry Andric void dumpNodeName(const SUnit &SU) const; 6010b57cec5SDimitry Andric 6020b57cec5SDimitry Andric /// Returns a label for an SUnit node in a visualization of the ScheduleDAG. 6030b57cec5SDimitry Andric virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0; 6040b57cec5SDimitry Andric 6050b57cec5SDimitry Andric /// Returns a label for the region of code covered by the DAG. 6060b57cec5SDimitry Andric virtual std::string getDAGName() const = 0; 6070b57cec5SDimitry Andric 6080b57cec5SDimitry Andric /// Adds custom features for a visualization of the ScheduleDAG. addCustomGraphFeatures(GraphWriter<ScheduleDAG * > &)6090b57cec5SDimitry Andric virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {} 6100b57cec5SDimitry Andric 6110b57cec5SDimitry Andric #ifndef NDEBUG 6120b57cec5SDimitry Andric /// Verifies that all SUnits were scheduled and that their state is 6130b57cec5SDimitry Andric /// consistent. Returns the number of scheduled SUnits. 6140b57cec5SDimitry Andric unsigned VerifyScheduledDAG(bool isBottomUp); 6150b57cec5SDimitry Andric #endif 6160b57cec5SDimitry Andric 6170b57cec5SDimitry Andric protected: 6180b57cec5SDimitry Andric void dumpNodeAll(const SUnit &SU) const; 6190b57cec5SDimitry Andric 6200b57cec5SDimitry Andric private: 6210b57cec5SDimitry Andric /// Returns the MCInstrDesc of this SDNode or NULL. 6220b57cec5SDimitry Andric const MCInstrDesc *getNodeDesc(const SDNode *Node) const; 6230b57cec5SDimitry Andric }; 6240b57cec5SDimitry Andric 625fe6060f1SDimitry Andric class SUnitIterator { 6260b57cec5SDimitry Andric SUnit *Node; 6270b57cec5SDimitry Andric unsigned Operand; 6280b57cec5SDimitry Andric SUnitIterator(SUnit * N,unsigned Op)6290b57cec5SDimitry Andric SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {} 6300b57cec5SDimitry Andric 6310b57cec5SDimitry Andric public: 632fe6060f1SDimitry Andric using iterator_category = std::forward_iterator_tag; 633fe6060f1SDimitry Andric using value_type = SUnit; 634fe6060f1SDimitry Andric using difference_type = std::ptrdiff_t; 635fe6060f1SDimitry Andric using pointer = value_type *; 636fe6060f1SDimitry Andric using reference = value_type &; 637fe6060f1SDimitry Andric 6380b57cec5SDimitry Andric bool operator==(const SUnitIterator& x) const { 6390b57cec5SDimitry Andric return Operand == x.Operand; 6400b57cec5SDimitry Andric } 6410b57cec5SDimitry Andric bool operator!=(const SUnitIterator& x) const { return !operator==(x); } 6420b57cec5SDimitry Andric 6430b57cec5SDimitry Andric pointer operator*() const { 6440b57cec5SDimitry Andric return Node->Preds[Operand].getSUnit(); 6450b57cec5SDimitry Andric } 6460b57cec5SDimitry Andric pointer operator->() const { return operator*(); } 6470b57cec5SDimitry Andric 6480b57cec5SDimitry Andric SUnitIterator& operator++() { // Preincrement 6490b57cec5SDimitry Andric ++Operand; 6500b57cec5SDimitry Andric return *this; 6510b57cec5SDimitry Andric } 6520b57cec5SDimitry Andric SUnitIterator operator++(int) { // Postincrement 6530b57cec5SDimitry Andric SUnitIterator tmp = *this; ++*this; return tmp; 6540b57cec5SDimitry Andric } 6550b57cec5SDimitry Andric begin(SUnit * N)6560b57cec5SDimitry Andric static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); } end(SUnit * N)6570b57cec5SDimitry Andric static SUnitIterator end (SUnit *N) { 6580b57cec5SDimitry Andric return SUnitIterator(N, (unsigned)N->Preds.size()); 6590b57cec5SDimitry Andric } 6600b57cec5SDimitry Andric getOperand()6610b57cec5SDimitry Andric unsigned getOperand() const { return Operand; } getNode()6620b57cec5SDimitry Andric const SUnit *getNode() const { return Node; } 6630b57cec5SDimitry Andric 6640b57cec5SDimitry Andric /// Tests if this is not an SDep::Data dependence. isCtrlDep()6650b57cec5SDimitry Andric bool isCtrlDep() const { 6660b57cec5SDimitry Andric return getSDep().isCtrl(); 6670b57cec5SDimitry Andric } isArtificialDep()6680b57cec5SDimitry Andric bool isArtificialDep() const { 6690b57cec5SDimitry Andric return getSDep().isArtificial(); 6700b57cec5SDimitry Andric } getSDep()6710b57cec5SDimitry Andric const SDep &getSDep() const { 6720b57cec5SDimitry Andric return Node->Preds[Operand]; 6730b57cec5SDimitry Andric } 6740b57cec5SDimitry Andric }; 6750b57cec5SDimitry Andric 6760b57cec5SDimitry Andric template <> struct GraphTraits<SUnit*> { 6770b57cec5SDimitry Andric typedef SUnit *NodeRef; 6780b57cec5SDimitry Andric typedef SUnitIterator ChildIteratorType; 6790b57cec5SDimitry Andric static NodeRef getEntryNode(SUnit *N) { return N; } 6800b57cec5SDimitry Andric static ChildIteratorType child_begin(NodeRef N) { 6810b57cec5SDimitry Andric return SUnitIterator::begin(N); 6820b57cec5SDimitry Andric } 6830b57cec5SDimitry Andric static ChildIteratorType child_end(NodeRef N) { 6840b57cec5SDimitry Andric return SUnitIterator::end(N); 6850b57cec5SDimitry Andric } 6860b57cec5SDimitry Andric }; 6870b57cec5SDimitry Andric 6880b57cec5SDimitry Andric template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> { 6890b57cec5SDimitry Andric typedef pointer_iterator<std::vector<SUnit>::iterator> nodes_iterator; 6900b57cec5SDimitry Andric static nodes_iterator nodes_begin(ScheduleDAG *G) { 6910b57cec5SDimitry Andric return nodes_iterator(G->SUnits.begin()); 6920b57cec5SDimitry Andric } 6930b57cec5SDimitry Andric static nodes_iterator nodes_end(ScheduleDAG *G) { 6940b57cec5SDimitry Andric return nodes_iterator(G->SUnits.end()); 6950b57cec5SDimitry Andric } 6960b57cec5SDimitry Andric }; 6970b57cec5SDimitry Andric 6980b57cec5SDimitry Andric /// This class can compute a topological ordering for SUnits and provides 6990b57cec5SDimitry Andric /// methods for dynamically updating the ordering as new edges are added. 7000b57cec5SDimitry Andric /// 7010b57cec5SDimitry Andric /// This allows a very fast implementation of IsReachable, for example. 7020b57cec5SDimitry Andric class ScheduleDAGTopologicalSort { 7030b57cec5SDimitry Andric /// A reference to the ScheduleDAG's SUnits. 7040b57cec5SDimitry Andric std::vector<SUnit> &SUnits; 7050b57cec5SDimitry Andric SUnit *ExitSU; 7060b57cec5SDimitry Andric 7070b57cec5SDimitry Andric // Have any new nodes been added? 7080b57cec5SDimitry Andric bool Dirty = false; 7090b57cec5SDimitry Andric 7100b57cec5SDimitry Andric // Outstanding added edges, that have not been applied to the ordering. 7110b57cec5SDimitry Andric SmallVector<std::pair<SUnit *, SUnit *>, 16> Updates; 7120b57cec5SDimitry Andric 7130b57cec5SDimitry Andric /// Maps topological index to the node number. 7140b57cec5SDimitry Andric std::vector<int> Index2Node; 7150b57cec5SDimitry Andric /// Maps the node number to its topological index. 7160b57cec5SDimitry Andric std::vector<int> Node2Index; 7170b57cec5SDimitry Andric /// a set of nodes visited during a DFS traversal. 7180b57cec5SDimitry Andric BitVector Visited; 7190b57cec5SDimitry Andric 7200b57cec5SDimitry Andric /// Makes a DFS traversal and mark all nodes affected by the edge insertion. 7210b57cec5SDimitry Andric /// These nodes will later get new topological indexes by means of the Shift 7220b57cec5SDimitry Andric /// method. 7230b57cec5SDimitry Andric void DFS(const SUnit *SU, int UpperBound, bool& HasLoop); 7240b57cec5SDimitry Andric 7250b57cec5SDimitry Andric /// Reassigns topological indexes for the nodes in the DAG to 7260b57cec5SDimitry Andric /// preserve the topological ordering. 7270b57cec5SDimitry Andric void Shift(BitVector& Visited, int LowerBound, int UpperBound); 7280b57cec5SDimitry Andric 7290b57cec5SDimitry Andric /// Assigns the topological index to the node n. 7300b57cec5SDimitry Andric void Allocate(int n, int index); 7310b57cec5SDimitry Andric 7320b57cec5SDimitry Andric /// Fix the ordering, by either recomputing from scratch or by applying 7330b57cec5SDimitry Andric /// any outstanding updates. Uses a heuristic to estimate what will be 7340b57cec5SDimitry Andric /// cheaper. 7350b57cec5SDimitry Andric void FixOrder(); 7360b57cec5SDimitry Andric 7370b57cec5SDimitry Andric public: 7380b57cec5SDimitry Andric ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU); 7390b57cec5SDimitry Andric 7405ffd83dbSDimitry Andric /// Add a SUnit without predecessors to the end of the topological order. It 7415ffd83dbSDimitry Andric /// also must be the first new node added to the DAG. 7425ffd83dbSDimitry Andric void AddSUnitWithoutPredecessors(const SUnit *SU); 7435ffd83dbSDimitry Andric 7440b57cec5SDimitry Andric /// Creates the initial topological ordering from the DAG to be scheduled. 7450b57cec5SDimitry Andric void InitDAGTopologicalSorting(); 7460b57cec5SDimitry Andric 7470b57cec5SDimitry Andric /// Returns an array of SUs that are both in the successor 7480b57cec5SDimitry Andric /// subtree of StartSU and in the predecessor subtree of TargetSU. 7490b57cec5SDimitry Andric /// StartSU and TargetSU are not in the array. 7500b57cec5SDimitry Andric /// Success is false if TargetSU is not in the successor subtree of 7510b57cec5SDimitry Andric /// StartSU, else it is true. 7520b57cec5SDimitry Andric std::vector<int> GetSubGraph(const SUnit &StartSU, const SUnit &TargetSU, 7530b57cec5SDimitry Andric bool &Success); 7540b57cec5SDimitry Andric 7550b57cec5SDimitry Andric /// Checks if \p SU is reachable from \p TargetSU. 7560b57cec5SDimitry Andric bool IsReachable(const SUnit *SU, const SUnit *TargetSU); 7570b57cec5SDimitry Andric 7580b57cec5SDimitry Andric /// Returns true if addPred(TargetSU, SU) creates a cycle. 7590b57cec5SDimitry Andric bool WillCreateCycle(SUnit *TargetSU, SUnit *SU); 7600b57cec5SDimitry Andric 7610b57cec5SDimitry Andric /// Updates the topological ordering to accommodate an edge to be 7620b57cec5SDimitry Andric /// added from SUnit \p X to SUnit \p Y. 7630b57cec5SDimitry Andric void AddPred(SUnit *Y, SUnit *X); 7640b57cec5SDimitry Andric 7650b57cec5SDimitry Andric /// Queues an update to the topological ordering to accommodate an edge to 7660b57cec5SDimitry Andric /// be added from SUnit \p X to SUnit \p Y. 7670b57cec5SDimitry Andric void AddPredQueued(SUnit *Y, SUnit *X); 7680b57cec5SDimitry Andric 7695f757f3fSDimitry Andric /// Updates the topological ordering to accommodate an edge to be 7700b57cec5SDimitry Andric /// removed from the specified node \p N from the predecessors of the 7710b57cec5SDimitry Andric /// current node \p M. 7720b57cec5SDimitry Andric void RemovePred(SUnit *M, SUnit *N); 7730b57cec5SDimitry Andric 7740b57cec5SDimitry Andric /// Mark the ordering as temporarily broken, after a new node has been 7750b57cec5SDimitry Andric /// added. 7760b57cec5SDimitry Andric void MarkDirty() { Dirty = true; } 7770b57cec5SDimitry Andric 7780b57cec5SDimitry Andric typedef std::vector<int>::iterator iterator; 7790b57cec5SDimitry Andric typedef std::vector<int>::const_iterator const_iterator; 7800b57cec5SDimitry Andric iterator begin() { return Index2Node.begin(); } 7810b57cec5SDimitry Andric const_iterator begin() const { return Index2Node.begin(); } 7820b57cec5SDimitry Andric iterator end() { return Index2Node.end(); } 7830b57cec5SDimitry Andric const_iterator end() const { return Index2Node.end(); } 7840b57cec5SDimitry Andric 7850b57cec5SDimitry Andric typedef std::vector<int>::reverse_iterator reverse_iterator; 7860b57cec5SDimitry Andric typedef std::vector<int>::const_reverse_iterator const_reverse_iterator; 7870b57cec5SDimitry Andric reverse_iterator rbegin() { return Index2Node.rbegin(); } 7880b57cec5SDimitry Andric const_reverse_iterator rbegin() const { return Index2Node.rbegin(); } 7890b57cec5SDimitry Andric reverse_iterator rend() { return Index2Node.rend(); } 7900b57cec5SDimitry Andric const_reverse_iterator rend() const { return Index2Node.rend(); } 7910b57cec5SDimitry Andric }; 7920b57cec5SDimitry Andric 7930b57cec5SDimitry Andric } // end namespace llvm 7940b57cec5SDimitry Andric 7950b57cec5SDimitry Andric #endif // LLVM_CODEGEN_SCHEDULEDAG_H 796