This is an archive of the discontinued LLVM Phabricator instance.

[VPlan] Add VPReductionPHIRecipe (NFC).
ClosedPublic

Authored by fhahn on Jun 27 2021, 3:08 AM.

Details

Summary

This patch is a first step towards splitting up VPWidenPHIRecipe into
separate recipes for the 3 distinct cases they model:

  1. reduction phis,
  2. first-order recurrence phis,
  3. pointer induction phis.

This allows untangling the code generation and allows us to reduce the
reliance on LoopVectorizationCostModel during VPlan code generation.

Discussed/suggested in D100102, D100113, D104197.

Diff Detail

Event Timeline

fhahn created this revision.Jun 27 2021, 3:08 AM
fhahn requested review of this revision.Jun 27 2021, 3:08 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 27 2021, 3:08 AM
Herald added a subscriber: vkmr. · View Herald Transcript
Ayal added inline comments.Jun 28 2021, 9:09 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
4132–4133

use dyn_cast instead of isa&cast?

4328–4329

bool IsInLoopReductionPhi = PhiR->isInLoop()?

4342–4343

(unrelated to this patch, but:

  • isOrdered() implies isInLoop()
  • IsOrdered here should be IsOrderedAndVectorized
  • another place worth defining LastPartForVecRdxPhi
  • wonder what happens when isOrdered()&NotVectorized wires UF parts(?)

)

4746–4747

Drop Cost->isInLoopReduction, this now deals w/ FOR only

(wonder if FOR works well for VF=1, e.g., w/o sinkAfter(?))

4756–4757

Drop isFOR, we now know it is

4761

"above" >> "elsewhere"

8042

Are both PrevBB and VectorPreHeader needed?

llvm/lib/Transforms/Vectorize/VPlan.cpp
1139

IsOrdered applies to VF=1 as well, right? Rename variable to IsOrderedAndVectorized?

llvm/lib/Transforms/Vectorize/VPlan.h
308–315

Comment?

739–740

Introduce a base class common to all phi recipes to ask isa<> instead of isPhi?

Check range of SC's (from FirstPHI to LastPHI) instead of multiple ||'s, or make sure they compile down to a range check?

1062

VPWidenPHIRecipe(VPVID, VPDefID, Phi) constructor should be 'protected'? Else drop 'protected'.

1132

Implies reduction is also in-loop.

1147–1173

Add bool isInLoop()?

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp
279

&& !isa<VPReductionPHIRecipe>(UI) ?

llvm/lib/Transforms/Vectorize/VPlanValue.h
100

keep lexical order?
or keep all Phi's together?

329

ditto

kmclaughlin added inline comments.Jun 28 2021, 10:00 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
4343

Hi @fhahn, I recently created D104533 to fix ordered reductions where the VF = 1. After this change, the State.VF.isVector() check here (and in VPReductionPHIRecipe::execute) is no longer required.

fhahn updated this revision to Diff 355287.Jun 29 2021, 10:22 AM
fhahn marked 14 inline comments as done.

Address comments, thanks!

fhahn added inline comments.Jun 29 2021, 10:25 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
4132–4133

Done, thanks!

4328–4329

I updated the code to just use PhiR->isInLoop.

4342–4343

isOrdered() implies isInLoop()

Now only isOrdered is check. The VPReductionPHIRecipe constructor ensures IsInLoop is set whenever IsOrdered is true.

IsOrdered here should be IsOrderedAndVectorized

Removed the variable, use isOrdered instead.

another place worth defining LastPartForVecRdxPhi

Done!

wonder what happens when isOrdered()&NotVectorized wires UF parts(?)

After recent changes, there's no need to check for isVector.

4343

Thanks, removed!

8042

Not really, we can use LoopInfo to get the pre-header block. Updated the code.

llvm/lib/Transforms/Vectorize/VPlan.cpp
1139

No need to check for isVector, as @kmclaughlin mentioned. I just replaced the variable with isOrdered() checks.

llvm/lib/Transforms/Vectorize/VPlan.h
308–315

The member is now gone again.

739–740

Introduce a base class common to all phi recipes to ask isa<> instead of isPhi?

Sounds like a good idea. I think it would be best to split up the existing WidenPHIRecipe first, to avoid moving too much at the same time.

Check range of SC's (from FirstPHI to LastPHI) instead of multiple ||'s, or make sure they compile down to a range check?

Done, added First/Last values to the enum.

1062

Moved, thanks!

1132

Added that IsOrdered also requires IsInLoop.

1147–1173

Done, also added doc-comments.

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp
279

Yes, updated! But I don't think it is possible to create a test case that shows the issue, because it would require a non-widenable reduction instruction I think.

llvm/lib/Transforms/Vectorize/VPlanValue.h
100

I moved them together, so the range check is more efficient. Also added VPFirstPHISC/VPLastPHISC to facilitate the range check.

Ayal added inline comments.Jul 1 2021, 1:17 PM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
505–506

Above comment deserves an update?

4132–4133

dyn_cast<VPReductionPHIRecipe>(PhiR) or directly dyn_cast<VPReductionPHIRecipe>(&R), instead of going from PhiR to its VPValue base class and back via getDef()?

8042

Are both PrevBB and VectorPreHeader needed?

Ahh, it indeed seems more logical to set State.CFG.VectorPreHeader = ILV.createVectorizedLoopSkeleton(); here; and then have VPlan::execute() retrieve this VectorPreHeader and set/reset State.CFG.PrevBB, LastBB during code-gen of the vector loop's basic blocks.

But this issue of having to record the preheader in an additional State field, or look for it via LoopInfo, raises a more general thought regarding VPlan generating preheader code, noted below.

llvm/lib/Transforms/Vectorize/VPlan.cpp
1166

Code that VPlan is to generate inside the vector preheader, should ideally (/arguably?) be represented by recipes that reside inside a VPBasicBlock which represents this preheader, thereby properly extending the scope of VPlan; rather than redirecting Builder's insertion point. Sounds reasonable, perhaps as a follow-up?

fhahn updated this revision to Diff 356512.Jul 5 2021, 8:22 AM
fhahn marked an inline comment as done.

Addressed latest comments, thanks!

fhahn marked an inline comment as done.Jul 5 2021, 8:24 AM
fhahn added inline comments.
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
505–506

Yes, I updated it in the latest version. Should only generate code for first-order recurrence phis and pointer inductions.

4132–4133

Done! Needed to add a classof implementation for VPWidenPHIRecipe to VPReductionPHIRecipe, to resolve multiple available overloads.

8042

Ok, I went back to having a separate field for the vector preheader. I kept the code to set both VectorPreHeader and PrevBB to the block returned by createVectorizedLoopSkeleton.

llvm/lib/Transforms/Vectorize/VPlan.cpp
1166

Sounds reasonable, perhaps as a follow-up?

+1, I'll look into modeling & generating the code in the pre-header as a follow-up patch.

Ayal accepted this revision.Jul 5 2021, 1:25 PM

Looks good to me, adding a few minor optional last comments.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8042

On second thought, considering that State.CFG.VectorPreHeader may be temporary, it may be simpler to set it locally (and temporarily) inside VPlan::execute() as mentioned below.

llvm/lib/Transforms/Vectorize/VPlan.cpp
765

Another option, to keep this change local, is to keep
BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
and set here
State->CFG.VectorPreHeader = VectorPreHeaderBB;

1124

This TODO and associated if block below can be removed for VPReductionPHIRecipe?

1149

L used only in assert?

llvm/lib/Transforms/Vectorize/VPlan.h
1054

Mention that VPWidenPHIRecipe also serves as a base class for reduction phis?

This revision is now accepted and ready to land.Jul 5 2021, 1:25 PM
fhahn marked 4 inline comments as done.Jul 6 2021, 3:25 AM

Thanks Ayal, I addressed the remaining comments in the committed version.

This revision was automatically updated to reflect the committed changes.