LCOV - code coverage report
Current view: top level - lib/Target/AMDGPU - GCNMinRegStrategy.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 102 103 99.0 %
Date: 2017-09-14 15:23:50 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          42 : 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        4116 :       : 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     1025712 :     return NumPreds[SU->NodeNum] == std::numeric_limits<unsigned>::max();
      48             :   }
      49             : 
      50             :   void setIsScheduled(const SUnit *SU)  {
      51             :     assert(!SU->isBoundaryNode());
      52        4116 :     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       29444 :     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        4128 :   for (unsigned I = 0; I < SUnits.size(); ++I)
      90        6174 :     NumPreds[I] = SUnits[I].NumPredsLeft;
      91           6 : }
      92             : 
      93       27034 : int GCNMinRegScheduler::getReadySuccessors(const SUnit *SU) const {
      94       27034 :   unsigned NumSchedSuccs = 0;
      95      276286 :   for (auto SDep : SU->Succs) {
      96      195184 :     bool wouldBeScheduled = true;
      97      663752 :     for (auto PDep : SDep.getSUnit()->Preds) {
      98      257828 :       auto PSU = PDep.getSUnit();
      99             :       assert(!PSU->isBoundaryNode());
     100      479702 :       if (PSU != SU && !isScheduled(PSU)) {
     101             :         wouldBeScheduled = false;
     102             :         break;
     103             :       }
     104             :     }
     105      195184 :     NumSchedSuccs += wouldBeScheduled ? 1 : 0;
     106             :   }
     107       27034 :   return NumSchedSuccs;
     108             : }
     109             : 
     110             : int GCNMinRegScheduler::getNotReadySuccessors(const SUnit *SU) const {
     111       29492 :   return SU->Succs.size() - getReadySuccessors(SU);
     112             : }
     113             : 
     114             : template <typename Calc>
     115        3540 : unsigned GCNMinRegScheduler::findMax(unsigned Num, Calc C) {
     116             :   assert(!RQ.empty() && Num <= RQ.size());
     117             : 
     118             :   using T = decltype(C(*RQ.begin())) ;
     119             : 
     120        3540 :   T Max = std::numeric_limits<T>::min();
     121        3540 :   unsigned NumMax = 0;
     122      127440 :   for (auto I = RQ.begin(); Num; --Num) {
     123      155406 :     T Cur = C(*I);
     124      120360 :     if (Cur >= Max) {
     125       51052 :       if (Cur > Max) {
     126             :         Max = Cur;
     127             :         NumMax = 1;
     128             :       } else
     129       38110 :         ++NumMax;
     130      153156 :       auto &Cand = *I++;
     131      102104 :       RQ.remove(Cand);
     132      102104 :       RQ.push_front(Cand);
     133       51052 :       continue;
     134             :     }
     135             :     ++I;
     136             :   }
     137        3540 :   return NumMax;
     138             : }
     139             : 
     140        2058 : GCNMinRegScheduler::Candidate* GCNMinRegScheduler::pickCandidate() {
     141             :   do {
     142        4116 :     unsigned Num = RQ.size();
     143        2058 :     if (Num == 1) break;
     144             : 
     145             :     DEBUG(dbgs() << "\nSelecting max priority candidates among " << Num << '\n');
     146        2032 :     Num = findMax(Num, [=](const Candidate &C) { return C.Priority; });
     147        2032 :     if (Num == 1) break;
     148             : 
     149             :     DEBUG(dbgs() << "\nSelecting min non-ready producing candidate among "
     150             :                  << Num << '\n');
     151         644 :     Num = findMax(Num, [=](const Candidate &C) {
     152       14746 :       auto SU = C.SU;
     153       29492 :       int Res = getNotReadySuccessors(SU);
     154             :       DEBUG(dbgs() << "SU(" << SU->NodeNum << ") would left non-ready "
     155             :                    << Res << " successors, metric = " << -Res << '\n');
     156       14746 :       return -Res;
     157             :     });
     158         644 :     if (Num == 1) break;
     159             : 
     160             :     DEBUG(dbgs() << "\nSelecting most producing candidate among "
     161             :                  << Num << '\n');
     162         472 :     Num = findMax(Num, [=](const Candidate &C) {
     163       10230 :       auto SU = C.SU;
     164       10230 :       auto Res = getReadySuccessors(SU);
     165             :       DEBUG(dbgs() << "SU(" << SU->NodeNum << ") would make ready "
     166             :                    << Res << " successors, metric = " << Res << '\n');
     167             :       return Res;
     168             :     });
     169         472 :     if (Num == 1) break;
     170             : 
     171         392 :     Num = Num ? Num : RQ.size();
     172             :     DEBUG(dbgs() << "\nCan't find best candidate, selecting in program order among "
     173             :                  << Num << '\n');
     174       10462 :     Num = findMax(Num, [=](const Candidate &C) { return -(int64_t)C.SU->NodeNum; });
     175             :     assert(Num == 1);
     176             :   } while (false);
     177             : 
     178        4116 :   return &RQ.front();
     179             : }
     180             : 
     181         744 : void GCNMinRegScheduler::bumpPredsPriority(const SUnit *SchedSU, int Priority) {
     182        1488 :   SmallPtrSet<const SUnit*, 32> Set;
     183        9624 :   for (const auto &S : SchedSU->Succs) {
     184       29568 :     if (S.getSUnit()->isBoundaryNode() || isScheduled(S.getSUnit()) ||
     185        7392 :         S.getKind() != SDep::Data)
     186        6490 :       continue;
     187       36518 :     for (const auto &P : S.getSUnit()->Preds) {
     188       33812 :       auto PSU = P.getSUnit();
     189             :       assert(!PSU->isBoundaryNode());
     190       66722 :       if (PSU != SchedSU && !isScheduled(PSU)) {
     191       14160 :         Set.insert(PSU);
     192             :       }
     193             :     }
     194             :   }
     195        1488 :   SmallVector<const SUnit*, 32> Worklist(Set.begin(), Set.end());
     196       27078 :   while (!Worklist.empty()) {
     197       26334 :     auto SU = Worklist.pop_back_val();
     198             :     assert(!SU->isBoundaryNode());
     199      329682 :     for (const auto &P : SU->Preds) {
     200      850394 :       if (!P.getSUnit()->isBoundaryNode() && !isScheduled(P.getSUnit()) &&
     201      334570 :           Set.insert(P.getSUnit()).second)
     202       14464 :         Worklist.push_back(P.getSUnit());
     203             :     }
     204             :   }
     205             :   DEBUG(dbgs() << "Make the predecessors of SU(" << SchedSU->NodeNum
     206             :                << ")'s non-ready successors of " << Priority
     207             :                << " priority in ready queue: ");
     208         744 :   const auto SetEnd = Set.end();
     209       32842 :   for (auto &C : RQ) {
     210       30610 :     if (Set.find(C.SU) != SetEnd) {
     211        9860 :       C.Priority = Priority;
     212             :       DEBUG(dbgs() << " SU(" << C.SU->NodeNum << ')');
     213             :     }
     214             :   }
     215             :   DEBUG(dbgs() << '\n');
     216         744 : }
     217             : 
     218        2064 : void GCNMinRegScheduler::releaseSuccessors(const SUnit* SU, int Priority) {
     219       20914 :   for (const auto &S : SU->Succs) {
     220       14722 :     auto SuccSU = S.getSUnit();
     221       14722 :     if (S.isWeak())
     222           0 :       continue;
     223             :     assert(SuccSU->isBoundaryNode() || getNumPreds(SuccSU) > 0);
     224       29444 :     if (!SuccSU->isBoundaryNode() && decNumPreds(SuccSU) == 0)
     225        6126 :       RQ.push_front(*new (Alloc.Allocate()) Candidate(SuccSU, Priority));
     226             :   }
     227        2064 : }
     228             : 
     229             : std::vector<const SUnit*>
     230           6 : GCNMinRegScheduler::schedule(ArrayRef<const SUnit*> TopRoots,
     231             :                              const ScheduleDAG &DAG) {
     232           6 :   const auto &SUnits = DAG.SUnits;
     233           6 :   std::vector<const SUnit*> Schedule;
     234          12 :   Schedule.reserve(SUnits.size());
     235             : 
     236           6 :   initNumPreds(SUnits);
     237             : 
     238           6 :   int StepNo = 0;
     239             : 
     240          28 :   for (auto SU : TopRoots) {
     241          64 :     RQ.push_back(*new (Alloc.Allocate()) Candidate(SU, StepNo));
     242             :   }
     243           6 :   releaseSuccessors(&DAG.EntrySU, StepNo);
     244             : 
     245        6186 :   while (!RQ.empty()) {
     246             :     DEBUG(
     247             :       dbgs() << "\n=== Picking candidate, Step = " << StepNo << "\n"
     248             :                 "Ready queue:";
     249             :       for (auto &C : RQ)
     250             :         dbgs() << ' ' << C.SU->NodeNum << "(P" << C.Priority << ')';
     251             :       dbgs() << '\n';
     252             :     );
     253             : 
     254        2058 :     auto C = pickCandidate();
     255             :     assert(C);
     256        4116 :     RQ.remove(*C);
     257        2058 :     auto SU = C->SU;
     258             :     DEBUG(dbgs() << "Selected "; SU->dump(&DAG));
     259             : 
     260        2058 :     releaseSuccessors(SU, StepNo);
     261        2058 :     Schedule.push_back(SU);
     262        4116 :     setIsScheduled(SU);
     263             : 
     264        2058 :     if (getReadySuccessors(SU) == 0)
     265         744 :       bumpPredsPriority(SU, StepNo);
     266             : 
     267        2058 :     ++StepNo;
     268             :   }
     269             :   assert(SUnits.size() == Schedule.size());
     270             : 
     271           6 :   return Schedule;
     272             : }
     273             : 
     274             : namespace llvm {
     275             : 
     276           6 : std::vector<const SUnit*> makeMinRegSchedule(ArrayRef<const SUnit*> TopRoots,
     277             :                                              const ScheduleDAG &DAG) {
     278          12 :   GCNMinRegScheduler S;
     279          12 :   return S.schedule(TopRoots, DAG);
     280             : }
     281             : 
     282             : } // end namespace llvm

Generated by: LCOV version 1.13