This is an archive of the discontinued LLVM Phabricator instance.

[VPlan] Track both incoming values for first-order recurrence phis.

Authored by fhahn on Jun 13 2021, 8:27 AM.



This patch updates VPWidenPHI recipes for first-order recurrences to
also track the incoming value from the back-edge. Similar to D99294,
which did the same for reductions.

Diff Detail

Event Timeline

fhahn created this revision.Jun 13 2021, 8:27 AM
fhahn requested review of this revision.Jun 13 2021, 8:27 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 13 2021, 8:27 AM
Herald added a subscriber: vkmr. · View Herald Transcript
Ayal added inline comments.Jun 15 2021, 11:53 PM

This does raise an eyebrow... rename StartVPV and StartV to something like ReductionStartVPV and ReductionStartV? Only start values of reductions are handled here, those of firstOrderRecurrences are handled in fixFirstOrderRecurrence().

Better yet to first handle firstOrderRecurrences, separately? It's just creating the phi (which will eventually be replaced by the one fixFirstOrderRecurrence() creates) and setting the state, per part.


This StartV for non-reduction phi's is currently not being used, except perhaps as a placeholder to ensure backedge takes 2nd place, right? Should potentially serve fixFirstOrderRecurrence()?


What's left as 'else' here, pointer inductions? Worth a TODO to model their backedges as well?


dyn_cast may return null; use cast<>?


Comments in VPRecipeBuilder.h that PhisToFix handles reduction phi's only should be updated, to include FOR phi's as well:

/// Cross-iteration **reduction** phis for which we need to add the incoming value
/// from the backedge after all recipes have been created.
SmallVector<VPWidenPHIRecipe *, 4> PhisToFix;
/// Add the incoming values from the backedge to **reduction** cross-iteration
/// phis.
void fixHeaderPhis();

Comments in VPlan.h about the backedge of VPWidenPHIRecipe should be updated as well:

/// For **reduction** PHIs, RdxDesc must point to the corresponding recurrence
/// descriptor, the start value is the first operand of the recipe and the
/// incoming value from the backedge is the second operand.
/// Returns the incoming value from the loop backedge, if it is a **reduction**.
VPValue *getBackedgeValue()
fhahn updated this revision to Diff 353212.Jun 19 2021, 2:30 PM

Addressed comments, thanks!

I also updated fixFirstOrderRecurrence to use the VPValues for the start and backedge values.

fhahn marked 3 inline comments as done.Jun 19 2021, 2:32 PM
fhahn added inline comments.

I re-organized the code a bit more. WDYT?


I updated the patch to use both the start and backedge VPValue in fixFirstOrderRecurrence.


Added the todo.

fhahn marked an inline comment as done.Jun 19 2021, 2:32 PM
Ayal added inline comments.Jun 24 2021, 1:47 PM

(Unrelated to this patch, but setting the loop's upper bound in advance to unsigned LastPartForNewPhi = IsOrdered ? 1 : State.UF; seems clearer than breaking inside the loop. Here and below.)


Instead of asking if (RdxDesc) here, move the following block earlier to after FOR(P)'s return; i.e., have the "if (RdxDesc || FOR(P))" fully handle both?

This will also allow to keep the definitions of ScalarPHI and VecTy inside "if (RdxDesc || FOR(P))".


Add a VPWidenPHIRecipe(Phi, *StartV) constructor? (If not split into VPWidenReductionPHIRecipe, VPWidenFORPHIRecipe, VPWidenPointerIVPHIRecipe.)

fhahn updated this revision to Diff 354668.Jun 26 2021, 5:25 AM

Address latest comments, thanks!

fhahn added inline comments.Jun 26 2021, 5:27 AM

Done in 7f369819774d


Sounds good, I moved the code up.


I added the new constructor. I'm planning to split them up as discussed at the other phi related patches as follow ups.

fhahn updated this revision to Diff 354669.Jun 26 2021, 5:29 AM

Use LastPartForNewPhi in second loop as well.

Ayal accepted this revision.Jun 27 2021, 12:39 AM

This looks good to me, thanks!
Adding a couple of final nits.


Better place this definition of Phi after the following comment, right before it is needed for defining Start?


Better keep this definition of IsOrdered inside the if (RdxDesc || Legal->isFirstOrderRecurrence(P)) { below, right before it is used to define LastPartForNewPhi?

This revision is now accepted and ready to land.Jun 27 2021, 12:39 AM
This revision was automatically updated to reflect the committed changes.
fhahn marked an inline comment as done.
fhahn added a comment.Jun 27 2021, 6:33 AM

Thanks Ayal! I included your suggestions in the committed version.