This is an archive of the discontinued LLVM Phabricator instance.

[DSE] Enable removal of lifetime intrinsics in terminating blocks
ClosedPublic

Authored by dotdash on Aug 2 2015, 5:56 AM.

Diff Detail

Event Timeline

dotdash updated this revision to Diff 31204.Aug 2 2015, 5:56 AM
dotdash retitled this revision from to [SimplifyCFG] Ignore lifetime intrinsics when looking for empty landing pads.
dotdash updated this object.
dotdash added a reviewer: reames.
dotdash added a subscriber: llvm-commits.
reames edited edge metadata.Aug 3 2015, 5:36 PM

The code looks completely correct, but I'm a bit unsure it's the right approach. In particular, it seems undesirable to loose lifetime information in a particular resume path before inlining. If we have a lifetime.end along one path, but not another, that's an interesting optimization fact. After inlining, that could result in further simplification of the caller. Have you thought about the trade offs here?

It seems like a lifetime end for an alloca in a terminating block adds no information. Similarly, the liftime.start is redundant. This patch would be obviously correct if restricted to values derived from allocas, but even there, maybe the removal should be done elsewhere? In particular, this seems a lot like a DSE problem. Thoughts?

In my case, the callee also contained a call to llvm.lifetime.end, so I didn't consider the removal a problem even if the callee is inlined. But of course you're right, in the general case this could preclude further optimizations.

The problem I saw with handling it as a DSE problem is that you can't handle the lifetime intrinsics for a given alloca in isolation. Given a terminating block like this:

out:
    call void @llvm.lifetime.start(i64 16, i8* %a)
    ; Use %a
    call void @llvm.lifetime.end(i64 16, i8* %a)
    call void @llvm.lifetime.start(i64 16, i8* %b)
    ; Use %b
    call void @llvm.lifetime.end(i64 16, i8* %b)
    ret void

Here, the lifetime end is useful stack coloring, even though it's in a terminating block.

Thinking about it some more though, I think that we could track whether we found a lifetime start that we didn't remove yet, and until that is the case, we can strip lifetime ends without affecting stack coloring. So for the above, the lifetime end for %b would get removed, but the other lifetime intrinsics are kept. But if %b was unused, we'd also remove its lifetime start, and then go on to also remove the lifetime end for %a.

Sounds good?

dotdash updated this revision to Diff 31800.Aug 11 2015, 6:12 AM
dotdash edited edge metadata.

Replaced the original approach of ignoring lifetime intrinsic when looking for
empty landing pads with an implementation that enhances DSE to remove lifetime
intrinsics from terminating blocks.

dotdash retitled this revision from [SimplifyCFG] Ignore lifetime intrinsics when looking for empty landing pads to [DSE] Enable removal of lifetime intrinsics in terminating blocks.Aug 11 2015, 6:13 AM
reames added inline comments.Aug 12 2015, 11:29 AM
lib/Transforms/Scalar/DeadStoreElimination.cpp
737 ↗(On Diff #31800)

The isLifetimeStart variable appears redundant. I'd just check if BBI is a lifetime start at the one place you use this.

739 ↗(On Diff #31800)

More generally, the special casing here seems unneccessary. It looks like there is already handling in hasMemoryWrite and isRemovable for lifetime_end. I think you just need to adjust that logic and possible pass in the removeLifetimeEnds flag.

786 ↗(On Diff #31800)

You might consider adding the code to handle a value where isLifetimeStart is the only remaining use of an operand, but feel free to defer that until another patch. You should also check to see if isTrivialDead already catches that case.

Looking at your test case, it looks like something *is* removing the lifetime start. You might want to look into that to make sure you understand why.

test/Transforms/DeadStoreElimination/lifetime.ll
39 ↗(On Diff #31800)

Remove the personality function if it's not required please.

42 ↗(On Diff #31800)

The fact this is an invoke isn't relevant to the test case is it? If not, please use a call. If you're just using this to break the block, consider a branch on an i1 argument.

57 ↗(On Diff #31800)

I don't see where this check-not comes from in the code. Can you explain? This makes me slightly nervous that I'm not understanding the patch. (Feel free to revise and then explain/investigate only if this artifact persists.)

87 ↗(On Diff #31800)

Same here.

The test with invoke was just to have an unwind block, because that's what my original testcase had. I'll remove that test because with just a call it adds nothing that isn't already handled in the other tests.

I'll keep the special casing for lifetime start/end for now given because I think I need it for lifetime start anyway and that keeps hasMemoryWrite and isRemovable simpler. If you think it's better to integrate the special case with those two functions though, I'll do that.

lib/Transforms/Scalar/DeadStoreElimination.cpp
739 ↗(On Diff #31800)

I guess my failure to rename removeLifetimeEnds after I changed the logic caused some confusion here. It should really be called removeLifetimeIntrinsics.

The idea here is to remove all lifetime intrinsics (start and end) for dead objects, until we hit a lifetime start for a live object. The case for lifetime_start below falls through to lifetime_end. Should have added a comment for that.

That's also why I did not touch hasMemoryWrite because handling lifetime_start there seemed wrong to me.

786 ↗(On Diff #31800)

See above, the removal of both kinds of lifetime intrinsics is intended, I just chose a misleading name for the flag that guards it.

isIntructionTriviallyDead only handles lifetime intrinsics on undef values.

dotdash updated this revision to Diff 32140.Aug 14 2015, 1:59 AM

[DSE] Enable removal of lifetime intrinsics in terminating blocks

Usually DSE is not supposed to remove lifetime intrinsics, but it's
actually ok to remove them for dead objects in terminating blocks,
because they convey no extra information there. Until we hit a lifetime
start that cannot be removed, that is. Because from that point on the
lifetime intrinsics become interesting again, e.g. for stack coloring.

dotdash added inline comments.Aug 18 2015, 11:59 AM
lib/Transforms/Scalar/DeadStoreElimination.cpp
781 ↗(On Diff #32140)

Oh, I only now realized that I need to move my check for lifetime start intrinsics that can't be removed down after the isInstructionTriviallyDead part. Otherwise we would stop removing lifetime intrinsics too soon. I'll update the patch accordingly and add a test case for lifetime intrinsics on undef pointers.

dotdash updated this revision to Diff 32438.Aug 18 2015, 12:38 PM

Updated to correctly handle lifetime intrinsics on undef pointers

reames accepted this revision.Aug 19 2015, 9:49 AM
reames edited edge metadata.

LGTM w/minor comments addressed. No further rounds of review needed.

lib/Transforms/Scalar/DeadStoreElimination.cpp
852 ↗(On Diff #32438)

Naming wise, please use canRemoveLifetimeIntrinsics. This is a legality check, so let's make that obvious.

Add a one line comment to describe purpose. e.g.
// becomes false once lifetime intrinsics are observable or useful for stack colouring

864 ↗(On Diff #32438)

I still think that the handling you've added could be done by extending getStoredPointerOperand, hasMemoryWrite, and isRemovable, however, I won't require this. These are used in enough other places that changing them would require a good amount of care and is somewhat risky for minimal gain. I'd still prefer that - it seems like the better long term choice - but I won't hold the review on that.

What bugs me about the special casing is that lifetime begin and end *are* stores. They just store undef into the memory instead of a real value. (Caveat. I believe that's a conservatively correct interpretation, but I think the actual semantics are a bit less strict per previous mailing list discussions.)

test/Transforms/DeadStoreElimination/lifetime.ll
14 ↗(On Diff #32438)

It looks like this store is also now dead, mind adding an check line for that?

This revision is now accepted and ready to land.Aug 19 2015, 9:49 AM
This revision was automatically updated to reflect the committed changes.

I had to revert this because it caused test failures in clang, which made me realize that this interacts badly with inlining as it is. The inliner only adds lifetime intrinsics for an inlined alloca if there are no lifetime intrinsics for this alloca at all. But with this patch, we can end up with an alloca that only has a lifetime start but no end. In that case, the inliner wouldn't add lifetime intrinsics, leading to worse stack coloring than before.

Interesting. Definitely not an interaction I saw coming. Do you have
any thoughts on how to address? I'm assuming we need to tweak the
inliner's logic here, but I'm not familiar enough with the code in
question to give good suggestions.

Philip

I don't have a plan for this yet. Basically, it seems like we'd have to check for each terminator that is not dominated by a lifetime end whether it is dominated by a lifetime start for each alloca in the function that is being inlined. I'm not sure whether that's feasible or if it would end up being too expensive. Any input is very welcome.