[DebugInfo] PR40010: Avoid register coalesing altering DBG_VALUE valuations

[jmorse]

Summary

This is a fix for PR40010 [0]. DBG_VALUE instructions do not contribute to the liveness of virtual registers, making them invisible to the register coaleser, which may merge new register valuations over the top of DBG_VALUEs. When this happens, new valuations can appear to debuggers that were never in the source program, which is misleading.

To avoid this, examine the debug users of the register being eliminated, and pick out any that:

1. Lie in a location where the register isn't live, and
2. Where the destination register _is_ live at that location, and has a different def.

Which means the DBG_VALUE definitely gets resurrected, with a different value. This patch can leave DBG_VALUEs of non-live registers so long as the register isn't written to.

Note this also marks use-before-any-def's as undef, if they're coalesced to a different register, as it's unclear to me how to establish which def a DBG_VALUE is supposed to refer to in that case.

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

[jmorse]

Hmmm. In retrospect, aiming to cover all cases where there's a def of the dest-reg in between the last src-def and the DBG_VALUE means considering control flow, which I haven't done.

It's probably better for now to only account for circumstances where reg-coalescing makes the DBG_VALUE live again, and thus we can be 100% confident it does the wrong thing. That more closely matches the test case uploaded.

[jmorse]

Target only DBG_VALUEs that are definitely resurrected with a different def by register coalescing.

[vsk]

Thanks for working on this.

As you pointed out in llvm.org/PR40010, we do have a general problem of leaving around DBG_VALUE instructions which should be dead/undef but aren't. Do you think it would be possible/worthwhile to diagnose this issue in MachineVerifier?

lib/CodeGen/RegisterCoalescer.cpp

1900

Using MachineRegisterInfo::reg_instructions might aid readability here. Any reason not to?

1906

Could you explain why it's sufficient to fix up coalescer pairs in which the destination is a vreg?

[jmorse]

Thanks for the review,

In D56151#1343002, @vsk wrote:

As you pointed out in llvm.org/PR40010, we do have a general problem of leaving around DBG_VALUE instructions which should be dead/undef but aren't. Do you think it would be possible/worthwhile to diagnose this issue in MachineVerifier?

IMHO that's a definite yes, eventually. It's non-trivial for a human to see where liveness starts and ends for DBG_VALUEs, but a significant liability for optimisations as they can't "see" the DBG_VALUEs they're messing with. A truly dead DBG_VALUE will be dropped anyway, because it has no meaning, so it's not a useful feature to keep.

I'm not familiar with the machine verifier, but it appears to check liveness for things like kill flags, and just ignores debug users, so enabling checking of DBG_VALUEs should be easy to implement.

(I'm preparing a patch that recovers dead DBG_VALUEs from still-live copies, which would have to change if we made dead DBG_VALUEs illegal, but that's a different matter).

lib/CodeGen/RegisterCoalescer.cpp

1900

No reason (lack of familiarity), I'll switch to that,

1906

Hmmm. I've been operating on the assumption that the coalescer only operates on vregs, but I now see that isn't necessarily the case... I'll investigate this one.

[jmorse]

On the topic of coalescing physical registers, it appears the liveness test is well defined in joinReservedPhysReg. However while absorbing all of this, I've realised that dead DBG_VALUEs of both src and dst registers can be resurrected when their intervals are joined. I'll attempt to generalise further...

[jmorse]

Here's a further revision. Two significant changes:

• Because DBG_VALUEs of either the source or destination register can be resurrected by coalescing, check both,
• There's now no attempt to check whether the two registers refer to the same value number.

Examining physical registers is only performed for the destination regnum as the CoalescerPair class cannonicalises to make any physreg the destination.

LiveIntervals isn't as strong an analysis as I'd thought, and it looks like my attempt in the previous revision to find the value the DBG_VALUE referred to before it was killed, will break in the presence of any control flow. The patch as it is will now make DBG_VALUEs undef even if the coalescing by coincidence resurrects it to the same value. IMHO this is a reasonable trade-off when we can't prove the resurrection is correct.

On a stage2 build of llvm/clang r349779 a trivial fraction of variable locations are lost by this (less than 0.01%).

It'd be great to revert this patch if we reach a state where dead DBG_VALUEs can't make it as far as simple-register-coalescing in the future.

[aprantl]

lib/CodeGen/RegisterCoalescer.cpp

248

valuation is not a term we typically use in this context? Perhaps should the operands of the DBG_VALUE be updated?

[jmorse]

Revise comment for mergeChangesDbgValue

[jmorse]

lib/CodeGen/RegisterCoalescer.cpp

248

Updated with some new text -- I've gone for "would the def that a DBG_VALUE refers to change?", which should be precise about what the function tests for.

[bjope]

test/CodeGen/X86/pr40010.mir

82

I think you can remove all the false initializations here (keep tracksRegLiveness: true).

See: https://llvm.org/docs/MIRLangRef.html#simplifying-mir-files

89

I think the registers: section can be removed (these mapping are given by the MIR below, right?
And liveins, fixedStack, stack, constants can also be removed here, right?

See: https://llvm.org/docs/MIRLangRef.html#simplifying-mir-files

115

Maybe easier to read if you put all CHECK:s for the basic block here (consecutive lines)?
Or all checks for the function just before/after the function (might need to use # CHECK: instead of ; CHECK: depending on context.

(I've actually never used ; CHECK: within the body like this so I did not know that it works like that.)

I would probably have used something like this:

# <description of what the test is supposed to verify>
# 
# CHECK-LABEL: name:            test1
# CHECK: bb.1:
# CHECK:   %7:gr32 = ADD32rr %7
# CHECK:   DBG_VALUE $noreg
# CHECK: bb.2:

Where the CHECK-LABEL is supposed to make sure that each subtest is self-contained (do not match with anything from another subtest). This also makes it possible to skip some of the IR (since you do not need the symbolic names for the basic blocks.

[jmorse]

Trim and revise MIR test as per Björn's comments.

I've put the block of CHECKs together, which looks a lot better now.

[aprantl]

lib/CodeGen/RegisterCoalescer.cpp

1628

clang-format?

[jmorse]

clang-format-diff, whoops.

[TWeaver]

lib/CodeGen/RegisterCoalescer.cpp

1724

I believe theres a typo in this comment

We now "have" whether...

should be

We now "know" whether...

[jmorse]

Fix a comment wording.

[qcolombet]

test/CodeGen/X86/pr40010.mir

2

Use a filename that describes the problem briefly rather than referencing the PR number.

[jmorse]

Rename new test case's file name, move it to the 'DebugInfo' directory too as that seems more appropriate.

[jmorse]

Ping on this -- I think we all agree that this is a part of a large issue (DBG_VALUEs of non-live variables), but this patch is a step in the right direction.

[bjope]

FYI: I've downloaded this patch and have been running some tests (on a C code base). Lots of DBG_VALUE:s that now becomes undef. Some of them were totally wrong before (so this patch is good). But in some situations it looks like a regression. Need some more time to analyse those to find out if there is something wrong with mergingChangesDbgValue (that can be easily fixed), or to understand better why we get those regressions.

The defensive approach would of course be to land this, since it obviously fixes some "hard" faults while getting "optimized out" isn't a fault (even if it might be considered a regression). So I just want to understand that it isn't some obvious fault with the liveness checks that makes this just randomly turning DBG_VALUE:s into undef before I approve this.

[bjope]

I'll try to describe one "regression" that I've seen.

Before ISel we've got

...
%0 = tail call %struct. @llvm.phx.divm.u16.s_struct.s(i16 %a, i16 %b), !dbg !708
%.fca.0.extract = extractvalue %struct. %0, 0, !dbg !708
call void @llvm.dbg.value(metadata i16 %.fca.0.extract, metadata !686, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 16)), !dbg !709
%.fca.1.extract = extractvalue %struct. %0, 1, !dbg !708
call void @llvm.dbg.value(metadata i16 %.fca.1.extract, metadata !686, metadata !DIExpression(DW_OP_LLVM_fragment, 16, 16)), !dbg !709
...
use %.fca.0.extract
use %.fca.1.extract
...

After ISel it looks like this

...
%14:anh_0_7, %15:anh_0_7 = divm16_pseudo killed %13:anh_0_7, %7:anh_0_7, implicit-def dead $ccreg, debug-location !708; 
DBG_VALUE %14:anh_0_7, $noreg, !"cycleDiv", !DIExpression(DW_OP_LLVM_fragment, 0, 16), debug-location !709;
%0:anh_rn = COPY %15:anh_0_7, debug-location !708;
DBG_VALUE %15:anh_0_7, $noreg, !"cycleDiv", !DIExpression(DW_OP_LLVM_fragment, 16, 16), debug-location !709;
...
use %14:anh_0_7
use %0:anh:rn
...

Maybe ISel should have put the COPY to %0 after the last DBG_VALUE (now we got a dbg-use of %15 after the last non-dbg-use of %15). Or maybe it should have used %0 instead of %15 in that DBG_VALUE. Or maybe there should be one DBG_VALUE before the COPY using %15 and one after using %0.

Before simple register coalescing we get this (some more COPY instructions after expanding the pseudo that is using some hard coded physical registers):

...
208B	  divm16 0, $noreg, 0, implicit-def $a4_40, implicit-def dead $af4, implicit-def dead $ccreg, implicit-def $a5_40, implicit $a4h, implicit $a5h, debug-location !708;
224B	  %42:an40_0_7 = COPY $a4_40, debug-location !708;
240B	  %14:anh_0_7 = COPY %42.hi16:an40_0_7, debug-location !708;
256B	  %43:an40_0_7 = COPY $a5_40, debug-location !708;
272B	  %15:anh_0_7 = COPY %43.hi16:an40_0_7, debug-location !708;
	  DBG_VALUE %14:anh_0_7, $noreg, !"cycleDiv", !DIExpression(DW_OP_LLVM_fragment, 0, 16), debug-location !709;
288B	  %0:anh_0_7 = COPY %15:anh_0_7, debug-location !708;
	  DBG_VALUE %15:anh_0_7, $noreg, !"cycleDiv", !DIExpression(DW_OP_LLVM_fragment, 16, 16), debug-location !709;
...
          use %14:anh_0_7
          use %0:anh_0_7
...

Without this patch we get

...
208B	  divm16 0, $noreg, 0, implicit-def $a4_40, implicit-def dead $af4, implicit-def dead $ccreg, implicit-def $a5_40, implicit $a4h, implicit $a5h, debug-location !708;
224B	  %42:an40_0_7 = COPY $a4_40, debug-location !708;
256B	  %43:an40_0_7 = COPY $a5_40, debug-location !708;
	  DBG_VALUE %42.hi16:an40_0_7, $noreg, !"cycleDiv", !DIExpression(DW_OP_LLVM_fragment, 0, 16), debug-location !709;
	  DBG_VALUE %43.hi16:an40_0_7, $noreg, !"cycleDiv", !DIExpression(DW_OP_LLVM_fragment, 16, 16), debug-location !709;
...
          use %42.hi16:an40_0_7
          use %43.hi16:an40_0_7
...

With the patch the last DBG_VALUE is changed into using %noreg, so instead we get

...
208B	  divm16 0, $noreg, 0, implicit-def $a4_40, implicit-def dead $af4, implicit-def dead $ccreg, implicit-def $a5_40, implicit $a4h, implicit $a5h, debug-location !708;
224B	  %42:an40_0_7 = COPY $a4_40, debug-location !708;
256B	  %43:an40_0_7 = COPY $a5_40, debug-location !708;
	  DBG_VALUE %42.hi16:an40_0_7, $noreg, !"cycleDiv", !DIExpression(DW_OP_LLVM_fragment, 0, 16), debug-location !709;
	  DBG_VALUE %noreg.hi16, $noreg, !"cycleDiv", !DIExpression(DW_OP_LLVM_fragment, 16, 16), debug-location !709;
...
          use %42.hi16:an40_0_7
          use %43.hi16:an40_0_7
...

It is when analyzing the COPY to %0 that we detect that the DBG_VALUE is unsound:

272B	%15:anh_0_7 = COPY %43.hi16:an40_0_7, debug-location !708;
	Considering merging to aN40_0_7 with %15 in %43:hi16
		RHS = %15 [272r,288r:0)  0@272r weight:0.000000e+00
		LHS = %43 [256r,272r:0)  0@256r weight:0.000000e+00
		merge %15:0@272r into %43:0@256r --> @256r
		erased:	272r	%15:anh_0_7 = COPY %43.hi16:an40_0_7, debug-location !708;
		updated: 288B	%0:anh_0_7 = COPY %43.hi16:an40_0_7, debug-location !708;
		updated: DBG_VALUE %43.hi16:an40_0_7, $noreg, !"cycleDiv", !DIExpression(DW_OP_LLVM_fragment, 16, 16), debug-location !709;
Shrink: %43 [256r,288r:0)  0@256r weight:0.000000e+00
Shrunk: %43 [256r,288r:0)  0@256r weight:0.000000e+00
	Success: %15:hi16 -> %43
	Result = %43 [256r,288r:0)  0@256r weight:0.000000e+00

288B	%0:anh_0_7 = COPY %43.hi16:an40_0_7, debug-location !708;
	Considering merging to aN40_0_7 with %0 in %43:hi16
		RHS = %0 [288r,928r:0)  0@288r weight:0.000000e+00
		LHS = %43 [256r,288r:0)  0@256r weight:0.000000e+00
		merge %0:0@288r into %43:0@256r --> @256r
		erased:	288r	%0:anh_0_7 = COPY %43.hi16:an40_0_7, debug-location !708;
		updated: 928B	%54:anh_0_7 = subs_a16_a16_a16 %40:anh_0_7, %43.hi16:an40_0_7, 0, $noreg, 0, implicit-def dead $ccreg, implicit $cuc, debug-location !758;
Update of %43.hi16:an40_0_7 would be unsound, setting undef

So we have already merged aN40_0_7 with %15 in %43:hi16 and updated the DBG_VALUE to use %43:hi16 before we find it unsound. So in the past this coalescing made the DBG_VALUE sound (as it extended the live range for %43 to cover the DBG_VALUE). But with this patch we instead detect the DBG_VALUE as being unsound.

Inside mergingChangesDbgValue I can see

DbgV->dump() =>   DBG_VALUE %43.hi16:an40_0_7, $noreg, !"cycleDiv", !DIExpression(DW_OP_LLVM_fragment, 16, 16), debug-location !709;
DbgReg = 2147483691 (%43)
DstReg = 2147483691 (%43)
SrcReg = 2147483648 (%0)
SrcLive = true
DstLive = false

That is basically how far I've analysed this scenario at the moment.

Some thoughts:

• Should this be seen as a fault in ISel? We could probably get a better result if ISel worked differently. But in general I think we allow dbg-uses outside the non-dbg-live-interval, so I do not think it really is a fault.
• A late dbg-use (for an otherwise killed reg) is only unsound if the register allocator is using the allocated physical register for some other purpose. Isn't it a little bit early to detect that in the register coalescer? Maybe we need to take the register allocation into account if we want to make a better solution. Isn't LiveDebugVariables supposed to handle this?
• Is this patch really supposed to detect this DBG_VALUE as unsound? (we are not updating %43 here, we are only extending the live range to cover the DBG_VALUE that already is using %43). Should perhaps mergingChangesDbgValue return false also when (SrcLive && DstReg == DbgReg), or could this be unsound?

[bjope]

In D56151#1444227, @bjope wrote:

• Is this patch really supposed to detect this DBG_VALUE as unsound? (we are not updating %43 here, we are only extending the live range to cover the DBG_VALUE that already is using %43). Should perhaps mergingChangesDbgValue return false also when (SrcLive && DstReg == DbgReg), or could this be unsound?

I can probably answer that myself. This is after de-SSA (for awhile I didn't consider that), so I guess this is more or less exactly what this patch is supposed to detec. We do not know that SrcReg has the same value as DstReg for the full live range of SrcReg and DstReg (only at the COPY). We just merge the live ranges, but the register could have different values throughout the program. Unfortunately for my example program this will be seen as a regression since there are no redefinition of SrcReg/DstReg between the COPY and the DBG_VALUE. And the FIXME you have added on line 1974 probably covers that case.

[jmorse]

Maybe ISel should have put the COPY to %0 after the last DBG_VALUE (now we got a dbg-use of %15 after the last non-dbg-use of %15). Or maybe it should have used %0 instead of %15 in that DBG_VALUE. Or maybe there should be one DBG_VALUE before the COPY using %15 and one after using %0.

Ugh, I remember debugging into this issue now (it then fell out of my short term memory). IIRC:

• All Values used between blocks get a vreg allocated,
• When the DAG is converted to MIR instructions, each instruction (with a def) gets its own vreg number
• CopyToReg nodes then copy from a local vreg to a cross-block vreg.

In various cases this means a DBG_VALUE gets attached to a block-local vreg that immediately gets copy-killed to the cross-block vreg, which this patch then has difficulties with. Given that this is, more or less, a design feature of SelectionDAG, I guess it should be considered An Issue (TM).

Should this be seen as a fault in ISel? We could probably get a better result if ISel worked differently. But in general I think we allow dbg-uses outside the non-dbg-live-interval, so I do not think it really is a fault.

It seems to be part of the design, and I don't know SelectionDAG well enough to determine whether changing it would break assumptions elsewhere. Assuming my summary above is correct, a quick fix might be to prefer allocated vreg locations over even SDNodes when processing dbg.value intrinsics, but I haven't considered what else might go wrong.

The real trouble is that the DBG_VALUEs are correct while the MIR function is in SSA form, but when we leave it and consider liveness, they can become incorrect (or non-live at least).

A late dbg-use (for an otherwise killed reg) is only unsound if the register allocator is using the allocated physical register for some other purpose. Isn't it a little bit early to detect that in the register coalescer? Maybe we need to take the register allocation into account if we want to make a better solution. Isn't LiveDebugVariables supposed to handle this?

Alas, I believe the register coalescer is doing some of the register allocators job: consider this example, produced by mangling test2 in the added regression test:

bb.0.entry:
  successors: %bb.1(0x80000000)
  liveins: $rdi

  %1:gr32 = COPY $rdi
  %3:gr32 = MOV32r0 implicit-def dead $eflags

bb.1.start.test2:
  successors: %bb.1(0x7c000000)

  %0:gr32 = PHI %50, %bb.1.start.test2, %3, %bb.0.entry
  %50:gr32 = XOR32rr %0, %1, implicit-def dead $eflags
  DBG_VALUE %0, $noreg, !3, !DIExpression(), debug-location !5
  JMP_1 %bb.1

Full file here: https://pastebin.com/HqkCB6Bi . Important feature is that the DBG_VALUE refers to %0, which is not live. Note that XOR32rr is a two-address instruction. If I run "llc -simplify-mir in.mir -start-before=phi-node-elimination -stop-before=simple-register-coalescing -o -", the value of %0 is preserved by the two-address-instruction pass through a copy, and the DBG_VALUE refers to that. But then if you change "stop-before" to "stop-after", you can see the coalescer merges %0 and %50, and the DBG_VALUE now refers to a live copy of the result of the XOR, not the input to it. (With this patch applied, I don't believe it does). Once the coalescer has run, there's no way to recover the original behaviour AFAIK.

LiveDebugVariables discards all non-live DBG_VALUEs [0]. I tried to fight against this for a bit, but then found bugs like this (this patch) cropping up.

~

Given that we've identified this now, it's probably best to keep this & the associated patches hanging until there's a fix for this behaviour (the local/cross-function vreg copying that is). Which is awkward, but it's ages until LLVM9 branches.

[0] https://github.com/llvm-mirror/llvm/blob/19a56211e133d6981fca86913ca6b97a701cee52/lib/CodeGen/LiveDebugVariables.cpp#L626

[jmorse]

NB: I've written up a sort of broad-ish summary of what's wrong with the SelectionDAG scheduling of DBG_VALUEs in PR41583 [0], which IMO is the cause of the unfortunate variable-location droppage described above. I've got an additional patch that should go up tomorrow.

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

[jmorse]

Hi, I've uploaded D61181 with a patch that might fix those regressions -- if you happen to have any spare cycles for evaluating it that'd be appreciated.

If that patch doesn't work well though, then we're likely stuck in the tar pit with some unfortunate facts:

• Avoiding debug uses of non-live VRegs would be difficult to fix quickly,
• This patch here would lead to debug regressions if committed,
• Without this patch, disabling placeDbgValues (D58453) and the resulting greater distribution of dbg.values throughout functions would be liable to the failure mode this patch tries to fix.

[jmorse]

Ping: we should hammer out this review, seeing how the branch date for llvm-9 has been announced. Could I suggest that everyone is happy with the *implementation* of this patch, but that it's not yet agreed that it needs merging?

The patch effectively makes the codegen backend stricter about what DBG_VALUE insts it will accept, i.e. they have to refer to vregs that are alive. If it helps, this is already something that's enforced a few optimisation passes later in LiveDebugVariables [0], this patch just brings that check further forwards, due to the errors that can be introduced (described above). What's unfortunate is that this also prevents occasions where register coalescing re-enlivens DBG_VALUEs with a vreg that has the right value in it, occasions which can be generated due to limitations in SelectionDAG.

This then becomes a trade-off (see immediately preceeding comment) of whether the problem is so bad that we should trade some lost locations for getting rid of placeDbgValues. IMHO: yes, because we're trading definitely-incorrect locations for some more being optimized-out, a net reduction in error, to me. Other opinions most welcome.

[0] https://github.com/llvm/llvm-project/blob/b9f1e7b16ed2341e54b4e2033d111e7a2ca19b9a/llvm/lib/CodeGen/LiveDebugVariables.cpp#L624

[aprantl]

In D56151#1557861, @jmorse wrote:

Ping: we should hammer out this review, seeing how the branch date for llvm-9 has been announced. Could I suggest that everyone is happy with the *implementation* of this patch, but that it's not yet agreed that it needs merging?

The patch effectively makes the codegen backend stricter about what DBG_VALUE insts it will accept, i.e. they have to refer to vregs that are alive. If it helps, this is already something that's enforced a few optimisation passes later in LiveDebugVariables [0], this patch just brings that check further forwards, due to the errors that can be introduced (described above). What's unfortunate is that this also prevents occasions where register coalescing re-enlivens DBG_VALUEs with a vreg that has the right value in it, occasions which can be generated due to limitations in SelectionDAG.

This then becomes a trade-off (see immediately preceeding comment) of whether the problem is so bad that we should trade some lost locations for getting rid of placeDbgValues. IMHO: yes, because we're trading definitely-incorrect locations for some more being optimized-out, a net reduction in error, to me. Other opinions most welcome.

[0] https://github.com/llvm/llvm-project/blob/b9f1e7b16ed2341e54b4e2033d111e7a2ca19b9a/llvm/lib/CodeGen/LiveDebugVariables.cpp#L624

I'm reading this as: "this patch make debug info more accurate by rejecting invalid DBG_VALUEs earlier on, but it overshoots the target a bit and also rejects a few(?) false positives". I support this approach, as we all want to move LLVM into the "more accurate" direction, assuming that the false positives are fixable and the ratio of rejected incorrect DBG_VALUEs to false positives is favorable.

[jmorse]

Hi,

In D56151#1558161, @aprantl wrote:

I'm reading this as: "this patch make debug info more accurate by rejecting invalid DBG_VALUEs earlier on, but it overshoots the target a bit and also rejects a few(?) false positives". I support this approach, as we all want to move LLVM into the "more accurate" direction, assuming that the false positives are fixable and the ratio of rejected incorrect DBG_VALUEs to false positives is favorable.

Exactly that; on x86_64 at least from my comment here [0] the loss in variable locations is small (possibly it's larger for Bjorns arch?), but the false-positives are very obvious to the human eye, which is annoying. I don't have a feeling for the true/false ratio (I can dig into it), but again the impact is small.

(As I recall, there was no way to detect the false-positives without adding a new MachineDominatorTree analysis, which seemed excessive when we shouldn't be generating the faulty DBG_VALUEs in the first place).

[0] https://reviews.llvm.org/D56151#1346195

[aprantl]

lib/CodeGen/RegisterCoalescer.cpp

1695

source register

1709

Constant physical registers

[bjope]

LGTM as well.

I'll also share some stats after running some tests last night:

Compiled 4458 C files (using our DSP-C frontend and customized DSP backend).
Without this patch we get 1791988 "DEBUG_VALUE" comments in the resulting .s files, with the patch 1791453 (-535).
By doing a simple diff between all the .s files it seems like 753 old DEBUG_VALUE comments have been replaced by 218 new ones. And out of the new ones 183 now got "undef" as the value.

I haven't looked through all of those in detail (and I do not intend to do it either right now, not always easy to map things back to the source code to understand if it is "more correct" now or not).
What I've seen is that there are a few cases where I believe the old DEBUG_VALUE was correct and now we get "undef", and some cases where it looks like we would get faulty debug info without this patch.

FWIW, this analysis was of course not perfect when it comes to comparing the quality of debug info, but it gives some kind of measure.
My feeling is that the cases where we now lose some debug info is quite rare (at least for our DSP-C/DSP target), and the benefit of making the register coalescers handling of DBG_VALUE more sound outweigh that problem.

[jmorse]

Bjorn wrote:

My feeling is that the cases where we now lose some debug info is quite rare (at least for our DSP-C/DSP target), and the benefit of making the register coalescers handling of DBG_VALUE more sound outweigh that problem.

Awesome -- now dropping this in with a minor test change (JB_1 -> JCC_1) and comment fixes. Many thanks for all the reviews!

lib/CodeGen/RegisterCoalescer.cpp

class RegisterCoalescer : public MachineFunctionPass,
     /// If the source of a copy is defined by a
     /// trivial computation, replace the copy by rematerialize the definition.
     bool reMaterializeTrivialDef(const CoalescerPair &CP, MachineInstr *CopyMI,
                                  bool &IsDefCopy);
 
     /// Return true if a copy involving a physreg should be joined.
     bool canJoinPhys(const CoalescerPair &CP);
 
+    /// When merging DstLI into the vreg operand of the specified DBG_VALUE,
+    /// would it change the valuation of the DBG_VALUE? This can happen when
+    /// the DBG_VALUE is in a non-live range and DstLI is merged into that
+    /// range.
+    bool mergingChangesDbgValue(MachineInstr *DbgV,
+                                const LiveInterval &DstLI) const;
+
     /// Replace all defs and uses of SrcReg to DstReg and update the subregister
     /// number if it is not zero. If DstReg is a physical register and the
     /// existing subregister number of the def / use being updated is not zero,
     /// make sure to set it to the correct physical subregister.
     void updateRegDefsUses(unsigned SrcReg, unsigned DstReg, unsigned SubIdx);
 
     /// If the given machine operand reads only undefined lanes add an undef
     /// flag.
if (IsUndef) {
     // point so we have to potentially shrink the main range if the
     // use was ending a live segment there.
     LiveQueryResult Q = Int.Query(UseIdx);
     if (Q.valueOut() == nullptr)
       ShrinkMainRange = true;
   }
 }
 
+bool RegisterCoalescer::mergingChangesDbgValue(MachineInstr *DbgV,
+                                              const LiveInterval &DstLI) const {
+  assert(DbgV->isDebugValue());
+  assert(DbgV->getParent() && "DbgValue with no parent");
+  const MachineOperand &MO = DbgV->getOperand(0);
+  if (!MO.isReg())
+    return false;
+
+  SlotIndex MIIdx = LIS->getSlotIndexes()->getIndexAfter(*DbgV);
+  const LiveInterval &SrcLI = LIS->getInterval(MO.getReg());
+
+  // Now then -- is the src reg live at the point of the DBG_VALUE?
+  auto LII = SrcLI.find(MIIdx);
+  if (LII != SrcLI.end() && LII->contains(MIIdx))
+    // Reg is live across the DBG_VALUE, so coalescing will protect against
+    // its valuation changing.
+    return false;
+
+  auto getPriorDef = [](SlotIndex MI,
+                               const LiveInterval &LI) -> const VNInfo * {
+    auto LII = LI.find(MI);
+
+    // If the interval is live at the slot, we can just look up the def.
+    if (LII != LI.end() && LII->contains(MI))
+      return LI.getVNInfoAt(MI);
+
+    // Is this slot ahead of all defs? We already know LII doesn't contain the
+    // slot. This also accounts for begin==end.
+    if (LII == LI.begin())
+      return nullptr;
+
+    // Get the value number for whatever was live before this slot. Move to
+    // previous interval segment, and get live VN at its end.
+    auto LIIPrev = std::prev(LII);
+    return LI.getVNInfoBefore(LIIPrev->end);
+  };
+
+  // Get whichever assignment to the vreg happened before the slot.
+  const VNInfo *SrcVN = getPriorDef(MIIdx, SrcLI);
+  const VNInfo *DstVN = getPriorDef(MIIdx, DstLI);
+
+  // If the src is a use-before-def, it's already unclear which def it was
+  // supposed to refer to, and it'll be even more unclear after we merge with
+  // the destination register. Flag this to be undef.
+  if (!SrcVN)
+    return true;
+
+  // By merging to dest, are we inserting a def between the src def and the dbg
+  // value? This includes circumstances where the dest register is defined and
+  // loses liveness, because that'll still mean something different.
+  if (DstVN)
+    return (DstVN->def < MIIdx) && (DstVN->def > SrcVN->def);
+  else
+    return false;
+}
+
 void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg,
                                           unsigned DstReg,
                                           unsigned SubIdx) {
   bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
   LiveInterval *DstInt = DstIsPhys ? nullptr : &LIS->getInterval(DstReg);
 
   if (DstInt && DstInt->hasSubRanges() && DstReg != SrcReg) {
     for (MachineOperand &MO : MRI->reg_operands(DstReg)) {
       unsigned SubReg = MO.getSubReg();
       if (SubReg == 0 || MO.isUndef())
         continue;
       MachineInstr &MI = *MO.getParent();
       if (MI.isDebugValue())
         continue;
       SlotIndex UseIdx = LIS->getInstructionIndex(MI).getRegSlot(true);
       addUndefFlag(*DstInt, UseIdx, MO, SubReg);
     }
   }
 
   SmallPtrSet<MachineInstr*, 8> Visited;
   for (MachineRegisterInfo::reg_instr_iterator
        I = MRI->reg_instr_begin(SrcReg), E = MRI->reg_instr_end();
        I != E; ) {
     MachineInstr *UseMI = &*(I++);
 
     // Each instruction can only be rewritten once because sub-register
     // composition is not always idempotent. When SrcReg != DstReg, rewriting
     // the UseMI operands removes them from the SrcReg use-def chain, but when
     // SrcReg is DstReg we could encounter UseMI twice if it has multiple
     // operands mentioning the virtual register.
     if (SrcReg == DstReg && !Visited.insert(UseMI).second)
       continue;
 
     SmallVector<unsigned,8> Ops;
     bool Reads, Writes;
     std::tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops);
 
     // If SrcReg wasn't read, it may still be the case that DstReg is live-in
     // because SrcReg is a sub-register.
     if (DstInt && !Reads && SubIdx && !UseMI->isDebugValue())
       Reads = DstInt->liveAt(LIS->getInstructionIndex(*UseMI));
 
     // Replace SrcReg with DstReg in all UseMI operands.
     for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
       MachineOperand &MO = UseMI->getOperand(Ops[i]);
 
       // Adjust <undef> flags in case of sub-register joins. We don't want to
       // turn a full def into a read-modify-write sub-register def and vice
       // versa.
       if (SubIdx && MO.isDef())
LLVM_DEBUG({
         dbgs() << printReg(CP.getSrcReg(), TRI) << " in "
                << printReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n';
     });
   }
 
   ShrinkMask = LaneBitmask::getNone();
   ShrinkMainRange = false;
 
+  // Although we can update the DBG_VALUEs to the merged register, as debug uses
+  // do not contribute to liveness it might not be a sound update. Collect
+  // DBG_VALUEs that would change value were this interval merging succeed.
+  SmallVector<MachineInstr *, 4> DbgValuesToChange;
+  for (MachineRegisterInfo::reg_instr_iterator
+           I = MRI->reg_instr_begin(CP.getSrcReg()),
+           E = MRI->reg_instr_end();
+       I != E;) {
+    MachineInstr *UseMI = &*(I++);
+    if (UseMI->isDebugValue() && UseMI->getOperand(0).isReg() &&
+        TargetRegisterInfo::isVirtualRegister(CP.getDstReg()) &&
+        mergingChangesDbgValue(UseMI, LIS->getInterval(CP.getDstReg())))
+      DbgValuesToChange.push_back(UseMI);
+  }
+
   // Okay, attempt to join these two intervals.  On failure, this returns false.
   // Otherwise, if one of the intervals being joined is a physreg, this method
   // always canonicalizes DstInt to be it.  The output "SrcInt" will not have
   // been modified, so we can use this information below to update aliases.
   if (!joinIntervals(CP)) {
     // Coalescing failed.
 
     // If definition of source is defined by trivial computation, try
bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) {
   ErasedInstrs.erase(CopyMI);
 
   // Rewrite all SrcReg operands to DstReg.
   // Also update DstReg operands to include DstIdx if it is set.
   if (CP.getDstIdx())
     updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx());
   updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx());
 
+  // The updates to these DBG_VALUEs are not sound -- mark them undef.
+  // FIXME: further analysis might recover them, this is the minimal sound
+  // solution.
+  for (MachineInstr *MI : DbgValuesToChange) {
+    assert(MI->getOperand(0).isReg());
+    LLVM_DEBUG(dbgs() << "Update of " << MI->getOperand(0) << " would be "
+                      << "unsound, setting undef\n");
+    MI->getOperand(0).setReg(0);
+  }
+
   // Shrink subregister ranges if necessary.
   if (ShrinkMask.any()) {
     LiveInterval &LI = LIS->getInterval(CP.getDstReg());
     for (LiveInterval::SubRange &S : LI.subranges()) {
       if ((S.LaneMask & ShrinkMask).none())
         continue;
       LLVM_DEBUG(dbgs() << "Shrink LaneUses (Lane " << PrintLaneMask(S.LaneMask)
                         << ")\n");

test/CodeGen/X86/pr40010.mir

+# RUN: llc %s -o - -run-pass=simple-register-coalescing | FileCheck %s
+# PR40010: DBG_VALUEs do not contribute to the liveness of virtual registers,
+# and the register coalescer would merge new live values on top of DBG_VALUEs,
+# leading to them presenting new (wrong) values to the debugger. Test that
+# when out of liveness, coalescing will mark DBG_VALUEs in non-live locations
+# as undef.
+--- |
+  ; ModuleID = './test.ll'
+  source_filename = "./test.ll"
+  target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+  ; Function Attrs: nounwind readnone speculatable
+  declare void @llvm.dbg.value(metadata, metadata, metadata) #0
+
+  ; Original IR source here:
+  define i32 @test(i32* %pin) {
+  entry:
+    br label %start.test1
+
+  start.test1:                                       ; preds = %start, %entry
+    %foo = phi i32 [ 0, %entry ], [ %bar, %start.test1 ]
+    %baz = load i32, i32* %pin, align 1
+    %qux = xor i32 %baz, 1234
+    %bar = add i32 %qux, %foo
+    call void @llvm.dbg.value(metadata i32 %foo, metadata !3, metadata !DIExpression()), !dbg !5
+    %cmp = icmp ugt i32 %bar, 1000000
+    br i1 %cmp, label %leave, label %start.test1
+
+  leave:                                            ; preds = %start
+    ret i32 %bar
+  }
+
+  ; Stubs to appease the MIR parser
+  define i32 @test2(i32* %pin) {
+  entry:
+    ret i32 0
+  start.test2:
+    ret i32 0
+  leave:
+    ret i32 0
+  }
+
+  define i32 @test3(i32* %pin) {
+  entry:
+    ret i32 0
+  start.test3:
+    ret i32 0
+  leave:
+    ret i32 0
+  }
+
+  ; Function Attrs: nounwind
+  declare void @llvm.stackprotector(i8*, i8**) #1
+
+  attributes #0 = { nounwind readnone speculatable }
+  attributes #1 = { nounwind }
+
+  !llvm.module.flags = !{!0}
+  !llvm.dbg.cu = !{!1}
+
+  !0 = !{i32 2, !"Debug Info Version", i32 3}
+  !1 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !2, producer: "beards", isOptimized: true, runtimeVersion: 4, emissionKind: FullDebug)
+  !2 = !DIFile(filename: "bees.cpp", directory: "")
+  !3 = !DILocalVariable(name: "bees", scope: !4)
+  !4 = distinct !DISubprogram(name: "nope", scope: !1, file: !2, line: 1, spFlags: DISPFlagDefinition, unit: !1)
+  !5 = !DILocation(line: 0, scope: !4)
+
+...
+---
+name:            test
+alignment:       4
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+hasWinCFI:       false
+registers:
+  - { id: 0, class: gr32, preferred-register: '' }
+  - { id: 1, class: gr32, preferred-register: '' }
+  - { id: 2, class: gr64, preferred-register: '' }
+  - { id: 3, class: gr32, preferred-register: '' }
+  - { id: 4, class: gr32, preferred-register: '' }
+  - { id: 5, class: gr32, preferred-register: '' }
+  - { id: 6, class: gr32, preferred-register: '' }
+  - { id: 7, class: gr32, preferred-register: '' }
+  - { id: 8, class: gr32, preferred-register: '' }
+liveins:
+  - { reg: '$rdi', virtual-reg: '%2' }
+fixedStack:      []
+stack:           []
+constants:       []
+body:             |
+  bb.0.entry:
+    successors: %bb.1(0x80000000)
+    liveins: $rdi
+
+    %2:gr64 = COPY killed $rdi
+    %3:gr32 = MOV32r0 implicit-def dead $eflags
+    %4:gr32 = MOV32ri 1234
+    %7:gr32 = COPY killed %3
+
+  bb.1.start.test1:
+    ; CHECK-LABEL: bb.1.start.test1
+    successors: %bb.2(0x04000000), %bb.1(0x7c000000)
+
+    %0:gr32 = COPY killed %7
+    %8:gr32 = MOV32rm %2, 1, $noreg, 0, $noreg :: (load 4 from %ir.pin, align 1)
+    %5:gr32 = COPY killed %8
+    %5:gr32 = XOR32rr %5, %4, implicit-def dead $eflags
+    %1:gr32 = COPY killed %0
+    ; We currently expect %1 and %0 to merge into %7
+    %1:gr32 = ADD32rr %1, killed %5, implicit-def dead $eflags
+    ; CHECK: %7:gr32 = ADD32rr %7
+    DBG_VALUE %0, $noreg, !3, !DIExpression(), debug-location !5
+    ; CHECK-NEXT: DBG_VALUE $noreg
+    CMP32ri %1, 1000001, implicit-def $eflags
+    %7:gr32 = COPY %1
+    JB_1 %bb.1, implicit killed $eflags
+    JMP_1 %bb.2
+
+  bb.2.leave:
+    $eax = COPY killed %1
+    RET 0, killed $eax
+
+...
+---
+name:            test2
+alignment:       4
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+hasWinCFI:       false
+registers:
+  - { id: 0, class: gr32, preferred-register: '' }
+  - { id: 1, class: gr32, preferred-register: '' }
+  - { id: 2, class: gr64, preferred-register: '' }
+  - { id: 3, class: gr32, preferred-register: '' }
+  - { id: 4, class: gr32, preferred-register: '' }
+  - { id: 5, class: gr32, preferred-register: '' }
+  - { id: 6, class: gr32, preferred-register: '' }
+  - { id: 7, class: gr32, preferred-register: '' }
+  - { id: 8, class: gr32, preferred-register: '' }
+liveins:
+  - { reg: '$rdi', virtual-reg: '%2' }
+fixedStack:      []
+stack:           []
+constants:       []
+body:             |
+  bb.0.entry:
+    successors: %bb.1(0x80000000)
+    liveins: $rdi
+
+    %2:gr64 = COPY killed $rdi
+    %3:gr32 = MOV32r0 implicit-def dead $eflags
+    %4:gr32 = MOV32ri 1234
+    %7:gr32 = COPY killed %3
+
+  bb.1.start.test2:
+    ; CHECK-LABEL: bb.1.start.test2
+    successors: %bb.2(0x04000000), %bb.1(0x7c000000)
+
+    %0:gr32 = COPY killed %7
+    %8:gr32 = MOV32rm %2, 1, $noreg, 0, $noreg :: (load 4 from %ir.pin, align 1)
+    %5:gr32 = COPY killed %8
+    %5:gr32 = XOR32rr %5, %4, implicit-def dead $eflags
+    ; %0 should be merged into %7, but as %0 is live at this location the
+    ; DBG_VALUE should be preserved and point at the operand of ADD32rr.
+    DBG_VALUE %0, $noreg, !3, !DIExpression(), debug-location !5
+    ; CHECK: DBG_VALUE %7, $noreg
+    %1:gr32 = COPY killed %0
+    %1:gr32 = ADD32rr %1, killed %5, implicit-def dead $eflags
+    ; CHECK: %7:gr32 = ADD32rr %7
+    CMP32ri %1, 1000001, implicit-def $eflags
+    %7:gr32 = COPY %1
+    JB_1 %bb.1, implicit killed $eflags
+    JMP_1 %bb.2
+
+  bb.2.leave:
+    $eax = COPY killed %1
+    RET 0, killed $eax
+
+...
+---
+name:            test3
+alignment:       4
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+hasWinCFI:       false
+registers:
+  - { id: 0, class: gr32, preferred-register: '' }
+  - { id: 1, class: gr32, preferred-register: '' }
+  - { id: 2, class: gr64, preferred-register: '' }
+  - { id: 3, class: gr32, preferred-register: '' }
+  - { id: 4, class: gr32, preferred-register: '' }
+  - { id: 5, class: gr32, preferred-register: '' }
+  - { id: 6, class: gr32, preferred-register: '' }
+  - { id: 7, class: gr32, preferred-register: '' }
+  - { id: 8, class: gr32, preferred-register: '' }
+liveins:
+  - { reg: '$rdi', virtual-reg: '%2' }
+fixedStack:      []
+stack:           []
+constants:       []
+body:             |
+  bb.0.entry:
+    successors: %bb.1(0x80000000)
+    liveins: $rdi
+
+    %2:gr64 = COPY killed $rdi
+    %3:gr32 = MOV32r0 implicit-def dead $eflags
+    %4:gr32 = MOV32ri 1234
+    %7:gr32 = COPY killed %3
+
+  bb.1.start.test3:
+    ; CHECK-LABEL: bb.1.start.test3
+    successors: %bb.2(0x04000000), %bb.1(0x7c000000)
+
+    ; This is a use-before-def, merging new registers into %0 could unsoundly
+    ; make it live again, on merge mark it undef.
+    DBG_VALUE %0, $noreg, !3, !DIExpression(), debug-location !5
+    ; CHECK: DBG_VALUE $noreg
+    %0:gr32 = COPY killed %7
+    %8:gr32 = MOV32rm %2, 1, $noreg, 0, $noreg :: (load 4 from %ir.pin, align 1)
+    %5:gr32 = COPY killed %8
+    %5:gr32 = XOR32rr %5, %4, implicit-def dead $eflags
+    %1:gr32 = COPY killed %0
+    %1:gr32 = ADD32rr %1, killed %5, implicit-def dead $eflags
+    ; Check merging happened
+    ; CHECK: %7:gr32 = ADD32rr %7
+    CMP32ri %1, 1000001, implicit-def $eflags
+    %7:gr32 = COPY %1
+    JB_1 %bb.1, implicit killed $eflags
+    JMP_1 %bb.2
+
+  bb.2.leave:
+    $eax = COPY killed %1
+    RET 0, killed $eax
+
+...