[DebugInfo][LDV] Teach LDV how to identify source variables and handle fragments

[Orlando]

Summary

Related bugs [0, 1]: 41992, 43957

This patch prevents DBG_VALUE instructions being incorrectly coalesced by LiveDebugVariables.

Currently a UserValue represents part of a source variable. A UserValue is identified by the source variable, DIExpression, and the inlined scope of the source variable. DBG_VALUES definitions are added to a particular UserValue if it can be identified by these constraints. The definitions are coalesced if they refer to the same location and are at adjacent slots.

This is a problem because arbitrary DIExpressions are used to classify the definitions. For example, a DW_OP_deref on the value presented in the DBG_VALUE shouldn't change what source variable (part) we're describing, but it will according to the existing model. Instead of looking at the whole expression to classify definitions we should just be looking at the fragment.

This patch changes the internal structure of LDV: Now DBG_VALUES are instead grouped by the Fragment of the SourceVariable (DIVariable, Inlining scope) they refer to.

When adding a value definition for a Fragment of a SourceVariable, we search for overlapping fragments within the SourceVariable and add a dummy 'blocker' definition into their location interval map to prevent adjacent locations being coalesced and the definition range being extended beyond this point.

With this patch overlapping fragments are correctly handled and arbitrary DIExpression operations are not used to classify which source variable is being referred to by the DBG_VALUES.

To give a concrete example for arbitrary DIExpression operations preventing DBG_VALUES being coalesced from pr43957:

Going into LiveDebugVariables:
DBG_VALUE 36901, $noreg, !"l_801", !DIExpression()
DBG_VALUE 36901, $noreg, !"l_801", !DIExpression(DW_OP_plus_uconst, 1, DW_OP_stack_value)

Coming out of VirtRegRewriter without this patch:
DBG_VALUE 36901, $noreg, !"l_801", !DIExpression(DW_OP_plus_uconst, 1, DW_OP_stack_value)
DBG_VALUE 36901, $noreg, !"l_801", !DIExpression() // Despite referring to the same source variable as the previous DBG_VALUE, this one isn't dropped AND has been reordered.

Coming out of VirtRegRewriter with this patch:
DBG_VALUE 36901, $noreg, !"l_801", !DIExpression(DW_OP_plus_uconst, 1, DW_OP_stack_value)

You can see a similar example for overlapping fragments by looking at pr41992.ll which covers 3 previously failing cases.

coalesce_dbg_values.cpp is a Dexter test based on the reproducer in 43957. I'm happy to discuss whether this is an appropriate case!

[0] https://bugs.llvm.org/show_bug.cgi?id=41992
[1] https://bugs.llvm.org/show_bug.cgi?id=43957

More info and notes:

1. This is loosely based on top of D68816 (adding a read-from-invalid-ptr fix), but removes or changes a lot of it, so I've included all of it in this diff.

2. I want to improve test coverage for this. I haven't managed to come up with any more just yet.

3. I had to modify llvm/test/DebugInfo/ARM/PR26163.ll to make it pass.

[aprantl]

llvm/lib/CodeGen/LiveDebugVariables.cpp

111

getExpression

113

getLocNo

326

I don't know if this helps, but in other places we conceptually treat std::pair<DILocalVariable *, FragmentInfo> as unique "variables" and the remainder expression as part of a "location".

439

Why this change?

[Orlando]

llvm/lib/CodeGen/LiveDebugVariables.cpp

326

Yes that makes sense, I can probably improve the class name and comment here.

439

This line was changed as part of the work for D68816 (see point 1 in my summary). In D68816 VRMap was a DenseMap and this has been changed to an unordered_map to avoid potentially reading from an invalid pointer.

[Orlando]

More Info about this patch: As far as LDV is concerned undefs and 'blockers' are semantically very similar. However, blockers are not emitted (as DBG_VALUES) because it is unnecessary: They are only added to UserValues with overlapping fragments for any given def, and a def implicitly terminates preceding defs with overlapping fragments [0].

[0] https://llvm.org/docs/SourceLevelDebugging.html#object-lifetime-in-optimized-code

[Orlando]

+ Improve some comments
+ rename getter/setters as Adrian requested
+ remove some whitespace changes

[Orlando]

+ Added reviewers

llvm/lib/CodeGen/LiveDebugVariables.cpp

326

These terms feel overloaded but much more descriptive. How do you feel about this kind of thing:

UserValue is now responsible for all DBG_VALUEs which refer to an exact _fragment_.

UserValue -> Fragment

UserValueGroup groups UserValues (Fragments) that refer to the same _variable_

UserValueGroup -> Variable

Maybe a suitable prefix would help too.

[TWeaver]

some super nits. Patch is huge and difficult to parse, will require several passes I feel.

llvm/lib/CodeGen/LiveDebugVariables.cpp

101

'This is acts'

should be

'This acts'

?

110–115

'May return nullptr'

Should be

'Will return nullptr'

or is there a case where it can be a dummy value and not return a nullptr?

333

We refer to? We point to?

not sure "are part of" is quite the right description here.

bit nitty I know...

[djtodoro]

@Orlando Thanks for this! Please consider splitting this into two or more patches (i.e. one for NFC and one teaching functionality).

llvm/test/DebugInfo/pr41992.ll

88

Nit: producer: "clang version 10.0.0"

[aprantl]

llvm/lib/CodeGen/LiveDebugVariables.cpp

132–133

= 0

133

= nullptr

326

UserValue is now responsible for all DBG_VALUEs which refer to an exact _fragment_.

You need to be prepared to deal with debug info were the fragments aren't always the same size. Particularly it's common to have both the entire variable and then a version of the variable being split up into fragments. In other passes I've used a concept of a non-overlapping fragment, which I believe is what you mean, but I wanted to be sure you are aware of this!

[Orlando]

Thanks all for the initial reviews.

Removing 'WIP' -- there is likely more work to do but it'll be driven by reviews at this point.

I've changed the names of some classes to better reflect what's happening and I've updated the summary for this review.

+ dexter test
+ suggested changes/nits
+ fix typo in previous update

[Orlando]

@aprantl wrote https://reviews.llvm.org/D70318#inline-635016:

@Orlando cf. the discussion in https://reviews.llvm.org/D70121

This patch could be rewritten in terms of the DebugVariable class being discussed in D70318. We'd still need to group the DebugVariables by { Variable, InlinedAt } to let us search for overlaps so it looks to me like the only benefit would be unification of representations across passes (which is important IMO).

At a glance I'm not sure how much work this would require.

[jmorse]

debuginfo-tests/dexter-tests/coalesce_dbg_values.cpp

1

This would more ideally be "UNSUPPORTED: system-windows" so that it runs on the darwin debuginfo-tests bot too.

I think there's still some uncertainty (to me) about what should go into debuginfo-tests, but integration tests for what happens when things are optimised out sounds great.

[Orlando]

Ping.

+ Update dexter test for @jmorse.
+ Small additional change to print().
+ Rebase.
+ Rephrase a small part of the summary.

@djtodoro said:

Please consider splitting this into two or more patches (i.e. one for NFC and one teaching functionality)

I'm not sure if that's possible here. Everything seems quite interdependent, and the bug fix (functionality change) happens as a result of the structural change (also a functionality change).
I could split this into two or more dependant patches and keep 'related' things together. For example, put all the debug print() updates in a single patch. Not sure that this would this help though, what do you think?
There is a very small change/fix to DbgValueLocation which I included in this patch. I could take that out (and probably should) but it won't have a noticable impact on the diff size.

@aprantl since your last review I've updated the class names and summary, how do you feel about these changes?

[Orlando]

llvm/test/DebugInfo/pr41992.ll

88

Ah forgot about this one, I'll include this in the next round of updates.

[djtodoro]

I'm not sure if that's possible here. Everything seems quite interdependent, and the bug fix (functionality change) happens as a result of the structural change (also a functionality change).
I could split this into two or more dependant patches and keep 'related' things together. For example, put all the debug print() updates in a single patch. Not sure that this would this help though, what do you think?
There is a very small change/fix to DbgValueLocation which I included in this patch. I could take that out (and probably should) but it won't have a noticable impact on the diff size.

I see. The semantic of the change does not allow us to get it shorter, so I am OK with that. Thanks for considering that!

llvm/lib/CodeGen/LiveDebugVariables.cpp

739–740

Do not need the braces anymore.

1040

Frag ==> Fragment

1485

Frag ==> Fragment

[Orlando]

ping

+ Rebase.
+ Address comments from @djtodoro.

[Orlando]

Missed one of djtodoro's comments, sorry for the spam!

[aprantl]

llvm/lib/CodeGen/LiveDebugVariables.cpp

108

DbgValueLocation() = default;

337

Should this use https://reviews.llvm.org/D70486?

[Orlando]

Thanks for taking a look @aprantl.

llvm/lib/CodeGen/LiveDebugVariables.cpp

108

I'll update this in the next revision, thanks!

337

The point of SourceVariable is to, for any given def, allow us to quickly find
overlapping fragments and explicitly terminate the range of any previous defs.

The key difference between SourceVariable and DebugVariable (from D70486)
is that a SourceVariable represents a group of fragments, and a DebugVariable
is closer to what I've called a Fragment here; it represents a unique _part of_
a variable only.

So I don't believe we can use DebugVariable in place of SourceVariable. But at
the cost of some refactoring and a couple of redundant fields (repeated
DIVariable*, DILocation*, and bool part of OptFragInfo per DebugVariable)
I could replace Fragment with DebugVariable? I do not feel particularly
strongly either way.

[djtodoro]

llvm/lib/CodeGen/LiveDebugVariables.cpp

337

The key difference between SourceVariable and DebugVariable (from D70486)
is that a SourceVariable represents a group of fragments, and a DebugVariable
is closer to what I've called a Fragment here; it represents a unique _part of_
a variable only.

Can we document this somehow?

[Orlando]

llvm/lib/CodeGen/LiveDebugVariables.cpp

337

I could certainly improve the doxygen comment. Would it be appropriate to document anywhere else?

[djtodoro]

llvm/lib/CodeGen/LiveDebugVariables.cpp

337

The doxygen comment will help. I am not sure for some other place, maybe the docs/SourceLevelDebugging is good place.

[Orlando]

Hi, sorry for the slow update.

The classes DbgValueLocation (line 144), Fragment (line 172), and SourceVariable (line 356) all have new doxygen comments.

+ Rebase
+ Address reviewer comments

Thanks,
Orlando

[djtodoro]

Thanks for this! This looks good to me now!

[Orlando]

Thanks @djtodoro for looking at this. Sorry for this really delayed response!

This was initially going to be a ping, but as a result of some light offline
discussion I have a few questions. For clarification an "overlap" here refers to
a partial overlap between fragments in DIExpressions.

There are other places in llvm which do not consider overlaps, and patches
which ignore overlaps are being accepted (e.g. D71478).

1. Do overlapping fragments in dbg.values ever occur before isel currently? I would be happy to write an IRVerifier check for this and document it somewhere if this is appropriate.

2. More radically and long term, would it be feasible to ever ban overlapping fragments in DBG_VALUEs (MIR) somehow?

As demonstrated by this patch overlapping fragments are a pain to handle
properly. The original patch D66415 was much smaller but didn't handle
overlaps.

I have gathered some stats from clang and llvm-as RelWithDebInfo builds @
llvm 3.4 by counting overlaps found in the livedebugvars pass with this patch:

Terminology:
Def: A { Variable, Scope, Fragment } tuple representing a dbg.value instance.
VarSet: A set containing all the Defs with any given Variable and Scope.
Overlaps: Sum of unique Fragment overlaps between Defs in a VarSet for each VarSet.

llvm 3.4 binary |     llvm-as |       clang
----------------|--------------------------
Num VarSets     |     2284961 |    14430359
Overlaps        |           2 |           7

These stats are only anecdotal and the results are C++ specific so any conclusion
would have to be drawn very tentatively. But:

3. I would be okay with dropping this patch in favour of cleaning up D66415 and adding a FIXME comment since this patch may be useless in the real world. What do you think?

[Orlando]

Ping. Please see my previous comment for an update on this.

[vsk]

In D70121#1824298, @Orlando wrote:

Thanks @djtodoro for looking at this. Sorry for this really delayed response!

This was initially going to be a ping, but as a result of some light offline
discussion I have a few questions. For clarification an "overlap" here refers to
a partial overlap between fragments in DIExpressions.

Apologies, I'm not up-to-date on this patch and would appreciate some clarification / a few short examples of what overlapping fragments are. Is it when you have adjacent dbg.value / DBG_VALUEs, s.t. there is some overlap in the bits they describe? So, are these valid examples? --

Example 1 (full overlap)
dbg.value(..., "var", DIExpression())
dbg.value(..., "var", DIExpression())

Example 2 (partial overlap)
dbg.value(..., "var", DIExpression(DW_OP_LLVM_fragment 0 16))
dbg.value(..., "var", DIExpression(DW_OP_LLVM_fragment 8 24)) ; bits 8-16 overlap

Example 3 (no overlap)
dbg.value(..., "var", DIExpression(DW_OP_LLVM_fragment 0 16))
dbg.value(..., "var", DIExpression(DW_OP_LLVM_fragment 16 16))

Example 3 (also no overlap)
dbg.value(..., "var", DIExpression(DW_OP_LLVM_fragment 0 16))
dbg.value(..., "other_var", DIExpression())
dbg.value(..., "var", DIExpression(DW_OP_LLVM_fragment 8 24))  ; bits 8-16 would overlap, but there's an intervening dbg.value

There are other places in llvm which do not consider overlaps, and patches
which ignore overlaps are being accepted (e.g. D71478).

I'm fuzzy on the definition here so apologies for the probably naive question, but: why are overlaps a problem? Would you mind following up on the review for D71478 describing what it's missing?

1. Do overlapping fragments in dbg.values ever occur before isel currently? I would be happy to write an IRVerifier check for this and document it somewhere if this is appropriate.

2. More radically and long term, would it be feasible to ever ban overlapping fragments in DBG_VALUEs (MIR) somehow?

As demonstrated by this patch overlapping fragments are a pain to handle
properly. The original patch D66415 was much smaller but didn't handle
overlaps.

I have gathered some stats from clang and llvm-as RelWithDebInfo builds @
llvm 3.4 by counting overlaps found in the livedebugvars pass with this patch:

Terminology:
Def: A { Variable, Scope, Fragment } tuple representing a dbg.value instance.
VarSet: A set containing all the Defs with any given Variable and Scope.
Overlaps: Sum of unique Fragment overlaps between Defs in a VarSet for each VarSet.

^ Sorry, I didn't quite parse this definition.

llvm 3.4 binary |     llvm-as |       clang
----------------|--------------------------
Num VarSets     |     2284961 |    14430359
Overlaps        |           2 |           7

These stats are only anecdotal and the results are C++ specific so any conclusion
would have to be drawn very tentatively. But:

3. I would be okay with dropping this patch in favour of cleaning up D66415 and adding a FIXME comment since this patch may be useless in the real world. What do you think?

[Orlando]

Hi @vsk, thank you for taking a look at this. Please bear with me, getting you some (relatively concise) answers it is taking a little longer than I expected but I am working on it.

[Orlando]

@vsk this is the situation as far as I understand it. I appreciate that this is
a lot of text; there is a summary at the end. I hope this helps.

Apologies, I'm not up-to-date on this patch and would appreciate some
clarification / a few short examples of what overlapping fragments are. Is it
when you have adjacent dbg.value / DBG_VALUEs, s.t. there is some overlap in
the bits they describe?

Yes, except adjacency is not part of that relationship.

Example 5
DBG_VALUE %0, $noreg, "x", DIExpression() ; DV1
...
DBG_VALUE %0, $noreg, "y", DIExpression(DW_OP_LLVM_fragment 0 16) ; DV2
...
DBG_VALUE %1, $noreg, "x", DIExpression() ; DV3 
...
DBG_VALUE %0, $noreg, "y", DIExpression(DW_OP_LLVM_fragment 8 8)  ; DV4

DV1, DV3, have fully overlapping fragments. DV2 and DV4 have partially
overlapping fragments.

So, in your example 4 the first and last DBG_VALUEs partially overlap.

are these valid examples?

Example 1: Correct - I will explicitly state "full overlap" if I must refer
           to this case.  
Example 2: Correct.
Example 3: Correct.
Example 4: Not quite, that's still a partial overlap. See above.

I'm fuzzy on the definition here so apologies for the probably naive question,
but: why are overlaps a problem?

Having to consider fragment overlaps complicates value liveness queries for any
particular bits of a source variable. 'value' here refers to the combination of
a location (e.g. vreg, const) and DIExpression (because this may add a modifier
to the location).

Would you mind following up on the review for D71478 describing what it's
missing?

Ah, looking closely at D71478 the pass will never produce wrong debuginfo. It
doesn't remove any dbg.values which _may overlap_ by ignoring the fragment part.
It takes a conservative approach, but this has no effect on the final debuginfo
so it turns out it isn't a very compelling example.

In the Example 6 below it would be safe to remove DV3, but the pass
implemented in D71478 will not currently do so because DV3 and DV2 _may
overlap_.

Example 6
dbg.value %1, "x", Fragment(0, 16) ; DV1
...
dbg.value %2, "x", Fragment(16, 16) ; DV2
...
dbg.value %1, "x", Fragment(0, 16) ; DV3

why are overlaps a problem? (continued)

LiveDebugVariables (LDV) removes DBG_VALUEs before regalloc and reinserts after.
It cannot afford to be so conservative because this reduces coverage. Before I
explain this I have to show you what is wrong with LDV currently.

LDV uses interval maps to explicitly represent the intervals that the removed
DBG_VALUEs implicitly described. The DBG_VALUEs are filtered into an interval
map based on their { Source Variable, DIExpression }. The interval map will
coalesce adjacent entries that use the same location.

Consider (interval maps before coalescing on the left):

Example 7
+------------DBG_VALUE %0, $noreg, "x", DIExpression() ; DV1
|            ...
|       +----DBG_VALUE %1, $noreg, "x", DIExpression(DW_OP_plus_uconst, 4, DW_OP_stack_value) ; DV2
|       |    ...    
+-------|----DBG_VALUE %0, $noreg, "x", DIExpression() ; DV3
|       |
DV1(%0) DV2(%1)
DV3(%0)

This approach generates incorrect debuginfo. The interval map coalesces DV3 into
DV1 because they use the same location.

Taking the same approach as D71478 and filtering only on { Source Variable }
would fix the bug described above but also may greatly reduce coverage. For
example:

Example 8
+----DBG_VALUE %0, "x", (DW_OP_LLVM_fragment 0 8) ; DV1
|    ...
+----DBG_VALUE %1, "x", (DW_OP_LLVM_fragment 8 8) ; DV2
|  
+----DBG_VALUE %0, "x", (DW_OP_LLVM_fragment 0 8) ; DV3
|
DV1(%0)
DV2(%1)
DV3(%0)

In Example 8 DV3 is not coalesced into DV1. Imagine that regalloc wants to
spill %0:

Example 9
+----DBG_VALUE %0, "x", (DW_OP_LLVM_fragment 0 8) ; DV1
|    ...
+----DBG_VALUE %1, "x", (DW_OP_LLVM_fragment 8 8) ; DV2
|    <SPILL %0 into STACK0>
+----DBG_VALUE %0, "x", (DW_OP_LLVM_fragment 0 8) ; DV3
|
DV1(%0)
DV2(%1) <----| %0 is not used in this interval in this map.
DV3(%0)      | Really, DV2 should not be in this map.

Because the spill range isn't represented in the interval map we just lose that
coverage.

Patch D66415 changes this so that the DBG_VALUEs are filtered into interval maps
based on { Source Variable, Fragment } and will coalesce adjacent entries that
use the same { Location, DIExpression }.

This method correctly handles fully overlapping fragments and non-overlapping
fragments of the same Source Variable and fixes case [0] and [1]. However, it
still produces incorrect debuginfo when presented with partially overlapping
fragments in much the same way:

Example 10
+-------------------DBG_VALUE %0, "x", (DW_OP_LLVM_fragment 0 16) ; DV1
|                   ...
|              +----DBG_VALUE %1, "x", (DW_OP_LLVM_fragment 0 8)  ; DV2
|              |    ...
+--------------|----DBG_VALUE %0, "x", (DW_OP_LLVM_fragment 0 16) ; DV3
|              |
DV1(%0, Expr0) DV2(%1, Expr1)
DV3(%0, Expr0)

DV2 will get filtered into a separate interval map and therefore DV3 and DV1
will be incorrectly coalesced.

So, the patch D66415 may cause incorrect debuginfo, but in practice it is should
cause much less than the current implementation because we are more building more
accurate intervals for any given bits.

^ Sorry, I didn't quite parse this definition.

TL;DR The upper bound of DBG_VALUEs coming into LDV with partially overlapping
fragments in a clang 3.4 RelWithDebInfo build is around 0.00005%.

Summary and questions

Partially overlapping fragments (between DBG_VALUEs) are allowed in IR and MIR
but they are not handled everywhere. For a large C++ codebase I saw a
negligible number of partial overlaps coming into LiveDebugVariablesq.

This patch (in theory) fixes the problem of overlapping fragments for LDV. But
it is large and difficult to review, so:

1. Please can we accept a patch that looks like D66415 (plus FIXME: overlaps)? It will produce incorrect debuginfo given partially overlapping fragments, but it is still strictly an improvement on the current implementation, fixes [0] and [1], and is far simpler than this patch which does handle partial overlaps.

My numbers are only anecdotal and there may be languages / situations which
necessitate partially overlapping fragments (e.g. C allows much more type
punning than C++). With this in mind:

2. It seems difficult to actually get clang to produce these pesky overlaps. Do you know of any cases where overlapping fragments in either IR or MIR are _required_ to produce correct debuginfo? Hypothetically, if it were feasible to ban partial overlaps, then D66415 would be fully correct and it would be very easy to make D71478 optimal.

Thanks,
Orlando

[0] https://bugs.llvm.org/show_bug.cgi?id=41992
[1] https://bugs.llvm.org/show_bug.cgi?id=43957

[vsk]

@Orlando thanks for your patient and thorough explanation, I really appreciate it!

In D70121#1849741, @Orlando wrote:

@vsk this is the situation as far as I understand it. I appreciate that this is
a lot of text; there is a summary at the end. I hope this helps.

Apologies, I'm not up-to-date on this patch and would appreciate some
clarification / a few short examples of what overlapping fragments are. Is it
when you have adjacent dbg.value / DBG_VALUEs, s.t. there is some overlap in
the bits they describe?

Yes, except adjacency is not part of that relationship.

Example 5
DBG_VALUE %0, $noreg, "x", DIExpression() ; DV1
...
DBG_VALUE %0, $noreg, "y", DIExpression(DW_OP_LLVM_fragment 0 16) ; DV2
...
DBG_VALUE %1, $noreg, "x", DIExpression() ; DV3 
...
DBG_VALUE %0, $noreg, "y", DIExpression(DW_OP_LLVM_fragment 8 8)  ; DV4

DV1, DV3, have fully overlapping fragments. DV2 and DV4 have partially
overlapping fragments.

So, in your example 4 the first and last DBG_VALUEs partially overlap.

are these valid examples?

Example 1: Correct - I will explicitly state "full overlap" if I must refer
           to this case.  
Example 2: Correct.
Example 3: Correct.
Example 4: Not quite, that's still a partial overlap. See above.

Got it.

I'm fuzzy on the definition here so apologies for the probably naive question,
but: why are overlaps a problem?

Having to consider fragment overlaps complicates value liveness queries for any
particular bits of a source variable. 'value' here refers to the combination of
a location (e.g. vreg, const) and DIExpression (because this may add a modifier
to the location).

Would you mind following up on the review for D71478 describing what it's
missing?

Ah, looking closely at D71478 the pass will never produce wrong debuginfo. It
doesn't remove any dbg.values which _may overlap_ by ignoring the fragment part.
It takes a conservative approach, but this has no effect on the final debuginfo
so it turns out it isn't a very compelling example.

In the Example 6 below it would be safe to remove DV3, but the pass
implemented in D71478 will not currently do so because DV3 and DV2 _may
overlap_.

Example 6
dbg.value %1, "x", Fragment(0, 16) ; DV1
...
dbg.value %2, "x", Fragment(16, 16) ; DV2
...
dbg.value %1, "x", Fragment(0, 16) ; DV3

why are overlaps a problem? (continued)

LiveDebugVariables (LDV) removes DBG_VALUEs before regalloc and reinserts after.
It cannot afford to be so conservative because this reduces coverage. Before I
explain this I have to show you what is wrong with LDV currently.

LDV uses interval maps to explicitly represent the intervals that the removed
DBG_VALUEs implicitly described. The DBG_VALUEs are filtered into an interval
map based on their { Source Variable, DIExpression }. The interval map will
coalesce adjacent entries that use the same location.

Consider (interval maps before coalescing on the left):

Example 7
+------------DBG_VALUE %0, $noreg, "x", DIExpression() ; DV1
|            ...
|       +----DBG_VALUE %1, $noreg, "x", DIExpression(DW_OP_plus_uconst, 4, DW_OP_stack_value) ; DV2
|       |    ...    
+-------|----DBG_VALUE %0, $noreg, "x", DIExpression() ; DV3
|       |
DV1(%0) DV2(%1)
DV3(%0)

This approach generates incorrect debuginfo. The interval map coalesces DV3 into
DV1 because they use the same location.

Let me see if I can restate that correctly. So, the problem here is: for the list of user-values tracked by the interval map for the range containing [DV1, DV3], there are two entries: one for {DV1, DV3} (coalesced), and another for {DV2}. This would result in "x" being interpreted as %1 + 4 instead of %0 in that interval (by the debugger)?

Taking the same approach as D71478 and filtering only on { Source Variable }
would fix the bug described above but also may greatly reduce coverage. For
example:

IIUC that would essentially make fragments not 'work', or appear fully, in debug sessions? As you'd only ever see the the last fragment described in an interval?

Example 8
+----DBG_VALUE %0, "x", (DW_OP_LLVM_fragment 0 8) ; DV1
|    ...
+----DBG_VALUE %1, "x", (DW_OP_LLVM_fragment 8 8) ; DV2
|  
+----DBG_VALUE %0, "x", (DW_OP_LLVM_fragment 0 8) ; DV3
|
DV1(%0)
DV2(%1)
DV3(%0)

In Example 8 DV3 is not coalesced into DV1. Imagine that regalloc wants to
spill %0:

Example 9
+----DBG_VALUE %0, "x", (DW_OP_LLVM_fragment 0 8) ; DV1
|    ...
+----DBG_VALUE %1, "x", (DW_OP_LLVM_fragment 8 8) ; DV2
|    <SPILL %0 into STACK0>
+----DBG_VALUE %0, "x", (DW_OP_LLVM_fragment 0 8) ; DV3
|
DV1(%0)
DV2(%1) <----| %0 is not used in this interval in this map.
DV3(%0)      | Really, DV2 should not be in this map.

Because the spill range isn't represented in the interval map we just lose that
coverage.

Patch D66415 changes this so that the DBG_VALUEs are filtered into interval maps
based on { Source Variable, Fragment } and will coalesce adjacent entries that
use the same { Location, DIExpression }.

Ah, sgtm, then.

This method correctly handles fully overlapping fragments and non-overlapping
fragments of the same Source Variable and fixes case [0] and [1]. However, it
still produces incorrect debuginfo when presented with partially overlapping
fragments in much the same way:

Example 10
+-------------------DBG_VALUE %0, "x", (DW_OP_LLVM_fragment 0 16) ; DV1
|                   ...
|              +----DBG_VALUE %1, "x", (DW_OP_LLVM_fragment 0 8)  ; DV2
|              |    ...
+--------------|----DBG_VALUE %0, "x", (DW_OP_LLVM_fragment 0 16) ; DV3
|              |
DV1(%0, Expr0) DV2(%1, Expr1)
DV3(%0, Expr0)

DV2 will get filtered into a separate interval map and therefore DV3 and DV1
will be incorrectly coalesced.

I don't think we should ban these partial overlaps from showing up in IR, as I can imagine situations where this sort of IR is legitimately describing the known bits in a value. What we might consider doing to make LDV more conservative is a) identifying partial overlaps in a dbg.value pack using a backwards scan and b) deleting any earlier dbg.values which overlap with bits described later in the pack. That should be conservatively correct, and wouldn't require changing the interval map structure?

So, the patch D66415 may cause incorrect debuginfo, but in practice it is should
cause much less than the current implementation because we are more building more
accurate intervals for any given bits.

^ Sorry, I didn't quite parse this definition.

TL;DR The upper bound of DBG_VALUEs coming into LDV with partially overlapping
fragments in a clang 3.4 RelWithDebInfo build is around 0.00005%.

Summary and questions

Partially overlapping fragments (between DBG_VALUEs) are allowed in IR and MIR
but they are not handled everywhere. For a large C++ codebase I saw a
negligible number of partial overlaps coming into LiveDebugVariablesq.

This patch (in theory) fixes the problem of overlapping fragments for LDV. But
it is large and difficult to review, so:

1. Please can we accept a patch that looks like D66415 (plus FIXME: overlaps)? It will produce incorrect debuginfo given partially overlapping fragments, but it is still strictly an improvement on the current implementation, fixes [0] and [1], and is far simpler than this patch which does handle partial overlaps.

Sgtm, I very strongly feel that we should handle the 99.99995% case first and then handle the rest later.

My numbers are only anecdotal and there may be languages / situations which
necessitate partially overlapping fragments (e.g. C allows much more type
punning than C++). With this in mind:

2. It seems difficult to actually get clang to produce these pesky overlaps. Do you know of any cases where overlapping fragments in either IR or MIR are _required_ to produce correct debuginfo?

Anything I'd write here would be highly contrived, but I don't believe that these overlaps are senseless. E.g. we see this in IR all the time:

dbg.value(i32 0, "x", DIExpression())
dbg.value(i32 1, "x", DIExpression())

and this is seen as well-defined.

Hypothetically, if it were feasible to ban partial overlaps, then D66415
would be fully correct and it would be very easy to make D71478 optimal.

Thanks,
Orlando

[0] https://bugs.llvm.org/show_bug.cgi?id=41992
[1] https://bugs.llvm.org/show_bug.cgi?id=43957

[Orlando]

Let me see if I can restate that correctly. So, the problem here is: for the list of user-values tracked by the interval map for the range containing [DV1, DV3], there are two entries: one for {DV1, DV3} (coalesced), and another for {DV2}. This would result in "x" being interpreted as %1 + 4 instead of %0 in that interval (by the debugger)?

Short answer: yes, that is the behaviour we observe in the debugger. Longer
answer: the cause of the issue is slightly different to how I read your
explanation. The core problem here is that in this situation _two_ interval maps
are created instead of one:

A: { [DV1, DV3), [DV3, ...) }
   ** Coalesce these adjacent ranges because they both use the same location (%0) **
   { [DV1, ...) }
B: { [DV2, ...) }

This results in "x" being interpreted as %1 + 4 in the range [DV2, ...). As
stated previously this happens because of the method we use currently to filter
DBG_VALUEs into the 'correct' interval maps.

In this example, to get correct debuginfo, we would want to see the filter
changed so that all of these DBG_VALUEs end up in the same map, and slightly
different coalescing rules (e.g. D66415):

C: { [DV1, DV2), [DV2, DV3), [DV3, ...) }
   ** No coalescing because no adjacent ranges use the same location AND expression. **

Anything I'd write here would be highly contrived, but I don't believe that these overlaps are senseless. E.g. we see this in IR all the time:

dbg.value(i32 0, "x", DIExpression())
dbg.value(i32 1, "x", DIExpression())

and this is seen as well-defined.

Sorry, this question was badly written. I meant to ask if we could ever consider
banning _paritally_ overlapping fragments. But you do answer this elsewhere anyway:

I don't think we should ban these partial overlaps from showing up in IR, as I can
imagine situations where this sort of IR is legitimately describing the known bits
in a value. What we might consider doing to make LDV more conservative is a)
identifying partial overlaps in a dbg.value pack using a backwards scan and b)
deleting any earlier dbg.values which overlap with bits described later in the
pack. That should be conservatively correct, and wouldn't require changing the
interval map structure?

IIUC I'm not sure that works with this example?

DBG_VALUE %0, "x", (DW_OP_LLVM_fragment 00 16) ; DV1
...
DBG_VALUE %1, "x", (DW_OP_LLVM_fragment 00 16) ; DV2
DBG_VALUE %0, "x", (DW_OP_LLVM_fragment 08 32) ; DV3
...
DBG_VALUE %0, "x", (DW_OP_LLVM_fragment 00 16) ; DV4

Going forward, I will:

1. Abandon this patch (for now...)
2. Touch-up and reopen D66415 (fixes the 99.99995% case)

Thank you for sticking with me on this one!

[Orlando]

I've opened a stack of patches starting at D74052 which implement the 99.99...% fix (handle fully overlapping fragments) discussed above.

debuginfo-tests/dexter-tests/coalesce_dbg_values.cpp

+// REQUIRES: system-linux
+//
+// RUN: %dexter --fail-lt 1.0 -w --builder 'clang' \
+// RUN:      --debugger 'lldb' --cflags '-O3 -g' -- %s
+char a, b;
+int main() {
+  --b;
+  unsigned var = 36901;
+  ++var;
+  if (a) // DexLabel('watch')
+    b = 0;
+}
+
+// DexExpectWatchValue('var', 36902, on_line='watch')

llvm/lib/CodeGen/LiveDebugVariables.cpp

 }
 
 LiveDebugVariables::LiveDebugVariables() : MachineFunctionPass(ID) {
   initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
 }
 
 enum : unsigned { UndefLocNo = ~0U };
 
-/// Describes a location by number along with some flags about the original
-/// usage of the location.
+/// Describes a location by number. Keeps track of the original DIExpression
+/// to prevent adjacent locations coalescing in the interval map if they
+/// don't have the same expression. In addition, a nullptr Expression and undef
+/// location represents a dummy blocker value. This acts like an undef except it
+/// will not be emitted as a DBG_VALUE.
 class DbgValueLocation {
 public:
-  DbgValueLocation(unsigned LocNo)
-      : LocNo(LocNo) {
-    static_assert(sizeof(*this) == sizeof(unsigned), "bad bitfield packing");
-    assert(locNo() == LocNo && "location truncation");
-  }
+  DbgValueLocation(unsigned LocNo, const DIExpression *Expr)
+      : LocNo(LocNo), Expression(Expr) {}
 
-  DbgValueLocation() : LocNo(0) {}
+  DbgValueLocation() : LocNo(0), Expression(nullptr) {}
 
-  unsigned locNo() const {
-    // Fix up the undef location number, which gets truncated.
-    return LocNo == INT_MAX ? UndefLocNo : LocNo;
-  }
-  bool isUndef() const { return locNo() == UndefLocNo; }
+  /// Will return nullptr if this is a dummy value.
+  const DIExpression *getExpression() const { return Expression; }
+
+  unsigned getLocNo() const { return LocNo; }
+
+  bool isUndef() const { return getLocNo() == UndefLocNo; }
 
   DbgValueLocation changeLocNo(unsigned NewLocNo) const {
-    return DbgValueLocation(NewLocNo);
+    return DbgValueLocation(NewLocNo, Expression);
   }
 
   friend inline bool operator==(const DbgValueLocation &LHS,
                                 const DbgValueLocation &RHS) {
-    return LHS.LocNo == RHS.LocNo;
+    return LHS.LocNo == RHS.LocNo && LHS.Expression == RHS.Expression;
   }
 
   friend inline bool operator!=(const DbgValueLocation &LHS,
                                 const DbgValueLocation &RHS) {
     return !(LHS == RHS);
   }
 
 private:
-  unsigned LocNo;
+  unsigned LocNo = 0;
+  const DIExpression *Expression = nullptr;
 };
 
 /// Map of where a user value is live, and its location.
 using LocMap = IntervalMap<SlotIndex, DbgValueLocation, 4>;
 
 /// Map of stack slot offsets for spilled locations.
 /// Non-spilled locations are not added to the map.
 using SpillOffsetMap = DenseMap<unsigned, unsigned>;
 
 namespace {
+/// Return a MO which represents a DBG_VALUE undef.
+static MachineOperand getUndefMO() {
+  MachineOperand MO = MachineOperand::CreateReg(0U, false);
+  MO.setIsDebug();
+  return MO;
+}
 
 class LDVImpl;
+class SourceVariable;
 
-/// A user value is a part of a debug info user variable.
+/// A Fragment is a part of a SourceVariable. It has value definitions which are
+/// live in specific intervals.
 ///
 /// A DBG_VALUE instruction notes that (a sub-register of) a virtual register
-/// holds part of a user variable. The part is identified by a byte offset.
-///
-/// UserValues are grouped into equivalence classes for easier searching. Two
-/// user values are related if they refer to the same variable, or if they are
-/// held by the same virtual register. The equivalence class is the transitive
-/// closure of that relation.
-class UserValue {
-  const DILocalVariable *Variable; ///< The debug info variable we are part of.
-  const DIExpression *Expression; ///< Any complex address expression.
-  DebugLoc dl;            ///< The debug location for the variable. This is
-                          ///< used by dwarf writer to find lexical scope.
-  UserValue *leader;      ///< Equivalence class leader.
-  UserValue *next = nullptr; ///< Next value in equivalence class, or null.
+/// holds part of a source variable. We emit a DBG_VALUE for each fragment with
+/// value definitions for each source variable.
+class Fragment {
+  /// Fragment of source variable covered.
+  DIExpression::FragmentInfo FragmentInfo;
 
   /// Numbered locations referenced by locmap.
   SmallVector<MachineOperand, 4> locations;
 
-  /// Map of slot indices where this value is live.
+  /// Map of slot indices where these values are live.
   LocMap locInts;
 
   /// Insert a DBG_VALUE into MBB at Idx for LocNo.
-  void insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx,
+  void insertDebugValue(const DIVariable *Variable, const DebugLoc &DebugLoc,
+                        MachineBasicBlock *MBB, SlotIndex StartIdx,
                         SlotIndex StopIdx, DbgValueLocation Loc, bool Spilled,
                         unsigned SpillOffset, LiveIntervals &LIS,
                         const TargetInstrInfo &TII,
                         const TargetRegisterInfo &TRI);
 
   /// Replace OldLocNo ranges with NewRegs ranges where NewRegs
   /// is live. Returns true if any changes were made.
   bool splitLocation(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
                      LiveIntervals &LIS);
 
-public:
-  /// Create a new UserValue.
-  UserValue(const DILocalVariable *var, const DIExpression *expr, DebugLoc L,
-            LocMap::Allocator &alloc)
-      : Variable(var), Expression(expr), dl(std::move(L)), leader(this),
-        locInts(alloc) {}
-
-  /// Get the leader of this value's equivalence class.
-  UserValue *getLeader() {
-    UserValue *l = leader;
-    while (l != l->leader)
-      l = l->leader;
-    return leader = l;
-  }
-
-  /// Return the next UserValue in the equivalence class.
-  UserValue *getNext() const { return next; }
-
-  /// Does this UserValue match the parameters?
-  bool match(const DILocalVariable *Var, const DIExpression *Expr,
-             const DILocation *IA) const {
-    // FIXME: The fragment should be part of the equivalence class, but not
-    // other things in the expression like stack values.
-    return Var == Variable && Expr == Expression && dl->getInlinedAt() == IA;
-  }
-
-  /// Merge equivalence classes.
-  static UserValue *merge(UserValue *L1, UserValue *L2) {
-    L2 = L2->getLeader();
-    if (!L1)
-      return L2;
-    L1 = L1->getLeader();
-    if (L1 == L2)
-      return L1;
-    // Splice L2 before L1's members.
-    UserValue *End = L2;
-    while (End->next) {
-      End->leader = L1;
-      End = End->next;
-    }
-    End->leader = L1;
-    End->next = L1->next;
-    L1->next = L2;
-    return L1;
-  }
-
   /// Return the location number that matches Loc.
   ///
   /// For undef values we always return location number UndefLocNo without
   /// inserting anything in locations. Since locations is a vector and the
   /// location number is the position in the vector and UndefLocNo is ~0,
   /// we would need a very big vector to put the value at the right position.
   unsigned getLocationNo(const MachineOperand &LocMO) {
     if (LocMO.isReg()) {
class Fragment {
   }
 
   /// Remove (recycle) a location number. If \p LocNo still is used by the
   /// locInts nothing is done.
   void removeLocationIfUnused(unsigned LocNo) {
     // Bail out if LocNo still is used.
     for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) {
       DbgValueLocation Loc = I.value();
-      if (Loc.locNo() == LocNo)
+      if (Loc.getLocNo() == LocNo)
         return;
     }
     // Remove the entry in the locations vector, and adjust all references to
     // location numbers above the removed entry.
     locations.erase(locations.begin() + LocNo);
     for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) {
       DbgValueLocation Loc = I.value();
-      if (!Loc.isUndef() && Loc.locNo() > LocNo)
-        I.setValueUnchecked(Loc.changeLocNo(Loc.locNo() - 1));
+      if (!Loc.isUndef() && Loc.getLocNo() > LocNo)
+        I.setValueUnchecked(Loc.changeLocNo(Loc.getLocNo() - 1));
     }
   }
 
+public:
+  Fragment(const Fragment &) = delete;
+
+  /// Create a new Fragment.
+  Fragment(DIExpression::FragmentInfo FragInfo, LocMap::Allocator &alloc)
+      : FragmentInfo(FragInfo), locInts(alloc) {}
+
   /// Ensure that all virtual register locations are mapped.
   void mapVirtRegs(LDVImpl *LDV);
 
-  /// Add a definition point to this value.
-  void addDef(SlotIndex Idx, const MachineOperand &LocMO) {
-    DbgValueLocation Loc(getLocationNo(LocMO));
+  /// Add a value definition point for this fragment.
+  void addDef(SlotIndex Idx, const MachineOperand &LocMO,
+              const DIExpression *Expr) {
+    DbgValueLocation Loc(getLocationNo(LocMO), Expr);
     // Add a singular (Idx,Idx) -> Loc mapping.
     LocMap::iterator I = locInts.find(Idx);
     if (!I.valid() || I.start() != Idx)
       I.insert(Idx, Idx.getNextSlot(), Loc);
     else
       // A later DBG_VALUE at the same SlotIndex overrides the old location.
       I.setValue(Loc);
   }
 
+  /// Add a fake definition point which prevents adjacent locations coalescing.
+  void addBlocker(SlotIndex Idx) { addDef(Idx, getUndefMO(), nullptr); }
+
   /// Extend the current definition as far as possible down.
   ///
   /// Stop when meeting an existing def or when leaving the live
   /// range of VNI. End points where VNI is no longer live are added to Kills.
   ///
   /// We only propagate DBG_VALUES locally here. LiveDebugValues performs a
   /// data-flow analysis to propagate them beyond basic block boundaries.
   ///
   /// \param Idx Starting point for the definition.
   /// \param Loc Location number to propagate.
   /// \param LR Restrict liveness to where LR has the value VNI. May be null.
   /// \param VNI When LR is not null, this is the value to restrict to.
   /// \param [out] Kills Append end points of VNI's live range to Kills.
   /// \param LIS Live intervals analysis.
   void extendDef(SlotIndex Idx, DbgValueLocation Loc,
                  LiveRange *LR, const VNInfo *VNI,
                  SmallVectorImpl<SlotIndex> *Kills,
                  LiveIntervals &LIS);
 
   /// The value in LI/LocNo may be copies to other registers. Determine if
   /// any of the copies are available at the kill points, and add defs if
   /// possible.
   ///
+  /// \param SrcVar Block value intervals for overlapping fragments.
   /// \param LI Scan for copies of the value in LI->reg.
   /// \param LocNo Location number of LI->reg.
   /// \param Kills Points where the range of LocNo could be extended.
   /// \param [in,out] NewDefs Append (Idx, LocNo) of inserted defs here.
   void addDefsFromCopies(
-      LiveInterval *LI, unsigned LocNo,
+      SourceVariable &SrcVar, LiveInterval *LI, DbgValueLocation Loc,
       const SmallVectorImpl<SlotIndex> &Kills,
       SmallVectorImpl<std::pair<SlotIndex, DbgValueLocation>> &NewDefs,
       MachineRegisterInfo &MRI, LiveIntervals &LIS);
 
   /// Compute the live intervals of all locations after collecting all their
   /// def points.
-  void computeIntervals(MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI,
-                        LiveIntervals &LIS, LexicalScopes &LS);
+  void computeIntervals(SourceVariable &SrcVar, MachineRegisterInfo &MRI,
+                        const TargetRegisterInfo &TRI, LiveIntervals &LIS,
+                        LexicalScopes &LS);
 
   /// Replace OldReg ranges with NewRegs ranges where NewRegs is
   /// live. Returns true if any changes were made.
   bool splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs,
                      LiveIntervals &LIS);
 
   /// Rewrite virtual register locations according to the provided virtual
   /// register map. Record the stack slot offsets for the locations that
   /// were spilled.
   void rewriteLocations(VirtRegMap &VRM, const MachineFunction &MF,
                         const TargetInstrInfo &TII,
                         const TargetRegisterInfo &TRI,
                         SpillOffsetMap &SpillOffsets);
 
   /// Recreate DBG_VALUE instruction from data structures.
-  void emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS,
+  void emitDebugValues(const DIVariable *Variable, const DebugLoc &DebugLoc,
+                       VirtRegMap *VRM, LiveIntervals &LIS,
                        const TargetInstrInfo &TII,
                        const TargetRegisterInfo &TRI,
                        const SpillOffsetMap &SpillOffsets);
 
-  /// Return DebugLoc of this UserValue.
-  DebugLoc getDebugLoc() { return dl;}
+  /// Returns true if FragInfo covers exactly the same bits as this fragment.
+  bool match(DIExpression::FragmentInfo FragInfo) {
+    return FragmentInfo == FragInfo;
+  }
+
+  /// Returns true if FragInfo covers any of the same bits as this fragment.
+  bool overlap(DIExpression::FragmentInfo FragInfo) {
+    return DIExpression::fragmentsOverlap(FragmentInfo, FragInfo);
+  }
+
+  void print(raw_ostream &, const TargetRegisterInfo *);
+  void print(raw_ostream &, const DIVariable *, const DebugLoc &,
+             const TargetRegisterInfo *);
+};
+
+/// A SourceVariable has a set of Fragments. Each Fragment has value definitions
+/// which are live in specific intervals.
+class SourceVariable {
+  using FragmentInfo = DIExpression::FragmentInfo;
+
+  /// A DefaultFragment covers the whole variable.
+  static const FragmentInfo DefaultFragment;
+
+  /// The debug info variable we are describing.
+  const DILocalVariable *Variable;
+
+  /// The debug location for the variable.
+  DebugLoc DL;
+
+  /// The fragments for this variable which have definition points.
+  SmallVector<std::unique_ptr<Fragment>, 4> Fragments;
+
+  /// Allocator required for Fragment ctor.
+  LocMap::Allocator &Allocator;
+
+  /// Get FragmentInfo from Expr or return DefaultFragment if there isn't one.
+  static FragmentInfo getFragmentInfo(const DIExpression *Expr);
+
+public:
+  using iterator = SmallVectorImpl<std::unique_ptr<Fragment>>::iterator;
+
+  SourceVariable() = delete;
+  SourceVariable(const DILocalVariable *Var, DebugLoc L,
+                 LocMap::Allocator &MapAllocator)
+      : Variable(Var), DL(std::move(L)), Allocator(MapAllocator) {}
+
+  /// Add a value definition point for the fragment described by Expr and add a
+  /// blocker to overlapping fragments.
+  void addDef(SlotIndex Idx, const MachineOperand &LocMO,
+              const DIExpression *Expr);
+
+  /// Add a blocker to overlapping fragments (excluding an exact match).
+  void addBlockerForOverlaps(SlotIndex Idx, const DIExpression *Expr);
+
+  const DIVariable *getVariable() const { return Variable; }
+
+  DebugLoc getDebugLoc() const { return DL; }
+
+  /// Iterate over the fragments for this variable which have definition points.
+  iterator begin() { return Fragments.begin(); }
+
+  /// Iterate over the fragments for this variable which have definition points.
+  iterator end() { return Fragments.end(); }
 
   void print(raw_ostream &, const TargetRegisterInfo *);
 };
 
 /// A user label is a part of a debug info user label.
 class UserLabel {
   const DILabel *Label; ///< The debug info label we are part of.
   DebugLoc dl;          ///< The debug location for the label. This is
class LDVImpl {
   const TargetRegisterInfo *TRI;
 
   /// Whether emitDebugValues is called.
   bool EmitDone = false;
 
   /// Whether the machine function is modified during the pass.
   bool ModifiedMF = false;
 
-  /// All allocated UserValue instances.
-  SmallVector<std::unique_ptr<UserValue>, 8> userValues;
+  /// All allocated SourceVariable instances.
+  SmallVector<std::unique_ptr<SourceVariable>, 8> sourceVariables;
 
   /// All allocated UserLabel instances.
   SmallVector<std::unique_ptr<UserLabel>, 2> userLabels;
 
-  /// Map virtual register to eq class leader.
-  using VRMap = DenseMap<unsigned, UserValue *>;
-  VRMap virtRegToEqClass;
-
-  /// Map user variable to eq class leader.
-  using UVMap = DenseMap<const DILocalVariable *, UserValue *>;
-  UVMap userVarMap;
+  /// Map virtual register to Fragments with values which use it.
+  using VRMap = std::unordered_map<unsigned, SmallVector<Fragment *, 4>>;
+  VRMap VirtRegToFragments;
+
+  /// SourceVariables are mapped to an ID for fast searching when adding
+  /// initial fragment value definitions.
+  using SourceVariableId = std::pair<const DIVariable *, const DILocation *>;
+  using SVMap = DenseMap<SourceVariableId, SourceVariable *>;
+  SVMap SourceVariableMap;
 
-  /// Find or create a UserValue.
-  UserValue *getUserValue(const DILocalVariable *Var, const DIExpression *Expr,
+  /// Find or create a SourceVariable.
+  SourceVariable *getSourceVariable(const DILocalVariable *Var,
                                     const DebugLoc &DL);
 
-  /// Find the EC leader for VirtReg or null.
-  UserValue *lookupVirtReg(unsigned VirtReg);
+  /// Return the fragments with values using VirtReg, or nullptr if non exist.
+  SmallVectorImpl<Fragment *> *lookupVirtReg(unsigned VirtReg);
 
   /// Add DBG_VALUE instruction to our maps.
   ///
   /// \param MI DBG_VALUE instruction
   /// \param Idx Last valid SLotIndex before instruction.
   ///
   /// \returns True if the DBG_VALUE instruction should be deleted.
   bool handleDebugValue(MachineInstr &MI, SlotIndex Idx);
 
   /// Add DBG_LABEL instruction to UserLabel.
   ///
   /// \param MI DBG_LABEL instruction
   /// \param Idx Last valid SlotIndex before instruction.
   ///
   /// \returns True if the DBG_LABEL instruction should be deleted.
   bool handleDebugLabel(MachineInstr &MI, SlotIndex Idx);
 
-  /// Collect and erase all DBG_VALUE instructions, adding a UserValue def
-  /// for each instruction.
+  /// Collect and erase all DBG_VALUE instructions, adding a variable fragment
+  /// value def for each instruction.
   ///
   /// \param mf MachineFunction to be scanned.
   ///
   /// \returns True if any debug values were found.
   bool collectDebugValues(MachineFunction &mf);
 
   /// Compute the live intervals of all user values after collecting all
   /// their def points.
   void computeIntervals();
 
 public:
   LDVImpl(LiveDebugVariables *ps) : pass(*ps) {}
 
   bool runOnMachineFunction(MachineFunction &mf);
 
   /// Release all memory.
   void clear() {
     MF = nullptr;
-    userValues.clear();
+    sourceVariables.clear();
     userLabels.clear();
-    virtRegToEqClass.clear();
-    userVarMap.clear();
+    VirtRegToFragments.clear();
+    SourceVariableMap.clear();
     // Make sure we call emitDebugValues if the machine function was modified.
     assert((!ModifiedMF || EmitDone) &&
            "Dbg values are not emitted in LDV");
     EmitDone = false;
     ModifiedMF = false;
   }
 
-  /// Map virtual register to an equivalence class.
-  void mapVirtReg(unsigned VirtReg, UserValue *EC);
+  /// Map virtual register to a Fragment.
+  void mapVirtReg(unsigned VirtReg, Fragment *F);
 
   /// Replace all references to OldReg with NewRegs.
   void splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs);
 
   /// Recreate DBG_VALUE instruction from data structures.
   void emitDebugValues(VirtRegMap *VRM);
 
   void print(raw_ostream&);
if (InlinedAt) {
     if (DebugLoc InlinedAtDL = InlinedAt) {
       OS << " @[";
       printDebugLoc(InlinedAtDL, OS, Ctx);
       OS << "]";
     }
   }
 }
 
-void UserValue::print(raw_ostream &OS, const TargetRegisterInfo *TRI) {
+void Fragment::print(raw_ostream &OS, const DIVariable *V, const DebugLoc &DL,
+                     const TargetRegisterInfo *TRI) {
   OS << "!\"";
-  printExtendedName(OS, Variable, dl);
+  printExtendedName(OS, V, DL);
+  OS << "\"";
+  print(OS, TRI);
+}
 
-  OS << "\"\t";
+void Fragment::print(raw_ostream &OS, const TargetRegisterInfo *TRI) {
+  OS << "\t";
   for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) {
+    if (!I.value().getExpression())
+      continue;
     OS << " [" << I.start() << ';' << I.stop() << "):";
     if (I.value().isUndef())
       OS << "undef";
-    else {
-      OS << I.value().locNo();
-    }
+    else
+      OS << I.value().getLocNo();
+    OS << *I.value().getExpression();
   }
   for (unsigned i = 0, e = locations.size(); i != e; ++i) {
     OS << " Loc" << i << '=';
     locations[i].print(OS, TRI);
   }
   OS << '\n';
 }
 
+void SourceVariable::print(raw_ostream &OS, const TargetRegisterInfo *TRI) {
+  for (auto &F : Fragments)
+    F->print(OS, Variable, DL, TRI);
+}
+
 void UserLabel::print(raw_ostream &OS, const TargetRegisterInfo *TRI) {
   OS << "!\"";
   printExtendedName(OS, Label, dl);
 
   OS << "\"\t";
   OS << loc;
   OS << '\n';
 }
 
 void LDVImpl::print(raw_ostream &OS) {
   OS << "********** DEBUG VARIABLES **********\n";
-  for (auto &userValue : userValues)
-    userValue->print(OS, TRI);
+  for (auto &SrcVar : sourceVariables)
+    SrcVar->print(OS, TRI);
   OS << "********** DEBUG LABELS **********\n";
   for (auto &userLabel : userLabels)
     userLabel->print(OS, TRI);
 }
 #endif
 
-void UserValue::mapVirtRegs(LDVImpl *LDV) {
+void Fragment::mapVirtRegs(LDVImpl *LDV) {
   for (unsigned i = 0, e = locations.size(); i != e; ++i)
     if (locations[i].isReg() &&
         Register::isVirtualRegister(locations[i].getReg()))
       LDV->mapVirtReg(locations[i].getReg(), this);
 }
 
-UserValue *LDVImpl::getUserValue(const DILocalVariable *Var,
-                                 const DIExpression *Expr, const DebugLoc &DL) {
-  UserValue *&Leader = userVarMap[Var];
-  if (Leader) {
-    UserValue *UV = Leader->getLeader();
-    Leader = UV;
-    for (; UV; UV = UV->getNext())
-      if (UV->match(Var, Expr, DL->getInlinedAt()))
-        return UV;
-  }
-
-  userValues.push_back(
-      std::make_unique<UserValue>(Var, Expr, DL, allocator));
-  UserValue *UV = userValues.back().get();
-  Leader = UserValue::merge(Leader, UV);
-  return UV;
+const DIExpression::FragmentInfo SourceVariable::DefaultFragment = {
+    std::numeric_limits<uint64_t>::max(), std::numeric_limits<uint64_t>::min()};
+
+SourceVariable::FragmentInfo
+SourceVariable::getFragmentInfo(const DIExpression *Expr) {
+  return Expr->getFragmentInfo().getValueOr(DefaultFragment);
+}
+
+void SourceVariable::addDef(SlotIndex Idx, const MachineOperand &LocMO,
+                            const DIExpression *Expr) {
+  FragmentInfo FragInfo = SourceVariable::getFragmentInfo(Expr);
+  // Search for exact matching Fragment.
+  Fragment *ExactMatch = nullptr;
+  for (auto &Fragment : Fragments) {
+    if (Fragment->match(FragInfo))
+      ExactMatch = Fragment.get();
+    // Add blocker def for any overlaps.
+    else if (Fragment->overlap(FragInfo))
+      Fragment->addBlocker(Idx);
+  }
+
+  // Create a new Fragment if there wans't one for this Fragment.
+  if (!ExactMatch) {
+    Fragments.push_back(std::make_unique<Fragment>(FragInfo, Allocator));
+    ExactMatch = Fragments.back().get();
+  }
+
+  // Add def for the fragment range.
+  ExactMatch->addDef(Idx, LocMO, Expr);
+}
+
+void SourceVariable::addBlockerForOverlaps(SlotIndex Idx,
+                                           const DIExpression *Expr) {
+  FragmentInfo FragInfo = SourceVariable::getFragmentInfo(Expr);
+  for (auto &Fragment : Fragments) {
+    if (!Fragment->overlap(FragInfo))
+      continue;
+    if (Fragment->match(FragInfo))
+      continue;
+    Fragment->addBlocker(Idx);
+  }
+}
+
+SourceVariable *LDVImpl::getSourceVariable(const DILocalVariable *Var,
+                                           const DebugLoc &DL) {
+  auto Ident = std::make_pair(Var, DL->getInlinedAt());
+  SourceVariable *&SVEntry = SourceVariableMap[Ident];
+
+  if (SVEntry)
+    return SVEntry;
+
+  sourceVariables.push_back(
+      std::make_unique<SourceVariable>(Var, DL, allocator));
+  return SVEntry = sourceVariables.back().get();
 }
 
-void LDVImpl::mapVirtReg(unsigned VirtReg, UserValue *EC) {
+void LDVImpl::mapVirtReg(unsigned VirtReg, Fragment *F) {
   assert(Register::isVirtualRegister(VirtReg) && "Only map VirtRegs");
-  UserValue *&Leader = virtRegToEqClass[VirtReg];
-  Leader = UserValue::merge(Leader, EC);
+  VirtRegToFragments[VirtReg].push_back(F);
 }
 
-UserValue *LDVImpl::lookupVirtReg(unsigned VirtReg) {
-  if (UserValue *UV = virtRegToEqClass.lookup(VirtReg))
-    return UV->getLeader();
+SmallVectorImpl<Fragment *> *LDVImpl::lookupVirtReg(unsigned VirtReg) {
+  VRMap::iterator Itr = VirtRegToFragments.find(VirtReg);
+  if (Itr != VirtRegToFragments.end())
+    return &Itr->second;
   return nullptr;
 }
 
 bool LDVImpl::handleDebugValue(MachineInstr &MI, SlotIndex Idx) {
   // DBG_VALUE loc, offset, variable
   if (MI.getNumOperands() != 4 ||
       !(MI.getOperand(1).isReg() || MI.getOperand(1).isImm()) ||
       !MI.getOperand(2).isMetadata()) {
if (!LIS->hasInterval(Reg)) {
         // is not live. Discard the DBG_VALUE.
         Discard = true;
         LLVM_DEBUG(dbgs() << "Discarding debug info (reg not live): " << Idx
                           << " " << MI);
       }
     }
   }
 
-  // Get or create the UserValue for (variable,offset) here.
+  // Get or create the Fragment for (variable,offset) here.
   assert(!MI.getOperand(1).isImm() && "DBG_VALUE with indirect flag before "
                                       "LiveDebugVariables");
   const DILocalVariable *Var = MI.getDebugVariable();
   const DIExpression *Expr = MI.getDebugExpression();
-  UserValue *UV =
-      getUserValue(Var, Expr, MI.getDebugLoc());
+  SourceVariable *SrcVar = getSourceVariable(Var, MI.getDebugLoc());
   if (!Discard)
-    UV->addDef(Idx, MI.getOperand(0));
+    SrcVar->addDef(Idx, MI.getOperand(0), Expr);
   else {
-    MachineOperand MO = MachineOperand::CreateReg(0U, false);
-    MO.setIsDebug();
-    UV->addDef(Idx, MO);
+    SrcVar->addDef(Idx, getUndefMO(), Expr);
   }
   return true;
 }
 
 bool LDVImpl::handleDebugLabel(MachineInstr &MI, SlotIndex Idx) {
   // DBG_LABEL label
   if (MI.getNumOperands() != 1 || !MI.getOperand(0).isMetadata()) {
     LLVM_DEBUG(dbgs() << "Can't handle " << MI);
for (MachineBasicBlock::iterator MBBI = MBB->begin(), MBBE = MBB->end();
         } else
           ++MBBI;
       } while (MBBI != MBBE && MBBI->isDebugInstr());
     }
   }
   return Changed;
 }
 
-void UserValue::extendDef(SlotIndex Idx, DbgValueLocation Loc, LiveRange *LR,
-                          const VNInfo *VNI, SmallVectorImpl<SlotIndex> *Kills,
-                          LiveIntervals &LIS) {
+void Fragment::extendDef(SlotIndex Idx, DbgValueLocation Loc, LiveRange *LR,
   SlotIndex Start = Idx;
   MachineBasicBlock *MBB = LIS.getMBBFromIndex(Start);
   SlotIndex Stop = LIS.getMBBEndIdx(MBB);
   LocMap::iterator I = locInts.find(Start);
 
   // Limit to VNI's live range.
   bool ToEnd = true;
   if (LR && VNI) {
void Fragment::extendDef(SlotIndex Idx, DbgValueLocation Loc, LiveRange *LR,
   // Limited by VNI's live range.
   else if (!ToEnd && Kills)
     Kills->push_back(Stop);
 
   if (Start < Stop)
     I.insert(Start, Stop, Loc);
 }
 
-void UserValue::addDefsFromCopies(
-    LiveInterval *LI, unsigned LocNo,
+void Fragment::addDefsFromCopies(
+    SourceVariable &SrcVar, LiveInterval *LI, DbgValueLocation Loc,
     const SmallVectorImpl<SlotIndex> &Kills,
     SmallVectorImpl<std::pair<SlotIndex, DbgValueLocation>> &NewDefs,
     MachineRegisterInfo &MRI, LiveIntervals &LIS) {
   if (Kills.empty())
     return;
   // Don't track copies from physregs, there are too many uses.
   if (!Register::isVirtualRegister(LI->reg))
     return;
for (MachineOperand &MO : MRI.use_nodbg_operands(LI->reg)) {
     // or it could be spilled.
     if (!Register::isVirtualRegister(DstReg))
       continue;
 
     // Is LocNo extended to reach this copy? If not, another def may be blocking
     // it, or we are looking at a wrong value of LI.
     SlotIndex Idx = LIS.getInstructionIndex(*MI);
     LocMap::iterator I = locInts.find(Idx.getRegSlot(true));
-    if (!I.valid() || I.value().locNo() != LocNo)
+    if (!I.valid() || I.value().getLocNo() != Loc.getLocNo())
       continue;
 
     if (!LIS.hasInterval(DstReg))
       continue;
     LiveInterval *DstLI = &LIS.getInterval(DstReg);
     const VNInfo *DstVNI = DstLI->getVNInfoAt(Idx.getRegSlot());
     assert(DstVNI && DstVNI->def == Idx.getRegSlot() && "Bad copy value");
     CopyValues.push_back(std::make_pair(DstLI, DstVNI));
for (unsigned j = 0, e = CopyValues.size(); j != e; ++j) {
       LocMap::iterator I = locInts.find(Idx);
       if (I.valid() && I.start() <= Idx)
         continue;
       LLVM_DEBUG(dbgs() << "Kill at " << Idx << " covered by valno #"
                         << DstVNI->id << " in " << *DstLI << '\n');
       MachineInstr *CopyMI = LIS.getInstructionFromIndex(DstVNI->def);
       assert(CopyMI && CopyMI->isCopy() && "Bad copy value");
       unsigned LocNo = getLocationNo(CopyMI->getOperand(0));
-      DbgValueLocation NewLoc(LocNo);
+      DbgValueLocation NewLoc = Loc.changeLocNo(LocNo);
       I.insert(Idx, Idx.getNextSlot(), NewLoc);
       NewDefs.push_back(std::make_pair(Idx, NewLoc));
+      SrcVar.addBlockerForOverlaps(Idx, Loc.getExpression());
       break;
     }
   }
 }
 
-void UserValue::computeIntervals(MachineRegisterInfo &MRI,
-                                 const TargetRegisterInfo &TRI,
-                                 LiveIntervals &LIS, LexicalScopes &LS) {
+void Fragment::computeIntervals(SourceVariable &SrcVar,
+                                MachineRegisterInfo &MRI,
   SmallVector<std::pair<SlotIndex, DbgValueLocation>, 16> Defs;
 
   // Collect all defs to be extended (Skipping undefs).
   for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I)
     if (!I.value().isUndef())
       Defs.push_back(std::make_pair(I.start(), I.value()));
 
   // Extend all defs, and possibly add new ones along the way.
   for (unsigned i = 0; i != Defs.size(); ++i) {
     SlotIndex Idx = Defs[i].first;
     DbgValueLocation Loc = Defs[i].second;
-    const MachineOperand &LocMO = locations[Loc.locNo()];
+    const MachineOperand &LocMO = locations[Loc.getLocNo()];
 
     if (!LocMO.isReg()) {
       extendDef(Idx, Loc, nullptr, nullptr, nullptr, LIS);
       continue;
     }
 
     // Register locations are constrained to where the register value is live.
     if (Register::isVirtualRegister(LocMO.getReg())) {
if (Register::isVirtualRegister(LocMO.getReg())) {
       // if the original location for example is %vreg0:sub_hi, and we find a
       // full register copy in addDefsFromCopies (at the moment it only handles
       // full register copies), then we must add the sub1 sub-register index to
       // the new location. However, that is only possible if the new virtual
       // register is of the same regclass (or if there is an equivalent
       // sub-register in that regclass). For now, simply skip handling copies if
       // a sub-register is involved.
       if (LI && !LocMO.getSubReg())
-        addDefsFromCopies(LI, Loc.locNo(), Kills, Defs, MRI, LIS);
+        addDefsFromCopies(SrcVar, LI, Loc, Kills, Defs, MRI, LIS);
       continue;
     }
 
     // For physregs, we only mark the start slot idx. DwarfDebug will see it
     // as if the DBG_VALUE is valid up until the end of the basic block, or
     // the next def of the physical register. So we do not need to extend the
     // range. It might actually happen that the DBG_VALUE is the last use of
     // the physical register (e.g. if this is an unused input argument to a
     // function).
   }
 
   // The computed intervals may extend beyond the range of the debug
   // location's lexical scope. In this case, splitting of an interval
   // can result in an interval outside of the scope being created,
   // causing extra unnecessary DBG_VALUEs to be emitted. To prevent
   // this, trim the intervals to the lexical scope.
 
-  LexicalScope *Scope = LS.findLexicalScope(dl);
+  LexicalScope *Scope = LS.findLexicalScope(SrcVar.getDebugLoc());
   if (!Scope)
     return;
 
   SlotIndex PrevEnd;
   LocMap::iterator I = locInts.begin();
 
   // Iterate over the lexical scope ranges. Each time round the loop
   // we check the intervals for overlap with the end of the previous
void Fragment::computeIntervals(SourceVariable &SrcVar,
   if (PrevEnd && I.start() < PrevEnd)
     I.setStopUnchecked(PrevEnd);
 }
 
 void LDVImpl::computeIntervals() {
   LexicalScopes LS;
   LS.initialize(*MF);
 
-  for (unsigned i = 0, e = userValues.size(); i != e; ++i) {
-    userValues[i]->computeIntervals(MF->getRegInfo(), *TRI, *LIS, LS);
-    userValues[i]->mapVirtRegs(this);
+  for (auto &SrcVar : sourceVariables) {
+    for (const auto &Frag : *SrcVar) {
+      Frag->computeIntervals(*SrcVar, MF->getRegInfo(), *TRI, *LIS, LS);
+      Frag->mapVirtRegs(this);
+    }
   }
 }
 
 bool LDVImpl::runOnMachineFunction(MachineFunction &mf) {
   clear();
   MF = &mf;
   LIS = &pass.getAnalysis<LiveIntervals>();
   TRI = mf.getSubtarget().getRegisterInfo();
LiveDebugVariables::~LiveDebugVariables() {
   if (pImpl)
     delete static_cast<LDVImpl*>(pImpl);
 }
 
 //===----------------------------------------------------------------------===//
 //                           Live Range Splitting
 //===----------------------------------------------------------------------===//
 
-bool
-UserValue::splitLocation(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
-                         LiveIntervals& LIS) {
+bool Fragment::splitLocation(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
+                             LiveIntervals &LIS) {
   LLVM_DEBUG({
     dbgs() << "Splitting Loc" << OldLocNo << '\t';
     print(dbgs(), nullptr);
   });
   bool DidChange = false;
   LocMap::iterator LocMapI;
   LocMapI.setMap(locInts);
   for (unsigned i = 0; i != NewRegs.size(); ++i) {
for (unsigned i = 0; i != NewRegs.size(); ++i) {
     LiveInterval::iterator LIE = LI->end();
     while (LocMapI.valid() && LII != LIE) {
       // At this point, we know that LocMapI.stop() > LII->start.
       LII = LI->advanceTo(LII, LocMapI.start());
       if (LII == LIE)
         break;
 
       // Now LII->end > LocMapI.start(). Do we have an overlap?
-      if (LocMapI.value().locNo() == OldLocNo && LII->start < LocMapI.stop()) {
+      if (LocMapI.value().getLocNo() == OldLocNo &&
+          LII->start < LocMapI.stop()) {
         // Overlapping correct location. Allocate NewLocNo now.
         if (NewLocNo == UndefLocNo) {
           MachineOperand MO = MachineOperand::CreateReg(LI->reg, false);
           MO.setSubReg(locations[OldLocNo].getSubReg());
           NewLocNo = getLocationNo(MO);
           DidChange = true;
         }
 
bool Fragment::splitLocation(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
 
   LLVM_DEBUG({
     dbgs() << "Split result: \t";
     print(dbgs(), nullptr);
   });
   return DidChange;
 }
 
-bool
-UserValue::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs,
+bool Fragment::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs,
                              LiveIntervals &LIS) {
   bool DidChange = false;
   // Split locations referring to OldReg. Iterate backwards so splitLocation can
   // safely erase unused locations.
   for (unsigned i = locations.size(); i ; --i) {
     unsigned LocNo = i-1;
     const MachineOperand *Loc = &locations[LocNo];
     if (!Loc->isReg() || Loc->getReg() != OldReg)
       continue;
     DidChange |= splitLocation(LocNo, NewRegs, LIS);
   }
   return DidChange;
 }
 
 void LDVImpl::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs) {
   bool DidChange = false;
-  for (UserValue *UV = lookupVirtReg(OldReg); UV; UV = UV->getNext())
-    DidChange |= UV->splitRegister(OldReg, NewRegs, *LIS);
+  if (auto *Fragments = lookupVirtReg(OldReg))
+    for (auto *Fragment : *Fragments)
+      DidChange |= Fragment->splitRegister(OldReg, NewRegs, *LIS);
 
   if (!DidChange)
     return;
 
   // Map all of the new virtual registers.
-  UserValue *UV = lookupVirtReg(OldReg);
+  if (auto *Fragments = lookupVirtReg(OldReg))
+    for (auto *Fragment : *Fragments)
       for (unsigned i = 0; i != NewRegs.size(); ++i)
-    mapVirtReg(NewRegs[i], UV);
+        mapVirtReg(NewRegs[i], Fragment);
 }
 
 void LiveDebugVariables::
 splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs, LiveIntervals &LIS) {
   if (pImpl)
     static_cast<LDVImpl*>(pImpl)->splitRegister(OldReg, NewRegs);
 }
 
-void UserValue::rewriteLocations(VirtRegMap &VRM, const MachineFunction &MF,
-                                 const TargetInstrInfo &TII,
-                                 const TargetRegisterInfo &TRI,
-                                 SpillOffsetMap &SpillOffsets) {
+void Fragment::rewriteLocations(VirtRegMap &VRM, const MachineFunction &MF,
   // Build a set of new locations with new numbers so we can coalesce our
   // IntervalMap if two vreg intervals collapse to the same physical location.
   // Use MapVector instead of SetVector because MapVector::insert returns the
   // position of the previously or newly inserted element. The boolean value
   // tracks if the location was produced by a spill.
   // FIXME: This will be problematic if we ever support direct and indirect
   // frame index locations, i.e. expressing both variables in memory and
   // 'int x, *px = &x'. The "spilled" bit must become part of the location.
void Fragment::rewriteLocations(VirtRegMap &VRM, const MachineFunction &MF,
   // DBG_VALUE intervals with different vregs that were allocated to the same
   // physical register.
   for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) {
     DbgValueLocation Loc = I.value();
     // Undef values don't exist in locations (and thus not in LocNoMap either)
     // so skip over them. See getLocationNo().
     if (Loc.isUndef())
       continue;
-    unsigned NewLocNo = LocNoMap[Loc.locNo()];
+    unsigned NewLocNo = LocNoMap[Loc.getLocNo()];
     I.setValueUnchecked(Loc.changeLocNo(NewLocNo));
     I.setStart(I.start());
   }
 }
 
 /// Find an iterator for inserting a DBG_VALUE instruction.
 static MachineBasicBlock::iterator
 findInsertLocation(MachineBasicBlock *MBB, SlotIndex Idx,
while (I != MBB->end() && !I->isTerminator()) {
     if (I->definesRegister(Reg, &TRI))
       // The insert location is directly after the instruction/bundle.
       return std::next(I);
     ++I;
   }
   return MBB->end();
 }
 
-void UserValue::insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx,
-                                 SlotIndex StopIdx, DbgValueLocation Loc,
-                                 bool Spilled, unsigned SpillOffset,
-                                 LiveIntervals &LIS, const TargetInstrInfo &TII,
-                                 const TargetRegisterInfo &TRI) {
+void Fragment::insertDebugValue(const DIVariable *Variable, const DebugLoc &DL,
+                                MachineBasicBlock *MBB, SlotIndex StartIdx,
   SlotIndex MBBEndIdx = LIS.getMBBEndIdx(&*MBB);
   // Only search within the current MBB.
   StopIdx = (MBBEndIdx < StopIdx) ? MBBEndIdx : StopIdx;
   MachineBasicBlock::iterator I = findInsertLocation(MBB, StartIdx, LIS);
   // Undef values don't exist in locations so create new "noreg" register MOs
   // for them. See getLocationNo().
-  MachineOperand MO = !Loc.isUndef() ?
-    locations[Loc.locNo()] :
-    MachineOperand::CreateReg(/* Reg */ 0, /* isDef */ false, /* isImp */ false,
-                              /* isKill */ false, /* isDead */ false,
-                              /* isUndef */ false, /* isEarlyClobber */ false,
-                              /* SubReg */ 0, /* isDebug */ true);
+  MachineOperand MO =
+      !Loc.isUndef() ? locations[Loc.getLocNo()]
+                     : MachineOperand::CreateReg(
+                           /* Reg */ 0, /* isDef */ false, /* isImp */ false,
 
   ++NumInsertedDebugValues;
 
-  assert(cast<DILocalVariable>(Variable)
-             ->isValidLocationForIntrinsic(getDebugLoc()) &&
+  assert(cast<DILocalVariable>(Variable)->isValidLocationForIntrinsic(DL) &&
          "Expected inlined-at fields to agree");
 
+  const DIExpression *Expr = Loc.getExpression();
+  assert(Expr && "nullptr represents dummy value.");
   // If the location was spilled, the new DBG_VALUE will be indirect. If the
   // original DBG_VALUE was indirect, we need to add DW_OP_deref to indicate
   // that the original virtual register was a pointer. Also, add the stack slot
   // offset for the spilled register to the expression.
-  const DIExpression *Expr = Expression;
   if (Spilled)
     Expr = DIExpression::prepend(Expr, DIExpression::ApplyOffset, SpillOffset);
 
   assert((!Spilled || MO.isFI()) && "a spilled location must be a frame index");
 
   do {
-    BuildMI(*MBB, I, getDebugLoc(), TII.get(TargetOpcode::DBG_VALUE),
-            Spilled, MO, Variable, Expr);
+    BuildMI(*MBB, I, DL, TII.get(TargetOpcode::DBG_VALUE), Spilled, MO,
+            Variable, Expr);
 
     // Continue and insert DBG_VALUES after every redefinition of register
     // associated with the debug value within the range
     I = findNextInsertLocation(MBB, I, StopIdx, MO, LIS, TRI);
   } while (I != MBB->end());
 }
 
 void UserLabel::insertDebugLabel(MachineBasicBlock *MBB, SlotIndex Idx,
                                  LiveIntervals &LIS,
                                  const TargetInstrInfo &TII) {
   MachineBasicBlock::iterator I = findInsertLocation(MBB, Idx, LIS);
   ++NumInsertedDebugLabels;
   BuildMI(*MBB, I, getDebugLoc(), TII.get(TargetOpcode::DBG_LABEL))
       .addMetadata(Label);
 }
 
-void UserValue::emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS,
-                                const TargetInstrInfo &TII,
-                                const TargetRegisterInfo &TRI,
-                                const SpillOffsetMap &SpillOffsets) {
+void Fragment::emitDebugValues(const DIVariable *Variable, const DebugLoc &DL,
+                               VirtRegMap *VRM, LiveIntervals &LIS,
   MachineFunction::iterator MFEnd = VRM->getMachineFunction().end();
 
   for (LocMap::const_iterator I = locInts.begin(); I.valid();) {
     SlotIndex Start = I.start();
     SlotIndex Stop = I.stop();
     DbgValueLocation Loc = I.value();
+
+    ++I;
+    // Skip dummy values.
+    if (!Loc.getExpression())
+      continue;
+
     auto SpillIt =
-        !Loc.isUndef() ? SpillOffsets.find(Loc.locNo()) : SpillOffsets.end();
+        !Loc.isUndef() ? SpillOffsets.find(Loc.getLocNo()) : SpillOffsets.end();
     bool Spilled = SpillIt != SpillOffsets.end();
     unsigned SpillOffset = Spilled ? SpillIt->second : 0;
 
-    LLVM_DEBUG(dbgs() << "\t[" << Start << ';' << Stop << "):" << Loc.locNo());
+    LLVM_DEBUG(dbgs() << "\t[" << Start << ';' << Stop
+                      << "):" << Loc.getLocNo());
     MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator();
     SlotIndex MBBEnd = LIS.getMBBEndIdx(&*MBB);
 
     LLVM_DEBUG(dbgs() << ' ' << printMBBReference(*MBB) << '-' << MBBEnd);
-    insertDebugValue(&*MBB, Start, Stop, Loc, Spilled, SpillOffset, LIS, TII,
-                     TRI);
+    insertDebugValue(Variable, DL, &*MBB, Start, Stop, Loc, Spilled,
+                     SpillOffset, LIS, TII, TRI);
     // This interval may span multiple basic blocks.
     // Insert a DBG_VALUE into each one.
     while (Stop > MBBEnd) {
       // Move to the next block.
       Start = MBBEnd;
       if (++MBB == MFEnd)
         break;
       MBBEnd = LIS.getMBBEndIdx(&*MBB);
       LLVM_DEBUG(dbgs() << ' ' << printMBBReference(*MBB) << '-' << MBBEnd);
-      insertDebugValue(&*MBB, Start, Stop, Loc, Spilled, SpillOffset, LIS, TII,
-                       TRI);
+      insertDebugValue(Variable, DL, &*MBB, Start, Stop, Loc, Spilled,
+                       SpillOffset, LIS, TII, TRI);
     }
     LLVM_DEBUG(dbgs() << '\n');
     if (MBB == MFEnd)
       break;
-
-    ++I;
   }
 }
 
 void UserLabel::emitDebugLabel(LiveIntervals &LIS, const TargetInstrInfo &TII) {
   LLVM_DEBUG(dbgs() << "\t" << loc);
   MachineFunction::iterator MBB = LIS.getMBBFromIndex(loc)->getIterator();
 
   LLVM_DEBUG(dbgs() << ' ' << printMBBReference(*MBB));
   insertDebugLabel(&*MBB, loc, LIS, TII);
 
   LLVM_DEBUG(dbgs() << '\n');
 }
 
 void LDVImpl::emitDebugValues(VirtRegMap *VRM) {
   LLVM_DEBUG(dbgs() << "********** EMITTING LIVE DEBUG VARIABLES **********\n");
   if (!MF)
     return;
   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
   SpillOffsetMap SpillOffsets;
-  for (auto &userValue : userValues) {
-    LLVM_DEBUG(userValue->print(dbgs(), TRI));
-    userValue->rewriteLocations(*VRM, *MF, *TII, *TRI, SpillOffsets);
-    userValue->emitDebugValues(VRM, *LIS, *TII, *TRI, SpillOffsets);
+  for (auto &SrcVar : sourceVariables) {
+    for (const auto &Frag : *SrcVar) {
+      LLVM_DEBUG(Frag->print(dbgs(), SrcVar->getVariable(),
+                             SrcVar->getDebugLoc(), TRI));
+      Frag->rewriteLocations(*VRM, *MF, *TII, *TRI, SpillOffsets);
+      Frag->emitDebugValues(SrcVar->getVariable(), SrcVar->getDebugLoc(), VRM,
+                            *LIS, *TII, *TRI, SpillOffsets);
+    }
   }
   LLVM_DEBUG(dbgs() << "********** EMITTING LIVE DEBUG LABELS **********\n");
   for (auto &userLabel : userLabels) {
     LLVM_DEBUG(userLabel->print(dbgs(), TRI));
     userLabel->emitDebugLabel(*LIS, *TII);
   }
   EmitDone = true;
 }

llvm/test/DebugInfo/ARM/PR26163.ll

 ; RUN: llc -filetype=obj -o - < %s | llvm-dwarfdump -v -debug-info - | FileCheck %s
 ;
 ; Checks that we're omitting the first range, as it is empty, and that we're
 ; emitting one that spans the rest of the function. In this case, the first
 ; range, which we omit, describes 8 bytes of the variable using DW_OP_litX,
 ; whereas the second one only describes 4 bytes, so clobbering the whole 8 byte
 ; fragment with the 4 bytes fragment isn't necessarily best thing to do here,
 ; but it is what is currently being emitted. Any change here needs to be
 ; intentional, so the test is very specific.
 ;
 ; CHECK: DW_TAG_inlined_subroutine
 ; CHECK: DW_TAG_variable
-; CHECK:   DW_AT_location [DW_FORM_sec_offset] ({{.*}}
-; CHECK-NEXT: [0x00000004, 0x00000014): DW_OP_lit0, DW_OP_stack_value, DW_OP_piece 0x4)
+; CHECK: DW_AT_location [DW_FORM_exprloc] (DW_OP_lit0, DW_OP_stack_value, DW_OP_piece 0x4)
 
 ; Created form the following test case (PR26163) with
 ; clang -cc1 -triple armv4t--freebsd11.0-gnueabi -emit-obj -debug-info-kind=standalone -O2 -x c test.c
 ;
 ; typedef unsigned int  size_t;
 ; struct timeval {
 ;   long long tv_sec;
 ;   int tv_usec;

llvm/test/DebugInfo/MIR/X86/live-debug-vars-unused-arg-debugonly.mir

 
 # Let's verify that the slot index ranges for the unused variables argc/argv,
 # connected to physical regs $edi and $rsi, does not overlap with the ranges
 # for %2 and %3. The register allocator is actually allocating the
 # virtual registers # to $edi and $esi, so the ranges for argc/argv should
 # not cover the whole BB.
 #
 # CHECKDBG-LABEL: ********** EMITTING LIVE DEBUG VARIABLES **********
-# CHECKDBG-NEXT: !"argc,5"        [0B;0e):0 Loc0=$edi
+# CHECKDBG-NEXT: !"argc,5"        [0B;0e):0{{.*}}Loc0=$edi
 # CHECKDBG-NEXT:         [0B;0e):0 %bb.0-160B
-# CHECKDBG-NEXT: !"argv,5"        [0B;0e):0 Loc0=$rsi
+# CHECKDBG-NEXT: !"argv,5"        [0B;0e):0{{.*}}Loc0=$rsi
 # CHECKDBG-NEXT:         [0B;0e):0 %bb.0-160B
-# CHECKDBG-NEXT: !"a0,7"  [16r;64r):0 Loc0=%2
+# CHECKDBG-NEXT: !"a0,7"  [16r;64r):0{{.*}}Loc0=%2
 # CHECKDBG-NEXT:         [16r;64r):0 %bb.0-160B
-# CHECKDBG-NEXT: !"a1,8"  [32r;80r):0 Loc0=%3
+# CHECKDBG-NEXT: !"a1,8"  [32r;80r):0{{.*}}Loc0=%3
 # CHECKDBG-NEXT:         [32r;80r):0 %bb.0-160B

llvm/test/DebugInfo/X86/dbg-addr-dse.ll

 ; RUN: llc %s -o %t.s
 ; RUN: llvm-mc %t.s -filetype=obj -triple=x86_64-windows-msvc -o %t.o
 ; RUN: FileCheck %s < %t.s --check-prefix=ASM
 ; RUN: llvm-dwarfdump %t.o | FileCheck %s --check-prefix=DWARF
 
-; XFAIL: *
-; See PR41992, the third and final dbg.value disappears after
-; LiveDebugVariables.
-
 ; In this example, the variable lives mostly in memory, but at the point of the
 ; assignment to global, it lives nowhere, and is described as the constant
 ; value 1.
 
 ; C source:
 ;
 ; void escape(int *);
 ; extern int global;

llvm/test/DebugInfo/X86/live-debug-vars-dse.mir

 # RUN: llc -start-after=machine-scheduler %s -o - | FileCheck %s
 
-# XFAIL: *
-# See PR41992, the third and final dbg.value disappears after
-# LiveDebugVariables.
-
 # C source:
 # void escape(int *);
 # extern int global;
 # void f(int x) {
 #   escape(&x);
 #   x = 1;
 #   global = x;
 #   x = 2;

llvm/test/DebugInfo/pr41992.ll

+; Test that identical DBG_VALUES are correctly coalesced (or not).
+; NOTE: The IR in this file has been modified by hand and is based off the IR
+; in the top comment here https://bugs.llvm.org/show_bug.cgi?id=41992
+
+; RUN: llc %s -stop-after=virtregrewriter -o - | FileCheck %s --implicit-check-not=DBG_VALUE
+
+; Test that two identical DBG_VALUEs are not coalesced when another used to
+; describe the same source variable fragment but with a different DIExpression
+; is found between them.
+;
+; CHECK: name: f1
+; CHECK: DBG_VALUE %stack.0.x.addr, $noreg, ![[DBG_VAR:[0-9]+]], !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16)
+; CHECK: DBG_VALUE %stack.0.x.addr, $noreg, ![[DBG_VAR]], !DIExpression(DW_OP_LLVM_fragment, 0, 16)
+; CHECK: DBG_VALUE %stack.0.x.addr, $noreg, ![[DBG_VAR]], !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16)
+
+
+; Test that two identical DBG_VALUEs are not coalesced when another used to
+; describe overlapping fragments of the same variable but with a different DIExpression
+; is found between them.
+;
+; CHECK: name: f2
+; CHECK: DBG_VALUE %stack.0.x.addr, $noreg, ![[DBG_VAR:[0-9]+]], !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16)
+; CHECK: DBG_VALUE %stack.0.x.addr, $noreg, ![[DBG_VAR]], !DIExpression(DW_OP_LLVM_fragment, 8, 16)
+; CHECK: DBG_VALUE %stack.0.x.addr, $noreg, ![[DBG_VAR]], !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16)
+
+
+; Test that two identical DBG_VALUEs are coalesced when another used to
+; describe another fragment of the same source variable s found between them.
+;
+; CHECK: name: f3
+; CHECK: DBG_VALUE %stack.0.x.addr, $noreg, ![[DBG_VAR:[0-9]+]], !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16)
+; CHECK: DBG_VALUE %stack.0.x.addr, $noreg, ![[DBG_VAR]], !DIExpression(DW_OP_LLVM_fragment, 16, 16)
+
+
+declare void @llvm.dbg.addr(metadata, metadata, metadata)
+declare void @llvm.dbg.value(metadata, metadata, metadata)
+declare void @escape(i32*)
+
+@global = external global i32, align 4
+
+define void @f1(i32 %x) !dbg !8 {
+entry:
+  %x.addr = alloca i32, align 4
+  store i32 %x, i32* %x.addr, align 4
+  call void @llvm.dbg.value(metadata i32* %x.addr, metadata !13, metadata !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16)), !dbg !18
+  call void @escape(i32* %x.addr), !dbg !18
+  call void @llvm.dbg.value(metadata i32* %x.addr, metadata !13, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 16)), !dbg !18
+  store i32 1, i32* @global, align 4, !dbg !18
+  call void @llvm.dbg.value(metadata i32* %x.addr, metadata !13, metadata !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16)), !dbg !18
+  store i32 2, i32* %x.addr, align 4, !dbg !18
+  call void @escape(i32* %x.addr), !dbg !18
+  ret void, !dbg !18
+}
+
+define void @f2(i32 %x) !dbg !22 {
+entry:
+  %x.addr = alloca i32, align 4
+  store i32 %x, i32* %x.addr, align 4
+  call void @llvm.dbg.value(metadata i32* %x.addr, metadata !24, metadata !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16)), !dbg !23
+  call void @escape(i32* %x.addr)
+  call void @llvm.dbg.value(metadata i32* %x.addr, metadata !24, metadata !DIExpression(DW_OP_LLVM_fragment, 8, 16)), !dbg !23
+  store i32 1, i32* @global, align 4
+  call void @llvm.dbg.value(metadata i32* %x.addr, metadata !24, metadata !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16)), !dbg !23
+  store i32 2, i32* %x.addr, align 4
+  call void @escape(i32* %x.addr)
+  ret void
+}
+
+define void @f3(i32 %x) !dbg !19 {
+entry:
+  %x.addr = alloca i32, align 4
+  store i32 %x, i32* %x.addr, align 4
+  call void @llvm.dbg.value(metadata i32* %x.addr, metadata !21, metadata !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16)), !dbg !20
+  call void @escape(i32* %x.addr)
+  call void @llvm.dbg.value(metadata i32* %x.addr, metadata !21, metadata !DIExpression(DW_OP_LLVM_fragment, 16, 16)), !dbg !20
+  store i32 1, i32* @global, align 4
+  call void @llvm.dbg.value(metadata i32* %x.addr, metadata !21, metadata !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16)), !dbg !20
+  store i32 2, i32* %x.addr, align 4
+  call void @escape(i32* %x.addr)
+  ret void
+}
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4}
+!llvm.ident = !{!7}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 6.0.0 ", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+!1 = !DIFile(filename: "dse.c", directory: "")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!7 = !{!"clang version 6.0.0 "}
+!8 = distinct !DISubprogram(name: "f1", scope: !1, file: !1, line: 3, type: !9, isLocal: false, isDefinition: true, scopeLine: 3, flags: DIFlagPrototyped, isOptimized: true, unit: !0, retainedNodes: !12)
+!9 = !DISubroutineType(types: !10)
+!10 = !{null, !11}
+!11 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!12 = !{!13}
+!13 = !DILocalVariable(name: "x", arg: 1, scope: !8, file: !1, line: 3, type: !11)
+!18 = !DILocation(line: 3, column: 12, scope: !8)
+!19 = distinct !DISubprogram(name: "f2", scope: !1, file: !1, line: 20, type: !9, isLocal: false, isDefinition: true, scopeLine: 20, flags: DIFlagPrototyped, isOptimized: true, unit: !0, retainedNodes: !12)
+!20 = !DILocation(line: 23, column: 12, scope: !19)
+!21 = !DILocalVariable(name: "x", arg: 1, scope: !19, file: !1, line: 21, type: !11)
+!22 = distinct !DISubprogram(name: "f3", scope: !1, file: !1, line: 20, type: !9, isLocal: false, isDefinition: true, scopeLine: 30, flags: DIFlagPrototyped, isOptimized: true, unit: !0, retainedNodes: !12)
+!23 = !DILocation(line: 23, column: 12, scope: !22)
+!24 = !DILocalVariable(name: "x", arg: 1, scope: !22, file: !1, line: 31, type: !11)