[LAA] Modify canCheckPtrAtRT to analyze conflicting alias sets only

[joesavage]

Summary

Resolves an issue in which some loops cannot be auto-vectorized with
runtime checks despite all relevant alias sets having computable bounds.

[fhahn]

Thanks for illustrating the issue here. I was a bit surprised this happens, as canCheckPtrAtRT already contains code to figure out if runtime checks are needed for a alias set. But it turns out that it sets 'CanDoRT` to false for alias sets with uncomputable bounds, even if no runtime checks are required for the AS.

I've put up D80622 with an alternative fix, that slightly extends the existing logic in canCheckPtrAtRT to correctly handle this case. I think this has a slight advantage of not having 2 different alias set collections, which potentially could lead to confusion down the road (if the wrong one is used).

[fhahn]

IIUC this was subsumed by D80622. Marking as changes requested to clear up review queue.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

private:
 
   /// Set of pointers that are read only.
   SmallPtrSet<Value*, 16> ReadOnlyPtr;
 
   /// An alias set tracker to partition the access set by underlying object and
   //intrinsic property (such as TBAA metadata).
   AliasSetTracker AST;
 
+  /// Similar to above, but instead contains only the alias sets we care about
+  /// when doing runtime checks.
+  SmallVector<AliasSet *, 4> ReducedAST;
+
   LoopInfo *LI;
 
   /// Sets of potentially dependent accesses - members of one set share an
   /// underlying pointer. The set "CheckDeps" identfies which sets really need a
   /// dependence check.
   MemoryDepChecker::DepCandidates &DepCands;
 
   /// Initial processing of memory accesses determined that we may need
bool AccessAnalysis::canCheckPtrAtRT(RuntimePointerChecking &RtCheck,
   bool NeedRTCheck = false;
   if (!IsRTCheckAnalysisNeeded) return true;
 
   bool IsDepCheckNeeded = isDependencyCheckNeeded();
 
   // We assign a consecutive id to access from different alias sets.
   // Accesses between different groups doesn't need to be checked.
   unsigned ASId = 1;
-  for (auto &AS : AST) {
+  for (auto &AS : ReducedAST) {
     int NumReadPtrChecks = 0;
     int NumWritePtrChecks = 0;
     bool CanDoAliasSetRT = true;
 
     // We assign consecutive id to access from different dependence sets.
     // Accesses within the same set don't need a runtime check.
     unsigned RunningDepId = 1;
     DenseMap<Value *, unsigned> DepSetId;
 
     SmallVector<MemAccessInfo, 4> Retries;
 
-    for (auto A : AS) {
+    for (auto A : *AS) {
       Value *Ptr = A.getValue();
       bool IsWrite = Accesses.count(MemAccessInfo(Ptr, true));
       MemAccessInfo Access(Ptr, IsWrite);
 
       if (IsWrite)
         ++NumWritePtrChecks;
       else
         ++NumReadPtrChecks;
void AccessAnalysis::processMemAccesses() {
   LLVM_DEBUG(dbgs() << "  AST: "; AST.dump());
   LLVM_DEBUG(dbgs() << "LAA:   Accesses(" << Accesses.size() << "):\n");
   LLVM_DEBUG({
     for (auto A : Accesses)
       dbgs() << "\t" << *A.getPointer() << " (" <<
                 (A.getInt() ? "write" : (ReadOnlyPtr.count(A.getPointer()) ?
                                          "read-only" : "read")) << ")\n";
   });
+  ReducedAST.clear();
 
   // The AliasSetTracker has nicely partitioned our pointers by metadata
   // compatibility and potential for underlying-object overlap. As a result, we
   // only need to check for potential pointer dependencies within each alias
   // set.
   for (auto &AS : AST) {
     // Note that both the alias-set tracker and the alias sets themselves used
     // linked lists internally and so the iteration order here is deterministic
     // (matching the original instruction order within each set).
 
     bool SetHasWrite = false;
+    bool AnalyzeAS = false;
 
     // Map of pointers to last access encountered.
     typedef DenseMap<const Value*, MemAccessInfo> UnderlyingObjToAccessMap;
     UnderlyingObjToAccessMap ObjToLastAccess;
 
     // Set of access to check after all writes have been processed.
     PtrAccessSet DeferredAccesses;
 
for (int SetIteration = 0; SetIteration < 2; ++SetIteration) {
 
           // If this is a write - check other reads and writes for conflicts. If
           // this is a read only check other writes for conflicts (but only if
           // there is no other write to the ptr - this is an optimization to
           // catch "a[i] = a[i] + " without having to do a dependence check).
           if ((IsWrite || IsReadOnlyPtr) && SetHasWrite) {
             CheckDeps.push_back(Access);
             IsRTCheckAnalysisNeeded = true;
+            AnalyzeAS = true;
           }
 
           if (IsWrite)
             SetHasWrite = true;
 
           // Create sets of pointers connected by a shared alias set and
           // underlying object.
           typedef SmallVector<const Value *, 16> ValueVector;
for (int SetIteration = 0; SetIteration < 2; ++SetIteration) {
               DepCands.unionSets(Access, Prev->second);
 
             ObjToLastAccess[UnderlyingObj] = Access;
             LLVM_DEBUG(dbgs() << "  " << *UnderlyingObj << "\n");
           }
         }
       }
     }
+    if (AnalyzeAS)
+      ReducedAST.push_back(&AS);
   }
 }
 
 static bool isInBoundsGep(Value *Ptr) {
   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr))
     return GEP->isInBounds();
   return false;
 }

llvm/test/Transforms/LoopVectorize/AArch64/mult-stores-alias-set.ll

+; RUN: opt -loop-accesses -analyze -O3 -S < %s | FileCheck %s
+
+; In this particular loop we have a gather and two stores, where the
+; alias sets are as follows:
+;    Alias Set A: 1. Gather load
+;    Alias Set B: 1. First store, 2. second store
+; Our loop analysis code correctly determines that the two stores in a
+; single alias set (B) don't actually alias with each other. However,
+; this means we should only need to do runtime check analysis on alias
+; set B, since we know that A does not alias with B. If we also do
+; runtime check analysis of A we will produce an error saying we cannot
+; determine the runtime array bounds of the gather load. This test
+; makes sure we the analysis succeeds.
+
+; CHECK: Memory dependences are safe with run-time checks
+; CHECK:        %18 = bitcast float* %17 to i32*
+; CHECK:        %21 = bitcast float* %20 to i32*
+define dso_local void @foo(float* noalias nocapture, float* noalias nocapture readonly, i32* noalias nocapture readonly, i32) {
+  %5 = icmp sgt i32 %3, 0
+  br i1 %5, label %6, label %25
+
+; <label>:6:                                      ; preds = %4
+  %7 = sext i32 %3 to i64
+  %8 = zext i32 %3 to i64
+  br label %9
+
+; <label>:9:                                      ; preds = %9, %6
+  %10 = phi i64 [ 0, %6 ], [ %22, %9 ]
+  %11 = getelementptr inbounds i32, i32* %2, i64 %10
+  %12 = load i32, i32* %11, align 4, !tbaa !2
+  %13 = sext i32 %12 to i64
+  %14 = getelementptr inbounds float, float* %1, i64 %13
+  %15 = bitcast float* %14 to i32*
+  %16 = load i32, i32* %15, align 4, !tbaa !6
+  %17 = getelementptr inbounds float, float* %0, i64 %10
+  %18 = bitcast float* %17 to i32*
+  store i32 %16, i32* %18, align 4, !tbaa !6
+  %19 = add nsw i64 %10, %7
+  %20 = getelementptr inbounds float, float* %0, i64 %19
+  %21 = bitcast float* %20 to i32*
+  store i32 %16, i32* %21, align 4, !tbaa !6
+  %22 = add nuw nsw i64 %10, 1
+  %23 = icmp eq i64 %22, %8
+  br i1 %23, label %24, label %9
+
+; <label>:24:                                     ; preds = %9
+  br label %25
+
+; <label>:25:                                     ; preds = %24, %4
+  ret void
+}
+
+!2 = !{!3, !3, i64 0}
+!3 = !{!"int", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C/C++ TBAA"}
+!6 = !{!7, !7, i64 0}
+!7 = !{!"float", !4, i64 0}
+!8 = !{!9}
+!9 = distinct !{!9, !10}
+!10 = distinct !{!10, !"LVerDomain"}
+!11 = !{!12}
+!12 = distinct !{!12, !10}
+!13 = distinct !{!13, !14, !15}
+!14 = !{!"llvm.loop.vectorize.width", i32 1}
+!15 = !{!"llvm.loop.interleave.count", i32 1}
+!16 = distinct !{!16, !14, !15}