Movatterモバイル変換

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//===----------------------------------------------------------------------===//

9#include "llvm/CodeGen/AssignmentTrackingAnalysis.h"

10#include "LiveDebugValues/LiveDebugValues.h"

11#include "llvm/ADT/BitVector.h"

12#include "llvm/ADT/DenseMapInfo.h"

13#include "llvm/ADT/IntervalMap.h"

14#include "llvm/ADT/PostOrderIterator.h"

15#include "llvm/ADT/STLExtras.h"

16#include "llvm/ADT/Statistic.h"

17#include "llvm/ADT/UniqueVector.h"

18#include "llvm/BinaryFormat/Dwarf.h"

19#include "llvm/IR/BasicBlock.h"

20#include "llvm/IR/DataLayout.h"

21#include "llvm/IR/DebugInfo.h"

22#include "llvm/IR/DebugProgramInstruction.h"

23#include "llvm/IR/Function.h"

24#include "llvm/IR/Instruction.h"

25#include "llvm/IR/IntrinsicInst.h"

26#include "llvm/IR/Module.h"

27#include "llvm/IR/PassManager.h"

28#include "llvm/IR/PrintPasses.h"

29#include "llvm/InitializePasses.h"

30#include "llvm/Support/CommandLine.h"

31#include "llvm/Support/ErrorHandling.h"

32#include "llvm/Support/raw_ostream.h"

33#include "llvm/Transforms/Utils/BasicBlockUtils.h"

34#include <assert.h>

35#include <cstdint>

36#include <optional>

37#include <queue>

38#include <sstream>

39#include <unordered_map>

41using namespacellvm;

42#define DEBUG_TYPE "debug-ata"

44STATISTIC(NumDefsScanned,"Number of dbg locs that get scanned for removal");

45STATISTIC(NumDefsRemoved,"Number of dbg locs removed");

46STATISTIC(NumWedgesScanned,"Number of dbg wedges scanned");

47STATISTIC(NumWedgesChanged,"Number of dbg wedges changed");

49staticcl::opt<unsigned>

50MaxNumBlocks("debug-ata-max-blocks",cl::init(10000),

51cl::desc("Maximum num basic blocks before debug info dropped"),

52cl::Hidden);

53/// Option for debugging the pass, determines if the memory location fragment

54/// filling happens after generating the variable locations.

55staticcl::opt<bool>EnableMemLocFragFill("mem-loc-frag-fill",cl::init(true),

56cl::Hidden);

57/// Print the results of the analysis. Respects -filter-print-funcs.

58staticcl::opt<bool>PrintResults("print-debug-ata",cl::init(false),

59cl::Hidden);

61/// Coalesce adjacent dbg locs describing memory locations that have contiguous

62/// fragments. This reduces the cost of LiveDebugValues which does SSA

63/// construction for each explicitly stated variable fragment.

64staticcl::opt<cl::boolOrDefault>

65CoalesceAdjacentFragmentsOpt("debug-ata-coalesce-frags",cl::Hidden);

67// Implicit conversions are disabled for enum class types, so unfortunately we

68// need to create a DenseMapInfo wrapper around the specified underlying type.

69template <>structllvm::DenseMapInfo<VariableID> {

70usingWrapped =DenseMapInfo<unsigned>;

71staticinlineVariableID getEmptyKey() {

72returnstatic_cast<VariableID>(Wrapped::getEmptyKey());

73 }

74staticinlineVariableID getTombstoneKey() {

75returnstatic_cast<VariableID>(Wrapped::getTombstoneKey());

76 }

77staticunsignedgetHashValue(constVariableID &Val) {

78return Wrapped::getHashValue(static_cast<unsigned>(Val));

79 }

80staticboolisEqual(constVariableID &LHS,constVariableID &RHS) {

81returnLHS ==RHS;

82 }

83};

85usingVarLocInsertPt =PointerUnion<const Instruction *, const DbgRecord *>;

87namespacestd {

88template <>structhash<VarLocInsertPt> {

89usingargument_type =VarLocInsertPt;

90usingresult_type = std::size_t;

92result_type operator()(constargument_type &Arg) const{

93return std::hash<void *>()(Arg.getOpaqueValue());

94 }

95};

96}// namespace std

98/// Helper class to build FunctionVarLocs, since that class isn't easy to

99/// modify. TODO: There's not a great deal of value in the split, it could be

100/// worth merging the two classes.

101classFunctionVarLocsBuilder {

102friendFunctionVarLocs;

103UniqueVector<DebugVariable> Variables;

104// Use an unordered_map so we don't invalidate iterators after

105// insert/modifications.

106 std::unordered_map<VarLocInsertPt, SmallVector<VarLocInfo>> VarLocsBeforeInst;

107

108SmallVector<VarLocInfo> SingleLocVars;

109

110public:

111unsignedgetNumVariables() const{return Variables.size(); }

112

113 /// Find or insert \p V and return the ID.

114VariableID insertVariable(DebugVariable V) {

115returnstatic_cast<VariableID>(Variables.insert(V));

116 }

117

118 /// Get a variable from its \p ID.

119constDebugVariable &getVariable(VariableID ID) const{

120return Variables[static_cast<unsigned>(ID)];

121 }

122

123 /// Return ptr to wedge of defs or nullptr if no defs come just before /p

124 /// Before.

125constSmallVectorImpl<VarLocInfo> *getWedge(VarLocInsertPt Before) const{

126auto R = VarLocsBeforeInst.find(Before);

127if (R == VarLocsBeforeInst.end())

128returnnullptr;

129return &R->second;

130 }

131

132 /// Replace the defs that come just before /p Before with /p Wedge.

133voidsetWedge(VarLocInsertPt Before,SmallVector<VarLocInfo> &&Wedge) {

134 VarLocsBeforeInst[Before] = std::move(Wedge);

135 }

136

137 /// Add a def for a variable that is valid for its lifetime.

138voidaddSingleLocVar(DebugVariable Var,DIExpression *Expr,DebugLoc DL,

139RawLocationWrapper R) {

140VarLocInfo VarLoc;

141 VarLoc.VariableID =insertVariable(Var);

142 VarLoc.Expr = Expr;

143 VarLoc.DL =DL;

144 VarLoc.Values = R;

145 SingleLocVars.emplace_back(VarLoc);

146 }

147

148 /// Add a def to the wedge of defs just before /p Before.

149voidaddVarLoc(VarLocInsertPt Before,DebugVariable Var,DIExpression *Expr,

150DebugLoc DL,RawLocationWrapper R) {

151VarLocInfo VarLoc;

152 VarLoc.VariableID =insertVariable(Var);

153 VarLoc.Expr = Expr;

154 VarLoc.DL =DL;

155 VarLoc.Values = R;

156 VarLocsBeforeInst[Before].emplace_back(VarLoc);

157 }

158};

159

160voidFunctionVarLocs::print(raw_ostream &OS,constFunction &Fn) const{

161// Print the variable table first. TODO: Sorting by variable could make the

162// output more stable?

163unsigned Counter = -1;

164OS <<"=== Variables ===\n";

165for (constDebugVariable &V : Variables) {

166 ++Counter;

167// Skip first entry because it is a dummy entry.

168if (Counter == 0) {

169continue;

170 }

171OS <<"[" << Counter <<"] " << V.getVariable()->getName();

172if (autoF = V.getFragment())

173OS <<" bits [" <<F->OffsetInBits <<", "

174 <<F->OffsetInBits +F->SizeInBits <<")";

175if (constauto *IA = V.getInlinedAt())

176OS <<" inlined-at " << *IA;

177OS <<"\n";

178 }

179

180auto PrintLoc = [&OS](constVarLocInfo &Loc) {

181OS <<"DEF Var=[" << (unsigned)Loc.VariableID <<"]"

182 <<" Expr=" << *Loc.Expr <<" Values=(";

183for (auto *Op : Loc.Values.location_ops()) {

184errs() <<Op->getName() <<" ";

185 }

186errs() <<")\n";

187 };

188

189// Print the single location variables.

190OS <<"=== Single location vars ===\n";

191for (auto It =single_locs_begin(),End =single_locs_end(); It !=End;

192 ++It) {

193 PrintLoc(*It);

194 }

195

196// Print the non-single-location defs in line with IR.

197OS <<"=== In-line variable defs ===";

198for (constBasicBlock &BB : Fn) {

199OS <<"\n" << BB.getName() <<":\n";

200for (constInstruction &I : BB) {

201for (auto It =locs_begin(&I),End =locs_end(&I); It !=End; ++It) {

202 PrintLoc(*It);

203 }

204OS <<I <<"\n";

205 }

206 }

207}

208

209voidFunctionVarLocs::init(FunctionVarLocsBuilder &Builder) {

210// Add the single-location variables first.

211for (constauto &VarLoc : Builder.SingleLocVars)

212 VarLocRecords.emplace_back(VarLoc);

213// Mark the end of the section.

214 SingleVarLocEnd = VarLocRecords.size();

215

216// Insert a contiguous block of VarLocInfos for each instruction, mapping it

217// to the start and end position in the vector with VarLocsBeforeInst. This

218// block includes VarLocs for any DbgVariableRecords attached to that

219// instruction.

220for (auto &P : Builder.VarLocsBeforeInst) {

221// Process VarLocs attached to a DbgRecord alongside their marker

222// Instruction.

223if (isa<const DbgRecord *>(P.first))

224continue;

225constInstruction *I = cast<const Instruction *>(P.first);

226unsigned BlockStart = VarLocRecords.size();

227// Any VarLocInfos attached to a DbgRecord should now be remapped to their

228// marker Instruction, in order of DbgRecord appearance and prior to any

229// VarLocInfos attached directly to that instruction.

230for (constDbgVariableRecord &DVR :filterDbgVars(I->getDbgRecordRange())) {

231// Even though DVR defines a variable location, VarLocsBeforeInst can

232// still be empty if that VarLoc was redundant.

233auto It = Builder.VarLocsBeforeInst.find(&DVR);

234if (It == Builder.VarLocsBeforeInst.end())

235continue;

236for (constVarLocInfo &VarLoc : It->second)

237 VarLocRecords.emplace_back(VarLoc);

238 }

239for (constVarLocInfo &VarLoc :P.second)

240 VarLocRecords.emplace_back(VarLoc);

241unsigned BlockEnd = VarLocRecords.size();

242// Record the start and end indices.

243if (BlockEnd != BlockStart)

244 VarLocsBeforeInst[I] = {BlockStart, BlockEnd};

245 }

246

247// Copy the Variables vector from the builder's UniqueVector.

248assert(Variables.empty() &&"Expect clear before init");

249// UniqueVectors IDs are one-based (which means the VarLocInfo VarID values

250// are one-based) so reserve an extra and insert a dummy.

251 Variables.reserve(Builder.Variables.size() + 1);

252 Variables.push_back(DebugVariable(nullptr, std::nullopt,nullptr));

253 Variables.append(Builder.Variables.begin(), Builder.Variables.end());

254}

255

256voidFunctionVarLocs::clear() {

257 Variables.clear();

258 VarLocRecords.clear();

259 VarLocsBeforeInst.clear();

260 SingleVarLocEnd = 0;

261}

262

263/// Walk backwards along constant GEPs and bitcasts to the base storage from \p

264/// Start as far as possible. Prepend \Expression with the offset and append it

265/// with a DW_OP_deref that haes been implicit until now. Returns the walked-to

266/// value and modified expression.

267static std::pair<Value *, DIExpression *>

268walkToAllocaAndPrependOffsetDeref(constDataLayout &DL,Value *Start,

269DIExpression *Expression) {

270APInt OffsetInBytes(DL.getTypeSizeInBits(Start->getType()),false);

271Value *End =

272 Start->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetInBytes);

273SmallVector<uint64_t, 3> Ops;

274if (OffsetInBytes.getBoolValue()) {

275 Ops = {dwarf::DW_OP_plus_uconst, OffsetInBytes.getZExtValue()};

276Expression =DIExpression::prependOpcodes(

277Expression, Ops,/*StackValue=*/false,/*EntryValue=*/false);

278 }

279Expression =DIExpression::append(Expression, {dwarf::DW_OP_deref});

280return {End,Expression};

281}

282

283/// Extract the offset used in \p DIExpr. Returns std::nullopt if the expression

284/// doesn't explicitly describe a memory location with DW_OP_deref or if the

285/// expression is too complex to interpret.

286static std::optional<int64_t>

287getDerefOffsetInBytes(constDIExpression *DIExpr) {

288 int64_tOffset = 0;

289constunsigned NumElements = DIExpr->getNumElements();

290constauto Elements = DIExpr->getElements();

291unsigned ExpectedDerefIdx = 0;

292// Extract the offset.

293if (NumElements > 2 && Elements[0] == dwarf::DW_OP_plus_uconst) {

294Offset = Elements[1];

295 ExpectedDerefIdx = 2;

296 }elseif (NumElements > 3 && Elements[0] == dwarf::DW_OP_constu) {

297 ExpectedDerefIdx = 3;

298if (Elements[2] == dwarf::DW_OP_plus)

299Offset = Elements[1];

300elseif (Elements[2] == dwarf::DW_OP_minus)

301Offset = -Elements[1];

302else

303return std::nullopt;

304 }

305

306// If that's all there is it means there's no deref.

307if (ExpectedDerefIdx >= NumElements)

308return std::nullopt;

309

310// Check the next element is DW_OP_deref - otherwise this is too complex or

311// isn't a deref expression.

312if (Elements[ExpectedDerefIdx] != dwarf::DW_OP_deref)

313return std::nullopt;

314

315// Check the final operation is either the DW_OP_deref or is a fragment.

316if (NumElements == ExpectedDerefIdx + 1)

317returnOffset;// Ends with deref.

318unsigned ExpectedFragFirstIdx = ExpectedDerefIdx + 1;

319unsigned ExpectedFragFinalIdx = ExpectedFragFirstIdx + 2;

320if (NumElements == ExpectedFragFinalIdx + 1 &&

321 Elements[ExpectedFragFirstIdx] ==dwarf::DW_OP_LLVM_fragment)

322returnOffset;// Ends with deref + fragment.

323

324// Don't bother trying to interpret anything more complex.

325return std::nullopt;

326}

327

328/// A whole (unfragmented) source variable.

329usingDebugAggregate = std::pair<const DILocalVariable *, const DILocation *>;

330staticDebugAggregate getAggregate(constDbgVariableIntrinsic *DII) {

331returnDebugAggregate(DII->getVariable(), DII->getDebugLoc().getInlinedAt());

332}

333staticDebugAggregate getAggregate(constDebugVariable &Var) {

334returnDebugAggregate(Var.getVariable(), Var.getInlinedAt());

335}

336

337staticboolshouldCoalesceFragments(Function &F) {

338// Enabling fragment coalescing reduces compiler run time when instruction

339// referencing is enabled. However, it may cause LiveDebugVariables to create

340// incorrect locations. Since instruction-referencing mode effectively

341// bypasses LiveDebugVariables we only enable coalescing if the cl::opt flag

342// has not been explicitly set and instruction-referencing is turned on.

343switch (CoalesceAdjacentFragmentsOpt) {

344casecl::boolOrDefault::BOU_UNSET:

345returndebuginfoShouldUseDebugInstrRef(

346Triple(F.getParent()->getTargetTriple()));

347casecl::boolOrDefault::BOU_TRUE:

348returntrue;

349casecl::boolOrDefault::BOU_FALSE:

350returnfalse;

351 }

352llvm_unreachable("Unknown boolOrDefault value");

353}

354

355namespace{

356/// In dwarf emission, the following sequence

357/// 1. dbg.value ... Fragment(0, 64)

358/// 2. dbg.value ... Fragment(0, 32)

359/// effectively sets Fragment(32, 32) to undef (each def sets all bits not in

360/// the intersection of the fragments to having "no location"). This makes

361/// sense for implicit location values because splitting the computed values

362/// could be troublesome, and is probably quite uncommon. When we convert

363/// dbg.assigns to dbg.value+deref this kind of thing is common, and describing

364/// a location (memory) rather than a value means we don't need to worry about

365/// splitting any values, so we try to recover the rest of the fragment

366/// location here.

367/// This class performs a(nother) dataflow analysis over the function, adding

368/// variable locations so that any bits of a variable with a memory location

369/// have that location explicitly reinstated at each subsequent variable

370/// location definition that that doesn't overwrite those bits. i.e. after a

371/// variable location def, insert new defs for the memory location with

372/// fragments for the difference of "all bits currently in memory" and "the

373/// fragment of the second def".

374classMemLocFragmentFill {

375Function &Fn;

376FunctionVarLocsBuilder *FnVarLocs;

377constDenseSet<DebugAggregate> *VarsWithStackSlot;

378bool CoalesceAdjacentFragments;

379

380// 0 = no memory location.

381usingBaseAddress =unsigned;

382usingOffsetInBitsTy =unsigned;

383usingFragTraits =IntervalMapHalfOpenInfo<OffsetInBitsTy>;

384usingFragsInMemMap =IntervalMap<

385 OffsetInBitsTy, BaseAddress,

386IntervalMapImpl::NodeSizer<OffsetInBitsTy, BaseAddress>::LeafSize,

387 FragTraits>;

388 FragsInMemMap::Allocator IntervalMapAlloc;

389usingVarFragMap =DenseMap<unsigned, FragsInMemMap>;

390

391 /// IDs for memory location base addresses in maps. Use 0 to indicate that

392 /// there's no memory location.

393UniqueVector<RawLocationWrapper> Bases;

394UniqueVector<DebugAggregate>Aggregates;

395DenseMap<const BasicBlock *, VarFragMap> LiveIn;

396DenseMap<const BasicBlock *, VarFragMap> LiveOut;

397

398structFragMemLoc {

399unsigned Var;

400unsignedBase;

401unsigned OffsetInBits;

402unsigned SizeInBits;

403DebugLoc DL;

404 };

405usingInsertMap =MapVector<VarLocInsertPt, SmallVector<FragMemLoc>>;

406

407 /// BBInsertBeforeMap holds a description for the set of location defs to be

408 /// inserted after the analysis is complete. It is updated during the dataflow

409 /// and the entry for a block is CLEARED each time it is (re-)visited. After

410 /// the dataflow is complete, each block entry will contain the set of defs

411 /// calculated during the final (fixed-point) iteration.

412DenseMap<const BasicBlock *, InsertMap> BBInsertBeforeMap;

413

414staticbool intervalMapsAreEqual(const FragsInMemMap &A,

415const FragsInMemMap &B) {

416auto AIt =A.begin(), AEnd =A.end();

417auto BIt =B.begin(), BEnd =B.end();

418for (; AIt != AEnd; ++AIt, ++BIt) {

419if (BIt == BEnd)

420returnfalse;// B has fewer elements than A.

421if (AIt.start() != BIt.start() || AIt.stop() != BIt.stop())

422returnfalse;// Interval is different.

423if (*AIt != *BIt)

424returnfalse;// Value at interval is different.

425 }

426// AIt == AEnd. Check BIt is also now at end.

427return BIt == BEnd;

428 }

429

430staticbool varFragMapsAreEqual(const VarFragMap &A,const VarFragMap &B) {

431if (A.size() !=B.size())

432returnfalse;

433for (constauto &APair :A) {

434auto BIt =B.find(APair.first);

435if (BIt ==B.end())

436returnfalse;

437if (!intervalMapsAreEqual(APair.second, BIt->second))

438returnfalse;

439 }

440returntrue;

441 }

442

443 /// Return a string for the value that \p BaseID represents.

444 std::stringtoString(unsigned BaseID) {

445if (BaseID)

446return Bases[BaseID].getVariableLocationOp(0)->getName().str();

447else

448return"None";

449 }

450

451 /// Format string describing an FragsInMemMap (IntervalMap) interval.

452 std::stringtoString(FragsInMemMap::const_iterator It,bool Newline =true) {

453 std::stringString;

454 std::stringstream S(String);

455if (It.valid()) {

456 S <<"[" << It.start() <<", " << It.stop()

457 <<"): " <<toString(It.value());

458 }else {

459 S <<"invalid iterator (end)";

460 }

461if (Newline)

462 S <<"\n";

463return S.str();

464 };

465

466 FragsInMemMap meetFragments(const FragsInMemMap &A,const FragsInMemMap &B) {

467 FragsInMemMapResult(IntervalMapAlloc);

468for (auto AIt =A.begin(), AEnd =A.end(); AIt != AEnd; ++AIt) {

469LLVM_DEBUG(dbgs() <<"a " <<toString(AIt));

470// This is basically copied from process() and inverted (process is

471// performing something like a union whereas this is more of an

472// intersect).

473

474// There's no work to do if interval `a` overlaps no fragments in map `B`.

475if (!B.overlaps(AIt.start(), AIt.stop()))

476continue;

477

478// Does StartBit intersect an existing fragment?

479auto FirstOverlap =B.find(AIt.start());

480assert(FirstOverlap !=B.end());

481bool IntersectStart = FirstOverlap.start() < AIt.start();

482LLVM_DEBUG(dbgs() <<"- FirstOverlap " <<toString(FirstOverlap,false)

483 <<", IntersectStart: " << IntersectStart <<"\n");

484

485// Does EndBit intersect an existing fragment?

486auto LastOverlap =B.find(AIt.stop());

487bool IntersectEnd =

488 LastOverlap !=B.end() && LastOverlap.start() < AIt.stop();

489LLVM_DEBUG(dbgs() <<"- LastOverlap " <<toString(LastOverlap,false)

490 <<", IntersectEnd: " << IntersectEnd <<"\n");

491

492// Check if both ends of `a` intersect the same interval `b`.

493if (IntersectStart && IntersectEnd && FirstOverlap == LastOverlap) {

494// Insert `a` (`a` is contained in `b`) if the values match.

495// [ a ]

496// [ - b - ]

497// -

498// [ r ]

499LLVM_DEBUG(dbgs() <<"- a is contained within "

500 <<toString(FirstOverlap));

501if (*AIt && *AIt == *FirstOverlap)

502Result.insert(AIt.start(), AIt.stop(), *AIt);

503 }else {

504// There's an overlap but `a` is not fully contained within

505// `b`. Shorten any end-point intersections.

506// [ - a - ]

507// [ - b - ]

508// -

509// [ r ]

510auto Next = FirstOverlap;

511if (IntersectStart) {

512LLVM_DEBUG(dbgs() <<"- insert intersection of a and "

513 <<toString(FirstOverlap));

514if (*AIt && *AIt == *FirstOverlap)

515Result.insert(AIt.start(), FirstOverlap.stop(), *AIt);

516 ++Next;

517 }

518// [ - a - ]

519// [ - b - ]

520// -

521// [ r ]

522if (IntersectEnd) {

523LLVM_DEBUG(dbgs() <<"- insert intersection of a and "

524 <<toString(LastOverlap));

525if (*AIt && *AIt == *LastOverlap)

526Result.insert(LastOverlap.start(), AIt.stop(), *AIt);

527 }

528

529// Insert all intervals in map `B` that are contained within interval

530// `a` where the values match.

531// [ - - a - - ]

532// [ b1 ] [ b2 ]

533// -

534// [ r1 ] [ r2 ]

535while (Next !=B.end() && Next.start() < AIt.stop() &&

536 Next.stop() <= AIt.stop()) {

537LLVM_DEBUG(dbgs()

538 <<"- insert intersection of a and " <<toString(Next));

539if (*AIt && *AIt == *Next)

540Result.insert(Next.start(), Next.stop(), *Next);

541 ++Next;

542 }

543 }

544 }

545returnResult;

546 }

547

548 /// Meet \p A and \p B, storing the result in \p A.

549void meetVars(VarFragMap &A,const VarFragMap &B) {

550// Meet A and B.

551//

552// Result = meet(a, b) for a in A, b in B where Var(a) == Var(b)

553for (auto It =A.begin(),End =A.end(); It !=End; ++It) {

554unsigned AVar = It->first;

555 FragsInMemMap &AFrags = It->second;

556auto BIt =B.find(AVar);

557if (BIt ==B.end()) {

558A.erase(It);

559continue;// Var has no bits defined in B.

560 }

561LLVM_DEBUG(dbgs() <<"meet fragment maps for "

562 <<Aggregates[AVar].first->getName() <<"\n");

563 AFrags = meetFragments(AFrags, BIt->second);

564 }

565 }

566

567bool meet(constBasicBlock &BB,

568constSmallPtrSet<BasicBlock *, 16> &Visited) {

569LLVM_DEBUG(dbgs() <<"meet block info from preds of " << BB.getName()

570 <<"\n");

571

572 VarFragMap BBLiveIn;

573bool FirstMeet =true;

574// LiveIn locs for BB is the meet of the already-processed preds' LiveOut

575// locs.

576for (constBasicBlock *Pred :predecessors(&BB)) {

577// Ignore preds that haven't been processed yet. This is essentially the

578// same as initialising all variables to implicit top value (⊤) which is

579// the identity value for the meet operation.

580if (!Visited.count(Pred))

581continue;

582

583auto PredLiveOut = LiveOut.find(Pred);

584assert(PredLiveOut != LiveOut.end());

585

586if (FirstMeet) {

587LLVM_DEBUG(dbgs() <<"BBLiveIn = " << Pred->getName() <<"\n");

588 BBLiveIn = PredLiveOut->second;

589 FirstMeet =false;

590 }else {

591LLVM_DEBUG(dbgs() <<"BBLiveIn = meet BBLiveIn, " << Pred->getName()

592 <<"\n");

593 meetVars(BBLiveIn, PredLiveOut->second);

594 }

595

596// An empty set is ⊥ for the intersect-like meet operation. If we've

597// already got ⊥ there's no need to run the code - we know the result is

598// ⊥ since `meet(a, ⊥) = ⊥`.

599if (BBLiveIn.size() == 0)

600break;

601 }

602

603auto CurrentLiveInEntry = LiveIn.find(&BB);

604// If there's no LiveIn entry for the block yet, add it.

605if (CurrentLiveInEntry == LiveIn.end()) {

606LLVM_DEBUG(dbgs() <<"change=true (first) on meet on " << BB.getName()

607 <<"\n");

608 LiveIn[&BB] = std::move(BBLiveIn);

609return/*Changed=*/true;

610 }

611

612// If the LiveIn set has changed (expensive check) update it and return

613// true.

614if (!varFragMapsAreEqual(BBLiveIn, CurrentLiveInEntry->second)) {

615LLVM_DEBUG(dbgs() <<"change=true on meet on " << BB.getName() <<"\n");

616 CurrentLiveInEntry->second = std::move(BBLiveIn);

617return/*Changed=*/true;

618 }

619

620LLVM_DEBUG(dbgs() <<"change=false on meet on " << BB.getName() <<"\n");

621return/*Changed=*/false;

622 }

623

624void insertMemLoc(BasicBlock &BB,VarLocInsertPt Before,unsigned Var,

625unsigned StartBit,unsigned EndBit,unsignedBase,

626DebugLoc DL) {

627assert(StartBit < EndBit &&"Cannot create fragment of size <= 0");

628if (!Base)

629return;

630 FragMemLoc Loc;

631 Loc.Var = Var;

632 Loc.OffsetInBits = StartBit;

633 Loc.SizeInBits = EndBit - StartBit;

634assert(Base &&"Expected a non-zero ID for Base address");

635 Loc.Base =Base;

636 Loc.DL =DL;

637 BBInsertBeforeMap[&BB][Before].push_back(Loc);

638LLVM_DEBUG(dbgs() <<"Add mem def for " <<Aggregates[Var].first->getName()

639 <<" bits [" << StartBit <<", " << EndBit <<")\n");

640 }

641

642 /// Inserts a new dbg def if the interval found when looking up \p StartBit

643 /// in \p FragMap starts before \p StartBit or ends after \p EndBit (which

644 /// indicates - assuming StartBit->EndBit has just been inserted - that the

645 /// slice has been coalesced in the map).

646void coalesceFragments(BasicBlock &BB,VarLocInsertPt Before,unsigned Var,

647unsigned StartBit,unsigned EndBit,unsignedBase,

648DebugLoc DL,const FragsInMemMap &FragMap) {

649if (!CoalesceAdjacentFragments)

650return;

651// We've inserted the location into the map. The map will have coalesced

652// adjacent intervals (variable fragments) that describe the same memory

653// location. Use this knowledge to insert a debug location that describes

654// that coalesced fragment. This may eclipse other locs we've just

655// inserted. This is okay as redundant locs will be cleaned up later.

656auto CoalescedFrag = FragMap.find(StartBit);

657// Bail if no coalescing has taken place.

658if (CoalescedFrag.start() == StartBit && CoalescedFrag.stop() == EndBit)

659return;

660

661LLVM_DEBUG(dbgs() <<"- Insert loc for bits " << CoalescedFrag.start()

662 <<" to " << CoalescedFrag.stop() <<"\n");

663 insertMemLoc(BB,Before, Var, CoalescedFrag.start(), CoalescedFrag.stop(),

664Base,DL);

665 }

666

667void addDef(constVarLocInfo &VarLoc,VarLocInsertPt Before,BasicBlock &BB,

668 VarFragMap &LiveSet) {

669DebugVariable DbgVar = FnVarLocs->getVariable(VarLoc.VariableID);

670if (skipVariable(DbgVar.getVariable()))

671return;

672// Don't bother doing anything for this variables if we know it's fully

673// promoted. We're only interested in variables that (sometimes) live on

674// the stack here.

675if (!VarsWithStackSlot->count(getAggregate(DbgVar)))

676return;

677unsigned Var =Aggregates.insert(

678DebugAggregate(DbgVar.getVariable(), VarLoc.DL.getInlinedAt()));

679

680// [StartBit: EndBit) are the bits affected by this def.

681constDIExpression *DIExpr = VarLoc.Expr;

682unsigned StartBit;

683unsigned EndBit;

684if (auto Frag = DIExpr->getFragmentInfo()) {

685 StartBit = Frag->OffsetInBits;

686 EndBit = StartBit + Frag->SizeInBits;

687 }else {

688assert(static_cast<bool>(DbgVar.getVariable()->getSizeInBits()));

689 StartBit = 0;

690 EndBit = *DbgVar.getVariable()->getSizeInBits();

691 }

692

693// We will only fill fragments for simple memory-describing dbg.value

694// intrinsics. If the fragment offset is the same as the offset from the

695// base pointer, do The Thing, otherwise fall back to normal dbg.value

696// behaviour. AssignmentTrackingLowering has generated DIExpressions

697// written in terms of the base pointer.

698// TODO: Remove this condition since the fragment offset doesn't always

699// equal the offset from base pointer (e.g. for a SROA-split variable).

700constauto DerefOffsetInBytes =getDerefOffsetInBytes(DIExpr);

701constunsignedBase =

702 DerefOffsetInBytes && *DerefOffsetInBytes * 8 == StartBit

703 ? Bases.insert(VarLoc.Values)

704 : 0;

705LLVM_DEBUG(dbgs() <<"DEF " << DbgVar.getVariable()->getName() <<" ["

706 << StartBit <<", " << EndBit <<"): " <<toString(Base)

707 <<"\n");

708

709// First of all, any locs that use mem that are disrupted need reinstating.

710// Unfortunately, IntervalMap doesn't let us insert intervals that overlap

711// with existing intervals so this code involves a lot of fiddling around

712// with intervals to do that manually.

713auto FragIt = LiveSet.find(Var);

714

715// Check if the variable does not exist in the map.

716if (FragIt == LiveSet.end()) {

717// Add this variable to the BB map.

718autoP = LiveSet.try_emplace(Var, FragsInMemMap(IntervalMapAlloc));

719assert(P.second &&"Var already in map?");

720// Add the interval to the fragment map.

721P.first->second.insert(StartBit, EndBit,Base);

722return;

723 }

724// The variable has an entry in the map.

725

726 FragsInMemMap &FragMap = FragIt->second;

727// First check the easy case: the new fragment `f` doesn't overlap with any

728// intervals.

729if (!FragMap.overlaps(StartBit, EndBit)) {

730LLVM_DEBUG(dbgs() <<"- No overlaps\n");

731 FragMap.insert(StartBit, EndBit,Base);

732 coalesceFragments(BB,Before, Var, StartBit, EndBit,Base, VarLoc.DL,

733 FragMap);

734return;

735 }

736// There is at least one overlap.

737

738// Does StartBit intersect an existing fragment?

739auto FirstOverlap = FragMap.find(StartBit);

740assert(FirstOverlap != FragMap.end());

741bool IntersectStart = FirstOverlap.start() < StartBit;

742

743// Does EndBit intersect an existing fragment?

744auto LastOverlap = FragMap.find(EndBit);

745bool IntersectEnd = LastOverlap.valid() && LastOverlap.start() < EndBit;

746

747// Check if both ends of `f` intersect the same interval `i`.

748if (IntersectStart && IntersectEnd && FirstOverlap == LastOverlap) {

749LLVM_DEBUG(dbgs() <<"- Intersect single interval @ both ends\n");

750// Shorten `i` so that there's space to insert `f`.

751// [ f ]

752// [ - i - ]

753// +

754// [ i ][ f ][ i ]

755

756// Save values for use after inserting a new interval.

757auto EndBitOfOverlap = FirstOverlap.stop();

758unsigned OverlapValue = FirstOverlap.value();

759

760// Shorten the overlapping interval.

761 FirstOverlap.setStop(StartBit);

762 insertMemLoc(BB,Before, Var, FirstOverlap.start(), StartBit,

763 OverlapValue, VarLoc.DL);

764

765// Insert a new interval to represent the end part.

766 FragMap.insert(EndBit, EndBitOfOverlap, OverlapValue);

767 insertMemLoc(BB,Before, Var, EndBit, EndBitOfOverlap, OverlapValue,

768 VarLoc.DL);

769

770// Insert the new (middle) fragment now there is space.

771 FragMap.insert(StartBit, EndBit,Base);

772 }else {

773// There's an overlap but `f` may not be fully contained within

774// `i`. Shorten any end-point intersections so that we can then

775// insert `f`.

776// [ - f - ]

777// [ - i - ]

778// | |

779// [ i ]

780// Shorten any end-point intersections.

781if (IntersectStart) {

782LLVM_DEBUG(dbgs() <<"- Intersect interval at start\n");

783// Split off at the intersection.

784 FirstOverlap.setStop(StartBit);

785 insertMemLoc(BB,Before, Var, FirstOverlap.start(), StartBit,

786 *FirstOverlap, VarLoc.DL);

787 }

788// [ - f - ]

789// [ - i - ]

790// | |

791// [ i ]

792if (IntersectEnd) {

793LLVM_DEBUG(dbgs() <<"- Intersect interval at end\n");

794// Split off at the intersection.

795 LastOverlap.setStart(EndBit);

796 insertMemLoc(BB,Before, Var, EndBit, LastOverlap.stop(), *LastOverlap,

797 VarLoc.DL);

798 }

799

800LLVM_DEBUG(dbgs() <<"- Erase intervals contained within\n");

801// FirstOverlap and LastOverlap have been shortened such that they're

802// no longer overlapping with [StartBit, EndBit). Delete any overlaps

803// that remain (these will be fully contained within `f`).

804// [ - f - ] }

805// [ - i - ] } Intersection shortening that has happened above.

806// | | }

807// [ i ] }

808// -----------------

809// [i2 ] } Intervals fully contained within `f` get erased.

810// -----------------

811// [ - f - ][ i ] } Completed insertion.

812auto It = FirstOverlap;

813if (IntersectStart)

814 ++It;// IntersectStart: first overlap has been shortened.

815while (It.valid() && It.start() >= StartBit && It.stop() <= EndBit) {

816LLVM_DEBUG(dbgs() <<"- Erase " <<toString(It));

817 It.erase();// This increments It after removing the interval.

818 }

819// We've dealt with all the overlaps now!

820assert(!FragMap.overlaps(StartBit, EndBit));

821LLVM_DEBUG(dbgs() <<"- Insert DEF into now-empty space\n");

822 FragMap.insert(StartBit, EndBit,Base);

823 }

824

825 coalesceFragments(BB,Before, Var, StartBit, EndBit,Base, VarLoc.DL,

826 FragMap);

827 }

828

829bool skipVariable(constDILocalVariable *V) {return !V->getSizeInBits(); }

830

831void process(BasicBlock &BB, VarFragMap &LiveSet) {

832 BBInsertBeforeMap[&BB].clear();

833for (auto &I : BB) {

834for (DbgVariableRecord &DVR :filterDbgVars(I.getDbgRecordRange())) {

835if (constauto *Locs = FnVarLocs->getWedge(&DVR)) {

836for (constVarLocInfo &Loc : *Locs) {

837 addDef(Loc, &DVR, *I.getParent(), LiveSet);

838 }

839 }

840 }

841if (constauto *Locs = FnVarLocs->getWedge(&I)) {

842for (constVarLocInfo &Loc : *Locs) {

843 addDef(Loc, &I, *I.getParent(), LiveSet);

844 }

845 }

846 }

847 }

848

849public:

850 MemLocFragmentFill(Function &Fn,

851constDenseSet<DebugAggregate> *VarsWithStackSlot,

852bool CoalesceAdjacentFragments)

853 : Fn(Fn), VarsWithStackSlot(VarsWithStackSlot),

854 CoalesceAdjacentFragments(CoalesceAdjacentFragments) {}

855

856 /// Add variable locations to \p FnVarLocs so that any bits of a variable

857 /// with a memory location have that location explicitly reinstated at each

858 /// subsequent variable location definition that that doesn't overwrite those

859 /// bits. i.e. after a variable location def, insert new defs for the memory

860 /// location with fragments for the difference of "all bits currently in

861 /// memory" and "the fragment of the second def". e.g.

862 ///

863 /// Before:

864 ///

865 /// var x bits 0 to 63: value in memory

866 /// more instructions

867 /// var x bits 0 to 31: value is %0

868 ///

869 /// After:

870 ///

871 /// var x bits 0 to 63: value in memory

872 /// more instructions

873 /// var x bits 0 to 31: value is %0

874 /// var x bits 32 to 61: value in memory ; <-- new loc def

875 ///

876voidrun(FunctionVarLocsBuilder *FnVarLocs) {

877if (!EnableMemLocFragFill)

878return;

879

880 this->FnVarLocs = FnVarLocs;

881

882// Prepare for traversal.

883//

884ReversePostOrderTraversal<Function *> RPOT(&Fn);

885 std::priority_queue<unsigned int, std::vector<unsigned int>,

886 std::greater<unsigned int>>

887 Worklist;

888 std::priority_queue<unsigned int, std::vector<unsigned int>,

889 std::greater<unsigned int>>

890 Pending;

891DenseMap<unsigned int, BasicBlock *> OrderToBB;

892DenseMap<BasicBlock *, unsigned int> BBToOrder;

893 {// Init OrderToBB and BBToOrder.

894unsignedint RPONumber = 0;

895for (BasicBlock *BB : RPOT) {

896 OrderToBB[RPONumber] = BB;

897 BBToOrder[BB] = RPONumber;

898 Worklist.push(RPONumber);

899 ++RPONumber;

900 }

901 LiveIn.init(RPONumber);

902 LiveOut.init(RPONumber);

903 }

904

905// Perform the traversal.

906//

907// This is a standard "intersect of predecessor outs" dataflow problem. To

908// solve it, we perform meet() and process() using the two worklist method

909// until the LiveIn data for each block becomes unchanging.

910//

911// This dataflow is essentially working on maps of sets and at each meet we

912// intersect the maps and the mapped sets. So, initialized live-in maps

913// monotonically decrease in value throughout the dataflow.

914SmallPtrSet<BasicBlock *, 16> Visited;

915while (!Worklist.empty() || !Pending.empty()) {

916// We track what is on the pending worklist to avoid inserting the same

917// thing twice. We could avoid this with a custom priority queue, but

918// this is probably not worth it.

919SmallPtrSet<BasicBlock *, 16> OnPending;

920LLVM_DEBUG(dbgs() <<"Processing Worklist\n");

921while (!Worklist.empty()) {

922BasicBlock *BB = OrderToBB[Worklist.top()];

923LLVM_DEBUG(dbgs() <<"\nPop BB " << BB->getName() <<"\n");

924 Worklist.pop();

925bool InChanged = meet(*BB, Visited);

926// Always consider LiveIn changed on the first visit.

927 InChanged |= Visited.insert(BB).second;

928if (InChanged) {

929LLVM_DEBUG(dbgs()

930 << BB->getName() <<" has new InLocs, process it\n");

931// Mutate a copy of LiveIn while processing BB. Once we've processed

932// the terminator LiveSet is the LiveOut set for BB.

933// This is an expensive copy!

934 VarFragMap LiveSet = LiveIn[BB];

935

936// Process the instructions in the block.

937 process(*BB, LiveSet);

938

939// Relatively expensive check: has anything changed in LiveOut for BB?

940if (!varFragMapsAreEqual(LiveOut[BB], LiveSet)) {

941LLVM_DEBUG(dbgs() << BB->getName()

942 <<" has new OutLocs, add succs to worklist: [ ");

943 LiveOut[BB] = std::move(LiveSet);

944for (BasicBlock *Succ :successors(BB)) {

945if (OnPending.insert(Succ).second) {

946LLVM_DEBUG(dbgs() << Succ->getName() <<" ");

947 Pending.push(BBToOrder[Succ]);

948 }

949 }

950LLVM_DEBUG(dbgs() <<"]\n");

951 }

952 }

953 }

954 Worklist.swap(Pending);

955// At this point, pending must be empty, since it was just the empty

956// worklist

957assert(Pending.empty() &&"Pending should be empty");

958 }

959

960// Insert new location defs.

961for (auto &Pair : BBInsertBeforeMap) {

962 InsertMap &Map = Pair.second;

963for (auto &Pair : Map) {

964auto InsertBefore = Pair.first;

965assert(InsertBefore &&"should never be null");

966auto FragMemLocs = Pair.second;

967auto &Ctx = Fn.getContext();

968

969for (auto &FragMemLoc : FragMemLocs) {

970DIExpression *Expr = DIExpression::get(Ctx, {});

971if (FragMemLoc.SizeInBits !=

972 *Aggregates[FragMemLoc.Var].first->getSizeInBits())

973 Expr = *DIExpression::createFragmentExpression(

974 Expr, FragMemLoc.OffsetInBits, FragMemLoc.SizeInBits);

975 Expr =DIExpression::prepend(Expr,DIExpression::DerefAfter,

976 FragMemLoc.OffsetInBits / 8);

977DebugVariable Var(Aggregates[FragMemLoc.Var].first, Expr,

978 FragMemLoc.DL.getInlinedAt());

979 FnVarLocs->addVarLoc(InsertBefore, Var, Expr, FragMemLoc.DL,

980 Bases[FragMemLoc.Base]);

981 }

982 }

983 }

984 }

985};

986

987/// AssignmentTrackingLowering encapsulates a dataflow analysis over a function

988/// that interprets assignment tracking debug info metadata and stores in IR to

989/// create a map of variable locations.

990classAssignmentTrackingLowering {

991public:

992 /// The kind of location in use for a variable, where Mem is the stack home,

993 /// Val is an SSA value or const, and None means that there is not one single

994 /// kind (either because there are multiple or because there is none; it may

995 /// prove useful to split this into two values in the future).

996 ///

997 /// LocKind is a join-semilattice with the partial order:

998 /// None > Mem, Val

999 ///

1000 /// i.e.

1001 /// join(Mem, Mem) = Mem

1002 /// join(Val, Val) = Val

1003 /// join(Mem, Val) = None

1004 /// join(None, Mem) = None

1005 /// join(None, Val) = None

1006 /// join(None, None) = None

1007 ///

1008 /// Note: the order is not `None > Val > Mem` because we're using DIAssignID

1009 /// to name assignments and are not tracking the actual stored values.

1010 /// Therefore currently there's no way to ensure that Mem values and Val

1011 /// values are the same. This could be a future extension, though it's not

1012 /// clear that many additional locations would be recovered that way in

1013 /// practice as the likelihood of this sitation arising naturally seems

1014 /// incredibly low.

1015enum class LocKind { Mem, Val,None };

1016

1017 /// An abstraction of the assignment of a value to a variable or memory

1018 /// location.

1019 ///

1020 /// An Assignment is Known or NoneOrPhi. A Known Assignment means we have a

1021 /// DIAssignID ptr that represents it. NoneOrPhi means that we don't (or

1022 /// can't) know the ID of the last assignment that took place.

1023 ///

1024 /// The Status of the Assignment (Known or NoneOrPhi) is another

1025 /// join-semilattice. The partial order is:

1026 /// NoneOrPhi > Known {id_0, id_1, ...id_N}

1027 ///

1028 /// i.e. for all values x and y where x != y:

1029 /// join(x, x) = x

1030 /// join(x, y) = NoneOrPhi

1031usingAssignRecord =PointerUnion<DbgAssignIntrinsic *, DbgVariableRecord *>;

1032structAssignment {

1033enum S { Known, NoneOrPhi }Status;

1034 /// ID of the assignment. nullptr if Status is not Known.

1035DIAssignID *ID;

1036 /// The dbg.assign that marks this dbg-def. Mem-defs don't use this field.

1037 /// May be nullptr.

1038 AssignRecordSource;

1039

1040bool isSameSourceAssignment(const Assignment &Other) const{

1041// Don't include Source in the equality check. Assignments are

1042// defined by their ID, not debug intrinsic(s).

1043return std::tie(Status,ID) == std::tie(Other.Status,Other.ID);

1044 }

1045voiddump(raw_ostream &OS) {

1046staticconstchar *LUT[] = {"Known","NoneOrPhi"};

1047OS <<LUT[Status] <<"(id=";

1048if (ID)

1049OS <<ID;

1050else

1051OS <<"null";

1052OS <<", s=";

1053if (Source.isNull())

1054OS <<"null";

1055elseif (constauto *DAI = dyn_cast<DbgAssignIntrinsic *>(Source))

1056OS << DAI;

1057else

1058 OS << cast<DbgVariableRecord *>(Source);

1059OS <<")";

1060 }

1061

1062static Assignmentmake(DIAssignID *ID,DbgAssignIntrinsic *Source) {

1063return Assignment(Known,ID, Source);

1064 }

1065static Assignmentmake(DIAssignID *ID,DbgVariableRecord *Source) {

1066assert(Source->isDbgAssign() &&

1067"Cannot make an assignment from a non-assign DbgVariableRecord");

1068return Assignment(Known,ID, Source);

1069 }

1070static Assignmentmake(DIAssignID *ID, AssignRecord Source) {

1071return Assignment(Known,ID, Source);

1072 }

1073static Assignment makeFromMemDef(DIAssignID *ID) {

1074return Assignment(Known,ID);

1075 }

1076static Assignment makeNoneOrPhi() {return Assignment(NoneOrPhi,nullptr); }

1077// Again, need a Top value?

1078 Assignment() :Status(NoneOrPhi),ID(nullptr) {}// Can we delete this?

1079 Assignment(SStatus,DIAssignID *ID) :Status(Status),ID(ID) {

1080// If the Status is Known then we expect there to be an assignment ID.

1081assert(Status == NoneOrPhi ||ID);

1082 }

1083 Assignment(SStatus,DIAssignID *ID,DbgAssignIntrinsic *Source)

1084 :Status(Status),ID(ID),Source(Source) {

1085// If the Status is Known then we expect there to be an assignment ID.

1086assert(Status == NoneOrPhi ||ID);

1087 }

1088 Assignment(SStatus,DIAssignID *ID,DbgVariableRecord *Source)

1089 :Status(Status),ID(ID),Source(Source) {

1090// If the Status is Known then we expect there to be an assignment ID.

1091assert(Status == NoneOrPhi ||ID);

1092 }

1093 Assignment(SStatus,DIAssignID *ID, AssignRecord Source)

1094 :Status(Status),ID(ID),Source(Source) {

1095// If the Status is Known then we expect there to be an assignment ID.

1096assert(Status == NoneOrPhi ||ID);

1097 }

1098 };

1099

1100usingAssignmentMap =SmallVector<Assignment>;

1101usingLocMap =SmallVector<LocKind>;

1102usingOverlapMap =DenseMap<VariableID, SmallVector<VariableID>>;

1103usingUntaggedStoreAssignmentMap =

1104DenseMap<constInstruction *,

1105SmallVector<std::pair<VariableID, at::AssignmentInfo>>>;

1106

1107private:

1108 /// The highest numbered VariableID for partially promoted variables plus 1,

1109 /// the values for which start at 1.

1110unsigned TrackedVariablesVectorSize = 0;

1111 /// Map a variable to the set of variables that it fully contains.

1112OverlapMap VarContains;

1113 /// Map untagged stores to the variable fragments they assign to. Used by

1114 /// processUntaggedInstruction.

1115 UntaggedStoreAssignmentMap UntaggedStoreVars;

1116

1117// Machinery to defer inserting dbg.values.

1118usingInstInsertMap =MapVector<VarLocInsertPt, SmallVector<VarLocInfo>>;

1119 InstInsertMap InsertBeforeMap;

1120 /// Clear the location definitions currently cached for insertion after /p

1121 /// After.

1122void resetInsertionPoint(Instruction &After);

1123void resetInsertionPoint(DbgVariableRecord &After);

1124

1125// emitDbgValue can be called with:

1126// Source=[AssignRecord|DbgValueInst*|DbgAssignIntrinsic*|DbgVariableRecord*]

1127// Since AssignRecord can be cast to one of the latter two types, and all

1128// other types have a shared interface, we use a template to handle the latter

1129// three types, and an explicit overload for AssignRecord that forwards to

1130// the template version with the right type.

1131void emitDbgValue(LocKind Kind, AssignRecord Source,VarLocInsertPt After);

1132template <typename T>

1133void emitDbgValue(LocKind Kind,constT Source,VarLocInsertPt After);

1134

1135staticbool mapsAreEqual(constBitVector &Mask,const AssignmentMap &A,

1136const AssignmentMap &B) {

1137returnllvm::all_of(Mask.set_bits(), [&](unsignedVarID) {

1138 return A[VarID].isSameSourceAssignment(B[VarID]);

1139 });

1140 }

1141

1142 /// Represents the stack and debug assignments in a block. Used to describe

1143 /// the live-in and live-out values for blocks, as well as the "current"

1144 /// value as we process each instruction in a block.

1145structBlockInfo {

1146 /// The set of variables (VariableID) being tracked in this block.

1147BitVector VariableIDsInBlock;

1148 /// Dominating assignment to memory for each variable, indexed by

1149 /// VariableID.

1150 AssignmentMap StackHomeValue;

1151 /// Dominating assignemnt to each variable, indexed by VariableID.

1152 AssignmentMap DebugValue;

1153 /// Location kind for each variable. LiveLoc indicates whether the

1154 /// dominating assignment in StackHomeValue (LocKind::Mem), DebugValue

1155 /// (LocKind::Val), or neither (LocKind::None) is valid, in that order of

1156 /// preference. This cannot be derived by inspecting DebugValue and

1157 /// StackHomeValue due to the fact that there's no distinction in

1158 /// Assignment (the class) between whether an assignment is unknown or a

1159 /// merge of multiple assignments (both are Status::NoneOrPhi). In other

1160 /// words, the memory location may well be valid while both DebugValue and

1161 /// StackHomeValue contain Assignments that have a Status of NoneOrPhi.

1162 /// Indexed by VariableID.

1163LocMap LiveLoc;

1164

1165public:

1166enum AssignmentKind {Stack,Debug };

1167const AssignmentMap &getAssignmentMap(AssignmentKind Kind) const{

1168switch (Kind) {

1169caseStack:

1170return StackHomeValue;

1171caseDebug:

1172return DebugValue;

1173 }

1174llvm_unreachable("Unknown AssignmentKind");

1175 }

1176 AssignmentMap &getAssignmentMap(AssignmentKind Kind) {

1177returnconst_cast<AssignmentMap &>(

1178const_cast<constBlockInfo *>(this)->getAssignmentMap(Kind));

1179 }

1180

1181bool isVariableTracked(VariableID Var) const{

1182return VariableIDsInBlock[static_cast<unsigned>(Var)];

1183 }

1184

1185const Assignment &getAssignment(AssignmentKind Kind,VariableID Var) const{

1186assert(isVariableTracked(Var) &&"Var not tracked in block");

1187return getAssignmentMap(Kind)[static_cast<unsigned>(Var)];

1188 }

1189

1190 LocKind getLocKind(VariableID Var) const{

1191assert(isVariableTracked(Var) &&"Var not tracked in block");

1192return LiveLoc[static_cast<unsigned>(Var)];

1193 }

1194

1195 /// Set LocKind for \p Var only: does not set LocKind for VariableIDs of

1196 /// fragments contained win \p Var.

1197void setLocKind(VariableID Var, LocKind K) {

1198 VariableIDsInBlock.set(static_cast<unsigned>(Var));

1199 LiveLoc[static_cast<unsigned>(Var)] = K;

1200 }

1201

1202 /// Set the assignment in the \p Kind assignment map for \p Var only: does

1203 /// not set the assignment for VariableIDs of fragments contained win \p

1204 /// Var.

1205void setAssignment(AssignmentKind Kind,VariableID Var,

1206const Assignment &AV) {

1207 VariableIDsInBlock.set(static_cast<unsigned>(Var));

1208 getAssignmentMap(Kind)[static_cast<unsigned>(Var)] = AV;

1209 }

1210

1211 /// Return true if there is an assignment matching \p AV in the \p Kind

1212 /// assignment map. Does consider assignments for VariableIDs of fragments

1213 /// contained win \p Var.

1214bool hasAssignment(AssignmentKind Kind,VariableID Var,

1215const Assignment &AV) const{

1216if (!isVariableTracked(Var))

1217returnfalse;

1218return AV.isSameSourceAssignment(getAssignment(Kind, Var));

1219 }

1220

1221 /// Compare every element in each map to determine structural equality

1222 /// (slow).

1223booloperator==(const BlockInfo &Other) const{

1224return VariableIDsInBlock ==Other.VariableIDsInBlock &&

1225 LiveLoc ==Other.LiveLoc &&

1226 mapsAreEqual(VariableIDsInBlock, StackHomeValue,

1227Other.StackHomeValue) &&

1228 mapsAreEqual(VariableIDsInBlock, DebugValue,Other.DebugValue);

1229 }

1230booloperator!=(const BlockInfo &Other) const{return !(*this ==Other); }

1231boolisValid() {

1232return LiveLoc.size() == DebugValue.size() &&

1233 LiveLoc.size() == StackHomeValue.size();

1234 }

1235

1236 /// Clear everything and initialise with ⊤-values for all variables.

1237voidinit(int NumVars) {

1238 StackHomeValue.clear();

1239 DebugValue.clear();

1240 LiveLoc.clear();

1241 VariableIDsInBlock =BitVector(NumVars);

1242 StackHomeValue.insert(StackHomeValue.begin(), NumVars,

1243 Assignment::makeNoneOrPhi());

1244 DebugValue.insert(DebugValue.begin(), NumVars,

1245 Assignment::makeNoneOrPhi());

1246 LiveLoc.insert(LiveLoc.begin(), NumVars, LocKind::None);

1247 }

1248

1249 /// Helper for join.

1250template <typename ElmtType,typename FnInputType>

1251staticvoid joinElmt(intIndex,SmallVector<ElmtType> &Target,

1252constSmallVector<ElmtType> &A,

1253constSmallVector<ElmtType> &B,

1254 ElmtType (*Fn)(FnInputType, FnInputType)) {

1255Target[Index] = Fn(A[Index],B[Index]);

1256 }

1257

1258 /// See comment for AssignmentTrackingLowering::joinBlockInfo.

1259static BlockInfo join(const BlockInfo &A,const BlockInfo &B,int NumVars) {

1260// Join A and B.

1261//

1262// Intersect = join(a, b) for a in A, b in B where Var(a) == Var(b)

1263// Difference = join(x, ⊤) for x where Var(x) is in A xor B

1264// Join = Intersect ∪ Difference

1265//

1266// This is achieved by performing a join on elements from A and B with

1267// variables common to both A and B (join elements indexed by var

1268// intersect), then adding ⊤-value elements for vars in A xor B. The

1269// latter part is equivalent to performing join on elements with variables

1270// in A xor B with the ⊤-value for the map element since join(x, ⊤) = ⊤.

1271// BlockInfo::init initializes all variable entries to the ⊤ value so we

1272// don't need to explicitly perform that step as Join.VariableIDsInBlock

1273// is set to the union of the variables in A and B at the end of this

1274// function.

1275 BlockInfo Join;

1276 Join.init(NumVars);

1277

1278BitVector Intersect =A.VariableIDsInBlock;

1279 Intersect &=B.VariableIDsInBlock;

1280

1281for (autoVarID : Intersect.set_bits()) {

1282 joinElmt(VarID, Join.LiveLoc,A.LiveLoc,B.LiveLoc, joinKind);

1283 joinElmt(VarID, Join.DebugValue,A.DebugValue,B.DebugValue,

1284 joinAssignment);

1285 joinElmt(VarID, Join.StackHomeValue,A.StackHomeValue,B.StackHomeValue,

1286 joinAssignment);

1287 }

1288

1289 Join.VariableIDsInBlock =A.VariableIDsInBlock;

1290 Join.VariableIDsInBlock |=B.VariableIDsInBlock;

1291assert(Join.isValid());

1292return Join;

1293 }

1294 };

1295

1296Function &Fn;

1297constDataLayout &Layout;

1298constDenseSet<DebugAggregate> *VarsWithStackSlot;

1299FunctionVarLocsBuilder *FnVarLocs;

1300DenseMap<const BasicBlock *, BlockInfo> LiveIn;

1301DenseMap<const BasicBlock *, BlockInfo> LiveOut;

1302

1303 /// Helper for process methods to track variables touched each frame.

1304DenseSet<VariableID> VarsTouchedThisFrame;

1305

1306 /// The set of variables that sometimes are not located in their stack home.

1307DenseSet<DebugAggregate> NotAlwaysStackHomed;

1308

1309VariableID getVariableID(constDebugVariable &Var) {

1310returnstatic_cast<VariableID>(FnVarLocs->insertVariable(Var));

1311 }

1312

1313 /// Join the LiveOut values of preds that are contained in \p Visited into

1314 /// LiveIn[BB]. Return True if LiveIn[BB] has changed as a result. LiveIn[BB]

1315 /// values monotonically increase. See the @link joinMethods join methods

1316 /// @endlink documentation for more info.

1317bool join(constBasicBlock &BB,constSmallPtrSet<BasicBlock *, 16> &Visited);

1318 ///@name joinMethods

1319 /// Functions that implement `join` (the least upper bound) for the

1320 /// join-semilattice types used in the dataflow. There is an explicit bottom

1321 /// value (⊥) for some types and and explicit top value (⊤) for all types.

1322 /// By definition:

1323 ///

1324 /// Join(A, B) >= A && Join(A, B) >= B

1325 /// Join(A, ⊥) = A

1326 /// Join(A, ⊤) = ⊤

1327 ///

1328 /// These invariants are important for monotonicity.

1329 ///

1330 /// For the map-type functions, all unmapped keys in an empty map are

1331 /// associated with a bottom value (⊥). This represents their values being

1332 /// unknown. Unmapped keys in non-empty maps (joining two maps with a key

1333 /// only present in one) represents either a variable going out of scope or

1334 /// dropped debug info. It is assumed the key is associated with a top value

1335 /// (⊤) in this case (unknown location / assignment).

1336 ///@{

1337static LocKind joinKind(LocKindA, LocKindB);

1338static Assignment joinAssignment(const Assignment &A,const Assignment &B);

1339 BlockInfo joinBlockInfo(const BlockInfo &A,const BlockInfo &B);

1340 ///@}

1341

1342 /// Process the instructions in \p BB updating \p LiveSet along the way. \p

1343 /// LiveSet must be initialized with the current live-in locations before

1344 /// calling this.

1345void process(BasicBlock &BB, BlockInfo *LiveSet);

1346 ///@name processMethods

1347 /// Methods to process instructions in order to update the LiveSet (current

1348 /// location information).

1349 ///@{

1350void processNonDbgInstruction(Instruction &I, BlockInfo *LiveSet);

1351void processDbgInstruction(DbgInfoIntrinsic &I, BlockInfo *LiveSet);

1352 /// Update \p LiveSet after encountering an instruction with a DIAssignID

1353 /// attachment, \p I.

1354void processTaggedInstruction(Instruction &I, BlockInfo *LiveSet);

1355 /// Update \p LiveSet after encountering an instruciton without a DIAssignID

1356 /// attachment, \p I.

1357void processUntaggedInstruction(Instruction &I, BlockInfo *LiveSet);

1358void processDbgAssign(AssignRecord Assign, BlockInfo *LiveSet);

1359void processDbgVariableRecord(DbgVariableRecord &DVR, BlockInfo *LiveSet);

1360void processDbgValue(

1361PointerUnion<DbgValueInst *, DbgVariableRecord *> DbgValueRecord,

1362 BlockInfo *LiveSet);

1363 /// Add an assignment to memory for the variable /p Var.

1364void addMemDef(BlockInfo *LiveSet,VariableID Var,const Assignment &AV);

1365 /// Add an assignment to the variable /p Var.

1366void addDbgDef(BlockInfo *LiveSet,VariableID Var,const Assignment &AV);

1367 ///@}

1368

1369 /// Set the LocKind for \p Var.

1370void setLocKind(BlockInfo *LiveSet,VariableID Var, LocKind K);

1371 /// Get the live LocKind for a \p Var. Requires addMemDef or addDbgDef to

1372 /// have been called for \p Var first.

1373 LocKind getLocKind(BlockInfo *LiveSet,VariableID Var);

1374 /// Return true if \p Var has an assignment in \p M matching \p AV.

1375bool hasVarWithAssignment(BlockInfo *LiveSet, BlockInfo::AssignmentKind Kind,

1376VariableID Var,const Assignment &AV);

1377 /// Return the set of VariableIDs corresponding the fragments contained fully

1378 /// within the variable/fragment \p Var.

1379ArrayRef<VariableID> getContainedFragments(VariableID Var)const;

1380

1381 /// Mark \p Var as having been touched this frame. Note, this applies only

1382 /// to the exact fragment \p Var and not to any fragments contained within.

1383void touchFragment(VariableID Var);

1384

1385 /// Emit info for variables that are fully promoted.

1386bool emitPromotedVarLocs(FunctionVarLocsBuilder *FnVarLocs);

1387

1388public:

1389 AssignmentTrackingLowering(Function &Fn,constDataLayout &Layout,

1390constDenseSet<DebugAggregate> *VarsWithStackSlot)

1391 : Fn(Fn), Layout(Layout), VarsWithStackSlot(VarsWithStackSlot) {}

1392 /// Run the analysis, adding variable location info to \p FnVarLocs. Returns

1393 /// true if any variable locations have been added to FnVarLocs.

1394boolrun(FunctionVarLocsBuilder *FnVarLocs);

1395};

1396}// namespace

1397

1398ArrayRef<VariableID>

1399AssignmentTrackingLowering::getContainedFragments(VariableID Var) const{

1400autoR = VarContains.find(Var);

1401if (R == VarContains.end())

1402return {};

1403returnR->second;

1404}

1405

1406void AssignmentTrackingLowering::touchFragment(VariableID Var) {

1407 VarsTouchedThisFrame.insert(Var);

1408}

1409

1410void AssignmentTrackingLowering::setLocKind(BlockInfo *LiveSet,VariableID Var,

1411 LocKind K) {

1412auto SetKind = [this](BlockInfo *LiveSet,VariableID Var, LocKindK) {

1413 LiveSet->setLocKind(Var, K);

1414 touchFragment(Var);

1415 };

1416 SetKind(LiveSet, Var, K);

1417

1418// Update the LocKind for all fragments contained within Var.

1419for (VariableID Frag : getContainedFragments(Var))

1420 SetKind(LiveSet, Frag, K);

1421}

1422

1423AssignmentTrackingLowering::LocKind

1424AssignmentTrackingLowering::getLocKind(BlockInfo *LiveSet,VariableID Var) {

1425return LiveSet->getLocKind(Var);

1426}

1427

1428void AssignmentTrackingLowering::addMemDef(BlockInfo *LiveSet,VariableID Var,

1429const Assignment &AV) {

1430 LiveSet->setAssignment(BlockInfo::Stack, Var, AV);

1431

1432// Use this assigment for all fragments contained within Var, but do not

1433// provide a Source because we cannot convert Var's value to a value for the

1434// fragment.

1435 Assignment FragAV = AV;

1436 FragAV.Source =nullptr;

1437for (VariableID Frag : getContainedFragments(Var))

1438 LiveSet->setAssignment(BlockInfo::Stack, Frag, FragAV);

1439}

1440

1441void AssignmentTrackingLowering::addDbgDef(BlockInfo *LiveSet,VariableID Var,

1442const Assignment &AV) {

1443 LiveSet->setAssignment(BlockInfo::Debug, Var, AV);

1444

1445// Use this assigment for all fragments contained within Var, but do not

1446// provide a Source because we cannot convert Var's value to a value for the

1447// fragment.

1448 Assignment FragAV = AV;

1449 FragAV.Source =nullptr;

1450for (VariableID Frag : getContainedFragments(Var))

1451 LiveSet->setAssignment(BlockInfo::Debug, Frag, FragAV);

1452}

1453

1454staticDIAssignID *getIDFromInst(constInstruction &I) {

1455return cast<DIAssignID>(I.getMetadata(LLVMContext::MD_DIAssignID));

1456}

1457

1458staticDIAssignID *getIDFromMarker(constDbgAssignIntrinsic &DAI) {

1459return cast<DIAssignID>(DAI.getAssignID());

1460}

1461

1462staticDIAssignID *getIDFromMarker(constDbgVariableRecord &DVR) {

1463assert(DVR.isDbgAssign() &&

1464"Cannot get a DIAssignID from a non-assign DbgVariableRecord!");

1465return DVR.getAssignID();

1466}

1467

1468/// Return true if \p Var has an assignment in \p M matching \p AV.

1469bool AssignmentTrackingLowering::hasVarWithAssignment(

1470 BlockInfo *LiveSet, BlockInfo::AssignmentKind Kind,VariableID Var,

1471const Assignment &AV) {

1472if (!LiveSet->hasAssignment(Kind, Var, AV))

1473returnfalse;

1474

1475// Check all the frags contained within Var as these will have all been

1476// mapped to AV at the last store to Var.

1477for (VariableID Frag : getContainedFragments(Var))

1478if (!LiveSet->hasAssignment(Kind, Frag, AV))

1479returnfalse;

1480returntrue;

1481}

1482

1483#ifndef NDEBUG

1484constchar *locStr(AssignmentTrackingLowering::LocKind Loc) {

1485usingLocKind = AssignmentTrackingLowering::LocKind;

1486switch (Loc) {

1487case LocKind::Val:

1488return"Val";

1489case LocKind::Mem:

1490return"Mem";

1491case LocKind::None:

1492return"None";

1493 };

1494llvm_unreachable("unknown LocKind");

1495}

1496#endif

1497

1498VarLocInsertPt getNextNode(constDbgRecord *DVR) {

1499auto NextIt = ++(DVR->getIterator());

1500if (NextIt == DVR->getMarker()->getDbgRecordRange().end())

1501return DVR->getMarker()->MarkedInstr;

1502return &*NextIt;

1503}

1504VarLocInsertPt getNextNode(constInstruction *Inst) {

1505constInstruction *Next = Inst->getNextNode();

1506if (!Next->hasDbgRecords())

1507return Next;

1508return &*Next->getDbgRecordRange().begin();

1509}

1510VarLocInsertPt getNextNode(VarLocInsertPt InsertPt) {

1511if (isa<const Instruction *>(InsertPt))

1512returngetNextNode(cast<const Instruction *>(InsertPt));

1513returngetNextNode(cast<const DbgRecord *>(InsertPt));

1514}

1515

1516DbgAssignIntrinsic *CastToDbgAssign(DbgVariableIntrinsic *DVI) {

1517return cast<DbgAssignIntrinsic>(DVI);

1518}

1519

1520DbgVariableRecord *CastToDbgAssign(DbgVariableRecord *DVR) {

1521assert(DVR->isDbgAssign() &&

1522"Attempted to cast non-assign DbgVariableRecord to DVRAssign.");

1523return DVR;

1524}

1525

1526void AssignmentTrackingLowering::emitDbgValue(

1527 AssignmentTrackingLowering::LocKind Kind,

1528AssignmentTrackingLowering::AssignRecord Source,VarLocInsertPt After) {

1529if (isa<DbgAssignIntrinsic *>(Source))

1530 emitDbgValue(Kind, cast<DbgAssignIntrinsic *>(Source),After);

1531else

1532 emitDbgValue(Kind, cast<DbgVariableRecord *>(Source),After);

1533}

1534template <typename T>

1535void AssignmentTrackingLowering::emitDbgValue(

1536 AssignmentTrackingLowering::LocKind Kind,constT Source,

1537VarLocInsertPt After) {

1538

1539DILocation *DL =Source->getDebugLoc();

1540auto Emit = [this,Source,After,DL](Metadata *Val,DIExpression *Expr) {

1541assert(Expr);

1542if (!Val)

1543 Val =ValueAsMetadata::get(

1544PoisonValue::get(Type::getInt1Ty(Source->getContext())));

1545

1546// Find a suitable insert point.

1547auto InsertBefore =getNextNode(After);

1548assert(InsertBefore &&"Shouldn't be inserting after a terminator");

1549

1550VariableID Var = getVariableID(DebugVariable(Source));

1551VarLocInfo VarLoc;

1552 VarLoc.VariableID =static_cast<VariableID>(Var);

1553 VarLoc.Expr = Expr;

1554 VarLoc.Values =RawLocationWrapper(Val);

1555 VarLoc.DL =DL;

1556// Insert it into the map for later.

1557 InsertBeforeMap[InsertBefore].push_back(VarLoc);

1558 };

1559

1560// NOTE: This block can mutate Kind.

1561if (Kind == LocKind::Mem) {

1562constauto *Assign =CastToDbgAssign(Source);

1563// Check the address hasn't been dropped (e.g. the debug uses may not have

1564// been replaced before deleting a Value).

1565if (Assign->isKillAddress()) {

1566// The address isn't valid so treat this as a non-memory def.

1567Kind = LocKind::Val;

1568 }else {

1569Value *Val =Assign->getAddress();

1570DIExpression *Expr =Assign->getAddressExpression();

1571assert(!Expr->getFragmentInfo() &&

1572"fragment info should be stored in value-expression only");

1573// Copy the fragment info over from the value-expression to the new

1574// DIExpression.

1575if (auto OptFragInfo =Source->getExpression()->getFragmentInfo()) {

1576auto FragInfo = *OptFragInfo;

1577 Expr = *DIExpression::createFragmentExpression(

1578 Expr, FragInfo.OffsetInBits, FragInfo.SizeInBits);

1579 }

1580// The address-expression has an implicit deref, add it now.

1581 std::tie(Val, Expr) =

1582walkToAllocaAndPrependOffsetDeref(Layout, Val, Expr);

1583 Emit(ValueAsMetadata::get(Val), Expr);

1584return;

1585 }

1586 }

1587

1588if (Kind == LocKind::Val) {

1589 Emit(Source->getRawLocation(),Source->getExpression());

1590return;

1591 }

1592

1593if (Kind == LocKind::None) {

1594 Emit(nullptr,Source->getExpression());

1595return;

1596 }

1597}

1598

1599void AssignmentTrackingLowering::processNonDbgInstruction(

1600Instruction &I, AssignmentTrackingLowering::BlockInfo *LiveSet) {

1601if (I.hasMetadata(LLVMContext::MD_DIAssignID))

1602 processTaggedInstruction(I, LiveSet);

1603else

1604 processUntaggedInstruction(I, LiveSet);

1605}

1606

1607void AssignmentTrackingLowering::processUntaggedInstruction(

1608Instruction &I, AssignmentTrackingLowering::BlockInfo *LiveSet) {

1609// Interpret stack stores that are not tagged as an assignment in memory for

1610// the variables associated with that address. These stores may not be tagged

1611// because a) the store cannot be represented using dbg.assigns (non-const

1612// length or offset) or b) the tag was accidentally dropped during

1613// optimisations. For these stores we fall back to assuming that the stack

1614// home is a valid location for the variables. The benefit is that this

1615// prevents us missing an assignment and therefore incorrectly maintaining

1616// earlier location definitions, and in many cases it should be a reasonable

1617// assumption. However, this will occasionally lead to slight

1618// inaccuracies. The value of a hoisted untagged store will be visible

1619// "early", for example.

1620assert(!I.hasMetadata(LLVMContext::MD_DIAssignID));

1621auto It = UntaggedStoreVars.find(&I);

1622if (It == UntaggedStoreVars.end())

1623return;// No variables associated with the store destination.

1624

1625LLVM_DEBUG(dbgs() <<"processUntaggedInstruction on UNTAGGED INST " <<I

1626 <<"\n");

1627// Iterate over the variables that this store affects, add a NoneOrPhi dbg

1628// and mem def, set lockind to Mem, and emit a location def for each.

1629for (auto [Var, Info] : It->second) {

1630// This instruction is treated as both a debug and memory assignment,

1631// meaning the memory location should be used. We don't have an assignment

1632// ID though so use Assignment::makeNoneOrPhi() to create an imaginary one.

1633 addMemDef(LiveSet, Var, Assignment::makeNoneOrPhi());

1634 addDbgDef(LiveSet, Var, Assignment::makeNoneOrPhi());

1635 setLocKind(LiveSet, Var, LocKind::Mem);

1636LLVM_DEBUG(dbgs() <<" setting Stack LocKind to: " <<locStr(LocKind::Mem)

1637 <<"\n");

1638// Build the dbg location def to insert.

1639//

1640// DIExpression: Add fragment and offset.

1641DebugVariable V = FnVarLocs->getVariable(Var);

1642DIExpression *DIE =DIExpression::get(I.getContext(), {});

1643if (auto Frag =V.getFragment()) {

1644autoR =DIExpression::createFragmentExpression(DIE, Frag->OffsetInBits,

1645 Frag->SizeInBits);

1646assert(R &&"unexpected createFragmentExpression failure");

1647DIE = *R;

1648 }

1649SmallVector<uint64_t, 3> Ops;

1650if (Info.OffsetInBits)

1651 Ops = {dwarf::DW_OP_plus_uconst,Info.OffsetInBits / 8};

1652 Ops.push_back(dwarf::DW_OP_deref);

1653DIE =DIExpression::prependOpcodes(DIE, Ops,/*StackValue=*/false,

1654/*EntryValue=*/false);

1655// Find a suitable insert point, before the next instruction or DbgRecord

1656// after I.

1657auto InsertBefore =getNextNode(&I);

1658assert(InsertBefore &&"Shouldn't be inserting after a terminator");

1659

1660// Get DILocation for this unrecorded assignment.

1661DILocation *InlinedAt =const_cast<DILocation *>(V.getInlinedAt());

1662constDILocation *DILoc =DILocation::get(

1663 Fn.getContext(), 0, 0,V.getVariable()->getScope(), InlinedAt);

1664

1665VarLocInfo VarLoc;

1666 VarLoc.VariableID =static_cast<VariableID>(Var);

1667 VarLoc.Expr =DIE;

1668 VarLoc.Values =RawLocationWrapper(

1669ValueAsMetadata::get(const_cast<AllocaInst *>(Info.Base)));

1670 VarLoc.DL = DILoc;

1671// 3. Insert it into the map for later.

1672 InsertBeforeMap[InsertBefore].push_back(VarLoc);

1673 }

1674}

1675

1676void AssignmentTrackingLowering::processTaggedInstruction(

1677Instruction &I, AssignmentTrackingLowering::BlockInfo *LiveSet) {

1678auto Linked =at::getAssignmentMarkers(&I);

1679auto LinkedDPAssigns =at::getDVRAssignmentMarkers(&I);

1680// No dbg.assign intrinsics linked.

1681// FIXME: All vars that have a stack slot this store modifies that don't have

1682// a dbg.assign linked to it should probably treat this like an untagged

1683// store.

1684if (Linked.empty() && LinkedDPAssigns.empty())

1685return;

1686

1687LLVM_DEBUG(dbgs() <<"processTaggedInstruction on " <<I <<"\n");

1688auto ProcessLinkedAssign = [&](auto *Assign) {

1689VariableID Var = getVariableID(DebugVariable(Assign));

1690// Something has gone wrong if VarsWithStackSlot doesn't contain a variable

1691// that is linked to a store.

1692assert(VarsWithStackSlot->count(getAggregate(Assign)) &&

1693"expected Assign's variable to have stack slot");

1694

1695 Assignment AV = Assignment::makeFromMemDef(getIDFromInst(I));

1696 addMemDef(LiveSet, Var, AV);

1697

1698LLVM_DEBUG(dbgs() <<" linked to " << *Assign <<"\n");

1699LLVM_DEBUG(dbgs() <<" LiveLoc " <<locStr(getLocKind(LiveSet, Var))

1700 <<" -> ");

1701

1702// The last assignment to the stack is now AV. Check if the last debug

1703// assignment has a matching Assignment.

1704if (hasVarWithAssignment(LiveSet, BlockInfo::Debug, Var, AV)) {

1705// The StackHomeValue and DebugValue for this variable match so we can

1706// emit a stack home location here.

1707LLVM_DEBUG(dbgs() <<"Mem, Stack matches Debug program\n";);

1708LLVM_DEBUG(dbgs() <<" Stack val: "; AV.dump(dbgs());dbgs() <<"\n");

1709LLVM_DEBUG(dbgs() <<" Debug val: ";

1710 LiveSet->DebugValue[static_cast<unsigned>(Var)].dump(dbgs());

1711dbgs() <<"\n");

1712 setLocKind(LiveSet, Var, LocKind::Mem);

1713 emitDbgValue(LocKind::Mem, Assign, &I);

1714return;

1715 }

1716

1717// The StackHomeValue and DebugValue for this variable do not match. I.e.

1718// The value currently stored in the stack is not what we'd expect to

1719// see, so we cannot use emit a stack home location here. Now we will

1720// look at the live LocKind for the variable and determine an appropriate

1721// dbg.value to emit.

1722 LocKind PrevLoc = getLocKind(LiveSet, Var);

1723switch (PrevLoc) {

1724case LocKind::Val: {

1725// The value in memory in memory has changed but we're not currently

1726// using the memory location. Do nothing.

1727LLVM_DEBUG(dbgs() <<"Val, (unchanged)\n";);

1728 setLocKind(LiveSet, Var, LocKind::Val);

1729 }break;

1730case LocKind::Mem: {

1731// There's been an assignment to memory that we were using as a

1732// location for this variable, and the Assignment doesn't match what

1733// we'd expect to see in memory.

1734 Assignment DbgAV = LiveSet->getAssignment(BlockInfo::Debug, Var);

1735if (DbgAV.Status == Assignment::NoneOrPhi) {

1736// We need to terminate any previously open location now.

1737LLVM_DEBUG(dbgs() <<"None, No Debug value available\n";);

1738 setLocKind(LiveSet, Var, LocKind::None);

1739 emitDbgValue(LocKind::None, Assign, &I);

1740 }else {

1741// The previous DebugValue Value can be used here.

1742LLVM_DEBUG(dbgs() <<"Val, Debug value is Known\n";);

1743 setLocKind(LiveSet, Var, LocKind::Val);

1744if (DbgAV.Source) {

1745 emitDbgValue(LocKind::Val, DbgAV.Source, &I);

1746 }else {

1747// PrevAV.Source is nullptr so we must emit undef here.

1748 emitDbgValue(LocKind::None, Assign, &I);

1749 }

1750 }

1751 }break;

1752case LocKind::None: {

1753// There's been an assignment to memory and we currently are

1754// not tracking a location for the variable. Do not emit anything.

1755LLVM_DEBUG(dbgs() <<"None, (unchanged)\n";);

1756 setLocKind(LiveSet, Var, LocKind::None);

1757 }break;

1758 }

1759 };

1760for (DbgAssignIntrinsic *DAI : Linked)

1761 ProcessLinkedAssign(DAI);

1762for (DbgVariableRecord *DVR : LinkedDPAssigns)

1763 ProcessLinkedAssign(DVR);

1764}

1765

1766void AssignmentTrackingLowering::processDbgAssign(AssignRecord Assign,

1767 BlockInfo *LiveSet) {

1768auto ProcessDbgAssignImpl = [&](auto *DbgAssign) {

1769// Only bother tracking variables that are at some point stack homed. Other

1770// variables can be dealt with trivially later.

1771if (!VarsWithStackSlot->count(getAggregate(DbgAssign)))

1772return;

1773

1774VariableID Var = getVariableID(DebugVariable(DbgAssign));

1775 Assignment AV = Assignment::make(getIDFromMarker(*DbgAssign), DbgAssign);

1776 addDbgDef(LiveSet, Var, AV);

1777

1778LLVM_DEBUG(dbgs() <<"processDbgAssign on " << *DbgAssign <<"\n";);

1779LLVM_DEBUG(dbgs() <<" LiveLoc " <<locStr(getLocKind(LiveSet, Var))

1780 <<" -> ");

1781

1782// Check if the DebugValue and StackHomeValue both hold the same

1783// Assignment.

1784if (hasVarWithAssignment(LiveSet, BlockInfo::Stack, Var, AV)) {

1785// They match. We can use the stack home because the debug intrinsics

1786// state that an assignment happened here, and we know that specific

1787// assignment was the last one to take place in memory for this variable.

1788 LocKindKind;

1789if (DbgAssign->isKillAddress()) {

1790LLVM_DEBUG(

1791dbgs()

1792 <<"Val, Stack matches Debug program but address is killed\n";);

1793Kind = LocKind::Val;

1794 }else {

1795LLVM_DEBUG(dbgs() <<"Mem, Stack matches Debug program\n";);

1796Kind = LocKind::Mem;

1797 };

1798 setLocKind(LiveSet, Var, Kind);

1799 emitDbgValue(Kind, DbgAssign, DbgAssign);

1800 }else {

1801// The last assignment to the memory location isn't the one that we want

1802// to show to the user so emit a dbg.value(Value). Value may be undef.

1803LLVM_DEBUG(dbgs() <<"Val, Stack contents is unknown\n";);

1804 setLocKind(LiveSet, Var, LocKind::Val);

1805 emitDbgValue(LocKind::Val, DbgAssign, DbgAssign);

1806 }

1807 };

1808if (isa<DbgVariableRecord *>(Assign))

1809return ProcessDbgAssignImpl(cast<DbgVariableRecord *>(Assign));

1810return ProcessDbgAssignImpl(cast<DbgAssignIntrinsic *>(Assign));

1811}

1812

1813void AssignmentTrackingLowering::processDbgValue(

1814PointerUnion<DbgValueInst *, DbgVariableRecord *> DbgValueRecord,

1815 BlockInfo *LiveSet) {

1816auto ProcessDbgValueImpl = [&](auto *DbgValue) {

1817// Only other tracking variables that are at some point stack homed.

1818// Other variables can be dealt with trivally later.

1819if (!VarsWithStackSlot->count(getAggregate(DbgValue)))

1820return;

1821

1822VariableID Var = getVariableID(DebugVariable(DbgValue));

1823// We have no ID to create an Assignment with so we mark this assignment as

1824// NoneOrPhi. Note that the dbg.value still exists, we just cannot determine

1825// the assignment responsible for setting this value.

1826// This is fine; dbg.values are essentially interchangable with unlinked

1827// dbg.assigns, and some passes such as mem2reg and instcombine add them to

1828// PHIs for promoted variables.

1829 Assignment AV = Assignment::makeNoneOrPhi();

1830 addDbgDef(LiveSet, Var, AV);

1831

1832LLVM_DEBUG(dbgs() <<"processDbgValue on " << *DbgValue <<"\n";);

1833LLVM_DEBUG(dbgs() <<" LiveLoc " <<locStr(getLocKind(LiveSet, Var))

1834 <<" -> Val, dbg.value override");

1835

1836 setLocKind(LiveSet, Var, LocKind::Val);

1837 emitDbgValue(LocKind::Val,DbgValue,DbgValue);

1838 };

1839if (isa<DbgVariableRecord *>(DbgValueRecord))

1840return ProcessDbgValueImpl(cast<DbgVariableRecord *>(DbgValueRecord));

1841return ProcessDbgValueImpl(cast<DbgValueInst *>(DbgValueRecord));

1842}

1843

1844template <typename T>staticboolhasZeroSizedFragment(T &DbgValue) {

1845if (autoF =DbgValue.getExpression()->getFragmentInfo())

1846returnF->SizeInBits == 0;

1847returnfalse;

1848}

1849

1850void AssignmentTrackingLowering::processDbgInstruction(

1851DbgInfoIntrinsic &I, AssignmentTrackingLowering::BlockInfo *LiveSet) {

1852auto *DVI = dyn_cast<DbgVariableIntrinsic>(&I);

1853if (!DVI)

1854return;

1855

1856// Ignore assignments to zero bits of the variable.

1857if (hasZeroSizedFragment(*DVI))

1858return;

1859

1860if (auto *DAI = dyn_cast<DbgAssignIntrinsic>(&I))

1861 processDbgAssign(DAI, LiveSet);

1862elseif (auto *DVI = dyn_cast<DbgValueInst>(&I))

1863 processDbgValue(DVI, LiveSet);

1864}

1865void AssignmentTrackingLowering::processDbgVariableRecord(

1866DbgVariableRecord &DVR, AssignmentTrackingLowering::BlockInfo *LiveSet) {

1867// Ignore assignments to zero bits of the variable.

1868if (hasZeroSizedFragment(DVR))

1869return;

1870

1871if (DVR.isDbgAssign())

1872 processDbgAssign(&DVR, LiveSet);

1873elseif (DVR.isDbgValue())

1874 processDbgValue(&DVR, LiveSet);

1875}

1876

1877void AssignmentTrackingLowering::resetInsertionPoint(Instruction &After) {

1878assert(!After.isTerminator() &&"Can't insert after a terminator");

1879auto *R = InsertBeforeMap.find(getNextNode(&After));

1880if (R == InsertBeforeMap.end())

1881return;

1882R->second.clear();

1883}

1884void AssignmentTrackingLowering::resetInsertionPoint(DbgVariableRecord &After) {

1885auto *R = InsertBeforeMap.find(getNextNode(&After));

1886if (R == InsertBeforeMap.end())

1887return;

1888R->second.clear();

1889}

1890

1891void AssignmentTrackingLowering::process(BasicBlock &BB, BlockInfo *LiveSet) {

1892// If the block starts with DbgRecords, we need to process those DbgRecords as

1893// their own frame without processing any instructions first.

1894bool ProcessedLeadingDbgRecords = !BB.begin()->hasDbgRecords();

1895for (autoII = BB.begin(), EI = BB.end();II != EI;) {

1896assert(VarsTouchedThisFrame.empty());

1897// Process the instructions in "frames". A "frame" includes a single

1898// non-debug instruction followed any debug instructions before the

1899// next non-debug instruction.

1900

1901// Skip the current instruction if it has unprocessed DbgRecords attached

1902// (see comment above `ProcessedLeadingDbgRecords`).

1903if (ProcessedLeadingDbgRecords) {

1904// II is now either a debug intrinsic, a non-debug instruction with no

1905// attached DbgRecords, or a non-debug instruction with attached processed

1906// DbgRecords.

1907// II has not been processed.

1908if (!isa<DbgInfoIntrinsic>(&*II)) {

1909if (II->isTerminator())

1910break;

1911 resetInsertionPoint(*II);

1912 processNonDbgInstruction(*II, LiveSet);

1913assert(LiveSet->isValid());

1914 ++II;

1915 }

1916 }

1917// II is now either a debug intrinsic, a non-debug instruction with no

1918// attached DbgRecords, or a non-debug instruction with attached unprocessed

1919// DbgRecords.

1920if (II != EI &&II->hasDbgRecords()) {

1921// Skip over non-variable debug records (i.e., labels). They're going to

1922// be read from IR (possibly re-ordering them within the debug record

1923// range) rather than from the analysis results.

1924for (DbgVariableRecord &DVR :filterDbgVars(II->getDbgRecordRange())) {

1925 resetInsertionPoint(DVR);

1926 processDbgVariableRecord(DVR, LiveSet);

1927assert(LiveSet->isValid());

1928 }

1929 }

1930 ProcessedLeadingDbgRecords =true;

1931while (II != EI) {

1932auto *Dbg = dyn_cast<DbgInfoIntrinsic>(&*II);

1933if (!Dbg)

1934break;

1935 resetInsertionPoint(*II);

1936 processDbgInstruction(*Dbg, LiveSet);

1937assert(LiveSet->isValid());

1938 ++II;

1939 }

1940// II is now a non-debug instruction either with no attached DbgRecords, or

1941// with attached processed DbgRecords. II has not been processed, and all

1942// debug instructions or DbgRecords in the frame preceding II have been

1943// processed.

1944

1945// We've processed everything in the "frame". Now determine which variables

1946// cannot be represented by a dbg.declare.

1947for (auto Var : VarsTouchedThisFrame) {

1948 LocKind Loc = getLocKind(LiveSet, Var);

1949// If a variable's LocKind is anything other than LocKind::Mem then we

1950// must note that it cannot be represented with a dbg.declare.

1951// Note that this check is enough without having to check the result of

1952// joins() because for join to produce anything other than Mem after

1953// we've already seen a Mem we'd be joining None or Val with Mem. In that

1954// case, we've already hit this codepath when we set the LocKind to Val

1955// or None in that block.

1956if (Loc != LocKind::Mem) {

1957DebugVariable DbgVar = FnVarLocs->getVariable(Var);

1958DebugAggregate Aggr{DbgVar.getVariable(), DbgVar.getInlinedAt()};

1959 NotAlwaysStackHomed.insert(Aggr);

1960 }

1961 }

1962 VarsTouchedThisFrame.clear();

1963 }

1964}

1965

1966AssignmentTrackingLowering::LocKind

1967AssignmentTrackingLowering::joinKind(LocKindA, LocKindB) {

1968// Partial order:

1969// None > Mem, Val

1970returnA ==B ?A : LocKind::None;

1971}

1972

1973AssignmentTrackingLowering::Assignment

1974AssignmentTrackingLowering::joinAssignment(const Assignment &A,

1975const Assignment &B) {

1976// Partial order:

1977// NoneOrPhi(null, null) > Known(v, ?s)

1978

1979// If either are NoneOrPhi the join is NoneOrPhi.

1980// If either value is different then the result is

1981// NoneOrPhi (joining two values is a Phi).

1982if (!A.isSameSourceAssignment(B))

1983return Assignment::makeNoneOrPhi();

1984if (A.Status == Assignment::NoneOrPhi)

1985return Assignment::makeNoneOrPhi();

1986

1987// Source is used to lookup the value + expression in the debug program if

1988// the stack slot gets assigned a value earlier than expected. Because

1989// we're only tracking the one dbg.assign, we can't capture debug PHIs.

1990// It's unlikely that we're losing out on much coverage by avoiding that

1991// extra work.

1992// The Source may differ in this situation:

1993// Pred.1:

1994// dbg.assign i32 0, ..., !1, ...

1995// Pred.2:

1996// dbg.assign i32 1, ..., !1, ...

1997// Here the same assignment (!1) was performed in both preds in the source,

1998// but we can't use either one unless they are identical (e.g. .we don't

1999// want to arbitrarily pick between constant values).

2000auto JoinSource = [&]() -> AssignRecord {

2001if (A.Source ==B.Source)

2002returnA.Source;

2003if (!A.Source || !B.Source)

2004return AssignRecord();

2005assert(isa<DbgVariableRecord *>(A.Source) ==

2006 isa<DbgVariableRecord *>(B.Source));

2007if (isa<DbgVariableRecord *>(A.Source) &&

2008 cast<DbgVariableRecord *>(A.Source)->isEquivalentTo(

2009 *cast<DbgVariableRecord *>(B.Source)))

2010returnA.Source;

2011if (isa<DbgAssignIntrinsic *>(A.Source) &&

2012 cast<DbgAssignIntrinsic *>(A.Source)->isIdenticalTo(

2013 cast<DbgAssignIntrinsic *>(B.Source)))

2014returnA.Source;

2015return AssignRecord();

2016 };

2017 AssignRecordSource = JoinSource();

2018assert(A.Status ==B.Status &&A.Status == Assignment::Known);

2019assert(A.ID ==B.ID);

2020return Assignment::make(A.ID, Source);

2021}

2022

2023AssignmentTrackingLowering::BlockInfo

2024AssignmentTrackingLowering::joinBlockInfo(const BlockInfo &A,

2025const BlockInfo &B) {

2026return BlockInfo::join(A,B, TrackedVariablesVectorSize);

2027}

2028

2029bool AssignmentTrackingLowering::join(

2030constBasicBlock &BB,constSmallPtrSet<BasicBlock *, 16> &Visited) {

2031

2032SmallVector<const BasicBlock *> VisitedPreds;

2033// Ignore backedges if we have not visited the predecessor yet. As the

2034// predecessor hasn't yet had locations propagated into it, most locations

2035// will not yet be valid, so treat them as all being uninitialized and

2036// potentially valid. If a location guessed to be correct here is

2037// invalidated later, we will remove it when we revisit this block. This

2038// is essentially the same as initialising all LocKinds and Assignments to

2039// an implicit ⊥ value which is the identity value for the join operation.

2040for (constBasicBlock *Pred :predecessors(&BB)) {

2041if (Visited.count(Pred))

2042 VisitedPreds.push_back(Pred);

2043 }

2044

2045// No preds visited yet.

2046if (VisitedPreds.empty()) {

2047auto It = LiveIn.try_emplace(&BB, BlockInfo());

2048bool DidInsert = It.second;

2049if (DidInsert)

2050 It.first->second.init(TrackedVariablesVectorSize);

2051return/*Changed*/ DidInsert;

2052 }

2053

2054// Exactly one visited pred. Copy the LiveOut from that pred into BB LiveIn.

2055if (VisitedPreds.size() == 1) {

2056const BlockInfo &PredLiveOut = LiveOut.find(VisitedPreds[0])->second;

2057auto CurrentLiveInEntry = LiveIn.find(&BB);

2058

2059// Check if there isn't an entry, or there is but the LiveIn set has

2060// changed (expensive check).

2061if (CurrentLiveInEntry == LiveIn.end())

2062 LiveIn.insert(std::make_pair(&BB, PredLiveOut));

2063elseif (PredLiveOut != CurrentLiveInEntry->second)

2064 CurrentLiveInEntry->second = PredLiveOut;

2065else

2066return/*Changed*/false;

2067return/*Changed*/true;

2068 }

2069

2070// More than one pred. Join LiveOuts of blocks 1 and 2.

2071assert(VisitedPreds.size() > 1);

2072const BlockInfo &PredLiveOut0 = LiveOut.find(VisitedPreds[0])->second;

2073const BlockInfo &PredLiveOut1 = LiveOut.find(VisitedPreds[1])->second;

2074 BlockInfo BBLiveIn = joinBlockInfo(PredLiveOut0, PredLiveOut1);

2075

2076// Join the LiveOuts of subsequent blocks.

2077ArrayRef Tail =ArrayRef(VisitedPreds).drop_front(2);

2078for (constBasicBlock *Pred :Tail) {

2079constauto &PredLiveOut = LiveOut.find(Pred);

2080assert(PredLiveOut != LiveOut.end() &&

2081"block should have been processed already");

2082 BBLiveIn = joinBlockInfo(std::move(BBLiveIn), PredLiveOut->second);

2083 }

2084

2085// Save the joined result for BB.

2086auto CurrentLiveInEntry = LiveIn.find(&BB);

2087// Check if there isn't an entry, or there is but the LiveIn set has changed

2088// (expensive check).

2089if (CurrentLiveInEntry == LiveIn.end())

2090 LiveIn.try_emplace(&BB, std::move(BBLiveIn));

2091elseif (BBLiveIn != CurrentLiveInEntry->second)

2092 CurrentLiveInEntry->second = std::move(BBLiveIn);

2093else

2094return/*Changed*/false;

2095return/*Changed*/true;

2096}

2097

2098/// Return true if A fully contains B.

2099staticboolfullyContains(DIExpression::FragmentInfo A,

2100DIExpression::FragmentInfo B) {

2101auto ALeft =A.OffsetInBits;

2102auto BLeft =B.OffsetInBits;

2103if (BLeft < ALeft)

2104returnfalse;

2105

2106auto ARight = ALeft +A.SizeInBits;

2107auto BRight = BLeft +B.SizeInBits;

2108if (BRight > ARight)

2109returnfalse;

2110returntrue;

2111}

2112

2113static std::optional<at::AssignmentInfo>

2114getUntaggedStoreAssignmentInfo(constInstruction &I,constDataLayout &Layout) {

2115// Don't bother checking if this is an AllocaInst. We know this

2116// instruction has no tag which means there are no variables associated

2117// with it.

2118if (constauto *SI = dyn_cast<StoreInst>(&I))

2119returnat::getAssignmentInfo(Layout, SI);

2120if (constauto *MI = dyn_cast<MemIntrinsic>(&I))

2121returnat::getAssignmentInfo(Layout,MI);

2122// Alloca or non-store-like inst.

2123return std::nullopt;

2124}

2125

2126DbgDeclareInst *DynCastToDbgDeclare(DbgVariableIntrinsic *DVI) {

2127return dyn_cast<DbgDeclareInst>(DVI);

2128}

2129

2130DbgVariableRecord *DynCastToDbgDeclare(DbgVariableRecord *DVR) {

2131return DVR->isDbgDeclare() ? DVR :nullptr;

2132}

2133

2134/// Build a map of {Variable x: Variables y} where all variable fragments

2135/// contained within the variable fragment x are in set y. This means that

2136/// y does not contain all overlaps because partial overlaps are excluded.

2137///

2138/// While we're iterating over the function, add single location defs for

2139/// dbg.declares to \p FnVarLocs.

2140///

2141/// Variables that are interesting to this pass in are added to

2142/// FnVarLocs->Variables first. TrackedVariablesVectorSize is set to the ID of

2143/// the last interesting variable plus 1, meaning variables with ID 1

2144/// (inclusive) to TrackedVariablesVectorSize (exclusive) are interesting. The

2145/// subsequent variables are either stack homed or fully promoted.

2146///

2147/// Finally, populate UntaggedStoreVars with a mapping of untagged stores to

2148/// the stored-to variable fragments.

2149///

2150/// These tasks are bundled together to reduce the number of times we need

2151/// to iterate over the function as they can be achieved together in one pass.

2152staticAssignmentTrackingLowering::OverlapMap buildOverlapMapAndRecordDeclares(

2153Function &Fn,FunctionVarLocsBuilder *FnVarLocs,

2154constDenseSet<DebugAggregate> &VarsWithStackSlot,

2155AssignmentTrackingLowering::UntaggedStoreAssignmentMap &UntaggedStoreVars,

2156unsigned &TrackedVariablesVectorSize) {

2157DenseSet<DebugVariable> Seen;

2158// Map of Variable: [Fragments].

2159DenseMap<DebugAggregate, SmallVector<DebugVariable, 8>> FragmentMap;

2160// Iterate over all instructions:

2161// - dbg.declare -> add single location variable record

2162// - dbg.* -> Add fragments to FragmentMap

2163// - untagged store -> Add fragments to FragmentMap and update

2164// UntaggedStoreVars.

2165// We need to add fragments for untagged stores too so that we can correctly

2166// clobber overlapped fragment locations later.

2167SmallVector<DbgDeclareInst *> InstDeclares;

2168SmallVector<DbgVariableRecord *> DPDeclares;

2169auto ProcessDbgRecord = [&](auto *Record,auto &DeclareList) {

2170if (auto *Declare =DynCastToDbgDeclare(Record)) {

2171 DeclareList.push_back(Declare);

2172return;

2173 }

2174DebugVariable DV =DebugVariable(Record);

2175DebugAggregate DA = {DV.getVariable(), DV.getInlinedAt()};

2176if (!VarsWithStackSlot.contains(DA))

2177return;

2178if (Seen.insert(DV).second)

2179 FragmentMap[DA].push_back(DV);

2180 };

2181for (auto &BB : Fn) {

2182for (auto &I : BB) {

2183for (DbgVariableRecord &DVR :filterDbgVars(I.getDbgRecordRange()))

2184 ProcessDbgRecord(&DVR, DPDeclares);

2185if (auto *DII = dyn_cast<DbgVariableIntrinsic>(&I)) {

2186 ProcessDbgRecord(DII, InstDeclares);

2187 }elseif (autoInfo =getUntaggedStoreAssignmentInfo(

2188I, Fn.getDataLayout())) {

2189// Find markers linked to this alloca.

2190auto HandleDbgAssignForStore = [&](auto *Assign) {

2191 std::optional<DIExpression::FragmentInfo> FragInfo;

2192

2193// Skip this assignment if the affected bits are outside of the

2194// variable fragment.

2195if (!at::calculateFragmentIntersect(

2196I.getDataLayout(),Info->Base,

2197Info->OffsetInBits,Info->SizeInBits, Assign, FragInfo) ||

2198 (FragInfo && FragInfo->SizeInBits == 0))

2199return;

2200

2201// FragInfo from calculateFragmentIntersect is nullopt if the

2202// resultant fragment matches DAI's fragment or entire variable - in

2203// which case copy the fragment info from DAI. If FragInfo is still

2204// nullopt after the copy it means "no fragment info" instead, which

2205// is how it is usually interpreted.

2206if (!FragInfo)

2207 FragInfo = Assign->getExpression()->getFragmentInfo();

2208

2209DebugVariable DV =

2210DebugVariable(Assign->getVariable(), FragInfo,

2211 Assign->getDebugLoc().getInlinedAt());

2212DebugAggregate DA = {DV.getVariable(), DV.getInlinedAt()};

2213if (!VarsWithStackSlot.contains(DA))

2214return;

2215

2216// Cache this info for later.

2217 UntaggedStoreVars[&I].push_back(

2218 {FnVarLocs->insertVariable(DV), *Info});

2219

2220if (Seen.insert(DV).second)

2221 FragmentMap[DA].push_back(DV);

2222 };

2223for (DbgAssignIntrinsic *DAI :at::getAssignmentMarkers(Info->Base))

2224 HandleDbgAssignForStore(DAI);

2225for (DbgVariableRecord *DVR :at::getDVRAssignmentMarkers(Info->Base))

2226 HandleDbgAssignForStore(DVR);

2227 }

2228 }

2229 }

2230

2231// Sort the fragment map for each DebugAggregate in ascending

2232// order of fragment size - there should be no duplicates.

2233for (auto &Pair : FragmentMap) {

2234SmallVector<DebugVariable, 8> &Frags = Pair.second;

2235 std::sort(Frags.begin(), Frags.end(),

2236 [](constDebugVariable &Next,constDebugVariable &Elmt) {

2237 return Elmt.getFragmentOrDefault().SizeInBits >

2238 Next.getFragmentOrDefault().SizeInBits;

2239 });

2240// Check for duplicates.

2241assert(std::adjacent_find(Frags.begin(), Frags.end()) == Frags.end());

2242 }

2243

2244// Build the map.

2245AssignmentTrackingLowering::OverlapMap Map;

2246for (auto &Pair : FragmentMap) {

2247auto &Frags = Pair.second;

2248for (auto It = Frags.begin(), IEnd = Frags.end(); It != IEnd; ++It) {

2249DIExpression::FragmentInfo Frag = It->getFragmentOrDefault();

2250// Find the frags that this is contained within.

2251//

2252// Because Frags is sorted by size and none have the same offset and

2253// size, we know that this frag can only be contained by subsequent

2254// elements.

2255SmallVector<DebugVariable, 8>::iterator OtherIt = It;

2256 ++OtherIt;

2257VariableID ThisVar = FnVarLocs->insertVariable(*It);

2258for (; OtherIt != IEnd; ++OtherIt) {

2259DIExpression::FragmentInfo OtherFrag = OtherIt->getFragmentOrDefault();

2260VariableID OtherVar = FnVarLocs->insertVariable(*OtherIt);

2261if (fullyContains(OtherFrag, Frag))

2262 Map[OtherVar].push_back(ThisVar);

2263 }

2264 }

2265 }

2266

2267// VariableIDs are 1-based so the variable-tracking bitvector needs

2268// NumVariables plus 1 bits.

2269 TrackedVariablesVectorSize = FnVarLocs->getNumVariables() + 1;

2270

2271// Finally, insert the declares afterwards, so the first IDs are all

2272// partially stack homed vars.

2273for (auto *DDI : InstDeclares)

2274 FnVarLocs->addSingleLocVar(DebugVariable(DDI), DDI->getExpression(),

2275 DDI->getDebugLoc(), DDI->getWrappedLocation());

2276for (auto *DVR : DPDeclares)

2277 FnVarLocs->addSingleLocVar(DebugVariable(DVR), DVR->getExpression(),

2278 DVR->getDebugLoc(),

2279RawLocationWrapper(DVR->getRawLocation()));

2280return Map;

2281}

2282

2283bool AssignmentTrackingLowering::run(FunctionVarLocsBuilder *FnVarLocsBuilder) {

2284if (Fn.size() >MaxNumBlocks) {

2285LLVM_DEBUG(dbgs() <<"[AT] Dropping var locs in: " << Fn.getName()

2286 <<": too many blocks (" << Fn.size() <<")\n");

2287at::deleteAll(&Fn);

2288returnfalse;

2289 }

2290

2291 FnVarLocs = FnVarLocsBuilder;

2292

2293// The general structure here is inspired by VarLocBasedImpl.cpp

2294// (LiveDebugValues).

2295

2296// Build the variable fragment overlap map.

2297// Note that this pass doesn't handle partial overlaps correctly (FWIW

2298// neither does LiveDebugVariables) because that is difficult to do and

2299// appears to be rare occurance.

2300 VarContains =buildOverlapMapAndRecordDeclares(

2301 Fn, FnVarLocs, *VarsWithStackSlot, UntaggedStoreVars,

2302 TrackedVariablesVectorSize);

2303

2304// Prepare for traversal.

2305ReversePostOrderTraversal<Function *> RPOT(&Fn);

2306 std::priority_queue<unsigned int, std::vector<unsigned int>,

2307 std::greater<unsigned int>>

2308 Worklist;

2309 std::priority_queue<unsigned int, std::vector<unsigned int>,

2310 std::greater<unsigned int>>

2311 Pending;

2312DenseMap<unsigned int, BasicBlock *> OrderToBB;

2313DenseMap<BasicBlock *, unsigned int> BBToOrder;

2314 {// Init OrderToBB and BBToOrder.

2315unsignedint RPONumber = 0;

2316for (BasicBlock *BB : RPOT) {

2317 OrderToBB[RPONumber] = BB;

2318 BBToOrder[BB] = RPONumber;

2319 Worklist.push(RPONumber);

2320 ++RPONumber;

2321 }

2322 LiveIn.init(RPONumber);

2323 LiveOut.init(RPONumber);

2324 }

2325

2326// Perform the traversal.

2327//

2328// This is a standard "union of predecessor outs" dataflow problem. To solve

2329// it, we perform join() and process() using the two worklist method until

2330// the LiveIn data for each block becomes unchanging. The "proof" that this

2331// terminates can be put together by looking at the comments around LocKind,

2332// Assignment, and the various join methods, which show that all the elements

2333// involved are made up of join-semilattices; LiveIn(n) can only

2334// monotonically increase in value throughout the dataflow.

2335//

2336SmallPtrSet<BasicBlock *, 16> Visited;

2337while (!Worklist.empty()) {

2338// We track what is on the pending worklist to avoid inserting the same

2339// thing twice.

2340SmallPtrSet<BasicBlock *, 16> OnPending;

2341LLVM_DEBUG(dbgs() <<"Processing Worklist\n");

2342while (!Worklist.empty()) {

2343BasicBlock *BB = OrderToBB[Worklist.top()];

2344LLVM_DEBUG(dbgs() <<"\nPop BB " << BB->getName() <<"\n");

2345 Worklist.pop();

2346bool InChanged = join(*BB, Visited);

2347// Always consider LiveIn changed on the first visit.

2348 InChanged |= Visited.insert(BB).second;

2349if (InChanged) {

2350LLVM_DEBUG(dbgs() << BB->getName() <<" has new InLocs, process it\n");

2351// Mutate a copy of LiveIn while processing BB. After calling process

2352// LiveSet is the LiveOut set for BB.

2353 BlockInfo LiveSet = LiveIn[BB];

2354

2355// Process the instructions in the block.

2356 process(*BB, &LiveSet);

2357

2358// Relatively expensive check: has anything changed in LiveOut for BB?

2359if (LiveOut[BB] != LiveSet) {

2360LLVM_DEBUG(dbgs() << BB->getName()

2361 <<" has new OutLocs, add succs to worklist: [ ");

2362 LiveOut[BB] = std::move(LiveSet);

2363for (BasicBlock *Succ :successors(BB)) {

2364if (OnPending.insert(Succ).second) {

2365LLVM_DEBUG(dbgs() << Succ->getName() <<" ");

2366 Pending.push(BBToOrder[Succ]);

2367 }

2368 }

2369LLVM_DEBUG(dbgs() <<"]\n");

2370 }

2371 }

2372 }

2373 Worklist.swap(Pending);

2374// At this point, pending must be empty, since it was just the empty

2375// worklist

2376assert(Pending.empty() &&"Pending should be empty");

2377 }

2378

2379// That's the hard part over. Now we just have some admin to do.

2380

2381// Record whether we inserted any intrinsics.

2382bool InsertedAnyIntrinsics =false;

2383

2384// Identify and add defs for single location variables.

2385//

2386// Go through all of the defs that we plan to add. If the aggregate variable

2387// it's a part of is not in the NotAlwaysStackHomed set we can emit a single

2388// location def and omit the rest. Add an entry to AlwaysStackHomed so that

2389// we can identify those uneeded defs later.

2390DenseSet<DebugAggregate> AlwaysStackHomed;

2391for (constauto &Pair : InsertBeforeMap) {

2392auto &Vec = Pair.second;

2393for (VarLocInfo VarLoc : Vec) {

2394DebugVariable Var = FnVarLocs->getVariable(VarLoc.VariableID);

2395DebugAggregate Aggr{Var.getVariable(), Var.getInlinedAt()};

2396

2397// Skip this Var if it's not always stack homed.

2398if (NotAlwaysStackHomed.contains(Aggr))

2399continue;

2400

2401// Skip complex cases such as when different fragments of a variable have

2402// been split into different allocas. Skipping in this case means falling

2403// back to using a list of defs (which could reduce coverage, but is no

2404// less correct).

2405boolSimple =

2406 VarLoc.Expr->getNumElements() == 1 && VarLoc.Expr->startsWithDeref();

2407if (!Simple) {

2408 NotAlwaysStackHomed.insert(Aggr);

2409continue;

2410 }

2411

2412// All source assignments to this variable remain and all stores to any

2413// part of the variable store to the same address (with varying

2414// offsets). We can just emit a single location for the whole variable.

2415//

2416// Unless we've already done so, create the single location def now.

2417if (AlwaysStackHomed.insert(Aggr).second) {

2418assert(!VarLoc.Values.hasArgList());

2419// TODO: When more complex cases are handled VarLoc.Expr should be

2420// built appropriately rather than always using an empty DIExpression.

2421// The assert below is a reminder.

2422assert(Simple);

2423 VarLoc.Expr =DIExpression::get(Fn.getContext(), {});

2424DebugVariable Var = FnVarLocs->getVariable(VarLoc.VariableID);

2425 FnVarLocs->addSingleLocVar(Var, VarLoc.Expr, VarLoc.DL, VarLoc.Values);

2426 InsertedAnyIntrinsics =true;

2427 }

2428 }

2429 }

2430

2431// Insert the other DEFs.

2432for (constauto &[InsertBefore, Vec] : InsertBeforeMap) {

2433SmallVector<VarLocInfo> NewDefs;

2434for (constVarLocInfo &VarLoc : Vec) {

2435DebugVariable Var = FnVarLocs->getVariable(VarLoc.VariableID);

2436DebugAggregate Aggr{Var.getVariable(), Var.getInlinedAt()};

2437// If this variable is always stack homed then we have already inserted a

2438// dbg.declare and deleted this dbg.value.

2439if (AlwaysStackHomed.contains(Aggr))

2440continue;

2441 NewDefs.push_back(VarLoc);

2442 InsertedAnyIntrinsics =true;

2443 }

2444

2445 FnVarLocs->setWedge(InsertBefore, std::move(NewDefs));

2446 }

2447

2448 InsertedAnyIntrinsics |= emitPromotedVarLocs(FnVarLocs);

2449

2450return InsertedAnyIntrinsics;

2451}

2452

2453bool AssignmentTrackingLowering::emitPromotedVarLocs(

2454FunctionVarLocsBuilder *FnVarLocs) {

2455bool InsertedAnyIntrinsics =false;

2456// Go through every block, translating debug intrinsics for fully promoted

2457// variables into FnVarLocs location defs. No analysis required for these.

2458auto TranslateDbgRecord = [&](auto *Record) {

2459// Skip variables that haven't been promoted - we've dealt with those

2460// already.

2461if (VarsWithStackSlot->contains(getAggregate(Record)))

2462return;

2463auto InsertBefore =getNextNode(Record);

2464assert(InsertBefore &&"Unexpected: debug intrinsics after a terminator");

2465 FnVarLocs->addVarLoc(InsertBefore,DebugVariable(Record),

2466Record->getExpression(),Record->getDebugLoc(),

2467RawLocationWrapper(Record->getRawLocation()));

2468 InsertedAnyIntrinsics =true;

2469 };

2470for (auto &BB : Fn) {

2471for (auto &I : BB) {

2472// Skip instructions other than dbg.values and dbg.assigns.

2473for (DbgVariableRecord &DVR :filterDbgVars(I.getDbgRecordRange()))

2474if (DVR.isDbgValue() || DVR.isDbgAssign())

2475 TranslateDbgRecord(&DVR);

2476auto *DVI = dyn_cast<DbgValueInst>(&I);

2477if (DVI)

2478 TranslateDbgRecord(DVI);

2479 }

2480 }

2481return InsertedAnyIntrinsics;

2482}

2483

2484/// Remove redundant definitions within sequences of consecutive location defs.

2485/// This is done using a backward scan to keep the last def describing a

2486/// specific variable/fragment.

2487///

2488/// This implements removeRedundantDbgInstrsUsingBackwardScan from

2489/// lib/Transforms/Utils/BasicBlockUtils.cpp for locations described with

2490/// FunctionVarLocsBuilder instead of with intrinsics.

2491staticbool

2492removeRedundantDbgLocsUsingBackwardScan(constBasicBlock *BB,

2493FunctionVarLocsBuilder &FnVarLocs) {

2494bool Changed =false;

2495SmallDenseMap<DebugAggregate, BitVector> VariableDefinedBytes;

2496// Scan over the entire block, not just over the instructions mapped by

2497// FnVarLocs, because wedges in FnVarLocs may only be separated by debug

2498// instructions.

2499for (constInstruction &I :reverse(*BB)) {

2500if (!isa<DbgVariableIntrinsic>(I)) {

2501// Sequence of consecutive defs ended. Clear map for the next one.

2502 VariableDefinedBytes.clear();

2503 }

2504

2505auto HandleLocsForWedge = [&](auto *WedgePosition) {

2506// Get the location defs that start just before this instruction.

2507constauto *Locs = FnVarLocs.getWedge(WedgePosition);

2508if (!Locs)

2509return;

2510

2511 NumWedgesScanned++;

2512bool ChangedThisWedge =false;

2513// The new pruned set of defs, reversed because we're scanning backwards.

2514SmallVector<VarLocInfo> NewDefsReversed;

2515

2516// Iterate over the existing defs in reverse.

2517for (auto RIt = Locs->rbegin(), REnd = Locs->rend(); RIt != REnd; ++RIt) {

2518 NumDefsScanned++;

2519DebugAggregate Aggr =

2520getAggregate(FnVarLocs.getVariable(RIt->VariableID));

2521uint64_t SizeInBits = Aggr.first->getSizeInBits().value_or(0);

2522uint64_t SizeInBytes =divideCeil(SizeInBits, 8);

2523

2524// Cutoff for large variables to prevent expensive bitvector operations.

2525constuint64_t MaxSizeBytes = 2048;

2526

2527if (SizeInBytes == 0 || SizeInBytes > MaxSizeBytes) {

2528// If the size is unknown (0) then keep this location def to be safe.

2529// Do the same for defs of large variables, which would be expensive

2530// to represent with a BitVector.

2531 NewDefsReversed.push_back(*RIt);

2532continue;

2533 }

2534

2535// Only keep this location definition if it is not fully eclipsed by

2536// other definitions in this wedge that come after it

2537

2538// Inert the bytes the location definition defines.

2539auto InsertResult =

2540 VariableDefinedBytes.try_emplace(Aggr,BitVector(SizeInBytes));

2541bool FirstDefinition = InsertResult.second;

2542BitVector &DefinedBytes = InsertResult.first->second;

2543

2544DIExpression::FragmentInfo Fragment =

2545 RIt->Expr->getFragmentInfo().value_or(

2546DIExpression::FragmentInfo(SizeInBits, 0));

2547bool InvalidFragment = Fragment.endInBits() > SizeInBits;

2548uint64_t StartInBytes = Fragment.startInBits() / 8;

2549uint64_t EndInBytes =divideCeil(Fragment.endInBits(), 8);

2550

2551// If this defines any previously undefined bytes, keep it.

2552if (FirstDefinition || InvalidFragment ||

2553 DefinedBytes.find_first_unset_in(StartInBytes, EndInBytes) != -1) {

2554if (!InvalidFragment)

2555 DefinedBytes.set(StartInBytes, EndInBytes);

2556 NewDefsReversed.push_back(*RIt);

2557continue;

2558 }

2559

2560// Redundant def found: throw it away. Since the wedge of defs is being

2561// rebuilt, doing nothing is the same as deleting an entry.

2562 ChangedThisWedge =true;

2563 NumDefsRemoved++;

2564 }

2565

2566// Un-reverse the defs and replace the wedge with the pruned version.

2567if (ChangedThisWedge) {

2568 std::reverse(NewDefsReversed.begin(), NewDefsReversed.end());

2569 FnVarLocs.setWedge(WedgePosition, std::move(NewDefsReversed));

2570 NumWedgesChanged++;

2571 Changed =true;

2572 }

2573 };

2574 HandleLocsForWedge(&I);

2575for (DbgVariableRecord &DVR :reverse(filterDbgVars(I.getDbgRecordRange())))

2576 HandleLocsForWedge(&DVR);

2577 }

2578

2579return Changed;

2580}

2581

2582/// Remove redundant location defs using a forward scan. This can remove a

2583/// location definition that is redundant due to indicating that a variable has

2584/// the same value as is already being indicated by an earlier def.

2585///

2586/// This implements removeRedundantDbgInstrsUsingForwardScan from

2587/// lib/Transforms/Utils/BasicBlockUtils.cpp for locations described with

2588/// FunctionVarLocsBuilder instead of with intrinsics

2589staticbool

2590removeRedundantDbgLocsUsingForwardScan(constBasicBlock *BB,

2591FunctionVarLocsBuilder &FnVarLocs) {

2592bool Changed =false;

2593DenseMap<DebugVariable, std::pair<RawLocationWrapper, DIExpression *>>

2594 VariableMap;

2595

2596// Scan over the entire block, not just over the instructions mapped by

2597// FnVarLocs, because wedges in FnVarLocs may only be separated by debug

2598// instructions.

2599for (constInstruction &I : *BB) {

2600// Get the defs that come just before this instruction.

2601auto HandleLocsForWedge = [&](auto *WedgePosition) {

2602constauto *Locs = FnVarLocs.getWedge(WedgePosition);

2603if (!Locs)

2604return;

2605

2606 NumWedgesScanned++;

2607bool ChangedThisWedge =false;

2608// The new pruned set of defs.

2609SmallVector<VarLocInfo> NewDefs;

2610

2611// Iterate over the existing defs.

2612for (constVarLocInfo &Loc : *Locs) {

2613 NumDefsScanned++;

2614DebugVariable Key(FnVarLocs.getVariable(Loc.VariableID).getVariable(),

2615 std::nullopt, Loc.DL.getInlinedAt());

2616auto VMI = VariableMap.find(Key);

2617

2618// Update the map if we found a new value/expression describing the

2619// variable, or if the variable wasn't mapped already.

2620if (VMI == VariableMap.end() || VMI->second.first != Loc.Values ||

2621 VMI->second.second != Loc.Expr) {

2622 VariableMap[Key] = {Loc.Values, Loc.Expr};

2623 NewDefs.push_back(Loc);

2624continue;

2625 }

2626

2627// Did not insert this Loc, which is the same as removing it.

2628 ChangedThisWedge =true;

2629 NumDefsRemoved++;

2630 }

2631

2632// Replace the existing wedge with the pruned version.

2633if (ChangedThisWedge) {

2634 FnVarLocs.setWedge(WedgePosition, std::move(NewDefs));

2635 NumWedgesChanged++;

2636 Changed =true;

2637 }

2638 };

2639

2640for (DbgVariableRecord &DVR :filterDbgVars(I.getDbgRecordRange()))

2641 HandleLocsForWedge(&DVR);

2642 HandleLocsForWedge(&I);

2643 }

2644

2645return Changed;

2646}

2647

2648staticbool

2649removeUndefDbgLocsFromEntryBlock(constBasicBlock *BB,

2650FunctionVarLocsBuilder &FnVarLocs) {

2651assert(BB->isEntryBlock());

2652// Do extra work to ensure that we remove semantically unimportant undefs.

2653//

2654// This is to work around the fact that SelectionDAG will hoist dbg.values

2655// using argument values to the top of the entry block. That can move arg

2656// dbg.values before undef and constant dbg.values which they previously

2657// followed. The easiest thing to do is to just try to feed SelectionDAG

2658// input it's happy with.

2659//

2660// Map of {Variable x: Fragments y} where the fragments y of variable x have

2661// have at least one non-undef location defined already. Don't use directly,

2662// instead call DefineBits and HasDefinedBits.

2663SmallDenseMap<DebugAggregate, SmallDenseSet<DIExpression::FragmentInfo>>

2664 VarsWithDef;

2665// Specify that V (a fragment of A) has a non-undef location.

2666auto DefineBits = [&VarsWithDef](DebugAggregate A,DebugVariable V) {

2667 VarsWithDef[A].insert(V.getFragmentOrDefault());

2668 };

2669// Return true if a non-undef location has been defined for V (a fragment of

2670// A). Doesn't imply that the location is currently non-undef, just that a

2671// non-undef location has been seen previously.

2672auto HasDefinedBits = [&VarsWithDef](DebugAggregate A,DebugVariable V) {

2673auto FragsIt = VarsWithDef.find(A);

2674if (FragsIt == VarsWithDef.end())

2675returnfalse;

2676returnllvm::any_of(FragsIt->second, [V](auto Frag) {

2677 return DIExpression::fragmentsOverlap(Frag, V.getFragmentOrDefault());

2678 });

2679 };

2680

2681bool Changed =false;

2682DenseMap<DebugVariable, std::pair<Value *, DIExpression *>> VariableMap;

2683

2684// Scan over the entire block, not just over the instructions mapped by

2685// FnVarLocs, because wedges in FnVarLocs may only be separated by debug

2686// instructions.

2687for (constInstruction &I : *BB) {

2688// Get the defs that come just before this instruction.

2689auto HandleLocsForWedge = [&](auto *WedgePosition) {

2690constauto *Locs = FnVarLocs.getWedge(WedgePosition);

2691if (!Locs)

2692return;

2693

2694 NumWedgesScanned++;

2695bool ChangedThisWedge =false;

2696// The new pruned set of defs.

2697SmallVector<VarLocInfo> NewDefs;

2698

2699// Iterate over the existing defs.

2700for (constVarLocInfo &Loc : *Locs) {

2701 NumDefsScanned++;

2702DebugAggregate Aggr{FnVarLocs.getVariable(Loc.VariableID).getVariable(),

2703 Loc.DL.getInlinedAt()};

2704DebugVariable Var = FnVarLocs.getVariable(Loc.VariableID);

2705

2706// Remove undef entries that are encountered before any non-undef

2707// intrinsics from the entry block.

2708if (Loc.Values.isKillLocation(Loc.Expr) && !HasDefinedBits(Aggr, Var)) {

2709// Did not insert this Loc, which is the same as removing it.

2710 NumDefsRemoved++;

2711 ChangedThisWedge =true;

2712continue;

2713 }

2714

2715 DefineBits(Aggr, Var);

2716 NewDefs.push_back(Loc);

2717 }

2718

2719// Replace the existing wedge with the pruned version.

2720if (ChangedThisWedge) {

2721 FnVarLocs.setWedge(WedgePosition, std::move(NewDefs));

2722 NumWedgesChanged++;

2723 Changed =true;

2724 }

2725 };

2726for (DbgVariableRecord &DVR :filterDbgVars(I.getDbgRecordRange()))

2727 HandleLocsForWedge(&DVR);

2728 HandleLocsForWedge(&I);

2729 }

2730

2731return Changed;

2732}

2733

2734staticboolremoveRedundantDbgLocs(constBasicBlock *BB,

2735FunctionVarLocsBuilder &FnVarLocs) {

2736bool MadeChanges =false;

2737 MadeChanges |=removeRedundantDbgLocsUsingBackwardScan(BB, FnVarLocs);

2738if (BB->isEntryBlock())

2739 MadeChanges |=removeUndefDbgLocsFromEntryBlock(BB, FnVarLocs);

2740 MadeChanges |=removeRedundantDbgLocsUsingForwardScan(BB, FnVarLocs);

2741

2742if (MadeChanges)

2743LLVM_DEBUG(dbgs() <<"Removed redundant dbg locs from: " << BB->getName()

2744 <<"\n");

2745return MadeChanges;

2746}

2747

2748staticDenseSet<DebugAggregate>findVarsWithStackSlot(Function &Fn) {

2749DenseSet<DebugAggregate> Result;

2750for (auto &BB : Fn) {

2751for (auto &I : BB) {

2752// Any variable linked to an instruction is considered

2753// interesting. Ideally we only need to check Allocas, however, a

2754// DIAssignID might get dropped from an alloca but not stores. In that

2755// case, we need to consider the variable interesting for NFC behaviour

2756// with this change. TODO: Consider only looking at allocas.

2757for (DbgAssignIntrinsic *DAI :at::getAssignmentMarkers(&I)) {

2758 Result.insert({DAI->getVariable(), DAI->getDebugLoc().getInlinedAt()});

2759 }

2760for (DbgVariableRecord *DVR :at::getDVRAssignmentMarkers(&I)) {

2761 Result.insert({DVR->getVariable(), DVR->getDebugLoc().getInlinedAt()});

2762 }

2763 }

2764 }

2765return Result;

2766}

2767

2768staticvoidanalyzeFunction(Function &Fn,constDataLayout &Layout,

2769FunctionVarLocsBuilder *FnVarLocs) {

2770// The analysis will generate location definitions for all variables, but we

2771// only need to perform a dataflow on the set of variables which have a stack

2772// slot. Find those now.

2773DenseSet<DebugAggregate> VarsWithStackSlot =findVarsWithStackSlot(Fn);

2774

2775bool Changed =false;

2776

2777// Use a scope block to clean up AssignmentTrackingLowering before running

2778// MemLocFragmentFill to reduce peak memory consumption.

2779 {

2780 AssignmentTrackingLoweringPass(Fn, Layout, &VarsWithStackSlot);

2781 Changed =Pass.run(FnVarLocs);

2782 }

2783

2784if (Changed) {

2785 MemLocFragmentFillPass(Fn, &VarsWithStackSlot,

2786shouldCoalesceFragments(Fn));

2787Pass.run(FnVarLocs);

2788

2789// Remove redundant entries. As well as reducing memory consumption and

2790// avoiding waiting cycles later by burning some now, this has another

2791// important job. That is to work around some SelectionDAG quirks. See

2792// removeRedundantDbgLocsUsingForwardScan comments for more info on that.

2793for (auto &BB : Fn)

2794removeRedundantDbgLocs(&BB, *FnVarLocs);

2795 }

2796}

2797

2798FunctionVarLocs

2799DebugAssignmentTrackingAnalysis::run(Function &F,

2800FunctionAnalysisManager &FAM) {

2801if (!isAssignmentTrackingEnabled(*F.getParent()))

2802returnFunctionVarLocs();

2803

2804auto &DL =F.getDataLayout();

2805

2806FunctionVarLocsBuilder Builder;

2807analyzeFunction(F,DL, &Builder);

2808

2809// Save these results.

2810FunctionVarLocs Results;

2811Results.init(Builder);

2812returnResults;

2813}

2814

2815AnalysisKey DebugAssignmentTrackingAnalysis::Key;

2816

2817PreservedAnalyses

2818DebugAssignmentTrackingPrinterPass::run(Function &F,

2819FunctionAnalysisManager &FAM) {

2820FAM.getResult<DebugAssignmentTrackingAnalysis>(F).print(OS,F);

2821returnPreservedAnalyses::all();

2822}

2823

2824boolAssignmentTrackingAnalysis::runOnFunction(Function &F) {

2825if (!isAssignmentTrackingEnabled(*F.getParent()))

2826returnfalse;

2827

2828LLVM_DEBUG(dbgs() <<"AssignmentTrackingAnalysis run on " <<F.getName()

2829 <<"\n");

2830

2831// Clear previous results.

2832 Results->clear();

2833

2834FunctionVarLocsBuilder Builder;

2835analyzeFunction(F,F.getDataLayout(), &Builder);

2836

2837// Save these results.

2838 Results->init(Builder);

2839

2840if (PrintResults &&isFunctionInPrintList(F.getName()))

2841 Results->print(errs(),F);

2842

2843// Return false because this pass does not modify the function.

2844returnfalse;

2845}

2846

2847AssignmentTrackingAnalysis::AssignmentTrackingAnalysis()

2848 :FunctionPass(ID),Results(std::make_unique<FunctionVarLocs>()) {}

2849

2850charAssignmentTrackingAnalysis::ID = 0;

2851

2852INITIALIZE_PASS(AssignmentTrackingAnalysis,DEBUG_TYPE,

2853"Assignment Tracking Analysis",false,true)

for

for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))

Definition:AArch64ExpandPseudoInsts.cpp:115

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Definition:ARMSLSHardening.cpp:73

Results

Function Alias Analysis Results

Definition:AliasAnalysis.cpp:731

DebugAggregate

std::pair< const DILocalVariable *, const DILocation * > DebugAggregate

A whole (unfragmented) source variable.

Definition:AssignmentTrackingAnalysis.cpp:329

getNextNode

VarLocInsertPt getNextNode(const DbgRecord *DVR)

Definition:AssignmentTrackingAnalysis.cpp:1498

analyzeFunction

static void analyzeFunction(Function &Fn, const DataLayout &Layout, FunctionVarLocsBuilder *FnVarLocs)

Definition:AssignmentTrackingAnalysis.cpp:2768

walkToAllocaAndPrependOffsetDeref

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.

Definition:AssignmentTrackingAnalysis.cpp:268

getIDFromMarker

static DIAssignID * getIDFromMarker(const DbgAssignIntrinsic &DAI)

Definition:AssignmentTrackingAnalysis.cpp:1458

findVarsWithStackSlot

static DenseSet< DebugAggregate > findVarsWithStackSlot(Function &Fn)

Definition:AssignmentTrackingAnalysis.cpp:2748

fullyContains

static bool fullyContains(DIExpression::FragmentInfo A, DIExpression::FragmentInfo B)

Return true if A fully contains B.

Definition:AssignmentTrackingAnalysis.cpp:2099

getAggregate

static DebugAggregate getAggregate(const DbgVariableIntrinsic *DII)

Definition:AssignmentTrackingAnalysis.cpp:330

getUntaggedStoreAssignmentInfo

static std::optional< at::AssignmentInfo > getUntaggedStoreAssignmentInfo(const Instruction &I, const DataLayout &Layout)

Definition:AssignmentTrackingAnalysis.cpp:2114

buildOverlapMapAndRecordDeclares

static AssignmentTrackingLowering::OverlapMap buildOverlapMapAndRecordDeclares(Function &Fn, FunctionVarLocsBuilder *FnVarLocs, const DenseSet< DebugAggregate > &VarsWithStackSlot, AssignmentTrackingLowering::UntaggedStoreAssignmentMap &UntaggedStoreVars, unsigned &TrackedVariablesVectorSize)

Build a map of {Variable x: Variables y} where all variable fragments contained within the variable f...

Definition:AssignmentTrackingAnalysis.cpp:2152

removeUndefDbgLocsFromEntryBlock

static bool removeUndefDbgLocsFromEntryBlock(const BasicBlock *BB, FunctionVarLocsBuilder &FnVarLocs)

Definition:AssignmentTrackingAnalysis.cpp:2649

PrintResults

static cl::opt< bool > PrintResults("print-debug-ata", cl::init(false), cl::Hidden)

Print the results of the analysis. Respects -filter-print-funcs.

locStr

const char * locStr(AssignmentTrackingLowering::LocKind Loc)

Definition:AssignmentTrackingAnalysis.cpp:1484

VarLocInsertPt

PointerUnion< const Instruction *, const DbgRecord * > VarLocInsertPt

Definition:AssignmentTrackingAnalysis.cpp:85

removeRedundantDbgLocsUsingForwardScan

static bool removeRedundantDbgLocsUsingForwardScan(const BasicBlock *BB, FunctionVarLocsBuilder &FnVarLocs)

Remove redundant location defs using a forward scan.

Definition:AssignmentTrackingAnalysis.cpp:2590

removeRedundantDbgLocs

static bool removeRedundantDbgLocs(const BasicBlock *BB, FunctionVarLocsBuilder &FnVarLocs)

Definition:AssignmentTrackingAnalysis.cpp:2734

EnableMemLocFragFill

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...

getIDFromInst

static DIAssignID * getIDFromInst(const Instruction &I)

Definition:AssignmentTrackingAnalysis.cpp:1454

CastToDbgAssign

DbgAssignIntrinsic * CastToDbgAssign(DbgVariableIntrinsic *DVI)

Definition:AssignmentTrackingAnalysis.cpp:1516

getDerefOffsetInBytes

static std::optional< int64_t > getDerefOffsetInBytes(const DIExpression *DIExpr)

Extract the offset used in DIExpr.

Definition:AssignmentTrackingAnalysis.cpp:287

removeRedundantDbgLocsUsingBackwardScan

static bool removeRedundantDbgLocsUsingBackwardScan(const BasicBlock *BB, FunctionVarLocsBuilder &FnVarLocs)

Remove redundant definitions within sequences of consecutive location defs.

Definition:AssignmentTrackingAnalysis.cpp:2492

hasZeroSizedFragment

static bool hasZeroSizedFragment(T &DbgValue)

Definition:AssignmentTrackingAnalysis.cpp:1844

CoalesceAdjacentFragmentsOpt

static cl::opt< cl::boolOrDefault > CoalesceAdjacentFragmentsOpt("debug-ata-coalesce-frags", cl::Hidden)

Coalesce adjacent dbg locs describing memory locations that have contiguous fragments.

MaxNumBlocks

static cl::opt< unsigned > MaxNumBlocks("debug-ata-max-blocks", cl::init(10000), cl::desc("Maximum num basic blocks before debug info dropped"), cl::Hidden)

shouldCoalesceFragments

static bool shouldCoalesceFragments(Function &F)

Definition:AssignmentTrackingAnalysis.cpp:337

DynCastToDbgDeclare

DbgDeclareInst * DynCastToDbgDeclare(DbgVariableIntrinsic *DVI)

Definition:AssignmentTrackingAnalysis.cpp:2126

AssignmentTrackingAnalysis.h

BasicBlockUtils.h

BitVector.h

This file implements the BitVector class.

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

Info

Analysis containing CSE Info

Definition:CSEInfo.cpp:27

CommandLine.h

DataLayout.h

DebugProgramInstruction.h

Debug

static ManagedStatic< cl::opt< bool, true >, CreateDebug > Debug

Definition:Debug.cpp:108

LLVM_DEBUG

#define LLVM_DEBUG(...)

Definition:Debug.h:106

DenseMapInfo.h

This file defines DenseMapInfo traits for DenseMap.

Dwarf.h

This file contains constants used for implementing Dwarf debug support.

Index

uint32_t Index

Definition:ELFObjHandler.cpp:83

Other

std::optional< std::vector< StOtherPiece > > Other

Definition:ELFYAML.cpp:1315

End

bool End

Definition:ELF_riscv.cpp:480

DEBUG_TYPE

#define DEBUG_TYPE

Definition:GenericCycleImpl.h:31

IRTranslator LLVM IR MI

Definition:IRTranslator.cpp:112

Module.h This file contains the declarations for the Module class.

PassManager.h

This header defines various interfaces for pass management in LLVM.

InitializePasses.h

IntervalMap.h

This file implements a coalescing interval map for small objects.

LiveDebugValues.h

#define F(x, y, z)

Definition:MD5.cpp:55

#define I(x, y, z)

Definition:MD5.cpp:58

uint64_t IntrinsicInst * II

Definition:NVVMIntrRange.cpp:51

#define P(N)

FAM

FunctionAnalysisManager FAM

Definition:PassBuilderBindings.cpp:61

INITIALIZE_PASS

#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)

Definition:PassSupport.h:38

PostOrderIterator.h

This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.

PrintPasses.h

isValid

static bool isValid(const char C)

Returns true if C is a valid mangled character: <0-9a-zA-Z_>.

Definition:RustDemangle.cpp:181

assert

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

Aggregates

Scalar Replacement Of Aggregates

Definition:SROA.cpp:5847

STLExtras.h

This file contains some templates that are useful if you are working with the STL at all.

raw_pwrite_stream & OS

Definition:SampleProfWriter.cpp:51

IRDumpFileSuffixType::After

@ After

IRDumpFileSuffixType::Before

@ Before

Statistic.h

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

STATISTIC

#define STATISTIC(VARNAME, DESC)

Definition:Statistic.h:166

LUT

static const char LUT[]

Definition:TypeSanitizer.cpp:199

UniqueVector.h

RHS

Value * RHS

Definition:X86PartialReduction.cpp:74

LHS

Value * LHS

Definition:X86PartialReduction.cpp:73

FunctionVarLocsBuilder

Helper class to build FunctionVarLocs, since that class isn't easy to modify.

Definition:AssignmentTrackingAnalysis.cpp:101

FunctionVarLocsBuilder::setWedge

void setWedge(VarLocInsertPt Before, SmallVector< VarLocInfo > &&Wedge)

Replace the defs that come just before /p Before with /p Wedge.

Definition:AssignmentTrackingAnalysis.cpp:133

FunctionVarLocsBuilder::getWedge

const SmallVectorImpl< VarLocInfo > * getWedge(VarLocInsertPt Before) const

Return ptr to wedge of defs or nullptr if no defs come just before /p Before.

Definition:AssignmentTrackingAnalysis.cpp:125

FunctionVarLocsBuilder::getNumVariables

unsigned getNumVariables() const

Definition:AssignmentTrackingAnalysis.cpp:111

FunctionVarLocsBuilder::addSingleLocVar

void addSingleLocVar(DebugVariable Var, DIExpression *Expr, DebugLoc DL, RawLocationWrapper R)

Add a def for a variable that is valid for its lifetime.

Definition:AssignmentTrackingAnalysis.cpp:138

FunctionVarLocsBuilder::insertVariable

VariableID insertVariable(DebugVariable V)

Find or insert V and return the ID.

Definition:AssignmentTrackingAnalysis.cpp:114

FunctionVarLocsBuilder::addVarLoc

void addVarLoc(VarLocInsertPt Before, DebugVariable Var, DIExpression *Expr, DebugLoc DL, RawLocationWrapper R)

Add a def to the wedge of defs just before /p Before.

Definition:AssignmentTrackingAnalysis.cpp:149

FunctionVarLocsBuilder::getVariable

const DebugVariable & getVariable(VariableID ID) const

Get a variable from its ID.

Definition:AssignmentTrackingAnalysis.cpp:119

LiveDebugValues::DbgValue

Class recording the (high level) value of a variable.

Definition:InstrRefBasedImpl.h:512

llvm::APInt

Class for arbitrary precision integers.

Definition:APInt.h:78

llvm::APInt::getZExtValue

uint64_t getZExtValue() const

Get zero extended value.

Definition:APInt.h:1520

llvm::APInt::getBoolValue

bool getBoolValue() const

Convert APInt to a boolean value.

Definition:APInt.h:471

llvm::AllocaInst

an instruction to allocate memory on the stack

Definition:Instructions.h:63

llvm::AnalysisManager

A container for analyses that lazily runs them and caches their results.

Definition:PassManager.h:253

llvm::AnalysisManager::getResult

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

Definition:PassManager.h:410

llvm::ArrayRef

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

Definition:ArrayRef.h:41

llvm::ArrayRef::drop_front

ArrayRef< T > drop_front(size_t N=1) const

Drop the first N elements of the array.

Definition:ArrayRef.h:207

llvm::AssignmentTrackingAnalysis

Definition:AssignmentTrackingAnalysis.h:124

llvm::AssignmentTrackingAnalysis::AssignmentTrackingAnalysis

AssignmentTrackingAnalysis()

Definition:AssignmentTrackingAnalysis.cpp:2847

llvm::AssignmentTrackingAnalysis::runOnFunction

bool runOnFunction(Function &F) override

runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.

Definition:AssignmentTrackingAnalysis.cpp:2824

llvm::AssignmentTrackingAnalysis::ID

static char ID

Definition:AssignmentTrackingAnalysis.h:128

llvm::BasicBlock

LLVM Basic Block Representation.

Definition:BasicBlock.h:61

llvm::BasicBlock::end

iterator end()

Definition:BasicBlock.h:474

llvm::BasicBlock::begin

iterator begin()

Instruction iterator methods.

Definition:BasicBlock.h:461

llvm::BasicBlock::isEntryBlock

bool isEntryBlock() const

Return true if this is the entry block of the containing function.

Definition:BasicBlock.cpp:593

llvm::BitVector

Definition:BitVector.h:82

llvm::BitVector::find_first_unset_in

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

llvm::BitVector::set

BitVector & set()

Definition:BitVector.h:351

llvm::BitVector::set_bits

iterator_range< const_set_bits_iterator > set_bits() const

Definition:BitVector.h:140

llvm::DIAssignID

Assignment ID.

Definition:DebugInfoMetadata.h:309

llvm::DIE

A structured debug information entry.

Definition:DIE.h:819

llvm::DIExpression

DWARF expression.

Definition:DebugInfoMetadata.h:2763

llvm::DIExpression::append

static DIExpression * append(const DIExpression *Expr, ArrayRef< uint64_t > Ops)

Append the opcodes Ops to DIExpr.

Definition:DebugInfoMetadata.cpp:1948

llvm::DIExpression::getNumElements

unsigned getNumElements() const

Definition:DebugInfoMetadata.h:2789

llvm::DIExpression::startsWithDeref

bool startsWithDeref() const

Return whether the first element a DW_OP_deref.

Definition:DebugInfoMetadata.cpp:1382

llvm::DIExpression::DerefAfter

@ DerefAfter

Definition:DebugInfoMetadata.h:3046

llvm::DIExpression::getFragmentInfo

static std::optional< FragmentInfo > getFragmentInfo(expr_op_iterator Start, expr_op_iterator End)

Retrieve the details of this fragment expression.

Definition:DebugInfoMetadata.cpp:1677

llvm::DIExpression::getElements

ArrayRef< uint64_t > getElements() const

Definition:DebugInfoMetadata.h:2787

llvm::DIExpression::createFragmentExpression

static std::optional< DIExpression * > createFragmentExpression(const DIExpression *Expr, unsigned OffsetInBits, unsigned SizeInBits)

Create a DIExpression to describe one part of an aggregate variable that is fragmented across multipl...

Definition:DebugInfoMetadata.cpp:2006

llvm::DIExpression::prepend

static DIExpression * prepend(const DIExpression *Expr, uint8_t Flags, int64_t Offset=0)

Prepend DIExpr with a deref and offset operation and optionally turn it into a stack value or/and an ...

Definition:DebugInfoMetadata.cpp:1842

llvm::DIExpression::prependOpcodes

static DIExpression * prependOpcodes(const DIExpression *Expr, SmallVectorImpl< uint64_t > &Ops, bool StackValue=false, bool EntryValue=false)

Prepend DIExpr with the given opcodes and optionally turn it into a stack value.

Definition:DebugInfoMetadata.cpp:1915

llvm::DILocalVariable

Local variable.

Definition:DebugInfoMetadata.h:3460

llvm::DILocation

Debug location.

Definition:DebugInfoMetadata.h:1988

llvm::DIVariable::getSizeInBits

std::optional< uint64_t > getSizeInBits() const

Determines the size of the variable's type.

Definition:DebugInfoMetadata.cpp:1331

llvm::DIVariable::getName

StringRef getName() const

Definition:DebugInfoMetadata.h:2709

llvm::DWARFExpression::Operation

This class represents an Operation in the Expression.

Definition:DWARFExpression.h:32

llvm::DataLayout

A parsed version of the target data layout string in and methods for querying it.

Definition:DataLayout.h:63

llvm::DbgAssignIntrinsic

This represents the llvm.dbg.assign instruction.

Definition:IntrinsicInst.h:492

llvm::DbgAssignIntrinsic::getAssignID

DIAssignID * getAssignID() const

Definition:IntrinsicInst.h:510

llvm::DbgDeclareInst

This represents the llvm.dbg.declare instruction.

Definition:IntrinsicInst.h:448

llvm::DbgInfoIntrinsic

This is the common base class for debug info intrinsics.

Definition:IntrinsicInst.h:181

llvm::DbgMarker::MarkedInstr

Instruction * MarkedInstr

Link back to the Instruction that owns this marker.

Definition:DebugProgramInstruction.h:588

llvm::DbgMarker::getDbgRecordRange

iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange()

Produce a range over all the DbgRecords in this Marker.

Definition:DebugProgramInstruction.cpp:666

llvm::DbgRecord

Base class for non-instruction debug metadata records that have positions within IR.

Definition:DebugProgramInstruction.h:134

llvm::DbgRecord::getDebugLoc

DebugLoc getDebugLoc() const

Definition:DebugProgramInstruction.h:208

llvm::DbgRecord::getMarker

DbgMarker * getMarker()

Definition:DebugProgramInstruction.h:171

llvm::DbgVariableIntrinsic

This is the common base class for debug info intrinsics for variables.

Definition:IntrinsicInst.h:308

llvm::DbgVariableIntrinsic::getVariable

DILocalVariable * getVariable() const

Definition:IntrinsicInst.h:371

llvm::DbgVariableRecord

Record of a variable value-assignment, aka a non instruction representation of the dbg....

Definition:DebugProgramInstruction.h:270

llvm::DbgVariableRecord::isDbgValue

bool isDbgValue() const

Definition:DebugProgramInstruction.h:410

llvm::DbgVariableRecord::getAssignID

DIAssignID * getAssignID() const

Definition:DebugProgramInstruction.cpp:485

llvm::DbgVariableRecord::isDbgAssign

bool isDbgAssign() const

Definition:DebugProgramInstruction.h:506

llvm::DbgVariableRecord::getExpression

DIExpression * getExpression() const

Definition:DebugProgramInstruction.h:453

llvm::DbgVariableRecord::getVariable

DILocalVariable * getVariable() const

Definition:DebugProgramInstruction.h:449

llvm::DbgVariableRecord::getRawLocation

Metadata * getRawLocation() const

Returns the metadata operand for the first location description.

Definition:DebugProgramInstruction.h:460

llvm::DbgVariableRecord::isDbgDeclare

bool isDbgDeclare() const

Definition:DebugProgramInstruction.h:409

llvm::DebugAssignmentTrackingAnalysis

Definition:AssignmentTrackingAnalysis.h:106

llvm::DebugAssignmentTrackingAnalysis::run

Result run(Function &F, FunctionAnalysisManager &FAM)

Definition:AssignmentTrackingAnalysis.cpp:2799

llvm::DebugAssignmentTrackingPrinterPass::run

PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)

Definition:AssignmentTrackingAnalysis.cpp:2818

llvm::DebugLoc

A debug info location.

Definition:DebugLoc.h:33

llvm::DebugLoc::getInlinedAt

DILocation * getInlinedAt() const

Definition:DebugLoc.cpp:39

llvm::DebugVariable

Identifies a unique instance of a variable.

Definition:DebugInfoMetadata.h:4024

llvm::DebugVariable::getInlinedAt

const DILocation * getInlinedAt() const

Definition:DebugInfoMetadata.h:4052

llvm::DebugVariable::getVariable

const DILocalVariable * getVariable() const

Definition:DebugInfoMetadata.h:4050

llvm::DenseMapBase::find

iterator find(const_arg_type_t< KeyT > Val)

Definition:DenseMap.h:156

llvm::DenseMapBase::try_emplace

std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)

Definition:DenseMap.h:226

llvm::DenseMapBase::end

iterator end()

Definition:DenseMap.h:84

llvm::DenseMapBase::insert

std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)

Definition:DenseMap.h:211

llvm::DenseMapBase::clear

void clear()

Definition:DenseMap.h:110

llvm::DenseMap

Definition:DenseMap.h:727

llvm::DenseMap::init

void init(unsigned InitNumEntries)

Definition:DenseMap.h:803

llvm::DenseSet

Implements a dense probed hash-table based set.

Definition:DenseSet.h:278

llvm::Expression

Class representing an expression and its matching format.

Definition:FileCheckImpl.h:189

llvm::FunctionPass

FunctionPass class - This class is used to implement most global optimizations.

Definition:Pass.h:310

llvm::FunctionVarLocs

Data structure describing the variable locations in a function.

Definition:AssignmentTrackingAnalysis.h:38

llvm::FunctionVarLocs::print

void print(raw_ostream &OS, const Function &Fn) const

Definition:AssignmentTrackingAnalysis.cpp:160

llvm::FunctionVarLocs::locs_begin

const VarLocInfo * locs_begin(const Instruction *Before) const

First variable location definition that comes before Before.

Definition:AssignmentTrackingAnalysis.h:79

llvm::FunctionVarLocs::single_locs_begin

const VarLocInfo * single_locs_begin() const

Definition:AssignmentTrackingAnalysis.h:71

llvm::FunctionVarLocs::clear

void clear()

Definition:AssignmentTrackingAnalysis.cpp:256

llvm::FunctionVarLocs::locs_end

const VarLocInfo * locs_end(const Instruction *Before) const

One past the last variable location definition that comes before Before.

Definition:AssignmentTrackingAnalysis.h:87

llvm::FunctionVarLocs::single_locs_end

const VarLocInfo * single_locs_end() const

One past the last single-location variable location definition.

Definition:AssignmentTrackingAnalysis.h:73

llvm::FunctionVarLocs::init

void init(FunctionVarLocsBuilder &Builder)

Definition:AssignmentTrackingAnalysis.cpp:209

llvm::Function

Definition:Function.h:63

llvm::Function::getDataLayout

const DataLayout & getDataLayout() const

Get the data layout of the module this function belongs to.

Definition:Function.cpp:373

llvm::Function::size

size_t size() const

Definition:Function.h:858

llvm::Function::getContext

LLVMContext & getContext() const

getContext - Return a reference to the LLVMContext associated with this function.

Definition:Function.cpp:369

llvm::Instruction

Definition:Instruction.h:68

llvm::Instruction::getDbgRecordRange

iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const

Return a range over the DbgRecords attached to this instruction.

Definition:Instruction.h:104

llvm::Instruction::getDebugLoc

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

Definition:Instruction.h:511

llvm::Instruction::hasDbgRecords

bool hasDbgRecords() const

Returns true if any DbgRecords are attached to this instruction.

Definition:Instruction.cpp:280

llvm::IntervalMap

Definition:IntervalMap.h:936

llvm::IntervalMap::begin

const_iterator begin() const

Definition:IntervalMap.h:1146

llvm::IntervalMap::insert

void insert(KeyT a, KeyT b, ValT y)

insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.

Definition:IntervalMap.h:1129

llvm::IntervalMap::clear

void clear()

clear - Remove all entries.

Definition:IntervalMap.h:1330

llvm::MDNode::get

static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)

Definition:Metadata.h:1549

llvm::MachineBasicBlock::push_back

void push_back(MachineInstr *MI)

Definition:MachineBasicBlock.h:1002

llvm::MapVector

This class implements a map that also provides access to all stored values in a deterministic order.

Definition:MapVector.h:36

llvm::Metadata

Root of the metadata hierarchy.

Definition:Metadata.h:62

llvm::Pass

Pass interface - Implemented by all 'passes'.

Definition:Pass.h:94

llvm::PointerUnion

A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...

Definition:PointerUnion.h:118

llvm::PointerUnion::getOpaqueValue

void * getOpaqueValue() const

Definition:PointerUnion.h:199

llvm::PoisonValue::get

static PoisonValue * get(Type *T)

Static factory methods - Return an 'poison' object of the specified type.

Definition:Constants.cpp:1878

llvm::PreservedAnalyses

A set of analyses that are preserved following a run of a transformation pass.

Definition:Analysis.h:111

llvm::PreservedAnalyses::all

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

Definition:Analysis.h:117

llvm::RawLocationWrapper

Lightweight class that wraps the location operand metadata of a debug intrinsic.

Definition:IntrinsicInst.h:243

llvm::RawLocationWrapper::hasArgList

bool hasArgList() const

Definition:IntrinsicInst.h:267

llvm::Record

Definition:Record.h:1596

llvm::ReversePostOrderTraversal

Definition:PostOrderIterator.h:299

llvm::SmallDenseMap

Definition:DenseMap.h:883

llvm::SmallPtrSetImpl::count

size_type count(ConstPtrType Ptr) const

count - Return 1 if the specified pointer is in the set, 0 otherwise.

Definition:SmallPtrSet.h:452

llvm::SmallPtrSetImpl::insert

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

Definition:SmallPtrSet.h:384

llvm::SmallPtrSet

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

Definition:SmallPtrSet.h:519

llvm::SmallVectorBase::empty

bool empty() const

Definition:SmallVector.h:81

llvm::SmallVectorBase::size

size_t size() const

Definition:SmallVector.h:78

llvm::SmallVectorImpl

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

Definition:SmallVector.h:573

llvm::SmallVectorImpl::emplace_back

reference emplace_back(ArgTypes &&... Args)

Definition:SmallVector.h:937

llvm::SmallVectorImpl::clear

void clear()

Definition:SmallVector.h:610

llvm::SmallVectorTemplateBase::push_back

void push_back(const T &Elt)

Definition:SmallVector.h:413

llvm::SmallVectorTemplateCommon::end

iterator end()

Definition:SmallVector.h:269

llvm::SmallVectorTemplateCommon::begin

iterator begin()

Definition:SmallVector.h:267

llvm::SmallVector

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

Definition:SmallVector.h:1196

llvm::Target

Target - Wrapper for Target specific information.

Definition:TargetRegistry.h:144

llvm::Triple

Triple - Helper class for working with autoconf configuration names.

Definition:Triple.h:44

llvm::Type::getInt1Ty

static IntegerType * getInt1Ty(LLVMContext &C)

llvm::UniqueVector

UniqueVector - This class produces a sequential ID number (base 1) for each unique entry that is adde...

Definition:UniqueVector.h:24

llvm::UniqueVector::insert

unsigned insert(const T &Entry)

insert - Append entry to the vector if it doesn't already exist.

Definition:UniqueVector.h:40

llvm::UniqueVector::size

size_t size() const

size - Returns the number of entries in the vector.

Definition:UniqueVector.h:87

llvm::UniqueVector::end

iterator end()

Return an iterator to the end of the vector.

Definition:UniqueVector.h:81

llvm::UniqueVector::begin

iterator begin()

Return an iterator to the start of the vector.

Definition:UniqueVector.h:75

llvm::ValueAsMetadata::get

static ValueAsMetadata * get(Value *V)

Definition:Metadata.cpp:501

llvm::Value

LLVM Value Representation.

Definition:Value.h:74

llvm::Value::getName

StringRef getName() const

Return a constant reference to the value's name.

Definition:Value.cpp:309

llvm::cl::opt

Definition:CommandLine.h:1423

llvm::detail::DenseSetImpl::insert

std::pair< iterator, bool > insert(const ValueT &V)

Definition:DenseSet.h:213

llvm::detail::DenseSetImpl::contains

bool contains(const_arg_type_t< ValueT > V) const

Check if the set contains the given element.

Definition:DenseSet.h:193

llvm::detail::DenseSetImpl::count

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:95

llvm::ilist_node_impl::getIterator

self_iterator getIterator()

Definition:ilist_node.h:132

llvm::ilist_node_with_parent::getNextNode

NodeTy * getNextNode()

Get the next node, or nullptr for the list tail.

Definition:ilist_node.h:353

llvm::raw_ostream

This class implements an extremely fast bulk output stream that can only output to a stream.

Definition:raw_ostream.h:52

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

Definition:ErrorHandling.h:143

llvm::BitmaskEnumDetail::Mask

constexpr std::underlying_type_t< E > Mask()

Get a bitmask with 1s in all places up to the high-order bit of E's largest value.

Definition:BitmaskEnum.h:125

llvm::CallingConv::Tail

@ Tail

Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...

Definition:CallingConv.h:76

llvm::CallingConv::ID

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

Definition:CallingConv.h:24

llvm::M68k::MemAddrModeKind::V

@ V

llvm::M68k::MemAddrModeKind::K

@ K

llvm::RISCVFenceField::R

@ R

Definition:RISCVBaseInfo.h:373

llvm::Sched::Source

@ Source

Definition:TargetLowering.h:102

llvm::at::deleteAll

void deleteAll(Function *F)

Remove all Assignment Tracking related intrinsics and metadata from F.

Definition:DebugInfo.cpp:1906

llvm::at::getAssignmentMarkers

AssignmentMarkerRange getAssignmentMarkers(DIAssignID *ID)

Return a range of dbg.assign intrinsics which use \ID as an operand.

Definition:DebugInfo.cpp:1867

llvm::at::getDVRAssignmentMarkers

SmallVector< DbgVariableRecord * > getDVRAssignmentMarkers(const Instruction *Inst)

Definition:DebugInfo.h:240

llvm::at::getAssignmentInfo

std::optional< AssignmentInfo > getAssignmentInfo(const DataLayout &DL, const MemIntrinsic *I)

Definition:DebugInfo.cpp:2028

llvm::at::calculateFragmentIntersect

bool calculateFragmentIntersect(const DataLayout &DL, const Value *Dest, uint64_t SliceOffsetInBits, uint64_t SliceSizeInBits, const DbgAssignIntrinsic *DbgAssign, std::optional< DIExpression::FragmentInfo > &Result)

Calculate the fragment of the variable in DAI covered from (Dest + SliceOffsetInBits) to to (Dest + S...

Definition:DebugInfo.cpp:1962

llvm::cl::Hidden

@ Hidden

Definition:CommandLine.h:137

llvm::cl::BOU_FALSE

@ BOU_FALSE

Definition:CommandLine.h:637

llvm::cl::BOU_UNSET

@ BOU_UNSET

Definition:CommandLine.h:637

llvm::cl::BOU_TRUE

@ BOU_TRUE

Definition:CommandLine.h:637

llvm::cl::init

initializer< Ty > init(const Ty &Val)

Definition:CommandLine.h:443

llvm::dwarf::DW_OP_LLVM_fragment

@ DW_OP_LLVM_fragment

Only used in LLVM metadata.

Definition:Dwarf.h:142

llvm::dxil::PointerTypeAnalysis::run

PointerTypeMap run(const Module &M)

Compute the PointerTypeMap for the module M.

Definition:PointerTypeAnalysis.cpp:191

llvm::lltok::Kind

Kind

Definition:LLToken.h:18

llvm::mdconst::detail::make

T & make()

llvm::ms_demangle::IntrinsicFunctionKind::Assign

@ Assign

llvm::ms_demangle::QualifierMangleMode::Result

@ Result

llvm::msgpack::Type::Map

@ Map

llvm::pdb::PDB_MemoryType::Stack

@ Stack

llvm::pdb::PDB_TableType::Dbg

@ Dbg

llvm::sampleprof::Base

@ Base

Definition:Discriminator.h:58

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18

llvm::dump

void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)

Definition:SparseBitVector.h:877

llvm::Offset

@ Offset

Definition:DWP.cpp:480

llvm::all_of

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:1739

llvm::TailFoldingOpts::Simple

@ Simple

llvm::successors

auto successors(const MachineBasicBlock *BB)

Definition:MachineBasicBlock.h:1376

llvm::operator!=

bool operator!=(uint64_t V1, const APInt &V2)

Definition:APInt.h:2082

llvm::operator==

bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)

Definition:AddressRanges.h:153

llvm::print

Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)

Definition:GCNRegPressure.cpp:227

llvm::any_of

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:1746

llvm::reverse

auto reverse(ContainerTy &&C)

Definition:STLExtras.h:420

llvm::None

@ None

Definition:CodeGenData.h:106

llvm::dbgs

raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

Definition:Debug.cpp:163

llvm::VarID

std::tuple< const DIScope *, const DIScope *, const DILocalVariable * > VarID

A unique key that represents a debug variable.

Definition:DroppedVariableStats.h:30

llvm::isFunctionInPrintList

bool isFunctionInPrintList(StringRef FunctionName)

Definition:PrintPasses.cpp:160

llvm::VariableID

VariableID

Type wrapper for integer ID for Variables. 0 is reserved.

Definition:AssignmentTrackingAnalysis.h:26

llvm::errs

raw_fd_ostream & errs()

This returns a reference to a raw_ostream for standard error.

Definition:raw_ostream.cpp:907

llvm::divideCeil

constexpr T divideCeil(U Numerator, V Denominator)

Returns the integer ceil(Numerator / Denominator).

Definition:MathExtras.h:404

llvm::isAssignmentTrackingEnabled

bool isAssignmentTrackingEnabled(const Module &M)

Return true if assignment tracking is enabled for module M.

Definition:DebugInfo.cpp:2299

llvm::HighlightColor::String

@ String

llvm::predecessors

auto predecessors(const MachineBasicBlock *BB)

Definition:MachineBasicBlock.h:1377

llvm::toString

const char * toString(DWARFSectionKind Kind)

Definition:DWARFUnitIndex.h:67

llvm::filterDbgVars

static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)

Filter the DbgRecord range to DbgVariableRecord types only and downcast.

Definition:DebugProgramInstruction.h:555

llvm::debuginfoShouldUseDebugInstrRef

bool debuginfoShouldUseDebugInstrRef(const Triple &T)

Definition:LiveDebugValues.cpp:123

std

Implement std::hash so that hash_code can be used in STL containers.

Definition:BitVector.h:858

raw_ostream.h

Status

Definition:SIModeRegister.cpp:29

llvm::AnalysisKey

A special type used by analysis passes to provide an address that identifies that particular analysis...

Definition:Analysis.h:28

llvm::DbgVariableFragmentInfo

Definition:DbgVariableFragmentInfo.h:18

llvm::DbgVariableFragmentInfo::startInBits

uint64_t startInBits() const

Return the index of the first bit of the fragment.

Definition:DbgVariableFragmentInfo.h:25

llvm::DbgVariableFragmentInfo::endInBits

uint64_t endInBits() const

Return the index of the bit after the end of the fragment, e.g.

Definition:DbgVariableFragmentInfo.h:28

llvm::DenseMapInfo< VariableID >::getTombstoneKey

static VariableID getTombstoneKey()

Definition:AssignmentTrackingAnalysis.cpp:74

llvm::DenseMapInfo< VariableID >::isEqual

static bool isEqual(const VariableID &LHS, const VariableID &RHS)

Definition:AssignmentTrackingAnalysis.cpp:80

llvm::DenseMapInfo< VariableID >::getHashValue

static unsigned getHashValue(const VariableID &Val)

Definition:AssignmentTrackingAnalysis.cpp:77

llvm::DenseMapInfo< VariableID >::getEmptyKey

static VariableID getEmptyKey()

Definition:AssignmentTrackingAnalysis.cpp:71

llvm::DenseMapInfo< unsigned >

Definition:DenseMapInfo.h:126

llvm::DenseMapInfo

An information struct used to provide DenseMap with the various necessary components for a given valu...

Definition:DenseMapInfo.h:52

llvm::IntervalMapHalfOpenInfo

Definition:IntervalMap.h:167

llvm::IntervalMapImpl::NodeSizer

Definition:IntervalMap.h:439

llvm::VarLocInfo

Variable location definition used by FunctionVarLocs.

Definition:AssignmentTrackingAnalysis.h:28

llvm::VarLocInfo::Expr

DIExpression * Expr

Definition:AssignmentTrackingAnalysis.h:30

llvm::VarLocInfo::Values

RawLocationWrapper Values

Definition:AssignmentTrackingAnalysis.h:32

llvm::VarLocInfo::DL

DebugLoc DL

Definition:AssignmentTrackingAnalysis.h:31

llvm::VarLocInfo::VariableID

llvm::VariableID VariableID

Definition:AssignmentTrackingAnalysis.h:29

llvm::cl::desc

Definition:CommandLine.h:409

std::hash< VarLocInsertPt >::operator()

result_type operator()(const argument_type &Arg) const

Definition:AssignmentTrackingAnalysis.cpp:92

std::hash< VarLocInsertPt >::result_type

std::size_t result_type

Definition:AssignmentTrackingAnalysis.cpp:90