DwarfDebug.cpp

//===-- llvm/CodeGen/DwarfDebug.cpp - Dwarf Debug Framework ---------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file contains support for writing dwarf debug info into asm files.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "dwarfdebug"
#include "DwarfDebug.h"
#include "DIE.h"
#include "DIEHash.h"
#include "DwarfAccelTable.h"
#include "DwarfCompileUnit.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/Triple.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/DIBuilder.h"
#include "llvm/DebugInfo.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/MC/MCAsmInfo.h"
#include "llvm/MC/MCSection.h"
#include "llvm/MC/MCStreamer.h"
#include "llvm/MC/MCSymbol.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Dwarf.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/FormattedStream.h"
#include "llvm/Support/MD5.h"
#include "llvm/Support/Path.h"
#include "llvm/Support/Timer.h"
#include "llvm/Support/ValueHandle.h"
#include "llvm/Target/TargetFrameLowering.h"
#include "llvm/Target/TargetLoweringObjectFile.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"
#include "llvm/Target/TargetRegisterInfo.h"
using namespace llvm;

static cl::opt<bool>
DisableDebugInfoPrinting("disable-debug-info-print", cl::Hidden,
                         cl::desc("Disable debug info printing"));

static cl::opt<bool> UnknownLocations(
    "use-unknown-locations", cl::Hidden,
    cl::desc("Make an absence of debug location information explicit."),
    cl::init(false));

static cl::opt<bool>
GenerateODRHash("generate-odr-hash", cl::Hidden,
                cl::desc("Add an ODR hash to external type DIEs."),
                cl::init(false));

static cl::opt<bool>
GenerateCUHash("generate-cu-hash", cl::Hidden,
               cl::desc("Add the CU hash as the dwo_id."),
               cl::init(false));

static cl::opt<bool>
GenerateGnuPubSections("generate-gnu-dwarf-pub-sections", cl::Hidden,
                       cl::desc("Generate GNU-style pubnames and pubtypes"),
                       cl::init(false));

namespace {
enum DefaultOnOff {
  Default,
  Enable,
  Disable
};
}

static cl::opt<DefaultOnOff>
DwarfAccelTables("dwarf-accel-tables", cl::Hidden,
                 cl::desc("Output prototype dwarf accelerator tables."),
                 cl::values(clEnumVal(Default, "Default for platform"),
                            clEnumVal(Enable, "Enabled"),
                            clEnumVal(Disable, "Disabled"), clEnumValEnd),
                 cl::init(Default));

static cl::opt<DefaultOnOff>
SplitDwarf("split-dwarf", cl::Hidden,
           cl::desc("Output prototype dwarf split debug info."),
           cl::values(clEnumVal(Default, "Default for platform"),
                      clEnumVal(Enable, "Enabled"),
                      clEnumVal(Disable, "Disabled"), clEnumValEnd),
           cl::init(Default));

static cl::opt<DefaultOnOff>
DwarfPubSections("generate-dwarf-pub-sections", cl::Hidden,
                 cl::desc("Generate DWARF pubnames and pubtypes sections"),
                 cl::values(clEnumVal(Default, "Default for platform"),
                            clEnumVal(Enable, "Enabled"),
                            clEnumVal(Disable, "Disabled"), clEnumValEnd),
                 cl::init(Default));

static const char *const DWARFGroupName = "DWARF Emission";
static const char *const DbgTimerName = "DWARF Debug Writer";

//===----------------------------------------------------------------------===//

// Configuration values for initial hash set sizes (log2).
//
static const unsigned InitAbbreviationsSetSize = 9; // log2(512)

namespace llvm {

/// resolve - Look in the DwarfDebug map for the MDNode that
/// corresponds to the reference.
template <typename T>
T DbgVariable::resolve(DIRef<T> Ref) const {
  return DD->resolve(Ref);
}

DIType DbgVariable::getType() const {
  DIType Ty = Var.getType();
  // FIXME: isBlockByrefVariable should be reformulated in terms of complex
  // addresses instead.
  if (Var.isBlockByrefVariable()) {
    /* Byref variables, in Blocks, are declared by the programmer as
       "SomeType VarName;", but the compiler creates a
       __Block_byref_x_VarName struct, and gives the variable VarName
       either the struct, or a pointer to the struct, as its type.  This
       is necessary for various behind-the-scenes things the compiler
       needs to do with by-reference variables in blocks.

       However, as far as the original *programmer* is concerned, the
       variable should still have type 'SomeType', as originally declared.

       The following function dives into the __Block_byref_x_VarName
       struct to find the original type of the variable.  This will be
       passed back to the code generating the type for the Debug
       Information Entry for the variable 'VarName'.  'VarName' will then
       have the original type 'SomeType' in its debug information.

       The original type 'SomeType' will be the type of the field named
       'VarName' inside the __Block_byref_x_VarName struct.

       NOTE: In order for this to not completely fail on the debugger
       side, the Debug Information Entry for the variable VarName needs to
       have a DW_AT_location that tells the debugger how to unwind through
       the pointers and __Block_byref_x_VarName struct to find the actual
       value of the variable.  The function addBlockByrefType does this.  */
    DIType subType = Ty;
    uint16_t tag = Ty.getTag();

    if (tag == dwarf::DW_TAG_pointer_type)
      subType = resolve(DIDerivedType(Ty).getTypeDerivedFrom());

    DIArray Elements = DICompositeType(subType).getTypeArray();
    for (unsigned i = 0, N = Elements.getNumElements(); i < N; ++i) {
      DIDerivedType DT = DIDerivedType(Elements.getElement(i));
      if (getName() == DT.getName())
        return (resolve(DT.getTypeDerivedFrom()));
    }
  }
  return Ty;
}

} // end llvm namespace

/// Return Dwarf Version by checking module flags.
static unsigned getDwarfVersionFromModule(const Module *M) {
  Value *Val = M->getModuleFlag("Dwarf Version");
  if (!Val)
    return dwarf::DWARF_VERSION;
  return cast<ConstantInt>(Val)->getZExtValue();
}

DwarfDebug::DwarfDebug(AsmPrinter *A, Module *M)
  : Asm(A), MMI(Asm->MMI), FirstCU(0),
    AbbreviationsSet(InitAbbreviationsSetSize),
    SourceIdMap(DIEValueAllocator),
    PrevLabel(NULL), GlobalCUIndexCount(0),
    InfoHolder(A, &AbbreviationsSet, &Abbreviations, "info_string",
               DIEValueAllocator),
    SkeletonAbbrevSet(InitAbbreviationsSetSize),
    SkeletonHolder(A, &SkeletonAbbrevSet, &SkeletonAbbrevs, "skel_string",
                   DIEValueAllocator) {

  DwarfInfoSectionSym = DwarfAbbrevSectionSym = 0;
  DwarfStrSectionSym = TextSectionSym = 0;
  DwarfDebugRangeSectionSym = DwarfDebugLocSectionSym = DwarfLineSectionSym = 0;
  DwarfAddrSectionSym = 0;
  DwarfAbbrevDWOSectionSym = DwarfStrDWOSectionSym = 0;
  FunctionBeginSym = FunctionEndSym = 0;

  // Turn on accelerator tables for Darwin by default, pubnames by
  // default for non-Darwin, and handle split dwarf.
  bool IsDarwin = Triple(A->getTargetTriple()).isOSDarwin();

  if (DwarfAccelTables == Default)
    HasDwarfAccelTables = IsDarwin;
  else
    HasDwarfAccelTables = DwarfAccelTables == Enable;

  if (SplitDwarf == Default)
    HasSplitDwarf = false;
  else
    HasSplitDwarf = SplitDwarf == Enable;

  if (DwarfPubSections == Default)
    HasDwarfPubSections = !IsDarwin;
  else
    HasDwarfPubSections = DwarfPubSections == Enable;

  DwarfVersion = getDwarfVersionFromModule(MMI->getModule());

  {
    NamedRegionTimer T(DbgTimerName, DWARFGroupName, TimePassesIsEnabled);
    beginModule();
  }
}

// Switch to the specified MCSection and emit an assembler
// temporary label to it if SymbolStem is specified.
static MCSymbol *emitSectionSym(AsmPrinter *Asm, const MCSection *Section,
                                const char *SymbolStem = 0) {
  Asm->OutStreamer.SwitchSection(Section);
  if (!SymbolStem) return 0;

  MCSymbol *TmpSym = Asm->GetTempSymbol(SymbolStem);
  Asm->OutStreamer.EmitLabel(TmpSym);
  return TmpSym;
}

MCSymbol *DwarfUnits::getStringPoolSym() {
  return Asm->GetTempSymbol(StringPref);
}

MCSymbol *DwarfUnits::getStringPoolEntry(StringRef Str) {
  std::pair<MCSymbol*, unsigned> &Entry =
    StringPool.GetOrCreateValue(Str).getValue();
  if (Entry.first) return Entry.first;

  Entry.second = NextStringPoolNumber++;
  return Entry.first = Asm->GetTempSymbol(StringPref, Entry.second);
}

unsigned DwarfUnits::getStringPoolIndex(StringRef Str) {
  std::pair<MCSymbol*, unsigned> &Entry =
    StringPool.GetOrCreateValue(Str).getValue();
  if (Entry.first) return Entry.second;

  Entry.second = NextStringPoolNumber++;
  Entry.first = Asm->GetTempSymbol(StringPref, Entry.second);
  return Entry.second;
}

unsigned DwarfUnits::getAddrPoolIndex(const MCSymbol *Sym) {
  return getAddrPoolIndex(MCSymbolRefExpr::Create(Sym, Asm->OutContext));
}

unsigned DwarfUnits::getAddrPoolIndex(const MCExpr *Sym) {
  std::pair<DenseMap<const MCExpr *, unsigned>::iterator, bool> P =
      AddressPool.insert(std::make_pair(Sym, NextAddrPoolNumber));
  if (P.second)
    ++NextAddrPoolNumber;
  return P.first->second;
}

// Define a unique number for the abbreviation.
//
void DwarfUnits::assignAbbrevNumber(DIEAbbrev &Abbrev) {
  // Check the set for priors.
  DIEAbbrev *InSet = AbbreviationsSet->GetOrInsertNode(&Abbrev);

  // If it's newly added.
  if (InSet == &Abbrev) {
    // Add to abbreviation list.
    Abbreviations->push_back(&Abbrev);

    // Assign the vector position + 1 as its number.
    Abbrev.setNumber(Abbreviations->size());
  } else {
    // Assign existing abbreviation number.
    Abbrev.setNumber(InSet->getNumber());
  }
}

static bool isObjCClass(StringRef Name) {
  return Name.startswith("+") || Name.startswith("-");
}

static bool hasObjCCategory(StringRef Name) {
  if (!isObjCClass(Name)) return false;

  return Name.find(") ") != StringRef::npos;
}

static void getObjCClassCategory(StringRef In, StringRef &Class,
                                 StringRef &Category) {
  if (!hasObjCCategory(In)) {
    Class = In.slice(In.find('[') + 1, In.find(' '));
    Category = "";
    return;
  }

  Class = In.slice(In.find('[') + 1, In.find('('));
  Category = In.slice(In.find('[') + 1, In.find(' '));
  return;
}

static StringRef getObjCMethodName(StringRef In) {
  return In.slice(In.find(' ') + 1, In.find(']'));
}

// Helper for sorting sections into a stable output order.
static bool SectionSort(const MCSection *A, const MCSection *B) {
    std::string LA = (A ? A->getLabelBeginName() : "");
    std::string LB = (B ? B->getLabelBeginName() : "");
    return LA < LB;
}

// Add the various names to the Dwarf accelerator table names.
// TODO: Determine whether or not we should add names for programs
// that do not have a DW_AT_name or DW_AT_linkage_name field - this
// is only slightly different than the lookup of non-standard ObjC names.
static void addSubprogramNames(CompileUnit *TheCU, DISubprogram SP,
                               DIE* Die) {
  if (!SP.isDefinition()) return;
  TheCU->addAccelName(SP.getName(), Die);

  // If the linkage name is different than the name, go ahead and output
  // that as well into the name table.
  if (SP.getLinkageName() != "" && SP.getName() != SP.getLinkageName())
    TheCU->addAccelName(SP.getLinkageName(), Die);

  // If this is an Objective-C selector name add it to the ObjC accelerator
  // too.
  if (isObjCClass(SP.getName())) {
    StringRef Class, Category;
    getObjCClassCategory(SP.getName(), Class, Category);
    TheCU->addAccelObjC(Class, Die);
    if (Category != "")
      TheCU->addAccelObjC(Category, Die);
    // Also add the base method name to the name table.
    TheCU->addAccelName(getObjCMethodName(SP.getName()), Die);
  }
}

/// isSubprogramContext - Return true if Context is either a subprogram
/// or another context nested inside a subprogram.
bool DwarfDebug::isSubprogramContext(const MDNode *Context) {
  if (!Context)
    return false;
  DIDescriptor D(Context);
  if (D.isSubprogram())
    return true;
  if (D.isType())
    return isSubprogramContext(resolve(DIType(Context).getContext()));
  return false;
}

// Find DIE for the given subprogram and attach appropriate DW_AT_low_pc
// and DW_AT_high_pc attributes. If there are global variables in this
// scope then create and insert DIEs for these variables.
DIE *DwarfDebug::updateSubprogramScopeDIE(CompileUnit *SPCU,
                                          const MDNode *SPNode) {
  DIE *SPDie = SPCU->getDIE(SPNode);

  assert(SPDie && "Unable to find subprogram DIE!");
  DISubprogram SP(SPNode);

  // If we're updating an abstract DIE, then we will be adding the children and
  // object pointer later on. But what we don't want to do is process the
  // concrete DIE twice.
  if (DIE *AbsSPDIE = AbstractSPDies.lookup(SPNode)) {
    // Pick up abstract subprogram DIE.
    SPDie = new DIE(dwarf::DW_TAG_subprogram);
    SPCU->addDIEEntry(SPDie, dwarf::DW_AT_abstract_origin, AbsSPDIE);
    SPCU->addDie(SPDie);
  } else {
    DISubprogram SPDecl = SP.getFunctionDeclaration();
    if (!SPDecl.isSubprogram()) {
      // There is not any need to generate specification DIE for a function
      // defined at compile unit level. If a function is defined inside another
      // function then gdb prefers the definition at top level and but does not
      // expect specification DIE in parent function. So avoid creating
      // specification DIE for a function defined inside a function.
      DIScope SPContext = resolve(SP.getContext());
      if (SP.isDefinition() && !SPContext.isCompileUnit() &&
          !SPContext.isFile() &&
          !isSubprogramContext(SPContext)) {
        SPCU->addFlag(SPDie, dwarf::DW_AT_declaration);

        // Add arguments.
        DICompositeType SPTy = SP.getType();
        DIArray Args = SPTy.getTypeArray();
        uint16_t SPTag = SPTy.getTag();
        if (SPTag == dwarf::DW_TAG_subroutine_type)
          for (unsigned i = 1, N = Args.getNumElements(); i < N; ++i) {
            DIE *Arg = new DIE(dwarf::DW_TAG_formal_parameter);
            DIType ATy = DIType(Args.getElement(i));
            SPCU->addType(Arg, ATy);
            if (ATy.isArtificial())
              SPCU->addFlag(Arg, dwarf::DW_AT_artificial);
            if (ATy.isObjectPointer())
              SPCU->addDIEEntry(SPDie, dwarf::DW_AT_object_pointer, Arg);
            SPDie->addChild(Arg);
          }
        DIE *SPDeclDie = SPDie;
        SPDie = new DIE(dwarf::DW_TAG_subprogram);
        SPCU->addDIEEntry(SPDie, dwarf::DW_AT_specification, SPDeclDie);
        SPCU->addDie(SPDie);
      }
    }
  }

  SPCU->addLabelAddress(SPDie, dwarf::DW_AT_low_pc,
                        Asm->GetTempSymbol("func_begin",
                                           Asm->getFunctionNumber()));
  SPCU->addLabelAddress(SPDie, dwarf::DW_AT_high_pc,
                        Asm->GetTempSymbol("func_end",
                                           Asm->getFunctionNumber()));
  const TargetRegisterInfo *RI = Asm->TM.getRegisterInfo();
  MachineLocation Location(RI->getFrameRegister(*Asm->MF));
  SPCU->addAddress(SPDie, dwarf::DW_AT_frame_base, Location);

  // Add name to the name table, we do this here because we're guaranteed
  // to have concrete versions of our DW_TAG_subprogram nodes.
  addSubprogramNames(SPCU, SP, SPDie);

  return SPDie;
}

/// Check whether we should create a DIE for the given Scope, return true
/// if we don't create a DIE (the corresponding DIE is null).
bool DwarfDebug::isLexicalScopeDIENull(LexicalScope *Scope) {
  if (Scope->isAbstractScope())
    return false;

  // We don't create a DIE if there is no Range.
  const SmallVectorImpl<InsnRange> &Ranges = Scope->getRanges();
  if (Ranges.empty())
    return true;

  if (Ranges.size() > 1)
    return false;

  // We don't create a DIE if we have a single Range and the end label
  // is null.
  SmallVectorImpl<InsnRange>::const_iterator RI = Ranges.begin();
  MCSymbol *End = getLabelAfterInsn(RI->second);
  return !End;
}

// Construct new DW_TAG_lexical_block for this scope and attach
// DW_AT_low_pc/DW_AT_high_pc labels.
DIE *DwarfDebug::constructLexicalScopeDIE(CompileUnit *TheCU,
                                          LexicalScope *Scope) {
  if (isLexicalScopeDIENull(Scope))
    return 0;

  DIE *ScopeDIE = new DIE(dwarf::DW_TAG_lexical_block);
  if (Scope->isAbstractScope())
    return ScopeDIE;

  const SmallVectorImpl<InsnRange> &Ranges = Scope->getRanges();
  // If we have multiple ranges, emit them into the range section.
  if (Ranges.size() > 1) {
    // .debug_range section has not been laid out yet. Emit offset in
    // .debug_range as a uint, size 4, for now. emitDIE will handle
    // DW_AT_ranges appropriately.
    TheCU->addUInt(ScopeDIE, dwarf::DW_AT_ranges, dwarf::DW_FORM_data4,
                   DebugRangeSymbols.size()
                   * Asm->getDataLayout().getPointerSize());
    for (SmallVectorImpl<InsnRange>::const_iterator RI = Ranges.begin(),
         RE = Ranges.end(); RI != RE; ++RI) {
      DebugRangeSymbols.push_back(getLabelBeforeInsn(RI->first));
      DebugRangeSymbols.push_back(getLabelAfterInsn(RI->second));
    }

    // Terminate the range list.
    DebugRangeSymbols.push_back(NULL);
    DebugRangeSymbols.push_back(NULL);
    return ScopeDIE;
  }

  // Construct the address range for this DIE.
  SmallVectorImpl<InsnRange>::const_iterator RI = Ranges.begin();
  MCSymbol *Start = getLabelBeforeInsn(RI->first);
  MCSymbol *End = getLabelAfterInsn(RI->second);
  assert(End && "End label should not be null!");

  assert(Start->isDefined() && "Invalid starting label for an inlined scope!");
  assert(End->isDefined() && "Invalid end label for an inlined scope!");

  TheCU->addLabelAddress(ScopeDIE, dwarf::DW_AT_low_pc, Start);
  TheCU->addLabelAddress(ScopeDIE, dwarf::DW_AT_high_pc, End);

  return ScopeDIE;
}

// This scope represents inlined body of a function. Construct DIE to
// represent this concrete inlined copy of the function.
DIE *DwarfDebug::constructInlinedScopeDIE(CompileUnit *TheCU,
                                          LexicalScope *Scope) {
  const SmallVectorImpl<InsnRange> &Ranges = Scope->getRanges();
  assert(Ranges.empty() == false &&
         "LexicalScope does not have instruction markers!");

  if (!Scope->getScopeNode())
    return NULL;
  DIScope DS(Scope->getScopeNode());
  DISubprogram InlinedSP = getDISubprogram(DS);
  DIE *OriginDIE = TheCU->getDIE(InlinedSP);
  if (!OriginDIE) {
    DEBUG(dbgs() << "Unable to find original DIE for an inlined subprogram.");
    return NULL;
  }

  DIE *ScopeDIE = new DIE(dwarf::DW_TAG_inlined_subroutine);
  TheCU->addDIEEntry(ScopeDIE, dwarf::DW_AT_abstract_origin, OriginDIE);

  if (Ranges.size() > 1) {
    // .debug_range section has not been laid out yet. Emit offset in
    // .debug_range as a uint, size 4, for now. emitDIE will handle
    // DW_AT_ranges appropriately.
    TheCU->addUInt(ScopeDIE, dwarf::DW_AT_ranges, dwarf::DW_FORM_data4,
                   DebugRangeSymbols.size()
                   * Asm->getDataLayout().getPointerSize());
    for (SmallVectorImpl<InsnRange>::const_iterator RI = Ranges.begin(),
         RE = Ranges.end(); RI != RE; ++RI) {
      DebugRangeSymbols.push_back(getLabelBeforeInsn(RI->first));
      DebugRangeSymbols.push_back(getLabelAfterInsn(RI->second));
    }
    DebugRangeSymbols.push_back(NULL);
    DebugRangeSymbols.push_back(NULL);
  } else {
    SmallVectorImpl<InsnRange>::const_iterator RI = Ranges.begin();
    MCSymbol *StartLabel = getLabelBeforeInsn(RI->first);
    MCSymbol *EndLabel = getLabelAfterInsn(RI->second);

    if (StartLabel == 0 || EndLabel == 0)
      llvm_unreachable("Unexpected Start and End labels for an inlined scope!");

    assert(StartLabel->isDefined() &&
           "Invalid starting label for an inlined scope!");
    assert(EndLabel->isDefined() && "Invalid end label for an inlined scope!");

    TheCU->addLabelAddress(ScopeDIE, dwarf::DW_AT_low_pc, StartLabel);
    TheCU->addLabelAddress(ScopeDIE, dwarf::DW_AT_high_pc, EndLabel);
  }

  InlinedSubprogramDIEs.insert(OriginDIE);

  // Add the call site information to the DIE.
  DILocation DL(Scope->getInlinedAt());
  TheCU->addUInt(ScopeDIE, dwarf::DW_AT_call_file, 0,
                 getOrCreateSourceID(DL.getFilename(), DL.getDirectory(),
                                     TheCU->getUniqueID()));
  TheCU->addUInt(ScopeDIE, dwarf::DW_AT_call_line, 0, DL.getLineNumber());

  // Add name to the name table, we do this here because we're guaranteed
  // to have concrete versions of our DW_TAG_inlined_subprogram nodes.
  addSubprogramNames(TheCU, InlinedSP, ScopeDIE);

  return ScopeDIE;
}

DIE *DwarfDebug::createScopeChildrenDIE(CompileUnit *TheCU, LexicalScope *Scope,
                                        SmallVectorImpl<DIE*> &Children) {
    DIE *ObjectPointer = NULL;

  // Collect arguments for current function.
  if (LScopes.isCurrentFunctionScope(Scope))
    for (unsigned i = 0, N = CurrentFnArguments.size(); i < N; ++i)
      if (DbgVariable *ArgDV = CurrentFnArguments[i])
        if (DIE *Arg =
            TheCU->constructVariableDIE(ArgDV, Scope->isAbstractScope())) {
          Children.push_back(Arg);
          if (ArgDV->isObjectPointer()) ObjectPointer = Arg;
        }

  // Collect lexical scope children first.
  const SmallVectorImpl<DbgVariable *> &Variables =ScopeVariables.lookup(Scope);
  for (unsigned i = 0, N = Variables.size(); i < N; ++i)
    if (DIE *Variable =
        TheCU->constructVariableDIE(Variables[i], Scope->isAbstractScope())) {
      Children.push_back(Variable);
      if (Variables[i]->isObjectPointer()) ObjectPointer = Variable;
    }
  const SmallVectorImpl<LexicalScope *> &Scopes = Scope->getChildren();
  for (unsigned j = 0, M = Scopes.size(); j < M; ++j)
    if (DIE *Nested = constructScopeDIE(TheCU, Scopes[j]))
      Children.push_back(Nested);
  return ObjectPointer;
}

// Construct a DIE for this scope.
DIE *DwarfDebug::constructScopeDIE(CompileUnit *TheCU, LexicalScope *Scope) {
  if (!Scope || !Scope->getScopeNode())
    return NULL;

  DIScope DS(Scope->getScopeNode());

  SmallVector<DIE *, 8> Children;
  DIE *ObjectPointer = NULL;
  bool ChildrenCreated = false;

  // We try to create the scope DIE first, then the children DIEs. This will
  // avoid creating un-used children then removing them later when we find out
  // the scope DIE is null.
  DIE *ScopeDIE = NULL;
  if (Scope->getInlinedAt())
    ScopeDIE = constructInlinedScopeDIE(TheCU, Scope);
  else if (DS.isSubprogram()) {
    ProcessedSPNodes.insert(DS);
    if (Scope->isAbstractScope()) {
      ScopeDIE = TheCU->getDIE(DS);
      // Note down abstract DIE.
      if (ScopeDIE)
        AbstractSPDies.insert(std::make_pair(DS, ScopeDIE));
    }
    else
      ScopeDIE = updateSubprogramScopeDIE(TheCU, DS);
  }
  else {
    // Early exit when we know the scope DIE is going to be null.
    if (isLexicalScopeDIENull(Scope))
      return NULL;

    // We create children here when we know the scope DIE is not going to be
    // null and the children will be added to the scope DIE.
    ObjectPointer = createScopeChildrenDIE(TheCU, Scope, Children);
    ChildrenCreated = true;

    // There is no need to emit empty lexical block DIE.
    std::pair<ImportedEntityMap::const_iterator,
              ImportedEntityMap::const_iterator> Range = std::equal_range(
        ScopesWithImportedEntities.begin(), ScopesWithImportedEntities.end(),
        std::pair<const MDNode *, const MDNode *>(DS, (const MDNode*)0),
        less_first());
    if (Children.empty() && Range.first == Range.second)
      return NULL;
    ScopeDIE = constructLexicalScopeDIE(TheCU, Scope);
    assert(ScopeDIE && "Scope DIE should not be null.");
    for (ImportedEntityMap::const_iterator i = Range.first; i != Range.second;
         ++i)
      constructImportedEntityDIE(TheCU, i->second, ScopeDIE);
  }

  if (!ScopeDIE) {
    assert(Children.empty() &&
           "We create children only when the scope DIE is not null.");
    return NULL;
  }
  if (!ChildrenCreated)
    // We create children when the scope DIE is not null.
    ObjectPointer = createScopeChildrenDIE(TheCU, Scope, Children);

  // Add children
  for (SmallVectorImpl<DIE *>::iterator I = Children.begin(),
         E = Children.end(); I != E; ++I)
    ScopeDIE->addChild(*I);

  if (DS.isSubprogram() && ObjectPointer != NULL)
    TheCU->addDIEEntry(ScopeDIE, dwarf::DW_AT_object_pointer, ObjectPointer);

  if (DS.isSubprogram())
    TheCU->addPubTypes(DISubprogram(DS));

  return ScopeDIE;
}

// Look up the source id with the given directory and source file names.
// If none currently exists, create a new id and insert it in the
// SourceIds map. This can update DirectoryNames and SourceFileNames maps
// as well.
unsigned DwarfDebug::getOrCreateSourceID(StringRef FileName,
                                         StringRef DirName, unsigned CUID) {
  // If we use .loc in assembly, we can't separate .file entries according to
  // compile units. Thus all files will belong to the default compile unit.

  // FIXME: add a better feature test than hasRawTextSupport. Even better,
  // extend .file to support this.
  if (Asm->TM.hasMCUseLoc() && Asm->OutStreamer.hasRawTextSupport())
    CUID = 0;

  // If FE did not provide a file name, then assume stdin.
  if (FileName.empty())
    return getOrCreateSourceID("<stdin>", StringRef(), CUID);

  // TODO: this might not belong here. See if we can factor this better.
  if (DirName == CompilationDir)
    DirName = "";

  // FileIDCUMap stores the current ID for the given compile unit.
  unsigned SrcId = FileIDCUMap[CUID] + 1;

  // We look up the CUID/file/dir by concatenating them with a zero byte.
  SmallString<128> NamePair;
  NamePair += utostr(CUID);
  NamePair += '\0';
  NamePair += DirName;
  NamePair += '\0'; // Zero bytes are not allowed in paths.
  NamePair += FileName;

  StringMapEntry<unsigned> &Ent = SourceIdMap.GetOrCreateValue(NamePair, SrcId);
  if (Ent.getValue() != SrcId)
    return Ent.getValue();

  FileIDCUMap[CUID] = SrcId;
  // Print out a .file directive to specify files for .loc directives.
  Asm->OutStreamer.EmitDwarfFileDirective(SrcId, DirName, FileName, CUID);

  return SrcId;
}

// Create new CompileUnit for the given metadata node with tag
// DW_TAG_compile_unit.
CompileUnit *DwarfDebug::constructCompileUnit(const MDNode *N) {
  DICompileUnit DIUnit(N);
  StringRef FN = DIUnit.getFilename();
  CompilationDir = DIUnit.getDirectory();

  DIE *Die = new DIE(dwarf::DW_TAG_compile_unit);
  CompileUnit *NewCU =
      new CompileUnit(GlobalCUIndexCount++, Die, N, Asm, this, &InfoHolder);

  FileIDCUMap[NewCU->getUniqueID()] = 0;
  // Call this to emit a .file directive if it wasn't emitted for the source
  // file this CU comes from yet.
  getOrCreateSourceID(FN, CompilationDir, NewCU->getUniqueID());

  NewCU->addString(Die, dwarf::DW_AT_producer, DIUnit.getProducer());
  NewCU->addUInt(Die, dwarf::DW_AT_language, dwarf::DW_FORM_data2,
                 DIUnit.getLanguage());
  NewCU->addString(Die, dwarf::DW_AT_name, FN);

  // 2.17.1 requires that we use DW_AT_low_pc for a single entry point
  // into an entity. We're using 0 (or a NULL label) for this. For
  // split dwarf it's in the skeleton CU so omit it here.
  if (!useSplitDwarf())
    NewCU->addLabelAddress(Die, dwarf::DW_AT_low_pc, NULL);

  // Define start line table label for each Compile Unit.
  MCSymbol *LineTableStartSym = Asm->GetTempSymbol("line_table_start",
                                                   NewCU->getUniqueID());
  Asm->OutStreamer.getContext().setMCLineTableSymbol(LineTableStartSym,
                                                     NewCU->getUniqueID());

  // Use a single line table if we are using .loc and generating assembly.
  bool UseTheFirstCU =
      (Asm->TM.hasMCUseLoc() && Asm->OutStreamer.hasRawTextSupport()) ||
      (NewCU->getUniqueID() == 0);

  if (!useSplitDwarf()) {
    // DW_AT_stmt_list is a offset of line number information for this
    // compile unit in debug_line section. For split dwarf this is
    // left in the skeleton CU and so not included.
    // The line table entries are not always emitted in assembly, so it
    // is not okay to use line_table_start here.
    if (Asm->MAI->doesDwarfUseRelocationsAcrossSections())
      NewCU->addLabel(Die, dwarf::DW_AT_stmt_list, dwarf::DW_FORM_sec_offset,
                      UseTheFirstCU ? Asm->GetTempSymbol("section_line")
                                    : LineTableStartSym);
    else if (UseTheFirstCU)
      NewCU->addUInt(Die, dwarf::DW_AT_stmt_list, dwarf::DW_FORM_data4, 0);
    else
      NewCU->addDelta(Die, dwarf::DW_AT_stmt_list, dwarf::DW_FORM_data4,
                      LineTableStartSym, DwarfLineSectionSym);

    // If we're using split dwarf the compilation dir is going to be in the
    // skeleton CU and so we don't need to duplicate it here.
    if (!CompilationDir.empty())
      NewCU->addString(Die, dwarf::DW_AT_comp_dir, CompilationDir);

    // Flags to let the linker know we have emitted new style pubnames. Only
    // emit it here if we don't have a skeleton CU for split dwarf.
    if (GenerateGnuPubSections) {
      if (Asm->MAI->doesDwarfUseRelocationsAcrossSections())
        NewCU->addLabel(Die, dwarf::DW_AT_GNU_pubnames,
                        dwarf::DW_FORM_sec_offset,
                        Asm->GetTempSymbol("gnu_pubnames",
                                           NewCU->getUniqueID()));
      else
        NewCU->addDelta(Die, dwarf::DW_AT_GNU_pubnames, dwarf::DW_FORM_data4,
                        Asm->GetTempSymbol("gnu_pubnames",
                                           NewCU->getUniqueID()),
                        DwarfGnuPubNamesSectionSym);

      if (Asm->MAI->doesDwarfUseRelocationsAcrossSections())
        NewCU->addLabel(Die, dwarf::DW_AT_GNU_pubtypes,
                        dwarf::DW_FORM_sec_offset,
                        Asm->GetTempSymbol("gnu_pubtypes",
                                           NewCU->getUniqueID()));
      else
        NewCU->addDelta(Die, dwarf::DW_AT_GNU_pubtypes, dwarf::DW_FORM_data4,
                        Asm->GetTempSymbol("gnu_pubtypes",
                                           NewCU->getUniqueID()),
                        DwarfGnuPubTypesSectionSym);
    }
  }

  if (DIUnit.isOptimized())
    NewCU->addFlag(Die, dwarf::DW_AT_APPLE_optimized);

  StringRef Flags = DIUnit.getFlags();
  if (!Flags.empty())
    NewCU->addString(Die, dwarf::DW_AT_APPLE_flags, Flags);

  if (unsigned RVer = DIUnit.getRunTimeVersion())
    NewCU->addUInt(Die, dwarf::DW_AT_APPLE_major_runtime_vers,
            dwarf::DW_FORM_data1, RVer);

  if (!FirstCU)
    FirstCU = NewCU;

  InfoHolder.addUnit(NewCU);

  CUMap.insert(std::make_pair(N, NewCU));
  return NewCU;
}

// Construct subprogram DIE.
void DwarfDebug::constructSubprogramDIE(CompileUnit *TheCU, const MDNode *N) {
  // FIXME: We should only call this routine once, however, during LTO if a
  // program is defined in multiple CUs we could end up calling it out of
  // beginModule as we walk the CUs.

  CompileUnit *&CURef = SPMap[N];
  if (CURef)
    return;
  CURef = TheCU;

  DISubprogram SP(N);
  if (!SP.isDefinition())
    // This is a method declaration which will be handled while constructing
    // class type.
    return;

  DIE *SubprogramDie = TheCU->getOrCreateSubprogramDIE(SP);

  // Expose as a global name.
  TheCU->addGlobalName(SP.getName(), SubprogramDie, resolve(SP.getContext()));
}

void DwarfDebug::constructImportedEntityDIE(CompileUnit *TheCU,
                                            const MDNode *N) {
  DIImportedEntity Module(N);
  if (!Module.Verify())
    return;
  if (DIE *D = TheCU->getOrCreateContextDIE(Module.getContext()))
    constructImportedEntityDIE(TheCU, Module, D);
}

void DwarfDebug::constructImportedEntityDIE(CompileUnit *TheCU, const MDNode *N,
                                            DIE *Context) {
  DIImportedEntity Module(N);
  if (!Module.Verify())
    return;
  return constructImportedEntityDIE(TheCU, Module, Context);
}

void DwarfDebug::constructImportedEntityDIE(CompileUnit *TheCU,
                                            const DIImportedEntity &Module,
                                            DIE *Context) {
  assert(Module.Verify() &&
         "Use one of the MDNode * overloads to handle invalid metadata");
  assert(Context && "Should always have a context for an imported_module");
  DIE *IMDie = new DIE(Module.getTag());
  TheCU->insertDIE(Module, IMDie);
  DIE *EntityDie;
  DIDescriptor Entity = Module.getEntity();
  if (Entity.isNameSpace())
    EntityDie = TheCU->getOrCreateNameSpace(DINameSpace(Entity));
  else if (Entity.isSubprogram())
    EntityDie = TheCU->getOrCreateSubprogramDIE(DISubprogram(Entity));
  else if (Entity.isType())
    EntityDie = TheCU->getOrCreateTypeDIE(DIType(Entity));
  else
    EntityDie = TheCU->getDIE(Entity);
  unsigned FileID = getOrCreateSourceID(Module.getContext().getFilename(),
                                        Module.getContext().getDirectory(),
                                        TheCU->getUniqueID());
  TheCU->addUInt(IMDie, dwarf::DW_AT_decl_file, 0, FileID);
  TheCU->addUInt(IMDie, dwarf::DW_AT_decl_line, 0, Module.getLineNumber());
  TheCU->addDIEEntry(IMDie, dwarf::DW_AT_import, EntityDie);
  StringRef Name = Module.getName();
  if (!Name.empty())
    TheCU->addString(IMDie, dwarf::DW_AT_name, Name);
  Context->addChild(IMDie);
}

// Emit all Dwarf sections that should come prior to the content. Create
// global DIEs and emit initial debug info sections. This is invoked by
// the target AsmPrinter.
void DwarfDebug::beginModule() {
  if (DisableDebugInfoPrinting)
    return;

  const Module *M = MMI->getModule();

  // If module has named metadata anchors then use them, otherwise scan the
  // module using debug info finder to collect debug info.
  NamedMDNode *CU_Nodes = M->getNamedMetadata("llvm.dbg.cu");
  if (!CU_Nodes)
    return;
  TypeIdentifierMap = generateDITypeIdentifierMap(CU_Nodes);

  // Emit initial sections so we can reference labels later.
  emitSectionLabels();

  for (unsigned i = 0, e = CU_Nodes->getNumOperands(); i != e; ++i) {
    DICompileUnit CUNode(CU_Nodes->getOperand(i));
    CompileUnit *CU = constructCompileUnit(CUNode);
    DIArray ImportedEntities = CUNode.getImportedEntities();
    for (unsigned i = 0, e = ImportedEntities.getNumElements(); i != e; ++i)
      ScopesWithImportedEntities.push_back(std::make_pair(
          DIImportedEntity(ImportedEntities.getElement(i)).getContext(),
          ImportedEntities.getElement(i)));
    std::sort(ScopesWithImportedEntities.begin(),
              ScopesWithImportedEntities.end(), less_first());
    DIArray GVs = CUNode.getGlobalVariables();
    for (unsigned i = 0, e = GVs.getNumElements(); i != e; ++i)
      CU->createGlobalVariableDIE(GVs.getElement(i));
    DIArray SPs = CUNode.getSubprograms();
    for (unsigned i = 0, e = SPs.getNumElements(); i != e; ++i)
      constructSubprogramDIE(CU, SPs.getElement(i));
    DIArray EnumTypes = CUNode.getEnumTypes();
    for (unsigned i = 0, e = EnumTypes.getNumElements(); i != e; ++i)
      CU->getOrCreateTypeDIE(EnumTypes.getElement(i));
    DIArray RetainedTypes = CUNode.getRetainedTypes();
    for (unsigned i = 0, e = RetainedTypes.getNumElements(); i != e; ++i)
      CU->getOrCreateTypeDIE(RetainedTypes.getElement(i));
    // Emit imported_modules last so that the relevant context is already
    // available.
    for (unsigned i = 0, e = ImportedEntities.getNumElements(); i != e; ++i)
      constructImportedEntityDIE(CU, ImportedEntities.getElement(i));
  }

  // Tell MMI that we have debug info.
  MMI->setDebugInfoAvailability(true);

  // Prime section data.
  SectionMap[Asm->getObjFileLowering().getTextSection()];
}

// Attach DW_AT_inline attribute with inlined subprogram DIEs.
void DwarfDebug::computeInlinedDIEs() {
  // Attach DW_AT_inline attribute with inlined subprogram DIEs.
  for (SmallPtrSet<DIE *, 4>::iterator AI = InlinedSubprogramDIEs.begin(),
         AE = InlinedSubprogramDIEs.end(); AI != AE; ++AI) {
    DIE *ISP = *AI;
    FirstCU->addUInt(ISP, dwarf::DW_AT_inline, 0, dwarf::DW_INL_inlined);
  }
  for (DenseMap<const MDNode *, DIE *>::iterator AI = AbstractSPDies.begin(),
         AE = AbstractSPDies.end(); AI != AE; ++AI) {
    DIE *ISP = AI->second;
    if (InlinedSubprogramDIEs.count(ISP))
      continue;
    FirstCU->addUInt(ISP, dwarf::DW_AT_inline, 0, dwarf::DW_INL_inlined);
  }
}

// Collect info for variables that were optimized out.
void DwarfDebug::collectDeadVariables() {
  const Module *M = MMI->getModule();
  DenseMap<const MDNode *, LexicalScope *> DeadFnScopeMap;

  if (NamedMDNode *CU_Nodes = M->getNamedMetadata("llvm.dbg.cu")) {
    for (unsigned i = 0, e = CU_Nodes->getNumOperands(); i != e; ++i) {
      DICompileUnit TheCU(CU_Nodes->getOperand(i));
      DIArray Subprograms = TheCU.getSubprograms();
      for (unsigned i = 0, e = Subprograms.getNumElements(); i != e; ++i) {
        DISubprogram SP(Subprograms.getElement(i));
        if (ProcessedSPNodes.count(SP) != 0)
          continue;
        if (!SP.isSubprogram())
          continue;
        if (!SP.isDefinition())
          continue;
        DIArray Variables = SP.getVariables();
        if (Variables.getNumElements() == 0)
          continue;

        LexicalScope *Scope =
            new LexicalScope(NULL, DIDescriptor(SP), NULL, false);
        DeadFnScopeMap[SP] = Scope;

        // Construct subprogram DIE and add variables DIEs.
        CompileUnit *SPCU = CUMap.lookup(TheCU);
        assert(SPCU && "Unable to find Compile Unit!");
	// FIXME: See the comment in constructSubprogramDIE about duplicate
	// subprogram DIEs.
	constructSubprogramDIE(SPCU, SP);
	DIE *SPDIE = SPCU->getDIE(SP);