[DebugInfo][SelectionDAG] Change order while transferring SDDbgValue to another node

[krisb]

Summary

SelectionDAG::transferDbgValues() can 'reattach' SDDbgValue from one to another node, but doesn't change its source order. If the destination node has the order greater than the SDDbgValue, there are two possible issues revealed later:

• If debug info is attached to an instruction that is the first definition of a register, this ends up with a def-after-use case and the debug info gets 'undef' later.
• If MIR has another definition of a register above the debug info, debug info won't be 'undef' but may represent a source variable incorrectly because it appears (significantly) before an instruction corresponded to this debug info.

So, the patch changes the order of an SDDbgValue if it's being moved to a node with greater order.

[aprantl]

That seems reasonable.

llvm/test/DebugInfo/X86/sdag-transfer-dbgvalue.ll

28

Do we need all three dbg.values or could we further reduce the testcase by removing all but one?

[djtodoro]

llvm/test/DebugInfo/X86/sdag-transfer-dbgvalue.ll

74

I guess we do not need the TBAA metadata in the testcase.

[jmorse]

This risks changing the order in which variable assignments appear to occur, as there's no consideration of whether the new IROrder goes past a dbg.value intrinsic of the same variable.

This patch is potentially worth paying that price though: AFAIUI, SelectionDAG::transferDbgValues happens all the time, but multiple debug intrinsics for the same variable in the same block aren't necessarily common. Running a clang-3.4 build with this patch, I see a few thousand more locations, which is great, although there's no headline-grabbing impact.

Note that ScheduleDAGSDNodes does attempt to emit DBG_VALUEs immediately after node definitions (ProcessSourceNode and nearby), but it's fairly flakey. I also wrote up some details in [0] about the fact that nothing considers both

• where a value becomes available and
• where the value should become the variable location.

[0] https://bugs.llvm.org/show_bug.cgi?id=41583

[krisb]

Reduced the test.

[krisb]

@aprantl, @djtodoro thanks! I reduced the test a bit more.

@jmorse, thanks for pointing on this!

I found a couple of dozens of cases building clang where this patch causes SelectionDAG::transferDbgValues() to move processed debug value past another debug value of the same variable and I'm going to investigate them in details but it can take some time.

For now, I think we could conservatively let such debug values be on their places not changing their order (although it doesn't seem necessarily correct) and add corresponding TODO or FIXME note for further investigation.

It looks easy to check if a debug value gets moved past any others of the same variable: just to iterate over SDDbgValues and to find one that in-between From and To by their order. But there is one issue I faced that seems weird to me. I'd expect that a node should get an order that is greater than orders of its operands, but after DAGCombiner it's not true. I found lots of cases where a node has an order less than its operands. Do you know is it expected behavior?

[aprantl]

llvm/test/DebugInfo/X86/sdag-transfer-dbgvalue.ll

28

Another trick you can do is to delete all unneeded !dbg attachements or make them all point to the same location.

[jmorse]

I found a couple of dozens of cases building clang where this patch causes SelectionDAG::transferDbgValues() to move processed debug value past another debug value of the same variable and I'm going to investigate them in details but it can take some time.

For now, I think we could conservatively let such debug values be on their places not changing their order (although it doesn't seem necessarily correct) and add corresponding TODO or FIXME note for further investigation.

Yeah, the rest of the code around SelectionDAG doesn't do a good job of keeping location intrinsics in order; I think it's acceptable to suffer a little bit more re-ordering here for an increase in available locations, for now.

It looks easy to check if a debug value gets moved past any others of the same variable: just to iterate over SDDbgValues and to find one that in-between From and To by their order.

This is potentially expensive, particularly in ASAN builds where there are lots of variable locations. It might be worth benchmarking though in case I'm wrong.

But there is one issue I faced that seems weird to me. I'd expect that a node should get an order that is greater than orders of its operands, but after DAGCombiner it's not true. I found lots of cases where a node has an order less than its operands. Do you know is it expected behavior?

Ah, that's interesting -- according to comments for the "IROrder" field in SelectionDAGNodes.h, that number can be used to order node output instead of using a scheduler. So I wouldn't expect to see nodes with lesser order numbers. That being said, I'm not a SelectionDAG expert, so there could be some other explanation.

[krisb]

Rebased and reduced the test a bit more.

[krisb]

Yeah, the rest of the code around SelectionDAG doesn't do a good job of keeping location intrinsics in order; I think it's acceptable to suffer a little bit more re-ordering here for an increase in available locations, for now.

Okay, I'll commit the patch as is, then. This issue with 'IROrder' in SelectionDAG is quite tricky, so I'll submit further changes in separate patches.

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

if (SizeInBits) {
           continue;
       auto Fragment = DIExpression::createFragmentExpression(Expr, OffsetInBits,
                                                              SizeInBits);
       if (!Fragment)
         continue;
       Expr = *Fragment;
     }
     // Clone the SDDbgValue and move it to To.
-    SDDbgValue *Clone =
-        getDbgValue(Var, Expr, ToNode, To.getResNo(), Dbg->isIndirect(),
-                    Dbg->getDebugLoc(), Dbg->getOrder());
+    SDDbgValue *Clone = getDbgValue(
+        Var, Expr, ToNode, To.getResNo(), Dbg->isIndirect(), Dbg->getDebugLoc(),
+        std::max(ToNode->getIROrder(), Dbg->getOrder()));
     ClonedDVs.push_back(Clone);
 
     if (InvalidateDbg) {
       // Invalidate value and indicate the SDDbgValue should not be emitted.
       Dbg->setIsInvalidated();
       Dbg->setIsEmitted();
     }
   }

llvm/test/DebugInfo/X86/sdag-transfer-dbgvalue.ll

+; RUN: llc -start-after=codegenprepare -stop-before finalize-isel -o - %s | FileCheck %s
+
+; This tests that transferDbgValues() changes order of SDDbgValue transferred
+; to another node and debug info for 'ADD32ri' appears *after* the instruction.
+;
+; This test case was generated from the following program
+; using: clang -g -O3 -S -emit-llvm test.c
+;
+; int foo(int a, int *b) {
+;   int c = a + 512;
+;   if (c != 0)
+;     *b = a;
+;   return c;
+; }
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK-LABEL: bb.0.entry:
+; CHECK:       %[[REG:[0-9]+]]:gr32 = ADD32ri %1, 512
+; CHECK-NEXT:  DBG_VALUE %[[REG]]
+
+; Function Attrs: nofree norecurse nounwind uwtable writeonly
+define dso_local i32 @foo(i32 %a, i32* nocapture %b) local_unnamed_addr !dbg !7 {
+entry:
+  %add = add nsw i32 %a, 512, !dbg !18
+  call void @llvm.dbg.value(metadata i32 %add, metadata !16, metadata !DIExpression()), !dbg !17
+  %cmp = icmp eq i32 %add, 0, !dbg !19
+  br i1 %cmp, label %if.end, label %if.then, !dbg !21
+
+if.then:                                          ; preds = %entry
+  store i32 %a, i32* %b, align 4, !dbg !22
+  br label %if.end, !dbg !27
+
+if.end:                                           ; preds = %entry, %if.then
+  ret i32 %add, !dbg !28
+}
+
+; Function Attrs: nounwind readnone speculatable willreturn
+declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4, !5}
+!llvm.ident = !{!6}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 10.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, nameTableKind: None)
+!1 = !DIFile(filename: "test.c", directory: "/")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{i32 1, !"wchar_size", i32 4}
+!6 = !{!"clang version 10.0.0"}
+!7 = distinct !DISubprogram(name: "foo", scope: !8, file: !8, line: 1, type: !9, scopeLine: 1, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !13)
+!8 = !DIFile(filename: "test.c", directory: "/")
+!9 = !DISubroutineType(types: !10)
+!10 = !{!11, !11, !12}
+!11 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!12 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !11, size: 64)
+!13 = !{!14, !15, !16}
+!14 = !DILocalVariable(name: "a", arg: 1, scope: !7, file: !8, line: 1, type: !11)
+!15 = !DILocalVariable(name: "b", arg: 2, scope: !7, file: !8, line: 1, type: !12)
+!16 = !DILocalVariable(name: "c", scope: !7, file: !8, line: 2, type: !11)
+!17 = !DILocation(line: 0, scope: !7)
+!18 = !DILocation(line: 2, column: 13, scope: !7)
+!19 = !DILocation(line: 3, column: 9, scope: !20)
+!20 = distinct !DILexicalBlock(scope: !7, file: !8, line: 3, column: 7)
+!21 = !DILocation(line: 3, column: 7, scope: !7)
+!22 = !DILocation(line: 4, column: 8, scope: !20)
+!27 = !DILocation(line: 4, column: 5, scope: !20)
+!28 = !DILocation(line: 5, column: 3, scope: !7)