This is an archive of the discontinued LLVM Phabricator instance.

[SimpleLoopUnswitch] Unswitch by experimental.guard intrinsics
ClosedPublic

Authored by mkazantsev on Oct 25 2018, 10:22 PM.

Details

Summary

This patch adds support of llvm.experimental.guard intrinsics to non-trivial
simple loop unswitching. These intrinsics represent implicit control flow which
has pretty much the same semantics as usual conditional branches. The
algorithm of dealing with them is following:

  • Consider guards as unswitching candidates;
  • If a guard is considered the best candidate, turn it into a branch;
  • Apply normal unswitching algorithm on this branch.

The patch has no compile time effect on code that does not contain any guards.

Diff Detail

Event Timeline

mkazantsev created this revision.Oct 25 2018, 10:22 PM

While this is a neat way to handle this, I'm a bit worried about the effects of it...

Does normal unswitch do the same thing currently?

Have you looked at how hard it would be to handle this case directly rather than by introducing a branch?

lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2253–2255

What happens if the guard isn't unswitched? Will anything clean up the branch?

2451–2452

Needs clang-format?

The old version of unswitching only needs a condition to unswitch on, not a particular user of this condition. That's why guards and branches can be handled in the same manner there. New one, however, also needs info about the particular user (which is currently always a terminator instruction). The boons it gives to us is that we can make a surgical DT and LI update and not invalidate these analyzes as a whole. The underlying logic in unswitchNontrivialInvariants deeply specializes on the terminator type (either branch of switch), and introducing a new type of a user (which is also a non-terminator) will make us write a lot of ugly duplicating code or mess up the existing code. It will also be bug prone.

I think it's not worth doing because I hope that we will be able to get rid of llvm.experimental.guard at all once we have D51207 merged. In that case, guards will be expressed as normal branches. I put a lot of faith into this patch, that's why I don't want to mess up the existing code (or duplicate it) just to support something that isn't going to live long.

lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2253–2255

Nope. As far as I'm aware, unswitchNontrivialInvariants can only return false if one of successors starts with CleanupPadInst, which is not the case we have after this split. I believe that in practice unswitching should be always successful after this transform. I placed a TODO to follow-up on this in the future (I think we need to assert that fact).

mkazantsev marked an inline comment as done.

Fixed formatting.

mkazantsev added inline comments.Oct 26 2018, 12:54 AM
lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2253–2255

The only way how unswitch may fail is marked as FIXME:

// We cannot unswitch if exit blocks contain a cleanuppad instruction as we
// don't know how to split those exit blocks.
// FIXME: We should teach SplitBlock to handle this and remove this
// restriction.
for (auto *ExitBB : ExitBlocks)
  if (isa<CleanupPadInst>(ExitBB->getFirstNonPHI()))
    return false;

I think it's more or less OK to not heal the guard if unswitching failed, provided that there is a plan to either make it unfailable or migrate to new guards representation in D51207.

mkazantsev planned changes to this revision.Oct 26 2018, 12:57 AM
mkazantsev added inline comments.
lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2476

We should signal that we did this and return Changed.

mkazantsev marked an inline comment as done.

Fixed Changed reporting for case when lowering was successful and unswitching was not.

The old version of unswitching only needs a condition to unswitch on, not a particular user of this condition. That's why guards and branches can be handled in the same manner there. New one, however, also needs info about the particular user (which is currently always a terminator instruction). The boons it gives to us is that we can make a surgical DT and LI update and not invalidate these analyzes as a whole. The underlying logic in unswitchNontrivialInvariants deeply specializes on the terminator type (either branch of switch), and introducing a new type of a user (which is also a non-terminator) will make us write a lot of ugly duplicating code or mess up the existing code. It will also be bug prone.

I think it's not worth doing because I hope that we will be able to get rid of llvm.experimental.guard at all once we have D51207 merged. In that case, guards will be expressed as normal branches. I put a lot of faith into this patch, that's why I don't want to mess up the existing code (or duplicate it) just to support something that isn't going to live long.

Thanks for the background context on why you're going with this approach. I think it makes total sense in that context.

I think it might be good to write some of this information down in the documentation next to the code. Something along the lines of:

/// FIXME: Eventually, the use of this routine to handle guard intrinsics should be removed in favor of non-implicit control flow intrinsics, or re-visited to ensure we have a sustainable approach. The approach here of converting to branches is intended to be a simple and hopefully not long-term mechanism to support the existing users of guard intrinsics.
chandlerc added inline comments.Oct 26 2018, 1:21 AM
lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2253–2255

I think you should just go ahead and assert this.

Because this code is *creating* the branch, it can (and does) ensure that the resulting branch does not go to a block with a cleanup pad. The invariant that this is an unswitchable condition should always hold and we should just verify it.

Then we don't even need to discuss cleanups, etc.

mkazantsev added inline comments.Oct 26 2018, 1:31 AM
lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2253–2255

Unfortunately, unswitching breaks is *any* exit block has a cleanup. :( I was able to construct such test:

define void @test_cleanuppad(i1 %cond, i32 %N) uwtable ssp personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {

entry:
  br label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
  call void (i1, ...) @llvm.experimental.guard(i1 %cond) [ "deopt"() ]
  %iv.next = add i32 %iv, 1
  invoke void @may_throw(i32 %iv) to label %loop unwind label %exit

exit:
  %cp = cleanuppad within none []
  cleanupret from %cp unwind to caller

}

I think we can make the cleanup check before we make any transform, and therefore we guarantee that the unswitching is always successful.

mkazantsev planned changes to this revision.Oct 26 2018, 1:31 AM
chandlerc added inline comments.Oct 26 2018, 1:47 AM
lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2253–2255

Ah, nice test case, and yeah I like the idea of making this layer check the conditions necessary.

Rebased on top of https://reviews.llvm.org/D53747. Now we know for sure that we have a point after which the unswitching will succeed, and we don't need to worry about turning guard into a branch and then failing to unswitch.

chandlerc accepted this revision.Oct 26 2018, 2:25 AM

Generally looks fine, two minor adjustments below and LGTM once the underlying cleanuppad change lands.

lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2253–2254

Update comment to reflect that this is now accurate?

2270–2277

I assume this is trying to avoid the cost of looking for a guard intrinsic? We already walk all the instructions in the loop several times in this routine, so I'm not sure this matters much in practice. I'd just skip this and check the flag below.

This revision is now accepted and ready to land.Oct 26 2018, 2:25 AM
mkazantsev added inline comments.Oct 26 2018, 2:42 AM
lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2478

I just realized that we should add the newly-created exit block to the array here.

mkazantsev marked an inline comment as done.

Added the new exit block to the vector. Though it was pretty straightforward, I will re-run my fuzz testing to make sure everything is fine now.

lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2270–2277

Maybe we'll remove it in future, but I see no harm in it.

mkazantsev marked an inline comment as done.Oct 26 2018, 3:14 AM
This revision was automatically updated to reflect the committed changes.