LLVM 19.0.0git
AssignmentTrackingAnalysis.cpp
Go to the documentation of this file.
1//===-- AssignmentTrackingAnalysis.cpp ------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
11#include "llvm/ADT/BitVector.h"
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/Statistic.h"
20#include "llvm/IR/BasicBlock.h"
21#include "llvm/IR/DataLayout.h"
22#include "llvm/IR/DebugInfo.h"
24#include "llvm/IR/Function.h"
25#include "llvm/IR/Instruction.h"
27#include "llvm/IR/PassManager.h"
28#include "llvm/IR/PrintPasses.h"
34#include <assert.h>
35#include <cstdint>
36#include <optional>
37#include <queue>
38#include <sstream>
39#include <unordered_map>
40
41using namespace llvm;
42#define DEBUG_TYPE "debug-ata"
43
44STATISTIC(NumDefsScanned, "Number of dbg locs that get scanned for removal");
45STATISTIC(NumDefsRemoved, "Number of dbg locs removed");
46STATISTIC(NumWedgesScanned, "Number of dbg wedges scanned");
47STATISTIC(NumWedgesChanged, "Number of dbg wedges changed");
48
50 MaxNumBlocks("debug-ata-max-blocks", cl::init(10000),
51 cl::desc("Maximum num basic blocks before debug info dropped"),
53/// Option for debugging the pass, determines if the memory location fragment
54/// filling happens after generating the variable locations.
55static cl::opt<bool> EnableMemLocFragFill("mem-loc-frag-fill", cl::init(true),
57/// Print the results of the analysis. Respects -filter-print-funcs.
58static cl::opt<bool> PrintResults("print-debug-ata", cl::init(false),
60
61/// Coalesce adjacent dbg locs describing memory locations that have contiguous
62/// fragments. This reduces the cost of LiveDebugValues which does SSA
63/// construction for each explicitly stated variable fragment.
65 CoalesceAdjacentFragmentsOpt("debug-ata-coalesce-frags", cl::Hidden);
66
67// Implicit conversions are disabled for enum class types, so unfortunately we
68// need to create a DenseMapInfo wrapper around the specified underlying type.
69template <> struct llvm::DenseMapInfo<VariableID> {
71 static inline VariableID getEmptyKey() {
72 return static_cast<VariableID>(Wrapped::getEmptyKey());
73 }
74 static inline VariableID getTombstoneKey() {
75 return static_cast<VariableID>(Wrapped::getTombstoneKey());
76 }
77 static unsigned getHashValue(const VariableID &Val) {
78 return Wrapped::getHashValue(static_cast<unsigned>(Val));
79 }
80 static bool isEqual(const VariableID &LHS, const VariableID &RHS) {
81 return LHS == RHS;
82 }
83};
84
86
87namespace std {
88template <> struct hash<VarLocInsertPt> {
90 using result_type = std::size_t;
91
93 return std::hash<void *>()(Arg.getOpaqueValue());
94 }
95};
96} // namespace std
97
98/// Helper class to build FunctionVarLocs, since that class isn't easy to
99/// modify. TODO: There's not a great deal of value in the split, it could be
100/// worth merging the two classes.
102 friend FunctionVarLocs;
104 // Use an unordered_map so we don't invalidate iterators after
105 // insert/modifications.
106 std::unordered_map<VarLocInsertPt, SmallVector<VarLocInfo>> VarLocsBeforeInst;
107
108 SmallVector<VarLocInfo> SingleLocVars;
109
110public:
111 unsigned getNumVariables() const { return Variables.size(); }
112
113 /// Find or insert \p V and return the ID.
115 return static_cast<VariableID>(Variables.insert(V));
116 }
117
118 /// Get a variable from its \p ID.
120 return Variables[static_cast<unsigned>(ID)];
121 }
122
123 /// Return ptr to wedge of defs or nullptr if no defs come just before /p
124 /// Before.
126 auto R = VarLocsBeforeInst.find(Before);
127 if (R == VarLocsBeforeInst.end())
128 return nullptr;
129 return &R->second;
130 }
131
132 /// Replace the defs that come just before /p Before with /p Wedge.
134 VarLocsBeforeInst[Before] = std::move(Wedge);
135 }
136
137 /// Add a def for a variable that is valid for its lifetime.
140 VarLocInfo VarLoc;
141 VarLoc.VariableID = insertVariable(Var);
142 VarLoc.Expr = Expr;
143 VarLoc.DL = DL;
144 VarLoc.Values = R;
145 SingleLocVars.emplace_back(VarLoc);
146 }
147
148 /// Add a def to the wedge of defs just before /p Before.
151 VarLocInfo VarLoc;
152 VarLoc.VariableID = insertVariable(Var);
153 VarLoc.Expr = Expr;
154 VarLoc.DL = DL;
155 VarLoc.Values = R;
156 VarLocsBeforeInst[Before].emplace_back(VarLoc);
157 }
158};
159
161 // Print the variable table first. TODO: Sorting by variable could make the
162 // output more stable?
163 unsigned Counter = -1;
164 OS << "=== Variables ===\n";
165 for (const DebugVariable &V : Variables) {
166 ++Counter;
167 // Skip first entry because it is a dummy entry.
168 if (Counter == 0) {
169 continue;
170 }
171 OS << "[" << Counter << "] " << V.getVariable()->getName();
172 if (auto F = V.getFragment())
173 OS << " bits [" << F->OffsetInBits << ", "
174 << F->OffsetInBits + F->SizeInBits << ")";
175 if (const auto *IA = V.getInlinedAt())
176 OS << " inlined-at " << *IA;
177 OS << "\n";
178 }
179
180 auto PrintLoc = [&OS](const VarLocInfo &Loc) {
181 OS << "DEF Var=[" << (unsigned)Loc.VariableID << "]"
182 << " Expr=" << *Loc.Expr << " Values=(";
183 for (auto *Op : Loc.Values.location_ops()) {
184 errs() << Op->getName() << " ";
185 }
186 errs() << ")\n";
187 };
188
189 // Print the single location variables.
190 OS << "=== Single location vars ===\n";
191 for (auto It = single_locs_begin(), End = single_locs_end(); It != End;
192 ++It) {
193 PrintLoc(*It);
194 }
195
196 // Print the non-single-location defs in line with IR.
197 OS << "=== In-line variable defs ===";
198 for (const BasicBlock &BB : Fn) {
199 OS << "\n" << BB.getName() << ":\n";
200 for (const Instruction &I : BB) {
201 for (auto It = locs_begin(&I), End = locs_end(&I); It != End; ++It) {
202 PrintLoc(*It);
203 }
204 OS << I << "\n";
205 }
206 }
207}
208
210 // Add the single-location variables first.
211 for (const auto &VarLoc : Builder.SingleLocVars)
212 VarLocRecords.emplace_back(VarLoc);
213 // Mark the end of the section.
214 SingleVarLocEnd = VarLocRecords.size();
215
216 // Insert a contiguous block of VarLocInfos for each instruction, mapping it
217 // to the start and end position in the vector with VarLocsBeforeInst. This
218 // block includes VarLocs for any DPValues attached to that instruction.
219 for (auto &P : Builder.VarLocsBeforeInst) {
220 // Process VarLocs attached to a DPValue alongside their marker Instruction.
221 if (isa<const DbgRecord *>(P.first))
222 continue;
223 const Instruction *I = cast<const Instruction *>(P.first);
224 unsigned BlockStart = VarLocRecords.size();
225 // Any VarLocInfos attached to a DPValue should now be remapped to their
226 // marker Instruction, in order of DPValue appearance and prior to any
227 // VarLocInfos attached directly to that instruction.
228 for (const DPValue &DPV : DPValue::filter(I->getDbgValueRange())) {
229 // Even though DPV defines a variable location, VarLocsBeforeInst can
230 // still be empty if that VarLoc was redundant.
231 if (!Builder.VarLocsBeforeInst.count(&DPV))
232 continue;
233 for (const VarLocInfo &VarLoc : Builder.VarLocsBeforeInst[&DPV])
234 VarLocRecords.emplace_back(VarLoc);
235 }
236 for (const VarLocInfo &VarLoc : P.second)
237 VarLocRecords.emplace_back(VarLoc);
238 unsigned BlockEnd = VarLocRecords.size();
239 // Record the start and end indices.
240 if (BlockEnd != BlockStart)
241 VarLocsBeforeInst[I] = {BlockStart, BlockEnd};
242 }
243
244 // Copy the Variables vector from the builder's UniqueVector.
245 assert(Variables.empty() && "Expect clear before init");
246 // UniqueVectors IDs are one-based (which means the VarLocInfo VarID values
247 // are one-based) so reserve an extra and insert a dummy.
248 Variables.reserve(Builder.Variables.size() + 1);
249 Variables.push_back(DebugVariable(nullptr, std::nullopt, nullptr));
250 Variables.append(Builder.Variables.begin(), Builder.Variables.end());
251}
252
254 Variables.clear();
255 VarLocRecords.clear();
256 VarLocsBeforeInst.clear();
257 SingleVarLocEnd = 0;
258}
259
260/// Walk backwards along constant GEPs and bitcasts to the base storage from \p
261/// Start as far as possible. Prepend \Expression with the offset and append it
262/// with a DW_OP_deref that haes been implicit until now. Returns the walked-to
263/// value and modified expression.
264static std::pair<Value *, DIExpression *>
267 APInt OffsetInBytes(DL.getTypeSizeInBits(Start->getType()), false);
268 Value *End =
269 Start->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetInBytes);
271 if (OffsetInBytes.getBoolValue()) {
272 Ops = {dwarf::DW_OP_plus_uconst, OffsetInBytes.getZExtValue()};
274 Expression, Ops, /*StackValue=*/false, /*EntryValue=*/false);
275 }
276 Expression = DIExpression::append(Expression, {dwarf::DW_OP_deref});
277 return {End, Expression};
278}
279
280/// Extract the offset used in \p DIExpr. Returns std::nullopt if the expression
281/// doesn't explicitly describe a memory location with DW_OP_deref or if the
282/// expression is too complex to interpret.
283static std::optional<int64_t>
285 int64_t Offset = 0;
286 const unsigned NumElements = DIExpr->getNumElements();
287 const auto Elements = DIExpr->getElements();
288 unsigned ExpectedDerefIdx = 0;
289 // Extract the offset.
290 if (NumElements > 2 && Elements[0] == dwarf::DW_OP_plus_uconst) {
291 Offset = Elements[1];
292 ExpectedDerefIdx = 2;
293 } else if (NumElements > 3 && Elements[0] == dwarf::DW_OP_constu) {
294 ExpectedDerefIdx = 3;
295 if (Elements[2] == dwarf::DW_OP_plus)
296 Offset = Elements[1];
297 else if (Elements[2] == dwarf::DW_OP_minus)
298 Offset = -Elements[1];
299 else
300 return std::nullopt;
301 }
302
303 // If that's all there is it means there's no deref.
304 if (ExpectedDerefIdx >= NumElements)
305 return std::nullopt;
306
307 // Check the next element is DW_OP_deref - otherwise this is too complex or
308 // isn't a deref expression.
309 if (Elements[ExpectedDerefIdx] != dwarf::DW_OP_deref)
310 return std::nullopt;
311
312 // Check the final operation is either the DW_OP_deref or is a fragment.
313 if (NumElements == ExpectedDerefIdx + 1)
314 return Offset; // Ends with deref.
315 unsigned ExpectedFragFirstIdx = ExpectedDerefIdx + 1;
316 unsigned ExpectedFragFinalIdx = ExpectedFragFirstIdx + 2;
317 if (NumElements == ExpectedFragFinalIdx + 1 &&
318 Elements[ExpectedFragFirstIdx] == dwarf::DW_OP_LLVM_fragment)
319 return Offset; // Ends with deref + fragment.
320
321 // Don't bother trying to interpret anything more complex.
322 return std::nullopt;
323}
324
325/// A whole (unfragmented) source variable.
326using DebugAggregate = std::pair<const DILocalVariable *, const DILocation *>;
328 return DebugAggregate(DII->getVariable(), DII->getDebugLoc().getInlinedAt());
329}
331 return DebugAggregate(Var.getVariable(), Var.getInlinedAt());
332}
333
335 // Enabling fragment coalescing reduces compiler run time when instruction
336 // referencing is enabled. However, it may cause LiveDebugVariables to create
337 // incorrect locations. Since instruction-referencing mode effectively
338 // bypasses LiveDebugVariables we only enable coalescing if the cl::opt flag
339 // has not been explicitly set and instruction-referencing is turned on.
343 Triple(F.getParent()->getTargetTriple()));
345 return true;
347 return false;
348 }
349 llvm_unreachable("Unknown boolOrDefault value");
350}
351
352namespace {
353/// In dwarf emission, the following sequence
354/// 1. dbg.value ... Fragment(0, 64)
355/// 2. dbg.value ... Fragment(0, 32)
356/// effectively sets Fragment(32, 32) to undef (each def sets all bits not in
357/// the intersection of the fragments to having "no location"). This makes
358/// sense for implicit location values because splitting the computed values
359/// could be troublesome, and is probably quite uncommon. When we convert
360/// dbg.assigns to dbg.value+deref this kind of thing is common, and describing
361/// a location (memory) rather than a value means we don't need to worry about
362/// splitting any values, so we try to recover the rest of the fragment
363/// location here.
364/// This class performs a(nother) dataflow analysis over the function, adding
365/// variable locations so that any bits of a variable with a memory location
366/// have that location explicitly reinstated at each subsequent variable
367/// location definition that that doesn't overwrite those bits. i.e. after a
368/// variable location def, insert new defs for the memory location with
369/// fragments for the difference of "all bits currently in memory" and "the
370/// fragment of the second def".
371class MemLocFragmentFill {
372 Function &Fn;
373 FunctionVarLocsBuilder *FnVarLocs;
374 const DenseSet<DebugAggregate> *VarsWithStackSlot;
375 bool CoalesceAdjacentFragments;
376
377 // 0 = no memory location.
378 using BaseAddress = unsigned;
379 using OffsetInBitsTy = unsigned;
381 using FragsInMemMap = IntervalMap<
382 OffsetInBitsTy, BaseAddress,
384 FragTraits>;
385 FragsInMemMap::Allocator IntervalMapAlloc;
386 using VarFragMap = DenseMap<unsigned, FragsInMemMap>;
387
388 /// IDs for memory location base addresses in maps. Use 0 to indicate that
389 /// there's no memory location.
394
395 struct FragMemLoc {
396 unsigned Var;
397 unsigned Base;
398 unsigned OffsetInBits;
399 unsigned SizeInBits;
400 DebugLoc DL;
401 };
403
404 /// BBInsertBeforeMap holds a description for the set of location defs to be
405 /// inserted after the analysis is complete. It is updated during the dataflow
406 /// and the entry for a block is CLEARED each time it is (re-)visited. After
407 /// the dataflow is complete, each block entry will contain the set of defs
408 /// calculated during the final (fixed-point) iteration.
410
411 static bool intervalMapsAreEqual(const FragsInMemMap &A,
412 const FragsInMemMap &B) {
413 auto AIt = A.begin(), AEnd = A.end();
414 auto BIt = B.begin(), BEnd = B.end();
415 for (; AIt != AEnd; ++AIt, ++BIt) {
416 if (BIt == BEnd)
417 return false; // B has fewer elements than A.
418 if (AIt.start() != BIt.start() || AIt.stop() != BIt.stop())
419 return false; // Interval is different.
420 if (*AIt != *BIt)
421 return false; // Value at interval is different.
422 }
423 // AIt == AEnd. Check BIt is also now at end.
424 return BIt == BEnd;
425 }
426
427 static bool varFragMapsAreEqual(const VarFragMap &A, const VarFragMap &B) {
428 if (A.size() != B.size())
429 return false;
430 for (const auto &APair : A) {
431 auto BIt = B.find(APair.first);
432 if (BIt == B.end())
433 return false;
434 if (!intervalMapsAreEqual(APair.second, BIt->second))
435 return false;
436 }
437 return true;
438 }
439
440 /// Return a string for the value that \p BaseID represents.
441 std::string toString(unsigned BaseID) {
442 if (BaseID)
443 return Bases[BaseID].getVariableLocationOp(0)->getName().str();
444 else
445 return "None";
446 }
447
448 /// Format string describing an FragsInMemMap (IntervalMap) interval.
449 std::string toString(FragsInMemMap::const_iterator It, bool Newline = true) {
450 std::string String;
451 std::stringstream S(String);
452 if (It.valid()) {
453 S << "[" << It.start() << ", " << It.stop()
454 << "): " << toString(It.value());
455 } else {
456 S << "invalid iterator (end)";
457 }
458 if (Newline)
459 S << "\n";
460 return S.str();
461 };
462
463 FragsInMemMap meetFragments(const FragsInMemMap &A, const FragsInMemMap &B) {
464 FragsInMemMap Result(IntervalMapAlloc);
465 for (auto AIt = A.begin(), AEnd = A.end(); AIt != AEnd; ++AIt) {
466 LLVM_DEBUG(dbgs() << "a " << toString(AIt));
467 // This is basically copied from process() and inverted (process is
468 // performing something like a union whereas this is more of an
469 // intersect).
470
471 // There's no work to do if interval `a` overlaps no fragments in map `B`.
472 if (!B.overlaps(AIt.start(), AIt.stop()))
473 continue;
474
475 // Does StartBit intersect an existing fragment?
476 auto FirstOverlap = B.find(AIt.start());
477 assert(FirstOverlap != B.end());
478 bool IntersectStart = FirstOverlap.start() < AIt.start();
479 LLVM_DEBUG(dbgs() << "- FirstOverlap " << toString(FirstOverlap, false)
480 << ", IntersectStart: " << IntersectStart << "\n");
481
482 // Does EndBit intersect an existing fragment?
483 auto LastOverlap = B.find(AIt.stop());
484 bool IntersectEnd =
485 LastOverlap != B.end() && LastOverlap.start() < AIt.stop();
486 LLVM_DEBUG(dbgs() << "- LastOverlap " << toString(LastOverlap, false)
487 << ", IntersectEnd: " << IntersectEnd << "\n");
488
489 // Check if both ends of `a` intersect the same interval `b`.
490 if (IntersectStart && IntersectEnd && FirstOverlap == LastOverlap) {
491 // Insert `a` (`a` is contained in `b`) if the values match.
492 // [ a ]
493 // [ - b - ]
494 // -
495 // [ r ]
496 LLVM_DEBUG(dbgs() << "- a is contained within "
497 << toString(FirstOverlap));
498 if (*AIt && *AIt == *FirstOverlap)
499 Result.insert(AIt.start(), AIt.stop(), *AIt);
500 } else {
501 // There's an overlap but `a` is not fully contained within
502 // `b`. Shorten any end-point intersections.
503 // [ - a - ]
504 // [ - b - ]
505 // -
506 // [ r ]
507 auto Next = FirstOverlap;
508 if (IntersectStart) {
509 LLVM_DEBUG(dbgs() << "- insert intersection of a and "
510 << toString(FirstOverlap));
511 if (*AIt && *AIt == *FirstOverlap)
512 Result.insert(AIt.start(), FirstOverlap.stop(), *AIt);
513 ++Next;
514 }
515 // [ - a - ]
516 // [ - b - ]
517 // -
518 // [ r ]
519 if (IntersectEnd) {
520 LLVM_DEBUG(dbgs() << "- insert intersection of a and "
521 << toString(LastOverlap));
522 if (*AIt && *AIt == *LastOverlap)
523 Result.insert(LastOverlap.start(), AIt.stop(), *AIt);
524 }
525
526 // Insert all intervals in map `B` that are contained within interval
527 // `a` where the values match.
528 // [ - - a - - ]
529 // [ b1 ] [ b2 ]
530 // -
531 // [ r1 ] [ r2 ]
532 while (Next != B.end() && Next.start() < AIt.stop() &&
533 Next.stop() <= AIt.stop()) {
535 << "- insert intersection of a and " << toString(Next));
536 if (*AIt && *AIt == *Next)
537 Result.insert(Next.start(), Next.stop(), *Next);
538 ++Next;
539 }
540 }
541 }
542 return Result;
543 }
544
545 /// Meet \p A and \p B, storing the result in \p A.
546 void meetVars(VarFragMap &A, const VarFragMap &B) {
547 // Meet A and B.
548 //
549 // Result = meet(a, b) for a in A, b in B where Var(a) == Var(b)
550 for (auto It = A.begin(), End = A.end(); It != End; ++It) {
551 unsigned AVar = It->first;
552 FragsInMemMap &AFrags = It->second;
553 auto BIt = B.find(AVar);
554 if (BIt == B.end()) {
555 A.erase(It);
556 continue; // Var has no bits defined in B.
557 }
558 LLVM_DEBUG(dbgs() << "meet fragment maps for "
559 << Aggregates[AVar].first->getName() << "\n");
560 AFrags = meetFragments(AFrags, BIt->second);
561 }
562 }
563
564 bool meet(const BasicBlock &BB,
565 const SmallPtrSet<BasicBlock *, 16> &Visited) {
566 LLVM_DEBUG(dbgs() << "meet block info from preds of " << BB.getName()
567 << "\n");
568
569 VarFragMap BBLiveIn;
570 bool FirstMeet = true;
571 // LiveIn locs for BB is the meet of the already-processed preds' LiveOut
572 // locs.
573 for (auto I = pred_begin(&BB), E = pred_end(&BB); I != E; I++) {
574 // Ignore preds that haven't been processed yet. This is essentially the
575 // same as initialising all variables to implicit top value (⊤) which is
576 // the identity value for the meet operation.
577 const BasicBlock *Pred = *I;
578 if (!Visited.count(Pred))
579 continue;
580
581 auto PredLiveOut = LiveOut.find(Pred);
582 assert(PredLiveOut != LiveOut.end());
583
584 if (FirstMeet) {
585 LLVM_DEBUG(dbgs() << "BBLiveIn = " << Pred->getName() << "\n");
586 BBLiveIn = PredLiveOut->second;
587 FirstMeet = false;
588 } else {
589 LLVM_DEBUG(dbgs() << "BBLiveIn = meet BBLiveIn, " << Pred->getName()
590 << "\n");
591 meetVars(BBLiveIn, PredLiveOut->second);
592 }
593
594 // An empty set is ⊥ for the intersect-like meet operation. If we've
595 // already got ⊥ there's no need to run the code - we know the result is
596 // ⊥ since `meet(a, ⊥) = ⊥`.
597 if (BBLiveIn.size() == 0)
598 break;
599 }
600
601 auto CurrentLiveInEntry = LiveIn.find(&BB);
602 // If there's no LiveIn entry for the block yet, add it.
603 if (CurrentLiveInEntry == LiveIn.end()) {
604 LLVM_DEBUG(dbgs() << "change=true (first) on meet on " << BB.getName()
605 << "\n");
606 LiveIn[&BB] = std::move(BBLiveIn);
607 return /*Changed=*/true;
608 }
609
610 // If the LiveIn set has changed (expensive check) update it and return
611 // true.
612 if (!varFragMapsAreEqual(BBLiveIn, CurrentLiveInEntry->second)) {
613 LLVM_DEBUG(dbgs() << "change=true on meet on " << BB.getName() << "\n");
614 CurrentLiveInEntry->second = std::move(BBLiveIn);
615 return /*Changed=*/true;
616 }
617
618 LLVM_DEBUG(dbgs() << "change=false on meet on " << BB.getName() << "\n");
619 return /*Changed=*/false;
620 }
621
622 void insertMemLoc(BasicBlock &BB, VarLocInsertPt Before, unsigned Var,
623 unsigned StartBit, unsigned EndBit, unsigned Base,
624 DebugLoc DL) {
625 assert(StartBit < EndBit && "Cannot create fragment of size <= 0");
626 if (!Base)
627 return;
628 FragMemLoc Loc;
629 Loc.Var = Var;
630 Loc.OffsetInBits = StartBit;
631 Loc.SizeInBits = EndBit - StartBit;
632 assert(Base && "Expected a non-zero ID for Base address");
633 Loc.Base = Base;
634 Loc.DL = DL;
635 BBInsertBeforeMap[&BB][Before].push_back(Loc);
636 LLVM_DEBUG(dbgs() << "Add mem def for " << Aggregates[Var].first->getName()
637 << " bits [" << StartBit << ", " << EndBit << ")\n");
638 }
639
640 /// Inserts a new dbg def if the interval found when looking up \p StartBit
641 /// in \p FragMap starts before \p StartBit or ends after \p EndBit (which
642 /// indicates - assuming StartBit->EndBit has just been inserted - that the
643 /// slice has been coalesced in the map).
644 void coalesceFragments(BasicBlock &BB, VarLocInsertPt Before, unsigned Var,
645 unsigned StartBit, unsigned EndBit, unsigned Base,
646 DebugLoc DL, const FragsInMemMap &FragMap) {
647 if (!CoalesceAdjacentFragments)
648 return;
649 // We've inserted the location into the map. The map will have coalesced
650 // adjacent intervals (variable fragments) that describe the same memory
651 // location. Use this knowledge to insert a debug location that describes
652 // that coalesced fragment. This may eclipse other locs we've just
653 // inserted. This is okay as redundant locs will be cleaned up later.
654 auto CoalescedFrag = FragMap.find(StartBit);
655 // Bail if no coalescing has taken place.
656 if (CoalescedFrag.start() == StartBit && CoalescedFrag.stop() == EndBit)
657 return;
658
659 LLVM_DEBUG(dbgs() << "- Insert loc for bits " << CoalescedFrag.start()
660 << " to " << CoalescedFrag.stop() << "\n");
661 insertMemLoc(BB, Before, Var, CoalescedFrag.start(), CoalescedFrag.stop(),
662 Base, DL);
663 }
664
665 void addDef(const VarLocInfo &VarLoc, VarLocInsertPt Before, BasicBlock &BB,
666 VarFragMap &LiveSet) {
667 DebugVariable DbgVar = FnVarLocs->getVariable(VarLoc.VariableID);
668 if (skipVariable(DbgVar.getVariable()))
669 return;
670 // Don't bother doing anything for this variables if we know it's fully
671 // promoted. We're only interested in variables that (sometimes) live on
672 // the stack here.
673 if (!VarsWithStackSlot->count(getAggregate(DbgVar)))
674 return;
675 unsigned Var = Aggregates.insert(
676 DebugAggregate(DbgVar.getVariable(), VarLoc.DL.getInlinedAt()));
677
678 // [StartBit: EndBit) are the bits affected by this def.
679 const DIExpression *DIExpr = VarLoc.Expr;
680 unsigned StartBit;
681 unsigned EndBit;
682 if (auto Frag = DIExpr->getFragmentInfo()) {
683 StartBit = Frag->OffsetInBits;
684 EndBit = StartBit + Frag->SizeInBits;
685 } else {
686 assert(static_cast<bool>(DbgVar.getVariable()->getSizeInBits()));
687 StartBit = 0;
688 EndBit = *DbgVar.getVariable()->getSizeInBits();
689 }
690
691 // We will only fill fragments for simple memory-describing dbg.value
692 // intrinsics. If the fragment offset is the same as the offset from the
693 // base pointer, do The Thing, otherwise fall back to normal dbg.value
694 // behaviour. AssignmentTrackingLowering has generated DIExpressions
695 // written in terms of the base pointer.
696 // TODO: Remove this condition since the fragment offset doesn't always
697 // equal the offset from base pointer (e.g. for a SROA-split variable).
698 const auto DerefOffsetInBytes = getDerefOffsetInBytes(DIExpr);
699 const unsigned Base =
700 DerefOffsetInBytes && *DerefOffsetInBytes * 8 == StartBit
701 ? Bases.insert(VarLoc.Values)
702 : 0;
703 LLVM_DEBUG(dbgs() << "DEF " << DbgVar.getVariable()->getName() << " ["
704 << StartBit << ", " << EndBit << "): " << toString(Base)
705 << "\n");
706
707 // First of all, any locs that use mem that are disrupted need reinstating.
708 // Unfortunately, IntervalMap doesn't let us insert intervals that overlap
709 // with existing intervals so this code involves a lot of fiddling around
710 // with intervals to do that manually.
711 auto FragIt = LiveSet.find(Var);
712
713 // Check if the variable does not exist in the map.
714 if (FragIt == LiveSet.end()) {
715 // Add this variable to the BB map.
716 auto P = LiveSet.try_emplace(Var, FragsInMemMap(IntervalMapAlloc));
717 assert(P.second && "Var already in map?");
718 // Add the interval to the fragment map.
719 P.first->second.insert(StartBit, EndBit, Base);
720 return;
721 }
722 // The variable has an entry in the map.
723
724 FragsInMemMap &FragMap = FragIt->second;
725 // First check the easy case: the new fragment `f` doesn't overlap with any
726 // intervals.
727 if (!FragMap.overlaps(StartBit, EndBit)) {
728 LLVM_DEBUG(dbgs() << "- No overlaps\n");
729 FragMap.insert(StartBit, EndBit, Base);
730 coalesceFragments(BB, Before, Var, StartBit, EndBit, Base, VarLoc.DL,
731 FragMap);
732 return;
733 }
734 // There is at least one overlap.
735
736 // Does StartBit intersect an existing fragment?
737 auto FirstOverlap = FragMap.find(StartBit);
738 assert(FirstOverlap != FragMap.end());
739 bool IntersectStart = FirstOverlap.start() < StartBit;
740
741 // Does EndBit intersect an existing fragment?
742 auto LastOverlap = FragMap.find(EndBit);
743 bool IntersectEnd = LastOverlap.valid() && LastOverlap.start() < EndBit;
744
745 // Check if both ends of `f` intersect the same interval `i`.
746 if (IntersectStart && IntersectEnd && FirstOverlap == LastOverlap) {
747 LLVM_DEBUG(dbgs() << "- Intersect single interval @ both ends\n");
748 // Shorten `i` so that there's space to insert `f`.
749 // [ f ]
750 // [ - i - ]
751 // +
752 // [ i ][ f ][ i ]
753
754 // Save values for use after inserting a new interval.
755 auto EndBitOfOverlap = FirstOverlap.stop();
756 unsigned OverlapValue = FirstOverlap.value();
757
758 // Shorten the overlapping interval.
759 FirstOverlap.setStop(StartBit);
760 insertMemLoc(BB, Before, Var, FirstOverlap.start(), StartBit,
761 OverlapValue, VarLoc.DL);
762
763 // Insert a new interval to represent the end part.
764 FragMap.insert(EndBit, EndBitOfOverlap, OverlapValue);
765 insertMemLoc(BB, Before, Var, EndBit, EndBitOfOverlap, OverlapValue,
766 VarLoc.DL);
767
768 // Insert the new (middle) fragment now there is space.
769 FragMap.insert(StartBit, EndBit, Base);
770 } else {
771 // There's an overlap but `f` may not be fully contained within
772 // `i`. Shorten any end-point intersections so that we can then
773 // insert `f`.
774 // [ - f - ]
775 // [ - i - ]
776 // | |
777 // [ i ]
778 // Shorten any end-point intersections.
779 if (IntersectStart) {
780 LLVM_DEBUG(dbgs() << "- Intersect interval at start\n");
781 // Split off at the intersection.
782 FirstOverlap.setStop(StartBit);
783 insertMemLoc(BB, Before, Var, FirstOverlap.start(), StartBit,
784 *FirstOverlap, VarLoc.DL);
785 }
786 // [ - f - ]
787 // [ - i - ]
788 // | |
789 // [ i ]
790 if (IntersectEnd) {
791 LLVM_DEBUG(dbgs() << "- Intersect interval at end\n");
792 // Split off at the intersection.
793 LastOverlap.setStart(EndBit);
794 insertMemLoc(BB, Before, Var, EndBit, LastOverlap.stop(), *LastOverlap,
795 VarLoc.DL);
796 }
797
798 LLVM_DEBUG(dbgs() << "- Erase intervals contained within\n");
799 // FirstOverlap and LastOverlap have been shortened such that they're
800 // no longer overlapping with [StartBit, EndBit). Delete any overlaps
801 // that remain (these will be fully contained within `f`).
802 // [ - f - ] }
803 // [ - i - ] } Intersection shortening that has happened above.
804 // | | }
805 // [ i ] }
806 // -----------------
807 // [i2 ] } Intervals fully contained within `f` get erased.
808 // -----------------
809 // [ - f - ][ i ] } Completed insertion.
810 auto It = FirstOverlap;
811 if (IntersectStart)
812 ++It; // IntersectStart: first overlap has been shortened.
813 while (It.valid() && It.start() >= StartBit && It.stop() <= EndBit) {
814 LLVM_DEBUG(dbgs() << "- Erase " << toString(It));
815 It.erase(); // This increments It after removing the interval.
816 }
817 // We've dealt with all the overlaps now!
818 assert(!FragMap.overlaps(StartBit, EndBit));
819 LLVM_DEBUG(dbgs() << "- Insert DEF into now-empty space\n");
820 FragMap.insert(StartBit, EndBit, Base);
821 }
822
823 coalesceFragments(BB, Before, Var, StartBit, EndBit, Base, VarLoc.DL,
824 FragMap);
825 }
826
827 bool skipVariable(const DILocalVariable *V) { return !V->getSizeInBits(); }
828
829 void process(BasicBlock &BB, VarFragMap &LiveSet) {
830 BBInsertBeforeMap[&BB].clear();
831 for (auto &I : BB) {
832 for (DPValue &DPV : DPValue::filter(I.getDbgValueRange())) {
833 if (const auto *Locs = FnVarLocs->getWedge(&DPV)) {
834 for (const VarLocInfo &Loc : *Locs) {
835 addDef(Loc, &DPV, *I.getParent(), LiveSet);
836 }
837 }
838 }
839 if (const auto *Locs = FnVarLocs->getWedge(&I)) {
840 for (const VarLocInfo &Loc : *Locs) {
841 addDef(Loc, &I, *I.getParent(), LiveSet);
842 }
843 }
844 }
845 }
846
847public:
848 MemLocFragmentFill(Function &Fn,
849 const DenseSet<DebugAggregate> *VarsWithStackSlot,
850 bool CoalesceAdjacentFragments)
851 : Fn(Fn), VarsWithStackSlot(VarsWithStackSlot),
852 CoalesceAdjacentFragments(CoalesceAdjacentFragments) {}
853
854 /// Add variable locations to \p FnVarLocs so that any bits of a variable
855 /// with a memory location have that location explicitly reinstated at each
856 /// subsequent variable location definition that that doesn't overwrite those
857 /// bits. i.e. after a variable location def, insert new defs for the memory
858 /// location with fragments for the difference of "all bits currently in
859 /// memory" and "the fragment of the second def". e.g.
860 ///
861 /// Before:
862 ///
863 /// var x bits 0 to 63: value in memory
864 /// more instructions
865 /// var x bits 0 to 31: value is %0
866 ///
867 /// After:
868 ///
869 /// var x bits 0 to 63: value in memory
870 /// more instructions
871 /// var x bits 0 to 31: value is %0
872 /// var x bits 32 to 61: value in memory ; <-- new loc def
873 ///
874 void run(FunctionVarLocsBuilder *FnVarLocs) {
876 return;
877
878 this->FnVarLocs = FnVarLocs;
879
880 // Prepare for traversal.
881 //
883 std::priority_queue<unsigned int, std::vector<unsigned int>,
884 std::greater<unsigned int>>
885 Worklist;
886 std::priority_queue<unsigned int, std::vector<unsigned int>,
887 std::greater<unsigned int>>
888 Pending;
891 { // Init OrderToBB and BBToOrder.
892 unsigned int RPONumber = 0;
893 for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
894 OrderToBB[RPONumber] = *RI;
895 BBToOrder[*RI] = RPONumber;
896 Worklist.push(RPONumber);
897 ++RPONumber;
898 }
899 LiveIn.init(RPONumber);
900 LiveOut.init(RPONumber);
901 }
902
903 // Perform the traversal.
904 //
905 // This is a standard "intersect of predecessor outs" dataflow problem. To
906 // solve it, we perform meet() and process() using the two worklist method
907 // until the LiveIn data for each block becomes unchanging.
908 //
909 // This dataflow is essentially working on maps of sets and at each meet we
910 // intersect the maps and the mapped sets. So, initialized live-in maps
911 // monotonically decrease in value throughout the dataflow.
913 while (!Worklist.empty() || !Pending.empty()) {
914 // We track what is on the pending worklist to avoid inserting the same
915 // thing twice. We could avoid this with a custom priority queue, but
916 // this is probably not worth it.
918 LLVM_DEBUG(dbgs() << "Processing Worklist\n");
919 while (!Worklist.empty()) {
920 BasicBlock *BB = OrderToBB[Worklist.top()];
921 LLVM_DEBUG(dbgs() << "\nPop BB " << BB->getName() << "\n");
922 Worklist.pop();
923 bool InChanged = meet(*BB, Visited);
924 // Always consider LiveIn changed on the first visit.
925 InChanged |= Visited.insert(BB).second;
926 if (InChanged) {
928 << BB->getName() << " has new InLocs, process it\n");
929 // Mutate a copy of LiveIn while processing BB. Once we've processed
930 // the terminator LiveSet is the LiveOut set for BB.
931 // This is an expensive copy!
932 VarFragMap LiveSet = LiveIn[BB];
933
934 // Process the instructions in the block.
935 process(*BB, LiveSet);
936
937 // Relatively expensive check: has anything changed in LiveOut for BB?
938 if (!varFragMapsAreEqual(LiveOut[BB], LiveSet)) {
939 LLVM_DEBUG(dbgs() << BB->getName()
940 << " has new OutLocs, add succs to worklist: [ ");
941 LiveOut[BB] = std::move(LiveSet);
942 for (auto I = succ_begin(BB), E = succ_end(BB); I != E; I++) {
943 if (OnPending.insert(*I).second) {
944 LLVM_DEBUG(dbgs() << I->getName() << " ");
945 Pending.push(BBToOrder[*I]);
946 }
947 }
948 LLVM_DEBUG(dbgs() << "]\n");
949 }
950 }
951 }
952 Worklist.swap(Pending);
953 // At this point, pending must be empty, since it was just the empty
954 // worklist
955 assert(Pending.empty() && "Pending should be empty");
956 }
957
958 // Insert new location defs.
959 for (auto &Pair : BBInsertBeforeMap) {
960 InsertMap &Map = Pair.second;
961 for (auto &Pair : Map) {
962 auto InsertBefore = Pair.first;
963 assert(InsertBefore && "should never be null");
964 auto FragMemLocs = Pair.second;
965 auto &Ctx = Fn.getContext();
966
967 for (auto &FragMemLoc : FragMemLocs) {
968 DIExpression *Expr = DIExpression::get(Ctx, std::nullopt);
969 if (FragMemLoc.SizeInBits !=
970 *Aggregates[FragMemLoc.Var].first->getSizeInBits())
972 Expr, FragMemLoc.OffsetInBits, FragMemLoc.SizeInBits);
974 FragMemLoc.OffsetInBits / 8);
975 DebugVariable Var(Aggregates[FragMemLoc.Var].first, Expr,
976 FragMemLoc.DL.getInlinedAt());
977 FnVarLocs->addVarLoc(InsertBefore, Var, Expr, FragMemLoc.DL,
978 Bases[FragMemLoc.Base]);
979 }
980 }
981 }
982 }
983};
984
985/// AssignmentTrackingLowering encapsulates a dataflow analysis over a function
986/// that interprets assignment tracking debug info metadata and stores in IR to
987/// create a map of variable locations.
988class AssignmentTrackingLowering {
989public:
990 /// The kind of location in use for a variable, where Mem is the stack home,
991 /// Val is an SSA value or const, and None means that there is not one single
992 /// kind (either because there are multiple or because there is none; it may
993 /// prove useful to split this into two values in the future).
994 ///
995 /// LocKind is a join-semilattice with the partial order:
996 /// None > Mem, Val
997 ///
998 /// i.e.
999 /// join(Mem, Mem) = Mem
1000 /// join(Val, Val) = Val
1001 /// join(Mem, Val) = None
1002 /// join(None, Mem) = None
1003 /// join(None, Val) = None
1004 /// join(None, None) = None
1005 ///
1006 /// Note: the order is not `None > Val > Mem` because we're using DIAssignID
1007 /// to name assignments and are not tracking the actual stored values.
1008 /// Therefore currently there's no way to ensure that Mem values and Val
1009 /// values are the same. This could be a future extension, though it's not
1010 /// clear that many additional locations would be recovered that way in
1011 /// practice as the likelihood of this sitation arising naturally seems
1012 /// incredibly low.
1013 enum class LocKind { Mem, Val, None };
1014
1015 /// An abstraction of the assignment of a value to a variable or memory
1016 /// location.
1017 ///
1018 /// An Assignment is Known or NoneOrPhi. A Known Assignment means we have a
1019 /// DIAssignID ptr that represents it. NoneOrPhi means that we don't (or
1020 /// can't) know the ID of the last assignment that took place.
1021 ///
1022 /// The Status of the Assignment (Known or NoneOrPhi) is another
1023 /// join-semilattice. The partial order is:
1024 /// NoneOrPhi > Known {id_0, id_1, ...id_N}
1025 ///
1026 /// i.e. for all values x and y where x != y:
1027 /// join(x, x) = x
1028 /// join(x, y) = NoneOrPhi
1030 struct Assignment {
1031 enum S { Known, NoneOrPhi } Status;
1032 /// ID of the assignment. nullptr if Status is not Known.
1033 DIAssignID *ID;
1034 /// The dbg.assign that marks this dbg-def. Mem-defs don't use this field.
1035 /// May be nullptr.
1036 AssignRecord Source;
1037
1038 bool isSameSourceAssignment(const Assignment &Other) const {
1039 // Don't include Source in the equality check. Assignments are
1040 // defined by their ID, not debug intrinsic(s).
1041 return std::tie(Status, ID) == std::tie(Other.Status, Other.ID);
1042 }
1043 void dump(raw_ostream &OS) {
1044 static const char *LUT[] = {"Known", "NoneOrPhi"};
1045 OS << LUT[Status] << "(id=";
1046 if (ID)
1047 OS << ID;
1048 else
1049 OS << "null";
1050 OS << ", s=";
1051 if (Source.isNull())
1052 OS << "null";
1053 else if (isa<DbgAssignIntrinsic *>(Source))
1054 OS << Source.get<DbgAssignIntrinsic *>();
1055 else
1056 OS << Source.get<DPValue *>();
1057 OS << ")";
1058 }
1059
1060 static Assignment make(DIAssignID *ID, DbgAssignIntrinsic *Source) {
1061 return Assignment(Known, ID, Source);
1062 }
1063 static Assignment make(DIAssignID *ID, DPValue *Source) {
1064 assert(Source->isDbgAssign() &&
1065 "Cannot make an assignment from a non-assign DPValue");
1066 return Assignment(Known, ID, Source);
1067 }
1068 static Assignment make(DIAssignID *ID, AssignRecord Source) {
1069 return Assignment(Known, ID, Source);
1070 }
1071 static Assignment makeFromMemDef(DIAssignID *ID) {
1072 return Assignment(Known, ID);
1073 }
1074 static Assignment makeNoneOrPhi() { return Assignment(NoneOrPhi, nullptr); }
1075 // Again, need a Top value?
1076 Assignment() : Status(NoneOrPhi), ID(nullptr) {} // Can we delete this?
1077 Assignment(S Status, DIAssignID *ID) : Status(Status), ID(ID) {
1078 // If the Status is Known then we expect there to be an assignment ID.
1079 assert(Status == NoneOrPhi || ID);
1080 }
1081 Assignment(S Status, DIAssignID *ID, DbgAssignIntrinsic *Source)
1082 : Status(Status), ID(ID), Source(Source) {
1083 // If the Status is Known then we expect there to be an assignment ID.
1084 assert(Status == NoneOrPhi || ID);
1085 }
1086 Assignment(S Status, DIAssignID *ID, DPValue *Source)
1087 : Status(Status), ID(ID), Source(Source) {
1088 // If the Status is Known then we expect there to be an assignment ID.
1089 assert(Status == NoneOrPhi || ID);
1090 }
1091 Assignment(S Status, DIAssignID *ID, AssignRecord Source)
1092 : Status(Status), ID(ID), Source(Source) {
1093 // If the Status is Known then we expect there to be an assignment ID.
1094 assert(Status == NoneOrPhi || ID);
1095 }
1096 };
1097
1098 using AssignmentMap = SmallVector<Assignment>;
1101 using UntaggedStoreAssignmentMap =
1102 DenseMap<const Instruction *,
1104
1105private:
1106 /// The highest numbered VariableID for partially promoted variables plus 1,
1107 /// the values for which start at 1.
1108 unsigned TrackedVariablesVectorSize = 0;
1109 /// Map a variable to the set of variables that it fully contains.
1110 OverlapMap VarContains;
1111 /// Map untagged stores to the variable fragments they assign to. Used by
1112 /// processUntaggedInstruction.
1113 UntaggedStoreAssignmentMap UntaggedStoreVars;
1114
1115 // Machinery to defer inserting dbg.values.
1117 InstInsertMap InsertBeforeMap;
1118 /// Clear the location definitions currently cached for insertion after /p
1119 /// After.
1120 void resetInsertionPoint(Instruction &After);
1121 void resetInsertionPoint(DPValue &After);
1122
1123 // emitDbgValue can be called with:
1124 // Source=[AssignRecord|DbgValueInst*|DbgAssignIntrinsic*|DPValue*]
1125 // Since AssignRecord can be cast to one of the latter two types, and all
1126 // other types have a shared interface, we use a template to handle the latter
1127 // three types, and an explicit overload for AssignRecord that forwards to
1128 // the template version with the right type.
1129 void emitDbgValue(LocKind Kind, AssignRecord Source, VarLocInsertPt After);
1130 template <typename T>
1131 void emitDbgValue(LocKind Kind, const T Source, VarLocInsertPt After);
1132
1133 static bool mapsAreEqual(const BitVector &Mask, const AssignmentMap &A,
1134 const AssignmentMap &B) {
1135 return llvm::all_of(Mask.set_bits(), [&](unsigned VarID) {
1136 return A[VarID].isSameSourceAssignment(B[VarID]);
1137 });
1138 }
1139
1140 /// Represents the stack and debug assignments in a block. Used to describe
1141 /// the live-in and live-out values for blocks, as well as the "current"
1142 /// value as we process each instruction in a block.
1143 struct BlockInfo {
1144 /// The set of variables (VariableID) being tracked in this block.
1145 BitVector VariableIDsInBlock;
1146 /// Dominating assignment to memory for each variable, indexed by
1147 /// VariableID.
1148 AssignmentMap StackHomeValue;
1149 /// Dominating assignemnt to each variable, indexed by VariableID.
1150 AssignmentMap DebugValue;
1151 /// Location kind for each variable. LiveLoc indicates whether the
1152 /// dominating assignment in StackHomeValue (LocKind::Mem), DebugValue
1153 /// (LocKind::Val), or neither (LocKind::None) is valid, in that order of
1154 /// preference. This cannot be derived by inspecting DebugValue and
1155 /// StackHomeValue due to the fact that there's no distinction in
1156 /// Assignment (the class) between whether an assignment is unknown or a
1157 /// merge of multiple assignments (both are Status::NoneOrPhi). In other
1158 /// words, the memory location may well be valid while both DebugValue and
1159 /// StackHomeValue contain Assignments that have a Status of NoneOrPhi.
1160 /// Indexed by VariableID.
1161 LocMap LiveLoc;
1162
1163 public:
1164 enum AssignmentKind { Stack, Debug };
1165 const AssignmentMap &getAssignmentMap(AssignmentKind Kind) const {
1166 switch (Kind) {
1167 case Stack:
1168 return StackHomeValue;
1169 case Debug:
1170 return DebugValue;
1171 }
1172 llvm_unreachable("Unknown AssignmentKind");
1173 }
1174 AssignmentMap &getAssignmentMap(AssignmentKind Kind) {
1175 return const_cast<AssignmentMap &>(
1176 const_cast<const BlockInfo *>(this)->getAssignmentMap(Kind));
1177 }
1178
1179 bool isVariableTracked(VariableID Var) const {
1180 return VariableIDsInBlock[static_cast<unsigned>(Var)];
1181 }
1182
1183 const Assignment &getAssignment(AssignmentKind Kind, VariableID Var) const {
1184 assert(isVariableTracked(Var) && "Var not tracked in block");
1185 return getAssignmentMap(Kind)[static_cast<unsigned>(Var)];
1186 }
1187
1188 LocKind getLocKind(VariableID Var) const {
1189 assert(isVariableTracked(Var) && "Var not tracked in block");
1190 return LiveLoc[static_cast<unsigned>(Var)];
1191 }
1192
1193 /// Set LocKind for \p Var only: does not set LocKind for VariableIDs of
1194 /// fragments contained win \p Var.
1195 void setLocKind(VariableID Var, LocKind K) {
1196 VariableIDsInBlock.set(static_cast<unsigned>(Var));
1197 LiveLoc[static_cast<unsigned>(Var)] = K;
1198 }
1199
1200 /// Set the assignment in the \p Kind assignment map for \p Var only: does
1201 /// not set the assignment for VariableIDs of fragments contained win \p
1202 /// Var.
1203 void setAssignment(AssignmentKind Kind, VariableID Var,
1204 const Assignment &AV) {
1205 VariableIDsInBlock.set(static_cast<unsigned>(Var));
1206 getAssignmentMap(Kind)[static_cast<unsigned>(Var)] = AV;
1207 }
1208
1209 /// Return true if there is an assignment matching \p AV in the \p Kind
1210 /// assignment map. Does consider assignments for VariableIDs of fragments
1211 /// contained win \p Var.
1212 bool hasAssignment(AssignmentKind Kind, VariableID Var,
1213 const Assignment &AV) const {
1214 if (!isVariableTracked(Var))
1215 return false;
1216 return AV.isSameSourceAssignment(getAssignment(Kind, Var));
1217 }
1218
1219 /// Compare every element in each map to determine structural equality
1220 /// (slow).
1221 bool operator==(const BlockInfo &Other) const {
1222 return VariableIDsInBlock == Other.VariableIDsInBlock &&
1223 LiveLoc == Other.LiveLoc &&
1224 mapsAreEqual(VariableIDsInBlock, StackHomeValue,
1225 Other.StackHomeValue) &&
1226 mapsAreEqual(VariableIDsInBlock, DebugValue, Other.DebugValue);
1227 }
1228 bool operator!=(const BlockInfo &Other) const { return !(*this == Other); }
1229 bool isValid() {
1230 return LiveLoc.size() == DebugValue.size() &&
1231 LiveLoc.size() == StackHomeValue.size();
1232 }
1233
1234 /// Clear everything and initialise with ⊤-values for all variables.
1235 void init(int NumVars) {
1236 StackHomeValue.clear();
1237 DebugValue.clear();
1238 LiveLoc.clear();
1239 VariableIDsInBlock = BitVector(NumVars);
1240 StackHomeValue.insert(StackHomeValue.begin(), NumVars,
1241 Assignment::makeNoneOrPhi());
1242 DebugValue.insert(DebugValue.begin(), NumVars,
1243 Assignment::makeNoneOrPhi());
1244 LiveLoc.insert(LiveLoc.begin(), NumVars, LocKind::None);
1245 }
1246
1247 /// Helper for join.
1248 template <typename ElmtType, typename FnInputType>
1249 static void joinElmt(int Index, SmallVector<ElmtType> &Target,
1250 const SmallVector<ElmtType> &A,
1251 const SmallVector<ElmtType> &B,
1252 ElmtType (*Fn)(FnInputType, FnInputType)) {
1253 Target[Index] = Fn(A[Index], B[Index]);
1254 }
1255
1256 /// See comment for AssignmentTrackingLowering::joinBlockInfo.
1257 static BlockInfo join(const BlockInfo &A, const BlockInfo &B, int NumVars) {
1258 // Join A and B.
1259 //
1260 // Intersect = join(a, b) for a in A, b in B where Var(a) == Var(b)
1261 // Difference = join(x, ⊤) for x where Var(x) is in A xor B
1262 // Join = Intersect ∪ Difference
1263 //
1264 // This is achieved by performing a join on elements from A and B with
1265 // variables common to both A and B (join elements indexed by var
1266 // intersect), then adding ⊤-value elements for vars in A xor B. The
1267 // latter part is equivalent to performing join on elements with variables
1268 // in A xor B with the ⊤-value for the map element since join(x, ⊤) = ⊤.
1269 // BlockInfo::init initializes all variable entries to the ⊤ value so we
1270 // don't need to explicitly perform that step as Join.VariableIDsInBlock
1271 // is set to the union of the variables in A and B at the end of this
1272 // function.
1273 BlockInfo Join;
1274 Join.init(NumVars);
1275
1276 BitVector Intersect = A.VariableIDsInBlock;
1277 Intersect &= B.VariableIDsInBlock;
1278
1279 for (auto VarID : Intersect.set_bits()) {
1280 joinElmt(VarID, Join.LiveLoc, A.LiveLoc, B.LiveLoc, joinKind);
1281 joinElmt(VarID, Join.DebugValue, A.DebugValue, B.DebugValue,
1282 joinAssignment);
1283 joinElmt(VarID, Join.StackHomeValue, A.StackHomeValue, B.StackHomeValue,
1284 joinAssignment);
1285 }
1286
1287 Join.VariableIDsInBlock = A.VariableIDsInBlock;
1288 Join.VariableIDsInBlock |= B.VariableIDsInBlock;
1289 assert(Join.isValid());
1290 return Join;
1291 }
1292 };
1293
1294 Function &Fn;
1295 const DataLayout &Layout;
1296 const DenseSet<DebugAggregate> *VarsWithStackSlot;
1297 FunctionVarLocsBuilder *FnVarLocs;
1300
1301 /// Helper for process methods to track variables touched each frame.
1302 DenseSet<VariableID> VarsTouchedThisFrame;
1303
1304 /// The set of variables that sometimes are not located in their stack home.
1305 DenseSet<DebugAggregate> NotAlwaysStackHomed;
1306
1307 VariableID getVariableID(const DebugVariable &Var) {
1308 return static_cast<VariableID>(FnVarLocs->insertVariable(Var));
1309 }
1310
1311 /// Join the LiveOut values of preds that are contained in \p Visited into
1312 /// LiveIn[BB]. Return True if LiveIn[BB] has changed as a result. LiveIn[BB]
1313 /// values monotonically increase. See the @link joinMethods join methods
1314 /// @endlink documentation for more info.
1315 bool join(const BasicBlock &BB, const SmallPtrSet<BasicBlock *, 16> &Visited);
1316 ///@name joinMethods
1317 /// Functions that implement `join` (the least upper bound) for the
1318 /// join-semilattice types used in the dataflow. There is an explicit bottom
1319 /// value (⊥) for some types and and explicit top value (⊤) for all types.
1320 /// By definition:
1321 ///
1322 /// Join(A, B) >= A && Join(A, B) >= B
1323 /// Join(A, ⊥) = A
1324 /// Join(A, ⊤) = ⊤
1325 ///
1326 /// These invariants are important for monotonicity.
1327 ///
1328 /// For the map-type functions, all unmapped keys in an empty map are
1329 /// associated with a bottom value (⊥). This represents their values being
1330 /// unknown. Unmapped keys in non-empty maps (joining two maps with a key
1331 /// only present in one) represents either a variable going out of scope or
1332 /// dropped debug info. It is assumed the key is associated with a top value
1333 /// (⊤) in this case (unknown location / assignment).
1334 ///@{
1335 static LocKind joinKind(LocKind A, LocKind B);
1336 static Assignment joinAssignment(const Assignment &A, const Assignment &B);
1337 BlockInfo joinBlockInfo(const BlockInfo &A, const BlockInfo &B);
1338 ///@}
1339
1340 /// Process the instructions in \p BB updating \p LiveSet along the way. \p
1341 /// LiveSet must be initialized with the current live-in locations before
1342 /// calling this.
1343 void process(BasicBlock &BB, BlockInfo *LiveSet);
1344 ///@name processMethods
1345 /// Methods to process instructions in order to update the LiveSet (current
1346 /// location information).
1347 ///@{
1348 void processNonDbgInstruction(Instruction &I, BlockInfo *LiveSet);
1349 void processDbgInstruction(DbgInfoIntrinsic &I, BlockInfo *LiveSet);
1350 /// Update \p LiveSet after encountering an instruction with a DIAssignID
1351 /// attachment, \p I.
1352 void processTaggedInstruction(Instruction &I, BlockInfo *LiveSet);
1353 /// Update \p LiveSet after encountering an instruciton without a DIAssignID
1354 /// attachment, \p I.
1355 void processUntaggedInstruction(Instruction &I, BlockInfo *LiveSet);
1356 void processDbgAssign(AssignRecord Assign, BlockInfo *LiveSet);
1357 void processDPValue(DPValue &DPV, BlockInfo *LiveSet);
1358 void processDbgValue(PointerUnion<DbgValueInst *, DPValue *> DbgValueRecord,
1359 BlockInfo *LiveSet);
1360 /// Add an assignment to memory for the variable /p Var.
1361 void addMemDef(BlockInfo *LiveSet, VariableID Var, const Assignment &AV);
1362 /// Add an assignment to the variable /p Var.
1363 void addDbgDef(BlockInfo *LiveSet, VariableID Var, const Assignment &AV);
1364 ///@}
1365
1366 /// Set the LocKind for \p Var.
1367 void setLocKind(BlockInfo *LiveSet, VariableID Var, LocKind K);
1368 /// Get the live LocKind for a \p Var. Requires addMemDef or addDbgDef to
1369 /// have been called for \p Var first.
1370 LocKind getLocKind(BlockInfo *LiveSet, VariableID Var);
1371 /// Return true if \p Var has an assignment in \p M matching \p AV.
1372 bool hasVarWithAssignment(BlockInfo *LiveSet, BlockInfo::AssignmentKind Kind,
1373 VariableID Var, const Assignment &AV);
1374 /// Return the set of VariableIDs corresponding the fragments contained fully
1375 /// within the variable/fragment \p Var.
1376 ArrayRef<VariableID> getContainedFragments(VariableID Var) const;
1377
1378 /// Mark \p Var as having been touched this frame. Note, this applies only
1379 /// to the exact fragment \p Var and not to any fragments contained within.
1380 void touchFragment(VariableID Var);
1381
1382 /// Emit info for variables that are fully promoted.
1383 bool emitPromotedVarLocs(FunctionVarLocsBuilder *FnVarLocs);
1384
1385public:
1386 AssignmentTrackingLowering(Function &Fn, const DataLayout &Layout,
1387 const DenseSet<DebugAggregate> *VarsWithStackSlot)
1388 : Fn(Fn), Layout(Layout), VarsWithStackSlot(VarsWithStackSlot) {}
1389 /// Run the analysis, adding variable location info to \p FnVarLocs. Returns
1390 /// true if any variable locations have been added to FnVarLocs.
1391 bool run(FunctionVarLocsBuilder *FnVarLocs);
1392};
1393} // namespace
1394
1396AssignmentTrackingLowering::getContainedFragments(VariableID Var) const {
1397 auto R = VarContains.find(Var);
1398 if (R == VarContains.end())
1399 return std::nullopt;
1400 return R->second;
1401}
1402
1403void AssignmentTrackingLowering::touchFragment(VariableID Var) {
1404 VarsTouchedThisFrame.insert(Var);
1405}
1406
1407void AssignmentTrackingLowering::setLocKind(BlockInfo *LiveSet, VariableID Var,
1408 LocKind K) {
1409 auto SetKind = [this](BlockInfo *LiveSet, VariableID Var, LocKind K) {
1410 LiveSet->setLocKind(Var, K);
1411 touchFragment(Var);
1412 };
1413 SetKind(LiveSet, Var, K);
1414
1415 // Update the LocKind for all fragments contained within Var.
1416 for (VariableID Frag : getContainedFragments(Var))
1417 SetKind(LiveSet, Frag, K);
1418}
1419
1420AssignmentTrackingLowering::LocKind
1421AssignmentTrackingLowering::getLocKind(BlockInfo *LiveSet, VariableID Var) {
1422 return LiveSet->getLocKind(Var);
1423}
1424
1425void AssignmentTrackingLowering::addMemDef(BlockInfo *LiveSet, VariableID Var,
1426 const Assignment &AV) {
1427 LiveSet->setAssignment(BlockInfo::Stack, Var, AV);
1428
1429 // Use this assigment for all fragments contained within Var, but do not
1430 // provide a Source because we cannot convert Var's value to a value for the
1431 // fragment.
1432 Assignment FragAV = AV;
1433 FragAV.Source = nullptr;
1434 for (VariableID Frag : getContainedFragments(Var))
1435 LiveSet->setAssignment(BlockInfo::Stack, Frag, FragAV);
1436}
1437
1438void AssignmentTrackingLowering::addDbgDef(BlockInfo *LiveSet, VariableID Var,
1439 const Assignment &AV) {
1440 LiveSet->setAssignment(BlockInfo::Debug, Var, AV);
1441
1442 // Use this assigment for all fragments contained within Var, but do not
1443 // provide a Source because we cannot convert Var's value to a value for the
1444 // fragment.
1445 Assignment FragAV = AV;
1446 FragAV.Source = nullptr;
1447 for (VariableID Frag : getContainedFragments(Var))
1448 LiveSet->setAssignment(BlockInfo::Debug, Frag, FragAV);
1449}
1450
1452 return cast<DIAssignID>(I.getMetadata(LLVMContext::MD_DIAssignID));
1453}
1454
1456 return cast<DIAssignID>(DAI.getAssignID());
1457}
1458
1460 assert(DPV.isDbgAssign() &&
1461 "Cannot get a DIAssignID from a non-assign DPValue!");
1462 return DPV.getAssignID();
1463}
1464
1465/// Return true if \p Var has an assignment in \p M matching \p AV.
1466bool AssignmentTrackingLowering::hasVarWithAssignment(
1467 BlockInfo *LiveSet, BlockInfo::AssignmentKind Kind, VariableID Var,
1468 const Assignment &AV) {
1469 if (!LiveSet->hasAssignment(Kind, Var, AV))
1470 return false;
1471
1472 // Check all the frags contained within Var as these will have all been
1473 // mapped to AV at the last store to Var.
1474 for (VariableID Frag : getContainedFragments(Var))
1475 if (!LiveSet->hasAssignment(Kind, Frag, AV))
1476 return false;
1477 return true;
1478}
1479
1480#ifndef NDEBUG
1481const char *locStr(AssignmentTrackingLowering::LocKind Loc) {
1482 using LocKind = AssignmentTrackingLowering::LocKind;
1483 switch (Loc) {
1484 case LocKind::Val:
1485 return "Val";
1486 case LocKind::Mem:
1487 return "Mem";
1488 case LocKind::None:
1489 return "None";
1490 };
1491 llvm_unreachable("unknown LocKind");
1492}
1493#endif
1494
1496 auto NextIt = ++(DPV->getIterator());
1497 if (NextIt == DPV->getMarker()->getDbgValueRange().end())
1498 return DPV->getMarker()->MarkedInstr;
1499 return &*NextIt;
1500}
1502 const Instruction *Next = Inst->getNextNode();
1503 if (!Next->hasDbgValues())
1504 return Next;
1505 return &*Next->getDbgValueRange().begin();
1506}
1508 if (isa<const Instruction *>(InsertPt))
1509 return getNextNode(cast<const Instruction *>(InsertPt));
1510 return getNextNode(cast<const DbgRecord *>(InsertPt));
1511}
1512
1514 return cast<DbgAssignIntrinsic>(DVI);
1515}
1516
1518 assert(DPV->isDbgAssign() &&
1519 "Attempted to cast non-assign DPValue to DPVAssign.");
1520 return DPV;
1521}
1522
1523void AssignmentTrackingLowering::emitDbgValue(
1524 AssignmentTrackingLowering::LocKind Kind,
1526 if (isa<DbgAssignIntrinsic *>(Source))
1527 emitDbgValue(Kind, cast<DbgAssignIntrinsic *>(Source), After);
1528 else
1529 emitDbgValue(Kind, cast<DPValue *>(Source), After);
1530}
1531template <typename T>
1532void AssignmentTrackingLowering::emitDbgValue(
1533 AssignmentTrackingLowering::LocKind Kind, const T Source,
1535
1536 DILocation *DL = Source->getDebugLoc();
1537 auto Emit = [this, Source, After, DL](Metadata *Val, DIExpression *Expr) {
1538 assert(Expr);
1539 if (!Val)
1541 PoisonValue::get(Type::getInt1Ty(Source->getContext())));
1542
1543 // Find a suitable insert point.
1544 auto InsertBefore = getNextNode(After);
1545 assert(InsertBefore && "Shouldn't be inserting after a terminator");
1546
1547 VariableID Var = getVariableID(DebugVariable(Source));
1548 VarLocInfo VarLoc;
1549 VarLoc.VariableID = static_cast<VariableID>(Var);
1550 VarLoc.Expr = Expr;
1551 VarLoc.Values = RawLocationWrapper(Val);
1552 VarLoc.DL = DL;
1553 // Insert it into the map for later.
1554 InsertBeforeMap[InsertBefore].push_back(VarLoc);
1555 };
1556
1557 // NOTE: This block can mutate Kind.
1558 if (Kind == LocKind::Mem) {
1559 const auto *Assign = CastToDbgAssign(Source);
1560 // Check the address hasn't been dropped (e.g. the debug uses may not have
1561 // been replaced before deleting a Value).
1562 if (Assign->isKillAddress()) {
1563 // The address isn't valid so treat this as a non-memory def.
1564 Kind = LocKind::Val;
1565 } else {
1566 Value *Val = Assign->getAddress();
1567 DIExpression *Expr = Assign->getAddressExpression();
1568 assert(!Expr->getFragmentInfo() &&
1569 "fragment info should be stored in value-expression only");
1570 // Copy the fragment info over from the value-expression to the new
1571 // DIExpression.
1572 if (auto OptFragInfo = Source->getExpression()->getFragmentInfo()) {
1573 auto FragInfo = *OptFragInfo;
1575 Expr, FragInfo.OffsetInBits, FragInfo.SizeInBits);
1576 }
1577 // The address-expression has an implicit deref, add it now.
1578 std::tie(Val, Expr) =
1579 walkToAllocaAndPrependOffsetDeref(Layout, Val, Expr);
1580 Emit(ValueAsMetadata::get(Val), Expr);
1581 return;
1582 }
1583 }
1584
1585 if (Kind == LocKind::Val) {
1586 Emit(Source->getRawLocation(), Source->getExpression());
1587 return;
1588 }
1589
1590 if (Kind == LocKind::None) {
1591 Emit(nullptr, Source->getExpression());
1592 return;
1593 }
1594}
1595
1596void AssignmentTrackingLowering::processNonDbgInstruction(
1597 Instruction &I, AssignmentTrackingLowering::BlockInfo *LiveSet) {
1598 if (I.hasMetadata(LLVMContext::MD_DIAssignID))
1599 processTaggedInstruction(I, LiveSet);
1600 else
1601 processUntaggedInstruction(I, LiveSet);
1602}
1603
1604void AssignmentTrackingLowering::processUntaggedInstruction(
1605 Instruction &I, AssignmentTrackingLowering::BlockInfo *LiveSet) {
1606 // Interpret stack stores that are not tagged as an assignment in memory for
1607 // the variables associated with that address. These stores may not be tagged
1608 // because a) the store cannot be represented using dbg.assigns (non-const
1609 // length or offset) or b) the tag was accidentally dropped during
1610 // optimisations. For these stores we fall back to assuming that the stack
1611 // home is a valid location for the variables. The benefit is that this
1612 // prevents us missing an assignment and therefore incorrectly maintaining
1613 // earlier location definitions, and in many cases it should be a reasonable
1614 // assumption. However, this will occasionally lead to slight
1615 // inaccuracies. The value of a hoisted untagged store will be visible
1616 // "early", for example.
1617 assert(!I.hasMetadata(LLVMContext::MD_DIAssignID));
1618 auto It = UntaggedStoreVars.find(&I);
1619 if (It == UntaggedStoreVars.end())
1620 return; // No variables associated with the store destination.
1621
1622 LLVM_DEBUG(dbgs() << "processUntaggedInstruction on UNTAGGED INST " << I
1623 << "\n");
1624 // Iterate over the variables that this store affects, add a NoneOrPhi dbg
1625 // and mem def, set lockind to Mem, and emit a location def for each.
1626 for (auto [Var, Info] : It->second) {
1627 // This instruction is treated as both a debug and memory assignment,
1628 // meaning the memory location should be used. We don't have an assignment
1629 // ID though so use Assignment::makeNoneOrPhi() to create an imaginary one.
1630 addMemDef(LiveSet, Var, Assignment::makeNoneOrPhi());
1631 addDbgDef(LiveSet, Var, Assignment::makeNoneOrPhi());
1632 setLocKind(LiveSet, Var, LocKind::Mem);
1633 LLVM_DEBUG(dbgs() << " setting Stack LocKind to: " << locStr(LocKind::Mem)
1634 << "\n");
1635 // Build the dbg location def to insert.
1636 //
1637 // DIExpression: Add fragment and offset.
1638 DebugVariable V = FnVarLocs->getVariable(Var);
1639 DIExpression *DIE = DIExpression::get(I.getContext(), std::nullopt);
1640 if (auto Frag = V.getFragment()) {
1641 auto R = DIExpression::createFragmentExpression(DIE, Frag->OffsetInBits,
1642 Frag->SizeInBits);
1643 assert(R && "unexpected createFragmentExpression failure");
1644 DIE = *R;
1645 }
1647 if (Info.OffsetInBits)
1648 Ops = {dwarf::DW_OP_plus_uconst, Info.OffsetInBits / 8};
1649 Ops.push_back(dwarf::DW_OP_deref);
1650 DIE = DIExpression::prependOpcodes(DIE, Ops, /*StackValue=*/false,
1651 /*EntryValue=*/false);
1652 // Find a suitable insert point, before the next instruction or DPValue
1653 // after I.
1654 auto InsertBefore = getNextNode(&I);
1655 assert(InsertBefore && "Shouldn't be inserting after a terminator");
1656
1657 // Get DILocation for this unrecorded assignment.
1658 DILocation *InlinedAt = const_cast<DILocation *>(V.getInlinedAt());
1659 const DILocation *DILoc = DILocation::get(
1660 Fn.getContext(), 0, 0, V.getVariable()->getScope(), InlinedAt);
1661
1662 VarLocInfo VarLoc;
1663 VarLoc.VariableID = static_cast<VariableID>(Var);
1664 VarLoc.Expr = DIE;
1665 VarLoc.Values = RawLocationWrapper(
1666 ValueAsMetadata::get(const_cast<AllocaInst *>(Info.Base)));
1667 VarLoc.DL = DILoc;
1668 // 3. Insert it into the map for later.
1669 InsertBeforeMap[InsertBefore].push_back(VarLoc);
1670 }
1671}
1672
1673void AssignmentTrackingLowering::processTaggedInstruction(
1674 Instruction &I, AssignmentTrackingLowering::BlockInfo *LiveSet) {
1675 auto Linked = at::getAssignmentMarkers(&I);
1676 auto LinkedDPAssigns = at::getDPVAssignmentMarkers(&I);
1677 // No dbg.assign intrinsics linked.
1678 // FIXME: All vars that have a stack slot this store modifies that don't have
1679 // a dbg.assign linked to it should probably treat this like an untagged
1680 // store.
1681 if (Linked.empty() && LinkedDPAssigns.empty())
1682 return;
1683
1684 LLVM_DEBUG(dbgs() << "processTaggedInstruction on " << I << "\n");
1685 auto ProcessLinkedAssign = [&](auto *Assign) {
1686 VariableID Var = getVariableID(DebugVariable(Assign));
1687 // Something has gone wrong if VarsWithStackSlot doesn't contain a variable
1688 // that is linked to a store.
1689 assert(VarsWithStackSlot->count(getAggregate(Assign)) &&
1690 "expected Assign's variable to have stack slot");
1691
1692 Assignment AV = Assignment::makeFromMemDef(getIDFromInst(I));
1693 addMemDef(LiveSet, Var, AV);
1694
1695 LLVM_DEBUG(dbgs() << " linked to " << *Assign << "\n");
1696 LLVM_DEBUG(dbgs() << " LiveLoc " << locStr(getLocKind(LiveSet, Var))
1697 << " -> ");
1698
1699 // The last assignment to the stack is now AV. Check if the last debug
1700 // assignment has a matching Assignment.
1701 if (hasVarWithAssignment(LiveSet, BlockInfo::Debug, Var, AV)) {
1702 // The StackHomeValue and DebugValue for this variable match so we can
1703 // emit a stack home location here.
1704 LLVM_DEBUG(dbgs() << "Mem, Stack matches Debug program\n";);
1705 LLVM_DEBUG(dbgs() << " Stack val: "; AV.dump(dbgs()); dbgs() << "\n");
1706 LLVM_DEBUG(dbgs() << " Debug val: ";
1707 LiveSet->DebugValue[static_cast<unsigned>(Var)].dump(dbgs());
1708 dbgs() << "\n");
1709 setLocKind(LiveSet, Var, LocKind::Mem);
1710 emitDbgValue(LocKind::Mem, Assign, &I);
1711 return;
1712 }
1713
1714 // The StackHomeValue and DebugValue for this variable do not match. I.e.
1715 // The value currently stored in the stack is not what we'd expect to
1716 // see, so we cannot use emit a stack home location here. Now we will
1717 // look at the live LocKind for the variable and determine an appropriate
1718 // dbg.value to emit.
1719 LocKind PrevLoc = getLocKind(LiveSet, Var);
1720 switch (PrevLoc) {
1721 case LocKind::Val: {
1722 // The value in memory in memory has changed but we're not currently
1723 // using the memory location. Do nothing.
1724 LLVM_DEBUG(dbgs() << "Val, (unchanged)\n";);
1725 setLocKind(LiveSet, Var, LocKind::Val);
1726 } break;
1727 case LocKind::Mem: {
1728 // There's been an assignment to memory that we were using as a
1729 // location for this variable, and the Assignment doesn't match what
1730 // we'd expect to see in memory.
1731 Assignment DbgAV = LiveSet->getAssignment(BlockInfo::Debug, Var);
1732 if (DbgAV.Status == Assignment::NoneOrPhi) {
1733 // We need to terminate any previously open location now.
1734 LLVM_DEBUG(dbgs() << "None, No Debug value available\n";);
1735 setLocKind(LiveSet, Var, LocKind::None);
1736 emitDbgValue(LocKind::None, Assign, &I);
1737 } else {
1738 // The previous DebugValue Value can be used here.
1739 LLVM_DEBUG(dbgs() << "Val, Debug value is Known\n";);
1740 setLocKind(LiveSet, Var, LocKind::Val);
1741 if (DbgAV.Source) {
1742 emitDbgValue(LocKind::Val, DbgAV.Source, &I);
1743 } else {
1744 // PrevAV.Source is nullptr so we must emit undef here.
1745 emitDbgValue(LocKind::None, Assign, &I);
1746 }
1747 }
1748 } break;
1749 case LocKind::None: {
1750 // There's been an assignment to memory and we currently are
1751 // not tracking a location for the variable. Do not emit anything.
1752 LLVM_DEBUG(dbgs() << "None, (unchanged)\n";);
1753 setLocKind(LiveSet, Var, LocKind::None);
1754 } break;
1755 }
1756 };
1757 for (DbgAssignIntrinsic *DAI : Linked)
1758 ProcessLinkedAssign(DAI);
1759 for (DPValue *DPV : LinkedDPAssigns)
1760 ProcessLinkedAssign(DPV);
1761}
1762
1763void AssignmentTrackingLowering::processDbgAssign(AssignRecord Assign,
1764 BlockInfo *LiveSet) {
1765 auto ProcessDbgAssignImpl = [&](auto *DbgAssign) {
1766 // Only bother tracking variables that are at some point stack homed. Other
1767 // variables can be dealt with trivially later.
1768 if (!VarsWithStackSlot->count(getAggregate(DbgAssign)))
1769 return;
1770
1771 VariableID Var = getVariableID(DebugVariable(DbgAssign));
1772 Assignment AV = Assignment::make(getIDFromMarker(*DbgAssign), DbgAssign);
1773 addDbgDef(LiveSet, Var, AV);
1774
1775 LLVM_DEBUG(dbgs() << "processDbgAssign on " << *DbgAssign << "\n";);
1776 LLVM_DEBUG(dbgs() << " LiveLoc " << locStr(getLocKind(LiveSet, Var))
1777 << " -> ");
1778
1779 // Check if the DebugValue and StackHomeValue both hold the same
1780 // Assignment.
1781 if (hasVarWithAssignment(LiveSet, BlockInfo::Stack, Var, AV)) {
1782 // They match. We can use the stack home because the debug intrinsics
1783 // state that an assignment happened here, and we know that specific
1784 // assignment was the last one to take place in memory for this variable.
1785 LocKind Kind;
1786 if (DbgAssign->isKillAddress()) {
1787 LLVM_DEBUG(
1788 dbgs()
1789 << "Val, Stack matches Debug program but address is killed\n";);
1790 Kind = LocKind::Val;
1791 } else {
1792 LLVM_DEBUG(dbgs() << "Mem, Stack matches Debug program\n";);
1793 Kind = LocKind::Mem;
1794 };
1795 setLocKind(LiveSet, Var, Kind);
1796 emitDbgValue(Kind, DbgAssign, DbgAssign);
1797 } else {
1798 // The last assignment to the memory location isn't the one that we want
1799 // to show to the user so emit a dbg.value(Value). Value may be undef.
1800 LLVM_DEBUG(dbgs() << "Val, Stack contents is unknown\n";);
1801 setLocKind(LiveSet, Var, LocKind::Val);
1802 emitDbgValue(LocKind::Val, DbgAssign, DbgAssign);
1803 }
1804 };
1805 if (isa<DPValue *>(Assign))
1806 return ProcessDbgAssignImpl(cast<DPValue *>(Assign));
1807 return ProcessDbgAssignImpl(cast<DbgAssignIntrinsic *>(Assign));
1808}
1809
1810void AssignmentTrackingLowering::processDbgValue(
1812 BlockInfo *LiveSet) {
1813 auto ProcessDbgValueImpl = [&](auto *DbgValue) {
1814 // Only other tracking variables that are at some point stack homed.
1815 // Other variables can be dealt with trivally later.
1816 if (!VarsWithStackSlot->count(getAggregate(DbgValue)))
1817 return;
1818
1819 VariableID Var = getVariableID(DebugVariable(DbgValue));
1820 // We have no ID to create an Assignment with so we mark this assignment as
1821 // NoneOrPhi. Note that the dbg.value still exists, we just cannot determine
1822 // the assignment responsible for setting this value.
1823 // This is fine; dbg.values are essentially interchangable with unlinked
1824 // dbg.assigns, and some passes such as mem2reg and instcombine add them to
1825 // PHIs for promoted variables.
1826 Assignment AV = Assignment::makeNoneOrPhi();
1827 addDbgDef(LiveSet, Var, AV);
1828
1829 LLVM_DEBUG(dbgs() << "processDbgValue on " << *DbgValue << "\n";);
1830 LLVM_DEBUG(dbgs() << " LiveLoc " << locStr(getLocKind(LiveSet, Var))
1831 << " -> Val, dbg.value override");
1832
1833 setLocKind(LiveSet, Var, LocKind::Val);
1834 emitDbgValue(LocKind::Val, DbgValue, DbgValue);
1835 };
1836 if (isa<DPValue *>(DbgValueRecord))
1837 return ProcessDbgValueImpl(cast<DPValue *>(DbgValueRecord));
1838 return ProcessDbgValueImpl(cast<DbgValueInst *>(DbgValueRecord));
1839}
1840
1841template <typename T> static bool hasZeroSizedFragment(T &DbgValue) {
1842 if (auto F = DbgValue.getExpression()->getFragmentInfo())
1843 return F->SizeInBits == 0;
1844 return false;
1845}
1846
1847void AssignmentTrackingLowering::processDbgInstruction(
1848 DbgInfoIntrinsic &I, AssignmentTrackingLowering::BlockInfo *LiveSet) {
1849 auto *DVI = dyn_cast<DbgVariableIntrinsic>(&I);
1850 if (!DVI)
1851 return;
1852
1853 // Ignore assignments to zero bits of the variable.
1854 if (hasZeroSizedFragment(*DVI))
1855 return;
1856
1857 if (auto *DAI = dyn_cast<DbgAssignIntrinsic>(&I))
1858 processDbgAssign(DAI, LiveSet);
1859 else if (auto *DVI = dyn_cast<DbgValueInst>(&I))
1860 processDbgValue(DVI, LiveSet);
1861}
1862void AssignmentTrackingLowering::processDPValue(
1863 DPValue &DPV, AssignmentTrackingLowering::BlockInfo *LiveSet) {
1864 // Ignore assignments to zero bits of the variable.
1865 if (hasZeroSizedFragment(DPV))
1866 return;
1867
1868 if (DPV.isDbgAssign())
1869 processDbgAssign(&DPV, LiveSet);
1870 else if (DPV.isDbgValue())
1871 processDbgValue(&DPV, LiveSet);
1872}
1873
1874void AssignmentTrackingLowering::resetInsertionPoint(Instruction &After) {
1875 assert(!After.isTerminator() && "Can't insert after a terminator");
1876 auto *R = InsertBeforeMap.find(getNextNode(&After));
1877 if (R == InsertBeforeMap.end())
1878 return;
1879 R->second.clear();
1880}
1881void AssignmentTrackingLowering::resetInsertionPoint(DPValue &After) {
1882 auto *R = InsertBeforeMap.find(getNextNode(&After));
1883 if (R == InsertBeforeMap.end())
1884 return;
1885 R->second.clear();
1886}
1887
1888void AssignmentTrackingLowering::process(BasicBlock &BB, BlockInfo *LiveSet) {
1889 // If the block starts with DPValues, we need to process those DPValues as
1890 // their own frame without processing any instructions first.
1891 bool ProcessedLeadingDPValues = !BB.begin()->hasDbgValues();
1892 for (auto II = BB.begin(), EI = BB.end(); II != EI;) {
1893 assert(VarsTouchedThisFrame.empty());
1894 // Process the instructions in "frames". A "frame" includes a single
1895 // non-debug instruction followed any debug instructions before the
1896 // next non-debug instruction.
1897
1898 // Skip the current instruction if it has unprocessed DPValues attached (see
1899 // comment above `ProcessedLeadingDPValues`).
1900 if (ProcessedLeadingDPValues) {
1901 // II is now either a debug intrinsic, a non-debug instruction with no
1902 // attached DPValues, or a non-debug instruction with attached processed
1903 // DPValues.
1904 // II has not been processed.
1905 if (!isa<DbgInfoIntrinsic>(&*II)) {
1906 if (II->isTerminator())
1907 break;
1908 resetInsertionPoint(*II);
1909 processNonDbgInstruction(*II, LiveSet);
1910 assert(LiveSet->isValid());
1911 ++II;
1912 }
1913 }
1914 // II is now either a debug intrinsic, a non-debug instruction with no
1915 // attached DPValues, or a non-debug instruction with attached unprocessed
1916 // DPValues.
1917 if (II != EI && II->hasDbgValues()) {
1918 // Skip over non-variable debug records (i.e., labels). They're going to
1919 // be read from IR (possibly re-ordering them within the debug record
1920 // range) rather than from the analysis results.
1921 for (DPValue &DPV : DPValue::filter(II->getDbgValueRange())) {
1922 resetInsertionPoint(DPV);
1923 processDPValue(DPV, LiveSet);
1924 assert(LiveSet->isValid());
1925 }
1926 }
1927 ProcessedLeadingDPValues = true;
1928 while (II != EI) {
1929 auto *Dbg = dyn_cast<DbgInfoIntrinsic>(&*II);
1930 if (!Dbg)
1931 break;
1932 resetInsertionPoint(*II);
1933 processDbgInstruction(*Dbg, LiveSet);
1934 assert(LiveSet->isValid());
1935 ++II;
1936 }
1937 // II is now a non-debug instruction either with no attached DPValues, or
1938 // with attached processed DPValues. II has not been processed, and all
1939 // debug instructions or DPValues in the frame preceding II have been
1940 // processed.
1941
1942 // We've processed everything in the "frame". Now determine which variables
1943 // cannot be represented by a dbg.declare.
1944 for (auto Var : VarsTouchedThisFrame) {
1945 LocKind Loc = getLocKind(LiveSet, Var);
1946 // If a variable's LocKind is anything other than LocKind::Mem then we
1947 // must note that it cannot be represented with a dbg.declare.
1948 // Note that this check is enough without having to check the result of
1949 // joins() because for join to produce anything other than Mem after
1950 // we've already seen a Mem we'd be joining None or Val with Mem. In that
1951 // case, we've already hit this codepath when we set the LocKind to Val
1952 // or None in that block.
1953 if (Loc != LocKind::Mem) {
1954 DebugVariable DbgVar = FnVarLocs->getVariable(Var);
1955 DebugAggregate Aggr{DbgVar.getVariable(), DbgVar.getInlinedAt()};
1956 NotAlwaysStackHomed.insert(Aggr);
1957 }
1958 }
1959 VarsTouchedThisFrame.clear();
1960 }
1961}
1962
1963AssignmentTrackingLowering::LocKind
1964AssignmentTrackingLowering::joinKind(LocKind A, LocKind B) {
1965 // Partial order:
1966 // None > Mem, Val
1967 return A == B ? A : LocKind::None;
1968}
1969
1970AssignmentTrackingLowering::Assignment
1971AssignmentTrackingLowering::joinAssignment(const Assignment &A,
1972 const Assignment &B) {
1973 // Partial order:
1974 // NoneOrPhi(null, null) > Known(v, ?s)
1975
1976 // If either are NoneOrPhi the join is NoneOrPhi.
1977 // If either value is different then the result is
1978 // NoneOrPhi (joining two values is a Phi).
1979 if (!A.isSameSourceAssignment(B))
1980 return Assignment::makeNoneOrPhi();
1981 if (A.Status == Assignment::NoneOrPhi)
1982 return Assignment::makeNoneOrPhi();
1983
1984 // Source is used to lookup the value + expression in the debug program if
1985 // the stack slot gets assigned a value earlier than expected. Because
1986 // we're only tracking the one dbg.assign, we can't capture debug PHIs.
1987 // It's unlikely that we're losing out on much coverage by avoiding that
1988 // extra work.
1989 // The Source may differ in this situation:
1990 // Pred.1:
1991 // dbg.assign i32 0, ..., !1, ...
1992 // Pred.2:
1993 // dbg.assign i32 1, ..., !1, ...
1994 // Here the same assignment (!1) was performed in both preds in the source,
1995 // but we can't use either one unless they are identical (e.g. .we don't
1996 // want to arbitrarily pick between constant values).
1997 auto JoinSource = [&]() -> AssignRecord {
1998 if (A.Source == B.Source)
1999 return A.Source;
2000 if (!A.Source || !B.Source)
2001 return AssignRecord();
2002 assert(isa<DPValue *>(A.Source) == isa<DPValue *>(B.Source));
2003 if (isa<DPValue *>(A.Source) &&
2004 cast<DPValue *>(A.Source)->isEquivalentTo(*cast<DPValue *>(B.Source)))
2005 return A.Source;
2006 if (isa<DbgAssignIntrinsic *>(A.Source) &&
2007 cast<DbgAssignIntrinsic *>(A.Source)->isIdenticalTo(
2008 cast<DbgAssignIntrinsic *>(B.Source)))
2009 return A.Source;
2010 return AssignRecord();
2011 };
2012 AssignRecord Source = JoinSource();
2013 assert(A.Status == B.Status && A.Status == Assignment::Known);
2014 assert(A.ID == B.ID);
2015 return Assignment::make(A.ID, Source);
2016}
2017
2018AssignmentTrackingLowering::BlockInfo
2019AssignmentTrackingLowering::joinBlockInfo(const BlockInfo &A,
2020 const BlockInfo &B) {
2021 return BlockInfo::join(A, B, TrackedVariablesVectorSize);
2022}
2023
2024bool AssignmentTrackingLowering::join(
2025 const BasicBlock &BB, const SmallPtrSet<BasicBlock *, 16> &Visited) {
2026
2028 // Ignore backedges if we have not visited the predecessor yet. As the
2029 // predecessor hasn't yet had locations propagated into it, most locations
2030 // will not yet be valid, so treat them as all being uninitialized and
2031 // potentially valid. If a location guessed to be correct here is
2032 // invalidated later, we will remove it when we revisit this block. This
2033 // is essentially the same as initialising all LocKinds and Assignments to
2034 // an implicit ⊥ value which is the identity value for the join operation.
2035 for (const BasicBlock *Pred : predecessors(&BB)) {
2036 if (Visited.count(Pred))
2037 VisitedPreds.push_back(Pred);
2038 }
2039
2040 // No preds visited yet.
2041 if (VisitedPreds.empty()) {
2042 auto It = LiveIn.try_emplace(&BB, BlockInfo());
2043 bool DidInsert = It.second;
2044 if (DidInsert)
2045 It.first->second.init(TrackedVariablesVectorSize);
2046 return /*Changed*/ DidInsert;
2047 }
2048
2049 // Exactly one visited pred. Copy the LiveOut from that pred into BB LiveIn.
2050 if (VisitedPreds.size() == 1) {
2051 const BlockInfo &PredLiveOut = LiveOut.find(VisitedPreds[0])->second;
2052 auto CurrentLiveInEntry = LiveIn.find(&BB);
2053
2054 // Check if there isn't an entry, or there is but the LiveIn set has
2055 // changed (expensive check).
2056 if (CurrentLiveInEntry == LiveIn.end())
2057 LiveIn.insert(std::make_pair(&BB, PredLiveOut));
2058 else if (PredLiveOut != CurrentLiveInEntry->second)
2059 CurrentLiveInEntry->second = PredLiveOut;
2060 else
2061 return /*Changed*/ false;
2062 return /*Changed*/ true;
2063 }
2064
2065 // More than one pred. Join LiveOuts of blocks 1 and 2.
2066 assert(VisitedPreds.size() > 1);
2067 const BlockInfo &PredLiveOut0 = LiveOut.find(VisitedPreds[0])->second;
2068 const BlockInfo &PredLiveOut1 = LiveOut.find(VisitedPreds[1])->second;
2069 BlockInfo BBLiveIn = joinBlockInfo(PredLiveOut0, PredLiveOut1);
2070
2071 // Join the LiveOuts of subsequent blocks.
2072 ArrayRef Tail = ArrayRef(VisitedPreds).drop_front(2);
2073 for (const BasicBlock *Pred : Tail) {
2074 const auto &PredLiveOut = LiveOut.find(Pred);
2075 assert(PredLiveOut != LiveOut.end() &&
2076 "block should have been processed already");
2077 BBLiveIn = joinBlockInfo(std::move(BBLiveIn), PredLiveOut->second);
2078 }
2079
2080 // Save the joined result for BB.
2081 auto CurrentLiveInEntry = LiveIn.find(&BB);
2082 // Check if there isn't an entry, or there is but the LiveIn set has changed
2083 // (expensive check).
2084 if (CurrentLiveInEntry == LiveIn.end())
2085 LiveIn.try_emplace(&BB, std::move(BBLiveIn));
2086 else if (BBLiveIn != CurrentLiveInEntry->second)
2087 CurrentLiveInEntry->second = std::move(BBLiveIn);
2088 else
2089 return /*Changed*/ false;
2090 return /*Changed*/ true;
2091}
2092
2093/// Return true if A fully contains B.
2096 auto ALeft = A.OffsetInBits;
2097 auto BLeft = B.OffsetInBits;
2098 if (BLeft < ALeft)
2099 return false;
2100
2101 auto ARight = ALeft + A.SizeInBits;
2102 auto BRight = BLeft + B.SizeInBits;
2103 if (BRight > ARight)
2104 return false;
2105 return true;
2106}
2107
2108static std::optional<at::AssignmentInfo>
2110 // Don't bother checking if this is an AllocaInst. We know this
2111 // instruction has no tag which means there are no variables associated
2112 // with it.
2113 if (const auto *SI = dyn_cast<StoreInst>(&I))
2114 return at::getAssignmentInfo(Layout, SI);
2115 if (const auto *MI = dyn_cast<MemIntrinsic>(&I))
2116 return at::getAssignmentInfo(Layout, MI);
2117 // Alloca or non-store-like inst.
2118 return std::nullopt;
2119}
2120
2122 return dyn_cast<DbgDeclareInst>(DVI);
2123}
2124
2126 return DPV->isDbgDeclare() ? DPV : nullptr;
2127}
2128
2129/// Build a map of {Variable x: Variables y} where all variable fragments
2130/// contained within the variable fragment x are in set y. This means that
2131/// y does not contain all overlaps because partial overlaps are excluded.
2132///
2133/// While we're iterating over the function, add single location defs for
2134/// dbg.declares to \p FnVarLocs.
2135///
2136/// Variables that are interesting to this pass in are added to
2137/// FnVarLocs->Variables first. TrackedVariablesVectorSize is set to the ID of
2138/// the last interesting variable plus 1, meaning variables with ID 1
2139/// (inclusive) to TrackedVariablesVectorSize (exclusive) are interesting. The
2140/// subsequent variables are either stack homed or fully promoted.
2141///
2142/// Finally, populate UntaggedStoreVars with a mapping of untagged stores to
2143/// the stored-to variable fragments.
2144///
2145/// These tasks are bundled together to reduce the number of times we need
2146/// to iterate over the function as they can be achieved together in one pass.
2148 Function &Fn, FunctionVarLocsBuilder *FnVarLocs,
2149 const DenseSet<DebugAggregate> &VarsWithStackSlot,
2151 unsigned &TrackedVariablesVectorSize) {
2153 // Map of Variable: [Fragments].
2155 // Iterate over all instructions:
2156 // - dbg.declare -> add single location variable record
2157 // - dbg.* -> Add fragments to FragmentMap
2158 // - untagged store -> Add fragments to FragmentMap and update
2159 // UntaggedStoreVars.
2160 // We need to add fragments for untagged stores too so that we can correctly
2161 // clobber overlapped fragment locations later.
2162 SmallVector<DbgDeclareInst *> InstDeclares;
2163 SmallVector<DPValue *> DPDeclares;
2164 auto ProcessDbgRecord = [&](auto *Record, auto &DeclareList) {
2165 if (auto *Declare = DynCastToDbgDeclare(Record)) {
2166 DeclareList.push_back(Declare);
2167 return;
2168 }
2170 DebugAggregate DA = {DV.getVariable(), DV.getInlinedAt()};
2171 if (!VarsWithStackSlot.contains(DA))
2172 return;
2173 if (Seen.insert(DV).second)
2174 FragmentMap[DA].push_back(DV);
2175 };
2176 for (auto &BB : Fn) {
2177 for (auto &I : BB) {
2178 for (DPValue &DPV : DPValue::filter(I.getDbgValueRange()))
2179 ProcessDbgRecord(&DPV, DPDeclares);
2180 if (auto *DII = dyn_cast<DbgVariableIntrinsic>(&I)) {
2181 ProcessDbgRecord(DII, InstDeclares);
2182 } else if (auto Info = getUntaggedStoreAssignmentInfo(
2183 I, Fn.getParent()->getDataLayout())) {
2184 // Find markers linked to this alloca.
2185 auto HandleDbgAssignForStore = [&](auto *Assign) {
2186 std::optional<DIExpression::FragmentInfo> FragInfo;
2187
2188 // Skip this assignment if the affected bits are outside of the
2189 // variable fragment.
2191 I.getModule()->getDataLayout(), Info->Base,
2192 Info->OffsetInBits, Info->SizeInBits, Assign, FragInfo) ||
2193 (FragInfo && FragInfo->SizeInBits == 0))
2194 return;
2195
2196 // FragInfo from calculateFragmentIntersect is nullopt if the
2197 // resultant fragment matches DAI's fragment or entire variable - in
2198 // which case copy the fragment info from DAI. If FragInfo is still
2199 // nullopt after the copy it means "no fragment info" instead, which
2200 // is how it is usually interpreted.
2201 if (!FragInfo)
2202 FragInfo = Assign->getExpression()->getFragmentInfo();
2203
2204 DebugVariable DV =
2205 DebugVariable(Assign->getVariable(), FragInfo,
2206 Assign->getDebugLoc().getInlinedAt());
2207 DebugAggregate DA = {DV.getVariable(), DV.getInlinedAt()};
2208 if (!VarsWithStackSlot.contains(DA))
2209 return;
2210
2211 // Cache this info for later.
2212 UntaggedStoreVars[&I].push_back(
2213 {FnVarLocs->insertVariable(DV), *Info});
2214
2215 if (Seen.insert(DV).second)
2216 FragmentMap[DA].push_back(DV);
2217 };
2219 HandleDbgAssignForStore(DAI);
2220 for (DPValue *DPV : at::getDPVAssignmentMarkers(Info->Base))
2221 HandleDbgAssignForStore(DPV);
2222 }
2223 }
2224 }
2225
2226 // Sort the fragment map for each DebugAggregate in ascending
2227 // order of fragment size - there should be no duplicates.
2228 for (auto &Pair : FragmentMap) {
2229 SmallVector<DebugVariable, 8> &Frags = Pair.second;
2230 std::sort(Frags.begin(), Frags.end(),
2231 [](const DebugVariable &Next, const DebugVariable &Elmt) {
2232 return Elmt.getFragmentOrDefault().SizeInBits >
2233 Next.getFragmentOrDefault().SizeInBits;
2234 });
2235 // Check for duplicates.
2236 assert(std::adjacent_find(Frags.begin(), Frags.end()) == Frags.end());
2237 }
2238
2239 // Build the map.
2241 for (auto &Pair : FragmentMap) {
2242 auto &Frags = Pair.second;
2243 for (auto It = Frags.begin(), IEnd = Frags.end(); It != IEnd; ++It) {
2244 DIExpression::FragmentInfo Frag = It->getFragmentOrDefault();
2245 // Find the frags that this is contained within.
2246 //
2247 // Because Frags is sorted by size and none have the same offset and
2248 // size, we know that this frag can only be contained by subsequent
2249 // elements.
2251 ++OtherIt;
2252 VariableID ThisVar = FnVarLocs->insertVariable(*It);
2253 for (; OtherIt != IEnd; ++OtherIt) {
2254 DIExpression::FragmentInfo OtherFrag = OtherIt->getFragmentOrDefault();
2255 VariableID OtherVar = FnVarLocs->insertVariable(*OtherIt);
2256 if (fullyContains(OtherFrag, Frag))
2257 Map[OtherVar].push_back(ThisVar);
2258 }
2259 }
2260 }
2261
2262 // VariableIDs are 1-based so the variable-tracking bitvector needs
2263 // NumVariables plus 1 bits.
2264 TrackedVariablesVectorSize = FnVarLocs->getNumVariables() + 1;
2265
2266 // Finally, insert the declares afterwards, so the first IDs are all
2267 // partially stack homed vars.
2268 for (auto *DDI : InstDeclares)
2269 FnVarLocs->addSingleLocVar(DebugVariable(DDI), DDI->getExpression(),
2270 DDI->getDebugLoc(), DDI->getWrappedLocation());
2271 for (auto *DPV : DPDeclares)
2272 FnVarLocs->addSingleLocVar(DebugVariable(DPV), DPV->getExpression(),
2273 DPV->getDebugLoc(),
2275 return Map;
2276}
2277
2278bool AssignmentTrackingLowering::run(FunctionVarLocsBuilder *FnVarLocsBuilder) {
2279 if (Fn.size() > MaxNumBlocks) {
2280 LLVM_DEBUG(dbgs() << "[AT] Dropping var locs in: " << Fn.getName()
2281 << ": too many blocks (" << Fn.size() << ")\n");
2282 at::deleteAll(&Fn);
2283 return false;
2284 }
2285
2286 FnVarLocs = FnVarLocsBuilder;
2287
2288 // The general structure here is inspired by VarLocBasedImpl.cpp
2289 // (LiveDebugValues).
2290
2291 // Build the variable fragment overlap map.
2292 // Note that this pass doesn't handle partial overlaps correctly (FWIW
2293 // neither does LiveDebugVariables) because that is difficult to do and
2294 // appears to be rare occurance.
2296 Fn, FnVarLocs, *VarsWithStackSlot, UntaggedStoreVars,
2297 TrackedVariablesVectorSize);
2298
2299 // Prepare for traversal.
2301 std::priority_queue<unsigned int, std::vector<unsigned int>,
2302 std::greater<unsigned int>>
2303 Worklist;
2304 std::priority_queue<unsigned int, std::vector<unsigned int>,
2305 std::greater<unsigned int>>
2306 Pending;
2309 { // Init OrderToBB and BBToOrder.
2310 unsigned int RPONumber = 0;
2311 for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
2312 OrderToBB[RPONumber] = *RI;
2313 BBToOrder[*RI] = RPONumber;
2314 Worklist.push(RPONumber);
2315 ++RPONumber;
2316 }
2317 LiveIn.init(RPONumber);
2318 LiveOut.init(RPONumber);
2319 }
2320
2321 // Perform the traversal.
2322 //
2323 // This is a standard "union of predecessor outs" dataflow problem. To solve
2324 // it, we perform join() and process() using the two worklist method until
2325 // the LiveIn data for each block becomes unchanging. The "proof" that this
2326 // terminates can be put together by looking at the comments around LocKind,
2327 // Assignment, and the various join methods, which show that all the elements
2328 // involved are made up of join-semilattices; LiveIn(n) can only
2329 // monotonically increase in value throughout the dataflow.
2330 //
2332 while (!Worklist.empty()) {
2333 // We track what is on the pending worklist to avoid inserting the same
2334 // thing twice.
2336 LLVM_DEBUG(dbgs() << "Processing Worklist\n");
2337 while (!Worklist.empty()) {
2338 BasicBlock *BB = OrderToBB[Worklist.top()];
2339 LLVM_DEBUG(dbgs() << "\nPop BB " << BB->getName() << "\n");
2340 Worklist.pop();
2341 bool InChanged = join(*BB, Visited);
2342 // Always consider LiveIn changed on the first visit.
2343 InChanged |= Visited.insert(BB).second;
2344 if (InChanged) {
2345 LLVM_DEBUG(dbgs() << BB->getName() << " has new InLocs, process it\n");
2346 // Mutate a copy of LiveIn while processing BB. After calling process
2347 // LiveSet is the LiveOut set for BB.
2348 BlockInfo LiveSet = LiveIn[BB];
2349
2350 // Process the instructions in the block.
2351 process(*BB, &LiveSet);
2352
2353 // Relatively expensive check: has anything changed in LiveOut for BB?
2354 if (LiveOut[BB] != LiveSet) {
2355 LLVM_DEBUG(dbgs() << BB->getName()
2356 << " has new OutLocs, add succs to worklist: [ ");
2357 LiveOut[BB] = std::move(LiveSet);
2358 for (auto I = succ_begin(BB), E = succ_end(BB); I != E; I++) {
2359 if (OnPending.insert(*I).second) {
2360 LLVM_DEBUG(dbgs() << I->getName() << " ");
2361 Pending.push(BBToOrder[*I]);
2362 }
2363 }
2364 LLVM_DEBUG(dbgs() << "]\n");
2365 }
2366 }
2367 }
2368 Worklist.swap(Pending);
2369 // At this point, pending must be empty, since it was just the empty
2370 // worklist
2371 assert(Pending.empty() && "Pending should be empty");
2372 }
2373
2374 // That's the hard part over. Now we just have some admin to do.
2375
2376 // Record whether we inserted any intrinsics.
2377 bool InsertedAnyIntrinsics = false;
2378
2379 // Identify and add defs for single location variables.
2380 //
2381 // Go through all of the defs that we plan to add. If the aggregate variable
2382 // it's a part of is not in the NotAlwaysStackHomed set we can emit a single
2383 // location def and omit the rest. Add an entry to AlwaysStackHomed so that
2384 // we can identify those uneeded defs later.
2385 DenseSet<DebugAggregate> AlwaysStackHomed;
2386 for (const auto &Pair : InsertBeforeMap) {
2387 auto &Vec = Pair.second;
2388 for (VarLocInfo VarLoc : Vec) {
2389 DebugVariable Var = FnVarLocs->getVariable(VarLoc.VariableID);
2390 DebugAggregate Aggr{Var.getVariable(), Var.getInlinedAt()};
2391
2392 // Skip this Var if it's not always stack homed.
2393 if (NotAlwaysStackHomed.contains(Aggr))
2394 continue;
2395
2396 // Skip complex cases such as when different fragments of a variable have
2397 // been split into different allocas. Skipping in this case means falling
2398 // back to using a list of defs (which could reduce coverage, but is no
2399 // less correct).
2400 bool Simple =
2401 VarLoc.Expr->getNumElements() == 1 && VarLoc.Expr->startsWithDeref();
2402 if (!Simple) {
2403 NotAlwaysStackHomed.insert(Aggr);
2404 continue;
2405 }
2406
2407 // All source assignments to this variable remain and all stores to any
2408 // part of the variable store to the same address (with varying
2409 // offsets). We can just emit a single location for the whole variable.
2410 //
2411 // Unless we've already done so, create the single location def now.
2412 if (AlwaysStackHomed.insert(Aggr).second) {
2413 assert(!VarLoc.Values.hasArgList());
2414 // TODO: When more complex cases are handled VarLoc.Expr should be
2415 // built appropriately rather than always using an empty DIExpression.
2416 // The assert below is a reminder.
2417 assert(Simple);
2418 VarLoc.Expr = DIExpression::get(Fn.getContext(), std::nullopt);
2419 DebugVariable Var = FnVarLocs->getVariable(VarLoc.VariableID);
2420 FnVarLocs->addSingleLocVar(Var, VarLoc.Expr, VarLoc.DL, VarLoc.Values);
2421 InsertedAnyIntrinsics = true;
2422 }
2423 }
2424 }
2425
2426 // Insert the other DEFs.
2427 for (const auto &[InsertBefore, Vec] : InsertBeforeMap) {
2429 for (const VarLocInfo &VarLoc : Vec) {
2430 DebugVariable Var = FnVarLocs->getVariable(VarLoc.VariableID);
2431 DebugAggregate Aggr{Var.getVariable(), Var.getInlinedAt()};
2432 // If this variable is always stack homed then we have already inserted a
2433 // dbg.declare and deleted this dbg.value.
2434 if (AlwaysStackHomed.contains(Aggr))
2435 continue;
2436 NewDefs.push_back(VarLoc);
2437 InsertedAnyIntrinsics = true;
2438 }
2439
2440 FnVarLocs->setWedge(InsertBefore, std::move(NewDefs));
2441 }
2442
2443 InsertedAnyIntrinsics |= emitPromotedVarLocs(FnVarLocs);
2444
2445 return InsertedAnyIntrinsics;
2446}
2447
2448bool AssignmentTrackingLowering::emitPromotedVarLocs(
2449 FunctionVarLocsBuilder *FnVarLocs) {
2450 bool InsertedAnyIntrinsics = false;
2451 // Go through every block, translating debug intrinsics for fully promoted
2452 // variables into FnVarLocs location defs. No analysis required for these.
2453 auto TranslateDbgRecord = [&](auto *Record) {
2454 // Skip variables that haven't been promoted - we've dealt with those
2455 // already.
2456 if (VarsWithStackSlot->contains(getAggregate(Record)))
2457 return;
2458 auto InsertBefore = getNextNode(Record);
2459 assert(InsertBefore && "Unexpected: debug intrinsics after a terminator");
2460 FnVarLocs->addVarLoc(InsertBefore, DebugVariable(Record),
2461 Record->getExpression(), Record->getDebugLoc(),
2462 RawLocationWrapper(Record->getRawLocation()));
2463 InsertedAnyIntrinsics = true;
2464 };
2465 for (auto &BB : Fn) {
2466 for (auto &I : BB) {
2467 // Skip instructions other than dbg.values and dbg.assigns.
2468 for (DPValue &DPV : DPValue::filter(I.getDbgValueRange()))
2469 if (DPV.isDbgValue() || DPV.isDbgAssign())
2470 TranslateDbgRecord(&DPV);
2471 auto *DVI = dyn_cast<DbgValueInst>(&I);
2472 if (DVI)
2473 TranslateDbgRecord(DVI);
2474 }
2475 }
2476 return InsertedAnyIntrinsics;
2477}
2478
2479/// Remove redundant definitions within sequences of consecutive location defs.
2480/// This is done using a backward scan to keep the last def describing a
2481/// specific variable/fragment.
2482///
2483/// This implements removeRedundantDbgInstrsUsingBackwardScan from
2484/// lib/Transforms/Utils/BasicBlockUtils.cpp for locations described with
2485/// FunctionVarLocsBuilder instead of with intrinsics.
2486static bool
2488 FunctionVarLocsBuilder &FnVarLocs) {
2489 bool Changed = false;
2490 SmallDenseMap<DebugAggregate, BitVector> VariableDefinedBytes;
2491 // Scan over the entire block, not just over the instructions mapped by
2492 // FnVarLocs, because wedges in FnVarLocs may only be seperated by debug
2493 // instructions.
2494 for (const Instruction &I : reverse(*BB)) {
2495 if (!isa<DbgVariableIntrinsic>(I)) {
2496 // Sequence of consecutive defs ended. Clear map for the next one.
2497 VariableDefinedBytes.clear();
2498 }
2499
2500 auto HandleLocsForWedge = [&](auto *WedgePosition) {
2501 // Get the location defs that start just before this instruction.
2502 const auto *Locs = FnVarLocs.getWedge(WedgePosition);
2503 if (!Locs)
2504 return;
2505
2506 NumWedgesScanned++;
2507 bool ChangedThisWedge = false;
2508 // The new pruned set of defs, reversed because we're scanning backwards.
2509 SmallVector<VarLocInfo> NewDefsReversed;
2510
2511 // Iterate over the existing defs in reverse.
2512 for (auto RIt = Locs->rbegin(), REnd = Locs->rend(); RIt != REnd; ++RIt) {
2513 NumDefsScanned++;
2514 DebugAggregate Aggr =
2515 getAggregate(FnVarLocs.getVariable(RIt->VariableID));
2516 uint64_t SizeInBits = Aggr.first->getSizeInBits().value_or(0);
2517 uint64_t SizeInBytes = divideCeil(SizeInBits, 8);
2518
2519 // Cutoff for large variables to prevent expensive bitvector operations.
2520 const uint64_t MaxSizeBytes = 2048;
2521
2522 if (SizeInBytes == 0 || SizeInBytes > MaxSizeBytes) {
2523 // If the size is unknown (0) then keep this location def to be safe.
2524 // Do the same for defs of large variables, which would be expensive
2525 // to represent with a BitVector.
2526 NewDefsReversed.push_back(*RIt);
2527 continue;
2528 }
2529
2530 // Only keep this location definition if it is not fully eclipsed by
2531 // other definitions in this wedge that come after it
2532
2533 // Inert the bytes the location definition defines.
2534 auto InsertResult =
2535 VariableDefinedBytes.try_emplace(Aggr, BitVector(SizeInBytes));
2536 bool FirstDefinition = InsertResult.second;
2537 BitVector &DefinedBytes = InsertResult.first->second;
2538
2540 RIt->Expr->getFragmentInfo().value_or(
2541 DIExpression::FragmentInfo(SizeInBits, 0));
2542 bool InvalidFragment = Fragment.endInBits() > SizeInBits;
2543 uint64_t StartInBytes = Fragment.startInBits() / 8;
2544 uint64_t EndInBytes = divideCeil(Fragment.endInBits(), 8);
2545
2546 // If this defines any previously undefined bytes, keep it.
2547 if (FirstDefinition || InvalidFragment ||
2548 DefinedBytes.find_first_unset_in(StartInBytes, EndInBytes) != -1) {
2549 if (!InvalidFragment)
2550 DefinedBytes.set(StartInBytes, EndInBytes);
2551 NewDefsReversed.push_back(*RIt);
2552 continue;
2553 }
2554
2555 // Redundant def found: throw it away. Since the wedge of defs is being
2556 // rebuilt, doing nothing is the same as deleting an entry.
2557 ChangedThisWedge = true;
2558 NumDefsRemoved++;
2559 }
2560
2561 // Un-reverse the defs and replace the wedge with the pruned version.
2562 if (ChangedThisWedge) {
2563 std::reverse(NewDefsReversed.begin(), NewDefsReversed.end());
2564 FnVarLocs.setWedge(WedgePosition, std::move(NewDefsReversed));
2565 NumWedgesChanged++;
2566 Changed = true;
2567 }
2568 };
2569 HandleLocsForWedge(&I);
2570 for (DPValue &DPV : reverse(DPValue::filter(I.getDbgValueRange())))
2571 HandleLocsForWedge(&DPV);
2572 }
2573
2574 return Changed;
2575}
2576
2577/// Remove redundant location defs using a forward scan. This can remove a
2578/// location definition that is redundant due to indicating that a variable has
2579/// the same value as is already being indicated by an earlier def.
2580///
2581/// This implements removeRedundantDbgInstrsUsingForwardScan from
2582/// lib/Transforms/Utils/BasicBlockUtils.cpp for locations described with
2583/// FunctionVarLocsBuilder instead of with intrinsics
2584static bool
2586 FunctionVarLocsBuilder &FnVarLocs) {
2587 bool Changed = false;
2589 VariableMap;
2590
2591 // Scan over the entire block, not just over the instructions mapped by
2592 // FnVarLocs, because wedges in FnVarLocs may only be seperated by debug
2593 // instructions.
2594 for (const Instruction &I : *BB) {
2595 // Get the defs that come just before this instruction.
2596 auto HandleLocsForWedge = [&](auto *WedgePosition) {
2597 const auto *Locs = FnVarLocs.getWedge(WedgePosition);
2598 if (!Locs)
2599 return;
2600
2601 NumWedgesScanned++;
2602 bool ChangedThisWedge = false;
2603 // The new pruned set of defs.
2605
2606 // Iterate over the existing defs.
2607 for (const VarLocInfo &Loc : *Locs) {
2608 NumDefsScanned++;
2609 DebugVariable Key(FnVarLocs.getVariable(Loc.VariableID).getVariable(),
2610 std::nullopt, Loc.DL.getInlinedAt());
2611 auto VMI = VariableMap.find(Key);
2612
2613 // Update the map if we found a new value/expression describing the
2614 // variable, or if the variable wasn't mapped already.
2615 if (VMI == VariableMap.end() || VMI->second.first != Loc.Values ||
2616 VMI->second.second != Loc.Expr) {
2617 VariableMap[Key] = {Loc.Values, Loc.Expr};
2618 NewDefs.push_back(Loc);
2619 continue;
2620 }
2621
2622 // Did not insert this Loc, which is the same as removing it.
2623 ChangedThisWedge = true;
2624 NumDefsRemoved++;
2625 }
2626
2627 // Replace the existing wedge with the pruned version.
2628 if (ChangedThisWedge) {
2629 FnVarLocs.setWedge(WedgePosition, std::move(NewDefs));
2630 NumWedgesChanged++;
2631 Changed = true;
2632 }
2633 };
2634
2635 for (DPValue &DPV : DPValue::filter(I.getDbgValueRange()))
2636 HandleLocsForWedge(&DPV);
2637 HandleLocsForWedge(&I);
2638 }
2639
2640 return Changed;
2641}
2642
2643static bool
2645 FunctionVarLocsBuilder &FnVarLocs) {
2646 assert(BB->isEntryBlock());
2647 // Do extra work to ensure that we remove semantically unimportant undefs.
2648 //
2649 // This is to work around the fact that SelectionDAG will hoist dbg.values
2650 // using argument values to the top of the entry block. That can move arg
2651 // dbg.values before undef and constant dbg.values which they previously
2652 // followed. The easiest thing to do is to just try to feed SelectionDAG
2653 // input it's happy with.
2654 //
2655 // Map of {Variable x: Fragments y} where the fragments y of variable x have
2656 // have at least one non-undef location defined already. Don't use directly,
2657 // instead call DefineBits and HasDefinedBits.
2659 VarsWithDef;
2660 // Specify that V (a fragment of A) has a non-undef location.
2661 auto DefineBits = [&VarsWithDef](DebugAggregate A, DebugVariable V) {
2662 VarsWithDef[A].insert(V.getFragmentOrDefault());
2663 };
2664 // Return true if a non-undef location has been defined for V (a fragment of
2665 // A). Doesn't imply that the location is currently non-undef, just that a
2666 // non-undef location has been seen previously.
2667 auto HasDefinedBits = [&VarsWithDef](DebugAggregate A, DebugVariable V) {
2668 auto FragsIt = VarsWithDef.find(A);
2669 if (FragsIt == VarsWithDef.end())
2670 return false;
2671 return llvm::any_of(FragsIt->second, [V](auto Frag) {
2672 return DIExpression::fragmentsOverlap(Frag, V.getFragmentOrDefault());
2673 });
2674 };
2675
2676 bool Changed = false;
2678
2679 // Scan over the entire block, not just over the instructions mapped by
2680 // FnVarLocs, because wedges in FnVarLocs may only be seperated by debug
2681 // instructions.
2682 for (const Instruction &I : *BB) {
2683 // Get the defs that come just before this instruction.
2684 auto HandleLocsForWedge = [&](auto *WedgePosition) {
2685 const auto *Locs = FnVarLocs.getWedge(WedgePosition);
2686 if (!Locs)
2687 return;
2688
2689 NumWedgesScanned++;
2690 bool ChangedThisWedge = false;
2691 // The new pruned set of defs.
2693
2694 // Iterate over the existing defs.
2695 for (const VarLocInfo &Loc : *Locs) {
2696 NumDefsScanned++;
2697 DebugAggregate Aggr{FnVarLocs.getVariable(Loc.VariableID).getVariable(),
2698 Loc.DL.getInlinedAt()};
2699 DebugVariable Var = FnVarLocs.getVariable(Loc.VariableID);
2700
2701 // Remove undef entries that are encountered before any non-undef
2702 // intrinsics from the entry block.
2703 if (Loc.Values.isKillLocation(Loc.Expr) && !HasDefinedBits(Aggr, Var)) {
2704 // Did not insert this Loc, which is the same as removing it.
2705 NumDefsRemoved++;
2706 ChangedThisWedge = true;
2707 continue;
2708 }
2709
2710 DefineBits(Aggr, Var);
2711 NewDefs.push_back(Loc);
2712 }
2713
2714 // Replace the existing wedge with the pruned version.
2715 if (ChangedThisWedge) {
2716 FnVarLocs.setWedge(WedgePosition, std::move(NewDefs));
2717 NumWedgesChanged++;
2718 Changed = true;
2719 }
2720 };
2721 for (DPValue &DPV : DPValue::filter(I.getDbgValueRange()))
2722 HandleLocsForWedge(&DPV);
2723 HandleLocsForWedge(&I);
2724 }
2725
2726 return Changed;
2727}
2728
2730 FunctionVarLocsBuilder &FnVarLocs) {
2731 bool MadeChanges = false;
2732 MadeChanges |= removeRedundantDbgLocsUsingBackwardScan(BB, FnVarLocs);
2733 if (BB->isEntryBlock())
2734 MadeChanges |= removeUndefDbgLocsFromEntryBlock(BB, FnVarLocs);
2735 MadeChanges |= removeRedundantDbgLocsUsingForwardScan(BB, FnVarLocs);
2736
2737 if (MadeChanges)
2738 LLVM_DEBUG(dbgs() << "Removed redundant dbg locs from: " << BB->getName()
2739 << "\n");
2740 return MadeChanges;
2741}
2742
2745 for (auto &BB : Fn) {
2746 for (auto &I : BB) {
2747 // Any variable linked to an instruction is considered
2748 // interesting. Ideally we only need to check Allocas, however, a
2749 // DIAssignID might get dropped from an alloca but not stores. In that
2750 // case, we need to consider the variable interesting for NFC behaviour
2751 // with this change. TODO: Consider only looking at allocas.
2753 Result.insert({DAI->getVariable(), DAI->getDebugLoc().getInlinedAt()});
2754 }
2755 for (DPValue *DPV : at::getDPVAssignmentMarkers(&I)) {
2756 Result.insert({DPV->getVariable(), DPV->getDebugLoc().getInlinedAt()});
2757 }
2758 }
2759 }
2760 return Result;
2761}
2762
2763static void analyzeFunction(Function &Fn, const DataLayout &Layout,
2764 FunctionVarLocsBuilder *FnVarLocs) {
2765 // The analysis will generate location definitions for all variables, but we
2766 // only need to perform a dataflow on the set of variables which have a stack
2767 // slot. Find those now.
2768 DenseSet<DebugAggregate> VarsWithStackSlot = findVarsWithStackSlot(Fn);
2769
2770 bool Changed = false;
2771
2772 // Use a scope block to clean up AssignmentTrackingLowering before running
2773 // MemLocFragmentFill to reduce peak memory consumption.
2774 {
2775 AssignmentTrackingLowering Pass(Fn, Layout, &VarsWithStackSlot);
2776 Changed = Pass.run(FnVarLocs);
2777 }
2778
2779 if (Changed) {
2780 MemLocFragmentFill Pass(Fn, &VarsWithStackSlot,
2782 Pass.run(FnVarLocs);
2783
2784 // Remove redundant entries. As well as reducing memory consumption and
2785 // avoiding waiting cycles later by burning some now, this has another
2786 // important job. That is to work around some SelectionDAG quirks. See
2787 // removeRedundantDbgLocsUsingForwardScan comments for more info on that.
2788 for (auto &BB : Fn)
2789 removeRedundantDbgLocs(&BB, *FnVarLocs);
2790 }
2791}
2792
2796 if (!isAssignmentTrackingEnabled(*F.getParent()))
2797 return FunctionVarLocs();
2798
2799 auto &DL = F.getParent()->getDataLayout();
2800
2801 FunctionVarLocsBuilder Builder;
2802 analyzeFunction(F, DL, &Builder);
2803
2804 // Save these results.
2806 Results.init(Builder);
2807 return Results;
2808}
2809
2810AnalysisKey DebugAssignmentTrackingAnalysis::Key;
2811
2816 return PreservedAnalyses::all();
2817}
2818
2820 if (!isAssignmentTrackingEnabled(*F.getParent()))
2821 return false;
2822
2823 LLVM_DEBUG(dbgs() << "AssignmentTrackingAnalysis run on " << F.getName()
2824 << "\n");
2825 auto DL = std::make_unique<DataLayout>(F.getParent());
2826
2827 // Clear previous results.
2828 Results->clear();
2829
2830 FunctionVarLocsBuilder Builder;
2831 analyzeFunction(F, *DL.get(), &Builder);
2832
2833 // Save these results.
2834 Results->init(Builder);
2835
2836 if (PrintResults && isFunctionInPrintList(F.getName()))
2837 Results->print(errs(), F);
2838
2839 // Return false because this pass does not modify the function.
2840 return false;
2841}
2842
2844 : FunctionPass(ID), Results(std::make_unique<FunctionVarLocs>()) {}
2845
2847
2849 "Assignment Tracking Analysis", false, true)
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
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 AssignmentTrackingLowering::OverlapMap buildOverlapMapAndRecordDeclares(Function &Fn, FunctionVarLocsBuilder *FnVarLocs, const DenseSet< DebugAggregate > &VarsWithStackSlot, AssignmentTrackingLowering::UntaggedStoreAssignmentMap &UntaggedStoreVars, unsigned &TrackedVariablesVectorSize)
Build a map of {Variable x: Variables y} where all variable fragments contained within the variable f...
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)
PointerUnion< const Instruction *, const DbgRecord * > VarLocInsertPt
static bool removeRedundantDbgLocsUsingForwardScan(const BasicBlock *BB, FunctionVarLocsBuilder &FnVarLocs)
Remove redundant location defs using a forward scan.
static bool removeRedundantDbgLocs(const BasicBlock *BB, FunctionVarLocsBuilder &FnVarLocs)
VarLocInsertPt getNextNode(const DbgRecord *DPV)
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)
DbgAssignIntrinsic * CastToDbgAssign(DbgVariableIntrinsic *DVI)
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 bool hasZeroSizedFragment(T &DbgValue)
static cl::opt< cl::boolOrDefault > CoalesceAdjacentFragmentsOpt("debug-ata-coalesce-frags", cl::Hidden)
Coalesce adjacent dbg locs describing memory locations that have contiguous fragments.
static cl::opt< unsigned > MaxNumBlocks("debug-ata-max-blocks", cl::init(10000), cl::desc("Maximum num basic blocks before debug info dropped"), cl::Hidden)
static bool shouldCoalesceFragments(Function &F)
DbgDeclareInst * DynCastToDbgDeclare(DbgVariableIntrinsic *DVI)
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:1290
bool End
Definition: ELF_riscv.cpp:480
#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)
FunctionAnalysisManager FAM
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_>.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Scalar Replacement Of Aggregates
Definition: SROA.cpp:5475
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 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
@ None
Value * RHS
Value * LHS
Helper class to build FunctionVarLocs, since that class isn't easy to modify.
void setWedge(VarLocInsertPt Before, SmallVector< VarLocInfo > &&Wedge)
Replace the defs that come just before /p Before with /p Wedge.
const SmallVectorImpl< VarLocInfo > * getWedge(VarLocInsertPt 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.
void addVarLoc(VarLocInsertPt Before, DebugVariable Var, DIExpression *Expr, DebugLoc DL, RawLocationWrapper R)
Add a def to the wedge of defs just before /p Before.
const DebugVariable & getVariable(VariableID ID) const
Get a variable from its ID.
Class recording the (high level) value of a variable.
Class for arbitrary precision integers.
Definition: APInt.h:76
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1485
bool getBoolValue() const
Convert APInt to a boolean value.
Definition: APInt.h:449
an instruction to allocate memory on the stack
Definition: Instructions.h:59
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
ArrayRef< T > drop_front(size_t N=1) const
Drop the first N elements of the array.
Definition: ArrayRef.h:204
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:60
iterator end()
Definition: BasicBlock.h:451
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:438
bool isEntryBlock() const
Return true if this is the entry block of the containing function.
Definition: BasicBlock.cpp:607
int find_first_unset_in(unsigned Begin, unsigned End) const
find_first_unset_in - Returns the index of the first unset bit in the range [Begin,...
Definition: BitVector.h:261
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:819
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
Instruction * MarkedInstr
Link back to the Instruction that owns this marker.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgValueRange()
Produce a range over all the DPValues in this Marker.
Record of a variable value-assignment, aka a non instruction representation of the dbg....
DIExpression * getExpression() const
Metadata * getRawLocation() const
Returns the metadata operand for the first location description.
DIAssignID * getAssignID() const
DILocalVariable * getVariable() const
static auto filter(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DPValue types only and downcast.
This class represents an Operation in the Expression.
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
This represents the llvm.dbg.declare instruction.
This is the common base class for debug info intrinsics.
Base class for non-instruction debug metadata records that have positions within IR.
DebugLoc getDebugLoc() const
This is the common base class for debug info intrinsics for variables.
DILocalVariable * getVariable() const
Result run(Function &F, FunctionAnalysisManager &FAM)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
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
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
Definition: DenseMap.h:235
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:819
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:311
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:800
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:342
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:655
bool hasDbgValues() const
Returns true if any DPValues are attached to this instruction.
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgValueRange() const
Return a range over the DPValues attached to this instruction.
Definition: Instruction.h:82
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:452
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:1541
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:36
Root of the metadata hierarchy.
Definition: Metadata.h:62
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.h:275
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:94
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
Definition: PointerUnion.h:118
void * getOpaqueValue() const
Definition: PointerUnion.h:193
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1827
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
Lightweight class that wraps the location operand metadata of a debug intrinsic.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:360
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:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
bool empty() const
Definition: SmallVector.h:94
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:586
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:950
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Target - Wrapper for Target specific information.
Triple - Helper class for working with autoconf configuration names.
Definition: Triple.h:44
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
iterator end()
Return an iterator to the end of the vector.
Definition: UniqueVector.h:81
iterator begin()
Return an iterator to the start of the vector.
Definition: UniqueVector.h:75
static ValueAsMetadata * get(Value *V)
Definition: Metadata.cpp:492
LLVM Value Representation.
Definition: Value.h:74
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
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
self_iterator getIterator()
Definition: ilist_node.h:109
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:316
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:121
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ Tail
Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...
Definition: CallingConv.h:76
void deleteAll(Function *F)
Remove all Assignment Tracking related intrinsics and metadata from F.
Definition: DebugInfo.cpp:1824
AssignmentMarkerRange getAssignmentMarkers(DIAssignID *ID)
Return a range of dbg.assign intrinsics which use \ID as an operand.
Definition: DebugInfo.cpp:1785
SmallVector< DPValue * > getDPVAssignmentMarkers(const Instruction *Inst)
Definition: DebugInfo.h:236
std::optional< AssignmentInfo > getAssignmentInfo(const DataLayout &DL, const MemIntrinsic *I)
Definition: DebugInfo.cpp:2047
bool calculateFragmentIntersect(const DataLayout &DL, const Value *Dest, uint64_t SliceOffsetInBits, uint64_t SliceSizeInBits, const DbgAssignIntrinsic *DbgAssign, std::optional< DIExpression::FragmentInfo > &Result)
Calculate the fragment of the variable in DAI covered from (Dest + SliceOffsetInBits) to to (Dest + S...
Definition: DebugInfo.cpp:2008
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
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:456
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:1731
uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator)
Returns the integer ceil(Numerator / Denominator).
Definition: MathExtras.h:417
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:2036
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)
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
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:1738
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:428
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:2315
auto predecessors(const MachineBasicBlock *BB)
bool debuginfoShouldUseDebugInstrRef(const Triple &T)
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:26
Holds the characteristics of one fragment of a larger variable.
uint64_t endInBits() const
Return the index of the bit after the end of the fragment, e.g.
uint64_t startInBits() const
Return the index of the first bit of the fragment.
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:50
Variable location definition used by FunctionVarLocs.
RawLocationWrapper Values
result_type operator()(const argument_type &Arg) const