LLVM API Documentation

ConstantFold.cpp

Go to the documentation of this file.
00001 //===- ConstantFold.cpp - LLVM constant folder ----------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements folding of constants for LLVM.  This implements the
00011 // (internal) ConstantFold.h interface, which is used by the
00012 // ConstantExpr::get* methods to automatically fold constants when possible.
00013 //
00014 // The current constant folding implementation is implemented in two pieces: the
00015 // template-based folder for simple primitive constants like ConstantInt, and
00016 // the special case hackery that we use to symbolically evaluate expressions
00017 // that use ConstantExprs.
00018 //
00019 //===----------------------------------------------------------------------===//
00020 
00021 #include "ConstantFold.h"
00022 #include "llvm/Constants.h"
00023 #include "llvm/Instructions.h"
00024 #include "llvm/DerivedTypes.h"
00025 #include "llvm/Function.h"
00026 #include "llvm/GlobalAlias.h"
00027 #include "llvm/LLVMContext.h"
00028 #include "llvm/ADT/SmallVector.h"
00029 #include "llvm/Support/Compiler.h"
00030 #include "llvm/Support/ErrorHandling.h"
00031 #include "llvm/Support/GetElementPtrTypeIterator.h"
00032 #include "llvm/Support/ManagedStatic.h"
00033 #include "llvm/Support/MathExtras.h"
00034 #include <limits>
00035 using namespace llvm;
00036 
00037 //===----------------------------------------------------------------------===//
00038 //                ConstantFold*Instruction Implementations
00039 //===----------------------------------------------------------------------===//
00040 
00041 /// BitCastConstantVector - Convert the specified ConstantVector node to the
00042 /// specified vector type.  At this point, we know that the elements of the
00043 /// input vector constant are all simple integer or FP values.
00044 static Constant *BitCastConstantVector(LLVMContext &Context, ConstantVector *CV,
00045                                        const VectorType *DstTy) {
00046   // If this cast changes element count then we can't handle it here:
00047   // doing so requires endianness information.  This should be handled by
00048   // Analysis/ConstantFolding.cpp
00049   unsigned NumElts = DstTy->getNumElements();
00050   if (NumElts != CV->getNumOperands())
00051     return 0;
00052   
00053   // Check to verify that all elements of the input are simple.
00054   for (unsigned i = 0; i != NumElts; ++i) {
00055     if (!isa<ConstantInt>(CV->getOperand(i)) &&
00056         !isa<ConstantFP>(CV->getOperand(i)))
00057       return 0;
00058   }
00059 
00060   // Bitcast each element now.
00061   std::vector<Constant*> Result;
00062   const Type *DstEltTy = DstTy->getElementType();
00063   for (unsigned i = 0; i != NumElts; ++i)
00064     Result.push_back(ConstantExpr::getBitCast(CV->getOperand(i),
00065                                                     DstEltTy));
00066   return ConstantVector::get(Result);
00067 }
00068 
00069 /// This function determines which opcode to use to fold two constant cast 
00070 /// expressions together. It uses CastInst::isEliminableCastPair to determine
00071 /// the opcode. Consequently its just a wrapper around that function.
00072 /// @brief Determine if it is valid to fold a cast of a cast
00073 static unsigned
00074 foldConstantCastPair(
00075   unsigned opc,          ///< opcode of the second cast constant expression
00076   const ConstantExpr*Op, ///< the first cast constant expression
00077   const Type *DstTy      ///< desintation type of the first cast
00078 ) {
00079   assert(Op && Op->isCast() && "Can't fold cast of cast without a cast!");
00080   assert(DstTy && DstTy->isFirstClassType() && "Invalid cast destination type");
00081   assert(CastInst::isCast(opc) && "Invalid cast opcode");
00082   
00083   // The the types and opcodes for the two Cast constant expressions
00084   const Type *SrcTy = Op->getOperand(0)->getType();
00085   const Type *MidTy = Op->getType();
00086   Instruction::CastOps firstOp = Instruction::CastOps(Op->getOpcode());
00087   Instruction::CastOps secondOp = Instruction::CastOps(opc);
00088 
00089   // Let CastInst::isEliminableCastPair do the heavy lifting.
00090   return CastInst::isEliminableCastPair(firstOp, secondOp, SrcTy, MidTy, DstTy,
00091                                         Type::getInt64Ty(DstTy->getContext()));
00092 }
00093 
00094 static Constant *FoldBitCast(LLVMContext &Context, 
00095                              Constant *V, const Type *DestTy) {
00096   const Type *SrcTy = V->getType();
00097   if (SrcTy == DestTy)
00098     return V; // no-op cast
00099   
00100   // Check to see if we are casting a pointer to an aggregate to a pointer to
00101   // the first element.  If so, return the appropriate GEP instruction.
00102   if (const PointerType *PTy = dyn_cast<PointerType>(V->getType()))
00103     if (const PointerType *DPTy = dyn_cast<PointerType>(DestTy))
00104       if (PTy->getAddressSpace() == DPTy->getAddressSpace()) {
00105         SmallVector<Value*, 8> IdxList;
00106         Value *Zero = Constant::getNullValue(Type::getInt32Ty(Context));
00107         IdxList.push_back(Zero);
00108         const Type *ElTy = PTy->getElementType();
00109         while (ElTy != DPTy->getElementType()) {
00110           if (const StructType *STy = dyn_cast<StructType>(ElTy)) {
00111             if (STy->getNumElements() == 0) break;
00112             ElTy = STy->getElementType(0);
00113             IdxList.push_back(Zero);
00114           } else if (const SequentialType *STy = 
00115                      dyn_cast<SequentialType>(ElTy)) {
00116             if (isa<PointerType>(ElTy)) break;  // Can't index into pointers!
00117             ElTy = STy->getElementType();
00118             IdxList.push_back(Zero);
00119           } else {
00120             break;
00121           }
00122         }
00123         
00124         if (ElTy == DPTy->getElementType())
00125           // This GEP is inbounds because all indices are zero.
00126           return ConstantExpr::getInBoundsGetElementPtr(V, &IdxList[0],
00127                                                         IdxList.size());
00128       }
00129   
00130   // Handle casts from one vector constant to another.  We know that the src 
00131   // and dest type have the same size (otherwise its an illegal cast).
00132   if (const VectorType *DestPTy = dyn_cast<VectorType>(DestTy)) {
00133     if (const VectorType *SrcTy = dyn_cast<VectorType>(V->getType())) {
00134       assert(DestPTy->getBitWidth() == SrcTy->getBitWidth() &&
00135              "Not cast between same sized vectors!");
00136       SrcTy = NULL;
00137       // First, check for null.  Undef is already handled.
00138       if (isa<ConstantAggregateZero>(V))
00139         return Constant::getNullValue(DestTy);
00140       
00141       if (ConstantVector *CV = dyn_cast<ConstantVector>(V))
00142         return BitCastConstantVector(Context, CV, DestPTy);
00143     }
00144 
00145     // Canonicalize scalar-to-vector bitcasts into vector-to-vector bitcasts
00146     // This allows for other simplifications (although some of them
00147     // can only be handled by Analysis/ConstantFolding.cpp).
00148     if (isa<ConstantInt>(V) || isa<ConstantFP>(V))
00149       return ConstantExpr::getBitCast(
00150                                      ConstantVector::get(&V, 1), DestPTy);
00151   }
00152   
00153   // Finally, implement bitcast folding now.   The code below doesn't handle
00154   // bitcast right.
00155   if (isa<ConstantPointerNull>(V))  // ptr->ptr cast.
00156     return ConstantPointerNull::get(cast<PointerType>(DestTy));
00157   
00158   // Handle integral constant input.
00159   if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
00160     if (DestTy->isInteger())
00161       // Integral -> Integral. This is a no-op because the bit widths must
00162       // be the same. Consequently, we just fold to V.
00163       return V;
00164 
00165     if (DestTy->isFloatingPoint())
00166       return ConstantFP::get(Context, APFloat(CI->getValue(),
00167                                      DestTy != Type::getPPC_FP128Ty(Context)));
00168 
00169     // Otherwise, can't fold this (vector?)
00170     return 0;
00171   }
00172 
00173   // Handle ConstantFP input.
00174   if (const ConstantFP *FP = dyn_cast<ConstantFP>(V))
00175     // FP -> Integral.
00176     return ConstantInt::get(Context, FP->getValueAPF().bitcastToAPInt());
00177 
00178   return 0;
00179 }
00180 
00181 
00182 Constant *llvm::ConstantFoldCastInstruction(LLVMContext &Context, 
00183                                             unsigned opc, const Constant *V,
00184                                             const Type *DestTy) {
00185   if (isa<UndefValue>(V)) {
00186     // zext(undef) = 0, because the top bits will be zero.
00187     // sext(undef) = 0, because the top bits will all be the same.
00188     // [us]itofp(undef) = 0, because the result value is bounded.
00189     if (opc == Instruction::ZExt || opc == Instruction::SExt ||
00190         opc == Instruction::UIToFP || opc == Instruction::SIToFP)
00191       return Constant::getNullValue(DestTy);
00192     return UndefValue::get(DestTy);
00193   }
00194   // No compile-time operations on this type yet.
00195   if (V->getType() == Type::getPPC_FP128Ty(Context) || DestTy == Type::getPPC_FP128Ty(Context))
00196     return 0;
00197 
00198   // If the cast operand is a constant expression, there's a few things we can
00199   // do to try to simplify it.
00200   if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
00201     if (CE->isCast()) {
00202       // Try hard to fold cast of cast because they are often eliminable.
00203       if (unsigned newOpc = foldConstantCastPair(opc, CE, DestTy))
00204         return ConstantExpr::getCast(newOpc, CE->getOperand(0), DestTy);
00205     } else if (CE->getOpcode() == Instruction::GetElementPtr) {
00206       // If all of the indexes in the GEP are null values, there is no pointer
00207       // adjustment going on.  We might as well cast the source pointer.
00208       bool isAllNull = true;
00209       for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
00210         if (!CE->getOperand(i)->isNullValue()) {
00211           isAllNull = false;
00212           break;
00213         }
00214       if (isAllNull)
00215         // This is casting one pointer type to another, always BitCast
00216         return ConstantExpr::getPointerCast(CE->getOperand(0), DestTy);
00217     }
00218   }
00219 
00220   // If the cast operand is a constant vector, perform the cast by
00221   // operating on each element. In the cast of bitcasts, the element
00222   // count may be mismatched; don't attempt to handle that here.
00223   if (const ConstantVector *CV = dyn_cast<ConstantVector>(V))
00224     if (isa<VectorType>(DestTy) &&
00225         cast<VectorType>(DestTy)->getNumElements() ==
00226         CV->getType()->getNumElements()) {
00227       std::vector<Constant*> res;
00228       const VectorType *DestVecTy = cast<VectorType>(DestTy);
00229       const Type *DstEltTy = DestVecTy->getElementType();
00230       for (unsigned i = 0, e = CV->getType()->getNumElements(); i != e; ++i)
00231         res.push_back(ConstantExpr::getCast(opc,
00232                                             CV->getOperand(i), DstEltTy));
00233       return ConstantVector::get(DestVecTy, res);
00234     }
00235 
00236   // We actually have to do a cast now. Perform the cast according to the
00237   // opcode specified.
00238   switch (opc) {
00239   case Instruction::FPTrunc:
00240   case Instruction::FPExt:
00241     if (const ConstantFP *FPC = dyn_cast<ConstantFP>(V)) {
00242       bool ignored;
00243       APFloat Val = FPC->getValueAPF();
00244       Val.convert(DestTy == Type::getFloatTy(Context) ? APFloat::IEEEsingle :
00245                   DestTy == Type::getDoubleTy(Context) ? APFloat::IEEEdouble :
00246                   DestTy == Type::getX86_FP80Ty(Context) ? APFloat::x87DoubleExtended :
00247                   DestTy == Type::getFP128Ty(Context) ? APFloat::IEEEquad :
00248                   APFloat::Bogus,
00249                   APFloat::rmNearestTiesToEven, &ignored);
00250       return ConstantFP::get(Context, Val);
00251     }
00252     return 0; // Can't fold.
00253   case Instruction::FPToUI: 
00254   case Instruction::FPToSI:
00255     if (const ConstantFP *FPC = dyn_cast<ConstantFP>(V)) {
00256       const APFloat &V = FPC->getValueAPF();
00257       bool ignored;
00258       uint64_t x[2]; 
00259       uint32_t DestBitWidth = cast<IntegerType>(DestTy)->getBitWidth();
00260       (void) V.convertToInteger(x, DestBitWidth, opc==Instruction::FPToSI,
00261                                 APFloat::rmTowardZero, &ignored);
00262       APInt Val(DestBitWidth, 2, x);
00263       return ConstantInt::get(Context, Val);
00264     }
00265     return 0; // Can't fold.
00266   case Instruction::IntToPtr:   //always treated as unsigned
00267     if (V->isNullValue())       // Is it an integral null value?
00268       return ConstantPointerNull::get(cast<PointerType>(DestTy));
00269     return 0;                   // Other pointer types cannot be casted
00270   case Instruction::PtrToInt:   // always treated as unsigned
00271     if (V->isNullValue())       // is it a null pointer value?
00272       return ConstantInt::get(DestTy, 0);
00273     return 0;                   // Other pointer types cannot be casted
00274   case Instruction::UIToFP:
00275   case Instruction::SIToFP:
00276     if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
00277       APInt api = CI->getValue();
00278       const uint64_t zero[] = {0, 0};
00279       APFloat apf = APFloat(APInt(DestTy->getPrimitiveSizeInBits(),
00280                                   2, zero));
00281       (void)apf.convertFromAPInt(api, 
00282                                  opc==Instruction::SIToFP,
00283                                  APFloat::rmNearestTiesToEven);
00284       return ConstantFP::get(Context, apf);
00285     }
00286     return 0;
00287   case Instruction::ZExt:
00288     if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
00289       uint32_t BitWidth = cast<IntegerType>(DestTy)->getBitWidth();
00290       APInt Result(CI->getValue());
00291       Result.zext(BitWidth);
00292       return ConstantInt::get(Context, Result);
00293     }
00294     return 0;
00295   case Instruction::SExt:
00296     if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
00297       uint32_t BitWidth = cast<IntegerType>(DestTy)->getBitWidth();
00298       APInt Result(CI->getValue());
00299       Result.sext(BitWidth);
00300       return ConstantInt::get(Context, Result);
00301     }
00302     return 0;
00303   case Instruction::Trunc:
00304     if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
00305       uint32_t BitWidth = cast<IntegerType>(DestTy)->getBitWidth();
00306       APInt Result(CI->getValue());
00307       Result.trunc(BitWidth);
00308       return ConstantInt::get(Context, Result);
00309     }
00310     return 0;
00311   case Instruction::BitCast:
00312     return FoldBitCast(Context, const_cast<Constant*>(V), DestTy);
00313   default:
00314     assert(!"Invalid CE CastInst opcode");
00315     break;
00316   }
00317 
00318   llvm_unreachable("Failed to cast constant expression");
00319   return 0;
00320 }
00321 
00322 Constant *llvm::ConstantFoldSelectInstruction(LLVMContext&,
00323                                               const Constant *Cond,
00324                                               const Constant *V1,
00325                                               const Constant *V2) {
00326   if (const ConstantInt *CB = dyn_cast<ConstantInt>(Cond))
00327     return const_cast<Constant*>(CB->getZExtValue() ? V1 : V2);
00328 
00329   if (isa<UndefValue>(V1)) return const_cast<Constant*>(V2);
00330   if (isa<UndefValue>(V2)) return const_cast<Constant*>(V1);
00331   if (isa<UndefValue>(Cond)) return const_cast<Constant*>(V1);
00332   if (V1 == V2) return const_cast<Constant*>(V1);
00333   return 0;
00334 }
00335 
00336 Constant *llvm::ConstantFoldExtractElementInstruction(LLVMContext &Context,
00337                                                       const Constant *Val,
00338                                                       const Constant *Idx) {
00339   if (isa<UndefValue>(Val))  // ee(undef, x) -> undef
00340     return UndefValue::get(cast<VectorType>(Val->getType())->getElementType());
00341   if (Val->isNullValue())  // ee(zero, x) -> zero
00342     return Constant::getNullValue(
00343                           cast<VectorType>(Val->getType())->getElementType());
00344   
00345   if (const ConstantVector *CVal = dyn_cast<ConstantVector>(Val)) {
00346     if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Idx)) {
00347       return CVal->getOperand(CIdx->getZExtValue());
00348     } else if (isa<UndefValue>(Idx)) {
00349       // ee({w,x,y,z}, undef) -> w (an arbitrary value).
00350       return CVal->getOperand(0);
00351     }
00352   }
00353   return 0;
00354 }
00355 
00356 Constant *llvm::ConstantFoldInsertElementInstruction(LLVMContext &Context,
00357                                                      const Constant *Val,
00358                                                      const Constant *Elt,
00359                                                      const Constant *Idx) {
00360   const ConstantInt *CIdx = dyn_cast<ConstantInt>(Idx);
00361   if (!CIdx) return 0;
00362   APInt idxVal = CIdx->getValue();
00363   if (isa<UndefValue>(Val)) { 
00364     // Insertion of scalar constant into vector undef
00365     // Optimize away insertion of undef
00366     if (isa<UndefValue>(Elt))
00367       return const_cast<Constant*>(Val);
00368     // Otherwise break the aggregate undef into multiple undefs and do
00369     // the insertion
00370     unsigned numOps = 
00371       cast<VectorType>(Val->getType())->getNumElements();
00372     std::vector<Constant*> Ops; 
00373     Ops.reserve(numOps);
00374     for (unsigned i = 0; i < numOps; ++i) {
00375       const Constant *Op =
00376         (idxVal == i) ? Elt : UndefValue::get(Elt->getType());
00377       Ops.push_back(const_cast<Constant*>(Op));
00378     }
00379     return ConstantVector::get(Ops);
00380   }
00381   if (isa<ConstantAggregateZero>(Val)) {
00382     // Insertion of scalar constant into vector aggregate zero
00383     // Optimize away insertion of zero
00384     if (Elt->isNullValue())
00385       return const_cast<Constant*>(Val);
00386     // Otherwise break the aggregate zero into multiple zeros and do
00387     // the insertion
00388     unsigned numOps = 
00389       cast<VectorType>(Val->getType())->getNumElements();
00390     std::vector<Constant*> Ops; 
00391     Ops.reserve(numOps);
00392     for (unsigned i = 0; i < numOps; ++i) {
00393       const Constant *Op =
00394         (idxVal == i) ? Elt : Constant::getNullValue(Elt->getType());
00395       Ops.push_back(const_cast<Constant*>(Op));
00396     }
00397     return ConstantVector::get(Ops);
00398   }
00399   if (const ConstantVector *CVal = dyn_cast<ConstantVector>(Val)) {
00400     // Insertion of scalar constant into vector constant
00401     std::vector<Constant*> Ops; 
00402     Ops.reserve(CVal->getNumOperands());
00403     for (unsigned i = 0; i < CVal->getNumOperands(); ++i) {
00404       const Constant *Op =
00405         (idxVal == i) ? Elt : cast<Constant>(CVal->getOperand(i));
00406       Ops.push_back(const_cast<Constant*>(Op));
00407     }
00408     return ConstantVector::get(Ops);
00409   }
00410 
00411   return 0;
00412 }
00413 
00414 /// GetVectorElement - If C is a ConstantVector, ConstantAggregateZero or Undef
00415 /// return the specified element value.  Otherwise return null.
00416 static Constant *GetVectorElement(LLVMContext &Context, const Constant *C,
00417                                   unsigned EltNo) {
00418   if (const ConstantVector *CV = dyn_cast<ConstantVector>(C))
00419     return CV->getOperand(EltNo);
00420   
00421   const Type *EltTy = cast<VectorType>(C->getType())->getElementType();
00422   if (isa<ConstantAggregateZero>(C))
00423     return Constant::getNullValue(EltTy);
00424   if (isa<UndefValue>(C))
00425     return UndefValue::get(EltTy);
00426   return 0;
00427 }
00428 
00429 Constant *llvm::ConstantFoldShuffleVectorInstruction(LLVMContext &Context,
00430                                                      const Constant *V1,
00431                                                      const Constant *V2,
00432                                                      const Constant *Mask) {
00433   // Undefined shuffle mask -> undefined value.
00434   if (isa<UndefValue>(Mask)) return UndefValue::get(V1->getType());
00435 
00436   unsigned MaskNumElts = cast<VectorType>(Mask->getType())->getNumElements();
00437   unsigned SrcNumElts = cast<VectorType>(V1->getType())->getNumElements();
00438   const Type *EltTy = cast<VectorType>(V1->getType())->getElementType();
00439 
00440   // Loop over the shuffle mask, evaluating each element.
00441   SmallVector<Constant*, 32> Result;
00442   for (unsigned i = 0; i != MaskNumElts; ++i) {
00443     Constant *InElt = GetVectorElement(Context, Mask, i);
00444     if (InElt == 0) return 0;
00445 
00446     if (isa<UndefValue>(InElt))
00447       InElt = UndefValue::get(EltTy);
00448     else if (ConstantInt *CI = dyn_cast<ConstantInt>(InElt)) {
00449       unsigned Elt = CI->getZExtValue();
00450       if (Elt >= SrcNumElts*2)
00451         InElt = UndefValue::get(EltTy);
00452       else if (Elt >= SrcNumElts)
00453         InElt = GetVectorElement(Context, V2, Elt - SrcNumElts);
00454       else
00455         InElt = GetVectorElement(Context, V1, Elt);
00456       if (InElt == 0) return 0;
00457     } else {
00458       // Unknown value.
00459       return 0;
00460     }
00461     Result.push_back(InElt);
00462   }
00463 
00464   return ConstantVector::get(&Result[0], Result.size());
00465 }
00466 
00467 Constant *llvm::ConstantFoldExtractValueInstruction(LLVMContext &Context,
00468                                                     const Constant *Agg,
00469                                                     const unsigned *Idxs,
00470                                                     unsigned NumIdx) {
00471   // Base case: no indices, so return the entire value.
00472   if (NumIdx == 0)
00473     return const_cast<Constant *>(Agg);
00474 
00475   if (isa<UndefValue>(Agg))  // ev(undef, x) -> undef
00476     return UndefValue::get(ExtractValueInst::getIndexedType(Agg->getType(),
00477                                                             Idxs,
00478                                                             Idxs + NumIdx));
00479 
00480   if (isa<ConstantAggregateZero>(Agg))  // ev(0, x) -> 0
00481     return
00482       Constant::getNullValue(ExtractValueInst::getIndexedType(Agg->getType(),
00483                                                               Idxs,
00484                                                               Idxs + NumIdx));
00485 
00486   // Otherwise recurse.
00487   return ConstantFoldExtractValueInstruction(Context, Agg->getOperand(*Idxs),
00488                                              Idxs+1, NumIdx-1);
00489 }
00490 
00491 Constant *llvm::ConstantFoldInsertValueInstruction(LLVMContext &Context,
00492                                                    const Constant *Agg,
00493                                                    const Constant *Val,
00494                                                    const unsigned *Idxs,
00495                                                    unsigned NumIdx) {
00496   // Base case: no indices, so replace the entire value.
00497   if (NumIdx == 0)
00498     return const_cast<Constant *>(Val);
00499 
00500   if (isa<UndefValue>(Agg)) {
00501     // Insertion of constant into aggregate undef
00502     // Optimize away insertion of undef.
00503     if (isa<UndefValue>(Val))
00504       return const_cast<Constant*>(Agg);
00505     
00506     // Otherwise break the aggregate undef into multiple undefs and do
00507     // the insertion.
00508     const CompositeType *AggTy = cast<CompositeType>(Agg->getType());
00509     unsigned numOps;
00510     if (const ArrayType *AR = dyn_cast<ArrayType>(AggTy))
00511       numOps = AR->getNumElements();
00512     else
00513       numOps = cast<StructType>(AggTy)->getNumElements();
00514     
00515     std::vector<Constant*> Ops(numOps); 
00516     for (unsigned i = 0; i < numOps; ++i) {
00517       const Type *MemberTy = AggTy->getTypeAtIndex(i);
00518       const Constant *Op =
00519         (*Idxs == i) ?
00520         ConstantFoldInsertValueInstruction(Context, UndefValue::get(MemberTy),
00521                                            Val, Idxs+1, NumIdx-1) :
00522         UndefValue::get(MemberTy);
00523       Ops[i] = const_cast<Constant*>(Op);
00524     }
00525     
00526     if (const StructType* ST = dyn_cast<StructType>(AggTy))
00527       return ConstantStruct::get(Context, Ops, ST->isPacked());
00528     return ConstantArray::get(cast<ArrayType>(AggTy), Ops);
00529   }
00530   
00531   if (isa<ConstantAggregateZero>(Agg)) {
00532     // Insertion of constant into aggregate zero
00533     // Optimize away insertion of zero.
00534     if (Val->isNullValue())
00535       return const_cast<Constant*>(Agg);
00536     
00537     // Otherwise break the aggregate zero into multiple zeros and do
00538     // the insertion.
00539     const CompositeType *AggTy = cast<CompositeType>(Agg->getType());
00540     unsigned numOps;
00541     if (const ArrayType *AR = dyn_cast<ArrayType>(AggTy))
00542       numOps = AR->getNumElements();
00543     else
00544       numOps = cast<StructType>(AggTy)->getNumElements();
00545     
00546     std::vector<Constant*> Ops(numOps);
00547     for (unsigned i = 0; i < numOps; ++i) {
00548       const Type *MemberTy = AggTy->getTypeAtIndex(i);
00549       const Constant *Op =
00550         (*Idxs == i) ?
00551         ConstantFoldInsertValueInstruction(Context, 
00552                                            Constant::getNullValue(MemberTy),
00553                                            Val, Idxs+1, NumIdx-1) :
00554         Constant::getNullValue(MemberTy);
00555       Ops[i] = const_cast<Constant*>(Op);
00556     }
00557     
00558     if (const StructType* ST = dyn_cast<StructType>(AggTy))
00559       return ConstantStruct::get(Context, Ops, ST->isPacked());
00560     return ConstantArray::get(cast<ArrayType>(AggTy), Ops);
00561   }
00562   
00563   if (isa<ConstantStruct>(Agg) || isa<ConstantArray>(Agg)) {
00564     // Insertion of constant into aggregate constant.
00565     std::vector<Constant*> Ops(Agg->getNumOperands());
00566     for (unsigned i = 0; i < Agg->getNumOperands(); ++i) {
00567       const Constant *Op =
00568         (*Idxs == i) ?
00569         ConstantFoldInsertValueInstruction(Context, Agg->getOperand(i),
00570                                            Val, Idxs+1, NumIdx-1) :
00571         Agg->getOperand(i);
00572       Ops[i] = const_cast<Constant*>(Op);
00573     }
00574     
00575     if (const StructType* ST = dyn_cast<StructType>(Agg->getType()))
00576       return ConstantStruct::get(Context, Ops, ST->isPacked());
00577     return ConstantArray::get(cast<ArrayType>(Agg->getType()), Ops);
00578   }
00579 
00580   return 0;
00581 }
00582 
00583 
00584 Constant *llvm::ConstantFoldBinaryInstruction(LLVMContext &Context,
00585                                               unsigned Opcode,
00586                                               const Constant *C1,
00587                                               const Constant *C2) {
00588   // No compile-time operations on this type yet.
00589   if (C1->getType() == Type::getPPC_FP128Ty(Context))
00590     return 0;
00591 
00592   // Handle UndefValue up front.
00593   if (isa<UndefValue>(C1) || isa<UndefValue>(C2)) {
00594     switch (Opcode) {
00595     case Instruction::Xor:
00596       if (isa<UndefValue>(C1) && isa<UndefValue>(C2))
00597         // Handle undef ^ undef -> 0 special case. This is a common
00598         // idiom (misuse).
00599         return Constant::getNullValue(C1->getType());
00600       // Fallthrough
00601     case Instruction::Add:
00602     case Instruction::Sub:
00603       return UndefValue::get(C1->getType());
00604     case Instruction::Mul:
00605     case Instruction::And:
00606       return Constant::getNullValue(C1->getType());
00607     case Instruction::UDiv:
00608     case Instruction::SDiv:
00609     case Instruction::URem:
00610     case Instruction::SRem:
00611       if (!isa<UndefValue>(C2))                    // undef / X -> 0
00612         return Constant::getNullValue(C1->getType());
00613       return const_cast<Constant*>(C2);            // X / undef -> undef
00614     case Instruction::Or:                          // X | undef -> -1
00615       if (const VectorType *PTy = dyn_cast<VectorType>(C1->getType()))
00616         return Constant::getAllOnesValue(PTy);
00617       return Constant::getAllOnesValue(C1->getType());
00618     case Instruction::LShr:
00619       if (isa<UndefValue>(C2) && isa<UndefValue>(C1))
00620         return const_cast<Constant*>(C1);           // undef lshr undef -> undef
00621       return Constant::getNullValue(C1->getType()); // X lshr undef -> 0
00622                                                     // undef lshr X -> 0
00623     case Instruction::AShr:
00624       if (!isa<UndefValue>(C2))
00625         return const_cast<Constant*>(C1);           // undef ashr X --> undef
00626       else if (isa<UndefValue>(C1)) 
00627         return const_cast<Constant*>(C1);           // undef ashr undef -> undef
00628       else
00629         return const_cast<Constant*>(C1);           // X ashr undef --> X
00630     case Instruction::Shl:
00631       // undef << X -> 0   or   X << undef -> 0
00632       return Constant::getNullValue(C1->getType());
00633     }
00634   }
00635 
00636   // Handle simplifications when the RHS is a constant int.
00637   if (const ConstantInt *CI2 = dyn_cast<ConstantInt>(C2)) {
00638     switch (Opcode) {
00639     case Instruction::Add:
00640       if (CI2->equalsInt(0)) return const_cast<Constant*>(C1);  // X + 0 == X
00641       break;
00642     case Instruction::Sub:
00643       if (CI2->equalsInt(0)) return const_cast<Constant*>(C1);  // X - 0 == X
00644       break;
00645     case Instruction::Mul:
00646       if (CI2->equalsInt(0)) return const_cast<Constant*>(C2);  // X * 0 == 0
00647       if (CI2->equalsInt(1))
00648         return const_cast<Constant*>(C1);                       // X * 1 == X
00649       break;
00650     case Instruction::UDiv:
00651     case Instruction::SDiv:
00652       if (CI2->equalsInt(1))
00653         return const_cast<Constant*>(C1);                     // X / 1 == X
00654       if (CI2->equalsInt(0))
00655         return UndefValue::get(CI2->getType());               // X / 0 == undef
00656       break;
00657     case Instruction::URem:
00658     case Instruction::SRem:
00659       if (CI2->equalsInt(1))
00660         return Constant::getNullValue(CI2->getType());        // X % 1 == 0
00661       if (CI2->equalsInt(0))
00662         return UndefValue::get(CI2->getType());               // X % 0 == undef
00663       break;
00664     case Instruction::And:
00665       if (CI2->isZero()) return const_cast<Constant*>(C2);    // X & 0 == 0
00666       if (CI2->isAllOnesValue())
00667         return const_cast<Constant*>(C1);                     // X & -1 == X
00668       
00669       if (const ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1)) {
00670         // (zext i32 to i64) & 4294967295 -> (zext i32 to i64)
00671         if (CE1->getOpcode() == Instruction::ZExt) {
00672           unsigned DstWidth = CI2->getType()->getBitWidth();
00673           unsigned SrcWidth =
00674             CE1->getOperand(0)->getType()->getPrimitiveSizeInBits();
00675           APInt PossiblySetBits(APInt::getLowBitsSet(DstWidth, SrcWidth));
00676           if ((PossiblySetBits & CI2->getValue()) == PossiblySetBits)
00677             return const_cast<Constant*>(C1);
00678         }
00679         
00680         // If and'ing the address of a global with a constant, fold it.
00681         if (CE1->getOpcode() == Instruction::PtrToInt && 
00682             isa<GlobalValue>(CE1->getOperand(0))) {
00683           GlobalValue *GV = cast<GlobalValue>(CE1->getOperand(0));
00684         
00685           // Functions are at least 4-byte aligned.
00686           unsigned GVAlign = GV->getAlignment();
00687           if (isa<Function>(GV))
00688             GVAlign = std::max(GVAlign, 4U);
00689           
00690           if (GVAlign > 1) {
00691             unsigned DstWidth = CI2->getType()->getBitWidth();
00692             unsigned SrcWidth = std::min(DstWidth, Log2_32(GVAlign));
00693             APInt BitsNotSet(APInt::getLowBitsSet(DstWidth, SrcWidth));
00694 
00695             // If checking bits we know are clear, return zero.
00696             if ((CI2->getValue() & BitsNotSet) == CI2->getValue())
00697               return Constant::getNullValue(CI2->getType());
00698           }
00699         }
00700       }
00701       break;
00702     case Instruction::Or:
00703       if (CI2->equalsInt(0)) return const_cast<Constant*>(C1);  // X | 0 == X
00704       if (CI2->isAllOnesValue())
00705         return const_cast<Constant*>(C2);  // X | -1 == -1
00706       break;
00707     case Instruction::Xor:
00708       if (CI2->equalsInt(0)) return const_cast<Constant*>(C1);  // X ^ 0 == X
00709       break;
00710     case Instruction::AShr:
00711       // ashr (zext C to Ty), C2 -> lshr (zext C, CSA), C2
00712       if (const ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1))
00713         if (CE1->getOpcode() == Instruction::ZExt)  // Top bits known zero.
00714           return ConstantExpr::getLShr(const_cast<Constant*>(C1),
00715                                              const_cast<Constant*>(C2));
00716       break;
00717     }
00718   }
00719   
00720   // At this point we know neither constant is an UndefValue.
00721   if (const ConstantInt *CI1 = dyn_cast<ConstantInt>(C1)) {
00722     if (const ConstantInt *CI2 = dyn_cast<ConstantInt>(C2)) {
00723       using namespace APIntOps;
00724       const APInt &C1V = CI1->getValue();
00725       const APInt &C2V = CI2->getValue();
00726       switch (Opcode) {
00727       default:
00728         break;
00729       case Instruction::Add:     
00730         return ConstantInt::get(Context, C1V + C2V);
00731       case Instruction::Sub:     
00732         return ConstantInt::get(Context, C1V - C2V);
00733       case Instruction::Mul:     
00734         return ConstantInt::get(Context, C1V * C2V);
00735       case Instruction::UDiv:
00736         assert(!CI2->isNullValue() && "Div by zero handled above");
00737         return ConstantInt::get(Context, C1V.udiv(C2V));
00738       case Instruction::SDiv:
00739         assert(!CI2->isNullValue() && "Div by zero handled above");
00740         if (C2V.isAllOnesValue() && C1V.isMinSignedValue())
00741           return UndefValue::get(CI1->getType());   // MIN_INT / -1 -> undef
00742         return ConstantInt::get(Context, C1V.sdiv(C2V));
00743       case Instruction::URem:
00744         assert(!CI2->isNullValue() && "Div by zero handled above");
00745         return ConstantInt::get(Context, C1V.urem(C2V));
00746       case Instruction::SRem:
00747         assert(!CI2->isNullValue() && "Div by zero handled above");
00748         if (C2V.isAllOnesValue() && C1V.isMinSignedValue())
00749           return UndefValue::get(CI1->getType());   // MIN_INT % -1 -> undef
00750         return ConstantInt::get(Context, C1V.srem(C2V));
00751       case Instruction::And:
00752         return ConstantInt::get(Context, C1V & C2V);
00753       case Instruction::Or:
00754         return ConstantInt::get(Context, C1V | C2V);
00755       case Instruction::Xor:
00756         return ConstantInt::get(Context, C1V ^ C2V);
00757       case Instruction::Shl: {
00758         uint32_t shiftAmt = C2V.getZExtValue();
00759         if (shiftAmt < C1V.getBitWidth())
00760           return ConstantInt::get(Context, C1V.shl(shiftAmt));
00761         else
00762           return UndefValue::get(C1->getType()); // too big shift is undef
00763       }
00764       case Instruction::LShr: {
00765         uint32_t shiftAmt = C2V.getZExtValue();
00766         if (shiftAmt < C1V.getBitWidth())
00767           return ConstantInt::get(Context, C1V.lshr(shiftAmt));
00768         else
00769           return UndefValue::get(C1->getType()); // too big shift is undef
00770       }
00771       case Instruction::AShr: {
00772         uint32_t shiftAmt = C2V.getZExtValue();
00773         if (shiftAmt < C1V.getBitWidth())
00774           return ConstantInt::get(Context, C1V.ashr(shiftAmt));
00775         else
00776           return UndefValue::get(C1->getType()); // too big shift is undef
00777       }
00778       }
00779     }
00780 
00781     switch (Opcode) {
00782     case Instruction::SDiv:
00783     case Instruction::UDiv:
00784     case Instruction::URem:
00785     case Instruction::SRem:
00786     case Instruction::LShr:
00787     case Instruction::AShr:
00788     case Instruction::Shl:
00789       if (CI1->equalsInt(0)) return const_cast<Constant*>(C1);
00790       break;
00791     default:
00792       break;
00793     }
00794   } else if (const ConstantFP *CFP1 = dyn_cast<ConstantFP>(C1)) {
00795     if (const ConstantFP *CFP2 = dyn_cast<ConstantFP>(C2)) {
00796       APFloat C1V = CFP1->getValueAPF();
00797       APFloat C2V = CFP2->getValueAPF();
00798       APFloat C3V = C1V;  // copy for modification
00799       switch (Opcode) {
00800       default:                   
00801         break;
00802       case Instruction::FAdd:
00803         (void)C3V.add(C2V, APFloat::rmNearestTiesToEven);
00804         return ConstantFP::get(Context, C3V);
00805       case Instruction::FSub:
00806         (void)C3V.subtract(C2V, APFloat::rmNearestTiesToEven);
00807         return ConstantFP::get(Context, C3V);
00808       case Instruction::FMul:
00809         (void)C3V.multiply(C2V, APFloat::rmNearestTiesToEven);
00810         return ConstantFP::get(Context, C3V);
00811       case Instruction::FDiv:
00812         (void)C3V.divide(C2V, APFloat::rmNearestTiesToEven);
00813         return ConstantFP::get(Context, C3V);
00814       case Instruction::FRem:
00815         (void)C3V.mod(C2V, APFloat::rmNearestTiesToEven);
00816         return ConstantFP::get(Context, C3V);
00817       }
00818     }
00819   } else if (const VectorType *VTy = dyn_cast<VectorType>(C1->getType())) {
00820     const ConstantVector *CP1 = dyn_cast<ConstantVector>(C1);
00821     const ConstantVector *CP2 = dyn_cast<ConstantVector>(C2);
00822     if ((CP1 != NULL || isa<ConstantAggregateZero>(C1)) &&
00823         (CP2 != NULL || isa<ConstantAggregateZero>(C2))) {
00824       std::vector<Constant*> Res;
00825       const Type* EltTy = VTy->getElementType();  
00826       const Constant *C1 = 0;
00827       const Constant *C2 = 0;
00828       switch (Opcode) {
00829       default:
00830         break;
00831       case Instruction::Add:
00832         for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
00833           C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy);
00834           C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy);
00835           Res.push_back(ConstantExpr::getAdd(const_cast<Constant*>(C1),
00836                                                    const_cast<Constant*>(C2)));
00837         }
00838         return ConstantVector::get(Res);
00839       case Instruction::FAdd:
00840         for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
00841           C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy);
00842           C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy);
00843           Res.push_back(ConstantExpr::getFAdd(const_cast<Constant*>(C1),
00844                                                     const_cast<Constant*>(C2)));
00845         }
00846         return ConstantVector::get(Res);
00847       case Instruction::Sub:
00848         for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
00849           C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy);
00850           C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy);
00851           Res.push_back(ConstantExpr::getSub(const_cast<Constant*>(C1),
00852                                                    const_cast<Constant*>(C2)));
00853         }
00854         return ConstantVector::get(Res);
00855       case Instruction::FSub:
00856         for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
00857           C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy);
00858           C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy);
00859           Res.push_back(ConstantExpr::getFSub(const_cast<Constant*>(C1),
00860                                                     const_cast<Constant*>(C2)));
00861         }
00862         return ConstantVector::get(Res);
00863       case Instruction::Mul:
00864         for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
00865           C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy);
00866           C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy);
00867           Res.push_back(ConstantExpr::getMul(const_cast<Constant*>(C1),
00868                                                    const_cast<Constant*>(C2)));
00869         }
00870         return ConstantVector::get(Res);
00871       case Instruction::FMul:
00872         for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
00873           C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy);
00874           C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy);
00875           Res.push_back(ConstantExpr::getFMul(const_cast<Constant*>(C1),
00876                                                     const_cast<Constant*>(C2)));
00877         }
00878         return ConstantVector::get(Res);
00879       case Instruction::UDiv:
00880         for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
00881           C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy);
00882           C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy);
00883           Res.push_back(ConstantExpr::getUDiv(const_cast<Constant*>(C1),
00884                                                     const_cast<Constant*>(C2)));
00885         }
00886         return ConstantVector::get(Res);
00887       case Instruction::SDiv:
00888         for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
00889           C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy);
00890           C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy);
00891           Res.push_back(ConstantExpr::getSDiv(const_cast<Constant*>(C1),
00892                                                     const_cast<Constant*>(C2)));
00893         }
00894         return ConstantVector::get(Res);
00895       case Instruction::FDiv:
00896         for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
00897           C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy);
00898           C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy);
00899           Res.push_back(ConstantExpr::getFDiv(const_cast<Constant*>(C1),
00900                                                     const_cast<Constant*>(C2)));
00901         }
00902         return ConstantVector::get(Res);
00903       case Instruction::URem:
00904         for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
00905           C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy);
00906           C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy);
00907           Res.push_back(ConstantExpr::getURem(const_cast<Constant*>(C1),
00908                                                     const_cast<Constant*>(C2)));
00909         }
00910         return ConstantVector::get(Res);
00911       case Instruction::SRem:
00912         for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
00913           C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy);
00914           C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy);
00915           Res.push_back(ConstantExpr::getSRem(const_cast<Constant*>(C1),
00916                                                     const_cast<Constant*>(C2)));
00917         }
00918         return ConstantVector::get(Res);
00919       case Instruction::FRem:
00920         for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
00921           C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy);
00922           C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy);
00923           Res.push_back(ConstantExpr::getFRem(const_cast<Constant*>(C1),
00924                                                     const_cast<Constant*>(C2)));
00925         }
00926         return ConstantVector::get(Res);
00927       case Instruction::And: 
00928         for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
00929           C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy);
00930           C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy);
00931           Res.push_back(ConstantExpr::getAnd(const_cast<Constant*>(C1),
00932                                                    const_cast<Constant*>(C2)));
00933         }
00934         return ConstantVector::get(Res);
00935       case Instruction::Or:
00936         for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
00937           C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy);
00938           C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy);
00939           Res.push_back(ConstantExpr::getOr(const_cast<Constant*>(C1),
00940                                                   const_cast<Constant*>(C2)));
00941         }
00942         return ConstantVector::get(Res);
00943       case Instruction::Xor:
00944         for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
00945           C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy);
00946           C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy);
00947           Res.push_back(ConstantExpr::getXor(const_cast<Constant*>(C1),
00948                                                    const_cast<Constant*>(C2)));
00949         }
00950         return ConstantVector::get(Res);
00951       case Instruction::LShr:
00952         for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
00953           C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy);
00954           C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy);
00955           Res.push_back(ConstantExpr::getLShr(const_cast<Constant*>(C1),
00956                                                     const_cast<Constant*>(C2)));
00957         }
00958         return ConstantVector::get(Res);
00959       case Instruction::AShr:
00960         for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
00961           C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy);
00962           C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy);
00963           Res.push_back(ConstantExpr::getAShr(const_cast<Constant*>(C1),
00964                                                     const_cast<Constant*>(C2)));
00965         }
00966         return ConstantVector::get(Res);
00967       case Instruction::Shl:
00968         for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
00969           C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy);
00970           C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy);
00971           Res.push_back(ConstantExpr::getShl(const_cast<Constant*>(C1),
00972                                                    const_cast<Constant*>(C2)));
00973         }
00974         return ConstantVector::get(Res);
00975       }
00976     }
00977   }
00978 
00979   if (isa<ConstantExpr>(C1)) {
00980     // There are many possible foldings we could do here.  We should probably
00981     // at least fold add of a pointer with an integer into the appropriate
00982     // getelementptr.  This will improve alias analysis a bit.
00983   } else if (isa<ConstantExpr>(C2)) {
00984     // If C2 is a constant expr and C1 isn't, flop them around and fold the
00985     // other way if possible.
00986     switch (Opcode) {
00987     case Instruction::Add:
00988     case Instruction::FAdd:
00989     case Instruction::Mul:
00990     case Instruction::FMul:
00991     case Instruction::And:
00992     case Instruction::Or:
00993     case Instruction::Xor:
00994       // No change of opcode required.
00995       return ConstantFoldBinaryInstruction(Context, Opcode, C2, C1);
00996       
00997     case Instruction::Shl:
00998     case Instruction::LShr:
00999     case Instruction::AShr:
01000     case Instruction::Sub:
01001     case Instruction::FSub:
01002     case Instruction::SDiv:
01003     case Instruction::UDiv:
01004     case Instruction::FDiv:
01005     case Instruction::URem:
01006     case Instruction::SRem:
01007     case Instruction::FRem:
01008     default:  // These instructions cannot be flopped around.
01009       break;
01010     }
01011   }
01012   
01013   // We don't know how to fold this.
01014   return 0;
01015 }
01016 
01017 /// isZeroSizedType - This type is zero sized if its an array or structure of
01018 /// zero sized types.  The only leaf zero sized type is an empty structure.
01019 static bool isMaybeZeroSizedType(const Type *Ty) {
01020   if (isa<OpaqueType>(Ty)) return true;  // Can't say.
01021   if (const StructType *STy = dyn_cast<StructType>(Ty)) {
01022 
01023     // If all of elements have zero size, this does too.
01024     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
01025       if (!isMaybeZeroSizedType(STy->getElementType(i))) return false;
01026     return true;
01027 
01028   } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
01029     return isMaybeZeroSizedType(ATy->getElementType());
01030   }
01031   return false;
01032 }
01033 
01034 /// IdxCompare - Compare the two constants as though they were getelementptr
01035 /// indices.  This allows coersion of the types to be the same thing.
01036 ///
01037 /// If the two constants are the "same" (after coersion), return 0.  If the
01038 /// first is less than the second, return -1, if the second is less than the
01039 /// first, return 1.  If the constants are not integral, return -2.
01040 ///
01041 static int IdxCompare(LLVMContext &Context, Constant *C1, Constant *C2, 
01042                       const Type *ElTy) {
01043   if (C1 == C2) return 0;
01044 
01045   // Ok, we found a different index.  If they are not ConstantInt, we can't do
01046   // anything with them.
01047   if (!isa<ConstantInt>(C1) || !isa<ConstantInt>(C2))
01048     return -2; // don't know!
01049 
01050   // Ok, we have two differing integer indices.  Sign extend them to be the same
01051   // type.  Long is always big enough, so we use it.
01052   if (C1->getType() != Type::getInt64Ty(Context))
01053     C1 = ConstantExpr::getSExt(C1, Type::getInt64Ty(Context));
01054 
01055   if (C2->getType() != Type::getInt64Ty(Context))
01056     C2 = ConstantExpr::getSExt(C2, Type::getInt64Ty(Context));
01057 
01058   if (C1 == C2) return 0;  // They are equal
01059 
01060   // If the type being indexed over is really just a zero sized type, there is
01061   // no pointer difference being made here.
01062   if (isMaybeZeroSizedType(ElTy))
01063     return -2; // dunno.
01064 
01065   // If they are really different, now that they are the same type, then we
01066   // found a difference!
01067   if (cast<ConstantInt>(C1)->getSExtValue() < 
01068       cast<ConstantInt>(C2)->getSExtValue())
01069     return -1;
01070   else
01071     return 1;
01072 }
01073 
01074 /// evaluateFCmpRelation - This function determines if there is anything we can
01075 /// decide about the two constants provided.  This doesn't need to handle simple
01076 /// things like ConstantFP comparisons, but should instead handle ConstantExprs.
01077 /// If we can determine that the two constants have a particular relation to 
01078 /// each other, we should return the corresponding FCmpInst predicate, 
01079 /// otherwise return FCmpInst::BAD_FCMP_PREDICATE. This is used below in
01080 /// ConstantFoldCompareInstruction.
01081 ///
01082 /// To simplify this code we canonicalize the relation so that the first
01083 /// operand is always the most "complex" of the two.  We consider ConstantFP
01084 /// to be the simplest, and ConstantExprs to be the most complex.
01085 static FCmpInst::Predicate evaluateFCmpRelation(LLVMContext &Context,
01086                                                 const Constant *V1, 
01087                                                 const Constant *V2) {
01088   assert(V1->getType() == V2->getType() &&
01089          "Cannot compare values of different types!");
01090 
01091   // No compile-time operations on this type yet.
01092   if (V1->getType() == Type::getPPC_FP128Ty(Context))
01093     return FCmpInst::BAD_FCMP_PREDICATE;
01094 
01095   // Handle degenerate case quickly
01096   if (V1 == V2) return FCmpInst::FCMP_OEQ;
01097 
01098   if (!isa<ConstantExpr>(V1)) {
01099     if (!isa<ConstantExpr>(V2)) {
01100       // We distilled thisUse the standard constant folder for a few cases
01101       ConstantInt *R = 0;
01102       Constant *C1 = const_cast<Constant*>(V1);
01103       Constant *C2 = const_cast<Constant*>(V2);
01104       R = dyn_cast<ConstantInt>(
01105                       ConstantExpr::getFCmp(FCmpInst::FCMP_OEQ, C1, C2));
01106       if (R && !R->isZero()) 
01107         return FCmpInst::FCMP_OEQ;
01108       R = dyn_cast<ConstantInt>(
01109                       ConstantExpr::getFCmp(FCmpInst::FCMP_OLT, C1, C2));
01110       if (R && !R->isZero()) 
01111         return FCmpInst::FCMP_OLT;
01112       R = dyn_cast<ConstantInt>(
01113                       ConstantExpr::getFCmp(FCmpInst::FCMP_OGT, C1, C2));
01114       if (R && !R->isZero()) 
01115         return FCmpInst::FCMP_OGT;
01116 
01117       // Nothing more we can do
01118       return FCmpInst::BAD_FCMP_PREDICATE;
01119     }
01120     
01121     // If the first operand is simple and second is ConstantExpr, swap operands.
01122     FCmpInst::Predicate SwappedRelation = evaluateFCmpRelation(Context, V2, V1);
01123     if (SwappedRelation != FCmpInst::BAD_FCMP_PREDICATE)
01124       return FCmpInst::getSwappedPredicate(SwappedRelation);
01125   } else {
01126     // Ok, the LHS is known to be a constantexpr.  The RHS can be any of a
01127     // constantexpr or a simple constant.
01128     const ConstantExpr *CE1 = cast<ConstantExpr>(V1);
01129     switch (CE1->getOpcode()) {
01130     case Instruction::FPTrunc:
01131     case Instruction::FPExt:
01132     case Instruction::UIToFP:
01133     case Instruction::SIToFP:
01134       // We might be able to do something with these but we don't right now.
01135       break;
01136     default:
01137       break;
01138     }
01139   }
01140   // There are MANY other foldings that we could perform here.  They will
01141   // probably be added on demand, as they seem needed.
01142   return FCmpInst::BAD_FCMP_PREDICATE;
01143 }
01144 
01145 /// evaluateICmpRelation - This function determines if there is anything we can
01146 /// decide about the two constants provided.  This doesn't need to handle simple
01147 /// things like integer comparisons, but should instead handle ConstantExprs
01148 /// and GlobalValues.  If we can determine that the two constants have a
01149 /// particular relation to each other, we should return the corresponding ICmp
01150 /// predicate, otherwise return ICmpInst::BAD_ICMP_PREDICATE.
01151 ///
01152 /// To simplify this code we canonicalize the relation so that the first
01153 /// operand is always the most "complex" of the two.  We consider simple
01154 /// constants (like ConstantInt) to be the simplest, followed by
01155 /// GlobalValues, followed by ConstantExpr's (the most complex).
01156 ///
01157 static ICmpInst::Predicate evaluateICmpRelation(LLVMContext &Context,
01158                                                 const Constant *V1, 
01159                                                 const Constant *V2,
01160                                                 bool isSigned) {
01161   assert(V1->getType() == V2->getType() &&
01162          "Cannot compare different types of values!");
01163   if (V1 == V2) return ICmpInst::ICMP_EQ;
01164 
01165   if (!isa<ConstantExpr>(V1) && !isa<GlobalValue>(V1)) {
01166     if (!isa<GlobalValue>(V2) && !isa<ConstantExpr>(V2)) {
01167       // We distilled this down to a simple case, use the standard constant
01168       // folder.
01169       ConstantInt *R = 0;
01170       Constant *C1 = const_cast<Constant*>(V1);
01171       Constant *C2 = const_cast<Constant*>(V2);
01172       ICmpInst::Predicate pred = ICmpInst::ICMP_EQ;
01173       R = dyn_cast<ConstantInt>(ConstantExpr::getICmp(pred, C1, C2));
01174       if (R && !R->isZero()) 
01175         return pred;
01176       pred = isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
01177       R = dyn_cast<ConstantInt>(ConstantExpr::getICmp(pred, C1, C2));
01178       if (R && !R->isZero())
01179         return pred;
01180       pred = isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
01181       R = dyn_cast<ConstantInt>(ConstantExpr::getICmp(pred, C1, C2));
01182       if (R && !R->isZero())
01183         return pred;
01184       
01185       // If we couldn't figure it out, bail.
01186       return ICmpInst::BAD_ICMP_PREDICATE;
01187     }
01188     
01189     // If the first operand is simple, swap operands.
01190     ICmpInst::Predicate SwappedRelation = 
01191       evaluateICmpRelation(Context, V2, V1, isSigned);
01192     if (SwappedRelation != ICmpInst::BAD_ICMP_PREDICATE)
01193       return ICmpInst::getSwappedPredicate(SwappedRelation);
01194 
01195   } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(V1)) {
01196     if (isa<ConstantExpr>(V2)) {  // Swap as necessary.
01197       ICmpInst::Predicate SwappedRelation = 
01198         evaluateICmpRelation(Context, V2, V1, isSigned);
01199       if (SwappedRelation != ICmpInst::BAD_ICMP_PREDICATE)
01200         return ICmpInst::getSwappedPredicate(SwappedRelation);
01201       else
01202         return ICmpInst::BAD_ICMP_PREDICATE;
01203     }
01204 
01205     // Now we know that the RHS is a GlobalValue or simple constant,
01206     // which (since the types must match) means that it's a ConstantPointerNull.
01207     if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) {
01208       // Don't try to decide equality of aliases.
01209       if (!isa<GlobalAlias>(CPR1) && !isa<GlobalAlias>(CPR2))
01210         if (!CPR1->hasExternalWeakLinkage() || !CPR2->hasExternalWeakLinkage())
01211           return ICmpInst::ICMP_NE;
01212     } else {
01213       assert(isa<ConstantPointerNull>(V2) && "Canonicalization guarantee!");
01214       // GlobalVals can never be null.  Don't try to evaluate aliases.
01215       if (!CPR1->hasExternalWeakLinkage() && !isa<GlobalAlias>(CPR1))
01216         return ICmpInst::ICMP_NE;
01217     }
01218   } else {
01219     // Ok, the LHS is known to be a constantexpr.  The RHS can be any of a
01220     // constantexpr, a CPR, or a simple constant.
01221     const ConstantExpr *CE1 = cast<ConstantExpr>(V1);
01222     const Constant *CE1Op0 = CE1->getOperand(0);
01223 
01224     switch (CE1->getOpcode()) {
01225     case Instruction::Trunc:
01226     case Instruction::FPTrunc:
01227     case Instruction::FPExt:
01228     case Instruction::FPToUI:
01229     case Instruction::FPToSI:
01230       break; // We can't evaluate floating point casts or truncations.
01231 
01232     case Instruction::UIToFP:
01233     case Instruction::SIToFP:
01234     case Instruction::BitCast:
01235     case Instruction::ZExt:
01236     case Instruction::SExt:
01237       // If the cast is not actually changing bits, and the second operand is a
01238       // null pointer, do the comparison with the pre-casted value.
01239       if (V2->isNullValue() &&
01240           (isa<PointerType>(CE1->getType()) || CE1->getType()->isInteger())) {
01241         bool sgnd = isSigned;
01242         if (CE1->getOpcode() == Instruction::ZExt) isSigned = false;
01243         if (CE1->getOpcode() == Instruction::SExt) isSigned = true;
01244         return evaluateICmpRelation(Context, CE1Op0,
01245                                     Constant::getNullValue(CE1Op0->getType()), 
01246                                     sgnd);
01247       }
01248 
01249       // If the dest type is a pointer type, and the RHS is a constantexpr cast
01250       // from the same type as the src of the LHS, evaluate the inputs.  This is
01251       // important for things like "icmp eq (cast 4 to int*), (cast 5 to int*)",
01252       // which happens a lot in compilers with tagged integers.
01253       if (const ConstantExpr *CE2 = dyn_cast<ConstantExpr>(V2))
01254         if (CE2->isCast() && isa<PointerType>(CE1->getType()) &&
01255             CE1->getOperand(0)->getType() == CE2->getOperand(0)->getType() &&
01256             CE1->getOperand(0)->getType()->isInteger()) {
01257           bool sgnd = isSigned;
01258           if (CE1->getOpcode() == Instruction::ZExt) isSigned = false;
01259           if (CE1->getOpcode() == Instruction::SExt) isSigned = true;
01260           return evaluateICmpRelation(Context, CE1->getOperand(0), 
01261                                       CE2->getOperand(0), sgnd);
01262         }
01263       break;
01264 
01265     case Instruction::GetElementPtr:
01266       // Ok, since this is a getelementptr, we know that the constant has a
01267       // pointer type.  Check the various cases.
01268       if (isa<ConstantPointerNull>(V2)) {
01269         // If we are comparing a GEP to a null pointer, check to see if the base
01270         // of the GEP equals the null pointer.
01271         if (const GlobalValue *GV = dyn_cast<GlobalValue>(CE1Op0)) {
01272           if (GV->hasExternalWeakLinkage())
01273             // Weak linkage GVals could be zero or not. We're comparing that
01274             // to null pointer so its greater-or-equal
01275             return isSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE;
01276           else 
01277             // If its not weak linkage, the GVal must have a non-zero address
01278             // so the result is greater-than
01279             return isSigned ? ICmpInst::ICMP_SGT :  ICmpInst::ICMP_UGT;
01280         } else if (isa<ConstantPointerNull>(CE1Op0)) {
01281           // If we are indexing from a null pointer, check to see if we have any
01282           // non-zero indices.
01283           for (unsigned i = 1, e = CE1->getNumOperands(); i != e; ++i)
01284             if (!CE1->getOperand(i)->isNullValue())
01285               // Offsetting from null, must not be equal.
01286               return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
01287           // Only zero indexes from null, must still be zero.
01288           return ICmpInst::ICMP_EQ;
01289         }
01290         // Otherwise, we can't really say if the first operand is null or not.
01291       } else if (const GlobalValue *CPR2 = dyn_cast<GlobalValue>(V2)) {
01292         if (isa<ConstantPointerNull>(CE1Op0)) {
01293           if (CPR2->hasExternalWeakLinkage())
01294             // Weak linkage GVals could be zero or not. We're comparing it to
01295             // a null pointer, so its less-or-equal
01296             return isSigned ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
01297           else
01298             // If its not weak linkage, the GVal must have a non-zero address
01299             // so the result is less-than
01300             return isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
01301         } else if (const GlobalValue *CPR1 = dyn_cast<GlobalValue>(CE1Op0)) {
01302           if (CPR1 == CPR2) {
01303             // If this is a getelementptr of the same global, then it must be
01304             // different.  Because the types must match, the getelementptr could
01305             // only have at most one index, and because we fold getelementptr's
01306             // with a single zero index, it must be nonzero.
01307             assert(CE1->getNumOperands() == 2 &&
01308                    !CE1->getOperand(1)->isNullValue() &&
01309                    "Suprising getelementptr!");
01310             return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
01311           } else {
01312             // If they are different globals, we don't know what the value is,
01313             // but they can't be equal.
01314             return ICmpInst::ICMP_NE;
01315           }
01316         }
01317       } else {
01318         const ConstantExpr *CE2 = cast<ConstantExpr>(V2);
01319         const Constant *CE2Op0 = CE2->getOperand(0);
01320 
01321         // There are MANY other foldings that we could perform here.  They will
01322         // probably be added on demand, as they seem needed.
01323         switch (CE2->getOpcode()) {
01324         default: break;
01325         case Instruction::GetElementPtr:
01326           // By far the most common case to handle is when the base pointers are
01327           // obviously to the same or different globals.
01328           if (isa<GlobalValue>(CE1Op0) && isa<GlobalValue>(CE2Op0)) {
01329             if (CE1Op0 != CE2Op0) // Don't know relative ordering, but not equal
01330               return ICmpInst::ICMP_NE;
01331             // Ok, we know that both getelementptr instructions are based on the
01332             // same global.  From this, we can precisely determine the relative
01333             // ordering of the resultant pointers.
01334             unsigned i = 1;
01335 
01336             // Compare all of the operands the GEP's have in common.
01337             gep_type_iterator GTI = gep_type_begin(CE1);
01338             for (;i != CE1->getNumOperands() && i != CE2->getNumOperands();
01339                  ++i, ++GTI)
01340               switch (IdxCompare(Context, CE1->getOperand(i),
01341                                  CE2->getOperand(i), GTI.getIndexedType())) {
01342               case -1: return isSigned ? ICmpInst::ICMP_SLT:ICmpInst::ICMP_ULT;
01343               case 1:  return isSigned ? ICmpInst::ICMP_SGT:ICmpInst::ICMP_UGT;
01344               case -2: return ICmpInst::BAD_ICMP_PREDICATE;
01345               }
01346 
01347             // Ok, we ran out of things they have in common.  If any leftovers
01348             // are non-zero then we have a difference, otherwise we are equal.
01349             for (; i < CE1->getNumOperands(); ++i)
01350               if (!CE1->getOperand(i)->isNullValue()) {
01351                 if (isa<ConstantInt>(CE1->getOperand(i)))
01352                   return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
01353                 else
01354                   return ICmpInst::BAD_ICMP_PREDICATE; // Might be equal.
01355               }
01356 
01357             for (; i < CE2->getNumOperands(); ++i)
01358               if (!CE2->getOperand(i)->isNullValue()) {
01359                 if (isa<ConstantInt>(CE2->getOperand(i)))
01360                   return isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
01361                 else
01362                   return ICmpInst::BAD_ICMP_PREDICATE; // Might be equal.
01363               }
01364             return ICmpInst::ICMP_EQ;
01365           }
01366         }
01367       }
01368     default:
01369       break;
01370     }
01371   }
01372 
01373   return ICmpInst::BAD_ICMP_PREDICATE;
01374 }
01375 
01376 Constant *llvm::ConstantFoldCompareInstruction(LLVMContext &Context,
01377                                                unsigned short pred, 
01378                                                const Constant *C1, 
01379                                                const Constant *C2) {
01380   const Type *ResultTy;
01381   if (const VectorType *VT = dyn_cast<VectorType>(C1->getType()))
01382     ResultTy = VectorType::get(Type::getInt1Ty(Context), VT->getNumElements());
01383   else
01384     ResultTy = Type::getInt1Ty(Context);
01385 
01386   // Fold FCMP_FALSE/FCMP_TRUE unconditionally.
01387   if (pred == FCmpInst::FCMP_FALSE)
01388     return Constant::getNullValue(ResultTy);
01389 
01390   if (pred == FCmpInst::FCMP_TRUE)
01391     return Constant::getAllOnesValue(ResultTy);
01392 
01393   // Handle some degenerate cases first
01394   if (isa<UndefValue>(C1) || isa<UndefValue>(C2))
01395     return UndefValue::get(ResultTy);
01396 
01397   // No compile-time operations on this type yet.
01398   if (C1->getType() == Type::getPPC_FP128Ty(Context))
01399     return 0;
01400 
01401   // icmp eq/ne(null,GV) -> false/true
01402   if (C1->isNullValue()) {
01403     if (const GlobalValue *GV = dyn_cast<GlobalValue>(C2))
01404       // Don't try to evaluate aliases.  External weak GV can be null.
01405       if (!isa<GlobalAlias>(GV) && !GV->hasExternalWeakLinkage()) {
01406         if (pred == ICmpInst::ICMP_EQ)
01407           return ConstantInt::getFalse(Context);
01408         else if (pred == ICmpInst::ICMP_NE)
01409           return ConstantInt::getTrue(Context);
01410       }
01411   // icmp eq/ne(GV,null) -> false/true
01412   } else if (C2->isNullValue()) {
01413     if (const GlobalValue *GV = dyn_cast<GlobalValue>(C1))
01414       // Don't try to evaluate aliases.  External weak GV can be null.
01415       if (!isa<GlobalAlias>(GV) && !GV->hasExternalWeakLinkage()) {
01416         if (pred == ICmpInst::ICMP_EQ)
01417           return ConstantInt::getFalse(Context);
01418         else if (pred == ICmpInst::ICMP_NE)
01419           return ConstantInt::getTrue(Context);
01420       }
01421   }
01422 
01423   if (isa<ConstantInt>(C1) && isa<ConstantInt>(C2)) {
01424     APInt V1 = cast<ConstantInt>(C1)->getValue();
01425     APInt V2 = cast<ConstantInt>(C2)->getValue();
01426     switch (pred) {
01427     default: llvm_unreachable("Invalid ICmp Predicate"); return 0;
01428     case ICmpInst::ICMP_EQ:
01429       return ConstantInt::get(Type::getInt1Ty(Context), V1 == V2);
01430     case ICmpInst::ICMP_NE: 
01431       return ConstantInt::get(Type::getInt1Ty(Context), V1 != V2);
01432     case ICmpInst::ICMP_SLT:
01433       return ConstantInt::get(Type::getInt1Ty(Context), V1.slt(V2));
01434     case ICmpInst::ICMP_SGT:
01435       return ConstantInt::get(Type::getInt1Ty(Context), V1.sgt(V2));
01436     case ICmpInst::ICMP_SLE:
01437       return ConstantInt::get(Type::getInt1Ty(Context), V1.sle(V2));
01438     case ICmpInst::ICMP_SGE:
01439       return ConstantInt::get(Type::getInt1Ty(Context), V1.sge(V2));
01440     case ICmpInst::ICMP_ULT:
01441       return ConstantInt::get(Type::getInt1Ty(Context), V1.ult(V2));
01442     case ICmpInst::ICMP_UGT:
01443       return ConstantInt::get(Type::getInt1Ty(Context), V1.ugt(V2));
01444     case ICmpInst::ICMP_ULE:
01445       return ConstantInt::get(Type::getInt1Ty(Context), V1.ule(V2));
01446     case ICmpInst::ICMP_UGE:
01447       return ConstantInt::get(Type::getInt1Ty(Context), V1.uge(V2));
01448     }
01449   } else if (isa<ConstantFP>(C1) && isa<ConstantFP>(C2)) {
01450     APFloat C1V = cast<ConstantFP>(C1)->getValueAPF();
01451     APFloat C2V = cast<ConstantFP>(C2)->getValueAPF();
01452     APFloat::cmpResult R = C1V.compare(C2V);
01453     switch (pred) {
01454     default: llvm_unreachable("Invalid FCmp Predicate"); return 0;
01455     case FCmpInst::FCMP_FALSE: return ConstantInt::getFalse(Context);
01456     case FCmpInst::FCMP_TRUE:  return ConstantInt::getTrue(Context);
01457     case FCmpInst::FCMP_UNO:
01458       return ConstantInt::get(Type::getInt1Ty(Context), R==APFloat::cmpUnordered);
01459     case FCmpInst::FCMP_ORD:
01460       return ConstantInt::get(Type::getInt1Ty(Context), R!=APFloat::cmpUnordered);
01461     case FCmpInst::FCMP_UEQ:
01462       return ConstantInt::get(Type::getInt1Ty(Context), R==APFloat::cmpUnordered ||
01463                                             R==APFloat::cmpEqual);
01464     case FCmpInst::FCMP_OEQ:   
01465       return ConstantInt::get(Type::getInt1Ty(Context), R==APFloat::cmpEqual);
01466     case FCmpInst::FCMP_UNE:
01467       return ConstantInt::get(Type::getInt1Ty(Context), R!=APFloat::cmpEqual);
01468     case FCmpInst::FCMP_ONE:   
01469       return ConstantInt::get(Type::getInt1Ty(Context), R==APFloat::cmpLessThan ||
01470                                             R==APFloat::cmpGreaterThan);
01471     case FCmpInst::FCMP_ULT: 
01472       return ConstantInt::get(Type::getInt1Ty(Context), R==APFloat::cmpUnordered ||
01473                                             R==APFloat::cmpLessThan);
01474     case FCmpInst::FCMP_OLT:   
01475       return ConstantInt::get(Type::getInt1Ty(Context), R==APFloat::cmpLessThan);
01476     case FCmpInst::FCMP_UGT:
01477       return ConstantInt::get(Type::getInt1Ty(Context), R==APFloat::cmpUnordered ||
01478                                             R==APFloat::cmpGreaterThan);
01479     case FCmpInst::FCMP_OGT:
01480       return ConstantInt::get(Type::getInt1Ty(Context), R==APFloat::cmpGreaterThan);
01481     case FCmpInst::FCMP_ULE:
01482       return ConstantInt::get(Type::getInt1Ty(Context), R!=APFloat::cmpGreaterThan);
01483     case FCmpInst::FCMP_OLE: 
01484       return ConstantInt::get(Type::getInt1Ty(Context), R==APFloat::cmpLessThan ||
01485                                             R==APFloat::cmpEqual);
01486     case FCmpInst::FCMP_UGE:
01487       return ConstantInt::get(Type::getInt1Ty(Context), R!=APFloat::cmpLessThan);
01488     case FCmpInst::FCMP_OGE: 
01489       return ConstantInt::get(Type::getInt1Ty(Context), R==APFloat::cmpGreaterThan ||
01490                                             R==APFloat::cmpEqual);
01491     }
01492   } else if (isa<VectorType>(C1->getType())) {
01493     SmallVector<Constant*, 16> C1Elts, C2Elts;
01494     C1->getVectorElements(Context, C1Elts);
01495     C2->getVectorElements(Context, C2Elts);
01496     
01497     // If we can constant fold the comparison of each element, constant fold
01498     // the whole vector comparison.
01499     SmallVector<Constant*, 4> ResElts;
01500     for (unsigned i = 0, e = C1Elts.size(); i != e; ++i) {
01501       // Compare the elements, producing an i1 result or constant expr.
01502       ResElts.push_back(
01503                     ConstantExpr::getCompare(pred, C1Elts[i], C2Elts[i]));
01504     }
01505     return ConstantVector::get(&ResElts[0], ResElts.size());
01506   }
01507 
01508   if (C1->getType()->isFloatingPoint()) {
01509     int Result = -1;  // -1 = unknown, 0 = known false, 1 = known true.
01510     switch (evaluateFCmpRelation(Context, C1, C2)) {
01511     default: llvm_unreachable("Unknown relation!");
01512     case FCmpInst::FCMP_UNO:
01513     case FCmpInst::FCMP_ORD:
01514     case FCmpInst::FCMP_UEQ:
01515     case FCmpInst::FCMP_UNE:
01516     case FCmpInst::FCMP_ULT:
01517     case FCmpInst::FCMP_UGT:
01518     case FCmpInst::FCMP_ULE:
01519     case FCmpInst::FCMP_UGE:
01520     case FCmpInst::FCMP_TRUE:
01521     case FCmpInst::FCMP_FALSE:
01522     case FCmpInst::BAD_FCMP_PREDICATE:
01523       break; // Couldn't determine anything about these constants.
01524     case FCmpInst::FCMP_OEQ: // We know that C1 == C2
01525       Result = (pred == FCmpInst::FCMP_UEQ || pred == FCmpInst::FCMP_OEQ ||
01526                 pred == FCmpInst::FCMP_ULE || pred == FCmpInst::FCMP_OLE ||
01527                 pred == FCmpInst::FCMP_UGE || pred == FCmpInst::FCMP_OGE);
01528       break;
01529     case FCmpInst::FCMP_OLT: // We know that C1 < C2
01530       Result = (pred == FCmpInst::FCMP_UNE || pred == FCmpInst::FCMP_ONE ||
01531                 pred == FCmpInst::FCMP_ULT || pred == FCmpInst::FCMP_OLT ||
01532                 pred == FCmpInst::FCMP_ULE || pred == FCmpInst::FCMP_OLE);
01533       break;
01534     case FCmpInst::FCMP_OGT: // We know that C1 > C2
01535       Result = (pred == FCmpInst::FCMP_UNE || pred == FCmpInst::FCMP_ONE ||
01536                 pred == FCmpInst::FCMP_UGT || pred == FCmpInst::FCMP_OGT ||
01537                 pred == FCmpInst::FCMP_UGE || pred == FCmpInst::FCMP_OGE);
01538       break;
01539     case FCmpInst::FCMP_OLE: // We know that C1 <= C2
01540       // We can only partially decide this relation.
01541       if (pred == FCmpInst::FCMP_UGT || pred == FCmpInst::FCMP_OGT) 
01542         Result = 0;
01543       else if (pred == FCmpInst::FCMP_ULT || pred == FCmpInst::FCMP_OLT) 
01544         Result = 1;
01545       break;
01546     case FCmpInst::FCMP_OGE: // We known that C1 >= C2
01547       // We can only partially decide this relation.
01548       if (pred == FCmpInst::FCMP_ULT || pred == FCmpInst::FCMP_OLT) 
01549         Result = 0;
01550       else if (pred == FCmpInst::FCMP_UGT || pred == FCmpInst::FCMP_OGT) 
01551         Result = 1;
01552       break;
01553     case ICmpInst::ICMP_NE: // We know that C1 != C2
01554       // We can only partially decide this relation.
01555       if (pred == FCmpInst::FCMP_OEQ || pred == FCmpInst::FCMP_UEQ) 
01556         Result = 0;
01557       else if (pred == FCmpInst::FCMP_ONE || pred == FCmpInst::FCMP_UNE) 
01558         Result = 1;
01559       break;
01560     }
01561     
01562     // If we evaluated the result, return it now.
01563     if (Result != -1)
01564       return ConstantInt::get(Type::getInt1Ty(Context), Result);
01565 
01566   } else {
01567     // Evaluate the relation between the two constants, per the predicate.
01568     int Result = -1;  // -1 = unknown, 0 = known false, 1 = known true.
01569     switch (evaluateICmpRelation(Context, C1, C2, CmpInst::isSigned(pred))) {
01570     default: llvm_unreachable("Unknown relational!");
01571     case ICmpInst::BAD_ICMP_PREDICATE:
01572       break;  // Couldn't determine anything about these constants.
01573     case ICmpInst::ICMP_EQ:   // We know the constants are equal!
01574       // If we know the constants are equal, we can decide the result of this
01575       // computation precisely.
01576       Result = (pred == ICmpInst::ICMP_EQ  ||
01577                 pred == ICmpInst::ICMP_ULE ||
01578                 pred == ICmpInst::ICMP_SLE ||
01579                 pred == ICmpInst::ICMP_UGE ||
01580                 pred == ICmpInst::ICMP_SGE);
01581       break;
01582     case ICmpInst::ICMP_ULT:
01583       // If we know that C1 < C2, we can decide the result of this computation
01584       // precisely.
01585       Result = (pred == ICmpInst::ICMP_ULT ||
01586                 pred == ICmpInst::ICMP_NE  ||
01587                 pred == ICmpInst::ICMP_ULE);
01588       break;
01589     case ICmpInst::ICMP_SLT:
01590       // If we know that C1 < C2, we can decide the result of this computation
01591       // precisely.
01592       Result = (pred == ICmpInst::ICMP_SLT ||
01593                 pred == ICmpInst::ICMP_NE  ||
01594                 pred == ICmpInst::ICMP_SLE);
01595       break;
01596     case ICmpInst::ICMP_UGT:
01597       // If we know that C1 > C2, we can decide the result of this computation
01598       // precisely.
01599       Result = (pred == ICmpInst::ICMP_UGT ||
01600                 pred == ICmpInst::ICMP_NE  ||
01601                 pred == ICmpInst::ICMP_UGE);
01602       break;
01603     case ICmpInst::ICMP_SGT:
01604       // If we know that C1 > C2, we can decide the result of this computation
01605       // precisely.
01606       Result = (pred == ICmpInst::ICMP_SGT ||
01607                 pred == ICmpInst::ICMP_NE  ||
01608                 pred == ICmpInst::ICMP_SGE);
01609       break;
01610     case ICmpInst::ICMP_ULE:
01611       // If we know that C1 <= C2, we can only partially decide this relation.
01612       if (pred == ICmpInst::ICMP_UGT) Result = 0;
01613       if (pred == ICmpInst::ICMP_ULT) Result = 1;
01614       break;
01615     case ICmpInst::ICMP_SLE:
01616       // If we know that C1 <= C2, we can only partially decide this relation.
01617       if (pred == ICmpInst::ICMP_SGT) Result = 0;
01618       if (pred == ICmpInst::ICMP_SLT) Result = 1;
01619       break;
01620 
01621     case ICmpInst::ICMP_UGE:
01622       // If we know that C1 >= C2, we can only partially decide this relation.
01623       if (pred == ICmpInst::ICMP_ULT) Result = 0;
01624       if (pred == ICmpInst::ICMP_UGT) Result = 1;
01625       break;
01626     case ICmpInst::ICMP_SGE:
01627       // If we know that C1 >= C2, we can only partially decide this relation.
01628       if (pred == ICmpInst::ICMP_SLT) Result = 0;
01629       if (pred == ICmpInst::ICMP_SGT) Result = 1;
01630       break;
01631 
01632     case ICmpInst::ICMP_NE:
01633       // If we know that C1 != C2, we can only partially decide this relation.
01634       if (pred == ICmpInst::ICMP_EQ) Result = 0;
01635       if (pred == ICmpInst::ICMP_NE) Result = 1;
01636       break;
01637     }
01638     
01639     // If we evaluated the result, return it now.
01640     if (Result != -1)
01641       return ConstantInt::get(Type::getInt1Ty(Context), Result);
01642     
01643     if (!isa<ConstantExpr>(C1) && isa<ConstantExpr>(C2)) {
01644       // If C2 is a constant expr and C1 isn't, flip them around and fold the
01645       // other way if possible.
01646       switch (pred) {
01647       case ICmpInst::ICMP_EQ:
01648       case ICmpInst::ICMP_NE:
01649         // No change of predicate required.
01650         return ConstantFoldCompareInstruction(Context, pred, C2, C1);
01651 
01652       case ICmpInst::ICMP_ULT:
01653       case ICmpInst::ICMP_SLT:
01654       case ICmpInst::ICMP_UGT:
01655       case ICmpInst::ICMP_SGT:
01656       case ICmpInst::ICMP_ULE:
01657       case ICmpInst::ICMP_SLE:
01658       case ICmpInst::ICMP_UGE:
01659       case ICmpInst::ICMP_SGE:
01660         // Change the predicate as necessary to swap the operands.
01661         pred = ICmpInst::getSwappedPredicate((ICmpInst::Predicate)pred);
01662         return ConstantFoldCompareInstruction(Context, pred, C2, C1);
01663 
01664       default:  // These predicates cannot be flopped around.
01665         break;
01666       }
01667     }
01668   }
01669   return 0;
01670   }
01671 
01672 Constant *llvm::ConstantFoldGetElementPtr(LLVMContext &Context, 
01673                                           const Constant *C,
01674                                           Constant* const *Idxs,
01675                                           unsigned NumIdx) {
01676   if (NumIdx == 0 ||
01677       (NumIdx == 1 && Idxs[0]->isNullValue()))
01678     return const_cast<Constant*>(C);
01679 
01680   if (isa<UndefValue>(C)) {
01681     const PointerType *Ptr = cast<PointerType>(C->getType());
01682     const Type *Ty = GetElementPtrInst::getIndexedType(Ptr,
01683                                                        (Value **)Idxs,
01684                                                        (Value **)Idxs+NumIdx);
01685     assert(Ty != 0 && "Invalid indices for GEP!");
01686     return UndefValue::get(PointerType::get(Ty, Ptr->getAddressSpace()));
01687   }
01688 
01689   Constant *Idx0 = Idxs[0];
01690   if (C->isNullValue()) {
01691     bool isNull = true;
01692     for (unsigned i = 0, e = NumIdx; i != e; ++i)
01693       if (!Idxs[i]->isNullValue()) {
01694         isNull = false;
01695         break;
01696       }
01697     if (isNull) {
01698       const PointerType *Ptr = cast<PointerType>(C->getType());
01699       const Type *Ty = GetElementPtrInst::getIndexedType(Ptr,
01700                                                          (Value**)Idxs,
01701                                                          (Value**)Idxs+NumIdx);
01702       assert(Ty != 0 && "Invalid indices for GEP!");
01703       return  ConstantPointerNull::get(
01704                             PointerType::get(Ty,Ptr->getAddressSpace()));
01705     }
01706   }
01707 
01708   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(const_cast<Constant*>(C))) {
01709     // Combine Indices - If the source pointer to this getelementptr instruction
01710     // is a getelementptr instruction, combine the indices of the two
01711     // getelementptr instructions into a single instruction.
01712     //
01713     if (CE->getOpcode() == Instruction::GetElementPtr) {
01714       const Type *LastTy = 0;
01715       for (gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
01716            I != E; ++I)
01717         LastTy = *I;
01718 
01719       if ((LastTy && isa<ArrayType>(LastTy)) || Idx0->isNullValue()) {
01720         SmallVector<Value*, 16> NewIndices;
01721         NewIndices.reserve(NumIdx + CE->getNumOperands());
01722         for (unsigned i = 1, e = CE->getNumOperands()-1; i != e; ++i)
01723           NewIndices.push_back(CE->getOperand(i));
01724 
01725         // Add the last index of the source with the first index of the new GEP.
01726         // Make sure to handle the case when they are actually different types.
01727         Constant *Combined = CE->getOperand(CE->getNumOperands()-1);
01728         // Otherwise it must be an array.
01729         if (!Idx0->isNullValue()) {
01730           const Type *IdxTy = Combined->getType();
01731           if (IdxTy != Idx0->getType()) {
01732             Constant *C1 =
01733               ConstantExpr::getSExtOrBitCast(Idx0, Type::getInt64Ty(Context));
01734             Constant *C2 = ConstantExpr::getSExtOrBitCast(Combined, 
01735                                                           Type::getInt64Ty(Context));
01736             Combined = ConstantExpr::get(Instruction::Add, C1, C2);
01737           } else {
01738             Combined =
01739               ConstantExpr::get(Instruction::Add, Idx0, Combined);
01740           }
01741         }
01742 
01743         NewIndices.push_back(Combined);
01744         NewIndices.insert(NewIndices.end(), Idxs+1, Idxs+NumIdx);
01745         return ConstantExpr::getGetElementPtr(CE->getOperand(0),
01746                                               &NewIndices[0],
01747                                               NewIndices.size());
01748       }
01749     }
01750 
01751     // Implement folding of:
01752     //    int* getelementptr ([2 x int]* cast ([3 x int]* %X to [2 x int]*),
01753     //                        long 0, long 0)
01754     // To: int* getelementptr ([3 x int]* %X, long 0, long 0)
01755     //
01756     if (CE->isCast() && NumIdx > 1 && Idx0->isNullValue()) {
01757       if (const PointerType *SPT =
01758           dyn_cast<PointerType>(CE->getOperand(0)->getType()))
01759         if (const ArrayType *SAT = dyn_cast<ArrayType>(SPT->getElementType()))
01760           if (const ArrayType *CAT =
01761         dyn_cast<ArrayType>(cast<PointerType>(C->getType())->getElementType()))
01762             if (CAT->getElementType() == SAT->getElementType())
01763               return ConstantExpr::getGetElementPtr(
01764                       (Constant*)CE->getOperand(0), Idxs, NumIdx);
01765     }
01766     
01767     // Fold: getelementptr (i8* inttoptr (i64 1 to i8*), i32 -1)
01768     // Into: inttoptr (i64 0 to i8*)
01769     // This happens with pointers to member functions in C++.
01770     if (CE->getOpcode() == Instruction::IntToPtr && NumIdx == 1 &&
01771         isa<ConstantInt>(CE->getOperand(0)) && isa<ConstantInt>(Idxs[0]) &&
01772         cast<PointerType>(CE->getType())->getElementType() == Type::getInt8Ty(Context)) {
01773       Constant *Base = CE->getOperand(0);
01774       Constant *Offset = Idxs[0];
01775       
01776       // Convert the smaller integer to the larger type.
01777       if (Offset->getType()->getPrimitiveSizeInBits() < 
01778           Base->getType()->getPrimitiveSizeInBits())
01779         Offset = ConstantExpr::getSExt(Offset, Base->getType());
01780       else if (Base->getType()->getPrimitiveSizeInBits() <
01781                Offset->getType()->getPrimitiveSizeInBits())
01782         Base = ConstantExpr::getZExt(Base, Offset->getType());
01783       
01784       Base = ConstantExpr::getAdd(Base, Offset);
01785       return ConstantExpr::getIntToPtr(Base, CE->getType());
01786     }
01787   }
01788   return 0;
01789 }
01790