//===-------------------- MultiExitLoopVectorizer.h -----------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//====  Copyright (c) 2015 Advanced Micro Devices, Inc.  All rights reserved.
//
//               Developed by: Advanced Micro Devices, Inc.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal 
// with the Software without restriction, including without limitation the 
// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or 
// sell copies of the Software, and to permit persons to whom the Software is 
// furnished to do so, subject to the following conditions:
//
// Redistributions of source code must retain the above copyright notice, this 
// list of conditions and the following disclaimers.
//
// Redistributions in binary form must reproduce the above copyright notice, 
// this list of conditions and the following disclaimers in the documentation 
// and/or other materials provided with the distribution.
//
// Neither the names of Advanced Micro Devices, Inc., nor the names of its 
// contributors may be used to endorse or promote products derived from this 
// Software without specific prior written permission.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
// CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH 
// THE SOFTWARE.
//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_VECTORIZE_MELV_H
#define LLVM_TRANSFORMS_VECTORIZE_MELV_H

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Analysis/CodeMetrics.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/IntrinsicsX86.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Pass.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopSimplify.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/LoopVersioning.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
#include "llvm/Transforms/Utils/SafeLibFuncsUtil.h"
#include "llvm/Transforms/Vectorize.h"
#include "llvm/Transforms/Vectorize/LoopVectorize.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include <map>

#define LV_NAME "melv-vectorize"
#define DEBUG_TYPE LV_NAME

using namespace llvm;

/// Maximum vectorization interleave count.
static const unsigned MELVMaxInterleaveFactor = 16;

/// Maximum factor for an interleaved memory access.
extern llvm::cl::opt<unsigned> MELVMaxInterleaveGroupFactor;

namespace melv {
class LoopVectorizeHints;
class LoopVectorizationLegality;
class LoopVectorizationRequirements;

/// A helper function that returns the type of loaded or stored value.
static Type *getMemInstValueType(Value *I) {
  assert((isa<LoadInst>(I) || isa<StoreInst>(I)) &&
         "Expected Load or Store instruction");
  if (auto *LI = dyn_cast<LoadInst>(I))
    return LI->getType();
  return cast<StoreInst>(I)->getValueOperand()->getType();
}

/// \brief The group of interleaved loads/stores sharing the same stride and
/// close to each other.
///
/// Each member in this group has an index starting from 0, and the largest
/// index should be less than interleaved factor, which is equal to the absolute
/// value of the access's stride.
///
/// E.g. An interleaved load group of factor 4:
///        for (unsigned i = 0; i < 1024; i+=4) {
///          a = A[i];                           // Member of index 0
///          b = A[i+1];                         // Member of index 1
///          d = A[i+3];                         // Member of index 3
///          ...
///        }
///
///      An interleaved store group of factor 4:
///        for (unsigned i = 0; i < 1024; i+=4) {
///          ...
///          A[i]   = a;                         // Member of index 0
///          A[i+1] = b;                         // Member of index 1
///          A[i+2] = c;                         // Member of index 2
///          A[i+3] = d;                         // Member of index 3
///        }
///
/// Note: the interleaved load group could have gaps (missing members), but
/// the interleaved store group doesn't allow gaps.
class InterleaveGroup {
public:
  InterleaveGroup(Instruction *Instr, int Stride, unsigned Align)
      : Align(Align), SmallestKey(0), LargestKey(0), InsertPos(Instr) {
    assert(Align && "The alignment should be non-zero");

    Factor = std::abs(Stride);
    assert(Factor > 1 && "Invalid interleave factor");

    Reverse = Stride < 0;
    Members[0] = Instr;
  }

  bool isReverse() const { return Reverse; }
  unsigned getFactor() const { return Factor; }
  unsigned getAlignment() const { return Align; }
  unsigned getNumMembers() const { return Members.size(); }

  /// \brief Try to insert a new member \p Instr with index \p Index and
  /// alignment \p NewAlign. The index is related to the leader and it could be
  /// negative if it is the new leader.
  ///
  /// \returns false if the instruction doesn't belong to the group.
  bool insertMember(Instruction *Instr, int Index, unsigned NewAlign) {
    assert(NewAlign && "The new member's alignment should be non-zero");

    int Key = Index + SmallestKey;

    // Skip if there is already a member with the same index.
    if (Members.count(Key))
      return false;

    if (Key > LargestKey) {
      // The largest index is always less than the interleave factor.
      if (Index >= static_cast<int>(Factor))
        return false;

      LargestKey = Key;
    } else if (Key < SmallestKey) {
      // The largest index is always less than the interleave factor.
      if (LargestKey - Key >= static_cast<int>(Factor))
        return false;

      SmallestKey = Key;
    }

    // It's always safe to select the minimum alignment.
    Align = std::min(Align, NewAlign);
    Members[Key] = Instr;
    return true;
  }

  /// \brief Get the member with the given index \p Index
  ///
  /// \returns nullptr if contains no such member.
  Instruction *getMember(unsigned Index) const {
    int Key = SmallestKey + Index;
    if (!Members.count(Key))
      return nullptr;

    return Members.find(Key)->second;
  }

  /// \brief Get the index for the given member. Unlike the key in the member
  /// map, the index starts from 0.
  unsigned getIndex(Instruction *Instr) const {
    for (auto I : Members)
      if (I.second == Instr)
        return I.first - SmallestKey;

    llvm_unreachable("InterleaveGroup contains no such member");
  }

  Instruction *getInsertPos() const { return InsertPos; }
  void setInsertPos(Instruction *Inst) { InsertPos = Inst; }

private:
  unsigned Factor; // Interleave Factor.
  bool Reverse;
  unsigned Align;
  DenseMap<int, Instruction *> Members;
  int SmallestKey;
  int LargestKey;

  // To avoid breaking dependences, vectorized instructions of an interleave
  // group should be inserted at either the first load or the last store in
  // program order.
  //
  // E.g. %even = load i32             // Insert Position
  //      %add = add i32 %even         // Use of %even
  //      %odd = load i32
  //
  //      store i32 %even
  //      %odd = add i32               // Def of %odd
  //      store i32 %odd               // Insert Position
  Instruction *InsertPos;
};

/// \brief The descriptor for a strided memory access.
struct StrideDescriptor {
  StrideDescriptor(int Stride, const SCEV *Scev, unsigned Size, unsigned Align)
      : Stride(Stride), Scev(Scev), Size(Size), Align(Align) {}

  StrideDescriptor() : Stride(0), Scev(nullptr), Size(0), Align(0) {}

  int Stride;       // The access's stride. It is negative for a reverse access.
  const SCEV *Scev; // The scalar expression of this access
  unsigned Size;    // The size of the memory object.
  unsigned Align;   // The alignment of this access.
};

class MEStrideAccessInfo {
public:
  const Instruction *MemAccessInstr;
  StrideDescriptor &SD;
  bool hasValidStride;
  ScalarEvolution *SE;
  Loop *CurLoop;
  LoopInfo *LInfo;
  SmallVector<const Instruction *, 8> DependentInstr;

  MEStrideAccessInfo(const Instruction *MemAccessInstr, StrideDescriptor &SD,
                   ScalarEvolution *SE, Loop *CurLoop, LoopInfo *LInfo)
      : MemAccessInstr(MemAccessInstr), SD(SD), hasValidStride(false), SE(SE),
        CurLoop(CurLoop), LInfo(LInfo) {
    analyzeStride(MemAccessInstr);
  }

  void insertDependentInstr(const Instruction *I) {
    DependentInstr.push_back(I);
  }

  SmallVector<const Instruction *, 8> &getDependentInstr(const Instruction *I) {
    return DependentInstr;
  }

  bool isValidStrideOperationMelv() const;
  bool mevalidateStrideOperation(Instruction *I);
  void analyzeStride(const Instruction *);

  void print() const {
    dbgs() << "Memory Instruction : ";
    MemAccessInstr->dump();
    dbgs() << "Has dependent Instr \n";
    SmallVector<const Instruction *, 8>::const_iterator I, E;
    for (I = DependentInstr.begin(), E = DependentInstr.end(); I != E; ++I) {
      dbgs() << "    ";
      (*I)->dump();
      dbgs() << "\n";
    }
  }
};

/// \brief Drive the analysis of interleaved memory accesses in the loop.
///
/// Use this class to analyze interleaved accesses only when we can vectorize
/// a loop. Otherwise it's meaningless to do analysis as the vectorization
/// on interleaved accesses is unsafe.
///
/// The analysis collects interleave groups and records the relationships
/// between the member and the group in a map.
class MEInterleavedAccessInfo {
public:
  MEInterleavedAccessInfo(PredicatedScalarEvolution &PSE, Loop *L,
                        DominatorTree *DT, LoopInfo *LI)
      : PSE(PSE), TheLoop(L), DT(DT), LI(LI), LAI(nullptr),
        RequiresScalarEpilogue(false) {}

  ~MEInterleavedAccessInfo() {
    SmallSet<InterleaveGroup *, 4> DelSet;
    // Avoid releasing a pointer twice.
    for (auto &I : InterleaveGroupMap)
      DelSet.insert(I.second);
    for (auto *Ptr : DelSet)
      delete Ptr;
  }

  /// \brief Analyze the interleaved accesses and collect them in interleave
  /// groups. Substitute symbolic strides using \p Strides.
  void analyzeInterleaving(const DenseMap<Value *, const SCEV *> &Strides, LoopInfo *LInfo);

  /// \brief Check if \p Instr belongs to any interleave group.
  bool isInterleaved(Instruction *Instr) const {
    return InterleaveGroupMap.count(Instr);
  }

  /// \brief Return the maximum interleave factor of all interleaved groups.
  unsigned getMaxInterleaveFactor() const {
    unsigned MaxFactor = 1;
    for (auto &Entry : InterleaveGroupMap)
      MaxFactor = std::max(MaxFactor, Entry.second->getFactor());
    return MaxFactor;
  }

  /// \brief Get the interleave group that \p Instr belongs to.
  ///
  /// \returns nullptr if doesn't have such group.
  InterleaveGroup *getInterleaveGroup(Instruction *Instr) const {
    if (InterleaveGroupMap.count(Instr))
      return InterleaveGroupMap.find(Instr)->second;
    return nullptr;
  }

  /// For a strided memory access, it returns true if hold valid stride
  /// operation, else it returns false.
  bool isValidStrideOperationMelv(Instruction *I) {
    MapVector<Instruction *, const MEStrideAccessInfo>::iterator It =
        StrideInfo.find(I);
    if (It != StrideInfo.end())
      return It->second.isValidStrideOperationMelv();
    return false;
  }

  /// Holds instruction & its stride access information.
  MapVector<Instruction *, const MEStrideAccessInfo> StrideInfo;
  /// \brief Returns true if an interleaved group that may access memory
  /// out-of-bounds requires a scalar epilogue iteration for correctness.
  bool requiresScalarEpilogue() const { return RequiresScalarEpilogue; }

  /// \brief Initialize the LoopAccessInfo used for dependence checking.
  void setLAI(const LoopAccessInfo *Info) { LAI = Info; }

private:
  /// A wrapper around ScalarEvolution, used to add runtime SCEV checks.
  /// Simplifies SCEV expressions in the context of existing SCEV assumptions.
  /// The interleaved access analysis can also add new predicates (for example
  /// by versioning strides of pointers).
  PredicatedScalarEvolution &PSE;
  Loop *TheLoop;
  DominatorTree *DT;
  LoopInfo *LI;
  const LoopAccessInfo *LAI;

  /// True if the loop may contain non-reversed interleaved groups with
  /// out-of-bounds accesses. We ensure we don't speculatively access memory
  /// out-of-bounds by executing at least one scalar epilogue iteration.
  bool RequiresScalarEpilogue;

  /// Holds the relationships between the members and the interleave group.
  DenseMap<Instruction *, InterleaveGroup *> InterleaveGroupMap;

  /// Holds dependences among the memory accesses in the loop. It maps a source
  /// access to a set of dependent sink accesses.
  DenseMap<Instruction *, SmallPtrSet<Instruction *, 2>> Dependences;

  /// \brief A type for holding instructions and their stride descriptors.
  typedef std::pair<Instruction *, StrideDescriptor> StrideEntry;

  /// \brief Create a new interleave group with the given instruction \p Instr,
  /// stride \p Stride and alignment \p Align.
  ///
  /// \returns the newly created interleave group.
  InterleaveGroup *createInterleaveGroup(Instruction *Instr, int Stride,
                                         unsigned Align) {
    assert(!InterleaveGroupMap.count(Instr) &&
           "Already in an interleaved access group");
    InterleaveGroupMap[Instr] = new InterleaveGroup(Instr, Stride, Align);
    return InterleaveGroupMap[Instr];
  }

  /// \brief Release the group and remove all the relationships.
  void releaseGroup(InterleaveGroup *Group) {
    for (unsigned i = 0; i < Group->getFactor(); i++)
      if (Instruction *Member = Group->getMember(i))
        InterleaveGroupMap.erase(Member);

    delete Group;
  }

  /// \brief Collect all the accesses with a constant stride in program order.
  void collectConstStrideAccesses(
      MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,
      const DenseMap<Value *, const SCEV *> &Strides, LoopInfo *LInfo);

  /// \brief Returns true if \p Stride is allowed in an interleaved group.
  static bool isStrided(int Stride) {
    unsigned Factor = std::abs(Stride);
    return Factor >= 2 && Factor <= MELVMaxInterleaveGroupFactor;
  }

  /// \brief Returns true if \p BB is a predicated block.
  bool isPredicated(BasicBlock *BB) const {
    return LoopAccessInfo::blockNeedsPredication(BB, TheLoop, DT);
  }

  /// \brief Returns true if LoopAccessInfo can be used for dependence queries.
  bool areDependencesValid() const {
    return LAI && LAI->getDepChecker().getDependences();
  }

  /// \brief Returns true if memory accesses \p A and \p B can be reordered, if
  /// necessary, when constructing interleaved groups.
  ///
  /// \p A must precede \p B in program order. We return false if reordering is
  /// not necessary or is prevented because \p A and \p B may be dependent.
  bool canReorderMemAccessesForInterleavedGroups(StrideEntry *A,
                                                 StrideEntry *B) const {

    // Code motion for interleaved accesses can potentially hoist strided loads
    // and sink strided stores. The code below checks the legality of the
    // following two conditions:
    //
    // 1. Potentially moving a strided load (B) before any store (A) that
    //    precedes B, or
    //
    // 2. Potentially moving a strided store (A) after any load or store (B)
    //    that A precedes.
    //
    // It's legal to reorder A and B if we know there isn't a dependence from A
    // to B. Note that this determination is conservative since some
    // dependences could potentially be reordered safely.

    // A is potentially the source of a dependence.
    auto *Src = A->first;
    auto SrcDes = A->second;

    // B is potentially the sink of a dependence.
    auto *Sink = B->first;
    auto SinkDes = B->second;

    // Code motion for interleaved accesses can't violate WAR dependences.
    // Thus, reordering is legal if the source isn't a write.
    if (!Src->mayWriteToMemory())
      return true;

    // At least one of the accesses must be strided.
    if (!isStrided(SrcDes.Stride) && !isStrided(SinkDes.Stride))
      return true;

    // If dependence information is not available from LoopAccessInfo,
    // conservatively assume the instructions can't be reordered.
    if (!areDependencesValid())
      return false;

    // If we know there is a dependence from source to sink, assume the
    // instructions can't be reordered. Otherwise, reordering is legal.
    return !Dependences.count(Src) || !Dependences.lookup(Src).count(Sink);
  }

  /// \brief Collect the dependences from LoopAccessInfo.
  ///
  /// We process the dependences once during the interleaved access analysis to
  /// enable constant-time dependence queries.
  void collectDependences() {
    if (!areDependencesValid())
      return;
    auto *Deps = LAI->getDepChecker().getDependences();
    for (auto Dep : *Deps)
      Dependences[Dep.getSource(*LAI)].insert(Dep.getDestination(*LAI));
  }
};

/// Utility class for getting and setting loop vectorizer hints in the form
/// of loop metadata.
/// This class keeps a number of loop annotations locally (as member variables)
/// and can, upon request, write them back as metadata on the loop. It will
/// initially scan the loop for existing metadata, and will update the local
/// values based on information in the loop.
/// We cannot write all values to metadata, as the mere presence of some info,
/// for example 'force', means a decision has been made. So, we need to be
/// careful NOT to add them if the user hasn't specifically asked so.
class LoopVectorizeHints {
  enum HintKind { HK_WIDTH, HK_UNROLL, HK_FORCE };

  /// Hint - associates name and validation with the hint value.
  struct Hint {
    const char *Name;
    unsigned Value; // This may have to change for non-numeric values.
    HintKind Kind;

    Hint(const char *Name, unsigned Value, HintKind Kind)
        : Name(Name), Value(Value), Kind(Kind) {}

    bool validate(unsigned Val) {
      switch (Kind) {
      case HK_WIDTH:
        return isPowerOf2_32(Val) && Val <= VectorizerParams::MaxVectorWidth;
      case HK_UNROLL:
        return isPowerOf2_32(Val) && Val <= MELVMaxInterleaveFactor;
      case HK_FORCE:
        return (Val <= 1);
      }
      return false;
    }
  };

  /// Vectorization width.
  Hint Width;
  /// Vectorization interleave factor.
  Hint Interleave;
  /// Vectorization forced
  Hint Force;

  /// Return the loop metadata prefix.
  static StringRef Prefix() { return "llvm.loop."; }

  /// True if there is any unsafe math in the loop.
  bool PotentiallyUnsafe;

public:
  enum ForceKind {
    FK_Undefined = -1, ///< Not selected.
    FK_Disabled = 0,   ///< Forcing disabled.
    FK_Enabled = 1,    ///< Forcing enabled.
  };

  LoopVectorizeHints(const Loop *L, bool DisableInterleaving,
                     OptimizationRemarkEmitter &ORE)
      : Width("vectorize.width", VectorizerParams::VectorizationFactor,
              HK_WIDTH),
        Interleave("interleave.count", DisableInterleaving, HK_UNROLL),
        Force("vectorize.enable", FK_Undefined, HK_FORCE),
        PotentiallyUnsafe(false), TheLoop(L), ORE(ORE) {
    // Populate values with existing loop metadata.
    getHintsFromMetadata();

    // force-vector-interleave overrides DisableInterleaving.
    if (VectorizerParams::isInterleaveForced())
      Interleave.Value = VectorizerParams::VectorizationInterleave;

    LLVM_DEBUG(if (DisableInterleaving && Interleave.Value == 1) dbgs()
          << "LV: Interleaving disabled by the pass manager\n");
  }

  /// Mark the loop L as already vectorized by setting the width to 1.
  void setAlreadyVectorized() {
    Width.Value = Interleave.Value = 1;
    Hint Hints[] = {Width, Interleave};
    writeHintsToMetadata(Hints);
  }

  bool allowVectorization(Function *F, Loop *L, bool VectorizeOnlyWhenForced) const {
    if (getForce() == LoopVectorizeHints::FK_Disabled) {
      LLVM_DEBUG(dbgs() << "LV: Not vectorizing: #pragma vectorize disable.\n");
      emitRemarkWithHints();
      return false;
    }

    if (VectorizeOnlyWhenForced && getForce() != LoopVectorizeHints::FK_Enabled) {
      LLVM_DEBUG(dbgs() << "LV: Not vectorizing: No #pragma vectorize enable.\n");
      emitRemarkWithHints();
      return false;
    }

    if (getWidth() == 1 && getInterleave() == 1) {
      // FIXME: Add a separate metadata to indicate when the loop has already
      // been vectorized instead of setting width and count to 1.
      LLVM_DEBUG(dbgs() << "LV: Not vectorizing: Disabled/already vectorized.\n");
      // FIXME: Add interleave.disable metadata. This will allow
      // vectorize.disable to be used without disabling the pass and errors
      // to differentiate between disabled vectorization and a width of 1.
      ORE.emit(OptimizationRemarkAnalysis(vectorizeAnalysisPassName(),
                                          "AllDisabled", L->getStartLoc(),
                                          L->getHeader())
               << "loop not vectorized: vectorization and interleaving are "
                  "explicitly disabled, or vectorize width and interleave "
                  "count are both set to 1");
      return false;
    }

    return true;
  }

  /// Dumps all the hint information.
  void emitRemarkWithHints() const {
    //using namespace ore;
    if (Force.Value == LoopVectorizeHints::FK_Disabled)
      ORE.emit(OptimizationRemarkMissed(LV_NAME, "MissedExplicitlyDisabled",
                                        TheLoop->getStartLoc(),
                                        TheLoop->getHeader())
               << "loop not vectorized: vectorization is explicitly disabled");
    else {
      OptimizationRemarkMissed R(LV_NAME, "MissedDetails",
                                 TheLoop->getStartLoc(), TheLoop->getHeader());
      R << "loop not vectorized";
      if (Force.Value == LoopVectorizeHints::FK_Enabled) {
        R << " (Force=" << ore::NV("Force", true);
        if (Width.Value != 0)
          R << ", Vector Width=" << ore::NV("VectorWidth", Width.Value);
        if (Interleave.Value != 0)
          R << ", Interleave Count=" << ore::NV("InterleaveCount", Interleave.Value);
        R << ")";
      }
      ORE.emit(R);
    }
  }

  unsigned getWidth() const { return Width.Value; }
  unsigned getInterleave() const { return Interleave.Value; }
  enum ForceKind getForce() const { return (ForceKind)Force.Value; }

  /// \brief If hints are provided that force vectorization, use the AlwaysPrint
  /// pass name to force the frontend to print the diagnostic.
  const char *vectorizeAnalysisPassName() const {
    if (getWidth() == 1)
      return LV_NAME;
    if (getForce() == LoopVectorizeHints::FK_Disabled)
      return LV_NAME;
    if (getForce() == LoopVectorizeHints::FK_Undefined && getWidth() == 0)
      return LV_NAME;
    return OptimizationRemarkAnalysis::AlwaysPrint;
  }

  bool allowReordering() const {
    // When enabling loop hints are provided we allow the vectorizer to change
    // the order of operations that is given by the scalar loop. This is not
    // enabled by default because can be unsafe or inefficient. For example,
    // reordering floating-point operations will change the way round-off
    // error accumulates in the loop.
    return getForce() == LoopVectorizeHints::FK_Enabled || getWidth() > 1;
  }

  bool isPotentiallyUnsafe() const {
    // Avoid FP vectorization if the target is unsure about proper support.
    // This may be related to the SIMD unit in the target not handling
    // IEEE 754 FP ops properly, or bad single-to-double promotions.
    // Otherwise, a sequence of vectorized loops, even without reduction,
    // could lead to different end results on the destination vectors.
    return getForce() != LoopVectorizeHints::FK_Enabled && PotentiallyUnsafe;
  }

  void setPotentiallyUnsafe() { PotentiallyUnsafe = true; }

private:
  /// Find hints specified in the loop metadata and update local values.
  void getHintsFromMetadata() {
    MDNode *LoopID = TheLoop->getLoopID();
    if (!LoopID)
      return;

    // First operand should refer to the loop id itself.
    assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
    assert(LoopID->getOperand(0) == LoopID && "invalid loop id");

    for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
      const MDString *S = nullptr;
      SmallVector<Metadata *, 4> Args;

      // The expected hint is either a MDString or a MDNode with the first
      // operand a MDString.
      if (const MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i))) {
        if (!MD || MD->getNumOperands() == 0)
          continue;
        S = dyn_cast<MDString>(MD->getOperand(0));
        for (unsigned i = 1, ie = MD->getNumOperands(); i < ie; ++i)
          Args.push_back(MD->getOperand(i));
      } else {
        S = dyn_cast<MDString>(LoopID->getOperand(i));
        assert(Args.size() == 0 && "too many arguments for MDString");
      }

      if (!S)
        continue;

      // Check if the hint starts with the loop metadata prefix.
      StringRef Name = S->getString();
      if (Args.size() == 1)
        setHint(Name, Args[0]);
    }
  }

  /// Checks string hint with one operand and set value if valid.
  void setHint(StringRef Name, Metadata *Arg) {
    if (!Name.startswith(Prefix()))
      return;
    Name = Name.substr(Prefix().size(), StringRef::npos);

    const ConstantInt *C = mdconst::dyn_extract<ConstantInt>(Arg);
    if (!C)
      return;
    unsigned Val = C->getZExtValue();

    Hint *Hints[] = {&Width, &Interleave, &Force};
    for (auto H : Hints) {
      if (Name == H->Name) {
        if (H->validate(Val))
          H->Value = Val;
        else
          LLVM_DEBUG(dbgs() << "LV: ignoring invalid hint '" << Name << "'\n");
        break;
      }
    }
  }

  /// Create a new hint from name / value pair.
  MDNode *createHintMetadata(StringRef Name, unsigned V) const {
    LLVMContext &Context = TheLoop->getHeader()->getContext();
    Metadata *MDs[] = {MDString::get(Context, Name),
                       ConstantAsMetadata::get(
                           ConstantInt::get(Type::getInt32Ty(Context), V))};
    return MDNode::get(Context, MDs);
  }

  /// Matches metadata with hint name.
  bool matchesHintMetadataName(MDNode *Node, ArrayRef<Hint> HintTypes) {
    MDString *Name = dyn_cast<MDString>(Node->getOperand(0));
    if (!Name)
      return false;

    for (auto H : HintTypes)
      if (Name->getString().endswith(H.Name))
        return true;
    return false;
  }

  /// Sets current hints into loop metadata, keeping other values intact.
  void writeHintsToMetadata(ArrayRef<Hint> HintTypes) {
    if (HintTypes.size() == 0)
      return;

    // Reserve the first element to LoopID (see below).
    SmallVector<Metadata *, 4> MDs(1);
    // If the loop already has metadata, then ignore the existing operands.
    MDNode *LoopID = TheLoop->getLoopID();
    if (LoopID) {
      for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
        MDNode *Node = cast<MDNode>(LoopID->getOperand(i));
        // If node in update list, ignore old value.
        if (!matchesHintMetadataName(Node, HintTypes))
          MDs.push_back(Node);
      }
    }

    // Now, add the missing hints.
    for (auto H : HintTypes)
      MDs.push_back(createHintMetadata(Twine(Prefix(), H.Name).str(), H.Value));

    // Replace current metadata node with new one.
    LLVMContext &Context = TheLoop->getHeader()->getContext();
    MDNode *NewLoopID = MDNode::get(Context, MDs);
    // Set operand 0 to refer to the loop id itself.
    NewLoopID->replaceOperandWith(0, NewLoopID);

    TheLoop->setLoopID(NewLoopID);
  }

  /// The loop these hints belong to.
  const Loop *TheLoop;

  /// Interface to emit optimization remarks.
  OptimizationRemarkEmitter &ORE;
};

/// LoopVectorizationLegality checks if it is legal to vectorize a loop, and
/// to what vectorization factor.
/// This class does not look at the profitability of vectorization, only the
/// legality. This class has two main kinds of checks:
/// * Memory checks - The code in canVectorizeMemory checks if vectorization
///   will change the order of memory accesses in a way that will change the
///   correctness of the program.
/// * Scalars checks - The code in canVectorizeInstrs and canVectorizeMemory
/// checks for a number of different conditions, such as the availability of a
/// 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,
      const TargetTransformInfo *TTI,
      const TargetLibraryInfo *TLI, AliasAnalysis *AA, Function *F, // AOCC line
      LoopAccessInfoManager &LAIs, LoopInfo *LI,
      OptimizationRemarkEmitter *ORE, LoopVectorizationRequirements *R,
      LoopVectorizeHints *H)
      : NumPredStores(0), TheLoop(L), PSE(PSE), TTI(TTI), TLI(TLI), DT(DT),
        LAIs(LAIs), LAI(nullptr), ORE(ORE), InterleaveInfo(PSE, L, DT, LI),
        PrimaryInduction(nullptr), WidestIndTy(nullptr), HasFunNoNaNAttr(false),
        Requirements(R), Hints(H), LInfo(LI) {}

  /// ReductionList contains the reduction descriptors for all
  /// of the reductions that were found in the loop.
  typedef DenseMap<PHINode *, RecurrenceDescriptor> ReductionList;

  /// InductionList saves induction variables and maps them to the
  /// induction descriptor.
  typedef MapVector<PHINode *, InductionDescriptor> InductionList;

  /// RecurrenceSet contains the phi nodes that are recurrences other than
  /// inductions and reductions.
  typedef SmallPtrSet<const PHINode *, 8> RecurrenceSet;

  /// Returns true if it is legal to vectorize this loop.
  /// This does not mean that it is profitable to vectorize this
  /// loop, only that it is legal to do so.
  bool canVectorize();

  /// Returns the primary induction variable.
  PHINode *getPrimaryInduction() { return PrimaryInduction; }

  /// Returns the reduction variables found in the loop.
  ReductionList *getReductionVars() { return &Reductions; }

  /// Returns the induction variables found in the loop.
  InductionList *getInductionVars() { return &Inductions; }

  /// Return the first-order recurrences found in the loop.
  RecurrenceSet *getFirstOrderRecurrences() { return &FirstOrderRecurrences; }

  /// Sets Inductions for given Phi and Induction Descriptor ID
  void setInductionVar(PHINode *Phi, InductionDescriptor &ID) {
    Inductions[Phi] = ID;
  }

  /// Return the set of instructions to sink to handle first-order recurrences.
  DenseMap<Instruction *, Instruction *> &getSinkAfter() { return SinkAfter; }

  /// Returns the widest induction type.
  Type *getWidestInductionType() { return WidestIndTy; }

  /// Returns True if V is an induction variable in this loop.
  bool isInductionVariable(const Value *V);

  /// Returns True if PN is a reduction variable in this loop.
  bool isReductionVariable(PHINode *PN) { return Reductions.count(PN); }

  /// Returns True if Phi is a first-order recurrence in this loop.
  bool isFirstOrderRecurrence(const PHINode *Phi);

  /// Return true if the block BB needs to be predicated in order for the loop
  /// to be vectorized.
  bool blockNeedsPredication(BasicBlock *BB);

  /// Check if this pointer is consecutive when vectorizing. This happens
  /// when the last index of the GEP is the induction variable, or that the
  /// pointer itself is an induction variable.
  /// This check allows us to vectorize A[idx] into a wide load/store.
  /// Returns:
  /// 0 - Stride is unknown or non-consecutive.
  /// 1 - Address is consecutive.
  /// -1 - Address is consecutive, and decreasing.
  int isConsecutivePtr(Type *AccessTy, Value *Ptr);

  /// Returns true if the value V is uniform within the loop.
  bool isUniform(Value *V);

  /// Returns the information that we collected about runtime memory check.
  const RuntimePointerChecking *getRuntimePointerChecking() const {
    return LAI->getRuntimePointerChecking();
  }

  const LoopAccessInfo *getLAI() const { return LAI; }

  /// \brief Check if \p Instr belongs to any interleaved access group.
  bool isAccessInterleaved(Instruction *Instr) {
    return InterleaveInfo.isInterleaved(Instr);
  }

  /// \brief Return the maximum interleave factor of all interleaved groups.
  unsigned getMaxInterleaveFactor() const {
    return InterleaveInfo.getMaxInterleaveFactor();
  }

  /// \brief Get the interleaved access group that \p Instr belongs to.
  const InterleaveGroup *getInterleavedAccessGroup(Instruction *Instr) {
    return InterleaveInfo.getInterleaveGroup(Instr);
  }

  /// \brief Returns true if an interleaved group requires a scalar iteration
  /// to handle accesses with gaps.
  bool requiresScalarEpilogue() const {
    return InterleaveInfo.requiresScalarEpilogue();
  }

  /// Returns true if the target machine supports masked store operation
  /// for the given \p DataType and kind of access to \p Ptr.
  bool isLegalMaskedStore(Type *DataType, Value *Ptr, unsigned Alignment) {
    return isConsecutivePtr(DataType, Ptr) &&
           TTI->isLegalMaskedStore(DataType, Align(Alignment));
  }
  /// Returns true if the target machine supports masked load operation
  /// for the given \p DataType and kind of access to \p Ptr.
  bool isLegalMaskedLoad(Type *DataType, Value *Ptr, unsigned Alignment) {
    return isConsecutivePtr(DataType, Ptr) &&
           TTI->isLegalMaskedLoad(DataType, Align(Alignment));
  }
  /// Returns true if the target machine supports masked scatter operation
  /// for the given \p DataType.
  bool isLegalMaskedScatter(Type *DataType, Align Alignment) {
    return TTI->isLegalMaskedScatter(DataType, Alignment);
  }
  /// Returns true if the target machine supports masked gather operation
  /// for the given \p DataType.
  bool isLegalMaskedGather(Type *DataType, Align Alignment) {
    return TTI->isLegalMaskedGather(DataType, Alignment);
  }
  /// Returns true if the target machine can represent \p V as a masked gather
  /// or scatter operation.
   bool isLegalGatherOrScatter(Value *V) {
   bool LI = isa<LoadInst>(V);
   bool SI = isa<StoreInst>(V);
   if (!LI && !SI)
     return false;
   auto *Ty = getMemInstValueType(V);
   return ((LI && isLegalMaskedGather(Ty, Align((dyn_cast<LoadInst>(V))->getAlignment()))) 
           || (SI && isLegalMaskedScatter(Ty, Align((dyn_cast<StoreInst>(V))->getAlignment()))));
  }

  /// Returns true if vector representation of the instruction \p I
  /// requires mask.
  bool isMaskRequired(const Instruction *I) { return (MaskedOp.count(I) != 0); }
  unsigned getNumStores() const { return LAI->getNumStores(); }
  unsigned getNumLoads() const { return LAI->getNumLoads(); }
  unsigned getNumPredStores() const { return NumPredStores; }

  /// \brief Get the interleaved access group that \p Instr belongs to.
  MapVector<Instruction *, const MEStrideAccessInfo> &getStrideAccessGroup() {
    return InterleaveInfo.StrideInfo;
  }

  /// For a strided memory access, it returns true if hold valid stride
  /// operation, else it returns false.
  bool isValidStrideOperationMelv(Instruction *I) {
    return InterleaveInfo.isValidStrideOperationMelv(I);
  }

  /// Returns true if \p I is an instruction that will be scalarized with
  /// predication. Such instructions include conditional stores and
  /// instructions that may divide by zero.
  bool isScalarWithPredication(Instruction *I);

  /// Returns true if \p I is a memory instruction with consecutive memory
  /// access that can be widened.
  bool memoryInstructionCanBeWidened(Instruction *I, unsigned VF = 1);

  // Returns true if the NoNaN attribute is set on the function.
  bool hasFunNoNaNAttr() const { return HasFunNoNaNAttr; }

private:
  /// Check if a single basic block loop is vectorizable.
  /// At this point we know that this is a loop with a constant trip count
  /// and we only need to check individual instructions.
  bool canVectorizeInstrs();

  /// When we vectorize loops we may change the order in which
  /// we read and write from memory. This method checks if it is
  /// legal to vectorize the code, considering only memory constrains.
  /// Returns true if the loop is vectorizable
  bool canVectorizeMemory();

  /// Return true if we can vectorize this loop using the IF-conversion
  /// transformation.
  bool canVectorizeWithIfConvert();

  /// Return true if all of the instructions in the block can be speculatively
  /// executed. \p SafePtrs is a list of addresses that are known to be legal
  /// and we know that we can read from them without segfault.
  bool blockCanBePredicated(BasicBlock *BB, SmallPtrSetImpl<Value *> &SafePtrs);

  /// Updates the vectorization state by adding \p Phi to the inductions list.
  /// This can set \p Phi as the main induction of the loop if \p Phi is a
  /// better choice for the main induction than the existing one.
  void addInductionPhi(PHINode *Phi, const InductionDescriptor &ID,
                       SmallPtrSetImpl<Value *> &AllowedExit);

  /// \brief If an access has a symbolic strides, this maps the pointer value to
  /// the stride symbol.
  const DenseMap<Value *, const SCEV *> *getSymbolicStrides() {
    // FIXME: Currently, the set of symbolic strides is sometimes queried before
    // it's collected.  This happens from canVectorizeWithIfConvert, when the
    // pointer is checked to reference consecutive elements suitable for a
    // masked access.
    return LAI ? &LAI->getSymbolicStrides() : nullptr;
  }

  unsigned NumPredStores;

  /// The loop that we evaluate.
  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 Transform Info
  const TargetTransformInfo *TTI;
  /// Target Library Info.
  const TargetLibraryInfo *TLI;
  /// Dominator Tree.
  DominatorTree *DT;
  // LoopAccess analysis.
  LoopAccessInfoManager &LAIs;
  // And the loop-accesses info corresponding to this loop.  This pointer is
  // null until canVectorizeMemory sets it up.
  const LoopAccessInfo *LAI;
  /// Interface to emit optimization remarks.
  OptimizationRemarkEmitter *ORE;

  /// The interleave access information contains groups of interleaved accesses
  /// with the same stride and close to each other.
  MEInterleavedAccessInfo InterleaveInfo;

  //  ---  vectorization state --- //

  /// Holds the primary induction variable. This is the counter of the
  /// loop.
  PHINode *PrimaryInduction;
  /// Holds the reduction variables.
  ReductionList Reductions;
  /// Holds all of the induction variables that we found in the loop.
  /// Notice that inductions don't need to start at zero and that induction
  /// variables can be pointers.
  InductionList Inductions;
  /// Holds the phi nodes that are first-order recurrences.
  RecurrenceSet FirstOrderRecurrences;
  /// Holds instructions that need to sink past other instructions to handle
  /// first-order recurrences.
  DenseMap<Instruction *, Instruction *> SinkAfter;
  /// Holds the widest induction type encountered.
  Type *WidestIndTy;

  /// Allowed outside users. This holds the induction and reduction
  /// vars which can be accessed from outside the loop.
  SmallPtrSet<Value *, 4> AllowedExit;

  /// Can we assume the absence of NaNs.
  bool HasFunNoNaNAttr;

  /// Vectorization requirements that will go through late-evaluation.
  LoopVectorizationRequirements *Requirements;

  /// Used to emit an analysis of any legality issues.
  LoopVectorizeHints *Hints;

  /// While vectorizing these instructions we have to generate a
  /// call to the appropriate masked intrinsic
  SmallPtrSet<const Instruction *, 8> MaskedOp;
  LoopInfo *LInfo;
};

/// \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
/// has been provided.
/// Late evaluation of these requirements allows helpful diagnostics to be
/// composed that tells the user what need to be done to vectorize the loop. For
/// example, by specifying #pragma clang loop vectorize or -ffast-math. Late
/// evaluation should be used only when diagnostics can generated that can be
/// followed by a non-expert user.
class LoopVectorizationRequirements {
public:
  LoopVectorizationRequirements(OptimizationRemarkEmitter &ORE)
      : NumRuntimePointerChecks(0), UnsafeAlgebraInst(nullptr), ORE(ORE) {}

  void addUnsafeAlgebraInst(Instruction *I) {
    // First unsafe algebra instruction.
    if (!UnsafeAlgebraInst)
      UnsafeAlgebraInst = I;
  }

  void addRuntimePointerChecks(unsigned Num) { NumRuntimePointerChecks = Num; }

  bool doesNotMeet(Function *F, Loop *L, const LoopVectorizeHints &Hints);

private:
  unsigned NumRuntimePointerChecks;
  Instruction *UnsafeAlgebraInst;

  /// Interface to emit optimization remarks.
  OptimizationRemarkEmitter &ORE;
};

///// \brief Look for a meaningful debug location on the instruction or it's
///// operands.
//static Instruction *getDebugLocFromInstOrOperands(Instruction *I) {
//  if (!I)
//    return I;
//
//  DebugLoc Empty;
//  if (I->getDebugLoc() != Empty)
//    return I;
//
//  for (User::op_iterator OI = I->op_begin(), OE = I->op_end(); OI != OE; ++OI) {
//    if (Instruction *OpInst = dyn_cast<Instruction>(*OI))
//      if (OpInst->getDebugLoc() != Empty)
//        return OpInst;
//  }
//
//  return I;
//}

struct CSEDenseMapInfo {
  static bool canHandle(const Instruction *I) {
    return isa<InsertElementInst>(I) || isa<ExtractElementInst>(I) ||
           isa<ShuffleVectorInst>(I) || isa<GetElementPtrInst>(I);
  }
  static inline Instruction *getEmptyKey() {
    return DenseMapInfo<Instruction *>::getEmptyKey();
  }
  static inline Instruction *getTombstoneKey() {
    return DenseMapInfo<Instruction *>::getTombstoneKey();
  }
  static unsigned getHashValue(const Instruction *I) {
    assert(canHandle(I) && "Unknown instruction!");
    return hash_combine(I->getOpcode(), hash_combine_range(I->value_op_begin(),
                                                           I->value_op_end()));
  }
  static bool isEqual(const Instruction *LHS, const Instruction *RHS) {
    if (LHS == getEmptyKey() || RHS == getEmptyKey() ||
        LHS == getTombstoneKey() || RHS == getTombstoneKey())
      return LHS == RHS;
    return LHS->isIdenticalTo(RHS);
  }
};

class MultiExitLoopVectorizer {
public:
  MultiExitLoopVectorizer(Loop *OrigLoop, PredicatedScalarEvolution &PSE,
                          LoopInfo *LI, DominatorTree *DT,
                          const TargetLibraryInfo *TLI,
                          const TargetTransformInfo *TTI, unsigned VecWidth,
                          unsigned UnrollFactor, LoopVectorizationLegality *LVL,
                          llvm::OptimizationRemarkEmitter *ORE,
                          bool LTOVectorization = false,
                          bool MallocPadding = true)
      : OrigLoop(OrigLoop), PSE(PSE), LI(LI), DT(DT), TLI(TLI), TTI(TTI),
        ORE(ORE), VF(VecWidth), UF(UnrollFactor),
        Builder(PSE.getSE()->getContext()), Induction(nullptr),
        OldInduction(nullptr), TripCount(nullptr), VectorTripCount(nullptr),
        AddedSafetyChecks(false), SE(PSE.getSE()), WidenMap(UnrollFactor),
        LTOVectorization(LTOVectorization), MallocPadding(MallocPadding) {
    Legal = LVL;
    buildSafeLibFuncs();
    PtrInduction = nullptr;
    OneIterationPeel = false;
    PeelForAlignment = false;
  }

  //Virtual destructor
  virtual ~MultiExitLoopVectorizer() {};

  // Perform the actual loop widening (vectorization).
  void vectorize() {
    // Update Loop Exit Blocks
    getLoopExitBlocks();
    // Create a new empty loop. Unlink the old loop and connect the new one.
    createEmptyLoop();
    // Widen each instruction in the old loop to a new one in the new loop.
    // Use the Legality module to find the induction and reduction variables.
    vectorizeLoop();

    //Add metadata to loop. This is usefult to check if vect compare is energised or not
    //
    // Do not set this meta data, when we want to avoid padding. Malloc Padding
    // pass will not do anything if this meta data is not set.
    if (isMallocPadding()) {
      LLVM_DEBUG (errs() << "MELV : Setting loop meta data\n");
      addStringMetadataToLoop(OrigLoop, "llvm.loop.vect.melv");
    } else
      LLVM_DEBUG (errs() << "MELV : Not setting loop meta data to "
                         << "avoid malloc padding" << "\n");
  }

  // Check if the original induction varaible has decreasing trip count.
  bool isDecreasingTripCount();

  // Set the loop exiting blocks.
  // This function sets the peeled loop exiting blocks. PeelLoopExitingBlock
  // will be the one where the induciton variable is incremented and
  // PeelLoopBreakExitingBlock will be set to the one where early exit happens.
  // Their rolls are swapped in case of while and non-while loops.
  void setLoopExitingBlocks(bool isPeeled);
  // Get the vector loop induction variable.
  PHINode *getVectLoopInductionVar() { return VectLoopIndVar; }
  // Peeled loop normal exiting block with update to induction variable
  BasicBlock *getPeelLoopExitingBlock() { return PeelLoopExitingBlock; }
  // Peeled loop exiting block with early exit
  BasicBlock *getPeelLoopBreakExitingBlock() {
    return PeelLoopBreakExitingBlock;
  }
  // Original loop normal exiting block with update to induction variable
  BasicBlock *getOrigLoopExitingBlock() { return OrigLoopExitingBlock; }
  // Peeled loop exiting block with early exit
  BasicBlock *getOrigLoopBreakExitingBlock() {
    return OrigLoopBreakExitingBlock;
  }

  /// Checks whether the Loop L is vectorizable.
  bool SearchPattern(Loop *L);

  // This function returns false if any function other than main has linkage
  // type external
  bool checkLinkage(Module *M);

  // Functions helping to peel the loop
  //
  // Set malloc padding to true or false.
  void setMallocPadding(bool val) { MallocPadding = val; }
  // Check if malloc padding is on or off.
  bool isMallocPadding() { return MallocPadding; }
  // Check if the loop can be peeled.
  bool canPeel();
  // Functions for check if one iteration peeling or peeling for alignment
  void setOneIterationPeel(bool val) { OneIterationPeel = val; }
  void setPeelForAlignment(bool val) { PeelForAlignment = val; }
  bool isOneIterPeeling() { return OneIterationPeel; }
  bool isPeelForAlignment() { return PeelForAlignment; }
  // Create the peeled loop.
  void createPeeledLoop(bool DecreasingTripCount);
  // Peel the MELV vectorized loop either
  // 1. for just one iteration if the predicate of early exit is 'ne' or
  // 2. till the base address is aligned to the vector factor boundary to avoid
  // malloc padding.
  void peelMELVLoop(bool DecreasingTripCount);
  // Update the phi nodes in the exit blocks of peeled loop blocks.
  void updateLCSSAPhisFromPeeledLoop(BasicBlock *ExitBlock);
  // Set the vector width according to the type of the loaded value
  void setMELVVectorWidth(LoadInst *L);
  // Get the vector width.
  int getMELVVectorWidth() { return MELVVectorWidth; }
  // Get the vector lane size in bytes.
  int getMELVVectorLaneSize() { return MELVVectorLaneSize; }
  // Get the start value of induction variable to be resumed in the reminder
  // or the peeled loop.
  PHINode* getResumeInductionVal() { return ResumeInductionVal; }
  // Get the start index of original loop
  Value* getOrigLoopStartIdx() { return OrigLoopStartIdx; }
  // Get the Strarting value of pointer induction in the reminder loop
  PHINode *getPtrIndStartValInScalarLoop() {
    return PtrIndStartValInScalarLoop;
  }
  // Get the GEP for the pointer induction in the vector loop
  GetElementPtrInst *getGEPForPtrIndInVecLoop() {
    return GEPForPtrIndInVecLoop;
  }
protected:
  /// The original loop.
  Loop *OrigLoop;
  /// 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;
  /// Interface to emit optimization remarks.
  OptimizationRemarkEmitter *ORE;

  /// \brief LoopVersioning.  It's only set up (non-null) if memchecks were
  /// used.
  ///
  /// This is currently only used to add no-alias metadata based on the
  /// memchecks.  The actually versioning is performed manually.
  std::unique_ptr<LoopVersioning> LVer;

  /// The vectorization SIMD factor to use. Each vector will have this many
  /// vector elements.
  unsigned VF;

  /// The vectorization unroll factor to use. Each scalar is vectorized to this
  /// many different vector instructions.
  unsigned UF;

  /// The builder that we use
  IRBuilder<> Builder;

  /// A small list of PHINodes.
  typedef SmallVector<PHINode *, 4> PhiVector;

  /// A type for vectorized values in the new loop. Each value from the
  /// original loop, when vectorized, is represented by UF vector values in the
  /// new unrolled loop, where UF is the unroll factor.
  typedef SmallVector<Value *, 2> VectorParts;

  // 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;

  /// This is a helper class that holds the vectorizer state. It maps scalar
  /// instructions to vector instructions. When the code is 'unrolled' then
  /// then a single scalar value is mapped to multiple vector parts. The parts
  /// are stored in the VectorPart type.
  struct ValueMap {
    /// C'tor.  UnrollFactor controls the number of vectors ('parts') that
    /// are mapped.
    ValueMap(unsigned UnrollFactor) : UF(UnrollFactor) {}

    /// \return True if 'Key' is saved in the Value Map.
    bool has(Value *Key) const { return MapStorage.count(Key); }

    /// Initializes a new entry in the map. Sets all of the vector parts to the
    /// save value in 'Val'.
    /// \return A reference to a vector with splat values.
    VectorParts &splat(Value *Key, Value *Val) {
      VectorParts &Entry = MapStorage[Key];
      Entry.assign(UF, Val);
      return Entry;
    }

    ///\return A reference to the value that is stored at 'Key'.
    VectorParts &get(Value *Key) {
      VectorParts &Entry = MapStorage[Key];
      if (Entry.empty())
        Entry.resize(UF);
      assert(Entry.size() == UF);
      return Entry;
    }

  private:
    /// The unroll factor. Each entry in the map stores this number of vector
    /// elements.
    unsigned UF;

    /// Map storage. We use std::map and not DenseMap because insertions to a
    /// dense map invalidates its iterators.
    std::map<Value *, VectorParts> MapStorage;
  };

  /// A map of induction variables from the original loop to their
  /// corresponding VF * UF scalarized values in the vectorized loop. The
  /// purpose of ScalarIVMap is similar to that of WidenMap. Whereas WidenMap
  /// maps original loop values to their vector versions in the new loop,
  /// ScalarIVMap maps induction variables from the original loop that are not
  /// vectorized to their scalar equivalents in the vector loop. Maintaining a
  /// separate map for scalarized induction variables allows us to avoid
  /// unnecessary scalar-to-vector-to-scalar conversions.
  DenseMap<Value *, SmallVector<Value *, 8>> ScalarIVMap;

  // --- Vectorization state ---

  /// The vector-loop preheader.
  BasicBlock *LoopVectorPreHeader;
  /// The scalar-loop preheader.
  BasicBlock *LoopScalarPreHeader;
  /// 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;
  /// 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;

  /// Pointer induction variable if it is found.
  PHINode *PtrInduction = nullptr;
  /// Element type of pointer induction
  Type *MELVLoadType = nullptr;

  /// Store instructions that should be predicated, as a pair
  ///   <StoreInst, Predicate>
  SmallVector<std::pair<Instruction *, Value *>, 4> PredicatedInstructions;
  EdgeMaskCache MaskCache;
  /// Trip count of the original loop.
  Value *TripCount;
  /// Trip count of the widened loop (TripCount - TripCount % (VF*UF))
  Value *VectorTripCount;
  /// Trip count of remainder loop;
  Value *RemainderTripCount;
  /// Value of pointer induction when coming from middle block
  Value *ResumeGEPValMiddle;

  /// Map of scalar integer values to the smallest bitwidth they can be legally
  /// represented as. The vector equivalents of these values should be truncated
  /// to this type.
  const MapVector<Instruction *, uint64_t> *MinBWs;

  LoopVectorizationLegality *Legal;

  // Record whether runtime checks are added.
  bool AddedSafetyChecks;

  /// This function adds (StartIdx, StartIdx + Step, StartIdx + 2*Step, ...)
  /// to each vector element of Val. The sequence starts at StartIndex.
  /// \p Opcode is relevant for FP induction variable.
  Value *
  getStepVector(Value *Val, int StartIdx, Value *Step,
                Instruction::BinaryOps Opcode = Instruction::BinaryOpsEnd);

  /// This function adds (StartIdx, StartIdx + Step, StartIdx + 2*Step, ...)
  /// to each vector element of Val. The sequence starts at StartIndex.
  /// Step is a SCEV. In order to get StepValue it takes the existing value
  /// from SCEV or creates a new using SCEVExpander.
  Value *getStepVector(Value *Val, int StartIdx, const SCEV *Step);

  /// Compute a step vector like the above function, but scalarize the
  /// arithmetic instead. The results of the computation are inserted into a
  /// new vector with VF elements. \p Val is the initial value, \p Step is the
  /// size of the step, and \p StartIdx indicates the index of the increment
  /// from which to start computing the steps.
  // Value *getScalarizedStepVector(Value *Val, int StartIdx, Value *Step);
  /// Compute scalar induction steps. \p ScalarIV is the scalar induction
  /// variable on which to base the steps, \p Step is the size of the step, and
  /// \p EntryVal is the value from the original loop that maps to the steps.
  /// Note that \p EntryVal doesn't have to be an induction variable (e.g., it
  /// can be a truncate instruction).
  void buildScalarSteps(Value *ScalarIV, Value *Step, Value *EntryVal);

  /// Returns true if we should generate a scalar version of \p IV.
  bool needsScalarInduction(Instruction *IV) const;

  /// 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);

  /// \brief Similar to the previous function but it adds the metadata to a
  /// vector of instructions.
  void addMetadata(ArrayRef<Value *> To, Instruction *From);

  /// A helper function that computes the predicate of the block BB, assuming
  /// that the header block of the loop is set to True. It returns the *entry*
  /// mask for the block BB.
  VectorParts createBlockInMask(BasicBlock *BB);

  /// A helper function that computes the predicate of the edge between SRC
  /// and DST.
  VectorParts createEdgeMask(BasicBlock *Src, BasicBlock *Dst);

  /// Generate a shuffle sequence that will reverse the vector Vec.
  Value *reverseVector(Value *Vec);

  /// Create a vector induction phi node based on an existing scalar one. This
  /// currently only works for integer induction variables with a constant
  /// step. If \p TruncType is non-null, instead of widening the original IV,
  /// we widen a version of the IV truncated to \p TruncType.
  void createVectorIntOrFpInductionPHI(const InductionDescriptor &II,
                                       VectorParts &Entry,
                                       IntegerType *TruncType);

  /// Widen an integer induction variable \p IV. If \p Trunc is provided, the
  /// induction variable will first be truncated to the corresponding type. The
  /// widened values are placed in \p Entry.
  void widenIntInduction(PHINode *IV, VectorParts &Entry,
                         TruncInst *Trunc = nullptr);

  void vectorizeBlockInLoop(BasicBlock *BB, PhiVector *PV);

  void scalarizeInstruction(Instruction *Instr, bool IfPredicateInstr = false);

  /// When we go over instructions in the basic block we rely on previous
  /// values within the current basic block or on loop invariant values.
  /// When we widen (vectorize) values we place them in the map. If the values
  /// are not within the map, they have to be loop invariant, so we simply
  /// broadcast them into a vector.
  VectorParts &getVectorValue(Value *V);

  /// \brief The Loop exit block may have single value PHI nodes where the
  /// incoming value is 'Undef'. While vectorizing we only handled real values
  /// that were defined inside the loop. Here we fix the 'undef case'.
  /// See PR14725.
  void fixLCSSAPHIs();

  /// Insert the new loop to the loop hierarchy and pass manager
  /// and update the analysis passes.
  void updateAnalysis();

  /// Vectorize Load and Store instructions,
  void vectorizeMemoryInstruction(Instruction *Instr);

  /// Create an empty loop, based on the loop ranges of the old loop.
  void createEmptyLoop();

  // IsSafe function checks whether the loop with multiple exits is suitable for
  // vectorization or not
  // Currently it checks only for the store conditions.
  bool IsSafe(Loop *L);

  // Set vector factor according to the type of the loaded value.
  void setVF(LoadInst *L);

  // Checks whether Loop CmpOperand is loop invariant or load based on the
  // induction variable whose induction constant is 1
  bool SearchRecurr(Loop *L, Value *CmpOperand);

  /// Returns trip count of the scalar loop.
  Value *getTripCount();

  /// Returns (and creates if needed) the trip count of the widened loop.
  Value *getOrCreateVectorTripCount(Loop *L, Value *StartIdx);

  /// Create a new induction variable inside L.
  PHINode *createInductionVariable(Loop *L, BasicBlock *Latch, Value *Start,
                                   Value *End, Value *Step, Instruction *DL);

  // Emits code for testing whether vector trip count is same as start index.
  // If vector trip count is same as staring index then jump to scalar loop
  void emitVectorLoopEnteredCheck(Loop *L, BasicBlock *Bypass, Value *StartIdx);

  // Emits code for testing whether loop generates minimum number of iterations
  // to vectorize or else jump to Scalar Loop.
  void emitItersCheck(Loop *L, BasicBlock *Bypass, Value *StartIdx);

  // Updates LoopBreakExitBlock and LoopExitBlock
  void getLoopExitBlocks();

  /// Copy and widen the instructions from the old loop.
  void vectorizeLoop();

  // Generates instrinsic call for VPTEST instruction
  Value *generatePTESTCInstruction(Module *M, SmallVector<Value *, 4> &args);
  // Generates instrinsic call for TZCNT instruction
  Value *generateTZCNTInstruction(Module *M, SmallVector<Value *, 4> &args);
  // Generates instrinsic call for PMOVMSKB instruction
  Value *generatePMOVMSKBInstruction(Module *M, SmallVector<Value *, 4> &args);

  // Creates Break Condition Exiting Block
  void createBreakCondBlocks(BasicBlock *VectCmpBlock);

  // Populates break condition exiting block
  void createCheckBlock(Value *CmpResVect);

  // Creates extract element instruction for VectInst for Index in BB and
  // returns pointer to the instruction.
  Value *getScalarElement(VectorParts &VectInst, BasicBlock *BB, Value *Index);

  // Checks whether Loop header has only one PHI Node or not
  // FIXME Not Required once MultiExitLoop vectorization is generalised
  bool hasOnlyOnePHINode();

  // We allow maximum of two phi nodes. If we have two phi one of them should
  // be of pointer type.
  // FIXME Not Required once MultiExitLoop vectorization is generalised
  bool hasMaxTwoPHIsOneWithPtrType(bool &hasPtrPhi);

  // Returns pointer to the compare instruction of BB's terminal branching
  // is based on or else returns null
  CmpInst *getTermCmpInst(BasicBlock *BB);

  // Returns the integer iterator of Loop L
  PHINode *getLoopIterator(Loop *L);

  // If Expr is one of the Operands of GEP then returns if the calculated
  // address is accessed consecutively across iterations
  bool isConsecutiveAccess(const SCEV *Expr);

  bool isInvariantOrConsecutveAccess(Loop *L, Value *PrevInst);

  // CanHandleWhileLoop function returns true only when the induction block
  // has no further uses of incremented induction variable apart from comparing
  // the result.
  bool CanHandleWhileLoop();
  Value *getBroadcastInstrs(Value *V);

  // clone of InnerLoopVectorizer::emitTransformedIndex.
  // This is replicated here because this particular pass has poor design
  // choices.
  Value *emitTransformedIndex(IRBuilder<> &B, Value *Index, ScalarEvolution *SE,
                              const DataLayout &DL,
                              const InductionDescriptor &ID) const;

  /// Vectorize a single PHINode in a block. This method handles the induction
  /// variable canonicalization. It supports both VF = 1 for unrolled loops and
  /// arbitrary length vectors.
  virtual void widenPHIInstruction(Instruction *PN, VectorParts &Entry,
                                   unsigned UF, unsigned VF, PhiVector *PV);

  // Returns base pointer of memory being accessed within the loop
  // Return null if loop has more than one memory base ptr
  Value *getMemBasePtr(Loop *L);

  // Check if any of the incoming values of LCSSAPhi can reach the pointer
  // induction phi.
  bool canReachPointerInduction(Value *LCSSAPhi);
protected:
  /// Induction of Original Loop
  PHINode *OrigInduction = nullptr;

  /// True is Orignal Loop is while loop
  bool isWhile = false;
  /// Pointer to Vector Loop
  Loop *VectLoop;
  /// Scev analysis to use.
  ScalarEvolution *SE;
  /// Pointer to adjusted index in LoopBreakHeaderBlock
  Value *FinalIndex = nullptr;
  /// Adjusted Start value of loop induction
  Value *NewStartIdx = nullptr;
  /// Offset from Induction in vector loop
  Value *IndexDiff = nullptr;
  /// The vector loop body.
  SmallVector<BasicBlock *, 4> LoopVectorBody;

  /// Scalar Loop Break Exit Block
  BasicBlock *LoopBreakExitBlock = nullptr;
  /// Vector  Loop Break Header
  BasicBlock *LoopBreakHeaderBlock = nullptr;
  /// Phi incrementing instruction
  Instruction *PhiIncInst = nullptr;
  /// Step Increasing instructions(zexted or truncated) set
  SmallVector<Value *, 4> StepInc;
  /// Maps scalars to widened vectors.
  ValueMap WidenMap;
  /// LTOVectorization is true if in LTOMode
  bool LTOVectorization;
  /// Capture if malloc padding is enabled or not.
  bool MallocPadding;
  // Vector loop induction variable
  PHINode *VectLoopIndVar;
  // Original loop normal exiting block with update to induction variable
  BasicBlock *OrigLoopExitingBlock;
  // Peeled loop exiting block with early exit
  BasicBlock *OrigLoopBreakExitingBlock;
  // Peeled loop normal exiting block with update to induction variable
  BasicBlock *PeelLoopExitingBlock;
  // Peeled loop exiting block with early exit
  BasicBlock *PeelLoopBreakExitingBlock;

  /// The branch instruction used to determine the branches of the vector
  /// compare block.
  BranchInst *OrigLoopBreakBranchInst = nullptr;

  /// Variables saved for Peeling.
  //
  // The peeled loop.
  Loop *PeeledLoop;
  // Variables to check if one iteration peeling or peeling for alignment
  bool OneIterationPeel = false;
  bool PeelForAlignment = false;
  // Compare instruction in the latch block.
  BasicBlock *PeelLoopPHEdgeSrc;
  BasicBlock *PeelLoopPHEdgeDest;
  // Vector lane size in bytes.
  unsigned MELVVectorLaneSize;
  // Vector width to be used for peeling
  unsigned MELVVectorWidth;
  // Store the base pointer accessed in the loop
  Value *BasePtr;
  // Store the start index of original loop
  Value *OrigLoopStartIdx;
  // Store the start value of induction variable to be resumed in the reminder
  // or the peeled loop.
  PHINode *ResumeInductionVal;
  // Value map for the peeled loop.
  ValueToValueMapTy PeeledLoopVMap;
  // Starting Value of pointer induction in the reminder loop
  PHINode *PtrIndStartValInScalarLoop;
  // GEP for the pointer induction in the vector loop
  GetElementPtrInst *GEPForPtrIndInVecLoop;
public:
  // Get the vector factor.
  unsigned getVF() { return VF; }
};

} // namespace melv

#undef DEBUG_TYPE
#undef LV_NAME
#endif
