[rustc.git] / src / llvm / lib / CodeGen / LexicalScopes.cpp

//===- 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.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/LexicalScopes.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/Function.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/FormattedStream.h"
using namespace llvm;

#define DEBUG_TYPE "lexicalscopes"

/// reset - Reset the instance so that it's prepared for another function.
void LexicalScopes::reset() {
  MF = nullptr;
  CurrentFnLexicalScope = nullptr;
  LexicalScopeMap.clear();
  AbstractScopeMap.clear();
  InlinedLexicalScopeMap.clear();
  AbstractScopesList.clear();
}

/// initialize - Scan machine function and constuct lexical scope nest.
void LexicalScopes::initialize(const MachineFunction &Fn) {
  reset();
  MF = &Fn;
  SmallVector<InsnRange, 4> MIRanges;
  DenseMap<const MachineInstr *, LexicalScope *> 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<InsnRange> &MIRanges,
    DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {

  // Scan each instruction and create scopes. First build working set of scopes.
  for (const auto &MBB : *MF) {
    const MachineInstr *RangeBeginMI = nullptr;
    const MachineInstr *PrevMI = nullptr;
    DebugLoc PrevDL;
    for (const auto &MInsn : MBB) {
      // 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);
    }
  }
}

LexicalScope *LexicalScopes::findInlinedScope(DebugLoc DL) {
  MDNode *Scope = nullptr;
  MDNode *IA = nullptr;
  DL.getScopeAndInlinedAt(Scope, IA, MF->getFunction()->getContext());
  auto I = InlinedLexicalScopeMap.find(std::make_pair(Scope, IA));
  return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr;
}

/// findLexicalScope - Find lexical scope, either regular or inlined, for the
/// given DebugLoc. Return NULL if not found.
LexicalScope *LexicalScopes::findLexicalScope(DebugLoc DL) {
  MDNode *Scope = nullptr;
  MDNode *IA = nullptr;
  DL.getScopeAndInlinedAt(Scope, IA, MF->getFunction()->getContext());
  if (!Scope)
    return nullptr;

  // 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) {
    auto I = InlinedLexicalScopeMap.find(std::make_pair(Scope, IA));
    return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr;
  }
  return findLexicalScope(Scope);
}

/// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If
/// not available then create new lexical scope.
LexicalScope *LexicalScopes::getOrCreateLexicalScope(DebugLoc DL) {
  if (DL.isUnknown())
    return nullptr;
  MDNode *Scope = nullptr;
  MDNode *InlinedAt = nullptr;
  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) {
  DIDescriptor D = DIDescriptor(Scope);
  if (D.isLexicalBlockFile()) {
    Scope = DILexicalBlockFile(Scope).getScope();
    D = DIDescriptor(Scope);
  }

  auto I = LexicalScopeMap.find(Scope);
  if (I != LexicalScopeMap.end())
    return &I->second;

  LexicalScope *Parent = nullptr;
  if (D.isLexicalBlock())
    Parent = getOrCreateLexicalScope(DebugLoc::getFromDILexicalBlock(Scope));
  // FIXME: Use forward_as_tuple instead of make_tuple, once MSVC2012
  // compatibility is no longer required.
  I = LexicalScopeMap.emplace(std::piecewise_construct, std::make_tuple(Scope),
                              std::make_tuple(Parent, DIDescriptor(Scope),
                                              nullptr, false)).first;

  if (!Parent) {
    assert(DIDescriptor(Scope).isSubprogram());
    assert(DISubprogram(Scope).describes(MF->getFunction()));
    assert(!CurrentFnLexicalScope);
    CurrentFnLexicalScope = &I->second;
  }

  return &I->second;
}

/// getOrCreateInlinedScope - Find or create an inlined lexical scope.
LexicalScope *LexicalScopes::getOrCreateInlinedScope(MDNode *ScopeNode,
                                                     MDNode *InlinedAt) {
  std::pair<const MDNode*, const MDNode*> P(ScopeNode, InlinedAt);
  auto I = InlinedLexicalScopeMap.find(P);
  if (I != InlinedLexicalScopeMap.end())
    return &I->second;

  LexicalScope *Parent;
  DILexicalBlock Scope(ScopeNode);
  if (Scope.isSubprogram())
    Parent = getOrCreateLexicalScope(DebugLoc::getFromDILocation(InlinedAt));
  else
    Parent = getOrCreateInlinedScope(Scope.getContext(), InlinedAt);

  // FIXME: Use forward_as_tuple instead of make_tuple, once MSVC2012
  // compatibility is no longer required.
  I = InlinedLexicalScopeMap.emplace(std::piecewise_construct,
                                     std::make_tuple(P),
                                     std::make_tuple(Parent, Scope, InlinedAt,
                                                     false)).first;
  return &I->second;
}

/// getOrCreateAbstractScope - Find or create an abstract lexical scope.
LexicalScope *LexicalScopes::getOrCreateAbstractScope(const MDNode *N) {
  assert(N && "Invalid Scope encoding!");

  DIDescriptor Scope(N);
  if (Scope.isLexicalBlockFile())
    Scope = DILexicalBlockFile(Scope).getScope();
  auto I = AbstractScopeMap.find(Scope);
  if (I != AbstractScopeMap.end())
    return &I->second;

  LexicalScope *Parent = nullptr;
  if (Scope.isLexicalBlock()) {
    DILexicalBlock DB(Scope);
    DIDescriptor ParentDesc = DB.getContext();
    Parent = getOrCreateAbstractScope(ParentDesc);
  }
  I = AbstractScopeMap.emplace(std::piecewise_construct,
                               std::forward_as_tuple(Scope),
                               std::forward_as_tuple(Parent, Scope,
                                                     nullptr, true)).first;
  if (Scope.isSubprogram())
    AbstractScopesList.push_back(&I->second);
  return &I->second;
}

/// constructScopeNest
void LexicalScopes::constructScopeNest(LexicalScope *Scope) {
  assert(Scope && "Unable to calculate scope dominance graph!");
  SmallVector<LexicalScope *, 4> WorkStack;
  WorkStack.push_back(Scope);
  unsigned Counter = 0;
  while (!WorkStack.empty()) {
    LexicalScope *WS = WorkStack.back();
    const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
    bool visitedChildren = false;
    for (SmallVectorImpl<LexicalScope *>::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<InsnRange> &MIRanges,
    DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {

  LexicalScope *PrevLexicalScope = nullptr;
  for (SmallVectorImpl<InsnRange>::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, SmallPtrSetImpl<const MachineBasicBlock *> &MBBs) {
  MBBs.clear();
  LexicalScope *Scope = getOrCreateLexicalScope(DL);
  if (!Scope)
    return;

  if (Scope == CurrentFnLexicalScope) {
    for (const auto &MBB : *MF)
      MBBs.insert(&MBB);
    return;
  }

  SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges();
  for (SmallVectorImpl<InsnRange>::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;

  // 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) {
    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(unsigned Indent) const {
#ifndef NDEBUG
  raw_ostream &err = dbgs();
  err.indent(Indent);
  err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n";
  const MDNode *N = Desc;
  err.indent(Indent);
  N->dump();
  if (AbstractScope)
    err << std::string(Indent, ' ') << "Abstract Scope\n";

  if (!Children.empty())
    err << std::string(Indent + 2, ' ') << "Children ...\n";
  for (unsigned i = 0, e = Children.size(); i != e; ++i)
    if (Children[i] != this)
      Children[i]->dump(Indent + 2);
#endif
}
Commit	Line	Data
223e47cc LB	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
223e47cc	17	#include "llvm/CodeGen/LexicalScopes.h"
223e47cc LB	18	#include "llvm/CodeGen/MachineFunction.h"
223e47cc LB	19	#include "llvm/CodeGen/MachineInstr.h"
1a4d82fc	20	#include "llvm/IR/DebugInfo.h"
970d7e83	21	#include "llvm/IR/Function.h"
223e47cc LB	22	#include "llvm/Support/Debug.h"
	23	#include "llvm/Support/ErrorHandling.h"
	24	#include "llvm/Support/FormattedStream.h"
	25	using namespace llvm;
	26
1a4d82fc	27	#define DEBUG_TYPE "lexicalscopes"
223e47cc	28
1a4d82fc JJ	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();
223e47cc LB	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) {
1a4d82fc	41	reset();
223e47cc LB	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.
1a4d82fc JJ	54	void LexicalScopes::extractLexicalScopes(
	55	SmallVectorImpl<InsnRange> &MIRanges,
	56	DenseMap<const MachineInstr , LexicalScope > &MI2ScopeMap) {
223e47cc LB	57
223e47cc LB	58	// Scan each instruction and create scopes. First build working set of scopes.
1a4d82fc JJ	59	for (const auto &MBB : *MF) {
	60	const MachineInstr *RangeBeginMI = nullptr;
	61	const MachineInstr *PrevMI = nullptr;
223e47cc	62	DebugLoc PrevDL;
1a4d82fc	63	for (const auto &MInsn : MBB) {
223e47cc	64	// Check if instruction has valid location information.
1a4d82fc	65	const DebugLoc MIDL = MInsn.getDebugLoc();
223e47cc	66	if (MIDL.isUnknown()) {
1a4d82fc	67	PrevMI = &MInsn;
223e47cc LB	68	continue;
	69	}
	70
	71	// If scope has not changed then skip this instruction.
	72	if (MIDL == PrevDL) {
1a4d82fc	73	PrevMI = &MInsn;
223e47cc LB	74	continue;
	75	}
	76
	77	// Ignore DBG_VALUE. It does not contribute to any instruction in output.
1a4d82fc	78	if (MInsn.isDebugValue())
223e47cc LB	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.
1a4d82fc	91	RangeBeginMI = &MInsn;
223e47cc LB	92
223e47cc LB	93	// Reset previous markers.
1a4d82fc	94	PrevMI = &MInsn;
223e47cc LB	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
1a4d82fc JJ	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
223e47cc LB	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) {
1a4d82fc JJ	118	MDNode *Scope = nullptr;
1a4d82fc JJ	119	MDNode *IA = nullptr;
223e47cc	120	DL.getScopeAndInlinedAt(Scope, IA, MF->getFunction()->getContext());
1a4d82fc JJ	121	if (!Scope)
1a4d82fc JJ	122	return nullptr;
223e47cc LB	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();
1a4d82fc JJ	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);
223e47cc LB	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) {
85aaf69f SL	140	if (DL.isUnknown())
85aaf69f SL	141	return nullptr;
1a4d82fc JJ	142	MDNode *Scope = nullptr;
1a4d82fc JJ	143	MDNode *InlinedAt = nullptr;
223e47cc LB	144	DL.getScopeAndInlinedAt(Scope, InlinedAt, MF->getFunction()->getContext());
	145
	146	if (InlinedAt) {
	147	// Create an abstract scope for inlined function.
	148	getOrCreateAbstractScope(Scope);
	149	// Create an inlined scope for inlined function.
	150	return getOrCreateInlinedScope(Scope, InlinedAt);
	151	}
1a4d82fc	152
223e47cc LB	153	return getOrCreateRegularScope(Scope);
	154	}
	155
	156	/// getOrCreateRegularScope - Find or create a regular lexical scope.
	157	LexicalScope LexicalScopes::getOrCreateRegularScope(MDNode Scope) {
	158	DIDescriptor D = DIDescriptor(Scope);
	159	if (D.isLexicalBlockFile()) {
	160	Scope = DILexicalBlockFile(Scope).getScope();
	161	D = DIDescriptor(Scope);
	162	}
223e47cc	163
1a4d82fc JJ	164	auto I = LexicalScopeMap.find(Scope);
	165	if (I != LexicalScopeMap.end())
	166	return &I->second;
	167
	168	LexicalScope *Parent = nullptr;
223e47cc LB	169	if (D.isLexicalBlock())
223e47cc LB	170	Parent = getOrCreateLexicalScope(DebugLoc::getFromDILexicalBlock(Scope));
1a4d82fc JJ	171	// FIXME: Use forward_as_tuple instead of make_tuple, once MSVC2012
	172	// compatibility is no longer required.
	173	I = LexicalScopeMap.emplace(std::piecewise_construct, std::make_tuple(Scope),
	174	std::make_tuple(Parent, DIDescriptor(Scope),
	175	nullptr, false)).first;
	176
85aaf69f SL	177	if (!Parent) {
	178	assert(DIDescriptor(Scope).isSubprogram());
	179	assert(DISubprogram(Scope).describes(MF->getFunction()));
	180	assert(!CurrentFnLexicalScope);
1a4d82fc	181	CurrentFnLexicalScope = &I->second;
85aaf69f	182	}
1a4d82fc JJ	183
1a4d82fc JJ	184	return &I->second;
223e47cc LB	185	}
	186
	187	/// getOrCreateInlinedScope - Find or create an inlined lexical scope.
1a4d82fc	188	LexicalScope LexicalScopes::getOrCreateInlinedScope(MDNode ScopeNode,
223e47cc	189	MDNode *InlinedAt) {
1a4d82fc JJ	190	std::pair<const MDNode, const MDNode> P(ScopeNode, InlinedAt);
	191	auto I = InlinedLexicalScopeMap.find(P);
	192	if (I != InlinedLexicalScopeMap.end())
	193	return &I->second;
	194
	195	LexicalScope *Parent;
	196	DILexicalBlock Scope(ScopeNode);
	197	if (Scope.isSubprogram())
	198	Parent = getOrCreateLexicalScope(DebugLoc::getFromDILocation(InlinedAt));
	199	else
	200	Parent = getOrCreateInlinedScope(Scope.getContext(), InlinedAt);
	201
	202	// FIXME: Use forward_as_tuple instead of make_tuple, once MSVC2012
	203	// compatibility is no longer required.
	204	I = InlinedLexicalScopeMap.emplace(std::piecewise_construct,
	205	std::make_tuple(P),
	206	std::make_tuple(Parent, Scope, InlinedAt,
	207	false)).first;
	208	return &I->second;
223e47cc LB	209	}
	210
	211	/// getOrCreateAbstractScope - Find or create an abstract lexical scope.
	212	LexicalScope LexicalScopes::getOrCreateAbstractScope(const MDNode N) {
	213	assert(N && "Invalid Scope encoding!");
	214
	215	DIDescriptor Scope(N);
	216	if (Scope.isLexicalBlockFile())
	217	Scope = DILexicalBlockFile(Scope).getScope();
1a4d82fc JJ	218	auto I = AbstractScopeMap.find(Scope);
	219	if (I != AbstractScopeMap.end())
	220	return &I->second;
223e47cc	221
1a4d82fc	222	LexicalScope *Parent = nullptr;
223e47cc	223	if (Scope.isLexicalBlock()) {
1a4d82fc	224	DILexicalBlock DB(Scope);
223e47cc LB	225	DIDescriptor ParentDesc = DB.getContext();
	226	Parent = getOrCreateAbstractScope(ParentDesc);
	227	}
1a4d82fc JJ	228	I = AbstractScopeMap.emplace(std::piecewise_construct,
	229	std::forward_as_tuple(Scope),
	230	std::forward_as_tuple(Parent, Scope,
	231	nullptr, true)).first;
	232	if (Scope.isSubprogram())
	233	AbstractScopesList.push_back(&I->second);
	234	return &I->second;
223e47cc LB	235	}
	236
	237	/// constructScopeNest
	238	void LexicalScopes::constructScopeNest(LexicalScope *Scope) {
1a4d82fc	239	assert(Scope && "Unable to calculate scope dominance graph!");
223e47cc LB	240	SmallVector<LexicalScope *, 4> WorkStack;
	241	WorkStack.push_back(Scope);
	242	unsigned Counter = 0;
	243	while (!WorkStack.empty()) {
	244	LexicalScope *WS = WorkStack.back();
1a4d82fc	245	const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
223e47cc	246	bool visitedChildren = false;
1a4d82fc JJ	247	for (SmallVectorImpl<LexicalScope *>::const_iterator SI = Children.begin(),
	248	SE = Children.end();
	249	SI != SE; ++SI) {
223e47cc LB	250	LexicalScope ChildScope = SI;
	251	if (!ChildScope->getDFSOut()) {
	252	WorkStack.push_back(ChildScope);
	253	visitedChildren = true;
	254	ChildScope->setDFSIn(++Counter);
	255	break;
	256	}
	257	}
	258	if (!visitedChildren) {
	259	WorkStack.pop_back();
	260	WS->setDFSOut(++Counter);
	261	}
	262	}
	263	}
	264
	265	/// assignInstructionRanges - Find ranges of instructions covered by each
	266	/// lexical scope.
1a4d82fc JJ	267	void LexicalScopes::assignInstructionRanges(
	268	SmallVectorImpl<InsnRange> &MIRanges,
	269	DenseMap<const MachineInstr , LexicalScope > &MI2ScopeMap) {
	270
	271	LexicalScope *PrevLexicalScope = nullptr;
223e47cc	272	for (SmallVectorImpl<InsnRange>::const_iterator RI = MIRanges.begin(),
1a4d82fc JJ	273	RE = MIRanges.end();
1a4d82fc JJ	274	RI != RE; ++RI) {
223e47cc LB	275	const InsnRange &R = *RI;
223e47cc LB	276	LexicalScope *S = MI2ScopeMap.lookup(R.first);
1a4d82fc	277	assert(S && "Lost LexicalScope for a machine instruction!");
223e47cc LB	278	if (PrevLexicalScope && !PrevLexicalScope->dominates(S))
	279	PrevLexicalScope->closeInsnRange(S);
	280	S->openInsnRange(R.first);
	281	S->extendInsnRange(R.second);
	282	PrevLexicalScope = S;
	283	}
	284
	285	if (PrevLexicalScope)
	286	PrevLexicalScope->closeInsnRange();
	287	}
	288
	289	/// getMachineBasicBlocks - Populate given set using machine basic blocks which
1a4d82fc	290	/// have machine instructions that belong to lexical scope identified by
223e47cc	291	/// DebugLoc.
1a4d82fc JJ	292	void LexicalScopes::getMachineBasicBlocks(
1a4d82fc JJ	293	DebugLoc DL, SmallPtrSetImpl<const MachineBasicBlock *> &MBBs) {
223e47cc LB	294	MBBs.clear();
	295	LexicalScope *Scope = getOrCreateLexicalScope(DL);
	296	if (!Scope)
	297	return;
1a4d82fc	298
223e47cc	299	if (Scope == CurrentFnLexicalScope) {
1a4d82fc JJ	300	for (const auto &MBB : *MF)
1a4d82fc JJ	301	MBBs.insert(&MBB);
223e47cc LB	302	return;
	303	}
	304
1a4d82fc JJ	305	SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges();
	306	for (SmallVectorImpl<InsnRange>::iterator I = InsnRanges.begin(),
	307	E = InsnRanges.end();
	308	I != E; ++I) {
223e47cc LB	309	InsnRange &R = *I;
	310	MBBs.insert(R.first->getParent());
	311	}
	312	}
	313
	314	/// dominates - Return true if DebugLoc's lexical scope dominates at least one
	315	/// machine instruction's lexical scope in a given machine basic block.
	316	bool LexicalScopes::dominates(DebugLoc DL, MachineBasicBlock *MBB) {
	317	LexicalScope *Scope = getOrCreateLexicalScope(DL);
	318	if (!Scope)
	319	return false;
	320
	321	// Current function scope covers all basic blocks in the function.
	322	if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF)
	323	return true;
	324
	325	bool Result = false;
1a4d82fc JJ	326	for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
1a4d82fc JJ	327	++I) {
223e47cc LB	328	DebugLoc IDL = I->getDebugLoc();
	329	if (IDL.isUnknown())
	330	continue;
	331	if (LexicalScope *IScope = getOrCreateLexicalScope(IDL))
	332	if (Scope->dominates(IScope))
	333	return true;
	334	}
	335	return Result;
	336	}
	337
223e47cc	338	/// dump - Print data structures.
970d7e83	339	void LexicalScope::dump(unsigned Indent) const {
223e47cc LB	340	#ifndef NDEBUG
223e47cc LB	341	raw_ostream &err = dbgs();
970d7e83	342	err.indent(Indent);
223e47cc LB	343	err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n";
223e47cc LB	344	const MDNode *N = Desc;
970d7e83	345	err.indent(Indent);
223e47cc LB	346	N->dump();
223e47cc LB	347	if (AbstractScope)
970d7e83	348	err << std::string(Indent, ' ') << "Abstract Scope\n";
223e47cc	349
223e47cc	350	if (!Children.empty())
970d7e83	351	err << std::string(Indent + 2, ' ') << "Children ...\n";
223e47cc LB	352	for (unsigned i = 0, e = Children.size(); i != e; ++i)
223e47cc LB	353	if (Children[i] != this)
970d7e83	354	Children[i]->dump(Indent + 2);
223e47cc LB	355	#endif
223e47cc LB	356	}