390 lines · cpp
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-exception6//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 << " - " << *Expression34 << " }";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(BB);52}53 54DbgValueDef DebugSSAUpdater::findValueForBlock(DbgSSABlock *BB) const {55 return AV.lookup(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 use69 // '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 each74 // 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(PredBB);81 PredValues.push_back(std::make_pair(PredBB, PredVal));82 83 // Compute SingularValue.84 if (IsFirstPred) {85 SingularValue = PredVal;86 IsFirstPred = false;87 } else if (!PredVal.agreesWith(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(PredValue.first, PredValue.second);105 106 // See if the PHI node can be merged to a single value. This can happen in107 // 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(InsertedPHI);112 113 LLVM_DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n");114 return InsertedPHI;115}116 117DbgSSABlock *DbgSSABlockSuccIterator::operator*() {118 return Updater.getDbgSSABlock(*SuccIt);119}120DbgSSABlock *DbgSSABlockPredIterator::operator*() {121 return Updater.getDbgSSABlock(*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 iterator143 : PHI(P), Idx(0) {}144 PHI_iterator(DbgSSAPhi *P, bool) // end iterator145 : 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 Preds162 /// 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(*PredIt);167 }168 169 /// GetPoisonVal - Get an undefined value of the same type as the value170 /// 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 for183 /// the specified predecessor block.184 static void AddPHIOperand(DbgSSAPhi *PHI, DbgValueDef Val,185 DbgSSABlock *Pred) {186 PHI->addIncoming(Pred, 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 source195 /// 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 value204 /// that it defines.205 static DbgValueDef GetPHIValue(DbgSSAPhi *PHI) { return PHI; }206};207 208} // end namespace llvm209 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 required212/// placement of PHIs and then inserting new PHIs where needed.213DbgValueDef DebugSSAUpdater::getValueAtEndOfBlockInternal(DbgSSABlock *BB) {214 if (AV.contains(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->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(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(&DVR);257 }258 }259 if (!FoundInstructionInScope && I.getDebugLoc()) {260 if (I.getDebugLoc().getInlinedAt() == InlinedAt &&261 isContained(cast<DILocalScope>(I.getDebugLoc().getScope()),262 Var->getScope())) {263 FoundInstructionInScope = true;264 HasAnyInstructionsInScope.insert(&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 values278 // for each block. The end goal is to have, for every block with any279 // instructions in scope, a LiveIn value.280 // Currently we anticipate that either a variable has a set of #dbg_values, in281 // which case we need a complete SSA liveness analysis to determine live-in282 // 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 instead293 // 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(DbgBB, DbgValueDef(LastValueInBlock));305 }306 307 for (BasicBlock &BB : *F) {308 if (!HasAnyInstructionsInScope.contains(&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(SSAUpdater.getDbgSSABlock(&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({LastIt, DVRStartIt, LiveValue});330 LiveValue = DbgValueDef(DVR);331 LastIt = DVRStartIt;332 }333 334 // After considering all in-block debug values, if any, create a range335 // covering the remainder of the block.336 if (HasValidValue(LiveValue))337 BlockDbgRanges.push_back({LastIt, BB.end(), LiveValue});338 LLVM_DEBUG(dbgs() << "Create set of ranges with " << BlockDbgRanges.size()339 << " entries!\n");340 if (!BlockDbgRanges.empty())341 OrigVariableValueRangeTable[DVA].append(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 else369 OS << *RangeEntry.End;370 }371 OS << ") [" << RangeEntry.Value << "]\n";372 }373}374 375SSAValueNameMap::ValueID SSAValueNameMap::addValue(Value *V) {376 auto ExistingID = ValueToIDMap.find(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({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(Stream, true);388 return NewID;389}390