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