LLVM API Documentation
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