LLVM  mainline
LexicalScopes.cpp
Go to the documentation of this file.
00001 //===- LexicalScopes.cpp - Collecting lexical scope info ------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements LexicalScopes analysis.
00011 //
00012 // This pass collects lexical scope information and maps machine instructions
00013 // to respective lexical scopes.
00014 //
00015 //===----------------------------------------------------------------------===//
00016 
00017 #include "llvm/CodeGen/LexicalScopes.h"
00018 #include "llvm/CodeGen/MachineFunction.h"
00019 #include "llvm/CodeGen/MachineInstr.h"
00020 #include "llvm/IR/DebugInfo.h"
00021 #include "llvm/IR/Function.h"
00022 #include "llvm/Support/Debug.h"
00023 #include "llvm/Support/ErrorHandling.h"
00024 #include "llvm/Support/FormattedStream.h"
00025 using namespace llvm;
00026 
00027 #define DEBUG_TYPE "lexicalscopes"
00028 
00029 /// reset - Reset the instance so that it's prepared for another function.
00030 void LexicalScopes::reset() {
00031   MF = nullptr;
00032   CurrentFnLexicalScope = nullptr;
00033   LexicalScopeMap.clear();
00034   AbstractScopeMap.clear();
00035   InlinedLexicalScopeMap.clear();
00036   AbstractScopesList.clear();
00037 }
00038 
00039 /// initialize - Scan machine function and constuct lexical scope nest.
00040 void LexicalScopes::initialize(const MachineFunction &Fn) {
00041   reset();
00042   MF = &Fn;
00043   SmallVector<InsnRange, 4> MIRanges;
00044   DenseMap<const MachineInstr *, LexicalScope *> MI2ScopeMap;
00045   extractLexicalScopes(MIRanges, MI2ScopeMap);
00046   if (CurrentFnLexicalScope) {
00047     constructScopeNest(CurrentFnLexicalScope);
00048     assignInstructionRanges(MIRanges, MI2ScopeMap);
00049   }
00050 }
00051 
00052 /// extractLexicalScopes - Extract instruction ranges for each lexical scopes
00053 /// for the given machine function.
00054 void LexicalScopes::extractLexicalScopes(
00055     SmallVectorImpl<InsnRange> &MIRanges,
00056     DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {
00057 
00058   // Scan each instruction and create scopes. First build working set of scopes.
00059   for (const auto &MBB : *MF) {
00060     const MachineInstr *RangeBeginMI = nullptr;
00061     const MachineInstr *PrevMI = nullptr;
00062     const MDLocation *PrevDL = nullptr;
00063     for (const auto &MInsn : MBB) {
00064       // Check if instruction has valid location information.
00065       const MDLocation *MIDL = MInsn.getDebugLoc();
00066       if (!MIDL) {
00067         PrevMI = &MInsn;
00068         continue;
00069       }
00070 
00071       // If scope has not changed then skip this instruction.
00072       if (MIDL == PrevDL) {
00073         PrevMI = &MInsn;
00074         continue;
00075       }
00076 
00077       // Ignore DBG_VALUE. It does not contribute to any instruction in output.
00078       if (MInsn.isDebugValue())
00079         continue;
00080 
00081       if (RangeBeginMI) {
00082         // If we have already seen a beginning of an instruction range and
00083         // current instruction scope does not match scope of first instruction
00084         // in this range then create a new instruction range.
00085         InsnRange R(RangeBeginMI, PrevMI);
00086         MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
00087         MIRanges.push_back(R);
00088       }
00089 
00090       // This is a beginning of a new instruction range.
00091       RangeBeginMI = &MInsn;
00092 
00093       // Reset previous markers.
00094       PrevMI = &MInsn;
00095       PrevDL = MIDL;
00096     }
00097 
00098     // Create last instruction range.
00099     if (RangeBeginMI && PrevMI && PrevDL) {
00100       InsnRange R(RangeBeginMI, PrevMI);
00101       MIRanges.push_back(R);
00102       MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
00103     }
00104   }
00105 }
00106 
00107 /// findLexicalScope - Find lexical scope, either regular or inlined, for the
00108 /// given DebugLoc. Return NULL if not found.
00109 LexicalScope *LexicalScopes::findLexicalScope(const MDLocation *DL) {
00110   MDLocalScope *Scope = DL->getScope();
00111   if (!Scope)
00112     return nullptr;
00113 
00114   // The scope that we were created with could have an extra file - which
00115   // isn't what we care about in this case.
00116   if (auto *File = dyn_cast<MDLexicalBlockFile>(Scope))
00117     Scope = File->getScope();
00118 
00119   if (auto *IA = DL->getInlinedAt()) {
00120     auto I = InlinedLexicalScopeMap.find(std::make_pair(Scope, IA));
00121     return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr;
00122   }
00123   return findLexicalScope(Scope);
00124 }
00125 
00126 /// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If
00127 /// not available then create new lexical scope.
00128 LexicalScope *LexicalScopes::getOrCreateLexicalScope(const MDLocalScope *Scope,
00129                                                      const MDLocation *IA) {
00130   if (IA) {
00131     // Create an abstract scope for inlined function.
00132     getOrCreateAbstractScope(Scope);
00133     // Create an inlined scope for inlined function.
00134     return getOrCreateInlinedScope(Scope, IA);
00135   }
00136 
00137   return getOrCreateRegularScope(Scope);
00138 }
00139 
00140 /// getOrCreateRegularScope - Find or create a regular lexical scope.
00141 LexicalScope *
00142 LexicalScopes::getOrCreateRegularScope(const MDLocalScope *Scope) {
00143   if (auto *File = dyn_cast<MDLexicalBlockFile>(Scope))
00144     Scope = File->getScope();
00145 
00146   auto I = LexicalScopeMap.find(Scope);
00147   if (I != LexicalScopeMap.end())
00148     return &I->second;
00149 
00150   // FIXME: Should the following dyn_cast be MDLexicalBlock?
00151   LexicalScope *Parent = nullptr;
00152   if (auto *Block = dyn_cast<MDLexicalBlockBase>(Scope))
00153     Parent = getOrCreateLexicalScope(Block->getScope());
00154   I = LexicalScopeMap.emplace(std::piecewise_construct,
00155                               std::forward_as_tuple(Scope),
00156                               std::forward_as_tuple(Parent, Scope, nullptr,
00157                                                     false)).first;
00158 
00159   if (!Parent) {
00160     assert(DIDescriptor(Scope).isSubprogram());
00161     assert(DISubprogram(Scope).describes(MF->getFunction()));
00162     assert(!CurrentFnLexicalScope);
00163     CurrentFnLexicalScope = &I->second;
00164   }
00165 
00166   return &I->second;
00167 }
00168 
00169 /// getOrCreateInlinedScope - Find or create an inlined lexical scope.
00170 LexicalScope *
00171 LexicalScopes::getOrCreateInlinedScope(const MDLocalScope *Scope,
00172                                        const MDLocation *InlinedAt) {
00173   std::pair<const MDLocalScope *, const MDLocation *> P(Scope, InlinedAt);
00174   auto I = InlinedLexicalScopeMap.find(P);
00175   if (I != InlinedLexicalScopeMap.end())
00176     return &I->second;
00177 
00178   LexicalScope *Parent;
00179   if (auto *Block = dyn_cast<MDLexicalBlockBase>(Scope))
00180     Parent = getOrCreateInlinedScope(Block->getScope(), InlinedAt);
00181   else
00182     Parent = getOrCreateLexicalScope(InlinedAt);
00183 
00184   I = InlinedLexicalScopeMap.emplace(std::piecewise_construct,
00185                                      std::forward_as_tuple(P),
00186                                      std::forward_as_tuple(Parent, Scope,
00187                                                            InlinedAt, false))
00188           .first;
00189   return &I->second;
00190 }
00191 
00192 /// getOrCreateAbstractScope - Find or create an abstract lexical scope.
00193 LexicalScope *
00194 LexicalScopes::getOrCreateAbstractScope(const MDLocalScope *Scope) {
00195   assert(Scope && "Invalid Scope encoding!");
00196 
00197   if (auto *File = dyn_cast<MDLexicalBlockFile>(Scope))
00198     Scope = File->getScope();
00199   auto I = AbstractScopeMap.find(Scope);
00200   if (I != AbstractScopeMap.end())
00201     return &I->second;
00202 
00203   // FIXME: Should the following isa be MDLexicalBlock?
00204   LexicalScope *Parent = nullptr;
00205   if (auto *Block = dyn_cast<MDLexicalBlockBase>(Scope))
00206     Parent = getOrCreateAbstractScope(Block->getScope());
00207 
00208   I = AbstractScopeMap.emplace(std::piecewise_construct,
00209                                std::forward_as_tuple(Scope),
00210                                std::forward_as_tuple(Parent, Scope,
00211                                                      nullptr, true)).first;
00212   if (isa<MDSubprogram>(Scope))
00213     AbstractScopesList.push_back(&I->second);
00214   return &I->second;
00215 }
00216 
00217 /// constructScopeNest
00218 void LexicalScopes::constructScopeNest(LexicalScope *Scope) {
00219   assert(Scope && "Unable to calculate scope dominance graph!");
00220   SmallVector<LexicalScope *, 4> WorkStack;
00221   WorkStack.push_back(Scope);
00222   unsigned Counter = 0;
00223   while (!WorkStack.empty()) {
00224     LexicalScope *WS = WorkStack.back();
00225     const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
00226     bool visitedChildren = false;
00227     for (SmallVectorImpl<LexicalScope *>::const_iterator SI = Children.begin(),
00228                                                          SE = Children.end();
00229          SI != SE; ++SI) {
00230       LexicalScope *ChildScope = *SI;
00231       if (!ChildScope->getDFSOut()) {
00232         WorkStack.push_back(ChildScope);
00233         visitedChildren = true;
00234         ChildScope->setDFSIn(++Counter);
00235         break;
00236       }
00237     }
00238     if (!visitedChildren) {
00239       WorkStack.pop_back();
00240       WS->setDFSOut(++Counter);
00241     }
00242   }
00243 }
00244 
00245 /// assignInstructionRanges - Find ranges of instructions covered by each
00246 /// lexical scope.
00247 void LexicalScopes::assignInstructionRanges(
00248     SmallVectorImpl<InsnRange> &MIRanges,
00249     DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {
00250 
00251   LexicalScope *PrevLexicalScope = nullptr;
00252   for (SmallVectorImpl<InsnRange>::const_iterator RI = MIRanges.begin(),
00253                                                   RE = MIRanges.end();
00254        RI != RE; ++RI) {
00255     const InsnRange &R = *RI;
00256     LexicalScope *S = MI2ScopeMap.lookup(R.first);
00257     assert(S && "Lost LexicalScope for a machine instruction!");
00258     if (PrevLexicalScope && !PrevLexicalScope->dominates(S))
00259       PrevLexicalScope->closeInsnRange(S);
00260     S->openInsnRange(R.first);
00261     S->extendInsnRange(R.second);
00262     PrevLexicalScope = S;
00263   }
00264 
00265   if (PrevLexicalScope)
00266     PrevLexicalScope->closeInsnRange();
00267 }
00268 
00269 /// getMachineBasicBlocks - Populate given set using machine basic blocks which
00270 /// have machine instructions that belong to lexical scope identified by
00271 /// DebugLoc.
00272 void LexicalScopes::getMachineBasicBlocks(
00273     const MDLocation *DL, SmallPtrSetImpl<const MachineBasicBlock *> &MBBs) {
00274   MBBs.clear();
00275   LexicalScope *Scope = getOrCreateLexicalScope(DL);
00276   if (!Scope)
00277     return;
00278 
00279   if (Scope == CurrentFnLexicalScope) {
00280     for (const auto &MBB : *MF)
00281       MBBs.insert(&MBB);
00282     return;
00283   }
00284 
00285   SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges();
00286   for (SmallVectorImpl<InsnRange>::iterator I = InsnRanges.begin(),
00287                                             E = InsnRanges.end();
00288        I != E; ++I) {
00289     InsnRange &R = *I;
00290     MBBs.insert(R.first->getParent());
00291   }
00292 }
00293 
00294 /// dominates - Return true if DebugLoc's lexical scope dominates at least one
00295 /// machine instruction's lexical scope in a given machine basic block.
00296 bool LexicalScopes::dominates(const MDLocation *DL, MachineBasicBlock *MBB) {
00297   LexicalScope *Scope = getOrCreateLexicalScope(DL);
00298   if (!Scope)
00299     return false;
00300 
00301   // Current function scope covers all basic blocks in the function.
00302   if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF)
00303     return true;
00304 
00305   bool Result = false;
00306   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
00307        ++I) {
00308     if (const MDLocation *IDL = I->getDebugLoc())
00309       if (LexicalScope *IScope = getOrCreateLexicalScope(IDL))
00310         if (Scope->dominates(IScope))
00311           return true;
00312   }
00313   return Result;
00314 }
00315 
00316 /// dump - Print data structures.
00317 void LexicalScope::dump(unsigned Indent) const {
00318 #ifndef NDEBUG
00319   raw_ostream &err = dbgs();
00320   err.indent(Indent);
00321   err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n";
00322   const MDNode *N = Desc;
00323   err.indent(Indent);
00324   N->dump();
00325   if (AbstractScope)
00326     err << std::string(Indent, ' ') << "Abstract Scope\n";
00327 
00328   if (!Children.empty())
00329     err << std::string(Indent + 2, ' ') << "Children ...\n";
00330   for (unsigned i = 0, e = Children.size(); i != e; ++i)
00331     if (Children[i] != this)
00332       Children[i]->dump(Indent + 2);
00333 #endif
00334 }