[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

8903

This stretches the already too long method to exceed 400 lines... please outline.

8910

This should get rather than add, right?

Check if V is a header phi recipe, whose exit values are not represented yet?

Exit values of inductions are disconnected from the loop body by precomputing them in preheader, so modeling them as VPInstructions in the middle block would require also modeling their precomputation in the preheader?

8917

Can alternatively first identify all VPValues in loop which are Not-To-Feed-Exit-VPInstruction, then wrap every middle-block loop-closed phi with an Exit VPInstruction provided it does not use an NTFEV VPValue? Instead of collecting NTFEV's and calling removeExitUsers() for each.

llvm/lib/Transforms/Vectorize/VPlan.cpp

820

Indicate that ExitValue usesScalars()?
Perhaps worth emphasizing in the name - reduction epilogues using vectors probably deserve a separate "Exit Value" recipe.

824

nit: empty line?

[fhahn]

Address latest comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8903

Moved to a separate function, thanks!

8910

This should get rather than add, right?

We could have loop invariant incoming values which won't be modeled in VPlan, hence getOrAddVPValue.

Exit values of inductions are disconnected from the loop body by precomputing them in preheader, so modeling them as VPInstructions in the middle block would require also modeling their precomputation in the preheader?

We should be able to add those to the pre-header, but I think it's best to do it one step at a time?

8917

Updated to collect values to skip first, thanks!

llvm/lib/Transforms/Vectorize/VPlan.cpp

820

Indicate that ExitValue usesScalars()?

Added usesScalars implementation.

Perhaps worth emphasizing in the name - reduction epilogues using vectors probably deserve a separate "Exit Value" recipe.

Good point, not sure what the ideal name would be. Changed ScalarExitValue but I am not sure if that is much better. They model all exit values that do not need special handling.

824

Removed, thanks!

[fhahn]

Bring back getOrAddVPValue, as per inline comment.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4044–4045

Is this made redundant by ScalarExitValues?

8711

ScalarExitValue represents a (loop-closed) phi, and as such can be inserted at the top of MiddleVPBB?

8712

Early-exit if loop has multiple exit blocks, at the outset?

8715

Early-exit instead, if ExitBB has more that one predecessor, at the outset?

8720

This should get rather than add, right?

We could have loop invariant incoming values which won't be modeled in VPlan, hence getOrAddVPValue.

Hmm, IncomingValue is initially an IR Instruction inside the loop feeding a loop-closed phi; if it is loop invariant (missed pre-LV LICM) then LV could LICM and move it to the pre-header (analogous to hoisting up a live-out IV) but instead VPlan keeps it in place wrapping it up with a uniform ReplicateRecipe?

8910

Exit values of inductions are disconnected from the loop body by precomputing them in preheader, so modeling them as VPInstructions in the middle block would require also modeling their precomputation in the preheader?

We should be able to add those to the pre-header, but I think it's best to do it one step at a time?

Sure, by all means.

10638

Populate the exit block of the epilog vector loop with scalar exit value recipes, only to discard them all here?

llvm/lib/Transforms/Vectorize/VPlan.cpp

335

Sounds right, but is this really needed - ScalarExitValue recipes seem to only hook-up loop-closed phis (at this time), w/o generating any instructions using Builder?

815

nit: seems more logical to generate code when called for the last part rather than the first, bailing out here if (Part != State.UF - 1), and using Part later rather than State.UF - 1?

820

Indicate that ExitValue usesScalars()?

Added usesScalars implementation.

It actually usesFirstOrLastLane only... perhaps something to think of in the future.

820

Perhaps worth emphasizing in the name - reduction epilogues using vectors probably deserve a separate "Exit Value" recipe.

Good point, not sure what the ideal name would be. Changed ScalarExitValue but I am not sure if that is much better. They model all exit values that do not need special handling.

Hmm, it seems ScalarExitValue merely models/wraps an IR loop-closed-ssa-phi taking care only of hooking it's operand. Perhaps deserves a "VPLiveOut" or "VPLoopClosedPhi" subclass of VPUser?

823

Placing ScalarExitValues inside middleBlock suggests they represent loop-closed phi's that will appear there, but actually the loop-closed phi's reside all along in Exit block, and use ScalarExitValue to retrieve its parent - middleBlock when rewiring its operand(?)

Test pr51366 below shows a ScalarExitValue inside 'exit' block which follows 'middleBlock'. Wonder if they are meant to be fused, provided 'exit' block has no other predecessor, or should ScalarExitValue introduce a loop-closed phi in middleBlock instead?

llvm/test/Transforms/LoopVectorize/X86/pr51366-sunk-instruction-used-outside-of-loop.ll

45

This GEP_LCSSA phi was hooked-up to TMP2 by a ScalarExitValue, right?

[fhahn]

Address latest comments, thanks!

[fhahn]

Remove redundant loop.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4044–4045

It is in the latest version of the patch. One wrinkle is that we need to update the ScalarExitValue instructions in the the plan for the epilogue loop. At the moment this is done by removing the exit values referring the LCSSA phi's for the main loop's exits and adding exit values for the newly created exit block.

That unfortunately requires exposing a bit more functionality to be able to do so.

8711

Added a comment, thanks!

8712

Added check for single predecessor, thanks!

8715

Added early exit, thanks!

8720

Yes that would be an option. It is likely only relevant for handwritten tests.

10638

The issue is that at this point, the exit values do not refer to the LCSSA phis created for the new exit block. I updated the code to re-add the exit values for the newly create exit block after executing the main plan. This allows removing fixLCSSAPHIs.

llvm/lib/Transforms/Vectorize/VPlan.cpp

335

We might need to insert extracts I think.

823

Placing ScalarExitValues inside middleBlock suggests they represent loop-closed phi's that will appear there, but actually the loop-closed phi's reside all along in Exit block, and use ScalarExitValue to retrieve its parent - middleBlock when rewiring its operand(?)

The recipe doesn't create new LCSSA phis, but only updates existing ones. It may need to insert extracts, which should be placed in the middle block.

Test pr51366 below shows a ScalarExitValue inside 'exit' block which follows 'middleBlock'. Wonder if they are meant to be fused, provided 'exit' block has no other predecessor, or should ScalarExitValue introduce a loop-closed phi in middleBlock instead?

I think the exit block can have multiple predecessors, in the test case it also has the latch of the scalar loop as predecessor. We could also generate an LCSSA phi in the middle block, but it doesn't seem needed currently.

llvm/test/Transforms/LoopVectorize/X86/pr51366-sunk-instruction-used-outside-of-loop.ll

45

Yep exactly.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4044–4045

Perhaps better to progress gradually - first introduce loop-closed phi recipes inside Middle block (admittedly affecting many tests?), and model VPlan live-out VPUsers + update VPlan's fixLCSSAPHIs() afterwards?

8711

ScalarExitValue represents a (loop-closed) phi, and as such can be inserted at the top of MiddleVPBB?

Ah, original comment suggested that insert point could alternatively be set to MiddleVPBB->begin() instead of MiddleVPBB->getFirstNonPhi() for ScalarExitValue. But that is incorrect - ScalarExitValue currently represents the rewiring of a loop-value to a loop-closed phi residing in Exit block, rather than a loop-closed phi in Middle block, along with an implicit potential extract - which must appear in MiddleBlock following all its phi's.

A recipe is designed to take care of generating an instruction (one or more) and hooking it up to its operands, rather than taking care of its users.

The term "live-out" may be ambiguous - referring to values defined inside the loop body and used outside of it, and/or values defined inside VPlan's scope and used outside of it. By definition, VPlan live-outs should be represented using a derivative of VPUser that is not a recipe - they must have underlying Instruction/User, which need to be rewired, but belong to no VPBB, potentially held by VPlan itself; analogous to VPlan live-ins represented using VPValues that are not part of any recipe's VPDef, and held in VPlan's VPExternalDefs.

8720

Original comment just notes that this should get rather than add, even if incoming value is loop invariant.

llvm/lib/Transforms/Vectorize/VPlan.cpp

335

Ah, right! Better to dispel this magic rather than place a recipe in a given VPBB for no apparent reason.

815

sounds right?

823

Placing ScalarExitValues inside middleBlock suggests they represent loop-closed phi's that will appear there, but actually the loop-closed phi's reside all along in Exit block, and use ScalarExitValue to retrieve its parent - middleBlock when rewiring its operand(?)

The recipe doesn't create new LCSSA phis, but only updates existing ones. It may need to insert extracts, which should be placed in the middle block.

Let's try to use recipes, represent VPlan live-outs and model loop-closed phi's more explicitly and clearly.

Test pr51366 below shows a ScalarExitValue inside 'exit' block which follows 'middleBlock'. Wonder if they are meant to be fused, provided 'exit' block has no other predecessor, or should ScalarExitValue introduce a loop-closed phi in middleBlock instead?

I think the exit block can have multiple predecessors, in the test case it also has the latch of the scalar loop as predecessor. We could also generate an LCSSA phi in the middle block, but it doesn't seem needed currently.

Generating an LCSSA phi in the middle block, using a dedicated recipe/VPInstruction, seems most reasonable - it would in turn feed the original loop-closed phi of the Exit block (along with an extract if needed), represented as a VPlan live-out VPUser?

[fhahn]

Update the patch to use a dedicated user class (VPExitValue) instead of piggybacking on VPInstruction.

[fhahn]

ping :)

Comments should be addressed in the most recent update.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4044–4045

I think we should try to fix the exit-value case first, as this can currently cause crashes and mis-compiles. I could undo the changes here and keep using fixLCSSAPHIs for the epilogue case. What do you think?

8711

Update to use a dedicated user for exit values.

8720

Ah right! I think we still may need to add a value, e.g. in case if the exit value is only used in the exit phi.

llvm/lib/Transforms/Vectorize/VPlan.cpp

823

Updated the patch to use a separate VPUser for instead a recipe.

[Ayal]

Summary deserves updating.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8712

Comment needs updating: exit values are now represented as VPUsers rather than recipes, they belong to VPlan - 'residing' outside any of VPlan's VPBasicBlock, rather than be added to the beginning of exit/middle block.
No need to set insertion point.

llvm/lib/Transforms/Vectorize/VPlan.cpp

335

Better to set the insertion point to middle block when calling fixPhi's, rather than here, noting that the latter may need to generate extracts there?

1059

Set the insertion point of State's builder here?

1097

Should this check for duplicates, as in getOrAdd?

llvm/lib/Transforms/Vectorize/VPlan.h

678

nit: "recipe"

2523

Can clear exit values regardless if Entry or not?

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

10637

change independent of this patch?

10641

change independent of this patch?

[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

8712

This code is now completely gone.

10637

Done in 5b00d13c0071.

10641

Done in 5b00d13c0071.

llvm/lib/Transforms/Vectorize/VPlan.cpp

335

Should be adjusted in the current version, thanks!

1059

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

1097

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!

2523

Fixed, thanks!

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

10641

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

10653

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()?

10662

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

llvm/lib/Transforms/Vectorize/VPlan.cpp

1088

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.)

2627

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()?

3364

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

3678

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

3679

Worth reversing the condition to handle the simpler case first?

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

3681

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…)

3830

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

3886

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

4003

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

8667

Can fold both early exits into one.

Also early exit if requiresScalarEpilogue()?

9163

ditto regarding retention of LoopExitValue vs. VPlanLiveOut.

llvm/lib/Transforms/Vectorize/VPlan.cpp

652

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.

1098

assert count is zero?

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

211 ↗

(On Diff #430274)

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.

3364

Yes that should be sufficient, updated!

3678

Reworded the comment, thanks!

3679

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.

3681

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.

3830

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.

3886

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

4003

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).

8667

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.

9163

Changed back thanks!

10641

Done in fcfb86483b29df124c0b4a61ff65b0c6800f64b7

10653

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

10662

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

llvm/lib/Transforms/Vectorize/VPlan.cpp

652

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.

820

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?

1088

Renamed to VPLiveOut &LiveOut.

I added a check to the VPlan verifier.

1098

adjusted, thanks!

llvm/lib/Transforms/Vectorize/VPlan.h

685

Adjusted, thanks!

2627

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

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

211 ↗

(On Diff #430274)

Adjusted, thanks!

[Ayal]

Looks good to me, thanks!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3685

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

3830

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

4003

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

8667

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 ↗

(On Diff #430905)

Nice cleanup!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3685

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

3830

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

8667

I'll adjust the comment here.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8667

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

3683

This loop is affected by DenseMap.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3683

Thanks, should be fixed by 1ba42dd04b8d

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

#endif
 
   /// Test a \p Predicate on a \p Range of VF's. Return the value of applying
   /// \p Predicate on Range.Start, possibly decreasing Range.End such that the
   /// returned value holds for the entire \p Range.
   static bool
   getDecisionAndClampRange(const std::function<bool(ElementCount)> &Predicate,
                            VFRange &Range);
 
-protected:
   /// Collect the instructions from the original loop that would be trivially
   /// dead in the vectorized loop if generated.
   void collectTriviallyDeadInstructions(
       SmallPtrSetImpl<Instruction *> &DeadInstructions);
 
+protected:
   /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
   /// according to the information gathered by Legal when it checked if it is
   /// legal to vectorize the loop.
   void buildVPlans(ElementCount MinVF, ElementCount MaxVF);
 
 private:
   /// Build a VPlan according to the information gathered by Legal. \return a
   /// VPlan for vectorization factors \p Range.Start and up to \p Range.End

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

protected:
 
   /// Create code for the loop exit value of the reduction.
   void fixReduction(VPReductionPHIRecipe *Phi, VPTransformState &State);
 
   /// Clear NSW/NUW flags from reduction instructions if necessary.
   void clearReductionWrapFlags(const RecurrenceDescriptor &RdxDesc,
                                VPTransformState &State);
 
-  /// Fixup the LCSSA phi nodes in the unique exit block.  This simply
-  /// means we need to add the appropriate incoming value from the middle
-  /// block as exiting edges from the scalar epilogue loop (if present) are
-  /// already in place, and we exit the vector loop exclusively to the middle
-  /// block.
-  void fixLCSSAPHIs(VPTransformState &State);
-
   /// Iteratively sink the scalarized operands of a predicated instruction into
   /// the block that was created for it.
   void sinkScalarOperands(Instruction *PredInst);
 
   /// Shrinks vector element sizes to the smallest bitwidth they can be legally
   /// represented as.
   void truncateToMinimalBitwidths(VPTransformState &State);
 
for (auto &I : MissingVals) {
     PHINode *PHI = cast<PHINode>(I.first);
     // One corner case we have to handle is two IVs "chasing" each-other,
     // that is %IV2 = phi [...], [ %IV1, %latch ]
     // In this case, if IV1 has an external use, we need to avoid adding both
     // "last value of IV1" and "penultimate value of IV2". So, verify that we
     // don't already have an incoming value for the middle block.
     if (PHI->getBasicBlockIndex(MiddleBlock) == -1)
       PHI->addIncoming(I.second, MiddleBlock);
   }
 }
 
 namespace {
 
 struct CSEDenseMapInfo {
   static bool canHandle(const Instruction *I) {
     return isa<InsertElementInst>(I) || isa<ExtractElementInst>(I) ||
            isa<ShuffleVectorInst>(I) || isa<GetElementPtrInst>(I);
void InnerLoopVectorizer::fixVectorizedLoop(VPTransformState &State,
   // edge.
   if (!Cost->requiresScalarEpilogue(VF)) {
     // Fix-up external users of the induction variables.
     for (auto &Entry : Legal->getInductionVars())
       fixupIVUsers(Entry.first, Entry.second,
                    getOrCreateVectorTripCount(VectorLoop->getLoopPreheader()),
                    IVEndValues[Entry.first], LoopMiddleBlock,
                    VectorLoop->getHeader());
-
-    fixLCSSAPHIs(State);
   }
 
   for (Instruction *PI : PredicatedInstructions)
     sinkScalarOperands(&*PI);
 
   // Remove redundant induction instructions.
   cse(VectorLoop->getHeader());
 
   // Set/update profile weights for the vector and remainder loops as original
   // loop iterations are now distributed among them. Note that original loop
   // represented by LoopScalarBody becomes remainder loop after vectorization.
   //
   // For cases like foldTailByMasking() and requiresScalarEpiloque() we may
   // end up getting slightly roughened result but that should be OK since
   // profile is not inherently precise anyway. Note also possible bypass of
void InnerLoopVectorizer::fixFirstOrderRecurrence(
   // had multiple exiting edges (as we always run the last iteration in the
   // scalar epilogue); in that case, there is no edge from middle to exit and
   // and thus no phis which needed updated.
   if (!Cost->requiresScalarEpilogue(VF))
     for (PHINode &LCSSAPhi : LoopExitBlock->phis())
       if (llvm::is_contained(LCSSAPhi.incoming_values(), Phi))
         LCSSAPhi.addIncoming(ExtractForPhiUsedOutsideLoop, LoopMiddleBlock);
 }
 
 void InnerLoopVectorizer::fixReduction(VPReductionPHIRecipe *PhiR,
                                        VPTransformState &State) {
   PHINode *OrigPhi = cast<PHINode>(PhiR->getUnderlyingValue());
   // Get it's reduction variable descriptor.
   assert(Legal->isReductionVariable(OrigPhi) &&
          "Unable to find the reduction variable");
   const RecurrenceDescriptor &RdxDesc = PhiR->getRecurrenceDescriptor();
 
for (unsigned Part = 0; Part < UF; ++Part) {
       }
       assert(Sel && "Reduction exit feeds no select");
       State.reset(LoopExitInstDef, Sel, Part);
 
       // If the target can create a predicated operator for the reduction at no
       // extra cost in the loop (for example a predicated vadd), it can be
       // cheaper for the select to remain in the loop than be sunk out of it,
       // and so use the select value for the phi instead of the old
       // LoopExitValue.
       if (PreferPredicatedReductionSelect ||
           TTI->preferPredicatedReductionSelect(
               RdxDesc.getOpcode(), PhiTy,
               TargetTransformInfo::ReductionFlags())) {
         auto *VecRdxPhi =
             cast<PHINode>(State.get(PhiR, Part));
         VecRdxPhi->setIncomingValueForBlock(VectorLoopLatch, Sel);
       }
void InnerLoopVectorizer::fixReduction(VPReductionPHIRecipe *PhiR,
   // We know that the loop is in LCSSA form. We need to update the PHI nodes
   // in the exit blocks.  See comment on analogous loop in
   // fixFirstOrderRecurrence for a more complete explaination of the logic.
   if (!Cost->requiresScalarEpilogue(VF))
     for (PHINode &LCSSAPhi : LoopExitBlock->phis())
       if (llvm::is_contained(LCSSAPhi.incoming_values(), LoopExitInst))
         LCSSAPhi.addIncoming(ReducedPartRdx, LoopMiddleBlock);
 
   // Fix the scalar loop reduction variable with the incoming reduction sum
   // from the vector body and from the backedge value.
   int IncomingEdgeBlockIdx =
       OrigPhi->getBasicBlockIndex(OrigLoop->getLoopLatch());
   assert(IncomingEdgeBlockIdx >= 0 && "Invalid block index");
   // Pick the other block.
   int SelfEdgeBlockIdx = (IncomingEdgeBlockIdx ? 0 : 1);
   OrigPhi->setIncomingValue(SelfEdgeBlockIdx, BCBlockPhi);
   OrigPhi->setIncomingValue(IncomingEdgeBlockIdx, LoopExitInst);
while (!Worklist.empty()) {
     for (User *U : Cur->users()) {
       Instruction *UI = cast<Instruction>(U);
       if ((Cur != LoopExitInstr || OrigLoop->contains(UI->getParent())) &&
           Visited.insert(UI).second)
         Worklist.push_back(UI);
     }
   }
 }
 
-void InnerLoopVectorizer::fixLCSSAPHIs(VPTransformState &State) {
-  for (PHINode &LCSSAPhi : LoopExitBlock->phis()) {
-    if (LCSSAPhi.getBasicBlockIndex(LoopMiddleBlock) != -1)
-      // Some phis were already hand updated by the reduction and recurrence
-      // code above, leave them alone.
-      continue;
-
-    auto *IncomingValue = LCSSAPhi.getIncomingValue(0);
-    // Non-instruction incoming values will have only one value.
-
-    VPLane Lane = VPLane::getFirstLane();
-    if (isa<Instruction>(IncomingValue) &&
-        !Cost->isUniformAfterVectorization(cast<Instruction>(IncomingValue),
-                                           VF))
-      Lane = VPLane::getLastLaneForVF(VF);
-
-    // Can be a loop invariant incoming value or the last scalar value to be
-    // extracted from the vectorized loop.
-    // FIXME: Should not rely on getVPValue at this point.
-    Builder.SetInsertPoint(LoopMiddleBlock->getTerminator());
-    Value *lastIncomingValue =
-        OrigLoop->isLoopInvariant(IncomingValue)
-            ? IncomingValue
-            : State.get(State.Plan->getVPValue(IncomingValue, true),
-                        VPIteration(UF - 1, Lane));
-    LCSSAPhi.addIncoming(lastIncomingValue, LoopMiddleBlock);
-  }
-}
-
 void InnerLoopVectorizer::sinkScalarOperands(Instruction *PredInst) {
   // The basic block and loop containing the predicated instruction.
   auto *PredBB = PredInst->getParent();
   auto *VectorLoop = LI->getLoopFor(PredBB);
 
   // Initialize a worklist with the operands of the predicated instruction.
   SetVector<Value *> Worklist(PredInst->op_begin(), PredInst->op_end());
 
   // Holds instructions that we need to analyze again. An instruction may be
static void addCanonicalIVRecipes(VPlan &Plan, Type *IdxTy, DebugLoc DL,
   EB->appendRecipe(CanonicalIVIncrement);
 
   auto *BranchOnCount =
       new VPInstruction(VPInstruction::BranchOnCount,
                         {CanonicalIVIncrement, &Plan.getVectorTripCount()}, DL);
   EB->appendRecipe(BranchOnCount);
 }
 
+// Add exit values to \p Plan.
+static void
+addUsersInExitBlock(VPBasicBlock *HeaderVPBB, VPBasicBlock *MiddleVPBB,
+                    Loop *OrigLoop, VPBuilder &Builder, VPlan &Plan,
+                    SmallPtrSetImpl<Instruction *> &DeadInstructions) {
+  // First, collect VPValues for which the exit user is not modeled yet in
+  // VPlan. Those include:
+  // 1. First-order recurrences,
+  // 2. Integer, fp & pointer inductions and their increments,
+  // 3. Reduction chains.
+  SmallPtrSet<VPValue *, 8> SkipExitValues;
+  for (VPRecipeBase &R : HeaderVPBB->phis()) {
+    PHINode *Phi = nullptr;
+    if (auto *Recur = dyn_cast<VPFirstOrderRecurrencePHIRecipe>(&R)) {
+      SkipExitValues.insert(Recur);
+    } else if (auto *Ind = dyn_cast<VPWidenIntOrFpInductionRecipe>(&R)) {
+      if (Ind->getTruncInst())
+        continue;
+      Phi = Ind->getPHINode();
+    } else if (isa<VPWidenPointerInductionRecipe>(&R))
+      Phi = cast<PHINode>(R.getVPSingleValue()->getUnderlyingValue());
+    if (Phi) {
+      SkipExitValues.insert(R.getVPSingleValue());
+      auto *PostInc = Phi->getIncomingValueForBlock(OrigLoop->getLoopLatch());
+
+      if (DeadInstructions.count(cast<Instruction>(PostInc)))
+        continue;
+      SkipExitValues.insert(Plan.getVPValue(PostInc));
+    }
+
+    if (!isa<VPReductionPHIRecipe>(&R))
+      continue;
+
+    SmallVector<VPValue *> WorkList;
+    SmallPtrSet<VPValue *, 8> Visited;
+    WorkList.push_back(R.getVPSingleValue());
+
+    while (!WorkList.empty()) {
+      VPValue *V = WorkList.pop_back_val();
+
+      for (VPUser *U : V->users()) {
+        auto *VPI = dyn_cast<VPInstruction>(U);
+        auto *R = dyn_cast<VPRecipeBase>(U);
+        if (!VPI) {
+          if (R && Visited.insert(R->getVPSingleValue()).second)
+            WorkList.push_back(R->getVPSingleValue());
+          continue;
+        }
+      }
+      SkipExitValues.insert(V);
+    }
+  }
+
+  // Introduce recipes modeling the exit values. They represent LCSSA phis and
+  // must be added to the beginning of the exit/middle block.
+  Builder.setInsertPoint(MiddleVPBB, MiddleVPBB->getFirstNonPhi());
+  BasicBlock *ExitBB = OrigLoop->getUniqueExitBlock();
+  if (!ExitBB)
+    return;
+  // Only handle single-exit loops for now.
+  if (!ExitBB->getSinglePredecessor())
+    return;
+  for (PHINode &ExitPhi : ExitBB->phis()) {
+    Value *IncomingValue =
+        ExitPhi.getIncomingValueForBlock(OrigLoop->getLoopLatch());
+    VPValue *V = Plan.getOrAddVPValue(IncomingValue, true);
+    if (SkipExitValues.count(V))
+      continue;
+    Builder.createNaryOp(VPInstruction::ScalarExitValue, {V}, &ExitPhi);
+  }
+}
+
 VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
     VFRange &Range, SmallPtrSetImpl<Instruction *> &DeadInstructions,
     const MapVector<Instruction *, Instruction *> &SinkAfter) {
 
   SmallPtrSet<const InterleaveGroup<Instruction> *, 1> InterleaveGroups;
 
   VPRecipeBuilder RecipeBuilder(OrigLoop, TLI, Legal, CM, PSE, Builder);
 
VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
   HeaderVPBB->setName("vector.body");
 
   // Fold the last, empty block into its predecessor.
   VPBB = VPBlockUtils::tryToMergeBlockIntoPredecessor(VPBB);
   assert(VPBB && "expected to fold last (empty) block");
   // After here, VPBB should not be used.
   VPBB = nullptr;
 
+  addUsersInExitBlock(HeaderVPBB, MiddleVPBB, OrigLoop, Builder, *Plan,
+                      DeadInstructions);
+
   assert(isa<VPRegionBlock>(Plan->getVectorLoopRegion()) &&
          !Plan->getVectorLoopRegion()->getEntryBasicBlock()->empty() &&
          "entry block must be set to a VPRegionBlock having a non-empty entry "
          "VPBasicBlock");
   RecipeBuilder.fixHeaderPhis();
 
   // ---------------------------------------------------------------------------
   // Transform initial VPlan: Apply previously taken decisions, in order, to
   // bring the VPlan to its final state.
   // ---------------------------------------------------------------------------
 
   // Apply Sink-After legal constraints.
   auto GetReplicateRegion = [](VPRecipeBase *R) -> VPRegionBlock * {
     auto *Region = dyn_cast_or_null<VPRegionBlock>(R->getParent()->getParent());
     if (Region && Region->isReplicator()) {
       assert(Region->getNumSuccessors() == 1 &&
              Region->getNumPredecessors() == 1 && "Expected SESE region!");
       assert(R->getParent()->size() == 1 &&
              "A recipe in an original replicator region must be the only "
              "recipe in its block");
for (auto &Reduction : CM.getInLoopReductionChains()) {
     const RecurrenceDescriptor &RdxDesc =
         Legal->getReductionVars().find(Phi)->second;
     const SmallVector<Instruction *, 4> &ReductionOperations = Reduction.second;
 
     if (MinVF.isScalar() && !CM.useOrderedReductions(RdxDesc))
       continue;
 
     // ReductionOperations are orders top-down from the phi's use to the
     // LoopExitValue. We keep a track of the previous item (the Chain) to tell
     // which of the two operands will remain scalar and which will be reduced.
     // For minmax the chain will be the select instructions.
     Instruction *Chain = Phi;
     for (Instruction *R : ReductionOperations) {
       VPRecipeBase *WidenRecipe = RecipeBuilder.getRecipe(R);
       RecurKind Kind = RdxDesc.getRecurrenceKind();
 
       VPValue *ChainOp = Plan->getVPValue(Chain);
if (!VectorizeLoop) {
         // edges from the first pass.
         EPI.MainLoopVF = EPI.EpilogueVF;
         EPI.MainLoopUF = EPI.EpilogueUF;
         EpilogueVectorizerEpilogueLoop EpilogILV(L, PSE, LI, DT, TLI, TTI, AC,
                                                  ORE, EPI, &LVL, &CM, BFI, PSI,
                                                  Checks);
 
         VPlan &BestEpiPlan = LVP.getBestPlanFor(EPI.EpilogueVF);
-        BestEpiPlan.getVectorLoopRegion()->getEntryBasicBlock()->setName(
-            "vec.epilog.vector.body");
+        VPRegionBlock *VectorLoop = BestEpiPlan.getVectorLoopRegion();
+        VectorLoop->getEntryBasicBlock()->setName("vec.epilog.vector.body");
 
         // Ensure that the start values for any VPReductionPHIRecipes are
         // updated before vectorising the epilogue loop.
-        VPBasicBlock *Header =
-            BestEpiPlan.getVectorLoopRegion()->getEntryBasicBlock();
+        VPBasicBlock *Header = VectorLoop->getEntryBasicBlock();
         for (VPRecipeBase &R : Header->phis()) {
           if (auto *ReductionPhi = dyn_cast<VPReductionPHIRecipe>(&R)) {
             if (auto *Resume = MainILV.getReductionResumeValue(
                     ReductionPhi->getRecurrenceDescriptor())) {
               VPValue *StartVal = BestEpiPlan.getOrAddExternalDef(Resume);
               ReductionPhi->setOperand(0, StartVal);
             }
           }
         }
 
+        // Update exit values for LCSSA phis in the exit block for the epilogue
+        // loop.
+        VPBasicBlock *MiddleVPBB =
+            cast<VPBasicBlock>(VectorLoop->getSingleSuccessor());
+        for (VPRecipeBase &R : make_early_inc_range(*MiddleVPBB)) {
+          auto *VPI = dyn_cast<VPInstruction>(&R);
+          if (!VPI || VPI->getOpcode() != VPInstruction::ScalarExitValue)
+            continue;
+          VPI->eraseFromParent();
+        }
+        VPBuilder B;
+        SmallPtrSet<Instruction *, 4> DeadInstructions;
+        LVP.collectTriviallyDeadInstructions(DeadInstructions);
+        addUsersInExitBlock(Header, MiddleVPBB, L, B, BestEpiPlan,
+                            DeadInstructions);
+
         LVP.executePlan(EPI.EpilogueVF, EPI.EpilogueUF, BestEpiPlan, EpilogILV,
                         DT);
         ++LoopsEpilogueVectorized;
 
         if (!MainILV.areSafetyChecksAdded())
           DisableRuntimeUnroll = true;
       } else {
         InnerLoopVectorizer LB(L, PSE, LI, DT, TLI, TTI, AC, ORE, VF.Width, IC,

llvm/lib/Transforms/Vectorize/VPlan.h

 /// VPRecipeBases that also inherit from VPValue must make sure to inherit from
 /// VPRecipeBase before VPValue.
 class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock>,
                      public VPDef,
                      public VPUser {
   friend VPBasicBlock;
   friend class VPBlockUtils;
 
   /// Each VPRecipe belongs to a single VPBasicBlock.
   VPBasicBlock *Parent = nullptr;
 
 public:
   VPRecipeBase(const unsigned char SC, ArrayRef<VPValue *> Operands)
       : VPDef(SC), VPUser(Operands, VPUser::VPUserID::Recipe) {}
 
   template <typename IterT>
   VPRecipeBase(const unsigned char SC, iterator_range<IterT> Operands)
       : VPDef(SC), VPUser(Operands, VPUser::VPUserID::Recipe) {}
   virtual ~VPRecipeBase() = default;
 
   /// \return the VPBasicBlock which this VPRecipe belongs to.
   VPBasicBlock *getParent() { return Parent; }
   const VPBasicBlock *getParent() const { return Parent; }
 
enum {
     Not,
     ICmpULE,
     SLPLoad,
     SLPStore,
     ActiveLaneMask,
     CanonicalIVIncrement,
     CanonicalIVIncrementNUW,
     BranchOnCount,
+    ScalarExitValue,
   };
 
 private:
   typedef unsigned char OpcodeTy;
   OpcodeTy Opcode;
   FastMathFlags FMF;
   DebugLoc DL;
 
bool onlyFirstLaneUsed(const VPValue *Op) const override {
     case VPInstruction::ActiveLaneMask:
     case VPInstruction::CanonicalIVIncrement:
     case VPInstruction::CanonicalIVIncrementNUW:
     case VPInstruction::BranchOnCount:
       return true;
     };
     llvm_unreachable("switch should return");
   }
+
+  /// Returns true if the recipe uses scalars of operand \p Op.
+  bool usesScalars(const VPValue *Op) const override {
+    assert(is_contained(operands(), Op) &&
+           "Op must be an operand of the recipe");
+    switch (getOpcode()) {
+    default:
+      return onlyFirstLaneUsed(Op);
+    case VPInstruction::ScalarExitValue:
+      return true;
+    };
+    llvm_unreachable("switch should return");
+  }
 };
 
 /// VPWidenRecipe is a recipe for producing a copy of vector type its
 /// ingredient. This recipe covers most of the traditional vectorization cases
 /// where each ingredient transforms into a vectorized version of itself.
 class VPWidenRecipe : public VPRecipeBase, public VPValue {
 public:
   template <typename IterT>
public:
   VPlan(VPBlockBase *Entry = nullptr) : Entry(Entry) {
     if (Entry)
       Entry->setPlan(this);
   }
 
   ~VPlan() {
     if (Entry) {
       VPValue DummyValue;
       for (VPBlockBase *Block : depth_first(Entry))
         Block->dropAllReferences(&DummyValue);
 
       VPBlockBase::deleteCFG(Entry);
     }
     for (VPValue *VPV : VPValuesToFree)
       delete VPV;
     if (TripCount)
       delete TripCount;
public:
   /// OverrideAllowed can be used to disable checking whether it is safe to
   /// query VPValues using IR Values.
   VPValue *getOrAddVPValue(Value *V, bool OverrideAllowed = false) {
     assert((OverrideAllowed || isa<Constant>(V) || Value2VPValueEnabled) &&
            "Value2VPValue mapping may be out of date!");
     assert(V && "Trying to get or add the VPValue of a null Value");
     if (!Value2VPValue.count(V))
       addVPValue(V);
-    return getVPValue(V);
+    return getVPValue(V, OverrideAllowed);
   }
 
   void removeVPValueFor(Value *V) {
     assert(Value2VPValueEnabled &&
            "IR value to VPValue mapping may be out of date!");
     Value2VPValue.erase(V);
   }
 

llvm/lib/Transforms/Vectorize/VPlan.cpp

auto IsLoopRegion = [](VPBlockBase *BB) {
     return R && !R->isReplicator();
   };
 
   // 1. Create an IR basic block, or reuse the last one or ExitBB if possible.
   if (getPlan()->getVectorLoopRegion()->getSingleSuccessor() == this) {
     // ExitBB can be re-used for the exit block of the Plan.
     NewBB = State->CFG.ExitBB;
     State->CFG.PrevBB = NewBB;
+    State->Builder.SetInsertPoint(NewBB, NewBB->begin());
   } else if (PrevVPBB && /* A */
              !((SingleHPred = getSingleHierarchicalPredecessor()) &&
                SingleHPred->getExitBasicBlock() == PrevVPBB &&
                PrevVPBB->getSingleHierarchicalSuccessor() &&
                (SingleHPred->getParent() == getEnclosingLoopRegion() &&
                 !IsLoopRegion(SingleHPred))) &&         /* B */
              !(Replica && getPredecessors().empty())) { /* C */
     // The last IR basic block is reused, as an optimization, in three cases:
case VPReplicateSC: {
     return R->getUnderlyingInstr()->mayHaveSideEffects();
   }
   default:
     return true;
   }
 }
 
 void VPRecipeBase::insertBefore(VPRecipeBase *InsertPos) {
   assert(!Parent && "Recipe already in some VPBasicBlock");
   assert(InsertPos->getParent() &&
          "Insertion position not in any VPBasicBlock");
   Parent = InsertPos->getParent();
   Parent->getRecipeList().insert(InsertPos->getIterator(), this);
 }
 
 void VPRecipeBase::insertBefore(VPBasicBlock &BB,
                                 iplist<VPRecipeBase>::iterator I) {
case VPInstruction::BranchOnCount: {
     // TODO: Once the exit block is modeled in VPlan, use it instead of going
     // through State.CFG.ExitBB.
     BasicBlock *Exit = State.CFG.ExitBB;
 
     Builder.CreateCondBr(Cond, Exit, State.CFG.VPBB2IRBB[Header]);
     Builder.GetInsertBlock()->getTerminator()->eraseFromParent();
     break;
   }
+  case VPInstruction::ScalarExitValue: {
+    if (Part != 0)
+      break;
+    PHINode *ExitPhi = cast<PHINode>(getUnderlyingValue());
+    auto Lane = VPLane::getLastLaneForVF(State.VF);
+    if (getParent()->getPlan()->isUniformAfterVectorization(getOperand(0)))
+      Lane = VPLane::getFirstLane();
+    ExitPhi->addIncoming(
+        State.get(getOperand(0), VPIteration(State.UF - 1, Lane)),
+        State.CFG.VPBB2IRBB[getParent()]);
+    break;
+  }
   default:
     llvm_unreachable("Unsupported opcode for instruction");
   }
 }
 
 void VPInstruction::execute(VPTransformState &State) {
   assert(!State.Instance && "VPInstruction executing an Instance");
   IRBuilderBase::FastMathFlagGuard FMFGuard(State.Builder);
case VPInstruction::CanonicalIVIncrement:
     O << "VF * UF + ";
     break;
   case VPInstruction::CanonicalIVIncrementNUW:
     O << "VF * UF +(nuw) ";
     break;
   case VPInstruction::BranchOnCount:
     O << "branch-on-count ";
     break;
+  case VPInstruction::ScalarExitValue:
+    O << "scalar-exit-value ";
+    break;
   default:
     O << Instruction::getOpcodeName(getOpcode());
   }
 
   O << FMF;
 
   for (const VPValue *Operand : operands()) {
     O << " ";
void VPlan::execute(VPTransformState *State) {
 
   // We do not attempt to preserve DT for outer loop vectorization currently.
   if (!EnableVPlanNativePath) {
     BasicBlock *VectorHeaderBB = State->CFG.VPBB2IRBB[Header];
     State->DT->addNewBlock(VectorHeaderBB, VectorPreHeader);
     updateDominatorTree(State->DT, VectorHeaderBB, VectorLatchBB,
                         State->CFG.ExitBB);
   }
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD
 void VPlan::print(raw_ostream &O) const {
   VPSlotTracker SlotTracker(this);
 
   O << "VPlan '" << Name << "' {";
 
void VPlan::print(raw_ostream &O) const {
   for (const VPBlockBase *Block : depth_first(getEntry())) {
     O << '\n';
     Block->print(O, "", SlotTracker);
   }
   O << "}\n";
 }
 
 LLVM_DUMP_METHOD
 void VPlan::printDOT(raw_ostream &O) const {
   VPlanPrinter Printer(O, *this);
   Printer.dump();
 }
 
 LLVM_DUMP_METHOD
 void VPlan::dump() const { print(dbgs()); }
 #endif
 
 void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopHeaderBB,
                                 BasicBlock *LoopLatchBB,
                                 BasicBlock *LoopExitBB) {
   // The vector body may be more than a single basic-block by this point.
   // Update the dominator tree information inside the vector body by propagating
   // it from header to latch, expecting only triangular control-flow, if any.
   BasicBlock *PostDomSucc = nullptr;
   for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
     // Get the list of successors of this block.
     std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));

llvm/test/Transforms/LoopVectorize/AArch64/scalable-avoid-scalarization.ll

 ; CHECK-NEXT:    [[WIDE_LOAD:%.*]] = load <vscale x 2 x double>, <vscale x 2 x double>* [[TMP16]], align 8
 ; CHECK-NEXT:    [[TMP17:%.*]] = call i32 @llvm.vscale.i32()
 ; CHECK-NEXT:    [[TMP18:%.*]] = mul i32 [[TMP17]], 2
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i32 [[INDEX]], [[TMP18]]
 ; CHECK-NEXT:    [[VEC_IND_NEXT]] = add <vscale x 2 x i32> [[VEC_IND]], [[DOTSPLAT2]]
 ; CHECK-NEXT:    [[TMP19:%.*]] = icmp eq i32 [[INDEX_NEXT]], [[N_VEC]]
 ; CHECK-NEXT:    br i1 [[TMP19]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP0:![0-9]+]]
 ; CHECK:       middle.block:
-; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i32 [[TMP1]], [[N_VEC]]
 ; CHECK-NEXT:    [[TMP20:%.*]] = call i32 @llvm.vscale.i32()
 ; CHECK-NEXT:    [[TMP21:%.*]] = mul i32 [[TMP20]], 2
 ; CHECK-NEXT:    [[TMP22:%.*]] = sub i32 [[TMP21]], 1
 ; CHECK-NEXT:    [[TMP23:%.*]] = extractelement <vscale x 2 x i64*> [[TMP12]], i32 [[TMP22]]
+; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i32 [[TMP1]], [[N_VEC]]
 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[L_EXIT:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i32 [ [[IND_END]], [[MIDDLE_BLOCK]] ], [ [[IDX]], [[L_ENTRY:%.*]] ]
 ; CHECK-NEXT:    br label [[L_LOOPBODY:%.*]]
 ; CHECK:       L.LoopBody:
 ; CHECK-NEXT:    [[INDVAR:%.*]] = phi i32 [ [[INDVAR_NEXT:%.*]], [[L_LOOPBODY]] ], [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ]
 ; CHECK-NEXT:    [[INDVAR_NEXT]] = add nsw i32 [[INDVAR]], 1
 ; CHECK-NEXT:    [[TMP24:%.*]] = getelementptr i64, i64* [[A]], i32 [[INDVAR]]

llvm/test/Transforms/LoopVectorize/X86/invariant-load-gather.ll

 ; CHECK-NEXT:    store <16 x i32> [[BROADCAST_SPLAT9]], <16 x i32>* [[TMP1]], align 4, !alias.scope !0, !noalias !3
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 16
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
 ; CHECK-NEXT:    br i1 [[TMP2]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP5:![0-9]+]]
 ; CHECK:       middle.block:
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne <16 x i32*> [[BROADCAST_SPLAT]], zeroinitializer
 ; CHECK-NEXT:    [[WIDE_MASKED_GATHER:%.*]] = call <16 x i32> @llvm.masked.gather.v16i32.v16p0i32(<16 x i32*> [[BROADCAST_SPLAT]], i32 4, <16 x i1> [[TMP3]], <16 x i32> undef), !alias.scope !3
 ; CHECK-NEXT:    [[PREDPHI:%.*]] = select <16 x i1> [[TMP3]], <16 x i32> [[WIDE_MASKED_GATHER]], <16 x i32> <i32 poison, i32 poison, i32 poison, i32 poison, i32 poison, i32 poison, i32 poison, i32 poison, i32 poison, i32 poison, i32 poison, i32 poison, i32 poison, i32 poison, i32 poison, i32 1>
-; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 [[SMAX6]], [[N_VEC]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = extractelement <16 x i32> [[PREDPHI]], i64 15
+; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 [[SMAX6]], [[N_VEC]]
 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[FOR_END:%.*]], label [[VEC_EPILOG_ITER_CHECK:%.*]]
 ; CHECK:       vec.epilog.iter.check:
 ; CHECK-NEXT:    [[N_VEC_REMAINING:%.*]] = and i64 [[SMAX6]], 8
 ; CHECK-NEXT:    [[MIN_EPILOG_ITERS_CHECK_NOT_NOT:%.*]] = icmp eq i64 [[N_VEC_REMAINING]], 0
 ; CHECK-NEXT:    br i1 [[MIN_EPILOG_ITERS_CHECK_NOT_NOT]], label [[VEC_EPILOG_SCALAR_PH]], label [[VEC_EPILOG_PH]]
 ; CHECK:       vec.epilog.ph:
 ; CHECK-NEXT:    [[VEC_EPILOG_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[VEC_EPILOG_ITER_CHECK]] ], [ 0, [[VECTOR_MAIN_LOOP_ITER_CHECK]] ]
 ; CHECK-NEXT:    [[N_VEC13:%.*]] = and i64 [[SMAX6]], 9223372036854775800

 ; CHECK-NEXT:    store <8 x i32> [[BROADCAST_SPLAT20]], <8 x i32>* [[TMP6]], align 4
 ; CHECK-NEXT:    [[INDEX_NEXT23]] = add nuw i64 [[OFFSET_IDX]], 8
 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i64 [[INDEX_NEXT23]], [[N_VEC13]]
 ; CHECK-NEXT:    br i1 [[TMP7]], label [[VEC_EPILOG_MIDDLE_BLOCK:%.*]], label [[VEC_EPILOG_VECTOR_BODY]], !llvm.loop [[LOOP7:![0-9]+]]
 ; CHECK:       vec.epilog.middle.block:
 ; CHECK-NEXT:    [[TMP8:%.*]] = icmp ne <8 x i32*> [[BROADCAST_SPLAT18]], zeroinitializer
 ; CHECK-NEXT:    [[WIDE_MASKED_GATHER21:%.*]] = call <8 x i32> @llvm.masked.gather.v8i32.v8p0i32(<8 x i32*> [[BROADCAST_SPLAT18]], i32 4, <8 x i1> [[TMP8]], <8 x i32> undef)
 ; CHECK-NEXT:    [[PREDPHI22:%.*]] = select <8 x i1> [[TMP8]], <8 x i32> [[WIDE_MASKED_GATHER21]], <8 x i32> <i32 poison, i32 poison, i32 poison, i32 poison, i32 poison, i32 poison, i32 poison, i32 1>
-; CHECK-NEXT:    [[CMP_N14:%.*]] = icmp eq i64 [[SMAX6]], [[N_VEC13]]
 ; CHECK-NEXT:    [[TMP9:%.*]] = extractelement <8 x i32> [[PREDPHI22]], i64 7
+; CHECK-NEXT:    [[CMP_N14:%.*]] = icmp eq i64 [[SMAX6]], [[N_VEC13]]
 ; CHECK-NEXT:    br i1 [[CMP_N14]], label [[FOR_END_LOOPEXIT:%.*]], label [[VEC_EPILOG_SCALAR_PH]]
 ; CHECK:       vec.epilog.scalar.ph:
 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC13]], [[VEC_EPILOG_MIDDLE_BLOCK]] ], [ [[N_VEC]], [[VEC_EPILOG_ITER_CHECK]] ], [ 0, [[VECTOR_MEMCHECK]] ], [ 0, [[ITER_CHECK:%.*]] ]
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_NEXT:%.*]], [[LATCH:%.*]] ], [ [[BC_RESUME_VAL]], [[VEC_EPILOG_SCALAR_PH]] ]
 ; CHECK-NEXT:    [[I1:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[I]]
 ; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32* [[A]], null

llvm/test/Transforms/LoopVectorize/X86/pr51366-sunk-instruction-used-outside-of-loop.ll

+; RUN: opt -passes=loop-vectorize -mtriple=x86_64-unknown-linux -force-vector-width=2 -force-vector-interleave=1 -S %s | FileCheck %s
+
+define i32* @test(i32* noalias %src, i32* noalias %dst) {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  entry:
+; CHECK:       vector.body:
+; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %vector.ph ], [ [[INDEX_NEXT:%.*]], [[PRED_LOAD_CONTINUE2:%.*]] ]
+; CHECK-NEXT:    [[VEC_IND:%.*]] = phi <2 x i64> [ <i64 0, i64 1>, %vector.ph ], [ [[VEC_IND_NEXT:%.*]], [[PRED_LOAD_CONTINUE2]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[INDEX]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[INDEX]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i32, i32* [[SRC:%.*]], i64 [[TMP1]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq <2 x i64> [[VEC_IND]], zeroinitializer
+; CHECK-NEXT:    [[TMP4:%.*]] = xor <2 x i1> [[TMP3]], <i1 true, i1 true>
+; CHECK-NEXT:    [[TMP5:%.*]] = extractelement <2 x i1> [[TMP4]], i32 0
+; CHECK-NEXT:    br i1 [[TMP5]], label [[PRED_LOAD_IF:%.*]], label [[PRED_LOAD_CONTINUE:%.*]]
+; CHECK:       pred.load.if:
+; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds i32, i32* [[SRC]], i64 [[TMP0]]
+; CHECK-NEXT:    [[TMP7:%.*]] = load i32, i32* [[TMP6]], align 4
+; CHECK-NEXT:    [[TMP8:%.*]] = insertelement <2 x i32> poison, i32 [[TMP7]], i32 0
+; CHECK-NEXT:    br label [[PRED_LOAD_CONTINUE]]
+; CHECK:       pred.load.continue:
+; CHECK-NEXT:    [[TMP9:%.*]] = phi <2 x i32> [ poison, %vector.body ], [ [[TMP8]], [[PRED_LOAD_IF]] ]
+; CHECK-NEXT:    [[TMP10:%.*]] = extractelement <2 x i1> [[TMP4]], i32 1
+; CHECK-NEXT:    br i1 [[TMP10]], label [[PRED_LOAD_IF1:%.*]], label [[PRED_LOAD_CONTINUE2]]
+; CHECK:       pred.load.if1:
+; CHECK-NEXT:    [[TMP11:%.*]] = load i32, i32* [[TMP2]], align 4
+; CHECK-NEXT:    [[TMP12:%.*]] = insertelement <2 x i32> [[TMP9]], i32 [[TMP11]], i32 1
+; CHECK-NEXT:    br label [[PRED_LOAD_CONTINUE2]]
+; CHECK:       pred.load.continue2:
+; CHECK-NEXT:    [[TMP13:%.*]] = phi <2 x i32> [ [[TMP9]], [[PRED_LOAD_CONTINUE]] ], [ [[TMP12]], [[PRED_LOAD_IF1]] ]
+; CHECK-NEXT:    [[PREDPHI:%.*]] = select <2 x i1> [[TMP3]], <2 x i32> zeroinitializer, <2 x i32> [[TMP13]]
+; CHECK-NEXT:    [[TMP14:%.*]] = getelementptr inbounds i32, i32* [[DST:%.*]], i64 [[TMP0]]
+; CHECK-NEXT:    [[TMP15:%.*]] = getelementptr inbounds i32, i32* [[TMP14]], i32 0
+; CHECK-NEXT:    [[TMP16:%.*]] = bitcast i32* [[TMP15]] to <2 x i32>*
+; CHECK-NEXT:    store <2 x i32> [[PREDPHI]], <2 x i32>* [[TMP16]], align 4
+; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 2
+; CHECK-NEXT:    [[VEC_IND_NEXT]] = add <2 x i64> [[VEC_IND]], <i64 2, i64 2>
+; CHECK-NEXT:    [[TMP17:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000
+; CHECK-NEXT:    br i1 [[TMP17]], label [[MIDDLE_BLOCK:%.*]], label %vector.body
+; CHECK:       middle.block:
+; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 1000, 1000
+; CHECK-NEXT:    br i1 [[CMP_N]], label %exit, label %scalar.ph
+; CHECK:       exit:
+; CHECK-NEXT:    [[GEP_LCSSA:%.*]] = phi i32* [ %gep.src, %loop.latch ], [ [[TMP2]], %middle.block ]
+; CHECK-NEXT:    ret i32* [[GEP_LCSSA]]
+;
+entry:
+  br label %loop.header
+
+loop.header:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
+  %gep.src = getelementptr inbounds i32, i32* %src, i64 %iv
+  %cmp.1 = icmp eq i64 %iv, 0
+  br i1 %cmp.1, label %loop.latch, label %then
+
+then:
+  %l = load i32, i32* %gep.src, align 4
+  br label %loop.latch
+
+loop.latch:
+  %m = phi i32 [ %l, %then ], [ 0, %loop.header ]
+  %gep.dst = getelementptr inbounds i32, i32* %dst, i64 %iv
+  store i32 %m, i32* %gep.dst, align 4
+  %iv.next = add nsw i64 %iv, 1
+  %cmp.2 = icmp slt i64 %iv.next, 1000
+  br i1 %cmp.2, label %loop.header, label %exit
+
+exit:
+  %gep.lcssa = phi i32* [ %gep.src, %loop.latch ]
+  ret i32* %gep.lcssa
+}

llvm/test/Transforms/LoopVectorize/extract-last-veclane.ll

 ; CHECK-NEXT:    [[TMP2:%.*]] = shl nsw <4 x i32> [[WIDE_LOAD]], <i32 1, i32 1, i32 1, i32 1>
 ; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i64 [[INDEX]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = bitcast i32* [[TMP3]] to <4 x i32>*
 ; CHECK-NEXT:    store <4 x i32> [[TMP2]], <4 x i32>* [[TMP4]], align 4
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
 ; CHECK-NEXT:    br i1 [[TMP5]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP0:![0-9]+]]
 ; CHECK:       middle.block:
-; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 [[N_VEC]], [[N]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = extractelement <4 x i32> [[TMP2]], i64 3
+; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 [[N_VEC]], [[N]]
 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[EXIT:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[INDVARS_IV]]
 ; CHECK-NEXT:    [[TMP7:%.*]] = load i32, i32* [[ARRAYIDX]], align 4

 ; CHECK-NEXT:    [[TMP2:%.*]] = fmul <4 x float> [[WIDE_LOAD]], <float 2.000000e+00, float 2.000000e+00, float 2.000000e+00, float 2.000000e+00>
 ; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds float, float* [[A:%.*]], i64 [[INDEX]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = bitcast float* [[TMP3]] to <4 x float>*
 ; CHECK-NEXT:    store <4 x float> [[TMP2]], <4 x float>* [[TMP4]], align 4
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
 ; CHECK-NEXT:    br i1 [[TMP5]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP4:![0-9]+]]
 ; CHECK:       middle.block:
-; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 [[N_VEC]], [[N]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = extractelement <4 x float> [[TMP2]], i64 3
+; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 [[N_VEC]], [[N]]
 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[EXIT:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds float, float* [[B]], i64 [[INDVARS_IV]]
 ; CHECK-NEXT:    [[TMP7:%.*]] = load float, float* [[ARRAYIDX]], align 4

llvm/test/Transforms/LoopVectorize/instruction-only-used-outside-of-loop.ll

 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i32, i32* [[TMP1]], i32 0
 ; CHECK-NEXT:    [[TMP3:%.*]] = bitcast i32* [[TMP2]] to <4 x i32>*
 ; CHECK-NEXT:    [[WIDE_LOAD:%.*]] = load <4 x i32>, <4 x i32>* [[TMP3]], align 4
 ; CHECK-NEXT:    [[TMP4:%.*]] = xor <4 x i32> <i32 25500, i32 25500, i32 25500, i32 25500>, [[WIDE_LOAD]]
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i32 [[INDEX]], 4
 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i32 [[INDEX_NEXT]], 0
 ; CHECK-NEXT:    br i1 [[TMP5]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP0:![0-9]+]]
 ; CHECK:       middle.block:
-; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i32 0, 0
 ; CHECK-NEXT:    [[TMP6:%.*]] = extractelement <4 x i32> [[TMP4]], i32 3
+; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i32 0, 0
 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[EXIT:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i32 [ 0, [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
 ; CHECK-NEXT:    [[SRC_GEP:%.*]] = getelementptr inbounds i32, i32* [[SRC]], i32 [[IV]]
 ; CHECK-NEXT:    [[LV:%.*]] = load i32, i32* [[SRC_GEP]], align 4

 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i32, i32* [[TMP1]], i32 0
 ; CHECK-NEXT:    [[TMP3:%.*]] = bitcast i32* [[TMP2]] to <4 x i32>*
 ; CHECK-NEXT:    [[WIDE_LOAD:%.*]] = load <4 x i32>, <4 x i32>* [[TMP3]], align 4
 ; CHECK-NEXT:    [[TMP4:%.*]] = xor <4 x i32> <i32 25500, i32 25500, i32 25500, i32 25500>, [[WIDE_LOAD]]
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i32 [[INDEX]], 4
 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i32 [[INDEX_NEXT]], 0
 ; CHECK-NEXT:    br i1 [[TMP5]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP4:![0-9]+]]
 ; CHECK:       middle.block:
-; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i32 0, 0
 ; CHECK-NEXT:    [[TMP6:%.*]] = extractelement <4 x i32> [[TMP4]], i32 3
+; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i32 0, 0
 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[EXIT:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i32 [ 0, [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
 ; CHECK-NEXT:    [[SRC_GEP:%.*]] = getelementptr inbounds i32, i32* [[SRC]], i32 [[IV]]
 ; CHECK-NEXT:    [[LV:%.*]] = load i32, i32* [[SRC_GEP]], align 4

 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp ne <4 x i32> [[VEC_IND]], [[BROADCAST_SPLAT]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = xor <4 x i1> [[TMP5]], <i1 true, i1 true, i1 true, i1 true>
 ; CHECK-NEXT:    [[PREDPHI:%.*]] = select <4 x i1> [[TMP6]], <4 x i32> <i32 10, i32 10, i32 10, i32 10>, <4 x i32> [[TMP4]]
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i32 [[INDEX]], 4
 ; CHECK-NEXT:    [[VEC_IND_NEXT]] = add <4 x i32> [[VEC_IND]], <i32 4, i32 4, i32 4, i32 4>
 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i32 [[INDEX_NEXT]], 0
 ; CHECK-NEXT:    br i1 [[TMP7]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP6:![0-9]+]]
 ; CHECK:       middle.block:
-; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i32 0, 0
 ; CHECK-NEXT:    [[TMP8:%.*]] = extractelement <4 x i32> [[PREDPHI]], i32 3
+; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i32 0, 0
 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[EXIT:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i32 [ 0, [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
 ; CHECK-NEXT:    [[SRC_GEP:%.*]] = getelementptr inbounds i32, i32* [[SRC]], i32 [[IV]]
 ; CHECK-NEXT:    [[LV:%.*]] = load i32, i32* [[SRC_GEP]], align 4

 ; CHECK:       vector.body:
 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
 ; CHECK-NEXT:    [[VEC_IND:%.*]] = phi <4 x i32> [ <i32 0, i32 1, i32 2, i32 3>, [[VECTOR_PH]] ], [ [[VEC_IND_NEXT:%.*]], [[VECTOR_BODY]] ]
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 ; CHECK-NEXT:    [[VEC_IND_NEXT]] = add <4 x i32> [[VEC_IND]], <i32 4, i32 4, i32 4, i32 4>
 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000
 ; CHECK-NEXT:    br i1 [[TMP0]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP8:![0-9]+]]
 ; CHECK:       middle.block:
-; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 1000, 1000
 ; CHECK-NEXT:    [[TMP1:%.*]] = extractelement <4 x i32> [[VEC_IND]], i32 3
+; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 1000, 1000
 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[EXIT:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ 1000, [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[IV_TRUNC:%.*]] = trunc i64 [[IV]] to i32
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1

llvm/test/Transforms/LoopVectorize/optimal-epilog-vectorization-liveout.ll

 ; VF-TWO-CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds i32, i32* [[TMP4]], i32 0
 ; VF-TWO-CHECK-NEXT:    [[TMP6:%.*]] = bitcast i32* [[TMP5]] to <2 x i32>*
 ; VF-TWO-CHECK-NEXT:    [[WIDE_LOAD2:%.*]] = load <2 x i32>, <2 x i32>* [[TMP6]], align 4
 ; VF-TWO-CHECK-NEXT:    [[TMP7:%.*]] = add nsw <2 x i32> [[WIDE_LOAD]], [[WIDE_LOAD2]]
 ; VF-TWO-CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 2
 ; VF-TWO-CHECK-NEXT:    [[TMP8:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
 ; VF-TWO-CHECK-NEXT:    br i1 [[TMP8]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], [[LOOP0:!llvm.loop !.*]]
 ; VF-TWO-CHECK:       middle.block:
-; VF-TWO-CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 [[WIDE_TRIP_COUNT]], [[N_VEC]]
 ; VF-TWO-CHECK-NEXT:    [[TMP9:%.*]] = extractelement <2 x i32> [[TMP7]], i32 1
+; VF-TWO-CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 [[WIDE_TRIP_COUNT]], [[N_VEC]]
 ; VF-TWO-CHECK-NEXT:    br i1 [[CMP_N]], label [[FOR_END_LOOPEXIT:%.*]], label [[VEC_EPILOG_ITER_CHECK:%.*]]
 ; VF-TWO-CHECK:       vec.epilog.iter.check:
 ; VF-TWO-CHECK-NEXT:    [[N_VEC_REMAINING:%.*]] = sub i64 [[WIDE_TRIP_COUNT]], [[N_VEC]]
 ; VF-TWO-CHECK-NEXT:    [[MIN_EPILOG_ITERS_CHECK:%.*]] = icmp ult i64 [[N_VEC_REMAINING]], 2
 ; VF-TWO-CHECK-NEXT:    br i1 [[MIN_EPILOG_ITERS_CHECK]], label [[VEC_EPILOG_SCALAR_PH]], label [[VEC_EPILOG_PH]]
 ; VF-TWO-CHECK:       vec.epilog.ph:
 ; VF-TWO-CHECK-NEXT:    [[VEC_EPILOG_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[VEC_EPILOG_ITER_CHECK]] ], [ 0, [[VECTOR_MAIN_LOOP_ITER_CHECK]] ]
 ; VF-TWO-CHECK-NEXT:    [[N_MOD_VF4:%.*]] = urem i64 [[WIDE_TRIP_COUNT]], 2

 ; VF-TWO-CHECK-NEXT:    [[TMP15:%.*]] = getelementptr inbounds i32, i32* [[TMP14]], i32 0
 ; VF-TWO-CHECK-NEXT:    [[TMP16:%.*]] = bitcast i32* [[TMP15]] to <2 x i32>*
 ; VF-TWO-CHECK-NEXT:    [[WIDE_LOAD10:%.*]] = load <2 x i32>, <2 x i32>* [[TMP16]], align 4
 ; VF-TWO-CHECK-NEXT:    [[TMP17:%.*]] = add nsw <2 x i32> [[WIDE_LOAD9]], [[WIDE_LOAD10]]
 ; VF-TWO-CHECK-NEXT:    [[INDEX_NEXT7]] = add nuw i64 [[INDEX6]], 2
 ; VF-TWO-CHECK-NEXT:    [[TMP18:%.*]] = icmp eq i64 [[INDEX_NEXT7]], [[N_VEC5]]
 ; VF-TWO-CHECK-NEXT:    br i1 [[TMP18]], label [[VEC_EPILOG_MIDDLE_BLOCK:%.*]], label [[VEC_EPILOG_VECTOR_BODY]], [[LOOP2:!llvm.loop !.*]]
 ; VF-TWO-CHECK:       vec.epilog.middle.block:
-; VF-TWO-CHECK-NEXT:    [[CMP_N8:%.*]] = icmp eq i64 [[WIDE_TRIP_COUNT]], [[N_VEC5]]
 ; VF-TWO-CHECK-NEXT:    [[TMP19:%.*]] = extractelement <2 x i32> [[TMP17]], i32 1
+; VF-TWO-CHECK-NEXT:    [[CMP_N8:%.*]] = icmp eq i64 [[WIDE_TRIP_COUNT]], [[N_VEC5]]
 ; VF-TWO-CHECK-NEXT:    br i1 [[CMP_N8]], label [[FOR_END_LOOPEXIT_LOOPEXIT:%.*]], label [[VEC_EPILOG_SCALAR_PH]]
 ; VF-TWO-CHECK:       vec.epilog.scalar.ph:
 ; VF-TWO-CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC5]], [[VEC_EPILOG_MIDDLE_BLOCK]] ], [ [[N_VEC]], [[VEC_EPILOG_ITER_CHECK]] ], [ 0, [[ITER_CHECK]] ]
 ; VF-TWO-CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; VF-TWO-CHECK:       for.body:
 ; VF-TWO-CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[VEC_EPILOG_SCALAR_PH]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
 ; VF-TWO-CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[A]], i64 [[INDVARS_IV]]
 ; VF-TWO-CHECK-NEXT:    [[TMP20:%.*]] = load i32, i32* [[ARRAYIDX]], align 4