LLVM API Documentation

ConstantFolding.cpp

Go to the documentation of this file.
00001 //===-- ConstantFolding.cpp - Analyze constant folding possibilities ------===//
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 family of functions determines the possibility of performing constant
00011 // folding.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #include "llvm/Analysis/ConstantFolding.h"
00016 #include "llvm/Constants.h"
00017 #include "llvm/DerivedTypes.h"
00018 #include "llvm/Function.h"
00019 #include "llvm/GlobalVariable.h"
00020 #include "llvm/Instructions.h"
00021 #include "llvm/Intrinsics.h"
00022 #include "llvm/LLVMContext.h"
00023 #include "llvm/ADT/SmallVector.h"
00024 #include "llvm/ADT/StringMap.h"
00025 #include "llvm/Target/TargetData.h"
00026 #include "llvm/Support/ErrorHandling.h"
00027 #include "llvm/Support/GetElementPtrTypeIterator.h"
00028 #include "llvm/Support/MathExtras.h"
00029 #include <cerrno>
00030 #include <cmath>
00031 using namespace llvm;
00032 
00033 //===----------------------------------------------------------------------===//
00034 // Constant Folding internal helper functions
00035 //===----------------------------------------------------------------------===//
00036 
00037 /// IsConstantOffsetFromGlobal - If this constant is actually a constant offset
00038 /// from a global, return the global and the constant.  Because of
00039 /// constantexprs, this function is recursive.
00040 static bool IsConstantOffsetFromGlobal(Constant *C, GlobalValue *&GV,
00041                                        int64_t &Offset, const TargetData &TD) {
00042   // Trivial case, constant is the global.
00043   if ((GV = dyn_cast<GlobalValue>(C))) {
00044     Offset = 0;
00045     return true;
00046   }
00047   
00048   // Otherwise, if this isn't a constant expr, bail out.
00049   ConstantExpr *CE = dyn_cast<ConstantExpr>(C);
00050   if (!CE) return false;
00051   
00052   // Look through ptr->int and ptr->ptr casts.
00053   if (CE->getOpcode() == Instruction::PtrToInt ||
00054       CE->getOpcode() == Instruction::BitCast)
00055     return IsConstantOffsetFromGlobal(CE->getOperand(0), GV, Offset, TD);
00056   
00057   // i32* getelementptr ([5 x i32]* @a, i32 0, i32 5)    
00058   if (CE->getOpcode() == Instruction::GetElementPtr) {
00059     // Cannot compute this if the element type of the pointer is missing size
00060     // info.
00061     if (!cast<PointerType>(CE->getOperand(0)->getType())
00062                  ->getElementType()->isSized())
00063       return false;
00064     
00065     // If the base isn't a global+constant, we aren't either.
00066     if (!IsConstantOffsetFromGlobal(CE->getOperand(0), GV, Offset, TD))
00067       return false;
00068     
00069     // Otherwise, add any offset that our operands provide.
00070     gep_type_iterator GTI = gep_type_begin(CE);
00071     for (User::const_op_iterator i = CE->op_begin() + 1, e = CE->op_end();
00072          i != e; ++i, ++GTI) {
00073       ConstantInt *CI = dyn_cast<ConstantInt>(*i);
00074       if (!CI) return false;  // Index isn't a simple constant?
00075       if (CI->getZExtValue() == 0) continue;  // Not adding anything.
00076       
00077       if (const StructType *ST = dyn_cast<StructType>(*GTI)) {
00078         // N = N + Offset
00079         Offset += TD.getStructLayout(ST)->getElementOffset(CI->getZExtValue());
00080       } else {
00081         const SequentialType *SQT = cast<SequentialType>(*GTI);
00082         Offset += TD.getTypeAllocSize(SQT->getElementType())*CI->getSExtValue();
00083       }
00084     }
00085     return true;
00086   }
00087   
00088   return false;
00089 }
00090 
00091 
00092 /// SymbolicallyEvaluateBinop - One of Op0/Op1 is a constant expression.
00093 /// Attempt to symbolically evaluate the result of a binary operator merging
00094 /// these together.  If target data info is available, it is provided as TD, 
00095 /// otherwise TD is null.
00096 static Constant *SymbolicallyEvaluateBinop(unsigned Opc, Constant *Op0,
00097                                            Constant *Op1, const TargetData *TD,
00098                                            LLVMContext &Context){
00099   // SROA
00100   
00101   // Fold (and 0xffffffff00000000, (shl x, 32)) -> shl.
00102   // Fold (lshr (or X, Y), 32) -> (lshr [X/Y], 32) if one doesn't contribute
00103   // bits.
00104   
00105   
00106   // If the constant expr is something like &A[123] - &A[4].f, fold this into a
00107   // constant.  This happens frequently when iterating over a global array.
00108   if (Opc == Instruction::Sub && TD) {
00109     GlobalValue *GV1, *GV2;
00110     int64_t Offs1, Offs2;
00111     
00112     if (IsConstantOffsetFromGlobal(Op0, GV1, Offs1, *TD))
00113       if (IsConstantOffsetFromGlobal(Op1, GV2, Offs2, *TD) &&
00114           GV1 == GV2) {
00115         // (&GV+C1) - (&GV+C2) -> C1-C2, pointer arithmetic cannot overflow.
00116         return ConstantInt::get(Op0->getType(), Offs1-Offs2);
00117       }
00118   }
00119     
00120   return 0;
00121 }
00122 
00123 /// SymbolicallyEvaluateGEP - If we can symbolically evaluate the specified GEP
00124 /// constant expression, do so.
00125 static Constant *SymbolicallyEvaluateGEP(Constant* const* Ops, unsigned NumOps,
00126                                          const Type *ResultTy,
00127                                          LLVMContext &Context,
00128                                          const TargetData *TD) {
00129   Constant *Ptr = Ops[0];
00130   if (!TD || !cast<PointerType>(Ptr->getType())->getElementType()->isSized())
00131     return 0;
00132 
00133   unsigned BitWidth = TD->getTypeSizeInBits(TD->getIntPtrType(Context));
00134   APInt BasePtr(BitWidth, 0);
00135   bool BaseIsInt = true;
00136   if (!Ptr->isNullValue()) {
00137     // If this is a inttoptr from a constant int, we can fold this as the base,
00138     // otherwise we can't.
00139     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr))
00140       if (CE->getOpcode() == Instruction::IntToPtr)
00141         if (ConstantInt *Base = dyn_cast<ConstantInt>(CE->getOperand(0))) {
00142           BasePtr = Base->getValue();
00143           BasePtr.zextOrTrunc(BitWidth);
00144         }
00145     
00146     if (BasePtr == 0)
00147       BaseIsInt = false;
00148   }
00149 
00150   // If this is a constant expr gep that is effectively computing an
00151   // "offsetof", fold it into 'cast int Size to T*' instead of 'gep 0, 0, 12'
00152   for (unsigned i = 1; i != NumOps; ++i)
00153     if (!isa<ConstantInt>(Ops[i]))
00154       return 0;
00155   
00156   APInt Offset = APInt(BitWidth,
00157                        TD->getIndexedOffset(Ptr->getType(),
00158                                             (Value**)Ops+1, NumOps-1));
00159   // If the base value for this address is a literal integer value, fold the
00160   // getelementptr to the resulting integer value casted to the pointer type.
00161   if (BaseIsInt) {
00162     Constant *C = ConstantInt::get(Context, Offset+BasePtr);
00163     return ConstantExpr::getIntToPtr(C, ResultTy);
00164   }
00165 
00166   // Otherwise form a regular getelementptr. Recompute the indices so that
00167   // we eliminate over-indexing of the notional static type array bounds.
00168   // This makes it easy to determine if the getelementptr is "inbounds".
00169   // Also, this helps GlobalOpt do SROA on GlobalVariables.
00170   const Type *Ty = Ptr->getType();
00171   SmallVector<Constant*, 32> NewIdxs;
00172   do {
00173     if (const SequentialType *ATy = dyn_cast<SequentialType>(Ty)) {
00174       // The only pointer indexing we'll do is on the first index of the GEP.
00175       if (isa<PointerType>(ATy) && !NewIdxs.empty())
00176         break;
00177       // Determine which element of the array the offset points into.
00178       APInt ElemSize(BitWidth, TD->getTypeAllocSize(ATy->getElementType()));
00179       if (ElemSize == 0)
00180         return 0;
00181       APInt NewIdx = Offset.udiv(ElemSize);
00182       Offset -= NewIdx * ElemSize;
00183       NewIdxs.push_back(ConstantInt::get(TD->getIntPtrType(Context), NewIdx));
00184       Ty = ATy->getElementType();
00185     } else if (const StructType *STy = dyn_cast<StructType>(Ty)) {
00186       // Determine which field of the struct the offset points into. The
00187       // getZExtValue is at least as safe as the StructLayout API because we
00188       // know the offset is within the struct at this point.
00189       const StructLayout &SL = *TD->getStructLayout(STy);
00190       unsigned ElIdx = SL.getElementContainingOffset(Offset.getZExtValue());
00191       NewIdxs.push_back(ConstantInt::get(Type::getInt32Ty(Context), ElIdx));
00192       Offset -= APInt(BitWidth, SL.getElementOffset(ElIdx));
00193       Ty = STy->getTypeAtIndex(ElIdx);
00194     } else {
00195       // We've reached some non-indexable type.
00196       break;
00197     }
00198   } while (Ty != cast<PointerType>(ResultTy)->getElementType());
00199 
00200   // If we haven't used up the entire offset by descending the static
00201   // type, then the offset is pointing into the middle of an indivisible
00202   // member, so we can't simplify it.
00203   if (Offset != 0)
00204     return 0;
00205 
00206   // If the base is the start of a GlobalVariable and all the array indices
00207   // remain in their static bounds, the GEP is inbounds. We can check that
00208   // all indices are in bounds by just checking the first index only
00209   // because we've just normalized all the indices.
00210   Constant *C = isa<GlobalVariable>(Ptr) && NewIdxs[0]->isNullValue() ?
00211     ConstantExpr::getInBoundsGetElementPtr(Ptr, &NewIdxs[0], NewIdxs.size()) :
00212     ConstantExpr::getGetElementPtr(Ptr, &NewIdxs[0], NewIdxs.size());
00213   assert(cast<PointerType>(C->getType())->getElementType() == Ty &&
00214          "Computed GetElementPtr has unexpected type!");
00215 
00216   // If we ended up indexing a member with a type that doesn't match
00217   // the type of what the original indices indexed, add a cast.
00218   if (Ty != cast<PointerType>(ResultTy)->getElementType())
00219     C = ConstantExpr::getBitCast(C, ResultTy);
00220 
00221   return C;
00222 }
00223 
00224 /// FoldBitCast - Constant fold bitcast, symbolically evaluating it with 
00225 /// targetdata.  Return 0 if unfoldable.
00226 static Constant *FoldBitCast(Constant *C, const Type *DestTy,
00227                              const TargetData &TD, LLVMContext &Context) {
00228   // If this is a bitcast from constant vector -> vector, fold it.
00229   if (ConstantVector *CV = dyn_cast<ConstantVector>(C)) {
00230     if (const VectorType *DestVTy = dyn_cast<VectorType>(DestTy)) {
00231       // If the element types match, VMCore can fold it.
00232       unsigned NumDstElt = DestVTy->getNumElements();
00233       unsigned NumSrcElt = CV->getNumOperands();
00234       if (NumDstElt == NumSrcElt)
00235         return 0;
00236       
00237       const Type *SrcEltTy = CV->getType()->getElementType();
00238       const Type *DstEltTy = DestVTy->getElementType();
00239       
00240       // Otherwise, we're changing the number of elements in a vector, which 
00241       // requires endianness information to do the right thing.  For example,
00242       //    bitcast (<2 x i64> <i64 0, i64 1> to <4 x i32>)
00243       // folds to (little endian):
00244       //    <4 x i32> <i32 0, i32 0, i32 1, i32 0>
00245       // and to (big endian):
00246       //    <4 x i32> <i32 0, i32 0, i32 0, i32 1>
00247       
00248       // First thing is first.  We only want to think about integer here, so if
00249       // we have something in FP form, recast it as integer.
00250       if (DstEltTy->isFloatingPoint()) {
00251         // Fold to an vector of integers with same size as our FP type.
00252         unsigned FPWidth = DstEltTy->getPrimitiveSizeInBits();
00253         const Type *DestIVTy = VectorType::get(
00254                                  IntegerType::get(Context, FPWidth), NumDstElt);
00255         // Recursively handle this integer conversion, if possible.
00256         C = FoldBitCast(C, DestIVTy, TD, Context);
00257         if (!C) return 0;
00258         
00259         // Finally, VMCore can handle this now that #elts line up.
00260         return ConstantExpr::getBitCast(C, DestTy);
00261       }
00262       
00263       // Okay, we know the destination is integer, if the input is FP, convert
00264       // it to integer first.
00265       if (SrcEltTy->isFloatingPoint()) {
00266         unsigned FPWidth = SrcEltTy->getPrimitiveSizeInBits();
00267         const Type *SrcIVTy = VectorType::get(
00268                                  IntegerType::get(Context, FPWidth), NumSrcElt);
00269         // Ask VMCore to do the conversion now that #elts line up.
00270         C = ConstantExpr::getBitCast(C, SrcIVTy);
00271         CV = dyn_cast<ConstantVector>(C);
00272         if (!CV) return 0;  // If VMCore wasn't able to fold it, bail out.
00273       }
00274       
00275       // Now we know that the input and output vectors are both integer vectors
00276       // of the same size, and that their #elements is not the same.  Do the
00277       // conversion here, which depends on whether the input or output has
00278       // more elements.
00279       bool isLittleEndian = TD.isLittleEndian();
00280       
00281       SmallVector<Constant*, 32> Result;
00282       if (NumDstElt < NumSrcElt) {
00283         // Handle: bitcast (<4 x i32> <i32 0, i32 1, i32 2, i32 3> to <2 x i64>)
00284         Constant *Zero = Constant::getNullValue(DstEltTy);
00285         unsigned Ratio = NumSrcElt/NumDstElt;
00286         unsigned SrcBitSize = SrcEltTy->getPrimitiveSizeInBits();
00287         unsigned SrcElt = 0;
00288         for (unsigned i = 0; i != NumDstElt; ++i) {
00289           // Build each element of the result.
00290           Constant *Elt = Zero;
00291           unsigned ShiftAmt = isLittleEndian ? 0 : SrcBitSize*(Ratio-1);
00292           for (unsigned j = 0; j != Ratio; ++j) {
00293             Constant *Src = dyn_cast<ConstantInt>(CV->getOperand(SrcElt++));
00294             if (!Src) return 0;  // Reject constantexpr elements.
00295             
00296             // Zero extend the element to the right size.
00297             Src = ConstantExpr::getZExt(Src, Elt->getType());
00298             
00299             // Shift it to the right place, depending on endianness.
00300             Src = ConstantExpr::getShl(Src, 
00301                              ConstantInt::get(Src->getType(), ShiftAmt));
00302             ShiftAmt += isLittleEndian ? SrcBitSize : -SrcBitSize;
00303             
00304             // Mix it in.
00305             Elt = ConstantExpr::getOr(Elt, Src);
00306           }
00307           Result.push_back(Elt);
00308         }
00309       } else {
00310         // Handle: bitcast (<2 x i64> <i64 0, i64 1> to <4 x i32>)
00311         unsigned Ratio = NumDstElt/NumSrcElt;
00312         unsigned DstBitSize = DstEltTy->getPrimitiveSizeInBits();
00313         
00314         // Loop over each source value, expanding into multiple results.
00315         for (unsigned i = 0; i != NumSrcElt; ++i) {
00316           Constant *Src = dyn_cast<ConstantInt>(CV->getOperand(i));
00317           if (!Src) return 0;  // Reject constantexpr elements.
00318 
00319           unsigned ShiftAmt = isLittleEndian ? 0 : DstBitSize*(Ratio-1);
00320           for (unsigned j = 0; j != Ratio; ++j) {
00321             // Shift the piece of the value into the right place, depending on
00322             // endianness.
00323             Constant *Elt = ConstantExpr::getLShr(Src, 
00324                             ConstantInt::get(Src->getType(), ShiftAmt));
00325             ShiftAmt += isLittleEndian ? DstBitSize : -DstBitSize;
00326 
00327             // Truncate and remember this piece.
00328             Result.push_back(ConstantExpr::getTrunc(Elt, DstEltTy));
00329           }
00330         }
00331       }
00332       
00333       return ConstantVector::get(Result.data(), Result.size());
00334     }
00335   }
00336   
00337   return 0;
00338 }
00339 
00340 
00341 //===----------------------------------------------------------------------===//
00342 // Constant Folding public APIs
00343 //===----------------------------------------------------------------------===//
00344 
00345 
00346 /// ConstantFoldInstruction - Attempt to constant fold the specified
00347 /// instruction.  If successful, the constant result is returned, if not, null
00348 /// is returned.  Note that this function can only fail when attempting to fold
00349 /// instructions like loads and stores, which have no constant expression form.
00350 ///
00351 Constant *llvm::ConstantFoldInstruction(Instruction *I, LLVMContext &Context,
00352                                         const TargetData *TD) {
00353   if (PHINode *PN = dyn_cast<PHINode>(I)) {
00354     if (PN->getNumIncomingValues() == 0)
00355       return UndefValue::get(PN->getType());
00356 
00357     Constant *Result = dyn_cast<Constant>(PN->getIncomingValue(0));
00358     if (Result == 0) return 0;
00359 
00360     // Handle PHI nodes specially here...
00361     for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i)
00362       if (PN->getIncomingValue(i) != Result && PN->getIncomingValue(i) != PN)
00363         return 0;   // Not all the same incoming constants...
00364 
00365     // If we reach here, all incoming values are the same constant.
00366     return Result;
00367   }
00368 
00369   // Scan the operand list, checking to see if they are all constants, if so,
00370   // hand off to ConstantFoldInstOperands.
00371   SmallVector<Constant*, 8> Ops;
00372   for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i)
00373     if (Constant *Op = dyn_cast<Constant>(*i))
00374       Ops.push_back(Op);
00375     else
00376       return 0;  // All operands not constant!
00377 
00378   if (const CmpInst *CI = dyn_cast<CmpInst>(I))
00379     return ConstantFoldCompareInstOperands(CI->getPredicate(),
00380                                            Ops.data(), Ops.size(), 
00381                                            Context, TD);
00382   else
00383     return ConstantFoldInstOperands(I->getOpcode(), I->getType(),
00384                                     Ops.data(), Ops.size(), Context, TD);
00385 }
00386 
00387 /// ConstantFoldConstantExpression - Attempt to fold the constant expression
00388 /// using the specified TargetData.  If successful, the constant result is
00389 /// result is returned, if not, null is returned.
00390 Constant *llvm::ConstantFoldConstantExpression(ConstantExpr *CE,
00391                                                LLVMContext &Context,
00392                                                const TargetData *TD) {
00393   SmallVector<Constant*, 8> Ops;
00394   for (User::op_iterator i = CE->op_begin(), e = CE->op_end(); i != e; ++i)
00395     Ops.push_back(cast<Constant>(*i));
00396 
00397   if (CE->isCompare())
00398     return ConstantFoldCompareInstOperands(CE->getPredicate(),
00399                                            Ops.data(), Ops.size(), 
00400                                            Context, TD);
00401   else 
00402     return ConstantFoldInstOperands(CE->getOpcode(), CE->getType(),
00403                                     Ops.data(), Ops.size(), Context, TD);
00404 }
00405 
00406 /// ConstantFoldInstOperands - Attempt to constant fold an instruction with the
00407 /// specified opcode and operands.  If successful, the constant result is
00408 /// returned, if not, null is returned.  Note that this function can fail when
00409 /// attempting to fold instructions like loads and stores, which have no
00410 /// constant expression form.
00411 ///
00412 Constant *llvm::ConstantFoldInstOperands(unsigned Opcode, const Type *DestTy, 
00413                                          Constant* const* Ops, unsigned NumOps,
00414                                          LLVMContext &Context,
00415                                          const TargetData *TD) {
00416   // Handle easy binops first.
00417   if (Instruction::isBinaryOp(Opcode)) {
00418     if (isa<ConstantExpr>(Ops[0]) || isa<ConstantExpr>(Ops[1]))
00419       if (Constant *C = SymbolicallyEvaluateBinop(Opcode, Ops[0], Ops[1], TD,
00420                                                   Context))
00421         return C;
00422     
00423     return ConstantExpr::get(Opcode, Ops[0], Ops[1]);
00424   }
00425   
00426   switch (Opcode) {
00427   default: return 0;
00428   case Instruction::Call:
00429     if (Function *F = dyn_cast<Function>(Ops[0]))
00430       if (canConstantFoldCallTo(F))
00431         return ConstantFoldCall(F, Ops+1, NumOps-1);
00432     return 0;
00433   case Instruction::ICmp:
00434   case Instruction::FCmp:
00435     llvm_unreachable("This function is invalid for compares: no predicate specified");
00436   case Instruction::PtrToInt:
00437     // If the input is a inttoptr, eliminate the pair.  This requires knowing
00438     // the width of a pointer, so it can't be done in ConstantExpr::getCast.
00439     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ops[0])) {
00440       if (TD && CE->getOpcode() == Instruction::IntToPtr) {
00441         Constant *Input = CE->getOperand(0);
00442         unsigned InWidth = Input->getType()->getScalarSizeInBits();
00443         if (TD->getPointerSizeInBits() < InWidth) {
00444           Constant *Mask = 
00445             ConstantInt::get(Context, APInt::getLowBitsSet(InWidth,
00446                                                   TD->getPointerSizeInBits()));
00447           Input = ConstantExpr::getAnd(Input, Mask);
00448         }
00449         // Do a zext or trunc to get to the dest size.
00450         return ConstantExpr::getIntegerCast(Input, DestTy, false);
00451       }
00452     }
00453     return ConstantExpr::getCast(Opcode, Ops[0], DestTy);
00454   case Instruction::IntToPtr:
00455     // If the input is a ptrtoint, turn the pair into a ptr to ptr bitcast if
00456     // the int size is >= the ptr size.  This requires knowing the width of a
00457     // pointer, so it can't be done in ConstantExpr::getCast.
00458     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ops[0])) {
00459       if (TD &&
00460           TD->getPointerSizeInBits() <=
00461           CE->getType()->getScalarSizeInBits()) {
00462         if (CE->getOpcode() == Instruction::PtrToInt) {
00463           Constant *Input = CE->getOperand(0);
00464           Constant *C = FoldBitCast(Input, DestTy, *TD, Context);
00465           return C ? C : ConstantExpr::getBitCast(Input, DestTy);
00466         }
00467         // If there's a constant offset added to the integer value before
00468         // it is casted back to a pointer, see if the expression can be
00469         // converted into a GEP.
00470         if (CE->getOpcode() == Instruction::Add)
00471           if (ConstantInt *L = dyn_cast<ConstantInt>(CE->getOperand(0)))
00472             if (ConstantExpr *R = dyn_cast<ConstantExpr>(CE->getOperand(1)))
00473               if (R->getOpcode() == Instruction::PtrToInt)
00474                 if (GlobalVariable *GV =
00475                       dyn_cast<GlobalVariable>(R->getOperand(0))) {
00476                   const PointerType *GVTy = cast<PointerType>(GV->getType());
00477                   if (const ArrayType *AT =
00478                         dyn_cast<ArrayType>(GVTy->getElementType())) {
00479                     const Type *ElTy = AT->getElementType();
00480                     uint64_t AllocSize = TD->getTypeAllocSize(ElTy);
00481                     APInt PSA(L->getValue().getBitWidth(), AllocSize);
00482                     if (ElTy == cast<PointerType>(DestTy)->getElementType() &&
00483                         L->getValue().urem(PSA) == 0) {
00484                       APInt ElemIdx = L->getValue().udiv(PSA);
00485                       if (ElemIdx.ult(APInt(ElemIdx.getBitWidth(),
00486                                             AT->getNumElements()))) {
00487                         Constant *Index[] = {
00488                           Constant::getNullValue(CE->getType()),
00489                           ConstantInt::get(Context, ElemIdx)
00490                         };
00491                         return
00492                         ConstantExpr::getGetElementPtr(GV, &Index[0], 2);
00493                       }
00494                     }
00495                   }
00496                 }
00497       }
00498     }
00499     return ConstantExpr::getCast(Opcode, Ops[0], DestTy);
00500   case Instruction::Trunc:
00501   case Instruction::ZExt:
00502   case Instruction::SExt:
00503   case Instruction::FPTrunc:
00504   case Instruction::FPExt:
00505   case Instruction::UIToFP:
00506   case Instruction::SIToFP:
00507   case Instruction::FPToUI:
00508   case Instruction::FPToSI:
00509       return ConstantExpr::getCast(Opcode, Ops[0], DestTy);
00510   case Instruction::BitCast:
00511     if (TD)
00512       if (Constant *C = FoldBitCast(Ops[0], DestTy, *TD, Context))
00513         return C;
00514     return ConstantExpr::getBitCast(Ops[0], DestTy);
00515   case Instruction::Select:
00516     return ConstantExpr::getSelect(Ops[0], Ops[1], Ops[2]);
00517   case Instruction::ExtractElement:
00518     return ConstantExpr::getExtractElement(Ops[0], Ops[1]);
00519   case Instruction::InsertElement:
00520     return ConstantExpr::getInsertElement(Ops[0], Ops[1], Ops[2]);
00521   case Instruction::ShuffleVector:
00522     return ConstantExpr::getShuffleVector(Ops[0], Ops[1], Ops[2]);
00523   case Instruction::GetElementPtr:
00524     if (Constant *C = SymbolicallyEvaluateGEP(Ops, NumOps, DestTy, Context, TD))
00525       return C;
00526     
00527     return ConstantExpr::getGetElementPtr(Ops[0], Ops+1, NumOps-1);
00528   }
00529 }
00530 
00531 /// ConstantFoldCompareInstOperands - Attempt to constant fold a compare
00532 /// instruction (icmp/fcmp) with the specified operands.  If it fails, it
00533 /// returns a constant expression of the specified operands.
00534 ///
00535 Constant *llvm::ConstantFoldCompareInstOperands(unsigned Predicate,
00536                                                 Constant*const * Ops, 
00537                                                 unsigned NumOps,
00538                                                 LLVMContext &Context,
00539                                                 const TargetData *TD) {
00540   // fold: icmp (inttoptr x), null         -> icmp x, 0
00541   // fold: icmp (ptrtoint x), 0            -> icmp x, null
00542   // fold: icmp (inttoptr x), (inttoptr y) -> icmp trunc/zext x, trunc/zext y
00543   // fold: icmp (ptrtoint x), (ptrtoint y) -> icmp x, y
00544   //
00545   // ConstantExpr::getCompare cannot do this, because it doesn't have TD
00546   // around to know if bit truncation is happening.
00547   if (ConstantExpr *CE0 = dyn_cast<ConstantExpr>(Ops[0])) {
00548     if (TD && Ops[1]->isNullValue()) {
00549       const Type *IntPtrTy = TD->getIntPtrType(Context);
00550       if (CE0->getOpcode() == Instruction::IntToPtr) {
00551         // Convert the integer value to the right size to ensure we get the
00552         // proper extension or truncation.
00553         Constant *C = ConstantExpr::getIntegerCast(CE0->getOperand(0),
00554                                                    IntPtrTy, false);
00555         Constant *NewOps[] = { C, Constant::getNullValue(C->getType()) };
00556         return ConstantFoldCompareInstOperands(Predicate, NewOps, 2,
00557                                                Context, TD);
00558       }
00559       
00560       // Only do this transformation if the int is intptrty in size, otherwise
00561       // there is a truncation or extension that we aren't modeling.
00562       if (CE0->getOpcode() == Instruction::PtrToInt && 
00563           CE0->getType() == IntPtrTy) {
00564         Constant *C = CE0->getOperand(0);
00565         Constant *NewOps[] = { C, Constant::getNullValue(C->getType()) };
00566         // FIXME!
00567         return ConstantFoldCompareInstOperands(Predicate, NewOps, 2,
00568                                                Context, TD);
00569       }
00570     }
00571     
00572     if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(Ops[1])) {
00573       if (TD && CE0->getOpcode() == CE1->getOpcode()) {
00574         const Type *IntPtrTy = TD->getIntPtrType(Context);
00575 
00576         if (CE0->getOpcode() == Instruction::IntToPtr) {
00577           // Convert the integer value to the right size to ensure we get the
00578           // proper extension or truncation.
00579           Constant *C0 = ConstantExpr::getIntegerCast(CE0->getOperand(0),
00580                                                       IntPtrTy, false);
00581           Constant *C1 = ConstantExpr::getIntegerCast(CE1->getOperand(0),
00582                                                       IntPtrTy, false);
00583           Constant *NewOps[] = { C0, C1 };
00584           return ConstantFoldCompareInstOperands(Predicate, NewOps, 2, 
00585                                                  Context, TD);
00586         }
00587 
00588         // Only do this transformation if the int is intptrty in size, otherwise
00589         // there is a truncation or extension that we aren't modeling.
00590         if ((CE0->getOpcode() == Instruction::PtrToInt &&
00591              CE0->getType() == IntPtrTy &&
00592              CE0->getOperand(0)->getType() == CE1->getOperand(0)->getType())) {
00593           Constant *NewOps[] = { 
00594             CE0->getOperand(0), CE1->getOperand(0) 
00595           };
00596           return ConstantFoldCompareInstOperands(Predicate, NewOps, 2, 
00597                                                  Context, TD);
00598         }
00599       }
00600     }
00601   }
00602   return ConstantExpr::getCompare(Predicate, Ops[0], Ops[1]);
00603 }
00604 
00605 
00606 /// ConstantFoldLoadThroughGEPConstantExpr - Given a constant and a
00607 /// getelementptr constantexpr, return the constant value being addressed by the
00608 /// constant expression, or null if something is funny and we can't decide.
00609 Constant *llvm::ConstantFoldLoadThroughGEPConstantExpr(Constant *C, 
00610                                                        ConstantExpr *CE,
00611                                                        LLVMContext &Context) {
00612   if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType()))
00613     return 0;  // Do not allow stepping over the value!
00614   
00615   // Loop over all of the operands, tracking down which value we are
00616   // addressing...
00617   gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
00618   for (++I; I != E; ++I)
00619     if (const StructType *STy = dyn_cast<StructType>(*I)) {
00620       ConstantInt *CU = cast<ConstantInt>(I.getOperand());
00621       assert(CU->getZExtValue() < STy->getNumElements() &&
00622              "Struct index out of range!");
00623       unsigned El = (unsigned)CU->getZExtValue();
00624       if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
00625         C = CS->getOperand(El);
00626       } else if (isa<ConstantAggregateZero>(C)) {
00627         C = Constant::getNullValue(STy->getElementType(El));
00628       } else if (isa<UndefValue>(C)) {
00629         C = UndefValue::get(STy->getElementType(El));
00630       } else {
00631         return 0;
00632       }
00633     } else if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) {
00634       if (const ArrayType *ATy = dyn_cast<ArrayType>(*I)) {
00635         if (CI->getZExtValue() >= ATy->getNumElements())
00636          return 0;
00637         if (ConstantArray *CA = dyn_cast<ConstantArray>(C))
00638           C = CA->getOperand(CI->getZExtValue());
00639         else if (isa<ConstantAggregateZero>(C))
00640           C = Constant::getNullValue(ATy->getElementType());
00641         else if (isa<UndefValue>(C))
00642           C = UndefValue::get(ATy->getElementType());
00643         else
00644           return 0;
00645       } else if (const VectorType *PTy = dyn_cast<VectorType>(*I)) {
00646         if (CI->getZExtValue() >= PTy->getNumElements())
00647           return 0;
00648         if (ConstantVector *CP = dyn_cast<ConstantVector>(C))
00649           C = CP->getOperand(CI->getZExtValue());
00650         else if (isa<ConstantAggregateZero>(C))
00651           C = Constant::getNullValue(PTy->getElementType());
00652         else if (isa<UndefValue>(C))
00653           C = UndefValue::get(PTy->getElementType());
00654         else
00655           return 0;
00656       } else {
00657         return 0;
00658       }
00659     } else {
00660       return 0;
00661     }
00662   return C;
00663 }
00664 
00665 
00666 //===----------------------------------------------------------------------===//
00667 //  Constant Folding for Calls
00668 //
00669 
00670 /// canConstantFoldCallTo - Return true if its even possible to fold a call to
00671 /// the specified function.
00672 bool
00673 llvm::canConstantFoldCallTo(const Function *F) {
00674   switch (F->getIntrinsicID()) {
00675   case Intrinsic::sqrt:
00676   case Intrinsic::powi:
00677   case Intrinsic::bswap:
00678   case Intrinsic::ctpop:
00679   case Intrinsic::ctlz:
00680   case Intrinsic::cttz:
00681     return true;
00682   default: break;
00683   }
00684 
00685   if (!F->hasName()) return false;
00686   StringRef Name = F->getName();
00687   
00688   // In these cases, the check of the length is required.  We don't want to
00689   // return true for a name like "cos\0blah" which strcmp would return equal to
00690   // "cos", but has length 8.
00691   switch (Name[0]) {
00692   default: return false;
00693   case 'a':
00694     return Name == "acos" || Name == "asin" || 
00695       Name == "atan" || Name == "atan2";
00696   case 'c':
00697     return Name == "cos" || Name == "ceil" || Name == "cosf" || Name == "cosh";
00698   case 'e':
00699     return Name == "exp";
00700   case 'f':
00701     return Name == "fabs" || Name == "fmod" || Name == "floor";
00702   case 'l':
00703     return Name == "log" || Name == "log10";
00704   case 'p':
00705     return Name == "pow";
00706   case 's':
00707     return Name == "sin" || Name == "sinh" || Name == "sqrt" ||
00708       Name == "sinf" || Name == "sqrtf";
00709   case 't':
00710     return Name == "tan" || Name == "tanh";
00711   }
00712 }
00713 
00714 static Constant *ConstantFoldFP(double (*NativeFP)(double), double V, 
00715                                 const Type *Ty, LLVMContext &Context) {
00716   errno = 0;
00717   V = NativeFP(V);
00718   if (errno != 0) {
00719     errno = 0;
00720     return 0;
00721   }
00722   
00723   if (Ty == Type::getFloatTy(Context))
00724     return ConstantFP::get(Context, APFloat((float)V));
00725   if (Ty == Type::getDoubleTy(Context))
00726     return ConstantFP::get(Context, APFloat(V));
00727   llvm_unreachable("Can only constant fold float/double");
00728   return 0; // dummy return to suppress warning
00729 }
00730 
00731 static Constant *ConstantFoldBinaryFP(double (*NativeFP)(double, double),
00732                                       double V, double W,
00733                                       const Type *Ty,
00734                                       LLVMContext &Context) {
00735   errno = 0;
00736   V = NativeFP(V, W);
00737   if (errno != 0) {
00738     errno = 0;
00739     return 0;
00740   }
00741   
00742   if (Ty == Type::getFloatTy(Context))
00743     return ConstantFP::get(Context, APFloat((float)V));
00744   if (Ty == Type::getDoubleTy(Context))
00745     return ConstantFP::get(Context, APFloat(V));
00746   llvm_unreachable("Can only constant fold float/double");
00747   return 0; // dummy return to suppress warning
00748 }
00749 
00750 /// ConstantFoldCall - Attempt to constant fold a call to the specified function
00751 /// with the specified arguments, returning null if unsuccessful.
00752 
00753 Constant *
00754 llvm::ConstantFoldCall(Function *F, 
00755                        Constant* const* Operands, unsigned NumOperands) {
00756   if (!F->hasName()) return 0;
00757   LLVMContext &Context = F->getContext();
00758   StringRef Name = F->getName();
00759   
00760   const Type *Ty = F->getReturnType();
00761   if (NumOperands == 1) {
00762     if (ConstantFP *Op = dyn_cast<ConstantFP>(Operands[0])) {
00763       if (Ty!=Type::getFloatTy(F->getContext()) &&
00764           Ty!=Type::getDoubleTy(Context))
00765         return 0;
00766       /// Currently APFloat versions of these functions do not exist, so we use
00767       /// the host native double versions.  Float versions are not called
00768       /// directly but for all these it is true (float)(f((double)arg)) ==
00769       /// f(arg).  Long double not supported yet.
00770       double V = Ty==Type::getFloatTy(F->getContext()) ?
00771                                      (double)Op->getValueAPF().convertToFloat():
00772                                      Op->getValueAPF().convertToDouble();
00773       switch (Name[0]) {
00774       case 'a':
00775         if (Name == "acos")
00776           return ConstantFoldFP(acos, V, Ty, Context);
00777         else if (Name == "asin")
00778           return ConstantFoldFP(asin, V, Ty, Context);
00779         else if (Name == "atan")
00780           return ConstantFoldFP(atan, V, Ty, Context);
00781         break;
00782       case 'c':
00783         if (Name == "ceil")
00784           return ConstantFoldFP(ceil, V, Ty, Context);
00785         else if (Name == "cos")
00786           return ConstantFoldFP(cos, V, Ty, Context);
00787         else if (Name == "cosh")
00788           return ConstantFoldFP(cosh, V, Ty, Context);
00789         else if (Name == "cosf")
00790           return ConstantFoldFP(cos, V, Ty, Context);
00791         break;
00792       case 'e':
00793         if (Name == "exp")
00794           return ConstantFoldFP(exp, V, Ty, Context);
00795         break;
00796       case 'f':
00797         if (Name == "fabs")
00798           return ConstantFoldFP(fabs, V, Ty, Context);
00799         else if (Name == "floor")
00800           return ConstantFoldFP(floor, V, Ty, Context);
00801         break;
00802       case 'l':
00803         if (Name == "log" && V > 0)
00804           return ConstantFoldFP(log, V, Ty, Context);
00805         else if (Name == "log10" && V > 0)
00806           return ConstantFoldFP(log10, V, Ty, Context);
00807         else if (Name == "llvm.sqrt.f32" ||
00808                  Name == "llvm.sqrt.f64") {
00809           if (V >= -0.0)
00810             return ConstantFoldFP(sqrt, V, Ty, Context);
00811           else // Undefined
00812             return Constant::getNullValue(Ty);
00813         }
00814         break;
00815       case 's':
00816         if (Name == "sin")
00817           return ConstantFoldFP(sin, V, Ty, Context);
00818         else if (Name == "sinh")
00819           return ConstantFoldFP(sinh, V, Ty, Context);
00820         else if (Name == "sqrt" && V >= 0)
00821           return ConstantFoldFP(sqrt, V, Ty, Context);
00822         else if (Name == "sqrtf" && V >= 0)
00823           return ConstantFoldFP(sqrt, V, Ty, Context);
00824         else if (Name == "sinf")
00825           return ConstantFoldFP(sin, V, Ty, Context);
00826         break;
00827       case 't':
00828         if (Name == "tan")
00829           return ConstantFoldFP(tan, V, Ty, Context);
00830         else if (Name == "tanh")
00831           return ConstantFoldFP(tanh, V, Ty, Context);
00832         break;
00833       default:
00834         break;
00835       }
00836     } else if (ConstantInt *Op = dyn_cast<ConstantInt>(Operands[0])) {
00837       if (Name.startswith("llvm.bswap"))
00838         return ConstantInt::get(Context, Op->getValue().byteSwap());
00839       else if (Name.startswith("llvm.ctpop"))
00840         return ConstantInt::get(Ty, Op->getValue().countPopulation());
00841       else if (Name.startswith("llvm.cttz"))
00842         return ConstantInt::get(Ty, Op->getValue().countTrailingZeros());
00843       else if (Name.startswith("llvm.ctlz"))
00844         return ConstantInt::get(Ty, Op->getValue().countLeadingZeros());
00845     }
00846   } else if (NumOperands == 2) {
00847     if (ConstantFP *Op1 = dyn_cast<ConstantFP>(Operands[0])) {
00848       if (Ty!=Type::getFloatTy(F->getContext()) && 
00849           Ty!=Type::getDoubleTy(Context))
00850         return 0;
00851       double Op1V = Ty==Type::getFloatTy(F->getContext()) ? 
00852                       (double)Op1->getValueAPF().convertToFloat():
00853                       Op1->getValueAPF().convertToDouble();
00854       if (ConstantFP *Op2 = dyn_cast<ConstantFP>(Operands[1])) {
00855         double Op2V = Ty==Type::getFloatTy(F->getContext()) ? 
00856                       (double)Op2->getValueAPF().convertToFloat():
00857                       Op2->getValueAPF().convertToDouble();
00858 
00859         if (Name == "pow") {
00860           return ConstantFoldBinaryFP(pow, Op1V, Op2V, Ty, Context);
00861         } else if (Name == "fmod") {
00862           return ConstantFoldBinaryFP(fmod, Op1V, Op2V, Ty, Context);
00863         } else if (Name == "atan2") {
00864           return ConstantFoldBinaryFP(atan2, Op1V, Op2V, Ty, Context);
00865         }
00866       } else if (ConstantInt *Op2C = dyn_cast<ConstantInt>(Operands[1])) {
00867         if (Name == "llvm.powi.f32") {
00868           return ConstantFP::get(Context, APFloat((float)std::pow((float)Op1V,
00869                                                  (int)Op2C->getZExtValue())));
00870         } else if (Name == "llvm.powi.f64") {
00871           return ConstantFP::get(Context, APFloat((double)std::pow((double)Op1V,
00872                                                  (int)Op2C->getZExtValue())));
00873         }
00874       }
00875     }
00876   }
00877   return 0;
00878 }
00879