lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp

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