This is an archive of the discontinued LLVM Phabricator instance.

[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

fhahn created this revision.Dec 17 2021, 10:26 AM
fhahn requested review of this revision.Dec 17 2021, 10:26 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 17 2021, 10:26 AM
Herald added a subscriber: vkmr. · View Herald Transcript
fhahn updated this revision to Diff 395733.Dec 21 2021, 12:06 PM

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
561

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

2712

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

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

?

7920

OldInduction already set at State construction above?

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

8407

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.

8905

early-exit if !OnlyScalarStepsNeeded()

8914

Pass StepSCEV instead of II->getSteps()?

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

8919

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.

9061

VectorIVs and ScalarIVs seem useless?

9062

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
9088

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

9094

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.

9105

Why is this setRecipe moved?

9121

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

9716

Store per-part 0?

9718

ditto

10182

Update comment

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

Document?

177

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
645–646

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
703

(Here the insertBefores appear next to each other.)

1121

"their [vector and] scalar values"?

1134

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.

1145

"[vectorized and]"

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

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
2701

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?

8530

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

9715

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
1287

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
703

Deserves a separate/additional comment?

1395

\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

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

410

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

TODO: Step should be placed in preheader?

llvm/lib/Transforms/Vectorize/VPlanTransforms.h
59

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
561

OldInduction is not needed in the latest version.

2701

Updated the comment, thanks!

2712

Folded, thanks!

7920

removed in the latest version

8407

Removed in the latest version

8530

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

8905

The whole function is gone now.

8914

The whole function is gone now.

8919

The whole function is gone now.

9061

Those changes are gone now.

9062

Those changes are gone now.

9088

Those changes are gone now.

9094

Those changes are gone now.

9105

changes gone in latest iteration

9121

changes gone in latest iteration

9715

Added assert, thanks!

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

This is gone in the latest version.

llvm/lib/Transforms/Vectorize/VPlan.cpp
645–646

Done!

1287

Added accessors and comment, thanks.

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

Removed, thanks!

1134

Simplified, thanks!

1145

Removed, thanks!

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

Moved, thanks!

410

Done, thanks!

415

Added the TODO, thanks!

llvm/lib/Transforms/Vectorize/VPlanTransforms.h
59

Much better description, updated!

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

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
9219

leave this w/o change?

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

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

1394

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.