lib/VMCore/ConstantFold.cpp

   1 //===- ConstantFold.cpp - LLVM constant folder ----------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements folding of constants for LLVM.  This implements the
  11 // (internal) ConstantFold.h interface, which is used by the
  12 // ConstantExpr::get* methods to automatically fold constants when possible.
  13 //
  14 // The current constant folding implementation is implemented in two pieces: the
  15 // template-based folder for simple primitive constants like ConstantInt, and
  16 // the special case hackery that we use to symbolically evaluate expressions
  17 // that use ConstantExprs.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #include "ConstantFold.h"
  22 #include "llvm/Constants.h"
  23 #include "llvm/Instructions.h"
  24 #include "llvm/DerivedTypes.h"
  25 #include "llvm/Function.h"
  26 #include "llvm/GlobalAlias.h"
  27 #include "llvm/ADT/SmallVector.h"
  28 #include "llvm/Support/Compiler.h"
  29 #include "llvm/Support/GetElementPtrTypeIterator.h"
  30 #include "llvm/Support/ManagedStatic.h"
  31 #include "llvm/Support/MathExtras.h"
  32 #include <limits>
  33 using namespace llvm;
  34
  35 //===----------------------------------------------------------------------===//
  36 //                ConstantFold*Instruction Implementations
  37 //===----------------------------------------------------------------------===//
  38
  39 /// CastConstantVector - Convert the specified ConstantVector node to the
  40 /// specified vector type.  At this point, we know that the elements of the
  41 /// input vector constant are all simple integer or FP values.
  42 static Constant *CastConstantVector(ConstantVector *CV,
  43                                     const VectorType *DstTy) {
  44   unsigned SrcNumElts = CV->getType()->getNumElements();
  45   unsigned DstNumElts = DstTy->getNumElements();
  46   const Type *SrcEltTy = CV->getType()->getElementType();
  47   const Type *DstEltTy = DstTy->getElementType();
  48
  49   // If both vectors have the same number of elements (thus, the elements
  50   // are the same size), perform the conversion now.
  51   if (SrcNumElts == DstNumElts) {
  52     std::vector<Constant*> Result;
  53
  54     // If the src and dest elements are both integers, or both floats, we can
  55     // just BitCast each element because the elements are the same size.
  56     if ((SrcEltTy->isInteger() && DstEltTy->isInteger()) ||
  57         (SrcEltTy->isFloatingPoint() && DstEltTy->isFloatingPoint())) {
  58       for (unsigned i = 0; i != SrcNumElts; ++i)
  59         Result.push_back(
  60           ConstantExpr::getBitCast(CV->getOperand(i), DstEltTy));
  61       return ConstantVector::get(Result);
  62     }
  63
  64     // If this is an int-to-fp cast ..
  65     if (SrcEltTy->isInteger()) {
  66       // Ensure that it is int-to-fp cast
  67       assert(DstEltTy->isFloatingPoint());
  68       if (DstEltTy->getTypeID() == Type::DoubleTyID) {
  69         for (unsigned i = 0; i != SrcNumElts; ++i) {
  70           ConstantInt *CI = cast<ConstantInt>(CV->getOperand(i));
  71           double V = CI->getValue().bitsToDouble();
  72           Result.push_back(ConstantFP::get(Type::DoubleTy, APFloat(V)));
  73         }
  74         return ConstantVector::get(Result);
  75       }
  76       assert(DstEltTy == Type::FloatTy && "Unknown fp type!");
  77       for (unsigned i = 0; i != SrcNumElts; ++i) {
  78         ConstantInt *CI = cast<ConstantInt>(CV->getOperand(i));
  79         float V = CI->getValue().bitsToFloat();
  80         Result.push_back(ConstantFP::get(Type::FloatTy, APFloat(V)));
  81       }
  82       return ConstantVector::get(Result);
  83     }
  84
  85     // Otherwise, this is an fp-to-int cast.
  86     assert(SrcEltTy->isFloatingPoint() && DstEltTy->isInteger());
  87
  88     if (SrcEltTy->getTypeID() == Type::DoubleTyID) {
  89       for (unsigned i = 0; i != SrcNumElts; ++i) {
  90         uint64_t V =
  91           DoubleToBits(cast<ConstantFP>(CV->getOperand(i))->
  92                        getValueAPF().convertToDouble());
  93         Constant *C = ConstantInt::get(Type::Int64Ty, V);
  94         Result.push_back(ConstantExpr::getBitCast(C, DstEltTy ));
  95       }
  96       return ConstantVector::get(Result);
  97     }
  98
  99     assert(SrcEltTy->getTypeID() == Type::FloatTyID);
 100     for (unsigned i = 0; i != SrcNumElts; ++i) {
 101       uint32_t V = FloatToBits(cast<ConstantFP>(CV->getOperand(i))->
 102                                getValueAPF().convertToFloat());
 103       Constant *C = ConstantInt::get(Type::Int32Ty, V);
 104       Result.push_back(ConstantExpr::getBitCast(C, DstEltTy));
 105     }
 106     return ConstantVector::get(Result);
 107   }
 108
 109   // Otherwise, this is a cast that changes element count and size.  Handle
 110   // casts which shrink the elements here.
 111
 112   // FIXME: We need to know endianness to do this!
 113
 114   return 0;
 115 }
 116
 117 /// This function determines which opcode to use to fold two constant cast
 118 /// expressions together. It uses CastInst::isEliminableCastPair to determine
 119 /// the opcode. Consequently its just a wrapper around that function.
 120 /// @brief Determine if it is valid to fold a cast of a cast
 121 static unsigned
 122 foldConstantCastPair(
 123   unsigned opc,          ///< opcode of the second cast constant expression
 124   const ConstantExpr*Op, ///< the first cast constant expression
 125   const Type *DstTy      ///< desintation type of the first cast
 126 ) {
 127   assert(Op && Op->isCast() && "Can't fold cast of cast without a cast!");
 128   assert(DstTy && DstTy->isFirstClassType() && "Invalid cast destination type");
 129   assert(CastInst::isCast(opc) && "Invalid cast opcode");
 130
 131   // The the types and opcodes for the two Cast constant expressions
 132   const Type *SrcTy = Op->getOperand(0)->getType();
 133   const Type *MidTy = Op->getType();
 134   Instruction::CastOps firstOp = Instruction::CastOps(Op->getOpcode());
 135   Instruction::CastOps secondOp = Instruction::CastOps(opc);
 136
 137   // Let CastInst::isEliminableCastPair do the heavy lifting.
 138   return CastInst::isEliminableCastPair(firstOp, secondOp, SrcTy, MidTy, DstTy,
 139                                         Type::Int64Ty);
 140 }
 141
 142 Constant *llvm::ConstantFoldCastInstruction(unsigned opc, const Constant *V,
 143                                             const Type *DestTy) {
 144   const Type *SrcTy = V->getType();
 145
 146   if (isa<UndefValue>(V)) {
 147     // zext(undef) = 0, because the top bits will be zero.
 148     // sext(undef) = 0, because the top bits will all be the same.
 149     if (opc == Instruction::ZExt || opc == Instruction::SExt)
 150       return Constant::getNullValue(DestTy);
 151     return UndefValue::get(DestTy);
 152   }
 153
 154   // If the cast operand is a constant expression, there's a few things we can
 155   // do to try to simplify it.
 156   if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
 157     if (CE->isCast()) {
 158       // Try hard to fold cast of cast because they are often eliminable.
 159       if (unsigned newOpc = foldConstantCastPair(opc, CE, DestTy))
 160         return ConstantExpr::getCast(newOpc, CE->getOperand(0), DestTy);
 161     } else if (CE->getOpcode() == Instruction::GetElementPtr) {
 162       // If all of the indexes in the GEP are null values, there is no pointer
 163       // adjustment going on.  We might as well cast the source pointer.
 164       bool isAllNull = true;
 165       for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
 166         if (!CE->getOperand(i)->isNullValue()) {
 167           isAllNull = false;
 168           break;
 169         }
 170       if (isAllNull)
 171         // This is casting one pointer type to another, always BitCast
 172         return ConstantExpr::getPointerCast(CE->getOperand(0), DestTy);
 173     }
 174   }
 175
 176   // We actually have to do a cast now. Perform the cast according to the
 177   // opcode specified.
 178   switch (opc) {
 179   case Instruction::FPTrunc:
 180   case Instruction::FPExt:
 181     if (const ConstantFP *FPC = dyn_cast<ConstantFP>(V)) {
 182        APFloat Val = FPC->getValueAPF();
 183       Val.convert(DestTy==Type::FloatTy ? APFloat::IEEEsingle :
 184                                           APFloat::IEEEdouble,
 185                   APFloat::rmNearestTiesToEven);
 186       return ConstantFP::get(DestTy, Val);
 187     }
 188     return 0; // Can't fold.
 189   case Instruction::FPToUI:
 190     if (const ConstantFP *FPC = dyn_cast<ConstantFP>(V)) {
 191       APFloat V = FPC->getValueAPF();
 192       bool isDouble = &V.getSemantics()==&APFloat::IEEEdouble;
 193       uint32_t DestBitWidth = cast<IntegerType>(DestTy)->getBitWidth();
 194       APInt Val(APIntOps::RoundDoubleToAPInt(isDouble ? V.convertToDouble() :
 195                                    (double)V.convertToFloat(), DestBitWidth));
 196       return ConstantInt::get(Val);
 197     }
 198     return 0; // Can't fold.
 199   case Instruction::FPToSI:
 200     if (const ConstantFP *FPC = dyn_cast<ConstantFP>(V)) {
 201       APFloat V = FPC->getValueAPF();
 202       bool isDouble = &V.getSemantics()==&APFloat::IEEEdouble;
 203       uint32_t DestBitWidth = cast<IntegerType>(DestTy)->getBitWidth();
 204       APInt Val(APIntOps::RoundDoubleToAPInt(isDouble ? V.convertToDouble() :
 205                                     (double)V.convertToFloat(), DestBitWidth));
 206       return ConstantInt::get(Val);
 207     }
 208     return 0; // Can't fold.
 209   case Instruction::IntToPtr:   //always treated as unsigned
 210     if (V->isNullValue())       // Is it an integral null value?
 211       return ConstantPointerNull::get(cast<PointerType>(DestTy));
 212     return 0;                   // Other pointer types cannot be casted
 213   case Instruction::PtrToInt:   // always treated as unsigned
 214     if (V->isNullValue())       // is it a null pointer value?
 215       return ConstantInt::get(DestTy, 0);
 216     return 0;                   // Other pointer types cannot be casted
 217   case Instruction::UIToFP:
 218     if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 219       if (DestTy==Type::FloatTy)
 220         return ConstantFP::get(DestTy,
 221                             APFloat((float)CI->getValue().roundToDouble()));
 222       else
 223         return ConstantFP::get(DestTy, APFloat(CI->getValue().roundToDouble()));
 224     }
 225     return 0;
 226   case Instruction::SIToFP:
 227     if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 228       double d = CI->getValue().signedRoundToDouble();
 229       if (DestTy==Type::FloatTy)
 230         return ConstantFP::get(DestTy, APFloat((float)d));
 231       else
 232         return ConstantFP::get(DestTy, APFloat(d));
 233     }
 234     return 0;
 235   case Instruction::ZExt:
 236     if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 237       uint32_t BitWidth = cast<IntegerType>(DestTy)->getBitWidth();
 238       APInt Result(CI->getValue());
 239       Result.zext(BitWidth);
 240       return ConstantInt::get(Result);
 241     }
 242     return 0;
 243   case Instruction::SExt:
 244     if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 245       uint32_t BitWidth = cast<IntegerType>(DestTy)->getBitWidth();
 246       APInt Result(CI->getValue());
 247       Result.sext(BitWidth);
 248       return ConstantInt::get(Result);
 249     }
 250     return 0;
 251   case Instruction::Trunc:
 252     if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 253       uint32_t BitWidth = cast<IntegerType>(DestTy)->getBitWidth();
 254       APInt Result(CI->getValue());
 255       Result.trunc(BitWidth);
 256       return ConstantInt::get(Result);
 257     }
 258     return 0;
 259   case Instruction::BitCast:
 260     if (SrcTy == DestTy)
 261       return (Constant*)V; // no-op cast
 262
 263     // Check to see if we are casting a pointer to an aggregate to a pointer to
 264     // the first element.  If so, return the appropriate GEP instruction.
 265     if (const PointerType *PTy = dyn_cast<PointerType>(V->getType()))
 266       if (const PointerType *DPTy = dyn_cast<PointerType>(DestTy)) {
 267         SmallVector<Value*, 8> IdxList;
 268         IdxList.push_back(Constant::getNullValue(Type::Int32Ty));
 269         const Type *ElTy = PTy->getElementType();
 270         while (ElTy != DPTy->getElementType()) {
 271           if (const StructType *STy = dyn_cast<StructType>(ElTy)) {
 272             if (STy->getNumElements() == 0) break;
 273             ElTy = STy->getElementType(0);
 274             IdxList.push_back(Constant::getNullValue(Type::Int32Ty));
 275           } else if (const SequentialType *STy =
 276                      dyn_cast<SequentialType>(ElTy)) {
 277             if (isa<PointerType>(ElTy)) break;  // Can't index into pointers!
 278             ElTy = STy->getElementType();
 279             IdxList.push_back(IdxList[0]);
 280           } else {
 281             break;
 282           }
 283         }
 284
 285         if (ElTy == DPTy->getElementType())
 286           return ConstantExpr::getGetElementPtr(
 287               const_cast<Constant*>(V), &IdxList[0], IdxList.size());
 288       }
 289
 290     // Handle casts from one vector constant to another.  We know that the src
 291     // and dest type have the same size (otherwise its an illegal cast).
 292     if (const VectorType *DestPTy = dyn_cast<VectorType>(DestTy)) {
 293       if (const VectorType *SrcTy = dyn_cast<VectorType>(V->getType())) {
 294         assert(DestPTy->getBitWidth() == SrcTy->getBitWidth() &&
 295                "Not cast between same sized vectors!");
 296         // First, check for null and undef
 297         if (isa<ConstantAggregateZero>(V))
 298           return Constant::getNullValue(DestTy);
 299         if (isa<UndefValue>(V))
 300           return UndefValue::get(DestTy);
 301
 302         if (const ConstantVector *CV = dyn_cast<ConstantVector>(V)) {
 303           // This is a cast from a ConstantVector of one type to a
 304           // ConstantVector of another type.  Check to see if all elements of
 305           // the input are simple.
 306           bool AllSimpleConstants = true;
 307           for (unsigned i = 0, e = CV->getNumOperands(); i != e; ++i) {
 308             if (!isa<ConstantInt>(CV->getOperand(i)) &&
 309                 !isa<ConstantFP>(CV->getOperand(i))) {
 310               AllSimpleConstants = false;
 311               break;
 312             }
 313           }
 314
 315           // If all of the elements are simple constants, we can fold this.
 316           if (AllSimpleConstants)
 317             return CastConstantVector(const_cast<ConstantVector*>(CV), DestPTy);
 318         }
 319       }
 320     }
 321
 322     // Finally, implement bitcast folding now.   The code below doesn't handle
 323     // bitcast right.
 324     if (isa<ConstantPointerNull>(V))  // ptr->ptr cast.
 325       return ConstantPointerNull::get(cast<PointerType>(DestTy));
 326
 327     // Handle integral constant input.
 328     if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 329       if (DestTy->isInteger())
 330         // Integral -> Integral. This is a no-op because the bit widths must
 331         // be the same. Consequently, we just fold to V.
 332         return const_cast<Constant*>(V);
 333
 334       if (DestTy->isFloatingPoint()) {
 335         if (DestTy == Type::FloatTy)
 336           return ConstantFP::get(DestTy, APFloat(CI->getValue().bitsToFloat()));
 337         assert(DestTy == Type::DoubleTy && "Unknown FP type!");
 338         return ConstantFP::get(DestTy, APFloat(CI->getValue().bitsToDouble()));
 339       }
 340       // Otherwise, can't fold this (vector?)
 341       return 0;
 342     }
 343
 344     // Handle ConstantFP input.
 345     if (const ConstantFP *FP = dyn_cast<ConstantFP>(V)) {
 346       // FP -> Integral.
 347       if (DestTy == Type::Int32Ty) {
 348         APInt Val(32, 0);
 349         return ConstantInt::get(Val.floatToBits(FP->
 350                                 getValueAPF().convertToFloat()));
 351       } else {
 352         assert(DestTy == Type::Int64Ty && "only support f32/f64 for now!");
 353         APInt Val(64, 0);
 354         return ConstantInt::get(Val.doubleToBits(FP->
 355                                 getValueAPF().convertToDouble()));
 356       }
 357     }
 358     return 0;
 359   default:
 360     assert(!"Invalid CE CastInst opcode");
 361     break;
 362   }
 363
 364   assert(0 && "Failed to cast constant expression");
 365   return 0;
 366 }
 367
 368 Constant *llvm::ConstantFoldSelectInstruction(const Constant *Cond,
 369                                               const Constant *V1,
 370                                               const Constant *V2) {
 371   if (const ConstantInt *CB = dyn_cast<ConstantInt>(Cond))
 372     return const_cast<Constant*>(CB->getZExtValue() ? V1 : V2);
 373
 374   if (isa<UndefValue>(V1)) return const_cast<Constant*>(V2);
 375   if (isa<UndefValue>(V2)) return const_cast<Constant*>(V1);
 376   if (isa<UndefValue>(Cond)) return const_cast<Constant*>(V1);
 377   if (V1 == V2) return const_cast<Constant*>(V1);
 378   return 0;
 379 }
 380
 381 Constant *llvm::ConstantFoldExtractElementInstruction(const Constant *Val,
 382                                                       const Constant *Idx) {
 383   if (isa<UndefValue>(Val))  // ee(undef, x) -> undef
 384     return UndefValue::get(cast<VectorType>(Val->getType())->getElementType());
 385   if (Val->isNullValue())  // ee(zero, x) -> zero
 386     return Constant::getNullValue(
 387                           cast<VectorType>(Val->getType())->getElementType());
 388
 389   if (const ConstantVector *CVal = dyn_cast<ConstantVector>(Val)) {
 390     if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Idx)) {
 391       return const_cast<Constant*>(CVal->getOperand(CIdx->getZExtValue()));
 392     } else if (isa<UndefValue>(Idx)) {
 393       // ee({w,x,y,z}, undef) -> w (an arbitrary value).
 394       return const_cast<Constant*>(CVal->getOperand(0));
 395     }
 396   }
 397   return 0;
 398 }
 399
 400 Constant *llvm::ConstantFoldInsertElementInstruction(const Constant *Val,
 401                                                      const Constant *Elt,
 402                                                      const Constant *Idx) {
 403   const ConstantInt *CIdx = dyn_cast<ConstantInt>(Idx);
 404   if (!CIdx) return 0;
 405   APInt idxVal = CIdx->getValue();
 406   if (isa<UndefValue>(Val)) {
 407     // Insertion of scalar constant into vector undef
 408     // Optimize away insertion of undef
 409     if (isa<UndefValue>(Elt))
 410       return const_cast<Constant*>(Val);
 411     // Otherwise break the aggregate undef into multiple undefs and do
 412     // the insertion
 413     unsigned numOps =
 414       cast<VectorType>(Val->getType())->getNumElements();
 415     std::vector<Constant*> Ops;
 416     Ops.reserve(numOps);
 417     for (unsigned i = 0; i < numOps; ++i) {
 418       const Constant *Op =
 419         (idxVal == i) ? Elt : UndefValue::get(Elt->getType());
 420       Ops.push_back(const_cast<Constant*>(Op));
 421     }
 422     return ConstantVector::get(Ops);
 423   }
 424   if (isa<ConstantAggregateZero>(Val)) {
 425     // Insertion of scalar constant into vector aggregate zero
 426     // Optimize away insertion of zero
 427     if (Elt->isNullValue())
 428       return const_cast<Constant*>(Val);
 429     // Otherwise break the aggregate zero into multiple zeros and do
 430     // the insertion
 431     unsigned numOps =
 432       cast<VectorType>(Val->getType())->getNumElements();
 433     std::vector<Constant*> Ops;
 434     Ops.reserve(numOps);
 435     for (unsigned i = 0; i < numOps; ++i) {
 436       const Constant *Op =
 437         (idxVal == i) ? Elt : Constant::getNullValue(Elt->getType());
 438       Ops.push_back(const_cast<Constant*>(Op));
 439     }
 440     return ConstantVector::get(Ops);
 441   }
 442   if (const ConstantVector *CVal = dyn_cast<ConstantVector>(Val)) {
 443     // Insertion of scalar constant into vector constant
 444     std::vector<Constant*> Ops;
 445     Ops.reserve(CVal->getNumOperands());
 446     for (unsigned i = 0; i < CVal->getNumOperands(); ++i) {
 447       const Constant *Op =
 448         (idxVal == i) ? Elt : cast<Constant>(CVal->getOperand(i));
 449       Ops.push_back(const_cast<Constant*>(Op));
 450     }
 451     return ConstantVector::get(Ops);
 452   }
 453   return 0;
 454 }
 455
 456 Constant *llvm::ConstantFoldShuffleVectorInstruction(const Constant *V1,
 457                                                      const Constant *V2,
 458                                                      const Constant *Mask) {
 459   // TODO:
 460   return 0;
 461 }
 462
 463 /// EvalVectorOp - Given two vector constants and a function pointer, apply the
 464 /// function pointer to each element pair, producing a new ConstantVector
 465 /// constant.
 466 static Constant *EvalVectorOp(const ConstantVector *V1,
 467                               const ConstantVector *V2,
 468                               Constant *(*FP)(Constant*, Constant*)) {
 469   std::vector<Constant*> Res;
 470   for (unsigned i = 0, e = V1->getNumOperands(); i != e; ++i)
 471     Res.push_back(FP(const_cast<Constant*>(V1->getOperand(i)),
 472                      const_cast<Constant*>(V2->getOperand(i))));
 473   return ConstantVector::get(Res);
 474 }
 475
 476 Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode,
 477                                               const Constant *C1,
 478                                               const Constant *C2) {
 479   // Handle UndefValue up front
 480   if (isa<UndefValue>(C1) || isa<UndefValue>(C2)) {
 481     switch (Opcode) {
 482     case Instruction::Add:
 483     case Instruction::Sub:
 484     case Instruction::Xor:
 485       return UndefValue::get(C1->getType());
 486     case Instruction::Mul:
 487     case Instruction::And:
 488       return Constant::getNullValue(C1->getType());
 489     case Instruction::UDiv:
 490     case Instruction::SDiv:
 491     case Instruction::FDiv:
 492     case Instruction::URem:
 493     case Instruction::SRem:
 494     case Instruction::FRem:
 495       if (!isa<UndefValue>(C2))                    // undef / X -> 0
 496         return Constant::getNullValue(C1->getType());
 497       return const_cast<Constant*>(C2);            // X / undef -> undef
 498     case Instruction::Or:                          // X | undef -> -1
 499       if (const VectorType *PTy = dyn_cast<VectorType>(C1->getType()))
 500         return ConstantVector::getAllOnesValue(PTy);
 501       return ConstantInt::getAllOnesValue(C1->getType());
 502     case Instruction::LShr:
 503       if (isa<UndefValue>(C2) && isa<UndefValue>(C1))
 504         return const_cast<Constant*>(C1);           // undef lshr undef -> undef
 505       return Constant::getNullValue(C1->getType()); // X lshr undef -> 0
 506                                                     // undef lshr X -> 0
 507     case Instruction::AShr:
 508       if (!isa<UndefValue>(C2))
 509         return const_cast<Constant*>(C1);           // undef ashr X --> undef
 510       else if (isa<UndefValue>(C1))
 511         return const_cast<Constant*>(C1);           // undef ashr undef -> undef
 512       else
 513         return const_cast<Constant*>(C1);           // X ashr undef --> X
 514     case Instruction::Shl:
 515       // undef << X -> 0   or   X << undef -> 0
 516       return Constant::getNullValue(C1->getType());
 517     }
 518   }
 519
 520   if (const ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1)) {
 521     if (isa<ConstantExpr>(C2)) {
 522       // There are many possible foldings we could do here.  We should probably
 523       // at least fold add of a pointer with an integer into the appropriate
 524       // getelementptr.  This will improve alias analysis a bit.
 525     } else {
 526       // Just implement a couple of simple identities.
 527       switch (Opcode) {
 528       case Instruction::Add:
 529         if (C2->isNullValue()) return const_cast<Constant*>(C1);  // X + 0 == X
 530         break;
 531       case Instruction::Sub:
 532         if (C2->isNullValue()) return const_cast<Constant*>(C1);  // X - 0 == X
 533         break;
 534       case Instruction::Mul:
 535         if (C2->isNullValue()) return const_cast<Constant*>(C2);  // X * 0 == 0
 536         if (const ConstantInt *CI = dyn_cast<ConstantInt>(C2))
 537           if (CI->equalsInt(1))
 538             return const_cast<Constant*>(C1);                     // X * 1 == X
 539         break;
 540       case Instruction::UDiv:
 541       case Instruction::SDiv:
 542         if (const ConstantInt *CI = dyn_cast<ConstantInt>(C2))
 543           if (CI->equalsInt(1))
 544             return const_cast<Constant*>(C1);                     // X / 1 == X
 545         break;
 546       case Instruction::URem:
 547       case Instruction::SRem:
 548         if (const ConstantInt *CI = dyn_cast<ConstantInt>(C2))
 549           if (CI->equalsInt(1))
 550             return Constant::getNullValue(CI->getType());         // X % 1 == 0
 551         break;
 552       case Instruction::And:
 553         if (const ConstantInt *CI = dyn_cast<ConstantInt>(C2)) {
 554           if (CI->isZero()) return const_cast<Constant*>(C2);     // X & 0 == 0
 555           if (CI->isAllOnesValue())
 556             return const_cast<Constant*>(C1);                     // X & -1 == X
 557
 558           // (zext i32 to i64) & 4294967295 -> (zext i32 to i64)
 559           if (CE1->getOpcode() == Instruction::ZExt) {
 560             APInt PossiblySetBits
 561               = cast<IntegerType>(CE1->getOperand(0)->getType())->getMask();
 562             PossiblySetBits.zext(C1->getType()->getPrimitiveSizeInBits());
 563             if ((PossiblySetBits & CI->getValue()) == PossiblySetBits)
 564               return const_cast<Constant*>(C1);
 565           }
 566         }
 567         if (CE1->isCast() && isa<GlobalValue>(CE1->getOperand(0))) {
 568           GlobalValue *CPR = cast<GlobalValue>(CE1->getOperand(0));
 569
 570           // Functions are at least 4-byte aligned.  If and'ing the address of a
 571           // function with a constant < 4, fold it to zero.
 572           if (const ConstantInt *CI = dyn_cast<ConstantInt>(C2))
 573             if (CI->getValue().ult(APInt(CI->getType()->getBitWidth(),4)) &&
 574                 isa<Function>(CPR))
 575               return Constant::getNullValue(CI->getType());
 576         }
 577         break;
 578       case Instruction::Or:
 579         if (C2->isNullValue()) return const_cast<Constant*>(C1);  // X | 0 == X
 580         if (const ConstantInt *CI = dyn_cast<ConstantInt>(C2))
 581           if (CI->isAllOnesValue())
 582             return const_cast<Constant*>(C2);  // X | -1 == -1
 583         break;
 584       case Instruction::Xor:
 585         if (C2->isNullValue()) return const_cast<Constant*>(C1);  // X ^ 0 == X
 586         break;
 587       case Instruction::AShr:
 588         // ashr (zext C to Ty), C2 -> lshr (zext C, CSA), C2
 589         if (CE1->getOpcode() == Instruction::ZExt)  // Top bits known zero.
 590           return ConstantExpr::getLShr(const_cast<Constant*>(C1),
 591                                        const_cast<Constant*>(C2));
 592         break;
 593       }
 594     }
 595   } else if (isa<ConstantExpr>(C2)) {
 596     // If C2 is a constant expr and C1 isn't, flop them around and fold the
 597     // other way if possible.
 598     switch (Opcode) {
 599     case Instruction::Add:
 600     case Instruction::Mul:
 601     case Instruction::And:
 602     case Instruction::Or:
 603     case Instruction::Xor:
 604       // No change of opcode required.
 605       return ConstantFoldBinaryInstruction(Opcode, C2, C1);
 606
 607     case Instruction::Shl:
 608     case Instruction::LShr:
 609     case Instruction::AShr:
 610     case Instruction::Sub:
 611     case Instruction::SDiv:
 612     case Instruction::UDiv:
 613     case Instruction::FDiv:
 614     case Instruction::URem:
 615     case Instruction::SRem:
 616     case Instruction::FRem:
 617     default:  // These instructions cannot be flopped around.
 618       return 0;
 619     }
 620   }
 621
 622   // At this point we know neither constant is an UndefValue nor a ConstantExpr
 623   // so look at directly computing the value.
 624   if (const ConstantInt *CI1 = dyn_cast<ConstantInt>(C1)) {
 625     if (const ConstantInt *CI2 = dyn_cast<ConstantInt>(C2)) {
 626       using namespace APIntOps;
 627       APInt C1V = CI1->getValue();
 628       APInt C2V = CI2->getValue();
 629       switch (Opcode) {
 630       default:
 631         break;
 632       case Instruction::Add:
 633         return ConstantInt::get(C1V + C2V);
 634       case Instruction::Sub:
 635         return ConstantInt::get(C1V - C2V);
 636       case Instruction::Mul:
 637         return ConstantInt::get(C1V * C2V);
 638       case Instruction::UDiv:
 639         if (CI2->isNullValue())
 640           return 0;        // X / 0 -> can't fold
 641         return ConstantInt::get(C1V.udiv(C2V));
 642       case Instruction::SDiv:
 643         if (CI2->isNullValue())
 644           return 0;        // X / 0 -> can't fold
 645         if (C2V.isAllOnesValue() && C1V.isMinSignedValue())
 646           return 0;        // MIN_INT / -1 -> overflow
 647         return ConstantInt::get(C1V.sdiv(C2V));
 648       case Instruction::URem:
 649         if (C2->isNullValue())
 650           return 0;        // X / 0 -> can't fold
 651         return ConstantInt::get(C1V.urem(C2V));
 652       case Instruction::SRem:
 653         if (CI2->isNullValue())
 654           return 0;        // X % 0 -> can't fold
 655         if (C2V.isAllOnesValue() && C1V.isMinSignedValue())
 656           return 0;        // MIN_INT % -1 -> overflow
 657         return ConstantInt::get(C1V.srem(C2V));
 658       case Instruction::And:
 659         return ConstantInt::get(C1V & C2V);
 660       case Instruction::Or:
 661         return ConstantInt::get(C1V | C2V);
 662       case Instruction::Xor:
 663         return ConstantInt::get(C1V ^ C2V);
 664       case Instruction::Shl:
 665         if (uint32_t shiftAmt = C2V.getZExtValue())
 666           if (shiftAmt < C1V.getBitWidth())
 667             return ConstantInt::get(C1V.shl(shiftAmt));
 668           else
 669             return UndefValue::get(C1->getType()); // too big shift is undef
 670         return const_cast<ConstantInt*>(CI1); // Zero shift is identity
 671       case Instruction::LShr:
 672         if (uint32_t shiftAmt = C2V.getZExtValue())
 673           if (shiftAmt < C1V.getBitWidth())
 674             return ConstantInt::get(C1V.lshr(shiftAmt));
 675           else
 676             return UndefValue::get(C1->getType()); // too big shift is undef
 677         return const_cast<ConstantInt*>(CI1); // Zero shift is identity
 678       case Instruction::AShr:
 679         if (uint32_t shiftAmt = C2V.getZExtValue())
 680           if (shiftAmt < C1V.getBitWidth())
 681             return ConstantInt::get(C1V.ashr(shiftAmt));
 682           else
 683             return UndefValue::get(C1->getType()); // too big shift is undef
 684         return const_cast<ConstantInt*>(CI1); // Zero shift is identity
 685       }
 686     }
 687   } else if (const ConstantFP *CFP1 = dyn_cast<ConstantFP>(C1)) {
 688     if (const ConstantFP *CFP2 = dyn_cast<ConstantFP>(C2)) {
 689       APFloat C1V = CFP1->getValueAPF();
 690       APFloat C2V = CFP2->getValueAPF();
 691       APFloat C3V = C1V;  // copy for modification
 692       bool isDouble = CFP1->getType()==Type::DoubleTy;
 693       switch (Opcode) {
 694       default:
 695         break;
 696       case Instruction::Add:
 697         (void)C3V.add(C2V, APFloat::rmNearestTiesToEven);
 698         return ConstantFP::get(CFP1->getType(), C3V);
 699       case Instruction::Sub:
 700         (void)C3V.subtract(C2V, APFloat::rmNearestTiesToEven);
 701         return ConstantFP::get(CFP1->getType(), C3V);
 702       case Instruction::Mul:
 703         (void)C3V.multiply(C2V, APFloat::rmNearestTiesToEven);
 704         return ConstantFP::get(CFP1->getType(), C3V);
 705       case Instruction::FDiv:
 706         // FIXME better to look at the return code
 707         if (C2V.isZero())
 708           if (C1V.isZero())
 709             // IEEE 754, Section 7.1, #4
 710             return ConstantFP::get(CFP1->getType(), isDouble ?
 711                             APFloat(std::numeric_limits<double>::quiet_NaN()) :
 712                             APFloat(std::numeric_limits<float>::quiet_NaN()));
 713           else if (C2V.isNegZero() || C1V.isNegative())
 714             // IEEE 754, Section 7.2, negative infinity case
 715             return ConstantFP::get(CFP1->getType(), isDouble ?
 716                             APFloat(-std::numeric_limits<double>::infinity()) :
 717                             APFloat(-std::numeric_limits<float>::infinity()));
 718           else
 719             // IEEE 754, Section 7.2, positive infinity case
 720             return ConstantFP::get(CFP1->getType(), isDouble ?
 721                             APFloat(std::numeric_limits<double>::infinity()) :
 722                             APFloat(std::numeric_limits<float>::infinity()));
 723         (void)C3V.divide(C2V, APFloat::rmNearestTiesToEven);
 724         return ConstantFP::get(CFP1->getType(), C3V);
 725       case Instruction::FRem:
 726         if (C2V.isZero())
 727           // IEEE 754, Section 7.1, #5
 728           return ConstantFP::get(CFP1->getType(), isDouble ?
 729                             APFloat(std::numeric_limits<double>::quiet_NaN()) :
 730                             APFloat(std::numeric_limits<float>::quiet_NaN()));
 731         (void)C3V.mod(C2V, APFloat::rmNearestTiesToEven);
 732         return ConstantFP::get(CFP1->getType(), C3V);
 733       }
 734     }
 735   } else if (const ConstantVector *CP1 = dyn_cast<ConstantVector>(C1)) {
 736     if (const ConstantVector *CP2 = dyn_cast<ConstantVector>(C2)) {
 737       switch (Opcode) {
 738         default:
 739           break;
 740         case Instruction::Add:
 741           return EvalVectorOp(CP1, CP2, ConstantExpr::getAdd);
 742         case Instruction::Sub:
 743           return EvalVectorOp(CP1, CP2, ConstantExpr::getSub);
 744         case Instruction::Mul:
 745           return EvalVectorOp(CP1, CP2, ConstantExpr::getMul);
 746         case Instruction::UDiv:
 747           return EvalVectorOp(CP1, CP2, ConstantExpr::getUDiv);
 748         case Instruction::SDiv:
 749           return EvalVectorOp(CP1, CP2, ConstantExpr::getSDiv);
 750         case Instruction::FDiv:
 751           return EvalVectorOp(CP1, CP2, ConstantExpr::getFDiv);
 752         case Instruction::URem:
 753           return EvalVectorOp(CP1, CP2, ConstantExpr::getURem);
 754         case Instruction::SRem:
 755           return EvalVectorOp(CP1, CP2, ConstantExpr::getSRem);
 756         case Instruction::FRem:
 757           return EvalVectorOp(CP1, CP2, ConstantExpr::getFRem);
 758         case Instruction::And:
 759           return EvalVectorOp(CP1, CP2, ConstantExpr::getAnd);
 760         case Instruction::Or:
 761           return EvalVectorOp(CP1, CP2, ConstantExpr::getOr);
 762         case Instruction::Xor:
 763           return EvalVectorOp(CP1, CP2, ConstantExpr::getXor);
 764       }
 765     }
 766   }
 767
 768   // We don't know how to fold this
 769   return 0;
 770 }
 771
 772 /// isZeroSizedType - This type is zero sized if its an array or structure of
 773 /// zero sized types.  The only leaf zero sized type is an empty structure.
 774 static bool isMaybeZeroSizedType(const Type *Ty) {
 775   if (isa<OpaqueType>(Ty)) return true;  // Can't say.
 776   if (const StructType *STy = dyn_cast<StructType>(Ty)) {
 777
 778     // If all of elements have zero size, this does too.
 779     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
 780       if (!isMaybeZeroSizedType(STy->getElementType(i))) return false;
 781     return true;
 782
 783   } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
 784     return isMaybeZeroSizedType(ATy->getElementType());
 785   }
 786   return false;
 787 }
 788
 789 /// IdxCompare - Compare the two constants as though they were getelementptr
 790 /// indices.  This allows coersion of the types to be the same thing.
 791 ///
 792 /// If the two constants are the "same" (after coersion), return 0.  If the
 793 /// first is less than the second, return -1, if the second is less than the
 794 /// first, return 1.  If the constants are not integral, return -2.
 795 ///
 796 static int IdxCompare(Constant *C1, Constant *C2, const Type *ElTy) {
 797   if (C1 == C2) return 0;
 798
 799   // Ok, we found a different index.  If they are not ConstantInt, we can't do
 800   // anything with them.
 801   if (!isa<ConstantInt>(C1) || !isa<ConstantInt>(C2))
 802     return -2; // don't know!
 803
 804   // Ok, we have two differing integer indices.  Sign extend them to be the same
 805   // type.  Long is always big enough, so we use it.
 806   if (C1->getType() != Type::Int64Ty)
 807     C1 = ConstantExpr::getSExt(C1, Type::Int64Ty);
 808
 809   if (C2->getType() != Type::Int64Ty)
 810     C2 = ConstantExpr::getSExt(C2, Type::Int64Ty);
 811
 812   if (C1 == C2) return 0;  // They are equal
 813
 814   // If the type being indexed over is really just a zero sized type, there is
 815   // no pointer difference being made here.
 816   if (isMaybeZeroSizedType(ElTy))
 817     return -2; // dunno.
 818
 819   // If they are really different, now that they are the same type, then we
 820   // found a difference!
 821   if (cast<ConstantInt>(C1)->getSExtValue() <
 822       cast<ConstantInt>(C2)->getSExtValue())
 823     return -1;
 824   else
 825     return 1;
 826 }
 827
 828 /// evaluateFCmpRelation - This function determines if there is anything we can
 829 /// decide about the two constants provided.  This doesn't need to handle simple
 830 /// things like ConstantFP comparisons, but should instead handle ConstantExprs.
 831 /// If we can determine that the two constants have a particular relation to
 832 /// each other, we should return the corresponding FCmpInst predicate,
 833 /// otherwise return FCmpInst::BAD_FCMP_PREDICATE. This is used below in
 834 /// ConstantFoldCompareInstruction.
 835 ///
 836 /// To simplify this code we canonicalize the relation so that the first
 837 /// operand is always the most "complex" of the two.  We consider ConstantFP
 838 /// to be the simplest, and ConstantExprs to be the most complex.
 839 static FCmpInst::Predicate evaluateFCmpRelation(const Constant *V1,
 840                                                 const Constant *V2) {
 841   assert(V1->getType() == V2->getType() &&
 842          "Cannot compare values of different types!");
 843   // Handle degenerate case quickly
 844   if (V1 == V2) return FCmpInst::FCMP_OEQ;
 845
 846   if (!isa<ConstantExpr>(V1)) {
 847     if (!isa<ConstantExpr>(V2)) {
 848       // We distilled thisUse the standard constant folder for a few cases
 849       ConstantInt *R = 0;
 850       Constant *C1 = const_cast<Constant*>(V1);
 851       Constant *C2 = const_cast<Constant*>(V2);
 852       R = dyn_cast<ConstantInt>(
 853                              ConstantExpr::getFCmp(FCmpInst::FCMP_OEQ, C1, C2));
 854       if (R && !R->isZero())
 855         return FCmpInst::FCMP_OEQ;
 856       R = dyn_cast<ConstantInt>(
 857                              ConstantExpr::getFCmp(FCmpInst::FCMP_OLT, C1, C2));
 858       if (R && !R->isZero())
 859         return FCmpInst::FCMP_OLT;
 860       R = dyn_cast<ConstantInt>(
 861                              ConstantExpr::getFCmp(FCmpInst::FCMP_OGT, C1, C2));
 862       if (R && !R->isZero())
 863         return FCmpInst::FCMP_OGT;
 864
 865       // Nothing more we can do
 866       return FCmpInst::BAD_FCMP_PREDICATE;
 867     }
 868
 869     // If the first operand is simple and second is ConstantExpr, swap operands.
 870     FCmpInst::Predicate SwappedRelation = evaluateFCmpRelation(V2, V1);
 871     if (SwappedRelation != FCmpInst::BAD_FCMP_PREDICATE)
 872       return FCmpInst::getSwappedPredicate(SwappedRelation);
 873   } else {
 874     // Ok, the LHS is known to be a constantexpr.  The RHS can be any of a
 875     // constantexpr or a simple constant.
 876     const ConstantExpr *CE1 = cast<ConstantExpr>(V1);
 877     switch (CE1->getOpcode()) {
 878     case Instruction::FPTrunc:
 879     case Instruction::FPExt:
 880     case Instruction::UIToFP:
 881     case Instruction::SIToFP:
 882       // We might be able to do something with these but we don't right now.
 883       break;
 884     default:
 885       break;
 886     }
 887   }
 888   // There are MANY other foldings that we could perform here.  They will
 889   // probably be added on demand, as they seem needed.
 890   return FCmpInst::BAD_FCMP_PREDICATE;
 891 }
 892
 893 /// evaluateICmpRelation - This function determines if there is anything we can
 894 /// decide about the two constants provided.  This doesn't need to handle simple
 895 /// things like integer comparisons, but should instead handle ConstantExprs
 896 /// and GlobalValues.  If we can determine that the two constants have a
 897 /// particular relation to each other, we should return the corresponding ICmp
 898 /// predicate, otherwise return ICmpInst::BAD_ICMP_PREDICATE.
 899 ///
 900 /// To simplify this code we canonicalize the relation so that the first
 901 /// operand is always the most "complex" of the two.  We consider simple
 902 /// constants (like ConstantInt) to be the simplest, followed by
 903 /// GlobalValues, followed by ConstantExpr's (the most complex).
 904 ///
 905 static ICmpInst::Predicate evaluateICmpRelation(const Constant *V1,
 906                                                 const Constant *V2,
 907                                                 bool isSigned) {
 908   assert(V1->getType() == V2->getType() &&
 909          "Cannot compare different types of values!");
 910   if (V1 == V2) return ICmpInst::ICMP_EQ;
 911
 912   if (!isa<ConstantExpr>(V1) && !isa<GlobalValue>(V1)) {
 913     if (!isa<GlobalValue>(V2) && !isa<ConstantExpr>(V2)) {
 914       // We distilled this down to a simple case, use the standard constant
 915       // folder.
 916       ConstantInt *R = 0;
 917       Constant *C1 = const_cast<Constant*>(V1);
 918       Constant *C2 = const_cast<Constant*>(V2);
 919       ICmpInst::Predicate pred = ICmpInst::ICMP_EQ;
 920       R = dyn_cast<ConstantInt>(ConstantExpr::getICmp(pred, C1, C2));
 921       if (R && !R->isZero())
 922         return pred;
 923       pred = isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
 924       R = dyn_cast<ConstantInt>(ConstantExpr::getICmp(pred, C1, C2));
 925       if (R && !R->isZero())
 926         return pred;
 927       pred = isSigned ?  ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
 928       R = dyn_cast<ConstantInt>(ConstantExpr::getICmp(pred, C1, C2));
 929       if (R && !R->isZero())
 930         return pred;
 931
 932       // If we couldn't figure it out, bail.
 933       return ICmpInst::BAD_ICMP_PREDICATE;
 934     }
 935
 936     // If the first operand is simple, swap operands.
 937     ICmpInst::Predicate SwappedRelation =
 938       evaluateICmpRelation(V2, V1, isSigned);
 939     if (SwappedRelation != ICmpInst::BAD_ICMP_PREDICATE)
 940       return ICmpInst::getSwappedPredicate(SwappedRelation);
 941
 942   } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(V1)) {
 943     if (isa<ConstantExpr>(V2)) {  // Swap as necessary.
 944       ICmpInst::Predicate SwappedRelation =
 945         evaluateICmpRelation(V2, V1, isSigned);
 946       if (SwappedRelation != ICmpInst::BAD_ICMP_PREDICATE)
 947         return ICmpInst::getSwappedPredicate(SwappedRelation);
 948       else
 949         return ICmpInst::BAD_ICMP_PREDICATE;
 950     }
 951
 952     // Now we know that the RHS is a GlobalValue or simple constant,
 953     // which (since the types must match) means that it's a ConstantPointerNull.
 954     if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) {
 955       // Don't try to decide equality of aliases.
 956       if (!isa<GlobalAlias>(CPR1) && !isa<GlobalAlias>(CPR2))
 957         if (!CPR1->hasExternalWeakLinkage() || !CPR2->hasExternalWeakLinkage())
 958           return ICmpInst::ICMP_NE;
 959     } else {
 960       assert(isa<ConstantPointerNull>(V2) && "Canonicalization guarantee!");
 961       // GlobalVals can never be null.  Don't try to evaluate aliases.
 962       if (!CPR1->hasExternalWeakLinkage() && !isa<GlobalAlias>(CPR1))
 963         return ICmpInst::ICMP_NE;
 964     }
 965   } else {
 966     // Ok, the LHS is known to be a constantexpr.  The RHS can be any of a
 967     // constantexpr, a CPR, or a simple constant.
 968     const ConstantExpr *CE1 = cast<ConstantExpr>(V1);
 969     const Constant *CE1Op0 = CE1->getOperand(0);
 970
 971     switch (CE1->getOpcode()) {
 972     case Instruction::Trunc:
 973     case Instruction::FPTrunc:
 974     case Instruction::FPExt:
 975     case Instruction::FPToUI:
 976     case Instruction::FPToSI:
 977       break; // We can't evaluate floating point casts or truncations.
 978
 979     case Instruction::UIToFP:
 980     case Instruction::SIToFP:
 981     case Instruction::IntToPtr:
 982     case Instruction::BitCast:
 983     case Instruction::ZExt:
 984     case Instruction::SExt:
 985     case Instruction::PtrToInt:
 986       // If the cast is not actually changing bits, and the second operand is a
 987       // null pointer, do the comparison with the pre-casted value.
 988       if (V2->isNullValue() &&
 989           (isa<PointerType>(CE1->getType()) || CE1->getType()->isInteger())) {
 990         bool sgnd = CE1->getOpcode() == Instruction::ZExt ? false :
 991           (CE1->getOpcode() == Instruction::SExt ? true :
 992            (CE1->getOpcode() == Instruction::PtrToInt ? false : isSigned));
 993         return evaluateICmpRelation(
 994             CE1Op0, Constant::getNullValue(CE1Op0->getType()), sgnd);
 995       }
 996
 997       // If the dest type is a pointer type, and the RHS is a constantexpr cast
 998       // from the same type as the src of the LHS, evaluate the inputs.  This is
 999       // important for things like "icmp eq (cast 4 to int*), (cast 5 to int*)",
1000       // which happens a lot in compilers with tagged integers.
1001       if (const ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2))
1002         if (CE2->isCast() && isa<PointerType>(CE1->getType()) &&
1003             CE1->getOperand(0)->getType() == CE2->getOperand(0)->getType() &&
1004             CE1->getOperand(0)->getType()->isInteger()) {
1005           bool sgnd = CE1->getOpcode() == Instruction::ZExt ? false :
1006             (CE1->getOpcode() == Instruction::SExt ? true :
1007              (CE1->getOpcode() == Instruction::PtrToInt ? false : isSigned));
1008           return evaluateICmpRelation(CE1->getOperand(0), CE2->getOperand(0),
1009               sgnd);
1010         }
1011       break;
1012
1013     case Instruction::GetElementPtr:
1014       // Ok, since this is a getelementptr, we know that the constant has a
1015       // pointer type.  Check the various cases.
1016       if (isa<ConstantPointerNull>(V2)) {
1017         // If we are comparing a GEP to a null pointer, check to see if the base
1018         // of the GEP equals the null pointer.
1019         if (const GlobalValue *GV = dyn_cast<GlobalValue>(CE1Op0)) {
1020           if (GV->hasExternalWeakLinkage())
1021             // Weak linkage GVals could be zero or not. We're comparing that
1022             // to null pointer so its greater-or-equal
1023             return isSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE;
1024           else
1025             // If its not weak linkage, the GVal must have a non-zero address
1026             // so the result is greater-than
1027             return isSigned ? ICmpInst::ICMP_SGT :  ICmpInst::ICMP_UGT;
1028         } else if (isa<ConstantPointerNull>(CE1Op0)) {
1029           // If we are indexing from a null pointer, check to see if we have any
1030           // non-zero indices.
1031           for (unsigned i = 1, e = CE1->getNumOperands(); i != e; ++i)
1032             if (!CE1->getOperand(i)->isNullValue())
1033               // Offsetting from null, must not be equal.
1034               return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
1035           // Only zero indexes from null, must still be zero.
1036           return ICmpInst::ICMP_EQ;
1037         }
1038         // Otherwise, we can't really say if the first operand is null or not.
1039       } else if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) {
1040         if (isa<ConstantPointerNull>(CE1Op0)) {
1041           if (CPR2->hasExternalWeakLinkage())
1042             // Weak linkage GVals could be zero or not. We're comparing it to
1043             // a null pointer, so its less-or-equal
1044             return isSigned ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
1045           else
1046             // If its not weak linkage, the GVal must have a non-zero address
1047             // so the result is less-than
1048             return isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1049         } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(CE1Op0)) {
1050           if (CPR1 == CPR2) {
1051             // If this is a getelementptr of the same global, then it must be
1052             // different.  Because the types must match, the getelementptr could
1053             // only have at most one index, and because we fold getelementptr's
1054             // with a single zero index, it must be nonzero.
1055             assert(CE1->getNumOperands() == 2 &&
1056                    !CE1->getOperand(1)->isNullValue() &&
1057                    "Suprising getelementptr!");
1058             return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
1059           } else {
1060             // If they are different globals, we don't know what the value is,
1061             // but they can't be equal.
1062             return ICmpInst::ICMP_NE;
1063           }
1064         }
1065       } else {
1066         const ConstantExpr *CE2 = cast<ConstantExpr>(V2);
1067         const Constant *CE2Op0 = CE2->getOperand(0);
1068
1069         // There are MANY other foldings that we could perform here.  They will
1070         // probably be added on demand, as they seem needed.
1071         switch (CE2->getOpcode()) {
1072         default: break;
1073         case Instruction::GetElementPtr:
1074           // By far the most common case to handle is when the base pointers are
1075           // obviously to the same or different globals.
1076           if (isa<GlobalValue>(CE1Op0) && isa<GlobalValue>(CE2Op0)) {
1077             if (CE1Op0 != CE2Op0) // Don't know relative ordering, but not equal
1078               return ICmpInst::ICMP_NE;
1079             // Ok, we know that both getelementptr instructions are based on the
1080             // same global.  From this, we can precisely determine the relative
1081             // ordering of the resultant pointers.
1082             unsigned i = 1;
1083
1084             // Compare all of the operands the GEP's have in common.
1085             gep_type_iterator GTI = gep_type_begin(CE1);
1086             for (;i != CE1->getNumOperands() && i != CE2->getNumOperands();
1087                  ++i, ++GTI)
1088               switch (IdxCompare(CE1->getOperand(i), CE2->getOperand(i),
1089                                  GTI.getIndexedType())) {
1090               case -1: return isSigned ? ICmpInst::ICMP_SLT:ICmpInst::ICMP_ULT;
1091               case 1:  return isSigned ? ICmpInst::ICMP_SGT:ICmpInst::ICMP_UGT;
1092               case -2: return ICmpInst::BAD_ICMP_PREDICATE;
1093               }
1094
1095             // Ok, we ran out of things they have in common.  If any leftovers
1096             // are non-zero then we have a difference, otherwise we are equal.
1097             for (; i < CE1->getNumOperands(); ++i)
1098               if (!CE1->getOperand(i)->isNullValue())
1099                 if (isa<ConstantInt>(CE1->getOperand(i)))
1100                   return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
1101                 else
1102                   return ICmpInst::BAD_ICMP_PREDICATE; // Might be equal.
1103
1104             for (; i < CE2->getNumOperands(); ++i)
1105               if (!CE2->getOperand(i)->isNullValue())
1106                 if (isa<ConstantInt>(CE2->getOperand(i)))
1107                   return isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1108                 else
1109                   return ICmpInst::BAD_ICMP_PREDICATE; // Might be equal.
1110             return ICmpInst::ICMP_EQ;
1111           }
1112         }
1113       }
1114     default:
1115       break;
1116     }
1117   }
1118
1119   return ICmpInst::BAD_ICMP_PREDICATE;
1120 }
1121
1122 Constant *llvm::ConstantFoldCompareInstruction(unsigned short pred,
1123                                                const Constant *C1,
1124                                                const Constant *C2) {
1125
1126   // Handle some degenerate cases first
1127   if (isa<UndefValue>(C1) || isa<UndefValue>(C2))
1128     return UndefValue::get(Type::Int1Ty);
1129
1130   // icmp eq/ne(null,GV) -> false/true
1131   if (C1->isNullValue()) {
1132     if (const GlobalValue *GV = dyn_cast<GlobalValue>(C2))
1133       if (!GV->hasExternalWeakLinkage()) // External weak GV can be null
1134         if (pred == ICmpInst::ICMP_EQ)
1135           return ConstantInt::getFalse();
1136         else if (pred == ICmpInst::ICMP_NE)
1137           return ConstantInt::getTrue();
1138   // icmp eq/ne(GV,null) -> false/true
1139   } else if (C2->isNullValue()) {
1140     if (const GlobalValue *GV = dyn_cast<GlobalValue>(C1))
1141       if (!GV->hasExternalWeakLinkage()) // External weak GV can be null
1142         if (pred == ICmpInst::ICMP_EQ)
1143           return ConstantInt::getFalse();
1144         else if (pred == ICmpInst::ICMP_NE)
1145           return ConstantInt::getTrue();
1146   }
1147
1148   if (isa<ConstantInt>(C1) && isa<ConstantInt>(C2)) {
1149     APInt V1 = cast<ConstantInt>(C1)->getValue();
1150     APInt V2 = cast<ConstantInt>(C2)->getValue();
1151     switch (pred) {
1152     default: assert(0 && "Invalid ICmp Predicate"); return 0;
1153     case ICmpInst::ICMP_EQ: return ConstantInt::get(Type::Int1Ty, V1 == V2);
1154     case ICmpInst::ICMP_NE: return ConstantInt::get(Type::Int1Ty, V1 != V2);
1155     case ICmpInst::ICMP_SLT:return ConstantInt::get(Type::Int1Ty, V1.slt(V2));
1156     case ICmpInst::ICMP_SGT:return ConstantInt::get(Type::Int1Ty, V1.sgt(V2));
1157     case ICmpInst::ICMP_SLE:return ConstantInt::get(Type::Int1Ty, V1.sle(V2));
1158     case ICmpInst::ICMP_SGE:return ConstantInt::get(Type::Int1Ty, V1.sge(V2));
1159     case ICmpInst::ICMP_ULT:return ConstantInt::get(Type::Int1Ty, V1.ult(V2));
1160     case ICmpInst::ICMP_UGT:return ConstantInt::get(Type::Int1Ty, V1.ugt(V2));
1161     case ICmpInst::ICMP_ULE:return ConstantInt::get(Type::Int1Ty, V1.ule(V2));
1162     case ICmpInst::ICMP_UGE:return ConstantInt::get(Type::Int1Ty, V1.uge(V2));
1163     }
1164   } else if (isa<ConstantFP>(C1) && isa<ConstantFP>(C2)) {
1165     APFloat C1V = cast<ConstantFP>(C1)->getValueAPF();
1166     APFloat C2V = cast<ConstantFP>(C2)->getValueAPF();
1167     APFloat::cmpResult R = C1V.compare(C2V);
1168     switch (pred) {
1169     default: assert(0 && "Invalid FCmp Predicate"); return 0;
1170     case FCmpInst::FCMP_FALSE: return ConstantInt::getFalse();
1171     case FCmpInst::FCMP_TRUE:  return ConstantInt::getTrue();
1172     case FCmpInst::FCMP_UNO:
1173       return ConstantInt::get(Type::Int1Ty, R==APFloat::cmpUnordered);
1174     case FCmpInst::FCMP_ORD:
1175       return ConstantInt::get(Type::Int1Ty, R!=APFloat::cmpUnordered);
1176     case FCmpInst::FCMP_UEQ:
1177       return ConstantInt::get(Type::Int1Ty, R==APFloat::cmpUnordered ||
1178                                             R==APFloat::cmpEqual);
1179     case FCmpInst::FCMP_OEQ:
1180       return ConstantInt::get(Type::Int1Ty, R==APFloat::cmpEqual);
1181     case FCmpInst::FCMP_UNE:
1182       return ConstantInt::get(Type::Int1Ty, R!=APFloat::cmpEqual);
1183     case FCmpInst::FCMP_ONE:
1184       return ConstantInt::get(Type::Int1Ty, R==APFloat::cmpLessThan ||
1185                                             R==APFloat::cmpGreaterThan);
1186     case FCmpInst::FCMP_ULT:
1187       return ConstantInt::get(Type::Int1Ty, R==APFloat::cmpUnordered ||
1188                                             R==APFloat::cmpLessThan);
1189     case FCmpInst::FCMP_OLT:
1190       return ConstantInt::get(Type::Int1Ty, R==APFloat::cmpLessThan);
1191     case FCmpInst::FCMP_UGT:
1192       return ConstantInt::get(Type::Int1Ty, R==APFloat::cmpUnordered ||
1193                                             R==APFloat::cmpGreaterThan);
1194     case FCmpInst::FCMP_OGT:
1195       return ConstantInt::get(Type::Int1Ty, R==APFloat::cmpGreaterThan);
1196     case FCmpInst::FCMP_ULE:
1197       return ConstantInt::get(Type::Int1Ty, R!=APFloat::cmpGreaterThan);
1198     case FCmpInst::FCMP_OLE:
1199       return ConstantInt::get(Type::Int1Ty, R==APFloat::cmpLessThan ||
1200                                             R==APFloat::cmpEqual);
1201     case FCmpInst::FCMP_UGE:
1202       return ConstantInt::get(Type::Int1Ty, R!=APFloat::cmpLessThan);
1203     case FCmpInst::FCMP_OGE:
1204       return ConstantInt::get(Type::Int1Ty, R==APFloat::cmpGreaterThan ||
1205                                             R==APFloat::cmpEqual);
1206     }
1207   } else if (const ConstantVector *CP1 = dyn_cast<ConstantVector>(C1)) {
1208     if (const ConstantVector *CP2 = dyn_cast<ConstantVector>(C2)) {
1209       if (pred == FCmpInst::FCMP_OEQ || pred == FCmpInst::FCMP_UEQ) {
1210         for (unsigned i = 0, e = CP1->getNumOperands(); i != e; ++i) {
1211           Constant *C= ConstantExpr::getFCmp(FCmpInst::FCMP_OEQ,
1212               const_cast<Constant*>(CP1->getOperand(i)),
1213               const_cast<Constant*>(CP2->getOperand(i)));
1214           if (ConstantInt *CB = dyn_cast<ConstantInt>(C))
1215             return CB;
1216         }
1217         // Otherwise, could not decide from any element pairs.
1218         return 0;
1219       } else if (pred == ICmpInst::ICMP_EQ) {
1220         for (unsigned i = 0, e = CP1->getNumOperands(); i != e; ++i) {
1221           Constant *C = ConstantExpr::getICmp(ICmpInst::ICMP_EQ,
1222               const_cast<Constant*>(CP1->getOperand(i)),
1223               const_cast<Constant*>(CP2->getOperand(i)));
1224           if (ConstantInt *CB = dyn_cast<ConstantInt>(C))
1225             return CB;
1226         }
1227         // Otherwise, could not decide from any element pairs.
1228         return 0;
1229       }
1230     }
1231   }
1232
1233   if (C1->getType()->isFloatingPoint()) {
1234     switch (evaluateFCmpRelation(C1, C2)) {
1235     default: assert(0 && "Unknown relation!");
1236     case FCmpInst::FCMP_UNO:
1237     case FCmpInst::FCMP_ORD:
1238     case FCmpInst::FCMP_UEQ:
1239     case FCmpInst::FCMP_UNE:
1240     case FCmpInst::FCMP_ULT:
1241     case FCmpInst::FCMP_UGT:
1242     case FCmpInst::FCMP_ULE:
1243     case FCmpInst::FCMP_UGE:
1244     case FCmpInst::FCMP_TRUE:
1245     case FCmpInst::FCMP_FALSE:
1246     case FCmpInst::BAD_FCMP_PREDICATE:
1247       break; // Couldn't determine anything about these constants.
1248     case FCmpInst::FCMP_OEQ: // We know that C1 == C2
1249       return ConstantInt::get(Type::Int1Ty,
1250           pred == FCmpInst::FCMP_UEQ || pred == FCmpInst::FCMP_OEQ ||
1251           pred == FCmpInst::FCMP_ULE || pred == FCmpInst::FCMP_OLE ||
1252           pred == FCmpInst::FCMP_UGE || pred == FCmpInst::FCMP_OGE);
1253     case FCmpInst::FCMP_OLT: // We know that C1 < C2
1254       return ConstantInt::get(Type::Int1Ty,
1255           pred == FCmpInst::FCMP_UNE || pred == FCmpInst::FCMP_ONE ||
1256           pred == FCmpInst::FCMP_ULT || pred == FCmpInst::FCMP_OLT ||
1257           pred == FCmpInst::FCMP_ULE || pred == FCmpInst::FCMP_OLE);
1258     case FCmpInst::FCMP_OGT: // We know that C1 > C2
1259       return ConstantInt::get(Type::Int1Ty,
1260           pred == FCmpInst::FCMP_UNE || pred == FCmpInst::FCMP_ONE ||
1261           pred == FCmpInst::FCMP_UGT || pred == FCmpInst::FCMP_OGT ||
1262           pred == FCmpInst::FCMP_UGE || pred == FCmpInst::FCMP_OGE);
1263     case FCmpInst::FCMP_OLE: // We know that C1 <= C2
1264       // We can only partially decide this relation.
1265       if (pred == FCmpInst::FCMP_UGT || pred == FCmpInst::FCMP_OGT)
1266         return ConstantInt::getFalse();
1267       if (pred == FCmpInst::FCMP_ULT || pred == FCmpInst::FCMP_OLT)
1268         return ConstantInt::getTrue();
1269       break;
1270     case FCmpInst::FCMP_OGE: // We known that C1 >= C2
1271       // We can only partially decide this relation.
1272       if (pred == FCmpInst::FCMP_ULT || pred == FCmpInst::FCMP_OLT)
1273         return ConstantInt::getFalse();
1274       if (pred == FCmpInst::FCMP_UGT || pred == FCmpInst::FCMP_OGT)
1275         return ConstantInt::getTrue();
1276       break;
1277     case ICmpInst::ICMP_NE: // We know that C1 != C2
1278       // We can only partially decide this relation.
1279       if (pred == FCmpInst::FCMP_OEQ || pred == FCmpInst::FCMP_UEQ)
1280         return ConstantInt::getFalse();
1281       if (pred == FCmpInst::FCMP_ONE || pred == FCmpInst::FCMP_UNE)
1282         return ConstantInt::getTrue();
1283       break;
1284     }
1285   } else {
1286     // Evaluate the relation between the two constants, per the predicate.
1287     switch (evaluateICmpRelation(C1, C2, CmpInst::isSigned(pred))) {
1288     default: assert(0 && "Unknown relational!");
1289     case ICmpInst::BAD_ICMP_PREDICATE:
1290       break;  // Couldn't determine anything about these constants.
1291     case ICmpInst::ICMP_EQ:   // We know the constants are equal!
1292       // If we know the constants are equal, we can decide the result of this
1293       // computation precisely.
1294       return ConstantInt::get(Type::Int1Ty,
1295                               pred == ICmpInst::ICMP_EQ  ||
1296                               pred == ICmpInst::ICMP_ULE ||
1297                               pred == ICmpInst::ICMP_SLE ||
1298                               pred == ICmpInst::ICMP_UGE ||
1299                               pred == ICmpInst::ICMP_SGE);
1300     case ICmpInst::ICMP_ULT:
1301       // If we know that C1 < C2, we can decide the result of this computation
1302       // precisely.
1303       return ConstantInt::get(Type::Int1Ty,
1304                               pred == ICmpInst::ICMP_ULT ||
1305                               pred == ICmpInst::ICMP_NE  ||
1306                               pred == ICmpInst::ICMP_ULE);
1307     case ICmpInst::ICMP_SLT:
1308       // If we know that C1 < C2, we can decide the result of this computation
1309       // precisely.
1310       return ConstantInt::get(Type::Int1Ty,
1311                               pred == ICmpInst::ICMP_SLT ||
1312                               pred == ICmpInst::ICMP_NE  ||
1313                               pred == ICmpInst::ICMP_SLE);
1314     case ICmpInst::ICMP_UGT:
1315       // If we know that C1 > C2, we can decide the result of this computation
1316       // precisely.
1317       return ConstantInt::get(Type::Int1Ty,
1318                               pred == ICmpInst::ICMP_UGT ||
1319                               pred == ICmpInst::ICMP_NE  ||
1320                               pred == ICmpInst::ICMP_UGE);
1321     case ICmpInst::ICMP_SGT:
1322       // If we know that C1 > C2, we can decide the result of this computation
1323       // precisely.
1324       return ConstantInt::get(Type::Int1Ty,
1325                               pred == ICmpInst::ICMP_SGT ||
1326                               pred == ICmpInst::ICMP_NE  ||
1327                               pred == ICmpInst::ICMP_SGE);
1328     case ICmpInst::ICMP_ULE:
1329       // If we know that C1 <= C2, we can only partially decide this relation.
1330       if (pred == ICmpInst::ICMP_UGT) return ConstantInt::getFalse();
1331       if (pred == ICmpInst::ICMP_ULT) return ConstantInt::getTrue();
1332       break;
1333     case ICmpInst::ICMP_SLE:
1334       // If we know that C1 <= C2, we can only partially decide this relation.
1335       if (pred == ICmpInst::ICMP_SGT) return ConstantInt::getFalse();
1336       if (pred == ICmpInst::ICMP_SLT) return ConstantInt::getTrue();
1337       break;
1338
1339     case ICmpInst::ICMP_UGE:
1340       // If we know that C1 >= C2, we can only partially decide this relation.
1341       if (pred == ICmpInst::ICMP_ULT) return ConstantInt::getFalse();
1342       if (pred == ICmpInst::ICMP_UGT) return ConstantInt::getTrue();
1343       break;
1344     case ICmpInst::ICMP_SGE:
1345       // If we know that C1 >= C2, we can only partially decide this relation.
1346       if (pred == ICmpInst::ICMP_SLT) return ConstantInt::getFalse();
1347       if (pred == ICmpInst::ICMP_SGT) return ConstantInt::getTrue();
1348       break;
1349
1350     case ICmpInst::ICMP_NE:
1351       // If we know that C1 != C2, we can only partially decide this relation.
1352       if (pred == ICmpInst::ICMP_EQ) return ConstantInt::getFalse();
1353       if (pred == ICmpInst::ICMP_NE) return ConstantInt::getTrue();
1354       break;
1355     }
1356
1357     if (!isa<ConstantExpr>(C1) && isa<ConstantExpr>(C2)) {
1358       // If C2 is a constant expr and C1 isn't, flop them around and fold the
1359       // other way if possible.
1360       switch (pred) {
1361       case ICmpInst::ICMP_EQ:
1362       case ICmpInst::ICMP_NE:
1363         // No change of predicate required.
1364         return ConstantFoldCompareInstruction(pred, C2, C1);
1365
1366       case ICmpInst::ICMP_ULT:
1367       case ICmpInst::ICMP_SLT:
1368       case ICmpInst::ICMP_UGT:
1369       case ICmpInst::ICMP_SGT:
1370       case ICmpInst::ICMP_ULE:
1371       case ICmpInst::ICMP_SLE:
1372       case ICmpInst::ICMP_UGE:
1373       case ICmpInst::ICMP_SGE:
1374         // Change the predicate as necessary to swap the operands.
1375         pred = ICmpInst::getSwappedPredicate((ICmpInst::Predicate)pred);
1376         return ConstantFoldCompareInstruction(pred, C2, C1);
1377
1378       default:  // These predicates cannot be flopped around.
1379         break;
1380       }
1381     }
1382   }
1383   return 0;
1384 }
1385
1386 Constant *llvm::ConstantFoldGetElementPtr(const Constant *C,
1387                                           Constant* const *Idxs,
1388                                           unsigned NumIdx) {
1389   if (NumIdx == 0 ||
1390       (NumIdx == 1 && Idxs[0]->isNullValue()))
1391     return const_cast<Constant*>(C);
1392
1393   if (isa<UndefValue>(C)) {
1394     const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(),
1395                                                        (Value **)Idxs,
1396                                                        (Value **)Idxs+NumIdx,
1397                                                        true);
1398     assert(Ty != 0 && "Invalid indices for GEP!");
1399     return UndefValue::get(PointerType::get(Ty));
1400   }
1401
1402   Constant *Idx0 = Idxs[0];
1403   if (C->isNullValue()) {
1404     bool isNull = true;
1405     for (unsigned i = 0, e = NumIdx; i != e; ++i)
1406       if (!Idxs[i]->isNullValue()) {
1407         isNull = false;
1408         break;
1409       }
1410     if (isNull) {
1411       const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(),
1412                                                          (Value**)Idxs,
1413                                                          (Value**)Idxs+NumIdx,
1414                                                          true);
1415       assert(Ty != 0 && "Invalid indices for GEP!");
1416       return ConstantPointerNull::get(PointerType::get(Ty));
1417     }
1418   }
1419
1420   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(const_cast<Constant*>(C))) {
1421     // Combine Indices - If the source pointer to this getelementptr instruction
1422     // is a getelementptr instruction, combine the indices of the two
1423     // getelementptr instructions into a single instruction.
1424     //
1425     if (CE->getOpcode() == Instruction::GetElementPtr) {
1426       const Type *LastTy = 0;
1427       for (gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
1428            I != E; ++I)
1429         LastTy = *I;
1430
1431       if ((LastTy && isa<ArrayType>(LastTy)) || Idx0->isNullValue()) {
1432         SmallVector<Value*, 16> NewIndices;
1433         NewIndices.reserve(NumIdx + CE->getNumOperands());
1434         for (unsigned i = 1, e = CE->getNumOperands()-1; i != e; ++i)
1435           NewIndices.push_back(CE->getOperand(i));
1436
1437         // Add the last index of the source with the first index of the new GEP.
1438         // Make sure to handle the case when they are actually different types.
1439         Constant *Combined = CE->getOperand(CE->getNumOperands()-1);
1440         // Otherwise it must be an array.
1441         if (!Idx0->isNullValue()) {
1442           const Type *IdxTy = Combined->getType();
1443           if (IdxTy != Idx0->getType()) {
1444             Constant *C1 = ConstantExpr::getSExtOrBitCast(Idx0, Type::Int64Ty);
1445             Constant *C2 = ConstantExpr::getSExtOrBitCast(Combined,
1446                                                           Type::Int64Ty);
1447             Combined = ConstantExpr::get(Instruction::Add, C1, C2);
1448           } else {
1449             Combined =
1450               ConstantExpr::get(Instruction::Add, Idx0, Combined);
1451           }
1452         }
1453
1454         NewIndices.push_back(Combined);
1455         NewIndices.insert(NewIndices.end(), Idxs+1, Idxs+NumIdx);
1456         return ConstantExpr::getGetElementPtr(CE->getOperand(0), &NewIndices[0],
1457                                               NewIndices.size());
1458       }
1459     }
1460
1461     // Implement folding of:
1462     //    int* getelementptr ([2 x int]* cast ([3 x int]* %X to [2 x int]*),
1463     //                        long 0, long 0)
1464     // To: int* getelementptr ([3 x int]* %X, long 0, long 0)
1465     //
1466     if (CE->isCast() && NumIdx > 1 && Idx0->isNullValue()) {
1467       if (const PointerType *SPT =
1468           dyn_cast<PointerType>(CE->getOperand(0)->getType()))
1469         if (const ArrayType *SAT = dyn_cast<ArrayType>(SPT->getElementType()))
1470           if (const ArrayType *CAT =
1471         dyn_cast<ArrayType>(cast<PointerType>(C->getType())->getElementType()))
1472             if (CAT->getElementType() == SAT->getElementType())
1473               return ConstantExpr::getGetElementPtr(
1474                       (Constant*)CE->getOperand(0), Idxs, NumIdx);
1475     }
1476
1477     // Fold: getelementptr (i8* inttoptr (i64 1 to i8*), i32 -1)
1478     // Into: inttoptr (i64 0 to i8*)
1479     // This happens with pointers to member functions in C++.
1480     if (CE->getOpcode() == Instruction::IntToPtr && NumIdx == 1 &&
1481         isa<ConstantInt>(CE->getOperand(0)) && isa<ConstantInt>(Idxs[0]) &&
1482         cast<PointerType>(CE->getType())->getElementType() == Type::Int8Ty) {
1483       Constant *Base = CE->getOperand(0);
1484       Constant *Offset = Idxs[0];
1485
1486       // Convert the smaller integer to the larger type.
1487       if (Offset->getType()->getPrimitiveSizeInBits() <
1488           Base->getType()->getPrimitiveSizeInBits())
1489         Offset = ConstantExpr::getSExt(Offset, Base->getType());
1490       else if (Base->getType()->getPrimitiveSizeInBits() <
1491                Offset->getType()->getPrimitiveSizeInBits())
1492         Base = ConstantExpr::getZExt(Base, Base->getType());
1493
1494       Base = ConstantExpr::getAdd(Base, Offset);
1495       return ConstantExpr::getIntToPtr(Base, CE->getType());
1496     }
1497   }
1498   return 0;
1499 }
1500