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