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