LCOV - code coverage report
Current view: top level - lib/Target/AMDGPU - AMDGPUMachineCFGStructurizer.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 0 931 0.0 %
Date: 2018-09-23 13:06:45 Functions: 0 122 0.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13