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