[LAA] Add remarks for unbounded array access

[malharJ]

Summary

Depends on D108371

[malharJ]

• Updated unit test
• Updated minor clang-formatting errors.

[malharJ]

• Updated unit test again (had missed something earlier)

[malharJ]

llvm/test/Transforms/LoopVectorize/X86/vectorization-remarks-missed.ll

200

This change is to address the comment: https://reviews.llvm.org/D108371#inline-1093152

I've updated the debug info in the test to point the loop to
at least the correct source line now.
( I assume this is some error in the initial test or it has been
written by hand )

[malharJ]

• Rebased patch to acquire changes from D108371
• minor updates in the lit test

[malharJ]

• Added YAML to LIT test

(This is in response to https://reviews.llvm.org/D108371#inline-1112148)

[sdesmalen]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

564

Instead of passing in the pointer with a default value of nullptr, can you make it a reference, so that it always gets set, e.g.

Value *&UncomputablePtr

That also removes the need for the conditional write.

llvm/test/Transforms/LoopVectorize/X86/vectorization-remarks-missed.ll

200

Is this an unrelated change?

[malharJ]

• Rebased patch onto parent.

[malharJ]

• Minor update to unit test.

[malharJ]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

564

Can we please leave it as initialised as nullptr ?

The conditional write ensures that the first unsafe dependence gets reported by the remark.

if (UncomputablePtr)
    *UncomputablePtr = Access.getPointer();

llvm/test/Transforms/LoopVectorize/X86/vectorization-remarks-missed.ll

200

Ok. I've submitted as a separate commit to avoid any confusion.
https://github.com/llvm/llvm-project/commit/b75bdff4a0e91af1237ba77adce2f9fc7198ec26

[malharJ]

• Changed UncomputablePtr parameter to be a reference to a pointer.

[malharJ]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

564

Ok please ignore the above. I've made the change as suggested,

But I didn't remove that bit in the code.
The conditional write ensures that the first unsafe dependence gets reported by the remark.

if (!UncomputablePtr)
    UncomputablePtr = Access.getPointer();

[malharJ]

• trivial (clang) formatting updates

[sdesmalen]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

564

But I didn't remove that bit in the code.
The conditional write ensures that the first unsafe dependence gets reported by the remark.

That should be the choice of the caller, not the callee. If the caller doesn't want the value to be overwritten, it should pass a dummy variable

802

I believe this check should be removed (see my other comment as well)

2114

This variable aliases with UncomputablePtr defined on line 2075. Either pass in the same variable, or give this variable a different name.

[malharJ]

• removed conditional write of UncomputablePtr

[sdesmalen]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

2083–2086

Before this change, recordAnalysis was called unconditionally, but now it is only called if UncomputablePtr is set. I don't think that's intentional, so you can instead just do this:

auto *I = dyn_cast_or_null<Instruction>(UncomputablePtr);
recordAnalysis("CantIdentifyArrayBounds", I) << "cannot identify array bounds";

2114

nit: s/UncomputablePtr2/UncomputablePtrUnused/

[malharJ]

• call recordAnalysis unconditionally.

[malharJ]

• updated to pass uncomputableptr to recordAnalysis()

[malharJ]

ping.

[sdesmalen]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

2114

nit: I'm not really a fan of the name, so personally I would prefer to reuse the old variable, e.g. reset it first:

UncomputablePtr = nullptr;

and then pass that into canCheckPtrAtRT.

[malharJ]

Thanks a lot for the review !

llvm/lib/Analysis/LoopAccessAnalysis.cpp

public:
 
   /// Check whether we can check the pointers at runtime for
   /// non-intersection.
   ///
   /// Returns true if we need no check or if we do and we can generate them
   /// (i.e. the pointers have computable bounds).
   bool canCheckPtrAtRT(RuntimePointerChecking &RtCheck, ScalarEvolution *SE,
                        Loop *TheLoop, const ValueToValueMap &Strides,
-                       bool ShouldCheckWrap = false);
+                       bool ShouldCheckWrap = false,
+                       Value **UncomputablePtr = nullptr);
 
   /// Goes over all memory accesses, checks whether a RT check is needed
   /// and builds sets of dependent accesses.
   void buildDependenceSets() {
     processMemAccesses();
   }
 
   /// Initial processing of memory accesses determined that we need to
bool AccessAnalysis::createCheckForAccess(RuntimePointerChecking &RtCheck,
   LLVM_DEBUG(dbgs() << "LAA: Found a runtime check ptr:" << *Ptr << '\n');
 
   return true;
  }
 
 bool AccessAnalysis::canCheckPtrAtRT(RuntimePointerChecking &RtCheck,
                                      ScalarEvolution *SE, Loop *TheLoop,
                                      const ValueToValueMap &StridesMap,
-                                     bool ShouldCheckWrap) {
+                                     bool ShouldCheckWrap, Value **UncomputablePtr) {
   // Find pointers with computable bounds. We are going to use this information
   // to place a runtime bound check.
   bool CanDoRT = true;
 
   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 = 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;
 
     // First, count how many write and read accesses are in the alias set. Also
     // collect MemAccessInfos for later.
     SmallVector<MemAccessInfo, 4> AccessInfos;
if (NeedsAliasSetRTCheck && !CanDoAliasSetRT) {
       // We know that we need these checks, so we can now be more aggressive
       // and add further checks if required (overflow checks).
       CanDoAliasSetRT = true;
       for (auto Access : Retries)
         if (!createCheckForAccess(RtCheck, Access, StridesMap, DepSetId,
                                   TheLoop, RunningDepId, ASId,
                                   ShouldCheckWrap, /*Assume=*/true)) {
           CanDoAliasSetRT = false;
+          if (UncomputablePtr)
+            *UncomputablePtr = Access.getPointer();
           break;
         }
     }
 
     CanDoRT &= CanDoAliasSetRT;
     MayNeedRTCheck |= NeedsAliasSetRTCheck;
     ++ASId;
   }
for (unsigned i = 0; i < NumPointers; ++i) {
     }
   }
 
   if (MayNeedRTCheck && CanDoRT)
     RtCheck.generateChecks(DepCands, IsDepCheckNeeded);
 
   LLVM_DEBUG(dbgs() << "LAA: We need to do " << RtCheck.getNumberOfChecks()
                     << " pointer comparisons.\n");
 
   // If we can do run-time checks, but there are no checks, no runtime checks
   // are needed. This can happen when all pointers point to the same underlying
   // object for example.
   RtCheck.Need = CanDoRT ? RtCheck.getNumberOfChecks() != 0 : MayNeedRTCheck;
 
   bool CanDoRTIfNeeded = !RtCheck.Need || CanDoRT;
   if (!CanDoRTIfNeeded)
     RtCheck.reset();
void LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI,
   }
 
   // Build dependence sets and check whether we need a runtime pointer bounds
   // check.
   Accesses.buildDependenceSets();
 
   // Find pointers with computable bounds. We are going to use this information
   // to place a runtime bound check.
-  bool CanDoRTIfNeeded = Accesses.canCheckPtrAtRT(*PtrRtChecking, PSE->getSE(),
-                                                  TheLoop, SymbolicStrides);
+  Value *UncomputablePtr = nullptr;
+  bool CanDoRTIfNeeded =
+      Accesses.canCheckPtrAtRT(*PtrRtChecking, PSE->getSE(), TheLoop,
+                               SymbolicStrides, false, &UncomputablePtr);
   if (!CanDoRTIfNeeded) {
-    recordAnalysis("CantIdentifyArrayBounds") << "cannot identify array bounds";
+    if (auto *I = dyn_cast_or_null<Instruction>(UncomputablePtr)) {
+      recordAnalysis("CantIdentifyArrayBounds", I)
+          << "cannot identify array bounds";
+    }
     LLVM_DEBUG(dbgs() << "LAA: We can't vectorize because we can't find "
                       << "the array bounds.\n");
     CanVecMem = false;
     return;
   }
 
   LLVM_DEBUG(
     dbgs() << "LAA: May be able to perform a memory runtime check if needed.\n");
if (!CanVecMem && DepChecker->shouldRetryWithRuntimeCheck()) {
       // Clear the dependency checks. We assume they are not needed.
       Accesses.resetDepChecks(*DepChecker);
 
       PtrRtChecking->reset();
       PtrRtChecking->Need = true;
 
       auto *SE = PSE->getSE();
       CanDoRTIfNeeded = Accesses.canCheckPtrAtRT(*PtrRtChecking, SE, TheLoop,
                                                  SymbolicStrides, true);
 
       // Check that we found the bounds for the pointer.
       if (!CanDoRTIfNeeded) {
         recordAnalysis("CantCheckMemDepsAtRunTime")
             << "cannot check memory dependencies at runtime";
         LLVM_DEBUG(dbgs() << "LAA: Can't vectorize with memory checks\n");
         CanVecMem = false;
         return;

llvm/test/Transforms/LoopVectorize/X86/vectorization-remarks-missed.ll

 ; CHECK: remark: source.cpp:12:8: loop not vectorized: vectorization and interleaving are explicitly disabled, or the loop has already been vectorized
 
 ; void test_array_bounds(int *A, int *B, int Length) {
 ; #pragma clang loop vectorize(enable)
 ;   for (int i = 0; i < Length; i++)
 ;     A[i] = A[B[i]];
 ; }
 ; CHECK: remark: source.cpp:19:5: loop not vectorized: cannot identify array bounds
-; CHECK: remark: source.cpp:19:5: loop not vectorized
-; CHECK: warning: source.cpp:19:5: loop not vectorized: the optimizer was unable to perform the requested transformation; the transformation might be disabled or specified as part of an unsupported transformation ordering
+; CHECK: remark: source.cpp:18:8: loop not vectorized (Force=true)
+; CHECK: warning: source.cpp:18:8: loop not vectorized: the optimizer was unable to perform the requested transformation; the transformation might be disabled or specified as part of an unsupported transformation ordering
 
 ; int foo();
 ; void test_multiple_failures(int *A) {
 ;   int k = 0;
 ; #pragma clang loop vectorize(enable) interleave(enable)
 ;   for (int i = 0; i < 1000; i+=A[i]) {
 ;     if (A[i])
 ;       k = foo();

 ; YAML-NEXT: Function:        _Z17test_array_boundsPiS_i
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - String:          'loop not vectorized: '
 ; YAML-NEXT:   - String:          cannot identify array bounds
 ; YAML-NEXT: ...
 ; YAML-NEXT: --- !Missed
 ; YAML-NEXT: Pass:            loop-vectorize
 ; YAML-NEXT: Name:            MissedDetails
-; YAML-NEXT: DebugLoc:        { File: source.cpp, Line: 19, Column: 5 }
+; YAML-NEXT: DebugLoc:        { File: source.cpp, Line: 18, Column: 8 }
 ; YAML-NEXT: Function:        _Z17test_array_boundsPiS_i
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - String:          loop not vectorized
 ; YAML-NEXT:   - String:          ' (Force='
 ; YAML-NEXT:   - Force:           'true'
 ; YAML-NEXT:   - String:          ')'
 ; YAML-NEXT: ...
 ; YAML-NEXT: --- !Failure
 ; YAML-NEXT: Pass:            transform-warning
 ; YAML-NEXT: Name:            FailedRequestedVectorization
-; YAML-NEXT: DebugLoc:        { File: source.cpp, Line: 19, Column: 5 }
+; YAML-NEXT: DebugLoc:        { File: source.cpp, Line: 18, Column: 8 }
 ; YAML-NEXT: Function:        _Z17test_array_boundsPiS_i
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - String:          'loop not vectorized: the optimizer was unable to perform the requested transformation; the transformation might be disabled or specified as part of an unsupported transformation ordering'
 ; YAML-NEXT: ...
 ; YAML-NEXT: --- !Analysis
 ; YAML-NEXT: Pass:            loop-vectorize
 ; YAML-NEXT: Name:            NoCFGForSelect
 ; YAML-NEXT: DebugLoc:        { File: source.cpp, Line: 29, Column: 7 }

 
 ; Function Attrs: nounwind optsize ssp uwtable
 define void @_Z17test_array_boundsPiS_i(i32* nocapture %A, i32* nocapture readonly %B, i32 %Length) #0 !dbg !8 {
 entry:
   %cmp9 = icmp sgt i32 %Length, 0, !dbg !32
   br i1 %cmp9, label %for.body.preheader, label %for.end, !dbg !32, !llvm.loop !34
 
 for.body.preheader:                               ; preds = %entry
-  br label %for.body, !dbg !35
+  br label %for.body, !dbg !32
 
 for.body:                                         ; preds = %for.body.preheader, %for.body
   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %for.body.preheader ]
   %arrayidx = getelementptr inbounds i32, i32* %B, i64 %indvars.iv, !dbg !35
   %0 = load i32, i32* %arrayidx, align 4, !dbg !35, !tbaa !18
   %idxprom1 = sext i32 %0 to i64, !dbg !35
   %arrayidx2 = getelementptr inbounds i32, i32* %A, i64 %idxprom1, !dbg !35
   %1 = load i32, i32* %arrayidx2, align 4, !dbg !35, !tbaa !18

llvm/test/Transforms/LoopVectorize/memory-dep-remarks.ll

 ; RUN: opt -passes='loop(require<access-info>),function(loop-vectorize)' -disable-output -pass-remarks-analysis=loop-vectorize < %s 2>&1 | FileCheck %s
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 
+; // Loop has an array element B[i] (%arrayidx in IR) being used as index to
+; // another array (A), and since the value of B[i] is unknown,
+; // the bound for array A is unknown.
+; void test_unknown_bounds(int* A, int* B, int n) {
+;     for(int i = 0; i < n ; ++i)
+;         A[i] = A[B[i]] + 1;
+; }
+
+; CHECK: remark: source.c:4:16: loop not vectorized: cannot identify array bounds
+
+define void @test_unknown_bounds(i32* nocapture %A, i32* nocapture readonly %B, i64 %n) !dbg !13 {
+entry:
+  %cmp10 = icmp sgt i64 %n, 0
+  br i1 %cmp10, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %idxprom1 = sext i32 %0 to i64, !dbg !35
+  %arrayidx2 = getelementptr inbounds i32, i32* %A, i64 %idxprom1, !dbg !35
+  %1 = load i32, i32* %arrayidx2, align 4, !dbg !35
+  %add = add nsw i32 %1, 1
+  %arrayidx4 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 %add, i32* %arrayidx4, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond.not = icmp eq i64 %indvars.iv.next, %n
+  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body, !dbg !28
+}
+
 ; // a) Dependence::NoDep
 ; // Loop containing only reads (here of the array A) does not hinder vectorization
 ; void test_nodep(int n, int* A, int* B) {
 ;   for(int i = 1; i < n ; ++i) {
 ;     B[i] = A[i-1] + A[i+2];
 ;   }
 ; }