clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name CriticalAntiDepBreaker.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/CodeGen/CriticalAntiDepBreaker.cpp
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
14 | |
15 | #include "CriticalAntiDepBreaker.h" |
16 | #include "llvm/ADT/ArrayRef.h" |
17 | #include "llvm/ADT/DenseMap.h" |
18 | #include "llvm/ADT/SmallVector.h" |
19 | #include "llvm/CodeGen/MachineBasicBlock.h" |
20 | #include "llvm/CodeGen/MachineFrameInfo.h" |
21 | #include "llvm/CodeGen/MachineFunction.h" |
22 | #include "llvm/CodeGen/MachineInstr.h" |
23 | #include "llvm/CodeGen/MachineOperand.h" |
24 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
25 | #include "llvm/CodeGen/RegisterClassInfo.h" |
26 | #include "llvm/CodeGen/ScheduleDAG.h" |
27 | #include "llvm/CodeGen/TargetInstrInfo.h" |
28 | #include "llvm/CodeGen/TargetRegisterInfo.h" |
29 | #include "llvm/CodeGen/TargetSubtargetInfo.h" |
30 | #include "llvm/MC/MCInstrDesc.h" |
31 | #include "llvm/MC/MCRegisterInfo.h" |
32 | #include "llvm/Support/Debug.h" |
33 | #include "llvm/Support/raw_ostream.h" |
34 | #include <cassert> |
35 | #include <utility> |
36 | |
37 | using namespace llvm; |
38 | |
39 | #define DEBUG_TYPE "post-RA-sched" |
40 | |
41 | CriticalAntiDepBreaker::CriticalAntiDepBreaker(MachineFunction &MFi, |
42 | const RegisterClassInfo &RCI) |
43 | : AntiDepBreaker(), MF(MFi), MRI(MF.getRegInfo()), |
44 | TII(MF.getSubtarget().getInstrInfo()), |
45 | TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI), |
46 | Classes(TRI->getNumRegs(), nullptr), KillIndices(TRI->getNumRegs(), 0), |
47 | DefIndices(TRI->getNumRegs(), 0), KeepRegs(TRI->getNumRegs(), false) {} |
48 | |
49 | CriticalAntiDepBreaker::~CriticalAntiDepBreaker() = default; |
50 | |
51 | void CriticalAntiDepBreaker::StartBlock(MachineBasicBlock *BB) { |
52 | const unsigned BBSize = BB->size(); |
53 | for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i) { |
54 | |
55 | Classes[i] = nullptr; |
56 | |
57 | |
58 | KillIndices[i] = ~0u; |
59 | DefIndices[i] = BBSize; |
60 | } |
61 | |
62 | |
63 | KeepRegs.reset(); |
64 | |
65 | bool IsReturnBlock = BB->isReturnBlock(); |
66 | |
67 | |
68 | for (const MachineBasicBlock *Succ : BB->successors()) |
69 | for (const auto &LI : Succ->liveins()) { |
70 | for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI) { |
71 | unsigned Reg = *AI; |
72 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); |
73 | KillIndices[Reg] = BBSize; |
74 | DefIndices[Reg] = ~0u; |
75 | } |
76 | } |
77 | |
78 | |
79 | |
80 | |
81 | const MachineFrameInfo &MFI = MF.getFrameInfo(); |
82 | BitVector Pristine = MFI.getPristineRegs(MF); |
83 | for (const MCPhysReg *I = MF.getRegInfo().getCalleeSavedRegs(); *I; |
84 | ++I) { |
85 | unsigned Reg = *I; |
86 | if (!IsReturnBlock && !Pristine.test(Reg)) |
87 | continue; |
88 | for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI) { |
89 | unsigned Reg = *AI; |
90 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); |
91 | KillIndices[Reg] = BBSize; |
92 | DefIndices[Reg] = ~0u; |
93 | } |
94 | } |
95 | } |
96 | |
97 | void CriticalAntiDepBreaker::FinishBlock() { |
98 | RegRefs.clear(); |
99 | KeepRegs.reset(); |
100 | } |
101 | |
102 | void CriticalAntiDepBreaker::Observe(MachineInstr &MI, unsigned Count, |
103 | unsigned InsertPosIndex) { |
104 | |
105 | |
106 | |
107 | |
108 | |
109 | |
110 | |
111 | if (MI.isDebugInstr() || MI.isKill()) |
112 | return; |
113 | assert(Count < InsertPosIndex && "Instruction index out of expected range!"); |
114 | |
115 | for (unsigned Reg = 0; Reg != TRI->getNumRegs(); ++Reg) { |
116 | if (KillIndices[Reg] != ~0u) { |
117 | |
118 | |
119 | |
120 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); |
121 | KillIndices[Reg] = Count; |
122 | } else if (DefIndices[Reg] < InsertPosIndex && DefIndices[Reg] >= Count) { |
123 | |
124 | |
125 | |
126 | |
127 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); |
128 | |
129 | |
130 | |
131 | DefIndices[Reg] = InsertPosIndex; |
132 | } |
133 | } |
134 | |
135 | PrescanInstruction(MI); |
136 | ScanInstruction(MI, Count); |
137 | } |
138 | |
139 | |
140 | |
141 | static const SDep *CriticalPathStep(const SUnit *SU) { |
142 | const SDep *Next = nullptr; |
143 | unsigned NextDepth = 0; |
144 | |
145 | for (const SDep &P : SU->Preds) { |
146 | const SUnit *PredSU = P.getSUnit(); |
147 | unsigned PredLatency = P.getLatency(); |
148 | unsigned PredTotalLatency = PredSU->getDepth() + PredLatency; |
149 | |
150 | |
151 | if (NextDepth < PredTotalLatency || |
152 | (NextDepth == PredTotalLatency && P.getKind() == SDep::Anti)) { |
153 | NextDepth = PredTotalLatency; |
154 | Next = &P; |
155 | } |
156 | } |
157 | return Next; |
158 | } |
159 | |
160 | void CriticalAntiDepBreaker::PrescanInstruction(MachineInstr &MI) { |
161 | |
162 | |
163 | |
164 | |
165 | |
166 | |
167 | |
168 | |
169 | |
170 | |
171 | |
172 | |
173 | |
174 | |
175 | |
176 | |
177 | bool Special = |
178 | MI.isCall() || MI.hasExtraSrcRegAllocReq() || TII->isPredicated(MI); |
179 | |
180 | |
181 | |
182 | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { |
183 | MachineOperand &MO = MI.getOperand(i); |
184 | if (!MO.isReg()) continue; |
185 | Register Reg = MO.getReg(); |
186 | if (Reg == 0) continue; |
187 | const TargetRegisterClass *NewRC = nullptr; |
188 | |
189 | if (i < MI.getDesc().getNumOperands()) |
190 | NewRC = TII->getRegClass(MI.getDesc(), i, TRI, MF); |
191 | |
192 | |
193 | |
194 | if (!Classes[Reg] && NewRC) |
195 | Classes[Reg] = NewRC; |
196 | else if (!NewRC || Classes[Reg] != NewRC) |
197 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); |
198 | |
199 | |
200 | for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) { |
201 | |
202 | |
203 | |
204 | unsigned AliasReg = *AI; |
205 | if (Classes[AliasReg]) { |
206 | Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); |
207 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); |
208 | } |
209 | } |
210 | |
211 | |
212 | if (Classes[Reg] != reinterpret_cast<TargetRegisterClass *>(-1)) |
213 | RegRefs.insert(std::make_pair(Reg, &MO)); |
214 | |
215 | |
216 | |
217 | |
218 | |
219 | |
220 | |
221 | |
222 | |
223 | |
224 | |
225 | if (MI.isRegTiedToUseOperand(i) && |
226 | Classes[Reg] == reinterpret_cast<TargetRegisterClass *>(-1)) { |
227 | for (MCSubRegIterator SubRegs(Reg, TRI, true); |
228 | SubRegs.isValid(); ++SubRegs) { |
229 | KeepRegs.set(*SubRegs); |
230 | } |
231 | for (MCSuperRegIterator SuperRegs(Reg, TRI); |
232 | SuperRegs.isValid(); ++SuperRegs) { |
233 | KeepRegs.set(*SuperRegs); |
234 | } |
235 | } |
236 | |
237 | if (MO.isUse() && Special) { |
238 | if (!KeepRegs.test(Reg)) { |
239 | for (MCSubRegIterator SubRegs(Reg, TRI, true); |
240 | SubRegs.isValid(); ++SubRegs) |
241 | KeepRegs.set(*SubRegs); |
242 | } |
243 | } |
244 | } |
245 | } |
246 | |
247 | void CriticalAntiDepBreaker::ScanInstruction(MachineInstr &MI, unsigned Count) { |
248 | |
249 | |
250 | |
251 | assert(!MI.isKill() && "Attempting to scan a kill instruction"); |
252 | |
253 | if (!TII->isPredicated(MI)) { |
254 | |
255 | |
256 | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { |
257 | MachineOperand &MO = MI.getOperand(i); |
258 | |
259 | if (MO.isRegMask()) { |
260 | auto ClobbersPhysRegAndSubRegs = [&](unsigned PhysReg) { |
261 | for (MCSubRegIterator SRI(PhysReg, TRI, true); SRI.isValid(); ++SRI) |
262 | if (!MO.clobbersPhysReg(*SRI)) |
263 | return false; |
264 | |
265 | return true; |
266 | }; |
267 | |
268 | for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i) { |
269 | if (ClobbersPhysRegAndSubRegs(i)) { |
270 | DefIndices[i] = Count; |
271 | KillIndices[i] = ~0u; |
272 | KeepRegs.reset(i); |
273 | Classes[i] = nullptr; |
274 | RegRefs.erase(i); |
275 | } |
276 | } |
277 | } |
278 | |
279 | if (!MO.isReg()) continue; |
280 | Register Reg = MO.getReg(); |
281 | if (Reg == 0) continue; |
282 | if (!MO.isDef()) continue; |
283 | |
284 | |
285 | if (MI.isRegTiedToUseOperand(i)) |
286 | continue; |
287 | |
288 | |
289 | |
290 | bool Keep = KeepRegs.test(Reg); |
291 | |
292 | |
293 | |
294 | for (MCSubRegIterator SRI(Reg, TRI, true); SRI.isValid(); ++SRI) { |
295 | unsigned SubregReg = *SRI; |
296 | DefIndices[SubregReg] = Count; |
297 | KillIndices[SubregReg] = ~0u; |
298 | Classes[SubregReg] = nullptr; |
299 | RegRefs.erase(SubregReg); |
300 | if (!Keep) |
301 | KeepRegs.reset(SubregReg); |
302 | } |
303 | |
304 | for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR) |
305 | Classes[*SR] = reinterpret_cast<TargetRegisterClass *>(-1); |
306 | } |
307 | } |
308 | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { |
309 | MachineOperand &MO = MI.getOperand(i); |
310 | if (!MO.isReg()) continue; |
311 | Register Reg = MO.getReg(); |
312 | if (Reg == 0) continue; |
313 | if (!MO.isUse()) continue; |
314 | |
315 | const TargetRegisterClass *NewRC = nullptr; |
316 | if (i < MI.getDesc().getNumOperands()) |
317 | NewRC = TII->getRegClass(MI.getDesc(), i, TRI, MF); |
318 | |
319 | |
320 | |
321 | if (!Classes[Reg] && NewRC) |
322 | Classes[Reg] = NewRC; |
323 | else if (!NewRC || Classes[Reg] != NewRC) |
324 | Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); |
325 | |
326 | RegRefs.insert(std::make_pair(Reg, &MO)); |
327 | |
328 | |
329 | |
330 | for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { |
331 | unsigned AliasReg = *AI; |
332 | if (KillIndices[AliasReg] == ~0u) { |
333 | KillIndices[AliasReg] = Count; |
334 | DefIndices[AliasReg] = ~0u; |
335 | } |
336 | } |
337 | } |
338 | } |
339 | |
340 | |
341 | |
342 | |
343 | |
344 | |
345 | |
346 | |
347 | |
348 | |
349 | |
350 | |
351 | bool |
352 | CriticalAntiDepBreaker::isNewRegClobberedByRefs(RegRefIter RegRefBegin, |
353 | RegRefIter RegRefEnd, |
354 | unsigned NewReg) { |
355 | for (RegRefIter I = RegRefBegin; I != RegRefEnd; ++I ) { |
356 | MachineOperand *RefOper = I->second; |
357 | |
358 | |
359 | |
360 | |
361 | if (RefOper->isDef() && RefOper->isEarlyClobber()) |
362 | return true; |
363 | |
364 | |
365 | MachineInstr *MI = RefOper->getParent(); |
366 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
367 | const MachineOperand &CheckOper = MI->getOperand(i); |
368 | |
369 | if (CheckOper.isRegMask() && CheckOper.clobbersPhysReg(NewReg)) |
370 | return true; |
371 | |
372 | if (!CheckOper.isReg() || !CheckOper.isDef() || |
373 | CheckOper.getReg() != NewReg) |
374 | continue; |
375 | |
376 | |
377 | |
378 | if (RefOper->isDef()) |
379 | return true; |
380 | |
381 | |
382 | |
383 | if (CheckOper.isEarlyClobber()) |
384 | return true; |
385 | |
386 | |
387 | |
388 | if (MI->isInlineAsm()) |
389 | return true; |
390 | } |
391 | } |
392 | return false; |
393 | } |
394 | |
395 | unsigned CriticalAntiDepBreaker:: |
396 | findSuitableFreeRegister(RegRefIter RegRefBegin, |
397 | RegRefIter RegRefEnd, |
398 | unsigned AntiDepReg, |
399 | unsigned LastNewReg, |
400 | const TargetRegisterClass *RC, |
401 | SmallVectorImpl<unsigned> &Forbid) { |
402 | ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(RC); |
403 | for (unsigned i = 0; i != Order.size(); ++i) { |
404 | unsigned NewReg = Order[i]; |
405 | |
406 | if (NewReg == AntiDepReg) continue; |
407 | |
408 | |
409 | |
410 | if (NewReg == LastNewReg) continue; |
411 | |
412 | |
413 | |
414 | if (isNewRegClobberedByRefs(RegRefBegin, RegRefEnd, NewReg)) continue; |
415 | |
416 | |
417 | assert(((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg] == ~0u)) |
418 | && "Kill and Def maps aren't consistent for AntiDepReg!"); |
419 | assert(((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u)) |
420 | && "Kill and Def maps aren't consistent for NewReg!"); |
421 | if (KillIndices[NewReg] != ~0u || |
422 | Classes[NewReg] == reinterpret_cast<TargetRegisterClass *>(-1) || |
423 | KillIndices[AntiDepReg] > DefIndices[NewReg]) |
424 | continue; |
425 | |
426 | bool Forbidden = false; |
427 | for (unsigned R : Forbid) |
428 | if (TRI->regsOverlap(NewReg, R)) { |
429 | Forbidden = true; |
430 | break; |
431 | } |
432 | if (Forbidden) continue; |
433 | return NewReg; |
434 | } |
435 | |
436 | |
437 | return 0; |
438 | } |
439 | |
440 | unsigned CriticalAntiDepBreaker:: |
441 | BreakAntiDependencies(const std::vector<SUnit> &SUnits, |
442 | MachineBasicBlock::iterator Begin, |
443 | MachineBasicBlock::iterator End, |
444 | unsigned InsertPosIndex, |
445 | DbgValueVector &DbgValues) { |
446 | |
447 | |
448 | if (SUnits.empty()) return 0; |
| 1 | Assuming the condition is false | |
|
| |
449 | |
450 | |
451 | |
452 | |
453 | |
454 | DenseMap<MachineInstr *, const SUnit *> MISUnitMap; |
455 | |
456 | |
457 | const SUnit *Max = nullptr; |
| 3 | | 'Max' initialized to a null pointer value | |
|
458 | for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { |
| 4 | | Assuming 'i' is equal to 'e' | |
|
| 5 | | Loop condition is false. Execution continues on line 464 | |
|
459 | const SUnit *SU = &SUnits[i]; |
460 | MISUnitMap[SU->getInstr()] = SU; |
461 | if (!Max || SU->getDepth() + SU->Latency > Max->getDepth() + Max->Latency) |
462 | Max = SU; |
463 | } |
464 | assert(Max && "Failed to find bottom of the critical path"); |
465 | |
466 | #ifndef NDEBUG |
467 | { |
468 | LLVM_DEBUG(dbgs() << "Critical path has total latency " |
469 | << (Max->getDepth() + Max->Latency) << "\n"); |
470 | LLVM_DEBUG(dbgs() << "Available regs:"); |
471 | for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) { |
472 | if (KillIndices[Reg] == ~0u) |
473 | LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI)); |
474 | } |
475 | LLVM_DEBUG(dbgs() << '\n'); |
476 | } |
477 | #endif |
478 | |
479 | |
480 | |
481 | const SUnit *CriticalPathSU = Max; |
| 6 | | 'CriticalPathSU' initialized to a null pointer value | |
|
482 | MachineInstr *CriticalPathMI = CriticalPathSU->getInstr(); |
| 7 | | Called C++ object pointer is null |
|
483 | |
484 | |
485 | |
486 | |
487 | |
488 | |
489 | |
490 | |
491 | |
492 | |
493 | |
494 | |
495 | |
496 | |
497 | |
498 | |
499 | |
500 | |
501 | |
502 | |
503 | |
504 | |
505 | |
506 | |
507 | |
508 | |
509 | |
510 | |
511 | |
512 | |
513 | |
514 | |
515 | |
516 | |
517 | |
518 | |
519 | |
520 | |
521 | |
522 | |
523 | |
524 | |
525 | std::vector<unsigned> LastNewReg(TRI->getNumRegs(), 0); |
526 | |
527 | |
528 | |
529 | |
530 | unsigned Broken = 0; |
531 | unsigned Count = InsertPosIndex - 1; |
532 | for (MachineBasicBlock::iterator I = End, E = Begin; I != E; --Count) { |
533 | MachineInstr &MI = *--I; |
534 | |
535 | |
536 | |
537 | |
538 | |
539 | |
540 | |
541 | if (MI.isDebugInstr() || MI.isKill()) |
542 | continue; |
543 | |
544 | |
545 | |
546 | |
547 | |
548 | |
549 | |
550 | |
551 | |
552 | |
553 | |
554 | |
555 | |
556 | |
557 | unsigned AntiDepReg = 0; |
558 | if (&MI == CriticalPathMI) { |
559 | if (const SDep *Edge = CriticalPathStep(CriticalPathSU)) { |
560 | const SUnit *NextSU = Edge->getSUnit(); |
561 | |
562 | |
563 | if (Edge->getKind() == SDep::Anti) { |
564 | AntiDepReg = Edge->getReg(); |
565 | assert(AntiDepReg != 0 && "Anti-dependence on reg0?"); |
566 | if (!MRI.isAllocatable(AntiDepReg)) |
567 | |
568 | AntiDepReg = 0; |
569 | else if (KeepRegs.test(AntiDepReg)) |
570 | |
571 | |
572 | AntiDepReg = 0; |
573 | else { |
574 | |
575 | |
576 | |
577 | |
578 | |
579 | |
580 | |
581 | |
582 | for (const SDep &P : CriticalPathSU->Preds) |
583 | if (P.getSUnit() == NextSU |
584 | ? (P.getKind() != SDep::Anti || P.getReg() != AntiDepReg) |
585 | : (P.getKind() == SDep::Data && |
586 | P.getReg() == AntiDepReg)) { |
587 | AntiDepReg = 0; |
588 | break; |
589 | } |
590 | } |
591 | } |
592 | CriticalPathSU = NextSU; |
593 | CriticalPathMI = CriticalPathSU->getInstr(); |
594 | } else { |
595 | |
596 | CriticalPathSU = nullptr; |
597 | CriticalPathMI = nullptr; |
598 | } |
599 | } |
600 | |
601 | PrescanInstruction(MI); |
602 | |
603 | SmallVector<unsigned, 2> ForbidRegs; |
604 | |
605 | |
606 | |
607 | |
608 | if (MI.isCall() || MI.hasExtraDefRegAllocReq() || TII->isPredicated(MI)) |
609 | |
610 | |
611 | AntiDepReg = 0; |
612 | else if (AntiDepReg) { |
613 | |
614 | |
615 | |
616 | |
617 | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { |
618 | MachineOperand &MO = MI.getOperand(i); |
619 | if (!MO.isReg()) continue; |
620 | Register Reg = MO.getReg(); |
621 | if (Reg == 0) continue; |
622 | if (MO.isUse() && TRI->regsOverlap(AntiDepReg, Reg)) { |
623 | AntiDepReg = 0; |
624 | break; |
625 | } |
626 | if (MO.isDef() && Reg != AntiDepReg) |
627 | ForbidRegs.push_back(Reg); |
628 | } |
629 | } |
630 | |
631 | |
632 | |
633 | const TargetRegisterClass *RC = AntiDepReg != 0 ? Classes[AntiDepReg] |
634 | : nullptr; |
635 | assert((AntiDepReg == 0 || RC != nullptr) && |
636 | "Register should be live if it's causing an anti-dependence!"); |
637 | if (RC == reinterpret_cast<TargetRegisterClass *>(-1)) |
638 | AntiDepReg = 0; |
639 | |
640 | |
641 | |
642 | |
643 | |
644 | if (AntiDepReg != 0) { |
645 | std::pair<std::multimap<unsigned, MachineOperand *>::iterator, |
646 | std::multimap<unsigned, MachineOperand *>::iterator> |
647 | Range = RegRefs.equal_range(AntiDepReg); |
648 | if (unsigned NewReg = findSuitableFreeRegister(Range.first, Range.second, |
649 | AntiDepReg, |
650 | LastNewReg[AntiDepReg], |
651 | RC, ForbidRegs)) { |
652 | LLVM_DEBUG(dbgs() << "Breaking anti-dependence edge on " |
653 | << printReg(AntiDepReg, TRI) << " with " |
654 | << RegRefs.count(AntiDepReg) << " references" |
655 | << " using " << printReg(NewReg, TRI) << "!\n"); |
656 | |
657 | |
658 | |
659 | for (std::multimap<unsigned, MachineOperand *>::iterator |
660 | Q = Range.first, QE = Range.second; Q != QE; ++Q) { |
661 | Q->second->setReg(NewReg); |
662 | |
663 | |
664 | |
665 | const SUnit *SU = MISUnitMap[Q->second->getParent()]; |
666 | if (!SU) continue; |
667 | UpdateDbgValues(DbgValues, Q->second->getParent(), |
668 | AntiDepReg, NewReg); |
669 | } |
670 | |
671 | |
672 | |
673 | |
674 | Classes[NewReg] = Classes[AntiDepReg]; |
675 | DefIndices[NewReg] = DefIndices[AntiDepReg]; |
676 | KillIndices[NewReg] = KillIndices[AntiDepReg]; |
677 | assert(((KillIndices[NewReg] == ~0u) != |
678 | (DefIndices[NewReg] == ~0u)) && |
679 | "Kill and Def maps aren't consistent for NewReg!"); |
680 | |
681 | Classes[AntiDepReg] = nullptr; |
682 | DefIndices[AntiDepReg] = KillIndices[AntiDepReg]; |
683 | KillIndices[AntiDepReg] = ~0u; |
684 | assert(((KillIndices[AntiDepReg] == ~0u) != |
685 | (DefIndices[AntiDepReg] == ~0u)) && |
686 | "Kill and Def maps aren't consistent for AntiDepReg!"); |
687 | |
688 | RegRefs.erase(AntiDepReg); |
689 | LastNewReg[AntiDepReg] = NewReg; |
690 | ++Broken; |
691 | } |
692 | } |
693 | |
694 | ScanInstruction(MI, Count); |
695 | } |
696 | |
697 | return Broken; |
698 | } |
699 | |
700 | AntiDepBreaker * |
701 | llvm::createCriticalAntiDepBreaker(MachineFunction &MFi, |
702 | const RegisterClassInfo &RCI) { |
703 | return new CriticalAntiDepBreaker(MFi, RCI); |
704 | } |