Page MenuHomePhabricator

[LoopNest] False negative of `arePerfectlyNested` with LCSSA loops
ClosedPublic

Authored by TaWeiTu on Aug 18 2020, 4:24 AM.

Details

Summary

The LCSSA pass (required for all loop passes) sometimes adds additional blocks containing LCSSA variables, and checkLoopsStructure may return false even when the loops are perfectly nested in this case.
This is because the successor of the exit block of the inner loop now points to the LCSSA block instead of the latch block of the outer loop.
Examples are shown in the test nests-with-lcssa.ll.

To fix the issue, the successor of the exit block of the inner loop can now point to a block in which all instructions are LCSSA phi node (except the terminator), and the sole successor of that block should point to the latch block of the outer loop.

Diff Detail

Event Timeline

TaWeiTu created this revision.Aug 18 2020, 4:24 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 18 2020, 4:24 AM
TaWeiTu requested review of this revision.Aug 18 2020, 4:24 AM
TaWeiTu retitled this revision from [LoopNest] False negative of `when LCSSA pass to [LoopNest] False negative of `arePerfectlyNested` with LCSSA.
TaWeiTu added a reviewer: Whitney.
TaWeiTu retitled this revision from [LoopNest] False negative of `arePerfectlyNested` with LCSSA to [LoopNest] False negative of `arePerfectlyNested` with LCSSA loops.

arePerfectlyNested is written very conservative to start with, this patch allows loop nests with PHINodes in between to be considered perfect.

llvm/lib/Analysis/LoopNestAnalysis.cpp
232

How about taking a reference, so no need to check for nullptr.

239

Don't think checking name is ideal, because it can be changed in between passes.
How about PHINodes that have single incoming entry?

296–298

Use const BasicBlock *

llvm/test/Analysis/LoopNestAnalysis/nests-with-lcssa.ll
2

can the LLVMIR in this LIT be already after loop-rotate, so it doesn't need to reply on loop rotate.

12

Function Attrs are not needed, so can all be removed.

14

please rename the loop header name after rotation, so they can be easily identify.
e.g. for.i for the loop header of loop i.

TaWeiTu updated this revision to Diff 286273.Aug 18 2020, 6:50 AM

Fix LCSSA block checking. Rename loops in the test file.

TaWeiTu marked 4 inline comments as done.Aug 18 2020, 6:52 AM
TaWeiTu added inline comments.
llvm/lib/Analysis/LoopNestAnalysis.cpp
239

The LCSSA PHINodes may have two incoming entries, one from the exit block of the inner loop and the other from the header of the outer loop.
I'm not entirely sure about whether the condition is correct and sufficient, though.

TaWeiTu marked an inline comment as done.Aug 18 2020, 6:53 AM
Whitney added inline comments.Aug 18 2020, 8:22 AM
llvm/lib/Analysis/LoopNestAnalysis.cpp
239

The LCSSA PHINodes may have two incoming entries, one from the exit block of the inner loop and the other from the header of the outer loop.

I guess you mean from the exiting block of the inner loop? I thought LCSSA blocks are the exit blocks.
https://llvm.org/docs/LoopTerminology.html#loop-closed-ssa-lcssa
they can just iterate over all the (loop closing) PHI nodes in the exit blocks

I see what you mean by looking at the LIT test, in function f, %split is actually the LCSSA phi, not %res.1.lcssa. %res.1.lcssa is just a generic PHINode.

TaWeiTu added inline comments.Aug 18 2020, 8:48 AM
llvm/lib/Analysis/LoopNestAnalysis.cpp
239

Oh I see. Thanks for clarifying!
Should I update the name of IsLCSSABlock to something else?

Whitney added inline comments.Aug 18 2020, 12:07 PM
llvm/lib/Analysis/LoopNestAnalysis.cpp
239

Right, need to be renamed as it is not a LCSSA block (i.e. loop exit block).
Thinking of what we are trying to allow for perfect nest in this patch....
one extra block (optional) between inner exit block and outer latch block, which only contains PHINodes.

That extra basic block is needed because the inner loop is guarded and there exists LCSSA PHINodes in the inner loop exit block.

Can we add this logic in?

TaWeiTu updated this revision to Diff 286462.Aug 18 2020, 7:58 PM

Check the existence of the extra block only when the inner loop is guarded and the inner loop exit contains LCSSA Phi instructions.

TaWeiTu marked an inline comment as done.Aug 18 2020, 7:58 PM
Whitney accepted this revision.Aug 19 2020, 7:05 AM
Whitney added inline comments.
llvm/lib/Analysis/LoopNestAnalysis.cpp
232

Rename B to ExitBlock.

This revision is now accepted and ready to land.Aug 19 2020, 7:05 AM
fhahn added a subscriber: fhahn.Aug 19 2020, 7:18 AM
fhahn added inline comments.
llvm/lib/Analysis/LoopNestAnalysis.cpp
233

You only need to check phi nodes. There's B.phis(). Also, usually it is more common to use BB for BasicBlock variables.

239

It might be helpful to add a comment here to specify what 'extra phi block' means.

Also, If you just need to look at PHI nodes, I think you can use B.phis().

TaWeiTu updated this revision to Diff 286564.Aug 19 2020, 8:12 AM

Rename variables. Use BasicBlock::phis(). Explain what "extra Phi block" means in the comment.

TaWeiTu marked 3 inline comments as done.Aug 19 2020, 8:18 AM

Hi @Whitney, @fhahn, thanks for your review and comment!
Please let me know if there's any other problem with the patch.
Also, if the patch is ready to land, is it possible for you to commit it instead (I believe I don't have the commit access)?

Hi @Whitney, @fhahn, thanks for your review and comment!
Please let me know if there's any other problem with the patch.
Also, if the patch is ready to land, is it possible for you to commit it instead (I believe I don't have the commit access)?

One minor comment, then LGTM. Let's see what Florian thinks.

Instruction to obtain commit access:
https://llvm.org/docs/DeveloperPolicy.html#obtaining-commit-access

Prior to obtaining commit access, it is common practice to request that someone with commit access commits on your behalf. When doing so, please provide the name and email address you would like to use in the Author property of the commit.

--author="Ta-Wei Tu <tu.da.wei@gmail.com>" Good?

llvm/lib/Analysis/LoopNestAnalysis.cpp
245

Usually blocks of PHINodes are named IncomingBlock

TaWeiTu updated this revision to Diff 286701.Aug 19 2020, 7:17 PM

Source -> IncomingBlock

TaWeiTu marked an inline comment as done.Aug 19 2020, 7:19 PM

--author="Ta-Wei Tu <tu.da.wei@gmail.com>" Good?

Sure, thank you very much!

fhahn added a comment.Aug 20 2020, 1:17 AM

Hi @Whitney, @fhahn, thanks for your review and comment!
Please let me know if there's any other problem with the patch.
Also, if the patch is ready to land, is it possible for you to commit it instead (I believe I don't have the commit access)?

One minor comment, then LGTM. Let's see what Florian thinks.

Looks like my comments have been addressed thanks!

llvm/lib/Analysis/LoopNestAnalysis.cpp
233

This only uses PN in the closure, right? So no need to use [&].

TaWeiTu updated this revision to Diff 286739.Aug 20 2020, 1:40 AM

Replace unnecessary [&] with [].

TaWeiTu marked an inline comment as done.Aug 20 2020, 1:40 AM
etiotto accepted this revision.Aug 21 2020, 9:44 AM

Hi @etiotto, @Whitney thanks for your reviews!
Can you commit this for me? --author="Ta-Wei Tu <tu.da.wei@gmail.com>" as mentioned above looks good to me, thanks!

Hi @etiotto, @Whitney thanks for your reviews!
Can you commit this for me? --author="Ta-Wei Tu <tu.da.wei@gmail.com>" as mentioned above looks good to me, thanks!

Sure. I am swamped with other work, finally have time to get to it today.

Hi @etiotto, @Whitney thanks for your reviews!
Can you commit this for me? --author="Ta-Wei Tu <tu.da.wei@gmail.com>" as mentioned above looks good to me, thanks!

Sure. I am swamped with other work, finally have time to get to it today.

Thanks!