[DebugInfo][InstCombine] Prefer salvaging dbg.values over sinking them

[jmorse]

Summary

When sinking an instruction InstCombine currently sinks any local dbg.value users -- something that potentially re-orders variables. I've experienced some circumstances where pointer casts (and associated dbg.values) get sunk across multiple blocks to the point where they're used, artificially shortening the location range of the corresponding debuginfo variable.

Instead of sinking everything, attempt to salvage the dbg.value first. This requires exposing a more expressive form of salvageDebugInfo where we can specify which debug users to attempt to salvage -- otherwise many debug users would be needlessly rewritten. If un-successful, the debug users gets sunk as it does now to prevent debug-use-before-def, if successful it stays. While we're here, fix the salvageDebugUsers' salvaging of GEPs to return false if it's unsalvagable.

Testing for this behaviour happens in the updated test -- where we can push through both the sunk addition, and even the load, to keep all dbg.values in their original locations.

(This patch makes minimal differences to a build of clang-3.4, once more due to our old friend placeDbgValues, but is a worthwhile improvement IMHO).

[aprantl]

Seems reasonable to me.

include/llvm/Transforms/Utils/Local.h

348 ↗

(On Diff #182056)

ArrayRef ?

[jmorse]

Use an ArrayRef rather than a SmallVectorImpl

[jmorse]

Ping

[aprantl]

I think this looks reasonable, thanks!

[bjope]

test/Transforms/InstCombine/debuginfo_add.ll

52 ↗

(On Diff #182264)

Shouldn't there still be som dbg.value for variable !25 after the load, indicating that the variable is in %0?

Have you checked what happens in the final output? It all might depend on which live range that is longest (%start or %0), but if this load is the last user of %start we only know how to get the value of the variable !25 from %0 after the load.

I'm also not sure how well LLVM handles these dbg.value intrinsics with DW_OP_deref. What defines the end of the debug range for those? The end of the BB? The next instruction that potentially can write to memory? When the pointer register is dead? The use of DW_OP_deref (in opt) has been quite rare so far (afaik). A direct mapping to the SSA value is a more well established concept (the dbg.value is valid for the range of the SSA value, or up until the next dbg.value that indicates that the variable is somewhere else). Perhaps also limited to the current BB (or is that only for DBG_VALUE and not dbg.value? or only after de-SSA?). But when we say that the variable is in memory (and not a unique stack slot for the variable), how do we know when this isn't valid any longer when calculating debug value ranges?

[jmorse]

test/Transforms/InstCombine/debuginfo_add.ll

52 ↗

(On Diff #182264)

Shouldn't there still be some dbg.value for variable !25 after the load, indicating that the variable is in %0?

Have you checked what happens in the final output? It all might depend on which live range that is longest (%start or %0), but if this load is the last user of %start we only know how to get the value of the variable !25 from %0 after the load.

Definitely true -- experimentally testing this on a build of clang-3.4, with the patch as it is we give 75.07% of all variables locations, and cover 45.15% of scope bytes; placing a dbg.value at the sunk location too produces 75.16% location coverage and 45.71%. Which is a small but non-trivial improvement.

The downside is that we will leave a dbg.value in each block an instruction sinks through -- and if multiple memory computations are salvaged through (load then gep then ptrcast) each one will leave a dbg.value in blocks sunk through. That being said, a few timed builds of clang-3.4 show the performance penalty as being less than 0.5%, which is well within error margins.

I'm also not sure how well LLVM handles these dbg.value intrinsics with DW_OP_deref. [Various possibilities].

A great question, that I don't know the answer to right now. I'll try and break some examples using this patch.

[jmorse]

I suspect this change now blocks on https://bugs.llvm.org/show_bug.cgi?id=40628 (see inline comments), or at least until there's more understanding of how to resolve problems with new DW_OP_derefs being introduced.

test/Transforms/InstCombine/debuginfo_add.ll

52 ↗

(On Diff #182264)

I'm also not sure how well LLVM handles these dbg.value intrinsics with DW_OP_deref.

Unfortunately it would appear there's no termination of such location ranges at all, and a variable that becomes a salvaged load can observe subsequent stores through the DW_OP_deref expression. I've filed this as https://bugs.llvm.org/show_bug.cgi?id=40628

[jmorse]

The issue with generating new DW_OP_derefs has been resolved by r353824, as a result we no longer change existing tests with this patch.

I realised at the same time that we should be emitting undef dbg.values at this stage: if we sink a dbg.value and cannot salvage it, then we should terminate any earlier location range. Trying the clang-3.4 build statistics I get the following results based on r353832 (note that the llvm-dwarfdump --statistics formula changed recently). First column variables-with-location coverage, second scope-bytes-covered.

r353832: 76.9%, 44.8%
salvage, no undef: 77.2%, 44.9%
salvage and undef: 77.2%, 45.5%

Adding the undefs loses 300 variable locations (0.008%), and yields 0.6% more scope bytes covered. Exactly where the scope-bytes-covered improvement comes from is a bit of a mystery to me, but it's an improvement nonetheless.

Note that I've added a reverse() on the iteration over DbgUsers... without this, the order of some dbg.values in Transforms/InstCombine/debuginfo_add.ll swap (!25 and !26). I.. don't really have a good explanation as to why.

[jmorse]

(Plus I added a new test to cover this behaviour, and removed some plumbing for salvageDebugUsersForDbgValues that was folded into an earlier commit).

[aprantl]

lib/Transforms/InstCombine/InstructionCombining.cpp

3110 ↗

(On Diff #186479)

"is local to" -> is in the same basic block ?

3123 ↗

(On Diff #186479)

Should we add a replaceWithUndef method to DebugInfoIntrinsicInst?

[bjope]

LGTM as well!

[jmorse]

lib/Transforms/InstCombine/InstructionCombining.cpp

3110 ↗

(On Diff #186479)

Folding into commit,

3123 ↗

(On Diff #186479)

We definitely should -- this should be a common operation by optimisations. (I'll file a follow-up at some point).

[jmorse]

Also, thanks for reviews!

[bjope]

llvm/trunk/lib/Transforms/InstCombine/InstructionCombining.cpp

3122

(post commit comment)
I see things like this in the IR after this:

call void @llvm.dbg.value(metadata %foo * undef, metadata !2292, metadata !DIExpression(DW_OP_plus_uconst, 3, DW_OP_stack_value)), !dbg !2760

It doesn't fill any purpose to have a complicated DIExpression when being based on an undef value afaict.
Maybe we should strip away the DIExpression right away here, or what do you think?

[jmorse]

llvm/trunk/lib/Transforms/InstCombine/InstructionCombining.cpp

3122

I agree, it's pointless memory use and a distraction (or even misleading). This should probably be rolled into a DbgVariableIntrinsic method that sets operand-0 to undef *and* clears the expression.

I imagine that for fragments of larger variables though, we would need to keep the DW_OP_LLVM_fragment so that only that portion of the variable gets undef'd.

(I can't follow this up with code for about a week due to other backlogs alas).

[bjope]

llvm/trunk/lib/Transforms/InstCombine/InstructionCombining.cpp

3122

Yes, good catch. We still need it (or at least parts of the DIExpression) for fragments, I did not think about that.

Anyway, this won't cost anything in the final DWARF location lists, so it is not that important. It is just a little bit confusing when looking at the IR, and it might have a negligible cost in the IR.

(Maybe I'll find some time to fix it. Although not on top of the priority list right now. And I do not think it is worth writing a PR for this.)

llvm/trunk/lib/Transforms/InstCombine/InstructionCombining.cpp

for (BasicBlock::iterator Scan = I->getIterator(),
       if (Scan->mayWriteToMemory())
         return false;
   }
   BasicBlock::iterator InsertPos = DestBlock->getFirstInsertionPt();
   I->moveBefore(&*InsertPos);
   ++NumSunkInst;
 
   // Also sink all related debug uses from the source basic block. Otherwise we
-  // get debug use before the def.
-  SmallVector<DbgVariableIntrinsic *, 1> DbgUsers;
+  // get debug use before the def. Attempt to salvage debug uses first, to
+  // maximise the range variables have location for. If we cannot salvage, then
+  // mark the location undef: we know it was supposed to receive a new location
+  // here, but that computation has been sunk.
+  SmallVector<DbgVariableIntrinsic *, 2> DbgUsers;
   findDbgUsers(DbgUsers, I);
-  for (auto *DII : DbgUsers) {
+  for (auto *DII : reverse(DbgUsers)) {
     if (DII->getParent() == SrcBlock) {
-      DII->moveBefore(&*InsertPos);
+      // dbg.value is in the same basic block as the sunk inst, see if we can
+      // salvage it. Clone a new copy of the instruction: on success we need
+      // both salvaged and unsalvaged copies.
+      SmallVector<DbgVariableIntrinsic *, 1> TmpUser{
+          cast<DbgVariableIntrinsic>(DII->clone())};
+
+      if (!salvageDebugInfoForDbgValues(*I, TmpUser)) {
+        // We are unable to salvage: sink the cloned dbg.value, and mark the
+        // original as undef, terminating any earlier variable location.
         LLVM_DEBUG(dbgs() << "SINK: " << *DII << '\n');
+        TmpUser[0]->insertBefore(&*InsertPos);
+        Value *Undef = UndefValue::get(I->getType());
+        DII->setOperand(0, MetadataAsValue::get(DII->getContext(),
+                                                ValueAsMetadata::get(Undef)));
+      } else {
+        // We successfully salvaged: place the salvaged dbg.value in the
+        // original location, and move the unmodified dbg.value to sink with
+        // the sunk inst.
+        TmpUser[0]->insertBefore(DII);
+        DII->moveBefore(&*InsertPos);
+      }
     }
   }
   return true;
 }
 
 bool InstCombiner::run() {
   while (!Worklist.isEmpty()) {
     Instruction *I = Worklist.RemoveOne();

llvm/trunk/test/Transforms/InstCombine/debuginfo-sink.ll

+; RUN: opt  %s -instcombine -S | FileCheck %s
+
+; Test sinking of dbg.values when instcombine sinks associated instructions.
+
+declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+; This GEP is sunk, but can be folded into a DIExpression. Check that it
+; gets folded. The dbg.value should be duplicated in the block its sunk
+; into, to maximise liveness.
+;
+; CHECK-LABEL: define i32 @foo(i32*
+; CHECK:       call void @llvm.dbg.value(metadata i32* %a, metadata !{{[0-9]+}},
+; CHECK-SAME:  metadata !DIExpression(DW_OP_plus_uconst, 4, DW_OP_stack_value))
+; CHECK-NEXT:  br label %sink1
+
+define i32 @foo(i32 *%a) !dbg !7 {
+entry:
+  %gep = getelementptr i32, i32 *%a, i32 1
+  call void @llvm.dbg.value(metadata i32 *%gep, metadata !16, metadata !12), !dbg !15
+  br label %sink1
+
+sink1:
+; CHECK-LABEL: sink1:
+; CHECK:       call void @llvm.dbg.value(metadata i32* %gep,
+; CHECK-SAME:                    metadata !{{[0-9]+}}, metadata !DIExpression())
+; CHECK-NEXT:  load
+  %0 = load i32, i32* %gep, align 4, !dbg !15
+  ret i32 %0, !dbg !15
+}
+
+; In this example the GEP cannot (yet) be salvaged. Check that not only is the
+; dbg.value sunk, but an undef dbg.value is left to terminate any earlier
+; value range.
+
+; CHECK-LABEL: define i32 @bar(
+; CHECK:       call void @llvm.dbg.value(metadata i32* undef,
+; CHECK-NEXT:  br label %sink2
+
+define i32 @bar(i32 *%a, i32 %b) !dbg !70 {
+entry:
+  %gep = getelementptr i32, i32 *%a, i32 %b
+  call void @llvm.dbg.value(metadata i32* %gep, metadata !73, metadata !12), !dbg !74
+  br label %sink2
+
+sink2:
+; CHECK-LABEL: sink2:
+; CHECK:       call void @llvm.dbg.value(metadata i32* %gep,
+; CHECK-SAME:                    metadata !{{[0-9]+}}, metadata !DIExpression())
+; CHECK-NEXT:  load
+; CHECK-NEXT:  ret
+  %0 = load i32, i32* %gep
+  ret i32 %0
+}
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4, !5}
+!llvm.ident = !{!6}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug)
+!1 = !DIFile(filename: "a.c", directory: ".")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{i32 1, !"PIC Level", i32 2}
+!6 = !{!"clang"}
+!7 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 2, type: !8, isLocal: false, isDefinition: true, scopeLine: 3, flags: DIFlagPrototyped, isOptimized: false, unit: !0, retainedNodes: !2)
+!8 = !DISubroutineType(types: !9)
+!9 = !{!10, !10}
+!10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!11 = !DILocalVariable(name: "j", scope: !7, file: !1, line: 2, type: !10)
+!12 = !DIExpression()
+!15 = !DILocation(line: 5, column: 3, scope: !7)
+!16 = !DILocalVariable(name: "h", scope: !7, file: !1, line: 4, type: !10)
+!70 = distinct !DISubprogram(name: "bar", scope: !1, file: !1, line: 2, type: !71, isLocal: false, isDefinition: true, scopeLine: 3, flags: DIFlagPrototyped, isOptimized: false, unit: !0, retainedNodes: !2)
+!71 = !DISubroutineType(types: !72)
+!72 = !{!10, !10, !10}
+!73 = !DILocalVariable(name: "k", scope: !70, file: !1, line: 2, type: !10)
+!74 = !DILocation(line: 5, column: 3, scope: !70)