LCOV - code coverage report
Current view: top level - include/llvm/CodeGen - ScheduleDAG.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 68 76 89.5 %
Date: 2017-09-14 15:23:50 Functions: 10 18 55.6 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- llvm/CodeGen/ScheduleDAG.h - Common Base Class -----------*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : /// \file Implements the ScheduleDAG class, which is used as the common base
      11             : /// class for instruction schedulers. This encapsulates the scheduling DAG,
      12             : /// which is shared between SelectionDAG and MachineInstr scheduling.
      13             : //
      14             : //===----------------------------------------------------------------------===//
      15             : 
      16             : #ifndef LLVM_CODEGEN_SCHEDULEDAG_H
      17             : #define LLVM_CODEGEN_SCHEDULEDAG_H
      18             : 
      19             : #include "llvm/ADT/BitVector.h"
      20             : #include "llvm/ADT/GraphTraits.h"
      21             : #include "llvm/ADT/PointerIntPair.h"
      22             : #include "llvm/ADT/SmallVector.h"
      23             : #include "llvm/ADT/iterator.h"
      24             : #include "llvm/CodeGen/MachineInstr.h"
      25             : #include "llvm/Support/ErrorHandling.h"
      26             : #include "llvm/Target/TargetLowering.h"
      27             : #include <cassert>
      28             : #include <cstddef>
      29             : #include <iterator>
      30             : #include <string>
      31             : #include <vector>
      32             : 
      33             : namespace llvm {
      34             : 
      35             : template<class Graph> class GraphWriter;
      36             : class MachineFunction;
      37             : class MachineRegisterInfo;
      38             : class MCInstrDesc;
      39             : struct MCSchedClassDesc;
      40             : class ScheduleDAG;
      41             : class SDNode;
      42             : class SUnit;
      43             : class TargetInstrInfo;
      44             : class TargetMachine;
      45             : class TargetRegisterClass;
      46             : class TargetRegisterInfo;
      47             : 
      48             :   /// Scheduling dependency. This represents one direction of an edge in the
      49             :   /// scheduling DAG.
      50             :   class SDep {
      51             :   public:
      52             :     /// These are the different kinds of scheduling dependencies.
      53             :     enum Kind {
      54             :       Data,        ///< Regular data dependence (aka true-dependence).
      55             :       Anti,        ///< A register anti-dependence (aka WAR).
      56             :       Output,      ///< A register output-dependence (aka WAW).
      57             :       Order        ///< Any other ordering dependency.
      58             :     };
      59             : 
      60             :     // Strong dependencies must be respected by the scheduler. Artificial
      61             :     // dependencies may be removed only if they are redundant with another
      62             :     // strong dependence.
      63             :     //
      64             :     // Weak dependencies may be violated by the scheduling strategy, but only if
      65             :     // the strategy can prove it is correct to do so.
      66             :     //
      67             :     // Strong OrderKinds must occur before "Weak".
      68             :     // Weak OrderKinds must occur after "Weak".
      69             :     enum OrderKind {
      70             :       Barrier,      ///< An unknown scheduling barrier.
      71             :       MayAliasMem,  ///< Nonvolatile load/Store instructions that may alias.
      72             :       MustAliasMem, ///< Nonvolatile load/Store instructions that must alias.
      73             :       Artificial,   ///< Arbitrary strong DAG edge (no real dependence).
      74             :       Weak,         ///< Arbitrary weak DAG edge.
      75             :       Cluster       ///< Weak DAG edge linking a chain of clustered instrs.
      76             :     };
      77             : 
      78             :   private:
      79             :     /// \brief A pointer to the depending/depended-on SUnit, and an enum
      80             :     /// indicating the kind of the dependency.
      81             :     PointerIntPair<SUnit *, 2, Kind> Dep;
      82             : 
      83             :     /// A union discriminated by the dependence kind.
      84             :     union {
      85             :       /// For Data, Anti, and Output dependencies, the associated register. For
      86             :       /// Data dependencies that don't currently have a register/ assigned, this
      87             :       /// is set to zero.
      88             :       unsigned Reg;
      89             : 
      90             :       /// Additional information about Order dependencies.
      91             :       unsigned OrdKind; // enum OrderKind
      92             :     } Contents;
      93             : 
      94             :     /// The time associated with this edge. Often this is just the value of the
      95             :     /// Latency field of the predecessor, however advanced models may provide
      96             :     /// additional information about specific edges.
      97             :     unsigned Latency;
      98             : 
      99             :   public:
     100             :     /// Constructs a null SDep. This is only for use by container classes which
     101             :     /// require default constructors. SUnits may not/ have null SDep edges.
     102     4293894 :     SDep() : Dep(nullptr, Data) {}
     103             : 
     104             :     /// Constructs an SDep with the specified values.
     105             :     SDep(SUnit *S, Kind kind, unsigned Reg)
     106    14152262 :       : Dep(S, kind), Contents() {
     107             :       switch (kind) {
     108             :       default:
     109             :         llvm_unreachable("Reg given for non-register dependence!");
     110             :       case Anti:
     111             :       case Output:
     112             :         assert(Reg != 0 &&
     113             :                "SDep::Anti and SDep::Output must use a non-zero Reg!");
     114     1688937 :         Contents.Reg = Reg;
     115     1688541 :         Latency = 0;
     116             :         break;
     117             :       case Data:
     118     4050717 :         Contents.Reg = Reg;
     119     1421278 :         Latency = 1;
     120             :         break;
     121             :       }
     122             :     }
     123             : 
     124             :     SDep(SUnit *S, OrderKind kind)
     125    10576276 :       : Dep(S, Order), Contents(), Latency(0) {
     126     4471360 :       Contents.OrdKind = kind;
     127             :     }
     128             : 
     129             :     /// Returns true if the specified SDep is equivalent except for latency.
     130             :     bool overlaps(const SDep &Other) const;
     131             : 
     132      339887 :     bool operator==(const SDep &Other) const {
     133      100736 :       return overlaps(Other) && Latency == Other.Latency;
     134             :     }
     135             : 
     136             :     bool operator!=(const SDep &Other) const {
     137             :       return !operator==(Other);
     138             :     }
     139             : 
     140             :     /// \brief Returns the latency value for this edge, which roughly means the
     141             :     /// minimum number of cycles that must elapse between the predecessor and
     142             :     /// the successor, given that they have this edge between them.
     143             :     unsigned getLatency() const {
     144             :       return Latency;
     145             :     }
     146             : 
     147             :     /// Sets the latency for this edge.
     148             :     void setLatency(unsigned Lat) {
     149    11852022 :       Latency = Lat;
     150             :     }
     151             : 
     152             :     //// Returns the SUnit to which this edge points.
     153             :     SUnit *getSUnit() const;
     154             : 
     155             :     //// Assigns the SUnit to which this edge points.
     156             :     void setSUnit(SUnit *SU);
     157             : 
     158             :     /// Returns an enum value representing the kind of the dependence.
     159             :     Kind getKind() const;
     160             : 
     161             :     /// Shorthand for getKind() != SDep::Data.
     162             :     bool isCtrl() const {
     163    48428927 :       return getKind() != Data;
     164             :     }
     165             : 
     166             :     /// \brief Tests if this is an Order dependence between two memory accesses
     167             :     /// where both sides of the dependence access memory in non-volatile and
     168             :     /// fully modeled ways.
     169             :     bool isNormalMemory() const {
     170        6446 :       return getKind() == Order && (Contents.OrdKind == MayAliasMem
     171        2341 :                                     || Contents.OrdKind == MustAliasMem);
     172             :     }
     173             : 
     174             :     /// Tests if this is an Order dependence that is marked as a barrier.
     175             :     bool isBarrier() const {
     176        2189 :       return getKind() == Order && Contents.OrdKind == Barrier;
     177             :     }
     178             : 
     179             :     /// Tests if this is could be any kind of memory dependence.
     180             :     bool isNormalMemoryOrBarrier() const {
     181             :       return (isNormalMemory() || isBarrier());
     182             :     }
     183             : 
     184             :     /// \brief Tests if this is an Order dependence that is marked as
     185             :     /// "must alias", meaning that the SUnits at either end of the edge have a
     186             :     /// memory dependence on a known memory location.
     187             :     bool isMustAlias() const {
     188             :       return getKind() == Order && Contents.OrdKind == MustAliasMem;
     189             :     }
     190             : 
     191             :     /// Tests if this a weak dependence. Weak dependencies are considered DAG
     192             :     /// edges for height computation and other heuristics, but do not force
     193             :     /// ordering. Breaking a weak edge may require the scheduler to compensate,
     194             :     /// for example by inserting a copy.
     195             :     bool isWeak() const {
     196    27604703 :       return getKind() == Order && Contents.OrdKind >= Weak;
     197             :     }
     198             : 
     199             :     /// \brief Tests if this is an Order dependence that is marked as
     200             :     /// "artificial", meaning it isn't necessary for correctness.
     201             :     bool isArtificial() const {
     202      231168 :       return getKind() == Order && Contents.OrdKind == Artificial;
     203             :     }
     204             : 
     205             :     /// \brief Tests if this is an Order dependence that is marked as "cluster",
     206             :     /// meaning it is artificial and wants to be adjacent.
     207             :     bool isCluster() const {
     208       73290 :       return getKind() == Order && Contents.OrdKind == Cluster;
     209             :     }
     210             : 
     211             :     /// Tests if this is a Data dependence that is associated with a register.
     212             :     bool isAssignedRegDep() const {
     213    10790333 :       return getKind() == Data && Contents.Reg != 0;
     214             :     }
     215             : 
     216             :     /// Returns the register associated with this edge. This is only valid on
     217             :     /// Data, Anti, and Output edges. On Data edges, this value may be zero,
     218             :     /// meaning there is no associated register.
     219             :     unsigned getReg() const {
     220             :       assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
     221             :              "getReg called on non-register dependence edge!");
     222             :       return Contents.Reg;
     223             :     }
     224             : 
     225             :     /// Assigns the associated register for this edge. This is only valid on
     226             :     /// Data, Anti, and Output edges. On Anti and Output edges, this value must
     227             :     /// not be zero. On Data edges, the value may be zero, which would mean that
     228             :     /// no specific register is associated with this edge.
     229             :     void setReg(unsigned Reg) {
     230             :       assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
     231             :              "setReg called on non-register dependence edge!");
     232             :       assert((getKind() != Anti || Reg != 0) &&
     233             :              "SDep::Anti edge cannot use the zero register!");
     234             :       assert((getKind() != Output || Reg != 0) &&
     235             :              "SDep::Output edge cannot use the zero register!");
     236             :       Contents.Reg = Reg;
     237             :     }
     238             : 
     239             :     raw_ostream &print(raw_ostream &O,
     240             :                        const TargetRegisterInfo *TRI = nullptr) const;
     241             :   };
     242             : 
     243             :   template <>
     244             :   struct isPodLike<SDep> { static const bool value = true; };
     245             : 
     246             :   /// Scheduling unit. This is a node in the scheduling DAG.
     247    37980186 :   class SUnit {
     248             :   private:
     249             :     enum : unsigned { BoundaryID = ~0u };
     250             : 
     251             :     SDNode *Node = nullptr;        ///< Representative node.
     252             :     MachineInstr *Instr = nullptr; ///< Alternatively, a MachineInstr.
     253             : 
     254             :   public:
     255             :     SUnit *OrigNode = nullptr; ///< If not this, the node from which this node 
     256             :                                /// was cloned. (SD scheduling only)
     257             : 
     258             :     const MCSchedClassDesc *SchedClass =
     259             :         nullptr; ///< nullptr or resolved SchedClass.
     260             : 
     261             :     SmallVector<SDep, 4> Preds;  ///< All sunit predecessors.
     262             :     SmallVector<SDep, 4> Succs;  ///< All sunit successors.
     263             : 
     264             :     typedef SmallVectorImpl<SDep>::iterator pred_iterator;
     265             :     typedef SmallVectorImpl<SDep>::iterator succ_iterator;
     266             :     typedef SmallVectorImpl<SDep>::const_iterator const_pred_iterator;
     267             :     typedef SmallVectorImpl<SDep>::const_iterator const_succ_iterator;
     268             : 
     269             :     unsigned NodeNum = BoundaryID;     ///< Entry # of node in the node vector.
     270             :     unsigned NodeQueueId = 0;          ///< Queue id of node.
     271             :     unsigned NumPreds = 0;             ///< # of SDep::Data preds.
     272             :     unsigned NumSuccs = 0;             ///< # of SDep::Data sucss.
     273             :     unsigned NumPredsLeft = 0;         ///< # of preds not scheduled.
     274             :     unsigned NumSuccsLeft = 0;         ///< # of succs not scheduled.
     275             :     unsigned WeakPredsLeft = 0;        ///< # of weak preds not scheduled.
     276             :     unsigned WeakSuccsLeft = 0;        ///< # of weak succs not scheduled.
     277             :     unsigned short NumRegDefsLeft = 0; ///< # of reg defs with no scheduled use.
     278             :     unsigned short Latency = 0;        ///< Node latency.
     279             :     bool isVRegCycle      : 1;         ///< May use and def the same vreg.
     280             :     bool isCall           : 1;         ///< Is a function call.
     281             :     bool isCallOp         : 1;         ///< Is a function call operand.
     282             :     bool isTwoAddress     : 1;         ///< Is a two-address instruction.
     283             :     bool isCommutable     : 1;         ///< Is a commutable instruction.
     284             :     bool hasPhysRegUses   : 1;         ///< Has physreg uses.
     285             :     bool hasPhysRegDefs   : 1;         ///< Has physreg defs that are being used.
     286             :     bool hasPhysRegClobbers : 1;       ///< Has any physreg defs, used or not.
     287             :     bool isPending        : 1;         ///< True once pending.
     288             :     bool isAvailable      : 1;         ///< True once available.
     289             :     bool isScheduled      : 1;         ///< True once scheduled.
     290             :     bool isScheduleHigh   : 1;         ///< True if preferable to schedule high.
     291             :     bool isScheduleLow    : 1;         ///< True if preferable to schedule low.
     292             :     bool isCloned         : 1;         ///< True if this node has been cloned.
     293             :     bool isUnbuffered     : 1;         ///< Uses an unbuffered resource.
     294             :     bool hasReservedResource : 1;      ///< Uses a reserved resource.
     295             :     Sched::Preference SchedulingPref = Sched::None; ///< Scheduling preference.
     296             : 
     297             :   private:
     298             :     bool isDepthCurrent   : 1;         ///< True if Depth is current.
     299             :     bool isHeightCurrent  : 1;         ///< True if Height is current.
     300             :     unsigned Depth = 0;                ///< Node depth.
     301             :     unsigned Height = 0;               ///< Node height.
     302             : 
     303             :   public:
     304             :     unsigned TopReadyCycle = 0; ///< Cycle relative to start when node is ready.
     305             :     unsigned BotReadyCycle = 0; ///< Cycle relative to end when node is ready.
     306             : 
     307             :     const TargetRegisterClass *CopyDstRC =
     308             :         nullptr; ///< Is a special copy node if != nullptr.
     309             :     const TargetRegisterClass *CopySrcRC = nullptr;
     310             : 
     311             :     /// \brief Constructs an SUnit for pre-regalloc scheduling to represent an
     312             :     /// SDNode and any nodes flagged to it.
     313     3575904 :     SUnit(SDNode *node, unsigned nodenum)
     314     3575904 :       : Node(node), NodeNum(nodenum), isVRegCycle(false), isCall(false),
     315             :         isCallOp(false), isTwoAddress(false), isCommutable(false),
     316             :         hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
     317             :         isPending(false), isAvailable(false), isScheduled(false),
     318             :         isScheduleHigh(false), isScheduleLow(false), isCloned(false),
     319             :         isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false),
     320    10727712 :         isHeightCurrent(false) {}
     321             : 
     322             :     /// \brief Constructs an SUnit for post-regalloc scheduling to represent a
     323             :     /// MachineInstr.
     324     3163448 :     SUnit(MachineInstr *instr, unsigned nodenum)
     325     3163448 :       : Instr(instr), NodeNum(nodenum), isVRegCycle(false), isCall(false),
     326             :         isCallOp(false), isTwoAddress(false), isCommutable(false),
     327             :         hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
     328             :         isPending(false), isAvailable(false), isScheduled(false),
     329             :         isScheduleHigh(false), isScheduleLow(false), isCloned(false),
     330             :         isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false),
     331     9490344 :         isHeightCurrent(false) {}
     332             : 
     333             :     /// \brief Constructs a placeholder SUnit.
     334     3390428 :     SUnit()
     335     3390428 :       : isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false),
     336             :         isCommutable(false), hasPhysRegUses(false), hasPhysRegDefs(false),
     337             :         hasPhysRegClobbers(false), isPending(false), isAvailable(false),
     338             :         isScheduled(false), isScheduleHigh(false), isScheduleLow(false),
     339             :         isCloned(false), isUnbuffered(false), hasReservedResource(false),
     340    10171284 :         isDepthCurrent(false), isHeightCurrent(false) {}
     341             : 
     342             :     /// \brief Boundary nodes are placeholders for the boundary of the
     343             :     /// scheduling region.
     344             :     ///
     345             :     /// BoundaryNodes can have DAG edges, including Data edges, but they do not
     346             :     /// correspond to schedulable entities (e.g. instructions) and do not have a
     347             :     /// valid ID. Consequently, always check for boundary nodes before accessing
     348             :     /// an associative data structure keyed on node ID.
     349             :     bool isBoundaryNode() const { return NodeNum == BoundaryID; }
     350             : 
     351             :     /// Assigns the representative SDNode for this SUnit. This may be used
     352             :     /// during pre-regalloc scheduling.
     353             :     void setNode(SDNode *N) {
     354             :       assert(!Instr && "Setting SDNode of SUnit with MachineInstr!");
     355     3544182 :       Node = N;
     356             :     }
     357             : 
     358             :     /// Returns the representative SDNode for this SUnit. This may be used
     359             :     /// during pre-regalloc scheduling.
     360             :     SDNode *getNode() const {
     361             :       assert(!Instr && "Reading SDNode of SUnit with MachineInstr!");
     362             :       return Node;
     363             :     }
     364             : 
     365             :     /// \brief Returns true if this SUnit refers to a machine instruction as
     366             :     /// opposed to an SDNode.
     367             :     bool isInstr() const { return Instr; }
     368             : 
     369             :     /// Assigns the instruction for the SUnit. This may be used during
     370             :     /// post-regalloc scheduling.
     371             :     void setInstr(MachineInstr *MI) {
     372             :       assert(!Node && "Setting MachineInstr of SUnit with SDNode!");
     373      977188 :       Instr = MI;
     374             :     }
     375             : 
     376             :     /// Returns the representative MachineInstr for this SUnit. This may be used
     377             :     /// during post-regalloc scheduling.
     378             :     MachineInstr *getInstr() const {
     379             :       assert(!Node && "Reading MachineInstr of SUnit with SDNode!");
     380             :       return Instr;
     381             :     }
     382             : 
     383             :     /// Adds the specified edge as a pred of the current node if not already.
     384             :     /// It also adds the current node as a successor of the specified node.
     385             :     bool addPred(const SDep &D, bool Required = true);
     386             : 
     387             :     /// \brief Adds a barrier edge to SU by calling addPred(), with latency 0
     388             :     /// generally or latency 1 for a store followed by a load.
     389       97520 :     bool addPredBarrier(SUnit *SU) {
     390       97520 :       SDep Dep(SU, SDep::Barrier);
     391             :       unsigned TrueMemOrderLatency =
     392       97520 :         ((SU->getInstr()->mayStore() && this->getInstr()->mayLoad()) ? 1 : 0);
     393      195040 :       Dep.setLatency(TrueMemOrderLatency);
     394       97520 :       return addPred(Dep);
     395             :     }
     396             : 
     397             :     /// Removes the specified edge as a pred of the current node if it exists.
     398             :     /// It also removes the current node as a successor of the specified node.
     399             :     void removePred(const SDep &D);
     400             : 
     401             :     /// Returns the depth of this node, which is the length of the maximum path
     402             :     /// up to any node which has no predecessors.
     403             :     unsigned getDepth() const {
     404    23184379 :       if (!isDepthCurrent)
     405     2486409 :         const_cast<SUnit *>(this)->ComputeDepth();
     406    23184379 :       return Depth;
     407             :     }
     408             : 
     409             :     /// \brief Returns the height of this node, which is the length of the
     410             :     /// maximum path down to any node which has no successors.
     411             :     unsigned getHeight() const {
     412    44443232 :       if (!isHeightCurrent)
     413     5742455 :         const_cast<SUnit *>(this)->ComputeHeight();
     414    44443232 :       return Height;
     415             :     }
     416             : 
     417             :     /// \brief If NewDepth is greater than this node's depth value, sets it to
     418             :     /// be the new depth value. This also recursively marks successor nodes
     419             :     /// dirty.
     420             :     void setDepthToAtLeast(unsigned NewDepth);
     421             : 
     422             :     /// \brief If NewDepth is greater than this node's depth value, set it to be
     423             :     /// the new height value. This also recursively marks predecessor nodes
     424             :     /// dirty.
     425             :     void setHeightToAtLeast(unsigned NewHeight);
     426             : 
     427             :     /// \brief Sets a flag in this node to indicate that its stored Depth value
     428             :     /// will require recomputation the next time getDepth() is called.
     429             :     void setDepthDirty();
     430             : 
     431             :     /// \brief Sets a flag in this node to indicate that its stored Height value
     432             :     /// will require recomputation the next time getHeight() is called.
     433             :     void setHeightDirty();
     434             : 
     435             :     /// Tests if node N is a predecessor of this node.
     436             :     bool isPred(const SUnit *N) const {
     437          50 :       for (const SDep &Pred : Preds)
     438          14 :         if (Pred.getSUnit() == N)
     439             :           return true;
     440             :       return false;
     441             :     }
     442             : 
     443             :     /// Tests if node N is a successor of this node.
     444             :     bool isSucc(const SUnit *N) const {
     445      344334 :       for (const SDep &Succ : Succs)
     446      174256 :         if (Succ.getSUnit() == N)
     447             :           return true;
     448             :       return false;
     449             :     }
     450             : 
     451             :     bool isTopReady() const {
     452             :       return NumPredsLeft == 0;
     453             :     }
     454             :     bool isBottomReady() const {
     455             :       return NumSuccsLeft == 0;
     456             :     }
     457             : 
     458             :     /// \brief Orders this node's predecessor edges such that the critical path
     459             :     /// edge occurs first.
     460             :     void biasCriticalPath();
     461             : 
     462             :     void dump(const ScheduleDAG *G) const;
     463             :     void dumpAll(const ScheduleDAG *G) const;
     464             :     raw_ostream &print(raw_ostream &O,
     465             :                        const SUnit *N = nullptr,
     466             :                        const SUnit *X = nullptr) const;
     467             :     raw_ostream &print(raw_ostream &O, const ScheduleDAG *G) const;
     468             : 
     469             :   private:
     470             :     void ComputeDepth();
     471             :     void ComputeHeight();
     472             :   };
     473             : 
     474             :   /// Returns true if the specified SDep is equivalent except for latency.
     475             :   inline bool SDep::overlaps(const SDep &Other) const {
     476   194167156 :     if (Dep != Other.Dep)
     477             :       return false;
     478     3531466 :     switch (Dep.getInt()) {
     479      775132 :     case Data:
     480             :     case Anti:
     481             :     case Output:
     482      775132 :       return Contents.Reg == Other.Contents.Reg;
     483      990601 :     case Order:
     484      990601 :       return Contents.OrdKind == Other.Contents.OrdKind;
     485             :     }
     486           0 :     llvm_unreachable("Invalid dependency kind!");
     487             :   }
     488             : 
     489             :   //// Returns the SUnit to which this edge points.
     490   347935614 :   inline SUnit *SDep::getSUnit() const { return Dep.getPointer(); }
     491             : 
     492             :   //// Assigns the SUnit to which this edge points.
     493    21920670 :   inline void SDep::setSUnit(SUnit *SU) { Dep.setPointer(SU); }
     494             : 
     495             :   /// Returns an enum value representing the kind of the dependence.
     496   201664992 :   inline SDep::Kind SDep::getKind() const { return Dep.getInt(); }
     497             : 
     498             :   //===--------------------------------------------------------------------===//
     499             : 
     500             :   /// \brief This interface is used to plug different priorities computation
     501             :   /// algorithms into the list scheduler. It implements the interface of a
     502             :   /// standard priority queue, where nodes are inserted in arbitrary order and
     503             :   /// returned in priority order.  The computation of the priority and the
     504             :   /// representation of the queue are totally up to the implementation to
     505             :   /// decide.
     506             :   class SchedulingPriorityQueue {
     507             :     virtual void anchor();
     508             : 
     509             :     unsigned CurCycle = 0;
     510             :     bool HasReadyFilter;
     511             : 
     512             :   public:
     513      312486 :     SchedulingPriorityQueue(bool rf = false) :  HasReadyFilter(rf) {}
     514             : 
     515             :     virtual ~SchedulingPriorityQueue() = default;
     516             : 
     517             :     virtual bool isBottomUp() const = 0;
     518             : 
     519             :     virtual void initNodes(std::vector<SUnit> &SUnits) = 0;
     520             :     virtual void addNode(const SUnit *SU) = 0;
     521             :     virtual void updateNode(const SUnit *SU) = 0;
     522             :     virtual void releaseState() = 0;
     523             : 
     524             :     virtual bool empty() const = 0;
     525             : 
     526             :     bool hasReadyFilter() const { return HasReadyFilter; }
     527             : 
     528           0 :     virtual bool tracksRegPressure() const { return false; }
     529             : 
     530           0 :     virtual bool isReady(SUnit *) const {
     531             :       assert(!HasReadyFilter && "The ready filter must override isReady()");
     532           0 :       return true;
     533             :     }
     534             : 
     535             :     virtual void push(SUnit *U) = 0;
     536             : 
     537             :     void push_all(const std::vector<SUnit *> &Nodes) {
     538       49838 :       for (std::vector<SUnit *>::const_iterator I = Nodes.begin(),
     539      143998 :            E = Nodes.end(); I != E; ++I)
     540       69241 :         push(*I);
     541             :     }
     542             : 
     543             :     virtual SUnit *pop() = 0;
     544             : 
     545             :     virtual void remove(SUnit *SU) = 0;
     546             : 
     547           0 :     virtual void dump(ScheduleDAG *) const {}
     548             : 
     549             :     /// As each node is scheduled, this method is invoked.  This allows the
     550             :     /// priority function to adjust the priority of related unscheduled nodes,
     551             :     /// for example.
     552           0 :     virtual void scheduledNode(SUnit *) {}
     553             : 
     554           0 :     virtual void unscheduledNode(SUnit *) {}
     555             : 
     556             :     void setCurCycle(unsigned Cycle) {
     557     3620857 :       CurCycle = Cycle;
     558             :     }
     559             : 
     560             :     unsigned getCurCycle() const {
     561             :       return CurCycle;
     562             :     }
     563             :   };
     564             : 
     565      430089 :   class ScheduleDAG {
     566             :   public:
     567             :     const TargetMachine &TM;            ///< Target processor
     568             :     const TargetInstrInfo *TII;         ///< Target instruction information
     569             :     const TargetRegisterInfo *TRI;      ///< Target processor register info
     570             :     MachineFunction &MF;                ///< Machine function
     571             :     MachineRegisterInfo &MRI;           ///< Virtual/real register map
     572             :     std::vector<SUnit> SUnits;          ///< The scheduling units.
     573             :     SUnit EntrySU;                      ///< Special node for the region entry.
     574             :     SUnit ExitSU;                       ///< Special node for the region exit.
     575             : 
     576             : #ifdef NDEBUG
     577             :     static const bool StressSched = false;
     578             : #else
     579             :     bool StressSched;
     580             : #endif
     581             : 
     582             :     explicit ScheduleDAG(MachineFunction &mf);
     583             : 
     584             :     virtual ~ScheduleDAG();
     585             : 
     586             :     /// Clears the DAG state (between regions).
     587             :     void clearDAG();
     588             : 
     589             :     /// Returns the MCInstrDesc of this SUnit.
     590             :     /// Returns NULL for SDNodes without a machine opcode.
     591             :     const MCInstrDesc *getInstrDesc(const SUnit *SU) const {
     592      807346 :       if (SU->isInstr()) return &SU->getInstr()->getDesc();
     593      313757 :       return getNodeDesc(SU->getNode());
     594             :     }
     595             : 
     596             :     /// Pops up a GraphViz/gv window with the ScheduleDAG rendered using 'dot'.
     597             :     virtual void viewGraph(const Twine &Name, const Twine &Title);
     598             :     virtual void viewGraph();
     599             : 
     600             :     virtual void dumpNode(const SUnit *SU) const = 0;
     601             : 
     602             :     /// Returns a label for an SUnit node in a visualization of the ScheduleDAG.
     603             :     virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0;
     604             : 
     605             :     /// Returns a label for the region of code covered by the DAG.
     606             :     virtual std::string getDAGName() const = 0;
     607             : 
     608             :     /// Adds custom features for a visualization of the ScheduleDAG.
     609           0 :     virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {}
     610             : 
     611             : #ifndef NDEBUG
     612             :     /// \brief Verifies that all SUnits were scheduled and that their state is
     613             :     /// consistent. Returns the number of scheduled SUnits.
     614             :     unsigned VerifyScheduledDAG(bool isBottomUp);
     615             : #endif
     616             : 
     617             :   private:
     618             :     /// Returns the MCInstrDesc of this SDNode or NULL.
     619             :     const MCInstrDesc *getNodeDesc(const SDNode *Node) const;
     620             :   };
     621             : 
     622             :   class SUnitIterator : public std::iterator<std::forward_iterator_tag,
     623             :                                              SUnit, ptrdiff_t> {
     624             :     SUnit *Node;
     625             :     unsigned Operand;
     626             : 
     627             :     SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {}
     628             : 
     629             :   public:
     630             :     bool operator==(const SUnitIterator& x) const {
     631             :       return Operand == x.Operand;
     632             :     }
     633             :     bool operator!=(const SUnitIterator& x) const { return !operator==(x); }
     634             : 
     635             :     pointer operator*() const {
     636             :       return Node->Preds[Operand].getSUnit();
     637             :     }
     638             :     pointer operator->() const { return operator*(); }
     639             : 
     640             :     SUnitIterator& operator++() {                // Preincrement
     641             :       ++Operand;
     642             :       return *this;
     643             :     }
     644             :     SUnitIterator operator++(int) { // Postincrement
     645             :       SUnitIterator tmp = *this; ++*this; return tmp;
     646             :     }
     647             : 
     648             :     static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); }
     649             :     static SUnitIterator end  (SUnit *N) {
     650             :       return SUnitIterator(N, (unsigned)N->Preds.size());
     651             :     }
     652             : 
     653             :     unsigned getOperand() const { return Operand; }
     654             :     const SUnit *getNode() const { return Node; }
     655             : 
     656             :     /// Tests if this is not an SDep::Data dependence.
     657             :     bool isCtrlDep() const {
     658             :       return getSDep().isCtrl();
     659             :     }
     660             :     bool isArtificialDep() const {
     661             :       return getSDep().isArtificial();
     662             :     }
     663             :     const SDep &getSDep() const {
     664             :       return Node->Preds[Operand];
     665             :     }
     666             :   };
     667             : 
     668             :   template <> struct GraphTraits<SUnit*> {
     669             :     typedef SUnit *NodeRef;
     670             :     typedef SUnitIterator ChildIteratorType;
     671             :     static NodeRef getEntryNode(SUnit *N) { return N; }
     672             :     static ChildIteratorType child_begin(NodeRef N) {
     673             :       return SUnitIterator::begin(N);
     674             :     }
     675             :     static ChildIteratorType child_end(NodeRef N) {
     676             :       return SUnitIterator::end(N);
     677             :     }
     678             :   };
     679             : 
     680             :   template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> {
     681             :     typedef pointer_iterator<std::vector<SUnit>::iterator> nodes_iterator;
     682             :     static nodes_iterator nodes_begin(ScheduleDAG *G) {
     683             :       return nodes_iterator(G->SUnits.begin());
     684             :     }
     685             :     static nodes_iterator nodes_end(ScheduleDAG *G) {
     686             :       return nodes_iterator(G->SUnits.end());
     687             :     }
     688             :   };
     689             : 
     690             :   /// This class can compute a topological ordering for SUnits and provides
     691             :   /// methods for dynamically updating the ordering as new edges are added.
     692             :   ///
     693             :   /// This allows a very fast implementation of IsReachable, for example.
     694     1578408 :   class ScheduleDAGTopologicalSort {
     695             :     /// A reference to the ScheduleDAG's SUnits.
     696             :     std::vector<SUnit> &SUnits;
     697             :     SUnit *ExitSU;
     698             : 
     699             :     /// Maps topological index to the node number.
     700             :     std::vector<int> Index2Node;
     701             :     /// Maps the node number to its topological index.
     702             :     std::vector<int> Node2Index;
     703             :     /// a set of nodes visited during a DFS traversal.
     704             :     BitVector Visited;
     705             : 
     706             :     /// Makes a DFS traversal and mark all nodes affected by the edge insertion.
     707             :     /// These nodes will later get new topological indexes by means of the Shift
     708             :     /// method.
     709             :     void DFS(const SUnit *SU, int UpperBound, bool& HasLoop);
     710             : 
     711             :     /// \brief Reassigns topological indexes for the nodes in the DAG to
     712             :     /// preserve the topological ordering.
     713             :     void Shift(BitVector& Visited, int LowerBound, int UpperBound);
     714             : 
     715             :     /// Assigns the topological index to the node n.
     716             :     void Allocate(int n, int index);
     717             : 
     718             :   public:
     719             :     ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU);
     720             : 
     721             :     /// Creates the initial topological ordering from the DAG to be scheduled.
     722             :     void InitDAGTopologicalSorting();
     723             : 
     724             :     /// Returns an array of SUs that are both in the successor
     725             :     /// subtree of StartSU and in the predecessor subtree of TargetSU.
     726             :     /// StartSU and TargetSU are not in the array.
     727             :     /// Success is false if TargetSU is not in the successor subtree of
     728             :     /// StartSU, else it is true.
     729             :     std::vector<int> GetSubGraph(const SUnit &StartSU, const SUnit &TargetSU,
     730             :                                  bool &Success);
     731             : 
     732             :     /// Checks if \p SU is reachable from \p TargetSU.
     733             :     bool IsReachable(const SUnit *SU, const SUnit *TargetSU);
     734             : 
     735             :     /// Returns true if addPred(TargetSU, SU) creates a cycle.
     736             :     bool WillCreateCycle(SUnit *TargetSU, SUnit *SU);
     737             : 
     738             :     /// \brief Updates the topological ordering to accommodate an edge to be
     739             :     /// added from SUnit \p X to SUnit \p Y.
     740             :     void AddPred(SUnit *Y, SUnit *X);
     741             : 
     742             :     /// \brief Updates the topological ordering to accommodate an an edge to be
     743             :     /// removed from the specified node \p N from the predecessors of the
     744             :     /// current node \p M.
     745             :     void RemovePred(SUnit *M, SUnit *N);
     746             : 
     747             :     typedef std::vector<int>::iterator iterator;
     748             :     typedef std::vector<int>::const_iterator const_iterator;
     749         228 :     iterator begin() { return Index2Node.begin(); }
     750             :     const_iterator begin() const { return Index2Node.begin(); }
     751         228 :     iterator end() { return Index2Node.end(); }
     752             :     const_iterator end() const { return Index2Node.end(); }
     753             : 
     754             :     typedef std::vector<int>::reverse_iterator reverse_iterator;
     755             :     typedef std::vector<int>::const_reverse_iterator const_reverse_iterator;
     756           4 :     reverse_iterator rbegin() { return Index2Node.rbegin(); }
     757             :     const_reverse_iterator rbegin() const { return Index2Node.rbegin(); }
     758           4 :     reverse_iterator rend() { return Index2Node.rend(); }
     759             :     const_reverse_iterator rend() const { return Index2Node.rend(); }
     760             :   };
     761             : 
     762             : } // end namespace llvm
     763             : 
     764             : #endif // LLVM_CODEGEN_SCHEDULEDAG_H

Generated by: LCOV version 1.13