From 103b8e653c981fe916b855f1b96cb35e01c4543e Mon Sep 17 00:00:00 2001 From: Devang Patel Date: Wed, 10 Aug 2011 19:04:06 +0000 Subject: Provide utility to extract and use lexical scoping information from machine instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137237 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/LexicalScopes.cpp | 305 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 305 insertions(+) create mode 100644 lib/CodeGen/LexicalScopes.cpp (limited to 'lib/CodeGen/LexicalScopes.cpp') diff --git a/lib/CodeGen/LexicalScopes.cpp b/lib/CodeGen/LexicalScopes.cpp new file mode 100644 index 0000000..2276004 --- /dev/null +++ b/lib/CodeGen/LexicalScopes.cpp @@ -0,0 +1,305 @@ +//===- LexicalScopes.cpp - Collecting lexical scope info ------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements LexicalScopes analysis. +// +// This pass collects lexical scope information and maps machine instructions +// to respective lexical scopes. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "lexicalscopes" +#include "llvm/CodeGen/LexicalScopes.h" +#include "llvm/Function.h" +#include "llvm/Analysis/DebugInfo.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/FormattedStream.h" +using namespace llvm; + +LexicalScopes::~LexicalScopes() { + releaseMemory(); +} + +/// releaseMemory - release memory. +void LexicalScopes::releaseMemory() { + MF = NULL; + CurrentFnLexicalScope = NULL; + DeleteContainerSeconds(LexicalScopeMap); + DeleteContainerSeconds(AbstractScopeMap); + InlinedLexicalScopeMap.clear(); + AbstractScopesList.clear(); +} + +/// initialize - Scan machine function and constuct lexical scope nest. +void LexicalScopes::initialize(const MachineFunction &Fn) { + releaseMemory(); + MF = &Fn; + SmallVector MIRanges; + DenseMap MI2ScopeMap; + extractLexicalScopes(MIRanges, MI2ScopeMap); + if (CurrentFnLexicalScope) { + constructScopeNest(CurrentFnLexicalScope); + assignInstructionRanges(MIRanges, MI2ScopeMap); + } +} + +/// extractLexicalScopes - Extract instruction ranges for each lexical scopes +/// for the given machine function. +void LexicalScopes:: +extractLexicalScopes(SmallVectorImpl &MIRanges, + DenseMap &MI2ScopeMap) { + + // Scan each instruction and create scopes. First build working set of scopes. + for (MachineFunction::const_iterator I = MF->begin(), E = MF->end(); + I != E; ++I) { + const MachineInstr *RangeBeginMI = NULL; + const MachineInstr *PrevMI = NULL; + DebugLoc PrevDL; + for (MachineBasicBlock::const_iterator II = I->begin(), IE = I->end(); + II != IE; ++II) { + const MachineInstr *MInsn = II; + + // Check if instruction has valid location information. + const DebugLoc MIDL = MInsn->getDebugLoc(); + if (MIDL.isUnknown()) { + PrevMI = MInsn; + continue; + } + + // If scope has not changed then skip this instruction. + if (MIDL == PrevDL) { + PrevMI = MInsn; + continue; + } + + // Ignore DBG_VALUE. It does not contribute to any instruction in output. + if (MInsn->isDebugValue()) + continue; + + if (RangeBeginMI) { + // If we have already seen a beginning of an instruction range and + // current instruction scope does not match scope of first instruction + // in this range then create a new instruction range. + InsnRange R(RangeBeginMI, PrevMI); + MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL); + MIRanges.push_back(R); + } + + // This is a beginning of a new instruction range. + RangeBeginMI = MInsn; + + // Reset previous markers. + PrevMI = MInsn; + PrevDL = MIDL; + } + + // Create last instruction range. + if (RangeBeginMI && PrevMI && !PrevDL.isUnknown()) { + InsnRange R(RangeBeginMI, PrevMI); + MIRanges.push_back(R); + MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL); + } + } +} + +/// findLexicalScope - Find lexical scope, either regular or inlined, for the +/// given DebugLoc. Return NULL if not found. +LexicalScope *LexicalScopes::findLexicalScope(DebugLoc DL) { + MDNode *Scope = NULL; + MDNode *IA = NULL; + DL.getScopeAndInlinedAt(Scope, IA, MF->getFunction()->getContext()); + if (!Scope) return NULL; + if (IA) + return InlinedLexicalScopeMap.lookup(DebugLoc::getFromDILocation(IA)); + return LexicalScopeMap.lookup(DL.getScope(Scope->getContext())); +} + +/// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If +/// not available then create new lexical scope. +LexicalScope *LexicalScopes::getOrCreateLexicalScope(DebugLoc DL) { + MDNode *Scope = NULL; + MDNode *InlinedAt = NULL; + DL.getScopeAndInlinedAt(Scope, InlinedAt, MF->getFunction()->getContext()); + if (InlinedAt) { + // Create an abstract scope for inlined function. + getOrCreateAbstractScope(Scope); + // Create an inlined scope for inlined function. + return getOrCreateInlinedScope(Scope, InlinedAt); + } + + return getOrCreateRegularScope(Scope); +} + +/// getOrCreateRegularScope - Find or create a regular lexical scope. +LexicalScope *LexicalScopes::getOrCreateRegularScope(MDNode *Scope) { + LexicalScope *WScope = LexicalScopeMap.lookup(Scope); + if (WScope) + return WScope; + + LexicalScope *Parent = NULL; + if (DIDescriptor(Scope).isLexicalBlock()) + Parent = getOrCreateLexicalScope(DebugLoc::getFromDILexicalBlock(Scope)); + WScope = new LexicalScope(Parent, DIDescriptor(Scope), NULL, false); + LexicalScopeMap.insert(std::make_pair(Scope, WScope)); + if (!Parent && DIDescriptor(Scope).isSubprogram() + && DISubprogram(Scope).describes(MF->getFunction())) + CurrentFnLexicalScope = WScope; + + return WScope; +} + +/// getOrCreateInlinedScope - Find or create an inlined lexical scope. +LexicalScope *LexicalScopes::getOrCreateInlinedScope(MDNode *Scope, + MDNode *InlinedAt) { + LexicalScope *InlinedScope = LexicalScopeMap.lookup(InlinedAt); + if (InlinedScope) + return InlinedScope; + + DebugLoc InlinedLoc = DebugLoc::getFromDILocation(InlinedAt); + InlinedScope = new LexicalScope(getOrCreateLexicalScope(InlinedLoc), + DIDescriptor(Scope), InlinedAt, false); + InlinedLexicalScopeMap[InlinedLoc] = InlinedScope; + LexicalScopeMap[InlinedAt] = InlinedScope; + return InlinedScope; +} + +/// getOrCreateAbstractScope - Find or create an abstract lexical scope. +LexicalScope *LexicalScopes::getOrCreateAbstractScope(const MDNode *N) { + assert(N && "Invalid Scope encoding!"); + + LexicalScope *AScope = AbstractScopeMap.lookup(N); + if (AScope) + return AScope; + + LexicalScope *Parent = NULL; + DIDescriptor Scope(N); + if (Scope.isLexicalBlock()) { + DILexicalBlock DB(N); + DIDescriptor ParentDesc = DB.getContext(); + Parent = getOrCreateAbstractScope(ParentDesc); + } + AScope = new LexicalScope(Parent, DIDescriptor(N), NULL, true); + AbstractScopeMap[N] = AScope; + if (DIDescriptor(N).isSubprogram()) + AbstractScopesList.push_back(AScope); + return AScope; +} + +/// constructScopeNest +void LexicalScopes::constructScopeNest(LexicalScope *Scope) { + assert (Scope && "Unable to calculate scop edominance graph!"); + SmallVector WorkStack; + WorkStack.push_back(Scope); + unsigned Counter = 0; + while (!WorkStack.empty()) { + LexicalScope *WS = WorkStack.back(); + const SmallVector &Children = WS->getChildren(); + bool visitedChildren = false; + for (SmallVector::const_iterator SI = Children.begin(), + SE = Children.end(); SI != SE; ++SI) { + LexicalScope *ChildScope = *SI; + if (!ChildScope->getDFSOut()) { + WorkStack.push_back(ChildScope); + visitedChildren = true; + ChildScope->setDFSIn(++Counter); + break; + } + } + if (!visitedChildren) { + WorkStack.pop_back(); + WS->setDFSOut(++Counter); + } + } +} + +/// assignInstructionRanges - Find ranges of instructions covered by each lexical +/// scope. +void LexicalScopes:: +assignInstructionRanges(SmallVectorImpl &MIRanges, + DenseMap &MI2ScopeMap) { + + LexicalScope *PrevLexicalScope = NULL; + for (SmallVectorImpl::const_iterator RI = MIRanges.begin(), + RE = MIRanges.end(); RI != RE; ++RI) { + const InsnRange &R = *RI; + LexicalScope *S = MI2ScopeMap.lookup(R.first); + assert (S && "Lost LexicalScope for a machine instruction!"); + if (PrevLexicalScope && !PrevLexicalScope->dominates(S)) + PrevLexicalScope->closeInsnRange(S); + S->openInsnRange(R.first); + S->extendInsnRange(R.second); + PrevLexicalScope = S; + } + + if (PrevLexicalScope) + PrevLexicalScope->closeInsnRange(); +} + +/// getMachineBasicBlocks - Populate given set using machine basic blocks which +/// have machine instructions that belong to lexical scope identified by +/// DebugLoc. +void LexicalScopes:: +getMachineBasicBlocks(DebugLoc DL, SmallPtrSet &MBBs) { + MBBs.clear(); + LexicalScope *Scope = getOrCreateLexicalScope(DL); + if (!Scope) + return; + + SmallVector &InsnRanges = Scope->getRanges(); + for (SmallVector::iterator I = InsnRanges.begin(), + E = InsnRanges.end(); I != E; ++I) { + InsnRange &R = *I; + MBBs.insert(R.first->getParent()); + } +} + +/// dominates - Return true if DebugLoc's lexical scope dominates at least one +/// machine instruction's lexical scope in a given machine basic block. +bool LexicalScopes::dominates(DebugLoc DL, MachineBasicBlock *MBB) { + LexicalScope *Scope = getOrCreateLexicalScope(DL); + if (!Scope) + return false; + bool Result = false; + for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); + I != E; ++I) { + DebugLoc IDL = I->getDebugLoc(); + if (IDL.isUnknown()) + continue; + if (LexicalScope *IScope = getOrCreateLexicalScope(IDL)) + if (Scope->dominates(IScope)) + return true; + } + return Result; +} + +/// dump - Print data structures. +void LexicalScope::dump() const { +#ifndef NDEBUG + raw_ostream &err = dbgs(); + err.indent(IndentLevel); + err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n"; + const MDNode *N = Desc; + N->dump(); + if (AbstractScope) + err << "Abstract Scope\n"; + + IndentLevel += 2; + if (!Children.empty()) + err << "Children ...\n"; + for (unsigned i = 0, e = Children.size(); i != e; ++i) + if (Children[i] != this) + Children[i]->dump(); + + IndentLevel -= 2; +#endif +} + -- cgit v1.1 From 5bc942cc3cc970836d48d8ad276ef3b2b1120ffc Mon Sep 17 00:00:00 2001 From: Devang Patel Date: Wed, 10 Aug 2011 23:58:09 +0000 Subject: Stay within 80 columns. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137283 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/LexicalScopes.cpp | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) (limited to 'lib/CodeGen/LexicalScopes.cpp') diff --git a/lib/CodeGen/LexicalScopes.cpp b/lib/CodeGen/LexicalScopes.cpp index 2276004..6763284 100644 --- a/lib/CodeGen/LexicalScopes.cpp +++ b/lib/CodeGen/LexicalScopes.cpp @@ -221,11 +221,12 @@ void LexicalScopes::constructScopeNest(LexicalScope *Scope) { } } -/// assignInstructionRanges - Find ranges of instructions covered by each lexical -/// scope. +/// assignInstructionRanges - Find ranges of instructions covered by each +/// lexical scope. void LexicalScopes:: assignInstructionRanges(SmallVectorImpl &MIRanges, - DenseMap &MI2ScopeMap) { + DenseMap &MI2ScopeMap) +{ LexicalScope *PrevLexicalScope = NULL; for (SmallVectorImpl::const_iterator RI = MIRanges.begin(), @@ -248,7 +249,8 @@ assignInstructionRanges(SmallVectorImpl &MIRanges, /// have machine instructions that belong to lexical scope identified by /// DebugLoc. void LexicalScopes:: -getMachineBasicBlocks(DebugLoc DL, SmallPtrSet &MBBs) { +getMachineBasicBlocks(DebugLoc DL, + SmallPtrSet &MBBs) { MBBs.clear(); LexicalScope *Scope = getOrCreateLexicalScope(DL); if (!Scope) -- cgit v1.1 From 2e85b1bfa7412577dd61f21ea10a686d3685144b Mon Sep 17 00:00:00 2001 From: Devang Patel Date: Fri, 12 Aug 2011 18:01:34 +0000 Subject: Provide fast path as Jakob suggested. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137478 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/LexicalScopes.cpp | 12 ++++++++++++ 1 file changed, 12 insertions(+) (limited to 'lib/CodeGen/LexicalScopes.cpp') diff --git a/lib/CodeGen/LexicalScopes.cpp b/lib/CodeGen/LexicalScopes.cpp index 6763284..ae06a40 100644 --- a/lib/CodeGen/LexicalScopes.cpp +++ b/lib/CodeGen/LexicalScopes.cpp @@ -256,6 +256,13 @@ getMachineBasicBlocks(DebugLoc DL, if (!Scope) return; + if (Scope == CurrentFnLexicalScope) { + for (MachineFunction::const_iterator I = MF->begin(), E = MF->end(); + I != E; ++I) + MBBs.insert(I); + return; + } + SmallVector &InsnRanges = Scope->getRanges(); for (SmallVector::iterator I = InsnRanges.begin(), E = InsnRanges.end(); I != E; ++I) { @@ -270,6 +277,11 @@ bool LexicalScopes::dominates(DebugLoc DL, MachineBasicBlock *MBB) { LexicalScope *Scope = getOrCreateLexicalScope(DL); if (!Scope) return false; + + // Current function scope covers all basic blocks in the function. + if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF) + return true; + bool Result = false; for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ++I) { -- cgit v1.1 From 6618a241f7ba2571a1a55b3733c4441d467baf42 Mon Sep 17 00:00:00 2001 From: Eric Christopher Date: Tue, 11 Oct 2011 22:59:11 +0000 Subject: Add a new wrapper node for a DILexicalBlock that encapsulates it and a file. Since it should only be used when necessary propagate it through the backend code generation and tweak testcases accordingly. This helps with code like in clang's test/CodeGen/debug-info-line.c where we have multiple #line directives within a single lexical block and want to generate only a single block that contains each file change. Part of rdar://10246360 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141729 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/LexicalScopes.cpp | 20 +++++++++++++++++--- 1 file changed, 17 insertions(+), 3 deletions(-) (limited to 'lib/CodeGen/LexicalScopes.cpp') diff --git a/lib/CodeGen/LexicalScopes.cpp b/lib/CodeGen/LexicalScopes.cpp index ae06a40..02fa525 100644 --- a/lib/CodeGen/LexicalScopes.cpp +++ b/lib/CodeGen/LexicalScopes.cpp @@ -118,9 +118,16 @@ LexicalScope *LexicalScopes::findLexicalScope(DebugLoc DL) { MDNode *IA = NULL; DL.getScopeAndInlinedAt(Scope, IA, MF->getFunction()->getContext()); if (!Scope) return NULL; + + // The scope that we were created with could have an extra file - which + // isn't what we care about in this case. + DIDescriptor D = DIDescriptor(Scope); + if (D.isLexicalBlockFile()) + Scope = DILexicalBlockFile(Scope).getScope(); + if (IA) return InlinedLexicalScopeMap.lookup(DebugLoc::getFromDILocation(IA)); - return LexicalScopeMap.lookup(DL.getScope(Scope->getContext())); + return LexicalScopeMap.lookup(Scope); } /// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If @@ -129,6 +136,7 @@ LexicalScope *LexicalScopes::getOrCreateLexicalScope(DebugLoc DL) { MDNode *Scope = NULL; MDNode *InlinedAt = NULL; DL.getScopeAndInlinedAt(Scope, InlinedAt, MF->getFunction()->getContext()); + if (InlinedAt) { // Create an abstract scope for inlined function. getOrCreateAbstractScope(Scope); @@ -141,12 +149,16 @@ LexicalScope *LexicalScopes::getOrCreateLexicalScope(DebugLoc DL) { /// getOrCreateRegularScope - Find or create a regular lexical scope. LexicalScope *LexicalScopes::getOrCreateRegularScope(MDNode *Scope) { + DIDescriptor D = DIDescriptor(Scope); + if (D.isLexicalBlockFile()) + Scope = DILexicalBlockFile(Scope).getScope(); + LexicalScope *WScope = LexicalScopeMap.lookup(Scope); if (WScope) return WScope; LexicalScope *Parent = NULL; - if (DIDescriptor(Scope).isLexicalBlock()) + if (D.isLexicalBlock()) Parent = getOrCreateLexicalScope(DebugLoc::getFromDILexicalBlock(Scope)); WScope = new LexicalScope(Parent, DIDescriptor(Scope), NULL, false); LexicalScopeMap.insert(std::make_pair(Scope, WScope)); @@ -176,12 +188,14 @@ LexicalScope *LexicalScopes::getOrCreateInlinedScope(MDNode *Scope, LexicalScope *LexicalScopes::getOrCreateAbstractScope(const MDNode *N) { assert(N && "Invalid Scope encoding!"); + DIDescriptor Scope(N); + if (Scope.isLexicalBlockFile()) + Scope = DILexicalBlockFile(Scope).getScope(); LexicalScope *AScope = AbstractScopeMap.lookup(N); if (AScope) return AScope; LexicalScope *Parent = NULL; - DIDescriptor Scope(N); if (Scope.isLexicalBlock()) { DILexicalBlock DB(N); DIDescriptor ParentDesc = DB.getContext(); -- cgit v1.1 From fe28ef41e34e842e6b77d9aa4bdf2bc2d6f17cae Mon Sep 17 00:00:00 2001 From: Eric Christopher Date: Thu, 13 Oct 2011 21:43:44 +0000 Subject: Don't forget to reconstruct D after changing the scope that we're looking at. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141892 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/LexicalScopes.cpp | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'lib/CodeGen/LexicalScopes.cpp') diff --git a/lib/CodeGen/LexicalScopes.cpp b/lib/CodeGen/LexicalScopes.cpp index 02fa525..a12e1a3 100644 --- a/lib/CodeGen/LexicalScopes.cpp +++ b/lib/CodeGen/LexicalScopes.cpp @@ -150,8 +150,10 @@ LexicalScope *LexicalScopes::getOrCreateLexicalScope(DebugLoc DL) { /// getOrCreateRegularScope - Find or create a regular lexical scope. LexicalScope *LexicalScopes::getOrCreateRegularScope(MDNode *Scope) { DIDescriptor D = DIDescriptor(Scope); - if (D.isLexicalBlockFile()) + if (D.isLexicalBlockFile()) { Scope = DILexicalBlockFile(Scope).getScope(); + D = DIDescriptor(Scope); + } LexicalScope *WScope = LexicalScopeMap.lookup(Scope); if (WScope) -- cgit v1.1