clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -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 -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/CodeGen -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include -D NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/CodeGen -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-09-04-040900-46481-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/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 | MachineInstr *MI = |
1385 | MTracker->emitLoc(Dst, Var, ActiveVLocIt->second.Properties); |
1386 | PendingDbgValues.push_back(MI); |
1387 | } |
1388 | ActiveMLocs[Src].clear(); |
1389 | flushDbgValues(Pos, nullptr); |
1390 | |
1391 | |
1392 | |
1393 | if (EmulateOldLDV) |
1394 | VarLocs[Src.asU64()] = ValueIDNum::EmptyValue; |
1395 | } |
1396 | |
1397 | MachineInstrBuilder emitMOLoc(const MachineOperand &MO, |
1398 | const DebugVariable &Var, |
1399 | const DbgValueProperties &Properties) { |
1400 | DebugLoc DL = DILocation::get(Var.getVariable()->getContext(), 0, 0, |
1401 | Var.getVariable()->getScope(), |
1402 | const_cast<DILocation *>(Var.getInlinedAt())); |
1403 | auto MIB = BuildMI(MF, DL, TII->get(TargetOpcode::DBG_VALUE)); |
1404 | MIB.add(MO); |
1405 | if (Properties.Indirect) |
1406 | MIB.addImm(0); |
1407 | else |
1408 | MIB.addReg(0); |
1409 | MIB.addMetadata(Var.getVariable()); |
1410 | MIB.addMetadata(Properties.DIExpr); |
1411 | return MIB; |
1412 | } |
1413 | }; |
1414 | |
1415 | class InstrRefBasedLDV : public LDVImpl { |
1416 | private: |
1417 | using FragmentInfo = DIExpression::FragmentInfo; |
1418 | using OptFragmentInfo = Optional<DIExpression::FragmentInfo>; |
1419 | |
1420 | |
1421 | |
1422 | using VarToFragments = |
1423 | DenseMap<const DILocalVariable *, SmallSet<FragmentInfo, 4>>; |
1424 | |
1425 | |
1426 | |
1427 | using MLocTransferMap = std::map<LocIdx, ValueIDNum>; |
1428 | |
1429 | |
1430 | |
1431 | using LiveIdxT = |
1432 | DenseMap<const MachineBasicBlock *, DenseMap<DebugVariable, DbgValue> *>; |
1433 | |
1434 | using VarAndLoc = std::pair<DebugVariable, DbgValue>; |
1435 | |
1436 | |
1437 | using InValueT = std::pair<MachineBasicBlock *, DbgValue *>; |
1438 | |
1439 | |
1440 | |
1441 | using LiveInsT = SmallVector<SmallVector<VarAndLoc, 8>, 8>; |
1442 | |
1443 | const TargetRegisterInfo *TRI; |
1444 | const TargetInstrInfo *TII; |
1445 | const TargetFrameLowering *TFI; |
1446 | const MachineFrameInfo *MFI; |
1447 | BitVector CalleeSavedRegs; |
1448 | LexicalScopes LS; |
1449 | TargetPassConfig *TPC; |
1450 | |
1451 | |
1452 | |
1453 | MLocTracker *MTracker; |
1454 | |
1455 | |
1456 | unsigned CurBB; |
1457 | |
1458 | |
1459 | unsigned CurInst; |
1460 | |
1461 | |
1462 | |
1463 | |
1464 | VLocTracker *VTracker; |
1465 | |
1466 | |
1467 | |
1468 | |
1469 | TransferTracker *TTracker; |
1470 | |
1471 | |
1472 | |
1473 | SmallPtrSet<const MachineBasicBlock *, 16> ArtificialBlocks; |
1474 | |
1475 | |
1476 | DenseMap<unsigned int, MachineBasicBlock *> OrderToBB; |
1477 | DenseMap<MachineBasicBlock *, unsigned int> BBToOrder; |
1478 | DenseMap<unsigned, unsigned> BBNumToRPO; |
1479 | |
1480 | |
1481 | using InstAndNum = std::pair<const MachineInstr *, unsigned>; |
1482 | |
1483 | |
1484 | |
1485 | std::map<uint64_t, InstAndNum> DebugInstrNumToInstr; |
1486 | |
1487 | |
1488 | class DebugPHIRecord { |
1489 | public: |
1490 | uint64_t InstrNum; |
1491 | MachineBasicBlock *MBB; |
1492 | ValueIDNum ValueRead; |
1493 | LocIdx ReadLoc; |
1494 | |
1495 | operator unsigned() const { return InstrNum; } |
1496 | }; |
1497 | |
1498 | |
1499 | |
1500 | |
1501 | |
1502 | SmallVector<DebugPHIRecord, 32> DebugPHINumToValue; |
1503 | |
1504 | |
1505 | OverlapMap OverlapFragments; |
1506 | VarToFragments SeenFragments; |
1507 | |
1508 | |
1509 | bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF); |
1510 | |
1511 | |
1512 | |
1513 | |
1514 | |
1515 | |
1516 | |
1517 | bool isLocationSpill(const MachineInstr &MI, MachineFunction *MF, |
1518 | unsigned &Reg); |
1519 | |
1520 | |
1521 | |
1522 | Optional<SpillLoc> isRestoreInstruction(const MachineInstr &MI, |
1523 | MachineFunction *MF, unsigned &Reg); |
1524 | |
1525 | |
1526 | |
1527 | SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI); |
1528 | |
1529 | |
1530 | void process(MachineInstr &MI, ValueIDNum **MLiveOuts = nullptr, |
1531 | ValueIDNum **MLiveIns = nullptr); |
1532 | |
1533 | |
1534 | |
1535 | bool transferDebugValue(const MachineInstr &MI); |
1536 | |
1537 | |
1538 | |
1539 | bool transferDebugInstrRef(MachineInstr &MI, ValueIDNum **MLiveOuts, |
1540 | ValueIDNum **MLiveIns); |
1541 | |
1542 | |
1543 | |
1544 | |
1545 | bool transferDebugPHI(MachineInstr &MI); |
1546 | |
1547 | |
1548 | |
1549 | bool transferRegisterCopy(MachineInstr &MI); |
1550 | |
1551 | |
1552 | |
1553 | bool transferSpillOrRestoreInst(MachineInstr &MI); |
1554 | |
1555 | |
1556 | void transferRegisterDef(MachineInstr &MI); |
1557 | |
1558 | |
1559 | |
1560 | void performCopy(Register Src, Register Dst); |
1561 | |
1562 | void accumulateFragmentMap(MachineInstr &MI); |
1563 | |
1564 | |
1565 | |
1566 | |
1567 | |
1568 | |
1569 | |
1570 | |
1571 | Optional<ValueIDNum> resolveDbgPHIs(MachineFunction &MF, |
1572 | ValueIDNum **MLiveOuts, |
1573 | ValueIDNum **MLiveIns, MachineInstr &Here, |
1574 | uint64_t InstrNum); |
1575 | |
1576 | |
1577 | |
1578 | |
1579 | |
1580 | void |
1581 | produceMLocTransferFunction(MachineFunction &MF, |
1582 | SmallVectorImpl<MLocTransferMap> &MLocTransfer, |
1583 | unsigned MaxNumBlocks); |
1584 | |
1585 | |
1586 | |
1587 | |
1588 | |
1589 | |
1590 | void mlocDataflow(ValueIDNum **MInLocs, ValueIDNum **MOutLocs, |
1591 | SmallVectorImpl<MLocTransferMap> &MLocTransfer); |
1592 | |
1593 | |
1594 | |
1595 | |
1596 | |
1597 | |
1598 | |
1599 | |
1600 | std::tuple<bool, bool> |
1601 | mlocJoin(MachineBasicBlock &MBB, |
1602 | SmallPtrSet<const MachineBasicBlock *, 16> &Visited, |
1603 | ValueIDNum **OutLocs, ValueIDNum *InLocs); |
1604 | |
1605 | |
1606 | |
1607 | |
1608 | |
1609 | |
1610 | |
1611 | |
1612 | |
1613 | |
1614 | |
1615 | |
1616 | |
1617 | |
1618 | void vlocDataflow(const LexicalScope *Scope, const DILocation *DILoc, |
1619 | const SmallSet<DebugVariable, 4> &VarsWeCareAbout, |
1620 | SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks, |
1621 | LiveInsT &Output, ValueIDNum **MOutLocs, |
1622 | ValueIDNum **MInLocs, |
1623 | SmallVectorImpl<VLocTracker> &AllTheVLocs); |
1624 | |
1625 | |
1626 | |
1627 | |
1628 | |
1629 | |
1630 | |
1631 | |
1632 | |
1633 | |
1634 | std::tuple<bool, bool> |
1635 | vlocJoin(MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, LiveIdxT &VLOCInLocs, |
1636 | SmallPtrSet<const MachineBasicBlock *, 16> *VLOCVisited, |
1637 | unsigned BBNum, const SmallSet<DebugVariable, 4> &AllVars, |
1638 | ValueIDNum **MOutLocs, ValueIDNum **MInLocs, |
1639 | SmallPtrSet<const MachineBasicBlock *, 8> &InScopeBlocks, |
1640 | SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore, |
1641 | DenseMap<DebugVariable, DbgValue> &InLocsT); |
1642 | |
1643 | |
1644 | |
1645 | |
1646 | |
1647 | |
1648 | |
1649 | |
1650 | |
1651 | bool vlocDowngradeLattice(const MachineBasicBlock &MBB, |
1652 | const DbgValue &OldLiveInLocation, |
1653 | const SmallVectorImpl<InValueT> &Values, |
1654 | unsigned CurBlockRPONum); |
1655 | |
1656 | |
1657 | |
1658 | |
1659 | |
1660 | |
1661 | |
1662 | |
1663 | |
1664 | std::tuple<Optional<ValueIDNum>, bool> |
1665 | pickVPHILoc(MachineBasicBlock &MBB, const DebugVariable &Var, |
1666 | const LiveIdxT &LiveOuts, ValueIDNum **MOutLocs, |
1667 | ValueIDNum **MInLocs, |
1668 | const SmallVectorImpl<MachineBasicBlock *> &BlockOrders); |
1669 | |
1670 | |
1671 | |
1672 | |
1673 | |
1674 | |
1675 | |
1676 | |
1677 | void emitLocations(MachineFunction &MF, LiveInsT SavedLiveIns, |
1678 | ValueIDNum **MOutLocs, ValueIDNum **MInLocs, |
1679 | DenseMap<DebugVariable, unsigned> &AllVarsNumbering, |
1680 | const TargetPassConfig &TPC); |
1681 | |
1682 | |
1683 | |
1684 | void initialSetup(MachineFunction &MF); |
1685 | |
1686 | bool ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC, |
1687 | unsigned InputBBLimit, unsigned InputDbgValLimit) 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 | |
1763 | |
1764 | |
1765 | if (MI.isDebugValueList()) { |
1766 | if (VTracker) |
1767 | VTracker->defVar(MI, Properties, None); |
1768 | if (TTracker) |
1769 | TTracker->redefVar(MI, Properties, None); |
1770 | return true; |
1771 | } |
1772 | |
1773 | const MachineOperand &MO = MI.getOperand(0); |
1774 | |
1775 | |
1776 | |
1777 | if (MO.isReg() && MO.getReg() != 0) |
1778 | (void)MTracker->readReg(MO.getReg()); |
1779 | |
1780 | |
1781 | |
1782 | |
1783 | if (VTracker) { |
1784 | if (MO.isReg()) { |
1785 | |
1786 | |
1787 | if (MO.getReg()) |
1788 | VTracker->defVar(MI, Properties, MTracker->readReg(MO.getReg())); |
1789 | else |
1790 | VTracker->defVar(MI, Properties, None); |
1791 | } else if (MI.getOperand(0).isImm() || MI.getOperand(0).isFPImm() || |
1792 | MI.getOperand(0).isCImm()) { |
1793 | VTracker->defVar(MI, MI.getOperand(0)); |
1794 | } |
1795 | } |
1796 | |
1797 | |
1798 | |
1799 | if (TTracker) |
1800 | TTracker->redefVar(MI); |
1801 | return true; |
1802 | } |
1803 | |
1804 | bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI, |
1805 | ValueIDNum **MLiveOuts, |
1806 | ValueIDNum **MLiveIns) { |
1807 | if (!MI.isDebugRef()) |
1808 | return false; |
1809 | |
1810 | |
1811 | |
1812 | if (!VTracker) |
1813 | return false; |
1814 | |
1815 | unsigned InstNo = MI.getOperand(0).getImm(); |
1816 | unsigned OpNo = MI.getOperand(1).getImm(); |
1817 | |
1818 | const DILocalVariable *Var = MI.getDebugVariable(); |
1819 | const DIExpression *Expr = MI.getDebugExpression(); |
1820 | const DILocation *DebugLoc = MI.getDebugLoc(); |
1821 | const DILocation *InlinedAt = DebugLoc->getInlinedAt(); |
1822 | assert(Var->isValidLocationForIntrinsic(DebugLoc) && |
1823 | "Expected inlined-at fields to agree"); |
1824 | |
1825 | DebugVariable V(Var, Expr, InlinedAt); |
1826 | |
1827 | auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get()); |
1828 | if (Scope == nullptr) |
1829 | return true; |
1830 | |
1831 | const MachineFunction &MF = *MI.getParent()->getParent(); |
1832 | |
1833 | |
1834 | |
1835 | |
1836 | |
1837 | |
1838 | |
1839 | auto SoughtSub = |
1840 | MachineFunction::DebugSubstitution({InstNo, OpNo}, {0, 0}, 0); |
1841 | |
1842 | SmallVector<unsigned, 4> SeenSubregs; |
1843 | auto LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub); |
1844 | while (LowerBoundIt != MF.DebugValueSubstitutions.end() && |
1845 | LowerBoundIt->Src == SoughtSub.Src) { |
1846 | std::tie(InstNo, OpNo) = LowerBoundIt->Dest; |
1847 | SoughtSub.Src = LowerBoundIt->Dest; |
1848 | if (unsigned Subreg = LowerBoundIt->Subreg) |
1849 | SeenSubregs.push_back(Subreg); |
1850 | LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub); |
1851 | } |
1852 | |
1853 | |
1854 | |
1855 | Optional<ValueIDNum> NewID = None; |
1856 | |
1857 | |
1858 | |
1859 | auto InstrIt = DebugInstrNumToInstr.find(InstNo); |
1860 | auto PHIIt = std::lower_bound(DebugPHINumToValue.begin(), |
1861 | DebugPHINumToValue.end(), InstNo); |
1862 | if (InstrIt != DebugInstrNumToInstr.end()) { |
1863 | const MachineInstr &TargetInstr = *InstrIt->second.first; |
1864 | uint64_t BlockNo = TargetInstr.getParent()->getNumber(); |
1865 | |
1866 | |
1867 | assert(OpNo < TargetInstr.getNumOperands()); |
1868 | const MachineOperand &MO = TargetInstr.getOperand(OpNo); |
1869 | |
1870 | |
1871 | assert(MO.isReg() && MO.isDef()); |
1872 | |
1873 | unsigned LocID = MTracker->getLocID(MO.getReg(), false); |
1874 | LocIdx L = MTracker->LocIDToLocIdx[LocID]; |
1875 | NewID = ValueIDNum(BlockNo, InstrIt->second.second, L); |
1876 | } else if (PHIIt != DebugPHINumToValue.end() && PHIIt->InstrNum == InstNo) { |
1877 | |
1878 | |
1879 | NewID = resolveDbgPHIs(*MI.getParent()->getParent(), MLiveOuts, MLiveIns, |
1880 | MI, InstNo); |
1881 | } |
1882 | |
1883 | |
1884 | |
1885 | |
1886 | |
1887 | |
1888 | |
1889 | |
1890 | |
1891 | |
1892 | if (NewID && !SeenSubregs.empty()) { |
1893 | unsigned Offset = 0; |
1894 | unsigned Size = 0; |
1895 | |
1896 | |
1897 | |
1898 | |
1899 | |
1900 | for (unsigned Subreg : reverse(SeenSubregs)) { |
1901 | unsigned ThisSize = TRI->getSubRegIdxSize(Subreg); |
1902 | unsigned ThisOffset = TRI->getSubRegIdxOffset(Subreg); |
1903 | Offset += ThisOffset; |
1904 | Size = (Size == 0) ? ThisSize : std::min(Size, ThisSize); |
1905 | } |
1906 | |
1907 | |
1908 | |
1909 | |
1910 | |
1911 | LocIdx L = NewID->getLoc(); |
1912 | if (NewID && !MTracker->isSpill(L)) { |
1913 | |
1914 | |
1915 | Register Reg = MTracker->LocIdxToLocID[L]; |
1916 | const TargetRegisterClass *TRC = nullptr; |
1917 | for (auto *TRCI : TRI->regclasses()) |
1918 | if (TRCI->contains(Reg)) |
1919 | TRC = TRCI; |
1920 | assert(TRC && "Couldn't find target register class?"); |
1921 | |
1922 | |
1923 | |
1924 | unsigned MainRegSize = TRI->getRegSizeInBits(*TRC); |
1925 | if (Size != MainRegSize || Offset) { |
1926 | |
1927 | Register NewReg = 0; |
1928 | for (MCSubRegIterator SRI(Reg, TRI, false); SRI.isValid(); ++SRI) { |
1929 | unsigned Subreg = TRI->getSubRegIndex(Reg, *SRI); |
1930 | unsigned SubregSize = TRI->getSubRegIdxSize(Subreg); |
1931 | unsigned SubregOffset = TRI->getSubRegIdxOffset(Subreg); |
1932 | if (SubregSize == Size && SubregOffset == Offset) { |
1933 | NewReg = *SRI; |
1934 | break; |
1935 | } |
1936 | } |
1937 | |
1938 | |
1939 | if (!NewReg) { |
1940 | NewID = None; |
1941 | } else { |
1942 | |
1943 | |
1944 | LocIdx NewLoc = MTracker->lookupOrTrackRegister(NewReg); |
1945 | NewID = ValueIDNum(NewID->getBlock(), NewID->getInst(), NewLoc); |
1946 | } |
1947 | } |
1948 | } else { |
1949 | |
1950 | NewID = None; |
1951 | } |
1952 | } |
1953 | |
1954 | |
1955 | |
1956 | |
1957 | |
1958 | DbgValueProperties Properties(Expr, false); |
1959 | VTracker->defVar(MI, Properties, NewID); |
1960 | |
1961 | |
1962 | |
1963 | if (!TTracker) |
1964 | return true; |
1965 | |
1966 | |
1967 | |
1968 | Optional<LocIdx> FoundLoc = None; |
1969 | for (auto Location : MTracker->locations()) { |
1970 | LocIdx CurL = Location.Idx; |
1971 | ValueIDNum ID = MTracker->LocIdxToIDNum[CurL]; |
1972 | if (NewID && ID == NewID) { |
1973 | |
1974 | |
1975 | if (!FoundLoc) { |
1976 | FoundLoc = CurL; |
1977 | continue; |
1978 | } |
1979 | |
1980 | if (MTracker->isSpill(CurL)) |
1981 | FoundLoc = CurL; |
1982 | else if (!MTracker->isSpill(*FoundLoc) && |
1983 | !MTracker->isSpill(CurL) && |
1984 | !isCalleeSaved(*FoundLoc) && |
1985 | isCalleeSaved(CurL)) |
1986 | FoundLoc = CurL; |
1987 | } |
1988 | } |
1989 | |
1990 | |
1991 | TTracker->redefVar(MI, Properties, FoundLoc); |
1992 | |
1993 | |
1994 | |
1995 | if (!FoundLoc && NewID && NewID->getBlock() == CurBB && |
1996 | NewID->getInst() > CurInst) |
1997 | TTracker->addUseBeforeDef(V, {MI.getDebugExpression(), false}, *NewID); |
1998 | |
1999 | |
2000 | |
2001 | |
2002 | |
2003 | MachineInstr *DbgMI = MTracker->emitLoc(FoundLoc, V, Properties); |
2004 | TTracker->PendingDbgValues.push_back(DbgMI); |
2005 | TTracker->flushDbgValues(MI.getIterator(), nullptr); |
2006 | return true; |
2007 | } |
2008 | |
2009 | bool InstrRefBasedLDV::transferDebugPHI(MachineInstr &MI) { |
2010 | if (!MI.isDebugPHI()) |
2011 | return false; |
2012 | |
2013 | |
2014 | if (VTracker || TTracker) |
2015 | return true; |
2016 | |
2017 | |
2018 | |
2019 | const MachineOperand &MO = MI.getOperand(0); |
2020 | unsigned InstrNum = MI.getOperand(1).getImm(); |
2021 | |
2022 | if (MO.isReg()) { |
2023 | |
2024 | |
2025 | Register Reg = MO.getReg(); |
2026 | ValueIDNum Num = MTracker->readReg(Reg); |
2027 | auto PHIRec = DebugPHIRecord( |
2028 | {InstrNum, MI.getParent(), Num, MTracker->lookupOrTrackRegister(Reg)}); |
2029 | DebugPHINumToValue.push_back(PHIRec); |
2030 | } else { |
2031 | |
2032 | assert(MO.isFI()); |
2033 | unsigned FI = MO.getIndex(); |
2034 | |
2035 | |
2036 | |
2037 | if (MFI->isDeadObjectIndex(FI)) |
2038 | return true; |
2039 | |
2040 | |
2041 | Register Base; |
2042 | StackOffset Offs = TFI->getFrameIndexReference(*MI.getMF(), FI, Base); |
2043 | SpillLoc SL = {Base, Offs}; |
2044 | Optional<ValueIDNum> Num = MTracker->readSpill(SL); |
2045 | |
2046 | if (!Num) |
2047 | |
2048 | return true; |
2049 | |
2050 | |
2051 | auto DbgPHI = DebugPHIRecord( |
2052 | {InstrNum, MI.getParent(), *Num, *MTracker->getSpillMLoc(SL)}); |
2053 | DebugPHINumToValue.push_back(DbgPHI); |
2054 | } |
2055 | |
2056 | return true; |
2057 | } |
2058 | |
2059 | void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) { |
2060 | |
2061 | |
2062 | if (MI.isImplicitDef()) { |
2063 | |
2064 | |
2065 | |
2066 | |
2067 | ValueIDNum Num = MTracker->readReg(MI.getOperand(0).getReg()); |
2068 | |
2069 | if (Num.getLoc() != 0) |
2070 | return; |
2071 | |
2072 | } else if (MI.isMetaInstruction()) |
2073 | return; |
2074 | |
2075 | MachineFunction *MF = MI.getMF(); |
2076 | const TargetLowering *TLI = MF->getSubtarget().getTargetLowering(); |
2077 | Register SP = TLI->getStackPointerRegisterToSaveRestore(); |
2078 | |
2079 | |
2080 | |
2081 | |
2082 | SmallSet<uint32_t, 32> DeadRegs; |
2083 | SmallVector<const uint32_t *, 4> RegMasks; |
2084 | SmallVector<const MachineOperand *, 4> RegMaskPtrs; |
2085 | for (const MachineOperand &MO : MI.operands()) { |
2086 | |
2087 | if (MO.isReg() && MO.isDef() && MO.getReg() && |
2088 | Register::isPhysicalRegister(MO.getReg()) && |
2089 | !(MI.isCall() && MO.getReg() == SP)) { |
2090 | |
2091 | for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI) |
2092 | |
2093 | DeadRegs.insert(*RAI); |
2094 | } else if (MO.isRegMask()) { |
2095 | RegMasks.push_back(MO.getRegMask()); |
2096 | RegMaskPtrs.push_back(&MO); |
2097 | } |
2098 | } |
2099 | |
2100 | |
2101 | for (uint32_t DeadReg : DeadRegs) |
2102 | MTracker->defReg(DeadReg, CurBB, CurInst); |
2103 | |
2104 | for (auto *MO : RegMaskPtrs) |
2105 | MTracker->writeRegMask(MO, CurBB, CurInst); |
2106 | |
2107 | if (!TTracker) |
2108 | return; |
2109 | |
2110 | |
2111 | |
2112 | |
2113 | |
2114 | |
2115 | for (uint32_t DeadReg : DeadRegs) { |
2116 | LocIdx Loc = MTracker->lookupOrTrackRegister(DeadReg); |
2117 | TTracker->clobberMloc(Loc, MI.getIterator(), false); |
2118 | } |
2119 | |
2120 | |
2121 | |
2122 | for (auto L : MTracker->locations()) { |
2123 | |
2124 | if (MTracker->isSpill(L.Idx)) |
2125 | continue; |
2126 | |
2127 | Register Reg = MTracker->LocIdxToLocID[L.Idx]; |
2128 | for (auto *MO : RegMaskPtrs) |
2129 | if (MO->clobbersPhysReg(Reg)) |
2130 | TTracker->clobberMloc(L.Idx, MI.getIterator(), false); |
2131 | } |
2132 | } |
2133 | |
2134 | void InstrRefBasedLDV::performCopy(Register SrcRegNum, Register DstRegNum) { |
2135 | ValueIDNum SrcValue = MTracker->readReg(SrcRegNum); |
2136 | |
2137 | MTracker->setReg(DstRegNum, SrcValue); |
2138 | |
2139 | |
2140 | |
2141 | |
2142 | |
2143 | for (MCSuperRegIterator SRI(DstRegNum, TRI); SRI.isValid(); ++SRI) |
2144 | MTracker->defReg(*SRI, CurBB, CurInst); |
2145 | |
2146 | |
2147 | |
2148 | |
2149 | if (EmulateOldLDV) { |
2150 | for (MCSubRegIndexIterator DRI(DstRegNum, TRI); DRI.isValid(); ++DRI) |
2151 | MTracker->defReg(DRI.getSubReg(), CurBB, CurInst); |
2152 | return; |
2153 | } |
2154 | |
2155 | |
2156 | |
2157 | |
2158 | for (MCSubRegIndexIterator SRI(SrcRegNum, TRI); SRI.isValid(); ++SRI) { |
2159 | unsigned SrcSubReg = SRI.getSubReg(); |
2160 | unsigned SubRegIdx = SRI.getSubRegIndex(); |
2161 | unsigned DstSubReg = TRI->getSubReg(DstRegNum, SubRegIdx); |
2162 | if (!DstSubReg) |
2163 | continue; |
2164 | |
2165 | |
2166 | |
2167 | |
2168 | |
2169 | (void)MTracker->readReg(SrcSubReg); |
2170 | LocIdx SrcL = MTracker->getRegMLoc(SrcSubReg); |
2171 | assert(SrcL.asU64()); |
2172 | (void)MTracker->readReg(DstSubReg); |
2173 | LocIdx DstL = MTracker->getRegMLoc(DstSubReg); |
2174 | assert(DstL.asU64()); |
2175 | (void)DstL; |
2176 | ValueIDNum CpyValue = {SrcValue.getBlock(), SrcValue.getInst(), SrcL}; |
2177 | |
2178 | MTracker->setReg(DstSubReg, CpyValue); |
2179 | } |
2180 | } |
2181 | |
2182 | bool InstrRefBasedLDV::isSpillInstruction(const MachineInstr &MI, |
2183 | MachineFunction *MF) { |
2184 | |
2185 | if (!MI.hasOneMemOperand()) |
2186 | return false; |
2187 | |
2188 | if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII)) |
2189 | return false; |
2190 | |
2191 | |
2192 | return true; |
2193 | } |
2194 | |
2195 | bool InstrRefBasedLDV::isLocationSpill(const MachineInstr &MI, |
2196 | MachineFunction *MF, unsigned &Reg) { |
2197 | if (!isSpillInstruction(MI, MF)) |
2198 | return false; |
2199 | |
2200 | int FI; |
2201 | Reg = TII->isStoreToStackSlotPostFE(MI, FI); |
2202 | return Reg != 0; |
2203 | } |
2204 | |
2205 | Optional<SpillLoc> |
2206 | InstrRefBasedLDV::isRestoreInstruction(const MachineInstr &MI, |
2207 | MachineFunction *MF, unsigned &Reg) { |
2208 | if (!MI.hasOneMemOperand()) |
2209 | return None; |
2210 | |
2211 | |
2212 | |
2213 | if (MI.getRestoreSize(TII)) { |
2214 | Reg = MI.getOperand(0).getReg(); |
2215 | return extractSpillBaseRegAndOffset(MI); |
2216 | } |
2217 | return None; |
2218 | } |
2219 | |
2220 | bool InstrRefBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI) { |
2221 | |
2222 | |
2223 | |
2224 | if (EmulateOldLDV) |
2225 | return false; |
2226 | |
2227 | MachineFunction *MF = MI.getMF(); |
2228 | unsigned Reg; |
2229 | Optional<SpillLoc> Loc; |
2230 | |
2231 | LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump();); |
2232 | |
2233 | |
2234 | |
2235 | |
2236 | if (isSpillInstruction(MI, MF)) { |
2237 | Loc = extractSpillBaseRegAndOffset(MI); |
2238 | |
2239 | if (TTracker) { |
2240 | Optional<LocIdx> MLoc = MTracker->getSpillMLoc(*Loc); |
2241 | if (MLoc) { |
2242 | |
2243 | |
2244 | MTracker->setMLoc(*MLoc, ValueIDNum::EmptyValue); |
2245 | TTracker->clobberMloc(*MLoc, MI.getIterator()); |
2246 | } |
2247 | } |
2248 | } |
2249 | |
2250 | |
2251 | if (isLocationSpill(MI, MF, Reg)) { |
2252 | Loc = extractSpillBaseRegAndOffset(MI); |
2253 | auto ValueID = MTracker->readReg(Reg); |
2254 | |
2255 | |
2256 | if (ValueID.getLoc() == 0) |
2257 | ValueID = {CurBB, 0, MTracker->getRegMLoc(Reg)}; |
2258 | |
2259 | MTracker->setSpill(*Loc, ValueID); |
2260 | auto OptSpillLocIdx = MTracker->getSpillMLoc(*Loc); |
2261 | assert(OptSpillLocIdx && "Spill slot set but has no LocIdx?"); |
2262 | LocIdx SpillLocIdx = *OptSpillLocIdx; |
2263 | |
2264 | |
2265 | if (TTracker) |
2266 | TTracker->transferMlocs(MTracker->getRegMLoc(Reg), SpillLocIdx, |
2267 | MI.getIterator()); |
2268 | } else { |
2269 | if (!(Loc = isRestoreInstruction(MI, MF, Reg))) |
2270 | return false; |
2271 | |
2272 | |
2273 | auto OptValueID = MTracker->readSpill(*Loc); |
2274 | if (OptValueID) { |
2275 | ValueIDNum ValueID = *OptValueID; |
2276 | LocIdx SpillLocIdx = *MTracker->getSpillMLoc(*Loc); |
2277 | |
2278 | |
2279 | for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) |
2280 | MTracker->defReg(*RAI, CurBB, CurInst); |
2281 | |
2282 | |
2283 | MTracker->setReg(Reg, ValueID); |
2284 | |
2285 | |
2286 | if (TTracker) |
2287 | TTracker->transferMlocs(SpillLocIdx, MTracker->getRegMLoc(Reg), |
2288 | MI.getIterator()); |
2289 | } else { |
2290 | |
2291 | |
2292 | for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) |
2293 | MTracker->defReg(*RAI, CurBB, CurInst); |
2294 | |
2295 | |
2296 | LocIdx L = MTracker->getOrTrackSpillLoc(*Loc); |
2297 | |
2298 | |
2299 | |
2300 | |
2301 | ValueIDNum ValueID = {CurBB, 0, L}; |
2302 | MTracker->setReg(Reg, ValueID); |
2303 | MTracker->setSpill(*Loc, ValueID); |
2304 | } |
2305 | } |
2306 | return true; |
2307 | } |
2308 | |
2309 | bool InstrRefBasedLDV::transferRegisterCopy(MachineInstr &MI) { |
2310 | auto DestSrc = TII->isCopyInstr(MI); |
2311 | if (!DestSrc) |
2312 | return false; |
2313 | |
2314 | const MachineOperand *DestRegOp = DestSrc->Destination; |
2315 | const MachineOperand *SrcRegOp = DestSrc->Source; |
2316 | |
2317 | auto isCalleeSavedReg = [&](unsigned Reg) { |
2318 | for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) |
2319 | if (CalleeSavedRegs.test(*RAI)) |
2320 | return true; |
2321 | return false; |
2322 | }; |
2323 | |
2324 | Register SrcReg = SrcRegOp->getReg(); |
2325 | Register DestReg = DestRegOp->getReg(); |
2326 | |
2327 | |
2328 | if (SrcReg == DestReg) |
2329 | return true; |
2330 | |
2331 | |
2332 | |
2333 | |
2334 | |
2335 | |
2336 | |
2337 | |
2338 | |
2339 | |
2340 | if (EmulateOldLDV && !isCalleeSavedReg(DestReg)) |
2341 | return false; |
2342 | |
2343 | |
2344 | if (EmulateOldLDV && !SrcRegOp->isKill()) |
2345 | return false; |
2346 | |
2347 | |
2348 | InstrRefBasedLDV::performCopy(SrcReg, DestReg); |
2349 | |
2350 | |
2351 | |
2352 | |
2353 | if (TTracker && isCalleeSavedReg(DestReg) && SrcRegOp->isKill()) |
2354 | TTracker->transferMlocs(MTracker->getRegMLoc(SrcReg), |
2355 | MTracker->getRegMLoc(DestReg), MI.getIterator()); |
2356 | |
2357 | |
2358 | if (EmulateOldLDV && SrcReg != DestReg) |
2359 | MTracker->defReg(SrcReg, CurBB, CurInst); |
2360 | |
2361 | |
2362 | |
2363 | if (TTracker) { |
2364 | for (MCRegAliasIterator RAI(DestReg, TRI, true); RAI.isValid(); ++RAI) { |
2365 | LocIdx ClobberedLoc = MTracker->getRegMLoc(*RAI); |
2366 | TTracker->clobberMloc(ClobberedLoc, MI.getIterator(), false); |
2367 | } |
2368 | } |
2369 | |
2370 | return true; |
2371 | } |
2372 | |
2373 | |
2374 | |
2375 | |
2376 | |
2377 | |
2378 | |
2379 | void InstrRefBasedLDV::accumulateFragmentMap(MachineInstr &MI) { |
2380 | DebugVariable MIVar(MI.getDebugVariable(), MI.getDebugExpression(), |
2381 | MI.getDebugLoc()->getInlinedAt()); |
2382 | FragmentInfo ThisFragment = MIVar.getFragmentOrDefault(); |
2383 | |
2384 | |
2385 | |
2386 | |
2387 | auto SeenIt = SeenFragments.find(MIVar.getVariable()); |
2388 | if (SeenIt == SeenFragments.end()) { |
2389 | SmallSet<FragmentInfo, 4> OneFragment; |
2390 | OneFragment.insert(ThisFragment); |
2391 | SeenFragments.insert({MIVar.getVariable(), OneFragment}); |
2392 | |
2393 | OverlapFragments.insert({{MIVar.getVariable(), ThisFragment}, {}}); |
2394 | return; |
2395 | } |
2396 | |
2397 | |
2398 | |
2399 | auto IsInOLapMap = |
2400 | OverlapFragments.insert({{MIVar.getVariable(), ThisFragment}, {}}); |
2401 | if (!IsInOLapMap.second) |
2402 | return; |
2403 | |
2404 | auto &ThisFragmentsOverlaps = IsInOLapMap.first->second; |
2405 | auto &AllSeenFragments = SeenIt->second; |
2406 | |
2407 | |
2408 | |
2409 | |
2410 | for (auto &ASeenFragment : AllSeenFragments) { |
2411 | |
2412 | if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) { |
2413 | |
2414 | ThisFragmentsOverlaps.push_back(ASeenFragment); |
2415 | |
2416 | |
2417 | auto ASeenFragmentsOverlaps = |
2418 | OverlapFragments.find({MIVar.getVariable(), ASeenFragment}); |
2419 | assert(ASeenFragmentsOverlaps != OverlapFragments.end() && |
2420 | "Previously seen var fragment has no vector of overlaps"); |
2421 | ASeenFragmentsOverlaps->second.push_back(ThisFragment); |
2422 | } |
2423 | } |
2424 | |
2425 | AllSeenFragments.insert(ThisFragment); |
2426 | } |
2427 | |
2428 | void InstrRefBasedLDV::process(MachineInstr &MI, ValueIDNum **MLiveOuts, |
2429 | ValueIDNum **MLiveIns) { |
2430 | |
2431 | |
2432 | |
2433 | if (transferDebugValue(MI)) |
2434 | return; |
2435 | if (transferDebugInstrRef(MI, MLiveOuts, MLiveIns)) |
2436 | return; |
2437 | if (transferDebugPHI(MI)) |
2438 | return; |
2439 | if (transferRegisterCopy(MI)) |
2440 | return; |
2441 | if (transferSpillOrRestoreInst(MI)) |
2442 | return; |
2443 | transferRegisterDef(MI); |
2444 | } |
2445 | |
2446 | void InstrRefBasedLDV::produceMLocTransferFunction( |
2447 | MachineFunction &MF, SmallVectorImpl<MLocTransferMap> &MLocTransfer, |
2448 | unsigned MaxNumBlocks) { |
2449 | |
2450 | |
2451 | |
2452 | |
2453 | |
2454 | |
2455 | |
2456 | |
2457 | SmallVector<BitVector, 32> BlockMasks; |
2458 | BlockMasks.resize(MaxNumBlocks); |
2459 | |
2460 | |
2461 | unsigned BVWords = MachineOperand::getRegMaskSize(TRI->getNumRegs()); |
2462 | for (auto &BV : BlockMasks) |
2463 | BV.resize(TRI->getNumRegs(), true); |
2464 | |
2465 | |
2466 | for (auto &MBB : MF) { |
2467 | |
2468 | |
2469 | CurBB = MBB.getNumber(); |
2470 | CurInst = 1; |
2471 | |
2472 | |
2473 | |
2474 | MTracker->reset(); |
2475 | MTracker->setMPhis(CurBB); |
2476 | |
2477 | |
2478 | for (auto &MI : MBB) { |
2479 | process(MI); |
2480 | |
2481 | if (MI.isDebugValue()) |
2482 | accumulateFragmentMap(MI); |
2483 | |
2484 | |
2485 | |
2486 | if (uint64_t InstrNo = MI.peekDebugInstrNum()) { |
2487 | auto InstrAndPos = std::make_pair(&MI, CurInst); |
2488 | auto InsertResult = |
2489 | DebugInstrNumToInstr.insert(std::make_pair(InstrNo, InstrAndPos)); |
2490 | |
2491 | |
2492 | assert(InsertResult.second); |
2493 | (void)InsertResult; |
2494 | } |
2495 | |
2496 | ++CurInst; |
2497 | } |
2498 | |
2499 | |
2500 | |
2501 | |
2502 | |
2503 | for (auto Location : MTracker->locations()) { |
2504 | LocIdx Idx = Location.Idx; |
2505 | ValueIDNum &P = Location.Value; |
2506 | if (P.isPHI() && P.getLoc() == Idx.asU64()) |
2507 | continue; |
2508 | |
2509 | |
2510 | auto &TransferMap = MLocTransfer[CurBB]; |
2511 | auto Result = TransferMap.insert(std::make_pair(Idx.asU64(), P)); |
2512 | if (!Result.second) |
2513 | Result.first->second = P; |
2514 | } |
2515 | |
2516 | |
2517 | |
2518 | for (auto &P : MTracker->Masks) { |
2519 | BlockMasks[CurBB].clearBitsNotInMask(P.first->getRegMask(), BVWords); |
2520 | } |
2521 | } |
2522 | |
2523 | |
2524 | const TargetLowering *TLI = MF.getSubtarget().getTargetLowering(); |
2525 | Register SP = TLI->getStackPointerRegisterToSaveRestore(); |
2526 | BitVector UsedRegs(TRI->getNumRegs()); |
2527 | for (auto Location : MTracker->locations()) { |
2528 | unsigned ID = MTracker->LocIdxToLocID[Location.Idx]; |
2529 | if (ID >= TRI->getNumRegs() || ID == SP) |
2530 | continue; |
2531 | UsedRegs.set(ID); |
2532 | } |
2533 | |
2534 | |
2535 | |
2536 | |
2537 | for (unsigned int I = 0; I < MaxNumBlocks; ++I) { |
2538 | BitVector &BV = BlockMasks[I]; |
2539 | BV.flip(); |
2540 | BV &= UsedRegs; |
2541 | |
2542 | |
2543 | |
2544 | for (unsigned Bit : BV.set_bits()) { |
2545 | unsigned ID = MTracker->getLocID(Bit, false); |
2546 | LocIdx Idx = MTracker->LocIDToLocIdx[ID]; |
2547 | auto &TransferMap = MLocTransfer[I]; |
2548 | |
2549 | |
2550 | |
2551 | |
2552 | |
2553 | |
2554 | ValueIDNum NotGeneratedNum = ValueIDNum(I, 1, Idx); |
2555 | auto Result = |
2556 | TransferMap.insert(std::make_pair(Idx.asU64(), NotGeneratedNum)); |
2557 | if (!Result.second) { |
2558 | ValueIDNum &ValueID = Result.first->second; |
2559 | if (ValueID.getBlock() == I && ValueID.isPHI()) |
2560 | |
2561 | ValueID = NotGeneratedNum; |
2562 | } |
2563 | } |
2564 | } |
2565 | } |
2566 | |
2567 | std::tuple<bool, bool> |
2568 | InstrRefBasedLDV::mlocJoin(MachineBasicBlock &MBB, |
2569 | SmallPtrSet<const MachineBasicBlock *, 16> &Visited, |
2570 | ValueIDNum **OutLocs, ValueIDNum *InLocs) { |
2571 | LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n"); |
2572 | bool Changed = false; |
2573 | bool DowngradeOccurred = false; |
2574 | |
2575 | |
2576 | |
2577 | |
2578 | SmallVector<const MachineBasicBlock *, 8> BlockOrders; |
2579 | for (auto Pred : MBB.predecessors()) { |
2580 | if (Visited.count(Pred)) { |
2581 | BlockOrders.push_back(Pred); |
2582 | } |
2583 | } |
2584 | |
2585 | |
2586 | auto Cmp = [&](const MachineBasicBlock *A, const MachineBasicBlock *B) { |
2587 | return BBToOrder.find(A)->second < BBToOrder.find(B)->second; |
2588 | }; |
2589 | llvm::sort(BlockOrders, Cmp); |
2590 | |
2591 | |
2592 | if (BlockOrders.size() == 0) |
2593 | return std::tuple<bool, bool>(false, false); |
2594 | |
2595 | |
2596 | |
2597 | unsigned ThisBlockRPO = BBToOrder.find(&MBB)->second; |
2598 | for (auto Location : MTracker->locations()) { |
2599 | LocIdx Idx = Location.Idx; |
2600 | |
2601 | |
2602 | ValueIDNum BaseVal = OutLocs[BlockOrders[0]->getNumber()][Idx.asU64()]; |
2603 | |
2604 | |
2605 | |
2606 | bool Disagree = false; |
2607 | bool NonBackEdgeDisagree = false; |
2608 | |
2609 | |
2610 | for (unsigned int I = 1; I < BlockOrders.size(); ++I) { |
2611 | auto *MBB = BlockOrders[I]; |
2612 | if (BaseVal != OutLocs[MBB->getNumber()][Idx.asU64()]) { |
2613 | |
2614 | Disagree = true; |
2615 | |
2616 | |
2617 | if (BBToOrder.find(MBB)->second < ThisBlockRPO) |
2618 | NonBackEdgeDisagree = true; |
2619 | } |
2620 | } |
2621 | |
2622 | bool OverRide = false; |
2623 | if (Disagree && !NonBackEdgeDisagree) { |
2624 | |
2625 | |
2626 | |
2627 | |
2628 | |
2629 | |
2630 | |
2631 | |
2632 | |
2633 | |
2634 | unsigned BaseBlockRPONum = BBNumToRPO[BaseVal.getBlock()] + 1; |
2635 | if (!BaseVal.isPHI()) |
2636 | BaseBlockRPONum = 0; |
2637 | |
2638 | ValueIDNum &InLocID = InLocs[Idx.asU64()]; |
2639 | unsigned InLocRPONum = BBNumToRPO[InLocID.getBlock()] + 1; |
2640 | if (!InLocID.isPHI()) |
2641 | InLocRPONum = 0; |
2642 | |
2643 | |
2644 | |
2645 | unsigned ThisBlockRPONum = BBNumToRPO[MBB.getNumber()] + 1; |
2646 | if (BaseBlockRPONum > InLocRPONum && BaseBlockRPONum < ThisBlockRPONum) { |
2647 | |
2648 | OverRide = true; |
2649 | DowngradeOccurred = true; |
2650 | } |
2651 | } |
2652 | |
2653 | |
2654 | |
2655 | |
2656 | ValueIDNum PHI = {(uint64_t)MBB.getNumber(), 0, Idx}; |
2657 | ValueIDNum NewVal = (Disagree && !OverRide) ? PHI : BaseVal; |
2658 | if (InLocs[Idx.asU64()] != NewVal) { |
2659 | Changed |= true; |
2660 | InLocs[Idx.asU64()] = NewVal; |
2661 | } |
2662 | } |
2663 | |
2664 | |
2665 | return std::tuple<bool, bool>(Changed, DowngradeOccurred); |
2666 | } |
2667 | |
2668 | void InstrRefBasedLDV::mlocDataflow( |
2669 | ValueIDNum **MInLocs, ValueIDNum **MOutLocs, |
2670 | SmallVectorImpl<MLocTransferMap> &MLocTransfer) { |
2671 | std::priority_queue<unsigned int, std::vector<unsigned int>, |
2672 | std::greater<unsigned int>> |
2673 | Worklist, Pending; |
2674 | |
2675 | |
2676 | |
2677 | |
2678 | SmallPtrSet<MachineBasicBlock *, 16> OnPending, OnWorklist; |
2679 | |
2680 | |
2681 | for (unsigned int I = 0; I < BBToOrder.size(); ++I) { |
2682 | Worklist.push(I); |
2683 | OnWorklist.insert(OrderToBB[I]); |
2684 | } |
2685 | |
2686 | MTracker->reset(); |
2687 | |
2688 | |
2689 | |
2690 | MTracker->setMPhis(0); |
2691 | for (auto Location : MTracker->locations()) |
2692 | MInLocs[0][Location.Idx.asU64()] = Location.Value; |
2693 | |
2694 | SmallPtrSet<const MachineBasicBlock *, 16> Visited; |
2695 | while (!Worklist.empty() || !Pending.empty()) { |
2696 | |
2697 | SmallVector<std::pair<LocIdx, ValueIDNum>, 32> ToRemap; |
2698 | |
2699 | while (!Worklist.empty()) { |
2700 | MachineBasicBlock *MBB = OrderToBB[Worklist.top()]; |
2701 | CurBB = MBB->getNumber(); |
2702 | Worklist.pop(); |
2703 | |
2704 | |
2705 | bool InLocsChanged, DowngradeOccurred; |
2706 | std::tie(InLocsChanged, DowngradeOccurred) = |
2707 | mlocJoin(*MBB, Visited, MOutLocs, MInLocs[CurBB]); |
2708 | InLocsChanged |= Visited.insert(MBB).second; |
2709 | |
2710 | |
2711 | |
2712 | if (DowngradeOccurred && OnPending.insert(MBB).second) |
2713 | Pending.push(BBToOrder[MBB]); |
2714 | |
2715 | |
2716 | |
2717 | if (!InLocsChanged) |
2718 | continue; |
2719 | |
2720 | |
2721 | MTracker->loadFromArray(MInLocs[CurBB], CurBB); |
2722 | |
2723 | |
2724 | |
2725 | ToRemap.clear(); |
2726 | for (auto &P : MLocTransfer[CurBB]) { |
2727 | if (P.second.getBlock() == CurBB && P.second.isPHI()) { |
2728 | |
2729 | ValueIDNum NewID = MTracker->getNumAtPos(P.second.getLoc()); |
2730 | ToRemap.push_back(std::make_pair(P.first, NewID)); |
2731 | } else { |
2732 | |
2733 | assert(P.second.getBlock() == CurBB); |
2734 | ToRemap.push_back(std::make_pair(P.first, P.second)); |
2735 | } |
2736 | } |
2737 | |
2738 | |
2739 | |
2740 | for (auto &P : ToRemap) |
2741 | MTracker->setMLoc(P.first, P.second); |
2742 | |
2743 | |
2744 | |
2745 | |
2746 | bool OLChanged = false; |
2747 | for (auto Location : MTracker->locations()) { |
2748 | OLChanged |= MOutLocs[CurBB][Location.Idx.asU64()] != Location.Value; |
2749 | MOutLocs[CurBB][Location.Idx.asU64()] = Location.Value; |
2750 | } |
2751 | |
2752 | MTracker->reset(); |
2753 | |
2754 | |
2755 | if (!OLChanged) |
2756 | continue; |
2757 | |
2758 | |
2759 | |
2760 | |
2761 | for (auto s : MBB->successors()) { |
2762 | |
2763 | if (BBToOrder[s] > BBToOrder[MBB]) { |
2764 | |
2765 | if (OnWorklist.insert(s).second) |
2766 | Worklist.push(BBToOrder[s]); |
2767 | } else { |
2768 | |
2769 | if (OnPending.insert(s).second) |
2770 | Pending.push(BBToOrder[s]); |
2771 | } |
2772 | } |
2773 | } |
2774 | |
2775 | Worklist.swap(Pending); |
2776 | std::swap(OnPending, OnWorklist); |
2777 | OnPending.clear(); |
2778 | |
2779 | |
2780 | assert(Pending.empty() && "Pending should be empty"); |
2781 | } |
2782 | |
2783 | |
2784 | |
2785 | } |
2786 | |
2787 | bool InstrRefBasedLDV::vlocDowngradeLattice( |
2788 | const MachineBasicBlock &MBB, const DbgValue &OldLiveInLocation, |
2789 | const SmallVectorImpl<InValueT> &Values, unsigned CurBlockRPONum) { |
2790 | |
2791 | |
2792 | |
2793 | |
2794 | int OldLiveInRank = BBNumToRPO[OldLiveInLocation.ID.getBlock()] + 1; |
2795 | if (!OldLiveInLocation.ID.isPHI()) |
2796 | OldLiveInRank = 0; |
2797 | |
2798 | |
2799 | if (OldLiveInLocation.Kind == DbgValue::NoVal) { |
2800 | |
2801 | |
2802 | if (OldLiveInLocation.BlockNo == (unsigned)MBB.getNumber()) |
2803 | return false; |
2804 | OldLiveInRank = INT_MIN; |
2805 | } |
2806 | |
2807 | auto &InValue = *Values[0].second; |
2808 | |
2809 | if (InValue.Kind == DbgValue::Const || InValue.Kind == DbgValue::NoVal) |
2810 | return false; |
2811 | |
2812 | unsigned ThisRPO = BBNumToRPO[InValue.ID.getBlock()]; |
2813 | int ThisRank = ThisRPO + 1; |
2814 | if (!InValue.ID.isPHI()) |
2815 | ThisRank = 0; |
2816 | |
2817 | |
2818 | if (ThisRPO >= CurBlockRPONum) |
2819 | return false; |
2820 | |
2821 | |
2822 | if (ThisRank <= OldLiveInRank) |
2823 | return false; |
2824 | |
2825 | return true; |
2826 | } |
2827 | |
2828 | std::tuple<Optional<ValueIDNum>, bool> InstrRefBasedLDV::pickVPHILoc( |
2829 | MachineBasicBlock &MBB, const DebugVariable &Var, const LiveIdxT &LiveOuts, |
2830 | ValueIDNum **MOutLocs, ValueIDNum **MInLocs, |
2831 | const SmallVectorImpl<MachineBasicBlock *> &BlockOrders) { |
2832 | |
2833 | |
2834 | SmallVector<SmallVector<LocIdx, 4>, 8> Locs; |
2835 | unsigned NumLocs = MTracker->getNumLocs(); |
2836 | unsigned BackEdgesStart = 0; |
2837 | |
2838 | for (auto p : BlockOrders) { |
2839 | |
2840 | |
2841 | if (BBToOrder[p] < BBToOrder[&MBB]) |
2842 | ++BackEdgesStart; |
2843 | |
2844 | |
2845 | Locs.resize(Locs.size() + 1); |
2846 | unsigned ThisBBNum = p->getNumber(); |
2847 | auto LiveOutMap = LiveOuts.find(p); |
2848 | if (LiveOutMap == LiveOuts.end()) |
2849 | |
2850 | |
2851 | continue; |
2852 | |
2853 | auto It = LiveOutMap->second->find(Var); |
2854 | if (It == LiveOutMap->second->end()) |
2855 | |
2856 | |
2857 | continue; |
2858 | |
2859 | const DbgValue &OutVal = It->second; |
2860 | |
2861 | if (OutVal.Kind == DbgValue::Const || OutVal.Kind == DbgValue::NoVal) |
2862 | |
2863 | continue; |
2864 | |
2865 | assert(OutVal.Kind == DbgValue::Proposed || OutVal.Kind == DbgValue::Def); |
2866 | ValueIDNum ValToLookFor = OutVal.ID; |
2867 | |
2868 | |
2869 | for (unsigned int I = 0; I < NumLocs; ++I) { |
2870 | if (MOutLocs[ThisBBNum][I] == ValToLookFor) |
2871 | Locs.back().push_back(LocIdx(I)); |
2872 | } |
2873 | } |
2874 | |
2875 | |
2876 | if (Locs.empty()) |
2877 | return std::tuple<Optional<ValueIDNum>, bool>(None, false); |
2878 | |
2879 | |
2880 | using LocsIt = SmallVector<SmallVector<LocIdx, 4>, 8>::iterator; |
2881 | auto SeekLocation = |
2882 | [&Locs](llvm::iterator_range<LocsIt> SearchRange) -> Optional<LocIdx> { |
2883 | |
2884 | |
2885 | SmallVector<LocIdx, 4> base = Locs[0]; |
2886 | for (auto &S : SearchRange) { |
2887 | SmallVector<LocIdx, 4> new_base; |
2888 | std::set_intersection(base.begin(), base.end(), S.begin(), S.end(), |
2889 | std::inserter(new_base, new_base.begin())); |
2890 | base = new_base; |
2891 | } |
2892 | if (base.empty()) |
2893 | return None; |
2894 | |
2895 | |
2896 | |
2897 | |
2898 | return *base.begin(); |
2899 | }; |
2900 | |
2901 | |
2902 | |
2903 | bool ValidForAllLocs = true; |
2904 | auto TheLoc = SeekLocation(Locs); |
2905 | if (!TheLoc) { |
2906 | ValidForAllLocs = false; |
2907 | TheLoc = |
2908 | SeekLocation(make_range(Locs.begin(), Locs.begin() + BackEdgesStart)); |
2909 | } |
2910 | |
2911 | if (!TheLoc) |
2912 | return std::tuple<Optional<ValueIDNum>, bool>(None, false); |
2913 | |
2914 | |
2915 | LocIdx L = *TheLoc; |
2916 | ValueIDNum PHIVal = {(unsigned)MBB.getNumber(), 0, L}; |
2917 | return std::tuple<Optional<ValueIDNum>, bool>(PHIVal, ValidForAllLocs); |
2918 | } |
2919 | |
2920 | std::tuple<bool, bool> InstrRefBasedLDV::vlocJoin( |
2921 | MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, LiveIdxT &VLOCInLocs, |
2922 | SmallPtrSet<const MachineBasicBlock *, 16> *VLOCVisited, unsigned BBNum, |
2923 | const SmallSet<DebugVariable, 4> &AllVars, ValueIDNum **MOutLocs, |
2924 | ValueIDNum **MInLocs, |
2925 | SmallPtrSet<const MachineBasicBlock *, 8> &InScopeBlocks, |
2926 | SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore, |
2927 | DenseMap<DebugVariable, DbgValue> &InLocsT) { |
2928 | bool DowngradeOccurred = false; |
2929 | |
2930 | |
2931 | |
2932 | |
2933 | if (InScopeBlocks.count(&MBB) == 0 && !ArtificialBlocks.count(&MBB)) { |
2934 | if (VLOCVisited) |
2935 | return std::tuple<bool, bool>(true, false); |
2936 | return std::tuple<bool, bool>(false, false); |
2937 | } |
2938 | |
2939 | LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n"); |
2940 | bool Changed = false; |
2941 | |
2942 | |
2943 | auto ILSIt = VLOCInLocs.find(&MBB); |
2944 | assert(ILSIt != VLOCInLocs.end()); |
2945 | auto &ILS = *ILSIt->second; |
2946 | |
2947 | |
2948 | SmallVector<MachineBasicBlock *, 8> BlockOrders(MBB.predecessors()); |
2949 | |
2950 | auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) { |
2951 | return BBToOrder[A] < BBToOrder[B]; |
2952 | }; |
2953 | |
2954 | llvm::sort(BlockOrders, Cmp); |
2955 | |
2956 | unsigned CurBlockRPONum = BBToOrder[&MBB]; |
2957 | |
2958 | |
2959 | |
2960 | |
2961 | if (!BlockOrders.empty() && |
2962 | BBToOrder[BlockOrders[BlockOrders.size() - 1]] >= CurBlockRPONum && |
2963 | VLOCVisited) |
2964 | DowngradeOccurred = true; |
2965 | |
2966 | auto ConfirmValue = [&InLocsT](const DebugVariable &DV, DbgValue VR) { |
2967 | auto Result = InLocsT.insert(std::make_pair(DV, VR)); |
2968 | (void)Result; |
2969 | assert(Result.second); |
2970 | }; |
2971 | |
2972 | auto ConfirmNoVal = [&ConfirmValue, &MBB](const DebugVariable &Var, const DbgValueProperties &Properties) { |
2973 | DbgValue NoLocPHIVal(MBB.getNumber(), Properties, DbgValue::NoVal); |
2974 | |
2975 | ConfirmValue(Var, NoLocPHIVal); |
2976 | }; |
2977 | |
2978 | |
2979 | for (auto &Var : AllVars) { |
2980 | |
2981 | SmallVector<InValueT, 8> Values; |
2982 | bool Bail = false; |
2983 | unsigned BackEdgesStart = 0; |
2984 | for (auto p : BlockOrders) { |
2985 | |
2986 | |
2987 | if (!BlocksToExplore.contains(p)) { |
2988 | Bail = true; |
2989 | break; |
2990 | } |
2991 | |
2992 | |
2993 | |
2994 | if (VLOCVisited && !VLOCVisited->count(p)) |
2995 | continue; |
2996 | |
2997 | |
2998 | auto OL = VLOCOutLocs.find(p); |
2999 | if (OL == VLOCOutLocs.end()) { |
3000 | Bail = true; |
3001 | break; |
3002 | } |
3003 | |
3004 | |
3005 | |
3006 | auto VIt = OL->second->find(Var); |
3007 | if (VIt == OL->second->end()) { |
3008 | Bail = true; |
3009 | break; |
3010 | } |
3011 | |
3012 | |
3013 | |
3014 | unsigned ThisBBRPONum = BBToOrder[p]; |
3015 | if (ThisBBRPONum < CurBlockRPONum) |
3016 | ++BackEdgesStart; |
3017 | |
3018 | Values.push_back(std::make_pair(p, &VIt->second)); |
3019 | } |
3020 | |
3021 | |
3022 | |
3023 | |
3024 | if (Bail || Values.size() == 0) |
3025 | continue; |
3026 | |
3027 | |
3028 | enum { |
3029 | Unset = 0, |
3030 | Agreed, |
3031 | PropDisagree, |
3032 | BEDisagree, |
3033 | PHINeeded, |
3034 | NoSolution |
3035 | } OurState = Unset; |
3036 | |
3037 | |
3038 | |
3039 | |
3040 | const DbgValue &FirstVal = *Values[0].second; |
3041 | const ValueIDNum &FirstID = FirstVal.ID; |
3042 | |
3043 | |
3044 | |
3045 | |
3046 | for (auto &V : Values) { |
3047 | if (V.second->Properties != FirstVal.Properties) |
3048 | OurState = NoSolution; |
3049 | if (V.second->Kind == DbgValue::Const && FirstVal.Kind != DbgValue::Const) |
3050 | OurState = NoSolution; |
3051 | } |
3052 | |
3053 | |
3054 | bool NonBackEdgeDisagree = false; |
3055 | bool DisagreeOnPHINess = false; |
3056 | bool IDDisagree = false; |
3057 | bool Disagree = false; |
3058 | if (OurState == Unset) { |
3059 | for (auto &V : Values) { |
3060 | if (*V.second == FirstVal) |
3061 | continue; |
3062 | |
3063 | Disagree = true; |
3064 | |
3065 | |
3066 | if (V.second->ID != FirstID) |
3067 | IDDisagree = true; |
3068 | |
3069 | |
3070 | |
3071 | unsigned ThisBBRPONum = BBToOrder[V.first]; |
3072 | if (ThisBBRPONum < CurBlockRPONum) |
3073 | NonBackEdgeDisagree = true; |
3074 | |
3075 | |
3076 | |
3077 | if (V.second->Kind != FirstVal.Kind && |
3078 | (V.second->Kind == DbgValue::Proposed || |
3079 | V.second->Kind == DbgValue::Def) && |
3080 | (FirstVal.Kind == DbgValue::Proposed || |
3081 | FirstVal.Kind == DbgValue::Def)) |
3082 | DisagreeOnPHINess = true; |
3083 | } |
3084 | |
3085 | |
3086 | |
3087 | if (!Disagree) |
3088 | OurState = Agreed; |
3089 | else if (!IDDisagree && DisagreeOnPHINess) |
3090 | OurState = PropDisagree; |
3091 | else if (!NonBackEdgeDisagree) |
3092 | OurState = BEDisagree; |
3093 | else |
3094 | OurState = PHINeeded; |
3095 | } |
3096 | |
3097 | |
3098 | |
3099 | |
3100 | bool PropOnlyInBEs = Disagree && !IDDisagree && DisagreeOnPHINess && |
3101 | !NonBackEdgeDisagree && FirstVal.Kind == DbgValue::Def; |
3102 | |
3103 | const auto &Properties = FirstVal.Properties; |
3104 | |
3105 | auto OldLiveInIt = ILS.find(Var); |
3106 | const DbgValue *OldLiveInLocation = |
3107 | (OldLiveInIt != ILS.end()) ? &OldLiveInIt->second : nullptr; |
3108 | |
3109 | bool OverRide = false; |
3110 | if (OurState == BEDisagree && OldLiveInLocation) { |
3111 | |
3112 | |
3113 | |
3114 | OverRide = |
3115 | vlocDowngradeLattice(MBB, *OldLiveInLocation, Values, CurBlockRPONum); |
3116 | } |
3117 | |
3118 | |
3119 | |
3120 | |
3121 | |
3122 | |
3123 | |
3124 | |
3125 | if (OurState == Agreed) { |
3126 | |
3127 | ConfirmValue(Var, FirstVal); |
3128 | } else if (OurState == BEDisagree && OverRide) { |
3129 | |
3130 | |
3131 | DowngradeOccurred = true; |
3132 | ConfirmValue(Var, FirstVal); |
3133 | } else if (OurState == PropDisagree) { |
3134 | |
3135 | |
3136 | |
3137 | if (FirstID.getBlock() == (uint64_t)MBB.getNumber() && FirstID.isPHI()) { |
3138 | ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Def)); |
3139 | } else if (PropOnlyInBEs) { |
3140 | |
3141 | |
3142 | ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Def)); |
3143 | } else { |
3144 | |
3145 | ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Proposed)); |
3146 | } |
3147 | } else if ((OurState == PHINeeded || OurState == BEDisagree)) { |
3148 | |
3149 | |
3150 | Optional<ValueIDNum> VPHI; |
3151 | bool AllEdgesVPHI = false; |
3152 | std::tie(VPHI, AllEdgesVPHI) = |
3153 | pickVPHILoc(MBB, Var, VLOCOutLocs, MOutLocs, MInLocs, BlockOrders); |
3154 | |
3155 | if (VPHI && AllEdgesVPHI) { |
3156 | |
3157 | |
3158 | |
3159 | |
3160 | DbgValue::KindT K = DbgValue::Def; |
3161 | for (unsigned int I = 0; I < BackEdgesStart; ++I) |
3162 | if (Values[I].second->Kind == DbgValue::Proposed) |
3163 | K = DbgValue::Proposed; |
3164 | |
3165 | ConfirmValue(Var, DbgValue(*VPHI, Properties, K)); |
3166 | } else if (VPHI) { |
3167 | |
3168 | |
3169 | |
3170 | DbgValue NoBEValue = DbgValue(*VPHI, Properties, DbgValue::Proposed); |
3171 | ConfirmValue(Var, NoBEValue); |
3172 | } else { |
3173 | ConfirmNoVal(Var, Properties); |
3174 | } |
3175 | } else { |
3176 | |
3177 | ConfirmNoVal(Var, Properties); |
3178 | } |
3179 | } |
3180 | |
3181 | |
3182 | Changed = ILS != InLocsT; |
3183 | if (Changed) |
3184 | ILS = InLocsT; |
3185 | |
3186 | return std::tuple<bool, bool>(Changed, DowngradeOccurred); |
3187 | } |
3188 | |
3189 | void InstrRefBasedLDV::vlocDataflow( |
3190 | const LexicalScope *Scope, const DILocation *DILoc, |
3191 | const SmallSet<DebugVariable, 4> &VarsWeCareAbout, |
3192 | SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks, LiveInsT &Output, |
3193 | ValueIDNum **MOutLocs, ValueIDNum **MInLocs, |
3194 | SmallVectorImpl<VLocTracker> &AllTheVLocs) { |
3195 | |
3196 | |
3197 | |
3198 | |
3199 | std::priority_queue<unsigned int, std::vector<unsigned int>, |
3200 | std::greater<unsigned int>> |
3201 | Worklist, Pending; |
3202 | SmallPtrSet<MachineBasicBlock *, 16> OnWorklist, OnPending; |
3203 | |
3204 | |
3205 | SmallPtrSet<const MachineBasicBlock *, 8> BlocksToExplore; |
3206 | |
3207 | |
3208 | SmallVector<MachineBasicBlock *, 8> BlockOrders; |
3209 | |
3210 | |
3211 | auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) { |
3212 | return BBToOrder[A] < BBToOrder[B]; |
3213 | }; |
3214 | |
3215 | LS.getMachineBasicBlocks(DILoc, BlocksToExplore); |
3216 | |
3217 | |
3218 | |
3219 | SmallPtrSet<const MachineBasicBlock *, 8> InScopeBlocks = BlocksToExplore; |
3220 | |
3221 | |
3222 | |
3223 | |
3224 | if (EmulateOldLDV) |
3225 | BlocksToExplore.insert(AssignBlocks.begin(), AssignBlocks.end()); |
3226 | |
3227 | |
3228 | |
3229 | DenseSet<const MachineBasicBlock *> ToAdd; |
3230 | |
3231 | |
3232 | |
3233 | auto AccumulateArtificialBlocks = |
3234 | [this, &ToAdd, &BlocksToExplore, |
3235 | &InScopeBlocks](const MachineBasicBlock *MBB) { |
3236 | |
3237 | |
3238 | SmallVector<std::pair<const MachineBasicBlock *, |
3239 | MachineBasicBlock::const_succ_iterator>, |
3240 | 8> |
3241 | DFS; |
3242 | |
3243 | |
3244 | for (auto *succ : MBB->successors()) { |
3245 | if (BlocksToExplore.count(succ) || InScopeBlocks.count(succ)) |
3246 | continue; |
3247 | if (!ArtificialBlocks.count(succ)) |
3248 | continue; |
3249 | DFS.push_back(std::make_pair(succ, succ->succ_begin())); |
3250 | ToAdd.insert(succ); |
3251 | } |
3252 | |
3253 | |
3254 | while (!DFS.empty()) { |
3255 | const MachineBasicBlock *CurBB = DFS.back().first; |
3256 | MachineBasicBlock::const_succ_iterator &CurSucc = DFS.back().second; |
3257 | |
3258 | if (CurSucc == CurBB->succ_end()) { |
3259 | DFS.pop_back(); |
3260 | continue; |
3261 | } |
3262 | |
3263 | |
3264 | |
3265 | if (!ToAdd.count(*CurSucc) && ArtificialBlocks.count(*CurSucc)) { |
3266 | DFS.push_back(std::make_pair(*CurSucc, (*CurSucc)->succ_begin())); |
3267 | ToAdd.insert(*CurSucc); |
3268 | continue; |
3269 | } |
3270 | |
3271 | ++CurSucc; |
3272 | } |
3273 | }; |
3274 | |
3275 | |
3276 | |
3277 | for (auto *MBB : BlocksToExplore) |
3278 | AccumulateArtificialBlocks(MBB); |
3279 | for (auto *MBB : InScopeBlocks) |
3280 | AccumulateArtificialBlocks(MBB); |
3281 | |
3282 | BlocksToExplore.insert(ToAdd.begin(), ToAdd.end()); |
3283 | InScopeBlocks.insert(ToAdd.begin(), ToAdd.end()); |
3284 | |
3285 | |
3286 | |
3287 | |
3288 | |
3289 | if (BlocksToExplore.size() == 1) |
3290 | return; |
3291 | |
3292 | |
3293 | for (auto *MBB : BlocksToExplore) |
3294 | BlockOrders.push_back(const_cast<MachineBasicBlock *>(MBB)); |
3295 | |
3296 | llvm::sort(BlockOrders, Cmp); |
3297 | unsigned NumBlocks = BlockOrders.size(); |
3298 | |
3299 | |
3300 | SmallVector<DenseMap<DebugVariable, DbgValue>, 32> LiveIns, LiveOuts; |
3301 | LiveIns.resize(NumBlocks); |
3302 | LiveOuts.resize(NumBlocks); |
3303 | |
3304 | |
3305 | |
3306 | LiveIdxT LiveOutIdx, LiveInIdx; |
3307 | LiveOutIdx.reserve(NumBlocks); |
3308 | LiveInIdx.reserve(NumBlocks); |
3309 | for (unsigned I = 0; I < NumBlocks; ++I) { |
3310 | LiveOutIdx[BlockOrders[I]] = &LiveOuts[I]; |
3311 | LiveInIdx[BlockOrders[I]] = &LiveIns[I]; |
3312 | } |
3313 | |
3314 | for (auto *MBB : BlockOrders) { |
3315 | Worklist.push(BBToOrder[MBB]); |
3316 | OnWorklist.insert(MBB); |
3317 | } |
3318 | |
3319 | |
3320 | bool FirstTrip = true; |
3321 | SmallPtrSet<const MachineBasicBlock *, 16> VLOCVisited; |
3322 | while (!Worklist.empty() || !Pending.empty()) { |
3323 | while (!Worklist.empty()) { |
3324 | auto *MBB = OrderToBB[Worklist.top()]; |
3325 | CurBB = MBB->getNumber(); |
3326 | Worklist.pop(); |
3327 | |
3328 | DenseMap<DebugVariable, DbgValue> JoinedInLocs; |
3329 | |
3330 | |
3331 | |
3332 | bool InLocsChanged, DowngradeOccurred; |
3333 | std::tie(InLocsChanged, DowngradeOccurred) = vlocJoin( |
3334 | *MBB, LiveOutIdx, LiveInIdx, (FirstTrip) ? &VLOCVisited : nullptr, |
3335 | CurBB, VarsWeCareAbout, MOutLocs, MInLocs, InScopeBlocks, |
3336 | BlocksToExplore, JoinedInLocs); |
3337 | |
3338 | bool FirstVisit = VLOCVisited.insert(MBB).second; |
3339 | |
3340 | |
3341 | |
3342 | InLocsChanged |= FirstVisit; |
3343 | |
3344 | |
3345 | |
3346 | if (DowngradeOccurred && OnPending.insert(MBB).second) |
3347 | Pending.push(BBToOrder[MBB]); |
3348 | |
3349 | if (!InLocsChanged) |
3350 | continue; |
3351 | |
3352 | |
3353 | auto &VTracker = AllTheVLocs[MBB->getNumber()]; |
3354 | for (auto &Transfer : VTracker.Vars) { |
3355 | |
3356 | if (VarsWeCareAbout.count(Transfer.first)) { |
3357 | |
3358 | if (Transfer.second.Kind == DbgValue::Undef) { |
3359 | JoinedInLocs.erase(Transfer.first); |
3360 | } else { |
3361 | |
3362 | auto NewValuePair = std::make_pair(Transfer.first, Transfer.second); |
3363 | auto Result = JoinedInLocs.insert(NewValuePair); |
3364 | if (!Result.second) |
3365 | Result.first->second = Transfer.second; |
3366 | } |
3367 | } |
3368 | } |
3369 | |
3370 | |
3371 | bool OLChanged = JoinedInLocs != *LiveOutIdx[MBB]; |
3372 | |
3373 | |
3374 | if (!OLChanged) |
3375 | continue; |
3376 | |
3377 | |
3378 | *LiveOutIdx[MBB] = JoinedInLocs; |
3379 | |
3380 | |
3381 | |
3382 | |
3383 | for (auto s : MBB->successors()) { |
3384 | |
3385 | if (LiveInIdx.find(s) == LiveInIdx.end()) |
3386 | continue; |
3387 | |
3388 | if (BBToOrder[s] > BBToOrder[MBB]) { |
3389 | if (OnWorklist.insert(s).second) |
3390 | Worklist.push(BBToOrder[s]); |
3391 | } else if (OnPending.insert(s).second && (FirstTrip || OLChanged)) { |
3392 | Pending.push(BBToOrder[s]); |
3393 | } |
3394 | } |
3395 | } |
3396 | Worklist.swap(Pending); |
3397 | std::swap(OnWorklist, OnPending); |
3398 | OnPending.clear(); |
3399 | assert(Pending.empty()); |
3400 | FirstTrip = false; |
3401 | } |
3402 | |
3403 | |
3404 | |
3405 | |
3406 | |
3407 | for (auto *MBB : BlockOrders) { |
3408 | auto &VarMap = *LiveInIdx[MBB]; |
3409 | for (auto &P : VarMap) { |
3410 | if (P.second.Kind == DbgValue::Proposed || |
3411 | P.second.Kind == DbgValue::NoVal) |
3412 | continue; |
3413 | Output[MBB->getNumber()].push_back(P); |
3414 | } |
3415 | } |
3416 | |
3417 | BlockOrders.clear(); |
3418 | BlocksToExplore.clear(); |
3419 | } |
3420 | |
3421 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
3422 | void InstrRefBasedLDV::dump_mloc_transfer( |
3423 | const MLocTransferMap &mloc_transfer) const { |
3424 | for (auto &P : mloc_transfer) { |
3425 | std::string foo = MTracker->LocIdxToName(P.first); |
3426 | std::string bar = MTracker->IDAsString(P.second); |
3427 | dbgs() << "Loc " << foo << " --> " << bar << "\n"; |
3428 | } |
3429 | } |
3430 | #endif |
3431 | |
3432 | void InstrRefBasedLDV::emitLocations( |
3433 | MachineFunction &MF, LiveInsT SavedLiveIns, ValueIDNum **MOutLocs, |
3434 | ValueIDNum **MInLocs, DenseMap<DebugVariable, unsigned> &AllVarsNumbering, |
3435 | const TargetPassConfig &TPC) { |
3436 | TTracker = new TransferTracker(TII, MTracker, MF, *TRI, CalleeSavedRegs, TPC); |
3437 | unsigned NumLocs = MTracker->getNumLocs(); |
3438 | |
3439 | |
3440 | |
3441 | |
3442 | for (MachineBasicBlock &MBB : MF) { |
3443 | unsigned bbnum = MBB.getNumber(); |
3444 | MTracker->reset(); |
3445 | MTracker->loadFromArray(MInLocs[bbnum], bbnum); |
3446 | TTracker->loadInlocs(MBB, MInLocs[bbnum], SavedLiveIns[MBB.getNumber()], |
3447 | NumLocs); |
3448 | |
3449 | CurBB = bbnum; |
3450 | CurInst = 1; |
3451 | for (auto &MI : MBB) { |
3452 | process(MI, MOutLocs, MInLocs); |
3453 | TTracker->checkInstForNewValues(CurInst, MI.getIterator()); |
3454 | ++CurInst; |
3455 | } |
3456 | } |
3457 | |
3458 | |
3459 | |
3460 | |
3461 | auto OrderDbgValues = [&](const MachineInstr *A, |
3462 | const MachineInstr *B) -> bool { |
3463 | DebugVariable VarA(A->getDebugVariable(), A->getDebugExpression(), |
3464 | A->getDebugLoc()->getInlinedAt()); |
3465 | DebugVariable VarB(B->getDebugVariable(), B->getDebugExpression(), |
3466 | B->getDebugLoc()->getInlinedAt()); |
3467 | return AllVarsNumbering.find(VarA)->second < |
3468 | AllVarsNumbering.find(VarB)->second; |
3469 | }; |
3470 | |
3471 | |
3472 | |
3473 | |
3474 | for (auto &P : TTracker->Transfers) { |
3475 | |
3476 | llvm::sort(P.Insts, OrderDbgValues); |
3477 | |
3478 | if (P.MBB) { |
3479 | MachineBasicBlock &MBB = *P.MBB; |
3480 | for (auto *MI : P.Insts) { |
3481 | MBB.insert(P.Pos, MI); |
3482 | } |
3483 | } else { |
3484 | |
3485 | |
3486 | if (P.Pos->isTerminator()) |
3487 | continue; |
3488 | |
3489 | MachineBasicBlock &MBB = *P.Pos->getParent(); |
3490 | for (auto *MI : P.Insts) { |
3491 | MBB.insertAfterBundle(P.Pos, MI); |
3492 | } |
3493 | } |
3494 | } |
3495 | } |
3496 | |
3497 | void InstrRefBasedLDV::initialSetup(MachineFunction &MF) { |
3498 | |
3499 | auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool { |
3500 | if (const DebugLoc &DL = MI.getDebugLoc()) |
3501 | return DL.getLine() != 0; |
3502 | return false; |
3503 | }; |
3504 | |
3505 | for (auto &MBB : MF) |
3506 | if (none_of(MBB.instrs(), hasNonArtificialLocation)) |
3507 | ArtificialBlocks.insert(&MBB); |
3508 | |
3509 | |
3510 | ReversePostOrderTraversal<MachineFunction *> RPOT(&MF); |
3511 | unsigned int RPONumber = 0; |
3512 | for (MachineBasicBlock *MBB : RPOT) { |
3513 | OrderToBB[RPONumber] = MBB; |
3514 | BBToOrder[MBB] = RPONumber; |
3515 | BBNumToRPO[MBB->getNumber()] = RPONumber; |
3516 | ++RPONumber; |
3517 | } |
3518 | |
3519 | |
3520 | llvm::sort(MF.DebugValueSubstitutions); |
3521 | |
3522 | #ifdef EXPENSIVE_CHECKS |
3523 | |
3524 | |
3525 | if (MF.DebugValueSubstitutions.size() > 2) { |
3526 | for (auto It = MF.DebugValueSubstitutions.begin(); |
3527 | It != std::prev(MF.DebugValueSubstitutions.end()); ++It) { |
3528 | assert(It->Src != std::next(It)->Src && "Duplicate variable location " |
3529 | "substitution seen"); |
3530 | } |
3531 | } |
3532 | #endif |
3533 | } |
3534 | |
3535 | |
3536 | |
3537 | bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC, |
3538 | unsigned InputBBLimit, |
3539 | unsigned InputDbgValLimit) { |
3540 | |
3541 | if (!MF.getFunction().getSubprogram()) |
| 1 | Assuming the condition is false | |
|
| |
3542 | return false; |
3543 | |
3544 | LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n"); |
| 3 | | Loop condition is false. Exiting loop | |
|
3545 | this->TPC = TPC; |
3546 | |
3547 | TRI = MF.getSubtarget().getRegisterInfo(); |
3548 | TII = MF.getSubtarget().getInstrInfo(); |
3549 | TFI = MF.getSubtarget().getFrameLowering(); |
3550 | TFI->getCalleeSaves(MF, CalleeSavedRegs); |
3551 | MFI = &MF.getFrameInfo(); |
3552 | LS.initialize(MF); |
3553 | |
3554 | MTracker = |
3555 | new MLocTracker(MF, *TII, *TRI, *MF.getSubtarget().getTargetLowering()); |
3556 | VTracker = nullptr; |
3557 | TTracker = nullptr; |
3558 | |
3559 | SmallVector<MLocTransferMap, 32> MLocTransfer; |
3560 | SmallVector<VLocTracker, 8> vlocs; |
3561 | LiveInsT SavedLiveIns; |
3562 | |
3563 | int MaxNumBlocks = -1; |
3564 | for (auto &MBB : MF) |
3565 | MaxNumBlocks = std::max(MBB.getNumber(), MaxNumBlocks); |
3566 | assert(MaxNumBlocks >= 0); |
3567 | ++MaxNumBlocks; |
3568 | |
3569 | MLocTransfer.resize(MaxNumBlocks); |
3570 | vlocs.resize(MaxNumBlocks); |
3571 | SavedLiveIns.resize(MaxNumBlocks); |
3572 | |
3573 | initialSetup(MF); |
3574 | |
3575 | produceMLocTransferFunction(MF, MLocTransfer, MaxNumBlocks); |
3576 | |
3577 | |
3578 | |
3579 | |
3580 | ValueIDNum **MOutLocs = new ValueIDNum *[MaxNumBlocks]; |
3581 | ValueIDNum **MInLocs = new ValueIDNum *[MaxNumBlocks]; |
| |
3582 | unsigned NumLocs = MTracker->getNumLocs(); |
3583 | for (int i = 0; i < MaxNumBlocks; ++i) { |
| 5 | | Loop condition is false. Execution continues on line 3592 | |
|
3584 | MOutLocs[i] = new ValueIDNum[NumLocs]; |
3585 | MInLocs[i] = new ValueIDNum[NumLocs]; |
3586 | } |
3587 | |
3588 | |
3589 | |
3590 | |
3591 | |
3592 | mlocDataflow(MInLocs, MOutLocs, MLocTransfer); |
3593 | |
3594 | |
3595 | |
3596 | for (auto &DBG_PHI : DebugPHINumToValue) { |
| 6 | | Assuming '__begin1' is equal to '__end1' | |
|
3597 | |
3598 | ValueIDNum &Num = DBG_PHI.ValueRead; |
3599 | if (!Num.isPHI()) |
3600 | continue; |
3601 | |
3602 | unsigned BlockNo = Num.getBlock(); |
3603 | LocIdx LocNo = Num.getLoc(); |
3604 | Num = MInLocs[BlockNo][LocNo.asU64()]; |
3605 | } |
3606 | |
3607 | llvm::sort(DebugPHINumToValue); |
3608 | |
3609 | |
3610 | |
3611 | for (auto &OrderPair : OrderToBB) { |
3612 | MachineBasicBlock &MBB = *OrderPair.second; |
3613 | CurBB = MBB.getNumber(); |
3614 | VTracker = &vlocs[CurBB]; |
3615 | VTracker->MBB = &MBB; |
3616 | MTracker->loadFromArray(MInLocs[CurBB], CurBB); |
| 7 | | Use of zero-allocated memory |
|
3617 | CurInst = 1; |
3618 | for (auto &MI : MBB) { |
3619 | process(MI, MOutLocs, MInLocs); |
3620 | ++CurInst; |
3621 | } |
3622 | MTracker->reset(); |
3623 | } |
3624 | |
3625 | |
3626 | |
3627 | DenseMap<DebugVariable, unsigned> AllVarsNumbering; |
3628 | |
3629 | |
3630 | DenseMap<const LexicalScope *, SmallSet<DebugVariable, 4>> ScopeToVars; |
3631 | |
3632 | |
3633 | DenseMap<const LexicalScope *, SmallPtrSet<MachineBasicBlock *, 4>> |
3634 | ScopeToBlocks; |
3635 | |
3636 | |
3637 | DenseMap<const LexicalScope *, const DILocation *> ScopeToDILocation; |
3638 | |
3639 | |
3640 | |
3641 | unsigned VarAssignCount = 0; |
3642 | for (unsigned int I = 0; I < OrderToBB.size(); ++I) { |
3643 | auto *MBB = OrderToBB[I]; |
3644 | auto *VTracker = &vlocs[MBB->getNumber()]; |
3645 | |
3646 | for (auto &idx : VTracker->Vars) { |
3647 | const auto &Var = idx.first; |
3648 | const DILocation *ScopeLoc = VTracker->Scopes[Var]; |
3649 | assert(ScopeLoc != nullptr); |
3650 | auto *Scope = LS.findLexicalScope(ScopeLoc); |
3651 | |
3652 | |
3653 | assert(Scope != nullptr); |
3654 | |
3655 | AllVarsNumbering.insert(std::make_pair(Var, AllVarsNumbering.size())); |
3656 | ScopeToVars[Scope].insert(Var); |
3657 | ScopeToBlocks[Scope].insert(VTracker->MBB); |
3658 | ScopeToDILocation[Scope] = ScopeLoc; |
3659 | ++VarAssignCount; |
3660 | } |
3661 | } |
3662 | |
3663 | bool Changed = false; |
3664 | |
3665 | |
3666 | |
3667 | |
3668 | if ((unsigned)MaxNumBlocks > InputBBLimit && |
3669 | VarAssignCount > InputDbgValLimit) { |
3670 | LLVM_DEBUG(dbgs() << "Disabling InstrRefBasedLDV: " << MF.getName() |
3671 | << " has " << MaxNumBlocks << " basic blocks and " |
3672 | << VarAssignCount |
3673 | << " variable assignments, exceeding limits.\n"); |
3674 | } else { |
3675 | |
3676 | |
3677 | |
3678 | |
3679 | for (auto &P : ScopeToVars) { |
3680 | vlocDataflow(P.first, ScopeToDILocation[P.first], P.second, |
3681 | ScopeToBlocks[P.first], SavedLiveIns, MOutLocs, MInLocs, |
3682 | vlocs); |
3683 | } |
3684 | |
3685 | |
3686 | |
3687 | |
3688 | emitLocations(MF, SavedLiveIns, MOutLocs, MInLocs, AllVarsNumbering, *TPC); |
3689 | |
3690 | |
3691 | Changed = TTracker->Transfers.size() != 0; |
3692 | } |
3693 | |
3694 | |
3695 | for (int Idx = 0; Idx < MaxNumBlocks; ++Idx) { |
3696 | delete[] MOutLocs[Idx]; |
3697 | delete[] MInLocs[Idx]; |
3698 | } |
3699 | delete[] MOutLocs; |
3700 | delete[] MInLocs; |
3701 | |
3702 | delete MTracker; |
3703 | delete TTracker; |
3704 | MTracker = nullptr; |
3705 | VTracker = nullptr; |
3706 | TTracker = nullptr; |
3707 | |
3708 | ArtificialBlocks.clear(); |
3709 | OrderToBB.clear(); |
3710 | BBToOrder.clear(); |
3711 | BBNumToRPO.clear(); |
3712 | DebugInstrNumToInstr.clear(); |
3713 | DebugPHINumToValue.clear(); |
3714 | |
3715 | return Changed; |
3716 | } |
3717 | |
3718 | LDVImpl *llvm::makeInstrRefBasedLiveDebugValues() { |
3719 | return new InstrRefBasedLDV(); |
3720 | } |
3721 | |
3722 | namespace { |
3723 | class LDVSSABlock; |
3724 | class LDVSSAUpdater; |
3725 | |
3726 | |
3727 | |
3728 | |
3729 | typedef uint64_t BlockValueNum; |
3730 | |
3731 | |
3732 | |
3733 | |
3734 | class LDVSSAPhi { |
3735 | public: |
3736 | SmallVector<std::pair<LDVSSABlock *, BlockValueNum>, 4> IncomingValues; |
3737 | LDVSSABlock *ParentBlock; |
3738 | BlockValueNum PHIValNum; |
3739 | LDVSSAPhi(BlockValueNum PHIValNum, LDVSSABlock *ParentBlock) |
3740 | : ParentBlock(ParentBlock), PHIValNum(PHIValNum) {} |
3741 | |
3742 | LDVSSABlock *getParent() { return ParentBlock; } |
3743 | }; |
3744 | |
3745 | |
3746 | |
3747 | class LDVSSABlockIterator { |
3748 | public: |
3749 | MachineBasicBlock::pred_iterator PredIt; |
3750 | LDVSSAUpdater &Updater; |
3751 | |
3752 | LDVSSABlockIterator(MachineBasicBlock::pred_iterator PredIt, |
3753 | LDVSSAUpdater &Updater) |
3754 | : PredIt(PredIt), Updater(Updater) {} |
3755 | |
3756 | bool operator!=(const LDVSSABlockIterator &OtherIt) const { |
3757 | return OtherIt.PredIt != PredIt; |
3758 | } |
3759 | |
3760 | LDVSSABlockIterator &operator++() { |
3761 | ++PredIt; |
3762 | return *this; |
3763 | } |
3764 | |
3765 | LDVSSABlock *operator*(); |
3766 | }; |
3767 | |
3768 | |
3769 | |
3770 | |
3771 | class LDVSSABlock { |
3772 | public: |
3773 | MachineBasicBlock &BB; |
3774 | LDVSSAUpdater &Updater; |
3775 | using PHIListT = SmallVector<LDVSSAPhi, 1>; |
3776 | |
3777 | PHIListT PHIList; |
3778 | |
3779 | LDVSSABlock(MachineBasicBlock &BB, LDVSSAUpdater &Updater) |
3780 | : BB(BB), Updater(Updater) {} |
3781 | |
3782 | LDVSSABlockIterator succ_begin() { |
3783 | return LDVSSABlockIterator(BB.succ_begin(), Updater); |
3784 | } |
3785 | |
3786 | LDVSSABlockIterator succ_end() { |
3787 | return LDVSSABlockIterator(BB.succ_end(), Updater); |
3788 | } |
3789 | |
3790 | |
3791 | LDVSSAPhi *newPHI(BlockValueNum Value) { |
3792 | PHIList.emplace_back(Value, this); |
3793 | return &PHIList.back(); |
3794 | } |
3795 | |
3796 | |
3797 | PHIListT &phis() { return PHIList; } |
3798 | }; |
3799 | |
3800 | |
3801 | |
3802 | |
3803 | class LDVSSAUpdater { |
3804 | public: |
3805 | |
3806 | DenseMap<BlockValueNum, LDVSSAPhi *> PHIs; |
3807 | |
3808 | |
3809 | DenseMap<MachineBasicBlock *, BlockValueNum> UndefMap; |
3810 | |
3811 | DenseMap<MachineBasicBlock *, LDVSSABlock *> BlockMap; |
3812 | |
3813 | LocIdx Loc; |
3814 | |
3815 | ValueIDNum **MLiveIns; |
3816 | |
3817 | LDVSSAUpdater(LocIdx L, ValueIDNum **MLiveIns) : Loc(L), MLiveIns(MLiveIns) {} |
3818 | |
3819 | void reset() { |
3820 | for (auto &Block : BlockMap) |
3821 | delete Block.second; |
3822 | |
3823 | PHIs.clear(); |
3824 | UndefMap.clear(); |
3825 | BlockMap.clear(); |
3826 | } |
3827 | |
3828 | ~LDVSSAUpdater() { reset(); } |
3829 | |
3830 | |
3831 | |
3832 | LDVSSABlock *getSSALDVBlock(MachineBasicBlock *BB) { |
3833 | auto it = BlockMap.find(BB); |
3834 | if (it == BlockMap.end()) { |
3835 | BlockMap[BB] = new LDVSSABlock(*BB, *this); |
3836 | it = BlockMap.find(BB); |
3837 | } |
3838 | return it->second; |
3839 | } |
3840 | |
3841 | |
3842 | |
3843 | BlockValueNum getValue(LDVSSABlock *LDVBB) { |
3844 | return MLiveIns[LDVBB->BB.getNumber()][Loc.asU64()].asU64(); |
3845 | } |
3846 | }; |
3847 | |
3848 | LDVSSABlock *LDVSSABlockIterator::operator*() { |
3849 | return Updater.getSSALDVBlock(*PredIt); |
3850 | } |
3851 | |
3852 | #ifndef NDEBUG |
3853 | |
3854 | raw_ostream &operator<<(raw_ostream &out, const LDVSSAPhi &PHI) { |
3855 | out << "SSALDVPHI " << PHI.PHIValNum; |
3856 | return out; |
3857 | } |
3858 | |
3859 | #endif |
3860 | |
3861 | } |
3862 | |
3863 | namespace llvm { |
3864 | |
3865 | |
3866 | |
3867 | |
3868 | |
3869 | template <> class SSAUpdaterTraits<LDVSSAUpdater> { |
3870 | public: |
3871 | using BlkT = LDVSSABlock; |
3872 | using ValT = BlockValueNum; |
3873 | using PhiT = LDVSSAPhi; |
3874 | using BlkSucc_iterator = LDVSSABlockIterator; |
3875 | |
3876 | |
3877 | static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); } |
3878 | static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); } |
3879 | |
3880 | |
3881 | class PHI_iterator { |
3882 | private: |
3883 | LDVSSAPhi *PHI; |
3884 | unsigned Idx; |
3885 | |
3886 | public: |
3887 | explicit PHI_iterator(LDVSSAPhi *P) |
3888 | : PHI(P), Idx(0) {} |
3889 | PHI_iterator(LDVSSAPhi *P, bool) |
3890 | : PHI(P), Idx(PHI->IncomingValues.size()) {} |
3891 | |
3892 | PHI_iterator &operator++() { |
3893 | Idx++; |
3894 | return *this; |
3895 | } |
3896 | bool operator==(const PHI_iterator &X) const { return Idx == X.Idx; } |
3897 | bool operator!=(const PHI_iterator &X) const { return !operator==(X); } |
3898 | |
3899 | BlockValueNum getIncomingValue() { return PHI->IncomingValues[Idx].second; } |
3900 | |
3901 | LDVSSABlock *getIncomingBlock() { return PHI->IncomingValues[Idx].first; } |
3902 | }; |
3903 | |
3904 | static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); } |
3905 | |
3906 | static inline PHI_iterator PHI_end(PhiT *PHI) { |
3907 | return PHI_iterator(PHI, true); |
3908 | } |
3909 | |
3910 | |
3911 | |
3912 | static void FindPredecessorBlocks(LDVSSABlock *BB, |
3913 | SmallVectorImpl<LDVSSABlock *> *Preds) { |
3914 | for (MachineBasicBlock::pred_iterator PI = BB->BB.pred_begin(), |
3915 | E = BB->BB.pred_end(); |
3916 | PI != E; ++PI) |
3917 | Preds->push_back(BB->Updater.getSSALDVBlock(*PI)); |
3918 | } |
3919 | |
3920 | |
3921 | |
3922 | |
3923 | static BlockValueNum GetUndefVal(LDVSSABlock *BB, LDVSSAUpdater *Updater) { |
3924 | |
3925 | |
3926 | |
3927 | BlockValueNum Num = ValueIDNum(BB->BB.getNumber(), 0, Updater->Loc).asU64(); |
3928 | Updater->UndefMap[&BB->BB] = Num; |
3929 | return Num; |
3930 | } |
3931 | |
3932 | |
3933 | |
3934 | |
3935 | |
3936 | |
3937 | static BlockValueNum CreateEmptyPHI(LDVSSABlock *BB, unsigned NumPreds, |
3938 | LDVSSAUpdater *Updater) { |
3939 | BlockValueNum PHIValNum = Updater->getValue(BB); |
3940 | LDVSSAPhi *PHI = BB->newPHI(PHIValNum); |
3941 | Updater->PHIs[PHIValNum] = PHI; |
3942 | return PHIValNum; |
3943 | } |
3944 | |
3945 | |
3946 | |
3947 | static void AddPHIOperand(LDVSSAPhi *PHI, BlockValueNum Val, LDVSSABlock *Pred) { |
3948 | PHI->IncomingValues.push_back(std::make_pair(Pred, Val)); |
3949 | } |
3950 | |
3951 | |
3952 | |
3953 | static LDVSSAPhi *ValueIsPHI(BlockValueNum Val, LDVSSAUpdater *Updater) { |
3954 | auto PHIIt = Updater->PHIs.find(Val); |
3955 | if (PHIIt == Updater->PHIs.end()) |
3956 | return nullptr; |
3957 | return PHIIt->second; |
3958 | } |
3959 | |
3960 | |
3961 | |
3962 | static LDVSSAPhi *ValueIsNewPHI(BlockValueNum Val, LDVSSAUpdater *Updater) { |
3963 | LDVSSAPhi *PHI = ValueIsPHI(Val, Updater); |
3964 | if (PHI && PHI->IncomingValues.size() == 0) |
3965 | return PHI; |
3966 | return nullptr; |
3967 | } |
3968 | |
3969 | |
3970 | |
3971 | static BlockValueNum GetPHIValue(LDVSSAPhi *PHI) { return PHI->PHIValNum; } |
3972 | }; |
3973 | |
3974 | } |
3975 | |
3976 | Optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIs(MachineFunction &MF, |
3977 | ValueIDNum **MLiveOuts, |
3978 | ValueIDNum **MLiveIns, |
3979 | MachineInstr &Here, |
3980 | uint64_t InstrNum) { |
3981 | |
3982 | |
3983 | auto RangePair = std::equal_range(DebugPHINumToValue.begin(), |
3984 | DebugPHINumToValue.end(), InstrNum); |
3985 | auto LowerIt = RangePair.first; |
3986 | auto UpperIt = RangePair.second; |
3987 | |
3988 | |
3989 | if (LowerIt == UpperIt) |
3990 | return None; |
3991 | |
3992 | |
3993 | if (std::distance(LowerIt, UpperIt) == 1) |
3994 | return LowerIt->ValueRead; |
3995 | |
3996 | auto DBGPHIRange = make_range(LowerIt, UpperIt); |
3997 | |
3998 | |
3999 | |
4000 | |
4001 | |
4002 | LocIdx Loc = LowerIt->ReadLoc; |
4003 | |
4004 | |
4005 | |
4006 | |
4007 | |
4008 | |
4009 | |
4010 | |
4011 | LDVSSAUpdater Updater(Loc, MLiveIns); |
4012 | |
4013 | DenseMap<LDVSSABlock *, BlockValueNum> AvailableValues; |
4014 | |
4015 | SmallVector<LDVSSAPhi *, 8> CreatedPHIs; |
4016 | |
4017 | |
4018 | |
4019 | for (const auto &DBG_PHI : DBGPHIRange) { |
4020 | LDVSSABlock *Block = Updater.getSSALDVBlock(DBG_PHI.MBB); |
4021 | const ValueIDNum &Num = DBG_PHI.ValueRead; |
4022 | AvailableValues.insert(std::make_pair(Block, Num.asU64())); |
4023 | } |
4024 | |
4025 | LDVSSABlock *HereBlock = Updater.getSSALDVBlock(Here.getParent()); |
4026 | const auto &AvailIt = AvailableValues.find(HereBlock); |
4027 | if (AvailIt != AvailableValues.end()) { |
4028 | |
4029 | |
4030 | return ValueIDNum::fromU64(AvailIt->second); |
4031 | } |
4032 | |
4033 | |
4034 | |
4035 | SSAUpdaterImpl<LDVSSAUpdater> Impl(&Updater, &AvailableValues, &CreatedPHIs); |
4036 | BlockValueNum ResultInt = Impl.GetValue(Updater.getSSALDVBlock(Here.getParent())); |
4037 | ValueIDNum Result = ValueIDNum::fromU64(ResultInt); |
4038 | |
4039 | |
4040 | |
4041 | |
4042 | |
4043 | |
4044 | |
4045 | |
4046 | |
4047 | |
4048 | |
4049 | |
4050 | DenseMap<LDVSSABlock *, ValueIDNum> ValidatedValues; |
4051 | |
4052 | |
4053 | for (const auto &DBG_PHI : DBGPHIRange) { |
4054 | LDVSSABlock *Block = Updater.getSSALDVBlock(DBG_PHI.MBB); |
4055 | const ValueIDNum &Num = DBG_PHI.ValueRead; |
4056 | ValidatedValues.insert(std::make_pair(Block, Num)); |
4057 | } |
4058 | |
4059 | |
4060 | SmallVector<LDVSSAPhi *, 8> SortedPHIs; |
4061 | for (auto &PHI : CreatedPHIs) |
4062 | SortedPHIs.push_back(PHI); |
4063 | |
4064 | std::sort( |
4065 | SortedPHIs.begin(), SortedPHIs.end(), [&](LDVSSAPhi *A, LDVSSAPhi *B) { |
4066 | return BBToOrder[&A->getParent()->BB] < BBToOrder[&B->getParent()->BB]; |
4067 | }); |
4068 | |
4069 | for (auto &PHI : SortedPHIs) { |
4070 | ValueIDNum ThisBlockValueNum = |
4071 | MLiveIns[PHI->ParentBlock->BB.getNumber()][Loc.asU64()]; |
4072 | |
4073 | |
4074 | for (auto &PHIIt : PHI->IncomingValues) { |
4075 | |
4076 | if (Updater.UndefMap.find(&PHIIt.first->BB) != Updater.UndefMap.end()) |
4077 | return None; |
4078 | |
4079 | ValueIDNum ValueToCheck; |
4080 | ValueIDNum *BlockLiveOuts = MLiveOuts[PHIIt.first->BB.getNumber()]; |
4081 | |
4082 | auto VVal = ValidatedValues.find(PHIIt.first); |
4083 | if (VVal == ValidatedValues.end()) { |
4084 | |
4085 | |
4086 | |
4087 | |
4088 | ValueToCheck = ThisBlockValueNum; |
4089 | } else { |
4090 | |
4091 | |
4092 | ValueToCheck = VVal->second; |
4093 | } |
4094 | |
4095 | if (BlockLiveOuts[Loc.asU64()] != ValueToCheck) |
4096 | return None; |
4097 | } |
4098 | |
4099 | |
4100 | ValidatedValues.insert({PHI->ParentBlock, ThisBlockValueNum}); |
4101 | } |
4102 | |
4103 | |
4104 | |
4105 | return Result; |
4106 | } |