Page MenuHomePhabricator

[SimpleLoopUnswitch] Create SimpleLoopNestUnswitch pass
Needs ReviewPublic

Authored by uint256_t on Aug 15 2021, 8:49 AM.



This patch adds a new LoopNest pass called SimpleLoopNestUnswitch. This pass is similar to SimpleLoopUnswitch, but only unswitches branches out of a whole loop nest. In other words, this pass doesn't make branches in-between loops. This helps create/maintain a perfect loop nest.
See also for another example of creating a new LoopNest pass of existing passes.

Diff Detail

Event Timeline

uint256_t created this revision.Aug 15 2021, 8:49 AM
uint256_t requested review of this revision.Aug 15 2021, 8:49 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 15 2021, 8:49 AM

This patch is not ready for review. I'll update the diff soon.

uint256_t updated this revision to Diff 367756.Aug 20 2021, 4:05 AM
uint256_t edited the summary of this revision. (Show Details)

Ready for review

uint256_t set the repository for this revision to rG LLVM Github Monorepo.Aug 20 2021, 4:09 AM
uint256_t edited the summary of this revision. (Show Details)Aug 20 2021, 4:22 AM
uint256_t updated this revision to Diff 367958.Aug 21 2021, 8:15 AM

Small change

uint256_t updated this revision to Diff 367961.Aug 21 2021, 9:13 AM

Follow clang-tidy

If possible, can you let us know what kinds of improvement this patch achieve please? like performance, code size, compile time and etc.

If we remove conditional branch inside loop, it could help loop vectorization. I am not sure the improvement from the perfect loop nest is better than that...

Maybe, other people could give you more good comments.

uint256_t added a comment.EditedAug 23 2021, 1:50 AM

For example, we may have an opportunity to perform loop-interchange (or some other transformations that require a perfect loop nest) after performing simple-loop-nest-unswitch.
We can perform simple-loop-unswitch after that, so there should be no problem for loop vectorization.
What order we put passes including simple-loop-nest-unswitch in a pass pipeline is still a problem though...

Whitney added inline comments.Aug 24 2021, 11:21 AM

When given BestUnswitchTIForLoopNest, why do we want to findBestUnswitchTI?

When given BestUnswitchTIForLoopNest, this code only unswitch if BestUnswitchTIForLoopNest == findBestUnswitchTI. Is it possible that BestUnswitchTIForLoopNest != findBestUnswitchTI only have some loop level?

uint256_t marked 2 inline comments as done.Aug 24 2021, 8:06 PM
uint256_t added inline comments.

We want to findBestUnswitchTI to obtain PartialIVInfo, ExitBlocks, and BestUnswitchInvariants. However it seems we can remove some code.
I'll change the code soon.

uint256_t updated this revision to Diff 368543.EditedAug 24 2021, 8:17 PM
  • No longer do findBestUnswitchTI every time we call unswitchBestCondition given BestUnswitchTIForLoopNest.
  • Remove the condition BestUnswitchTIForLoopNest == findBestUnswitchTI, which was confusing.