Ignore Unknown dependencies using vectorize.ivdep metadata

[YashasAndaluri]

Summary

This patch implements the functionality of llvm.loop.vectorize.ivdep.enable metadata. The metadata indicates that dependencies of Unknown type can be assumed to be Safe during the CanVecMem check. This patch depends on D69391

[Meinersbur]

[serious] We did not come to a conclusion during the discussion about the semantics ivdep being implementation-dependent.

Also consider that vectorize_enable(assume_safety) has been designed such that if previous passes move code into the loop that has not been in the source code loop, the safety semantic does not apply to the moved code. This implementation would apply ivdep on the moved code (which might be okay if we shift the responsibility to the code motion pass to remove the metadata).

llvm/docs/LangRef.rst

5492

[serious] Please also describe the relationship to llvm.mem.parallel_loop_access.

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

204

[style] Start variables with a capital letter. Also to not use two different styles on the same line.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

2035–2037

[serious] areDepsSafe is an expensive call which we should not do redundantly when only one of the result is actually used.

[suggestion] Use only CanVecMem and update it according to ivdep.

[YashasAndaluri]

Passed Ivdep hint from LoopVectorizationLegality using GetLAA, to avoid computing areDepsSafe twice.

[YashasAndaluri]

Thank you for checking this diff and for the suggestions! Sorry for the delayed update on this.

In D70634#1758952, @Meinersbur wrote:

[serious] We did not come to a conclusion during the discussion about the semantics ivdep being implementation-dependent.

I was under the impression that Unknown dependencies were ambiguous to the vectorizer and so would be along the lines of the Cray semantics. Please suggest what would be a good approach for this.

Also consider that vectorize_enable(assume_safety) has been designed such that if previous passes move code into the loop that has not been in the source code loop, the safety semantic does not apply to the moved code. This implementation would apply ivdep on the moved code (which might be okay if we shift the responsibility to the code motion pass to remove the metadata).

I believe vectorize_enable(assume_safety) does this by marking the memory access instructions in the original loop (before any code is moved into the loop) with llvm.access.group metadata? Would it be recommended to do something similar for ivdep?

[YashasAndaluri]

llvm/docs/LangRef.rst

5492

llvm.loop.parallel_accesses metadata indicates that no dependencies exist between instructions marked with llvm.access.group metadata and can be executed in parallel, whereas llvm.loop.vectorize.ivdep.enable indicates that Unknown dependencies are safe for vectorization.

[Meinersbur]

In D70634#1781787, @YashasAndaluri wrote:

In D70634#1758952, @Meinersbur wrote:

[serious] We did not come to a conclusion during the discussion about the semantics ivdep being implementation-dependent.

I was under the impression that Unknown dependencies were ambiguous to the vectorizer and so would be along the lines of the Cray semantics. Please suggest what would be a good approach for this.

Cray's semantics are dangerous in that it may unpredictably miscompile depending on which compiler you are using. Just being slower would have been fine. The issue is that there might not be a good approach and I am not convinced that approximated compatibility to Cray is a good-enough reason to introduce unpredictable miscompilation. However, just parsing #pragma ivdep but ignoring it might be fine.

Why may it miscompile unpredictably? Consider:

#pragma ivdep
for (int i = 0; i < n; i+=1)
  sum[i/n] += A[i];

Since 0 <= i < n, i/n will always evaluate to 0. But does the compiler known? If it does, it might recognize the reduction in

double tmp = sum[0];
for (int i = 0; i < n; i+=1)
  tmp += A[i];
sum[0] = tmp;

and vectorize it correctly. However, if it does not, ivdep allows it to ignore the loop-carried dependency and write arbitrary values to sum[0] (for instance just the last value sum[0] = A[n-1]), i.e. miscompile the reduction.

We cannot assume that LLVM's capability to recognize dependencies and reductions are stricly superior over Cray's, hence miscompile programs that Cray's compiler did not. Even worse, the user cannot deduce whether their code will be compiled correctly or not.

[YashasAndaluri]

Added tests

[YashasAndaluri]

Updated tests

[YashasAndaluri]

Add checks for vector instructions

[Meinersbur]

Do you try getting this uptreamed? It won't be accepted before we come to a conclusion for the unpredictable miscompilation.

[YashasAndaluri]

In D70634#1855030, @Meinersbur wrote:

Do you try getting this uptreamed? It won't be accepted before we come to a conclusion for the unpredictable miscompilation.

I understand, I am not trying to upstream it.

llvm/docs/LangRef.rst

 the bit operand value is 1 vectorization is enabled. A value of 0 disables
 vectorization:
 
 .. code-block:: llvm
 
    !0 = !{!"llvm.loop.vectorize.predicate.enable", i1 0}
    !1 = !{!"llvm.loop.vectorize.predicate.enable", i1 1}
 
+'``llvm.loop.vectorize.ivdep.enable``' Metadata
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+This metadata indicates to the vectorizer to ignore dependencies between
+memory accesses which have not been determined to be either safe or unsafe
+for vectorization. This differs from ``llvm.loop.parallel_access``, which
+considers no dependencies to be present between memory accesses belonging
+to the same access group. The first operand is the string
+``llvm.loop.vectorize.ivdep.enable`` and the second operand is a bit. A
+value of 1 implies that the functionality of this metadata is enabled for
+the loop.
+
+.. code-block:: llvm
+
+   !0 = !{!"llvm.loop.vectorize.ivdep.enable", i1 1}
+
 '``llvm.loop.vectorize.width``' Metadata
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 This metadata sets the target width of the vectorizer. The first
 operand is the string ``llvm.loop.vectorize.width`` and the second
 operand is an integer specifying the width. For example:
 
 .. code-block:: llvm

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

void addAccess(LoadInst *LI) {
     InstMap.push_back(LI);
     ++AccessIdx;
   }
 
   /// Check whether the dependencies between the accesses are safe.
   ///
   /// Only checks sets with elements in \p CheckDeps.
   bool areDepsSafe(DepCandidates &AccessSets, MemAccessInfoList &CheckDeps,
-                   const ValueToValueMap &Strides);
+                   const ValueToValueMap &Strides, bool UnknownDepHint);
 
   /// No memory dependence was encountered that would inhibit
   /// vectorization.
   bool isSafeForVectorization() const {
     return Status == VectorizationSafetyStatus::Safe;
   }
 
   /// The maximum number of bytes of a vector register we can vectorize

 /// ScalarEvolution, we will generate run-time checks by emitting a
 /// SCEVUnionPredicate.
 ///
 /// Checks for both memory dependences and the SCEV predicates contained in the
 /// PSE must be emitted in order for the results of this analysis to be valid.
 class LoopAccessInfo {
 public:
   LoopAccessInfo(Loop *L, ScalarEvolution *SE, const TargetLibraryInfo *TLI,
-                 AliasAnalysis *AA, DominatorTree *DT, LoopInfo *LI);
+                 AliasAnalysis *AA, DominatorTree *DT, LoopInfo *LI,
+                 bool UnknownDepHint = false);
 
   /// Return true we can analyze the memory accesses in the loop and there are
   /// no memory dependence cycles.
   bool canVectorizeMemory() const { return CanVecMem; }
 
   /// Return true if there is a convergent operation in the loop. There may
   /// still be reported runtime pointer checks that would be required, but it is
   /// not legal to insert them.
public:
   /// should be re-written (and therefore simplified) according to PSE.
   /// A user of LoopAccessAnalysis will need to emit the runtime checks
   /// associated with this predicate.
   const PredicatedScalarEvolution &getPSE() const { return *PSE; }
 
 private:
   /// Analyze the loop.
   void analyzeLoop(AliasAnalysis *AA, LoopInfo *LI,
-                   const TargetLibraryInfo *TLI, DominatorTree *DT);
+                   const TargetLibraryInfo *TLI, DominatorTree *DT,
+                   bool UnknownDepHint);
 
   /// Check if the structure of the loop allows it to be analyzed by this
   /// pass.
   bool canAnalyzeLoop();
 
   /// Save the analysis remark.
   ///
   /// LAA does not directly emits the remarks.  Instead it stores it which the
public:
 
   bool runOnFunction(Function &F) override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   /// Query the result of the loop access information for the loop \p L.
   ///
   /// If there is no cached result available run the analysis.
-  const LoopAccessInfo &getInfo(Loop *L);
+  const LoopAccessInfo &getInfo(Loop *L, bool UnknownDepHint = false);
 
   void releaseMemory() override {
     // Invalidate the cache when the pass is freed.
     LoopAccessInfoMap.clear();
   }
 
   /// Print the result of the analysis when invoked with -analyze.
   void print(raw_ostream &OS, const Module *M = nullptr) const override;

llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h

 /// 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, HK_ISVECTORIZED,
-                  HK_PREDICATE };
+                  HK_PREDICATE, HK_IVDEP };
 
   /// 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)
class LoopVectorizeHints {
   Hint Force;
 
   /// Already Vectorized
   Hint IsVectorized;
 
   /// Vector Predicate
   Hint Predicate;
 
+  /// Ignore Vector dependencies
+  Hint Ivdep;
+
   /// Return the loop metadata prefix.
   static StringRef Prefix() { return "llvm.loop."; }
 
   /// True if there is any unsafe math in the loop.
   bool PotentiallyUnsafe = false;
 
 public:
   enum ForceKind {
public:
 
   /// Dumps all the hint information.
   void emitRemarkWithHints() const;
 
   unsigned getWidth() const { return Width.Value; }
   unsigned getInterleave() const { return Interleave.Value; }
   unsigned getIsVectorized() const { return IsVectorized.Value; }
   unsigned getPredicate() const { return Predicate.Value; }
+  unsigned getIvdep() const { return Ivdep.Value; }
   enum ForceKind getForce() const {
     if ((ForceKind)Force.Value == FK_Undefined &&
         hasDisableAllTransformsHint(TheLoop))
       return FK_Disabled;
     return (ForceKind)Force.Value;
   }
 
   /// If hints are provided that force vectorization, use the AlwaysPrint

 /// 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,
       TargetTransformInfo *TTI, TargetLibraryInfo *TLI, AliasAnalysis *AA,
-      Function *F, std::function<const LoopAccessInfo &(Loop &)> *GetLAA,
+      Function *F, std::function<const LoopAccessInfo &(Loop &, bool)> *GetLAA,
       LoopInfo *LI, OptimizationRemarkEmitter *ORE,
       LoopVectorizationRequirements *R, LoopVectorizeHints *H, DemandedBits *DB,
       AssumptionCache *AC)
       : TheLoop(L), LI(LI), PSE(PSE), TTI(TTI), TLI(TLI), DT(DT),
         GetLAA(GetLAA), ORE(ORE), Requirements(R), Hints(H), DB(DB), AC(AC) {}
 
   /// ReductionList contains the reduction descriptors for all
   /// of the reductions that were found in the loop.
private:
 
   /// Target Library Info.
   TargetLibraryInfo *TLI;
 
   /// Dominator Tree.
   DominatorTree *DT;
 
   // LoopAccess analysis.
-  std::function<const LoopAccessInfo &(Loop &)> *GetLAA;
+  std::function<const LoopAccessInfo &(Loop &, bool)> *GetLAA;
 
   // And the loop-accesses info corresponding to this loop.  This pointer is
   // null until canVectorizeMemory sets it up.
   const LoopAccessInfo *LAI = nullptr;
 
   /// Interface to emit optimization remarks.
   OptimizationRemarkEmitter *ORE;
 

llvm/include/llvm/Transforms/Vectorize/LoopVectorize.h

struct LoopVectorizePass : public PassInfoMixin<LoopVectorizePass> {
   LoopInfo *LI;
   TargetTransformInfo *TTI;
   DominatorTree *DT;
   BlockFrequencyInfo *BFI;
   TargetLibraryInfo *TLI;
   DemandedBits *DB;
   AliasAnalysis *AA;
   AssumptionCache *AC;
-  std::function<const LoopAccessInfo &(Loop &)> *GetLAA;
+  std::function<const LoopAccessInfo &(Loop &, bool)> *GetLAA;
   OptimizationRemarkEmitter *ORE;
   ProfileSummaryInfo *PSI;
 
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   // Shim for old PM.
   bool runImpl(Function &F, ScalarEvolution &SE_, LoopInfo &LI_,
                TargetTransformInfo &TTI_, DominatorTree &DT_,
                BlockFrequencyInfo &BFI_, TargetLibraryInfo *TLI_,
                DemandedBits &DB_, AliasAnalysis &AA_, AssumptionCache &AC_,
-               std::function<const LoopAccessInfo &(Loop &)> &GetLAA_,
+               std::function<const LoopAccessInfo &(Loop &, bool)> &GetLAA_,
                OptimizationRemarkEmitter &ORE_, ProfileSummaryInfo *PSI_);
 
   bool processLoop(Loop *L);
 };
 
 /// Reports a vectorization failure: print \p DebugMsg for debugging
 /// purposes along with the corresponding optimization remark \p RemarkName.
 /// If \p I is passed, it is an instruction that prevents vectorization.
 /// Otherwise, the loop \p TheLoop is used for the location of the remark.
 void reportVectorizationFailure(const StringRef DebugMsg,
     const StringRef OREMsg, const StringRef ORETag,
     OptimizationRemarkEmitter *ORE, Loop *TheLoop, Instruction *I = nullptr);
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZE_H

llvm/lib/Analysis/LoopAccessAnalysis.cpp

LLVM_DEBUG(dbgs() << "LAA: Positive distance " << Val.getSExtValue()
                     << " with max VF = " << MaxVF << '\n');
   uint64_t MaxVFInBits = MaxVF * TypeByteSize * 8;
   MaxSafeRegisterWidth = std::min(MaxSafeRegisterWidth, MaxVFInBits);
   return Dependence::BackwardVectorizable;
 }
 
 bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets,
                                    MemAccessInfoList &CheckDeps,
-                                   const ValueToValueMap &Strides) {
+                                   const ValueToValueMap &Strides,
+                                   bool UnknownDepHint) {
 
   MaxSafeDepDistBytes = -1;
   SmallPtrSet<MemAccessInfo, 8> Visited;
+  Status = VectorizationSafetyStatus::Safe;
   for (MemAccessInfo CurAccess : CheckDeps) {
     if (Visited.count(CurAccess))
       continue;
 
     // Get the relevant memory access set.
     EquivalenceClasses<MemAccessInfo>::iterator I =
       AccessSets.findValue(AccessSets.getLeaderValue(CurAccess));
 
while (AI != AE) {
             auto B = std::make_pair(&*OI, *I2);
 
             assert(*I1 != *I2);
             if (*I1 > *I2)
               std::swap(A, B);
 
             Dependence::DepType Type =
                 isDependent(*A.first, A.second, *B.first, B.second, Strides);
+            // Update safety status depending on whether the Dependence type
+            // is safe. If Unknown Dependence type is to be considered safe,
+            // do not update safety status.
+            if (!UnknownDepHint ||
+                !(Dependence::isSafeForVectorization(Type) ==
+                VectorizationSafetyStatus::PossiblySafeWithRtChecks))
               mergeInStatus(Dependence::isSafeForVectorization(Type));
 
             // Gather dependences unless we accumulated MaxDependences
             // dependences.  In that case return as soon as we find the first
             // unsafe dependence.  This puts a limit on this quadratic
             // algorithm.
             if (RecordDependences) {
               if (Type != Dependence::NoDep)
                 Dependences.push_back(Dependence(A.second, B.second, Type));
if (ExitCount == PSE->getSE()->getCouldNotCompute()) {
     return false;
   }
 
   return true;
 }
 
 void LoopAccessInfo::analyzeLoop(AliasAnalysis *AA, LoopInfo *LI,
                                  const TargetLibraryInfo *TLI,
-                                 DominatorTree *DT) {
+                                 DominatorTree *DT,
+                                 bool UnknownDepHint) {
   typedef SmallPtrSet<Value*, 16> ValueSet;
 
   // Holds the Load and Store instructions.
   SmallVector<LoadInst *, 16> Loads;
   SmallVector<StoreInst *, 16> Stores;
 
   // Holds all the different accesses in the loop.
   unsigned NumReads = 0;
void LoopAccessInfo::analyzeLoop(AliasAnalysis *AA, LoopInfo *LI,
 
   LLVM_DEBUG(
     dbgs() << "LAA: May be able to perform a memory runtime check if needed.\n");
 
   CanVecMem = true;
   if (Accesses.isDependencyCheckNeeded()) {
     LLVM_DEBUG(dbgs() << "LAA: Checking memory dependencies\n");
     CanVecMem = DepChecker->areDepsSafe(
-        DependentAccesses, Accesses.getDependenciesToCheck(), SymbolicStrides);
+        DependentAccesses, Accesses.getDependenciesToCheck(), SymbolicStrides,
+        UnknownDepHint);
     MaxSafeDepDistBytes = DepChecker->getMaxSafeDepDistBytes();
 
     if (!CanVecMem && DepChecker->shouldRetryWithRuntimeCheck()) {
       LLVM_DEBUG(dbgs() << "LAA: Retrying with memory checks\n");
 
       // Clear the dependency checks. We assume they are not needed.
       Accesses.resetDepChecks(*DepChecker);
 
       PtrRtChecking->reset();
       PtrRtChecking->Need = true;
void LoopAccessInfo::collectStridedAccess(Value *MemAccess) {
   LLVM_DEBUG(dbgs() << "LAA: Found a strided access that we can version.");
 
   SymbolicStrides[Ptr] = Stride;
   StrideSet.insert(Stride);
 }
 
 LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE,
                                const TargetLibraryInfo *TLI, AliasAnalysis *AA,
-                               DominatorTree *DT, LoopInfo *LI)
+                               DominatorTree *DT, LoopInfo *LI,
+                               bool UnknownDepHint)
     : PSE(std::make_unique<PredicatedScalarEvolution>(*SE, *L)),
       PtrRtChecking(std::make_unique<RuntimePointerChecking>(SE)),
       DepChecker(std::make_unique<MemoryDepChecker>(*PSE, L)), TheLoop(L),
       NumLoads(0), NumStores(0), MaxSafeDepDistBytes(-1), CanVecMem(false),
       HasConvergentOp(false),
       HasDependenceInvolvingLoopInvariantAddress(false) {
   if (canAnalyzeLoop())
-    analyzeLoop(AA, LI, TLI, DT);
+    analyzeLoop(AA, LI, TLI, DT, UnknownDepHint);
 }
 
 void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
   if (CanVecMem) {
     OS.indent(Depth) << "Memory dependences are safe";
     if (MaxSafeDepDistBytes != -1ULL)
       OS << " with a maximum dependence distance of " << MaxSafeDepDistBytes
          << " bytes";
void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
   PSE->getUnionPredicate().print(OS, Depth);
 
   OS << "\n";
 
   OS.indent(Depth) << "Expressions re-written:\n";
   PSE->print(OS, Depth);
 }
 
-const LoopAccessInfo &LoopAccessLegacyAnalysis::getInfo(Loop *L) {
+const LoopAccessInfo &LoopAccessLegacyAnalysis::getInfo(Loop *L,
+                                                        bool UnknownDepHint) {
   auto &LAI = LoopAccessInfoMap[L];
 
   if (!LAI)
-    LAI = std::make_unique<LoopAccessInfo>(L, SE, TLI, AA, DT, LI);
+    LAI = std::make_unique<LoopAccessInfo>(L, SE, TLI, AA, DT, LI,
+                                           UnknownDepHint);
 
   return *LAI.get();
 }
 
 void LoopAccessLegacyAnalysis::print(raw_ostream &OS, const Module *M) const {
   LoopAccessLegacyAnalysis &LAA = *const_cast<LoopAccessLegacyAnalysis *>(this);
 
   for (Loop *TopLevelLoop : *LI)

llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

case HK_WIDTH:
     return isPowerOf2_32(Val) && Val <= VectorizerParams::MaxVectorWidth;
   case HK_UNROLL:
     return isPowerOf2_32(Val) && Val <= MaxInterleaveFactor;
   case HK_FORCE:
     return (Val <= 1);
   case HK_ISVECTORIZED:
   case HK_PREDICATE:
     return (Val == 0 || Val == 1);
+  case HK_IVDEP:
+    return (Val == 1);
   }
   return false;
 }
 
 LoopVectorizeHints::LoopVectorizeHints(const Loop *L,
                                        bool InterleaveOnlyWhenForced,
                                        OptimizationRemarkEmitter &ORE)
     : Width("vectorize.width", VectorizerParams::VectorizationFactor, HK_WIDTH),
       Interleave("interleave.count", InterleaveOnlyWhenForced, HK_UNROLL),
       Force("vectorize.enable", FK_Undefined, HK_FORCE),
       IsVectorized("isvectorized", 0, HK_ISVECTORIZED),
-      Predicate("vectorize.predicate.enable", 0, HK_PREDICATE), TheLoop(L),
+      Predicate("vectorize.predicate.enable", 0, HK_PREDICATE),
+      Ivdep("vectorize.ivdep.enable", 0, HK_IVDEP), TheLoop(L),
       ORE(ORE) {
   // Populate values with existing loop metadata.
   getHintsFromMetadata();
 
   // force-vector-interleave overrides DisableInterleaving.
   if (VectorizerParams::isInterleaveForced())
     Interleave.Value = VectorizerParams::VectorizationInterleave;
 
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, &IsVectorized, &Predicate};
+  Hint *Hints[] = {&Width, &Interleave, &Force, &IsVectorized, &Predicate,
+                   &Ivdep};
   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;
     }
bool LoopVectorizationLegality::canVectorizeInstrs() {
   // will create another.
   if (PrimaryInduction && WidestIndTy != PrimaryInduction->getType())
     PrimaryInduction = nullptr;
 
   return true;
 }
 
 bool LoopVectorizationLegality::canVectorizeMemory() {
-  LAI = &(*GetLAA)(*TheLoop);
+  LAI = &(*GetLAA)(*TheLoop, Hints->getIvdep());
   const OptimizationRemarkAnalysis *LAR = LAI->getReport();
   if (LAR) {
     ORE->emit([&]() {
       return OptimizationRemarkAnalysis(Hints->vectorizeAnalysisPassName(),
                                         "loop not vectorized: ", *LAR);
     });
   }
   if (!LAI->canVectorizeMemory())

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

bool runOnFunction(Function &F) override {
     auto *TLI = TLIP ? &TLIP->getTLI(F) : nullptr;
     auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
     auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
     auto *LAA = &getAnalysis<LoopAccessLegacyAnalysis>();
     auto *DB = &getAnalysis<DemandedBitsWrapperPass>().getDemandedBits();
     auto *ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
     auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
 
-    std::function<const LoopAccessInfo &(Loop &)> GetLAA =
-        [&](Loop &L) -> const LoopAccessInfo & { return LAA->getInfo(&L); };
+    std::function<const LoopAccessInfo &(Loop &, bool)> GetLAA =
+        [&](Loop &L, bool UnknownDepHint) -> const LoopAccessInfo &
+                                             { return LAA->
+                                               getInfo(&L, UnknownDepHint); };
 
     return Impl.runImpl(F, *SE, *LI, *TTI, *DT, *BFI, TLI, *DB, *AA, *AC,
                         GetLAA, *ORE, PSI);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<BlockFrequencyInfoWrapperPass>();
#endif /* NDEBUG */
   LLVM_DEBUG(verifyFunction(*L->getHeader()->getParent()));
   return true;
 }
 
 bool LoopVectorizePass::runImpl(
     Function &F, ScalarEvolution &SE_, LoopInfo &LI_, TargetTransformInfo &TTI_,
     DominatorTree &DT_, BlockFrequencyInfo &BFI_, TargetLibraryInfo *TLI_,
     DemandedBits &DB_, AliasAnalysis &AA_, AssumptionCache &AC_,
-    std::function<const LoopAccessInfo &(Loop &)> &GetLAA_,
+    std::function<const LoopAccessInfo &(Loop &, bool)> &GetLAA_,
     OptimizationRemarkEmitter &ORE_, ProfileSummaryInfo *PSI_) {
   SE = &SE_;
   LI = &LI_;
   TTI = &TTI_;
   DT = &DT_;
   BFI = &BFI_;
   TLI = TLI_;
   AA = &AA_;
PreservedAnalyses LoopVectorizePass::run(Function &F,
     auto &AC = AM.getResult<AssumptionAnalysis>(F);
     auto &DB = AM.getResult<DemandedBitsAnalysis>(F);
     auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
     MemorySSA *MSSA = EnableMSSALoopDependency
                           ? &AM.getResult<MemorySSAAnalysis>(F).getMSSA()
                           : nullptr;
 
     auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
-    std::function<const LoopAccessInfo &(Loop &)> GetLAA =
-        [&](Loop &L) -> const LoopAccessInfo & {
+    std::function<const LoopAccessInfo &(Loop &, bool)> GetLAA =
+        [&](Loop &L, bool UnknownDepHint) -> const LoopAccessInfo & {
       LoopStandardAnalysisResults AR = {AA, AC, DT, LI, SE, TLI, TTI, MSSA};
       return LAM.getResult<LoopAccessAnalysis>(L, AR);
     };
     const ModuleAnalysisManager &MAM =
         AM.getResult<ModuleAnalysisManagerFunctionProxy>(F).getManager();
     ProfileSummaryInfo *PSI =
         MAM.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
     bool Changed =

llvm/test/Transforms/LoopVectorize/X86/ivdep-alias.ll

+; RUN: opt < %s -O3 -S | FileCheck %s
+; IR generated for a function containing the loop:
+;   #pragma clang loop ivdep(enable)
+;   for (int i=0; i<LEN_1D; i++)
+;     a[b[i]]++
+; where LEN_1D is an integer constant.
+; The above is an unknown dependency as the vectorizer cannot determine if
+; vectorizing accesses to a[b[i]] will be safe or unsafe.
+; Check if loop has been vectorized when ivdep is present.
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: noinline nounwind uwtable
+define dso_local i32* @addLoops(i32* noalias %a, i32* noalias %b, i32 %LEN_1D) #0 {
+entry:
+  %a.addr = alloca i32*, align 8
+  %b.addr = alloca i32*, align 8
+  %LEN_1D.addr = alloca i32, align 4
+  %i = alloca i32, align 4
+  store i32* %a, i32** %a.addr, align 8
+  store i32* %b, i32** %b.addr, align 8
+  store i32 %LEN_1D, i32* %LEN_1D.addr, align 4
+  store i32 0, i32* %i, align 4
+  br label %for.cond
+
+; CHECK: vector.ph:
+; CHECK-NEXT: %n.vec = and i64 %wide.trip.count, 4294967292
+for.cond:                                         ; preds = %for.inc, %entry
+  %0 = load i32, i32* %i, align 4
+  %1 = load i32, i32* %LEN_1D.addr, align 4
+  %cmp = icmp slt i32 %0, %1
+  br i1 %cmp, label %for.body, label %for.end
+; CHECK: br label %vector.body
+
+; CHECK: vector.body:
+for.body:                                         ; preds = %for.cond
+  %2 = load i32*, i32** %a.addr, align 8
+  %3 = load i32*, i32** %b.addr, align 8
+; CHECK: %wide.load = load <4 x i32>, <4 x i32>* %1, align 4
+; CHECK: %3 = extractelement <4 x i64> %2, i32 0
+  %4 = load i32, i32* %i, align 4
+  %idxprom = sext i32 %4 to i64
+  %arrayidx = getelementptr inbounds i32, i32* %3, i64 %idxprom
+  %5 = load i32, i32* %arrayidx, align 4
+; CHECK: %16 = insertelement <4 x i32> %15, i32 %12, i32 1
+; CHECK: %21 = extractelement <4 x i32> %19, i32 1
+  %idxprom1 = sext i32 %5 to i64
+  %arrayidx2 = getelementptr inbounds i32, i32* %2, i64 %idxprom1
+  %6 = load i32, i32* %arrayidx2, align 4
+  %inc = add nsw i32 %6, 1
+  store i32 %inc, i32* %arrayidx2, align 4
+  br label %for.inc
+; CHECK: %24 = icmp eq i64 %index.next, %n.vec
+; CHECK: br i1 %24, label %middle.block, label %vector.body, !llvm.loop !2
+
+for.inc:                                          ; preds = %for.body
+  %7 = load i32, i32* %i, align 4
+  %inc3 = add nsw i32 %7, 1
+  store i32 %inc3, i32* %i, align 4
+  br label %for.cond, !llvm.loop !2
+
+for.end:                                          ; preds = %for.cond
+  %8 = load i32*, i32** %a.addr, align 8
+  ret i32* %8
+}
+
+attributes #0 = { noinline nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 10.0.0 (https://github.com/llvm/llvm-project 8a5bfbe6db2824642bf9a1d27a24c5b6132b244f)"}
+; CHECK: !2 = distinct !{!2, !3}
+; CHECK-NEXT: !3 = !{!"llvm.loop.isvectorized", i32 1}
+; CHECK-NEXT: !4 = distinct !{!4, !5, !3}
+; CHECK-NEXT: !5 = !{!"llvm.loop.unroll.runtime.disable"}
+!2 = distinct !{!2, !3, !4}
+!3 = !{!"llvm.loop.vectorize.ivdep.enable", i1 true}
+!4 = !{!"llvm.loop.vectorize.enable", i1 true}

llvm/test/Transforms/LoopVectorize/X86/ivdep-novec.ll

+; RUN: opt < %s -O3 -S | FileCheck %s
+; IR generated for a function containing the loop:
+;   #pragma clang loop ivdep(enable)
+;     for (i = 1; i < n; i++)
+;       A[i] = A[i] + A[i-1];
+; where n is an integer constants.
+; The above dependency can be determine by the vectorizer to be unsafe for
+; vectorization.
+; Should not vectorize even if ivdep is present.
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: noinline nounwind uwtable
+define dso_local i32* @calcDepArray(i32* %A, i32 %n) #0 {
+entry:
+  %A.addr = alloca i32*, align 8
+  %n.addr = alloca i32, align 4
+  %i = alloca i32, align 4
+  store i32* %A, i32** %A.addr, align 8
+  store i32 %n, i32* %n.addr, align 4
+  store i32 1, i32* %i, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %0 = load i32, i32* %i, align 4
+  %1 = load i32, i32* %n.addr, align 4
+  %cmp = icmp slt i32 %0, %1
+  br i1 %cmp, label %for.body, label %for.end
+
+; CHECK: for.body:
+for.body:                                         ; preds = %for.cond
+  %2 = load i32*, i32** %A.addr, align 8
+  %3 = load i32, i32* %i, align 4
+  %idxprom = sext i32 %3 to i64
+  %arrayidx = getelementptr inbounds i32, i32* %2, i64 %idxprom
+  %4 = load i32, i32* %arrayidx, align 4
+  %5 = load i32*, i32** %A.addr, align 8
+  %6 = load i32, i32* %i, align 4
+  %sub = sub nsw i32 %6, 1
+  %idxprom1 = sext i32 %sub to i64
+  %arrayidx2 = getelementptr inbounds i32, i32* %5, i64 %idxprom1
+  %7 = load i32, i32* %arrayidx2, align 4
+  %add = add nsw i32 %4, %7
+  %8 = load i32*, i32** %A.addr, align 8
+  %9 = load i32, i32* %i, align 4
+  %idxprom3 = sext i32 %9 to i64
+  %arrayidx4 = getelementptr inbounds i32, i32* %8, i64 %idxprom3
+  store i32 %add, i32* %arrayidx4, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %10 = load i32, i32* %i, align 4
+  %inc = add nsw i32 %10, 1
+  store i32 %inc, i32* %i, align 4
+  br label %for.cond, !llvm.loop !2
+
+for.end:                                          ; preds = %for.cond
+  %11 = load i32*, i32** %A.addr, align 8
+  ret i32* %11
+}
+
+attributes #0 = { noinline nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 10.0.0 (https://github.com/llvm/llvm-project 8a5bfbe6db2824642bf9a1d27a24c5b6132b244f)"}
+; CHECK: !2 = distinct !{!2, !3, !4}
+; CHECK-NEXT: !3 = !{!"llvm.loop.vectorize.ivdep.enable", i1 true}
+; CHECK-NEXT: !4 = !{!"llvm.loop.vectorize.enable", i1 true}
+!2 = distinct !{!2, !3, !4}
+!3 = !{!"llvm.loop.vectorize.ivdep.enable", i1 true}
+!4 = !{!"llvm.loop.vectorize.enable", i1 true}

llvm/test/Transforms/LoopVectorize/X86/ivdep-unkbounds.ll

+; RUN: opt < %s -O3 -S | FileCheck %s
+; IR generated for a function containing the loop:
+;   #pragma clang loop ivdep(enable)
+;     for (i = 0; i < 64; i++)
+;       A[i*i] *= 2;
+; In the above example, the vectorizer cannot determine if
+; array accesses are within array bounds and is safe for vectorization.
+; Vectorizer regards it as an unknown dependency.
+; Check if loop has been vectorized when ivdep is present.
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: noinline nounwind uwtable
+define dso_local i32* @doubleArrayElements(i32* %A) #0 {
+entry:
+  %A.addr = alloca i32*, align 8
+  %i = alloca i32, align 4
+  store i32* %A, i32** %A.addr, align 8
+  store i32 0, i32* %i, align 4
+  br label %for.cond
+; CHECK: br label %vector.body
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %0 = load i32, i32* %i, align 4
+  %cmp = icmp slt i32 %0, 64
+  br i1 %cmp, label %for.body, label %for.end
+
+; CHECK: vector.body:
+for.body:                                         ; preds = %for.cond
+; CHECK: %vec.ind = phi <4 x i64> [ <i64 0, i64 1, i64 2, i64 3>, %entry ], [ %vec.ind.next, %vector.body ] 
+; CHECK: %0 = mul <4 x i64> %vec.ind, %vec.ind
+; CHECK: %2 = extractelement <4 x i64> %1, i32 0
+  %1 = load i32*, i32** %A.addr, align 8
+  %2 = load i32, i32* %i, align 4
+  %3 = load i32, i32* %i, align 4
+  %mul = mul nsw i32 %2, %3
+  %idxprom = sext i32 %mul to i64
+  %arrayidx = getelementptr inbounds i32, i32* %1, i64 %idxprom
+; CHECK: %15 = insertelement <4 x i32> %14, i32 %11, i32 1
+; CHECK: %21 = extractelement <4 x i32> %18, i32 2
+  %4 = load i32, i32* %arrayidx, align 4
+  %mul1 = mul nsw i32 %4, 2
+  store i32 %mul1, i32* %arrayidx, align 4
+; CHECK: %vec.ind.next = add <4 x i64> %vec.ind, <i64 4, i64 4, i64 4, i64 4>
+  br label %for.inc
+; CHECK: br i1 %23, label %for.end, label %vector.body, !llvm.loop !2
+
+for.inc:                                          ; preds = %for.body
+  %5 = load i32, i32* %i, align 4
+  %inc = add nsw i32 %5, 1
+  store i32 %inc, i32* %i, align 4
+  br label %for.cond, !llvm.loop !2
+
+for.end:                                          ; preds = %for.cond
+  %6 = load i32*, i32** %A.addr, align 8
+  ret i32* %6
+}
+
+attributes #0 = { noinline nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 10.0.0 (https://github.com/llvm/llvm-project 8a5bfbe6db2824642bf9a1d27a24c5b6132b244f)"}
+; CHECK: !2 = distinct !{!2, !3}
+; CHECK-NEXT: !3 = !{!"llvm.loop.isvectorized", i32 1}
+!2 = distinct !{!2, !3, !4}
+!3 = !{!"llvm.loop.vectorize.ivdep.enable", i1 true}
+!4 = !{!"llvm.loop.vectorize.enable", i1 true}

llvm/test/Transforms/LoopVectorize/X86/ivdep-unkdep.ll

+; RUN: opt < %s -O3 -S | FileCheck %s
+; IR generated for a function containing the loop:
+;    #pragma clang loop ivdep(enable)
+;    for (i = 0; i < m; i++){
+;      a[i] = a[i + k] * c;
+; where m, k, c are integer constants.
+; The above is an unknown dependency as the vectorizer cannot determine if
+; accesses are independent and a[i + k] is within
+; array bounds. It depends on value of k and dependence is not determined to
+; be safe or unsafe.
+; Check if the loop has been vectorized when ivdep is present.
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: noinline nounwind uwtable
+define dso_local i32 @calcArray(i32* %a, i32 %m, i32 %k, i32 %c) #0 {
+entry:
+  %a.addr = alloca i32*, align 8
+  %m.addr = alloca i32, align 4
+  %k.addr = alloca i32, align 4
+  %c.addr = alloca i32, align 4
+  %i = alloca i32, align 4
+  store i32* %a, i32** %a.addr, align 8
+  store i32 %m, i32* %m.addr, align 4
+  store i32 %k, i32* %k.addr, align 4
+  store i32 %c, i32* %c.addr, align 4
+  store i32 0, i32* %i, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %0 = load i32, i32* %i, align 4
+  %1 = load i32, i32* %m.addr, align 4
+  %cmp = icmp slt i32 %0, %1
+  br i1 %cmp, label %for.body, label %for.end
+; CHECK: vector.ph
+; CHECK: %n.vec = and i64 %wide.trip.count, 4294967288
+; CHECK: %broadcast.splatinsert10 = insertelement <4 x i32> undef, i32 %c, i32 0
+; CHECK: %broadcast.splat11 = shufflevector <4 x i32> %broadcast.splatinsert10, <4 x i32> undef, <4 x i32> zeroinitializer
+; CHECK: br i1 %4, label %middle.block.unr-lcssa, label %vector.ph.new
+
+; CHECK: vector.ph.new:
+; CHECK: br label %vector.body
+
+for.body:                                         ; preds = %for.cond
+  %2 = load i32*, i32** %a.addr, align 8
+  %3 = load i32, i32* %i, align 4
+  %4 = load i32, i32* %k.addr, align 4
+  %add = add nsw i32 %3, %4
+  %idxprom = sext i32 %add to i64
+  %arrayidx = getelementptr inbounds i32, i32* %2, i64 %idxprom
+  %5 = load i32, i32* %arrayidx, align 4
+  %6 = load i32, i32* %c.addr, align 4
+; CHECK: %wide.load = load <4 x i32>, <4 x i32>* %7, align 4
+; CHECK: %10 = mul nsw <4 x i32> %wide.load, %broadcast.splat11
+; CHECK: store <4 x i32> %10, <4 x i32>* %13, align 4
+  %mul = mul nsw i32 %5, %6
+  %7 = load i32*, i32** %a.addr, align 8
+  %8 = load i32, i32* %i, align 4
+  %idxprom1 = sext i32 %8 to i64
+  %arrayidx2 = getelementptr inbounds i32, i32* %7, i64 %idxprom1
+  store i32 %mul, i32* %arrayidx2, align 4
+  br label %for.inc
+; CHECK:  br i1 %niter.ncmp.1, label %middle.block.unr-lcssa, label %vector.body, !llvm.loop !2
+
+for.inc:                                          ; preds = %for.body
+  %9 = load i32, i32* %i, align 4
+  %inc = add nsw i32 %9, 1
+  store i32 %inc, i32* %i, align 4
+  br label %for.cond, !llvm.loop !2
+
+for.end:                                          ; preds = %for.cond
+  ret i32 0
+}
+
+attributes #0 = { noinline nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 10.0.0 (https://github.com/llvm/llvm-project 8a5bfbe6db2824642bf9a1d27a24c5b6132b244f)"}
+; CHECK: !2 = distinct !{!2, !3}
+; CHECK-NEXT: !3 = !{!"llvm.loop.isvectorized", i32 1}
+; CHECK-NEXT: !4 = distinct !{!4, !5, !3}
+; CHECK-NEXT: !5 = !{!"llvm.loop.unroll.runtime.disable"}
+!2 = distinct !{!2, !3, !4}
+!3 = !{!"llvm.loop.vectorize.ivdep.enable", i1 true}
+!4 = !{!"llvm.loop.vectorize.enable", i1 true}