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