[LLVMdev] Thoughts on maintaining liveness information for stackmaps

[Kevin Modzelewski]

Ok I will look into migrating the forwards analysis to a backwards one in
BranchFolder (and other places).  For now we're running with a simple patch
to the stackmaps liveness that ignores invalid registers in the live-out
set.

On Tue, Oct 14, 2014 at 9:19 AM, Andrew Trick <atrick at apple.com> wrote:

>
> On Oct 14, 2014, at 12:52 AM, Kevin Modzelewski <kmod at dropbox.com> wrote:
>
> 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.
>
>
> Yep, I can see that happening. It is a good example of why KILL flags
> cause more problems than they solve.
>
> 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?
>
>
> The forward analysis is ok if the client doesn’t need accuracy. It’s
> unfortunate that we’re using it to set LiveIns though. Technically it’s ok
> for LiveIns to be conservatively inaccurate, but very undesirable. So I can
> see three options:
>
> (1) It would be cool if BranchFolder and TailDup used proper backward
> liveness. The current implementation leaves around inconsistent LiveIn sets
> - it’s confusing and pessimizes downstream passes. That would solve your
> immediate problem and probably be good thing in general. However, I haven’t
> looked at the code to determine how complicated it will be to convert.
>
> (2) We could modify StackMapLivenessAnalysis to update LiveIns (not a pure
> analysis any more). That would entail changing the loop that iterates over
> blocks to iterate in reverse-post-order. It would be naturally conservative
> around loops which is fine. But since this runs so late, it won’t benefit
> any other passes. So it fixes your problem but is only marginally useful
> and we’ll get conservative liveness in the stackmap
>
> (3) We could just assume that ISEL scheduling did it’s job and no pass
> inserts a patchpoint later without checking physreg liveness first. Then
> StackMapLiveness can be easily modified to remove the patchpoints return
> value and clobbers from the liveset before calling addLiveOutSetToMI. To do
> that LiveRegs.stepBackward(MI) can be split into
> LiveRegs.removeDefsAndClobbers(MI) and LiveRegs.addUses(MI). We lose a
> little bit of verification and get conservative liveness in the stackmap,
> but it’s probably not a big deal.
>
> Feel free to file bugs against BranchFolder/TailDup if you end up going
> for an easy fix in StackMapLiveness instead.
>
> -Andy
>
> 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/20141017/cb96799b/attachment.html>