[VPlan] Model first exit values using VPLiveOut.

[fhahn]

Summary

This patch introduces a new VPLiveOut subclass of VPUser to model
exit values explicitly. The initial version handles exit values that
are neither part of induction or reduction chains nor first order
recurrence phis.

Fixes #51366, #54867, #55167, #55459

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

10647

change independent of this patch?

10651–10652

change independent of this patch?

llvm/lib/Transforms/Vectorize/VPlan.cpp

1052

Set the insertion point of State's builder here?

[fhahn]

Address comments, greatly simplify patch. The new version adds VPExitValues for all values used by LCSSA phis. Non-vplan based helper (fixupIVUsers, fixFirstOrderRecurrence, fixReduction) remove VPExitValues for LCSSA phis they handle directly, before fixing the remaining VPExitValues.

Follow-up patches will gradually replace those helpers with dedicated users in VPlan.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8753

This code is now completely gone.

10647

Done in 5b00d13c0071.

10651–10652

Done in 5b00d13c0071.

llvm/lib/Transforms/Vectorize/VPlan.cpp

335

Should be adjusted in the current version, thanks!

1052

Done in the latest version (at the new place this is called)

1101

I think this should never be called multiple times with the same PN. Added an assertion.

llvm/lib/Transforms/Vectorize/VPlan.h

678

Fixed, thanks!

2526

Fixed, thanks!

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

10651–10652

While we're here, first set Header then set its name?

10663

How do the new exit values created by addUsersInExitBlock() below differ from the existing exit values of BestEpiPlan they replace? Both wrap the same LCSSA phis and presumably use the same VPValue from within BestEpiPlan. When called to fix their phi, they should update distinct incoming values corresponding to distinct middle blocks, but those are independent of the exit values themselves - that's why Plan is provided to fixPhi()?

10672

This processLoop() method is becoming 388 LOC long... any change to it should consider refactoring?

llvm/lib/Transforms/Vectorize/VPlan.cpp

1081

Perhaps call them VPLiveOut/VPLiveOutIR/VPLiveOutUser/VPLiveOutIRUser rather than VPExitValue, given how they are printed, and to complement live-in IR Values which are represented via VPDef-less VPValues supporting getLiveInIRValue()?

assert/verify/note somewhere that VPExitValue is assumed to have a single operand?

llvm/lib/Transforms/Vectorize/VPlan.h

685

const?
(Currently used for printing only.)

2630

Change related to this patch?
Can a test demonstrate its need?

[fhahn]

Address latest comments, thanks!

[Ayal]

Looks good to me! Adding minor suggestions.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

591

Worth retaining this explanation when documenting LiveOut/fixPhi()?

3394

Suffice to remove LiveOut only when actually fixing the incoming, i.e., under the if?

3716

I.e., there’s nothing to fix from vector loop, phi should have incoming from scalar loop only?

3717

Worth reversing the condition to handle the simpler case first?

Or have addUsersInExitBlock() bail out early if requiresScalarEpilogue()?

3719

Set to first non phi instead of begin, as we prepare for non phi extracts, although middle block is free of (LCSSA) phi’s atm?

May as well pass MiddleBlock to fixPhi, having directed Builder to it, instead of having each fixPhi derive it from Plan? (Can also have fixPhi derive MiddleBlock from Builder…)

3874

Single else placed earlier suffices, no need for same else here as well?

3932

In general LiveOut exits from VPlan to IR rather than from Loop. Distinction more important for outerloop vectorization.

4060

A bit confusing when to else cleanup LiveOuts; perhaps do so directly rather than as an else, or when creating LiveOuts?

8708

Can fold both early exits into one.

Also early exit if requiresScalarEpilogue()?

9157

ditto regarding retention of LoopExitValue vs. VPlanLiveOut.

llvm/lib/Transforms/Vectorize/VPlan.cpp

651

nits: set ExitingVPValue to operand(0), used twice.
Derive and set MiddleVPBock from loop/outermost region enclosing ExitingVPValue, rather than from Plan? Or OTOH have it passed in, as it’s the same for all phis to fix.

1102

assert count is zero?

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

212

nit: empty line before final return true?

[fhahn]

Address latest comments, thanks!

The latest version also removes a workaround to detect users outside the loop using IR def-use chains (HasUsersOutsideLoop).

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

591

I moved the comment to VPLiveOut::fixPhi.

3394

Yes that should be sufficient, updated!

3716

Reworded the comment, thanks!

3717

Worth reversing the condition to handle the simpler case first?

Done!

Or have addUsersInExitBlock() bail out early if requiresScalarEpilogue()?

I think that would have the drawback that we might miss uses outside the vector loop in VPlan analyses. The latest version of the patch removed a workaround that required us checking the IR def-use chains to detect outside users.

3719

Set to first non phi instead of begin, as we prepare for non phi extracts, although middle block is free of (LCSSA) phi’s atm?

Done thanks!

May as well pass MiddleBlock to fixPhi, having directed Builder to it, instead of having each fixPhi derive it from Plan? (Can also have fixPhi derive MiddleBlock from Builder…)

I updated fixPhi to use the current block from the builder instead, seemed simpler.

3874

I think I might be missing something. Are you referring to removing all live outs earlier in fixVectorizedLoop via Plan.clearLiveOuts? This should only cover the case where we require scalar epilogues, whereas here we only deal with the other case.

3932

I'll undo the change, this was just an accidental replacement.

4060

I'm not entirely sure what you are suggesting here. The reason this is done here to only remove the live-out of the current reduction. Doing so when creating LiveOuts is more complicated (as in earlier versions of the patch).

8708

Can fold both early exits into one.

Done, thanks!

Also early exit if requiresScalarEpilogue()?

I think we should still create live-outs if requiresScalarEpilogue, otherwise some recipes may be considered dead if they only have uses outside the loop. The latest version of the patch uses that property to remove a workaround in VPlanTransforms that used IR def use chains to detect users outside the loop.

9157

Changed back thanks!

10651–10652

Done in fcfb86483b29df124c0b4a61ff65b0c6800f64b7

10663

I think the comment was for an earlier version, the code is gone now. Depends on D125810

10672

I think this comment was for an earlier version of the patch, the changes are gone now

llvm/lib/Transforms/Vectorize/VPlan.cpp

651

nits: set ExitingVPValue to operand(0), used twice.

Done, thanks!

Derive and set MiddleVPBock from loop/outermost region enclosing ExitingVPValue, rather than from Plan? Or OTOH have it passed in, as it’s the same for all phis to fix.

Updated to get the block from the builder directly.

828

Do you mean in addition to VPScalarExitValue? I've not added a new subclass in this patch as perhaps it would be good add it once we have multiple sub-classes?

1081

Renamed to VPLiveOut &LiveOut.

I added a check to the VPlan verifier.

1102

adjusted, thanks!

llvm/lib/Transforms/Vectorize/VPlan.h

685

Adjusted, thanks!

2630

I forgot to remove this change, it's not needed any longer. Removed, thanks!

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

212

Adjusted, thanks!

[Ayal]

Looks good to me, thanks!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3714

OK, this is where LCSSA phis were fixed originally, can clear LiveOuts here if requiresScalarEpilogue().

3874

Yes; we’re also checking if requiresScalarEpilogue() here, as done earlier and later when dealing with various reductions/inductions/recurrences

4060

Was only referring to avoiding creating any LiveOut if requiresScalarEpilogue().

8708

Also early exit if requiresScalarEpilogue()?

I think we should still create live-outs if requiresScalarEpilogue, otherwise some recipes may be considered dead if they only have uses outside the loop. The latest version of the patch uses that property to remove a workaround in VPlanTransforms that used IR def use chains to detect users outside the loop.

This perhaps deserves a comment somewhere, explaining that VPLiveOuts are used to represent loop live out values that originally fed LCSSA phis in Exit Block, where these phis may or may not require fixing - if their edge is removed due to required scalar epilogue - in which case they are still live out but feed only preheader of scalar epilogue?

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

386

Nice cleanup!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3714

Sounds good, that's what the latest version of the patch is doing.

3874

I think for now it is easiest to keep the check and remove it once we migrate exit value handling for those.

8708

I'll adjust the comment here.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8708

I'll adjust the comment here.

Thanks!

Perhaps instead of deleting LiveOuts whose phis are fixed or need not be fixed due to required scalar epilog, such LiveOuts should be marked as "fixed" - so that queries of outside users still hold while preventing their future fixes(?). This may become clearer when external users of inductions/reductions/recurrences are introduced.

[paulwalker-arm]

Hi @fhahn. This patch looks be the cause of the failure reported by https://lab.llvm.org/buildbot/#/builders/176/builds/1723. As well as on AArch64 I also see the failure on X86_64 when doing the following cross compile:

./bin/clang++ -target aarch64-linux-gnu --sysroot=/opt/aarch64-sysroot --gcc-toolchain=/opt/aarch64-cross-compiler -DGTEST_HAS_RTTI=0 -D_DEBUG -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Ilib/Transforms/Scalar -I/home/pmw/projects/upstream-llvm/llvm-project/llvm/lib/Transforms/Scalar -Iinclude -I/home/pmw/projects/upstream-llvm/llvm-project/llvm/include -mcpu=a64fx -msve-vector-bits=512 -mllvm -treat-scalable-fixed-error-as-warning=false -fPIC -fno-semantic-interposition -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wc++98-compat-extra-semi -Wimplicit-fallthrough -Wcovered-switch-default -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wsuggest-override -Wno-comment -Wstring-conversion -Wmisleading-indentation -fdiagnostics-color -ffunction-sections -fdata-sections -O3 -DNDEBUG    -fno-exceptions -fno-rtti -UNDEBUG -std=c++14 -MD -MT lib/Transforms/Scalar/CMakeFiles/LLVMScalarOpts.dir/SimpleLoopUnswitch.cpp.o -MF lib/Transforms/Scalar/CMakeFiles/LLVMScalarOpts.dir/SimpleLoopUnswitch.cpp.o.d -o SimpleLoopUnswitch.cpp.o -c /home/pmw/projects/upstream-llvm/llvm-project/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

The failure disappears after locally reverting this patch.

[fhahn]

In D123537#3530208, @paulwalker-arm wrote:

Hi @fhahn. This patch looks be the cause of the failure reported by https://lab.llvm.org/buildbot/#/builders/176/builds/1723. As well as on AArch64 I also see the failure on X86_64 when doing the following cross compile:

./bin/clang++ -target aarch64-linux-gnu --sysroot=/opt/aarch64-sysroot --gcc-toolchain=/opt/aarch64-cross-compiler -DGTEST_HAS_RTTI=0 -D_DEBUG -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Ilib/Transforms/Scalar -I/home/pmw/projects/upstream-llvm/llvm-project/llvm/lib/Transforms/Scalar -Iinclude -I/home/pmw/projects/upstream-llvm/llvm-project/llvm/include -mcpu=a64fx -msve-vector-bits=512 -mllvm -treat-scalable-fixed-error-as-warning=false -fPIC -fno-semantic-interposition -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wc++98-compat-extra-semi -Wimplicit-fallthrough -Wcovered-switch-default -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wsuggest-override -Wno-comment -Wstring-conversion -Wmisleading-indentation -fdiagnostics-color -ffunction-sections -fdata-sections -O3 -DNDEBUG    -fno-exceptions -fno-rtti -UNDEBUG -std=c++14 -MD -MT lib/Transforms/Scalar/CMakeFiles/LLVMScalarOpts.dir/SimpleLoopUnswitch.cpp.o -MF lib/Transforms/Scalar/CMakeFiles/LLVMScalarOpts.dir/SimpleLoopUnswitch.cpp.o.d -o SimpleLoopUnswitch.cpp.o -c /home/pmw/projects/upstream-llvm/llvm-project/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

The failure disappears after locally reverting this patch.

Thanks for the heads up! I pushed 97590baead08 which should fixe the issue. I am keeping an eye on the bot, it looks like it made it past building SimpleLoopUnswitch.cpp already.

[chapuni]

This brings unstable behavior.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3721

This loop is affected by DenseMap.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3721

Thanks, should be fixed by 1ba42dd04b8d