This is an archive of the discontinued LLVM Phabricator instance.

[Loop Peeling] Enable peeling for loops with multiple exits
ClosedPublic

Authored by skatkov on Jun 28 2019, 3:06 AM.

Details

Summary

This CL enables peeling of the loop with multiple exits where
one exit should be from latch and others are basic blocks with
call to deopt.

The peeling is enabled under the flag which is false by default.

Diff Detail

Event Timeline

skatkov created this revision.Jun 28 2019, 3:06 AM
reames requested changes to this revision.Jun 28 2019, 2:59 PM
reames added inline comments.
lib/Transforms/Utils/LoopUnrollPeel.cpp
65 ↗(On Diff #207021)

Submit disabled, then enable in future commit?

And maybe you want a three way choice: none, deopt-only, all?

84 ↗(On Diff #207021)

This looks like a useful helper function which could be factored out and reused, for example by canProfitablyUnrollMultiExitLoop.

Maybe: bool allNonLatchExitsDeoptimize or allNonLatchExitsPredicatedNeverTaken?

lib/Transforms/Utils/LoopUtils.cpp
626 ↗(On Diff #207021)

A suggestion here. Extend the existing function to allow multiple exits, but only if those exits have 0 taken probability. Return None for any exit with non-zero exit.

(I'm trying to avoid the need for the new function.)

This revision now requires changes to proceed.Jun 28 2019, 2:59 PM
skatkov marked 2 inline comments as done.Jul 2 2019, 12:23 AM
skatkov added inline comments.
lib/Transforms/Utils/LoopUnrollPeel.cpp
65 ↗(On Diff #207021)

Sure, will change to false.

I do not support the non deopt-only now in terms of update of branch weights. So introducing the explicit difference between deopt-only and all is not what I think make sense.

lib/Transforms/Utils/LoopUtils.cpp
626 ↗(On Diff #207021)

Unfortunately, zero probability is not what is used in llvm. Even BranchProbability analysis will set smallest but greater than zero probability for edge coming to block with unreachable terminator.

So if want to add a complexity to this method we should introduce some threshold below which we consider the exit has '0' probability.

Do you still see the value in it?
Please note that getLoopEstimatedTripCount is widely used in code base.

fhahn added inline comments.Jul 3 2019, 4:56 AM
lib/Transforms/Utils/LoopUnrollPeel.cpp
65 ↗(On Diff #207021)

I think it would be good for the naming to somehow reflect that we do not support any multi-exit loop, but just a very restricted set. The current naming/description sounds more general than the actual implementation.

skatkov updated this revision to Diff 207998.Jul 4 2019, 2:47 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 4 2019, 2:47 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
reames accepted this revision.Jul 9 2019, 10:30 AM

LGTM w/two requested changes before or after commit, no further review needed.

  1. allNonLatchExitsDeopt should be separated into a utility file and reused to implement the same (existing) check in the LoopUnroll code to ensure there's no accidental divergence.
  1. getEstimatedTripCount should return a answer for all loops it knows how to. After this change sequence, that will be single exit loops, and multiple exit loops where all non-latch exits are deopt calls. Existing callers should be updated to either a) add the single exit check or b) call a new shim function (getETCForSingleExitLoop) which contains the check.
This revision is now accepted and ready to land.Jul 9 2019, 10:30 AM
skatkov updated this revision to Diff 209416.Jul 11 2019, 10:44 PM

Handled Philip's comments.

I decided to avoid introduction of utility function for check that all side exits
end up with deopt. The current code with all_of looks short enough and clear
to understand. At the same time, the case in LoopUnrollruntime is more narrow
due to it supports only one side exits, so updating that case to use the same utility
function does not improve readability from my view.

Please take a look.

xbolva00 added inline comments.
llvm/lib/Transforms/Utils/LoopUnrollPeel.cpp
96

Nit: if (!Exists.empty())

This revision was automatically updated to reflect the committed changes.