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