[Assignment Tracking][11/*] Update RemoveRedundantDbgInstrs

[Orlando]

Summary

Update the RemoveRedundantDbgInstrs utility to avoid sometimes losing information when deleting dbg.assign intrinsics.

removeRedundantDbgInstrsUsingBackwardScan - treat dbg.assign intrinsics that are not linked to any instruction just like dbg.values. That is, in a block of contiguous debug intrinsics, delete all other than the last definition for a fragment. Leave linked dbg.assign intrinsics in place.

removeRedundantDbgInstrsUsingForwardScan - this function has two changes. First, undef and unlinked dbg.assign intrinsics encountered in the entry block before any non-undef non-unlinked intrinsics for a given fragment are deleted. Second, don't delete linked dbg.assign intrinsics and don't the next intrinsic found even if it would otherwise be eligible for deletion.

[jmorse]

If I understand the logic in the forward scan correctly, whenever you see a linked dbg.assign, you will _always_ keep the next debug intrinsic for that variable, because the expression is nullptr. The next debug intrinsic then resets the map, so if it's a dbg-value-like intrinsic, subsequent dbg-value-like intrinsics will be removed as redundant.

I can sort of see why this is necessary (moving a variable from "linked" to "not linked" is a meaningful transition that we shouldn't remove), is there a definite use case for it, and is it covered by the test? (I don't see it being covered by the test, but I might not have read it correctly).

As annoying as this is: the codepaths using SeenDefForAggregate should be tested by the test too, it'll make it easier for me to grasp what's going on.

llvm/test/DebugInfo/Generic/assignment-tracking/remove-redundant.ll

18–19

... in the entry block, being the important feature, no?

51–55

Deliberately identical to lines 44 -> 48?

[Orlando]

If I understand the logic in the forward scan correctly, whenever you see a linked dbg.assign, you will _always_ keep the next debug intrinsic for that variable, because the expression is nullptr. The next debug intrinsic then resets the map, so if it's a dbg-value-like intrinsic, subsequent dbg-value-like intrinsics will be removed as redundant.

I can sort of see why this is necessary (moving a variable from "linked" to "not linked" is a meaningful transition that we shouldn't remove), is there a definite use case for it, and is it covered by the test? (I don't see it being covered by the test, but I might not have read it correctly).

Yeah that's right. I thought I had covered it in the tests but looking again I think you're right.

is there a definite use case for it?

This is a good question - I think so, but I tried to come up with a source reproducer and failed to do so quickly. I'll need to think about this one some more.

llvm/test/DebugInfo/Generic/assignment-tracking/remove-redundant.ll

18–19

Yes for sure, I'll add that to the comment.

51–55

Yeah - the comments don't make it particularly clear or obvious but the difference is that the shadowing intrinsic is a dbg.value in the first check and a dbg.assign in the second.

;; redundant by the previous dbg.value is removed.

;; redundant by the previous dbg.assign is removed.

I can improve the wording there to make it clearer.

57–60

This demonstrates the SeenDefForAggregate path - we're in the entry block and this is a unlinked and undef dbg.assign (so far it's a candidate for removal). We don't want to remove it though because we've already seen non-undef or non-unlinked intrinsic for the same variable.

Essentially, scanning forwards, we can only remove an undef unlinked dbg.assign from entry block iff we've not already seen a def for the variable.

[Orlando]

I can sort of see why this is necessary (moving a variable from "linked" to "not linked" is a meaningful transition that we shouldn't remove), is there a definite use case for it, and is it covered by the test? (I don't see it being covered by the test, but I might not have read it correctly).

I've added remove-redundant-fwd-scan-linked.ll which is a test case reduced from real code. Note, this IR was generated using the (updated) DSE insert-undef behaviour in D133315.

[Orlando]

+ Improve the new test by checking DIAssignID instances are unique.

(Sorry for the double-update)

[jmorse]

LGTM. Due diligence: is there a scenario you can think of where there would be meaningful difference in the generated debug-info if the tested-for dbg.assign in remove-redundant-fwd-scan-linked.ll were dropped? As mentioned it feels like a meaningful transition (linked -> unlinked), but I can't put my finger on exactly what it means.

llvm/test/DebugInfo/Generic/assignment-tracking/remove-redundant.ll

19

[Orlando]

+ Separate out the entry-block-undef-removal into it's own scan, in line with @StephenTozer 's comments in D136321.
+ Rebase.
+ Switch to opaque pointers in tests.

[jmorse]

LGTM with some cosmetic nits.

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

436

Probably wants a comment to summarise the purpose, i.e., "dbg.assigns with no linked instructions can be...". I know there's a similar comment below, but IMO it makes more sense to put that comment up here.

500

Early-continue better than indentation IMO.

509

Best to be 100% explicit -- push DAI, and change the type of the container to be DbgAssignInst?

515

Nit, auto * rather than a reference to the pointer? I vaguely recall some past compilers issuing diagnostics about this.

[Orlando]

Done - thanks!

[StephenTozer]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

391–392

[Orlando]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

391–392

I think the continue is correct (this isn't the end of the loop, it's inside the if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) block) - continue because we're still in a block of consecutive dbg intrinsics.

[StephenTozer]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

391–392

Ah, my bad - just misread it! LGTM.

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
static bool removeRedundantDbgInstrsUsingBackwardScan(BasicBlock *BB) {
   SmallVector<DbgValueInst *, 8> ToBeRemoved;
   SmallDenseSet<DebugVariable> VariableSet;
   for (auto &I : reverse(*BB)) {
     if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) {
       DebugVariable Key(DVI->getVariable(),
                         DVI->getExpression(),
                         DVI->getDebugLoc()->getInlinedAt());
       auto R = VariableSet.insert(Key);
+      // If the variable fragment hasn't been seen before then we don't want
+      // to remove this dbg intrinsic.
+      if (R.second)
+        continue;
+
+      if (auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI)) {
+        // Don't delete dbg.assign intrinsics that are linked to instructions.
+        if (!at::getAssignmentInsts(DAI).empty())
+          continue;
+        // Unlinked dbg.assign intrinsics can be treated like dbg.values.
+      }
+
       // If the same variable fragment is described more than once it is enough
       // to keep the last one (i.e. the first found since we for reverse
       // iteration).
-      if (!R.second)
-        ToBeRemoved.push_back(DVI);
       continue;
     }
     // Sequence with consecutive dbg.value instrs ended. Clear the map to
     // restart identifying redundant instructions if case we find another
     // dbg.value sequence.
     VariableSet.clear();
   }
 
   for (auto &Instr : ToBeRemoved)
static bool removeRedundantDbgInstrsUsingForwardScan(BasicBlock *BB) {
   DenseMap<DebugVariable, std::pair<SmallVector<Value *, 4>, DIExpression *>>
       VariableMap;
   for (auto &I : *BB) {
     if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) {
       DebugVariable Key(DVI->getVariable(),
                         NoneType(),
                         DVI->getDebugLoc()->getInlinedAt());
       auto VMI = VariableMap.find(Key);
+      auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI);
+      // A dbg.assign with no linked instructions can be treated like a
+      // dbg.value (i.e. can be deleted).
+      bool IsDbgValueKind = (!DAI || at::getAssignmentInsts(DAI).empty());
+
       // Update the map if we found a new value/expression describing the
       // variable, or if the variable wasn't mapped already.
       SmallVector<Value *, 4> Values(DVI->getValues());
       if (VMI == VariableMap.end() || VMI->second.first != Values ||
           VMI->second.second != DVI->getExpression()) {
+        // Use a sentinal value (nullptr) for the DIExpression when we see a
+        // linked dbg.assign so that the next debug intrinsic will never match
+        // it (i.e. always treat linked dbg.assigns as if they're unique).
+        if (IsDbgValueKind)
           VariableMap[Key] = {Values, DVI->getExpression()};
+        else
+          VariableMap[Key] = {Values, nullptr};
         continue;
       }
-      // Found an identical mapping. Remember the instruction for later removal.
+
+      // Don't delete dbg.assign intrinsics that are linked to instructions.
+      if (!IsDbgValueKind)
+        continue;
       ToBeRemoved.push_back(DVI);
     }
   }
 
   for (auto &Instr : ToBeRemoved)
     Instr->eraseFromParent();
 
   return !ToBeRemoved.empty();
 }
 
+/// Remove redundant undef dbg.assign intrinsic from an entry block using a
+/// forward scan.
+/// Strategy:
+/// ---------------------
+/// Scanning forward, delete dbg.assign intrinsics iff they are undef, not
+/// linked to an intrinsic, and don't share an aggregate variable with a debug
+/// intrinsic that didn't meet the criteria. In other words, undef dbg.assigns
+/// that come before non-undef debug intrinsics for the variable are
+/// deleted. Given:
+///
+///   dbg.assign undef, "x", FragmentX1 (*)
+///   <block of instructions, none being "dbg.value ..., "x", ...">
+///   dbg.value %V, "x", FragmentX2
+///   <block of instructions, none being "dbg.value ..., "x", ...">
+///   dbg.assign undef, "x", FragmentX1
+///
+/// then (only) the instruction marked with (*) can be removed.
+/// Possible improvements:
+/// - Keep track of non-overlapping fragments.
+static bool remomveUndefDbgAssignsFromEntryBlock(BasicBlock *BB) {
+  assert(BB->isEntryBlock() && "expected entry block");
+  SmallVector<DbgAssignIntrinsic *, 8> ToBeRemoved;
+  DenseSet<DebugVariable> SeenDefForAggregate;
+  // Returns the DebugVariable for DVI with no fragment info.
+  auto GetAggregateVariable = [](DbgValueInst *DVI) {
+    return DebugVariable(DVI->getVariable(), NoneType(),
+                         DVI->getDebugLoc()->getInlinedAt());
+  };
+
+  // Remove undef dbg.assign intrinsics that are encountered before
+  // any non-undef intrinsics from the entry block.
+  for (auto &I : *BB) {
+    DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I);
+    if (!DVI)
+      continue;
+    auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI);
+    bool IsDbgValueKind = (!DAI || at::getAssignmentInsts(DAI).empty());
+    DebugVariable Aggregate = GetAggregateVariable(DVI);
+    if (!SeenDefForAggregate.contains(Aggregate)) {
+      bool IsUndef = DVI->isUndef() && IsDbgValueKind;
+      if (!IsUndef) {
+        SeenDefForAggregate.insert(Aggregate);
+      } else if (DAI) {
+        ToBeRemoved.push_back(DAI);
+      }
+    }
+  }
+
+  for (DbgAssignIntrinsic *DAI : ToBeRemoved)
+    DAI->eraseFromParent();
+
+  return !ToBeRemoved.empty();
+}
+
 bool llvm::RemoveRedundantDbgInstrs(BasicBlock *BB) {
   bool MadeChanges = false;
   // By using the "backward scan" strategy before the "forward scan" strategy we
   // can remove both dbg.value (2) and (3) in a situation like this:
   //
   //   (1) dbg.value V1, "x", DIExpression()
   //       ...
   //   (2) dbg.value V2, "x", DIExpression()
   //   (3) dbg.value V1, "x", DIExpression()
   //
   // The backward scan will remove (2), it is made obsolete by (3). After
   // getting (2) out of the way, the foward scan will remove (3) since "x"
   // already is described as having the value V1 at (1).
   MadeChanges |= removeRedundantDbgInstrsUsingBackwardScan(BB);
+  if (BB->isEntryBlock() && getEnableAssignmentTracking())
+    MadeChanges |= remomveUndefDbgAssignsFromEntryBlock(BB);
   MadeChanges |= removeRedundantDbgInstrsUsingForwardScan(BB);
 
   if (MadeChanges)
     LLVM_DEBUG(dbgs() << "Removed redundant dbg instrs from: "
                       << BB->getName() << "\n");
   return MadeChanges;
 }
 

llvm/test/DebugInfo/Generic/assignment-tracking/remove-redundant-fwd-scan-linked.ll

+; RUN: opt -passes=redundant-dbg-inst-elim -S %s -o - -experimental-assignment-tracking \
+; RUN: | FileCheck %s --implicit-check-not="call void @llvm.dbg"
+
+;; $ cat -n reduce.c
+;;  1 void ext();
+;;  2 typedef struct {
+;;  3   short *a;
+;;  4   char *b;
+;;  5 } c;
+;;  6 char d;
+;;  7 void f();
+;;  8 typedef struct {
+;;  9   c decoder;
+;; 10 } e;
+;; 11 void g() {
+;; 12   e a;
+;; 13   (&(&a)->decoder)->b = 0;
+;; 14   (&(&a)->decoder)->a = 0;
+;; 15   ext();
+;; 16   a.decoder.b = &d;
+;; 17   f(&a);
+;; 18 }
+
+;; clang -O2 -g -Xclang -fexperiemental-assignment-tracking:
+;;
+;; MemCpyOptPass: Aggregate scalar stores from line 13 and 14 into memset.
+;; DSE: Shorten aggregated store because field 'b' is re-assigned later.
+;;      Insert an unlinked dbg.assign after the dbg.assign describing
+;;      the fragment for field 'b', which is still linked to the memset.
+;;
+;; Check we don't delete that inserted unlinked dbg.assign.
+
+; CHECK:      %a = alloca %struct.e, align 8, !DIAssignID ![[ID_0:[0-9]+]]
+; CHECK-NEXT: call void @llvm.dbg.assign({{.*}}, metadata ![[ID_0]],{{.*}})
+
+;; This dbg.assign is linked to the memset.
+; CHECK:      call void @llvm.dbg.assign(metadata ptr null,{{.*}}, metadata !DIExpression(DW_OP_LLVM_fragment, 64, 64), metadata ![[ID_1:[0-9]+]], metadata ptr %b, metadata !DIExpression())
+
+;; Importantly, check this unlinked dbg.assign which is shadowed by the
+;; dbg.assign above isn't deleted.
+; CHECK-NEXT: call void @llvm.dbg.assign(metadata ptr null,{{.*}}, metadata !DIExpression(DW_OP_LLVM_fragment, 64, 64), metadata ![[ID_2:[0-9]+]], metadata ptr undef, metadata !DIExpression())
+
+; CHECK:      call void @llvm.dbg.assign(metadata ptr null,{{.*}}, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 64), metadata ![[ID_1]], metadata ptr %a2, metadata !DIExpression())
+
+; CHECK:      call void @llvm.memset{{.*}}, !DIAssignID ![[ID_1]]
+
+; CHECK:      store ptr @d, ptr %b, align 8,{{.*}}!DIAssignID ![[ID_3:[0-9]+]]
+; CHECK-NEXT: call void @llvm.dbg.assign(metadata ptr @d,{{.*}}, metadata !DIExpression(DW_OP_LLVM_fragment, 64, 64), metadata ![[ID_3]], metadata ptr %b, metadata !DIExpression())
+
+; CHECK-DAG: ![[ID_0]] = distinct !DIAssignID()
+; CHECK-DAG: ![[ID_1]] = distinct !DIAssignID()
+; CHECK-DAG: ![[ID_2]] = distinct !DIAssignID()
+; CHECK-DAG: ![[ID_3]] = distinct !DIAssignID()
+
+%struct.e = type { %struct.c }
+%struct.c = type { ptr, ptr }
+
+@d = dso_local global i8 0, align 1, !dbg !0
+
+define dso_local void @g() local_unnamed_addr #0 !dbg !12 {
+entry:
+  %a = alloca %struct.e, align 8, !DIAssignID !29
+  call void @llvm.dbg.assign(metadata i1 undef, metadata !16, metadata !DIExpression(), metadata !29, metadata ptr %a, metadata !DIExpression()), !dbg !30
+  call void @llvm.lifetime.start.p0i8(i64 16, ptr nonnull %a) #5, !dbg !31
+  %b = getelementptr inbounds %struct.e, ptr %a, i64 0, i32 0, i32 1, !dbg !32
+  call void @llvm.dbg.assign(metadata ptr null, metadata !16, metadata !DIExpression(DW_OP_LLVM_fragment, 64, 64), metadata !33, metadata ptr %b, metadata !DIExpression()), !dbg !30
+  call void @llvm.dbg.assign(metadata ptr null, metadata !16, metadata !DIExpression(DW_OP_LLVM_fragment, 64, 64), metadata !34, metadata ptr undef, metadata !DIExpression()), !dbg !30
+  %a2 = getelementptr inbounds %struct.e, ptr %a, i64 0, i32 0, i32 0, !dbg !35
+  call void @llvm.dbg.assign(metadata ptr null, metadata !16, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 64), metadata !33, metadata ptr %a2, metadata !DIExpression()), !dbg !30
+  call void @llvm.memset.p0i8.i64(ptr align 8 %a2, i8 0, i64 8, i1 false), !dbg !35, !DIAssignID !33
+  tail call void (...) @ext() #5, !dbg !36
+  store ptr @d, ptr %b, align 8, !dbg !37, !DIAssignID !44
+  call void @llvm.dbg.assign(metadata ptr @d, metadata !16, metadata !DIExpression(DW_OP_LLVM_fragment, 64, 64), metadata !44, metadata ptr %b, metadata !DIExpression()), !dbg !30
+  call void @llvm.lifetime.end.p0i8(i64 16, ptr nonnull %a) #5, !dbg !46
+  ret void, !dbg !46
+}
+
+declare void @llvm.lifetime.start.p0i8(i64 immarg, ptr nocapture) #1
+declare !dbg !47 dso_local void @ext(...) local_unnamed_addr #2
+declare dso_local void @f(...) local_unnamed_addr #2
+declare void @llvm.lifetime.end.p0i8(i64 immarg, ptr nocapture) #1
+declare void @llvm.dbg.assign(metadata, metadata, metadata, metadata, metadata, metadata) #3
+declare void @llvm.memset.p0i8.i64(ptr nocapture writeonly, i8, i64, i1 immarg) #4
+
+!llvm.dbg.cu = !{!2}
+!llvm.module.flags = !{!6, !7, !8, !9, !10}
+!llvm.ident = !{!11}
+
+!0 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression())
+!1 = distinct !DIGlobalVariable(name: "d", scope: !2, file: !3, line: 6, type: !5, isLocal: false, isDefinition: true)
+!2 = distinct !DICompileUnit(language: DW_LANG_C99, file: !3, producer: "clang version 16.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, globals: !4, splitDebugInlining: false, nameTableKind: None)
+!3 = !DIFile(filename: "reduce.c", directory: "/")
+!4 = !{!0}
+!5 = !DIBasicType(name: "char", size: 8, encoding: DW_ATE_signed_char)
+!6 = !{i32 7, !"Dwarf Version", i32 5}
+!7 = !{i32 2, !"Debug Info Version", i32 3}
+!8 = !{i32 1, !"wchar_size", i32 4}
+!9 = !{i32 7, !"uwtable", i32 1}
+!10 = !{i32 7, !"frame-pointer", i32 2}
+!11 = !{!"clang version 14.0.0"}
+!12 = distinct !DISubprogram(name: "g", scope: !3, file: !3, line: 11, type: !13, scopeLine: 11, flags: DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !2, retainedNodes: !15)
+!13 = !DISubroutineType(types: !14)
+!14 = !{null}
+!15 = !{!16}
+!16 = !DILocalVariable(name: "a", scope: !12, file: !3, line: 12, type: !17)
+!17 = !DIDerivedType(tag: DW_TAG_typedef, name: "e", file: !3, line: 10, baseType: !18)
+!18 = distinct !DICompositeType(tag: DW_TAG_structure_type, file: !3, line: 8, size: 128, elements: !19)
+!19 = !{!20}
+!20 = !DIDerivedType(tag: DW_TAG_member, name: "decoder", scope: !18, file: !3, line: 9, baseType: !21, size: 128)
+!21 = !DIDerivedType(tag: DW_TAG_typedef, name: "c", file: !3, line: 5, baseType: !22)
+!22 = distinct !DICompositeType(tag: DW_TAG_structure_type, file: !3, line: 2, size: 128, elements: !23)
+!23 = !{!24, !27}
+!24 = !DIDerivedType(tag: DW_TAG_member, name: "a", scope: !22, file: !3, line: 3, baseType: !25, size: 64)
+!25 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !26, size: 64)
+!26 = !DIBasicType(name: "short", size: 16, encoding: DW_ATE_signed)
+!27 = !DIDerivedType(tag: DW_TAG_member, name: "b", scope: !22, file: !3, line: 4, baseType: !28, size: 64, offset: 64)
+!28 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !5, size: 64)
+!29 = distinct !DIAssignID()
+!30 = !DILocation(line: 0, scope: !12)
+!31 = !DILocation(line: 12, scope: !12)
+!32 = !DILocation(line: 13, scope: !12)
+!33 = distinct !DIAssignID()
+!34 = distinct !DIAssignID()
+!35 = !DILocation(line: 14, scope: !12)
+!36 = !DILocation(line: 15, scope: !12)
+!37 = !DILocation(line: 16, scope: !12)
+!44 = distinct !DIAssignID()
+!45 = !DILocation(line: 17, scope: !12)
+!46 = !DILocation(line: 18, scope: !12)
+!47 = !DISubprogram(name: "ext", scope: !3, file: !3, line: 1, type: !13, spFlags: DISPFlagOptimized, retainedNodes: !48)
+!48 = !{}

llvm/test/DebugInfo/Generic/assignment-tracking/remove-redundant.ll

+; RUN: opt -passes=redundant-dbg-inst-elim -S %s -o - -experimental-assignment-tracking \
+; RUN: | FileCheck %s --implicit-check-not="call void @llvm.dbg"
+
+;; Hand-written. Test how RemoveRedundantDbgInstrs interacts with dbg.assign
+;; intrinsics. FileCehck directives are inline.
+
+define dso_local void @_Z1fv() !dbg !7 {
+entry:
+  %test = alloca i32, align 4, !DIAssignID !20
+; CHECK: alloca
+;; Forward scan: This dbg.assign for Local2 contains an undef value component
+;; in the entry block and is the first debug intrinsic for the variable, but is
+;; linked to an instruction so should not be deleted.
+; CHECK-NEXT: call void @llvm.dbg.assign(metadata i1 undef, metadata ![[Local2:[0-9]+]]
+  call void @llvm.dbg.assign(metadata i1 undef, metadata !19, metadata !DIExpression(), metadata !20, metadata ptr %test, metadata !DIExpression()), !dbg !14
+
+;; Forward scan: dbg.assign for Local unlinked with undef value component, in
+;; the enrty bock and seen before any non-undefs; delete it.
+; CHECK-NEXT: @step()
+  call void @llvm.dbg.assign(metadata i32 undef, metadata !11, metadata !DIExpression(), metadata !15, metadata ptr undef, metadata !DIExpression()), !dbg !14
+  call void @step()
+
+;; Forward scan: Repeat the previous test to check it works more than once.
+; CHECK-NEXT: @step()
+  call void @llvm.dbg.assign(metadata i32 undef, metadata !11, metadata !DIExpression(), metadata !15, metadata ptr undef, metadata !DIExpression()), !dbg !14
+  call void @step()
+
+;; Backward scan: Check that a dbg.value made redundant by a dbg.assign is
+;; removed.
+;; CHECK-NEXT: call void @llvm.dbg.assign(metadata i32 1, metadata ![[Local:[0-9]+]]
+;; CHECK-NEXT: @step()
+  call void @llvm.dbg.value(metadata i32 0, metadata !11, metadata !DIExpression()), !dbg !14
+  call void @llvm.dbg.assign(metadata i32 1, metadata !11, metadata !DIExpression(), metadata !15, metadata ptr undef, metadata !DIExpression()), !dbg !14
+  call void @step()
+
+;; Backward scan: Check that a dbg.assign made redundant by a dbg.value is
+;; removed.
+;; CHECK-NEXT: call void @llvm.dbg.value(metadata i32 3, metadata ![[Local:[0-9]+]]
+;; CHECK-NEXT: @step()
+  call void @llvm.dbg.assign(metadata i32 2, metadata !11, metadata !DIExpression(), metadata !15, metadata ptr undef, metadata !DIExpression()), !dbg !14
+  call void @llvm.dbg.value(metadata i32 3, metadata !11, metadata !DIExpression()), !dbg !14
+  call void @step()
+
+;; Forward scan: This unlinked dbg.assign(3, ...) is shadowed by the
+;; dbg.value(3,...) above. Check it is removed.
+;; CHECK-NEXT: @step()
+  call void @llvm.dbg.assign(metadata i32 3, metadata !11, metadata !DIExpression(), metadata !15, metadata ptr undef, metadata !DIExpression()), !dbg !14
+  call void @step()
+
+;; Forward scan: Same as above except this dbg.assign is shadowed by
+;; another dbg.assign rather than a dbg.value. Check it is removed.
+;; CHECK-NEXT: @step()
+  call void @llvm.dbg.assign(metadata i32 3, metadata !11, metadata !DIExpression(), metadata !15, metadata ptr undef, metadata !DIExpression()), !dbg !14
+  call void @step()
+
+;; Forward scan: We've seen non-undef dbg intrinsics for Local in the entry
+;; block so we shouldn't delete this undef.
+; CHECK-NEXT: call void @llvm.dbg.assign(metadata i32 undef, metadata ![[Local]]
+  call void @llvm.dbg.assign(metadata i32 undef, metadata !11, metadata !DIExpression(), metadata !15, metadata ptr undef, metadata !DIExpression()), !dbg !14
+  br label %next
+
+next:
+;; Forward scan: Do not delete undef dbg.assigns from non-entry blocks.
+; CHECK: call void @llvm.dbg.assign(metadata i32 undef, metadata ![[Local2]]
+; CHECK-NEXT: @step()
+  call void @llvm.dbg.assign(metadata i32 undef, metadata !19, metadata !DIExpression(), metadata !21, metadata ptr %test, metadata !DIExpression()), !dbg !14
+  call void @step()
+
+;; Forward scan: The next dbg.assign would be made redundant by this dbg.value
+;; if it were not for the fact that it is linked to an instruction. Ensure it
+;; isn't removed.
+;; Backward scan: It (the next dbg.assign) is also followed by another for the
+;; same variable - check it isn't remove (because it's linked).
+; CHECK-NEXT: call void @llvm.dbg.value(metadata i32 0, metadata ![[Local2]]
+; CHECK-NEXT: store
+; CHECK-NEXT: store
+; CHECK-NEXT: call void @llvm.dbg.assign(metadata i32 0, metadata ![[Local2]]
+; CHECK-NEXT: call void @llvm.dbg.assign(metadata i32 1, metadata ![[Local2]]
+  call void @llvm.dbg.value(metadata i32 0, metadata !19, metadata !DIExpression()), !dbg !14
+  store i32 0, ptr %test, !DIAssignID !17
+  store i32 1, ptr %test, !DIAssignID !16
+  call void @llvm.dbg.assign(metadata i32 0, metadata !19, metadata !DIExpression(), metadata !17, metadata ptr %test, metadata !DIExpression()), !dbg !14
+  call void @llvm.dbg.assign(metadata i32 1, metadata !19, metadata !DIExpression(), metadata !16, metadata ptr %test, metadata !DIExpression()), !dbg !14
+  ret void, !dbg !18
+}
+
+; CHECK-DAG: ![[Local2]] = !DILocalVariable(name: "Local2",
+; CHECK-DAG: ![[Local]] = !DILocalVariable(name: "Local",
+
+declare dso_local void @step()
+declare void @llvm.dbg.assign(metadata, metadata, metadata, metadata, metadata, metadata)
+declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!2, !3, !4, !5}
+!llvm.ident = !{!6}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, producer: "clang version 14.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, splitDebugInlining: false, nameTableKind: None)
+!1 = !DIFile(filename: "test.cpp", directory: "/")
+!2 = !{i32 7, !"Dwarf Version", i32 5}
+!3 = !{i32 2, !"Debug Info Version", i32 3}
+!4 = !{i32 1, !"wchar_size", i32 4}
+!5 = !{i32 7, !"uwtable", i32 1}
+!6 = !{!"clang version 14.0.0"}
+!7 = distinct !DISubprogram(name: "f", linkageName: "_Z1fv", scope: !1, file: !1, line: 1, type: !8, scopeLine: 1, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !10)
+!8 = !DISubroutineType(types: !9)
+!9 = !{null}
+!10 = !{!11, !19}
+!11 = !DILocalVariable(name: "Local", scope: !7, file: !1, line: 2, type: !12)
+!12 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!13 = distinct !DIAssignID()
+!14 = !DILocation(line: 0, scope: !7)
+!15 = distinct !DIAssignID()
+!16 = distinct !DIAssignID()
+!17 = distinct !DIAssignID()
+!18 = !DILocation(line: 6, column: 1, scope: !7)
+!19 = !DILocalVariable(name: "Local2", scope: !7, file: !1, line: 2, type: !12)
+!20 = distinct !DIAssignID()
+!21 = distinct !DIAssignID()