Teach basic AA about PHI nodes. If all operands of a phi NoAlias another value than it's safe to declare the PHI NoAlias the value. Ditto for MustAlias.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@84038 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 155 insertions, 12 deletions

diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp
index 900a5b61ee..75fd0e8f22 100644
--- a/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/lib/Analysis/BasicAliasAnalysis.cpp
@@ -27,6 +27,7 @@
 #include "llvm/Operator.h"
 #include "llvm/Pass.h"
 #include "llvm/Target/TargetData.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Compiler.h"
@@ -201,7 +202,10 @@ namespace {
     static char ID; // Class identification, replacement for typeinfo
     BasicAliasAnalysis() : NoAA(&ID) {}
     AliasResult alias(const Value *V1, unsigned V1Size,
-                      const Value *V2, unsigned V2Size);
+                      const Value *V2, unsigned V2Size) {
+      SmallSet<const Value*, 16> VisitedPHIs;
+      return aliasCheck(V1, V1Size, V2, V2Size, VisitedPHIs);
+    }
 
     ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
     ModRefResult getModRefInfo(CallSite CS1, CallSite CS2);
@@ -218,7 +222,16 @@ namespace {
     // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction
     // against another.
     AliasResult aliasGEP(const Value *V1, unsigned V1Size,
-                         const Value *V2, unsigned V2Size);
+                         const Value *V2, unsigned V2Size,
+                         SmallSet<const Value*, 16> &VisitedPHIs);
+
+    AliasResult aliasPHI(const Value *V1, unsigned V1Size,
+                         const Value *V2, unsigned V2Size,
+                         SmallSet<const Value*, 16> &VisitedPHIs);
+
+    AliasResult aliasCheck(const Value *V1, unsigned V1Size,
+                           const Value *V2, unsigned V2Size,
+                           SmallSet<const Value*, 16> &VisitedPHIs);
 
     // CheckGEPInstructions - Check two GEP instructions with known
     // must-aliasing base pointers.  This checks to see if the index expressions
@@ -339,7 +352,8 @@ BasicAliasAnalysis::getModRefInfo(CallSite CS1, CallSite CS2) {
 //
 AliasAnalysis::AliasResult
 BasicAliasAnalysis::aliasGEP(const Value *V1, unsigned V1Size,
-                             const Value *V2, unsigned V2Size) {
+                             const Value *V2, unsigned V2Size,
+                             SmallSet<const Value*, 16> &VisitedPHIs) {
   // If we have two gep instructions with must-alias'ing base pointers, figure
   // out if the indexes to the GEP tell us anything about the derived pointer.
   // Note that we also handle chains of getelementptr instructions as well as
@@ -359,8 +373,8 @@ BasicAliasAnalysis::aliasGEP(const Value *V1, unsigned V1Size,
         GEP1->getOperand(0)->getType() == GEP2->getOperand(0)->getType() &&
         // All operands are the same, ignoring the base.
         std::equal(GEP1->op_begin()+1, GEP1->op_end(), GEP2->op_begin()+1))
-      return alias(GEP1->getOperand(0), V1Size, GEP2->getOperand(0), V2Size);
-    
+      return aliasCheck(GEP1->getOperand(0), V1Size,
+                        GEP2->getOperand(0), V2Size, VisitedPHIs);
     
     // Drill down into the first non-gep value, to test for must-aliasing of
     // the base pointers.
@@ -377,7 +391,8 @@ BasicAliasAnalysis::aliasGEP(const Value *V1, unsigned V1Size,
     const Value *BasePtr2 = GEP2->getOperand(0);
 
     // Do the base pointers alias?
-    AliasResult BaseAlias = alias(BasePtr1, ~0U, BasePtr2, ~0U);
+    AliasResult BaseAlias = aliasCheck(BasePtr1, ~0U, BasePtr2, ~0U,
+                                       VisitedPHIs);
     if (BaseAlias == NoAlias) return NoAlias;
     if (BaseAlias == MustAlias) {
       // If the base pointers alias each other exactly, check to see if we can
@@ -413,7 +428,7 @@ BasicAliasAnalysis::aliasGEP(const Value *V1, unsigned V1Size,
   SmallVector<Value*, 16> GEPOperands;
   const Value *BasePtr = GetGEPOperands(V1, GEPOperands);
 
-  AliasResult R = alias(BasePtr, V1Size, V2, V2Size);
+  AliasResult R = aliasCheck(BasePtr, V1Size, V2, V2Size, VisitedPHIs);
   if (R == MustAlias) {
     // If there is at least one non-zero constant index, we know they cannot
     // alias.
@@ -462,12 +477,47 @@ BasicAliasAnalysis::aliasGEP(const Value *V1, unsigned V1Size,
   return MayAlias;
 }
 
-// alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such
-// as array references.
+AliasAnalysis::AliasResult
+BasicAliasAnalysis::aliasPHI(const Value *V1, unsigned V1Size,
+                             const Value *V2, unsigned V2Size,
+                             SmallSet<const Value*, 16> &VisitedPHIs) {
+  // The PHI node has already been visited, avoid recursion any further.
+  if (!VisitedPHIs.insert(V1))
+    return MayAlias;
+
+  SmallSet<Value*, 4> UniqueSrc;
+  SmallVector<Value*, 4> V1Srcs;
+  const PHINode *PN = cast<PHINode>(V1);
+  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
+    Value *PV1 = PN->getIncomingValue(i);
+    if (isa<PHINode>(PV1))
+      // If any of the source itself is a PHI, return MayAlias conservatively
+      // to avoid compile time explosion.
+      return MayAlias;
+    if (UniqueSrc.insert(PV1))
+      V1Srcs.push_back(PV1);
+  }
+
+  // If all sources of the PHI node NoAlias or MustAlias V2, then returns
+  // NoAlias / MustAlias. Otherwise, returns MayAlias.
+  AliasResult Alias = aliasCheck(V1Srcs[0], V1Size, V2, V2Size, VisitedPHIs);
+  for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) {
+    Value *V = V1Srcs[i];
+    AliasResult ThisAlias = aliasCheck(V, V1Size, V2, V2Size, VisitedPHIs);
+    if (ThisAlias != Alias)
+      return MayAlias;
+  }
+
+  return Alias;
+}
+
+// aliasCheck - Provide a bunch of ad-hoc rules to disambiguate in common cases,
+// such as array references.
 //
 AliasAnalysis::AliasResult
-BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
-                          const Value *V2, unsigned V2Size) {
+BasicAliasAnalysis::aliasCheck(const Value *V1, unsigned V1Size,
+                               const Value *V2, unsigned V2Size,
+                               SmallSet<const Value*, 16> &VisitedPHIs) {
   // Strip off any casts if they exist.
   V1 = V1->stripPointerCasts();
   V2 = V2->stripPointerCasts();
@@ -521,7 +571,14 @@ BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
     std::swap(V1Size, V2Size);
   }
   if (isGEP(V1))
-    return aliasGEP(V1, V1Size, V2, V2Size);
+    return aliasGEP(V1, V1Size, V2, V2Size, VisitedPHIs);
+
+  if (isa<PHINode>(V2) && !isa<PHINode>(V1)) {
+    std::swap(V1, V2);
+    std::swap(V1Size, V2Size);
+  }
+  if (isa<PHINode>(V1))
+    return aliasPHI(V1, V1Size, V2, V2Size, VisitedPHIs);
 
   return MayAlias;
 }
diff --git a/test/Analysis/BasicAA/phi-aa.ll b/test/Analysis/BasicAA/phi-aa.ll
new file mode 100644
index 0000000000..a3e89e963c
--- /dev/null
+++ b/test/Analysis/BasicAA/phi-aa.ll
@@ -0,0 +1,86 @@
+; RUN: opt < %s -basicaa -licm -S | FileCheck %s
+; rdar://7282591
+
+%struct.CFRuntimeBase = type { i32, [4 x i8] }
+%struct.XXXAffineTransform = type { float, float, float, float, float, float }
+%struct.XXXContext = type { %struct.CFRuntimeBase, i32, i32, i32, i8*, %struct.XXXContextDelegate*, void (%struct.XXXContext*)*, void (%struct.XXXContext*)*, %struct.XXXImage* (%struct.XXXContext*, %struct.XXXRect*, %struct.XXXImage*, i8*)*, i8*, %struct.__CFDictionary*, i32, %struct.XXXGState*, %struct.XXXGStack*, %struct.XXXRenderingState*, %struct.XXXAffineTransform, %struct.XXXPath*, %struct.__CFDictionary*, %struct.XXXPixelAccess* }
+%struct.XXXContextDelegate = type opaque
+%struct.XXXGStack = type opaque
+%struct.XXXGState = type opaque
+%struct.XXXImage = type opaque
+%struct.XXXPath = type opaque
+%struct.XXXPixelAccess = type opaque
+%struct.XXXPoint = type { float, float }
+%struct.XXXRect = type { %struct.XXXPoint, %struct.XXXPoint }
+%struct.XXXRenderingState = type opaque
+%struct.__CFDictionary = type opaque
+
+define void @t(%struct.XXXContext* %context, i16* %glyphs, %struct.XXXPoint* %advances, i32 %count) nounwind optsize ssp {
+; CHECK: @t
+; CHECK: bb21.preheader:
+; CHECK: %tmp28 = getelementptr
+; CHECK: %tmp28.promoted = load
+entry:
+  br i1 undef, label %bb1, label %bb
+
+bb:                                               ; preds = %entry
+  br i1 undef, label %bb2, label %bb1
+
+bb1:                                              ; preds = %bb, %entry
+  ret void
+
+bb2:                                              ; preds = %bb
+  br i1 undef, label %bb35, label %bb7
+
+bb7:                                              ; preds = %bb2
+  br i1 undef, label %bb35, label %bb10
+
+bb10:                                             ; preds = %bb7
+  %tmp18 = alloca i8, i32 undef, align 1          ; <i8*> [#uses=1]
+  br i1 undef, label %bb35, label %bb15
+
+bb15:                                             ; preds = %bb10
+  br i1 undef, label %bb17, label %bb16
+
+bb16:                                             ; preds = %bb15
+  %tmp21 = bitcast i8* %tmp18 to %struct.XXXPoint* ; <%struct.XXXPoint*> [#uses=1]
+  br label %bb18
+
+bb17:                                             ; preds = %bb15
+  %tmp22 = malloc %struct.XXXPoint, i32 %count     ; <%struct.XXXPoint*> [#uses=1]
+  br label %bb18
+
+bb18:                                             ; preds = %bb17, %bb16
+  %positions.0 = phi %struct.XXXPoint* [ %tmp21, %bb16 ], [ %tmp22, %bb17 ] ; <%struct.XXXPoint*> [#uses=1]
+  br i1 undef, label %bb35, label %bb20
+
+bb20:                                             ; preds = %bb18
+  br i1 undef, label %bb21, label %bb25
+
+bb21:                                             ; preds = %bb21, %bb20
+  %tmp28 = getelementptr inbounds %struct.XXXPoint* %positions.0, i32 undef, i32 0 ; <float*> [#uses=1]
+  store float undef, float* %tmp28, align 4
+  %elt22 = getelementptr inbounds %struct.XXXPoint* %advances, i32 undef, i32 1 ; <float*> [#uses=1]
+  %val23 = load float* %elt22                     ; <float> [#uses=0]
+  br i1 undef, label %bb21, label %bb25
+
+bb25:                                             ; preds = %bb21, %bb20
+  switch i32 undef, label %bb26 [
+    i32 4, label %bb27
+    i32 5, label %bb27
+    i32 6, label %bb27
+    i32 7, label %bb28
+  ]
+
+bb26:                                             ; preds = %bb25
+  unreachable
+
+bb27:                                             ; preds = %bb25, %bb25, %bb25
+  unreachable
+
+bb28:                                             ; preds = %bb25
+  unreachable
+
+bb35:                                             ; preds = %bb18, %bb10, %bb7, %bb2
+  ret void
+}