LCOV - code coverage report
Current view: top level - lib/CodeGen - LexicalScopes.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 116 116 100.0 %
Date: 2018-07-13 00:08:38 Functions: 12 12 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- LexicalScopes.cpp - Collecting lexical scope info ------------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file implements LexicalScopes analysis.
      11             : //
      12             : // This pass collects lexical scope information and maps machine instructions
      13             : // to respective lexical scopes.
      14             : //
      15             : //===----------------------------------------------------------------------===//
      16             : 
      17             : #include "llvm/CodeGen/LexicalScopes.h"
      18             : #include "llvm/ADT/DenseMap.h"
      19             : #include "llvm/ADT/SmallVector.h"
      20             : #include "llvm/CodeGen/MachineBasicBlock.h"
      21             : #include "llvm/CodeGen/MachineFunction.h"
      22             : #include "llvm/CodeGen/MachineInstr.h"
      23             : #include "llvm/Config/llvm-config.h"
      24             : #include "llvm/IR/DebugInfoMetadata.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       79036 : void LexicalScopes::reset() {
      41       79036 :   MF = nullptr;
      42       79036 :   CurrentFnLexicalScope = nullptr;
      43             :   LexicalScopeMap.clear();
      44             :   AbstractScopeMap.clear();
      45             :   InlinedLexicalScopeMap.clear();
      46             :   AbstractScopesList.clear();
      47       79036 : }
      48             : 
      49             : /// initialize - Scan machine function and constuct lexical scope nest.
      50       79036 : void LexicalScopes::initialize(const MachineFunction &Fn) {
      51       79036 :   reset();
      52             :   // Don't attempt any lexical scope creation for a NoDebug compile unit.
      53      158072 :   if (Fn.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
      54             :       DICompileUnit::NoDebug)
      55          16 :     return;
      56       79020 :   MF = &Fn;
      57             :   SmallVector<InsnRange, 4> MIRanges;
      58             :   DenseMap<const MachineInstr *, LexicalScope *> MI2ScopeMap;
      59       79020 :   extractLexicalScopes(MIRanges, MI2ScopeMap);
      60       79020 :   if (CurrentFnLexicalScope) {
      61       78862 :     constructScopeNest(CurrentFnLexicalScope);
      62       78862 :     assignInstructionRanges(MIRanges, MI2ScopeMap);
      63             :   }
      64             : }
      65             : 
      66             : /// extractLexicalScopes - Extract instruction ranges for each lexical scopes
      67             : /// for the given machine function.
      68       79020 : void LexicalScopes::extractLexicalScopes(
      69             :     SmallVectorImpl<InsnRange> &MIRanges,
      70             :     DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {
      71             :   // Scan each instruction and create scopes. First build working set of scopes.
      72      685034 :   for (const auto &MBB : *MF) {
      73      526994 :     const MachineInstr *RangeBeginMI = nullptr;
      74             :     const MachineInstr *PrevMI = nullptr;
      75             :     const DILocation *PrevDL = nullptr;
      76     7186578 :     for (const auto &MInsn : MBB) {
      77             :       // Check if instruction has valid location information.
      78             :       const DILocation *MIDL = MInsn.getDebugLoc();
      79     6132590 :       if (!MIDL) {
      80             :         PrevMI = &MInsn;
      81     1117246 :         continue;
      82             :       }
      83             : 
      84             :       // If scope has not changed then skip this instruction.
      85     5015344 :       if (MIDL == PrevDL) {
      86             :         PrevMI = &MInsn;
      87     3205342 :         continue;
      88             :       }
      89             : 
      90             :       // Ignore DBG_VALUE and similar instruction that do not contribute to any
      91             :       // instruction in the output.
      92      174590 :       if (MInsn.isMetaInstruction())
      93      174590 :         continue;
      94             : 
      95     1635412 :       if (RangeBeginMI) {
      96             :         // If we have already seen a beginning of an instruction range and
      97             :         // current instruction scope does not match scope of first instruction
      98             :         // in this range then create a new instruction range.
      99             :         InsnRange R(RangeBeginMI, PrevMI);
     100     1140706 :         MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
     101     1140706 :         MIRanges.push_back(R);
     102             :       }
     103             : 
     104             :       // This is a beginning of a new instruction range.
     105     1635412 :       RangeBeginMI = &MInsn;
     106             : 
     107             :       // Reset previous markers.
     108             :       PrevMI = &MInsn;
     109             :       PrevDL = MIDL;
     110             :     }
     111             : 
     112             :     // Create last instruction range.
     113      526994 :     if (RangeBeginMI && PrevMI && PrevDL) {
     114             :       InsnRange R(RangeBeginMI, PrevMI);
     115      494706 :       MIRanges.push_back(R);
     116      494706 :       MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
     117             :     }
     118             :   }
     119       79020 : }
     120             : 
     121             : /// findLexicalScope - Find lexical scope, either regular or inlined, for the
     122             : /// given DebugLoc. Return NULL if not found.
     123      100497 : LexicalScope *LexicalScopes::findLexicalScope(const DILocation *DL) {
     124             :   DILocalScope *Scope = DL->getScope();
     125      100497 :   if (!Scope)
     126             :     return nullptr;
     127             : 
     128             :   // The scope that we were created with could have an extra file - which
     129             :   // isn't what we care about in this case.
     130      100497 :   Scope = Scope->getNonLexicalBlockFileScope();
     131             : 
     132             :   if (auto *IA = DL->getInlinedAt()) {
     133       42220 :     auto I = InlinedLexicalScopeMap.find(std::make_pair(Scope, IA));
     134       42220 :     return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr;
     135             :   }
     136             :   return findLexicalScope(Scope);
     137             : }
     138             : 
     139             : /// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If
     140             : /// not available then create new lexical scope.
     141     2206943 : LexicalScope *LexicalScopes::getOrCreateLexicalScope(const DILocalScope *Scope,
     142             :                                                      const DILocation *IA) {
     143     2206943 :   if (IA) {
     144             :     // Skip scopes inlined from a NoDebug compile unit.
     145     2441968 :     if (Scope->getSubprogram()->getUnit()->getEmissionKind() ==
     146             :         DICompileUnit::NoDebug)
     147           3 :       return getOrCreateLexicalScope(IA);
     148             :     // Create an abstract scope for inlined function.
     149     1220981 :     getOrCreateAbstractScope(Scope);
     150             :     // Create an inlined scope for inlined function.
     151     1220981 :     return getOrCreateInlinedScope(Scope, IA);
     152             :   }
     153             : 
     154      985959 :   return getOrCreateRegularScope(Scope);
     155             : }
     156             : 
     157             : /// getOrCreateRegularScope - Find or create a regular lexical scope.
     158             : LexicalScope *
     159      985959 : LexicalScopes::getOrCreateRegularScope(const DILocalScope *Scope) {
     160             :   assert(Scope && "Invalid Scope encoding!");
     161      985959 :   Scope = Scope->getNonLexicalBlockFileScope();
     162             : 
     163             :   auto I = LexicalScopeMap.find(Scope);
     164      985959 :   if (I != LexicalScopeMap.end())
     165      875339 :     return &I->second;
     166             : 
     167             :   // FIXME: Should the following dyn_cast be DILexicalBlock?
     168      110620 :   LexicalScope *Parent = nullptr;
     169             :   if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
     170       31754 :     Parent = getOrCreateLexicalScope(Block->getScope());
     171             :   I = LexicalScopeMap.emplace(std::piecewise_construct,
     172      110620 :                               std::forward_as_tuple(Scope),
     173      110620 :                               std::forward_as_tuple(Parent, Scope, nullptr,
     174      221240 :                                                     false)).first;
     175             : 
     176      110620 :   if (!Parent) {
     177             :     assert(cast<DISubprogram>(Scope)->describes(&MF->getFunction()));
     178             :     assert(!CurrentFnLexicalScope);
     179       78866 :     CurrentFnLexicalScope = &I->second;
     180             :   }
     181             : 
     182      110620 :   return &I->second;
     183             : }
     184             : 
     185             : /// getOrCreateInlinedScope - Find or create an inlined lexical scope.
     186             : LexicalScope *
     187     1235571 : LexicalScopes::getOrCreateInlinedScope(const DILocalScope *Scope,
     188             :                                        const DILocation *InlinedAt) {
     189             :   assert(Scope && "Invalid Scope encoding!");
     190     1235571 :   Scope = Scope->getNonLexicalBlockFileScope();
     191             :   std::pair<const DILocalScope *, const DILocation *> P(Scope, InlinedAt);
     192             :   auto I = InlinedLexicalScopeMap.find(P);
     193     1235571 :   if (I != InlinedLexicalScopeMap.end())
     194      925242 :     return &I->second;
     195             : 
     196             :   LexicalScope *Parent;
     197      310329 :   if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
     198       29180 :     Parent = getOrCreateInlinedScope(Block->getScope(), InlinedAt);
     199             :   else
     200      295739 :     Parent = getOrCreateLexicalScope(InlinedAt);
     201             : 
     202             :   I = InlinedLexicalScopeMap
     203      310329 :           .emplace(std::piecewise_construct, std::forward_as_tuple(P),
     204      620658 :                    std::forward_as_tuple(Parent, Scope, InlinedAt, false))
     205             :           .first;
     206      310329 :   return &I->second;
     207             : }
     208             : 
     209             : /// getOrCreateAbstractScope - Find or create an abstract lexical scope.
     210             : LexicalScope *
     211     1230237 : LexicalScopes::getOrCreateAbstractScope(const DILocalScope *Scope) {
     212             :   assert(Scope && "Invalid Scope encoding!");
     213     1230237 :   Scope = Scope->getNonLexicalBlockFileScope();
     214             :   auto I = AbstractScopeMap.find(Scope);
     215     1230237 :   if (I != AbstractScopeMap.end())
     216     1095590 :     return &I->second;
     217             : 
     218             :   // FIXME: Should the following isa be DILexicalBlock?
     219      134647 :   LexicalScope *Parent = nullptr;
     220             :   if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
     221        7705 :     Parent = getOrCreateAbstractScope(Block->getScope());
     222             : 
     223             :   I = AbstractScopeMap.emplace(std::piecewise_construct,
     224      134647 :                                std::forward_as_tuple(Scope),
     225      134647 :                                std::forward_as_tuple(Parent, Scope,
     226      269294 :                                                      nullptr, true)).first;
     227      269294 :   if (isa<DISubprogram>(Scope))
     228      126942 :     AbstractScopesList.push_back(&I->second);
     229      134647 :   return &I->second;
     230             : }
     231             : 
     232             : /// constructScopeNest
     233       78862 : void LexicalScopes::constructScopeNest(LexicalScope *Scope) {
     234             :   assert(Scope && "Unable to calculate scope dominance graph!");
     235             :   SmallVector<LexicalScope *, 4> WorkStack;
     236       78862 :   WorkStack.push_back(Scope);
     237             :   unsigned Counter = 0;
     238      839586 :   while (!WorkStack.empty()) {
     239      760724 :     LexicalScope *WS = WorkStack.back();
     240             :     const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
     241             :     bool visitedChildren = false;
     242     6668772 :     for (auto &ChildScope : Children)
     243     3294955 :       if (!ChildScope->getDFSOut()) {
     244      340931 :         WorkStack.push_back(ChildScope);
     245             :         visitedChildren = true;
     246      340931 :         ChildScope->setDFSIn(++Counter);
     247             :         break;
     248             :       }
     249      760724 :     if (!visitedChildren) {
     250             :       WorkStack.pop_back();
     251      419793 :       WS->setDFSOut(++Counter);
     252             :     }
     253             :   }
     254       78862 : }
     255             : 
     256             : /// assignInstructionRanges - Find ranges of instructions covered by each
     257             : /// lexical scope.
     258       78862 : void LexicalScopes::assignInstructionRanges(
     259             :     SmallVectorImpl<InsnRange> &MIRanges,
     260             :     DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {
     261             :   LexicalScope *PrevLexicalScope = nullptr;
     262     3349686 :   for (const auto &R : MIRanges) {
     263     1635412 :     LexicalScope *S = MI2ScopeMap.lookup(R.first);
     264             :     assert(S && "Lost LexicalScope for a machine instruction!");
     265     1635412 :     if (PrevLexicalScope && !PrevLexicalScope->dominates(S))
     266      413716 :       PrevLexicalScope->closeInsnRange(S);
     267     1635412 :     S->openInsnRange(R.first);
     268     1635412 :     S->extendInsnRange(R.second);
     269             :     PrevLexicalScope = S;
     270             :   }
     271             : 
     272       78862 :   if (PrevLexicalScope)
     273       78862 :     PrevLexicalScope->closeInsnRange();
     274       78862 : }
     275             : 
     276             : /// getMachineBasicBlocks - Populate given set using machine basic blocks which
     277             : /// have machine instructions that belong to lexical scope identified by
     278             : /// DebugLoc.
     279       15254 : void LexicalScopes::getMachineBasicBlocks(
     280             :     const DILocation *DL, SmallPtrSetImpl<const MachineBasicBlock *> &MBBs) {
     281             :   assert(MF && "Method called on a uninitialized LexicalScopes object!");
     282       15254 :   MBBs.clear();
     283             : 
     284       15254 :   LexicalScope *Scope = getOrCreateLexicalScope(DL);
     285       15254 :   if (!Scope)
     286             :     return;
     287             : 
     288       15254 :   if (Scope == CurrentFnLexicalScope) {
     289       51261 :     for (const auto &MBB : *MF)
     290       48241 :       MBBs.insert(&MBB);
     291             :     return;
     292             :   }
     293             : 
     294             :   SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges();
     295       43398 :   for (auto &R : InsnRanges)
     296       14827 :     MBBs.insert(R.first->getParent());
     297             : }
     298             : 
     299             : /// dominates - Return true if DebugLoc's lexical scope dominates at least one
     300             : /// machine instruction's lexical scope in a given machine basic block.
     301       46005 : bool LexicalScopes::dominates(const DILocation *DL, MachineBasicBlock *MBB) {
     302             :   assert(MF && "Unexpected uninitialized LexicalScopes object!");
     303       46005 :   LexicalScope *Scope = getOrCreateLexicalScope(DL);
     304       46005 :   if (!Scope)
     305             :     return false;
     306             : 
     307             :   // Current function scope covers all basic blocks in the function.
     308       46005 :   if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF)
     309             :     return true;
     310             : 
     311             :   bool Result = false;
     312      277245 :   for (auto &I : *MBB) {
     313      207070 :     if (const DILocation *IDL = I.getDebugLoc())
     314      182776 :       if (LexicalScope *IScope = getOrCreateLexicalScope(IDL))
     315             :         if (Scope->dominates(IScope))
     316       21835 :           return true;
     317             :   }
     318       24170 :   return Result;
     319             : }
     320             : 
     321             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     322             : LLVM_DUMP_METHOD void LexicalScope::dump(unsigned Indent) const {
     323             :   raw_ostream &err = dbgs();
     324             :   err.indent(Indent);
     325             :   err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n";
     326             :   const MDNode *N = Desc;
     327             :   err.indent(Indent);
     328             :   N->dump();
     329             :   if (AbstractScope)
     330             :     err << std::string(Indent, ' ') << "Abstract Scope\n";
     331             : 
     332             :   if (!Children.empty())
     333             :     err << std::string(Indent + 2, ' ') << "Children ...\n";
     334             :   for (unsigned i = 0, e = Children.size(); i != e; ++i)
     335             :     if (Children[i] != this)
     336             :       Children[i]->dump(Indent + 2);
     337             : }
     338             : #endif

Generated by: LCOV version 1.13