LCOV - code coverage report
Current view: top level - lib/CodeGen - ScheduleDAG.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 195 259 75.3 %
Date: 2018-06-17 00:07:59 Functions: 21 24 87.5 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- ScheduleDAG.cpp - Implement the ScheduleDAG class ------------------===//
       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 a base class used by
      11             : /// scheduling implementation classes.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #include "llvm/CodeGen/ScheduleDAG.h"
      16             : #include "llvm/ADT/STLExtras.h"
      17             : #include "llvm/ADT/SmallVector.h"
      18             : #include "llvm/ADT/iterator_range.h"
      19             : #include "llvm/CodeGen/MachineFunction.h"
      20             : #include "llvm/CodeGen/ScheduleHazardRecognizer.h"
      21             : #include "llvm/CodeGen/SelectionDAGNodes.h"
      22             : #include "llvm/CodeGen/TargetInstrInfo.h"
      23             : #include "llvm/CodeGen/TargetRegisterInfo.h"
      24             : #include "llvm/CodeGen/TargetSubtargetInfo.h"
      25             : #include "llvm/Config/llvm-config.h"
      26             : #include "llvm/Support/CommandLine.h"
      27             : #include "llvm/Support/Compiler.h"
      28             : #include "llvm/Support/Debug.h"
      29             : #include "llvm/Support/raw_ostream.h"
      30             : #include <algorithm>
      31             : #include <cassert>
      32             : #include <iterator>
      33             : #include <limits>
      34             : #include <utility>
      35             : #include <vector>
      36             : 
      37             : using namespace llvm;
      38             : 
      39             : #define DEBUG_TYPE "pre-RA-sched"
      40             : 
      41             : #ifndef NDEBUG
      42             : static cl::opt<bool> StressSchedOpt(
      43             :   "stress-sched", cl::Hidden, cl::init(false),
      44             :   cl::desc("Stress test instruction scheduling"));
      45             : #endif
      46             : 
      47           0 : void SchedulingPriorityQueue::anchor() {}
      48             : 
      49      577922 : ScheduleDAG::ScheduleDAG(MachineFunction &mf)
      50     1155844 :     : TM(mf.getTarget()), TII(mf.getSubtarget().getInstrInfo()),
      51      577922 :       TRI(mf.getSubtarget().getRegisterInfo()), MF(mf),
      52     2889610 :       MRI(mf.getRegInfo()) {
      53             : #ifndef NDEBUG
      54             :   StressSched = StressSchedOpt;
      55             : #endif
      56      577922 : }
      57             : 
      58             : ScheduleDAG::~ScheduleDAG() = default;
      59             : 
      60     1192781 : void ScheduleDAG::clearDAG() {
      61             :   SUnits.clear();
      62     1192781 :   EntrySU = SUnit();
      63     1192781 :   ExitSU = SUnit();
      64     1192781 : }
      65             : 
      66      334640 : const MCInstrDesc *ScheduleDAG::getNodeDesc(const SDNode *Node) const {
      67      334640 :   if (!Node || !Node->isMachineOpcode()) return nullptr;
      68      648975 :   return &TII->get(Node->getMachineOpcode());
      69             : }
      70             : 
      71             : LLVM_DUMP_METHOD
      72           0 : raw_ostream &SDep::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const {
      73           0 :   switch (getKind()) {
      74           0 :   case Data:   OS << "Data"; break;
      75           0 :   case Anti:   OS << "Anti"; break;
      76           0 :   case Output: OS << "Out "; break;
      77           0 :   case Order:  OS << "Ord "; break;
      78             :   }
      79             : 
      80           0 :   switch (getKind()) {
      81           0 :   case Data:
      82           0 :     OS << " Latency=" << getLatency();
      83           0 :     if (TRI && isAssignedRegDep())
      84           0 :       OS << " Reg=" << printReg(getReg(), TRI);
      85             :     break;
      86           0 :   case Anti:
      87             :   case Output:
      88           0 :     OS << " Latency=" << getLatency();
      89             :     break;
      90           0 :   case Order:
      91           0 :     OS << " Latency=" << getLatency();
      92           0 :     switch(Contents.OrdKind) {
      93           0 :     case Barrier:      OS << " Barrier"; break;
      94           0 :     case MayAliasMem:
      95           0 :     case MustAliasMem: OS << " Memory"; break;
      96           0 :     case Artificial:   OS << " Artificial"; break;
      97           0 :     case Weak:         OS << " Weak"; break;
      98           0 :     case Cluster:      OS << " Cluster"; break;
      99             :     }
     100             :     break;
     101             :   }
     102             : 
     103           0 :   return OS;
     104             : }
     105             : 
     106    13972551 : bool SUnit::addPred(const SDep &D, bool Required) {
     107             :   // If this node already has this dependence, don't add a redundant one.
     108   142877983 :   for (SDep &PredDep : Preds) {
     109             :     // Zero-latency weak edges may be added purely for heuristic ordering. Don't
     110             :     // add them if another kind of edge already exists.
     111    67675060 :     if (!Required && PredDep.getSUnit() == D.getSUnit())
     112             :       return false;
     113     2601945 :     if (PredDep.overlaps(D)) {
     114             :       // Extend the latency if needed. Equivalent to
     115             :       // removePred(PredDep) + addPred(D).
     116     2420039 :       if (PredDep.getLatency() < D.getLatency()) {
     117             :         SUnit *PredSU = PredDep.getSUnit();
     118             :         // Find the corresponding successor in N.
     119        1466 :         SDep ForwardD = PredDep;
     120             :         ForwardD.setSUnit(this);
     121        3466 :         for (SDep &SuccDep : PredSU->Succs) {
     122        2466 :           if (SuccDep == ForwardD) {
     123             :             SuccDep.setLatency(D.getLatency());
     124             :             break;
     125             :           }
     126             :         }
     127        1466 :         PredDep.setLatency(D.getLatency());
     128             :       }
     129             :       return false;
     130             :     }
     131             :   }
     132             :   // Now add a corresponding succ to N.
     133    11522846 :   SDep P = D;
     134             :   P.setSUnit(this);
     135             :   SUnit *N = D.getSUnit();
     136             :   // Update the bookkeeping.
     137    11522846 :   if (D.getKind() == SDep::Data) {
     138             :     assert(NumPreds < std::numeric_limits<unsigned>::max() &&
     139             :            "NumPreds will overflow!");
     140             :     assert(N->NumSuccs < std::numeric_limits<unsigned>::max() &&
     141             :            "NumSuccs will overflow!");
     142     5669556 :     ++NumPreds;
     143     5669556 :     ++N->NumSuccs;
     144             :   }
     145    11522846 :   if (!N->isScheduled) {
     146             :     if (D.isWeak()) {
     147       43294 :       ++WeakPredsLeft;
     148             :     }
     149             :     else {
     150             :       assert(NumPredsLeft < std::numeric_limits<unsigned>::max() &&
     151             :              "NumPredsLeft will overflow!");
     152    11479552 :       ++NumPredsLeft;
     153             :     }
     154             :   }
     155    11522846 :   if (!isScheduled) {
     156             :     if (D.isWeak()) {
     157       43294 :       ++N->WeakSuccsLeft;
     158             :     }
     159             :     else {
     160             :       assert(N->NumSuccsLeft < std::numeric_limits<unsigned>::max() &&
     161             :              "NumSuccsLeft will overflow!");
     162    11447002 :       ++N->NumSuccsLeft;
     163             :     }
     164             :   }
     165    11522846 :   Preds.push_back(D);
     166    11522846 :   N->Succs.push_back(P);
     167    11522846 :   if (P.getLatency() != 0) {
     168     7912078 :     this->setDepthDirty();
     169     7912078 :     N->setHeightDirty();
     170             :   }
     171             :   return true;
     172             : }
     173             : 
     174       49449 : void SUnit::removePred(const SDep &D) {
     175             :   // Find the matching predecessor.
     176             :   SmallVectorImpl<SDep>::iterator I = llvm::find(Preds, D);
     177       49449 :   if (I == Preds.end())
     178         305 :     return;
     179             :   // Find the corresponding successor in N.
     180       49144 :   SDep P = D;
     181             :   P.setSUnit(this);
     182             :   SUnit *N = D.getSUnit();
     183             :   SmallVectorImpl<SDep>::iterator Succ = llvm::find(N->Succs, P);
     184             :   assert(Succ != N->Succs.end() && "Mismatching preds / succs lists!");
     185             :   N->Succs.erase(Succ);
     186             :   Preds.erase(I);
     187             :   // Update the bookkeeping.
     188       49144 :   if (P.getKind() == SDep::Data) {
     189             :     assert(NumPreds > 0 && "NumPreds will underflow!");
     190             :     assert(N->NumSuccs > 0 && "NumSuccs will underflow!");
     191       36364 :     --NumPreds;
     192       36364 :     --N->NumSuccs;
     193             :   }
     194       49144 :   if (!N->isScheduled) {
     195             :     if (D.isWeak())
     196           0 :       --WeakPredsLeft;
     197             :     else {
     198             :       assert(NumPredsLeft > 0 && "NumPredsLeft will underflow!");
     199       49144 :       --NumPredsLeft;
     200             :     }
     201             :   }
     202       49144 :   if (!isScheduled) {
     203             :     if (D.isWeak())
     204           0 :       --N->WeakSuccsLeft;
     205             :     else {
     206             :       assert(N->NumSuccsLeft > 0 && "NumSuccsLeft will underflow!");
     207       16899 :       --N->NumSuccsLeft;
     208             :     }
     209             :   }
     210       49144 :   if (P.getLatency() != 0) {
     211       48096 :     this->setDepthDirty();
     212       48096 :     N->setHeightDirty();
     213             :   }
     214             : }
     215             : 
     216    10999980 : void SUnit::setDepthDirty() {
     217    21862746 :   if (!isDepthCurrent) return;
     218             :   SmallVector<SUnit*, 8> WorkList;
     219      137214 :   WorkList.push_back(this);
     220             :   do {
     221             :     SUnit *SU = WorkList.pop_back_val();
     222      146028 :     SU->isDepthCurrent = false;
     223     1582678 :     for (SDep &SuccDep : SU->Succs) {
     224      718325 :       SUnit *SuccSU = SuccDep.getSUnit();
     225      718325 :       if (SuccSU->isDepthCurrent)
     226        8814 :         WorkList.push_back(SuccSU);
     227             :     }
     228      146028 :   } while (!WorkList.empty());
     229             : }
     230             : 
     231    15420583 : void SUnit::setHeightDirty() {
     232    29335011 :   if (!isHeightCurrent) return;
     233             :   SmallVector<SUnit*, 8> WorkList;
     234     1506155 :   WorkList.push_back(this);
     235             :   do {
     236             :     SUnit *SU = WorkList.pop_back_val();
     237     1662096 :     SU->isHeightCurrent = false;
     238     6286666 :     for (SDep &PredDep : SU->Preds) {
     239     2312285 :       SUnit *PredSU = PredDep.getSUnit();
     240     2312285 :       if (PredSU->isHeightCurrent)
     241      155941 :         WorkList.push_back(PredSU);
     242             :     }
     243     1662096 :   } while (!WorkList.empty());
     244             : }
     245             : 
     246      887244 : void SUnit::setDepthToAtLeast(unsigned NewDepth) {
     247      887244 :   if (NewDepth <= getDepth())
     248             :     return;
     249      136918 :   setDepthDirty();
     250      136918 :   Depth = NewDepth;
     251      136918 :   isDepthCurrent = true;
     252             : }
     253             : 
     254     4255787 : void SUnit::setHeightToAtLeast(unsigned NewHeight) {
     255     4255787 :   if (NewHeight <= getHeight())
     256             :     return;
     257     1497647 :   setHeightDirty();
     258     1497647 :   Height = NewHeight;
     259     1497647 :   isHeightCurrent = true;
     260             : }
     261             : 
     262             : /// Calculates the maximal path from the node to the exit.
     263     2766238 : void SUnit::ComputeDepth() {
     264             :   SmallVector<SUnit*, 8> WorkList;
     265     2766238 :   WorkList.push_back(this);
     266             :   do {
     267     7116107 :     SUnit *Cur = WorkList.back();
     268             : 
     269             :     bool Done = true;
     270     7116107 :     unsigned MaxPredDepth = 0;
     271    28781963 :     for (const SDep &PredDep : Cur->Preds) {
     272    10832928 :       SUnit *PredSU = PredDep.getSUnit();
     273    10832928 :       if (PredSU->isDepthCurrent)
     274     8191423 :         MaxPredDepth = std::max(MaxPredDepth,
     275    16382846 :                                 PredSU->Depth + PredDep.getLatency());
     276             :       else {
     277             :         Done = false;
     278     2641505 :         WorkList.push_back(PredSU);
     279             :       }
     280             :     }
     281             : 
     282     7116107 :     if (Done) {
     283             :       WorkList.pop_back();
     284     5407743 :       if (MaxPredDepth != Cur->Depth) {
     285     2901629 :         Cur->setDepthDirty();
     286     2901629 :         Cur->Depth = MaxPredDepth;
     287             :       }
     288     5407743 :       Cur->isDepthCurrent = true;
     289             :     }
     290     7116107 :   } while (!WorkList.empty());
     291     2766238 : }
     292             : 
     293             : /// Calculates the maximal path from the node to the entry.
     294     6343279 : void SUnit::ComputeHeight() {
     295             :   SmallVector<SUnit*, 8> WorkList;
     296     6343279 :   WorkList.push_back(this);
     297             :   do {
     298     9295674 :     SUnit *Cur = WorkList.back();
     299             : 
     300             :     bool Done = true;
     301     9295674 :     unsigned MaxSuccHeight = 0;
     302    48326458 :     for (const SDep &SuccDep : Cur->Succs) {
     303    19515392 :       SUnit *SuccSU = SuccDep.getSUnit();
     304    19515392 :       if (SuccSU->isHeightCurrent)
     305    17554288 :         MaxSuccHeight = std::max(MaxSuccHeight,
     306    35108576 :                                  SuccSU->Height + SuccDep.getLatency());
     307             :       else {
     308             :         Done = false;
     309     1961104 :         WorkList.push_back(SuccSU);
     310             :       }
     311             :     }
     312             : 
     313     9295674 :     if (Done) {
     314             :       WorkList.pop_back();
     315     8304383 :       if (MaxSuccHeight != Cur->Height) {
     316     5952999 :         Cur->setHeightDirty();
     317     5952999 :         Cur->Height = MaxSuccHeight;
     318             :       }
     319     8304383 :       Cur->isHeightCurrent = true;
     320             :     }
     321     9295674 :   } while (!WorkList.empty());
     322     6343279 : }
     323             : 
     324     2746209 : void SUnit::biasCriticalPath() {
     325     2746209 :   if (NumPreds < 2)
     326             :     return;
     327             : 
     328             :   SUnit::pred_iterator BestI = Preds.begin();
     329             :   unsigned MaxDepth = BestI->getSUnit()->getDepth();
     330     2415247 :   for (SUnit::pred_iterator I = std::next(BestI), E = Preds.end(); I != E;
     331             :        ++I) {
     332     1571653 :     if (I->getKind() == SDep::Data && I->getSUnit()->getDepth() > MaxDepth)
     333             :       BestI = I;
     334             :   }
     335      375401 :   if (BestI != Preds.begin())
     336             :     std::swap(*Preds.begin(), *BestI);
     337             : }
     338             : 
     339             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     340             : LLVM_DUMP_METHOD
     341             : raw_ostream &SUnit::print(raw_ostream &OS,
     342             :                           const SUnit *Entry, const SUnit *Exit) const {
     343             :   if (this == Entry)
     344             :     OS << "EntrySU";
     345             :   else if (this == Exit)
     346             :     OS << "ExitSU";
     347             :   else
     348             :     OS << "SU(" << NodeNum << ")";
     349             :   return OS;
     350             : }
     351             : 
     352             : LLVM_DUMP_METHOD
     353             : raw_ostream &SUnit::print(raw_ostream &OS, const ScheduleDAG *G) const {
     354             :   return print(OS, &G->EntrySU, &G->ExitSU);
     355             : }
     356             : 
     357             : LLVM_DUMP_METHOD
     358             : void SUnit::dump(const ScheduleDAG *G) const {
     359             :   print(dbgs(), G);
     360             :   dbgs() << ": ";
     361             :   G->dumpNode(this);
     362             : }
     363             : 
     364             : LLVM_DUMP_METHOD void SUnit::dumpAll(const ScheduleDAG *G) const {
     365             :   dump(G);
     366             : 
     367             :   dbgs() << "  # preds left       : " << NumPredsLeft << "\n";
     368             :   dbgs() << "  # succs left       : " << NumSuccsLeft << "\n";
     369             :   if (WeakPredsLeft)
     370             :     dbgs() << "  # weak preds left  : " << WeakPredsLeft << "\n";
     371             :   if (WeakSuccsLeft)
     372             :     dbgs() << "  # weak succs left  : " << WeakSuccsLeft << "\n";
     373             :   dbgs() << "  # rdefs left       : " << NumRegDefsLeft << "\n";
     374             :   dbgs() << "  Latency            : " << Latency << "\n";
     375             :   dbgs() << "  Depth              : " << getDepth() << "\n";
     376             :   dbgs() << "  Height             : " << getHeight() << "\n";
     377             : 
     378             :   if (Preds.size() != 0) {
     379             :     dbgs() << "  Predecessors:\n";
     380             :     for (const SDep &Dep : Preds) {
     381             :       dbgs() << "    ";
     382             :       Dep.getSUnit()->print(dbgs(), G); dbgs() << ": ";
     383             :       Dep.print(dbgs(), G->TRI); dbgs() << '\n';
     384             :     }
     385             :   }
     386             :   if (Succs.size() != 0) {
     387             :     dbgs() << "  Successors:\n";
     388             :     for (const SDep &Dep : Succs) {
     389             :       dbgs() << "    ";
     390             :       Dep.getSUnit()->print(dbgs(), G); dbgs() << ": ";
     391             :       Dep.print(dbgs(), G->TRI); dbgs() << '\n';
     392             :     }
     393             :   }
     394             : }
     395             : #endif
     396             : 
     397             : #ifndef NDEBUG
     398             : unsigned ScheduleDAG::VerifyScheduledDAG(bool isBottomUp) {
     399             :   bool AnyNotSched = false;
     400             :   unsigned DeadNodes = 0;
     401             :   for (const SUnit &SUnit : SUnits) {
     402             :     if (!SUnit.isScheduled) {
     403             :       if (SUnit.NumPreds == 0 && SUnit.NumSuccs == 0) {
     404             :         ++DeadNodes;
     405             :         continue;
     406             :       }
     407             :       if (!AnyNotSched)
     408             :         dbgs() << "*** Scheduling failed! ***\n";
     409             :       SUnit.dump(this);
     410             :       dbgs() << "has not been scheduled!\n";
     411             :       AnyNotSched = true;
     412             :     }
     413             :     if (SUnit.isScheduled &&
     414             :         (isBottomUp ? SUnit.getHeight() : SUnit.getDepth()) >
     415             :           unsigned(std::numeric_limits<int>::max())) {
     416             :       if (!AnyNotSched)
     417             :         dbgs() << "*** Scheduling failed! ***\n";
     418             :       SUnit.dump(this);
     419             :       dbgs() << "has an unexpected "
     420             :            << (isBottomUp ? "Height" : "Depth") << " value!\n";
     421             :       AnyNotSched = true;
     422             :     }
     423             :     if (isBottomUp) {
     424             :       if (SUnit.NumSuccsLeft != 0) {
     425             :         if (!AnyNotSched)
     426             :           dbgs() << "*** Scheduling failed! ***\n";
     427             :         SUnit.dump(this);
     428             :         dbgs() << "has successors left!\n";
     429             :         AnyNotSched = true;
     430             :       }
     431             :     } else {
     432             :       if (SUnit.NumPredsLeft != 0) {
     433             :         if (!AnyNotSched)
     434             :           dbgs() << "*** Scheduling failed! ***\n";
     435             :         SUnit.dump(this);
     436             :         dbgs() << "has predecessors left!\n";
     437             :         AnyNotSched = true;
     438             :       }
     439             :     }
     440             :   }
     441             :   assert(!AnyNotSched);
     442             :   return SUnits.size() - DeadNodes;
     443             : }
     444             : #endif
     445             : 
     446      777340 : void ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() {
     447             :   // The idea of the algorithm is taken from
     448             :   // "Online algorithms for managing the topological order of
     449             :   // a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly
     450             :   // This is the MNR algorithm, which was first introduced by
     451             :   // A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in
     452             :   // "Maintaining a topological order under edge insertions".
     453             :   //
     454             :   // Short description of the algorithm:
     455             :   //
     456             :   // Topological ordering, ord, of a DAG maps each node to a topological
     457             :   // index so that for all edges X->Y it is the case that ord(X) < ord(Y).
     458             :   //
     459             :   // This means that if there is a path from the node X to the node Z,
     460             :   // then ord(X) < ord(Z).
     461             :   //
     462             :   // This property can be used to check for reachability of nodes:
     463             :   // if Z is reachable from X, then an insertion of the edge Z->X would
     464             :   // create a cycle.
     465             :   //
     466             :   // The algorithm first computes a topological ordering for the DAG by
     467             :   // initializing the Index2Node and Node2Index arrays and then tries to keep
     468             :   // the ordering up-to-date after edge insertions by reordering the DAG.
     469             :   //
     470             :   // On insertion of the edge X->Y, the algorithm first marks by calling DFS
     471             :   // the nodes reachable from Y, and then shifts them using Shift to lie
     472             :   // immediately after X in Index2Node.
     473     1554680 :   unsigned DAGSize = SUnits.size();
     474             :   std::vector<SUnit*> WorkList;
     475      777340 :   WorkList.reserve(DAGSize);
     476             : 
     477      777340 :   Index2Node.resize(DAGSize);
     478      777340 :   Node2Index.resize(DAGSize);
     479             : 
     480             :   // Initialize the data structures.
     481      777340 :   if (ExitSU)
     482      379010 :     WorkList.push_back(ExitSU);
     483     8825434 :   for (SUnit &SU : SUnits) {
     484     7270754 :     int NodeNum = SU.NodeNum;
     485     7270754 :     unsigned Degree = SU.Succs.size();
     486             :     // Temporarily use the Node2Index array as scratch space for degree counts.
     487    14541508 :     Node2Index[NodeNum] = Degree;
     488             : 
     489             :     // Is it a node without dependencies?
     490     7270754 :     if (Degree == 0) {
     491             :       assert(SU.Succs.empty() && "SUnit should have no successors");
     492             :       // Collect leaf nodes.
     493     1497260 :       WorkList.push_back(&SU);
     494             :     }
     495             :   }
     496             : 
     497      777340 :   int Id = DAGSize;
     498     8427104 :   while (!WorkList.empty()) {
     499     7649764 :     SUnit *SU = WorkList.back();
     500             :     WorkList.pop_back();
     501     7649764 :     if (SU->NodeNum < DAGSize)
     502     7270754 :       Allocate(SU->NodeNum, --Id);
     503    27651014 :     for (const SDep &PredDep : SU->Preds) {
     504    10000625 :       SUnit *SU = PredDep.getSUnit();
     505    20001250 :       if (SU->NodeNum < DAGSize && !--Node2Index[SU->NodeNum])
     506             :         // If all dependencies of the node are processed already,
     507             :         // then the node can be computed now.
     508     6522124 :         WorkList.push_back(SU);
     509             :     }
     510             :   }
     511             : 
     512      777340 :   Visited.resize(DAGSize);
     513             : 
     514             : #ifndef NDEBUG
     515             :   // Check correctness of the ordering
     516             :   for (SUnit &SU : SUnits)  {
     517             :     for (const SDep &PD : SU.Preds) {
     518             :       assert(Node2Index[SU.NodeNum] > Node2Index[PD.getSUnit()->NodeNum] &&
     519             :       "Wrong topological sorting");
     520             :     }
     521             :   }
     522             : #endif
     523      777340 : }
     524             : 
     525      216729 : void ScheduleDAGTopologicalSort::AddPred(SUnit *Y, SUnit *X) {
     526             :   int UpperBound, LowerBound;
     527      433458 :   LowerBound = Node2Index[Y->NodeNum];
     528      433458 :   UpperBound = Node2Index[X->NodeNum];
     529      216729 :   bool HasLoop = false;
     530             :   // Is Ord(X) < Ord(Y) ?
     531      216729 :   if (LowerBound < UpperBound) {
     532             :     // Update the topological order.
     533             :     Visited.reset();
     534       60655 :     DFS(Y, UpperBound, HasLoop);
     535             :     assert(!HasLoop && "Inserted edge creates a loop!");
     536             :     // Recompute topological indexes.
     537       60655 :     Shift(Visited, LowerBound, UpperBound);
     538             :   }
     539      216729 : }
     540             : 
     541       48560 : void ScheduleDAGTopologicalSort::RemovePred(SUnit *M, SUnit *N) {
     542             :   // InitDAGTopologicalSorting();
     543       48560 : }
     544             : 
     545      125323 : void ScheduleDAGTopologicalSort::DFS(const SUnit *SU, int UpperBound,
     546             :                                      bool &HasLoop) {
     547             :   std::vector<const SUnit*> WorkList;
     548      250646 :   WorkList.reserve(SUnits.size());
     549             : 
     550      125323 :   WorkList.push_back(SU);
     551             :   do {
     552      442970 :     SU = WorkList.back();
     553             :     WorkList.pop_back();
     554      442970 :     Visited.set(SU->NodeNum);
     555             :     for (const SDep &SuccDep
     556      442970 :          : make_range(SU->Succs.rbegin(), SU->Succs.rend())) {
     557      819087 :       unsigned s = SuccDep.getSUnit()->NodeNum;
     558             :       // Edges to non-SUnits are allowed but ignored (e.g. ExitSU).
     559     1638174 :       if (s >= Node2Index.size())
     560        3724 :         continue;
     561      815363 :       if (Node2Index[s] == UpperBound) {
     562       36067 :         HasLoop = true;
     563             :         return;
     564             :       }
     565             :       // Visit successors if not already and in affected region.
     566      779296 :       if (!Visited.test(s) && Node2Index[s] < UpperBound) {
     567      767040 :         WorkList.push_back(SuccDep.getSUnit());
     568             :       }
     569             :     }
     570      406903 :   } while (!WorkList.empty());
     571             : }
     572             : 
     573           0 : std::vector<int> ScheduleDAGTopologicalSort::GetSubGraph(const SUnit &StartSU,
     574             :                                                          const SUnit &TargetSU,
     575             :                                                          bool &Success) {
     576             :   std::vector<const SUnit*> WorkList;
     577           0 :   int LowerBound = Node2Index[StartSU.NodeNum];
     578           0 :   int UpperBound = Node2Index[TargetSU.NodeNum];
     579             :   bool Found = false;
     580             :   BitVector VisitedBack;
     581             :   std::vector<int> Nodes;
     582             : 
     583           0 :   if (LowerBound > UpperBound) {
     584           0 :     Success = false;
     585           0 :     return Nodes;
     586             :   }
     587             : 
     588           0 :   WorkList.reserve(SUnits.size());
     589             :   Visited.reset();
     590             : 
     591             :   // Starting from StartSU, visit all successors up
     592             :   // to UpperBound.
     593           0 :   WorkList.push_back(&StartSU);
     594             :   do {
     595           0 :     const SUnit *SU = WorkList.back();
     596             :     WorkList.pop_back();
     597           0 :     for (int I = SU->Succs.size()-1; I >= 0; --I) {
     598           0 :       const SUnit *Succ = SU->Succs[I].getSUnit();
     599           0 :       unsigned s = Succ->NodeNum;
     600             :       // Edges to non-SUnits are allowed but ignored (e.g. ExitSU).
     601           0 :       if (Succ->isBoundaryNode())
     602           0 :         continue;
     603           0 :       if (Node2Index[s] == UpperBound) {
     604             :         Found = true;
     605           0 :         continue;
     606             :       }
     607             :       // Visit successors if not already and in affected region.
     608           0 :       if (!Visited.test(s) && Node2Index[s] < UpperBound) {
     609             :         Visited.set(s);
     610           0 :         WorkList.push_back(Succ);
     611             :       }
     612             :     }
     613           0 :   } while (!WorkList.empty());
     614             : 
     615           0 :   if (!Found) {
     616           0 :     Success = false;
     617           0 :     return Nodes;
     618             :   }
     619             : 
     620             :   WorkList.clear();
     621           0 :   VisitedBack.resize(SUnits.size());
     622             :   Found = false;
     623             : 
     624             :   // Starting from TargetSU, visit all predecessors up
     625             :   // to LowerBound. SUs that are visited by the two
     626             :   // passes are added to Nodes.
     627           0 :   WorkList.push_back(&TargetSU);
     628             :   do {
     629           0 :     const SUnit *SU = WorkList.back();
     630             :     WorkList.pop_back();
     631           0 :     for (int I = SU->Preds.size()-1; I >= 0; --I) {
     632           0 :       const SUnit *Pred = SU->Preds[I].getSUnit();
     633           0 :       unsigned s = Pred->NodeNum;
     634             :       // Edges to non-SUnits are allowed but ignored (e.g. EntrySU).
     635           0 :       if (Pred->isBoundaryNode())
     636           0 :         continue;
     637           0 :       if (Node2Index[s] == LowerBound) {
     638             :         Found = true;
     639           0 :         continue;
     640             :       }
     641           0 :       if (!VisitedBack.test(s) && Visited.test(s)) {
     642             :         VisitedBack.set(s);
     643           0 :         WorkList.push_back(Pred);
     644           0 :         Nodes.push_back(s);
     645             :       }
     646             :     }
     647           0 :   } while (!WorkList.empty());
     648             : 
     649             :   assert(Found && "Error in SUnit Graph!");
     650           0 :   Success = true;
     651           0 :   return Nodes;
     652             : }
     653             : 
     654       60655 : void ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound,
     655             :                                        int UpperBound) {
     656             :   std::vector<int> L;
     657             :   int shift = 0;
     658             :   int i;
     659             : 
     660     1466273 :   for (i = LowerBound; i <= UpperBound; ++i) {
     661             :     // w is node at topological index i.
     662     1405618 :     int w = Index2Node[i];
     663     1405618 :     if (Visited.test(w)) {
     664             :       // Unmark.
     665             :       Visited.reset(w);
     666      198183 :       L.push_back(w);
     667      198183 :       shift = shift + 1;
     668             :     } else {
     669      504626 :       Allocate(w, i - shift);
     670             :     }
     671             :   }
     672             : 
     673      258838 :   for (unsigned LI : L) {
     674      198183 :     Allocate(LI, i - shift);
     675      198183 :     i = i + 1;
     676             :   }
     677       60655 : }
     678             : 
     679       24730 : bool ScheduleDAGTopologicalSort::WillCreateCycle(SUnit *TargetSU, SUnit *SU) {
     680             :   // Is SU reachable from TargetSU via successor edges?
     681       24730 :   if (IsReachable(SU, TargetSU))
     682             :     return true;
     683        7504 :   for (const SDep &PredDep : TargetSU->Preds)
     684         931 :     if (PredDep.isAssignedRegDep() &&
     685         931 :         IsReachable(SU, PredDep.getSUnit()))
     686             :       return true;
     687             :   return false;
     688             : }
     689             : 
     690      161072 : bool ScheduleDAGTopologicalSort::IsReachable(const SUnit *SU,
     691             :                                              const SUnit *TargetSU) {
     692             :   // If insertion of the edge SU->TargetSU would create a cycle
     693             :   // then there is a path from TargetSU to SU.
     694             :   int UpperBound, LowerBound;
     695      322144 :   LowerBound = Node2Index[TargetSU->NodeNum];
     696      322144 :   UpperBound = Node2Index[SU->NodeNum];
     697      161072 :   bool HasLoop = false;
     698             :   // Is Ord(TargetSU) < Ord(SU) ?
     699      161072 :   if (LowerBound < UpperBound) {
     700             :     Visited.reset();
     701             :     // There may be a path from TargetSU to SU. Check for it.
     702       64668 :     DFS(TargetSU, UpperBound, HasLoop);
     703             :   }
     704      161072 :   return HasLoop;
     705             : }
     706             : 
     707     7973563 : void ScheduleDAGTopologicalSort::Allocate(int n, int index) {
     708    15947126 :   Node2Index[n] = index;
     709    15947126 :   Index2Node[index] = n;
     710     7973563 : }
     711             : 
     712      529571 : ScheduleDAGTopologicalSort::
     713      529571 : ScheduleDAGTopologicalSort(std::vector<SUnit> &sunits, SUnit *exitsu)
     714     1059142 :   : SUnits(sunits), ExitSU(exitsu) {}
     715             : 
     716             : ScheduleHazardRecognizer::~ScheduleHazardRecognizer() = default;

Generated by: LCOV version 1.13