Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

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