llvm/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp

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