Page MenuHomePhabricator

[VPlan] Use incoming VPValue to detect in-loop reductions (NFC).
Needs ReviewPublic

Authored by fhahn on Apr 8 2021, 6:30 AM.

Details

Summary

After adding the incoming value from the backedge to the operands of
VPWidenPHIRecipe (D99294) , we can use that to check for in-loop
reductions.

This reduces the coupling with the cost model by using information
directly in VPlan.

Diff Detail

Event Timeline

fhahn created this revision.Apr 8 2021, 6:30 AM
fhahn requested review of this revision.Apr 8 2021, 6:30 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 8 2021, 6:30 AM
Herald added a subscriber: vkmr. · View Herald Transcript
Ayal added a comment.Apr 27 2021, 6:20 AM

Reducing the coupling with the cost model by using information directly in VPlan is great. Have a few comments.

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

number of operands must be 2, right?

this may be fragile, if some (cast?) vpinstruction is introduced between the VPReductionRecipe and the header phi it feeds? Since in-loop-reduction phi's require special code-gen handling, perhaps their recipes should be marked as such?

4722

ditto

9170–9171

Perhaps RecipeBuilder should allow checking if it has any (in-loop) reduction phi's, and iterate over them?

fhahn updated this revision to Diff 340869.Apr 27 2021, 9:05 AM

Remove unnecessary check on number of operands, add assertion to catch if we miss an in-loop reduction in VPlan.

fhahn added inline comments.Apr 27 2021, 9:09 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
4307

number of operands must be 2, right?

It's not needed here, I removed it.

this may be fragile, if some (cast?) vpinstruction is introduced between the VPReductionRecipe and the header phi it feeds? Since in-loop-reduction phi's require special code-gen handling, perhaps their recipes should be marked as such?

Agreed, but not sure if we need to fix this issue before landing the patch?

I added an assertion in the code below to catch the case where we fail to identify an in-loop reduction in VPlan.

4722

here PhiR could also be a first order recurrence, so for now I think we need to at least make sure it's a reduction.

Ayal added inline comments.Apr 28 2021, 2:29 PM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
4307

wouldn't it be simpler, clearer and more robust if adjustRecipesForInLoopReductions() would turn on an "IsInLoop" bit inside VPWidenPhiRecipe, when converting its associated VPWiden[Select]Recipes into VPReductionRecipes?

fhahn added inline comments.Apr 29 2021, 12:56 PM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
4307

It would be simpler, but I'm not sure if it is worth adding this extra coupling by adding a new InLoopReduction field to the general VPWidenPHIRecipe that needs to be maintained at this point? We could also just traverse the whole cycle if needed I think as in practice it should be only a very small number of steps. WDYT?

Ayal added inline comments.May 3 2021, 12:44 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
4307

Agreed - the overhead of checking the cycle/chain to figure out if the reduction is in-loop or not, should be tolerable. It's about having recipes clearly model the code they represent up-front, during VPlan construction and/or planning, than whether to cache the results of this "isInLoop" query eagerly versus (re)running it lazily on demand during VPlan execution. A phi recipe representing an in-loop reduction is arguably conceptually distinct from a "regular" VPWidenPHIRecipe, with respect to the scalar-versus-vector data each operates on, and the epilogue each feeds. If the "cached result" needs to be updated, so may the cost of the recipe and of dependent recipes. Sounds reasonable?

4722

Agreed; "ditto" referred to asking here too directly if PhiR->isInLoopReduction().

9177

ditto ;-)

9180

This is to avoid redundant creation of the header block in-mask when the loop contains no non-in-loop reductions?
Worth doing in a separate patch?

9188

#ifndef NDEBUG?

perhaps an overkill - would CM.getInLoopReductionChains() eventually be discarded?

fhahn updated this revision to Diff 342975.May 5 2021, 3:00 AM

Thanks for the latest comments!

This is just a rebase, will address comments separately!

fhahn updated this revision to Diff 343169.May 5 2021, 1:37 PM

Add isInLoopReduction helper & use it instead isa<VPReductionRecipe>

fhahn marked 2 inline comments as done.May 5 2021, 1:41 PM
fhahn added inline comments.
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
4307

I went ahead and added a VPWidenPHIRecipe::isInLoopReduction helper.

I'm not 100% sure this is in line with your suggestions, please let me know if I misunderstood and we should add a flag as well to start with :)

9188

Yes I think CM.getInLoopReductionChains is going away at some point. But until then it might be good to try to ensure they do not diverge. But I'd be more than happy to drop it as well, it might just be a bit too paranoid

fhahn updated this revision to Diff 343183.May 5 2021, 1:55 PM
fhahn marked an inline comment as done.

Clang-format.

Ayal added inline comments.May 10 2021, 3:04 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
4307

This API looks good to me, thanks!
Adding a flag to implement it, as argued above, would also be good.
As stated elsewhere, there are actually 3 types of reductions, including two types of in-loop reductions: ordered and unordered.

9177

nit: suffice to check if (!PhiR || PhiR->isInLoopReduction()) - the latter implies PhiR has a recurrence descriptor.

9180

There's a subtle change here: BlockInMask may currently be created redundantly here if there are reductions but no in-loop reductions; this modification eliminates this redundancy.
Probably insignificant, given foldTailByMasking?

9188

I'd vote for cleaner, paranoia free code in this case.

One could verify the integrity of in-loop reduction chains (or VPlan in general?), say before code-gen; i.e., that in-loop header phi recipes are consistent with reduction recipes.

9257

Wouldn't it be better, if in addition to converting widen recipes of in-loop-reduction chains into reduction recipes here, we also convert their header phi upfront:

auto *PhiR = cast<VPWidenPHIRecipe>(RecipeBuilder.getRecipe(Phi));
PhiR->setIsInLoopReduction();

?

(Making sure to record the recipe of Phi)

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

(being 'const' it can't even cache the result for repeated queries...)