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 // FIXME: This should be changed for fragments!
285 LLVM_DEBUG(dbgs() << "Single location found for variable!\n");
286 assert(NumRecordsFound == 1 &&
287 "Found multiple records for a #dbg_declare variable!");
288 OrigSingleLocVariableValueTable[DVA] = DbgValueDef(LastRecordFound);
289 return;
290 }
291
292 // We don't have a single location for the variable's entire scope, so instead
293 // we must now perform a liveness analysis to create a location list.
294 SmallVector<DbgSSAPhi *> HypotheticalPHIs;
295 DebugSSAUpdater SSAUpdater(&HypotheticalPHIs);
296 SSAUpdater.initialize();
297 for (auto &[BB, DVs] : BlockDbgRecordValues) {
298 auto *DbgBB = SSAUpdater.getDbgSSABlock(BB);
299 if (DVs.empty())
300 continue;
301 auto *LastValueInBlock = DVs.back();
302 LLVM_DEBUG(dbgs() << "Last value in " << BB->getName() << ": "
303 << *LastValueInBlock << "\n");
304 SSAUpdater.addAvailableValue(BB: DbgBB, DV: DbgValueDef(LastValueInBlock));
305 }
306
307 for (BasicBlock &BB : *F) {
308 if (!HasAnyInstructionsInScope.contains(V: &BB)) {
309 LLVM_DEBUG(dbgs() << "Skipping finding debug ranges for '" << BB.getName()
310 << "' due to no in-scope instructions.\n");
311 continue;
312 }
313 LLVM_DEBUG(dbgs() << "Finding live-in value for '" << BB.getName()
314 << "'...\n");
315 DbgValueDef LiveValue =
316 SSAUpdater.getValueInMiddleOfBlock(BB: SSAUpdater.getDbgSSABlock(BB: &BB));
317 LLVM_DEBUG(dbgs() << "Found live-in: " << LiveValue << "\n");
318 auto HasValidValue = [](DbgValueDef DV) {
319 return !DV.IsUndef && DV.Phi == nullptr;
320 };
321
322 SmallVector<DbgRangeEntry> BlockDbgRanges;
323 BasicBlock::iterator LastIt = BB.begin();
324 for (auto *DVR : BlockDbgRecordValues[&BB]) {
325 // Create a range that ends as of DVR.
326 BasicBlock::iterator DVRStartIt =
327 const_cast<Instruction *>(DVR->getInstruction())->getIterator();
328 if (HasValidValue(LiveValue))
329 BlockDbgRanges.push_back(Elt: {.Start: LastIt, .End: DVRStartIt, .Value: LiveValue});
330 LiveValue = DbgValueDef(DVR);
331 LastIt = DVRStartIt;
332 }
333
334 // After considering all in-block debug values, if any, create a range
335 // covering the remainder of the block.
336 if (HasValidValue(LiveValue))
337 BlockDbgRanges.push_back(Elt: {.Start: LastIt, .End: BB.end(), .Value: LiveValue});
338 LLVM_DEBUG(dbgs() << "Create set of ranges with " << BlockDbgRanges.size()
339 << " entries!\n");
340 if (!BlockDbgRanges.empty())
341 OrigVariableValueRangeTable[DVA].append(RHS: BlockDbgRanges);
342 }
343}
344
345void DbgValueRangeTable::printValues(DebugVariableAggregate DVA,
346 raw_ostream &OS) {
347 OS << "Variable Table for '" << DVA.getVariable()->getName() << "' (at "
348 << DVA.getInlinedAt() << "):\n";
349 if (!hasVariableEntry(DVA)) {
350 OS << " Empty!\n";
351 return;
352 }
353 if (hasSingleLocEntry(DVA)) {
354 OS << " SingleLoc: " << OrigSingleLocVariableValueTable[DVA] << "\n";
355 return;
356 }
357 OS << " LocRange:\n";
358 for (DbgRangeEntry RangeEntry : OrigVariableValueRangeTable[DVA]) {
359 OS << " (";
360 if (RangeEntry.Start == RangeEntry.Start->getParent()->begin() &&
361 RangeEntry.End == RangeEntry.Start->getParent()->end()) {
362 OS << RangeEntry.Start->getParent()->getName();
363 } else {
364 OS << RangeEntry.Start->getParent()->getName() << ": "
365 << *RangeEntry.Start << ", ";
366 if (RangeEntry.End == RangeEntry.Start->getParent()->end())
367 OS << "..";
368 else
369 OS << *RangeEntry.End;
370 }
371 OS << ") [" << RangeEntry.Value << "]\n";
372 }
373}
374
375SSAValueNameMap::ValueID SSAValueNameMap::addValue(Value *V) {
376 auto ExistingID = ValueToIDMap.find(Val: V);
377 if (ExistingID != ValueToIDMap.end())
378 return ExistingID->second;
379 // First, get a new ID and Map V to it.
380 ValueID NewID = NextID++;
381 ValueToIDMap.insert(KV: {V, NewID});
382 // Then, get the name string for V and map NewID to it.
383 assert(!ValueIDToNameMap.contains(NewID) &&
384 "New value ID already maps to a name?");
385 std::string &ValueText = ValueIDToNameMap[NewID];
386 raw_string_ostream Stream(ValueText);
387 V->printAsOperand(O&: Stream, PrintType: true);
388 return NewID;
389}
390