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(cast<MDSubprogram>(Scope)->describes(MF->getFunction()));
00161     assert(!CurrentFnLexicalScope);
00162     CurrentFnLexicalScope = &I->second;
00163   }
00164 
00165   return &I->second;
00166 }
00167 
00168 /// getOrCreateInlinedScope - Find or create an inlined lexical scope.
00169 LexicalScope *
00170 LexicalScopes::getOrCreateInlinedScope(const MDLocalScope *Scope,
00171                                        const MDLocation *InlinedAt) {
00172   std::pair<const MDLocalScope *, const MDLocation *> P(Scope, InlinedAt);
00173   auto I = InlinedLexicalScopeMap.find(P);
00174   if (I != InlinedLexicalScopeMap.end())
00175     return &I->second;
00176 
00177   LexicalScope *Parent;
00178   if (auto *Block = dyn_cast<MDLexicalBlockBase>(Scope))
00179     Parent = getOrCreateInlinedScope(Block->getScope(), InlinedAt);
00180   else
00181     Parent = getOrCreateLexicalScope(InlinedAt);
00182 
00183   I = InlinedLexicalScopeMap.emplace(std::piecewise_construct,
00184                                      std::forward_as_tuple(P),
00185                                      std::forward_as_tuple(Parent, Scope,
00186                                                            InlinedAt, false))
00187           .first;
00188   return &I->second;
00189 }
00190 
00191 /// getOrCreateAbstractScope - Find or create an abstract lexical scope.
00192 LexicalScope *
00193 LexicalScopes::getOrCreateAbstractScope(const MDLocalScope *Scope) {
00194   assert(Scope && "Invalid Scope encoding!");
00195 
00196   if (auto *File = dyn_cast<MDLexicalBlockFile>(Scope))
00197     Scope = File->getScope();
00198   auto I = AbstractScopeMap.find(Scope);
00199   if (I != AbstractScopeMap.end())
00200     return &I->second;
00201 
00202   // FIXME: Should the following isa be MDLexicalBlock?
00203   LexicalScope *Parent = nullptr;
00204   if (auto *Block = dyn_cast<MDLexicalBlockBase>(Scope))
00205     Parent = getOrCreateAbstractScope(Block->getScope());
00206 
00207   I = AbstractScopeMap.emplace(std::piecewise_construct,
00208                                std::forward_as_tuple(Scope),
00209                                std::forward_as_tuple(Parent, Scope,
00210                                                      nullptr, true)).first;
00211   if (isa<MDSubprogram>(Scope))
00212     AbstractScopesList.push_back(&I->second);
00213   return &I->second;
00214 }
00215 
00216 /// constructScopeNest
00217 void LexicalScopes::constructScopeNest(LexicalScope *Scope) {
00218   assert(Scope && "Unable to calculate scope dominance graph!");
00219   SmallVector<LexicalScope *, 4> WorkStack;
00220   WorkStack.push_back(Scope);
00221   unsigned Counter = 0;
00222   while (!WorkStack.empty()) {
00223     LexicalScope *WS = WorkStack.back();
00224     const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
00225     bool visitedChildren = false;
00226     for (SmallVectorImpl<LexicalScope *>::const_iterator SI = Children.begin(),
00227                                                          SE = Children.end();
00228          SI != SE; ++SI) {
00229       LexicalScope *ChildScope = *SI;
00230       if (!ChildScope->getDFSOut()) {
00231         WorkStack.push_back(ChildScope);
00232         visitedChildren = true;
00233         ChildScope->setDFSIn(++Counter);
00234         break;
00235       }
00236     }
00237     if (!visitedChildren) {
00238       WorkStack.pop_back();
00239       WS->setDFSOut(++Counter);
00240     }
00241   }
00242 }
00243 
00244 /// assignInstructionRanges - Find ranges of instructions covered by each
00245 /// lexical scope.
00246 void LexicalScopes::assignInstructionRanges(
00247     SmallVectorImpl<InsnRange> &MIRanges,
00248     DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {
00249 
00250   LexicalScope *PrevLexicalScope = nullptr;
00251   for (SmallVectorImpl<InsnRange>::const_iterator RI = MIRanges.begin(),
00252                                                   RE = MIRanges.end();
00253        RI != RE; ++RI) {
00254     const InsnRange &R = *RI;
00255     LexicalScope *S = MI2ScopeMap.lookup(R.first);
00256     assert(S && "Lost LexicalScope for a machine instruction!");
00257     if (PrevLexicalScope && !PrevLexicalScope->dominates(S))
00258       PrevLexicalScope->closeInsnRange(S);
00259     S->openInsnRange(R.first);
00260     S->extendInsnRange(R.second);
00261     PrevLexicalScope = S;
00262   }
00263 
00264   if (PrevLexicalScope)
00265     PrevLexicalScope->closeInsnRange();
00266 }
00267 
00268 /// getMachineBasicBlocks - Populate given set using machine basic blocks which
00269 /// have machine instructions that belong to lexical scope identified by
00270 /// DebugLoc.
00271 void LexicalScopes::getMachineBasicBlocks(
00272     const MDLocation *DL, SmallPtrSetImpl<const MachineBasicBlock *> &MBBs) {
00273   MBBs.clear();
00274   LexicalScope *Scope = getOrCreateLexicalScope(DL);
00275   if (!Scope)
00276     return;
00277 
00278   if (Scope == CurrentFnLexicalScope) {
00279     for (const auto &MBB : *MF)
00280       MBBs.insert(&MBB);
00281     return;
00282   }
00283 
00284   SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges();
00285   for (SmallVectorImpl<InsnRange>::iterator I = InsnRanges.begin(),
00286                                             E = InsnRanges.end();
00287        I != E; ++I) {
00288     InsnRange &R = *I;
00289     MBBs.insert(R.first->getParent());
00290   }
00291 }
00292 
00293 /// dominates - Return true if DebugLoc's lexical scope dominates at least one
00294 /// machine instruction's lexical scope in a given machine basic block.
00295 bool LexicalScopes::dominates(const MDLocation *DL, MachineBasicBlock *MBB) {
00296   LexicalScope *Scope = getOrCreateLexicalScope(DL);
00297   if (!Scope)
00298     return false;
00299 
00300   // Current function scope covers all basic blocks in the function.
00301   if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF)
00302     return true;
00303 
00304   bool Result = false;
00305   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
00306        ++I) {
00307     if (const MDLocation *IDL = I->getDebugLoc())
00308       if (LexicalScope *IScope = getOrCreateLexicalScope(IDL))
00309         if (Scope->dominates(IScope))
00310           return true;
00311   }
00312   return Result;
00313 }
00314 
00315 /// dump - Print data structures.
00316 void LexicalScope::dump(unsigned Indent) const {
00317 #ifndef NDEBUG
00318   raw_ostream &err = dbgs();
00319   err.indent(Indent);
00320   err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n";
00321   const MDNode *N = Desc;
00322   err.indent(Indent);
00323   N->dump();
00324   if (AbstractScope)
00325     err << std::string(Indent, ' ') << "Abstract Scope\n";
00326 
00327   if (!Children.empty())
00328     err << std::string(Indent + 2, ' ') << "Children ...\n";
00329   for (unsigned i = 0, e = Children.size(); i != e; ++i)
00330     if (Children[i] != this)
00331       Children[i]->dump(Indent + 2);
00332 #endif
00333 }