search

Quuxplusone / LLVMBugzillaTest

0 stars 0 forks source link

Parameter location list unnecessarily complex when value available in multiple regs #41804

Open Quuxplusone opened 5 years ago

Quuxplusone commented 5 years ago
Bugzilla Link PR42834
Status NEW
Importance P normal
Reported by Vedant Kumar (vsk@apple.com)
Reported on 2019-07-30 15:00:20 -0700
Last modified on 2020-05-15 03:36:20 -0700
Version trunk
Hardware PC All
CC aprantl@apple.com, djordje.todorovic@rt-rk.com, jeremy.morse.llvm@gmail.com, llvm-bugs@lists.llvm.org, neeilans@live.com, orlando.hyams@sony.com, richard-llvm@metafoo.co.uk
Fixed by commit(s)
Attachments cgscc-func.mir (15737 bytes, text/plain)
cgscc-func.ll (9611 bytes, text/plain)
Blocks
Blocked by
See also PR38997 
Created attachment 22319
MIR reproducer

A value may be available in multiple locations simultaneously. However, llvm
does not always emit a minimal location list in this situation.

Consider the attached IR/MIR (cgscc-func.mir). The parameter “V” is never
modified, and is almost-always available in both $rdi and $rax. However, the
location list looks like:

0x000510ce:     DW_TAG_formal_parameter
                  DW_AT_location        (0x00000c78
                     [0x0000000100002730,  0x000000010000273c): DW_OP_reg5 RDI
                     [0x000000010000273c,  0x0000000100002746): DW_OP_reg0 RAX
                     [0x0000000100002746,  0x0000000100002748): DW_OP_GNU_entry_value(DW_OP_reg5 RDI), DW_OP_stack_value
                     [0x0000000100002748,  0x000000010000275f): DW_OP_reg0 RAX
                     [0x000000010000275f,  0x0000000100002765): DW_OP_GNU_entry_value(DW_OP_reg5 RDI), DW_OP_stack_value
                     [0x0000000100002765,  0x000000010000276d): DW_OP_reg0 RAX
                     [0x000000010000276d,  0x0000000100002773): DW_OP_GNU_entry_value(DW_OP_reg5 RDI), DW_OP_stack_value
                     [0x0000000100002773,  0x000000010000277b): DW_OP_reg0 RAX
                     [0x000000010000277b,  0x000000010000277d): DW_OP_GNU_entry_value(DW_OP_reg5 RDI), DW_OP_stack_value
                     [0x000000010000277d,  0x0000000100002784): DW_OP_reg5 RDI
                     [0x0000000100002784,  0x000000010000279c): DW_OP_GNU_entry_value(DW_OP_reg5 RDI), DW_OP_stack_value
                     [0x000000010000279c,  0x00000001000027bb): DW_OP_reg0 RAX
                     [0x00000001000027bb,  0x00000001000027bb): DW_OP_GNU_entry_value(DW_OP_reg5 RDI), DW_OP_stack_value)
                  DW_AT_name    ("V")

This alternative seems better:

0x000510ce:     DW_TAG_formal_parameter
                  DW_AT_location        (0x00000c78
                     [0x0000000100002730,  0x00000001000027bb): DW_OP_reg5 RDI)
                  DW_AT_name    ("V")

Notes:

After the following COPY is inserted, the DBG_VALUEs for “V” tend to point to
%5 ($rax):

bb.0.entry:
  successors: %bb.1(0x00000001), %bb.2(0x7fffffff); %bb.1(0.00%), %bb.2(100.00%)
  liveins: $rdi
  DBG_VALUE $rdi, $noreg, !"V", !DIExpression(), debug-location !51604
  %5:gr64_with_sub_8bit = COPY $rdi
  DBG_VALUE %5:gr64_with_sub_8bit, $noreg, !"V", !DIExpression(), debug-location !51604

I’m not sure whether it’s worth tracking all locations for all values in the
general case (I doubt it). But for this specific case, maybe we can avoid
emitting the DBG_VALUE for $rax until $rdi is actually clobbered.
Quuxplusone commented 5 years ago

Attached cgscc-func.mir (15737 bytes, text/plain): MIR reproducer

Quuxplusone commented 5 years ago

Attached cgscc-func.ll (9611 bytes, text/plain): IR reproducer

Quuxplusone commented 5 years ago

I took a look into this and it makes sense to me.

Maybe we can let the DBG_VALUEs being created and handle it very late within the DbgEntityHistoryCalculator. An idea is to introduce a new EntryKind for backup DBG_VALUEs where for the variable already exists a valid DBG_VALUE. The backup DBG_VALUE wont be considered until the main one (actually the register holding a value) gets clobbered.

WDYT?

Quuxplusone commented 5 years ago 
(In reply to Djordje Todorovic from comment #2)
> I took a look into this and it makes sense to me.
>
> Maybe we can let the DBG_VALUEs being created and handle it very late within
> the DbgEntityHistoryCalculator. An idea is to introduce a new EntryKind for
> backup DBG_VALUEs where for the variable already exists a valid DBG_VALUE.
> The backup DBG_VALUE  wont be considered until the main one (actually the
> register holding a value) gets clobbered.
>
> WDYT?

That sounds like a reasonable place to implement the optimization. Instead of
starting a new instr range as soon as a new dbg_value is encountered, maybe we
could just keep a record of the dbg_value if it's from a COPY MI, like you're
saying? If the affected reg is ever clobbered, we can try to use the COPY to
keep the range open. I suppose we'd have to teach whatever logic there is to
end instr ranges to end the ranges of COPY dbg_values as well.
Quuxplusone commented 5 years ago 
>Instead of starting a new instr range as soon as a new dbg_value is
encountered, maybe we could just keep a record of the dbg_value if it's from a
COPY MI, like you're saying?

For now, we can keep records just for the dbg_values that are coming from COPY-
like MIs. I believe we can (later) extend the support for some other MIs as
well.

>I suppose we'd have to teach whatever logic there is to end instr ranges to
end the ranges of COPY dbg_values as well.

Yes, we'd have to handle that as well. We could hold a map of register pairs
simultaneously holding the same value in order to speed up the process. I guess
we can also introduce one another EntryKind that will work as special
clobbering kind for the backup (copy) dbg_values.
Quuxplusone commented 5 years ago 
My understanding of this is that the excessively large number of locations
is due to LiveDebugValues propagating the $rax location to a bunch of
blocks, mixed with $rdi locations and clobbering instructions. I've
replicated this through scattering a little debuginfo in [0], and I think
it's worth noting that there's a shallow cause too. This clause [1] in
LiveDebugValues would normally prevent the copy to $rax being propagated,
but because "V" is an argument, it grows an extra DBG_VALUE much earlier in
SelectionDAG, and LiveDebugValues sees it in both $rdi and $rax.

The copy-recording idea is good, but I don't believe it would easily fix
this particular example -- the copy from $rdi to $rax occurs in a different
basic block to where the register clobbers occur, DbgEntityHistoryCalculator
would need to start considering control flow (it doesn't right now). If it
did, it would basically re-implement LiveDebugValues.

Stepping back slightly,

Vedant wrote:
> I'm not sure whether it’s worth tracking all locations for all values in
> the general case (I doubt it).

We (the Sony lot) wound up digging into this during the course of bug 38997.
It might be difficult to interpret from the ticket (there are a couple of
problems described there), but if you compile Toms reproducer with
trunk today LiveDebugValues gets "count"s location in the loop wrong. It
fails to recognise the loop back-edge as something that might have caused
"count" to be clobbered.

While digging, we figured that only a stronger static analysis would let
LiveDebugValues get this right (In Cooper/Torczon's "Engineering a compiler
(2nd)" this is the "Available expressions" analysis, Section 9.2.4).
Specifically, we think working out all the variable locations a backedge
might clobber is the same as working out all the locations for all values,
some discussion of that occurred here [2] long ago.

Thus: IMHO, the natural place to address this would be LiveDebugValues
(which already considers locations, clobbers and control flows), with a
stronger static analysis seeing how LiveDebugValues already needs it.
How to go about this is an open question, we moved on to other things after
looking at bug 38997. Sorry if this seems that I'm dragging this
location-quality issue onto another topic, but IMHO/YMMV they're closely
related.

[0] https://gist.github.com/jmorse/44c0d74271390c138fbe2f09a747e102 (there
wasn't any in the reproducer),
[1] https://github.com/llvm/llvm-
project/blob/2bea69bf6503ffc9f3cde9a52b5dac1a25e94e1c/llvm/lib/CodeGen/LiveDebugValues.cpp#L891
[2] https://groups.google.com/d/msg/llvm-dev/nlgxIfDQnhs/0Az0_j8VAAAJ
Quuxplusone commented 5 years ago 
Having that in mind the LiveDebugValues seems to be better place to do add such
thing.

First problem we need to resolve is to get rid of the code that generates the
additional DBG_VALUEs for values movements (such as [0]) or other cases that
should be the LiveDebugValues domain. After that, we can refactor the
LiveDebugValues in order to handle a list of valid locations at the time, so
i.e. the first location from the list would be the primary one, the others will
be considered as 'backup' locations. We should keep considering the primary
location as is until it gets clobbered, and then start using the second one,
etc. That will allow us to minimize the debug location lists.

[0] https://github.com/llvm/llvm-
project/blob/f24ac13aaae63d92317dac839ce57857a7b444dc/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp#L587
Quuxplusone commented 4 years ago 
Hi,

Djordje wrote:
> First problem we need to resolve is to get rid of the code that generates
> the additional DBG_VALUEs for values movements (such as [0]) or other cases
> that should be the LiveDebugValues domain.

I guess the LiveDebugVariables "extendDef" feature does this too, as it tries
to salvage values that go out of liveness by looking for copies.

Something I'd like to do in the future is experimentally turning extendDef off,
seeing how many tests break, and whether there's actually any loss in variable
coverage that LiveDebugValues can't recover through propagation.