[LAA] Iteratively traverse pointer phis.

[fhahn]

Summary

Follow-up to D102266 to iteratively traverse pointer phis.

[Meinersbur]

After having been merged folded into D102266, can this be abandoned?

[fhahn]

In D109381#2997249, @Meinersbur wrote:

After having been merged folded into D102266, can this be abandoned?

Yes! Abandoning.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

bool llvm::isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
   Type *ElemTyB = getLoadStoreType(B);
   Optional<int> Diff = getPointersDiff(ElemTyA, PtrA, ElemTyB, PtrB, DL, SE,
                                        /*StrictCheck=*/true, CheckType);
   return Diff && *Diff == 1;
 }
 
 static void visitPointers(Value *StartPtr, const Loop &InnermostLoop,
                           function_ref<void(Value *)> AddPointer) {
-  auto *PN = dyn_cast<PHINode>(StartPtr);
+  SmallVector<Value *> WorkList;
+  WorkList.push_back(StartPtr);
+
+  while (!WorkList.empty()) {
+    Value *Ptr = WorkList.pop_back_val();
+    auto *PN = dyn_cast<PHINode>(Ptr);
     // SCEV does not look through non-header PHIs inside the loop. Such phis
     // can be analyzed by adding separate accesses for each incoming pointer
     // value.
     if (PN && InnermostLoop.contains(PN->getParent()) &&
         PN->getParent() != InnermostLoop.getHeader()) {
       for (const Use &Inc : PN->incoming_values())
-      AddPointer(Inc);
+        WorkList.push_back(Inc);
     } else
-    AddPointer(StartPtr);
+      AddPointer(Ptr);
+  }
 }
 
 void MemoryDepChecker::addAccess(StoreInst *SI) {
   visitPointers(SI->getPointerOperand(), *InnermostLoop,
                 [this, SI](Value *Ptr) {
                   Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx);
                   InstMap.push_back(SI);
                   ++AccessIdx;

llvm/test/Analysis/LoopAccessAnalysis/pointer-phis.ll

 }
 
 define i32 @store_with_pointer_phi_runtime_checks(double* %A, double* %B, double* %C) {
 ; CHECK-LABEL: 'store_with_pointer_phi_runtime_checks'
 ; CHECK-NEXT:  loop.header:
 ; CHECK-NEXT:    Memory dependences are safe with run-time checks
 ; CHECK:         Run-time memory checks:
 ; CHECK-NEXT:    Check 0:
-; CHECK-NEXT:      Comparing group ([[GROUP_C:.+]]):
-; CHECK-NEXT:        %gep.2 = getelementptr inbounds double, double* %C, i64 %iv
-; CHECK-NEXT:      Against group ([[GROUP_B:.+]]):
+; CHECK-NEXT:      Comparing group ([[GROUP_B:.+]]):
 ; CHECK-NEXT:        %gep.1 = getelementptr inbounds double, double* %B, i64 %iv
-; CHECK-NEXT:    Check 1:
-; CHECK-NEXT:      Comparing group ([[GROUP_C]]):
+; CHECK-NEXT:      Against group ([[GROUP_C:.+]]):
 ; CHECK-NEXT:        %gep.2 = getelementptr inbounds double, double* %C, i64 %iv
+; CHECK-NEXT:    Check 1:
+; CHECK-NEXT:      Comparing group ([[GROUP_B]]):
+; CHECK-NEXT:        %gep.1 = getelementptr inbounds double, double* %B, i64 %iv
 ; CHECK-NEXT:      Against group ([[GROUP_A:.+]]):
 ; CHECK-NEXT:        %arrayidx = getelementptr inbounds double, double* %A, i64 %iv
 ; CHECK-NEXT:    Check 2:
-; CHECK-NEXT:      Comparing group ([[GROUP_B]]):
-; CHECK-NEXT:        %gep.1 = getelementptr inbounds double, double* %B, i64 %iv
+; CHECK-NEXT:      Comparing group ([[GROUP_C]]):
+; CHECK-NEXT:        %gep.2 = getelementptr inbounds double, double* %C, i64 %iv
 ; CHECK-NEXT:      Against group ([[GROUP_A]]):
 ; CHECK-NEXT:        %arrayidx = getelementptr inbounds double, double* %A, i64 %iv
 ;
 entry:
   br label %loop.header
 
 loop.header:                                        ; preds = %loop.latch, %entry
   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]

 
 exit:                                             ; preds = %loop.latch
   ret i32 10
 }
 
 define i32 @store_with_pointer_phi_incoming_phi(double* %A, double* %B, double* %C, i1 %c.0, i1 %c.1) {
 ; CHECK-LABEL: 'store_with_pointer_phi_incoming_phi'
 ; CHECK-NEXT:  loop.header:
-; CHECK-NEXT:    Report: cannot identify array bounds
+; CHECK-NEXT:    Report: 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
 ; CHECK-NEXT:    Dependences:
+; CHECK-NEXT:      Unknown:
+; CHECK-NEXT:          %v8 = load double, double* %arrayidx, align 8 ->
+; CHECK-NEXT:          store double %mul16, double* %ptr.2, align 8
+; CHECK-EMPTY:
 ; CHECK-NEXT:    Run-time memory checks:
+; CHECK-NEXT:    Check 0:
+; CHECK-NEXT:      Comparing group ([[GROUP_C:.+]]):
+; CHECK-NEXT:      double* %C
+; CHECK-NEXT:      Against group ([[GROUP_B:.+]]):
+; CHECK-NEXT:      double* %B
+; CHECK-NEXT:    Check 1:
+; CHECK-NEXT:      Comparing group ([[GROUP_C]]):
+; CHECK-NEXT:      double* %C
+; CHECK-NEXT:      Against group ([[GROUP_A:.+]]):
+; CHECK-NEXT:        %arrayidx = getelementptr inbounds double, double* %A, i64 %iv
+; CHECK-NEXT:      double* %A
+; CHECK-NEXT:    Check 2:
+; CHECK-NEXT:      Comparing group ([[GROUP_B]]):
+; CHECK-NEXT:      double* %B
+; CHECK-NEXT:      Against group ([[GROUP_A]]):
+; CHECK-NEXT:        %arrayidx = getelementptr inbounds double, double* %A, i64 %iv
+; CHECK-NEXT:      double* %A
 ; CHECK-NEXT:    Grouped accesses:
-; CHECK-EMPTY:
-; CHECK-NEXT:    Non vectorizable stores to invariant address were not found in loop.
-;
+; CHECK-NEXT:      Group [[GROUP_C]]:
+; CHECK-NEXT:        (Low: %C High: (8 + %C))
+; CHECK-NEXT:          Member: %C
+; CHECK-NEXT:      Group [[GROUP_B]]:
+; CHECK-NEXT:        (Low: %B High: (8 + %B))
+; CHECK-NEXT:          Member: %B
+; CHECK-NEXT:      Group [[GROUP_A]]:
+; CHECK-NEXT:        (Low: %A High: (256000 + %A))
+; CHECK-NEXT:          Member: {%A,+,8}<nuw><%loop.header>
+; CHECK-NEXT:          Member: %A
+; CHECK-EMPTY
 entry:
   br label %loop.header
 
 loop.header:                                        ; preds = %loop.latch, %entry
   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
   %iv.next = add nuw nsw i64 %iv, 1
   %arrayidx = getelementptr inbounds double, double* %A, i64 %iv
   %v8 = load double, double* %arrayidx, align 8
loop.header:                                        ; preds = %loop.latch, %entry
   store double %mul16, double* %ptr, align 8
   %exitcond.not = icmp eq i64 %iv.next, 32000
   br i1 %exitcond.not, label %exit, label %loop.header
 
 exit:                                             ; preds = %loop.latch
   ret i32 10
 }
 
+
+
 define i32 @store_with_pointer_phi_in_same_bb_use_other_phi(double* %A, double* %B, double* %C, double* %D, i1 %c.0, i1 %c.1) {
 ; CHECK-LABEL: Loop access info in function 'store_with_pointer_phi_in_same_bb_use_other_phi':
 ; CHECK-NEXT:   loop.header:
 ; CHECK-NEXT:     Report: cannot identify array bounds
 ; CHECK-NEXT:     Dependences:
 ; CHECK-NEXT:     Run-time memory checks:
 ; CHECK-NEXT:     Grouped accesses:
 ; CHECK-EMPTY:

 ; CHECK-NEXT:          store i16 %lv, i16* %A, align 1
 ; CHECK-EMPTY:
 ; CHECK-NEXT:      Unknown:
 ; CHECK-NEXT:          store i16 %lv, i16* %A, align 1 ->
 ; CHECK-NEXT:          %lv2 = load i16, i16* %A, align 1
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Run-time memory checks:
 ; CHECK-NEXT:    Check 0:
-; CHECK-NEXT:      Comparing group ([[GROUP_A:.*]]):
+; CHECK-NEXT:      Comparing group ([[GROUP_A:.+]]):
 ; CHECK-NEXT:      i16* %A
 ; CHECK-NEXT:      i16* %A
-; CHECK-NEXT:      Against group ([[GROUP_B:.*]]):
-; CHECK-NEXT:      i16* %B
-; CHECK-NEXT:      i16* %B
+; CHECK-NEXT:      Against group ([[GROUP_C:.+]]):
+; CHECK-NEXT:      i16* %C
+; CHECK-NEXT:      i16* %C
 ; CHECK-NEXT:    Check 1:
 ; CHECK-NEXT:      Comparing group ([[GROUP_A]]):
 ; CHECK-NEXT:      i16* %A
 ; CHECK-NEXT:      i16* %A
-; CHECK-NEXT:      Against group ([[GROUP_C:.*]]):
-; CHECK-NEXT:      i16* %C
-; CHECK-NEXT:      i16* %C
-; CHECK-NEXT:    Check 2:
-; CHECK-NEXT:      Comparing group ([[GROUP_B]]):
+; CHECK-NEXT:      Against group ([[GROUP_B:.+]]):
 ; CHECK-NEXT:      i16* %B
 ; CHECK-NEXT:      i16* %B
-; CHECK-NEXT:      Against group ([[GROUP_C]]):
+; CHECK-NEXT:    Check 2:
+; CHECK-NEXT:      Comparing group ([[GROUP_C]]):
 ; CHECK-NEXT:      i16* %C
 ; CHECK-NEXT:      i16* %C
+; CHECK-NEXT:      Against group ([[GROUP_B]]):
+; CHECK-NEXT:      i16* %B
+; CHECK-NEXT:      i16* %B
 ; CHECK-NEXT:    Grouped accesses:
 ; CHECK-NEXT:      Group [[GROUP_A]]
 ; CHECK-NEXT:        (Low: %A High: (2 + %A))
 ; CHECK-NEXT:          Member: %A
 ; CHECK-NEXT:          Member: %A
-; CHECK-NEXT:      Group [[GROUP_B]]
-; CHECK-NEXT:        (Low: %B High: (2 + %B))
-; CHECK-NEXT:          Member: %B
-; CHECK-NEXT:          Member: %B
 ; CHECK-NEXT:      Group [[GROUP_C]]
 ; CHECK-NEXT:        (Low: %C High: (2 + %C))
 ; CHECK-NEXT:          Member: %C
 ; CHECK-NEXT:          Member: %C
+; CHECK-NEXT:      Group [[GROUP_B]]
+; CHECK-NEXT:        (Low: %B High: (2 + %B))
+; CHECK-NEXT:          Member: %B
+; CHECK-NEXT:          Member: %B
 ; CHECK-EMPTY:
 ;
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %if.end, %entry
   %iv = phi i16 [ 0, %entry ], [ %iv.next, %if.end ]
   %lv = load i16, i16* %A, align 1