[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

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

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

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

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

3102–3106

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

3115

Should we add a replaceWithUndef method to DebugInfoIntrinsicInst?

[bjope]

LGTM as well!

[jmorse]

lib/Transforms/InstCombine/InstructionCombining.cpp

3102–3106

Folding into commit,

3115

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 ↗

(On Diff #186616)

(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 ↗

(On Diff #186616)

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 ↗

(On Diff #186616)

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.)

include/llvm/Transforms/Utils/Local.h

 void replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
                               DIBuilder &Builder, int Offset = 0);
 
 /// Assuming the instruction \p I is going to be deleted, attempt to salvage
 /// debug users of \p I by writing the effect of \p I in a DIExpression.
 /// Returns true if any debug users were updated.
 bool salvageDebugInfo(Instruction &I);
 
+/// Implementation of salvageDebugInfo, applying only to instructions in
+/// \p Insns, rather than all debug users of \p I.
+bool salvageDebugInfoForDbgValues(Instruction &I,
+                                  ArrayRef<DbgVariableIntrinsic *> Insns);
+
 /// Point debug users of \p From to \p To or salvage them. Use this function
 /// only when replacing all uses of \p From with \p To, with a guarantee that
 /// \p From is going to be deleted.
 ///
 /// Follow these rules to prevent use-before-def of \p To:
 ///   . If \p To is a linked Instruction, set \p DomPoint to \p To.
 ///   . If \p To is an unlinked Instruction, set \p DomPoint to the Instruction
 ///     \p To will be inserted after.

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, as we
+  // don't wish to un-necessarily re-order variables.
+  SmallVector<DbgVariableIntrinsic *, 2> DbgUsers;
   findDbgUsers(DbgUsers, I);
   for (auto *DII : DbgUsers) {
     if (DII->getParent() == SrcBlock) {
+      SmallVector<DbgVariableIntrinsic *, 1> TmpUser{DII};
+      if (!salvageDebugInfoForDbgValues(*I, TmpUser)) {
         DII->moveBefore(&*InsertPos);
         LLVM_DEBUG(dbgs() << "SINK: " << *DII << '\n');
       }
     }
+  }
   return true;
 }
 
 bool InstCombiner::run() {
   while (!Worklist.isEmpty()) {
     Instruction *I = Worklist.RemoveOne();
     if (I == nullptr) continue;  // skip null values.
 
     // Check to see if we can DCE the instruction.
     if (isInstructionTriviallyDead(I, &TLI)) {
       LLVM_DEBUG(dbgs() << "IC: DCE: " << *I << '\n');
       eraseInstFromFunction(*I);
       ++NumDeadInst;
       MadeIRChange = true;
       continue;

lib/Transforms/Utils/Local.cpp

 }
 
 bool llvm::salvageDebugInfo(Instruction &I) {
   SmallVector<DbgVariableIntrinsic *, 1> DbgUsers;
   findDbgUsers(DbgUsers, &I);
   if (DbgUsers.empty())
     return false;
 
+  return salvageDebugInfoForDbgValues(I, DbgUsers);
+}
+
+bool llvm::salvageDebugInfoForDbgValues(
+    Instruction &I, ArrayRef<DbgVariableIntrinsic *> DbgUsers) {
   auto &M = *I.getModule();
   auto &DL = M.getDataLayout();
   auto &Ctx = I.getContext();
   auto wrapMD = [&](Value *V) { return wrapValueInMetadata(Ctx, V); };
 
   auto doSalvage = [&](DbgVariableIntrinsic *DII, SmallVectorImpl<uint64_t> &Ops) {
     auto *DIExpr = DII->getExpression();
     if (!Ops.empty()) {
if (auto *CI = dyn_cast<CastInst>(&I)) {
     return true;
   } else if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
     unsigned BitWidth =
         M.getDataLayout().getIndexSizeInBits(GEP->getPointerAddressSpace());
     // Rewrite a constant GEP into a DIExpression.  Since we are performing
     // arithmetic to compute the variable's *value* in the DIExpression, we
     // need to mark the expression with a DW_OP_stack_value.
     APInt Offset(BitWidth, 0);
-    if (GEP->accumulateConstantOffset(M.getDataLayout(), Offset))
+    if (GEP->accumulateConstantOffset(M.getDataLayout(), Offset)) {
       for (auto *DII : DbgUsers)
         applyOffset(DII, Offset.getSExtValue());
       return true;
+    } else {
+      return false;
+    }
   } else if (auto *BI = dyn_cast<BinaryOperator>(&I)) {
     // Rewrite binary operations with constant integer operands.
     auto *ConstInt = dyn_cast<ConstantInt>(I.getOperand(1));
     if (!ConstInt || ConstInt->getBitWidth() > 64)
       return false;
 
     uint64_t Val = ConstInt->getSExtValue();
     for (auto *DII : DbgUsers) {

test/Transforms/InstCombine/debuginfo_add.ll

 target datalayout = "e-m:o-p:32:32-f64:32:64-v64:32:64-v128:32:128-a:0:32-n32-S32"
 target triple = "thumbv7s-apple-ios5.0.0"
 
 %struct.vm_object = type { i64 }
 
 ; Function Attrs: nounwind ssp
 define void @f(%struct.vm_object* %object, i64* nocapture readonly %start) local_unnamed_addr #0 !dbg !11 {
 entry:
+
+  ; The 'load' and the 'add' are sunken out of this basic block. However it's
+  ; undesirable for the dbg.values to move: they can and should be salvaged.
+  ; Check that the middle dbg.value below is salvaged back to operating only
+  ; on %start rather than the sunk insts.
+  ;
+  ; CHECK-LABEL: entry:
+  ; CHECK:      call void @llvm.dbg.value(metadata i64* %start, metadata !22, metadata !DIExpression()), !dbg !
+  ; CHECK-NEXT: call void @llvm.dbg.value(metadata i64* %start, metadata !25, metadata !DIExpression(DW_OP_deref)), !dbg !
+  ; CHECK-NEXT: call void @llvm.dbg.value(metadata i64* %start, metadata !26, metadata !DIExpression(DW_OP_deref, DW_OP_constu, 4096, DW_OP_minus, DW_OP_stack_value)), !dbg !
+  ; CHECK-NEXT: call void @llvm.dbg.value(metadata i32 undef, metadata !23, metadata !DIExpression()), !dbg !
+  ; CHECK-NEXT: br i1 undef
+
+
   tail call void @llvm.dbg.value(metadata %struct.vm_object* %object, metadata !21, metadata !DIExpression()), !dbg !27
   tail call void @llvm.dbg.value(metadata i64* %start, metadata !22, metadata !DIExpression()), !dbg !28
   %0 = load i64, i64* %start, align 4, !dbg !29
   tail call void @llvm.dbg.value(metadata i64 %0, metadata !25, metadata !DIExpression()), !dbg !30
   %offset.08 = add i64 %0, -4096
   tail call void @llvm.dbg.value(metadata i64 %offset.08, metadata !26, metadata !DIExpression()), !dbg !31
   tail call void @llvm.dbg.value(metadata i32 undef, metadata !23, metadata !DIExpression()), !dbg !32
   br i1 undef, label %for.end, label %for.body.lr.ph, !dbg !32
 
 for.body.lr.ph:                                   ; preds = %entry
-  ; The 'load' and the 'add' are sunken to this basic block. So let's verify that the related dbg.values are sunken as well.
-  ; The add is later eliminated, so we verify that the dbg.value is salvaged by using DW_OP_minus.
+  ; Check that the load is sunk here; the add is optimised out. Nothing else
+  ; should be in this block.
   ; CHECK-LABEL: for.body.lr.ph:
   ; CHECK-NEXT: %0 = load
-  ; CHECK-NEXT: call void @llvm.dbg.value(metadata i64 %0, metadata !25, metadata !DIExpression()), !dbg !
-  ; CHECK-NEXT: call void @llvm.dbg.value(metadata i64 %0, metadata !26, metadata !DIExpression(DW_OP_constu, 4096, DW_OP_minus, DW_OP_stack_value)), !dbg !
+  ; CHECK-NEXT: br label %for.body
   br label %for.body, !dbg !32
 
 for.body:                                         ; preds = %for.body.lr.ph, %for.body
   ; CHECK-LABEL: for.body:
   %offset.010 = phi i64 [ %offset.08, %for.body.lr.ph ], [ %offset.0, %for.body ]
   %head_size.09 = phi i32 [ undef, %for.body.lr.ph ], [ %sub2, %for.body ]
   tail call void @llvm.dbg.value(metadata i32 %head_size.09, metadata !23, metadata !DIExpression()), !dbg !31
   %call = tail call i32 bitcast (i32 (...)* @use to i32 (i64, %struct.vm_object*)*)(i64 %offset.010, %struct.vm_object* %object) #3, !dbg !34