X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FBasicAliasAnalysis.cpp;h=5785d09ff66468bed5c039eeeee6eb515b73909c;hb=3fefc182a00663bfadbcbe17711b6d08469c9727;hp=d37a4b176f7a0525426ec73fe6d89b53f8b08283;hpb=e4d87aa2de6e52952dca73716386db09aad5a8fd;p=oota-llvm.git

diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp
index d37a4b176f7..5785d09ff66 100644
--- a/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/lib/Analysis/BasicAliasAnalysis.cpp
@@ -22,6 +22,7 @@
 #include "llvm/Instructions.h"
 #include "llvm/Pass.h"
 #include "llvm/Target/TargetData.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/GetElementPtrTypeIterator.h"
 #include "llvm/Support/ManagedStatic.h"
@@ -104,17 +105,17 @@ namespace {
     bool pointsToConstantMemory(const Value *P);
 
     virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS,
-                                             std::vector<PointerAccessInfo> *Info);
+                                          std::vector<PointerAccessInfo> *Info);
 
   private:
     // CheckGEPInstructions - Check two GEP instructions with known
     // must-aliasing base pointers.  This checks to see if the index expressions
     // preclude the pointers from aliasing...
     AliasResult
-    CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops,
-                         unsigned G1Size,
-                         const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops,
-                         unsigned G2Size);
+    CheckGEPInstructions(const Type* BasePtr1Ty,
+                         Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1Size,
+                         const Type *BasePtr2Ty,
+                         Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2Size);
   };
 
   // Register this pass...
@@ -160,7 +161,8 @@ static const User *isGEP(const Value *V) {
   return 0;
 }
 
-static const Value *GetGEPOperands(const Value *V, std::vector<Value*> &GEPOps){
+static const Value *GetGEPOperands(const Value *V, 
+                                   SmallVector<Value*, 16> &GEPOps){
   assert(GEPOps.empty() && "Expect empty list to populate!");
   GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1,
                 cast<User>(V)->op_end());
@@ -269,16 +271,14 @@ BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
   if (V1 == V2) return MustAlias;
 
   if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) &&
-      V1->getType() != Type::LongTy && V2->getType() != Type::LongTy)
+      V1->getType() != Type::Int64Ty && V2->getType() != Type::Int64Ty)
     return NoAlias;  // Scalars cannot alias each other
 
   // Strip off cast instructions...
   if (const BitCastInst *I = dyn_cast<BitCastInst>(V1))
-    if (isa<PointerType>(I->getOperand(0)->getType()))
-      return alias(I->getOperand(0), V1Size, V2, V2Size);
+    return alias(I->getOperand(0), V1Size, V2, V2Size);
   if (const BitCastInst *I = dyn_cast<BitCastInst>(V2))
-    if (isa<PointerType>(I->getOperand(0)->getType()))
-      return alias(V1, V1Size, I->getOperand(0), V2Size);
+    return alias(V1, V1Size, I->getOperand(0), V2Size);
 
   // Figure out what objects these things are pointing to if we can...
   const Value *O1 = getUnderlyingObject(V1);
@@ -363,7 +363,7 @@ BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
        Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType()));
 
     // Do the base pointers alias?
-    AliasResult BaseAlias = alias(BasePtr1, V1Size, BasePtr2, V2Size);
+    AliasResult BaseAlias = alias(BasePtr1, ~0U, BasePtr2, ~0U);
     if (BaseAlias == NoAlias) return NoAlias;
     if (BaseAlias == MustAlias) {
       // If the base pointers alias each other exactly, check to see if we can
@@ -371,7 +371,7 @@ BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
       // non-aliasing.
 
       // Collect all of the chained GEP operands together into one simple place
-      std::vector<Value*> GEP1Ops, GEP2Ops;
+      SmallVector<Value*, 16> GEP1Ops, GEP2Ops;
       BasePtr1 = GetGEPOperands(V1, GEP1Ops);
       BasePtr2 = GetGEPOperands(V2, GEP2Ops);
 
@@ -379,8 +379,10 @@ BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
       // do the comparison.
       if (BasePtr1 == BasePtr2) {
         AliasResult GAlias =
-          CheckGEPInstructions(BasePtr1->getType(), GEP1Ops, V1Size,
-                               BasePtr2->getType(), GEP2Ops, V2Size);
+          CheckGEPInstructions(BasePtr1->getType(),
+                               &GEP1Ops[0], GEP1Ops.size(), V1Size,
+                               BasePtr2->getType(),
+                               &GEP2Ops[0], GEP2Ops.size(), V2Size);
         if (GAlias != MayAlias)
           return GAlias;
       }
@@ -398,7 +400,7 @@ BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
 
   if (V1Size != ~0U && V2Size != ~0U)
     if (isGEP(V1)) {
-      std::vector<Value*> GEPOperands;
+      SmallVector<Value*, 16> GEPOperands;
       const Value *BasePtr = GetGEPOperands(V1, GEPOperands);
 
       AliasResult R = alias(BasePtr, V1Size, V2, V2Size);
@@ -438,7 +440,9 @@ BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
                 GEPOperands[i] =
                   Constant::getNullValue(GEPOperands[i]->getType());
             int64_t Offset =
-              getTargetData().getIndexedOffset(BasePtr->getType(), GEPOperands);
+              getTargetData().getIndexedOffset(BasePtr->getType(),
+                                               &GEPOperands[0],
+                                               GEPOperands.size());
 
             if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size)
               return NoAlias;
@@ -458,14 +462,10 @@ static bool IndexOperandsEqual(Value *V1, Value *V2) {
   if (Constant *C1 = dyn_cast<Constant>(V1))
     if (Constant *C2 = dyn_cast<Constant>(V2)) {
       // Sign extend the constants to long types, if necessary
-      if (C1->getType()->getPrimitiveSizeInBits() < 64)
-        C1 = ConstantExpr::getSExt(C1, Type::LongTy);
-      else if (C1->getType() == Type::ULongTy)
-        C1 = ConstantExpr::getBitCast(C1, Type::LongTy);
-      if (C2->getType()->getPrimitiveSizeInBits() < 64)
-        C2 = ConstantExpr::getSExt(C2, Type::LongTy);
-      else if (C2->getType() == Type::ULongTy)
-        C2 = ConstantExpr::getBitCast(C2, Type::LongTy);
+      if (C1->getType() != Type::Int64Ty)
+        C1 = ConstantExpr::getSExt(C1, Type::Int64Ty);
+      if (C2->getType() != Type::Int64Ty) 
+        C2 = ConstantExpr::getSExt(C2, Type::Int64Ty);
       return C1 == C2;
     }
   return false;
@@ -476,8 +476,8 @@ static bool IndexOperandsEqual(Value *V1, Value *V2) {
 /// pointers from aliasing...
 AliasAnalysis::AliasResult 
 BasicAliasAnalysis::CheckGEPInstructions(
-  const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops, unsigned G1S,
-  const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops, unsigned G2S) {
+  const Type* BasePtr1Ty, Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1S,
+  const Type *BasePtr2Ty, Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2S) {
   // We currently can't handle the case when the base pointers have different
   // primitive types.  Since this is uncommon anyway, we are happy being
   // extremely conservative.
@@ -488,7 +488,7 @@ BasicAliasAnalysis::CheckGEPInstructions(
 
   // Find the (possibly empty) initial sequence of equal values... which are not
   // necessarily constants.
-  unsigned NumGEP1Operands = GEP1Ops.size(), NumGEP2Operands = GEP2Ops.size();
+  unsigned NumGEP1Operands = NumGEP1Ops, NumGEP2Operands = NumGEP2Ops;
   unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands);
   unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands);
   unsigned UnequalOper = 0;
@@ -512,7 +512,10 @@ BasicAliasAnalysis::CheckGEPInstructions(
   // getelementptrs, check to see if the tail of the leftover one is all zeros.
   // If so, return mustalias.
   if (UnequalOper == MinOperands) {
-    if (GEP1Ops.size() < GEP2Ops.size()) std::swap(GEP1Ops, GEP2Ops);
+    if (NumGEP1Ops < NumGEP2Ops) {
+      std::swap(GEP1Ops, GEP2Ops);
+      std::swap(NumGEP1Ops, NumGEP2Ops);
+    }
 
     bool AllAreZeros = true;
     for (unsigned i = UnequalOper; i != MaxOperands; ++i)
@@ -554,14 +557,10 @@ BasicAliasAnalysis::CheckGEPInstructions(
         if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){
           if (G1OC->getType() != G2OC->getType()) {
             // Sign extend both operands to long.
-            if (G1OC->getType()->getPrimitiveSizeInBits() < 64)
-              G1OC = ConstantExpr::getSExt(G1OC, Type::LongTy);
-            else if (G1OC->getType() == Type::ULongTy)
-              G1OC = ConstantExpr::getBitCast(G1OC, Type::LongTy);
-            if (G2OC->getType()->getPrimitiveSizeInBits() < 64)
-              G2OC = ConstantExpr::getSExt(G2OC, Type::LongTy);
-            else if (G2OC->getType() == Type::ULongTy)
-              G2OC = ConstantExpr::getBitCast(G2OC, Type::LongTy);
+            if (G1OC->getType() != Type::Int64Ty)
+              G1OC = ConstantExpr::getSExt(G1OC, Type::Int64Ty);
+            if (G2OC->getType() != Type::Int64Ty) 
+              G2OC = ConstantExpr::getSExt(G2OC, Type::Int64Ty);
             GEP1Ops[FirstConstantOper] = G1OC;
             GEP2Ops[FirstConstantOper] = G2OC;
           }
@@ -592,9 +591,11 @@ BasicAliasAnalysis::CheckGEPInstructions(
             if (G1OC) {
               Constant *Compare = ConstantExpr::getICmp(ICmpInst::ICMP_SGT, 
                                                         G1OC, G2OC);
-              if (ConstantBool *CV = dyn_cast<ConstantBool>(Compare)) {
-                if (CV->getValue())   // If they are comparable and G2 > G1
+              if (ConstantInt *CV = dyn_cast<ConstantInt>(Compare)) {
+                if (CV->getZExtValue()) {  // If they are comparable and G2 > G1
                   std::swap(GEP1Ops, GEP2Ops);  // Make GEP1 < GEP2
+                  std::swap(NumGEP1Ops, NumGEP2Ops);
+                }
                 break;
               }
             }
@@ -610,13 +611,15 @@ BasicAliasAnalysis::CheckGEPInstructions(
   // case, there may still be hope.  Check this now.
   if (FirstConstantOper == MinOperands) {
     // Make GEP1Ops be the longer one if there is a longer one.
-    if (GEP1Ops.size() < GEP2Ops.size())
+    if (NumGEP1Ops < NumGEP2Ops) {
       std::swap(GEP1Ops, GEP2Ops);
+      std::swap(NumGEP1Ops, NumGEP2Ops);
+    }
 
     // Is there anything to check?
-    if (GEP1Ops.size() > MinOperands) {
+    if (NumGEP1Ops > MinOperands) {
       for (unsigned i = FirstConstantOper; i != MaxOperands; ++i)
-        if (isa<ConstantInt>(GEP1Ops[i]) &&
+        if (isa<ConstantInt>(GEP1Ops[i]) && 
             !cast<Constant>(GEP1Ops[i])->isNullValue()) {
           // Yup, there's a constant in the tail.  Set all variables to
           // constants in the GEP instruction to make it suiteable for
@@ -627,11 +630,12 @@ BasicAliasAnalysis::CheckGEPInstructions(
           // Okay, now get the offset.  This is the relative offset for the full
           // instruction.
           const TargetData &TD = getTargetData();
-          int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops);
+          int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops,
+                                                NumGEP1Ops);
 
-          // Now crop off any constants from the end...
-          GEP1Ops.resize(MinOperands);
-          int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops);
+          // Now check without any constants at the end.
+          int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops,
+                                                MinOperands);
 
           // If the tail provided a bit enough offset, return noalias!
           if ((uint64_t)(Offset2-Offset1) >= SizeMax)
@@ -661,7 +665,7 @@ BasicAliasAnalysis::CheckGEPInstructions(
   const Type *ZeroIdxTy = GEPPointerTy;
   for (unsigned i = 0; i != FirstConstantOper; ++i) {
     if (!isa<StructType>(ZeroIdxTy))
-      GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::UIntTy);
+      GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::Int32Ty);
 
     if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy))
       ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]);
@@ -671,8 +675,8 @@ BasicAliasAnalysis::CheckGEPInstructions(
 
   // Loop over the rest of the operands...
   for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) {
-    const Value *Op1 = i < GEP1Ops.size() ? GEP1Ops[i] : 0;
-    const Value *Op2 = i < GEP2Ops.size() ? GEP2Ops[i] : 0;
+    const Value *Op1 = i < NumGEP1Ops ? GEP1Ops[i] : 0;
+    const Value *Op2 = i < NumGEP2Ops ? GEP2Ops[i] : 0;
     // If they are equal, use a zero index...
     if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) {
       if (!isa<ConstantInt>(Op1))
@@ -685,7 +689,7 @@ BasicAliasAnalysis::CheckGEPInstructions(
           if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) {
             if (Op1C->getZExtValue() >= AT->getNumElements())
               return MayAlias;  // Be conservative with out-of-range accesses
-          } else if (const PackedType *PT = dyn_cast<PackedType>(BasePtr1Ty)) {
+          } else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty)) {
             if (Op1C->getZExtValue() >= PT->getNumElements())
               return MayAlias;  // Be conservative with out-of-range accesses
           }
@@ -702,9 +706,9 @@ BasicAliasAnalysis::CheckGEPInstructions(
           // value possible.
           //
           if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
-            GEP1Ops[i] = ConstantInt::get(Type::LongTy, AT->getNumElements()-1);
-          else if (const PackedType *PT = dyn_cast<PackedType>(BasePtr1Ty))
-            GEP1Ops[i] = ConstantInt::get(Type::LongTy, PT->getNumElements()-1);
+            GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,AT->getNumElements()-1);
+          else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty))
+            GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,PT->getNumElements()-1);
 
         }
       }
@@ -715,7 +719,7 @@ BasicAliasAnalysis::CheckGEPInstructions(
           if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) {
             if (Op2C->getZExtValue() >= AT->getNumElements())
               return MayAlias;  // Be conservative with out-of-range accesses
-          } else if (const PackedType *PT = dyn_cast<PackedType>(BasePtr1Ty)) {
+          } else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty)) {
             if (Op2C->getZExtValue() >= PT->getNumElements())
               return MayAlias;  // Be conservative with out-of-range accesses
           }
@@ -741,8 +745,10 @@ BasicAliasAnalysis::CheckGEPInstructions(
   }
 
   if (GEPPointerTy->getElementType()->isSized()) {
-    int64_t Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops);
-    int64_t Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops);
+    int64_t Offset1 =
+      getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops, NumGEP1Ops);
+    int64_t Offset2 = 
+      getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops, NumGEP2Ops);
     assert(Offset1<Offset2 && "There is at least one different constant here!");
 
     if ((uint64_t)(Offset2-Offset1) >= SizeMax) {
@@ -755,7 +761,7 @@ BasicAliasAnalysis::CheckGEPInstructions(
 }
 
 namespace {
-  struct StringCompare {
+  struct VISIBILITY_HIDDEN StringCompare {
     bool operator()(const char *LHS, const char *RHS) {
       return strcmp(LHS, RHS) < 0;
     }
@@ -833,7 +839,7 @@ static ManagedStatic<std::vector<const char*> > OnlyReadsMemoryTable;
 AliasAnalysis::ModRefBehavior
 BasicAliasAnalysis::getModRefBehavior(Function *F, CallSite CS,
                                       std::vector<PointerAccessInfo> *Info) {
-  if (!F->isExternal()) return UnknownModRefBehavior;
+  if (!F->isDeclaration()) return UnknownModRefBehavior;
 
   static bool Initialized = false;
   if (!Initialized) {