Bug Summary

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