Bug Summary

File:lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp
Warning:line 1911, column 42
Called C++ object pointer is null

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