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