[LV] Generate RT checks up-front and remove them if required.

[fhahn]

Summary

This patch updates LV to generate the runtime checks just after cost
modeling, to allow a more precise estimate of the actual cost of the
checks. This information will be used in future patches to generate
larger runtime checks in cases where the checks only make up a small
fraction of the expected scalar loop execution time.

The runtime checks are created up-front in a temporary block to allow better
estimating the cost and un-linked from the existing IR. After deciding to
vectorize, the checks are moved backed. If deciding not to vectorize, the
temporary block is completely removed.

This patch is similar in spirit to D71053, but explores a different
direction: instead of delaying the decision on whether to vectorize in
the presence of runtime checks it instead optimistically creates the
runtime checks early and discards them later if decided to not
vectorize. This has the advantage that the cost-modeling decisions
can be kept together and can be done up-front and thus preserving the
general code structure. I think delaying (part) of the decision to
vectorize would also make the VPlan migration a bit harder.

One potential drawback of this patch is that we speculatively
generate IR which we might have to clean up later. However it seems like
the code required to do so is quite manageable.

[lebedev.ri]

Thank you for looking into this!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

1887

'moved backed'?

[lebedev.ri]

Reverse-ping. Can i somehow help get this going? :)

One potential drawback of this patch is that we speculatively
generate IR which we might have to clean up later. However it seems like
the code required to do so is quite manageable.

There's prior art for that, loop idiom pass has ExpandedValuesCleaner e.g.

[fhahn]

In D75980#2164971, @lebedev.ri wrote:

Reverse-ping. Can i somehow help get this going? :)

I actually started rebasing/updating over the weekend. There are a few more loose ends to tie up, but I should be able to share an update in the next few days.

One potential drawback of this patch is that we speculatively
generate IR which we might have to clean up later. However it seems like
the code required to do so is quite manageable.

There's prior art for that, loop idiom pass has ExpandedValuesCleaner e.g.

Yes, part of the update is to fix SCEVExpander to actually collect all instructions it generates automatically, so they can be cleaned up later. It already does so for some instructions, but is missing a ton of cases.

[lebedev.ri]

In D75980#2165028, @fhahn wrote:

In D75980#2164971, @lebedev.ri wrote:

Reverse-ping. Can i somehow help get this going? :)

I actually started rebasing/updating over the weekend. There are a few more loose ends to tie up, but I should be able to share an update in the next few days.

One potential drawback of this patch is that we speculatively
generate IR which we might have to clean up later. However it seems like
the code required to do so is quite manageable.

There's prior art for that, loop idiom pass has ExpandedValuesCleaner e.g.

Yes, part of the update is to fix SCEVExpander to actually collect all instructions it generates automatically, so they can be cleaned up later. It already does so for some instructions, but is missing a ton of cases.

Without looking at how it would look, i would imagine that can be cleaned by supplying a callback to the builder, that would automatically put each new instruction into some vector.
Let me know if that is the right direction and if it would be helpful for me to look into that (unless you're halfway there of course)

[ebrevnov]

I'm glad to see this discussion alive again. Thanks Roman!

I think the topic deserves a dedicated discussion on dev list in a wider audience because it is not trivial one.

In fact I have an experience of doing similar thing in SLP and it was mainly negative. Things look simple in the beginning and we went ahead and implemented this approach. The problem was that over the time it became hard to manage pre-generated instructions correctly and we started having nasty bugs. Everything is simple until you don't have sharing. If you have references from multiple places (both from inside IR and internal data structures) things become complex and error prone. I would not like to go this direction again until we 1000% sure things will remain simple.

One more thing is concerning me in this particular implementation. I think the way we are trying to "hide" Checks.TmpBlock from all global analysis and data structures is fragile and can be source of bugs in future. In my opinion it would be much easier and cleaner to make pre-generated code runtime dead (by changing guarding condition to be unconditionally false) and let dedicated cleanup passes make their job.

[fhahn]

In D75980#2165968, @ebrevnov wrote:

I think the topic deserves a dedicated discussion on dev list in a wider audience because it is not trivial one.

Agreed, it would be good to make sure there are no major objections on the general approach. We already have a few cases of 'prior art' in the code base, but this patch might take things a little further than in some other places.

In fact I have an experience of doing similar thing in SLP and it was mainly negative. Things look simple in the beginning and we went ahead and implemented this approach. The problem was that over the time it became hard to manage pre-generated instructions correctly and we started having nasty bugs. Everything is simple until you don't have sharing. If you have references from multiple places (both from inside IR and internal data structures) things become complex and error prone. I would not like to go this direction again until we 1000% sure things will remain simple.

From what I've seen so far, the major concerns is around SCEV expansion. I started some patches solidifying the way we clean up after SCEV expansion (D84327), which is already done in LoopIdiomRecognize. I think we need to properly address this first, before continuing here.

I am not too concerned about interactions with other LV internal data structures, as the runtime checks are pretty independent of vector code generation/legality, as they are outside of the loop and nothing in the vector loop should be aware of the checks.

One more thing is concerning me in this particular implementation. I think the way we are trying to "hide" Checks.TmpBlock from all global analysis and data structures is fragile and can be source of bugs in future. In my opinion it would be much easier and cleaner to make pre-generated code runtime dead (by changing guarding condition to be unconditionally false) and let dedicated cleanup passes make their job.

That's an interesting suggestion and would certainly simplify things. My main concern with leaving cleanup to another pass is that it would mean that LV would always modify functions with loops that need runtime checks, even if the checks are not used. Not sure how big of an issue that would be in terms of compile-time caused by the additional invalidations.

[lebedev.ri]

It would be helpful if you could add prerequisite patches are parents of this patch.
What else needs to be done before this?

[fhahn]

rebase

[lebedev.ri]

I approve of the general direction of this patch series :)
Some high-level notes. I'm not that familiar with the code in question,
so it will be best for someone else to review, too.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

2699–2701

Should this go into a separate patch? Is this a preexisting problem?

2704–2709

Are these two assertions not identical?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

919

s/they/vectorization/

1951

I'm guessing it can't be i1 true ?

3294–3297

[lebedev.ri]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3349–3351

[lebedev.ri]

(marking as reviewed)

[fhahn]

Just in the process of rebasing this again now that most other parts landed and discovered I accidentally made our job harder by teaching SCEVExpander to preserve LCSSA. Needs a bit of more work now.

[fhahn]

Rebased on top of current trunk. This version now can build MultiSource/SPEC2006/SPEC2000 with -O3 -flto without crashing.

In D75980#2317378, @fhahn wrote:

Just in the process of rebasing this again now that most other parts landed and discovered I accidentally made our job harder by teaching SCEVExpander to preserve LCSSA. Needs a bit of more work now.

I recently fixed a related issue (0ea3749b3cde), which makes this point obsolete; the final CFG is constructed before expanding, which solves the issue.

[fhahn]

Split off the addRuntimeCheck changes to D94295

[fhahn]

Sent mail to llvm-dev (https://lists.llvm.org/pipermail/llvm-dev/2021-January/147678.html), to get thoughts on the 'speculatively create IR and throw away if not needed` pattern in general

[fhahn]

Rebase & ping. The thread on llvm-dev did not surface any objections, so I think it might be time to finally restart the review on this one :)

[lebedev.ri]

I haven't reviewed this in full detail, but this looks good to me overall.
It would probably be good for someone else to also signoff, too.

[ebrevnov]

I'm going to take a look next week if nobody outstrip me...

[fhahn]

Rebased

In D75980#2546738, @ebrevnov wrote:

I'm going to take a look next week if nobody outstrip me...

That would be very much appreciated! :)

[fhahn]

Rebased again & ping :)

I am planning on landing this within the next few days or early next week, unless there are any additional concerns. The 'build IR and throw away if not needed' is already used in multiple places and there have been no objections in llvm-dev. I am also more than happy to iterate on this once in tree to iron out any issues.

[ebrevnov]

I started looking into this... Hopefully, will be able to provide my feedback by tomorrow.

[ebrevnov]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

435

Please add empty lines around and add something like "// Forward declarations" or similar

460

Would "RTChecks" be a better name?

741

Update description on return value. Also consider using Optional<BasicBlock *>.

1888

Some general notes. I would like us to:

1. Consolidate all the work related to runtime checks under this helper abstraction. Currently, it looks like some functionality still on it's old place. Find more comments on this as you go.
2. Make clear boundaries between this GeneratedRTChecks and its users. Please, convert it to class and define clear public API.

1902

'Preheader' looks redundant here as it can easily be get from Loop

1912

Do you really need as separate hook to kick in generation of runtime checks? In other words can we simply move this functionality to constructor?

1915

The goal is to create "un-linked" block(s). Right? In that case, would it be simpler to not depend on Preheader and use CreateBlock directly. I believe it would be easier to un-link the block then.

1924

I would suggest generating SCEV and MemRuntime checks into separate temporary blocks in the first place. I believe that will simplify further managment.

1958

I'm surprised to see the following piece of code dealing with deletion. I would expected SCEVExpanderCleaner does all necessary cleanup. It should be enough just to properly set "markResultUsed". If this is not the case can we rework in this direction?

3282

I believe this functionality should be moved to GeneratedRTChecks.

3289–3290

I believe this functionality should be moved to GeneratedRTChecks.

3294–3297

Please address.

3357

I believe this functionality should be moved to GeneratedRTChecks.

3375

TmpBlock should not be directly exposed outside of GeneratedRTChecks.

8056

I think we should better get all info about runtime checks from GeneratedruntimeChecks directly.

9519

Why do we need to create GeneratedRTChecks outside of InnerLoopVectorizer? Can/Should it have bigger life time?

9768

Why this was moved from its original place?

llvm/test/Transforms/LoopVectorize/pr47343-expander-lcssa-after-cfg-update.ll

59

Looks like we stopped vectorizing something, did we?

[fhahn]

Addressed comments, thanks! Major changes include turning GeneratedRTChecks into a class, maintaining separate blocks for SCEV checks and mem checks, moving most code to add checks back to CFG to GeneratedRTChecks.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

460

Agreed, changed to RTChecks, thanks!

1888

That's a great suggestion, thanks! I moved most of the code from emitSCEVChecks & emitMemRuntimeChecks here. There's some code (mostly assertions), which remain in the original functions, because they need access to various member of ILV.

The new function names potentially can be improved and they should have doc-comments, but I'd prefer to first settle on the final API before doing that.

1915

I updated the code put SCEV and memory checks in separate blocks. It still uses SplitBlock, because this keeps the blocks in the DT/LI, which may be used during SCEV expansion and it also keeps them linked to the right predecessors during expansion (SCEVExpander tries to find values to re-use in predecessors).

1958

The extra cleanup is needed for instructions create directly by addRuntimeChecks, like compares, and/ors which compare pointer bounds (which are generated through SCEV expansion). I updated the comment and made it clearer. It is also only needed for the block with the mem-checks.

9519

For some users (e.g. epilogue vectorization), GeneratedRTChecks needs to be shared unfortunately.

9768

This is only needed for the follow-up, I moved it to the original place for this patch.

llvm/test/Transforms/LoopVectorize/pr47343-expander-lcssa-after-cfg-update.ll

59

We still vectorize, but we now do not create an unnecessary phi node (which has no users)

[ebrevnov]

Thanks for doing the changes. Overall this version looks fine to me. Please go ahead with some final cleanups.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

744

Please update this one as well.

1915

Please, put that info into the code as a comment. SCEVExpander also can decide to hoist some instruction(s) into predecessors. Will they be properly scheduled for deletion?

1983–1984

Please revisit

2029

Why do we need to set it to null?

2056

Why storing to temp?

2057

Why needed?

[fhahn]

Addressed latest round of comments, thanks! I also added additional comments to some of the fields in GeneratedRTChecks.

[fhahn]

re-flow comment not properly formatted

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

1912

I forgot to post my response here. In some cases we know that we do not need runtime checks up front (e.g. because we only interleave the loop). Having a helper to only generate the RT checks if needed helps to avoid unnecessary work.

1915

That's a great idea, I added the comment. All instructions that are generated by SCEVExpander should be tracked by it; it uses an IRBuilder callback to collect them, so it should not matter where exactly they are added.

1951

I am not entirely sure, but I think if the compares could be simplified to true/false during generation from SCEV expression, LoopAccessInfo should have been able to figure out that the checks are unneeded. We could also check for i1 true, but I think that would be best in a separate patch, as the original code had the same assert.

1983–1984

Fixed comment, thanks!

2029

This is used to indicate the check was used and should not be cleaned up. I'll add a comment.

2056

It's not needed any longer, earlier versions set MemCheckBlock = nullptr. I removed it.

2057

This is used to indicate the check was used and should not be cleaned up. I'll add a comment.

[ebrevnov]

LGTM.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

2024

Can/Should SCEVCheckCond be used instead? Just to make it symmetric with emitMemRuntimeChecks.

[fhahn]

Update to use SCEVCheckCond.

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H
 #define LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/ScalarEvolutionNormalization.h"
 #include "llvm/Analysis/TargetFolder.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/CommandLine.h"
class SCEVExpanderCleaner {
   /// Indicates whether the result of the expansion is used. If false, the
   /// instructions added during expansion are removed.
   bool ResultUsed;
 
 public:
   SCEVExpanderCleaner(SCEVExpander &Expander, DominatorTree &DT)
       : Expander(Expander), DT(DT), ResultUsed(false) {}
 
-  ~SCEVExpanderCleaner();
+  ~SCEVExpanderCleaner() { cleanup(); }
 
   /// Indicate that the result of the expansion is used.
   void markResultUsed() { ResultUsed = true; }
+
+  void cleanup();
 };
 } // namespace llvm
 
 #endif

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

if (InsertionPoint->getParent()->getTerminator() == InsertionPoint)
       return true;
     if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S))
       if (llvm::is_contained(InsertionPoint->operand_values(), U->getValue()))
         return true;
   }
   return false;
 }
 
-SCEVExpanderCleaner::~SCEVExpanderCleaner() {
+void SCEVExpanderCleaner::cleanup() {
   // Result is used, nothing to remove.
   if (ResultUsed)
     return;
 
   auto InsertedInstructions = Expander.getAllInsertedInstructions();
 #ifndef NDEBUG
   SmallPtrSet<Instruction *, 8> InsertedSet(InsertedInstructions.begin(),
                                             InsertedInstructions.end());
   (void)InsertedSet;
 #endif
   // Remove sets with value handles.
   Expander.clear();
 
   // Sort so that earlier instructions do not dominate later instructions.
   stable_sort(InsertedInstructions, [this](Instruction *A, Instruction *B) {
     return DT.dominates(B, A);
   });
   // Remove all inserted instructions.
   for (Instruction *I : InsertedInstructions) {
 
 #ifndef NDEBUG
     assert(all_of(I->users(),
                   [&InsertedSet](Value *U) {
                     return InsertedSet.contains(cast<Instruction>(U));
                   }) &&
            "removed instruction should only be used by instructions inserted "
            "during expansion");
 #endif
     assert(!I->getType()->isVoidTy() &&
            "inserted instruction should have non-void types");
     I->replaceAllUsesWith(UndefValue::get(I->getType()));
     I->eraseFromParent();
   }
 }
 }

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

if (auto EstimatedTC = getLoopEstimatedTripCount(L))
       return EstimatedTC;
 
   // Check if upper bound estimate is known.
   if (unsigned ExpectedTC = SE.getSmallConstantMaxTripCount(L))
     return ExpectedTC;
 
   return None;
 }
-
+struct GeneratedRTChecks;
 namespace llvm {
-
 /// InnerLoopVectorizer vectorizes loops which contain only one basic
 /// block to a specified vectorization factor (VF).
 /// This class performs the widening of scalars into vectors, or multiple
 /// scalars. This class also implements the following features:
 /// * It inserts an epilogue loop for handling loops that don't have iteration
 ///   counts that are known to be a multiple of the vectorization factor.
 /// * It handles the code generation for reduction variables.
 /// * Scalarization (implementation using scalars) of un-vectorizable
 ///   instructions.
 /// InnerLoopVectorizer does not perform any vectorization-legality
 /// checks, and relies on the caller to check for the different legality
 /// aspects. The InnerLoopVectorizer relies on the
 /// LoopVectorizationLegality class to provide information about the induction
 /// and reduction variables that were found to a given vectorization factor.
 class InnerLoopVectorizer {
 public:
   InnerLoopVectorizer(Loop *OrigLoop, PredicatedScalarEvolution &PSE,
                       LoopInfo *LI, DominatorTree *DT,
                       const TargetLibraryInfo *TLI,
                       const TargetTransformInfo *TTI, AssumptionCache *AC,
                       OptimizationRemarkEmitter *ORE, ElementCount VecWidth,
                       unsigned UnrollFactor, LoopVectorizationLegality *LVL,
                       LoopVectorizationCostModel *CM, BlockFrequencyInfo *BFI,
-                      ProfileSummaryInfo *PSI)
+                      ProfileSummaryInfo *PSI, GeneratedRTChecks &Check)
       : OrigLoop(OrigLoop), PSE(PSE), LI(LI), DT(DT), TLI(TLI), TTI(TTI),
         AC(AC), ORE(ORE), VF(VecWidth), UF(UnrollFactor),
         Builder(PSE.getSE()->getContext()),
         VectorLoopValueMap(UnrollFactor, VecWidth), Legal(LVL), Cost(CM),
-        BFI(BFI), PSI(PSI) {
+        BFI(BFI), PSI(PSI), Check(Check) {
     // Query this against the original loop and save it here because the profile
     // of the original loop header may change as the transformation happens.
     OptForSizeBasedOnProfile = llvm::shouldOptimizeForSize(
         OrigLoop->getHeader(), PSI, BFI, PGSOQueryType::IRPass);
   }
 
   virtual ~InnerLoopVectorizer() = default;
 
Value *createBitOrPointerCast(Value *V, VectorType *DstVTy,
                                 const DataLayout &DL);
 
   /// Emit a bypass check to see if the vector trip count is zero, including if
   /// it overflows.
   void emitMinimumIterationCountCheck(Loop *L, BasicBlock *Bypass);
 
   /// Emit a bypass check to see if all of the SCEV assumptions we've
   /// had to make are correct.
-  void emitSCEVChecks(Loop *L, BasicBlock *Bypass);
+  BasicBlock *emitSCEVChecks(Loop *L, BasicBlock *Bypass);
 
   /// Emit bypass checks to check any memory assumptions we may have made.
-  void emitMemRuntimeChecks(Loop *L, BasicBlock *Bypass);
+  BasicBlock *emitMemRuntimeChecks(Loop *L, BasicBlock *Bypass);
 
   /// Compute the transformed value of Index at offset StartValue using step
   /// StepValue.
   /// For integer induction, returns StartValue + Index * StepValue.
   /// For pointer induction, returns StartValue[Index * StepValue].
   /// FIXME: The newly created binary instructions should contain nsw/nuw
   /// flags, which can be found from the original scalar operations.
   Value *emitTransformedIndex(IRBuilder<> &B, Value *Index, ScalarEvolution *SE,
protected:
 
   /// BFI and PSI are used to check for profile guided size optimizations.
   BlockFrequencyInfo *BFI;
   ProfileSummaryInfo *PSI;
 
   // Whether this loop should be optimized for size based on profile guided size
   // optimizatios.
   bool OptForSizeBasedOnProfile;
+
+  /// Structure to hold information about generated runtime checks, responsible
+  /// for cleaning the checks, if they turn out unprofitable.
+  GeneratedRTChecks &Check;
 };
 
 class InnerLoopUnroller : public InnerLoopVectorizer {
 public:
   InnerLoopUnroller(Loop *OrigLoop, PredicatedScalarEvolution &PSE,
                     LoopInfo *LI, DominatorTree *DT,
                     const TargetLibraryInfo *TLI,
                     const TargetTransformInfo *TTI, AssumptionCache *AC,
                     OptimizationRemarkEmitter *ORE, unsigned UnrollFactor,
                     LoopVectorizationLegality *LVL,
                     LoopVectorizationCostModel *CM, BlockFrequencyInfo *BFI,
-                    ProfileSummaryInfo *PSI)
+                    ProfileSummaryInfo *PSI, GeneratedRTChecks &Check)
       : InnerLoopVectorizer(OrigLoop, PSE, LI, DT, TLI, TTI, AC, ORE,
                             ElementCount::getFixed(1), UnrollFactor, LVL, CM,
-                            BFI, PSI) {}
+                            BFI, PSI, Check) {}
 
 private:
   Value *getBroadcastInstrs(Value *V) override;
   Value *getStepVector(Value *Val, int StartIdx, Value *Step,
                        Instruction::BinaryOps Opcode =
                        Instruction::BinaryOpsEnd) override;
   Value *reverseVector(Value *Vec) override;
 };

 class InnerLoopAndEpilogueVectorizer : public InnerLoopVectorizer {
 public:
   InnerLoopAndEpilogueVectorizer(
       Loop *OrigLoop, PredicatedScalarEvolution &PSE, LoopInfo *LI,
       DominatorTree *DT, const TargetLibraryInfo *TLI,
       const TargetTransformInfo *TTI, AssumptionCache *AC,
       OptimizationRemarkEmitter *ORE, EpilogueLoopVectorizationInfo &EPI,
       LoopVectorizationLegality *LVL, llvm::LoopVectorizationCostModel *CM,
-      BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI)
+      BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
+      GeneratedRTChecks &Checks)
       : InnerLoopVectorizer(OrigLoop, PSE, LI, DT, TLI, TTI, AC, ORE,
-                            EPI.MainLoopVF, EPI.MainLoopUF, LVL, CM, BFI, PSI),
+                            EPI.MainLoopVF, EPI.MainLoopUF, LVL, CM, BFI, PSI,
+                            Checks),
         EPI(EPI) {}
 
   // Override this function to handle the more complex control flow around the
   // three loops.
   BasicBlock *createVectorizedLoopSkeleton() final override {
     return createEpilogueVectorizedLoopSkeleton();
   }
 

 class EpilogueVectorizerMainLoop : public InnerLoopAndEpilogueVectorizer {
 public:
   EpilogueVectorizerMainLoop(
       Loop *OrigLoop, PredicatedScalarEvolution &PSE, LoopInfo *LI,
       DominatorTree *DT, const TargetLibraryInfo *TLI,
       const TargetTransformInfo *TTI, AssumptionCache *AC,
       OptimizationRemarkEmitter *ORE, EpilogueLoopVectorizationInfo &EPI,
       LoopVectorizationLegality *LVL, llvm::LoopVectorizationCostModel *CM,
-      BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI)
+      BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
+      GeneratedRTChecks &Check)
       : InnerLoopAndEpilogueVectorizer(OrigLoop, PSE, LI, DT, TLI, TTI, AC, ORE,
-                                       EPI, LVL, CM, BFI, PSI) {}
+                                       EPI, LVL, CM, BFI, PSI, Check) {}
   /// Implements the interface for creating a vectorized skeleton using the
   /// *main loop* strategy (ie the first pass of vplan execution).
   BasicBlock *createEpilogueVectorizedLoopSkeleton() final override;
 
 protected:
   /// Emits an iteration count bypass check once for the main loop (when \p
   /// ForEpilogue is false) and once for the epilogue loop (when \p
   /// ForEpilogue is true).
   BasicBlock *emitMinimumIterationCountCheck(Loop *L, BasicBlock *Bypass,
                                              bool ForEpilogue);
   void printDebugTracesAtStart() override;
   void printDebugTracesAtEnd() override;
 };
 
 // A specialized derived class of inner loop vectorizer that performs
 // vectorization of *epilogue* loops in the process of vectorizing loops and
 // their epilogues.
 class EpilogueVectorizerEpilogueLoop : public InnerLoopAndEpilogueVectorizer {
 public:
-  EpilogueVectorizerEpilogueLoop(Loop *OrigLoop, PredicatedScalarEvolution &PSE,
-                    LoopInfo *LI, DominatorTree *DT,
-                    const TargetLibraryInfo *TLI,
-                    const TargetTransformInfo *TTI, AssumptionCache *AC,
-                    OptimizationRemarkEmitter *ORE,
-                    EpilogueLoopVectorizationInfo &EPI,
-                    LoopVectorizationLegality *LVL,
-                    llvm::LoopVectorizationCostModel *CM,
-                    BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI)
+  EpilogueVectorizerEpilogueLoop(
+      Loop *OrigLoop, PredicatedScalarEvolution &PSE, LoopInfo *LI,
+      DominatorTree *DT, const TargetLibraryInfo *TLI,
+      OptimizationRemarkEmitter *ORE, EpilogueLoopVectorizationInfo &EPI,
+      LoopVectorizationLegality *LVL, llvm::LoopVectorizationCostModel *CM,
+      BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
+      GeneratedRTChecks &Checks)
       : InnerLoopAndEpilogueVectorizer(OrigLoop, PSE, LI, DT, TLI, TTI, AC, ORE,
-                                       EPI, LVL, CM, BFI, PSI) {}
+                                       EPI, LVL, CM, BFI, PSI, Checks) {}
   /// Implements the interface for creating a vectorized skeleton using the
   /// *epilogue loop* strategy (ie the second pass of vplan execution).
   BasicBlock *createEpilogueVectorizedLoopSkeleton() final override;
 
 protected:
   /// Emits an iteration count bypass check after the main vector loop has
   /// finished to see if there are any iterations left to execute by either
   /// the vector epilogue or the scalar epilogue.
public:
   SmallPtrSet<const Value *, 16> ValuesToIgnore;
 
   /// Values to ignore in the cost model when VF > 1.
   SmallPtrSet<const Value *, 16> VecValuesToIgnore;
 
   /// Profitable vector factors.
   SmallVector<VectorizationFactor, 8> ProfitableVFs;
 };
-
 } // end namespace llvm
 
+/// Helper struct to manage generating runtime checks for vectorization.
+///
+/// The runtime checks are created up-front in a temporary block to allow better
+/// estimating the cost and un-linked from the existing IR. After deciding to
+/// vectorize, the checks are moved backed. If deciding not to vectorize, the
+/// temporary block is completely removed.
+struct GeneratedRTChecks {
+  BasicBlock *TmpBlock = nullptr;
+  BasicBlock *Preheader;
+  Value *SCEVCheck;
+  Instruction *FirstCheckInst = nullptr;
+  Instruction *MemRuntimeCheck = nullptr;
+
+  ScalarEvolution &SE;
+  DominatorTree *DT;
+
+  SCEVExpander Exp;
+  SCEVExpanderCleaner Cleaner;
+
+  GeneratedRTChecks(BasicBlock *Preheader, ScalarEvolution &SE,
+                    DominatorTree *DT)
+      : Preheader(Preheader), SE(SE), DT(DT),
+        Exp(SE, Preheader->getModule()->getDataLayout(), "scev.check"),
+        Cleaner(Exp, *DT) {}
+
+  /// Generate runtime checks in temporary block (TmpBlock), so we can
+  /// accurately estimate the cost of the runtime checks. The block is un-linked
+  /// from the IR and is added back during vector code generation. If there is
+  /// no vector code generation, the check blocks is removed completely.
+  void Create(Loop *L, const LoopAccessInfo &LAI,
+              const SCEVUnionPredicate &UnionPred, LoopInfo *LI) {
+    BasicBlock *LoopHeader = Preheader->getSingleSuccessor();
+    TmpBlock = SplitBlock(Preheader, Preheader->getTerminator(), DT, LI,
+                          nullptr, "tmp.rtchecks");
+
+    SCEVCheck =
+        Exp.expandCodeForPredicate(&UnionPred, TmpBlock->getTerminator());
+
+    const auto &RtPtrChecking = *LAI.getRuntimePointerChecking();
+    if (RtPtrChecking.Need) {
+      std::tie(FirstCheckInst, MemRuntimeCheck) = addRuntimeChecks(
+          TmpBlock->getTerminator(), L, RtPtrChecking.getChecks(), Exp);
+      assert(MemRuntimeCheck && "no RT checks generated although RtPtrChecking "
+                                "claimed checks are required");
+    }
+
+    // Unhook the temporary block with the checks, update various places
+    // accordingly.
+    TmpBlock->replaceAllUsesWith(Preheader);
+    TmpBlock->getTerminator()->moveBefore(Preheader->getTerminator());
+    Preheader->getTerminator()->eraseFromParent();
+    DT->changeImmediateDominator(LoopHeader, Preheader);
+    DT->eraseNode(TmpBlock);
+    LI->removeBlock(TmpBlock);
+  }
+
+  ~GeneratedRTChecks() {
+    if (!TmpBlock) {
+      Cleaner.markResultUsed();
+      return;
+    }
+
+    if (!SCEVCheck && TmpBlock->empty()) {
+      Cleaner.markResultUsed();
+      TmpBlock->eraseFromParent();
+      return;
+    }
+
+    if (MemRuntimeCheck && !isa<Constant>(MemRuntimeCheck))
+      MemRuntimeCheck->replaceAllUsesWith(
+          ConstantInt::getFalse(MemRuntimeCheck->getType()->getContext()));
+    if (SCEVCheck && !isa<Constant>(SCEVCheck))
+      SCEVCheck->replaceAllUsesWith(
+          ConstantInt::getFalse(SCEVCheck->getType()->getContext()));
+
+    SmallPtrSet<Value *, 8> Removed;
+    // Completely remove the block.
+    for (auto &I : make_early_inc_range(reverse(*TmpBlock))) {
+      if (Exp.isInsertedInstruction(&I))
+        continue;
+      SE.forgetValue(&I);
+      SE.eraseValueFromMap(&I);
+      Removed.insert(&I);
+      I.eraseFromParent();
+    }
+
+    Cleaner.cleanup();
+    TmpBlock->eraseFromParent();
+  }
+};
+
 // Return true if \p OuterLp is an outer loop annotated with hints for explicit
 // vectorization. The loop needs to be annotated with #pragma omp simd
 // simdlen(#) or #pragma clang vectorize(enable) vectorize_width(#). If the
 // vector length information is not provided, vectorization is not considered
 // explicit. Interleave hints are not allowed either. These limitations will be
 // relaxed in the future.
 // Please, note that we are currently forced to abuse the pragma 'clang
 // vectorize' semantics. This pragma provides *auto-vectorization hints*
 // (i.e., LV must check that vectorization is legal) whereas pragma 'omp simd'
 // provides *explicit vectorization hints* (LV can bypass legal checks and
 // assume that vectorization is legal). However, both hints are implemented
 // using the same metadata (llvm.loop.vectorize, processed by
 // LoopVectorizeHints). This will be fixed in the future when the native IR
 // representation for pragma 'omp simd' is introduced.
 static bool isExplicitVecOuterLoop(Loop *OuterLp,
                                    OptimizationRemarkEmitter *ORE) {
   assert(!OuterLp->isInnermost() && "This is not an outer loop");
   LoopVectorizeHints Hints(OuterLp, true /*DisableInterleaving*/, *ORE);
 

 static void collectSupportedLoops(Loop &L, LoopInfo *LI,
                                   OptimizationRemarkEmitter *ORE,
                                   SmallVectorImpl<Loop *> &V) {
   // Collect inner loops and outer loops without irreducible control flow. For
   // now, only collect outer loops that have explicit vectorization hints. If we
   // are stress testing the VPlan H-CFG construction, we collect the outermost
   // loop of every loop nest.
   if (L.isInnermost() || VPlanBuildStressTest ||
       (EnableVPlanNativePath && isExplicitVecOuterLoop(&L, ORE))) {
     LoopBlocksRPO RPOT(&L);
     RPOT.perform(LI);
     if (!containsIrreducibleCFG<const BasicBlock *>(RPOT, *LI)) {
       V.push_back(&L);
       // TODO: Collect inner loops inside marked outer loops in case
       // vectorization fails for the outer loop. Do not invoke
       // 'containsIrreducibleCFG' again for inner loops when the outer loop is
       // already known to be reducible. We can use an inherited attribute for
       // that.
       return;
     }
   }
   for (Loop *InnerL : L)
struct LoopVectorize : public FunctionPass {
   LoopVectorizePass Impl;
 
   explicit LoopVectorize(bool InterleaveOnlyWhenForced = false,
                          bool VectorizeOnlyWhenForced = false)
       : FunctionPass(ID),
         Impl({InterleaveOnlyWhenForced, VectorizeOnlyWhenForced}) {
     initializeLoopVectorizePass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
 
     auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
     auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
     auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     auto *BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
void InnerLoopVectorizer::emitMinimumIterationCountCheck(Loop *L,
   DT->changeImmediateDominator(LoopExitBlock, TCCheckBlock);
 
   ReplaceInstWithInst(
       TCCheckBlock->getTerminator(),
       BranchInst::Create(Bypass, LoopVectorPreHeader, CheckMinIters));
   LoopBypassBlocks.push_back(TCCheckBlock);
 }
 
-void InnerLoopVectorizer::emitSCEVChecks(Loop *L, BasicBlock *Bypass) {
+BasicBlock *InnerLoopVectorizer::emitSCEVChecks(Loop *L, BasicBlock *Bypass) {
   // Reuse existing vector loop preheader for SCEV checks.
   // Note that new preheader block is generated for vector loop.
-  BasicBlock *const SCEVCheckBlock = LoopVectorPreHeader;
-
-  // Generate the code to check that the SCEV assumptions that we made.
-  // We want the new basic block to start at the first instruction in a
-  // sequence of instructions that form a check.
-  SCEVExpander Exp(*PSE.getSE(), Bypass->getModule()->getDataLayout(),
-                   "scev.check");
-  Value *SCEVCheck = Exp.expandCodeForPredicate(
-      &PSE.getUnionPredicate(), SCEVCheckBlock->getTerminator());
+  BasicBlock *const SCEVCheckBlock = Check.TmpBlock;
 
-  if (auto *C = dyn_cast<ConstantInt>(SCEVCheck))
+  if (!Check.TmpBlock)
+    return nullptr;
+  if (auto *C = dyn_cast<ConstantInt>(Check.SCEVCheck))
     if (C->isZero())
-      return;
+      return nullptr;
 
   assert(!(SCEVCheckBlock->getParent()->hasOptSize() ||
            (OptForSizeBasedOnProfile &&
             Cost->Hints->getForce() != LoopVectorizeHints::FK_Enabled)) &&
          "Cannot SCEV check stride or overflow when optimizing for size");
 
   SCEVCheckBlock->setName("vector.scevcheck");
+
+  auto *Pred = LoopVectorPreHeader->getSinglePredecessor();
+
+  BranchInst::Create(LoopVectorPreHeader, Check.TmpBlock);
   // Create new preheader for vector loop.
-  LoopVectorPreHeader =
-      SplitBlock(SCEVCheckBlock, SCEVCheckBlock->getTerminator(), DT, LI,
-                 nullptr, "vector.ph");
+  Check.TmpBlock = SplitBlock(
+      SCEVCheckBlock, cast<Instruction>(Check.SCEVCheck)->getNextNode(),
+      (DominatorTree *)nullptr, nullptr, nullptr, "vector.ph", false);
+
+  if (auto *PL = LI->getLoopFor(LoopVectorPreHeader))
+    PL->addBasicBlockToLoop(SCEVCheckBlock, *LI);
+
+  Check.TmpBlock->replaceAllUsesWith(SCEVCheckBlock);
+  Check.TmpBlock->getTerminator()->moveBefore(SCEVCheckBlock->getTerminator());
+  SCEVCheckBlock->getTerminator()->eraseFromParent();
+  SCEVCheckBlock->moveBefore(LoopVectorPreHeader);
+
+  auto *PHTerm = Pred->getTerminator();
+  for (unsigned i = 0; i < PHTerm->getNumSuccessors(); i++)
+    if (PHTerm->getSuccessor(i) == LoopVectorPreHeader)
+      PHTerm->setSuccessor(i, SCEVCheckBlock);
+
+  DT->addNewBlock(SCEVCheckBlock, Pred);
+  DT->changeImmediateDominator(LoopVectorPreHeader, SCEVCheckBlock);
 
   // Update dominator only if this is first RT check.
   if (LoopBypassBlocks.empty()) {
     DT->changeImmediateDominator(Bypass, SCEVCheckBlock);
     DT->changeImmediateDominator(LoopExitBlock, SCEVCheckBlock);
   }
 
   ReplaceInstWithInst(
       SCEVCheckBlock->getTerminator(),
-      BranchInst::Create(Bypass, LoopVectorPreHeader, SCEVCheck));
+      BranchInst::Create(Bypass, LoopVectorPreHeader, Check.SCEVCheck));
   LoopBypassBlocks.push_back(SCEVCheckBlock);
   AddedSafetyChecks = true;
+  Check.SCEVCheck = nullptr;
+  return SCEVCheckBlock;
 }
 
-void InnerLoopVectorizer::emitMemRuntimeChecks(Loop *L, BasicBlock *Bypass) {
+BasicBlock *InnerLoopVectorizer::emitMemRuntimeChecks(Loop *L,
+                                                      BasicBlock *Bypass) {
   // VPlan-native path does not do any analysis for runtime checks currently.
   if (EnableVPlanNativePath)
-    return;
+    return nullptr;
 
   // Reuse existing vector loop preheader for runtime memory checks.
   // Note that new preheader block is generated for vector loop.
-  BasicBlock *const MemCheckBlock = L->getLoopPreheader();
+  BasicBlock *const MemCheckBlock = Check.TmpBlock;
 
-  // Generate the code that checks in runtime if arrays overlap. We put the
-  // checks into a separate block to make the more common case of few elements
-  // faster.
-  auto *LAI = Legal->getLAI();
-  const auto &RtPtrChecking = *LAI->getRuntimePointerChecking();
-  if (!RtPtrChecking.Need)
-    return;
+  // Check if we generated code that checks in runtime if arrays overlap. We put
+  // the checks into a separate block to make the more common case of few
+  // elements faster.
+  if (!Check.MemRuntimeCheck)
+    return nullptr;
 
   if (MemCheckBlock->getParent()->hasOptSize() || OptForSizeBasedOnProfile) {
     assert(Cost->Hints->getForce() == LoopVectorizeHints::FK_Enabled &&
            "Cannot emit memory checks when optimizing for size, unless forced "
            "to vectorize.");
     ORE->emit([&]() {
       return OptimizationRemarkAnalysis(DEBUG_TYPE, "VectorizationCodeSize",
                                         L->getStartLoc(), L->getHeader())
              << "Code-size may be reduced by not forcing "
                 "vectorization, or by source-code modifications "
                 "eliminating the need for runtime checks "
                 "(e.g., adding 'restrict').";
     });
   }
 
+  auto *Pred = LoopVectorPreHeader->getSinglePredecessor();
+  auto *PHTerm = Pred->getTerminator();
+  for (unsigned i = 0; i < PHTerm->getNumSuccessors(); i++)
+    if (PHTerm->getSuccessor(i) == LoopVectorPreHeader)
+      PHTerm->setSuccessor(i, Check.TmpBlock);
+  auto *BI = BranchInst::Create(LoopVectorPreHeader, Check.TmpBlock);
+  BI->setDebugLoc(PHTerm->getDebugLoc());
+
+  DT->addNewBlock(Check.TmpBlock, Pred);
+  DT->changeImmediateDominator(LoopVectorPreHeader, MemCheckBlock);
+  Check.TmpBlock->moveBefore(LoopVectorPreHeader);
+
+  if (auto *PL = LI->getLoopFor(LoopVectorPreHeader))
+    PL->addBasicBlockToLoop(Check.TmpBlock, *LI);
+
   MemCheckBlock->setName("vector.memcheck");
-  // Create new preheader for vector loop.
-  LoopVectorPreHeader =
-      SplitBlock(MemCheckBlock, MemCheckBlock->getTerminator(), DT, LI, nullptr,
-                 "vector.ph");
 
   auto *CondBranch = cast<BranchInst>(
       Builder.CreateCondBr(Builder.getTrue(), Bypass, LoopVectorPreHeader));
   ReplaceInstWithInst(MemCheckBlock->getTerminator(), CondBranch);
   LoopBypassBlocks.push_back(MemCheckBlock);
   AddedSafetyChecks = true;
 
   // Update dominator only if this is first RT check.
   if (LoopBypassBlocks.empty()) {
     DT->changeImmediateDominator(Bypass, MemCheckBlock);
     DT->changeImmediateDominator(LoopExitBlock, MemCheckBlock);
   }
+  Check.TmpBlock = nullptr;
 
-  Instruction *FirstCheckInst;
-  Instruction *MemRuntimeCheck;
-  SCEVExpander Exp(*PSE.getSE(), MemCheckBlock->getModule()->getDataLayout(),
-                   "induction");
-  std::tie(FirstCheckInst, MemRuntimeCheck) = addRuntimeChecks(
-      MemCheckBlock->getTerminator(), OrigLoop, RtPtrChecking.getChecks(), Exp);
-  assert(MemRuntimeCheck && "no RT checks generated although RtPtrChecking "
-                            "claimed checks are required");
-  CondBranch->setCondition(MemRuntimeCheck);
+  ReplaceInstWithInst(
+      MemCheckBlock->getTerminator(),
+      BranchInst::Create(Bypass, LoopVectorPreHeader, Check.MemRuntimeCheck));
+  AddedSafetyChecks = true;
 
   // We currently don't use LoopVersioning for the actual loop cloning but we
   // still use it to add the noalias metadata.
   LVer = std::make_unique<LoopVersioning>(
       *Legal->getLAI(),
       Legal->getLAI()->getRuntimePointerChecking()->getChecks(), OrigLoop, LI,
       DT, PSE.getSE());
   LVer->prepareNoAliasMetadata();
+  return MemCheckBlock;
 }
 
 Value *InnerLoopVectorizer::emitTransformedIndex(
     IRBuilder<> &B, Value *Index, ScalarEvolution *SE, const DataLayout &DL,
     const InductionDescriptor &ID) const {
 
   SCEVExpander Exp(*SE, DL, "induction");
   auto Step = ID.getStep();
BasicBlock *EpilogueVectorizerMainLoop::createEpilogueVectorizedLoopSkeleton() {
   // Generate the code to check the minimum iteration count of the vector
   // epilogue (see below).
   EPI.EpilogueIterationCountCheck =
       emitMinimumIterationCountCheck(Lp, LoopScalarPreHeader, true);
   EPI.EpilogueIterationCountCheck->setName("iter.check");
 
   // Generate the code to check any assumptions that we've made for SCEV
   // expressions.
-  BasicBlock *SavedPreHeader = LoopVectorPreHeader;
-  emitSCEVChecks(Lp, LoopScalarPreHeader);
-
-  // If a safety check was generated save it.
-  if (SavedPreHeader != LoopVectorPreHeader)
-    EPI.SCEVSafetyCheck = SavedPreHeader;
+  EPI.SCEVSafetyCheck = emitSCEVChecks(Lp, LoopScalarPreHeader);
 
   // Generate the code that checks at runtime if arrays overlap. We put the
   // checks into a separate block to make the more common case of few elements
   // faster.
-  SavedPreHeader = LoopVectorPreHeader;
-  emitMemRuntimeChecks(Lp, LoopScalarPreHeader);
-
-  // If a safety check was generated save/overwite it.
-  if (SavedPreHeader != LoopVectorPreHeader)
-    EPI.MemSafetyCheck = SavedPreHeader;
+  EPI.MemSafetyCheck = emitMemRuntimeChecks(Lp, LoopScalarPreHeader);
 
   // Generate the iteration count check for the main loop, *after* the check
   // for the epilogue loop, so that the path-length is shorter for the case
   // that goes directly through the vector epilogue. The longer-path length for
   // the main loop is compensated for, by the gain from vectorizing the larger
   // trip count. Note: the branch will get updated later on when we vectorize
   // the epilogue.
   EPI.MainLoopIterationCountCheck =
static bool processLoopInVPlanNativePath(
   // code. Masked vector code generation support will follow soon.
   // Also, do not attempt to vectorize if no vector code will be produced.
   if (VPlanBuildStressTest || EnableVPlanPredication ||
       VectorizationFactor::Disabled() == VF)
     return false;
 
   LVP.setBestPlan(VF.Width, 1);
 
+  {
+    GeneratedRTChecks Checks(L->getLoopPreheader(), *PSE.getSE(), DT);
     InnerLoopVectorizer LB(L, PSE, LI, DT, TLI, TTI, AC, ORE, VF.Width, 1, LVL,
-                         &CM, BFI, PSI);
+                           &CM, BFI, PSI, Checks);
     LLVM_DEBUG(dbgs() << "Vectorizing outer loop in \""
                       << L->getHeader()->getParent()->getName() << "\"\n");
     LVP.executePlan(LB, DT);
+  }
 
   // Mark the loop as already vectorized to avoid vectorizing again.
   Hints.setAlreadyVectorized();
-
   assert(!verifyFunction(*L->getHeader()->getParent(), &dbgs()));
   return true;
 }
 
 LoopVectorizePass::LoopVectorizePass(LoopVectorizeOptions Opts)
     : InterleaveOnlyWhenForced(Opts.InterleaveOnlyWhenForced ||
                                !EnableLoopInterleaving),
       VectorizeOnlyWhenForced(Opts.VectorizeOnlyWhenForced ||
#endif /* NDEBUG */
   unsigned IC = 1;
 
   if (MaybeVF) {
     VF = *MaybeVF;
     // Select the interleave count.
     IC = CM.selectInterleaveCount(VF.Width, VF.Cost);
   }
 
+  bool VectorizeLoop = true, InterleaveLoop = true;
   // Identify the diagnostic messages that should be produced.
   std::pair<StringRef, std::string> VecDiagMsg, IntDiagMsg;
-  bool VectorizeLoop = true, InterleaveLoop = true;
-  if (Requirements.doesNotMeet(F, L, Hints)) {
-    LLVM_DEBUG(dbgs() << "LV: Not vectorizing: loop did not meet vectorization "
-                         "requirements.\n");
-    Hints.emitRemarkWithHints();
-    return false;
-  }
-
   if (VF.Width.isScalar()) {
     LLVM_DEBUG(dbgs() << "LV: Vectorization is possible but not beneficial.\n");
     VecDiagMsg = std::make_pair(
         "VectorizationNotBeneficial",
         "the cost-model indicates that vectorization is not beneficial");
     VectorizeLoop = false;
   }
 
ORE->emit([&]() {
              << IntDiagMsg.second;
     });
   } else if (VectorizeLoop && InterleaveLoop) {
     LLVM_DEBUG(dbgs() << "LV: Found a vectorizable loop (" << VF.Width
                       << ") in " << DebugLocStr << '\n');
     LLVM_DEBUG(dbgs() << "LV: Interleave Count is " << IC << '\n');
   }
 
-  LVP.setBestPlan(VF.Width, IC);
+  if (Requirements.doesNotMeet(F, L, Hints)) {
+    LLVM_DEBUG(dbgs() << "LV: Not vectorizing: loop did not meet vectorization "
+                         "requirements.\n");
+    Hints.emitRemarkWithHints();
+    return false;
+  }
 
-  using namespace ore;
   bool DisableRuntimeUnroll = false;
   MDNode *OrigLoopID = L->getLoopID();
+  {
+    // Optimistically generate runtime checks. Drop them if they turn out to not
+    // be profitable. Limit the scope of Checks, so the cleanup happens
+    // immediately after vector codegeneration is done.
+    GeneratedRTChecks Checks(L->getLoopPreheader(), *PSE.getSE(), DT);
+    if (!VF.Width.isScalar() || IC > 1)
+      Checks.Create(L, *LVL.getLAI(), PSE.getUnionPredicate(), LI);
+    LVP.setBestPlan(VF.Width, IC);
 
+    using namespace ore;
     if (!VectorizeLoop) {
       assert(IC > 1 && "interleave count should not be 1 or 0");
       // If we decided that it is not legal to vectorize the loop, then
       // interleave it.
-    InnerLoopUnroller Unroller(L, PSE, LI, DT, TLI, TTI, AC, ORE, IC, &LVL, &CM,
-                               BFI, PSI);
+      InnerLoopUnroller Unroller(L, PSE, LI, DT, TLI, TTI, AC, ORE, IC, &LVL,
+                                 &CM, BFI, PSI, Checks);
       LVP.executePlan(Unroller, DT);
 
       ORE->emit([&]() {
         return OptimizationRemark(LV_NAME, "Interleaved", L->getStartLoc(),
                                   L->getHeader())
                << "interleaved loop (interleaved count: "
                << NV("InterleaveCount", IC) << ")";
       });
     } else {
       // If we decided that it is *legal* to vectorize the loop, then do it.
 
       // Consider vectorizing the epilogue too if it's profitable.
       VectorizationFactor EpilogueVF =
           CM.selectEpilogueVectorizationFactor(VF.Width, LVP);
       if (EpilogueVF.Width.isVector()) {
 
         // The first pass vectorizes the main loop and creates a scalar epilogue
         // to be vectorized by executing the plan (potentially with a different
         // factor) again shortly afterwards.
         EpilogueLoopVectorizationInfo EPI(VF.Width.getKnownMinValue(), IC,
-                                        EpilogueVF.Width.getKnownMinValue(), 1);
-      EpilogueVectorizerMainLoop MainILV(L, PSE, LI, DT, TLI, TTI, AC, ORE, EPI,
-                                         &LVL, &CM, BFI, PSI);
+                                          EpilogueVF.Width.getKnownMinValue(),
+                                          1);
+        EpilogueVectorizerMainLoop MainILV(L, PSE, LI, DT, TLI, TTI, AC, ORE,
+                                           EPI, &LVL, &CM, BFI, PSI, Checks);
 
         LVP.setBestPlan(EPI.MainLoopVF, EPI.MainLoopUF);
         LVP.executePlan(MainILV, DT);
         ++LoopsVectorized;
 
         simplifyLoop(L, DT, LI, SE, AC, nullptr, false /* PreserveLCSSA */);
         formLCSSARecursively(*L, *DT, LI, SE);
 
         // Second pass vectorizes the epilogue and adjusts the control flow
         // edges from the first pass.
         LVP.setBestPlan(EPI.EpilogueVF, EPI.EpilogueUF);
         EPI.MainLoopVF = EPI.EpilogueVF;
         EPI.MainLoopUF = EPI.EpilogueUF;
         EpilogueVectorizerEpilogueLoop EpilogILV(L, PSE, LI, DT, TLI, TTI, AC,
-                                               ORE, EPI, &LVL, &CM, BFI, PSI);
+                                                 ORE, EPI, &LVL, &CM, BFI, PSI,
+                                                 Checks);
         LVP.executePlan(EpilogILV, DT);
         ++LoopsEpilogueVectorized;
 
         if (!MainILV.areSafetyChecksAdded())
           DisableRuntimeUnroll = true;
       } else {
         InnerLoopVectorizer LB(L, PSE, LI, DT, TLI, TTI, AC, ORE, VF.Width, IC,
-                             &LVL, &CM, BFI, PSI);
+                               &LVL, &CM, BFI, PSI, Checks);
         LVP.executePlan(LB, DT);
         ++LoopsVectorized;
 
-      // Add metadata to disable runtime unrolling a scalar loop when there are
-      // no runtime checks about strides and memory. A scalar loop that is
+        // Add metadata to disable runtime unrolling a scalar loop when there
+        // are no runtime checks about strides and memory. A scalar loop that is
         // rarely used is not worth unrolling.
         if (!LB.areSafetyChecksAdded())
           DisableRuntimeUnroll = true;
       }
-
       // Report the vectorization decision.
       ORE->emit([&]() {
         return OptimizationRemark(LV_NAME, "Vectorized", L->getStartLoc(),
                                   L->getHeader())
                << "vectorized loop (vectorization width: "
                << NV("VectorizationFactor", VF.Width)
                << ", interleaved count: " << NV("InterleaveCount", IC) << ")";
       });
     }
+  }
 
   Optional<MDNode *> RemainderLoopID =
       makeFollowupLoopID(OrigLoopID, {LLVMLoopVectorizeFollowupAll,
                                       LLVMLoopVectorizeFollowupEpilogue});
   if (RemainderLoopID.hasValue()) {
     L->setLoopID(RemainderLoopID.getValue());
   } else {
     if (DisableRuntimeUnroll)
while (!Worklist.empty()) {
 
     // For the inner loops we actually process, form LCSSA to simplify the
     // transform.
     Changed |= formLCSSARecursively(*L, *DT, LI, SE);
 
     Changed |= CFGChanged |= processLoop(L);
   }
 
+  assert(!Changed || !verifyFunction(F, &dbgs()));
+
   // Process each loop nest in the function.
   return LoopVectorizeResult(Changed, CFGChanged);
 }
 
 PreservedAnalyses LoopVectorizePass::run(Function &F,
                                          FunctionAnalysisManager &AM) {
     auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
     auto &LI = AM.getResult<LoopAnalysis>(F);

llvm/test/Transforms/LoopVectorize/X86/illegal-parallel-loop-uniform-write.ll

 ; Function Attrs: nounwind uwtable
 define void @foo(i32* nocapture %a, i32* nocapture %b, i32 %k, i32 %m) #0 {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP27:%.*]] = icmp sgt i32 [[M:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP27]], label [[FOR_BODY3_LR_PH_US_PREHEADER:%.*]], label [[FOR_END15:%.*]]
 ; CHECK:       for.body3.lr.ph.us.preheader:
 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[M]], -1
-; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[TMP0]] to i64
-; CHECK-NEXT:    [[TMP2:%.*]] = add nuw nsw i64 [[TMP1]], 1
-; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[K:%.*]] to i64
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[K:%.*]] to i64
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[TMP0]] to i64
+; CHECK-NEXT:    [[TMP3:%.*]] = add nuw nsw i64 [[TMP2]], 1
 ; CHECK-NEXT:    br label [[FOR_BODY3_LR_PH_US:%.*]]
 ; CHECK:       for.end.us:
 ; CHECK-NEXT:    [[ARRAYIDX9_US:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i64 [[INDVARS_IV33:%.*]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = load i32, i32* [[ARRAYIDX9_US]], align 4, !llvm.mem.parallel_loop_access !0
 ; CHECK-NEXT:    [[ADD10_US:%.*]] = add nsw i32 [[TMP4]], 3
 ; CHECK-NEXT:    store i32 [[ADD10_US]], i32* [[ARRAYIDX9_US]], align 4, !llvm.mem.parallel_loop_access !0
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT34:%.*]] = add i64 [[INDVARS_IV33]], 1
 ; CHECK-NEXT:    [[LFTR_WIDEIV35:%.*]] = trunc i64 [[INDVARS_IV_NEXT34]] to i32

 ; CHECK-NEXT:    [[ADD5_US:%.*]] = add nsw i32 [[TMP6]], 1
 ; CHECK-NEXT:    store i32 [[ADD5_US]], i32* [[ARRAYIDX7_US:%.*]], align 4, !llvm.mem.parallel_loop_access !0
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT30]] = add i64 [[INDVARS_IV29]], 1
 ; CHECK-NEXT:    [[LFTR_WIDEIV31:%.*]] = trunc i64 [[INDVARS_IV_NEXT30]] to i32
 ; CHECK-NEXT:    [[EXITCOND32:%.*]] = icmp eq i32 [[LFTR_WIDEIV31]], [[M]]
 ; CHECK-NEXT:    br i1 [[EXITCOND32]], label [[FOR_END_US:%.*]], label [[FOR_BODY3_US]], !llvm.loop !3
 ; CHECK:       for.body3.lr.ph.us:
 ; CHECK-NEXT:    [[INDVARS_IV33]] = phi i64 [ [[INDVARS_IV_NEXT34]], [[FOR_END_US]] ], [ 0, [[FOR_BODY3_LR_PH_US_PREHEADER]] ]
-; CHECK-NEXT:    [[TMP7:%.*]] = add i64 [[TMP3]], [[INDVARS_IV33]]
+; CHECK-NEXT:    [[TMP7:%.*]] = add i64 [[TMP1]], [[INDVARS_IV33]]
 ; CHECK-NEXT:    [[TMP8:%.*]] = trunc i64 [[TMP7]] to i32
 ; CHECK-NEXT:    [[TMP9:%.*]] = trunc i64 [[INDVARS_IV33]] to i32
 ; CHECK-NEXT:    [[ADD_US]] = add i32 [[TMP9]], [[K]]
 ; CHECK-NEXT:    [[ARRAYIDX7_US]] = getelementptr inbounds i32, i32* [[A]], i64 [[INDVARS_IV33]]
-; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[TMP2]], 4
+; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[TMP3]], 4
 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH]], label [[VECTOR_SCEVCHECK:%.*]]
 ; CHECK:       vector.scevcheck:
 ; CHECK-NEXT:    [[MUL:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 1, i32 [[TMP0]])
 ; CHECK-NEXT:    [[MUL_RESULT:%.*]] = extractvalue { i32, i1 } [[MUL]], 0
 ; CHECK-NEXT:    [[MUL_OVERFLOW:%.*]] = extractvalue { i32, i1 } [[MUL]], 1
 ; CHECK-NEXT:    [[TMP10:%.*]] = add i32 [[TMP8]], [[MUL_RESULT]]
 ; CHECK-NEXT:    [[TMP11:%.*]] = sub i32 [[TMP8]], [[MUL_RESULT]]
 ; CHECK-NEXT:    [[TMP12:%.*]] = icmp sgt i32 [[TMP11]], [[TMP8]]
 ; CHECK-NEXT:    [[TMP13:%.*]] = icmp slt i32 [[TMP10]], [[TMP8]]
 ; CHECK-NEXT:    [[TMP14:%.*]] = select i1 false, i1 [[TMP12]], i1 [[TMP13]]
 ; CHECK-NEXT:    [[TMP15:%.*]] = or i1 [[TMP14]], [[MUL_OVERFLOW]]
 ; CHECK-NEXT:    [[TMP16:%.*]] = or i1 false, [[TMP15]]
 ; CHECK-NEXT:    br i1 [[TMP16]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]
 ; CHECK:       vector.ph:
-; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[TMP2]], 4
-; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TMP2]], [[N_MOD_VF]]
+; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[TMP3]], 4
+; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TMP3]], [[N_MOD_VF]]
 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 ; CHECK:       vector.body:
 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
 ; CHECK-NEXT:    [[TMP17:%.*]] = trunc i64 [[INDEX]] to i32
 ; CHECK-NEXT:    [[TMP18:%.*]] = add i32 [[TMP17]], 0
 ; CHECK-NEXT:    [[TMP19:%.*]] = add i32 [[ADD_US]], [[TMP18]]
 ; CHECK-NEXT:    [[TMP20:%.*]] = sext i32 [[TMP19]] to i64
 ; CHECK-NEXT:    [[TMP21:%.*]] = getelementptr inbounds i32, i32* [[A]], i64 [[TMP20]]
 ; CHECK-NEXT:    [[TMP22:%.*]] = getelementptr inbounds i32, i32* [[TMP21]], i32 0
 ; CHECK-NEXT:    [[TMP23:%.*]] = bitcast i32* [[TMP22]] to <4 x i32>*
 ; CHECK-NEXT:    [[WIDE_LOAD:%.*]] = load <4 x i32>, <4 x i32>* [[TMP23]], align 4
 ; CHECK-NEXT:    [[TMP24:%.*]] = add nsw <4 x i32> [[WIDE_LOAD]], <i32 1, i32 1, i32 1, i32 1>
 ; CHECK-NEXT:    [[TMP25:%.*]] = extractelement <4 x i32> [[TMP24]], i32 0
 ; CHECK-NEXT:    store i32 [[TMP25]], i32* [[ARRAYIDX7_US]], align 4, !llvm.mem.parallel_loop_access !0
 ; CHECK-NEXT:    [[TMP26:%.*]] = extractelement <4 x i32> [[TMP24]], i32 1
 ; CHECK-NEXT:    store i32 [[TMP26]], i32* [[ARRAYIDX7_US]], align 4, !llvm.mem.parallel_loop_access !0
 ; CHECK-NEXT:    [[TMP27:%.*]] = extractelement <4 x i32> [[TMP24]], i32 2
 ; CHECK-NEXT:    store i32 [[TMP27]], i32* [[ARRAYIDX7_US]], align 4, !llvm.mem.parallel_loop_access !0
 ; CHECK-NEXT:    [[TMP28:%.*]] = extractelement <4 x i32> [[TMP24]], i32 3
 ; CHECK-NEXT:    store i32 [[TMP28]], i32* [[ARRAYIDX7_US]], align 4, !llvm.mem.parallel_loop_access !0
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add i64 [[INDEX]], 4
 ; CHECK-NEXT:    [[TMP29:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
 ; CHECK-NEXT:    br i1 [[TMP29]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop !5
 ; CHECK:       middle.block:
-; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 [[TMP2]], [[N_VEC]]
+; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 [[TMP3]], [[N_VEC]]
 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[FOR_END_US]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
 ; CHECK-NEXT:    [[BC_RESUME_VAL]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[FOR_BODY3_LR_PH_US]] ], [ 0, [[VECTOR_SCEVCHECK]] ]
 ; CHECK-NEXT:    br label [[FOR_BODY3_US]]
 ; CHECK:       for.end15.loopexit:
 ; CHECK-NEXT:    br label [[FOR_END15]]
 ; CHECK:       for.end15:
 ; CHECK-NEXT:    ret void

llvm/test/Transforms/LoopVectorize/pr47343-expander-lcssa-after-cfg-update.ll

 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[INDEX_NEXT]], 500
 ; CHECK-NEXT:    br i1 [[TMP3]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], [[LOOP5:!llvm.loop !.*]]
 
 ; CHECK:       middle.block:
 ; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i32 500, 500
 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[EXIT:%.*]], label [[SCALAR_PH]]
 
 ; CHECK:       scalar.ph:
-; CHECK-NEXT:    [[TMP4:%.*]] = phi i8* [ [[TMP1]], %vector.memcheck ], [ [[TMP1]], %loop.preheader ], [ [[TMP1]], %middle.block ]
 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i32 [ 500, %middle.block ], [ 0, %loop.preheader ], [ 0, %vector.memcheck ]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ;
 entry:
   br label %outer.header
 
 outer.header:                            ; preds = %cleanup, %entry
   %0 = load i8*, i8** @d, align 1

llvm/test/Transforms/LoopVectorize/runtime-drop-crash.ll

+; RUN: opt -loop-vectorize -force-vector-width=4 %s | FileCheck %s
+
+%struct.foo = type { [400 x double] }
+
+; Make sure we do not crash when dropping runtime checks.
+
+; CHECK-NOT: vector.body
+
+define void @barney(%struct.foo* %ptr) {
+entry:
+  br label %loop
+
+loop:
+  %tmp3 = phi i64 [ 0, %entry ], [ %tmp18, %loop ]
+  %tmp4 = getelementptr inbounds %struct.foo, %struct.foo* %ptr, i64 undef
+  %tmp5 = bitcast %struct.foo* %tmp4 to i64*
+  store i64 0, i64* %tmp5, align 8
+  %tmp8 = add i64 1, %tmp3
+  %tmp10 = getelementptr inbounds %struct.foo, %struct.foo* %ptr, i64 %tmp8
+  %tmp11 = bitcast %struct.foo* %tmp10 to i64*
+  store i64 1, i64* %tmp11, align 8
+  %tmp14 = add i64 undef, %tmp3
+  %tmp16 = getelementptr inbounds %struct.foo, %struct.foo* %ptr, i64 %tmp14
+  %tmp17 = bitcast %struct.foo* %tmp16 to i64*
+  store i64 2, i64* %tmp17, align 8
+  %tmp18 = add nuw nsw i64 %tmp3, 4
+  %c = icmp ult i64 %tmp18, 400
+  br i1 %c, label %exit, label %loop
+
+exit:
+  ret void
+}

llvm/test/Transforms/LoopVectorize/skeleton-lcssa-crash.ll

 ; CHECK-NEXT:    br label [[INNER:%.*]]
 ; CHECK:       inner:
 ; CHECK-NEXT:    [[C_2:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[C_2]], label [[OUTER_LATCH:%.*]], label [[INNER_BB:%.*]]
 ; CHECK:       inner.bb:
 ; CHECK-NEXT:    [[C_3:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[C_3]], label [[LOOP3_PREHEADER:%.*]], label [[INNER_LATCH:%.*]]
 ; CHECK:       loop3.preheader:
-; CHECK-NEXT:    [[L_1_LCSSA11:%.*]] = phi i16* [ [[L_1]], [[INNER_BB]] ]
+; CHECK-NEXT:    [[L_1_LCSSA8:%.*]] = phi i16* [ [[L_1]], [[INNER_BB]] ]
 ; CHECK-NEXT:    [[L_1_LCSSA:%.*]] = phi i16* [ [[L_1]], [[INNER_BB]] ]
 ; CHECK-NEXT:    [[L_2_LCSSA:%.*]] = phi i16* [ [[L_2]], [[INNER_BB]] ]
-; CHECK-NEXT:    [[L_2_LCSSA4:%.*]] = bitcast i16* [[L_2_LCSSA]] to i8*
+; CHECK-NEXT:    [[L_2_LCSSA3:%.*]] = bitcast i16* [[L_2_LCSSA]] to i8*
 ; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[N:%.*]], 1
 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[TMP0]], 2
 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]]
 ; CHECK:       vector.memcheck:
-; CHECK-NEXT:    [[UGLYGEP:%.*]] = getelementptr i8, i8* [[L_2_LCSSA4]], i64 1
+; CHECK-NEXT:    [[UGLYGEP:%.*]] = getelementptr i8, i8* [[L_2_LCSSA3]], i64 1
 ; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i16, i16* [[L_1_LCSSA]], i64 1
-; CHECK-NEXT:    [[SCEVGEP9:%.*]] = bitcast i16* [[SCEVGEP]] to i8*
+; CHECK-NEXT:    [[SCEVGEP6:%.*]] = bitcast i16* [[SCEVGEP]] to i8*
 ; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[N]], 2
-; CHECK-NEXT:    [[SCEVGEP10:%.*]] = getelementptr i16, i16* [[L_1_LCSSA11]], i64 [[TMP1]]
-; CHECK-NEXT:    [[SCEVGEP1013:%.*]] = bitcast i16* [[SCEVGEP10]] to i8*
-; CHECK-NEXT:    [[BOUND0:%.*]] = icmp ult i8* [[L_2_LCSSA4]], [[SCEVGEP1013]]
-; CHECK-NEXT:    [[BOUND1:%.*]] = icmp ult i8* [[SCEVGEP9]], [[UGLYGEP]]
+; CHECK-NEXT:    [[SCEVGEP7:%.*]] = getelementptr i16, i16* [[L_1_LCSSA8]], i64 [[TMP1]]
+; CHECK-NEXT:    [[SCEVGEP710:%.*]] = bitcast i16* [[SCEVGEP7]] to i8*
+; CHECK-NEXT:    [[BOUND0:%.*]] = icmp ult i8* [[L_2_LCSSA3]], [[SCEVGEP710]]
+; CHECK-NEXT:    [[BOUND1:%.*]] = icmp ult i8* [[SCEVGEP6]], [[UGLYGEP]]
 ; CHECK-NEXT:    [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
 ; CHECK-NEXT:    [[MEMCHECK_CONFLICT:%.*]] = and i1 [[FOUND_CONFLICT]], true
 ; CHECK-NEXT:    br i1 [[MEMCHECK_CONFLICT]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]
 ; CHECK:       vector.ph:
 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[TMP0]], 2
 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TMP0]], [[N_MOD_VF]]
 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 ; CHECK:       vector.body:

 ; CHECK-NEXT:    store i16 [[TMP9]], i16* [[TMP7]], align 2, !alias.scope !3, !noalias !0
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add i64 [[INDEX]], 2
 ; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
 ; CHECK-NEXT:    br i1 [[TMP10]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], [[LOOP5:!llvm.loop !.*]]
 ; CHECK:       middle.block:
 ; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 [[TMP0]], [[N_VEC]]
 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[EXIT_LOOPEXIT:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
-; CHECK-NEXT:    [[L_18:%.*]] = phi i16* [ [[L_1_LCSSA]], [[VECTOR_MEMCHECK]] ], [ [[L_1_LCSSA]], [[LOOP3_PREHEADER]] ], [ [[L_1_LCSSA]], [[MIDDLE_BLOCK]] ]
-; CHECK-NEXT:    [[L_23:%.*]] = phi i16* [ [[L_2_LCSSA]], [[VECTOR_MEMCHECK]] ], [ [[L_2_LCSSA]], [[LOOP3_PREHEADER]] ], [ [[L_2_LCSSA]], [[MIDDLE_BLOCK]] ]
 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[LOOP3_PREHEADER]] ], [ 0, [[VECTOR_MEMCHECK]] ]
 ; CHECK-NEXT:    br label [[LOOP3:%.*]]
 ; CHECK:       inner.latch:
 ; CHECK-NEXT:    [[C_4:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[C_4]], label [[EXIT_LOOPEXIT1:%.*]], label [[INNER]]
 ; CHECK:       outer.latch:
 ; CHECK-NEXT:    br label [[OUTER_BACKEDGE]]
 ; CHECK:       loop3:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP3]] ], [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp ult i64 [[IV]], [[N]]
-; CHECK-NEXT:    [[GEP_1:%.*]] = getelementptr inbounds i16, i16* [[L_18]], i64 [[IV_NEXT]]
+; CHECK-NEXT:    [[GEP_1:%.*]] = getelementptr inbounds i16, i16* [[L_1_LCSSA]], i64 [[IV_NEXT]]
 ; CHECK-NEXT:    [[LOOP_L_1:%.*]] = load i16, i16* [[GEP_1]], align 2
-; CHECK-NEXT:    [[GEP_2:%.*]] = getelementptr inbounds i16, i16* [[L_23]], i64 0
+; CHECK-NEXT:    [[GEP_2:%.*]] = getelementptr inbounds i16, i16* [[L_2_LCSSA]], i64 0
 ; CHECK-NEXT:    store i16 [[LOOP_L_1]], i16* [[GEP_2]], align 2
 ; CHECK-NEXT:    br i1 [[C_5]], label [[LOOP3]], label [[EXIT_LOOPEXIT]], [[LOOP7:!llvm.loop !.*]]
 ; CHECK:       exit.loopexit:
-; CHECK-NEXT:    [[L_17:%.*]] = phi i16* [ [[L_1_LCSSA]], [[MIDDLE_BLOCK]] ], [ [[L_18]], [[LOOP3]] ]
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit.loopexit1:
-; CHECK-NEXT:    [[L_1_LCSSA5:%.*]] = phi i16* [ [[L_1]], [[INNER_LATCH]] ]
+; CHECK-NEXT:    [[L_1_LCSSA4:%.*]] = phi i16* [ [[L_1]], [[INNER_LATCH]] ]
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[L_16:%.*]] = phi i16* [ [[L_1_LCSSA5]], [[EXIT_LOOPEXIT1]] ], [ [[L_17]], [[EXIT_LOOPEXIT]] ]
-; CHECK-NEXT:    [[L_3:%.*]] = load i16, i16* [[L_16]], align 2
+; CHECK-NEXT:    [[L_15:%.*]] = phi i16* [ [[L_1_LCSSA4]], [[EXIT_LOOPEXIT1]] ], [ [[L_1_LCSSA]], [[EXIT_LOOPEXIT]] ]
+; CHECK-NEXT:    [[L_3:%.*]] = load i16, i16* [[L_15]], align 2
 ; CHECK-NEXT:    ret i16 [[L_3]]
 ;
 entry:
   br label %outer
 
 outer:
   %l.1 = load i16*, i16** %arg, align 8
   %l.2 = load i16*, i16** %arg, align 8