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

Authored by skatkov on Jun 15 2017, 11:02 PM.

Details

Summary

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

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

Diff Detail

Repository
rL LLVM
skatkov created this revision.Jun 15 2017, 11:02 PM
iteratee added inline comments.Jun 19 2017, 1:52 PM
lib/CodeGen/MachineBlockPlacement.cpp
1941 ↗(On Diff #102787)

How is your test different from the test above?

skatkov added inline comments.Jun 19 2017, 8:30 PM
lib/CodeGen/MachineBlockPlacement.cpp
1941 ↗(On Diff #102787)

The test above checks whether Bottom block has a fallthrough out of the loop. If it has than there is no reason to make a loop rotation due to it will introduce a branch to that out of loop basic block.

My check is described in the summary. It checks the creation of extra branch inside a loop in case of loop rotation. Simply if Exit Candidate has a fallthrough BB and Bottom does not fallthrough (potentially) to Top then rotation will not create a fallthrough from Bottom to Top but will create a branch from Exit Candidate to next block in a chain (which will become the first block in a chain).

Dear Reviewers, Can I do anything to make a progress on this?

iteratee added inline comments.Jun 22 2017, 11:26 AM
lib/CodeGen/MachineBlockPlacement.cpp
1952 ↗(On Diff #102787)

Can you re-write this comment, I can't make heads or tails of what you're trying to do.

Something like:
Rotating a loop exit to the bottom when there is a fallthrough to top trades the entry fallthrough for an exit fallthrough.
If there is no bottom->top edge, but the chosen exit block does have a fallthrough, We break that fallthrough for nothing in return.

You don't have to use that language, but embedding your example may help as well. Include the Pre and Post blocks in the sequences, it makes it more obvious what's going on, and don't assume that the the header is the chosen exit block.

skatkov updated this revision to Diff 103686.Jun 22 2017, 8:28 PM

Hi Kyle, please take a look, whether it is better wording?

iteratee accepted this revision.Jun 23 2017, 11:39 AM

Approved with the changes I've marked.

lib/CodeGen/MachineBlockPlacement.cpp
1957 ↗(On Diff #103686)

*broken now*

1963 ↗(On Diff #103686)

This is really good. Thank you.
Could you add one more sentence, that we know there is no exit fallthrough from Bn because of the check above?

1972 ↗(On Diff #103686)

"Rotating loop to put exit " ... " at bottom.\n"

This revision is now accepted and ready to land.Jun 23 2017, 11:39 AM

The commit has been reverted as it causes sanitizer build bot crash. Will investigate.

This revision was automatically updated to reflect the committed changes.