This is an archive of the discontinued LLVM Phabricator instance.

[VPlan] Add recipe for first-order rec phis, make splicing explicit.
ClosedPublic

Authored by fhahn on Jun 28 2021, 2:48 AM.

Details

Summary

This patch adds a VPFirstOrderRecurrencePHIRecipe, to further untangle
VPWidenPHIRecipe into distinct recipes for distinct use cases/lowering.
See D104989 for a new recipe for reduction phis.

This patch also introduces a new FirstOrderRecurrenceSplice
VPInstruction opcode, which is used to make the forming of the vector
recurrence value explicit in VPlan. This more accurately models def-uses
in VPlan and also simplifies code-generation. Now, the vector recurrence
values are created at the right place during VPlan-codegeneration,
rather than during post-VPlan fixups.

Diff Detail

Event Timeline

fhahn created this revision.Jun 28 2021, 2:48 AM
fhahn requested review of this revision.Jun 28 2021, 2:48 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 28 2021, 2:48 AM
Herald added a subscriber: vkmr. · View Herald Transcript
Ayal added inline comments.Jul 5 2021, 3:01 PM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
4169

no need to check if !PhiR, no need to getDef()

4199

temporary value for s1 - this value is no longer temporary, but rather one that is updated here

4225–4226

Can have FORRecipe::execute() name the phi and hook it up to VectorInit (Start)?

4229

UF is at-least 1?

9181–9182

(lambda taken out of loop, to be reused below)

9227–9250

Add a comment what the code below does?

9229

drop getVPValue()?
RecurP >> RecurPHI?

9234

BackedgeValue is always a recipe; maybe worth having getBackedgeRecipe()

9237

Better have a VPValue *Prev rather than getDef()->getVP[Single]Value()?

9238

assert Prev is the last insn in its region?

9240

moveBefore first non-phi?

9244

RecurSplice was built with RecurP as it's first operand?

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

TODO needed here?

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

try to maintain lexicographic order?

1143

another constructor for VPWidenPHIRecipe, receiving both Phi and Start, in addition to the two SC's?

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

If we expect a single value, call getVPSingleValue?

Ayal added inline comments.Jul 6 2021, 2:08 PM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
4232

Can RecipeBuilder.fixHeaderPhis() hook up to LastPrevious incoming across the backedge?

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

Worth a comment regarding Incoming (V1?) for first Part == 0, that getOperand(0) == RecurPHI has only a single Part, hence we get it's single Part 0 from State?

fhahn updated this revision to Diff 357807.Jul 11 2021, 9:47 AM
fhahn marked 13 inline comments as done.

Addressed latest comments,thanks Ayal. I hope I didnt' miss anything. There might be a few formatting issues, which I'll fix once I have updated my local clang-format.

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

Updated to say that we create a phi node v1 for s1.

4225–4226

That's a good point, moved!

4229

Yes, if UF == 0, then VecPhi is used.

9227–9250

Done, I added a description.

9234

Sounds good, updated.

9237

I moved the call to getBackedgeValue directly here and use getBackedgeRecipe below.

9238

GetReplicateRegion already asserts that the recipes parent block contains exactly 1 instruction.

9244

Yes, but we replace all uses of RecurP, so this gets fixed up here.

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

nope, removed.

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

I moved it to the top, but left the others as is for now. I can clean up the ordering separately.

1143

Added and used by VPReductionPHI as well.

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

yes, removed!

I'll remove the default value from the const version in a separate commit.

Ayal added inline comments.Jul 12 2021, 3:53 PM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
4169

nit: can remove PhiR, check directly if &R is a Reduction or FOR PHIRecipe, and rename R >> PhiR

4225–4226

above comment deserves update

4225–4226

SetInsertPoint(VecPhi)?

4226

nit: can keep IdxTy in original location to reduce diff

4229

but when can UF == 0?
isn't the operand of VecPhi across the backedge always the last part of PreviousDef?
Can RecipeBuilder.fixHeaderPhis() hook up this operand?

4235

(This part of fixing middle block and beyond should remain in ILV::fixFirstOrderRecurrence(), until the scope of VPlan expands.)

9227–9250

LVP::buildVPlanWithVPRecipes() is now reaching 300 LOC... would be good to split it, possibly in a follow-up patch.

9238
VPRecipeBase[ ]*PrevRecipe
9244

ah, right, should RAU but for RecurSplice. Worth a comment?

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

Perhaps it would be clearer to first set

auto *V1 = State.get(getOperand(0), 0));

and then use it to set Incoming, better renamed PartMinus1?

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

This check for IsImmovableRecipe is no longer needed?

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

(try to) keep lex order within Phi-like VPValues?

338

ditto

fhahn marked 14 inline comments as done.Jul 13 2021, 12:51 PM
fhahn added inline comments.
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
4169

I think this one should be addressed now.

4225–4226

I removed it as it seems out of date now.

4229

Oh right, not sure where this originally came from. I removed it now.

I don't think we can hook this up in RecipeBuilder.fixHeaderPhis() , because we only need to hook up the last part.

4235

sounds good, the code will remain here for now.

9227–9250

sounds good as a follow up.

9244

yes, added a comment.

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

updated, thanks.

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

no, because the shuffle mentioned in the comment is now explicit in the VPlan, and the existing def-use checks ensure that the transform does not happen in the case.

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

should be at the right place now.

338

should be at the right place now.

fhahn updated this revision to Diff 358396.Jul 13 2021, 12:51 PM
fhahn marked 8 inline comments as done.

Address latest comments, thanks!

Ayal added inline comments.Jul 15 2021, 2:17 PM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
4169

Suffice to simply do:

for (VPRecipeBase &PhiR : Header->phis()) {
  if (auto *ReductionPhi = dyn_cast<VPReductionPHIRecipe>(&PhiR))
    fixReduction(ReductionPhi, State);
  else if (isa<VPFirstOrderRecurrencePHIRecipe>(&PhiR))
    fixFirstOrderRecurrence(&PhiR, State);
}

?

4229

I don't think we can hook this up in RecipeBuilder.fixHeaderPhis() , because we only need to hook up the last part.

Ah, sorry, RecipeBuilder.fixHeaderPhis() already hooks up the 2nd operand of FOR phi's. I meant to offload the code-gen fixing of VecPhi to Incoming's last part, from ILV here over to VPlan::execute(), possibly in a last stage there; leaving here only code-gen fixings of middle-block and beyond. Can also be done in a separate follow-up patch.

4230

Is this needed? We're not inserting anything at VecPhi, right?

fhahn updated this revision to Diff 359645.Jul 18 2021, 12:49 PM
fhahn marked an inline comment as done.

Address latest comments, thanks!

fhahn marked an inline comment as done.Jul 18 2021, 12:51 PM
fhahn added inline comments.
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
4169

Sounds good, updated.

4229

Oh I see. I put up D106244 as follow-up.

4230

Nope, I removed it.

Ayal accepted this revision.Jul 18 2021, 2:34 PM

Looks good to me, thanks!
With a minor last nit.

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

Document, explaining that the backedge value must correspond to a recipe?

This revision is now accepted and ready to land.Jul 18 2021, 2:34 PM
This revision was landed with ongoing or failed builds.Jul 20 2021, 7:14 AM
This revision was automatically updated to reflect the committed changes.
fhahn marked an inline comment as done.
fhahn added a comment.Jul 20 2021, 7:16 AM

Thanks Ayal!

thakis added a subscriber: thakis.Jul 25 2021, 2:29 PM

This makes clang assert (in +Asserts builds) or crash (in -Asserts builds) in this standalone repro: https://bugs.chromium.org/p/chromium/issues/detail?id=1232798#c2

This makes clang assert (in +Asserts builds) or crash (in -Asserts builds) in this standalone repro: https://bugs.chromium.org/p/chromium/issues/detail?id=1232798#c2

Reverted for now in b1777b04dc4b1a9fee0e7effa7e177892ab32ef0

fhahn added a comment.Jul 26 2021, 7:53 AM

This makes clang assert (in +Asserts builds) or crash (in -Asserts builds) in this standalone repro: https://bugs.chromium.org/p/chromium/issues/detail?id=1232798#c2

Reverted for now in b1777b04dc4b1a9fee0e7effa7e177892ab32ef0

Thanks for the reproducer & revert!

The underlying issue was that we were using VPValues fetched for the stored values in the original IR, rather than the potentially modified stored values in the memory recipes. that should be fixed in d995d6376. I added a reduced version of the reproducer as test in 93664503be6b. And I now recommitted the patch.