Add preliminary support for hashing DIEs and breaking them into

type units.

Initially this support is used in the computation of an ODR checker
for C++. For now we're attaching it to the DIE, but in the future
it will be attached to the type unit.

This also starts breaking out types into the separation for type
units, but without actually splitting the DIEs.

In preparation for hashing the DIEs this adds a DIEString type
that contains a StringRef with the string contained at the label.

llvm-svn: 187213

5 files changed, 254 insertions, 4 deletions

diff --git a/llvm/lib/CodeGen/AsmPrinter/DIE.cpp b/llvm/lib/CodeGen/AsmPrinter/DIE.cpp
index d6caef7e5b8..0b154123315 100644
--- a/llvm/lib/CodeGen/AsmPrinter/DIE.cpp
+++ b/llvm/lib/CodeGen/AsmPrinter/DIE.cpp
@@ -24,6 +24,7 @@
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/FormattedStream.h"
+#include "llvm/Support/MD5.h"
 using namespace llvm;
 
 //===----------------------------------------------------------------------===//
@@ -323,6 +324,29 @@ void DIEDelta::print(raw_ostream &O) const {
 #endif
 
 //===----------------------------------------------------------------------===//
+// DIEString Implementation
+//===----------------------------------------------------------------------===//
+
+/// EmitValue - Emit string value.
+///
+void DIEString::EmitValue(AsmPrinter *AP, unsigned Form) const {
+  Access->EmitValue(AP, Form);
+}
+
+/// SizeOf - Determine size of delta value in bytes.
+///
+unsigned DIEString::SizeOf(AsmPrinter *AP, unsigned Form) const {
+  return Access->SizeOf(AP, Form);
+}
+
+#ifndef NDEBUG
+void DIEString::print(raw_ostream &O) const {
+  O << "String: " << Str << "\tSymbol: ";
+  Access->print(O);
+}
+#endif
+
+//===----------------------------------------------------------------------===//
 // DIEEntry Implementation
 //===----------------------------------------------------------------------===//
 
diff --git a/llvm/lib/CodeGen/AsmPrinter/DIE.h b/llvm/lib/CodeGen/AsmPrinter/DIE.h
index 3b04e206254..e2f49d64bee 100644
--- a/llvm/lib/CodeGen/AsmPrinter/DIE.h
+++ b/llvm/lib/CodeGen/AsmPrinter/DIE.h
@@ -346,6 +346,36 @@ namespace llvm {
   };
 
   //===--------------------------------------------------------------------===//
+  /// DIEString - A container for string values.
+  ///
+  class DIEString : public DIEValue {
+    const DIEValue *Access;
+    const StringRef Str;
+
+  public:
+    DIEString(const DIEValue *Acc, const StringRef S)
+        : DIEValue(isString), Access(Acc), Str(S) {}
+
+    /// getString - Grab the string out of the object.
+    StringRef getString() const { return Str; }
+
+    /// EmitValue - Emit delta value.
+    ///
+    virtual void EmitValue(AsmPrinter *AP, unsigned Form) const;
+
+    /// SizeOf - Determine size of delta value in bytes.
+    ///
+    virtual unsigned SizeOf(AsmPrinter *AP, unsigned Form) const;
+
+    // Implement isa/cast/dyncast.
+    static bool classof(const DIEValue *D) { return D->getType() == isString; }
+
+  #ifndef NDEBUG
+    virtual void print(raw_ostream &O) const;
+  #endif
+  };
+
+  //===--------------------------------------------------------------------===//
   /// DIEEntry - A pointer to another debug information entry.  An instance of
   /// this class can also be used as a proxy for a debug information entry not
   /// yet defined (ie. types.)
diff --git a/llvm/lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp b/llvm/lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp
index 37eedc27e5a..e912076a65b 100644
--- a/llvm/lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp
+++ b/llvm/lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp
@@ -132,21 +132,24 @@ void CompileUnit::addSInt(DIE *Die, unsigned Attribute,
 /// into another table which gets us the static offset into the string
 /// table.
 void CompileUnit::addString(DIE *Die, unsigned Attribute, StringRef String) {
+  DIEValue *Value;
+  unsigned Form;
   if (!DD->useSplitDwarf()) {
     MCSymbol *Symb = DU->getStringPoolEntry(String);
-    DIEValue *Value;
     if (Asm->needsRelocationsForDwarfStringPool())
       Value = new (DIEValueAllocator) DIELabel(Symb);
     else {
       MCSymbol *StringPool = DU->getStringPoolSym();
       Value = new (DIEValueAllocator) DIEDelta(Symb, StringPool);
     }
-    Die->addValue(Attribute, dwarf::DW_FORM_strp, Value);
+    Form = dwarf::DW_FORM_strp;
   } else {
     unsigned idx = DU->getStringPoolIndex(String);
-    DIEValue *Value = new (DIEValueAllocator) DIEInteger(idx);
-    Die->addValue(Attribute, dwarf::DW_FORM_GNU_str_index, Value);
+    Value = new (DIEValueAllocator) DIEInteger(idx);
+    Form = dwarf::DW_FORM_GNU_str_index;
   }
+  DIEValue *Str = new (DIEValueAllocator) DIEString(Value, String);
+  Die->addValue(Attribute, Form, Str);
 }
 
 /// addLocalString - Add a string attribute data and value. This is guaranteed
@@ -878,6 +881,39 @@ void CompileUnit::constructTypeDIE(DIE &Buffer, DIDerivedType DTy) {
     addSourceLine(&Buffer, DTy);
 }
 
+/// Return true if the type is appropriately scoped to be contained inside
+/// its own type unit.
+static bool isTypeUnitScoped(DIType Ty) {
+  DIScope Parent = Ty.getContext();
+  while (Parent) {
+    // Don't generate a hash for anything scoped inside a function.
+    if (Parent.isSubprogram())
+      return false;
+    Parent = Parent.getContext();
+  }
+  return true;
+}
+
+/// Return true if the type should be split out into a type unit.
+static bool shouldCreateTypeUnit(DICompositeType CTy) {
+  unsigned Tag = CTy.getTag();
+
+  switch (Tag) {
+  case dwarf::DW_TAG_structure_type:
+  case dwarf::DW_TAG_union_type:
+  case dwarf::DW_TAG_enumeration_type:
+  case dwarf::DW_TAG_class_type:
+    // If this is a class, structure, union, or enumeration type
+    // that is not a declaration, is a type definition, and not scoped
+    // inside a function then separate this out as a type unit.
+    if (CTy.isForwardDecl() || !isTypeUnitScoped(CTy))
+      return 0;
+    return 1;
+  default:
+    return 0;
+  }
+}
+
 /// constructTypeDIE - Construct type DIE from DICompositeType.
 void CompileUnit::constructTypeDIE(DIE &Buffer, DICompositeType CTy) {
   // Get core information.
@@ -1075,6 +1111,10 @@ void CompileUnit::constructTypeDIE(DIE &Buffer, DICompositeType CTy) {
       addUInt(&Buffer, dwarf::DW_AT_APPLE_runtime_class,
               dwarf::DW_FORM_data1, RLang);
   }
+  // If this is a type applicable to a type unit it then add it to the
+  // list of types we'll compute a hash for later.
+  if (shouldCreateTypeUnit(CTy))
+    DD->addTypeUnitType(&Buffer);
 }
 
 /// getOrCreateTemplateTypeParameterDIE - Find existing DIE or create new DIE
diff --git a/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp b/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp
index 8dc44b7fdc4..fae1ece086f 100644
--- a/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp
+++ b/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp
@@ -36,6 +36,7 @@
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/FormattedStream.h"
+#include "llvm/Support/MD5.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Timer.h"
 #include "llvm/Support/ValueHandle.h"
@@ -60,6 +61,11 @@ GenerateDwarfPubNamesSection("generate-dwarf-pubnames", cl::Hidden,
                              cl::init(false),
                              cl::desc("Generate DWARF pubnames section"));
 
+static cl::opt<bool>
+GenerateODRHash("generate-odr-hash", cl::Hidden,
+                cl::desc("Add an ODR hash to external type DIEs."),
+                cl::init(false));
+
 namespace {
 enum DefaultOnOff {
   Default,
@@ -956,6 +962,135 @@ void DwarfDebug::collectDeadVariables() {
   DeleteContainerSeconds(DeadFnScopeMap);
 }
 
+// Type Signature computation code.
+typedef ArrayRef<uint8_t> HashValue;
+
+/// \brief Grabs the string in whichever attribute is passed in and returns
+/// a reference to it.
+static StringRef getDIEStringAttr(DIE *Die, unsigned Attr) {
+  const SmallVectorImpl<DIEValue *> &Values = Die->getValues();
+  const DIEAbbrev &Abbrevs = Die->getAbbrev();
+
+  // Iterate through all the attributes until we find the one we're
+  // looking for, if we can't find it return an empty string.
+  for (size_t i = 0; i < Values.size(); ++i) {
+    if (Abbrevs.getData()[i].getAttribute() == Attr) {
+      DIEValue *V = Values[i];
+      assert(isa<DIEString>(V) && "String requested. Not a string.");
+      DIEString *S = cast<DIEString>(V);
+      return S->getString();
+    }
+  }
+  return StringRef("");
+}
+
+/// \brief Adds the string in \p Str to the hash in \p Hash. This also hashes
+/// a trailing NULL with the string.
+static void addStringToHash(MD5 &Hash, StringRef Str) {
+  DEBUG(dbgs() << "Adding string " << Str << " to hash.\n");
+  HashValue SVal((const uint8_t *)Str.data(), Str.size());
+  const uint8_t NB = '\0';
+  HashValue NBVal((const uint8_t *)&NB, 1);
+  Hash.update(SVal);
+  Hash.update(NBVal);
+}
+
+/// \brief Adds the character string in \p Str to the hash in \p Hash. This does
+/// not hash a trailing NULL on the character.
+static void addLetterToHash(MD5 &Hash, StringRef Str) {
+  DEBUG(dbgs() << "Adding letter " << Str << " to hash.\n");
+  assert(Str.size() == 1 && "Trying to add a too large letter?");
+  HashValue SVal((const uint8_t *)Str.data(), Str.size());
+  Hash.update(SVal);
+}
+
+// FIXME: These are copied and only slightly modified out of LEB128.h.
+
+/// \brief Adds the unsigned in \p N to the hash in \p Hash. This also encodes
+/// the unsigned as a ULEB128.
+static void addULEB128ToHash(MD5 &Hash, uint64_t Value) {
+  DEBUG(dbgs() << "Adding ULEB128 " << Value << " to hash.\n");
+  do {
+    uint8_t Byte = Value & 0x7f;
+    Value >>= 7;
+    if (Value != 0)
+      Byte |= 0x80; // Mark this byte to show that more bytes will follow.
+    Hash.update(Byte);
+  } while (Value != 0);
+}
+
+/// \brief Including \p Parent adds the context of Parent to \p Hash.
+static void addParentContextToHash(MD5 &Hash, DIE *Parent) {
+  unsigned Tag = Parent->getTag();
+
+  DEBUG(dbgs() << "Adding parent context to hash...\n");
+  
+  // For each surrounding type or namespace...
+  if (Tag != dwarf::DW_TAG_namespace && Tag != dwarf::DW_TAG_class_type &&
+      Tag != dwarf::DW_TAG_structure_type)
+    return;
+
+  // ... beginning with the outermost such construct...
+  if (Parent->getParent() != NULL)
+    addParentContextToHash(Hash, Parent->getParent());
+
+  // Append the letter "C" to the sequence.
+  addLetterToHash(Hash, "C");
+
+  // Followed by the DWARF tag of the construct.
+  addULEB128ToHash(Hash, Parent->getTag());
+
+  // Then the name, taken from the DW_AT_name attribute.
+  StringRef Name = getDIEStringAttr(Parent, dwarf::DW_AT_name);
+  if (!Name.empty())
+    addStringToHash(Hash, Name);
+}
+
+/// This is based on the type signature computation given in section 7.27 of the
+/// DWARF4 standard. It is the md5 hash of a flattened description of the DIE.
+static void addDIEODRSignature(MD5 &Hash, CompileUnit *CU, DIE *Die) {
+
+  // Add the contexts to the hash.
+  DIE *Parent = Die->getParent();
+  if (Parent)
+    addParentContextToHash(Hash, Parent);
+
+  // Add the current DIE information.
+
+  // Add the DWARF tag of the DIE.
+  addULEB128ToHash(Hash, Die->getTag());
+
+  // Add the name of the type to the hash.
+  addStringToHash(Hash, getDIEStringAttr(Die, dwarf::DW_AT_name));
+
+  // Now get the result.
+  MD5::MD5Result Result;
+  Hash.final(Result);
+
+  // ... take the least significant 8 bytes and store those as the attribute.
+  uint64_t Signature;
+  memcpy(&Signature, &Result[8], 8);
+
+  // FIXME: This should be added onto the type unit, not the type, but this
+  // works as an intermediate stage.
+  CU->addUInt(Die, dwarf::DW_AT_GNU_odr_signature, dwarf::DW_FORM_data8,
+              Signature);
+}
+
+/// Return true if the current DIE is contained within an anonymous namespace.
+static bool isContainedInAnonNamespace(DIE *Die) {
+  DIE *Parent = Die->getParent();
+
+  while (Parent) {
+    if (Die->getTag() == dwarf::DW_TAG_namespace &&
+        getDIEStringAttr(Die, dwarf::DW_AT_name) == "")
+      return true;
+    Parent = Parent->getParent();
+  }
+
+  return false;
+}
+
 void DwarfDebug::finalizeModuleInfo() {
   // Collect info for variables that were optimized out.
   collectDeadVariables();
@@ -971,6 +1106,20 @@ void DwarfDebug::finalizeModuleInfo() {
     TheCU->constructContainingTypeDIEs();
   }
 
+  // For types that we'd like to move to type units or ODR check go ahead
+  // and either move the types out or add the ODR attribute now.
+  // FIXME: Do type splitting.
+  for (unsigned i = 0, e = TypeUnits.size(); i != e; ++i) {
+    MD5 Hash;
+    DIE *Die = TypeUnits[i];
+    // If we're in C++ and we want to generate the hash then go ahead and do
+    // that now.
+    if (GenerateODRHash &&
+        CUMap.begin()->second->getLanguage() == dwarf::DW_LANG_C_plus_plus &&
+        !isContainedInAnonNamespace(Die))
+      addDIEODRSignature(Hash, CUMap.begin()->second, Die);
+  }
+
    // Compute DIE offsets and sizes.
   InfoHolder.computeSizeAndOffsets();
   if (useSplitDwarf())
diff --git a/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.h b/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.h
index deb2e606899..e14f9b135b3 100644
--- a/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.h
+++ b/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.h
@@ -428,6 +428,9 @@ class DwarfDebug {
     ImportedEntityMap;
   ImportedEntityMap ScopesWithImportedEntities;
 
+  // Holder for types that are going to be extracted out into a type unit.
+  std::vector<DIE *> TypeUnits;
+
   // DWARF5 Experimental Options
   bool HasDwarfAccelTables;
   bool HasSplitDwarf;
@@ -651,6 +654,10 @@ public:
   /// \brief Process end of an instruction.
   void endInstruction(const MachineInstr *MI);
 
+  /// \brief Add a DIE to the set of types that we're going to pull into
+  /// type units.
+  void addTypeUnitType(DIE *Die) { TypeUnits.push_back(Die); }
+
   /// \brief Look up the source id with the given directory and source file
   /// names. If none currently exists, create a new id and insert it in the
   /// SourceIds map.