[VPlan] Introduce recipe to build scalar steps.

[fhahn]

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.

[fhahn]

rebase on top of D116123

[fhahn]

rebased after moving SCEV expansion to extra recipe D116288

[Ayal]

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.

8922

early-exit if !OnlyScalarStepsNeeded()

8931

Pass StepSCEV instead of II->getSteps()?

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

8936

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.

9078

VectorIVs and ScalarIVs seem useless?

9079

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

9105

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

9111

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.

9122

Why is this setRecipe moved?

9138

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

9733

Store per-part 0?

9735

ditto

10201

Update comment

llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h

174 ↗

(On Diff #396234)

Document?

176 ↗

(On Diff #396234)

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.)

1115

"their [vector and] scalar values"?

1128

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.

1139

"[vectorized and]"

llvm/lib/Transforms/Vectorize/VPlanValue.h

342

Lex order

[fhahn]

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]

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?

9732

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?

1379

\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]

Address latest comments, thanks!

[fhahn]

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!

8922

The whole function is gone now.

8931

The whole function is gone now.

8936

The whole function is gone now.

9078

Those changes are gone now.

9079

Those changes are gone now.

9105

Those changes are gone now.

9111

Those changes are gone now.

9122

changes gone in latest iteration

9138

changes gone in latest iteration

9732

Added assert, thanks!

llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h

176 ↗

(On Diff #396234)

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

1115

Removed, thanks!

1128

Simplified, thanks!

1139

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!

[Ayal]

Looks good to me, thanks!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9236

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?

1378

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

[fhahn]

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