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