LCOV - code coverage report
Current view: top level - lib/Target/AMDGPU - AMDGPUMachineCFGStructurizer.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 2 886 0.2 %
Date: 2018-02-22 04:41:24 Functions: 1 99 1.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- AMDGPUMachineCFGStructurizer.cpp - Machine code if conversion pass. ===//
       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             : // This file implements the machine instruction level CFG structurizer pass.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #include "AMDGPU.h"
      15             : #include "AMDGPUSubtarget.h"
      16             : #include "SIInstrInfo.h"
      17             : #include "llvm/ADT/ArrayRef.h"
      18             : #include "llvm/ADT/DenseMap.h"
      19             : #include "llvm/ADT/DenseSet.h"
      20             : #include "llvm/ADT/PostOrderIterator.h"
      21             : #include "llvm/ADT/SetVector.h"
      22             : #include "llvm/ADT/SmallPtrSet.h"
      23             : #include "llvm/ADT/SmallVector.h"
      24             : #include "llvm/CodeGen/MachineBasicBlock.h"
      25             : #include "llvm/CodeGen/MachineFunction.h"
      26             : #include "llvm/CodeGen/MachineFunctionPass.h"
      27             : #include "llvm/CodeGen/MachineInstr.h"
      28             : #include "llvm/CodeGen/MachineInstrBuilder.h"
      29             : #include "llvm/CodeGen/MachineOperand.h"
      30             : #include "llvm/CodeGen/MachineRegionInfo.h"
      31             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      32             : #include "llvm/CodeGen/TargetOpcodes.h"
      33             : #include "llvm/CodeGen/TargetRegisterInfo.h"
      34             : #include "llvm/IR/DebugLoc.h"
      35             : #include "llvm/Pass.h"
      36             : #include "llvm/Support/Compiler.h"
      37             : #include "llvm/Support/Debug.h"
      38             : #include "llvm/Support/ErrorHandling.h"
      39             : #include "llvm/Support/raw_ostream.h"
      40             : #include <cassert>
      41             : #include <tuple>
      42             : #include <utility>
      43             : 
      44             : using namespace llvm;
      45             : 
      46             : #define DEBUG_TYPE "amdgpucfgstructurizer"
      47             : 
      48             : namespace {
      49             : 
      50             : class PHILinearizeDestIterator;
      51             : 
      52           0 : class PHILinearize {
      53             :   friend class PHILinearizeDestIterator;
      54             : 
      55             : public:
      56             :   using PHISourceT = std::pair<unsigned, MachineBasicBlock *>;
      57             : 
      58             : private:
      59             :   using PHISourcesT = DenseSet<PHISourceT>;
      60           0 :   using PHIInfoElementT = struct {
      61             :     unsigned DestReg;
      62             :     DebugLoc DL;
      63             :     PHISourcesT Sources;
      64             :   };
      65             :   using PHIInfoT = SmallPtrSet<PHIInfoElementT *, 2>;
      66             :   PHIInfoT PHIInfo;
      67             : 
      68             :   static unsigned phiInfoElementGetDest(PHIInfoElementT *Info);
      69             :   static void phiInfoElementSetDef(PHIInfoElementT *Info, unsigned NewDef);
      70             :   static PHISourcesT &phiInfoElementGetSources(PHIInfoElementT *Info);
      71             :   static void phiInfoElementAddSource(PHIInfoElementT *Info, unsigned SourceReg,
      72             :                                       MachineBasicBlock *SourceMBB);
      73             :   static void phiInfoElementRemoveSource(PHIInfoElementT *Info,
      74             :                                          unsigned SourceReg,
      75             :                                          MachineBasicBlock *SourceMBB);
      76             :   PHIInfoElementT *findPHIInfoElement(unsigned DestReg);
      77             :   PHIInfoElementT *findPHIInfoElementFromSource(unsigned SourceReg,
      78             :                                                 MachineBasicBlock *SourceMBB);
      79             : 
      80             : public:
      81             :   bool findSourcesFromMBB(MachineBasicBlock *SourceMBB,
      82             :                           SmallVector<unsigned, 4> &Sources);
      83             :   void addDest(unsigned DestReg, const DebugLoc &DL);
      84             :   void replaceDef(unsigned OldDestReg, unsigned NewDestReg);
      85             :   void deleteDef(unsigned DestReg);
      86             :   void addSource(unsigned DestReg, unsigned SourceReg,
      87             :                  MachineBasicBlock *SourceMBB);
      88             :   void removeSource(unsigned DestReg, unsigned SourceReg,
      89             :                     MachineBasicBlock *SourceMBB = nullptr);
      90             :   bool findDest(unsigned SourceReg, MachineBasicBlock *SourceMBB,
      91             :                 unsigned &DestReg);
      92             :   bool isSource(unsigned Reg, MachineBasicBlock *SourceMBB = nullptr);
      93             :   unsigned getNumSources(unsigned DestReg);
      94             :   void dump(MachineRegisterInfo *MRI);
      95             :   void clear();
      96             : 
      97             :   using source_iterator = PHISourcesT::iterator;
      98             :   using dest_iterator = PHILinearizeDestIterator;
      99             : 
     100             :   dest_iterator dests_begin();
     101             :   dest_iterator dests_end();
     102             : 
     103             :   source_iterator sources_begin(unsigned Reg);
     104             :   source_iterator sources_end(unsigned Reg);
     105             : };
     106             : 
     107             : class PHILinearizeDestIterator {
     108             : private:
     109             :   PHILinearize::PHIInfoT::iterator Iter;
     110             : 
     111             : public:
     112             :   PHILinearizeDestIterator(PHILinearize::PHIInfoT::iterator I) : Iter(I) {}
     113             : 
     114           0 :   unsigned operator*() { return PHILinearize::phiInfoElementGetDest(*Iter); }
     115             :   PHILinearizeDestIterator &operator++() {
     116             :     ++Iter;
     117             :     return *this;
     118             :   }
     119             :   bool operator==(const PHILinearizeDestIterator &I) const {
     120             :     return I.Iter == Iter;
     121             :   }
     122             :   bool operator!=(const PHILinearizeDestIterator &I) const {
     123             :     return I.Iter != Iter;
     124             :   }
     125             : };
     126             : 
     127             : } // end anonymous namespace
     128             : 
     129             : unsigned PHILinearize::phiInfoElementGetDest(PHIInfoElementT *Info) {
     130             :   return Info->DestReg;
     131             : }
     132             : 
     133             : void PHILinearize::phiInfoElementSetDef(PHIInfoElementT *Info,
     134             :                                         unsigned NewDef) {
     135           0 :   Info->DestReg = NewDef;
     136             : }
     137             : 
     138             : PHILinearize::PHISourcesT &
     139             : PHILinearize::phiInfoElementGetSources(PHIInfoElementT *Info) {
     140             :   return Info->Sources;
     141             : }
     142             : 
     143             : void PHILinearize::phiInfoElementAddSource(PHIInfoElementT *Info,
     144             :                                            unsigned SourceReg,
     145             :                                            MachineBasicBlock *SourceMBB) {
     146             :   // Assertion ensures we don't use the same SourceMBB for the
     147             :   // sources, because we cannot have different registers with
     148             :   // identical predecessors, but we can have the same register for
     149             :   // multiple predecessors.
     150             : #if !defined(NDEBUG)
     151             :   for (auto SI : phiInfoElementGetSources(Info)) {
     152             :     assert((SI.second != SourceMBB || SourceReg == SI.first));
     153             :   }
     154             : #endif
     155             : 
     156           0 :   phiInfoElementGetSources(Info).insert(PHISourceT(SourceReg, SourceMBB));
     157             : }
     158             : 
     159           0 : void PHILinearize::phiInfoElementRemoveSource(PHIInfoElementT *Info,
     160             :                                               unsigned SourceReg,
     161             :                                               MachineBasicBlock *SourceMBB) {
     162             :   auto &Sources = phiInfoElementGetSources(Info);
     163             :   SmallVector<PHISourceT, 4> ElimiatedSources;
     164           0 :   for (auto SI : Sources) {
     165           0 :     if (SI.first == SourceReg &&
     166           0 :         (SI.second == nullptr || SI.second == SourceMBB)) {
     167           0 :       ElimiatedSources.push_back(PHISourceT(SI.first, SI.second));
     168             :     }
     169             :   }
     170             : 
     171           0 :   for (auto &Source : ElimiatedSources) {
     172             :     Sources.erase(Source);
     173             :   }
     174           0 : }
     175             : 
     176             : PHILinearize::PHIInfoElementT *
     177           0 : PHILinearize::findPHIInfoElement(unsigned DestReg) {
     178           0 :   for (auto I : PHIInfo) {
     179           0 :     if (phiInfoElementGetDest(I) == DestReg) {
     180           0 :       return I;
     181             :     }
     182             :   }
     183           0 :   return nullptr;
     184             : }
     185             : 
     186             : PHILinearize::PHIInfoElementT *
     187           0 : PHILinearize::findPHIInfoElementFromSource(unsigned SourceReg,
     188             :                                            MachineBasicBlock *SourceMBB) {
     189           0 :   for (auto I : PHIInfo) {
     190           0 :     for (auto SI : phiInfoElementGetSources(I)) {
     191           0 :       if (SI.first == SourceReg &&
     192           0 :           (SI.second == nullptr || SI.second == SourceMBB)) {
     193           0 :         return I;
     194             :       }
     195             :     }
     196             :   }
     197           0 :   return nullptr;
     198             : }
     199             : 
     200           0 : bool PHILinearize::findSourcesFromMBB(MachineBasicBlock *SourceMBB,
     201             :                                       SmallVector<unsigned, 4> &Sources) {
     202             :   bool FoundSource = false;
     203           0 :   for (auto I : PHIInfo) {
     204           0 :     for (auto SI : phiInfoElementGetSources(I)) {
     205           0 :       if (SI.second == SourceMBB) {
     206             :         FoundSource = true;
     207           0 :         Sources.push_back(SI.first);
     208             :       }
     209             :     }
     210             :   }
     211           0 :   return FoundSource;
     212             : }
     213             : 
     214           0 : void PHILinearize::addDest(unsigned DestReg, const DebugLoc &DL) {
     215             :   assert(findPHIInfoElement(DestReg) == nullptr && "Dest already exsists");
     216             :   PHISourcesT EmptySet;
     217           0 :   PHIInfoElementT *NewElement = new PHIInfoElementT();
     218           0 :   NewElement->DestReg = DestReg;
     219             :   NewElement->DL = DL;
     220             :   NewElement->Sources = EmptySet;
     221           0 :   PHIInfo.insert(NewElement);
     222           0 : }
     223             : 
     224             : void PHILinearize::replaceDef(unsigned OldDestReg, unsigned NewDestReg) {
     225           0 :   phiInfoElementSetDef(findPHIInfoElement(OldDestReg), NewDestReg);
     226             : }
     227             : 
     228           0 : void PHILinearize::deleteDef(unsigned DestReg) {
     229           0 :   PHIInfoElementT *InfoElement = findPHIInfoElement(DestReg);
     230             :   PHIInfo.erase(InfoElement);
     231           0 :   delete InfoElement;
     232           0 : }
     233             : 
     234           0 : void PHILinearize::addSource(unsigned DestReg, unsigned SourceReg,
     235             :                              MachineBasicBlock *SourceMBB) {
     236           0 :   phiInfoElementAddSource(findPHIInfoElement(DestReg), SourceReg, SourceMBB);
     237           0 : }
     238             : 
     239             : void PHILinearize::removeSource(unsigned DestReg, unsigned SourceReg,
     240             :                                 MachineBasicBlock *SourceMBB) {
     241           0 :   phiInfoElementRemoveSource(findPHIInfoElement(DestReg), SourceReg, SourceMBB);
     242             : }
     243             : 
     244             : bool PHILinearize::findDest(unsigned SourceReg, MachineBasicBlock *SourceMBB,
     245             :                             unsigned &DestReg) {
     246             :   PHIInfoElementT *InfoElement =
     247           0 :       findPHIInfoElementFromSource(SourceReg, SourceMBB);
     248           0 :   if (InfoElement != nullptr) {
     249           0 :     DestReg = phiInfoElementGetDest(InfoElement);
     250             :     return true;
     251             :   }
     252             :   return false;
     253             : }
     254             : 
     255             : bool PHILinearize::isSource(unsigned Reg, MachineBasicBlock *SourceMBB) {
     256             :   unsigned DestReg;
     257             :   return findDest(Reg, SourceMBB, DestReg);
     258             : }
     259             : 
     260             : unsigned PHILinearize::getNumSources(unsigned DestReg) {
     261           0 :   return phiInfoElementGetSources(findPHIInfoElement(DestReg)).size();
     262             : }
     263             : 
     264             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     265             : LLVM_DUMP_METHOD void PHILinearize::dump(MachineRegisterInfo *MRI) {
     266             :   const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
     267             :   dbgs() << "=PHIInfo Start=\n";
     268             :   for (auto PII : this->PHIInfo) {
     269             :     PHIInfoElementT &Element = *PII;
     270             :     dbgs() << "Dest: " << printReg(Element.DestReg, TRI)
     271             :            << " Sources: {";
     272             :     for (auto &SI : Element.Sources) {
     273             :       dbgs() << printReg(SI.first, TRI) << '(' << printMBBReference(*SI.second)
     274             :              << "),";
     275             :     }
     276             :     dbgs() << "}\n";
     277             :   }
     278             :   dbgs() << "=PHIInfo End=\n";
     279             : }
     280             : #endif
     281             : 
     282           0 : void PHILinearize::clear() { PHIInfo = PHIInfoT(); }
     283             : 
     284             : PHILinearize::dest_iterator PHILinearize::dests_begin() {
     285           0 :   return PHILinearizeDestIterator(PHIInfo.begin());
     286             : }
     287             : 
     288             : PHILinearize::dest_iterator PHILinearize::dests_end() {
     289           0 :   return PHILinearizeDestIterator(PHIInfo.end());
     290             : }
     291             : 
     292           0 : PHILinearize::source_iterator PHILinearize::sources_begin(unsigned Reg) {
     293           0 :   auto InfoElement = findPHIInfoElement(Reg);
     294           0 :   return phiInfoElementGetSources(InfoElement).begin();
     295             : }
     296             : 
     297             : PHILinearize::source_iterator PHILinearize::sources_end(unsigned Reg) {
     298           0 :   auto InfoElement = findPHIInfoElement(Reg);
     299             :   return phiInfoElementGetSources(InfoElement).end();
     300             : }
     301             : 
     302             : static unsigned getPHINumInputs(MachineInstr &PHI) {
     303             :   assert(PHI.isPHI());
     304           0 :   return (PHI.getNumOperands() - 1) / 2;
     305             : }
     306             : 
     307             : static MachineBasicBlock *getPHIPred(MachineInstr &PHI, unsigned Index) {
     308             :   assert(PHI.isPHI());
     309           0 :   return PHI.getOperand(Index * 2 + 2).getMBB();
     310             : }
     311             : 
     312             : static void setPhiPred(MachineInstr &PHI, unsigned Index,
     313             :                        MachineBasicBlock *NewPred) {
     314             :   PHI.getOperand(Index * 2 + 2).setMBB(NewPred);
     315             : }
     316             : 
     317             : static unsigned getPHISourceReg(MachineInstr &PHI, unsigned Index) {
     318             :   assert(PHI.isPHI());
     319           0 :   return PHI.getOperand(Index * 2 + 1).getReg();
     320             : }
     321             : 
     322             : static unsigned getPHIDestReg(MachineInstr &PHI) {
     323             :   assert(PHI.isPHI());
     324           0 :   return PHI.getOperand(0).getReg();
     325             : }
     326             : 
     327             : namespace {
     328             : 
     329             : class RegionMRT;
     330             : class MBBMRT;
     331             : 
     332             : class LinearizedRegion {
     333             : protected:
     334             :   MachineBasicBlock *Entry;
     335             :   // The exit block is part of the region, and is the last
     336             :   // merge block before exiting the region.
     337             :   MachineBasicBlock *Exit;
     338             :   DenseSet<unsigned> LiveOuts;
     339             :   SmallPtrSet<MachineBasicBlock *, 1> MBBs;
     340             :   bool HasLoop;
     341             :   LinearizedRegion *Parent;
     342             :   RegionMRT *RMRT;
     343             : 
     344             :   void storeLiveOutReg(MachineBasicBlock *MBB, unsigned Reg,
     345             :                        MachineInstr *DefInstr, const MachineRegisterInfo *MRI,
     346             :                        const TargetRegisterInfo *TRI, PHILinearize &PHIInfo);
     347             : 
     348             :   void storeLiveOutRegRegion(RegionMRT *Region, unsigned Reg,
     349             :                              MachineInstr *DefInstr,
     350             :                              const MachineRegisterInfo *MRI,
     351             :                              const TargetRegisterInfo *TRI,
     352             :                              PHILinearize &PHIInfo);
     353             : 
     354             :   void storeMBBLiveOuts(MachineBasicBlock *MBB, const MachineRegisterInfo *MRI,
     355             :                         const TargetRegisterInfo *TRI, PHILinearize &PHIInfo,
     356             :                         RegionMRT *TopRegion);
     357             : 
     358             :   void storeLiveOuts(MachineBasicBlock *MBB, const MachineRegisterInfo *MRI,
     359             :                      const TargetRegisterInfo *TRI, PHILinearize &PHIInfo);
     360             : 
     361             :   void storeLiveOuts(RegionMRT *Region, const MachineRegisterInfo *MRI,
     362             :                      const TargetRegisterInfo *TRI, PHILinearize &PHIInfo,
     363             :                      RegionMRT *TopRegion = nullptr);
     364             : 
     365             : public:
     366             :   LinearizedRegion();
     367             :   LinearizedRegion(MachineBasicBlock *MBB, const MachineRegisterInfo *MRI,
     368             :                    const TargetRegisterInfo *TRI, PHILinearize &PHIInfo);
     369           0 :   ~LinearizedRegion() = default;
     370             : 
     371           0 :   void setRegionMRT(RegionMRT *Region) { RMRT = Region; }
     372             : 
     373             :   RegionMRT *getRegionMRT() { return RMRT; }
     374             : 
     375           0 :   void setParent(LinearizedRegion *P) { Parent = P; }
     376             : 
     377             :   LinearizedRegion *getParent() { return Parent; }
     378             : 
     379             :   void print(raw_ostream &OS, const TargetRegisterInfo *TRI = nullptr);
     380             : 
     381             :   void setBBSelectRegIn(unsigned Reg);
     382             : 
     383             :   unsigned getBBSelectRegIn();
     384             : 
     385             :   void setBBSelectRegOut(unsigned Reg, bool IsLiveOut);
     386             : 
     387             :   unsigned getBBSelectRegOut();
     388             : 
     389             :   void setHasLoop(bool Value);
     390             : 
     391             :   bool getHasLoop();
     392             : 
     393             :   void addLiveOut(unsigned VReg);
     394             : 
     395             :   void removeLiveOut(unsigned Reg);
     396             : 
     397             :   void replaceLiveOut(unsigned OldReg, unsigned NewReg);
     398             : 
     399             :   void replaceRegister(unsigned Register, unsigned NewRegister,
     400             :                        MachineRegisterInfo *MRI, bool ReplaceInside,
     401             :                        bool ReplaceOutside, bool IncludeLoopPHIs);
     402             : 
     403             :   void replaceRegisterInsideRegion(unsigned Register, unsigned NewRegister,
     404             :                                    bool IncludeLoopPHIs,
     405             :                                    MachineRegisterInfo *MRI);
     406             : 
     407             :   void replaceRegisterOutsideRegion(unsigned Register, unsigned NewRegister,
     408             :                                     bool IncludeLoopPHIs,
     409             :                                     MachineRegisterInfo *MRI);
     410             : 
     411             :   DenseSet<unsigned> *getLiveOuts();
     412             : 
     413             :   void setEntry(MachineBasicBlock *NewEntry);
     414             : 
     415             :   MachineBasicBlock *getEntry();
     416             : 
     417             :   void setExit(MachineBasicBlock *NewExit);
     418             : 
     419             :   MachineBasicBlock *getExit();
     420             : 
     421             :   void addMBB(MachineBasicBlock *MBB);
     422             : 
     423             :   void addMBBs(LinearizedRegion *InnerRegion);
     424             : 
     425             :   bool contains(MachineBasicBlock *MBB);
     426             : 
     427             :   bool isLiveOut(unsigned Reg);
     428             : 
     429             :   bool hasNoDef(unsigned Reg, MachineRegisterInfo *MRI);
     430             : 
     431             :   void removeFalseRegisterKills(MachineRegisterInfo *MRI);
     432             : 
     433             :   void initLiveOut(RegionMRT *Region, const MachineRegisterInfo *MRI,
     434             :                    const TargetRegisterInfo *TRI, PHILinearize &PHIInfo);
     435             : };
     436             : 
     437             : class MRT {
     438             : protected:
     439             :   RegionMRT *Parent;
     440             :   unsigned BBSelectRegIn;
     441             :   unsigned BBSelectRegOut;
     442             : 
     443             : public:
     444             :   virtual ~MRT() = default;
     445             : 
     446             :   unsigned getBBSelectRegIn() { return BBSelectRegIn; }
     447             : 
     448             :   unsigned getBBSelectRegOut() { return BBSelectRegOut; }
     449             : 
     450           0 :   void setBBSelectRegIn(unsigned Reg) { BBSelectRegIn = Reg; }
     451             : 
     452           0 :   void setBBSelectRegOut(unsigned Reg) { BBSelectRegOut = Reg; }
     453             : 
     454           0 :   virtual RegionMRT *getRegionMRT() { return nullptr; }
     455             : 
     456           0 :   virtual MBBMRT *getMBBMRT() { return nullptr; }
     457             : 
     458           0 :   bool isRegion() { return getRegionMRT() != nullptr; }
     459             : 
     460           0 :   bool isMBB() { return getMBBMRT() != nullptr; }
     461             : 
     462             :   bool isRoot() { return Parent == nullptr; }
     463             : 
     464           0 :   void setParent(RegionMRT *Region) { Parent = Region; }
     465             : 
     466             :   RegionMRT *getParent() { return Parent; }
     467             : 
     468             :   static MachineBasicBlock *
     469             :   initializeMRT(MachineFunction &MF, const MachineRegionInfo *RegionInfo,
     470             :                 DenseMap<MachineRegion *, RegionMRT *> &RegionMap);
     471             : 
     472             :   static RegionMRT *buildMRT(MachineFunction &MF,
     473             :                              const MachineRegionInfo *RegionInfo,
     474             :                              const SIInstrInfo *TII,
     475             :                              MachineRegisterInfo *MRI);
     476             : 
     477             :   virtual void dump(const TargetRegisterInfo *TRI, int depth = 0) = 0;
     478             : 
     479           0 :   void dumpDepth(int depth) {
     480           0 :     for (int i = depth; i > 0; --i) {
     481           0 :       dbgs() << "  ";
     482             :     }
     483           0 :   }
     484             : };
     485             : 
     486           0 : class MBBMRT : public MRT {
     487             :   MachineBasicBlock *MBB;
     488             : 
     489             : public:
     490           0 :   MBBMRT(MachineBasicBlock *BB) : MBB(BB) {
     491             :     setParent(nullptr);
     492             :     setBBSelectRegOut(0);
     493             :     setBBSelectRegIn(0);
     494             :   }
     495             : 
     496           0 :   MBBMRT *getMBBMRT() override { return this; }
     497             : 
     498             :   MachineBasicBlock *getMBB() { return MBB; }
     499             : 
     500           0 :   void dump(const TargetRegisterInfo *TRI, int depth = 0) override {
     501           0 :     dumpDepth(depth);
     502           0 :     dbgs() << "MBB: " << getMBB()->getNumber();
     503           0 :     dbgs() << " In: " << printReg(getBBSelectRegIn(), TRI);
     504           0 :     dbgs() << ", Out: " << printReg(getBBSelectRegOut(), TRI) << "\n";
     505           0 :   }
     506             : };
     507             : 
     508             : class RegionMRT : public MRT {
     509             : protected:
     510             :   MachineRegion *Region;
     511             :   LinearizedRegion *LRegion = nullptr;
     512             :   MachineBasicBlock *Succ = nullptr;
     513             :   SetVector<MRT *> Children;
     514             : 
     515             : public:
     516           0 :   RegionMRT(MachineRegion *MachineRegion) : Region(MachineRegion) {
     517             :     setParent(nullptr);
     518             :     setBBSelectRegOut(0);
     519             :     setBBSelectRegIn(0);
     520             :   }
     521             : 
     522           0 :   ~RegionMRT() override {
     523           0 :     if (LRegion) {
     524           0 :       delete LRegion;
     525             :     }
     526             : 
     527           0 :     for (auto CI : Children) {
     528           0 :       delete &(*CI);
     529             :     }
     530           0 :   }
     531             : 
     532           0 :   RegionMRT *getRegionMRT() override { return this; }
     533             : 
     534             :   void setLinearizedRegion(LinearizedRegion *LinearizeRegion) {
     535           0 :     LRegion = LinearizeRegion;
     536             :   }
     537             : 
     538             :   LinearizedRegion *getLinearizedRegion() { return LRegion; }
     539             : 
     540             :   MachineRegion *getMachineRegion() { return Region; }
     541             : 
     542             :   unsigned getInnerOutputRegister() {
     543           0 :     return (*(Children.begin()))->getBBSelectRegOut();
     544             :   }
     545             : 
     546           0 :   void addChild(MRT *Tree) { Children.insert(Tree); }
     547             : 
     548             :   SetVector<MRT *> *getChildren() { return &Children; }
     549             : 
     550           0 :   void dump(const TargetRegisterInfo *TRI, int depth = 0) override {
     551           0 :     dumpDepth(depth);
     552           0 :     dbgs() << "Region: " << (void *)Region;
     553           0 :     dbgs() << " In: " << printReg(getBBSelectRegIn(), TRI);
     554           0 :     dbgs() << ", Out: " << printReg(getBBSelectRegOut(), TRI) << "\n";
     555             : 
     556           0 :     dumpDepth(depth);
     557           0 :     if (getSucc())
     558           0 :       dbgs() << "Succ: " << getSucc()->getNumber() << "\n";
     559             :     else
     560           0 :       dbgs() << "Succ: none \n";
     561           0 :     for (auto MRTI : Children) {
     562           0 :       MRTI->dump(TRI, depth + 1);
     563             :     }
     564           0 :   }
     565             : 
     566             :   MRT *getEntryTree() { return Children.back(); }
     567             : 
     568             :   MRT *getExitTree() { return Children.front(); }
     569             : 
     570           0 :   MachineBasicBlock *getEntry() {
     571           0 :     MRT *Tree = Children.back();
     572           0 :     return (Tree->isRegion()) ? Tree->getRegionMRT()->getEntry()
     573           0 :                               : Tree->getMBBMRT()->getMBB();
     574             :   }
     575             : 
     576             :   MachineBasicBlock *getExit() {
     577             :     MRT *Tree = Children.front();
     578             :     return (Tree->isRegion()) ? Tree->getRegionMRT()->getExit()
     579             :                               : Tree->getMBBMRT()->getMBB();
     580             :   }
     581             : 
     582           0 :   void setSucc(MachineBasicBlock *MBB) { Succ = MBB; }
     583             : 
     584             :   MachineBasicBlock *getSucc() { return Succ; }
     585             : 
     586           0 :   bool contains(MachineBasicBlock *MBB) {
     587           0 :     for (auto CI : Children) {
     588           0 :       if (CI->isMBB()) {
     589           0 :         if (MBB == CI->getMBBMRT()->getMBB()) {
     590             :           return true;
     591             :         }
     592             :       } else {
     593           0 :         if (CI->getRegionMRT()->contains(MBB)) {
     594             :           return true;
     595           0 :         } else if (CI->getRegionMRT()->getLinearizedRegion() != nullptr &&
     596           0 :                    CI->getRegionMRT()->getLinearizedRegion()->contains(MBB)) {
     597             :           return true;
     598             :         }
     599             :       }
     600             :     }
     601             :     return false;
     602             :   }
     603             : 
     604           0 :   void replaceLiveOutReg(unsigned Register, unsigned NewRegister) {
     605           0 :     LinearizedRegion *LRegion = getLinearizedRegion();
     606           0 :     LRegion->replaceLiveOut(Register, NewRegister);
     607           0 :     for (auto &CI : Children) {
     608           0 :       if (CI->isRegion()) {
     609           0 :         CI->getRegionMRT()->replaceLiveOutReg(Register, NewRegister);
     610             :       }
     611             :     }
     612           0 :   }
     613             : };
     614             : 
     615             : } // end anonymous namespace
     616             : 
     617             : static unsigned createBBSelectReg(const SIInstrInfo *TII,
     618             :                                   MachineRegisterInfo *MRI) {
     619           0 :   return MRI->createVirtualRegister(TII->getPreferredSelectRegClass(32));
     620             : }
     621             : 
     622             : MachineBasicBlock *
     623             : MRT::initializeMRT(MachineFunction &MF, const MachineRegionInfo *RegionInfo,
     624             :                    DenseMap<MachineRegion *, RegionMRT *> &RegionMap) {
     625           0 :   for (auto &MFI : MF) {
     626             :     MachineBasicBlock *ExitMBB = &MFI;
     627           0 :     if (ExitMBB->succ_size() == 0) {
     628             :       return ExitMBB;
     629             :     }
     630             :   }
     631           0 :   llvm_unreachable("CFG has no exit block");
     632             :   return nullptr;
     633             : }
     634             : 
     635           0 : RegionMRT *MRT::buildMRT(MachineFunction &MF,
     636             :                          const MachineRegionInfo *RegionInfo,
     637             :                          const SIInstrInfo *TII, MachineRegisterInfo *MRI) {
     638             :   SmallPtrSet<MachineRegion *, 4> PlacedRegions;
     639             :   DenseMap<MachineRegion *, RegionMRT *> RegionMap;
     640           0 :   MachineRegion *TopLevelRegion = RegionInfo->getTopLevelRegion();
     641           0 :   RegionMRT *Result = new RegionMRT(TopLevelRegion);
     642           0 :   RegionMap[TopLevelRegion] = Result;
     643             : 
     644             :   // Insert the exit block first, we need it to be the merge node
     645             :   // for the top level region.
     646             :   MachineBasicBlock *Exit = initializeMRT(MF, RegionInfo, RegionMap);
     647             : 
     648             :   unsigned BBSelectRegIn = createBBSelectReg(TII, MRI);
     649           0 :   MBBMRT *ExitMRT = new MBBMRT(Exit);
     650           0 :   RegionMap[RegionInfo->getRegionFor(Exit)]->addChild(ExitMRT);
     651             :   ExitMRT->setBBSelectRegIn(BBSelectRegIn);
     652             : 
     653           0 :   for (auto MBBI : post_order(&(MF.front()))) {
     654             :     MachineBasicBlock *MBB = &(*MBBI);
     655             : 
     656             :     // Skip Exit since we already added it
     657           0 :     if (MBB == Exit) {
     658           0 :       continue;
     659             :     }
     660             : 
     661             :     DEBUG(dbgs() << "Visiting " << printMBBReference(*MBB) << "\n");
     662           0 :     MBBMRT *NewMBB = new MBBMRT(MBB);
     663           0 :     MachineRegion *Region = RegionInfo->getRegionFor(MBB);
     664             : 
     665             :     // Ensure we have the MRT region
     666             :     if (RegionMap.count(Region) == 0) {
     667           0 :       RegionMRT *NewMRTRegion = new RegionMRT(Region);
     668           0 :       RegionMap[Region] = NewMRTRegion;
     669             : 
     670             :       // Ensure all parents are in the RegionMap
     671           0 :       MachineRegion *Parent = Region->getParent();
     672           0 :       while (RegionMap.count(Parent) == 0) {
     673           0 :         RegionMRT *NewMRTParent = new RegionMRT(Parent);
     674             :         NewMRTParent->addChild(NewMRTRegion);
     675             :         NewMRTRegion->setParent(NewMRTParent);
     676           0 :         RegionMap[Parent] = NewMRTParent;
     677             :         NewMRTRegion = NewMRTParent;
     678           0 :         Parent = Parent->getParent();
     679             :       }
     680           0 :       RegionMap[Parent]->addChild(NewMRTRegion);
     681           0 :       NewMRTRegion->setParent(RegionMap[Parent]);
     682             :     }
     683             : 
     684             :     // Add MBB to Region MRT
     685           0 :     RegionMap[Region]->addChild(NewMBB);
     686           0 :     NewMBB->setParent(RegionMap[Region]);
     687           0 :     RegionMap[Region]->setSucc(Region->getExit());
     688             :   }
     689           0 :   return Result;
     690             : }
     691             : 
     692           0 : void LinearizedRegion::storeLiveOutReg(MachineBasicBlock *MBB, unsigned Reg,
     693             :                                        MachineInstr *DefInstr,
     694             :                                        const MachineRegisterInfo *MRI,
     695             :                                        const TargetRegisterInfo *TRI,
     696             :                                        PHILinearize &PHIInfo) {
     697           0 :   if (TRI->isVirtualRegister(Reg)) {
     698             :     DEBUG(dbgs() << "Considering Register: " << printReg(Reg, TRI) << "\n");
     699             :     // If this is a source register to a PHI we are chaining, it
     700             :     // must be live out.
     701             :     if (PHIInfo.isSource(Reg)) {
     702             :       DEBUG(dbgs() << "Add LiveOut (PHI): " << printReg(Reg, TRI) << "\n");
     703             :       addLiveOut(Reg);
     704             :     } else {
     705             :       // If this is live out of the MBB
     706           0 :       for (auto &UI : MRI->use_operands(Reg)) {
     707           0 :         if (UI.getParent()->getParent() != MBB) {
     708             :           DEBUG(dbgs() << "Add LiveOut (MBB " << printMBBReference(*MBB)
     709             :                        << "): " << printReg(Reg, TRI) << "\n");
     710             :           addLiveOut(Reg);
     711             :         } else {
     712             :           // If the use is in the same MBB we have to make sure
     713             :           // it is after the def, otherwise it is live out in a loop
     714             :           MachineInstr *UseInstr = UI.getParent();
     715             :           for (MachineBasicBlock::instr_iterator
     716           0 :                    MII = UseInstr->getIterator(),
     717             :                    MIE = UseInstr->getParent()->instr_end();
     718           0 :                MII != MIE; ++MII) {
     719           0 :             if ((&(*MII)) == DefInstr) {
     720             :               DEBUG(dbgs() << "Add LiveOut (Loop): " << printReg(Reg, TRI)
     721             :                            << "\n");
     722             :               addLiveOut(Reg);
     723             :             }
     724             :           }
     725             :         }
     726             :       }
     727             :     }
     728             :   }
     729           0 : }
     730             : 
     731           0 : void LinearizedRegion::storeLiveOutRegRegion(RegionMRT *Region, unsigned Reg,
     732             :                                              MachineInstr *DefInstr,
     733             :                                              const MachineRegisterInfo *MRI,
     734             :                                              const TargetRegisterInfo *TRI,
     735             :                                              PHILinearize &PHIInfo) {
     736           0 :   if (TRI->isVirtualRegister(Reg)) {
     737             :     DEBUG(dbgs() << "Considering Register: " << printReg(Reg, TRI) << "\n");
     738           0 :     for (auto &UI : MRI->use_operands(Reg)) {
     739           0 :       if (!Region->contains(UI.getParent()->getParent())) {
     740             :         DEBUG(dbgs() << "Add LiveOut (Region " << (void *)Region
     741             :                      << "): " << printReg(Reg, TRI) << "\n");
     742             :         addLiveOut(Reg);
     743             :       }
     744             :     }
     745             :   }
     746           0 : }
     747             : 
     748           0 : void LinearizedRegion::storeLiveOuts(MachineBasicBlock *MBB,
     749             :                                      const MachineRegisterInfo *MRI,
     750             :                                      const TargetRegisterInfo *TRI,
     751             :                                      PHILinearize &PHIInfo) {
     752             :   DEBUG(dbgs() << "-Store Live Outs Begin (" << printMBBReference(*MBB)
     753             :                << ")-\n");
     754           0 :   for (auto &II : *MBB) {
     755           0 :     for (auto &RI : II.defs()) {
     756           0 :       storeLiveOutReg(MBB, RI.getReg(), RI.getParent(), MRI, TRI, PHIInfo);
     757             :     }
     758           0 :     for (auto &IRI : II.implicit_operands()) {
     759           0 :       if (IRI.isDef()) {
     760           0 :         storeLiveOutReg(MBB, IRI.getReg(), IRI.getParent(), MRI, TRI, PHIInfo);
     761             :       }
     762             :     }
     763             :   }
     764             : 
     765             :   // If we have a successor with a PHI, source coming from this MBB we have to
     766             :   // add the register as live out
     767             :   for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
     768             :                                         E = MBB->succ_end();
     769           0 :        SI != E; ++SI) {
     770           0 :     for (auto &II : *(*SI)) {
     771             :       if (II.isPHI()) {
     772             :         MachineInstr &PHI = II;
     773           0 :         int numPreds = getPHINumInputs(PHI);
     774           0 :         for (int i = 0; i < numPreds; ++i) {
     775           0 :           if (getPHIPred(PHI, i) == MBB) {
     776             :             unsigned PHIReg = getPHISourceReg(PHI, i);
     777             :             DEBUG(dbgs() << "Add LiveOut (PhiSource " << printMBBReference(*MBB)
     778             :                          << " -> " << printMBBReference(*(*SI))
     779             :                          << "): " << printReg(PHIReg, TRI) << "\n");
     780             :             addLiveOut(PHIReg);
     781             :           }
     782             :         }
     783             :       }
     784             :     }
     785             :   }
     786             : 
     787             :   DEBUG(dbgs() << "-Store Live Outs Endn-\n");
     788           0 : }
     789             : 
     790           0 : void LinearizedRegion::storeMBBLiveOuts(MachineBasicBlock *MBB,
     791             :                                         const MachineRegisterInfo *MRI,
     792             :                                         const TargetRegisterInfo *TRI,
     793             :                                         PHILinearize &PHIInfo,
     794             :                                         RegionMRT *TopRegion) {
     795           0 :   for (auto &II : *MBB) {
     796           0 :     for (auto &RI : II.defs()) {
     797           0 :       storeLiveOutRegRegion(TopRegion, RI.getReg(), RI.getParent(), MRI, TRI,
     798             :                             PHIInfo);
     799             :     }
     800           0 :     for (auto &IRI : II.implicit_operands()) {
     801           0 :       if (IRI.isDef()) {
     802           0 :         storeLiveOutRegRegion(TopRegion, IRI.getReg(), IRI.getParent(), MRI,
     803             :                               TRI, PHIInfo);
     804             :       }
     805             :     }
     806             :   }
     807           0 : }
     808             : 
     809           0 : void LinearizedRegion::storeLiveOuts(RegionMRT *Region,
     810             :                                      const MachineRegisterInfo *MRI,
     811             :                                      const TargetRegisterInfo *TRI,
     812             :                                      PHILinearize &PHIInfo,
     813             :                                      RegionMRT *CurrentTopRegion) {
     814           0 :   MachineBasicBlock *Exit = Region->getSucc();
     815             : 
     816             :   RegionMRT *TopRegion =
     817           0 :       CurrentTopRegion == nullptr ? Region : CurrentTopRegion;
     818             : 
     819             :   // Check if exit is end of function, if so, no live outs.
     820           0 :   if (Exit == nullptr)
     821             :     return;
     822             : 
     823             :   auto Children = Region->getChildren();
     824           0 :   for (auto CI : *Children) {
     825           0 :     if (CI->isMBB()) {
     826           0 :       auto MBB = CI->getMBBMRT()->getMBB();
     827           0 :       storeMBBLiveOuts(MBB, MRI, TRI, PHIInfo, TopRegion);
     828             :     } else {
     829           0 :       LinearizedRegion *SubRegion = CI->getRegionMRT()->getLinearizedRegion();
     830             :       // We should be limited to only store registers that are live out from the
     831             :       // lineaized region
     832           0 :       for (auto MBBI : SubRegion->MBBs) {
     833           0 :         storeMBBLiveOuts(MBBI, MRI, TRI, PHIInfo, TopRegion);
     834             :       }
     835             :     }
     836             :   }
     837             : 
     838           0 :   if (CurrentTopRegion == nullptr) {
     839           0 :     auto Succ = Region->getSucc();
     840           0 :     for (auto &II : *Succ) {
     841             :       if (II.isPHI()) {
     842             :         MachineInstr &PHI = II;
     843           0 :         int numPreds = getPHINumInputs(PHI);
     844           0 :         for (int i = 0; i < numPreds; ++i) {
     845           0 :           if (Region->contains(getPHIPred(PHI, i))) {
     846             :             unsigned PHIReg = getPHISourceReg(PHI, i);
     847             :             DEBUG(dbgs() << "Add Region LiveOut (" << (void *)Region
     848             :                          << "): " << printReg(PHIReg, TRI) << "\n");
     849             :             addLiveOut(PHIReg);
     850             :           }
     851             :         }
     852             :       }
     853             :     }
     854             :   }
     855             : }
     856             : 
     857             : #ifndef NDEBUG
     858             : void LinearizedRegion::print(raw_ostream &OS, const TargetRegisterInfo *TRI) {
     859             :   OS << "Linearized Region {";
     860             :   bool IsFirst = true;
     861             :   for (const auto &MBB : MBBs) {
     862             :     if (IsFirst) {
     863             :       IsFirst = false;
     864             :     } else {
     865             :       OS << " ,";
     866             :     }
     867             :     OS << MBB->getNumber();
     868             :   }
     869             :   OS << "} (" << Entry->getNumber() << ", "
     870             :      << (Exit == nullptr ? -1 : Exit->getNumber())
     871             :      << "): In:" << printReg(getBBSelectRegIn(), TRI)
     872             :      << " Out:" << printReg(getBBSelectRegOut(), TRI) << " {";
     873             :   for (auto &LI : LiveOuts) {
     874             :     OS << printReg(LI, TRI) << " ";
     875             :   }
     876             :   OS << "} \n";
     877             : }
     878             : #endif
     879             : 
     880             : unsigned LinearizedRegion::getBBSelectRegIn() {
     881           0 :   return getRegionMRT()->getBBSelectRegIn();
     882             : }
     883             : 
     884             : unsigned LinearizedRegion::getBBSelectRegOut() {
     885           0 :   return getRegionMRT()->getBBSelectRegOut();
     886             : }
     887             : 
     888           0 : void LinearizedRegion::setHasLoop(bool Value) { HasLoop = Value; }
     889             : 
     890             : bool LinearizedRegion::getHasLoop() { return HasLoop; }
     891             : 
     892             : void LinearizedRegion::addLiveOut(unsigned VReg) { LiveOuts.insert(VReg); }
     893             : 
     894           0 : void LinearizedRegion::removeLiveOut(unsigned Reg) {
     895           0 :   if (isLiveOut(Reg))
     896             :     LiveOuts.erase(Reg);
     897           0 : }
     898             : 
     899           0 : void LinearizedRegion::replaceLiveOut(unsigned OldReg, unsigned NewReg) {
     900             :   if (isLiveOut(OldReg)) {
     901           0 :     removeLiveOut(OldReg);
     902             :     addLiveOut(NewReg);
     903             :   }
     904           0 : }
     905             : 
     906           0 : void LinearizedRegion::replaceRegister(unsigned Register, unsigned NewRegister,
     907             :                                        MachineRegisterInfo *MRI,
     908             :                                        bool ReplaceInside, bool ReplaceOutside,
     909             :                                        bool IncludeLoopPHI) {
     910             :   assert(Register != NewRegister && "Cannot replace a reg with itself");
     911             : 
     912             :   DEBUG(dbgs() << "Pepareing to replace register (region): "
     913             :                << printReg(Register, MRI->getTargetRegisterInfo()) << " with "
     914             :                << printReg(NewRegister, MRI->getTargetRegisterInfo()) << "\n");
     915             : 
     916             :   // If we are replacing outside, we also need to update the LiveOuts
     917           0 :   if (ReplaceOutside &&
     918           0 :       (isLiveOut(Register) || this->getParent()->isLiveOut(Register))) {
     919             :     LinearizedRegion *Current = this;
     920           0 :     while (Current != nullptr && Current->getEntry() != nullptr) {
     921             :       DEBUG(dbgs() << "Region before register replace\n");
     922             :       DEBUG(Current->print(dbgs(), MRI->getTargetRegisterInfo()));
     923           0 :       Current->replaceLiveOut(Register, NewRegister);
     924             :       DEBUG(dbgs() << "Region after register replace\n");
     925             :       DEBUG(Current->print(dbgs(), MRI->getTargetRegisterInfo()));
     926           0 :       Current = Current->getParent();
     927             :     }
     928             :   }
     929             : 
     930             :   for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Register),
     931             :                                          E = MRI->reg_end();
     932           0 :        I != E;) {
     933             :     MachineOperand &O = *I;
     934             :     ++I;
     935             : 
     936             :     // We don't rewrite defs.
     937           0 :     if (O.isDef())
     938           0 :       continue;
     939             : 
     940           0 :     bool IsInside = contains(O.getParent()->getParent());
     941           0 :     bool IsLoopPHI = IsInside && (O.getParent()->isPHI() &&
     942           0 :                                   O.getParent()->getParent() == getEntry());
     943           0 :     bool ShouldReplace = (IsInside && ReplaceInside) ||
     944           0 :                          (!IsInside && ReplaceOutside) ||
     945           0 :                          (IncludeLoopPHI && IsLoopPHI);
     946             :     if (ShouldReplace) {
     947             : 
     948           0 :       if (TargetRegisterInfo::isPhysicalRegister(NewRegister)) {
     949             :         DEBUG(dbgs() << "Trying to substitute physical register: "
     950             :                      << printReg(NewRegister, MRI->getTargetRegisterInfo())
     951             :                      << "\n");
     952           0 :         llvm_unreachable("Cannot substitute physical registers");
     953             :       } else {
     954             :         DEBUG(dbgs() << "Replacing register (region): "
     955             :                      << printReg(Register, MRI->getTargetRegisterInfo())
     956             :                      << " with "
     957             :                      << printReg(NewRegister, MRI->getTargetRegisterInfo())
     958             :                      << "\n");
     959           0 :         O.setReg(NewRegister);
     960             :       }
     961             :     }
     962             :   }
     963           0 : }
     964             : 
     965             : void LinearizedRegion::replaceRegisterInsideRegion(unsigned Register,
     966             :                                                    unsigned NewRegister,
     967             :                                                    bool IncludeLoopPHIs,
     968             :                                                    MachineRegisterInfo *MRI) {
     969           0 :   replaceRegister(Register, NewRegister, MRI, true, false, IncludeLoopPHIs);
     970             : }
     971             : 
     972             : void LinearizedRegion::replaceRegisterOutsideRegion(unsigned Register,
     973             :                                                     unsigned NewRegister,
     974             :                                                     bool IncludeLoopPHIs,
     975             :                                                     MachineRegisterInfo *MRI) {
     976           0 :   replaceRegister(Register, NewRegister, MRI, false, true, IncludeLoopPHIs);
     977             : }
     978             : 
     979             : DenseSet<unsigned> *LinearizedRegion::getLiveOuts() { return &LiveOuts; }
     980             : 
     981             : void LinearizedRegion::setEntry(MachineBasicBlock *NewEntry) {
     982           0 :   Entry = NewEntry;
     983             : }
     984             : 
     985             : MachineBasicBlock *LinearizedRegion::getEntry() { return Entry; }
     986             : 
     987           0 : void LinearizedRegion::setExit(MachineBasicBlock *NewExit) { Exit = NewExit; }
     988             : 
     989             : MachineBasicBlock *LinearizedRegion::getExit() { return Exit; }
     990             : 
     991           0 : void LinearizedRegion::addMBB(MachineBasicBlock *MBB) { MBBs.insert(MBB); }
     992             : 
     993           0 : void LinearizedRegion::addMBBs(LinearizedRegion *InnerRegion) {
     994           0 :   for (const auto &MBB : InnerRegion->MBBs) {
     995             :     addMBB(MBB);
     996             :   }
     997           0 : }
     998             : 
     999             : bool LinearizedRegion::contains(MachineBasicBlock *MBB) {
    1000           0 :   return MBBs.count(MBB) == 1;
    1001             : }
    1002             : 
    1003             : bool LinearizedRegion::isLiveOut(unsigned Reg) {
    1004             :   return LiveOuts.count(Reg) == 1;
    1005             : }
    1006             : 
    1007             : bool LinearizedRegion::hasNoDef(unsigned Reg, MachineRegisterInfo *MRI) {
    1008           0 :   return MRI->def_begin(Reg) == MRI->def_end();
    1009             : }
    1010             : 
    1011             : // After the code has been structurized, what was flagged as kills
    1012             : // before are no longer register kills.
    1013           0 : void LinearizedRegion::removeFalseRegisterKills(MachineRegisterInfo *MRI) {
    1014           0 :   const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
    1015           0 :   for (auto MBBI : MBBs) {
    1016             :     MachineBasicBlock *MBB = MBBI;
    1017           0 :     for (auto &II : *MBB) {
    1018           0 :       for (auto &RI : II.uses()) {
    1019           0 :         if (RI.isReg()) {
    1020           0 :           unsigned Reg = RI.getReg();
    1021           0 :           if (TRI->isVirtualRegister(Reg)) {
    1022           0 :             if (hasNoDef(Reg, MRI))
    1023           0 :               continue;
    1024           0 :             if (!MRI->hasOneDef(Reg)) {
    1025             :               DEBUG(this->getEntry()->getParent()->dump());
    1026             :               DEBUG(dbgs() << printReg(Reg, TRI) << "\n");
    1027             :             }
    1028             : 
    1029           0 :             if (MRI->def_begin(Reg) == MRI->def_end()) {
    1030             :               DEBUG(dbgs() << "Register "
    1031             :                            << printReg(Reg, MRI->getTargetRegisterInfo())
    1032             :                            << " has NO defs\n");
    1033           0 :             } else if (!MRI->hasOneDef(Reg)) {
    1034             :               DEBUG(dbgs() << "Register "
    1035             :                            << printReg(Reg, MRI->getTargetRegisterInfo())
    1036             :                            << " has multiple defs\n");
    1037             :             }
    1038             : 
    1039             :             assert(MRI->hasOneDef(Reg) && "Register has multiple definitions");
    1040           0 :             MachineOperand *Def = &(*(MRI->def_begin(Reg)));
    1041             :             MachineOperand *UseOperand = &(RI);
    1042           0 :             bool UseIsOutsideDefMBB = Def->getParent()->getParent() != MBB;
    1043           0 :             if (UseIsOutsideDefMBB && UseOperand->isKill()) {
    1044             :               DEBUG(dbgs() << "Removing kill flag on register: "
    1045             :                            << printReg(Reg, TRI) << "\n");
    1046             :               UseOperand->setIsKill(false);
    1047             :             }
    1048             :           }
    1049             :         }
    1050             :       }
    1051             :     }
    1052             :   }
    1053           0 : }
    1054             : 
    1055             : void LinearizedRegion::initLiveOut(RegionMRT *Region,
    1056             :                                    const MachineRegisterInfo *MRI,
    1057             :                                    const TargetRegisterInfo *TRI,
    1058             :                                    PHILinearize &PHIInfo) {
    1059           0 :   storeLiveOuts(Region, MRI, TRI, PHIInfo);
    1060             : }
    1061             : 
    1062           0 : LinearizedRegion::LinearizedRegion(MachineBasicBlock *MBB,
    1063             :                                    const MachineRegisterInfo *MRI,
    1064             :                                    const TargetRegisterInfo *TRI,
    1065           0 :                                    PHILinearize &PHIInfo) {
    1066             :   setEntry(MBB);
    1067             :   setExit(MBB);
    1068           0 :   storeLiveOuts(MBB, MRI, TRI, PHIInfo);
    1069           0 :   MBBs.insert(MBB);
    1070           0 :   Parent = nullptr;
    1071           0 : }
    1072             : 
    1073           0 : LinearizedRegion::LinearizedRegion() {
    1074             :   setEntry(nullptr);
    1075             :   setExit(nullptr);
    1076           0 :   Parent = nullptr;
    1077             : }
    1078             : 
    1079             : namespace {
    1080             : 
    1081           0 : class AMDGPUMachineCFGStructurizer : public MachineFunctionPass {
    1082             : private:
    1083             :   const MachineRegionInfo *Regions;
    1084             :   const SIInstrInfo *TII;
    1085             :   const TargetRegisterInfo *TRI;
    1086             :   MachineRegisterInfo *MRI;
    1087             :   unsigned BBSelectRegister;
    1088             :   PHILinearize PHIInfo;
    1089             :   DenseMap<MachineBasicBlock *, MachineBasicBlock *> FallthroughMap;
    1090             :   RegionMRT *RMRT;
    1091             : 
    1092             :   void getPHIRegionIndices(RegionMRT *Region, MachineInstr &PHI,
    1093             :                            SmallVector<unsigned, 2> &RegionIndices);
    1094             :   void getPHIRegionIndices(LinearizedRegion *Region, MachineInstr &PHI,
    1095             :                            SmallVector<unsigned, 2> &RegionIndices);
    1096             :   void getPHINonRegionIndices(LinearizedRegion *Region, MachineInstr &PHI,
    1097             :                               SmallVector<unsigned, 2> &PHINonRegionIndices);
    1098             : 
    1099             :   void storePHILinearizationInfoDest(
    1100             :       unsigned LDestReg, MachineInstr &PHI,
    1101             :       SmallVector<unsigned, 2> *RegionIndices = nullptr);
    1102             : 
    1103             :   unsigned storePHILinearizationInfo(MachineInstr &PHI,
    1104             :                                      SmallVector<unsigned, 2> *RegionIndices);
    1105             : 
    1106             :   void extractKilledPHIs(MachineBasicBlock *MBB);
    1107             : 
    1108             :   bool shrinkPHI(MachineInstr &PHI, SmallVector<unsigned, 2> &PHIIndices,
    1109             :                  unsigned *ReplaceReg);
    1110             : 
    1111             :   bool shrinkPHI(MachineInstr &PHI, unsigned CombinedSourceReg,
    1112             :                  MachineBasicBlock *SourceMBB,
    1113             :                  SmallVector<unsigned, 2> &PHIIndices, unsigned *ReplaceReg);
    1114             : 
    1115             :   void replacePHI(MachineInstr &PHI, unsigned CombinedSourceReg,
    1116             :                   MachineBasicBlock *LastMerge,
    1117             :                   SmallVector<unsigned, 2> &PHIRegionIndices);
    1118             :   void replaceEntryPHI(MachineInstr &PHI, unsigned CombinedSourceReg,
    1119             :                        MachineBasicBlock *IfMBB,
    1120             :                        SmallVector<unsigned, 2> &PHIRegionIndices);
    1121             :   void replaceLiveOutRegs(MachineInstr &PHI,
    1122             :                           SmallVector<unsigned, 2> &PHIRegionIndices,
    1123             :                           unsigned CombinedSourceReg,
    1124             :                           LinearizedRegion *LRegion);
    1125             :   void rewriteRegionExitPHI(RegionMRT *Region, MachineBasicBlock *LastMerge,
    1126             :                             MachineInstr &PHI, LinearizedRegion *LRegion);
    1127             : 
    1128             :   void rewriteRegionExitPHIs(RegionMRT *Region, MachineBasicBlock *LastMerge,
    1129             :                              LinearizedRegion *LRegion);
    1130             :   void rewriteRegionEntryPHI(LinearizedRegion *Region, MachineBasicBlock *IfMBB,
    1131             :                              MachineInstr &PHI);
    1132             :   void rewriteRegionEntryPHIs(LinearizedRegion *Region,
    1133             :                               MachineBasicBlock *IfMBB);
    1134             : 
    1135             :   bool regionIsSimpleIf(RegionMRT *Region);
    1136             : 
    1137             :   void transformSimpleIfRegion(RegionMRT *Region);
    1138             : 
    1139             :   void eliminateDeadBranchOperands(MachineBasicBlock::instr_iterator &II);
    1140             : 
    1141             :   void insertUnconditionalBranch(MachineBasicBlock *MBB,
    1142             :                                  MachineBasicBlock *Dest,
    1143             :                                  const DebugLoc &DL = DebugLoc());
    1144             : 
    1145             :   MachineBasicBlock *createLinearizedExitBlock(RegionMRT *Region);
    1146             : 
    1147             :   void insertMergePHI(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB,
    1148             :                       MachineBasicBlock *MergeBB, unsigned DestRegister,
    1149             :                       unsigned IfSourceRegister, unsigned CodeSourceRegister,
    1150             :                       bool IsUndefIfSource = false);
    1151             : 
    1152             :   MachineBasicBlock *createIfBlock(MachineBasicBlock *MergeBB,
    1153             :                                    MachineBasicBlock *CodeBBStart,
    1154             :                                    MachineBasicBlock *CodeBBEnd,
    1155             :                                    MachineBasicBlock *SelectBB, unsigned IfReg,
    1156             :                                    bool InheritPreds);
    1157             : 
    1158             :   void prunePHIInfo(MachineBasicBlock *MBB);
    1159             :   void createEntryPHI(LinearizedRegion *CurrentRegion, unsigned DestReg);
    1160             : 
    1161             :   void createEntryPHIs(LinearizedRegion *CurrentRegion);
    1162             :   void resolvePHIInfos(MachineBasicBlock *FunctionEntry);
    1163             : 
    1164             :   void replaceRegisterWith(unsigned Register, unsigned NewRegister);
    1165             : 
    1166             :   MachineBasicBlock *createIfRegion(MachineBasicBlock *MergeBB,
    1167             :                                     MachineBasicBlock *CodeBB,
    1168             :                                     LinearizedRegion *LRegion,
    1169             :                                     unsigned BBSelectRegIn,
    1170             :                                     unsigned BBSelectRegOut);
    1171             : 
    1172             :   MachineBasicBlock *
    1173             :   createIfRegion(MachineBasicBlock *MergeMBB, LinearizedRegion *InnerRegion,
    1174             :                  LinearizedRegion *CurrentRegion, MachineBasicBlock *SelectBB,
    1175             :                  unsigned BBSelectRegIn, unsigned BBSelectRegOut);
    1176             :   void ensureCondIsNotKilled(SmallVector<MachineOperand, 1> Cond);
    1177             : 
    1178             :   void rewriteCodeBBTerminator(MachineBasicBlock *CodeBB,
    1179             :                                MachineBasicBlock *MergeBB,
    1180             :                                unsigned BBSelectReg);
    1181             : 
    1182             :   MachineInstr *getDefInstr(unsigned Reg);
    1183             :   void insertChainedPHI(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB,
    1184             :                         MachineBasicBlock *MergeBB,
    1185             :                         LinearizedRegion *InnerRegion, unsigned DestReg,
    1186             :                         unsigned SourceReg);
    1187             :   bool containsDef(MachineBasicBlock *MBB, LinearizedRegion *InnerRegion,
    1188             :                    unsigned Register);
    1189             :   void rewriteLiveOutRegs(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB,
    1190             :                           MachineBasicBlock *MergeBB,
    1191             :                           LinearizedRegion *InnerRegion,
    1192             :                           LinearizedRegion *LRegion);
    1193             : 
    1194             :   void splitLoopPHI(MachineInstr &PHI, MachineBasicBlock *Entry,
    1195             :                     MachineBasicBlock *EntrySucc, LinearizedRegion *LRegion);
    1196             :   void splitLoopPHIs(MachineBasicBlock *Entry, MachineBasicBlock *EntrySucc,
    1197             :                      LinearizedRegion *LRegion);
    1198             : 
    1199             :   MachineBasicBlock *splitExit(LinearizedRegion *LRegion);
    1200             : 
    1201             :   MachineBasicBlock *splitEntry(LinearizedRegion *LRegion);
    1202             : 
    1203             :   LinearizedRegion *initLinearizedRegion(RegionMRT *Region);
    1204             : 
    1205             :   bool structurizeComplexRegion(RegionMRT *Region);
    1206             : 
    1207             :   bool structurizeRegion(RegionMRT *Region);
    1208             : 
    1209             :   bool structurizeRegions(RegionMRT *Region, bool isTopRegion);
    1210             : 
    1211             : public:
    1212             :   static char ID;
    1213             : 
    1214           0 :   AMDGPUMachineCFGStructurizer() : MachineFunctionPass(ID) {
    1215           0 :     initializeAMDGPUMachineCFGStructurizerPass(*PassRegistry::getPassRegistry());
    1216           0 :   }
    1217             : 
    1218           0 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
    1219             :     AU.addRequired<MachineRegionInfoPass>();
    1220           0 :     MachineFunctionPass::getAnalysisUsage(AU);
    1221           0 :   }
    1222             : 
    1223             :   void initFallthroughMap(MachineFunction &MF);
    1224             : 
    1225             :   void createLinearizedRegion(RegionMRT *Region, unsigned SelectOut);
    1226             : 
    1227             :   unsigned initializeSelectRegisters(MRT *MRT, unsigned ExistingExitReg,
    1228             :                                      MachineRegisterInfo *MRI,
    1229             :                                      const SIInstrInfo *TII);
    1230             : 
    1231           0 :   void setRegionMRT(RegionMRT *RegionTree) { RMRT = RegionTree; }
    1232             : 
    1233             :   RegionMRT *getRegionMRT() { return RMRT; }
    1234             : 
    1235             :   bool runOnMachineFunction(MachineFunction &MF) override;
    1236             : };
    1237             : 
    1238             : } // end anonymous namespace
    1239             : 
    1240             : char AMDGPUMachineCFGStructurizer::ID = 0;
    1241             : 
    1242             : bool AMDGPUMachineCFGStructurizer::regionIsSimpleIf(RegionMRT *Region) {
    1243             :   MachineBasicBlock *Entry = Region->getEntry();
    1244             :   MachineBasicBlock *Succ = Region->getSucc();
    1245             :   bool FoundBypass = false;
    1246             :   bool FoundIf = false;
    1247             : 
    1248             :   if (Entry->succ_size() != 2) {
    1249             :     return false;
    1250             :   }
    1251             : 
    1252             :   for (MachineBasicBlock::const_succ_iterator SI = Entry->succ_begin(),
    1253             :                                               E = Entry->succ_end();
    1254             :        SI != E; ++SI) {
    1255             :     MachineBasicBlock *Current = *SI;
    1256             : 
    1257             :     if (Current == Succ) {
    1258             :       FoundBypass = true;
    1259             :     } else if ((Current->succ_size() == 1) &&
    1260             :                *(Current->succ_begin()) == Succ) {
    1261             :       FoundIf = true;
    1262             :     }
    1263             :   }
    1264             : 
    1265             :   return FoundIf && FoundBypass;
    1266             : }
    1267             : 
    1268             : void AMDGPUMachineCFGStructurizer::transformSimpleIfRegion(RegionMRT *Region) {
    1269             :   MachineBasicBlock *Entry = Region->getEntry();
    1270             :   MachineBasicBlock *Exit = Region->getExit();
    1271             :   TII->convertNonUniformIfRegion(Entry, Exit);
    1272             : }
    1273             : 
    1274           0 : static void fixMBBTerminator(MachineBasicBlock *MBB) {
    1275           0 :   if (MBB->succ_size() == 1) {
    1276           0 :     auto *Succ = *(MBB->succ_begin());
    1277           0 :     for (auto &TI : MBB->terminators()) {
    1278           0 :       for (auto &UI : TI.uses()) {
    1279           0 :         if (UI.isMBB() && UI.getMBB() != Succ) {
    1280             :           UI.setMBB(Succ);
    1281             :         }
    1282             :       }
    1283             :     }
    1284             :   }
    1285           0 : }
    1286             : 
    1287           0 : static void fixRegionTerminator(RegionMRT *Region) {
    1288             :   MachineBasicBlock *InternalSucc = nullptr;
    1289             :   MachineBasicBlock *ExternalSucc = nullptr;
    1290           0 :   LinearizedRegion *LRegion = Region->getLinearizedRegion();
    1291           0 :   auto Exit = LRegion->getExit();
    1292             : 
    1293             :   SmallPtrSet<MachineBasicBlock *, 2> Successors;
    1294             :   for (MachineBasicBlock::const_succ_iterator SI = Exit->succ_begin(),
    1295             :                                               SE = Exit->succ_end();
    1296           0 :        SI != SE; ++SI) {
    1297           0 :     MachineBasicBlock *Succ = *SI;
    1298           0 :     if (LRegion->contains(Succ)) {
    1299             :       // Do not allow re-assign
    1300             :       assert(InternalSucc == nullptr);
    1301             :       InternalSucc = Succ;
    1302             :     } else {
    1303             :       // Do not allow re-assign
    1304             :       assert(ExternalSucc == nullptr);
    1305             :       ExternalSucc = Succ;
    1306             :     }
    1307             :   }
    1308             : 
    1309           0 :   for (auto &TI : Exit->terminators()) {
    1310           0 :     for (auto &UI : TI.uses()) {
    1311           0 :       if (UI.isMBB()) {
    1312           0 :         auto Target = UI.getMBB();
    1313           0 :         if (Target != InternalSucc && Target != ExternalSucc) {
    1314             :           UI.setMBB(ExternalSucc);
    1315             :         }
    1316             :       }
    1317             :     }
    1318             :   }
    1319           0 : }
    1320             : 
    1321             : // If a region region is just a sequence of regions (and the exit
    1322             : // block in the case of the top level region), we can simply skip
    1323             : // linearizing it, because it is already linear
    1324           0 : bool regionIsSequence(RegionMRT *Region) {
    1325             :   auto Children = Region->getChildren();
    1326           0 :   for (auto CI : *Children) {
    1327           0 :     if (!CI->isRegion()) {
    1328           0 :       if (CI->getMBBMRT()->getMBB()->succ_size() > 1) {
    1329             :         return false;
    1330             :       }
    1331             :     }
    1332             :   }
    1333             :   return true;
    1334             : }
    1335             : 
    1336           0 : void fixupRegionExits(RegionMRT *Region) {
    1337             :   auto Children = Region->getChildren();
    1338           0 :   for (auto CI : *Children) {
    1339           0 :     if (!CI->isRegion()) {
    1340           0 :       fixMBBTerminator(CI->getMBBMRT()->getMBB());
    1341             :     } else {
    1342           0 :       fixRegionTerminator(CI->getRegionMRT());
    1343             :     }
    1344             :   }
    1345           0 : }
    1346             : 
    1347           0 : void AMDGPUMachineCFGStructurizer::getPHIRegionIndices(
    1348             :     RegionMRT *Region, MachineInstr &PHI,
    1349             :     SmallVector<unsigned, 2> &PHIRegionIndices) {
    1350             :   unsigned NumInputs = getPHINumInputs(PHI);
    1351           0 :   for (unsigned i = 0; i < NumInputs; ++i) {
    1352             :     MachineBasicBlock *Pred = getPHIPred(PHI, i);
    1353           0 :     if (Region->contains(Pred)) {
    1354           0 :       PHIRegionIndices.push_back(i);
    1355             :     }
    1356             :   }
    1357           0 : }
    1358             : 
    1359           0 : void AMDGPUMachineCFGStructurizer::getPHIRegionIndices(
    1360             :     LinearizedRegion *Region, MachineInstr &PHI,
    1361             :     SmallVector<unsigned, 2> &PHIRegionIndices) {
    1362             :   unsigned NumInputs = getPHINumInputs(PHI);
    1363           0 :   for (unsigned i = 0; i < NumInputs; ++i) {
    1364             :     MachineBasicBlock *Pred = getPHIPred(PHI, i);
    1365           0 :     if (Region->contains(Pred)) {
    1366           0 :       PHIRegionIndices.push_back(i);
    1367             :     }
    1368             :   }
    1369           0 : }
    1370             : 
    1371           0 : void AMDGPUMachineCFGStructurizer::getPHINonRegionIndices(
    1372             :     LinearizedRegion *Region, MachineInstr &PHI,
    1373             :     SmallVector<unsigned, 2> &PHINonRegionIndices) {
    1374             :   unsigned NumInputs = getPHINumInputs(PHI);
    1375           0 :   for (unsigned i = 0; i < NumInputs; ++i) {
    1376             :     MachineBasicBlock *Pred = getPHIPred(PHI, i);
    1377           0 :     if (!Region->contains(Pred)) {
    1378           0 :       PHINonRegionIndices.push_back(i);
    1379             :     }
    1380             :   }
    1381           0 : }
    1382             : 
    1383           0 : void AMDGPUMachineCFGStructurizer::storePHILinearizationInfoDest(
    1384             :     unsigned LDestReg, MachineInstr &PHI,
    1385             :     SmallVector<unsigned, 2> *RegionIndices) {
    1386           0 :   if (RegionIndices) {
    1387           0 :     for (auto i : *RegionIndices) {
    1388           0 :       PHIInfo.addSource(LDestReg, getPHISourceReg(PHI, i), getPHIPred(PHI, i));
    1389             :     }
    1390             :   } else {
    1391             :     unsigned NumInputs = getPHINumInputs(PHI);
    1392           0 :     for (unsigned i = 0; i < NumInputs; ++i) {
    1393           0 :       PHIInfo.addSource(LDestReg, getPHISourceReg(PHI, i), getPHIPred(PHI, i));
    1394             :     }
    1395             :   }
    1396           0 : }
    1397             : 
    1398           0 : unsigned AMDGPUMachineCFGStructurizer::storePHILinearizationInfo(
    1399             :     MachineInstr &PHI, SmallVector<unsigned, 2> *RegionIndices) {
    1400             :   unsigned DestReg = getPHIDestReg(PHI);
    1401             :   unsigned LinearizeDestReg =
    1402           0 :       MRI->createVirtualRegister(MRI->getRegClass(DestReg));
    1403           0 :   PHIInfo.addDest(LinearizeDestReg, PHI.getDebugLoc());
    1404           0 :   storePHILinearizationInfoDest(LinearizeDestReg, PHI, RegionIndices);
    1405           0 :   return LinearizeDestReg;
    1406             : }
    1407             : 
    1408           0 : void AMDGPUMachineCFGStructurizer::extractKilledPHIs(MachineBasicBlock *MBB) {
    1409             :   // We need to create a new chain for the killed phi, but there is no
    1410             :   // need to do the renaming outside or inside the block.
    1411             :   SmallPtrSet<MachineInstr *, 2> PHIs;
    1412             :   for (MachineBasicBlock::instr_iterator I = MBB->instr_begin(),
    1413             :                                          E = MBB->instr_end();
    1414           0 :        I != E; ++I) {
    1415             :     MachineInstr &Instr = *I;
    1416             :     if (Instr.isPHI()) {
    1417             :       unsigned PHIDestReg = getPHIDestReg(Instr);
    1418             :       DEBUG(dbgs() << "Extractking killed phi:\n");
    1419             :       DEBUG(Instr.dump());
    1420           0 :       PHIs.insert(&Instr);
    1421           0 :       PHIInfo.addDest(PHIDestReg, Instr.getDebugLoc());
    1422           0 :       storePHILinearizationInfoDest(PHIDestReg, Instr);
    1423             :     }
    1424             :   }
    1425             : 
    1426           0 :   for (auto PI : PHIs) {
    1427           0 :     PI->eraseFromParent();
    1428             :   }
    1429           0 : }
    1430             : 
    1431             : static bool isPHIRegionIndex(SmallVector<unsigned, 2> PHIRegionIndices,
    1432             :                              unsigned Index) {
    1433           0 :   for (auto i : PHIRegionIndices) {
    1434           0 :     if (i == Index)
    1435             :       return true;
    1436             :   }
    1437             :   return false;
    1438             : }
    1439             : 
    1440             : bool AMDGPUMachineCFGStructurizer::shrinkPHI(MachineInstr &PHI,
    1441             :                                        SmallVector<unsigned, 2> &PHIIndices,
    1442             :                                        unsigned *ReplaceReg) {
    1443           0 :   return shrinkPHI(PHI, 0, nullptr, PHIIndices, ReplaceReg);
    1444             : }
    1445             : 
    1446           0 : bool AMDGPUMachineCFGStructurizer::shrinkPHI(MachineInstr &PHI,
    1447             :                                        unsigned CombinedSourceReg,
    1448             :                                        MachineBasicBlock *SourceMBB,
    1449             :                                        SmallVector<unsigned, 2> &PHIIndices,
    1450             :                                        unsigned *ReplaceReg) {
    1451             :   DEBUG(dbgs() << "Shrink PHI: ");
    1452             :   DEBUG(PHI.dump());
    1453             :   DEBUG(dbgs() << " to " << printReg(getPHIDestReg(PHI), TRI) << " = PHI(");
    1454             : 
    1455             :   bool Replaced = false;
    1456             :   unsigned NumInputs = getPHINumInputs(PHI);
    1457             :   int SingleExternalEntryIndex = -1;
    1458           0 :   for (unsigned i = 0; i < NumInputs; ++i) {
    1459           0 :     if (!isPHIRegionIndex(PHIIndices, i)) {
    1460           0 :       if (SingleExternalEntryIndex == -1) {
    1461             :         // Single entry
    1462           0 :         SingleExternalEntryIndex = i;
    1463             :       } else {
    1464             :         // Multiple entries
    1465             :         SingleExternalEntryIndex = -2;
    1466             :       }
    1467             :     }
    1468             :   }
    1469             : 
    1470           0 :   if (SingleExternalEntryIndex > -1) {
    1471           0 :     *ReplaceReg = getPHISourceReg(PHI, SingleExternalEntryIndex);
    1472             :     // We should not rewrite the code, we should only pick up the single value
    1473             :     // that represents the shrunk PHI.
    1474             :     Replaced = true;
    1475             :   } else {
    1476           0 :     MachineBasicBlock *MBB = PHI.getParent();
    1477             :     MachineInstrBuilder MIB =
    1478           0 :         BuildMI(*MBB, PHI, PHI.getDebugLoc(), TII->get(TargetOpcode::PHI),
    1479           0 :                 getPHIDestReg(PHI));
    1480           0 :     if (SourceMBB) {
    1481           0 :       MIB.addReg(CombinedSourceReg);
    1482             :       MIB.addMBB(SourceMBB);
    1483             :       DEBUG(dbgs() << printReg(CombinedSourceReg, TRI) << ", "
    1484             :                    << printMBBReference(*SourceMBB));
    1485             :     }
    1486             : 
    1487           0 :     for (unsigned i = 0; i < NumInputs; ++i) {
    1488           0 :       if (isPHIRegionIndex(PHIIndices, i)) {
    1489             :         continue;
    1490             :       }
    1491             :       unsigned SourceReg = getPHISourceReg(PHI, i);
    1492             :       MachineBasicBlock *SourcePred = getPHIPred(PHI, i);
    1493           0 :       MIB.addReg(SourceReg);
    1494             :       MIB.addMBB(SourcePred);
    1495             :       DEBUG(dbgs() << printReg(SourceReg, TRI) << ", "
    1496             :                    << printMBBReference(*SourcePred));
    1497             :     }
    1498             :     DEBUG(dbgs() << ")\n");
    1499             :   }
    1500           0 :   PHI.eraseFromParent();
    1501           0 :   return Replaced;
    1502             : }
    1503             : 
    1504           0 : void AMDGPUMachineCFGStructurizer::replacePHI(
    1505             :     MachineInstr &PHI, unsigned CombinedSourceReg, MachineBasicBlock *LastMerge,
    1506             :     SmallVector<unsigned, 2> &PHIRegionIndices) {
    1507             :   DEBUG(dbgs() << "Replace PHI: ");
    1508             :   DEBUG(PHI.dump());
    1509             :   DEBUG(dbgs() << " with " << printReg(getPHIDestReg(PHI), TRI) << " = PHI(");
    1510             : 
    1511             :   bool HasExternalEdge = false;
    1512             :   unsigned NumInputs = getPHINumInputs(PHI);
    1513           0 :   for (unsigned i = 0; i < NumInputs; ++i) {
    1514           0 :     if (!isPHIRegionIndex(PHIRegionIndices, i)) {
    1515             :       HasExternalEdge = true;
    1516             :     }
    1517             :   }
    1518             : 
    1519           0 :   if (HasExternalEdge) {
    1520           0 :     MachineBasicBlock *MBB = PHI.getParent();
    1521             :     MachineInstrBuilder MIB =
    1522           0 :         BuildMI(*MBB, PHI, PHI.getDebugLoc(), TII->get(TargetOpcode::PHI),
    1523           0 :                 getPHIDestReg(PHI));
    1524           0 :     MIB.addReg(CombinedSourceReg);
    1525             :     MIB.addMBB(LastMerge);
    1526             :     DEBUG(dbgs() << printReg(CombinedSourceReg, TRI) << ", "
    1527             :                  << printMBBReference(*LastMerge));
    1528           0 :     for (unsigned i = 0; i < NumInputs; ++i) {
    1529           0 :       if (isPHIRegionIndex(PHIRegionIndices, i)) {
    1530           0 :         continue;
    1531             :       }
    1532             :       unsigned SourceReg = getPHISourceReg(PHI, i);
    1533             :       MachineBasicBlock *SourcePred = getPHIPred(PHI, i);
    1534           0 :       MIB.addReg(SourceReg);
    1535             :       MIB.addMBB(SourcePred);
    1536             :       DEBUG(dbgs() << printReg(SourceReg, TRI) << ", "
    1537             :                    << printMBBReference(*SourcePred));
    1538             :     }
    1539             :     DEBUG(dbgs() << ")\n");
    1540             :   } else {
    1541           0 :     replaceRegisterWith(getPHIDestReg(PHI), CombinedSourceReg);
    1542             :   }
    1543           0 :   PHI.eraseFromParent();
    1544           0 : }
    1545             : 
    1546           0 : void AMDGPUMachineCFGStructurizer::replaceEntryPHI(
    1547             :     MachineInstr &PHI, unsigned CombinedSourceReg, MachineBasicBlock *IfMBB,
    1548             :     SmallVector<unsigned, 2> &PHIRegionIndices) {
    1549             :   DEBUG(dbgs() << "Replace entry PHI: ");
    1550             :   DEBUG(PHI.dump());
    1551             :   DEBUG(dbgs() << " with ");
    1552             : 
    1553             :   unsigned NumInputs = getPHINumInputs(PHI);
    1554             :   unsigned NumNonRegionInputs = NumInputs;
    1555           0 :   for (unsigned i = 0; i < NumInputs; ++i) {
    1556           0 :     if (isPHIRegionIndex(PHIRegionIndices, i)) {
    1557           0 :       NumNonRegionInputs--;
    1558             :     }
    1559             :   }
    1560             : 
    1561           0 :   if (NumNonRegionInputs == 0) {
    1562             :     auto DestReg = getPHIDestReg(PHI);
    1563           0 :     replaceRegisterWith(DestReg, CombinedSourceReg);
    1564             :     DEBUG(dbgs() << " register " << printReg(CombinedSourceReg, TRI) << "\n");
    1565           0 :     PHI.eraseFromParent();
    1566             :   } else {
    1567             :     DEBUG(dbgs() << printReg(getPHIDestReg(PHI), TRI) << " = PHI(");
    1568           0 :     MachineBasicBlock *MBB = PHI.getParent();
    1569             :     MachineInstrBuilder MIB =
    1570           0 :         BuildMI(*MBB, PHI, PHI.getDebugLoc(), TII->get(TargetOpcode::PHI),
    1571           0 :                 getPHIDestReg(PHI));
    1572           0 :     MIB.addReg(CombinedSourceReg);
    1573             :     MIB.addMBB(IfMBB);
    1574             :     DEBUG(dbgs() << printReg(CombinedSourceReg, TRI) << ", "
    1575             :                  << printMBBReference(*IfMBB));
    1576             :     unsigned NumInputs = getPHINumInputs(PHI);
    1577           0 :     for (unsigned i = 0; i < NumInputs; ++i) {
    1578           0 :       if (isPHIRegionIndex(PHIRegionIndices, i)) {
    1579           0 :         continue;
    1580             :       }
    1581             :       unsigned SourceReg = getPHISourceReg(PHI, i);
    1582             :       MachineBasicBlock *SourcePred = getPHIPred(PHI, i);
    1583           0 :       MIB.addReg(SourceReg);
    1584             :       MIB.addMBB(SourcePred);
    1585             :       DEBUG(dbgs() << printReg(SourceReg, TRI) << ", "
    1586             :                    << printMBBReference(*SourcePred));
    1587             :     }
    1588             :     DEBUG(dbgs() << ")\n");
    1589           0 :     PHI.eraseFromParent();
    1590             :   }
    1591           0 : }
    1592             : 
    1593           0 : void AMDGPUMachineCFGStructurizer::replaceLiveOutRegs(
    1594             :     MachineInstr &PHI, SmallVector<unsigned, 2> &PHIRegionIndices,
    1595             :     unsigned CombinedSourceReg, LinearizedRegion *LRegion) {
    1596             :   bool WasLiveOut = false;
    1597           0 :   for (auto PII : PHIRegionIndices) {
    1598             :     unsigned Reg = getPHISourceReg(PHI, PII);
    1599             :     if (LRegion->isLiveOut(Reg)) {
    1600             :       bool IsDead = true;
    1601             : 
    1602             :       // Check if register is live out of the basic block
    1603           0 :       MachineBasicBlock *DefMBB = getDefInstr(Reg)->getParent();
    1604           0 :       for (auto UI = MRI->use_begin(Reg), E = MRI->use_end(); UI != E; ++UI) {
    1605           0 :         if ((*UI).getParent()->getParent() != DefMBB) {
    1606             :           IsDead = false;
    1607             :         }
    1608             :       }
    1609             : 
    1610             :       DEBUG(dbgs() << "Register " << printReg(Reg, TRI) << " is "
    1611             :                    << (IsDead ? "dead" : "alive") << " after PHI replace\n");
    1612           0 :       if (IsDead) {
    1613           0 :         LRegion->removeLiveOut(Reg);
    1614             :       }
    1615             :       WasLiveOut = true;
    1616             :     }
    1617             :   }
    1618             : 
    1619           0 :   if (WasLiveOut)
    1620             :     LRegion->addLiveOut(CombinedSourceReg);
    1621           0 : }
    1622             : 
    1623           0 : void AMDGPUMachineCFGStructurizer::rewriteRegionExitPHI(RegionMRT *Region,
    1624             :                                                   MachineBasicBlock *LastMerge,
    1625             :                                                   MachineInstr &PHI,
    1626             :                                                   LinearizedRegion *LRegion) {
    1627             :   SmallVector<unsigned, 2> PHIRegionIndices;
    1628           0 :   getPHIRegionIndices(Region, PHI, PHIRegionIndices);
    1629             :   unsigned LinearizedSourceReg =
    1630           0 :       storePHILinearizationInfo(PHI, &PHIRegionIndices);
    1631             : 
    1632           0 :   replacePHI(PHI, LinearizedSourceReg, LastMerge, PHIRegionIndices);
    1633           0 :   replaceLiveOutRegs(PHI, PHIRegionIndices, LinearizedSourceReg, LRegion);
    1634           0 : }
    1635             : 
    1636           0 : void AMDGPUMachineCFGStructurizer::rewriteRegionEntryPHI(LinearizedRegion *Region,
    1637             :                                                    MachineBasicBlock *IfMBB,
    1638             :                                                    MachineInstr &PHI) {
    1639             :   SmallVector<unsigned, 2> PHINonRegionIndices;
    1640           0 :   getPHINonRegionIndices(Region, PHI, PHINonRegionIndices);
    1641             :   unsigned LinearizedSourceReg =
    1642           0 :       storePHILinearizationInfo(PHI, &PHINonRegionIndices);
    1643           0 :   replaceEntryPHI(PHI, LinearizedSourceReg, IfMBB, PHINonRegionIndices);
    1644           0 : }
    1645             : 
    1646           0 : static void collectPHIs(MachineBasicBlock *MBB,
    1647             :                         SmallVector<MachineInstr *, 2> &PHIs) {
    1648           0 :   for (auto &BBI : *MBB) {
    1649             :     if (BBI.isPHI()) {
    1650           0 :       PHIs.push_back(&BBI);
    1651             :     }
    1652             :   }
    1653           0 : }
    1654             : 
    1655           0 : void AMDGPUMachineCFGStructurizer::rewriteRegionExitPHIs(RegionMRT *Region,
    1656             :                                                    MachineBasicBlock *LastMerge,
    1657             :                                                    LinearizedRegion *LRegion) {
    1658             :   SmallVector<MachineInstr *, 2> PHIs;
    1659           0 :   auto Exit = Region->getSucc();
    1660           0 :   if (Exit == nullptr)
    1661             :     return;
    1662             : 
    1663           0 :   collectPHIs(Exit, PHIs);
    1664             : 
    1665           0 :   for (auto PHII : PHIs) {
    1666           0 :     rewriteRegionExitPHI(Region, LastMerge, *PHII, LRegion);
    1667             :   }
    1668             : }
    1669             : 
    1670           0 : void AMDGPUMachineCFGStructurizer::rewriteRegionEntryPHIs(LinearizedRegion *Region,
    1671             :                                                     MachineBasicBlock *IfMBB) {
    1672             :   SmallVector<MachineInstr *, 2> PHIs;
    1673           0 :   auto Entry = Region->getEntry();
    1674             : 
    1675           0 :   collectPHIs(Entry, PHIs);
    1676             : 
    1677           0 :   for (auto PHII : PHIs) {
    1678           0 :     rewriteRegionEntryPHI(Region, IfMBB, *PHII);
    1679             :   }
    1680           0 : }
    1681             : 
    1682           0 : void AMDGPUMachineCFGStructurizer::insertUnconditionalBranch(MachineBasicBlock *MBB,
    1683             :                                                        MachineBasicBlock *Dest,
    1684             :                                                        const DebugLoc &DL) {
    1685             :   DEBUG(dbgs() << "Inserting unconditional branch: " << MBB->getNumber()
    1686             :                << " -> " << Dest->getNumber() << "\n");
    1687           0 :   MachineBasicBlock::instr_iterator Terminator = MBB->getFirstInstrTerminator();
    1688             :   bool HasTerminator = Terminator != MBB->instr_end();
    1689           0 :   if (HasTerminator) {
    1690           0 :     TII->ReplaceTailWithBranchTo(Terminator, Dest);
    1691             :   }
    1692           0 :   if (++MachineFunction::iterator(MBB) != MachineFunction::iterator(Dest)) {
    1693           0 :     TII->insertUnconditionalBranch(*MBB, Dest, DL);
    1694             :   }
    1695           0 : }
    1696             : 
    1697             : static MachineBasicBlock *getSingleExitNode(MachineFunction &MF) {
    1698             :   MachineBasicBlock *result = nullptr;
    1699           0 :   for (auto &MFI : MF) {
    1700           0 :     if (MFI.succ_size() == 0) {
    1701           0 :       if (result == nullptr) {
    1702             :         result = &MFI;
    1703             :       } else {
    1704             :         return nullptr;
    1705             :       }
    1706             :     }
    1707             :   }
    1708             : 
    1709             :   return result;
    1710             : }
    1711             : 
    1712             : static bool hasOneExitNode(MachineFunction &MF) {
    1713             :   return getSingleExitNode(MF) != nullptr;
    1714             : }
    1715             : 
    1716             : MachineBasicBlock *
    1717           0 : AMDGPUMachineCFGStructurizer::createLinearizedExitBlock(RegionMRT *Region) {
    1718           0 :   auto Exit = Region->getSucc();
    1719             : 
    1720             :   // If the exit is the end of the function, we just use the existing
    1721           0 :   MachineFunction *MF = Region->getEntry()->getParent();
    1722           0 :   if (Exit == nullptr && hasOneExitNode(*MF)) {
    1723           0 :     return &(*(--(Region->getEntry()->getParent()->end())));
    1724             :   }
    1725             : 
    1726           0 :   MachineBasicBlock *LastMerge = MF->CreateMachineBasicBlock();
    1727           0 :   if (Exit == nullptr) {
    1728             :     MachineFunction::iterator ExitIter = MF->end();
    1729             :     MF->insert(ExitIter, LastMerge);
    1730             :   } else {
    1731           0 :     MachineFunction::iterator ExitIter = Exit->getIterator();
    1732             :     MF->insert(ExitIter, LastMerge);
    1733           0 :     LastMerge->addSuccessor(Exit);
    1734           0 :     insertUnconditionalBranch(LastMerge, Exit);
    1735             :     DEBUG(dbgs() << "Created exit block: " << LastMerge->getNumber() << "\n");
    1736             :   }
    1737             :   return LastMerge;
    1738             : }
    1739             : 
    1740           0 : void AMDGPUMachineCFGStructurizer::insertMergePHI(MachineBasicBlock *IfBB,
    1741             :                                             MachineBasicBlock *CodeBB,
    1742             :                                             MachineBasicBlock *MergeBB,
    1743             :                                             unsigned DestRegister,
    1744             :                                             unsigned IfSourceRegister,
    1745             :                                             unsigned CodeSourceRegister,
    1746             :                                             bool IsUndefIfSource) {
    1747             :   // If this is the function exit block, we don't need a phi.
    1748           0 :   if (MergeBB->succ_begin() == MergeBB->succ_end()) {
    1749           0 :     return;
    1750             :   }
    1751             :   DEBUG(dbgs() << "Merge PHI (" << printMBBReference(*MergeBB)
    1752             :                << "): " << printReg(DestRegister, TRI) << " = PHI("
    1753             :                << printReg(IfSourceRegister, TRI) << ", "
    1754             :                << printMBBReference(*IfBB) << printReg(CodeSourceRegister, TRI)
    1755             :                << ", " << printMBBReference(*CodeBB) << ")\n");
    1756             :   const DebugLoc &DL = MergeBB->findDebugLoc(MergeBB->begin());
    1757             :   MachineInstrBuilder MIB = BuildMI(*MergeBB, MergeBB->instr_begin(), DL,
    1758           0 :                                     TII->get(TargetOpcode::PHI), DestRegister);
    1759             :   if (IsUndefIfSource && false) {
    1760             :     MIB.addReg(IfSourceRegister, RegState::Undef);
    1761             :   } else {
    1762           0 :     MIB.addReg(IfSourceRegister);
    1763             :   }
    1764             :   MIB.addMBB(IfBB);
    1765           0 :   MIB.addReg(CodeSourceRegister);
    1766             :   MIB.addMBB(CodeBB);
    1767             : }
    1768             : 
    1769           0 : static void removeExternalCFGSuccessors(MachineBasicBlock *MBB) {
    1770             :   for (MachineBasicBlock::succ_iterator PI = MBB->succ_begin(),
    1771             :                                         E = MBB->succ_end();
    1772           0 :        PI != E; ++PI) {
    1773           0 :     if ((*PI) != MBB) {
    1774           0 :       (MBB)->removeSuccessor(*PI);
    1775             :     }
    1776             :   }
    1777           0 : }
    1778             : 
    1779           0 : static void removeExternalCFGEdges(MachineBasicBlock *StartMBB,
    1780             :                                    MachineBasicBlock *EndMBB) {
    1781             : 
    1782             :   // We have to check against the StartMBB successor becasuse a
    1783             :   // structurized region with a loop will have the entry block split,
    1784             :   // and the backedge will go to the entry successor.
    1785             :   DenseSet<std::pair<MachineBasicBlock *, MachineBasicBlock *>> Succs;
    1786             :   unsigned SuccSize = StartMBB->succ_size();
    1787           0 :   if (SuccSize > 0) {
    1788           0 :     MachineBasicBlock *StartMBBSucc = *(StartMBB->succ_begin());
    1789             :     for (MachineBasicBlock::succ_iterator PI = EndMBB->succ_begin(),
    1790             :                                           E = EndMBB->succ_end();
    1791           0 :          PI != E; ++PI) {
    1792             :       // Either we have a back-edge to the entry block, or a back-edge to the
    1793             :       // successor of the entry block since the block may be split.
    1794           0 :       if ((*PI) != StartMBB &&
    1795           0 :           !((*PI) == StartMBBSucc && StartMBB != EndMBB && SuccSize == 1)) {
    1796             :         Succs.insert(
    1797           0 :             std::pair<MachineBasicBlock *, MachineBasicBlock *>(EndMBB, *PI));
    1798             :       }
    1799             :     }
    1800             :   }
    1801             : 
    1802             :   for (MachineBasicBlock::pred_iterator PI = StartMBB->pred_begin(),
    1803             :                                         E = StartMBB->pred_end();
    1804           0 :        PI != E; ++PI) {
    1805           0 :     if ((*PI) != EndMBB) {
    1806             :       Succs.insert(
    1807           0 :           std::pair<MachineBasicBlock *, MachineBasicBlock *>(*PI, StartMBB));
    1808             :     }
    1809             :   }
    1810             : 
    1811           0 :   for (auto SI : Succs) {
    1812             :     std::pair<MachineBasicBlock *, MachineBasicBlock *> Edge = SI;
    1813             :     DEBUG(dbgs() << "Removing edge: " << printMBBReference(*Edge.first)
    1814             :                  << " -> " << printMBBReference(*Edge.second) << "\n");
    1815           0 :     Edge.first->removeSuccessor(Edge.second);
    1816             :   }
    1817           0 : }
    1818             : 
    1819           0 : MachineBasicBlock *AMDGPUMachineCFGStructurizer::createIfBlock(
    1820             :     MachineBasicBlock *MergeBB, MachineBasicBlock *CodeBBStart,
    1821             :     MachineBasicBlock *CodeBBEnd, MachineBasicBlock *SelectBB, unsigned IfReg,
    1822             :     bool InheritPreds) {
    1823           0 :   MachineFunction *MF = MergeBB->getParent();
    1824           0 :   MachineBasicBlock *IfBB = MF->CreateMachineBasicBlock();
    1825             : 
    1826           0 :   if (InheritPreds) {
    1827             :     for (MachineBasicBlock::pred_iterator PI = CodeBBStart->pred_begin(),
    1828             :                                           E = CodeBBStart->pred_end();
    1829           0 :          PI != E; ++PI) {
    1830           0 :       if ((*PI) != CodeBBEnd) {
    1831             :         MachineBasicBlock *Pred = (*PI);
    1832           0 :         Pred->addSuccessor(IfBB);
    1833             :       }
    1834             :     }
    1835             :   }
    1836             : 
    1837           0 :   removeExternalCFGEdges(CodeBBStart, CodeBBEnd);
    1838             : 
    1839           0 :   auto CodeBBStartI = CodeBBStart->getIterator();
    1840           0 :   auto CodeBBEndI = CodeBBEnd->getIterator();
    1841           0 :   auto MergeIter = MergeBB->getIterator();
    1842             :   MF->insert(MergeIter, IfBB);
    1843             :   MF->splice(MergeIter, CodeBBStartI, ++CodeBBEndI);
    1844           0 :   IfBB->addSuccessor(MergeBB);
    1845           0 :   IfBB->addSuccessor(CodeBBStart);
    1846             : 
    1847             :   DEBUG(dbgs() << "Created If block: " << IfBB->getNumber() << "\n");
    1848             :   // Ensure that the MergeBB is a successor of the CodeEndBB.
    1849           0 :   if (!CodeBBEnd->isSuccessor(MergeBB))
    1850           0 :     CodeBBEnd->addSuccessor(MergeBB);
    1851             : 
    1852             :   DEBUG(dbgs() << "Moved " << printMBBReference(*CodeBBStart) << " through "
    1853             :                << printMBBReference(*CodeBBEnd) << "\n");
    1854             : 
    1855             :   // If we have a single predecessor we can find a reasonable debug location
    1856             :   MachineBasicBlock *SinglePred =
    1857           0 :       CodeBBStart->pred_size() == 1 ? *(CodeBBStart->pred_begin()) : nullptr;
    1858             :   const DebugLoc &DL = SinglePred
    1859             :                     ? SinglePred->findDebugLoc(SinglePred->getFirstTerminator())
    1860           0 :                     : DebugLoc();
    1861             : 
    1862             :   unsigned Reg =
    1863           0 :       TII->insertEQ(IfBB, IfBB->begin(), DL, IfReg,
    1864           0 :                     SelectBB->getNumber() /* CodeBBStart->getNumber() */);
    1865           0 :   if (&(*(IfBB->getParent()->begin())) == IfBB) {
    1866           0 :     TII->materializeImmediate(*IfBB, IfBB->begin(), DL, IfReg,
    1867           0 :                               CodeBBStart->getNumber());
    1868             :   }
    1869             :   MachineOperand RegOp = MachineOperand::CreateReg(Reg, false, false, true);
    1870             :   ArrayRef<MachineOperand> Cond(RegOp);
    1871           0 :   TII->insertBranch(*IfBB, MergeBB, CodeBBStart, Cond, DL);
    1872             : 
    1873           0 :   return IfBB;
    1874             : }
    1875             : 
    1876           0 : void AMDGPUMachineCFGStructurizer::ensureCondIsNotKilled(
    1877             :     SmallVector<MachineOperand, 1> Cond) {
    1878           0 :   if (Cond.size() != 1)
    1879             :     return;
    1880           0 :   if (!Cond[0].isReg())
    1881             :     return;
    1882             : 
    1883           0 :   unsigned CondReg = Cond[0].getReg();
    1884           0 :   for (auto UI = MRI->use_begin(CondReg), E = MRI->use_end(); UI != E; ++UI) {
    1885             :     (*UI).setIsKill(false);
    1886             :   }
    1887             : }
    1888             : 
    1889           0 : void AMDGPUMachineCFGStructurizer::rewriteCodeBBTerminator(MachineBasicBlock *CodeBB,
    1890             :                                                      MachineBasicBlock *MergeBB,
    1891             :                                                      unsigned BBSelectReg) {
    1892           0 :   MachineBasicBlock *TrueBB = nullptr;
    1893           0 :   MachineBasicBlock *FalseBB = nullptr;
    1894             :   SmallVector<MachineOperand, 1> Cond;
    1895           0 :   MachineBasicBlock *FallthroughBB = FallthroughMap[CodeBB];
    1896           0 :   TII->analyzeBranch(*CodeBB, TrueBB, FalseBB, Cond);
    1897             : 
    1898           0 :   const DebugLoc &DL = CodeBB->findDebugLoc(CodeBB->getFirstTerminator());
    1899             : 
    1900           0 :   if (FalseBB == nullptr && TrueBB == nullptr && FallthroughBB == nullptr) {
    1901             :     // This is an exit block, hence no successors. We will assign the
    1902             :     // bb select register to the entry block.
    1903           0 :     TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
    1904             :                               BBSelectReg,
    1905           0 :                               CodeBB->getParent()->begin()->getNumber());
    1906           0 :     insertUnconditionalBranch(CodeBB, MergeBB, DL);
    1907             :     return;
    1908             :   }
    1909             : 
    1910           0 :   if (FalseBB == nullptr && TrueBB == nullptr) {
    1911           0 :     TrueBB = FallthroughBB;
    1912           0 :   } else if (TrueBB != nullptr) {
    1913           0 :     FalseBB =
    1914           0 :         (FallthroughBB && (FallthroughBB != TrueBB)) ? FallthroughBB : FalseBB;
    1915             :   }
    1916             : 
    1917           0 :   if ((TrueBB != nullptr && FalseBB == nullptr) || (TrueBB == FalseBB)) {
    1918           0 :     TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
    1919           0 :                               BBSelectReg, TrueBB->getNumber());
    1920             :   } else {
    1921           0 :     const TargetRegisterClass *RegClass = MRI->getRegClass(BBSelectReg);
    1922           0 :     unsigned TrueBBReg = MRI->createVirtualRegister(RegClass);
    1923           0 :     unsigned FalseBBReg = MRI->createVirtualRegister(RegClass);
    1924           0 :     TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
    1925           0 :                               TrueBBReg, TrueBB->getNumber());
    1926           0 :     TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
    1927           0 :                               FalseBBReg, FalseBB->getNumber());
    1928           0 :     ensureCondIsNotKilled(Cond);
    1929           0 :     TII->insertVectorSelect(*CodeBB, CodeBB->getFirstTerminator(), DL,
    1930             :                             BBSelectReg, Cond, TrueBBReg, FalseBBReg);
    1931             :   }
    1932             : 
    1933           0 :   insertUnconditionalBranch(CodeBB, MergeBB, DL);
    1934             : }
    1935             : 
    1936           0 : MachineInstr *AMDGPUMachineCFGStructurizer::getDefInstr(unsigned Reg) {
    1937           0 :   if (MRI->def_begin(Reg) == MRI->def_end()) {
    1938             :     DEBUG(dbgs() << "Register " << printReg(Reg, MRI->getTargetRegisterInfo())
    1939             :                  << " has NO defs\n");
    1940           0 :   } else if (!MRI->hasOneDef(Reg)) {
    1941             :     DEBUG(dbgs() << "Register " << printReg(Reg, MRI->getTargetRegisterInfo())
    1942             :                  << " has multiple defs\n");
    1943             :     DEBUG(dbgs() << "DEFS BEGIN:\n");
    1944           0 :     for (auto DI = MRI->def_begin(Reg), DE = MRI->def_end(); DI != DE; ++DI) {
    1945             :       DEBUG(DI->getParent()->dump());
    1946             :     }
    1947             :     DEBUG(dbgs() << "DEFS END\n");
    1948             :   }
    1949             : 
    1950             :   assert(MRI->hasOneDef(Reg) && "Register has multiple definitions");
    1951           0 :   return (*(MRI->def_begin(Reg))).getParent();
    1952             : }
    1953             : 
    1954           0 : void AMDGPUMachineCFGStructurizer::insertChainedPHI(MachineBasicBlock *IfBB,
    1955             :                                               MachineBasicBlock *CodeBB,
    1956             :                                               MachineBasicBlock *MergeBB,
    1957             :                                               LinearizedRegion *InnerRegion,
    1958             :                                               unsigned DestReg,
    1959             :                                               unsigned SourceReg) {
    1960             :   // In this function we know we are part of a chain already, so we need
    1961             :   // to add the registers to the existing chain, and rename the register
    1962             :   // inside the region.
    1963           0 :   bool IsSingleBB = InnerRegion->getEntry() == InnerRegion->getExit();
    1964           0 :   MachineInstr *DefInstr = getDefInstr(SourceReg);
    1965           0 :   if (DefInstr->isPHI() && DefInstr->getParent() == CodeBB && IsSingleBB) {
    1966             :     // Handle the case where the def is a PHI-def inside a basic
    1967             :     // block, then we only need to do renaming. Special care needs to
    1968             :     // be taken if the PHI-def is part of an existing chain, or if a
    1969             :     // new one needs to be created.
    1970           0 :     InnerRegion->replaceRegisterInsideRegion(SourceReg, DestReg, true, MRI);
    1971             : 
    1972             :     // We collect all PHI Information, and if we are at the region entry,
    1973             :     // all PHIs will be removed, and then re-introduced if needed.
    1974           0 :     storePHILinearizationInfoDest(DestReg, *DefInstr);
    1975             :     // We have picked up all the information we need now and can remove
    1976             :     // the PHI
    1977           0 :     PHIInfo.removeSource(DestReg, SourceReg, CodeBB);
    1978           0 :     DefInstr->eraseFromParent();
    1979             :   } else {
    1980             :     // If this is not a phi-def, or it is a phi-def but from a linearized region
    1981           0 :     if (IsSingleBB && DefInstr->getParent() == InnerRegion->getEntry()) {
    1982             :       // If this is a single BB and the definition is in this block we
    1983             :       // need to replace any uses outside the region.
    1984           0 :       InnerRegion->replaceRegisterOutsideRegion(SourceReg, DestReg, false, MRI);
    1985             :     }
    1986           0 :     const TargetRegisterClass *RegClass = MRI->getRegClass(DestReg);
    1987           0 :     unsigned NextDestReg = MRI->createVirtualRegister(RegClass);
    1988           0 :     bool IsLastDef = PHIInfo.getNumSources(DestReg) == 1;
    1989             :     DEBUG(dbgs() << "Insert Chained PHI\n");
    1990           0 :     insertMergePHI(IfBB, InnerRegion->getExit(), MergeBB, DestReg, NextDestReg,
    1991             :                    SourceReg, IsLastDef);
    1992             : 
    1993             :     PHIInfo.removeSource(DestReg, SourceReg, CodeBB);
    1994           0 :     if (IsLastDef) {
    1995           0 :       const DebugLoc &DL = IfBB->findDebugLoc(IfBB->getFirstTerminator());
    1996           0 :       TII->materializeImmediate(*IfBB, IfBB->getFirstTerminator(), DL,
    1997             :                                 NextDestReg, 0);
    1998           0 :       PHIInfo.deleteDef(DestReg);
    1999             :     } else {
    2000             :       PHIInfo.replaceDef(DestReg, NextDestReg);
    2001             :     }
    2002             :   }
    2003           0 : }
    2004             : 
    2005           0 : bool AMDGPUMachineCFGStructurizer::containsDef(MachineBasicBlock *MBB,
    2006             :                                          LinearizedRegion *InnerRegion,
    2007             :                                          unsigned Register) {
    2008           0 :   return getDefInstr(Register)->getParent() == MBB ||
    2009           0 :          InnerRegion->contains(getDefInstr(Register)->getParent());
    2010             : }
    2011             : 
    2012           0 : void AMDGPUMachineCFGStructurizer::rewriteLiveOutRegs(MachineBasicBlock *IfBB,
    2013             :                                                 MachineBasicBlock *CodeBB,
    2014             :                                                 MachineBasicBlock *MergeBB,
    2015             :                                                 LinearizedRegion *InnerRegion,
    2016             :                                                 LinearizedRegion *LRegion) {
    2017             :   DenseSet<unsigned> *LiveOuts = InnerRegion->getLiveOuts();
    2018             :   SmallVector<unsigned, 4> OldLiveOuts;
    2019           0 :   bool IsSingleBB = InnerRegion->getEntry() == InnerRegion->getExit();
    2020           0 :   for (auto OLI : *LiveOuts) {
    2021           0 :     OldLiveOuts.push_back(OLI);
    2022             :   }
    2023             : 
    2024           0 :   for (auto LI : OldLiveOuts) {
    2025             :     DEBUG(dbgs() << "LiveOut: " << printReg(LI, TRI));
    2026           0 :     if (!containsDef(CodeBB, InnerRegion, LI) ||
    2027           0 :         (!IsSingleBB && (getDefInstr(LI)->getParent() == LRegion->getExit()))) {
    2028             :       // If the register simly lives through the CodeBB, we don't have
    2029             :       // to rewrite anything since the register is not defined in this
    2030             :       // part of the code.
    2031             :       DEBUG(dbgs() << "- through");
    2032           0 :       continue;
    2033             :     }
    2034             :     DEBUG(dbgs() << "\n");
    2035             :     unsigned Reg = LI;
    2036           0 :     if (/*!PHIInfo.isSource(Reg) &&*/ Reg != InnerRegion->getBBSelectRegOut()) {
    2037             :       // If the register is live out, we do want to create a phi,
    2038             :       // unless it is from the Exit block, becasuse in that case there
    2039             :       // is already a PHI, and no need to create a new one.
    2040             : 
    2041             :       // If the register is just a live out def and not part of a phi
    2042             :       // chain, we need to create a PHI node to handle the if region,
    2043             :       // and replace all uses outside of the region with the new dest
    2044             :       // register, unless it is the outgoing BB select register. We have
    2045             :       // already creaed phi nodes for these.
    2046           0 :       const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
    2047           0 :       unsigned PHIDestReg = MRI->createVirtualRegister(RegClass);
    2048           0 :       unsigned IfSourceReg = MRI->createVirtualRegister(RegClass);
    2049             :       // Create initializer, this value is never used, but is needed
    2050             :       // to satisfy SSA.
    2051             :       DEBUG(dbgs() << "Initializer for reg: " << printReg(Reg) << "\n");
    2052           0 :       TII->materializeImmediate(*IfBB, IfBB->getFirstTerminator(), DebugLoc(),
    2053             :                         IfSourceReg, 0);
    2054             : 
    2055           0 :       InnerRegion->replaceRegisterOutsideRegion(Reg, PHIDestReg, true, MRI);
    2056             :       DEBUG(dbgs() << "Insert Non-Chained Live out PHI\n");
    2057           0 :       insertMergePHI(IfBB, InnerRegion->getExit(), MergeBB, PHIDestReg,
    2058             :                      IfSourceReg, Reg, true);
    2059             :     }
    2060             :   }
    2061             : 
    2062             :   // Handle the chained definitions in PHIInfo, checking if this basic block
    2063             :   // is a source block for a definition.
    2064             :   SmallVector<unsigned, 4> Sources;
    2065           0 :   if (PHIInfo.findSourcesFromMBB(CodeBB, Sources)) {
    2066             :     DEBUG(dbgs() << "Inserting PHI Live Out from " << printMBBReference(*CodeBB)
    2067             :                  << "\n");
    2068           0 :     for (auto SI : Sources) {
    2069             :       unsigned DestReg;
    2070             :       PHIInfo.findDest(SI, CodeBB, DestReg);
    2071           0 :       insertChainedPHI(IfBB, CodeBB, MergeBB, InnerRegion, DestReg, SI);
    2072             :     }
    2073             :     DEBUG(dbgs() << "Insertion done.\n");
    2074             :   }
    2075             : 
    2076             :   DEBUG(PHIInfo.dump(MRI));
    2077           0 : }
    2078             : 
    2079           0 : void AMDGPUMachineCFGStructurizer::prunePHIInfo(MachineBasicBlock *MBB) {
    2080             :   DEBUG(dbgs() << "Before PHI Prune\n");
    2081             :   DEBUG(PHIInfo.dump(MRI));
    2082             :   SmallVector<std::tuple<unsigned, unsigned, MachineBasicBlock *>, 4>
    2083             :       ElimiatedSources;
    2084           0 :   for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
    2085             :        ++DRI) {
    2086             : 
    2087             :     unsigned DestReg = *DRI;
    2088           0 :     auto SE = PHIInfo.sources_end(DestReg);
    2089             : 
    2090             :     bool MBBContainsPHISource = false;
    2091             :     // Check if there is a PHI source in this MBB
    2092           0 :     for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
    2093           0 :       unsigned SourceReg = (*SRI).first;
    2094           0 :       MachineOperand *Def = &(*(MRI->def_begin(SourceReg)));
    2095           0 :       if (Def->getParent()->getParent() == MBB) {
    2096             :         MBBContainsPHISource = true;
    2097             :       }
    2098             :     }
    2099             : 
    2100             :     // If so, all other sources are useless since we know this block
    2101             :     // is always executed when the region is executed.
    2102           0 :     if (MBBContainsPHISource) {
    2103           0 :       for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
    2104           0 :         PHILinearize::PHISourceT Source = *SRI;
    2105             :         unsigned SourceReg = Source.first;
    2106             :         MachineBasicBlock *SourceMBB = Source.second;
    2107           0 :         MachineOperand *Def = &(*(MRI->def_begin(SourceReg)));
    2108           0 :         if (Def->getParent()->getParent() != MBB) {
    2109           0 :           ElimiatedSources.push_back(
    2110           0 :               std::make_tuple(DestReg, SourceReg, SourceMBB));
    2111             :         }
    2112             :       }
    2113             :     }
    2114             :   }
    2115             : 
    2116             :   // Remove the PHI sources that are in the given MBB
    2117           0 :   for (auto &SourceInfo : ElimiatedSources) {
    2118           0 :     PHIInfo.removeSource(std::get<0>(SourceInfo), std::get<1>(SourceInfo),
    2119             :                          std::get<2>(SourceInfo));
    2120             :   }
    2121             :   DEBUG(dbgs() << "After PHI Prune\n");
    2122             :   DEBUG(PHIInfo.dump(MRI));
    2123           0 : }
    2124             : 
    2125           0 : void AMDGPUMachineCFGStructurizer::createEntryPHI(LinearizedRegion *CurrentRegion,
    2126             :                                             unsigned DestReg) {
    2127           0 :   MachineBasicBlock *Entry = CurrentRegion->getEntry();
    2128           0 :   MachineBasicBlock *Exit = CurrentRegion->getExit();
    2129             : 
    2130             :   DEBUG(dbgs() << "RegionExit: " << Exit->getNumber()
    2131             :                << " Pred: " << (*(Entry->pred_begin()))->getNumber() << "\n");
    2132             : 
    2133             :   int NumSources = 0;
    2134           0 :   auto SE = PHIInfo.sources_end(DestReg);
    2135             : 
    2136           0 :   for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
    2137           0 :     NumSources++;
    2138             :   }
    2139             : 
    2140           0 :   if (NumSources == 1) {
    2141           0 :     auto SRI = PHIInfo.sources_begin(DestReg);
    2142           0 :     unsigned SourceReg = (*SRI).first;
    2143           0 :     replaceRegisterWith(DestReg, SourceReg);
    2144             :   } else {
    2145             :     const DebugLoc &DL = Entry->findDebugLoc(Entry->begin());
    2146             :     MachineInstrBuilder MIB = BuildMI(*Entry, Entry->instr_begin(), DL,
    2147           0 :                                       TII->get(TargetOpcode::PHI), DestReg);
    2148             :     DEBUG(dbgs() << "Entry PHI " << printReg(DestReg, TRI) << " = PHI(");
    2149             : 
    2150             :     unsigned CurrentBackedgeReg = 0;
    2151             : 
    2152           0 :     for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
    2153           0 :       unsigned SourceReg = (*SRI).first;
    2154             : 
    2155           0 :       if (CurrentRegion->contains((*SRI).second)) {
    2156           0 :         if (CurrentBackedgeReg == 0) {
    2157             :           CurrentBackedgeReg = SourceReg;
    2158             :         } else {
    2159           0 :           MachineInstr *PHIDefInstr = getDefInstr(SourceReg);
    2160           0 :           MachineBasicBlock *PHIDefMBB = PHIDefInstr->getParent();
    2161             :           const TargetRegisterClass *RegClass =
    2162           0 :               MRI->getRegClass(CurrentBackedgeReg);
    2163           0 :           unsigned NewBackedgeReg = MRI->createVirtualRegister(RegClass);
    2164             :           MachineInstrBuilder BackedgePHI =
    2165             :               BuildMI(*PHIDefMBB, PHIDefMBB->instr_begin(), DL,
    2166           0 :                       TII->get(TargetOpcode::PHI), NewBackedgeReg);
    2167           0 :           BackedgePHI.addReg(CurrentBackedgeReg);
    2168             :           BackedgePHI.addMBB(getPHIPred(*PHIDefInstr, 0));
    2169           0 :           BackedgePHI.addReg(getPHISourceReg(*PHIDefInstr, 1));
    2170           0 :           BackedgePHI.addMBB((*SRI).second);
    2171             :           CurrentBackedgeReg = NewBackedgeReg;
    2172             :           DEBUG(dbgs() << "Inserting backedge PHI: "
    2173             :                        << printReg(NewBackedgeReg, TRI) << " = PHI("
    2174             :                        << printReg(CurrentBackedgeReg, TRI) << ", "
    2175             :                        << printMBBReference(*getPHIPred(*PHIDefInstr, 0))
    2176             :                        << ", "
    2177             :                        << printReg(getPHISourceReg(*PHIDefInstr, 1), TRI)
    2178             :                        << ", " << printMBBReference(*(*SRI).second));
    2179             :         }
    2180             :       } else {
    2181           0 :         MIB.addReg(SourceReg);
    2182           0 :         MIB.addMBB((*SRI).second);
    2183             :         DEBUG(dbgs() << printReg(SourceReg, TRI) << ", "
    2184             :                      << printMBBReference(*(*SRI).second) << ", ");
    2185             :       }
    2186             :     }
    2187             : 
    2188             :     // Add the final backedge register source to the entry phi
    2189           0 :     if (CurrentBackedgeReg != 0) {
    2190           0 :       MIB.addReg(CurrentBackedgeReg);
    2191             :       MIB.addMBB(Exit);
    2192             :       DEBUG(dbgs() << printReg(CurrentBackedgeReg, TRI) << ", "
    2193             :                    << printMBBReference(*Exit) << ")\n");
    2194             :     } else {
    2195             :       DEBUG(dbgs() << ")\n");
    2196             :     }
    2197             :   }
    2198           0 : }
    2199             : 
    2200           0 : void AMDGPUMachineCFGStructurizer::createEntryPHIs(LinearizedRegion *CurrentRegion) {
    2201             :   DEBUG(PHIInfo.dump(MRI));
    2202             : 
    2203           0 :   for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
    2204             :        ++DRI) {
    2205             : 
    2206             :     unsigned DestReg = *DRI;
    2207           0 :     createEntryPHI(CurrentRegion, DestReg);
    2208             :   }
    2209           0 :   PHIInfo.clear();
    2210           0 : }
    2211             : 
    2212           0 : void AMDGPUMachineCFGStructurizer::replaceRegisterWith(unsigned Register,
    2213             :                                                  unsigned NewRegister) {
    2214             :   assert(Register != NewRegister && "Cannot replace a reg with itself");
    2215             : 
    2216           0 :   for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Register),
    2217             :                                          E = MRI->reg_end();
    2218           0 :        I != E;) {
    2219             :     MachineOperand &O = *I;
    2220             :     ++I;
    2221           0 :     if (TargetRegisterInfo::isPhysicalRegister(NewRegister)) {
    2222             :       DEBUG(dbgs() << "Trying to substitute physical register: "
    2223             :                    << printReg(NewRegister, MRI->getTargetRegisterInfo())
    2224             :                    << "\n");
    2225           0 :       llvm_unreachable("Cannot substitute physical registers");
    2226             :       // We don't handle physical registers, but if we need to
    2227             :       // in the future This is how we do it:
    2228             :       // O.substPhysReg(NewRegister, *TRI);
    2229             :     } else {
    2230             :       DEBUG(dbgs() << "Replacing register: "
    2231             :                    << printReg(Register, MRI->getTargetRegisterInfo())
    2232             :                    << " with "
    2233             :                    << printReg(NewRegister, MRI->getTargetRegisterInfo())
    2234             :                    << "\n");
    2235           0 :       O.setReg(NewRegister);
    2236             :     }
    2237             :   }
    2238           0 :   PHIInfo.deleteDef(Register);
    2239             : 
    2240           0 :   getRegionMRT()->replaceLiveOutReg(Register, NewRegister);
    2241             : 
    2242             :   DEBUG(PHIInfo.dump(MRI));
    2243           0 : }
    2244             : 
    2245           0 : void AMDGPUMachineCFGStructurizer::resolvePHIInfos(MachineBasicBlock *FunctionEntry) {
    2246             :   DEBUG(dbgs() << "Resolve PHI Infos\n");
    2247             :   DEBUG(PHIInfo.dump(MRI));
    2248           0 :   for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
    2249             :        ++DRI) {
    2250             :     unsigned DestReg = *DRI;
    2251             :     DEBUG(dbgs() << "DestReg: " << printReg(DestReg, TRI) << "\n");
    2252           0 :     auto SRI = PHIInfo.sources_begin(DestReg);
    2253           0 :     unsigned SourceReg = (*SRI).first;
    2254             :     DEBUG(dbgs() << "DestReg: " << printReg(DestReg, TRI)
    2255             :                  << " SourceReg: " << printReg(SourceReg, TRI) << "\n");
    2256             : 
    2257             :     assert(PHIInfo.sources_end(DestReg) == ++SRI &&
    2258             :            "More than one phi source in entry node");
    2259           0 :     replaceRegisterWith(DestReg, SourceReg);
    2260             :   }
    2261           0 : }
    2262             : 
    2263             : static bool isFunctionEntryBlock(MachineBasicBlock *MBB) {
    2264           0 :   return ((&(*(MBB->getParent()->begin()))) == MBB);
    2265             : }
    2266             : 
    2267           0 : MachineBasicBlock *AMDGPUMachineCFGStructurizer::createIfRegion(
    2268             :     MachineBasicBlock *MergeBB, MachineBasicBlock *CodeBB,
    2269             :     LinearizedRegion *CurrentRegion, unsigned BBSelectRegIn,
    2270             :     unsigned BBSelectRegOut) {
    2271           0 :   if (isFunctionEntryBlock(CodeBB) && !CurrentRegion->getHasLoop()) {
    2272             :     // Handle non-loop function entry block.
    2273             :     // We need to allow loops to the entry block and then
    2274           0 :     rewriteCodeBBTerminator(CodeBB, MergeBB, BBSelectRegOut);
    2275           0 :     resolvePHIInfos(CodeBB);
    2276           0 :     removeExternalCFGSuccessors(CodeBB);
    2277           0 :     CodeBB->addSuccessor(MergeBB);
    2278             :     CurrentRegion->addMBB(CodeBB);
    2279           0 :     return nullptr;
    2280             :   }
    2281           0 :   if (CurrentRegion->getEntry() == CodeBB && !CurrentRegion->getHasLoop()) {
    2282             :     // Handle non-loop region entry block.
    2283           0 :     MachineFunction *MF = MergeBB->getParent();
    2284           0 :     auto MergeIter = MergeBB->getIterator();
    2285           0 :     auto CodeBBStartIter = CodeBB->getIterator();
    2286             :     auto CodeBBEndIter = ++(CodeBB->getIterator());
    2287           0 :     if (CodeBBEndIter != MergeIter) {
    2288             :       MF->splice(MergeIter, CodeBBStartIter, CodeBBEndIter);
    2289             :     }
    2290           0 :     rewriteCodeBBTerminator(CodeBB, MergeBB, BBSelectRegOut);
    2291           0 :     prunePHIInfo(CodeBB);
    2292           0 :     createEntryPHIs(CurrentRegion);
    2293           0 :     removeExternalCFGSuccessors(CodeBB);
    2294           0 :     CodeBB->addSuccessor(MergeBB);
    2295             :     CurrentRegion->addMBB(CodeBB);
    2296             :     return nullptr;
    2297             :   } else {
    2298             :     // Handle internal block.
    2299           0 :     const TargetRegisterClass *RegClass = MRI->getRegClass(BBSelectRegIn);
    2300           0 :     unsigned CodeBBSelectReg = MRI->createVirtualRegister(RegClass);
    2301           0 :     rewriteCodeBBTerminator(CodeBB, MergeBB, CodeBBSelectReg);
    2302           0 :     bool IsRegionEntryBB = CurrentRegion->getEntry() == CodeBB;
    2303           0 :     MachineBasicBlock *IfBB = createIfBlock(MergeBB, CodeBB, CodeBB, CodeBB,
    2304           0 :                                             BBSelectRegIn, IsRegionEntryBB);
    2305             :     CurrentRegion->addMBB(IfBB);
    2306             :     // If this is the entry block we need to make the If block the new
    2307             :     // linearized region entry.
    2308           0 :     if (IsRegionEntryBB) {
    2309             :       CurrentRegion->setEntry(IfBB);
    2310             : 
    2311           0 :       if (CurrentRegion->getHasLoop()) {
    2312           0 :         MachineBasicBlock *RegionExit = CurrentRegion->getExit();
    2313           0 :         MachineBasicBlock *ETrueBB = nullptr;
    2314           0 :         MachineBasicBlock *EFalseBB = nullptr;
    2315             :         SmallVector<MachineOperand, 1> ECond;
    2316             : 
    2317           0 :         const DebugLoc &DL = DebugLoc();
    2318           0 :         TII->analyzeBranch(*RegionExit, ETrueBB, EFalseBB, ECond);
    2319           0 :         TII->removeBranch(*RegionExit);
    2320             : 
    2321             :         // We need to create a backedge if there is a loop
    2322           0 :         unsigned Reg = TII->insertNE(
    2323             :             RegionExit, RegionExit->instr_end(), DL,
    2324             :             CurrentRegion->getRegionMRT()->getInnerOutputRegister(),
    2325           0 :             CurrentRegion->getRegionMRT()->getEntry()->getNumber());
    2326             :         MachineOperand RegOp =
    2327             :             MachineOperand::CreateReg(Reg, false, false, true);
    2328             :         ArrayRef<MachineOperand> Cond(RegOp);
    2329             :         DEBUG(dbgs() << "RegionExitReg: ");
    2330             :         DEBUG(Cond[0].print(dbgs(), TRI));
    2331             :         DEBUG(dbgs() << "\n");
    2332           0 :         TII->insertBranch(*RegionExit, CurrentRegion->getEntry(), RegionExit,
    2333           0 :                           Cond, DebugLoc());
    2334           0 :         RegionExit->addSuccessor(CurrentRegion->getEntry());
    2335             :       }
    2336             :     }
    2337             :     CurrentRegion->addMBB(CodeBB);
    2338           0 :     LinearizedRegion InnerRegion(CodeBB, MRI, TRI, PHIInfo);
    2339             : 
    2340             :     InnerRegion.setParent(CurrentRegion);
    2341             :     DEBUG(dbgs() << "Insert BB Select PHI (BB)\n");
    2342           0 :     insertMergePHI(IfBB, CodeBB, MergeBB, BBSelectRegOut, BBSelectRegIn,
    2343             :                    CodeBBSelectReg);
    2344             :     InnerRegion.addMBB(MergeBB);
    2345             : 
    2346             :     DEBUG(InnerRegion.print(dbgs(), TRI));
    2347           0 :     rewriteLiveOutRegs(IfBB, CodeBB, MergeBB, &InnerRegion, CurrentRegion);
    2348           0 :     extractKilledPHIs(CodeBB);
    2349           0 :     if (IsRegionEntryBB) {
    2350           0 :       createEntryPHIs(CurrentRegion);
    2351             :     }
    2352             :     return IfBB;
    2353             :   }
    2354             : }
    2355             : 
    2356           0 : MachineBasicBlock *AMDGPUMachineCFGStructurizer::createIfRegion(
    2357             :     MachineBasicBlock *MergeBB, LinearizedRegion *InnerRegion,
    2358             :     LinearizedRegion *CurrentRegion, MachineBasicBlock *SelectBB,
    2359             :     unsigned BBSelectRegIn, unsigned BBSelectRegOut) {
    2360             :   unsigned CodeBBSelectReg =
    2361           0 :       InnerRegion->getRegionMRT()->getInnerOutputRegister();
    2362           0 :   MachineBasicBlock *CodeEntryBB = InnerRegion->getEntry();
    2363           0 :   MachineBasicBlock *CodeExitBB = InnerRegion->getExit();
    2364             :   MachineBasicBlock *IfBB = createIfBlock(MergeBB, CodeEntryBB, CodeExitBB,
    2365           0 :                                           SelectBB, BBSelectRegIn, true);
    2366             :   CurrentRegion->addMBB(IfBB);
    2367           0 :   bool isEntry = CurrentRegion->getEntry() == InnerRegion->getEntry();
    2368           0 :   if (isEntry) {
    2369             : 
    2370           0 :     if (CurrentRegion->getHasLoop()) {
    2371           0 :       MachineBasicBlock *RegionExit = CurrentRegion->getExit();
    2372           0 :       MachineBasicBlock *ETrueBB = nullptr;
    2373           0 :       MachineBasicBlock *EFalseBB = nullptr;
    2374             :       SmallVector<MachineOperand, 1> ECond;
    2375             : 
    2376           0 :       const DebugLoc &DL = DebugLoc();
    2377           0 :       TII->analyzeBranch(*RegionExit, ETrueBB, EFalseBB, ECond);
    2378           0 :       TII->removeBranch(*RegionExit);
    2379             : 
    2380             :       // We need to create a backedge if there is a loop
    2381             :       unsigned Reg =
    2382           0 :           TII->insertNE(RegionExit, RegionExit->instr_end(), DL,
    2383             :                         CurrentRegion->getRegionMRT()->getInnerOutputRegister(),
    2384           0 :                         CurrentRegion->getRegionMRT()->getEntry()->getNumber());
    2385             :       MachineOperand RegOp = MachineOperand::CreateReg(Reg, false, false, true);
    2386             :       ArrayRef<MachineOperand> Cond(RegOp);
    2387             :       DEBUG(dbgs() << "RegionExitReg: ");
    2388             :       DEBUG(Cond[0].print(dbgs(), TRI));
    2389             :       DEBUG(dbgs() << "\n");
    2390           0 :       TII->insertBranch(*RegionExit, CurrentRegion->getEntry(), RegionExit,
    2391           0 :                         Cond, DebugLoc());
    2392           0 :       RegionExit->addSuccessor(IfBB);
    2393             :     }
    2394             :   }
    2395           0 :   CurrentRegion->addMBBs(InnerRegion);
    2396             :   DEBUG(dbgs() << "Insert BB Select PHI (region)\n");
    2397           0 :   insertMergePHI(IfBB, CodeExitBB, MergeBB, BBSelectRegOut, BBSelectRegIn,
    2398             :                  CodeBBSelectReg);
    2399             : 
    2400           0 :   rewriteLiveOutRegs(IfBB, /* CodeEntryBB */ CodeExitBB, MergeBB, InnerRegion,
    2401             :                      CurrentRegion);
    2402             : 
    2403           0 :   rewriteRegionEntryPHIs(InnerRegion, IfBB);
    2404             : 
    2405           0 :   if (isEntry) {
    2406             :     CurrentRegion->setEntry(IfBB);
    2407             :   }
    2408             : 
    2409           0 :   if (isEntry) {
    2410           0 :     createEntryPHIs(CurrentRegion);
    2411             :   }
    2412             : 
    2413           0 :   return IfBB;
    2414             : }
    2415             : 
    2416           0 : void AMDGPUMachineCFGStructurizer::splitLoopPHI(MachineInstr &PHI,
    2417             :                                           MachineBasicBlock *Entry,
    2418             :                                           MachineBasicBlock *EntrySucc,
    2419             :                                           LinearizedRegion *LRegion) {
    2420             :   SmallVector<unsigned, 2> PHIRegionIndices;
    2421           0 :   getPHIRegionIndices(LRegion, PHI, PHIRegionIndices);
    2422             : 
    2423             :   assert(PHIRegionIndices.size() == 1);
    2424             : 
    2425           0 :   unsigned RegionIndex = PHIRegionIndices[0];
    2426             :   unsigned RegionSourceReg = getPHISourceReg(PHI, RegionIndex);
    2427             :   MachineBasicBlock *RegionSourceMBB = getPHIPred(PHI, RegionIndex);
    2428             :   unsigned PHIDest = getPHIDestReg(PHI);
    2429             :   unsigned PHISource = PHIDest;
    2430             :   unsigned ReplaceReg;
    2431             : 
    2432           0 :   if (shrinkPHI(PHI, PHIRegionIndices, &ReplaceReg)) {
    2433           0 :     PHISource = ReplaceReg;
    2434             :   }
    2435             : 
    2436           0 :   const TargetRegisterClass *RegClass = MRI->getRegClass(PHIDest);
    2437           0 :   unsigned NewDestReg = MRI->createVirtualRegister(RegClass);
    2438           0 :   LRegion->replaceRegisterInsideRegion(PHIDest, NewDestReg, false, MRI);
    2439             :   MachineInstrBuilder MIB =
    2440             :       BuildMI(*EntrySucc, EntrySucc->instr_begin(), PHI.getDebugLoc(),
    2441           0 :               TII->get(TargetOpcode::PHI), NewDestReg);
    2442             :   DEBUG(dbgs() << "Split Entry PHI " << printReg(NewDestReg, TRI) << " = PHI(");
    2443           0 :   MIB.addReg(PHISource);
    2444             :   MIB.addMBB(Entry);
    2445             :   DEBUG(dbgs() << printReg(PHISource, TRI) << ", "
    2446             :                << printMBBReference(*Entry));
    2447           0 :   MIB.addReg(RegionSourceReg);
    2448             :   MIB.addMBB(RegionSourceMBB);
    2449             :   DEBUG(dbgs() << " ," << printReg(RegionSourceReg, TRI) << ", "
    2450             :                << printMBBReference(*RegionSourceMBB) << ")\n");
    2451           0 : }
    2452             : 
    2453           0 : void AMDGPUMachineCFGStructurizer::splitLoopPHIs(MachineBasicBlock *Entry,
    2454             :                                            MachineBasicBlock *EntrySucc,
    2455             :                                            LinearizedRegion *LRegion) {
    2456             :   SmallVector<MachineInstr *, 2> PHIs;
    2457           0 :   collectPHIs(Entry, PHIs);
    2458             : 
    2459           0 :   for (auto PHII : PHIs) {
    2460           0 :     splitLoopPHI(*PHII, Entry, EntrySucc, LRegion);
    2461             :   }
    2462           0 : }
    2463             : 
    2464             : // Split the exit block so that we can insert a end control flow
    2465             : MachineBasicBlock *
    2466           0 : AMDGPUMachineCFGStructurizer::splitExit(LinearizedRegion *LRegion) {
    2467           0 :   auto MRTRegion = LRegion->getRegionMRT();
    2468           0 :   auto Exit = LRegion->getExit();
    2469           0 :   auto MF = Exit->getParent();
    2470           0 :   auto Succ = MRTRegion->getSucc();
    2471             : 
    2472           0 :   auto NewExit = MF->CreateMachineBasicBlock();
    2473           0 :   auto AfterExitIter = Exit->getIterator();
    2474             :   AfterExitIter++;
    2475             :   MF->insert(AfterExitIter, NewExit);
    2476           0 :   Exit->removeSuccessor(Succ);
    2477           0 :   Exit->addSuccessor(NewExit);
    2478           0 :   NewExit->addSuccessor(Succ);
    2479           0 :   insertUnconditionalBranch(NewExit, Succ);
    2480             :   LRegion->addMBB(NewExit);
    2481             :   LRegion->setExit(NewExit);
    2482             : 
    2483             :   DEBUG(dbgs() << "Created new exit block: " << NewExit->getNumber() << "\n");
    2484             : 
    2485             :   // Replace any PHI Predecessors in the successor with NewExit
    2486           0 :   for (auto &II : *Succ) {
    2487             :     MachineInstr &Instr = II;
    2488             : 
    2489             :     // If we are past the PHI instructions we are done
    2490             :     if (!Instr.isPHI())
    2491             :       break;
    2492             : 
    2493           0 :     int numPreds = getPHINumInputs(Instr);
    2494           0 :     for (int i = 0; i < numPreds; ++i) {
    2495           0 :       auto Pred = getPHIPred(Instr, i);
    2496           0 :       if (Pred == Exit) {
    2497             :         setPhiPred(Instr, i, NewExit);
    2498             :       }
    2499             :     }
    2500             :   }
    2501             : 
    2502           0 :   return NewExit;
    2503             : }
    2504             : 
    2505           0 : static MachineBasicBlock *split(MachineBasicBlock::iterator I) {
    2506             :   // Create the fall-through block.
    2507           0 :   MachineBasicBlock *MBB = (*I).getParent();
    2508           0 :   MachineFunction *MF = MBB->getParent();
    2509           0 :   MachineBasicBlock *SuccMBB = MF->CreateMachineBasicBlock();
    2510           0 :   auto MBBIter = ++(MBB->getIterator());
    2511             :   MF->insert(MBBIter, SuccMBB);
    2512           0 :   SuccMBB->transferSuccessorsAndUpdatePHIs(MBB);
    2513           0 :   MBB->addSuccessor(SuccMBB);
    2514             : 
    2515             :   // Splice the code over.
    2516             :   SuccMBB->splice(SuccMBB->end(), MBB, I, MBB->end());
    2517             : 
    2518           0 :   return SuccMBB;
    2519             : }
    2520             : 
    2521             : // Split the entry block separating PHI-nodes and the rest of the code
    2522             : // This is needed to insert an initializer for the bb select register
    2523             : // inloop regions.
    2524             : 
    2525             : MachineBasicBlock *
    2526           0 : AMDGPUMachineCFGStructurizer::splitEntry(LinearizedRegion *LRegion) {
    2527           0 :   MachineBasicBlock *Entry = LRegion->getEntry();
    2528           0 :   MachineBasicBlock *EntrySucc = split(Entry->getFirstNonPHI());
    2529           0 :   MachineBasicBlock *Exit = LRegion->getExit();
    2530             : 
    2531             :   DEBUG(dbgs() << "Split " << printMBBReference(*Entry) << " to "
    2532             :                << printMBBReference(*Entry) << " -> "
    2533             :                << printMBBReference(*EntrySucc) << "\n");
    2534             :   LRegion->addMBB(EntrySucc);
    2535             : 
    2536             :   // Make the backedge go to Entry Succ
    2537           0 :   if (Exit->isSuccessor(Entry)) {
    2538           0 :     Exit->removeSuccessor(Entry);
    2539             :   }
    2540           0 :   Exit->addSuccessor(EntrySucc);
    2541             :   MachineInstr &Branch = *(Exit->instr_rbegin());
    2542           0 :   for (auto &UI : Branch.uses()) {
    2543           0 :     if (UI.isMBB() && UI.getMBB() == Entry) {
    2544             :       UI.setMBB(EntrySucc);
    2545             :     }
    2546             :   }
    2547             : 
    2548           0 :   splitLoopPHIs(Entry, EntrySucc, LRegion);
    2549             : 
    2550           0 :   return EntrySucc;
    2551             : }
    2552             : 
    2553             : LinearizedRegion *
    2554           0 : AMDGPUMachineCFGStructurizer::initLinearizedRegion(RegionMRT *Region) {
    2555           0 :   LinearizedRegion *LRegion = Region->getLinearizedRegion();
    2556           0 :   LRegion->initLiveOut(Region, MRI, TRI, PHIInfo);
    2557           0 :   LRegion->setEntry(Region->getEntry());
    2558           0 :   return LRegion;
    2559             : }
    2560             : 
    2561           0 : static void removeOldExitPreds(RegionMRT *Region) {
    2562           0 :   MachineBasicBlock *Exit = Region->getSucc();
    2563           0 :   if (Exit == nullptr) {
    2564             :     return;
    2565             :   }
    2566             :   for (MachineBasicBlock::pred_iterator PI = Exit->pred_begin(),
    2567             :                                         E = Exit->pred_end();
    2568           0 :        PI != E; ++PI) {
    2569           0 :     if (Region->contains(*PI)) {
    2570           0 :       (*PI)->removeSuccessor(Exit);
    2571             :     }
    2572             :   }
    2573             : }
    2574             : 
    2575             : static bool mbbHasBackEdge(MachineBasicBlock *MBB,
    2576             :                            SmallPtrSet<MachineBasicBlock *, 8> &MBBs) {
    2577           0 :   for (auto SI = MBB->succ_begin(), SE = MBB->succ_end(); SI != SE; ++SI) {
    2578           0 :     if (MBBs.count(*SI) != 0) {
    2579             :       return true;
    2580             :     }
    2581             :   }
    2582             :   return false;
    2583             : }
    2584             : 
    2585           0 : static bool containsNewBackedge(MRT *Tree,
    2586             :                                 SmallPtrSet<MachineBasicBlock *, 8> &MBBs) {
    2587             :   // Need to traverse this in reverse since it is in post order.
    2588           0 :   if (Tree == nullptr)
    2589             :     return false;
    2590             : 
    2591           0 :   if (Tree->isMBB()) {
    2592           0 :     MachineBasicBlock *MBB = Tree->getMBBMRT()->getMBB();
    2593           0 :     MBBs.insert(MBB);
    2594           0 :     if (mbbHasBackEdge(MBB, MBBs)) {
    2595             :       return true;
    2596             :     }
    2597             :   } else {
    2598           0 :     RegionMRT *Region = Tree->getRegionMRT();
    2599             :     SetVector<MRT *> *Children = Region->getChildren();
    2600           0 :     for (auto CI = Children->rbegin(), CE = Children->rend(); CI != CE; ++CI) {
    2601           0 :       if (containsNewBackedge(*CI, MBBs))
    2602             :         return true;
    2603             :     }
    2604             :   }
    2605             :   return false;
    2606             : }
    2607             : 
    2608           0 : static bool containsNewBackedge(RegionMRT *Region) {
    2609             :   SmallPtrSet<MachineBasicBlock *, 8> MBBs;
    2610           0 :   return containsNewBackedge(Region, MBBs);
    2611             : }
    2612             : 
    2613           0 : bool AMDGPUMachineCFGStructurizer::structurizeComplexRegion(RegionMRT *Region) {
    2614           0 :   auto *LRegion = initLinearizedRegion(Region);
    2615           0 :   LRegion->setHasLoop(containsNewBackedge(Region));
    2616           0 :   MachineBasicBlock *LastMerge = createLinearizedExitBlock(Region);
    2617             :   MachineBasicBlock *CurrentMerge = LastMerge;
    2618             :   LRegion->addMBB(LastMerge);
    2619             :   LRegion->setExit(LastMerge);
    2620             : 
    2621           0 :   rewriteRegionExitPHIs(Region, LastMerge, LRegion);
    2622           0 :   removeOldExitPreds(Region);
    2623             : 
    2624             :   DEBUG(PHIInfo.dump(MRI));
    2625             : 
    2626             :   SetVector<MRT *> *Children = Region->getChildren();
    2627             :   DEBUG(dbgs() << "===========If Region Start===============\n");
    2628             :   if (LRegion->getHasLoop()) {
    2629             :     DEBUG(dbgs() << "Has Backedge: Yes\n");
    2630             :   } else {
    2631             :     DEBUG(dbgs() << "Has Backedge: No\n");
    2632             :   }
    2633             : 
    2634             :   unsigned BBSelectRegIn;
    2635             :   unsigned BBSelectRegOut;
    2636           0 :   for (auto CI = Children->begin(), CE = Children->end(); CI != CE; ++CI) {
    2637             :     DEBUG(dbgs() << "CurrentRegion: \n");
    2638             :     DEBUG(LRegion->print(dbgs(), TRI));
    2639             : 
    2640             :     auto CNI = CI;
    2641             :     ++CNI;
    2642             : 
    2643           0 :     MRT *Child = (*CI);
    2644             : 
    2645           0 :     if (Child->isRegion()) {
    2646             : 
    2647             :       LinearizedRegion *InnerLRegion =
    2648           0 :           Child->getRegionMRT()->getLinearizedRegion();
    2649             :       // We found the block is the exit of an inner region, we need
    2650             :       // to put it in the current linearized region.
    2651             : 
    2652             :       DEBUG(dbgs() << "Linearizing region: ");
    2653             :       DEBUG(InnerLRegion->print(dbgs(), TRI));
    2654             :       DEBUG(dbgs() << "\n");
    2655             : 
    2656           0 :       MachineBasicBlock *InnerEntry = InnerLRegion->getEntry();
    2657           0 :       if ((&(*(InnerEntry->getParent()->begin()))) == InnerEntry) {
    2658             :         // Entry has already been linearized, no need to do this region.
    2659             :         unsigned OuterSelect = InnerLRegion->getBBSelectRegOut();
    2660             :         unsigned InnerSelectReg =
    2661             :             InnerLRegion->getRegionMRT()->getInnerOutputRegister();
    2662           0 :         replaceRegisterWith(InnerSelectReg, OuterSelect),
    2663           0 :             resolvePHIInfos(InnerEntry);
    2664           0 :         if (!InnerLRegion->getExit()->isSuccessor(CurrentMerge))
    2665           0 :           InnerLRegion->getExit()->addSuccessor(CurrentMerge);
    2666           0 :         continue;
    2667             :       }
    2668             : 
    2669           0 :       BBSelectRegOut = Child->getBBSelectRegOut();
    2670           0 :       BBSelectRegIn = Child->getBBSelectRegIn();
    2671             : 
    2672             :       DEBUG(dbgs() << "BBSelectRegIn: " << printReg(BBSelectRegIn, TRI)
    2673             :                    << "\n");
    2674             :       DEBUG(dbgs() << "BBSelectRegOut: " << printReg(BBSelectRegOut, TRI)
    2675             :                    << "\n");
    2676             : 
    2677             :       MachineBasicBlock *IfEnd = CurrentMerge;
    2678           0 :       CurrentMerge = createIfRegion(CurrentMerge, InnerLRegion, LRegion,
    2679           0 :                                     Child->getRegionMRT()->getEntry(),
    2680             :                                     BBSelectRegIn, BBSelectRegOut);
    2681           0 :       TII->convertNonUniformIfRegion(CurrentMerge, IfEnd);
    2682             :     } else {
    2683           0 :       MachineBasicBlock *MBB = Child->getMBBMRT()->getMBB();
    2684             :       DEBUG(dbgs() << "Linearizing block: " << MBB->getNumber() << "\n");
    2685             : 
    2686           0 :       if (MBB == getSingleExitNode(*(MBB->getParent()))) {
    2687             :         // If this is the exit block then we need to skip to the next.
    2688             :         // The "in" register will be transferred to "out" in the next
    2689             :         // iteration.
    2690           0 :         continue;
    2691             :       }
    2692             : 
    2693           0 :       BBSelectRegOut = Child->getBBSelectRegOut();
    2694           0 :       BBSelectRegIn = Child->getBBSelectRegIn();
    2695             : 
    2696             :       DEBUG(dbgs() << "BBSelectRegIn: " << printReg(BBSelectRegIn, TRI)
    2697             :                    << "\n");
    2698             :       DEBUG(dbgs() << "BBSelectRegOut: " << printReg(BBSelectRegOut, TRI)
    2699             :                    << "\n");
    2700             : 
    2701             :       MachineBasicBlock *IfEnd = CurrentMerge;
    2702             :       // This is a basic block that is not part of an inner region, we
    2703             :       // need to put it in the current linearized region.
    2704           0 :       CurrentMerge = createIfRegion(CurrentMerge, MBB, LRegion, BBSelectRegIn,
    2705             :                                     BBSelectRegOut);
    2706           0 :       if (CurrentMerge) {
    2707           0 :         TII->convertNonUniformIfRegion(CurrentMerge, IfEnd);
    2708             :       }
    2709             : 
    2710             :       DEBUG(PHIInfo.dump(MRI));
    2711             :     }
    2712             :   }
    2713             : 
    2714           0 :   LRegion->removeFalseRegisterKills(MRI);
    2715             : 
    2716           0 :   if (LRegion->getHasLoop()) {
    2717           0 :     MachineBasicBlock *NewSucc = splitEntry(LRegion);
    2718           0 :     if (isFunctionEntryBlock(LRegion->getEntry())) {
    2719           0 :       resolvePHIInfos(LRegion->getEntry());
    2720             :     }
    2721           0 :     const DebugLoc &DL = NewSucc->findDebugLoc(NewSucc->getFirstNonPHI());
    2722             :     unsigned InReg = LRegion->getBBSelectRegIn();
    2723             :     unsigned InnerSelectReg =
    2724           0 :         MRI->createVirtualRegister(MRI->getRegClass(InReg));
    2725           0 :     unsigned NewInReg = MRI->createVirtualRegister(MRI->getRegClass(InReg));
    2726           0 :     TII->materializeImmediate(*(LRegion->getEntry()),
    2727             :                               LRegion->getEntry()->getFirstTerminator(), DL,
    2728           0 :                               NewInReg, Region->getEntry()->getNumber());
    2729             :     // Need to be careful about updating the registers inside the region.
    2730           0 :     LRegion->replaceRegisterInsideRegion(InReg, InnerSelectReg, false, MRI);
    2731             :     DEBUG(dbgs() << "Loop BBSelect Merge PHI:\n");
    2732           0 :     insertMergePHI(LRegion->getEntry(), LRegion->getExit(), NewSucc,
    2733             :                    InnerSelectReg, NewInReg,
    2734             :                    LRegion->getRegionMRT()->getInnerOutputRegister());
    2735           0 :     splitExit(LRegion);
    2736           0 :     TII->convertNonUniformLoopRegion(NewSucc, LastMerge);
    2737             :   }
    2738             : 
    2739           0 :   if (Region->isRoot()) {
    2740           0 :     TII->insertReturn(*LastMerge);
    2741             :   }
    2742             : 
    2743             :   DEBUG(Region->getEntry()->getParent()->dump());
    2744             :   DEBUG(LRegion->print(dbgs(), TRI));
    2745             :   DEBUG(PHIInfo.dump(MRI));
    2746             : 
    2747             :   DEBUG(dbgs() << "===========If Region End===============\n");
    2748             : 
    2749             :   Region->setLinearizedRegion(LRegion);
    2750           0 :   return true;
    2751             : }
    2752             : 
    2753           0 : bool AMDGPUMachineCFGStructurizer::structurizeRegion(RegionMRT *Region) {
    2754             :   if (false && regionIsSimpleIf(Region)) {
    2755             :     transformSimpleIfRegion(Region);
    2756             :     return true;
    2757           0 :   } else if (regionIsSequence(Region)) {
    2758           0 :     fixupRegionExits(Region);
    2759           0 :     return false;
    2760             :   } else {
    2761           0 :     structurizeComplexRegion(Region);
    2762             :   }
    2763           0 :   return false;
    2764             : }
    2765             : 
    2766             : static int structurize_once = 0;
    2767             : 
    2768           0 : bool AMDGPUMachineCFGStructurizer::structurizeRegions(RegionMRT *Region,
    2769             :                                                 bool isTopRegion) {
    2770             :   bool Changed = false;
    2771             : 
    2772             :   auto Children = Region->getChildren();
    2773           0 :   for (auto CI : *Children) {
    2774           0 :     if (CI->isRegion()) {
    2775           0 :       Changed |= structurizeRegions(CI->getRegionMRT(), false);
    2776             :     }
    2777             :   }
    2778             : 
    2779             :   if (structurize_once < 2 || true) {
    2780           0 :     Changed |= structurizeRegion(Region);
    2781           0 :     structurize_once++;
    2782             :   }
    2783           0 :   return Changed;
    2784             : }
    2785             : 
    2786           0 : void AMDGPUMachineCFGStructurizer::initFallthroughMap(MachineFunction &MF) {
    2787             :   DEBUG(dbgs() << "Fallthrough Map:\n");
    2788           0 :   for (auto &MBBI : MF) {
    2789           0 :     MachineBasicBlock *MBB = MBBI.getFallThrough();
    2790             :     if (MBB != nullptr) {
    2791             :       DEBUG(dbgs() << "Fallthrough: " << MBBI.getNumber() << " -> "
    2792             :                    << MBB->getNumber() << "\n");
    2793             :     }
    2794           0 :     FallthroughMap[&MBBI] = MBB;
    2795             :   }
    2796           0 : }
    2797             : 
    2798           0 : void AMDGPUMachineCFGStructurizer::createLinearizedRegion(RegionMRT *Region,
    2799             :                                                     unsigned SelectOut) {
    2800           0 :   LinearizedRegion *LRegion = new LinearizedRegion();
    2801           0 :   if (SelectOut) {
    2802             :     LRegion->addLiveOut(SelectOut);
    2803             :     DEBUG(dbgs() << "Add LiveOut (BBSelect): " << printReg(SelectOut, TRI)
    2804             :                  << "\n");
    2805             :   }
    2806             :   LRegion->setRegionMRT(Region);
    2807             :   Region->setLinearizedRegion(LRegion);
    2808           0 :   LRegion->setParent(Region->getParent()
    2809             :                          ? Region->getParent()->getLinearizedRegion()
    2810             :                          : nullptr);
    2811           0 : }
    2812             : 
    2813             : unsigned
    2814           0 : AMDGPUMachineCFGStructurizer::initializeSelectRegisters(MRT *MRT, unsigned SelectOut,
    2815             :                                                   MachineRegisterInfo *MRI,
    2816             :                                                   const SIInstrInfo *TII) {
    2817           0 :   if (MRT->isRegion()) {
    2818           0 :     RegionMRT *Region = MRT->getRegionMRT();
    2819             :     Region->setBBSelectRegOut(SelectOut);
    2820             :     unsigned InnerSelectOut = createBBSelectReg(TII, MRI);
    2821             : 
    2822             :     // Fixme: Move linearization creation to the original spot
    2823           0 :     createLinearizedRegion(Region, SelectOut);
    2824             : 
    2825             :     for (auto CI = Region->getChildren()->begin(),
    2826             :               CE = Region->getChildren()->end();
    2827           0 :          CI != CE; ++CI) {
    2828           0 :       InnerSelectOut =
    2829           0 :           initializeSelectRegisters((*CI), InnerSelectOut, MRI, TII);
    2830             :     }
    2831             :     MRT->setBBSelectRegIn(InnerSelectOut);
    2832           0 :     return InnerSelectOut;
    2833             :   } else {
    2834             :     MRT->setBBSelectRegOut(SelectOut);
    2835             :     unsigned NewSelectIn = createBBSelectReg(TII, MRI);
    2836             :     MRT->setBBSelectRegIn(NewSelectIn);
    2837           0 :     return NewSelectIn;
    2838             :   }
    2839             : }
    2840             : 
    2841             : static void checkRegOnlyPHIInputs(MachineFunction &MF) {
    2842           0 :   for (auto &MBBI : MF) {
    2843             :     for (MachineBasicBlock::instr_iterator I = MBBI.instr_begin(),
    2844             :                                            E = MBBI.instr_end();
    2845           0 :          I != E; ++I) {
    2846             :       MachineInstr &Instr = *I;
    2847             :       if (Instr.isPHI()) {
    2848             :         int numPreds = getPHINumInputs(Instr);
    2849             :         for (int i = 0; i < numPreds; ++i) {
    2850             :           assert(Instr.getOperand(i * 2 + 1).isReg() &&
    2851             :                  "PHI Operand not a register");
    2852             :         }
    2853             :       }
    2854             :     }
    2855             :   }
    2856             : }
    2857             : 
    2858           0 : bool AMDGPUMachineCFGStructurizer::runOnMachineFunction(MachineFunction &MF) {
    2859           0 :   const SISubtarget &ST = MF.getSubtarget<SISubtarget>();
    2860             :   const SIInstrInfo *TII = ST.getInstrInfo();
    2861           0 :   TRI = ST.getRegisterInfo();
    2862           0 :   MRI = &(MF.getRegInfo());
    2863           0 :   initFallthroughMap(MF);
    2864             : 
    2865             :   checkRegOnlyPHIInputs(MF);
    2866             :   DEBUG(dbgs() << "----STRUCTURIZER START----\n");
    2867             :   DEBUG(MF.dump());
    2868             : 
    2869           0 :   Regions = &(getAnalysis<MachineRegionInfoPass>().getRegionInfo());
    2870             :   DEBUG(Regions->dump());
    2871             : 
    2872           0 :   RegionMRT *RTree = MRT::buildMRT(MF, Regions, TII, MRI);
    2873             :   setRegionMRT(RTree);
    2874           0 :   initializeSelectRegisters(RTree, 0, MRI, TII);
    2875             :   DEBUG(RTree->dump(TRI));
    2876           0 :   bool result = structurizeRegions(RTree, true);
    2877           0 :   delete RTree;
    2878             :   DEBUG(dbgs() << "----STRUCTURIZER END----\n");
    2879           0 :   initFallthroughMap(MF);
    2880           0 :   return result;
    2881             : }
    2882             : 
    2883       81626 : char AMDGPUMachineCFGStructurizerID = AMDGPUMachineCFGStructurizer::ID;
    2884             : 
    2885           0 : INITIALIZE_PASS_BEGIN(AMDGPUMachineCFGStructurizer, "amdgpu-machine-cfg-structurizer",
    2886             :                       "AMDGPU Machine CFG Structurizer", false, false)
    2887           0 : INITIALIZE_PASS_DEPENDENCY(MachineRegionInfoPass)
    2888           0 : INITIALIZE_PASS_END(AMDGPUMachineCFGStructurizer, "amdgpu-machine-cfg-structurizer",
    2889             :                     "AMDGPU Machine CFG Structurizer", false, false)
    2890             : 
    2891           0 : FunctionPass *llvm::createAMDGPUMachineCFGStructurizerPass() {
    2892           0 :   return new AMDGPUMachineCFGStructurizer();
    2893      163252 : }

Generated by: LCOV version 1.13