[DebugInfo] Remove invalidated locations during LiveDebugValues

[jmorse]

Summary

LiveDebugValues gives variable locations to blocks, but it should also take away. There are various circumstances where a variable location is known until a loop backedge with a different location is detected. In those circumstances, where there's no agreement on the variable location, it should be undef / removed, otherwise we end up picking a location that's valid on some loop iterations but not others.

However, LiveDebugValues doesn't currently do this, see the new testcase attached. Without this patch, the location of !3 is assumed to be %bar through the loop. Once it's added to the In-Locations list, it's never removed, even though the later dbg.value(0... of !3 makes the location un-knowable.

This patch checks during block-location-joining to see whether any previously-present locations have been removed in a predecessor. If they have, the live-ins have changed, and the block needs reprocessing. Similarly, in transferTerminator, assign rather than |= the Out-Locations after processing a block, as we may have deleted some previously valid locations. This will mean that LiveDebugValues performs more propagation -- but that's necessary for it being correct.

In the two tests that change, in pieces.ll some spurious variable locations are now no longer propagated. In fission-ranges.ll, we now notice that the "a" / !14 variable is not valid for most of the function, instead a backedge with a mismatching location invalidates its location early. The control flow in the newly added test is slightly more complex than it needs to be (loop2 isn't necessary) due to other bugs.

On a clang-3.4 build a tiny number of variable locations get dropped, however the percentage of scope-bytes-covered falls from 46.5% to 45.2%. IMO this is good: those are invalid locations.

[jmorse]

lib/CodeGen/LiveDebugValues.cpp

1305–1311

Not technically necessary change here but I think it's worthwhile: the "OnPending" set this function maintains clears itself by going out of scope and back in again. This misled me for a bit, thinking there was something magical going on that meant OnPending didn't need clearing. IMHO YMMV it's better to explicitly clear it (hunk below) for ease of understanding. (Or if it's too irrelevant, then never mind).

[aprantl]

lib/CodeGen/LiveDebugValues.cpp

946

Makes sense.

1305–1311

I'm not sure about this change. Now OnPending has state that needs to be reasoned about. Let's not roll this into this patch.

test/DebugInfo/X86/live-debug-values-remove-range.ll

21

This is a really nice testcase!

[jmorse]

Remove an unnecessary change.

lib/CodeGen/LiveDebugValues.cpp

 #include <utility>
 #include <vector>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "livedebugvalues"
 
 STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
+STATISTIC(NumRemoved, "Number of DBG_VALUE instructions removed");
 
 // If @MI is a DBG_VALUE with debug value described by a defined
 // register, returns the number of this register. In the other case, returns 0.
 static Register isDbgValueDescribedByReg(const MachineInstr &MI) {
   assert(MI.isDebugValue() && "expected a DBG_VALUE");
   assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
   // If location of variable is described using a register (directly
   // or indirectly), this register is always a first operand.
bool LiveDebugValues::transferTerminator(MachineBasicBlock *CurMBB,
 
   LLVM_DEBUG(for (unsigned ID
                   : OpenRanges.getVarLocs()) {
     // Copy OpenRanges to OutLocs, if not already present.
     dbgs() << "Add to OutLocs in MBB #" << CurMBB->getNumber() << ":  ";
     VarLocIDs[ID].dump();
   });
   VarLocSet &VLS = OutLocs[CurMBB];
-  Changed = VLS |= OpenRanges.getVarLocs();
+  Changed = VLS != OpenRanges.getVarLocs();
   // New OutLocs set may be different due to spill, restore or register
   // copy instruction processing.
   if (Changed)
     VLS = OpenRanges.getVarLocs();
   OpenRanges.clear();
   return Changed;
 }
 
bool LiveDebugValues::join(
   }
   InLocsT.intersectWithComplement(KillSet);
 
   // As we are processing blocks in reverse post-order we
   // should have processed at least one predecessor, unless it
   // is the entry block which has no predecessor.
   assert((NumVisited || MBB.pred_empty()) &&
          "Should have processed at least one predecessor");
-  if (InLocsT.empty())
-    return false;
 
   VarLocSet &ILS = InLocs[&MBB];
   VarLocSet &Pending = PendingInLocs[&MBB];
 
   // New locations will have DBG_VALUE insts inserted at the start of the
   // block, after location propagation has finished. Record the insertions
   // that we need to perform in the Pending set.
   VarLocSet Diff = InLocsT;
   Diff.intersectWithComplement(ILS);
   for (auto ID : Diff) {
     Pending.set(ID);
     ILS.set(ID);
     ++NumInserted;
     Changed = true;
   }
+
+  // We may have lost locations by learning about a predecessor that either
+  // loses or moves a variable. Find any locations in ILS that are not in the
+  // new in-locations, and delete those.
+  VarLocSet Removed = ILS;
+  Removed.intersectWithComplement(InLocsT);
+  for (auto ID : Removed) {
+    Pending.reset(ID);
+    ILS.reset(ID);
+    ++NumRemoved;
+    Changed = true;
+  }
+
   return Changed;
 }
 
 void LiveDebugValues::flushPendingLocs(VarLocInMBB &PendingInLocs,
                                        VarLocMap &VarLocIDs) {
   // PendingInLocs records all locations propagated into blocks, which have
   // not had DBG_VALUE insts created. Go through and create those insts now.
   for (auto &Iter : PendingInLocs) {
for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
     Worklist.push(RPONumber);
     ++RPONumber;
   }
   // This is a standard "union of predecessor outs" dataflow problem.
   // To solve it, we perform join() and process() using the two worklist method
   // until the ranges converge.
   // Ranges have converged when both worklists are empty.
   SmallPtrSet<const MachineBasicBlock *, 16> Visited;
   while (!Worklist.empty() || !Pending.empty()) {
     // We track what is on the pending worklist to avoid inserting the same
     // thing twice.  We could avoid this with a custom priority queue, but this
     // is probably not worth it.
     SmallPtrSet<MachineBasicBlock *, 16> OnPending;
     LLVM_DEBUG(dbgs() << "Processing Worklist\n");
     while (!Worklist.empty()) {
       MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
       Worklist.pop();
       MBBJoined = join(*MBB, OutLocs, InLocs, VarLocIDs, Visited,
                        ArtificialBlocks, PendingInLocs);
       Visited.insert(MBB);
       if (MBBJoined) {
         MBBJoined = false;
         Changed = true;

test/DebugInfo/COFF/pieces.ll

 ; ASM:        #DEBUG_VALUE: loop_csr:o <- [DW_OP_LLVM_fragment 0 32] 0
 ; ASM:        #DEBUG_VALUE: loop_csr:o <- [DW_OP_LLVM_fragment 32 32] 0
 ; ASM: # %bb.2:                                 # %for.body.preheader
 ; ASM:         xorl    %edi, %edi
 ; ASM:         xorl    %esi, %esi
 ; ASM: [[oy_ox_start:\.Ltmp[0-9]+]]:
 ; ASM:         .p2align        4, 0x90
 ; ASM: .LBB0_3:                                # %for.body
-; ASM:        #DEBUG_VALUE: loop_csr:o <- [DW_OP_LLVM_fragment 0 32] 0
 ; ASM:        #DEBUG_VALUE: loop_csr:o <- [DW_OP_LLVM_fragment 0 32] $edi
 ; ASM:        #DEBUG_VALUE: loop_csr:o <- [DW_OP_LLVM_fragment 32 32] $esi
 ; ASM:        .cv_loc 0 1 13 11               # t.c:13:11
 ; ASM:        movl    %edi, %ecx
 ; ASM:        callq   g
 ; ASM:        movl    %eax, %edi
 ; ASM: [[ox_start:\.Ltmp[0-9]+]]:
 ; ASM:         #DEBUG_VALUE: loop_csr:o <- [DW_OP_LLVM_fragment 0 32] $edi

test/DebugInfo/X86/fission-ranges.ll

 ; CHECK-NOT: .debug_loc contents:
 ; CHECK-NOT: Beginning address offset
 ; CHECK: .debug_loc.dwo contents:
 
 ; Don't assume these locations are entirely correct - feel free to update them
 ; if they've changed due to a bugfix, change in register allocation, etc.
 
 ; CHECK:      [[A]]:
-; CHECK-NEXT:   Addr idx 2 (w/ length 169): DW_OP_consts +0, DW_OP_stack_value
+; CHECK-NEXT:   Addr idx 2 (w/ length 15): DW_OP_consts +0, DW_OP_stack_value
 ; CHECK-NEXT:   Addr idx 3 (w/ length 15): DW_OP_reg0 RAX
 ; CHECK-NEXT:   Addr idx 4 (w/ length 18): DW_OP_breg7 RSP-8
 ; CHECK:      [[E]]:
 ; CHECK-NEXT:   Addr idx 5 (w/ length 9): DW_OP_reg0 RAX
 ; CHECK-NEXT:   Addr idx 6 (w/ length 98): DW_OP_breg7 RSP-44
 ; CHECK:      [[B]]:
 ; CHECK-NEXT:   Addr idx 7 (w/ length 15): DW_OP_reg0 RAX
 ; CHECK-NEXT:   Addr idx 8 (w/ length 66): DW_OP_breg7 RSP-32

test/DebugInfo/X86/live-debug-values-remove-range.ll

+; RUN: llc -mtriple=x86_64-unknown-unknown %s -o - -stop-after=livedebugvalues | FileCheck %s
+;
+; In the simple loop below, the location of the variable "toast" is %bar in
+; the entry block, then set to constant zero at the end of the loop. We cannot
+; know the location of "toast" at the start of the %loop block. Test that no
+; location is given until after the call to @booler.
+;
+; CHECK: ![[VARNUM:[0-9]+]] = !DILocalVariable(name: "toast"
+;
+; CHECK-LABEL: bb.1.loop
+; CHECK-NOT:   DBG_VALUE
+; CHECK-LABEL: CALL64pcrel32 @booler
+; CHECK:       DBG_VALUE 0, $noreg, ![[VARNUM]]
+
+declare i1 @booler()
+declare void @escape(i32)
+declare void @llvm.dbg.value(metadata, metadata, metadata)
+@glob = global i32 0
+
+define i32 @foo(i32 %bar) !dbg !4 {
+entry:
+  call void @llvm.dbg.value(metadata i32 %bar, metadata !3, metadata !DIExpression()), !dbg !6
+  br label %loop
+loop:
+  call void @escape(i32 %bar)
+  %retval = call i1 @booler(), !dbg !6
+  call void @llvm.dbg.value(metadata i32 0, metadata !3, metadata !DIExpression()), !dbg !6
+  br i1 %retval, label %loop2, label %exit
+loop2:
+  store i32 %bar, i32 *@glob
+  br label %loop
+exit:
+  ret i32 %bar
+}
+
+!llvm.module.flags = !{!0, !100}
+!llvm.dbg.cu = !{!1}
+
+!100 = !{i32 2, !"Dwarf Version", i32 4}
+!0 = !{i32 2, !"Debug Info Version", i32 3}
+!1 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !2, producer: "beards", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug)
+!2 = !DIFile(filename: "bees.cpp", directory: ".")
+!3 = !DILocalVariable(name: "toast", scope: !4, file: !2, line: 1, type: !16)
+!4 = distinct !DISubprogram(name: "nope", scope: !2, file: !2, line: 1, spFlags: DISPFlagDefinition, unit: !1, retainedNodes: !13, type: !14, isDefinition: true)
+!6 = !DILocation(line: 1, scope: !4)
+!13 = !{!3}
+!14 = !DISubroutineType(types: !15)
+!15 = !{!16}
+!16 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed)