LCOV - code coverage report
Current view: top level - lib/CodeGen - LexicalScopes.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 153 153 100.0 %
Date: 2017-09-14 15:23:50 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/IR/DebugInfoMetadata.h"
      24             : #include "llvm/IR/Metadata.h"
      25             : #include "llvm/Support/Casting.h"
      26             : #include "llvm/Support/Compiler.h"
      27             : #include "llvm/Support/Debug.h"
      28             : #include "llvm/Support/raw_ostream.h"
      29             : #include <cassert>
      30             : #include <string>
      31             : #include <tuple>
      32             : #include <utility>
      33             : 
      34             : using namespace llvm;
      35             : 
      36             : #define DEBUG_TYPE "lexicalscopes"
      37             : 
      38             : /// reset - Reset the instance so that it's prepared for another function.
      39       18292 : void LexicalScopes::reset() {
      40       18292 :   MF = nullptr;
      41       18292 :   CurrentFnLexicalScope = nullptr;
      42       36584 :   LexicalScopeMap.clear();
      43       36584 :   AbstractScopeMap.clear();
      44       36584 :   InlinedLexicalScopeMap.clear();
      45       36584 :   AbstractScopesList.clear();
      46       18292 : }
      47             : 
      48             : /// initialize - Scan machine function and constuct lexical scope nest.
      49       18292 : void LexicalScopes::initialize(const MachineFunction &Fn) {
      50       18292 :   reset();
      51             :   // Don't attempt any lexical scope creation for a NoDebug compile unit.
      52       36584 :   if (Fn.getFunction()->getSubprogram()->getUnit()->getEmissionKind() ==
      53             :       DICompileUnit::NoDebug)
      54          15 :     return;
      55       18277 :   MF = &Fn;
      56       36554 :   SmallVector<InsnRange, 4> MIRanges;
      57       36554 :   DenseMap<const MachineInstr *, LexicalScope *> MI2ScopeMap;
      58       18277 :   extractLexicalScopes(MIRanges, MI2ScopeMap);
      59       18277 :   if (CurrentFnLexicalScope) {
      60       18181 :     constructScopeNest(CurrentFnLexicalScope);
      61       18181 :     assignInstructionRanges(MIRanges, MI2ScopeMap);
      62             :   }
      63             : }
      64             : 
      65             : /// extractLexicalScopes - Extract instruction ranges for each lexical scopes
      66             : /// for the given machine function.
      67       18277 : void LexicalScopes::extractLexicalScopes(
      68             :     SmallVectorImpl<InsnRange> &MIRanges,
      69             :     DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {
      70             :   // Scan each instruction and create scopes. First build working set of scopes.
      71      411936 :   for (const auto &MBB : *MF) {
      72      357105 :     const MachineInstr *RangeBeginMI = nullptr;
      73      357105 :     const MachineInstr *PrevMI = nullptr;
      74      357105 :     const DILocation *PrevDL = nullptr;
      75     9979638 :     for (const auto &MInsn : MBB) {
      76             :       // Check if instruction has valid location information.
      77     8551218 :       const DILocation *MIDL = MInsn.getDebugLoc();
      78     4833578 :       if (!MIDL) {
      79      557969 :         PrevMI = &MInsn;
      80      557969 :         continue;
      81             :       }
      82             : 
      83             :       // If scope has not changed then skip this instruction.
      84     6166609 :       if (MIDL == PrevDL) {
      85     2448969 :         PrevMI = &MInsn;
      86     2448969 :         continue;
      87             :       }
      88             : 
      89             :       // Ignore DBG_VALUE and similar instruction that do not contribute to any
      90             :       // instruction in the output.
      91       89325 :       if (MInsn.isMetaInstruction())
      92       89325 :         continue;
      93             : 
      94     1179346 :       if (RangeBeginMI) {
      95             :         // If we have already seen a beginning of an instruction range and
      96             :         // current instruction scope does not match scope of first instruction
      97             :         // in this range then create a new instruction range.
      98      846591 :         InsnRange R(RangeBeginMI, PrevMI);
      99      846591 :         MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
     100      846591 :         MIRanges.push_back(R);
     101             :       }
     102             : 
     103             :       // This is a beginning of a new instruction range.
     104     1179346 :       RangeBeginMI = &MInsn;
     105             : 
     106             :       // Reset previous markers.
     107     1179346 :       PrevMI = &MInsn;
     108     1179346 :       PrevDL = MIDL;
     109             :     }
     110             : 
     111             :     // Create last instruction range.
     112      357105 :     if (RangeBeginMI && PrevMI && PrevDL) {
     113      332755 :       InsnRange R(RangeBeginMI, PrevMI);
     114      332755 :       MIRanges.push_back(R);
     115      332755 :       MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
     116             :     }
     117             :   }
     118       18277 : }
     119             : 
     120             : /// findLexicalScope - Find lexical scope, either regular or inlined, for the
     121             : /// given DebugLoc. Return NULL if not found.
     122       27262 : LexicalScope *LexicalScopes::findLexicalScope(const DILocation *DL) {
     123       27262 :   DILocalScope *Scope = DL->getScope();
     124       27262 :   if (!Scope)
     125             :     return nullptr;
     126             : 
     127             :   // The scope that we were created with could have an extra file - which
     128             :   // isn't what we care about in this case.
     129       27262 :   Scope = Scope->getNonLexicalBlockFileScope();
     130             : 
     131       22587 :   if (auto *IA = DL->getInlinedAt()) {
     132       90348 :     auto I = InlinedLexicalScopeMap.find(std::make_pair(Scope, IA));
     133       66624 :     return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr;
     134             :   }
     135        4675 :   return findLexicalScope(Scope);
     136             : }
     137             : 
     138             : /// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If
     139             : /// not available then create new lexical scope.
     140     1569748 : LexicalScope *LexicalScopes::getOrCreateLexicalScope(const DILocalScope *Scope,
     141             :                                                      const DILocation *IA) {
     142     1569748 :   if (IA) {
     143             :     // Skip scopes inlined from a NoDebug compile unit.
     144     2105052 :     if (Scope->getSubprogram()->getUnit()->getEmissionKind() ==
     145             :         DICompileUnit::NoDebug)
     146           3 :       return getOrCreateLexicalScope(IA);
     147             :     // Create an abstract scope for inlined function.
     148     1052523 :     getOrCreateAbstractScope(Scope);
     149             :     // Create an inlined scope for inlined function.
     150     1052523 :     return getOrCreateInlinedScope(Scope, IA);
     151             :   }
     152             : 
     153      517222 :   return getOrCreateRegularScope(Scope);
     154             : }
     155             : 
     156             : /// getOrCreateRegularScope - Find or create a regular lexical scope.
     157             : LexicalScope *
     158      517222 : LexicalScopes::getOrCreateRegularScope(const DILocalScope *Scope) {
     159             :   assert(Scope && "Invalid Scope encoding!");
     160      517222 :   Scope = Scope->getNonLexicalBlockFileScope();
     161             : 
     162     1034444 :   auto I = LexicalScopeMap.find(Scope);
     163     1034444 :   if (I != LexicalScopeMap.end())
     164      494903 :     return &I->second;
     165             : 
     166             :   // FIXME: Should the following dyn_cast be DILexicalBlock?
     167       22319 :   LexicalScope *Parent = nullptr;
     168       26456 :   if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
     169        4137 :     Parent = getOrCreateLexicalScope(Block->getScope());
     170       22319 :   I = LexicalScopeMap.emplace(std::piecewise_construct,
     171       22319 :                               std::forward_as_tuple(Scope),
     172       22319 :                               std::forward_as_tuple(Parent, Scope, nullptr,
     173       89276 :                                                     false)).first;
     174             : 
     175       22319 :   if (!Parent) {
     176             :     assert(cast<DISubprogram>(Scope)->describes(MF->getFunction()));
     177             :     assert(!CurrentFnLexicalScope);
     178       18182 :     CurrentFnLexicalScope = &I->second;
     179             :   }
     180             : 
     181       22319 :   return &I->second;
     182             : }
     183             : 
     184             : /// getOrCreateInlinedScope - Find or create an inlined lexical scope.
     185             : LexicalScope *
     186     1063329 : LexicalScopes::getOrCreateInlinedScope(const DILocalScope *Scope,
     187             :                                        const DILocation *InlinedAt) {
     188             :   assert(Scope && "Invalid Scope encoding!");
     189     1063329 :   Scope = Scope->getNonLexicalBlockFileScope();
     190     1063329 :   std::pair<const DILocalScope *, const DILocation *> P(Scope, InlinedAt);
     191     2126658 :   auto I = InlinedLexicalScopeMap.find(P);
     192     2126658 :   if (I != InlinedLexicalScopeMap.end())
     193      788520 :     return &I->second;
     194             : 
     195             :   LexicalScope *Parent;
     196      285615 :   if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
     197       21612 :     Parent = getOrCreateInlinedScope(Block->getScope(), InlinedAt);
     198             :   else
     199      264003 :     Parent = getOrCreateLexicalScope(InlinedAt);
     200             : 
     201      274809 :   I = InlinedLexicalScopeMap
     202      549618 :           .emplace(std::piecewise_construct, std::forward_as_tuple(P),
     203     1099236 :                    std::forward_as_tuple(Parent, Scope, InlinedAt, false))
     204             :           .first;
     205      274809 :   return &I->second;
     206             : }
     207             : 
     208             : /// getOrCreateAbstractScope - Find or create an abstract lexical scope.
     209             : LexicalScope *
     210     1061282 : LexicalScopes::getOrCreateAbstractScope(const DILocalScope *Scope) {
     211             :   assert(Scope && "Invalid Scope encoding!");
     212     1061282 :   Scope = Scope->getNonLexicalBlockFileScope();
     213     2122564 :   auto I = AbstractScopeMap.find(Scope);
     214     2122564 :   if (I != AbstractScopeMap.end())
     215      946634 :     return &I->second;
     216             : 
     217             :   // FIXME: Should the following isa be DILexicalBlock?
     218      114648 :   LexicalScope *Parent = nullptr;
     219      120111 :   if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
     220        5463 :     Parent = getOrCreateAbstractScope(Block->getScope());
     221             : 
     222      114648 :   I = AbstractScopeMap.emplace(std::piecewise_construct,
     223      114648 :                                std::forward_as_tuple(Scope),
     224      114648 :                                std::forward_as_tuple(Parent, Scope,
     225      458592 :                                                      nullptr, true)).first;
     226      229296 :   if (isa<DISubprogram>(Scope))
     227      218370 :     AbstractScopesList.push_back(&I->second);
     228      114648 :   return &I->second;
     229             : }
     230             : 
     231             : /// constructScopeNest
     232       18181 : void LexicalScopes::constructScopeNest(LexicalScope *Scope) {
     233             :   assert(Scope && "Unable to calculate scope dominance graph!");
     234       36362 :   SmallVector<LexicalScope *, 4> WorkStack;
     235       18181 :   WorkStack.push_back(Scope);
     236       18181 :   unsigned Counter = 0;
     237      593238 :   while (!WorkStack.empty()) {
     238     1150114 :     LexicalScope *WS = WorkStack.back();
     239      575057 :     const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
     240      575057 :     bool visitedChildren = false;
     241     4511844 :     for (auto &ChildScope : Children)
     242     3065111 :       if (!ChildScope->getDFSOut()) {
     243      278438 :         WorkStack.push_back(ChildScope);
     244      278438 :         visitedChildren = true;
     245      278438 :         ChildScope->setDFSIn(++Counter);
     246             :         break;
     247             :       }
     248      575057 :     if (!visitedChildren) {
     249      296619 :       WorkStack.pop_back();
     250      296619 :       WS->setDFSOut(++Counter);
     251             :     }
     252             :   }
     253       18181 : }
     254             : 
     255             : /// assignInstructionRanges - Find ranges of instructions covered by each
     256             : /// lexical scope.
     257       18181 : void LexicalScopes::assignInstructionRanges(
     258             :     SmallVectorImpl<InsnRange> &MIRanges,
     259             :     DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {
     260       18181 :   LexicalScope *PrevLexicalScope = nullptr;
     261     1233889 :   for (const auto &R : MIRanges) {
     262     2358692 :     LexicalScope *S = MI2ScopeMap.lookup(R.first);
     263             :     assert(S && "Lost LexicalScope for a machine instruction!");
     264     1179346 :     if (PrevLexicalScope && !PrevLexicalScope->dominates(S))
     265      362948 :       PrevLexicalScope->closeInsnRange(S);
     266     2358692 :     S->openInsnRange(R.first);
     267     2358692 :     S->extendInsnRange(R.second);
     268     1179346 :     PrevLexicalScope = S;
     269             :   }
     270             : 
     271       18181 :   if (PrevLexicalScope)
     272       18181 :     PrevLexicalScope->closeInsnRange();
     273       18181 : }
     274             : 
     275             : /// getMachineBasicBlocks - Populate given set using machine basic blocks which
     276             : /// have machine instructions that belong to lexical scope identified by
     277             : /// DebugLoc.
     278        7625 : void LexicalScopes::getMachineBasicBlocks(
     279             :     const DILocation *DL, SmallPtrSetImpl<const MachineBasicBlock *> &MBBs) {
     280             :   assert(MF && "Method called on a uninitialized LexicalScopes object!");
     281        7625 :   MBBs.clear();
     282             : 
     283        7625 :   LexicalScope *Scope = getOrCreateLexicalScope(DL);
     284        7625 :   if (!Scope)
     285             :     return;
     286             : 
     287        7625 :   if (Scope == CurrentFnLexicalScope) {
     288       36603 :     for (const auto &MBB : *MF)
     289       33609 :       MBBs.insert(&MBB);
     290             :     return;
     291             :   }
     292             : 
     293        6627 :   SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges();
     294       27239 :   for (auto &R : InsnRanges)
     295        7358 :     MBBs.insert(R.first->getParent());
     296             : }
     297             : 
     298             : /// dominates - Return true if DebugLoc's lexical scope dominates at least one
     299             : /// machine instruction's lexical scope in a given machine basic block.
     300       26257 : bool LexicalScopes::dominates(const DILocation *DL, MachineBasicBlock *MBB) {
     301             :   assert(MF && "Unexpected uninitialized LexicalScopes object!");
     302       26257 :   LexicalScope *Scope = getOrCreateLexicalScope(DL);
     303       26257 :   if (!Scope)
     304             :     return false;
     305             : 
     306             :   // Current function scope covers all basic blocks in the function.
     307       26257 :   if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF)
     308             :     return true;
     309             : 
     310       26257 :   bool Result = false;
     311      291111 :   for (auto &I : *MBB) {
     312      200042 :     if (const DILocation *IDL = I.getDebugLoc())
     313       88377 :       if (LexicalScope *IScope = getOrCreateLexicalScope(IDL))
     314             :         if (Scope->dominates(IScope))
     315       13959 :           return true;
     316             :   }
     317       12298 :   return Result;
     318             : }
     319             : 
     320             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     321             : LLVM_DUMP_METHOD void LexicalScope::dump(unsigned Indent) const {
     322             :   raw_ostream &err = dbgs();
     323             :   err.indent(Indent);
     324             :   err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n";
     325             :   const MDNode *N = Desc;
     326             :   err.indent(Indent);
     327             :   N->dump();
     328             :   if (AbstractScope)
     329             :     err << std::string(Indent, ' ') << "Abstract Scope\n";
     330             : 
     331             :   if (!Children.empty())
     332             :     err << std::string(Indent + 2, ' ') << "Children ...\n";
     333             :   for (unsigned i = 0, e = Children.size(); i != e; ++i)
     334             :     if (Children[i] != this)
     335             :       Children[i]->dump(Indent + 2);
     336             : }
     337             : #endif

Generated by: LCOV version 1.13