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