[LAA] Do not set CanDoRT to false for AS that do not need RT checks.

[fhahn]

Summary

Alternative approach to D80570.

canCheckPtrAtRT already contains checks the figure out for which alias
sets runtime checks are needed. But it currently sets CanDoRT to false
for alias sets for which we cannot do RT checks but also do not need
any.

If we know that we do not need RT checks based on the number of
reads/writes in the alias set, we can skip processing the AS.

This patch also adds an assertion to ensure that DepCands does not
contain more than one write from the alias set.

This patch still needs a test.

[dmgreen]

This seems to make sense. Do you have a testcase? Maybe the one from D80570 with some cleanup?

llvm/lib/Analysis/LoopAccessAnalysis.cpp

763

I think you need brackets around the ||

[fhahn]

Add reduced tests based on D80570., add missing ()

[dmgreen]

Thanks. LGTM

llvm/lib/Analysis/LoopAccessAnalysis.cpp

bool AccessAnalysis::canCheckPtrAtRT(RuntimePointerChecking &RtCheck,
 
   bool MayNeedRTCheck = 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;
+  unsigned ASId = 0;
   for (auto &AS : AST) {
     int NumReadPtrChecks = 0;
     int NumWritePtrChecks = 0;
     bool CanDoAliasSetRT = true;
+    ++ASId;
 
     // 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 &AS : AST) {
     // check them.  But there is no need to checks if there is only one
     // dependence set for this alias set.
     //
     // Note that this function computes CanDoRT and MayNeedRTCheck
     // independently. For example CanDoRT=false, MayNeedRTCheck=false means that
     // we have a pointer for which we couldn't find the bounds but we don't
     // actually need to emit any checks so it does not matter.
     bool NeedsAliasSetRTCheck = false;
-    if (!(IsDepCheckNeeded && CanDoAliasSetRT && RunningDepId == 2))
+    if (!(IsDepCheckNeeded && CanDoAliasSetRT && RunningDepId == 2)) {
       NeedsAliasSetRTCheck = (NumWritePtrChecks >= 2 ||
                              (NumReadPtrChecks >= 1 && NumWritePtrChecks >= 1));
+      // For alias sets without at least 2 writes or 1 write and 1 read, there
+      // is no need to generate RT checks and CanDoAliasSetRT for this alias set
+      // does not impact whether runtime checks can be generated.
+      if (!NeedsAliasSetRTCheck) {
+        assert((AS.size() <= 1 ||
+                all_of(AS,
+                       [this](auto AC) {
+                         MemAccessInfo AccessWrite(AC.getValue(), true);
+                         return DepCands.findValue(AccessWrite) ==
+                                DepCands.end();
+                       })) &&
+               "Can only skip updating CanDoRT below, if all entries in AS "
+               "are reads or there is at most 1 entry");
+        continue;
+      }
+    }
 
     // We need to perform run-time alias checks, but some pointers had bounds
     // that couldn't be checked.
     if (NeedsAliasSetRTCheck && !CanDoAliasSetRT) {
       // Reset the CanDoSetRt flag and retry all accesses that have failed.
       // We know that we need these checks, so we can now be more aggressive
       // and add further checks if required (overflow checks).
       CanDoAliasSetRT = true;

llvm/test/Transforms/LoopVectorize/alias-set-with-uncomputable-bounds.ll

+; RUN: opt  -loop-vectorize -force-vector-width=2 -S %s | FileCheck %s
+
+; Tests with alias sets that contain points with uncomputable bounds because
+; they include %offset.1, which is loaded in each loop iteration.
+
+; Alias set with uncomputable bounds contains a single load. We do not need
+; runtime checks for that group and it should not block vectorization.
+define void @test1_uncomputable_bounds_single_load(i32* noalias %ptr.1, i32* noalias %ptr.2, i32* noalias %ptr.3, i64 %N, i64 %X) {
+; CHECK-LABEL: define void @test1_uncomputable_bounds_single_load
+; CHECK:       vector.body
+; CHECK:         ret void
+
+entry:
+  %cond = icmp sgt i64 %N, 0
+  br i1 %cond, label %ph, label %exit
+
+ph:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %ph ], [ %iv.next, %loop ]
+  %gep.1 = getelementptr inbounds i32, i32* %ptr.3, i64 %iv
+  %offset.1 = load i32, i32* %gep.1, align 4
+  %gep.2 = getelementptr inbounds i32, i32* %ptr.2, i32 %offset.1
+  %lv = load i32, i32* %gep.2, align 4
+  %gep.3 = getelementptr inbounds i32, i32* %ptr.1, i64 %iv
+  store i32 %lv , i32* %gep.3, align 4
+  %offset.2 = add nsw i64 %iv, %X
+  %gep.4 = getelementptr inbounds i32, i32* %ptr.1, i64 %offset.2
+  store i32 %lv, i32* %gep.4, align 4
+  %iv.next = add nuw nsw i64 %iv, 1
+  %exitcond = icmp eq i64 %iv.next, %N
+  br i1 %exitcond, label %loop.exit, label %loop
+
+loop.exit:
+  br label %exit
+
+exit:
+  ret void
+}
+
+; Alias set with uncomputable bounds contains a single store. We do not need
+; runtime checks for that group and it should not block vectorization.
+define void @test2_uncomputable_bounds_single_store(i32* noalias %ptr.1, i32* noalias %ptr.2, i32* noalias %ptr.3, i64 %N, i64 %X) {
+; CHECK-LABEL: define void @test2_uncomputable_bounds_single_store
+; CHECK:       vector.body
+; CHECK:         ret void
+
+entry:
+  %cond = icmp sgt i64 %N, 0
+  br i1 %cond, label %ph, label %exit
+
+ph:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %ph ], [ %iv.next, %loop ]
+  %gep.1 = getelementptr inbounds i32, i32* %ptr.3, i64 %iv
+  %offset.1 = load i32, i32* %gep.1, align 4
+  %gep.2 = getelementptr inbounds i32, i32* %ptr.2, i32 %offset.1
+  store i32 20, i32* %gep.2, align 4
+  %gep.3 = getelementptr inbounds i32, i32* %ptr.1, i64 %iv
+  store i32 0 , i32* %gep.3, align 4
+  %offset.2 = add nsw i64 %iv, %X
+  %gep.4 = getelementptr inbounds i32, i32* %ptr.1, i64 %offset.2
+  store i32 10, i32* %gep.4, align 4
+  %iv.next = add nuw nsw i64 %iv, 1
+  %exitcond = icmp eq i64 %iv.next, %N
+  br i1 %exitcond, label %loop.exit, label %loop
+
+loop.exit:
+  br label %exit
+
+exit:
+  ret void
+}
+
+; Alias set with uncomputable bounds contains a load and a store. This blocks
+; vectorization, as we cannot generate runtime-checks for the set.
+define void @test3_uncomputable_bounds_load_store(i32* noalias %ptr.1, i32* noalias %ptr.2, i32* noalias %ptr.3, i64 %N, i64 %X) {
+; CHECK-LABEL: define void @test3_uncomputable_bounds_load_store
+; CHECK-NOT: vector.body
+
+entry:
+  %cond = icmp sgt i64 %N, 0
+  br i1 %cond, label %ph, label %exit
+
+ph:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %ph ], [ %iv.next, %loop ]
+  %gep.1 = getelementptr inbounds i32, i32* %ptr.3, i64 %iv
+  %offset.1 = load i32, i32* %gep.1, align 4
+  %gep.2 = getelementptr inbounds i32, i32* %ptr.2, i32 %offset.1
+  store i32 20, i32* %gep.2, align 4
+  %gep.22 = getelementptr inbounds i32, i32* %ptr.2, i64 %iv
+  %lv = load i32, i32* %gep.22, align 4
+  %gep.3 = getelementptr inbounds i32, i32* %ptr.1, i64 %iv
+  store i32 %lv , i32* %gep.3, align 4
+  %offset.2 = add nsw i64 %iv, %X
+  %gep.4 = getelementptr inbounds i32, i32* %ptr.1, i64 %offset.2
+  store i32 %lv, i32* %gep.4, align 4
+  %iv.next = add nuw nsw i64 %iv, 1
+  %exitcond = icmp eq i64 %iv.next, %N
+  br i1 %exitcond, label %loop.exit, label %loop
+
+loop.exit:
+  br label %exit
+
+exit:
+  ret void
+}
+
+; Alias set with uncomputable bounds contains a load and a store. This blocks
+; vectorization, as we cannot generate runtime-checks for the set.
+define void @test4_uncomputable_bounds_store_store(i32* noalias %ptr.1, i32* noalias %ptr.2, i32* noalias %ptr.3, i64 %N, i64 %X) {
+; CHECK-LABEL: define void @test4_uncomputable_bounds_store_store
+; CHECK-NOT: vector.body
+
+entry:
+  %cond = icmp sgt i64 %N, 0
+  br i1 %cond, label %ph, label %exit
+
+ph:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %ph ], [ %iv.next, %loop ]
+  %gep.1 = getelementptr inbounds i32, i32* %ptr.3, i64 %iv
+  %offset.1 = load i32, i32* %gep.1, align 4
+  %gep.2 = getelementptr inbounds i32, i32* %ptr.2, i32 %offset.1
+  store i32 20, i32* %gep.2, align 4
+  %gep.22 = getelementptr inbounds i32, i32* %ptr.2, i64 %iv
+  store i32 30, i32* %gep.22, align 4
+  %gep.3 = getelementptr inbounds i32, i32* %ptr.1, i64 %iv
+  store i32 0 , i32* %gep.3, align 4
+  %offset.2 = add nsw i64 %iv, %X
+  %gep.4 = getelementptr inbounds i32, i32* %ptr.1, i64 %offset.2
+  store i32 10, i32* %gep.4, align 4
+  %iv.next = add nuw nsw i64 %iv, 1
+  %exitcond = icmp eq i64 %iv.next, %N
+  br i1 %exitcond, label %loop.exit, label %loop
+
+loop.exit:
+  br label %exit
+
+exit:
+  ret void
+}