Avoid redundant or out-of-order debug value sinking in InstCombine

[StephenTozer]

Summary

This patch modifies TryToSinkInstruction in the InstCombine pass, to prevent redundant debug intrinsics from being produced, and also prevent the intrinsics from being emitted in an incorrect order. It does this by ensuring that when this pass sinks an instruction and creates clones of the debug intrinsics that use that instruction, it inserts those debug intrinsics in their original order, and only inserts the last debug intrinsic for each variable in the Instruction's block.

This patch was created to deal with an issue found while testing another patch (D94631) in which repeated sinking of instructions across a very large number of basic blocks resulted in a cascading mass of debug intrinsics as each sink clones each previous intrinsic as well as any new ones in the current basic block. For one of the clang 3.4 source files, this resulted in an LL file 14gb in size after optimizations; this patch reduces the resulting file to 5mb. Although this is a very extreme case, it is quite likely that this problem is occuring on a smaller scale for other large source files - large switches seem particularly susceptible (in this generated by CodeEmitterGenerator using TableGen).

Note that as redundant debug intrinsics will not be emitted in the final debug info, this patch should not have any actual effect on the size of debug info produced; it should however improve correctness in cases where debug intrinsics were being emitted out-of-order (causing old debug values to overwrite new ones), and has a positive effect on compile time and memory usage in cases where this issue occurs.

[rnk]

Nice find!

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

18–1

This comparison here makes it so that the non-deterministic ordering of users doesn't cause non-deterministic output.

24–26

If we already know SrcBlock before we do this sort, I think it would be clearer to the reader if you start out by filtering out all the users not in SrcBlock. Then this comment about other blocks is unnecessary.

[StephenTozer]

Filter out DbgUsers that will not be sunk prior to sorting.

[jmorse]

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

51–52

Doesn't this need a CHECK-NOT dbg.value in there, to verify that only one dbg.value is sunk?

[StephenTozer]

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

51–52

I don't think so - this line should match either of the debug values, and the next lines are CHECK-SAME and CHECK-NEXT. As all the sunk debug values are in a single contiguous block, this should match iff there is only one debug value sunk.

[jmorse]

LGTM, but pls2leave it 24 hours or so in case @rnk chimes in.

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

51–52

Fiddling with inputs, I couldn't get it to not fail. I think what I wanted was a much plainer "There are no dbg.values between the start of the block and the one we're matching". It looks like by having the first CHECK test for %gep, this ensures that there's only one dbg.value for %gep, which is good enough.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

 // into:
 //    %Z = add i32 %X, 2
 //
 // This is a simple worklist driven algorithm.
 //
 // This pass guarantees that the following canonicalizations are performed on
 // the program:
 //    1. If a binary operator has a constant operand, it is moved to the RHS
 //    2. Bitwise operators with constant operands are always grouped so that
 //       shifts are performed first, then or's, then and's, then xor's.
 //    3. Compare instructions are converted from <,>,<=,>= to ==,!= if possible
 //    4. All cmp instructions on boolean values are replaced with logical ops
 //    5. add X, X is represented as (X*2) => (X << 1)
 //    6. Multiplies with a power-of-two constant argument are transformed into
 //       shifts.
 //   ... etc.
 //
 //===----------------------------------------------------------------------===//
 
static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) {
 
   // Also sink all related debug uses from the source basic block. Otherwise we
   // 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);
+  // Process the sinking DbgUsers in reverse order, as we only want to clone the
+  // last appearing debug intrinsic for each given variable.
+  SmallVector<DbgVariableIntrinsic *, 2> DbgUsersToSink;
+  for (DbgVariableIntrinsic *DVI : DbgUsers)
+    if (DVI->getParent() == SrcBlock)
+      DbgUsersToSink.push_back(DVI);
+  llvm::sort(DbgUsersToSink,
+             [](auto *A, auto *B) { return B->comesBefore(A); });
 
   // Update the arguments of a dbg.declare instruction, so that it
   // does not point into a sunk instruction.
   auto updateDbgDeclare = [&I](DbgVariableIntrinsic *DII) {
     if (!isa<DbgDeclareInst>(DII))
       return false;
 
     if (isa<CastInst>(I))
       DII->setOperand(
           0, MetadataAsValue::get(I->getContext(),
                                   ValueAsMetadata::get(I->getOperand(0))));
     return true;
   };
 
   SmallVector<DbgVariableIntrinsic *, 2> DIIClones;
-  for (auto User : DbgUsers) {
+  SmallSet<DebugVariable, 4> SunkVariables;
+  for (auto User : DbgUsersToSink) {
     // A dbg.declare instruction should not be cloned, since there can only be
     // one per variable fragment. It should be left in the original place
     // because the sunk instruction is not an alloca (otherwise we could not be
     // here).
-    if (User->getParent() != SrcBlock || updateDbgDeclare(User))
+    if (updateDbgDeclare(User))
+      continue;
+
+    DebugVariable DbgUserVariable =
+        DebugVariable(User->getVariable(), User->getExpression(),
+                      User->getDebugLoc()->getInlinedAt());
+
+    if (!SunkVariables.insert(DbgUserVariable).second)
       continue;
 
     DIIClones.emplace_back(cast<DbgVariableIntrinsic>(User->clone()));
     LLVM_DEBUG(dbgs() << "CLONE: " << *DIIClones.back() << '\n');
   }
 
   // Perform salvaging without the clones, then sink the clones.
   if (!DIIClones.empty()) {
     salvageDebugInfoForDbgValues(*I, DbgUsers);
-    for (auto &DIIClone : DIIClones) {
+    // The clones are in reverse order of original appearance, reverse again to
+    // maintain the original order.
+    for (auto &DIIClone : llvm::reverse(DIIClones)) {
       DIIClone->insertBefore(&*InsertPos);
       LLVM_DEBUG(dbgs() << "SINK: " << *DIIClone << '\n');
     }
   }
 
   return true;
 }
 

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

entry:
   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
 }
 
+; This GEP is sunk, and has multiple debug uses in the same block. Check that
+; only the last use is cloned into the sunk block, and that both of the
+; original dbg.values are salvaged.
+;
+; CHECK-LABEL: define i32 @baz(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:  call void @llvm.dbg.value(metadata i32* %a, metadata !{{[0-9]+}},
+; CHECK-SAME:  metadata !DIExpression(DW_OP_plus_uconst, 4, DW_OP_plus_uconst, 5, DW_OP_stack_value))
+; CHECK-NEXT:  br label %sink1
+
+define i32 @baz(i32 *%a) !dbg !80 {
+entry:
+  %gep = getelementptr i32, i32 *%a, i32 1
+  call void @llvm.dbg.value(metadata i32 *%gep, metadata !83, metadata !12), !dbg !84
+  call void @llvm.dbg.value(metadata i32 *%gep, metadata !83, metadata !DIExpression(DW_OP_plus_uconst, 5)), !dbg !85
+  br label %sink1
+
+sink1:
+; CHECK-LABEL: sink1:
+; CHECK:       call void @llvm.dbg.value(metadata i32* %gep,
+; CHECK-SAME:  metadata !{{[0-9]+}}, metadata !DIExpression(DW_OP_plus_uconst, 5))
+; CHECK-NEXT:  load
+  %0 = load i32, i32* %gep, align 4, !dbg !85
+  ret i32 %0, !dbg !85
+}
+
 !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)
+!80 = distinct !DISubprogram(name: "baz", scope: !1, file: !1, line: 2, type: !8, isLocal: false, isDefinition: true, scopeLine: 3, flags: DIFlagPrototyped, isOptimized: false, unit: !0, retainedNodes: !2)
+!83 = !DILocalVariable(name: "l", scope: !80, file: !1, line: 2, type: !10)
+!84 = !DILocation(line: 5, column: 3, scope: !80)
+!85 = !DILocation(line: 6, column: 3, scope: !80)

llvm/test/Transforms/InstCombine/debuginfo_add.ll

entry:
   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-LABEL: for.body.lr.ph:
   ; CHECK-NEXT: %0 = load
-  ; 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: 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 !
   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