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     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     DEBUG(dbgs() << "Considering Register: " << printReg(Reg, TRI) << "\n");
700     // If this is a source register to a PHI we are chaining, it
701     // must be live out.
702     if (PHIInfo.isSource(Reg)) {
703       DEBUG(dbgs() << "Add LiveOut (PHI): " << printReg(Reg, TRI) << "\n");
704       addLiveOut(Reg);
705     } else {
706       // If this is live out of the MBB
707       for (auto &UI : MRI->use_operands(Reg)) {
708         if (UI.getParent()->getParent() != MBB) {
709           DEBUG(dbgs() << "Add LiveOut (MBB " << printMBBReference(*MBB)
710                        << "): " << printReg(Reg, TRI) << "\n");
711           addLiveOut(Reg);
712         } else {
713           // If the use is in the same MBB we have to make sure
714           // it is after the def, otherwise it is live out in a loop
715           MachineInstr *UseInstr = UI.getParent();
716           for (MachineBasicBlock::instr_iterator
717                    MII = UseInstr->getIterator(),
718                    MIE = UseInstr->getParent()->instr_end();
719                MII != MIE; ++MII) {
720             if ((&(*MII)) == DefInstr) {
721               DEBUG(dbgs() << "Add LiveOut (Loop): " << printReg(Reg, TRI)
722                            << "\n");
723               addLiveOut(Reg);
724             }
725           }
726         }
727       }
728     }
729   }
730 }
731 
732 void LinearizedRegion::storeLiveOutRegRegion(RegionMRT *Region, unsigned Reg,
733                                              MachineInstr *DefInstr,
734                                              const MachineRegisterInfo *MRI,
735                                              const TargetRegisterInfo *TRI,
736                                              PHILinearize &PHIInfo) {
737   if (TRI->isVirtualRegister(Reg)) {
738     DEBUG(dbgs() << "Considering Register: " << printReg(Reg, TRI) << "\n");
739     for (auto &UI : MRI->use_operands(Reg)) {
740       if (!Region->contains(UI.getParent()->getParent())) {
741         DEBUG(dbgs() << "Add LiveOut (Region " << (void *)Region
742                      << "): " << printReg(Reg, TRI) << "\n");
743         addLiveOut(Reg);
744       }
745     }
746   }
747 }
748 
749 void LinearizedRegion::storeLiveOuts(MachineBasicBlock *MBB,
750                                      const MachineRegisterInfo *MRI,
751                                      const TargetRegisterInfo *TRI,
752                                      PHILinearize &PHIInfo) {
753   DEBUG(dbgs() << "-Store Live Outs Begin (" << printMBBReference(*MBB)
754                << ")-\n");
755   for (auto &II : *MBB) {
756     for (auto &RI : II.defs()) {
757       storeLiveOutReg(MBB, RI.getReg(), RI.getParent(), MRI, TRI, PHIInfo);
758     }
759     for (auto &IRI : II.implicit_operands()) {
760       if (IRI.isDef()) {
761         storeLiveOutReg(MBB, IRI.getReg(), IRI.getParent(), MRI, TRI, PHIInfo);
762       }
763     }
764   }
765 
766   // If we have a successor with a PHI, source coming from this MBB we have to
767   // add the register as live out
768   for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
769                                         E = MBB->succ_end();
770        SI != E; ++SI) {
771     for (auto &II : *(*SI)) {
772       if (II.isPHI()) {
773         MachineInstr &PHI = II;
774         int numPreds = getPHINumInputs(PHI);
775         for (int i = 0; i < numPreds; ++i) {
776           if (getPHIPred(PHI, i) == MBB) {
777             unsigned PHIReg = getPHISourceReg(PHI, i);
778             DEBUG(dbgs() << "Add LiveOut (PhiSource " << printMBBReference(*MBB)
779                          << " -> " << printMBBReference(*(*SI))
780                          << "): " << printReg(PHIReg, TRI) << "\n");
781             addLiveOut(PHIReg);
782           }
783         }
784       }
785     }
786   }
787 
788   DEBUG(dbgs() << "-Store Live Outs Endn-\n");
789 }
790 
791 void LinearizedRegion::storeMBBLiveOuts(MachineBasicBlock *MBB,
792                                         const MachineRegisterInfo *MRI,
793                                         const TargetRegisterInfo *TRI,
794                                         PHILinearize &PHIInfo,
795                                         RegionMRT *TopRegion) {
796   for (auto &II : *MBB) {
797     for (auto &RI : II.defs()) {
798       storeLiveOutRegRegion(TopRegion, RI.getReg(), RI.getParent(), MRI, TRI,
799                             PHIInfo);
800     }
801     for (auto &IRI : II.implicit_operands()) {
802       if (IRI.isDef()) {
803         storeLiveOutRegRegion(TopRegion, IRI.getReg(), IRI.getParent(), MRI,
804                               TRI, PHIInfo);
805       }
806     }
807   }
808 }
809 
810 void LinearizedRegion::storeLiveOuts(RegionMRT *Region,
811                                      const MachineRegisterInfo *MRI,
812                                      const TargetRegisterInfo *TRI,
813                                      PHILinearize &PHIInfo,
814                                      RegionMRT *CurrentTopRegion) {
815   MachineBasicBlock *Exit = Region->getSucc();
816 
817   RegionMRT *TopRegion =
818       CurrentTopRegion == nullptr ? Region : CurrentTopRegion;
819 
820   // Check if exit is end of function, if so, no live outs.
821   if (Exit == nullptr)
822     return;
823 
824   auto Children = Region->getChildren();
825   for (auto CI : *Children) {
826     if (CI->isMBB()) {
827       auto MBB = CI->getMBBMRT()->getMBB();
828       storeMBBLiveOuts(MBB, MRI, TRI, PHIInfo, TopRegion);
829     } else {
830       LinearizedRegion *SubRegion = CI->getRegionMRT()->getLinearizedRegion();
831       // We should be limited to only store registers that are live out from the
832       // lineaized region
833       for (auto MBBI : SubRegion->MBBs) {
834         storeMBBLiveOuts(MBBI, MRI, TRI, PHIInfo, TopRegion);
835       }
836     }
837   }
838 
839   if (CurrentTopRegion == nullptr) {
840     auto Succ = Region->getSucc();
841     for (auto &II : *Succ) {
842       if (II.isPHI()) {
843         MachineInstr &PHI = II;
844         int numPreds = getPHINumInputs(PHI);
845         for (int i = 0; i < numPreds; ++i) {
846           if (Region->contains(getPHIPred(PHI, i))) {
847             unsigned PHIReg = getPHISourceReg(PHI, i);
848             DEBUG(dbgs() << "Add Region LiveOut (" << (void *)Region
849                          << "): " << printReg(PHIReg, TRI) << "\n");
850             addLiveOut(PHIReg);
851           }
852         }
853       }
854     }
855   }
856 }
857 
858 #ifndef NDEBUG
859 void LinearizedRegion::print(raw_ostream &OS, const TargetRegisterInfo *TRI) {
860   OS << "Linearized Region {";
861   bool IsFirst = true;
862   for (const auto &MBB : MBBs) {
863     if (IsFirst) {
864       IsFirst = false;
865     } else {
866       OS << " ,";
867     }
868     OS << MBB->getNumber();
869   }
870   OS << "} (" << Entry->getNumber() << ", "
871      << (Exit == nullptr ? -1 : Exit->getNumber())
872      << "): In:" << printReg(getBBSelectRegIn(), TRI)
873      << " Out:" << printReg(getBBSelectRegOut(), TRI) << " {";
874   for (auto &LI : LiveOuts) {
875     OS << printReg(LI, TRI) << " ";
876   }
877   OS << "} \n";
878 }
879 #endif
880 
881 unsigned LinearizedRegion::getBBSelectRegIn() {
882   return getRegionMRT()->getBBSelectRegIn();
883 }
884 
885 unsigned LinearizedRegion::getBBSelectRegOut() {
886   return getRegionMRT()->getBBSelectRegOut();
887 }
888 
889 void LinearizedRegion::setHasLoop(bool Value) { HasLoop = Value; }
890 
891 bool LinearizedRegion::getHasLoop() { return HasLoop; }
892 
893 void LinearizedRegion::addLiveOut(unsigned VReg) { LiveOuts.insert(VReg); }
894 
895 void LinearizedRegion::removeLiveOut(unsigned Reg) {
896   if (isLiveOut(Reg))
897     LiveOuts.erase(Reg);
898 }
899 
900 void LinearizedRegion::replaceLiveOut(unsigned OldReg, unsigned NewReg) {
901   if (isLiveOut(OldReg)) {
902     removeLiveOut(OldReg);
903     addLiveOut(NewReg);
904   }
905 }
906 
907 void LinearizedRegion::replaceRegister(unsigned Register, unsigned NewRegister,
908                                        MachineRegisterInfo *MRI,
909                                        bool ReplaceInside, bool ReplaceOutside,
910                                        bool IncludeLoopPHI) {
911   assert(Register != NewRegister && "Cannot replace a reg with itself");
912 
913   DEBUG(dbgs() << "Pepareing to replace register (region): "
914                << printReg(Register, MRI->getTargetRegisterInfo()) << " with "
915                << printReg(NewRegister, MRI->getTargetRegisterInfo()) << "\n");
916 
917   // If we are replacing outside, we also need to update the LiveOuts
918   if (ReplaceOutside &&
919       (isLiveOut(Register) || this->getParent()->isLiveOut(Register))) {
920     LinearizedRegion *Current = this;
921     while (Current != nullptr && Current->getEntry() != nullptr) {
922       DEBUG(dbgs() << "Region before register replace\n");
923       DEBUG(Current->print(dbgs(), MRI->getTargetRegisterInfo()));
924       Current->replaceLiveOut(Register, NewRegister);
925       DEBUG(dbgs() << "Region after register replace\n");
926       DEBUG(Current->print(dbgs(), MRI->getTargetRegisterInfo()));
927       Current = Current->getParent();
928     }
929   }
930 
931   for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Register),
932                                          E = MRI->reg_end();
933        I != E;) {
934     MachineOperand &O = *I;
935     ++I;
936 
937     // We don't rewrite defs.
938     if (O.isDef())
939       continue;
940 
941     bool IsInside = contains(O.getParent()->getParent());
942     bool IsLoopPHI = IsInside && (O.getParent()->isPHI() &&
943                                   O.getParent()->getParent() == getEntry());
944     bool ShouldReplace = (IsInside && ReplaceInside) ||
945                          (!IsInside && ReplaceOutside) ||
946                          (IncludeLoopPHI && IsLoopPHI);
947     if (ShouldReplace) {
948 
949       if (TargetRegisterInfo::isPhysicalRegister(NewRegister)) {
950         DEBUG(dbgs() << "Trying to substitute physical register: "
951                      << printReg(NewRegister, MRI->getTargetRegisterInfo())
952                      << "\n");
953         llvm_unreachable("Cannot substitute physical registers");
954       } else {
955         DEBUG(dbgs() << "Replacing register (region): "
956                      << printReg(Register, MRI->getTargetRegisterInfo())
957                      << " with "
958                      << printReg(NewRegister, MRI->getTargetRegisterInfo())
959                      << "\n");
960         O.setReg(NewRegister);
961       }
962     }
963   }
964 }
965 
966 void LinearizedRegion::replaceRegisterInsideRegion(unsigned Register,
967                                                    unsigned NewRegister,
968                                                    bool IncludeLoopPHIs,
969                                                    MachineRegisterInfo *MRI) {
970   replaceRegister(Register, NewRegister, MRI, true, false, IncludeLoopPHIs);
971 }
972 
973 void LinearizedRegion::replaceRegisterOutsideRegion(unsigned Register,
974                                                     unsigned NewRegister,
975                                                     bool IncludeLoopPHIs,
976                                                     MachineRegisterInfo *MRI) {
977   replaceRegister(Register, NewRegister, MRI, false, true, IncludeLoopPHIs);
978 }
979 
980 DenseSet<unsigned> *LinearizedRegion::getLiveOuts() { return &LiveOuts; }
981 
982 void LinearizedRegion::setEntry(MachineBasicBlock *NewEntry) {
983   Entry = NewEntry;
984 }
985 
986 MachineBasicBlock *LinearizedRegion::getEntry() { return Entry; }
987 
988 void LinearizedRegion::setExit(MachineBasicBlock *NewExit) { Exit = NewExit; }
989 
990 MachineBasicBlock *LinearizedRegion::getExit() { return Exit; }
991 
992 void LinearizedRegion::addMBB(MachineBasicBlock *MBB) { MBBs.insert(MBB); }
993 
994 void LinearizedRegion::addMBBs(LinearizedRegion *InnerRegion) {
995   for (const auto &MBB : InnerRegion->MBBs) {
996     addMBB(MBB);
997   }
998 }
999 
1000 bool LinearizedRegion::contains(MachineBasicBlock *MBB) {
1001   return MBBs.count(MBB) == 1;
1002 }
1003 
1004 bool LinearizedRegion::isLiveOut(unsigned Reg) {
1005   return LiveOuts.count(Reg) == 1;
1006 }
1007 
1008 bool LinearizedRegion::hasNoDef(unsigned Reg, MachineRegisterInfo *MRI) {
1009   return MRI->def_begin(Reg) == MRI->def_end();
1010 }
1011 
1012 // After the code has been structurized, what was flagged as kills
1013 // before are no longer register kills.
1014 void LinearizedRegion::removeFalseRegisterKills(MachineRegisterInfo *MRI) {
1015   const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
1016   for (auto MBBI : MBBs) {
1017     MachineBasicBlock *MBB = MBBI;
1018     for (auto &II : *MBB) {
1019       for (auto &RI : II.uses()) {
1020         if (RI.isReg()) {
1021           unsigned Reg = RI.getReg();
1022           if (TRI->isVirtualRegister(Reg)) {
1023             if (hasNoDef(Reg, MRI))
1024               continue;
1025             if (!MRI->hasOneDef(Reg)) {
1026               DEBUG(this->getEntry()->getParent()->dump());
1027               DEBUG(dbgs() << printReg(Reg, TRI) << "\n");
1028             }
1029 
1030             if (MRI->def_begin(Reg) == MRI->def_end()) {
1031               DEBUG(dbgs() << "Register "
1032                            << printReg(Reg, MRI->getTargetRegisterInfo())
1033                            << " has NO defs\n");
1034             } else if (!MRI->hasOneDef(Reg)) {
1035               DEBUG(dbgs() << "Register "
1036                            << printReg(Reg, MRI->getTargetRegisterInfo())
1037                            << " has multiple defs\n");
1038             }
1039 
1040             assert(MRI->hasOneDef(Reg) && "Register has multiple definitions");
1041             MachineOperand *Def = &(*(MRI->def_begin(Reg)));
1042             MachineOperand *UseOperand = &(RI);
1043             bool UseIsOutsideDefMBB = Def->getParent()->getParent() != MBB;
1044             if (UseIsOutsideDefMBB && UseOperand->isKill()) {
1045               DEBUG(dbgs() << "Removing kill flag on register: "
1046                            << printReg(Reg, TRI) << "\n");
1047               UseOperand->setIsKill(false);
1048             }
1049           }
1050         }
1051       }
1052     }
1053   }
1054 }
1055 
1056 void LinearizedRegion::initLiveOut(RegionMRT *Region,
1057                                    const MachineRegisterInfo *MRI,
1058                                    const TargetRegisterInfo *TRI,
1059                                    PHILinearize &PHIInfo) {
1060   storeLiveOuts(Region, MRI, TRI, PHIInfo);
1061 }
1062 
1063 LinearizedRegion::LinearizedRegion(MachineBasicBlock *MBB,
1064                                    const MachineRegisterInfo *MRI,
1065                                    const TargetRegisterInfo *TRI,
1066                                    PHILinearize &PHIInfo) {
1067   setEntry(MBB);
1068   setExit(MBB);
1069   storeLiveOuts(MBB, MRI, TRI, PHIInfo);
1070   MBBs.insert(MBB);
1071   Parent = nullptr;
1072 }
1073 
1074 LinearizedRegion::LinearizedRegion() {
1075   setEntry(nullptr);
1076   setExit(nullptr);
1077   Parent = nullptr;
1078 }
1079 
1080 namespace {
1081 
1082 class AMDGPUMachineCFGStructurizer : public MachineFunctionPass {
1083 private:
1084   const MachineRegionInfo *Regions;
1085   const SIInstrInfo *TII;
1086   const TargetRegisterInfo *TRI;
1087   MachineRegisterInfo *MRI;
1088   unsigned BBSelectRegister;
1089   PHILinearize PHIInfo;
1090   DenseMap<MachineBasicBlock *, MachineBasicBlock *> FallthroughMap;
1091   RegionMRT *RMRT;
1092 
1093   void getPHIRegionIndices(RegionMRT *Region, MachineInstr &PHI,
1094                            SmallVector<unsigned, 2> &RegionIndices);
1095   void getPHIRegionIndices(LinearizedRegion *Region, MachineInstr &PHI,
1096                            SmallVector<unsigned, 2> &RegionIndices);
1097   void getPHINonRegionIndices(LinearizedRegion *Region, MachineInstr &PHI,
1098                               SmallVector<unsigned, 2> &PHINonRegionIndices);
1099 
1100   void storePHILinearizationInfoDest(
1101       unsigned LDestReg, MachineInstr &PHI,
1102       SmallVector<unsigned, 2> *RegionIndices = nullptr);
1103 
1104   unsigned storePHILinearizationInfo(MachineInstr &PHI,
1105                                      SmallVector<unsigned, 2> *RegionIndices);
1106 
1107   void extractKilledPHIs(MachineBasicBlock *MBB);
1108 
1109   bool shrinkPHI(MachineInstr &PHI, SmallVector<unsigned, 2> &PHIIndices,
1110                  unsigned *ReplaceReg);
1111 
1112   bool shrinkPHI(MachineInstr &PHI, unsigned CombinedSourceReg,
1113                  MachineBasicBlock *SourceMBB,
1114                  SmallVector<unsigned, 2> &PHIIndices, unsigned *ReplaceReg);
1115 
1116   void replacePHI(MachineInstr &PHI, unsigned CombinedSourceReg,
1117                   MachineBasicBlock *LastMerge,
1118                   SmallVector<unsigned, 2> &PHIRegionIndices);
1119   void replaceEntryPHI(MachineInstr &PHI, unsigned CombinedSourceReg,
1120                        MachineBasicBlock *IfMBB,
1121                        SmallVector<unsigned, 2> &PHIRegionIndices);
1122   void replaceLiveOutRegs(MachineInstr &PHI,
1123                           SmallVector<unsigned, 2> &PHIRegionIndices,
1124                           unsigned CombinedSourceReg,
1125                           LinearizedRegion *LRegion);
1126   void rewriteRegionExitPHI(RegionMRT *Region, MachineBasicBlock *LastMerge,
1127                             MachineInstr &PHI, LinearizedRegion *LRegion);
1128 
1129   void rewriteRegionExitPHIs(RegionMRT *Region, MachineBasicBlock *LastMerge,
1130                              LinearizedRegion *LRegion);
1131   void rewriteRegionEntryPHI(LinearizedRegion *Region, MachineBasicBlock *IfMBB,
1132                              MachineInstr &PHI);
1133   void rewriteRegionEntryPHIs(LinearizedRegion *Region,
1134                               MachineBasicBlock *IfMBB);
1135 
1136   bool regionIsSimpleIf(RegionMRT *Region);
1137 
1138   void transformSimpleIfRegion(RegionMRT *Region);
1139 
1140   void eliminateDeadBranchOperands(MachineBasicBlock::instr_iterator &II);
1141 
1142   void insertUnconditionalBranch(MachineBasicBlock *MBB,
1143                                  MachineBasicBlock *Dest,
1144                                  const DebugLoc &DL = DebugLoc());
1145 
1146   MachineBasicBlock *createLinearizedExitBlock(RegionMRT *Region);
1147 
1148   void insertMergePHI(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB,
1149                       MachineBasicBlock *MergeBB, unsigned DestRegister,
1150                       unsigned IfSourceRegister, unsigned CodeSourceRegister,
1151                       bool IsUndefIfSource = false);
1152 
1153   MachineBasicBlock *createIfBlock(MachineBasicBlock *MergeBB,
1154                                    MachineBasicBlock *CodeBBStart,
1155                                    MachineBasicBlock *CodeBBEnd,
1156                                    MachineBasicBlock *SelectBB, unsigned IfReg,
1157                                    bool InheritPreds);
1158 
1159   void prunePHIInfo(MachineBasicBlock *MBB);
1160   void createEntryPHI(LinearizedRegion *CurrentRegion, unsigned DestReg);
1161 
1162   void createEntryPHIs(LinearizedRegion *CurrentRegion);
1163   void resolvePHIInfos(MachineBasicBlock *FunctionEntry);
1164 
1165   void replaceRegisterWith(unsigned Register, unsigned NewRegister);
1166 
1167   MachineBasicBlock *createIfRegion(MachineBasicBlock *MergeBB,
1168                                     MachineBasicBlock *CodeBB,
1169                                     LinearizedRegion *LRegion,
1170                                     unsigned BBSelectRegIn,
1171                                     unsigned BBSelectRegOut);
1172 
1173   MachineBasicBlock *
1174   createIfRegion(MachineBasicBlock *MergeMBB, LinearizedRegion *InnerRegion,
1175                  LinearizedRegion *CurrentRegion, MachineBasicBlock *SelectBB,
1176                  unsigned BBSelectRegIn, unsigned BBSelectRegOut);
1177   void ensureCondIsNotKilled(SmallVector<MachineOperand, 1> Cond);
1178 
1179   void rewriteCodeBBTerminator(MachineBasicBlock *CodeBB,
1180                                MachineBasicBlock *MergeBB,
1181                                unsigned BBSelectReg);
1182 
1183   MachineInstr *getDefInstr(unsigned Reg);
1184   void insertChainedPHI(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB,
1185                         MachineBasicBlock *MergeBB,
1186                         LinearizedRegion *InnerRegion, unsigned DestReg,
1187                         unsigned SourceReg);
1188   bool containsDef(MachineBasicBlock *MBB, LinearizedRegion *InnerRegion,
1189                    unsigned Register);
1190   void rewriteLiveOutRegs(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB,
1191                           MachineBasicBlock *MergeBB,
1192                           LinearizedRegion *InnerRegion,
1193                           LinearizedRegion *LRegion);
1194 
1195   void splitLoopPHI(MachineInstr &PHI, MachineBasicBlock *Entry,
1196                     MachineBasicBlock *EntrySucc, LinearizedRegion *LRegion);
1197   void splitLoopPHIs(MachineBasicBlock *Entry, MachineBasicBlock *EntrySucc,
1198                      LinearizedRegion *LRegion);
1199 
1200   MachineBasicBlock *splitExit(LinearizedRegion *LRegion);
1201 
1202   MachineBasicBlock *splitEntry(LinearizedRegion *LRegion);
1203 
1204   LinearizedRegion *initLinearizedRegion(RegionMRT *Region);
1205 
1206   bool structurizeComplexRegion(RegionMRT *Region);
1207 
1208   bool structurizeRegion(RegionMRT *Region);
1209 
1210   bool structurizeRegions(RegionMRT *Region, bool isTopRegion);
1211 
1212 public:
1213   static char ID;
1214 
1215   AMDGPUMachineCFGStructurizer() : MachineFunctionPass(ID) {
1216     initializeAMDGPUMachineCFGStructurizerPass(*PassRegistry::getPassRegistry());
1217   }
1218 
1219   void getAnalysisUsage(AnalysisUsage &AU) const override {
1220     AU.addRequired<MachineRegionInfoPass>();
1221     MachineFunctionPass::getAnalysisUsage(AU);
1222   }
1223 
1224   void initFallthroughMap(MachineFunction &MF);
1225 
1226   void createLinearizedRegion(RegionMRT *Region, unsigned SelectOut);
1227 
1228   unsigned initializeSelectRegisters(MRT *MRT, unsigned ExistingExitReg,
1229                                      MachineRegisterInfo *MRI,
1230                                      const SIInstrInfo *TII);
1231 
1232   void setRegionMRT(RegionMRT *RegionTree) { RMRT = RegionTree; }
1233 
1234   RegionMRT *getRegionMRT() { return RMRT; }
1235 
1236   bool runOnMachineFunction(MachineFunction &MF) override;
1237 };
1238 
1239 } // end anonymous namespace
1240 
1241 char AMDGPUMachineCFGStructurizer::ID = 0;
1242 
1243 bool AMDGPUMachineCFGStructurizer::regionIsSimpleIf(RegionMRT *Region) {
1244   MachineBasicBlock *Entry = Region->getEntry();
1245   MachineBasicBlock *Succ = Region->getSucc();
1246   bool FoundBypass = false;
1247   bool FoundIf = false;
1248 
1249   if (Entry->succ_size() != 2) {
1250     return false;
1251   }
1252 
1253   for (MachineBasicBlock::const_succ_iterator SI = Entry->succ_begin(),
1254                                               E = Entry->succ_end();
1255        SI != E; ++SI) {
1256     MachineBasicBlock *Current = *SI;
1257 
1258     if (Current == Succ) {
1259       FoundBypass = true;
1260     } else if ((Current->succ_size() == 1) &&
1261                *(Current->succ_begin()) == Succ) {
1262       FoundIf = true;
1263     }
1264   }
1265 
1266   return FoundIf && FoundBypass;
1267 }
1268 
1269 void AMDGPUMachineCFGStructurizer::transformSimpleIfRegion(RegionMRT *Region) {
1270   MachineBasicBlock *Entry = Region->getEntry();
1271   MachineBasicBlock *Exit = Region->getExit();
1272   TII->convertNonUniformIfRegion(Entry, Exit);
1273 }
1274 
1275 static void fixMBBTerminator(MachineBasicBlock *MBB) {
1276   if (MBB->succ_size() == 1) {
1277     auto *Succ = *(MBB->succ_begin());
1278     for (auto &TI : MBB->terminators()) {
1279       for (auto &UI : TI.uses()) {
1280         if (UI.isMBB() && UI.getMBB() != Succ) {
1281           UI.setMBB(Succ);
1282         }
1283       }
1284     }
1285   }
1286 }
1287 
1288 static void fixRegionTerminator(RegionMRT *Region) {
1289   MachineBasicBlock *InternalSucc = nullptr;
1290   MachineBasicBlock *ExternalSucc = nullptr;
1291   LinearizedRegion *LRegion = Region->getLinearizedRegion();
1292   auto Exit = LRegion->getExit();
1293 
1294   SmallPtrSet<MachineBasicBlock *, 2> Successors;
1295   for (MachineBasicBlock::const_succ_iterator SI = Exit->succ_begin(),
1296                                               SE = Exit->succ_end();
1297        SI != SE; ++SI) {
1298     MachineBasicBlock *Succ = *SI;
1299     if (LRegion->contains(Succ)) {
1300       // Do not allow re-assign
1301       assert(InternalSucc == nullptr);
1302       InternalSucc = Succ;
1303     } else {
1304       // Do not allow re-assign
1305       assert(ExternalSucc == nullptr);
1306       ExternalSucc = Succ;
1307     }
1308   }
1309 
1310   for (auto &TI : Exit->terminators()) {
1311     for (auto &UI : TI.uses()) {
1312       if (UI.isMBB()) {
1313         auto Target = UI.getMBB();
1314         if (Target != InternalSucc && Target != ExternalSucc) {
1315           UI.setMBB(ExternalSucc);
1316         }
1317       }
1318     }
1319   }
1320 }
1321 
1322 // If a region region is just a sequence of regions (and the exit
1323 // block in the case of the top level region), we can simply skip
1324 // linearizing it, because it is already linear
1325 bool regionIsSequence(RegionMRT *Region) {
1326   auto Children = Region->getChildren();
1327   for (auto CI : *Children) {
1328     if (!CI->isRegion()) {
1329       if (CI->getMBBMRT()->getMBB()->succ_size() > 1) {
1330         return false;
1331       }
1332     }
1333   }
1334   return true;
1335 }
1336 
1337 void fixupRegionExits(RegionMRT *Region) {
1338   auto Children = Region->getChildren();
1339   for (auto CI : *Children) {
1340     if (!CI->isRegion()) {
1341       fixMBBTerminator(CI->getMBBMRT()->getMBB());
1342     } else {
1343       fixRegionTerminator(CI->getRegionMRT());
1344     }
1345   }
1346 }
1347 
1348 void AMDGPUMachineCFGStructurizer::getPHIRegionIndices(
1349     RegionMRT *Region, MachineInstr &PHI,
1350     SmallVector<unsigned, 2> &PHIRegionIndices) {
1351   unsigned NumInputs = getPHINumInputs(PHI);
1352   for (unsigned i = 0; i < NumInputs; ++i) {
1353     MachineBasicBlock *Pred = getPHIPred(PHI, i);
1354     if (Region->contains(Pred)) {
1355       PHIRegionIndices.push_back(i);
1356     }
1357   }
1358 }
1359 
1360 void AMDGPUMachineCFGStructurizer::getPHIRegionIndices(
1361     LinearizedRegion *Region, MachineInstr &PHI,
1362     SmallVector<unsigned, 2> &PHIRegionIndices) {
1363   unsigned NumInputs = getPHINumInputs(PHI);
1364   for (unsigned i = 0; i < NumInputs; ++i) {
1365     MachineBasicBlock *Pred = getPHIPred(PHI, i);
1366     if (Region->contains(Pred)) {
1367       PHIRegionIndices.push_back(i);
1368     }
1369   }
1370 }
1371 
1372 void AMDGPUMachineCFGStructurizer::getPHINonRegionIndices(
1373     LinearizedRegion *Region, MachineInstr &PHI,
1374     SmallVector<unsigned, 2> &PHINonRegionIndices) {
1375   unsigned NumInputs = getPHINumInputs(PHI);
1376   for (unsigned i = 0; i < NumInputs; ++i) {
1377     MachineBasicBlock *Pred = getPHIPred(PHI, i);
1378     if (!Region->contains(Pred)) {
1379       PHINonRegionIndices.push_back(i);
1380     }
1381   }
1382 }
1383 
1384 void AMDGPUMachineCFGStructurizer::storePHILinearizationInfoDest(
1385     unsigned LDestReg, MachineInstr &PHI,
1386     SmallVector<unsigned, 2> *RegionIndices) {
1387   if (RegionIndices) {
1388     for (auto i : *RegionIndices) {
1389       PHIInfo.addSource(LDestReg, getPHISourceReg(PHI, i), getPHIPred(PHI, i));
1390     }
1391   } else {
1392     unsigned NumInputs = getPHINumInputs(PHI);
1393     for (unsigned i = 0; i < NumInputs; ++i) {
1394       PHIInfo.addSource(LDestReg, getPHISourceReg(PHI, i), getPHIPred(PHI, i));
1395     }
1396   }
1397 }
1398 
1399 unsigned AMDGPUMachineCFGStructurizer::storePHILinearizationInfo(
1400     MachineInstr &PHI, SmallVector<unsigned, 2> *RegionIndices) {
1401   unsigned DestReg = getPHIDestReg(PHI);
1402   unsigned LinearizeDestReg =
1403       MRI->createVirtualRegister(MRI->getRegClass(DestReg));
1404   PHIInfo.addDest(LinearizeDestReg, PHI.getDebugLoc());
1405   storePHILinearizationInfoDest(LinearizeDestReg, PHI, RegionIndices);
1406   return LinearizeDestReg;
1407 }
1408 
1409 void AMDGPUMachineCFGStructurizer::extractKilledPHIs(MachineBasicBlock *MBB) {
1410   // We need to create a new chain for the killed phi, but there is no
1411   // need to do the renaming outside or inside the block.
1412   SmallPtrSet<MachineInstr *, 2> PHIs;
1413   for (MachineBasicBlock::instr_iterator I = MBB->instr_begin(),
1414                                          E = MBB->instr_end();
1415        I != E; ++I) {
1416     MachineInstr &Instr = *I;
1417     if (Instr.isPHI()) {
1418       unsigned PHIDestReg = getPHIDestReg(Instr);
1419       DEBUG(dbgs() << "Extractking killed phi:\n");
1420       DEBUG(Instr.dump());
1421       PHIs.insert(&Instr);
1422       PHIInfo.addDest(PHIDestReg, Instr.getDebugLoc());
1423       storePHILinearizationInfoDest(PHIDestReg, Instr);
1424     }
1425   }
1426 
1427   for (auto PI : PHIs) {
1428     PI->eraseFromParent();
1429   }
1430 }
1431 
1432 static bool isPHIRegionIndex(SmallVector<unsigned, 2> PHIRegionIndices,
1433                              unsigned Index) {
1434   for (auto i : PHIRegionIndices) {
1435     if (i == Index)
1436       return true;
1437   }
1438   return false;
1439 }
1440 
1441 bool AMDGPUMachineCFGStructurizer::shrinkPHI(MachineInstr &PHI,
1442                                        SmallVector<unsigned, 2> &PHIIndices,
1443                                        unsigned *ReplaceReg) {
1444   return shrinkPHI(PHI, 0, nullptr, PHIIndices, ReplaceReg);
1445 }
1446 
1447 bool AMDGPUMachineCFGStructurizer::shrinkPHI(MachineInstr &PHI,
1448                                        unsigned CombinedSourceReg,
1449                                        MachineBasicBlock *SourceMBB,
1450                                        SmallVector<unsigned, 2> &PHIIndices,
1451                                        unsigned *ReplaceReg) {
1452   DEBUG(dbgs() << "Shrink PHI: ");
1453   DEBUG(PHI.dump());
1454   DEBUG(dbgs() << " to " << printReg(getPHIDestReg(PHI), TRI) << " = PHI(");
1455 
1456   bool Replaced = false;
1457   unsigned NumInputs = getPHINumInputs(PHI);
1458   int SingleExternalEntryIndex = -1;
1459   for (unsigned i = 0; i < NumInputs; ++i) {
1460     if (!isPHIRegionIndex(PHIIndices, i)) {
1461       if (SingleExternalEntryIndex == -1) {
1462         // Single entry
1463         SingleExternalEntryIndex = i;
1464       } else {
1465         // Multiple entries
1466         SingleExternalEntryIndex = -2;
1467       }
1468     }
1469   }
1470 
1471   if (SingleExternalEntryIndex > -1) {
1472     *ReplaceReg = getPHISourceReg(PHI, SingleExternalEntryIndex);
1473     // We should not rewrite the code, we should only pick up the single value
1474     // that represents the shrunk PHI.
1475     Replaced = true;
1476   } else {
1477     MachineBasicBlock *MBB = PHI.getParent();
1478     MachineInstrBuilder MIB =
1479         BuildMI(*MBB, PHI, PHI.getDebugLoc(), TII->get(TargetOpcode::PHI),
1480                 getPHIDestReg(PHI));
1481     if (SourceMBB) {
1482       MIB.addReg(CombinedSourceReg);
1483       MIB.addMBB(SourceMBB);
1484       DEBUG(dbgs() << printReg(CombinedSourceReg, TRI) << ", "
1485                    << printMBBReference(*SourceMBB));
1486     }
1487 
1488     for (unsigned i = 0; i < NumInputs; ++i) {
1489       if (isPHIRegionIndex(PHIIndices, i)) {
1490         continue;
1491       }
1492       unsigned SourceReg = getPHISourceReg(PHI, i);
1493       MachineBasicBlock *SourcePred = getPHIPred(PHI, i);
1494       MIB.addReg(SourceReg);
1495       MIB.addMBB(SourcePred);
1496       DEBUG(dbgs() << printReg(SourceReg, TRI) << ", "
1497                    << printMBBReference(*SourcePred));
1498     }
1499     DEBUG(dbgs() << ")\n");
1500   }
1501   PHI.eraseFromParent();
1502   return Replaced;
1503 }
1504 
1505 void AMDGPUMachineCFGStructurizer::replacePHI(
1506     MachineInstr &PHI, unsigned CombinedSourceReg, MachineBasicBlock *LastMerge,
1507     SmallVector<unsigned, 2> &PHIRegionIndices) {
1508   DEBUG(dbgs() << "Replace PHI: ");
1509   DEBUG(PHI.dump());
1510   DEBUG(dbgs() << " with " << printReg(getPHIDestReg(PHI), TRI) << " = PHI(");
1511 
1512   bool HasExternalEdge = false;
1513   unsigned NumInputs = getPHINumInputs(PHI);
1514   for (unsigned i = 0; i < NumInputs; ++i) {
1515     if (!isPHIRegionIndex(PHIRegionIndices, i)) {
1516       HasExternalEdge = true;
1517     }
1518   }
1519 
1520   if (HasExternalEdge) {
1521     MachineBasicBlock *MBB = PHI.getParent();
1522     MachineInstrBuilder MIB =
1523         BuildMI(*MBB, PHI, PHI.getDebugLoc(), TII->get(TargetOpcode::PHI),
1524                 getPHIDestReg(PHI));
1525     MIB.addReg(CombinedSourceReg);
1526     MIB.addMBB(LastMerge);
1527     DEBUG(dbgs() << printReg(CombinedSourceReg, TRI) << ", "
1528                  << printMBBReference(*LastMerge));
1529     for (unsigned i = 0; i < NumInputs; ++i) {
1530       if (isPHIRegionIndex(PHIRegionIndices, i)) {
1531         continue;
1532       }
1533       unsigned SourceReg = getPHISourceReg(PHI, i);
1534       MachineBasicBlock *SourcePred = getPHIPred(PHI, i);
1535       MIB.addReg(SourceReg);
1536       MIB.addMBB(SourcePred);
1537       DEBUG(dbgs() << printReg(SourceReg, TRI) << ", "
1538                    << printMBBReference(*SourcePred));
1539     }
1540     DEBUG(dbgs() << ")\n");
1541   } else {
1542     replaceRegisterWith(getPHIDestReg(PHI), CombinedSourceReg);
1543   }
1544   PHI.eraseFromParent();
1545 }
1546 
1547 void AMDGPUMachineCFGStructurizer::replaceEntryPHI(
1548     MachineInstr &PHI, unsigned CombinedSourceReg, MachineBasicBlock *IfMBB,
1549     SmallVector<unsigned, 2> &PHIRegionIndices) {
1550   DEBUG(dbgs() << "Replace entry PHI: ");
1551   DEBUG(PHI.dump());
1552   DEBUG(dbgs() << " with ");
1553 
1554   unsigned NumInputs = getPHINumInputs(PHI);
1555   unsigned NumNonRegionInputs = NumInputs;
1556   for (unsigned i = 0; i < NumInputs; ++i) {
1557     if (isPHIRegionIndex(PHIRegionIndices, i)) {
1558       NumNonRegionInputs--;
1559     }
1560   }
1561 
1562   if (NumNonRegionInputs == 0) {
1563     auto DestReg = getPHIDestReg(PHI);
1564     replaceRegisterWith(DestReg, CombinedSourceReg);
1565     DEBUG(dbgs() << " register " << printReg(CombinedSourceReg, TRI) << "\n");
1566     PHI.eraseFromParent();
1567   } else {
1568     DEBUG(dbgs() << printReg(getPHIDestReg(PHI), TRI) << " = PHI(");
1569     MachineBasicBlock *MBB = PHI.getParent();
1570     MachineInstrBuilder MIB =
1571         BuildMI(*MBB, PHI, PHI.getDebugLoc(), TII->get(TargetOpcode::PHI),
1572                 getPHIDestReg(PHI));
1573     MIB.addReg(CombinedSourceReg);
1574     MIB.addMBB(IfMBB);
1575     DEBUG(dbgs() << printReg(CombinedSourceReg, TRI) << ", "
1576                  << printMBBReference(*IfMBB));
1577     unsigned NumInputs = getPHINumInputs(PHI);
1578     for (unsigned i = 0; i < NumInputs; ++i) {
1579       if (isPHIRegionIndex(PHIRegionIndices, i)) {
1580         continue;
1581       }
1582       unsigned SourceReg = getPHISourceReg(PHI, i);
1583       MachineBasicBlock *SourcePred = getPHIPred(PHI, i);
1584       MIB.addReg(SourceReg);
1585       MIB.addMBB(SourcePred);
1586       DEBUG(dbgs() << printReg(SourceReg, TRI) << ", "
1587                    << printMBBReference(*SourcePred));
1588     }
1589     DEBUG(dbgs() << ")\n");
1590     PHI.eraseFromParent();
1591   }
1592 }
1593 
1594 void AMDGPUMachineCFGStructurizer::replaceLiveOutRegs(
1595     MachineInstr &PHI, SmallVector<unsigned, 2> &PHIRegionIndices,
1596     unsigned CombinedSourceReg, LinearizedRegion *LRegion) {
1597   bool WasLiveOut = false;
1598   for (auto PII : PHIRegionIndices) {
1599     unsigned Reg = getPHISourceReg(PHI, PII);
1600     if (LRegion->isLiveOut(Reg)) {
1601       bool IsDead = true;
1602 
1603       // Check if register is live out of the basic block
1604       MachineBasicBlock *DefMBB = getDefInstr(Reg)->getParent();
1605       for (auto UI = MRI->use_begin(Reg), E = MRI->use_end(); UI != E; ++UI) {
1606         if ((*UI).getParent()->getParent() != DefMBB) {
1607           IsDead = false;
1608         }
1609       }
1610 
1611       DEBUG(dbgs() << "Register " << printReg(Reg, TRI) << " is "
1612                    << (IsDead ? "dead" : "alive") << " after PHI replace\n");
1613       if (IsDead) {
1614         LRegion->removeLiveOut(Reg);
1615       }
1616       WasLiveOut = true;
1617     }
1618   }
1619 
1620   if (WasLiveOut)
1621     LRegion->addLiveOut(CombinedSourceReg);
1622 }
1623 
1624 void AMDGPUMachineCFGStructurizer::rewriteRegionExitPHI(RegionMRT *Region,
1625                                                   MachineBasicBlock *LastMerge,
1626                                                   MachineInstr &PHI,
1627                                                   LinearizedRegion *LRegion) {
1628   SmallVector<unsigned, 2> PHIRegionIndices;
1629   getPHIRegionIndices(Region, PHI, PHIRegionIndices);
1630   unsigned LinearizedSourceReg =
1631       storePHILinearizationInfo(PHI, &PHIRegionIndices);
1632 
1633   replacePHI(PHI, LinearizedSourceReg, LastMerge, PHIRegionIndices);
1634   replaceLiveOutRegs(PHI, PHIRegionIndices, LinearizedSourceReg, LRegion);
1635 }
1636 
1637 void AMDGPUMachineCFGStructurizer::rewriteRegionEntryPHI(LinearizedRegion *Region,
1638                                                    MachineBasicBlock *IfMBB,
1639                                                    MachineInstr &PHI) {
1640   SmallVector<unsigned, 2> PHINonRegionIndices;
1641   getPHINonRegionIndices(Region, PHI, PHINonRegionIndices);
1642   unsigned LinearizedSourceReg =
1643       storePHILinearizationInfo(PHI, &PHINonRegionIndices);
1644   replaceEntryPHI(PHI, LinearizedSourceReg, IfMBB, PHINonRegionIndices);
1645 }
1646 
1647 static void collectPHIs(MachineBasicBlock *MBB,
1648                         SmallVector<MachineInstr *, 2> &PHIs) {
1649   for (auto &BBI : *MBB) {
1650     if (BBI.isPHI()) {
1651       PHIs.push_back(&BBI);
1652     }
1653   }
1654 }
1655 
1656 void AMDGPUMachineCFGStructurizer::rewriteRegionExitPHIs(RegionMRT *Region,
1657                                                    MachineBasicBlock *LastMerge,
1658                                                    LinearizedRegion *LRegion) {
1659   SmallVector<MachineInstr *, 2> PHIs;
1660   auto Exit = Region->getSucc();
1661   if (Exit == nullptr)
1662     return;
1663 
1664   collectPHIs(Exit, PHIs);
1665 
1666   for (auto PHII : PHIs) {
1667     rewriteRegionExitPHI(Region, LastMerge, *PHII, LRegion);
1668   }
1669 }
1670 
1671 void AMDGPUMachineCFGStructurizer::rewriteRegionEntryPHIs(LinearizedRegion *Region,
1672                                                     MachineBasicBlock *IfMBB) {
1673   SmallVector<MachineInstr *, 2> PHIs;
1674   auto Entry = Region->getEntry();
1675 
1676   collectPHIs(Entry, PHIs);
1677 
1678   for (auto PHII : PHIs) {
1679     rewriteRegionEntryPHI(Region, IfMBB, *PHII);
1680   }
1681 }
1682 
1683 void AMDGPUMachineCFGStructurizer::insertUnconditionalBranch(MachineBasicBlock *MBB,
1684                                                        MachineBasicBlock *Dest,
1685                                                        const DebugLoc &DL) {
1686   DEBUG(dbgs() << "Inserting unconditional branch: " << MBB->getNumber()
1687                << " -> " << Dest->getNumber() << "\n");
1688   MachineBasicBlock::instr_iterator Terminator = MBB->getFirstInstrTerminator();
1689   bool HasTerminator = Terminator != MBB->instr_end();
1690   if (HasTerminator) {
1691     TII->ReplaceTailWithBranchTo(Terminator, Dest);
1692   }
1693   if (++MachineFunction::iterator(MBB) != MachineFunction::iterator(Dest)) {
1694     TII->insertUnconditionalBranch(*MBB, Dest, DL);
1695   }
1696 }
1697 
1698 static MachineBasicBlock *getSingleExitNode(MachineFunction &MF) {
1699   MachineBasicBlock *result = nullptr;
1700   for (auto &MFI : MF) {
1701     if (MFI.succ_size() == 0) {
1702       if (result == nullptr) {
1703         result = &MFI;
1704       } else {
1705         return nullptr;
1706       }
1707     }
1708   }
1709 
1710   return result;
1711 }
1712 
1713 static bool hasOneExitNode(MachineFunction &MF) {
1714   return getSingleExitNode(MF) != nullptr;
1715 }
1716 
1717 MachineBasicBlock *
1718 AMDGPUMachineCFGStructurizer::createLinearizedExitBlock(RegionMRT *Region) {
1719   auto Exit = Region->getSucc();
1720 
1721   // If the exit is the end of the function, we just use the existing
1722   MachineFunction *MF = Region->getEntry()->getParent();
1723   if (Exit == nullptr && hasOneExitNode(*MF)) {
1724     return &(*(--(Region->getEntry()->getParent()->end())));
1725   }
1726 
1727   MachineBasicBlock *LastMerge = MF->CreateMachineBasicBlock();
1728   if (Exit == nullptr) {
1729     MachineFunction::iterator ExitIter = MF->end();
1730     MF->insert(ExitIter, LastMerge);
1731   } else {
1732     MachineFunction::iterator ExitIter = Exit->getIterator();
1733     MF->insert(ExitIter, LastMerge);
1734     LastMerge->addSuccessor(Exit);
1735     insertUnconditionalBranch(LastMerge, Exit);
1736     DEBUG(dbgs() << "Created exit block: " << LastMerge->getNumber() << "\n");
1737   }
1738   return LastMerge;
1739 }
1740 
1741 void AMDGPUMachineCFGStructurizer::insertMergePHI(MachineBasicBlock *IfBB,
1742                                             MachineBasicBlock *CodeBB,
1743                                             MachineBasicBlock *MergeBB,
1744                                             unsigned DestRegister,
1745                                             unsigned IfSourceRegister,
1746                                             unsigned CodeSourceRegister,
1747                                             bool IsUndefIfSource) {
1748   // If this is the function exit block, we don't need a phi.
1749   if (MergeBB->succ_begin() == MergeBB->succ_end()) {
1750     return;
1751   }
1752   DEBUG(dbgs() << "Merge PHI (" << printMBBReference(*MergeBB)
1753                << "): " << printReg(DestRegister, TRI) << " = PHI("
1754                << printReg(IfSourceRegister, TRI) << ", "
1755                << printMBBReference(*IfBB) << printReg(CodeSourceRegister, TRI)
1756                << ", " << printMBBReference(*CodeBB) << ")\n");
1757   const DebugLoc &DL = MergeBB->findDebugLoc(MergeBB->begin());
1758   MachineInstrBuilder MIB = BuildMI(*MergeBB, MergeBB->instr_begin(), DL,
1759                                     TII->get(TargetOpcode::PHI), DestRegister);
1760   if (IsUndefIfSource && false) {
1761     MIB.addReg(IfSourceRegister, RegState::Undef);
1762   } else {
1763     MIB.addReg(IfSourceRegister);
1764   }
1765   MIB.addMBB(IfBB);
1766   MIB.addReg(CodeSourceRegister);
1767   MIB.addMBB(CodeBB);
1768 }
1769 
1770 static void removeExternalCFGSuccessors(MachineBasicBlock *MBB) {
1771   for (MachineBasicBlock::succ_iterator PI = MBB->succ_begin(),
1772                                         E = MBB->succ_end();
1773        PI != E; ++PI) {
1774     if ((*PI) != MBB) {
1775       (MBB)->removeSuccessor(*PI);
1776     }
1777   }
1778 }
1779 
1780 static void removeExternalCFGEdges(MachineBasicBlock *StartMBB,
1781                                    MachineBasicBlock *EndMBB) {
1782 
1783   // We have to check against the StartMBB successor becasuse a
1784   // structurized region with a loop will have the entry block split,
1785   // and the backedge will go to the entry successor.
1786   DenseSet<std::pair<MachineBasicBlock *, MachineBasicBlock *>> Succs;
1787   unsigned SuccSize = StartMBB->succ_size();
1788   if (SuccSize > 0) {
1789     MachineBasicBlock *StartMBBSucc = *(StartMBB->succ_begin());
1790     for (MachineBasicBlock::succ_iterator PI = EndMBB->succ_begin(),
1791                                           E = EndMBB->succ_end();
1792          PI != E; ++PI) {
1793       // Either we have a back-edge to the entry block, or a back-edge to the
1794       // successor of the entry block since the block may be split.
1795       if ((*PI) != StartMBB &&
1796           !((*PI) == StartMBBSucc && StartMBB != EndMBB && SuccSize == 1)) {
1797         Succs.insert(
1798             std::pair<MachineBasicBlock *, MachineBasicBlock *>(EndMBB, *PI));
1799       }
1800     }
1801   }
1802 
1803   for (MachineBasicBlock::pred_iterator PI = StartMBB->pred_begin(),
1804                                         E = StartMBB->pred_end();
1805        PI != E; ++PI) {
1806     if ((*PI) != EndMBB) {
1807       Succs.insert(
1808           std::pair<MachineBasicBlock *, MachineBasicBlock *>(*PI, StartMBB));
1809     }
1810   }
1811 
1812   for (auto SI : Succs) {
1813     std::pair<MachineBasicBlock *, MachineBasicBlock *> Edge = SI;
1814     DEBUG(dbgs() << "Removing edge: " << printMBBReference(*Edge.first)
1815                  << " -> " << printMBBReference(*Edge.second) << "\n");
1816     Edge.first->removeSuccessor(Edge.second);
1817   }
1818 }
1819 
1820 MachineBasicBlock *AMDGPUMachineCFGStructurizer::createIfBlock(
1821     MachineBasicBlock *MergeBB, MachineBasicBlock *CodeBBStart,
1822     MachineBasicBlock *CodeBBEnd, MachineBasicBlock *SelectBB, unsigned IfReg,
1823     bool InheritPreds) {
1824   MachineFunction *MF = MergeBB->getParent();
1825   MachineBasicBlock *IfBB = MF->CreateMachineBasicBlock();
1826 
1827   if (InheritPreds) {
1828     for (MachineBasicBlock::pred_iterator PI = CodeBBStart->pred_begin(),
1829                                           E = CodeBBStart->pred_end();
1830          PI != E; ++PI) {
1831       if ((*PI) != CodeBBEnd) {
1832         MachineBasicBlock *Pred = (*PI);
1833         Pred->addSuccessor(IfBB);
1834       }
1835     }
1836   }
1837 
1838   removeExternalCFGEdges(CodeBBStart, CodeBBEnd);
1839 
1840   auto CodeBBStartI = CodeBBStart->getIterator();
1841   auto CodeBBEndI = CodeBBEnd->getIterator();
1842   auto MergeIter = MergeBB->getIterator();
1843   MF->insert(MergeIter, IfBB);
1844   MF->splice(MergeIter, CodeBBStartI, ++CodeBBEndI);
1845   IfBB->addSuccessor(MergeBB);
1846   IfBB->addSuccessor(CodeBBStart);
1847 
1848   DEBUG(dbgs() << "Created If block: " << IfBB->getNumber() << "\n");
1849   // Ensure that the MergeBB is a successor of the CodeEndBB.
1850   if (!CodeBBEnd->isSuccessor(MergeBB))
1851     CodeBBEnd->addSuccessor(MergeBB);
1852 
1853   DEBUG(dbgs() << "Moved " << printMBBReference(*CodeBBStart) << " through "
1854                << printMBBReference(*CodeBBEnd) << "\n");
1855 
1856   // If we have a single predecessor we can find a reasonable debug location
1857   MachineBasicBlock *SinglePred =
1858       CodeBBStart->pred_size() == 1 ? *(CodeBBStart->pred_begin()) : nullptr;
1859   const DebugLoc &DL = SinglePred
1860                     ? SinglePred->findDebugLoc(SinglePred->getFirstTerminator())
1861                     : DebugLoc();
1862 
1863   unsigned Reg =
1864       TII->insertEQ(IfBB, IfBB->begin(), DL, IfReg,
1865                     SelectBB->getNumber() /* CodeBBStart->getNumber() */);
1866   if (&(*(IfBB->getParent()->begin())) == IfBB) {
1867     TII->materializeImmediate(*IfBB, IfBB->begin(), DL, IfReg,
1868                               CodeBBStart->getNumber());
1869   }
1870   MachineOperand RegOp = MachineOperand::CreateReg(Reg, false, false, true);
1871   ArrayRef<MachineOperand> Cond(RegOp);
1872   TII->insertBranch(*IfBB, MergeBB, CodeBBStart, Cond, DL);
1873 
1874   return IfBB;
1875 }
1876 
1877 void AMDGPUMachineCFGStructurizer::ensureCondIsNotKilled(
1878     SmallVector<MachineOperand, 1> Cond) {
1879   if (Cond.size() != 1)
1880     return;
1881   if (!Cond[0].isReg())
1882     return;
1883 
1884   unsigned CondReg = Cond[0].getReg();
1885   for (auto UI = MRI->use_begin(CondReg), E = MRI->use_end(); UI != E; ++UI) {
1886     (*UI).setIsKill(false);
1887   }
1888 }
1889 
1890 void AMDGPUMachineCFGStructurizer::rewriteCodeBBTerminator(MachineBasicBlock *CodeBB,
1891                                                      MachineBasicBlock *MergeBB,
1892                                                      unsigned BBSelectReg) {
1893   MachineBasicBlock *TrueBB = nullptr;
1894   MachineBasicBlock *FalseBB = nullptr;
1895   SmallVector<MachineOperand, 1> Cond;
1896   MachineBasicBlock *FallthroughBB = FallthroughMap[CodeBB];
1897   TII->analyzeBranch(*CodeBB, TrueBB, FalseBB, Cond);
1898 
1899   const DebugLoc &DL = CodeBB->findDebugLoc(CodeBB->getFirstTerminator());
1900 
1901   if (FalseBB == nullptr && TrueBB == nullptr && FallthroughBB == nullptr) {
1902     // This is an exit block, hence no successors. We will assign the
1903     // bb select register to the entry block.
1904     TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
1905                               BBSelectReg,
1906                               CodeBB->getParent()->begin()->getNumber());
1907     insertUnconditionalBranch(CodeBB, MergeBB, DL);
1908     return;
1909   }
1910 
1911   if (FalseBB == nullptr && TrueBB == nullptr) {
1912     TrueBB = FallthroughBB;
1913   } else if (TrueBB != nullptr) {
1914     FalseBB =
1915         (FallthroughBB && (FallthroughBB != TrueBB)) ? FallthroughBB : FalseBB;
1916   }
1917 
1918   if ((TrueBB != nullptr && FalseBB == nullptr) || (TrueBB == FalseBB)) {
1919     TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
1920                               BBSelectReg, TrueBB->getNumber());
1921   } else {
1922     const TargetRegisterClass *RegClass = MRI->getRegClass(BBSelectReg);
1923     unsigned TrueBBReg = MRI->createVirtualRegister(RegClass);
1924     unsigned FalseBBReg = MRI->createVirtualRegister(RegClass);
1925     TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
1926                               TrueBBReg, TrueBB->getNumber());
1927     TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
1928                               FalseBBReg, FalseBB->getNumber());
1929     ensureCondIsNotKilled(Cond);
1930     TII->insertVectorSelect(*CodeBB, CodeBB->getFirstTerminator(), DL,
1931                             BBSelectReg, Cond, TrueBBReg, FalseBBReg);
1932   }
1933 
1934   insertUnconditionalBranch(CodeBB, MergeBB, DL);
1935 }
1936 
1937 MachineInstr *AMDGPUMachineCFGStructurizer::getDefInstr(unsigned Reg) {
1938   if (MRI->def_begin(Reg) == MRI->def_end()) {
1939     DEBUG(dbgs() << "Register " << printReg(Reg, MRI->getTargetRegisterInfo())
1940                  << " has NO defs\n");
1941   } else if (!MRI->hasOneDef(Reg)) {
1942     DEBUG(dbgs() << "Register " << printReg(Reg, MRI->getTargetRegisterInfo())
1943                  << " has multiple defs\n");
1944     DEBUG(dbgs() << "DEFS BEGIN:\n");
1945     for (auto DI = MRI->def_begin(Reg), DE = MRI->def_end(); DI != DE; ++DI) {
1946       DEBUG(DI->getParent()->dump());
1947     }
1948     DEBUG(dbgs() << "DEFS END\n");
1949   }
1950 
1951   assert(MRI->hasOneDef(Reg) && "Register has multiple definitions");
1952   return (*(MRI->def_begin(Reg))).getParent();
1953 }
1954 
1955 void AMDGPUMachineCFGStructurizer::insertChainedPHI(MachineBasicBlock *IfBB,
1956                                               MachineBasicBlock *CodeBB,
1957                                               MachineBasicBlock *MergeBB,
1958                                               LinearizedRegion *InnerRegion,
1959                                               unsigned DestReg,
1960                                               unsigned SourceReg) {
1961   // In this function we know we are part of a chain already, so we need
1962   // to add the registers to the existing chain, and rename the register
1963   // inside the region.
1964   bool IsSingleBB = InnerRegion->getEntry() == InnerRegion->getExit();
1965   MachineInstr *DefInstr = getDefInstr(SourceReg);
1966   if (DefInstr->isPHI() && DefInstr->getParent() == CodeBB && IsSingleBB) {
1967     // Handle the case where the def is a PHI-def inside a basic
1968     // block, then we only need to do renaming. Special care needs to
1969     // be taken if the PHI-def is part of an existing chain, or if a
1970     // new one needs to be created.
1971     InnerRegion->replaceRegisterInsideRegion(SourceReg, DestReg, true, MRI);
1972 
1973     // We collect all PHI Information, and if we are at the region entry,
1974     // all PHIs will be removed, and then re-introduced if needed.
1975     storePHILinearizationInfoDest(DestReg, *DefInstr);
1976     // We have picked up all the information we need now and can remove
1977     // the PHI
1978     PHIInfo.removeSource(DestReg, SourceReg, CodeBB);
1979     DefInstr->eraseFromParent();
1980   } else {
1981     // If this is not a phi-def, or it is a phi-def but from a linearized region
1982     if (IsSingleBB && DefInstr->getParent() == InnerRegion->getEntry()) {
1983       // If this is a single BB and the definition is in this block we
1984       // need to replace any uses outside the region.
1985       InnerRegion->replaceRegisterOutsideRegion(SourceReg, DestReg, false, MRI);
1986     }
1987     const TargetRegisterClass *RegClass = MRI->getRegClass(DestReg);
1988     unsigned NextDestReg = MRI->createVirtualRegister(RegClass);
1989     bool IsLastDef = PHIInfo.getNumSources(DestReg) == 1;
1990     DEBUG(dbgs() << "Insert Chained PHI\n");
1991     insertMergePHI(IfBB, InnerRegion->getExit(), MergeBB, DestReg, NextDestReg,
1992                    SourceReg, IsLastDef);
1993 
1994     PHIInfo.removeSource(DestReg, SourceReg, CodeBB);
1995     if (IsLastDef) {
1996       const DebugLoc &DL = IfBB->findDebugLoc(IfBB->getFirstTerminator());
1997       TII->materializeImmediate(*IfBB, IfBB->getFirstTerminator(), DL,
1998                                 NextDestReg, 0);
1999       PHIInfo.deleteDef(DestReg);
2000     } else {
2001       PHIInfo.replaceDef(DestReg, NextDestReg);
2002     }
2003   }
2004 }
2005 
2006 bool AMDGPUMachineCFGStructurizer::containsDef(MachineBasicBlock *MBB,
2007                                          LinearizedRegion *InnerRegion,
2008                                          unsigned Register) {
2009   return getDefInstr(Register)->getParent() == MBB ||
2010          InnerRegion->contains(getDefInstr(Register)->getParent());
2011 }
2012 
2013 void AMDGPUMachineCFGStructurizer::rewriteLiveOutRegs(MachineBasicBlock *IfBB,
2014                                                 MachineBasicBlock *CodeBB,
2015                                                 MachineBasicBlock *MergeBB,
2016                                                 LinearizedRegion *InnerRegion,
2017                                                 LinearizedRegion *LRegion) {
2018   DenseSet<unsigned> *LiveOuts = InnerRegion->getLiveOuts();
2019   SmallVector<unsigned, 4> OldLiveOuts;
2020   bool IsSingleBB = InnerRegion->getEntry() == InnerRegion->getExit();
2021   for (auto OLI : *LiveOuts) {
2022     OldLiveOuts.push_back(OLI);
2023   }
2024 
2025   for (auto LI : OldLiveOuts) {
2026     DEBUG(dbgs() << "LiveOut: " << printReg(LI, TRI));
2027     if (!containsDef(CodeBB, InnerRegion, LI) ||
2028         (!IsSingleBB && (getDefInstr(LI)->getParent() == LRegion->getExit()))) {
2029       // If the register simly lives through the CodeBB, we don't have
2030       // to rewrite anything since the register is not defined in this
2031       // part of the code.
2032       DEBUG(dbgs() << "- through");
2033       continue;
2034     }
2035     DEBUG(dbgs() << "\n");
2036     unsigned Reg = LI;
2037     if (/*!PHIInfo.isSource(Reg) &&*/ Reg != InnerRegion->getBBSelectRegOut()) {
2038       // If the register is live out, we do want to create a phi,
2039       // unless it is from the Exit block, becasuse in that case there
2040       // is already a PHI, and no need to create a new one.
2041 
2042       // If the register is just a live out def and not part of a phi
2043       // chain, we need to create a PHI node to handle the if region,
2044       // and replace all uses outside of the region with the new dest
2045       // register, unless it is the outgoing BB select register. We have
2046       // already creaed phi nodes for these.
2047       const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
2048       unsigned PHIDestReg = MRI->createVirtualRegister(RegClass);
2049       unsigned IfSourceReg = MRI->createVirtualRegister(RegClass);
2050       // Create initializer, this value is never used, but is needed
2051       // to satisfy SSA.
2052       DEBUG(dbgs() << "Initializer for reg: " << printReg(Reg) << "\n");
2053       TII->materializeImmediate(*IfBB, IfBB->getFirstTerminator(), DebugLoc(),
2054                         IfSourceReg, 0);
2055 
2056       InnerRegion->replaceRegisterOutsideRegion(Reg, PHIDestReg, true, MRI);
2057       DEBUG(dbgs() << "Insert Non-Chained Live out PHI\n");
2058       insertMergePHI(IfBB, InnerRegion->getExit(), MergeBB, PHIDestReg,
2059                      IfSourceReg, Reg, true);
2060     }
2061   }
2062 
2063   // Handle the chained definitions in PHIInfo, checking if this basic block
2064   // is a source block for a definition.
2065   SmallVector<unsigned, 4> Sources;
2066   if (PHIInfo.findSourcesFromMBB(CodeBB, Sources)) {
2067     DEBUG(dbgs() << "Inserting PHI Live Out from " << printMBBReference(*CodeBB)
2068                  << "\n");
2069     for (auto SI : Sources) {
2070       unsigned DestReg;
2071       PHIInfo.findDest(SI, CodeBB, DestReg);
2072       insertChainedPHI(IfBB, CodeBB, MergeBB, InnerRegion, DestReg, SI);
2073     }
2074     DEBUG(dbgs() << "Insertion done.\n");
2075   }
2076 
2077   DEBUG(PHIInfo.dump(MRI));
2078 }
2079 
2080 void AMDGPUMachineCFGStructurizer::prunePHIInfo(MachineBasicBlock *MBB) {
2081   DEBUG(dbgs() << "Before PHI Prune\n");
2082   DEBUG(PHIInfo.dump(MRI));
2083   SmallVector<std::tuple<unsigned, unsigned, MachineBasicBlock *>, 4>
2084       ElimiatedSources;
2085   for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
2086        ++DRI) {
2087 
2088     unsigned DestReg = *DRI;
2089     auto SE = PHIInfo.sources_end(DestReg);
2090 
2091     bool MBBContainsPHISource = false;
2092     // Check if there is a PHI source in this MBB
2093     for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
2094       unsigned SourceReg = (*SRI).first;
2095       MachineOperand *Def = &(*(MRI->def_begin(SourceReg)));
2096       if (Def->getParent()->getParent() == MBB) {
2097         MBBContainsPHISource = true;
2098       }
2099     }
2100 
2101     // If so, all other sources are useless since we know this block
2102     // is always executed when the region is executed.
2103     if (MBBContainsPHISource) {
2104       for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
2105         PHILinearize::PHISourceT Source = *SRI;
2106         unsigned SourceReg = Source.first;
2107         MachineBasicBlock *SourceMBB = Source.second;
2108         MachineOperand *Def = &(*(MRI->def_begin(SourceReg)));
2109         if (Def->getParent()->getParent() != MBB) {
2110           ElimiatedSources.push_back(
2111               std::make_tuple(DestReg, SourceReg, SourceMBB));
2112         }
2113       }
2114     }
2115   }
2116 
2117   // Remove the PHI sources that are in the given MBB
2118   for (auto &SourceInfo : ElimiatedSources) {
2119     PHIInfo.removeSource(std::get<0>(SourceInfo), std::get<1>(SourceInfo),
2120                          std::get<2>(SourceInfo));
2121   }
2122   DEBUG(dbgs() << "After PHI Prune\n");
2123   DEBUG(PHIInfo.dump(MRI));
2124 }
2125 
2126 void AMDGPUMachineCFGStructurizer::createEntryPHI(LinearizedRegion *CurrentRegion,
2127                                             unsigned DestReg) {
2128   MachineBasicBlock *Entry = CurrentRegion->getEntry();
2129   MachineBasicBlock *Exit = CurrentRegion->getExit();
2130 
2131   DEBUG(dbgs() << "RegionExit: " << Exit->getNumber()
2132                << " Pred: " << (*(Entry->pred_begin()))->getNumber() << "\n");
2133 
2134   int NumSources = 0;
2135   auto SE = PHIInfo.sources_end(DestReg);
2136 
2137   for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
2138     NumSources++;
2139   }
2140 
2141   if (NumSources == 1) {
2142     auto SRI = PHIInfo.sources_begin(DestReg);
2143     unsigned SourceReg = (*SRI).first;
2144     replaceRegisterWith(DestReg, SourceReg);
2145   } else {
2146     const DebugLoc &DL = Entry->findDebugLoc(Entry->begin());
2147     MachineInstrBuilder MIB = BuildMI(*Entry, Entry->instr_begin(), DL,
2148                                       TII->get(TargetOpcode::PHI), DestReg);
2149     DEBUG(dbgs() << "Entry PHI " << printReg(DestReg, TRI) << " = PHI(");
2150 
2151     unsigned CurrentBackedgeReg = 0;
2152 
2153     for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
2154       unsigned SourceReg = (*SRI).first;
2155 
2156       if (CurrentRegion->contains((*SRI).second)) {
2157         if (CurrentBackedgeReg == 0) {
2158           CurrentBackedgeReg = SourceReg;
2159         } else {
2160           MachineInstr *PHIDefInstr = getDefInstr(SourceReg);
2161           MachineBasicBlock *PHIDefMBB = PHIDefInstr->getParent();
2162           const TargetRegisterClass *RegClass =
2163               MRI->getRegClass(CurrentBackedgeReg);
2164           unsigned NewBackedgeReg = MRI->createVirtualRegister(RegClass);
2165           MachineInstrBuilder BackedgePHI =
2166               BuildMI(*PHIDefMBB, PHIDefMBB->instr_begin(), DL,
2167                       TII->get(TargetOpcode::PHI), NewBackedgeReg);
2168           BackedgePHI.addReg(CurrentBackedgeReg);
2169           BackedgePHI.addMBB(getPHIPred(*PHIDefInstr, 0));
2170           BackedgePHI.addReg(getPHISourceReg(*PHIDefInstr, 1));
2171           BackedgePHI.addMBB((*SRI).second);
2172           CurrentBackedgeReg = NewBackedgeReg;
2173           DEBUG(dbgs() << "Inserting backedge PHI: "
2174                        << printReg(NewBackedgeReg, TRI) << " = PHI("
2175                        << printReg(CurrentBackedgeReg, TRI) << ", "
2176                        << printMBBReference(*getPHIPred(*PHIDefInstr, 0))
2177                        << ", "
2178                        << printReg(getPHISourceReg(*PHIDefInstr, 1), TRI)
2179                        << ", " << printMBBReference(*(*SRI).second));
2180         }
2181       } else {
2182         MIB.addReg(SourceReg);
2183         MIB.addMBB((*SRI).second);
2184         DEBUG(dbgs() << printReg(SourceReg, TRI) << ", "
2185                      << printMBBReference(*(*SRI).second) << ", ");
2186       }
2187     }
2188 
2189     // Add the final backedge register source to the entry phi
2190     if (CurrentBackedgeReg != 0) {
2191       MIB.addReg(CurrentBackedgeReg);
2192       MIB.addMBB(Exit);
2193       DEBUG(dbgs() << printReg(CurrentBackedgeReg, TRI) << ", "
2194                    << printMBBReference(*Exit) << ")\n");
2195     } else {
2196       DEBUG(dbgs() << ")\n");
2197     }
2198   }
2199 }
2200 
2201 void AMDGPUMachineCFGStructurizer::createEntryPHIs(LinearizedRegion *CurrentRegion) {
2202   DEBUG(PHIInfo.dump(MRI));
2203 
2204   for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
2205        ++DRI) {
2206 
2207     unsigned DestReg = *DRI;
2208     createEntryPHI(CurrentRegion, DestReg);
2209   }
2210   PHIInfo.clear();
2211 }
2212 
2213 void AMDGPUMachineCFGStructurizer::replaceRegisterWith(unsigned Register,
2214                                                  unsigned NewRegister) {
2215   assert(Register != NewRegister && "Cannot replace a reg with itself");
2216 
2217   for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Register),
2218                                          E = MRI->reg_end();
2219        I != E;) {
2220     MachineOperand &O = *I;
2221     ++I;
2222     if (TargetRegisterInfo::isPhysicalRegister(NewRegister)) {
2223       DEBUG(dbgs() << "Trying to substitute physical register: "
2224                    << printReg(NewRegister, MRI->getTargetRegisterInfo())
2225                    << "\n");
2226       llvm_unreachable("Cannot substitute physical registers");
2227       // We don't handle physical registers, but if we need to
2228       // in the future This is how we do it:
2229       // O.substPhysReg(NewRegister, *TRI);
2230     } else {
2231       DEBUG(dbgs() << "Replacing register: "
2232                    << printReg(Register, MRI->getTargetRegisterInfo())
2233                    << " with "
2234                    << printReg(NewRegister, MRI->getTargetRegisterInfo())
2235                    << "\n");
2236       O.setReg(NewRegister);
2237     }
2238   }
2239   PHIInfo.deleteDef(Register);
2240 
2241   getRegionMRT()->replaceLiveOutReg(Register, NewRegister);
2242 
2243   DEBUG(PHIInfo.dump(MRI));
2244 }
2245 
2246 void AMDGPUMachineCFGStructurizer::resolvePHIInfos(MachineBasicBlock *FunctionEntry) {
2247   DEBUG(dbgs() << "Resolve PHI Infos\n");
2248   DEBUG(PHIInfo.dump(MRI));
2249   for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
2250        ++DRI) {
2251     unsigned DestReg = *DRI;
2252     DEBUG(dbgs() << "DestReg: " << printReg(DestReg, TRI) << "\n");
2253     auto SRI = PHIInfo.sources_begin(DestReg);
2254     unsigned SourceReg = (*SRI).first;
2255     DEBUG(dbgs() << "DestReg: " << printReg(DestReg, TRI)
2256                  << " SourceReg: " << printReg(SourceReg, TRI) << "\n");
2257 
2258     assert(PHIInfo.sources_end(DestReg) == ++SRI &&
2259            "More than one phi source in entry node");
2260     replaceRegisterWith(DestReg, SourceReg);
2261   }
2262 }
2263 
2264 static bool isFunctionEntryBlock(MachineBasicBlock *MBB) {
2265   return ((&(*(MBB->getParent()->begin()))) == MBB);
2266 }
2267 
2268 MachineBasicBlock *AMDGPUMachineCFGStructurizer::createIfRegion(
2269     MachineBasicBlock *MergeBB, MachineBasicBlock *CodeBB,
2270     LinearizedRegion *CurrentRegion, unsigned BBSelectRegIn,
2271     unsigned BBSelectRegOut) {
2272   if (isFunctionEntryBlock(CodeBB) && !CurrentRegion->getHasLoop()) {
2273     // Handle non-loop function entry block.
2274     // We need to allow loops to the entry block and then
2275     rewriteCodeBBTerminator(CodeBB, MergeBB, BBSelectRegOut);
2276     resolvePHIInfos(CodeBB);
2277     removeExternalCFGSuccessors(CodeBB);
2278     CodeBB->addSuccessor(MergeBB);
2279     CurrentRegion->addMBB(CodeBB);
2280     return nullptr;
2281   }
2282   if (CurrentRegion->getEntry() == CodeBB && !CurrentRegion->getHasLoop()) {
2283     // Handle non-loop region entry block.
2284     MachineFunction *MF = MergeBB->getParent();
2285     auto MergeIter = MergeBB->getIterator();
2286     auto CodeBBStartIter = CodeBB->getIterator();
2287     auto CodeBBEndIter = ++(CodeBB->getIterator());
2288     if (CodeBBEndIter != MergeIter) {
2289       MF->splice(MergeIter, CodeBBStartIter, CodeBBEndIter);
2290     }
2291     rewriteCodeBBTerminator(CodeBB, MergeBB, BBSelectRegOut);
2292     prunePHIInfo(CodeBB);
2293     createEntryPHIs(CurrentRegion);
2294     removeExternalCFGSuccessors(CodeBB);
2295     CodeBB->addSuccessor(MergeBB);
2296     CurrentRegion->addMBB(CodeBB);
2297     return nullptr;
2298   } else {
2299     // Handle internal block.
2300     const TargetRegisterClass *RegClass = MRI->getRegClass(BBSelectRegIn);
2301     unsigned CodeBBSelectReg = MRI->createVirtualRegister(RegClass);
2302     rewriteCodeBBTerminator(CodeBB, MergeBB, CodeBBSelectReg);
2303     bool IsRegionEntryBB = CurrentRegion->getEntry() == CodeBB;
2304     MachineBasicBlock *IfBB = createIfBlock(MergeBB, CodeBB, CodeBB, CodeBB,
2305                                             BBSelectRegIn, IsRegionEntryBB);
2306     CurrentRegion->addMBB(IfBB);
2307     // If this is the entry block we need to make the If block the new
2308     // linearized region entry.
2309     if (IsRegionEntryBB) {
2310       CurrentRegion->setEntry(IfBB);
2311 
2312       if (CurrentRegion->getHasLoop()) {
2313         MachineBasicBlock *RegionExit = CurrentRegion->getExit();
2314         MachineBasicBlock *ETrueBB = nullptr;
2315         MachineBasicBlock *EFalseBB = nullptr;
2316         SmallVector<MachineOperand, 1> ECond;
2317 
2318         const DebugLoc &DL = DebugLoc();
2319         TII->analyzeBranch(*RegionExit, ETrueBB, EFalseBB, ECond);
2320         TII->removeBranch(*RegionExit);
2321 
2322         // We need to create a backedge if there is a loop
2323         unsigned Reg = TII->insertNE(
2324             RegionExit, RegionExit->instr_end(), DL,
2325             CurrentRegion->getRegionMRT()->getInnerOutputRegister(),
2326             CurrentRegion->getRegionMRT()->getEntry()->getNumber());
2327         MachineOperand RegOp =
2328             MachineOperand::CreateReg(Reg, false, false, true);
2329         ArrayRef<MachineOperand> Cond(RegOp);
2330         DEBUG(dbgs() << "RegionExitReg: ");
2331         DEBUG(Cond[0].print(dbgs(), TRI));
2332         DEBUG(dbgs() << "\n");
2333         TII->insertBranch(*RegionExit, CurrentRegion->getEntry(), RegionExit,
2334                           Cond, DebugLoc());
2335         RegionExit->addSuccessor(CurrentRegion->getEntry());
2336       }
2337     }
2338     CurrentRegion->addMBB(CodeBB);
2339     LinearizedRegion InnerRegion(CodeBB, MRI, TRI, PHIInfo);
2340 
2341     InnerRegion.setParent(CurrentRegion);
2342     DEBUG(dbgs() << "Insert BB Select PHI (BB)\n");
2343     insertMergePHI(IfBB, CodeBB, MergeBB, BBSelectRegOut, BBSelectRegIn,
2344                    CodeBBSelectReg);
2345     InnerRegion.addMBB(MergeBB);
2346 
2347     DEBUG(InnerRegion.print(dbgs(), TRI));
2348     rewriteLiveOutRegs(IfBB, CodeBB, MergeBB, &InnerRegion, CurrentRegion);
2349     extractKilledPHIs(CodeBB);
2350     if (IsRegionEntryBB) {
2351       createEntryPHIs(CurrentRegion);
2352     }
2353     return IfBB;
2354   }
2355 }
2356 
2357 MachineBasicBlock *AMDGPUMachineCFGStructurizer::createIfRegion(
2358     MachineBasicBlock *MergeBB, LinearizedRegion *InnerRegion,
2359     LinearizedRegion *CurrentRegion, MachineBasicBlock *SelectBB,
2360     unsigned BBSelectRegIn, unsigned BBSelectRegOut) {
2361   unsigned CodeBBSelectReg =
2362       InnerRegion->getRegionMRT()->getInnerOutputRegister();
2363   MachineBasicBlock *CodeEntryBB = InnerRegion->getEntry();
2364   MachineBasicBlock *CodeExitBB = InnerRegion->getExit();
2365   MachineBasicBlock *IfBB = createIfBlock(MergeBB, CodeEntryBB, CodeExitBB,
2366                                           SelectBB, BBSelectRegIn, true);
2367   CurrentRegion->addMBB(IfBB);
2368   bool isEntry = CurrentRegion->getEntry() == InnerRegion->getEntry();
2369   if (isEntry) {
2370 
2371     if (CurrentRegion->getHasLoop()) {
2372       MachineBasicBlock *RegionExit = CurrentRegion->getExit();
2373       MachineBasicBlock *ETrueBB = nullptr;
2374       MachineBasicBlock *EFalseBB = nullptr;
2375       SmallVector<MachineOperand, 1> ECond;
2376 
2377       const DebugLoc &DL = DebugLoc();
2378       TII->analyzeBranch(*RegionExit, ETrueBB, EFalseBB, ECond);
2379       TII->removeBranch(*RegionExit);
2380 
2381       // We need to create a backedge if there is a loop
2382       unsigned Reg =
2383           TII->insertNE(RegionExit, RegionExit->instr_end(), DL,
2384                         CurrentRegion->getRegionMRT()->getInnerOutputRegister(),
2385                         CurrentRegion->getRegionMRT()->getEntry()->getNumber());
2386       MachineOperand RegOp = MachineOperand::CreateReg(Reg, false, false, true);
2387       ArrayRef<MachineOperand> Cond(RegOp);
2388       DEBUG(dbgs() << "RegionExitReg: ");
2389       DEBUG(Cond[0].print(dbgs(), TRI));
2390       DEBUG(dbgs() << "\n");
2391       TII->insertBranch(*RegionExit, CurrentRegion->getEntry(), RegionExit,
2392                         Cond, DebugLoc());
2393       RegionExit->addSuccessor(IfBB);
2394     }
2395   }
2396   CurrentRegion->addMBBs(InnerRegion);
2397   DEBUG(dbgs() << "Insert BB Select PHI (region)\n");
2398   insertMergePHI(IfBB, CodeExitBB, MergeBB, BBSelectRegOut, BBSelectRegIn,
2399                  CodeBBSelectReg);
2400 
2401   rewriteLiveOutRegs(IfBB, /* CodeEntryBB */ CodeExitBB, MergeBB, InnerRegion,
2402                      CurrentRegion);
2403 
2404   rewriteRegionEntryPHIs(InnerRegion, IfBB);
2405 
2406   if (isEntry) {
2407     CurrentRegion->setEntry(IfBB);
2408   }
2409 
2410   if (isEntry) {
2411     createEntryPHIs(CurrentRegion);
2412   }
2413 
2414   return IfBB;
2415 }
2416 
2417 void AMDGPUMachineCFGStructurizer::splitLoopPHI(MachineInstr &PHI,
2418                                           MachineBasicBlock *Entry,
2419                                           MachineBasicBlock *EntrySucc,
2420                                           LinearizedRegion *LRegion) {
2421   SmallVector<unsigned, 2> PHIRegionIndices;
2422   getPHIRegionIndices(LRegion, PHI, PHIRegionIndices);
2423 
2424   assert(PHIRegionIndices.size() == 1);
2425 
2426   unsigned RegionIndex = PHIRegionIndices[0];
2427   unsigned RegionSourceReg = getPHISourceReg(PHI, RegionIndex);
2428   MachineBasicBlock *RegionSourceMBB = getPHIPred(PHI, RegionIndex);
2429   unsigned PHIDest = getPHIDestReg(PHI);
2430   unsigned PHISource = PHIDest;
2431   unsigned ReplaceReg;
2432 
2433   if (shrinkPHI(PHI, PHIRegionIndices, &ReplaceReg)) {
2434     PHISource = ReplaceReg;
2435   }
2436 
2437   const TargetRegisterClass *RegClass = MRI->getRegClass(PHIDest);
2438   unsigned NewDestReg = MRI->createVirtualRegister(RegClass);
2439   LRegion->replaceRegisterInsideRegion(PHIDest, NewDestReg, false, MRI);
2440   MachineInstrBuilder MIB =
2441       BuildMI(*EntrySucc, EntrySucc->instr_begin(), PHI.getDebugLoc(),
2442               TII->get(TargetOpcode::PHI), NewDestReg);
2443   DEBUG(dbgs() << "Split Entry PHI " << printReg(NewDestReg, TRI) << " = PHI(");
2444   MIB.addReg(PHISource);
2445   MIB.addMBB(Entry);
2446   DEBUG(dbgs() << printReg(PHISource, TRI) << ", "
2447                << printMBBReference(*Entry));
2448   MIB.addReg(RegionSourceReg);
2449   MIB.addMBB(RegionSourceMBB);
2450   DEBUG(dbgs() << " ," << printReg(RegionSourceReg, TRI) << ", "
2451                << printMBBReference(*RegionSourceMBB) << ")\n");
2452 }
2453 
2454 void AMDGPUMachineCFGStructurizer::splitLoopPHIs(MachineBasicBlock *Entry,
2455                                            MachineBasicBlock *EntrySucc,
2456                                            LinearizedRegion *LRegion) {
2457   SmallVector<MachineInstr *, 2> PHIs;
2458   collectPHIs(Entry, PHIs);
2459 
2460   for (auto PHII : PHIs) {
2461     splitLoopPHI(*PHII, Entry, EntrySucc, LRegion);
2462   }
2463 }
2464 
2465 // Split the exit block so that we can insert a end control flow
2466 MachineBasicBlock *
2467 AMDGPUMachineCFGStructurizer::splitExit(LinearizedRegion *LRegion) {
2468   auto MRTRegion = LRegion->getRegionMRT();
2469   auto Exit = LRegion->getExit();
2470   auto MF = Exit->getParent();
2471   auto Succ = MRTRegion->getSucc();
2472 
2473   auto NewExit = MF->CreateMachineBasicBlock();
2474   auto AfterExitIter = Exit->getIterator();
2475   AfterExitIter++;
2476   MF->insert(AfterExitIter, NewExit);
2477   Exit->removeSuccessor(Succ);
2478   Exit->addSuccessor(NewExit);
2479   NewExit->addSuccessor(Succ);
2480   insertUnconditionalBranch(NewExit, Succ);
2481   LRegion->addMBB(NewExit);
2482   LRegion->setExit(NewExit);
2483 
2484   DEBUG(dbgs() << "Created new exit block: " << NewExit->getNumber() << "\n");
2485 
2486   // Replace any PHI Predecessors in the successor with NewExit
2487   for (auto &II : *Succ) {
2488     MachineInstr &Instr = II;
2489 
2490     // If we are past the PHI instructions we are done
2491     if (!Instr.isPHI())
2492       break;
2493 
2494     int numPreds = getPHINumInputs(Instr);
2495     for (int i = 0; i < numPreds; ++i) {
2496       auto Pred = getPHIPred(Instr, i);
2497       if (Pred == Exit) {
2498         setPhiPred(Instr, i, NewExit);
2499       }
2500     }
2501   }
2502 
2503   return NewExit;
2504 }
2505 
2506 static MachineBasicBlock *split(MachineBasicBlock::iterator I) {
2507   // Create the fall-through block.
2508   MachineBasicBlock *MBB = (*I).getParent();
2509   MachineFunction *MF = MBB->getParent();
2510   MachineBasicBlock *SuccMBB = MF->CreateMachineBasicBlock();
2511   auto MBBIter = ++(MBB->getIterator());
2512   MF->insert(MBBIter, SuccMBB);
2513   SuccMBB->transferSuccessorsAndUpdatePHIs(MBB);
2514   MBB->addSuccessor(SuccMBB);
2515 
2516   // Splice the code over.
2517   SuccMBB->splice(SuccMBB->end(), MBB, I, MBB->end());
2518 
2519   return SuccMBB;
2520 }
2521 
2522 // Split the entry block separating PHI-nodes and the rest of the code
2523 // This is needed to insert an initializer for the bb select register
2524 // inloop regions.
2525 
2526 MachineBasicBlock *
2527 AMDGPUMachineCFGStructurizer::splitEntry(LinearizedRegion *LRegion) {
2528   MachineBasicBlock *Entry = LRegion->getEntry();
2529   MachineBasicBlock *EntrySucc = split(Entry->getFirstNonPHI());
2530   MachineBasicBlock *Exit = LRegion->getExit();
2531 
2532   DEBUG(dbgs() << "Split " << printMBBReference(*Entry) << " to "
2533                << printMBBReference(*Entry) << " -> "
2534                << printMBBReference(*EntrySucc) << "\n");
2535   LRegion->addMBB(EntrySucc);
2536 
2537   // Make the backedge go to Entry Succ
2538   if (Exit->isSuccessor(Entry)) {
2539     Exit->removeSuccessor(Entry);
2540   }
2541   Exit->addSuccessor(EntrySucc);
2542   MachineInstr &Branch = *(Exit->instr_rbegin());
2543   for (auto &UI : Branch.uses()) {
2544     if (UI.isMBB() && UI.getMBB() == Entry) {
2545       UI.setMBB(EntrySucc);
2546     }
2547   }
2548 
2549   splitLoopPHIs(Entry, EntrySucc, LRegion);
2550 
2551   return EntrySucc;
2552 }
2553 
2554 LinearizedRegion *
2555 AMDGPUMachineCFGStructurizer::initLinearizedRegion(RegionMRT *Region) {
2556   LinearizedRegion *LRegion = Region->getLinearizedRegion();
2557   LRegion->initLiveOut(Region, MRI, TRI, PHIInfo);
2558   LRegion->setEntry(Region->getEntry());
2559   return LRegion;
2560 }
2561 
2562 static void removeOldExitPreds(RegionMRT *Region) {
2563   MachineBasicBlock *Exit = Region->getSucc();
2564   if (Exit == nullptr) {
2565     return;
2566   }
2567   for (MachineBasicBlock::pred_iterator PI = Exit->pred_begin(),
2568                                         E = Exit->pred_end();
2569        PI != E; ++PI) {
2570     if (Region->contains(*PI)) {
2571       (*PI)->removeSuccessor(Exit);
2572     }
2573   }
2574 }
2575 
2576 static bool mbbHasBackEdge(MachineBasicBlock *MBB,
2577                            SmallPtrSet<MachineBasicBlock *, 8> &MBBs) {
2578   for (auto SI = MBB->succ_begin(), SE = MBB->succ_end(); SI != SE; ++SI) {
2579     if (MBBs.count(*SI) != 0) {
2580       return true;
2581     }
2582   }
2583   return false;
2584 }
2585 
2586 static bool containsNewBackedge(MRT *Tree,
2587                                 SmallPtrSet<MachineBasicBlock *, 8> &MBBs) {
2588   // Need to traverse this in reverse since it is in post order.
2589   if (Tree == nullptr)
2590     return false;
2591 
2592   if (Tree->isMBB()) {
2593     MachineBasicBlock *MBB = Tree->getMBBMRT()->getMBB();
2594     MBBs.insert(MBB);
2595     if (mbbHasBackEdge(MBB, MBBs)) {
2596       return true;
2597     }
2598   } else {
2599     RegionMRT *Region = Tree->getRegionMRT();
2600     SetVector<MRT *> *Children = Region->getChildren();
2601     for (auto CI = Children->rbegin(), CE = Children->rend(); CI != CE; ++CI) {
2602       if (containsNewBackedge(*CI, MBBs))
2603         return true;
2604     }
2605   }
2606   return false;
2607 }
2608 
2609 static bool containsNewBackedge(RegionMRT *Region) {
2610   SmallPtrSet<MachineBasicBlock *, 8> MBBs;
2611   return containsNewBackedge(Region, MBBs);
2612 }
2613 
2614 bool AMDGPUMachineCFGStructurizer::structurizeComplexRegion(RegionMRT *Region) {
2615   auto *LRegion = initLinearizedRegion(Region);
2616   LRegion->setHasLoop(containsNewBackedge(Region));
2617   MachineBasicBlock *LastMerge = createLinearizedExitBlock(Region);
2618   MachineBasicBlock *CurrentMerge = LastMerge;
2619   LRegion->addMBB(LastMerge);
2620   LRegion->setExit(LastMerge);
2621 
2622   rewriteRegionExitPHIs(Region, LastMerge, LRegion);
2623   removeOldExitPreds(Region);
2624 
2625   DEBUG(PHIInfo.dump(MRI));
2626 
2627   SetVector<MRT *> *Children = Region->getChildren();
2628   DEBUG(dbgs() << "===========If Region Start===============\n");
2629   if (LRegion->getHasLoop()) {
2630     DEBUG(dbgs() << "Has Backedge: Yes\n");
2631   } else {
2632     DEBUG(dbgs() << "Has Backedge: No\n");
2633   }
2634 
2635   unsigned BBSelectRegIn;
2636   unsigned BBSelectRegOut;
2637   for (auto CI = Children->begin(), CE = Children->end(); CI != CE; ++CI) {
2638     DEBUG(dbgs() << "CurrentRegion: \n");
2639     DEBUG(LRegion->print(dbgs(), TRI));
2640 
2641     auto CNI = CI;
2642     ++CNI;
2643 
2644     MRT *Child = (*CI);
2645 
2646     if (Child->isRegion()) {
2647 
2648       LinearizedRegion *InnerLRegion =
2649           Child->getRegionMRT()->getLinearizedRegion();
2650       // We found the block is the exit of an inner region, we need
2651       // to put it in the current linearized region.
2652 
2653       DEBUG(dbgs() << "Linearizing region: ");
2654       DEBUG(InnerLRegion->print(dbgs(), TRI));
2655       DEBUG(dbgs() << "\n");
2656 
2657       MachineBasicBlock *InnerEntry = InnerLRegion->getEntry();
2658       if ((&(*(InnerEntry->getParent()->begin()))) == InnerEntry) {
2659         // Entry has already been linearized, no need to do this region.
2660         unsigned OuterSelect = InnerLRegion->getBBSelectRegOut();
2661         unsigned InnerSelectReg =
2662             InnerLRegion->getRegionMRT()->getInnerOutputRegister();
2663         replaceRegisterWith(InnerSelectReg, OuterSelect),
2664             resolvePHIInfos(InnerEntry);
2665         if (!InnerLRegion->getExit()->isSuccessor(CurrentMerge))
2666           InnerLRegion->getExit()->addSuccessor(CurrentMerge);
2667         continue;
2668       }
2669 
2670       BBSelectRegOut = Child->getBBSelectRegOut();
2671       BBSelectRegIn = Child->getBBSelectRegIn();
2672 
2673       DEBUG(dbgs() << "BBSelectRegIn: " << printReg(BBSelectRegIn, TRI)
2674                    << "\n");
2675       DEBUG(dbgs() << "BBSelectRegOut: " << printReg(BBSelectRegOut, TRI)
2676                    << "\n");
2677 
2678       MachineBasicBlock *IfEnd = CurrentMerge;
2679       CurrentMerge = createIfRegion(CurrentMerge, InnerLRegion, LRegion,
2680                                     Child->getRegionMRT()->getEntry(),
2681                                     BBSelectRegIn, BBSelectRegOut);
2682       TII->convertNonUniformIfRegion(CurrentMerge, IfEnd);
2683     } else {
2684       MachineBasicBlock *MBB = Child->getMBBMRT()->getMBB();
2685       DEBUG(dbgs() << "Linearizing block: " << MBB->getNumber() << "\n");
2686 
2687       if (MBB == getSingleExitNode(*(MBB->getParent()))) {
2688         // If this is the exit block then we need to skip to the next.
2689         // The "in" register will be transferred to "out" in the next
2690         // iteration.
2691         continue;
2692       }
2693 
2694       BBSelectRegOut = Child->getBBSelectRegOut();
2695       BBSelectRegIn = Child->getBBSelectRegIn();
2696 
2697       DEBUG(dbgs() << "BBSelectRegIn: " << printReg(BBSelectRegIn, TRI)
2698                    << "\n");
2699       DEBUG(dbgs() << "BBSelectRegOut: " << printReg(BBSelectRegOut, TRI)
2700                    << "\n");
2701 
2702       MachineBasicBlock *IfEnd = CurrentMerge;
2703       // This is a basic block that is not part of an inner region, we
2704       // need to put it in the current linearized region.
2705       CurrentMerge = createIfRegion(CurrentMerge, MBB, LRegion, BBSelectRegIn,
2706                                     BBSelectRegOut);
2707       if (CurrentMerge) {
2708         TII->convertNonUniformIfRegion(CurrentMerge, IfEnd);
2709       }
2710 
2711       DEBUG(PHIInfo.dump(MRI));
2712     }
2713   }
2714 
2715   LRegion->removeFalseRegisterKills(MRI);
2716 
2717   if (LRegion->getHasLoop()) {
2718     MachineBasicBlock *NewSucc = splitEntry(LRegion);
2719     if (isFunctionEntryBlock(LRegion->getEntry())) {
2720       resolvePHIInfos(LRegion->getEntry());
2721     }
2722     const DebugLoc &DL = NewSucc->findDebugLoc(NewSucc->getFirstNonPHI());
2723     unsigned InReg = LRegion->getBBSelectRegIn();
2724     unsigned InnerSelectReg =
2725         MRI->createVirtualRegister(MRI->getRegClass(InReg));
2726     unsigned NewInReg = MRI->createVirtualRegister(MRI->getRegClass(InReg));
2727     TII->materializeImmediate(*(LRegion->getEntry()),
2728                               LRegion->getEntry()->getFirstTerminator(), DL,
2729                               NewInReg, Region->getEntry()->getNumber());
2730     // Need to be careful about updating the registers inside the region.
2731     LRegion->replaceRegisterInsideRegion(InReg, InnerSelectReg, false, MRI);
2732     DEBUG(dbgs() << "Loop BBSelect Merge PHI:\n");
2733     insertMergePHI(LRegion->getEntry(), LRegion->getExit(), NewSucc,
2734                    InnerSelectReg, NewInReg,
2735                    LRegion->getRegionMRT()->getInnerOutputRegister());
2736     splitExit(LRegion);
2737     TII->convertNonUniformLoopRegion(NewSucc, LastMerge);
2738   }
2739 
2740   if (Region->isRoot()) {
2741     TII->insertReturn(*LastMerge);
2742   }
2743 
2744   DEBUG(Region->getEntry()->getParent()->dump());
2745   DEBUG(LRegion->print(dbgs(), TRI));
2746   DEBUG(PHIInfo.dump(MRI));
2747 
2748   DEBUG(dbgs() << "===========If Region End===============\n");
2749 
2750   Region->setLinearizedRegion(LRegion);
2751   return true;
2752 }
2753 
2754 bool AMDGPUMachineCFGStructurizer::structurizeRegion(RegionMRT *Region) {
2755   if (false && regionIsSimpleIf(Region)) {
2756     transformSimpleIfRegion(Region);
2757     return true;
2758   } else if (regionIsSequence(Region)) {
2759     fixupRegionExits(Region);
2760     return false;
2761   } else {
2762     structurizeComplexRegion(Region);
2763   }
2764   return false;
2765 }
2766 
2767 static int structurize_once = 0;
2768 
2769 bool AMDGPUMachineCFGStructurizer::structurizeRegions(RegionMRT *Region,
2770                                                 bool isTopRegion) {
2771   bool Changed = false;
2772 
2773   auto Children = Region->getChildren();
2774   for (auto CI : *Children) {
2775     if (CI->isRegion()) {
2776       Changed |= structurizeRegions(CI->getRegionMRT(), false);
2777     }
2778   }
2779 
2780   if (structurize_once < 2 || true) {
2781     Changed |= structurizeRegion(Region);
2782     structurize_once++;
2783   }
2784   return Changed;
2785 }
2786 
2787 void AMDGPUMachineCFGStructurizer::initFallthroughMap(MachineFunction &MF) {
2788   DEBUG(dbgs() << "Fallthrough Map:\n");
2789   for (auto &MBBI : MF) {
2790     MachineBasicBlock *MBB = MBBI.getFallThrough();
2791     if (MBB != nullptr) {
2792       DEBUG(dbgs() << "Fallthrough: " << MBBI.getNumber() << " -> "
2793                    << MBB->getNumber() << "\n");
2794     }
2795     FallthroughMap[&MBBI] = MBB;
2796   }
2797 }
2798 
2799 void AMDGPUMachineCFGStructurizer::createLinearizedRegion(RegionMRT *Region,
2800                                                     unsigned SelectOut) {
2801   LinearizedRegion *LRegion = new LinearizedRegion();
2802   if (SelectOut) {
2803     LRegion->addLiveOut(SelectOut);
2804     DEBUG(dbgs() << "Add LiveOut (BBSelect): " << printReg(SelectOut, TRI)
2805                  << "\n");
2806   }
2807   LRegion->setRegionMRT(Region);
2808   Region->setLinearizedRegion(LRegion);
2809   LRegion->setParent(Region->getParent()
2810                          ? Region->getParent()->getLinearizedRegion()
2811                          : nullptr);
2812 }
2813 
2814 unsigned
2815 AMDGPUMachineCFGStructurizer::initializeSelectRegisters(MRT *MRT, unsigned SelectOut,
2816                                                   MachineRegisterInfo *MRI,
2817                                                   const SIInstrInfo *TII) {
2818   if (MRT->isRegion()) {
2819     RegionMRT *Region = MRT->getRegionMRT();
2820     Region->setBBSelectRegOut(SelectOut);
2821     unsigned InnerSelectOut = createBBSelectReg(TII, MRI);
2822 
2823     // Fixme: Move linearization creation to the original spot
2824     createLinearizedRegion(Region, SelectOut);
2825 
2826     for (auto CI = Region->getChildren()->begin(),
2827               CE = Region->getChildren()->end();
2828          CI != CE; ++CI) {
2829       InnerSelectOut =
2830           initializeSelectRegisters((*CI), InnerSelectOut, MRI, TII);
2831     }
2832     MRT->setBBSelectRegIn(InnerSelectOut);
2833     return InnerSelectOut;
2834   } else {
2835     MRT->setBBSelectRegOut(SelectOut);
2836     unsigned NewSelectIn = createBBSelectReg(TII, MRI);
2837     MRT->setBBSelectRegIn(NewSelectIn);
2838     return NewSelectIn;
2839   }
2840 }
2841 
2842 static void checkRegOnlyPHIInputs(MachineFunction &MF) {
2843   for (auto &MBBI : MF) {
2844     for (MachineBasicBlock::instr_iterator I = MBBI.instr_begin(),
2845                                            E = MBBI.instr_end();
2846          I != E; ++I) {
2847       MachineInstr &Instr = *I;
2848       if (Instr.isPHI()) {
2849         int numPreds = getPHINumInputs(Instr);
2850         for (int i = 0; i < numPreds; ++i) {
2851           assert(Instr.getOperand(i * 2 + 1).isReg() &&
2852                  "PHI Operand not a register");
2853         }
2854       }
2855     }
2856   }
2857 }
2858 
2859 bool AMDGPUMachineCFGStructurizer::runOnMachineFunction(MachineFunction &MF) {
2860   const SISubtarget &ST = MF.getSubtarget<SISubtarget>();
2861   const SIInstrInfo *TII = ST.getInstrInfo();
2862   TRI = ST.getRegisterInfo();
2863   MRI = &(MF.getRegInfo());
2864   initFallthroughMap(MF);
2865 
2866   checkRegOnlyPHIInputs(MF);
2867   DEBUG(dbgs() << "----STRUCTURIZER START----\n");
2868   DEBUG(MF.dump());
2869 
2870   Regions = &(getAnalysis<MachineRegionInfoPass>().getRegionInfo());
2871   DEBUG(Regions->dump());
2872 
2873   RegionMRT *RTree = MRT::buildMRT(MF, Regions, TII, MRI);
2874   setRegionMRT(RTree);
2875   initializeSelectRegisters(RTree, 0, MRI, TII);
2876   DEBUG(RTree->dump(TRI));
2877   bool result = structurizeRegions(RTree, true);
2878   delete RTree;
2879   DEBUG(dbgs() << "----STRUCTURIZER END----\n");
2880   initFallthroughMap(MF);
2881   return result;
2882 }
2883 
2884 char AMDGPUMachineCFGStructurizerID = AMDGPUMachineCFGStructurizer::ID;
2885 
2886 INITIALIZE_PASS_BEGIN(AMDGPUMachineCFGStructurizer, "amdgpu-machine-cfg-structurizer",
2887                       "AMDGPU Machine CFG Structurizer", false, false)
2888 INITIALIZE_PASS_DEPENDENCY(MachineRegionInfoPass)
2889 INITIALIZE_PASS_END(AMDGPUMachineCFGStructurizer, "amdgpu-machine-cfg-structurizer",
2890                     "AMDGPU Machine CFG Structurizer", false, false)
2891 
2892 FunctionPass *llvm::createAMDGPUMachineCFGStructurizerPass() {
2893   return new AMDGPUMachineCFGStructurizer();
2894 }
2895