DwarfDebug.cpp

//===-- llvm/CodeGen/DwarfDebug.cpp - Dwarf Debug Framework ---------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file contains support for writing dwarf debug info into asm files.
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "dwarfdebug"
#include "DwarfDebug.h"
#include "llvm/Module.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/MC/MCSection.h"
#include "llvm/MC/MCStreamer.h"
#include "llvm/MC/MCAsmInfo.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Target/TargetFrameInfo.h"
#include "llvm/Target/TargetLoweringObjectFile.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/Mangler.h"
#include "llvm/Support/Timer.h"
#include "llvm/Support/Debug.h"
#include "llvm/System/Path.h"
using namespace llvm;

static TimerGroup &getDwarfTimerGroup() {
  static TimerGroup DwarfTimerGroup("Dwarf Debugging");
  return DwarfTimerGroup;
}

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

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

namespace llvm {

//===----------------------------------------------------------------------===//
/// CompileUnit - This dwarf writer support class manages information associate
/// with a source file.
class VISIBILITY_HIDDEN CompileUnit {
  /// ID - File identifier for source.
  ///
  unsigned ID;

  /// Die - Compile unit debug information entry.
  ///
  DIE *Die;

  /// GVToDieMap - Tracks the mapping of unit level debug informaton
  /// variables to debug information entries.
  /// FIXME : Rename GVToDieMap -> NodeToDieMap
  std::map<MDNode *, DIE *> GVToDieMap;

  /// GVToDIEEntryMap - Tracks the mapping of unit level debug informaton
  /// descriptors to debug information entries using a DIEEntry proxy.
  /// FIXME : Rename
  std::map<MDNode *, DIEEntry *> GVToDIEEntryMap;

  /// Globals - A map of globally visible named entities for this unit.
  ///
  StringMap<DIE*> Globals;

  /// DiesSet - Used to uniquely define dies within the compile unit.
  ///
  FoldingSet<DIE> DiesSet;
public:
  CompileUnit(unsigned I, DIE *D)
    : ID(I), Die(D), DiesSet(InitDiesSetSize) {}
  ~CompileUnit() { delete Die; }

  // Accessors.
  unsigned getID() const { return ID; }
  DIE* getDie() const { return Die; }
  StringMap<DIE*> &getGlobals() { return Globals; }

  /// hasContent - Return true if this compile unit has something to write out.
  ///
  bool hasContent() const { return !Die->getChildren().empty(); }

  /// AddGlobal - Add a new global entity to the compile unit.
  ///
  void AddGlobal(const std::string &Name, DIE *Die) { Globals[Name] = Die; }

  /// getDieMapSlotFor - Returns the debug information entry map slot for the
  /// specified debug variable.
  DIE *&getDieMapSlotFor(MDNode *N) { return GVToDieMap[N]; }

  /// getDIEEntrySlotFor - Returns the debug information entry proxy slot for
  /// the specified debug variable.
  DIEEntry *&getDIEEntrySlotFor(MDNode *N) {
    return GVToDIEEntryMap[N];
  }

  /// AddDie - Adds or interns the DIE to the compile unit.
  ///
  DIE *AddDie(DIE &Buffer) {
    FoldingSetNodeID ID;
    Buffer.Profile(ID);
    void *Where;
    DIE *Die = DiesSet.FindNodeOrInsertPos(ID, Where);

    if (!Die) {
      Die = new DIE(Buffer);
      DiesSet.InsertNode(Die, Where);
      this->Die->AddChild(Die);
      Buffer.Detach();
    }

    return Die;
  }
};

//===----------------------------------------------------------------------===//
/// DbgVariable - This class is used to track local variable information.
///
class VISIBILITY_HIDDEN DbgVariable {
  DIVariable Var;                    // Variable Descriptor.
  unsigned FrameIndex;               // Variable frame index.
  bool InlinedFnVar;                 // Variable for an inlined function.
public:
  DbgVariable(DIVariable V, unsigned I, bool IFV)
    : Var(V), FrameIndex(I), InlinedFnVar(IFV)  {}

  // Accessors.
  DIVariable getVariable() const { return Var; }
  unsigned getFrameIndex() const { return FrameIndex; }
  bool isInlinedFnVar() const { return InlinedFnVar; }
};

//===----------------------------------------------------------------------===//
/// DbgScope - This class is used to track scope information.
///
class DbgConcreteScope;
class VISIBILITY_HIDDEN DbgScope {
  DbgScope *Parent;                   // Parent to this scope.
  DIDescriptor Desc;                  // Debug info descriptor for scope.
                                      // Either subprogram or block.
  unsigned StartLabelID;              // Label ID of the beginning of scope.
  unsigned EndLabelID;                // Label ID of the end of scope.
  const MachineInstr *LastInsn;       // Last instruction of this scope.
  const MachineInstr *FirstInsn;      // First instruction of this scope.
  SmallVector<DbgScope *, 4> Scopes;  // Scopes defined in scope.
  SmallVector<DbgVariable *, 8> Variables;// Variables declared in scope.
  SmallVector<DbgConcreteScope *, 8> ConcreteInsts;// Concrete insts of funcs.

  // Private state for dump()
  mutable unsigned IndentLevel;
public:
  DbgScope(DbgScope *P, DIDescriptor D)
    : Parent(P), Desc(D), StartLabelID(0), EndLabelID(0), LastInsn(0),
      FirstInsn(0), IndentLevel(0) {}
  virtual ~DbgScope();

  // Accessors.
  DbgScope *getParent()          const { return Parent; }
  DIDescriptor getDesc()         const { return Desc; }
  unsigned getStartLabelID()     const { return StartLabelID; }
  unsigned getEndLabelID()       const { return EndLabelID; }
  SmallVector<DbgScope *, 4> &getScopes() { return Scopes; }
  SmallVector<DbgVariable *, 8> &getVariables() { return Variables; }
  SmallVector<DbgConcreteScope*,8> &getConcreteInsts() { return ConcreteInsts; }
  void setStartLabelID(unsigned S) { StartLabelID = S; }
  void setEndLabelID(unsigned E)   { EndLabelID = E; }
  void setLastInsn(const MachineInstr *MI) { LastInsn = MI; }
  const MachineInstr *getLastInsn()      { return LastInsn; }
  void setFirstInsn(const MachineInstr *MI) { FirstInsn = MI; }
  const MachineInstr *getFirstInsn()      { return FirstInsn; }
  /// AddScope - Add a scope to the scope.
  ///
  void AddScope(DbgScope *S) { Scopes.push_back(S); }

  /// AddVariable - Add a variable to the scope.
  ///
  void AddVariable(DbgVariable *V) { Variables.push_back(V); }

  /// AddConcreteInst - Add a concrete instance to the scope.
  ///
  void AddConcreteInst(DbgConcreteScope *C) { ConcreteInsts.push_back(C); }

  void FixInstructionMarkers() {
    assert (getFirstInsn() && "First instruction is missing!");
    if (getLastInsn())
      return;
    
    // If a scope does not have an instruction to mark an end then use
    // the end of last child scope.
    SmallVector<DbgScope *, 4> &Scopes = getScopes();
    assert (!Scopes.empty() && "Inner most scope does not have last insn!");
    DbgScope *L = Scopes.back();
    if (!L->getLastInsn())
      L->FixInstructionMarkers();
    setLastInsn(L->getLastInsn());
  }

#ifndef NDEBUG
  void dump() const;
#endif
};

#ifndef NDEBUG
void DbgScope::dump() const {
  raw_ostream &err = errs();
  err.indent(IndentLevel);
  Desc.dump();
  err << " [" << StartLabelID << ", " << EndLabelID << "]\n";

  IndentLevel += 2;

  for (unsigned i = 0, e = Scopes.size(); i != e; ++i)
    if (Scopes[i] != this)
      Scopes[i]->dump();

  IndentLevel -= 2;
}
#endif

//===----------------------------------------------------------------------===//
/// DbgConcreteScope - This class is used to track a scope that holds concrete
/// instance information.
///
class VISIBILITY_HIDDEN DbgConcreteScope : public DbgScope {
  CompileUnit *Unit;
  DIE *Die;                           // Debug info for this concrete scope.
public:
  DbgConcreteScope(DIDescriptor D) : DbgScope(NULL, D) {}

  // Accessors.
  DIE *getDie() const { return Die; }
  void setDie(DIE *D) { Die = D; }
};

DbgScope::~DbgScope() {
  for (unsigned i = 0, N = Scopes.size(); i < N; ++i)
    delete Scopes[i];
  for (unsigned j = 0, M = Variables.size(); j < M; ++j)
    delete Variables[j];
  for (unsigned k = 0, O = ConcreteInsts.size(); k < O; ++k)
    delete ConcreteInsts[k];
}

} // end llvm namespace

DwarfDebug::DwarfDebug(raw_ostream &OS, AsmPrinter *A, const MCAsmInfo *T)
  : Dwarf(OS, A, T, "dbg"), ModuleCU(0),
    AbbreviationsSet(InitAbbreviationsSetSize), Abbreviations(),
    ValuesSet(InitValuesSetSize), Values(), StringPool(),
    SectionSourceLines(), didInitial(false), shouldEmit(false),
    FunctionDbgScope(0), DebugTimer(0) {
  if (TimePassesIsEnabled)
    DebugTimer = new Timer("Dwarf Debug Writer",
                           getDwarfTimerGroup());
}
DwarfDebug::~DwarfDebug() {
  for (unsigned j = 0, M = Values.size(); j < M; ++j)
    delete Values[j];

  for (DenseMap<const MDNode *, DbgScope *>::iterator
         I = AbstractInstanceRootMap.begin(),
         E = AbstractInstanceRootMap.end(); I != E;++I)
    delete I->second;

  delete DebugTimer;
}

/// AssignAbbrevNumber - Define a unique number for the abbreviation.
///
void DwarfDebug::AssignAbbrevNumber(DIEAbbrev &Abbrev) {
  // Profile the node so that we can make it unique.
  FoldingSetNodeID ID;
  Abbrev.Profile(ID);

  // Check the set for priors.
  DIEAbbrev *InSet = AbbreviationsSet.GetOrInsertNode(&Abbrev);

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

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

/// CreateDIEEntry - Creates a new DIEEntry to be a proxy for a debug
/// information entry.
DIEEntry *DwarfDebug::CreateDIEEntry(DIE *Entry) {
  DIEEntry *Value;

  if (Entry) {
    FoldingSetNodeID ID;
    DIEEntry::Profile(ID, Entry);
    void *Where;
    Value = static_cast<DIEEntry *>(ValuesSet.FindNodeOrInsertPos(ID, Where));

    if (Value) return Value;

    Value = new DIEEntry(Entry);
    ValuesSet.InsertNode(Value, Where);
  } else {
    Value = new DIEEntry(Entry);
  }

  Values.push_back(Value);
  return Value;
}

/// SetDIEEntry - Set a DIEEntry once the debug information entry is defined.
///
void DwarfDebug::SetDIEEntry(DIEEntry *Value, DIE *Entry) {
  Value->setEntry(Entry);

  // Add to values set if not already there.  If it is, we merely have a
  // duplicate in the values list (no harm.)
  ValuesSet.GetOrInsertNode(Value);
}

/// AddUInt - Add an unsigned integer attribute data and value.
///
void DwarfDebug::AddUInt(DIE *Die, unsigned Attribute,
                         unsigned Form, uint64_t Integer) {
  if (!Form) Form = DIEInteger::BestForm(false, Integer);

  FoldingSetNodeID ID;
  DIEInteger::Profile(ID, Integer);
  void *Where;
  DIEValue *Value = ValuesSet.FindNodeOrInsertPos(ID, Where);

  if (!Value) {
    Value = new DIEInteger(Integer);
    ValuesSet.InsertNode(Value, Where);
    Values.push_back(Value);
  }

  Die->AddValue(Attribute, Form, Value);
}

/// AddSInt - Add an signed integer attribute data and value.
///
void DwarfDebug::AddSInt(DIE *Die, unsigned Attribute,
                         unsigned Form, int64_t Integer) {
  if (!Form) Form = DIEInteger::BestForm(true, Integer);

  FoldingSetNodeID ID;
  DIEInteger::Profile(ID, (uint64_t)Integer);
  void *Where;
  DIEValue *Value = ValuesSet.FindNodeOrInsertPos(ID, Where);

  if (!Value) {
    Value = new DIEInteger(Integer);
    ValuesSet.InsertNode(Value, Where);
    Values.push_back(Value);
  }

  Die->AddValue(Attribute, Form, Value);
}

/// AddString - Add a string attribute data and value.
///
void DwarfDebug::AddString(DIE *Die, unsigned Attribute, unsigned Form,
                           const std::string &String) {
  FoldingSetNodeID ID;
  DIEString::Profile(ID, String);
  void *Where;
  DIEValue *Value = ValuesSet.FindNodeOrInsertPos(ID, Where);

  if (!Value) {
    Value = new DIEString(String);
    ValuesSet.InsertNode(Value, Where);
    Values.push_back(Value);
  }

  Die->AddValue(Attribute, Form, Value);
}

/// AddLabel - Add a Dwarf label attribute data and value.
///
void DwarfDebug::AddLabel(DIE *Die, unsigned Attribute, unsigned Form,
                          const DWLabel &Label) {
  FoldingSetNodeID ID;
  DIEDwarfLabel::Profile(ID, Label);
  void *Where;
  DIEValue *Value = ValuesSet.FindNodeOrInsertPos(ID, Where);

  if (!Value) {
    Value = new DIEDwarfLabel(Label);
    ValuesSet.InsertNode(Value, Where);
    Values.push_back(Value);
  }

  Die->AddValue(Attribute, Form, Value);
}

/// AddObjectLabel - Add an non-Dwarf label attribute data and value.
///
void DwarfDebug::AddObjectLabel(DIE *Die, unsigned Attribute, unsigned Form,
                                const std::string &Label) {
  FoldingSetNodeID ID;
  DIEObjectLabel::Profile(ID, Label);
  void *Where;
  DIEValue *Value = ValuesSet.FindNodeOrInsertPos(ID, Where);

  if (!Value) {
    Value = new DIEObjectLabel(Label);
    ValuesSet.InsertNode(Value, Where);
    Values.push_back(Value);
  }

  Die->AddValue(Attribute, Form, Value);
}

/// AddSectionOffset - Add a section offset label attribute data and value.
///
void DwarfDebug::AddSectionOffset(DIE *Die, unsigned Attribute, unsigned Form,
                                  const DWLabel &Label, const DWLabel &Section,
                                  bool isEH, bool useSet) {
  FoldingSetNodeID ID;
  DIESectionOffset::Profile(ID, Label, Section);
  void *Where;
  DIEValue *Value = ValuesSet.FindNodeOrInsertPos(ID, Where);

  if (!Value) {
    Value = new DIESectionOffset(Label, Section, isEH, useSet);
    ValuesSet.InsertNode(Value, Where);
    Values.push_back(Value);
  }

  Die->AddValue(Attribute, Form, Value);
}

/// AddDelta - Add a label delta attribute data and value.
///
void DwarfDebug::AddDelta(DIE *Die, unsigned Attribute, unsigned Form,
                          const DWLabel &Hi, const DWLabel &Lo) {
  FoldingSetNodeID ID;
  DIEDelta::Profile(ID, Hi, Lo);
  void *Where;
  DIEValue *Value = ValuesSet.FindNodeOrInsertPos(ID, Where);

  if (!Value) {
    Value = new DIEDelta(Hi, Lo);
    ValuesSet.InsertNode(Value, Where);
    Values.push_back(Value);
  }

  Die->AddValue(Attribute, Form, Value);
}

/// AddBlock - Add block data.
///
void DwarfDebug::AddBlock(DIE *Die, unsigned Attribute, unsigned Form,
                          DIEBlock *Block) {
  Block->ComputeSize(TD);
  FoldingSetNodeID ID;
  Block->Profile(ID);
  void *Where;
  DIEValue *Value = ValuesSet.FindNodeOrInsertPos(ID, Where);

  if (!Value) {
    Value = Block;
    ValuesSet.InsertNode(Value, Where);
    Values.push_back(Value);
  } else {
    // Already exists, reuse the previous one.
    delete Block;
    Block = cast<DIEBlock>(Value);
  }

  Die->AddValue(Attribute, Block->BestForm(), Value);
}

/// AddSourceLine - Add location information to specified debug information
/// entry.
void DwarfDebug::AddSourceLine(DIE *Die, const DIVariable *V) {
  // If there is no compile unit specified, don't add a line #.
  if (V->getCompileUnit().isNull())
    return;

  unsigned Line = V->getLineNumber();
  unsigned FileID = FindCompileUnit(V->getCompileUnit()).getID();
  assert(FileID && "Invalid file id");
  AddUInt(Die, dwarf::DW_AT_decl_file, 0, FileID);
  AddUInt(Die, dwarf::DW_AT_decl_line, 0, Line);
}

/// AddSourceLine - Add location information to specified debug information
/// entry.
void DwarfDebug::AddSourceLine(DIE *Die, const DIGlobal *G) {
  // If there is no compile unit specified, don't add a line #.
  if (G->getCompileUnit().isNull())
    return;

  unsigned Line = G->getLineNumber();
  unsigned FileID = FindCompileUnit(G->getCompileUnit()).getID();
  assert(FileID && "Invalid file id");
  AddUInt(Die, dwarf::DW_AT_decl_file, 0, FileID);
  AddUInt(Die, dwarf::DW_AT_decl_line, 0, Line);
}

/// AddSourceLine - Add location information to specified debug information
/// entry.
void DwarfDebug::AddSourceLine(DIE *Die, const DISubprogram *SP) {
  // If there is no compile unit specified, don't add a line #.
  if (SP->getCompileUnit().isNull())
    return;
  // If the line number is 0, don't add it.
  if (SP->getLineNumber() == 0)
    return;


  unsigned Line = SP->getLineNumber();
  unsigned FileID = FindCompileUnit(SP->getCompileUnit()).getID();
  assert(FileID && "Invalid file id");
  AddUInt(Die, dwarf::DW_AT_decl_file, 0, FileID);
  AddUInt(Die, dwarf::DW_AT_decl_line, 0, Line);
}

/// AddSourceLine - Add location information to specified debug information
/// entry.
void DwarfDebug::AddSourceLine(DIE *Die, const DIType *Ty) {
  // If there is no compile unit specified, don't add a line #.
  DICompileUnit CU = Ty->getCompileUnit();
  if (CU.isNull())
    return;

  unsigned Line = Ty->getLineNumber();
  unsigned FileID = FindCompileUnit(CU).getID();
  assert(FileID && "Invalid file id");
  AddUInt(Die, dwarf::DW_AT_decl_file, 0, FileID);
  AddUInt(Die, dwarf::DW_AT_decl_line, 0, Line);
}

/* Byref variables, in Blocks, are declared by the programmer as
   "SomeType VarName;", but the compiler creates a
   __Block_byref_x_VarName struct, and gives the variable VarName
   either the struct, or a pointer to the struct, as its type.  This
   is necessary for various behind-the-scenes things the compiler
   needs to do with by-reference variables in blocks.

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

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

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

   NOTE: In order for this to not completely fail on the debugger
   side, the Debug Information Entry for the variable VarName needs to
   have a DW_AT_location that tells the debugger how to unwind through
   the pointers and __Block_byref_x_VarName struct to find the actual
   value of the variable.  The function AddBlockByrefType does this.  */

/// Find the type the programmer originally declared the variable to be
/// and return that type.
///
DIType DwarfDebug::GetBlockByrefType(DIType Ty, std::string Name) {

  DIType subType = Ty;
  unsigned tag = Ty.getTag();

  if (tag == dwarf::DW_TAG_pointer_type) {
    DIDerivedType DTy = DIDerivedType(Ty.getNode());
    subType = DTy.getTypeDerivedFrom();
  }

  DICompositeType blockStruct = DICompositeType(subType.getNode());

  DIArray Elements = blockStruct.getTypeArray();

  if (Elements.isNull())
    return Ty;

  for (unsigned i = 0, N = Elements.getNumElements(); i < N; ++i) {
    DIDescriptor Element = Elements.getElement(i);
    DIDerivedType DT = DIDerivedType(Element.getNode());
    if (strcmp(Name.c_str(), DT.getName()) == 0)
      return (DT.getTypeDerivedFrom());
  }

  return Ty;
}

/// AddComplexAddress - Start with the address based on the location provided,
/// and generate the DWARF information necessary to find the actual variable
/// given the extra address information encoded in the DIVariable, starting from
/// the starting location.  Add the DWARF information to the die.
///
void DwarfDebug::AddComplexAddress(DbgVariable *&DV, DIE *Die,
                                   unsigned Attribute,
                                   const MachineLocation &Location) {
  const DIVariable &VD = DV->getVariable();
  DIType Ty = VD.getType();

  // Decode the original location, and use that as the start of the byref
  // variable's location.
  unsigned Reg = RI->getDwarfRegNum(Location.getReg(), false);
  DIEBlock *Block = new DIEBlock();

  if (Location.isReg()) {
    if (Reg < 32) {
      AddUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_reg0 + Reg);
    } else {
      Reg = Reg - dwarf::DW_OP_reg0;
      AddUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_breg0 + Reg);
      AddUInt(Block, 0, dwarf::DW_FORM_udata, Reg);
    }
  } else {
    if (Reg < 32)
      AddUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_breg0 + Reg);
    else {
      AddUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_bregx);
      AddUInt(Block, 0, dwarf::DW_FORM_udata, Reg);
    }

    AddUInt(Block, 0, dwarf::DW_FORM_sdata, Location.getOffset());
  }

  for (unsigned i = 0, N = VD.getNumAddrElements(); i < N; ++i) {
    uint64_t Element = VD.getAddrElement(i);

    if (Element == DIFactory::OpPlus) {
      AddUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_plus_uconst);
      AddUInt(Block, 0, dwarf::DW_FORM_udata, VD.getAddrElement(++i));
    } else if (Element == DIFactory::OpDeref) {
      AddUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_deref);
    } else llvm_unreachable("unknown DIFactory Opcode");
  }

  // Now attach the location information to the DIE.
  AddBlock(Die, Attribute, 0, Block);
}

/* Byref variables, in Blocks, are declared by the programmer as "SomeType
   VarName;", but the compiler creates a __Block_byref_x_VarName struct, and
   gives the variable VarName either the struct, or a pointer to the struct, as
   its type.  This is necessary for various behind-the-scenes things the
   compiler needs to do with by-reference variables in Blocks.

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

   The function GetBlockByrefType dives into the __Block_byref_x_VarName
   struct to find the original type of the variable, which is then assigned to
   the variable's Debug Information Entry as its real type.  So far, so good.
   However now the debugger will expect the variable VarName to have the type
   SomeType.  So we need the location attribute for the variable to be an
   expression that explains to the debugger how to navigate through the
   pointers and struct to find the actual variable of type SomeType.

   The following function does just that.  We start by getting
   the "normal" location for the variable. This will be the location
   of either the struct __Block_byref_x_VarName or the pointer to the
   struct __Block_byref_x_VarName.

   The struct will look something like:

   struct __Block_byref_x_VarName {
     ... <various fields>
     struct __Block_byref_x_VarName *forwarding;
     ... <various other fields>
     SomeType VarName;
     ... <maybe more fields>
   };

   If we are given the struct directly (as our starting point) we
   need to tell the debugger to:

   1).  Add the offset of the forwarding field.

   2).  Follow that pointer to get the the real __Block_byref_x_VarName
   struct to use (the real one may have been copied onto the heap).

   3).  Add the offset for the field VarName, to find the actual variable.

   If we started with a pointer to the struct, then we need to
   dereference that pointer first, before the other steps.
   Translating this into DWARF ops, we will need to append the following
   to the current location description for the variable:

   DW_OP_deref                    -- optional, if we start with a pointer
   DW_OP_plus_uconst <forward_fld_offset>
   DW_OP_deref
   DW_OP_plus_uconst <varName_fld_offset>

   That is what this function does.  */

/// AddBlockByrefAddress - Start with the address based on the location
/// provided, and generate the DWARF information necessary to find the
/// actual Block variable (navigating the Block struct) based on the
/// starting location.  Add the DWARF information to the die.  For
/// more information, read large comment just above here.
///
void DwarfDebug::AddBlockByrefAddress(DbgVariable *&DV, DIE *Die,
                                      unsigned Attribute,
                                      const MachineLocation &Location) {
  const DIVariable &VD = DV->getVariable();
  DIType Ty = VD.getType();
  DIType TmpTy = Ty;
  unsigned Tag = Ty.getTag();
  bool isPointer = false;

  const char *varName = VD.getName();

  if (Tag == dwarf::DW_TAG_pointer_type) {
    DIDerivedType DTy = DIDerivedType(Ty.getNode());
    TmpTy = DTy.getTypeDerivedFrom();
    isPointer = true;
  }

  DICompositeType blockStruct = DICompositeType(TmpTy.getNode());

  // Find the __forwarding field and the variable field in the __Block_byref
  // struct.
  DIArray Fields = blockStruct.getTypeArray();
  DIDescriptor varField = DIDescriptor();
  DIDescriptor forwardingField = DIDescriptor();


  for (unsigned i = 0, N = Fields.getNumElements(); i < N; ++i) {
    DIDescriptor Element = Fields.getElement(i);
    DIDerivedType DT = DIDerivedType(Element.getNode());
    const char *fieldName = DT.getName();
    if (strcmp(fieldName, "__forwarding") == 0)
      forwardingField = Element;
    else if (strcmp(fieldName, varName) == 0)
      varField = Element;
  }

  assert(!varField.isNull() && "Can't find byref variable in Block struct");
  assert(!forwardingField.isNull()
         && "Can't find forwarding field in Block struct");

  // Get the offsets for the forwarding field and the variable field.
  unsigned int forwardingFieldOffset =
    DIDerivedType(forwardingField.getNode()).getOffsetInBits() >> 3;
  unsigned int varFieldOffset =
    DIDerivedType(varField.getNode()).getOffsetInBits() >> 3;

  // Decode the original location, and use that as the start of the byref
  // variable's location.
  unsigned Reg = RI->getDwarfRegNum(Location.getReg(), false);
  DIEBlock *Block = new DIEBlock();

  if (Location.isReg()) {
    if (Reg < 32)
      AddUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_reg0 + Reg);
    else {
      Reg = Reg - dwarf::DW_OP_reg0;
      AddUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_breg0 + Reg);
      AddUInt(Block, 0, dwarf::DW_FORM_udata, Reg);
    }
  } else {
    if (Reg < 32)
      AddUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_breg0 + Reg);
    else {
      AddUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_bregx);
      AddUInt(Block, 0, dwarf::DW_FORM_udata, Reg);
    }

    AddUInt(Block, 0, dwarf::DW_FORM_sdata, Location.getOffset());
  }

  // If we started with a pointer to the __Block_byref... struct, then
  // the first thing we need to do is dereference the pointer (DW_OP_deref).
  if (isPointer)
    AddUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_deref);

  // Next add the offset for the '__forwarding' field:
  // DW_OP_plus_uconst ForwardingFieldOffset.  Note there's no point in
  // adding the offset if it's 0.
  if (forwardingFieldOffset > 0) {
    AddUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_plus_uconst);
    AddUInt(Block, 0, dwarf::DW_FORM_udata, forwardingFieldOffset);
  }

  // Now dereference the __forwarding field to get to the real __Block_byref
  // struct:  DW_OP_deref.
  AddUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_deref);

  // Now that we've got the real __Block_byref... struct, add the offset
  // for the variable's field to get to the location of the actual variable:
  // DW_OP_plus_uconst varFieldOffset.  Again, don't add if it's 0.
  if (varFieldOffset > 0) {
    AddUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_plus_uconst);
    AddUInt(Block, 0, dwarf::DW_FORM_udata, varFieldOffset);
  }

  // Now attach the location information to the DIE.
  AddBlock(Die, Attribute, 0, Block);
}

/// AddAddress - Add an address attribute to a die based on the location
/// provided.
void DwarfDebug::AddAddress(DIE *Die, unsigned Attribute,
                            const MachineLocation &Location) {
  unsigned Reg = RI->getDwarfRegNum(Location.getReg(), false);
  DIEBlock *Block = new DIEBlock();

  if (Location.isReg()) {
    if (Reg < 32) {
      AddUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_reg0 + Reg);
    } else {
      AddUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_regx);
      AddUInt(Block, 0, dwarf::DW_FORM_udata, Reg);
    }
  } else {
    if (Reg < 32) {
      AddUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_breg0 + Reg);
    } else {
      AddUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_bregx);
      AddUInt(Block, 0, dwarf::DW_FORM_udata, Reg);
    }

    AddUInt(Block, 0, dwarf::DW_FORM_sdata, Location.getOffset());
  }

  AddBlock(Die, Attribute, 0, Block);
}

/// AddType - Add a new type attribute to the specified entity.
void DwarfDebug::AddType(CompileUnit *DW_Unit, DIE *Entity, DIType Ty) {
  if (Ty.isNull())
    return;

  // Check for pre-existence.
  DIEEntry *&Slot = DW_Unit->getDIEEntrySlotFor(Ty.getNode());

  // If it exists then use the existing value.
  if (Slot) {
    Entity->AddValue(dwarf::DW_AT_type, dwarf::DW_FORM_ref4, Slot);
    return;
  }

  // Set up proxy.
  Slot = CreateDIEEntry();

  // Construct type.
  DIE Buffer(dwarf::DW_TAG_base_type);
  if (Ty.isBasicType())
    ConstructTypeDIE(DW_Unit, Buffer, DIBasicType(Ty.getNode()));
  else if (Ty.isCompositeType())
    ConstructTypeDIE(DW_Unit, Buffer, DICompositeType(Ty.getNode()));
  else {
    assert(Ty.isDerivedType() && "Unknown kind of DIType");
    ConstructTypeDIE(DW_Unit, Buffer, DIDerivedType(Ty.getNode()));
  }

  // Add debug information entry to entity and appropriate context.
  DIE *Die = NULL;
  DIDescriptor Context = Ty.getContext();
  if (!Context.isNull())
    Die = DW_Unit->getDieMapSlotFor(Context.getNode());

  if (Die) {
    DIE *Child = new DIE(Buffer);
    Die->AddChild(Child);
    Buffer.Detach();
    SetDIEEntry(Slot, Child);
  } else {
    Die = DW_Unit->AddDie(Buffer);
    SetDIEEntry(Slot, Die);
  }

  Entity->AddValue(dwarf::DW_AT_type, dwarf::DW_FORM_ref4, Slot);
}

/// ConstructTypeDIE - Construct basic type die from DIBasicType.
void DwarfDebug::ConstructTypeDIE(CompileUnit *DW_Unit, DIE &Buffer,
                                  DIBasicType BTy) {
  // Get core information.
  const char *Name = BTy.getName();
  Buffer.setTag(dwarf::DW_TAG_base_type);
  AddUInt(&Buffer, dwarf::DW_AT_encoding,  dwarf::DW_FORM_data1,
          BTy.getEncoding());

  // Add name if not anonymous or intermediate type.
  if (Name)
    AddString(&Buffer, dwarf::DW_AT_name, dwarf::DW_FORM_string, Name);
  uint64_t Size = BTy.getSizeInBits() >> 3;
  AddUInt(&Buffer, dwarf::DW_AT_byte_size, 0, Size);
}

/// ConstructTypeDIE - Construct derived type die from DIDerivedType.
void DwarfDebug::ConstructTypeDIE(CompileUnit *DW_Unit, DIE &Buffer,
                                  DIDerivedType DTy) {
  // Get core information.
  const char *Name = DTy.getName();
  uint64_t Size = DTy.getSizeInBits() >> 3;
  unsigned Tag = DTy.getTag();

  // FIXME - Workaround for templates.
  if (Tag == dwarf::DW_TAG_inheritance) Tag = dwarf::DW_TAG_reference_type;

  Buffer.setTag(Tag);

  // Map to main type, void will not have a type.
  DIType FromTy = DTy.getTypeDerivedFrom();
  AddType(DW_Unit, &Buffer, FromTy);

  // Add name if not anonymous or intermediate type.
  if (Name)
    AddString(&Buffer, dwarf::DW_AT_name, dwarf::DW_FORM_string, Name);

  // Add size if non-zero (derived types might be zero-sized.)
  if (Size)
    AddUInt(&Buffer, dwarf::DW_AT_byte_size, 0, Size);

  // Add source line info if available and TyDesc is not a forward declaration.
  if (!DTy.isForwardDecl())
    AddSourceLine(&Buffer, &DTy);
}

/// ConstructTypeDIE - Construct type DIE from DICompositeType.
void DwarfDebug::ConstructTypeDIE(CompileUnit *DW_Unit, DIE &Buffer,
                                  DICompositeType CTy) {
  // Get core information.
  const char *Name = CTy.getName();

  uint64_t Size = CTy.getSizeInBits() >> 3;
  unsigned Tag = CTy.getTag();
  Buffer.setTag(Tag);

  switch (Tag) {
  case dwarf::DW_TAG_vector_type:
  case dwarf::DW_TAG_array_type:
    ConstructArrayTypeDIE(DW_Unit, Buffer, &CTy);
    break;
  case dwarf::DW_TAG_enumeration_type: {
    DIArray Elements = CTy.getTypeArray();

    // Add enumerators to enumeration type.
    for (unsigned i = 0, N = Elements.getNumElements(); i < N; ++i) {
      DIE *ElemDie = NULL;
      DIEnumerator Enum(Elements.getElement(i).getNode());
      ElemDie = ConstructEnumTypeDIE(DW_Unit, &Enum);
      Buffer.AddChild(ElemDie);
    }
  }
    break;
  case dwarf::DW_TAG_subroutine_type: {
    // Add return type.
    DIArray Elements = CTy.getTypeArray();
    DIDescriptor RTy = Elements.getElement(0);
    AddType(DW_Unit, &Buffer, DIType(RTy.getNode()));

    // Add prototype flag.
    AddUInt(&Buffer, dwarf::DW_AT_prototyped, dwarf::DW_FORM_flag, 1);

    // Add arguments.
    for (unsigned i = 1, N = Elements.getNumElements(); i < N; ++i) {
      DIE *Arg = new DIE(dwarf::DW_TAG_formal_parameter);
      DIDescriptor Ty = Elements.getElement(i);
      AddType(DW_Unit, Arg, DIType(Ty.getNode()));
      Buffer.AddChild(Arg);
    }
  }
    break;
  case dwarf::DW_TAG_structure_type:
  case dwarf::DW_TAG_union_type:
  case dwarf::DW_TAG_class_type: {
    // Add elements to structure type.
    DIArray Elements = CTy.getTypeArray();

    // A forward struct declared type may not have elements available.
    if (Elements.isNull())
      break;

    // Add elements to structure type.
    for (unsigned i = 0, N = Elements.getNumElements(); i < N; ++i) {
      DIDescriptor Element = Elements.getElement(i);
      if (Element.isNull())
        continue;
      DIE *ElemDie = NULL;
      if (Element.getTag() == dwarf::DW_TAG_subprogram)
        ElemDie = CreateSubprogramDIE(DW_Unit,
                                      DISubprogram(Element.getNode()));
      else
        ElemDie = CreateMemberDIE(DW_Unit,
                                  DIDerivedType(Element.getNode()));
      Buffer.AddChild(ElemDie);
    }