[DebugInfo] Replace debug uses in replaceUsesOutsideBlock

[Orlando]

Summary

Value::replaceUsesOutsideBlock doesn't replace debug uses which leads to an
unnecessary reduction in variable location coverage. Fix this, add a unittest for
it, and add a regression test demonstrating the change through instcombine's
replacedSelectWithOperand.

[Orlando]

I wonder if it would be better update Value::replaceUsesWithIf instead, which would reach more code. Though that shape of that change might need some discussion. For instance, would we pass in the MetadataAsValue-ValueAsMetadata-Value debug uses to the predicate, or alternatively, have a a separate predicate for debug uses? wdyt?

Unrelated to my question, here are some fun stats for this patch since I have them to hand. llvm-locstats summary for RelWithDebInfo clang-3.4 built with clang main (@ 9c16621):

=================================================
-the number of debug variables processed: 2635805
-PC ranges covered: 66%
-------------------------------------------------
-total availability: 63%
=================================================

llvm-locstats summary for RelWithDebInfo clang-3.4 built with clang (@ 9c16621) with this patch applied:

=================================================
-the number of debug variables processed: 2655643 (+19,838)
-PC ranges covered: 66% (+1%)
-------------------------------------------------
-total availability: 64% (+1%)
=================================================

[Orlando]

Ping

[djtodoro]

Thanks for this! The results are amazing.

llvm/lib/IR/Value.cpp

556–562

Can we factor out this into a separate predicate?

llvm/test/DebugInfo/Generic/instcombine-replaced-select-with-operand.ll

109–112

I guess we don't need tbaa

[Orlando]

In D99169#2670983, @djtodoro wrote:

Thanks for this! The results are amazing.

Thanks for taking a look. And thanks to @jmorse for pointing out this bug to me offline!

llvm/lib/IR/Value.cpp

556–562

Just to check I understand - your suggestion is to change replaceUsesWithIf to accept a new additional predicate which handles these debug uses?

llvm/test/DebugInfo/Generic/instcombine-replaced-select-with-operand.ll

109–112

Probably not, I'll remove it in the next update.

[djtodoro]

llvm/lib/IR/Value.cpp

556–562

I vote either for extending the replaceUsesWithIf() or creating a separate static function that has this code.

[Orlando]

+ Remove tbaa metadata from lit test.
+ Fix clang-tidy warning in unittest.
+ Move the code into a new function replaceDbgUsesOutsideBlock.

Hi @djtodoro, is this what you meant?

Sorry for the delay, I was investigating what we could do with replaceUsesWithIf as an alternative. replaceUsesWithIf takes a predicate function which has a Use parameter. Looking at current replaceUsesWithIf call sites I noticed that most of the predicates actually only look at the Use's User rather than the Use itself. I came up with an overload (code below) which accepts a predicate with a User parameter rather than Use. This allows s to use that single predicate for both normal uses and llvm.dbg.* (metadata-as-value value-as-metadata) uses.

Existing replaceUsesWithIf declaration in Value.h:

void replaceUsesWithIf(Value *New, llvm::function_ref<bool(Use &U)> ShouldReplace)

New replaceUsesWithIf overload:

void Value::replaceUsesWithIf(
    Value *New, llvm::function_ref<bool(User *U)> ShouldReplaceIn) {
  assert(New && "Value::replaceUsesWithIf(<null>) is invalid!");
  assert(New->getType() == getType() &&
         "replaceUses of value with new value of different type!");
  SmallVector<User *> Users(users());
  for (auto *U : Users) {
    if (ShouldReplaceIn(U))
      U->replaceUsesOfWith(this, New);
  }
  SmallVector<DbgVariableIntrinsic *> DbgUsers;
  findDbgUsers(DbgUsers, this);
  for (auto *DVI : DbgUsers) {
    if (ShouldReplaceIn(DVI))
      DVI->replaceVariableLocationOp(this, New);
  }
}

Existing replaceUsesWithIf call sites can be updated to use the new User predicate, e.g. the change to this patch would be:

@@ -564,8 +555,9 @@ void Value::replaceUsesOutsideBlock(Value *New, BasicBlock *BB) {
          "replaceUses of value with new value of different type!");
   assert(BB && "Basic block that may contain a use of 'New' must be defined\n");
 
+  replaceUsesWithIf(New, [BB](User *U) {
+      auto *I = dyn_cast<Instruction>(U);
-  replaceDbgUsesOutsideBlock(this, New, BB);
-  replaceUsesWithIf(New, [BB](Use &U) {
-    auto *I = dyn_cast<Instruction>(U.getUser());
     // Don't replace if it's an instruction in the BB basic block.
     return !I || I->getParent() != BB;
   });

The benefit of this is that most replaceUsesWithIf calls can handle llvm.dbg.* updates with a minimal change. The downsides are that it touches more code, and creates a slightly confusing interface where one replaceUsesWithIf overload updates debug uses and the other does not. So, maybe it's better to keep the fix simple (the patch as it exists in review now) - I'm unsure. wdyt?

[djtodoro]

Thanks! LGTM like this...

(I vote for this simple code change rather than introducing this overloading, but please wait for couple of more days, so we can see if someone else has a different opinion.)

[Orlando]

In D99169#2678746, @djtodoro wrote:

Thanks! LGTM like this...

(I vote for this simple code change rather than introducing this overloading, but please wait for couple of more days, so we can see if someone else has a different opinion.)

Thanks @djtodoro. Sure, I will leave this up a few days before landing.

[Orlando]

In D99169#2683001, @Orlando wrote:

In D99169#2678746, @djtodoro wrote:

Thanks! LGTM like this...

(I vote for this simple code change rather than introducing this overloading, but please wait for couple of more days, so we can see if someone else has a different opinion.)

Thanks @djtodoro. Sure, I will leave this up a few days before landing.

I came to do this just now but noticed that this patch isn't "Accepted". @djtodoro is this intentional? I'm happy to wait for another reviewer if so but I just wanted to check.

[djtodoro]

LGTM from my side :)

[Orlando]

Thanks!

[Orlando]

Landing this tripped up some build bots (e.g. https://lab.llvm.org/buildbot/#/builders/109/builds/12664). I've created D100632 which should fix the issue iiuc.

[nikic]

Please either convert the llvm/test/DebugInfo/Generic/instcombine-replaced-select-with-operand.ll test to use opaque pointers, or delete it if it's not relevant anymore (the thing it currently tests is based on pointer bitcasts).

[Orlando]

In D99169#4246001, @nikic wrote:

Please either convert the llvm/test/DebugInfo/Generic/instcombine-replaced-select-with-operand.ll test to use opaque pointers, or delete it if it's not relevant anymore (the thing it currently tests is based on pointer bitcasts).

Done in 1a0653a80dee2b0db5fb44f50777153fb7690a4f. I just replaced the typed pointers with opaque pointers because that still stimulates the code-path we want to test here (I checked the test still fails when the code change is reverted). If that's weird or not in keeping, the next option is to regenerate from the source, and if that doesn't work then I think dropping the test wouldn't be the end of the world given we have unittest coverage of the underlying functionality.

[nikic]

In D99169#4246075, @Orlando wrote:

In D99169#4246001, @nikic wrote:

Please either convert the llvm/test/DebugInfo/Generic/instcombine-replaced-select-with-operand.ll test to use opaque pointers, or delete it if it's not relevant anymore (the thing it currently tests is based on pointer bitcasts).

Done in 1a0653a80dee2b0db5fb44f50777153fb7690a4f. I just replaced the typed pointers with opaque pointers because that still stimulates the code-path we want to test here (I checked the test still fails when the code change is reverted). If that's weird or not in keeping, the next option is to regenerate from the source, and if that doesn't work then I think dropping the test wouldn't be the end of the world given we have unittest coverage of the underlying functionality.

Thanks! I was mainly uncertain because the bitcast will now just get optimized away and not folded into the select or similar. But if this still covers the relevant codepath, that's great.

llvm/lib/IR/Value.cpp

 #include "llvm/IR/Operator.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/IR/ValueSymbolTable.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include <algorithm>
 
 using namespace llvm;
 
 static cl::opt<unsigned> UseDerefAtPointSemantics(
     "use-dereferenceable-at-point-semantics", cl::Hidden, cl::init(false),
     cl::desc("Deref attributes and metadata infer facts at definition only"));
 

 void Value::replaceAllUsesWith(Value *New) {
   doRAUW(New, ReplaceMetadataUses::Yes);
 }
 
 void Value::replaceNonMetadataUsesWith(Value *New) {
   doRAUW(New, ReplaceMetadataUses::No);
 }
 
+/// Replace llvm.dbg.* uses of MetadataAsValue(ValueAsMetadata(V)) outside BB
+/// with New.
+static void replaceDbgUsesOutsideBlock(Value *V, Value *New, BasicBlock *BB) {
+  SmallVector<DbgVariableIntrinsic *> DbgUsers;
+  findDbgUsers(DbgUsers, V);
+  for (auto *DVI : DbgUsers) {
+    if (DVI->getParent() != BB)
+      DVI->replaceVariableLocationOp(V, New);
+  }
+}
+
 // Like replaceAllUsesWith except it does not handle constants or basic blocks.
 // This routine leaves uses within BB.
 void Value::replaceUsesOutsideBlock(Value *New, BasicBlock *BB) {
   assert(New && "Value::replaceUsesOutsideBlock(<null>, BB) is invalid!");
   assert(!contains(New, this) &&
          "this->replaceUsesOutsideBlock(expr(this), BB) is NOT valid!");
   assert(New->getType() == getType() &&
          "replaceUses of value with new value of different type!");
   assert(BB && "Basic block that may contain a use of 'New' must be defined\n");
 
+  replaceDbgUsesOutsideBlock(this, New, BB);
   replaceUsesWithIf(New, [BB](Use &U) {
     auto *I = dyn_cast<Instruction>(U.getUser());
     // Don't replace if it's an instruction in the BB basic block.
     return !I || I->getParent() != BB;
   });
 }
 
 namespace {
 // Various metrics for how much to strip off of pointers.
 enum PointerStripKind {
   PSK_ZeroIndices,
   PSK_ZeroIndicesAndAliases,
   PSK_ZeroIndicesSameRepresentation,
   PSK_ForAliasAnalysis,

llvm/test/DebugInfo/Generic/instcombine-replaced-select-with-operand.ll

+; RUN: opt -instcombine -S %s | FileCheck %s
+
+;; Ensure that debug uses of a select are replaced when the select is replaced
+;; with one of its operands in InstCombine's replacedSelectWithOperand.
+
+;; Based on IR generated from this source, compiled with -O2 -g:
+;;
+;; extern void* glob;
+;; struct Thing {
+;;   void *ptr;
+;;   void *get() {return ptr;}
+;; };
+;; Thing *two(void *in) {
+;;   if ((long)in & 1)
+;;     return nullptr;
+;;   return static_cast<Thing *>(in);
+;; }
+;; void one() {
+;;   if (Thing *a = two(glob))
+;;     // Without the fix we lose 'this' (a) in the inlined call below.
+;;     glob = a->get();
+;; }
+
+;; Look at the instruction:
+;;     %retval.0.i = select i1 %tobool.not.i, %struct.Thing* %2, %struct.Thing* null
+;; Note that %2 is a bitcast of %0.
+;; InstCombine replaces the use of %retval.0.i in if.then with %0 because
+;; if.then is only branched to when retval.0.is not null. Ensure that debug use
+;; of %retval.0.i is also replaced with %0.
+
+; CHECK: if.then:
+; CHECK-NEXT: call void @llvm.dbg.value(metadata i8* %0, metadata ![[THIS:[0-9]+]], metadata !DIExpression())
+; CHECK: ![[THIS]] = !DILocalVariable(name: "this",
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.Thing = type { i8* }
+
+@glob = external dso_local local_unnamed_addr global i8*, align 8
+
+define dso_local void @_Z3onev() local_unnamed_addr !dbg !29 {
+entry:
+  %0 = load i8*, i8** @glob, align 8, !dbg !35
+  call void @llvm.dbg.value(metadata i8* %0, metadata !22, metadata !DIExpression()), !dbg !40
+  %1 = ptrtoint i8* %0 to i64, !dbg !42
+  %and.i = and i64 %1, 1, !dbg !43
+  %tobool.not.i = icmp eq i64 %and.i, 0, !dbg !42
+  %2 = bitcast i8* %0 to %struct.Thing*, !dbg !44
+  %retval.0.i = select i1 %tobool.not.i, %struct.Thing* %2, %struct.Thing* null, !dbg !44
+  call void @llvm.dbg.value(metadata %struct.Thing* %retval.0.i, metadata !33, metadata !DIExpression()), !dbg !45
+  %tobool.not = icmp eq %struct.Thing* %retval.0.i, null, !dbg !46
+  br i1 %tobool.not, label %if.end, label %if.then, !dbg !47
+
+if.then:                                          ; preds = %entry
+  call void @llvm.dbg.value(metadata %struct.Thing* %retval.0.i, metadata !48, metadata !DIExpression()), !dbg !51
+  %ptr.i = getelementptr inbounds %struct.Thing, %struct.Thing* %retval.0.i, i64 0, i32 0, !dbg !53
+  %3 = load i8*, i8** %ptr.i, align 8, !dbg !53
+  store i8* %3, i8** @glob, align 8, !dbg !56
+  br label %if.end, !dbg !57
+
+if.end:                                           ; preds = %if.then, %entry
+  ret void, !dbg !58
+}
+
+declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!14, !15, !16}
+!llvm.ident = !{!17}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, producer: "clang version 13.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, retainedTypes: !3, splitDebugInlining: false, nameTableKind: None)
+!1 = !DIFile(filename: "test.cpp", directory: "/")
+!2 = !{}
+!3 = !{!4, !5}
+!4 = !DIBasicType(name: "long int", size: 64, encoding: DW_ATE_signed)
+!5 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !6, size: 64)
+!6 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "Thing", file: !1, line: 2, size: 64, flags: DIFlagTypePassByValue, elements: !7, identifier: "_ZTS5Thing")
+!7 = !{!8, !10}
+!8 = !DIDerivedType(tag: DW_TAG_member, name: "ptr", scope: !6, file: !1, line: 3, baseType: !9, size: 64)
+!9 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: null, size: 64)
+!10 = !DISubprogram(name: "get", linkageName: "_ZN5Thing3getEv", scope: !6, file: !1, line: 4, type: !11, scopeLine: 4, flags: DIFlagPrototyped, spFlags: DISPFlagOptimized)
+!11 = !DISubroutineType(types: !12)
+!12 = !{!9, !13}
+!13 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !6, size: 64, flags: DIFlagArtificial | DIFlagObjectPointer)
+!14 = !{i32 7, !"Dwarf Version", i32 4}
+!15 = !{i32 2, !"Debug Info Version", i32 3}
+!16 = !{i32 1, !"wchar_size", i32 4}
+!17 = !{!"clang version 13.0.0"}
+!18 = distinct !DISubprogram(name: "two", linkageName: "_Z3twoPv", scope: !1, file: !1, line: 6, type: !19, scopeLine: 6, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !21)
+!19 = !DISubroutineType(types: !20)
+!20 = !{!5, !9}
+!21 = !{!22}
+!22 = !DILocalVariable(name: "in", arg: 1, scope: !18, file: !1, line: 6, type: !9)
+!23 = !DILocation(line: 0, scope: !18)
+!24 = !DILocation(line: 7, column: 7, scope: !25)
+!25 = distinct !DILexicalBlock(scope: !18, file: !1, line: 7, column: 7)
+!26 = !DILocation(line: 7, column: 16, scope: !25)
+!27 = !DILocation(line: 7, column: 7, scope: !18)
+!28 = !DILocation(line: 10, column: 1, scope: !18)
+!29 = distinct !DISubprogram(name: "one", linkageName: "_Z3onev", scope: !1, file: !1, line: 11, type: !30, scopeLine: 11, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !32)
+!30 = !DISubroutineType(types: !31)
+!31 = !{null}
+!32 = !{!33}
+!33 = !DILocalVariable(name: "a", scope: !34, file: !1, line: 12, type: !5)
+!34 = distinct !DILexicalBlock(scope: !29, file: !1, line: 12, column: 14)
+!35 = !DILocation(line: 12, column: 22, scope: !34)
+!40 = !DILocation(line: 0, scope: !18, inlinedAt: !41)
+!41 = distinct !DILocation(line: 12, column: 18, scope: !34)
+!42 = !DILocation(line: 7, column: 7, scope: !25, inlinedAt: !41)
+!43 = !DILocation(line: 7, column: 16, scope: !25, inlinedAt: !41)
+!44 = !DILocation(line: 7, column: 7, scope: !18, inlinedAt: !41)
+!45 = !DILocation(line: 0, scope: !34)
+!46 = !DILocation(line: 12, column: 14, scope: !34)
+!47 = !DILocation(line: 12, column: 14, scope: !29)
+!48 = !DILocalVariable(name: "this", arg: 1, scope: !49, type: !5, flags: DIFlagArtificial | DIFlagObjectPointer)
+!49 = distinct !DISubprogram(name: "get", linkageName: "_ZN5Thing3getEv", scope: !6, file: !1, line: 4, type: !11, scopeLine: 4, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, declaration: !10, retainedNodes: !50)
+!50 = !{!48}
+!51 = !DILocation(line: 0, scope: !49, inlinedAt: !52)
+!52 = distinct !DILocation(line: 14, column: 15, scope: !34)
+!53 = !DILocation(line: 4, column: 23, scope: !49, inlinedAt: !52)
+!56 = !DILocation(line: 14, column: 10, scope: !34)
+!57 = !DILocation(line: 14, column: 5, scope: !34)
+!58 = !DILocation(line: 15, column: 1, scope: !29)
+!59 = !DILocation(line: 0, scope: !49)
+!60 = !DILocation(line: 4, column: 23, scope: !49)
+!61 = !DILocation(line: 4, column: 16, scope: !49)

llvm/unittests/IR/ValueTest.cpp

 //===- llvm/unittest/IR/ValueTest.cpp - Value unit tests ------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/Value.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/Function.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/ModuleSlotTracker.h"
 #include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
 using namespace llvm;
 
 namespace {
TEST(ValueTest, getLocalSlotDeath) {
   BasicBlock *BB2 = &*++F->begin();
   ASSERT_TRUE(BB2);
 
   ModuleSlotTracker MST(M.get());
   EXPECT_DEATH(MST.getLocalSlot(BB2), "No function incorporated");
 }
 #endif
 
+TEST(ValueTest, replaceUsesOutsideBlock) {
+  // Check that Value::replaceUsesOutsideBlock(New, BB) replaces uses outside
+  // BB, including dbg.* uses of MetadataAsValue(ValueAsMetadata(this)).
+  const auto *IR = R"(
+    define i32 @f() !dbg !6 {
+    entry:
+      %a = add i32 0, 1, !dbg !15
+      %b = add i32 0, 2, !dbg !15
+      %c = add i32 %a, 2, !dbg !15
+      call void @llvm.dbg.value(metadata i32 %a, metadata !9, metadata !DIExpression()), !dbg !15
+      br label %exit, !dbg !15
+
+    exit:
+      call void @llvm.dbg.value(metadata i32 %a, metadata !11, metadata !DIExpression()), !dbg !16
+      ret i32 %a, !dbg !16
+    }
+
+    declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+    !llvm.dbg.cu = !{!0}
+    !llvm.module.flags = !{!5}
+
+    !0 = distinct !DICompileUnit(language: DW_LANG_C, file: !1, producer: "debugify", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+    !1 = !DIFile(filename: "test.ll", directory: "/")
+    !2 = !{}
+    !5 = !{i32 2, !"Debug Info Version", i32 3}
+    !6 = distinct !DISubprogram(name: "f", linkageName: "f", scope: null, file: !1, line: 1, type: !7, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: true, unit: !0, retainedNodes: !8)
+    !7 = !DISubroutineType(types: !2)
+    !8 = !{!9, !11}
+    !9 = !DILocalVariable(name: "1", scope: !6, file: !1, line: 1, type: !10)
+    !10 = !DIBasicType(name: "ty32", size: 32, encoding: DW_ATE_signed)
+    !11 = !DILocalVariable(name: "2", scope: !6, file: !1, line: 2, type: !12)
+    !12 = !DIBasicType(name: "ty64", size: 64, encoding: DW_ATE_signed)
+    !15 = !DILocation(line: 1, column: 1, scope: !6)
+    !16 = !DILocation(line: 5, column: 1, scope: !6)
+  )";
+  LLVMContext Ctx;
+  SMDiagnostic Err;
+  std::unique_ptr<Module> M = parseAssemblyString(IR, Err, Ctx);
+  if (!M)
+    Err.print("ValueTest", errs());
+
+  auto GetNext = [](auto *I) { return &*++I->getIterator(); };
+
+  Function *F = M->getFunction("f");
+  // Entry.
+  BasicBlock *Entry = &F->front();
+  Instruction *A = &Entry->front();
+  Instruction *B = GetNext(A);
+  Instruction *C = GetNext(B);
+  auto *EntryDbg = cast<DbgValueInst>(GetNext(C));
+  // Exit.
+  BasicBlock *Exit = GetNext(Entry);
+  auto *ExitDbg = cast<DbgValueInst>(&Exit->front());
+  Instruction *Ret = GetNext(ExitDbg);
+
+  A->replaceUsesOutsideBlock(B, Entry);
+  // These users are in Entry so shouldn't be changed.
+  ASSERT_TRUE(C->getOperand(0) == cast<Value>(A));
+  ASSERT_TRUE(EntryDbg->getValue(0) == cast<Value>(A));
+  // These users are outside Entry so should be changed.
+  ASSERT_TRUE(ExitDbg->getValue(0) == cast<Value>(B));
+  ASSERT_TRUE(Ret->getOperand(0) == cast<Value>(B));
+}
 } // end anonymous namespace