Page MenuHomePhabricator

[LOOPGUARD] Disable loop with multiple loop exiting blocks.
ClosedPublic

Authored by Whitney on Aug 21 2019, 6:23 AM.

Details

Summary

As discussed in the loop group meeting. With the current definition of loop guard, we should not allow multiple loop exiting blocks. For loops that has multiple loop exiting blocks, we can simply unable to find the loop guard.

When getUniqueExitBlock() obtains a vector size not equals to one, that means there is either no exit blocks or there exists more than one unique block the loop exit to.
If we don't disallow loop with multiple loop exit blocks, then with our current implementation, there can exist exit blocks don't post dominated by the non pre-header successor of the guard block.

Diff Detail

Repository
rL LLVM

Event Timeline

Whitney created this revision.Aug 21 2019, 6:23 AM
fhahn added a subscriber: fhahn.Aug 21 2019, 9:14 AM

This needs a test with loops with multiple exit blocks.

Whitney updated this revision to Diff 216428.Aug 21 2019, 10:34 AM

Add a test case with multiple loop exiting blocks.

I don't remember why exactly this was necessary.
Looking at the current definition in LoopInfo.h, it's not immediately obvious to me either.
Could you either update the definition of getLoopGuardBranch in LoopInfo.h to state this case is not handled (and why). Or, if it's something obvious that I'm not seeing, expand the description here to make it clear?

Thanks.

Whitney updated this revision to Diff 221750.Sep 25 2019, 6:44 AM
Whitney edited the summary of this revision. (Show Details)

Any reason not to use Loop::getExitBlock()? The behavior is different when there are are multiple exiting edges to the same block, but does it matter? Maybe we should change Loop::getExitBlock() to only return nullptr if two different exit blocks exist, as e.g. getLoopPredecessor() already does.

llvm/lib/Analysis/LoopInfo.cpp
378 ↗(On Diff #221750)

I think that getUniqueExitBlocks never adds nullptr elements anyway. However, asserts don't hurt.

Any reason not to use Loop::getExitBlock()? The behavior is different when there are are multiple exiting edges to the same block, but does it matter? Maybe we should change Loop::getExitBlock() to only return nullptr if two different exit blocks exist, as e.g. getLoopPredecessor() already does.

Originally I used getExitBlock(), and found that the new test case MultiExitingLoop failed to find the loop guard, as getExitBlock() returns nullptr if there are more than one exiting block, even if all exiting blocks go to the same exit block. As the reason we want to add an early exit is because we don't check post dominations for all exit blocks, we don't need to exit early if there is only one unique exit block. I don't know if it matters, but more loops can find their guard in this way.

This revision is now accepted and ready to land.Sep 26 2019, 10:23 AM
kbarton accepted this revision.Sep 26 2019, 11:58 AM

LGTM.
Thanks for adding the comment.

Meinersbur added inline comments.Sep 26 2019, 12:14 PM
llvm/lib/Analysis/LoopInfo.cpp
372–375 ↗(On Diff #221750)

There actually is a LoopBase::getUniqueExitBlock() with this code inside. Could you use that one?

Whitney marked an inline comment as done.Sep 26 2019, 12:26 PM
Whitney added inline comments.
llvm/lib/Analysis/LoopInfo.cpp
372–375 ↗(On Diff #221750)

Thanks for letting me know. Not sure how I could missed it.

This revision was automatically updated to reflect the committed changes.
Whitney marked an inline comment as done.Sep 26 2019, 1:24 PM