llvm dev - Sep 2020 - [RFC] [DebugInfo] Using DW_OP_entry_value within LLVM IR

Hi Djordje,

[Late reply as I was away, alas],

For the example in https://reviews.llvm.org/D85012 , I'm not sure that
just using an entry value is correct. The reason why the dbg.values
for arguments are set to undef is not because the value can't be
described, it's because deadargelim changes all the call sites to pass
in 'undef', which I believe makes the value unrecoverable even with
entry values. Can call sites like that be described by DWARF? If so, I
guess a combination of entry-value variable locations and salvaging
the call-site arguments would work.

The isel example in https://reviews.llvm.org/D87233 is good --
although dropping the variable location there is largely because of
SelectionDAGs own limitations rather than the generated code. We can't
describe arguments that aren't used because they're not copied to a
virtual register.

In general, I reckon entry values will be a key part of recovering
variable locations, however I'm not sure that there are many places
where it's truly necessary in LLVM-IR. deadargelim is definitely one
of them; but even then, the Argument remains in the function
signature. We're still able to refer to the Argument in dbg.values, in
program positions where the argument will be available, and where it
will be unavailable. In my opinion, entry values are probably most
useful when things go out of liveness; however we don't know what's in
or out of liveness until the register allocator runs.

As you say, we could speculatively produce entry value expressions as
a "backup". I reckon this will work fine, although there'll be
some
un-necessary work involved due to it being speculative. I kind of have
a different vision for how this could be done though, and not just for
entry values. It hinges on the instruction referencing variable
location stuff I've been working on: I believe we can use that to
connect variable values at the end of compilation back to LLVM-IR
Values. If that's achievable, we'll have:
 * Information about the set of LLVM-IR Values that are live, and what
physical registers they're in,
 * The IR itself, which contains the target-independent relationships
between Values,
After which we will have enough information at the end of compilation
to directly answer the question "How can we describe this variable
value using only Values that are live?", effectively doing very late
salvaging. We can consider entry values to be always available, and
should be able to recover any value that _can_ be described in terms
of entry values.

That's assuming that the instruction referencing stuff works out. I
can elaborate and give some examples if wanted. My overarching feeling
is that it'd be great to avoid doing extra working during compilation,
instead leaving things until the end when there's more information
available.

--
Thanks,
Jeremy

Hi Jeremy,

Thanks a lot for your feedback.

For the example in https://reviews.llvm.org/D85012 , I'm not sure that
just using an entry value is correct. The reason why the dbg.values
for arguments are set to undef is not because the value can't be
described, it's because deadargelim changes all the call sites to pass
in 'undef', which I believe makes the value unrecoverable even with
entry values. Can call sites like that be described by DWARF? If so, I
guess a combination of entry-value variable locations and salvaging
the call-site arguments would work.
Using entry-values ('callee' side of the feature) is not enough in any
case. It is always connected to the call-site-param (function arguments but we
call it call-site-params; 'caller' side of the feature) debug info. I
believe that there are call-site-params that could be expressed in terms of
DWARF for the cases we face within deadargelim. GCC does perform correct output
for both caller and callee sides for unused params.

As you say, we could speculatively produce entry value expressions as
a "backup". I reckon this will work fine, although there'll be
some
un-necessary work involved due to it being speculative. I kind of have
a different vision for how this could be done though, and not just for
entry values. It hinges on the instruction referencing variable
location stuff I've been working on: I believe we can use that to
connect variable values at the end of compilation back to LLVM-IR
Values. If that's achievable, we'll have:
 * Information about the set of LLVM-IR Values that are live, and what
physical registers they're in,
 * The IR itself, which contains the target-independent relationships
between Values,
After which we will have enough information at the end of compilation
to directly answer the question "How can we describe this variable
value using only Values that are live?", effectively doing very late
salvaging. We can consider entry values to be always available, and
should be able to recover any value that _can_ be described in terms
of entry values.

That's assuming that the instruction referencing stuff works out. I
can elaborate and give some examples if wanted.
Please share that work when you are ready.

My overarching feeling
is that it'd be great to avoid doing extra working during compilation,
instead leaving things until the end when there's more information
available.
I agree with the statement (it'd be better if possible).

Best,
Djordje

________________________________
From: Jeremy Morse <jeremy.morse.llvm at gmail.com>
Sent: Tuesday, September 8, 2020 2:25 PM
To: Djordje Todorovic <Djordje.Todorovic at syrmia.com>
Cc: David Stenberg <david.stenberg at ericsson.com>; llvm-dev at
lists.llvm.org <llvm-dev at lists.llvm.org>; Nikola Tesic <Nikola.Tesic
at syrmia.com>; Petar Jovanovic <petar.jovanovic at syrmia.com>; ibaev
at cisco.com <ibaev at cisco.com>; asowda at cisco.com <asowda at
cisco.com>
Subject: Re: [llvm-dev] [RFC] [DebugInfo] Using DW_OP_entry_value within LLVM IR

Hi Djordje,

[Late reply as I was away, alas],

For the example in https://reviews.llvm.org/D85012 , I'm not sure that
just using an entry value is correct. The reason why the dbg.values
for arguments are set to undef is not because the value can't be
described, it's because deadargelim changes all the call sites to pass
in 'undef', which I believe makes the value unrecoverable even with
entry values. Can call sites like that be described by DWARF? If so, I
guess a combination of entry-value variable locations and salvaging
the call-site arguments would work.

The isel example in https://reviews.llvm.org/D87233 is good --
although dropping the variable location there is largely because of
SelectionDAGs own limitations rather than the generated code. We can't
describe arguments that aren't used because they're not copied to a
virtual register.

In general, I reckon entry values will be a key part of recovering
variable locations, however I'm not sure that there are many places
where it's truly necessary in LLVM-IR. deadargelim is definitely one
of them; but even then, the Argument remains in the function
signature. We're still able to refer to the Argument in dbg.values, in
program positions where the argument will be available, and where it
will be unavailable. In my opinion, entry values are probably most
useful when things go out of liveness; however we don't know what's in
or out of liveness until the register allocator runs.

As you say, we could speculatively produce entry value expressions as
a "backup". I reckon this will work fine, although there'll be
some
un-necessary work involved due to it being speculative. I kind of have
a different vision for how this could be done though, and not just for
entry values. It hinges on the instruction referencing variable
location stuff I've been working on: I believe we can use that to
connect variable values at the end of compilation back to LLVM-IR
Values. If that's achievable, we'll have:
 * Information about the set of LLVM-IR Values that are live, and what
physical registers they're in,
 * The IR itself, which contains the target-independent relationships
between Values,
After which we will have enough information at the end of compilation
to directly answer the question "How can we describe this variable
value using only Values that are live?", effectively doing very late
salvaging. We can consider entry values to be always available, and
should be able to recover any value that _can_ be described in terms
of entry values.

That's assuming that the instruction referencing stuff works out. I
can elaborate and give some examples if wanted. My overarching feeling
is that it'd be great to avoid doing extra working during compilation,
instead leaving things until the end when there's more information
available.

--
Thanks,
Jeremy
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200909/3adbd6ac/attachment.html>

Hi Djordje,

On Wed, Sep 9, 2020 at 7:52 AM Djordje Todorovic
<Djordje.Todorovic at syrmia.com> wrote:
> Using entry-values ('callee' side of the feature) is not enough in
any case. It is always connected to the call-site-param (function arguments but
we call it call-site-params; 'caller' side of the feature) debug info. I
believe that there are call-site-params that could be expressed in terms of
DWARF for the cases we face within deadargelim. GCC does perform correct output
for both caller and callee sides for unused params.
Ah, that covers my concerns. This is definitely a worthy cause then --
especially as parameters are usually considered more important to
preserve than other variables.

Djordje
> Please share that work when you are ready.
Sure, explanation below: note that I'm bringing this up now because I
see producing entry-value "backup" locations as a technique to recover
from the register allocator clobbering things, and I feel the below is
a more general solution.

I'd like to use this (contrived) code as an illustrative example:

    void ext(long);
    void foo(long *ptr, long bar, long baz) {
      for (long i = 0; i < bar; ++i) {
        long index = baz + i;
        long *curptr = &ptr[index];
        ext(*curptr);
      }
    }

All it does is iterate over a loop, loading values from an offset into
a pointer. I've compiled this at -O2, and then given it an additional
run of -loop-reduce with opt [0]. During optimisation, LLVM rightly
identifies that the 'baz' offset is loop-invariant, and that it can
fold some of the offset calculation into the loop preheader. This then
leads to both 'ptr' and 'baz' being out of liveness, and being
clobbered in the body of the loop. In addition, the 'index' variable
is optimised out too, and that's the variable I'd like to focus on.

Today, we're not able to describe 'index' in the IR after
-loop-reduce, but I'm confident that the variadic variable locations
work will make that possible. I'm going to assume that we can describe
such locations for the rest of this email.

"index" could be described by using the entry value of 'baz'
and
adding it to 'i', which remains in liveness throughout. To produce a
"backup" location though, we would have to guess that 'baz'
would go
out of liveness in advance, and speculatively produce the expression.
I reckon that we can instead calculate the location at end of
compilation by using the SSA-like information from instruction
referencing. Here's the MIR for the reduced loop body, using
instruction-referencing [1] and lightly edited to remove noise, with
only variable locations for the 'i' variable. I've added some
explanatory comments:

    DBG_PHI $rbx, 2
    DBG_INSTR_REF 2, 0, !16, !DIExpression(), debug-location !23
    ;  This is the load from *curptr:
    renamable $rdi = MOV64rm renamable $r15, 8, renamable $rbx
    ; Call to ext,
    CALL64pcrel32 @ext, csr_64, [implicit defs]
    ; Loop increment:
    renamable $rbx = nuw nsw ADD64ri8 killed renamable $rbx, 1,
debug-instr-number 1
    DBG_INSTR_REF 1, 0, !16, !DIExpression(), debug-location !23
    CMP64rr renamable $r14, renamable $rbx, implicit-def $eflags
    JCC_1 %bb.2, 5, implicit $eflags

The label "debug-instr-number 1" on the ADD64ri8 identifies the ADD as
corresponding to the loop increment, and the DBG_PHI for $rbx as the
position where the loop PHI occurs. My key observation is that there
is a one-to-one relationship between LLVM-IR Values and these
end-of-compilation instruction numbers [2]. If we stored a mapping
during instruction selection of Value <=> instruction reference, at
the end of compilation we would be able to salvage variable locations
that had gone out of liveness.

Imagine for a moment that we described the "index" variable as a
variadic variable location, possibly looking like this:

    DBG_INSTR_REF {3, 0}, {2, 0}, !17, !DIExpression(DW_OP_LLVM_arg,
0, DW_OP_LLVM_arg, 1, DW_OP_plus)

Where the {3, 0} instruction number referred to the 'baz' argument,
and {2, 0} the value of 'i' on entry to the loop body. The workflow
for salvaging would look something like this, after LiveDebugValues
has finished doing dataflow things:
  1) Examine instruction reference {3, 0},
  2) Observe that it's out of liveness in the current location (the loop
body),
  3) Look up the LLVM-IR Value that {3, 0} corresponds to, finding the
Argument in LLVM-IR,
  4) Because it's an Argument, replace DW_OP_LLVM_arg, 0 with the
corresponding entry value expression,
  5) Emit variable location.

This is harder than just speculating how we might salvage the location
earlier in compilation, but is more direct, and involves no
un-necessary work. Additionally, it's not limited to entry values: for
any value that goes out of liveness that was computed by a side-effect
free instruction, we could:
  4) For each operand of the corresponding LLVM-IR Instruction,
  4.1) Identify the instruction number of this operand,
  4.2) Confirm that that number is still in liveness (if not: abort),
  5) Compute an expression that recomputes the Value using the
locations of the operands,
  6) Emit variable location.

We could even go the other way and recover a value from other
computations that used the value (if an inverse operation exists).

~

This may sound far-fetched, but I think a lot of the information
necessary to do the above is becoming available. Doing this completely
in general would involve putting instruction references on every
LLVM-IR Value in the function being compiled, which could add an
overhead. Whether that's worth it depends on how many variable
locations could be recovered.

Again, it hinges on not finding something fatal in the instruction
referencing approach to variable locations. Tail duplication is being
miserable, but hasn't thrown up anything fatal yet.

Thanks for listening!

[0] I'm not sure why -loop-reduce wasn't firing during -O2, but
that's
not important.
[1] It's possible with all the patches I've uploaded for review so
far; although I seem to have missed the patch to InstrEmitter.cpp that
labels PHI instructions, I'll try to get that up soon.
[2] Not necessarily true after tail-duplication runs; but I believe
that can be addressed with some minor pain.

--
Thanks,
Jeremy