[DebugInfo] LiveDebugValues should always revisit backedges if it skips them

[jmorse]

Summary

LiveDebugValues currently ignores loop backedges on the first iteration -- this is because any variable locations that are live-through a loop need to be propagated in regardless. Otherwise, the unvisited backedge would always invalidate any potential live-through variable locations.

However: LiveDebugValues only revisits blocks if the out-locations of a predecessor changes. This creates situations like the "baz" function added in this patch:

• Location of !103 enters the loop block as %bar, which is taken on faith by ignoring the backedge,
• Location of !103 changes in the loop block to constant-zero, which should later invalidate the in-location for the loop through the backedge, like it does in the "foo" function,
• However, the out-locations of the loop block are not changed as the result of propagation, therefore the loop block is never re-visited.

The net effect of which is that we took the !103 == %bar location on faith, and as the backedge is not seen, it's kept forever. (This doesn't happen in the "foo" function in the same file because I've deliberately set that up to have an out-location change, to continue propagation). Some of this is behind PR38997.

This patch tries to rectify this by, whenever we ignore a backedge, forcing the ignoring block to be revisited at least once. This rectifies the immediate problem. The previous discussion about how this is supposed to work seems to be here [0]: I'm not completely convinced that what we have right now will always get the right answer because, as Vikram puts half way through that thread, getting a full answer requires initialising every block as having all variables in all locations. However, with this patch I think we get more accurate locations, so it's a step in the right direction.

On a clang-3.4 build we drop a single variable location; and the scope-bytes-covered statistic ticks up 0.2%. This is mildly counter-intuitive as I would expect more locations to be invalidated. I'm hoping this is just complex location interactions, with fewer wrong locations it might be easier to prove there are more right ones, currently looking closer.

I've added a third function in the test file that positively checks a variable location that's live-through a loop has its location preserved, just in case we mess with this further.

In the DW_AT_location-reference.ll test that changes, placeDbgValues moves the non-constant variable locations into the middle of the loops. Previously we marked the first instruction of each loop body as having a constant value (which would be wrong), which doesn't occur now -- in fact no instruction gets a constant-value of "x", hence the fewer location list entries. This test says it only cares about the fact that "x" moves around though, so I believe it still works (TM).

[0] https://groups.google.com/d/msg/llvm-dev/nlgxIfDQnhs/c55kcncIAAAJ

[aprantl]

LiveDebugValues currently ignores loop backedges on the first iteration -- this is because any variable locations that are live-through a loop need to be propagated in regardless. Otherwise, the unvisited backedge would always invalidate any potential live-through variable locations.

Conceptually, the analysis uses a lattice with three elements to describe each VarLoc at each point: ⊥ (uninitialized), true (VarLoc is valid), false (VarLoc is not valid). As @dberlin pointed out in the linked thread, we LiveDebugValues *implicitly* represents the (uninitialized) state by ensuring a specific iteration order. (Not joining the unvisited backedge with the incoming edge, is equivalent to joining a set full of ⊥'s with the incoming edge).

However: LiveDebugValues only revisits blocks if the out-locations of a predecessor changes. This creates situations like the "baz" function added in this patch:

Location of !103 enters the loop block as %bar, which is taken on faith by ignoring the backedge,

Makes sense.

Location of !103 changes in the loop block to constant-zero, which should later invalidate the in-location for the loop through the backedge, like it does in the "foo" function,

When the set out OutLocs changes (and in this case it changes from [crumpets=⊥] to [crumpets=0]) all successor blocks (in this case also the block itself because of the back edge) should be added to worklist automatically. Why isn't this happening?

However, the out-locations of the loop block are not changed as the result of propagation, therefore the loop block is never re-visited.

That I don't understand yet. They change from "no info" -> "some info". What am I missing?

The net effect of which is that we took the !103 == %bar location on faith, and as the backedge is not seen, it's kept forever. (This doesn't happen in the "foo" function in the same file because I've deliberately set that up to have an out-location change, to continue propagation). Some of this is behind PR38997.

This patch tries to rectify this by, whenever we ignore a backedge, forcing the ignoring block to be revisited at least once. This rectifies the immediate problem. The previous discussion about how this is supposed to work seems to be here [0]: I'm not completely convinced that what we have right now will always get the right answer because, as Vikram puts half way through that thread, getting a full answer requires initialising every block as having all variables in all locations. However, with this patch I think we get more accurate locations, so it's a step in the right direction.

[jmorse]

In D66663#1643786, @aprantl wrote:

Location of !103 changes in the loop block to constant-zero, which should later invalidate the in-location for the loop through the backedge, like it does in the "foo" function,

When the set out OutLocs changes (and in this case it changes from [crumpets=⊥] to [crumpets=0]) all successor blocks (in this case also the block itself because of the back edge) should be added to worklist automatically. Why isn't this happening?

However, the out-locations of the loop block are not changed as the result of propagation, therefore the loop block is never re-visited.

That I don't understand yet. They change from "no info" -> "some info". What am I missing?

Ah, this comes down to the initialisation that OutLocs experiences, performed here [0] before cross-block propagation starts. Because OutLocs is initialised with [crumpets=0] rather than ⊥, reprocessing the loop block after joining appears to change nothing, hence there's no further iteration.

Exactly why the initialisation happens isn't clear to me (it appears to be as old as LiveDebugValues). It causes other problems too (the entry block is never revisited in propagation, causing entry register/stack transfers to not be recorded) but that's for some other time.

I'll try reimplementing this patch by removing the initialisation phase and see what happens; I think (80%) there will still be some special casing needed though. If in the example the variable location was instead clobbered/undef'd in the loop block, the OutLocs for the loop would have effectively changed from uninitialised to false and the loop head would need revisiting, but this wouldn't actually present as a difference in the OutLocs vector-of-valid-locations.

[0] https://github.com/llvm/llvm-project/blob/0ae549814693eb201d7e7a0a77856e55a98e19ee/llvm/lib/CodeGen/LiveDebugValues.cpp#L1257

[aprantl]

I think (80%) there will still be some special casing needed though.

Unless we change the implementation of VarLocSet to actually include three values instead of two, I think you are right. We could try and see if something like:

1. not in the set -> ⊥
2. in the set -> true
3. in the set with a special KILL marker (perhaps implemented as an extra set of killed VarLocs) -> false

makes the implementation look more regular. This is not the only way to achieve this, just the first thing I came with on the spot.

[jmorse]

This update removes the "initialisation" phase that was happening in LiveDebugValues, and doing so fixes the original problem I was trying to solve, horray.

The change in logic (the |= to MBBJoined) forces all blocks to be joined again after the first pass through. Before, the "join" logic for unvisited predecessors was effectively firing on the _second_ pass through because OutLocs was already initialised. Now that happens on the first pass, and it correctly sees added/missing locations on the second pass through.

I've eliminated the initialization flag for the "process" method while doing this, as I can't find any reason for it to exist. All the instructions get processed for transfers at least once, just as before, and no tests fail. I've added a MIR regression test for the behaviour where the entry block not being revisited will lead to transfers there not being recognised, which is another thing fixed by getting rid of the initialisation.

compiler-gen-bbs-livedebugvalues.mir: This test now recognises a stack spill and creates a second DBG_VALUE, where LiveDebugVariables has already created a DBG_VALUE. This is annoying, but not faulty IMO.

debug-info-blocks.ll: is more problematic. It seems a hash-collision and PR43058 [0] causes a stack-load of a return address to be recognised as a variable transfer, which I've XFailed. I haven't committed in the fix for PR43058 because of what I've written on bugzilla; IMHO it's best to xfail this test and move forwards, although we could also leave the patch hanging until PR43058 is done.

There are negligible differences in the debug statistics for a clang-3.4 build.

[0] https://bugs.llvm.org/show_bug.cgi?id=43058

[aprantl]

This patch looks really elegant. Does the removal of the initialization phase have any adverse effect on the performance?

Which hash is colliding to contribute top the XFAILed test? Should we fix PR43058 before landing this?

[jmorse]

In D66663#1647741, @aprantl wrote:

This patch looks really elegant. Does the removal of the initialization phase have any adverse effect on the performance?

A few asan-builds of clang-3.4 showed no notable difference in performance at all.

Which hash is colliding to contribute top the XFAILed test? Should we fix PR43058 before landing this?

I've uploaded D66895 to fix this, it wasn't as deep a problem as I feared. I've added it as a child revision to this patch because the regression test I add in D66895 depends on transfers in the entry block being considered, which they aren't without this patch.

[aprantl]

Thanks!

llvm/trunk/lib/CodeGen/LiveDebugValues.cpp

void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges,
                            VarLocMap &VarLocIDs, TransferMap &Transfers,
                            DebugParamMap &DebugEntryVals);
   bool transferTerminator(MachineBasicBlock *MBB, OpenRangesSet &OpenRanges,
                           VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs);
 
   void process(MachineInstr &MI, OpenRangesSet &OpenRanges,
                VarLocInMBB &OutLocs, VarLocMap &VarLocIDs,
                TransferMap &Transfers, DebugParamMap &DebugEntryVals,
-               bool transferChanges, OverlapMap &OverlapFragments,
+               OverlapMap &OverlapFragments,
                VarToFragments &SeenFragments);
 
   void accumulateFragmentMap(MachineInstr &MI, VarToFragments &SeenFragments,
                              OverlapMap &OLapMap);
 
   bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
             const VarLocMap &VarLocIDs,
             SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
void LiveDebugValues::accumulateFragmentMap(MachineInstr &MI,
   }
 
   AllSeenFragments.insert(ThisFragment);
 }
 
 /// This routine creates OpenRanges and OutLocs.
 void LiveDebugValues::process(MachineInstr &MI, OpenRangesSet &OpenRanges,
                               VarLocInMBB &OutLocs, VarLocMap &VarLocIDs,
-                              TransferMap &Transfers, DebugParamMap &DebugEntryVals,
-                              bool transferChanges,
+                              TransferMap &Transfers,
+                              DebugParamMap &DebugEntryVals,
                               OverlapMap &OverlapFragments,
                               VarToFragments &SeenFragments) {
   transferDebugValue(MI, OpenRanges, VarLocIDs);
   transferRegisterDef(MI, OpenRanges, VarLocIDs, Transfers,
                       DebugEntryVals);
-  if (transferChanges) {
-    transferRegisterCopy(MI, OpenRanges, VarLocIDs, Transfers);
-    transferSpillOrRestoreInst(MI, OpenRanges, VarLocIDs, Transfers);
-  } else {
-    // Build up a map of overlapping fragments on the first run through.
-    if (MI.isDebugValue())
-      accumulateFragmentMap(MI, SeenFragments, OverlapFragments);
-  }
 }
 
 /// This routine joins the analysis results of all incoming edges in @MBB by
 /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
 /// source variable in all the predecessors of @MBB reside in the same location.
 bool LiveDebugValues::join(
     MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
     const VarLocMap &VarLocIDs,
     SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
     SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks,
     VarLocInMBB &PendingInLocs) {
   LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
   bool Changed = false;
 
   VarLocSet InLocsT; // Temporary incoming locations.
 
   // For all predecessors of this MBB, find the set of VarLocs that
   // can be joined.
   int NumVisited = 0;
   for (auto p : MBB.predecessors()) {
-    // Ignore unvisited predecessor blocks.  As we are processing
-    // the blocks in reverse post-order any unvisited block can
-    // be considered to not remove any incoming values.
+    // Ignore backedges if we have not visited the predecessor yet. As the
+    // predecessor hasn't yet had locations propagated into it, most locations
+    // will not yet be valid, so treat them as all being uninitialized and
+    // potentially valid. If a location guessed to be correct here is
+    // invalidated later, we will remove it when we revisit this block.
     if (!Visited.count(p)) {
       LLVM_DEBUG(dbgs() << "  ignoring unvisited pred MBB: " << p->getNumber()
                         << "\n");
       continue;
     }
     auto OL = OutLocs.find(p);
     // Join is null in case of empty OutLocs from any of the pred.
     if (OL == OutLocs.end())
bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
   DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
   std::priority_queue<unsigned int, std::vector<unsigned int>,
                       std::greater<unsigned int>>
       Worklist;
   std::priority_queue<unsigned int, std::vector<unsigned int>,
                       std::greater<unsigned int>>
       Pending;
 
-  enum : bool { dontTransferChanges = false, transferChanges = true };
-
   // Besides parameter's modification, check whether a DBG_VALUE is inlined
   // in order to deduce whether the variable that it tracks comes from
   // a different function. If that is the case we can't track its entry value.
   auto IsUnmodifiedFuncParam = [&](const MachineInstr &MI) {
     auto *DIVar = MI.getDebugVariable();
     return DIVar->isParameter() && DIVar->isNotModified() &&
            !MI.getDebugLoc()->getInlinedAt();
   };
bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
   // parameters entry values.
   for (auto &MI : First_MBB)
     if (MI.isDebugValue() && IsUnmodifiedFuncParam(MI) &&
         !MI.isIndirectDebugValue() && IsRegOtherThanSPAndFP(MI.getOperand(0)) &&
         !DebugEntryVals.count(MI.getDebugVariable()) &&
         !MI.getDebugExpression()->isFragment())
       DebugEntryVals[MI.getDebugVariable()] = &MI;
 
-  // Initialize every mbb with OutLocs.
-  // We are not looking at any spill instructions during the initial pass
-  // over the BBs. The LiveDebugVariables pass has already created DBG_VALUE
-  // instructions for spills of registers that are known to be user variables
-  // within the BB in which the spill occurs.
+  // Initialize per-block structures and scan for fragment overlaps.
   for (auto &MBB : MF) {
+    PendingInLocs[&MBB] = VarLocSet();
+
     for (auto &MI : MBB) {
-      process(MI, OpenRanges, OutLocs, VarLocIDs, Transfers, DebugEntryVals,
-              dontTransferChanges, OverlapFragments, SeenFragments);
-    }
-    transferTerminator(&MBB, OpenRanges, OutLocs, VarLocIDs);
-    // Add any entry DBG_VALUE instructions necessitated by parameter
-    // clobbering.
-    for (auto &TR : Transfers) {
-      MBB.insertAfter(MachineBasicBlock::iterator(*TR.TransferInst),
-                     TR.DebugInst);
+      if (MI.isDebugValue())
+        accumulateFragmentMap(MI, SeenFragments, OverlapFragments);
     }
-    Transfers.clear();
-
-    // Initialize pending inlocs.
-    PendingInLocs[&MBB] = VarLocSet();
   }
 
   auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
     if (const DebugLoc &DL = MI.getDebugLoc())
       return DL.getLine() != 0;
     return false;
   };
   for (auto &MBB : MF)
while (!Worklist.empty() || !Pending.empty()) {
     // 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);
+      MBBJoined |= Visited.insert(MBB).second;
       if (MBBJoined) {
         MBBJoined = false;
         Changed = true;
         // Now that we have started to extend ranges across BBs we need to
         // examine spill instructions to see whether they spill registers that
         // correspond to user variables.
         // First load any pending inlocs.
         OpenRanges.insertFromLocSet(PendingInLocs[MBB], VarLocIDs);
         for (auto &MI : *MBB)
               process(MI, OpenRanges, OutLocs, VarLocIDs, Transfers,
-                      DebugEntryVals, transferChanges, OverlapFragments,
-                      SeenFragments);
+                      DebugEntryVals, OverlapFragments, SeenFragments);
         OLChanged |= transferTerminator(MBB, OpenRanges, OutLocs, VarLocIDs);
 
         // Add any DBG_VALUE instructions necessitated by spills.
         for (auto &TR : Transfers)
           MBB->insertAfter(MachineBasicBlock::iterator(*TR.TransferInst),
                            TR.DebugInst);
         Transfers.clear();
 

llvm/trunk/test/CodeGen/ARM/debug-info-blocks.ll

 ; RUN: llc -filetype=obj -O0 < %s | llvm-dwarfdump -v - | FileCheck %s
 
+; XFAIL: *
+; PR43058
+
 ; debug_info content
 ; CHECK: DW_AT_name {{.*}} "foobar_func_block_invoke_0"
 ; CHECK-NOT: DW_TAG_subprogram
 ; CHECK: DW_TAG_variable
 ; CHECK-NOT: DW_TAG
 ; CHECK-NEXT: DW_AT_location [DW_FORM_sec_offset]
 ; CHECK-NEXT:    [0x{{.*}}, 0x{{.*}}): {{.*}} DW_OP_plus_uconst 0x4, DW_OP_deref, DW_OP_plus_uconst 0x18
 ; CHECK-NEXT:    [0x{{.*}}, 0x{{.*}}): {{.*}} DW_OP_plus_uconst 0x4, DW_OP_deref, DW_OP_plus_uconst 0x18

llvm/trunk/test/DebugInfo/AArch64/compiler-gen-bbs-livedebugvalues.mir

bb.0.entry:
     renamable $w0 = ADDWri killed renamable $w0, 1, 0, debug-location !12
     DBG_VALUE renamable $w0, $noreg, !9, !DIExpression(), debug-location !12
     STRWui killed $w0, $sp, 3 :: (store 4 into %stack.0)
     DBG_VALUE $sp, 0, !9, !DIExpression(DW_OP_plus_uconst, 12), debug-location !12
 
     ; CHECK: DBG_VALUE renamable $w0, $noreg, !9, !DIExpression(), debug-location !12
     ; CHECK-NEXT: STRWui killed $w0, $sp, 3 :: (store 4 into %stack.0)
     ; CHECK-NEXT: DBG_VALUE $sp, 0, !9, !DIExpression(DW_OP_plus_uconst, 12)
+    ; CHECK-NEXT: DBG_VALUE $sp, 0, !9, !DIExpression(DW_OP_plus_uconst, 12)
   
   bb.1.artificial-bb-1:
     ; CHECK-LABEL: bb.1.artificial-bb-1:
     ; CHECK: DBG_VALUE $sp, 0, !9, !DIExpression(DW_OP_plus_uconst, 12)
       
   bb.2.artificial-bb-2:
     ; CHECK-LABEL: bb.2.artificial-bb-2:
     ; CHECK: DBG_VALUE $sp, 0, !9, !DIExpression(DW_OP_plus_uconst, 12)

llvm/trunk/test/DebugInfo/MIR/X86/live-debug-values-entry-transfer.mir

+# RUN: llc %s -o - -run-pass=livedebugvalues -mtriple=x86_64-unknown-unknown | FileCheck %s
+#
+# In this lightly modified test case, the transfer in the entry block from
+# geti32's return value in $eax to the non-volatile $ebx should be recognized,
+# and propagated throughout the whole function.
+#
+# CHECK-LABEL: bb.0.entry
+# CHECK:       DBG_VALUE $eax
+# CHECK:       DBG_VALUE $ebx
+# CHECK-LABEL: bb.1.loop2
+# CHECK:       DBG_VALUE $ebx
+# CHECK-LABEL: bb.2.loop
+# CHECK:       DBG_VALUE $ebx
+# CHECK-LABEL: bb.3.exit
+# CHECK:       DBG_VALUE $ebx
+--- |
+  ; ModuleID = 'asdf'
+  source_filename = "asdf.ll"
+  target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+  target triple = "x86_64-unknown-unknown"
+
+  @glob = global i32 0
+
+  declare i1 @booler()
+
+  declare i32 @geti32()
+
+  declare void @escape(i32)
+
+  ; Function Attrs: nounwind readnone speculatable willreturn
+  declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+  define i32 @foo() !dbg !4 {
+  entry:
+    %bar = call i32 @geti32(), !dbg !10
+    call void @llvm.dbg.value(metadata i32 %bar, metadata !9, metadata !DIExpression()), !dbg !10
+    br label %loop
+
+  loop:                                             ; preds = %loop2, %entry
+    call void @escape(i32 %bar)
+    %retval = call i1 @booler(), !dbg !10
+    br i1 %retval, label %loop2, label %exit
+
+  loop2:                                            ; preds = %loop
+    store i32 %bar, i32* @glob
+    br label %loop
+
+  exit:                                             ; preds = %loop
+    ret i32 %bar
+  }
+
+  ; Function Attrs: nounwind
+  declare void @llvm.stackprotector(i8*, i8**)
+
+  !llvm.module.flags = !{!0, !1}
+  !llvm.dbg.cu = !{!2}
+
+  !0 = !{i32 2, !"Debug Info Version", i32 3}
+  !1 = !{i32 2, !"Dwarf Version", i32 4}
+  !2 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !3, producer: "beards", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug)
+  !3 = !DIFile(filename: "bees.cpp", directory: ".")
+  !4 = distinct !DISubprogram(name: "nope", scope: !3, file: !3, line: 1, type: !5, spFlags: DISPFlagDefinition, unit: !2, retainedNodes: !8)
+  !5 = !DISubroutineType(types: !6)
+  !6 = !{!7}
+  !7 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed)
+  !8 = !{!9}
+  !9 = !DILocalVariable(name: "toast", scope: !4, file: !3, line: 1, type: !7)
+  !10 = !DILocation(line: 1, scope: !4)
+
+...
+---
+name:            foo
+tracksRegLiveness: true
+frameInfo:
+  stackSize:       8
+  offsetAdjustment: -8
+  adjustsStack:    true
+  hasCalls:        true
+  cvBytesOfCalleeSavedRegisters: 8
+fixedStack:
+  - { id: 0, type: spill-slot, offset: -16, size: 8, alignment: 16, stack-id: default,
+      callee-saved-register: '$rbx', callee-saved-restored: true, debug-info-variable: '',
+      debug-info-expression: '', debug-info-location: '' }
+stack:           []
+body:             |
+  bb.0.entry:
+    successors: %bb.1(0x80000000)
+    liveins: $rbx
+
+    frame-setup PUSH64r killed $rbx, implicit-def $rsp, implicit $rsp, debug-location !10
+    CFI_INSTRUCTION def_cfa_offset 16
+    CFI_INSTRUCTION offset $rbx, -16
+    CALL64pcrel32 @geti32, csr_64, implicit $rsp, implicit $ssp, implicit-def $rsp, implicit-def $ssp, implicit-def $eax, debug-location !10
+    DBG_VALUE $eax, $noreg, !9, !DIExpression(), debug-location !10
+    $ebx = MOV32rr killed $eax, debug-location !10
+    JMP_1 %bb.1
+
+  bb.1.loop2:
+    successors: %bb.2
+    liveins: $ebx
+
+    MOV32mr $rip, 1, $noreg, @glob, $noreg, renamable $ebx :: (store 4 into @glob)
+
+  bb.2.loop:
+    successors: %bb.1, %bb.3
+    liveins: $ebx
+
+    $edi = MOV32rr $ebx
+    CALL64pcrel32 @escape, csr_64, implicit $rsp, implicit $ssp, implicit killed $edi, implicit-def $rsp, implicit-def $ssp
+    CALL64pcrel32 @booler, csr_64, implicit $rsp, implicit $ssp, implicit-def $rsp, implicit-def $ssp, implicit-def $al, debug-location !10
+    TEST8ri killed renamable $al, 1, implicit-def $eflags
+    JCC_1 %bb.1, 5, implicit $eflags
+
+  bb.3.exit:
+    liveins: $ebx
+
+    $eax = MOV32rr killed $ebx
+    $rbx = frame-destroy POP64r implicit-def $rsp, implicit $rsp
+    CFI_INSTRUCTION def_cfa_offset 8
+    RETQ $eax
+
+...

llvm/trunk/test/DebugInfo/X86/DW_AT_location-reference.ll

 ;   while (x & 2) { x *= a; }
 ;   a = g(0, x);
 ; }
 
 ; // The 'x' variable and its symbol reference location
 ; CHECK: .debug_info contents:
 ; CHECK:      DW_TAG_variable
 ; CHECK-NEXT:   DW_AT_location [DW_FORM_sec_offset] (0x00000000
-; Check that the location contains only 4 ranges - this verifies that the 4th
-; and 5th ranges were successfully merged into a single range.
-; CHECK-NEXT:   [0x{{[0-9a-f]*}}, 0x{{[0-9a-f]*}}):
-; CHECK-NEXT:   [0x{{[0-9a-f]*}}, 0x{{[0-9a-f]*}}):
+; Check that the location contains only 2 ranges.
 ; CHECK-NEXT:   [0x{{[0-9a-f]*}}, 0x{{[0-9a-f]*}}):
 ; CHECK-NEXT:   [0x{{[0-9a-f]*}}, 0x{{[0-9a-f]*}}): {{.*}})
 ; CHECK-NEXT:   DW_AT_name {{.*}} "x"
 ; CHECK-NEXT:   DW_AT_decl_file
 ; CHECK-NEXT:   DW_AT_decl_line
 ; CHECK-NEXT:   DW_AT_type
 
 ; Check that we have no relocations in Darwin's output.

llvm/trunk/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"
+; Second function @baz added with an even tighter loop -- this tests different
+; code-paths through LiveDebugValues. Any blocks with an incoming backedge need
+; reconsideration after the parent of the backedge has had its OutLocs
+; initialized, even if OutLocs hasn't changed.
 ;
+; Third function @quux tests that we don't delete too many variable locations.
+; A variable that is live across the body of the loop should maintain its
+; location across that loop, and not be invalidated.
+;
+; CHECK: ![[FOOVARNUM:[0-9]+]] = !DILocalVariable(name: "toast"
+; CHECK: ![[BAZVARNUM:[0-9]+]] = !DILocalVariable(name: "crumpets"
+; CHECK: ![[QUUXVARNUM:[0-9]+]] = !DILocalVariable(name: "teacake"
+;
+; foo tests
+; CHECK-LABEL: bb.1.loop
+; CHECK-NOT:   DBG_VALUE
+; CHECK-LABEL: CALL64pcrel32 @booler
+; CHECK:       DBG_VALUE 0, $noreg, ![[FOOVARNUM]]
+;
+; baz tests
+; CHECK-LABEL: name: baz
 ; CHECK-LABEL: bb.1.loop
 ; CHECK-NOT:   DBG_VALUE
 ; CHECK-LABEL: CALL64pcrel32 @booler
-; CHECK:       DBG_VALUE 0, $noreg, ![[VARNUM]]
+; CHECK:       DBG_VALUE 0, $noreg, ![[BAZVARNUM]]
+;
+; quux tests -- the variable arrives in $edi, should get a non-undef location
+; before the loop, and its position re-stated in each block.
+; CHECK-LABEL: name: quux
+; CHECK:       DBG_VALUE $edi, $noreg, ![[QUUXVARNUM]]
+; CHECK:       DBG_VALUE [[QUUXLOC:[a-zA-Z0-9$_]+]], $noreg, ![[QUUXVARNUM]]
+; CHECK-LABEL: bb.1.loop
+; CHECK:       DBG_VALUE [[QUUXLOC]], $noreg, ![[QUUXVARNUM]]
+; CHECK-NOT:   DBG_VALUE $noreg
+; CHECK-LABEL: bb.2.exit
+; CHECK:       DBG_VALUE [[QUUXLOC]], $noreg, ![[QUUXVARNUM]]
+; CHECK-NOT:   DBG_VALUE $noreg
 
 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
 }
 
+define i32 @baz(i32 %bar) !dbg !104 {
+entry:
+  call void @llvm.dbg.value(metadata i32 %bar, metadata !103, metadata !DIExpression()), !dbg !106
+  br label %loop
+loop:
+  call void @escape(i32 %bar)
+  %retval = call i1 @booler(), !dbg !106
+  call void @llvm.dbg.value(metadata i32 0, metadata !103, metadata !DIExpression()), !dbg !106
+  br i1 %retval, label %loop, label %exit
+exit:
+  ret i32 %bar
+}
+
+define i32 @quux(i32 %bar) !dbg !204 {
+entry:
+  ; %bar will be placed in a nonvolatile or spill location for the loop,
+  ; before being returned later.
+  call void @llvm.dbg.value(metadata i32 %bar, metadata !203, metadata !DIExpression()), !dbg !206
+  br label %loop
+loop:
+  %retval = call i1 @booler(), !dbg !206
+  br i1 %retval, label %loop, label %exit
+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)
+!103 = !DILocalVariable(name: "crumpets", scope: !104, file: !2, line: 1, type: !16)
+!104 = distinct !DISubprogram(name: "ribbit", scope: !2, file: !2, line: 1, spFlags: DISPFlagDefinition, unit: !1, retainedNodes: !113, type: !14, isDefinition: true)
+!106 = !DILocation(line: 1, scope: !104)
+!113 = !{!103}
+!203 = !DILocalVariable(name: "teacake", scope: !204, file: !2, line: 1, type: !16)
+!204 = distinct !DISubprogram(name: "toad", scope: !2, file: !2, line: 1, spFlags: DISPFlagDefinition, unit: !1, retainedNodes: !113, type: !14, isDefinition: true)
+!206 = !DILocation(line: 1, scope: !204)
+!213 = !{!203}