Machine Level CFG Structurizer

[jsjodin]

Summary

This patch implements CFG structurization based on the paper "Taming Control Divergence in GPUs through Control Flow Linearization" by Jayvant Anantpur, Govindarajan R.
It works somewhat different than the algorithm in the paper, the main difference is that it is region based, and does the transformation backward in stead of forward within a region.

The purpose for the new pass is to do the structurization much later in the compiler to not inhibit optimization. In the AMDGPU backend it is added right before register allocation. The transform is implemented as a target independent pass with a few new callbacks to the target. Hopefully it will be useful to others at some point.

There is a hidden flag added to be able to select the early (old) and the late CFG structurizer. There are some littest failures with the AMDGPU tests when running with the new structurizer, which we are working on fixing.

[jsjodin]

I see some commented out code that I missed to remove. I will fix that asap.

[jsjodin]

Remove commented out code.

[jsjodin]

Updated patch to use better debug locations when instructions are created.

[arsenm]

What effect does this have on what instructions are emitted for the mask modifications? I noticed that sc emits fewer instructions to modify the exec mask. For example, we currently emit for if/then/else

if:
s_and_saveexec_b64 SaveExec, vcc
s_xor_b64 SaveExec, exec, SaveExec

else:
s_or_saveexec_b64 SaveExec, SaveExec
s_xor_b64 exec, exec, SaveExec

endif:
s_or_b64 exec, exec, SaveExec

While sc emits:
if:
s_and_saveexec_b64 SaveExec, vcc

else:
s_andn2_b64, exec, SaveExec, exec

endif:
s_mov_b64 exec, SaveExec

Switching this seems easy, but I tried with the current scheme, but I think it requires modification of how if.break and else.break are inserted

lib/Target/AMDGPU/SIInstrInfo.h

137 ↗

(On Diff #67570)

Don't need virtual

[jsjodin]

Fixed various bugs related to maintaining live out information. Fixed merge issues.

[jsjodin]

Remove virtual

[jsjodin]

In D23209#525350, @arsenm wrote:

What effect does this have on what instructions are emitted for the mask modifications? I noticed that sc emits fewer instructions to modify the exec mask. For example, we currently emit for if/then/else

if:
s_and_saveexec_b64 SaveExec, vcc
s_xor_b64 SaveExec, exec, SaveExec

else:
s_or_saveexec_b64 SaveExec, SaveExec
s_xor_b64 exec, exec, SaveExec

endif:
s_or_b64 exec, exec, SaveExec

While sc emits:
if:
s_and_saveexec_b64 SaveExec, vcc

else:
s_andn2_b64, exec, SaveExec, exec

endif:
s_mov_b64 exec, SaveExec

Switching this seems easy, but I tried with the current scheme, but I think it requires modification of how if.break and else.break are inserted

I think that should be okay, since we don't emit if.break or else. break with the new structurizer. I can try it out and see what happens.

Actually we do emit if.break because it is used to get out of loops. I'm not sure if there is a better scheme for this.

[jsjodin]

Fixed various bugs. The code now transforms DAGs, Loops and nested regions, and the generated code executes correctly, for some small examples.

[jsjodin]

Fix insertSelect to handle VCCZ and VCCNZ conditions.

[majnemer]

Please clang-format this.

[arsenm]

lib/Target/AMDGPU/SIInstrInfo.cpp

598–604 ↗

(On Diff #79604)

I have a patch that more comprehensively implements insertSelect in D26101

[jsjodin]

Cleaned up the code a bit and and clang-formatted everything.

[jsjodin]

lib/Target/AMDGPU/SIInstrInfo.cpp

598–604 ↗

(On Diff #79604)

Good! Are you planning to submit this soon? I guess any reviewer can take note of this and ignore this code.

[jsjodin]

Revert back to "Not Done", accidentally checked the box.

[jsjodin]

Added function to only run the structurizer on a region if there are non-uniform branch instructions present. The interface function should perhaps be called something more generic. Also synced with trunk.

[jsjodin]

Moved the code into the AMDGPU backend since there was little interest in a generic version. If someone wants to use this in the future, it is easy to lift it out into CodeGen again.

[jsjodin]

lib/Target/AMDGPU/SIInstrInfo.cpp

598–604 ↗

(On Diff #79604)

I changed this function to insertVectorSelect. We can merge the two functions later on. I don't want this patch to affect anything.

[arsenm]

lib/CodeGen/MachineRegionInfo.cpp

108 ↗

(On Diff #91067)

Adding commented out code

126 ↗

(On Diff #91067)

This should be committed separately

lib/Target/AMDGPU/SIInstrInfo.cpp

464–466 ↗

(On Diff #91067)

This should just insert copies?

479 ↗

(On Diff #91067)

This will never see a VReg_1

1055 ↗

(On Diff #91067)

succ_empty

598–604 ↗

(On Diff #79604)

I committed the patch for insertSelect already

lib/Target/AMDGPU/SIInstructions.td

174 ↗

(On Diff #91067)

Does this also need to setDef?

175 ↗

(On Diff #91067)

There is a CFPseudoInst which will handle the use/def of EXEC for you

[jsjodin]

lib/CodeGen/MachineRegionInfo.cpp

108 ↗

(On Diff #91067)

Will fix.

126 ↗

(On Diff #91067)

I will split the MachineRegionInfo changes into a separate patch.

126 ↗

(On Diff #91067)

I will split the MachineRegionInfoPass changes to a separate patch.

lib/Target/AMDGPU/SIInstrInfo.cpp

464–466 ↗

(On Diff #91067)

It should just set a register to a specific value.

479 ↗

(On Diff #91067)

I will remove that case.

1055 ↗

(On Diff #91067)

Will fix.

598–604 ↗

(On Diff #79604)

I called this function insertVectorSelect since it only deals with vector ops, and I think insertSelect only does scalar at the moment. I'd prefer no overlap for now since this is only used by the structurizer. It could be merged later.

lib/Target/AMDGPU/SIInstructions.td

174 ↗

(On Diff #91067)

I don't know. What do you think?

175 ↗

(On Diff #91067)

So what should the change be instead? Is this instruction a duplicate of the other instruction?

[jsjodin]

Removed the MachineRegion changes and submitted in a different patch. Fixed a few of the comments made by Matt.

[jsjodin]

Also fixed succ_empty.

[arsenm]

lib/Target/AMDGPU/SIInstrInfo.cpp

494 ↗

(On Diff #94861)

This is really materializeImmediate or something like that

495 ↗

(On Diff #94861)

const DebugLoc &

496 ↗

(On Diff #94861)

Value should be int64_t

502 ↗

(On Diff #94861)

addImms on next lines

508–512 ↗

(On Diff #94861)

Do you actually need to handle all of these large register classes?

726 ↗

(On Diff #94861)

2 space indent

1083 ↗

(On Diff #94861)

assert(Info->isEntryFunction())

4219 ↗

(On Diff #94861)

() not needed around MF

[arsenm]

lib/Target/AMDGPU/SIInstructions.td

174 ↗

(On Diff #91067)

It's expanded into instructions that do, so it should have it as a def too

[jsjodin]

Fixed issues raised by Matt.

[jsjodin]

Fixed remaining comments.

[jsjodin]

lib/Target/AMDGPU/SIInstrInfo.cpp

508–512 ↗

(On Diff #94861)

Yes, I added these as I encountered them in the various tests.

lib/Target/AMDGPU/SIInstructions.td

175 ↗

(On Diff #91067)

Okay, now I realized what you meant. I used the CFPseudoInstSI

[arsenm]

lib/Target/AMDGPU/SIInstrInfo.cpp

1530 ↗

(On Diff #96461)

nullptr

1699–1701 ↗

(On Diff #96461)

No return after else

598–604 ↗

(On Diff #79604)

insertSelect should handle an arbitrary number of elements

lib/Target/AMDGPU/SIInstrInfo.h

156 ↗

(On Diff #96461)

const DebugLoc &

160 ↗

(On Diff #96461)

const DebugLoc &

163–168 ↗

(On Diff #96461)

Accidentally added this?

785–789 ↗

(On Diff #96461)

These don't need to be virtual anymore?

[jsjodin]

Fixed issues raised by Matt.

[jsjodin]

lib/Target/AMDGPU/SIInstrInfo.cpp

598–604 ↗

(On Diff #79604)

Sure, insertSelect does, but this function is not part of the InstrInfo interface. When the functions are merged this can be fixed.

[arsenm]

lib/Target/AMDGPU/SIInstrInfo.cpp

605 ↗

(On Diff #98313)

This can still be condensed similarly to how copyPhysReg does it

[jsjodin]

Made the implementation of materializeImmediate more compact as Matt suggested.

[arsenm]

LGTM

llvm/trunk/lib/Target/AMDGPU/AMDGPU.h

 FunctionPass *createSILoadStoreOptimizerPass(TargetMachine &tm);
 FunctionPass *createSIWholeQuadModePass();
 FunctionPass *createSIFixControlFlowLiveIntervalsPass();
 FunctionPass *createSIFixSGPRCopiesPass();
 FunctionPass *createSIDebuggerInsertNopsPass();
 FunctionPass *createSIInsertWaitsPass();
 FunctionPass *createSIInsertWaitcntsPass();
 FunctionPass *createAMDGPUCodeGenPreparePass(const GCNTargetMachine *TM = nullptr);
+FunctionPass *createAMDGPUMachineCFGStructurizerPass();
+
+void initializeAMDGPUMachineCFGStructurizerPass(PassRegistry&);
+extern char &AMDGPUMachineCFGStructurizerID;
 
 ModulePass *createAMDGPUAnnotateKernelFeaturesPass(const TargetMachine *TM = nullptr);
 void initializeAMDGPUAnnotateKernelFeaturesPass(PassRegistry &);
 extern char &AMDGPUAnnotateKernelFeaturesID;
 
 ModulePass *createAMDGPULowerIntrinsicsPass(const TargetMachine *TM = nullptr);
 void initializeAMDGPULowerIntrinsicsPass(PassRegistry &);
 extern char &AMDGPULowerIntrinsicsID;

llvm/trunk/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp

+//===-- AMDGPUMachineCFGStructurizer.cpp - Machine code if conversion pass. -----===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the machine instruction level CFG structurizer pass.
+//
+//===----------------------------------------------------------------------===//
+
+#include "AMDGPU.h"
+#include "SIInstrInfo.h"
+#include "AMDGPUSubtarget.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/CFG.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineRegionInfo.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/IR/DebugLoc.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetLowering.h"
+#include "llvm/Target/TargetSubtargetInfo.h"
+#include <tuple>
+using namespace llvm;
+
+#define DEBUG_TYPE "amdgpucfgstructurizer"
+
+namespace {
+class PHILinearizeDestIterator;
+
+class PHILinearize {
+  friend class PHILinearizeDestIterator;
+
+public:
+  typedef std::pair<unsigned, MachineBasicBlock *> PHISourceT;
+
+private:
+  typedef DenseSet<PHISourceT> PHISourcesT;
+  typedef struct {
+    unsigned DestReg;
+    DebugLoc DL;
+    PHISourcesT Sources;
+  } PHIInfoElementT;
+  typedef SmallPtrSet<PHIInfoElementT *, 2> PHIInfoT;
+  PHIInfoT PHIInfo;
+
+  static unsigned phiInfoElementGetDest(PHIInfoElementT *Info);
+  static void phiInfoElementSetDef(PHIInfoElementT *Info, unsigned NewDef);
+  static DebugLoc phiInfoElementGetDebugLoc(PHIInfoElementT *Info);
+  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);
+
+public:
+  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);
+  DebugLoc getDebugLoc(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();
+
+  typedef PHISourcesT::iterator source_iterator;
+  typedef PHILinearizeDestIterator dest_iterator;
+
+  dest_iterator dests_begin();
+  dest_iterator dests_end();
+
+  source_iterator sources_begin(unsigned Reg);
+  source_iterator sources_end(unsigned Reg);
+};
+
+class PHILinearizeDestIterator {
+private:
+  PHILinearize::PHIInfoT::iterator Iter;
+
+public:
+  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;
+  }
+
+  PHILinearizeDestIterator(PHILinearize::PHIInfoT::iterator I) : Iter(I) {}
+};
+
+unsigned PHILinearize::phiInfoElementGetDest(PHIInfoElementT *Info) {
+  return Info->DestReg;
+}
+
+void PHILinearize::phiInfoElementSetDef(PHIInfoElementT *Info,
+                                        unsigned NewDef) {
+  Info->DestReg = NewDef;
+}
+
+DebugLoc PHILinearize::phiInfoElementGetDebugLoc(PHIInfoElementT *Info) {
+  return Info->DL;
+}
+
+PHILinearize::PHISourcesT &
+PHILinearize::phiInfoElementGetSources(PHIInfoElementT *Info) {
+  return Info->Sources;
+}
+
+void 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.
+  for (auto SI : phiInfoElementGetSources(Info)) {
+    assert((SI.second != SourceMBB || SourceReg == SI.first));
+  }
+
+  phiInfoElementGetSources(Info).insert(PHISourceT(SourceReg, SourceMBB));
+}
+
+void 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);
+  }
+}
+
+PHILinearize::PHIInfoElementT *
+PHILinearize::findPHIInfoElement(unsigned DestReg) {
+  for (auto I : PHIInfo) {
+    if (phiInfoElementGetDest(I) == DestReg) {
+      return I;
+    }
+  }
+  return nullptr;
+}
+
+PHILinearize::PHIInfoElementT *
+PHILinearize::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;
+}
+
+bool 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;
+}
+
+void PHILinearize::addDest(unsigned DestReg, const DebugLoc &DL) {
+  assert(findPHIInfoElement(DestReg) == nullptr && "Dest already exsists");
+  PHISourcesT EmptySet;
+  PHIInfoElementT *NewElement = new PHIInfoElementT();
+  NewElement->DestReg = DestReg;
+  NewElement->DL = DL;
+  NewElement->Sources = EmptySet;
+  PHIInfo.insert(NewElement);
+}
+
+void PHILinearize::replaceDef(unsigned OldDestReg, unsigned NewDestReg) {
+  phiInfoElementSetDef(findPHIInfoElement(OldDestReg), NewDestReg);
+}
+
+void PHILinearize::deleteDef(unsigned DestReg) {
+  PHIInfoElementT *InfoElement = findPHIInfoElement(DestReg);
+  PHIInfo.erase(InfoElement);
+  delete InfoElement;
+}
+
+DebugLoc PHILinearize::getDebugLoc(unsigned DestReg) {
+  return phiInfoElementGetDebugLoc(findPHIInfoElement(DestReg));
+}
+
+void PHILinearize::addSource(unsigned DestReg, unsigned SourceReg,
+                             MachineBasicBlock *SourceMBB) {
+  phiInfoElementAddSource(findPHIInfoElement(DestReg), SourceReg, SourceMBB);
+}
+
+void PHILinearize::removeSource(unsigned DestReg, unsigned SourceReg,
+                                MachineBasicBlock *SourceMBB) {
+  phiInfoElementRemoveSource(findPHIInfoElement(DestReg), SourceReg, SourceMBB);
+}
+
+bool PHILinearize::findDest(unsigned SourceReg, MachineBasicBlock *SourceMBB,
+                            unsigned &DestReg) {
+  PHIInfoElementT *InfoElement =
+      findPHIInfoElementFromSource(SourceReg, SourceMBB);
+  if (InfoElement != nullptr) {
+    DestReg = phiInfoElementGetDest(InfoElement);
+    return true;
+  }
+  return false;
+}
+
+bool PHILinearize::isSource(unsigned Reg, MachineBasicBlock *SourceMBB) {
+  unsigned DestReg;
+  return findDest(Reg, SourceMBB, DestReg);
+}
+
+unsigned PHILinearize::getNumSources(unsigned DestReg) {
+  return phiInfoElementGetSources(findPHIInfoElement(DestReg)).size();
+}
+
+void PHILinearize::dump(MachineRegisterInfo *MRI) {
+  const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
+  DEBUG(dbgs() << "=PHIInfo Start=\n");
+  for (auto PII : this->PHIInfo) {
+    PHIInfoElementT &Element = *PII;
+    DEBUG(dbgs() << "Dest: " << PrintReg(Element.DestReg, TRI)
+                 << " Sources: {");
+    for (auto &SI : Element.Sources) {
+      DEBUG(dbgs() << PrintReg(SI.first, TRI) << "(BB#"
+                   << SI.second->getNumber() << "),");
+    }
+    DEBUG(dbgs() << "}\n");
+  }
+  DEBUG(dbgs() << "=PHIInfo End=\n");
+}
+
+void PHILinearize::clear() { PHIInfo = PHIInfoT(); }
+
+PHILinearize::dest_iterator PHILinearize::dests_begin() {
+  return PHILinearizeDestIterator(PHIInfo.begin());
+}
+
+PHILinearize::dest_iterator PHILinearize::dests_end() {
+  return PHILinearizeDestIterator(PHIInfo.end());
+}
+
+PHILinearize::source_iterator PHILinearize::sources_begin(unsigned Reg) {
+  auto InfoElement = findPHIInfoElement(Reg);
+  return phiInfoElementGetSources(InfoElement).begin();
+}
+PHILinearize::source_iterator PHILinearize::sources_end(unsigned Reg) {
+  auto InfoElement = findPHIInfoElement(Reg);
+  return phiInfoElementGetSources(InfoElement).end();
+}
+
+class RegionMRT;
+class MBBMRT;
+
+static unsigned getPHINumInputs(MachineInstr &PHI) {
+  assert(PHI.isPHI());
+  return (PHI.getNumOperands() - 1) / 2;
+}
+
+static MachineBasicBlock *getPHIPred(MachineInstr &PHI, unsigned Index) {
+  assert(PHI.isPHI());
+  return PHI.getOperand(Index * 2 + 2).getMBB();
+}
+
+static void setPhiPred(MachineInstr &PHI, unsigned Index,
+                       MachineBasicBlock *NewPred) {
+  PHI.getOperand(Index * 2 + 2).setMBB(NewPred);
+}
+
+static unsigned getPHISourceReg(MachineInstr &PHI, unsigned Index) {
+  assert(PHI.isPHI());
+  return PHI.getOperand(Index * 2 + 1).getReg();
+}
+
+static unsigned getPHIDestReg(MachineInstr &PHI) {
+  assert(PHI.isPHI());
+  return PHI.getOperand(0).getReg();
+}
+
+class LinearizedRegion {
+protected:
+  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);
+
+public:
+  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 addLiveOuts(LinearizedRegion *LRegion);
+
+  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);
+
+  bool isDefinedInRegion(unsigned Reg, MachineRegisterInfo *MRI);
+
+  void removeFalseRegisterKills(MachineRegisterInfo *MRI);
+
+  void initLiveOut(RegionMRT *Region, const MachineRegisterInfo *MRI,
+                   const TargetRegisterInfo *TRI, PHILinearize &PHIInfo);
+
+  LinearizedRegion(MachineBasicBlock *MBB, const MachineRegisterInfo *MRI,
+                   const TargetRegisterInfo *TRI, PHILinearize &PHIInfo);
+
+  LinearizedRegion(RegionMRT *Region, const MachineRegisterInfo *MRI,
+                   const TargetRegisterInfo *TRI, PHILinearize &PHIInfo);
+
+  LinearizedRegion();
+
+  ~LinearizedRegion();
+};
+
+class MRT {
+protected:
+  RegionMRT *Parent;
+  unsigned BBSelectRegIn;
+  unsigned BBSelectRegOut;
+
+public:
+  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() << "  ";
+    }
+  }
+
+  virtual ~MRT() {}
+};
+
+class MBBMRT : public MRT {
+  MachineBasicBlock *MBB;
+
+public:
+  virtual MBBMRT *getMBBMRT() { return this; }
+
+  MachineBasicBlock *getMBB() { return MBB; }
+
+  virtual void dump(const TargetRegisterInfo *TRI, int depth = 0) {
+    dumpDepth(depth);
+    dbgs() << "MBB: " << getMBB()->getNumber();
+    dbgs() << " In: " << PrintReg(getBBSelectRegIn(), TRI);
+    dbgs() << ", Out: " << PrintReg(getBBSelectRegOut(), TRI) << "\n";
+  }
+
+  MBBMRT(MachineBasicBlock *BB) : MBB(BB) {
+    setParent(nullptr);
+    setBBSelectRegOut(0);
+    setBBSelectRegIn(0);
+  }
+};
+
+class RegionMRT : public MRT {
+protected:
+  MachineRegion *Region;
+  LinearizedRegion *LRegion;
+  MachineBasicBlock *Succ;
+
+  SetVector<MRT *> Children;
+
+public:
+  virtual RegionMRT *getRegionMRT() { 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; }
+
+  virtual void dump(const TargetRegisterInfo *TRI, int depth = 0) {
+    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);
+      }
+    }
+  }
+
+  RegionMRT(MachineRegion *MachineRegion)
+      : Region(MachineRegion), LRegion(nullptr), Succ(nullptr) {
+    setParent(nullptr);
+    setBBSelectRegOut(0);
+    setBBSelectRegIn(0);
+  }
+
+  virtual ~RegionMRT() {
+    if (LRegion) {
+      delete LRegion;
+    }
+
+    for (auto CI : Children) {
+      delete &(*CI);
+    }
+  }
+};
+
+static unsigned createBBSelectReg(const SIInstrInfo *TII,
+                                  MachineRegisterInfo *MRI) {
+  return MRI->createVirtualRegister(TII->getPreferredSelectRegClass(32));
+}
+
+MachineBasicBlock *
+MRT::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");
+  return nullptr;
+}
+
+RegionMRT *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 BB#" << MBB->getNumber() << "\n");
+    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;
+}
+
+void 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");
+    // 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");
+      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 BB#" << MBB->getNumber()
+                       << "): " << PrintReg(Reg, TRI) << "\n");
+          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)
+                           << "\n");
+              addLiveOut(Reg);
+            }
+          }
+        }
+      }
+    }
+  }
+}
+
+void 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");
+    for (auto &UI : MRI->use_operands(Reg)) {
+      if (!Region->contains(UI.getParent()->getParent())) {
+        DEBUG(dbgs() << "Add LiveOut (Region " << (void *)Region
+                     << "): " << PrintReg(Reg, TRI) << "\n");
+        addLiveOut(Reg);
+      }
+    }
+  }
+}
+
+void LinearizedRegion::storeLiveOuts(MachineBasicBlock *MBB,
+                                     const MachineRegisterInfo *MRI,
+                                     const TargetRegisterInfo *TRI,
+                                     PHILinearize &PHIInfo) {
+  DEBUG(dbgs() << "-Store Live Outs Begin (BB#" << MBB->getNumber() << ")-\n");
+  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 BB#" << MBB->getNumber()
+                         << " -> BB#" << (*SI)->getNumber()
+                         << "): " << PrintReg(PHIReg, TRI) << "\n");
+            addLiveOut(PHIReg);
+          }
+        }
+      }
+    }
+  }
+
+  DEBUG(dbgs() << "-Store Live Outs Endn-\n");
+}
+
+void 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);
+      }
+    }
+  }
+}
+
+void 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 *)Region
+                         << "): " << PrintReg(PHIReg, TRI) << "\n");
+            addLiveOut(PHIReg);
+          }
+        }
+      }
+    }
+  }
+}
+
+void 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";
+}
+
+unsigned LinearizedRegion::getBBSelectRegIn() {
+  return getRegionMRT()->getBBSelectRegIn();
+}
+
+unsigned LinearizedRegion::getBBSelectRegOut() {
+  return getRegionMRT()->getBBSelectRegOut();
+}
+
+void LinearizedRegion::setHasLoop(bool Value) { HasLoop = Value; }
+
+bool LinearizedRegion::getHasLoop() { return HasLoop; }
+
+void LinearizedRegion::addLiveOut(unsigned VReg) { LiveOuts.insert(VReg); }
+
+void LinearizedRegion::addLiveOuts(LinearizedRegion *LRegion) {
+  DenseSet<unsigned> *RegionLiveOuts = LRegion->getLiveOuts();
+  for (auto R : *RegionLiveOuts) {
+    addLiveOut(R);
+  }
+}
+
+void LinearizedRegion::removeLiveOut(unsigned Reg) {
+  if (isLiveOut(Reg))
+    LiveOuts.erase(Reg);
+}
+
+void LinearizedRegion::replaceLiveOut(unsigned OldReg, unsigned NewReg) {
+  if (isLiveOut(OldReg)) {
+    removeLiveOut(OldReg);
+    addLiveOut(NewReg);
+  }
+}
+
+void LinearizedRegion::replaceRegister(unsigned Register, unsigned NewRegister,
+                                       MachineRegisterInfo *MRI,
+                                       bool ReplaceInside, bool ReplaceOutside,
+                                       bool IncludeLoopPHI) {
+  assert(Register != NewRegister && "Cannot replace a reg with itself");
+
+  DEBUG(dbgs() << "Pepareing to replace register (region): "
+               << PrintReg(Register, MRI->getTargetRegisterInfo()) << " with "
+               << PrintReg(NewRegister, MRI->getTargetRegisterInfo()) << "\n");
+
+  // 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");
+      DEBUG(Current->print(dbgs(), MRI->getTargetRegisterInfo()));
+      Current->replaceLiveOut(Register, NewRegister);
+      DEBUG(dbgs() << "Region after register replace\n");
+      DEBUG(Current->print(dbgs(), MRI->getTargetRegisterInfo()));
+      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: "
+                     << PrintReg(NewRegister, MRI->getTargetRegisterInfo())
+                     << "\n");
+        llvm_unreachable("Cannot substitute physical registers");
+      } else {
+        DEBUG(dbgs() << "Replacing register (region): "
+                     << PrintReg(Register, MRI->getTargetRegisterInfo())
+                     << " with "
+                     << PrintReg(NewRegister, MRI->getTargetRegisterInfo())
+                     << "\n");
+        O.setReg(NewRegister);
+      }
+    }
+  }
+}
+
+void LinearizedRegion::replaceRegisterInsideRegion(unsigned Register,
+                                                   unsigned NewRegister,
+                                                   bool IncludeLoopPHIs,
+                                                   MachineRegisterInfo *MRI) {
+  replaceRegister(Register, NewRegister, MRI, true, false, IncludeLoopPHIs);
+}
+
+void LinearizedRegion::replaceRegisterOutsideRegion(unsigned Register,
+                                                    unsigned NewRegister,
+                                                    bool IncludeLoopPHIs,
+                                                    MachineRegisterInfo *MRI) {
+  replaceRegister(Register, NewRegister, MRI, false, true, IncludeLoopPHIs);
+}
+
+DenseSet<unsigned> *LinearizedRegion::getLiveOuts() { return &LiveOuts; }
+
+void LinearizedRegion::setEntry(MachineBasicBlock *NewEntry) {
+  Entry = NewEntry;
+}
+
+MachineBasicBlock *LinearizedRegion::getEntry() { return Entry; }
+
+void LinearizedRegion::setExit(MachineBasicBlock *NewExit) { Exit = NewExit; }
+
+MachineBasicBlock *LinearizedRegion::getExit() { return Exit; }
+
+void LinearizedRegion::addMBB(MachineBasicBlock *MBB) { MBBs.insert(MBB); }
+
+void LinearizedRegion::addMBBs(LinearizedRegion *InnerRegion) {
+  for (const auto &MBB : InnerRegion->MBBs) {
+    addMBB(MBB);
+  }
+}
+
+bool LinearizedRegion::contains(MachineBasicBlock *MBB) {
+  return MBBs.count(MBB) == 1;
+}
+
+bool LinearizedRegion::isLiveOut(unsigned Reg) {
+  return LiveOuts.count(Reg) == 1;
+}
+
+bool LinearizedRegion::hasNoDef(unsigned Reg, MachineRegisterInfo *MRI) {
+  return MRI->def_begin(Reg) == MRI->def_end();
+}
+
+bool LinearizedRegion::isDefinedInRegion(unsigned Reg,
+                                         MachineRegisterInfo *MRI) {
+  bool NoDef = hasNoDef(Reg, MRI);
+  if (NoDef) {
+    return false;
+  }
+
+  if (!MRI->hasOneDef(Reg)) {
+    DEBUG(dbgs() << "Register " << PrintReg(Reg, MRI->getTargetRegisterInfo())
+                 << " has multiple defs\n");
+  }
+
+  assert(MRI->hasOneDef(Reg) && "Register has multiple definitions");
+  MachineOperand *Def = &(*(MRI->def_begin(Reg)));
+  return contains(Def->getParent()->getParent());
+}
+
+// After the code has been structurized, what was flagged as kills
+// before are no longer register kills.
+void 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());
+              DEBUG(dbgs() << PrintReg(Reg, TRI) << "\n");
+            }
+
+            if (MRI->def_begin(Reg) == MRI->def_end()) {
+              DEBUG(dbgs() << "Register "
+                           << PrintReg(Reg, MRI->getTargetRegisterInfo())
+                           << " has NO defs\n");
+            } else if (!MRI->hasOneDef(Reg)) {
+              DEBUG(dbgs() << "Register "
+                           << PrintReg(Reg, MRI->getTargetRegisterInfo())
+                           << " has multiple defs\n");
+            }
+
+            assert(MRI->hasOneDef(Reg) && "Register has multiple definitions");
+            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: "
+                           << PrintReg(Reg, TRI) << "\n");
+              UseOperand->setIsKill(false);
+            }
+          }
+        }
+      }
+    }
+  }
+}
+
+void LinearizedRegion::initLiveOut(RegionMRT *Region,
+                                   const MachineRegisterInfo *MRI,
+                                   const TargetRegisterInfo *TRI,
+                                   PHILinearize &PHIInfo) {
+  storeLiveOuts(Region, MRI, TRI, PHIInfo);
+}
+
+LinearizedRegion::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;
+}
+
+LinearizedRegion::LinearizedRegion(RegionMRT *Region,
+                                   const MachineRegisterInfo *MRI,
+                                   const TargetRegisterInfo *TRI,
+                                   PHILinearize &PHIInfo) {
+  setEntry(Region->getEntry());
+  // We don't have a single exit block that is part of the region
+  // at this point. When the transform is performed this block
+  // will be created.
+  setExit(nullptr);
+  storeLiveOuts(Region, MRI, TRI, PHIInfo);
+  Parent = nullptr;
+}
+
+LinearizedRegion::LinearizedRegion() {
+  setEntry(nullptr);
+  setExit(nullptr);
+  Parent = nullptr;
+}
+
+LinearizedRegion::~LinearizedRegion() {}
+
+class AMDGPUMachineCFGStructurizer : public MachineFunctionPass {
+private:
+  const MachineRegionInfo *Regions;
+  const SIInstrInfo *TII;
+  const TargetRegisterInfo *TRI;
+  MachineRegisterInfo *MRI;
+  unsigned BBSelectRegister;
+  PHILinearize PHIInfo;
+  DenseMap<MachineBasicBlock *, MachineBasicBlock *> FallthroughMap;
+
+  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);
+  void extractKilledPHIs(LinearizedRegion *LRegion);
+
+  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);
+
+  bool regionIsSimpleLoop(RegionMRT *Region);
+
+  void transformSimpleLoopRegion(RegionMRT *Region);
+
+  void eliminateDeadBranchOperands(MachineBasicBlock::instr_iterator &II);
+
+  void insertUnconditionalBranch(MachineBasicBlock *MBB,
+                                 MachineBasicBlock *Dest,
+                                 const DebugLoc &DL = DebugLoc());
+
+  MachineBasicBlock *createLinearizedExitBlock(RegionMRT *Region);
+
+  void replaceRegisterOutsideMBB(MachineBasicBlock *MBB, unsigned Register,
+                                 unsigned NewRegister);
+
+  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);
+
+public:
+  static char ID;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<MachineRegionInfoPass>();
+    MachineFunctionPass::getAnalysisUsage(AU);
+  }
+
+    AMDGPUMachineCFGStructurizer() : MachineFunctionPass(ID) {
+      initializeAMDGPUMachineCFGStructurizerPass(*PassRegistry::getPassRegistry());
+    }
+
+  void initFallthroughMap(MachineFunction &MF);
+
+  void createLinearizedRegion(RegionMRT *Region, unsigned SelectOut);
+
+  unsigned initializeSelectRegisters(MRT *MRT, unsigned ExistingExitReg,
+                                     MachineRegisterInfo *MRI,
+                                     const SIInstrInfo *TII);
+
+  RegionMRT *RMRT;
+  void setRegionMRT(RegionMRT *RegionTree) { RMRT = RegionTree; }
+
+  RegionMRT *getRegionMRT() { return RMRT; }
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+};
+}
+
+char AMDGPUMachineCFGStructurizer::ID = 0;
+
+bool 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;
+}
+
+void AMDGPUMachineCFGStructurizer::transformSimpleIfRegion(RegionMRT *Region) {
+  MachineBasicBlock *Entry = Region->getEntry();
+  MachineBasicBlock *Exit = Region->getExit();
+  TII->convertNonUniformIfRegion(Entry, Exit);
+}
+
+bool AMDGPUMachineCFGStructurizer::regionIsSimpleLoop(RegionMRT *Region) {
+  MachineBasicBlock *Entry = Region->getEntry();
+
+  if (Entry->succ_size() != 1) {
+    return false;
+  }
+
+  int NumRegionExitEdges = 0;
+  MachineBasicBlock *BackBlock = nullptr;
+  for (MachineBasicBlock::const_pred_iterator PI = Entry->succ_begin(),
+                                              PE = Entry->succ_end();
+       PI != PE; ++PI) {
+    MachineBasicBlock *CurrentSP = *PI;
+    if (Region->contains(CurrentSP)) {
+      BackBlock = CurrentSP;
+    }
+  }
+
+  bool HasBackedge = false;
+
+  for (MachineBasicBlock::const_succ_iterator SI = Entry->succ_begin(),
+                                              SE = Entry->succ_end();
+       SI != SE; ++SI) {
+    MachineBasicBlock *CurrentBS = *SI;
+    if (CurrentBS == Entry) {
+      HasBackedge = true;
+    }
+  }
+
+  return NumRegionExitEdges == 1 && BackBlock->succ_size() == 2 && HasBackedge;
+}
+
+void AMDGPUMachineCFGStructurizer::transformSimpleLoopRegion(RegionMRT *Region) {
+  MachineBasicBlock *Entry = Region->getEntry();
+  MachineBasicBlock *BackBlock = nullptr;
+  for (MachineBasicBlock::const_pred_iterator PI = Entry->succ_begin(),
+                                              PE = Entry->succ_end();
+       PI != PE; ++PI) {
+    MachineBasicBlock *CurrentSP = *PI;
+    if (Region->contains(CurrentSP)) {
+      BackBlock = CurrentSP;
+    }
+  }
+
+  TII->convertNonUniformLoopRegion(Entry, BackBlock);
+}
+
+static 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);
+        }
+      }
+    }
+  }
+}
+
+static 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);
+      InternalSucc = Succ;
+    } else {
+      // Do not allow re-assign
+      assert(ExternalSucc == nullptr);
+      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);
+        }
+      }
+    }
+  }
+}
+
+// If a region region is just a sequence of regions (and the exit
+// block in the case of the top level region), we can simply skip
+// linearizing it, because it is already linear
+bool 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;
+}
+
+void fixupRegionExits(RegionMRT *Region) {
+  auto Children = Region->getChildren();
+  for (auto CI : *Children) {
+    if (!CI->isRegion()) {
+      fixMBBTerminator(CI->getMBBMRT()->getMBB());
+    } else {
+      fixRegionTerminator(CI->getRegionMRT());
+    }
+  }
+}
+
+void 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);
+    }
+  }
+}
+
+void 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);
+    }
+  }
+}
+
+void 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);
+    }
+  }
+}
+
+void 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));
+    }
+  }
+}
+
+unsigned 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;
+}
+
+void 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");
+      DEBUG(Instr.dump());
+      PHIs.insert(&Instr);
+      PHIInfo.addDest(PHIDestReg, Instr.getDebugLoc());
+      storePHILinearizationInfoDest(PHIDestReg, Instr);
+    }
+  }
+
+  for (auto PI : PHIs) {
+    PI->eraseFromParent();
+  }
+}
+
+void AMDGPUMachineCFGStructurizer::extractKilledPHIs(LinearizedRegion *LRegion) {
+  // PHIs can only exist in the entry block.
+  extractKilledPHIs(LRegion->getEntry());
+}
+
+static bool isPHIRegionIndex(SmallVector<unsigned, 2> PHIRegionIndices,
+                             unsigned Index) {
+  for (auto i : PHIRegionIndices) {
+    if (i == Index)
+      return true;
+  }
+  return false;
+}
+
+bool AMDGPUMachineCFGStructurizer::shrinkPHI(MachineInstr &PHI,
+                                       SmallVector<unsigned, 2> &PHIIndices,
+                                       unsigned *ReplaceReg) {
+  return shrinkPHI(PHI, 0, nullptr, PHIIndices, ReplaceReg);
+}
+
+bool AMDGPUMachineCFGStructurizer::shrinkPHI(MachineInstr &PHI,
+                                       unsigned CombinedSourceReg,
+                                       MachineBasicBlock *SourceMBB,
+                                       SmallVector<unsigned, 2> &PHIIndices,
+                                       unsigned *ReplaceReg) {
+  DEBUG(dbgs() << "Shrink PHI: ");
+  DEBUG(PHI.dump());
+  DEBUG(dbgs() << " to " << PrintReg(getPHIDestReg(PHI), TRI)
+               << "<def> = PHI(");
+
+  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) << ", BB#"
+                   << SourceMBB->getNumber());
+    }
+
+    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) << ", BB#"
+                   << SourcePred->getNumber());
+    }
+    DEBUG(dbgs() << ")\n");
+  }
+  PHI.eraseFromParent();
+  return Replaced;
+}
+
+void AMDGPUMachineCFGStructurizer::replacePHI(
+    MachineInstr &PHI, unsigned CombinedSourceReg, MachineBasicBlock *LastMerge,
+    SmallVector<unsigned, 2> &PHIRegionIndices) {
+  DEBUG(dbgs() << "Replace PHI: ");
+  DEBUG(PHI.dump());
+  DEBUG(dbgs() << " with " << PrintReg(getPHIDestReg(PHI), TRI)
+               << "<def> = PHI(");
+
+  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) << ", BB#"
+                 << LastMerge->getNumber());
+    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) << ", BB#"
+                   << SourcePred->getNumber());
+    }
+    DEBUG(dbgs() << ")\n");
+  } else {
+    replaceRegisterWith(getPHIDestReg(PHI), CombinedSourceReg);
+  }
+  PHI.eraseFromParent();
+}
+
+void AMDGPUMachineCFGStructurizer::replaceEntryPHI(
+    MachineInstr &PHI, unsigned CombinedSourceReg, MachineBasicBlock *IfMBB,
+    SmallVector<unsigned, 2> &PHIRegionIndices) {
+
+  DEBUG(dbgs() << "Replace entry PHI: ");
+  DEBUG(PHI.dump());
+  DEBUG(dbgs() << " with ");
+
+  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");
+    PHI.eraseFromParent();
+  } else {
+    DEBUG(dbgs() << PrintReg(getPHIDestReg(PHI), TRI) << "<def> = PHI(");
+    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) << ", BB#"
+                 << IfMBB->getNumber());
+    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) << ", BB#"
+                   << SourcePred->getNumber());
+    }
+    DEBUG(dbgs() << ")\n");
+    PHI.eraseFromParent();
+  }
+}
+
+void 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 "
+                   << (IsDead ? "dead" : "alive") << " after PHI replace\n");
+      if (IsDead) {
+        LRegion->removeLiveOut(Reg);
+      }
+      WasLiveOut = true;
+    }
+  }
+
+  if (WasLiveOut)
+    LRegion->addLiveOut(CombinedSourceReg);
+}
+
+void 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);
+}
+
+void 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);
+}
+
+static void collectPHIs(MachineBasicBlock *MBB,
+                        SmallVector<MachineInstr *, 2> &PHIs) {
+  for (auto &BBI : *MBB) {
+    if (BBI.isPHI()) {
+      PHIs.push_back(&BBI);
+    }
+  }
+}
+
+void 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);
+  }
+}
+
+void 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);
+  }
+}
+
+void AMDGPUMachineCFGStructurizer::insertUnconditionalBranch(MachineBasicBlock *MBB,
+                                                       MachineBasicBlock *Dest,
+                                                       const DebugLoc &DL) {
+  DEBUG(dbgs() << "Inserting unconditional branch: " << MBB->getNumber()
+               << " -> " << Dest->getNumber() << "\n");
+  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);
+  }
+}
+
+static 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;
+}
+
+static bool hasOneExitNode(MachineFunction &MF) {
+  return getSingleExitNode(MF) != nullptr;
+}
+
+MachineBasicBlock *
+AMDGPUMachineCFGStructurizer::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");
+  }
+  return LastMerge;
+}
+
+void AMDGPUMachineCFGStructurizer::replaceRegisterOutsideMBB(MachineBasicBlock *MBB,
+                                                       unsigned Register,
+                                                       unsigned NewRegister) {
+  assert(Register != NewRegister && "Cannot replace a reg with itself");
+
+  for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Register),
+                                         E = MRI->reg_end();
+       I != E;) {
+    MachineOperand &O = *I;
+    ++I;
+    if (O.getParent()->getParent() != MBB) {
+      if (TargetRegisterInfo::isPhysicalRegister(NewRegister)) {
+        llvm_unreachable("Cannot substitute physical registers");
+        // 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 {
+        O.setReg(NewRegister);
+      }
+    }
+  }
+}
+
+void 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 (BB#" << MergeBB->getNumber()
+               << "): " << PrintReg(DestRegister, TRI) << "<def> = PHI("
+               << PrintReg(IfSourceRegister, TRI) << ", BB#"
+               << IfBB->getNumber() << PrintReg(CodeSourceRegister, TRI)
+               << ", BB#" << CodeBB->getNumber() << ")\n");
+  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);
+}
+
+static 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);
+    }
+  }
+}
+
+static 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
+      // succesor 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: BB#" << Edge.first->getNumber() << " -> BB#"
+                 << Edge.second->getNumber() << "\n");
+    Edge.first->removeSuccessor(Edge.second);
+  }
+}
+
+MachineBasicBlock *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");
+  // Ensure that the MergeBB is a succesor of the CodeEndBB.
+  if (!CodeBBEnd->isSuccessor(MergeBB))
+    CodeBBEnd->addSuccessor(MergeBB);
+
+  DEBUG(dbgs() << "Moved MBB#" << CodeBBStart->getNumber() << " through MBB#"
+               << CodeBBEnd->getNumber() << "\n");
+
+  // 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;
+}
+
+void 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);
+  }
+}
+
+void 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);
+}
+
+MachineInstr *AMDGPUMachineCFGStructurizer::getDefInstr(unsigned Reg) {
+  if (MRI->def_begin(Reg) == MRI->def_end()) {
+    DEBUG(dbgs() << "Register " << PrintReg(Reg, MRI->getTargetRegisterInfo())
+                 << " has NO defs\n");
+  } else if (!MRI->hasOneDef(Reg)) {
+    DEBUG(dbgs() << "Register " << PrintReg(Reg, MRI->getTargetRegisterInfo())
+                 << " has multiple defs\n");
+    DEBUG(dbgs() << "DEFS BEGIN:\n");
+    for (auto DI = MRI->def_begin(Reg), DE = MRI->def_end(); DI != DE; ++DI) {
+      DEBUG(DI->getParent()->dump());
+    }
+    DEBUG(dbgs() << "DEFS END\n");
+  }
+
+  assert(MRI->hasOneDef(Reg) && "Register has multiple definitions");
+  return (*(MRI->def_begin(Reg))).getParent();
+}
+
+void 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");
+    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);
+    }
+  }
+}
+
+bool AMDGPUMachineCFGStructurizer::containsDef(MachineBasicBlock *MBB,
+                                         LinearizedRegion *InnerRegion,
+                                         unsigned Register) {
+  return getDefInstr(Register)->getParent() == MBB ||
+         InnerRegion->contains(getDefInstr(Register)->getParent());
+}
+
+void 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();
+  for (auto OLI : *LiveOuts) {
+    OldLiveOuts.push_back(OLI);
+  }
+
+  for (auto LI : OldLiveOuts) {
+    DEBUG(dbgs() << "LiveOut: " << PrintReg(LI, TRI));
+    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");
+      continue;
+    }
+    DEBUG(dbgs() << "\n");
+    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");
+      TII->materializeImmediate(*IfBB, IfBB->getFirstTerminator(), DebugLoc(),
+                        IfSourceReg, 0);
+
+      InnerRegion->replaceRegisterOutsideRegion(Reg, PHIDestReg, true, MRI);
+      DEBUG(dbgs() << "Insert Non-Chained Live out PHI\n");
+      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)) {
+    DEBUG(dbgs() << "Inserting PHI Live Out from BB#" << CodeBB->getNumber()
+                 << "\n");
+    for (auto SI : Sources) {
+      unsigned DestReg;
+      PHIInfo.findDest(SI, CodeBB, DestReg);
+      insertChainedPHI(IfBB, CodeBB, MergeBB, InnerRegion, DestReg, SI);
+    }
+    DEBUG(dbgs() << "Insertion done.\n");
+  }
+
+  PHIInfo.dump(MRI);
+}
+
+void AMDGPUMachineCFGStructurizer::prunePHIInfo(MachineBasicBlock *MBB) {
+  DEBUG(dbgs() << "Before PHI Prune\n");
+  DEBUG(PHIInfo.dump(MRI));
+  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");
+  DEBUG(PHIInfo.dump(MRI));
+}
+
+void AMDGPUMachineCFGStructurizer::createEntryPHI(LinearizedRegion *CurrentRegion,
+                                            unsigned DestReg) {
+  MachineBasicBlock *Entry = CurrentRegion->getEntry();
+  MachineBasicBlock *Exit = CurrentRegion->getExit();
+  MachineBasicBlock *Pred = *(Entry->pred_begin());
+
+  DEBUG(dbgs() << "RegionExit: " << Exit->getNumber()
+               << " Pred: " << Pred->getNumber() << "\n");
+
+  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) << "<def> = PHI(");
+
+    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: "
+                       << PrintReg(NewBackedgeReg, TRI) << "<def> = PHI("
+                       << PrintReg(CurrentBackedgeReg, TRI) << ", BB#"
+                       << getPHIPred(*PHIDefInstr, 0)->getNumber() << ", "
+                       << PrintReg(getPHISourceReg(*PHIDefInstr, 1), TRI)
+                       << ", BB#" << (*SRI).second->getNumber());
+        }
+      } else {
+        MIB.addReg(SourceReg);
+        MIB.addMBB((*SRI).second);
+        DEBUG(dbgs() << PrintReg(SourceReg, TRI) << ", BB#"
+                     << (*SRI).second->getNumber() << ", ");
+      }
+    }
+
+    // Add the final backedge register source to the entry phi
+    if (CurrentBackedgeReg != 0) {
+      MIB.addReg(CurrentBackedgeReg);
+      MIB.addMBB(Exit);
+      DEBUG(dbgs() << PrintReg(CurrentBackedgeReg, TRI) << ", BB#"
+                   << Exit->getNumber() << ")\n");
+    } else {
+      DEBUG(dbgs() << ")\n");
+    }
+  }
+}
+
+void AMDGPUMachineCFGStructurizer::createEntryPHIs(LinearizedRegion *CurrentRegion) {
+  DEBUG(PHIInfo.dump(MRI));
+
+  for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
+       ++DRI) {
+
+    unsigned DestReg = *DRI;
+    createEntryPHI(CurrentRegion, DestReg);
+  }
+  PHIInfo.clear();
+}
+
+void AMDGPUMachineCFGStructurizer::replaceRegisterWith(unsigned Register,
+                                                 unsigned NewRegister) {
+  assert(Register != NewRegister && "Cannot replace a reg with itself");
+
+  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: "
+                   << PrintReg(NewRegister, MRI->getTargetRegisterInfo())
+                   << "\n");
+      llvm_unreachable("Cannot substitute physical registers");
+      // 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: "
+                   << PrintReg(Register, MRI->getTargetRegisterInfo())
+                   << " with "
+                   << PrintReg(NewRegister, MRI->getTargetRegisterInfo())
+                   << "\n");
+      O.setReg(NewRegister);
+    }
+  }
+  PHIInfo.deleteDef(Register);
+
+  getRegionMRT()->replaceLiveOutReg(Register, NewRegister);
+
+  DEBUG(PHIInfo.dump(MRI));
+}
+
+void AMDGPUMachineCFGStructurizer::resolvePHIInfos(MachineBasicBlock *FunctionEntry) {
+  DEBUG(dbgs() << "Resolve PHI Infos\n");
+  DEBUG(PHIInfo.dump(MRI));
+  for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
+       ++DRI) {
+    unsigned DestReg = *DRI;
+    DEBUG(dbgs() << "DestReg: " << PrintReg(DestReg, TRI) << "\n");
+    auto SRI = PHIInfo.sources_begin(DestReg);
+    unsigned SourceReg = (*SRI).first;
+    DEBUG(dbgs() << "DestReg: " << PrintReg(DestReg, TRI)
+                 << " SourceReg: " << PrintReg(SourceReg, TRI) << "\n");
+
+    assert(PHIInfo.sources_end(DestReg) == ++SRI &&
+           "More than one phi source in entry node");
+    replaceRegisterWith(DestReg, SourceReg);
+  }
+}
+
+static bool isFunctionEntryBlock(MachineBasicBlock *MBB) {
+  return ((&(*(MBB->getParent()->begin()))) == MBB);
+}
+
+MachineBasicBlock *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: ");
+        DEBUG(Cond[0].print(dbgs(), TRI));
+        DEBUG(dbgs() << "\n");
+        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");
+    insertMergePHI(IfBB, CodeBB, MergeBB, BBSelectRegOut, BBSelectRegIn,
+                   CodeBBSelectReg);
+    InnerRegion.addMBB(MergeBB);
+
+    DEBUG(InnerRegion.print(dbgs(), TRI));
+    rewriteLiveOutRegs(IfBB, CodeBB, MergeBB, &InnerRegion, CurrentRegion);
+    extractKilledPHIs(CodeBB);
+    if (IsRegionEntryBB) {
+      createEntryPHIs(CurrentRegion);
+    }
+    return IfBB;
+  }
+}
+
+MachineBasicBlock *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();
+  if (isEntry) {
+
+    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: ");
+      DEBUG(Cond[0].print(dbgs(), TRI));
+      DEBUG(dbgs() << "\n");
+      TII->insertBranch(*RegionExit, CurrentRegion->getEntry(), RegionExit,
+                        Cond, DebugLoc());
+      RegionExit->addSuccessor(IfBB);
+    }
+  }
+  CurrentRegion->addMBBs(InnerRegion);
+  DEBUG(dbgs() << "Insert BB Select PHI (region)\n");
+  insertMergePHI(IfBB, CodeExitBB, MergeBB, BBSelectRegOut, BBSelectRegIn,
+                 CodeBBSelectReg);
+
+  rewriteLiveOutRegs(IfBB, /* CodeEntryBB */ CodeExitBB, MergeBB, InnerRegion,
+                     CurrentRegion);
+
+  rewriteRegionEntryPHIs(InnerRegion, IfBB);
+
+  if (isEntry) {
+    CurrentRegion->setEntry(IfBB);
+  }
+
+  if (isEntry) {
+    createEntryPHIs(CurrentRegion);
+  }
+
+  return IfBB;
+}
+
+void AMDGPUMachineCFGStructurizer::splitLoopPHI(MachineInstr &PHI,
+                                          MachineBasicBlock *Entry,
+                                          MachineBasicBlock *EntrySucc,
+                                          LinearizedRegion *LRegion) {
+  SmallVector<unsigned, 2> PHIRegionIndices;
+  getPHIRegionIndices(LRegion, PHI, PHIRegionIndices);
+
+  assert(PHIRegionIndices.size() == 1);
+
+  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)
+               << "<def> = PHI(");
+  MIB.addReg(PHISource);
+  MIB.addMBB(Entry);
+  DEBUG(dbgs() << PrintReg(PHISource, TRI) << ", BB#" << Entry->getNumber());
+  MIB.addReg(RegionSourceReg);
+  MIB.addMBB(RegionSourceMBB);
+  DEBUG(dbgs() << " ," << PrintReg(RegionSourceReg, TRI) << ", BB#"
+               << RegionSourceMBB->getNumber() << ")\n");
+}
+
+void AMDGPUMachineCFGStructurizer::splitLoopPHIs(MachineBasicBlock *Entry,
+                                           MachineBasicBlock *EntrySucc,
+                                           LinearizedRegion *LRegion) {
+  SmallVector<MachineInstr *, 2> PHIs;
+  collectPHIs(Entry, PHIs);
+
+  for (auto PHII : PHIs) {
+    splitLoopPHI(*PHII, Entry, EntrySucc, LRegion);
+  }
+}
+
+// Split the exit block so that we can insert a end control flow
+MachineBasicBlock *
+AMDGPUMachineCFGStructurizer::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");
+
+  // 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;
+}
+
+
+static 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;
+}
+
+// Split the entry block separating PHI-nodes and the rest of the code
+// This is needed to insert an initializer for the bb select register
+// inloop regions.
+
+MachineBasicBlock *
+AMDGPUMachineCFGStructurizer::splitEntry(LinearizedRegion *LRegion) {
+  MachineBasicBlock *Entry = LRegion->getEntry();
+  MachineBasicBlock *EntrySucc = split(Entry->getFirstNonPHI());
+  MachineBasicBlock *Exit = LRegion->getExit();
+
+  DEBUG(dbgs() << "Split BB#" << Entry->getNumber() << " to BB#"
+               << Entry->getNumber() << " -> BB#" << EntrySucc->getNumber()
+               << "\n");
+  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;
+}
+
+LinearizedRegion *
+AMDGPUMachineCFGStructurizer::initLinearizedRegion(RegionMRT *Region) {
+  LinearizedRegion *LRegion = Region->getLinearizedRegion();
+  LRegion->initLiveOut(Region, MRI, TRI, PHIInfo);
+  LRegion->setEntry(Region->getEntry());
+  return LRegion;
+}
+
+static 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);
+    }
+  }
+}
+
+static 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;
+}
+
+static 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;
+}
+
+static bool containsNewBackedge(RegionMRT *Region) {
+  SmallPtrSet<MachineBasicBlock *, 8> MBBs;
+  return containsNewBackedge(Region, MBBs);
+}
+
+bool 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));
+
+  auto Entry = Region->getEntry();
+
+  SetVector<MRT *> *Children = Region->getChildren();
+  DEBUG(dbgs() << "===========If Region Start===============\n");
+  if (LRegion->getHasLoop()) {
+    DEBUG(dbgs() << "Has Backedge: Yes\n");
+  } else {
+    DEBUG(dbgs() << "Has Backedge: No\n");
+  }
+
+  unsigned BBSelectRegIn;
+  unsigned BBSelectRegOut;
+  for (auto CI = Children->begin(), CE = Children->end(); CI != CE; ++CI) {
+    DEBUG(dbgs() << "CurrentRegion: \n");
+    DEBUG(LRegion->print(dbgs(), TRI));
+
+    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: ");
+      DEBUG(InnerLRegion->print(dbgs(), TRI));
+      DEBUG(dbgs() << "\n");
+
+      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)
+                   << "\n");
+      DEBUG(dbgs() << "BBSelectRegOut: " << PrintReg(BBSelectRegOut, TRI)
+                   << "\n");
+
+      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");
+
+      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)
+                   << "\n");
+      DEBUG(dbgs() << "BBSelectRegOut: " << PrintReg(BBSelectRegOut, TRI)
+                   << "\n");
+
+      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));
+    }
+  }
+
+  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");
+    insertMergePHI(LRegion->getEntry(), LRegion->getExit(), NewSucc,
+                   InnerSelectReg, NewInReg,
+                   LRegion->getRegionMRT()->getInnerOutputRegister());
+    splitExit(LRegion);
+    TII->convertNonUniformLoopRegion(NewSucc, LastMerge);
+  }
+
+  if (Region->isRoot()) {
+    TII->insertReturn(*LastMerge);
+  }
+
+  DEBUG(Entry->getParent()->dump());
+  DEBUG(LRegion->print(dbgs(), TRI));
+  DEBUG(PHIInfo.dump(MRI));
+
+  DEBUG(dbgs() << "===========If Region End===============\n");
+
+  Region->setLinearizedRegion(LRegion);
+  return true;
+}
+
+bool 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;
+}
+
+static int structurize_once = 0;
+
+bool 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;
+}
+
+void AMDGPUMachineCFGStructurizer::initFallthroughMap(MachineFunction &MF) {
+  DEBUG(dbgs() << "Fallthrough Map:\n");
+  for (auto &MBBI : MF) {
+    MachineBasicBlock *MBB = MBBI.getFallThrough();
+    if (MBB != nullptr) {
+      DEBUG(dbgs() << "Fallthrough: " << MBBI.getNumber() << " -> "
+                   << MBB->getNumber() << "\n");
+    }
+    FallthroughMap[&MBBI] = MBB;
+  }
+}
+
+void AMDGPUMachineCFGStructurizer::createLinearizedRegion(RegionMRT *Region,
+                                                    unsigned SelectOut) {
+  LinearizedRegion *LRegion = new LinearizedRegion();
+  if (SelectOut) {
+    LRegion->addLiveOut(SelectOut);
+    DEBUG(dbgs() << "Add LiveOut (BBSelect): " << PrintReg(SelectOut, TRI)
+                 << "\n");
+  }
+  LRegion->setRegionMRT(Region);
+  Region->setLinearizedRegion(LRegion);
+  LRegion->setParent(Region->getParent()
+                         ? Region->getParent()->getLinearizedRegion()
+                         : nullptr);
+}
+
+unsigned
+AMDGPUMachineCFGStructurizer::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;
+  }
+}
+
+static 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() &&
+                 "PHI Operand not a register");
+        }
+      }
+    }
+  }
+}
+
+
+INITIALIZE_PASS_BEGIN(AMDGPUMachineCFGStructurizer, "amdgpu-machine-cfg-structurizer",
+                      "AMDGPU Machine CFG Structurizer", false, false)
+INITIALIZE_PASS_DEPENDENCY(MachineRegionInfoPass)
+INITIALIZE_PASS_END(AMDGPUMachineCFGStructurizer, "amdgpu-machine-cfg-structurizer",
+                    "AMDGPU Machine CFG Structurizer", false, false)
+
+char AMDGPUMachineCFGStructurizerID = AMDGPUMachineCFGStructurizer::ID;
+
+
+bool 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");
+  DEBUG(MF.dump());
+
+  Regions = &(getAnalysis<MachineRegionInfoPass>().getRegionInfo());
+  DEBUG(Regions->dump());
+
+  RegionMRT *RTree = MRT::buildMRT(MF, Regions, TII, MRI);
+  setRegionMRT(RTree);
+  initializeSelectRegisters(RTree, 0, MRI, TII);
+  DEBUG(RTree->dump(TRI));
+  bool result = structurizeRegions(RTree, true);
+  delete RTree;
+  DEBUG(dbgs() << "----STRUCTURIZER END----\n");
+  initFallthroughMap(MF);
+  return result;
+}
+
+FunctionPass *llvm::createAMDGPUMachineCFGStructurizerPass() {
+  return new AMDGPUMachineCFGStructurizer();
+}
+

llvm/trunk/lib/Target/AMDGPU/AMDGPUTargetMachine.cpp

static cl::opt<bool> EnableAMDGPUAliasAnalysis("enable-amdgpu-aa", cl::Hidden,
   cl::init(true));
 
 // Option to enable new waitcnt insertion pass.
 static cl::opt<bool> EnableSIInsertWaitcntsPass(
   "enable-si-insert-waitcnts",
   cl::desc("Use new waitcnt insertion pass"),
   cl::init(false));
 
+// Option to run late CFG structurizer
+static cl::opt<bool> LateCFGStructurize(
+  "amdgpu-late-structurize",
+  cl::desc("Enable late CFG structurization"),
+  cl::init(false),
+  cl::Hidden);
+
 extern "C" void LLVMInitializeAMDGPUTarget() {
   // Register the target
   RegisterTargetMachine<R600TargetMachine> X(getTheAMDGPUTarget());
   RegisterTargetMachine<GCNTargetMachine> Y(getTheGCNTarget());
 
   PassRegistry *PR = PassRegistry::getPassRegistry();
   initializeSILowerI1CopiesPass(*PR);
   initializeSIFixSGPRCopiesPass(*PR);
bool GCNPassConfig::addPreISel() {
   // FIXME: We need to run a pass to propagate the attributes when calls are
   // supported.
   const AMDGPUTargetMachine &TM = getAMDGPUTargetMachine();
   addPass(createAMDGPUAnnotateKernelFeaturesPass(&TM));
 
   // Merge divergent exit nodes. StructurizeCFG won't recognize the multi-exit
   // regions formed by them.
   addPass(&AMDGPUUnifyDivergentExitNodesID);
+  if (!LateCFGStructurize) {
     addPass(createStructurizeCFGPass(true)); // true -> SkipUniformRegions
+  }
   addPass(createSinkingPass());
   addPass(createSITypeRewriter());
   addPass(createAMDGPUAnnotateUniformValues());
+  if (!LateCFGStructurize) {
     addPass(createSIAnnotateControlFlowPass());
+  }
 
   return false;
 }
 
 void GCNPassConfig::addMachineSSAOptimization() {
   TargetPassConfig::addMachineSSAOptimization();
 
   // We want to fold operands after PeepholeOptimizer has run (or as part of

 bool GCNPassConfig::addGlobalInstructionSelect() {
   addPass(new InstructionSelect());
   return false;
 }
 
 #endif
 
 void GCNPassConfig::addPreRegAlloc() {
+  if (LateCFGStructurize) {
+    addPass(createAMDGPUMachineCFGStructurizerPass());
+  }
   addPass(createSIWholeQuadModePass());
 }
 
 void GCNPassConfig::addFastRegAlloc(FunctionPass *RegAllocPass) {
   // FIXME: We have to disable the verifier here because of PHIElimination +
   // TwoAddressInstructions disabling it.
 
   // This must be run immediately after phi elimination and before

llvm/trunk/lib/Target/AMDGPU/CMakeLists.txt

add_llvm_target(AMDGPUCodeGen
   AMDGPUAsmPrinter.cpp
   AMDGPUCodeGenPrepare.cpp
   AMDGPUFrameLowering.cpp
   AMDGPUTargetObjectFile.cpp
   AMDGPUIntrinsicInfo.cpp
   AMDGPUISelDAGToDAG.cpp
   AMDGPULowerIntrinsics.cpp
   AMDGPUMCInstLower.cpp
+  AMDGPUMachineCFGStructurizer.cpp
   AMDGPUMachineFunction.cpp
   AMDGPUUnifyMetadata.cpp
   AMDGPUOpenCLImageTypeLoweringPass.cpp
   AMDGPUSubtarget.cpp
   AMDGPUTargetMachine.cpp
   AMDGPUTargetTransformInfo.cpp
   AMDGPUISelLowering.cpp
   AMDGPUInstrInfo.cpp

llvm/trunk/lib/Target/AMDGPU/SIInstrInfo.h

public:
   void copyPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
                    const DebugLoc &DL, unsigned DestReg, unsigned SrcReg,
                    bool KillSrc) const override;
 
   unsigned calculateLDSSpillAddress(MachineBasicBlock &MBB, MachineInstr &MI,
                                     RegScavenger *RS, unsigned TmpReg,
                                     unsigned Offset, unsigned Size) const;
 
+  void materializeImmediate(MachineBasicBlock &MBB,
+                            MachineBasicBlock::iterator MI,
+                            const DebugLoc &DL,
+                            unsigned DestReg,
+                            int64_t Value) const;
+
+  const TargetRegisterClass *getPreferredSelectRegClass(
+                               unsigned Size) const;
+
+  unsigned insertNE(MachineBasicBlock *MBB,
+                    MachineBasicBlock::iterator I, const DebugLoc &DL,
+                    unsigned SrcReg, int Value)  const;
+
+  unsigned insertEQ(MachineBasicBlock *MBB,
+                    MachineBasicBlock::iterator I, const DebugLoc &DL,
+                    unsigned SrcReg, int Value)  const;
+
   void storeRegToStackSlot(MachineBasicBlock &MBB,
                            MachineBasicBlock::iterator MI, unsigned SrcReg,
                            bool isKill, int FrameIndex,
                            const TargetRegisterClass *RC,
                            const TargetRegisterInfo *TRI) const override;
 
   void loadRegFromStackSlot(MachineBasicBlock &MBB,
                             MachineBasicBlock::iterator MI, unsigned DestReg,
bool analyzeBranchImpl(MachineBasicBlock &MBB,
                          MachineBasicBlock *&TBB,
                          MachineBasicBlock *&FBB,
                          SmallVectorImpl<MachineOperand> &Cond,
                          bool AllowModify) const;
 
   bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
                      MachineBasicBlock *&FBB,
                      SmallVectorImpl<MachineOperand> &Cond,
-                     bool AllowModify) const override;
+                     bool AllowModify = false) const override;
 
   unsigned removeBranch(MachineBasicBlock &MBB,
                         int *BytesRemoved = nullptr) const override;
 
   unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB,
                         MachineBasicBlock *FBB, ArrayRef<MachineOperand> Cond,
                         const DebugLoc &DL,
                         int *BytesAdded = nullptr) const override;
 
   bool reverseBranchCondition(
     SmallVectorImpl<MachineOperand> &Cond) const override;
 
 
   bool canInsertSelect(const MachineBasicBlock &MBB,
                        ArrayRef<MachineOperand> Cond,
                        unsigned TrueReg, unsigned FalseReg,
                        int &CondCycles,
                        int &TrueCycles, int &FalseCycles) const override;
 
   void insertSelect(MachineBasicBlock &MBB,
                     MachineBasicBlock::iterator I, const DebugLoc &DL,
                     unsigned DstReg, ArrayRef<MachineOperand> Cond,
                     unsigned TrueReg, unsigned FalseReg) const override;
 
+  void insertVectorSelect(MachineBasicBlock &MBB,
+                          MachineBasicBlock::iterator I, const DebugLoc &DL,
+                          unsigned DstReg, ArrayRef<MachineOperand> Cond,
+                          unsigned TrueReg, unsigned FalseReg) const;
+
   bool
   areMemAccessesTriviallyDisjoint(MachineInstr &MIa, MachineInstr &MIb,
                                   AliasAnalysis *AA = nullptr) const override;
 
   bool isFoldableCopy(const MachineInstr &MI) const;
 
   bool FoldImmediate(MachineInstr &UseMI, MachineInstr &DefMI, unsigned Reg,
                      MachineRegisterInfo *MRI) const final;
public:
   void moveToVALU(MachineInstr &MI) const;
 
   void insertWaitStates(MachineBasicBlock &MBB,MachineBasicBlock::iterator MI,
                         int Count) const;
 
   void insertNoop(MachineBasicBlock &MBB,
                   MachineBasicBlock::iterator MI) const override;
 
+  void insertReturn(MachineBasicBlock &MBB) const;
   /// \brief Return the number of wait states that result from executing this
   /// instruction.
   unsigned getNumWaitStates(const MachineInstr &MI) const;
 
   /// \brief Returns the operand named \p Op.  If \p MI does not have an
   /// operand named \c Op, this function returns nullptr.
   LLVM_READONLY
   MachineOperand *getNamedOperand(MachineInstr &MI, unsigned OperandName) const;
unsigned isLoadFromStackSlot(const MachineInstr &MI,
                                int &FrameIndex) const override;
   unsigned isStoreToStackSlot(const MachineInstr &MI,
                               int &FrameIndex) const override;
 
   unsigned getInstSizeInBytes(const MachineInstr &MI) const override;
 
   bool mayAccessFlatAddressSpace(const MachineInstr &MI) const;
 
+  bool isNonUniformBranchInstr(MachineInstr &Instr) const;
+
+  void convertNonUniformIfRegion(MachineBasicBlock *IfEntry,
+                                 MachineBasicBlock *IfEnd) const;
+
+  void convertNonUniformLoopRegion(MachineBasicBlock *LoopEntry,
+                                   MachineBasicBlock *LoopEnd) const;
+
   ArrayRef<std::pair<int, const char *>>
   getSerializableTargetIndices() const override;
 
   ScheduleHazardRecognizer *
   CreateTargetPostRAHazardRecognizer(const InstrItineraryData *II,
                                  const ScheduleDAG *DAG) const override;
 
   ScheduleHazardRecognizer *

llvm/trunk/lib/Target/AMDGPU/SIInstrInfo.cpp

int SIInstrInfo::commuteOpcode(unsigned Opcode) const {
   NewOpc = AMDGPU::getCommuteOrig(Opcode);
   if (NewOpc != -1)
     // Check if the original (non-REV) opcode exists on the target.
     return pseudoToMCOpcode(NewOpc) != -1 ? NewOpc : -1;
 
   return Opcode;
 }
 
+void SIInstrInfo::materializeImmediate(MachineBasicBlock &MBB,
+                                       MachineBasicBlock::iterator MI,
+                                       const DebugLoc &DL, unsigned DestReg,
+                                       int64_t Value) const {
+  MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
+  const TargetRegisterClass *RegClass = MRI.getRegClass(DestReg);
+  if (RegClass == &AMDGPU::SReg_32RegClass ||
+      RegClass == &AMDGPU::SGPR_32RegClass ||
+      RegClass == &AMDGPU::SReg_32_XM0RegClass ||
+      RegClass == &AMDGPU::SReg_32_XM0_XEXECRegClass) {
+    BuildMI(MBB, MI, DL, get(AMDGPU::S_MOV_B32), DestReg)
+      .addImm(Value);
+    return;
+  }
+
+  if (RegClass == &AMDGPU::SReg_64RegClass ||
+      RegClass == &AMDGPU::SGPR_64RegClass ||
+      RegClass == &AMDGPU::SReg_64_XEXECRegClass) {
+    BuildMI(MBB, MI, DL, get(AMDGPU::S_MOV_B64), DestReg)
+      .addImm(Value);
+    return;
+  }
+
+  if (RegClass == &AMDGPU::VGPR_32RegClass) {
+    BuildMI(MBB, MI, DL, get(AMDGPU::V_MOV_B32_e32), DestReg)
+      .addImm(Value);
+    return;
+  }
+  if (RegClass == &AMDGPU::VReg_64RegClass) {
+    BuildMI(MBB, MI, DL, get(AMDGPU::V_MOV_B64_PSEUDO), DestReg)
+      .addImm(Value);
+    return;
+  }
+
+  unsigned EltSize = 4;
+  unsigned Opcode = AMDGPU::V_MOV_B32_e32;
+  if (RI.isSGPRClass(RegClass)) {
+    if (RI.getRegSizeInBits(*RegClass) > 32) {
+      Opcode =  AMDGPU::S_MOV_B64;
+      EltSize = 8;
+    } else {
+      Opcode = AMDGPU::S_MOV_B32;
+      EltSize = 4;
+    }
+  }
+
+  ArrayRef<int16_t> SubIndices = RI.getRegSplitParts(RegClass, EltSize);
+  for (unsigned Idx = 0; Idx < SubIndices.size(); ++Idx) {
+    int64_t IdxValue = Idx == 0 ? Value : 0;
+
+    MachineInstrBuilder Builder = BuildMI(MBB, MI, DL,
+      get(Opcode), RI.getSubReg(DestReg, Idx));
+    Builder.addImm(IdxValue);
+  }
+}
+
+const TargetRegisterClass *
+SIInstrInfo::getPreferredSelectRegClass(unsigned Size) const {
+  return &AMDGPU::VGPR_32RegClass;
+}
+
+void SIInstrInfo::insertVectorSelect(MachineBasicBlock &MBB,
+                                     MachineBasicBlock::iterator I,
+                                     const DebugLoc &DL, unsigned DstReg,
+                                     ArrayRef<MachineOperand> Cond,
+                                     unsigned TrueReg,
+                                     unsigned FalseReg) const {
+  MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
+  const TargetRegisterClass *RegClass = MRI.getRegClass(DstReg);
+  assert(RegClass == &AMDGPU::VGPR_32RegClass && "Not a VGPR32 reg");
+
+  if (Cond.size() == 1) {
+    BuildMI(MBB, I, DL, get(AMDGPU::V_CNDMASK_B32_e64), DstReg)
+      .addReg(FalseReg)
+      .addReg(TrueReg)
+      .add(Cond[0]);
+  } else if (Cond.size() == 2) {
+    assert(Cond[0].isImm() && "Cond[0] is not an immediate");
+    switch (Cond[0].getImm()) {
+    case SIInstrInfo::SCC_TRUE: {
+      unsigned SReg = MRI.createVirtualRegister(&AMDGPU::SReg_64RegClass);
+      BuildMI(MBB, I, DL, get(AMDGPU::S_CSELECT_B64), SReg)
+        .addImm(-1)
+        .addImm(0);
+      BuildMI(MBB, I, DL, get(AMDGPU::V_CNDMASK_B32_e64), DstReg)
+        .addReg(FalseReg)
+        .addReg(TrueReg)
+        .addReg(SReg);
+      break;
+    }
+    case SIInstrInfo::SCC_FALSE: {
+      unsigned SReg = MRI.createVirtualRegister(&AMDGPU::SReg_64RegClass);
+      BuildMI(MBB, I, DL, get(AMDGPU::S_CSELECT_B64), SReg)
+        .addImm(0)
+        .addImm(-1);
+      BuildMI(MBB, I, DL, get(AMDGPU::V_CNDMASK_B32_e64), DstReg)
+        .addReg(FalseReg)
+        .addReg(TrueReg)
+        .addReg(SReg);
+      break;
+    }
+    case SIInstrInfo::VCCNZ: {
+      MachineOperand RegOp = Cond[1];
+      RegOp.setImplicit(false);
+      BuildMI(MBB, I, DL, get(AMDGPU::V_CNDMASK_B32_e64), DstReg)
+          .addReg(FalseReg)
+          .addReg(TrueReg)
+          .add(RegOp);
+      break;
+    }
+    case SIInstrInfo::VCCZ: {
+      MachineOperand RegOp = Cond[1];
+      RegOp.setImplicit(false);
+      BuildMI(MBB, I, DL, get(AMDGPU::V_CNDMASK_B32_e64), DstReg)
+          .addReg(TrueReg)
+          .addReg(FalseReg)
+          .add(RegOp);
+      break;
+    }
+    case SIInstrInfo::EXECNZ: {
+      unsigned SReg = MRI.createVirtualRegister(&AMDGPU::SReg_64RegClass);
+      unsigned SReg2 = MRI.createVirtualRegister(&AMDGPU::SReg_64RegClass);
+      BuildMI(MBB, I, DL, get(AMDGPU::S_OR_SAVEEXEC_B64), SReg2)
+        .addImm(0);
+      BuildMI(MBB, I, DL, get(AMDGPU::S_CSELECT_B64), SReg)
+        .addImm(-1)
+        .addImm(0);
+      BuildMI(MBB, I, DL, get(AMDGPU::V_CNDMASK_B32_e64), DstReg)
+        .addReg(FalseReg)
+        .addReg(TrueReg)
+        .addReg(SReg);
+      break;
+    }
+    case SIInstrInfo::EXECZ: {
+      unsigned SReg = MRI.createVirtualRegister(&AMDGPU::SReg_64RegClass);
+      unsigned SReg2 = MRI.createVirtualRegister(&AMDGPU::SReg_64RegClass);
+      BuildMI(MBB, I, DL, get(AMDGPU::S_OR_SAVEEXEC_B64), SReg2)
+        .addImm(0);
+      BuildMI(MBB, I, DL, get(AMDGPU::S_CSELECT_B64), SReg)
+        .addImm(0)
+        .addImm(-1);
+      BuildMI(MBB, I, DL, get(AMDGPU::V_CNDMASK_B32_e64), DstReg)
+        .addReg(FalseReg)
+        .addReg(TrueReg)
+        .addReg(SReg);
+      llvm_unreachable("Unhandled branch predicate EXECZ");
+      break;
+    }
+    default:
+      llvm_unreachable("invalid branch predicate");
+    }
+  } else {
+    llvm_unreachable("Can only handle Cond size 1 or 2");
+  }
+}
+
+unsigned SIInstrInfo::insertEQ(MachineBasicBlock *MBB,
+                               MachineBasicBlock::iterator I,
+                               const DebugLoc &DL,
+                               unsigned SrcReg, int Value) const {
+  MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
+  unsigned Reg = MRI.createVirtualRegister(&AMDGPU::SReg_64RegClass);
+  BuildMI(*MBB, I, DL, get(AMDGPU::V_CMP_EQ_I32_e64), Reg)
+    .addImm(Value)
+    .addReg(SrcReg);
+
+  return Reg;
+}
+
+unsigned SIInstrInfo::insertNE(MachineBasicBlock *MBB,
+                               MachineBasicBlock::iterator I,
+                               const DebugLoc &DL,
+                               unsigned SrcReg, int Value) const {
+  MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
+  unsigned Reg = MRI.createVirtualRegister(&AMDGPU::SReg_64RegClass);
+  BuildMI(*MBB, I, DL, get(AMDGPU::V_CMP_NE_I32_e64), Reg)
+    .addImm(Value)
+    .addReg(SrcReg);
+
+  return Reg;
+}
+
 unsigned SIInstrInfo::getMovOpcode(const TargetRegisterClass *DstRC) const {
 
   if (RI.getRegSizeInBits(*DstRC) == 32) {
     return RI.isSGPRClass(DstRC) ? AMDGPU::S_MOV_B32 : AMDGPU::V_MOV_B32_e32;
   } else if (RI.getRegSizeInBits(*DstRC) == 64 && RI.isSGPRClass(DstRC)) {
     return AMDGPU::S_MOV_B64;
   } else if (RI.getRegSizeInBits(*DstRC) == 64 && !RI.isSGPRClass(DstRC)) {
     return  AMDGPU::V_MOV_B64_PSEUDO;
void SIInstrInfo::insertWaitStates(MachineBasicBlock &MBB,
   }
 }
 
 void SIInstrInfo::insertNoop(MachineBasicBlock &MBB,
                              MachineBasicBlock::iterator MI) const {
   insertWaitStates(MBB, MI, 1);
 }
 
+void SIInstrInfo::insertReturn(MachineBasicBlock &MBB) const {
+  auto MF = MBB.getParent();
+  SIMachineFunctionInfo *Info = MF->getInfo<SIMachineFunctionInfo>();
+
+  assert(Info->isEntryFunction());
+
+  if (MBB.succ_empty()) {
+    bool HasNoTerminator = MBB.getFirstTerminator() == MBB.end();
+    if (HasNoTerminator)
+      BuildMI(MBB, MBB.end(), DebugLoc(),
+              get(Info->returnsVoid() ? AMDGPU::S_ENDPGM : AMDGPU::SI_RETURN_TO_EPILOG));
+  }
+}
+
 unsigned SIInstrInfo::getNumWaitStates(const MachineInstr &MI) const {
   switch (MI.getOpcode()) {
   default: return 1; // FIXME: Do wait states equal cycles?
 
   case AMDGPU::S_NOP:
     return MI.getOperand(0).getImm() + 1;
   }
 }
bool SIInstrInfo::analyzeBranchImpl(MachineBasicBlock &MBB,
                                     SmallVectorImpl<MachineOperand> &Cond,
                                     bool AllowModify) const {
   if (I->getOpcode() == AMDGPU::S_BRANCH) {
     // Unconditional Branch
     TBB = I->getOperand(0).getMBB();
     return false;
   }
 
+  MachineBasicBlock *CondBB = nullptr;
+
+  if (I->getOpcode() == AMDGPU::SI_NON_UNIFORM_BRCOND_PSEUDO) {
+    CondBB = I->getOperand(1).getMBB();
+    Cond.push_back(I->getOperand(0));
+  } else {
     BranchPredicate Pred = getBranchPredicate(I->getOpcode());
     if (Pred == INVALID_BR)
       return true;
 
-  MachineBasicBlock *CondBB = I->getOperand(0).getMBB();
+    CondBB = I->getOperand(0).getMBB();
     Cond.push_back(MachineOperand::CreateImm(Pred));
     Cond.push_back(I->getOperand(1)); // Save the branch register.
-
+  }
   ++I;
 
   if (I == MBB.end()) {
     // Conditional branch followed by fall-through.
     TBB = CondBB;
     return false;
   }
 
unsigned SIInstrInfo::insertBranch(MachineBasicBlock &MBB,
   if (!FBB && Cond.empty()) {
     BuildMI(&MBB, DL, get(AMDGPU::S_BRANCH))
       .addMBB(TBB);
     if (BytesAdded)
       *BytesAdded = 4;
     return 1;
   }
 
+  if(Cond.size() == 1 && Cond[0].isReg()) {
+     BuildMI(&MBB, DL, get(AMDGPU::SI_NON_UNIFORM_BRCOND_PSEUDO))
+       .add(Cond[0])
+       .addMBB(TBB);
+     return 1;
+  }
+
   assert(TBB && Cond[0].isImm());
 
   unsigned Opcode
     = getBranchOpcode(static_cast<BranchPredicate>(Cond[0].getImm()));
 
   if (!FBB) {
     Cond[1].isUndef();
     MachineInstr *CondBr =
unsigned SIInstrInfo::insertBranch(MachineBasicBlock &MBB,
   if (BytesAdded)
       *BytesAdded = 8;
 
   return 2;
 }
 
 bool SIInstrInfo::reverseBranchCondition(
   SmallVectorImpl<MachineOperand> &Cond) const {
-  assert(Cond.size() == 2);
+  if (Cond.size() != 2) {
+    return true;
+  }
+
+  if (Cond[0].isImm()) {
     Cond[0].setImm(-Cond[0].getImm());
     return false;
   }
 
+  return true;
+}
+
 bool SIInstrInfo::canInsertSelect(const MachineBasicBlock &MBB,
                                   ArrayRef<MachineOperand> Cond,
                                   unsigned TrueReg, unsigned FalseReg,
                                   int &CondCycles,
                                   int &TrueCycles, int &FalseCycles) const {
   switch (Cond[0].getImm()) {
   case VCCNZ:
   case VCCZ: {
bool SIInstrInfo::mayAccessFlatAddressSpace(const MachineInstr &MI) const {
 
   for (const MachineMemOperand *MMO : MI.memoperands()) {
     if (MMO->getAddrSpace() == AMDGPUASI.FLAT_ADDRESS)
       return true;
   }
   return false;
 }
 
+bool SIInstrInfo::isNonUniformBranchInstr(MachineInstr &Branch) const {
+  return Branch.getOpcode() == AMDGPU::SI_NON_UNIFORM_BRCOND_PSEUDO;
+}
+
+void SIInstrInfo::convertNonUniformIfRegion(MachineBasicBlock *IfEntry,
+                                            MachineBasicBlock *IfEnd) const {
+  MachineBasicBlock::iterator TI = IfEntry->getFirstTerminator();
+  assert(TI != IfEntry->end());
+
+  MachineInstr *Branch = &(*TI);
+  MachineFunction *MF = IfEntry->getParent();
+  MachineRegisterInfo &MRI = IfEntry->getParent()->getRegInfo();
+
+  if (Branch->getOpcode() == AMDGPU::SI_NON_UNIFORM_BRCOND_PSEUDO) {
+    unsigned DstReg = MRI.createVirtualRegister(&AMDGPU::SReg_64RegClass);
+    MachineInstr *SIIF =
+        BuildMI(*MF, Branch->getDebugLoc(), get(AMDGPU::SI_IF), DstReg)
+            .add(Branch->getOperand(0))
+            .add(Branch->getOperand(1));
+    MachineInstr *SIEND =
+        BuildMI(*MF, Branch->getDebugLoc(), get(AMDGPU::SI_END_CF))
+            .addReg(DstReg);
+
+    IfEntry->erase(TI);
+    IfEntry->insert(IfEntry->end(), SIIF);
+    IfEnd->insert(IfEnd->getFirstNonPHI(), SIEND);
+  }
+}
+
+void SIInstrInfo::convertNonUniformLoopRegion(
+    MachineBasicBlock *LoopEntry, MachineBasicBlock *LoopEnd) const {
+  MachineBasicBlock::iterator TI = LoopEnd->getFirstTerminator();
+  // We expect 2 terminators, one conditional and one unconditional.
+  assert(TI != LoopEnd->end());
+
+  MachineInstr *Branch = &(*TI);
+  MachineFunction *MF = LoopEnd->getParent();
+  MachineRegisterInfo &MRI = LoopEnd->getParent()->getRegInfo();
+
+  if (Branch->getOpcode() == AMDGPU::SI_NON_UNIFORM_BRCOND_PSEUDO) {
+
+    unsigned DstReg = MRI.createVirtualRegister(&AMDGPU::SReg_64RegClass);
+    unsigned BackEdgeReg = MRI.createVirtualRegister(&AMDGPU::SReg_64RegClass);
+    MachineInstrBuilder HeaderPHIBuilder =
+        BuildMI(*(MF), Branch->getDebugLoc(), get(TargetOpcode::PHI), DstReg);
+    for (MachineBasicBlock::pred_iterator PI = LoopEntry->pred_begin(),
+                                          E = LoopEntry->pred_end();
+         PI != E; ++PI) {
+      if (*PI == LoopEnd) {
+        HeaderPHIBuilder.addReg(BackEdgeReg);
+      } else {
+        MachineBasicBlock *PMBB = *PI;
+        unsigned ZeroReg = MRI.createVirtualRegister(&AMDGPU::SReg_64RegClass);
+        materializeImmediate(*PMBB, PMBB->getFirstTerminator(), DebugLoc(),
+                             ZeroReg, 0);
+        HeaderPHIBuilder.addReg(ZeroReg);
+      }
+      HeaderPHIBuilder.addMBB(*PI);
+    }
+    MachineInstr *HeaderPhi = HeaderPHIBuilder;
+    MachineInstr *SIIFBREAK = BuildMI(*(MF), Branch->getDebugLoc(),
+                                      get(AMDGPU::SI_IF_BREAK), BackEdgeReg)
+                                  .addReg(DstReg)
+                                  .add(Branch->getOperand(0));
+    MachineInstr *SILOOP =
+        BuildMI(*(MF), Branch->getDebugLoc(), get(AMDGPU::SI_LOOP))
+            .addReg(BackEdgeReg)
+            .addMBB(LoopEntry);
+
+    LoopEntry->insert(LoopEntry->begin(), HeaderPhi);
+    LoopEnd->erase(TI);
+    LoopEnd->insert(LoopEnd->end(), SIIFBREAK);
+    LoopEnd->insert(LoopEnd->end(), SILOOP);
+  }
+}
+
 ArrayRef<std::pair<int, const char *>>
 SIInstrInfo::getSerializableTargetIndices() const {
   static const std::pair<int, const char *> TargetIndices[] = {
       {AMDGPU::TI_CONSTDATA_START, "amdgpu-constdata-start"},
       {AMDGPU::TI_SCRATCH_RSRC_DWORD0, "amdgpu-scratch-rsrc-dword0"},
       {AMDGPU::TI_SCRATCH_RSRC_DWORD1, "amdgpu-scratch-rsrc-dword1"},
       {AMDGPU::TI_SCRATCH_RSRC_DWORD2, "amdgpu-scratch-rsrc-dword2"},
       {AMDGPU::TI_SCRATCH_RSRC_DWORD3, "amdgpu-scratch-rsrc-dword3"}};

llvm/trunk/lib/Target/AMDGPU/SIInstructions.td

def SI_MASK_BRANCH : VPseudoInstSI <
   let SchedRW = [];
   let hasNoSchedulingInfo = 1;
   let FixedSize = 1;
   let Size = 0;
 }
 
 let isTerminator = 1 in {
 
+ def SI_NON_UNIFORM_BRCOND_PSEUDO : CFPseudoInstSI <
+  (outs),
+  (ins SReg_64:$vcc, brtarget:$target),
+  [(brcond i1:$vcc, bb:$target)]> {
+    let Size = 12;
+}
+
 def SI_IF: CFPseudoInstSI <
   (outs SReg_64:$dst), (ins SReg_64:$vcc, brtarget:$target),
   [(set i64:$dst, (AMDGPUif i1:$vcc, bb:$target))], 1, 1> {
   let Constraints = "";
   let Size = 12;
   let hasSideEffects = 1;
 }