This is an archive of the discontinued LLVM Phabricator instance.

[VPlan] Replace CondBit with BranchOnCond VPInstruction.
ClosedPublic

Authored by fhahn on May 29 2022, 1:43 PM.

Details

Summary

This patch removes CondBit and Predicate from VPBasicBlock. To do so,
the patch introduces a new branch-on-cond VPInstruction opcode to model
a branch on a condition explicitly.

This addresses a long-standing TODO/FIXME that blocks shouldn't be users
of VPValues. Those extra users can cause issues for VPValue-based
analyses that don't expect blocks. Addressing this fixme should allow us
to re-introduce 266ea446ab7476.

The generic branch opcode can also be used in follow-up patches.

Depends on D123005.

Diff Detail

Event Timeline

fhahn created this revision.May 29 2022, 1:43 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 29 2022, 1:43 PM
fhahn requested review of this revision.May 29 2022, 1:43 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 29 2022, 1:43 PM
Herald added a subscriber: vkmr. · View Herald Transcript
Ayal added a comment.May 29 2022, 11:39 PM

Should tests check for new BranchOnCond VPInstruction?

Are the users of CondBit/Predicate ok w/ this change (VPlanPredicator)?

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

Similar to VPBranchOnMaskRecipe (have all terminator recipes share this somehow?):

// Replace the temporary unreachable terminator with a new conditional branch,
// hooking it up to backward destination now and to forward destination(s) later when they are created.

Handle loop branches of all loops, not only outermost?

Set exit successor to nullptr to be set later, rather than Builder.GetInsertBlock()?

llvm/lib/Transforms/Vectorize/VPlan.h
548–549

Update comment.

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp
60

May be useful to have an isaTerminator(Recipe).

Can have VPBB hold its 'singleton' terminator recipe (instead of CondBit) separately from all other recipes, analogous to the idea for Region to hold its singleton canonical IV recipe directly.

fhahn updated this revision to Diff 432986.May 30 2022, 2:03 PM
fhahn marked an inline comment as done.

Address latest comments, thanks!

Should tests check for new BranchOnCond VPInstruction?

There's Transforms/LoopVectorize/vplan-printing-outer-loop.ll now, which tests this.

Are the users of CondBit/Predicate ok w/ this change (VPlanPredicator)?

There are no remaining users after this change. VPlanPredicator at the current stage is not used and would need major updates to support the new region structure. There's D123017 to remove it, which has been approved and I plan to land this soon, ideally once D123005 is ready/

fhahn added inline comments.May 30 2022, 2:33 PM
llvm/lib/Transforms/Vectorize/VPlan.cpp
778

Similar to VPBranchOnMaskRecipe (have all terminator recipes share this somehow?):

Not sure how to best do this at the moment. Might be worth introducing a dedicated terminator subclass once things settle down a bit?

Handle loop branches of all loops, not only outermost?

Done, removed the VPlan native code and also use parent region rather than topmost.

Set exit successor to nullptr to be set later, rather than Builder.GetInsertBlock()?

Done, thanks!

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp
60

I added a VPBasicBlock::getTerminator() helper. Not sure if it is worth adding state to track the terminator, as it is trivial to access them for now.

fhahn updated this revision to Diff 433100.May 31 2022, 8:50 AM

Remove a bit of unneeded code to hook up to ExitBB.

Ayal added inline comments.Jun 1 2022, 1:02 PM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8513

nit, unrelated to this patch: should this Exit also be Exiting?

8667–8668

Seems somewhat awkward for addCanonicalIVRecipes() to take care of erasing a redundant terminator; could this cleanup take place when VPlanNative creates said terminator, before it calls addCanonicalIVRecipes()?

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

VPBB's w/o successors - must not be empty?

401

Should some 'isLatch()' check if a VPBB is exiting its enclosing loop region?

768

When is this called? Expecting Predication to replace forward BranchOnCond by Blend or BranchOnMask's for UF>1 and/or VF>1, and backward BranchOnCond to be replaced by BranchOnCount?

Assert here that Part==0?

777

If isLatch()?
Have separate VPInstructions for forward and backward/loop-latch branches?

778

Similar to VPBranchOnMaskRecipe (have all terminator recipes share this somehow?):

Not sure how to best do this at the moment. Might be worth introducing a dedicated terminator subclass once things settle down a bit?

Sure; perhaps convert VPBranchOnMaskRecipe to VPInstruction, thereby having an opcode interval for terminating branch VPInstructions, in a follow-up patch.

782

nit: can remove {}'s

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

or if there are no successors

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp
219–225

Should BranchOnCond be created here instead of below in buildPlainCFG()?
Comment deserves updating.

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

Why is this change needed now?

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp
60

Sure, also follows LLVM-IR, except that successors are held in VPBB and their order must match the direction dictated by CondBit of BranchOnCond.

fhahn updated this revision to Diff 433560.Jun 1 2022, 2:57 PM
fhahn marked 11 inline comments as done.

Address latest comments, thanks!

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

Updated in 08482830eb8a.

8667–8668

I tried remove this when building the native plan, but this leaves the plan in an inconsistent state (exiting block without cond terminator) which triggers asserts with getTerminator calls. I move the code to remove it to the caller of this function.

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

I think in theory it could be possible in native path, at least I don't think that's an enforced invariant?

401

Thanks, I added an isExiting helper, which might be a bit more descriptive and more in-line with the naming for the other helpers.

768

It is called for different parts, but everything worked because it always removed the previous terminator. Updated to break on part != 0.

777

Updated to use isExiting. I'm not sure if there's any benefit at the moment to introduce different recipes.

782

Removed, thanks!

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

Adjusted, thanks!

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp
219–225

Moved, thanks!

I also updated the comment.

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

BranchOnCount are VPInstructions without underlying values. I updated the code to just skip terminators.

Ayal accepted this revision.Jun 2 2022, 1:43 AM

This looks good to me, thanks!
Adding minor nits.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8667–8668

This is fine, thanks.

Perhaps native should addCanonicalIVRecipes from within its VPInstructionsToVPRecipes.

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

Relax assert to check for no more than a single successor?

427

Does 'exiting' here refer to loop-exiting/latch or to region-exiting? I.e., are replicating region exits included or excluded.

768

ok, this implies condition must be uniform, may be good to assert so.

777

Ok. A thought to keep in mind.

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp
317

w/o the using condition bit bit.

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

Ahh, fine, very good.

nit: there's not much to continue after reaching the terminator; can iterate excluding terminator similar to excluding phi's.

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp
54

|| isExiting(VPB)?

This revision is now accepted and ready to land.Jun 2 2022, 1:43 AM
fhahn updated this revision to Diff 433731.Jun 2 2022, 6:36 AM
fhahn marked 8 inline comments as done.

This looks good to me, thanks!
Adding minor nits.

Thanks. Addressed the latest comments and I am planning on landing this soon.

fhahn added inline comments.Jun 2 2022, 6:39 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8667–8668

Will do as follow-up!

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

Yes, adjusted!

427

The current version just checks for exiting of a region.

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp
317

Updated, thanks!

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

Updated, thanks!

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp
54

Updated thanks!

This revision was landed with ongoing or failed builds.Jun 3 2022, 3:49 AM
This revision was automatically updated to reflect the committed changes.