1226584Sdim//===- LexicalScopes.cpp - Collecting lexical scope info ------------------===// 2226584Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6226584Sdim// 7226584Sdim//===----------------------------------------------------------------------===// 8226584Sdim// 9226584Sdim// This file implements LexicalScopes analysis. 10226584Sdim// 11226584Sdim// This pass collects lexical scope information and maps machine instructions 12226584Sdim// to respective lexical scopes. 13226584Sdim// 14226584Sdim//===----------------------------------------------------------------------===// 15226584Sdim 16226584Sdim#include "llvm/CodeGen/LexicalScopes.h" 17321369Sdim#include "llvm/ADT/DenseMap.h" 18321369Sdim#include "llvm/ADT/SmallVector.h" 19321369Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 20226584Sdim#include "llvm/CodeGen/MachineFunction.h" 21226584Sdim#include "llvm/CodeGen/MachineInstr.h" 22341825Sdim#include "llvm/Config/llvm-config.h" 23321369Sdim#include "llvm/IR/DebugInfoMetadata.h" 24360784Sdim#include "llvm/IR/Function.h" 25321369Sdim#include "llvm/IR/Metadata.h" 26321369Sdim#include "llvm/Support/Casting.h" 27321369Sdim#include "llvm/Support/Compiler.h" 28226584Sdim#include "llvm/Support/Debug.h" 29321369Sdim#include "llvm/Support/raw_ostream.h" 30321369Sdim#include <cassert> 31321369Sdim#include <string> 32321369Sdim#include <tuple> 33321369Sdim#include <utility> 34321369Sdim 35226584Sdimusing namespace llvm; 36226584Sdim 37276479Sdim#define DEBUG_TYPE "lexicalscopes" 38226584Sdim 39276479Sdim/// reset - Reset the instance so that it's prepared for another function. 40276479Sdimvoid LexicalScopes::reset() { 41276479Sdim MF = nullptr; 42276479Sdim CurrentFnLexicalScope = nullptr; 43276479Sdim LexicalScopeMap.clear(); 44276479Sdim AbstractScopeMap.clear(); 45226584Sdim InlinedLexicalScopeMap.clear(); 46226584Sdim AbstractScopesList.clear(); 47226584Sdim} 48226584Sdim 49226584Sdim/// initialize - Scan machine function and constuct lexical scope nest. 50226584Sdimvoid LexicalScopes::initialize(const MachineFunction &Fn) { 51327952Sdim reset(); 52321369Sdim // Don't attempt any lexical scope creation for a NoDebug compile unit. 53327952Sdim if (Fn.getFunction().getSubprogram()->getUnit()->getEmissionKind() == 54321369Sdim DICompileUnit::NoDebug) 55321369Sdim return; 56226584Sdim MF = &Fn; 57226584Sdim SmallVector<InsnRange, 4> MIRanges; 58226584Sdim DenseMap<const MachineInstr *, LexicalScope *> MI2ScopeMap; 59226584Sdim extractLexicalScopes(MIRanges, MI2ScopeMap); 60226584Sdim if (CurrentFnLexicalScope) { 61226584Sdim constructScopeNest(CurrentFnLexicalScope); 62226584Sdim assignInstructionRanges(MIRanges, MI2ScopeMap); 63226584Sdim } 64226584Sdim} 65226584Sdim 66226584Sdim/// extractLexicalScopes - Extract instruction ranges for each lexical scopes 67226584Sdim/// for the given machine function. 68276479Sdimvoid LexicalScopes::extractLexicalScopes( 69276479Sdim SmallVectorImpl<InsnRange> &MIRanges, 70276479Sdim DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) { 71226584Sdim // Scan each instruction and create scopes. First build working set of scopes. 72276479Sdim for (const auto &MBB : *MF) { 73276479Sdim const MachineInstr *RangeBeginMI = nullptr; 74276479Sdim const MachineInstr *PrevMI = nullptr; 75288943Sdim const DILocation *PrevDL = nullptr; 76276479Sdim for (const auto &MInsn : MBB) { 77226584Sdim // Check if instruction has valid location information. 78288943Sdim const DILocation *MIDL = MInsn.getDebugLoc(); 79288943Sdim if (!MIDL) { 80276479Sdim PrevMI = &MInsn; 81226584Sdim continue; 82226584Sdim } 83226584Sdim 84226584Sdim // If scope has not changed then skip this instruction. 85226584Sdim if (MIDL == PrevDL) { 86276479Sdim PrevMI = &MInsn; 87226584Sdim continue; 88226584Sdim } 89226584Sdim 90321369Sdim // Ignore DBG_VALUE and similar instruction that do not contribute to any 91321369Sdim // instruction in the output. 92321369Sdim if (MInsn.isMetaInstruction()) 93226584Sdim continue; 94226584Sdim 95226584Sdim if (RangeBeginMI) { 96226584Sdim // If we have already seen a beginning of an instruction range and 97226584Sdim // current instruction scope does not match scope of first instruction 98226584Sdim // in this range then create a new instruction range. 99226584Sdim InsnRange R(RangeBeginMI, PrevMI); 100226584Sdim MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL); 101226584Sdim MIRanges.push_back(R); 102226584Sdim } 103226584Sdim 104226584Sdim // This is a beginning of a new instruction range. 105276479Sdim RangeBeginMI = &MInsn; 106226584Sdim 107226584Sdim // Reset previous markers. 108276479Sdim PrevMI = &MInsn; 109226584Sdim PrevDL = MIDL; 110226584Sdim } 111226584Sdim 112226584Sdim // Create last instruction range. 113288943Sdim if (RangeBeginMI && PrevMI && PrevDL) { 114226584Sdim InsnRange R(RangeBeginMI, PrevMI); 115226584Sdim MIRanges.push_back(R); 116226584Sdim MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL); 117226584Sdim } 118226584Sdim } 119226584Sdim} 120226584Sdim 121226584Sdim/// findLexicalScope - Find lexical scope, either regular or inlined, for the 122226584Sdim/// given DebugLoc. Return NULL if not found. 123288943SdimLexicalScope *LexicalScopes::findLexicalScope(const DILocation *DL) { 124288943Sdim DILocalScope *Scope = DL->getScope(); 125276479Sdim if (!Scope) 126276479Sdim return nullptr; 127226584Sdim 128226584Sdim // The scope that we were created with could have an extra file - which 129226584Sdim // isn't what we care about in this case. 130309124Sdim Scope = Scope->getNonLexicalBlockFileScope(); 131276479Sdim 132288943Sdim if (auto *IA = DL->getInlinedAt()) { 133276479Sdim auto I = InlinedLexicalScopeMap.find(std::make_pair(Scope, IA)); 134276479Sdim return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr; 135276479Sdim } 136276479Sdim return findLexicalScope(Scope); 137226584Sdim} 138226584Sdim 139226584Sdim/// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If 140226584Sdim/// not available then create new lexical scope. 141288943SdimLexicalScope *LexicalScopes::getOrCreateLexicalScope(const DILocalScope *Scope, 142288943Sdim const DILocation *IA) { 143288943Sdim if (IA) { 144321369Sdim // Skip scopes inlined from a NoDebug compile unit. 145321369Sdim if (Scope->getSubprogram()->getUnit()->getEmissionKind() == 146321369Sdim DICompileUnit::NoDebug) 147321369Sdim return getOrCreateLexicalScope(IA); 148226584Sdim // Create an abstract scope for inlined function. 149226584Sdim getOrCreateAbstractScope(Scope); 150226584Sdim // Create an inlined scope for inlined function. 151288943Sdim return getOrCreateInlinedScope(Scope, IA); 152226584Sdim } 153276479Sdim 154226584Sdim return getOrCreateRegularScope(Scope); 155226584Sdim} 156226584Sdim 157226584Sdim/// getOrCreateRegularScope - Find or create a regular lexical scope. 158288943SdimLexicalScope * 159288943SdimLexicalScopes::getOrCreateRegularScope(const DILocalScope *Scope) { 160309124Sdim assert(Scope && "Invalid Scope encoding!"); 161309124Sdim Scope = Scope->getNonLexicalBlockFileScope(); 162226584Sdim 163276479Sdim auto I = LexicalScopeMap.find(Scope); 164276479Sdim if (I != LexicalScopeMap.end()) 165276479Sdim return &I->second; 166276479Sdim 167288943Sdim // FIXME: Should the following dyn_cast be DILexicalBlock? 168276479Sdim LexicalScope *Parent = nullptr; 169288943Sdim if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope)) 170288943Sdim Parent = getOrCreateLexicalScope(Block->getScope()); 171288943Sdim I = LexicalScopeMap.emplace(std::piecewise_construct, 172288943Sdim std::forward_as_tuple(Scope), 173288943Sdim std::forward_as_tuple(Parent, Scope, nullptr, 174288943Sdim false)).first; 175276479Sdim 176280031Sdim if (!Parent) { 177327952Sdim assert(cast<DISubprogram>(Scope)->describes(&MF->getFunction())); 178280031Sdim assert(!CurrentFnLexicalScope); 179276479Sdim CurrentFnLexicalScope = &I->second; 180280031Sdim } 181276479Sdim 182276479Sdim return &I->second; 183226584Sdim} 184226584Sdim 185226584Sdim/// getOrCreateInlinedScope - Find or create an inlined lexical scope. 186288943SdimLexicalScope * 187288943SdimLexicalScopes::getOrCreateInlinedScope(const DILocalScope *Scope, 188288943Sdim const DILocation *InlinedAt) { 189309124Sdim assert(Scope && "Invalid Scope encoding!"); 190309124Sdim Scope = Scope->getNonLexicalBlockFileScope(); 191288943Sdim std::pair<const DILocalScope *, const DILocation *> P(Scope, InlinedAt); 192276479Sdim auto I = InlinedLexicalScopeMap.find(P); 193276479Sdim if (I != InlinedLexicalScopeMap.end()) 194276479Sdim return &I->second; 195226584Sdim 196276479Sdim LexicalScope *Parent; 197288943Sdim if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope)) 198288943Sdim Parent = getOrCreateInlinedScope(Block->getScope(), InlinedAt); 199276479Sdim else 200288943Sdim Parent = getOrCreateLexicalScope(InlinedAt); 201276479Sdim 202321369Sdim I = InlinedLexicalScopeMap 203321369Sdim .emplace(std::piecewise_construct, std::forward_as_tuple(P), 204321369Sdim std::forward_as_tuple(Parent, Scope, InlinedAt, false)) 205288943Sdim .first; 206276479Sdim return &I->second; 207226584Sdim} 208226584Sdim 209226584Sdim/// getOrCreateAbstractScope - Find or create an abstract lexical scope. 210288943SdimLexicalScope * 211288943SdimLexicalScopes::getOrCreateAbstractScope(const DILocalScope *Scope) { 212288943Sdim assert(Scope && "Invalid Scope encoding!"); 213309124Sdim Scope = Scope->getNonLexicalBlockFileScope(); 214276479Sdim auto I = AbstractScopeMap.find(Scope); 215276479Sdim if (I != AbstractScopeMap.end()) 216276479Sdim return &I->second; 217226584Sdim 218288943Sdim // FIXME: Should the following isa be DILexicalBlock? 219276479Sdim LexicalScope *Parent = nullptr; 220288943Sdim if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope)) 221288943Sdim Parent = getOrCreateAbstractScope(Block->getScope()); 222288943Sdim 223276479Sdim I = AbstractScopeMap.emplace(std::piecewise_construct, 224276479Sdim std::forward_as_tuple(Scope), 225276479Sdim std::forward_as_tuple(Parent, Scope, 226276479Sdim nullptr, true)).first; 227288943Sdim if (isa<DISubprogram>(Scope)) 228276479Sdim AbstractScopesList.push_back(&I->second); 229276479Sdim return &I->second; 230226584Sdim} 231226584Sdim 232226584Sdim/// constructScopeNest 233226584Sdimvoid LexicalScopes::constructScopeNest(LexicalScope *Scope) { 234276479Sdim assert(Scope && "Unable to calculate scope dominance graph!"); 235226584Sdim SmallVector<LexicalScope *, 4> WorkStack; 236226584Sdim WorkStack.push_back(Scope); 237226584Sdim unsigned Counter = 0; 238226584Sdim while (!WorkStack.empty()) { 239226584Sdim LexicalScope *WS = WorkStack.back(); 240261991Sdim const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren(); 241226584Sdim bool visitedChildren = false; 242314564Sdim for (auto &ChildScope : Children) 243226584Sdim if (!ChildScope->getDFSOut()) { 244226584Sdim WorkStack.push_back(ChildScope); 245226584Sdim visitedChildren = true; 246226584Sdim ChildScope->setDFSIn(++Counter); 247226584Sdim break; 248226584Sdim } 249226584Sdim if (!visitedChildren) { 250226584Sdim WorkStack.pop_back(); 251226584Sdim WS->setDFSOut(++Counter); 252226584Sdim } 253226584Sdim } 254226584Sdim} 255226584Sdim 256226584Sdim/// assignInstructionRanges - Find ranges of instructions covered by each 257226584Sdim/// lexical scope. 258276479Sdimvoid LexicalScopes::assignInstructionRanges( 259276479Sdim SmallVectorImpl<InsnRange> &MIRanges, 260276479Sdim DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) { 261276479Sdim LexicalScope *PrevLexicalScope = nullptr; 262314564Sdim for (const auto &R : MIRanges) { 263226584Sdim LexicalScope *S = MI2ScopeMap.lookup(R.first); 264276479Sdim assert(S && "Lost LexicalScope for a machine instruction!"); 265226584Sdim if (PrevLexicalScope && !PrevLexicalScope->dominates(S)) 266226584Sdim PrevLexicalScope->closeInsnRange(S); 267226584Sdim S->openInsnRange(R.first); 268226584Sdim S->extendInsnRange(R.second); 269226584Sdim PrevLexicalScope = S; 270226584Sdim } 271226584Sdim 272226584Sdim if (PrevLexicalScope) 273226584Sdim PrevLexicalScope->closeInsnRange(); 274226584Sdim} 275226584Sdim 276226584Sdim/// getMachineBasicBlocks - Populate given set using machine basic blocks which 277276479Sdim/// have machine instructions that belong to lexical scope identified by 278226584Sdim/// DebugLoc. 279276479Sdimvoid LexicalScopes::getMachineBasicBlocks( 280288943Sdim const DILocation *DL, SmallPtrSetImpl<const MachineBasicBlock *> &MBBs) { 281327952Sdim assert(MF && "Method called on a uninitialized LexicalScopes object!"); 282226584Sdim MBBs.clear(); 283327952Sdim 284226584Sdim LexicalScope *Scope = getOrCreateLexicalScope(DL); 285226584Sdim if (!Scope) 286226584Sdim return; 287276479Sdim 288226584Sdim if (Scope == CurrentFnLexicalScope) { 289276479Sdim for (const auto &MBB : *MF) 290276479Sdim MBBs.insert(&MBB); 291226584Sdim return; 292226584Sdim } 293226584Sdim 294261991Sdim SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges(); 295314564Sdim for (auto &R : InsnRanges) 296226584Sdim MBBs.insert(R.first->getParent()); 297226584Sdim} 298226584Sdim 299226584Sdim/// dominates - Return true if DebugLoc's lexical scope dominates at least one 300226584Sdim/// machine instruction's lexical scope in a given machine basic block. 301288943Sdimbool LexicalScopes::dominates(const DILocation *DL, MachineBasicBlock *MBB) { 302327952Sdim assert(MF && "Unexpected uninitialized LexicalScopes object!"); 303226584Sdim LexicalScope *Scope = getOrCreateLexicalScope(DL); 304226584Sdim if (!Scope) 305226584Sdim return false; 306226584Sdim 307226584Sdim // Current function scope covers all basic blocks in the function. 308226584Sdim if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF) 309226584Sdim return true; 310226584Sdim 311226584Sdim bool Result = false; 312314564Sdim for (auto &I : *MBB) { 313314564Sdim if (const DILocation *IDL = I.getDebugLoc()) 314288943Sdim if (LexicalScope *IScope = getOrCreateLexicalScope(IDL)) 315288943Sdim if (Scope->dominates(IScope)) 316288943Sdim return true; 317226584Sdim } 318226584Sdim return Result; 319226584Sdim} 320226584Sdim 321321369Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 322321369SdimLLVM_DUMP_METHOD void LexicalScope::dump(unsigned Indent) const { 323226584Sdim raw_ostream &err = dbgs(); 324249423Sdim err.indent(Indent); 325226584Sdim err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n"; 326226584Sdim const MDNode *N = Desc; 327249423Sdim err.indent(Indent); 328226584Sdim N->dump(); 329226584Sdim if (AbstractScope) 330249423Sdim err << std::string(Indent, ' ') << "Abstract Scope\n"; 331226584Sdim 332226584Sdim if (!Children.empty()) 333249423Sdim err << std::string(Indent + 2, ' ') << "Children ...\n"; 334226584Sdim for (unsigned i = 0, e = Children.size(); i != e; ++i) 335226584Sdim if (Children[i] != this) 336249423Sdim Children[i]->dump(Indent + 2); 337321369Sdim} 338226584Sdim#endif 339