[BasicAA] Generalize recursive phi alias analysis

[nikic]

Summary

For recursive phis, we skip the recursive operands and check that the remaining operands are NoAlias with an unknown size. Currently, this is limited to inbounds GEPs with positive offsets, to guarantee that the recursion only ever increases the pointer.

Make this more general by only requiring that the underlying object of the phi operand is the phi itself, i.e. it it based on itself in some way. To compensate, we need to use a beforeOrAfterPointer() location size, as we no longer have the guarantee that the pointer is strictly increasing.

This allows us to handle some additional cases like negative geps, geps with dynamic offsets or geps that aren't inbounds.

[dmgreen]

Nice. Sounds good to me, from what I can remember about this, so long as others agree.

[asbirlea]

sgtm too.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

if (PN2->getParent() == PN->getParent()) {
 
       // Reset if speculation failed.
       if (Alias != NoAlias)
         AAQI.updateResult(Locs, OrigAliasResult);
       return Alias;
     }
 
   SmallVector<Value *, 4> V1Srcs;
-  // For a recursive phi, that recurses through a contant gep, we can perform
-  // aliasing calculations using the other phi operands with an unknown size to
-  // specify that an unknown number of elements after the initial value are
-  // potentially accessed.
+  // If a phi operand recurses back to the phi, we can still determine NoAlias
+  // if we don't alias the underlying objects of the other phi operands, as we
+  // know that the recursive phi needs to be based on them in some way.
   bool isRecursive = false;
   auto CheckForRecPhi = [&](Value *PV) {
     if (!EnableRecPhiAnalysis)
       return false;
-    if (GEPOperator *PVGEP = dyn_cast<GEPOperator>(PV)) {
-      // Check whether the incoming value is a GEP that advances the pointer
-      // result of this PHI node (e.g. in a loop). If this is the case, we
-      // would recurse and always get a MayAlias. Handle this case specially
-      // below. We need to ensure that the phi is inbounds and has a constant
-      // positive operand so that we can check for alias with the initial value
-      // and an unknown but positive size.
-      if (PVGEP->getPointerOperand() == PN && PVGEP->isInBounds() &&
-          PVGEP->getNumIndices() == 1 && isa<ConstantInt>(PVGEP->idx_begin()) &&
-          !cast<ConstantInt>(PVGEP->idx_begin())->isNegative()) {
-        isRecursive = true;
-        return true;
-      }
-    }
+    if (getUnderlyingObject(PV) == PN) {
     return false;
   };
 
   if (PV) {
     // If we have PhiValues then use it to get the underlying phi values.
     const PhiValues::ValueSet &PhiValueSet = PV->getValuesForPhi(PN);
     // If we have more phi values than the search depth then return MayAlias
     // conservatively to avoid compile time explosion. The worst possible case
AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize,
   }
 
   // If V1Srcs is empty then that means that the phi has no underlying non-phi
   // value. This should only be possible in blocks unreachable from the entry
   // block, but return MayAlias just in case.
   if (V1Srcs.empty())
     return MayAlias;
 
-  // If this PHI node is recursive, set the size of the accessed memory to
-  // unknown to represent all the possible values the GEP could advance the
-  // pointer to.
+  // If this PHI node is recursive, indicate that the pointer may be moved
+  // across iterations. We can only prove NoAlias if different underlying
+  // objects are involved.
   if (isRecursive)
-    // TODO: We are checking above that the addrec GEP has a positive offset
-    // and can thus assume that all accesses happen after the base pointer.
-    // It might be better to drop the offset requirement and use
-    // beforeOrAfterPointer().
-    PNSize = LocationSize::afterPointer();
+    PNSize = LocationSize::beforeOrAfterPointer();
 
   // In the recursive alias queries below, we may compare values from two
   // different loop iterations. Keep track of visited phi blocks, which will
   // be used when determining value equivalence.
   bool BlockInserted = VisitedPhiBBs.insert(PN->getParent()).second;
   auto _ = make_scope_exit([&]() {
     if (BlockInserted)
       VisitedPhiBBs.erase(PN->getParent());

llvm/test/Analysis/BasicAA/recphi.ll

 if.end: ; preds = %f.exit
   ret i32 0
 }
 
 ; CHECK-LABEL: Function: negative: 6 pointers, 1 call sites
 ; CHECK:         NoAlias:      [3 x i16]* %int_arr.10, i16** %argv.6.par
 ; CHECK:         NoAlias:      i16* %_tmp1, i16** %argv.6.par
 ; CHECK:         PartialAlias: [3 x i16]* %int_arr.10, i16* %_tmp1
-; CHECK:         MayAlias:     i16* %ls1.9.0, i16** %argv.6.par
+; CHECK:         NoAlias:      i16* %ls1.9.0, i16** %argv.6.par
 ; CHECK:         MayAlias:     [3 x i16]* %int_arr.10, i16* %ls1.9.0
 ; CHECK:         MayAlias:     i16* %_tmp1, i16* %ls1.9.0
-; CHECK:         MayAlias:     i16* %_tmp7, i16** %argv.6.par
+; CHECK:         NoAlias:      i16* %_tmp7, i16** %argv.6.par
 ; CHECK:         MayAlias:     [3 x i16]* %int_arr.10, i16* %_tmp7
 ; CHECK:         MayAlias:     i16* %_tmp1, i16* %_tmp7
 ; CHECK:         NoAlias:      i16* %_tmp7, i16* %ls1.9.0
 ; CHECK:         NoAlias:      i16* %_tmp11, i16** %argv.6.par
 ; CHECK:         PartialAlias: [3 x i16]* %int_arr.10, i16* %_tmp11
 ; CHECK:         NoAlias:      i16* %_tmp1, i16* %_tmp11
 ; CHECK:         MayAlias:     i16* %_tmp11, i16* %ls1.9.0
 ; CHECK:         MayAlias:     i16* %_tmp11, i16* %_tmp7

 
 bb5:                                              ; preds = %bb3, %bb4
   ret i16 0
 }
 
 ; CHECK-LABEL: Function: dynamic_offset
 ; CHECK: NoAlias:  i8* %a, i8* %p.base
 ; CHECK: MayAlias: i8* %p, i8* %p.base
-; CHECK: MayAlias: i8* %a, i8* %p
+; CHECK: NoAlias:  i8* %a, i8* %p
 ; CHECK: MayAlias: i8* %p.base, i8* %p.next
-; CHECK: MayAlias: i8* %a, i8* %p.next
+; CHECK: NoAlias:  i8* %a, i8* %p.next
 ; CHECK: MayAlias: i8* %p, i8* %p.next
 define void @dynamic_offset(i1 %c, i8* noalias %p.base) {
 entry:
   %a = alloca i8
   br label %loop
 
 loop:
   %p = phi i8* [ %p.base, %entry ], [ %p.next, %loop ]

llvm/test/CodeGen/Thumb2/mve-float32regloops.ll

 ; CHECK-NEXT:    vdup.32 q2, r6
 ; CHECK-NEXT:    vmov.f32 s10, s12
 ; CHECK-NEXT:    mov r7, r2
 ; CHECK-NEXT:    vmov.f32 s11, s12
 ; CHECK-NEXT:  .LBB17_3: @ Parent Loop BB17_2 Depth=1
 ; CHECK-NEXT:    @ => This Inner Loop Header: Depth=2
 ; CHECK-NEXT:    vldrw.u32 q4, [r1, q0, uxtw #2]
 ; CHECK-NEXT:    vldrw.u32 q5, [r4, q0, uxtw #2]
+; CHECK-NEXT:    vldrw.u32 q3, [sp, #8]
 ; CHECK-NEXT:    adds r1, #8
 ; CHECK-NEXT:    vfma.f32 q5, q4, r5
+; CHECK-NEXT:    vfma.f32 q3, q5, q2
 ; CHECK-NEXT:    vstmia r7, {s20, s21}
 ; CHECK-NEXT:    adds r7, #8
-; CHECK-NEXT:    vldrw.u32 q3, [sp, #8]
-; CHECK-NEXT:    vfma.f32 q3, q5, q2
 ; CHECK-NEXT:    vfma.f32 q3, q4, q1
 ; CHECK-NEXT:    vstrw.32 q3, [r4]
 ; CHECK-NEXT:    le lr, .LBB17_3
 ; CHECK-NEXT:  @ %bb.4: @ in Loop: Header=BB17_2 Depth=1
 ; CHECK-NEXT:    subs.w r12, r12, #1
 ; CHECK-NEXT:    add.w r0, r0, #20
 ; CHECK-NEXT:    vstrb.8 q3, [r3], #16
 ; CHECK-NEXT:    mov r1, r2