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