Page MenuHomePhabricator

[LV] Patch up induction phis after VPlan execution.
Needs ReviewPublic

Authored by fhahn on Thu, Nov 4, 5:31 AM.

Details

Reviewers
Ayal
gilr
rengolin
Summary

This patch moves fixing up the incoming value of phis for
VPWidenIntOrFpInductionRecipes to after the VPlan is executed.

At the moment, the code in widenIntOrFpInduction relies on the vector
loop latch being created *before* the VPlan is executed. This prevents
us from modeling the vector latch, preheader and exit blocks in VPlan.

By patching up the incoming values for induction PHIs after VPlan
execution, we remove the need to create the latch up front. This enables
generating the vector latch directly from VPlan, which in turn is
required to enable modeling prehader and exit blocks.

The patch uses a workaround to access both the induction increment and
the vector phi for the recipe. It adds 2 new VPValues which are set to
them. While this is a temporary workaround, this will be removed once
the induction code generation is moved to work on VPlan more directly.
See D111303 for the next step, making the induction increment explicit
as VPValue operand.

Diff Detail

Event Timeline

fhahn created this revision.Thu, Nov 4, 5:31 AM
fhahn requested review of this revision.Thu, Nov 4, 5:31 AM
Herald added a project: Restricted Project. · View Herald TranscriptThu, Nov 4, 5:31 AM
Herald added a subscriber: vkmr. · View Herald Transcript
Ayal added a comment.Mon, Nov 22, 10:04 AM

Would it be easier to first keep LastInduction in its original place in the header and then sink it to the latch as a VPlan-to-VPlan transformation after all blocks have been formed? Such a patch should refer to the original D22416.

fhahn updated this revision to Diff 389514.Wed, Nov 24, 8:52 AM

Rebased, all tests should be passing now!

Would it be easier to first keep LastInduction in its original place in the header and then sink it to the latch as a VPlan-to-VPlan transformation after all blocks have been formed? Such a patch should refer to the original D22416.

In this patch, there is still no recipe to represent LastInduction, so unfortuantely I don't think it could be sunk just yet. But D113223 (next patch in stack after the current one) introduces new VPInstruction opcodes InductionIncrementNUW/InductionIncrement and uses them to explicitly model LastInduction.

he patch then can simplify add it to the last block of the plan. The exit condition & branch get a similar treatment in D113224.

Ayal added a comment.Thu, Nov 25, 1:04 AM

Rebased, all tests should be passing now!

Would it be easier to first keep LastInduction in its original place in the header and then sink it to the latch as a VPlan-to-VPlan transformation after all blocks have been formed? Such a patch should refer to the original D22416.

In this patch, there is still no recipe to represent LastInduction, so unfortuantely I don't think it could be sunk just yet. But D113223 (next patch in stack after the current one) introduces new VPInstruction opcodes InductionIncrementNUW/InductionIncrement and uses them to explicitly model LastInduction.

he patch then can simplify add it to the last block of the plan. The exit condition & branch get a similar treatment in D113224.

Yes, in order to sink LastInduction it should be wrapped in a recipe by itself, separating it from VPWidenIntOrFpInductionRecipe. Would introducing such a LastInduction recipe here, potentially created in FixHeaderPhis out of its feeding/consuming VPWidenIntOrFpInductionRecipe, be simpler for this patch? It needs only to take of

LastInduction = cast<Instruction>(
    Builder.CreateBinOp(AddOp, LastInduction, SplatVF, "step.add"));
LastInduction->setDebugLoc(EntryVal->getDebugLoc());

keeping VPWidenIntOrFpInductionRecipe with a single value Def.

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

Is this addition of excluding VPWidenIntOrFpInductionRecipe independent of this patch?

2447

PhiDef is redundant? VecInd is already being State.set above as part 0 of Def.

9167

This is when an induction feeds a reduction/FOR; the induction became a multi-valued def so we want to select its first, original value?

Perhaps Inductions should be treated as Reductions, included in PhisToFix, and their increment recipe introduced and rewired here?

IV isn't used, suffice to ask isa<>.

9523–9524

(Related to introducing additional values to a Def; having no underlying values?)

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

who needs the II?

fhahn updated this revision to Diff 389735.Thu, Nov 25, 4:15 AM
fhahn marked 2 inline comments as done.

Addressed comments and added a few additional code comments.

Yes, in order to sink LastInduction it should be wrapped in a recipe by itself, separating it from VPWidenIntOrFpInductionRecipe. Would introducing such a LastInduction recipe here, potentially created in FixHeaderPhis out of its feeding/consuming VPWidenIntOrFpInductionRecipe, be simpler for this patch? It needs only to take of

I had a look, but unfortunately I don't think this is feasible additional work. The step increment value depends on the induction descriptor and may need to be expanded from a SCEV expression in the pre-header. Once we can model the preheader in VPlan, we can add a recipe in the preheader to create the step value.

Alternatively we could land D111303 first, which expands the step up front and maps it to a VPValue that can be used by the induction recipes. Please let me know if you prefer that direction.

A further complication is that LastInduction is also set for CastDef.

LastInduction = cast<Instruction>(
    Builder.CreateBinOp(AddOp, LastInduction, SplatVF, "step.add"));
LastInduction->setDebugLoc(EntryVal->getDebugLoc());

keeping VPWidenIntOrFpInductionRecipe with a single value Def.

Unfortunately VPWidenIntOrFpInductionRecipe is already a multi-def in some cases (due to handling casts as well).

fhahn marked 2 inline comments as done.Thu, Nov 25, 4:20 AM
fhahn added inline comments.
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
1211

I think it makes sense to exclude it in any case, but it is becoming problematic with the patch (due to adding additional defs, causing a crash in `getUndderlyingValue). I *think* it could also cause issues if the induction recipe has a CastDef.

2447

Unfortunately Def may be reset to something other than the phi, e.g. in CreateSplatIV .

9167

I changed it to isa<>.

Perhaps Inductions should be treated as Reductions, included in PhisToFix, and their increment recipe introduced and rewired here?

Agreed, but could/should be a separate change?

9523–9524

Yes.

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

No, it is a leftover from an earlier version. Removed all II-related changes.