Avoid duplicating loop header which leads to unnatural loops (and just seem like...

[oota-llvm.git] / lib / Analysis / BasicAliasAnalysis.cpp

diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp
index be8fe07f2c97c245c5c8a79ab6b6e7f671d62477..599a6f650fd3da4afa5ba3e31c094e6c3554ae0c 100644 (file)
--- a/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/lib/Analysis/BasicAliasAnalysis.cpp
@@ -21,7 +21,7 @@
 #include "llvm/ParameterAttributes.h"
 #include "llvm/GlobalVariable.h"
 #include "llvm/Instructions.h"
-#include "llvm/Intrinsics.h"
+#include "llvm/IntrinsicInst.h"
 #include "llvm/Pass.h"
 #include "llvm/Target/TargetData.h"
 #include "llvm/ADT/SmallVector.h"
@@ -79,15 +79,15 @@ namespace {
     virtual void deleteValue(Value *V) {}
     virtual void copyValue(Value *From, Value *To) {}
   };
+}  // End of anonymous namespace
 
-  // Register this pass...
-  char NoAA::ID = 0;
-  RegisterPass<NoAA>
-  U("no-aa", "No Alias Analysis (always returns 'may' alias)");
+// Register this pass...
+char NoAA::ID = 0;
+static RegisterPass<NoAA>
+U("no-aa", "No Alias Analysis (always returns 'may' alias)", true, true);
 
-  // Declare that we implement the AliasAnalysis interface
-  RegisterAnalysisGroup<AliasAnalysis> V(U);
-}  // End of anonymous namespace
+// Declare that we implement the AliasAnalysis interface
+static RegisterAnalysisGroup<AliasAnalysis> V(U);
 
 ImmutablePass *llvm::createNoAAPass() { return new NoAA(); }
 
@@ -124,15 +124,15 @@ namespace {
                          const Type *BasePtr2Ty,
                          Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2Size);
   };
+}  // End of anonymous namespace
 
-  // Register this pass...
-  char BasicAliasAnalysis::ID = 0;
-  RegisterPass<BasicAliasAnalysis>
-  X("basicaa", "Basic Alias Analysis (default AA impl)");
+// Register this pass...
+char BasicAliasAnalysis::ID = 0;
+static RegisterPass<BasicAliasAnalysis>
+X("basicaa", "Basic Alias Analysis (default AA impl)", false, true);
 
-  // Declare that we implement the AliasAnalysis interface
-  RegisterAnalysisGroup<AliasAnalysis, true> Y(X);
-}  // End of anonymous namespace
+// Declare that we implement the AliasAnalysis interface
+static RegisterAnalysisGroup<AliasAnalysis, true> Y(X);
 
 ImmutablePass *llvm::createBasicAliasAnalysisPass() {
   return new BasicAliasAnalysis();
@@ -219,8 +219,6 @@ static bool AddressMightEscape(const Value *V) {
         return true;
       break; // next use.
     case Instruction::BitCast:
-      if (!isa<PointerType>(I->getType()))
-        return true;
       if (AddressMightEscape(I))
         return true;
       break; // next use
@@ -228,6 +226,12 @@ static bool AddressMightEscape(const Value *V) {
       // If returned, the address will escape to calling functions, but no
       // callees could modify it.
       break; // next use
+    case Instruction::Call:
+      // If the call is to a few known safe intrinsics, we know that it does
+      // not escape
+      if (!isa<MemIntrinsic>(I))
+        return true;
+      break;  // next use
     default:
       return true;
     }
@@ -246,19 +250,36 @@ BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
     const Value *Object = getUnderlyingObject(P);
     // Allocations and byval arguments are "new" objects.
     if (Object &&
-        (isa<AllocationInst>(Object) ||
-         (isa<Argument>(Object) && cast<Argument>(Object)->hasByValAttr()))) {
-      // Okay, the pointer is to a stack allocated object.  If we can prove that
-      // the pointer never "escapes", then we know the call cannot clobber it,
-      // because it simply can't get its address.
-      if (!AddressMightEscape(Object))
-        return NoModRef;
+        (isa<AllocationInst>(Object) || isa<Argument>(Object))) {
+      // Okay, the pointer is to a stack allocated (or effectively so, for 
+      // for noalias parameters) object.  If the address of this object doesn't
+      // escape from this function body to a callee, then we know that no
+      // callees can mod/ref it unless they are actually passed it.
+      if (isa<AllocationInst>(Object) ||
+          cast<Argument>(Object)->hasByValAttr() ||
+          cast<Argument>(Object)->hasNoAliasAttr())
+        if (!AddressMightEscape(Object)) {
+          bool passedAsArg = false;
+          for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
+              CI != CE; ++CI)
+            if (isa<PointerType>((*CI)->getType()) &&
+                ( getUnderlyingObject(*CI) == P ||
+                  alias(cast<Value>(CI), ~0U, P, ~0U) != NoAlias) )
+              passedAsArg = true;
+          
+          if (!passedAsArg)
+            return NoModRef;
+        }
 
       // If this is a tail call and P points to a stack location, we know that
       // the tail call cannot access or modify the local stack.
-      if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction()))
-        if (CI->isTailCall() && !isa<MallocInst>(Object))
-          return NoModRef;
+      // We cannot exclude byval arguments here; these belong to the caller of
+      // the current function not to the current function, and a tail callee
+      // may reference them.
+      if (isa<AllocaInst>(Object))
+        if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction()))
+          if (CI->isTailCall())
+            return NoModRef;
     }
   }
 
@@ -666,7 +687,7 @@ BasicAliasAnalysis::CheckGEPInstructions(
         if (isa<ConstantInt>(GEP1Ops[i]) && 
             !cast<ConstantInt>(GEP1Ops[i])->isZero()) {
           // Yup, there's a constant in the tail.  Set all variables to
-          // constants in the GEP instruction to make it suiteable for
+          // constants in the GEP instruction to make it suitable for
           // TargetData::getIndexedOffset.
           for (i = 0; i != MaxOperands; ++i)
             if (!isa<ConstantInt>(GEP1Ops[i]))
@@ -681,9 +702,15 @@ BasicAliasAnalysis::CheckGEPInstructions(
           int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops,
                                                 MinOperands);
 
+          // Make sure we compare the absolute difference.
+          if (Offset1 > Offset2)
+            std::swap(Offset1, Offset2);
+
           // If the tail provided a bit enough offset, return noalias!
           if ((uint64_t)(Offset2-Offset1) >= SizeMax)
             return NoAlias;
+          // Otherwise break - we don't look for another constant in the tail.
+          break;
         }
     }