[DebugInfo] Skip dbg.value+derefs in RemoveRedundantDbgInstrs forward scan [3/3]

[Orlando]

Summary

See comment 3 on PR47946.

InlineLowerDbgDeclare looks for dbg.value+derefs which have been inserted before
call instructions by LowerDbgDeclare. However, without this patch these
intrinsics are eligable for removal by RemoveRedundantDbgInstr.

[bjope]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

423–425

Not sure I understand exactly how/if this motivates why the dbg.value should be kept. If we first say that the variable is at address X, and then later say that the variable is at address X, the second statement seem redundant to me.

llvm/test/DebugInfo/Generic/dont-remove-redundant-dbg-derefs.ll

30

So if you do this ten times in a row (couldn't that be the case if for example unrolling a loop fully?) you would keep all of them as well.
(well I guess the backward scan would clean it up if they really are consecutive)

An alternative would be to filter out all entries with a deref from the VariableMap when finding a call. Or is it still important that the dbg.value with a deref is just before the call? Then, how is it guaranteed that no other pass is inserting something between the dbg.value and the call in such sitautions?

[bjope]

llvm/test/DebugInfo/Generic/dont-remove-redundant-dbg-derefs.ll

30

Looking at patch 2/3 it seems like InlineLowerDbgDeclare only handle the dbg.value that are adjacent to the call.

One could use an intermediate MaybeToBeRemoved map that is cleaned when finding a call, or appended to ToBeRemoved (and cleaned) when finding a non-dbg-intrinsic during the forward scan. That would pinpoint the algorithm to just keep dbg.value+deref just before a call. But maybe not worth the fuzz if these otherwise redundant dbg.value+deref instructions are rare.

Still, it might be nice to for example duplicate the dbg.value here and on line 31 to see that the backward scan still eliminates redundant dbg.value+deref when they are adjacent to each other (non non-dbg-intrinsic in between).

[Orlando]

Thank you @bjope for taking a look at this.

llvm/test/DebugInfo/Generic/dont-remove-redundant-dbg-derefs.ll

30

Or is it still important that the dbg.value with a deref is just before the call? Then, how is it guaranteed that no other pass is inserting something between the dbg.value and the call in such sitautions?

Unfortunately there are no guarantees. I don't like this but I'm not sure what else we can reasonably do within the current debug-info framework.

Looking at patch 2/3 it seems like InlineLowerDbgDeclare only handle the dbg.value that are adjacent to the call.

Yeah that's right.

One could use an intermediate MaybeToBeRemoved map that is cleaned when finding a call, or appended to ToBeRemoved (and cleaned) when finding a non-dbg-intrinsic during the forward scan. That would pinpoint the algorithm to just keep dbg.value+deref just before a call. But maybe not worth the fuzz if these otherwise redundant dbg.value+deref instructions are rare.

In practice I don't think there are any problems with this suggestion, but based on @jeremy's comment here https://bugs.llvm.org/show_bug.cgi?id=47946#c4 I'm not sure whether we should remove any dbg.value+derefs in the forward scan. What do you think?

Still, it might be nice to for example duplicate the dbg.value here and on line 31 to see that the backward scan still eliminates redundant dbg.value+deref when they are adjacent to each other (non non-dbg-intrinsic in between)

SGTM, I will update the test.

[bjope]

llvm/test/DebugInfo/Generic/dont-remove-redundant-dbg-derefs.ll

30

One could use an intermediate MaybeToBeRemoved map that is cleaned when finding a call, or appended to ToBeRemoved (and cleaned) when finding a non-dbg-intrinsic during the forward scan. That would pinpoint the algorithm to just keep dbg.value+deref just before a call. But maybe not worth the fuzz if these otherwise redundant dbg.value+deref instructions are rare.

In practice I don't think there are any problems with this suggestion, but based on @jeremy's comment here https://bugs.llvm.org/show_bug.cgi?id=47946#c4 I'm not sure whether we should remove any dbg.value+derefs in the forward scan. What do you think?

I don't see it as incorrect to remove them. We currently only support that a variable is described by one location. So given a dbg.value or dbg.addr that says that binds a variable to a location we see it as that binding is valid until we find another dbg.value or dbg.addr that maps the variable to something different. Repeating the same dbg.value over and over again is not really adding any information (it just makes IR output longer and makes it more time consuming to iterate over the IR when not dealing with dbg-info).

But if this patch (leaving some dbg.value+deref) just before a call currently improve the debug experience I won't stop this patch. Just make it clear that the solution isn't bullet-proof. E.g. in case some pass inserts an instruction just before the call but after the dbg.value then the dbg.value may be removed. So it is a simple (cheap) solution to improve things in many situations, but generally speaking the problem could remain in some situations.

[Orlando]

Rebase

[Orlando]

Address feedback from @bjope:
+ Change comment for dbg.value+derefs in ShouldRemove lambda.
+ Update the test to check that the backward scan removes adjacent duplicate dbg.value+derefs still.

[Orlando]

Abandoning this old patch set; assignment tracking achieves a better result.

debuginfo-tests/dexter-tests/memvars/two-inlined-calls.c

-//// XFAIL:*
-//// RemoveRedundantDbgInstrs is removing the second dbg.value+DW_OP_deref.
-
 // REQUIRES: lldb
 // UNSUPPORTED: system-windows
 // RUN: %dexter --fail-lt 1.0 -w --debugger lldb \
 // RUN:     --builder clang-c  --cflags "-O2 -glldb" -- %s
 //
-//// The alloca 'param' uses can be promoted after inlining, and the final
-//// store to it is redundant and will be removed. Check that 'param' can still
-//// be read and has the expeted values throughout 'fun', and inlined calls to
-//// 'use'.
+//// See discussion here https://bugs.llvm.org/show_bug.cgi?id=47946#c3.  The
+//// alloca 'param' uses can be promoted after inlining, and the final store to
+//// it is redundant and will be removed. Check that 'param' can still be read
+//// and has the expected values throughout 'fun', and inlined calls to 'use'.
 
 int g;
 __attribute__((__always_inline__))
 static void use(int* p, int value) {
   g = *p;
   *p = value;
   volatile int step = 0;  // DexLabel('inlined')
 }

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

 ///
 /// then the instruction marked with (*) can be removed. Variable "x" is already
 /// described as being mapped to the SSA value X1.
 ///
 /// Possible improvements:
 /// - Keep track of non-overlapping fragments.
 static bool removeRedundantDbgInstrsUsingForwardScan(BasicBlock *BB) {
   SmallVector<DbgValueInst *, 8> ToBeRemoved;
-  DenseMap<DebugVariable, std::pair<Value *, DIExpression *> > VariableMap;
+  DenseMap<DebugVariable, std::pair<Value *, DIExpression *>> VariableMap;
+
+  auto ShouldRemove = [&](DebugVariable Var, const DbgValueInst *DVI) {
+    auto VMI = VariableMap.find(Var);
+    // Check if this is the first time we've encountered this variable.
+    if (VMI == VariableMap.end())
+      return false;
+    // Check if this is a new value for an existing variable.
+    if (VMI->second.first != DVI->getValue() ||
+        VMI->second.second != DVI->getExpression())
+      return false;
+    // The fix to PR47946 introduces InlineLowerDbgDeclare which scans
+    // backwards through debug intrinsics from inlined callsites to find the
+    // dbg.value+deref which LowerDbgDeclare may have inserted before calls. To
+    // improve the efficacy of the fix we avoid removing dbg.value+drefers
+    // here.
+    if (DVI->getExpression()->startsWithDeref())
+      return false;
+    return true;
+  };
+
   for (auto &I : *BB) {
     if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) {
-      DebugVariable Key(DVI->getVariable(),
-                        NoneType(),
+      DebugVariable Key(DVI->getVariable(), NoneType(),
                         DVI->getDebugLoc()->getInlinedAt());
-      auto VMI = VariableMap.find(Key);
-      // Update the map if we found a new value/expression describing the
-      // variable, or if the variable wasn't mapped already.
-      if (VMI == VariableMap.end() ||
-          VMI->second.first != DVI->getValue() ||
-          VMI->second.second != DVI->getExpression()) {
-        VariableMap[Key] = { DVI->getValue(), DVI->getExpression() };
-        continue;
-      }
-      // Found an identical mapping. Remember the instruction for later removal.
+      if (ShouldRemove(Key, DVI))
         ToBeRemoved.push_back(DVI);
+      else
+        VariableMap[Key] = {DVI->getValue(), DVI->getExpression()};
     }
   }
 
   for (auto &Instr : ToBeRemoved)
     Instr->eraseFromParent();
 
   return !ToBeRemoved.empty();
 }

llvm/test/DebugInfo/Generic/dont-remove-redundant-dbg-derefs.ll

+; RUN: opt -S -redundant-dbg-inst-elim %s | FileCheck %s
+
+;; See https://bugs.llvm.org/show_bug.cgi?id=47946#c3
+;; Check that RemoveRedundantDbgInstrs doesn't remove consecutive indirect
+;; dbg.value+derefs in the forward scan and that adjacent duplicates are
+;; still removed in the backwards scan.
+
+;; Generated from the following, with some metadata stripped out.
+;; $ clang test.c -O2 -g -Xclang -disable-llvm-passes -S -emit-llvm -o tmp.ll
+;; $ opt -S tmp.ll -o -instcombine
+;; $ cat test.c
+;; void use(int* p);
+;; void fun(int param) {
+;;   use(&param);
+;;   use(&param);
+;; }
+
+; CHECK: call void @llvm.dbg.value(metadata i32 %param, metadata ![[PARAM:[0-9]+]], metadata !DIExpression())
+; CHECK: call void @llvm.dbg.value(metadata i32* %param.addr, metadata ![[PARAM]], metadata !DIExpression(DW_OP_deref)
+;; Check that the adjacent duplicate
+; CHECK-NOT: call void @llvm.dbg.value(metadata i32* %param.addr, metadata ![[PARAM]], metadata !DIExpression(DW_OP_deref)
+; CHECK-NEXT: call void @use
+; CHECK: call void @llvm.dbg.value(metadata i32* %param.addr, metadata ![[PARAM]], metadata !DIExpression(DW_OP_deref)
+; CHECK-NEXT: call void @use
+; CHECK: ![[PARAM]] = !DILocalVariable(name: "param",
+
+define dso_local void @fun(i32 %param) !dbg !7 {
+entry:
+  %param.addr = alloca i32, align 4
+  call void @llvm.dbg.value(metadata i32 %param, metadata !12, metadata !DIExpression()), !dbg !13
+  store i32 %param, i32* %param.addr, align 4
+  call void @llvm.dbg.value(metadata i32* %param.addr, metadata !12, metadata !DIExpression(DW_OP_deref)), !dbg !13
+  ;; The following duplicate was added to check that it will still be removed by the backwards scan.
+  call void @llvm.dbg.value(metadata i32* %param.addr, metadata !12, metadata !DIExpression(DW_OP_deref)), !dbg !13
+  call void @use(i32* nonnull %param.addr), !dbg !18
+  call void @llvm.dbg.value(metadata i32* %param.addr, metadata !12, metadata !DIExpression(DW_OP_deref)), !dbg !13
+  call void @use(i32* nonnull %param.addr), !dbg !19
+  ret void, !dbg !20
+}
+
+declare !dbg !21 dso_local void @use(i32*)
+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 12.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+!1 = !DIFile(filename: "test.c", directory: "/")
+!2 = !{}
+!3 = !{i32 7, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{i32 1, !"wchar_size", i32 4}
+!6 = !{!"clang version 12.0.0"}
+!7 = distinct !DISubprogram(name: "fun", scope: !1, file: !1, line: 2, type: !8, scopeLine: 2, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !11)
+!8 = !DISubroutineType(types: !9)
+!9 = !{null, !10}
+!10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!11 = !{!12}
+!12 = !DILocalVariable(name: "param", arg: 1, scope: !7, file: !1, line: 2, type: !10)
+!13 = !DILocation(line: 0, scope: !7)
+!18 = !DILocation(line: 3, column: 3, scope: !7)
+!19 = !DILocation(line: 4, column: 3, scope: !7)
+!20 = !DILocation(line: 5, column: 1, scope: !7)
+!21 = !DISubprogram(name: "use", scope: !1, file: !1, line: 1, type: !22, flags: DIFlagPrototyped, spFlags: DISPFlagOptimized, retainedNodes: !2)
+!22 = !DISubroutineType(types: !23)
+!23 = !{null, !24}
+!24 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !10, size: 64)