Page MenuHomePhabricator

[VPlan] Introduce recipe to build scalar steps.
ClosedPublic

Authored by fhahn on Dec 17 2021, 10:26 AM.

Details

Summary

This patch adds a new VPScalarIVStepsRecipe to handle building scalar
steps.

In the first patch, it only handles the case where there is no vector
induction variable needed.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes

rebase on top of D116123

fhahn updated this revision to Diff 396234.Dec 26 2021, 12:05 PM

rebased after moving SCEV expansion to extra recipe D116288

Ayal added inline comments.Dec 27 2021, 7:41 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
562

OldInduction moved from protected to public (in some version?) - suffice to provide a const public method to retrieve OldInduction?

2773

Can be folded with above call to createVectorIntOrFpInductionPHI(), followed by

if (NeedsScalarIV) {
  Value *ScalarIV = CreateScalarIV(Step);
  buildScalarSteps(ScalarIV, Step, EntryVal, ID, Def, State);
}

?

7930

OldInduction already set at State construction above?

Also feed Vector/TripCounts to State constructor (indep. of this patch)?

8426

Update comment above, as block in mask may no longer be the first non-phi instruction in the block?
This suggests that VPScalarIVStepsRecipes should perhaps be introduced (as first non-phi insns) by a VPlan-to-VPlan transformation after an initial VPlan is formed with ICmpULE/ActiveLaneMask (as initial first non-phi insns) and other 'initial' recipes.

8934

early-exit if !OnlyScalarStepsNeeded()

8943

Pass StepSCEV instead of II->getSteps()?

This VPExpandSCEVRecipe needs to be placed somewhere by every caller of tryToBuildScalarSteps.

8948

Place ScalarStepsForI as last parameter? Can always pass it and have the constructor check if it's equal to Phi or else should be considered a Trunc.

9115

VectorIVs and ScalarIVs seem useless?

9116

MoveAfterPhis and InductionsToMove suggest that buildVPlanWithVPRecipes() is trying to do too much too early.
Both represent recipes that could not be accurately placed when constructed, and are later (re)positioned between last phi and first non-phi: InductionsToMove are trunc-folded-phi's that must first be placed at the position of the trunc before moving to appear among phi's, and MoveAfterPhis are VPExpandSCEVRecipes (that complement VPScalarIVStepsRecipes) which have yet to be placed - after all phi's but before other non-phi's (right? Some documentation would be helpful.)

Could buildVPlanWithVPRecipes() be simplified by having

  • a Trunc(-that-can-be-folded-into-phi) recipe placed according to the Trunc, with a VPlan2VPlan transformation that traverses such Truncs and replaces them with a Phi recipe
  • a Phi(-that-can-be-converted-into-scalar-steps) recipe placed according to the Phi, with a VPlan2VPlan transformation that traverses such Phis and places them with pairs of VPScalarIVStepsRecipes and VPExpandSCEVRecipes
  • similar to WidenMemory recipes placed according to Load/Stores, later replaced by InterleaveGroup recipes
9145

Rather than pass Instr twice, pass it once as the "Phi" and null as the potential Trunc?

9151

This attempt to build a VPScalarIVStepsRecipe given a Phi Instr should be placed inside tryToCreateWidenRecipe() along with its general handling of a Phi Instrs, rather be treated here. The fact that tryToBuildScalarSteps() generates two recipes, returning one (VPScalarIVStepsRecipes) which uses the other (VPExpandSCEVRecipe), where only a single recipe is traditionally created and returned per each Instr, can be dealt with later. In any case the actual placement of both VPScalarIVStepsRecipe
and VPExpandSCEVRecipe takes place later.

Having both "Steps" and "StepR" may be confusing.

9174

Why is this setRecipe moved?

9190

(This records both VPExpandSCEVRecipe and its VPScalarIVStepsRecipe created by tryToCreateWidenRecipe() for Trunc Instr., to be placed later.)

9815

Store per-part 0?

9817

ditto

10246

Update comment

llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h
174

Document?

176

First parameter is always a Phi; second can be a potentially null Trunc, rather than Trunc-if-exists-otherwise-Phi?

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

assert Parent is null, as in the above insertBefore(InsertPos)?
Place next to insertBefore(InsertPos) above, so that both moveAfter and moveBefore appear next to each other?
There are in general 8 combinations: [ move | insert ][ After | Before ][ Recipe | {VPBB, I} ]

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

(Here the insertBefores appear next to each other.)

1095

"their [vector and] scalar values"?

1108

Suffice to have a single constructor possibly with Trunc as its last optional parameter defaulted to null. Only distinction is the underlying value of VPValue which is set to (Trunc ? Trunc : IV).
Separate pointer to Trunc is redundant, can instead check if the underlying value is a Trunc.

1119

"[vectorized and]"

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

Lex order

fhahn updated this revision to Diff 408248.Feb 13 2022, 3:31 AM
fhahn marked 18 inline comments as done.

Completely restructured the patch to introduce VPScalarIVStepsRecipe in VPlan2VPlan transformation, similiar to how VPWidenCanonicalIV is handled.

The code should be much simpler now. I also tried to address the existing comments, if they still applied to the updated patch.

Ayal added inline comments.Feb 20 2022, 2:13 PM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
2767

By dropping "if (Def->needsVectorIV())" we create a vector IV even if one is (known at this point to) not be needed - all users want scalar values. This case will be cleaned up later, right?

8537

Is this change still needed or can tryToOptimizeInductionTruncate() continue to return VPWidenIntOrFpInductionRecipe?

9814

This is to run once, i.e., not per part/lane inside a replicating region - assert(!State.Instance && "..."); as above.

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

Add accessors instead of getOperand(0/1/2)?

Comment that this checks if start value is zero, aka the start of the canonical IV.

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

Deserves a separate/additional comment?

1340

\p CanonicalIV produces a canonical scalar value per part, this recipe complements it by producing the possibly skewed scalar values per lane.

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp
387 ↗(On Diff #408248)

Have both early-exits here doing if (!IV || IV->needsVectorIV()) continue; ?

410 ↗(On Diff #408248)

nit: pass IV->getPHINode() and IV->getTruncInst() instead of PhiI and TruncI? This is essentially transforming the VPWidenIntOrFpInductionRecipe IV into a VPScalarIVStepsRecipe, along with a specific Step.

415 ↗(On Diff #408248)

TODO: Step should be placed in preheader?

llvm/lib/Transforms/Vectorize/VPlanTransforms.h
59 ↗(On Diff #408248)

If all users of vector IV need scalar values, provide them by building scalar steps off of the canonical scalar IV, and remove the vector IV.

fhahn updated this revision to Diff 410291.Feb 21 2022, 6:20 AM
fhahn marked 11 inline comments as done.

Address latest comments, thanks!

fhahn added inline comments.Feb 21 2022, 6:22 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
562

OldInduction is not needed in the latest version.

2767

Updated the comment, thanks!

2773

Folded, thanks!

7930

removed in the latest version

8426

Removed in the latest version

8537

It's a leftover from earlier iterations, it is not needed. I removed it, thanks!

8934

The whole function is gone now.

8943

The whole function is gone now.

8948

The whole function is gone now.

9115

Those changes are gone now.

9116

Those changes are gone now.

9145

Those changes are gone now.

9151

Those changes are gone now.

9174

changes gone in latest iteration

9190

changes gone in latest iteration

9814

Added assert, thanks!

llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h
176

This is gone in the latest version.

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

Done!

1239

Added accessors and comment, thanks.

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

Removed, thanks!

1108

Simplified, thanks!

1119

Removed, thanks!

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp
387 ↗(On Diff #408248)

Moved, thanks!

410 ↗(On Diff #408248)

Done, thanks!

415 ↗(On Diff #408248)

Added the TODO, thanks!

llvm/lib/Transforms/Vectorize/VPlanTransforms.h
59 ↗(On Diff #408248)

Much better description, updated!

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

Moved, thanks!

simoll added a subscriber: simoll.Feb 21 2022, 6:34 AM
Ayal accepted this revision.Feb 22 2022, 1:45 AM

Looks good to me, thanks!

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

leave this w/o change?

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

Above comment refers to specified recipe (\p InsertPos); refer also to the \p BB and \p I interface?

1339

Define VPScalarIVStepsRecipe later to save this forward declaration of VPCanonicalIVPHIRecipe? Would also facilitate inlining of getCanonicalIV().

This revision is now accepted and ready to land.Feb 22 2022, 1:45 AM
fhahn updated this revision to Diff 411626.Feb 26 2022, 10:30 AM
fhahn marked an inline comment as done.

Thanks Ayal! Latest comments should be addressed and I am planning on landing this soon.

This revision was landed with ongoing or failed builds.Feb 27 2022, 9:34 AM
This revision was automatically updated to reflect the committed changes.