BasicAA: Recognize cyclic NoAlias phis

Enhances basic alias analysis to recognize phis whose first incoming values are
NoAlias and whose other incoming values are just the phi node itself through
some amount of recursion.

Example: With this change basicaa reports that ptr_phi and ptr_phi2 do not alias
each other.

bb:
 ptr = ptr2 + 1

loop:
  ptr_phi = phi [bb, ptr], [loop, ptr_plus_one]
  ptr2_phi = phi [bb, ptr2], [loop, ptr2_plus_one]
  ...
  ptr_plus_one = gep ptr_phi, 1
  ptr2_plus_one = gep ptr2_phi, 1

This enables the elimination of one load in code like the following:

extern int foo;

int test_noalias(int *ptr, int num, int* coeff) {
  int *ptr2 = ptr;
  int result = (*ptr++) * (*coeff--);
  while (num--) {
    *ptr2++ = *ptr;
    result +=  (*coeff--) * (*ptr++);
  }
  *ptr = foo;
  return result;
}

Part 2/2 of fix for PR13564.

llvm-svn: 163319

2 files changed, 68 insertions, 0 deletions

diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
index d537d633172..a3bc06a80f2 100644
--- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
@@ -1060,12 +1060,42 @@ BasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize,
   // on corresponding edges.
   if (const PHINode *PN2 = dyn_cast<PHINode>(V2))
     if (PN2->getParent() == PN->getParent()) {
+      LocPair Locs(Location(PN, PNSize, PNTBAAInfo),
+                   Location(V2, V2Size, V2TBAAInfo));
+      if (PN > V2)
+        std::swap(Locs.first, Locs.second);
+
       AliasResult Alias =
         aliasCheck(PN->getIncomingValue(0), PNSize, PNTBAAInfo,
                    PN2->getIncomingValueForBlock(PN->getIncomingBlock(0)),
                    V2Size, V2TBAAInfo);
       if (Alias == MayAlias)
         return MayAlias;
+
+      // If the first source of the PHI nodes NoAlias and the other inputs are
+      // the PHI node itself through some amount of recursion this does not add
+      // any new information so just return NoAlias.
+      // bb:
+      //    ptr = ptr2 + 1
+      // loop:
+      //    ptr_phi = phi [bb, ptr], [loop, ptr_plus_one]
+      //    ptr2_phi = phi [bb, ptr2], [loop, ptr2_plus_one]
+      //    ...
+      //    ptr_plus_one = gep ptr_phi, 1
+      //    ptr2_plus_one = gep ptr2_phi, 1
+      // We assume for the recursion that the the phis (ptr_phi, ptr2_phi) do
+      // not alias each other.
+      bool ArePhisAssumedNoAlias = false;
+      AliasResult OrigAliasResult;
+      if (Alias == NoAlias) {
+        // Pretend the phis do not alias.
+        assert(AliasCache.count(Locs) &&
+               "There must exist an entry for the phi node");
+        OrigAliasResult = AliasCache[Locs];
+        AliasCache[Locs] = NoAlias;
+        ArePhisAssumedNoAlias = true;
+      }
+
       for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) {
         AliasResult ThisAlias =
           aliasCheck(PN->getIncomingValue(i), PNSize, PNTBAAInfo,
@@ -1075,6 +1105,11 @@ BasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize,
         if (Alias == MayAlias)
           break;
       }
+
+      // Reset if speculation failed.
+      if (ArePhisAssumedNoAlias && Alias != NoAlias)
+        AliasCache[Locs] = OrigAliasResult;
+
       return Alias;
     }
 
diff --git a/llvm/test/Analysis/BasicAA/phi-speculation.ll b/llvm/test/Analysis/BasicAA/phi-speculation.ll
new file mode 100644
index 00000000000..21c65929862
--- /dev/null
+++ b/llvm/test/Analysis/BasicAA/phi-speculation.ll
@@ -0,0 +1,33 @@
+target datalayout =
+"e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+
+; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+; ptr_phi and ptr2_phi do not alias.
+; CHECK: NoAlias: i32* %ptr2_phi, i32* %ptr_phi
+
+define i32 @test_noalias(i32* %ptr2, i32 %count, i32* %coeff) {
+entry:
+  %ptr = getelementptr inbounds i32* %ptr2, i64 1
+  br label %while.body
+
+while.body:
+  %num = phi i32 [ %count, %entry ], [ %dec, %while.body ]
+  %ptr_phi = phi i32* [ %ptr, %entry ], [ %ptr_inc, %while.body ]
+  %ptr2_phi = phi i32* [ %ptr2, %entry ], [ %ptr2_inc, %while.body ]
+  %result.09 = phi i32 [ 0 , %entry ], [ %add, %while.body ]
+  %dec = add nsw i32 %num, -1
+  %0 = load i32* %ptr_phi, align 4
+  store i32 %0, i32* %ptr2_phi, align 4
+  %1 = load i32* %coeff, align 4
+  %2 = load i32* %ptr_phi, align 4
+  %mul = mul nsw i32 %1, %2
+  %add = add nsw i32 %mul, %result.09
+  %tobool = icmp eq i32 %dec, 0
+  %ptr_inc = getelementptr inbounds i32* %ptr_phi, i64 1
+  %ptr2_inc = getelementptr inbounds i32* %ptr2_phi, i64 1
+  br i1 %tobool, label %the_exit, label %while.body
+
+the_exit:
+  ret i32 %add
+}