[InstCombine] Signed saturation patterns
[llvm-complete.git] / lib / Target / AMDGPU / AMDGPUMachineCFGStructurizer.cpp
blobba72f71f43220e67a98e0ab74cff426b9838313d
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.
11 //===----------------------------------------------------------------------===//
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"
19 #include "llvm/ADT/PostOrderIterator.h"
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/CodeGen/MachineBasicBlock.h"
24 #include "llvm/CodeGen/MachineFunction.h"
25 #include "llvm/CodeGen/MachineFunctionPass.h"
26 #include "llvm/CodeGen/MachineInstr.h"
27 #include "llvm/CodeGen/MachineInstrBuilder.h"
28 #include "llvm/CodeGen/MachineOperand.h"
29 #include "llvm/CodeGen/MachineRegionInfo.h"
30 #include "llvm/CodeGen/MachineRegisterInfo.h"
31 #include "llvm/CodeGen/TargetOpcodes.h"
32 #include "llvm/CodeGen/TargetRegisterInfo.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"
38 #include "llvm/Support/ErrorHandling.h"
39 #include "llvm/Support/raw_ostream.h"
40 #include <cassert>
41 #include <tuple>
42 #include <utility>
44 using namespace llvm;
46 #define DEBUG_TYPE "amdgpucfgstructurizer"
48 namespace {
50 class PHILinearizeDestIterator;
52 class PHILinearize {
53 friend class PHILinearizeDestIterator;
55 public:
56 using PHISourceT = std::pair<unsigned, MachineBasicBlock *>;
58 private:
59 using PHISourcesT = DenseSet<PHISourceT>;
60 using PHIInfoElementT = struct {
61 unsigned DestReg;
62 DebugLoc DL;
63 PHISourcesT Sources;
65 using PHIInfoT = SmallPtrSet<PHIInfoElementT *, 2>;
66 PHIInfoT PHIInfo;
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);
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);
94 void dump(MachineRegisterInfo *MRI);
95 void clear();
97 using source_iterator = PHISourcesT::iterator;
98 using dest_iterator = PHILinearizeDestIterator;
100 dest_iterator dests_begin();
101 dest_iterator dests_end();
103 source_iterator sources_begin(unsigned Reg);
104 source_iterator sources_end(unsigned Reg);
107 class PHILinearizeDestIterator {
108 private:
109 PHILinearize::PHIInfoT::iterator Iter;
111 public:
112 PHILinearizeDestIterator(PHILinearize::PHIInfoT::iterator I) : Iter(I) {}
114 unsigned operator*() { return PHILinearize::phiInfoElementGetDest(*Iter); }
115 PHILinearizeDestIterator &operator++() {
116 ++Iter;
117 return *this;
119 bool operator==(const PHILinearizeDestIterator &I) const {
120 return I.Iter == Iter;
122 bool operator!=(const PHILinearizeDestIterator &I) const {
123 return I.Iter != Iter;
127 } // end anonymous namespace
129 unsigned PHILinearize::phiInfoElementGetDest(PHIInfoElementT *Info) {
130 return Info->DestReg;
133 void PHILinearize::phiInfoElementSetDef(PHIInfoElementT *Info,
134 unsigned NewDef) {
135 Info->DestReg = NewDef;
138 PHILinearize::PHISourcesT &
139 PHILinearize::phiInfoElementGetSources(PHIInfoElementT *Info) {
140 return Info->Sources;
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));
154 #endif
156 phiInfoElementGetSources(Info).insert(PHISourceT(SourceReg, SourceMBB));
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));
171 for (auto &Source : ElimiatedSources) {
172 Sources.erase(Source);
176 PHILinearize::PHIInfoElementT *
177 PHILinearize::findPHIInfoElement(unsigned DestReg) {
178 for (auto I : PHIInfo) {
179 if (phiInfoElementGetDest(I) == DestReg) {
180 return I;
183 return nullptr;
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;
197 return nullptr;
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);
211 return FoundSource;
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);
224 void PHILinearize::replaceDef(unsigned OldDestReg, unsigned NewDestReg) {
225 phiInfoElementSetDef(findPHIInfoElement(OldDestReg), NewDestReg);
228 void PHILinearize::deleteDef(unsigned DestReg) {
229 PHIInfoElementT *InfoElement = findPHIInfoElement(DestReg);
230 PHIInfo.erase(InfoElement);
231 delete InfoElement;
234 void PHILinearize::addSource(unsigned DestReg, unsigned SourceReg,
235 MachineBasicBlock *SourceMBB) {
236 phiInfoElementAddSource(findPHIInfoElement(DestReg), SourceReg, SourceMBB);
239 void PHILinearize::removeSource(unsigned DestReg, unsigned SourceReg,
240 MachineBasicBlock *SourceMBB) {
241 phiInfoElementRemoveSource(findPHIInfoElement(DestReg), SourceReg, SourceMBB);
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;
252 return false;
255 bool PHILinearize::isSource(unsigned Reg, MachineBasicBlock *SourceMBB) {
256 unsigned DestReg;
257 return findDest(Reg, SourceMBB, DestReg);
260 unsigned PHILinearize::getNumSources(unsigned DestReg) {
261 return phiInfoElementGetSources(findPHIInfoElement(DestReg)).size();
264 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
265 LLVM_DUMP_METHOD void PHILinearize::dump(MachineRegisterInfo *MRI) {
266 const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
267 dbgs() << "=PHIInfo Start=\n";
268 for (auto PII : this->PHIInfo) {
269 PHIInfoElementT &Element = *PII;
270 dbgs() << "Dest: " << printReg(Element.DestReg, TRI)
271 << " Sources: {";
272 for (auto &SI : Element.Sources) {
273 dbgs() << printReg(SI.first, TRI) << '(' << printMBBReference(*SI.second)
274 << "),";
276 dbgs() << "}\n";
278 dbgs() << "=PHIInfo End=\n";
280 #endif
282 void PHILinearize::clear() { PHIInfo = PHIInfoT(); }
284 PHILinearize::dest_iterator PHILinearize::dests_begin() {
285 return PHILinearizeDestIterator(PHIInfo.begin());
288 PHILinearize::dest_iterator PHILinearize::dests_end() {
289 return PHILinearizeDestIterator(PHIInfo.end());
292 PHILinearize::source_iterator PHILinearize::sources_begin(unsigned Reg) {
293 auto InfoElement = findPHIInfoElement(Reg);
294 return phiInfoElementGetSources(InfoElement).begin();
297 PHILinearize::source_iterator PHILinearize::sources_end(unsigned Reg) {
298 auto InfoElement = findPHIInfoElement(Reg);
299 return phiInfoElementGetSources(InfoElement).end();
302 static unsigned getPHINumInputs(MachineInstr &PHI) {
303 assert(PHI.isPHI());
304 return (PHI.getNumOperands() - 1) / 2;
307 static MachineBasicBlock *getPHIPred(MachineInstr &PHI, unsigned Index) {
308 assert(PHI.isPHI());
309 return PHI.getOperand(Index * 2 + 2).getMBB();
312 static void setPhiPred(MachineInstr &PHI, unsigned Index,
313 MachineBasicBlock *NewPred) {
314 PHI.getOperand(Index * 2 + 2).setMBB(NewPred);
317 static unsigned getPHISourceReg(MachineInstr &PHI, unsigned Index) {
318 assert(PHI.isPHI());
319 return PHI.getOperand(Index * 2 + 1).getReg();
322 static unsigned getPHIDestReg(MachineInstr &PHI) {
323 assert(PHI.isPHI());
324 return PHI.getOperand(0).getReg();
327 namespace {
329 class RegionMRT;
330 class MBBMRT;
332 class LinearizedRegion {
333 protected:
334 MachineBasicBlock *Entry;
335 // The exit block is part of the region, and is the last
336 // merge block before exiting the region.
337 MachineBasicBlock *Exit;
338 DenseSet<unsigned> LiveOuts;
339 SmallPtrSet<MachineBasicBlock *, 1> MBBs;
340 bool HasLoop;
341 LinearizedRegion *Parent;
342 RegionMRT *RMRT;
344 void storeLiveOutReg(MachineBasicBlock *MBB, unsigned Reg,
345 MachineInstr *DefInstr, const MachineRegisterInfo *MRI,
346 const TargetRegisterInfo *TRI, PHILinearize &PHIInfo);
348 void storeLiveOutRegRegion(RegionMRT *Region, unsigned Reg,
349 MachineInstr *DefInstr,
350 const MachineRegisterInfo *MRI,
351 const TargetRegisterInfo *TRI,
352 PHILinearize &PHIInfo);
354 void storeMBBLiveOuts(MachineBasicBlock *MBB, const MachineRegisterInfo *MRI,
355 const TargetRegisterInfo *TRI, PHILinearize &PHIInfo,
356 RegionMRT *TopRegion);
358 void storeLiveOuts(MachineBasicBlock *MBB, const MachineRegisterInfo *MRI,
359 const TargetRegisterInfo *TRI, PHILinearize &PHIInfo);
361 void storeLiveOuts(RegionMRT *Region, const MachineRegisterInfo *MRI,
362 const TargetRegisterInfo *TRI, PHILinearize &PHIInfo,
363 RegionMRT *TopRegion = nullptr);
365 public:
366 LinearizedRegion();
367 LinearizedRegion(MachineBasicBlock *MBB, const MachineRegisterInfo *MRI,
368 const TargetRegisterInfo *TRI, PHILinearize &PHIInfo);
369 ~LinearizedRegion() = default;
371 void setRegionMRT(RegionMRT *Region) { RMRT = Region; }
373 RegionMRT *getRegionMRT() { return RMRT; }
375 void setParent(LinearizedRegion *P) { Parent = P; }
377 LinearizedRegion *getParent() { return Parent; }
379 void print(raw_ostream &OS, const TargetRegisterInfo *TRI = nullptr);
381 void setBBSelectRegIn(unsigned Reg);
383 unsigned getBBSelectRegIn();
385 void setBBSelectRegOut(unsigned Reg, bool IsLiveOut);
387 unsigned getBBSelectRegOut();
389 void setHasLoop(bool Value);
391 bool getHasLoop();
393 void addLiveOut(unsigned VReg);
395 void removeLiveOut(unsigned Reg);
397 void replaceLiveOut(unsigned OldReg, unsigned NewReg);
399 void replaceRegister(unsigned Register, unsigned NewRegister,
400 MachineRegisterInfo *MRI, bool ReplaceInside,
401 bool ReplaceOutside, bool IncludeLoopPHIs);
403 void replaceRegisterInsideRegion(unsigned Register, unsigned NewRegister,
404 bool IncludeLoopPHIs,
405 MachineRegisterInfo *MRI);
407 void replaceRegisterOutsideRegion(unsigned Register, unsigned NewRegister,
408 bool IncludeLoopPHIs,
409 MachineRegisterInfo *MRI);
411 DenseSet<unsigned> *getLiveOuts();
413 void setEntry(MachineBasicBlock *NewEntry);
415 MachineBasicBlock *getEntry();
417 void setExit(MachineBasicBlock *NewExit);
419 MachineBasicBlock *getExit();
421 void addMBB(MachineBasicBlock *MBB);
423 void addMBBs(LinearizedRegion *InnerRegion);
425 bool contains(MachineBasicBlock *MBB);
427 bool isLiveOut(unsigned Reg);
429 bool hasNoDef(unsigned Reg, MachineRegisterInfo *MRI);
431 void removeFalseRegisterKills(MachineRegisterInfo *MRI);
433 void initLiveOut(RegionMRT *Region, const MachineRegisterInfo *MRI,
434 const TargetRegisterInfo *TRI, PHILinearize &PHIInfo);
437 class MRT {
438 protected:
439 RegionMRT *Parent;
440 unsigned BBSelectRegIn;
441 unsigned BBSelectRegOut;
443 public:
444 virtual ~MRT() = default;
446 unsigned getBBSelectRegIn() { return BBSelectRegIn; }
448 unsigned getBBSelectRegOut() { return BBSelectRegOut; }
450 void setBBSelectRegIn(unsigned Reg) { BBSelectRegIn = Reg; }
452 void setBBSelectRegOut(unsigned Reg) { BBSelectRegOut = Reg; }
454 virtual RegionMRT *getRegionMRT() { return nullptr; }
456 virtual MBBMRT *getMBBMRT() { return nullptr; }
458 bool isRegion() { return getRegionMRT() != nullptr; }
460 bool isMBB() { return getMBBMRT() != nullptr; }
462 bool isRoot() { return Parent == nullptr; }
464 void setParent(RegionMRT *Region) { Parent = Region; }
466 RegionMRT *getParent() { return Parent; }
468 static MachineBasicBlock *
469 initializeMRT(MachineFunction &MF, const MachineRegionInfo *RegionInfo,
470 DenseMap<MachineRegion *, RegionMRT *> &RegionMap);
472 static RegionMRT *buildMRT(MachineFunction &MF,
473 const MachineRegionInfo *RegionInfo,
474 const SIInstrInfo *TII,
475 MachineRegisterInfo *MRI);
477 virtual void dump(const TargetRegisterInfo *TRI, int depth = 0) = 0;
479 void dumpDepth(int depth) {
480 for (int i = depth; i > 0; --i) {
481 dbgs() << " ";
486 class MBBMRT : public MRT {
487 MachineBasicBlock *MBB;
489 public:
490 MBBMRT(MachineBasicBlock *BB) : MBB(BB) {
491 setParent(nullptr);
492 setBBSelectRegOut(0);
493 setBBSelectRegIn(0);
496 MBBMRT *getMBBMRT() override { return this; }
498 MachineBasicBlock *getMBB() { return MBB; }
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";
508 class RegionMRT : public MRT {
509 protected:
510 MachineRegion *Region;
511 LinearizedRegion *LRegion = nullptr;
512 MachineBasicBlock *Succ = nullptr;
513 SetVector<MRT *> Children;
515 public:
516 RegionMRT(MachineRegion *MachineRegion) : Region(MachineRegion) {
517 setParent(nullptr);
518 setBBSelectRegOut(0);
519 setBBSelectRegIn(0);
522 ~RegionMRT() override {
523 if (LRegion) {
524 delete LRegion;
527 for (auto CI : Children) {
528 delete &(*CI);
532 RegionMRT *getRegionMRT() override { return this; }
534 void setLinearizedRegion(LinearizedRegion *LinearizeRegion) {
535 LRegion = LinearizeRegion;
538 LinearizedRegion *getLinearizedRegion() { return LRegion; }
540 MachineRegion *getMachineRegion() { return Region; }
542 unsigned getInnerOutputRegister() {
543 return (*(Children.begin()))->getBBSelectRegOut();
546 void addChild(MRT *Tree) { Children.insert(Tree); }
548 SetVector<MRT *> *getChildren() { return &Children; }
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";
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);
566 MRT *getEntryTree() { return Children.back(); }
568 MRT *getExitTree() { return Children.front(); }
570 MachineBasicBlock *getEntry() {
571 MRT *Tree = Children.back();
572 return (Tree->isRegion()) ? Tree->getRegionMRT()->getEntry()
573 : Tree->getMBBMRT()->getMBB();
576 MachineBasicBlock *getExit() {
577 MRT *Tree = Children.front();
578 return (Tree->isRegion()) ? Tree->getRegionMRT()->getExit()
579 : Tree->getMBBMRT()->getMBB();
582 void setSucc(MachineBasicBlock *MBB) { Succ = MBB; }
584 MachineBasicBlock *getSucc() { return Succ; }
586 bool contains(MachineBasicBlock *MBB) {
587 for (auto CI : Children) {
588 if (CI->isMBB()) {
589 if (MBB == CI->getMBBMRT()->getMBB()) {
590 return true;
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;
601 return false;
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);
615 } // end anonymous namespace
617 static unsigned createBBSelectReg(const SIInstrInfo *TII,
618 MachineRegisterInfo *MRI) {
619 return MRI->createVirtualRegister(TII->getPreferredSelectRegClass(32));
622 MachineBasicBlock *
623 MRT::initializeMRT(MachineFunction &MF, const MachineRegionInfo *RegionInfo,
624 DenseMap<MachineRegion *, RegionMRT *> &RegionMap) {
625 for (auto &MFI : MF) {
626 MachineBasicBlock *ExitMBB = &MFI;
627 if (ExitMBB->succ_size() == 0) {
628 return ExitMBB;
631 llvm_unreachable("CFG has no exit block");
632 return nullptr;
635 RegionMRT *MRT::buildMRT(MachineFunction &MF,
636 const MachineRegionInfo *RegionInfo,
637 const SIInstrInfo *TII, MachineRegisterInfo *MRI) {
638 SmallPtrSet<MachineRegion *, 4> PlacedRegions;
639 DenseMap<MachineRegion *, RegionMRT *> RegionMap;
640 MachineRegion *TopLevelRegion = RegionInfo->getTopLevelRegion();
641 RegionMRT *Result = new RegionMRT(TopLevelRegion);
642 RegionMap[TopLevelRegion] = Result;
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);
648 unsigned BBSelectRegIn = createBBSelectReg(TII, MRI);
649 MBBMRT *ExitMRT = new MBBMRT(Exit);
650 RegionMap[RegionInfo->getRegionFor(Exit)]->addChild(ExitMRT);
651 ExitMRT->setBBSelectRegIn(BBSelectRegIn);
653 for (auto MBBI : post_order(&(MF.front()))) {
654 MachineBasicBlock *MBB = &(*MBBI);
656 // Skip Exit since we already added it
657 if (MBB == Exit) {
658 continue;
661 LLVM_DEBUG(dbgs() << "Visiting " << printMBBReference(*MBB) << "\n");
662 MBBMRT *NewMBB = new MBBMRT(MBB);
663 MachineRegion *Region = RegionInfo->getRegionFor(MBB);
665 // Ensure we have the MRT region
666 if (RegionMap.count(Region) == 0) {
667 RegionMRT *NewMRTRegion = new RegionMRT(Region);
668 RegionMap[Region] = NewMRTRegion;
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();
680 RegionMap[Parent]->addChild(NewMRTRegion);
681 NewMRTRegion->setParent(RegionMap[Parent]);
684 // Add MBB to Region MRT
685 RegionMap[Region]->addChild(NewMBB);
686 NewMBB->setParent(RegionMap[Region]);
687 RegionMap[Region]->setSucc(Region->getExit());
689 return Result;
692 void LinearizedRegion::storeLiveOutReg(MachineBasicBlock *MBB, unsigned Reg,
693 MachineInstr *DefInstr,
694 const MachineRegisterInfo *MRI,
695 const TargetRegisterInfo *TRI,
696 PHILinearize &PHIInfo) {
697 if (Register::isVirtualRegister(Reg)) {
698 LLVM_DEBUG(dbgs() << "Considering Register: " << printReg(Reg, TRI)
699 << "\n");
700 // If this is a source register to a PHI we are chaining, it
701 // must be live out.
702 if (PHIInfo.isSource(Reg)) {
703 LLVM_DEBUG(dbgs() << "Add LiveOut (PHI): " << printReg(Reg, TRI) << "\n");
704 addLiveOut(Reg);
705 } else {
706 // If this is live out of the MBB
707 for (auto &UI : MRI->use_operands(Reg)) {
708 if (UI.getParent()->getParent() != MBB) {
709 LLVM_DEBUG(dbgs() << "Add LiveOut (MBB " << printMBBReference(*MBB)
710 << "): " << printReg(Reg, TRI) << "\n");
711 addLiveOut(Reg);
712 } else {
713 // If the use is in the same MBB we have to make sure
714 // it is after the def, otherwise it is live out in a loop
715 MachineInstr *UseInstr = UI.getParent();
716 for (MachineBasicBlock::instr_iterator
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);
732 void LinearizedRegion::storeLiveOutRegRegion(RegionMRT *Region, unsigned Reg,
733 MachineInstr *DefInstr,
734 const MachineRegisterInfo *MRI,
735 const TargetRegisterInfo *TRI,
736 PHILinearize &PHIInfo) {
737 if (Register::isVirtualRegister(Reg)) {
738 LLVM_DEBUG(dbgs() << "Considering Register: " << printReg(Reg, TRI)
739 << "\n");
740 for (auto &UI : MRI->use_operands(Reg)) {
741 if (!Region->contains(UI.getParent()->getParent())) {
742 LLVM_DEBUG(dbgs() << "Add LiveOut (Region " << (void *)Region
743 << "): " << printReg(Reg, TRI) << "\n");
744 addLiveOut(Reg);
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);
760 for (auto &IRI : II.implicit_operands()) {
761 if (IRI.isDef()) {
762 storeLiveOutReg(MBB, IRI.getReg(), IRI.getParent(), MRI, TRI, PHIInfo);
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);
790 LLVM_DEBUG(dbgs() << "-Store Live Outs Endn-\n");
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);
803 for (auto &IRI : II.implicit_operands()) {
804 if (IRI.isDef()) {
805 storeLiveOutRegRegion(TopRegion, IRI.getReg(), IRI.getParent(), MRI,
806 TRI, PHIInfo);
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();
819 RegionMRT *TopRegion =
820 CurrentTopRegion == nullptr ? Region : CurrentTopRegion;
822 // Check if exit is end of function, if so, no live outs.
823 if (Exit == nullptr)
824 return;
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);
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);
860 #ifndef NDEBUG
861 void LinearizedRegion::print(raw_ostream &OS, const TargetRegisterInfo *TRI) {
862 OS << "Linearized Region {";
863 bool IsFirst = true;
864 for (const auto &MBB : MBBs) {
865 if (IsFirst) {
866 IsFirst = false;
867 } else {
868 OS << " ,";
870 OS << MBB->getNumber();
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) << " ";
879 OS << "} \n";
881 #endif
883 unsigned LinearizedRegion::getBBSelectRegIn() {
884 return getRegionMRT()->getBBSelectRegIn();
887 unsigned LinearizedRegion::getBBSelectRegOut() {
888 return getRegionMRT()->getBBSelectRegOut();
891 void LinearizedRegion::setHasLoop(bool Value) { HasLoop = Value; }
893 bool LinearizedRegion::getHasLoop() { return HasLoop; }
895 void LinearizedRegion::addLiveOut(unsigned VReg) { LiveOuts.insert(VReg); }
897 void LinearizedRegion::removeLiveOut(unsigned Reg) {
898 if (isLiveOut(Reg))
899 LiveOuts.erase(Reg);
902 void LinearizedRegion::replaceLiveOut(unsigned OldReg, unsigned NewReg) {
903 if (isLiveOut(OldReg)) {
904 removeLiveOut(OldReg);
905 addLiveOut(NewReg);
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");
915 LLVM_DEBUG(
916 dbgs() << "Pepareing to replace register (region): "
917 << printReg(Register, MRI->getTargetRegisterInfo()) << " with "
918 << printReg(NewRegister, MRI->getTargetRegisterInfo()) << "\n");
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();
934 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Register),
935 E = MRI->reg_end();
936 I != E;) {
937 MachineOperand &O = *I;
938 ++I;
940 // We don't rewrite defs.
941 if (O.isDef())
942 continue;
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) {
952 if (Register::isPhysicalRegister(NewRegister)) {
953 LLVM_DEBUG(dbgs() << "Trying to substitute physical register: "
954 << printReg(NewRegister, MRI->getTargetRegisterInfo())
955 << "\n");
956 llvm_unreachable("Cannot substitute physical registers");
957 } else {
958 LLVM_DEBUG(dbgs() << "Replacing register (region): "
959 << printReg(Register, MRI->getTargetRegisterInfo())
960 << " with "
961 << printReg(NewRegister, MRI->getTargetRegisterInfo())
962 << "\n");
963 O.setReg(NewRegister);
969 void LinearizedRegion::replaceRegisterInsideRegion(unsigned Register,
970 unsigned NewRegister,
971 bool IncludeLoopPHIs,
972 MachineRegisterInfo *MRI) {
973 replaceRegister(Register, NewRegister, MRI, true, false, IncludeLoopPHIs);
976 void LinearizedRegion::replaceRegisterOutsideRegion(unsigned Register,
977 unsigned NewRegister,
978 bool IncludeLoopPHIs,
979 MachineRegisterInfo *MRI) {
980 replaceRegister(Register, NewRegister, MRI, false, true, IncludeLoopPHIs);
983 DenseSet<unsigned> *LinearizedRegion::getLiveOuts() { return &LiveOuts; }
985 void LinearizedRegion::setEntry(MachineBasicBlock *NewEntry) {
986 Entry = NewEntry;
989 MachineBasicBlock *LinearizedRegion::getEntry() { return Entry; }
991 void LinearizedRegion::setExit(MachineBasicBlock *NewExit) { Exit = NewExit; }
993 MachineBasicBlock *LinearizedRegion::getExit() { return Exit; }
995 void LinearizedRegion::addMBB(MachineBasicBlock *MBB) { MBBs.insert(MBB); }
997 void LinearizedRegion::addMBBs(LinearizedRegion *InnerRegion) {
998 for (const auto &MBB : InnerRegion->MBBs) {
999 addMBB(MBB);
1003 bool LinearizedRegion::contains(MachineBasicBlock *MBB) {
1004 return MBBs.count(MBB) == 1;
1007 bool LinearizedRegion::isLiveOut(unsigned Reg) {
1008 return LiveOuts.count(Reg) == 1;
1011 bool LinearizedRegion::hasNoDef(unsigned Reg, MachineRegisterInfo *MRI) {
1012 return MRI->def_begin(Reg) == MRI->def_end();
1015 // After the code has been structurized, what was flagged as kills
1016 // before are no longer register kills.
1017 void LinearizedRegion::removeFalseRegisterKills(MachineRegisterInfo *MRI) {
1018 const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
1019 (void)TRI; // It's used by LLVM_DEBUG.
1021 for (auto MBBI : MBBs) {
1022 MachineBasicBlock *MBB = MBBI;
1023 for (auto &II : *MBB) {
1024 for (auto &RI : II.uses()) {
1025 if (RI.isReg()) {
1026 Register Reg = RI.getReg();
1027 if (Register::isVirtualRegister(Reg)) {
1028 if (hasNoDef(Reg, MRI))
1029 continue;
1030 if (!MRI->hasOneDef(Reg)) {
1031 LLVM_DEBUG(this->getEntry()->getParent()->dump());
1032 LLVM_DEBUG(dbgs() << printReg(Reg, TRI) << "\n");
1035 if (MRI->def_begin(Reg) == MRI->def_end()) {
1036 LLVM_DEBUG(dbgs() << "Register "
1037 << printReg(Reg, MRI->getTargetRegisterInfo())
1038 << " has NO defs\n");
1039 } else if (!MRI->hasOneDef(Reg)) {
1040 LLVM_DEBUG(dbgs() << "Register "
1041 << printReg(Reg, MRI->getTargetRegisterInfo())
1042 << " has multiple defs\n");
1045 assert(MRI->hasOneDef(Reg) && "Register has multiple definitions");
1046 MachineOperand *Def = &(*(MRI->def_begin(Reg)));
1047 MachineOperand *UseOperand = &(RI);
1048 bool UseIsOutsideDefMBB = Def->getParent()->getParent() != MBB;
1049 if (UseIsOutsideDefMBB && UseOperand->isKill()) {
1050 LLVM_DEBUG(dbgs() << "Removing kill flag on register: "
1051 << printReg(Reg, TRI) << "\n");
1052 UseOperand->setIsKill(false);
1061 void LinearizedRegion::initLiveOut(RegionMRT *Region,
1062 const MachineRegisterInfo *MRI,
1063 const TargetRegisterInfo *TRI,
1064 PHILinearize &PHIInfo) {
1065 storeLiveOuts(Region, MRI, TRI, PHIInfo);
1068 LinearizedRegion::LinearizedRegion(MachineBasicBlock *MBB,
1069 const MachineRegisterInfo *MRI,
1070 const TargetRegisterInfo *TRI,
1071 PHILinearize &PHIInfo) {
1072 setEntry(MBB);
1073 setExit(MBB);
1074 storeLiveOuts(MBB, MRI, TRI, PHIInfo);
1075 MBBs.insert(MBB);
1076 Parent = nullptr;
1079 LinearizedRegion::LinearizedRegion() {
1080 setEntry(nullptr);
1081 setExit(nullptr);
1082 Parent = nullptr;
1085 namespace {
1087 class AMDGPUMachineCFGStructurizer : public MachineFunctionPass {
1088 private:
1089 const MachineRegionInfo *Regions;
1090 const SIInstrInfo *TII;
1091 const TargetRegisterInfo *TRI;
1092 MachineRegisterInfo *MRI;
1093 unsigned BBSelectRegister;
1094 PHILinearize PHIInfo;
1095 DenseMap<MachineBasicBlock *, MachineBasicBlock *> FallthroughMap;
1096 RegionMRT *RMRT;
1098 void getPHIRegionIndices(RegionMRT *Region, MachineInstr &PHI,
1099 SmallVector<unsigned, 2> &RegionIndices);
1100 void getPHIRegionIndices(LinearizedRegion *Region, MachineInstr &PHI,
1101 SmallVector<unsigned, 2> &RegionIndices);
1102 void getPHINonRegionIndices(LinearizedRegion *Region, MachineInstr &PHI,
1103 SmallVector<unsigned, 2> &PHINonRegionIndices);
1105 void storePHILinearizationInfoDest(
1106 unsigned LDestReg, MachineInstr &PHI,
1107 SmallVector<unsigned, 2> *RegionIndices = nullptr);
1109 unsigned storePHILinearizationInfo(MachineInstr &PHI,
1110 SmallVector<unsigned, 2> *RegionIndices);
1112 void extractKilledPHIs(MachineBasicBlock *MBB);
1114 bool shrinkPHI(MachineInstr &PHI, SmallVector<unsigned, 2> &PHIIndices,
1115 unsigned *ReplaceReg);
1117 bool shrinkPHI(MachineInstr &PHI, unsigned CombinedSourceReg,
1118 MachineBasicBlock *SourceMBB,
1119 SmallVector<unsigned, 2> &PHIIndices, unsigned *ReplaceReg);
1121 void replacePHI(MachineInstr &PHI, unsigned CombinedSourceReg,
1122 MachineBasicBlock *LastMerge,
1123 SmallVector<unsigned, 2> &PHIRegionIndices);
1124 void replaceEntryPHI(MachineInstr &PHI, unsigned CombinedSourceReg,
1125 MachineBasicBlock *IfMBB,
1126 SmallVector<unsigned, 2> &PHIRegionIndices);
1127 void replaceLiveOutRegs(MachineInstr &PHI,
1128 SmallVector<unsigned, 2> &PHIRegionIndices,
1129 unsigned CombinedSourceReg,
1130 LinearizedRegion *LRegion);
1131 void rewriteRegionExitPHI(RegionMRT *Region, MachineBasicBlock *LastMerge,
1132 MachineInstr &PHI, LinearizedRegion *LRegion);
1134 void rewriteRegionExitPHIs(RegionMRT *Region, MachineBasicBlock *LastMerge,
1135 LinearizedRegion *LRegion);
1136 void rewriteRegionEntryPHI(LinearizedRegion *Region, MachineBasicBlock *IfMBB,
1137 MachineInstr &PHI);
1138 void rewriteRegionEntryPHIs(LinearizedRegion *Region,
1139 MachineBasicBlock *IfMBB);
1141 bool regionIsSimpleIf(RegionMRT *Region);
1143 void transformSimpleIfRegion(RegionMRT *Region);
1145 void eliminateDeadBranchOperands(MachineBasicBlock::instr_iterator &II);
1147 void insertUnconditionalBranch(MachineBasicBlock *MBB,
1148 MachineBasicBlock *Dest,
1149 const DebugLoc &DL = DebugLoc());
1151 MachineBasicBlock *createLinearizedExitBlock(RegionMRT *Region);
1153 void insertMergePHI(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB,
1154 MachineBasicBlock *MergeBB, unsigned DestRegister,
1155 unsigned IfSourceRegister, unsigned CodeSourceRegister,
1156 bool IsUndefIfSource = false);
1158 MachineBasicBlock *createIfBlock(MachineBasicBlock *MergeBB,
1159 MachineBasicBlock *CodeBBStart,
1160 MachineBasicBlock *CodeBBEnd,
1161 MachineBasicBlock *SelectBB, unsigned IfReg,
1162 bool InheritPreds);
1164 void prunePHIInfo(MachineBasicBlock *MBB);
1165 void createEntryPHI(LinearizedRegion *CurrentRegion, unsigned DestReg);
1167 void createEntryPHIs(LinearizedRegion *CurrentRegion);
1168 void resolvePHIInfos(MachineBasicBlock *FunctionEntry);
1170 void replaceRegisterWith(unsigned Register, unsigned NewRegister);
1172 MachineBasicBlock *createIfRegion(MachineBasicBlock *MergeBB,
1173 MachineBasicBlock *CodeBB,
1174 LinearizedRegion *LRegion,
1175 unsigned BBSelectRegIn,
1176 unsigned BBSelectRegOut);
1178 MachineBasicBlock *
1179 createIfRegion(MachineBasicBlock *MergeMBB, LinearizedRegion *InnerRegion,
1180 LinearizedRegion *CurrentRegion, MachineBasicBlock *SelectBB,
1181 unsigned BBSelectRegIn, unsigned BBSelectRegOut);
1182 void ensureCondIsNotKilled(SmallVector<MachineOperand, 1> Cond);
1184 void rewriteCodeBBTerminator(MachineBasicBlock *CodeBB,
1185 MachineBasicBlock *MergeBB,
1186 unsigned BBSelectReg);
1188 MachineInstr *getDefInstr(unsigned Reg);
1189 void insertChainedPHI(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB,
1190 MachineBasicBlock *MergeBB,
1191 LinearizedRegion *InnerRegion, unsigned DestReg,
1192 unsigned SourceReg);
1193 bool containsDef(MachineBasicBlock *MBB, LinearizedRegion *InnerRegion,
1194 unsigned Register);
1195 void rewriteLiveOutRegs(MachineBasicBlock *IfBB, MachineBasicBlock *CodeBB,
1196 MachineBasicBlock *MergeBB,
1197 LinearizedRegion *InnerRegion,
1198 LinearizedRegion *LRegion);
1200 void splitLoopPHI(MachineInstr &PHI, MachineBasicBlock *Entry,
1201 MachineBasicBlock *EntrySucc, LinearizedRegion *LRegion);
1202 void splitLoopPHIs(MachineBasicBlock *Entry, MachineBasicBlock *EntrySucc,
1203 LinearizedRegion *LRegion);
1205 MachineBasicBlock *splitExit(LinearizedRegion *LRegion);
1207 MachineBasicBlock *splitEntry(LinearizedRegion *LRegion);
1209 LinearizedRegion *initLinearizedRegion(RegionMRT *Region);
1211 bool structurizeComplexRegion(RegionMRT *Region);
1213 bool structurizeRegion(RegionMRT *Region);
1215 bool structurizeRegions(RegionMRT *Region, bool isTopRegion);
1217 public:
1218 static char ID;
1220 AMDGPUMachineCFGStructurizer() : MachineFunctionPass(ID) {
1221 initializeAMDGPUMachineCFGStructurizerPass(*PassRegistry::getPassRegistry());
1224 void getAnalysisUsage(AnalysisUsage &AU) const override {
1225 AU.addRequired<MachineRegionInfoPass>();
1226 MachineFunctionPass::getAnalysisUsage(AU);
1229 void initFallthroughMap(MachineFunction &MF);
1231 void createLinearizedRegion(RegionMRT *Region, unsigned SelectOut);
1233 unsigned initializeSelectRegisters(MRT *MRT, unsigned ExistingExitReg,
1234 MachineRegisterInfo *MRI,
1235 const SIInstrInfo *TII);
1237 void setRegionMRT(RegionMRT *RegionTree) { RMRT = RegionTree; }
1239 RegionMRT *getRegionMRT() { return RMRT; }
1241 bool runOnMachineFunction(MachineFunction &MF) override;
1244 } // end anonymous namespace
1246 char AMDGPUMachineCFGStructurizer::ID = 0;
1248 bool AMDGPUMachineCFGStructurizer::regionIsSimpleIf(RegionMRT *Region) {
1249 MachineBasicBlock *Entry = Region->getEntry();
1250 MachineBasicBlock *Succ = Region->getSucc();
1251 bool FoundBypass = false;
1252 bool FoundIf = false;
1254 if (Entry->succ_size() != 2) {
1255 return false;
1258 for (MachineBasicBlock::const_succ_iterator SI = Entry->succ_begin(),
1259 E = Entry->succ_end();
1260 SI != E; ++SI) {
1261 MachineBasicBlock *Current = *SI;
1263 if (Current == Succ) {
1264 FoundBypass = true;
1265 } else if ((Current->succ_size() == 1) &&
1266 *(Current->succ_begin()) == Succ) {
1267 FoundIf = true;
1271 return FoundIf && FoundBypass;
1274 void AMDGPUMachineCFGStructurizer::transformSimpleIfRegion(RegionMRT *Region) {
1275 MachineBasicBlock *Entry = Region->getEntry();
1276 MachineBasicBlock *Exit = Region->getExit();
1277 TII->convertNonUniformIfRegion(Entry, Exit);
1280 static void fixMBBTerminator(MachineBasicBlock *MBB) {
1281 if (MBB->succ_size() == 1) {
1282 auto *Succ = *(MBB->succ_begin());
1283 for (auto &TI : MBB->terminators()) {
1284 for (auto &UI : TI.uses()) {
1285 if (UI.isMBB() && UI.getMBB() != Succ) {
1286 UI.setMBB(Succ);
1293 static void fixRegionTerminator(RegionMRT *Region) {
1294 MachineBasicBlock *InternalSucc = nullptr;
1295 MachineBasicBlock *ExternalSucc = nullptr;
1296 LinearizedRegion *LRegion = Region->getLinearizedRegion();
1297 auto Exit = LRegion->getExit();
1299 SmallPtrSet<MachineBasicBlock *, 2> Successors;
1300 for (MachineBasicBlock::const_succ_iterator SI = Exit->succ_begin(),
1301 SE = Exit->succ_end();
1302 SI != SE; ++SI) {
1303 MachineBasicBlock *Succ = *SI;
1304 if (LRegion->contains(Succ)) {
1305 // Do not allow re-assign
1306 assert(InternalSucc == nullptr);
1307 InternalSucc = Succ;
1308 } else {
1309 // Do not allow re-assign
1310 assert(ExternalSucc == nullptr);
1311 ExternalSucc = Succ;
1315 for (auto &TI : Exit->terminators()) {
1316 for (auto &UI : TI.uses()) {
1317 if (UI.isMBB()) {
1318 auto Target = UI.getMBB();
1319 if (Target != InternalSucc && Target != ExternalSucc) {
1320 UI.setMBB(ExternalSucc);
1327 // If a region region is just a sequence of regions (and the exit
1328 // block in the case of the top level region), we can simply skip
1329 // linearizing it, because it is already linear
1330 bool regionIsSequence(RegionMRT *Region) {
1331 auto Children = Region->getChildren();
1332 for (auto CI : *Children) {
1333 if (!CI->isRegion()) {
1334 if (CI->getMBBMRT()->getMBB()->succ_size() > 1) {
1335 return false;
1339 return true;
1342 void fixupRegionExits(RegionMRT *Region) {
1343 auto Children = Region->getChildren();
1344 for (auto CI : *Children) {
1345 if (!CI->isRegion()) {
1346 fixMBBTerminator(CI->getMBBMRT()->getMBB());
1347 } else {
1348 fixRegionTerminator(CI->getRegionMRT());
1353 void AMDGPUMachineCFGStructurizer::getPHIRegionIndices(
1354 RegionMRT *Region, MachineInstr &PHI,
1355 SmallVector<unsigned, 2> &PHIRegionIndices) {
1356 unsigned NumInputs = getPHINumInputs(PHI);
1357 for (unsigned i = 0; i < NumInputs; ++i) {
1358 MachineBasicBlock *Pred = getPHIPred(PHI, i);
1359 if (Region->contains(Pred)) {
1360 PHIRegionIndices.push_back(i);
1365 void AMDGPUMachineCFGStructurizer::getPHIRegionIndices(
1366 LinearizedRegion *Region, MachineInstr &PHI,
1367 SmallVector<unsigned, 2> &PHIRegionIndices) {
1368 unsigned NumInputs = getPHINumInputs(PHI);
1369 for (unsigned i = 0; i < NumInputs; ++i) {
1370 MachineBasicBlock *Pred = getPHIPred(PHI, i);
1371 if (Region->contains(Pred)) {
1372 PHIRegionIndices.push_back(i);
1377 void AMDGPUMachineCFGStructurizer::getPHINonRegionIndices(
1378 LinearizedRegion *Region, MachineInstr &PHI,
1379 SmallVector<unsigned, 2> &PHINonRegionIndices) {
1380 unsigned NumInputs = getPHINumInputs(PHI);
1381 for (unsigned i = 0; i < NumInputs; ++i) {
1382 MachineBasicBlock *Pred = getPHIPred(PHI, i);
1383 if (!Region->contains(Pred)) {
1384 PHINonRegionIndices.push_back(i);
1389 void AMDGPUMachineCFGStructurizer::storePHILinearizationInfoDest(
1390 unsigned LDestReg, MachineInstr &PHI,
1391 SmallVector<unsigned, 2> *RegionIndices) {
1392 if (RegionIndices) {
1393 for (auto i : *RegionIndices) {
1394 PHIInfo.addSource(LDestReg, getPHISourceReg(PHI, i), getPHIPred(PHI, i));
1396 } else {
1397 unsigned NumInputs = getPHINumInputs(PHI);
1398 for (unsigned i = 0; i < NumInputs; ++i) {
1399 PHIInfo.addSource(LDestReg, getPHISourceReg(PHI, i), getPHIPred(PHI, i));
1404 unsigned AMDGPUMachineCFGStructurizer::storePHILinearizationInfo(
1405 MachineInstr &PHI, SmallVector<unsigned, 2> *RegionIndices) {
1406 unsigned DestReg = getPHIDestReg(PHI);
1407 Register LinearizeDestReg =
1408 MRI->createVirtualRegister(MRI->getRegClass(DestReg));
1409 PHIInfo.addDest(LinearizeDestReg, PHI.getDebugLoc());
1410 storePHILinearizationInfoDest(LinearizeDestReg, PHI, RegionIndices);
1411 return LinearizeDestReg;
1414 void AMDGPUMachineCFGStructurizer::extractKilledPHIs(MachineBasicBlock *MBB) {
1415 // We need to create a new chain for the killed phi, but there is no
1416 // need to do the renaming outside or inside the block.
1417 SmallPtrSet<MachineInstr *, 2> PHIs;
1418 for (MachineBasicBlock::instr_iterator I = MBB->instr_begin(),
1419 E = MBB->instr_end();
1420 I != E; ++I) {
1421 MachineInstr &Instr = *I;
1422 if (Instr.isPHI()) {
1423 unsigned PHIDestReg = getPHIDestReg(Instr);
1424 LLVM_DEBUG(dbgs() << "Extractking killed phi:\n");
1425 LLVM_DEBUG(Instr.dump());
1426 PHIs.insert(&Instr);
1427 PHIInfo.addDest(PHIDestReg, Instr.getDebugLoc());
1428 storePHILinearizationInfoDest(PHIDestReg, Instr);
1432 for (auto PI : PHIs) {
1433 PI->eraseFromParent();
1437 static bool isPHIRegionIndex(SmallVector<unsigned, 2> PHIRegionIndices,
1438 unsigned Index) {
1439 for (auto i : PHIRegionIndices) {
1440 if (i == Index)
1441 return true;
1443 return false;
1446 bool AMDGPUMachineCFGStructurizer::shrinkPHI(MachineInstr &PHI,
1447 SmallVector<unsigned, 2> &PHIIndices,
1448 unsigned *ReplaceReg) {
1449 return shrinkPHI(PHI, 0, nullptr, PHIIndices, ReplaceReg);
1452 bool AMDGPUMachineCFGStructurizer::shrinkPHI(MachineInstr &PHI,
1453 unsigned CombinedSourceReg,
1454 MachineBasicBlock *SourceMBB,
1455 SmallVector<unsigned, 2> &PHIIndices,
1456 unsigned *ReplaceReg) {
1457 LLVM_DEBUG(dbgs() << "Shrink PHI: ");
1458 LLVM_DEBUG(PHI.dump());
1459 LLVM_DEBUG(dbgs() << " to " << printReg(getPHIDestReg(PHI), TRI)
1460 << " = PHI(");
1462 bool Replaced = false;
1463 unsigned NumInputs = getPHINumInputs(PHI);
1464 int SingleExternalEntryIndex = -1;
1465 for (unsigned i = 0; i < NumInputs; ++i) {
1466 if (!isPHIRegionIndex(PHIIndices, i)) {
1467 if (SingleExternalEntryIndex == -1) {
1468 // Single entry
1469 SingleExternalEntryIndex = i;
1470 } else {
1471 // Multiple entries
1472 SingleExternalEntryIndex = -2;
1477 if (SingleExternalEntryIndex > -1) {
1478 *ReplaceReg = getPHISourceReg(PHI, SingleExternalEntryIndex);
1479 // We should not rewrite the code, we should only pick up the single value
1480 // that represents the shrunk PHI.
1481 Replaced = true;
1482 } else {
1483 MachineBasicBlock *MBB = PHI.getParent();
1484 MachineInstrBuilder MIB =
1485 BuildMI(*MBB, PHI, PHI.getDebugLoc(), TII->get(TargetOpcode::PHI),
1486 getPHIDestReg(PHI));
1487 if (SourceMBB) {
1488 MIB.addReg(CombinedSourceReg);
1489 MIB.addMBB(SourceMBB);
1490 LLVM_DEBUG(dbgs() << printReg(CombinedSourceReg, TRI) << ", "
1491 << printMBBReference(*SourceMBB));
1494 for (unsigned i = 0; i < NumInputs; ++i) {
1495 if (isPHIRegionIndex(PHIIndices, i)) {
1496 continue;
1498 unsigned SourceReg = getPHISourceReg(PHI, i);
1499 MachineBasicBlock *SourcePred = getPHIPred(PHI, i);
1500 MIB.addReg(SourceReg);
1501 MIB.addMBB(SourcePred);
1502 LLVM_DEBUG(dbgs() << printReg(SourceReg, TRI) << ", "
1503 << printMBBReference(*SourcePred));
1505 LLVM_DEBUG(dbgs() << ")\n");
1507 PHI.eraseFromParent();
1508 return Replaced;
1511 void AMDGPUMachineCFGStructurizer::replacePHI(
1512 MachineInstr &PHI, unsigned CombinedSourceReg, MachineBasicBlock *LastMerge,
1513 SmallVector<unsigned, 2> &PHIRegionIndices) {
1514 LLVM_DEBUG(dbgs() << "Replace PHI: ");
1515 LLVM_DEBUG(PHI.dump());
1516 LLVM_DEBUG(dbgs() << " with " << printReg(getPHIDestReg(PHI), TRI)
1517 << " = PHI(");
1519 bool HasExternalEdge = false;
1520 unsigned NumInputs = getPHINumInputs(PHI);
1521 for (unsigned i = 0; i < NumInputs; ++i) {
1522 if (!isPHIRegionIndex(PHIRegionIndices, i)) {
1523 HasExternalEdge = true;
1527 if (HasExternalEdge) {
1528 MachineBasicBlock *MBB = PHI.getParent();
1529 MachineInstrBuilder MIB =
1530 BuildMI(*MBB, PHI, PHI.getDebugLoc(), TII->get(TargetOpcode::PHI),
1531 getPHIDestReg(PHI));
1532 MIB.addReg(CombinedSourceReg);
1533 MIB.addMBB(LastMerge);
1534 LLVM_DEBUG(dbgs() << printReg(CombinedSourceReg, TRI) << ", "
1535 << printMBBReference(*LastMerge));
1536 for (unsigned i = 0; i < NumInputs; ++i) {
1537 if (isPHIRegionIndex(PHIRegionIndices, i)) {
1538 continue;
1540 unsigned SourceReg = getPHISourceReg(PHI, i);
1541 MachineBasicBlock *SourcePred = getPHIPred(PHI, i);
1542 MIB.addReg(SourceReg);
1543 MIB.addMBB(SourcePred);
1544 LLVM_DEBUG(dbgs() << printReg(SourceReg, TRI) << ", "
1545 << printMBBReference(*SourcePred));
1547 LLVM_DEBUG(dbgs() << ")\n");
1548 } else {
1549 replaceRegisterWith(getPHIDestReg(PHI), CombinedSourceReg);
1551 PHI.eraseFromParent();
1554 void AMDGPUMachineCFGStructurizer::replaceEntryPHI(
1555 MachineInstr &PHI, unsigned CombinedSourceReg, MachineBasicBlock *IfMBB,
1556 SmallVector<unsigned, 2> &PHIRegionIndices) {
1557 LLVM_DEBUG(dbgs() << "Replace entry PHI: ");
1558 LLVM_DEBUG(PHI.dump());
1559 LLVM_DEBUG(dbgs() << " with ");
1561 unsigned NumInputs = getPHINumInputs(PHI);
1562 unsigned NumNonRegionInputs = NumInputs;
1563 for (unsigned i = 0; i < NumInputs; ++i) {
1564 if (isPHIRegionIndex(PHIRegionIndices, i)) {
1565 NumNonRegionInputs--;
1569 if (NumNonRegionInputs == 0) {
1570 auto DestReg = getPHIDestReg(PHI);
1571 replaceRegisterWith(DestReg, CombinedSourceReg);
1572 LLVM_DEBUG(dbgs() << " register " << printReg(CombinedSourceReg, TRI)
1573 << "\n");
1574 PHI.eraseFromParent();
1575 } else {
1576 LLVM_DEBUG(dbgs() << printReg(getPHIDestReg(PHI), TRI) << " = PHI(");
1577 MachineBasicBlock *MBB = PHI.getParent();
1578 MachineInstrBuilder MIB =
1579 BuildMI(*MBB, PHI, PHI.getDebugLoc(), TII->get(TargetOpcode::PHI),
1580 getPHIDestReg(PHI));
1581 MIB.addReg(CombinedSourceReg);
1582 MIB.addMBB(IfMBB);
1583 LLVM_DEBUG(dbgs() << printReg(CombinedSourceReg, TRI) << ", "
1584 << printMBBReference(*IfMBB));
1585 unsigned NumInputs = getPHINumInputs(PHI);
1586 for (unsigned i = 0; i < NumInputs; ++i) {
1587 if (isPHIRegionIndex(PHIRegionIndices, i)) {
1588 continue;
1590 unsigned SourceReg = getPHISourceReg(PHI, i);
1591 MachineBasicBlock *SourcePred = getPHIPred(PHI, i);
1592 MIB.addReg(SourceReg);
1593 MIB.addMBB(SourcePred);
1594 LLVM_DEBUG(dbgs() << printReg(SourceReg, TRI) << ", "
1595 << printMBBReference(*SourcePred));
1597 LLVM_DEBUG(dbgs() << ")\n");
1598 PHI.eraseFromParent();
1602 void AMDGPUMachineCFGStructurizer::replaceLiveOutRegs(
1603 MachineInstr &PHI, SmallVector<unsigned, 2> &PHIRegionIndices,
1604 unsigned CombinedSourceReg, LinearizedRegion *LRegion) {
1605 bool WasLiveOut = false;
1606 for (auto PII : PHIRegionIndices) {
1607 unsigned Reg = getPHISourceReg(PHI, PII);
1608 if (LRegion->isLiveOut(Reg)) {
1609 bool IsDead = true;
1611 // Check if register is live out of the basic block
1612 MachineBasicBlock *DefMBB = getDefInstr(Reg)->getParent();
1613 for (auto UI = MRI->use_begin(Reg), E = MRI->use_end(); UI != E; ++UI) {
1614 if ((*UI).getParent()->getParent() != DefMBB) {
1615 IsDead = false;
1619 LLVM_DEBUG(dbgs() << "Register " << printReg(Reg, TRI) << " is "
1620 << (IsDead ? "dead" : "alive")
1621 << " after PHI replace\n");
1622 if (IsDead) {
1623 LRegion->removeLiveOut(Reg);
1625 WasLiveOut = true;
1629 if (WasLiveOut)
1630 LRegion->addLiveOut(CombinedSourceReg);
1633 void AMDGPUMachineCFGStructurizer::rewriteRegionExitPHI(RegionMRT *Region,
1634 MachineBasicBlock *LastMerge,
1635 MachineInstr &PHI,
1636 LinearizedRegion *LRegion) {
1637 SmallVector<unsigned, 2> PHIRegionIndices;
1638 getPHIRegionIndices(Region, PHI, PHIRegionIndices);
1639 unsigned LinearizedSourceReg =
1640 storePHILinearizationInfo(PHI, &PHIRegionIndices);
1642 replacePHI(PHI, LinearizedSourceReg, LastMerge, PHIRegionIndices);
1643 replaceLiveOutRegs(PHI, PHIRegionIndices, LinearizedSourceReg, LRegion);
1646 void AMDGPUMachineCFGStructurizer::rewriteRegionEntryPHI(LinearizedRegion *Region,
1647 MachineBasicBlock *IfMBB,
1648 MachineInstr &PHI) {
1649 SmallVector<unsigned, 2> PHINonRegionIndices;
1650 getPHINonRegionIndices(Region, PHI, PHINonRegionIndices);
1651 unsigned LinearizedSourceReg =
1652 storePHILinearizationInfo(PHI, &PHINonRegionIndices);
1653 replaceEntryPHI(PHI, LinearizedSourceReg, IfMBB, PHINonRegionIndices);
1656 static void collectPHIs(MachineBasicBlock *MBB,
1657 SmallVector<MachineInstr *, 2> &PHIs) {
1658 for (auto &BBI : *MBB) {
1659 if (BBI.isPHI()) {
1660 PHIs.push_back(&BBI);
1665 void AMDGPUMachineCFGStructurizer::rewriteRegionExitPHIs(RegionMRT *Region,
1666 MachineBasicBlock *LastMerge,
1667 LinearizedRegion *LRegion) {
1668 SmallVector<MachineInstr *, 2> PHIs;
1669 auto Exit = Region->getSucc();
1670 if (Exit == nullptr)
1671 return;
1673 collectPHIs(Exit, PHIs);
1675 for (auto PHII : PHIs) {
1676 rewriteRegionExitPHI(Region, LastMerge, *PHII, LRegion);
1680 void AMDGPUMachineCFGStructurizer::rewriteRegionEntryPHIs(LinearizedRegion *Region,
1681 MachineBasicBlock *IfMBB) {
1682 SmallVector<MachineInstr *, 2> PHIs;
1683 auto Entry = Region->getEntry();
1685 collectPHIs(Entry, PHIs);
1687 for (auto PHII : PHIs) {
1688 rewriteRegionEntryPHI(Region, IfMBB, *PHII);
1692 void AMDGPUMachineCFGStructurizer::insertUnconditionalBranch(MachineBasicBlock *MBB,
1693 MachineBasicBlock *Dest,
1694 const DebugLoc &DL) {
1695 LLVM_DEBUG(dbgs() << "Inserting unconditional branch: " << MBB->getNumber()
1696 << " -> " << Dest->getNumber() << "\n");
1697 MachineBasicBlock::instr_iterator Terminator = MBB->getFirstInstrTerminator();
1698 bool HasTerminator = Terminator != MBB->instr_end();
1699 if (HasTerminator) {
1700 TII->ReplaceTailWithBranchTo(Terminator, Dest);
1702 if (++MachineFunction::iterator(MBB) != MachineFunction::iterator(Dest)) {
1703 TII->insertUnconditionalBranch(*MBB, Dest, DL);
1707 static MachineBasicBlock *getSingleExitNode(MachineFunction &MF) {
1708 MachineBasicBlock *result = nullptr;
1709 for (auto &MFI : MF) {
1710 if (MFI.succ_size() == 0) {
1711 if (result == nullptr) {
1712 result = &MFI;
1713 } else {
1714 return nullptr;
1719 return result;
1722 static bool hasOneExitNode(MachineFunction &MF) {
1723 return getSingleExitNode(MF) != nullptr;
1726 MachineBasicBlock *
1727 AMDGPUMachineCFGStructurizer::createLinearizedExitBlock(RegionMRT *Region) {
1728 auto Exit = Region->getSucc();
1730 // If the exit is the end of the function, we just use the existing
1731 MachineFunction *MF = Region->getEntry()->getParent();
1732 if (Exit == nullptr && hasOneExitNode(*MF)) {
1733 return &(*(--(Region->getEntry()->getParent()->end())));
1736 MachineBasicBlock *LastMerge = MF->CreateMachineBasicBlock();
1737 if (Exit == nullptr) {
1738 MachineFunction::iterator ExitIter = MF->end();
1739 MF->insert(ExitIter, LastMerge);
1740 } else {
1741 MachineFunction::iterator ExitIter = Exit->getIterator();
1742 MF->insert(ExitIter, LastMerge);
1743 LastMerge->addSuccessor(Exit);
1744 insertUnconditionalBranch(LastMerge, Exit);
1745 LLVM_DEBUG(dbgs() << "Created exit block: " << LastMerge->getNumber()
1746 << "\n");
1748 return LastMerge;
1751 void AMDGPUMachineCFGStructurizer::insertMergePHI(MachineBasicBlock *IfBB,
1752 MachineBasicBlock *CodeBB,
1753 MachineBasicBlock *MergeBB,
1754 unsigned DestRegister,
1755 unsigned IfSourceRegister,
1756 unsigned CodeSourceRegister,
1757 bool IsUndefIfSource) {
1758 // If this is the function exit block, we don't need a phi.
1759 if (MergeBB->succ_begin() == MergeBB->succ_end()) {
1760 return;
1762 LLVM_DEBUG(dbgs() << "Merge PHI (" << printMBBReference(*MergeBB)
1763 << "): " << printReg(DestRegister, TRI) << " = PHI("
1764 << printReg(IfSourceRegister, TRI) << ", "
1765 << printMBBReference(*IfBB)
1766 << printReg(CodeSourceRegister, TRI) << ", "
1767 << printMBBReference(*CodeBB) << ")\n");
1768 const DebugLoc &DL = MergeBB->findDebugLoc(MergeBB->begin());
1769 MachineInstrBuilder MIB = BuildMI(*MergeBB, MergeBB->instr_begin(), DL,
1770 TII->get(TargetOpcode::PHI), DestRegister);
1771 if (IsUndefIfSource && false) {
1772 MIB.addReg(IfSourceRegister, RegState::Undef);
1773 } else {
1774 MIB.addReg(IfSourceRegister);
1776 MIB.addMBB(IfBB);
1777 MIB.addReg(CodeSourceRegister);
1778 MIB.addMBB(CodeBB);
1781 static void removeExternalCFGSuccessors(MachineBasicBlock *MBB) {
1782 for (MachineBasicBlock::succ_iterator PI = MBB->succ_begin(),
1783 E = MBB->succ_end();
1784 PI != E; ++PI) {
1785 if ((*PI) != MBB) {
1786 (MBB)->removeSuccessor(*PI);
1791 static void removeExternalCFGEdges(MachineBasicBlock *StartMBB,
1792 MachineBasicBlock *EndMBB) {
1794 // We have to check against the StartMBB successor becasuse a
1795 // structurized region with a loop will have the entry block split,
1796 // and the backedge will go to the entry successor.
1797 DenseSet<std::pair<MachineBasicBlock *, MachineBasicBlock *>> Succs;
1798 unsigned SuccSize = StartMBB->succ_size();
1799 if (SuccSize > 0) {
1800 MachineBasicBlock *StartMBBSucc = *(StartMBB->succ_begin());
1801 for (MachineBasicBlock::succ_iterator PI = EndMBB->succ_begin(),
1802 E = EndMBB->succ_end();
1803 PI != E; ++PI) {
1804 // Either we have a back-edge to the entry block, or a back-edge to the
1805 // successor of the entry block since the block may be split.
1806 if ((*PI) != StartMBB &&
1807 !((*PI) == StartMBBSucc && StartMBB != EndMBB && SuccSize == 1)) {
1808 Succs.insert(
1809 std::pair<MachineBasicBlock *, MachineBasicBlock *>(EndMBB, *PI));
1814 for (MachineBasicBlock::pred_iterator PI = StartMBB->pred_begin(),
1815 E = StartMBB->pred_end();
1816 PI != E; ++PI) {
1817 if ((*PI) != EndMBB) {
1818 Succs.insert(
1819 std::pair<MachineBasicBlock *, MachineBasicBlock *>(*PI, StartMBB));
1823 for (auto SI : Succs) {
1824 std::pair<MachineBasicBlock *, MachineBasicBlock *> Edge = SI;
1825 LLVM_DEBUG(dbgs() << "Removing edge: " << printMBBReference(*Edge.first)
1826 << " -> " << printMBBReference(*Edge.second) << "\n");
1827 Edge.first->removeSuccessor(Edge.second);
1831 MachineBasicBlock *AMDGPUMachineCFGStructurizer::createIfBlock(
1832 MachineBasicBlock *MergeBB, MachineBasicBlock *CodeBBStart,
1833 MachineBasicBlock *CodeBBEnd, MachineBasicBlock *SelectBB, unsigned IfReg,
1834 bool InheritPreds) {
1835 MachineFunction *MF = MergeBB->getParent();
1836 MachineBasicBlock *IfBB = MF->CreateMachineBasicBlock();
1838 if (InheritPreds) {
1839 for (MachineBasicBlock::pred_iterator PI = CodeBBStart->pred_begin(),
1840 E = CodeBBStart->pred_end();
1841 PI != E; ++PI) {
1842 if ((*PI) != CodeBBEnd) {
1843 MachineBasicBlock *Pred = (*PI);
1844 Pred->addSuccessor(IfBB);
1849 removeExternalCFGEdges(CodeBBStart, CodeBBEnd);
1851 auto CodeBBStartI = CodeBBStart->getIterator();
1852 auto CodeBBEndI = CodeBBEnd->getIterator();
1853 auto MergeIter = MergeBB->getIterator();
1854 MF->insert(MergeIter, IfBB);
1855 MF->splice(MergeIter, CodeBBStartI, ++CodeBBEndI);
1856 IfBB->addSuccessor(MergeBB);
1857 IfBB->addSuccessor(CodeBBStart);
1859 LLVM_DEBUG(dbgs() << "Created If block: " << IfBB->getNumber() << "\n");
1860 // Ensure that the MergeBB is a successor of the CodeEndBB.
1861 if (!CodeBBEnd->isSuccessor(MergeBB))
1862 CodeBBEnd->addSuccessor(MergeBB);
1864 LLVM_DEBUG(dbgs() << "Moved " << printMBBReference(*CodeBBStart)
1865 << " through " << printMBBReference(*CodeBBEnd) << "\n");
1867 // If we have a single predecessor we can find a reasonable debug location
1868 MachineBasicBlock *SinglePred =
1869 CodeBBStart->pred_size() == 1 ? *(CodeBBStart->pred_begin()) : nullptr;
1870 const DebugLoc &DL = SinglePred
1871 ? SinglePred->findDebugLoc(SinglePred->getFirstTerminator())
1872 : DebugLoc();
1874 unsigned Reg =
1875 TII->insertEQ(IfBB, IfBB->begin(), DL, IfReg,
1876 SelectBB->getNumber() /* CodeBBStart->getNumber() */);
1877 if (&(*(IfBB->getParent()->begin())) == IfBB) {
1878 TII->materializeImmediate(*IfBB, IfBB->begin(), DL, IfReg,
1879 CodeBBStart->getNumber());
1881 MachineOperand RegOp = MachineOperand::CreateReg(Reg, false, false, true);
1882 ArrayRef<MachineOperand> Cond(RegOp);
1883 TII->insertBranch(*IfBB, MergeBB, CodeBBStart, Cond, DL);
1885 return IfBB;
1888 void AMDGPUMachineCFGStructurizer::ensureCondIsNotKilled(
1889 SmallVector<MachineOperand, 1> Cond) {
1890 if (Cond.size() != 1)
1891 return;
1892 if (!Cond[0].isReg())
1893 return;
1895 Register CondReg = Cond[0].getReg();
1896 for (auto UI = MRI->use_begin(CondReg), E = MRI->use_end(); UI != E; ++UI) {
1897 (*UI).setIsKill(false);
1901 void AMDGPUMachineCFGStructurizer::rewriteCodeBBTerminator(MachineBasicBlock *CodeBB,
1902 MachineBasicBlock *MergeBB,
1903 unsigned BBSelectReg) {
1904 MachineBasicBlock *TrueBB = nullptr;
1905 MachineBasicBlock *FalseBB = nullptr;
1906 SmallVector<MachineOperand, 1> Cond;
1907 MachineBasicBlock *FallthroughBB = FallthroughMap[CodeBB];
1908 TII->analyzeBranch(*CodeBB, TrueBB, FalseBB, Cond);
1910 const DebugLoc &DL = CodeBB->findDebugLoc(CodeBB->getFirstTerminator());
1912 if (FalseBB == nullptr && TrueBB == nullptr && FallthroughBB == nullptr) {
1913 // This is an exit block, hence no successors. We will assign the
1914 // bb select register to the entry block.
1915 TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
1916 BBSelectReg,
1917 CodeBB->getParent()->begin()->getNumber());
1918 insertUnconditionalBranch(CodeBB, MergeBB, DL);
1919 return;
1922 if (FalseBB == nullptr && TrueBB == nullptr) {
1923 TrueBB = FallthroughBB;
1924 } else if (TrueBB != nullptr) {
1925 FalseBB =
1926 (FallthroughBB && (FallthroughBB != TrueBB)) ? FallthroughBB : FalseBB;
1929 if ((TrueBB != nullptr && FalseBB == nullptr) || (TrueBB == FalseBB)) {
1930 TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
1931 BBSelectReg, TrueBB->getNumber());
1932 } else {
1933 const TargetRegisterClass *RegClass = MRI->getRegClass(BBSelectReg);
1934 Register TrueBBReg = MRI->createVirtualRegister(RegClass);
1935 Register FalseBBReg = MRI->createVirtualRegister(RegClass);
1936 TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
1937 TrueBBReg, TrueBB->getNumber());
1938 TII->materializeImmediate(*CodeBB, CodeBB->getFirstTerminator(), DL,
1939 FalseBBReg, FalseBB->getNumber());
1940 ensureCondIsNotKilled(Cond);
1941 TII->insertVectorSelect(*CodeBB, CodeBB->getFirstTerminator(), DL,
1942 BBSelectReg, Cond, TrueBBReg, FalseBBReg);
1945 insertUnconditionalBranch(CodeBB, MergeBB, DL);
1948 MachineInstr *AMDGPUMachineCFGStructurizer::getDefInstr(unsigned Reg) {
1949 if (MRI->def_begin(Reg) == MRI->def_end()) {
1950 LLVM_DEBUG(dbgs() << "Register "
1951 << printReg(Reg, MRI->getTargetRegisterInfo())
1952 << " has NO defs\n");
1953 } else if (!MRI->hasOneDef(Reg)) {
1954 LLVM_DEBUG(dbgs() << "Register "
1955 << printReg(Reg, MRI->getTargetRegisterInfo())
1956 << " has multiple defs\n");
1957 LLVM_DEBUG(dbgs() << "DEFS BEGIN:\n");
1958 for (auto DI = MRI->def_begin(Reg), DE = MRI->def_end(); DI != DE; ++DI) {
1959 LLVM_DEBUG(DI->getParent()->dump());
1961 LLVM_DEBUG(dbgs() << "DEFS END\n");
1964 assert(MRI->hasOneDef(Reg) && "Register has multiple definitions");
1965 return (*(MRI->def_begin(Reg))).getParent();
1968 void AMDGPUMachineCFGStructurizer::insertChainedPHI(MachineBasicBlock *IfBB,
1969 MachineBasicBlock *CodeBB,
1970 MachineBasicBlock *MergeBB,
1971 LinearizedRegion *InnerRegion,
1972 unsigned DestReg,
1973 unsigned SourceReg) {
1974 // In this function we know we are part of a chain already, so we need
1975 // to add the registers to the existing chain, and rename the register
1976 // inside the region.
1977 bool IsSingleBB = InnerRegion->getEntry() == InnerRegion->getExit();
1978 MachineInstr *DefInstr = getDefInstr(SourceReg);
1979 if (DefInstr->isPHI() && DefInstr->getParent() == CodeBB && IsSingleBB) {
1980 // Handle the case where the def is a PHI-def inside a basic
1981 // block, then we only need to do renaming. Special care needs to
1982 // be taken if the PHI-def is part of an existing chain, or if a
1983 // new one needs to be created.
1984 InnerRegion->replaceRegisterInsideRegion(SourceReg, DestReg, true, MRI);
1986 // We collect all PHI Information, and if we are at the region entry,
1987 // all PHIs will be removed, and then re-introduced if needed.
1988 storePHILinearizationInfoDest(DestReg, *DefInstr);
1989 // We have picked up all the information we need now and can remove
1990 // the PHI
1991 PHIInfo.removeSource(DestReg, SourceReg, CodeBB);
1992 DefInstr->eraseFromParent();
1993 } else {
1994 // If this is not a phi-def, or it is a phi-def but from a linearized region
1995 if (IsSingleBB && DefInstr->getParent() == InnerRegion->getEntry()) {
1996 // If this is a single BB and the definition is in this block we
1997 // need to replace any uses outside the region.
1998 InnerRegion->replaceRegisterOutsideRegion(SourceReg, DestReg, false, MRI);
2000 const TargetRegisterClass *RegClass = MRI->getRegClass(DestReg);
2001 Register NextDestReg = MRI->createVirtualRegister(RegClass);
2002 bool IsLastDef = PHIInfo.getNumSources(DestReg) == 1;
2003 LLVM_DEBUG(dbgs() << "Insert Chained PHI\n");
2004 insertMergePHI(IfBB, InnerRegion->getExit(), MergeBB, DestReg, NextDestReg,
2005 SourceReg, IsLastDef);
2007 PHIInfo.removeSource(DestReg, SourceReg, CodeBB);
2008 if (IsLastDef) {
2009 const DebugLoc &DL = IfBB->findDebugLoc(IfBB->getFirstTerminator());
2010 TII->materializeImmediate(*IfBB, IfBB->getFirstTerminator(), DL,
2011 NextDestReg, 0);
2012 PHIInfo.deleteDef(DestReg);
2013 } else {
2014 PHIInfo.replaceDef(DestReg, NextDestReg);
2019 bool AMDGPUMachineCFGStructurizer::containsDef(MachineBasicBlock *MBB,
2020 LinearizedRegion *InnerRegion,
2021 unsigned Register) {
2022 return getDefInstr(Register)->getParent() == MBB ||
2023 InnerRegion->contains(getDefInstr(Register)->getParent());
2026 void AMDGPUMachineCFGStructurizer::rewriteLiveOutRegs(MachineBasicBlock *IfBB,
2027 MachineBasicBlock *CodeBB,
2028 MachineBasicBlock *MergeBB,
2029 LinearizedRegion *InnerRegion,
2030 LinearizedRegion *LRegion) {
2031 DenseSet<unsigned> *LiveOuts = InnerRegion->getLiveOuts();
2032 SmallVector<unsigned, 4> OldLiveOuts;
2033 bool IsSingleBB = InnerRegion->getEntry() == InnerRegion->getExit();
2034 for (auto OLI : *LiveOuts) {
2035 OldLiveOuts.push_back(OLI);
2038 for (auto LI : OldLiveOuts) {
2039 LLVM_DEBUG(dbgs() << "LiveOut: " << printReg(LI, TRI));
2040 if (!containsDef(CodeBB, InnerRegion, LI) ||
2041 (!IsSingleBB && (getDefInstr(LI)->getParent() == LRegion->getExit()))) {
2042 // If the register simly lives through the CodeBB, we don't have
2043 // to rewrite anything since the register is not defined in this
2044 // part of the code.
2045 LLVM_DEBUG(dbgs() << "- through");
2046 continue;
2048 LLVM_DEBUG(dbgs() << "\n");
2049 unsigned Reg = LI;
2050 if (/*!PHIInfo.isSource(Reg) &&*/ Reg != InnerRegion->getBBSelectRegOut()) {
2051 // If the register is live out, we do want to create a phi,
2052 // unless it is from the Exit block, becasuse in that case there
2053 // is already a PHI, and no need to create a new one.
2055 // If the register is just a live out def and not part of a phi
2056 // chain, we need to create a PHI node to handle the if region,
2057 // and replace all uses outside of the region with the new dest
2058 // register, unless it is the outgoing BB select register. We have
2059 // already creaed phi nodes for these.
2060 const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
2061 Register PHIDestReg = MRI->createVirtualRegister(RegClass);
2062 Register IfSourceReg = MRI->createVirtualRegister(RegClass);
2063 // Create initializer, this value is never used, but is needed
2064 // to satisfy SSA.
2065 LLVM_DEBUG(dbgs() << "Initializer for reg: " << printReg(Reg) << "\n");
2066 TII->materializeImmediate(*IfBB, IfBB->getFirstTerminator(), DebugLoc(),
2067 IfSourceReg, 0);
2069 InnerRegion->replaceRegisterOutsideRegion(Reg, PHIDestReg, true, MRI);
2070 LLVM_DEBUG(dbgs() << "Insert Non-Chained Live out PHI\n");
2071 insertMergePHI(IfBB, InnerRegion->getExit(), MergeBB, PHIDestReg,
2072 IfSourceReg, Reg, true);
2076 // Handle the chained definitions in PHIInfo, checking if this basic block
2077 // is a source block for a definition.
2078 SmallVector<unsigned, 4> Sources;
2079 if (PHIInfo.findSourcesFromMBB(CodeBB, Sources)) {
2080 LLVM_DEBUG(dbgs() << "Inserting PHI Live Out from "
2081 << printMBBReference(*CodeBB) << "\n");
2082 for (auto SI : Sources) {
2083 unsigned DestReg;
2084 PHIInfo.findDest(SI, CodeBB, DestReg);
2085 insertChainedPHI(IfBB, CodeBB, MergeBB, InnerRegion, DestReg, SI);
2087 LLVM_DEBUG(dbgs() << "Insertion done.\n");
2090 LLVM_DEBUG(PHIInfo.dump(MRI));
2093 void AMDGPUMachineCFGStructurizer::prunePHIInfo(MachineBasicBlock *MBB) {
2094 LLVM_DEBUG(dbgs() << "Before PHI Prune\n");
2095 LLVM_DEBUG(PHIInfo.dump(MRI));
2096 SmallVector<std::tuple<unsigned, unsigned, MachineBasicBlock *>, 4>
2097 ElimiatedSources;
2098 for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
2099 ++DRI) {
2101 unsigned DestReg = *DRI;
2102 auto SE = PHIInfo.sources_end(DestReg);
2104 bool MBBContainsPHISource = false;
2105 // Check if there is a PHI source in this MBB
2106 for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
2107 unsigned SourceReg = (*SRI).first;
2108 MachineOperand *Def = &(*(MRI->def_begin(SourceReg)));
2109 if (Def->getParent()->getParent() == MBB) {
2110 MBBContainsPHISource = true;
2114 // If so, all other sources are useless since we know this block
2115 // is always executed when the region is executed.
2116 if (MBBContainsPHISource) {
2117 for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
2118 PHILinearize::PHISourceT Source = *SRI;
2119 unsigned SourceReg = Source.first;
2120 MachineBasicBlock *SourceMBB = Source.second;
2121 MachineOperand *Def = &(*(MRI->def_begin(SourceReg)));
2122 if (Def->getParent()->getParent() != MBB) {
2123 ElimiatedSources.push_back(
2124 std::make_tuple(DestReg, SourceReg, SourceMBB));
2130 // Remove the PHI sources that are in the given MBB
2131 for (auto &SourceInfo : ElimiatedSources) {
2132 PHIInfo.removeSource(std::get<0>(SourceInfo), std::get<1>(SourceInfo),
2133 std::get<2>(SourceInfo));
2135 LLVM_DEBUG(dbgs() << "After PHI Prune\n");
2136 LLVM_DEBUG(PHIInfo.dump(MRI));
2139 void AMDGPUMachineCFGStructurizer::createEntryPHI(LinearizedRegion *CurrentRegion,
2140 unsigned DestReg) {
2141 MachineBasicBlock *Entry = CurrentRegion->getEntry();
2142 MachineBasicBlock *Exit = CurrentRegion->getExit();
2144 LLVM_DEBUG(dbgs() << "RegionExit: " << Exit->getNumber() << " Pred: "
2145 << (*(Entry->pred_begin()))->getNumber() << "\n");
2147 int NumSources = 0;
2148 auto SE = PHIInfo.sources_end(DestReg);
2150 for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
2151 NumSources++;
2154 if (NumSources == 1) {
2155 auto SRI = PHIInfo.sources_begin(DestReg);
2156 unsigned SourceReg = (*SRI).first;
2157 replaceRegisterWith(DestReg, SourceReg);
2158 } else {
2159 const DebugLoc &DL = Entry->findDebugLoc(Entry->begin());
2160 MachineInstrBuilder MIB = BuildMI(*Entry, Entry->instr_begin(), DL,
2161 TII->get(TargetOpcode::PHI), DestReg);
2162 LLVM_DEBUG(dbgs() << "Entry PHI " << printReg(DestReg, TRI) << " = PHI(");
2164 unsigned CurrentBackedgeReg = 0;
2166 for (auto SRI = PHIInfo.sources_begin(DestReg); SRI != SE; ++SRI) {
2167 unsigned SourceReg = (*SRI).first;
2169 if (CurrentRegion->contains((*SRI).second)) {
2170 if (CurrentBackedgeReg == 0) {
2171 CurrentBackedgeReg = SourceReg;
2172 } else {
2173 MachineInstr *PHIDefInstr = getDefInstr(SourceReg);
2174 MachineBasicBlock *PHIDefMBB = PHIDefInstr->getParent();
2175 const TargetRegisterClass *RegClass =
2176 MRI->getRegClass(CurrentBackedgeReg);
2177 Register NewBackedgeReg = MRI->createVirtualRegister(RegClass);
2178 MachineInstrBuilder BackedgePHI =
2179 BuildMI(*PHIDefMBB, PHIDefMBB->instr_begin(), DL,
2180 TII->get(TargetOpcode::PHI), NewBackedgeReg);
2181 BackedgePHI.addReg(CurrentBackedgeReg);
2182 BackedgePHI.addMBB(getPHIPred(*PHIDefInstr, 0));
2183 BackedgePHI.addReg(getPHISourceReg(*PHIDefInstr, 1));
2184 BackedgePHI.addMBB((*SRI).second);
2185 CurrentBackedgeReg = NewBackedgeReg;
2186 LLVM_DEBUG(dbgs()
2187 << "Inserting backedge PHI: "
2188 << printReg(NewBackedgeReg, TRI) << " = PHI("
2189 << printReg(CurrentBackedgeReg, TRI) << ", "
2190 << printMBBReference(*getPHIPred(*PHIDefInstr, 0)) << ", "
2191 << printReg(getPHISourceReg(*PHIDefInstr, 1), TRI) << ", "
2192 << printMBBReference(*(*SRI).second));
2194 } else {
2195 MIB.addReg(SourceReg);
2196 MIB.addMBB((*SRI).second);
2197 LLVM_DEBUG(dbgs() << printReg(SourceReg, TRI) << ", "
2198 << printMBBReference(*(*SRI).second) << ", ");
2202 // Add the final backedge register source to the entry phi
2203 if (CurrentBackedgeReg != 0) {
2204 MIB.addReg(CurrentBackedgeReg);
2205 MIB.addMBB(Exit);
2206 LLVM_DEBUG(dbgs() << printReg(CurrentBackedgeReg, TRI) << ", "
2207 << printMBBReference(*Exit) << ")\n");
2208 } else {
2209 LLVM_DEBUG(dbgs() << ")\n");
2214 void AMDGPUMachineCFGStructurizer::createEntryPHIs(LinearizedRegion *CurrentRegion) {
2215 LLVM_DEBUG(PHIInfo.dump(MRI));
2217 for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
2218 ++DRI) {
2220 unsigned DestReg = *DRI;
2221 createEntryPHI(CurrentRegion, DestReg);
2223 PHIInfo.clear();
2226 void AMDGPUMachineCFGStructurizer::replaceRegisterWith(unsigned Register,
2227 unsigned NewRegister) {
2228 assert(Register != NewRegister && "Cannot replace a reg with itself");
2230 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Register),
2231 E = MRI->reg_end();
2232 I != E;) {
2233 MachineOperand &O = *I;
2234 ++I;
2235 if (Register::isPhysicalRegister(NewRegister)) {
2236 LLVM_DEBUG(dbgs() << "Trying to substitute physical register: "
2237 << printReg(NewRegister, MRI->getTargetRegisterInfo())
2238 << "\n");
2239 llvm_unreachable("Cannot substitute physical registers");
2240 // We don't handle physical registers, but if we need to
2241 // in the future This is how we do it:
2242 // O.substPhysReg(NewRegister, *TRI);
2243 } else {
2244 LLVM_DEBUG(dbgs() << "Replacing register: "
2245 << printReg(Register, MRI->getTargetRegisterInfo())
2246 << " with "
2247 << printReg(NewRegister, MRI->getTargetRegisterInfo())
2248 << "\n");
2249 O.setReg(NewRegister);
2252 PHIInfo.deleteDef(Register);
2254 getRegionMRT()->replaceLiveOutReg(Register, NewRegister);
2256 LLVM_DEBUG(PHIInfo.dump(MRI));
2259 void AMDGPUMachineCFGStructurizer::resolvePHIInfos(MachineBasicBlock *FunctionEntry) {
2260 LLVM_DEBUG(dbgs() << "Resolve PHI Infos\n");
2261 LLVM_DEBUG(PHIInfo.dump(MRI));
2262 for (auto DRI = PHIInfo.dests_begin(), DE = PHIInfo.dests_end(); DRI != DE;
2263 ++DRI) {
2264 unsigned DestReg = *DRI;
2265 LLVM_DEBUG(dbgs() << "DestReg: " << printReg(DestReg, TRI) << "\n");
2266 auto SRI = PHIInfo.sources_begin(DestReg);
2267 unsigned SourceReg = (*SRI).first;
2268 LLVM_DEBUG(dbgs() << "DestReg: " << printReg(DestReg, TRI)
2269 << " SourceReg: " << printReg(SourceReg, TRI) << "\n");
2271 assert(PHIInfo.sources_end(DestReg) == ++SRI &&
2272 "More than one phi source in entry node");
2273 replaceRegisterWith(DestReg, SourceReg);
2277 static bool isFunctionEntryBlock(MachineBasicBlock *MBB) {
2278 return ((&(*(MBB->getParent()->begin()))) == MBB);
2281 MachineBasicBlock *AMDGPUMachineCFGStructurizer::createIfRegion(
2282 MachineBasicBlock *MergeBB, MachineBasicBlock *CodeBB,
2283 LinearizedRegion *CurrentRegion, unsigned BBSelectRegIn,
2284 unsigned BBSelectRegOut) {
2285 if (isFunctionEntryBlock(CodeBB) && !CurrentRegion->getHasLoop()) {
2286 // Handle non-loop function entry block.
2287 // We need to allow loops to the entry block and then
2288 rewriteCodeBBTerminator(CodeBB, MergeBB, BBSelectRegOut);
2289 resolvePHIInfos(CodeBB);
2290 removeExternalCFGSuccessors(CodeBB);
2291 CodeBB->addSuccessor(MergeBB);
2292 CurrentRegion->addMBB(CodeBB);
2293 return nullptr;
2295 if (CurrentRegion->getEntry() == CodeBB && !CurrentRegion->getHasLoop()) {
2296 // Handle non-loop region entry block.
2297 MachineFunction *MF = MergeBB->getParent();
2298 auto MergeIter = MergeBB->getIterator();
2299 auto CodeBBStartIter = CodeBB->getIterator();
2300 auto CodeBBEndIter = ++(CodeBB->getIterator());
2301 if (CodeBBEndIter != MergeIter) {
2302 MF->splice(MergeIter, CodeBBStartIter, CodeBBEndIter);
2304 rewriteCodeBBTerminator(CodeBB, MergeBB, BBSelectRegOut);
2305 prunePHIInfo(CodeBB);
2306 createEntryPHIs(CurrentRegion);
2307 removeExternalCFGSuccessors(CodeBB);
2308 CodeBB->addSuccessor(MergeBB);
2309 CurrentRegion->addMBB(CodeBB);
2310 return nullptr;
2311 } else {
2312 // Handle internal block.
2313 const TargetRegisterClass *RegClass = MRI->getRegClass(BBSelectRegIn);
2314 Register CodeBBSelectReg = MRI->createVirtualRegister(RegClass);
2315 rewriteCodeBBTerminator(CodeBB, MergeBB, CodeBBSelectReg);
2316 bool IsRegionEntryBB = CurrentRegion->getEntry() == CodeBB;
2317 MachineBasicBlock *IfBB = createIfBlock(MergeBB, CodeBB, CodeBB, CodeBB,
2318 BBSelectRegIn, IsRegionEntryBB);
2319 CurrentRegion->addMBB(IfBB);
2320 // If this is the entry block we need to make the If block the new
2321 // linearized region entry.
2322 if (IsRegionEntryBB) {
2323 CurrentRegion->setEntry(IfBB);
2325 if (CurrentRegion->getHasLoop()) {
2326 MachineBasicBlock *RegionExit = CurrentRegion->getExit();
2327 MachineBasicBlock *ETrueBB = nullptr;
2328 MachineBasicBlock *EFalseBB = nullptr;
2329 SmallVector<MachineOperand, 1> ECond;
2331 const DebugLoc &DL = DebugLoc();
2332 TII->analyzeBranch(*RegionExit, ETrueBB, EFalseBB, ECond);
2333 TII->removeBranch(*RegionExit);
2335 // We need to create a backedge if there is a loop
2336 unsigned Reg = TII->insertNE(
2337 RegionExit, RegionExit->instr_end(), DL,
2338 CurrentRegion->getRegionMRT()->getInnerOutputRegister(),
2339 CurrentRegion->getRegionMRT()->getEntry()->getNumber());
2340 MachineOperand RegOp =
2341 MachineOperand::CreateReg(Reg, false, false, true);
2342 ArrayRef<MachineOperand> Cond(RegOp);
2343 LLVM_DEBUG(dbgs() << "RegionExitReg: ");
2344 LLVM_DEBUG(Cond[0].print(dbgs(), TRI));
2345 LLVM_DEBUG(dbgs() << "\n");
2346 TII->insertBranch(*RegionExit, CurrentRegion->getEntry(), RegionExit,
2347 Cond, DebugLoc());
2348 RegionExit->addSuccessor(CurrentRegion->getEntry());
2351 CurrentRegion->addMBB(CodeBB);
2352 LinearizedRegion InnerRegion(CodeBB, MRI, TRI, PHIInfo);
2354 InnerRegion.setParent(CurrentRegion);
2355 LLVM_DEBUG(dbgs() << "Insert BB Select PHI (BB)\n");
2356 insertMergePHI(IfBB, CodeBB, MergeBB, BBSelectRegOut, BBSelectRegIn,
2357 CodeBBSelectReg);
2358 InnerRegion.addMBB(MergeBB);
2360 LLVM_DEBUG(InnerRegion.print(dbgs(), TRI));
2361 rewriteLiveOutRegs(IfBB, CodeBB, MergeBB, &InnerRegion, CurrentRegion);
2362 extractKilledPHIs(CodeBB);
2363 if (IsRegionEntryBB) {
2364 createEntryPHIs(CurrentRegion);
2366 return IfBB;
2370 MachineBasicBlock *AMDGPUMachineCFGStructurizer::createIfRegion(
2371 MachineBasicBlock *MergeBB, LinearizedRegion *InnerRegion,
2372 LinearizedRegion *CurrentRegion, MachineBasicBlock *SelectBB,
2373 unsigned BBSelectRegIn, unsigned BBSelectRegOut) {
2374 unsigned CodeBBSelectReg =
2375 InnerRegion->getRegionMRT()->getInnerOutputRegister();
2376 MachineBasicBlock *CodeEntryBB = InnerRegion->getEntry();
2377 MachineBasicBlock *CodeExitBB = InnerRegion->getExit();
2378 MachineBasicBlock *IfBB = createIfBlock(MergeBB, CodeEntryBB, CodeExitBB,
2379 SelectBB, BBSelectRegIn, true);
2380 CurrentRegion->addMBB(IfBB);
2381 bool isEntry = CurrentRegion->getEntry() == InnerRegion->getEntry();
2382 if (isEntry) {
2384 if (CurrentRegion->getHasLoop()) {
2385 MachineBasicBlock *RegionExit = CurrentRegion->getExit();
2386 MachineBasicBlock *ETrueBB = nullptr;
2387 MachineBasicBlock *EFalseBB = nullptr;
2388 SmallVector<MachineOperand, 1> ECond;
2390 const DebugLoc &DL = DebugLoc();
2391 TII->analyzeBranch(*RegionExit, ETrueBB, EFalseBB, ECond);
2392 TII->removeBranch(*RegionExit);
2394 // We need to create a backedge if there is a loop
2395 unsigned Reg =
2396 TII->insertNE(RegionExit, RegionExit->instr_end(), DL,
2397 CurrentRegion->getRegionMRT()->getInnerOutputRegister(),
2398 CurrentRegion->getRegionMRT()->getEntry()->getNumber());
2399 MachineOperand RegOp = MachineOperand::CreateReg(Reg, false, false, true);
2400 ArrayRef<MachineOperand> Cond(RegOp);
2401 LLVM_DEBUG(dbgs() << "RegionExitReg: ");
2402 LLVM_DEBUG(Cond[0].print(dbgs(), TRI));
2403 LLVM_DEBUG(dbgs() << "\n");
2404 TII->insertBranch(*RegionExit, CurrentRegion->getEntry(), RegionExit,
2405 Cond, DebugLoc());
2406 RegionExit->addSuccessor(IfBB);
2409 CurrentRegion->addMBBs(InnerRegion);
2410 LLVM_DEBUG(dbgs() << "Insert BB Select PHI (region)\n");
2411 insertMergePHI(IfBB, CodeExitBB, MergeBB, BBSelectRegOut, BBSelectRegIn,
2412 CodeBBSelectReg);
2414 rewriteLiveOutRegs(IfBB, /* CodeEntryBB */ CodeExitBB, MergeBB, InnerRegion,
2415 CurrentRegion);
2417 rewriteRegionEntryPHIs(InnerRegion, IfBB);
2419 if (isEntry) {
2420 CurrentRegion->setEntry(IfBB);
2423 if (isEntry) {
2424 createEntryPHIs(CurrentRegion);
2427 return IfBB;
2430 void AMDGPUMachineCFGStructurizer::splitLoopPHI(MachineInstr &PHI,
2431 MachineBasicBlock *Entry,
2432 MachineBasicBlock *EntrySucc,
2433 LinearizedRegion *LRegion) {
2434 SmallVector<unsigned, 2> PHIRegionIndices;
2435 getPHIRegionIndices(LRegion, PHI, PHIRegionIndices);
2437 assert(PHIRegionIndices.size() == 1);
2439 unsigned RegionIndex = PHIRegionIndices[0];
2440 unsigned RegionSourceReg = getPHISourceReg(PHI, RegionIndex);
2441 MachineBasicBlock *RegionSourceMBB = getPHIPred(PHI, RegionIndex);
2442 unsigned PHIDest = getPHIDestReg(PHI);
2443 unsigned PHISource = PHIDest;
2444 unsigned ReplaceReg;
2446 if (shrinkPHI(PHI, PHIRegionIndices, &ReplaceReg)) {
2447 PHISource = ReplaceReg;
2450 const TargetRegisterClass *RegClass = MRI->getRegClass(PHIDest);
2451 Register NewDestReg = MRI->createVirtualRegister(RegClass);
2452 LRegion->replaceRegisterInsideRegion(PHIDest, NewDestReg, false, MRI);
2453 MachineInstrBuilder MIB =
2454 BuildMI(*EntrySucc, EntrySucc->instr_begin(), PHI.getDebugLoc(),
2455 TII->get(TargetOpcode::PHI), NewDestReg);
2456 LLVM_DEBUG(dbgs() << "Split Entry PHI " << printReg(NewDestReg, TRI)
2457 << " = PHI(");
2458 MIB.addReg(PHISource);
2459 MIB.addMBB(Entry);
2460 LLVM_DEBUG(dbgs() << printReg(PHISource, TRI) << ", "
2461 << printMBBReference(*Entry));
2462 MIB.addReg(RegionSourceReg);
2463 MIB.addMBB(RegionSourceMBB);
2464 LLVM_DEBUG(dbgs() << " ," << printReg(RegionSourceReg, TRI) << ", "
2465 << printMBBReference(*RegionSourceMBB) << ")\n");
2468 void AMDGPUMachineCFGStructurizer::splitLoopPHIs(MachineBasicBlock *Entry,
2469 MachineBasicBlock *EntrySucc,
2470 LinearizedRegion *LRegion) {
2471 SmallVector<MachineInstr *, 2> PHIs;
2472 collectPHIs(Entry, PHIs);
2474 for (auto PHII : PHIs) {
2475 splitLoopPHI(*PHII, Entry, EntrySucc, LRegion);
2479 // Split the exit block so that we can insert a end control flow
2480 MachineBasicBlock *
2481 AMDGPUMachineCFGStructurizer::splitExit(LinearizedRegion *LRegion) {
2482 auto MRTRegion = LRegion->getRegionMRT();
2483 auto Exit = LRegion->getExit();
2484 auto MF = Exit->getParent();
2485 auto Succ = MRTRegion->getSucc();
2487 auto NewExit = MF->CreateMachineBasicBlock();
2488 auto AfterExitIter = Exit->getIterator();
2489 AfterExitIter++;
2490 MF->insert(AfterExitIter, NewExit);
2491 Exit->removeSuccessor(Succ);
2492 Exit->addSuccessor(NewExit);
2493 NewExit->addSuccessor(Succ);
2494 insertUnconditionalBranch(NewExit, Succ);
2495 LRegion->addMBB(NewExit);
2496 LRegion->setExit(NewExit);
2498 LLVM_DEBUG(dbgs() << "Created new exit block: " << NewExit->getNumber()
2499 << "\n");
2501 // Replace any PHI Predecessors in the successor with NewExit
2502 for (auto &II : *Succ) {
2503 MachineInstr &Instr = II;
2505 // If we are past the PHI instructions we are done
2506 if (!Instr.isPHI())
2507 break;
2509 int numPreds = getPHINumInputs(Instr);
2510 for (int i = 0; i < numPreds; ++i) {
2511 auto Pred = getPHIPred(Instr, i);
2512 if (Pred == Exit) {
2513 setPhiPred(Instr, i, NewExit);
2518 return NewExit;
2521 static MachineBasicBlock *split(MachineBasicBlock::iterator I) {
2522 // Create the fall-through block.
2523 MachineBasicBlock *MBB = (*I).getParent();
2524 MachineFunction *MF = MBB->getParent();
2525 MachineBasicBlock *SuccMBB = MF->CreateMachineBasicBlock();
2526 auto MBBIter = ++(MBB->getIterator());
2527 MF->insert(MBBIter, SuccMBB);
2528 SuccMBB->transferSuccessorsAndUpdatePHIs(MBB);
2529 MBB->addSuccessor(SuccMBB);
2531 // Splice the code over.
2532 SuccMBB->splice(SuccMBB->end(), MBB, I, MBB->end());
2534 return SuccMBB;
2537 // Split the entry block separating PHI-nodes and the rest of the code
2538 // This is needed to insert an initializer for the bb select register
2539 // inloop regions.
2541 MachineBasicBlock *
2542 AMDGPUMachineCFGStructurizer::splitEntry(LinearizedRegion *LRegion) {
2543 MachineBasicBlock *Entry = LRegion->getEntry();
2544 MachineBasicBlock *EntrySucc = split(Entry->getFirstNonPHI());
2545 MachineBasicBlock *Exit = LRegion->getExit();
2547 LLVM_DEBUG(dbgs() << "Split " << printMBBReference(*Entry) << " to "
2548 << printMBBReference(*Entry) << " -> "
2549 << printMBBReference(*EntrySucc) << "\n");
2550 LRegion->addMBB(EntrySucc);
2552 // Make the backedge go to Entry Succ
2553 if (Exit->isSuccessor(Entry)) {
2554 Exit->removeSuccessor(Entry);
2556 Exit->addSuccessor(EntrySucc);
2557 MachineInstr &Branch = *(Exit->instr_rbegin());
2558 for (auto &UI : Branch.uses()) {
2559 if (UI.isMBB() && UI.getMBB() == Entry) {
2560 UI.setMBB(EntrySucc);
2564 splitLoopPHIs(Entry, EntrySucc, LRegion);
2566 return EntrySucc;
2569 LinearizedRegion *
2570 AMDGPUMachineCFGStructurizer::initLinearizedRegion(RegionMRT *Region) {
2571 LinearizedRegion *LRegion = Region->getLinearizedRegion();
2572 LRegion->initLiveOut(Region, MRI, TRI, PHIInfo);
2573 LRegion->setEntry(Region->getEntry());
2574 return LRegion;
2577 static void removeOldExitPreds(RegionMRT *Region) {
2578 MachineBasicBlock *Exit = Region->getSucc();
2579 if (Exit == nullptr) {
2580 return;
2582 for (MachineBasicBlock::pred_iterator PI = Exit->pred_begin(),
2583 E = Exit->pred_end();
2584 PI != E; ++PI) {
2585 if (Region->contains(*PI)) {
2586 (*PI)->removeSuccessor(Exit);
2591 static bool mbbHasBackEdge(MachineBasicBlock *MBB,
2592 SmallPtrSet<MachineBasicBlock *, 8> &MBBs) {
2593 for (auto SI = MBB->succ_begin(), SE = MBB->succ_end(); SI != SE; ++SI) {
2594 if (MBBs.count(*SI) != 0) {
2595 return true;
2598 return false;
2601 static bool containsNewBackedge(MRT *Tree,
2602 SmallPtrSet<MachineBasicBlock *, 8> &MBBs) {
2603 // Need to traverse this in reverse since it is in post order.
2604 if (Tree == nullptr)
2605 return false;
2607 if (Tree->isMBB()) {
2608 MachineBasicBlock *MBB = Tree->getMBBMRT()->getMBB();
2609 MBBs.insert(MBB);
2610 if (mbbHasBackEdge(MBB, MBBs)) {
2611 return true;
2613 } else {
2614 RegionMRT *Region = Tree->getRegionMRT();
2615 SetVector<MRT *> *Children = Region->getChildren();
2616 for (auto CI = Children->rbegin(), CE = Children->rend(); CI != CE; ++CI) {
2617 if (containsNewBackedge(*CI, MBBs))
2618 return true;
2621 return false;
2624 static bool containsNewBackedge(RegionMRT *Region) {
2625 SmallPtrSet<MachineBasicBlock *, 8> MBBs;
2626 return containsNewBackedge(Region, MBBs);
2629 bool AMDGPUMachineCFGStructurizer::structurizeComplexRegion(RegionMRT *Region) {
2630 auto *LRegion = initLinearizedRegion(Region);
2631 LRegion->setHasLoop(containsNewBackedge(Region));
2632 MachineBasicBlock *LastMerge = createLinearizedExitBlock(Region);
2633 MachineBasicBlock *CurrentMerge = LastMerge;
2634 LRegion->addMBB(LastMerge);
2635 LRegion->setExit(LastMerge);
2637 rewriteRegionExitPHIs(Region, LastMerge, LRegion);
2638 removeOldExitPreds(Region);
2640 LLVM_DEBUG(PHIInfo.dump(MRI));
2642 SetVector<MRT *> *Children = Region->getChildren();
2643 LLVM_DEBUG(dbgs() << "===========If Region Start===============\n");
2644 if (LRegion->getHasLoop()) {
2645 LLVM_DEBUG(dbgs() << "Has Backedge: Yes\n");
2646 } else {
2647 LLVM_DEBUG(dbgs() << "Has Backedge: No\n");
2650 unsigned BBSelectRegIn;
2651 unsigned BBSelectRegOut;
2652 for (auto CI = Children->begin(), CE = Children->end(); CI != CE; ++CI) {
2653 LLVM_DEBUG(dbgs() << "CurrentRegion: \n");
2654 LLVM_DEBUG(LRegion->print(dbgs(), TRI));
2656 auto CNI = CI;
2657 ++CNI;
2659 MRT *Child = (*CI);
2661 if (Child->isRegion()) {
2663 LinearizedRegion *InnerLRegion =
2664 Child->getRegionMRT()->getLinearizedRegion();
2665 // We found the block is the exit of an inner region, we need
2666 // to put it in the current linearized region.
2668 LLVM_DEBUG(dbgs() << "Linearizing region: ");
2669 LLVM_DEBUG(InnerLRegion->print(dbgs(), TRI));
2670 LLVM_DEBUG(dbgs() << "\n");
2672 MachineBasicBlock *InnerEntry = InnerLRegion->getEntry();
2673 if ((&(*(InnerEntry->getParent()->begin()))) == InnerEntry) {
2674 // Entry has already been linearized, no need to do this region.
2675 unsigned OuterSelect = InnerLRegion->getBBSelectRegOut();
2676 unsigned InnerSelectReg =
2677 InnerLRegion->getRegionMRT()->getInnerOutputRegister();
2678 replaceRegisterWith(InnerSelectReg, OuterSelect),
2679 resolvePHIInfos(InnerEntry);
2680 if (!InnerLRegion->getExit()->isSuccessor(CurrentMerge))
2681 InnerLRegion->getExit()->addSuccessor(CurrentMerge);
2682 continue;
2685 BBSelectRegOut = Child->getBBSelectRegOut();
2686 BBSelectRegIn = Child->getBBSelectRegIn();
2688 LLVM_DEBUG(dbgs() << "BBSelectRegIn: " << printReg(BBSelectRegIn, TRI)
2689 << "\n");
2690 LLVM_DEBUG(dbgs() << "BBSelectRegOut: " << printReg(BBSelectRegOut, TRI)
2691 << "\n");
2693 MachineBasicBlock *IfEnd = CurrentMerge;
2694 CurrentMerge = createIfRegion(CurrentMerge, InnerLRegion, LRegion,
2695 Child->getRegionMRT()->getEntry(),
2696 BBSelectRegIn, BBSelectRegOut);
2697 TII->convertNonUniformIfRegion(CurrentMerge, IfEnd);
2698 } else {
2699 MachineBasicBlock *MBB = Child->getMBBMRT()->getMBB();
2700 LLVM_DEBUG(dbgs() << "Linearizing block: " << MBB->getNumber() << "\n");
2702 if (MBB == getSingleExitNode(*(MBB->getParent()))) {
2703 // If this is the exit block then we need to skip to the next.
2704 // The "in" register will be transferred to "out" in the next
2705 // iteration.
2706 continue;
2709 BBSelectRegOut = Child->getBBSelectRegOut();
2710 BBSelectRegIn = Child->getBBSelectRegIn();
2712 LLVM_DEBUG(dbgs() << "BBSelectRegIn: " << printReg(BBSelectRegIn, TRI)
2713 << "\n");
2714 LLVM_DEBUG(dbgs() << "BBSelectRegOut: " << printReg(BBSelectRegOut, TRI)
2715 << "\n");
2717 MachineBasicBlock *IfEnd = CurrentMerge;
2718 // This is a basic block that is not part of an inner region, we
2719 // need to put it in the current linearized region.
2720 CurrentMerge = createIfRegion(CurrentMerge, MBB, LRegion, BBSelectRegIn,
2721 BBSelectRegOut);
2722 if (CurrentMerge) {
2723 TII->convertNonUniformIfRegion(CurrentMerge, IfEnd);
2726 LLVM_DEBUG(PHIInfo.dump(MRI));
2730 LRegion->removeFalseRegisterKills(MRI);
2732 if (LRegion->getHasLoop()) {
2733 MachineBasicBlock *NewSucc = splitEntry(LRegion);
2734 if (isFunctionEntryBlock(LRegion->getEntry())) {
2735 resolvePHIInfos(LRegion->getEntry());
2737 const DebugLoc &DL = NewSucc->findDebugLoc(NewSucc->getFirstNonPHI());
2738 unsigned InReg = LRegion->getBBSelectRegIn();
2739 Register InnerSelectReg =
2740 MRI->createVirtualRegister(MRI->getRegClass(InReg));
2741 Register NewInReg = MRI->createVirtualRegister(MRI->getRegClass(InReg));
2742 TII->materializeImmediate(*(LRegion->getEntry()),
2743 LRegion->getEntry()->getFirstTerminator(), DL,
2744 NewInReg, Region->getEntry()->getNumber());
2745 // Need to be careful about updating the registers inside the region.
2746 LRegion->replaceRegisterInsideRegion(InReg, InnerSelectReg, false, MRI);
2747 LLVM_DEBUG(dbgs() << "Loop BBSelect Merge PHI:\n");
2748 insertMergePHI(LRegion->getEntry(), LRegion->getExit(), NewSucc,
2749 InnerSelectReg, NewInReg,
2750 LRegion->getRegionMRT()->getInnerOutputRegister());
2751 splitExit(LRegion);
2752 TII->convertNonUniformLoopRegion(NewSucc, LastMerge);
2755 if (Region->isRoot()) {
2756 TII->insertReturn(*LastMerge);
2759 LLVM_DEBUG(Region->getEntry()->getParent()->dump());
2760 LLVM_DEBUG(LRegion->print(dbgs(), TRI));
2761 LLVM_DEBUG(PHIInfo.dump(MRI));
2763 LLVM_DEBUG(dbgs() << "===========If Region End===============\n");
2765 Region->setLinearizedRegion(LRegion);
2766 return true;
2769 bool AMDGPUMachineCFGStructurizer::structurizeRegion(RegionMRT *Region) {
2770 if (false && regionIsSimpleIf(Region)) {
2771 transformSimpleIfRegion(Region);
2772 return true;
2773 } else if (regionIsSequence(Region)) {
2774 fixupRegionExits(Region);
2775 return false;
2776 } else {
2777 structurizeComplexRegion(Region);
2779 return false;
2782 static int structurize_once = 0;
2784 bool AMDGPUMachineCFGStructurizer::structurizeRegions(RegionMRT *Region,
2785 bool isTopRegion) {
2786 bool Changed = false;
2788 auto Children = Region->getChildren();
2789 for (auto CI : *Children) {
2790 if (CI->isRegion()) {
2791 Changed |= structurizeRegions(CI->getRegionMRT(), false);
2795 if (structurize_once < 2 || true) {
2796 Changed |= structurizeRegion(Region);
2797 structurize_once++;
2799 return Changed;
2802 void AMDGPUMachineCFGStructurizer::initFallthroughMap(MachineFunction &MF) {
2803 LLVM_DEBUG(dbgs() << "Fallthrough Map:\n");
2804 for (auto &MBBI : MF) {
2805 MachineBasicBlock *MBB = MBBI.getFallThrough();
2806 if (MBB != nullptr) {
2807 LLVM_DEBUG(dbgs() << "Fallthrough: " << MBBI.getNumber() << " -> "
2808 << MBB->getNumber() << "\n");
2810 FallthroughMap[&MBBI] = MBB;
2814 void AMDGPUMachineCFGStructurizer::createLinearizedRegion(RegionMRT *Region,
2815 unsigned SelectOut) {
2816 LinearizedRegion *LRegion = new LinearizedRegion();
2817 if (SelectOut) {
2818 LRegion->addLiveOut(SelectOut);
2819 LLVM_DEBUG(dbgs() << "Add LiveOut (BBSelect): " << printReg(SelectOut, TRI)
2820 << "\n");
2822 LRegion->setRegionMRT(Region);
2823 Region->setLinearizedRegion(LRegion);
2824 LRegion->setParent(Region->getParent()
2825 ? Region->getParent()->getLinearizedRegion()
2826 : nullptr);
2829 unsigned
2830 AMDGPUMachineCFGStructurizer::initializeSelectRegisters(MRT *MRT, unsigned SelectOut,
2831 MachineRegisterInfo *MRI,
2832 const SIInstrInfo *TII) {
2833 if (MRT->isRegion()) {
2834 RegionMRT *Region = MRT->getRegionMRT();
2835 Region->setBBSelectRegOut(SelectOut);
2836 unsigned InnerSelectOut = createBBSelectReg(TII, MRI);
2838 // Fixme: Move linearization creation to the original spot
2839 createLinearizedRegion(Region, SelectOut);
2841 for (auto CI = Region->getChildren()->begin(),
2842 CE = Region->getChildren()->end();
2843 CI != CE; ++CI) {
2844 InnerSelectOut =
2845 initializeSelectRegisters((*CI), InnerSelectOut, MRI, TII);
2847 MRT->setBBSelectRegIn(InnerSelectOut);
2848 return InnerSelectOut;
2849 } else {
2850 MRT->setBBSelectRegOut(SelectOut);
2851 unsigned NewSelectIn = createBBSelectReg(TII, MRI);
2852 MRT->setBBSelectRegIn(NewSelectIn);
2853 return NewSelectIn;
2857 static void checkRegOnlyPHIInputs(MachineFunction &MF) {
2858 for (auto &MBBI : MF) {
2859 for (MachineBasicBlock::instr_iterator I = MBBI.instr_begin(),
2860 E = MBBI.instr_end();
2861 I != E; ++I) {
2862 MachineInstr &Instr = *I;
2863 if (Instr.isPHI()) {
2864 int numPreds = getPHINumInputs(Instr);
2865 for (int i = 0; i < numPreds; ++i) {
2866 assert(Instr.getOperand(i * 2 + 1).isReg() &&
2867 "PHI Operand not a register");
2874 bool AMDGPUMachineCFGStructurizer::runOnMachineFunction(MachineFunction &MF) {
2875 const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
2876 const SIInstrInfo *TII = ST.getInstrInfo();
2877 TRI = ST.getRegisterInfo();
2878 MRI = &(MF.getRegInfo());
2879 initFallthroughMap(MF);
2881 checkRegOnlyPHIInputs(MF);
2882 LLVM_DEBUG(dbgs() << "----STRUCTURIZER START----\n");
2883 LLVM_DEBUG(MF.dump());
2885 Regions = &(getAnalysis<MachineRegionInfoPass>().getRegionInfo());
2886 LLVM_DEBUG(Regions->dump());
2888 RegionMRT *RTree = MRT::buildMRT(MF, Regions, TII, MRI);
2889 setRegionMRT(RTree);
2890 initializeSelectRegisters(RTree, 0, MRI, TII);
2891 LLVM_DEBUG(RTree->dump(TRI));
2892 bool result = structurizeRegions(RTree, true);
2893 delete RTree;
2894 LLVM_DEBUG(dbgs() << "----STRUCTURIZER END----\n");
2895 initFallthroughMap(MF);
2896 return result;
2899 char AMDGPUMachineCFGStructurizerID = AMDGPUMachineCFGStructurizer::ID;
2901 INITIALIZE_PASS_BEGIN(AMDGPUMachineCFGStructurizer, "amdgpu-machine-cfg-structurizer",
2902 "AMDGPU Machine CFG Structurizer", false, false)
2903 INITIALIZE_PASS_DEPENDENCY(MachineRegionInfoPass)
2904 INITIALIZE_PASS_END(AMDGPUMachineCFGStructurizer, "amdgpu-machine-cfg-structurizer",
2905 "AMDGPU Machine CFG Structurizer", false, false)
2907 FunctionPass *llvm::createAMDGPUMachineCFGStructurizerPass() {
2908 return new AMDGPUMachineCFGStructurizer();