llvm dev - Jun 2016 - Finding caller-saved registers at a function call site

Hi Rob,

Robert Lyerly wrote:
 > At a high level, I'm interested in finding the locations of all values
 > that are live at a given call site.**You can think of it like a
 > debugger, e.g. gdb -- I'd like to be able to unwind the stack, frame
by
 > frame, and locate all the live values for each function invocation
 > (i.e., where they are in a function's stack frame/register set) at the
 > function call site.  I'm currently using DWARF metadata to implement
the
 > frame unwinding mechanism, similarly to gdb.  I can't use DWARF
metadata
 > for live value location information, however, because it only generates
 > location information for named source code variables.  I also need to

Isn't DWARF info best effort (not a rhetorical question -- I don't
actually know)?  Or do you not care about being a 100% precise?

Given that you're interested in finding all values live at a
call-site, why not do just that -- run a liveness analysis over stack
slots and registers?  That should catch compiler temporaries too.

A related question is: are you interested in the *values* or the
*locations* the values are in?  For instance if a specific value (say
the result of a load) is spilled at 0x80(%rsp) and is also present in
%r13 (callee saved register), then do you have to know both the
locations or just one of the two?

 > locate compiler-generated temporaries, hence I've been looking at the
 > StackMap intrinsic [1] to provide live value location information.  It
 > does most of what I need, but it does not tell me where live values
 > stored in registers are spilled to the stack as part of the function
 > call procedure (whether they be in callee- or caller-saved registers) --
 > it simply tells me which registers they are stored in before/after the
 > function call procedure.  That's the impetus for my question.

With stackmaps, is the problem that it tells you e.g. a live value is
present in %r9 (caller saved register), but when unwinding the value
may have been clobbered?  This is something other people have run into
as well -- specifically the distinction between "live on call"
(available just before the call) vs. "live on return" (available after
the callee returns).  I'm hazy on the details, but IIRC if this is a
problem, then you may have problems bigger than just figuring out the
spill slots, since the caller saved register may not actually have
been spilled anywhere (since it does not need to live across the
call).

-- Sanjoy


 > This is *not* a problem for callee-saved registers -- these registers
 > are restored from the stack as part of the call frame unwinding
 > procedure detailed in the DWARF standard [2].  However, I'm left
trying
 > to find the locations of the live values that were in caller-saved
 > registers and were spilled to the stack as part of the function call
 > procedure (probably during instruction selection/register allocation,
 > I'm not familiar enough with this process).  I realize that for a
 > MachineInstr for a given call there are no live values in caller-saved
 > registers (as they would be clobbered and lost), but where on the stack
 > were they saved?
 >
 > In a nutshell, I'm trying to figure out where values that couldn't
be
 > placed in callee-saved registers (and that were allocated to
 > caller-saved registers) were spilled to the stack as part of the
 > function call procedure.  Hopefully this clarifies things -- thanks!
 >
 > [1] http://llvm.org/docs/StackMaps.html
 > [2] http://dwarfstd.org/doc/DWARF4.pdf, page 140

Hi Sanjoy,

On Mon, Jun 27, 2016 at 4:05 PM, Sanjoy Das <sanjoy at
playingwithpointers.com>
wrote:
> Hi Rob,
>
> Robert Lyerly wrote:
> > At a high level, I'm interested in finding the locations of all
values
> > that are live at a given call site.**You can think of it like a
> > debugger, e.g. gdb -- I'd like to be able to unwind the stack,
frame by
> > frame, and locate all the live values for each function invocation
> > (i.e., where they are in a function's stack frame/register set) at
the
> > function call site.  I'm currently using DWARF metadata to
implement the
> > frame unwinding mechanism, similarly to gdb.  I can't use DWARF
metadata
> > for live value location information, however, because it only
generates
> > location information for named source code variables.  I also need to
>
> Isn't DWARF info best effort (not a rhetorical question -- I don't
> actually know)?  Or do you not care about being a 100% precise?
>
>
Yes, tracking live values using DWARF metadata is best-effort, another
reason that it is not suitable for what I'm doing :).  The DWARF unwinding
procedure, however, seems to be trivial to implement correctly, as it's
literally just dumping metadata about the generated prologue.  I haven't
had any correctness or incompleteness problems yet with using this aspect
of the DWARF standard.

> Given that you're interested in finding all values live at a
> call-site, why not do just that -- run a liveness analysis over stack
> slots and registers?  That should catch compiler temporaries too.
>
>
The reason I can't just run a liveness analysis over stack slots and
registers in the backend is that I'm trying to map live value locations
back up into their corresponding values in LLVM bitcode.  This is why I'm
using the stackmap intrinsic, as it does exactly that -- provides a mapping
between a bitcode value and its storage location for the generated
assembly.  I need this intermediate-level value because I'm doing ABI
translation.  I'm plucking values out of a call frame laid out in one ABI
and storing them in a destination stack frame that is laid out according to
another ABI.  The IR value is essentially the "key" used to match
corresponding storage locations across the two ABIs.  I'm transforming a
thread's current stack laid out for one ABI into one laid out for another
ABI.

> A related question is: are you interested in the *values* or the
> *locations* the values are in?  For instance if a specific value (say
> the result of a load) is spilled at 0x80(%rsp) and is also present in
> %r13 (callee saved register), then do you have to know both the
> locations or just one of the two?
>
I'm actually only interested in being able to find values; I don't
particularly care about where they're stored.  In your hypothetical, as
long as the compiler could tell me that the value was stored in one of
those locations, that'd be okay.

>
> > locate compiler-generated temporaries, hence I've been looking at
the
> > StackMap intrinsic [1] to provide live value location information.  It
> > does most of what I need, but it does not tell me where live values
> > stored in registers are spilled to the stack as part of the function
> > call procedure (whether they be in callee- or caller-saved registers)
--
> > it simply tells me which registers they are stored in before/after the
> > function call procedure.  That's the impetus for my question.
>
> With stackmaps, is the problem that it tells you e.g. a live value is
> present in %r9 (caller saved register), but when unwinding the value
> may have been clobbered?  This is something other people have run into
> as well -- specifically the distinction between "live on call"
> (available just before the call) vs. "live on return" (available
after
> the callee returns).  I'm hazy on the details, but IIRC if this is a
> problem, then you may have problems bigger than just figuring out the
> spill slots, since the caller saved register may not actually have
> been spilled anywhere (since it does not need to live across the
> call).
>
I'm not concerned about values that are not live across the call ("live
on
call"), only those that are live after returning from the call ("live
on
return").  If the value is not live after the call, there's no need for
me
to able to recover it.  I just need to be able to resume execution in that
function correctly, so I'm only concerned about values in caller-saved
registers that are needed after the call completes, and therefore have been
spilled to the stack as part of the procedure call standard.

Because I'm rewriting the stack to change the ABI, I need to be able to set
up the stack so that execution can correctly unwind back up the call
chain.  This means that I need to be able to populate spill stack slots for
caller-saved registers, hence this is why I need their locations.

Thanks again for your help!

> -- Sanjoy
>
>
> > This is *not* a problem for callee-saved registers -- these registers
>
> > are restored from the stack as part of the call frame unwinding
> > procedure detailed in the DWARF standard [2].  However, I'm left
trying
> > to find the locations of the live values that were in caller-saved
> > registers and were spilled to the stack as part of the function call
> > procedure (probably during instruction selection/register allocation,
> > I'm not familiar enough with this process).  I realize that for a
> > MachineInstr for a given call there are no live values in caller-saved
> > registers (as they would be clobbered and lost), but where on the
stack
> > were they saved?
> >
> > In a nutshell, I'm trying to figure out where values that
couldn't be
> > placed in callee-saved registers (and that were allocated to
> > caller-saved registers) were spilled to the stack as part of the
> > function call procedure.  Hopefully this clarifies things -- thanks!
> >
> > [1] http://llvm.org/docs/StackMaps.html
> > [2] http://dwarfstd.org/doc/DWARF4.pdf, page 140
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160628/98b2f1a5/attachment.html>

I think I understand where the spill code is getting generated.  I've been
digging through the register allocation debug information, and I see that
the register allocator itself is generating the spill code around the call
site (the greedy allocator is also splitting the virtual register's live
range around the call site).  I don't care about the internals of the
register allocator, but I see that it produces a VirtRegMap which contains
the mapping of virtual registers to physical registers/spill slots.  I have
two questions about this:

1. Is there a way to access the produced VirtRegMap in the
architecture-specific AsmPrinter?  I tried the normal
getAnalysis<VirtRegMap>, but it produces and empty mapping.
2. If I manage to get access to this mapping, is there a way to correlate
an LLVM bitcode Value to a virtual register?

On Tue, Jun 28, 2016 at 9:59 AM, Robert Lyerly <rlyerly at vt.edu> wrote:
> Hi Sanjoy,
>
> On Mon, Jun 27, 2016 at 4:05 PM, Sanjoy Das <
> sanjoy at playingwithpointers.com> wrote:
>
>> Hi Rob,
>>
>> Robert Lyerly wrote:
>> > At a high level, I'm interested in finding the locations of
all values
>> > that are live at a given call site.**You can think of it like a
>> > debugger, e.g. gdb -- I'd like to be able to unwind the stack,
frame by
>> > frame, and locate all the live values for each function invocation
>> > (i.e., where they are in a function's stack frame/register
set) at the
>> > function call site.  I'm currently using DWARF metadata to
implement the
>> > frame unwinding mechanism, similarly to gdb.  I can't use
DWARF metadata
>> > for live value location information, however, because it only
generates
>> > location information for named source code variables.  I also need
to
>>
>> Isn't DWARF info best effort (not a rhetorical question -- I
don't
>> actually know)?  Or do you not care about being a 100% precise?
>>
>>
> Yes, tracking live values using DWARF metadata is best-effort, another
> reason that it is not suitable for what I'm doing :).  The DWARF
unwinding
> procedure, however, seems to be trivial to implement correctly, as it's
> literally just dumping metadata about the generated prologue.  I
haven't
> had any correctness or incompleteness problems yet with using this aspect
> of the DWARF standard.
>
>
>> Given that you're interested in finding all values live at a
>> call-site, why not do just that -- run a liveness analysis over stack
>> slots and registers?  That should catch compiler temporaries too.
>>
>>
> The reason I can't just run a liveness analysis over stack slots and
> registers in the backend is that I'm trying to map live value locations
> back up into their corresponding values in LLVM bitcode.  This is why
I'm
> using the stackmap intrinsic, as it does exactly that -- provides a mapping
> between a bitcode value and its storage location for the generated
> assembly.  I need this intermediate-level value because I'm doing ABI
> translation.  I'm plucking values out of a call frame laid out in one
ABI
> and storing them in a destination stack frame that is laid out according to
> another ABI.  The IR value is essentially the "key" used to match
> corresponding storage locations across the two ABIs.  I'm transforming
a
> thread's current stack laid out for one ABI into one laid out for
another
> ABI.
>
>
>> A related question is: are you interested in the *values* or the
>> *locations* the values are in?  For instance if a specific value (say
>> the result of a load) is spilled at 0x80(%rsp) and is also present in
>> %r13 (callee saved register), then do you have to know both the
>> locations or just one of the two?
>>
>
> I'm actually only interested in being able to find values; I don't
> particularly care about where they're stored.  In your hypothetical, as
> long as the compiler could tell me that the value was stored in one of
> those locations, that'd be okay.
>
>
>>
>> > locate compiler-generated temporaries, hence I've been looking
at the
>> > StackMap intrinsic [1] to provide live value location information.
It
>> > does most of what I need, but it does not tell me where live
values
>> > stored in registers are spilled to the stack as part of the
function
>> > call procedure (whether they be in callee- or caller-saved
registers) --
>> > it simply tells me which registers they are stored in before/after
the
>> > function call procedure.  That's the impetus for my question.
>>
>> With stackmaps, is the problem that it tells you e.g. a live value is
>> present in %r9 (caller saved register), but when unwinding the value
>> may have been clobbered?  This is something other people have run into
>> as well -- specifically the distinction between "live on
call"
>> (available just before the call) vs. "live on return"
(available after
>> the callee returns).  I'm hazy on the details, but IIRC if this is
a
>> problem, then you may have problems bigger than just figuring out the
>> spill slots, since the caller saved register may not actually have
>> been spilled anywhere (since it does not need to live across the
>> call).
>>
>
> I'm not concerned about values that are not live across the call
("live on
> call"), only those that are live after returning from the call
("live on
> return").  If the value is not live after the call, there's no
need for me
> to able to recover it.  I just need to be able to resume execution in that
> function correctly, so I'm only concerned about values in caller-saved
> registers that are needed after the call completes, and therefore have been
> spilled to the stack as part of the procedure call standard.
>
> Because I'm rewriting the stack to change the ABI, I need to be able to
> set up the stack so that execution can correctly unwind back up the call
> chain.  This means that I need to be able to populate spill stack slots for
> caller-saved registers, hence this is why I need their locations.
>
> Thanks again for your help!
>
>
>> -- Sanjoy
>>
>>
>> > This is *not* a problem for callee-saved registers -- these
registers
>>
>> > are restored from the stack as part of the call frame unwinding
>> > procedure detailed in the DWARF standard [2].  However, I'm
left trying
>> > to find the locations of the live values that were in caller-saved
>> > registers and were spilled to the stack as part of the function
call
>> > procedure (probably during instruction selection/register
allocation,
>> > I'm not familiar enough with this process).  I realize that
for a
>> > MachineInstr for a given call there are no live values in
caller-saved
>> > registers (as they would be clobbered and lost), but where on the
stack
>> > were they saved?
>> >
>> > In a nutshell, I'm trying to figure out where values that
couldn't be
>> > placed in callee-saved registers (and that were allocated to
>> > caller-saved registers) were spilled to the stack as part of the
>> > function call procedure.  Hopefully this clarifies things --
thanks!
>> >
>> > [1] http://llvm.org/docs/StackMaps.html
>> > [2] http://dwarfstd.org/doc/DWARF4.pdf, page 140
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160628/5de534d8/attachment.html>

Hi Rob,

Robert Lyerly wrote:
 > The reason I can't just run a liveness analysis over stack slots and
 > registers in the backend is that I'm trying to map live value
locations
 > back up into their corresponding values in LLVM bitcode.  This is why
 > I'm using the stackmap intrinsic, as it does exactly that -- provides
a
 > mapping between a bitcode value and its storage location for the
 > generated assembly.  I need this intermediate-level value because I'm
 > doing ABI translation.  I'm plucking values out of a call frame laid
out
 > in one ABI and storing them in a destination stack frame that is laid
 > out according to another ABI.  The IR value is essentially the
"key"
 > used to match corresponding storage locations across the two ABIs. 
I'm
 > transforming a thread's current stack laid out for one ABI into one
laid
 > out for another ABI.

This sounds exactly like the deoptimization[1] mechanism we use (and
LLVM has support for), except that when deoptimizing the code being
returned into is (and the associated frame layout) is generally
"fixed" i.e. is the interpreter or a low tier JIT.

 >     A related question is: are you interested in the *values* or the
 >     *locations* the values are in?  For instance if a specific value (say
 >     the result of a load) is spilled at 0x80(%rsp) and is also present in
 >     %r13 (callee saved register), then do you have to know both the
 >     locations or just one of the two?
 >
 >
 > I'm actually only interested in being able to find values; I don't
 > particularly care about where they're stored.  In your hypothetical,
as
 > long as the compiler could tell me that the value was stored in one of
 > those locations, that'd be okay.

Again, this makes it very close to deoptimization.

 > I'm not concerned about values that are not live across the call
("live
 > on call"), only those that are live after returning from the call
("live
 > on return").  If the value is not live after the call, there's no
need
 > for me to able to recover it.  I just need to be able to resume
 > execution in that function correctly, so I'm only concerned about
values
 > in caller-saved registers that are needed after the call completes, and
 > therefore have been spilled to the stack as part of the procedure call
 > standard.
 >
 > Because I'm rewriting the stack to change the ABI, I need to be able
to
 > set up the stack so that execution can correctly unwind back up the call
 > chain.  This means that I need to be able to populate spill stack slots
 > for caller-saved registers, hence this is why I need their locations.

Ah, so the spill slots are not just pertinent from the POV of the
function you're translating out of, but is also pertinent for the
function you're translating *into*?

IOW, you want to translate

void foo_0() {
   spill %rax to offset 0x90
   call bar
   reload %rax from offset 0x90
   return %rax
}

to

void foo_1() {
   spill %rax to offset 0x100
   call bar
   reload %rax from offset 0x100
   return %rax
}

at the call site to bar, and want to know that the contents of 0x90
need to be copied to 0x100 if you rewrite the stack frame?

I'm not sure how much of your project you're okay in discussing on a
public mailing list, but I suspect the strategy for the best scheme
here will depend on how different the two functions are from each
other.

If all they differ is in the physical stack slot offsets, then I'd
just look at opaquely rewriting the slot offsets and not specifically
caring about live values.

If they differ at a fundamental level, then maybe you need something
like what we do for precise relocating GCs (see documentation on
gc.statepoint); otherwise, for instance, how do you know that a value
that is put in a caller-saved-register in one compilation is also in a
caller-saved-register (and not in a callee-saved-register or constant
folded or rematerialized away) in another compilation?

-- Sanjoy

[1]: Hölzle, Urs, Craig Chambers, and David Ungar. “Debugging
   optimized code with dynamic deoptimization.” ACM Sigplan
   Notices. Vol. 27. No. 7. ACM, 1992.