/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp

Bug Summary

File:	lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp
Warning:	line 2071, column 7 5th function call argument is an uninitialized value
Annotated Source Code

Press '?' to see keyboard shortcuts
Show analyzer invocation
clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name AMDGPUMachineCFGStructurizer.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn326246/build-llvm/lib/Target/AMDGPU -I /build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU -I /build/llvm-toolchain-snapshot-7~svn326246/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn326246/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn326246/build-llvm/lib/Target/AMDGPU -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-02-28-041547-14988-1 -x c++ /build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp
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//===----------------------------------------------------------------------===//

14#include "AMDGPU.h"
15#include "AMDGPUSubtarget.h"
16#include "SIInstrInfo.h"
17#include "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/DenseSet.h"
20#include "llvm/ADT/PostOrderIterator.h"
21#include "llvm/ADT/SetVector.h"
22#include "llvm/ADT/SmallPtrSet.h"
23#include "llvm/ADT/SmallVector.h"
24#include "llvm/CodeGen/MachineBasicBlock.h"
25#include "llvm/CodeGen/MachineFunction.h"
26#include "llvm/CodeGen/MachineFunctionPass.h"
27#include "llvm/CodeGen/MachineInstr.h"
28#include "llvm/CodeGen/MachineInstrBuilder.h"
29#include "llvm/CodeGen/MachineOperand.h"
30#include "llvm/CodeGen/MachineRegionInfo.h"
31#include "llvm/CodeGen/MachineRegisterInfo.h"
32#include "llvm/CodeGen/TargetOpcodes.h"
33#include "llvm/CodeGen/TargetRegisterInfo.h"
34#include "llvm/IR/DebugLoc.h"
35#include "llvm/Pass.h"
36#include "llvm/Support/Compiler.h"
37#include "llvm/Support/Debug.h"
38#include "llvm/Support/ErrorHandling.h"
39#include "llvm/Support/raw_ostream.h"
40#include <cassert>
41#include <tuple>
42#include <utility>

44using namespace llvm;

46#define DEBUG_TYPE"amdgpucfgstructurizer" "amdgpucfgstructurizer"

48namespace {

50class PHILinearizeDestIterator;

52class PHILinearize {
friend class PHILinearizeDestIterator;

55public:
using PHISourceT = std::pair<unsigned, MachineBasicBlock *>;

58private:
using PHISourcesT = DenseSet<PHISourceT>;
using PHIInfoElementT = struct {
  unsigned DestReg;
  DebugLoc DL;
  PHISourcesT Sources;
};
using PHIInfoT = SmallPtrSet<PHIInfoElementT *, 2>;
PHIInfoT PHIInfo;

static unsigned phiInfoElementGetDest(PHIInfoElementT *Info);
static void phiInfoElementSetDef(PHIInfoElementT *Info, unsigned NewDef);
static PHISourcesT &phiInfoElementGetSources(PHIInfoElementT *Info);
static void phiInfoElementAddSource(PHIInfoElementT *Info, unsigned SourceReg,
                                    MachineBasicBlock *SourceMBB);
static void phiInfoElementRemoveSource(PHIInfoElementT *Info,
                                       unsigned SourceReg,
                                       MachineBasicBlock *SourceMBB);
PHIInfoElementT *findPHIInfoElement(unsigned DestReg);
PHIInfoElementT *findPHIInfoElementFromSource(unsigned SourceReg,
                                              MachineBasicBlock *SourceMBB);

80public:
bool findSourcesFromMBB(MachineBasicBlock *SourceMBB,
                        SmallVector<unsigned, 4> &Sources);
void addDest(unsigned DestReg, const DebugLoc &DL);
void replaceDef(unsigned OldDestReg, unsigned NewDestReg);
void deleteDef(unsigned DestReg);
void addSource(unsigned DestReg, unsigned SourceReg,
               MachineBasicBlock *SourceMBB);
void removeSource(unsigned DestReg, unsigned SourceReg,
                  MachineBasicBlock *SourceMBB = nullptr);
bool findDest(unsigned SourceReg, MachineBasicBlock *SourceMBB,
              unsigned &DestReg);
bool isSource(unsigned Reg, MachineBasicBlock *SourceMBB = nullptr);
unsigned getNumSources(unsigned DestReg);
void dump(MachineRegisterInfo *MRI);
void clear();

using source_iterator = PHISourcesT::iterator;
using dest_iterator = PHILinearizeDestIterator;

dest_iterator dests_begin();
dest_iterator dests_end();

source_iterator sources_begin(unsigned Reg);
source_iterator sources_end(unsigned Reg);
105};

107class PHILinearizeDestIterator {
108private:
PHILinearize::PHIInfoT::iterator Iter;

111public:
PHILinearizeDestIterator(PHILinearize::PHIInfoT::iterator I) : Iter(I) {}

unsigned operator*() { return PHILinearize::phiInfoElementGetDest(*Iter); }
PHILinearizeDestIterator &operator++() {
  ++Iter;
  return *this;
}
bool operator==(const PHILinearizeDestIterator &I) const {
  return I.Iter == Iter;
}
bool operator!=(const PHILinearizeDestIterator &I) const {
  return I.Iter != Iter;
}
125};

127} // end anonymous namespace

129unsigned PHILinearize::phiInfoElementGetDest(PHIInfoElementT *Info) {
return Info->DestReg;
131}

133void PHILinearize::phiInfoElementSetDef(PHIInfoElementT *Info,
                                      unsigned NewDef) {
Info->DestReg = NewDef;
136}

138PHILinearize::PHISourcesT &
139PHILinearize::phiInfoElementGetSources(PHIInfoElementT *Info) {
return Info->Sources;
141}

143void PHILinearize::phiInfoElementAddSource(PHIInfoElementT *Info,
                                         unsigned SourceReg,
                                         MachineBasicBlock *SourceMBB) {
// Assertion ensures we don't use the same SourceMBB for the
// sources, because we cannot have different registers with
// identical predecessors, but we can have the same register for
// multiple predecessors.
150#if !defined(NDEBUG)
for (auto SI : phiInfoElementGetSources(Info)) {
  assert((SI.second != SourceMBB || SourceReg == SI.first))(static_cast <bool> ((SI.second != SourceMBB || SourceReg
 == SI.first)) ? void (0) : __assert_fail ("(SI.second != SourceMBB || SourceReg == SI.first)"
, "/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp"
, 152, __extension__ __PRETTY_FUNCTION__));
}
154#endif

phiInfoElementGetSources(Info).insert(PHISourceT(SourceReg, SourceMBB));
157}

159void PHILinearize::phiInfoElementRemoveSource(PHIInfoElementT *Info,
                                            unsigned SourceReg,
                                            MachineBasicBlock *SourceMBB) {
auto &Sources = phiInfoElementGetSources(Info);
SmallVector<PHISourceT, 4> ElimiatedSources;
for (auto SI : Sources) {
  if (SI.first == SourceReg &&
      (SI.second == nullptr || SI.second == SourceMBB)) {
    ElimiatedSources.push_back(PHISourceT(SI.first, SI.second));
  }
}

for (auto &Source : ElimiatedSources) {
  Sources.erase(Source);
}
174}

176PHILinearize::PHIInfoElementT *
177PHILinearize::findPHIInfoElement(unsigned DestReg) {
for (auto I : PHIInfo) {
  if (phiInfoElementGetDest(I) == DestReg) {
    return I;
  }
}
return nullptr;
184}

186PHILinearize::PHIInfoElementT *
187PHILinearize::findPHIInfoElementFromSource(unsigned SourceReg,
                                         MachineBasicBlock *SourceMBB) {
for (auto I : PHIInfo) {
  for (auto SI : phiInfoElementGetSources(I)) {
    if (SI.first == SourceReg &&
        (SI.second == nullptr || SI.second == SourceMBB)) {
      return I;
    }
  }
}
return nullptr;
198}

200bool PHILinearize::findSourcesFromMBB(MachineBasicBlock *SourceMBB,
                                    SmallVector<unsigned, 4> &Sources) {
bool FoundSource = false;
for (auto I : PHIInfo) {
  for (auto SI : phiInfoElementGetSources(I)) {
    if (SI.second == SourceMBB) {
      FoundSource = true;
      Sources.push_back(SI.first);
    }
  }
}
return FoundSource;
212}

214void PHILinearize::addDest(unsigned DestReg, const DebugLoc &DL) {
assert(findPHIInfoElement(DestReg) == nullptr && "Dest already exsists")(static_cast <bool> (findPHIInfoElement(DestReg) == nullptr
 && "Dest already exsists") ? void (0) : __assert_fail
 ("findPHIInfoElement(DestReg) == nullptr && \"Dest already exsists\""
, "/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp"
, 215, __extension__ __PRETTY_FUNCTION__));
PHISourcesT EmptySet;
PHIInfoElementT *NewElement = new PHIInfoElementT();
NewElement->DestReg = DestReg;
NewElement->DL = DL;
NewElement->Sources = EmptySet;
PHIInfo.insert(NewElement);
222}

224void PHILinearize::replaceDef(unsigned OldDestReg, unsigned NewDestReg) {
phiInfoElementSetDef(findPHIInfoElement(OldDestReg), NewDestReg);
226}

228void PHILinearize::deleteDef(unsigned DestReg) {
PHIInfoElementT *InfoElement = findPHIInfoElement(DestReg);
PHIInfo.erase(InfoElement);
delete InfoElement;
232}

234void PHILinearize::addSource(unsigned DestReg, unsigned SourceReg,
                           MachineBasicBlock *SourceMBB) {
phiInfoElementAddSource(findPHIInfoElement(DestReg), SourceReg, SourceMBB);
237}

239void PHILinearize::removeSource(unsigned DestReg, unsigned SourceReg,
                              MachineBasicBlock *SourceMBB) {
phiInfoElementRemoveSource(findPHIInfoElement(DestReg), SourceReg, SourceMBB);
242}

244bool PHILinearize::findDest(unsigned SourceReg, MachineBasicBlock *SourceMBB,
                          unsigned &DestReg) {
PHIInfoElementT *InfoElement =
    findPHIInfoElementFromSource(SourceReg, SourceMBB);
if (InfoElement != nullptr) {
11
←
Assuming the condition is false→
12
←
Taking false branch→
  DestReg = phiInfoElementGetDest(InfoElement);
  return true;
}
return false;
13
←
Returning without writing to 'DestReg'→
253}

255bool PHILinearize::isSource(unsigned Reg, MachineBasicBlock *SourceMBB) {
unsigned DestReg;
return findDest(Reg, SourceMBB, DestReg);
258}

260unsigned PHILinearize::getNumSources(unsigned DestReg) {
return phiInfoElementGetSources(findPHIInfoElement(DestReg)).size();
262}

264#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
265LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void PHILinearize::dump(MachineRegisterInfo *MRI) {
const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
dbgs() << "=PHIInfo Start=\n";
for (auto PII : this->PHIInfo) {
  PHIInfoElementT &Element = *PII;
  dbgs() << "Dest: " << printReg(Element.DestReg, TRI)
         << " Sources: {";
  for (auto &SI : Element.Sources) {
    dbgs() << printReg(SI.first, TRI) << '(' << printMBBReference(*SI.second)
           << "),";
  }
  dbgs() << "}\n";
}
dbgs() << "=PHIInfo End=\n";
279}
280#endif

282void PHILinearize::clear() { PHIInfo = PHIInfoT(); }

284PHILinearize::dest_iterator PHILinearize::dests_begin() {
return PHILinearizeDestIterator(PHIInfo.begin());
286}

288PHILinearize::dest_iterator PHILinearize::dests_end() {
return PHILinearizeDestIterator(PHIInfo.end());
290}

292PHILinearize::source_iterator PHILinearize::sources_begin(unsigned Reg) {
auto InfoElement = findPHIInfoElement(Reg);
return phiInfoElementGetSources(InfoElement).begin();
295}

297PHILinearize::source_iterator PHILinearize::sources_end(unsigned Reg) {
auto InfoElement = findPHIInfoElement(Reg);
return phiInfoElementGetSources(InfoElement).end();
300}

302static unsigned getPHINumInputs(MachineInstr &PHI) {
assert(PHI.isPHI())(static_cast <bool> (PHI.isPHI()) ? void (0) : __assert_fail
 ("PHI.isPHI()", "/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp"
, 303, __extension__ __PRETTY_FUNCTION__));
return (PHI.getNumOperands() - 1) / 2;
305}

307static MachineBasicBlock *getPHIPred(MachineInstr &PHI, unsigned Index) {
assert(PHI.isPHI())(static_cast <bool> (PHI.isPHI()) ? void (0) : __assert_fail
 ("PHI.isPHI()", "/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp"
, 308, __extension__ __PRETTY_FUNCTION__));
return PHI.getOperand(Index * 2 + 2).getMBB();
310}

312static void setPhiPred(MachineInstr &PHI, unsigned Index,
                     MachineBasicBlock *NewPred) {
PHI.getOperand(Index * 2 + 2).setMBB(NewPred);
315}

317static unsigned getPHISourceReg(MachineInstr &PHI, unsigned Index) {
assert(PHI.isPHI())(static_cast <bool> (PHI.isPHI()) ? void (0) : __assert_fail
 ("PHI.isPHI()", "/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp"
, 318, __extension__ __PRETTY_FUNCTION__));
return PHI.getOperand(Index * 2 + 1).getReg();
320}

322static unsigned getPHIDestReg(MachineInstr &PHI) {
assert(PHI.isPHI())(static_cast <bool> (PHI.isPHI()) ? void (0) : __assert_fail
 ("PHI.isPHI()", "/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp"
, 323, __extension__ __PRETTY_FUNCTION__));
return PHI.getOperand(0).getReg();
325}

327namespace {

329class RegionMRT;
330class MBBMRT;

332class LinearizedRegion {
333protected:
MachineBasicBlock *Entry;
// The exit block is part of the region, and is the last
// merge block before exiting the region.
MachineBasicBlock *Exit;
DenseSet<unsigned> LiveOuts;
SmallPtrSet<MachineBasicBlock *, 1> MBBs;
bool HasLoop;
LinearizedRegion *Parent;
RegionMRT *RMRT;

void storeLiveOutReg(MachineBasicBlock *MBB, unsigned Reg,
                     MachineInstr *DefInstr, const MachineRegisterInfo *MRI,
                     const TargetRegisterInfo *TRI, PHILinearize &PHIInfo);

void storeLiveOutRegRegion(RegionMRT *Region, unsigned Reg,
                           MachineInstr *DefInstr,
                           const MachineRegisterInfo *MRI,
                           const TargetRegisterInfo *TRI,
                           PHILinearize &PHIInfo);

void storeMBBLiveOuts(MachineBasicBlock *MBB, const MachineRegisterInfo *MRI,
                      const TargetRegisterInfo *TRI, PHILinearize &PHIInfo,
                      RegionMRT *TopRegion);

void storeLiveOuts(MachineBasicBlock *MBB, const MachineRegisterInfo *MRI,
                   const TargetRegisterInfo *TRI, PHILinearize &PHIInfo);

void storeLiveOuts(RegionMRT *Region, const MachineRegisterInfo *MRI,
                   const TargetRegisterInfo *TRI, PHILinearize &PHIInfo,
                   RegionMRT *TopRegion = nullptr);

365public:
LinearizedRegion();
LinearizedRegion(MachineBasicBlock *MBB, const MachineRegisterInfo *MRI,
                 const TargetRegisterInfo *TRI, PHILinearize &PHIInfo);
~LinearizedRegion() = default;

void setRegionMRT(RegionMRT *Region) { RMRT = Region; }

RegionMRT *getRegionMRT() { return RMRT; }

void setParent(LinearizedRegion *P) { Parent = P; }

LinearizedRegion *getParent() { return Parent; }

void print(raw_ostream &OS, const TargetRegisterInfo *TRI = nullptr);

void setBBSelectRegIn(unsigned Reg);

unsigned getBBSelectRegIn();

void setBBSelectRegOut(unsigned Reg, bool IsLiveOut);

unsigned getBBSelectRegOut();

void setHasLoop(bool Value);

bool getHasLoop();

void addLiveOut(unsigned VReg);

void removeLiveOut(unsigned Reg);

void replaceLiveOut(unsigned OldReg, unsigned NewReg);

void replaceRegister(unsigned Register, unsigned NewRegister,
                     MachineRegisterInfo *MRI, bool ReplaceInside,
                     bool ReplaceOutside, bool IncludeLoopPHIs);

void replaceRegisterInsideRegion(unsigned Register, unsigned NewRegister,
                                 bool IncludeLoopPHIs,
                                 MachineRegisterInfo *MRI);

void replaceRegisterOutsideRegion(unsigned Register, unsigned NewRegister,
                                  bool IncludeLoopPHIs,
                                  MachineRegisterInfo *MRI);

DenseSet<unsigned> *getLiveOuts();

void setEntry(MachineBasicBlock *NewEntry);

MachineBasicBlock *getEntry();

void setExit(MachineBasicBlock *NewExit);

MachineBasicBlock *getExit();

void addMBB(MachineBasicBlock *MBB);

void addMBBs(LinearizedRegion *InnerRegion);

bool contains(MachineBasicBlock *MBB);

bool isLiveOut(unsigned Reg);

bool hasNoDef(unsigned Reg, MachineRegisterInfo *MRI);

void removeFalseRegisterKills(MachineRegisterInfo *MRI);

void initLiveOut(RegionMRT *Region, const MachineRegisterInfo *MRI,
                 const TargetRegisterInfo *TRI, PHILinearize &PHIInfo);
435};

437class MRT {
438protected:
RegionMRT *Parent;
unsigned BBSelectRegIn;
unsigned BBSelectRegOut;

443public:
virtual ~MRT() = default;

unsigned getBBSelectRegIn() { return BBSelectRegIn; }

unsigned getBBSelectRegOut() { return BBSelectRegOut; }

void setBBSelectRegIn(unsigned Reg) { BBSelectRegIn = Reg; }

void setBBSelectRegOut(unsigned Reg) { BBSelectRegOut = Reg; }

virtual RegionMRT *getRegionMRT() { return nullptr; }

virtual MBBMRT *getMBBMRT() { return nullptr; }

bool isRegion() { return getRegionMRT() != nullptr; }

bool isMBB() { return getMBBMRT() != nullptr; }

bool isRoot() { return Parent == nullptr; }

void setParent(RegionMRT *Region) { Parent = Region; }

RegionMRT *getParent() { return Parent; }

static MachineBasicBlock *
initializeMRT(MachineFunction &MF, const MachineRegionInfo *RegionInfo,
              DenseMap<MachineRegion *, RegionMRT *> &RegionMap);

static RegionMRT *buildMRT(MachineFunction &MF,
                           const MachineRegionInfo *RegionInfo,
                           const SIInstrInfo *TII,
                           MachineRegisterInfo *MRI);

virtual void dump(const TargetRegisterInfo *TRI, int depth = 0) = 0;

void dumpDepth(int depth) {
  for (int i = depth; i > 0; --i) {
    dbgs() << "  ";
  }
}
484};

486class MBBMRT : public MRT {
MachineBasicBlock *MBB;

489public:
MBBMRT(MachineBasicBlock *BB) : MBB(BB) {
  setParent(nullptr);
  setBBSelectRegOut(0);
  setBBSelectRegIn(0);
}

MBBMRT *getMBBMRT() override { return this; }

MachineBasicBlock *getMBB() { return MBB; }

void dump(const TargetRegisterInfo *TRI, int depth = 0) override {
  dumpDepth(depth);
  dbgs() << "MBB: " << getMBB()->getNumber();
  dbgs() << " In: " << printReg(getBBSelectRegIn(), TRI);
  dbgs() << ", Out: " << printReg(getBBSelectRegOut(), TRI) << "\n";
}
506};

508class RegionMRT : public MRT {
509protected:
MachineRegion *Region;
LinearizedRegion *LRegion = nullptr;
MachineBasicBlock *Succ = nullptr;
SetVector<MRT *> Children;

515public:
RegionMRT(MachineRegion *MachineRegion) : Region(MachineRegion) {
  setParent(nullptr);
  setBBSelectRegOut(0);
  setBBSelectRegIn(0);
}

~RegionMRT() override {
  if (LRegion) {
    delete LRegion;
  }

  for (auto CI : Children) {
    delete &(*CI);
  }
}

RegionMRT *getRegionMRT() override { return this; }

void setLinearizedRegion(LinearizedRegion *LinearizeRegion) {
  LRegion = LinearizeRegion;
}

LinearizedRegion *getLinearizedRegion() { return LRegion; }

MachineRegion *getMachineRegion() { return Region; }

unsigned getInnerOutputRegister() {
  return (*(Children.begin()))->getBBSelectRegOut();
}

void addChild(MRT *Tree) { Children.insert(Tree); }

SetVector<MRT *> *getChildren() { return &Children; }

void dump(const TargetRegisterInfo *TRI, int depth = 0) override {
  dumpDepth(depth);
  dbgs() << "Region: " << (void *)Region;
  dbgs() << " In: " << printReg(getBBSelectRegIn(), TRI);
  dbgs() << ", Out: " << printReg(getBBSelectRegOut(), TRI) << "\n";

  dumpDepth(depth);
  if (getSucc())
    dbgs() << "Succ: " << getSucc()->getNumber() << "\n";
  else
    dbgs() << "Succ: none \n";
  for (auto MRTI : Children) {
    MRTI->dump(TRI, depth + 1);
  }
}

MRT *getEntryTree() { return Children.back(); }

MRT *getExitTree() { return Children.front(); }

MachineBasicBlock *getEntry() {
  MRT *Tree = Children.back();
  return (Tree->isRegion()) ? Tree->getRegionMRT()->getEntry()
                            : Tree->getMBBMRT()->getMBB();
}

MachineBasicBlock *getExit() {
  MRT *Tree = Children.front();
  return (Tree->isRegion()) ? Tree->getRegionMRT()->getExit()
                            : Tree->getMBBMRT()->getMBB();
}

void setSucc(MachineBasicBlock *MBB) { Succ = MBB; }

MachineBasicBlock *getSucc() { return Succ; }

bool contains(MachineBasicBlock *MBB) {
  for (auto CI : Children) {
    if (CI->isMBB()) {
      if (MBB == CI->getMBBMRT()->getMBB()) {
        return true;
      }
    } else {
      if (CI->getRegionMRT()->contains(MBB)) {
        return true;
      } else if (CI->getRegionMRT()->getLinearizedRegion() != nullptr &&
                 CI->getRegionMRT()->getLinearizedRegion()->contains(MBB)) {
        return true;
      }
    }
  }
  return false;
}

void replaceLiveOutReg(unsigned Register, unsigned NewRegister) {
  LinearizedRegion *LRegion = getLinearizedRegion();
  LRegion->replaceLiveOut(Register, NewRegister);
  for (auto &CI : Children) {
    if (CI->isRegion()) {
      CI->getRegionMRT()->replaceLiveOutReg(Register, NewRegister);
    }
  }
}
613};

615} // end anonymous namespace

617static unsigned createBBSelectReg(const SIInstrInfo *TII,
                                MachineRegisterInfo *MRI) {
return MRI->createVirtualRegister(TII->getPreferredSelectRegClass(32));
620}

622MachineBasicBlock *
623MRT::initializeMRT(MachineFunction &MF, const MachineRegionInfo *RegionInfo,
                 DenseMap<MachineRegion *, RegionMRT *> &RegionMap) {
for (auto &MFI : MF) {
  MachineBasicBlock *ExitMBB = &MFI;
  if (ExitMBB->succ_size() == 0) {
    return ExitMBB;
  }
}
llvm_unreachable("CFG has no exit block")::llvm::llvm_unreachable_internal("CFG has no exit block", "/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp"
, 631);
return nullptr;
633}

635RegionMRT *MRT::buildMRT(MachineFunction &MF,
                       const MachineRegionInfo *RegionInfo,
                       const SIInstrInfo *TII, MachineRegisterInfo *MRI) {
SmallPtrSet<MachineRegion *, 4> PlacedRegions;
DenseMap<MachineRegion *, RegionMRT *> RegionMap;
MachineRegion *TopLevelRegion = RegionInfo->getTopLevelRegion();
RegionMRT *Result = new RegionMRT(TopLevelRegion);
RegionMap[TopLevelRegion] = Result;

// Insert the exit block first, we need it to be the merge node
// for the top level region.
MachineBasicBlock *Exit = initializeMRT(MF, RegionInfo, RegionMap);

unsigned BBSelectRegIn = createBBSelectReg(TII, MRI);
MBBMRT *ExitMRT = new MBBMRT(Exit);
RegionMap[RegionInfo->getRegionFor(Exit)]->addChild(ExitMRT);
ExitMRT->setBBSelectRegIn(BBSelectRegIn);

for (auto MBBI : post_order(&(MF.front()))) {
  MachineBasicBlock *MBB = &(*MBBI);

  // Skip Exit since we already added it
  if (MBB == Exit) {
    continue;
  }

  DEBUG(dbgs() << "Visiting " << printMBBReference(*MBB) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Visiting " <<
 printMBBReference(*MBB) << "\n"; } } while (false);
  MBBMRT *NewMBB = new MBBMRT(MBB);
  MachineRegion *Region = RegionInfo->getRegionFor(MBB);

  // Ensure we have the MRT region
  if (RegionMap.count(Region) == 0) {
    RegionMRT *NewMRTRegion = new RegionMRT(Region);
    RegionMap[Region] = NewMRTRegion;

    // Ensure all parents are in the RegionMap
    MachineRegion *Parent = Region->getParent();
    while (RegionMap.count(Parent) == 0) {
      RegionMRT *NewMRTParent = new RegionMRT(Parent);
      NewMRTParent->addChild(NewMRTRegion);
      NewMRTRegion->setParent(NewMRTParent);
      RegionMap[Parent] = NewMRTParent;
      NewMRTRegion = NewMRTParent;
      Parent = Parent->getParent();
    }
    RegionMap[Parent]->addChild(NewMRTRegion);
    NewMRTRegion->setParent(RegionMap[Parent]);
  }

  // Add MBB to Region MRT
  RegionMap[Region]->addChild(NewMBB);
  NewMBB->setParent(RegionMap[Region]);
  RegionMap[Region]->setSucc(Region->getExit());
}
return Result;
690}

692void LinearizedRegion::storeLiveOutReg(MachineBasicBlock *MBB, unsigned Reg,
                                     MachineInstr *DefInstr,
                                     const MachineRegisterInfo *MRI,
                                     const TargetRegisterInfo *TRI,
                                     PHILinearize &PHIInfo) {
if (TRI->isVirtualRegister(Reg)) {
  DEBUG(dbgs() << "Considering Register: " << printReg(Reg, TRI) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Considering Register: "
 << printReg(Reg, TRI) << "\n"; } } while (false);
  // If this is a source register to a PHI we are chaining, it
  // must be live out.
  if (PHIInfo.isSource(Reg)) {
    DEBUG(dbgs() << "Add LiveOut (PHI): " << printReg(Reg, TRI) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Add LiveOut (PHI): "
 << printReg(Reg, TRI) << "\n"; } } while (false);
    addLiveOut(Reg);
  } else {
    // If this is live out of the MBB
    for (auto &UI : MRI->use_operands(Reg)) {
      if (UI.getParent()->getParent() != MBB) {
        DEBUG(dbgs() << "Add LiveOut (MBB " << printMBBReference(*MBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Add LiveOut (MBB "
 << printMBBReference(*MBB) << "): " << printReg
(Reg, TRI) << "\n"; } } while (false)
                     << "): " << printReg(Reg, TRI) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Add LiveOut (MBB "
 << printMBBReference(*MBB) << "): " << printReg
(Reg, TRI) << "\n"; } } while (false);
        addLiveOut(Reg);
      } else {
        // If the use is in the same MBB we have to make sure
        // it is after the def, otherwise it is live out in a loop
        MachineInstr *UseInstr = UI.getParent();
        for (MachineBasicBlock::instr_iterator
                 MII = UseInstr->getIterator(),
                 MIE = UseInstr->getParent()->instr_end();
             MII != MIE; ++MII) {
          if ((&(*MII)) == DefInstr) {
            DEBUG(dbgs() << "Add LiveOut (Loop): " << printReg(Reg, TRI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Add LiveOut (Loop): "
 << printReg(Reg, TRI) << "\n"; } } while (false)
                         << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Add LiveOut (Loop): "
 << printReg(Reg, TRI) << "\n"; } } while (false);
            addLiveOut(Reg);
          }
        }
      }
    }
  }
}
729}

731void LinearizedRegion::storeLiveOutRegRegion(RegionMRT *Region, unsigned Reg,
                                           MachineInstr *DefInstr,
                                           const MachineRegisterInfo *MRI,
                                           const TargetRegisterInfo *TRI,
                                           PHILinearize &PHIInfo) {
if (TRI->isVirtualRegister(Reg)) {
  DEBUG(dbgs() << "Considering Register: " << printReg(Reg, TRI) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Considering Register: "
 << printReg(Reg, TRI) << "\n"; } } while (false);
  for (auto &UI : MRI->use_operands(Reg)) {
    if (!Region->contains(UI.getParent()->getParent())) {
      DEBUG(dbgs() << "Add LiveOut (Region " << (void *)Regiondo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Add LiveOut (Region "
 << (void *)Region << "): " << printReg(Reg
, TRI) << "\n"; } } while (false)
                   << "): " << printReg(Reg, TRI) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Add LiveOut (Region "
 << (void *)Region << "): " << printReg(Reg
, TRI) << "\n"; } } while (false);
      addLiveOut(Reg);
    }
  }
}
746}

748void LinearizedRegion::storeLiveOuts(MachineBasicBlock *MBB,
                                   const MachineRegisterInfo *MRI,
                                   const TargetRegisterInfo *TRI,
                                   PHILinearize &PHIInfo) {
DEBUG(dbgs() << "-Store Live Outs Begin (" << printMBBReference(*MBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "-Store Live Outs Begin ("
 << printMBBReference(*MBB) << ")-\n"; } } while (
false)
             << ")-\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "-Store Live Outs Begin ("
 << printMBBReference(*MBB) << ")-\n"; } } while (
false);
for (auto &II : *MBB) {
  for (auto &RI : II.defs()) {
    storeLiveOutReg(MBB, RI.getReg(), RI.getParent(), MRI, TRI, PHIInfo);
  }
  for (auto &IRI : II.implicit_operands()) {
    if (IRI.isDef()) {
      storeLiveOutReg(MBB, IRI.getReg(), IRI.getParent(), MRI, TRI, PHIInfo);
    }
  }
}

// If we have a successor with a PHI, source coming from this MBB we have to
// add the register as live out
for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
                                      E = MBB->succ_end();
     SI != E; ++SI) {
  for (auto &II : *(*SI)) {
    if (II.isPHI()) {
      MachineInstr &PHI = II;
      int numPreds = getPHINumInputs(PHI);
      for (int i = 0; i < numPreds; ++i) {
        if (getPHIPred(PHI, i) == MBB) {
          unsigned PHIReg = getPHISourceReg(PHI, i);
          DEBUG(dbgs() << "Add LiveOut (PhiSource " << printMBBReference(*MBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Add LiveOut (PhiSource "
 << printMBBReference(*MBB) << " -> " <<
 printMBBReference(*(*SI)) << "): " << printReg(PHIReg
, TRI) << "\n"; } } while (false)
                       << " -> " << printMBBReference(*(*SI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Add LiveOut (PhiSource "
 << printMBBReference(*MBB) << " -> " <<
 printMBBReference(*(*SI)) << "): " << printReg(PHIReg
, TRI) << "\n"; } } while (false)
                       << "): " << printReg(PHIReg, TRI) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Add LiveOut (PhiSource "
 << printMBBReference(*MBB) << " -> " <<
 printMBBReference(*(*SI)) << "): " << printReg(PHIReg
, TRI) << "\n"; } } while (false);
          addLiveOut(PHIReg);
        }
      }
    }
  }
}

DEBUG(dbgs() << "-Store Live Outs Endn-\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "-Store Live Outs Endn-\n"
; } } while (false);
788}

790void LinearizedRegion::storeMBBLiveOuts(MachineBasicBlock *MBB,
                                      const MachineRegisterInfo *MRI,
                                      const TargetRegisterInfo *TRI,
                                      PHILinearize &PHIInfo,
                                      RegionMRT *TopRegion) {
for (auto &II : *MBB) {
  for (auto &RI : II.defs()) {
    storeLiveOutRegRegion(TopRegion, RI.getReg(), RI.getParent(), MRI, TRI,
                          PHIInfo);
  }
  for (auto &IRI : II.implicit_operands()) {
    if (IRI.isDef()) {
      storeLiveOutRegRegion(TopRegion, IRI.getReg(), IRI.getParent(), MRI,
                            TRI, PHIInfo);
    }
  }
}
807}

809void LinearizedRegion::storeLiveOuts(RegionMRT *Region,
                                   const MachineRegisterInfo *MRI,
                                   const TargetRegisterInfo *TRI,
                                   PHILinearize &PHIInfo,
                                   RegionMRT *CurrentTopRegion) {
MachineBasicBlock *Exit = Region->getSucc();

RegionMRT *TopRegion =
    CurrentTopRegion == nullptr ? Region : CurrentTopRegion;

// Check if exit is end of function, if so, no live outs.
if (Exit == nullptr)
  return;

auto Children = Region->getChildren();
for (auto CI : *Children) {
  if (CI->isMBB()) {
    auto MBB = CI->getMBBMRT()->getMBB();
    storeMBBLiveOuts(MBB, MRI, TRI, PHIInfo, TopRegion);
  } else {
    LinearizedRegion *SubRegion = CI->getRegionMRT()->getLinearizedRegion();
    // We should be limited to only store registers that are live out from the
    // lineaized region
    for (auto MBBI : SubRegion->MBBs) {
      storeMBBLiveOuts(MBBI, MRI, TRI, PHIInfo, TopRegion);
    }
  }
}

if (CurrentTopRegion == nullptr) {
  auto Succ = Region->getSucc();
  for (auto &II : *Succ) {
    if (II.isPHI()) {
      MachineInstr &PHI = II;
      int numPreds = getPHINumInputs(PHI);
      for (int i = 0; i < numPreds; ++i) {
        if (Region->contains(getPHIPred(PHI, i))) {
          unsigned PHIReg = getPHISourceReg(PHI, i);
          DEBUG(dbgs() << "Add Region LiveOut (" << (void *)Regiondo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Add Region LiveOut ("
 << (void *)Region << "): " << printReg(PHIReg
, TRI) << "\n"; } } while (false)
                       << "): " << printReg(PHIReg, TRI) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Add Region LiveOut ("
 << (void *)Region << "): " << printReg(PHIReg
, TRI) << "\n"; } } while (false);
          addLiveOut(PHIReg);
        }
      }
    }
  }
}
855}

857#ifndef NDEBUG
858void LinearizedRegion::print(raw_ostream &OS, const TargetRegisterInfo *TRI) {
OS << "Linearized Region {";
bool IsFirst = true;
for (const auto &MBB : MBBs) {
  if (IsFirst) {
    IsFirst = false;
  } else {
    OS << " ,";
  }
  OS << MBB->getNumber();
}
OS << "} (" << Entry->getNumber() << ", "
   << (Exit == nullptr ? -1 : Exit->getNumber())
   << "): In:" << printReg(getBBSelectRegIn(), TRI)
   << " Out:" << printReg(getBBSelectRegOut(), TRI) << " {";
for (auto &LI : LiveOuts) {
  OS << printReg(LI, TRI) << " ";
}
OS << "} \n";
877}
878#endif

880unsigned LinearizedRegion::getBBSelectRegIn() {
return getRegionMRT()->getBBSelectRegIn();
882}

884unsigned LinearizedRegion::getBBSelectRegOut() {
return getRegionMRT()->getBBSelectRegOut();
886}

888void LinearizedRegion::setHasLoop(bool Value) { HasLoop = Value; }

890bool LinearizedRegion::getHasLoop() { return HasLoop; }

892void LinearizedRegion::addLiveOut(unsigned VReg) { LiveOuts.insert(VReg); }

894void LinearizedRegion::removeLiveOut(unsigned Reg) {
if (isLiveOut(Reg))
  LiveOuts.erase(Reg);
897}

899void LinearizedRegion::replaceLiveOut(unsigned OldReg, unsigned NewReg) {
if (isLiveOut(OldReg)) {
  removeLiveOut(OldReg);
  addLiveOut(NewReg);
}
904}

906void LinearizedRegion::replaceRegister(unsigned Register, unsigned NewRegister,
                                     MachineRegisterInfo *MRI,
                                     bool ReplaceInside, bool ReplaceOutside,
                                     bool IncludeLoopPHI) {
assert(Register != NewRegister && "Cannot replace a reg with itself")(static_cast <bool> (Register != NewRegister &&
 "Cannot replace a reg with itself") ? void (0) : __assert_fail
 ("Register != NewRegister && \"Cannot replace a reg with itself\""
, "/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp"
, 910, __extension__ __PRETTY_FUNCTION__));

DEBUG(dbgs() << "Pepareing to replace register (region): "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Pepareing to replace register (region): "
 << printReg(Register, MRI->getTargetRegisterInfo())
 << " with " << printReg(NewRegister, MRI->getTargetRegisterInfo
()) << "\n"; } } while (false)
             << printReg(Register, MRI->getTargetRegisterInfo()) << " with "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Pepareing to replace register (region): "
 << printReg(Register, MRI->getTargetRegisterInfo())
 << " with " << printReg(NewRegister, MRI->getTargetRegisterInfo
()) << "\n"; } } while (false)
             << printReg(NewRegister, MRI->getTargetRegisterInfo()) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Pepareing to replace register (region): "
 << printReg(Register, MRI->getTargetRegisterInfo())
 << " with " << printReg(NewRegister, MRI->getTargetRegisterInfo
()) << "\n"; } } while (false);

// If we are replacing outside, we also need to update the LiveOuts
if (ReplaceOutside &&
    (isLiveOut(Register) || this->getParent()->isLiveOut(Register))) {
  LinearizedRegion *Current = this;
  while (Current != nullptr && Current->getEntry() != nullptr) {
    DEBUG(dbgs() << "Region before register replace\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Region before register replace\n"
; } } while (false);
    DEBUG(Current->print(dbgs(), MRI->getTargetRegisterInfo()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { Current->print(dbgs(), MRI->
getTargetRegisterInfo()); } } while (false);
    Current->replaceLiveOut(Register, NewRegister);
    DEBUG(dbgs() << "Region after register replace\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Region after register replace\n"
; } } while (false);
    DEBUG(Current->print(dbgs(), MRI->getTargetRegisterInfo()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { Current->print(dbgs(), MRI->
getTargetRegisterInfo()); } } while (false);
    Current = Current->getParent();
  }
}

for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Register),
                                       E = MRI->reg_end();
     I != E;) {
  MachineOperand &O = *I;
  ++I;

  // We don't rewrite defs.
  if (O.isDef())
    continue;

  bool IsInside = contains(O.getParent()->getParent());
  bool IsLoopPHI = IsInside && (O.getParent()->isPHI() &&
                                O.getParent()->getParent() == getEntry());
  bool ShouldReplace = (IsInside && ReplaceInside) ||
                       (!IsInside && ReplaceOutside) ||
                       (IncludeLoopPHI && IsLoopPHI);
  if (ShouldReplace) {

    if (TargetRegisterInfo::isPhysicalRegister(NewRegister)) {
      DEBUG(dbgs() << "Trying to substitute physical register: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Trying to substitute physical register: "
 << printReg(NewRegister, MRI->getTargetRegisterInfo
()) << "\n"; } } while (false)
                   << printReg(NewRegister, MRI->getTargetRegisterInfo())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Trying to substitute physical register: "
 << printReg(NewRegister, MRI->getTargetRegisterInfo
()) << "\n"; } } while (false)
                   << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Trying to substitute physical register: "
 << printReg(NewRegister, MRI->getTargetRegisterInfo
()) << "\n"; } } while (false);
      llvm_unreachable("Cannot substitute physical registers")::llvm::llvm_unreachable_internal("Cannot substitute physical registers"
, "/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp"
, 952);
    } else {
      DEBUG(dbgs() << "Replacing register (region): "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Replacing register (region): "
 << printReg(Register, MRI->getTargetRegisterInfo())
 << " with " << printReg(NewRegister, MRI->getTargetRegisterInfo
()) << "\n"; } } while (false)
                   << printReg(Register, MRI->getTargetRegisterInfo())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Replacing register (region): "
 << printReg(Register, MRI->getTargetRegisterInfo())
 << " with " << printReg(NewRegister, MRI->getTargetRegisterInfo
()) << "\n"; } } while (false)
                   << " with "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Replacing register (region): "
 << printReg(Register, MRI->getTargetRegisterInfo())
 << " with " << printReg(NewRegister, MRI->getTargetRegisterInfo
()) << "\n"; } } while (false)
                   << printReg(NewRegister, MRI->getTargetRegisterInfo())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Replacing register (region): "
 << printReg(Register, MRI->getTargetRegisterInfo())
 << " with " << printReg(NewRegister, MRI->getTargetRegisterInfo
()) << "\n"; } } while (false)
                   << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Replacing register (region): "
 << printReg(Register, MRI->getTargetRegisterInfo())
 << " with " << printReg(NewRegister, MRI->getTargetRegisterInfo
()) << "\n"; } } while (false);
      O.setReg(NewRegister);
    }
  }
}
963}

965void LinearizedRegion::replaceRegisterInsideRegion(unsigned Register,
                                                 unsigned NewRegister,
                                                 bool IncludeLoopPHIs,
                                                 MachineRegisterInfo *MRI) {
replaceRegister(Register, NewRegister, MRI, true, false, IncludeLoopPHIs);
970}

972void LinearizedRegion::replaceRegisterOutsideRegion(unsigned Register,
                                                  unsigned NewRegister,
                                                  bool IncludeLoopPHIs,
                                                  MachineRegisterInfo *MRI) {
replaceRegister(Register, NewRegister, MRI, false, true, IncludeLoopPHIs);
977}

979DenseSet<unsigned> *LinearizedRegion::getLiveOuts() { return &LiveOuts; }

981void LinearizedRegion::setEntry(MachineBasicBlock *NewEntry) {
Entry = NewEntry;
983}

985MachineBasicBlock *LinearizedRegion::getEntry() { return Entry; }

987void LinearizedRegion::setExit(MachineBasicBlock *NewExit) { Exit = NewExit; }

989MachineBasicBlock *LinearizedRegion::getExit() { return Exit; }

991void LinearizedRegion::addMBB(MachineBasicBlock *MBB) { MBBs.insert(MBB); }

993void LinearizedRegion::addMBBs(LinearizedRegion *InnerRegion) {
for (const auto &MBB : InnerRegion->MBBs) {
  addMBB(MBB);
}
997}

999bool LinearizedRegion::contains(MachineBasicBlock *MBB) {
return MBBs.count(MBB) == 1;
1001}

1003bool LinearizedRegion::isLiveOut(unsigned Reg) {
return LiveOuts.count(Reg) == 1;
1005}

1007bool LinearizedRegion::hasNoDef(unsigned Reg, MachineRegisterInfo *MRI) {
return MRI->def_begin(Reg) == MRI->def_end();
1009}

1011// After the code has been structurized, what was flagged as kills
1012// before are no longer register kills.
1013void LinearizedRegion::removeFalseRegisterKills(MachineRegisterInfo *MRI) {
const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
for (auto MBBI : MBBs) {
  MachineBasicBlock *MBB = MBBI;
  for (auto &II : *MBB) {
    for (auto &RI : II.uses()) {
      if (RI.isReg()) {
        unsigned Reg = RI.getReg();
        if (TRI->isVirtualRegister(Reg)) {
          if (hasNoDef(Reg, MRI))
            continue;
          if (!MRI->hasOneDef(Reg)) {
            DEBUG(this->getEntry()->getParent()->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { this->getEntry()->getParent
()->dump(); } } while (false);
            DEBUG(dbgs() << printReg(Reg, TRI) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << printReg(Reg, TRI
) << "\n"; } } while (false);
          }

          if (MRI->def_begin(Reg) == MRI->def_end()) {
            DEBUG(dbgs() << "Register "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Register " <<
 printReg(Reg, MRI->getTargetRegisterInfo()) << " has NO defs\n"
; } } while (false)
                         << printReg(Reg, MRI->getTargetRegisterInfo())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Register " <<
 printReg(Reg, MRI->getTargetRegisterInfo()) << " has NO defs\n"
; } } while (false)
                         << " has NO defs\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Register " <<
 printReg(Reg, MRI->getTargetRegisterInfo()) << " has NO defs\n"
; } } while (false);
          } else if (!MRI->hasOneDef(Reg)) {
            DEBUG(dbgs() << "Register "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Register " <<
 printReg(Reg, MRI->getTargetRegisterInfo()) << " has multiple defs\n"
; } } while (false)
                         << printReg(Reg, MRI->getTargetRegisterInfo())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Register " <<
 printReg(Reg, MRI->getTargetRegisterInfo()) << " has multiple defs\n"
; } } while (false)
                         << " has multiple defs\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Register " <<
 printReg(Reg, MRI->getTargetRegisterInfo()) << " has multiple defs\n"
; } } while (false);
          }

          assert(MRI->hasOneDef(Reg) && "Register has multiple definitions")(static_cast <bool> (MRI->hasOneDef(Reg) && "Register has multiple definitions"
) ? void (0) : __assert_fail ("MRI->hasOneDef(Reg) && \"Register has multiple definitions\""
, "/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp"
, 1039, __extension__ __PRETTY_FUNCTION__));
          MachineOperand *Def = &(*(MRI->def_begin(Reg)));
          MachineOperand *UseOperand = &(RI);
          bool UseIsOutsideDefMBB = Def->getParent()->getParent() != MBB;
          if (UseIsOutsideDefMBB && UseOperand->isKill()) {
            DEBUG(dbgs() << "Removing kill flag on register: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Removing kill flag on register: "
 << printReg(Reg, TRI) << "\n"; } } while (false)
                         << printReg(Reg, TRI) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Removing kill flag on register: "
 << printReg(Reg, TRI) << "\n"; } } while (false);
            UseOperand->setIsKill(false);
          }
        }
      }
    }
  }
}
1053}

1055void LinearizedRegion::initLiveOut(RegionMRT *Region,
                                 const MachineRegisterInfo *MRI,
                                 const TargetRegisterInfo *TRI,
                                 PHILinearize &PHIInfo) {
storeLiveOuts(Region, MRI, TRI, PHIInfo);
1060}

1062LinearizedRegion::LinearizedRegion(MachineBasicBlock *MBB,
                                 const MachineRegisterInfo *MRI,
                                 const TargetRegisterInfo *TRI,
                                 PHILinearize &PHIInfo) {
setEntry(MBB);
setExit(MBB);
storeLiveOuts(MBB, MRI, TRI, PHIInfo);
MBBs.insert(MBB);
Parent = nullptr;
1071}

1073LinearizedRegion::LinearizedRegion() {
setEntry(nullptr);
setExit(nullptr);
Parent = nullptr;
1077}

1079namespace {

1081class AMDGPUMachineCFGStructurizer : public MachineFunctionPass {
1082private:
const MachineRegionInfo *Regions;
const SIInstrInfo *TII;
const TargetRegisterInfo *TRI;
MachineRegisterInfo *MRI;
unsigned BBSelectRegister;
PHILinearize PHIInfo;
DenseMap<MachineBasicBlock *, MachineBasicBlock *> FallthroughMap;
RegionMRT *RMRT;

void getPHIRegionIndices(RegionMRT *Region, MachineInstr &PHI,
                         SmallVector<unsigned, 2> &RegionIndices);
void getPHIRegionIndices(LinearizedRegion *Region, MachineInstr &PHI,
                         SmallVector<unsigned, 2> &RegionIndices);
void getPHINonRegionIndices(LinearizedRegion *Region, MachineInstr &PHI,
                            SmallVector<unsigned, 2> &PHINonRegionIndices);

void storePHILinearizationInfoDest(
    unsigned LDestReg, MachineInstr &PHI,
    SmallVector<unsigned, 2> *RegionIndices = nullptr);

unsigned storePHILinearizationInfo(MachineInstr &PHI,
                                   SmallVector<unsigned, 2> *RegionIndices);

void extractKilledPHIs(MachineBasicBlock *MBB);

bool shrinkPHI(MachineInstr &PHI, SmallVector<unsigned, 2> &PHIIndices,
               unsigned *ReplaceReg);

bool shrinkPHI(MachineInstr &PHI, unsigned CombinedSourceReg,
               MachineBasicBlock *SourceMBB,
               SmallVector<unsigned, 2> &PHIIndices, unsigned *ReplaceReg);

void replacePHI(MachineInstr &PHI, unsigned CombinedSourceReg,
                MachineBasicBlock *LastMerge,
                SmallVector<unsigned, 2> &PHIRegionIndices);
void replaceEntryPHI(MachineInstr &PHI, unsigned CombinedSourceReg,
                     MachineBasicBlock *IfMBB,
                     SmallVector<unsigned, 2> &PHIRegionIndices);
void replaceLiveOutRegs(MachineInstr &PHI,
                        SmallVector<unsigned, 2> &PHIRegionIndices,
                        unsigned CombinedSourceReg,
                        LinearizedRegion *LRegion);
void rewriteRegionExitPHI(RegionMRT *Region, MachineBasicBlock *LastMerge,
                          MachineInstr &PHI, LinearizedRegion *LRegion);

void rewriteRegionExitPHIs(RegionMRT *Region, MachineBasicBlock *LastMerge,
                           LinearizedRegion *LRegion);
void rewriteRegionEntryPHI(LinearizedRegion *Region, MachineBasicBlock *IfMBB,
                           MachineInstr &PHI);
void rewriteRegionEntryPHIs(LinearizedRegion *Region,
                            MachineBasicBlock *IfMBB);

bool regionIsSimpleIf(RegionMRT *Region);

void transformSimpleIfRegion(RegionMRT *Region);

void eliminateDeadBranchOperands(MachineBasicBlock::instr_iterator &II);

void insertUnconditionalBranch(MachineBasicBlock *MBB,
                               MachineBasicBlock *Dest,
                               const DebugLoc &DL = DebugLoc());

MachineBasicBlock *createLinearizedExitBlock(RegionMRT *Region);

void insertMergePHI(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB,
                    MachineBasicBlock *MergeBB, unsigned DestRegister,
                    unsigned IfSourceRegister, unsigned CodeSourceRegister,
                    bool IsUndefIfSource = false);

MachineBasicBlock *createIfBlock(MachineBasicBlock *MergeBB,
                                 MachineBasicBlock *CodeBBStart,
                                 MachineBasicBlock *CodeBBEnd,
                                 MachineBasicBlock *SelectBB, unsigned IfReg,
                                 bool InheritPreds);

void prunePHIInfo(MachineBasicBlock *MBB);
void createEntryPHI(LinearizedRegion *CurrentRegion, unsigned DestReg);

void createEntryPHIs(LinearizedRegion *CurrentRegion);
void resolvePHIInfos(MachineBasicBlock *FunctionEntry);

void replaceRegisterWith(unsigned Register, unsigned NewRegister);

MachineBasicBlock *createIfRegion(MachineBasicBlock *MergeBB,
                                  MachineBasicBlock *CodeBB,
                                  LinearizedRegion *LRegion,
                                  unsigned BBSelectRegIn,
                                  unsigned BBSelectRegOut);

MachineBasicBlock *
createIfRegion(MachineBasicBlock *MergeMBB, LinearizedRegion *InnerRegion,
               LinearizedRegion *CurrentRegion, MachineBasicBlock *SelectBB,
               unsigned BBSelectRegIn, unsigned BBSelectRegOut);
void ensureCondIsNotKilled(SmallVector<MachineOperand, 1> Cond);

void rewriteCodeBBTerminator(MachineBasicBlock *CodeBB,
                             MachineBasicBlock *MergeBB,
                             unsigned BBSelectReg);

MachineInstr *getDefInstr(unsigned Reg);
void insertChainedPHI(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB,
                      MachineBasicBlock *MergeBB,
                      LinearizedRegion *InnerRegion, unsigned DestReg,
                      unsigned SourceReg);
bool containsDef(MachineBasicBlock *MBB, LinearizedRegion *InnerRegion,
                 unsigned Register);
void rewriteLiveOutRegs(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB,
                        MachineBasicBlock *MergeBB,
                        LinearizedRegion *InnerRegion,
                        LinearizedRegion *LRegion);

void splitLoopPHI(MachineInstr &PHI, MachineBasicBlock *Entry,
                  MachineBasicBlock *EntrySucc, LinearizedRegion *LRegion);
void splitLoopPHIs(MachineBasicBlock *Entry, MachineBasicBlock *EntrySucc,
                   LinearizedRegion *LRegion);

MachineBasicBlock *splitExit(LinearizedRegion *LRegion);

MachineBasicBlock *splitEntry(LinearizedRegion *LRegion);

LinearizedRegion *initLinearizedRegion(RegionMRT *Region);

bool structurizeComplexRegion(RegionMRT *Region);

bool structurizeRegion(RegionMRT *Region);

bool structurizeRegions(RegionMRT *Region, bool isTopRegion);

1211public:
static char ID;

AMDGPUMachineCFGStructurizer() : MachineFunctionPass(ID) {
  initializeAMDGPUMachineCFGStructurizerPass(*PassRegistry::getPassRegistry());
}

void getAnalysisUsage(AnalysisUsage &AU) const override {
  AU.addRequired<MachineRegionInfoPass>();
  MachineFunctionPass::getAnalysisUsage(AU);
}

void initFallthroughMap(MachineFunction &MF);

void createLinearizedRegion(RegionMRT *Region, unsigned SelectOut);

unsigned initializeSelectRegisters(MRT *MRT, unsigned ExistingExitReg,
                                   MachineRegisterInfo *MRI,
                                   const SIInstrInfo *TII);

void setRegionMRT(RegionMRT *RegionTree) { RMRT = RegionTree; }

RegionMRT *getRegionMRT() { return RMRT; }

bool runOnMachineFunction(MachineFunction &MF) override;
1236};

1238} // end anonymous namespace

1240char AMDGPUMachineCFGStructurizer::ID = 0;

1242bool AMDGPUMachineCFGStructurizer::regionIsSimpleIf(RegionMRT *Region) {
MachineBasicBlock *Entry = Region->getEntry();
MachineBasicBlock *Succ = Region->getSucc();
bool FoundBypass = false;
bool FoundIf = false;

if (Entry->succ_size() != 2) {
  return false;
}

for (MachineBasicBlock::const_succ_iterator SI = Entry->succ_begin(),
                                            E = Entry->succ_end();
     SI != E; ++SI) {
  MachineBasicBlock *Current = *SI;

  if (Current == Succ) {
    FoundBypass = true;
  } else if ((Current->succ_size() == 1) &&
             *(Current->succ_begin()) == Succ) {
    FoundIf = true;
  }
}

return FoundIf && FoundBypass;
1266}

1268void AMDGPUMachineCFGStructurizer::transformSimpleIfRegion(RegionMRT *Region) {
MachineBasicBlock *Entry = Region->getEntry();
MachineBasicBlock *Exit = Region->getExit();
TII->convertNonUniformIfRegion(Entry, Exit);
1272}

1274static void fixMBBTerminator(MachineBasicBlock *MBB) {
if (MBB->succ_size() == 1) {
  auto *Succ = *(MBB->succ_begin());
  for (auto &TI : MBB->terminators()) {
    for (auto &UI : TI.uses()) {
      if (UI.isMBB() && UI.getMBB() != Succ) {
        UI.setMBB(Succ);
      }
    }
  }
}
1285}

1287static void fixRegionTerminator(RegionMRT *Region) {
MachineBasicBlock *InternalSucc = nullptr;
MachineBasicBlock *ExternalSucc = nullptr;
LinearizedRegion *LRegion = Region->getLinearizedRegion();
auto Exit = LRegion->getExit();

SmallPtrSet<MachineBasicBlock *, 2> Successors;
for (MachineBasicBlock::const_succ_iterator SI = Exit->succ_begin(),
                                            SE = Exit->succ_end();
     SI != SE; ++SI) {
  MachineBasicBlock *Succ = *SI;
  if (LRegion->contains(Succ)) {
    // Do not allow re-assign
    assert(InternalSucc == nullptr)(static_cast <bool> (InternalSucc == nullptr) ? void (0
) : __assert_fail ("InternalSucc == nullptr", "/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp"
, 1300, __extension__ __PRETTY_FUNCTION__));
    InternalSucc = Succ;
  } else {
    // Do not allow re-assign
    assert(ExternalSucc == nullptr)(static_cast <bool> (ExternalSucc == nullptr) ? void (0
) : __assert_fail ("ExternalSucc == nullptr", "/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp"
, 1304, __extension__ __PRETTY_FUNCTION__));
    ExternalSucc = Succ;
  }
}

for (auto &TI : Exit->terminators()) {
  for (auto &UI : TI.uses()) {
    if (UI.isMBB()) {
      auto Target = UI.getMBB();
      if (Target != InternalSucc && Target != ExternalSucc) {
        UI.setMBB(ExternalSucc);
      }
    }
  }
}
1319}

1321// If a region region is just a sequence of regions (and the exit
1322// block in the case of the top level region), we can simply skip
1323// linearizing it, because it is already linear
1324bool regionIsSequence(RegionMRT *Region) {
auto Children = Region->getChildren();
for (auto CI : *Children) {
  if (!CI->isRegion()) {
    if (CI->getMBBMRT()->getMBB()->succ_size() > 1) {
      return false;
    }
  }
}
return true;
1334}

1336void fixupRegionExits(RegionMRT *Region) {
auto Children = Region->getChildren();
for (auto CI : *Children) {
  if (!CI->isRegion()) {
    fixMBBTerminator(CI->getMBBMRT()->getMBB());
  } else {
    fixRegionTerminator(CI->getRegionMRT());
  }
}
1345}

1347void AMDGPUMachineCFGStructurizer::getPHIRegionIndices(
  RegionMRT *Region, MachineInstr &PHI,
  SmallVector<unsigned, 2> &PHIRegionIndices) {
unsigned NumInputs = getPHINumInputs(PHI);
for (unsigned i = 0; i < NumInputs; ++i) {
  MachineBasicBlock *Pred = getPHIPred(PHI, i);
  if (Region->contains(Pred)) {
    PHIRegionIndices.push_back(i);
  }
}
1357}

1359void AMDGPUMachineCFGStructurizer::getPHIRegionIndices(
  LinearizedRegion *Region, MachineInstr &PHI,
  SmallVector<unsigned, 2> &PHIRegionIndices) {
unsigned NumInputs = getPHINumInputs(PHI);
for (unsigned i = 0; i < NumInputs; ++i) {
  MachineBasicBlock *Pred = getPHIPred(PHI, i);
  if (Region->contains(Pred)) {
    PHIRegionIndices.push_back(i);
  }
}
1369}

1371void AMDGPUMachineCFGStructurizer::getPHINonRegionIndices(
  LinearizedRegion *Region, MachineInstr &PHI,
  SmallVector<unsigned, 2> &PHINonRegionIndices) {
unsigned NumInputs = getPHINumInputs(PHI);
for (unsigned i = 0; i < NumInputs; ++i) {
  MachineBasicBlock *Pred = getPHIPred(PHI, i);
  if (!Region->contains(Pred)) {
    PHINonRegionIndices.push_back(i);
  }
}
1381}

1383void AMDGPUMachineCFGStructurizer::storePHILinearizationInfoDest(
  unsigned LDestReg, MachineInstr &PHI,
  SmallVector<unsigned, 2> *RegionIndices) {
if (RegionIndices) {
  for (auto i : *RegionIndices) {
    PHIInfo.addSource(LDestReg, getPHISourceReg(PHI, i), getPHIPred(PHI, i));
  }
} else {
  unsigned NumInputs = getPHINumInputs(PHI);
  for (unsigned i = 0; i < NumInputs; ++i) {
    PHIInfo.addSource(LDestReg, getPHISourceReg(PHI, i), getPHIPred(PHI, i));
  }
}
1396}

1398unsigned AMDGPUMachineCFGStructurizer::storePHILinearizationInfo(
  MachineInstr &PHI, SmallVector<unsigned, 2> *RegionIndices) {
unsigned DestReg = getPHIDestReg(PHI);
unsigned LinearizeDestReg =
    MRI->createVirtualRegister(MRI->getRegClass(DestReg));
PHIInfo.addDest(LinearizeDestReg, PHI.getDebugLoc());
storePHILinearizationInfoDest(LinearizeDestReg, PHI, RegionIndices);
return LinearizeDestReg;
1406}

1408void AMDGPUMachineCFGStructurizer::extractKilledPHIs(MachineBasicBlock *MBB) {
// We need to create a new chain for the killed phi, but there is no
// need to do the renaming outside or inside the block.
SmallPtrSet<MachineInstr *, 2> PHIs;
for (MachineBasicBlock::instr_iterator I = MBB->instr_begin(),
                                       E = MBB->instr_end();
     I != E; ++I) {
  MachineInstr &Instr = *I;
  if (Instr.isPHI()) {
    unsigned PHIDestReg = getPHIDestReg(Instr);
    DEBUG(dbgs() << "Extractking killed phi:\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Extractking killed phi:\n"
; } } while (false);
    DEBUG(Instr.dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { Instr.dump(); } } while (false);
    PHIs.insert(&Instr);
    PHIInfo.addDest(PHIDestReg, Instr.getDebugLoc());
    storePHILinearizationInfoDest(PHIDestReg, Instr);
  }
}

for (auto PI : PHIs) {
  PI->eraseFromParent();
}
1429}

1431static bool isPHIRegionIndex(SmallVector<unsigned, 2> PHIRegionIndices,
                           unsigned Index) {
for (auto i : PHIRegionIndices) {
  if (i == Index)
    return true;
}
return false;
1438}

1440bool AMDGPUMachineCFGStructurizer::shrinkPHI(MachineInstr &PHI,
                                     SmallVector<unsigned, 2> &PHIIndices,
                                     unsigned *ReplaceReg) {
return shrinkPHI(PHI, 0, nullptr, PHIIndices, ReplaceReg);
1444}

1446bool AMDGPUMachineCFGStructurizer::shrinkPHI(MachineInstr &PHI,
                                     unsigned CombinedSourceReg,
                                     MachineBasicBlock *SourceMBB,
                                     SmallVector<unsigned, 2> &PHIIndices,
                                     unsigned *ReplaceReg) {
DEBUG(dbgs() << "Shrink PHI: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Shrink PHI: "; }
 } while (false);
DEBUG(PHI.dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { PHI.dump(); } } while (false);
DEBUG(dbgs() << " to " << printReg(getPHIDestReg(PHI), TRI) << " = PHI(")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << " to " << printReg
(getPHIDestReg(PHI), TRI) << " = PHI("; } } while (false
);

bool Replaced = false;
unsigned NumInputs = getPHINumInputs(PHI);
int SingleExternalEntryIndex = -1;
for (unsigned i = 0; i < NumInputs; ++i) {
  if (!isPHIRegionIndex(PHIIndices, i)) {
    if (SingleExternalEntryIndex == -1) {
      // Single entry
      SingleExternalEntryIndex = i;
    } else {
      // Multiple entries
      SingleExternalEntryIndex = -2;
    }
  }
}

if (SingleExternalEntryIndex > -1) {
  *ReplaceReg = getPHISourceReg(PHI, SingleExternalEntryIndex);
  // We should not rewrite the code, we should only pick up the single value
  // that represents the shrunk PHI.
  Replaced = true;
} else {
  MachineBasicBlock *MBB = PHI.getParent();
  MachineInstrBuilder MIB =
      BuildMI(*MBB, PHI, PHI.getDebugLoc(), TII->get(TargetOpcode::PHI),
              getPHIDestReg(PHI));
  if (SourceMBB) {
    MIB.addReg(CombinedSourceReg);
    MIB.addMBB(SourceMBB);
    DEBUG(dbgs() << printReg(CombinedSourceReg, TRI) << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << printReg(CombinedSourceReg
, TRI) << ", " << printMBBReference(*SourceMBB); }
 } while (false)
                 << printMBBReference(*SourceMBB))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << printReg(CombinedSourceReg
, TRI) << ", " << printMBBReference(*SourceMBB); }
 } while (false);
  }

  for (unsigned i = 0; i < NumInputs; ++i) {
    if (isPHIRegionIndex(PHIIndices, i)) {
      continue;
    }
    unsigned SourceReg = getPHISourceReg(PHI, i);
    MachineBasicBlock *SourcePred = getPHIPred(PHI, i);
    MIB.addReg(SourceReg);
    MIB.addMBB(SourcePred);
    DEBUG(dbgs() << printReg(SourceReg, TRI) << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << printReg(SourceReg
, TRI) << ", " << printMBBReference(*SourcePred);
 } } while (false)
                 << printMBBReference(*SourcePred))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << printReg(SourceReg
, TRI) << ", " << printMBBReference(*SourcePred);
 } } while (false);
  }
  DEBUG(dbgs() << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << ")\n"; } } while
 (false);
}
PHI.eraseFromParent();
return Replaced;
1502}

1504void AMDGPUMachineCFGStructurizer::replacePHI(
  MachineInstr &PHI, unsigned CombinedSourceReg, MachineBasicBlock *LastMerge,
  SmallVector<unsigned, 2> &PHIRegionIndices) {
DEBUG(dbgs() << "Replace PHI: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Replace PHI: ";
 } } while (false);
DEBUG(PHI.dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { PHI.dump(); } } while (false);
DEBUG(dbgs() << " with " << printReg(getPHIDestReg(PHI), TRI) << " = PHI(")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << " with " <<
 printReg(getPHIDestReg(PHI), TRI) << " = PHI("; } } while
 (false);

bool HasExternalEdge = false;
unsigned NumInputs = getPHINumInputs(PHI);
for (unsigned i = 0; i < NumInputs; ++i) {
  if (!isPHIRegionIndex(PHIRegionIndices, i)) {
    HasExternalEdge = true;
  }
}

if (HasExternalEdge) {
  MachineBasicBlock *MBB = PHI.getParent();
  MachineInstrBuilder MIB =
      BuildMI(*MBB, PHI, PHI.getDebugLoc(), TII->get(TargetOpcode::PHI),
              getPHIDestReg(PHI));
  MIB.addReg(CombinedSourceReg);
  MIB.addMBB(LastMerge);
  DEBUG(dbgs() << printReg(CombinedSourceReg, TRI) << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << printReg(CombinedSourceReg
, TRI) << ", " << printMBBReference(*LastMerge); }
 } while (false)
               << printMBBReference(*LastMerge))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << printReg(CombinedSourceReg
, TRI) << ", " << printMBBReference(*LastMerge); }
 } while (false);
  for (unsigned i = 0; i < NumInputs; ++i) {
    if (isPHIRegionIndex(PHIRegionIndices, i)) {
      continue;
    }
    unsigned SourceReg = getPHISourceReg(PHI, i);
    MachineBasicBlock *SourcePred = getPHIPred(PHI, i);
    MIB.addReg(SourceReg);
    MIB.addMBB(SourcePred);
    DEBUG(dbgs() << printReg(SourceReg, TRI) << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << printReg(SourceReg
, TRI) << ", " << printMBBReference(*SourcePred);
 } } while (false)
                 << printMBBReference(*SourcePred))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << printReg(SourceReg
, TRI) << ", " << printMBBReference(*SourcePred);
 } } while (false);
  }
  DEBUG(dbgs() << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << ")\n"; } } while
 (false);
} else {
  replaceRegisterWith(getPHIDestReg(PHI), CombinedSourceReg);
}
PHI.eraseFromParent();
1544}

1546void AMDGPUMachineCFGStructurizer::replaceEntryPHI(
  MachineInstr &PHI, unsigned CombinedSourceReg, MachineBasicBlock *IfMBB,
  SmallVector<unsigned, 2> &PHIRegionIndices) {
DEBUG(dbgs() << "Replace entry PHI: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Replace entry PHI: "
; } } while (false);
DEBUG(PHI.dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { PHI.dump(); } } while (false);
DEBUG(dbgs() << " with ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << " with "; } } while
 (false);

unsigned NumInputs = getPHINumInputs(PHI);
unsigned NumNonRegionInputs = NumInputs;
for (unsigned i = 0; i < NumInputs; ++i) {
  if (isPHIRegionIndex(PHIRegionIndices, i)) {
    NumNonRegionInputs--;
  }
}

if (NumNonRegionInputs == 0) {
  auto DestReg = getPHIDestReg(PHI);
  replaceRegisterWith(DestReg, CombinedSourceReg);
  DEBUG(dbgs() << " register " << printReg(CombinedSourceReg, TRI) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << " register " <<
 printReg(CombinedSourceReg, TRI) << "\n"; } } while (false
);
  PHI.eraseFromParent();
} else {
  DEBUG(dbgs() << printReg(getPHIDestReg(PHI), TRI) << " = PHI(")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << printReg(getPHIDestReg
(PHI), TRI) << " = PHI("; } } while (false);
  MachineBasicBlock *MBB = PHI.getParent();
  MachineInstrBuilder MIB =
      BuildMI(*MBB, PHI, PHI.getDebugLoc(), TII->get(TargetOpcode::PHI),
              getPHIDestReg(PHI));
  MIB.addReg(CombinedSourceReg);
  MIB.addMBB(IfMBB);
  DEBUG(dbgs() << printReg(CombinedSourceReg, TRI) << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << printReg(CombinedSourceReg
, TRI) << ", " << printMBBReference(*IfMBB); } } while
 (false)
               << printMBBReference(*IfMBB))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << printReg(CombinedSourceReg
, TRI) << ", " << printMBBReference(*IfMBB); } } while
 (false);
  unsigned NumInputs = getPHINumInputs(PHI);
  for (unsigned i = 0; i < NumInputs; ++i) {
    if (isPHIRegionIndex(PHIRegionIndices, i)) {
      continue;
    }
    unsigned SourceReg = getPHISourceReg(PHI, i);
    MachineBasicBlock *SourcePred = getPHIPred(PHI, i);
    MIB.addReg(SourceReg);
    MIB.addMBB(SourcePred);
    DEBUG(dbgs() << printReg(SourceReg, TRI) << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << printReg(SourceReg
, TRI) << ", " << printMBBReference(*SourcePred);
 } } while (false)
                 << printMBBReference(*SourcePred))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << printReg(SourceReg
, TRI) << ", " << printMBBReference(*SourcePred);
 } } while (false);
  }
  DEBUG(dbgs() << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << ")\n"; } } while
 (false);
  PHI.eraseFromParent();
}
1591}

1593void AMDGPUMachineCFGStructurizer::replaceLiveOutRegs(
  MachineInstr &PHI, SmallVector<unsigned, 2> &PHIRegionIndices,
  unsigned CombinedSourceReg, LinearizedRegion *LRegion) {
bool WasLiveOut = false;
for (auto PII : PHIRegionIndices) {
  unsigned Reg = getPHISourceReg(PHI, PII);
  if (LRegion->isLiveOut(Reg)) {
    bool IsDead = true;

    // Check if register is live out of the basic block
    MachineBasicBlock *DefMBB = getDefInstr(Reg)->getParent();
    for (auto UI = MRI->use_begin(Reg), E = MRI->use_end(); UI != E; ++UI) {
      if ((*UI).getParent()->getParent() != DefMBB) {
        IsDead = false;
      }
    }

    DEBUG(dbgs() << "Register " << printReg(Reg, TRI) << " is "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Register " <<
 printReg(Reg, TRI) << " is " << (IsDead ? "dead"
 : "alive") << " after PHI replace\n"; } } while (false
)
                 << (IsDead ? "dead" : "alive") << " after PHI replace\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Register " <<
 printReg(Reg, TRI) << " is " << (IsDead ? "dead"
 : "alive") << " after PHI replace\n"; } } while (false
);
    if (IsDead) {
      LRegion->removeLiveOut(Reg);
    }
    WasLiveOut = true;
  }
}

if (WasLiveOut)
  LRegion->addLiveOut(CombinedSourceReg);
1621}

1623void AMDGPUMachineCFGStructurizer::rewriteRegionExitPHI(RegionMRT *Region,
                                                MachineBasicBlock *LastMerge,
                                                MachineInstr &PHI,
                                                LinearizedRegion *LRegion) {
SmallVector<unsigned, 2> PHIRegionIndices;
getPHIRegionIndices(Region, PHI, PHIRegionIndices);
unsigned LinearizedSourceReg =
    storePHILinearizationInfo(PHI, &PHIRegionIndices);

replacePHI(PHI, LinearizedSourceReg, LastMerge, PHIRegionIndices);
replaceLiveOutRegs(PHI, PHIRegionIndices, LinearizedSourceReg, LRegion);
1634}

1636void AMDGPUMachineCFGStructurizer::rewriteRegionEntryPHI(LinearizedRegion *Region,
                                                 MachineBasicBlock *IfMBB,
                                                 MachineInstr &PHI) {
SmallVector<unsigned, 2> PHINonRegionIndices;
getPHINonRegionIndices(Region, PHI, PHINonRegionIndices);
unsigned LinearizedSourceReg =
    storePHILinearizationInfo(PHI, &PHINonRegionIndices);
replaceEntryPHI(PHI, LinearizedSourceReg, IfMBB, PHINonRegionIndices);
1644}

1646static void collectPHIs(MachineBasicBlock *MBB,
                      SmallVector<MachineInstr *, 2> &PHIs) {
for (auto &BBI : *MBB) {
  if (BBI.isPHI()) {
    PHIs.push_back(&BBI);
  }
}
1653}

1655void AMDGPUMachineCFGStructurizer::rewriteRegionExitPHIs(RegionMRT *Region,
                                                 MachineBasicBlock *LastMerge,
                                                 LinearizedRegion *LRegion) {
SmallVector<MachineInstr *, 2> PHIs;
auto Exit = Region->getSucc();
if (Exit == nullptr)
  return;

collectPHIs(Exit, PHIs);

for (auto PHII : PHIs) {
  rewriteRegionExitPHI(Region, LastMerge, *PHII, LRegion);
}
1668}

1670void AMDGPUMachineCFGStructurizer::rewriteRegionEntryPHIs(LinearizedRegion *Region,
                                                  MachineBasicBlock *IfMBB) {
SmallVector<MachineInstr *, 2> PHIs;
auto Entry = Region->getEntry();

collectPHIs(Entry, PHIs);

for (auto PHII : PHIs) {
  rewriteRegionEntryPHI(Region, IfMBB, *PHII);
}
1680}

1682void AMDGPUMachineCFGStructurizer::insertUnconditionalBranch(MachineBasicBlock *MBB,
                                                     MachineBasicBlock *Dest,
                                                     const DebugLoc &DL) {
DEBUG(dbgs() << "Inserting unconditional branch: " << MBB->getNumber()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Inserting unconditional branch: "
 << MBB->getNumber() << " -> " << Dest
->getNumber() << "\n"; } } while (false)
             << " -> " << Dest->getNumber() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Inserting unconditional branch: "
 << MBB->getNumber() << " -> " << Dest
->getNumber() << "\n"; } } while (false);
MachineBasicBlock::instr_iterator Terminator = MBB->getFirstInstrTerminator();
bool HasTerminator = Terminator != MBB->instr_end();
if (HasTerminator) {
  TII->ReplaceTailWithBranchTo(Terminator, Dest);
}
if (++MachineFunction::iterator(MBB) != MachineFunction::iterator(Dest)) {
  TII->insertUnconditionalBranch(*MBB, Dest, DL);
}
1695}

1697static MachineBasicBlock *getSingleExitNode(MachineFunction &MF) {
MachineBasicBlock *result = nullptr;
for (auto &MFI : MF) {
  if (MFI.succ_size() == 0) {
    if (result == nullptr) {
      result = &MFI;
    } else {
      return nullptr;
    }
  }
}

return result;
1710}

1712static bool hasOneExitNode(MachineFunction &MF) {
return getSingleExitNode(MF) != nullptr;
1714}

1716MachineBasicBlock *
1717AMDGPUMachineCFGStructurizer::createLinearizedExitBlock(RegionMRT *Region) {
auto Exit = Region->getSucc();

// If the exit is the end of the function, we just use the existing
MachineFunction *MF = Region->getEntry()->getParent();
if (Exit == nullptr && hasOneExitNode(*MF)) {
  return &(*(--(Region->getEntry()->getParent()->end())));
}

MachineBasicBlock *LastMerge = MF->CreateMachineBasicBlock();
if (Exit == nullptr) {
  MachineFunction::iterator ExitIter = MF->end();
  MF->insert(ExitIter, LastMerge);
} else {
  MachineFunction::iterator ExitIter = Exit->getIterator();
  MF->insert(ExitIter, LastMerge);
  LastMerge->addSuccessor(Exit);
  insertUnconditionalBranch(LastMerge, Exit);
  DEBUG(dbgs() << "Created exit block: " << LastMerge->getNumber() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Created exit block: "
 << LastMerge->getNumber() << "\n"; } } while (
false);
}
return LastMerge;
1738}

1740void AMDGPUMachineCFGStructurizer::insertMergePHI(MachineBasicBlock *IfBB,
                                          MachineBasicBlock *CodeBB,
                                          MachineBasicBlock *MergeBB,
                                          unsigned DestRegister,
                                          unsigned IfSourceRegister,
                                          unsigned CodeSourceRegister,
                                          bool IsUndefIfSource) {
// If this is the function exit block, we don't need a phi.
if (MergeBB->succ_begin() == MergeBB->succ_end()) {
  return;
}
DEBUG(dbgs() << "Merge PHI (" << printMBBReference(*MergeBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Merge PHI (" <<
 printMBBReference(*MergeBB) << "): " << printReg
(DestRegister, TRI) << " = PHI(" << printReg(IfSourceRegister
, TRI) << ", " << printMBBReference(*IfBB) <<
 printReg(CodeSourceRegister, TRI) << ", " << printMBBReference
(*CodeBB) << ")\n"; } } while (false)
             << "): " << printReg(DestRegister, TRI) << " = PHI("do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Merge PHI (" <<
 printMBBReference(*MergeBB) << "): " << printReg
(DestRegister, TRI) << " = PHI(" << printReg(IfSourceRegister
, TRI) << ", " << printMBBReference(*IfBB) <<
 printReg(CodeSourceRegister, TRI) << ", " << printMBBReference
(*CodeBB) << ")\n"; } } while (false)
             << printReg(IfSourceRegister, TRI) << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Merge PHI (" <<
 printMBBReference(*MergeBB) << "): " << printReg
(DestRegister, TRI) << " = PHI(" << printReg(IfSourceRegister
, TRI) << ", " << printMBBReference(*IfBB) <<
 printReg(CodeSourceRegister, TRI) << ", " << printMBBReference
(*CodeBB) << ")\n"; } } while (false)
             << printMBBReference(*IfBB) << printReg(CodeSourceRegister, TRI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Merge PHI (" <<
 printMBBReference(*MergeBB) << "): " << printReg
(DestRegister, TRI) << " = PHI(" << printReg(IfSourceRegister
, TRI) << ", " << printMBBReference(*IfBB) <<
 printReg(CodeSourceRegister, TRI) << ", " << printMBBReference
(*CodeBB) << ")\n"; } } while (false)
             << ", " << printMBBReference(*CodeBB) << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Merge PHI (" <<
 printMBBReference(*MergeBB) << "): " << printReg
(DestRegister, TRI) << " = PHI(" << printReg(IfSourceRegister
, TRI) << ", " << printMBBReference(*IfBB) <<
 printReg(CodeSourceRegister, TRI) << ", " << printMBBReference
(*CodeBB) << ")\n"; } } while (false);
const DebugLoc &DL = MergeBB->findDebugLoc(MergeBB->begin());
MachineInstrBuilder MIB = BuildMI(*MergeBB, MergeBB->instr_begin(), DL,
                                  TII->get(TargetOpcode::PHI), DestRegister);
if (IsUndefIfSource && false) {
  MIB.addReg(IfSourceRegister, RegState::Undef);
} else {
  MIB.addReg(IfSourceRegister);
}
MIB.addMBB(IfBB);
MIB.addReg(CodeSourceRegister);
MIB.addMBB(CodeBB);
1767}

1769static void removeExternalCFGSuccessors(MachineBasicBlock *MBB) {
for (MachineBasicBlock::succ_iterator PI = MBB->succ_begin(),
                                      E = MBB->succ_end();
     PI != E; ++PI) {
  if ((*PI) != MBB) {
    (MBB)->removeSuccessor(*PI);
  }
}
1777}

1779static void removeExternalCFGEdges(MachineBasicBlock *StartMBB,
                                 MachineBasicBlock *EndMBB) {

// We have to check against the StartMBB successor becasuse a
// structurized region with a loop will have the entry block split,
// and the backedge will go to the entry successor.
DenseSet<std::pair<MachineBasicBlock *, MachineBasicBlock *>> Succs;
unsigned SuccSize = StartMBB->succ_size();
if (SuccSize > 0) {
  MachineBasicBlock *StartMBBSucc = *(StartMBB->succ_begin());
  for (MachineBasicBlock::succ_iterator PI = EndMBB->succ_begin(),
                                        E = EndMBB->succ_end();
       PI != E; ++PI) {
    // Either we have a back-edge to the entry block, or a back-edge to the
    // successor of the entry block since the block may be split.
    if ((*PI) != StartMBB &&
        !((*PI) == StartMBBSucc && StartMBB != EndMBB && SuccSize == 1)) {
      Succs.insert(
          std::pair<MachineBasicBlock *, MachineBasicBlock *>(EndMBB, *PI));
    }
  }
}

for (MachineBasicBlock::pred_iterator PI = StartMBB->pred_begin(),
                                      E = StartMBB->pred_end();
     PI != E; ++PI) {
  if ((*PI) != EndMBB) {
    Succs.insert(
        std::pair<MachineBasicBlock *, MachineBasicBlock *>(*PI, StartMBB));
  }
}

for (auto SI : Succs) {
  std::pair<MachineBasicBlock *, MachineBasicBlock *> Edge = SI;
  DEBUG(dbgs() << "Removing edge: " << printMBBReference(*Edge.first)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Removing edge: "
 << printMBBReference(*Edge.first) << " -> " <<
 printMBBReference(*Edge.second) << "\n"; } } while (false
)
               << " -> " << printMBBReference(*Edge.second) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Removing edge: "
 << printMBBReference(*Edge.first) << " -> " <<
 printMBBReference(*Edge.second) << "\n"; } } while (false
);
  Edge.first->removeSuccessor(Edge.second);
}
1817}

1819MachineBasicBlock *AMDGPUMachineCFGStructurizer::createIfBlock(
  MachineBasicBlock *MergeBB, MachineBasicBlock *CodeBBStart,
  MachineBasicBlock *CodeBBEnd, MachineBasicBlock *SelectBB, unsigned IfReg,
  bool InheritPreds) {
MachineFunction *MF = MergeBB->getParent();
MachineBasicBlock *IfBB = MF->CreateMachineBasicBlock();

if (InheritPreds) {
  for (MachineBasicBlock::pred_iterator PI = CodeBBStart->pred_begin(),
                                        E = CodeBBStart->pred_end();
       PI != E; ++PI) {
    if ((*PI) != CodeBBEnd) {
      MachineBasicBlock *Pred = (*PI);
      Pred->addSuccessor(IfBB);
    }
  }
}

removeExternalCFGEdges(CodeBBStart, CodeBBEnd);

auto CodeBBStartI = CodeBBStart->getIterator();
auto CodeBBEndI = CodeBBEnd->getIterator();
auto MergeIter = MergeBB->getIterator();
MF->insert(MergeIter, IfBB);
MF->splice(MergeIter, CodeBBStartI, ++CodeBBEndI);
IfBB->addSuccessor(MergeBB);
IfBB->addSuccessor(CodeBBStart);

DEBUG(dbgs() << "Created If block: " << IfBB->getNumber() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Created If block: "
 << IfBB->getNumber() << "\n"; } } while (false
);
// Ensure that the MergeBB is a successor of the CodeEndBB.
if (!CodeBBEnd->isSuccessor(MergeBB))
  CodeBBEnd->addSuccessor(MergeBB);

DEBUG(dbgs() << "Moved " << printMBBReference(*CodeBBStart) << " through "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Moved " <<
 printMBBReference(*CodeBBStart) << " through " <<
 printMBBReference(*CodeBBEnd) << "\n"; } } while (false
)
             << printMBBReference(*CodeBBEnd) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Moved " <<
 printMBBReference(*CodeBBStart) << " through " <<
 printMBBReference(*CodeBBEnd) << "\n"; } } while (false
);

// If we have a single predecessor we can find a reasonable debug location
MachineBasicBlock *SinglePred =
    CodeBBStart->pred_size() == 1 ? *(CodeBBStart->pred_begin()) : nullptr;
const DebugLoc &DL = SinglePred
                  ? SinglePred->findDebugLoc(SinglePred->getFirstTerminator())
                  : DebugLoc();

unsigned Reg =
    TII->insertEQ(IfBB, IfBB->begin(), DL, IfReg,
                  SelectBB->getNumber() /* CodeBBStart->getNumber() */);
if (&(*(IfBB->getParent()->begin())) == IfBB) {
  TII->materializeImmediate(*IfBB, IfBB->begin(), DL, IfReg,
                            CodeBBStart->getNumber());
}
MachineOperand RegOp = MachineOperand::CreateReg(Reg, false, false, true);
ArrayRef<MachineOperand> Cond(RegOp);
TII->insertBranch(*IfBB, MergeBB, CodeBBStart, Cond, DL);

return IfBB;
1874}

1876void AMDGPUMachineCFGStructurizer::ensureCondIsNotKilled(
  SmallVector<MachineOperand, 1> Cond) {
if (Cond.size() != 1)
  return;
if (!Cond[0].isReg())
  return;

unsigned CondReg = Cond[0].getReg();
for (auto UI = MRI->use_begin(CondReg), E = MRI->use_end(); UI != E; ++UI) {
  (*UI).setIsKill(false);
}
1887}

1889void AMDGPUMachineCFGStructurizer::rewriteCodeBBTerminator(MachineBasicBlock *CodeBB,
                                                   MachineBasicBlock *MergeBB,
                                                   unsigned BBSelectReg) {
MachineBasicBlock *TrueBB = nullptr;
MachineBasicBlock *FalseBB = nullptr;
SmallVector<MachineOperand, 1> Cond;
MachineBasicBlock *FallthroughBB = FallthroughMap[CodeBB];
TII->analyzeBranch(*CodeBB, TrueBB, FalseBB, Cond);

const DebugLoc &DL = CodeBB->findDebugLoc(CodeBB->getFirstTerminator());

if (FalseBB == nullptr && TrueBB == nullptr && FallthroughBB == nullptr) {
  // This is an exit block, hence no successors. We will assign the
  // bb select register to the entry block.
  TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
                            BBSelectReg,
                            CodeBB->getParent()->begin()->getNumber());
  insertUnconditionalBranch(CodeBB, MergeBB, DL);
  return;
}

if (FalseBB == nullptr && TrueBB == nullptr) {
  TrueBB = FallthroughBB;
} else if (TrueBB != nullptr) {
  FalseBB =
      (FallthroughBB && (FallthroughBB != TrueBB)) ? FallthroughBB : FalseBB;
}

if ((TrueBB != nullptr && FalseBB == nullptr) || (TrueBB == FalseBB)) {
  TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
                            BBSelectReg, TrueBB->getNumber());
} else {
  const TargetRegisterClass *RegClass = MRI->getRegClass(BBSelectReg);
  unsigned TrueBBReg = MRI->createVirtualRegister(RegClass);
  unsigned FalseBBReg = MRI->createVirtualRegister(RegClass);
  TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
                            TrueBBReg, TrueBB->getNumber());
  TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
                            FalseBBReg, FalseBB->getNumber());
  ensureCondIsNotKilled(Cond);
  TII->insertVectorSelect(*CodeBB, CodeBB->getFirstTerminator(), DL,
                          BBSelectReg, Cond, TrueBBReg, FalseBBReg);
}

insertUnconditionalBranch(CodeBB, MergeBB, DL);
1934}

1936MachineInstr *AMDGPUMachineCFGStructurizer::getDefInstr(unsigned Reg) {
if (MRI->def_begin(Reg) == MRI->def_end()) {
  DEBUG(dbgs() << "Register " << printReg(Reg, MRI->getTargetRegisterInfo())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Register " <<
 printReg(Reg, MRI->getTargetRegisterInfo()) << " has NO defs\n"
; } } while (false)
               << " has NO defs\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Register " <<
 printReg(Reg, MRI->getTargetRegisterInfo()) << " has NO defs\n"
; } } while (false);
} else if (!MRI->hasOneDef(Reg)) {
  DEBUG(dbgs() << "Register " << printReg(Reg, MRI->getTargetRegisterInfo())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Register " <<
 printReg(Reg, MRI->getTargetRegisterInfo()) << " has multiple defs\n"
; } } while (false)
               << " has multiple defs\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Register " <<
 printReg(Reg, MRI->getTargetRegisterInfo()) << " has multiple defs\n"
; } } while (false);
  DEBUG(dbgs() << "DEFS BEGIN:\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "DEFS BEGIN:\n";
 } } while (false);
  for (auto DI = MRI->def_begin(Reg), DE = MRI->def_end(); DI != DE; ++DI) {
    DEBUG(DI->getParent()->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { DI->getParent()->dump(); }
 } while (false);
  }
  DEBUG(dbgs() << "DEFS END\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "DEFS END\n"; } }
 while (false);
}

assert(MRI->hasOneDef(Reg) && "Register has multiple definitions")(static_cast <bool> (MRI->hasOneDef(Reg) && "Register has multiple definitions"
) ? void (0) : __assert_fail ("MRI->hasOneDef(Reg) && \"Register has multiple definitions\""
, "/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp"
, 1950, __extension__ __PRETTY_FUNCTION__));
return (*(MRI->def_begin(Reg))).getParent();
1952}

1954void AMDGPUMachineCFGStructurizer::insertChainedPHI(MachineBasicBlock *IfBB,
                                            MachineBasicBlock *CodeBB,
                                            MachineBasicBlock *MergeBB,
                                            LinearizedRegion *InnerRegion,
                                            unsigned DestReg,
                                            unsigned SourceReg) {
// In this function we know we are part of a chain already, so we need
// to add the registers to the existing chain, and rename the register
// inside the region.
bool IsSingleBB = InnerRegion->getEntry() == InnerRegion->getExit();
MachineInstr *DefInstr = getDefInstr(SourceReg);
if (DefInstr->isPHI() && DefInstr->getParent() == CodeBB && IsSingleBB) {
  // Handle the case where the def is a PHI-def inside a basic
  // block, then we only need to do renaming. Special care needs to
  // be taken if the PHI-def is part of an existing chain, or if a
  // new one needs to be created.
  InnerRegion->replaceRegisterInsideRegion(SourceReg, DestReg, true, MRI);

  // We collect all PHI Information, and if we are at the region entry,
  // all PHIs will be removed, and then re-introduced if needed.
  storePHILinearizationInfoDest(DestReg, *DefInstr);
  // We have picked up all the information we need now and can remove
  // the PHI
  PHIInfo.removeSource(DestReg, SourceReg, CodeBB);
  DefInstr->eraseFromParent();
} else {
  // If this is not a phi-def, or it is a phi-def but from a linearized region
  if (IsSingleBB && DefInstr->getParent() == InnerRegion->getEntry()) {
    // If this is a single BB and the definition is in this block we
    // need to replace any uses outside the region.
    InnerRegion->replaceRegisterOutsideRegion(SourceReg, DestReg, false, MRI);
  }
  const TargetRegisterClass *RegClass = MRI->getRegClass(DestReg);
  unsigned NextDestReg = MRI->createVirtualRegister(RegClass);
  bool IsLastDef = PHIInfo.getNumSources(DestReg) == 1;
  DEBUG(dbgs() << "Insert Chained PHI\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Insert Chained PHI\n"
; } } while (false);
  insertMergePHI(IfBB, InnerRegion->getExit(), MergeBB, DestReg, NextDestReg,
                 SourceReg, IsLastDef);

  PHIInfo.removeSource(DestReg, SourceReg, CodeBB);
  if (IsLastDef) {
    const DebugLoc &DL = IfBB->findDebugLoc(IfBB->getFirstTerminator());
    TII->materializeImmediate(*IfBB, IfBB->getFirstTerminator(), DL,
                              NextDestReg, 0);
    PHIInfo.deleteDef(DestReg);
  } else {
    PHIInfo.replaceDef(DestReg, NextDestReg);
  }
}
2003}

2005bool AMDGPUMachineCFGStructurizer::containsDef(MachineBasicBlock *MBB,
                                       LinearizedRegion *InnerRegion,
                                       unsigned Register) {
return getDefInstr(Register)->getParent() == MBB ||
       InnerRegion->contains(getDefInstr(Register)->getParent());
2010}

2012void AMDGPUMachineCFGStructurizer::rewriteLiveOutRegs(MachineBasicBlock *IfBB,
                                              MachineBasicBlock *CodeBB,
                                              MachineBasicBlock *MergeBB,
                                              LinearizedRegion *InnerRegion,
                                              LinearizedRegion *LRegion) {
DenseSet<unsigned> *LiveOuts = InnerRegion->getLiveOuts();
SmallVector<unsigned, 4> OldLiveOuts;
bool IsSingleBB = InnerRegion->getEntry() == InnerRegion->getExit();
4
←
Assuming the condition is false→
for (auto OLI : *LiveOuts) {
  OldLiveOuts.push_back(OLI);
}

for (auto LI : OldLiveOuts) {
5
←
Assuming '__begin1' is equal to '__end1'→
  DEBUG(dbgs() << "LiveOut: " << printReg(LI, TRI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "LiveOut: " <<
 printReg(LI, TRI); } } while (false);
  if (!containsDef(CodeBB, InnerRegion, LI) ||
      (!IsSingleBB && (getDefInstr(LI)->getParent() == LRegion->getExit()))) {
    // If the register simly lives through the CodeBB, we don't have
    // to rewrite anything since the register is not defined in this
    // part of the code.
    DEBUG(dbgs() << "- through")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "- through"; } }
 while (false);
    continue;
  }
  DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "\n"; } } while (
false);
  unsigned Reg = LI;
  if (/*!PHIInfo.isSource(Reg) &&*/ Reg != InnerRegion->getBBSelectRegOut()) {
    // If the register is live out, we do want to create a phi,
    // unless it is from the Exit block, becasuse in that case there
    // is already a PHI, and no need to create a new one.

    // If the register is just a live out def and not part of a phi
    // chain, we need to create a PHI node to handle the if region,
    // and replace all uses outside of the region with the new dest
    // register, unless it is the outgoing BB select register. We have
    // already creaed phi nodes for these.
    const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
    unsigned PHIDestReg = MRI->createVirtualRegister(RegClass);
    unsigned IfSourceReg = MRI->createVirtualRegister(RegClass);
    // Create initializer, this value is never used, but is needed
    // to satisfy SSA.
    DEBUG(dbgs() << "Initializer for reg: " << printReg(Reg) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Initializer for reg: "
 << printReg(Reg) << "\n"; } } while (false);
    TII->materializeImmediate(*IfBB, IfBB->getFirstTerminator(), DebugLoc(),
                      IfSourceReg, 0);

    InnerRegion->replaceRegisterOutsideRegion(Reg, PHIDestReg, true, MRI);
    DEBUG(dbgs() << "Insert Non-Chained Live out PHI\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Insert Non-Chained Live out PHI\n"
; } } while (false);
    insertMergePHI(IfBB, InnerRegion->getExit(), MergeBB, PHIDestReg,
                   IfSourceReg, Reg, true);
  }
}

// Handle the chained definitions in PHIInfo, checking if this basic block
// is a source block for a definition.
SmallVector<unsigned, 4> Sources;
if (PHIInfo.findSourcesFromMBB(CodeBB, Sources)) {
6
←
Assuming the condition is true→
7
←
Taking true branch→
  DEBUG(dbgs() << "Inserting PHI Live Out from " << printMBBReference(*CodeBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Inserting PHI Live Out from "
 << printMBBReference(*CodeBB) << "\n"; } } while
 (false)
               << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Inserting PHI Live Out from "
 << printMBBReference(*CodeBB) << "\n"; } } while
 (false);
  for (auto SI : Sources) {
8
←
Assuming '__begin2' is not equal to '__end2'→
    unsigned DestReg;
9
←
'DestReg' declared without an initial value→
    PHIInfo.findDest(SI, CodeBB, DestReg);
10
←
Calling 'PHILinearize::findDest'→
14
←
Returning from 'PHILinearize::findDest'→
    insertChainedPHI(IfBB, CodeBB, MergeBB, InnerRegion, DestReg, SI);
15
←
5th function call argument is an uninitialized value
  }
  DEBUG(dbgs() << "Insertion done.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Insertion done.\n"
; } } while (false);
}

DEBUG(PHIInfo.dump(MRI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { PHIInfo.dump(MRI); } } while (false
);
2077}

2079void AMDGPUMachineCFGStructurizer::prunePHIInfo(MachineBasicBlock *MBB) {
DEBUG(dbgs() << "Before PHI Prune\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Before PHI Prune\n"
; } } while (false);
DEBUG(PHIInfo.dump(MRI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { PHIInfo.dump(MRI); } } while (false
);
SmallVector<std::tuple<unsigned, unsigned, MachineBasicBlock *>, 4>
    ElimiatedSources;
for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
     ++DRI) {

  unsigned DestReg = *DRI;
  auto SE = PHIInfo.sources_end(DestReg);

  bool MBBContainsPHISource = false;
  // Check if there is a PHI source in this MBB
  for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
    unsigned SourceReg = (*SRI).first;
    MachineOperand *Def = &(*(MRI->def_begin(SourceReg)));
    if (Def->getParent()->getParent() == MBB) {
      MBBContainsPHISource = true;
    }
  }

  // If so, all other sources are useless since we know this block
  // is always executed when the region is executed.
  if (MBBContainsPHISource) {
    for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
      PHILinearize::PHISourceT Source = *SRI;
      unsigned SourceReg = Source.first;
      MachineBasicBlock *SourceMBB = Source.second;
      MachineOperand *Def = &(*(MRI->def_begin(SourceReg)));
      if (Def->getParent()->getParent() != MBB) {
        ElimiatedSources.push_back(
            std::make_tuple(DestReg, SourceReg, SourceMBB));
      }
    }
  }
}

// Remove the PHI sources that are in the given MBB
for (auto &SourceInfo : ElimiatedSources) {
  PHIInfo.removeSource(std::get<0>(SourceInfo), std::get<1>(SourceInfo),
                       std::get<2>(SourceInfo));
}
DEBUG(dbgs() << "After PHI Prune\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "After PHI Prune\n"
; } } while (false);
DEBUG(PHIInfo.dump(MRI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { PHIInfo.dump(MRI); } } while (false
);
2123}

2125void AMDGPUMachineCFGStructurizer::createEntryPHI(LinearizedRegion *CurrentRegion,
                                          unsigned DestReg) {
MachineBasicBlock *Entry = CurrentRegion->getEntry();
MachineBasicBlock *Exit = CurrentRegion->getExit();

DEBUG(dbgs() << "RegionExit: " << Exit->getNumber()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "RegionExit: " <<
 Exit->getNumber() << " Pred: " << (*(Entry->
pred_begin()))->getNumber() << "\n"; } } while (false
)
             << " Pred: " << (*(Entry->pred_begin()))->getNumber() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "RegionExit: " <<
 Exit->getNumber() << " Pred: " << (*(Entry->
pred_begin()))->getNumber() << "\n"; } } while (false
);

int NumSources = 0;
auto SE = PHIInfo.sources_end(DestReg);

for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
  NumSources++;
}

if (NumSources == 1) {
  auto SRI = PHIInfo.sources_begin(DestReg);
  unsigned SourceReg = (*SRI).first;
  replaceRegisterWith(DestReg, SourceReg);
} else {
  const DebugLoc &DL = Entry->findDebugLoc(Entry->begin());
  MachineInstrBuilder MIB = BuildMI(*Entry, Entry->instr_begin(), DL,
                                    TII->get(TargetOpcode::PHI), DestReg);
  DEBUG(dbgs() << "Entry PHI " << printReg(DestReg, TRI) << " = PHI(")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Entry PHI " <<
 printReg(DestReg, TRI) << " = PHI("; } } while (false);

  unsigned CurrentBackedgeReg = 0;

  for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
    unsigned SourceReg = (*SRI).first;

    if (CurrentRegion->contains((*SRI).second)) {
      if (CurrentBackedgeReg == 0) {
        CurrentBackedgeReg = SourceReg;
      } else {
        MachineInstr *PHIDefInstr = getDefInstr(SourceReg);
        MachineBasicBlock *PHIDefMBB = PHIDefInstr->getParent();
        const TargetRegisterClass *RegClass =
            MRI->getRegClass(CurrentBackedgeReg);
        unsigned NewBackedgeReg = MRI->createVirtualRegister(RegClass);
        MachineInstrBuilder BackedgePHI =
            BuildMI(*PHIDefMBB, PHIDefMBB->instr_begin(), DL,
                    TII->get(TargetOpcode::PHI), NewBackedgeReg);
        BackedgePHI.addReg(CurrentBackedgeReg);
        BackedgePHI.addMBB(getPHIPred(*PHIDefInstr, 0));
        BackedgePHI.addReg(getPHISourceReg(*PHIDefInstr, 1));
        BackedgePHI.addMBB((*SRI).second);
        CurrentBackedgeReg = NewBackedgeReg;
        DEBUG(dbgs() << "Inserting backedge PHI: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Inserting backedge PHI: "
 << printReg(NewBackedgeReg, TRI) << " = PHI(" <<
 printReg(CurrentBackedgeReg, TRI) << ", " << printMBBReference
(*getPHIPred(*PHIDefInstr, 0)) << ", " << printReg
(getPHISourceReg(*PHIDefInstr, 1), TRI) << ", " <<
 printMBBReference(*(*SRI).second); } } while (false)
                     << printReg(NewBackedgeReg, TRI) << " = PHI("do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Inserting backedge PHI: "
 << printReg(NewBackedgeReg, TRI) << " = PHI(" <<
 printReg(CurrentBackedgeReg, TRI) << ", " << printMBBReference
(*getPHIPred(*PHIDefInstr, 0)) << ", " << printReg
(getPHISourceReg(*PHIDefInstr, 1), TRI) << ", " <<
 printMBBReference(*(*SRI).second); } } while (false)
                     << printReg(CurrentBackedgeReg, TRI) << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Inserting backedge PHI: "
 << printReg(NewBackedgeReg, TRI) << " = PHI(" <<
 printReg(CurrentBackedgeReg, TRI) << ", " << printMBBReference
(*getPHIPred(*PHIDefInstr, 0)) << ", " << printReg
(getPHISourceReg(*PHIDefInstr, 1), TRI) << ", " <<
 printMBBReference(*(*SRI).second); } } while (false)
                     << printMBBReference(*getPHIPred(*PHIDefInstr, 0))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Inserting backedge PHI: "
 << printReg(NewBackedgeReg, TRI) << " = PHI(" <<
 printReg(CurrentBackedgeReg, TRI) << ", " << printMBBReference
(*getPHIPred(*PHIDefInstr, 0)) << ", " << printReg
(getPHISourceReg(*PHIDefInstr, 1), TRI) << ", " <<
 printMBBReference(*(*SRI).second); } } while (false)
                     << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Inserting backedge PHI: "
 << printReg(NewBackedgeReg, TRI) << " = PHI(" <<
 printReg(CurrentBackedgeReg, TRI) << ", " << printMBBReference
(*getPHIPred(*PHIDefInstr, 0)) << ", " << printReg
(getPHISourceReg(*PHIDefInstr, 1), TRI) << ", " <<
 printMBBReference(*(*SRI).second); } } while (false)
                     << printReg(getPHISourceReg(*PHIDefInstr, 1), TRI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Inserting backedge PHI: "
 << printReg(NewBackedgeReg, TRI) << " = PHI(" <<
 printReg(CurrentBackedgeReg, TRI) << ", " << printMBBReference
(*getPHIPred(*PHIDefInstr, 0)) << ", " << printReg
(getPHISourceReg(*PHIDefInstr, 1), TRI) << ", " <<
 printMBBReference(*(*SRI).second); } } while (false)
                     << ", " << printMBBReference(*(*SRI).second))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Inserting backedge PHI: "
 << printReg(NewBackedgeReg, TRI) << " = PHI(" <<
 printReg(CurrentBackedgeReg, TRI) << ", " << printMBBReference
(*getPHIPred(*PHIDefInstr, 0)) << ", " << printReg
(getPHISourceReg(*PHIDefInstr, 1), TRI) << ", " <<
 printMBBReference(*(*SRI).second); } } while (false);
      }
    } else {
      MIB.addReg(SourceReg);
      MIB.addMBB((*SRI).second);
      DEBUG(dbgs() << printReg(SourceReg, TRI) << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << printReg(SourceReg
, TRI) << ", " << printMBBReference(*(*SRI).second
) << ", "; } } while (false)
                   << printMBBReference(*(*SRI).second) << ", ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << printReg(SourceReg
, TRI) << ", " << printMBBReference(*(*SRI).second
) << ", "; } } while (false);
    }
  }

  // Add the final backedge register source to the entry phi
  if (CurrentBackedgeReg != 0) {
    MIB.addReg(CurrentBackedgeReg);
    MIB.addMBB(Exit);
    DEBUG(dbgs() << printReg(CurrentBackedgeReg, TRI) << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << printReg(CurrentBackedgeReg
, TRI) << ", " << printMBBReference(*Exit) <<
 ")\n"; } } while (false)
                 << printMBBReference(*Exit) << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << printReg(CurrentBackedgeReg
, TRI) << ", " << printMBBReference(*Exit) <<
 ")\n"; } } while (false);
  } else {
    DEBUG(dbgs() << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << ")\n"; } } while
 (false);
  }
}
2198}

2200void AMDGPUMachineCFGStructurizer::createEntryPHIs(LinearizedRegion *CurrentRegion) {
DEBUG(PHIInfo.dump(MRI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { PHIInfo.dump(MRI); } } while (false
);

for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
     ++DRI) {

  unsigned DestReg = *DRI;
  createEntryPHI(CurrentRegion, DestReg);
}
PHIInfo.clear();
2210}

2212void AMDGPUMachineCFGStructurizer::replaceRegisterWith(unsigned Register,
                                               unsigned NewRegister) {
assert(Register != NewRegister && "Cannot replace a reg with itself")(static_cast <bool> (Register != NewRegister &&
 "Cannot replace a reg with itself") ? void (0) : __assert_fail
 ("Register != NewRegister && \"Cannot replace a reg with itself\""
, "/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp"
, 2214, __extension__ __PRETTY_FUNCTION__));

for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Register),
                                       E = MRI->reg_end();
     I != E;) {
  MachineOperand &O = *I;
  ++I;
  if (TargetRegisterInfo::isPhysicalRegister(NewRegister)) {
    DEBUG(dbgs() << "Trying to substitute physical register: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Trying to substitute physical register: "
 << printReg(NewRegister, MRI->getTargetRegisterInfo
()) << "\n"; } } while (false)
                 << printReg(NewRegister, MRI->getTargetRegisterInfo())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Trying to substitute physical register: "
 << printReg(NewRegister, MRI->getTargetRegisterInfo
()) << "\n"; } } while (false)
                 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Trying to substitute physical register: "
 << printReg(NewRegister, MRI->getTargetRegisterInfo
()) << "\n"; } } while (false);
    llvm_unreachable("Cannot substitute physical registers")::llvm::llvm_unreachable_internal("Cannot substitute physical registers"
, "/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp"
, 2225);
    // We don't handle physical registers, but if we need to
    // in the future This is how we do it:
    // O.substPhysReg(NewRegister, *TRI);
  } else {
    DEBUG(dbgs() << "Replacing register: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Replacing register: "
 << printReg(Register, MRI->getTargetRegisterInfo())
 << " with " << printReg(NewRegister, MRI->getTargetRegisterInfo
()) << "\n"; } } while (false)
                 << printReg(Register, MRI->getTargetRegisterInfo())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Replacing register: "
 << printReg(Register, MRI->getTargetRegisterInfo())
 << " with " << printReg(NewRegister, MRI->getTargetRegisterInfo
()) << "\n"; } } while (false)
                 << " with "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Replacing register: "
 << printReg(Register, MRI->getTargetRegisterInfo())
 << " with " << printReg(NewRegister, MRI->getTargetRegisterInfo
()) << "\n"; } } while (false)
                 << printReg(NewRegister, MRI->getTargetRegisterInfo())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Replacing register: "
 << printReg(Register, MRI->getTargetRegisterInfo())
 << " with " << printReg(NewRegister, MRI->getTargetRegisterInfo
()) << "\n"; } } while (false)
                 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Replacing register: "
 << printReg(Register, MRI->getTargetRegisterInfo())
 << " with " << printReg(NewRegister, MRI->getTargetRegisterInfo
()) << "\n"; } } while (false);
    O.setReg(NewRegister);
  }
}
PHIInfo.deleteDef(Register);

getRegionMRT()->replaceLiveOutReg(Register, NewRegister);

DEBUG(PHIInfo.dump(MRI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { PHIInfo.dump(MRI); } } while (false
);
2243}

2245void AMDGPUMachineCFGStructurizer::resolvePHIInfos(MachineBasicBlock *FunctionEntry) {
DEBUG(dbgs() << "Resolve PHI Infos\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Resolve PHI Infos\n"
; } } while (false);
DEBUG(PHIInfo.dump(MRI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { PHIInfo.dump(MRI); } } while (false
);
for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
     ++DRI) {
  unsigned DestReg = *DRI;
  DEBUG(dbgs() << "DestReg: " << printReg(DestReg, TRI) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "DestReg: " <<
 printReg(DestReg, TRI) << "\n"; } } while (false);
  auto SRI = PHIInfo.sources_begin(DestReg);
  unsigned SourceReg = (*SRI).first;
  DEBUG(dbgs() << "DestReg: " << printReg(DestReg, TRI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "DestReg: " <<
 printReg(DestReg, TRI) << " SourceReg: " << printReg
(SourceReg, TRI) << "\n"; } } while (false)
               << " SourceReg: " << printReg(SourceReg, TRI) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "DestReg: " <<
 printReg(DestReg, TRI) << " SourceReg: " << printReg
(SourceReg, TRI) << "\n"; } } while (false);

  assert(PHIInfo.sources_end(DestReg) == ++SRI &&(static_cast <bool> (PHIInfo.sources_end(DestReg) == ++
SRI && "More than one phi source in entry node") ? void
 (0) : __assert_fail ("PHIInfo.sources_end(DestReg) == ++SRI && \"More than one phi source in entry node\""
, "/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp"
, 2258, __extension__ __PRETTY_FUNCTION__))
         "More than one phi source in entry node")(static_cast <bool> (PHIInfo.sources_end(DestReg) == ++
SRI && "More than one phi source in entry node") ? void
 (0) : __assert_fail ("PHIInfo.sources_end(DestReg) == ++SRI && \"More than one phi source in entry node\""
, "/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp"
, 2258, __extension__ __PRETTY_FUNCTION__));
  replaceRegisterWith(DestReg, SourceReg);
}
2261}

2263static bool isFunctionEntryBlock(MachineBasicBlock *MBB) {
return ((&(*(MBB->getParent()->begin()))) == MBB);
2265}

2267MachineBasicBlock *AMDGPUMachineCFGStructurizer::createIfRegion(
  MachineBasicBlock *MergeBB, MachineBasicBlock *CodeBB,
  LinearizedRegion *CurrentRegion, unsigned BBSelectRegIn,
  unsigned BBSelectRegOut) {
if (isFunctionEntryBlock(CodeBB) && !CurrentRegion->getHasLoop()) {
  // Handle non-loop function entry block.
  // We need to allow loops to the entry block and then
  rewriteCodeBBTerminator(CodeBB, MergeBB, BBSelectRegOut);
  resolvePHIInfos(CodeBB);
  removeExternalCFGSuccessors(CodeBB);
  CodeBB->addSuccessor(MergeBB);
  CurrentRegion->addMBB(CodeBB);
  return nullptr;
}
if (CurrentRegion->getEntry() == CodeBB && !CurrentRegion->getHasLoop()) {
  // Handle non-loop region entry block.
  MachineFunction *MF = MergeBB->getParent();
  auto MergeIter = MergeBB->getIterator();
  auto CodeBBStartIter = CodeBB->getIterator();
  auto CodeBBEndIter = ++(CodeBB->getIterator());
  if (CodeBBEndIter != MergeIter) {
    MF->splice(MergeIter, CodeBBStartIter, CodeBBEndIter);
  }
  rewriteCodeBBTerminator(CodeBB, MergeBB, BBSelectRegOut);
  prunePHIInfo(CodeBB);
  createEntryPHIs(CurrentRegion);
  removeExternalCFGSuccessors(CodeBB);
  CodeBB->addSuccessor(MergeBB);
  CurrentRegion->addMBB(CodeBB);
  return nullptr;
} else {
  // Handle internal block.
  const TargetRegisterClass *RegClass = MRI->getRegClass(BBSelectRegIn);
  unsigned CodeBBSelectReg = MRI->createVirtualRegister(RegClass);
  rewriteCodeBBTerminator(CodeBB, MergeBB, CodeBBSelectReg);
  bool IsRegionEntryBB = CurrentRegion->getEntry() == CodeBB;
  MachineBasicBlock *IfBB = createIfBlock(MergeBB, CodeBB, CodeBB, CodeBB,
                                          BBSelectRegIn, IsRegionEntryBB);
  CurrentRegion->addMBB(IfBB);
  // If this is the entry block we need to make the If block the new
  // linearized region entry.
  if (IsRegionEntryBB) {
    CurrentRegion->setEntry(IfBB);

    if (CurrentRegion->getHasLoop()) {
      MachineBasicBlock *RegionExit = CurrentRegion->getExit();
      MachineBasicBlock *ETrueBB = nullptr;
      MachineBasicBlock *EFalseBB = nullptr;
      SmallVector<MachineOperand, 1> ECond;

      const DebugLoc &DL = DebugLoc();
      TII->analyzeBranch(*RegionExit, ETrueBB, EFalseBB, ECond);
      TII->removeBranch(*RegionExit);

      // We need to create a backedge if there is a loop
      unsigned Reg = TII->insertNE(
          RegionExit, RegionExit->instr_end(), DL,
          CurrentRegion->getRegionMRT()->getInnerOutputRegister(),
          CurrentRegion->getRegionMRT()->getEntry()->getNumber());
      MachineOperand RegOp =
          MachineOperand::CreateReg(Reg, false, false, true);
      ArrayRef<MachineOperand> Cond(RegOp);
      DEBUG(dbgs() << "RegionExitReg: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "RegionExitReg: "
; } } while (false);
      DEBUG(Cond[0].print(dbgs(), TRI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { Cond[0].print(dbgs(), TRI); } } while
 (false);
      DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "\n"; } } while (
false);
      TII->insertBranch(*RegionExit, CurrentRegion->getEntry(), RegionExit,
                        Cond, DebugLoc());
      RegionExit->addSuccessor(CurrentRegion->getEntry());
    }
  }
  CurrentRegion->addMBB(CodeBB);
  LinearizedRegion InnerRegion(CodeBB, MRI, TRI, PHIInfo);

  InnerRegion.setParent(CurrentRegion);
  DEBUG(dbgs() << "Insert BB Select PHI (BB)\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Insert BB Select PHI (BB)\n"
; } } while (false);
  insertMergePHI(IfBB, CodeBB, MergeBB, BBSelectRegOut, BBSelectRegIn,
                 CodeBBSelectReg);
  InnerRegion.addMBB(MergeBB);

  DEBUG(InnerRegion.print(dbgs(), TRI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { InnerRegion.print(dbgs(), TRI); }
 } while (false);
  rewriteLiveOutRegs(IfBB, CodeBB, MergeBB, &InnerRegion, CurrentRegion);
  extractKilledPHIs(CodeBB);
  if (IsRegionEntryBB) {
    createEntryPHIs(CurrentRegion);
  }
  return IfBB;
}
2354}

2356MachineBasicBlock *AMDGPUMachineCFGStructurizer::createIfRegion(
  MachineBasicBlock *MergeBB, LinearizedRegion *InnerRegion,
  LinearizedRegion *CurrentRegion, MachineBasicBlock *SelectBB,
  unsigned BBSelectRegIn, unsigned BBSelectRegOut) {
unsigned CodeBBSelectReg =
    InnerRegion->getRegionMRT()->getInnerOutputRegister();
MachineBasicBlock *CodeEntryBB = InnerRegion->getEntry();
MachineBasicBlock *CodeExitBB = InnerRegion->getExit();
MachineBasicBlock *IfBB = createIfBlock(MergeBB, CodeEntryBB, CodeExitBB,
                                        SelectBB, BBSelectRegIn, true);
CurrentRegion->addMBB(IfBB);
bool isEntry = CurrentRegion->getEntry() == InnerRegion->getEntry();
1
Assuming the condition is false→
if (isEntry) {
2
←
Taking false branch→

  if (CurrentRegion->getHasLoop()) {
    MachineBasicBlock *RegionExit = CurrentRegion->getExit();
    MachineBasicBlock *ETrueBB = nullptr;
    MachineBasicBlock *EFalseBB = nullptr;
    SmallVector<MachineOperand, 1> ECond;

    const DebugLoc &DL = DebugLoc();
    TII->analyzeBranch(*RegionExit, ETrueBB, EFalseBB, ECond);
    TII->removeBranch(*RegionExit);

    // We need to create a backedge if there is a loop
    unsigned Reg =
        TII->insertNE(RegionExit, RegionExit->instr_end(), DL,
                      CurrentRegion->getRegionMRT()->getInnerOutputRegister(),
                      CurrentRegion->getRegionMRT()->getEntry()->getNumber());
    MachineOperand RegOp = MachineOperand::CreateReg(Reg, false, false, true);
    ArrayRef<MachineOperand> Cond(RegOp);
    DEBUG(dbgs() << "RegionExitReg: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "RegionExitReg: "
; } } while (false);
    DEBUG(Cond[0].print(dbgs(), TRI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { Cond[0].print(dbgs(), TRI); } } while
 (false);
    DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "\n"; } } while (
false);
    TII->insertBranch(*RegionExit, CurrentRegion->getEntry(), RegionExit,
                      Cond, DebugLoc());
    RegionExit->addSuccessor(IfBB);
  }
}
CurrentRegion->addMBBs(InnerRegion);
DEBUG(dbgs() << "Insert BB Select PHI (region)\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Insert BB Select PHI (region)\n"
; } } while (false);
insertMergePHI(IfBB, CodeExitBB, MergeBB, BBSelectRegOut, BBSelectRegIn,
               CodeBBSelectReg);

rewriteLiveOutRegs(IfBB, /* CodeEntryBB */ CodeExitBB, MergeBB, InnerRegion,
3
←
Calling 'AMDGPUMachineCFGStructurizer::rewriteLiveOutRegs'→
                   CurrentRegion);

rewriteRegionEntryPHIs(InnerRegion, IfBB);

if (isEntry) {
  CurrentRegion->setEntry(IfBB);
}

if (isEntry) {
  createEntryPHIs(CurrentRegion);
}

return IfBB;
2414}

2416void AMDGPUMachineCFGStructurizer::splitLoopPHI(MachineInstr &PHI,
                                        MachineBasicBlock *Entry,
                                        MachineBasicBlock *EntrySucc,
                                        LinearizedRegion *LRegion) {
SmallVector<unsigned, 2> PHIRegionIndices;
getPHIRegionIndices(LRegion, PHI, PHIRegionIndices);

assert(PHIRegionIndices.size() == 1)(static_cast <bool> (PHIRegionIndices.size() == 1) ? void
 (0) : __assert_fail ("PHIRegionIndices.size() == 1", "/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp"
, 2423, __extension__ __PRETTY_FUNCTION__));

unsigned RegionIndex = PHIRegionIndices[0];
unsigned RegionSourceReg = getPHISourceReg(PHI, RegionIndex);
MachineBasicBlock *RegionSourceMBB = getPHIPred(PHI, RegionIndex);
unsigned PHIDest = getPHIDestReg(PHI);
unsigned PHISource = PHIDest;
unsigned ReplaceReg;

if (shrinkPHI(PHI, PHIRegionIndices, &ReplaceReg)) {
  PHISource = ReplaceReg;
}

const TargetRegisterClass *RegClass = MRI->getRegClass(PHIDest);
unsigned NewDestReg = MRI->createVirtualRegister(RegClass);
LRegion->replaceRegisterInsideRegion(PHIDest, NewDestReg, false, MRI);
MachineInstrBuilder MIB =
    BuildMI(*EntrySucc, EntrySucc->instr_begin(), PHI.getDebugLoc(),
            TII->get(TargetOpcode::PHI), NewDestReg);
DEBUG(dbgs() << "Split Entry PHI " << printReg(NewDestReg, TRI) << " = PHI(")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Split Entry PHI "
 << printReg(NewDestReg, TRI) << " = PHI("; } } while
 (false);
MIB.addReg(PHISource);
MIB.addMBB(Entry);
DEBUG(dbgs() << printReg(PHISource, TRI) << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << printReg(PHISource
, TRI) << ", " << printMBBReference(*Entry); } } while
 (false)
             << printMBBReference(*Entry))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << printReg(PHISource
, TRI) << ", " << printMBBReference(*Entry); } } while
 (false);
MIB.addReg(RegionSourceReg);
MIB.addMBB(RegionSourceMBB);
DEBUG(dbgs() << " ," << printReg(RegionSourceReg, TRI) << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << " ," << printReg
(RegionSourceReg, TRI) << ", " << printMBBReference
(*RegionSourceMBB) << ")\n"; } } while (false)
             << printMBBReference(*RegionSourceMBB) << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << " ," << printReg
(RegionSourceReg, TRI) << ", " << printMBBReference
(*RegionSourceMBB) << ")\n"; } } while (false);
2451}

2453void AMDGPUMachineCFGStructurizer::splitLoopPHIs(MachineBasicBlock *Entry,
                                         MachineBasicBlock *EntrySucc,
                                         LinearizedRegion *LRegion) {
SmallVector<MachineInstr *, 2> PHIs;
collectPHIs(Entry, PHIs);

for (auto PHII : PHIs) {
  splitLoopPHI(*PHII, Entry, EntrySucc, LRegion);
}
2462}

2464// Split the exit block so that we can insert a end control flow
2465MachineBasicBlock *
2466AMDGPUMachineCFGStructurizer::splitExit(LinearizedRegion *LRegion) {
auto MRTRegion = LRegion->getRegionMRT();
auto Exit = LRegion->getExit();
auto MF = Exit->getParent();
auto Succ = MRTRegion->getSucc();

auto NewExit = MF->CreateMachineBasicBlock();
auto AfterExitIter = Exit->getIterator();
AfterExitIter++;
MF->insert(AfterExitIter, NewExit);
Exit->removeSuccessor(Succ);
Exit->addSuccessor(NewExit);
NewExit->addSuccessor(Succ);
insertUnconditionalBranch(NewExit, Succ);
LRegion->addMBB(NewExit);
LRegion->setExit(NewExit);

DEBUG(dbgs() << "Created new exit block: " << NewExit->getNumber() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Created new exit block: "
 << NewExit->getNumber() << "\n"; } } while (false
);

// Replace any PHI Predecessors in the successor with NewExit
for (auto &II : *Succ) {
  MachineInstr &Instr = II;

  // If we are past the PHI instructions we are done
  if (!Instr.isPHI())
    break;

  int numPreds = getPHINumInputs(Instr);
  for (int i = 0; i < numPreds; ++i) {
    auto Pred = getPHIPred(Instr, i);
    if (Pred == Exit) {
      setPhiPred(Instr, i, NewExit);
    }
  }
}

return NewExit;
2503}

2505static MachineBasicBlock *split(MachineBasicBlock::iterator I) {
// Create the fall-through block.
MachineBasicBlock *MBB = (*I).getParent();
MachineFunction *MF = MBB->getParent();
MachineBasicBlock *SuccMBB = MF->CreateMachineBasicBlock();
auto MBBIter = ++(MBB->getIterator());
MF->insert(MBBIter, SuccMBB);
SuccMBB->transferSuccessorsAndUpdatePHIs(MBB);
MBB->addSuccessor(SuccMBB);

// Splice the code over.
SuccMBB->splice(SuccMBB->end(), MBB, I, MBB->end());

return SuccMBB;
2519}

2521// Split the entry block separating PHI-nodes and the rest of the code
2522// This is needed to insert an initializer for the bb select register
2523// inloop regions.

2525MachineBasicBlock *
2526AMDGPUMachineCFGStructurizer::splitEntry(LinearizedRegion *LRegion) {
MachineBasicBlock *Entry = LRegion->getEntry();
MachineBasicBlock *EntrySucc = split(Entry->getFirstNonPHI());
MachineBasicBlock *Exit = LRegion->getExit();

DEBUG(dbgs() << "Split " << printMBBReference(*Entry) << " to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Split " <<
 printMBBReference(*Entry) << " to " << printMBBReference
(*Entry) << " -> " << printMBBReference(*EntrySucc
) << "\n"; } } while (false)
             << printMBBReference(*Entry) << " -> "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Split " <<
 printMBBReference(*Entry) << " to " << printMBBReference
(*Entry) << " -> " << printMBBReference(*EntrySucc
) << "\n"; } } while (false)
             << printMBBReference(*EntrySucc) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Split " <<
 printMBBReference(*Entry) << " to " << printMBBReference
(*Entry) << " -> " << printMBBReference(*EntrySucc
) << "\n"; } } while (false);
LRegion->addMBB(EntrySucc);

// Make the backedge go to Entry Succ
if (Exit->isSuccessor(Entry)) {
  Exit->removeSuccessor(Entry);
}
Exit->addSuccessor(EntrySucc);
MachineInstr &Branch = *(Exit->instr_rbegin());
for (auto &UI : Branch.uses()) {
  if (UI.isMBB() && UI.getMBB() == Entry) {
    UI.setMBB(EntrySucc);
  }
}

splitLoopPHIs(Entry, EntrySucc, LRegion);

return EntrySucc;
2551}

2553LinearizedRegion *
2554AMDGPUMachineCFGStructurizer::initLinearizedRegion(RegionMRT *Region) {
LinearizedRegion *LRegion = Region->getLinearizedRegion();
LRegion->initLiveOut(Region, MRI, TRI, PHIInfo);
LRegion->setEntry(Region->getEntry());
return LRegion;
2559}

2561static void removeOldExitPreds(RegionMRT *Region) {
MachineBasicBlock *Exit = Region->getSucc();
if (Exit == nullptr) {
  return;
}
for (MachineBasicBlock::pred_iterator PI = Exit->pred_begin(),
                                      E = Exit->pred_end();
     PI != E; ++PI) {
  if (Region->contains(*PI)) {
    (*PI)->removeSuccessor(Exit);
  }
}
2573}

2575static bool mbbHasBackEdge(MachineBasicBlock *MBB,
                         SmallPtrSet<MachineBasicBlock *, 8> &MBBs) {
for (auto SI = MBB->succ_begin(), SE = MBB->succ_end(); SI != SE; ++SI) {
  if (MBBs.count(*SI) != 0) {
    return true;
  }
}
return false;
2583}

2585static bool containsNewBackedge(MRT *Tree,
                              SmallPtrSet<MachineBasicBlock *, 8> &MBBs) {
// Need to traverse this in reverse since it is in post order.
if (Tree == nullptr)
  return false;

if (Tree->isMBB()) {
  MachineBasicBlock *MBB = Tree->getMBBMRT()->getMBB();
  MBBs.insert(MBB);
  if (mbbHasBackEdge(MBB, MBBs)) {
    return true;
  }
} else {
  RegionMRT *Region = Tree->getRegionMRT();
  SetVector<MRT *> *Children = Region->getChildren();
  for (auto CI = Children->rbegin(), CE = Children->rend(); CI != CE; ++CI) {
    if (containsNewBackedge(*CI, MBBs))
      return true;
  }
}
return false;
2606}

2608static bool containsNewBackedge(RegionMRT *Region) {
SmallPtrSet<MachineBasicBlock *, 8> MBBs;
return containsNewBackedge(Region, MBBs);
2611}

2613bool AMDGPUMachineCFGStructurizer::structurizeComplexRegion(RegionMRT *Region) {
auto *LRegion = initLinearizedRegion(Region);
LRegion->setHasLoop(containsNewBackedge(Region));
MachineBasicBlock *LastMerge = createLinearizedExitBlock(Region);
MachineBasicBlock *CurrentMerge = LastMerge;
LRegion->addMBB(LastMerge);
LRegion->setExit(LastMerge);

rewriteRegionExitPHIs(Region, LastMerge, LRegion);
removeOldExitPreds(Region);

DEBUG(PHIInfo.dump(MRI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { PHIInfo.dump(MRI); } } while (false
);

SetVector<MRT *> *Children = Region->getChildren();
DEBUG(dbgs() << "===========If Region Start===============\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "===========If Region Start===============\n"
; } } while (false);
if (LRegion->getHasLoop()) {
  DEBUG(dbgs() << "Has Backedge: Yes\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Has Backedge: Yes\n"
; } } while (false);
} else {
  DEBUG(dbgs() << "Has Backedge: No\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Has Backedge: No\n"
; } } while (false);
}

unsigned BBSelectRegIn;
unsigned BBSelectRegOut;
for (auto CI = Children->begin(), CE = Children->end(); CI != CE; ++CI) {
  DEBUG(dbgs() << "CurrentRegion: \n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "CurrentRegion: \n"
; } } while (false);
  DEBUG(LRegion->print(dbgs(), TRI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { LRegion->print(dbgs(), TRI); }
 } while (false);

  auto CNI = CI;
  ++CNI;

  MRT *Child = (*CI);

  if (Child->isRegion()) {

    LinearizedRegion *InnerLRegion =
        Child->getRegionMRT()->getLinearizedRegion();
    // We found the block is the exit of an inner region, we need
    // to put it in the current linearized region.

    DEBUG(dbgs() << "Linearizing region: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Linearizing region: "
; } } while (false);
    DEBUG(InnerLRegion->print(dbgs(), TRI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { InnerLRegion->print(dbgs(), TRI
); } } while (false);
    DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "\n"; } } while (
false);

    MachineBasicBlock *InnerEntry = InnerLRegion->getEntry();
    if ((&(*(InnerEntry->getParent()->begin()))) == InnerEntry) {
      // Entry has already been linearized, no need to do this region.
      unsigned OuterSelect = InnerLRegion->getBBSelectRegOut();
      unsigned InnerSelectReg =
          InnerLRegion->getRegionMRT()->getInnerOutputRegister();
      replaceRegisterWith(InnerSelectReg, OuterSelect),
          resolvePHIInfos(InnerEntry);
      if (!InnerLRegion->getExit()->isSuccessor(CurrentMerge))
        InnerLRegion->getExit()->addSuccessor(CurrentMerge);
      continue;
    }

    BBSelectRegOut = Child->getBBSelectRegOut();
    BBSelectRegIn = Child->getBBSelectRegIn();

    DEBUG(dbgs() << "BBSelectRegIn: " << printReg(BBSelectRegIn, TRI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "BBSelectRegIn: "
 << printReg(BBSelectRegIn, TRI) << "\n"; } } while
 (false)
                 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "BBSelectRegIn: "
 << printReg(BBSelectRegIn, TRI) << "\n"; } } while
 (false);
    DEBUG(dbgs() << "BBSelectRegOut: " << printReg(BBSelectRegOut, TRI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "BBSelectRegOut: "
 << printReg(BBSelectRegOut, TRI) << "\n"; } } while
 (false)
                 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "BBSelectRegOut: "
 << printReg(BBSelectRegOut, TRI) << "\n"; } } while
 (false);

    MachineBasicBlock *IfEnd = CurrentMerge;
    CurrentMerge = createIfRegion(CurrentMerge, InnerLRegion, LRegion,
                                  Child->getRegionMRT()->getEntry(),
                                  BBSelectRegIn, BBSelectRegOut);
    TII->convertNonUniformIfRegion(CurrentMerge, IfEnd);
  } else {
    MachineBasicBlock *MBB = Child->getMBBMRT()->getMBB();
    DEBUG(dbgs() << "Linearizing block: " << MBB->getNumber() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Linearizing block: "
 << MBB->getNumber() << "\n"; } } while (false
);

    if (MBB == getSingleExitNode(*(MBB->getParent()))) {
      // If this is the exit block then we need to skip to the next.
      // The "in" register will be transferred to "out" in the next
      // iteration.
      continue;
    }

    BBSelectRegOut = Child->getBBSelectRegOut();
    BBSelectRegIn = Child->getBBSelectRegIn();

    DEBUG(dbgs() << "BBSelectRegIn: " << printReg(BBSelectRegIn, TRI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "BBSelectRegIn: "
 << printReg(BBSelectRegIn, TRI) << "\n"; } } while
 (false)
                 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "BBSelectRegIn: "
 << printReg(BBSelectRegIn, TRI) << "\n"; } } while
 (false);
    DEBUG(dbgs() << "BBSelectRegOut: " << printReg(BBSelectRegOut, TRI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "BBSelectRegOut: "
 << printReg(BBSelectRegOut, TRI) << "\n"; } } while
 (false)
                 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "BBSelectRegOut: "
 << printReg(BBSelectRegOut, TRI) << "\n"; } } while
 (false);

    MachineBasicBlock *IfEnd = CurrentMerge;
    // This is a basic block that is not part of an inner region, we
    // need to put it in the current linearized region.
    CurrentMerge = createIfRegion(CurrentMerge, MBB, LRegion, BBSelectRegIn,
                                  BBSelectRegOut);
    if (CurrentMerge) {
      TII->convertNonUniformIfRegion(CurrentMerge, IfEnd);
    }

    DEBUG(PHIInfo.dump(MRI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { PHIInfo.dump(MRI); } } while (false
);
  }
}

LRegion->removeFalseRegisterKills(MRI);

if (LRegion->getHasLoop()) {
  MachineBasicBlock *NewSucc = splitEntry(LRegion);
  if (isFunctionEntryBlock(LRegion->getEntry())) {
    resolvePHIInfos(LRegion->getEntry());
  }
  const DebugLoc &DL = NewSucc->findDebugLoc(NewSucc->getFirstNonPHI());
  unsigned InReg = LRegion->getBBSelectRegIn();
  unsigned InnerSelectReg =
      MRI->createVirtualRegister(MRI->getRegClass(InReg));
  unsigned NewInReg = MRI->createVirtualRegister(MRI->getRegClass(InReg));
  TII->materializeImmediate(*(LRegion->getEntry()),
                            LRegion->getEntry()->getFirstTerminator(), DL,
                            NewInReg, Region->getEntry()->getNumber());
  // Need to be careful about updating the registers inside the region.
  LRegion->replaceRegisterInsideRegion(InReg, InnerSelectReg, false, MRI);
  DEBUG(dbgs() << "Loop BBSelect Merge PHI:\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Loop BBSelect Merge PHI:\n"
; } } while (false);
  insertMergePHI(LRegion->getEntry(), LRegion->getExit(), NewSucc,
                 InnerSelectReg, NewInReg,
                 LRegion->getRegionMRT()->getInnerOutputRegister());
  splitExit(LRegion);
  TII->convertNonUniformLoopRegion(NewSucc, LastMerge);
}

if (Region->isRoot()) {
  TII->insertReturn(*LastMerge);
}

DEBUG(Region->getEntry()->getParent()->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { Region->getEntry()->getParent
()->dump(); } } while (false);
DEBUG(LRegion->print(dbgs(), TRI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { LRegion->print(dbgs(), TRI); }
 } while (false);
DEBUG(PHIInfo.dump(MRI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { PHIInfo.dump(MRI); } } while (false
);

DEBUG(dbgs() << "===========If Region End===============\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "===========If Region End===============\n"
; } } while (false);

Region->setLinearizedRegion(LRegion);
return true;
2751}

2753bool AMDGPUMachineCFGStructurizer::structurizeRegion(RegionMRT *Region) {
if (false && regionIsSimpleIf(Region)) {
  transformSimpleIfRegion(Region);
  return true;
} else if (regionIsSequence(Region)) {
  fixupRegionExits(Region);
  return false;
} else {
  structurizeComplexRegion(Region);
}
return false;
2764}

2766static int structurize_once = 0;

2768bool AMDGPUMachineCFGStructurizer::structurizeRegions(RegionMRT *Region,
                                              bool isTopRegion) {
bool Changed = false;

auto Children = Region->getChildren();
for (auto CI : *Children) {
  if (CI->isRegion()) {
    Changed |= structurizeRegions(CI->getRegionMRT(), false);
  }
}

if (structurize_once < 2 || true) {
  Changed |= structurizeRegion(Region);
  structurize_once++;
}
return Changed;
2784}

2786void AMDGPUMachineCFGStructurizer::initFallthroughMap(MachineFunction &MF) {
DEBUG(dbgs() << "Fallthrough Map:\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Fallthrough Map:\n"
; } } while (false);
for (auto &MBBI : MF) {
  MachineBasicBlock *MBB = MBBI.getFallThrough();
  if (MBB != nullptr) {
    DEBUG(dbgs() << "Fallthrough: " << MBBI.getNumber() << " -> "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Fallthrough: " <<
 MBBI.getNumber() << " -> " << MBB->getNumber
() << "\n"; } } while (false)
                 << MBB->getNumber() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Fallthrough: " <<
 MBBI.getNumber() << " -> " << MBB->getNumber
() << "\n"; } } while (false);
  }
  FallthroughMap[&MBBI] = MBB;
}
2796}

2798void AMDGPUMachineCFGStructurizer::createLinearizedRegion(RegionMRT *Region,
                                                  unsigned SelectOut) {
LinearizedRegion *LRegion = new LinearizedRegion();
if (SelectOut) {
  LRegion->addLiveOut(SelectOut);
  DEBUG(dbgs() << "Add LiveOut (BBSelect): " << printReg(SelectOut, TRI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Add LiveOut (BBSelect): "
 << printReg(SelectOut, TRI) << "\n"; } } while (
false)
               << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "Add LiveOut (BBSelect): "
 << printReg(SelectOut, TRI) << "\n"; } } while (
false);
}
LRegion->setRegionMRT(Region);
Region->setLinearizedRegion(LRegion);
LRegion->setParent(Region->getParent()
                       ? Region->getParent()->getLinearizedRegion()
                       : nullptr);
2811}

2813unsigned
2814AMDGPUMachineCFGStructurizer::initializeSelectRegisters(MRT *MRT, unsigned SelectOut,
                                                MachineRegisterInfo *MRI,
                                                const SIInstrInfo *TII) {
if (MRT->isRegion()) {
  RegionMRT *Region = MRT->getRegionMRT();
  Region->setBBSelectRegOut(SelectOut);
  unsigned InnerSelectOut = createBBSelectReg(TII, MRI);

  // Fixme: Move linearization creation to the original spot
  createLinearizedRegion(Region, SelectOut);

  for (auto CI = Region->getChildren()->begin(),
            CE = Region->getChildren()->end();
       CI != CE; ++CI) {
    InnerSelectOut =
        initializeSelectRegisters((*CI), InnerSelectOut, MRI, TII);
  }
  MRT->setBBSelectRegIn(InnerSelectOut);
  return InnerSelectOut;
} else {
  MRT->setBBSelectRegOut(SelectOut);
  unsigned NewSelectIn = createBBSelectReg(TII, MRI);
  MRT->setBBSelectRegIn(NewSelectIn);
  return NewSelectIn;
}
2839}

2841static void checkRegOnlyPHIInputs(MachineFunction &MF) {
for (auto &MBBI : MF) {
  for (MachineBasicBlock::instr_iterator I = MBBI.instr_begin(),
                                         E = MBBI.instr_end();
       I != E; ++I) {
    MachineInstr &Instr = *I;
    if (Instr.isPHI()) {
      int numPreds = getPHINumInputs(Instr);
      for (int i = 0; i < numPreds; ++i) {
        assert(Instr.getOperand(i * 2 + 1).isReg() &&(static_cast <bool> (Instr.getOperand(i * 2 + 1).isReg(
) && "PHI Operand not a register") ? void (0) : __assert_fail
 ("Instr.getOperand(i * 2 + 1).isReg() && \"PHI Operand not a register\""
, "/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp"
, 2851, __extension__ __PRETTY_FUNCTION__))
               "PHI Operand not a register")(static_cast <bool> (Instr.getOperand(i * 2 + 1).isReg(
) && "PHI Operand not a register") ? void (0) : __assert_fail
 ("Instr.getOperand(i * 2 + 1).isReg() && \"PHI Operand not a register\""
, "/build/llvm-toolchain-snapshot-7~svn326246/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp"
, 2851, __extension__ __PRETTY_FUNCTION__));
      }
    }
  }
}
2856}

2858bool AMDGPUMachineCFGStructurizer::runOnMachineFunction(MachineFunction &MF) {
const SISubtarget &ST = MF.getSubtarget<SISubtarget>();
const SIInstrInfo *TII = ST.getInstrInfo();
TRI = ST.getRegisterInfo();
MRI = &(MF.getRegInfo());
initFallthroughMap(MF);

checkRegOnlyPHIInputs(MF);
DEBUG(dbgs() << "----STRUCTURIZER START----\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "----STRUCTURIZER START----\n"
; } } while (false);
DEBUG(MF.dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { MF.dump(); } } while (false);

Regions = &(getAnalysis<MachineRegionInfoPass>().getRegionInfo());
DEBUG(Regions->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { Regions->dump(); } } while (false
);

RegionMRT *RTree = MRT::buildMRT(MF, Regions, TII, MRI);
setRegionMRT(RTree);
initializeSelectRegisters(RTree, 0, MRI, TII);
DEBUG(RTree->dump(TRI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { RTree->dump(TRI); } } while (
false);
bool result = structurizeRegions(RTree, true);
delete RTree;
DEBUG(dbgs() << "----STRUCTURIZER END----\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("amdgpucfgstructurizer")) { dbgs() << "----STRUCTURIZER END----\n"
; } } while (false);
initFallthroughMap(MF);
return result;
2881}

2883char AMDGPUMachineCFGStructurizerID = AMDGPUMachineCFGStructurizer::ID;

2885INITIALIZE_PASS_BEGIN(AMDGPUMachineCFGStructurizer, "amdgpu-machine-cfg-structurizer",static void *initializeAMDGPUMachineCFGStructurizerPassOnce(PassRegistry
 &Registry) {
                    "AMDGPU Machine CFG Structurizer", false, false)static void *initializeAMDGPUMachineCFGStructurizerPassOnce(PassRegistry
 &Registry) {
2887INITIALIZE_PASS_DEPENDENCY(MachineRegionInfoPass)initializeMachineRegionInfoPassPass(Registry);
2888INITIALIZE_PASS_END(AMDGPUMachineCFGStructurizer, "amdgpu-machine-cfg-structurizer",PassInfo *PI = new PassInfo( "AMDGPU Machine CFG Structurizer"
, "amdgpu-machine-cfg-structurizer", &AMDGPUMachineCFGStructurizer
::ID, PassInfo::NormalCtor_t(callDefaultCtor<AMDGPUMachineCFGStructurizer
>), false, false); Registry.registerPass(*PI, true); return
 PI; } static llvm::once_flag InitializeAMDGPUMachineCFGStructurizerPassFlag
; void llvm::initializeAMDGPUMachineCFGStructurizerPass(PassRegistry
 &Registry) { llvm::call_once(InitializeAMDGPUMachineCFGStructurizerPassFlag
, initializeAMDGPUMachineCFGStructurizerPassOnce, std::ref(Registry
)); }
                  "AMDGPU Machine CFG Structurizer", false, false)PassInfo *PI = new PassInfo( "AMDGPU Machine CFG Structurizer"
, "amdgpu-machine-cfg-structurizer", &AMDGPUMachineCFGStructurizer
::ID, PassInfo::NormalCtor_t(callDefaultCtor<AMDGPUMachineCFGStructurizer
>), false, false); Registry.registerPass(*PI, true); return
 PI; } static llvm::once_flag InitializeAMDGPUMachineCFGStructurizerPassFlag
; void llvm::initializeAMDGPUMachineCFGStructurizerPass(PassRegistry
 &Registry) { llvm::call_once(InitializeAMDGPUMachineCFGStructurizerPassFlag
, initializeAMDGPUMachineCFGStructurizerPassOnce, std::ref(Registry
)); }

2891FunctionPass *llvm::createAMDGPUMachineCFGStructurizerPass() {
return new AMDGPUMachineCFGStructurizer();
2893}