llvm.org GIT mirror llvm / testing lib / CodeGen / LexicalScopes.cpp
testing

Tree @testing (Download .tar.gz)

LexicalScopes.cpp @testing

103b8e6
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
e3e43d9
ad3a540
 
 
103b8e6
 
ad3a540
 
 
 
103b8e6
ad3a540
 
 
 
 
 
103b8e6
 
8677f2f
 
b88a94f
 
4ba8443
 
bccff0f
 
103b8e6
 
 
 
 
 
a6df1e5
0640903
 
 
 
103b8e6
 
 
 
 
 
 
 
 
 
 
 
73a69d6
 
 
103b8e6
4aef727
4ba8443
 
e56023a
8467812
103b8e6
e56023a
3637bab
8467812
103b8e6
 
 
 
 
8467812
103b8e6
 
 
14a1dd1
 
 
103b8e6
 
 
 
 
 
 
 
 
 
 
 
8467812
103b8e6
 
8467812
103b8e6
 
 
 
3637bab
103b8e6
 
 
 
 
 
 
 
 
e56023a
 
73a69d6
4ba8443
6618a24
 
 
1268621
73a69d6
35ff67e
ee8af3e
 
 
bccff0f
103b8e6
 
 
 
e56023a
 
497110d
0640903
 
 
 
103b8e6
 
 
497110d
103b8e6
73a69d6
103b8e6
 
 
 
62e3e38
e56023a
1268621
 
73a69d6
bccff0f
 
 
103b8e6
e56023a
4ba8443
e56023a
497110d
7fcd745
 
62e3e38
 
bccff0f
d661fde
e56023a
d661fde
bccff0f
d661fde
73a69d6
bccff0f
103b8e6
 
 
62e3e38
e56023a
 
1268621
 
e56023a
ee8af3e
 
bccff0f
103b8e6
ee8af3e
e56023a
62e3e38
ee8af3e
62e3e38
ee8af3e
71648d0
 
 
7fcd745
bccff0f
103b8e6
 
 
62e3e38
e56023a
62e3e38
1268621
cec3724
bccff0f
 
103b8e6
e56023a
4ba8443
e56023a
62e3e38
 
bccff0f
cec3724
 
bccff0f
e56023a
bccff0f
 
103b8e6
 
 
 
73a69d6
103b8e6
 
 
 
 
9f4c379
103b8e6
89584ae
103b8e6
 
 
 
 
 
 
 
 
 
 
 
 
5bc942c
 
73a69d6
 
 
4ba8443
89584ae
103b8e6
73a69d6
103b8e6
 
 
 
 
 
 
 
 
 
 
 
73a69d6
103b8e6
73a69d6
e56023a
a6df1e5
103b8e6
a6df1e5
103b8e6
 
 
73a69d6
2e85b1b
4aef727
 
2e85b1b
 
 
9f4c379
89584ae
103b8e6
 
 
 
 
e56023a
a6df1e5
103b8e6
 
 
2e85b1b
 
 
 
 
103b8e6
89584ae
 
1aa1d1a
 
 
103b8e6
 
 
 
1d03d38
88d2075
103b8e6
7650d9b
103b8e6
 
7650d9b
103b8e6
 
7650d9b
103b8e6
 
7650d9b
103b8e6
 
7650d9b
103b8e6
88d2075
//===- 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/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/Metadata.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <string>
#include <tuple>
#include <utility>

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();
  // Don't attempt any lexical scope creation for a NoDebug compile unit.
  if (Fn.getFunction()->getSubprogram()->getUnit()->getEmissionKind() ==
      DICompileUnit::NoDebug)
    return;
  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;
    const DILocation *PrevDL = nullptr;
    for (const auto &MInsn : MBB) {
      // Check if instruction has valid location information.
      const DILocation *MIDL = MInsn.getDebugLoc();
      if (!MIDL) {
        PrevMI = &MInsn;
        continue;
      }

      // If scope has not changed then skip this instruction.
      if (MIDL == PrevDL) {
        PrevMI = &MInsn;
        continue;
      }

      // Ignore DBG_VALUE and similar instruction that do not contribute to any
      // instruction in the output.
      if (MInsn.isMetaInstruction())
        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) {
      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(const DILocation *DL) {
  DILocalScope *Scope = DL->getScope();
  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.
  Scope = Scope->getNonLexicalBlockFileScope();

  if (auto *IA = DL->getInlinedAt()) {
    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(const DILocalScope *Scope,
                                                     const DILocation *IA) {
  if (IA) {
    // Skip scopes inlined from a NoDebug compile unit.
    if (Scope->getSubprogram()->getUnit()->getEmissionKind() ==
        DICompileUnit::NoDebug)
      return getOrCreateLexicalScope(IA);
    // Create an abstract scope for inlined function.
    getOrCreateAbstractScope(Scope);
    // Create an inlined scope for inlined function.
    return getOrCreateInlinedScope(Scope, IA);
  }

  return getOrCreateRegularScope(Scope);
}

/// getOrCreateRegularScope - Find or create a regular lexical scope.
LexicalScope *
LexicalScopes::getOrCreateRegularScope(const DILocalScope *Scope) {
  assert(Scope && "Invalid Scope encoding!");
  Scope = Scope->getNonLexicalBlockFileScope();

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

  // FIXME: Should the following dyn_cast be DILexicalBlock?
  LexicalScope *Parent = nullptr;
  if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
    Parent = getOrCreateLexicalScope(Block->getScope());
  I = LexicalScopeMap.emplace(std::piecewise_construct,
                              std::forward_as_tuple(Scope),
                              std::forward_as_tuple(Parent, Scope, nullptr,
                                                    false)).first;

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

  return &I->second;
}

/// getOrCreateInlinedScope - Find or create an inlined lexical scope.
LexicalScope *
LexicalScopes::getOrCreateInlinedScope(const DILocalScope *Scope,
                                       const DILocation *InlinedAt) {
  assert(Scope && "Invalid Scope encoding!");
  Scope = Scope->getNonLexicalBlockFileScope();
  std::pair<const DILocalScope *, const DILocation *> P(Scope, InlinedAt);
  auto I = InlinedLexicalScopeMap.find(P);
  if (I != InlinedLexicalScopeMap.end())
    return &I->second;

  LexicalScope *Parent;
  if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
    Parent = getOrCreateInlinedScope(Block->getScope(), InlinedAt);
  else
    Parent = getOrCreateLexicalScope(InlinedAt);

  I = InlinedLexicalScopeMap
          .emplace(std::piecewise_construct, std::forward_as_tuple(P),
                   std::forward_as_tuple(Parent, Scope, InlinedAt, false))
          .first;
  return &I->second;
}

/// getOrCreateAbstractScope - Find or create an abstract lexical scope.
LexicalScope *
LexicalScopes::getOrCreateAbstractScope(const DILocalScope *Scope) {
  assert(Scope && "Invalid Scope encoding!");
  Scope = Scope->getNonLexicalBlockFileScope();
  auto I = AbstractScopeMap.find(Scope);
  if (I != AbstractScopeMap.end())
    return &I->second;

  // FIXME: Should the following isa be DILexicalBlock?
  LexicalScope *Parent = nullptr;
  if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
    Parent = getOrCreateAbstractScope(Block->getScope());

  I = AbstractScopeMap.emplace(std::piecewise_construct,
                               std::forward_as_tuple(Scope),
                               std::forward_as_tuple(Parent, Scope,
                                                     nullptr, true)).first;
  if (isa<DISubprogram>(Scope))
    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 (auto &ChildScope : Children)
      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 (const auto &R : MIRanges) {
    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(
    const DILocation *DL, SmallPtrSetImpl<const MachineBasicBlock *> &MBBs) {
  assert(MF && "Method called on a uninitialized LexicalScopes object!");
  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 (auto &R : InsnRanges)
    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(const DILocation *DL, MachineBasicBlock *MBB) {
  assert(MF && "Unexpected uninitialized LexicalScopes object!");
  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 (auto &I : *MBB) {
    if (const DILocation *IDL = I.getDebugLoc())
      if (LexicalScope *IScope = getOrCreateLexicalScope(IDL))
        if (Scope->dominates(IScope))
          return true;
  }
  return Result;
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void LexicalScope::dump(unsigned Indent) const {
  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