Bug Summary

File:src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp
Warning:line 2276, column 27
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name AMDGPUMachineCFGStructurizer.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -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 -setup-static-analyzer -mrelocation-model pic -pic-level 1 -fhalf-no-semantic-interposition -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Analysis -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ASMParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/BinaryFormat -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitstream -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /include/llvm/CodeGen -I /include/llvm/CodeGen/PBQP -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Coroutines -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData/Coverage -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/CodeView -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/DWARF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/MSF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/PDB -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Demangle -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/JITLink -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/Orc -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenACC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenMP -I /include/llvm/CodeGen/GlobalISel -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IRReader -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/LTO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Linker -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC/MCParser -I /include/llvm/CodeGen/MIRParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Object -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Option -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Passes -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Scalar -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ADT -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/Symbolize -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Target -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Utils -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Vectorize -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/IPO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include -I /usr/src/gnu/usr.bin/clang/libLLVM/../include -I /usr/src/gnu/usr.bin/clang/libLLVM/obj -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include -D NDEBUG -D __STDC_LIMIT_MACROS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D LLVM_PREFIX="/usr" -D PIC -internal-isystem /usr/include/c++/v1 -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -ferror-limit 19 -fvisibility-inlines-hidden -fwrapv -D_RET_PROTECTOR -ret-protector -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c++ /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU/AMDGPUMachineCFGStructurizer.cpp

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

/usr/include/c++/v1/__iterator/wrap_iter.h

1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP___ITERATOR_WRAP_ITER_H
11#define _LIBCPP___ITERATOR_WRAP_ITER_H
12
13#include <__config>
14#include <__debug>
15#include <__iterator/iterator_traits.h>
16#include <__memory/pointer_traits.h> // __to_address
17#include <type_traits>
18
19#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
20#pragma GCC system_header
21#endif
22
23_LIBCPP_PUSH_MACROSpush_macro("min") push_macro("max")
24#include <__undef_macros>
25
26_LIBCPP_BEGIN_NAMESPACE_STDnamespace std { inline namespace __1 {
27
28template <class _Iter>
29class __wrap_iter
30{
31public:
32 typedef _Iter iterator_type;
33 typedef typename iterator_traits<iterator_type>::value_type value_type;
34 typedef typename iterator_traits<iterator_type>::difference_type difference_type;
35 typedef typename iterator_traits<iterator_type>::pointer pointer;
36 typedef typename iterator_traits<iterator_type>::reference reference;
37 typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
38#if _LIBCPP_STD_VER14 > 17
39 typedef contiguous_iterator_tag iterator_concept;
40#endif
41
42private:
43 iterator_type __i;
44public:
45 _LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr __wrap_iter() _NOEXCEPTnoexcept
46#if _LIBCPP_STD_VER14 > 11
47 : __i{}
48#endif
49 {
50#if _LIBCPP_DEBUG_LEVEL0 == 2
51 __get_db()->__insert_i(this);
52#endif
53 }
54 template <class _Up> _LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr
55 __wrap_iter(const __wrap_iter<_Up>& __u,
56 typename enable_if<is_convertible<_Up, iterator_type>::value>::type* = nullptr) _NOEXCEPTnoexcept
57 : __i(__u.base())
58 {
59#if _LIBCPP_DEBUG_LEVEL0 == 2
60 __get_db()->__iterator_copy(this, &__u);
61#endif
62 }
63#if _LIBCPP_DEBUG_LEVEL0 == 2
64 _LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr
65 __wrap_iter(const __wrap_iter& __x)
66 : __i(__x.base())
67 {
68 __get_db()->__iterator_copy(this, &__x);
69 }
70 _LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr
71 __wrap_iter& operator=(const __wrap_iter& __x)
72 {
73 if (this != &__x)
74 {
75 __get_db()->__iterator_copy(this, &__x);
76 __i = __x.__i;
77 }
78 return *this;
79 }
80 _LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr
81 ~__wrap_iter()
82 {
83 __get_db()->__erase_i(this);
84 }
85#endif
86 _LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr reference operator*() const _NOEXCEPTnoexcept
87 {
88#if _LIBCPP_DEBUG_LEVEL0 == 2
89 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),((void)0)
90 "Attempted to dereference a non-dereferenceable iterator")((void)0);
91#endif
92 return *__i;
93 }
94 _LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr pointer operator->() const _NOEXCEPTnoexcept
95 {
96#if _LIBCPP_DEBUG_LEVEL0 == 2
97 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),((void)0)
98 "Attempted to dereference a non-dereferenceable iterator")((void)0);
99#endif
100 return _VSTDstd::__1::__to_address(__i);
101 }
102 _LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr __wrap_iter& operator++() _NOEXCEPTnoexcept
103 {
104#if _LIBCPP_DEBUG_LEVEL0 == 2
105 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),((void)0)
106 "Attempted to increment a non-incrementable iterator")((void)0);
107#endif
108 ++__i;
109 return *this;
110 }
111 _LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr __wrap_iter operator++(int) _NOEXCEPTnoexcept
112 {__wrap_iter __tmp(*this); ++(*this); return __tmp;}
113
114 _LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr __wrap_iter& operator--() _NOEXCEPTnoexcept
115 {
116#if _LIBCPP_DEBUG_LEVEL0 == 2
117 _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),((void)0)
118 "Attempted to decrement a non-decrementable iterator")((void)0);
119#endif
120 --__i;
121 return *this;
122 }
123 _LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr __wrap_iter operator--(int) _NOEXCEPTnoexcept
124 {__wrap_iter __tmp(*this); --(*this); return __tmp;}
125 _LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr __wrap_iter operator+ (difference_type __n) const _NOEXCEPTnoexcept
126 {__wrap_iter __w(*this); __w += __n; return __w;}
127 _LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr __wrap_iter& operator+=(difference_type __n) _NOEXCEPTnoexcept
128 {
129#if _LIBCPP_DEBUG_LEVEL0 == 2
130 _LIBCPP_ASSERT(__get_const_db()->__addable(this, __n),((void)0)
131 "Attempted to add/subtract an iterator outside its valid range")((void)0);
132#endif
133 __i += __n;
134 return *this;
135 }
136 _LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr __wrap_iter operator- (difference_type __n) const _NOEXCEPTnoexcept
137 {return *this + (-__n);}
138 _LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr __wrap_iter& operator-=(difference_type __n) _NOEXCEPTnoexcept
139 {*this += -__n; return *this;}
140 _LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr reference operator[](difference_type __n) const _NOEXCEPTnoexcept
141 {
142#if _LIBCPP_DEBUG_LEVEL0 == 2
143 _LIBCPP_ASSERT(__get_const_db()->__subscriptable(this, __n),((void)0)
144 "Attempted to subscript an iterator outside its valid range")((void)0);
145#endif
146 return __i[__n];
147 }
148
149 _LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr iterator_type base() const _NOEXCEPTnoexcept {return __i;}
150
151private:
152#if _LIBCPP_DEBUG_LEVEL0 == 2
153 _LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr __wrap_iter(const void* __p, iterator_type __x) : __i(__x)
154 {
155 __get_db()->__insert_ic(this, __p);
156 }
157#else
158 _LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr __wrap_iter(iterator_type __x) _NOEXCEPTnoexcept : __i(__x) {}
159#endif
160
161 template <class _Up> friend class __wrap_iter;
162 template <class _CharT, class _Traits, class _Alloc> friend class basic_string;
163 template <class _Tp, class _Alloc> friend class _LIBCPP_TEMPLATE_VIS__attribute__ ((__type_visibility__("default"))) vector;
164 template <class _Tp, size_t> friend class _LIBCPP_TEMPLATE_VIS__attribute__ ((__type_visibility__("default"))) span;
165};
166
167template <class _Iter1>
168_LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr
169bool operator==(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPTnoexcept
170{
171 return __x.base() == __y.base();
25
←
Assuming the condition is false
→
26
←
Returning zero, which participates in a condition later
→
64
←
Assuming the condition is false
→
65
←
Returning zero, which participates in a condition later
→
172}
173
174template <class _Iter1, class _Iter2>
175_LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr
176bool operator==(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPTnoexcept
177{
178 return __x.base() == __y.base();
179}
180
181template <class _Iter1>
182_LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr
183bool operator<(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPTnoexcept
184{
185#if _LIBCPP_DEBUG_LEVEL0 == 2
186 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y),((void)0)
187 "Attempted to compare incomparable iterators")((void)0);
188#endif
189 return __x.base() < __y.base();
190}
191
192template <class _Iter1, class _Iter2>
193_LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr
194bool operator<(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPTnoexcept
195{
196#if _LIBCPP_DEBUG_LEVEL0 == 2
197 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y),((void)0)
198 "Attempted to compare incomparable iterators")((void)0);
199#endif
200 return __x.base() < __y.base();
201}
202
203template <class _Iter1>
204_LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr
205bool operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPTnoexcept
206{
207 return !(__x == __y);
24
←
Calling 'operator==<(anonymous namespace)::MRT *const *>'
→
27
←
Returning from 'operator==<(anonymous namespace)::MRT *const *>'
→
28
←
Returning the value 1, which participates in a condition later
→
63
←
Calling 'operator==<(anonymous namespace)::MRT *const *>'
→
66
←
Returning from 'operator==<(anonymous namespace)::MRT *const *>'
→
67
←
Returning the value 1, which participates in a condition later
→
208}
209
210template <class _Iter1, class _Iter2>
211_LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr
212bool operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPTnoexcept
213{
214 return !(__x == __y);
215}
216
217template <class _Iter1>
218_LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr
219bool operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPTnoexcept
220{
221 return __y < __x;
222}
223
224template <class _Iter1, class _Iter2>
225_LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr
226bool operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPTnoexcept
227{
228 return __y < __x;
229}
230
231template <class _Iter1>
232_LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr
233bool operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPTnoexcept
234{
235 return !(__x < __y);
236}
237
238template <class _Iter1, class _Iter2>
239_LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr
240bool operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPTnoexcept
241{
242 return !(__x < __y);
243}
244
245template <class _Iter1>
246_LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr
247bool operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPTnoexcept
248{
249 return !(__y < __x);
250}
251
252template <class _Iter1, class _Iter2>
253_LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr
254bool operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPTnoexcept
255{
256 return !(__y < __x);
257}
258
259template <class _Iter1, class _Iter2>
260_LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr
261#ifndef _LIBCPP_CXX03_LANG
262auto operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPTnoexcept
263 -> decltype(__x.base() - __y.base())
264#else
265typename __wrap_iter<_Iter1>::difference_type
266operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPTnoexcept
267#endif // C++03
268{
269#if _LIBCPP_DEBUG_LEVEL0 == 2
270 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y),((void)0)
271 "Attempted to subtract incompatible iterators")((void)0);
272#endif
273 return __x.base() - __y.base();
274}
275
276template <class _Iter1>
277_LIBCPP_INLINE_VISIBILITY__attribute__ ((__visibility__("hidden"))) __attribute__ ((__exclude_from_explicit_instantiation__
)) _LIBCPP_CONSTEXPR_IF_NODEBUGconstexpr
278__wrap_iter<_Iter1> operator+(typename __wrap_iter<_Iter1>::difference_type __n, __wrap_iter<_Iter1> __x) _NOEXCEPTnoexcept
279{
280 __x += __n;
281 return __x;
282}
283
284#if _LIBCPP_STD_VER14 <= 17
285template <class _It>
286struct __is_cpp17_contiguous_iterator<__wrap_iter<_It> > : true_type {};
287#endif
288
289template <class _Iter>
290_LIBCPP_CONSTEXPRconstexpr
291decltype(_VSTDstd::__1::__to_address(declval<_Iter>()))
292__to_address(__wrap_iter<_Iter> __w) _NOEXCEPTnoexcept {
293 return _VSTDstd::__1::__to_address(__w.base());
294}
295
296_LIBCPP_END_NAMESPACE_STD} }
297
298_LIBCPP_POP_MACROSpop_macro("min") pop_macro("max")
299
300#endif // _LIBCPP___ITERATOR_WRAP_ITER_H