DwarfDebug.cpp

  DEBUG(dbgs() << "Adding letter " << Str << " to hash.\n");
  assert(Str.size() == 1 && "Trying to add a too large letter?");
  HashValue SVal((const uint8_t *)Str.data(), Str.size());
  Hash.update(SVal);
}

// FIXME: These are copied and only slightly modified out of LEB128.h.

/// \brief Adds the unsigned in \p N to the hash in \p Hash. This also encodes
/// the unsigned as a ULEB128.
static void addULEB128ToHash(MD5 &Hash, uint64_t Value) {
  DEBUG(dbgs() << "Adding ULEB128 " << Value << " to hash.\n");
  do {
    uint8_t Byte = Value & 0x7f;
    Value >>= 7;
    if (Value != 0)
      Byte |= 0x80; // Mark this byte to show that more bytes will follow.
    Hash.update(Byte);
  } while (Value != 0);
}

/// \brief Including \p Parent adds the context of Parent to \p Hash.
static void addParentContextToHash(MD5 &Hash, DIE *Parent) {
  unsigned Tag = Parent->getTag();

  DEBUG(dbgs() << "Adding parent context to hash...\n");
  
  // For each surrounding type or namespace...
  if (Tag != dwarf::DW_TAG_namespace && Tag != dwarf::DW_TAG_class_type &&
      Tag != dwarf::DW_TAG_structure_type)
    return;

  // ... beginning with the outermost such construct...
  if (Parent->getParent() != NULL)
    addParentContextToHash(Hash, Parent->getParent());

  // Append the letter "C" to the sequence.
  addLetterToHash(Hash, "C");

  // Followed by the DWARF tag of the construct.
  addULEB128ToHash(Hash, Parent->getTag());

  // Then the name, taken from the DW_AT_name attribute.
  StringRef Name = getDIEStringAttr(Parent, dwarf::DW_AT_name);
  if (!Name.empty())
    addStringToHash(Hash, Name);
}

/// This is based on the type signature computation given in section 7.27 of the
/// DWARF4 standard. It is the md5 hash of a flattened description of the DIE.
static void addDIEODRSignature(MD5 &Hash, CompileUnit *CU, DIE *Die) {

  // Add the contexts to the hash.
  DIE *Parent = Die->getParent();
  if (Parent)
    addParentContextToHash(Hash, Parent);

  // Add the current DIE information.

  // Add the DWARF tag of the DIE.
  addULEB128ToHash(Hash, Die->getTag());

  // Add the name of the type to the hash.
  addStringToHash(Hash, getDIEStringAttr(Die, dwarf::DW_AT_name));

  // Now get the result.
  MD5::MD5Result Result;
  Hash.final(Result);

  // ... take the least significant 8 bytes and store those as the attribute.
  uint64_t Signature;
  memcpy(&Signature, &Result[8], 8);

  // FIXME: This should be added onto the type unit, not the type, but this
  // works as an intermediate stage.
  CU->addUInt(Die, dwarf::DW_AT_GNU_odr_signature, dwarf::DW_FORM_data8,
              Signature);
}

/// Return true if the current DIE is contained within an anonymous namespace.
static bool isContainedInAnonNamespace(DIE *Die) {
  DIE *Parent = Die->getParent();

  while (Parent) {
    if (Die->getTag() == dwarf::DW_TAG_namespace &&
        getDIEStringAttr(Die, dwarf::DW_AT_name) == "")
      return true;
    Parent = Parent->getParent();
  }

  return false;
}

void DwarfDebug::finalizeModuleInfo() {
  // Collect info for variables that were optimized out.
  collectDeadVariables();

  // Attach DW_AT_inline attribute with inlined subprogram DIEs.
  computeInlinedDIEs();

  // Emit DW_AT_containing_type attribute to connect types with their
  // vtable holding type.
  for (DenseMap<const MDNode *, CompileUnit *>::iterator CUI = CUMap.begin(),
         CUE = CUMap.end(); CUI != CUE; ++CUI) {
    CompileUnit *TheCU = CUI->second;
    TheCU->constructContainingTypeDIEs();
  }

  // For types that we'd like to move to type units or ODR check go ahead
  // and either move the types out or add the ODR attribute now.
  // FIXME: Do type splitting.
  for (unsigned i = 0, e = TypeUnits.size(); i != e; ++i) {
    MD5 Hash;
    DIE *Die = TypeUnits[i];
    // If we're in C++ and we want to generate the hash then go ahead and do
    // that now.
    if (GenerateODRHash &&
        CUMap.begin()->second->getLanguage() == dwarf::DW_LANG_C_plus_plus &&
        !isContainedInAnonNamespace(Die))
      addDIEODRSignature(Hash, CUMap.begin()->second, Die);
  }

   // Compute DIE offsets and sizes.
  InfoHolder.computeSizeAndOffsets();
  if (useSplitDwarf())
    SkeletonHolder.computeSizeAndOffsets();
}

void DwarfDebug::endSections() {
  // Standard sections final addresses.
  Asm->OutStreamer.SwitchSection(Asm->getObjFileLowering().getTextSection());
  Asm->OutStreamer.EmitLabel(Asm->GetTempSymbol("text_end"));
  Asm->OutStreamer.SwitchSection(Asm->getObjFileLowering().getDataSection());
  Asm->OutStreamer.EmitLabel(Asm->GetTempSymbol("data_end"));

  // End text sections.
  for (unsigned I = 0, E = SectionMap.size(); I != E; ++I) {
    Asm->OutStreamer.SwitchSection(SectionMap[I]);
    Asm->OutStreamer.EmitLabel(Asm->GetTempSymbol("section_end", I+1));
  }
}

// Emit all Dwarf sections that should come after the content.
void DwarfDebug::endModule() {

  if (!FirstCU) return;

  // End any existing sections.
  // TODO: Does this need to happen?
  endSections();

  // Finalize the debug info for the module.
  finalizeModuleInfo();

  if (!useSplitDwarf()) {
    // Emit all the DIEs into a debug info section.
    emitDebugInfo();

    // Corresponding abbreviations into a abbrev section.
    emitAbbreviations();

    // Emit info into a debug loc section.
    emitDebugLoc();

    // Emit info into a debug aranges section.
    emitDebugARanges();

    // Emit info into a debug ranges section.
    emitDebugRanges();

    // Emit info into a debug macinfo section.
    emitDebugMacInfo();

    // Emit inline info.
    // TODO: When we don't need the option anymore we
    // can remove all of the code that this section
    // depends upon.
    if (useDarwinGDBCompat())
      emitDebugInlineInfo();
  } else {
    // TODO: Fill this in for separated debug sections and separate
    // out information into new sections.

    // Emit the debug info section and compile units.
    emitDebugInfo();
    emitDebugInfoDWO();

    // Corresponding abbreviations into a abbrev section.
    emitAbbreviations();
    emitDebugAbbrevDWO();

    // Emit info into a debug loc section.
    emitDebugLoc();

    // Emit info into a debug aranges section.
    emitDebugARanges();

    // Emit info into a debug ranges section.
    emitDebugRanges();

    // Emit info into a debug macinfo section.
    emitDebugMacInfo();

    // Emit DWO addresses.
    InfoHolder.emitAddresses(Asm->getObjFileLowering().getDwarfAddrSection());

    // Emit inline info.
    // TODO: When we don't need the option anymore we
    // can remove all of the code that this section
    // depends upon.
    if (useDarwinGDBCompat())
      emitDebugInlineInfo();
  }

  // Emit info into the dwarf accelerator table sections.
  if (useDwarfAccelTables()) {
    emitAccelNames();
    emitAccelObjC();
    emitAccelNamespaces();
    emitAccelTypes();
  }

  // Emit info into a debug pubnames section, if requested.
  if (GenerateDwarfPubNamesSection)
    emitDebugPubnames();

  // Emit info into a debug pubtypes section.
  // TODO: When we don't need the option anymore we can
  // remove all of the code that adds to the table.
  if (useDarwinGDBCompat())
    emitDebugPubTypes();

  // Finally emit string information into a string table.
  emitDebugStr();
  if (useSplitDwarf())
    emitDebugStrDWO();

  // clean up.
  SPMap.clear();
  for (DenseMap<const MDNode *, CompileUnit *>::iterator I = CUMap.begin(),
         E = CUMap.end(); I != E; ++I)
    delete I->second;

  for (SmallVectorImpl<CompileUnit *>::iterator I = SkeletonCUs.begin(),
         E = SkeletonCUs.end(); I != E; ++I)
    delete *I;

  // Reset these for the next Module if we have one.
  FirstCU = NULL;
}

// Find abstract variable, if any, associated with Var.
DbgVariable *DwarfDebug::findAbstractVariable(DIVariable &DV,
                                              DebugLoc ScopeLoc) {
  LLVMContext &Ctx = DV->getContext();
  // More then one inlined variable corresponds to one abstract variable.
  DIVariable Var = cleanseInlinedVariable(DV, Ctx);
  DbgVariable *AbsDbgVariable = AbstractVariables.lookup(Var);
  if (AbsDbgVariable)
    return AbsDbgVariable;

  LexicalScope *Scope = LScopes.findAbstractScope(ScopeLoc.getScope(Ctx));
  if (!Scope)
    return NULL;

  AbsDbgVariable = new DbgVariable(Var, NULL);
  addScopeVariable(Scope, AbsDbgVariable);
  AbstractVariables[Var] = AbsDbgVariable;
  return AbsDbgVariable;
}

// If Var is a current function argument then add it to CurrentFnArguments list.
bool DwarfDebug::addCurrentFnArgument(const MachineFunction *MF,
                                      DbgVariable *Var, LexicalScope *Scope) {
  if (!LScopes.isCurrentFunctionScope(Scope))
    return false;
  DIVariable DV = Var->getVariable();
  if (DV.getTag() != dwarf::DW_TAG_arg_variable)
    return false;
  unsigned ArgNo = DV.getArgNumber();
  if (ArgNo == 0)
    return false;

  size_t Size = CurrentFnArguments.size();
  if (Size == 0)
    CurrentFnArguments.resize(MF->getFunction()->arg_size());
  // llvm::Function argument size is not good indicator of how many
  // arguments does the function have at source level.
  if (ArgNo > Size)
    CurrentFnArguments.resize(ArgNo * 2);
  CurrentFnArguments[ArgNo - 1] = Var;
  return true;
}

// Collect variable information from side table maintained by MMI.
void
DwarfDebug::collectVariableInfoFromMMITable(const MachineFunction *MF,
                                   SmallPtrSet<const MDNode *, 16> &Processed) {
  MachineModuleInfo::VariableDbgInfoMapTy &VMap = MMI->getVariableDbgInfo();
  for (MachineModuleInfo::VariableDbgInfoMapTy::iterator VI = VMap.begin(),
         VE = VMap.end(); VI != VE; ++VI) {
    const MDNode *Var = VI->first;
    if (!Var) continue;
    Processed.insert(Var);
    DIVariable DV(Var);
    const std::pair<unsigned, DebugLoc> &VP = VI->second;

    LexicalScope *Scope = LScopes.findLexicalScope(VP.second);

    // If variable scope is not found then skip this variable.
    if (Scope == 0)
      continue;

    DbgVariable *AbsDbgVariable = findAbstractVariable(DV, VP.second);
    DbgVariable *RegVar = new DbgVariable(DV, AbsDbgVariable);
    RegVar->setFrameIndex(VP.first);
    if (!addCurrentFnArgument(MF, RegVar, Scope))
      addScopeVariable(Scope, RegVar);
    if (AbsDbgVariable)
      AbsDbgVariable->setFrameIndex(VP.first);
  }
}

// Return true if debug value, encoded by DBG_VALUE instruction, is in a
// defined reg.
static bool isDbgValueInDefinedReg(const MachineInstr *MI) {
  assert(MI->isDebugValue() && "Invalid DBG_VALUE machine instruction!");
  return MI->getNumOperands() == 3 &&
         MI->getOperand(0).isReg() && MI->getOperand(0).getReg() &&
         (MI->getOperand(1).isImm() ||
          (MI->getOperand(1).isReg() && MI->getOperand(1).getReg() == 0U));
}

// Get .debug_loc entry for the instruction range starting at MI.
static DotDebugLocEntry getDebugLocEntry(AsmPrinter *Asm,
                                         const MCSymbol *FLabel,
                                         const MCSymbol *SLabel,
                                         const MachineInstr *MI) {
  const MDNode *Var =  MI->getOperand(MI->getNumOperands() - 1).getMetadata();

  assert(MI->getNumOperands() == 3);
  if (MI->getOperand(0).isReg()) {
    MachineLocation MLoc;
    // If the second operand is an immediate, this is a
    // register-indirect address.
    if (!MI->getOperand(1).isImm())
      MLoc.set(MI->getOperand(0).getReg());
    else
      MLoc.set(MI->getOperand(0).getReg(), MI->getOperand(1).getImm());
    return DotDebugLocEntry(FLabel, SLabel, MLoc, Var);
  }
  if (MI->getOperand(0).isImm())
    return DotDebugLocEntry(FLabel, SLabel, MI->getOperand(0).getImm());
  if (MI->getOperand(0).isFPImm())
    return DotDebugLocEntry(FLabel, SLabel, MI->getOperand(0).getFPImm());
  if (MI->getOperand(0).isCImm())
    return DotDebugLocEntry(FLabel, SLabel, MI->getOperand(0).getCImm());

  llvm_unreachable("Unexpected 3 operand DBG_VALUE instruction!");
}

// Find variables for each lexical scope.
void
DwarfDebug::collectVariableInfo(const MachineFunction *MF,
                                SmallPtrSet<const MDNode *, 16> &Processed) {

  // Grab the variable info that was squirreled away in the MMI side-table.
  collectVariableInfoFromMMITable(MF, Processed);

  for (SmallVectorImpl<const MDNode*>::const_iterator
         UVI = UserVariables.begin(), UVE = UserVariables.end(); UVI != UVE;
         ++UVI) {
    const MDNode *Var = *UVI;
    if (Processed.count(Var))
      continue;

    // History contains relevant DBG_VALUE instructions for Var and instructions
    // clobbering it.
    SmallVectorImpl<const MachineInstr*> &History = DbgValues[Var];
    if (History.empty())
      continue;
    const MachineInstr *MInsn = History.front();

    DIVariable DV(Var);
    LexicalScope *Scope = NULL;
    if (DV.getTag() == dwarf::DW_TAG_arg_variable &&
        DISubprogram(DV.getContext()).describes(MF->getFunction()))
      Scope = LScopes.getCurrentFunctionScope();
    else if (MDNode *IA = DV.getInlinedAt())
      Scope = LScopes.findInlinedScope(DebugLoc::getFromDILocation(IA));
    else
      Scope = LScopes.findLexicalScope(cast<MDNode>(DV->getOperand(1)));
    // If variable scope is not found then skip this variable.
    if (!Scope)
      continue;

    Processed.insert(DV);
    assert(MInsn->isDebugValue() && "History must begin with debug value");
    DbgVariable *AbsVar = findAbstractVariable(DV, MInsn->getDebugLoc());
    DbgVariable *RegVar = new DbgVariable(DV, AbsVar);
    if (!addCurrentFnArgument(MF, RegVar, Scope))
      addScopeVariable(Scope, RegVar);
    if (AbsVar)
      AbsVar->setMInsn(MInsn);

    // Simplify ranges that are fully coalesced.
    if (History.size() <= 1 || (History.size() == 2 &&
                                MInsn->isIdenticalTo(History.back()))) {
      RegVar->setMInsn(MInsn);
      continue;
    }

    // Handle multiple DBG_VALUE instructions describing one variable.
    RegVar->setDotDebugLocOffset(DotDebugLocEntries.size());

    for (SmallVectorImpl<const MachineInstr*>::const_iterator
           HI = History.begin(), HE = History.end(); HI != HE; ++HI) {
      const MachineInstr *Begin = *HI;
      assert(Begin->isDebugValue() && "Invalid History entry");

      // Check if DBG_VALUE is truncating a range.
      if (Begin->getNumOperands() > 1 && Begin->getOperand(0).isReg()
          && !Begin->getOperand(0).getReg())
        continue;

      // Compute the range for a register location.
      const MCSymbol *FLabel = getLabelBeforeInsn(Begin);
      const MCSymbol *SLabel = 0;

      if (HI + 1 == HE)
        // If Begin is the last instruction in History then its value is valid
        // until the end of the function.
        SLabel = FunctionEndSym;
      else {
        const MachineInstr *End = HI[1];
        DEBUG(dbgs() << "DotDebugLoc Pair:\n"
              << "\t" << *Begin << "\t" << *End << "\n");
        if (End->isDebugValue())
          SLabel = getLabelBeforeInsn(End);
        else {
          // End is a normal instruction clobbering the range.
          SLabel = getLabelAfterInsn(End);
          assert(SLabel && "Forgot label after clobber instruction");
          ++HI;
        }
      }

      // The value is valid until the next DBG_VALUE or clobber.
      DotDebugLocEntries.push_back(getDebugLocEntry(Asm, FLabel, SLabel,
                                                    Begin));
    }
    DotDebugLocEntries.push_back(DotDebugLocEntry());
  }

  // Collect info for variables that were optimized out.
  LexicalScope *FnScope = LScopes.getCurrentFunctionScope();
  DIArray Variables = DISubprogram(FnScope->getScopeNode()).getVariables();
  for (unsigned i = 0, e = Variables.getNumElements(); i != e; ++i) {
    DIVariable DV(Variables.getElement(i));
    if (!DV || !DV.isVariable() || !Processed.insert(DV))
      continue;
    if (LexicalScope *Scope = LScopes.findLexicalScope(DV.getContext()))
      addScopeVariable(Scope, new DbgVariable(DV, NULL));
  }
}

// Return Label preceding the instruction.
MCSymbol *DwarfDebug::getLabelBeforeInsn(const MachineInstr *MI) {
  MCSymbol *Label = LabelsBeforeInsn.lookup(MI);
  assert(Label && "Didn't insert label before instruction");
  return Label;
}

// Return Label immediately following the instruction.
MCSymbol *DwarfDebug::getLabelAfterInsn(const MachineInstr *MI) {
  return LabelsAfterInsn.lookup(MI);
}

// Process beginning of an instruction.
void DwarfDebug::beginInstruction(const MachineInstr *MI) {
  // Check if source location changes, but ignore DBG_VALUE locations.
  if (!MI->isDebugValue()) {
    DebugLoc DL = MI->getDebugLoc();
    if (DL != PrevInstLoc && (!DL.isUnknown() || UnknownLocations)) {
      unsigned Flags = 0;
      PrevInstLoc = DL;
      if (DL == PrologEndLoc) {
        Flags |= DWARF2_FLAG_PROLOGUE_END;
        PrologEndLoc = DebugLoc();
      }
      if (PrologEndLoc.isUnknown())
        Flags |= DWARF2_FLAG_IS_STMT;

      if (!DL.isUnknown()) {
        const MDNode *Scope = DL.getScope(Asm->MF->getFunction()->getContext());
        recordSourceLine(DL.getLine(), DL.getCol(), Scope, Flags);
      } else
        recordSourceLine(0, 0, 0, 0);
    }
  }

  // Insert labels where requested.
  DenseMap<const MachineInstr*, MCSymbol*>::iterator I =
    LabelsBeforeInsn.find(MI);

  // No label needed.
  if (I == LabelsBeforeInsn.end())
    return;

  // Label already assigned.
  if (I->second)
    return;

  if (!PrevLabel) {
    PrevLabel = MMI->getContext().CreateTempSymbol();
    Asm->OutStreamer.EmitLabel(PrevLabel);
  }
  I->second = PrevLabel;
}

// Process end of an instruction.
void DwarfDebug::endInstruction(const MachineInstr *MI) {
  // Don't create a new label after DBG_VALUE instructions.
  // They don't generate code.
  if (!MI->isDebugValue())
    PrevLabel = 0;

  DenseMap<const MachineInstr*, MCSymbol*>::iterator I =
    LabelsAfterInsn.find(MI);

  // No label needed.
  if (I == LabelsAfterInsn.end())
    return;

  // Label already assigned.
  if (I->second)
    return;

  // We need a label after this instruction.
  if (!PrevLabel) {
    PrevLabel = MMI->getContext().CreateTempSymbol();
    Asm->OutStreamer.EmitLabel(PrevLabel);
  }
  I->second = PrevLabel;
}

// Each LexicalScope has first instruction and last instruction to mark
// beginning and end of a scope respectively. Create an inverse map that list
// scopes starts (and ends) with an instruction. One instruction may start (or
// end) multiple scopes. Ignore scopes that are not reachable.
void DwarfDebug::identifyScopeMarkers() {
  SmallVector<LexicalScope *, 4> WorkList;
  WorkList.push_back(LScopes.getCurrentFunctionScope());
  while (!WorkList.empty()) {
    LexicalScope *S = WorkList.pop_back_val();

    const SmallVectorImpl<LexicalScope *> &Children = S->getChildren();
    if (!Children.empty())
      for (SmallVectorImpl<LexicalScope *>::const_iterator SI = Children.begin(),
             SE = Children.end(); SI != SE; ++SI)
        WorkList.push_back(*SI);

    if (S->isAbstractScope())
      continue;

    const SmallVectorImpl<InsnRange> &Ranges = S->getRanges();
    if (Ranges.empty())
      continue;
    for (SmallVectorImpl<InsnRange>::const_iterator RI = Ranges.begin(),
           RE = Ranges.end(); RI != RE; ++RI) {
      assert(RI->first && "InsnRange does not have first instruction!");
      assert(RI->second && "InsnRange does not have second instruction!");
      requestLabelBeforeInsn(RI->first);
      requestLabelAfterInsn(RI->second);
    }
  }
}

// Get MDNode for DebugLoc's scope.
static MDNode *getScopeNode(DebugLoc DL, const LLVMContext &Ctx) {
  if (MDNode *InlinedAt = DL.getInlinedAt(Ctx))
    return getScopeNode(DebugLoc::getFromDILocation(InlinedAt), Ctx);
  return DL.getScope(Ctx);
}

// Walk up the scope chain of given debug loc and find line number info
// for the function.
static DebugLoc getFnDebugLoc(DebugLoc DL, const LLVMContext &Ctx) {
  const MDNode *Scope = getScopeNode(DL, Ctx);
  DISubprogram SP = getDISubprogram(Scope);
  if (SP.isSubprogram()) {
    // Check for number of operands since the compatibility is
    // cheap here.
    if (SP->getNumOperands() > 19)
      return DebugLoc::get(SP.getScopeLineNumber(), 0, SP);
    else
      return DebugLoc::get(SP.getLineNumber(), 0, SP);
  }

  return DebugLoc();
}

// Gather pre-function debug information.  Assumes being called immediately
// after the function entry point has been emitted.
void DwarfDebug::beginFunction(const MachineFunction *MF) {
  if (!MMI->hasDebugInfo()) return;
  LScopes.initialize(*MF);
  if (LScopes.empty()) return;
  identifyScopeMarkers();

  // Set DwarfCompileUnitID in MCContext to the Compile Unit this function
  // belongs to.
  LexicalScope *FnScope = LScopes.getCurrentFunctionScope();
  CompileUnit *TheCU = SPMap.lookup(FnScope->getScopeNode());
  assert(TheCU && "Unable to find compile unit!");
  if (Asm->TM.hasMCUseLoc() &&
      Asm->OutStreamer.getKind() == MCStreamer::SK_AsmStreamer)
    // Use a single line table if we are using .loc and generating assembly.
    Asm->OutStreamer.getContext().setDwarfCompileUnitID(0);
  else
    Asm->OutStreamer.getContext().setDwarfCompileUnitID(TheCU->getUniqueID());

  FunctionBeginSym = Asm->GetTempSymbol("func_begin",
                                        Asm->getFunctionNumber());
  // Assumes in correct section after the entry point.
  Asm->OutStreamer.EmitLabel(FunctionBeginSym);

  assert(UserVariables.empty() && DbgValues.empty() && "Maps weren't cleaned");

  const TargetRegisterInfo *TRI = Asm->TM.getRegisterInfo();
  // LiveUserVar - Map physreg numbers to the MDNode they contain.
  std::vector<const MDNode*> LiveUserVar(TRI->getNumRegs());

  for (MachineFunction::const_iterator I = MF->begin(), E = MF->end();
       I != E; ++I) {
    bool AtBlockEntry = true;
    for (MachineBasicBlock::const_iterator II = I->begin(), IE = I->end();
         II != IE; ++II) {
      const MachineInstr *MI = II;

      if (MI->isDebugValue()) {
        assert(MI->getNumOperands() > 1 && "Invalid machine instruction!");

        // Keep track of user variables.
        const MDNode *Var =
          MI->getOperand(MI->getNumOperands() - 1).getMetadata();

        // Variable is in a register, we need to check for clobbers.
        if (isDbgValueInDefinedReg(MI))
          LiveUserVar[MI->getOperand(0).getReg()] = Var;

        // Check the history of this variable.
        SmallVectorImpl<const MachineInstr*> &History = DbgValues[Var];
        if (History.empty()) {
          UserVariables.push_back(Var);
          // The first mention of a function argument gets the FunctionBeginSym
          // label, so arguments are visible when breaking at function entry.
          DIVariable DV(Var);
          if (DV.isVariable() && DV.getTag() == dwarf::DW_TAG_arg_variable &&
              DISubprogram(getDISubprogram(DV.getContext()))
                .describes(MF->getFunction()))
            LabelsBeforeInsn[MI] = FunctionBeginSym;
        } else {
          // We have seen this variable before. Try to coalesce DBG_VALUEs.
          const MachineInstr *Prev = History.back();
          if (Prev->isDebugValue()) {
            // Coalesce identical entries at the end of History.
            if (History.size() >= 2 &&
                Prev->isIdenticalTo(History[History.size() - 2])) {
              DEBUG(dbgs() << "Coalescing identical DBG_VALUE entries:\n"
                    << "\t" << *Prev
                    << "\t" << *History[History.size() - 2] << "\n");
              History.pop_back();
            }

            // Terminate old register assignments that don't reach MI;
            MachineFunction::const_iterator PrevMBB = Prev->getParent();
            if (PrevMBB != I && (!AtBlockEntry || llvm::next(PrevMBB) != I) &&
                isDbgValueInDefinedReg(Prev)) {
              // Previous register assignment needs to terminate at the end of
              // its basic block.
              MachineBasicBlock::const_iterator LastMI =
                PrevMBB->getLastNonDebugInstr();
              if (LastMI == PrevMBB->end()) {
                // Drop DBG_VALUE for empty range.
                DEBUG(dbgs() << "Dropping DBG_VALUE for empty range:\n"
                      << "\t" << *Prev << "\n");
                History.pop_back();
              } else if (llvm::next(PrevMBB) != PrevMBB->getParent()->end())
                // Terminate after LastMI.
                History.push_back(LastMI);
            }
          }
        }
        History.push_back(MI);
      } else {
        // Not a DBG_VALUE instruction.
        if (!MI->isLabel())
          AtBlockEntry = false;

        // First known non-DBG_VALUE and non-frame setup location marks
        // the beginning of the function body.
        if (!MI->getFlag(MachineInstr::FrameSetup) &&
            (PrologEndLoc.isUnknown() && !MI->getDebugLoc().isUnknown()))
          PrologEndLoc = MI->getDebugLoc();

        // Check if the instruction clobbers any registers with debug vars.
        for (MachineInstr::const_mop_iterator MOI = MI->operands_begin(),
               MOE = MI->operands_end(); MOI != MOE; ++MOI) {
          if (!MOI->isReg() || !MOI->isDef() || !MOI->getReg())
            continue;
          for (MCRegAliasIterator AI(MOI->getReg(), TRI, true);
               AI.isValid(); ++AI) {
            unsigned Reg = *AI;
            const MDNode *Var = LiveUserVar[Reg];
            if (!Var)
              continue;
            // Reg is now clobbered.
            LiveUserVar[Reg] = 0;

            // Was MD last defined by a DBG_VALUE referring to Reg?
            DbgValueHistoryMap::iterator HistI = DbgValues.find(Var);
            if (HistI == DbgValues.end())
              continue;
            SmallVectorImpl<const MachineInstr*> &History = HistI->second;
            if (History.empty())
              continue;
            const MachineInstr *Prev = History.back();
            // Sanity-check: Register assignments are terminated at the end of
            // their block.
            if (!Prev->isDebugValue() || Prev->getParent() != MI->getParent())
              continue;
            // Is the variable still in Reg?
            if (!isDbgValueInDefinedReg(Prev) ||
                Prev->getOperand(0).getReg() != Reg)
              continue;
            // Var is clobbered. Make sure the next instruction gets a label.
            History.push_back(MI);
          }
        }
      }
    }
  }

  for (DbgValueHistoryMap::iterator I = DbgValues.begin(), E = DbgValues.end();
       I != E; ++I) {
    SmallVectorImpl<const MachineInstr*> &History = I->second;
    if (History.empty())
      continue;

    // Make sure the final register assignments are terminated.
    const MachineInstr *Prev = History.back();
    if (Prev->isDebugValue() && isDbgValueInDefinedReg(Prev)) {
      const MachineBasicBlock *PrevMBB = Prev->getParent();
      MachineBasicBlock::const_iterator LastMI =
        PrevMBB->getLastNonDebugInstr();
      if (LastMI == PrevMBB->end())
        // Drop DBG_VALUE for empty range.
        History.pop_back();
      else if (PrevMBB != &PrevMBB->getParent()->back()) {
        // Terminate after LastMI.
        History.push_back(LastMI);
      }
    }
    // Request labels for the full history.
    for (unsigned i = 0, e = History.size(); i != e; ++i) {
      const MachineInstr *MI = History[i];
      if (MI->isDebugValue())
        requestLabelBeforeInsn(MI);
      else
        requestLabelAfterInsn(MI);
    }
  }

  PrevInstLoc = DebugLoc();
  PrevLabel = FunctionBeginSym;

  // Record beginning of function.
  if (!PrologEndLoc.isUnknown()) {
    DebugLoc FnStartDL = getFnDebugLoc(PrologEndLoc,
                                       MF->getFunction()->getContext());
    recordSourceLine(FnStartDL.getLine(), FnStartDL.getCol(),
                     FnStartDL.getScope(MF->getFunction()->getContext()),
    // We'd like to list the prologue as "not statements" but GDB behaves
    // poorly if we do that. Revisit this with caution/GDB (7.5+) testing.
                     DWARF2_FLAG_IS_STMT);
  }
}

void DwarfDebug::addScopeVariable(LexicalScope *LS, DbgVariable *Var) {
  SmallVectorImpl<DbgVariable *> &Vars = ScopeVariables[LS];
  DIVariable DV = Var->getVariable();
  // Variables with positive arg numbers are parameters.
  if (unsigned ArgNum = DV.getArgNumber()) {
    // Keep all parameters in order at the start of the variable list to ensure
    // function types are correct (no out-of-order parameters)
    //
    // This could be improved by only doing it for optimized builds (unoptimized
    // builds have the right order to begin with), searching from the back (this
    // would catch the unoptimized case quickly), or doing a binary search
    // rather than linear search.
    SmallVectorImpl<DbgVariable *>::iterator I = Vars.begin();
    while (I != Vars.end()) {
      unsigned CurNum = (*I)->getVariable().getArgNumber();
      // A local (non-parameter) variable has been found, insert immediately
      // before it.
      if (CurNum == 0)
        break;
      // A later indexed parameter has been found, insert immediately before it.
      if (CurNum > ArgNum)
        break;
      ++I;
    }
    Vars.insert(I, Var);
    return;
  }

  Vars.push_back(Var);
}

// Gather and emit post-function debug information.
void DwarfDebug::endFunction(const MachineFunction *MF) {
  if (!MMI->hasDebugInfo() || LScopes.empty()) return;

  // Define end label for subprogram.
  FunctionEndSym = Asm->GetTempSymbol("func_end",
                                      Asm->getFunctionNumber());
  // Assumes in correct section after the entry point.
  Asm->OutStreamer.EmitLabel(FunctionEndSym);
  // Set DwarfCompileUnitID in MCContext to default value.
  Asm->OutStreamer.getContext().setDwarfCompileUnitID(0);

  SmallPtrSet<const MDNode *, 16> ProcessedVars;
  collectVariableInfo(MF, ProcessedVars);

  LexicalScope *FnScope = LScopes.getCurrentFunctionScope();
  CompileUnit *TheCU = SPMap.lookup(FnScope->getScopeNode());
  assert(TheCU && "Unable to find compile unit!");

  // Construct abstract scopes.
  ArrayRef<LexicalScope *> AList = LScopes.getAbstractScopesList();
  for (unsigned i = 0, e = AList.size(); i != e; ++i) {
    LexicalScope *AScope = AList[i];
    DISubprogram SP(AScope->getScopeNode());
    if (SP.isSubprogram()) {
      // Collect info for variables that were optimized out.
      DIArray Variables = SP.getVariables();
      for (unsigned i = 0, e = Variables.getNumElements(); i != e; ++i) {
        DIVariable DV(Variables.getElement(i));
        if (!DV || !DV.isVariable() || !ProcessedVars.insert(DV))
          continue;
        // Check that DbgVariable for DV wasn't created earlier, when
        // findAbstractVariable() was called for inlined instance of DV.
        LLVMContext &Ctx = DV->getContext();
        DIVariable CleanDV = cleanseInlinedVariable(DV, Ctx);
        if (AbstractVariables.lookup(CleanDV))
          continue;
        if (LexicalScope *Scope = LScopes.findAbstractScope(DV.getContext()))
          addScopeVariable(Scope, new DbgVariable(DV, NULL));
      }
    }
    if (ProcessedSPNodes.count(AScope->getScopeNode()) == 0)
      constructScopeDIE(TheCU, AScope);
  }

  DIE *CurFnDIE = constructScopeDIE(TheCU, FnScope);

  if (!MF->getTarget().Options.DisableFramePointerElim(*MF))
    TheCU->addFlag(CurFnDIE, dwarf::DW_AT_APPLE_omit_frame_ptr);

  // Clear debug info
  for (ScopeVariablesMap::iterator
         I = ScopeVariables.begin(), E = ScopeVariables.end(); I != E; ++I)
    DeleteContainerPointers(I->second);
  ScopeVariables.clear();
  DeleteContainerPointers(CurrentFnArguments);
  UserVariables.clear();
  DbgValues.clear();
  AbstractVariables.clear();
  LabelsBeforeInsn.clear();
  LabelsAfterInsn.clear();
  PrevLabel = NULL;
}

// Register a source line with debug info. Returns the  unique label that was
// emitted and which provides correspondence to the source line list.
void DwarfDebug::recordSourceLine(unsigned Line, unsigned Col, const MDNode *S,
                                  unsigned Flags) {
  StringRef Fn;
  StringRef Dir;
  unsigned Src = 1;
  if (S) {
    DIDescriptor Scope(S);

    if (Scope.isCompileUnit()) {
      DICompileUnit CU(S);
      Fn = CU.getFilename();
      Dir = CU.getDirectory();
    } else if (Scope.isFile()) {
      DIFile F(S);
      Fn = F.getFilename();
      Dir = F.getDirectory();
    } else if (Scope.isSubprogram()) {
      DISubprogram SP(S);
      Fn = SP.getFilename();
      Dir = SP.getDirectory();
    } else if (Scope.isLexicalBlockFile()) {
      DILexicalBlockFile DBF(S);
      Fn = DBF.getFilename();
      Dir = DBF.getDirectory();
    } else if (Scope.isLexicalBlock()) {
      DILexicalBlock DB(S);
      Fn = DB.getFilename();
      Dir = DB.getDirectory();
    } else
      llvm_unreachable("Unexpected scope info");

    Src = getOrCreateSourceID(Fn, Dir,
            Asm->OutStreamer.getContext().getDwarfCompileUnitID());
  }
  Asm->OutStreamer.EmitDwarfLocDirective(Src, Line, Col, Flags, 0, 0, Fn);
}

//===----------------------------------------------------------------------===//
// Emit Methods
//===----------------------------------------------------------------------===//

// Compute the size and offset of a DIE.
unsigned
DwarfUnits::computeSizeAndOffset(DIE *Die, unsigned Offset) {
  // Get the children.
  const std::vector<DIE *> &Children = Die->getChildren();

  // Record the abbreviation.
  assignAbbrevNumber(Die->getAbbrev());

  // Get the abbreviation for this DIE.
  unsigned AbbrevNumber = Die->getAbbrevNumber();
  const DIEAbbrev *Abbrev = Abbreviations->at(AbbrevNumber - 1);

  // Set DIE offset
  Die->setOffset(Offset);

  // Start the size with the size of abbreviation code.
  Offset += MCAsmInfo::getULEB128Size(AbbrevNumber);

  const SmallVectorImpl<DIEValue*> &Values = Die->getValues();
  const SmallVectorImpl<DIEAbbrevData> &AbbrevData = Abbrev->getData();

  // Size the DIE attribute values.
  for (unsigned i = 0, N = Values.size(); i < N; ++i)
    // Size attribute value.
    Offset += Values[i]->SizeOf(Asm, AbbrevData[i].getForm());

  // Size the DIE children if any.
  if (!Children.empty()) {
    assert(Abbrev->getChildrenFlag() == dwarf::DW_CHILDREN_yes &&
           "Children flag not set");

    for (unsigned j = 0, M = Children.size(); j < M; ++j)
      Offset = computeSizeAndOffset(Children[j], Offset);

    // End of children marker.
    Offset += sizeof(int8_t);
  }

  Die->setSize(Offset - Die->getOffset());
  return Offset;
}

// Compute the size and offset of all the DIEs.
void DwarfUnits::computeSizeAndOffsets() {
  // Offset from the beginning of debug info section.
  unsigned SecOffset = 0;
  for (SmallVectorImpl<CompileUnit *>::iterator I = CUs.begin(),
         E = CUs.end(); I != E; ++I) {
    (*I)->setDebugInfoOffset(SecOffset);
    unsigned Offset =
      sizeof(int32_t) + // Length of Compilation Unit Info
      sizeof(int16_t) + // DWARF version number
      sizeof(int32_t) + // Offset Into Abbrev. Section
      sizeof(int8_t);   // Pointer Size (in bytes)

    unsigned EndOffset = computeSizeAndOffset((*I)->getCUDie(), Offset);
    SecOffset += EndOffset;
  }
}

// Emit initial Dwarf sections with a label at the start of each one.
void DwarfDebug::emitSectionLabels() {
  const TargetLoweringObjectFile &TLOF = Asm->getObjFileLowering();

  // Dwarf sections base addresses.
  DwarfInfoSectionSym =
    emitSectionSym(Asm, TLOF.getDwarfInfoSection(), "section_info");
  DwarfAbbrevSectionSym =
    emitSectionSym(Asm, TLOF.getDwarfAbbrevSection(), "section_abbrev");
  if (useSplitDwarf())
    DwarfAbbrevDWOSectionSym =
      emitSectionSym(Asm, TLOF.getDwarfAbbrevDWOSection(),