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