Home | History | Annotate | Download | only in CodeGen 
      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/CodeGen/MachineFunction.h"
     19 #include "llvm/CodeGen/MachineInstr.h"
     20 #include "llvm/IR/DebugInfo.h"
     21 #include "llvm/IR/Function.h"
     22 #include "llvm/Support/Debug.h"
     23 #include "llvm/Support/ErrorHandling.h"
     24 #include "llvm/Support/FormattedStream.h"
     25 using namespace llvm;
     26 
     27 #define DEBUG_TYPE "lexicalscopes"
     28 
     29 /// reset - Reset the instance so that it's prepared for another function.
     30 void LexicalScopes::reset() {
     31   MF = nullptr;
     32   CurrentFnLexicalScope = nullptr;
     33   LexicalScopeMap.clear();
     34   AbstractScopeMap.clear();
     35   InlinedLexicalScopeMap.clear();
     36   AbstractScopesList.clear();
     37 }
     38 
     39 /// initialize - Scan machine function and constuct lexical scope nest.
     40 void LexicalScopes::initialize(const MachineFunction &Fn) {
     41   reset();
     42   MF = &Fn;
     43   SmallVector<InsnRange, 4> MIRanges;
     44   DenseMap<const MachineInstr *, LexicalScope *> MI2ScopeMap;
     45   extractLexicalScopes(MIRanges, MI2ScopeMap);
     46   if (CurrentFnLexicalScope) {
     47     constructScopeNest(CurrentFnLexicalScope);
     48     assignInstructionRanges(MIRanges, MI2ScopeMap);
     49   }
     50 }
     51 
     52 /// extractLexicalScopes - Extract instruction ranges for each lexical scopes
     53 /// for the given machine function.
     54 void LexicalScopes::extractLexicalScopes(
     55     SmallVectorImpl<InsnRange> &MIRanges,
     56     DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {
     57 
     58   // Scan each instruction and create scopes. First build working set of scopes.
     59   for (const auto &MBB : *MF) {
     60     const MachineInstr *RangeBeginMI = nullptr;
     61     const MachineInstr *PrevMI = nullptr;
     62     DebugLoc PrevDL;
     63     for (const auto &MInsn : MBB) {
     64       // Check if instruction has valid location information.
     65       const DebugLoc MIDL = MInsn.getDebugLoc();
     66       if (MIDL.isUnknown()) {
     67         PrevMI = &MInsn;
     68         continue;
     69       }
     70 
     71       // If scope has not changed then skip this instruction.
     72       if (MIDL == PrevDL) {
     73         PrevMI = &MInsn;
     74         continue;
     75       }
     76 
     77       // Ignore DBG_VALUE. It does not contribute to any instruction in output.
     78       if (MInsn.isDebugValue())
     79         continue;
     80 
     81       if (RangeBeginMI) {
     82         // If we have already seen a beginning of an instruction range and
     83         // current instruction scope does not match scope of first instruction
     84         // in this range then create a new instruction range.
     85         InsnRange R(RangeBeginMI, PrevMI);
     86         MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
     87         MIRanges.push_back(R);
     88       }
     89 
     90       // This is a beginning of a new instruction range.
     91       RangeBeginMI = &MInsn;
     92 
     93       // Reset previous markers.
     94       PrevMI = &MInsn;
     95       PrevDL = MIDL;
     96     }
     97 
     98     // Create last instruction range.
     99     if (RangeBeginMI && PrevMI && !PrevDL.isUnknown()) {
    100       InsnRange R(RangeBeginMI, PrevMI);
    101       MIRanges.push_back(R);
    102       MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
    103     }
    104   }
    105 }
    106 
    107 LexicalScope *LexicalScopes::findInlinedScope(DebugLoc DL) {
    108   MDNode *Scope = nullptr;
    109   MDNode *IA = nullptr;
    110   DL.getScopeAndInlinedAt(Scope, IA, MF->getFunction()->getContext());
    111   auto I = InlinedLexicalScopeMap.find(std::make_pair(Scope, IA));
    112   return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr;
    113 }
    114 
    115 /// findLexicalScope - Find lexical scope, either regular or inlined, for the
    116 /// given DebugLoc. Return NULL if not found.
    117 LexicalScope *LexicalScopes::findLexicalScope(DebugLoc DL) {
    118   MDNode *Scope = nullptr;
    119   MDNode *IA = nullptr;
    120   DL.getScopeAndInlinedAt(Scope, IA, MF->getFunction()->getContext());
    121   if (!Scope)
    122     return nullptr;
    123 
    124   // The scope that we were created with could have an extra file - which
    125   // isn't what we care about in this case.
    126   DIDescriptor D = DIDescriptor(Scope);
    127   if (D.isLexicalBlockFile())
    128     Scope = DILexicalBlockFile(Scope).getScope();
    129 
    130   if (IA) {
    131     auto I = InlinedLexicalScopeMap.find(std::make_pair(Scope, IA));
    132     return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr;
    133   }
    134   return findLexicalScope(Scope);
    135 }
    136 
    137 /// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If
    138 /// not available then create new lexical scope.
    139 LexicalScope *LexicalScopes::getOrCreateLexicalScope(DebugLoc DL) {
    140   MDNode *Scope = nullptr;
    141   MDNode *InlinedAt = nullptr;
    142   DL.getScopeAndInlinedAt(Scope, InlinedAt, MF->getFunction()->getContext());
    143 
    144   if (InlinedAt) {
    145     // Create an abstract scope for inlined function.
    146     getOrCreateAbstractScope(Scope);
    147     // Create an inlined scope for inlined function.
    148     return getOrCreateInlinedScope(Scope, InlinedAt);
    149   }
    150 
    151   return getOrCreateRegularScope(Scope);
    152 }
    153 
    154 /// getOrCreateRegularScope - Find or create a regular lexical scope.
    155 LexicalScope *LexicalScopes::getOrCreateRegularScope(MDNode *Scope) {
    156   DIDescriptor D = DIDescriptor(Scope);
    157   if (D.isLexicalBlockFile()) {
    158     Scope = DILexicalBlockFile(Scope).getScope();
    159     D = DIDescriptor(Scope);
    160   }
    161 
    162   auto I = LexicalScopeMap.find(Scope);
    163   if (I != LexicalScopeMap.end())
    164     return &I->second;
    165 
    166   LexicalScope *Parent = nullptr;
    167   if (D.isLexicalBlock())
    168     Parent = getOrCreateLexicalScope(DebugLoc::getFromDILexicalBlock(Scope));
    169   // FIXME: Use forward_as_tuple instead of make_tuple, once MSVC2012
    170   // compatibility is no longer required.
    171   I = LexicalScopeMap.emplace(std::piecewise_construct, std::make_tuple(Scope),
    172                               std::make_tuple(Parent, DIDescriptor(Scope),
    173                                               nullptr, false)).first;
    174 
    175   if (!Parent && DIDescriptor(Scope).isSubprogram() &&
    176       DISubprogram(Scope).describes(MF->getFunction()))
    177     CurrentFnLexicalScope = &I->second;
    178 
    179   return &I->second;
    180 }
    181 
    182 /// getOrCreateInlinedScope - Find or create an inlined lexical scope.
    183 LexicalScope *LexicalScopes::getOrCreateInlinedScope(MDNode *ScopeNode,
    184                                                      MDNode *InlinedAt) {
    185   std::pair<const MDNode*, const MDNode*> P(ScopeNode, InlinedAt);
    186   auto I = InlinedLexicalScopeMap.find(P);
    187   if (I != InlinedLexicalScopeMap.end())
    188     return &I->second;
    189 
    190   LexicalScope *Parent;
    191   DILexicalBlock Scope(ScopeNode);
    192   if (Scope.isSubprogram())
    193     Parent = getOrCreateLexicalScope(DebugLoc::getFromDILocation(InlinedAt));
    194   else
    195     Parent = getOrCreateInlinedScope(Scope.getContext(), InlinedAt);
    196 
    197   // FIXME: Use forward_as_tuple instead of make_tuple, once MSVC2012
    198   // compatibility is no longer required.
    199   I = InlinedLexicalScopeMap.emplace(std::piecewise_construct,
    200                                      std::make_tuple(P),
    201                                      std::make_tuple(Parent, Scope, InlinedAt,
    202                                                      false)).first;
    203   return &I->second;
    204 }
    205 
    206 /// getOrCreateAbstractScope - Find or create an abstract lexical scope.
    207 LexicalScope *LexicalScopes::getOrCreateAbstractScope(const MDNode *N) {
    208   assert(N && "Invalid Scope encoding!");
    209 
    210   DIDescriptor Scope(N);
    211   if (Scope.isLexicalBlockFile())
    212     Scope = DILexicalBlockFile(Scope).getScope();
    213   auto I = AbstractScopeMap.find(Scope);
    214   if (I != AbstractScopeMap.end())
    215     return &I->second;
    216 
    217   LexicalScope *Parent = nullptr;
    218   if (Scope.isLexicalBlock()) {
    219     DILexicalBlock DB(Scope);
    220     DIDescriptor ParentDesc = DB.getContext();
    221     Parent = getOrCreateAbstractScope(ParentDesc);
    222   }
    223   I = AbstractScopeMap.emplace(std::piecewise_construct,
    224                                std::forward_as_tuple(Scope),
    225                                std::forward_as_tuple(Parent, Scope,
    226                                                      nullptr, true)).first;
    227   if (Scope.isSubprogram())
    228     AbstractScopesList.push_back(&I->second);
    229   return &I->second;
    230 }
    231 
    232 /// constructScopeNest
    233 void LexicalScopes::constructScopeNest(LexicalScope *Scope) {
    234   assert(Scope && "Unable to calculate scope dominance graph!");
    235   SmallVector<LexicalScope *, 4> WorkStack;
    236   WorkStack.push_back(Scope);
    237   unsigned Counter = 0;
    238   while (!WorkStack.empty()) {
    239     LexicalScope *WS = WorkStack.back();
    240     const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
    241     bool visitedChildren = false;
    242     for (SmallVectorImpl<LexicalScope *>::const_iterator SI = Children.begin(),
    243                                                          SE = Children.end();
    244          SI != SE; ++SI) {
    245       LexicalScope *ChildScope = *SI;
    246       if (!ChildScope->getDFSOut()) {
    247         WorkStack.push_back(ChildScope);
    248         visitedChildren = true;
    249         ChildScope->setDFSIn(++Counter);
    250         break;
    251       }
    252     }
    253     if (!visitedChildren) {
    254       WorkStack.pop_back();
    255       WS->setDFSOut(++Counter);
    256     }
    257   }
    258 }
    259 
    260 /// assignInstructionRanges - Find ranges of instructions covered by each
    261 /// lexical scope.
    262 void LexicalScopes::assignInstructionRanges(
    263     SmallVectorImpl<InsnRange> &MIRanges,
    264     DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {
    265 
    266   LexicalScope *PrevLexicalScope = nullptr;
    267   for (SmallVectorImpl<InsnRange>::const_iterator RI = MIRanges.begin(),
    268                                                   RE = MIRanges.end();
    269        RI != RE; ++RI) {
    270     const InsnRange &R = *RI;
    271     LexicalScope *S = MI2ScopeMap.lookup(R.first);
    272     assert(S && "Lost LexicalScope for a machine instruction!");
    273     if (PrevLexicalScope && !PrevLexicalScope->dominates(S))
    274       PrevLexicalScope->closeInsnRange(S);
    275     S->openInsnRange(R.first);
    276     S->extendInsnRange(R.second);
    277     PrevLexicalScope = S;
    278   }
    279 
    280   if (PrevLexicalScope)
    281     PrevLexicalScope->closeInsnRange();
    282 }
    283 
    284 /// getMachineBasicBlocks - Populate given set using machine basic blocks which
    285 /// have machine instructions that belong to lexical scope identified by
    286 /// DebugLoc.
    287 void LexicalScopes::getMachineBasicBlocks(
    288     DebugLoc DL, SmallPtrSet<const MachineBasicBlock *, 4> &MBBs) {
    289   MBBs.clear();
    290   LexicalScope *Scope = getOrCreateLexicalScope(DL);
    291   if (!Scope)
    292     return;
    293 
    294   if (Scope == CurrentFnLexicalScope) {
    295     for (const auto &MBB : *MF)
    296       MBBs.insert(&MBB);
    297     return;
    298   }
    299 
    300   SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges();
    301   for (SmallVectorImpl<InsnRange>::iterator I = InsnRanges.begin(),
    302                                             E = InsnRanges.end();
    303        I != E; ++I) {
    304     InsnRange &R = *I;
    305     MBBs.insert(R.first->getParent());
    306   }
    307 }
    308 
    309 /// dominates - Return true if DebugLoc's lexical scope dominates at least one
    310 /// machine instruction's lexical scope in a given machine basic block.
    311 bool LexicalScopes::dominates(DebugLoc DL, MachineBasicBlock *MBB) {
    312   LexicalScope *Scope = getOrCreateLexicalScope(DL);
    313   if (!Scope)
    314     return false;
    315 
    316   // Current function scope covers all basic blocks in the function.
    317   if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF)
    318     return true;
    319 
    320   bool Result = false;
    321   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
    322        ++I) {
    323     DebugLoc IDL = I->getDebugLoc();
    324     if (IDL.isUnknown())
    325       continue;
    326     if (LexicalScope *IScope = getOrCreateLexicalScope(IDL))
    327       if (Scope->dominates(IScope))
    328         return true;
    329   }
    330   return Result;
    331 }
    332 
    333 /// dump - Print data structures.
    334 void LexicalScope::dump(unsigned Indent) const {
    335 #ifndef NDEBUG
    336   raw_ostream &err = dbgs();
    337   err.indent(Indent);
    338   err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n";
    339   const MDNode *N = Desc;
    340   err.indent(Indent);
    341   N->dump();
    342   if (AbstractScope)
    343     err << std::string(Indent, ' ') << "Abstract Scope\n";
    344 
    345   if (!Children.empty())
    346     err << std::string(Indent + 2, ' ') << "Children ...\n";
    347   for (unsigned i = 0, e = Children.size(); i != e; ++i)
    348     if (Children[i] != this)
    349       Children[i]->dump(Indent + 2);
    350 #endif
    351 }
    352