[Assignment Tracking] Improve removeRedundantDbgLocsUsingBackwardScan

[Orlando]

Summary

removeRedundantDbgLocsUsingBackwardScan removes redundant dbg loc definitions by scanning backwards through contiguous sets of them (a "wedge"), removing earlier (in IR order terms) defs for fragments of variables that are defined later in the wedge.

In this patch we use a Bitvector for each variable to track which bits have definitions to more accurately determine whether a loc def is redundant. This patch increases compile time by itself, but reduces it when combined with the follow-up patch.

[Orlando]

I think some kind of custom interval map could possibly yield further improvements, but combining the two patches (second one coming shortly) already gives a geomean 0.3% reduction in instructions retired in a CTMark LTO-O3-g build.

[jmorse]

LGTM with one question -- there's a semantic change whereby a debug intrinsic with no fragment is considered as covering the whole variable, right? (I think this is uncontroversial).

As you say, strictly this is doing more work, but to reduce work in the next patch.

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

2194

Any particular reason for switching from SmallDenseMap to DenseMap -- there's an initial allocation for DenseMaps that's going to mean one additional malloc/free for each block, even if there's little work to be done in it.

2230

[Orlando]

there's a semantic change whereby a debug intrinsic with no fragment is considered as covering the whole variable, right

I don't think there's been a change - I would argue that has always been the case.

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

2194

No reason - just a typo essentially I think. I will change it back.

[jmorse]

In D146978#4227321, @Orlando wrote:

I don't think there's been a change - I would argue that has always been the case.

Righty-ho, I just missed it then, LGTM

llvm/include/llvm/IR/DebugInfoMetadata.h

public:
   /// Return whether the first element a DW_OP_deref.
   bool startsWithDeref() const;
 
   /// Return whether there is exactly one operator and it is a DW_OP_deref;
   bool isDeref() const;
 
   /// Holds the characteristics of one fragment of a larger variable.
   struct FragmentInfo {
+    FragmentInfo() = default;
+    FragmentInfo(uint64_t SizeInBits, uint64_t OffsetInBits)
+        : SizeInBits(SizeInBits), OffsetInBits(OffsetInBits) {}
     uint64_t SizeInBits;
     uint64_t OffsetInBits;
     /// Return the index of the first bit of the fragment.
     uint64_t startInBits() const { return OffsetInBits; }
     /// Return the index of the bit after the end of the fragment, e.g. for
     /// fragment offset=16 and size=32 return their sum, 48.
     uint64_t endInBits() const { return OffsetInBits + SizeInBits; }
   };

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

 ///
 /// This implements removeRedundantDbgInstrsUsingBackwardScan from
 /// lib/Transforms/Utils/BasicBlockUtils.cpp for locations described with
 /// FunctionVarLocsBuilder instead of with intrinsics.
 static bool
 removeRedundantDbgLocsUsingBackwardScan(const BasicBlock *BB,
                                         FunctionVarLocsBuilder &FnVarLocs) {
   bool Changed = false;
-  SmallDenseSet<DebugVariable> VariableSet;
-
+  SmallDenseMap<DebugAggregate, BitVector> VariableDefinedBits;
   // Scan over the entire block, not just over the instructions mapped by
   // FnVarLocs, because wedges in FnVarLocs may only be seperated by debug
   // instructions.
   for (const Instruction &I : reverse(*BB)) {
     if (!isa<DbgVariableIntrinsic>(I)) {
       // Sequence of consecutive defs ended. Clear map for the next one.
-      VariableSet.clear();
+      VariableDefinedBits.clear();
     }
 
     // Get the location defs that start just before this instruction.
     const auto *Locs = FnVarLocs.getWedge(&I);
     if (!Locs)
       continue;
 
     NumWedgesScanned++;
     bool ChangedThisWedge = false;
     // The new pruned set of defs, reversed because we're scanning backwards.
     SmallVector<VarLocInfo> NewDefsReversed;
 
     // Iterate over the existing defs in reverse.
     for (auto RIt = Locs->rbegin(), REnd = Locs->rend(); RIt != REnd; ++RIt) {
       NumDefsScanned++;
-      const DebugVariable &Key = FnVarLocs.getVariable(RIt->VariableID);
-      bool FirstDefOfFragment = VariableSet.insert(Key).second;
+      DebugAggregate Aggr =
+          getAggregate(FnVarLocs.getVariable(RIt->VariableID));
+      uint64_t SizeInBits = Aggr.first->getSizeInBits().value_or(0);
 
-      // If the same variable fragment is described more than once it is enough
-      // to keep the last one (i.e. the first found in this reverse iteration).
-      if (FirstDefOfFragment) {
-        // New def found: keep it.
+      if (SizeInBits == 0) {
+        // If the size is unknown (0) then keep this location def to be safe.
         NewDefsReversed.push_back(*RIt);
-      } else {
-        // Redundant def found: throw it away. Since the wedge of defs is being
-        // rebuilt, doing nothing is the same as deleting an entry.
-        ChangedThisWedge = true;
-        NumDefsRemoved++;
-      }
-      continue;
-    }
+        continue;
+      }
+
+      // Only keep this location definition if it is not fully eclipsed by
+      // other definitions in this wedge that come after it
+
+      // Inert the bits the location definition defines.
+      auto InsertResult =
+          VariableDefinedBits.try_emplace(Aggr, BitVector(SizeInBits));
+      bool FirstDefinition = InsertResult.second;
+      BitVector &DefinedBits = InsertResult.first->second;
+
+      DIExpression::FragmentInfo Fragment =
+          RIt->Expr->getFragmentInfo().value_or(
+              DIExpression::FragmentInfo(SizeInBits, 0));
+      bool InvalidFragment = Fragment.endInBits() > SizeInBits;
+
+      // If this defines any previously undefined bits, keep it.
+      if (FirstDefinition || InvalidFragment ||
+          DefinedBits.find_first_unset_in(Fragment.startInBits(),
+                                          Fragment.endInBits()) != -1) {
+        if (!InvalidFragment)
+          DefinedBits.set(Fragment.startInBits(), Fragment.endInBits());
+        NewDefsReversed.push_back(*RIt);
+        continue;
+      }
+
 
     // Un-reverse the defs and replace the wedge with the pruned version.
     if (ChangedThisWedge) {
       std::reverse(NewDefsReversed.begin(), NewDefsReversed.end());
       FnVarLocs.setWedge(&I, std::move(NewDefsReversed));
       NumWedgesChanged++;
       Changed = true;
     }

llvm/test/DebugInfo/assignment-tracking/X86/nested-loop-frags.ll

entry:
   br label %do.body, !dbg !24
 ; CHECK-LABEL: bb.0.entry:
 ; CHECK-NEXT: successors
 ; CHECK-NEXT: {{^ *$}}
 ; CHECK-NEXT:    DBG_VALUE %stack.0.a.addr, $noreg, ![[a]], !DIExpression(DW_OP_deref)
 ; CHECK-NEXT:    DBG_VALUE %stack.1.b.addr, $noreg, ![[b]], !DIExpression(DW_OP_deref)
 ; CHECK-NEXT:    DBG_VALUE %stack.4.e.addr, $noreg, ![[e]], !DIExpression(DW_OP_deref)
 ; CHECK-NEXT:    MOV64mi32 %stack.0.a.addr, 1, $noreg, 0, $noreg, 1
-; CHECK-NEXT:    DBG_VALUE $noreg, $noreg, ![[a]], !DIExpression(DW_OP_LLVM_fragment, 32, 32)
-; CHECK-NEXT:    DBG_VALUE %stack.0.a.addr, $noreg, ![[a]], !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 32)
-; CHECK-NEXT:    DBG_VALUE %stack.0.a.addr, $noreg, ![[a]], !DIExpression(DW_OP_deref)
 ; CHECK-NEXT:    MOV64mi32 %stack.1.b.addr, 1, $noreg, 0, $noreg, 2
-; CHECK-NEXT:    DBG_VALUE $noreg, $noreg, ![[b]], !DIExpression(DW_OP_LLVM_fragment, 32, 32)
-; CHECK-NEXT:    DBG_VALUE %stack.1.b.addr, $noreg, ![[b]], !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 32)
-; CHECK-NEXT:    DBG_VALUE %stack.1.b.addr, $noreg, ![[b]], !DIExpression(DW_OP_deref)
 ; CHECK-NEXT:    DBG_VALUE %stack.4.e.addr, $noreg, ![[e]], !DIExpression(DW_OP_plus_uconst, 4, DW_OP_deref, DW_OP_LLVM_fragment, 32, 32)
 ; CHECK-NEXT:    DBG_VALUE %stack.4.e.addr, $noreg, ![[e]], !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 32)
 ; CHECK-NEXT:    MOV32mi %stack.0.a.addr, 1, $noreg, 0, $noreg, 3
 ; CHECK-NEXT:    DBG_VALUE $noreg, $noreg, ![[a]], !DIExpression(DW_OP_LLVM_fragment, 0, 32)
 ; CHECK-NEXT:    DBG_VALUE %stack.0.a.addr, $noreg, ![[a]], !DIExpression(DW_OP_plus_uconst, 4, DW_OP_deref, DW_OP_LLVM_fragment, 32, 32)
 ; CHECK-NEXT:    MOV32mi %stack.1.b.addr, 1, $noreg, 0, $noreg, 4
 ; CHECK-NEXT:    DBG_VALUE $noreg, $noreg, ![[b]], !DIExpression(DW_OP_LLVM_fragment, 0, 32)
 ; CHECK-NEXT:    DBG_VALUE %stack.1.b.addr, $noreg, ![[b]], !DIExpression(DW_OP_plus_uconst, 4, DW_OP_deref, DW_OP_LLVM_fragment, 32, 32)
do.cond:                                          ; preds = %if.then, %if.else
   call void @llvm.dbg.assign(metadata i1 undef, metadata !67, metadata !DIExpression(DW_OP_LLVM_fragment, 32, 32), metadata !69, metadata ptr %c.addr, metadata !DIExpression()), !dbg !27 ; VAR:c
   ;call void @llvm.dbg.assign(metadata i32 11, metadata !79, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 32), metadata !81, metadata ptr %f.addr, metadata !DIExpression()), !dbg !27 ; VAR:f
   %1 = load i32, ptr @g_b, align 4, !dbg !43
   %tobool3.not = icmp eq i32 %1, 0, !dbg !43
   br i1 %tobool3.not, label %do.cond4, label %do.body1, !dbg !44, !llvm.loop !45
 ; CHECK-LABEL: bb.5.do.cond:
 ; CHECK-NEXT: successors
 ; CHECK-NEXT: {{^ *$}}
-; xCHECK-NEXT:    XXX ?DBG_VALUE %stack.2.c.addr, $noreg, ![[c]], !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 32, 32)
-; xCHECK-NEXT:    DBG_VALUE 11, $noreg, ![[f]], !DIExpression(DW_OP_LLVM_fragment, 32, 32)
 ; CHECK-NOT: DBG_VALUE
 ; CHECK:      {{^ *$}}
 
 do.cond4:                                         ; preds = %do.cond
   %2 = load i32, ptr @g_c, align 4, !dbg !48
   %tobool5.not = icmp eq i32 %2, 0, !dbg !48
   br i1 %tobool5.not, label %do.end6, label %do.body, !dbg !49, !llvm.loop !50
 ; CHECK-LABEL: bb.6.do.cond4:
do.end6:                                          ; preds = %do.cond4
   call void @llvm.dbg.assign(metadata i32 6, metadata !72, metadata !DIExpression(), metadata !74, metadata ptr %d.addr, metadata !DIExpression()), !dbg !27 ; VAR:d
   ;call void @llvm.dbg.assign(metadata i32 11, metadata !79, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 32), metadata !81, metadata ptr %f.addr, metadata !DIExpression()), !dbg !27 ; VAR:f
   ret i32 0, !dbg !53
 ; CHECK-LABEL: bb.7.do.end6:
 ; CHECK-NEXT:    DBG_VALUE %stack.0.a.addr, $noreg, ![[a]], !DIExpression(DW_OP_plus_uconst, 32, DW_OP_deref, DW_OP_LLVM_fragment, 32, 32)
 ; CHECK-NEXT:    DBG_VALUE %stack.0.a.addr, $noreg, ![[a]], !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 32)
 ; CHECK-NEXT:    DBG_VALUE 4, $noreg, ![[b]], !DIExpression(DW_OP_LLVM_fragment, 0, 32)
 ; CHECK-NEXT:    DBG_VALUE %stack.1.b.addr, $noreg, ![[b]], !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 32, 32)
-; xCHECK-NEXT:    XXX ? DBG_VALUE %stack.3.d.addr, $noreg, ![[d]], !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 32, 32)
-; xCHECK-NEXT:    DBG_VALUE 11, $noreg, ![[f]], !DIExpression(DW_OP_LLVM_fragment, 32, 32)
 }
 
 declare !dbg !54 void @_Z4calli(i32 noundef) local_unnamed_addr #1
 declare void @llvm.dbg.declare(metadata, metadata, metadata)
 declare void @llvm.dbg.value(metadata, metadata, metadata)
 declare void @llvm.dbg.assign(metadata, metadata, metadata, metadata, metadata, metadata)
 
 !llvm.dbg.cu = !{!2}

llvm/test/DebugInfo/assignment-tracking/X86/remove-redundant-defs-bwd-scan.ll

+; RUN: llc %s -stop-after=finalize-isel -o - \
+; RUN: | FileCheck %s --implicit-check-not=DBG_
+
+;; Hand-written to test assignment tracking analysis' removal of redundant
+;; debug loc definitions. Checks written inline.
+
+target triple = "x86_64-unknown-linux-gnu"
+
+define dso_local void @f() #0 !dbg !8 {
+entry:
+  call void @llvm.dbg.value(metadata i32 0, metadata !14, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 32)), !dbg !15
+  call void @llvm.dbg.value(metadata i64 1, metadata !14, metadata !DIExpression()), !dbg !15
+;; def [0 -> 32)
+;; def [0          -> 64)
+;; Second frag fully contains the first so first should be removed.
+; CHECK:      DBG_VALUE 1,
+  call void @step()
+  call void @llvm.dbg.value(metadata i32 2, metadata !14, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 32)), !dbg !15
+  call void @llvm.dbg.value(metadata i32 3, metadata !14, metadata !DIExpression(DW_OP_LLVM_fragment, 32, 32)), !dbg !15
+;; def [0 -> 32)
+;; def         [32 -> 64)
+;; Frags don't overlap so no removal should take place:
+; CHECK:      DBG_VALUE 2,
+; CHECK-NEXT: DBG_VALUE 3,
+  call void @step()
+  call void @llvm.dbg.value(metadata i16 4, metadata !14, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 16)), !dbg !15
+  call void @llvm.dbg.value(metadata i8 5, metadata !14, metadata !DIExpression(DW_OP_LLVM_fragment, 8, 8)), !dbg !15
+;; def [0      -> 16)
+;; def      [8 -> 16)
+;; Second frag doesn't fully contain first so no removal should take place:
+; CHECK:      DBG_VALUE 4,
+; CHECK-NEXT: DBG_VALUE 5,
+  call void @step()
+  call void @llvm.dbg.value(metadata i16 6, metadata !14, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 16)), !dbg !15
+  call void @llvm.dbg.value(metadata i8 7, metadata !14, metadata !DIExpression(DW_OP_LLVM_fragment, 8, 8)), !dbg !15
+  call void @llvm.dbg.value(metadata i32 8, metadata !14, metadata !DIExpression(DW_OP_LLVM_fragment, 8, 16)), !dbg !15
+;; def [0      -> 16)
+;; def      [8 -> 16)
+;; def      [8       -> 24)
+;; Middle frag is fully contained by the last so should be removed.
+; CHECK:      DBG_VALUE 6,
+; CHECK-NEXT: DBG_VALUE 8,
+  ret void
+}
+
+declare void @step()
+declare void @llvm.dbg.value(metadata, metadata, metadata) #1
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!2, !3, !4, !5, !6, !1000}
+!llvm.ident = !{!7}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, producer: "clang version 14.0.0", isOptimized: false, 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 = !{i32 7, !"frame-pointer", i32 2}
+!7 = !{!"clang version 14.0.0"}
+!8 = distinct !DISubprogram(name: "f", linkageName: "_Z1fl", scope: !1, file: !1, line: 1, type: !9, scopeLine: 1, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !12)
+!9 = !DISubroutineType(types: !10)
+!10 = !{!11, !11}
+!11 = !DIBasicType(name: "long", size: 64, encoding: DW_ATE_signed)
+!12 = !{}
+!13 = distinct !DIAssignID()
+!14 = !DILocalVariable(name: "a", arg: 1, scope: !8, file: !1, line: 1, type: !11)
+!15 = !DILocation(line: 0, scope: !8)
+!16 = distinct !DIAssignID()
+!1000 = !{i32 7, !"debug-info-assignment-tracking", i1 true}

llvm/test/DebugInfo/assignment-tracking/X86/untagged-store-frag.ll

 ;; 3.       | Value        | Mem
 ;; 4.       | Value        | Value
 ;; 5.       | Mem          | Value
 ;; 6.       | Mem          | Mem
 
 ; CHECK-DAG: ![[A:[0-9]+]] = !DILocalVariable(name: "a",
 
 ; CHECK:      DBG_VALUE %stack.0.a.addr, $noreg, ![[A]], !DIExpression(DW_OP_deref)
+; CHECK-NEXT: ADJCALLSTACKDOWN
+; CHECK-NEXT: @step
+; CHECK-NEXT: ADJCALLSTACKUP
 ; CHECK-NEXT: DBG_VALUE 5,               $noreg, ![[A]], !DIExpression(DW_OP_LLVM_fragment, 0, 32)
 ; CHECK-NEXT: DBG_VALUE $noreg,          $noreg, ![[A]], !DIExpression(DW_OP_LLVM_fragment, 32, 32)
 ; CHECK-NEXT:   MOV32mi %stack.0.a.addr, 1, $noreg, 0, $noreg, 123
 ; CHECK-NEXT: DBG_VALUE %stack.0.a.addr, $noreg, ![[A]], !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 32)
 ; CHECK-NEXT:   MOV32mr %stack.0.a.addr, 1, $noreg, 4, $noreg, %1 :: (store (s32) into %ir.add.ptr, align 8)
 ; CHECK-NEXT: DBG_VALUE %stack.0.a.addr, $noreg, ![[A]], !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 32, 32)
 
-;; NOTE: The second and third DBG_VALUE combined make the first redundant. If
-;; removeRedundantDbgInstrs gets smarter, add an instruction between the first
-;; dbg.assign and the subsequent dbg.value.
-
 target triple = "x86_64-unknown-linux-gnu"
 
 define dso_local noundef i64 @_Z1fl(i64 noundef %a, i32 %b) #0 !dbg !8 {
 entry:
   %a.addr = alloca i64, align 8, !DIAssignID !13
   call void @llvm.dbg.assign(metadata i1 undef, metadata !14, metadata !DIExpression(), metadata !13, metadata ptr %a.addr, metadata !DIExpression()), !dbg !15
+  call void @step()
   call void @llvm.dbg.value(metadata i64 5, metadata !14, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 32)), !dbg !15
   call void @llvm.dbg.assign(metadata i1 undef, metadata !14, metadata !DIExpression(DW_OP_LLVM_fragment, 32, 32), metadata !16, metadata ptr %a.addr, metadata !DIExpression()), !dbg !15
   %frag.addr = bitcast ptr %a.addr to ptr
   store i32 123, ptr %frag.addr, align 8
   %0 = bitcast ptr %a.addr to ptr
   %add.ptr = getelementptr inbounds i32, ptr %0, i64 1
   store i32 %b, ptr %add.ptr, align 8, !DIAssignID !16
   %1 = load i64, ptr %a.addr, align 8
   ret i64 %1
 }
 
+declare void @step()
 declare void @llvm.dbg.value(metadata, metadata, metadata) #1
 declare void @llvm.dbg.assign(metadata, metadata, metadata, metadata, metadata, metadata) #1
 
 !llvm.dbg.cu = !{!0}
 !llvm.module.flags = !{!2, !3, !4, !5, !6, !1000}
 !llvm.ident = !{!7}
 
 !0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, producer: "clang version 14.0.0", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, splitDebugInlining: false, nameTableKind: None)