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