Page MenuHomePhabricator

Revert Revert [MBP] do not rotate loop if it creates extra branch

Authored by skatkov on Jun 28 2017, 2:57 AM.



This is a second attempt to land this patch.

The first one resulted in a crash of clang sanitizer buildbot.
The fix is here and regression test is added.

This is a last fix for the corner case of PR32214. Actually this is not really corner case in general.

We should not do a loop rotation if we create an additional branch due to it.
Consider the case where we have a loop chain H, M, B, C , where
H is header with viable fallthrough from pre-header and exit from the loop
M - some middle block
B - backedge to Header but with exit from the loop also.
C - some cold block of the loop.

Let's H is determined as a best exit. If we do a loop rotation M, B, C, H we can introduce the extra branch.
Let's compute the change in number of branches:
+1 branch from pre-header to header
-1 branch from header to exit
+1 branch from header to middle block if there is such
-1 branch from cold bock to header if there is one

So if C is not a predecessor of H then we introduce extra branch.

This change actually prohibits rotation of the loop if both true

Best Exit has next element in chain as successor.
Last element in chain is not a predecessor of first element of chain.

Diff Detail


Event Timeline

skatkov created this revision.Jun 28 2017, 2:57 AM

Hi Kyle,

please review the patch with a fix.

Thank you in advance!

1975 ↗(On Diff #104369)

The crash was on this line due to in some conditions ExitingBB may be the last BB in a chain.
The added regression test shows this condition. Specifically it is possible that ExitingBB has a fallthrough but it is not viable. For example, if exit block is a member of another loop which has been rotated and it results that there is no fallthrough from ExitingBB to loop header of another loop.

Hello, can I do anything more to make a progress on landing this?

Add a couple of more reviewers.

Adding Sam as one who did some changes in MachineBlockPlacement patch and Chandler as this patch is actually a follow-up of the branch weights patches he reviewed.

Please help to make a progress on this patch.

This is actually a revert-revert of the patch with a fix.

iteratee accepted this revision.Jul 10 2017, 11:35 AM

Looks fine. I would prefer the fallthrough checks be successor checks, but I can accept it either way.

1975 ↗(On Diff #104369)

Can you reverse this test? ExitingBB->isSuccessor(NextBlockInChain)

1976 ↗(On Diff #104369)

Same here.

This revision is now accepted and ready to land.Jul 10 2017, 11:35 AM

Thank you Kyle, will update before commit.

This revision was automatically updated to reflect the committed changes.