Epilog loop vectorization

[ashutosh.nema]

Summary

This is a proposal about epilog loop vectorization.

Currently Loop Vectorizer inserts an epilogue loop for handling loops that don’t have known iteration counts.

The Loop Vectorizer supports loops with an unknown trip count, unknown trip count may not be a multiple of the vector width, and the vectorizer has to execute the last few iterations as scalar code. It keeps a scalar copy of the loop for the remaining iterations.

Loop with the large width has a high possibility of executing many scalar iterations.
i.e. i8 data type with 256bits target register can vectorize with vector width 32, with that maximum trip count possibility for scalar(epilog) loop is 31, which is significant & worth vectorizing.

Large vector factor has following challenges:

1. Possibility of remainder iteration is substantial.
2. Actual trip count at runtime is substantial but not meeting minimum trip count to execute vector loop.

These challenges can be addressed by mask instructions, but these instructions are limited and may not be available to all targets.

By epilog vectorization our aim to vectorize epilog loop where original loop is vectorized with large vector factor and has a high possibility of executing scalar iterations.

This require following changes:

1. Costing: Preserve all profitable vector factor.
2. Transform: Create an additional vector loop with next profitable vector factor.

Please refer attached file (BlockLayout.png) for the details about transformed block layout.

[ashutosh.nema]

Block layout:

[ashutosh.nema]

Test cases are missing well add.

[rengolin]

I think this is an interesting idea, though with limited applicability. Furthermore, the way you implemented makes it completely orthogonal to the vectoriser, and at odds with the VPlan strategy being discussed.

Before VPlans get in, I'd assume you would sort the strategies by cost and, if they were in a beneficial order (ex. 4 > 2 > 1), you'd then split the loop in N parts, one for each size. The problem here is that the trade-offs are not clear, and this is probably only beneficial for *very* large VF (32+), because now you're adding more run time checks, shuffles and moves between scalar and vector register banks, which are not always free.

A few more ideas...

1. If the second loop needs to be >16, then just unroll however many instructions to match 16 lanes, no loops necessary.
2. Link this optimisation to code size restrictions. We don't wan't to run this at Os.
3. Once VPlans go in, this would be a separate VPlan that could be applied on top of others, so we may need to change the VPlan implementation to allow that.

Finally, tests. Even this just being a proposal, with tests you can show your proposal "in action" and allow us to discuss specific details of the pass that could be too opaque or intricate to realise just looking at the code.

cheers,
--renato

lib/Transforms/Vectorize/LoopVectorize.cpp

3345

So, you're assuming that just having more than 16 iterations is "beneficial", but you haven't done any cost analysis. It may very well be that the cost is just not worth it, especially for smaller vector sizes.

[mkuper]

I haven't looked at the patch yet - but I think it's a nice idea.
I know there was some experimentation with using masked epilogues, which, IIRC, did not provide a tangible benefit. Do you have any performance numbers showing that doing it this way does?

[ashutosh.nema]

lib/Transforms/Vectorize/LoopVectorize.cpp

3280

We can remove call to loop vectorizer’s legality before widening epilog loop, as legality is already proven for scalar loop while generating first vector version, it’s not required to prove again as scalar body has not changed. Epilog vectorization will depend on already computed legality. I have tried this change and found no impacts in my regular tests & benchmarks.

Please let me know thoughts on this.

3345

Costing is already done, during the cost calculation of first vector version we have preserved the profitable VFs.
At this point we look for the next profitable vector factor and widen epilog loop with it.

[ashutosh.nema]

This change includes:

a) Code refactoring.

b) Removed call to loop vectorizer’s legality before widening epilog loop as legality is already proven for scalar loop while generating first vector version, it’s not required to prove again as scalar body has not changed. Epilog vectorization will depend on already computed legality.

c) Added tests.

[ashutosh.nema]

Block layout description

[rengolin]

Hi Ashutosh,

Sorry for the delay. I think the patch is looking good from my end.

I'd add a TODO to maybe unroll+SLP if the proportion between the next profitable VF and the size of the tail are close together. This could also simplify the call graph.

Example: VF=8, so tail is at most 7 and next VF is 4. This would be better without a latch, just if (end - i) > 4 -> 4-way SIMD -> for (i .. end) -> scalar.

But this is not a job for this patch, I think.

So, now, it would be good to know a few numbers. Can you share some performance improvements?

Also, would be good to get @mkuper take on this.

cheers,
--renato

lib/Transforms/Vectorize/LoopVectorize.cpp

3280

Legality is not the problem, here, but the cost. If the transformation is legal for VF, then it's also legal for all vfs < VF.

6416

This makes sense to me, and it's exactly how I would implement it.

6426

You don't need the NOTE in comments...

[hfinkel]

After this patch was posted, there was an RFC discussion regarding approach. We discussed, for example, just adding metadata (or keeping similar state) to restrict VF and rerunning the vectorizer to vectorize the epilogue loop. Can you please summarize that discussion and how it relates to what's here? Did the design of this patch change as a result of that discussion? If not, why not?

include/llvm/Transforms/Utils/LoopVersioning.h

151

I don't see why this variable is needed. It only seems to be used to adjust the assert. I see no problem with relaxing the required loop conditions, but I think that you should just relax them and document what they are.

[magabari]

In D30247#700366, @hfinkel wrote:

After this patch was posted, there was an RFC discussion regarding approach. We discussed, for example, just adding metadata (or keeping similar state) to restrict VF and rerunning the vectorizer to vectorize the epilogue loop. Can you please summarize that discussion and how it relates to what's here? Did the design of this patch change as a result of that discussion? If not, why not?

@ashutosh.nema can you clarify where this patch stands? and if it's gonna be updated soon?

[ashutosh.nema]

This patch is little old and not updated with latest vectorization changes.

In the RFC there are few concerns raised around the new block layout:
a) If original loop alias check fails, then directly jump to scalar loop
b) On critical path there should not be extra checks, i.e. when minimum iteration check fails for the original vector loop then directly jump to scalar loop. In my opinion this is possible optimization opportunity loss, because when minimum iteration check for original loop fails, can still try executing epilog loop and that requires epilog loop’s minimum iteration check. We can keep his under option.

I guess both the cases can be handled, I’ll re initiate the discussion & update this patch soon.

[DavidMC]

In D30247#863168, @ashutosh.nema wrote:

This patch is little old and not updated with latest vectorization changes.

In the RFC there are few concerns raised around the new block layout:
a) If original loop alias check fails, then directly jump to scalar loop
b) On critical path there should not be extra checks, i.e. when minimum iteration check fails for the original vector loop then directly jump to scalar loop. In my opinion this is possible optimization opportunity loss, because when minimum iteration check for original loop fails, can still try executing epilog loop and that requires epilog loop’s minimum iteration check. We can keep his under option.

I guess both the cases can be handled, I’ll re initiate the discussion & update this patch soon.

Is there any update with this patch? I find it very useful for cycles and size for targets that has masked operations not just for load and store but also for other operations including intra operations

[Ayal]

In D30247#1340561, @DavidMC wrote:

In D30247#863168, @ashutosh.nema wrote:

This patch is little old and not updated with latest vectorization changes.

In the RFC there are few concerns raised around the new block layout:
a) If original loop alias check fails, then directly jump to scalar loop
b) On critical path there should not be extra checks, i.e. when minimum iteration check fails for the original vector loop then directly jump to scalar loop. In my opinion this is possible optimization opportunity loss, because when minimum iteration check for original loop fails, can still try executing epilog loop and that requires epilog loop’s minimum iteration check. We can keep his under option.

I guess both the cases can be handled, I’ll re initiate the discussion & update this patch soon.

Is there any update with this patch? I find it very useful for cycles and size for targets that has masked operations not just for load and store but also for other operations including intra operations

BTW, targets that have efficient masked operations may also find it useful for cycles and size to vectorize (including epilogs) under -Os, and following r345705 possibly also with enable-masked-interleaved-mem-accesses turned on.

[rengolin]

In D30247#1375520, @Ayal wrote:

BTW, targets that have efficient masked operations may also find it useful for cycles and size to vectorize (including epilogs) under -Os, and following r345705 possibly also with enable-masked-interleaved-mem-accesses turned on.

I agree, but I think this approach is a tad too heavy for masked operations.

In SVE, the masking will happen naturally and the last loop will just have the remaining elements as a consequence of the ISA design.

In non-scalable vector extensions, that's not true, so it would need some emulation. But I wouldn't make it such a special case and with so many checks.

I imagine that, if the vectorisation of the full vector length was legal, then so is the case for a smaller length. It may not be profitable on its own, but the fact that it continues the existing patterns (before moving results into scalar registers) will probably make it cheaper than a scalar tail.

This could either be some arithmetic on the mask computation (which would occur on every iteration of the loop + 1) or a tail loop with the same mask computation duplicated from the one just vectorised. I imagine -O3 would have different trade-offs than -Os, so we could potentially have both solutions.

include/llvm/Transforms/Utils/LoopVersioning.h

 class LoopVersioning {
 public:
   /// \brief Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.
   /// It uses runtime check provided by the user. If \p UseLAIChecks is true,
   /// we will retain the default checks made by LAI. Otherwise, construct an
   /// object having no checks and we expect the user to add them.
   LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
                  DominatorTree *DT, ScalarEvolution *SE,
-                 bool UseLAIChecks = true);
+                 bool UseLAIChecks = true, bool AssumeLoopSimplifyForm = false);
 
   /// \brief Performs the CFG manipulation part of versioning the loop including
   /// the DominatorTree and LoopInfo updates.
   ///
   /// The loop that was used to construct the class will be the "versioned" loop
   /// i.e. the loop that will receive control if all the memchecks pass.
   ///
   /// This allows the loop transform pass to operate on the same loop regardless
private:
   DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *>
       GroupToNonAliasingScopeList;
 
   /// \brief Analyses used.
   const LoopAccessInfo &LAI;
   LoopInfo *LI;
   DominatorTree *DT;
   ScalarEvolution *SE;
+  // Flag to allow non simplify form loops in LoopVersioning.
+  // Minimal expectation is Loop should have a pre header & single exit block.
+  bool AssumeLoopSimplifyForm;
 };
 }
 
 #endif

lib/Transforms/Utils/LoopVersioning.cpp

 static cl::opt<bool>
     AnnotateNoAlias("loop-version-annotate-no-alias", cl::init(true),
                     cl::Hidden,
                     cl::desc("Add no-alias annotation for instructions that "
                              "are disambiguated by memchecks"));
 
 LoopVersioning::LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
                                DominatorTree *DT, ScalarEvolution *SE,
-                               bool UseLAIChecks)
+                               bool UseLAIChecks, bool AssumeLoopSimplifyForm)
     : VersionedLoop(L), NonVersionedLoop(nullptr), LAI(LAI), LI(LI), DT(DT),
-      SE(SE) {
+      SE(SE), AssumeLoopSimplifyForm(AssumeLoopSimplifyForm) {
   assert(L->getExitBlock() && "No single exit block");
+  if (AssumeLoopSimplifyForm)
+    assert(L->getLoopPreheader() && "No preheader in the loop");
+  else
     assert(L->isLoopSimplifyForm() && "Loop is not in loop-simplify form");
   if (UseLAIChecks) {
     setAliasChecks(LAI.getRuntimePointerChecking()->getChecks());
     setSCEVChecks(LAI.getPSE().getUnionPredicate());
   }
 }
 
 void LoopVersioning::setAliasChecks(
     SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks) {

lib/Transforms/Vectorize/LoopVectorize.cpp

static cl::opt<unsigned> VectorizeSCEVCheckThreshold(
     "vectorize-scev-check-threshold", cl::init(16), cl::Hidden,
     cl::desc("The maximum number of SCEV checks allowed."));
 
 static cl::opt<unsigned> PragmaVectorizeSCEVCheckThreshold(
     "pragma-vectorize-scev-check-threshold", cl::init(128), cl::Hidden,
     cl::desc("The maximum number of SCEV checks allowed with a "
              "vectorize(enable) pragma"));
 
+static cl::opt<bool> EnableEpilogVectorization(
+    "enable-epilog-vectorization", cl::init(false), cl::Hidden,
+    cl::desc("Enable vectorization of epilog scalar loop."));
+
+static cl::opt<unsigned> MinWidthEpilogVectorization(
+    "min-width-epilog-vectorization", cl::init(16), cl::Hidden,
+    cl::desc("Minimum vector loop width to enable epilog vectorization."));
+
 /// Create an analysis remark that explains why vectorization failed
 ///
 /// \p PassName is the name of the pass (e.g. can be AlwaysPrint).  \p
 /// RemarkName is the identifier for the remark.  If \p I is passed it is an
 /// instruction that prevents vectorization.  Otherwise \p TheLoop is used for
 /// the location of the remark.  \return the remark object that can be
 /// streamed to.
 static OptimizationRemarkAnalysis

 class InnerLoopVectorizer {
 public:
   InnerLoopVectorizer(Loop *OrigLoop, PredicatedScalarEvolution &PSE,
                       LoopInfo *LI, DominatorTree *DT,
                       const TargetLibraryInfo *TLI,
                       const TargetTransformInfo *TTI, AssumptionCache *AC,
                       OptimizationRemarkEmitter *ORE, unsigned VecWidth,
                       unsigned UnrollFactor, LoopVectorizationLegality *LVL,
-                      LoopVectorizationCostModel *CM)
+                      LoopVectorizationCostModel *CM,
+                      unsigned EpilogVectorLoopWidth = 1,
+                      std::function<const LoopAccessInfo &(Loop &)> *GetLAA = nullptr,
+                      AliasAnalysis *AA = nullptr)
       : OrigLoop(OrigLoop), PSE(PSE), LI(LI), DT(DT), TLI(TLI), TTI(TTI),
-        AC(AC), ORE(ORE), VF(VecWidth), UF(UnrollFactor),
+        AA(AA), AC(AC), ORE(ORE), VF(VecWidth), UF(UnrollFactor),
         Builder(PSE.getSE()->getContext()), Induction(nullptr),
         OldInduction(nullptr), VectorLoopValueMap(UnrollFactor, VecWidth),
         TripCount(nullptr), VectorTripCount(nullptr), Legal(LVL), Cost(CM),
-        AddedSafetyChecks(false) {}
+        AddedSafetyChecks(false), EpilogVectorLoopWidth(EpilogVectorLoopWidth),
+        ScalarResumeValue(nullptr), AliasCheckResult(nullptr), GetLAA(GetLAA) {}
 
   // Perform the actual loop widening (vectorization).
-  void vectorize() {
+  void vectorize(Value *RemainderItrs = nullptr,
+                 Value *EpilogResumeValue = nullptr,
+                 PHINode *ACR = nullptr,
+                 PHINode *EpilogInduction = nullptr) {
+    AliasCheckResult = ACR;
     // Create a new empty loop. Unlink the old loop and connect the new one.
-    createEmptyLoop();
+    createEmptyLoop(RemainderItrs, EpilogResumeValue,
+                    EpilogInduction);
     // Widen each instruction in the old loop to a new one in the new loop.
     vectorizeLoop();
+    // If multi version is required, generate next VF nersion code.
+    if (canCreateVectorEpilog())
+      createVectorEpilog();
+
   }
 
   // Return true if any runtime check is added.
   bool areSafetyChecksAdded() { return AddedSafetyChecks; }
 
   virtual ~InnerLoopVectorizer() {}
 
 protected:
protected:
   typedef SmallVector<SmallVector<Value *, 4>, 2> ScalarParts;
 
   // When we if-convert we need to create edge masks. We have to cache values
   // so that we don't end up with exponential recursion/IR.
   typedef DenseMap<std::pair<BasicBlock *, BasicBlock *>, VectorParts>
       EdgeMaskCache;
 
   /// Create an empty loop, based on the loop ranges of the old loop.
-  void createEmptyLoop();
+  void createEmptyLoop(Value *RemainderItrs = nullptr,
+                       Value *EpilogResumeValue = nullptr,
+                       PHINode *EpilogInduction = nullptr);
 
   /// Set up the values of the IVs correctly when exiting the vector loop.
   void fixupIVUsers(PHINode *OrigPhi, const InductionDescriptor &II,
                     Value *CountRoundDown, Value *EndValue,
                     BasicBlock *MiddleBlock);
 
   /// Create a new induction variable inside L.
   PHINode *createInductionVariable(Loop *L, Value *Start, Value *End,
protected:
 
   /// Generate a shuffle sequence that will reverse the vector Vec.
   virtual Value *reverseVector(Value *Vec);
 
   /// Returns (and creates if needed) the original loop trip count.
   Value *getOrCreateTripCount(Loop *NewLoop);
 
   /// Returns (and creates if needed) the trip count of the widened loop.
-  Value *getOrCreateVectorTripCount(Loop *NewLoop);
+  Value *getOrCreateVectorTripCount(Loop *NewLoop, bool ReCreateVecTC = false);
 
   /// Emit a bypass check to see if the trip count would overflow, or we
   /// wouldn't have enough iterations to execute one vector loop.
-  void emitMinimumIterationCountCheck(Loop *L, BasicBlock *Bypass);
+  void emitMinimumIterationCountCheck(Loop *L, BasicBlock *Bypass,
+                                      unsigned NewVF = 0,
+                                      Value *KnownTripCount = nullptr);
   /// Emit a bypass check to see if the vector trip count is nonzero.
-  void emitVectorLoopEnteredCheck(Loop *L, BasicBlock *Bypass);
+  void emitVectorLoopEnteredCheck(Loop *L, BasicBlock *Bypass,
+                                  bool ReCreateVecTC = false);
+
   /// 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);
   /// Emit bypass checks to check any memory assumptions we may have made.
-  void emitMemRuntimeChecks(Loop *L, BasicBlock *Bypass);
-
+  BasicBlock* emitMemRuntimeChecks(Loop *L, BasicBlock *Bypass);
+  /// Emit bypass checks by checking runtime alias result.
+  BasicBlock* emitAliasResultCheck(Loop *L, BasicBlock *Bypass, Value *ACR);
   /// Add additional metadata to \p To that was not present on \p Orig.
   ///
   /// Currently this is used to add the noalias annotations based on the
   /// inserted memchecks.  Use this for instructions that are *cloned* into the
   /// vector loop.
   void addNewMetadata(Instruction *To, const Instruction *Orig);
 
   /// Add metadata from one instruction to another.
   ///
   /// This includes both the original MDs from \p From and additional ones (\see
   /// addNewMetadata).  Use this for *newly created* instructions in the vector
   /// loop.
   void addMetadata(Instruction *To, Instruction *From);
 
+  /// Returns true if epilog vectorization is legal.
+  /// Legality is already performed on the loop while first vector
+  /// loop generation, now checking minimal stuff required for versioning.
+  bool canCreateVectorEpilog() {
+    // Epilog vectorization option should be enabled.
+    if (!EnableEpilogVectorization)
+      return false;
+    // Epilog vector should have a valid vector width.
+    if (EpilogVectorLoopWidth == 1)
+      return false;
+    // Loop should have exit block.
+    if (!OrigLoop->getExitBlock())
+      return false;
+    // Loop should have pre header.
+    if (!OrigLoop->getLoopPreheader())
+      return false;
+    return true;
+  }
+
+  // Transform for vector multi versioning.
+  void createVectorEpilog();
+
+  // Create alias check result phinode.
+  PHINode* createAliasCheckResultPHI();
+
+  // Checks feasiblity of vector multi versioning.
+  bool canCreateEpilogVectorLoop(LoopVectorizationLegality &LVL);
+
   /// \brief Similar to the previous function but it adds the metadata to a
   /// vector of instructions.
   void addMetadata(ArrayRef<Value *> To, Instruction *From);
 
   /// \brief Set the debug location in the builder using the debug location in
   /// the instruction.
   void setDebugLocFromInst(IRBuilder<> &B, const Value *Ptr);
 
protected:
   /// A wrapper around ScalarEvolution used to add runtime SCEV checks. Applies
   /// dynamic knowledge to simplify SCEV expressions and converts them to a
   /// more usable form.
   PredicatedScalarEvolution &PSE;
   /// Loop Info.
   LoopInfo *LI;
   /// Dominator Tree.
   DominatorTree *DT;
-  /// Alias Analysis.
-  AliasAnalysis *AA;
   /// Target Library Info.
   const TargetLibraryInfo *TLI;
   /// Target Transform Info.
   const TargetTransformInfo *TTI;
+  /// Alias Analysis.
+  AliasAnalysis *AA;
   /// Assumption Cache.
   AssumptionCache *AC;
   /// Interface to emit optimization remarks.
   OptimizationRemarkEmitter *ORE;
 
   /// \brief LoopVersioning.  It's only set up (non-null) if memchecks were
   /// used.
   ///
protected:
   /// Middle Block between the vector and the scalar.
   BasicBlock *LoopMiddleBlock;
   /// The ExitBlock of the scalar loop.
   BasicBlock *LoopExitBlock;
   /// The vector loop body.
   BasicBlock *LoopVectorBody;
   /// The scalar loop body.
   BasicBlock *LoopScalarBody;
+  /// Alias check block.
+  BasicBlock* AliasCheckBlock;
   /// A list of all bypass blocks. The first block is the entry of the loop.
   SmallVector<BasicBlock *, 4> LoopBypassBlocks;
 
   /// The new Induction variable which was added to the new block.
   PHINode *Induction;
   /// The induction variable of the old basic block.
   PHINode *OldInduction;
 
protected:
   // separately emit induction "steps" when generating code for the new loop.
   // Similarly, we create a new latch condition when setting up the structure
   // of the new loop, so the old one can become dead.
   SmallPtrSet<Instruction *, 4> DeadInstructions;
 
   // Holds the end values for each induction variable. We save the end values
   // so we can later fix-up the external users of the induction variables.
   DenseMap<PHINode *, Value *> IVEndValues;
+  // Epilog vector loop width.
+  unsigned EpilogVectorLoopWidth;
+  /// Scalar block resume value PHINode.
+  PHINode *ScalarResumeValue;
+  /// Alias check result.
+  PHINode *AliasCheckResult;
+  /// Loop access analysis.
+  std::function<const LoopAccessInfo &(Loop &)> *GetLAA;
 };
 
 class InnerLoopUnroller : public InnerLoopVectorizer {
 public:
   InnerLoopUnroller(Loop *OrigLoop, PredicatedScalarEvolution &PSE,
                     LoopInfo *LI, DominatorTree *DT,
                     const TargetLibraryInfo *TLI,
                     const TargetTransformInfo *TTI, AssumptionCache *AC,

 /// single induction variable, that all types are supported and vectorize-able,
 /// etc. This code reflects the capabilities of InnerLoopVectorizer.
 /// This class is also used by InnerLoopVectorizer for identifying
 /// induction variable and the different reduction variables.
 class LoopVectorizationLegality {
 public:
   LoopVectorizationLegality(
       Loop *L, PredicatedScalarEvolution &PSE, DominatorTree *DT,
-      TargetLibraryInfo *TLI, AliasAnalysis *AA, Function *F,
+      const TargetLibraryInfo *TLI, AliasAnalysis *AA, Function *F,
       const TargetTransformInfo *TTI,
       std::function<const LoopAccessInfo &(Loop &)> *GetLAA, LoopInfo *LI,
       OptimizationRemarkEmitter *ORE, LoopVectorizationRequirements *R,
       LoopVectorizeHints *H)
       : NumPredStores(0), TheLoop(L), PSE(PSE), TLI(TLI), TTI(TTI), DT(DT),
         GetLAA(GetLAA), LAI(nullptr), ORE(ORE), InterleaveInfo(PSE, L, DT, LI),
         PrimaryInduction(nullptr), WidestIndTy(nullptr), HasFunNoNaNAttr(false),
         Requirements(R), Hints(H) {}
private:
   Loop *TheLoop;
   /// A wrapper around ScalarEvolution used to add runtime SCEV checks.
   /// Applies dynamic knowledge to simplify SCEV expressions in the context
   /// of existing SCEV assumptions. The analysis will also add a minimal set
   /// of new predicates if this is required to enable vectorization and
   /// unrolling.
   PredicatedScalarEvolution &PSE;
   /// Target Library Info.
-  TargetLibraryInfo *TLI;
+  const TargetLibraryInfo *TLI;
   /// Target Transform Info
   const TargetTransformInfo *TTI;
   /// Dominator Tree.
   DominatorTree *DT;
   // LoopAccess analysis.
   std::function<const LoopAccessInfo &(Loop &)> *GetLAA;
   // And the loop-accesses info corresponding to this loop.  This pointer is
   // null until canVectorizeMemory sets it up.
LoopVectorizationCostModel(Loop *L, PredicatedScalarEvolution &PSE,
                              const LoopVectorizeHints *Hints)
       : TheLoop(L), PSE(PSE), LI(LI), Legal(Legal), TTI(TTI), TLI(TLI), DB(DB),
         AC(AC), ORE(ORE), TheFunction(F), Hints(Hints) {}
 
   /// Information about vectorization costs
   struct VectorizationFactor {
     unsigned Width; // Vector width with best cost
     unsigned Cost;  // Cost of the loop with that width
+    VectorizationFactor() : Width(1), Cost(0) {}
+    VectorizationFactor(unsigned Width, unsigned Cost)
+        : Width(Width), Cost(Cost) {}
   };
   /// \return The most profitable vectorization factor and the cost of that VF.
   /// This method checks every power of two up to VF. If UserVF is not ZERO
   /// then this vectorization factor will be selected if vectorization is
   /// possible.
   VectorizationFactor selectVectorizationFactor(bool OptForSize);
 
+  /// \return The next profitable vector factor after the input vector factor
+  /// If there is not any next profitable vector factor return VectorizationFactor
+  /// with scalar as next possible factor.
+  VectorizationFactor identifyNextProfitableVF(const unsigned IVF);
+
   /// \return The size (in bits) of the smallest and widest types in the code
   /// that needs to be vectorized. We ignore values that remain scalar such as
   /// 64 bit loop indices.
   std::pair<unsigned, unsigned> getSmallestAndWidestTypes();
 
   /// \return The desired interleave count.
   /// If interleave count has been specified by metadata it will be returned.
   /// Otherwise, the interleave count is computed and returned. VF and LoopCost
public:
 
   const Function *TheFunction;
   /// Loop Vectorize Hint.
   const LoopVectorizeHints *Hints;
   /// Values to ignore in the cost model.
   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> ProfitableVF;
 };
 
 /// \brief This holds vectorization requirements that must be verified late in
 /// the process. The requirements are set by legalize and costmodel. Once
 /// vectorization has been determined to be possible and profitable the
 /// requirements can be verified by looking for metadata or compiler options.
 /// For example, some loops require FP commutativity which is only allowed if
 /// vectorization is explicitly specified or if the fast-math compiler option
for (unsigned Lane = 0; Lane < Lanes; ++Lane) {
       // End if-block.
       if (IfPredicateInstr)
         PredicatedInstructions.push_back(std::make_pair(Cloned, Cmp));
     }
   }
   VectorLoopValueMap.initScalar(Instr, Entry);
 }
 
+/// This function will generate PHINode for alias result check in original
+/// scalar loop's preheader block.
+PHINode* InnerLoopVectorizer::createAliasCheckResultPHI() {
+  // Return nullptr if no alias check created previously.
+  if (!AliasCheckBlock)
+    return nullptr;
+  auto &M = *LoopScalarPreHeader->getTerminator()->getFunction()->getParent();
+  auto &Ctx = M.getContext();
+  // Create PHINode for alias check result.
+  PHINode* ACR =
+      PHINode::Create(Type::getInt1Ty(Ctx), 3, "acr.val", ScalarResumeValue);
+  // From middle block set true incoming value.
+  ACR->addIncoming(Builder.getInt1(true), LoopMiddleBlock);
+  // From bypassing blocks set false incoming value.
+  for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I)
+    ACR->addIncoming(Builder.getInt1(false), LoopBypassBlocks[I]);
+  return ACR;
+}
+
+/// Returns true if its feasible to generate vector multi version, else false.
+bool InnerLoopVectorizer::canCreateEpilogVectorLoop(LoopVectorizationLegality &LVL) {
+  // Loop bypass blocks should not be empty.
+  if (!LoopBypassBlocks.size()) {
+    DEBUG(dbgs() << "Loop bypass blocks are empty !\n");
+    return false;
+  }
+  // Unique induction phi node should exist.
+  if (!ScalarResumeValue) {
+    DEBUG(dbgs() << "Unique induction phi node missing !\n");
+    return false;
+  }
+  // Original Trip count & resume value type should be same.
+  if (getOrCreateTripCount(OrigLoop)->getType() != ScalarResumeValue->getType()) {
+    DEBUG(dbgs() << "Type mismatch for resume & tripcount.\n");
+    return false;
+  }
+  // Old Induction variable should exist.
+  if (!OldInduction) {
+    DEBUG(dbgs() << "Scalar loop does not has explicit induction variable.\n");
+    return false;
+  }
+  // Should be legal to vectorize.
+  if (!LVL.canVectorize()) {
+    DEBUG(dbgs() << "MVer-LV: Not vectorizing: Cannot prove legality.\n");
+    return false;
+  }
+  return true;
+}
+
+///   This function will vectorize epilog by generating epilog vector version.
+///   In this function we generate a new loop. The new loop will contain
+///   the vectorized instructions with new vector factor.
+///
+///       [ ] <-- original loop iteration number check.
+///    /   |
+///   /    v
+///  |    [ ] <-- original vector loop bypass (may consist of multiple blocks
+///  |  /  |      having checks like alias checks & scev checks.)
+///  | /   v
+///  ||   [ ]     <-- original vector pre header.
+///  |/    |
+///  |     v
+///  |    [  ] \
+///  |    [  ]_|   <-- original vector loop.
+///  |     |
+///  |     v
+///  |   -[ ]   <--- original middle-block.
+///  |  /  |
+///  | /   v
+///  |----[ ] <-- new version loop iteration number check.
+///   | /  |
+///   |/   v
+///   /   [ ] <-- Previously executed alias result check.
+///  || /  |
+///  ||/   v
+///  |/   [ ]     <-- new vector version pre header.
+///  ||    |
+///  ||    v
+///  ||   [  ] \
+///  ||   [  ]_|   <-- new vector loop.
+///  ||    |
+///  ||    v
+///  ||  -[ ]   <--- new middle-block.
+///  || /  |
+///  | /   v
+///  -|- >[ ]     <--- scalar preheader.
+///   |    |
+///   |    v
+///   |   [ ] \
+///   |   [ ]_|   <-- scalar loop to handle remainder.
+///    \   |
+///     \  v
+///      >[ ]     <-- exit block.
+///   ...
+///
+void InnerLoopVectorizer::createVectorEpilog() {
+  // Create instance of LoopVectorizationLegality.
+  Function *F = LoopScalarPreHeader->getParent();
+  LoopVectorizationRequirements Requirements(*ORE);
+  LoopVectorizeHints Hints(OrigLoop, true, *ORE);
+  LoopVectorizationLegality MVLVL(OrigLoop, PSE, DT, TLI, AA, F, TTI, GetLAA,
+                                  LI, ORE, &Requirements, &Hints);
+  // Check if its legal to do vector multi versioning.
+  if (!canCreateEpilogVectorLoop(MVLVL)) {
+    DEBUG(dbgs() << "Epilog vectorization unable to prove legality !\n");
+    return;
+  }
+  DEBUG(dbgs() << "Epilog vectorization is beneficial with width : "
+               << EpilogVectorLoopWidth << " in Function: "
+               << LoopScalarPreHeader->getParent()->getName() << "\n");
+  // Create PHINode for alias check execution result.
+  AliasCheckResult = createAliasCheckResultPHI();
+  // Identify remaining number of iterations.
+  IRBuilder<> ResumeBuilder(&*LoopScalarPreHeader->getTerminator());
+  Value *RemainderItrs = ResumeBuilder.CreateSub(getOrCreateTripCount(OrigLoop),
+                                                 ScalarResumeValue, "rem.itrs");
+  // Create instance of inner loop vectorizer & vectorize.
+  InnerLoopVectorizer LB(OrigLoop, PSE, LI, DT, TLI, TTI, AC, ORE,
+                         EpilogVectorLoopWidth, 1, &MVLVL, Cost);
+  LB.vectorize(RemainderItrs, ScalarResumeValue,
+               AliasCheckResult, OldInduction);
+}
+
+
 PHINode *InnerLoopVectorizer::createInductionVariable(Loop *L, Value *Start,
                                                       Value *End, Value *Step,
                                                       Instruction *DL) {
   BasicBlock *Header = L->getHeader();
   BasicBlock *Latch = L->getLoopLatch();
   // As we're just creating this loop, it's possible no latch exists
   // yet. If so, use the header as this will be a single block loop.
   if (!Latch)
Value *InnerLoopVectorizer::getOrCreateTripCount(Loop *L) {
   if (TripCount->getType()->isPointerTy())
     TripCount =
         CastInst::CreatePointerCast(TripCount, IdxTy, "exitcount.ptrcnt.to.int",
                                     L->getLoopPreheader()->getTerminator());
 
   return TripCount;
 }
 
-Value *InnerLoopVectorizer::getOrCreateVectorTripCount(Loop *L) {
-  if (VectorTripCount)
+Value *InnerLoopVectorizer::getOrCreateVectorTripCount(Loop *L,
+                                                       bool ReCreateVecTC) {
+  if (!ReCreateVecTC && VectorTripCount)
     return VectorTripCount;
 
   Value *TC = getOrCreateTripCount(L);
   IRBuilder<> Builder(L->getLoopPreheader()->getTerminator());
 
   // Now we need to generate the expression for the part of the loop that the
   // vectorized body will execute. This is equal to N - (N % Step) if scalar
   // iterations are not required for correctness, or N - Step, otherwise. Step
if (VF > 1 && Legal->requiresScalarEpilogue()) {
     R = Builder.CreateSelect(IsZero, Step, R);
   }
 
   VectorTripCount = Builder.CreateSub(TC, R, "n.vec");
 
   return VectorTripCount;
 }
 
-void InnerLoopVectorizer::emitMinimumIterationCountCheck(Loop *L,
-                                                         BasicBlock *Bypass) {
-  Value *Count = getOrCreateTripCount(L);
+void InnerLoopVectorizer::emitMinimumIterationCountCheck(
+    Loop *L, BasicBlock *Bypass, unsigned NewVF, Value *KnownTripCount) {
+  // If its a known trip count then use it.
+  Value *Count = KnownTripCount ? KnownTripCount : getOrCreateTripCount(L);
+  // Minimum iteration count.
+  unsigned MinItrsCount = NewVF ? NewVF : (VF * UF);
   BasicBlock *BB = L->getLoopPreheader();
   IRBuilder<> Builder(BB->getTerminator());
 
   // Generate code to check that the loop's trip count that we computed by
   // adding one to the backedge-taken count will not overflow.
   Value *CheckMinIters = Builder.CreateICmpULT(
-      Count, ConstantInt::get(Count->getType(), VF * UF), "min.iters.check");
+      Count, ConstantInt::get(Count->getType(), MinItrsCount),
+      "min.iters.check");
 
   BasicBlock *NewBB =
       BB->splitBasicBlock(BB->getTerminator(), "min.iters.checked");
   // Update dominator tree immediately if the generated block is a
   // LoopBypassBlock because SCEV expansions to generate loop bypass
   // checks may query it before the current function is finished.
   DT->addNewBlock(NewBB, BB);
   if (L->getParentLoop())
     L->getParentLoop()->addBasicBlockToLoop(NewBB, *LI);
   ReplaceInstWithInst(BB->getTerminator(),
                       BranchInst::Create(Bypass, NewBB, CheckMinIters));
   LoopBypassBlocks.push_back(BB);
 }
 
 void InnerLoopVectorizer::emitVectorLoopEnteredCheck(Loop *L,
-                                                     BasicBlock *Bypass) {
-  Value *TC = getOrCreateVectorTripCount(L);
+                                                     BasicBlock *Bypass,
+                                                     bool ReCreateVecTC) {
+  Value *TC = getOrCreateVectorTripCount(L, ReCreateVecTC);
   BasicBlock *BB = L->getLoopPreheader();
   IRBuilder<> Builder(BB->getTerminator());
 
   // Now, compare the new count to zero. If it is zero skip the vector loop and
   // jump to the scalar loop.
   Value *Cmp = Builder.CreateICmpEQ(TC, Constant::getNullValue(TC->getType()),
                                     "cmp.zero");
 
void InnerLoopVectorizer::emitSCEVChecks(Loop *L, BasicBlock *Bypass) {
   if (L->getParentLoop())
     L->getParentLoop()->addBasicBlockToLoop(NewBB, *LI);
   ReplaceInstWithInst(BB->getTerminator(),
                       BranchInst::Create(Bypass, NewBB, SCEVCheck));
   LoopBypassBlocks.push_back(BB);
   AddedSafetyChecks = true;
 }
 
-void InnerLoopVectorizer::emitMemRuntimeChecks(Loop *L, BasicBlock *Bypass) {
+BasicBlock* InnerLoopVectorizer::emitMemRuntimeChecks(Loop *L,
+                                                      BasicBlock *Bypass) {
   BasicBlock *BB = L->getLoopPreheader();
 
   // 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.
   Instruction *FirstCheckInst;
   Instruction *MemRuntimeCheck;
   std::tie(FirstCheckInst, MemRuntimeCheck) =
       Legal->getLAI()->addRuntimeChecks(BB->getTerminator());
   if (!MemRuntimeCheck)
-    return;
+    return nullptr;
 
   // Create a new block containing the memory check.
   BB->setName("vector.memcheck");
   auto *NewBB = BB->splitBasicBlock(BB->getTerminator(), "vector.ph");
   // Update dominator tree immediately if the generated block is a
   // LoopBypassBlock because SCEV expansions to generate loop bypass
   // checks may query it before the current function is finished.
   DT->addNewBlock(NewBB, BB);
   if (L->getParentLoop())
     L->getParentLoop()->addBasicBlockToLoop(NewBB, *LI);
   ReplaceInstWithInst(BB->getTerminator(),
                       BranchInst::Create(Bypass, NewBB, MemRuntimeCheck));
   LoopBypassBlocks.push_back(BB);
   AddedSafetyChecks = true;
 
   // We currently don't use LoopVersioning for the actual loop cloning but we
   // still use it to add the noalias metadata.
   LVer = llvm::make_unique<LoopVersioning>(*Legal->getLAI(), OrigLoop, LI, DT,
-                                           PSE.getSE());
+                                           PSE.getSE(), true, true);
   LVer->prepareNoAliasMetadata();
+  // Return alias check basic block.
+  return BB;
 }
 
-void InnerLoopVectorizer::createEmptyLoop() {
+/// Generate a check for alias check result, if alias check is executed
+/// with no-alias result then jump to epilog loop min iteration check
+/// else jump to scalar loop.
+BasicBlock *InnerLoopVectorizer::emitAliasResultCheck(Loop *L,
+                                                      BasicBlock *Bypass,
+                                                      Value *ACR) {
+
+  BasicBlock *BB = L->getLoopPreheader();
+  // Create a new block containing the memory check.
+  BB->setName("alias.result.chk");
+  auto *NewBB = BB->splitBasicBlock(BB->getTerminator(), "vector.ph");
+  // Update dominator tree immediately if the generated block is a
+  // LoopBypassBlock because SCEV expansions to generate loop bypass
+  // checks may query it before the current function is finished.
+  DT->addNewBlock(NewBB, BB);
+  if (L->getParentLoop())
+    L->getParentLoop()->addBasicBlockToLoop(NewBB, *LI);
+  ReplaceInstWithInst(BB->getTerminator(),
+                      BranchInst::Create(NewBB, Bypass, ACR));
+  LoopBypassBlocks.push_back(BB);
+
+  // We currently don't use LoopVersioning for the actual loop cloning but we
+  // still use it to add the noalias metadata.
+  LVer = llvm::make_unique<LoopVersioning>(*Legal->getLAI(), OrigLoop, LI, DT,
+                                           PSE.getSE(), true, true);
+  LVer->prepareNoAliasMetadata();
+  return BB;
+}
+
+void InnerLoopVectorizer::createEmptyLoop(Value *RemainderItrs,
+                                          Value *EpilogResumeValue,
+                                          PHINode *EpilogInduction) {
   /*
    In this function we generate a new loop. The new loop will contain
    the vectorized instructions while the old loop will continue to run the
    scalar remainder.
 
        [ ] <-- loop iteration number check.
     /   |
    /    v
void InnerLoopVectorizer::createEmptyLoop(Value *RemainderItrs,
   // don't have a single induction variable.
   //
   // We try to obtain an induction variable from the original loop as hard
   // as possible. However if we don't find one that:
   //   - is an integer
   //   - counts from zero, stepping by one
   //   - is the size of the widest induction variable type
   // then we create a new one.
-  OldInduction = Legal->getPrimaryInduction();
+  OldInduction =
+      EpilogInduction ? EpilogInduction : Legal->getPrimaryInduction();
   Type *IdxTy = Legal->getWidestInductionType();
 
   // Split the single block loop into the two loop structure described above.
   BasicBlock *VecBody =
       VectorPH->splitBasicBlock(VectorPH->getTerminator(), "vector.body");
   BasicBlock *MiddleBlock =
       VecBody->splitBasicBlock(VecBody->getTerminator(), "middle.block");
   BasicBlock *ScalarPH =
void InnerLoopVectorizer::createEmptyLoop(Value *RemainderItrs,
   }
   Lp->addBasicBlockToLoop(VecBody, *LI);
 
   // Find the loop boundaries.
   Value *Count = getOrCreateTripCount(Lp);
 
   Value *StartIdx = ConstantInt::get(IdxTy, 0);
 
-  // We need to test whether the backedge-taken count is uint##_max. Adding one
-  // to it will cause overflow and an incorrect loop trip count in the vector
-  // body. In case of overflow we want to directly jump to the scalar remainder
-  // loop.
+  if (RemainderItrs) {
+    // Create minimum iteration check against remaining iterations.
+    emitMinimumIterationCountCheck(Lp, ScalarPH, VF, RemainderItrs);
+    // Now, compare the new count to zero.
+    // If it is zero skip the vector loop and jump to the scalar loop.
+    // Enfore recreation of vector trip count.
+    emitVectorLoopEnteredCheck(Lp, ScalarPH, true);
+  } else {
+    // We need to test whether the backedge-taken count is uint##_max.
+    // Adding one to it will cause overflow and an incorrect loop trip count
+    // in the vector body. In case of overflow we want to directly jump to the
+    // scalar remainder loop.
     emitMinimumIterationCountCheck(Lp, ScalarPH);
-  // Now, compare the new count to zero. If it is zero skip the vector loop and
-  // jump to the scalar loop.
+    // Now, compare the new count to zero. If it is zero skip the vector loop
+    // and jump to the scalar loop.
     emitVectorLoopEnteredCheck(Lp, ScalarPH);
+  }
+
   // Generate the code to check any assumptions that we've made for SCEV
   // expressions.
   emitSCEVChecks(Lp, ScalarPH);
 
   // 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.
-  emitMemRuntimeChecks(Lp, ScalarPH);
-
+  // If alias check is already executed decide based on its result,
+  // else generate runtime alias check.
+  BasicBlock *RuntimeCheckBlock = nullptr;
+  if (AliasCheckResult) {
+    RuntimeCheckBlock = emitAliasResultCheck(Lp, ScalarPH, AliasCheckResult);
+  } else {
+    RuntimeCheckBlock = emitMemRuntimeChecks(Lp, ScalarPH);
+  }
   // Generate the induction variable.
   // The loop step is equal to the vectorization factor (num of SIMD elements)
   // times the unroll factor (num of SIMD instructions).
   Value *CountRoundDown = getOrCreateVectorTripCount(Lp);
   Constant *Step = ConstantInt::get(IdxTy, VF * UF);
-  Induction =
-      createInductionVariable(Lp, StartIdx, CountRoundDown, Step,
+  if (EpilogResumeValue) {
+    Induction = createInductionVariable(Lp, EpilogResumeValue,
+                               CountRoundDown, Step,
                                getDebugLocFromInstOrOperands(OldInduction));
-
+  } else {
+    Induction = createInductionVariable(Lp, StartIdx, CountRoundDown, Step,
+                                getDebugLocFromInstOrOperands(OldInduction));
+  }
   // We are going to resume the execution of the scalar loop.
   // Go over all of the induction variables that we found and fix the
   // PHIs that are left in the scalar version of the loop.
   // The starting values of PHI nodes depend on the counter of the last
   // iteration in the vectorized loop.
   // If we come from a bypass edge then we need to start from the original
   // start value.
 
   // This variable saves the new starting index for the scalar loop. It is used
   // to test if there are any tail iterations left once the vector loop has
   // completed.
+  ScalarResumeValue = nullptr;
   LoopVectorizationLegality::InductionList *List = Legal->getInductionVars();
   for (auto &InductionEntry : *List) {
     PHINode *OrigPhi = InductionEntry.first;
     InductionDescriptor II = InductionEntry.second;
 
     // Create phi nodes to merge from the  backedge-taken check block.
     PHINode *BCResumeVal = PHINode::Create(
         OrigPhi->getType(), 3, "bc.resume.val", ScalarPH->getTerminator());
for (auto &InductionEntry : *List) {
     // or the value at the end of the vectorized loop.
     BCResumeVal->addIncoming(EndValue, MiddleBlock);
 
     // Fix the scalar body counter (PHI node).
     unsigned BlockIdx = OrigPhi->getBasicBlockIndex(ScalarPH);
 
     // The old induction's phi node in the scalar body needs the truncated
     // value.
-    for (BasicBlock *BB : LoopBypassBlocks)
-      BCResumeVal->addIncoming(II.getStartValue(), BB);
+    if (EpilogResumeValue) {
+      for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I)
+        BCResumeVal->addIncoming(EpilogResumeValue, LoopBypassBlocks[I]);
+    } else {
+      for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I)
+        BCResumeVal->addIncoming(II.getStartValue(), LoopBypassBlocks[I]);
+    }
     OrigPhi->setIncomingValue(BlockIdx, BCResumeVal);
+    ScalarResumeValue = BCResumeVal;
   }
 
+  // NOTE: Currently multiple induction variables not supported as multiple
+  // induction variable incurs multiple checks which may not be profitable.
+  if (List->size() > 1)
+    ScalarResumeValue = nullptr;
+
   // Add a check in the middle block to see if we have completed
   // all of the iterations in the first vector loop.
   // If (N - N%VF) == N, then we *don't* need to run the remainder.
   Value *CmpN =
       CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_EQ, Count,
                       CountRoundDown, "cmp.n", MiddleBlock->getTerminator());
   ReplaceInstWithInst(MiddleBlock->getTerminator(),
                       BranchInst::Create(ExitBlock, ScalarPH, CmpN));
 
   // Get ready to start creating new instructions into the vectorized body.
   Builder.SetInsertPoint(&*VecBody->getFirstInsertionPt());
 
   // Save the state.
   LoopVectorPreHeader = Lp->getLoopPreheader();
   LoopScalarPreHeader = ScalarPH;
   LoopMiddleBlock = MiddleBlock;
   LoopExitBlock = ExitBlock;
   LoopVectorBody = VecBody;
   LoopScalarBody = OldBasicBlock;
+  AliasCheckBlock = RuntimeCheckBlock;
 
   // Keep all loop hints from the original loop on the vector loop (we'll
   // replace the vectorizer-specific hints below).
   if (MDNode *LID = OrigLoop->getLoopID())
     Lp->setLoopID(LID);
 
   LoopVectorizeHints Hints(Lp, true, *ORE);
   Hints.setAlreadyVectorized();
void InnerLoopVectorizer::vectorizeBlockInLoop(BasicBlock *BB, PhiVector *PV) {
   }   // end of for_each instr.
 }
 
 void InnerLoopVectorizer::updateAnalysis() {
   // Forget the original basic block.
   PSE.getSE()->forgetLoop(OrigLoop);
 
   // Update the dominator tree information.
+  // With epilog vectorization not all loop bypass blocks dominates exit blocks.
+  if (!EnableEpilogVectorization)
     assert(DT->properlyDominates(LoopBypassBlocks.front(), LoopExitBlock) &&
            "Entry does not dominate exit.");
 
   // We don't predicate stores by this point, so the vector body should be a
   // single loop.
   DT->addNewBlock(LoopVectorBody, LoopVectorPreHeader);
 
   DT->addNewBlock(LoopMiddleBlock, LoopVectorBody);
   DT->addNewBlock(LoopScalarPreHeader, LoopBypassBlocks[0]);
   DT->changeImmediateDominator(LoopScalarBody, LoopScalarPreHeader);
+  // Change immedeate dominator only when:
+  // 1) When epilog vectorization is disabled.
+  // 2) When epilog vectorization is enabled and EpilogVectorLoopWidth
+  //    is not 1, this is when generating original vector version.
+  //    EpilogVectorLoopWidth will be 1 while generating epilog vector
+  //    version.
+  if (!EnableEpilogVectorization || EpilogVectorLoopWidth != 1)
     DT->changeImmediateDominator(LoopExitBlock, LoopBypassBlocks[0]);
 
   DEBUG(DT->verifyDomTree());
 }
 
 /// \brief Check whether it is safe to if-convert this phi node.
 ///
 /// Phi nodes with constant expressions that can trap are not safe to if
 /// convert.
if (LastMember) {
         continue;
       }
       DEBUG(dbgs() << "LV: Interleaved group requires epilogue iteration.\n");
       RequiresScalarEpilogue = true;
     }
   }
 }
 
+/// Identify epilog vector loop width from profitable VF's.
+LoopVectorizationCostModel::VectorizationFactor
+LoopVectorizationCostModel::identifyNextProfitableVF(const unsigned Width) {
+  // Find next VF.
+  unsigned VF = 1;
+  unsigned Cost = 0;
+  bool hasMultipleInductionVariables = (Legal->getInductionVars()->size() != 1);
+  // Check the loop vector width should be more than min width threshold.
+  if (Width < MinWidthEpilogVectorization)
+    return VectorizationFactor(VF, Cost);
+  // Return if epilog vectorization option not provided.
+  // NOTE: Currently multiple induction variables not supported as multiple
+  // induction variable incurs multiple checks which may not be profitable.
+  if (!EnableEpilogVectorization || hasMultipleInductionVariables)
+    return VectorizationFactor(VF, Cost);
+  // Identify next profitable VF.
+  for (auto &NextVF : ProfitableVF)
+    // NOTE: VF's in ProfitableVF is in accesding order.
+    if ((NextVF.Width < Width) && (VF == 1 || NextVF.Cost < Cost)) {
+      VF = NextVF.Width;
+      Cost = NextVF.Cost;
+    }
+  return VectorizationFactor(VF, Cost);
+}
+
 LoopVectorizationCostModel::VectorizationFactor
 LoopVectorizationCostModel::selectVectorizationFactor(bool OptForSize) {
   // Width 1 means no vectorize
   VectorizationFactor Factor = {1U, 0U};
   if (OptForSize && Legal->getRuntimePointerChecking()->Need) {
     ORE->emit(createMissedAnalysis("CantVersionLoopWithOptForSize")
               << "runtime pointer checks needed. Enable vectorization of this "
                  "loop with '#pragma clang loop vectorize(enable)' when "
for (unsigned i = 2; i <= VF; i *= 2) {
     DEBUG(dbgs() << "LV: Vector loop of width " << i
                  << " costs: " << (int)VectorCost << ".\n");
     if (!C.second && !ForceVectorization) {
       DEBUG(
           dbgs() << "LV: Not considering vector loop of width " << i
                  << " because it will not generate any vector instructions.\n");
       continue;
     }
+    // If profitable add it to ProfitableVF list.
+    if (VectorCost < ScalarCost)
+      ProfitableVF.push_back(VectorizationFactor(i, VectorCost));
     if (VectorCost < Cost) {
       Cost = VectorCost;
       Width = i;
     }
   }
 
   DEBUG(if (ForceVectorization && Width > 1 && Cost >= ScalarCost) dbgs()
         << "LV: Vectorization seems to be not beneficial, "
ORE->emit(OptimizationRemarkAnalysis(LV_NAME, IntDiagMsg.first,
               << IntDiagMsg.second);
   } else if (VectorizeLoop && InterleaveLoop) {
     DEBUG(dbgs() << "LV: Found a vectorizable loop (" << VF.Width << ") in "
                  << DebugLocStr << '\n');
     DEBUG(dbgs() << "LV: Interleave Count is " << IC << '\n');
   }
 
   using namespace ore;
+  // Identify multi version loop width
+  const LoopVectorizationCostModel::VectorizationFactor EpilogVF =
+      CM.identifyNextProfitableVF(VF.Width);
   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);
     Unroller.vectorize();
 
     ORE->emit(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.
     InnerLoopVectorizer LB(L, PSE, LI, DT, TLI, TTI, AC, ORE, VF.Width, IC,
-                           &LVL, &CM);
+                           &LVL, &CM, EpilogVF.Width, GetLAA, AA);
     LB.vectorize();
     ++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
     // rarely used is not worth unrolling.
     if (!LB.areSafetyChecksAdded())
       AddRuntimeUnrollDisableMetaData(L);