[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

563

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

563

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

563

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

563

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

823

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

2106–2108

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

2078–2079

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

2106–2108

nit: s/UncomputablePtr2/UncomputablePtrUnused/

[malharJ]

• call recordAnalysis unconditionally.

[malharJ]

• updated to pass uncomputableptr to recordAnalysis()

[malharJ]

ping.

[sdesmalen]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

2106–2108

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);
+                       Value *&UncomputablePtr, bool ShouldCheckWrap = false);
 
   /// 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
   /// perform dependency checking.
bool AccessAnalysis::createCheckForAccess(RuntimePointerChecking &RtCheck,
 
   bool IsWrite = Access.getInt();
   RtCheck.insert(TheLoop, Ptr, IsWrite, DepId, ASId, StridesMap, PSE);
   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) {
+                                     Value *&UncomputablePtr, bool ShouldCheckWrap) {
   // 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();
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;
+          UncomputablePtr = Access.getPointer();
           break;
         }
     }
 
     CanDoRT &= CanDoAliasSetRT;
     MayNeedRTCheck |= NeedsAliasSetRTCheck;
     ++ASId;
   }
 
   // If the pointers that we would use for the bounds comparison have different
   // address spaces, assume the values aren't directly comparable, so we can't
   // use them for the runtime check. We also have to assume they could
   // overlap. In the future there should be metadata for whether address spaces
   // are disjoint.
   unsigned NumPointers = RtCheck.Pointers.size();
   for (unsigned i = 0; i < NumPointers; ++i) {
     for (unsigned j = i + 1; j < NumPointers; ++j) {
       // Only need to check pointers between two different dependency sets.
       if (RtCheck.Pointers[i].DependencySetId ==
           RtCheck.Pointers[j].DependencySetId)
        continue;
       // Only need to check pointers in the same alias set.
       if (RtCheck.Pointers[i].AliasSetId != RtCheck.Pointers[j].AliasSetId)
         continue;
 
       Value *PtrI = RtCheck.Pointers[i].PointerValue;
       Value *PtrJ = RtCheck.Pointers[j].PointerValue;
 
       unsigned ASi = PtrI->getType()->getPointerAddressSpace();
       unsigned ASj = PtrJ->getType()->getPointerAddressSpace();
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, UncomputablePtr, false);
   if (!CanDoRTIfNeeded) {
-    recordAnalysis("CantIdentifyArrayBounds") << "cannot identify array bounds";
+    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);
+      Value *UncomputablePtrUnused;
+      CanDoRTIfNeeded = Accesses.canCheckPtrAtRT(
+          *PtrRtChecking, SE, TheLoop, SymbolicStrides, UncomputablePtrUnused, 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:18:8: loop not vectorized: cannot identify array bounds
+; CHECK: remark: source.cpp:19:5: loop not vectorized: cannot identify array bounds
 ; 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]) {

 ; YAML-NEXT: DebugLoc:        { File: source.cpp, Line: 12, Column: 8 }
 ; YAML-NEXT: Function:        _Z13test_disabledPii
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - String:          'loop not vectorized: vectorization and interleaving are explicitly disabled, or the loop has already been vectorized
 ; YAML-NEXT: ...
 ; YAML-NEXT: --- !Analysis
 ; YAML-NEXT: Pass:            ''
 ; YAML-NEXT: Name:            CantIdentifyArrayBounds
-; YAML-NEXT: DebugLoc:        { File: source.cpp, Line: 18, Column: 8 }
+; YAML-NEXT: DebugLoc:        { File: source.cpp, Line: 19, Column: 5 }
 ; 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

 
 ; 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 !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
 ; RUN: opt < %s -passes='loop(require<access-info>),function(loop-vectorize)' -o /dev/null -pass-remarks-output=%t.yaml
 ; RUN: cat %t.yaml | FileCheck -check-prefix=YAML %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 n, int* A, int* B) {
+;     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(i64 %n, i32* nocapture %A, i32* nocapture readonly %B) !dbg !13 {
+entry:
+  %cmp10 = icmp sgt i64 %n, 0
+  br i1 %cmp10, label %for.body, label %for.cond.cleanup
+
+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
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+}
+
 ; // 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];
 ;   }
 ; }
 
for.body:                                         ; preds = %entry, %for.body
   br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
 
   for.cond.cleanup:                                 ; preds = %for.body, %entry
     ret void
 }
 
 ; YAML:      --- !Analysis
 ; YAML-NEXT: Pass:            loop-vectorize
+; YAML-NEXT: Name:            CantIdentifyArrayBounds
+; YAML-NEXT: DebugLoc:        { File: source.c, Line: 4, Column: 16 }
+; YAML-NEXT: Function:        test_unknown_bounds
+; 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.c, Line: 3, Column: 5 }
+; YAML-NEXT: Function:        test_unknown_bounds
+; YAML-NEXT: Args:
+; YAML-NEXT:   - String:          loop not vectorized
+; YAML-NEXT: ...
+; YAML:      --- !Analysis
+; YAML-NEXT: Pass:            loop-vectorize
 ; YAML-NEXT: Name:            UnsafeDep
 ; YAML-NEXT: DebugLoc:        { File: source.c, Line: 48, Column: 14 }
 ; YAML-NEXT: Function:        test_backward_dep
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - String:          'loop not vectorized: '
 ; YAML-NEXT:   - String:          'unsafe dependent memory operations in loop. Use #pragma loop distribute(enable) to allow loop distribution to attempt to isolate the offending operations into a separate loop'
 ; YAML-NEXT:   - String:          "\nBackward loop carried data dependence."
 ; YAML-NEXT:   - String:          ' Memory location is the same as accessed at '

 
 !llvm.dbg.cu = !{!0}
 !llvm.module.flags = !{!4}
 
 !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 14.0.0 (https://github.com/llvm/llvm-project.git 54f0f826c5c7d0ff16c230b259cb6aad33e18d97)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
 !1 = !DIFile(filename: "source.c", directory: "")
 !2 = !{}
 !4 = !{i32 2, !"Debug Info Version", i32 3}
+!13 = distinct !DISubprogram(name: "test_unknown_bounds", scope: !1, file: !1, line: 2, type: !45, scopeLine: 2, unit: !0, retainedNodes: !2)
+!23 = distinct !DILexicalBlock(scope: !13, file: !1, line: 3, column: 5)
+!27 = distinct !DILexicalBlock(scope: !23, file: !1, line: 3, column: 5)
+!28 = !DILocation(line: 3, column: 5, scope: !23)
+!35 = !DILocation(line: 4, column: 16, scope: !27)
 !44 = distinct !DISubprogram(name: "test_nodep", scope: !1, file: !1, line: 14, type: !45, scopeLine: 14, unit: !0, retainedNodes: !2)
 !45 = !DISubroutineType(types: !46)
 !46 = !{null, !18, !16, !16}
 !16 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !17, size: 64)
 !17 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
 !18 = !DIBasicType(name: "int", size: 64, encoding: DW_ATE_signed)
 !52 = distinct !DILexicalBlock(scope: !44, file: !1, line: 15, column: 3)
 !56 = distinct !DILexicalBlock(scope: !52, file: !1, line: 15, column: 3)