DwarfDebug.cpp

         E = DbgFinder.subprogram_end(); I != E; ++I)
    constructSubprogramDIE(*I);

  // Create DIEs for each global variable.
  for (DebugInfoFinder::iterator I = DbgFinder.global_variable_begin(),
         E = DbgFinder.global_variable_end(); I != E; ++I)
    constructGlobalVariableDIE(*I);

  // Prime section data.
  SectionMap.insert(Asm->getObjFileLowering().getTextSection());

  // Print out .file directives to specify files for .loc directives. These are
  // printed out early so that they precede any .loc directives.
  if (Asm->MAI->hasDotLocAndDotFile()) {
    for (unsigned i = 1, e = getNumSourceIds()+1; i != e; ++i) {
      // Remember source id starts at 1.
      std::pair<unsigned, unsigned> Id = getSourceDirectoryAndFileIds(i);
      // FIXME: don't use sys::path for this!  This should not depend on the
      // host.
      sys::Path FullPath(getSourceDirectoryName(Id.first));
      bool AppendOk =
        FullPath.appendComponent(getSourceFileName(Id.second));
      assert(AppendOk && "Could not append filename to directory!");
      AppendOk = false;
      Asm->OutStreamer.EmitDwarfFileDirective(i, FullPath.str());
    }
  }
}

/// endModule - Emit all Dwarf sections that should come after the content.
///
void DwarfDebug::endModule() {
  if (!FirstCU) return;
  const Module *M = MMI->getModule();
  DenseMap<const MDNode *, DbgScope *> DeadFnScopeMap;
  if (NamedMDNode *AllSPs = M->getNamedMetadata("llvm.dbg.sp")) {
    for (unsigned SI = 0, SE = AllSPs->getNumOperands(); SI != SE; ++SI) {
      if (ProcessedSPNodes.count(AllSPs->getOperand(SI)) != 0) continue;
      DISubprogram SP(AllSPs->getOperand(SI));
      if (!SP.Verify()) continue;

      // Collect info for variables that were optimized out.
      if (!SP.isDefinition()) continue;
      StringRef FName = SP.getLinkageName();
      if (FName.empty())
        FName = SP.getName();
      NamedMDNode *NMD =
        M->getNamedMetadata(Twine("llvm.dbg.lv.", getRealLinkageName(FName)));
      if (!NMD) continue;
      unsigned E = NMD->getNumOperands();
      if (!E) continue;
      DbgScope *Scope = new DbgScope(NULL, DIDescriptor(SP), NULL);
      DeadFnScopeMap[SP] = Scope;
      for (unsigned I = 0; I != E; ++I) {
        DIVariable DV(NMD->getOperand(I));
        if (!DV.Verify()) continue;
        Scope->addVariable(new DbgVariable(DV));
      }

      // Construct subprogram DIE and add variables DIEs.
      constructSubprogramDIE(SP);
      DIE *ScopeDIE = getCompileUnit(SP)->getDIE(SP);
      const SmallVector<DbgVariable *, 8> &Variables = Scope->getVariables();
      for (unsigned i = 0, N = Variables.size(); i < N; ++i) {
        DIE *VariableDIE = constructVariableDIE(Variables[i], Scope);
        if (VariableDIE)
          ScopeDIE->addChild(VariableDIE);
      }
    }
  }

  // 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;
    addUInt(ISP, dwarf::DW_AT_inline, 0, dwarf::DW_INL_inlined);
  }

  for (DenseMap<DIE *, const MDNode *>::iterator CI = ContainingTypeMap.begin(),
         CE = ContainingTypeMap.end(); CI != CE; ++CI) {
    DIE *SPDie = CI->first;
    const MDNode *N = dyn_cast_or_null<MDNode>(CI->second);
    if (!N) continue;
    DIE *NDie = getCompileUnit(N)->getDIE(N);
    if (!NDie) continue;
    addDIEEntry(SPDie, dwarf::DW_AT_containing_type, dwarf::DW_FORM_ref4, NDie);
  }

  // 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 = 1, N = SectionMap.size(); i <= N; ++i) {
    Asm->OutStreamer.SwitchSection(SectionMap[i]);
    Asm->OutStreamer.EmitLabel(Asm->GetTempSymbol("section_end", i));
  }

  // Emit common frame information.
  emitCommonDebugFrame();

  // Emit function debug frame information
  for (std::vector<FunctionDebugFrameInfo>::iterator I = DebugFrames.begin(),
         E = DebugFrames.end(); I != E; ++I)
    emitFunctionDebugFrame(*I);

  // Compute DIE offsets and sizes.
  computeSizeAndOffsets();

  // Emit source line correspondence into a debug line section.
  emitDebugLines();

  // Emit all the DIEs into a debug info section
  emitDebugInfo();

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

  // Emit info into a debug pubnames section.
  emitDebugPubNames();

  // Emit info into a debug pubtypes section.
  emitDebugPubTypes();

  // 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.
  emitDebugInlineInfo();

  // Emit info into a debug str section.
  emitDebugStr();

  // clean up.
  DeleteContainerSeconds(DeadFnScopeMap);
  for (DenseMap<const MDNode *, CompileUnit *>::iterator I = CUMap.begin(),
         E = CUMap.end(); I != E; ++I)
    delete I->second;
  FirstCU = NULL;  // Reset for the next Module, if any.
}

/// findAbstractVariable - Find abstract variable, if any, associated with Var.
DbgVariable *DwarfDebug::findAbstractVariable(DIVariable &Var,
                                              DebugLoc ScopeLoc) {

  DbgVariable *AbsDbgVariable = AbstractVariables.lookup(Var);
  if (AbsDbgVariable)
    return AbsDbgVariable;

  LLVMContext &Ctx = Var->getContext();
  DbgScope *Scope = AbstractScopes.lookup(ScopeLoc.getScope(Ctx));
  if (!Scope)
    return NULL;

  AbsDbgVariable = new DbgVariable(Var);
  Scope->addVariable(AbsDbgVariable);
  AbstractVariables[Var] = AbsDbgVariable;
  return AbsDbgVariable;
}

/// collectVariableInfoFromMMITable - Collect variable information from
/// side table maintained by MMI.
void
DwarfDebug::collectVariableInfoFromMMITable(const MachineFunction * MF,
                                   SmallPtrSet<const MDNode *, 16> &Processed) {
  const LLVMContext &Ctx = Asm->MF->getFunction()->getContext();
  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;

    DbgScope *Scope = 0;
    if (const MDNode *IA = VP.second.getInlinedAt(Ctx))
      Scope = ConcreteScopes.lookup(IA);
    if (Scope == 0)
      Scope = DbgScopeMap.lookup(VP.second.getScope(Ctx));

    // 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);
    recordVariableFrameIndex(RegVar, VP.first);
    Scope->addVariable(RegVar);
    if (AbsDbgVariable) {
      recordVariableFrameIndex(AbsDbgVariable, VP.first);
      VarToAbstractVarMap[RegVar] = AbsDbgVariable;
    }
  }
}

/// isDbgValueInUndefinedReg - Return true if debug value, encoded by
/// DBG_VALUE instruction, is in undefined reg.
static bool isDbgValueInUndefinedReg(const MachineInstr *MI) {
  assert (MI->isDebugValue() && "Invalid DBG_VALUE machine instruction!");
  if (MI->getOperand(0).isReg() && !MI->getOperand(0).getReg())
    return true;
  return false;
}

/// isDbgValueInDefinedReg - 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!");
  if (MI->getOperand(0).isReg() && MI->getOperand(0).getReg())
    return true;
  return false;
}

/// collectVariableInfo - Populate DbgScope entries with variables' info.
void
DwarfDebug::collectVariableInfo(const MachineFunction *MF,
                                SmallPtrSet<const MDNode *, 16> &Processed) {

  /// collection info from MMI table.
  collectVariableInfoFromMMITable(MF, Processed);

  SmallVector<const MachineInstr *, 8> DbgValues;
  // Collect variable information from DBG_VALUE machine instructions;
  for (MachineFunction::const_iterator I = Asm->MF->begin(), E = Asm->MF->end();
       I != E; ++I)
    for (MachineBasicBlock::const_iterator II = I->begin(), IE = I->end();
         II != IE; ++II) {
      const MachineInstr *MInsn = II;
      if (!MInsn->isDebugValue() || isDbgValueInUndefinedReg(MInsn))
        continue;
      DbgValues.push_back(MInsn);
    }

  // This is a collection of DBV_VALUE instructions describing same variable.
  SmallVector<const MachineInstr *, 4> MultipleValues;
  for(SmallVector<const MachineInstr *, 8>::iterator I = DbgValues.begin(),
        E = DbgValues.end(); I != E; ++I) {
    const MachineInstr *MInsn = *I;
    MultipleValues.clear();
    if (isDbgValueInDefinedReg(MInsn))
      MultipleValues.push_back(MInsn);
    DIVariable DV(MInsn->getOperand(MInsn->getNumOperands() - 1).getMetadata());
    if (Processed.count(DV) != 0)
      continue;

    const MachineInstr *PrevMI = MInsn;
    for (SmallVector<const MachineInstr *, 8>::iterator MI = I+1,
           ME = DbgValues.end(); MI != ME; ++MI) {
      const MDNode *Var =
        (*MI)->getOperand((*MI)->getNumOperands()-1).getMetadata();
      if (Var == DV && isDbgValueInDefinedReg(*MI) &&
          !PrevMI->isIdenticalTo(*MI))
        MultipleValues.push_back(*MI);
      PrevMI = *MI;
    }

    DbgScope *Scope = findDbgScope(MInsn);
    bool CurFnArg = false;
    if (DV.getTag() == dwarf::DW_TAG_arg_variable &&
        DISubprogram(DV.getContext()).describes(MF->getFunction()))
      CurFnArg = true;
    if (!Scope && CurFnArg)
      Scope = CurrentFnDbgScope;
    // If variable scope is not found then skip this variable.
    if (!Scope)
      continue;

    Processed.insert(DV);
    DbgVariable *RegVar = new DbgVariable(DV);
    Scope->addVariable(RegVar);
    if (!CurFnArg)
      DbgVariableLabelsMap[RegVar] = getLabelBeforeInsn(MInsn);
    if (DbgVariable *AbsVar = findAbstractVariable(DV, MInsn->getDebugLoc())) {
      DbgVariableToDbgInstMap[AbsVar] = MInsn;
      VarToAbstractVarMap[RegVar] = AbsVar;
    }
    if (MultipleValues.size() <= 1) {
      DbgVariableToDbgInstMap[RegVar] = MInsn;
      continue;
    }

    // handle multiple DBG_VALUE instructions describing one variable.
    if (DotDebugLocEntries.empty())
      RegVar->setDotDebugLocOffset(0);
    else
      RegVar->setDotDebugLocOffset(DotDebugLocEntries.size());
    const MachineInstr *Begin = NULL;
    const MachineInstr *End = NULL;
    for (SmallVector<const MachineInstr *, 4>::iterator
           MVI = MultipleValues.begin(), MVE = MultipleValues.end();
         MVI != MVE; ++MVI) {
      if (!Begin) {
        Begin = *MVI;
        continue;
      }
      End = *MVI;
      MachineLocation MLoc;
      MLoc.set(Begin->getOperand(0).getReg(), 0);
      const MCSymbol *FLabel = getLabelBeforeInsn(Begin);
      const MCSymbol *SLabel = getLabelBeforeInsn(End);
      DotDebugLocEntries.push_back(DotDebugLocEntry(FLabel, SLabel, MLoc));
      Begin = End;
      if (MVI + 1 == MVE) {
        // If End is the last instruction then its value is valid
        // until the end of the funtion.
        MLoc.set(End->getOperand(0).getReg(), 0);
        DotDebugLocEntries.
          push_back(DotDebugLocEntry(SLabel, FunctionEndSym, MLoc));
      }
    }
    DotDebugLocEntries.push_back(DotDebugLocEntry());
  }

  // Collect info for variables that were optimized out.
  const Function *F = MF->getFunction();
  const Module *M = F->getParent();
  if (NamedMDNode *NMD =
      M->getNamedMetadata(Twine("llvm.dbg.lv.",
                                getRealLinkageName(F->getName())))) {
    for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i) {
      DIVariable DV(cast<MDNode>(NMD->getOperand(i)));
      if (!DV || !Processed.insert(DV))
        continue;
      DbgScope *Scope = DbgScopeMap.lookup(DV.getContext());
      if (Scope)
        Scope->addVariable(new DbgVariable(DV));
    }
  }
}

/// getLabelBeforeInsn - Return Label preceding the instruction.
const MCSymbol *DwarfDebug::getLabelBeforeInsn(const MachineInstr *MI) {
  DenseMap<const MachineInstr *, MCSymbol *>::iterator I =
    LabelsBeforeInsn.find(MI);
  if (I == LabelsBeforeInsn.end())
    // FunctionBeginSym always preceeds all the instruction in current function.
    return FunctionBeginSym;
  return I->second;
}

/// getLabelAfterInsn - Return Label immediately following the instruction.
const MCSymbol *DwarfDebug::getLabelAfterInsn(const MachineInstr *MI) {
  DenseMap<const MachineInstr *, MCSymbol *>::iterator I =
    LabelsAfterInsn.find(MI);
  if (I == LabelsAfterInsn.end())
    return NULL;
  return I->second;
}

/// beginScope - Process beginning of a scope.
void DwarfDebug::beginScope(const MachineInstr *MI) {
  if (InsnNeedsLabel.count(MI) == 0) {
    LabelsBeforeInsn[MI] = PrevLabel;
    return;
  }

  // Check location.
  DebugLoc DL = MI->getDebugLoc();
  if (!DL.isUnknown()) {
    const MDNode *Scope = DL.getScope(Asm->MF->getFunction()->getContext());
    PrevLabel = recordSourceLine(DL.getLine(), DL.getCol(), Scope);
    PrevInstLoc = DL;
    LabelsBeforeInsn[MI] = PrevLabel;
    return;
  }

  // If location is unknown then use temp label for this DBG_VALUE
  // instruction.
  if (MI->isDebugValue()) {
    PrevLabel = MMI->getContext().CreateTempSymbol();
    Asm->OutStreamer.EmitLabel(PrevLabel);
    LabelsBeforeInsn[MI] = PrevLabel;
    return;
  }

  if (UnknownLocations) {
    PrevLabel = recordSourceLine(0, 0, 0);
    LabelsBeforeInsn[MI] = PrevLabel;
    return;
  }

  assert (0 && "Instruction is not processed!");
}

/// endScope - Process end of a scope.
void DwarfDebug::endScope(const MachineInstr *MI) {
  if (InsnsEndScopeSet.count(MI) != 0) {
    // Emit a label if this instruction ends a scope.
    MCSymbol *Label = MMI->getContext().CreateTempSymbol();
    Asm->OutStreamer.EmitLabel(Label);
    LabelsAfterInsn[MI] = Label;
  }
}

/// getOrCreateDbgScope - Create DbgScope for the scope.
DbgScope *DwarfDebug::getOrCreateDbgScope(const MDNode *Scope,
                                          const MDNode *InlinedAt) {
  if (!InlinedAt) {
    DbgScope *WScope = DbgScopeMap.lookup(Scope);
    if (WScope)
      return WScope;
    WScope = new DbgScope(NULL, DIDescriptor(Scope), NULL);
    DbgScopeMap.insert(std::make_pair(Scope, WScope));
    if (DIDescriptor(Scope).isLexicalBlock()) {
      DbgScope *Parent =
        getOrCreateDbgScope(DILexicalBlock(Scope).getContext(), NULL);
      WScope->setParent(Parent);
      Parent->addScope(WScope);
    }

    if (!WScope->getParent()) {
      StringRef SPName = DISubprogram(Scope).getLinkageName();
      // We used to check only for a linkage name, but that fails
      // since we began omitting the linkage name for private
      // functions.  The new way is to check for the name in metadata,
      // but that's not supported in old .ll test cases.  Ergo, we
      // check both.
      if (SPName == Asm->MF->getFunction()->getName() ||
          DISubprogram(Scope).getFunction() == Asm->MF->getFunction())
        CurrentFnDbgScope = WScope;
    }

    return WScope;
  }

  getOrCreateAbstractScope(Scope);
  DbgScope *WScope = DbgScopeMap.lookup(InlinedAt);
  if (WScope)
    return WScope;

  WScope = new DbgScope(NULL, DIDescriptor(Scope), InlinedAt);
  DbgScopeMap.insert(std::make_pair(InlinedAt, WScope));
  DILocation DL(InlinedAt);
  DbgScope *Parent =
    getOrCreateDbgScope(DL.getScope(), DL.getOrigLocation());
  WScope->setParent(Parent);
  Parent->addScope(WScope);

  ConcreteScopes[InlinedAt] = WScope;

  return WScope;
}

/// hasValidLocation - Return true if debug location entry attached with
/// machine instruction encodes valid location info.
static bool hasValidLocation(LLVMContext &Ctx,
                             const MachineInstr *MInsn,
                             const MDNode *&Scope, const MDNode *&InlinedAt) {
  DebugLoc DL = MInsn->getDebugLoc();
  if (DL.isUnknown()) return false;

  const MDNode *S = DL.getScope(Ctx);

  // There is no need to create another DIE for compile unit. For all
  // other scopes, create one DbgScope now. This will be translated
  // into a scope DIE at the end.
  if (DIScope(S).isCompileUnit()) return false;

  Scope = S;
  InlinedAt = DL.getInlinedAt(Ctx);
  return true;
}

/// calculateDominanceGraph - Calculate dominance graph for DbgScope
/// hierarchy.
static void calculateDominanceGraph(DbgScope *Scope) {
  assert (Scope && "Unable to calculate scop edominance graph!");
  SmallVector<DbgScope *, 4> WorkStack;
  WorkStack.push_back(Scope);
  unsigned Counter = 0;
  while (!WorkStack.empty()) {
    DbgScope *WS = WorkStack.back();
    const SmallVector<DbgScope *, 4> &Children = WS->getScopes();
    bool visitedChildren = false;
    for (SmallVector<DbgScope *, 4>::const_iterator SI = Children.begin(),
           SE = Children.end(); SI != SE; ++SI) {
      DbgScope *ChildScope = *SI;
      if (!ChildScope->getDFSOut()) {
        WorkStack.push_back(ChildScope);
        visitedChildren = true;
        ChildScope->setDFSIn(++Counter);
        break;
      }
    }
    if (!visitedChildren) {
      WorkStack.pop_back();
      WS->setDFSOut(++Counter);
    }
  }
}

/// printDbgScopeInfo - Print DbgScope info for each machine instruction.
static
void printDbgScopeInfo(LLVMContext &Ctx, const MachineFunction *MF,
                       DenseMap<const MachineInstr *, DbgScope *> &MI2ScopeMap)
{
#ifndef NDEBUG
  unsigned PrevDFSIn = 0;
  for (MachineFunction::const_iterator I = MF->begin(), E = MF->end();
       I != E; ++I) {
    for (MachineBasicBlock::const_iterator II = I->begin(), IE = I->end();
         II != IE; ++II) {
      const MachineInstr *MInsn = II;
      const MDNode *Scope = NULL;
      const MDNode *InlinedAt = NULL;

      // Check if instruction has valid location information.
      if (hasValidLocation(Ctx, MInsn, Scope, InlinedAt)) {
        dbgs() << " [ ";
        if (InlinedAt)
          dbgs() << "*";
        DenseMap<const MachineInstr *, DbgScope *>::iterator DI =
          MI2ScopeMap.find(MInsn);
        if (DI != MI2ScopeMap.end()) {
          DbgScope *S = DI->second;
          dbgs() << S->getDFSIn();
          PrevDFSIn = S->getDFSIn();
        } else
          dbgs() << PrevDFSIn;
      } else
        dbgs() << " [ x" << PrevDFSIn;
      dbgs() << " ]";
      MInsn->dump();
    }
    dbgs() << "\n";
  }
#endif
}
/// extractScopeInformation - Scan machine instructions in this function
/// and collect DbgScopes. Return true, if at least one scope was found.
bool DwarfDebug::extractScopeInformation() {
  // If scope information was extracted using .dbg intrinsics then there is not
  // any need to extract these information by scanning each instruction.
  if (!DbgScopeMap.empty())
    return false;

  // Scan each instruction and create scopes. First build working set of scopes.
  LLVMContext &Ctx = Asm->MF->getFunction()->getContext();
  SmallVector<DbgRange, 4> MIRanges;
  DenseMap<const MachineInstr *, DbgScope *> MI2ScopeMap;
  const MDNode *PrevScope = NULL;
  const MDNode *PrevInlinedAt = NULL;
  const MachineInstr *RangeBeginMI = NULL;
  const MachineInstr *PrevMI = NULL;
  for (MachineFunction::const_iterator I = Asm->MF->begin(), E = Asm->MF->end();
       I != E; ++I) {
    for (MachineBasicBlock::const_iterator II = I->begin(), IE = I->end();
         II != IE; ++II) {
      const MachineInstr *MInsn = II;
      const MDNode *Scope = NULL;
      const MDNode *InlinedAt = NULL;

      // Check if instruction has valid location information.
      if (!hasValidLocation(Ctx, MInsn, Scope, InlinedAt)) {
        PrevMI = MInsn;
        continue;
      }

      // If scope has not changed then skip this instruction.
      if (Scope == PrevScope && PrevInlinedAt == InlinedAt) {
        PrevMI = MInsn;
        continue;
      }

      if (RangeBeginMI) {
        // If we have alread seen a beginning of a instruction range and
        // current instruction scope does not match scope of first instruction
        // in this range then create a new instruction range.
        DbgRange R(RangeBeginMI, PrevMI);
        MI2ScopeMap[RangeBeginMI] = getOrCreateDbgScope(PrevScope,
                                                        PrevInlinedAt);
        MIRanges.push_back(R);
      }

      // This is a beginning of a new instruction range.
      RangeBeginMI = MInsn;

      // Reset previous markers.
      PrevMI = MInsn;
      PrevScope = Scope;
      PrevInlinedAt = InlinedAt;
    }
  }

  // Create last instruction range.
  if (RangeBeginMI && PrevMI && PrevScope) {
    DbgRange R(RangeBeginMI, PrevMI);
    MIRanges.push_back(R);
    MI2ScopeMap[RangeBeginMI] = getOrCreateDbgScope(PrevScope, PrevInlinedAt);
  }

  if (!CurrentFnDbgScope)
    return false;

  calculateDominanceGraph(CurrentFnDbgScope);
  if (PrintDbgScope)
    printDbgScopeInfo(Ctx, Asm->MF, MI2ScopeMap);

  // Find ranges of instructions covered by each DbgScope;
  DbgScope *PrevDbgScope = NULL;
  for (SmallVector<DbgRange, 4>::const_iterator RI = MIRanges.begin(),
         RE = MIRanges.end(); RI != RE; ++RI) {
    const DbgRange &R = *RI;
    DbgScope *S = MI2ScopeMap.lookup(R.first);
    assert (S && "Lost DbgScope for a machine instruction!");
    if (PrevDbgScope && !PrevDbgScope->dominates(S))
      PrevDbgScope->closeInsnRange(S);
    S->openInsnRange(R.first);
    S->extendInsnRange(R.second);
    PrevDbgScope = S;
  }

  if (PrevDbgScope)
    PrevDbgScope->closeInsnRange();

  identifyScopeMarkers();

  return !DbgScopeMap.empty();
}

/// identifyScopeMarkers() -
/// Each DbgScope 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<DbgScope *, 4> WorkList;
  WorkList.push_back(CurrentFnDbgScope);
  while (!WorkList.empty()) {
    DbgScope *S = WorkList.pop_back_val();

    const SmallVector<DbgScope *, 4> &Children = S->getScopes();
    if (!Children.empty())
      for (SmallVector<DbgScope *, 4>::const_iterator SI = Children.begin(),
             SE = Children.end(); SI != SE; ++SI)
        WorkList.push_back(*SI);

    if (S->isAbstractScope())
      continue;

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

/// FindFirstDebugLoc - Find the first debug location in the function. This
/// is intended to be an approximation for the source position of the
/// beginning of the function.
static DebugLoc FindFirstDebugLoc(const MachineFunction *MF) {
  for (MachineFunction::const_iterator I = MF->begin(), E = MF->end();
       I != E; ++I)
    for (MachineBasicBlock::const_iterator MBBI = I->begin(), MBBE = I->end();
         MBBI != MBBE; ++MBBI) {
      DebugLoc DL = MBBI->getDebugLoc();
      if (!DL.isUnknown())
        return DL;
    }
  return DebugLoc();
}

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

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

  // Emit label for the implicitly defined dbg.stoppoint at the start of the
  // function.
  DebugLoc FDL = FindFirstDebugLoc(MF);
  if (FDL.isUnknown()) return;

  const MDNode *Scope = FDL.getScope(MF->getFunction()->getContext());
  const MDNode *TheScope = 0;

  DISubprogram SP = getDISubprogram(Scope);
  unsigned Line, Col;
  if (SP.Verify()) {
    Line = SP.getLineNumber();
    Col = 0;
    TheScope = SP;
  } else {
    Line = FDL.getLine();
    Col = FDL.getCol();
    TheScope = Scope;
  }

  recordSourceLine(Line, Col, TheScope);

  /// ProcessedArgs - Collection of arguments already processed.
  SmallPtrSet<const MDNode *, 8> ProcessedArgs;

  DebugLoc PrevLoc;
  for (MachineFunction::const_iterator I = MF->begin(), E = MF->end();
       I != E; ++I)
    for (MachineBasicBlock::const_iterator II = I->begin(), IE = I->end();
         II != IE; ++II) {
      const MachineInstr *MI = II;
      DebugLoc DL = MI->getDebugLoc();
      if (MI->isDebugValue()) {
        assert (MI->getNumOperands() > 1 && "Invalid machine instruction!");
        DIVariable DV(MI->getOperand(MI->getNumOperands() - 1).getMetadata());
        if (!DV.Verify()) continue;
        // If DBG_VALUE is for a local variable then it needs a label.
        if (DV.getTag() != dwarf::DW_TAG_arg_variable
            && isDbgValueInUndefinedReg(MI) == false)
          InsnNeedsLabel.insert(MI);
        // DBG_VALUE for inlined functions argument needs a label.
        else if (!DISubprogram(getDISubprogram(DV.getContext())).
                 describes(MF->getFunction()))
          InsnNeedsLabel.insert(MI);
        // DBG_VALUE indicating argument location change needs a label.
        else if (isDbgValueInUndefinedReg(MI) == false
                 && !ProcessedArgs.insert(DV))
          InsnNeedsLabel.insert(MI);
      } else {
        // If location is unknown then instruction needs a location only if
        // UnknownLocations flag is set.
        if (DL.isUnknown()) {
          if (UnknownLocations && !PrevLoc.isUnknown())
            InsnNeedsLabel.insert(MI);
        } else if (DL != PrevLoc)
          // Otherwise, instruction needs a location only if it is new location.
          InsnNeedsLabel.insert(MI);
      }

      if (!DL.isUnknown() || UnknownLocations)
        PrevLoc = DL;
    }

  PrevLabel = FunctionBeginSym;
}

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

  if (CurrentFnDbgScope) {

    // Define end label for subprogram.
    FunctionEndSym = Asm->GetTempSymbol("func_end",
                                        Asm->getFunctionNumber());
    // Assumes in correct section after the entry point.
    Asm->OutStreamer.EmitLabel(FunctionEndSym);

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

    // Get function line info.
    if (!Lines.empty()) {
      // Get section line info.
      unsigned ID = SectionMap.insert(Asm->getCurrentSection());
      if (SectionSourceLines.size() < ID) SectionSourceLines.resize(ID);
      std::vector<SrcLineInfo> &SectionLineInfos = SectionSourceLines[ID-1];
      // Append the function info to section info.
      SectionLineInfos.insert(SectionLineInfos.end(),
                              Lines.begin(), Lines.end());
    }

    // Construct abstract scopes.
    for (SmallVector<DbgScope *, 4>::iterator AI = AbstractScopesList.begin(),
           AE = AbstractScopesList.end(); AI != AE; ++AI) {
      DISubprogram SP((*AI)->getScopeNode());
      if (SP.Verify()) {
        // Collect info for variables that were optimized out.
        StringRef FName = SP.getLinkageName();
        if (FName.empty())
          FName = SP.getName();
        const Module *M = MF->getFunction()->getParent();
        if (NamedMDNode *NMD =
            M->getNamedMetadata(Twine("llvm.dbg.lv.",
                                      getRealLinkageName(FName)))) {
          for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i) {
          DIVariable DV(cast<MDNode>(NMD->getOperand(i)));
          if (!DV || !ProcessedVars.insert(DV))
            continue;
          DbgScope *Scope = AbstractScopes.lookup(DV.getContext());
          if (Scope)
            Scope->addVariable(new DbgVariable(DV));
          }
        }
      }
      if (ProcessedSPNodes.count((*AI)->getScopeNode()) == 0)
        constructScopeDIE(*AI);
    }

    DIE *CurFnDIE = constructScopeDIE(CurrentFnDbgScope);

    if (!DisableFramePointerElim(*MF))
      addUInt(CurFnDIE, dwarf::DW_AT_APPLE_omit_frame_ptr,
              dwarf::DW_FORM_flag, 1);


    DebugFrames.push_back(FunctionDebugFrameInfo(Asm->getFunctionNumber(),
                                                 MMI->getFrameMoves()));
  }

  // Clear debug info
  CurrentFnDbgScope = NULL;
  InsnNeedsLabel.clear();
  DbgVariableToFrameIndexMap.clear();
  VarToAbstractVarMap.clear();
  DbgVariableToDbgInstMap.clear();
  DbgVariableLabelsMap.clear();
  DeleteContainerSeconds(DbgScopeMap);
  InsnsEndScopeSet.clear();
  ConcreteScopes.clear();
  DeleteContainerSeconds(AbstractScopes);
  AbstractScopesList.clear();
  AbstractVariables.clear();
  LabelsBeforeInsn.clear();
  LabelsAfterInsn.clear();
  Lines.clear();
  PrevLabel = NULL;
}

/// recordVariableFrameIndex - Record a variable's index.
void DwarfDebug::recordVariableFrameIndex(const DbgVariable *V, int Index) {
  assert (V && "Invalid DbgVariable!");
  DbgVariableToFrameIndexMap[V] = Index;
}

/// findVariableFrameIndex - Return true if frame index for the variable
/// is found. Update FI to hold value of the index.
bool DwarfDebug::findVariableFrameIndex(const DbgVariable *V, int *FI) {
  assert (V && "Invalid DbgVariable!");
  DenseMap<const DbgVariable *, int>::iterator I =
    DbgVariableToFrameIndexMap.find(V);
  if (I == DbgVariableToFrameIndexMap.end())
    return false;
  *FI = I->second;
  return true;
}

/// findVariableLabel - Find MCSymbol for the variable.
const MCSymbol *DwarfDebug::findVariableLabel(const DbgVariable *V) {
  DenseMap<const DbgVariable *, const MCSymbol *>::iterator I
    = DbgVariableLabelsMap.find(V);
  if (I == DbgVariableLabelsMap.end())
    return NULL;
  else return I->second;
}

/// findDbgScope - Find DbgScope for the debug loc attached with an
/// instruction.
DbgScope *DwarfDebug::findDbgScope(const MachineInstr *MInsn) {
  DbgScope *Scope = NULL;
  LLVMContext &Ctx =
    MInsn->getParent()->getParent()->getFunction()->getContext();
  DebugLoc DL = MInsn->getDebugLoc();

  if (DL.isUnknown())
    return Scope;

  if (const MDNode *IA = DL.getInlinedAt(Ctx))
    Scope = ConcreteScopes.lookup(IA);
  if (Scope == 0)
    Scope = DbgScopeMap.lookup(DL.getScope(Ctx));

  return Scope;
}


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

  unsigned Src = 1;
  if (S) {
    DIDescriptor Scope(S);

    if (Scope.isCompileUnit()) {
      DICompileUnit CU(S);
      Dir = CU.getDirectory();
      Fn = CU.getFilename();
    } else if (Scope.isSubprogram()) {
      DISubprogram SP(S);
      Dir = SP.getDirectory();
      Fn = SP.getFilename();
    } else if (Scope.isLexicalBlock()) {
      DILexicalBlock DB(S);
      Dir = DB.getDirectory();
      Fn = DB.getFilename();
    } else
      assert(0 && "Unexpected scope info");

    Src = GetOrCreateSourceID(Dir, Fn);
  }

  MCSymbol *Label = MMI->getContext().CreateTempSymbol();
  Lines.push_back(SrcLineInfo(Line, Col, Src, Label));

  Asm->OutStreamer.EmitLabel(Label);
  return Label;
}

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

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

  // If not last sibling and has children then add sibling offset attribute.
  if (!Last && !Children.empty())
    Die->addSiblingOffset(DIEValueAllocator);

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

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

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

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

  const SmallVector<DIEValue*, 32> &Values = Die->getValues();
  const SmallVector<DIEAbbrevData, 8> &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, (j + 1) == M);

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

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

/// computeSizeAndOffsets - Compute the size and offset of all the DIEs.
///
void DwarfDebug::computeSizeAndOffsets() {
  unsigned PrevOffset = 0;
  for (DenseMap<const MDNode *, CompileUnit *>::iterator I = CUMap.begin(),
         E = CUMap.end(); I != E; ++I) {
    // Compute size of compile unit header.
    static unsigned Offset = PrevOffset +
      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)
    computeSizeAndOffset(I->second->getCUDie(), Offset, true);
    PrevOffset = Offset;
  }
}

/// EmitSectionSym - 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;