[BasicAA] Fix recursive phi MustAlias calculations

[dmgreen]

Summary

With the option -basic-aa-recphi we can detect recursive phis's that loop through constant geps, which allows us to detect more no-alias case for pointer IV's. If the other phi operand and the other alias operand are MustAlias though, we cannot presume that every element in the loop is also MustAlias. We need to instead be conservative and return MayAlias.

[efriedma]

Commit message uses "NoAlias" where it means to use "MayAlias"?

llvm/test/Analysis/BasicAA/recphi.ll

8

NoAlias: float* %next, float* %src2 is actually correct; not sure how hard it would be to prove, though.

[dmgreen]

In D82987#2126204, @efriedma wrote:

Commit message uses "NoAlias" where it means to use "MayAlias"?

Whoops. Yeah. MayAlias was what it was meant to say.

llvm/test/Analysis/BasicAA/recphi.ll

8

Yep. I left this test in because it does show it's not always better. Like you said I'm not sure how to prove that though. It might start to need something like SCEVAA. (Although in this case with the noalias - maybe it could be simpler than that).

I would like to turn this option on by default and these would all be better than (or equal) to current trunk, at least.

[efriedma]

LGTM

[efriedma]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1729

Actually, do you also need to check for PartialAlias?

[dmgreen]

Now including PartialAlias too.

[efriedma]

LGTM

llvm/lib/Analysis/BasicAliasAnalysis.cpp

AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize,
 
   AliasResult Alias = aliasCheck(V2, V2Size, V2AAInfo, V1Srcs[0], PNSize,
                                  PNAAInfo, AAQI, UnderV2);
 
   // Early exit if the check of the first PHI source against V2 is MayAlias.
   // Other results are not possible.
   if (Alias == MayAlias)
     return MayAlias;
+  // With recursive phis we cannot guarantee that MustAlias will remain equal to
+  // all elements and needs to conservatively return MayAlias.
+  if (isRecursive && Alias == MustAlias)
+    return MayAlias;
 
   // If all sources of the PHI node NoAlias or MustAlias V2, then returns
   // NoAlias / MustAlias. Otherwise, returns MayAlias.
   for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) {
     Value *V = V1Srcs[i];
 
     AliasResult ThisAlias =
         aliasCheck(V2, V2Size, V2AAInfo, V, PNSize, PNAAInfo, AAQI, UnderV2);

llvm/test/Analysis/BasicAA/recphi.ll

 ; RUN: opt < %s -basic-aa -aa-eval -print-all-alias-modref-info -basic-aa-recphi -disable-output 2>&1 | FileCheck %s
 
 ; CHECK-LABEL: Function: simple: 5 pointers, 0 call sites
 ; CHECK:         NoAlias:      float* %src1, float* %src2
 ; CHECK:         NoAlias:      float* %phi, float* %src1
-; CHECK:         MustAlias:    float* %phi, float* %src2
+; CHECK:         MayAlias:     float* %phi, float* %src2
 ; CHECK:         NoAlias:      float* %next, float* %src1
-; CHECK:         NoAlias:      float* %next, float* %src2
+; CHECK:         MayAlias:     float* %next, float* %src2
 ; CHECK:         NoAlias:      float* %next, float* %phi
 ; CHECK:         NoAlias:      float* %g, float* %src1
 ; CHECK:         NoAlias:      float* %g, float* %src2
 ; CHECK:         NoAlias:      float* %g, float* %phi
 ; CHECK:         NoAlias:      float* %g, float* %next
 define void @simple(float *%src1, float * noalias %src2, i32 %n) nounwind {
 entry:
   br label %loop

 
 ; CHECK-LABEL: Function: notmust: 6 pointers, 0 call sites
 ; CHECK:        MustAlias:    [2 x i32]* %tab, i8* %0
 ; CHECK:        PartialAlias: [2 x i32]* %tab, i32* %arrayidx
 ; CHECK:        NoAlias:      i32* %arrayidx, i8* %0
 ; CHECK:        MustAlias:    [2 x i32]* %tab, i32* %arrayidx1
 ; CHECK:        MustAlias:    i32* %arrayidx1, i8* %0
 ; CHECK:        NoAlias:      i32* %arrayidx, i32* %arrayidx1
-; CHECK:        MustAlias:    [2 x i32]* %tab, i32* %p.addr.05.i
-; CHECK:        MustAlias:    i32* %p.addr.05.i, i8* %0
-; CHECK:        NoAlias:      i32* %arrayidx, i32* %p.addr.05.i
-; CHECK:        MustAlias:    i32* %arrayidx1, i32* %p.addr.05.i
-; CHECK:        PartialAlias: [2 x i32]* %tab, i32* %incdec.ptr.i
+; CHECK:        MayAlias:     [2 x i32]* %tab, i32* %p.addr.05.i
+; CHECK:        MayAlias:     i32* %p.addr.05.i, i8* %0
+; CHECK:        MayAlias:     i32* %arrayidx, i32* %p.addr.05.i
+; CHECK:        MayAlias:     i32* %arrayidx1, i32* %p.addr.05.i
+; CHECK:        MayAlias:     [2 x i32]* %tab, i32* %incdec.ptr.i
 ; CHECK:        NoAlias:      i32* %incdec.ptr.i, i8* %0
-; CHECK:        MustAlias:    i32* %arrayidx, i32* %incdec.ptr.i
+; CHECK:        MayAlias:     i32* %arrayidx, i32* %incdec.ptr.i
 ; CHECK:        NoAlias:      i32* %arrayidx1, i32* %incdec.ptr.i
 ; CHECK:        NoAlias:      i32* %incdec.ptr.i, i32* %p.addr.05.i
 define i32 @notmust() nounwind {
 entry:
   %tab = alloca [2 x i32], align 4
   %0 = bitcast [2 x i32]* %tab to i8*
   %arrayidx = getelementptr inbounds [2 x i32], [2 x i32]* %tab, i32 0, i32 1
   store i32 0, i32* %arrayidx, align 4