Page MenuHomePhabricator

[LoopUnswitch] Add shortcut if unswitched path is a no-op.
ClosedPublic

Authored by fhahn on Jan 26 2021, 12:11 PM.

Details

Summary

If we determine that the invariant path through the loop has no effects,
we can directly branch to the exit block, instead to unswitching first.

Besides avoiding some extra work (unswitching first, then deleting the
loop again) this allows to be more aggressive than regular unswitching
with respect to cost-modeling. This approach should always be be
desirable.

This is similar in spirit to D93734, just that it uses the previously
added checks for loop-unswitching.

I tried to add the required no-op checks from scratch, as we only check
a subset of the loop. There is potential to unify the checks with
LoopDeletion, at the cost of adding a predicate whether a block should
be considered.

Diff Detail

Event Timeline

fhahn created this revision.Jan 26 2021, 12:11 PM
fhahn requested review of this revision.Jan 26 2021, 12:12 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 26 2021, 12:12 PM
jdoerfert added inline comments.Jan 26 2021, 12:26 PM
llvm/lib/Transforms/Scalar/LoopUnswitch.cpp
655

I would have assumed true here and no = true below.

733

Both assignments should not be needed, or assertions.

848

So the single exit stuff is not actually a conceptual requirement here, is it? I assume you need a single exit for your transformation but you could also collect all exists and later decide to act on them or not, right? Looking at no_partial_unswitch_shortcut_multi_exit, it has a single exit actually, it can be reached from multiple exiting blocks but a single exit.

1102

Flip the order here. First the shorter case where we use unswitchIfProfitable then the more complex one. The way it is is harder to read.

fhahn updated this revision to Diff 319537.Jan 27 2021, 5:26 AM

Thanks for taking a look!

updated to add additional tests, move IVConditionInfo creation to HasNoClobbersOnPath

fhahn marked an inline comment as done.Jan 27 2021, 5:33 AM
fhahn added inline comments.
llvm/lib/Transforms/Scalar/LoopUnswitch.cpp
733

I changed the code so IVConditionInfo is constructed here and returned directly by this function. So we can just start out with the (adjusted) defaults.

848

If multiple exit blocks can be reached, we would need to create a new exit block and branch to the correct original exit. Doable, but I am not sure it is worth the effort, at least initially.

Thanks for pointing out the issue in no_partial_unswitch_shortcut_multi_exit. This can indeed be handled by the current logic (different exiting blocks branching to the same exit block). I updated the logic above to support this case.

1102

The main advantage of doing the 'no-op path' handling first is that it avoids full unswitching. If we do unswitchIfProfitable first, then we might unnecessarily do full unswitching. Functionally it shouldn't be a big deal, because loop-delete should just remove the loop again, but it skips a bit of unnecessary work.

mdchen added a subscriber: mdchen.Jan 29 2021, 5:22 PM
jdoerfert accepted this revision.Jan 31 2021, 12:16 PM

LGTM

llvm/lib/Transforms/Scalar/LoopUnswitch.cpp
799

FWIW, any maximal trip count is fine, no need for a constant one.

1102

I see, I didn't realize that, thanks.

This revision is now accepted and ready to land.Jan 31 2021, 12:16 PM
This revision was landed with ongoing or failed builds.Feb 1 2021, 1:04 AM
This revision was automatically updated to reflect the committed changes.