This is an archive of the discontinued LLVM Phabricator instance.

[LoopRotate] add ability to repeat loop rotation until non-deoptimizing exit is found
ClosedPublic

Authored by fedor.sergeev on Jan 20 2020, 11:01 AM.

Details

Summary

In case of loops with multiple exit where all-but-one exit are deoptimizing
it might happen that the first rotation will end up with latch having a deoptimizing
exit. This makes the loop unsuitable for trip-count analysis (say, getLoopEstimatedTripCount)
as well as for loop transformations that know how to handle multple deoptimizing exits.

It pretty much means that canonical form in multple-deoptimizing-exits case should be
with non-deoptimizing exit at latch.
Teach loop-rotation to reach this canonical form by repeating rotation.

-loop-rotate-multi option introduced to control this behavior, currently disabled by default.

Event Timeline

fedor.sergeev created this revision.Jan 20 2020, 11:01 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 20 2020, 11:01 AM
fedor.sergeev retitled this revision from [LoopRotate] add ability repeat loop rotation until non-deoptimizing exit is found to [LoopRotate] add ability to repeat loop rotation until non-deoptimizing exit is found.Jan 20 2020, 11:49 AM

paranoia: Consider splitting this patch into two parts. The first one by default disables multi-exit, while the second one just switch flag on.

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp
230

Side comment, May be it makes sense to keep note here in comment.
As I understand getPostdominatingDeoptimizeCall may return false even if it ends with deopt. Say if you have a loop before deoptimization. In this case there is no need to rotate but we will do.

599

Does'not you want to convert this recursion into iteration by moving this code to LoopRotate::processLoop?

fedor.sergeev marked 2 inline comments as done.Jan 20 2020, 11:03 PM
fedor.sergeev added inline comments.
llvm/lib/Transforms/Utils/LoopRotationUtils.cpp
230

Yep, situation when all exits are in fact postdominated by calls to deoptimize is possible.
However it is a really degenerate case (every exit is unlikely, so the loop is either unlikely itself or it is an endless loop, thus does not have finite trip-count).
We should not care what we do here.

599

Then it makes the patch looking much bigger than it actually is due to lots of whitespace changes.
I'm not sure it is worth the effort.
Perhaps do that separately?
The only benefit is that in loop form it becomes super-easy to limit amount of iterations.

skatkov accepted this revision.Jan 20 2020, 11:58 PM

Please wait for one or two days before landing for comments from others.

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp
230

My point was just to put a comment here that getPostdominatingDeoptimizeCall may return false conservatively.

599

Ok, but still I like iterations more than recursions here.

This revision is now accepted and ready to land.Jan 20 2020, 11:58 PM

improving some comments

fedor.sergeev marked an inline comment as done.Jan 21 2020, 4:08 AM

made this change off by default.

fedor.sergeev edited the summary of this revision. (Show Details)Jan 21 2020, 4:08 AM
fedor.sergeev marked an inline comment as done.
fedor.sergeev added inline comments.
llvm/lib/Transforms/Utils/LoopRotationUtils.cpp
599

I'm gonna try iterations and see how bad it is :)

converting recursion into inner loop

Hmm... phabricator is good in white-space diffs elimination! :)

fedor.sergeev marked 2 inline comments as done.Jan 21 2020, 4:32 AM
skatkov requested changes to this revision.Jan 21 2020, 7:05 AM
skatkov added inline comments.
llvm/lib/Transforms/Utils/LoopRotationUtils.cpp
269–320

if it is a second iteration you should return true here and in other places.

This revision now requires changes to proceed.Jan 21 2020, 7:05 AM

fixing return value on subsequent iterations

fedor.sergeev marked an inline comment as done.Jan 21 2020, 9:35 AM
fedor.sergeev added inline comments.
llvm/lib/Transforms/Utils/LoopRotationUtils.cpp
269–320

thanks for the catch!
Perhaps, I should add a test verifying that...

skatkov accepted this revision.Jan 21 2020, 7:42 PM
This revision is now accepted and ready to land.Jan 21 2020, 7:42 PM

unittest added that verifies exit code of successful loop-rotate

fedor.sergeev marked an inline comment as done.Jan 23 2020, 4:54 AM
This revision was automatically updated to reflect the committed changes.