1//===- DebugSSAUpdater.cpp - Debug Variable SSA Update Tool ---------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the DebugSSAUpdater class.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Transforms/Utils/DebugSSAUpdater.h"
14#include "llvm/IR/CFG.h"
15#include "llvm/IR/DebugInfo.h"
16#include "llvm/IR/DebugInfoMetadata.h"
17#include "llvm/Transforms/Utils/SSAUpdaterImpl.h"
18
19using namespace llvm;
20
21#define DEBUG_TYPE "debug-ssa-updater"
22
23void DbgValueDef::print(raw_ostream &OS) const {
24 OS << "DbgVal{ ";
25 if (IsUndef) {
26 OS << "undef }";
27 return;
28 }
29 if (Phi) {
30 OS << *Phi << "}";
31 return;
32 }
33 OS << (IsMemory ? "Mem: " : "Def: ") << *Locations << " - " << *Expression
34 << " }";
35}
36
37void DbgSSAPhi::print(raw_ostream &OS) const {
38 OS << "DbgPhi ";
39 for (auto &[BB, DV] : IncomingValues)
40 OS << "[" << BB->BB.getName() << ", " << DV << "] ";
41}
42
43using AvailableValsTy = DenseMap<DbgSSABlock *, DbgValueDef>;
44
45DebugSSAUpdater::DebugSSAUpdater(SmallVectorImpl<DbgSSAPhi *> *NewPHI)
46 : InsertedPHIs(NewPHI) {}
47
48void DebugSSAUpdater::initialize() { AV.clear(); }
49
50bool DebugSSAUpdater::hasValueForBlock(DbgSSABlock *BB) const {
51 return AV.count(Val: BB);
52}
53
54DbgValueDef DebugSSAUpdater::findValueForBlock(DbgSSABlock *BB) const {
55 return AV.lookup(Val: BB);
56}
57
58void DebugSSAUpdater::addAvailableValue(DbgSSABlock *BB, DbgValueDef DV) {
59 AV[BB] = DV;
60}
61
62DbgValueDef DebugSSAUpdater::getValueAtEndOfBlock(DbgSSABlock *BB) {
63 DbgValueDef Res = getValueAtEndOfBlockInternal(BB);
64 return Res;
65}
66
67DbgValueDef DebugSSAUpdater::getValueInMiddleOfBlock(DbgSSABlock *BB) {
68 // If there is no definition of the renamed variable in this block, just use
69 // 'getValueAtEndOfBlock' to do our work.
70 if (!hasValueForBlock(BB))
71 return getValueAtEndOfBlock(BB);
72
73 // Otherwise, we have the hard case. Get the live-in values for each
74 // predecessor.
75 SmallVector<std::pair<DbgSSABlock *, DbgValueDef>, 8> PredValues;
76 DbgValueDef SingularValue;
77
78 bool IsFirstPred = true;
79 for (DbgSSABlock *PredBB : BB->predecessors()) {
80 DbgValueDef PredVal = getValueAtEndOfBlock(BB: PredBB);
81 PredValues.push_back(Elt: std::make_pair(x&: PredBB, y&: PredVal));
82
83 // Compute SingularValue.
84 if (IsFirstPred) {
85 SingularValue = PredVal;
86 IsFirstPred = false;
87 } else if (!PredVal.agreesWith(Other: SingularValue))
88 SingularValue = DbgValueDef();
89 }
90
91 // If there are no predecessors, just return undef.
92 if (PredValues.empty())
93 return DbgValueDef();
94
95 // Otherwise, if all the merged values are the same, just use it.
96 if (!SingularValue.IsUndef)
97 return SingularValue;
98
99 // Ok, we have no way out, insert a new one now.
100 DbgSSAPhi *InsertedPHI = BB->newPHI();
101
102 // Fill in all the predecessors of the PHI.
103 for (const auto &PredValue : PredValues)
104 InsertedPHI->addIncoming(BB: PredValue.first, DV: PredValue.second);
105
106 // See if the PHI node can be merged to a single value. This can happen in
107 // loop cases when we get a PHI of itself and one other value.
108
109 // If the client wants to know about all new instructions, tell it.
110 if (InsertedPHIs)
111 InsertedPHIs->push_back(Elt: InsertedPHI);
112
113 LLVM_DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n");
114 return InsertedPHI;
115}
116
117DbgSSABlock *DbgSSABlockSuccIterator::operator*() {
118 return Updater.getDbgSSABlock(BB: *SuccIt);
119}
120DbgSSABlock *DbgSSABlockPredIterator::operator*() {
121 return Updater.getDbgSSABlock(BB: *PredIt);
122}
123
124namespace llvm {
125
126template <> class SSAUpdaterTraits<DebugSSAUpdater> {
127public:
128 using BlkT = DbgSSABlock;
129 using ValT = DbgValueDef;
130 using PhiT = DbgSSAPhi;
131 using BlkSucc_iterator = DbgSSABlockSuccIterator;
132
133 static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); }
134 static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); }
135
136 class PHI_iterator {
137 private:
138 DbgSSAPhi *PHI;
139 unsigned Idx;
140
141 public:
142 explicit PHI_iterator(DbgSSAPhi *P) // begin iterator
143 : PHI(P), Idx(0) {}
144 PHI_iterator(DbgSSAPhi *P, bool) // end iterator
145 : PHI(P), Idx(PHI->getNumIncomingValues()) {}
146
147 PHI_iterator &operator++() {
148 ++Idx;
149 return *this;
150 }
151 bool operator==(const PHI_iterator &X) const { return Idx == X.Idx; }
152 bool operator!=(const PHI_iterator &X) const { return !operator==(X); }
153
154 DbgValueDef getIncomingValue() { return PHI->getIncomingValue(Idx); }
155 DbgSSABlock *getIncomingBlock() { return PHI->getIncomingBlock(Idx); }
156 };
157
158 static PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }
159 static PHI_iterator PHI_end(PhiT *PHI) { return PHI_iterator(PHI, true); }
160
161 /// FindPredecessorBlocks - Put the predecessors of BB into the Preds
162 /// vector.
163 static void FindPredecessorBlocks(DbgSSABlock *BB,
164 SmallVectorImpl<DbgSSABlock *> *Preds) {
165 for (auto PredIt = BB->pred_begin(); PredIt != BB->pred_end(); ++PredIt)
166 Preds->push_back(Elt: *PredIt);
167 }
168
169 /// GetPoisonVal - Get an undefined value of the same type as the value
170 /// being handled.
171 static DbgValueDef GetPoisonVal(DbgSSABlock *BB, DebugSSAUpdater *Updater) {
172 return DbgValueDef();
173 }
174
175 /// CreateEmptyPHI - Create a new debug PHI entry for the specified block.
176 static DbgSSAPhi *CreateEmptyPHI(DbgSSABlock *BB, unsigned NumPreds,
177 DebugSSAUpdater *Updater) {
178 DbgSSAPhi *PHI = BB->newPHI();
179 return PHI;
180 }
181
182 /// AddPHIOperand - Add the specified value as an operand of the PHI for
183 /// the specified predecessor block.
184 static void AddPHIOperand(DbgSSAPhi *PHI, DbgValueDef Val,
185 DbgSSABlock *Pred) {
186 PHI->addIncoming(BB: Pred, DV: Val);
187 }
188
189 /// ValueIsPHI - Check if a value is a PHI.
190 static DbgSSAPhi *ValueIsPHI(DbgValueDef Val, DebugSSAUpdater *Updater) {
191 return Val.Phi;
192 }
193
194 /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
195 /// operands, i.e., it was just added.
196 static DbgSSAPhi *ValueIsNewPHI(DbgValueDef Val, DebugSSAUpdater *Updater) {
197 DbgSSAPhi *PHI = ValueIsPHI(Val, Updater);
198 if (PHI && PHI->getNumIncomingValues() == 0)
199 return PHI;
200 return nullptr;
201 }
202
203 /// GetPHIValue - For the specified PHI instruction, return the value
204 /// that it defines.
205 static DbgValueDef GetPHIValue(DbgSSAPhi *PHI) { return PHI; }
206};
207
208} // end namespace llvm
209
210/// Check to see if AvailableVals has an entry for the specified BB and if so,
211/// return it. If not, construct SSA form by first calculating the required
212/// placement of PHIs and then inserting new PHIs where needed.
213DbgValueDef DebugSSAUpdater::getValueAtEndOfBlockInternal(DbgSSABlock *BB) {
214 if (AV.contains(Val: BB))
215 return AV[BB];
216
217 SSAUpdaterImpl<DebugSSAUpdater> Impl(this, &AV, InsertedPHIs);
218 return Impl.GetValue(BB);
219}
220
221bool isContained(DIScope *Inner, DIScope *Outer) {
222 if (Inner == Outer)
223 return true;
224 if (!Inner->getScope())
225 return false;
226 return isContained(Inner: Inner->getScope(), Outer);
227}
228
229void DbgValueRangeTable::addVariable(Function *F, DebugVariableAggregate DVA) {
230 const DILocalVariable *Var = DVA.getVariable();
231 const DILocation *InlinedAt = DVA.getInlinedAt();
232
233 DenseMap<BasicBlock *, SmallVector<DbgVariableRecord *>> BlockDbgRecordValues;
234 DenseSet<BasicBlock *> HasAnyInstructionsInScope;
235 int NumRecordsFound = 0;
236 DbgVariableRecord *LastRecordFound = nullptr;
237 bool DeclareRecordFound = false;
238
239 LLVM_DEBUG(dbgs() << "Finding variable info for " << *Var << " at "
240 << InlinedAt << "\n");
241
242 for (auto &BB : *F) {
243 auto &DbgRecordValues = BlockDbgRecordValues[&BB];
244 bool FoundInstructionInScope = false;
245 for (auto &I : BB) {
246 LLVM_DEBUG(dbgs() << "Instruction: '" << I << "'\n");
247
248 for (DbgVariableRecord &DVR : filterDbgVars(R: I.getDbgRecordRange())) {
249 if (DVR.getVariable() == Var &&
250 DVR.getDebugLoc().getInlinedAt() == InlinedAt) {
251 assert(!DVR.isDbgAssign() && "No support for #dbg_assign yet.");
252 if (DVR.isDbgDeclare())
253 DeclareRecordFound = true;
254 ++NumRecordsFound;
255 LastRecordFound = &DVR;
256 DbgRecordValues.push_back(Elt: &DVR);
257 }
258 }
259 if (!FoundInstructionInScope && I.getDebugLoc()) {
260 if (I.getDebugLoc().getInlinedAt() == InlinedAt &&
261 isContained(Inner: cast<DILocalScope>(Val: I.getDebugLoc().getScope()),
262 Outer: Var->getScope())) {
263 FoundInstructionInScope = true;
264 HasAnyInstructionsInScope.insert(V: &BB);
265 }
266 }
267 }
268 LLVM_DEBUG(dbgs() << "DbgRecordValues found in '" << BB.getName() << "':\n";
269 for_each(DbgRecordValues, [](auto *DV) { DV->dump(); }));
270 }
271
272 if (!NumRecordsFound) {
273 LLVM_DEBUG(dbgs() << "No dbg_records found for variable!\n");
274 return;
275 }
276
277 // Now that we have all the DbgValues, we can start defining available values
278 // for each block. The end goal is to have, for every block with any
279 // instructions in scope, a LiveIn value.
280 // Currently we anticipate that either a variable has a set of #dbg_values, in
281 // which case we need a complete SSA liveness analysis to determine live-in
282 // values per-block, or a variable has a single #dbg_declare.
283 if (DeclareRecordFound) {
284 // Rust generates multiple #dbg_declare's.
285 // %self.dbg.spill = alloca [8 x i8], align 8
286 // store ptr %self, ptr %self.dbg.spill, align 8
287 // #dbg_declare(ptr %self.dbg.spill, !892, !DIExpression(), !894)
288 // #dbg_declare(ptr %self.dbg.spill, !895, !DIExpression(), !905)
289 if (NumRecordsFound != 1) {
290 LLVM_DEBUG(dbgs() << "Multiple records for a #dbg_declare!\n");
291 return;
292 }
293 // FIXME: This should be changed for fragments!
294 LLVM_DEBUG(dbgs() << "Single location found for variable!\n");
295 OrigSingleLocVariableValueTable[DVA] = DbgValueDef(LastRecordFound);
296 return;
297 }
298
299 // We don't have a single location for the variable's entire scope, so instead
300 // we must now perform a liveness analysis to create a location list.
301 SmallVector<DbgSSAPhi *> HypotheticalPHIs;
302 DebugSSAUpdater SSAUpdater(&HypotheticalPHIs);
303 SSAUpdater.initialize();
304 for (auto &[BB, DVs] : BlockDbgRecordValues) {
305 auto *DbgBB = SSAUpdater.getDbgSSABlock(BB);
306 if (DVs.empty())
307 continue;
308 auto *LastValueInBlock = DVs.back();
309 LLVM_DEBUG(dbgs() << "Last value in " << BB->getName() << ": "
310 << *LastValueInBlock << "\n");
311 SSAUpdater.addAvailableValue(BB: DbgBB, DV: DbgValueDef(LastValueInBlock));
312 }
313
314 for (BasicBlock &BB : *F) {
315 if (!HasAnyInstructionsInScope.contains(V: &BB)) {
316 LLVM_DEBUG(dbgs() << "Skipping finding debug ranges for '" << BB.getName()
317 << "' due to no in-scope instructions.\n");
318 continue;
319 }
320 LLVM_DEBUG(dbgs() << "Finding live-in value for '" << BB.getName()
321 << "'...\n");
322 DbgValueDef LiveValue =
323 SSAUpdater.getValueInMiddleOfBlock(BB: SSAUpdater.getDbgSSABlock(BB: &BB));
324 LLVM_DEBUG(dbgs() << "Found live-in: " << LiveValue << "\n");
325 auto HasValidValue = [](DbgValueDef DV) {
326 return !DV.IsUndef && DV.Phi == nullptr;
327 };
328
329 SmallVector<DbgRangeEntry> BlockDbgRanges;
330 BasicBlock::iterator LastIt = BB.begin();
331 for (auto *DVR : BlockDbgRecordValues[&BB]) {
332 // Create a range that ends as of DVR.
333 BasicBlock::iterator DVRStartIt =
334 const_cast<Instruction *>(DVR->getInstruction())->getIterator();
335 if (HasValidValue(LiveValue))
336 BlockDbgRanges.push_back(Elt: {.Start: LastIt, .End: DVRStartIt, .Value: LiveValue});
337 LiveValue = DbgValueDef(DVR);
338 LastIt = DVRStartIt;
339 }
340
341 // After considering all in-block debug values, if any, create a range
342 // covering the remainder of the block.
343 if (HasValidValue(LiveValue))
344 BlockDbgRanges.push_back(Elt: {.Start: LastIt, .End: BB.end(), .Value: LiveValue});
345 LLVM_DEBUG(dbgs() << "Create set of ranges with " << BlockDbgRanges.size()
346 << " entries!\n");
347 if (!BlockDbgRanges.empty())
348 OrigVariableValueRangeTable[DVA].append(RHS: BlockDbgRanges);
349 }
350}
351
352void DbgValueRangeTable::printValues(DebugVariableAggregate DVA,
353 raw_ostream &OS) {
354 OS << "Variable Table for '" << DVA.getVariable()->getName() << "' (at "
355 << DVA.getInlinedAt() << "):\n";
356 if (!hasVariableEntry(DVA)) {
357 OS << " Empty!\n";
358 return;
359 }
360 if (hasSingleLocEntry(DVA)) {
361 OS << " SingleLoc: " << OrigSingleLocVariableValueTable[DVA] << "\n";
362 return;
363 }
364 OS << " LocRange:\n";
365 for (DbgRangeEntry RangeEntry : OrigVariableValueRangeTable[DVA]) {
366 OS << " (";
367 if (RangeEntry.Start == RangeEntry.Start->getParent()->begin() &&
368 RangeEntry.End == RangeEntry.Start->getParent()->end()) {
369 OS << RangeEntry.Start->getParent()->getName();
370 } else {
371 OS << RangeEntry.Start->getParent()->getName() << ": "
372 << *RangeEntry.Start << ", ";
373 if (RangeEntry.End == RangeEntry.Start->getParent()->end())
374 OS << "..";
375 else
376 OS << *RangeEntry.End;
377 }
378 OS << ") [" << RangeEntry.Value << "]\n";
379 }
380}
381
382SSAValueNameMap::ValueID SSAValueNameMap::addValue(Value *V) {
383 auto ExistingID = ValueToIDMap.find(Val: V);
384 if (ExistingID != ValueToIDMap.end())
385 return ExistingID->second;
386 // First, get a new ID and Map V to it.
387 ValueID NewID = NextID++;
388 ValueToIDMap.insert(KV: {V, NewID});
389 // Then, get the name string for V and map NewID to it.
390 assert(!ValueIDToNameMap.contains(NewID) &&
391 "New value ID already maps to a name?");
392 std::string &ValueText = ValueIDToNameMap[NewID];
393 raw_string_ostream Stream(ValueText);
394 V->printAsOperand(O&: Stream, PrintType: true);
395 return NewID;
396}
397