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