ConstantFolding.cpp revision 62d327e241f59735eed836e98c8f11ffaa6cf6f8
1//===-- ConstantFolding.cpp - Fold instructions into constants ------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines routines for folding instructions into constants. 11// 12// Also, to supplement the basic VMCore ConstantExpr simplifications, 13// this file defines some additional folding routines that can make use of 14// TargetData information. These functions cannot go in VMCore due to library 15// dependency issues. 16// 17//===----------------------------------------------------------------------===// 18 19#include "llvm/Analysis/ConstantFolding.h" 20#include "llvm/Constants.h" 21#include "llvm/DerivedTypes.h" 22#include "llvm/Function.h" 23#include "llvm/GlobalVariable.h" 24#include "llvm/Instructions.h" 25#include "llvm/Intrinsics.h" 26#include "llvm/LLVMContext.h" 27#include "llvm/Analysis/ValueTracking.h" 28#include "llvm/Target/TargetData.h" 29#include "llvm/ADT/SmallVector.h" 30#include "llvm/ADT/StringMap.h" 31#include "llvm/Support/ErrorHandling.h" 32#include "llvm/Support/GetElementPtrTypeIterator.h" 33#include "llvm/Support/MathExtras.h" 34#include <cerrno> 35#include <cmath> 36using namespace llvm; 37 38//===----------------------------------------------------------------------===// 39// Constant Folding internal helper functions 40//===----------------------------------------------------------------------===// 41 42/// IsConstantOffsetFromGlobal - If this constant is actually a constant offset 43/// from a global, return the global and the constant. Because of 44/// constantexprs, this function is recursive. 45static bool IsConstantOffsetFromGlobal(Constant *C, GlobalValue *&GV, 46 int64_t &Offset, const TargetData &TD) { 47 // Trivial case, constant is the global. 48 if ((GV = dyn_cast<GlobalValue>(C))) { 49 Offset = 0; 50 return true; 51 } 52 53 // Otherwise, if this isn't a constant expr, bail out. 54 ConstantExpr *CE = dyn_cast<ConstantExpr>(C); 55 if (!CE) return false; 56 57 // Look through ptr->int and ptr->ptr casts. 58 if (CE->getOpcode() == Instruction::PtrToInt || 59 CE->getOpcode() == Instruction::BitCast) 60 return IsConstantOffsetFromGlobal(CE->getOperand(0), GV, Offset, TD); 61 62 // i32* getelementptr ([5 x i32]* @a, i32 0, i32 5) 63 if (CE->getOpcode() == Instruction::GetElementPtr) { 64 // Cannot compute this if the element type of the pointer is missing size 65 // info. 66 if (!cast<PointerType>(CE->getOperand(0)->getType()) 67 ->getElementType()->isSized()) 68 return false; 69 70 // If the base isn't a global+constant, we aren't either. 71 if (!IsConstantOffsetFromGlobal(CE->getOperand(0), GV, Offset, TD)) 72 return false; 73 74 // Otherwise, add any offset that our operands provide. 75 gep_type_iterator GTI = gep_type_begin(CE); 76 for (User::const_op_iterator i = CE->op_begin() + 1, e = CE->op_end(); 77 i != e; ++i, ++GTI) { 78 ConstantInt *CI = dyn_cast<ConstantInt>(*i); 79 if (!CI) return false; // Index isn't a simple constant? 80 if (CI->getZExtValue() == 0) continue; // Not adding anything. 81 82 if (const StructType *ST = dyn_cast<StructType>(*GTI)) { 83 // N = N + Offset 84 Offset += TD.getStructLayout(ST)->getElementOffset(CI->getZExtValue()); 85 } else { 86 const SequentialType *SQT = cast<SequentialType>(*GTI); 87 Offset += TD.getTypeAllocSize(SQT->getElementType())*CI->getSExtValue(); 88 } 89 } 90 return true; 91 } 92 93 return false; 94} 95 96/// ConstantFoldLoadFromConstPtr - Return the value that a load from C would 97/// produce if it is constant and determinable. If this is not determinable, 98/// return null. 99Constant *llvm::ConstantFoldLoadFromConstPtr(Constant *C, 100 const TargetData *TD) { 101 // First, try the easy cases: 102 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C)) 103 if (GV->isConstant() && GV->hasDefinitiveInitializer()) 104 return GV->getInitializer(); 105 106 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { 107 if (CE->getOpcode() == Instruction::GetElementPtr) { 108 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0))) 109 if (GV->isConstant() && GV->hasDefinitiveInitializer()) 110 if (Constant *V = 111 ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE)) 112 return V; 113 } 114 115 // Instead of loading constant c string, use corresponding integer value 116 // directly if string length is small enough. 117 std::string Str; 118 if (TD && GetConstantStringInfo(CE->getOperand(0), Str) && !Str.empty()) { 119 unsigned len = Str.length(); 120 const Type *Ty = cast<PointerType>(CE->getType())->getElementType(); 121 unsigned numBits = Ty->getPrimitiveSizeInBits(); 122 // Replace LI with immediate integer store. 123 if ((numBits >> 3) == len + 1) { 124 APInt StrVal(numBits, 0); 125 APInt SingleChar(numBits, 0); 126 if (TD->isLittleEndian()) { 127 for (signed i = len-1; i >= 0; i--) { 128 SingleChar = (uint64_t) Str[i] & UCHAR_MAX; 129 StrVal = (StrVal << 8) | SingleChar; 130 } 131 } else { 132 for (unsigned i = 0; i < len; i++) { 133 SingleChar = (uint64_t) Str[i] & UCHAR_MAX; 134 StrVal = (StrVal << 8) | SingleChar; 135 } 136 // Append NULL at the end. 137 SingleChar = 0; 138 StrVal = (StrVal << 8) | SingleChar; 139 } 140 return ConstantInt::get(CE->getContext(), StrVal); 141 } 142 } 143 } 144 145 return 0; 146} 147 148static Constant *ConstantFoldLoadInst(const LoadInst *LI, const TargetData *TD){ 149 if (LI->isVolatile()) return 0; 150 151 if (Constant *C = dyn_cast<Constant>(LI->getOperand(0))) 152 return ConstantFoldLoadFromConstPtr(C, TD); 153 154 return 0; 155} 156 157/// SymbolicallyEvaluateBinop - One of Op0/Op1 is a constant expression. 158/// Attempt to symbolically evaluate the result of a binary operator merging 159/// these together. If target data info is available, it is provided as TD, 160/// otherwise TD is null. 161static Constant *SymbolicallyEvaluateBinop(unsigned Opc, Constant *Op0, 162 Constant *Op1, const TargetData *TD, 163 LLVMContext &Context){ 164 // SROA 165 166 // Fold (and 0xffffffff00000000, (shl x, 32)) -> shl. 167 // Fold (lshr (or X, Y), 32) -> (lshr [X/Y], 32) if one doesn't contribute 168 // bits. 169 170 171 // If the constant expr is something like &A[123] - &A[4].f, fold this into a 172 // constant. This happens frequently when iterating over a global array. 173 if (Opc == Instruction::Sub && TD) { 174 GlobalValue *GV1, *GV2; 175 int64_t Offs1, Offs2; 176 177 if (IsConstantOffsetFromGlobal(Op0, GV1, Offs1, *TD)) 178 if (IsConstantOffsetFromGlobal(Op1, GV2, Offs2, *TD) && 179 GV1 == GV2) { 180 // (&GV+C1) - (&GV+C2) -> C1-C2, pointer arithmetic cannot overflow. 181 return ConstantInt::get(Op0->getType(), Offs1-Offs2); 182 } 183 } 184 185 return 0; 186} 187 188/// SymbolicallyEvaluateGEP - If we can symbolically evaluate the specified GEP 189/// constant expression, do so. 190static Constant *SymbolicallyEvaluateGEP(Constant* const* Ops, unsigned NumOps, 191 const Type *ResultTy, 192 LLVMContext &Context, 193 const TargetData *TD) { 194 Constant *Ptr = Ops[0]; 195 if (!TD || !cast<PointerType>(Ptr->getType())->getElementType()->isSized()) 196 return 0; 197 198 unsigned BitWidth = TD->getTypeSizeInBits(TD->getIntPtrType(Context)); 199 APInt BasePtr(BitWidth, 0); 200 bool BaseIsInt = true; 201 if (!Ptr->isNullValue()) { 202 // If this is a inttoptr from a constant int, we can fold this as the base, 203 // otherwise we can't. 204 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) 205 if (CE->getOpcode() == Instruction::IntToPtr) 206 if (ConstantInt *Base = dyn_cast<ConstantInt>(CE->getOperand(0))) { 207 BasePtr = Base->getValue(); 208 BasePtr.zextOrTrunc(BitWidth); 209 } 210 211 if (BasePtr == 0) 212 BaseIsInt = false; 213 } 214 215 // If this is a constant expr gep that is effectively computing an 216 // "offsetof", fold it into 'cast int Size to T*' instead of 'gep 0, 0, 12' 217 for (unsigned i = 1; i != NumOps; ++i) 218 if (!isa<ConstantInt>(Ops[i])) 219 return 0; 220 221 APInt Offset = APInt(BitWidth, 222 TD->getIndexedOffset(Ptr->getType(), 223 (Value**)Ops+1, NumOps-1)); 224 // If the base value for this address is a literal integer value, fold the 225 // getelementptr to the resulting integer value casted to the pointer type. 226 if (BaseIsInt) { 227 Constant *C = ConstantInt::get(Context, Offset+BasePtr); 228 return ConstantExpr::getIntToPtr(C, ResultTy); 229 } 230 231 // Otherwise form a regular getelementptr. Recompute the indices so that 232 // we eliminate over-indexing of the notional static type array bounds. 233 // This makes it easy to determine if the getelementptr is "inbounds". 234 // Also, this helps GlobalOpt do SROA on GlobalVariables. 235 const Type *Ty = Ptr->getType(); 236 SmallVector<Constant*, 32> NewIdxs; 237 do { 238 if (const SequentialType *ATy = dyn_cast<SequentialType>(Ty)) { 239 // The only pointer indexing we'll do is on the first index of the GEP. 240 if (isa<PointerType>(ATy) && !NewIdxs.empty()) 241 break; 242 // Determine which element of the array the offset points into. 243 APInt ElemSize(BitWidth, TD->getTypeAllocSize(ATy->getElementType())); 244 if (ElemSize == 0) 245 return 0; 246 APInt NewIdx = Offset.udiv(ElemSize); 247 Offset -= NewIdx * ElemSize; 248 NewIdxs.push_back(ConstantInt::get(TD->getIntPtrType(Context), NewIdx)); 249 Ty = ATy->getElementType(); 250 } else if (const StructType *STy = dyn_cast<StructType>(Ty)) { 251 // Determine which field of the struct the offset points into. The 252 // getZExtValue is at least as safe as the StructLayout API because we 253 // know the offset is within the struct at this point. 254 const StructLayout &SL = *TD->getStructLayout(STy); 255 unsigned ElIdx = SL.getElementContainingOffset(Offset.getZExtValue()); 256 NewIdxs.push_back(ConstantInt::get(Type::getInt32Ty(Context), ElIdx)); 257 Offset -= APInt(BitWidth, SL.getElementOffset(ElIdx)); 258 Ty = STy->getTypeAtIndex(ElIdx); 259 } else { 260 // We've reached some non-indexable type. 261 break; 262 } 263 } while (Ty != cast<PointerType>(ResultTy)->getElementType()); 264 265 // If we haven't used up the entire offset by descending the static 266 // type, then the offset is pointing into the middle of an indivisible 267 // member, so we can't simplify it. 268 if (Offset != 0) 269 return 0; 270 271 // Create a GEP. 272 Constant *C = 273 ConstantExpr::getGetElementPtr(Ptr, &NewIdxs[0], NewIdxs.size()); 274 assert(cast<PointerType>(C->getType())->getElementType() == Ty && 275 "Computed GetElementPtr has unexpected type!"); 276 277 // If we ended up indexing a member with a type that doesn't match 278 // the type of what the original indices indexed, add a cast. 279 if (Ty != cast<PointerType>(ResultTy)->getElementType()) 280 C = ConstantExpr::getBitCast(C, ResultTy); 281 282 return C; 283} 284 285/// FoldBitCast - Constant fold bitcast, symbolically evaluating it with 286/// targetdata. Return 0 if unfoldable. 287static Constant *FoldBitCast(Constant *C, const Type *DestTy, 288 const TargetData &TD, LLVMContext &Context) { 289 // If this is a bitcast from constant vector -> vector, fold it. 290 if (ConstantVector *CV = dyn_cast<ConstantVector>(C)) { 291 if (const VectorType *DestVTy = dyn_cast<VectorType>(DestTy)) { 292 // If the element types match, VMCore can fold it. 293 unsigned NumDstElt = DestVTy->getNumElements(); 294 unsigned NumSrcElt = CV->getNumOperands(); 295 if (NumDstElt == NumSrcElt) 296 return 0; 297 298 const Type *SrcEltTy = CV->getType()->getElementType(); 299 const Type *DstEltTy = DestVTy->getElementType(); 300 301 // Otherwise, we're changing the number of elements in a vector, which 302 // requires endianness information to do the right thing. For example, 303 // bitcast (<2 x i64> <i64 0, i64 1> to <4 x i32>) 304 // folds to (little endian): 305 // <4 x i32> <i32 0, i32 0, i32 1, i32 0> 306 // and to (big endian): 307 // <4 x i32> <i32 0, i32 0, i32 0, i32 1> 308 309 // First thing is first. We only want to think about integer here, so if 310 // we have something in FP form, recast it as integer. 311 if (DstEltTy->isFloatingPoint()) { 312 // Fold to an vector of integers with same size as our FP type. 313 unsigned FPWidth = DstEltTy->getPrimitiveSizeInBits(); 314 const Type *DestIVTy = VectorType::get( 315 IntegerType::get(Context, FPWidth), NumDstElt); 316 // Recursively handle this integer conversion, if possible. 317 C = FoldBitCast(C, DestIVTy, TD, Context); 318 if (!C) return 0; 319 320 // Finally, VMCore can handle this now that #elts line up. 321 return ConstantExpr::getBitCast(C, DestTy); 322 } 323 324 // Okay, we know the destination is integer, if the input is FP, convert 325 // it to integer first. 326 if (SrcEltTy->isFloatingPoint()) { 327 unsigned FPWidth = SrcEltTy->getPrimitiveSizeInBits(); 328 const Type *SrcIVTy = VectorType::get( 329 IntegerType::get(Context, FPWidth), NumSrcElt); 330 // Ask VMCore to do the conversion now that #elts line up. 331 C = ConstantExpr::getBitCast(C, SrcIVTy); 332 CV = dyn_cast<ConstantVector>(C); 333 if (!CV) return 0; // If VMCore wasn't able to fold it, bail out. 334 } 335 336 // Now we know that the input and output vectors are both integer vectors 337 // of the same size, and that their #elements is not the same. Do the 338 // conversion here, which depends on whether the input or output has 339 // more elements. 340 bool isLittleEndian = TD.isLittleEndian(); 341 342 SmallVector<Constant*, 32> Result; 343 if (NumDstElt < NumSrcElt) { 344 // Handle: bitcast (<4 x i32> <i32 0, i32 1, i32 2, i32 3> to <2 x i64>) 345 Constant *Zero = Constant::getNullValue(DstEltTy); 346 unsigned Ratio = NumSrcElt/NumDstElt; 347 unsigned SrcBitSize = SrcEltTy->getPrimitiveSizeInBits(); 348 unsigned SrcElt = 0; 349 for (unsigned i = 0; i != NumDstElt; ++i) { 350 // Build each element of the result. 351 Constant *Elt = Zero; 352 unsigned ShiftAmt = isLittleEndian ? 0 : SrcBitSize*(Ratio-1); 353 for (unsigned j = 0; j != Ratio; ++j) { 354 Constant *Src = dyn_cast<ConstantInt>(CV->getOperand(SrcElt++)); 355 if (!Src) return 0; // Reject constantexpr elements. 356 357 // Zero extend the element to the right size. 358 Src = ConstantExpr::getZExt(Src, Elt->getType()); 359 360 // Shift it to the right place, depending on endianness. 361 Src = ConstantExpr::getShl(Src, 362 ConstantInt::get(Src->getType(), ShiftAmt)); 363 ShiftAmt += isLittleEndian ? SrcBitSize : -SrcBitSize; 364 365 // Mix it in. 366 Elt = ConstantExpr::getOr(Elt, Src); 367 } 368 Result.push_back(Elt); 369 } 370 } else { 371 // Handle: bitcast (<2 x i64> <i64 0, i64 1> to <4 x i32>) 372 unsigned Ratio = NumDstElt/NumSrcElt; 373 unsigned DstBitSize = DstEltTy->getPrimitiveSizeInBits(); 374 375 // Loop over each source value, expanding into multiple results. 376 for (unsigned i = 0; i != NumSrcElt; ++i) { 377 Constant *Src = dyn_cast<ConstantInt>(CV->getOperand(i)); 378 if (!Src) return 0; // Reject constantexpr elements. 379 380 unsigned ShiftAmt = isLittleEndian ? 0 : DstBitSize*(Ratio-1); 381 for (unsigned j = 0; j != Ratio; ++j) { 382 // Shift the piece of the value into the right place, depending on 383 // endianness. 384 Constant *Elt = ConstantExpr::getLShr(Src, 385 ConstantInt::get(Src->getType(), ShiftAmt)); 386 ShiftAmt += isLittleEndian ? DstBitSize : -DstBitSize; 387 388 // Truncate and remember this piece. 389 Result.push_back(ConstantExpr::getTrunc(Elt, DstEltTy)); 390 } 391 } 392 } 393 394 return ConstantVector::get(Result.data(), Result.size()); 395 } 396 } 397 398 return 0; 399} 400 401 402//===----------------------------------------------------------------------===// 403// Constant Folding public APIs 404//===----------------------------------------------------------------------===// 405 406 407/// ConstantFoldInstruction - Attempt to constant fold the specified 408/// instruction. If successful, the constant result is returned, if not, null 409/// is returned. Note that this function can only fail when attempting to fold 410/// instructions like loads and stores, which have no constant expression form. 411/// 412Constant *llvm::ConstantFoldInstruction(Instruction *I, LLVMContext &Context, 413 const TargetData *TD) { 414 if (PHINode *PN = dyn_cast<PHINode>(I)) { 415 if (PN->getNumIncomingValues() == 0) 416 return UndefValue::get(PN->getType()); 417 418 Constant *Result = dyn_cast<Constant>(PN->getIncomingValue(0)); 419 if (Result == 0) return 0; 420 421 // Handle PHI nodes specially here... 422 for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) 423 if (PN->getIncomingValue(i) != Result && PN->getIncomingValue(i) != PN) 424 return 0; // Not all the same incoming constants... 425 426 // If we reach here, all incoming values are the same constant. 427 return Result; 428 } 429 430 // Scan the operand list, checking to see if they are all constants, if so, 431 // hand off to ConstantFoldInstOperands. 432 SmallVector<Constant*, 8> Ops; 433 for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) 434 if (Constant *Op = dyn_cast<Constant>(*i)) 435 Ops.push_back(Op); 436 else 437 return 0; // All operands not constant! 438 439 if (const CmpInst *CI = dyn_cast<CmpInst>(I)) 440 return ConstantFoldCompareInstOperands(CI->getPredicate(), 441 Ops.data(), Ops.size(), 442 Context, TD); 443 444 if (const LoadInst *LI = dyn_cast<LoadInst>(I)) 445 return ConstantFoldLoadInst(LI, TD); 446 447 return ConstantFoldInstOperands(I->getOpcode(), I->getType(), 448 Ops.data(), Ops.size(), Context, TD); 449} 450 451/// ConstantFoldConstantExpression - Attempt to fold the constant expression 452/// using the specified TargetData. If successful, the constant result is 453/// result is returned, if not, null is returned. 454Constant *llvm::ConstantFoldConstantExpression(ConstantExpr *CE, 455 LLVMContext &Context, 456 const TargetData *TD) { 457 SmallVector<Constant*, 8> Ops; 458 for (User::op_iterator i = CE->op_begin(), e = CE->op_end(); i != e; ++i) 459 Ops.push_back(cast<Constant>(*i)); 460 461 if (CE->isCompare()) 462 return ConstantFoldCompareInstOperands(CE->getPredicate(), 463 Ops.data(), Ops.size(), 464 Context, TD); 465 return ConstantFoldInstOperands(CE->getOpcode(), CE->getType(), 466 Ops.data(), Ops.size(), Context, TD); 467} 468 469/// ConstantFoldInstOperands - Attempt to constant fold an instruction with the 470/// specified opcode and operands. If successful, the constant result is 471/// returned, if not, null is returned. Note that this function can fail when 472/// attempting to fold instructions like loads and stores, which have no 473/// constant expression form. 474/// 475Constant *llvm::ConstantFoldInstOperands(unsigned Opcode, const Type *DestTy, 476 Constant* const* Ops, unsigned NumOps, 477 LLVMContext &Context, 478 const TargetData *TD) { 479 // Handle easy binops first. 480 if (Instruction::isBinaryOp(Opcode)) { 481 if (isa<ConstantExpr>(Ops[0]) || isa<ConstantExpr>(Ops[1])) 482 if (Constant *C = SymbolicallyEvaluateBinop(Opcode, Ops[0], Ops[1], TD, 483 Context)) 484 return C; 485 486 return ConstantExpr::get(Opcode, Ops[0], Ops[1]); 487 } 488 489 switch (Opcode) { 490 default: return 0; 491 case Instruction::Call: 492 if (Function *F = dyn_cast<Function>(Ops[0])) 493 if (canConstantFoldCallTo(F)) 494 return ConstantFoldCall(F, Ops+1, NumOps-1); 495 return 0; 496 case Instruction::ICmp: 497 case Instruction::FCmp: 498 llvm_unreachable("This function is invalid for compares: no predicate specified"); 499 case Instruction::PtrToInt: 500 // If the input is a inttoptr, eliminate the pair. This requires knowing 501 // the width of a pointer, so it can't be done in ConstantExpr::getCast. 502 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ops[0])) { 503 if (TD && CE->getOpcode() == Instruction::IntToPtr) { 504 Constant *Input = CE->getOperand(0); 505 unsigned InWidth = Input->getType()->getScalarSizeInBits(); 506 if (TD->getPointerSizeInBits() < InWidth) { 507 Constant *Mask = 508 ConstantInt::get(Context, APInt::getLowBitsSet(InWidth, 509 TD->getPointerSizeInBits())); 510 Input = ConstantExpr::getAnd(Input, Mask); 511 } 512 // Do a zext or trunc to get to the dest size. 513 return ConstantExpr::getIntegerCast(Input, DestTy, false); 514 } 515 } 516 return ConstantExpr::getCast(Opcode, Ops[0], DestTy); 517 case Instruction::IntToPtr: 518 // If the input is a ptrtoint, turn the pair into a ptr to ptr bitcast if 519 // the int size is >= the ptr size. This requires knowing the width of a 520 // pointer, so it can't be done in ConstantExpr::getCast. 521 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ops[0])) { 522 if (TD && 523 TD->getPointerSizeInBits() <= 524 CE->getType()->getScalarSizeInBits()) { 525 if (CE->getOpcode() == Instruction::PtrToInt) { 526 Constant *Input = CE->getOperand(0); 527 Constant *C = FoldBitCast(Input, DestTy, *TD, Context); 528 return C ? C : ConstantExpr::getBitCast(Input, DestTy); 529 } 530 // If there's a constant offset added to the integer value before 531 // it is casted back to a pointer, see if the expression can be 532 // converted into a GEP. 533 if (CE->getOpcode() == Instruction::Add) 534 if (ConstantInt *L = dyn_cast<ConstantInt>(CE->getOperand(0))) 535 if (ConstantExpr *R = dyn_cast<ConstantExpr>(CE->getOperand(1))) 536 if (R->getOpcode() == Instruction::PtrToInt) 537 if (GlobalVariable *GV = 538 dyn_cast<GlobalVariable>(R->getOperand(0))) { 539 const PointerType *GVTy = cast<PointerType>(GV->getType()); 540 if (const ArrayType *AT = 541 dyn_cast<ArrayType>(GVTy->getElementType())) { 542 const Type *ElTy = AT->getElementType(); 543 uint64_t AllocSize = TD->getTypeAllocSize(ElTy); 544 APInt PSA(L->getValue().getBitWidth(), AllocSize); 545 if (ElTy == cast<PointerType>(DestTy)->getElementType() && 546 L->getValue().urem(PSA) == 0) { 547 APInt ElemIdx = L->getValue().udiv(PSA); 548 if (ElemIdx.ult(APInt(ElemIdx.getBitWidth(), 549 AT->getNumElements()))) { 550 Constant *Index[] = { 551 Constant::getNullValue(CE->getType()), 552 ConstantInt::get(Context, ElemIdx) 553 }; 554 return 555 ConstantExpr::getGetElementPtr(GV, &Index[0], 2); 556 } 557 } 558 } 559 } 560 } 561 } 562 return ConstantExpr::getCast(Opcode, Ops[0], DestTy); 563 case Instruction::Trunc: 564 case Instruction::ZExt: 565 case Instruction::SExt: 566 case Instruction::FPTrunc: 567 case Instruction::FPExt: 568 case Instruction::UIToFP: 569 case Instruction::SIToFP: 570 case Instruction::FPToUI: 571 case Instruction::FPToSI: 572 return ConstantExpr::getCast(Opcode, Ops[0], DestTy); 573 case Instruction::BitCast: 574 if (TD) 575 if (Constant *C = FoldBitCast(Ops[0], DestTy, *TD, Context)) 576 return C; 577 return ConstantExpr::getBitCast(Ops[0], DestTy); 578 case Instruction::Select: 579 return ConstantExpr::getSelect(Ops[0], Ops[1], Ops[2]); 580 case Instruction::ExtractElement: 581 return ConstantExpr::getExtractElement(Ops[0], Ops[1]); 582 case Instruction::InsertElement: 583 return ConstantExpr::getInsertElement(Ops[0], Ops[1], Ops[2]); 584 case Instruction::ShuffleVector: 585 return ConstantExpr::getShuffleVector(Ops[0], Ops[1], Ops[2]); 586 case Instruction::GetElementPtr: 587 if (Constant *C = SymbolicallyEvaluateGEP(Ops, NumOps, DestTy, Context, TD)) 588 return C; 589 590 return ConstantExpr::getGetElementPtr(Ops[0], Ops+1, NumOps-1); 591 } 592} 593 594/// ConstantFoldCompareInstOperands - Attempt to constant fold a compare 595/// instruction (icmp/fcmp) with the specified operands. If it fails, it 596/// returns a constant expression of the specified operands. 597/// 598Constant *llvm::ConstantFoldCompareInstOperands(unsigned Predicate, 599 Constant*const * Ops, 600 unsigned NumOps, 601 LLVMContext &Context, 602 const TargetData *TD) { 603 // fold: icmp (inttoptr x), null -> icmp x, 0 604 // fold: icmp (ptrtoint x), 0 -> icmp x, null 605 // fold: icmp (inttoptr x), (inttoptr y) -> icmp trunc/zext x, trunc/zext y 606 // fold: icmp (ptrtoint x), (ptrtoint y) -> icmp x, y 607 // 608 // ConstantExpr::getCompare cannot do this, because it doesn't have TD 609 // around to know if bit truncation is happening. 610 if (ConstantExpr *CE0 = dyn_cast<ConstantExpr>(Ops[0])) { 611 if (TD && Ops[1]->isNullValue()) { 612 const Type *IntPtrTy = TD->getIntPtrType(Context); 613 if (CE0->getOpcode() == Instruction::IntToPtr) { 614 // Convert the integer value to the right size to ensure we get the 615 // proper extension or truncation. 616 Constant *C = ConstantExpr::getIntegerCast(CE0->getOperand(0), 617 IntPtrTy, false); 618 Constant *NewOps[] = { C, Constant::getNullValue(C->getType()) }; 619 return ConstantFoldCompareInstOperands(Predicate, NewOps, 2, 620 Context, TD); 621 } 622 623 // Only do this transformation if the int is intptrty in size, otherwise 624 // there is a truncation or extension that we aren't modeling. 625 if (CE0->getOpcode() == Instruction::PtrToInt && 626 CE0->getType() == IntPtrTy) { 627 Constant *C = CE0->getOperand(0); 628 Constant *NewOps[] = { C, Constant::getNullValue(C->getType()) }; 629 // FIXME! 630 return ConstantFoldCompareInstOperands(Predicate, NewOps, 2, 631 Context, TD); 632 } 633 } 634 635 if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(Ops[1])) { 636 if (TD && CE0->getOpcode() == CE1->getOpcode()) { 637 const Type *IntPtrTy = TD->getIntPtrType(Context); 638 639 if (CE0->getOpcode() == Instruction::IntToPtr) { 640 // Convert the integer value to the right size to ensure we get the 641 // proper extension or truncation. 642 Constant *C0 = ConstantExpr::getIntegerCast(CE0->getOperand(0), 643 IntPtrTy, false); 644 Constant *C1 = ConstantExpr::getIntegerCast(CE1->getOperand(0), 645 IntPtrTy, false); 646 Constant *NewOps[] = { C0, C1 }; 647 return ConstantFoldCompareInstOperands(Predicate, NewOps, 2, 648 Context, TD); 649 } 650 651 // Only do this transformation if the int is intptrty in size, otherwise 652 // there is a truncation or extension that we aren't modeling. 653 if ((CE0->getOpcode() == Instruction::PtrToInt && 654 CE0->getType() == IntPtrTy && 655 CE0->getOperand(0)->getType() == CE1->getOperand(0)->getType())) { 656 Constant *NewOps[] = { 657 CE0->getOperand(0), CE1->getOperand(0) 658 }; 659 return ConstantFoldCompareInstOperands(Predicate, NewOps, 2, 660 Context, TD); 661 } 662 } 663 } 664 } 665 return ConstantExpr::getCompare(Predicate, Ops[0], Ops[1]); 666} 667 668 669/// ConstantFoldLoadThroughGEPConstantExpr - Given a constant and a 670/// getelementptr constantexpr, return the constant value being addressed by the 671/// constant expression, or null if something is funny and we can't decide. 672Constant *llvm::ConstantFoldLoadThroughGEPConstantExpr(Constant *C, 673 ConstantExpr *CE) { 674 if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType())) 675 return 0; // Do not allow stepping over the value! 676 677 // Loop over all of the operands, tracking down which value we are 678 // addressing... 679 gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE); 680 for (++I; I != E; ++I) 681 if (const StructType *STy = dyn_cast<StructType>(*I)) { 682 ConstantInt *CU = cast<ConstantInt>(I.getOperand()); 683 assert(CU->getZExtValue() < STy->getNumElements() && 684 "Struct index out of range!"); 685 unsigned El = (unsigned)CU->getZExtValue(); 686 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) { 687 C = CS->getOperand(El); 688 } else if (isa<ConstantAggregateZero>(C)) { 689 C = Constant::getNullValue(STy->getElementType(El)); 690 } else if (isa<UndefValue>(C)) { 691 C = UndefValue::get(STy->getElementType(El)); 692 } else { 693 return 0; 694 } 695 } else if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) { 696 if (const ArrayType *ATy = dyn_cast<ArrayType>(*I)) { 697 if (CI->getZExtValue() >= ATy->getNumElements()) 698 return 0; 699 if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) 700 C = CA->getOperand(CI->getZExtValue()); 701 else if (isa<ConstantAggregateZero>(C)) 702 C = Constant::getNullValue(ATy->getElementType()); 703 else if (isa<UndefValue>(C)) 704 C = UndefValue::get(ATy->getElementType()); 705 else 706 return 0; 707 } else if (const VectorType *VTy = dyn_cast<VectorType>(*I)) { 708 if (CI->getZExtValue() >= VTy->getNumElements()) 709 return 0; 710 if (ConstantVector *CP = dyn_cast<ConstantVector>(C)) 711 C = CP->getOperand(CI->getZExtValue()); 712 else if (isa<ConstantAggregateZero>(C)) 713 C = Constant::getNullValue(VTy->getElementType()); 714 else if (isa<UndefValue>(C)) 715 C = UndefValue::get(VTy->getElementType()); 716 else 717 return 0; 718 } else { 719 return 0; 720 } 721 } else { 722 return 0; 723 } 724 return C; 725} 726 727 728//===----------------------------------------------------------------------===// 729// Constant Folding for Calls 730// 731 732/// canConstantFoldCallTo - Return true if its even possible to fold a call to 733/// the specified function. 734bool 735llvm::canConstantFoldCallTo(const Function *F) { 736 switch (F->getIntrinsicID()) { 737 case Intrinsic::sqrt: 738 case Intrinsic::powi: 739 case Intrinsic::bswap: 740 case Intrinsic::ctpop: 741 case Intrinsic::ctlz: 742 case Intrinsic::cttz: 743 case Intrinsic::uadd_with_overflow: 744 case Intrinsic::usub_with_overflow: 745 case Intrinsic::sadd_with_overflow: 746 case Intrinsic::ssub_with_overflow: 747 return true; 748 default: 749 return false; 750 case 0: break; 751 } 752 753 if (!F->hasName()) return false; 754 StringRef Name = F->getName(); 755 756 // In these cases, the check of the length is required. We don't want to 757 // return true for a name like "cos\0blah" which strcmp would return equal to 758 // "cos", but has length 8. 759 switch (Name[0]) { 760 default: return false; 761 case 'a': 762 return Name == "acos" || Name == "asin" || 763 Name == "atan" || Name == "atan2"; 764 case 'c': 765 return Name == "cos" || Name == "ceil" || Name == "cosf" || Name == "cosh"; 766 case 'e': 767 return Name == "exp"; 768 case 'f': 769 return Name == "fabs" || Name == "fmod" || Name == "floor"; 770 case 'l': 771 return Name == "log" || Name == "log10"; 772 case 'p': 773 return Name == "pow"; 774 case 's': 775 return Name == "sin" || Name == "sinh" || Name == "sqrt" || 776 Name == "sinf" || Name == "sqrtf"; 777 case 't': 778 return Name == "tan" || Name == "tanh"; 779 } 780} 781 782static Constant *ConstantFoldFP(double (*NativeFP)(double), double V, 783 const Type *Ty, LLVMContext &Context) { 784 errno = 0; 785 V = NativeFP(V); 786 if (errno != 0) { 787 errno = 0; 788 return 0; 789 } 790 791 if (Ty->isFloatTy()) 792 return ConstantFP::get(Context, APFloat((float)V)); 793 if (Ty->isDoubleTy()) 794 return ConstantFP::get(Context, APFloat(V)); 795 llvm_unreachable("Can only constant fold float/double"); 796 return 0; // dummy return to suppress warning 797} 798 799static Constant *ConstantFoldBinaryFP(double (*NativeFP)(double, double), 800 double V, double W, 801 const Type *Ty, 802 LLVMContext &Context) { 803 errno = 0; 804 V = NativeFP(V, W); 805 if (errno != 0) { 806 errno = 0; 807 return 0; 808 } 809 810 if (Ty->isFloatTy()) 811 return ConstantFP::get(Context, APFloat((float)V)); 812 if (Ty->isDoubleTy()) 813 return ConstantFP::get(Context, APFloat(V)); 814 llvm_unreachable("Can only constant fold float/double"); 815 return 0; // dummy return to suppress warning 816} 817 818/// ConstantFoldCall - Attempt to constant fold a call to the specified function 819/// with the specified arguments, returning null if unsuccessful. 820Constant * 821llvm::ConstantFoldCall(Function *F, 822 Constant *const *Operands, unsigned NumOperands) { 823 if (!F->hasName()) return 0; 824 LLVMContext &Context = F->getContext(); 825 StringRef Name = F->getName(); 826 827 const Type *Ty = F->getReturnType(); 828 if (NumOperands == 1) { 829 if (ConstantFP *Op = dyn_cast<ConstantFP>(Operands[0])) { 830 if (!Ty->isFloatTy() && !Ty->isDoubleTy()) 831 return 0; 832 /// Currently APFloat versions of these functions do not exist, so we use 833 /// the host native double versions. Float versions are not called 834 /// directly but for all these it is true (float)(f((double)arg)) == 835 /// f(arg). Long double not supported yet. 836 double V = Ty->isFloatTy() ? (double)Op->getValueAPF().convertToFloat() : 837 Op->getValueAPF().convertToDouble(); 838 switch (Name[0]) { 839 case 'a': 840 if (Name == "acos") 841 return ConstantFoldFP(acos, V, Ty, Context); 842 else if (Name == "asin") 843 return ConstantFoldFP(asin, V, Ty, Context); 844 else if (Name == "atan") 845 return ConstantFoldFP(atan, V, Ty, Context); 846 break; 847 case 'c': 848 if (Name == "ceil") 849 return ConstantFoldFP(ceil, V, Ty, Context); 850 else if (Name == "cos") 851 return ConstantFoldFP(cos, V, Ty, Context); 852 else if (Name == "cosh") 853 return ConstantFoldFP(cosh, V, Ty, Context); 854 else if (Name == "cosf") 855 return ConstantFoldFP(cos, V, Ty, Context); 856 break; 857 case 'e': 858 if (Name == "exp") 859 return ConstantFoldFP(exp, V, Ty, Context); 860 break; 861 case 'f': 862 if (Name == "fabs") 863 return ConstantFoldFP(fabs, V, Ty, Context); 864 else if (Name == "floor") 865 return ConstantFoldFP(floor, V, Ty, Context); 866 break; 867 case 'l': 868 if (Name == "log" && V > 0) 869 return ConstantFoldFP(log, V, Ty, Context); 870 else if (Name == "log10" && V > 0) 871 return ConstantFoldFP(log10, V, Ty, Context); 872 else if (Name == "llvm.sqrt.f32" || 873 Name == "llvm.sqrt.f64") { 874 if (V >= -0.0) 875 return ConstantFoldFP(sqrt, V, Ty, Context); 876 else // Undefined 877 return Constant::getNullValue(Ty); 878 } 879 break; 880 case 's': 881 if (Name == "sin") 882 return ConstantFoldFP(sin, V, Ty, Context); 883 else if (Name == "sinh") 884 return ConstantFoldFP(sinh, V, Ty, Context); 885 else if (Name == "sqrt" && V >= 0) 886 return ConstantFoldFP(sqrt, V, Ty, Context); 887 else if (Name == "sqrtf" && V >= 0) 888 return ConstantFoldFP(sqrt, V, Ty, Context); 889 else if (Name == "sinf") 890 return ConstantFoldFP(sin, V, Ty, Context); 891 break; 892 case 't': 893 if (Name == "tan") 894 return ConstantFoldFP(tan, V, Ty, Context); 895 else if (Name == "tanh") 896 return ConstantFoldFP(tanh, V, Ty, Context); 897 break; 898 default: 899 break; 900 } 901 return 0; 902 } 903 904 905 if (ConstantInt *Op = dyn_cast<ConstantInt>(Operands[0])) { 906 if (Name.startswith("llvm.bswap")) 907 return ConstantInt::get(Context, Op->getValue().byteSwap()); 908 else if (Name.startswith("llvm.ctpop")) 909 return ConstantInt::get(Ty, Op->getValue().countPopulation()); 910 else if (Name.startswith("llvm.cttz")) 911 return ConstantInt::get(Ty, Op->getValue().countTrailingZeros()); 912 else if (Name.startswith("llvm.ctlz")) 913 return ConstantInt::get(Ty, Op->getValue().countLeadingZeros()); 914 return 0; 915 } 916 917 return 0; 918 } 919 920 if (NumOperands == 2) { 921 if (ConstantFP *Op1 = dyn_cast<ConstantFP>(Operands[0])) { 922 if (!Ty->isFloatTy() && !Ty->isDoubleTy()) 923 return 0; 924 double Op1V = Ty->isFloatTy() ? 925 (double)Op1->getValueAPF().convertToFloat() : 926 Op1->getValueAPF().convertToDouble(); 927 if (ConstantFP *Op2 = dyn_cast<ConstantFP>(Operands[1])) { 928 if (Op2->getType() != Op1->getType()) 929 return 0; 930 931 double Op2V = Ty->isFloatTy() ? 932 (double)Op2->getValueAPF().convertToFloat(): 933 Op2->getValueAPF().convertToDouble(); 934 935 if (Name == "pow") 936 return ConstantFoldBinaryFP(pow, Op1V, Op2V, Ty, Context); 937 if (Name == "fmod") 938 return ConstantFoldBinaryFP(fmod, Op1V, Op2V, Ty, Context); 939 if (Name == "atan2") 940 return ConstantFoldBinaryFP(atan2, Op1V, Op2V, Ty, Context); 941 } else if (ConstantInt *Op2C = dyn_cast<ConstantInt>(Operands[1])) { 942 if (Name == "llvm.powi.f32") 943 return ConstantFP::get(Context, APFloat((float)std::pow((float)Op1V, 944 (int)Op2C->getZExtValue()))); 945 if (Name == "llvm.powi.f64") 946 return ConstantFP::get(Context, APFloat((double)std::pow((double)Op1V, 947 (int)Op2C->getZExtValue()))); 948 } 949 return 0; 950 } 951 952 953 if (ConstantInt *Op1 = dyn_cast<ConstantInt>(Operands[0])) { 954 if (ConstantInt *Op2 = dyn_cast<ConstantInt>(Operands[1])) { 955 switch (F->getIntrinsicID()) { 956 default: break; 957 case Intrinsic::uadd_with_overflow: { 958 Constant *Res = ConstantExpr::getAdd(Op1, Op2); // result. 959 Constant *Ops[] = { 960 Res, ConstantExpr::getICmp(CmpInst::ICMP_ULT, Res, Op1) // overflow. 961 }; 962 return ConstantStruct::get(F->getContext(), Ops, 2, false); 963 } 964 case Intrinsic::usub_with_overflow: { 965 Constant *Res = ConstantExpr::getSub(Op1, Op2); // result. 966 Constant *Ops[] = { 967 Res, ConstantExpr::getICmp(CmpInst::ICMP_UGT, Res, Op1) // overflow. 968 }; 969 return ConstantStruct::get(F->getContext(), Ops, 2, false); 970 } 971 case Intrinsic::sadd_with_overflow: { 972 Constant *Res = ConstantExpr::getAdd(Op1, Op2); // result. 973 Constant *Overflow = ConstantExpr::getSelect( 974 ConstantExpr::getICmp(CmpInst::ICMP_SGT, 975 ConstantInt::get(Op1->getType(), 0), Op1), 976 ConstantExpr::getICmp(CmpInst::ICMP_SGT, Res, Op2), 977 ConstantExpr::getICmp(CmpInst::ICMP_SLT, Res, Op2)); // overflow. 978 979 Constant *Ops[] = { Res, Overflow }; 980 return ConstantStruct::get(F->getContext(), Ops, 2, false); 981 } 982 case Intrinsic::ssub_with_overflow: { 983 Constant *Res = ConstantExpr::getSub(Op1, Op2); // result. 984 Constant *Overflow = ConstantExpr::getSelect( 985 ConstantExpr::getICmp(CmpInst::ICMP_SGT, 986 ConstantInt::get(Op2->getType(), 0), Op2), 987 ConstantExpr::getICmp(CmpInst::ICMP_SLT, Res, Op1), 988 ConstantExpr::getICmp(CmpInst::ICMP_SGT, Res, Op1)); // overflow. 989 990 Constant *Ops[] = { Res, Overflow }; 991 return ConstantStruct::get(F->getContext(), Ops, 2, false); 992 } 993 } 994 } 995 996 return 0; 997 } 998 return 0; 999 } 1000 return 0; 1001} 1002 1003