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