lib/VMCore/ConstantFold.cpp

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