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