For PR950:

The long awaited CAST patch. This introduces 12 new instructions into LLVM
to replace the cast instruction. Corresponding changes throughout LLVM are
provided. This passes llvm-test, llvm/test, and SPEC CPUINT2000 with the
exception of 175.vpr which fails only on a slight floating point output
difference.


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

61 files changed, 5687 insertions, 3490 deletions

diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp
index ec1a72b951..a7269ffa09 100644
--- a/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/lib/Analysis/BasicAliasAnalysis.cpp
@@ -129,27 +129,23 @@ ImmutablePass *llvm::createBasicAliasAnalysisPass() {
   return new BasicAliasAnalysis();
 }
 
-// hasUniqueAddress - Return true if the specified value points to something
-// with a unique, discernable, address.
-static inline bool hasUniqueAddress(const Value *V) {
-  return isa<GlobalValue>(V) || isa<AllocationInst>(V);
-}
-
 // getUnderlyingObject - This traverses the use chain to figure out what object
 // the specified value points to.  If the value points to, or is derived from, a
 // unique object or an argument, return it.
 static const Value *getUnderlyingObject(const Value *V) {
   if (!isa<PointerType>(V->getType())) return 0;
 
-  // If we are at some type of object... return it.
-  if (hasUniqueAddress(V) || isa<Argument>(V)) return V;
+  // If we are at some type of object, return it. GlobalValues and Allocations
+  // have unique addresses. 
+  if (isa<GlobalValue>(V) || isa<AllocationInst>(V) || isa<Argument>(V))
+    return V;
 
   // Traverse through different addressing mechanisms...
   if (const Instruction *I = dyn_cast<Instruction>(V)) {
-    if (isa<CastInst>(I) || isa<GetElementPtrInst>(I))
+    if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I))
       return getUnderlyingObject(I->getOperand(0));
   } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
-    if (CE->getOpcode() == Instruction::Cast ||
+    if (CE->getOpcode() == Instruction::BitCast || 
         CE->getOpcode() == Instruction::GetElementPtr)
       return getUnderlyingObject(CE->getOperand(0));
   }
@@ -192,28 +188,34 @@ bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) {
   return false;
 }
 
+// Determine if an AllocationInst instruction escapes from the function it is
+// contained in. If it does not escape, there is no way for another function to
+// mod/ref it.  We do this by looking at its uses and determining if the uses
+// can escape (recursively).
 static bool AddressMightEscape(const Value *V) {
   for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end();
        UI != E; ++UI) {
     const Instruction *I = cast<Instruction>(*UI);
     switch (I->getOpcode()) {
-    case Instruction::Load: break;
+    case Instruction::Load: 
+      break; //next use.
     case Instruction::Store:
       if (I->getOperand(0) == V)
         return true; // Escapes if the pointer is stored.
-      break;
+      break; // next use.
     case Instruction::GetElementPtr:
-      if (AddressMightEscape(I)) return true;
-      break;
-    case Instruction::Cast:
+      if (AddressMightEscape(I))
+        return true;
+    case Instruction::BitCast:
       if (!isa<PointerType>(I->getType()))
         return true;
-      if (AddressMightEscape(I)) return true;
-      break;
+      if (AddressMightEscape(I))
+        return true;
+      break; // next use
     case Instruction::Ret:
       // If returned, the address will escape to calling functions, but no
       // callees could modify it.
-      break;
+      break; // next use
     default:
       return true;
     }
@@ -257,12 +259,10 @@ BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
                           const Value *V2, unsigned V2Size) {
   // Strip off any constant expression casts if they exist
   if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V1))
-    if (CE->getOpcode() == Instruction::Cast &&
-        isa<PointerType>(CE->getOperand(0)->getType()))
+    if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType()))
       V1 = CE->getOperand(0);
   if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2))
-    if (CE->getOpcode() == Instruction::Cast &&
-        isa<PointerType>(CE->getOperand(0)->getType()))
+    if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType()))
       V2 = CE->getOperand(0);
 
   // Are we checking for alias of the same value?
@@ -273,10 +273,10 @@ BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
     return NoAlias;  // Scalars cannot alias each other
 
   // Strip off cast instructions...
-  if (const Instruction *I = dyn_cast<CastInst>(V1))
+  if (const BitCastInst *I = dyn_cast<BitCastInst>(V1))
     if (isa<PointerType>(I->getOperand(0)->getType()))
       return alias(I->getOperand(0), V1Size, V2, V2Size);
-  if (const Instruction *I = dyn_cast<CastInst>(V2))
+  if (const BitCastInst *I = dyn_cast<BitCastInst>(V2))
     if (isa<PointerType>(I->getOperand(0)->getType()))
       return alias(V1, V1Size, I->getOperand(0), V2Size);
 
@@ -450,14 +450,22 @@ BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
   return MayAlias;
 }
 
-static bool ValuesEqual(Value *V1, Value *V2) {
+// This function is used to determin if the indices of two GEP instructions are
+// equal. V1 and V2 are the indices.
+static bool IndexOperandsEqual(Value *V1, Value *V2) {
   if (V1->getType() == V2->getType())
     return V1 == V2;
   if (Constant *C1 = dyn_cast<Constant>(V1))
     if (Constant *C2 = dyn_cast<Constant>(V2)) {
-      // Sign extend the constants to long types.
-      C1 = ConstantExpr::getSignExtend(C1, Type::LongTy);
-      C2 = ConstantExpr::getSignExtend(C2, Type::LongTy);
+      // Sign extend the constants to long types, if necessary
+      if (C1->getType()->getPrimitiveSizeInBits() < 64)
+        C1 = ConstantExpr::getSignExtend(C1, Type::LongTy);
+      else if (C1->getType() == Type::ULongTy)
+        C1 = ConstantExpr::getBitCast(C1, Type::LongTy);
+      if (C2->getType()->getPrimitiveSizeInBits() < 64)
+        C2 = ConstantExpr::getSignExtend(C2, Type::LongTy);
+      else if (C2->getType() == Type::ULongTy)
+        C2 = ConstantExpr::getBitCast(C2, Type::LongTy);
       return C1 == C2;
     }
   return false;
@@ -485,7 +493,7 @@ BasicAliasAnalysis::CheckGEPInstructions(
   unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands);
   unsigned UnequalOper = 0;
   while (UnequalOper != MinOperands &&
-         ValuesEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) {
+         IndexOperandsEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) {
     // Advance through the type as we go...
     ++UnequalOper;
     if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
@@ -546,8 +554,14 @@ BasicAliasAnalysis::CheckGEPInstructions(
         if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){
           if (G1OC->getType() != G2OC->getType()) {
             // Sign extend both operands to long.
-            G1OC = ConstantExpr::getSignExtend(G1OC, Type::LongTy);
-            G2OC = ConstantExpr::getSignExtend(G2OC, Type::LongTy);
+            if (G1OC->getType()->getPrimitiveSizeInBits() < 64)
+              G1OC = ConstantExpr::getSignExtend(G1OC, Type::LongTy);
+            else if (G1OC->getType() == Type::ULongTy)
+              G1OC = ConstantExpr::getBitCast(G1OC, Type::LongTy);
+            if (G2OC->getType()->getPrimitiveSizeInBits() < 64)
+              G2OC = ConstantExpr::getSignExtend(G2OC, Type::LongTy);
+            else if (G2OC->getType() == Type::ULongTy)
+              G2OC = ConstantExpr::getBitCast(G2OC, Type::LongTy);
             GEP1Ops[FirstConstantOper] = G1OC;
             GEP2Ops[FirstConstantOper] = G2OC;
           }
diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp
index 505fe91362..8b8bde0026 100644
--- a/lib/Analysis/DataStructure/DataStructure.cpp
+++ b/lib/Analysis/DataStructure/DataStructure.cpp
@@ -410,7 +410,7 @@ static bool ElementTypesAreCompatible(const Type *T1, const Type *T2,
 
     const Type *T1 = T1W.getCurrentType();
     const Type *T2 = T2W.getCurrentType();
-    if (T1 != T2 && !T1->isLosslesslyConvertibleTo(T2))
+    if (T1 != T2 && !T1->canLosslesslyBitCastTo(T2))
       return false;
 
     T1W.StepToNextType();
@@ -701,7 +701,7 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset,
   // Check to see if we have a compatible, but different type...
   if (NewTySize == SubTypeSize) {
     // Check to see if this type is obviously convertible... int -> uint f.e.
-    if (NewTy->isLosslesslyConvertibleTo(SubType))
+    if (NewTy->canLosslesslyBitCastTo(SubType))
       return false;
 
     // Check to see if we have a pointer & integer mismatch going on here,
diff --git a/lib/Analysis/DataStructure/Local.cpp b/lib/Analysis/DataStructure/Local.cpp
index c8880c11c5..34947371c6 100644
--- a/lib/Analysis/DataStructure/Local.cpp
+++ b/lib/Analysis/DataStructure/Local.cpp
@@ -240,7 +240,7 @@ DSNodeHandle GraphBuilder::getValueDest(Value &Val) {
     N->addGlobal(GV);
   } else if (Constant *C = dyn_cast<Constant>(V)) {
     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
-      if (CE->getOpcode() == Instruction::Cast) {
+      if (CE->isCast()) {
         if (isa<PointerType>(CE->getOperand(0)->getType()))
           NH = getValueDest(*CE->getOperand(0));
         else
@@ -1091,20 +1091,27 @@ void GraphBuilder::visitFreeInst(FreeInst &FI) {
 
 /// Handle casts...
 void GraphBuilder::visitCastInst(CastInst &CI) {
-  if (isPointerType(CI.getType()))
-    if (isPointerType(CI.getOperand(0)->getType())) {
-      DSNodeHandle Ptr = getValueDest(*CI.getOperand(0));
-      if (Ptr.getNode() == 0) return;
-
-      // Cast one pointer to the other, just act like a copy instruction
-      setDestTo(CI, Ptr);
-    } else {
-      // Cast something (floating point, small integer) to a pointer.  We need
-      // to track the fact that the node points to SOMETHING, just something we
-      // don't know about.  Make an "Unknown" node.
-      //
-      setDestTo(CI, createNode()->setUnknownNodeMarker());
-    }
+  // Pointers can only be cast with BitCast so check that the instruction
+  // is a BitConvert. If not, its guaranteed not to involve any pointers so
+  // we don't do anything.
+  switch (CI.getOpcode()) {
+  default: break;
+  case Instruction::BitCast:
+  case Instruction::IntToPtr:
+    if (isPointerType(CI.getType()))
+      if (isPointerType(CI.getOperand(0)->getType())) {
+        DSNodeHandle Ptr = getValueDest(*CI.getOperand(0));
+        if (Ptr.getNode() == 0) return;
+        // Cast one pointer to the other, just act like a copy instruction
+        setDestTo(CI, Ptr);
+      } else {
+        // Cast something (floating point, small integer) to a pointer.  We 
+        // need to track the fact that the node points to SOMETHING, just 
+        // something we don't know about.  Make an "Unknown" node.
+        setDestTo(CI, createNode()->setUnknownNodeMarker());
+      }
+    break;
+  }
 }
 
 
diff --git a/lib/Analysis/IPA/Andersens.cpp b/lib/Analysis/IPA/Andersens.cpp
index dd94b3832d..73aa231e21 100644
--- a/lib/Analysis/IPA/Andersens.cpp
+++ b/lib/Analysis/IPA/Andersens.cpp
@@ -529,11 +529,10 @@ Andersens::Node *Andersens::getNodeForConstantPointer(Constant *C) {
     switch (CE->getOpcode()) {
     case Instruction::GetElementPtr:
       return getNodeForConstantPointer(CE->getOperand(0));
-    case Instruction::Cast:
-      if (isa<PointerType>(CE->getOperand(0)->getType()))
-        return getNodeForConstantPointer(CE->getOperand(0));
-      else
-        return &GraphNodes[UniversalSet];
+    case Instruction::IntToPtr:
+      return &GraphNodes[UniversalSet];
+    case Instruction::BitCast:
+      return getNodeForConstantPointer(CE->getOperand(0));
     default:
       std::cerr << "Constant Expr not yet handled: " << *CE << "\n";
       assert(0);
@@ -557,11 +556,10 @@ Andersens::Node *Andersens::getNodeForConstantPointerTarget(Constant *C) {
     switch (CE->getOpcode()) {
     case Instruction::GetElementPtr:
       return getNodeForConstantPointerTarget(CE->getOperand(0));
-    case Instruction::Cast:
-      if (isa<PointerType>(CE->getOperand(0)->getType()))
-        return getNodeForConstantPointerTarget(CE->getOperand(0));
-      else
-        return &GraphNodes[UniversalSet];
+    case Instruction::IntToPtr:
+      return &GraphNodes[UniversalSet];
+    case Instruction::BitCast:
+      return getNodeForConstantPointerTarget(CE->getOperand(0));
     default:
       std::cerr << "Constant Expr not yet handled: " << *CE << "\n";
       assert(0);
diff --git a/lib/Analysis/IPA/GlobalsModRef.cpp b/lib/Analysis/IPA/GlobalsModRef.cpp
index d4dc18dc71..59cf66f6c3 100644
--- a/lib/Analysis/IPA/GlobalsModRef.cpp
+++ b/lib/Analysis/IPA/GlobalsModRef.cpp
@@ -167,10 +167,10 @@ static Value *getUnderlyingObject(Value *V) {
   
   // Traverse through different addressing mechanisms.
   if (Instruction *I = dyn_cast<Instruction>(V)) {
-    if (isa<CastInst>(I) || isa<GetElementPtrInst>(I))
+    if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I))
       return getUnderlyingObject(I->getOperand(0));
   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
-    if (CE->getOpcode() == Instruction::Cast ||
+    if (CE->getOpcode() == Instruction::BitCast || 
         CE->getOpcode() == Instruction::GetElementPtr)
       return getUnderlyingObject(CE->getOperand(0));
   }
@@ -252,8 +252,8 @@ bool GlobalsModRef::AnalyzeUsesOfPointer(Value *V,
       for (unsigned i = 3, e = II->getNumOperands(); i != e; ++i)
         if (II->getOperand(i) == V) return true;
     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) {
-      if (CE->getOpcode() == Instruction::GetElementPtr ||
-          CE->getOpcode() == Instruction::Cast) {
+      if (CE->getOpcode() == Instruction::GetElementPtr || 
+          CE->getOpcode() == Instruction::BitCast) {
         if (AnalyzeUsesOfPointer(CE, Readers, Writers))
           return true;
       } else {
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index cd7000503c..8c809f8c5a 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -203,7 +203,6 @@ static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
 SCEVTruncateExpr::SCEVTruncateExpr(const SCEVHandle &op, const Type *ty)
   : SCEV(scTruncate), Op(op), Ty(ty) {
   assert(Op->getType()->isInteger() && Ty->isInteger() &&
-         Ty->isUnsigned() &&
          "Cannot truncate non-integer value!");
   assert(Op->getType()->getPrimitiveSize() > Ty->getPrimitiveSize() &&
          "This is not a truncating conversion!");
@@ -230,7 +229,6 @@ static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
 SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty)
   : SCEV(scZeroExtend), Op(op), Ty(ty) {
   assert(Op->getType()->isInteger() && Ty->isInteger() &&
-         Ty->isUnsigned() &&
          "Cannot zero extend non-integer value!");
   assert(Op->getType()->getPrimitiveSize() < Ty->getPrimitiveSize() &&
          "This is not an extending conversion!");
@@ -1139,7 +1137,6 @@ namespace {
     /// createSCEV - We know that there is no SCEV for the specified value.
     /// Analyze the expression.
     SCEVHandle createSCEV(Value *V);
-    SCEVHandle createNodeForCast(CastInst *CI);
 
     /// createNodeForPHI - Provide the special handling we need to analyze PHI
     /// SCEVs.
@@ -1341,35 +1338,6 @@ SCEVHandle ScalarEvolutionsImpl::createNodeForPHI(PHINode *PN) {
   return SCEVUnknown::get(PN);
 }
 
-/// createNodeForCast - Handle the various forms of casts that we support.
-///
-SCEVHandle ScalarEvolutionsImpl::createNodeForCast(CastInst *CI) {
-  const Type *SrcTy = CI->getOperand(0)->getType();
-  const Type *DestTy = CI->getType();
-
-  // If this is a noop cast (ie, conversion from int to uint), ignore it.
-  if (SrcTy->isLosslesslyConvertibleTo(DestTy))
-    return getSCEV(CI->getOperand(0));
-
-  if (SrcTy->isInteger() && DestTy->isInteger()) {
-    // Otherwise, if this is a truncating integer cast, we can represent this
-    // cast.
-    if (SrcTy->getPrimitiveSize() > DestTy->getPrimitiveSize())
-      return SCEVTruncateExpr::get(getSCEV(CI->getOperand(0)),
-                                   CI->getType()->getUnsignedVersion());
-    if (SrcTy->isUnsigned() &&
-        SrcTy->getPrimitiveSize() <= DestTy->getPrimitiveSize())
-      return SCEVZeroExtendExpr::get(getSCEV(CI->getOperand(0)),
-                                     CI->getType()->getUnsignedVersion());
-  }
-
-  // If this is an sign or zero extending cast and we can prove that the value
-  // will never overflow, we could do similar transformations.
-
-  // Otherwise, we can't handle this cast!
-  return SCEVUnknown::get(CI);
-}
-
 
 /// createSCEV - We know that there is no SCEV for the specified value.
 /// Analyze the expression.
@@ -1401,8 +1369,21 @@ SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) {
       }
       break;
 
-    case Instruction::Cast:
-      return createNodeForCast(cast<CastInst>(I));
+    case Instruction::Trunc:
+      if (I->getType()->isInteger() && I->getOperand(0)->getType()->isInteger())
+        return SCEVTruncateExpr::get(getSCEV(I->getOperand(0)), 
+                                     I->getType()->getUnsignedVersion());
+      break;
+
+    case Instruction::ZExt:
+      if (I->getType()->isInteger() && I->getOperand(0)->getType()->isInteger())
+        return SCEVZeroExtendExpr::get(getSCEV(I->getOperand(0)), 
+                                       I->getType()->getUnsignedVersion());
+      break;
+
+    case Instruction::BitCast:
+      // BitCasts are no-op casts so we just eliminate the cast.
+      return getSCEV(I->getOperand(0));
 
     case Instruction::PHI:
       return createNodeForPHI(cast<PHINode>(I));
@@ -1724,9 +1705,10 @@ static Constant *ConstantFold(const Instruction *I,
   if (isa<BinaryOperator>(I) || isa<ShiftInst>(I))
     return ConstantExpr::get(I->getOpcode(), Operands[0], Operands[1]);
 
+  if (isa<CastInst>(I))
+    return ConstantExpr::getCast(I->getOpcode(), Operands[0], I->getType());
+
   switch (I->getOpcode()) {
-  case Instruction::Cast:
-    return ConstantExpr::getCast(Operands[0], I->getType());
   case Instruction::Select:
     return ConstantExpr::getSelect(Operands[0], Operands[1], Operands[2]);
   case Instruction::Call:
@@ -1734,7 +1716,6 @@ static Constant *ConstantFold(const Instruction *I,
       Operands.erase(Operands.begin());
       return ConstantFoldCall(cast<Function>(GV), Operands);
     }
-
     return 0;
   case Instruction::GetElementPtr:
     Constant *Base = Operands[0];
diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp
index 68b52dd4fa..b6d77b93ae 100644
--- a/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -30,8 +30,7 @@ Value *SCEVExpander::InsertCastOfTo(Value *V, const Type *Ty) {
          UI != E; ++UI) {
       if ((*UI)->getType() == Ty)
         if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) {
-          // If the cast isn't in the first instruction of the function,
-          // move it.
+          // If the cast isn't the first instruction of the function, move it.
           if (BasicBlock::iterator(CI) != 
               A->getParent()->getEntryBlock().begin()) {
             CI->moveBefore(A->getParent()->getEntryBlock().begin());
@@ -39,8 +38,8 @@ Value *SCEVExpander::InsertCastOfTo(Value *V, const Type *Ty) {
           return CI;
         }
     }
-    return new CastInst(V, Ty, V->getName(),
-                        A->getParent()->getEntryBlock().begin());
+    return CastInst::createInferredCast(V, Ty, V->getName(),
+