LLVM 17.0.0git
AssignmentTrackingAnalysis.cpp
Go to the documentation of this file.
7#include "llvm/ADT/SmallSet.h"
12#include "llvm/IR/BasicBlock.h"
13#include "llvm/IR/DataLayout.h"
14#include "llvm/IR/DebugInfo.h"
15#include "llvm/IR/Function.h"
16#include "llvm/IR/Instruction.h"
18#include "llvm/IR/PassManager.h"
19#include "llvm/IR/PrintPasses.h"
25#include <assert.h>
26#include <cstdint>
27#include <optional>
28#include <sstream>
29#include <unordered_map>
30
31using namespace llvm;
32#define DEBUG_TYPE "debug-ata"
33
34STATISTIC(NumDefsScanned, "Number of dbg locs that get scanned for removal");
35STATISTIC(NumDefsRemoved, "Number of dbg locs removed");
36STATISTIC(NumWedgesScanned, "Number of dbg wedges scanned");
37STATISTIC(NumWedgesChanged, "Number of dbg wedges changed");
38
40 MaxNumBlocks("debug-ata-max-blocks", cl::init(10000),
41 cl::desc("Maximum num basic blocks before debug info dropped"),
43/// Option for debugging the pass, determines if the memory location fragment
44/// filling happens after generating the variable locations.
45static cl::opt<bool> EnableMemLocFragFill("mem-loc-frag-fill", cl::init(true),
47/// Print the results of the analysis. Respects -filter-print-funcs.
48static cl::opt<bool> PrintResults("print-debug-ata", cl::init(false),
50
51// Implicit conversions are disabled for enum class types, so unfortunately we
52// need to create a DenseMapInfo wrapper around the specified underlying type.
53template <> struct llvm::DenseMapInfo<VariableID> {
55 static inline VariableID getEmptyKey() {
56 return static_cast<VariableID>(Wrapped::getEmptyKey());
57 }
58 static inline VariableID getTombstoneKey() {
59 return static_cast<VariableID>(Wrapped::getTombstoneKey());
60 }
61 static unsigned getHashValue(const VariableID &Val) {
62 return Wrapped::getHashValue(static_cast<unsigned>(Val));
63 }
64 static bool isEqual(const VariableID &LHS, const VariableID &RHS) {
65 return LHS == RHS;
66 }
67};
68
69/// Helper class to build FunctionVarLocs, since that class isn't easy to
70/// modify. TODO: There's not a great deal of value in the split, it could be
71/// worth merging the two classes.
73 friend FunctionVarLocs;
75 // Use an unordered_map so we don't invalidate iterators after
76 // insert/modifications.
77 std::unordered_map<const Instruction *, SmallVector<VarLocInfo>>
78 VarLocsBeforeInst;
79
80 SmallVector<VarLocInfo> SingleLocVars;
81
82public:
83 unsigned getNumVariables() const { return Variables.size(); }
84
85 /// Find or insert \p V and return the ID.
87 return static_cast<VariableID>(Variables.insert(V));
88 }
89
90 /// Get a variable from its \p ID.
92 return Variables[static_cast<unsigned>(ID)];
93 }
94
95 /// Return ptr to wedge of defs or nullptr if no defs come just before /p
96 /// Before.
97 const SmallVectorImpl<VarLocInfo> *getWedge(const Instruction *Before) const {
98 auto R = VarLocsBeforeInst.find(Before);
99 if (R == VarLocsBeforeInst.end())
100 return nullptr;
101 return &R->second;
102 }
103
104 /// Replace the defs that come just before /p Before with /p Wedge.
105 void setWedge(const Instruction *Before, SmallVector<VarLocInfo> &&Wedge) {
106 VarLocsBeforeInst[Before] = std::move(Wedge);
107 }
108
109 /// Add a def for a variable that is valid for its lifetime.
112 VarLocInfo VarLoc;
113 VarLoc.VariableID = insertVariable(Var);
114 VarLoc.Expr = Expr;
115 VarLoc.DL = DL;
116 VarLoc.Values = R;
117 SingleLocVars.emplace_back(VarLoc);
118 }
119
120 /// Add a def to the wedge of defs just before /p Before.
123 VarLocInfo VarLoc;
124 VarLoc.VariableID = insertVariable(Var);
125 VarLoc.Expr = Expr;
126 VarLoc.DL = DL;
127 VarLoc.Values = R;
128 VarLocsBeforeInst[Before].emplace_back(VarLoc);
129 }
130};
131
133 // Print the variable table first. TODO: Sorting by variable could make the
134 // output more stable?
135 unsigned Counter = -1;
136 OS << "=== Variables ===\n";
137 for (const DebugVariable &V : Variables) {
138 ++Counter;
139 // Skip first entry because it is a dummy entry.
140 if (Counter == 0) {
141 continue;
142 }
143 OS << "[" << Counter << "] " << V.getVariable()->getName();
144 if (auto F = V.getFragment())
145 OS << " bits [" << F->OffsetInBits << ", "
146 << F->OffsetInBits + F->SizeInBits << ")";
147 if (const auto *IA = V.getInlinedAt())
148 OS << " inlined-at " << *IA;
149 OS << "\n";
150 }
151
152 auto PrintLoc = [&OS](const VarLocInfo &Loc) {
153 OS << "DEF Var=[" << (unsigned)Loc.VariableID << "]"
154 << " Expr=" << *Loc.Expr << " Values=(";
155 for (auto *Op : Loc.Values.location_ops()) {
156 errs() << Op->getName() << " ";
157 }
158 errs() << ")\n";
159 };
160
161 // Print the single location variables.
162 OS << "=== Single location vars ===\n";
163 for (auto It = single_locs_begin(), End = single_locs_end(); It != End;
164 ++It) {
165 PrintLoc(*It);
166 }
167
168 // Print the non-single-location defs in line with IR.
169 OS << "=== In-line variable defs ===";
170 for (const BasicBlock &BB : Fn) {
171 OS << "\n" << BB.getName() << ":\n";
172 for (const Instruction &I : BB) {
173 for (auto It = locs_begin(&I), End = locs_end(&I); It != End; ++It) {
174 PrintLoc(*It);
175 }
176 OS << I << "\n";
177 }
178 }
179}
180
182 // Add the single-location variables first.
183 for (const auto &VarLoc : Builder.SingleLocVars)
184 VarLocRecords.emplace_back(VarLoc);
185 // Mark the end of the section.
186 SingleVarLocEnd = VarLocRecords.size();
187
188 // Insert a contiguous block of VarLocInfos for each instruction, mapping it
189 // to the start and end position in the vector with VarLocsBeforeInst.
190 for (auto &P : Builder.VarLocsBeforeInst) {
191 unsigned BlockStart = VarLocRecords.size();
192 for (const VarLocInfo &VarLoc : P.second)
193 VarLocRecords.emplace_back(VarLoc);
194 unsigned BlockEnd = VarLocRecords.size();
195 // Record the start and end indices.
196 if (BlockEnd != BlockStart)
197 VarLocsBeforeInst[P.first] = {BlockStart, BlockEnd};
198 }
199
200 // Copy the Variables vector from the builder's UniqueVector.
201 assert(Variables.empty() && "Expect clear before init");
202 // UniqueVectors IDs are one-based (which means the VarLocInfo VarID values
203 // are one-based) so reserve an extra and insert a dummy.
204 Variables.reserve(Builder.Variables.size() + 1);
205 Variables.push_back(DebugVariable(nullptr, std::nullopt, nullptr));
206 Variables.append(Builder.Variables.begin(), Builder.Variables.end());
207}
208
210 Variables.clear();
211 VarLocRecords.clear();
212 VarLocsBeforeInst.clear();
213 SingleVarLocEnd = 0;
214}
215
216/// Walk backwards along constant GEPs and bitcasts to the base storage from \p
217/// Start as far as possible. Prepend \Expression with the offset and append it
218/// with a DW_OP_deref that haes been implicit until now. Returns the walked-to
219/// value and modified expression.
220static std::pair<Value *, DIExpression *>
223 APInt OffsetInBytes(DL.getTypeSizeInBits(Start->getType()), false);
224 Value *End =
225 Start->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetInBytes);
227 if (OffsetInBytes.getBoolValue()) {
228 Ops = {dwarf::DW_OP_plus_uconst, OffsetInBytes.getZExtValue()};
230 Expression, Ops, /*StackValue=*/false, /*EntryValue=*/false);
231 }
232 Expression = DIExpression::append(Expression, {dwarf::DW_OP_deref});
233 return {End, Expression};
234}
235
236/// Extract the offset used in \p DIExpr. Returns std::nullopt if the expression
237/// doesn't explicitly describe a memory location with DW_OP_deref or if the
238/// expression is too complex to interpret.
239static std::optional<int64_t>
241 int64_t Offset = 0;
242 const unsigned NumElements = DIExpr->getNumElements();
243 const auto Elements = DIExpr->getElements();
244 unsigned ExpectedDerefIdx = 0;
245 // Extract the offset.
246 if (NumElements > 2 && Elements[0] == dwarf::DW_OP_plus_uconst) {
247 Offset = Elements[1];
248 ExpectedDerefIdx = 2;
249 } else if (NumElements > 3 && Elements[0] == dwarf::DW_OP_constu) {
250 ExpectedDerefIdx = 3;
251 if (Elements[2] == dwarf::DW_OP_plus)
252 Offset = Elements[1];
253 else if (Elements[2] == dwarf::DW_OP_minus)
254 Offset = -Elements[1];
255 else
256 return std::nullopt;
257 }
258
259 // If that's all there is it means there's no deref.
260 if (ExpectedDerefIdx >= NumElements)
261 return std::nullopt;
262
263 // Check the next element is DW_OP_deref - otherwise this is too complex or
264 // isn't a deref expression.
265 if (Elements[ExpectedDerefIdx] != dwarf::DW_OP_deref)
266 return std::nullopt;
267
268 // Check the final operation is either the DW_OP_deref or is a fragment.
269 if (NumElements == ExpectedDerefIdx + 1)
270 return Offset; // Ends with deref.
271 unsigned ExpectedFragFirstIdx = ExpectedDerefIdx + 1;
272 unsigned ExpectedFragFinalIdx = ExpectedFragFirstIdx + 2;
273 if (NumElements == ExpectedFragFinalIdx + 1 &&
274 Elements[ExpectedFragFirstIdx] == dwarf::DW_OP_LLVM_fragment)
275 return Offset; // Ends with deref + fragment.
276
277 // Don't bother trying to interpret anything more complex.
278 return std::nullopt;
279}
280
281/// A whole (unfragmented) source variable.
282using DebugAggregate = std::pair<const DILocalVariable *, const DILocation *>;
284 return DebugAggregate(DII->getVariable(), DII->getDebugLoc().getInlinedAt());
285}
287 return DebugAggregate(Var.getVariable(), Var.getInlinedAt());
288}
289
290namespace {
291/// In dwarf emission, the following sequence
292/// 1. dbg.value ... Fragment(0, 64)
293/// 2. dbg.value ... Fragment(0, 32)
294/// effectively sets Fragment(32, 32) to undef (each def sets all bits not in
295/// the intersection of the fragments to having "no location"). This makes
296/// sense for implicit location values because splitting the computed values
297/// could be troublesome, and is probably quite uncommon. When we convert
298/// dbg.assigns to dbg.value+deref this kind of thing is common, and describing
299/// a location (memory) rather than a value means we don't need to worry about
300/// splitting any values, so we try to recover the rest of the fragment
301/// location here.
302/// This class performs a(nother) dataflow analysis over the function, adding
303/// variable locations so that any bits of a variable with a memory location
304/// have that location explicitly reinstated at each subsequent variable
305/// location definition that that doesn't overwrite those bits. i.e. after a
306/// variable location def, insert new defs for the memory location with
307/// fragments for the difference of "all bits currently in memory" and "the
308/// fragment of the second def".
309class MemLocFragmentFill {
310 Function &Fn;
311 FunctionVarLocsBuilder *FnVarLocs;
312 const DenseSet<DebugAggregate> *VarsWithStackSlot;
313
314 // 0 = no memory location.
315 using BaseAddress = unsigned;
316 using OffsetInBitsTy = unsigned;
318 using FragsInMemMap = IntervalMap<
319 OffsetInBitsTy, BaseAddress,
321 FragTraits>;
322 FragsInMemMap::Allocator IntervalMapAlloc;
323 using VarFragMap = DenseMap<unsigned, FragsInMemMap>;
324
325 /// IDs for memory location base addresses in maps. Use 0 to indicate that
326 /// there's no memory location.
331
332 struct FragMemLoc {
333 unsigned Var;
334 unsigned Base;
335 unsigned OffsetInBits;
336 unsigned SizeInBits;
337 DebugLoc DL;
338 };
340
341 /// BBInsertBeforeMap holds a description for the set of location defs to be
342 /// inserted after the analysis is complete. It is updated during the dataflow
343 /// and the entry for a block is CLEARED each time it is (re-)visited. After
344 /// the dataflow is complete, each block entry will contain the set of defs
345 /// calculated during the final (fixed-point) iteration.
347
348 static bool intervalMapsAreEqual(const FragsInMemMap &A,
349 const FragsInMemMap &B) {
350 auto AIt = A.begin(), AEnd = A.end();
351 auto BIt = B.begin(), BEnd = B.end();
352 for (; AIt != AEnd; ++AIt, ++BIt) {
353 if (BIt == BEnd)
354 return false; // B has fewer elements than A.
355 if (AIt.start() != BIt.start() || AIt.stop() != BIt.stop())
356 return false; // Interval is different.
357 if (*AIt != *BIt)
358 return false; // Value at interval is different.
359 }
360 // AIt == AEnd. Check BIt is also now at end.
361 return BIt == BEnd;
362 }
363
364 static bool varFragMapsAreEqual(const VarFragMap &A, const VarFragMap &B) {
365 if (A.size() != B.size())
366 return false;
367 for (const auto &APair : A) {
368 auto BIt = B.find(APair.first);
369 if (BIt == B.end())
370 return false;
371 if (!intervalMapsAreEqual(APair.second, BIt->second))
372 return false;
373 }
374 return true;
375 }
376
377 /// Return a string for the value that \p BaseID represents.
378 std::string toString(unsigned BaseID) {
379 if (BaseID)
380 return Bases[BaseID].getVariableLocationOp(0)->getName().str();
381 else
382 return "None";
383 }
384
385 /// Format string describing an FragsInMemMap (IntervalMap) interval.
386 std::string toString(FragsInMemMap::const_iterator It, bool Newline = true) {
387 std::string String;
388 std::stringstream S(String);
389 if (It.valid()) {
390 S << "[" << It.start() << ", " << It.stop()
391 << "): " << toString(It.value());
392 } else {
393 S << "invalid iterator (end)";
394 }
395 if (Newline)
396 S << "\n";
397 return S.str();
398 };
399
400 FragsInMemMap meetFragments(const FragsInMemMap &A, const FragsInMemMap &B) {
401 FragsInMemMap Result(IntervalMapAlloc);
402 for (auto AIt = A.begin(), AEnd = A.end(); AIt != AEnd; ++AIt) {
403 LLVM_DEBUG(dbgs() << "a " << toString(AIt));
404 // This is basically copied from process() and inverted (process is
405 // performing something like a union whereas this is more of an
406 // intersect).
407
408 // There's no work to do if interval `a` overlaps no fragments in map `B`.
409 if (!B.overlaps(AIt.start(), AIt.stop()))
410 continue;
411
412 // Does StartBit intersect an existing fragment?
413 auto FirstOverlap = B.find(AIt.start());
414 assert(FirstOverlap != B.end());
415 bool IntersectStart = FirstOverlap.start() < AIt.start();
416 LLVM_DEBUG(dbgs() << "- FirstOverlap " << toString(FirstOverlap, false)
417 << ", IntersectStart: " << IntersectStart << "\n");
418
419 // Does EndBit intersect an existing fragment?
420 auto LastOverlap = B.find(AIt.stop());
421 bool IntersectEnd =
422 LastOverlap != B.end() && LastOverlap.start() < AIt.stop();
423 LLVM_DEBUG(dbgs() << "- LastOverlap " << toString(LastOverlap, false)
424 << ", IntersectEnd: " << IntersectEnd << "\n");
425
426 // Check if both ends of `a` intersect the same interval `b`.
427 if (IntersectStart && IntersectEnd && FirstOverlap == LastOverlap) {
428 // Insert `a` (`a` is contained in `b`) if the values match.
429 // [ a ]
430 // [ - b - ]
431 // -
432 // [ r ]
433 LLVM_DEBUG(dbgs() << "- a is contained within "
434 << toString(FirstOverlap));
435 if (*AIt && *AIt == *FirstOverlap)
436 Result.insert(AIt.start(), AIt.stop(), *AIt);
437 } else {
438 // There's an overlap but `a` is not fully contained within
439 // `b`. Shorten any end-point intersections.
440 // [ - a - ]
441 // [ - b - ]
442 // -
443 // [ r ]
444 auto Next = FirstOverlap;
445 if (IntersectStart) {
446 LLVM_DEBUG(dbgs() << "- insert intersection of a and "
447 << toString(FirstOverlap));
448 if (*AIt && *AIt == *FirstOverlap)
449 Result.insert(AIt.start(), FirstOverlap.stop(), *AIt);
450 ++Next;
451 }
452 // [ - a - ]
453 // [ - b - ]
454 // -
455 // [ r ]
456 if (IntersectEnd) {
457 LLVM_DEBUG(dbgs() << "- insert intersection of a and "
458 << toString(LastOverlap));
459 if (*AIt && *AIt == *LastOverlap)
460 Result.insert(LastOverlap.start(), AIt.stop(), *AIt);
461 }
462
463 // Insert all intervals in map `B` that are contained within interval
464 // `a` where the values match.
465 // [ - - a - - ]
466 // [ b1 ] [ b2 ]
467 // -
468 // [ r1 ] [ r2 ]
469 while (Next != B.end() && Next.start() < AIt.stop() &&
470 Next.stop() <= AIt.stop()) {
472 << "- insert intersection of a and " << toString(Next));
473 if (*AIt && *AIt == *Next)
474 Result.insert(Next.start(), Next.stop(), *Next);
475 ++Next;
476 }
477 }
478 }
479 return Result;
480 }
481
482 /// Meet \p A and \p B, storing the result in \p A.
483 void meetVars(VarFragMap &A, const VarFragMap &B) {
484 // Meet A and B.
485 //
486 // Result = meet(a, b) for a in A, b in B where Var(a) == Var(b)
487 for (auto It = A.begin(), End = A.end(); It != End; ++It) {
488 unsigned AVar = It->first;
489 FragsInMemMap &AFrags = It->second;
490 auto BIt = B.find(AVar);
491 if (BIt == B.end()) {
492 A.erase(It);
493 continue; // Var has no bits defined in B.
494 }
495 LLVM_DEBUG(dbgs() << "meet fragment maps for "
496 << Aggregates[AVar].first->getName() << "\n");
497 AFrags = meetFragments(AFrags, BIt->second);
498 }
499 }
500
501 bool meet(const BasicBlock &BB,
502 const SmallPtrSet<BasicBlock *, 16> &Visited) {
503 LLVM_DEBUG(dbgs() << "meet block info from preds of " << BB.getName()
504 << "\n");
505
506 VarFragMap BBLiveIn;
507 bool FirstMeet = true;
508 // LiveIn locs for BB is the meet of the already-processed preds' LiveOut
509 // locs.
510 for (auto I = pred_begin(&BB), E = pred_end(&BB); I != E; I++) {
511 // Ignore preds that haven't been processed yet. This is essentially the
512 // same as initialising all variables to implicit top value (⊤) which is
513 // the identity value for the meet operation.
514 const BasicBlock *Pred = *I;
515 if (!Visited.count(Pred))
516 continue;
517
518 auto PredLiveOut = LiveOut.find(Pred);
519 assert(PredLiveOut != LiveOut.end());
520
521 if (FirstMeet) {
522 LLVM_DEBUG(dbgs() << "BBLiveIn = " << Pred->getName() << "\n");
523 BBLiveIn = PredLiveOut->second;
524 FirstMeet = false;
525 } else {
526 LLVM_DEBUG(dbgs() << "BBLiveIn = meet BBLiveIn, " << Pred->getName()
527 << "\n");
528 meetVars(BBLiveIn, PredLiveOut->second);
529 }
530
531 // An empty set is ⊥ for the intersect-like meet operation. If we've
532 // already got ⊥ there's no need to run the code - we know the result is
533 // ⊥ since `meet(a, ⊥) = ⊥`.
534 if (BBLiveIn.size() == 0)
535 break;
536 }
537
538 auto CurrentLiveInEntry = LiveIn.find(&BB);
539 // If there's no LiveIn entry for the block yet, add it.
540 if (CurrentLiveInEntry == LiveIn.end()) {
541 LLVM_DEBUG(dbgs() << "change=true (first) on meet on " << BB.getName()
542 << "\n");
543 LiveIn[&BB] = std::move(BBLiveIn);
544 return /*Changed=*/true;
545 }
546
547 // If the LiveIn set has changed (expensive check) update it and return
548 // true.
549 if (!varFragMapsAreEqual(BBLiveIn, CurrentLiveInEntry->second)) {
550 LLVM_DEBUG(dbgs() << "change=true on meet on " << BB.getName() << "\n");
551 CurrentLiveInEntry->second = std::move(BBLiveIn);
552 return /*Changed=*/true;
553 }
554
555 LLVM_DEBUG(dbgs() << "change=false on meet on " << BB.getName() << "\n");
556 return /*Changed=*/false;
557 }
558
559 void insertMemLoc(BasicBlock &BB, Instruction &Before, unsigned Var,
560 unsigned StartBit, unsigned EndBit, unsigned Base,
561 DebugLoc DL) {
562 assert(StartBit < EndBit && "Cannot create fragment of size <= 0");
563 if (!Base)
564 return;
565 FragMemLoc Loc;
566 Loc.Var = Var;
567 Loc.OffsetInBits = StartBit;
568 Loc.SizeInBits = EndBit - StartBit;
569 assert(Base && "Expected a non-zero ID for Base address");
570 Loc.Base = Base;
571 Loc.DL = DL;
572 BBInsertBeforeMap[&BB][&Before].push_back(Loc);
573 LLVM_DEBUG(dbgs() << "Add mem def for " << Aggregates[Var].first->getName()
574 << " bits [" << StartBit << ", " << EndBit << ")\n");
575 }
576
577 void addDef(const VarLocInfo &VarLoc, Instruction &Before, BasicBlock &BB,
578 VarFragMap &LiveSet) {
579 DebugVariable DbgVar = FnVarLocs->getVariable(VarLoc.VariableID);
580 if (skipVariable(DbgVar.getVariable()))
581 return;
582 // Don't bother doing anything for this variables if we know it's fully
583 // promoted. We're only interested in variables that (sometimes) live on
584 // the stack here.
585 if (!VarsWithStackSlot->count(getAggregate(DbgVar)))
586 return;
587 unsigned Var = Aggregates.insert(
588 DebugAggregate(DbgVar.getVariable(), VarLoc.DL.getInlinedAt()));
589
590 // [StartBit: EndBit) are the bits affected by this def.
591 const DIExpression *DIExpr = VarLoc.Expr;
592 unsigned StartBit;
593 unsigned EndBit;
594 if (auto Frag = DIExpr->getFragmentInfo()) {
595 StartBit = Frag->OffsetInBits;
596 EndBit = StartBit + Frag->SizeInBits;
597 } else {
598 assert(static_cast<bool>(DbgVar.getVariable()->getSizeInBits()));
599 StartBit = 0;
600 EndBit = *DbgVar.getVariable()->getSizeInBits();
601 }
602
603 // We will only fill fragments for simple memory-describing dbg.value
604 // intrinsics. If the fragment offset is the same as the offset from the
605 // base pointer, do The Thing, otherwise fall back to normal dbg.value
606 // behaviour. AssignmentTrackingLowering has generated DIExpressions
607 // written in terms of the base pointer.
608 // TODO: Remove this condition since the fragment offset doesn't always
609 // equal the offset from base pointer (e.g. for a SROA-split variable).
610 const auto DerefOffsetInBytes = getDerefOffsetInBytes(DIExpr);
611 const unsigned Base =
612 DerefOffsetInBytes && *DerefOffsetInBytes * 8 == StartBit
613 ? Bases.insert(VarLoc.Values)
614 : 0;
615 LLVM_DEBUG(dbgs() << "DEF " << DbgVar.getVariable()->getName() << " ["
616 << StartBit << ", " << EndBit << "): " << toString(Base)
617 << "\n");
618
619 // First of all, any locs that use mem that are disrupted need reinstating.
620 // Unfortunately, IntervalMap doesn't let us insert intervals that overlap
621 // with existing intervals so this code involves a lot of fiddling around
622 // with intervals to do that manually.
623 auto FragIt = LiveSet.find(Var);
624
625 // Check if the variable does not exist in the map.
626 if (FragIt == LiveSet.end()) {
627 // Add this variable to the BB map.
628 auto P = LiveSet.try_emplace(Var, FragsInMemMap(IntervalMapAlloc));
629 assert(P.second && "Var already in map?");
630 // Add the interval to the fragment map.
631 P.first->second.insert(StartBit, EndBit, Base);
632 return;
633 }
634 // The variable has an entry in the map.
635
636 FragsInMemMap &FragMap = FragIt->second;
637 // First check the easy case: the new fragment `f` doesn't overlap with any
638 // intervals.
639 if (!FragMap.overlaps(StartBit, EndBit)) {
640 LLVM_DEBUG(dbgs() << "- No overlaps\n");
641 FragMap.insert(StartBit, EndBit, Base);
642 return;
643 }
644 // There is at least one overlap.
645
646 // Does StartBit intersect an existing fragment?
647 auto FirstOverlap = FragMap.find(StartBit);
648 assert(FirstOverlap != FragMap.end());
649 bool IntersectStart = FirstOverlap.start() < StartBit;
650
651 // Does EndBit intersect an existing fragment?
652 auto LastOverlap = FragMap.find(EndBit);
653 bool IntersectEnd = LastOverlap.valid() && LastOverlap.start() < EndBit;
654
655 // Check if both ends of `f` intersect the same interval `i`.
656 if (IntersectStart && IntersectEnd && FirstOverlap == LastOverlap) {
657 LLVM_DEBUG(dbgs() << "- Intersect single interval @ both ends\n");
658 // Shorten `i` so that there's space to insert `f`.
659 // [ f ]
660 // [ - i - ]
661 // +
662 // [ i ][ f ][ i ]
663
664 // Save values for use after inserting a new interval.
665 auto EndBitOfOverlap = FirstOverlap.stop();
666 unsigned OverlapValue = FirstOverlap.value();
667
668 // Shorten the overlapping interval.
669 FirstOverlap.setStop(StartBit);
670 insertMemLoc(BB, Before, Var, FirstOverlap.start(), StartBit,
671 OverlapValue, VarLoc.DL);
672
673 // Insert a new interval to represent the end part.
674 FragMap.insert(EndBit, EndBitOfOverlap, OverlapValue);
675 insertMemLoc(BB, Before, Var, EndBit, EndBitOfOverlap, OverlapValue,
676 VarLoc.DL);
677
678 // Insert the new (middle) fragment now there is space.
679 FragMap.insert(StartBit, EndBit, Base);
680 } else {
681 // There's an overlap but `f` may not be fully contained within
682 // `i`. Shorten any end-point intersections so that we can then
683 // insert `f`.
684 // [ - f - ]
685 // [ - i - ]
686 // | |
687 // [ i ]
688 // Shorten any end-point intersections.
689 if (IntersectStart) {
690 LLVM_DEBUG(dbgs() << "- Intersect interval at start\n");
691 // Split off at the intersection.
692 FirstOverlap.setStop(StartBit);
693 insertMemLoc(BB, Before, Var, FirstOverlap.start(), StartBit,
694 *FirstOverlap, VarLoc.DL);
695 }
696 // [ - f - ]
697 // [ - i - ]
698 // | |
699 // [ i ]
700 if (IntersectEnd) {
701 LLVM_DEBUG(dbgs() << "- Intersect interval at end\n");
702 // Split off at the intersection.
703 LastOverlap.setStart(EndBit);
704 insertMemLoc(BB, Before, Var, EndBit, LastOverlap.stop(), *LastOverlap,
705 VarLoc.DL);
706 }
707
708 LLVM_DEBUG(dbgs() << "- Erase intervals contained within\n");
709 // FirstOverlap and LastOverlap have been shortened such that they're
710 // no longer overlapping with [StartBit, EndBit). Delete any overlaps
711 // that remain (these will be fully contained within `f`).
712 // [ - f - ] }
713 // [ - i - ] } Intersection shortening that has happened above.
714 // | | }
715 // [ i ] }
716 // -----------------
717 // [i2 ] } Intervals fully contained within `f` get erased.
718 // -----------------
719 // [ - f - ][ i ] } Completed insertion.
720 auto It = FirstOverlap;
721 if (IntersectStart)
722 ++It; // IntersectStart: first overlap has been shortened.
723 while (It.valid() && It.start() >= StartBit && It.stop() <= EndBit) {
724 LLVM_DEBUG(dbgs() << "- Erase " << toString(It));
725 It.erase(); // This increments It after removing the interval.
726 }
727 // We've dealt with all the overlaps now!
728 assert(!FragMap.overlaps(StartBit, EndBit));
729 LLVM_DEBUG(dbgs() << "- Insert DEF into now-empty space\n");
730 FragMap.insert(StartBit, EndBit, Base);
731 }
732 }
733
734 bool skipVariable(const DILocalVariable *V) { return !V->getSizeInBits(); }
735
736 void process(BasicBlock &BB, VarFragMap &LiveSet) {
737 BBInsertBeforeMap[&BB].clear();
738 for (auto &I : BB) {
739 if (const auto *Locs = FnVarLocs->getWedge(&I)) {
740 for (const VarLocInfo &Loc : *Locs) {
741 addDef(Loc, I, *I.getParent(), LiveSet);
742 }
743 }
744 }
745 }
746
747public:
748 MemLocFragmentFill(Function &Fn,
749 const DenseSet<DebugAggregate> *VarsWithStackSlot)
750 : Fn(Fn), VarsWithStackSlot(VarsWithStackSlot) {}
751
752 /// Add variable locations to \p FnVarLocs so that any bits of a variable
753 /// with a memory location have that location explicitly reinstated at each
754 /// subsequent variable location definition that that doesn't overwrite those
755 /// bits. i.e. after a variable location def, insert new defs for the memory
756 /// location with fragments for the difference of "all bits currently in
757 /// memory" and "the fragment of the second def". e.g.
758 ///
759 /// Before:
760 ///
761 /// var x bits 0 to 63: value in memory
762 /// more instructions
763 /// var x bits 0 to 31: value is %0
764 ///
765 /// After:
766 ///
767 /// var x bits 0 to 63: value in memory
768 /// more instructions
769 /// var x bits 0 to 31: value is %0
770 /// var x bits 32 to 61: value in memory ; <-- new loc def
771 ///
772 void run(FunctionVarLocsBuilder *FnVarLocs) {
774 return;
775
776 this->FnVarLocs = FnVarLocs;
777
778 // Prepare for traversal.
779 //
781 std::priority_queue<unsigned int, std::vector<unsigned int>,
782 std::greater<unsigned int>>
783 Worklist;
784 std::priority_queue<unsigned int, std::vector<unsigned int>,
785 std::greater<unsigned int>>
786 Pending;
789 { // Init OrderToBB and BBToOrder.
790 unsigned int RPONumber = 0;
791 for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
792 OrderToBB[RPONumber] = *RI;
793 BBToOrder[*RI] = RPONumber;
794 Worklist.push(RPONumber);
795 ++RPONumber;
796 }
797 LiveIn.init(RPONumber);
798 LiveOut.init(RPONumber);
799 }
800
801 // Perform the traversal.
802 //
803 // This is a standard "intersect of predecessor outs" dataflow problem. To
804 // solve it, we perform meet() and process() using the two worklist method
805 // until the LiveIn data for each block becomes unchanging.
806 //
807 // This dataflow is essentially working on maps of sets and at each meet we
808 // intersect the maps and the mapped sets. So, initialized live-in maps
809 // monotonically decrease in value throughout the dataflow.
811 while (!Worklist.empty() || !Pending.empty()) {
812 // We track what is on the pending worklist to avoid inserting the same
813 // thing twice. We could avoid this with a custom priority queue, but
814 // this is probably not worth it.
816 LLVM_DEBUG(dbgs() << "Processing Worklist\n");
817 while (!Worklist.empty()) {
818 BasicBlock *BB = OrderToBB[Worklist.top()];
819 LLVM_DEBUG(dbgs() << "\nPop BB " << BB->getName() << "\n");
820 Worklist.pop();
821 bool InChanged = meet(*BB, Visited);
822 // Always consider LiveIn changed on the first visit.
823 InChanged |= Visited.insert(BB).second;
824 if (InChanged) {
826 << BB->getName() << " has new InLocs, process it\n");
827 // Mutate a copy of LiveIn while processing BB. Once we've processed
828 // the terminator LiveSet is the LiveOut set for BB.
829 // This is an expensive copy!
830 VarFragMap LiveSet = LiveIn[BB];
831
832 // Process the instructions in the block.
833 process(*BB, LiveSet);
834
835 // Relatively expensive check: has anything changed in LiveOut for BB?
836 if (!varFragMapsAreEqual(LiveOut[BB], LiveSet)) {
837 LLVM_DEBUG(dbgs() << BB->getName()
838 << " has new OutLocs, add succs to worklist: [ ");
839 LiveOut[BB] = std::move(LiveSet);
840 for (auto I = succ_begin(BB), E = succ_end(BB); I != E; I++) {
841 if (OnPending.insert(*I).second) {
842 LLVM_DEBUG(dbgs() << I->getName() << " ");
843 Pending.push(BBToOrder[*I]);
844 }
845 }
846 LLVM_DEBUG(dbgs() << "]\n");
847 }
848 }
849 }
850 Worklist.swap(Pending);
851 // At this point, pending must be empty, since it was just the empty
852 // worklist
853 assert(Pending.empty() && "Pending should be empty");
854 }
855
856 // Insert new location defs.
857 for (auto &Pair : BBInsertBeforeMap) {
858 InsertMap &Map = Pair.second;
859 for (auto &Pair : Map) {
860 Instruction *InsertBefore = Pair.first;
861 assert(InsertBefore && "should never be null");
862 auto FragMemLocs = Pair.second;
863 auto &Ctx = Fn.getContext();
864
865 for (auto &FragMemLoc : FragMemLocs) {
866 DIExpression *Expr = DIExpression::get(Ctx, std::nullopt);
868 Expr, FragMemLoc.OffsetInBits, FragMemLoc.SizeInBits);
870 FragMemLoc.OffsetInBits / 8);
871 DebugVariable Var(Aggregates[FragMemLoc.Var].first, Expr,
872 FragMemLoc.DL.getInlinedAt());
873 FnVarLocs->addVarLoc(InsertBefore, Var, Expr, FragMemLoc.DL,
874 Bases[FragMemLoc.Base]);
875 }
876 }
877 }
878 }
879};
880
881/// AssignmentTrackingLowering encapsulates a dataflow analysis over a function
882/// that interprets assignment tracking debug info metadata and stores in IR to
883/// create a map of variable locations.
884class AssignmentTrackingLowering {
885public:
886 /// The kind of location in use for a variable, where Mem is the stack home,
887 /// Val is an SSA value or const, and None means that there is not one single
888 /// kind (either because there are multiple or because there is none; it may
889 /// prove useful to split this into two values in the future).
890 ///
891 /// LocKind is a join-semilattice with the partial order:
892 /// None > Mem, Val
893 ///
894 /// i.e.
895 /// join(Mem, Mem) = Mem
896 /// join(Val, Val) = Val
897 /// join(Mem, Val) = None
898 /// join(None, Mem) = None
899 /// join(None, Val) = None
900 /// join(None, None) = None
901 ///
902 /// Note: the order is not `None > Val > Mem` because we're using DIAssignID
903 /// to name assignments and are not tracking the actual stored values.
904 /// Therefore currently there's no way to ensure that Mem values and Val
905 /// values are the same. This could be a future extension, though it's not
906 /// clear that many additional locations would be recovered that way in
907 /// practice as the likelihood of this sitation arising naturally seems
908 /// incredibly low.
909 enum class LocKind { Mem, Val, None };
910
911 /// An abstraction of the assignment of a value to a variable or memory
912 /// location.
913 ///
914 /// An Assignment is Known or NoneOrPhi. A Known Assignment means we have a
915 /// DIAssignID ptr that represents it. NoneOrPhi means that we don't (or
916 /// can't) know the ID of the last assignment that took place.
917 ///
918 /// The Status of the Assignment (Known or NoneOrPhi) is another
919 /// join-semilattice. The partial order is:
920 /// NoneOrPhi > Known {id_0, id_1, ...id_N}
921 ///
922 /// i.e. for all values x and y where x != y:
923 /// join(x, x) = x
924 /// join(x, y) = NoneOrPhi
925 struct Assignment {
926 enum S { Known, NoneOrPhi } Status;
927 /// ID of the assignment. nullptr if Status is not Known.
928 DIAssignID *ID;
929 /// The dbg.assign that marks this dbg-def. Mem-defs don't use this field.
930 /// May be nullptr.
932
933 bool isSameSourceAssignment(const Assignment &Other) const {
934 // Don't include Source in the equality check. Assignments are
935 // defined by their ID, not debug intrinsic(s).
936 return std::tie(Status, ID) == std::tie(Other.Status, Other.ID);
937 }
938 void dump(raw_ostream &OS) {
939 static const char *LUT[] = {"Known", "NoneOrPhi"};
940 OS << LUT[Status] << "(id=";
941 if (ID)
942 OS << ID;
943 else
944 OS << "null";
945 OS << ", s=";
946 if (Source)
947 OS << *Source;
948 else
949 OS << "null";
950 OS << ")";
951 }
952
953 static Assignment make(DIAssignID *ID, DbgAssignIntrinsic *Source) {
954 return Assignment(Known, ID, Source);
955 }
956 static Assignment makeFromMemDef(DIAssignID *ID) {
957 return Assignment(Known, ID, nullptr);
958 }
959 static Assignment makeNoneOrPhi() {
960 return Assignment(NoneOrPhi, nullptr, nullptr);
961 }
962 // Again, need a Top value?
963 Assignment()
964 : Status(NoneOrPhi), ID(nullptr), Source(nullptr) {
965 } // Can we delete this?
966 Assignment(S Status, DIAssignID *ID, DbgAssignIntrinsic *Source)
967 : Status(Status), ID(ID), Source(Source) {
968 // If the Status is Known then we expect there to be an assignment ID.
969 assert(Status == NoneOrPhi || ID);
970 }
971 };
972
973 using AssignmentMap = SmallVector<Assignment>;
976 using UntaggedStoreAssignmentMap =
977 DenseMap<const Instruction *,
979
980private:
981 /// The highest numbered VariableID for partially promoted variables plus 1,
982 /// the values for which start at 1.
983 unsigned TrackedVariablesVectorSize = 0;
984 /// Map a variable to the set of variables that it fully contains.
985 OverlapMap VarContains;
986 /// Map untagged stores to the variable fragments they assign to. Used by
987 /// processUntaggedInstruction.
988 UntaggedStoreAssignmentMap UntaggedStoreVars;
989
990 // Machinery to defer inserting dbg.values.
992 InsertMap InsertBeforeMap;
993 /// Clear the location definitions currently cached for insertion after /p
994 /// After.
995 void resetInsertionPoint(Instruction &After);
996 void emitDbgValue(LocKind Kind, const DbgVariableIntrinsic *Source,
997 Instruction *After);
998
999 static bool mapsAreEqual(const BitVector &Mask, const AssignmentMap &A,
1000 const AssignmentMap &B) {
1001 return llvm::all_of(Mask.set_bits(), [&](unsigned VarID) {
1002 return A[VarID].isSameSourceAssignment(B[VarID]);
1003 });
1004 }
1005
1006 /// Represents the stack and debug assignments in a block. Used to describe
1007 /// the live-in and live-out values for blocks, as well as the "current"
1008 /// value as we process each instruction in a block.
1009 struct BlockInfo {
1010 /// The set of variables (VariableID) being tracked in this block.
1011 BitVector VariableIDsInBlock;
1012 /// Dominating assignment to memory for each variable, indexed by
1013 /// VariableID.
1014 AssignmentMap StackHomeValue;
1015 /// Dominating assignemnt to each variable, indexed by VariableID.
1016 AssignmentMap DebugValue;
1017 /// Location kind for each variable. LiveLoc indicates whether the
1018 /// dominating assignment in StackHomeValue (LocKind::Mem), DebugValue
1019 /// (LocKind::Val), or neither (LocKind::None) is valid, in that order of
1020 /// preference. This cannot be derived by inspecting DebugValue and
1021 /// StackHomeValue due to the fact that there's no distinction in
1022 /// Assignment (the class) between whether an assignment is unknown or a
1023 /// merge of multiple assignments (both are Status::NoneOrPhi). In other
1024 /// words, the memory location may well be valid while both DebugValue and
1025 /// StackHomeValue contain Assignments that have a Status of NoneOrPhi.
1026 /// Indexed by VariableID.
1027 LocMap LiveLoc;
1028
1029 public:
1030 enum AssignmentKind { Stack, Debug };
1031 const AssignmentMap &getAssignmentMap(AssignmentKind Kind) const {
1032 switch (Kind) {
1033 case Stack:
1034 return StackHomeValue;
1035 case Debug:
1036 return DebugValue;
1037 }
1038 llvm_unreachable("Unknown AssignmentKind");
1039 }
1040 AssignmentMap &getAssignmentMap(AssignmentKind Kind) {
1041 return const_cast<AssignmentMap &>(
1042 const_cast<const BlockInfo *>(this)->getAssignmentMap(Kind));
1043 }
1044
1045 bool isVariableTracked(VariableID Var) const {
1046 return VariableIDsInBlock[static_cast<unsigned>(Var)];
1047 }
1048
1049 const Assignment &getAssignment(AssignmentKind Kind, VariableID Var) const {
1050 assert(isVariableTracked(Var) && "Var not tracked in block");
1051 return getAssignmentMap(Kind)[static_cast<unsigned>(Var)];
1052 }
1053
1054 LocKind getLocKind(VariableID Var) const {
1055 assert(isVariableTracked(Var) && "Var not tracked in block");
1056 return LiveLoc[static_cast<unsigned>(Var)];
1057 }
1058
1059 /// Set LocKind for \p Var only: does not set LocKind for VariableIDs of
1060 /// fragments contained win \p Var.
1061 void setLocKind(VariableID Var, LocKind K) {
1062 VariableIDsInBlock.set(static_cast<unsigned>(Var));
1063 LiveLoc[static_cast<unsigned>(Var)] = K;
1064 }
1065
1066 /// Set the assignment in the \p Kind assignment map for \p Var only: does
1067 /// not set the assignment for VariableIDs of fragments contained win \p
1068 /// Var.
1069 void setAssignment(AssignmentKind Kind, VariableID Var,
1070 const Assignment &AV) {
1071 VariableIDsInBlock.set(static_cast<unsigned>(Var));
1072 getAssignmentMap(Kind)[static_cast<unsigned>(Var)] = AV;
1073 }
1074
1075 /// Return true if there is an assignment matching \p AV in the \p Kind
1076 /// assignment map. Does consider assignments for VariableIDs of fragments
1077 /// contained win \p Var.
1078 bool hasAssignment(AssignmentKind Kind, VariableID Var,
1079 const Assignment &AV) const {
1080 if (!isVariableTracked(Var))
1081 return false;
1082 return AV.isSameSourceAssignment(getAssignment(Kind, Var));
1083 }
1084
1085 /// Compare every element in each map to determine structural equality
1086 /// (slow).
1087 bool operator==(const BlockInfo &Other) const {
1088 return VariableIDsInBlock == Other.VariableIDsInBlock &&
1089 LiveLoc == Other.LiveLoc &&
1090 mapsAreEqual(VariableIDsInBlock, StackHomeValue,
1091 Other.StackHomeValue) &&
1092 mapsAreEqual(VariableIDsInBlock, DebugValue, Other.DebugValue);
1093 }
1094 bool operator!=(const BlockInfo &Other) const { return !(*this == Other); }
1095 bool isValid() {
1096 return LiveLoc.size() == DebugValue.size() &&
1097 LiveLoc.size() == StackHomeValue.size();
1098 }
1099
1100 /// Clear everything and initialise with ⊤-values for all variables.
1101 void init(int NumVars) {
1102 StackHomeValue.clear();
1103 DebugValue.clear();
1104 LiveLoc.clear();
1105 VariableIDsInBlock = BitVector(NumVars);
1106 StackHomeValue.insert(StackHomeValue.begin(), NumVars,
1107 Assignment::makeNoneOrPhi());
1108 DebugValue.insert(DebugValue.begin(), NumVars,
1109 Assignment::makeNoneOrPhi());
1110 LiveLoc.insert(LiveLoc.begin(), NumVars, LocKind::None);
1111 }
1112
1113 /// Helper for join.
1114 template <typename ElmtType, typename FnInputType>
1115 static void joinElmt(int Index, SmallVector<ElmtType> &Target,
1116 const SmallVector<ElmtType> &A,
1117 const SmallVector<ElmtType> &B,
1118 ElmtType (*Fn)(FnInputType, FnInputType)) {
1119 Target[Index] = Fn(A[Index], B[Index]);
1120 }
1121
1122 /// See comment for AssignmentTrackingLowering::joinBlockInfo.
1123 static BlockInfo join(const BlockInfo &A, const BlockInfo &B, int NumVars) {
1124 // Join A and B.
1125 //
1126 // Intersect = join(a, b) for a in A, b in B where Var(a) == Var(b)
1127 // Difference = join(x, ⊤) for x where Var(x) is in A xor B
1128 // Join = Intersect ∪ Difference
1129 //
1130 // This is achieved by performing a join on elements from A and B with
1131 // variables common to both A and B (join elements indexed by var
1132 // intersect), then adding ⊤-value elements for vars in A xor B. The
1133 // latter part is equivalent to performing join on elements with variables
1134 // in A xor B with the ⊤-value for the map element since join(x, ⊤) = ⊤.
1135 // BlockInfo::init initializes all variable entries to the ⊤ value so we
1136 // don't need to explicitly perform that step as Join.VariableIDsInBlock
1137 // is set to the union of the variables in A and B at the end of this
1138 // function.
1139 BlockInfo Join;
1140 Join.init(NumVars);
1141
1142 BitVector Intersect = A.VariableIDsInBlock;
1143 Intersect &= B.VariableIDsInBlock;
1144
1145 for (auto VarID : Intersect.set_bits()) {
1146 joinElmt(VarID, Join.LiveLoc, A.LiveLoc, B.LiveLoc, joinKind);
1147 joinElmt(VarID, Join.DebugValue, A.DebugValue, B.DebugValue,
1148 joinAssignment);
1149 joinElmt(VarID, Join.StackHomeValue, A.StackHomeValue, B.StackHomeValue,
1150 joinAssignment);
1151 }
1152
1153 Join.VariableIDsInBlock = A.VariableIDsInBlock;
1154 Join.VariableIDsInBlock |= B.VariableIDsInBlock;
1155 assert(Join.isValid());
1156 return Join;
1157 }
1158 };
1159
1160 Function &Fn;
1161 const DataLayout &Layout;
1162 const DenseSet<DebugAggregate> *VarsWithStackSlot;
1163 FunctionVarLocsBuilder *FnVarLocs;
1166
1167 /// Helper for process methods to track variables touched each frame.
1168 DenseSet<VariableID> VarsTouchedThisFrame;
1169
1170 /// The set of variables that sometimes are not located in their stack home.
1171 DenseSet<DebugAggregate> NotAlwaysStackHomed;
1172
1173 VariableID getVariableID(const DebugVariable &Var) {
1174 return static_cast<VariableID>(FnVarLocs->insertVariable(Var));
1175 }
1176
1177 /// Join the LiveOut values of preds that are contained in \p Visited into
1178 /// LiveIn[BB]. Return True if LiveIn[BB] has changed as a result. LiveIn[BB]
1179 /// values monotonically increase. See the @link joinMethods join methods
1180 /// @endlink documentation for more info.
1181 bool join(const BasicBlock &BB, const SmallPtrSet<BasicBlock *, 16> &Visited);
1182 ///@name joinMethods
1183 /// Functions that implement `join` (the least upper bound) for the
1184 /// join-semilattice types used in the dataflow. There is an explicit bottom
1185 /// value (⊥) for some types and and explicit top value (⊤) for all types.
1186 /// By definition:
1187 ///
1188 /// Join(A, B) >= A && Join(A, B) >= B
1189 /// Join(A, ⊥) = A
1190 /// Join(A, ⊤) = ⊤
1191 ///
1192 /// These invariants are important for monotonicity.
1193 ///
1194 /// For the map-type functions, all unmapped keys in an empty map are
1195 /// associated with a bottom value (⊥). This represents their values being
1196 /// unknown. Unmapped keys in non-empty maps (joining two maps with a key
1197 /// only present in one) represents either a variable going out of scope or
1198 /// dropped debug info. It is assumed the key is associated with a top value
1199 /// (⊤) in this case (unknown location / assignment).
1200 ///@{
1201 static LocKind joinKind(LocKind A, LocKind B);
1202 static Assignment joinAssignment(const Assignment &A, const Assignment &B);
1203 BlockInfo joinBlockInfo(const BlockInfo &A, const BlockInfo &B);
1204 ///@}
1205
1206 /// Process the instructions in \p BB updating \p LiveSet along the way. \p
1207 /// LiveSet must be initialized with the current live-in locations before
1208 /// calling this.
1209 void process(BasicBlock &BB, BlockInfo *LiveSet);
1210 ///@name processMethods
1211 /// Methods to process instructions in order to update the LiveSet (current
1212 /// location information).
1213 ///@{
1214 void processNonDbgInstruction(Instruction &I, BlockInfo *LiveSet);
1215 void processDbgInstruction(Instruction &I, BlockInfo *LiveSet);
1216 /// Update \p LiveSet after encountering an instruction with a DIAssignID
1217 /// attachment, \p I.
1218 void processTaggedInstruction(Instruction &I, BlockInfo *LiveSet);
1219 /// Update \p LiveSet after encountering an instruciton without a DIAssignID
1220 /// attachment, \p I.
1221 void processUntaggedInstruction(Instruction &I, BlockInfo *LiveSet);
1222 void processDbgAssign(DbgAssignIntrinsic &DAI, BlockInfo *LiveSet);
1223 void processDbgValue(DbgValueInst &DVI, BlockInfo *LiveSet);
1224 /// Add an assignment to memory for the variable /p Var.
1225 void addMemDef(BlockInfo *LiveSet, VariableID Var, const Assignment &AV);
1226 /// Add an assignment to the variable /p Var.
1227 void addDbgDef(BlockInfo *LiveSet, VariableID Var, const Assignment &AV);
1228 ///@}
1229
1230 /// Set the LocKind for \p Var.
1231 void setLocKind(BlockInfo *LiveSet, VariableID Var, LocKind K);
1232 /// Get the live LocKind for a \p Var. Requires addMemDef or addDbgDef to
1233 /// have been called for \p Var first.
1234 LocKind getLocKind(BlockInfo *LiveSet, VariableID Var);
1235 /// Return true if \p Var has an assignment in \p M matching \p AV.
1236 bool hasVarWithAssignment(BlockInfo *LiveSet, BlockInfo::AssignmentKind Kind,
1237 VariableID Var, const Assignment &AV);
1238 /// Return the set of VariableIDs corresponding the fragments contained fully
1239 /// within the variable/fragment \p Var.
1240 ArrayRef<VariableID> getContainedFragments(VariableID Var) const;
1241
1242 /// Mark \p Var as having been touched this frame. Note, this applies only
1243 /// to the exact fragment \p Var and not to any fragments contained within.
1244 void touchFragment(VariableID Var);
1245
1246 /// Emit info for variables that are fully promoted.
1247 bool emitPromotedVarLocs(FunctionVarLocsBuilder *FnVarLocs);
1248
1249public:
1250 AssignmentTrackingLowering(Function &Fn, const DataLayout &Layout,
1251 const DenseSet<DebugAggregate> *VarsWithStackSlot)
1252 : Fn(Fn), Layout(Layout), VarsWithStackSlot(VarsWithStackSlot) {}
1253 /// Run the analysis, adding variable location info to \p FnVarLocs. Returns
1254 /// true if any variable locations have been added to FnVarLocs.
1255 bool run(FunctionVarLocsBuilder *FnVarLocs);
1256};
1257} // namespace
1258
1260AssignmentTrackingLowering::getContainedFragments(VariableID Var) const {
1261 auto R = VarContains.find(Var);
1262 if (R == VarContains.end())
1263 return std::nullopt;
1264 return R->second;
1265}
1266
1267void AssignmentTrackingLowering::touchFragment(VariableID Var) {
1268 VarsTouchedThisFrame.insert(Var);
1269}
1270
1271void AssignmentTrackingLowering::setLocKind(BlockInfo *LiveSet, VariableID Var,
1272 LocKind K) {
1273 auto SetKind = [this](BlockInfo *LiveSet, VariableID Var, LocKind K) {
1274 LiveSet->setLocKind(Var, K);
1275 touchFragment(Var);
1276 };
1277 SetKind(LiveSet, Var, K);
1278
1279 // Update the LocKind for all fragments contained within Var.
1280 for (VariableID Frag : getContainedFragments(Var))
1281 SetKind(LiveSet, Frag, K);
1282}
1283
1284AssignmentTrackingLowering::LocKind
1285AssignmentTrackingLowering::getLocKind(BlockInfo *LiveSet, VariableID Var) {
1286 return LiveSet->getLocKind(Var);
1287}
1288
1289void AssignmentTrackingLowering::addMemDef(BlockInfo *LiveSet, VariableID Var,
1290 const Assignment &AV) {
1291 LiveSet->setAssignment(BlockInfo::Stack, Var, AV);
1292
1293 // Use this assigment for all fragments contained within Var, but do not
1294 // provide a Source because we cannot convert Var's value to a value for the
1295 // fragment.
1296 Assignment FragAV = AV;
1297 FragAV.Source = nullptr;
1298 for (VariableID Frag : getContainedFragments(Var))
1299 LiveSet->setAssignment(BlockInfo::Stack, Frag, FragAV);
1300}
1301
1302void AssignmentTrackingLowering::addDbgDef(BlockInfo *LiveSet, VariableID Var,
1303 const Assignment &AV) {
1304 LiveSet->setAssignment(BlockInfo::Debug, Var, AV);
1305
1306 // Use this assigment for all fragments contained within Var, but do not
1307 // provide a Source because we cannot convert Var's value to a value for the
1308 // fragment.
1309 Assignment FragAV = AV;
1310 FragAV.Source = nullptr;
1311 for (VariableID Frag : getContainedFragments(Var))
1312 LiveSet->setAssignment(BlockInfo::Debug, Frag, FragAV);
1313}
1314
1316 return cast<DIAssignID>(I.getMetadata(LLVMContext::MD_DIAssignID));
1317}
1318
1320 return cast<DIAssignID>(DAI.getAssignID());
1321}
1322
1323/// Return true if \p Var has an assignment in \p M matching \p AV.
1324bool AssignmentTrackingLowering::hasVarWithAssignment(
1325 BlockInfo *LiveSet, BlockInfo::AssignmentKind Kind, VariableID Var,
1326 const Assignment &AV) {
1327 if (!LiveSet->hasAssignment(Kind, Var, AV))
1328 return false;
1329
1330 // Check all the frags contained within Var as these will have all been
1331 // mapped to AV at the last store to Var.
1332 for (VariableID Frag : getContainedFragments(Var))
1333 if (!LiveSet->hasAssignment(Kind, Frag, AV))
1334 return false;
1335 return true;
1336}
1337
1338#ifndef NDEBUG
1339const char *locStr(AssignmentTrackingLowering::LocKind Loc) {
1340 using LocKind = AssignmentTrackingLowering::LocKind;
1341 switch (Loc) {
1342 case LocKind::Val:
1343 return "Val";
1344 case LocKind::Mem:
1345 return "Mem";
1346 case LocKind::None:
1347 return "None";
1348 };
1349 llvm_unreachable("unknown LocKind");
1350}
1351#endif
1352
1353void AssignmentTrackingLowering::emitDbgValue(
1354 AssignmentTrackingLowering::LocKind Kind,
1355 const DbgVariableIntrinsic *Source, Instruction *After) {
1356
1357 DILocation *DL = Source->getDebugLoc();
1358 auto Emit = [this, Source, After, DL](Metadata *Val, DIExpression *Expr) {
1359 assert(Expr);
1360 if (!Val)
1362 PoisonValue::get(Type::getInt1Ty(Source->getContext())));
1363
1364 // Find a suitable insert point.
1365 Instruction *InsertBefore = After->getNextNode();
1366 assert(InsertBefore && "Shouldn't be inserting after a terminator");
1367
1368 VariableID Var = getVariableID(DebugVariable(Source));
1369 VarLocInfo VarLoc;
1370 VarLoc.VariableID = static_cast<VariableID>(Var);
1371 VarLoc.Expr = Expr;
1372 VarLoc.Values = RawLocationWrapper(Val);
1373 VarLoc.DL = DL;
1374 // Insert it into the map for later.
1375 InsertBeforeMap[InsertBefore].push_back(VarLoc);
1376 };
1377
1378 // NOTE: This block can mutate Kind.
1379 if (Kind == LocKind::Mem) {
1380 const auto *DAI = cast<DbgAssignIntrinsic>(Source);
1381 // Check the address hasn't been dropped (e.g. the debug uses may not have
1382 // been replaced before deleting a Value).
1383 if (DAI->isKillAddress()) {
1384 // The address isn't valid so treat this as a non-memory def.
1385 Kind = LocKind::Val;
1386 } else {
1387 Value *Val = DAI->getAddress();
1388 DIExpression *Expr = DAI->getAddressExpression();
1389 assert(!Expr->getFragmentInfo() &&
1390 "fragment info should be stored in value-expression only");
1391 // Copy the fragment info over from the value-expression to the new
1392 // DIExpression.
1393 if (auto OptFragInfo = Source->getExpression()->getFragmentInfo()) {
1394 auto FragInfo = *OptFragInfo;
1396 Expr, FragInfo.OffsetInBits, FragInfo.SizeInBits);
1397 }
1398 // The address-expression has an implicit deref, add it now.
1399 std::tie(Val, Expr) =
1400 walkToAllocaAndPrependOffsetDeref(Layout, Val, Expr);
1401 Emit(ValueAsMetadata::get(Val), Expr);
1402 return;
1403 }
1404 }
1405
1406 if (Kind == LocKind::Val) {
1407 Emit(Source->getRawLocation(), Source->getExpression());
1408 return;
1409 }
1410
1411 if (Kind == LocKind::None) {
1412 Emit(nullptr, Source->getExpression());
1413 return;
1414 }
1415}
1416
1417void AssignmentTrackingLowering::processNonDbgInstruction(
1418 Instruction &I, AssignmentTrackingLowering::BlockInfo *LiveSet) {
1419 if (I.hasMetadata(LLVMContext::MD_DIAssignID))
1420 processTaggedInstruction(I, LiveSet);
1421 else
1422 processUntaggedInstruction(I, LiveSet);
1423}
1424
1425void AssignmentTrackingLowering::processUntaggedInstruction(
1426 Instruction &I, AssignmentTrackingLowering::BlockInfo *LiveSet) {
1427 // Interpret stack stores that are not tagged as an assignment in memory for
1428 // the variables associated with that address. These stores may not be tagged
1429 // because a) the store cannot be represented using dbg.assigns (non-const
1430 // length or offset) or b) the tag was accidentally dropped during
1431 // optimisations. For these stores we fall back to assuming that the stack
1432 // home is a valid location for the variables. The benefit is that this
1433 // prevents us missing an assignment and therefore incorrectly maintaining
1434 // earlier location definitions, and in many cases it should be a reasonable
1435 // assumption. However, this will occasionally lead to slight
1436 // inaccuracies. The value of a hoisted untagged store will be visible
1437 // "early", for example.
1438 assert(!I.hasMetadata(LLVMContext::MD_DIAssignID));
1439 auto It = UntaggedStoreVars.find(&I);
1440 if (It == UntaggedStoreVars.end())
1441 return; // No variables associated with the store destination.
1442
1443 LLVM_DEBUG(dbgs() << "processUntaggedInstruction on UNTAGGED INST " << I
1444 << "\n");
1445 // Iterate over the variables that this store affects, add a NoneOrPhi dbg
1446 // and mem def, set lockind to Mem, and emit a location def for each.
1447 for (auto [Var, Info] : It->second) {
1448 // This instruction is treated as both a debug and memory assignment,
1449 // meaning the memory location should be used. We don't have an assignment
1450 // ID though so use Assignment::makeNoneOrPhi() to create an imaginary one.
1451 addMemDef(LiveSet, Var, Assignment::makeNoneOrPhi());
1452 addDbgDef(LiveSet, Var, Assignment::makeNoneOrPhi());
1453 setLocKind(LiveSet, Var, LocKind::Mem);
1454 LLVM_DEBUG(dbgs() << " setting Stack LocKind to: " << locStr(LocKind::Mem)
1455 << "\n");
1456 // Build the dbg location def to insert.
1457 //
1458 // DIExpression: Add fragment and offset.
1459 DebugVariable V = FnVarLocs->getVariable(Var);
1460 DIExpression *DIE = DIExpression::get(I.getContext(), std::nullopt);
1461 if (auto Frag = V.getFragment()) {
1462 auto R = DIExpression::createFragmentExpression(DIE, Frag->OffsetInBits,
1463 Frag->SizeInBits);
1464 assert(R && "unexpected createFragmentExpression failure");
1465 DIE = *R;
1466 }
1468 if (Info.OffsetInBits)
1469 Ops = {dwarf::DW_OP_plus_uconst, Info.OffsetInBits / 8};
1470 Ops.push_back(dwarf::DW_OP_deref);
1471 DIE = DIExpression::prependOpcodes(DIE, Ops, /*StackValue=*/false,
1472 /*EntryValue=*/false);
1473 // Find a suitable insert point.
1474 Instruction *InsertBefore = I.getNextNode();
1475 assert(InsertBefore && "Shouldn't be inserting after a terminator");
1476
1477 // Get DILocation for this unrecorded assignment.
1478 DILocation *InlinedAt = const_cast<DILocation *>(V.getInlinedAt());
1479 const DILocation *DILoc = DILocation::get(
1480 Fn.getContext(), 0, 0, V.getVariable()->getScope(), InlinedAt);
1481
1482 VarLocInfo VarLoc;
1483 VarLoc.VariableID = static_cast<VariableID>(Var);
1484 VarLoc.Expr = DIE;
1485 VarLoc.Values = RawLocationWrapper(
1486 ValueAsMetadata::get(const_cast<AllocaInst *>(Info.Base)));
1487 VarLoc.DL = DILoc;
1488 // 3. Insert it into the map for later.
1489 InsertBeforeMap[InsertBefore].push_back(VarLoc);
1490 }
1491}
1492
1493void AssignmentTrackingLowering::processTaggedInstruction(
1494 Instruction &I, AssignmentTrackingLowering::BlockInfo *LiveSet) {
1495 auto Linked = at::getAssignmentMarkers(&I);
1496 // No dbg.assign intrinsics linked.
1497 // FIXME: All vars that have a stack slot this store modifies that don't have
1498 // a dbg.assign linked to it should probably treat this like an untagged
1499 // store.
1500 if (Linked.empty())
1501 return;
1502
1503 LLVM_DEBUG(dbgs() << "processTaggedInstruction on " << I << "\n");
1504 for (DbgAssignIntrinsic *DAI : Linked) {
1505 VariableID Var = getVariableID(DebugVariable(DAI));
1506 // Something has gone wrong if VarsWithStackSlot doesn't contain a variable
1507 // that is linked to a store.
1508 assert(VarsWithStackSlot->count(getAggregate(DAI)) &&
1509 "expected DAI's variable to have stack slot");
1510
1511 Assignment AV = Assignment::makeFromMemDef(getIDFromInst(I));
1512 addMemDef(LiveSet, Var, AV);
1513
1514 LLVM_DEBUG(dbgs() << " linked to " << *DAI << "\n");
1515 LLVM_DEBUG(dbgs() << " LiveLoc " << locStr(getLocKind(LiveSet, Var))
1516 << " -> ");
1517
1518 // The last assignment to the stack is now AV. Check if the last debug
1519 // assignment has a matching Assignment.
1520 if (hasVarWithAssignment(LiveSet, BlockInfo::Debug, Var, AV)) {
1521 // The StackHomeValue and DebugValue for this variable match so we can
1522 // emit a stack home location here.
1523 LLVM_DEBUG(dbgs() << "Mem, Stack matches Debug program\n";);
1524 LLVM_DEBUG(dbgs() << " Stack val: "; AV.dump(dbgs()); dbgs() << "\n");
1525 LLVM_DEBUG(dbgs() << " Debug val: ";
1526 LiveSet->DebugValue[static_cast<unsigned>(Var)].dump(dbgs());
1527 dbgs() << "\n");
1528 setLocKind(LiveSet, Var, LocKind::Mem);
1529 emitDbgValue(LocKind::Mem, DAI, &I);
1530 continue;
1531 }
1532
1533 // The StackHomeValue and DebugValue for this variable do not match. I.e.
1534 // The value currently stored in the stack is not what we'd expect to
1535 // see, so we cannot use emit a stack home location here. Now we will
1536 // look at the live LocKind for the variable and determine an appropriate
1537 // dbg.value to emit.
1538 LocKind PrevLoc = getLocKind(LiveSet, Var);
1539 switch (PrevLoc) {
1540 case LocKind::Val: {
1541 // The value in memory in memory has changed but we're not currently
1542 // using the memory location. Do nothing.
1543 LLVM_DEBUG(dbgs() << "Val, (unchanged)\n";);
1544 setLocKind(LiveSet, Var, LocKind::Val);
1545 } break;
1546 case LocKind::Mem: {
1547 // There's been an assignment to memory that we were using as a
1548 // location for this variable, and the Assignment doesn't match what
1549 // we'd expect to see in memory.
1550 Assignment DbgAV = LiveSet->getAssignment(BlockInfo::Debug, Var);
1551 if (DbgAV.Status == Assignment::NoneOrPhi) {
1552 // We need to terminate any previously open location now.
1553 LLVM_DEBUG(dbgs() << "None, No Debug value available\n";);
1554 setLocKind(LiveSet, Var, LocKind::None);
1555 emitDbgValue(LocKind::None, DAI, &I);
1556 } else {
1557 // The previous DebugValue Value can be used here.
1558 LLVM_DEBUG(dbgs() << "Val, Debug value is Known\n";);
1559 setLocKind(LiveSet, Var, LocKind::Val);
1560 if (DbgAV.Source) {
1561 emitDbgValue(LocKind::Val, DbgAV.Source, &I);
1562 } else {
1563 // PrevAV.Source is nullptr so we must emit undef here.
1564 emitDbgValue(LocKind::None, DAI, &I);
1565 }
1566 }
1567 } break;
1568 case LocKind::None: {
1569 // There's been an assignment to memory and we currently are
1570 // not tracking a location for the variable. Do not emit anything.
1571 LLVM_DEBUG(dbgs() << "None, (unchanged)\n";);
1572 setLocKind(LiveSet, Var, LocKind::None);
1573 } break;
1574 }
1575 }
1576}
1577
1578void AssignmentTrackingLowering::processDbgAssign(DbgAssignIntrinsic &DAI,
1579 BlockInfo *LiveSet) {
1580 // Only bother tracking variables that are at some point stack homed. Other
1581 // variables can be dealt with trivially later.
1582 if (!VarsWithStackSlot->count(getAggregate(&DAI)))
1583 return;
1584
1585 VariableID Var = getVariableID(DebugVariable(&DAI));
1586 Assignment AV = Assignment::make(getIDFromMarker(DAI), &DAI);
1587 addDbgDef(LiveSet, Var, AV);
1588
1589 LLVM_DEBUG(dbgs() << "processDbgAssign on " << DAI << "\n";);
1590 LLVM_DEBUG(dbgs() << " LiveLoc " << locStr(getLocKind(LiveSet, Var))
1591 << " -> ");
1592
1593 // Check if the DebugValue and StackHomeValue both hold the same
1594 // Assignment.
1595 if (hasVarWithAssignment(LiveSet, BlockInfo::Stack, Var, AV)) {
1596 // They match. We can use the stack home because the debug intrinsics state
1597 // that an assignment happened here, and we know that specific assignment
1598 // was the last one to take place in memory for this variable.
1599 LocKind Kind;
1600 if (DAI.isKillAddress()) {
1601 LLVM_DEBUG(
1602 dbgs()
1603 << "Val, Stack matches Debug program but address is killed\n";);
1604 Kind = LocKind::Val;
1605 } else {
1606 LLVM_DEBUG(dbgs() << "Mem, Stack matches Debug program\n";);
1607 Kind = LocKind::Mem;
1608 };
1609 setLocKind(LiveSet, Var, Kind);
1610 emitDbgValue(Kind, &DAI, &DAI);
1611 } else {
1612 // The last assignment to the memory location isn't the one that we want to
1613 // show to the user so emit a dbg.value(Value). Value may be undef.
1614 LLVM_DEBUG(dbgs() << "Val, Stack contents is unknown\n";);
1615 setLocKind(LiveSet, Var, LocKind::Val);
1616 emitDbgValue(LocKind::Val, &DAI, &DAI);
1617 }
1618}
1619
1620void AssignmentTrackingLowering::processDbgValue(DbgValueInst &DVI,
1621 BlockInfo *LiveSet) {
1622 // Only other tracking variables that are at some point stack homed.
1623 // Other variables can be dealt with trivally later.
1624 if (!VarsWithStackSlot->count(getAggregate(&DVI)))
1625 return;
1626
1627 VariableID Var = getVariableID(DebugVariable(&DVI));
1628 // We have no ID to create an Assignment with so we mark this assignment as
1629 // NoneOrPhi. Note that the dbg.value still exists, we just cannot determine
1630 // the assignment responsible for setting this value.
1631 // This is fine; dbg.values are essentially interchangable with unlinked
1632 // dbg.assigns, and some passes such as mem2reg and instcombine add them to
1633 // PHIs for promoted variables.
1634 Assignment AV = Assignment::makeNoneOrPhi();
1635 addDbgDef(LiveSet, Var, AV);
1636
1637 LLVM_DEBUG(dbgs() << "processDbgValue on " << DVI << "\n";);
1638 LLVM_DEBUG(dbgs() << " LiveLoc " << locStr(getLocKind(LiveSet, Var))
1639 << " -> Val, dbg.value override");
1640
1641 setLocKind(LiveSet, Var, LocKind::Val);
1642 emitDbgValue(LocKind::Val, &DVI, &DVI);
1643}
1644
1645void AssignmentTrackingLowering::processDbgInstruction(
1646 Instruction &I, AssignmentTrackingLowering::BlockInfo *LiveSet) {
1647 if (auto *DAI = dyn_cast<DbgAssignIntrinsic>(&I))
1648 processDbgAssign(*DAI, LiveSet);
1649 else if (auto *DVI = dyn_cast<DbgValueInst>(&I))
1650 processDbgValue(*DVI, LiveSet);
1651}
1652
1653void AssignmentTrackingLowering::resetInsertionPoint(Instruction &After) {
1654 assert(!After.isTerminator() && "Can't insert after a terminator");
1655 auto R = InsertBeforeMap.find(After.getNextNode());
1656 if (R == InsertBeforeMap.end())
1657 return;
1658 R->second.clear();
1659}
1660
1661void AssignmentTrackingLowering::process(BasicBlock &BB, BlockInfo *LiveSet) {
1662 for (auto II = BB.begin(), EI = BB.end(); II != EI;) {
1663 assert(VarsTouchedThisFrame.empty());
1664 // Process the instructions in "frames". A "frame" includes a single
1665 // non-debug instruction followed any debug instructions before the
1666 // next non-debug instruction.
1667 if (!isa<DbgInfoIntrinsic>(&*II)) {
1668 if (II->isTerminator())
1669 break;
1670 resetInsertionPoint(*II);
1671 processNonDbgInstruction(*II, LiveSet);
1672 assert(LiveSet->isValid());
1673 ++II;
1674 }
1675 while (II != EI) {
1676 if (!isa<DbgInfoIntrinsic>(&*II))
1677 break;
1678 resetInsertionPoint(*II);
1679 processDbgInstruction(*II, LiveSet);
1680 assert(LiveSet->isValid());
1681 ++II;
1682 }
1683
1684 // We've processed everything in the "frame". Now determine which variables
1685 // cannot be represented by a dbg.declare.
1686 for (auto Var : VarsTouchedThisFrame) {
1687 LocKind Loc = getLocKind(LiveSet, Var);
1688 // If a variable's LocKind is anything other than LocKind::Mem then we
1689 // must note that it cannot be represented with a dbg.declare.
1690 // Note that this check is enough without having to check the result of
1691 // joins() because for join to produce anything other than Mem after
1692 // we've already seen a Mem we'd be joining None or Val with Mem. In that
1693 // case, we've already hit this codepath when we set the LocKind to Val
1694 // or None in that block.
1695 if (Loc != LocKind::Mem) {
1696 DebugVariable DbgVar = FnVarLocs->getVariable(Var);
1697 DebugAggregate Aggr{DbgVar.getVariable(), DbgVar.getInlinedAt()};
1698 NotAlwaysStackHomed.insert(Aggr);
1699 }
1700 }
1701 VarsTouchedThisFrame.clear();
1702 }
1703}
1704
1705AssignmentTrackingLowering::LocKind
1706AssignmentTrackingLowering::joinKind(LocKind A, LocKind B) {
1707 // Partial order:
1708 // None > Mem, Val
1709 return A == B ? A : LocKind::None;
1710}
1711
1712AssignmentTrackingLowering::Assignment
1713AssignmentTrackingLowering::joinAssignment(const Assignment &A,
1714 const Assignment &B) {
1715 // Partial order:
1716 // NoneOrPhi(null, null) > Known(v, ?s)
1717
1718 // If either are NoneOrPhi the join is NoneOrPhi.
1719 // If either value is different then the result is
1720 // NoneOrPhi (joining two values is a Phi).
1721 if (!A.isSameSourceAssignment(B))
1722 return Assignment::makeNoneOrPhi();
1723 if (A.Status == Assignment::NoneOrPhi)
1724 return Assignment::makeNoneOrPhi();
1725
1726 // Source is used to lookup the value + expression in the debug program if
1727 // the stack slot gets assigned a value earlier than expected. Because
1728 // we're only tracking the one dbg.assign, we can't capture debug PHIs.
1729 // It's unlikely that we're losing out on much coverage by avoiding that
1730 // extra work.
1731 // The Source may differ in this situation:
1732 // Pred.1:
1733 // dbg.assign i32 0, ..., !1, ...
1734 // Pred.2:
1735 // dbg.assign i32 1, ..., !1, ...
1736 // Here the same assignment (!1) was performed in both preds in the source,
1737 // but we can't use either one unless they are identical (e.g. .we don't
1738 // want to arbitrarily pick between constant values).
1739 auto JoinSource = [&]() -> DbgAssignIntrinsic * {
1740 if (A.Source == B.Source)
1741 return A.Source;
1742 if (A.Source == nullptr || B.Source == nullptr)
1743 return nullptr;
1744 if (A.Source->isIdenticalTo(B.Source))
1745 return A.Source;
1746 return nullptr;
1747 };
1748 DbgAssignIntrinsic *Source = JoinSource();
1749 assert(A.Status == B.Status && A.Status == Assignment::Known);
1750 assert(A.ID == B.ID);
1751 return Assignment::make(A.ID, Source);
1752}
1753
1754AssignmentTrackingLowering::BlockInfo
1755AssignmentTrackingLowering::joinBlockInfo(const BlockInfo &A,
1756 const BlockInfo &B) {
1757 return BlockInfo::join(A, B, TrackedVariablesVectorSize);
1758}
1759
1760bool AssignmentTrackingLowering::join(
1761 const BasicBlock &BB, const SmallPtrSet<BasicBlock *, 16> &Visited) {
1762 BlockInfo BBLiveIn;
1763 bool FirstJoin = true;
1764 // LiveIn locs for BB is the join of the already-processed preds' LiveOut
1765 // locs.
1766 for (auto I = pred_begin(&BB), E = pred_end(&BB); I != E; I++) {
1767 // Ignore backedges if we have not visited the predecessor yet. As the
1768 // predecessor hasn't yet had locations propagated into it, most locations
1769 // will not yet be valid, so treat them as all being uninitialized and
1770 // potentially valid. If a location guessed to be correct here is
1771 // invalidated later, we will remove it when we revisit this block. This
1772 // is essentially the same as initialising all LocKinds and Assignments to
1773 // an implicit ⊥ value which is the identity value for the join operation.
1774 const BasicBlock *Pred = *I;
1775 if (!Visited.count(Pred))
1776 continue;
1777
1778 auto PredLiveOut = LiveOut.find(Pred);
1779 // Pred must have been processed already. See comment at start of this loop.
1780 assert(PredLiveOut != LiveOut.end());
1781
1782 // Perform the join of BBLiveIn (current live-in info) and PrevLiveOut.
1783 if (FirstJoin)
1784 BBLiveIn = PredLiveOut->second;
1785 else
1786 BBLiveIn = joinBlockInfo(std::move(BBLiveIn), PredLiveOut->second);
1787 FirstJoin = false;
1788 }
1789
1790 if (FirstJoin)
1791 BBLiveIn.init(TrackedVariablesVectorSize);
1792
1793 auto CurrentLiveInEntry = LiveIn.find(&BB);
1794 // Check if there isn't an entry, or there is but the LiveIn set has changed
1795 // (expensive check).
1796 if (CurrentLiveInEntry == LiveIn.end() ||
1797 BBLiveIn != CurrentLiveInEntry->second) {
1798 LiveIn[&BB] = std::move(BBLiveIn);
1799 // A change has occured.
1800 return true;
1801 }
1802 // No change.
1803 return false;
1804}
1805
1806/// Return true if A fully contains B.
1809 auto ALeft = A.OffsetInBits;
1810 auto BLeft = B.OffsetInBits;
1811 if (BLeft < ALeft)
1812 return false;
1813
1814 auto ARight = ALeft + A.SizeInBits;
1815 auto BRight = BLeft + B.SizeInBits;
1816 if (BRight > ARight)
1817 return false;
1818 return true;
1819}
1820
1821static std::optional<at::AssignmentInfo>
1823 // Don't bother checking if this is an AllocaInst. We know this
1824 // instruction has no tag which means there are no variables associated
1825 // with it.
1826 if (const auto *SI = dyn_cast<StoreInst>(&I))
1827 return at::getAssignmentInfo(Layout, SI);
1828 if (const auto *MI = dyn_cast<MemIntrinsic>(&I))
1829 return at::getAssignmentInfo(Layout, MI);
1830 // Alloca or non-store-like inst.
1831 return std::nullopt;
1832}
1833
1834/// Build a map of {Variable x: Variables y} where all variable fragments
1835/// contained within the variable fragment x are in set y. This means that
1836/// y does not contain all overlaps because partial overlaps are excluded.
1837///
1838/// While we're iterating over the function, add single location defs for
1839/// dbg.declares to \p FnVarLocs.
1840///
1841/// Variables that are interesting to this pass in are added to
1842/// FnVarLocs->Variables first. TrackedVariablesVectorSize is set to the ID of
1843/// the last interesting variable plus 1, meaning variables with ID 1
1844/// (inclusive) to TrackedVariablesVectorSize (exclusive) are interesting. The
1845/// subsequent variables are either stack homed or fully promoted.
1846///
1847/// Finally, populate UntaggedStoreVars with a mapping of untagged stores to
1848/// the stored-to variable fragments.
1849///
1850/// These tasks are bundled together to reduce the number of times we need
1851/// to iterate over the function as they can be achieved together in one pass.
1853 Function &Fn, FunctionVarLocsBuilder *FnVarLocs,
1855 unsigned &TrackedVariablesVectorSize) {
1857 // Map of Variable: [Fragments].
1859 // Iterate over all instructions:
1860 // - dbg.declare -> add single location variable record
1861 // - dbg.* -> Add fragments to FragmentMap
1862 // - untagged store -> Add fragments to FragmentMap and update
1863 // UntaggedStoreVars.
1864 // We need to add fragments for untagged stores too so that we can correctly
1865 // clobber overlapped fragment locations later.
1867 for (auto &BB : Fn) {
1868 for (auto &I : BB) {
1869 if (auto *DDI = dyn_cast<DbgDeclareInst>(&I)) {
1870 Declares.push_back(DDI);
1871 } else if (auto *DII = dyn_cast<DbgVariableIntrinsic>(&I)) {
1872 DebugVariable DV = DebugVariable(DII);
1873 DebugAggregate DA = {DV.getVariable(), DV.getInlinedAt()};
1874 if (Seen.insert(DV).second)
1875 FragmentMap[DA].push_back(DV);
1876 } else if (auto Info = getUntaggedStoreAssignmentInfo(
1877 I, Fn.getParent()->getDataLayout())) {
1878 // Find markers linked to this alloca.
1880 // Discard the fragment if it covers the entire variable.
1881 std::optional<DIExpression::FragmentInfo> FragInfo =
1882 [&Info, DAI]() -> std::optional<DIExpression::FragmentInfo> {
1884 F.OffsetInBits = Info->OffsetInBits;
1885 F.SizeInBits = Info->SizeInBits;
1886 if (auto ExistingFrag = DAI->getExpression()->getFragmentInfo())
1887 F.OffsetInBits += ExistingFrag->OffsetInBits;
1888 if (auto Sz = DAI->getVariable()->getSizeInBits()) {
1889 if (F.OffsetInBits == 0 && F.SizeInBits == *Sz)
1890 return std::nullopt;
1891 }
1892 return F;
1893 }();
1894
1895 DebugVariable DV = DebugVariable(DAI->getVariable(), FragInfo,
1896 DAI->getDebugLoc().getInlinedAt());
1897 DebugAggregate DA = {DV.getVariable(), DV.getInlinedAt()};
1898
1899 // Cache this info for later.
1900 UntaggedStoreVars[&I].push_back(
1901 {FnVarLocs->insertVariable(DV), *Info});
1902
1903 if (Seen.insert(DV).second)
1904 FragmentMap[DA].push_back(DV);
1905 }
1906 }
1907 }
1908 }
1909
1910 // Sort the fragment map for each DebugAggregate in non-descending
1911 // order of fragment size. Assert no entries are duplicates.
1912 for (auto &Pair : FragmentMap) {
1913 SmallVector<DebugVariable, 8> &Frags = Pair.second;
1914 std::sort(
1915 Frags.begin(), Frags.end(), [](DebugVariable Next, DebugVariable Elmt) {
1916 assert(!(Elmt.getFragmentOrDefault() == Next.getFragmentOrDefault()));
1917 return Elmt.getFragmentOrDefault().SizeInBits >
1918 Next.getFragmentOrDefault().SizeInBits;
1919 });
1920 }
1921
1922 // Build the map.
1924 for (auto Pair : FragmentMap) {
1925 auto &Frags = Pair.second;
1926 for (auto It = Frags.begin(), IEnd = Frags.end(); It != IEnd; ++It) {
1927 DIExpression::FragmentInfo Frag = It->getFragmentOrDefault();
1928 // Find the frags that this is contained within.
1929 //
1930 // Because Frags is sorted by size and none have the same offset and
1931 // size, we know that this frag can only be contained by subsequent
1932 // elements.
1934 ++OtherIt;
1935 VariableID ThisVar = FnVarLocs->insertVariable(*It);
1936 for (; OtherIt != IEnd; ++OtherIt) {
1937 DIExpression::FragmentInfo OtherFrag = OtherIt->getFragmentOrDefault();
1938 VariableID OtherVar = FnVarLocs->insertVariable(*OtherIt);
1939 if (fullyContains(OtherFrag, Frag))
1940 Map[OtherVar].push_back(ThisVar);
1941 }
1942 }
1943 }
1944
1945 // VariableIDs are 1-based so the variable-tracking bitvector needs
1946 // NumVariables plus 1 bits.
1947 TrackedVariablesVectorSize = FnVarLocs->getNumVariables() + 1;
1948
1949 // Finally, insert the declares afterwards, so the first IDs are all
1950 // partially stack homed vars.
1951 for (auto *DDI : Declares)
1952 FnVarLocs->addSingleLocVar(DebugVariable(DDI), DDI->getExpression(),
1953 DDI->getDebugLoc(), DDI->getWrappedLocation());
1954 return Map;
1955}
1956
1957bool AssignmentTrackingLowering::run(FunctionVarLocsBuilder *FnVarLocsBuilder) {
1958 if (Fn.size() > MaxNumBlocks) {
1959 LLVM_DEBUG(dbgs() << "[AT] Dropping var locs in: " << Fn.getName()
1960 << ": too many blocks (" << Fn.size() << ")\n");
1961 at::deleteAll(&Fn);
1962 return false;
1963 }
1964
1965 FnVarLocs = FnVarLocsBuilder;
1966
1967 // The general structure here is inspired by VarLocBasedImpl.cpp
1968 // (LiveDebugValues).
1969
1970 // Build the variable fragment overlap map.
1971 // Note that this pass doesn't handle partial overlaps correctly (FWIW
1972 // neither does LiveDebugVariables) because that is difficult to do and
1973 // appears to be rare occurance.
1975 Fn, FnVarLocs, UntaggedStoreVars, TrackedVariablesVectorSize);
1976
1977 // Prepare for traversal.
1979 std::priority_queue<unsigned int, std::vector<unsigned int>,
1980 std::greater<unsigned int>>
1981 Worklist;
1982 std::priority_queue<unsigned int, std::vector<unsigned int>,
1983 std::greater<unsigned int>>
1984 Pending;
1987 { // Init OrderToBB and BBToOrder.
1988 unsigned int RPONumber = 0;
1989 for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
1990 OrderToBB[RPONumber] = *RI;
1991 BBToOrder[*RI] = RPONumber;
1992 Worklist.push(RPONumber);
1993 ++RPONumber;
1994 }
1995 LiveIn.init(RPONumber);
1996 LiveOut.init(RPONumber);
1997 }
1998
1999 // Perform the traversal.
2000 //
2001 // This is a standard "union of predecessor outs" dataflow problem. To solve
2002 // it, we perform join() and process() using the two worklist method until
2003 // the LiveIn data for each block becomes unchanging. The "proof" that this
2004 // terminates can be put together by looking at the comments around LocKind,
2005 // Assignment, and the various join methods, which show that all the elements
2006 // involved are made up of join-semilattices; LiveIn(n) can only
2007 // monotonically increase in value throughout the dataflow.
2008 //
2010 while (!Worklist.empty()) {
2011 // We track what is on the pending worklist to avoid inserting the same
2012 // thing twice.
2014 LLVM_DEBUG(dbgs() << "Processing Worklist\n");
2015 while (!Worklist.empty()) {
2016 BasicBlock *BB = OrderToBB[Worklist.top()];
2017 LLVM_DEBUG(dbgs() << "\nPop BB " << BB->getName() << "\n");
2018 Worklist.pop();
2019 bool InChanged = join(*BB, Visited);
2020 // Always consider LiveIn changed on the first visit.
2021 InChanged |= Visited.insert(BB).second;
2022 if (InChanged) {
2023 LLVM_DEBUG(dbgs() << BB->getName() << " has new InLocs, process it\n");
2024 // Mutate a copy of LiveIn while processing BB. After calling process
2025 // LiveSet is the LiveOut set for BB.
2026 BlockInfo LiveSet = LiveIn[BB];
2027
2028 // Process the instructions in the block.
2029 process(*BB, &LiveSet);
2030
2031 // Relatively expensive check: has anything changed in LiveOut for BB?
2032 if (LiveOut[BB] != LiveSet) {
2033 LLVM_DEBUG(dbgs() << BB->getName()
2034 << " has new OutLocs, add succs to worklist: [ ");
2035 LiveOut[BB] = std::move(LiveSet);
2036 for (auto I = succ_begin(BB), E = succ_end(BB); I != E; I++) {
2037 if (OnPending.insert(*I).second) {
2038 LLVM_DEBUG(dbgs() << I->getName() << " ");
2039 Pending.push(BBToOrder[*I]);
2040 }
2041 }
2042 LLVM_DEBUG(dbgs() << "]\n");
2043 }
2044 }
2045 }
2046 Worklist.swap(Pending);
2047 // At this point, pending must be empty, since it was just the empty
2048 // worklist
2049 assert(Pending.empty() && "Pending should be empty");
2050 }
2051
2052 // That's the hard part over. Now we just have some admin to do.
2053
2054 // Record whether we inserted any intrinsics.
2055 bool InsertedAnyIntrinsics = false;
2056
2057 // Identify and add defs for single location variables.
2058 //
2059 // Go through all of the defs that we plan to add. If the aggregate variable
2060 // it's a part of is not in the NotAlwaysStackHomed set we can emit a single
2061 // location def and omit the rest. Add an entry to AlwaysStackHomed so that
2062 // we can identify those uneeded defs later.
2063 DenseSet<DebugAggregate> AlwaysStackHomed;
2064 for (const auto &Pair : InsertBeforeMap) {
2065 const auto &Vec = Pair.second;
2066 for (VarLocInfo VarLoc : Vec) {
2067 DebugVariable Var = FnVarLocs->getVariable(VarLoc.VariableID);
2068 DebugAggregate Aggr{Var.getVariable(), Var.getInlinedAt()};
2069
2070 // Skip this Var if it's not always stack homed.
2071 if (NotAlwaysStackHomed.contains(Aggr))
2072 continue;
2073
2074 // Skip complex cases such as when different fragments of a variable have
2075 // been split into different allocas. Skipping in this case means falling
2076 // back to using a list of defs (which could reduce coverage, but is no
2077 // less correct).
2078 bool Simple =
2079 VarLoc.Expr->getNumElements() == 1 && VarLoc.Expr->startsWithDeref();
2080 if (!Simple) {
2081 NotAlwaysStackHomed.insert(Aggr);
2082 continue;
2083 }
2084
2085 // All source assignments to this variable remain and all stores to any
2086 // part of the variable store to the same address (with varying
2087 // offsets). We can just emit a single location for the whole variable.
2088 //
2089 // Unless we've already done so, create the single location def now.
2090 if (AlwaysStackHomed.insert(Aggr).second) {
2091 assert(!VarLoc.Values.hasArgList() &&
2092 isa<AllocaInst>(VarLoc.Values.getVariableLocationOp(0)));
2093 // TODO: When more complex cases are handled VarLoc.Expr should be
2094 // built appropriately rather than always using an empty DIExpression.
2095 // The assert below is a reminder.
2096 assert(Simple);
2097 VarLoc.Expr = DIExpression::get(Fn.getContext(), std::nullopt);
2098 DebugVariable Var = FnVarLocs->getVariable(VarLoc.VariableID);
2099 FnVarLocs->addSingleLocVar(Var, VarLoc.Expr, VarLoc.DL, VarLoc.Values);
2100 InsertedAnyIntrinsics = true;
2101 }
2102 }
2103 }
2104
2105 // Insert the other DEFs.
2106 for (const auto &[InsertBefore, Vec] : InsertBeforeMap) {
2108 for (const VarLocInfo &VarLoc : Vec) {
2109 DebugVariable Var = FnVarLocs->getVariable(VarLoc.VariableID);
2110 DebugAggregate Aggr{Var.getVariable(), Var.getInlinedAt()};
2111 // If this variable is always stack homed then we have already inserted a
2112 // dbg.declare and deleted this dbg.value.
2113 if (AlwaysStackHomed.contains(Aggr))
2114 continue;
2115 NewDefs.push_back(VarLoc);
2116 InsertedAnyIntrinsics = true;
2117 }
2118
2119 FnVarLocs->setWedge(InsertBefore, std::move(NewDefs));
2120 }
2121
2122 InsertedAnyIntrinsics |= emitPromotedVarLocs(FnVarLocs);
2123
2124 return InsertedAnyIntrinsics;
2125}
2126
2127bool AssignmentTrackingLowering::emitPromotedVarLocs(
2128 FunctionVarLocsBuilder *FnVarLocs) {
2129 bool InsertedAnyIntrinsics = false;
2130 // Go through every block, translating debug intrinsics for fully promoted
2131 // variables into FnVarLocs location defs. No analysis required for these.
2132 for (auto &BB : Fn) {
2133 for (auto &I : BB) {
2134 // Skip instructions other than dbg.values and dbg.assigns.
2135 auto *DVI = dyn_cast<DbgValueInst>(&I);
2136 if (!DVI)
2137 continue;
2138 // Skip variables that haven't been promoted - we've dealt with those
2139 // already.
2140 if (VarsWithStackSlot->contains(getAggregate(DVI)))
2141 continue;
2142 Instruction *InsertBefore = I.getNextNode();
2143 assert(InsertBefore && "Unexpected: debug intrinsics after a terminator");
2144 FnVarLocs->addVarLoc(InsertBefore, DebugVariable(DVI),
2145 DVI->getExpression(), DVI->getDebugLoc(),
2146 DVI->getWrappedLocation());
2147 InsertedAnyIntrinsics = true;
2148 }
2149 }
2150 return InsertedAnyIntrinsics;
2151}
2152
2153/// Remove redundant definitions within sequences of consecutive location defs.
2154/// This is done using a backward scan to keep the last def describing a
2155/// specific variable/fragment.
2156///
2157/// This implements removeRedundantDbgInstrsUsingBackwardScan from
2158/// lib/Transforms/Utils/BasicBlockUtils.cpp for locations described with
2159/// FunctionVarLocsBuilder instead of with intrinsics.
2160static bool
2162 FunctionVarLocsBuilder &FnVarLocs) {
2163 bool Changed = false;
2164 SmallDenseSet<DebugVariable> VariableSet;
2165
2166 // Scan over the entire block, not just over the instructions mapped by
2167 // FnVarLocs, because wedges in FnVarLocs may only be seperated by debug
2168 // instructions.
2169 for (const Instruction &I : reverse(*BB)) {
2170 if (!isa<DbgVariableIntrinsic>(I)) {
2171 // Sequence of consecutive defs ended. Clear map for the next one.
2172 VariableSet.clear();
2173 }
2174
2175 // Get the location defs that start just before this instruction.
2176 const auto *Locs = FnVarLocs.getWedge(&I);
2177 if (!Locs)
2178 continue;
2179
2180 NumWedgesScanned++;
2181 bool ChangedThisWedge = false;
2182 // The new pruned set of defs, reversed because we're scanning backwards.
2183 SmallVector<VarLocInfo> NewDefsReversed;
2184
2185 // Iterate over the existing defs in reverse.
2186 for (auto RIt = Locs->rbegin(), REnd = Locs->rend(); RIt != REnd; ++RIt) {
2187 NumDefsScanned++;
2188 const DebugVariable &Key = FnVarLocs.getVariable(RIt->VariableID);
2189 bool FirstDefOfFragment = VariableSet.insert(Key).second;
2190
2191 // If the same variable fragment is described more than once it is enough
2192 // to keep the last one (i.e. the first found in this reverse iteration).
2193 if (FirstDefOfFragment) {
2194 // New def found: keep it.
2195 NewDefsReversed.push_back(*RIt);
2196 } else {
2197 // Redundant def found: throw it away. Since the wedge of defs is being
2198 // rebuilt, doing nothing is the same as deleting an entry.
2199 ChangedThisWedge = true;
2200 NumDefsRemoved++;
2201 }
2202 continue;
2203 }
2204
2205 // Un-reverse the defs and replace the wedge with the pruned version.
2206 if (ChangedThisWedge) {
2207 std::reverse(NewDefsReversed.begin(), NewDefsReversed.end());
2208 FnVarLocs.setWedge(&I, std::move(NewDefsReversed));
2209 NumWedgesChanged++;
2210 Changed = true;
2211 }
2212 }
2213
2214 return Changed;
2215}
2216
2217/// Remove redundant location defs using a forward scan. This can remove a
2218/// location definition that is redundant due to indicating that a variable has
2219/// the same value as is already being indicated by an earlier def.
2220///
2221/// This implements removeRedundantDbgInstrsUsingForwardScan from
2222/// lib/Transforms/Utils/BasicBlockUtils.cpp for locations described with
2223/// FunctionVarLocsBuilder instead of with intrinsics
2224static bool
2226 FunctionVarLocsBuilder &FnVarLocs) {
2227 bool Changed = false;
2229 VariableMap;
2230
2231 // Scan over the entire block, not just over the instructions mapped by
2232 // FnVarLocs, because wedges in FnVarLocs may only be seperated by debug
2233 // instructions.
2234 for (const Instruction &I : *BB) {
2235 // Get the defs that come just before this instruction.
2236 const auto *Locs = FnVarLocs.getWedge(&I);
2237 if (!Locs)
2238 continue;
2239
2240 NumWedgesScanned++;
2241 bool ChangedThisWedge = false;
2242 // The new pruned set of defs.
2244
2245 // Iterate over the existing defs.
2246 for (const VarLocInfo &Loc : *Locs) {
2247 NumDefsScanned++;
2248 DebugVariable Key(FnVarLocs.getVariable(Loc.VariableID).getVariable(),
2249 std::nullopt, Loc.DL.getInlinedAt());
2250 auto VMI = VariableMap.find(Key);
2251
2252 // Update the map if we found a new value/expression describing the
2253 // variable, or if the variable wasn't mapped already.
2254 if (VMI == VariableMap.end() || VMI->second.first != Loc.Values ||
2255 VMI->second.second != Loc.Expr) {
2256 VariableMap[Key] = {Loc.Values, Loc.Expr};
2257 NewDefs.push_back(Loc);
2258 continue;
2259 }
2260
2261 // Did not insert this Loc, which is the same as removing it.
2262 ChangedThisWedge = true;
2263 NumDefsRemoved++;
2264 }
2265
2266 // Replace the existing wedge with the pruned version.
2267 if (ChangedThisWedge) {
2268 FnVarLocs.setWedge(&I, std::move(NewDefs));
2269 NumWedgesChanged++;
2270 Changed = true;
2271 }
2272 }
2273
2274 return Changed;
2275}
2276
2277static bool
2279 FunctionVarLocsBuilder &FnVarLocs) {
2280 assert(BB->isEntryBlock());
2281 // Do extra work to ensure that we remove semantically unimportant undefs.
2282 //
2283 // This is to work around the fact that SelectionDAG will hoist dbg.values
2284 // using argument values to the top of the entry block. That can move arg
2285 // dbg.values before undef and constant dbg.values which they previously
2286 // followed. The easiest thing to do is to just try to feed SelectionDAG
2287 // input it's happy with.
2288 //
2289 // Map of {Variable x: Fragments y} where the fragments y of variable x have
2290 // have at least one non-undef location defined already. Don't use directly,
2291 // instead call DefineBits and HasDefinedBits.
2293 VarsWithDef;
2294 // Specify that V (a fragment of A) has a non-undef location.
2295 auto DefineBits = [&VarsWithDef](DebugAggregate A, DebugVariable V) {
2296 VarsWithDef[A].insert(V.getFragmentOrDefault());
2297 };
2298 // Return true if a non-undef location has been defined for V (a fragment of
2299 // A). Doesn't imply that the location is currently non-undef, just that a
2300 // non-undef location has been seen previously.
2301 auto HasDefinedBits = [&VarsWithDef](DebugAggregate A, DebugVariable V) {
2302 auto FragsIt = VarsWithDef.find(A);
2303 if (FragsIt == VarsWithDef.end())
2304 return false;
2305 return llvm::any_of(FragsIt->second, [V](auto Frag) {
2306 return DIExpression::fragmentsOverlap(Frag, V.getFragmentOrDefault());
2307 });
2308 };
2309
2310 bool Changed = false;
2312
2313 // Scan over the entire block, not just over the instructions mapped by
2314 // FnVarLocs, because wedges in FnVarLocs may only be seperated by debug
2315 // instructions.
2316 for (const Instruction &I : *BB) {
2317 // Get the defs that come just before this instruction.
2318 const auto *Locs = FnVarLocs.getWedge(&I);
2319 if (!Locs)
2320 continue;
2321
2322 NumWedgesScanned++;
2323 bool ChangedThisWedge = false;
2324 // The new pruned set of defs.
2326
2327 // Iterate over the existing defs.
2328 for (const VarLocInfo &Loc : *Locs) {
2329 NumDefsScanned++;
2330 DebugAggregate Aggr{FnVarLocs.getVariable(Loc.VariableID).getVariable(),
2331 Loc.DL.getInlinedAt()};
2332 DebugVariable Var = FnVarLocs.getVariable(Loc.VariableID);
2333
2334 // Remove undef entries that are encountered before any non-undef
2335 // intrinsics from the entry block.
2336 if (Loc.Values.isKillLocation(Loc.Expr) && !HasDefinedBits(Aggr, Var)) {
2337 // Did not insert this Loc, which is the same as removing it.
2338 NumDefsRemoved++;
2339 ChangedThisWedge = true;
2340 continue;
2341 }
2342
2343 DefineBits(Aggr, Var);
2344 NewDefs.push_back(Loc);
2345 }
2346
2347 // Replace the existing wedge with the pruned version.
2348 if (ChangedThisWedge) {
2349 FnVarLocs.setWedge(&I, std::move(NewDefs));
2350 NumWedgesChanged++;
2351 Changed = true;
2352 }
2353 }
2354
2355 return Changed;
2356}
2357
2359 FunctionVarLocsBuilder &FnVarLocs) {
2360 bool MadeChanges = false;
2361 MadeChanges |= removeRedundantDbgLocsUsingBackwardScan(BB, FnVarLocs);
2362 if (BB->isEntryBlock())
2363 MadeChanges |= removeUndefDbgLocsFromEntryBlock(BB, FnVarLocs);
2364 MadeChanges |= removeRedundantDbgLocsUsingForwardScan(BB, FnVarLocs);
2365
2366 if (MadeChanges)
2367 LLVM_DEBUG(dbgs() << "Removed redundant dbg locs from: " << BB->getName()
2368 << "\n");
2369 return MadeChanges;
2370}
2371
2374 for (auto &BB : Fn) {
2375 for (auto &I : BB) {
2376 // Any variable linked to an instruction is considered
2377 // interesting. Ideally we only need to check Allocas, however, a
2378 // DIAssignID might get dropped from an alloca but not stores. In that
2379 // case, we need to consider the variable interesting for NFC behaviour
2380 // with this change. TODO: Consider only looking at allocas.
2382 Result.insert({DAI->getVariable(), DAI->getDebugLoc().getInlinedAt()});
2383 }
2384 }
2385 }
2386 return Result;
2387}
2388
2389static void analyzeFunction(Function &Fn, const DataLayout &Layout,
2390 FunctionVarLocsBuilder *FnVarLocs) {
2391 // The analysis will generate location definitions for all variables, but we
2392 // only need to perform a dataflow on the set of variables which have a stack
2393 // slot. Find those now.
2394 DenseSet<DebugAggregate> VarsWithStackSlot = findVarsWithStackSlot(Fn);
2395
2396 bool Changed = false;
2397
2398 // Use a scope block to clean up AssignmentTrackingLowering before running
2399 // MemLocFragmentFill to reduce peak memory consumption.
2400 {
2401 AssignmentTrackingLowering Pass(Fn, Layout, &VarsWithStackSlot);
2402 Changed = Pass.run(FnVarLocs);
2403 }
2404
2405 if (Changed) {
2406 MemLocFragmentFill Pass(Fn, &VarsWithStackSlot);
2407 Pass.run(FnVarLocs);
2408
2409 // Remove redundant entries. As well as reducing memory consumption and
2410 // avoiding waiting cycles later by burning some now, this has another
2411 // important job. That is to work around some SelectionDAG quirks. See
2412 // removeRedundantDbgLocsUsingForwardScan comments for more info on that.
2413 for (auto &BB : Fn)
2414 removeRedundantDbgLocs(&BB, *FnVarLocs);
2415 }
2416}
2417
2419 if (!isAssignmentTrackingEnabled(*F.getParent()))
2420 return false;
2421
2422 LLVM_DEBUG(dbgs() << "AssignmentTrackingAnalysis run on " << F.getName()
2423 << "\n");
2424 auto DL = std::make_unique<DataLayout>(F.getParent());
2425
2426 // Clear previous results.
2427 Results->clear();
2428
2430 analyzeFunction(F, *DL.get(), &Builder);
2431
2432 // Save these results.
2433 Results->init(Builder);
2434
2435 if (PrintResults && isFunctionInPrintList(F.getName()))
2436 Results->print(errs(), F);
2437
2438 // Return false because this pass does not modify the function.
2439 return false;
2440}
2441
2443 : FunctionPass(ID), Results(std::make_unique<FunctionVarLocs>()) {}
2444
2446
2448 "Assignment Tracking Analysis", false, true)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Function Alias Analysis Results
std::pair< const DILocalVariable *, const DILocation * > DebugAggregate
A whole (unfragmented) source variable.
static void analyzeFunction(Function &Fn, const DataLayout &Layout, FunctionVarLocsBuilder *FnVarLocs)
static std::pair< Value *, DIExpression * > walkToAllocaAndPrependOffsetDeref(const DataLayout &DL, Value *Start, DIExpression *Expression)
Walk backwards along constant GEPs and bitcasts to the base storage from Start as far as possible.
static DIAssignID * getIDFromMarker(const DbgAssignIntrinsic &DAI)
static DenseSet< DebugAggregate > findVarsWithStackSlot(Function &Fn)
static bool fullyContains(DIExpression::FragmentInfo A, DIExpression::FragmentInfo B)
Return true if A fully contains B.
static DebugAggregate getAggregate(const DbgVariableIntrinsic *DII)
static std::optional< at::AssignmentInfo > getUntaggedStoreAssignmentInfo(const Instruction &I, const DataLayout &Layout)
static bool removeUndefDbgLocsFromEntryBlock(const BasicBlock *BB, FunctionVarLocsBuilder &FnVarLocs)
static cl::opt< bool > PrintResults("print-debug-ata", cl::init(false), cl::Hidden)
Print the results of the analysis. Respects -filter-print-funcs.
const char * locStr(AssignmentTrackingLowering::LocKind Loc)
static bool removeRedundantDbgLocsUsingForwardScan(const BasicBlock *BB, FunctionVarLocsBuilder &FnVarLocs)
Remove redundant location defs using a forward scan.
static bool removeRedundantDbgLocs(const BasicBlock *BB, FunctionVarLocsBuilder &FnVarLocs)
static cl::opt< bool > EnableMemLocFragFill("mem-loc-frag-fill", cl::init(true), cl::Hidden)
Option for debugging the pass, determines if the memory location fragment filling happens after gener...
static DIAssignID * getIDFromInst(const Instruction &I)
static AssignmentTrackingLowering::OverlapMap buildOverlapMapAndRecordDeclares(Function &Fn, FunctionVarLocsBuilder *FnVarLocs, AssignmentTrackingLowering::UntaggedStoreAssignmentMap &UntaggedStoreVars, unsigned &TrackedVariablesVectorSize)
Build a map of {Variable x: Variables y} where all variable fragments contained within the variable f...
static std::optional< int64_t > getDerefOffsetInBytes(const DIExpression *DIExpr)
Extract the offset used in DIExpr.
static bool removeRedundantDbgLocsUsingBackwardScan(const BasicBlock *BB, FunctionVarLocsBuilder &FnVarLocs)
Remove redundant definitions within sequences of consecutive location defs.
static cl::opt< unsigned > MaxNumBlocks("debug-ata-max-blocks", cl::init(10000), cl::desc("Maximum num basic blocks before debug info dropped"), cl::Hidden)
assume Assume Builder
for(auto &MBB :MF)
This file implements the BitVector class.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
dxil metadata DXIL Metadata Emit
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines DenseMapInfo traits for DenseMap.
This file contains constants used for implementing Dwarf debug support.
std::optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1260
#define DEBUG_TYPE
IRTranslator LLVM IR MI
This file implements a coalescing interval map for small objects.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
if(VerifyEach)
bool Debug
This header defines various interfaces for pass management in LLVM.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
@ SI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Scalar Replacement Of Aggregates
Definition: SROA.cpp:5172
This file contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
This file defines the SmallSet class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
Value * RHS
Value * LHS
Helper class to build FunctionVarLocs, since that class isn't easy to modify.
void addVarLoc(Instruction *Before, DebugVariable Var, DIExpression *Expr, DebugLoc DL, RawLocationWrapper R)
Add a def to the wedge of defs just before /p Before.
void setWedge(const Instruction *Before, SmallVector< VarLocInfo > &&Wedge)
Replace the defs that come just before /p Before with /p Wedge.
const SmallVectorImpl< VarLocInfo > * getWedge(const Instruction *Before) const
Return ptr to wedge of defs or nullptr if no defs come just before /p Before.
void addSingleLocVar(DebugVariable Var, DIExpression *Expr, DebugLoc DL, RawLocationWrapper R)
Add a def for a variable that is valid for its lifetime.
VariableID insertVariable(DebugVariable V)
Find or insert V and return the ID.
const DebugVariable & getVariable(VariableID ID) const
Get a variable from its ID.
Class for arbitrary precision integers.
Definition: APInt.h:75
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1494
bool getBoolValue() const
Convert APInt to a boolean value.
Definition: APInt.h:459
an instruction to allocate memory on the stack
Definition: Instructions.h:58
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator end()
Definition: BasicBlock.h:316
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:314
bool isEntryBlock() const
Return true if this is the entry block of the containing function.
Definition: BasicBlock.cpp:395
BitVector & set()
Definition: BitVector.h:351
iterator_range< const_set_bits_iterator > set_bits() const
Definition: BitVector.h:140
Assignment ID.
A structured debug information entry.
Definition: DIE.h:744
DWARF expression.
static DIExpression * append(const DIExpression *Expr, ArrayRef< uint64_t > Ops)
Append the opcodes Ops to DIExpr.
unsigned getNumElements() const
bool startsWithDeref() const
Return whether the first element a DW_OP_deref.
static std::optional< FragmentInfo > getFragmentInfo(expr_op_iterator Start, expr_op_iterator End)
Retrieve the details of this fragment expression.
ArrayRef< uint64_t > getElements() const
static std::optional< DIExpression * > createFragmentExpression(const DIExpression *Expr, unsigned OffsetInBits, unsigned SizeInBits)
Create a DIExpression to describe one part of an aggregate variable that is fragmented across multipl...
static DIExpression * prepend(const DIExpression *Expr, uint8_t Flags, int64_t Offset=0)
Prepend DIExpr with a deref and offset operation and optionally turn it into a stack value or/and an ...
static DIExpression * prependOpcodes(const DIExpression *Expr, SmallVectorImpl< uint64_t > &Ops, bool StackValue=false, bool EntryValue=false)
Prepend DIExpr with the given opcodes and optionally turn it into a stack value.
Debug location.
std::optional< uint64_t > getSizeInBits() const
Determines the size of the variable's type.
StringRef getName() const
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
This represents the llvm.dbg.assign instruction.
DIAssignID * getAssignID() const
bool isKillAddress() const
Check whether this kills the address component.
This represents the llvm.dbg.value instruction.
This is the common base class for debug info intrinsics for variables.
DILocalVariable * getVariable() const
DIExpression * getExpression() const
RawLocationWrapper getWrappedLocation() const
A debug info location.
Definition: DebugLoc.h:33
DILocation * getInlinedAt() const
Definition: DebugLoc.cpp:39
Identifies a unique instance of a variable.
const DILocation * getInlinedAt() const
const DILocalVariable * getVariable() const
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
iterator end()
Definition: DenseMap.h:84
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
void init(unsigned InitNumEntries)
Definition: DenseMap.h:805
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Class representing an expression and its matching format.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
Data structure describing the variable locations in a function.
void print(raw_ostream &OS, const Function &Fn) const
const VarLocInfo * locs_begin(const Instruction *Before) const
First variable location definition that comes before Before.
const VarLocInfo * single_locs_begin() const
const VarLocInfo * locs_end(const Instruction *Before) const
One past the last variable location definition that comes before Before.
const VarLocInfo * single_locs_end() const
One past the last single-location variable location definition.
void init(FunctionVarLocsBuilder &Builder)
size_t size() const
Definition: Function.h:761
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:319
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:652
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:358
bool isTerminator() const
Definition: Instruction.h:171
const_iterator begin() const
Definition: IntervalMap.h:1146
void insert(KeyT a, KeyT b, ValT y)
insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
Definition: IntervalMap.h:1129
void clear()
clear - Remove all entries.
Definition: IntervalMap.h:1330
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1399
void push_back(MachineInstr *MI)
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
Root of the metadata hierarchy.
Definition: Metadata.h:61
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:398
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1750
Lightweight class that wraps the location operand metadata of a debug intrinsic.
Value * getVariableLocationOp(unsigned OpIdx) const
Implements a dense probed hash-table based set with some number of buckets stored inline.
Definition: DenseSet.h:290
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
Target - Wrapper for Target specific information.
static IntegerType * getInt1Ty(LLVMContext &C)
UniqueVector - This class produces a sequential ID number (base 1) for each unique entry that is adde...
Definition: UniqueVector.h:24
unsigned insert(const T &Entry)
insert - Append entry to the vector if it doesn't already exist.
Definition: UniqueVector.h:40
size_t size() const
size - Returns the number of entries in the vector.
Definition: UniqueVector.h:87
static ValueAsMetadata * get(Value *V)
Definition: Metadata.cpp:392
LLVM Value Representation.
Definition: Value.h:74
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
Definition: DenseSet.h:185
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:119
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
void deleteAll(Function *F)
Remove all Assignment Tracking related intrinsics and metadata from F.
Definition: DebugInfo.cpp:1782
AssignmentMarkerRange getAssignmentMarkers(DIAssignID *ID)
Return a range of dbg.assign intrinsics which use \ID as an operand.
Definition: DebugInfo.cpp:1741
std::optional< AssignmentInfo > getAssignmentInfo(const DataLayout &DL, const MemIntrinsic *I)
Definition: DebugInfo.cpp:1813
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
std::optional< const char * > toString(const std::optional< DWARFFormValue > &V)
Take an optional DWARFFormValue and try to extract a string value from it.
@ DW_OP_LLVM_fragment
Only used in LLVM metadata.
Definition: Dwarf.h:141
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
@ Offset
Definition: DWP.cpp:406
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1819
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:2047
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1826
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:511
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool isFunctionInPrintList(StringRef FunctionName)
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:109
VariableID
Type wrapper for integer ID for Variables. 0 is reserved.
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
bool isAssignmentTrackingEnabled(const Module &M)
Return true if assignment tracking is enabled for module M.
Definition: DebugInfo.cpp:2027
constexpr std::nullopt_t None
Definition: None.h:28
Definition: BitVector.h:858
Holds the characteristics of one fragment of a larger variable.
static bool isEqual(const VariableID &LHS, const VariableID &RHS)
static unsigned getHashValue(const VariableID &Val)
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: DenseMapInfo.h:51
Variable location definition used by FunctionVarLocs.
RawLocationWrapper Values