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