llvm dev - Oct 2014 - [LLVMdev] Thoughts on maintaining liveness information for stackmaps

Hi all, I've run into a couple bugs recently that affected stackmap
liveness analysis in various ways:
http://llvm.org/bugs/show_bug.cgi?id=19224 - function arguments stay live
unnecessarily
http://llvm.org/bugs/show_bug.cgi?id=21265 - eflags can end up as a live out
http://llvm.org/bugs/show_bug.cgi?id=21266 - %rip can end up as a live out

The first two have nothing to do with stackmaps specifically but just end
up affecting it; the last two will crash the stackmaps code.  I think my
takeaway is that at this late point in the pipeline, the stackmaps liveness
code has to be the main consumer of this information, otherwise these kinds
of bugs/behavior would have been noticed.  So fixing them might mostly be
in the interest of the stackmaps code, and I'm wondering if even if we do
classify these as bugs and fix them, if there would be a runtime cost paid
by non-stackmaps-using code.  I'm also worried that there might be more
than these three bugs and it might be a bit of a losing battle if getting
this perfectly right isn't useful beyond just stackmaps.


So I guess my question is: should we try to fix all these issues, or accept
that there can potentially be some extra registers in the live-outs set
when we get around to emitting the stackmaps section?  (Or another option?)
 By "accepting the possibility", I'm meaning that we could filter
out
non-feasible registers like eflags and rip, and consumers would have to
accept that there might be extra registers that are included unnecessarily
(which can already happen).

I created a hacky little patch that simply ignores bogus registers when
doing the liveness calculation:
https://github.com/kmod/pyston/blob/73a1a9897ec649f2249a69d523c820c0d4321786/llvm_patches/0009-Filter-out-extraneous-registers-from-live-outs-like-.patch
Not sure if this is the kind of approach we would like to go with, but so
far in my very limited testing it seems to be ok and at least things don't
crash.  What do you guys think?

kmod
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20141013/d0c31533/attachment.html>

> On Oct 13, 2014, at 5:45 PM, Kevin Modzelewski <kmod at dropbox.com>
wrote:
> 
> Hi all, I've run into a couple bugs recently that affected stackmap
liveness analysis in various ways:
> http://llvm.org/bugs/show_bug.cgi?id=19224
<http://llvm.org/bugs/show_bug.cgi?id=19224> - function arguments stay
live unnecessarily
> http://llvm.org/bugs/show_bug.cgi?id=21265
<http://llvm.org/bugs/show_bug.cgi?id=21265> - eflags can end up as a live
out
> http://llvm.org/bugs/show_bug.cgi?id=21266
<http://llvm.org/bugs/show_bug.cgi?id=21266> - %rip can end up as a live
out
> 
> The first two have nothing to do with stackmaps specifically but just end
up affecting it; the last two will crash the stackmaps code.  I think my
takeaway is that at this late point in the pipeline, the stackmaps liveness code
has to be the main consumer of this information, otherwise these kinds of
bugs/behavior would have been noticed.  So fixing them might mostly be in the
interest of the stackmaps code, and I'm wondering if even if we do classify
these as bugs and fix them, if there would be a runtime cost paid by
non-stackmaps-using code.  I'm also worried that there might be more than
these three bugs and it might be a bit of a losing battle if getting this
perfectly right isn't useful beyond just stackmaps.
> 
> 
> So I guess my question is: should we try to fix all these issues, or accept
that there can potentially be some extra registers in the live-outs set when we
get around to emitting the stackmaps section?  (Or another option?)  By
"accepting the possibility", I'm meaning that we could filter out
non-feasible registers like eflags and rip, and consumers would have to accept
that there might be extra registers that are included unnecessarily (which can
already happen).
> 
> I created a hacky little patch that simply ignores bogus registers when
doing the liveness calculation:
https://github.com/kmod/pyston/blob/73a1a9897ec649f2249a69d523c820c0d4321786/llvm_patches/0009-Filter-out-extraneous-registers-from-live-outs-like-.patch
<https://github.com/kmod/pyston/blob/73a1a9897ec649f2249a69d523c820c0d4321786/llvm_patches/0009-Filter-out-extraneous-registers-from-live-outs-like-.patch>
Not sure if this is the kind of approach we would like to go with, but so far in
my very limited testing it seems to be ok and at least things don't crash. 
What do you guys think?
The %RIP problem is a straightforward bug resulting from the X86 target lying to
LLVM about RIP being a register. The fix is that LivePhysRegs should not track
reserved regs. But before fixing that, we have to be careful about which
registers stackmap clients are expected to preserve "no matter what",
and the rest of the LLVM reserved regs (e.g. base pointer) should just be
unconditionally added to the live set. We can continue that discussion in the
PR.

LivePhysRegs.stepBackward should be completely valid at any point, so if there
are bugs they need to be fixed.  LivePhysRegs.stepForward is conservative and
relies on KILL flags so should only be used very early in the MI pipeline for
convenience as an optimization. StackMapLivenessAnalysis uses stepBackward so
should not depend on KILL flags at all. LivePhysRegs should not modify any MI
operands, so KILL flags shouldn’t be getting “removed” by anything related to
stackmaps or liveness.

Note that we would like to move to a world where KILL flags are completely
removed before allocating physical registers. Subsequent passes can use a
liveness utility to get the same information in a robust way. Unfortunately,
some target specific passes still work better with KILL flags and no one seems
to be working on migrating them. Although we can't eliminate KILL flags from
late passes yet, they are not required, and passes can safely drop them - in
fact a pass must either ensure the flags are accurate or drop them.

I think it’s nice that the StackMap implementation forces all live registers to
be dwarf encodable. It’s kind of important that LLVM ensure that EFLAGS are not
live across a patchpoint!

I’m honestly not sure why you’re hitting the first two bugs (function
args/eflags). I think the liveness and stackmap code is doing the right thing
here.

-Andy

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20141013/f56fd585/attachment.html>

I think what's happening is BranchFolder::MaintainLiveIns is using a
forward analysis on top of these missing kill flags, and updating the
BB-live-ins/live-outs with an incorrect set of registers.  Then when the
stackmaps liveness analysis happens, it's not doing anything wrong, but it
starts with the wrong set of live registers and will propagate those to the
point of the patchpoint/stackmap.

For now it might be possible to just fix BranchFolder (and also
TailDuplicatePass::TailDuplicate) to use a backwards analysis as well, but
if we really wanted to make sure that the liveness information was accurate
when the stackmaps code looks at it, wouldn't we need to get rid of
anything that supports forward liveness analysis?

On Mon, Oct 13, 2014 at 8:27 PM, Andrew Trick <atrick at apple.com> wrote:
>
> On Oct 13, 2014, at 5:45 PM, Kevin Modzelewski <kmod at dropbox.com>
wrote:
>
> Hi all, I've run into a couple bugs recently that affected stackmap
> liveness analysis in various ways:
> http://llvm.org/bugs/show_bug.cgi?id=19224 - function arguments stay live
> unnecessarily
> http://llvm.org/bugs/show_bug.cgi?id=21265 - eflags can end up as a live
> out
> http://llvm.org/bugs/show_bug.cgi?id=21266 - %rip can end up as a live out
>
> The first two have nothing to do with stackmaps specifically but just end
> up affecting it; the last two will crash the stackmaps code.  I think my
> takeaway is that at this late point in the pipeline, the stackmaps liveness
> code has to be the main consumer of this information, otherwise these kinds
> of bugs/behavior would have been noticed.  So fixing them might mostly be
> in the interest of the stackmaps code, and I'm wondering if even if we
do
> classify these as bugs and fix them, if there would be a runtime cost paid
> by non-stackmaps-using code.  I'm also worried that there might be more
> than these three bugs and it might be a bit of a losing battle if getting
> this perfectly right isn't useful beyond just stackmaps.
>
>
> So I guess my question is: should we try to fix all these issues, or
> accept that there can potentially be some extra registers in the live-outs
> set when we get around to emitting the stackmaps section?  (Or another
> option?)  By "accepting the possibility", I'm meaning that we
could filter
> out non-feasible registers like eflags and rip, and consumers would have to
> accept that there might be extra registers that are included unnecessarily
> (which can already happen).
>
> I created a hacky little patch that simply ignores bogus registers when
> doing the liveness calculation:
>
https://github.com/kmod/pyston/blob/73a1a9897ec649f2249a69d523c820c0d4321786/llvm_patches/0009-Filter-out-extraneous-registers-from-live-outs-like-.patch
> Not sure if this is the kind of approach we would like to go with, but so
> far in my very limited testing it seems to be ok and at least things
don't
> crash.  What do you guys think?
>
>
> The %RIP problem is a straightforward bug resulting from the X86 target
> lying to LLVM about RIP being a register. The fix is that LivePhysRegs
> should not track reserved regs. But before fixing that, we have to be
> careful about which registers stackmap clients are expected to preserve
"no
> matter what", and the rest of the LLVM reserved regs (e.g. base
pointer)
> should just be unconditionally added to the live set. We can continue that
> discussion in the PR.
>
> LivePhysRegs.stepBackward should be completely valid at any point, so if
> there are bugs they need to be fixed.  LivePhysRegs.stepForward is
> conservative and relies on KILL flags so should only be used very early in
> the MI pipeline for convenience as an optimization.
> StackMapLivenessAnalysis uses stepBackward so should not depend on KILL
> flags at all. LivePhysRegs should not modify any MI operands, so KILL flags
> shouldn’t be getting “removed” by anything related to stackmaps or
liveness.
>
> Note that we would like to move to a world where KILL flags are completely
> removed before allocating physical registers. Subsequent passes can use a
> liveness utility to get the same information in a robust way.
> Unfortunately, some target specific passes still work better with KILL
> flags and no one seems to be working on migrating them. Although we
can't
> eliminate KILL flags from late passes yet, they are not required, and
> passes can safely drop them - in fact a pass must either ensure the flags
> are accurate or drop them.
>
> I think it’s nice that the StackMap implementation forces all live
> registers to be dwarf encodable. It’s kind of important that LLVM ensure
> that EFLAGS are not live across a patchpoint!
>
> I’m honestly not sure why you’re hitting the first two bugs (function
> args/eflags). I think the liveness and stackmap code is doing the right
> thing here.
>
> -Andy
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20141014/d5f0d9bd/attachment.html>