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

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