clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name InstrRefBasedImpl.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 static -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" -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 -stack-protector 2 -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/LiveDebugValues/InstrRefBasedImpl.cpp
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
14 | |
15 | |
16 | |
17 | |
18 | |
19 | |
20 | |
21 | |
22 | |
23 | |
24 | |
25 | |
26 | |
27 | |
28 | |
29 | |
30 | |
31 | |
32 | |
33 | |
34 | |
35 | |
36 | |
37 | |
38 | |
39 | |
40 | |
41 | |
42 | |
43 | |
44 | |
45 | |
46 | |
47 | |
48 | |
49 | |
50 | |
51 | |
52 | |
53 | |
54 | |
55 | |
56 | |
57 | |
58 | |
59 | |
60 | |
61 | |
62 | |
63 | |
64 | |
65 | |
66 | |
67 | |
68 | |
69 | |
70 | |
71 | |
72 | |
73 | |
74 | |
75 | |
76 | |
77 | |
78 | |
79 | |
80 | |
81 | |
82 | |
83 | |
84 | |
85 | |
86 | |
87 | |
88 | |
89 | |
90 | |
91 | |
92 | |
93 | |
94 | |
95 | |
96 | |
97 | |
98 | |
99 | |
100 | |
101 | |
102 | |
103 | |
104 | |
105 | |
106 | |
107 | |
108 | |
109 | |
110 | |
111 | |
112 | |
113 | |
114 | |
115 | |
116 | |
117 | |
118 | |
119 | |
120 | |
121 | |
122 | |
123 | |
124 | |
125 | |
126 | |
127 | |
128 | |
129 | |
130 | |
131 | |
132 | |
133 | |
134 | |
135 | |
136 | |
137 | |
138 | |
139 | |
140 | |
141 | |
142 | |
143 | |
144 | |
145 | |
146 | |
147 | |
148 | |
149 | #include "llvm/ADT/DenseMap.h" |
150 | #include "llvm/ADT/PostOrderIterator.h" |
151 | #include "llvm/ADT/STLExtras.h" |
152 | #include "llvm/ADT/SmallPtrSet.h" |
153 | #include "llvm/ADT/SmallSet.h" |
154 | #include "llvm/ADT/SmallVector.h" |
155 | #include "llvm/ADT/Statistic.h" |
156 | #include "llvm/ADT/UniqueVector.h" |
157 | #include "llvm/CodeGen/LexicalScopes.h" |
158 | #include "llvm/CodeGen/MachineBasicBlock.h" |
159 | #include "llvm/CodeGen/MachineFrameInfo.h" |
160 | #include "llvm/CodeGen/MachineFunction.h" |
161 | #include "llvm/CodeGen/MachineFunctionPass.h" |
162 | #include "llvm/CodeGen/MachineInstr.h" |
163 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
164 | #include "llvm/CodeGen/MachineInstrBundle.h" |
165 | #include "llvm/CodeGen/MachineMemOperand.h" |
166 | #include "llvm/CodeGen/MachineOperand.h" |
167 | #include "llvm/CodeGen/PseudoSourceValue.h" |
168 | #include "llvm/CodeGen/RegisterScavenging.h" |
169 | #include "llvm/CodeGen/TargetFrameLowering.h" |
170 | #include "llvm/CodeGen/TargetInstrInfo.h" |
171 | #include "llvm/CodeGen/TargetLowering.h" |
172 | #include "llvm/CodeGen/TargetPassConfig.h" |
173 | #include "llvm/CodeGen/TargetRegisterInfo.h" |
174 | #include "llvm/CodeGen/TargetSubtargetInfo.h" |
175 | #include "llvm/Config/llvm-config.h" |
176 | #include "llvm/IR/DIBuilder.h" |
177 | #include "llvm/IR/DebugInfoMetadata.h" |
178 | #include "llvm/IR/DebugLoc.h" |
179 | #include "llvm/IR/Function.h" |
180 | #include "llvm/IR/Module.h" |
181 | #include "llvm/InitializePasses.h" |
182 | #include "llvm/MC/MCRegisterInfo.h" |
183 | #include "llvm/Pass.h" |
184 | #include "llvm/Support/Casting.h" |
185 | #include "llvm/Support/Compiler.h" |
186 | #include "llvm/Support/Debug.h" |
187 | #include "llvm/Support/TypeSize.h" |
188 | #include "llvm/Support/raw_ostream.h" |
189 | #include "llvm/Target/TargetMachine.h" |
190 | #include "llvm/Transforms/Utils/SSAUpdaterImpl.h" |
191 | #include <algorithm> |
192 | #include <cassert> |
193 | #include <cstdint> |
194 | #include <functional> |
195 | #include <queue> |
196 | #include <tuple> |
197 | #include <utility> |
198 | #include <vector> |
199 | #include <limits.h> |
200 | #include <limits> |
201 | |
202 | #include "LiveDebugValues.h" |
203 | |
204 | using namespace llvm; |
205 | |
206 | |
207 | #undef DEBUG_TYPE |
208 | #define DEBUG_TYPE "livedebugvalues" |
209 | |
210 | |
211 | |
212 | static cl::opt<bool> EmulateOldLDV("emulate-old-livedebugvalues", cl::Hidden, |
213 | cl::desc("Act like old LiveDebugValues did"), |
214 | cl::init(false)); |
215 | |
216 | namespace { |
217 | |
218 | |
219 | |
220 | struct SpillLoc { |
221 | unsigned SpillBase; |
222 | StackOffset SpillOffset; |
223 | bool operator==(const SpillLoc &Other) const { |
224 | return std::make_pair(SpillBase, SpillOffset) == |
225 | std::make_pair(Other.SpillBase, Other.SpillOffset); |
226 | } |
227 | bool operator<(const SpillLoc &Other) const { |
228 | return std::make_tuple(SpillBase, SpillOffset.getFixed(), |
229 | SpillOffset.getScalable()) < |
230 | std::make_tuple(Other.SpillBase, Other.SpillOffset.getFixed(), |
231 | Other.SpillOffset.getScalable()); |
232 | } |
233 | }; |
234 | |
235 | class LocIdx { |
236 | unsigned Location; |
237 | |
238 | |
239 | |
240 | LocIdx() : Location(UINT_MAX) { } |
241 | |
242 | public: |
243 | #define NUM_LOC_BITS 24 |
244 | LocIdx(unsigned L) : Location(L) { |
245 | assert(L < (1 << NUM_LOC_BITS) && "Machine locations must fit in 24 bits"); |
246 | } |
247 | |
248 | static LocIdx MakeIllegalLoc() { |
249 | return LocIdx(); |
250 | } |
251 | |
252 | bool isIllegal() const { |
253 | return Location == UINT_MAX; |
254 | } |
255 | |
256 | uint64_t asU64() const { |
257 | return Location; |
258 | } |
259 | |
260 | bool operator==(unsigned L) const { |
261 | return Location == L; |
262 | } |
263 | |
264 | bool operator==(const LocIdx &L) const { |
265 | return Location == L.Location; |
266 | } |
267 | |
268 | bool operator!=(unsigned L) const { |
269 | return !(*this == L); |
270 | } |
271 | |
272 | bool operator!=(const LocIdx &L) const { |
273 | return !(*this == L); |
274 | } |
275 | |
276 | bool operator<(const LocIdx &Other) const { |
277 | return Location < Other.Location; |
278 | } |
279 | }; |
280 | |
281 | class LocIdxToIndexFunctor { |
282 | public: |
283 | using argument_type = LocIdx; |
284 | unsigned operator()(const LocIdx &L) const { |
285 | return L.asU64(); |
286 | } |
287 | }; |
288 | |
289 | |
290 | |
291 | |
292 | |
293 | |
294 | |
295 | |
296 | |
297 | |
298 | |
299 | class ValueIDNum { |
300 | uint64_t BlockNo : 20; |
301 | uint64_t InstNo : 20; |
302 | |
303 | uint64_t LocNo : NUM_LOC_BITS; |
304 | |
305 | public: |
306 | |
307 | |
308 | ValueIDNum() : BlockNo(0xFFFFF), |
309 | InstNo(0xFFFFF), |
310 | LocNo(0xFFFFFF) { } |
311 | |
312 | ValueIDNum(uint64_t Block, uint64_t Inst, uint64_t Loc) |
313 | : BlockNo(Block), InstNo(Inst), LocNo(Loc) { } |
314 | |
315 | ValueIDNum(uint64_t Block, uint64_t Inst, LocIdx Loc) |
316 | : BlockNo(Block), InstNo(Inst), LocNo(Loc.asU64()) { } |
317 | |
318 | uint64_t getBlock() const { return BlockNo; } |
319 | uint64_t getInst() const { return InstNo; } |
320 | uint64_t getLoc() const { return LocNo; } |
321 | bool isPHI() const { return InstNo == 0; } |
322 | |
323 | uint64_t asU64() const { |
324 | uint64_t TmpBlock = BlockNo; |
325 | uint64_t TmpInst = InstNo; |
326 | return TmpBlock << 44ull | TmpInst << NUM_LOC_BITS | LocNo; |
327 | } |
328 | |
329 | static ValueIDNum fromU64(uint64_t v) { |
330 | uint64_t L = (v & 0x3FFF); |
331 | return {v >> 44ull, ((v >> NUM_LOC_BITS) & 0xFFFFF), L}; |
332 | } |
333 | |
334 | bool operator<(const ValueIDNum &Other) const { |
335 | return asU64() < Other.asU64(); |
336 | } |
337 | |
338 | bool operator==(const ValueIDNum &Other) const { |
339 | return std::tie(BlockNo, InstNo, LocNo) == |
340 | std::tie(Other.BlockNo, Other.InstNo, Other.LocNo); |
341 | } |
342 | |
343 | bool operator!=(const ValueIDNum &Other) const { return !(*this == Other); } |
344 | |
345 | std::string asString(const std::string &mlocname) const { |
346 | return Twine("Value{bb: ") |
347 | .concat(Twine(BlockNo).concat( |
348 | Twine(", inst: ") |
349 | .concat((InstNo ? Twine(InstNo) : Twine("live-in")) |
350 | .concat(Twine(", loc: ").concat(Twine(mlocname))) |
351 | .concat(Twine("}"))))) |
352 | .str(); |
353 | } |
354 | |
355 | static ValueIDNum EmptyValue; |
356 | }; |
357 | |
358 | } |
359 | |
360 | namespace { |
361 | |
362 | |
363 | |
364 | class DbgValueProperties { |
365 | public: |
366 | DbgValueProperties(const DIExpression *DIExpr, bool Indirect) |
367 | : DIExpr(DIExpr), Indirect(Indirect) {} |
368 | |
369 | |
370 | DbgValueProperties(const MachineInstr &MI) { |
371 | assert(MI.isDebugValue()); |
372 | DIExpr = MI.getDebugExpression(); |
373 | Indirect = MI.getOperand(1).isImm(); |
374 | } |
375 | |
376 | bool operator==(const DbgValueProperties &Other) const { |
377 | return std::tie(DIExpr, Indirect) == std::tie(Other.DIExpr, Other.Indirect); |
378 | } |
379 | |
380 | bool operator!=(const DbgValueProperties &Other) const { |
381 | return !(*this == Other); |
382 | } |
383 | |
384 | const DIExpression *DIExpr; |
385 | bool Indirect; |
386 | }; |
387 | |
388 | |
389 | |
390 | |
391 | |
392 | |
393 | |
394 | |
395 | |
396 | |
397 | |
398 | |
399 | |
400 | |
401 | |
402 | |
403 | |
404 | |
405 | |
406 | |
407 | |
408 | |
409 | class MLocTracker { |
410 | public: |
411 | MachineFunction &MF; |
412 | const TargetInstrInfo &TII; |
413 | const TargetRegisterInfo &TRI; |
414 | const TargetLowering &TLI; |
415 | |
416 | |
417 | using LocToValueType = IndexedMap<ValueIDNum, LocIdxToIndexFunctor>; |
418 | |
419 | |
420 | |
421 | LocToValueType LocIdxToIDNum; |
422 | |
423 | |
424 | |
425 | |
426 | |
427 | |
428 | |
429 | |
430 | |
431 | std::vector<LocIdx> LocIDToLocIdx; |
432 | |
433 | |
434 | IndexedMap<unsigned, LocIdxToIndexFunctor> LocIdxToLocID; |
435 | |
436 | |
437 | |
438 | UniqueVector<SpillLoc> SpillLocs; |
439 | |
440 | |
441 | |
442 | unsigned CurBB; |
443 | |
444 | |
445 | unsigned NumRegs; |
446 | |
447 | |
448 | |
449 | |
450 | |
451 | SmallVector<std::pair<const MachineOperand *, unsigned>, 32> Masks; |
452 | |
453 | |
454 | |
455 | |
456 | |
457 | class MLocIterator { |
458 | LocToValueType &ValueMap; |
459 | LocIdx Idx; |
460 | |
461 | public: |
462 | class value_type { |
463 | public: |
464 | value_type(LocIdx Idx, ValueIDNum &Value) : Idx(Idx), Value(Value) { } |
465 | const LocIdx Idx; |
466 | ValueIDNum &Value; |
467 | }; |
468 | |
469 | MLocIterator(LocToValueType &ValueMap, LocIdx Idx) |
470 | : ValueMap(ValueMap), Idx(Idx) { } |
471 | |
472 | bool operator==(const MLocIterator &Other) const { |
473 | assert(&ValueMap == &Other.ValueMap); |
474 | return Idx == Other.Idx; |
475 | } |
476 | |
477 | bool operator!=(const MLocIterator &Other) const { |
478 | return !(*this == Other); |
479 | } |
480 | |
481 | void operator++() { |
482 | Idx = LocIdx(Idx.asU64() + 1); |
483 | } |
484 | |
485 | value_type operator*() { |
486 | return value_type(Idx, ValueMap[LocIdx(Idx)]); |
487 | } |
488 | }; |
489 | |
490 | MLocTracker(MachineFunction &MF, const TargetInstrInfo &TII, |
491 | const TargetRegisterInfo &TRI, const TargetLowering &TLI) |
492 | : MF(MF), TII(TII), TRI(TRI), TLI(TLI), |
493 | LocIdxToIDNum(ValueIDNum::EmptyValue), |
494 | LocIdxToLocID(0) { |
495 | NumRegs = TRI.getNumRegs(); |
496 | reset(); |
497 | LocIDToLocIdx.resize(NumRegs, LocIdx::MakeIllegalLoc()); |
498 | assert(NumRegs < (1u << NUM_LOC_BITS)); |
499 | |
500 | |
501 | |
502 | |
503 | Register SP = TLI.getStackPointerRegisterToSaveRestore(); |
504 | if (SP) { |
505 | unsigned ID = getLocID(SP, false); |
506 | (void)lookupOrTrackRegister(ID); |
507 | } |
508 | } |
509 | |
510 | |
511 | |
512 | unsigned getLocID(Register RegOrSpill, bool isSpill) { |
513 | return (isSpill) ? RegOrSpill.id() + NumRegs - 1 : RegOrSpill.id(); |
514 | } |
515 | |
516 | |
517 | ValueIDNum getNumAtPos(LocIdx Idx) const { |
518 | assert(Idx.asU64() < LocIdxToIDNum.size()); |
519 | return LocIdxToIDNum[Idx]; |
520 | } |
521 | |
522 | unsigned getNumLocs(void) const { return LocIdxToIDNum.size(); } |
523 | |
524 | |
525 | |
526 | |
527 | void setMPhis(unsigned NewCurBB) { |
528 | CurBB = NewCurBB; |
529 | for (auto Location : locations()) |
530 | Location.Value = {CurBB, 0, Location.Idx}; |
531 | } |
532 | |
533 | |
534 | |
535 | void loadFromArray(ValueIDNum *Locs, unsigned NewCurBB) { |
536 | CurBB = NewCurBB; |
537 | |
538 | |
539 | for (auto Location : locations()) |
540 | Location.Value = Locs[Location.Idx.asU64()]; |
541 | } |
542 | |
543 | |
544 | void reset(void) { |
545 | |
546 | |
547 | |
548 | Masks.clear(); |
549 | } |
550 | |
551 | |
552 | |
553 | void clear(void) { |
554 | reset(); |
555 | LocIDToLocIdx.clear(); |
556 | LocIdxToLocID.clear(); |
557 | LocIdxToIDNum.clear(); |
558 | |
559 | SpillLocs = decltype(SpillLocs)(); |
560 | |
561 | LocIDToLocIdx.resize(NumRegs, LocIdx::MakeIllegalLoc()); |
562 | } |
563 | |
564 | |
565 | void setMLoc(LocIdx L, ValueIDNum Num) { |
566 | assert(L.asU64() < LocIdxToIDNum.size()); |
567 | LocIdxToIDNum[L] = Num; |
568 | } |
569 | |
570 | |
571 | |
572 | LocIdx trackRegister(unsigned ID) { |
573 | assert(ID != 0); |
574 | LocIdx NewIdx = LocIdx(LocIdxToIDNum.size()); |
575 | LocIdxToIDNum.grow(NewIdx); |
576 | LocIdxToLocID.grow(NewIdx); |
577 | |
578 | |
579 | ValueIDNum ValNum = {CurBB, 0, NewIdx}; |
580 | |
581 | for (const auto &MaskPair : reverse(Masks)) { |
582 | if (MaskPair.first->clobbersPhysReg(ID)) { |
583 | |
584 | ValNum = {CurBB, MaskPair.second, NewIdx}; |
585 | break; |
586 | } |
587 | } |
588 | |
589 | LocIdxToIDNum[NewIdx] = ValNum; |
590 | LocIdxToLocID[NewIdx] = ID; |
591 | return NewIdx; |
592 | } |
593 | |
594 | LocIdx lookupOrTrackRegister(unsigned ID) { |
595 | LocIdx &Index = LocIDToLocIdx[ID]; |
596 | if (Index.isIllegal()) |
597 | Index = trackRegister(ID); |
598 | return Index; |
599 | } |
600 | |
601 | |
602 | |
603 | |
604 | void defReg(Register R, unsigned BB, unsigned Inst) { |
605 | unsigned ID = getLocID(R, false); |
606 | LocIdx Idx = lookupOrTrackRegister(ID); |
607 | ValueIDNum ValueID = {BB, Inst, Idx}; |
608 | LocIdxToIDNum[Idx] = ValueID; |
609 | } |
610 | |
611 | |
612 | |
613 | void setReg(Register R, ValueIDNum ValueID) { |
614 | unsigned ID = getLocID(R, false); |
615 | LocIdx Idx = lookupOrTrackRegister(ID); |
616 | LocIdxToIDNum[Idx] = ValueID; |
617 | } |
618 | |
619 | ValueIDNum readReg(Register R) { |
620 | unsigned ID = getLocID(R, false); |
621 | LocIdx Idx = lookupOrTrackRegister(ID); |
622 | return LocIdxToIDNum[Idx]; |
623 | } |
624 | |
625 | |
626 | |
627 | |
628 | |
629 | void wipeRegister(Register R) { |
630 | unsigned ID = getLocID(R, false); |
631 | LocIdx Idx = LocIDToLocIdx[ID]; |
632 | LocIdxToIDNum[Idx] = ValueIDNum::EmptyValue; |
633 | } |
634 | |
635 | |
636 | LocIdx getRegMLoc(Register R) { |
637 | unsigned ID = getLocID(R, false); |
638 | return LocIDToLocIdx[ID]; |
639 | } |
640 | |
641 | |
642 | |
643 | |
644 | void writeRegMask(const MachineOperand *MO, unsigned CurBB, unsigned InstID) { |
645 | |
646 | Register SP = TLI.getStackPointerRegisterToSaveRestore(); |
647 | |
648 | |
649 | |
650 | |
651 | for (auto Location : locations()) { |
652 | unsigned ID = LocIdxToLocID[Location.Idx]; |
653 | |
654 | if (ID < NumRegs && ID != SP && MO->clobbersPhysReg(ID)) |
655 | defReg(ID, CurBB, InstID); |
656 | } |
657 | Masks.push_back(std::make_pair(MO, InstID)); |
658 | } |
659 | |
660 | |
661 | LocIdx getOrTrackSpillLoc(SpillLoc L) { |
662 | unsigned SpillID = SpillLocs.idFor(L); |
663 | if (SpillID == 0) { |
664 | SpillID = SpillLocs.insert(L); |
665 | unsigned L = getLocID(SpillID, true); |
666 | LocIdx Idx = LocIdx(LocIdxToIDNum.size()); |
667 | LocIdxToIDNum.grow(Idx); |
668 | LocIdxToLocID.grow(Idx); |
669 | LocIDToLocIdx.push_back(Idx); |
670 | LocIdxToLocID[Idx] = L; |
671 | return Idx; |
672 | } else { |
673 | unsigned L = getLocID(SpillID, true); |
674 | LocIdx Idx = LocIDToLocIdx[L]; |
675 | return Idx; |
676 | } |
677 | } |
678 | |
679 | |
680 | void setSpill(SpillLoc L, ValueIDNum ValueID) { |
681 | LocIdx Idx = getOrTrackSpillLoc(L); |
682 | LocIdxToIDNum[Idx] = ValueID; |
683 | } |
684 | |
685 | |
686 | Optional<ValueIDNum> readSpill(SpillLoc L) { |
687 | unsigned SpillID = SpillLocs.idFor(L); |
688 | if (SpillID == 0) |
689 | return None; |
690 | |
691 | unsigned LocID = getLocID(SpillID, true); |
692 | LocIdx Idx = LocIDToLocIdx[LocID]; |
693 | return LocIdxToIDNum[Idx]; |
694 | } |
695 | |
696 | |
697 | |
698 | Optional<LocIdx> getSpillMLoc(SpillLoc L) { |
699 | unsigned SpillID = SpillLocs.idFor(L); |
700 | if (SpillID == 0) |
701 | return None; |
702 | unsigned LocNo = getLocID(SpillID, true); |
703 | return LocIDToLocIdx[LocNo]; |
704 | } |
705 | |
706 | |
707 | bool isSpill(LocIdx Idx) const { |
708 | return LocIdxToLocID[Idx] >= NumRegs; |
709 | } |
710 | |
711 | MLocIterator begin() { |
712 | return MLocIterator(LocIdxToIDNum, 0); |
713 | } |
714 | |
715 | MLocIterator end() { |
716 | return MLocIterator(LocIdxToIDNum, LocIdxToIDNum.size()); |
717 | } |
718 | |
719 | |
720 | iterator_range<MLocIterator> locations() { |
721 | return llvm::make_range(begin(), end()); |
722 | } |
723 | |
724 | std::string LocIdxToName(LocIdx Idx) const { |
725 | unsigned ID = LocIdxToLocID[Idx]; |
726 | if (ID >= NumRegs) |
727 | return Twine("slot ").concat(Twine(ID - NumRegs)).str(); |
728 | else |
729 | return TRI.getRegAsmName(ID).str(); |
730 | } |
731 | |
732 | std::string IDAsString(const ValueIDNum &Num) const { |
733 | std::string DefName = LocIdxToName(Num.getLoc()); |
734 | return Num.asString(DefName); |
735 | } |
736 | |
737 | LLVM_DUMP_METHOD |
738 | void dump() { |
739 | for (auto Location : locations()) { |
740 | std::string MLocName = LocIdxToName(Location.Value.getLoc()); |
741 | std::string DefName = Location.Value.asString(MLocName); |
742 | dbgs() << LocIdxToName(Location.Idx) << " --> " << DefName << "\n"; |
743 | } |
744 | } |
745 | |
746 | LLVM_DUMP_METHOD |
747 | void dump_mloc_map() { |
748 | for (auto Location : locations()) { |
749 | std::string foo = LocIdxToName(Location.Idx); |
750 | dbgs() << "Idx " << Location.Idx.asU64() << " " << foo << "\n"; |
751 | } |
752 | } |
753 | |
754 | |
755 | |
756 | |
757 | MachineInstrBuilder emitLoc(Optional<LocIdx> MLoc, const DebugVariable &Var, |
758 | const DbgValueProperties &Properties) { |
759 | DebugLoc DL = DILocation::get(Var.getVariable()->getContext(), 0, 0, |
760 | Var.getVariable()->getScope(), |
761 | const_cast<DILocation *>(Var.getInlinedAt())); |
762 | auto MIB = BuildMI(MF, DL, TII.get(TargetOpcode::DBG_VALUE)); |
763 | |
764 | const DIExpression *Expr = Properties.DIExpr; |
765 | if (!MLoc) { |
766 | |
767 | MIB.addReg(0, RegState::Debug); |
768 | MIB.addReg(0, RegState::Debug); |
769 | } else if (LocIdxToLocID[*MLoc] >= NumRegs) { |
770 | unsigned LocID = LocIdxToLocID[*MLoc]; |
771 | const SpillLoc &Spill = SpillLocs[LocID - NumRegs + 1]; |
772 | |
773 | auto *TRI = MF.getSubtarget().getRegisterInfo(); |
774 | Expr = TRI->prependOffsetExpression(Expr, DIExpression::ApplyOffset, |
775 | Spill.SpillOffset); |
776 | unsigned Base = Spill.SpillBase; |
777 | MIB.addReg(Base, RegState::Debug); |
778 | MIB.addImm(0); |
779 | } else { |
780 | unsigned LocID = LocIdxToLocID[*MLoc]; |
781 | MIB.addReg(LocID, RegState::Debug); |
782 | if (Properties.Indirect) |
783 | MIB.addImm(0); |
784 | else |
785 | MIB.addReg(0, RegState::Debug); |
786 | } |
787 | |
788 | MIB.addMetadata(Var.getVariable()); |
789 | MIB.addMetadata(Expr); |
790 | return MIB; |
791 | } |
792 | }; |
793 | |
794 | |
795 | |
796 | |
797 | |
798 | |
799 | class DbgValue { |
800 | public: |
801 | union { |
802 | |
803 | ValueIDNum ID; |
804 | |
805 | MachineOperand MO; |
806 | |
807 | unsigned BlockNo; |
808 | }; |
809 | |
810 | DbgValueProperties Properties; |
811 | |
812 | typedef enum { |
813 | Undef, |
814 | Def, |
815 | Const, |
816 | Proposed, |
817 | |
818 | NoVal |
819 | |
820 | } KindT; |
821 | |
822 | KindT Kind; |
823 | |
824 | DbgValue(const ValueIDNum &Val, const DbgValueProperties &Prop, KindT Kind) |
825 | : ID(Val), Properties(Prop), Kind(Kind) { |
826 | assert(Kind == Def || Kind == Proposed); |
827 | } |
828 | |
829 | DbgValue(unsigned BlockNo, const DbgValueProperties &Prop, KindT Kind) |
830 | : BlockNo(BlockNo), Properties(Prop), Kind(Kind) { |
831 | assert(Kind == NoVal); |
832 | } |
833 | |
834 | DbgValue(const MachineOperand &MO, const DbgValueProperties &Prop, KindT Kind) |
835 | : MO(MO), Properties(Prop), Kind(Kind) { |
836 | assert(Kind == Const); |
837 | } |
838 | |
839 | DbgValue(const DbgValueProperties &Prop, KindT Kind) |
840 | : Properties(Prop), Kind(Kind) { |
841 | assert(Kind == Undef && |
842 | "Empty DbgValue constructor must pass in Undef kind"); |
843 | } |
844 | |
845 | void dump(const MLocTracker *MTrack) const { |
846 | if (Kind == Const) { |
847 | MO.dump(); |
848 | } else if (Kind == NoVal) { |
849 | dbgs() << "NoVal(" << BlockNo << ")"; |
850 | } else if (Kind == Proposed) { |
851 | dbgs() << "VPHI(" << MTrack->IDAsString(ID) << ")"; |
852 | } else { |
853 | assert(Kind == Def); |
854 | dbgs() << MTrack->IDAsString(ID); |
855 | } |
856 | if (Properties.Indirect) |
857 | dbgs() << " indir"; |
858 | if (Properties.DIExpr) |
859 | dbgs() << " " << *Properties.DIExpr; |
860 | } |
861 | |
862 | bool operator==(const DbgValue &Other) const { |
863 | if (std::tie(Kind, Properties) != std::tie(Other.Kind, Other.Properties)) |
864 | return false; |
865 | else if (Kind == Proposed && ID != Other.ID) |
866 | return false; |
867 | else if (Kind == Def && ID != Other.ID) |
868 | return false; |
869 | else if (Kind == NoVal && BlockNo != Other.BlockNo) |
870 | return false; |
871 | else if (Kind == Const) |
872 | return MO.isIdenticalTo(Other.MO); |
873 | |
874 | return true; |
875 | } |
876 | |
877 | bool operator!=(const DbgValue &Other) const { return !(*this == Other); } |
878 | }; |
879 | |
880 | |
881 | |
882 | |
883 | using FragmentOfVar = |
884 | std::pair<const DILocalVariable *, DIExpression::FragmentInfo>; |
885 | using OverlapMap = |
886 | DenseMap<FragmentOfVar, SmallVector<DIExpression::FragmentInfo, 1>>; |
887 | |
888 | |
889 | |
890 | |
891 | |
892 | class VLocTracker { |
893 | public: |
894 | |
895 | |
896 | |
897 | |
898 | |
899 | |
900 | |
901 | |
902 | MapVector<DebugVariable, DbgValue> Vars; |
903 | DenseMap<DebugVariable, const DILocation *> Scopes; |
904 | MachineBasicBlock *MBB; |
905 | |
906 | public: |
907 | VLocTracker() {} |
908 | |
909 | void defVar(const MachineInstr &MI, const DbgValueProperties &Properties, |
910 | Optional<ValueIDNum> ID) { |
911 | assert(MI.isDebugValue() || MI.isDebugRef()); |
912 | DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(), |
913 | MI.getDebugLoc()->getInlinedAt()); |
914 | DbgValue Rec = (ID) ? DbgValue(*ID, Properties, DbgValue::Def) |
915 | : DbgValue(Properties, DbgValue::Undef); |
916 | |
917 | |
918 | auto Result = Vars.insert(std::make_pair(Var, Rec)); |
919 | if (!Result.second) |
920 | Result.first->second = Rec; |
921 | Scopes[Var] = MI.getDebugLoc().get(); |
922 | } |
923 | |
924 | void defVar(const MachineInstr &MI, const MachineOperand &MO) { |
925 | |
926 | assert(MI.isDebugValue()); |
927 | DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(), |
928 | MI.getDebugLoc()->getInlinedAt()); |
929 | DbgValueProperties Properties(MI); |
930 | DbgValue Rec = DbgValue(MO, Properties, DbgValue::Const); |
931 | |
932 | |
933 | auto Result = Vars.insert(std::make_pair(Var, Rec)); |
934 | if (!Result.second) |
935 | Result.first->second = Rec; |
936 | Scopes[Var] = MI.getDebugLoc().get(); |
937 | } |
938 | }; |
939 | |
940 | |
941 | |
942 | |
943 | |
944 | |
945 | |
946 | |
947 | |
948 | |
949 | |
950 | |
951 | |
952 | |
953 | |
954 | |
955 | |
956 | class TransferTracker { |
957 | public: |
958 | const TargetInstrInfo *TII; |
959 | const TargetLowering *TLI; |
960 | |
961 | |
962 | |
963 | MLocTracker *MTracker; |
964 | MachineFunction &MF; |
965 | bool ShouldEmitDebugEntryValues; |
966 | |
967 | |
968 | |
969 | |
970 | struct Transfer { |
971 | MachineBasicBlock::instr_iterator Pos; |
972 | MachineBasicBlock *MBB; |
973 | SmallVector<MachineInstr *, 4> Insts; |
974 | }; |
975 | |
976 | struct LocAndProperties { |
977 | LocIdx Loc; |
978 | DbgValueProperties Properties; |
979 | }; |
980 | |
981 | |
982 | SmallVector<Transfer, 32> Transfers; |
983 | |
984 | |
985 | |
986 | |
987 | |
988 | std::vector<ValueIDNum> VarLocs; |
989 | |
990 | |
991 | |
992 | |
993 | std::map<LocIdx, SmallSet<DebugVariable, 4>> ActiveMLocs; |
994 | |
995 | |
996 | |
997 | |
998 | DenseMap<DebugVariable, LocAndProperties> ActiveVLocs; |
999 | |
1000 | |
1001 | SmallVector<MachineInstr *, 4> PendingDbgValues; |
1002 | |
1003 | |
1004 | |
1005 | |
1006 | struct UseBeforeDef { |
1007 | |
1008 | ValueIDNum ID; |
1009 | |
1010 | DebugVariable Var; |
1011 | |
1012 | DbgValueProperties Properties; |
1013 | }; |
1014 | |
1015 | |
1016 | |
1017 | DenseMap<unsigned, SmallVector<UseBeforeDef, 1>> UseBeforeDefs; |
1018 | |
1019 | |
1020 | |
1021 | |
1022 | DenseSet<DebugVariable> UseBeforeDefVariables; |
1023 | |
1024 | const TargetRegisterInfo &TRI; |
1025 | const BitVector &CalleeSavedRegs; |
1026 | |
1027 | TransferTracker(const TargetInstrInfo *TII, MLocTracker *MTracker, |
1028 | MachineFunction &MF, const TargetRegisterInfo &TRI, |
1029 | const BitVector &CalleeSavedRegs, const TargetPassConfig &TPC) |
1030 | : TII(TII), MTracker(MTracker), MF(MF), TRI(TRI), |
1031 | CalleeSavedRegs(CalleeSavedRegs) { |
1032 | TLI = MF.getSubtarget().getTargetLowering(); |
1033 | auto &TM = TPC.getTM<TargetMachine>(); |
1034 | ShouldEmitDebugEntryValues = TM.Options.ShouldEmitDebugEntryValues(); |
1035 | } |
1036 | |
1037 | |
1038 | |
1039 | |
1040 | |
1041 | |
1042 | |
1043 | void loadInlocs(MachineBasicBlock &MBB, ValueIDNum *MLocs, |
1044 | SmallVectorImpl<std::pair<DebugVariable, DbgValue>> &VLocs, |
1045 | unsigned NumLocs) { |
1046 | ActiveMLocs.clear(); |
1047 | ActiveVLocs.clear(); |
1048 | VarLocs.clear(); |
1049 | VarLocs.reserve(NumLocs); |
1050 | UseBeforeDefs.clear(); |
1051 | UseBeforeDefVariables.clear(); |
1052 | |
1053 | auto isCalleeSaved = [&](LocIdx L) { |
1054 | unsigned Reg = MTracker->LocIdxToLocID[L]; |
1055 | if (Reg >= MTracker->NumRegs) |
1056 | return false; |
1057 | for (MCRegAliasIterator RAI(Reg, &TRI, true); RAI.isValid(); ++RAI) |
1058 | if (CalleeSavedRegs.test(*RAI)) |
1059 | return true; |
1060 | return false; |
1061 | }; |
1062 | |
1063 | |
1064 | std::map<ValueIDNum, LocIdx> ValueToLoc; |
1065 | |
1066 | |
1067 | |
1068 | |
1069 | for (auto Location : MTracker->locations()) { |
1070 | LocIdx Idx = Location.Idx; |
1071 | ValueIDNum &VNum = MLocs[Idx.asU64()]; |
1072 | VarLocs.push_back(VNum); |
1073 | auto it = ValueToLoc.find(VNum); |
1074 | |
1075 | |
1076 | |
1077 | |
1078 | if (it == ValueToLoc.end() || MTracker->isSpill(it->second) || |
1079 | (!isCalleeSaved(it->second) && isCalleeSaved(Idx.asU64()))) { |
1080 | |
1081 | auto PrefLocRes = ValueToLoc.insert(std::make_pair(VNum, Idx)); |
1082 | if (!PrefLocRes.second) |
1083 | PrefLocRes.first->second = Idx; |
1084 | } |
1085 | } |
1086 | |
1087 | |
1088 | for (auto Var : VLocs) { |
1089 | if (Var.second.Kind == DbgValue::Const) { |
1090 | PendingDbgValues.push_back( |
1091 | emitMOLoc(Var.second.MO, Var.first, Var.second.Properties)); |
1092 | continue; |
1093 | } |
1094 | |
1095 | |
1096 | const ValueIDNum &Num = Var.second.ID; |
1097 | auto ValuesPreferredLoc = ValueToLoc.find(Num); |
1098 | if (ValuesPreferredLoc == ValueToLoc.end()) { |
1099 | |
1100 | |
1101 | if (Num.getBlock() == (unsigned)MBB.getNumber() && !Num.isPHI()) |
1102 | addUseBeforeDef(Var.first, Var.second.Properties, Num); |
1103 | else |
1104 | recoverAsEntryValue(Var.first, Var.second.Properties, Num); |
1105 | continue; |
1106 | } |
1107 | |
1108 | LocIdx M = ValuesPreferredLoc->second; |
1109 | auto NewValue = LocAndProperties{M, Var.second.Properties}; |
1110 | auto Result = ActiveVLocs.insert(std::make_pair(Var.first, NewValue)); |
1111 | if (!Result.second) |
1112 | Result.first->second = NewValue; |
1113 | ActiveMLocs[M].insert(Var.first); |
1114 | PendingDbgValues.push_back( |
1115 | MTracker->emitLoc(M, Var.first, Var.second.Properties)); |
1116 | } |
1117 | flushDbgValues(MBB.begin(), &MBB); |
1118 | } |
1119 | |
1120 | |
1121 | |
1122 | void addUseBeforeDef(const DebugVariable &Var, |
1123 | const DbgValueProperties &Properties, ValueIDNum ID) { |
1124 | UseBeforeDef UBD = {ID, Var, Properties}; |
1125 | UseBeforeDefs[ID.getInst()].push_back(UBD); |
1126 | UseBeforeDefVariables.insert(Var); |
1127 | } |
1128 | |
1129 | |
1130 | |
1131 | |
1132 | |
1133 | void checkInstForNewValues(unsigned Inst, MachineBasicBlock::iterator pos) { |
1134 | auto MIt = UseBeforeDefs.find(Inst); |
1135 | if (MIt == UseBeforeDefs.end()) |
1136 | return; |
1137 | |
1138 | for (auto &Use : MIt->second) { |
1139 | LocIdx L = Use.ID.getLoc(); |
1140 | |
1141 | |
1142 | |
1143 | |
1144 | |
1145 | if (MTracker->LocIdxToIDNum[L] != Use.ID) |
1146 | continue; |
1147 | |
1148 | |
1149 | |
1150 | if (!UseBeforeDefVariables.count(Use.Var)) |
1151 | continue; |
1152 | |
1153 | PendingDbgValues.push_back(MTracker->emitLoc(L, Use.Var, Use.Properties)); |
1154 | } |
1155 | flushDbgValues(pos, nullptr); |
1156 | } |
1157 | |
1158 | |
1159 | void flushDbgValues(MachineBasicBlock::iterator Pos, MachineBasicBlock *MBB) { |
1160 | if (PendingDbgValues.size() == 0) |
1161 | return; |
1162 | |
1163 | |
1164 | MachineBasicBlock::instr_iterator BundleStart; |
1165 | if (MBB && Pos == MBB->begin()) |
1166 | BundleStart = MBB->instr_begin(); |
1167 | else |
1168 | BundleStart = getBundleStart(Pos->getIterator()); |
1169 | |
1170 | Transfers.push_back({BundleStart, MBB, PendingDbgValues}); |
1171 | PendingDbgValues.clear(); |
1172 | } |
1173 | |
1174 | bool isEntryValueVariable(const DebugVariable &Var, |
1175 | const DIExpression *Expr) const { |
1176 | if (!Var.getVariable()->isParameter()) |
1177 | return false; |
1178 | |
1179 | if (Var.getInlinedAt()) |
1180 | return false; |
1181 | |
1182 | if (Expr->getNumElements() > 0) |
1183 | return false; |
1184 | |
1185 | return true; |
1186 | } |
1187 | |
1188 | bool isEntryValueValue(const ValueIDNum &Val) const { |
1189 | |
1190 | if (Val.getBlock() || !Val.isPHI()) |
1191 | return false; |
1192 | |
1193 | |
1194 | if (MTracker->isSpill(Val.getLoc())) |
1195 | return false; |
1196 | |
1197 | Register SP = TLI->getStackPointerRegisterToSaveRestore(); |
1198 | Register FP = TRI.getFrameRegister(MF); |
1199 | Register Reg = MTracker->LocIdxToLocID[Val.getLoc()]; |
1200 | return Reg != SP && Reg != FP; |
1201 | } |
1202 | |
1203 | bool recoverAsEntryValue(const DebugVariable &Var, DbgValueProperties &Prop, |
1204 | const ValueIDNum &Num) { |
1205 | |
1206 | |
1207 | if (!ShouldEmitDebugEntryValues) |
1208 | return false; |
1209 | |
1210 | |
1211 | if (!isEntryValueVariable(Var, Prop.DIExpr)) |
1212 | return false; |
1213 | |
1214 | |
1215 | if (!isEntryValueValue(Num)) |
1216 | return false; |
1217 | |
1218 | |
1219 | DIExpression *NewExpr = |
1220 | DIExpression::prepend(Prop.DIExpr, DIExpression::EntryValue); |
1221 | Register Reg = MTracker->LocIdxToLocID[Num.getLoc()]; |
1222 | MachineOperand MO = MachineOperand::CreateReg(Reg, false); |
1223 | MO.setIsDebug(true); |
1224 | |
1225 | PendingDbgValues.push_back(emitMOLoc(MO, Var, {NewExpr, Prop.Indirect})); |
1226 | return true; |
1227 | } |
1228 | |
1229 | |
1230 | void redefVar(const MachineInstr &MI) { |
1231 | DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(), |
1232 | MI.getDebugLoc()->getInlinedAt()); |
1233 | DbgValueProperties Properties(MI); |
1234 | |
1235 | const MachineOperand &MO = MI.getOperand(0); |
1236 | |
1237 | |
1238 | if (!MO.isReg() || MO.getReg() == 0) { |
1239 | auto It = ActiveVLocs.find(Var); |
1240 | if (It != ActiveVLocs.end()) { |
1241 | ActiveMLocs[It->second.Loc].erase(Var); |
1242 | ActiveVLocs.erase(It); |
1243 | } |
1244 | |
1245 | UseBeforeDefVariables.erase(Var); |
1246 | return; |
1247 | } |
1248 | |
1249 | Register Reg = MO.getReg(); |
1250 | LocIdx NewLoc = MTracker->getRegMLoc(Reg); |
1251 | redefVar(MI, Properties, NewLoc); |
1252 | } |
1253 | |
1254 | |
1255 | |
1256 | |
1257 | void redefVar(const MachineInstr &MI, const DbgValueProperties &Properties, |
1258 | Optional<LocIdx> OptNewLoc) { |
1259 | DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(), |
1260 | MI.getDebugLoc()->getInlinedAt()); |
1261 | |
1262 | UseBeforeDefVariables.erase(Var); |
1263 | |
1264 | |
1265 | auto It = ActiveVLocs.find(Var); |
1266 | if (It != ActiveVLocs.end()) |
1267 | ActiveMLocs[It->second.Loc].erase(Var); |
1268 | |
1269 | |
1270 | if (!OptNewLoc) |
1271 | return; |
1272 | LocIdx NewLoc = *OptNewLoc; |
1273 | |
1274 | |
1275 | |
1276 | |
1277 | if (MTracker->getNumAtPos(NewLoc) != VarLocs[NewLoc.asU64()]) { |
1278 | for (auto &P : ActiveMLocs[NewLoc]) { |
1279 | ActiveVLocs.erase(P); |
1280 | } |
1281 | ActiveMLocs[NewLoc.asU64()].clear(); |
1282 | VarLocs[NewLoc.asU64()] = MTracker->getNumAtPos(NewLoc); |
1283 | } |
1284 | |
1285 | ActiveMLocs[NewLoc].insert(Var); |
1286 | if (It == ActiveVLocs.end()) { |
1287 | ActiveVLocs.insert( |
1288 | std::make_pair(Var, LocAndProperties{NewLoc, Properties})); |
1289 | } else { |
1290 | It->second.Loc = NewLoc; |
1291 | It->second.Properties = Properties; |
1292 | } |
1293 | } |
1294 | |
1295 | |
1296 | |
1297 | |
1298 | |
1299 | void clobberMloc(LocIdx MLoc, MachineBasicBlock::iterator Pos, |
1300 | bool MakeUndef = true) { |
1301 | auto ActiveMLocIt = ActiveMLocs.find(MLoc); |
1302 | if (ActiveMLocIt == ActiveMLocs.end()) |
1303 | return; |
1304 | |
1305 | |
1306 | ValueIDNum OldValue = VarLocs[MLoc.asU64()]; |
1307 | VarLocs[MLoc.asU64()] = ValueIDNum::EmptyValue; |
1308 | |
1309 | |
1310 | |
1311 | Optional<LocIdx> NewLoc = None; |
1312 | for (auto Loc : MTracker->locations()) |
1313 | if (Loc.Value == OldValue) |
1314 | NewLoc = Loc.Idx; |
1315 | |
1316 | |
1317 | |
1318 | if (!NewLoc && !MakeUndef) { |
1319 | |
1320 | for (auto &Var : ActiveMLocIt->second) { |
1321 | auto &Prop = ActiveVLocs.find(Var)->second.Properties; |
1322 | recoverAsEntryValue(Var, Prop, OldValue); |
1323 | } |
1324 | flushDbgValues(Pos, nullptr); |
1325 | return; |
1326 | } |
1327 | |
1328 | |
1329 | DenseSet<DebugVariable> NewMLocs; |
1330 | for (auto &Var : ActiveMLocIt->second) { |
1331 | auto ActiveVLocIt = ActiveVLocs.find(Var); |
1332 | |
1333 | |
1334 | |
1335 | const DIExpression *Expr = ActiveVLocIt->second.Properties.DIExpr; |
1336 | DbgValueProperties Properties(Expr, false); |
1337 | PendingDbgValues.push_back(MTracker->emitLoc(NewLoc, Var, Properties)); |
1338 | |
1339 | |
1340 | |
1341 | if (!NewLoc) { |
1342 | ActiveVLocs.erase(ActiveVLocIt); |
1343 | } else { |
1344 | ActiveVLocIt->second.Loc = *NewLoc; |
1345 | NewMLocs.insert(Var); |
1346 | } |
1347 | } |
1348 | |
1349 | |
1350 | if (!NewMLocs.empty()) |
1351 | for (auto &Var : NewMLocs) |
1352 | ActiveMLocs[*NewLoc].insert(Var); |
1353 | |
1354 | |
1355 | |
1356 | if (NewLoc) |
1357 | VarLocs[NewLoc->asU64()] = OldValue; |
1358 | |
1359 | flushDbgValues(Pos, nullptr); |
1360 | |
1361 | ActiveMLocIt->second.clear(); |
1362 | } |
1363 | |
1364 | |
1365 | |
1366 | |
1367 | void transferMlocs(LocIdx Src, LocIdx Dst, MachineBasicBlock::iterator Pos) { |
1368 | |
1369 | |
1370 | if (VarLocs[Src.asU64()] != MTracker->getNumAtPos(Src)) |
1371 | return; |
1372 | |
1373 | |
1374 | |
1375 | ActiveMLocs[Dst] = ActiveMLocs[Src]; |
1376 | VarLocs[Dst.asU64()] = VarLocs[Src.asU64()]; |
1377 | |
1378 | |
1379 | for (auto &Var : ActiveMLocs[Src]) { |
1380 | auto ActiveVLocIt = ActiveVLocs.find(Var); |
1381 | assert(ActiveVLocIt != ActiveVLocs.end()); |
1382 | ActiveVLocIt->second.Loc = Dst; |
1383 | |
1384 | assert(Dst != 0); |
1385 | MachineInstr *MI = |
1386 | MTracker->emitLoc(Dst, Var, ActiveVLocIt->second.Properties); |
1387 | PendingDbgValues.push_back(MI); |
1388 | } |
1389 | ActiveMLocs[Src].clear(); |
1390 | flushDbgValues(Pos, nullptr); |
1391 | |
1392 | |
1393 | |
1394 | if (EmulateOldLDV) |
1395 | VarLocs[Src.asU64()] = ValueIDNum::EmptyValue; |
1396 | } |
1397 | |
1398 | MachineInstrBuilder emitMOLoc(const MachineOperand &MO, |
1399 | const DebugVariable &Var, |
1400 | const DbgValueProperties &Properties) { |
1401 | DebugLoc DL = DILocation::get(Var.getVariable()->getContext(), 0, 0, |
1402 | Var.getVariable()->getScope(), |
1403 | const_cast<DILocation *>(Var.getInlinedAt())); |
1404 | auto MIB = BuildMI(MF, DL, TII->get(TargetOpcode::DBG_VALUE)); |
1405 | MIB.add(MO); |
1406 | if (Properties.Indirect) |
1407 | MIB.addImm(0); |
1408 | else |
1409 | MIB.addReg(0); |
1410 | MIB.addMetadata(Var.getVariable()); |
1411 | MIB.addMetadata(Properties.DIExpr); |
1412 | return MIB; |
1413 | } |
1414 | }; |
1415 | |
1416 | class InstrRefBasedLDV : public LDVImpl { |
1417 | private: |
1418 | using FragmentInfo = DIExpression::FragmentInfo; |
1419 | using OptFragmentInfo = Optional<DIExpression::FragmentInfo>; |
1420 | |
1421 | |
1422 | |
1423 | using VarToFragments = |
1424 | DenseMap<const DILocalVariable *, SmallSet<FragmentInfo, 4>>; |
1425 | |
1426 | |
1427 | |
1428 | using MLocTransferMap = std::map<LocIdx, ValueIDNum>; |
1429 | |
1430 | |
1431 | |
1432 | using LiveIdxT = |
1433 | DenseMap<const MachineBasicBlock *, DenseMap<DebugVariable, DbgValue> *>; |
1434 | |
1435 | using VarAndLoc = std::pair<DebugVariable, DbgValue>; |
1436 | |
1437 | |
1438 | using InValueT = std::pair<MachineBasicBlock *, DbgValue *>; |
1439 | |
1440 | |
1441 | |
1442 | using LiveInsT = SmallVector<SmallVector<VarAndLoc, 8>, 8>; |
1443 | |
1444 | const TargetRegisterInfo *TRI; |
1445 | const TargetInstrInfo *TII; |
1446 | const TargetFrameLowering *TFI; |
1447 | const MachineFrameInfo *MFI; |
1448 | BitVector CalleeSavedRegs; |
1449 | LexicalScopes LS; |
1450 | TargetPassConfig *TPC; |
1451 | |
1452 | |
1453 | |
1454 | MLocTracker *MTracker; |
1455 | |
1456 | |
1457 | unsigned CurBB; |
1458 | |
1459 | |
1460 | unsigned CurInst; |
1461 | |
1462 | |
1463 | |
1464 | |
1465 | VLocTracker *VTracker; |
1466 | |
1467 | |
1468 | |
1469 | |
1470 | TransferTracker *TTracker; |
1471 | |
1472 | |
1473 | |
1474 | SmallPtrSet<const MachineBasicBlock *, 16> ArtificialBlocks; |
1475 | |
1476 | |
1477 | DenseMap<unsigned int, MachineBasicBlock *> OrderToBB; |
1478 | DenseMap<MachineBasicBlock *, unsigned int> BBToOrder; |
1479 | DenseMap<unsigned, unsigned> BBNumToRPO; |
1480 | |
1481 | |
1482 | using InstAndNum = std::pair<const MachineInstr *, unsigned>; |
1483 | |
1484 | |
1485 | |
1486 | std::map<uint64_t, InstAndNum> DebugInstrNumToInstr; |
1487 | |
1488 | |
1489 | class DebugPHIRecord { |
1490 | public: |
1491 | uint64_t InstrNum; |
1492 | MachineBasicBlock *MBB; |
1493 | ValueIDNum ValueRead; |
1494 | LocIdx ReadLoc; |
1495 | |
1496 | operator unsigned() const { return InstrNum; } |
1497 | }; |
1498 | |
1499 | |
1500 | |
1501 | |
1502 | |
1503 | SmallVector<DebugPHIRecord, 32> DebugPHINumToValue; |
1504 | |
1505 | |
1506 | OverlapMap OverlapFragments; |
1507 | VarToFragments SeenFragments; |
1508 | |
1509 | |
1510 | bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF); |
1511 | |
1512 | |
1513 | |
1514 | |
1515 | |
1516 | |
1517 | |
1518 | bool isLocationSpill(const MachineInstr &MI, MachineFunction *MF, |
1519 | unsigned &Reg); |
1520 | |
1521 | |
1522 | |
1523 | Optional<SpillLoc> isRestoreInstruction(const MachineInstr &MI, |
1524 | MachineFunction *MF, unsigned &Reg); |
1525 | |
1526 | |
1527 | |
1528 | SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI); |
1529 | |
1530 | |
1531 | void process(MachineInstr &MI, ValueIDNum **MLiveOuts = nullptr, |
1532 | ValueIDNum **MLiveIns = nullptr); |
1533 | |
1534 | |
1535 | |
1536 | bool transferDebugValue(const MachineInstr &MI); |
1537 | |
1538 | |
1539 | |
1540 | bool transferDebugInstrRef(MachineInstr &MI, ValueIDNum **MLiveOuts, |
1541 | ValueIDNum **MLiveIns); |
1542 | |
1543 | |
1544 | |
1545 | |
1546 | bool transferDebugPHI(MachineInstr &MI); |
1547 | |
1548 | |
1549 | |
1550 | bool transferRegisterCopy(MachineInstr &MI); |
1551 | |
1552 | |
1553 | |
1554 | bool transferSpillOrRestoreInst(MachineInstr &MI); |
1555 | |
1556 | |
1557 | void transferRegisterDef(MachineInstr &MI); |
1558 | |
1559 | |
1560 | |
1561 | void performCopy(Register Src, Register Dst); |
1562 | |
1563 | void accumulateFragmentMap(MachineInstr &MI); |
1564 | |
1565 | |
1566 | |
1567 | |
1568 | |
1569 | |
1570 | |
1571 | |
1572 | Optional<ValueIDNum> resolveDbgPHIs(MachineFunction &MF, |
1573 | ValueIDNum **MLiveOuts, |
1574 | ValueIDNum **MLiveIns, MachineInstr &Here, |
1575 | uint64_t InstrNum); |
1576 | |
1577 | |
1578 | |
1579 | |
1580 | |
1581 | void |
1582 | produceMLocTransferFunction(MachineFunction &MF, |
1583 | SmallVectorImpl<MLocTransferMap> &MLocTransfer, |
1584 | unsigned MaxNumBlocks); |
1585 | |
1586 | |
1587 | |
1588 | |
1589 | |
1590 | |
1591 | void mlocDataflow(ValueIDNum **MInLocs, ValueIDNum **MOutLocs, |
1592 | SmallVectorImpl<MLocTransferMap> &MLocTransfer); |
1593 | |
1594 | |
1595 | |
1596 | |
1597 | |
1598 | |
1599 | |
1600 | |
1601 | std::tuple<bool, bool> |
1602 | mlocJoin(MachineBasicBlock &MBB, |
1603 | SmallPtrSet<const MachineBasicBlock *, 16> &Visited, |
1604 | ValueIDNum **OutLocs, ValueIDNum *InLocs); |
1605 | |
1606 | |
1607 | |
1608 | |
1609 | |
1610 | |
1611 | |
1612 | |
1613 | |
1614 | |
1615 | |
1616 | |
1617 | |
1618 | |
1619 | void vlocDataflow(const LexicalScope *Scope, const DILocation *DILoc, |
1620 | const SmallSet<DebugVariable, 4> &VarsWeCareAbout, |
1621 | SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks, |
1622 | LiveInsT &Output, ValueIDNum **MOutLocs, |
1623 | ValueIDNum **MInLocs, |
1624 | SmallVectorImpl<VLocTracker> &AllTheVLocs); |
1625 | |
1626 | |
1627 | |
1628 | |
1629 | |
1630 | |
1631 | |
1632 | |
1633 | |
1634 | |
1635 | std::tuple<bool, bool> |
1636 | vlocJoin(MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, LiveIdxT &VLOCInLocs, |
1637 | SmallPtrSet<const MachineBasicBlock *, 16> *VLOCVisited, |
1638 | unsigned BBNum, const SmallSet<DebugVariable, 4> &AllVars, |
1639 | ValueIDNum **MOutLocs, ValueIDNum **MInLocs, |
1640 | SmallPtrSet<const MachineBasicBlock *, 8> &InScopeBlocks, |
1641 | SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore, |
1642 | DenseMap<DebugVariable, DbgValue> &InLocsT); |
1643 | |
1644 | |
1645 | |
1646 | |
1647 | |
1648 | |
1649 | |
1650 | |
1651 | |
1652 | bool vlocDowngradeLattice(const MachineBasicBlock &MBB, |
1653 | const DbgValue &OldLiveInLocation, |
1654 | const SmallVectorImpl<InValueT> &Values, |
1655 | unsigned CurBlockRPONum); |
1656 | |
1657 | |
1658 | |
1659 | |
1660 | |
1661 | |
1662 | |
1663 | |
1664 | |
1665 | std::tuple<Optional<ValueIDNum>, bool> |
1666 | pickVPHILoc(MachineBasicBlock &MBB, const DebugVariable &Var, |
1667 | const LiveIdxT &LiveOuts, ValueIDNum **MOutLocs, |
1668 | ValueIDNum **MInLocs, |
1669 | const SmallVectorImpl<MachineBasicBlock *> &BlockOrders); |
1670 | |
1671 | |
1672 | |
1673 | |
1674 | |
1675 | |
1676 | |
1677 | |
1678 | void emitLocations(MachineFunction &MF, LiveInsT SavedLiveIns, |
1679 | ValueIDNum **MOutLocs, ValueIDNum **MInLocs, |
1680 | DenseMap<DebugVariable, unsigned> &AllVarsNumbering, |
1681 | const TargetPassConfig &TPC); |
1682 | |
1683 | |
1684 | |
1685 | void initialSetup(MachineFunction &MF); |
1686 | |
1687 | bool ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC) override; |
1688 | |
1689 | public: |
1690 | |
1691 | InstrRefBasedLDV(); |
1692 | |
1693 | LLVM_DUMP_METHOD |
1694 | void dump_mloc_transfer(const MLocTransferMap &mloc_transfer) const; |
1695 | |
1696 | bool isCalleeSaved(LocIdx L) { |
1697 | unsigned Reg = MTracker->LocIdxToLocID[L]; |
1698 | for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) |
1699 | if (CalleeSavedRegs.test(*RAI)) |
1700 | return true; |
1701 | return false; |
1702 | } |
1703 | }; |
1704 | |
1705 | } |
1706 | |
1707 | |
1708 | |
1709 | |
1710 | |
1711 | ValueIDNum ValueIDNum::EmptyValue = {UINT_MAX, UINT_MAX, UINT_MAX}; |
1712 | |
1713 | |
1714 | InstrRefBasedLDV::InstrRefBasedLDV() {} |
1715 | |
1716 | |
1717 | |
1718 | |
1719 | |
1720 | #ifndef NDEBUG |
1721 | |
1722 | |
1723 | #endif |
1724 | |
1725 | SpillLoc |
1726 | InstrRefBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) { |
1727 | assert(MI.hasOneMemOperand() && |
1728 | "Spill instruction does not have exactly one memory operand?"); |
1729 | auto MMOI = MI.memoperands_begin(); |
1730 | const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue(); |
1731 | assert(PVal->kind() == PseudoSourceValue::FixedStack && |
1732 | "Inconsistent memory operand in spill instruction"); |
1733 | int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex(); |
1734 | const MachineBasicBlock *MBB = MI.getParent(); |
1735 | Register Reg; |
1736 | StackOffset Offset = TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg); |
1737 | return {Reg, Offset}; |
1738 | } |
1739 | |
1740 | |
1741 | |
1742 | bool InstrRefBasedLDV::transferDebugValue(const MachineInstr &MI) { |
1743 | if (!MI.isDebugValue()) |
1744 | return false; |
1745 | |
1746 | const DILocalVariable *Var = MI.getDebugVariable(); |
1747 | const DIExpression *Expr = MI.getDebugExpression(); |
1748 | const DILocation *DebugLoc = MI.getDebugLoc(); |
1749 | const DILocation *InlinedAt = DebugLoc->getInlinedAt(); |
1750 | assert(Var->isValidLocationForIntrinsic(DebugLoc) && |
1751 | "Expected inlined-at fields to agree"); |
1752 | |
1753 | DebugVariable V(Var, Expr, InlinedAt); |
1754 | DbgValueProperties Properties(MI); |
1755 | |
1756 | |
1757 | |
1758 | auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get()); |
1759 | if (Scope == nullptr) |
1760 | return true; |
1761 | |
1762 | const MachineOperand &MO = MI.getOperand(0); |
1763 | |
1764 | |
1765 | |
1766 | if (MO.isReg() && MO.getReg() != 0) |
1767 | (void)MTracker->readReg(MO.getReg()); |
1768 | |
1769 | |
1770 | |
1771 | |
1772 | if (VTracker) { |
1773 | if (MO.isReg()) { |
1774 | |
1775 | |
1776 | if (MO.getReg()) |
1777 | VTracker->defVar(MI, Properties, MTracker->readReg(MO.getReg())); |
1778 | else |
1779 | VTracker->defVar(MI, Properties, None); |
1780 | } else if (MI.getOperand(0).isImm() || MI.getOperand(0).isFPImm() || |
1781 | MI.getOperand(0).isCImm()) { |
1782 | VTracker->defVar(MI, MI.getOperand(0)); |
1783 | } |
1784 | } |
1785 | |
1786 | |
1787 | |
1788 | if (TTracker) |
1789 | TTracker->redefVar(MI); |
1790 | return true; |
1791 | } |
1792 | |
1793 | bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI, |
1794 | ValueIDNum **MLiveOuts, |
1795 | ValueIDNum **MLiveIns) { |
1796 | if (!MI.isDebugRef()) |
1797 | return false; |
1798 | |
1799 | |
1800 | |
1801 | if (!VTracker) |
1802 | return false; |
1803 | |
1804 | unsigned InstNo = MI.getOperand(0).getImm(); |
1805 | unsigned OpNo = MI.getOperand(1).getImm(); |
1806 | |
1807 | const DILocalVariable *Var = MI.getDebugVariable(); |
1808 | const DIExpression *Expr = MI.getDebugExpression(); |
1809 | const DILocation *DebugLoc = MI.getDebugLoc(); |
1810 | const DILocation *InlinedAt = DebugLoc->getInlinedAt(); |
1811 | assert(Var->isValidLocationForIntrinsic(DebugLoc) && |
1812 | "Expected inlined-at fields to agree"); |
1813 | |
1814 | DebugVariable V(Var, Expr, InlinedAt); |
1815 | |
1816 | auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get()); |
1817 | if (Scope == nullptr) |
1818 | return true; |
1819 | |
1820 | const MachineFunction &MF = *MI.getParent()->getParent(); |
1821 | |
1822 | |
1823 | |
1824 | |
1825 | |
1826 | |
1827 | |
1828 | auto SoughtSub = |
1829 | MachineFunction::DebugSubstitution({InstNo, OpNo}, {0, 0}, 0); |
1830 | |
1831 | SmallVector<unsigned, 4> SeenSubregs; |
1832 | auto LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub); |
1833 | while (LowerBoundIt != MF.DebugValueSubstitutions.end() && |
1834 | LowerBoundIt->Src == SoughtSub.Src) { |
1835 | std::tie(InstNo, OpNo) = LowerBoundIt->Dest; |
1836 | SoughtSub.Src = LowerBoundIt->Dest; |
1837 | if (unsigned Subreg = LowerBoundIt->Subreg) |
1838 | SeenSubregs.push_back(Subreg); |
1839 | LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub); |
1840 | } |
1841 | |
1842 | |
1843 | |
1844 | Optional<ValueIDNum> NewID = None; |
1845 | |
1846 | |
1847 | |
1848 | auto InstrIt = DebugInstrNumToInstr.find(InstNo); |
1849 | auto PHIIt = std::lower_bound(DebugPHINumToValue.begin(), |
1850 | DebugPHINumToValue.end(), InstNo); |
1851 | if (InstrIt != DebugInstrNumToInstr.end()) { |
1852 | const MachineInstr &TargetInstr = *InstrIt->second.first; |
1853 | uint64_t BlockNo = TargetInstr.getParent()->getNumber(); |
1854 | |
1855 | |
1856 | assert(OpNo < TargetInstr.getNumOperands()); |
1857 | const MachineOperand &MO = TargetInstr.getOperand(OpNo); |
1858 | |
1859 | |
1860 | assert(MO.isReg() && MO.isDef()); |
1861 | |
1862 | unsigned LocID = MTracker->getLocID(MO.getReg(), false); |
1863 | LocIdx L = MTracker->LocIDToLocIdx[LocID]; |
1864 | NewID = ValueIDNum(BlockNo, InstrIt->second.second, L); |
1865 | } else if (PHIIt != DebugPHINumToValue.end() && PHIIt->InstrNum == InstNo) { |
1866 | |
1867 | |
1868 | NewID = resolveDbgPHIs(*MI.getParent()->getParent(), MLiveOuts, MLiveIns, |
1869 | MI, InstNo); |
1870 | } |
1871 | |
1872 | |
1873 | |
1874 | |
1875 | |
1876 | |
1877 | |
1878 | |
1879 | |
1880 | |
1881 | if (NewID && !SeenSubregs.empty()) { |
1882 | unsigned Offset = 0; |
1883 | unsigned Size = 0; |
1884 | |
1885 | |
1886 | |
1887 | |
1888 | |
1889 | for (unsigned Subreg : reverse(SeenSubregs)) { |
1890 | unsigned ThisSize = TRI->getSubRegIdxSize(Subreg); |
1891 | unsigned ThisOffset = TRI->getSubRegIdxOffset(Subreg); |
1892 | Offset += ThisOffset; |
1893 | Size = (Size == 0) ? ThisSize : std::min(Size, ThisSize); |
1894 | } |
1895 | |
1896 | |
1897 | |
1898 | |
1899 | |
1900 | LocIdx L = NewID->getLoc(); |
1901 | if (NewID && !MTracker->isSpill(L)) { |
1902 | |
1903 | |
1904 | Register Reg = MTracker->LocIdxToLocID[L]; |
1905 | const TargetRegisterClass *TRC = nullptr; |
1906 | for (auto *TRCI : TRI->regclasses()) |
1907 | if (TRCI->contains(Reg)) |
1908 | TRC = TRCI; |
1909 | assert(TRC && "Couldn't find target register class?"); |
1910 | |
1911 | |
1912 | |
1913 | unsigned MainRegSize = TRI->getRegSizeInBits(*TRC); |
1914 | if (Size != MainRegSize || Offset) { |
1915 | |
1916 | Register NewReg = 0; |
1917 | for (MCSubRegIterator SRI(Reg, TRI, false); SRI.isValid(); ++SRI) { |
1918 | unsigned Subreg = TRI->getSubRegIndex(Reg, *SRI); |
1919 | unsigned SubregSize = TRI->getSubRegIdxSize(Subreg); |
1920 | unsigned SubregOffset = TRI->getSubRegIdxOffset(Subreg); |
1921 | if (SubregSize == Size && SubregOffset == Offset) { |
1922 | NewReg = *SRI; |
1923 | break; |
1924 | } |
1925 | } |
1926 | |
1927 | |
1928 | if (!NewReg) { |
1929 | NewID = None; |
1930 | } else { |
1931 | |
1932 | |
1933 | LocIdx NewLoc = MTracker->lookupOrTrackRegister(NewReg); |
1934 | NewID = ValueIDNum(NewID->getBlock(), NewID->getInst(), NewLoc); |
1935 | } |
1936 | } |
1937 | } else { |
1938 | |
1939 | NewID = None; |
1940 | } |
1941 | } |
1942 | |
1943 | |
1944 | |
1945 | |
1946 | |
1947 | DbgValueProperties Properties(Expr, false); |
1948 | VTracker->defVar(MI, Properties, NewID); |
1949 | |
1950 | |
1951 | |
1952 | if (!TTracker) |
1953 | return true; |
1954 | |
1955 | |
1956 | |
1957 | Optional<LocIdx> FoundLoc = None; |
1958 | for (auto Location : MTracker->locations()) { |
1959 | LocIdx CurL = Location.Idx; |
1960 | ValueIDNum ID = MTracker->LocIdxToIDNum[CurL]; |
1961 | if (NewID && ID == NewID) { |
1962 | |
1963 | |
1964 | if (!FoundLoc) { |
1965 | FoundLoc = CurL; |
1966 | continue; |
1967 | } |
1968 | |
1969 | if (MTracker->isSpill(CurL)) |
1970 | FoundLoc = CurL; |
1971 | else if (!MTracker->isSpill(*FoundLoc) && |
1972 | !MTracker->isSpill(CurL) && |
1973 | !isCalleeSaved(*FoundLoc) && |
1974 | isCalleeSaved(CurL)) |
1975 | FoundLoc = CurL; |
1976 | } |
1977 | } |
1978 | |
1979 | |
1980 | TTracker->redefVar(MI, Properties, FoundLoc); |
1981 | |
1982 | |
1983 | |
1984 | if (!FoundLoc && NewID && NewID->getBlock() == CurBB && |
1985 | NewID->getInst() > CurInst) |
1986 | TTracker->addUseBeforeDef(V, {MI.getDebugExpression(), false}, *NewID); |
1987 | |
1988 | |
1989 | |
1990 | |
1991 | |
1992 | MachineInstr *DbgMI = MTracker->emitLoc(FoundLoc, V, Properties); |
1993 | TTracker->PendingDbgValues.push_back(DbgMI); |
1994 | TTracker->flushDbgValues(MI.getIterator(), nullptr); |
1995 | return true; |
1996 | } |
1997 | |
1998 | bool InstrRefBasedLDV::transferDebugPHI(MachineInstr &MI) { |
1999 | if (!MI.isDebugPHI()) |
2000 | return false; |
2001 | |
2002 | |
2003 | if (VTracker || TTracker) |
2004 | return true; |
2005 | |
2006 | |
2007 | |
2008 | const MachineOperand &MO = MI.getOperand(0); |
2009 | unsigned InstrNum = MI.getOperand(1).getImm(); |
2010 | |
2011 | if (MO.isReg()) { |
2012 | |
2013 | |
2014 | Register Reg = MO.getReg(); |
2015 | ValueIDNum Num = MTracker->readReg(Reg); |
2016 | auto PHIRec = DebugPHIRecord( |
2017 | {InstrNum, MI.getParent(), Num, MTracker->lookupOrTrackRegister(Reg)}); |
2018 | DebugPHINumToValue.push_back(PHIRec); |
2019 | } else { |
2020 | |
2021 | assert(MO.isFI()); |
2022 | unsigned FI = MO.getIndex(); |
2023 | |
2024 | |
2025 | |
2026 | if (MFI->isDeadObjectIndex(FI)) |
2027 | return true; |
2028 | |
2029 | |
2030 | Register Base; |
2031 | StackOffset Offs = TFI->getFrameIndexReference(*MI.getMF(), FI, Base); |
2032 | SpillLoc SL = {Base, Offs}; |
2033 | Optional<ValueIDNum> Num = MTracker->readSpill(SL); |
2034 | |
2035 | if (!Num) |
2036 | |
2037 | return true; |
2038 | |
2039 | |
2040 | auto DbgPHI = DebugPHIRecord( |
2041 | {InstrNum, MI.getParent(), *Num, *MTracker->getSpillMLoc(SL)}); |
2042 | DebugPHINumToValue.push_back(DbgPHI); |
2043 | } |
2044 | |
2045 | return true; |
2046 | } |
2047 | |
2048 | void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) { |
2049 | |
2050 | |
2051 | if (MI.isImplicitDef()) { |
2052 | |
2053 | |
2054 | |
2055 | |
2056 | ValueIDNum Num = MTracker->readReg(MI.getOperand(0).getReg()); |
2057 | |
2058 | if (Num.getLoc() != 0) |
2059 | return; |
2060 | |
2061 | } else if (MI.isMetaInstruction()) |
2062 | return; |
2063 | |
2064 | MachineFunction *MF = MI.getMF(); |
2065 | const TargetLowering *TLI = MF->getSubtarget().getTargetLowering(); |
2066 | Register SP = TLI->getStackPointerRegisterToSaveRestore(); |
2067 | |
2068 | |
2069 | |
2070 | |
2071 | SmallSet<uint32_t, 32> DeadRegs; |
2072 | SmallVector<const uint32_t *, 4> RegMasks; |
2073 | SmallVector<const MachineOperand *, 4> RegMaskPtrs; |
2074 | for (const MachineOperand &MO : MI.operands()) { |
2075 | |
2076 | if (MO.isReg() && MO.isDef() && MO.getReg() && |
2077 | Register::isPhysicalRegister(MO.getReg()) && |
2078 | !(MI.isCall() && MO.getReg() == SP)) { |
2079 | |
2080 | for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI) |
2081 | |
2082 | DeadRegs.insert(*RAI); |
2083 | } else if (MO.isRegMask()) { |
2084 | RegMasks.push_back(MO.getRegMask()); |
2085 | RegMaskPtrs.push_back(&MO); |
2086 | } |
2087 | } |
2088 | |
2089 | |
2090 | for (uint32_t DeadReg : DeadRegs) |
2091 | MTracker->defReg(DeadReg, CurBB, CurInst); |
2092 | |
2093 | for (auto *MO : RegMaskPtrs) |
2094 | MTracker->writeRegMask(MO, CurBB, CurInst); |
2095 | |
2096 | if (!TTracker) |
2097 | return; |
2098 | |
2099 | |
2100 | |
2101 | |
2102 | |
2103 | |
2104 | for (uint32_t DeadReg : DeadRegs) { |
2105 | LocIdx Loc = MTracker->lookupOrTrackRegister(DeadReg); |
2106 | TTracker->clobberMloc(Loc, MI.getIterator(), false); |
2107 | } |
2108 | |
2109 | |
2110 | |
2111 | for (auto L : MTracker->locations()) { |
2112 | |
2113 | if (MTracker->isSpill(L.Idx)) |
2114 | continue; |
2115 | |
2116 | Register Reg = MTracker->LocIdxToLocID[L.Idx]; |
2117 | for (auto *MO : RegMaskPtrs) |
2118 | if (MO->clobbersPhysReg(Reg)) |
2119 | TTracker->clobberMloc(L.Idx, MI.getIterator(), false); |
2120 | } |
2121 | } |
2122 | |
2123 | void InstrRefBasedLDV::performCopy(Register SrcRegNum, Register DstRegNum) { |
2124 | ValueIDNum SrcValue = MTracker->readReg(SrcRegNum); |
2125 | |
2126 | MTracker->setReg(DstRegNum, SrcValue); |
2127 | |
2128 | |
2129 | |
2130 | |
2131 | |
2132 | for (MCSuperRegIterator SRI(DstRegNum, TRI); SRI.isValid(); ++SRI) |
2133 | MTracker->defReg(*SRI, CurBB, CurInst); |
2134 | |
2135 | |
2136 | |
2137 | |
2138 | if (EmulateOldLDV) { |
2139 | for (MCSubRegIndexIterator DRI(DstRegNum, TRI); DRI.isValid(); ++DRI) |
2140 | MTracker->defReg(DRI.getSubReg(), CurBB, CurInst); |
2141 | return; |
2142 | } |
2143 | |
2144 | |
2145 | |
2146 | |
2147 | for (MCSubRegIndexIterator SRI(SrcRegNum, TRI); SRI.isValid(); ++SRI) { |
2148 | unsigned SrcSubReg = SRI.getSubReg(); |
2149 | unsigned SubRegIdx = SRI.getSubRegIndex(); |
2150 | unsigned DstSubReg = TRI->getSubReg(DstRegNum, SubRegIdx); |
2151 | if (!DstSubReg) |
2152 | continue; |
2153 | |
2154 | |
2155 | |
2156 | |
2157 | |
2158 | (void)MTracker->readReg(SrcSubReg); |
2159 | LocIdx SrcL = MTracker->getRegMLoc(SrcSubReg); |
2160 | assert(SrcL.asU64()); |
2161 | (void)MTracker->readReg(DstSubReg); |
2162 | LocIdx DstL = MTracker->getRegMLoc(DstSubReg); |
2163 | assert(DstL.asU64()); |
2164 | (void)DstL; |
2165 | ValueIDNum CpyValue = {SrcValue.getBlock(), SrcValue.getInst(), SrcL}; |
2166 | |
2167 | MTracker->setReg(DstSubReg, CpyValue); |
2168 | } |
2169 | } |
2170 | |
2171 | bool InstrRefBasedLDV::isSpillInstruction(const MachineInstr &MI, |
2172 | MachineFunction *MF) { |
2173 | |
2174 | if (!MI.hasOneMemOperand()) |
2175 | return false; |
2176 | |
2177 | if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII)) |
2178 | return false; |
2179 | |
2180 | |
2181 | return true; |
2182 | } |
2183 | |
2184 | bool InstrRefBasedLDV::isLocationSpill(const MachineInstr &MI, |
2185 | MachineFunction *MF, unsigned &Reg) { |
2186 | if (!isSpillInstruction(MI, MF)) |
2187 | return false; |
2188 | |
2189 | int FI; |
2190 | Reg = TII->isStoreToStackSlotPostFE(MI, FI); |
2191 | return Reg != 0; |
2192 | } |
2193 | |
2194 | Optional<SpillLoc> |
2195 | InstrRefBasedLDV::isRestoreInstruction(const MachineInstr &MI, |
2196 | MachineFunction *MF, unsigned &Reg) { |
2197 | if (!MI.hasOneMemOperand()) |
2198 | return None; |
2199 | |
2200 | |
2201 | |
2202 | if (MI.getRestoreSize(TII)) { |
2203 | Reg = MI.getOperand(0).getReg(); |
2204 | return extractSpillBaseRegAndOffset(MI); |
2205 | } |
2206 | return None; |
2207 | } |
2208 | |
2209 | bool InstrRefBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI) { |
2210 | |
2211 | |
2212 | |
2213 | if (EmulateOldLDV) |
2214 | return false; |
2215 | |
2216 | MachineFunction *MF = MI.getMF(); |
2217 | unsigned Reg; |
2218 | Optional<SpillLoc> Loc; |
2219 | |
2220 | LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump();); |
2221 | |
2222 | |
2223 | |
2224 | |
2225 | if (isSpillInstruction(MI, MF)) { |
2226 | Loc = extractSpillBaseRegAndOffset(MI); |
2227 | |
2228 | if (TTracker) { |
2229 | Optional<LocIdx> MLoc = MTracker->getSpillMLoc(*Loc); |
2230 | if (MLoc) { |
2231 | |
2232 | |
2233 | MTracker->setMLoc(*MLoc, ValueIDNum::EmptyValue); |
2234 | TTracker->clobberMloc(*MLoc, MI.getIterator()); |
2235 | } |
2236 | } |
2237 | } |
2238 | |
2239 | |
2240 | if (isLocationSpill(MI, MF, Reg)) { |
2241 | Loc = extractSpillBaseRegAndOffset(MI); |
2242 | auto ValueID = MTracker->readReg(Reg); |
2243 | |
2244 | |
2245 | if (ValueID.getLoc() == 0) |
2246 | ValueID = {CurBB, 0, MTracker->getRegMLoc(Reg)}; |
2247 | |
2248 | MTracker->setSpill(*Loc, ValueID); |
2249 | auto OptSpillLocIdx = MTracker->getSpillMLoc(*Loc); |
2250 | assert(OptSpillLocIdx && "Spill slot set but has no LocIdx?"); |
2251 | LocIdx SpillLocIdx = *OptSpillLocIdx; |
2252 | |
2253 | |
2254 | if (TTracker) |
2255 | TTracker->transferMlocs(MTracker->getRegMLoc(Reg), SpillLocIdx, |
2256 | MI.getIterator()); |
2257 | } else { |
2258 | if (!(Loc = isRestoreInstruction(MI, MF, Reg))) |
2259 | return false; |
2260 | |
2261 | |
2262 | auto OptValueID = MTracker->readSpill(*Loc); |
2263 | if (OptValueID) { |
2264 | ValueIDNum ValueID = *OptValueID; |
2265 | LocIdx SpillLocIdx = *MTracker->getSpillMLoc(*Loc); |
2266 | |
2267 | |
2268 | for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) |
2269 | MTracker->defReg(*RAI, CurBB, CurInst); |
2270 | |
2271 | |
2272 | MTracker->setReg(Reg, ValueID); |
2273 | |
2274 | |
2275 | if (TTracker) |
2276 | TTracker->transferMlocs(SpillLocIdx, MTracker->getRegMLoc(Reg), |
2277 | MI.getIterator()); |
2278 | } else { |
2279 | |
2280 | |
2281 | for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) |
2282 | MTracker->defReg(*RAI, CurBB, CurInst); |
2283 | |
2284 | |
2285 | LocIdx L = MTracker->getOrTrackSpillLoc(*Loc); |
2286 | |
2287 | |
2288 | |
2289 | |
2290 | ValueIDNum ValueID = {CurBB, 0, L}; |
2291 | MTracker->setReg(Reg, ValueID); |
2292 | MTracker->setSpill(*Loc, ValueID); |
2293 | } |
2294 | } |
2295 | return true; |
2296 | } |
2297 | |
2298 | bool InstrRefBasedLDV::transferRegisterCopy(MachineInstr &MI) { |
2299 | auto DestSrc = TII->isCopyInstr(MI); |
2300 | if (!DestSrc) |
2301 | return false; |
2302 | |
2303 | const MachineOperand *DestRegOp = DestSrc->Destination; |
2304 | const MachineOperand *SrcRegOp = DestSrc->Source; |
2305 | |
2306 | auto isCalleeSavedReg = [&](unsigned Reg) { |
2307 | for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) |
2308 | if (CalleeSavedRegs.test(*RAI)) |
2309 | return true; |
2310 | return false; |
2311 | }; |
2312 | |
2313 | Register SrcReg = SrcRegOp->getReg(); |
2314 | Register DestReg = DestRegOp->getReg(); |
2315 | |
2316 | |
2317 | if (SrcReg == DestReg) |
2318 | return true; |
2319 | |
2320 | |
2321 | |
2322 | |
2323 | |
2324 | |
2325 | |
2326 | |
2327 | |
2328 | |
2329 | if (EmulateOldLDV && !isCalleeSavedReg(DestReg)) |
2330 | return false; |
2331 | |
2332 | |
2333 | if (EmulateOldLDV && !SrcRegOp->isKill()) |
2334 | return false; |
2335 | |
2336 | |
2337 | InstrRefBasedLDV::performCopy(SrcReg, DestReg); |
2338 | |
2339 | |
2340 | |
2341 | |
2342 | if (TTracker && isCalleeSavedReg(DestReg) && SrcRegOp->isKill()) |
2343 | TTracker->transferMlocs(MTracker->getRegMLoc(SrcReg), |
2344 | MTracker->getRegMLoc(DestReg), MI.getIterator()); |
2345 | |
2346 | |
2347 | if (EmulateOldLDV && SrcReg != DestReg) |
2348 | MTracker->defReg(SrcReg, CurBB, CurInst); |
2349 | |
2350 | |
2351 | |
2352 | if (TTracker) { |
2353 | for (MCRegAliasIterator RAI(DestReg, TRI, true); RAI.isValid(); ++RAI) { |
2354 | LocIdx ClobberedLoc = MTracker->getRegMLoc(*RAI); |
2355 | TTracker->clobberMloc(ClobberedLoc, MI.getIterator(), false); |
2356 | } |
2357 | } |
2358 | |
2359 | return true; |
2360 | } |
2361 | |
2362 | |
2363 | |
2364 | |
2365 | |
2366 | |
2367 | |
2368 | void InstrRefBasedLDV::accumulateFragmentMap(MachineInstr &MI) { |
2369 | DebugVariable MIVar(MI.getDebugVariable(), MI.getDebugExpression(), |
2370 | MI.getDebugLoc()->getInlinedAt()); |
2371 | FragmentInfo ThisFragment = MIVar.getFragmentOrDefault(); |
2372 | |
2373 | |
2374 | |
2375 | |
2376 | auto SeenIt = SeenFragments.find(MIVar.getVariable()); |
2377 | if (SeenIt == SeenFragments.end()) { |
2378 | SmallSet<FragmentInfo, 4> OneFragment; |
2379 | OneFragment.insert(ThisFragment); |
2380 | SeenFragments.insert({MIVar.getVariable(), OneFragment}); |
2381 | |
2382 | OverlapFragments.insert({{MIVar.getVariable(), ThisFragment}, {}}); |
2383 | return; |
2384 | } |
2385 | |
2386 | |
2387 | |
2388 | auto IsInOLapMap = |
2389 | OverlapFragments.insert({{MIVar.getVariable(), ThisFragment}, {}}); |
2390 | if (!IsInOLapMap.second) |
2391 | return; |
2392 | |
2393 | auto &ThisFragmentsOverlaps = IsInOLapMap.first->second; |
2394 | auto &AllSeenFragments = SeenIt->second; |
2395 | |
2396 | |
2397 | |
2398 | |
2399 | for (auto &ASeenFragment : AllSeenFragments) { |
2400 | |
2401 | if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) { |
2402 | |
2403 | ThisFragmentsOverlaps.push_back(ASeenFragment); |
2404 | |
2405 | |
2406 | auto ASeenFragmentsOverlaps = |
2407 | OverlapFragments.find({MIVar.getVariable(), ASeenFragment}); |
2408 | assert(ASeenFragmentsOverlaps != OverlapFragments.end() && |
2409 | "Previously seen var fragment has no vector of overlaps"); |
2410 | ASeenFragmentsOverlaps->second.push_back(ThisFragment); |
2411 | } |
2412 | } |
2413 | |
2414 | AllSeenFragments.insert(ThisFragment); |
2415 | } |
2416 | |
2417 | void InstrRefBasedLDV::process(MachineInstr &MI, ValueIDNum **MLiveOuts, |
2418 | ValueIDNum **MLiveIns) { |
2419 | |
2420 | |
2421 | |
2422 | if (transferDebugValue(MI)) |
2423 | return; |
2424 | if (transferDebugInstrRef(MI, MLiveOuts, MLiveIns)) |
2425 | return; |
2426 | if (transferDebugPHI(MI)) |
2427 | return; |
2428 | if (transferRegisterCopy(MI)) |
2429 | return; |
2430 | if (transferSpillOrRestoreInst(MI)) |
2431 | return; |
2432 | transferRegisterDef(MI); |
2433 | } |
2434 | |
2435 | void InstrRefBasedLDV::produceMLocTransferFunction( |
2436 | MachineFunction &MF, SmallVectorImpl<MLocTransferMap> &MLocTransfer, |
2437 | unsigned MaxNumBlocks) { |
2438 | |
2439 | |
2440 | |
2441 | |
2442 | |
2443 | |
2444 | |
2445 | |
2446 | SmallVector<BitVector, 32> BlockMasks; |
2447 | BlockMasks.resize(MaxNumBlocks); |
2448 | |
2449 | |
2450 | unsigned BVWords = MachineOperand::getRegMaskSize(TRI->getNumRegs()); |
2451 | for (auto &BV : BlockMasks) |
2452 | BV.resize(TRI->getNumRegs(), true); |
2453 | |
2454 | |
2455 | for (auto &MBB : MF) { |
2456 | |
2457 | |
2458 | CurBB = MBB.getNumber(); |
2459 | CurInst = 1; |
2460 | |
2461 | |
2462 | |
2463 | MTracker->reset(); |
2464 | MTracker->setMPhis(CurBB); |
2465 | |
2466 | |
2467 | for (auto &MI : MBB) { |
2468 | process(MI); |
2469 | |
2470 | if (MI.isDebugValue()) |
2471 | accumulateFragmentMap(MI); |
2472 | |
2473 | |
2474 | |
2475 | if (uint64_t InstrNo = MI.peekDebugInstrNum()) { |
2476 | auto InstrAndPos = std::make_pair(&MI, CurInst); |
2477 | auto InsertResult = |
2478 | DebugInstrNumToInstr.insert(std::make_pair(InstrNo, InstrAndPos)); |
2479 | |
2480 | |
2481 | assert(InsertResult.second); |
2482 | (void)InsertResult; |
2483 | } |
2484 | |
2485 | ++CurInst; |
2486 | } |
2487 | |
2488 | |
2489 | |
2490 | |
2491 | |
2492 | for (auto Location : MTracker->locations()) { |
2493 | LocIdx Idx = Location.Idx; |
2494 | ValueIDNum &P = Location.Value; |
2495 | if (P.isPHI() && P.getLoc() == Idx.asU64()) |
2496 | continue; |
2497 | |
2498 | |
2499 | auto &TransferMap = MLocTransfer[CurBB]; |
2500 | auto Result = TransferMap.insert(std::make_pair(Idx.asU64(), P)); |
2501 | if (!Result.second) |
2502 | Result.first->second = P; |
2503 | } |
2504 | |
2505 | |
2506 | |
2507 | for (auto &P : MTracker->Masks) { |
2508 | BlockMasks[CurBB].clearBitsNotInMask(P.first->getRegMask(), BVWords); |
2509 | } |
2510 | } |
2511 | |
2512 | |
2513 | const TargetLowering *TLI = MF.getSubtarget().getTargetLowering(); |
2514 | Register SP = TLI->getStackPointerRegisterToSaveRestore(); |
2515 | BitVector UsedRegs(TRI->getNumRegs()); |
2516 | for (auto Location : MTracker->locations()) { |
2517 | unsigned ID = MTracker->LocIdxToLocID[Location.Idx]; |
2518 | if (ID >= TRI->getNumRegs() || ID == SP) |
2519 | continue; |
2520 | UsedRegs.set(ID); |
2521 | } |
2522 | |
2523 | |
2524 | |
2525 | |
2526 | for (unsigned int I = 0; I < MaxNumBlocks; ++I) { |
2527 | BitVector &BV = BlockMasks[I]; |
2528 | BV.flip(); |
2529 | BV &= UsedRegs; |
2530 | |
2531 | |
2532 | |
2533 | for (unsigned Bit : BV.set_bits()) { |
2534 | unsigned ID = MTracker->getLocID(Bit, false); |
2535 | LocIdx Idx = MTracker->LocIDToLocIdx[ID]; |
2536 | auto &TransferMap = MLocTransfer[I]; |
2537 | |
2538 | |
2539 | |
2540 | |
2541 | |
2542 | |
2543 | ValueIDNum NotGeneratedNum = ValueIDNum(I, 1, Idx); |
2544 | auto Result = |
2545 | TransferMap.insert(std::make_pair(Idx.asU64(), NotGeneratedNum)); |
2546 | if (!Result.second) { |
2547 | ValueIDNum &ValueID = Result.first->second; |
2548 | if (ValueID.getBlock() == I && ValueID.isPHI()) |
2549 | |
2550 | ValueID = NotGeneratedNum; |
2551 | } |
2552 | } |
2553 | } |
2554 | } |
2555 | |
2556 | std::tuple<bool, bool> |
2557 | InstrRefBasedLDV::mlocJoin(MachineBasicBlock &MBB, |
2558 | SmallPtrSet<const MachineBasicBlock *, 16> &Visited, |
2559 | ValueIDNum **OutLocs, ValueIDNum *InLocs) { |
2560 | LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n"); |
2561 | bool Changed = false; |
2562 | bool DowngradeOccurred = false; |
2563 | |
2564 | |
2565 | |
2566 | |
2567 | SmallVector<const MachineBasicBlock *, 8> BlockOrders; |
2568 | for (auto Pred : MBB.predecessors()) { |
2569 | if (Visited.count(Pred)) { |
2570 | BlockOrders.push_back(Pred); |
2571 | } |
2572 | } |
2573 | |
2574 | |
2575 | auto Cmp = [&](const MachineBasicBlock *A, const MachineBasicBlock *B) { |
2576 | return BBToOrder.find(A)->second < BBToOrder.find(B)->second; |
2577 | }; |
2578 | llvm::sort(BlockOrders, Cmp); |
2579 | |
2580 | |
2581 | if (BlockOrders.size() == 0) |
2582 | return std::tuple<bool, bool>(false, false); |
2583 | |
2584 | |
2585 | |
2586 | unsigned ThisBlockRPO = BBToOrder.find(&MBB)->second; |
2587 | for (auto Location : MTracker->locations()) { |
2588 | LocIdx Idx = Location.Idx; |
2589 | |
2590 | |
2591 | ValueIDNum BaseVal = OutLocs[BlockOrders[0]->getNumber()][Idx.asU64()]; |
2592 | |
2593 | |
2594 | |
2595 | bool Disagree = false; |
2596 | bool NonBackEdgeDisagree = false; |
2597 | |
2598 | |
2599 | for (unsigned int I = 1; I < BlockOrders.size(); ++I) { |
2600 | auto *MBB = BlockOrders[I]; |
2601 | if (BaseVal != OutLocs[MBB->getNumber()][Idx.asU64()]) { |
2602 | |
2603 | Disagree = true; |
2604 | |
2605 | |
2606 | if (BBToOrder.find(MBB)->second < ThisBlockRPO) |
2607 | NonBackEdgeDisagree = true; |
2608 | } |
2609 | } |
2610 | |
2611 | bool OverRide = false; |
2612 | if (Disagree && !NonBackEdgeDisagree) { |
2613 | |
2614 | |
2615 | |
2616 | |
2617 | |
2618 | |
2619 | |
2620 | |
2621 | |
2622 | |
2623 | unsigned BaseBlockRPONum = BBNumToRPO[BaseVal.getBlock()] + 1; |
2624 | if (!BaseVal.isPHI()) |
2625 | BaseBlockRPONum = 0; |
2626 | |
2627 | ValueIDNum &InLocID = InLocs[Idx.asU64()]; |
2628 | unsigned InLocRPONum = BBNumToRPO[InLocID.getBlock()] + 1; |
2629 | if (!InLocID.isPHI()) |
2630 | InLocRPONum = 0; |
2631 | |
2632 | |
2633 | |
2634 | unsigned ThisBlockRPONum = BBNumToRPO[MBB.getNumber()] + 1; |
2635 | if (BaseBlockRPONum > InLocRPONum && BaseBlockRPONum < ThisBlockRPONum) { |
2636 | |
2637 | OverRide = true; |
2638 | DowngradeOccurred = true; |
2639 | } |
2640 | } |
2641 | |
2642 | |
2643 | |
2644 | |
2645 | ValueIDNum PHI = {(uint64_t)MBB.getNumber(), 0, Idx}; |
2646 | ValueIDNum NewVal = (Disagree && !OverRide) ? PHI : BaseVal; |
2647 | if (InLocs[Idx.asU64()] != NewVal) { |
2648 | Changed |= true; |
2649 | InLocs[Idx.asU64()] = NewVal; |
2650 | } |
2651 | } |
2652 | |
2653 | |
2654 | return std::tuple<bool, bool>(Changed, DowngradeOccurred); |
2655 | } |
2656 | |
2657 | void InstrRefBasedLDV::mlocDataflow( |
2658 | ValueIDNum **MInLocs, ValueIDNum **MOutLocs, |
2659 | SmallVectorImpl<MLocTransferMap> &MLocTransfer) { |
2660 | std::priority_queue<unsigned int, std::vector<unsigned int>, |
2661 | std::greater<unsigned int>> |
2662 | Worklist, Pending; |
2663 | |
2664 | |
2665 | |
2666 | |
2667 | SmallPtrSet<MachineBasicBlock *, 16> OnPending, OnWorklist; |
2668 | |
2669 | |
2670 | for (unsigned int I = 0; I < BBToOrder.size(); ++I) { |
2671 | Worklist.push(I); |
2672 | OnWorklist.insert(OrderToBB[I]); |
2673 | } |
2674 | |
2675 | MTracker->reset(); |
2676 | |
2677 | |
2678 | |
2679 | MTracker->setMPhis(0); |
2680 | for (auto Location : MTracker->locations()) |
2681 | MInLocs[0][Location.Idx.asU64()] = Location.Value; |
2682 | |
2683 | SmallPtrSet<const MachineBasicBlock *, 16> Visited; |
2684 | while (!Worklist.empty() || !Pending.empty()) { |
2685 | |
2686 | SmallVector<std::pair<LocIdx, ValueIDNum>, 32> ToRemap; |
2687 | |
2688 | while (!Worklist.empty()) { |
2689 | MachineBasicBlock *MBB = OrderToBB[Worklist.top()]; |
2690 | CurBB = MBB->getNumber(); |
2691 | Worklist.pop(); |
2692 | |
2693 | |
2694 | bool InLocsChanged, DowngradeOccurred; |
2695 | std::tie(InLocsChanged, DowngradeOccurred) = |
2696 | mlocJoin(*MBB, Visited, MOutLocs, MInLocs[CurBB]); |
2697 | InLocsChanged |= Visited.insert(MBB).second; |
2698 | |
2699 | |
2700 | |
2701 | if (DowngradeOccurred && OnPending.insert(MBB).second) |
2702 | Pending.push(BBToOrder[MBB]); |
2703 | |
2704 | |
2705 | |
2706 | if (!InLocsChanged) |
2707 | continue; |
2708 | |
2709 | |
2710 | MTracker->loadFromArray(MInLocs[CurBB], CurBB); |
2711 | |
2712 | |
2713 | |
2714 | ToRemap.clear(); |
2715 | for (auto &P : MLocTransfer[CurBB]) { |
2716 | if (P.second.getBlock() == CurBB && P.second.isPHI()) { |
2717 | |
2718 | ValueIDNum NewID = MTracker->getNumAtPos(P.second.getLoc()); |
2719 | ToRemap.push_back(std::make_pair(P.first, NewID)); |
2720 | } else { |
2721 | |
2722 | assert(P.second.getBlock() == CurBB); |
2723 | ToRemap.push_back(std::make_pair(P.first, P.second)); |
2724 | } |
2725 | } |
2726 | |
2727 | |
2728 | |
2729 | for (auto &P : ToRemap) |
2730 | MTracker->setMLoc(P.first, P.second); |
2731 | |
2732 | |
2733 | |
2734 | |
2735 | bool OLChanged = false; |
2736 | for (auto Location : MTracker->locations()) { |
2737 | OLChanged |= MOutLocs[CurBB][Location.Idx.asU64()] != Location.Value; |
2738 | MOutLocs[CurBB][Location.Idx.asU64()] = Location.Value; |
2739 | } |
2740 | |
2741 | MTracker->reset(); |
2742 | |
2743 | |
2744 | if (!OLChanged) |
2745 | continue; |
2746 | |
2747 | |
2748 | |
2749 | |
2750 | for (auto s : MBB->successors()) { |
2751 | |
2752 | if (BBToOrder[s] > BBToOrder[MBB]) { |
2753 | |
2754 | if (OnWorklist.insert(s).second) |
2755 | Worklist.push(BBToOrder[s]); |
2756 | } else { |
2757 | |
2758 | if (OnPending.insert(s).second) |
2759 | Pending.push(BBToOrder[s]); |
2760 | } |
2761 | } |
2762 | } |
2763 | |
2764 | Worklist.swap(Pending); |
2765 | std::swap(OnPending, OnWorklist); |
2766 | OnPending.clear(); |
2767 | |
2768 | |
2769 | assert(Pending.empty() && "Pending should be empty"); |
2770 | } |
2771 | |
2772 | |
2773 | |
2774 | } |
2775 | |
2776 | bool InstrRefBasedLDV::vlocDowngradeLattice( |
2777 | const MachineBasicBlock &MBB, const DbgValue &OldLiveInLocation, |
2778 | const SmallVectorImpl<InValueT> &Values, unsigned CurBlockRPONum) { |
2779 | |
2780 | |
2781 | |
2782 | |
2783 | int OldLiveInRank = BBNumToRPO[OldLiveInLocation.ID.getBlock()] + 1; |
2784 | if (!OldLiveInLocation.ID.isPHI()) |
2785 | OldLiveInRank = 0; |
2786 | |
2787 | |
2788 | if (OldLiveInLocation.Kind == DbgValue::NoVal) { |
2789 | |
2790 | |
2791 | if (OldLiveInLocation.BlockNo == (unsigned)MBB.getNumber()) |
2792 | return false; |
2793 | OldLiveInRank = INT_MIN; |
2794 | } |
2795 | |
2796 | auto &InValue = *Values[0].second; |
2797 | |
2798 | if (InValue.Kind == DbgValue::Const || InValue.Kind == DbgValue::NoVal) |
2799 | return false; |
2800 | |
2801 | unsigned ThisRPO = BBNumToRPO[InValue.ID.getBlock()]; |
2802 | int ThisRank = ThisRPO + 1; |
2803 | if (!InValue.ID.isPHI()) |
2804 | ThisRank = 0; |
2805 | |
2806 | |
2807 | if (ThisRPO >= CurBlockRPONum) |
2808 | return false; |
2809 | |
2810 | |
2811 | if (ThisRank <= OldLiveInRank) |
2812 | return false; |
2813 | |
2814 | return true; |
2815 | } |
2816 | |
2817 | std::tuple<Optional<ValueIDNum>, bool> InstrRefBasedLDV::pickVPHILoc( |
2818 | MachineBasicBlock &MBB, const DebugVariable &Var, const LiveIdxT &LiveOuts, |
2819 | ValueIDNum **MOutLocs, ValueIDNum **MInLocs, |
2820 | const SmallVectorImpl<MachineBasicBlock *> &BlockOrders) { |
2821 | |
2822 | |
2823 | SmallVector<SmallVector<LocIdx, 4>, 8> Locs; |
2824 | unsigned NumLocs = MTracker->getNumLocs(); |
2825 | unsigned BackEdgesStart = 0; |
2826 | |
2827 | for (auto p : BlockOrders) { |
2828 | |
2829 | |
2830 | if (BBToOrder[p] < BBToOrder[&MBB]) |
2831 | ++BackEdgesStart; |
2832 | |
2833 | |
2834 | Locs.resize(Locs.size() + 1); |
2835 | unsigned ThisBBNum = p->getNumber(); |
2836 | auto LiveOutMap = LiveOuts.find(p); |
2837 | if (LiveOutMap == LiveOuts.end()) |
2838 | |
2839 | |
2840 | continue; |
2841 | |
2842 | auto It = LiveOutMap->second->find(Var); |
2843 | if (It == LiveOutMap->second->end()) |
2844 | |
2845 | |
2846 | continue; |
2847 | |
2848 | const DbgValue &OutVal = It->second; |
2849 | |
2850 | if (OutVal.Kind == DbgValue::Const || OutVal.Kind == DbgValue::NoVal) |
2851 | |
2852 | continue; |
2853 | |
2854 | assert(OutVal.Kind == DbgValue::Proposed || OutVal.Kind == DbgValue::Def); |
2855 | ValueIDNum ValToLookFor = OutVal.ID; |
2856 | |
2857 | |
2858 | for (unsigned int I = 0; I < NumLocs; ++I) { |
2859 | if (MOutLocs[ThisBBNum][I] == ValToLookFor) |
2860 | Locs.back().push_back(LocIdx(I)); |
2861 | } |
2862 | } |
2863 | |
2864 | |
2865 | if (Locs.empty()) |
2866 | return std::tuple<Optional<ValueIDNum>, bool>(None, false); |
2867 | |
2868 | |
2869 | using LocsIt = SmallVector<SmallVector<LocIdx, 4>, 8>::iterator; |
2870 | auto SeekLocation = |
2871 | [&Locs](llvm::iterator_range<LocsIt> SearchRange) -> Optional<LocIdx> { |
2872 | |
2873 | |
2874 | SmallVector<LocIdx, 4> base = Locs[0]; |
2875 | for (auto &S : SearchRange) { |
2876 | SmallVector<LocIdx, 4> new_base; |
2877 | std::set_intersection(base.begin(), base.end(), S.begin(), S.end(), |
2878 | std::inserter(new_base, new_base.begin())); |
2879 | base = new_base; |
2880 | } |
2881 | if (base.empty()) |
2882 | return None; |
2883 | |
2884 | |
2885 | |
2886 | |
2887 | return *base.begin(); |
2888 | }; |
2889 | |
2890 | |
2891 | |
2892 | bool ValidForAllLocs = true; |
2893 | auto TheLoc = SeekLocation(Locs); |
2894 | if (!TheLoc) { |
2895 | ValidForAllLocs = false; |
2896 | TheLoc = |
2897 | SeekLocation(make_range(Locs.begin(), Locs.begin() + BackEdgesStart)); |
2898 | } |
2899 | |
2900 | if (!TheLoc) |
2901 | return std::tuple<Optional<ValueIDNum>, bool>(None, false); |
2902 | |
2903 | |
2904 | LocIdx L = *TheLoc; |
2905 | ValueIDNum PHIVal = {(unsigned)MBB.getNumber(), 0, L}; |
2906 | return std::tuple<Optional<ValueIDNum>, bool>(PHIVal, ValidForAllLocs); |
2907 | } |
2908 | |
2909 | std::tuple<bool, bool> InstrRefBasedLDV::vlocJoin( |
2910 | MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, LiveIdxT &VLOCInLocs, |
2911 | SmallPtrSet<const MachineBasicBlock *, 16> *VLOCVisited, unsigned BBNum, |
2912 | const SmallSet<DebugVariable, 4> &AllVars, ValueIDNum **MOutLocs, |
2913 | ValueIDNum **MInLocs, |
2914 | SmallPtrSet<const MachineBasicBlock *, 8> &InScopeBlocks, |
2915 | SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore, |
2916 | DenseMap<DebugVariable, DbgValue> &InLocsT) { |
2917 | bool DowngradeOccurred = false; |
2918 | |
2919 | |
2920 | |
2921 | |
2922 | if (InScopeBlocks.count(&MBB) == 0 && !ArtificialBlocks.count(&MBB)) { |
2923 | if (VLOCVisited) |
2924 | return std::tuple<bool, bool>(true, false); |
2925 | return std::tuple<bool, bool>(false, false); |
2926 | } |
2927 | |
2928 | LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n"); |
2929 | bool Changed = false; |
2930 | |
2931 | |
2932 | auto ILSIt = VLOCInLocs.find(&MBB); |
2933 | assert(ILSIt != VLOCInLocs.end()); |
2934 | auto &ILS = *ILSIt->second; |
2935 | |
2936 | |
2937 | SmallVector<MachineBasicBlock *, 8> BlockOrders(MBB.predecessors()); |
2938 | |
2939 | auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) { |
2940 | return BBToOrder[A] < BBToOrder[B]; |
2941 | }; |
2942 | |
2943 | llvm::sort(BlockOrders, Cmp); |
2944 | |
2945 | unsigned CurBlockRPONum = BBToOrder[&MBB]; |
2946 | |
2947 | |
2948 | |
2949 | |
2950 | if (!BlockOrders.empty() && |
2951 | BBToOrder[BlockOrders[BlockOrders.size() - 1]] >= CurBlockRPONum && |
2952 | VLOCVisited) |
2953 | DowngradeOccurred = true; |
2954 | |
2955 | auto ConfirmValue = [&InLocsT](const DebugVariable &DV, DbgValue VR) { |
2956 | auto Result = InLocsT.insert(std::make_pair(DV, VR)); |
2957 | (void)Result; |
2958 | assert(Result.second); |
2959 | }; |
2960 | |
2961 | auto ConfirmNoVal = [&ConfirmValue, &MBB](const DebugVariable &Var, const DbgValueProperties &Properties) { |
2962 | DbgValue NoLocPHIVal(MBB.getNumber(), Properties, DbgValue::NoVal); |
2963 | |
2964 | ConfirmValue(Var, NoLocPHIVal); |
2965 | }; |
2966 | |
2967 | |
2968 | for (auto &Var : AllVars) { |
2969 | |
2970 | SmallVector<InValueT, 8> Values; |
2971 | bool Bail = false; |
2972 | unsigned BackEdgesStart = 0; |
2973 | for (auto p : BlockOrders) { |
2974 | |
2975 | |
2976 | if (!BlocksToExplore.contains(p)) { |
2977 | Bail = true; |
2978 | break; |
2979 | } |
2980 | |
2981 | |
2982 | |
2983 | if (VLOCVisited && !VLOCVisited->count(p)) |
2984 | continue; |
2985 | |
2986 | |
2987 | auto OL = VLOCOutLocs.find(p); |
2988 | if (OL == VLOCOutLocs.end()) { |
2989 | Bail = true; |
2990 | break; |
2991 | } |
2992 | |
2993 | |
2994 | |
2995 | auto VIt = OL->second->find(Var); |
2996 | if (VIt == OL->second->end()) { |
2997 | Bail = true; |
2998 | break; |
2999 | } |
3000 | |
3001 | |
3002 | |
3003 | unsigned ThisBBRPONum = BBToOrder[p]; |
3004 | if (ThisBBRPONum < CurBlockRPONum) |
3005 | ++BackEdgesStart; |
3006 | |
3007 | Values.push_back(std::make_pair(p, &VIt->second)); |
3008 | } |
3009 | |
3010 | |
3011 | |
3012 | |
3013 | if (Bail || Values.size() == 0) |
3014 | continue; |
3015 | |
3016 | |
3017 | enum { |
3018 | Unset = 0, |
3019 | Agreed, |
3020 | PropDisagree, |
3021 | BEDisagree, |
3022 | PHINeeded, |
3023 | NoSolution |
3024 | } OurState = Unset; |
3025 | |
3026 | |
3027 | |
3028 | |
3029 | const DbgValue &FirstVal = *Values[0].second; |
3030 | const ValueIDNum &FirstID = FirstVal.ID; |
3031 | |
3032 | |
3033 | |
3034 | |
3035 | for (auto &V : Values) { |
3036 | if (V.second->Properties != FirstVal.Properties) |
3037 | OurState = NoSolution; |
3038 | if (V.second->Kind == DbgValue::Const && FirstVal.Kind != DbgValue::Const) |
3039 | OurState = NoSolution; |
3040 | } |
3041 | |
3042 | |
3043 | bool NonBackEdgeDisagree = false; |
3044 | bool DisagreeOnPHINess = false; |
3045 | bool IDDisagree = false; |
3046 | bool Disagree = false; |
3047 | if (OurState == Unset) { |
3048 | for (auto &V : Values) { |
3049 | if (*V.second == FirstVal) |
3050 | continue; |
3051 | |
3052 | Disagree = true; |
3053 | |
3054 | |
3055 | if (V.second->ID != FirstID) |
3056 | IDDisagree = true; |
3057 | |
3058 | |
3059 | |
3060 | unsigned ThisBBRPONum = BBToOrder[V.first]; |
3061 | if (ThisBBRPONum < CurBlockRPONum) |
3062 | NonBackEdgeDisagree = true; |
3063 | |
3064 | |
3065 | |
3066 | if (V.second->Kind != FirstVal.Kind && |
3067 | (V.second->Kind == DbgValue::Proposed || |
3068 | V.second->Kind == DbgValue::Def) && |
3069 | (FirstVal.Kind == DbgValue::Proposed || |
3070 | FirstVal.Kind == DbgValue::Def)) |
3071 | DisagreeOnPHINess = true; |
3072 | } |
3073 | |
3074 | |
3075 | |
3076 | if (!Disagree) |
3077 | OurState = Agreed; |
3078 | else if (!IDDisagree && DisagreeOnPHINess) |
3079 | OurState = PropDisagree; |
3080 | else if (!NonBackEdgeDisagree) |
3081 | OurState = BEDisagree; |
3082 | else |
3083 | OurState = PHINeeded; |
3084 | } |
3085 | |
3086 | |
3087 | |
3088 | |
3089 | bool PropOnlyInBEs = Disagree && !IDDisagree && DisagreeOnPHINess && |
3090 | !NonBackEdgeDisagree && FirstVal.Kind == DbgValue::Def; |
3091 | |
3092 | const auto &Properties = FirstVal.Properties; |
3093 | |
3094 | auto OldLiveInIt = ILS.find(Var); |
3095 | const DbgValue *OldLiveInLocation = |
3096 | (OldLiveInIt != ILS.end()) ? &OldLiveInIt->second : nullptr; |
3097 | |
3098 | bool OverRide = false; |
3099 | if (OurState == BEDisagree && OldLiveInLocation) { |
3100 | |
3101 | |
3102 | |
3103 | OverRide = |
3104 | vlocDowngradeLattice(MBB, *OldLiveInLocation, Values, CurBlockRPONum); |
3105 | } |
3106 | |
3107 | |
3108 | |
3109 | |
3110 | |
3111 | |
3112 | |
3113 | |
3114 | if (OurState == Agreed) { |
3115 | |
3116 | ConfirmValue(Var, FirstVal); |
3117 | } else if (OurState == BEDisagree && OverRide) { |
3118 | |
3119 | |
3120 | DowngradeOccurred = true; |
3121 | ConfirmValue(Var, FirstVal); |
3122 | } else if (OurState == PropDisagree) { |
3123 | |
3124 | |
3125 | |
3126 | if (FirstID.getBlock() == (uint64_t)MBB.getNumber() && FirstID.isPHI()) { |
3127 | ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Def)); |
3128 | } else if (PropOnlyInBEs) { |
3129 | |
3130 | |
3131 | ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Def)); |
3132 | } else { |
3133 | |
3134 | ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Proposed)); |
3135 | } |
3136 | } else if ((OurState == PHINeeded || OurState == BEDisagree)) { |
3137 | |
3138 | |
3139 | Optional<ValueIDNum> VPHI; |
3140 | bool AllEdgesVPHI = false; |
3141 | std::tie(VPHI, AllEdgesVPHI) = |
3142 | pickVPHILoc(MBB, Var, VLOCOutLocs, MOutLocs, MInLocs, BlockOrders); |
3143 | |
3144 | if (VPHI && AllEdgesVPHI) { |
3145 | |
3146 | |
3147 | |
3148 | |
3149 | DbgValue::KindT K = DbgValue::Def; |
3150 | for (unsigned int I = 0; I < BackEdgesStart; ++I) |
3151 | if (Values[I].second->Kind == DbgValue::Proposed) |
3152 | K = DbgValue::Proposed; |
3153 | |
3154 | ConfirmValue(Var, DbgValue(*VPHI, Properties, K)); |
3155 | } else if (VPHI) { |
3156 | |
3157 | |
3158 | |
3159 | DbgValue NoBEValue = DbgValue(*VPHI, Properties, DbgValue::Proposed); |
3160 | ConfirmValue(Var, NoBEValue); |
3161 | } else { |
3162 | ConfirmNoVal(Var, Properties); |
3163 | } |
3164 | } else { |
3165 | |
3166 | ConfirmNoVal(Var, Properties); |
3167 | } |
3168 | } |
3169 | |
3170 | |
3171 | Changed = ILS != InLocsT; |
3172 | if (Changed) |
3173 | ILS = InLocsT; |
3174 | |
3175 | return std::tuple<bool, bool>(Changed, DowngradeOccurred); |
3176 | } |
3177 | |
3178 | void InstrRefBasedLDV::vlocDataflow( |
3179 | const LexicalScope *Scope, const DILocation *DILoc, |
3180 | const SmallSet<DebugVariable, 4> &VarsWeCareAbout, |
3181 | SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks, LiveInsT &Output, |
3182 | ValueIDNum **MOutLocs, ValueIDNum **MInLocs, |
3183 | SmallVectorImpl<VLocTracker> &AllTheVLocs) { |
3184 | |
3185 | |
3186 | |
3187 | |
3188 | std::priority_queue<unsigned int, std::vector<unsigned int>, |
3189 | std::greater<unsigned int>> |
3190 | Worklist, Pending; |
3191 | SmallPtrSet<MachineBasicBlock *, 16> OnWorklist, OnPending; |
3192 | |
3193 | |
3194 | SmallPtrSet<const MachineBasicBlock *, 8> BlocksToExplore; |
3195 | |
3196 | |
3197 | SmallVector<MachineBasicBlock *, 8> BlockOrders; |
3198 | |
3199 | |
3200 | auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) { |
3201 | return BBToOrder[A] < BBToOrder[B]; |
3202 | }; |
3203 | |
3204 | LS.getMachineBasicBlocks(DILoc, BlocksToExplore); |
3205 | |
3206 | |
3207 | |
3208 | SmallPtrSet<const MachineBasicBlock *, 8> InScopeBlocks = BlocksToExplore; |
3209 | |
3210 | |
3211 | |
3212 | |
3213 | if (EmulateOldLDV) |
3214 | BlocksToExplore.insert(AssignBlocks.begin(), AssignBlocks.end()); |
3215 | |
3216 | |
3217 | |
3218 | DenseSet<const MachineBasicBlock *> ToAdd; |
3219 | |
3220 | |
3221 | |
3222 | auto AccumulateArtificialBlocks = |
3223 | [this, &ToAdd, &BlocksToExplore, |
3224 | &InScopeBlocks](const MachineBasicBlock *MBB) { |
3225 | |
3226 | |
3227 | SmallVector<std::pair<const MachineBasicBlock *, |
3228 | MachineBasicBlock::const_succ_iterator>, |
3229 | 8> |
3230 | DFS; |
3231 | |
3232 | |
3233 | for (auto *succ : MBB->successors()) { |
3234 | if (BlocksToExplore.count(succ) || InScopeBlocks.count(succ)) |
3235 | continue; |
3236 | if (!ArtificialBlocks.count(succ)) |
3237 | continue; |
3238 | DFS.push_back(std::make_pair(succ, succ->succ_begin())); |
3239 | ToAdd.insert(succ); |
3240 | } |
3241 | |
3242 | |
3243 | while (!DFS.empty()) { |
3244 | const MachineBasicBlock *CurBB = DFS.back().first; |
3245 | MachineBasicBlock::const_succ_iterator &CurSucc = DFS.back().second; |
3246 | |
3247 | if (CurSucc == CurBB->succ_end()) { |
3248 | DFS.pop_back(); |
3249 | continue; |
3250 | } |
3251 | |
3252 | |
3253 | |
3254 | if (!ToAdd.count(*CurSucc) && ArtificialBlocks.count(*CurSucc)) { |
3255 | DFS.push_back(std::make_pair(*CurSucc, (*CurSucc)->succ_begin())); |
3256 | ToAdd.insert(*CurSucc); |
3257 | continue; |
3258 | } |
3259 | |
3260 | ++CurSucc; |
3261 | } |
3262 | }; |
3263 | |
3264 | |
3265 | |
3266 | for (auto *MBB : BlocksToExplore) |
3267 | AccumulateArtificialBlocks(MBB); |
3268 | for (auto *MBB : InScopeBlocks) |
3269 | AccumulateArtificialBlocks(MBB); |
3270 | |
3271 | BlocksToExplore.insert(ToAdd.begin(), ToAdd.end()); |
3272 | InScopeBlocks.insert(ToAdd.begin(), ToAdd.end()); |
3273 | |
3274 | |
3275 | |
3276 | |
3277 | |
3278 | if (BlocksToExplore.size() == 1) |
3279 | return; |
3280 | |
3281 | |
3282 | for (auto *MBB : BlocksToExplore) |
3283 | BlockOrders.push_back(const_cast<MachineBasicBlock *>(MBB)); |
3284 | |
3285 | llvm::sort(BlockOrders, Cmp); |
3286 | unsigned NumBlocks = BlockOrders.size(); |
3287 | |
3288 | |
3289 | SmallVector<DenseMap<DebugVariable, DbgValue>, 32> LiveIns, LiveOuts; |
3290 | LiveIns.resize(NumBlocks); |
3291 | LiveOuts.resize(NumBlocks); |
3292 | |
3293 | |
3294 | |
3295 | LiveIdxT LiveOutIdx, LiveInIdx; |
3296 | LiveOutIdx.reserve(NumBlocks); |
3297 | LiveInIdx.reserve(NumBlocks); |
3298 | for (unsigned I = 0; I < NumBlocks; ++I) { |
3299 | LiveOutIdx[BlockOrders[I]] = &LiveOuts[I]; |
3300 | LiveInIdx[BlockOrders[I]] = &LiveIns[I]; |
3301 | } |
3302 | |
3303 | for (auto *MBB : BlockOrders) { |
3304 | Worklist.push(BBToOrder[MBB]); |
3305 | OnWorklist.insert(MBB); |
3306 | } |
3307 | |
3308 | |
3309 | bool FirstTrip = true; |
3310 | SmallPtrSet<const MachineBasicBlock *, 16> VLOCVisited; |
3311 | while (!Worklist.empty() || !Pending.empty()) { |
3312 | while (!Worklist.empty()) { |
3313 | auto *MBB = OrderToBB[Worklist.top()]; |
3314 | CurBB = MBB->getNumber(); |
3315 | Worklist.pop(); |
3316 | |
3317 | DenseMap<DebugVariable, DbgValue> JoinedInLocs; |
3318 | |
3319 | |
3320 | |
3321 | bool InLocsChanged, DowngradeOccurred; |
3322 | std::tie(InLocsChanged, DowngradeOccurred) = vlocJoin( |
3323 | *MBB, LiveOutIdx, LiveInIdx, (FirstTrip) ? &VLOCVisited : nullptr, |
3324 | CurBB, VarsWeCareAbout, MOutLocs, MInLocs, InScopeBlocks, |
3325 | BlocksToExplore, JoinedInLocs); |
3326 | |
3327 | bool FirstVisit = VLOCVisited.insert(MBB).second; |
3328 | |
3329 | |
3330 | |
3331 | InLocsChanged |= FirstVisit; |
3332 | |
3333 | |
3334 | |
3335 | if (DowngradeOccurred && OnPending.insert(MBB).second) |
3336 | Pending.push(BBToOrder[MBB]); |
3337 | |
3338 | if (!InLocsChanged) |
3339 | continue; |
3340 | |
3341 | |
3342 | auto &VTracker = AllTheVLocs[MBB->getNumber()]; |
3343 | for (auto &Transfer : VTracker.Vars) { |
3344 | |
3345 | if (VarsWeCareAbout.count(Transfer.first)) { |
3346 | |
3347 | if (Transfer.second.Kind == DbgValue::Undef) { |
3348 | JoinedInLocs.erase(Transfer.first); |
3349 | } else { |
3350 | |
3351 | auto NewValuePair = std::make_pair(Transfer.first, Transfer.second); |
3352 | auto Result = JoinedInLocs.insert(NewValuePair); |
3353 | if (!Result.second) |
3354 | Result.first->second = Transfer.second; |
3355 | } |
3356 | } |
3357 | } |
3358 | |
3359 | |
3360 | bool OLChanged = JoinedInLocs != *LiveOutIdx[MBB]; |
3361 | |
3362 | |
3363 | if (!OLChanged) |
3364 | continue; |
3365 | |
3366 | |
3367 | *LiveOutIdx[MBB] = JoinedInLocs; |
3368 | |
3369 | |
3370 | |
3371 | |
3372 | for (auto s : MBB->successors()) { |
3373 | |
3374 | if (LiveInIdx.find(s) == LiveInIdx.end()) |
3375 | continue; |
3376 | |
3377 | if (BBToOrder[s] > BBToOrder[MBB]) { |
3378 | if (OnWorklist.insert(s).second) |
3379 | Worklist.push(BBToOrder[s]); |
3380 | } else if (OnPending.insert(s).second && (FirstTrip || OLChanged)) { |
3381 | Pending.push(BBToOrder[s]); |
3382 | } |
3383 | } |
3384 | } |
3385 | Worklist.swap(Pending); |
3386 | std::swap(OnWorklist, OnPending); |
3387 | OnPending.clear(); |
3388 | assert(Pending.empty()); |
3389 | FirstTrip = false; |
3390 | } |
3391 | |
3392 | |
3393 | |
3394 | |
3395 | |
3396 | for (auto *MBB : BlockOrders) { |
3397 | auto &VarMap = *LiveInIdx[MBB]; |
3398 | for (auto &P : VarMap) { |
3399 | if (P.second.Kind == DbgValue::Proposed || |
3400 | P.second.Kind == DbgValue::NoVal) |
3401 | continue; |
3402 | Output[MBB->getNumber()].push_back(P); |
3403 | } |
3404 | } |
3405 | |
3406 | BlockOrders.clear(); |
3407 | BlocksToExplore.clear(); |
3408 | } |
3409 | |
3410 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
3411 | void InstrRefBasedLDV::dump_mloc_transfer( |
3412 | const MLocTransferMap &mloc_transfer) const { |
3413 | for (auto &P : mloc_transfer) { |
3414 | std::string foo = MTracker->LocIdxToName(P.first); |
3415 | std::string bar = MTracker->IDAsString(P.second); |
3416 | dbgs() << "Loc " << foo << " --> " << bar << "\n"; |
3417 | } |
3418 | } |
3419 | #endif |
3420 | |
3421 | void InstrRefBasedLDV::emitLocations( |
3422 | MachineFunction &MF, LiveInsT SavedLiveIns, ValueIDNum **MOutLocs, |
3423 | ValueIDNum **MInLocs, DenseMap<DebugVariable, unsigned> &AllVarsNumbering, |
3424 | const TargetPassConfig &TPC) { |
3425 | TTracker = new TransferTracker(TII, MTracker, MF, *TRI, CalleeSavedRegs, TPC); |
3426 | unsigned NumLocs = MTracker->getNumLocs(); |
3427 | |
3428 | |
3429 | |
3430 | |
3431 | for (MachineBasicBlock &MBB : MF) { |
3432 | unsigned bbnum = MBB.getNumber(); |
3433 | MTracker->reset(); |
3434 | MTracker->loadFromArray(MInLocs[bbnum], bbnum); |
3435 | TTracker->loadInlocs(MBB, MInLocs[bbnum], SavedLiveIns[MBB.getNumber()], |
3436 | NumLocs); |
3437 | |
3438 | CurBB = bbnum; |
3439 | CurInst = 1; |
3440 | for (auto &MI : MBB) { |
3441 | process(MI, MOutLocs, MInLocs); |
3442 | TTracker->checkInstForNewValues(CurInst, MI.getIterator()); |
3443 | ++CurInst; |
3444 | } |
3445 | } |
3446 | |
3447 | |
3448 | |
3449 | |
3450 | auto OrderDbgValues = [&](const MachineInstr *A, |
3451 | const MachineInstr *B) -> bool { |
3452 | DebugVariable VarA(A->getDebugVariable(), A->getDebugExpression(), |
3453 | A->getDebugLoc()->getInlinedAt()); |
3454 | DebugVariable VarB(B->getDebugVariable(), B->getDebugExpression(), |
3455 | B->getDebugLoc()->getInlinedAt()); |
3456 | return AllVarsNumbering.find(VarA)->second < |
3457 | AllVarsNumbering.find(VarB)->second; |
3458 | }; |
3459 | |
3460 | |
3461 | |
3462 | |
3463 | for (auto &P : TTracker->Transfers) { |
3464 | |
3465 | llvm::sort(P.Insts, OrderDbgValues); |
3466 | |
3467 | if (P.MBB) { |
3468 | MachineBasicBlock &MBB = *P.MBB; |
3469 | for (auto *MI : P.Insts) { |
3470 | MBB.insert(P.Pos, MI); |
3471 | } |
3472 | } else { |
3473 | |
3474 | |
3475 | if (P.Pos->isTerminator()) |
3476 | continue; |
3477 | |
3478 | MachineBasicBlock &MBB = *P.Pos->getParent(); |
3479 | for (auto *MI : P.Insts) { |
3480 | MBB.insertAfterBundle(P.Pos, MI); |
3481 | } |
3482 | } |
3483 | } |
3484 | } |
3485 | |
3486 | void InstrRefBasedLDV::initialSetup(MachineFunction &MF) { |
3487 | |
3488 | auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool { |
3489 | if (const DebugLoc &DL = MI.getDebugLoc()) |
3490 | return DL.getLine() != 0; |
3491 | return false; |
3492 | }; |
3493 | |
3494 | for (auto &MBB : MF) |
3495 | if (none_of(MBB.instrs(), hasNonArtificialLocation)) |
3496 | ArtificialBlocks.insert(&MBB); |
3497 | |
3498 | |
3499 | ReversePostOrderTraversal<MachineFunction *> RPOT(&MF); |
3500 | unsigned int RPONumber = 0; |
3501 | for (MachineBasicBlock *MBB : RPOT) { |
3502 | OrderToBB[RPONumber] = MBB; |
3503 | BBToOrder[MBB] = RPONumber; |
3504 | BBNumToRPO[MBB->getNumber()] = RPONumber; |
3505 | ++RPONumber; |
3506 | } |
3507 | |
3508 | |
3509 | llvm::sort(MF.DebugValueSubstitutions); |
3510 | |
3511 | #ifdef EXPENSIVE_CHECKS |
3512 | |
3513 | |
3514 | if (MF.DebugValueSubstitutions.size() > 2) { |
3515 | for (auto It = MF.DebugValueSubstitutions.begin(); |
3516 | It != std::prev(MF.DebugValueSubstitutions.end()); ++It) { |
3517 | assert(It->Src != std::next(It)->Src && "Duplicate variable location " |
3518 | "substitution seen"); |
3519 | } |
3520 | } |
3521 | #endif |
3522 | } |
3523 | |
3524 | |
3525 | |
3526 | bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF, |
3527 | TargetPassConfig *TPC) { |
3528 | |
3529 | if (!MF.getFunction().getSubprogram()) |
| 1 | Assuming the condition is false | |
|
| |
3530 | return false; |
3531 | |
3532 | LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n"); |
| 3 | | Loop condition is false. Exiting loop | |
|
3533 | this->TPC = TPC; |
3534 | |
3535 | TRI = MF.getSubtarget().getRegisterInfo(); |
3536 | TII = MF.getSubtarget().getInstrInfo(); |
3537 | TFI = MF.getSubtarget().getFrameLowering(); |
3538 | TFI->getCalleeSaves(MF, CalleeSavedRegs); |
3539 | MFI = &MF.getFrameInfo(); |
3540 | LS.initialize(MF); |
3541 | |
3542 | MTracker = |
3543 | new MLocTracker(MF, *TII, *TRI, *MF.getSubtarget().getTargetLowering()); |
3544 | VTracker = nullptr; |
3545 | TTracker = nullptr; |
3546 | |
3547 | SmallVector<MLocTransferMap, 32> MLocTransfer; |
3548 | SmallVector<VLocTracker, 8> vlocs; |
3549 | LiveInsT SavedLiveIns; |
3550 | |
3551 | int MaxNumBlocks = -1; |
3552 | for (auto &MBB : MF) |
3553 | MaxNumBlocks = std::max(MBB.getNumber(), MaxNumBlocks); |
3554 | assert(MaxNumBlocks >= 0); |
3555 | ++MaxNumBlocks; |
3556 | |
3557 | MLocTransfer.resize(MaxNumBlocks); |
3558 | vlocs.resize(MaxNumBlocks); |
3559 | SavedLiveIns.resize(MaxNumBlocks); |
3560 | |
3561 | initialSetup(MF); |
3562 | |
3563 | produceMLocTransferFunction(MF, MLocTransfer, MaxNumBlocks); |
3564 | |
3565 | |
3566 | |
3567 | |
3568 | ValueIDNum **MOutLocs = new ValueIDNum *[MaxNumBlocks]; |
3569 | ValueIDNum **MInLocs = new ValueIDNum *[MaxNumBlocks]; |
| |
3570 | unsigned NumLocs = MTracker->getNumLocs(); |
3571 | for (int i = 0; i < MaxNumBlocks; ++i) { |
| 5 | | Loop condition is false. Execution continues on line 3580 | |
|
3572 | MOutLocs[i] = new ValueIDNum[NumLocs]; |
3573 | MInLocs[i] = new ValueIDNum[NumLocs]; |
3574 | } |
3575 | |
3576 | |
3577 | |
3578 | |
3579 | |
3580 | mlocDataflow(MInLocs, MOutLocs, MLocTransfer); |
3581 | |
3582 | |
3583 | |
3584 | for (auto &DBG_PHI : DebugPHINumToValue) { |
| 6 | | Assuming '__begin1' is not equal to '__end1' | |
|
3585 | |
3586 | ValueIDNum &Num = DBG_PHI.ValueRead; |
3587 | if (!Num.isPHI()) |
| |
3588 | continue; |
3589 | |
3590 | unsigned BlockNo = Num.getBlock(); |
3591 | LocIdx LocNo = Num.getLoc(); |
3592 | Num = MInLocs[BlockNo][LocNo.asU64()]; |
| 8 | | Use of zero-allocated memory |
|
3593 | } |
3594 | |
3595 | llvm::sort(DebugPHINumToValue); |
3596 | |
3597 | |
3598 | |
3599 | for (auto &OrderPair : OrderToBB) { |
3600 | MachineBasicBlock &MBB = *OrderPair.second; |
3601 | CurBB = MBB.getNumber(); |
3602 | VTracker = &vlocs[CurBB]; |
3603 | VTracker->MBB = &MBB; |
3604 | MTracker->loadFromArray(MInLocs[CurBB], CurBB); |
3605 | CurInst = 1; |
3606 | for (auto &MI : MBB) { |
3607 | process(MI, MOutLocs, MInLocs); |
3608 | ++CurInst; |
3609 | } |
3610 | MTracker->reset(); |
3611 | } |
3612 | |
3613 | |
3614 | |
3615 | DenseMap<DebugVariable, unsigned> AllVarsNumbering; |
3616 | |
3617 | |
3618 | DenseMap<const LexicalScope *, SmallSet<DebugVariable, 4>> ScopeToVars; |
3619 | |
3620 | |
3621 | DenseMap<const LexicalScope *, SmallPtrSet<MachineBasicBlock *, 4>> |
3622 | ScopeToBlocks; |
3623 | |
3624 | |
3625 | DenseMap<const LexicalScope *, const DILocation *> ScopeToDILocation; |
3626 | |
3627 | |
3628 | |
3629 | for (unsigned int I = 0; I < OrderToBB.size(); ++I) { |
3630 | auto *MBB = OrderToBB[I]; |
3631 | auto *VTracker = &vlocs[MBB->getNumber()]; |
3632 | |
3633 | for (auto &idx : VTracker->Vars) { |
3634 | const auto &Var = idx.first; |
3635 | const DILocation *ScopeLoc = VTracker->Scopes[Var]; |
3636 | assert(ScopeLoc != nullptr); |
3637 | auto *Scope = LS.findLexicalScope(ScopeLoc); |
3638 | |
3639 | |
3640 | assert(Scope != nullptr); |
3641 | |
3642 | AllVarsNumbering.insert(std::make_pair(Var, AllVarsNumbering.size())); |
3643 | ScopeToVars[Scope].insert(Var); |
3644 | ScopeToBlocks[Scope].insert(VTracker->MBB); |
3645 | ScopeToDILocation[Scope] = ScopeLoc; |
3646 | } |
3647 | } |
3648 | |
3649 | |
3650 | |
3651 | |
3652 | |
3653 | for (auto &P : ScopeToVars) { |
3654 | vlocDataflow(P.first, ScopeToDILocation[P.first], P.second, |
3655 | ScopeToBlocks[P.first], SavedLiveIns, MOutLocs, MInLocs, |
3656 | vlocs); |
3657 | } |
3658 | |
3659 | |
3660 | |
3661 | |
3662 | emitLocations(MF, SavedLiveIns, MOutLocs, MInLocs, AllVarsNumbering, *TPC); |
3663 | |
3664 | for (int Idx = 0; Idx < MaxNumBlocks; ++Idx) { |
3665 | delete[] MOutLocs[Idx]; |
3666 | delete[] MInLocs[Idx]; |
3667 | } |
3668 | delete[] MOutLocs; |
3669 | delete[] MInLocs; |
3670 | |
3671 | |
3672 | bool Changed = TTracker->Transfers.size() != 0; |
3673 | |
3674 | delete MTracker; |
3675 | delete TTracker; |
3676 | MTracker = nullptr; |
3677 | VTracker = nullptr; |
3678 | TTracker = nullptr; |
3679 | |
3680 | ArtificialBlocks.clear(); |
3681 | OrderToBB.clear(); |
3682 | BBToOrder.clear(); |
3683 | BBNumToRPO.clear(); |
3684 | DebugInstrNumToInstr.clear(); |
3685 | DebugPHINumToValue.clear(); |
3686 | |
3687 | return Changed; |
3688 | } |
3689 | |
3690 | LDVImpl *llvm::makeInstrRefBasedLiveDebugValues() { |
3691 | return new InstrRefBasedLDV(); |
3692 | } |
3693 | |
3694 | namespace { |
3695 | class LDVSSABlock; |
3696 | class LDVSSAUpdater; |
3697 | |
3698 | |
3699 | |
3700 | |
3701 | typedef uint64_t BlockValueNum; |
3702 | |
3703 | |
3704 | |
3705 | |
3706 | class LDVSSAPhi { |
3707 | public: |
3708 | SmallVector<std::pair<LDVSSABlock *, BlockValueNum>, 4> IncomingValues; |
3709 | LDVSSABlock *ParentBlock; |
3710 | BlockValueNum PHIValNum; |
3711 | LDVSSAPhi(BlockValueNum PHIValNum, LDVSSABlock *ParentBlock) |
3712 | : ParentBlock(ParentBlock), PHIValNum(PHIValNum) {} |
3713 | |
3714 | LDVSSABlock *getParent() { return ParentBlock; } |
3715 | }; |
3716 | |
3717 | |
3718 | |
3719 | class LDVSSABlockIterator { |
3720 | public: |
3721 | MachineBasicBlock::pred_iterator PredIt; |
3722 | LDVSSAUpdater &Updater; |
3723 | |
3724 | LDVSSABlockIterator(MachineBasicBlock::pred_iterator PredIt, |
3725 | LDVSSAUpdater &Updater) |
3726 | : PredIt(PredIt), Updater(Updater) {} |
3727 | |
3728 | bool operator!=(const LDVSSABlockIterator &OtherIt) const { |
3729 | return OtherIt.PredIt != PredIt; |
3730 | } |
3731 | |
3732 | LDVSSABlockIterator &operator++() { |
3733 | ++PredIt; |
3734 | return *this; |
3735 | } |
3736 | |
3737 | LDVSSABlock *operator*(); |
3738 | }; |
3739 | |
3740 | |
3741 | |
3742 | |
3743 | class LDVSSABlock { |
3744 | public: |
3745 | MachineBasicBlock &BB; |
3746 | LDVSSAUpdater &Updater; |
3747 | using PHIListT = SmallVector<LDVSSAPhi, 1>; |
3748 | |
3749 | PHIListT PHIList; |
3750 | |
3751 | LDVSSABlock(MachineBasicBlock &BB, LDVSSAUpdater &Updater) |
3752 | : BB(BB), Updater(Updater) {} |
3753 | |
3754 | LDVSSABlockIterator succ_begin() { |
3755 | return LDVSSABlockIterator(BB.succ_begin(), Updater); |
3756 | } |
3757 | |
3758 | LDVSSABlockIterator succ_end() { |
3759 | return LDVSSABlockIterator(BB.succ_end(), Updater); |
3760 | } |
3761 | |
3762 | |
3763 | LDVSSAPhi *newPHI(BlockValueNum Value) { |
3764 | PHIList.emplace_back(Value, this); |
3765 | return &PHIList.back(); |
3766 | } |
3767 | |
3768 | |
3769 | PHIListT &phis() { return PHIList; } |
3770 | }; |
3771 | |
3772 | |
3773 | |
3774 | |
3775 | class LDVSSAUpdater { |
3776 | public: |
3777 | |
3778 | DenseMap<BlockValueNum, LDVSSAPhi *> PHIs; |
3779 | |
3780 | |
3781 | DenseMap<MachineBasicBlock *, BlockValueNum> UndefMap; |
3782 | |
3783 | DenseMap<MachineBasicBlock *, LDVSSABlock *> BlockMap; |
3784 | |
3785 | LocIdx Loc; |
3786 | |
3787 | ValueIDNum **MLiveIns; |
3788 | |
3789 | LDVSSAUpdater(LocIdx L, ValueIDNum **MLiveIns) : Loc(L), MLiveIns(MLiveIns) {} |
3790 | |
3791 | void reset() { |
3792 | for (auto &Block : BlockMap) |
3793 | delete Block.second; |
3794 | |
3795 | PHIs.clear(); |
3796 | UndefMap.clear(); |
3797 | BlockMap.clear(); |
3798 | } |
3799 | |
3800 | ~LDVSSAUpdater() { reset(); } |
3801 | |
3802 | |
3803 | |
3804 | LDVSSABlock *getSSALDVBlock(MachineBasicBlock *BB) { |
3805 | auto it = BlockMap.find(BB); |
3806 | if (it == BlockMap.end()) { |
3807 | BlockMap[BB] = new LDVSSABlock(*BB, *this); |
3808 | it = BlockMap.find(BB); |
3809 | } |
3810 | return it->second; |
3811 | } |
3812 | |
3813 | |
3814 | |
3815 | BlockValueNum getValue(LDVSSABlock *LDVBB) { |
3816 | return MLiveIns[LDVBB->BB.getNumber()][Loc.asU64()].asU64(); |
3817 | } |
3818 | }; |
3819 | |
3820 | LDVSSABlock *LDVSSABlockIterator::operator*() { |
3821 | return Updater.getSSALDVBlock(*PredIt); |
3822 | } |
3823 | |
3824 | #ifndef NDEBUG |
3825 | |
3826 | raw_ostream &operator<<(raw_ostream &out, const LDVSSAPhi &PHI) { |
3827 | out << "SSALDVPHI " << PHI.PHIValNum; |
3828 | return out; |
3829 | } |
3830 | |
3831 | #endif |
3832 | |
3833 | } |
3834 | |
3835 | namespace llvm { |
3836 | |
3837 | |
3838 | |
3839 | |
3840 | |
3841 | template <> class SSAUpdaterTraits<LDVSSAUpdater> { |
3842 | public: |
3843 | using BlkT = LDVSSABlock; |
3844 | using ValT = BlockValueNum; |
3845 | using PhiT = LDVSSAPhi; |
3846 | using BlkSucc_iterator = LDVSSABlockIterator; |
3847 | |
3848 | |
3849 | static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); } |
3850 | static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); } |
3851 | |
3852 | |
3853 | class PHI_iterator { |
3854 | private: |
3855 | LDVSSAPhi *PHI; |
3856 | unsigned Idx; |
3857 | |
3858 | public: |
3859 | explicit PHI_iterator(LDVSSAPhi *P) |
3860 | : PHI(P), Idx(0) {} |
3861 | PHI_iterator(LDVSSAPhi *P, bool) |
3862 | : PHI(P), Idx(PHI->IncomingValues.size()) {} |
3863 | |
3864 | PHI_iterator &operator++() { |
3865 | Idx++; |
3866 | return *this; |
3867 | } |
3868 | bool operator==(const PHI_iterator &X) const { return Idx == X.Idx; } |
3869 | bool operator!=(const PHI_iterator &X) const { return !operator==(X); } |
3870 | |
3871 | BlockValueNum getIncomingValue() { return PHI->IncomingValues[Idx].second; } |
3872 | |
3873 | LDVSSABlock *getIncomingBlock() { return PHI->IncomingValues[Idx].first; } |
3874 | }; |
3875 | |
3876 | static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); } |
3877 | |
3878 | static inline PHI_iterator PHI_end(PhiT *PHI) { |
3879 | return PHI_iterator(PHI, true); |
3880 | } |
3881 | |
3882 | |
3883 | |
3884 | static void FindPredecessorBlocks(LDVSSABlock *BB, |
3885 | SmallVectorImpl<LDVSSABlock *> *Preds) { |
3886 | for (MachineBasicBlock::pred_iterator PI = BB->BB.pred_begin(), |
3887 | E = BB->BB.pred_end(); |
3888 | PI != E; ++PI) |
3889 | Preds->push_back(BB->Updater.getSSALDVBlock(*PI)); |
3890 | } |
3891 | |
3892 | |
3893 | |
3894 | |
3895 | static BlockValueNum GetUndefVal(LDVSSABlock *BB, LDVSSAUpdater *Updater) { |
3896 | |
3897 | |
3898 | |
3899 | BlockValueNum Num = ValueIDNum(BB->BB.getNumber(), 0, Updater->Loc).asU64(); |
3900 | Updater->UndefMap[&BB->BB] = Num; |
3901 | return Num; |
3902 | } |
3903 | |
3904 | |
3905 | |
3906 | |
3907 | |
3908 | |
3909 | static BlockValueNum CreateEmptyPHI(LDVSSABlock *BB, unsigned NumPreds, |
3910 | LDVSSAUpdater *Updater) { |
3911 | BlockValueNum PHIValNum = Updater->getValue(BB); |
3912 | LDVSSAPhi *PHI = BB->newPHI(PHIValNum); |
3913 | Updater->PHIs[PHIValNum] = PHI; |
3914 | return PHIValNum; |
3915 | } |
3916 | |
3917 | |
3918 | |
3919 | static void AddPHIOperand(LDVSSAPhi *PHI, BlockValueNum Val, LDVSSABlock *Pred) { |
3920 | PHI->IncomingValues.push_back(std::make_pair(Pred, Val)); |
3921 | } |
3922 | |
3923 | |
3924 | |
3925 | static LDVSSAPhi *ValueIsPHI(BlockValueNum Val, LDVSSAUpdater *Updater) { |
3926 | auto PHIIt = Updater->PHIs.find(Val); |
3927 | if (PHIIt == Updater->PHIs.end()) |
3928 | return nullptr; |
3929 | return PHIIt->second; |
3930 | } |
3931 | |
3932 | |
3933 | |
3934 | static LDVSSAPhi *ValueIsNewPHI(BlockValueNum Val, LDVSSAUpdater *Updater) { |
3935 | LDVSSAPhi *PHI = ValueIsPHI(Val, Updater); |
3936 | if (PHI && PHI->IncomingValues.size() == 0) |
3937 | return PHI; |
3938 | return nullptr; |
3939 | } |
3940 | |
3941 | |
3942 | |
3943 | static BlockValueNum GetPHIValue(LDVSSAPhi *PHI) { return PHI->PHIValNum; } |
3944 | }; |
3945 | |
3946 | } |
3947 | |
3948 | Optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIs(MachineFunction &MF, |
3949 | ValueIDNum **MLiveOuts, |
3950 | ValueIDNum **MLiveIns, |
3951 | MachineInstr &Here, |
3952 | uint64_t InstrNum) { |
3953 | |
3954 | |
3955 | auto RangePair = std::equal_range(DebugPHINumToValue.begin(), |
3956 | DebugPHINumToValue.end(), InstrNum); |
3957 | auto LowerIt = RangePair.first; |
3958 | auto UpperIt = RangePair.second; |
3959 | |
3960 | |
3961 | if (LowerIt == UpperIt) |
3962 | return None; |
3963 | |
3964 | |
3965 | if (std::distance(LowerIt, UpperIt) == 1) |
3966 | return LowerIt->ValueRead; |
3967 | |
3968 | auto DBGPHIRange = make_range(LowerIt, UpperIt); |
3969 | |
3970 | |
3971 | |
3972 | |
3973 | |
3974 | LocIdx Loc = LowerIt->ReadLoc; |
3975 | |
3976 | |
3977 | |
3978 | |
3979 | |
3980 | |
3981 | |
3982 | |
3983 | LDVSSAUpdater Updater(Loc, MLiveIns); |
3984 | |
3985 | DenseMap<LDVSSABlock *, BlockValueNum> AvailableValues; |
3986 | |
3987 | SmallVector<LDVSSAPhi *, 8> CreatedPHIs; |
3988 | |
3989 | |
3990 | |
3991 | for (const auto &DBG_PHI : DBGPHIRange) { |
3992 | LDVSSABlock *Block = Updater.getSSALDVBlock(DBG_PHI.MBB); |
3993 | const ValueIDNum &Num = DBG_PHI.ValueRead; |
3994 | AvailableValues.insert(std::make_pair(Block, Num.asU64())); |
3995 | } |
3996 | |
3997 | LDVSSABlock *HereBlock = Updater.getSSALDVBlock(Here.getParent()); |
3998 | const auto &AvailIt = AvailableValues.find(HereBlock); |
3999 | if (AvailIt != AvailableValues.end()) { |
4000 | |
4001 | |
4002 | return ValueIDNum::fromU64(AvailIt->second); |
4003 | } |
4004 | |
4005 | |
4006 | |
4007 | SSAUpdaterImpl<LDVSSAUpdater> Impl(&Updater, &AvailableValues, &CreatedPHIs); |
4008 | BlockValueNum ResultInt = Impl.GetValue(Updater.getSSALDVBlock(Here.getParent())); |
4009 | ValueIDNum Result = ValueIDNum::fromU64(ResultInt); |
4010 | |
4011 | |
4012 | |
4013 | |
4014 | |
4015 | |
4016 | |
4017 | |
4018 | |
4019 | |
4020 | |
4021 | |
4022 | DenseMap<LDVSSABlock *, ValueIDNum> ValidatedValues; |
4023 | |
4024 | |
4025 | for (const auto &DBG_PHI : DBGPHIRange) { |
4026 | LDVSSABlock *Block = Updater.getSSALDVBlock(DBG_PHI.MBB); |
4027 | const ValueIDNum &Num = DBG_PHI.ValueRead; |
4028 | ValidatedValues.insert(std::make_pair(Block, Num)); |
4029 | } |
4030 | |
4031 | |
4032 | SmallVector<LDVSSAPhi *, 8> SortedPHIs; |
4033 | for (auto &PHI : CreatedPHIs) |
4034 | SortedPHIs.push_back(PHI); |
4035 | |
4036 | std::sort( |
4037 | SortedPHIs.begin(), SortedPHIs.end(), [&](LDVSSAPhi *A, LDVSSAPhi *B) { |
4038 | return BBToOrder[&A->getParent()->BB] < BBToOrder[&B->getParent()->BB]; |
4039 | }); |
4040 | |
4041 | for (auto &PHI : SortedPHIs) { |
4042 | ValueIDNum ThisBlockValueNum = |
4043 | MLiveIns[PHI->ParentBlock->BB.getNumber()][Loc.asU64()]; |
4044 | |
4045 | |
4046 | for (auto &PHIIt : PHI->IncomingValues) { |
4047 | |
4048 | if (Updater.UndefMap.find(&PHIIt.first->BB) != Updater.UndefMap.end()) |
4049 | return None; |
4050 | |
4051 | ValueIDNum ValueToCheck; |
4052 | ValueIDNum *BlockLiveOuts = MLiveOuts[PHIIt.first->BB.getNumber()]; |
4053 | |
4054 | auto VVal = ValidatedValues.find(PHIIt.first); |
4055 | if (VVal == ValidatedValues.end()) { |
4056 | |
4057 | |
4058 | |
4059 | |
4060 | ValueToCheck = ThisBlockValueNum; |
4061 | } else { |
4062 | |
4063 | |
4064 | ValueToCheck = VVal->second; |
4065 | } |
4066 | |
4067 | if (BlockLiveOuts[Loc.asU64()] != ValueToCheck) |
4068 | return None; |
4069 | } |
4070 | |
4071 | |
4072 | ValidatedValues.insert({PHI->ParentBlock, ThisBlockValueNum}); |
4073 | } |
4074 | |
4075 | |
4076 | |
4077 | return Result; |
4078 | } |