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
4170–4171

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

4201

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

4227–4228

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

4231

UF is at-least 1?

9254–9255

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

9300–9323

Add a comment what the code below does?

9302

drop getVPValue()?
RecurP >> RecurPHI?

9307

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

9310

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

9311

assert Prev is the last insn in its region?

9313

moveBefore first non-phi?

9317

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?

1144

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
4233

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
4201

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

4227–4228

That's a good point, moved!

4231

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

9300–9323

Done, I added a description.

9307

Sounds good, updated.

9310

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

9311

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

9317

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.

1144

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
4170–4171

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

4227–4228

above comment deserves update

4227–4228

SetInsertPoint(VecPhi)?

4228

nit: can keep IdxTy in original location to reduce diff

4231

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?

4236

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

9300–9323

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

9311
VPRecipeBase[ ]*PrevRecipe
9317

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
244

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
4170–4171

I think this one should be addressed now.

4227–4228

I removed it as it seems out of date now.

4231

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.

4236

sounds good, the code will remain here for now.

9300–9323

sounds good as a follow up.

9317

yes, added a comment.

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

updated, thanks.

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

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
4170–4171

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);
}

?

4231

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.

4232

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
4170–4171

Sounds good, updated.

4231

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

4232

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–1122

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.