[dsymutil] Fix assertion: (Ref > InputDIE.getOffset()), function cloneDieReferenceAttribute

[JDevlieghere]

Summary

D125469 changed the assumptions regarding forward references. Before the patch, a reference to an uncloned DIE was always a forward reference. After the change, that assumption no longer holds. It was enforced by the assertion in DWARFLinker::DIECloner::cloneDieReferenceAttribute (DWARFLinker.cpp:937):

assert(Ref > InputDIE.getOffset());

This patch is relatively straightforward: it adds a field to the DIEInfo to remember the DIE is a forward or backward reference. We then treat backward references like a forward references by fixing them up after the fact, when all DIEs have been cloned.

We tripped this assertion for an internal project built with LTO. Unfortunately that means I'm not able to share a test case. I've spent a few hours trying to craft a test case that would hit this case but didn't succeed. Getting a backward reference is easy, but a backward reference to a DIE that hasn't been cloned yet is not something I managed to reproduce. I'd love to have a test case to avoid regressing this in the future, so please let me know if you have an idea on how to trigger this behavior from an artificial test case.

rdar://102148054

[JDevlieghere]

Remove unrelated changes

[friss]

llvm/include/llvm/DWARFLinker/DWARFLinkerCompileUnit.h

81–82

When I read the comment, I was confused as I thought the flag was used to differentiate between forward and backward references. But in fact it's just signaling a reference to a DIE that has not been emitted yet. Maybe tweak the comment.

llvm/lib/DWARFLinker/DWARFLinker.cpp

961–962

Should we change the name of this function now that it's not only about forward references.

[JDevlieghere]

Address @friss' feedback.

[avl]

llvm/include/llvm/DWARFLinker/DWARFLinkerCompileUnit.h

82

Probably name it UnclonedReference ? or RefShouldBePatched?(or something like that)

llvm/lib/DWARFLinker/DWARFLinkerCompileUnit.cpp

79

/// Keep track of a cross-cu reference from this unit

[JDevlieghere]

Address @avl's feedback

[avl]

LGTM

[avl]

I think we need to create a test case. I tried(still trying) to create one, but it seems this assertions should always be satisfied : "assert(Ref > InputDIE.getOffset());". That might be an error if referenced DIE is not cloned.

[avl]

@JDevlieghere Is this assertion happened in single thread mode only, or multi-thread mode only, or both?

[JDevlieghere]

In D138176#3937163, @avl wrote:

That might be an error if referenced DIE is not cloned.

@friss and I were starting to wonder the same thing. I was out last week because of Thanksgiving but I'll dig into this a bit more this week.

In D138176#3939686, @avl wrote:

@JDevlieghere Is this assertion happened in single thread mode only, or multi-thread mode only, or both?

This is happening in dsymutil which runs in "lockstep mode" where analyze and clone happen sequentially per CU (but we start analyzing the next CU while we're cloning the previous one). It definitely sounds like that could have something to do with it.

[JDevlieghere]

Last week I debugged this further. Here's what I believe is going on. Consider the following simplified example with two CUs and a type Foo.

0x01: DW_TAG_compile_unit

0x02: DW_TAG_class_type
        DW_AT_containing_type (0x11)
        DW_AT_name            ("Foo")

0x03: DW_TAG_pointer_type
        DW_AT_type            (0x02 "Foo") 

...

0x10: DW_TAG_compile_unit

0x11: DW_TAG_class_type
       DW_AT_containing_type (0x11)
       DW_AT_name            ("Foo")

...

Assume that in the first compile unit, we have a relocation that causes us to keep the pointer to foo.

During the analysis phase, when looking for DIEs to keep, we encounter the definition of Foo. Through an ODR attribute (in this case DW_AT_containing_type) we see the same definition of Foo in the second CU. We decide to keep the definition in CU2 (0x11) and mark the decl context as having a canonical ODR DIE. As a result, we don't keep the definition in CU1.

During the emission phase, we encounter the pointer to foo again (0x03). As part of cloning, we go over its attributes and encounter 0x02 through the DW_AT_type. The canonical DIE in CU2 hasn't been cloned yet, so the RefInfo.Clone is false and so is the DeclContext's canonical DIE offset. As a result, we trip off the assertion because the reference (0x2) is less than the input DIEs offset (0x3) and therefore should already have been emitted. Instead, we should note the (forward) reference and fix it up later, which is what this patch does.

In the patch I called it a backward reference, because the original DIE comes before the DIE being emitted now, but as shown here, it really is a forward reference, so maybe it's better to keep the original naming.

This reproduces for several internal projects. The smallest one is an LTO build with 1.8 million lines of IR. I've been trying to reduce it with llvm-reduce, delta and bugpoint since last Thursday, but all of these tools are struggling with DI metadata and the size of the file. I'll give it another day or so but I'm not holding my breath this will generate anything that can be used as a test.

With the reduction running in the background, I've been trying to hand-craft a test that exposes the behavior I've described here, but with every DIE it becomes exponentially harder to trick dsymutil's algorithm into traversing the DIEs in the order you want.

[JDevlieghere]

Revert to old naming

[avl]

In D138176#3995675, @JDevlieghere wrote:

Last week I debugged this further. Here's what I believe is going on. Consider the following simplified example with two CUs and a type Foo.

0x01: DW_TAG_compile_unit

0x02: DW_TAG_class_type
        DW_AT_containing_type (0x11)
        DW_AT_name            ("Foo")

0x03: DW_TAG_pointer_type
        DW_AT_type            (0x02 "Foo") 

...

0x10: DW_TAG_compile_unit

0x11: DW_TAG_class_type
       DW_AT_containing_type (0x11)
       DW_AT_name            ("Foo")

...

Assume that in the first compile unit, we have a relocation that causes us to keep the pointer to foo.

During the analysis phase, when looking for DIEs to keep, we encounter the definition of Foo. Through an ODR attribute (in this case DW_AT_containing_type) we see the same definition of Foo in the second CU. We decide to keep the definition in CU2 (0x11) and mark the decl context as having a canonical ODR DIE. As a result, we don't keep the definition in CU1.

During the emission phase, we encounter the pointer to foo again (0x03). As part of cloning, we go over its attributes and encounter 0x02 through the DW_AT_type. The canonical DIE in CU2 hasn't been cloned yet, so the RefInfo.Clone is false and so is the DeclContext's canonical DIE offset. As a result, we trip off the assertion because the reference (0x2) is less than the input DIEs offset (0x3) and therefore should already have been emitted. Instead, we should note the (forward) reference and fix it up later, which is what this patch does.

I tryed to create a test according to this description. But, in its current state it does not lead to the assertion. So the real case, is probable more complicated.
In this example the type from the first compile unit is always cloned.

odr-two-units-in-single-file10.test5 KBDownload

In the patch I called it a backward reference, because the original DIE comes before the DIE being emitted now, but as shown here, it really is a forward reference, so maybe it's better to keep the original naming.

This reproduces for several internal projects. The smallest one is an LTO build with 1.8 million lines of IR. I've been trying to reduce it with llvm-reduce, delta and bugpoint since last Thursday, but all of these tools are struggling with DI metadata and the size of the file. I'll give it another day or so but I'm not holding my breath this will generate anything that can be used as a test.

With the reduction running in the background, I've been trying to hand-craft a test that exposes the behavior I've described here, but with every DIE it becomes exponentially harder to trick dsymutil's algorithm into traversing the DIEs in the order you want.

Though I think it would be useful to finally have a test case for this situation, it looks OK to approve this patch. If there would be reference to the uncloned DIE then this assertion should catch it:

void CompileUnit::fixupForwardReferences() {
  for (const auto &Ref : ForwardDIEReferences) {
    DIE *RefDie;
    const CompileUnit *RefUnit;
    PatchLocation Attr;
    DeclContext *Ctxt;
    std::tie(RefDie, RefUnit, Ctxt, Attr) = Ref;
    if (Ctxt && Ctxt->hasCanonicalDIE()) {
      assert(Ctxt->getCanonicalDIEOffset() &&
             "Canonical die offset is not set");   <<<<<<<<<<<<<<<<
      Attr.set(Ctxt->getCanonicalDIEOffset());
    } else
      Attr.set(RefDie->getOffset() + RefUnit->getStartOffset());
  }
}

[avl]

LGTM

[JDevlieghere]

In D138176#3997559, @avl wrote:

In D138176#3995675, @JDevlieghere wrote:

Last week I debugged this further. Here's what I believe is going on. Consider the following simplified example with two CUs and a type Foo.

0x01: DW_TAG_compile_unit

0x02: DW_TAG_class_type
        DW_AT_containing_type (0x11)
        DW_AT_name            ("Foo")

0x03: DW_TAG_pointer_type
        DW_AT_type            (0x02 "Foo") 

...

0x10: DW_TAG_compile_unit

0x11: DW_TAG_class_type
       DW_AT_containing_type (0x11)
       DW_AT_name            ("Foo")

...

Assume that in the first compile unit, we have a relocation that causes us to keep the pointer to foo.

During the analysis phase, when looking for DIEs to keep, we encounter the definition of Foo. Through an ODR attribute (in this case DW_AT_containing_type) we see the same definition of Foo in the second CU. We decide to keep the definition in CU2 (0x11) and mark the decl context as having a canonical ODR DIE. As a result, we don't keep the definition in CU1.

During the emission phase, we encounter the pointer to foo again (0x03). As part of cloning, we go over its attributes and encounter 0x02 through the DW_AT_type. The canonical DIE in CU2 hasn't been cloned yet, so the RefInfo.Clone is false and so is the DeclContext's canonical DIE offset. As a result, we trip off the assertion because the reference (0x2) is less than the input DIEs offset (0x3) and therefore should already have been emitted. Instead, we should note the (forward) reference and fix it up later, which is what this patch does.

I tryed to create a test according to this description. But, in its current state it does not lead to the assertion. So the real case, is probable more complicated.
In this example the type from the first compile unit is always cloned.

odr-two-units-in-single-file10.test5 KBDownload

Yes, I tried as well and I wasn't able to trick the algorithm into keeping the the type from the second CU.

In the patch I called it a backward reference, because the original DIE comes before the DIE being emitted now, but as shown here, it really is a forward reference, so maybe it's better to keep the original naming.

This reproduces for several internal projects. The smallest one is an LTO build with 1.8 million lines of IR. I've been trying to reduce it with llvm-reduce, delta and bugpoint since last Thursday, but all of these tools are struggling with DI metadata and the size of the file. I'll give it another day or so but I'm not holding my breath this will generate anything that can be used as a test.

With the reduction running in the background, I've been trying to hand-craft a test that exposes the behavior I've described here, but with every DIE it becomes exponentially harder to trick dsymutil's algorithm into traversing the DIEs in the order you want.

Though I think it would be useful to finally have a test case for this situation, it looks OK to approve this patch. If there would be reference to the uncloned DIE then this assertion should catch it:

void CompileUnit::fixupForwardReferences() {
  for (const auto &Ref : ForwardDIEReferences) {
    DIE *RefDie;
    const CompileUnit *RefUnit;
    PatchLocation Attr;
    DeclContext *Ctxt;
    std::tie(RefDie, RefUnit, Ctxt, Attr) = Ref;
    if (Ctxt && Ctxt->hasCanonicalDIE()) {
      assert(Ctxt->getCanonicalDIEOffset() &&
             "Canonical die offset is not set");   <<<<<<<<<<<<<<<<
      Attr.set(Ctxt->getCanonicalDIEOffset());
    } else
      Attr.set(RefDie->getOffset() + RefUnit->getStartOffset());
  }
}

Yup, exactly.

[avl]

Looks like I have a test case for this problem:

odr-two-units-in-single-file11.test5 KBDownload

compile units cross reference each other in this test case:

CU1:
  0x10 type 1
  ref to 0x40
CU2:
  0x40 type 1
  ref to 0x10

[avl]

Since this patch extends number of cases when uncloned dies are created, it is worth to add following check:

void CompileUnit::fixupForwardReferences() {
  for (const auto &Ref : ForwardDIEReferences) {
    DIE *RefDie;
    const CompileUnit *RefUnit;
    PatchLocation Attr;
    DeclContext *Ctxt;
    std::tie(RefDie, RefUnit, Ctxt, Attr) = Ref;
    if (Ctxt && Ctxt->hasCanonicalDIE()) {
      assert(Ctxt->getCanonicalDIEOffset() &&
             "Canonical die offset is not set");
      Attr.set(Ctxt->getCanonicalDIEOffset());
    } else {
      assert(RefDie->getOffset() && "Referenced die offset is not set");    <<<<<<<<<<<<<<<<<<<<
      Attr.set(RefDie->getOffset() + RefUnit->getStartOffset());
    }
  }
}

[JDevlieghere]

In D138176#4001739, @avl wrote:

Looks like I have a test case for this problem:

That's awesome, thank you for spending time on that!

I'll add the assert you suggested to this patch. Do you want to commit the test yourself or can I include it in my commit (I don't want to take credit for your hard work, but also don't want to give you more work :-)

[avl]

In D138176#4002154, @JDevlieghere wrote:

I'll add the assert you suggested to this patch. Do you want to commit the test yourself or can I include it in my commit (I don't want to take credit for your hard work, but also don't want to give you more work :-)

thank you for asking, include it to your commit please.

llvm/include/llvm/DWARFLinker/DWARFLinkerCompileUnit.h

struct DIEInfo {
     /// Does DIE transitively refer an incomplete decl?
     bool Incomplete : 1;
 
     /// Is DIE in the clang module scope?
     bool InModuleScope : 1;
 
     /// Is ODR marking done?
     bool ODRMarkingDone : 1;
+
+    /// Is this a reference to a DIE that hasn't been cloned yet?
+    bool UnclonedReference : 1;
   };
 
   CompileUnit(DWARFUnit &OrigUnit, unsigned ID, bool CanUseODR,
               StringRef ClangModuleName)
       : OrigUnit(OrigUnit), ID(ID), ClangModuleName(ClangModuleName) {
     Info.resize(OrigUnit.getNumDIEs());
 
     auto CUDie = OrigUnit.getUnitDIE(false);
public:
   /// reconstructed accelerator tables.
   void markEverythingAsKept();
 
   /// Compute the end offset for this unit. Must be called after the CU's DIEs
   /// have been cloned.  \returns the next unit offset (which is also the
   /// current debug_info section size).
   uint64_t computeNextUnitOffset(uint16_t DwarfVersion);
 
-  /// Keep track of a forward reference to DIE \p Die in \p RefUnit by \p
-  /// Attr. The attribute should be fixed up later to point to the absolute
-  /// offset of \p Die in the debug_info section or to the canonical offset of
-  /// \p Ctxt if it is non-null.
-  void noteForwardReference(DIE *Die, const CompileUnit *RefUnit,
-                            DeclContext *Ctxt, PatchLocation Attr);
+  /// Keep track of a forward or backward reference to DIE \p Die in \p RefUnit
+  /// by \p Attr. The attribute should be fixed up later to point to the
+  /// absolute offset of \p Die in the debug_info section or to the canonical
+  /// offset of \p Ctxt if it is non-null.
+  void noteReference(DIE *Die, const CompileUnit *RefUnit, DeclContext *Ctxt,
+                     PatchLocation Attr);
 
-  /// Apply all fixups recorded by noteForwardReference().
-  void fixupForwardReferences();
+  /// Apply all fixups recorded by noteReference().
+  void fixupReferences();
 
   /// Add the low_pc of a label that is relocated by applying
   /// offset \p PCOffset.
   void addLabelLowPc(uint64_t LabelLowPc, int64_t PcOffset);
 
   /// Add a function range [\p LowPC, \p HighPC) that is relocated by applying
   /// offset \p PCOffset.
   void addFunctionRange(uint64_t LowPC, uint64_t HighPC, int64_t PCOffset);
private:
   /// A list of attributes to fixup with the absolute offset of
   /// a DIE in the debug_info section.
   ///
   /// The offsets for the attributes in this array couldn't be set while
   /// cloning because for cross-cu forward references the target DIE's offset
   /// isn't known you emit the reference attribute.
   std::vector<
       std::tuple<DIE *, const CompileUnit *, DeclContext *, PatchLocation>>
-      ForwardDIEReferences;
+      DIEReferences;
 
   /// The ranges in that map are the PC ranges for functions in this unit,
   /// associated with the PC offset to apply to the addresses to get
   /// the linked address.
   RangesTy Ranges;
 
   /// The DW_AT_low_pc of each DW_TAG_label.
   SmallDenseMap<uint64_t, uint64_t, 1> Labels;

llvm/lib/DWARFLinker/DWARFLinker.cpp

assert(RefInfo.Ctxt->hasCanonicalDIE() &&
            "Offset to canonical die is set, but context is not marked");
     DIEInteger Attr(RefInfo.Ctxt->getCanonicalDIEOffset());
     Die.addValue(DIEAlloc, dwarf::Attribute(AttrSpec.Attr),
                  dwarf::DW_FORM_ref_addr, Attr);
     return U.getRefAddrByteSize();
   }
 
   if (!RefInfo.Clone) {
-    assert(Ref > InputDIE.getOffset());
     // We haven't cloned this DIE yet. Just create an empty one and
     // store it. It'll get really cloned when we process it.
+    RefInfo.UnclonedReference = true;
     RefInfo.Clone = DIE::get(DIEAlloc, dwarf::Tag(RefDie.getTag()));
   }
   NewRefDie = RefInfo.Clone;
 
   if (AttrSpec.Form == dwarf::DW_FORM_ref_addr ||
       (Unit.hasODR() && isODRAttribute(AttrSpec.Attr))) {
     // We cannot currently rely on a DIEEntry to emit ref_addr
     // references, because the implementation calls back to DwarfDebug
     // to find the unit offset. (We don't have a DwarfDebug)
     // FIXME: we should be able to design DIEEntry reliance on
     // DwarfDebug away.
     uint64_t Attr;
-    if (Ref < InputDIE.getOffset()) {
-      // We must have already cloned that DIE.
+    if (Ref < InputDIE.getOffset() && !RefInfo.UnclonedReference) {
+      // We have already cloned that DIE.
       uint32_t NewRefOffset =
           RefUnit->getStartOffset() + NewRefDie->getOffset();
       Attr = NewRefOffset;
       Die.addValue(DIEAlloc, dwarf::Attribute(AttrSpec.Attr),
                    dwarf::DW_FORM_ref_addr, DIEInteger(Attr));
     } else {
-      // A forward reference. Note and fixup later.
+      // A forward or backward reference. Note and fixup later.
       Attr = 0xBADDEF;
-      Unit.noteForwardReference(
-          NewRefDie, RefUnit, RefInfo.Ctxt,
+      Unit.noteReference(NewRefDie, RefUnit, RefInfo.Ctxt,
                          Die.addValue(DIEAlloc, dwarf::Attribute(AttrSpec.Attr),
-                       dwarf::DW_FORM_ref_addr, DIEInteger(Attr)));
+                                      dwarf::DW_FORM_ref_addr,
+                                      DIEInteger(Attr)));
     }
     return U.getRefAddrByteSize();
   }
 
   Die.addValue(DIEAlloc, dwarf::Attribute(AttrSpec.Attr),
                dwarf::Form(AttrSpec.Form), DIEEntry(*NewRefDie));
 
   return AttrSize;
uint64_t DWARFLinker::DIECloner::cloneAllCompileUnits(
 
   if (!Linker.Options.NoOutput) {
     assert(Emitter);
     // Emit all the compile unit's debug information.
     for (auto &CurrentUnit : CompileUnits) {
       if (LLVM_LIKELY(!Linker.Options.Update))
         Linker.generateUnitRanges(*CurrentUnit);
 
-      CurrentUnit->fixupForwardReferences();
+      CurrentUnit->fixupReferences();
 
       if (!CurrentUnit->getOutputUnitDIE())
         continue;
 
       unsigned DwarfVersion = CurrentUnit->getOrigUnit().getVersion();
 
       assert(Emitter->getDebugInfoSectionSize() ==
              CurrentUnit->getStartOffset());

llvm/lib/DWARFLinker/DWARFLinkerCompileUnit.cpp

uint64_t CompileUnit::computeNextUnitOffset(uint16_t DwarfVersion) {
   NextUnitOffset = StartOffset;
   if (NewUnit) {
     NextUnitOffset += (DwarfVersion >= 5) ? 12 : 11; // Header size
     NextUnitOffset += NewUnit->getUnitDie().getSize();
   }
   return NextUnitOffset;
 }
 
-/// Keep track of a forward cross-cu reference from this unit
+/// Keep track of a cross-cu reference from this unit
 /// to \p Die that lives in \p RefUnit.
-void CompileUnit::noteForwardReference(DIE *Die, const CompileUnit *RefUnit,
-                                       DeclContext *Ctxt, PatchLocation Attr) {
-  ForwardDIEReferences.emplace_back(Die, RefUnit, Ctxt, Attr);
+void CompileUnit::noteReference(DIE *Die, const CompileUnit *RefUnit,
+  DIEReferences.emplace_back(Die, RefUnit, Ctxt, Attr);
 }
 
-void CompileUnit::fixupForwardReferences() {
-  for (const auto &Ref : ForwardDIEReferences) {
+void CompileUnit::fixupReferences() {
+  for (const auto &Ref : DIEReferences) {
     DIE *RefDie;
     const CompileUnit *RefUnit;
     PatchLocation Attr;
     DeclContext *Ctxt;
     std::tie(RefDie, RefUnit, Ctxt, Attr) = Ref;
     if (Ctxt && Ctxt->hasCanonicalDIE()) {
       assert(Ctxt->getCanonicalDIEOffset() &&
              "Canonical die offset is not set");