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