[LAA] Support pointer phis in loop by analyzing each incoming pointer.

[fhahn]

Summary

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.

This results in 2 more loops vectorized in SPEC2000/186.crafty and
avoids regressions when sinking instructions before vectorizing.

[Meinersbur]

Makes sense to me.

Pre-merge bot could not apply the patch, possibly because you diffed it against a commit that is not upstream.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

1947

[style] Don’t “almost always” use auto

2001

[style] Don’t “almost always” use auto

[fhahn]

Rebased and replaced auto with Use

In D101286#2717804, @Meinersbur wrote:

Makes sense to me.

Pre-merge bot could not apply the patch, possibly because you diffed it against a commit that is not upstream.

Yes when I uploaded the patch I did not yet commit the initial change for the tests. That should be done now in a950f66de25f :)

[uabelho]

I noticed that loop-distribute started crashing with this patch, see
https://bugs.llvm.org/show_bug.cgi?id=50288

[efriedma]

Do you need to check anything about the CFG before you just grab the PHI operand values? For example, if there's a loop, you could have a PHI that refers to another PHI in the same basic block, and I suspect that would mess up the analysis.

[fhahn]

In D101286#2747921, @uabelho wrote:

I noticed that loop-distribute started crashing with this patch, see
https://bugs.llvm.org/show_bug.cgi?id=50288

In D101286#2749037, @efriedma wrote:

Do you need to check anything about the CFG before you just grab the PHI operand values? For example, if there's a loop, you could have a PHI that refers to another PHI in the same basic block, and I suspect that would mess up the analysis.

Thanks for the report. I think the issue here is slightly different: MemoryDepChecker does not collect the memory instructions for the translated pointers (the incoming values of the phi), but LoopDistribute tries to look them up. I put up D102266 which should address this.

[efriedma]

In D101286#2751552, @fhahn wrote:

In D101286#2749037, @efriedma wrote:

Do you need to check anything about the CFG before you just grab the PHI operand values? For example, if there's a loop, you could have a PHI that refers to another PHI in the same basic block, and I suspect that would mess up the analysis.

Thanks for the report. I think the issue here is slightly different: MemoryDepChecker does not collect the memory instructions for the translated pointers (the incoming values of the phi), but LoopDistribute tries to look them up. I put up D102266 which should address this.

I wasn't commenting specifically in response to the crash report; just a general concern from reading the patch. Are you confident the issue I'm describing isn't a problem?

[fhahn]

In D101286#2751900, @efriedma wrote:

In D101286#2751552, @fhahn wrote:

In D101286#2749037, @efriedma wrote:

Do you need to check anything about the CFG before you just grab the PHI operand values? For example, if there's a loop, you could have a PHI that refers to another PHI in the same basic block, and I suspect that would mess up the analysis.

...

I wasn't commenting specifically in response to the crash report; just a general concern from reading the patch. Are you confident the issue I'm describing isn't a problem?

Oh right, sorry about that and the delay! I added such a test (phi uses another phi as incoming value in the same block as store_with_pointer_phi_in_same_bb_use_other_phi) in D102266. If the incoming value is another phi, then when won't be able to compute the bounds, due to the phi. We could traverse them further to handle more cases, but it should not be an issue for correctness IIUC. Does that make sense?

llvm/lib/Analysis/LoopAccessAnalysis.cpp

if (Seen.insert(Ptr).second) {
 
       MemoryLocation Loc = MemoryLocation::get(ST);
       // The TBAA metadata could have a control dependency on the predication
       // condition, so we cannot rely on it when determining whether or not we
       // need runtime pointer checks.
       if (blockNeedsPredication(ST->getParent(), TheLoop, DT))
         Loc.AATags.TBAA = nullptr;
 
+      // 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.
+      auto *PN = dyn_cast<PHINode>(Loc.Ptr);
+      if (PN && TheLoop->contains(PN->getParent()) &&
+          PN->getParent() != TheLoop->getHeader()) {
+        for (const Use &Inc : PN->incoming_values()) {
+          MemoryLocation NewLoc = Loc.getWithNewPtr(Inc);
+          Accesses.addStore(NewLoc);
+        }
+      } else
         Accesses.addStore(Loc);
     }
   }
 
   if (IsAnnotatedParallel) {
     LLVM_DEBUG(
         dbgs() << "LAA: A loop annotated parallel, ignore memory dependency "
                << "checks.\n");
     CanVecMem = true;
for (LoadInst *LD : Loads) {
 
     MemoryLocation Loc = MemoryLocation::get(LD);
     // The TBAA metadata could have a control dependency on the predication
     // condition, so we cannot rely on it when determining whether or not we
     // need runtime pointer checks.
     if (blockNeedsPredication(LD->getParent(), TheLoop, DT))
       Loc.AATags.TBAA = nullptr;
 
+    // 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.
+    auto *PN = dyn_cast<PHINode>(Loc.Ptr);
+    if (PN && TheLoop->contains(PN->getParent()) &&
+        PN->getParent() != TheLoop->getHeader()) {
+      for (const Use &Inc : PN->incoming_values()) {
+        MemoryLocation NewLoc = Loc.getWithNewPtr(Inc);
+        Accesses.addLoad(NewLoc, IsReadOnlyPtr);
+      }
+    } else
       Accesses.addLoad(Loc, IsReadOnlyPtr);
   }
 
   // If we write (or read-write) to a single destination and there are no
   // other reads in this loop then is it safe to vectorize.
   if (NumReadWrites == 1 && NumReads == 0) {
     LLVM_DEBUG(dbgs() << "LAA: Found a write-only loop!\n");
     CanVecMem = true;
     return;

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

 ; RUN: opt -loop-accesses -analyze -enable-new-pm=0 < %s | FileCheck %s
 ; RUN: opt -passes='require<scalar-evolution>,require<aa>,loop(print-access-info)' -disable-output  < %s 2>&1 | FileCheck %s
 
 %s1 = type { [32000 x double], [32000 x double], [32000 x double] }
 
 define i32 @load_with_pointer_phi_no_runtime_checks(%s1* %data) {
 ; CHECK-LABEL: load_with_pointer_phi_no_runtime_checks
 ; CHECK-NEXT:  loop.header:
-; CHECK-NEXT:    Report: cannot identify array bounds
+; CHECK-NEXT:    Memory dependences are safe
 ;
 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
   %cmp5 = icmp ult i64 %iv, 15999

 
 exit:                                             ; preds = %loop.latch
   ret i32 10
 }
 
 define i32 @store_with_pointer_phi_no_runtime_checks(%s1* %data) {
 ; CHECK-LABEL: 'store_with_pointer_phi_no_runtime_checks'
 ; CHECK-NEXT:  loop.header:
-; CHECK-NEXT:    Report: cannot identify array bounds
+; CHECK-NEXT:    Memory dependences are safe
 ;
 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
   %cmp5 = icmp ult i64 %iv, 15999

 
 exit:                                             ; preds = %loop.latch
   ret i32 10
 }
 
 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:    Report: cannot identify array bounds
+; 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:        %gep.1 = getelementptr inbounds double, double* %B, i64 %iv
+; CHECK-NEXT:    Check 1:
+; 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
+; CHECK-NEXT:    Check 2:
+; 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
 ;
 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
   %cmp5 = icmp ult i64 %iv, 15999

llvm/test/Transforms/LoopVectorize/vectorize-pointer-phis.ll

 ; RUN: opt -loop-vectorize -force-vector-width=2 -S %s | FileCheck %s
 
 %s1 = type { [32000 x double], [32000 x double], [32000 x double] }
 
 define i32 @load_with_pointer_phi_no_runtime_checks(%s1* %data) {
 ; CHECK-LABEL: @load_with_pointer_phi_no_runtime_checks
-; CHECK-NOT: vector.body
+; CHECK-NOT: memcheck
+; CHECK:     vector.body:
 ;
 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
   %cmp5 = icmp ult i64 %iv, 15999
loop.latch:                                          ; preds = %if.else, %if.then
   br i1 %exitcond.not, label %exit, label %loop.header
 
 exit:                                             ; preds = %loop.latch
   ret i32 10
 }
 
 define i32 @store_with_pointer_phi_no_runtime_checks(%s1* %data) {
 ; CHECK-LABEL: @store_with_pointer_phi_no_runtime_checks
-; CHECK-NOT: vector.body
+; CHECK-NOT: memcheck
+; CHECK:     vector.body
 ;
 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
   %cmp5 = icmp ult i64 %iv, 15999
loop.latch:                                          ; preds = %if.else, %if.then
   br i1 %exitcond.not, label %exit, label %loop.header
 
 exit:                                             ; preds = %loop.latch
   ret i32 10
 }
 
 define i32 @store_with_pointer_phi_runtime_checks(double* %A, double* %B, double* %C) {
 ; CHECK-LABEL: @store_with_pointer_phi_runtime_checks
-; CHECK-NOT: vector.body
+; CHECK:     memcheck
+; CHECK:     vector.body
 ;
 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
   %cmp5 = icmp ult i64 %iv, 15999