DwarfDebug.cpp

  if (!CI || !CI->isZero())
    return NULL;

  // Third operand is offset.
  if (!isa<ConstantInt>(CE->getOperand(2)))
    return NULL;

  return CE;
}

/// constructGlobalVariableDIE - Construct global variable DIE.
void DwarfDebug::constructGlobalVariableDIE(const MDNode *N) {
  DIGlobalVariable GV(N);

  // If debug information is malformed then ignore it.
  if (GV.Verify() == false)
    return;

  // Check for pre-existence.
  CompileUnit *TheCU = getCompileUnit(N);
  if (TheCU->getDIE(GV))
    return;

  DIType GTy = GV.getType();
  DIE *VariableDIE = new DIE(GV.getTag());

  bool isGlobalVariable = GV.getGlobal() != NULL;

  // Add name.
  addString(VariableDIE, dwarf::DW_AT_name, dwarf::DW_FORM_string,
            GV.getDisplayName());
  StringRef LinkageName = GV.getLinkageName();
  if (!LinkageName.empty() && isGlobalVariable)
    addString(VariableDIE, dwarf::DW_AT_MIPS_linkage_name, dwarf::DW_FORM_string,
              getRealLinkageName(LinkageName));
  // Add type.
  addType(VariableDIE, GTy);
  if (GTy.isCompositeType() && !GTy.getName().empty()
      && !GTy.isForwardDecl()) {
    DIEEntry *Entry = TheCU->getDIEEntry(GTy);
    assert(Entry && "Missing global type!");
    TheCU->addGlobalType(GTy.getName(), Entry->getEntry());
  }
  // Add scoping info.
  if (!GV.isLocalToUnit()) {
    addUInt(VariableDIE, dwarf::DW_AT_external, dwarf::DW_FORM_flag, 1);
    // Expose as global. 
    TheCU->addGlobal(GV.getName(), VariableDIE);
  }
  // Add line number info.
  addSourceLine(VariableDIE, GV);
  // Add to map.
  TheCU->insertDIE(N, VariableDIE);
  // Add to context owner.
  DIDescriptor GVContext = GV.getContext();
  addToContextOwner(VariableDIE, GVContext);
  // Add location.
  if (isGlobalVariable) {
    DIEBlock *Block = new (DIEValueAllocator) DIEBlock();
    addUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_addr);
    addLabel(Block, 0, dwarf::DW_FORM_udata,
             Asm->Mang->getSymbol(GV.getGlobal()));
    // Do not create specification DIE if context is either compile unit
    // or a subprogram.
    if (GV.isDefinition() && !GVContext.isCompileUnit() &&
        !GVContext.isFile() && !isSubprogramContext(GVContext)) {
      // Create specification DIE.
      DIE *VariableSpecDIE = new DIE(dwarf::DW_TAG_variable);
      addDIEEntry(VariableSpecDIE, dwarf::DW_AT_specification,
                  dwarf::DW_FORM_ref4, VariableDIE);
      addBlock(VariableSpecDIE, dwarf::DW_AT_location, 0, Block);
      addUInt(VariableDIE, dwarf::DW_AT_declaration, dwarf::DW_FORM_flag, 1);
      TheCU->addDie(VariableSpecDIE);
    } else {
      addBlock(VariableDIE, dwarf::DW_AT_location, 0, Block);
    } 
  } else if (ConstantInt *CI = 
             dyn_cast_or_null<ConstantInt>(GV.getConstant()))
    addConstantValue(VariableDIE, CI, isUnsignedDIType(GTy));
  else if (const ConstantExpr *CE = getMergedGlobalExpr(N->getOperand(11))) {
    // GV is a merged global.
    DIEBlock *Block = new (DIEValueAllocator) DIEBlock();
    addUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_addr);
    addLabel(Block, 0, dwarf::DW_FORM_udata,
             Asm->Mang->getSymbol(cast<GlobalValue>(CE->getOperand(0))));
    ConstantInt *CII = cast<ConstantInt>(CE->getOperand(2));
    addUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_constu);
    addUInt(Block, 0, dwarf::DW_FORM_udata, CII->getZExtValue());
    addUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_plus);
    addBlock(VariableDIE, dwarf::DW_AT_location, 0, Block);
  }

  return;
}

/// construct SubprogramDIE - Construct subprogram DIE.
void DwarfDebug::constructSubprogramDIE(const MDNode *N) {
  DISubprogram SP(N);

  // Check for pre-existence.
  CompileUnit *TheCU = getCompileUnit(N);
  if (TheCU->getDIE(N))
    return;

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

  DIE *SubprogramDie = createSubprogramDIE(SP);

  // Add to map.
  TheCU->insertDIE(N, SubprogramDie);

  // Add to context owner.
  addToContextOwner(SubprogramDie, SP.getContext());

  // Expose as global.
  TheCU->addGlobal(SP.getName(), SubprogramDie);

  return;
}

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

  DebugInfoFinder DbgFinder;
  DbgFinder.processModule(*M);

  bool HasDebugInfo = false;

  // Scan all the compile-units to see if there are any marked as the main unit.
  // if not, we do not generate debug info.
  for (DebugInfoFinder::iterator I = DbgFinder.compile_unit_begin(),
       E = DbgFinder.compile_unit_end(); I != E; ++I) {
    if (DICompileUnit(*I).isMain()) {
      HasDebugInfo = true;
      break;
    }
  }

  if (!HasDebugInfo) return;

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

  // Emit initial sections.
  EmitSectionLabels();

  // Create all the compile unit DIEs.
  for (DebugInfoFinder::iterator I = DbgFinder.compile_unit_begin(),
         E = DbgFinder.compile_unit_end(); I != E; ++I)
    constructCompileUnit(*I);

  // Create DIEs for each subprogram.
  for (DebugInfoFinder::iterator I = DbgFinder.subprogram_begin(),
         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);

  //getOrCreateTypeDIE
  if (NamedMDNode *NMD = M->getNamedMetadata("llvm.dbg.enum"))
    for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i)
      getOrCreateTypeDIE(DIType(NMD->getOperand(i)));

  if (NamedMDNode *NMD = M->getNamedMetadata("llvm.dbg.ty"))
    for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i)
      getOrCreateTypeDIE(DIType(NMD->getOperand(i)));

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

/// 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 = getFnSpecificMDNode(*(MMI->getModule()), 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->getDbgVariables();
      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 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;
}

/// addCurrentFnArgument - If Var is an current function argument that add
/// it in CurrentFnArguments list.
bool DwarfDebug::addCurrentFnArgument(const MachineFunction *MF,
                                      DbgVariable *Var, DbgScope *Scope) {
  if (Scope != CurrentFnDbgScope) 
    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;

  if (CurrentFnArguments.size() == 0)
    CurrentFnArguments.resize(MF->getFunction()->arg_size());
  CurrentFnArguments[ArgNo - 1] = Var;
  return true;
}

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

/// 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())
        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 && 
          !PrevMI->isIdenticalTo(*MI))
        MultipleValues.push_back(*MI);
      PrevMI = *MI;
    }

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

    Processed.insert(DV);
    DbgVariable *RegVar = new DbgVariable(DV);
    if (!addCurrentFnArgument(MF, RegVar, Scope))
      Scope->addVariable(RegVar);
    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;
      if (Begin->getNumOperands() == 3) {
        if (Begin->getOperand(0).isReg() && Begin->getOperand(1).isImm())
          MLoc.set(Begin->getOperand(0).getReg(), Begin->getOperand(1).getImm());
      } else
        MLoc = Asm->getDebugValueLocation(Begin);

      const MCSymbol *FLabel = getLabelBeforeInsn(Begin);
      const MCSymbol *SLabel = getLabelBeforeInsn(End);
      if (MLoc.getReg())
        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.
        MachineLocation EMLoc;
        if (End->getNumOperands() == 3) {
          if (End->getOperand(0).isReg() && Begin->getOperand(1).isImm())
          EMLoc.set(Begin->getOperand(0).getReg(), Begin->getOperand(1).getImm());
        } else
          EMLoc = Asm->getDebugValueLocation(End);
        if (EMLoc.getReg()) 
          DotDebugLocEntries.
            push_back(DotDebugLocEntry(SLabel, FunctionEndSym, EMLoc));
      }
    }
    DotDebugLocEntries.push_back(DotDebugLocEntry());
  }

  // Collect info for variables that were optimized out.
  const Function *F = MF->getFunction();
  if (NamedMDNode *NMD = getFnSpecificMDNode(*(F->getParent()), 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;
}

/// beginInstruction - Process beginning of an instruction.
void DwarfDebug::beginInstruction(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!");
}

/// endInstruction - Process end of an instruction.
void DwarfDebug::endInstruction(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;
      }

      // Ignore DBG_VALUE. It does not contribute any instruction in output.
      if (MInsn->isDebugValue())
        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();
}

#ifndef NDEBUG
/// CheckLineNumbers - Count basicblocks whose instructions do not have any
/// line number information.
static void CheckLineNumbers(const MachineFunction *MF) {
  for (MachineFunction::const_iterator I = MF->begin(), E = MF->end();
       I != E; ++I) {
    bool FoundLineNo = false;
    for (MachineBasicBlock::const_iterator II = I->begin(), IE = I->end();
         II != IE; ++II) {
      const MachineInstr *MI = II;
      if (!MI->getDebugLoc().isUnknown()) {
        FoundLineNo = true;
        break;
      }
    }
    if (!FoundLineNo && I->size())
      ++BlocksWithoutLineNo;      
  }
}
#endif

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

#ifndef NDEBUG
  CheckLineNumbers(MF);
#endif

  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)
          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 (!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);

    // 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();
        if (NamedMDNode *NMD = 
            getFnSpecificMDNode(*(MF->getFunction()->getParent()), 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()));