362 lines · cpp
1//===- LexicalScopes.cpp - Collecting lexical scope info ------------------===//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 LexicalScopes analysis.10//11// This pass collects lexical scope information and maps machine instructions12// to respective lexical scopes.13//14//===----------------------------------------------------------------------===//15 16#include "llvm/CodeGen/LexicalScopes.h"17#include "llvm/ADT/DenseMap.h"18#include "llvm/ADT/SmallVector.h"19#include "llvm/CodeGen/MachineBasicBlock.h"20#include "llvm/CodeGen/MachineFunction.h"21#include "llvm/CodeGen/MachineInstr.h"22#include "llvm/Config/llvm-config.h"23#include "llvm/IR/DebugInfoMetadata.h"24#include "llvm/IR/Function.h"25#include "llvm/IR/Metadata.h"26#include "llvm/IR/Module.h"27#include "llvm/Support/Casting.h"28#include "llvm/Support/Compiler.h"29#include "llvm/Support/Debug.h"30#include "llvm/Support/raw_ostream.h"31#include <cassert>32#include <string>33#include <tuple>34#include <utility>35 36using namespace llvm;37 38#define DEBUG_TYPE "lexicalscopes"39 40static bool skipUnit(const DICompileUnit *CU) {41 return CU->getEmissionKind() == DICompileUnit::NoDebug;42}43 44void LexicalScopes::resetModule() {45 FunctionMap.clear();46 resetFunction();47}48 49void LexicalScopes::resetFunction() {50 MF = nullptr;51 CurrentFnLexicalScope = nullptr;52 LexicalScopeMap.clear();53 AbstractScopeMap.clear();54 InlinedLexicalScopeMap.clear();55 AbstractScopesList.clear();56 DominatedBlocks.clear();57}58 59void LexicalScopes::initialize(const Module &M) {60 resetModule();61 for (const Function &F : M) {62 DISubprogram *SP = F.getSubprogram();63 if (SP && (!SP->getUnit() || !skipUnit(SP->getUnit())))64 FunctionMap[SP] = &F;65 }66}67 68void LexicalScopes::scanFunction(const MachineFunction &Fn) {69 resetFunction();70 // Don't attempt any lexical scope creation for a NoDebug compile unit.71 if (skipUnit(Fn.getFunction().getSubprogram()->getUnit()))72 return;73 MF = &Fn;74 SmallVector<InsnRange, 4> MIRanges;75 DenseMap<const MachineInstr *, LexicalScope *> MI2ScopeMap;76 extractLexicalScopes(MIRanges, MI2ScopeMap);77 if (CurrentFnLexicalScope) {78 constructScopeNest(CurrentFnLexicalScope);79 assignInstructionRanges(MIRanges, MI2ScopeMap);80 }81}82 83/// extractLexicalScopes - Extract instruction ranges for each lexical scopes84/// for the given machine function.85void LexicalScopes::extractLexicalScopes(86 SmallVectorImpl<InsnRange> &MIRanges,87 DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {88 // Scan each instruction and create scopes. First build working set of scopes.89 for (const auto &MBB : *MF) {90 const MachineInstr *RangeBeginMI = nullptr;91 const MachineInstr *PrevMI = nullptr;92 const DILocation *PrevDL = nullptr;93 for (const auto &MInsn : MBB) {94 // Ignore DBG_VALUE and similar instruction that do not contribute to any95 // instruction in the output.96 if (MInsn.isMetaInstruction())97 continue;98 99 // Check if instruction has valid location information.100 const DILocation *MIDL = MInsn.getDebugLoc();101 if (!MIDL) {102 PrevMI = &MInsn;103 continue;104 }105 106 // If scope has not changed then skip this instruction.107 if (MIDL == PrevDL) {108 PrevMI = &MInsn;109 continue;110 }111 112 if (RangeBeginMI) {113 // If we have already seen a beginning of an instruction range and114 // current instruction scope does not match scope of first instruction115 // in this range then create a new instruction range.116 InsnRange R(RangeBeginMI, PrevMI);117 MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);118 MIRanges.push_back(R);119 }120 121 // This is a beginning of a new instruction range.122 RangeBeginMI = &MInsn;123 124 // Reset previous markers.125 PrevMI = &MInsn;126 PrevDL = MIDL;127 }128 129 // Create last instruction range.130 if (RangeBeginMI && PrevMI && PrevDL) {131 InsnRange R(RangeBeginMI, PrevMI);132 MIRanges.push_back(R);133 MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);134 }135 }136}137 138/// findLexicalScope - Find lexical scope, either regular or inlined, for the139/// given DebugLoc. Return NULL if not found.140LexicalScope *LexicalScopes::findLexicalScope(const DILocation *DL) {141 DILocalScope *Scope = DL->getScope();142 if (!Scope)143 return nullptr;144 145 // The scope that we were created with could have an extra file - which146 // isn't what we care about in this case.147 Scope = Scope->getNonLexicalBlockFileScope();148 149 if (auto *IA = DL->getInlinedAt()) {150 auto I = InlinedLexicalScopeMap.find(std::make_pair(Scope, IA));151 return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr;152 }153 return findLexicalScope(Scope);154}155 156/// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If157/// not available then create new lexical scope.158LexicalScope *LexicalScopes::getOrCreateLexicalScope(const DILocalScope *Scope,159 const DILocation *IA) {160 if (IA) {161 // Skip scopes inlined from a NoDebug compile unit.162 if (skipUnit(Scope->getSubprogram()->getUnit()))163 return getOrCreateLexicalScope(IA);164 // Create an abstract scope for inlined function.165 getOrCreateAbstractScope(Scope);166 // Create an inlined scope for inlined function.167 return getOrCreateInlinedScope(Scope, IA);168 }169 170 return getOrCreateRegularScope(Scope);171}172 173/// getOrCreateRegularScope - Find or create a regular lexical scope.174LexicalScope *175LexicalScopes::getOrCreateRegularScope(const DILocalScope *Scope) {176 assert(Scope && "Invalid Scope encoding!");177 Scope = Scope->getNonLexicalBlockFileScope();178 179 auto I = LexicalScopeMap.find(Scope);180 if (I != LexicalScopeMap.end())181 return &I->second;182 183 // FIXME: Should the following dyn_cast be DILexicalBlock?184 LexicalScope *Parent = nullptr;185 if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))186 Parent = getOrCreateLexicalScope(Block->getScope());187 I = LexicalScopeMap.emplace(std::piecewise_construct,188 std::forward_as_tuple(Scope),189 std::forward_as_tuple(Parent, Scope, nullptr,190 false)).first;191 192 if (!Parent) {193 assert(cast<DISubprogram>(Scope)->describes(&MF->getFunction()));194 assert(!CurrentFnLexicalScope);195 CurrentFnLexicalScope = &I->second;196 }197 198 return &I->second;199}200 201/// getOrCreateInlinedScope - Find or create an inlined lexical scope.202LexicalScope *203LexicalScopes::getOrCreateInlinedScope(const DILocalScope *Scope,204 const DILocation *InlinedAt) {205 assert(Scope && "Invalid Scope encoding!");206 Scope = Scope->getNonLexicalBlockFileScope();207 std::pair<const DILocalScope *, const DILocation *> P(Scope, InlinedAt);208 auto I = InlinedLexicalScopeMap.find(P);209 if (I != InlinedLexicalScopeMap.end())210 return &I->second;211 212 LexicalScope *Parent;213 if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))214 Parent = getOrCreateInlinedScope(Block->getScope(), InlinedAt);215 else216 Parent = getOrCreateLexicalScope(InlinedAt);217 218 I = InlinedLexicalScopeMap219 .emplace(std::piecewise_construct, std::forward_as_tuple(P),220 std::forward_as_tuple(Parent, Scope, InlinedAt, false))221 .first;222 return &I->second;223}224 225/// getOrCreateAbstractScope - Find or create an abstract lexical scope.226LexicalScope *227LexicalScopes::getOrCreateAbstractScope(const DILocalScope *Scope) {228 assert(Scope && "Invalid Scope encoding!");229 Scope = Scope->getNonLexicalBlockFileScope();230 auto I = AbstractScopeMap.find(Scope);231 if (I != AbstractScopeMap.end())232 return &I->second;233 234 // FIXME: Should the following isa be DILexicalBlock?235 LexicalScope *Parent = nullptr;236 if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))237 Parent = getOrCreateAbstractScope(Block->getScope());238 239 I = AbstractScopeMap.emplace(std::piecewise_construct,240 std::forward_as_tuple(Scope),241 std::forward_as_tuple(Parent, Scope,242 nullptr, true)).first;243 if (isa<DISubprogram>(Scope))244 AbstractScopesList.push_back(&I->second);245 return &I->second;246}247 248/// constructScopeNest - Traverse the Scope tree depth-first, storing249/// traversal state in WorkStack and recording the depth-first250/// numbering (setDFSIn, setDFSOut) for edge classification.251void LexicalScopes::constructScopeNest(LexicalScope *Scope) {252 assert(Scope && "Unable to calculate scope dominance graph!");253 SmallVector<std::pair<LexicalScope *, size_t>, 4> WorkStack;254 WorkStack.push_back(std::make_pair(Scope, 0));255 unsigned Counter = 0;256 while (!WorkStack.empty()) {257 auto &ScopePosition = WorkStack.back();258 LexicalScope *WS = ScopePosition.first;259 size_t ChildNum = ScopePosition.second++;260 const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();261 if (ChildNum < Children.size()) {262 auto &ChildScope = Children[ChildNum];263 WorkStack.push_back(std::make_pair(ChildScope, 0));264 ChildScope->setDFSIn(++Counter);265 } else {266 WorkStack.pop_back();267 WS->setDFSOut(++Counter);268 }269 }270}271 272/// assignInstructionRanges - Find ranges of instructions covered by each273/// lexical scope.274void LexicalScopes::assignInstructionRanges(275 SmallVectorImpl<InsnRange> &MIRanges,276 DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {277 LexicalScope *PrevLexicalScope = nullptr;278 for (const auto &R : MIRanges) {279 LexicalScope *S = MI2ScopeMap.lookup(R.first);280 assert(S && "Lost LexicalScope for a machine instruction!");281 if (PrevLexicalScope && !PrevLexicalScope->dominates(S))282 PrevLexicalScope->closeInsnRange(S);283 S->openInsnRange(R.first);284 S->extendInsnRange(R.second);285 PrevLexicalScope = S;286 }287 288 if (PrevLexicalScope)289 PrevLexicalScope->closeInsnRange();290}291 292/// getMachineBasicBlocks - Populate given set using machine basic blocks which293/// have machine instructions that belong to lexical scope identified by294/// DebugLoc.295void LexicalScopes::getMachineBasicBlocks(296 const DILocation *DL, SmallPtrSetImpl<const MachineBasicBlock *> &MBBs) {297 assert(MF && "Method called on a uninitialized LexicalScopes object!");298 MBBs.clear();299 300 LexicalScope *Scope = getOrCreateLexicalScope(DL);301 if (!Scope)302 return;303 304 if (Scope == CurrentFnLexicalScope) {305 MBBs.insert_range(llvm::make_pointer_range(*MF));306 return;307 }308 309 // The scope ranges can cover multiple basic blocks in each span. Iterate over310 // all blocks (in the order they are in the function) until we reach the one311 // containing the end of the span.312 SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges();313 for (auto &R : InsnRanges)314 for (auto CurMBBIt = R.first->getParent()->getIterator(),315 EndBBIt = std::next(R.second->getParent()->getIterator());316 CurMBBIt != EndBBIt; CurMBBIt++)317 MBBs.insert(&*CurMBBIt);318}319 320bool LexicalScopes::dominates(const DILocation *DL, MachineBasicBlock *MBB) {321 assert(MF && "Unexpected uninitialized LexicalScopes object!");322 LexicalScope *Scope = getOrCreateLexicalScope(DL);323 if (!Scope)324 return false;325 326 // Current function scope covers all basic blocks in the function.327 if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF)328 return true;329 330 // Fetch all the blocks in DLs scope. Because the range / block list also331 // contain any subscopes, any instruction that DL dominates can be found in332 // the block set.333 //334 // Cache the set of fetched blocks to avoid repeatedly recomputing the set in335 // the LiveDebugValues pass.336 std::unique_ptr<BlockSetT> &Set = DominatedBlocks[DL];337 if (!Set) {338 Set = std::make_unique<BlockSetT>();339 getMachineBasicBlocks(DL, *Set);340 }341 return Set->contains(MBB);342}343 344#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)345LLVM_DUMP_METHOD void LexicalScope::dump(unsigned Indent) const {346 raw_ostream &err = dbgs();347 err.indent(Indent);348 err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n";349 const MDNode *N = Desc;350 err.indent(Indent);351 N->dump();352 if (AbstractScope)353 err << std::string(Indent, ' ') << "Abstract Scope\n";354 355 if (!Children.empty())356 err << std::string(Indent + 2, ' ') << "Children ...\n";357 for (const LexicalScope *Child : Children)358 if (Child != this)359 Child->dump(Indent + 2);360}361#endif362