[dsymutil] Don't mark forward declarations as canonical.

[JDevlieghere]

Summary

This patch completes the work done by Frederic Riss (@friss) to
addresses dsymutil incorrectly considering forward declaration as
canonical during uniquing. This resulted in references to the forward
declaration even after the definition was encountered.

In addition to the test provided by Alexander Shaposhnikov (@alexshap)
in D29609, I added another test to cover several scenarios that were
mentioned in his conversation with Fred. We now also check that uniquing
still occurs after the definition was encountered.

For more context please refer to D29609

[aprantl]

mostly nitpicking :-)

test/tools/dsymutil/X86/odr-fwd-declaration.cpp

113

broken

114

referenced

tools/dsymutil/DwarfLinker.cpp

195

is there a more accurate description that "point to"? I.e., does this include a struct that has a fwddecl as a member?

1202

document the return value?

2210

extra newline? not sure if this was intentional

2261

maybe is complete?

2286

what does the return value mean?

[alexander-shaposhnikov]

@JDevlieghere, @friss, @aprantl - many thanks for working on this and getting the fix to the upstream!

[JDevlieghere]

Thanks for the review @aprantl! About the comment for the Incomplete member: can this strictly occur for members or has this a broader scope?

[friss]

A few nits, but this mostly LGTM

test/tools/dsymutil/X86/odr-fwd-declaration2.cpp

27

Add a CHECK-NOT: {{DW_TAG|NULL}} before this

86

Add the same CHECK-NOT here

99

You are reusing REF1. I suppose this those the right thing (overwrites it), but please use a different name.

135–136

As the bellow doesn't really test bPTr, bRef and bPtrToField, I would rephrase this as:
"Finally we confirm that uniquing isn't broken by checking that further references to 'struct A' point to its now complete definition.

tools/dsymutil/DwarfLinker.cpp

195

If it fits, "Does this DIE transitively refer to an incomplete decl?" would be better I think

[JDevlieghere]

Thanks @friss, I've updated the diff with your feedback.

[friss]

LGTM, thanks!

test/tools/dsymutil/X86/odr-fwd-declaration.cpp

+/* Compile with:
+   for FILE in `seq 3`; do
+     clang -g -c  X86/odr-fwd-declaration.cpp -DFILE$FILE -o Inputs/odr-fwd-declaration/$FILE.o
+   done
+ */
+
+// RUN: llvm-dsymutil -f -oso-prepend-path=%p/../Inputs/odr-fwd-declaration -y %p/dummy-debug-map.map -o - | llvm-dwarfdump -debug-dump=info - | FileCheck %s
+
+#ifdef FILE1
+# 1 "Header.h" 1
+typedef struct S *Sptr;
+typedef Sptr *Sptrptr;
+# 3 "Source1.cpp" 2
+void foo() {
+  Sptrptr ptr1 = 0;
+}
+
+// First we confirm that the typedefs reference the forward declaration of the
+// struct S.
+//
+// CHECK: TAG_variable
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_name{{.*}} "ptr1"
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[TYPEDEF1:[a-f0-9]*]]
+//
+// CHECK: [[TYPEDEF1]]:{{.*}}TAG_typedef
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[PTR1:[a-f0-9]*]]
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_name{{.*}} "Sptrptr"
+//
+// CHECK: [[PTR1]]:{{.*}}TAG_pointer_type
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[TYPEDEF2:[a-f0-9]*]]
+//
+// CHECK: [[TYPEDEF2]]:{{.*}}TAG_typedef
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[PTR2:[a-f0-9]*]]
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_name{{.*}} "Sptr"
+//
+// CHECK: [[PTR2]]:{{.*}}TAG_pointer_type
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[FWDSTRUCT:[a-f0-9]*]]
+//
+// CHECK: [[FWDSTRUCT]]:{{.*}}TAG_structure_type
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_name{{.*}} "S"
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_declaration
+// CHECK-NOT AT_byte_size
+
+#elif defined(FILE2)
+# 1 "Header.h" 1
+typedef struct S *Sptr;
+typedef Sptr *Sptrptr;
+# 3 "Source2.cpp" 2
+struct S {
+  int field;
+};
+void bar() {
+  Sptrptr ptr2 = 0;
+}
+
+// Next we confirm that the typedefs reference the definition rather than the
+// previous declaration of S.
+//
+// CHECK: TAG_variable
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_name{{.*}} "ptr2"
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[TYPEDEF3:[a-f0-9]*]]
+//
+// CHECK: [[TYPEDEF3]]:{{.*}}TAG_typedef
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[PTR3:[a-f0-9]*]]
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_name{{.*}} "Sptrptr"
+//
+// CHECK: [[PTR3]]:{{.*}}TAG_pointer_type
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[TYPEDEF4:[a-f0-9]*]]
+//
+// CHECK: [[TYPEDEF4]]:{{.*}}TAG_typedef
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[PTR4:[a-f0-9]*]]
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_name{{.*}} "Sptr"
+//
+// CHECK: [[PTR4]]:{{.*}}TAG_pointer_type
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[STRUCT:[a-f0-9]*]]
+//
+// CHECK: [[STRUCT]]:{{.*}}TAG_structure_type
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_name{{.*}} "S"
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK-NOT: AT_declaration
+// CHECK: AT_byte_size
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: TAG_member
+
+#elif defined(FILE3)
+# 1 "Header.h" 1
+typedef struct S *Sptr;
+typedef Sptr *Sptrptr;
+# 3 "Source1.cpp" 2
+void foo() {
+  Sptrptr ptr1 = 0;
+}
+
+// Finally we confirm that uniquing is not borken and the same typedef is
+// referneced by ptr1.
+//
+// CHECK: TAG_variable
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_name{{.*}} "ptr1"
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[TYPEDEF3]]
+// CHECK-NOT: TAG_typedef
+// CHECK-NOT: TAG_pointer
+// CHECK-NOT: TAG_structure_type
+
+#else
+#error "You must define which file you generate"
+#endif

test/tools/dsymutil/X86/odr-fwd-declaration2.cpp

+/* Compile with:
+   for FILE in `seq 3`; do
+     clang -g -c  X86/odr-fwd-declaration2.cpp -DFILE$FILE -o Inputs/odr-fwd-declaration2/$FILE.o
+   done
+ */
+
+// RUN: llvm-dsymutil -f -oso-prepend-path=%p/../Inputs/odr-fwd-declaration2 -y %p/dummy-debug-map.map -o - | llvm-dwarfdump -debug-dump=info - | FileCheck %s
+
+#ifdef FILE1
+# 1 "Header.h" 1
+struct A {
+  struct B;
+  B *bPtr;
+  B &bRef;
+  int B::*bPtrToField;
+};
+# 3 "Source1.cpp" 2
+void foo() {
+  A *ptr1 = 0;
+}
+
+// First we confirm that bPtr, bRef and bPtrToField reference the forward
+// declaration of the struct B.
+//
+// CHECK: DW_TAG_member
+// CHECK: AT_name{{.*}} "bPtr"
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[PTR1:[a-f0-9]*]]
+//
+// CHECK: [[STRUCT1:[a-f0-9]*]]:{{.*}}TAG_structure_type
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_name{{.*}} "B"
+// CHECK-NOT: AT_byte_size
+// CHECK: DW_AT_declaration
+//
+// CHECK: DW_TAG_member
+// CHECK: AT_name{{.*}} "bRef"
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[REF1:[a-f0-9]*]]
+//
+// CHECK: TAG_member
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_name{{.*}} "bPtrToField"
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[PTRTOMEMBER1:[a-f0-9]*]]
+//
+// CHECK: [[PTR1]]:{{.*}}TAG_pointer_type
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[STRUCT1]]
+//
+// CHECK: [[REF1]]:{{.*}}TAG_reference_type
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[STRUCT1]]
+//
+// CHECK: [[PTRTOMEMBER1]]:{{.*}}TAG_ptr_to_member_type
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_containing_type{{.*}}0x{{0*}}[[STRUCT1]]
+
+#elif defined(FILE2)
+# 1 "Header.h" 1
+struct A {
+  struct B;
+  B *bPtr;
+  B &bRef;
+  int B::*bPtrToField;
+};
+# 3 "Source2.cpp" 2
+struct A::B {
+  int x;
+};
+void bar() {
+  A *ptr2 = 0;
+}
+
+// Next we confirm that bPtr, bRef and bPtrToField reference the definition of
+// B, rather than its declaration.
+//
+// CHECK: [[STRUCTA:[a-f0-9]*]]:{{.*}}TAG_structure_type
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_name{{.*}} "A"
+// CHECK-NOT: AT_byte_size
+// CHECK: DW_AT_byte_size
+//
+// CHECK: DW_TAG_member
+// CHECK: AT_name{{.*}} "bPtr"
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[PTR2:[a-f0-9]*]]
+//
+// CHECK: [[STRUCT2:[a-f0-9]*]]:{{.*}}TAG_structure_type
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_name{{.*}} "B"
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: DW_AT_byte_size
+//
+// CHECK: DW_TAG_member
+// CHECK: AT_name{{.*}} "bRef"
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[REF1:[a-f0-9]*]]
+//
+// CHECK: TAG_member
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_name{{.*}} "bPtrToField"
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[PTRTOMEMBER2:[a-f0-9]*]]
+//
+// CHECK: [[PTR2]]:{{.*}}TAG_pointer_type
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[STRUCT2]]
+//
+// CHECK: [[REF1]]:{{.*}}TAG_reference_type
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[STRUCT2]]
+//
+// CHECK: [[PTRTOMEMBER2]]:{{.*}}TAG_ptr_to_member_type
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_containing_type{{.*}}0x{{0*}}[[STRUCT2:[a-f0-9]*]]
+
+#elif defined(FILE3)
+# 1 "Header.h" 1
+struct A {
+  struct B;
+  B *bPtr;
+  B &bRef;
+  int B::*bPtrToField;
+};
+# 3 "Source2.cpp" 2
+struct A::B {
+  int x;
+};
+void bar() {
+  A *ptr2 = 0;
+}
+
+// Finally we confirm that uniquing is not borken and bPtr, bRef and
+// bPtrToField still reference the same definition of B.
+//
+// CHECK: TAG_variable
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_name{{.*}} "ptr2"
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[PTR3:[a-f0-9]*]]
+//
+// CHECK: [[PTR3]]:{{.*}}TAG_pointer_type
+// CHECK-NOT: {{DW_TAG|NULL}}
+// CHECK: AT_type{{.*}}0x{{0*}}[[STRUCTA]]
+
+#else
+#error "You must define which file you generate"
+#endif

tools/dsymutil/DwarfLinker.cpp

 };
 
 /// Stores all information relating to a compile unit, be it in its original
 /// instance in the object file to its brand new cloned and linked DIE tree.
 class CompileUnit {
 public:
   /// Information gathered about a DIE in the object file.
   struct DIEInfo {
-    int64_t AddrAdjust; ///< Address offset to apply to the described entity.
-    DeclContext *Ctxt;  ///< ODR Declaration context.
-    DIE *Clone;         ///< Cloned version of that DIE.
-    uint32_t ParentIdx; ///< The index of this DIE's parent.
-    bool Keep : 1;      ///< Is the DIE part of the linked output?
-    bool InDebugMap : 1;///< Was this DIE's entity found in the map?
-    bool Prune : 1;     ///< Is this a pure forward declaration we can strip?
+    int64_t AddrAdjust;  ///< Address offset to apply to the described entity.
+    DeclContext *Ctxt;   ///< ODR Declaration context.
+    DIE *Clone;          ///< Cloned version of that DIE.
+    uint32_t ParentIdx;  ///< The index of this DIE's parent.
+    bool Keep : 1;       ///< Is the DIE part of the linked output?
+    bool InDebugMap : 1; ///< Was this DIE's entity found in the map?
+    bool Prune : 1;      ///< Is this a pure forward declaration we can strip?
+    bool Incomplete : 1; ///< Does this DIE point to an forward decl?
   };
 
   CompileUnit(DWARFUnit &OrigUnit, unsigned ID, bool CanUseODR,
               StringRef ClangModuleName)
       : OrigUnit(OrigUnit), ID(ID), LowPc(UINT64_MAX), HighPc(0), RangeAlloc(),
         Ranges(RangeAlloc), ClangModuleName(ClangModuleName) {
     Info.resize(OrigUnit.getNumDIEs());
 
bool applyValidRelocs(MutableArrayRef<char> Data, uint32_t BaseOffset,
                           bool isLittleEndian);
   };
 
   /// \defgroup FindRootDIEs Find DIEs corresponding to debug map entries.
   ///
   /// @{
   /// Recursively walk the \p DIE tree and look for DIEs to
   /// keep. Store that information in \p CU's DIEInfo.
-  void lookForDIEsToKeep(RelocationManager &RelocMgr,
-                         const DWARFDie &DIE,
+  bool lookForDIEsToKeep(RelocationManager &RelocMgr, const DWARFDie &DIE,
                          const DebugMapObject &DMO, CompileUnit &CU,
                          unsigned Flags);
 
   /// If this compile unit is really a skeleton CU that points to a
   /// clang module, register it in ClangModules and return true.
   ///
   /// A skeleton CU is a CU without children, a DW_AT_gnu_dwo_name
   /// pointing to the module, and a DW_AT_gnu_dwo_id with the module

 void DwarfLinker::keepDIEAndDependencies(RelocationManager &RelocMgr,
                                           const DWARFDie &Die,
                                           CompileUnit::DIEInfo &MyInfo,
                                           const DebugMapObject &DMO,
                                           CompileUnit &CU, bool UseODR) {
   DWARFUnit &Unit = CU.getOrigUnit();
   MyInfo.Keep = true;
 
+  // We're looking for incomplete types.
+  MyInfo.Incomplete = Die.getTag() != dwarf::DW_TAG_subprogram &&
+                      Die.getTag() != dwarf::DW_TAG_member &&
+                      dwarf::toUnsigned(Die.find(dwarf::DW_AT_declaration), 0);
+
   // First mark all the parent chain as kept.
   unsigned AncestorIdx = MyInfo.ParentIdx;
   while (!CU.getInfo(AncestorIdx).Keep) {
     unsigned ODRFlag = UseODR ? TF_ODR : 0;
     lookForDIEsToKeep(RelocMgr, Unit.getDIEAtIndex(AncestorIdx), DMO, CU,
                       TF_ParentWalk | TF_Keep | TF_DependencyWalk | ODRFlag);
+
     AncestorIdx = CU.getInfo(AncestorIdx).ParentIdx;
   }
 
   // Then we need to mark all the DIEs referenced by this DIE's
   // attributes as kept.
   DWARFDataExtractor Data = Unit.getDebugInfoExtractor();
   const auto *Abbrev = Die.getAbbreviationDeclarationPtr();
   uint32_t Offset = Die.getOffset() + getULEB128Size(Abbrev->getCode());
if (auto RefDie =
       // Keep a module forward declaration if there is no definition.
       if (!(isODRAttribute(AttrSpec.Attr) && Info.Ctxt &&
             Info.Ctxt->getCanonicalDIEOffset()))
         Info.Prune = false;
 
       unsigned ODRFlag = UseODR ? TF_ODR : 0;
       lookForDIEsToKeep(RelocMgr, RefDie, DMO, *ReferencedCU,
                         TF_Keep | TF_DependencyWalk | ODRFlag);
+
+      // If the current DIE is not incomplete, but it references an incomplete
+      // one we propagate the incompleteness.
+      if (Info.Incomplete && !MyInfo.Incomplete &&
+          (Die.getTag() == dwarf::DW_TAG_typedef ||
+           Die.getTag() == dwarf::DW_TAG_member ||
+           Die.getTag() == dwarf::DW_TAG_reference_type ||
+           Die.getTag() == dwarf::DW_TAG_ptr_to_member_type ||
+           Die.getTag() == dwarf::DW_TAG_pointer_type))
+        MyInfo.Incomplete = true;
     }
   }
 }
 
 /// Recursively walk the \p DIE tree and look for DIEs to
 /// keep. Store that information in \p CU's DIEInfo.
 ///
 /// This function is the entry point of the DIE selection
 /// algorithm. It is expected to walk the DIE tree in file order and
 /// (though the mediation of its helper) call hasValidRelocation() on
 /// each DIE that might be a 'root DIE' (See DwarfLinker class
 /// comment).
 /// While walking the dependencies of root DIEs, this function is
 /// also called, but during these dependency walks the file order is
 /// not respected. The TF_DependencyWalk flag tells us which kind of
 /// traversal we are currently doing.
-void DwarfLinker::lookForDIEsToKeep(RelocationManager &RelocMgr,
+bool DwarfLinker::lookForDIEsToKeep(RelocationManager &RelocMgr,
                                     const DWARFDie &Die,
                                     const DebugMapObject &DMO, CompileUnit &CU,
                                     unsigned Flags) {
   unsigned Idx = CU.getOrigUnit().getDIEIndex(Die);
   CompileUnit::DIEInfo &MyInfo = CU.getInfo(Idx);
   bool AlreadyKept = MyInfo.Keep;
   if (MyInfo.Prune)
-    return;
+    return true;
 
   // If the Keep flag is set, we are marking a required DIE's
   // dependencies. If our target is already marked as kept, we're all
   // set.
   if ((Flags & TF_DependencyWalk) && AlreadyKept)
-    return;
+    return MyInfo.Incomplete;
 
   // We must not call shouldKeepDIE while called from keepDIEAndDependencies,
   // because it would screw up the relocation finding logic.
   if (!(Flags & TF_DependencyWalk))
     Flags = shouldKeepDIE(RelocMgr, Die, CU, MyInfo, Flags);
 
   // If it is a newly kept DIE mark it as well as all its dependencies as kept.
   if (!AlreadyKept && (Flags & TF_Keep)) {
     bool UseOdr = (Flags & TF_DependencyWalk) ? (Flags & TF_ODR) : CU.hasODR();
     keepDIEAndDependencies(RelocMgr, Die, MyInfo, DMO, CU, UseOdr);
   }
   // The TF_ParentWalk flag tells us that we are currently walking up
   // the parent chain of a required DIE, and we don't want to mark all
   // the children of the parents as kept (consider for example a
   // DW_TAG_namespace node in the parent chain). There are however a
   // set of DIE types for which we want to ignore that directive and still
   // walk their children.
   if (dieNeedsChildrenToBeMeaningful(Die.getTag()))
     Flags &= ~TF_ParentWalk;
 
   if (!Die.hasChildren() || (Flags & TF_ParentWalk))
-    return;
+    return MyInfo.Incomplete;
 
-  for (auto Child: Die.children())
-    lookForDIEsToKeep(RelocMgr, Child, DMO, CU, Flags);
+  bool Incomplete = false;
+  for (auto Child : Die.children()) {
+    Incomplete |= lookForDIEsToKeep(RelocMgr, Child, DMO, CU, Flags);
+
+    // If any of the members are incomplete we propagate the incompleteness.
+    if (!MyInfo.Incomplete && Incomplete &&
+        (Die.getTag() == dwarf::DW_TAG_structure_type ||
+         Die.getTag() == dwarf::DW_TAG_class_type))
+      MyInfo.Incomplete = true;
+  }
+  return MyInfo.Incomplete;
 }
 
 /// Assign an abbreviation numer to \p Abbrev.
 ///
 /// Our DIEs get freed after every DebugMapObject has been processed,
 /// thus the FoldingSet we use to unique DIEAbbrevs cannot refer to
 /// the instances hold by the DIEs. When we encounter an abbreviation
 /// that we don't know, we create a permanent copy of it.
if (!Die) {
     // (see cloneDieReferenceAttribute()).
     if (!Info.Clone)
       Info.Clone = DIE::get(DIEAlloc, dwarf::Tag(InputDIE.getTag()));
     Die = Info.Clone;
   }
 
   assert(Die->getTag() == InputDIE.getTag());
   Die->setOffset(OutOffset);
-  if ((Unit.hasODR() || Unit.isClangModule()) &&
+  if ((Unit.hasODR() || Unit.isClangModule()) && !Info.Incomplete &&
       Die->getTag() != dwarf::DW_TAG_namespace && Info.Ctxt &&
       Info.Ctxt != Unit.getInfo(Info.ParentIdx).Ctxt &&
       !Info.Ctxt->getCanonicalDIEOffset()) {
     // We are about to emit a DIE that is the root of its own valid
     // DeclContext tree. Make the current offset the canonical offset
     // for this context.
     Info.Ctxt->setCanonicalDIEOffset(OutOffset + Unit.getStartOffset());
   }