LCOV - code coverage report
Current view: top level - lib/Target/AMDGPU - AMDGPUMachineCFGStructurizer.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 2 1124 0.2 %
Date: 2017-09-14 15:23:50 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/IR/DebugLoc.h"
      33             : #include "llvm/Pass.h"
      34             : #include "llvm/Support/Compiler.h"
      35             : #include "llvm/Support/Debug.h"
      36             : #include "llvm/Support/ErrorHandling.h"
      37             : #include "llvm/Support/raw_ostream.h"
      38             : #include "llvm/Target/TargetOpcodes.h"
      39             : #include "llvm/Target/TargetRegisterInfo.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           0 :     ++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           0 :     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           0 :   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           0 :   auto &Sources = phiInfoElementGetSources(Info);
     163           0 :   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           0 :     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           0 :   bool FoundSource = false;
     203           0 :   for (auto I : PHIInfo) {
     204           0 :     for (auto SI : phiInfoElementGetSources(I)) {
     205           0 :       if (SI.second == SourceMBB) {
     206           0 :         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           0 :   PHISourcesT EmptySet;
     217           0 :   PHIInfoElementT *NewElement = new PHIInfoElementT();
     218           0 :   NewElement->DestReg = DestReg;
     219           0 :   NewElement->DL = DL;
     220           0 :   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           0 :   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           0 :   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) << "(BB#"
     274             :              << SI.second->getNumber() << "),";
     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           0 :   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           0 :   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           0 :     setParent(nullptr);
     492           0 :     setBBSelectRegOut(0);
     493           0 :     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           0 :     setParent(nullptr);
     518           0 :     setBBSelectRegOut(0);
     519           0 :     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           0 :   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           0 :     MachineBasicBlock *ExitMBB = &MFI;
     627           0 :     if (ExitMBB->succ_size() == 0) {
     628           0 :       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           0 :   SmallPtrSet<MachineRegion *, 4> PlacedRegions;
     639           0 :   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           0 :   MachineBasicBlock *Exit = initializeMRT(MF, RegionInfo, RegionMap);
     647             : 
     648           0 :   unsigned BBSelectRegIn = createBBSelectReg(TII, MRI);
     649           0 :   MBBMRT *ExitMRT = new MBBMRT(Exit);
     650           0 :   RegionMap[RegionInfo->getRegionFor(Exit)]->addChild(ExitMRT);
     651           0 :   ExitMRT->setBBSelectRegIn(BBSelectRegIn);
     652             : 
     653           0 :   for (auto MBBI : post_order(&(MF.front()))) {
     654           0 :     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 BB#" << MBB->getNumber() << "\n");
     662           0 :     MBBMRT *NewMBB = new MBBMRT(MBB);
     663           0 :     MachineRegion *Region = RegionInfo->getRegionFor(MBB);
     664             : 
     665             :     // Ensure we have the MRT region
     666           0 :     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           0 :         NewMRTParent->addChild(NewMRTRegion);
     675           0 :         NewMRTRegion->setParent(NewMRTParent);
     676           0 :         RegionMap[Parent] = NewMRTParent;
     677           0 :         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           0 :     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 BB#" << MBB->getNumber()
     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           0 :           MachineInstr *UseInstr = UI.getParent();
     715             :           for (MachineBasicBlock::instr_iterator
     716           0 :                    MII = UseInstr->getIterator(),
     717           0 :                    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 (BB#" << MBB->getNumber() << ")-\n");
     753           0 :   for (auto &II : *MBB) {
     754           0 :     for (auto &RI : II.defs()) {
     755           0 :       storeLiveOutReg(MBB, RI.getReg(), RI.getParent(), MRI, TRI, PHIInfo);
     756             :     }
     757           0 :     for (auto &IRI : II.implicit_operands()) {
     758           0 :       if (IRI.isDef()) {
     759           0 :         storeLiveOutReg(MBB, IRI.getReg(), IRI.getParent(), MRI, TRI, PHIInfo);
     760             :       }
     761             :     }
     762             :   }
     763             : 
     764             :   // If we have a successor with a PHI, source coming from this MBB we have to
     765             :   // add the register as live out
     766           0 :   for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
     767           0 :                                         E = MBB->succ_end();
     768           0 :        SI != E; ++SI) {
     769           0 :     for (auto &II : *(*SI)) {
     770             :       if (II.isPHI()) {
     771           0 :         MachineInstr &PHI = II;
     772           0 :         int numPreds = getPHINumInputs(PHI);
     773           0 :         for (int i = 0; i < numPreds; ++i) {
     774           0 :           if (getPHIPred(PHI, i) == MBB) {
     775           0 :             unsigned PHIReg = getPHISourceReg(PHI, i);
     776             :             DEBUG(dbgs() << "Add LiveOut (PhiSource BB#" << MBB->getNumber()
     777             :                          << " -> BB#" << (*SI)->getNumber()
     778             :                          << "): " << PrintReg(PHIReg, TRI) << "\n");
     779             :             addLiveOut(PHIReg);
     780             :           }
     781             :         }
     782             :       }
     783             :     }
     784             :   }
     785             : 
     786             :   DEBUG(dbgs() << "-Store Live Outs Endn-\n");
     787           0 : }
     788             : 
     789           0 : void LinearizedRegion::storeMBBLiveOuts(MachineBasicBlock *MBB,
     790             :                                         const MachineRegisterInfo *MRI,
     791             :                                         const TargetRegisterInfo *TRI,
     792             :                                         PHILinearize &PHIInfo,
     793             :                                         RegionMRT *TopRegion) {
     794           0 :   for (auto &II : *MBB) {
     795           0 :     for (auto &RI : II.defs()) {
     796           0 :       storeLiveOutRegRegion(TopRegion, RI.getReg(), RI.getParent(), MRI, TRI,
     797             :                             PHIInfo);
     798             :     }
     799           0 :     for (auto &IRI : II.implicit_operands()) {
     800           0 :       if (IRI.isDef()) {
     801           0 :         storeLiveOutRegRegion(TopRegion, IRI.getReg(), IRI.getParent(), MRI,
     802             :                               TRI, PHIInfo);
     803             :       }
     804             :     }
     805             :   }
     806           0 : }
     807             : 
     808           0 : void LinearizedRegion::storeLiveOuts(RegionMRT *Region,
     809             :                                      const MachineRegisterInfo *MRI,
     810             :                                      const TargetRegisterInfo *TRI,
     811             :                                      PHILinearize &PHIInfo,
     812             :                                      RegionMRT *CurrentTopRegion) {
     813           0 :   MachineBasicBlock *Exit = Region->getSucc();
     814             : 
     815           0 :   RegionMRT *TopRegion =
     816           0 :       CurrentTopRegion == nullptr ? Region : CurrentTopRegion;
     817             : 
     818             :   // Check if exit is end of function, if so, no live outs.
     819           0 :   if (Exit == nullptr)
     820             :     return;
     821             : 
     822           0 :   auto Children = Region->getChildren();
     823           0 :   for (auto CI : *Children) {
     824           0 :     if (CI->isMBB()) {
     825           0 :       auto MBB = CI->getMBBMRT()->getMBB();
     826           0 :       storeMBBLiveOuts(MBB, MRI, TRI, PHIInfo, TopRegion);
     827             :     } else {
     828           0 :       LinearizedRegion *SubRegion = CI->getRegionMRT()->getLinearizedRegion();
     829             :       // We should be limited to only store registers that are live out from the
     830             :       // lineaized region
     831           0 :       for (auto MBBI : SubRegion->MBBs) {
     832           0 :         storeMBBLiveOuts(MBBI, MRI, TRI, PHIInfo, TopRegion);
     833             :       }
     834             :     }
     835             :   }
     836             : 
     837           0 :   if (CurrentTopRegion == nullptr) {
     838           0 :     auto Succ = Region->getSucc();
     839           0 :     for (auto &II : *Succ) {
     840             :       if (II.isPHI()) {
     841           0 :         MachineInstr &PHI = II;
     842           0 :         int numPreds = getPHINumInputs(PHI);
     843           0 :         for (int i = 0; i < numPreds; ++i) {
     844           0 :           if (Region->contains(getPHIPred(PHI, i))) {
     845           0 :             unsigned PHIReg = getPHISourceReg(PHI, i);
     846             :             DEBUG(dbgs() << "Add Region LiveOut (" << (void *)Region
     847             :                          << "): " << PrintReg(PHIReg, TRI) << "\n");
     848             :             addLiveOut(PHIReg);
     849             :           }
     850             :         }
     851             :       }
     852             :     }
     853             :   }
     854             : }
     855             : 
     856             : #ifndef NDEBUG
     857             : void LinearizedRegion::print(raw_ostream &OS, const TargetRegisterInfo *TRI) {
     858             :   OS << "Linearized Region {";
     859             :   bool IsFirst = true;
     860             :   for (const auto &MBB : MBBs) {
     861             :     if (IsFirst) {
     862             :       IsFirst = false;
     863             :     } else {
     864             :       OS << " ,";
     865             :     }
     866             :     OS << MBB->getNumber();
     867             :   }
     868             :   OS << "} (" << Entry->getNumber() << ", "
     869             :      << (Exit == nullptr ? -1 : Exit->getNumber())
     870             :      << "): In:" << PrintReg(getBBSelectRegIn(), TRI)
     871             :      << " Out:" << PrintReg(getBBSelectRegOut(), TRI) << " {";
     872             :   for (auto &LI : LiveOuts) {
     873             :     OS << PrintReg(LI, TRI) << " ";
     874             :   }
     875             :   OS << "} \n";
     876             : }
     877             : #endif
     878             : 
     879             : unsigned LinearizedRegion::getBBSelectRegIn() {
     880           0 :   return getRegionMRT()->getBBSelectRegIn();
     881             : }
     882             : 
     883             : unsigned LinearizedRegion::getBBSelectRegOut() {
     884           0 :   return getRegionMRT()->getBBSelectRegOut();
     885             : }
     886             : 
     887           0 : void LinearizedRegion::setHasLoop(bool Value) { HasLoop = Value; }
     888             : 
     889             : bool LinearizedRegion::getHasLoop() { return HasLoop; }
     890             : 
     891           0 : void LinearizedRegion::addLiveOut(unsigned VReg) { LiveOuts.insert(VReg); }
     892             : 
     893           0 : void LinearizedRegion::removeLiveOut(unsigned Reg) {
     894           0 :   if (isLiveOut(Reg))
     895           0 :     LiveOuts.erase(Reg);
     896           0 : }
     897             : 
     898           0 : void LinearizedRegion::replaceLiveOut(unsigned OldReg, unsigned NewReg) {
     899           0 :   if (isLiveOut(OldReg)) {
     900           0 :     removeLiveOut(OldReg);
     901             :     addLiveOut(NewReg);
     902             :   }
     903           0 : }
     904             : 
     905           0 : void LinearizedRegion::replaceRegister(unsigned Register, unsigned NewRegister,
     906             :                                        MachineRegisterInfo *MRI,
     907             :                                        bool ReplaceInside, bool ReplaceOutside,
     908             :                                        bool IncludeLoopPHI) {
     909             :   assert(Register != NewRegister && "Cannot replace a reg with itself");
     910             : 
     911             :   DEBUG(dbgs() << "Pepareing to replace register (region): "
     912             :                << PrintReg(Register, MRI->getTargetRegisterInfo()) << " with "
     913             :                << PrintReg(NewRegister, MRI->getTargetRegisterInfo()) << "\n");
     914             : 
     915             :   // If we are replacing outside, we also need to update the LiveOuts
     916           0 :   if (ReplaceOutside &&
     917           0 :       (isLiveOut(Register) || this->getParent()->isLiveOut(Register))) {
     918             :     LinearizedRegion *Current = this;
     919           0 :     while (Current != nullptr && Current->getEntry() != nullptr) {
     920             :       DEBUG(dbgs() << "Region before register replace\n");
     921             :       DEBUG(Current->print(dbgs(), MRI->getTargetRegisterInfo()));
     922           0 :       Current->replaceLiveOut(Register, NewRegister);
     923             :       DEBUG(dbgs() << "Region after register replace\n");
     924             :       DEBUG(Current->print(dbgs(), MRI->getTargetRegisterInfo()));
     925           0 :       Current = Current->getParent();
     926             :     }
     927             :   }
     928             : 
     929             :   for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Register),
     930             :                                          E = MRI->reg_end();
     931           0 :        I != E;) {
     932           0 :     MachineOperand &O = *I;
     933           0 :     ++I;
     934             : 
     935             :     // We don't rewrite defs.
     936           0 :     if (O.isDef())
     937           0 :       continue;
     938             : 
     939           0 :     bool IsInside = contains(O.getParent()->getParent());
     940           0 :     bool IsLoopPHI = IsInside && (O.getParent()->isPHI() &&
     941           0 :                                   O.getParent()->getParent() == getEntry());
     942           0 :     bool ShouldReplace = (IsInside && ReplaceInside) ||
     943           0 :                          (!IsInside && ReplaceOutside) ||
     944           0 :                          (IncludeLoopPHI && IsLoopPHI);
     945             :     if (ShouldReplace) {
     946             : 
     947           0 :       if (TargetRegisterInfo::isPhysicalRegister(NewRegister)) {
     948             :         DEBUG(dbgs() << "Trying to substitute physical register: "
     949             :                      << PrintReg(NewRegister, MRI->getTargetRegisterInfo())
     950             :                      << "\n");
     951           0 :         llvm_unreachable("Cannot substitute physical registers");
     952             :       } else {
     953             :         DEBUG(dbgs() << "Replacing register (region): "
     954             :                      << PrintReg(Register, MRI->getTargetRegisterInfo())
     955             :                      << " with "
     956             :                      << PrintReg(NewRegister, MRI->getTargetRegisterInfo())
     957             :                      << "\n");
     958           0 :         O.setReg(NewRegister);
     959             :       }
     960             :     }
     961             :   }
     962           0 : }
     963             : 
     964             : void LinearizedRegion::replaceRegisterInsideRegion(unsigned Register,
     965             :                                                    unsigned NewRegister,
     966             :                                                    bool IncludeLoopPHIs,
     967             :                                                    MachineRegisterInfo *MRI) {
     968           0 :   replaceRegister(Register, NewRegister, MRI, true, false, IncludeLoopPHIs);
     969             : }
     970             : 
     971             : void LinearizedRegion::replaceRegisterOutsideRegion(unsigned Register,
     972             :                                                     unsigned NewRegister,
     973             :                                                     bool IncludeLoopPHIs,
     974             :                                                     MachineRegisterInfo *MRI) {
     975           0 :   replaceRegister(Register, NewRegister, MRI, false, true, IncludeLoopPHIs);
     976             : }
     977             : 
     978           0 : DenseSet<unsigned> *LinearizedRegion::getLiveOuts() { return &LiveOuts; }
     979             : 
     980             : void LinearizedRegion::setEntry(MachineBasicBlock *NewEntry) {
     981           0 :   Entry = NewEntry;
     982             : }
     983             : 
     984             : MachineBasicBlock *LinearizedRegion::getEntry() { return Entry; }
     985             : 
     986           0 : void LinearizedRegion::setExit(MachineBasicBlock *NewExit) { Exit = NewExit; }
     987             : 
     988             : MachineBasicBlock *LinearizedRegion::getExit() { return Exit; }
     989             : 
     990           0 : void LinearizedRegion::addMBB(MachineBasicBlock *MBB) { MBBs.insert(MBB); }
     991             : 
     992           0 : void LinearizedRegion::addMBBs(LinearizedRegion *InnerRegion) {
     993           0 :   for (const auto &MBB : InnerRegion->MBBs) {
     994           0 :     addMBB(MBB);
     995             :   }
     996           0 : }
     997             : 
     998             : bool LinearizedRegion::contains(MachineBasicBlock *MBB) {
     999           0 :   return MBBs.count(MBB) == 1;
    1000             : }
    1001             : 
    1002             : bool LinearizedRegion::isLiveOut(unsigned Reg) {
    1003           0 :   return LiveOuts.count(Reg) == 1;
    1004             : }
    1005             : 
    1006             : bool LinearizedRegion::hasNoDef(unsigned Reg, MachineRegisterInfo *MRI) {
    1007           0 :   return MRI->def_begin(Reg) == MRI->def_end();
    1008             : }
    1009             : 
    1010             : // After the code has been structurized, what was flagged as kills
    1011             : // before are no longer register kills.
    1012           0 : void LinearizedRegion::removeFalseRegisterKills(MachineRegisterInfo *MRI) {
    1013           0 :   const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
    1014           0 :   for (auto MBBI : MBBs) {
    1015           0 :     MachineBasicBlock *MBB = MBBI;
    1016           0 :     for (auto &II : *MBB) {
    1017           0 :       for (auto &RI : II.uses()) {
    1018           0 :         if (RI.isReg()) {
    1019           0 :           unsigned Reg = RI.getReg();
    1020           0 :           if (TRI->isVirtualRegister(Reg)) {
    1021           0 :             if (hasNoDef(Reg, MRI))
    1022           0 :               continue;
    1023           0 :             if (!MRI->hasOneDef(Reg)) {
    1024             :               DEBUG(this->getEntry()->getParent()->dump());
    1025             :               DEBUG(dbgs() << PrintReg(Reg, TRI) << "\n");
    1026             :             }
    1027             : 
    1028           0 :             if (MRI->def_begin(Reg) == MRI->def_end()) {
    1029             :               DEBUG(dbgs() << "Register "
    1030             :                            << PrintReg(Reg, MRI->getTargetRegisterInfo())
    1031             :                            << " has NO defs\n");
    1032           0 :             } else if (!MRI->hasOneDef(Reg)) {
    1033             :               DEBUG(dbgs() << "Register "
    1034             :                            << PrintReg(Reg, MRI->getTargetRegisterInfo())
    1035             :                            << " has multiple defs\n");
    1036             :             }
    1037             : 
    1038             :             assert(MRI->hasOneDef(Reg) && "Register has multiple definitions");
    1039           0 :             MachineOperand *Def = &(*(MRI->def_begin(Reg)));
    1040           0 :             MachineOperand *UseOperand = &(RI);
    1041           0 :             bool UseIsOutsideDefMBB = Def->getParent()->getParent() != MBB;
    1042           0 :             if (UseIsOutsideDefMBB && UseOperand->isKill()) {
    1043             :               DEBUG(dbgs() << "Removing kill flag on register: "
    1044             :                            << PrintReg(Reg, TRI) << "\n");
    1045             :               UseOperand->setIsKill(false);
    1046             :             }
    1047             :           }
    1048             :         }
    1049             :       }
    1050             :     }
    1051             :   }
    1052           0 : }
    1053             : 
    1054             : void LinearizedRegion::initLiveOut(RegionMRT *Region,
    1055             :                                    const MachineRegisterInfo *MRI,
    1056             :                                    const TargetRegisterInfo *TRI,
    1057             :                                    PHILinearize &PHIInfo) {
    1058           0 :   storeLiveOuts(Region, MRI, TRI, PHIInfo);
    1059             : }
    1060             : 
    1061           0 : LinearizedRegion::LinearizedRegion(MachineBasicBlock *MBB,
    1062             :                                    const MachineRegisterInfo *MRI,
    1063             :                                    const TargetRegisterInfo *TRI,
    1064           0 :                                    PHILinearize &PHIInfo) {
    1065           0 :   setEntry(MBB);
    1066           0 :   setExit(MBB);
    1067           0 :   storeLiveOuts(MBB, MRI, TRI, PHIInfo);
    1068           0 :   MBBs.insert(MBB);
    1069           0 :   Parent = nullptr;
    1070           0 : }
    1071             : 
    1072           0 : LinearizedRegion::LinearizedRegion() {
    1073           0 :   setEntry(nullptr);
    1074           0 :   setExit(nullptr);
    1075           0 :   Parent = nullptr;
    1076             : }
    1077             : 
    1078             : namespace {
    1079             : 
    1080           0 : class AMDGPUMachineCFGStructurizer : public MachineFunctionPass {
    1081             : private:
    1082             :   const MachineRegionInfo *Regions;
    1083             :   const SIInstrInfo *TII;
    1084             :   const TargetRegisterInfo *TRI;
    1085             :   MachineRegisterInfo *MRI;
    1086             :   unsigned BBSelectRegister;
    1087             :   PHILinearize PHIInfo;
    1088             :   DenseMap<MachineBasicBlock *, MachineBasicBlock *> FallthroughMap;
    1089             :   RegionMRT *RMRT;
    1090             : 
    1091             :   void getPHIRegionIndices(RegionMRT *Region, MachineInstr &PHI,
    1092             :                            SmallVector<unsigned, 2> &RegionIndices);
    1093             :   void getPHIRegionIndices(LinearizedRegion *Region, MachineInstr &PHI,
    1094             :                            SmallVector<unsigned, 2> &RegionIndices);
    1095             :   void getPHINonRegionIndices(LinearizedRegion *Region, MachineInstr &PHI,
    1096             :                               SmallVector<unsigned, 2> &PHINonRegionIndices);
    1097             : 
    1098             :   void storePHILinearizationInfoDest(
    1099             :       unsigned LDestReg, MachineInstr &PHI,
    1100             :       SmallVector<unsigned, 2> *RegionIndices = nullptr);
    1101             : 
    1102             :   unsigned storePHILinearizationInfo(MachineInstr &PHI,
    1103             :                                      SmallVector<unsigned, 2> *RegionIndices);
    1104             : 
    1105             :   void extractKilledPHIs(MachineBasicBlock *MBB);
    1106             : 
    1107             :   bool shrinkPHI(MachineInstr &PHI, SmallVector<unsigned, 2> &PHIIndices,
    1108             :                  unsigned *ReplaceReg);
    1109             : 
    1110             :   bool shrinkPHI(MachineInstr &PHI, unsigned CombinedSourceReg,
    1111             :                  MachineBasicBlock *SourceMBB,
    1112             :                  SmallVector<unsigned, 2> &PHIIndices, unsigned *ReplaceReg);
    1113             : 
    1114             :   void replacePHI(MachineInstr &PHI, unsigned CombinedSourceReg,
    1115             :                   MachineBasicBlock *LastMerge,
    1116             :                   SmallVector<unsigned, 2> &PHIRegionIndices);
    1117             :   void replaceEntryPHI(MachineInstr &PHI, unsigned CombinedSourceReg,
    1118             :                        MachineBasicBlock *IfMBB,
    1119             :                        SmallVector<unsigned, 2> &PHIRegionIndices);
    1120             :   void replaceLiveOutRegs(MachineInstr &PHI,
    1121             :                           SmallVector<unsigned, 2> &PHIRegionIndices,
    1122             :                           unsigned CombinedSourceReg,
    1123             :                           LinearizedRegion *LRegion);
    1124             :   void rewriteRegionExitPHI(RegionMRT *Region, MachineBasicBlock *LastMerge,
    1125             :                             MachineInstr &PHI, LinearizedRegion *LRegion);
    1126             : 
    1127             :   void rewriteRegionExitPHIs(RegionMRT *Region, MachineBasicBlock *LastMerge,
    1128             :                              LinearizedRegion *LRegion);
    1129             :   void rewriteRegionEntryPHI(LinearizedRegion *Region, MachineBasicBlock *IfMBB,
    1130             :                              MachineInstr &PHI);
    1131             :   void rewriteRegionEntryPHIs(LinearizedRegion *Region,
    1132             :                               MachineBasicBlock *IfMBB);
    1133             : 
    1134             :   bool regionIsSimpleIf(RegionMRT *Region);
    1135             : 
    1136             :   void transformSimpleIfRegion(RegionMRT *Region);
    1137             : 
    1138             :   void eliminateDeadBranchOperands(MachineBasicBlock::instr_iterator &II);
    1139             : 
    1140             :   void insertUnconditionalBranch(MachineBasicBlock *MBB,
    1141             :                                  MachineBasicBlock *Dest,
    1142             :                                  const DebugLoc &DL = DebugLoc());
    1143             : 
    1144             :   MachineBasicBlock *createLinearizedExitBlock(RegionMRT *Region);
    1145             : 
    1146             :   void insertMergePHI(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB,
    1147             :                       MachineBasicBlock *MergeBB, unsigned DestRegister,
    1148             :                       unsigned IfSourceRegister, unsigned CodeSourceRegister,
    1149             :                       bool IsUndefIfSource = false);
    1150             : 
    1151             :   MachineBasicBlock *createIfBlock(MachineBasicBlock *MergeBB,
    1152             :                                    MachineBasicBlock *CodeBBStart,
    1153             :                                    MachineBasicBlock *CodeBBEnd,
    1154             :                                    MachineBasicBlock *SelectBB, unsigned IfReg,
    1155             :                                    bool InheritPreds);
    1156             : 
    1157             :   void prunePHIInfo(MachineBasicBlock *MBB);
    1158             :   void createEntryPHI(LinearizedRegion *CurrentRegion, unsigned DestReg);
    1159             : 
    1160             :   void createEntryPHIs(LinearizedRegion *CurrentRegion);
    1161             :   void resolvePHIInfos(MachineBasicBlock *FunctionEntry);
    1162             : 
    1163             :   void replaceRegisterWith(unsigned Register, unsigned NewRegister);
    1164             : 
    1165             :   MachineBasicBlock *createIfRegion(MachineBasicBlock *MergeBB,
    1166             :                                     MachineBasicBlock *CodeBB,
    1167             :                                     LinearizedRegion *LRegion,
    1168             :                                     unsigned BBSelectRegIn,
    1169             :                                     unsigned BBSelectRegOut);
    1170             : 
    1171             :   MachineBasicBlock *
    1172             :   createIfRegion(MachineBasicBlock *MergeMBB, LinearizedRegion *InnerRegion,
    1173             :                  LinearizedRegion *CurrentRegion, MachineBasicBlock *SelectBB,
    1174             :                  unsigned BBSelectRegIn, unsigned BBSelectRegOut);
    1175             :   void ensureCondIsNotKilled(SmallVector<MachineOperand, 1> Cond);
    1176             : 
    1177             :   void rewriteCodeBBTerminator(MachineBasicBlock *CodeBB,
    1178             :                                MachineBasicBlock *MergeBB,
    1179             :                                unsigned BBSelectReg);
    1180             : 
    1181             :   MachineInstr *getDefInstr(unsigned Reg);
    1182             :   void insertChainedPHI(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB,
    1183             :                         MachineBasicBlock *MergeBB,
    1184             :                         LinearizedRegion *InnerRegion, unsigned DestReg,
    1185             :                         unsigned SourceReg);
    1186             :   bool containsDef(MachineBasicBlock *MBB, LinearizedRegion *InnerRegion,
    1187             :                    unsigned Register);
    1188             :   void rewriteLiveOutRegs(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB,
    1189             :                           MachineBasicBlock *MergeBB,
    1190             :                           LinearizedRegion *InnerRegion,
    1191             :                           LinearizedRegion *LRegion);
    1192             : 
    1193             :   void splitLoopPHI(MachineInstr &PHI, MachineBasicBlock *Entry,
    1194             :                     MachineBasicBlock *EntrySucc, LinearizedRegion *LRegion);
    1195             :   void splitLoopPHIs(MachineBasicBlock *Entry, MachineBasicBlock *EntrySucc,
    1196             :                      LinearizedRegion *LRegion);
    1197             : 
    1198             :   MachineBasicBlock *splitExit(LinearizedRegion *LRegion);
    1199             : 
    1200             :   MachineBasicBlock *splitEntry(LinearizedRegion *LRegion);
    1201             : 
    1202             :   LinearizedRegion *initLinearizedRegion(RegionMRT *Region);
    1203             : 
    1204             :   bool structurizeComplexRegion(RegionMRT *Region);
    1205             : 
    1206             :   bool structurizeRegion(RegionMRT *Region);
    1207             : 
    1208             :   bool structurizeRegions(RegionMRT *Region, bool isTopRegion);
    1209             : 
    1210             : public:
    1211             :   static char ID;
    1212             : 
    1213           0 :   AMDGPUMachineCFGStructurizer() : MachineFunctionPass(ID) {
    1214           0 :     initializeAMDGPUMachineCFGStructurizerPass(*PassRegistry::getPassRegistry());
    1215           0 :   }
    1216             : 
    1217           0 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
    1218           0 :     AU.addRequired<MachineRegionInfoPass>();
    1219           0 :     MachineFunctionPass::getAnalysisUsage(AU);
    1220           0 :   }
    1221             : 
    1222             :   void initFallthroughMap(MachineFunction &MF);
    1223             : 
    1224             :   void createLinearizedRegion(RegionMRT *Region, unsigned SelectOut);
    1225             : 
    1226             :   unsigned initializeSelectRegisters(MRT *MRT, unsigned ExistingExitReg,
    1227             :                                      MachineRegisterInfo *MRI,
    1228             :                                      const SIInstrInfo *TII);
    1229             : 
    1230           0 :   void setRegionMRT(RegionMRT *RegionTree) { RMRT = RegionTree; }
    1231             : 
    1232             :   RegionMRT *getRegionMRT() { return RMRT; }
    1233             : 
    1234             :   bool runOnMachineFunction(MachineFunction &MF) override;
    1235             : };
    1236             : 
    1237             : } // end anonymous namespace
    1238             : 
    1239             : char AMDGPUMachineCFGStructurizer::ID = 0;
    1240             : 
    1241             : bool AMDGPUMachineCFGStructurizer::regionIsSimpleIf(RegionMRT *Region) {
    1242             :   MachineBasicBlock *Entry = Region->getEntry();
    1243             :   MachineBasicBlock *Succ = Region->getSucc();
    1244             :   bool FoundBypass = false;
    1245             :   bool FoundIf = false;
    1246             : 
    1247             :   if (Entry->succ_size() != 2) {
    1248             :     return false;
    1249             :   }
    1250             : 
    1251             :   for (MachineBasicBlock::const_succ_iterator SI = Entry->succ_begin(),
    1252             :                                               E = Entry->succ_end();
    1253             :        SI != E; ++SI) {
    1254             :     MachineBasicBlock *Current = *SI;
    1255             : 
    1256             :     if (Current == Succ) {
    1257             :       FoundBypass = true;
    1258             :     } else if ((Current->succ_size() == 1) &&
    1259             :                *(Current->succ_begin()) == Succ) {
    1260             :       FoundIf = true;
    1261             :     }
    1262             :   }
    1263             : 
    1264             :   return FoundIf && FoundBypass;
    1265             : }
    1266             : 
    1267             : void AMDGPUMachineCFGStructurizer::transformSimpleIfRegion(RegionMRT *Region) {
    1268             :   MachineBasicBlock *Entry = Region->getEntry();
    1269             :   MachineBasicBlock *Exit = Region->getExit();
    1270             :   TII->convertNonUniformIfRegion(Entry, Exit);
    1271             : }
    1272             : 
    1273           0 : static void fixMBBTerminator(MachineBasicBlock *MBB) {
    1274           0 :   if (MBB->succ_size() == 1) {
    1275           0 :     auto *Succ = *(MBB->succ_begin());
    1276           0 :     for (auto &TI : MBB->terminators()) {
    1277           0 :       for (auto &UI : TI.uses()) {
    1278           0 :         if (UI.isMBB() && UI.getMBB() != Succ) {
    1279           0 :           UI.setMBB(Succ);
    1280             :         }
    1281             :       }
    1282             :     }
    1283             :   }
    1284           0 : }
    1285             : 
    1286           0 : static void fixRegionTerminator(RegionMRT *Region) {
    1287           0 :   MachineBasicBlock *InternalSucc = nullptr;
    1288           0 :   MachineBasicBlock *ExternalSucc = nullptr;
    1289           0 :   LinearizedRegion *LRegion = Region->getLinearizedRegion();
    1290           0 :   auto Exit = LRegion->getExit();
    1291             : 
    1292           0 :   SmallPtrSet<MachineBasicBlock *, 2> Successors;
    1293           0 :   for (MachineBasicBlock::const_succ_iterator SI = Exit->succ_begin(),
    1294           0 :                                               SE = Exit->succ_end();
    1295           0 :        SI != SE; ++SI) {
    1296           0 :     MachineBasicBlock *Succ = *SI;
    1297           0 :     if (LRegion->contains(Succ)) {
    1298             :       // Do not allow re-assign
    1299             :       assert(InternalSucc == nullptr);
    1300             :       InternalSucc = Succ;
    1301             :     } else {
    1302             :       // Do not allow re-assign
    1303             :       assert(ExternalSucc == nullptr);
    1304           0 :       ExternalSucc = Succ;
    1305             :     }
    1306             :   }
    1307             : 
    1308           0 :   for (auto &TI : Exit->terminators()) {
    1309           0 :     for (auto &UI : TI.uses()) {
    1310           0 :       if (UI.isMBB()) {
    1311           0 :         auto Target = UI.getMBB();
    1312           0 :         if (Target != InternalSucc && Target != ExternalSucc) {
    1313           0 :           UI.setMBB(ExternalSucc);
    1314             :         }
    1315             :       }
    1316             :     }
    1317             :   }
    1318           0 : }
    1319             : 
    1320             : // If a region region is just a sequence of regions (and the exit
    1321             : // block in the case of the top level region), we can simply skip
    1322             : // linearizing it, because it is already linear
    1323           0 : bool regionIsSequence(RegionMRT *Region) {
    1324           0 :   auto Children = Region->getChildren();
    1325           0 :   for (auto CI : *Children) {
    1326           0 :     if (!CI->isRegion()) {
    1327           0 :       if (CI->getMBBMRT()->getMBB()->succ_size() > 1) {
    1328             :         return false;
    1329             :       }
    1330             :     }
    1331             :   }
    1332             :   return true;
    1333             : }
    1334             : 
    1335           0 : void fixupRegionExits(RegionMRT *Region) {
    1336           0 :   auto Children = Region->getChildren();
    1337           0 :   for (auto CI : *Children) {
    1338           0 :     if (!CI->isRegion()) {
    1339           0 :       fixMBBTerminator(CI->getMBBMRT()->getMBB());
    1340             :     } else {
    1341           0 :       fixRegionTerminator(CI->getRegionMRT());
    1342             :     }
    1343             :   }
    1344           0 : }
    1345             : 
    1346           0 : void AMDGPUMachineCFGStructurizer::getPHIRegionIndices(
    1347             :     RegionMRT *Region, MachineInstr &PHI,
    1348             :     SmallVector<unsigned, 2> &PHIRegionIndices) {
    1349           0 :   unsigned NumInputs = getPHINumInputs(PHI);
    1350           0 :   for (unsigned i = 0; i < NumInputs; ++i) {
    1351           0 :     MachineBasicBlock *Pred = getPHIPred(PHI, i);
    1352           0 :     if (Region->contains(Pred)) {
    1353           0 :       PHIRegionIndices.push_back(i);
    1354             :     }
    1355             :   }
    1356           0 : }
    1357             : 
    1358           0 : void AMDGPUMachineCFGStructurizer::getPHIRegionIndices(
    1359             :     LinearizedRegion *Region, MachineInstr &PHI,
    1360             :     SmallVector<unsigned, 2> &PHIRegionIndices) {
    1361           0 :   unsigned NumInputs = getPHINumInputs(PHI);
    1362           0 :   for (unsigned i = 0; i < NumInputs; ++i) {
    1363           0 :     MachineBasicBlock *Pred = getPHIPred(PHI, i);
    1364           0 :     if (Region->contains(Pred)) {
    1365           0 :       PHIRegionIndices.push_back(i);
    1366             :     }
    1367             :   }
    1368           0 : }
    1369             : 
    1370           0 : void AMDGPUMachineCFGStructurizer::getPHINonRegionIndices(
    1371             :     LinearizedRegion *Region, MachineInstr &PHI,
    1372             :     SmallVector<unsigned, 2> &PHINonRegionIndices) {
    1373           0 :   unsigned NumInputs = getPHINumInputs(PHI);
    1374           0 :   for (unsigned i = 0; i < NumInputs; ++i) {
    1375           0 :     MachineBasicBlock *Pred = getPHIPred(PHI, i);
    1376           0 :     if (!Region->contains(Pred)) {
    1377           0 :       PHINonRegionIndices.push_back(i);
    1378             :     }
    1379             :   }
    1380           0 : }
    1381             : 
    1382           0 : void AMDGPUMachineCFGStructurizer::storePHILinearizationInfoDest(
    1383             :     unsigned LDestReg, MachineInstr &PHI,
    1384             :     SmallVector<unsigned, 2> *RegionIndices) {
    1385           0 :   if (RegionIndices) {
    1386           0 :     for (auto i : *RegionIndices) {
    1387           0 :       PHIInfo.addSource(LDestReg, getPHISourceReg(PHI, i), getPHIPred(PHI, i));
    1388             :     }
    1389             :   } else {
    1390           0 :     unsigned NumInputs = getPHINumInputs(PHI);
    1391           0 :     for (unsigned i = 0; i < NumInputs; ++i) {
    1392           0 :       PHIInfo.addSource(LDestReg, getPHISourceReg(PHI, i), getPHIPred(PHI, i));
    1393             :     }
    1394             :   }
    1395           0 : }
    1396             : 
    1397           0 : unsigned AMDGPUMachineCFGStructurizer::storePHILinearizationInfo(
    1398             :     MachineInstr &PHI, SmallVector<unsigned, 2> *RegionIndices) {
    1399           0 :   unsigned DestReg = getPHIDestReg(PHI);
    1400             :   unsigned LinearizeDestReg =
    1401           0 :       MRI->createVirtualRegister(MRI->getRegClass(DestReg));
    1402           0 :   PHIInfo.addDest(LinearizeDestReg, PHI.getDebugLoc());
    1403           0 :   storePHILinearizationInfoDest(LinearizeDestReg, PHI, RegionIndices);
    1404           0 :   return LinearizeDestReg;
    1405             : }
    1406             : 
    1407           0 : void AMDGPUMachineCFGStructurizer::extractKilledPHIs(MachineBasicBlock *MBB) {
    1408             :   // We need to create a new chain for the killed phi, but there is no
    1409             :   // need to do the renaming outside or inside the block.
    1410           0 :   SmallPtrSet<MachineInstr *, 2> PHIs;
    1411           0 :   for (MachineBasicBlock::instr_iterator I = MBB->instr_begin(),
    1412           0 :                                          E = MBB->instr_end();
    1413           0 :        I != E; ++I) {
    1414           0 :     MachineInstr &Instr = *I;
    1415             :     if (Instr.isPHI()) {
    1416           0 :       unsigned PHIDestReg = getPHIDestReg(Instr);
    1417             :       DEBUG(dbgs() << "Extractking killed phi:\n");
    1418             :       DEBUG(Instr.dump());
    1419           0 :       PHIs.insert(&Instr);
    1420           0 :       PHIInfo.addDest(PHIDestReg, Instr.getDebugLoc());
    1421           0 :       storePHILinearizationInfoDest(PHIDestReg, Instr);
    1422             :     }
    1423             :   }
    1424             : 
    1425           0 :   for (auto PI : PHIs) {
    1426           0 :     PI->eraseFromParent();
    1427             :   }
    1428           0 : }
    1429             : 
    1430             : static bool isPHIRegionIndex(SmallVector<unsigned, 2> PHIRegionIndices,
    1431             :                              unsigned Index) {
    1432           0 :   for (auto i : PHIRegionIndices) {
    1433           0 :     if (i == Index)
    1434             :       return true;
    1435             :   }
    1436             :   return false;
    1437             : }
    1438             : 
    1439             : bool AMDGPUMachineCFGStructurizer::shrinkPHI(MachineInstr &PHI,
    1440             :                                        SmallVector<unsigned, 2> &PHIIndices,
    1441             :                                        unsigned *ReplaceReg) {
    1442           0 :   return shrinkPHI(PHI, 0, nullptr, PHIIndices, ReplaceReg);
    1443             : }
    1444             : 
    1445           0 : bool AMDGPUMachineCFGStructurizer::shrinkPHI(MachineInstr &PHI,
    1446             :                                        unsigned CombinedSourceReg,
    1447             :                                        MachineBasicBlock *SourceMBB,
    1448             :                                        SmallVector<unsigned, 2> &PHIIndices,
    1449             :                                        unsigned *ReplaceReg) {
    1450             :   DEBUG(dbgs() << "Shrink PHI: ");
    1451             :   DEBUG(PHI.dump());
    1452             :   DEBUG(dbgs() << " to " << PrintReg(getPHIDestReg(PHI), TRI)
    1453             :                << "<def> = PHI(");
    1454             : 
    1455           0 :   bool Replaced = false;
    1456           0 :   unsigned NumInputs = getPHINumInputs(PHI);
    1457           0 :   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           0 :     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) << ", BB#"
    1484             :                    << SourceMBB->getNumber());
    1485             :     }
    1486             : 
    1487           0 :     for (unsigned i = 0; i < NumInputs; ++i) {
    1488           0 :       if (isPHIRegionIndex(PHIIndices, i)) {
    1489             :         continue;
    1490             :       }
    1491           0 :       unsigned SourceReg = getPHISourceReg(PHI, i);
    1492           0 :       MachineBasicBlock *SourcePred = getPHIPred(PHI, i);
    1493           0 :       MIB.addReg(SourceReg);
    1494             :       MIB.addMBB(SourcePred);
    1495             :       DEBUG(dbgs() << PrintReg(SourceReg, TRI) << ", BB#"
    1496             :                    << SourcePred->getNumber());
    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)
    1510             :                << "<def> = PHI(");
    1511             : 
    1512           0 :   bool HasExternalEdge = false;
    1513           0 :   unsigned NumInputs = getPHINumInputs(PHI);
    1514           0 :   for (unsigned i = 0; i < NumInputs; ++i) {
    1515           0 :     if (!isPHIRegionIndex(PHIRegionIndices, i)) {
    1516           0 :       HasExternalEdge = true;
    1517             :     }
    1518             :   }
    1519             : 
    1520           0 :   if (HasExternalEdge) {
    1521           0 :     MachineBasicBlock *MBB = PHI.getParent();
    1522             :     MachineInstrBuilder MIB =
    1523           0 :         BuildMI(*MBB, PHI, PHI.getDebugLoc(), TII->get(TargetOpcode::PHI),
    1524           0 :                 getPHIDestReg(PHI));
    1525           0 :     MIB.addReg(CombinedSourceReg);
    1526           0 :     MIB.addMBB(LastMerge);
    1527             :     DEBUG(dbgs() << PrintReg(CombinedSourceReg, TRI) << ", BB#"
    1528             :                  << LastMerge->getNumber());
    1529           0 :     for (unsigned i = 0; i < NumInputs; ++i) {
    1530           0 :       if (isPHIRegionIndex(PHIRegionIndices, i)) {
    1531           0 :         continue;
    1532             :       }
    1533           0 :       unsigned SourceReg = getPHISourceReg(PHI, i);
    1534           0 :       MachineBasicBlock *SourcePred = getPHIPred(PHI, i);
    1535           0 :       MIB.addReg(SourceReg);
    1536             :       MIB.addMBB(SourcePred);
    1537             :       DEBUG(dbgs() << PrintReg(SourceReg, TRI) << ", BB#"
    1538             :                    << SourcePred->getNumber());
    1539             :     }
    1540             :     DEBUG(dbgs() << ")\n");
    1541             :   } else {
    1542           0 :     replaceRegisterWith(getPHIDestReg(PHI), CombinedSourceReg);
    1543             :   }
    1544           0 :   PHI.eraseFromParent();
    1545           0 : }
    1546             : 
    1547           0 : void AMDGPUMachineCFGStructurizer::replaceEntryPHI(
    1548             :     MachineInstr &PHI, unsigned CombinedSourceReg, MachineBasicBlock *IfMBB,
    1549             :     SmallVector<unsigned, 2> &PHIRegionIndices) {
    1550             :   DEBUG(dbgs() << "Replace entry PHI: ");
    1551             :   DEBUG(PHI.dump());
    1552             :   DEBUG(dbgs() << " with ");
    1553             : 
    1554           0 :   unsigned NumInputs = getPHINumInputs(PHI);
    1555           0 :   unsigned NumNonRegionInputs = NumInputs;
    1556           0 :   for (unsigned i = 0; i < NumInputs; ++i) {
    1557           0 :     if (isPHIRegionIndex(PHIRegionIndices, i)) {
    1558           0 :       NumNonRegionInputs--;
    1559             :     }
    1560             :   }
    1561             : 
    1562           0 :   if (NumNonRegionInputs == 0) {
    1563           0 :     auto DestReg = getPHIDestReg(PHI);
    1564           0 :     replaceRegisterWith(DestReg, CombinedSourceReg);
    1565             :     DEBUG(dbgs() << " register " << PrintReg(CombinedSourceReg, TRI) << "\n");
    1566           0 :     PHI.eraseFromParent();
    1567             :   } else {
    1568             :     DEBUG(dbgs() << PrintReg(getPHIDestReg(PHI), TRI) << "<def> = PHI(");
    1569           0 :     MachineBasicBlock *MBB = PHI.getParent();
    1570             :     MachineInstrBuilder MIB =
    1571           0 :         BuildMI(*MBB, PHI, PHI.getDebugLoc(), TII->get(TargetOpcode::PHI),
    1572           0 :                 getPHIDestReg(PHI));
    1573           0 :     MIB.addReg(CombinedSourceReg);
    1574           0 :     MIB.addMBB(IfMBB);
    1575             :     DEBUG(dbgs() << PrintReg(CombinedSourceReg, TRI) << ", BB#"
    1576             :                  << IfMBB->getNumber());
    1577           0 :     unsigned NumInputs = getPHINumInputs(PHI);
    1578           0 :     for (unsigned i = 0; i < NumInputs; ++i) {
    1579           0 :       if (isPHIRegionIndex(PHIRegionIndices, i)) {
    1580           0 :         continue;
    1581             :       }
    1582           0 :       unsigned SourceReg = getPHISourceReg(PHI, i);
    1583           0 :       MachineBasicBlock *SourcePred = getPHIPred(PHI, i);
    1584           0 :       MIB.addReg(SourceReg);
    1585             :       MIB.addMBB(SourcePred);
    1586             :       DEBUG(dbgs() << PrintReg(SourceReg, TRI) << ", BB#"
    1587             :                    << SourcePred->getNumber());
    1588             :     }
    1589             :     DEBUG(dbgs() << ")\n");
    1590           0 :     PHI.eraseFromParent();
    1591             :   }
    1592           0 : }
    1593             : 
    1594           0 : void AMDGPUMachineCFGStructurizer::replaceLiveOutRegs(
    1595             :     MachineInstr &PHI, SmallVector<unsigned, 2> &PHIRegionIndices,
    1596             :     unsigned CombinedSourceReg, LinearizedRegion *LRegion) {
    1597           0 :   bool WasLiveOut = false;
    1598           0 :   for (auto PII : PHIRegionIndices) {
    1599           0 :     unsigned Reg = getPHISourceReg(PHI, PII);
    1600           0 :     if (LRegion->isLiveOut(Reg)) {
    1601           0 :       bool IsDead = true;
    1602             : 
    1603             :       // Check if register is live out of the basic block
    1604           0 :       MachineBasicBlock *DefMBB = getDefInstr(Reg)->getParent();
    1605           0 :       for (auto UI = MRI->use_begin(Reg), E = MRI->use_end(); UI != E; ++UI) {
    1606           0 :         if ((*UI).getParent()->getParent() != DefMBB) {
    1607           0 :           IsDead = false;
    1608             :         }
    1609             :       }
    1610             : 
    1611             :       DEBUG(dbgs() << "Register " << PrintReg(Reg, TRI) << " is "
    1612             :                    << (IsDead ? "dead" : "alive") << " after PHI replace\n");
    1613           0 :       if (IsDead) {
    1614           0 :         LRegion->removeLiveOut(Reg);
    1615             :       }
    1616             :       WasLiveOut = true;
    1617             :     }
    1618             :   }
    1619             : 
    1620           0 :   if (WasLiveOut)
    1621             :     LRegion->addLiveOut(CombinedSourceReg);
    1622           0 : }
    1623             : 
    1624           0 : void AMDGPUMachineCFGStructurizer::rewriteRegionExitPHI(RegionMRT *Region,
    1625             :                                                   MachineBasicBlock *LastMerge,
    1626             :                                                   MachineInstr &PHI,
    1627             :                                                   LinearizedRegion *LRegion) {
    1628           0 :   SmallVector<unsigned, 2> PHIRegionIndices;
    1629           0 :   getPHIRegionIndices(Region, PHI, PHIRegionIndices);
    1630             :   unsigned LinearizedSourceReg =
    1631           0 :       storePHILinearizationInfo(PHI, &PHIRegionIndices);
    1632             : 
    1633           0 :   replacePHI(PHI, LinearizedSourceReg, LastMerge, PHIRegionIndices);
    1634           0 :   replaceLiveOutRegs(PHI, PHIRegionIndices, LinearizedSourceReg, LRegion);
    1635           0 : }
    1636             : 
    1637           0 : void AMDGPUMachineCFGStructurizer::rewriteRegionEntryPHI(LinearizedRegion *Region,
    1638             :                                                    MachineBasicBlock *IfMBB,
    1639             :                                                    MachineInstr &PHI) {
    1640           0 :   SmallVector<unsigned, 2> PHINonRegionIndices;
    1641           0 :   getPHINonRegionIndices(Region, PHI, PHINonRegionIndices);
    1642             :   unsigned LinearizedSourceReg =
    1643           0 :       storePHILinearizationInfo(PHI, &PHINonRegionIndices);
    1644           0 :   replaceEntryPHI(PHI, LinearizedSourceReg, IfMBB, PHINonRegionIndices);
    1645           0 : }
    1646             : 
    1647           0 : static void collectPHIs(MachineBasicBlock *MBB,
    1648             :                         SmallVector<MachineInstr *, 2> &PHIs) {
    1649           0 :   for (auto &BBI : *MBB) {
    1650             :     if (BBI.isPHI()) {
    1651           0 :       PHIs.push_back(&BBI);
    1652             :     }
    1653             :   }
    1654           0 : }
    1655             : 
    1656           0 : void AMDGPUMachineCFGStructurizer::rewriteRegionExitPHIs(RegionMRT *Region,
    1657             :                                                    MachineBasicBlock *LastMerge,
    1658             :                                                    LinearizedRegion *LRegion) {
    1659           0 :   SmallVector<MachineInstr *, 2> PHIs;
    1660           0 :   auto Exit = Region->getSucc();
    1661           0 :   if (Exit == nullptr)
    1662           0 :     return;
    1663             : 
    1664           0 :   collectPHIs(Exit, PHIs);
    1665             : 
    1666           0 :   for (auto PHII : PHIs) {
    1667           0 :     rewriteRegionExitPHI(Region, LastMerge, *PHII, LRegion);
    1668             :   }
    1669             : }
    1670             : 
    1671           0 : void AMDGPUMachineCFGStructurizer::rewriteRegionEntryPHIs(LinearizedRegion *Region,
    1672             :                                                     MachineBasicBlock *IfMBB) {
    1673           0 :   SmallVector<MachineInstr *, 2> PHIs;
    1674           0 :   auto Entry = Region->getEntry();
    1675             : 
    1676           0 :   collectPHIs(Entry, PHIs);
    1677             : 
    1678           0 :   for (auto PHII : PHIs) {
    1679           0 :     rewriteRegionEntryPHI(Region, IfMBB, *PHII);
    1680             :   }
    1681           0 : }
    1682             : 
    1683           0 : void AMDGPUMachineCFGStructurizer::insertUnconditionalBranch(MachineBasicBlock *MBB,
    1684             :                                                        MachineBasicBlock *Dest,
    1685             :                                                        const DebugLoc &DL) {
    1686             :   DEBUG(dbgs() << "Inserting unconditional branch: " << MBB->getNumber()
    1687             :                << " -> " << Dest->getNumber() << "\n");
    1688           0 :   MachineBasicBlock::instr_iterator Terminator = MBB->getFirstInstrTerminator();
    1689           0 :   bool HasTerminator = Terminator != MBB->instr_end();
    1690           0 :   if (HasTerminator) {
    1691           0 :     TII->ReplaceTailWithBranchTo(Terminator, Dest);
    1692             :   }
    1693           0 :   if (++MachineFunction::iterator(MBB) != MachineFunction::iterator(Dest)) {
    1694           0 :     TII->insertUnconditionalBranch(*MBB, Dest, DL);
    1695             :   }
    1696           0 : }
    1697             : 
    1698             : static MachineBasicBlock *getSingleExitNode(MachineFunction &MF) {
    1699           0 :   MachineBasicBlock *result = nullptr;
    1700           0 :   for (auto &MFI : MF) {
    1701           0 :     if (MFI.succ_size() == 0) {
    1702           0 :       if (result == nullptr) {
    1703             :         result = &MFI;
    1704             :       } else {
    1705             :         return nullptr;
    1706             :       }
    1707             :     }
    1708             :   }
    1709             : 
    1710             :   return result;
    1711             : }
    1712             : 
    1713             : static bool hasOneExitNode(MachineFunction &MF) {
    1714           0 :   return getSingleExitNode(MF) != nullptr;
    1715             : }
    1716             : 
    1717             : MachineBasicBlock *
    1718           0 : AMDGPUMachineCFGStructurizer::createLinearizedExitBlock(RegionMRT *Region) {
    1719           0 :   auto Exit = Region->getSucc();
    1720             : 
    1721             :   // If the exit is the end of the function, we just use the existing
    1722           0 :   MachineFunction *MF = Region->getEntry()->getParent();
    1723           0 :   if (Exit == nullptr && hasOneExitNode(*MF)) {
    1724           0 :     return &(*(--(Region->getEntry()->getParent()->end())));
    1725             :   }
    1726             : 
    1727           0 :   MachineBasicBlock *LastMerge = MF->CreateMachineBasicBlock();
    1728           0 :   if (Exit == nullptr) {
    1729           0 :     MachineFunction::iterator ExitIter = MF->end();
    1730           0 :     MF->insert(ExitIter, LastMerge);
    1731             :   } else {
    1732           0 :     MachineFunction::iterator ExitIter = Exit->getIterator();
    1733           0 :     MF->insert(ExitIter, LastMerge);
    1734           0 :     LastMerge->addSuccessor(Exit);
    1735           0 :     insertUnconditionalBranch(LastMerge, Exit);
    1736             :     DEBUG(dbgs() << "Created exit block: " << LastMerge->getNumber() << "\n");
    1737             :   }
    1738             :   return LastMerge;
    1739             : }
    1740             : 
    1741           0 : void AMDGPUMachineCFGStructurizer::insertMergePHI(MachineBasicBlock *IfBB,
    1742             :                                             MachineBasicBlock *CodeBB,
    1743             :                                             MachineBasicBlock *MergeBB,
    1744             :                                             unsigned DestRegister,
    1745             :                                             unsigned IfSourceRegister,
    1746             :                                             unsigned CodeSourceRegister,
    1747             :                                             bool IsUndefIfSource) {
    1748             :   // If this is the function exit block, we don't need a phi.
    1749           0 :   if (MergeBB->succ_begin() == MergeBB->succ_end()) {
    1750           0 :     return;
    1751             :   }
    1752             :   DEBUG(dbgs() << "Merge PHI (BB#" << MergeBB->getNumber()
    1753             :                << "): " << PrintReg(DestRegister, TRI) << "<def> = PHI("
    1754             :                << PrintReg(IfSourceRegister, TRI) << ", BB#"
    1755             :                << IfBB->getNumber() << PrintReg(CodeSourceRegister, TRI)
    1756             :                << ", BB#" << CodeBB->getNumber() << ")\n");
    1757           0 :   const DebugLoc &DL = MergeBB->findDebugLoc(MergeBB->begin());
    1758             :   MachineInstrBuilder MIB = BuildMI(*MergeBB, MergeBB->instr_begin(), DL,
    1759           0 :                                     TII->get(TargetOpcode::PHI), DestRegister);
    1760             :   if (IsUndefIfSource && false) {
    1761             :     MIB.addReg(IfSourceRegister, RegState::Undef);
    1762             :   } else {
    1763           0 :     MIB.addReg(IfSourceRegister);
    1764             :   }
    1765           0 :   MIB.addMBB(IfBB);
    1766           0 :   MIB.addReg(CodeSourceRegister);
    1767           0 :   MIB.addMBB(CodeBB);
    1768             : }
    1769             : 
    1770           0 : static void removeExternalCFGSuccessors(MachineBasicBlock *MBB) {
    1771           0 :   for (MachineBasicBlock::succ_iterator PI = MBB->succ_begin(),
    1772           0 :                                         E = MBB->succ_end();
    1773           0 :        PI != E; ++PI) {
    1774           0 :     if ((*PI) != MBB) {
    1775           0 :       (MBB)->removeSuccessor(*PI);
    1776             :     }
    1777             :   }
    1778           0 : }
    1779             : 
    1780           0 : static void removeExternalCFGEdges(MachineBasicBlock *StartMBB,
    1781             :                                    MachineBasicBlock *EndMBB) {
    1782             : 
    1783             :   // We have to check against the StartMBB successor becasuse a
    1784             :   // structurized region with a loop will have the entry block split,
    1785             :   // and the backedge will go to the entry successor.
    1786           0 :   DenseSet<std::pair<MachineBasicBlock *, MachineBasicBlock *>> Succs;
    1787           0 :   unsigned SuccSize = StartMBB->succ_size();
    1788           0 :   if (SuccSize > 0) {
    1789           0 :     MachineBasicBlock *StartMBBSucc = *(StartMBB->succ_begin());
    1790           0 :     for (MachineBasicBlock::succ_iterator PI = EndMBB->succ_begin(),
    1791           0 :                                           E = EndMBB->succ_end();
    1792           0 :          PI != E; ++PI) {
    1793             :       // Either we have a back-edge to the entry block, or a back-edge to the
    1794             :       // successor of the entry block since the block may be split.
    1795           0 :       if ((*PI) != StartMBB &&
    1796           0 :           !((*PI) == StartMBBSucc && StartMBB != EndMBB && SuccSize == 1)) {
    1797           0 :         Succs.insert(
    1798           0 :             std::pair<MachineBasicBlock *, MachineBasicBlock *>(EndMBB, *PI));
    1799             :       }
    1800             :     }
    1801             :   }
    1802             : 
    1803           0 :   for (MachineBasicBlock::pred_iterator PI = StartMBB->pred_begin(),
    1804           0 :                                         E = StartMBB->pred_end();
    1805           0 :        PI != E; ++PI) {
    1806           0 :     if ((*PI) != EndMBB) {
    1807           0 :       Succs.insert(
    1808           0 :           std::pair<MachineBasicBlock *, MachineBasicBlock *>(*PI, StartMBB));
    1809             :     }
    1810             :   }
    1811             : 
    1812           0 :   for (auto SI : Succs) {
    1813           0 :     std::pair<MachineBasicBlock *, MachineBasicBlock *> Edge = SI;
    1814             :     DEBUG(dbgs() << "Removing edge: BB#" << Edge.first->getNumber() << " -> BB#"
    1815             :                  << Edge.second->getNumber() << "\n");
    1816           0 :     Edge.first->removeSuccessor(Edge.second);
    1817             :   }
    1818           0 : }
    1819             : 
    1820           0 : MachineBasicBlock *AMDGPUMachineCFGStructurizer::createIfBlock(
    1821             :     MachineBasicBlock *MergeBB, MachineBasicBlock *CodeBBStart,
    1822             :     MachineBasicBlock *CodeBBEnd, MachineBasicBlock *SelectBB, unsigned IfReg,
    1823             :     bool InheritPreds) {
    1824           0 :   MachineFunction *MF = MergeBB->getParent();
    1825           0 :   MachineBasicBlock *IfBB = MF->CreateMachineBasicBlock();
    1826             : 
    1827           0 :   if (InheritPreds) {
    1828           0 :     for (MachineBasicBlock::pred_iterator PI = CodeBBStart->pred_begin(),
    1829           0 :                                           E = CodeBBStart->pred_end();
    1830           0 :          PI != E; ++PI) {
    1831           0 :       if ((*PI) != CodeBBEnd) {
    1832           0 :         MachineBasicBlock *Pred = (*PI);
    1833           0 :         Pred->addSuccessor(IfBB);
    1834             :       }
    1835             :     }
    1836             :   }
    1837             : 
    1838           0 :   removeExternalCFGEdges(CodeBBStart, CodeBBEnd);
    1839             : 
    1840           0 :   auto CodeBBStartI = CodeBBStart->getIterator();
    1841           0 :   auto CodeBBEndI = CodeBBEnd->getIterator();
    1842           0 :   auto MergeIter = MergeBB->getIterator();
    1843           0 :   MF->insert(MergeIter, IfBB);
    1844           0 :   MF->splice(MergeIter, CodeBBStartI, ++CodeBBEndI);
    1845           0 :   IfBB->addSuccessor(MergeBB);
    1846           0 :   IfBB->addSuccessor(CodeBBStart);
    1847             : 
    1848             :   DEBUG(dbgs() << "Created If block: " << IfBB->getNumber() << "\n");
    1849             :   // Ensure that the MergeBB is a successor of the CodeEndBB.
    1850           0 :   if (!CodeBBEnd->isSuccessor(MergeBB))
    1851           0 :     CodeBBEnd->addSuccessor(MergeBB);
    1852             : 
    1853             :   DEBUG(dbgs() << "Moved MBB#" << CodeBBStart->getNumber() << " through MBB#"
    1854             :                << CodeBBEnd->getNumber() << "\n");
    1855             : 
    1856             :   // If we have a single predecessor we can find a reasonable debug location
    1857             :   MachineBasicBlock *SinglePred =
    1858           0 :       CodeBBStart->pred_size() == 1 ? *(CodeBBStart->pred_begin()) : nullptr;
    1859             :   const DebugLoc &DL = SinglePred
    1860             :                     ? SinglePred->findDebugLoc(SinglePred->getFirstTerminator())
    1861           0 :                     : DebugLoc();
    1862             : 
    1863             :   unsigned Reg =
    1864           0 :       TII->insertEQ(IfBB, IfBB->begin(), DL, IfReg,
    1865           0 :                     SelectBB->getNumber() /* CodeBBStart->getNumber() */);
    1866           0 :   if (&(*(IfBB->getParent()->begin())) == IfBB) {
    1867           0 :     TII->materializeImmediate(*IfBB, IfBB->begin(), DL, IfReg,
    1868           0 :                               CodeBBStart->getNumber());
    1869             :   }
    1870           0 :   MachineOperand RegOp = MachineOperand::CreateReg(Reg, false, false, true);
    1871           0 :   ArrayRef<MachineOperand> Cond(RegOp);
    1872           0 :   TII->insertBranch(*IfBB, MergeBB, CodeBBStart, Cond, DL);
    1873             : 
    1874           0 :   return IfBB;
    1875             : }
    1876             : 
    1877           0 : void AMDGPUMachineCFGStructurizer::ensureCondIsNotKilled(
    1878             :     SmallVector<MachineOperand, 1> Cond) {
    1879           0 :   if (Cond.size() != 1)
    1880             :     return;
    1881           0 :   if (!Cond[0].isReg())
    1882             :     return;
    1883             : 
    1884           0 :   unsigned CondReg = Cond[0].getReg();
    1885           0 :   for (auto UI = MRI->use_begin(CondReg), E = MRI->use_end(); UI != E; ++UI) {
    1886           0 :     (*UI).setIsKill(false);
    1887             :   }
    1888             : }
    1889             : 
    1890           0 : void AMDGPUMachineCFGStructurizer::rewriteCodeBBTerminator(MachineBasicBlock *CodeBB,
    1891             :                                                      MachineBasicBlock *MergeBB,
    1892             :                                                      unsigned BBSelectReg) {
    1893           0 :   MachineBasicBlock *TrueBB = nullptr;
    1894           0 :   MachineBasicBlock *FalseBB = nullptr;
    1895           0 :   SmallVector<MachineOperand, 1> Cond;
    1896           0 :   MachineBasicBlock *FallthroughBB = FallthroughMap[CodeBB];
    1897           0 :   TII->analyzeBranch(*CodeBB, TrueBB, FalseBB, Cond);
    1898             : 
    1899           0 :   const DebugLoc &DL = CodeBB->findDebugLoc(CodeBB->getFirstTerminator());
    1900             : 
    1901           0 :   if (FalseBB == nullptr && TrueBB == nullptr && FallthroughBB == nullptr) {
    1902             :     // This is an exit block, hence no successors. We will assign the
    1903             :     // bb select register to the entry block.
    1904           0 :     TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
    1905             :                               BBSelectReg,
    1906           0 :                               CodeBB->getParent()->begin()->getNumber());
    1907           0 :     insertUnconditionalBranch(CodeBB, MergeBB, DL);
    1908           0 :     return;
    1909             :   }
    1910             : 
    1911           0 :   if (FalseBB == nullptr && TrueBB == nullptr) {
    1912           0 :     TrueBB = FallthroughBB;
    1913           0 :   } else if (TrueBB != nullptr) {
    1914           0 :     FalseBB =
    1915           0 :         (FallthroughBB && (FallthroughBB != TrueBB)) ? FallthroughBB : FalseBB;
    1916             :   }
    1917             : 
    1918           0 :   if ((TrueBB != nullptr && FalseBB == nullptr) || (TrueBB == FalseBB)) {
    1919           0 :     TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
    1920           0 :                               BBSelectReg, TrueBB->getNumber());
    1921             :   } else {
    1922           0 :     const TargetRegisterClass *RegClass = MRI->getRegClass(BBSelectReg);
    1923           0 :     unsigned TrueBBReg = MRI->createVirtualRegister(RegClass);
    1924           0 :     unsigned FalseBBReg = MRI->createVirtualRegister(RegClass);
    1925           0 :     TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
    1926           0 :                               TrueBBReg, TrueBB->getNumber());
    1927           0 :     TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
    1928           0 :                               FalseBBReg, FalseBB->getNumber());
    1929           0 :     ensureCondIsNotKilled(Cond);
    1930           0 :     TII->insertVectorSelect(*CodeBB, CodeBB->getFirstTerminator(), DL,
    1931             :                             BBSelectReg, Cond, TrueBBReg, FalseBBReg);
    1932             :   }
    1933             : 
    1934           0 :   insertUnconditionalBranch(CodeBB, MergeBB, DL);
    1935             : }
    1936             : 
    1937           0 : MachineInstr *AMDGPUMachineCFGStructurizer::getDefInstr(unsigned Reg) {
    1938           0 :   if (MRI->def_begin(Reg) == MRI->def_end()) {
    1939             :     DEBUG(dbgs() << "Register " << PrintReg(Reg, MRI->getTargetRegisterInfo())
    1940             :                  << " has NO defs\n");
    1941           0 :   } else if (!MRI->hasOneDef(Reg)) {
    1942             :     DEBUG(dbgs() << "Register " << PrintReg(Reg, MRI->getTargetRegisterInfo())
    1943             :                  << " has multiple defs\n");
    1944             :     DEBUG(dbgs() << "DEFS BEGIN:\n");
    1945           0 :     for (auto DI = MRI->def_begin(Reg), DE = MRI->def_end(); DI != DE; ++DI) {
    1946             :       DEBUG(DI->getParent()->dump());
    1947             :     }
    1948             :     DEBUG(dbgs() << "DEFS END\n");
    1949             :   }
    1950             : 
    1951             :   assert(MRI->hasOneDef(Reg) && "Register has multiple definitions");
    1952           0 :   return (*(MRI->def_begin(Reg))).getParent();
    1953             : }
    1954             : 
    1955           0 : void AMDGPUMachineCFGStructurizer::insertChainedPHI(MachineBasicBlock *IfBB,
    1956             :                                               MachineBasicBlock *CodeBB,
    1957             :                                               MachineBasicBlock *MergeBB,
    1958             :                                               LinearizedRegion *InnerRegion,
    1959             :                                               unsigned DestReg,
    1960             :                                               unsigned SourceReg) {
    1961             :   // In this function we know we are part of a chain already, so we need
    1962             :   // to add the registers to the existing chain, and rename the register
    1963             :   // inside the region.
    1964           0 :   bool IsSingleBB = InnerRegion->getEntry() == InnerRegion->getExit();
    1965           0 :   MachineInstr *DefInstr = getDefInstr(SourceReg);
    1966           0 :   if (DefInstr->isPHI() && DefInstr->getParent() == CodeBB && IsSingleBB) {
    1967             :     // Handle the case where the def is a PHI-def inside a basic
    1968             :     // block, then we only need to do renaming. Special care needs to
    1969             :     // be taken if the PHI-def is part of an existing chain, or if a
    1970             :     // new one needs to be created.
    1971           0 :     InnerRegion->replaceRegisterInsideRegion(SourceReg, DestReg, true, MRI);
    1972             : 
    1973             :     // We collect all PHI Information, and if we are at the region entry,
    1974             :     // all PHIs will be removed, and then re-introduced if needed.
    1975           0 :     storePHILinearizationInfoDest(DestReg, *DefInstr);
    1976             :     // We have picked up all the information we need now and can remove
    1977             :     // the PHI
    1978           0 :     PHIInfo.removeSource(DestReg, SourceReg, CodeBB);
    1979           0 :     DefInstr->eraseFromParent();
    1980             :   } else {
    1981             :     // If this is not a phi-def, or it is a phi-def but from a linearized region
    1982           0 :     if (IsSingleBB && DefInstr->getParent() == InnerRegion->getEntry()) {
    1983             :       // If this is a single BB and the definition is in this block we
    1984             :       // need to replace any uses outside the region.
    1985           0 :       InnerRegion->replaceRegisterOutsideRegion(SourceReg, DestReg, false, MRI);
    1986             :     }
    1987           0 :     const TargetRegisterClass *RegClass = MRI->getRegClass(DestReg);
    1988           0 :     unsigned NextDestReg = MRI->createVirtualRegister(RegClass);
    1989           0 :     bool IsLastDef = PHIInfo.getNumSources(DestReg) == 1;
    1990             :     DEBUG(dbgs() << "Insert Chained PHI\n");
    1991           0 :     insertMergePHI(IfBB, InnerRegion->getExit(), MergeBB, DestReg, NextDestReg,
    1992             :                    SourceReg, IsLastDef);
    1993             : 
    1994           0 :     PHIInfo.removeSource(DestReg, SourceReg, CodeBB);
    1995           0 :     if (IsLastDef) {
    1996           0 :       const DebugLoc &DL = IfBB->findDebugLoc(IfBB->getFirstTerminator());
    1997           0 :       TII->materializeImmediate(*IfBB, IfBB->getFirstTerminator(), DL,
    1998             :                                 NextDestReg, 0);
    1999           0 :       PHIInfo.deleteDef(DestReg);
    2000             :     } else {
    2001           0 :       PHIInfo.replaceDef(DestReg, NextDestReg);
    2002             :     }
    2003             :   }
    2004           0 : }
    2005             : 
    2006           0 : bool AMDGPUMachineCFGStructurizer::containsDef(MachineBasicBlock *MBB,
    2007             :                                          LinearizedRegion *InnerRegion,
    2008             :                                          unsigned Register) {
    2009           0 :   return getDefInstr(Register)->getParent() == MBB ||
    2010           0 :          InnerRegion->contains(getDefInstr(Register)->getParent());
    2011             : }
    2012             : 
    2013           0 : void AMDGPUMachineCFGStructurizer::rewriteLiveOutRegs(MachineBasicBlock *IfBB,
    2014             :                                                 MachineBasicBlock *CodeBB,
    2015             :                                                 MachineBasicBlock *MergeBB,
    2016             :                                                 LinearizedRegion *InnerRegion,
    2017             :                                                 LinearizedRegion *LRegion) {
    2018           0 :   DenseSet<unsigned> *LiveOuts = InnerRegion->getLiveOuts();
    2019           0 :   SmallVector<unsigned, 4> OldLiveOuts;
    2020           0 :   bool IsSingleBB = InnerRegion->getEntry() == InnerRegion->getExit();
    2021           0 :   for (auto OLI : *LiveOuts) {
    2022           0 :     OldLiveOuts.push_back(OLI);
    2023             :   }
    2024             : 
    2025           0 :   for (auto LI : OldLiveOuts) {
    2026             :     DEBUG(dbgs() << "LiveOut: " << PrintReg(LI, TRI));
    2027           0 :     if (!containsDef(CodeBB, InnerRegion, LI) ||
    2028           0 :         (!IsSingleBB && (getDefInstr(LI)->getParent() == LRegion->getExit()))) {
    2029             :       // If the register simly lives through the CodeBB, we don't have
    2030             :       // to rewrite anything since the register is not defined in this
    2031             :       // part of the code.
    2032             :       DEBUG(dbgs() << "- through");
    2033           0 :       continue;
    2034             :     }
    2035             :     DEBUG(dbgs() << "\n");
    2036           0 :     unsigned Reg = LI;
    2037           0 :     if (/*!PHIInfo.isSource(Reg) &&*/ Reg != InnerRegion->getBBSelectRegOut()) {
    2038             :       // If the register is live out, we do want to create a phi,
    2039             :       // unless it is from the Exit block, becasuse in that case there
    2040             :       // is already a PHI, and no need to create a new one.
    2041             : 
    2042             :       // If the register is just a live out def and not part of a phi
    2043             :       // chain, we need to create a PHI node to handle the if region,
    2044             :       // and replace all uses outside of the region with the new dest
    2045             :       // register, unless it is the outgoing BB select register. We have
    2046             :       // already creaed phi nodes for these.
    2047           0 :       const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
    2048           0 :       unsigned PHIDestReg = MRI->createVirtualRegister(RegClass);
    2049           0 :       unsigned IfSourceReg = MRI->createVirtualRegister(RegClass);
    2050             :       // Create initializer, this value is never used, but is needed
    2051             :       // to satisfy SSA.
    2052             :       DEBUG(dbgs() << "Initializer for reg: " << PrintReg(Reg) << "\n");
    2053           0 :       TII->materializeImmediate(*IfBB, IfBB->getFirstTerminator(), DebugLoc(),
    2054             :                         IfSourceReg, 0);
    2055             : 
    2056           0 :       InnerRegion->replaceRegisterOutsideRegion(Reg, PHIDestReg, true, MRI);
    2057             :       DEBUG(dbgs() << "Insert Non-Chained Live out PHI\n");
    2058           0 :       insertMergePHI(IfBB, InnerRegion->getExit(), MergeBB, PHIDestReg,
    2059             :                      IfSourceReg, Reg, true);
    2060             :     }
    2061             :   }
    2062             : 
    2063             :   // Handle the chained definitions in PHIInfo, checking if this basic block
    2064             :   // is a source block for a definition.
    2065           0 :   SmallVector<unsigned, 4> Sources;
    2066           0 :   if (PHIInfo.findSourcesFromMBB(CodeBB, Sources)) {
    2067             :     DEBUG(dbgs() << "Inserting PHI Live Out from BB#" << CodeBB->getNumber()
    2068             :                  << "\n");
    2069           0 :     for (auto SI : Sources) {
    2070             :       unsigned DestReg;
    2071           0 :       PHIInfo.findDest(SI, CodeBB, DestReg);
    2072           0 :       insertChainedPHI(IfBB, CodeBB, MergeBB, InnerRegion, DestReg, SI);
    2073             :     }
    2074             :     DEBUG(dbgs() << "Insertion done.\n");
    2075             :   }
    2076             : 
    2077             :   DEBUG(PHIInfo.dump(MRI));
    2078           0 : }
    2079             : 
    2080           0 : void AMDGPUMachineCFGStructurizer::prunePHIInfo(MachineBasicBlock *MBB) {
    2081             :   DEBUG(dbgs() << "Before PHI Prune\n");
    2082             :   DEBUG(PHIInfo.dump(MRI));
    2083             :   SmallVector<std::tuple<unsigned, unsigned, MachineBasicBlock *>, 4>
    2084           0 :       ElimiatedSources;
    2085           0 :   for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
    2086             :        ++DRI) {
    2087             : 
    2088           0 :     unsigned DestReg = *DRI;
    2089           0 :     auto SE = PHIInfo.sources_end(DestReg);
    2090             : 
    2091           0 :     bool MBBContainsPHISource = false;
    2092             :     // Check if there is a PHI source in this MBB
    2093           0 :     for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
    2094           0 :       unsigned SourceReg = (*SRI).first;
    2095           0 :       MachineOperand *Def = &(*(MRI->def_begin(SourceReg)));
    2096           0 :       if (Def->getParent()->getParent() == MBB) {
    2097           0 :         MBBContainsPHISource = true;
    2098             :       }
    2099             :     }
    2100             : 
    2101             :     // If so, all other sources are useless since we know this block
    2102             :     // is always executed when the region is executed.
    2103           0 :     if (MBBContainsPHISource) {
    2104           0 :       for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
    2105           0 :         PHILinearize::PHISourceT Source = *SRI;
    2106           0 :         unsigned SourceReg = Source.first;
    2107           0 :         MachineBasicBlock *SourceMBB = Source.second;
    2108           0 :         MachineOperand *Def = &(*(MRI->def_begin(SourceReg)));
    2109           0 :         if (Def->getParent()->getParent() != MBB) {
    2110           0 :           ElimiatedSources.push_back(
    2111           0 :               std::make_tuple(DestReg, SourceReg, SourceMBB));
    2112             :         }
    2113             :       }
    2114             :     }
    2115             :   }
    2116             : 
    2117             :   // Remove the PHI sources that are in the given MBB
    2118           0 :   for (auto &SourceInfo : ElimiatedSources) {
    2119           0 :     PHIInfo.removeSource(std::get<0>(SourceInfo), std::get<1>(SourceInfo),
    2120           0 :                          std::get<2>(SourceInfo));
    2121             :   }
    2122             :   DEBUG(dbgs() << "After PHI Prune\n");
    2123             :   DEBUG(PHIInfo.dump(MRI));
    2124           0 : }
    2125             : 
    2126           0 : void AMDGPUMachineCFGStructurizer::createEntryPHI(LinearizedRegion *CurrentRegion,
    2127             :                                             unsigned DestReg) {
    2128           0 :   MachineBasicBlock *Entry = CurrentRegion->getEntry();
    2129           0 :   MachineBasicBlock *Exit = CurrentRegion->getExit();
    2130             : 
    2131             :   DEBUG(dbgs() << "RegionExit: " << Exit->getNumber()
    2132             :                << " Pred: " << (*(Entry->pred_begin()))->getNumber() << "\n");
    2133             : 
    2134           0 :   int NumSources = 0;
    2135           0 :   auto SE = PHIInfo.sources_end(DestReg);
    2136             : 
    2137           0 :   for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
    2138           0 :     NumSources++;
    2139             :   }
    2140             : 
    2141           0 :   if (NumSources == 1) {
    2142           0 :     auto SRI = PHIInfo.sources_begin(DestReg);
    2143           0 :     unsigned SourceReg = (*SRI).first;
    2144           0 :     replaceRegisterWith(DestReg, SourceReg);
    2145             :   } else {
    2146           0 :     const DebugLoc &DL = Entry->findDebugLoc(Entry->begin());
    2147             :     MachineInstrBuilder MIB = BuildMI(*Entry, Entry->instr_begin(), DL,
    2148           0 :                                       TII->get(TargetOpcode::PHI), DestReg);
    2149             :     DEBUG(dbgs() << "Entry PHI " << PrintReg(DestReg, TRI) << "<def> = PHI(");
    2150             : 
    2151           0 :     unsigned CurrentBackedgeReg = 0;
    2152             : 
    2153           0 :     for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
    2154           0 :       unsigned SourceReg = (*SRI).first;
    2155             : 
    2156           0 :       if (CurrentRegion->contains((*SRI).second)) {
    2157           0 :         if (CurrentBackedgeReg == 0) {
    2158             :           CurrentBackedgeReg = SourceReg;
    2159             :         } else {
    2160           0 :           MachineInstr *PHIDefInstr = getDefInstr(SourceReg);
    2161           0 :           MachineBasicBlock *PHIDefMBB = PHIDefInstr->getParent();
    2162             :           const TargetRegisterClass *RegClass =
    2163           0 :               MRI->getRegClass(CurrentBackedgeReg);
    2164           0 :           unsigned NewBackedgeReg = MRI->createVirtualRegister(RegClass);
    2165             :           MachineInstrBuilder BackedgePHI =
    2166             :               BuildMI(*PHIDefMBB, PHIDefMBB->instr_begin(), DL,
    2167           0 :                       TII->get(TargetOpcode::PHI), NewBackedgeReg);
    2168           0 :           BackedgePHI.addReg(CurrentBackedgeReg);
    2169           0 :           BackedgePHI.addMBB(getPHIPred(*PHIDefInstr, 0));
    2170           0 :           BackedgePHI.addReg(getPHISourceReg(*PHIDefInstr, 1));
    2171           0 :           BackedgePHI.addMBB((*SRI).second);
    2172           0 :           CurrentBackedgeReg = NewBackedgeReg;
    2173             :           DEBUG(dbgs() << "Inserting backedge PHI: "
    2174             :                        << PrintReg(NewBackedgeReg, TRI) << "<def> = PHI("
    2175             :                        << PrintReg(CurrentBackedgeReg, TRI) << ", BB#"
    2176             :                        << getPHIPred(*PHIDefInstr, 0)->getNumber() << ", "
    2177             :                        << PrintReg(getPHISourceReg(*PHIDefInstr, 1), TRI)
    2178             :                        << ", BB#" << (*SRI).second->getNumber());
    2179             :         }
    2180             :       } else {
    2181           0 :         MIB.addReg(SourceReg);
    2182           0 :         MIB.addMBB((*SRI).second);
    2183             :         DEBUG(dbgs() << PrintReg(SourceReg, TRI) << ", BB#"
    2184             :                      << (*SRI).second->getNumber() << ", ");
    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) << ", BB#"
    2193             :                    << Exit->getNumber() << ")\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           0 :     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           0 :     MachineOperand &O = *I;
    2220           0 :     ++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           0 :     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           0 :     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           0 :     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           0 :     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           0 :     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           0 :       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           0 :         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           0 :             MachineOperand::CreateReg(Reg, false, false, true);
    2328           0 :         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           0 :     CurrentRegion->addMBB(CodeBB);
    2338           0 :     LinearizedRegion InnerRegion(CodeBB, MRI, TRI, PHIInfo);
    2339             : 
    2340           0 :     InnerRegion.setParent(CurrentRegion);
    2341             :     DEBUG(dbgs() << "Insert BB Select PHI (BB)\n");
    2342           0 :     insertMergePHI(IfBB, CodeBB, MergeBB, BBSelectRegOut, BBSelectRegIn,
    2343             :                    CodeBBSelectReg);
    2344           0 :     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           0 :   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           0 :       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           0 :       MachineOperand RegOp = MachineOperand::CreateReg(Reg, false, false, true);
    2386           0 :       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           0 :     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           0 :   SmallVector<unsigned, 2> PHIRegionIndices;
    2421           0 :   getPHIRegionIndices(LRegion, PHI, PHIRegionIndices);
    2422             : 
    2423             :   assert(PHIRegionIndices.size() == 1);
    2424             : 
    2425           0 :   unsigned RegionIndex = PHIRegionIndices[0];
    2426           0 :   unsigned RegionSourceReg = getPHISourceReg(PHI, RegionIndex);
    2427           0 :   MachineBasicBlock *RegionSourceMBB = getPHIPred(PHI, RegionIndex);
    2428           0 :   unsigned PHIDest = getPHIDestReg(PHI);
    2429           0 :   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)
    2443             :                << "<def> = PHI(");
    2444           0 :   MIB.addReg(PHISource);
    2445           0 :   MIB.addMBB(Entry);
    2446             :   DEBUG(dbgs() << PrintReg(PHISource, TRI) << ", BB#" << Entry->getNumber());
    2447           0 :   MIB.addReg(RegionSourceReg);
    2448           0 :   MIB.addMBB(RegionSourceMBB);
    2449             :   DEBUG(dbgs() << " ," << PrintReg(RegionSourceReg, TRI) << ", BB#"
    2450             :                << RegionSourceMBB->getNumber() << ")\n");
    2451           0 : }
    2452             : 
    2453           0 : void AMDGPUMachineCFGStructurizer::splitLoopPHIs(MachineBasicBlock *Entry,
    2454             :                                            MachineBasicBlock *EntrySucc,
    2455             :                                            LinearizedRegion *LRegion) {
    2456           0 :   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           0 :   AfterExitIter++;
    2475           0 :   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           0 :   LRegion->addMBB(NewExit);
    2481           0 :   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           0 :     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           0 :         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           0 :   MF->insert(MBBIter, SuccMBB);
    2512           0 :   SuccMBB->transferSuccessorsAndUpdatePHIs(MBB);
    2513           0 :   MBB->addSuccessor(SuccMBB);
    2514             : 
    2515             :   // Splice the code over.
    2516           0 :   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 BB#" << Entry->getNumber() << " to BB#"
    2532             :                << Entry->getNumber() << " -> BB#" << EntrySucc->getNumber()
    2533             :                << "\n");
    2534           0 :   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           0 :   MachineInstr &Branch = *(Exit->instr_rbegin());
    2542           0 :   for (auto &UI : Branch.uses()) {
    2543           0 :     if (UI.isMBB() && UI.getMBB() == Entry) {
    2544           0 :       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           0 :   for (MachineBasicBlock::pred_iterator PI = Exit->pred_begin(),
    2567           0 :                                         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           0 :     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           0 :   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           0 :   MachineBasicBlock *CurrentMerge = LastMerge;
    2618           0 :   LRegion->addMBB(LastMerge);
    2619           0 :   LRegion->setExit(LastMerge);
    2620             : 
    2621           0 :   rewriteRegionExitPHIs(Region, LastMerge, LRegion);
    2622           0 :   removeOldExitPreds(Region);
    2623             : 
    2624             :   DEBUG(PHIInfo.dump(MRI));
    2625             : 
    2626           0 :   SetVector<MRT *> *Children = Region->getChildren();
    2627             :   DEBUG(dbgs() << "===========If Region Start===============\n");
    2628           0 :   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           0 :     auto CNI = CI;
    2641           0 :     ++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           0 :         unsigned OuterSelect = InnerLRegion->getBBSelectRegOut();
    2660             :         unsigned InnerSelectReg =
    2661           0 :             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           0 :       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           0 :       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           0 :     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           0 :   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           0 :   bool Changed = false;
    2771             : 
    2772           0 :   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           0 :   LRegion->setRegionMRT(Region);
    2807           0 :   Region->setLinearizedRegion(LRegion);
    2808           0 :   LRegion->setParent(Region->getParent()
    2809           0 :                          ? 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           0 :     Region->setBBSelectRegOut(SelectOut);
    2820           0 :     unsigned InnerSelectOut = createBBSelectReg(TII, MRI);
    2821             : 
    2822             :     // Fixme: Move linearization creation to the original spot
    2823           0 :     createLinearizedRegion(Region, SelectOut);
    2824             : 
    2825           0 :     for (auto CI = Region->getChildren()->begin(),
    2826           0 :               CE = Region->getChildren()->end();
    2827           0 :          CI != CE; ++CI) {
    2828           0 :       InnerSelectOut =
    2829           0 :           initializeSelectRegisters((*CI), InnerSelectOut, MRI, TII);
    2830             :     }
    2831           0 :     MRT->setBBSelectRegIn(InnerSelectOut);
    2832           0 :     return InnerSelectOut;
    2833             :   } else {
    2834           0 :     MRT->setBBSelectRegOut(SelectOut);
    2835           0 :     unsigned NewSelectIn = createBBSelectReg(TII, MRI);
    2836           0 :     MRT->setBBSelectRegIn(NewSelectIn);
    2837           0 :     return NewSelectIn;
    2838             :   }
    2839             : }
    2840             : 
    2841             : static void checkRegOnlyPHIInputs(MachineFunction &MF) {
    2842           0 :   for (auto &MBBI : MF) {
    2843           0 :     for (MachineBasicBlock::instr_iterator I = MBBI.instr_begin(),
    2844           0 :                                            E = MBBI.instr_end();
    2845           0 :          I != E; ++I) {
    2846           0 :       MachineInstr &Instr = *I;
    2847             :       if (Instr.isPHI()) {
    2848           0 :         int numPreds = getPHINumInputs(Instr);
    2849           0 :         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           0 :   const SIInstrInfo *TII = ST.getInstrInfo();
    2861           0 :   TRI = ST.getRegisterInfo();
    2862           0 :   MRI = &(MF.getRegInfo());
    2863           0 :   initFallthroughMap(MF);
    2864             : 
    2865           0 :   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           0 :   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       72306 : 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      144612 : }

Generated by: LCOV version 1.13