This is an archive of the discontinued LLVM Phabricator instance.

[VPlan] Representing backedge def-use feeding reduction phis.
ClosedPublic

Authored by fhahn on Mar 24 2021, 12:53 PM.

Details

Summary

This patch updates the code handling reduction recipes to also keep
track of the incoming value from the latch in the recipe. This is needed
to model the def-use chains completely in VPlan, so that it is possible
to replace the incoming value with an arbitrary VPValue.

Diff Detail

Event Timeline

fhahn created this revision.Mar 24 2021, 12:53 PM
fhahn requested review of this revision.Mar 24 2021, 12:53 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 24 2021, 12:53 PM
Herald added a subscriber: vkmr. · View Herald Transcript
fhahn updated this revision to Diff 335473.Apr 6 2021, 4:14 AM

Rebase & ping.

I just pushed a small patch that prints prints VPWidenPHIRecipe using the VPValue operands, if there are operands for all incoming values (a6b06b785cda1bb94dd05f29d66892ccb44cf0cd).

Now the change in this patch (adding the incoming value from the loop backedge) is visible in the printing.

fhahn updated this revision to Diff 336113.Apr 8 2021, 8:09 AM

Rebased. I also put up 2 additional patches that make use of the operand for the incoming value of the backedge in more places: D100102 & D100113.

fhahn updated this revision to Diff 338872.Apr 20 2021, 7:49 AM

Update comment to clarify that the first operand of a VPWidenPHIRecipe for a reduction is the start value and the second operand is the incoming value from the backedge.

Ayal added a comment.Apr 26 2021, 2:16 PM

Looks good to me!
Adding a couple of nits and thoughts.
Perhaps "[VPlan] Representing backedge def-use feeding reduction phi's" may be a more accurate title - "incoming" also (more-so?) applies to the operand from the preheader.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
4323–4328

nit: worth hoisting LoopVectorLatch = LI->getLoopFor(LoopVectorBody)->getLoopLatch() here.
(admittedly independent of this patch)

4329–4330

nit: can continue to obtain the first-and-only VPValue defined by PhiR, by calling getVPValue() as before, which defaults to getVPValue(0), right?

8970

Worth a comment here explaining that source and destination of cross-iteration dependences are marked here in order to wire their recipes in VPlan later.

Current implementation looks fine. Raising a possible alternative, if preferred?
The wiring of header phi's could be delegated to RecipeBuilder: have it collect the 'partially constructed' widenPhiRecipes of reductions as it creates them, into a local "PhiRecipesToFix", along with recording the recipes of their latched-operands (only). Then have RecipeBuilder::fixHeaderPhi's() to complete the construction of its PhiRecipesToFix, via their underlying Phi's.

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

Worth supplying another interface to retrieve 'preheadered' and 'latched' operands of a header phi recipe (by setting them as 0 and 1 enum values?) to increase the readability of 'getOperand(0)' and 'getOperand(1)'?

llvm/test/Transforms/LoopVectorize/vplan-printing.ll
82

Clean up the TODO in VPlan.cpp/ VPWidenPHIRecipe::print() ?

fhahn retitled this revision from [LV] Track incoming values for reductions in recipe (NFC). to [VPlan] Representing backedge def-use feeding reduction phis..Apr 27 2021, 2:31 AM
fhahn updated this revision to Diff 340770.Apr 27 2021, 3:01 AM

Updated title, move logic to track phis-to-fix and fixup to VPRecipeBuilder.

fhahn updated this revision to Diff 340772.Apr 27 2021, 3:09 AM

Add & use VPWidenRecipe::getBackedgeValue.

fhahn marked an inline comment as done.Apr 27 2021, 3:11 AM
fhahn added inline comments.
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
4323–4328

I'll do that in a separate commit.

4329–4330

Yep, changed it back.

8970

Thanks for the suggestion. Doing the tracking and fixup directly in VPRecipeBuilder seems preferable. I updated the patch and added the additional comments to the new code.

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

I added a VPWidenPHIRecipe::getBackedgeValue(), similar to getStartValue. WDYT?

llvm/test/Transforms/LoopVectorize/vplan-printing.ll
82

Unfortunately there are still cases where we do not track the value from the back-edge (like first-order recurrences).

fhahn marked an inline comment as done.Apr 27 2021, 5:25 AM
fhahn added inline comments.Apr 27 2021, 5:51 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
4323–4328

Done in cb96d802d4d7

Ayal added inline comments.Apr 27 2021, 9:43 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8771

can alternatively traverse over R : PhiRecipesToFix, and use R's underlying ingredient to retrieve its PN, etc.

8886

Instead of recording the recipe of Phi, which the next line creates, can do

auto *PhiRecipe = new VPWidenPHIRecipe(Phi, RdxDesc, *StartV);
PhiRecipesToFix.push_back(PhiRecipe);
return toVPRecipeResult(PhiRecipe);
llvm/lib/Transforms/Vectorize/VPlan.h
997

Great!

llvm/test/Transforms/LoopVectorize/vplan-printing.ll
82

Ah, right.

fhahn updated this revision to Diff 340892.Apr 27 2021, 10:01 AM

Track VPWidenPhiRecipes directly in PhisToFix.

fhahn marked an inline comment as done.Apr 27 2021, 10:01 AM
fhahn added inline comments.
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8771

excellent idea, updated!

Ayal accepted this revision.Apr 27 2021, 1:28 PM

Adding a couple of related thoughts. Thanks!

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

while we're here: it may be useful to have a "getVPSingleValue()" which would take care of the assert (and the redundant 0)? In any case, the assert deserves an error message.

8889

while we're here: the use of toVPRecipeResult() and VPRecipeOrVPValueTy, if intended to solve D44800 Blend issue only, seem like an overkill - BlendRecipe pass-throughs a single-operand phi, having a full (null) mask; so it should be easy(ier) to have it pass-through an(y) operand also for a phi having multiple identical operands. I.e., tryToBlend() can always return a VPRecipe. Better to discuss this on a related review, if there is one available?

This revision is now accepted and ready to land.Apr 27 2021, 1:28 PM
fhahn added a comment.Apr 27 2021, 3:03 PM

Adding a couple of related thoughts. Thanks!

Thanks! This also depends on D99293, but I think I'll re-order the patches a bit tomorrow so we can use phis() from D100101 from the start.

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

Yes that sounds good. I'll push that as a separate commit before landing this change.

8889

Sure, let me take another look. Conceptually I think having a way to return a simplified value is convenient and cleaner, but it might be overkill for now.

fhahn added inline comments.Apr 29 2021, 5:42 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8775

Added getVPSingleValue in a0e1313c2329

fhahn updated this revision to Diff 341485.Apr 29 2021, 5:42 AM

update to use getVPSingleValue

fhahn updated this revision to Diff 342747.May 4 2021, 8:15 AM

rebased ahead of committing

This revision was landed with ongoing or failed builds.May 4 2021, 8:33 AM
This revision was automatically updated to reflect the committed changes.
Ayal added inline comments.May 4 2021, 9:23 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8882

nit: "// Record the [PHI and the] incoming value"

fhahn added inline comments.May 7 2021, 1:39 PM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8882

Thanks, should be fixed in 75b9997760c6

Hi,

I wrote a PR about a LV-crash that started happening with this patch:
https://bugs.llvm.org/show_bug.cgi?id=50298

fhahn added a comment.May 11 2021, 6:35 AM

Hi,

I wrote a PR about a LV-crash that started happening with this patch:
https://bugs.llvm.org/show_bug.cgi?id=50298

Thanks for the report! The problem was that we did not record the recipe if a simplified VPValue is used. I pushed faebc6bf108e to fix it for now, but as Ayal pointed out, it might be worth the simplify the handling, which I'll look into separately.