This is an archive of the discontinued LLVM Phabricator instance.

[LoopUtils] Extend the scope of getLoopEstimatedTripCount
ClosedPublic

Authored by skatkov on Jul 11 2019, 3:32 AM.

Details

Summary

With this patch the getLoopEstimatedTripCount function will
accept also the loops where there are more than one exit but
all exits except latch block should ends up with a call to deopt.

This side exits should not impact the estimated trip count.

Diff Detail

Event Timeline

skatkov created this revision.Jul 11 2019, 3:32 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 11 2019, 3:32 AM
Herald added a subscriber: hiraditya. · View Herald Transcript

May be good to have a test.

fhahn added a subscriber: fhahn.Jul 11 2019, 4:01 AM
fhahn added inline comments.
llvm/lib/Transforms/Utils/LoopUtils.cpp
624

Would it make sense to remove the restriction of having a single exit block/only deopt non latch exit by generalizing the function?

Wouldn't' it be reasonable to estimate the trip count by summing up the weights of all exit edges and dividing by the weight of the back-edge to the header? That should naturally cover the deopt cases as well, as they should have very low weights, right?

In any case, we should also update the doc-comment in the header describing the new behavior.

skatkov marked an inline comment as done.Jul 11 2019, 11:00 PM
skatkov added inline comments.
llvm/lib/Transforms/Utils/LoopUtils.cpp
624

Hi Florian, thank you for your comment.

I think that sum of exit weights from different branches is not a good idea. We can compare/use only probabilities not the real values.

Let's consider the following case, we have a loop with two exits. One of them has weights (10, 1) and the second one (1,1). for simplicity the second number is a weight of exit.

What will be Trip Count in this case?
According to your proposed formula it is 5. Looks strange.

Moreover it is totally fine to scale the weights by some constant. For example, (1,1) is actually the same as (100, 100).
In this case according to formula trip count will be 0.

So I think that it is not incorrect and to get the right formula is not really easy task, so I just want to adjust only guard of this formula for the moment.

With respect to update the header, The header description does not mention the restriction about only one exit now. It is more general and correct. If we can provide estimated trip count we do that. With my additional guard nothing changed.

If you really want to see that details in the header, please let me know and I will update a header.

May be good to have a test.

The tests using this functionality can be found in https://reviews.llvm.org/D63923 and https://reviews.llvm.org/D64618 or you need a separate unit test?

reames accepted this revision.Jul 12 2019, 10:50 AM

LGTM w/required fix before submit.

llvm/lib/Transforms/Utils/LoopUtils.cpp
624

I'd ask that we specifically do not extend the scope of this patch. A separate patch can expand scope, but let's start with something low risk, make sure the caller code is well exercised, then increase the scope. Working in stages to reduce risk is important.

628

There's a missing correctness check here. There's no guarantee that a loop *must* have a unique latch, so you need null check the result before dereferencing. Non unique latches are non-canonical, so you can just bail on that case.

Note that unique exit implies unique latch previously.

This revision is now accepted and ready to land.Jul 12 2019, 10:50 AM
skatkov marked an inline comment as done.Jul 14 2019, 8:44 PM
skatkov added inline comments.
llvm/lib/Transforms/Utils/LoopUtils.cpp
628

To be honest I do not understand how unique exit implies unique latch but I can add additional check.

This revision was automatically updated to reflect the committed changes.
efriedma added inline comments.
llvm/trunk/lib/Transforms/Utils/LoopUtils.cpp
640 ↗(On Diff #209764)

I'm seeing Assertion 'L->hasDedicatedExits() && "getUniqueExitBlocks assumes the loop has canonical form exits!"' failed. with some out-of-tree code that calls getLoopEstimatedTripCount. Does this analysis really require that the loop has dedicated exits? If it does, can we guard this call so getLoopEstimatedTripCount fails gracefully for loops without dedicated exits?

I think all the in-tree users of getLoopEstimatedTripCount require dedicated exits for other reasons, so no bug report.

skatkov marked an inline comment as done.Jul 15 2019, 8:18 PM
skatkov added inline comments.
llvm/trunk/lib/Transforms/Utils/LoopUtils.cpp
640 ↗(On Diff #209764)

Hello Eli,

getUniqueExitBlocks is written in a way that it expects that all predecessors of successor of loop's basic block is in a loop.

I totally fine to add a guard to fail gracefully. Will publish a patch in a couple of hours.

skatkov marked an inline comment as done.Jul 15 2019, 8:50 PM
skatkov added inline comments.
llvm/trunk/lib/Transforms/Utils/LoopUtils.cpp
640 ↗(On Diff #209764)

Hi again,

It is interesting catch. It seems I introduced a bug while adding getUniqueNonLatchExitBlocks utility function.
It seems that getUniqueExitBlocksHelper is written in a way it expects that all exits's first predecessor is in a loop and no need to check others predecessors. In case I skip latch I can miss the exit if it has two predecessors: latch and non-latch.

I will try to write a test and then re-write the getUniqueExitBlocksHelper function. So assert will be eliminated from it.

Thank you for pointing to this issue.

skatkov marked an inline comment as done.Jul 16 2019, 12:58 AM
skatkov added inline comments.
llvm/trunk/lib/Transforms/Utils/LoopUtils.cpp
640 ↗(On Diff #209764)

See D64787