LLVM API Documentation

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 #define DEBUG_TYPE "lexicalscopes"
00018 #include "llvm/CodeGen/LexicalScopes.h"
00019 #include "llvm/CodeGen/MachineFunction.h"
00020 #include "llvm/CodeGen/MachineInstr.h"
00021 #include "llvm/IR/DebugInfo.h"
00022 #include "llvm/IR/Function.h"
00023 #include "llvm/Support/Debug.h"
00024 #include "llvm/Support/ErrorHandling.h"
00025 #include "llvm/Support/FormattedStream.h"
00026 using namespace llvm;
00027 
00028 /// ~LexicalScopes - final cleanup after ourselves.
00029 LexicalScopes::~LexicalScopes() { reset(); }
00030 
00031 /// reset - Reset the instance so that it's prepared for another function.
00032 void LexicalScopes::reset() {
00033   MF = nullptr;
00034   CurrentFnLexicalScope = nullptr;
00035   DeleteContainerSeconds(LexicalScopeMap);
00036   DeleteContainerSeconds(AbstractScopeMap);
00037   InlinedLexicalScopeMap.clear();
00038   AbstractScopesList.clear();
00039 }
00040 
00041 /// initialize - Scan machine function and constuct lexical scope nest.
00042 void LexicalScopes::initialize(const MachineFunction &Fn) {
00043   reset();
00044   MF = &Fn;
00045   SmallVector<InsnRange, 4> MIRanges;
00046   DenseMap<const MachineInstr *, LexicalScope *> MI2ScopeMap;
00047   extractLexicalScopes(MIRanges, MI2ScopeMap);
00048   if (CurrentFnLexicalScope) {
00049     constructScopeNest(CurrentFnLexicalScope);
00050     assignInstructionRanges(MIRanges, MI2ScopeMap);
00051   }
00052 }
00053 
00054 /// extractLexicalScopes - Extract instruction ranges for each lexical scopes
00055 /// for the given machine function.
00056 void LexicalScopes::extractLexicalScopes(
00057     SmallVectorImpl<InsnRange> &MIRanges,
00058     DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {
00059 
00060   // Scan each instruction and create scopes. First build working set of scopes.
00061   for (MachineFunction::const_iterator I = MF->begin(), E = MF->end(); I != E;
00062        ++I) {
00063     const MachineInstr *RangeBeginMI = nullptr;
00064     const MachineInstr *PrevMI = nullptr;
00065     DebugLoc PrevDL;
00066     for (MachineBasicBlock::const_iterator II = I->begin(), IE = I->end();
00067          II != IE; ++II) {
00068       const MachineInstr *MInsn = II;
00069 
00070       // Check if instruction has valid location information.
00071       const DebugLoc MIDL = MInsn->getDebugLoc();
00072       if (MIDL.isUnknown()) {
00073         PrevMI = MInsn;
00074         continue;
00075       }
00076 
00077       // If scope has not changed then skip this instruction.
00078       if (MIDL == PrevDL) {
00079         PrevMI = MInsn;
00080         continue;
00081       }
00082 
00083       // Ignore DBG_VALUE. It does not contribute to any instruction in output.
00084       if (MInsn->isDebugValue())
00085         continue;
00086 
00087       if (RangeBeginMI) {
00088         // If we have already seen a beginning of an instruction range and
00089         // current instruction scope does not match scope of first instruction
00090         // in this range then create a new instruction range.
00091         InsnRange R(RangeBeginMI, PrevMI);
00092         MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
00093         MIRanges.push_back(R);
00094       }
00095 
00096       // This is a beginning of a new instruction range.
00097       RangeBeginMI = MInsn;
00098 
00099       // Reset previous markers.
00100       PrevMI = MInsn;
00101       PrevDL = MIDL;
00102     }
00103 
00104     // Create last instruction range.
00105     if (RangeBeginMI && PrevMI && !PrevDL.isUnknown()) {
00106       InsnRange R(RangeBeginMI, PrevMI);
00107       MIRanges.push_back(R);
00108       MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
00109     }
00110   }
00111 }
00112 
00113 /// findLexicalScope - Find lexical scope, either regular or inlined, for the
00114 /// given DebugLoc. Return NULL if not found.
00115 LexicalScope *LexicalScopes::findLexicalScope(DebugLoc DL) {
00116   MDNode *Scope = nullptr;
00117   MDNode *IA = nullptr;
00118   DL.getScopeAndInlinedAt(Scope, IA, MF->getFunction()->getContext());
00119   if (!Scope)
00120     return nullptr;
00121 
00122   // The scope that we were created with could have an extra file - which
00123   // isn't what we care about in this case.
00124   DIDescriptor D = DIDescriptor(Scope);
00125   if (D.isLexicalBlockFile())
00126     Scope = DILexicalBlockFile(Scope).getScope();
00127 
00128   if (IA)
00129     return InlinedLexicalScopeMap.lookup(DebugLoc::getFromDILocation(IA));
00130   return LexicalScopeMap.lookup(Scope);
00131 }
00132 
00133 /// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If
00134 /// not available then create new lexical scope.
00135 LexicalScope *LexicalScopes::getOrCreateLexicalScope(DebugLoc DL) {
00136   MDNode *Scope = nullptr;
00137   MDNode *InlinedAt = nullptr;
00138   DL.getScopeAndInlinedAt(Scope, InlinedAt, MF->getFunction()->getContext());
00139 
00140   if (InlinedAt) {
00141     // Create an abstract scope for inlined function.
00142     getOrCreateAbstractScope(Scope);
00143     // Create an inlined scope for inlined function.
00144     return getOrCreateInlinedScope(Scope, InlinedAt);
00145   }
00146 
00147   return getOrCreateRegularScope(Scope);
00148 }
00149 
00150 /// getOrCreateRegularScope - Find or create a regular lexical scope.
00151 LexicalScope *LexicalScopes::getOrCreateRegularScope(MDNode *Scope) {
00152   DIDescriptor D = DIDescriptor(Scope);
00153   if (D.isLexicalBlockFile()) {
00154     Scope = DILexicalBlockFile(Scope).getScope();
00155     D = DIDescriptor(Scope);
00156   }
00157 
00158   LexicalScope *WScope = LexicalScopeMap.lookup(Scope);
00159   if (WScope)
00160     return WScope;
00161 
00162   LexicalScope *Parent = nullptr;
00163   if (D.isLexicalBlock())
00164     Parent = getOrCreateLexicalScope(DebugLoc::getFromDILexicalBlock(Scope));
00165   WScope = new LexicalScope(Parent, DIDescriptor(Scope), nullptr, false);
00166   LexicalScopeMap.insert(std::make_pair(Scope, WScope));
00167   if (!Parent && DIDescriptor(Scope).isSubprogram() &&
00168       DISubprogram(Scope).describes(MF->getFunction()))
00169     CurrentFnLexicalScope = WScope;
00170 
00171   return WScope;
00172 }
00173 
00174 /// getOrCreateInlinedScope - Find or create an inlined lexical scope.
00175 LexicalScope *LexicalScopes::getOrCreateInlinedScope(MDNode *Scope,
00176                                                      MDNode *InlinedAt) {
00177   LexicalScope *InlinedScope = LexicalScopeMap.lookup(InlinedAt);
00178   if (InlinedScope)
00179     return InlinedScope;
00180 
00181   DebugLoc InlinedLoc = DebugLoc::getFromDILocation(InlinedAt);
00182   InlinedScope = new LexicalScope(getOrCreateLexicalScope(InlinedLoc),
00183                                   DIDescriptor(Scope), InlinedAt, false);
00184   InlinedLexicalScopeMap[InlinedLoc] = InlinedScope;
00185   LexicalScopeMap[InlinedAt] = InlinedScope;
00186   return InlinedScope;
00187 }
00188 
00189 /// getOrCreateAbstractScope - Find or create an abstract lexical scope.
00190 LexicalScope *LexicalScopes::getOrCreateAbstractScope(const MDNode *N) {
00191   assert(N && "Invalid Scope encoding!");
00192 
00193   DIDescriptor Scope(N);
00194   if (Scope.isLexicalBlockFile())
00195     Scope = DILexicalBlockFile(Scope).getScope();
00196   LexicalScope *AScope = AbstractScopeMap.lookup(N);
00197   if (AScope)
00198     return AScope;
00199 
00200   LexicalScope *Parent = nullptr;
00201   if (Scope.isLexicalBlock()) {
00202     DILexicalBlock DB(N);
00203     DIDescriptor ParentDesc = DB.getContext();
00204     Parent = getOrCreateAbstractScope(ParentDesc);
00205   }
00206   AScope = new LexicalScope(Parent, DIDescriptor(N), nullptr, true);
00207   AbstractScopeMap[N] = AScope;
00208   if (DIDescriptor(N).isSubprogram())
00209     AbstractScopesList.push_back(AScope);
00210   return AScope;
00211 }
00212 
00213 /// constructScopeNest
00214 void LexicalScopes::constructScopeNest(LexicalScope *Scope) {
00215   assert(Scope && "Unable to calculate scope dominance graph!");
00216   SmallVector<LexicalScope *, 4> WorkStack;
00217   WorkStack.push_back(Scope);
00218   unsigned Counter = 0;
00219   while (!WorkStack.empty()) {
00220     LexicalScope *WS = WorkStack.back();
00221     const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
00222     bool visitedChildren = false;
00223     for (SmallVectorImpl<LexicalScope *>::const_iterator SI = Children.begin(),
00224                                                          SE = Children.end();
00225          SI != SE; ++SI) {
00226       LexicalScope *ChildScope = *SI;
00227       if (!ChildScope->getDFSOut()) {
00228         WorkStack.push_back(ChildScope);
00229         visitedChildren = true;
00230         ChildScope->setDFSIn(++Counter);
00231         break;
00232       }
00233     }
00234     if (!visitedChildren) {
00235       WorkStack.pop_back();
00236       WS->setDFSOut(++Counter);
00237     }
00238   }
00239 }
00240 
00241 /// assignInstructionRanges - Find ranges of instructions covered by each
00242 /// lexical scope.
00243 void LexicalScopes::assignInstructionRanges(
00244     SmallVectorImpl<InsnRange> &MIRanges,
00245     DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {
00246 
00247   LexicalScope *PrevLexicalScope = nullptr;
00248   for (SmallVectorImpl<InsnRange>::const_iterator RI = MIRanges.begin(),
00249                                                   RE = MIRanges.end();
00250        RI != RE; ++RI) {
00251     const InsnRange &R = *RI;
00252     LexicalScope *S = MI2ScopeMap.lookup(R.first);
00253     assert(S && "Lost LexicalScope for a machine instruction!");
00254     if (PrevLexicalScope && !PrevLexicalScope->dominates(S))
00255       PrevLexicalScope->closeInsnRange(S);
00256     S->openInsnRange(R.first);
00257     S->extendInsnRange(R.second);
00258     PrevLexicalScope = S;
00259   }
00260 
00261   if (PrevLexicalScope)
00262     PrevLexicalScope->closeInsnRange();
00263 }
00264 
00265 /// getMachineBasicBlocks - Populate given set using machine basic blocks which
00266 /// have machine instructions that belong to lexical scope identified by
00267 /// DebugLoc.
00268 void LexicalScopes::getMachineBasicBlocks(
00269     DebugLoc DL, SmallPtrSet<const MachineBasicBlock *, 4> &MBBs) {
00270   MBBs.clear();
00271   LexicalScope *Scope = getOrCreateLexicalScope(DL);
00272   if (!Scope)
00273     return;
00274 
00275   if (Scope == CurrentFnLexicalScope) {
00276     for (MachineFunction::const_iterator I = MF->begin(), E = MF->end(); I != E;
00277          ++I)
00278       MBBs.insert(I);
00279     return;
00280   }
00281 
00282   SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges();
00283   for (SmallVectorImpl<InsnRange>::iterator I = InsnRanges.begin(),
00284                                             E = InsnRanges.end();
00285        I != E; ++I) {
00286     InsnRange &R = *I;
00287     MBBs.insert(R.first->getParent());
00288   }
00289 }
00290 
00291 /// dominates - Return true if DebugLoc's lexical scope dominates at least one
00292 /// machine instruction's lexical scope in a given machine basic block.
00293 bool LexicalScopes::dominates(DebugLoc DL, MachineBasicBlock *MBB) {
00294   LexicalScope *Scope = getOrCreateLexicalScope(DL);
00295   if (!Scope)
00296     return false;
00297 
00298   // Current function scope covers all basic blocks in the function.
00299   if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF)
00300     return true;
00301 
00302   bool Result = false;
00303   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
00304        ++I) {
00305     DebugLoc IDL = I->getDebugLoc();
00306     if (IDL.isUnknown())
00307       continue;
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 }