Kevin Modzelewski
2014-Oct-14 07:52 UTC
[LLVMdev] Thoughts on maintaining liveness information for stackmaps
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>
Andrew Trick
2014-Oct-14 16:19 UTC
[LLVMdev] Thoughts on maintaining liveness information for stackmaps
> 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 <mailto:atrick at apple.com>> wrote: > >> On Oct 13, 2014, at 5:45 PM, Kevin Modzelewski <kmod at dropbox.com <mailto: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/20141014/a049f2d6/attachment.html>
Kevin Modzelewski
2014-Oct-17 22:27 UTC
[LLVMdev] Thoughts on maintaining liveness information for stackmaps
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>