LCOV - code coverage report
Current view: top level - lib/Target/AMDGPU - GCNMinRegStrategy.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 81 83 97.6 %
Date: 2018-07-13 00:08:38 Functions: 12 12 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- GCNMinRegStrategy.cpp ----------------------------------------------===//
       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             : #include "llvm/ADT/ArrayRef.h"
      11             : #include "llvm/ADT/SmallPtrSet.h"
      12             : #include "llvm/ADT/SmallVector.h"
      13             : #include "llvm/ADT/ilist_node.h"
      14             : #include "llvm/ADT/simple_ilist.h"
      15             : #include "llvm/CodeGen/ScheduleDAG.h"
      16             : #include "llvm/Support/Allocator.h"
      17             : #include "llvm/Support/Debug.h"
      18             : #include "llvm/Support/raw_ostream.h"
      19             : #include <cassert>
      20             : #include <cstdint>
      21             : #include <limits>
      22             : #include <vector>
      23             : 
      24             : using namespace llvm;
      25             : 
      26             : #define DEBUG_TYPE "machine-scheduler"
      27             : 
      28             : namespace {
      29             : 
      30          18 : class GCNMinRegScheduler {
      31             :   struct Candidate : ilist_node<Candidate> {
      32             :     const SUnit *SU;
      33             :     int Priority;
      34             : 
      35             :     Candidate(const SUnit *SU_, int Priority_ = 0)
      36        3924 :       : SU(SU_), Priority(Priority_) {}
      37             :   };
      38             : 
      39             :   SpecificBumpPtrAllocator<Candidate> Alloc;
      40             :   using Queue = simple_ilist<Candidate>;
      41             :   Queue RQ; // Ready queue
      42             : 
      43             :   std::vector<unsigned> NumPreds;
      44             : 
      45             :   bool isScheduled(const SUnit *SU) const {
      46             :     assert(!SU->isBoundaryNode());
      47      983616 :     return NumPreds[SU->NodeNum] == std::numeric_limits<unsigned>::max();
      48             :   }
      49             : 
      50             :   void setIsScheduled(const SUnit *SU)  {
      51             :     assert(!SU->isBoundaryNode());
      52        3940 :     NumPreds[SU->NodeNum] = std::numeric_limits<unsigned>::max();
      53             :   }
      54             : 
      55             :   unsigned getNumPreds(const SUnit *SU) const {
      56             :     assert(!SU->isBoundaryNode());
      57             :     assert(NumPreds[SU->NodeNum] != std::numeric_limits<unsigned>::max());
      58             :     return NumPreds[SU->NodeNum];
      59             :   }
      60             : 
      61             :   unsigned decNumPreds(const SUnit *SU) {
      62             :     assert(!SU->isBoundaryNode());
      63             :     assert(NumPreds[SU->NodeNum] != std::numeric_limits<unsigned>::max());
      64       29268 :     return --NumPreds[SU->NodeNum];
      65             :   }
      66             : 
      67             :   void initNumPreds(const decltype(ScheduleDAG::SUnits) &SUnits);
      68             : 
      69             :   int getReadySuccessors(const SUnit *SU) const;
      70             :   int getNotReadySuccessors(const SUnit *SU) const;
      71             : 
      72             :   template <typename Calc>
      73             :   unsigned findMax(unsigned Num, Calc C);
      74             : 
      75             :   Candidate* pickCandidate();
      76             : 
      77             :   void bumpPredsPriority(const SUnit *SchedSU, int Priority);
      78             :   void releaseSuccessors(const SUnit* SU, int Priority);
      79             : 
      80             : public:
      81             :   std::vector<const SUnit*> schedule(ArrayRef<const SUnit*> TopRoots,
      82             :                                      const ScheduleDAG &DAG);
      83             : };
      84             : 
      85             : } // end anonymous namespace
      86             : 
      87           6 : void GCNMinRegScheduler::initNumPreds(const decltype(ScheduleDAG::SUnits) &SUnits) {
      88          12 :   NumPreds.resize(SUnits.size());
      89        5922 :   for (unsigned I = 0; I < SUnits.size(); ++I)
      90        3940 :     NumPreds[I] = SUnits[I].NumPredsLeft;
      91           6 : }
      92             : 
      93       22354 : int GCNMinRegScheduler::getReadySuccessors(const SUnit *SU) const {
      94             :   unsigned NumSchedSuccs = 0;
      95      402546 :   for (auto SDep : SU->Succs) {
      96             :     bool wouldBeScheduled = true;
      97      338204 :     for (auto PDep : SDep.getSUnit()->Preds) {
      98             :       auto PSU = PDep.getSUnit();
      99             :       assert(!PSU->isBoundaryNode());
     100      470744 :       if (PSU != SU && !isScheduled(PSU)) {
     101             :         wouldBeScheduled = false;
     102             :         break;
     103             :       }
     104             :     }
     105      190096 :     NumSchedSuccs += wouldBeScheduled ? 1 : 0;
     106             :   }
     107       22354 :   return NumSchedSuccs;
     108             : }
     109             : 
     110             : int GCNMinRegScheduler::getNotReadySuccessors(const SUnit *SU) const {
     111       12442 :   return SU->Succs.size() - getReadySuccessors(SU);
     112             : }
     113             : 
     114             : template <typename Calc>
     115        2860 : unsigned GCNMinRegScheduler::findMax(unsigned Num, Calc C) {
     116             :   assert(!RQ.empty() && Num <= RQ.size());
     117             : 
     118             :   using T = decltype(C(*RQ.begin())) ;
     119             : 
     120             :   T Max = std::numeric_limits<T>::min();
     121             :   unsigned NumMax = 0;
     122      209332 :   for (auto I = RQ.begin(); Num; --Num) {
     123      103236 :     T Cur = C(*I);
     124      103236 :     if (Cur >= Max) {
     125       42102 :       if (Cur > Max) {
     126             :         Max = Cur;
     127             :         NumMax = 1;
     128             :       } else
     129       31810 :         ++NumMax;
     130             :       auto &Cand = *I++;
     131             :       RQ.remove(Cand);
     132             :       RQ.push_front(Cand);
     133       42102 :       continue;
     134             :     }
     135             :     ++I;
     136             :   }
     137        2860 :   return NumMax;
     138             : }
     139             : 
     140        1970 : GCNMinRegScheduler::Candidate* GCNMinRegScheduler::pickCandidate() {
     141             :   do {
     142        1970 :     unsigned Num = RQ.size();
     143        1970 :     if (Num == 1) break;
     144             : 
     145             :     LLVM_DEBUG(dbgs() << "\nSelecting max priority candidates among " << Num
     146             :                       << '\n');
     147        1772 :     Num = findMax(Num, [=](const Candidate &C) { return C.Priority; });
     148        1772 :     if (Num == 1) break;
     149             : 
     150             :     LLVM_DEBUG(dbgs() << "\nSelecting min non-ready producing candidate among "
     151             :                       << Num << '\n');
     152         472 :     Num = findMax(Num, [=](const Candidate &C) {
     153             :       auto SU = C.SU;
     154       12442 :       int Res = getNotReadySuccessors(SU);
     155             :       LLVM_DEBUG(dbgs() << "SU(" << SU->NodeNum << ") would left non-ready "
     156             :                         << Res << " successors, metric = " << -Res << '\n');
     157       12442 :       return -Res;
     158             :     });
     159         472 :     if (Num == 1) break;
     160             : 
     161             :     LLVM_DEBUG(dbgs() << "\nSelecting most producing candidate among " << Num
     162             :                       << '\n');
     163         308 :     Num = findMax(Num, [=](const Candidate &C) {
     164             :       auto SU = C.SU;
     165        7942 :       auto Res = getReadySuccessors(SU);
     166             :       LLVM_DEBUG(dbgs() << "SU(" << SU->NodeNum << ") would make ready " << Res
     167             :                         << " successors, metric = " << Res << '\n');
     168             :       return Res;
     169             :     });
     170         308 :     if (Num == 1) break;
     171             : 
     172         308 :     Num = Num ? Num : RQ.size();
     173             :     LLVM_DEBUG(
     174             :         dbgs()
     175             :         << "\nCan't find best candidate, selecting in program order among "
     176             :         << Num << '\n');
     177        8250 :     Num = findMax(Num, [=](const Candidate &C) { return -(int64_t)C.SU->NodeNum; });
     178             :     assert(Num == 1);
     179             :   } while (false);
     180             : 
     181        1970 :   return &RQ.front();
     182             : }
     183             : 
     184         656 : void GCNMinRegScheduler::bumpPredsPriority(const SUnit *SchedSU, int Priority) {
     185             :   SmallPtrSet<const SUnit*, 32> Set;
     186       15264 :   for (const auto &S : SchedSU->Succs) {
     187       21912 :     if (S.getSUnit()->isBoundaryNode() || isScheduled(S.getSUnit()) ||
     188             :         S.getKind() != SDep::Data)
     189        6490 :       continue;
     190       48954 :     for (const auto &P : S.getSUnit()->Preds) {
     191             :       auto PSU = P.getSUnit();
     192             :       assert(!PSU->isBoundaryNode());
     193       47326 :       if (PSU != SchedSU && !isScheduled(PSU)) {
     194       13810 :         Set.insert(PSU);
     195             :       }
     196             :     }
     197             :   }
     198         656 :   SmallVector<const SUnit*, 32> Worklist(Set.begin(), Set.end());
     199       24820 :   while (!Worklist.empty()) {
     200             :     auto SU = Worklist.pop_back_val();
     201             :     assert(!SU->isBoundaryNode());
     202      503536 :     for (const auto &P : SU->Preds) {
     203      574968 :       if (!P.getSUnit()->isBoundaryNode() && !isScheduled(P.getSUnit()) &&
     204      322638 :           Set.insert(P.getSUnit()).second)
     205       12644 :         Worklist.push_back(P.getSUnit());
     206             :     }
     207             :   }
     208             :   LLVM_DEBUG(dbgs() << "Make the predecessors of SU(" << SchedSU->NodeNum
     209             :                     << ")'s non-ready successors of " << Priority
     210             :                     << " priority in ready queue: ");
     211         656 :   const auto SetEnd = Set.end();
     212       27174 :   for (auto &C : RQ) {
     213       26518 :     if (Set.find(C.SU) != SetEnd) {
     214        9604 :       C.Priority = Priority;
     215             :       LLVM_DEBUG(dbgs() << " SU(" << C.SU->NodeNum << ')');
     216             :     }
     217             :   }
     218             :   LLVM_DEBUG(dbgs() << '\n');
     219         656 : }
     220             : 
     221        1976 : void GCNMinRegScheduler::releaseSuccessors(const SUnit* SU, int Priority) {
     222       31244 :   for (const auto &S : SU->Succs) {
     223             :     auto SuccSU = S.getSUnit();
     224           0 :     if (S.isWeak())
     225           0 :       continue;
     226             :     assert(SuccSU->isBoundaryNode() || getNumPreds(SuccSU) > 0);
     227       29268 :     if (!SuccSU->isBoundaryNode() && decNumPreds(SuccSU) == 0)
     228             :       RQ.push_front(*new (Alloc.Allocate()) Candidate(SuccSU, Priority));
     229             :   }
     230        1976 : }
     231             : 
     232             : std::vector<const SUnit*>
     233           6 : GCNMinRegScheduler::schedule(ArrayRef<const SUnit*> TopRoots,
     234             :                              const ScheduleDAG &DAG) {
     235           6 :   const auto &SUnits = DAG.SUnits;
     236             :   std::vector<const SUnit*> Schedule;
     237          12 :   Schedule.reserve(SUnits.size());
     238             : 
     239           6 :   initNumPreds(SUnits);
     240             : 
     241             :   int StepNo = 0;
     242             : 
     243          38 :   for (auto SU : TopRoots) {
     244             :     RQ.push_back(*new (Alloc.Allocate()) Candidate(SU, StepNo));
     245             :   }
     246           6 :   releaseSuccessors(&DAG.EntrySU, StepNo);
     247             : 
     248        3946 :   while (!RQ.empty()) {
     249             :     LLVM_DEBUG(dbgs() << "\n=== Picking candidate, Step = " << StepNo
     250             :                       << "\n"
     251             :                          "Ready queue:";
     252             :                for (auto &C
     253             :                     : RQ) dbgs()
     254             :                << ' ' << C.SU->NodeNum << "(P" << C.Priority << ')';
     255             :                dbgs() << '\n';);
     256             : 
     257        1970 :     auto C = pickCandidate();
     258             :     assert(C);
     259             :     RQ.remove(*C);
     260        1970 :     auto SU = C->SU;
     261             :     LLVM_DEBUG(dbgs() << "Selected "; SU->dump(&DAG));
     262             : 
     263        1970 :     releaseSuccessors(SU, StepNo);
     264        1970 :     Schedule.push_back(SU);
     265        1970 :     setIsScheduled(SU);
     266             : 
     267        1970 :     if (getReadySuccessors(SU) == 0)
     268         656 :       bumpPredsPriority(SU, StepNo);
     269             : 
     270        1970 :     ++StepNo;
     271             :   }
     272             :   assert(SUnits.size() == Schedule.size());
     273             : 
     274           6 :   return Schedule;
     275             : }
     276             : 
     277             : namespace llvm {
     278             : 
     279           6 : std::vector<const SUnit*> makeMinRegSchedule(ArrayRef<const SUnit*> TopRoots,
     280             :                                              const ScheduleDAG &DAG) {
     281           6 :   GCNMinRegScheduler S;
     282          12 :   return S.schedule(TopRoots, DAG);
     283             : }
     284             : 
     285             : } // end namespace llvm

Generated by: LCOV version 1.13