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