[DWARF] Fix bad comparator in sortGlobalExprs.

[efriedma]

Summary

The comparator passed to std::sort must provide a strict weak ordering; otherwise, the behavior is undefined.

Fixes an assertion failure generating debug info for globals optimized by GlobalOpt. I have a testcase, but not sure how to reduce it, so not included here.

(I think this issue was exposed by r312318.)

[aprantl]

Thanks! Since for the testcase only global variables are interesting, you should be able to strip out everything from the IR that is not a global variable and not reachable via a !DIGlobalVariable metadata node. You can probably just run delta on the input (especially if you insert extra newlines after each element in a DIArray (!{!1, !2}).

lib/CodeGen/AsmPrinter/DwarfDebug.cpp

514 ↗

(On Diff #118725)

Does return !A.Expr achieve the same thing and is easier to read?

[efriedma]

See also https://bugs.llvm.org//show_bug.cgi?id=34921 .

you should be able to strip out everything from the IR that is not a global variable and not reachable via a !DIGlobalVariable metadata node

Okay. Actually, I probably also need to dump out the IR sometime after GlobalMerge runs (for some reason, the crash doesn't trigger otherwise), but I'll figure something out.

lib/CodeGen/AsmPrinter/DwarfDebug.cpp

514 ↗

(On Diff #118725)

Suppose A.Expr and B.Expr are null. Then the comparator should return false, but !A.Expr is true.

[efriedma]

The obvious ways to reduce the testcase aren't working for me, and I don't really have a day to sink into it now. If you really need it, it'll probably take me a couple weeks to find the time. (The construct that's triggering it is something like https://bugs.llvm.org//show_bug.cgi?id=34921, but there's some funny interaction GlobalMerge and the exact order of the input which means simple transformations make the problem disappear.)

[bjope]

Eli, I think this looks good.

As far as I know this method is focusing on sorting (and removing duplicates) for the fragmented expressions, so we just need to get all expressions without fragment info (including the null exprs) out of the way to let std:unique do its thing. We aren't guaranteed to remove all duplicates for the expressions without fragment info anyway (due to only creating a strict weak ordering for the expressions with fragment info before std::unique).
So in our out-of-tree target workaround we currently make no difference between the null exprs and non-fragmented expressions, but your solution should work as well.

I also think that creating a test case might be troublesome. Mikael Holmén had some reproducer for this, but I doubt that it still works.
Maybe it can be tested by creating some unit test, but I guess that would be "little bang for the buck".

lib/CodeGen/AsmPrinter/DwarfDebug.cpp

521 ↗

(On Diff #118725)

We should probably highlight here (or in the function header) that the uniqueness only is "guaranteed" for the expressions containing fragment offsets.

Afaik, std::unique is only removing consecutive elements that are equal. And the expressions without fragment info are not really sorted (they all end up before the fragmented expressions, but the non-fragmented expressions are not ordered relative to each other).
If we really want to remove all duplicates, then I think we need to use a more complex algorithm for removing duplicates instead of using std::unique.

[uabelho]

In D38830#895692, @bjope wrote:

I also think that creating a test case might be troublesome. Mikael Holmén had some reproducer for this, but I doubt that it still works.

We have this:

; RUN: llc -o /dev/null %s

; Don't crash. It would of course be nice to also check that the produced
; Dwarf info is not rubbish.

@f1.a.0 = external unnamed_addr global i16, align 1, !dbg !0
@f1.a.1 = external unnamed_addr global i16, align 1, !dbg !30
@f1.a.2 = external unnamed_addr global i16, align 1, !dbg !31
@f1.a.3 = external unnamed_addr global i16, align 1, !dbg !32
@f1.a.4 = external unnamed_addr global i1, align 1, !dbg !33
@f1.a.5 = external unnamed_addr global i16, align 1, !dbg !34
@f1.a.6 = external unnamed_addr global i16, align 1, !dbg !35
@f1.a.7 = external unnamed_addr global i16, align 1, !dbg !36
@f1.a.8 = external unnamed_addr global i16, align 1, !dbg !37
@f1.a.9 = external unnamed_addr global i16, align 1, !dbg !38
@f1.a.10 = external unnamed_addr global i16, align 1, !dbg !39
@f1.a.11 = external unnamed_addr global i16, align 1, !dbg !40
@f1.a.12 = external unnamed_addr global i16, align 1, !dbg !41
@f1.a.13 = external unnamed_addr global i16, align 1, !dbg !42
@f1.a.14 = external unnamed_addr global i16, align 1, !dbg !43
@f1.a.15 = external unnamed_addr global i1, align 1, !dbg !49
@f1.a.16 = external unnamed_addr global i16, align 1, !dbg !44

!llvm.dbg.cu = !{!6}
!llvm.module.flags = !{!45, !46, !47}
!llvm.ident = !{!48}

!0 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression(DW_OP_LLVM_fragment, 0, 16))
!1 = distinct !DIGlobalVariable(name: "a", scope: !2, file: !3, line: 26, type: !10, isLocal: true, isDefinition: true)
!2 = distinct !DISubprogram(name: "f1", scope: !3, file: !3, line: 24, type: !4, isLocal: false, isDefinition: true, scopeLine: 25, flags: DIFlagPrototyped, isOptimized: true, unit: !6, variables: !7)
!3 = !DIFile(filename: "foo.c", directory: "/bar")
!4 = !DISubroutineType(types: !5)
!5 = !{null}
!6 = distinct !DICompileUnit(language: DW_LANG_C99, file: !3, producer: "my compiler", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !7, globals: !8)
!7 = !{}
!8 = !{!9}
!9 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression())
!10 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "s1", file: !3, line: 1, size: 272, elements: !11)
!11 = !{!12, !14, !15, !16, !17, !18, !19, !20, !21, !22, !23, !24, !25, !26, !27, !28, !29}
!12 = !DIDerivedType(tag: DW_TAG_member, name: "i01", scope: !10, file: !3, line: 4, baseType: !13, size: 8, offset: 6, flags: DIFlagBitField, extraData: i64 0)
!13 = !DIBasicType(name: "int", size: 16, encoding: DW_ATE_signed)
!14 = !DIDerivedType(tag: DW_TAG_member, name: "i02", scope: !10, file: !3, line: 5, baseType: !13, size: 8, offset: 16, flags: DIFlagBitField, extraData: i64 16)
!15 = !DIDerivedType(tag: DW_TAG_member, name: "i03", scope: !10, file: !3, line: 6, baseType: !13, size: 15, offset: 32, flags: DIFlagBitField, extraData: i64 32)
!16 = !DIDerivedType(tag: DW_TAG_member, name: "i04", scope: !10, file: !3, line: 7, baseType: !13, size: 4, offset: 48, flags: DIFlagBitField, extraData: i64 48)
!17 = !DIDerivedType(tag: DW_TAG_member, name: "i05", scope: !10, file: !3, line: 8, baseType: !13, size: 16, offset: 64)
!18 = !DIDerivedType(tag: DW_TAG_member, name: "i06", scope: !10, file: !3, line: 9, baseType: !13, size: 13, offset: 80, flags: DIFlagBitField, extraData: i64 80)
!19 = !DIDerivedType(tag: DW_TAG_member, name: "i07", scope: !10, file: !3, line: 10, baseType: !13, size: 4, offset: 96, flags: DIFlagBitField, extraData: i64 96)
!20 = !DIDerivedType(tag: DW_TAG_member, name: "i08", scope: !10, file: !3, line: 11, baseType: !13, size: 13, offset: 112, flags: DIFlagBitField, extraData: i64 112)
!21 = !DIDerivedType(tag: DW_TAG_member, name: "i09", scope: !10, file: !3, line: 12, baseType: !13, size: 10, offset: 128, flags: DIFlagBitField, extraData: i64 128)
!22 = !DIDerivedType(tag: DW_TAG_member, name: "i10", scope: !10, file: !3, line: 13, baseType: !13, size: 15, offset: 144, flags: DIFlagBitField, extraData: i64 144)
!23 = !DIDerivedType(tag: DW_TAG_member, name: "i11", scope: !10, file: !3, line: 15, baseType: !13, size: 5, offset: 168, flags: DIFlagBitField, extraData: i64 160)
!24 = !DIDerivedType(tag: DW_TAG_member, name: "i12", scope: !10, file: !3, line: 16, baseType: !13, size: 6, offset: 176, flags: DIFlagBitField, extraData: i64 176)
!25 = !DIDerivedType(tag: DW_TAG_member, name: "i13", scope: !10, file: !3, line: 17, baseType: !13, size: 16, offset: 192)
!26 = !DIDerivedType(tag: DW_TAG_member, name: "i14", scope: !10, file: !3, line: 18, baseType: !13, size: 5, offset: 208, flags: DIFlagBitField, extraData: i64 208)
!27 = !DIDerivedType(tag: DW_TAG_member, name: "i15", scope: !10, file: !3, line: 19, baseType: !13, size: 14, offset: 224, flags: DIFlagBitField, extraData: i64 224)
!28 = !DIDerivedType(tag: DW_TAG_member, name: "i16", scope: !10, file: !3, line: 20, baseType: !13, size: 16, offset: 240)
!29 = !DIDerivedType(tag: DW_TAG_member, name: "i17", scope: !10, file: !3, line: 21, baseType: !13, size: 4, offset: 256, flags: DIFlagBitField, extraData: i64 256)
!30 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression(DW_OP_LLVM_fragment, 16, 16))
!31 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression(DW_OP_LLVM_fragment, 32, 16))
!32 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression(DW_OP_LLVM_fragment, 48, 16))
!33 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression(DW_OP_deref, DW_OP_constu, 1, DW_OP_plus, DW_OP_constu, 0, DW_OP_plus, DW_OP_stack_value))
!34 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression(DW_OP_LLVM_fragment, 80, 16))
!35 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression(DW_OP_LLVM_fragment, 96, 16))
!36 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression(DW_OP_LLVM_fragment, 112, 16))
!37 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression(DW_OP_LLVM_fragment, 128, 16))
!38 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression(DW_OP_LLVM_fragment, 144, 16))
!39 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression(DW_OP_LLVM_fragment, 160, 16))
!40 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression(DW_OP_LLVM_fragment, 176, 16))
!41 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression(DW_OP_LLVM_fragment, 192, 16))
!42 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression(DW_OP_LLVM_fragment, 208, 16))
!43 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression(DW_OP_LLVM_fragment, 224, 16))
!44 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression(DW_OP_LLVM_fragment, 256, 16))
!49 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression(DW_OP_deref, DW_OP_constu, 1, DW_OP_plus, DW_OP_constu, 0, DW_OP_plus, DW_OP_stack_value))

!45 = !{i32 2, !"Dwarf Version", i32 4}
!46 = !{i32 2, !"Debug Info Version", i32 3}
!47 = !{i32 1, !"wchar_size", i32 1}
!48 = !{!"clang version 6.0.0"}

With an llc compiled with 3.6.0 the above input makes llc hit an assert
llc: ../lib/CodeGen/AsmPrinter/DwarfExpression.cpp:405: void llvm::DwarfExpression::addFragmentOffset(const llvm::DIExpression *): Assertion `FragmentOffset >= OffsetInBits && "overlapping or duplicate fragments"' failed.

However, if I compile llc with some gcc version, I don't hit the assert, so it's not very stable.

Applying this patch makes the crash go away even if I compile with clang 3.6.0.

[aprantl]

LGTM together with Mikael's testcase modified to CHECK the output (otherwise the test will succeed even after symlinking llc to /bin/true :-)

llvm/trunk/lib/CodeGen/AsmPrinter/DwarfDebug.cpp

if (DIE *D = TheCU.getOrCreateContextDIE(N->getScope()))
     D->addChild(TheCU.constructImportedEntityDIE(N));
 }
 
 /// Sort and unique GVEs by comparing their fragment offset.
 static SmallVectorImpl<DwarfCompileUnit::GlobalExpr> &
 sortGlobalExprs(SmallVectorImpl<DwarfCompileUnit::GlobalExpr> &GVEs) {
   std::sort(GVEs.begin(), GVEs.end(),
             [](DwarfCompileUnit::GlobalExpr A, DwarfCompileUnit::GlobalExpr B) {
-              if (A.Expr != B.Expr && A.Expr && B.Expr) {
-                auto FragmentA = A.Expr->getFragmentInfo();
-                auto FragmentB = B.Expr->getFragmentInfo();
-                if (FragmentA && FragmentB)
-                  return FragmentA->OffsetInBits < FragmentB->OffsetInBits;
-              }
-              return false;
+              // Sort order: first null exprs, then exprs without fragment
+              // info, then sort by fragment offset in bits.
+              // FIXME: Come up with a more comprehensive comparator so
+              // the sorting isn't non-deterministic, and so the following
+              // std::unique call works correctly.
+              if (!A.Expr || !B.Expr)
+                return !!B.Expr;
+              if (!FragmentA || !FragmentB)
+                return !!FragmentB;
             });
   GVEs.erase(std::unique(GVEs.begin(), GVEs.end(),
                          [](DwarfCompileUnit::GlobalExpr A,
                             DwarfCompileUnit::GlobalExpr B) {
                            return A.Expr == B.Expr;
                          }),
              GVEs.end());
   return GVEs;