ConstantFolding.cpp revision e8e00f5efb4a22238f2407bf813de4606f30c5aa
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/Operator.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> 36 37#include "FEnv.h" 38using namespace llvm; 39 40//===----------------------------------------------------------------------===// 41// Constant Folding internal helper functions 42//===----------------------------------------------------------------------===// 43 44/// FoldBitCast - Constant fold bitcast, symbolically evaluating it with 45/// TargetData. This always returns a non-null constant, but it may be a 46/// ConstantExpr if unfoldable. 47static Constant *FoldBitCast(Constant *C, const Type *DestTy, 48 const TargetData &TD) { 49 50 // This only handles casts to vectors currently. 51 const VectorType *DestVTy = dyn_cast<VectorType>(DestTy); 52 if (DestVTy == 0) 53 return ConstantExpr::getBitCast(C, DestTy); 54 55 // If this is a scalar -> vector cast, convert the input into a <1 x scalar> 56 // vector so the code below can handle it uniformly. 57 if (isa<ConstantFP>(C) || isa<ConstantInt>(C)) { 58 Constant *Ops = C; // don't take the address of C! 59 return FoldBitCast(ConstantVector::get(Ops), DestTy, TD); 60 } 61 62 // If this is a bitcast from constant vector -> vector, fold it. 63 ConstantVector *CV = dyn_cast<ConstantVector>(C); 64 if (CV == 0) 65 return ConstantExpr::getBitCast(C, DestTy); 66 67 // If the element types match, VMCore can fold it. 68 unsigned NumDstElt = DestVTy->getNumElements(); 69 unsigned NumSrcElt = CV->getNumOperands(); 70 if (NumDstElt == NumSrcElt) 71 return ConstantExpr::getBitCast(C, DestTy); 72 73 const Type *SrcEltTy = CV->getType()->getElementType(); 74 const Type *DstEltTy = DestVTy->getElementType(); 75 76 // Otherwise, we're changing the number of elements in a vector, which 77 // requires endianness information to do the right thing. For example, 78 // bitcast (<2 x i64> <i64 0, i64 1> to <4 x i32>) 79 // folds to (little endian): 80 // <4 x i32> <i32 0, i32 0, i32 1, i32 0> 81 // and to (big endian): 82 // <4 x i32> <i32 0, i32 0, i32 0, i32 1> 83 84 // First thing is first. We only want to think about integer here, so if 85 // we have something in FP form, recast it as integer. 86 if (DstEltTy->isFloatingPointTy()) { 87 // Fold to an vector of integers with same size as our FP type. 88 unsigned FPWidth = DstEltTy->getPrimitiveSizeInBits(); 89 const Type *DestIVTy = 90 VectorType::get(IntegerType::get(C->getContext(), FPWidth), NumDstElt); 91 // Recursively handle this integer conversion, if possible. 92 C = FoldBitCast(C, DestIVTy, TD); 93 if (!C) return ConstantExpr::getBitCast(C, DestTy); 94 95 // Finally, VMCore can handle this now that #elts line up. 96 return ConstantExpr::getBitCast(C, DestTy); 97 } 98 99 // Okay, we know the destination is integer, if the input is FP, convert 100 // it to integer first. 101 if (SrcEltTy->isFloatingPointTy()) { 102 unsigned FPWidth = SrcEltTy->getPrimitiveSizeInBits(); 103 const Type *SrcIVTy = 104 VectorType::get(IntegerType::get(C->getContext(), FPWidth), NumSrcElt); 105 // Ask VMCore to do the conversion now that #elts line up. 106 C = ConstantExpr::getBitCast(C, SrcIVTy); 107 CV = dyn_cast<ConstantVector>(C); 108 if (!CV) // If VMCore wasn't able to fold it, bail out. 109 return C; 110 } 111 112 // Now we know that the input and output vectors are both integer vectors 113 // of the same size, and that their #elements is not the same. Do the 114 // conversion here, which depends on whether the input or output has 115 // more elements. 116 bool isLittleEndian = TD.isLittleEndian(); 117 118 SmallVector<Constant*, 32> Result; 119 if (NumDstElt < NumSrcElt) { 120 // Handle: bitcast (<4 x i32> <i32 0, i32 1, i32 2, i32 3> to <2 x i64>) 121 Constant *Zero = Constant::getNullValue(DstEltTy); 122 unsigned Ratio = NumSrcElt/NumDstElt; 123 unsigned SrcBitSize = SrcEltTy->getPrimitiveSizeInBits(); 124 unsigned SrcElt = 0; 125 for (unsigned i = 0; i != NumDstElt; ++i) { 126 // Build each element of the result. 127 Constant *Elt = Zero; 128 unsigned ShiftAmt = isLittleEndian ? 0 : SrcBitSize*(Ratio-1); 129 for (unsigned j = 0; j != Ratio; ++j) { 130 Constant *Src = dyn_cast<ConstantInt>(CV->getOperand(SrcElt++)); 131 if (!Src) // Reject constantexpr elements. 132 return ConstantExpr::getBitCast(C, DestTy); 133 134 // Zero extend the element to the right size. 135 Src = ConstantExpr::getZExt(Src, Elt->getType()); 136 137 // Shift it to the right place, depending on endianness. 138 Src = ConstantExpr::getShl(Src, 139 ConstantInt::get(Src->getType(), ShiftAmt)); 140 ShiftAmt += isLittleEndian ? SrcBitSize : -SrcBitSize; 141 142 // Mix it in. 143 Elt = ConstantExpr::getOr(Elt, Src); 144 } 145 Result.push_back(Elt); 146 } 147 } else { 148 // Handle: bitcast (<2 x i64> <i64 0, i64 1> to <4 x i32>) 149 unsigned Ratio = NumDstElt/NumSrcElt; 150 unsigned DstBitSize = DstEltTy->getPrimitiveSizeInBits(); 151 152 // Loop over each source value, expanding into multiple results. 153 for (unsigned i = 0; i != NumSrcElt; ++i) { 154 Constant *Src = dyn_cast<ConstantInt>(CV->getOperand(i)); 155 if (!Src) // Reject constantexpr elements. 156 return ConstantExpr::getBitCast(C, DestTy); 157 158 unsigned ShiftAmt = isLittleEndian ? 0 : DstBitSize*(Ratio-1); 159 for (unsigned j = 0; j != Ratio; ++j) { 160 // Shift the piece of the value into the right place, depending on 161 // endianness. 162 Constant *Elt = ConstantExpr::getLShr(Src, 163 ConstantInt::get(Src->getType(), ShiftAmt)); 164 ShiftAmt += isLittleEndian ? DstBitSize : -DstBitSize; 165 166 // Truncate and remember this piece. 167 Result.push_back(ConstantExpr::getTrunc(Elt, DstEltTy)); 168 } 169 } 170 } 171 172 return ConstantVector::get(Result); 173} 174 175 176/// IsConstantOffsetFromGlobal - If this constant is actually a constant offset 177/// from a global, return the global and the constant. Because of 178/// constantexprs, this function is recursive. 179static bool IsConstantOffsetFromGlobal(Constant *C, GlobalValue *&GV, 180 int64_t &Offset, const TargetData &TD) { 181 // Trivial case, constant is the global. 182 if ((GV = dyn_cast<GlobalValue>(C))) { 183 Offset = 0; 184 return true; 185 } 186 187 // Otherwise, if this isn't a constant expr, bail out. 188 ConstantExpr *CE = dyn_cast<ConstantExpr>(C); 189 if (!CE) return false; 190 191 // Look through ptr->int and ptr->ptr casts. 192 if (CE->getOpcode() == Instruction::PtrToInt || 193 CE->getOpcode() == Instruction::BitCast) 194 return IsConstantOffsetFromGlobal(CE->getOperand(0), GV, Offset, TD); 195 196 // i32* getelementptr ([5 x i32]* @a, i32 0, i32 5) 197 if (CE->getOpcode() == Instruction::GetElementPtr) { 198 // Cannot compute this if the element type of the pointer is missing size 199 // info. 200 if (!cast<PointerType>(CE->getOperand(0)->getType()) 201 ->getElementType()->isSized()) 202 return false; 203 204 // If the base isn't a global+constant, we aren't either. 205 if (!IsConstantOffsetFromGlobal(CE->getOperand(0), GV, Offset, TD)) 206 return false; 207 208 // Otherwise, add any offset that our operands provide. 209 gep_type_iterator GTI = gep_type_begin(CE); 210 for (User::const_op_iterator i = CE->op_begin() + 1, e = CE->op_end(); 211 i != e; ++i, ++GTI) { 212 ConstantInt *CI = dyn_cast<ConstantInt>(*i); 213 if (!CI) return false; // Index isn't a simple constant? 214 if (CI->isZero()) continue; // Not adding anything. 215 216 if (const StructType *ST = dyn_cast<StructType>(*GTI)) { 217 // N = N + Offset 218 Offset += TD.getStructLayout(ST)->getElementOffset(CI->getZExtValue()); 219 } else { 220 const SequentialType *SQT = cast<SequentialType>(*GTI); 221 Offset += TD.getTypeAllocSize(SQT->getElementType())*CI->getSExtValue(); 222 } 223 } 224 return true; 225 } 226 227 return false; 228} 229 230/// ReadDataFromGlobal - Recursive helper to read bits out of global. C is the 231/// constant being copied out of. ByteOffset is an offset into C. CurPtr is the 232/// pointer to copy results into and BytesLeft is the number of bytes left in 233/// the CurPtr buffer. TD is the target data. 234static bool ReadDataFromGlobal(Constant *C, uint64_t ByteOffset, 235 unsigned char *CurPtr, unsigned BytesLeft, 236 const TargetData &TD) { 237 assert(ByteOffset <= TD.getTypeAllocSize(C->getType()) && 238 "Out of range access"); 239 240 // If this element is zero or undefined, we can just return since *CurPtr is 241 // zero initialized. 242 if (isa<ConstantAggregateZero>(C) || isa<UndefValue>(C)) 243 return true; 244 245 if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) { 246 if (CI->getBitWidth() > 64 || 247 (CI->getBitWidth() & 7) != 0) 248 return false; 249 250 uint64_t Val = CI->getZExtValue(); 251 unsigned IntBytes = unsigned(CI->getBitWidth()/8); 252 253 for (unsigned i = 0; i != BytesLeft && ByteOffset != IntBytes; ++i) { 254 CurPtr[i] = (unsigned char)(Val >> (ByteOffset * 8)); 255 ++ByteOffset; 256 } 257 return true; 258 } 259 260 if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) { 261 if (CFP->getType()->isDoubleTy()) { 262 C = FoldBitCast(C, Type::getInt64Ty(C->getContext()), TD); 263 return ReadDataFromGlobal(C, ByteOffset, CurPtr, BytesLeft, TD); 264 } 265 if (CFP->getType()->isFloatTy()){ 266 C = FoldBitCast(C, Type::getInt32Ty(C->getContext()), TD); 267 return ReadDataFromGlobal(C, ByteOffset, CurPtr, BytesLeft, TD); 268 } 269 return false; 270 } 271 272 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) { 273 const StructLayout *SL = TD.getStructLayout(CS->getType()); 274 unsigned Index = SL->getElementContainingOffset(ByteOffset); 275 uint64_t CurEltOffset = SL->getElementOffset(Index); 276 ByteOffset -= CurEltOffset; 277 278 while (1) { 279 // If the element access is to the element itself and not to tail padding, 280 // read the bytes from the element. 281 uint64_t EltSize = TD.getTypeAllocSize(CS->getOperand(Index)->getType()); 282 283 if (ByteOffset < EltSize && 284 !ReadDataFromGlobal(CS->getOperand(Index), ByteOffset, CurPtr, 285 BytesLeft, TD)) 286 return false; 287 288 ++Index; 289 290 // Check to see if we read from the last struct element, if so we're done. 291 if (Index == CS->getType()->getNumElements()) 292 return true; 293 294 // If we read all of the bytes we needed from this element we're done. 295 uint64_t NextEltOffset = SL->getElementOffset(Index); 296 297 if (BytesLeft <= NextEltOffset-CurEltOffset-ByteOffset) 298 return true; 299 300 // Move to the next element of the struct. 301 CurPtr += NextEltOffset-CurEltOffset-ByteOffset; 302 BytesLeft -= NextEltOffset-CurEltOffset-ByteOffset; 303 ByteOffset = 0; 304 CurEltOffset = NextEltOffset; 305 } 306 // not reached. 307 } 308 309 if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) { 310 uint64_t EltSize = TD.getTypeAllocSize(CA->getType()->getElementType()); 311 uint64_t Index = ByteOffset / EltSize; 312 uint64_t Offset = ByteOffset - Index * EltSize; 313 for (; Index != CA->getType()->getNumElements(); ++Index) { 314 if (!ReadDataFromGlobal(CA->getOperand(Index), Offset, CurPtr, 315 BytesLeft, TD)) 316 return false; 317 if (EltSize >= BytesLeft) 318 return true; 319 320 Offset = 0; 321 BytesLeft -= EltSize; 322 CurPtr += EltSize; 323 } 324 return true; 325 } 326 327 if (ConstantVector *CV = dyn_cast<ConstantVector>(C)) { 328 uint64_t EltSize = TD.getTypeAllocSize(CV->getType()->getElementType()); 329 uint64_t Index = ByteOffset / EltSize; 330 uint64_t Offset = ByteOffset - Index * EltSize; 331 for (; Index != CV->getType()->getNumElements(); ++Index) { 332 if (!ReadDataFromGlobal(CV->getOperand(Index), Offset, CurPtr, 333 BytesLeft, TD)) 334 return false; 335 if (EltSize >= BytesLeft) 336 return true; 337 338 Offset = 0; 339 BytesLeft -= EltSize; 340 CurPtr += EltSize; 341 } 342 return true; 343 } 344 345 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { 346 if (CE->getOpcode() == Instruction::IntToPtr && 347 CE->getOperand(0)->getType() == TD.getIntPtrType(CE->getContext())) 348 return ReadDataFromGlobal(CE->getOperand(0), ByteOffset, CurPtr, 349 BytesLeft, TD); 350 } 351 352 // Otherwise, unknown initializer type. 353 return false; 354} 355 356static Constant *FoldReinterpretLoadFromConstPtr(Constant *C, 357 const TargetData &TD) { 358 const Type *LoadTy = cast<PointerType>(C->getType())->getElementType(); 359 const IntegerType *IntType = dyn_cast<IntegerType>(LoadTy); 360 361 // If this isn't an integer load we can't fold it directly. 362 if (!IntType) { 363 // If this is a float/double load, we can try folding it as an int32/64 load 364 // and then bitcast the result. This can be useful for union cases. Note 365 // that address spaces don't matter here since we're not going to result in 366 // an actual new load. 367 const Type *MapTy; 368 if (LoadTy->isFloatTy()) 369 MapTy = Type::getInt32PtrTy(C->getContext()); 370 else if (LoadTy->isDoubleTy()) 371 MapTy = Type::getInt64PtrTy(C->getContext()); 372 else if (LoadTy->isVectorTy()) { 373 MapTy = IntegerType::get(C->getContext(), 374 TD.getTypeAllocSizeInBits(LoadTy)); 375 MapTy = PointerType::getUnqual(MapTy); 376 } else 377 return 0; 378 379 C = FoldBitCast(C, MapTy, TD); 380 if (Constant *Res = FoldReinterpretLoadFromConstPtr(C, TD)) 381 return FoldBitCast(Res, LoadTy, TD); 382 return 0; 383 } 384 385 unsigned BytesLoaded = (IntType->getBitWidth() + 7) / 8; 386 if (BytesLoaded > 32 || BytesLoaded == 0) return 0; 387 388 GlobalValue *GVal; 389 int64_t Offset; 390 if (!IsConstantOffsetFromGlobal(C, GVal, Offset, TD)) 391 return 0; 392 393 GlobalVariable *GV = dyn_cast<GlobalVariable>(GVal); 394 if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer() || 395 !GV->getInitializer()->getType()->isSized()) 396 return 0; 397 398 // If we're loading off the beginning of the global, some bytes may be valid, 399 // but we don't try to handle this. 400 if (Offset < 0) return 0; 401 402 // If we're not accessing anything in this constant, the result is undefined. 403 if (uint64_t(Offset) >= TD.getTypeAllocSize(GV->getInitializer()->getType())) 404 return UndefValue::get(IntType); 405 406 unsigned char RawBytes[32] = {0}; 407 if (!ReadDataFromGlobal(GV->getInitializer(), Offset, RawBytes, 408 BytesLoaded, TD)) 409 return 0; 410 411 APInt ResultVal = APInt(IntType->getBitWidth(), RawBytes[BytesLoaded-1]); 412 for (unsigned i = 1; i != BytesLoaded; ++i) { 413 ResultVal <<= 8; 414 ResultVal |= RawBytes[BytesLoaded-1-i]; 415 } 416 417 return ConstantInt::get(IntType->getContext(), ResultVal); 418} 419 420/// ConstantFoldLoadFromConstPtr - Return the value that a load from C would 421/// produce if it is constant and determinable. If this is not determinable, 422/// return null. 423Constant *llvm::ConstantFoldLoadFromConstPtr(Constant *C, 424 const TargetData *TD) { 425 // First, try the easy cases: 426 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C)) 427 if (GV->isConstant() && GV->hasDefinitiveInitializer()) 428 return GV->getInitializer(); 429 430 // If the loaded value isn't a constant expr, we can't handle it. 431 ConstantExpr *CE = dyn_cast<ConstantExpr>(C); 432 if (!CE) return 0; 433 434 if (CE->getOpcode() == Instruction::GetElementPtr) { 435 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0))) 436 if (GV->isConstant() && GV->hasDefinitiveInitializer()) 437 if (Constant *V = 438 ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE)) 439 return V; 440 } 441 442 // Instead of loading constant c string, use corresponding integer value 443 // directly if string length is small enough. 444 std::string Str; 445 if (TD && GetConstantStringInfo(CE, Str) && !Str.empty()) { 446 unsigned StrLen = Str.length(); 447 const Type *Ty = cast<PointerType>(CE->getType())->getElementType(); 448 unsigned NumBits = Ty->getPrimitiveSizeInBits(); 449 // Replace load with immediate integer if the result is an integer or fp 450 // value. 451 if ((NumBits >> 3) == StrLen + 1 && (NumBits & 7) == 0 && 452 (isa<IntegerType>(Ty) || Ty->isFloatingPointTy())) { 453 APInt StrVal(NumBits, 0); 454 APInt SingleChar(NumBits, 0); 455 if (TD->isLittleEndian()) { 456 for (signed i = StrLen-1; i >= 0; i--) { 457 SingleChar = (uint64_t) Str[i] & UCHAR_MAX; 458 StrVal = (StrVal << 8) | SingleChar; 459 } 460 } else { 461 for (unsigned i = 0; i < StrLen; i++) { 462 SingleChar = (uint64_t) Str[i] & UCHAR_MAX; 463 StrVal = (StrVal << 8) | SingleChar; 464 } 465 // Append NULL at the end. 466 SingleChar = 0; 467 StrVal = (StrVal << 8) | SingleChar; 468 } 469 470 Constant *Res = ConstantInt::get(CE->getContext(), StrVal); 471 if (Ty->isFloatingPointTy()) 472 Res = ConstantExpr::getBitCast(Res, Ty); 473 return Res; 474 } 475 } 476 477 // If this load comes from anywhere in a constant global, and if the global 478 // is all undef or zero, we know what it loads. 479 if (GlobalVariable *GV = 480 dyn_cast<GlobalVariable>(GetUnderlyingObject(CE, TD))) { 481 if (GV->isConstant() && GV->hasDefinitiveInitializer()) { 482 const Type *ResTy = cast<PointerType>(C->getType())->getElementType(); 483 if (GV->getInitializer()->isNullValue()) 484 return Constant::getNullValue(ResTy); 485 if (isa<UndefValue>(GV->getInitializer())) 486 return UndefValue::get(ResTy); 487 } 488 } 489 490 // Try hard to fold loads from bitcasted strange and non-type-safe things. We 491 // currently don't do any of this for big endian systems. It can be 492 // generalized in the future if someone is interested. 493 if (TD && TD->isLittleEndian()) 494 return FoldReinterpretLoadFromConstPtr(CE, *TD); 495 return 0; 496} 497 498static Constant *ConstantFoldLoadInst(const LoadInst *LI, const TargetData *TD){ 499 if (LI->isVolatile()) return 0; 500 501 if (Constant *C = dyn_cast<Constant>(LI->getOperand(0))) 502 return ConstantFoldLoadFromConstPtr(C, TD); 503 504 return 0; 505} 506 507/// SymbolicallyEvaluateBinop - One of Op0/Op1 is a constant expression. 508/// Attempt to symbolically evaluate the result of a binary operator merging 509/// these together. If target data info is available, it is provided as TD, 510/// otherwise TD is null. 511static Constant *SymbolicallyEvaluateBinop(unsigned Opc, Constant *Op0, 512 Constant *Op1, const TargetData *TD){ 513 // SROA 514 515 // Fold (and 0xffffffff00000000, (shl x, 32)) -> shl. 516 // Fold (lshr (or X, Y), 32) -> (lshr [X/Y], 32) if one doesn't contribute 517 // bits. 518 519 520 // If the constant expr is something like &A[123] - &A[4].f, fold this into a 521 // constant. This happens frequently when iterating over a global array. 522 if (Opc == Instruction::Sub && TD) { 523 GlobalValue *GV1, *GV2; 524 int64_t Offs1, Offs2; 525 526 if (IsConstantOffsetFromGlobal(Op0, GV1, Offs1, *TD)) 527 if (IsConstantOffsetFromGlobal(Op1, GV2, Offs2, *TD) && 528 GV1 == GV2) { 529 // (&GV+C1) - (&GV+C2) -> C1-C2, pointer arithmetic cannot overflow. 530 return ConstantInt::get(Op0->getType(), Offs1-Offs2); 531 } 532 } 533 534 return 0; 535} 536 537/// CastGEPIndices - If array indices are not pointer-sized integers, 538/// explicitly cast them so that they aren't implicitly casted by the 539/// getelementptr. 540static Constant *CastGEPIndices(Constant *const *Ops, unsigned NumOps, 541 const Type *ResultTy, 542 const TargetData *TD) { 543 if (!TD) return 0; 544 const Type *IntPtrTy = TD->getIntPtrType(ResultTy->getContext()); 545 546 bool Any = false; 547 SmallVector<Constant*, 32> NewIdxs; 548 for (unsigned i = 1; i != NumOps; ++i) { 549 if ((i == 1 || 550 !isa<StructType>(GetElementPtrInst::getIndexedType(Ops[0]->getType(), 551 reinterpret_cast<Value *const *>(Ops+1), 552 i-1))) && 553 Ops[i]->getType() != IntPtrTy) { 554 Any = true; 555 NewIdxs.push_back(ConstantExpr::getCast(CastInst::getCastOpcode(Ops[i], 556 true, 557 IntPtrTy, 558 true), 559 Ops[i], IntPtrTy)); 560 } else 561 NewIdxs.push_back(Ops[i]); 562 } 563 if (!Any) return 0; 564 565 Constant *C = 566 ConstantExpr::getGetElementPtr(Ops[0], &NewIdxs[0], NewIdxs.size()); 567 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) 568 if (Constant *Folded = ConstantFoldConstantExpression(CE, TD)) 569 C = Folded; 570 return C; 571} 572 573/// SymbolicallyEvaluateGEP - If we can symbolically evaluate the specified GEP 574/// constant expression, do so. 575static Constant *SymbolicallyEvaluateGEP(Constant *const *Ops, unsigned NumOps, 576 const Type *ResultTy, 577 const TargetData *TD) { 578 Constant *Ptr = Ops[0]; 579 if (!TD || !cast<PointerType>(Ptr->getType())->getElementType()->isSized()) 580 return 0; 581 582 const Type *IntPtrTy = TD->getIntPtrType(Ptr->getContext()); 583 584 // If this is a constant expr gep that is effectively computing an 585 // "offsetof", fold it into 'cast int Size to T*' instead of 'gep 0, 0, 12' 586 for (unsigned i = 1; i != NumOps; ++i) 587 if (!isa<ConstantInt>(Ops[i])) { 588 589 // If this is "gep i8* Ptr, (sub 0, V)", fold this as: 590 // "inttoptr (sub (ptrtoint Ptr), V)" 591 if (NumOps == 2 && 592 cast<PointerType>(ResultTy)->getElementType()->isIntegerTy(8)) { 593 ConstantExpr *CE = dyn_cast<ConstantExpr>(Ops[1]); 594 assert((CE == 0 || CE->getType() == IntPtrTy) && 595 "CastGEPIndices didn't canonicalize index types!"); 596 if (CE && CE->getOpcode() == Instruction::Sub && 597 CE->getOperand(0)->isNullValue()) { 598 Constant *Res = ConstantExpr::getPtrToInt(Ptr, CE->getType()); 599 Res = ConstantExpr::getSub(Res, CE->getOperand(1)); 600 Res = ConstantExpr::getIntToPtr(Res, ResultTy); 601 if (ConstantExpr *ResCE = dyn_cast<ConstantExpr>(Res)) 602 Res = ConstantFoldConstantExpression(ResCE, TD); 603 return Res; 604 } 605 } 606 return 0; 607 } 608 609 unsigned BitWidth = TD->getTypeSizeInBits(IntPtrTy); 610 APInt Offset = APInt(BitWidth, 611 TD->getIndexedOffset(Ptr->getType(), 612 (Value**)Ops+1, NumOps-1)); 613 Ptr = cast<Constant>(Ptr->stripPointerCasts()); 614 615 // If this is a GEP of a GEP, fold it all into a single GEP. 616 while (GEPOperator *GEP = dyn_cast<GEPOperator>(Ptr)) { 617 SmallVector<Value *, 4> NestedOps(GEP->op_begin()+1, GEP->op_end()); 618 619 // Do not try the incorporate the sub-GEP if some index is not a number. 620 bool AllConstantInt = true; 621 for (unsigned i = 0, e = NestedOps.size(); i != e; ++i) 622 if (!isa<ConstantInt>(NestedOps[i])) { 623 AllConstantInt = false; 624 break; 625 } 626 if (!AllConstantInt) 627 break; 628 629 Ptr = cast<Constant>(GEP->getOperand(0)); 630 Offset += APInt(BitWidth, 631 TD->getIndexedOffset(Ptr->getType(), 632 (Value**)NestedOps.data(), 633 NestedOps.size())); 634 Ptr = cast<Constant>(Ptr->stripPointerCasts()); 635 } 636 637 // If the base value for this address is a literal integer value, fold the 638 // getelementptr to the resulting integer value casted to the pointer type. 639 APInt BasePtr(BitWidth, 0); 640 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) 641 if (CE->getOpcode() == Instruction::IntToPtr) 642 if (ConstantInt *Base = dyn_cast<ConstantInt>(CE->getOperand(0))) 643 BasePtr = Base->getValue().zextOrTrunc(BitWidth); 644 if (Ptr->isNullValue() || BasePtr != 0) { 645 Constant *C = ConstantInt::get(Ptr->getContext(), Offset+BasePtr); 646 return ConstantExpr::getIntToPtr(C, ResultTy); 647 } 648 649 // Otherwise form a regular getelementptr. Recompute the indices so that 650 // we eliminate over-indexing of the notional static type array bounds. 651 // This makes it easy to determine if the getelementptr is "inbounds". 652 // Also, this helps GlobalOpt do SROA on GlobalVariables. 653 const Type *Ty = Ptr->getType(); 654 SmallVector<Constant*, 32> NewIdxs; 655 do { 656 if (const SequentialType *ATy = dyn_cast<SequentialType>(Ty)) { 657 if (ATy->isPointerTy()) { 658 // The only pointer indexing we'll do is on the first index of the GEP. 659 if (!NewIdxs.empty()) 660 break; 661 662 // Only handle pointers to sized types, not pointers to functions. 663 if (!ATy->getElementType()->isSized()) 664 return 0; 665 } 666 667 // Determine which element of the array the offset points into. 668 APInt ElemSize(BitWidth, TD->getTypeAllocSize(ATy->getElementType())); 669 const IntegerType *IntPtrTy = TD->getIntPtrType(Ty->getContext()); 670 if (ElemSize == 0) 671 // The element size is 0. This may be [0 x Ty]*, so just use a zero 672 // index for this level and proceed to the next level to see if it can 673 // accommodate the offset. 674 NewIdxs.push_back(ConstantInt::get(IntPtrTy, 0)); 675 else { 676 // The element size is non-zero divide the offset by the element 677 // size (rounding down), to compute the index at this level. 678 APInt NewIdx = Offset.udiv(ElemSize); 679 Offset -= NewIdx * ElemSize; 680 NewIdxs.push_back(ConstantInt::get(IntPtrTy, NewIdx)); 681 } 682 Ty = ATy->getElementType(); 683 } else if (const StructType *STy = dyn_cast<StructType>(Ty)) { 684 // Determine which field of the struct the offset points into. The 685 // getZExtValue is at least as safe as the StructLayout API because we 686 // know the offset is within the struct at this point. 687 const StructLayout &SL = *TD->getStructLayout(STy); 688 unsigned ElIdx = SL.getElementContainingOffset(Offset.getZExtValue()); 689 NewIdxs.push_back(ConstantInt::get(Type::getInt32Ty(Ty->getContext()), 690 ElIdx)); 691 Offset -= APInt(BitWidth, SL.getElementOffset(ElIdx)); 692 Ty = STy->getTypeAtIndex(ElIdx); 693 } else { 694 // We've reached some non-indexable type. 695 break; 696 } 697 } while (Ty != cast<PointerType>(ResultTy)->getElementType()); 698 699 // If we haven't used up the entire offset by descending the static 700 // type, then the offset is pointing into the middle of an indivisible 701 // member, so we can't simplify it. 702 if (Offset != 0) 703 return 0; 704 705 // Create a GEP. 706 Constant *C = 707 ConstantExpr::getGetElementPtr(Ptr, &NewIdxs[0], NewIdxs.size()); 708 assert(cast<PointerType>(C->getType())->getElementType() == Ty && 709 "Computed GetElementPtr has unexpected type!"); 710 711 // If we ended up indexing a member with a type that doesn't match 712 // the type of what the original indices indexed, add a cast. 713 if (Ty != cast<PointerType>(ResultTy)->getElementType()) 714 C = FoldBitCast(C, ResultTy, *TD); 715 716 return C; 717} 718 719 720 721//===----------------------------------------------------------------------===// 722// Constant Folding public APIs 723//===----------------------------------------------------------------------===// 724 725/// ConstantFoldInstruction - Try to constant fold the specified instruction. 726/// If successful, the constant result is returned, if not, null is returned. 727/// Note that this fails if not all of the operands are constant. Otherwise, 728/// this function can only fail when attempting to fold instructions like loads 729/// and stores, which have no constant expression form. 730Constant *llvm::ConstantFoldInstruction(Instruction *I, const TargetData *TD) { 731 // Handle PHI nodes quickly here... 732 if (PHINode *PN = dyn_cast<PHINode>(I)) { 733 Constant *CommonValue = 0; 734 735 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 736 Value *Incoming = PN->getIncomingValue(i); 737 // If the incoming value is undef then skip it. Note that while we could 738 // skip the value if it is equal to the phi node itself we choose not to 739 // because that would break the rule that constant folding only applies if 740 // all operands are constants. 741 if (isa<UndefValue>(Incoming)) 742 continue; 743 // If the incoming value is not a constant, or is a different constant to 744 // the one we saw previously, then give up. 745 Constant *C = dyn_cast<Constant>(Incoming); 746 if (!C || (CommonValue && C != CommonValue)) 747 return 0; 748 CommonValue = C; 749 } 750 751 // If we reach here, all incoming values are the same constant or undef. 752 return CommonValue ? CommonValue : UndefValue::get(PN->getType()); 753 } 754 755 // Scan the operand list, checking to see if they are all constants, if so, 756 // hand off to ConstantFoldInstOperands. 757 SmallVector<Constant*, 8> Ops; 758 for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) 759 if (Constant *Op = dyn_cast<Constant>(*i)) 760 Ops.push_back(Op); 761 else 762 return 0; // All operands not constant! 763 764 if (const CmpInst *CI = dyn_cast<CmpInst>(I)) 765 return ConstantFoldCompareInstOperands(CI->getPredicate(), Ops[0], Ops[1], 766 TD); 767 768 if (const LoadInst *LI = dyn_cast<LoadInst>(I)) 769 return ConstantFoldLoadInst(LI, TD); 770 771 if (InsertValueInst *IVI = dyn_cast<InsertValueInst>(I)) 772 return ConstantExpr::getInsertValue( 773 cast<Constant>(IVI->getAggregateOperand()), 774 cast<Constant>(IVI->getInsertedValueOperand()), 775 IVI->idx_begin(), IVI->getNumIndices()); 776 777 if (ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(I)) 778 return ConstantExpr::getExtractValue( 779 cast<Constant>(EVI->getAggregateOperand()), 780 EVI->idx_begin(), EVI->getNumIndices()); 781 782 return ConstantFoldInstOperands(I->getOpcode(), I->getType(), 783 Ops.data(), Ops.size(), TD); 784} 785 786/// ConstantFoldConstantExpression - Attempt to fold the constant expression 787/// using the specified TargetData. If successful, the constant result is 788/// result is returned, if not, null is returned. 789Constant *llvm::ConstantFoldConstantExpression(const ConstantExpr *CE, 790 const TargetData *TD) { 791 SmallVector<Constant*, 8> Ops; 792 for (User::const_op_iterator i = CE->op_begin(), e = CE->op_end(); 793 i != e; ++i) { 794 Constant *NewC = cast<Constant>(*i); 795 // Recursively fold the ConstantExpr's operands. 796 if (ConstantExpr *NewCE = dyn_cast<ConstantExpr>(NewC)) 797 NewC = ConstantFoldConstantExpression(NewCE, TD); 798 Ops.push_back(NewC); 799 } 800 801 if (CE->isCompare()) 802 return ConstantFoldCompareInstOperands(CE->getPredicate(), Ops[0], Ops[1], 803 TD); 804 return ConstantFoldInstOperands(CE->getOpcode(), CE->getType(), 805 Ops.data(), Ops.size(), TD); 806} 807 808/// ConstantFoldInstOperands - Attempt to constant fold an instruction with the 809/// specified opcode and operands. If successful, the constant result is 810/// returned, if not, null is returned. Note that this function can fail when 811/// attempting to fold instructions like loads and stores, which have no 812/// constant expression form. 813/// 814/// TODO: This function neither utilizes nor preserves nsw/nuw/inbounds/etc 815/// information, due to only being passed an opcode and operands. Constant 816/// folding using this function strips this information. 817/// 818Constant *llvm::ConstantFoldInstOperands(unsigned Opcode, const Type *DestTy, 819 Constant* const* Ops, unsigned NumOps, 820 const TargetData *TD) { 821 // Handle easy binops first. 822 if (Instruction::isBinaryOp(Opcode)) { 823 if (isa<ConstantExpr>(Ops[0]) || isa<ConstantExpr>(Ops[1])) 824 if (Constant *C = SymbolicallyEvaluateBinop(Opcode, Ops[0], Ops[1], TD)) 825 return C; 826 827 return ConstantExpr::get(Opcode, Ops[0], Ops[1]); 828 } 829 830 switch (Opcode) { 831 default: return 0; 832 case Instruction::ICmp: 833 case Instruction::FCmp: assert(0 && "Invalid for compares"); 834 case Instruction::Call: 835 if (Function *F = dyn_cast<Function>(Ops[NumOps - 1])) 836 if (canConstantFoldCallTo(F)) 837 return ConstantFoldCall(F, Ops, NumOps - 1); 838 return 0; 839 case Instruction::PtrToInt: 840 // If the input is a inttoptr, eliminate the pair. This requires knowing 841 // the width of a pointer, so it can't be done in ConstantExpr::getCast. 842 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ops[0])) { 843 if (TD && CE->getOpcode() == Instruction::IntToPtr) { 844 Constant *Input = CE->getOperand(0); 845 unsigned InWidth = Input->getType()->getScalarSizeInBits(); 846 if (TD->getPointerSizeInBits() < InWidth) { 847 Constant *Mask = 848 ConstantInt::get(CE->getContext(), APInt::getLowBitsSet(InWidth, 849 TD->getPointerSizeInBits())); 850 Input = ConstantExpr::getAnd(Input, Mask); 851 } 852 // Do a zext or trunc to get to the dest size. 853 return ConstantExpr::getIntegerCast(Input, DestTy, false); 854 } 855 } 856 return ConstantExpr::getCast(Opcode, Ops[0], DestTy); 857 case Instruction::IntToPtr: 858 // If the input is a ptrtoint, turn the pair into a ptr to ptr bitcast if 859 // the int size is >= the ptr size. This requires knowing the width of a 860 // pointer, so it can't be done in ConstantExpr::getCast. 861 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ops[0])) 862 if (TD && 863 TD->getPointerSizeInBits() <= CE->getType()->getScalarSizeInBits() && 864 CE->getOpcode() == Instruction::PtrToInt) 865 return FoldBitCast(CE->getOperand(0), DestTy, *TD); 866 867 return ConstantExpr::getCast(Opcode, Ops[0], DestTy); 868 case Instruction::Trunc: 869 case Instruction::ZExt: 870 case Instruction::SExt: 871 case Instruction::FPTrunc: 872 case Instruction::FPExt: 873 case Instruction::UIToFP: 874 case Instruction::SIToFP: 875 case Instruction::FPToUI: 876 case Instruction::FPToSI: 877 return ConstantExpr::getCast(Opcode, Ops[0], DestTy); 878 case Instruction::BitCast: 879 if (TD) 880 return FoldBitCast(Ops[0], DestTy, *TD); 881 return ConstantExpr::getBitCast(Ops[0], DestTy); 882 case Instruction::Select: 883 return ConstantExpr::getSelect(Ops[0], Ops[1], Ops[2]); 884 case Instruction::ExtractElement: 885 return ConstantExpr::getExtractElement(Ops[0], Ops[1]); 886 case Instruction::InsertElement: 887 return ConstantExpr::getInsertElement(Ops[0], Ops[1], Ops[2]); 888 case Instruction::ShuffleVector: 889 return ConstantExpr::getShuffleVector(Ops[0], Ops[1], Ops[2]); 890 case Instruction::GetElementPtr: 891 if (Constant *C = CastGEPIndices(Ops, NumOps, DestTy, TD)) 892 return C; 893 if (Constant *C = SymbolicallyEvaluateGEP(Ops, NumOps, DestTy, TD)) 894 return C; 895 896 return ConstantExpr::getGetElementPtr(Ops[0], Ops+1, NumOps-1); 897 } 898} 899 900/// ConstantFoldCompareInstOperands - Attempt to constant fold a compare 901/// instruction (icmp/fcmp) with the specified operands. If it fails, it 902/// returns a constant expression of the specified operands. 903/// 904Constant *llvm::ConstantFoldCompareInstOperands(unsigned Predicate, 905 Constant *Ops0, Constant *Ops1, 906 const TargetData *TD) { 907 // fold: icmp (inttoptr x), null -> icmp x, 0 908 // fold: icmp (ptrtoint x), 0 -> icmp x, null 909 // fold: icmp (inttoptr x), (inttoptr y) -> icmp trunc/zext x, trunc/zext y 910 // fold: icmp (ptrtoint x), (ptrtoint y) -> icmp x, y 911 // 912 // ConstantExpr::getCompare cannot do this, because it doesn't have TD 913 // around to know if bit truncation is happening. 914 if (ConstantExpr *CE0 = dyn_cast<ConstantExpr>(Ops0)) { 915 if (TD && Ops1->isNullValue()) { 916 const Type *IntPtrTy = TD->getIntPtrType(CE0->getContext()); 917 if (CE0->getOpcode() == Instruction::IntToPtr) { 918 // Convert the integer value to the right size to ensure we get the 919 // proper extension or truncation. 920 Constant *C = ConstantExpr::getIntegerCast(CE0->getOperand(0), 921 IntPtrTy, false); 922 Constant *Null = Constant::getNullValue(C->getType()); 923 return ConstantFoldCompareInstOperands(Predicate, C, Null, TD); 924 } 925 926 // Only do this transformation if the int is intptrty in size, otherwise 927 // there is a truncation or extension that we aren't modeling. 928 if (CE0->getOpcode() == Instruction::PtrToInt && 929 CE0->getType() == IntPtrTy) { 930 Constant *C = CE0->getOperand(0); 931 Constant *Null = Constant::getNullValue(C->getType()); 932 return ConstantFoldCompareInstOperands(Predicate, C, Null, TD); 933 } 934 } 935 936 if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(Ops1)) { 937 if (TD && CE0->getOpcode() == CE1->getOpcode()) { 938 const Type *IntPtrTy = TD->getIntPtrType(CE0->getContext()); 939 940 if (CE0->getOpcode() == Instruction::IntToPtr) { 941 // Convert the integer value to the right size to ensure we get the 942 // proper extension or truncation. 943 Constant *C0 = ConstantExpr::getIntegerCast(CE0->getOperand(0), 944 IntPtrTy, false); 945 Constant *C1 = ConstantExpr::getIntegerCast(CE1->getOperand(0), 946 IntPtrTy, false); 947 return ConstantFoldCompareInstOperands(Predicate, C0, C1, TD); 948 } 949 950 // Only do this transformation if the int is intptrty in size, otherwise 951 // there is a truncation or extension that we aren't modeling. 952 if ((CE0->getOpcode() == Instruction::PtrToInt && 953 CE0->getType() == IntPtrTy && 954 CE0->getOperand(0)->getType() == CE1->getOperand(0)->getType())) 955 return ConstantFoldCompareInstOperands(Predicate, CE0->getOperand(0), 956 CE1->getOperand(0), TD); 957 } 958 } 959 960 // icmp eq (or x, y), 0 -> (icmp eq x, 0) & (icmp eq y, 0) 961 // icmp ne (or x, y), 0 -> (icmp ne x, 0) | (icmp ne y, 0) 962 if ((Predicate == ICmpInst::ICMP_EQ || Predicate == ICmpInst::ICMP_NE) && 963 CE0->getOpcode() == Instruction::Or && Ops1->isNullValue()) { 964 Constant *LHS = 965 ConstantFoldCompareInstOperands(Predicate, CE0->getOperand(0), Ops1,TD); 966 Constant *RHS = 967 ConstantFoldCompareInstOperands(Predicate, CE0->getOperand(1), Ops1,TD); 968 unsigned OpC = 969 Predicate == ICmpInst::ICMP_EQ ? Instruction::And : Instruction::Or; 970 Constant *Ops[] = { LHS, RHS }; 971 return ConstantFoldInstOperands(OpC, LHS->getType(), Ops, 2, TD); 972 } 973 } 974 975 return ConstantExpr::getCompare(Predicate, Ops0, Ops1); 976} 977 978 979/// ConstantFoldLoadThroughGEPConstantExpr - Given a constant and a 980/// getelementptr constantexpr, return the constant value being addressed by the 981/// constant expression, or null if something is funny and we can't decide. 982Constant *llvm::ConstantFoldLoadThroughGEPConstantExpr(Constant *C, 983 ConstantExpr *CE) { 984 if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType())) 985 return 0; // Do not allow stepping over the value! 986 987 // Loop over all of the operands, tracking down which value we are 988 // addressing... 989 gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE); 990 for (++I; I != E; ++I) 991 if (const StructType *STy = dyn_cast<StructType>(*I)) { 992 ConstantInt *CU = cast<ConstantInt>(I.getOperand()); 993 assert(CU->getZExtValue() < STy->getNumElements() && 994 "Struct index out of range!"); 995 unsigned El = (unsigned)CU->getZExtValue(); 996 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) { 997 C = CS->getOperand(El); 998 } else if (isa<ConstantAggregateZero>(C)) { 999 C = Constant::getNullValue(STy->getElementType(El)); 1000 } else if (isa<UndefValue>(C)) { 1001 C = UndefValue::get(STy->getElementType(El)); 1002 } else { 1003 return 0; 1004 } 1005 } else if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) { 1006 if (const ArrayType *ATy = dyn_cast<ArrayType>(*I)) { 1007 if (CI->getZExtValue() >= ATy->getNumElements()) 1008 return 0; 1009 if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) 1010 C = CA->getOperand(CI->getZExtValue()); 1011 else if (isa<ConstantAggregateZero>(C)) 1012 C = Constant::getNullValue(ATy->getElementType()); 1013 else if (isa<UndefValue>(C)) 1014 C = UndefValue::get(ATy->getElementType()); 1015 else 1016 return 0; 1017 } else if (const VectorType *VTy = dyn_cast<VectorType>(*I)) { 1018 if (CI->getZExtValue() >= VTy->getNumElements()) 1019 return 0; 1020 if (ConstantVector *CP = dyn_cast<ConstantVector>(C)) 1021 C = CP->getOperand(CI->getZExtValue()); 1022 else if (isa<ConstantAggregateZero>(C)) 1023 C = Constant::getNullValue(VTy->getElementType()); 1024 else if (isa<UndefValue>(C)) 1025 C = UndefValue::get(VTy->getElementType()); 1026 else 1027 return 0; 1028 } else { 1029 return 0; 1030 } 1031 } else { 1032 return 0; 1033 } 1034 return C; 1035} 1036 1037 1038//===----------------------------------------------------------------------===// 1039// Constant Folding for Calls 1040// 1041 1042/// canConstantFoldCallTo - Return true if its even possible to fold a call to 1043/// the specified function. 1044bool 1045llvm::canConstantFoldCallTo(const Function *F) { 1046 switch (F->getIntrinsicID()) { 1047 case Intrinsic::sqrt: 1048 case Intrinsic::powi: 1049 case Intrinsic::bswap: 1050 case Intrinsic::ctpop: 1051 case Intrinsic::ctlz: 1052 case Intrinsic::cttz: 1053 case Intrinsic::sadd_with_overflow: 1054 case Intrinsic::uadd_with_overflow: 1055 case Intrinsic::ssub_with_overflow: 1056 case Intrinsic::usub_with_overflow: 1057 case Intrinsic::smul_with_overflow: 1058 case Intrinsic::umul_with_overflow: 1059 case Intrinsic::convert_from_fp16: 1060 case Intrinsic::convert_to_fp16: 1061 case Intrinsic::x86_sse_cvtss2si: 1062 case Intrinsic::x86_sse_cvtss2si64: 1063 case Intrinsic::x86_sse_cvttss2si: 1064 case Intrinsic::x86_sse_cvttss2si64: 1065 case Intrinsic::x86_sse2_cvtsd2si: 1066 case Intrinsic::x86_sse2_cvtsd2si64: 1067 case Intrinsic::x86_sse2_cvttsd2si: 1068 case Intrinsic::x86_sse2_cvttsd2si64: 1069 return true; 1070 default: 1071 return false; 1072 case 0: break; 1073 } 1074 1075 if (!F->hasName()) return false; 1076 StringRef Name = F->getName(); 1077 1078 // In these cases, the check of the length is required. We don't want to 1079 // return true for a name like "cos\0blah" which strcmp would return equal to 1080 // "cos", but has length 8. 1081 switch (Name[0]) { 1082 default: return false; 1083 case 'a': 1084 return Name == "acos" || Name == "asin" || 1085 Name == "atan" || Name == "atan2"; 1086 case 'c': 1087 return Name == "cos" || Name == "ceil" || Name == "cosf" || Name == "cosh"; 1088 case 'e': 1089 return Name == "exp" || Name == "exp2"; 1090 case 'f': 1091 return Name == "fabs" || Name == "fmod" || Name == "floor"; 1092 case 'l': 1093 return Name == "log" || Name == "log10"; 1094 case 'p': 1095 return Name == "pow"; 1096 case 's': 1097 return Name == "sin" || Name == "sinh" || Name == "sqrt" || 1098 Name == "sinf" || Name == "sqrtf"; 1099 case 't': 1100 return Name == "tan" || Name == "tanh"; 1101 } 1102} 1103 1104static Constant *ConstantFoldFP(double (*NativeFP)(double), double V, 1105 const Type *Ty) { 1106 sys::llvm_fenv_clearexcept(); 1107 V = NativeFP(V); 1108 if (sys::llvm_fenv_testexcept()) { 1109 sys::llvm_fenv_clearexcept(); 1110 return 0; 1111 } 1112 1113 if (Ty->isFloatTy()) 1114 return ConstantFP::get(Ty->getContext(), APFloat((float)V)); 1115 if (Ty->isDoubleTy()) 1116 return ConstantFP::get(Ty->getContext(), APFloat(V)); 1117 llvm_unreachable("Can only constant fold float/double"); 1118 return 0; // dummy return to suppress warning 1119} 1120 1121static Constant *ConstantFoldBinaryFP(double (*NativeFP)(double, double), 1122 double V, double W, const Type *Ty) { 1123 sys::llvm_fenv_clearexcept(); 1124 V = NativeFP(V, W); 1125 if (sys::llvm_fenv_testexcept()) { 1126 sys::llvm_fenv_clearexcept(); 1127 return 0; 1128 } 1129 1130 if (Ty->isFloatTy()) 1131 return ConstantFP::get(Ty->getContext(), APFloat((float)V)); 1132 if (Ty->isDoubleTy()) 1133 return ConstantFP::get(Ty->getContext(), APFloat(V)); 1134 llvm_unreachable("Can only constant fold float/double"); 1135 return 0; // dummy return to suppress warning 1136} 1137 1138/// ConstantFoldConvertToInt - Attempt to an SSE floating point to integer 1139/// conversion of a constant floating point. If roundTowardZero is false, the 1140/// default IEEE rounding is used (toward nearest, ties to even). This matches 1141/// the behavior of the non-truncating SSE instructions in the default rounding 1142/// mode. The desired integer type Ty is used to select how many bits are 1143/// available for the result. Returns null if the conversion cannot be 1144/// performed, otherwise returns the Constant value resulting from the 1145/// conversion. 1146static Constant *ConstantFoldConvertToInt(ConstantFP *Op, bool roundTowardZero, 1147 const Type *Ty) { 1148 assert(Op && "Called with NULL operand"); 1149 APFloat Val(Op->getValueAPF()); 1150 1151 // All of these conversion intrinsics form an integer of at most 64bits. 1152 unsigned ResultWidth = cast<IntegerType>(Ty)->getBitWidth(); 1153 assert(ResultWidth <= 64 && 1154 "Can only constant fold conversions to 64 and 32 bit ints"); 1155 1156 uint64_t UIntVal; 1157 bool isExact = false; 1158 APFloat::roundingMode mode = roundTowardZero? APFloat::rmTowardZero 1159 : APFloat::rmNearestTiesToEven; 1160 APFloat::opStatus status = Val.convertToInteger(&UIntVal, ResultWidth, 1161 /*isSigned=*/true, mode, 1162 &isExact); 1163 if (status != APFloat::opOK && status != APFloat::opInexact) 1164 return 0; 1165 return ConstantInt::get(Ty, UIntVal, /*isSigned=*/true); 1166} 1167 1168/// ConstantFoldCall - Attempt to constant fold a call to the specified function 1169/// with the specified arguments, returning null if unsuccessful. 1170Constant * 1171llvm::ConstantFoldCall(Function *F, 1172 Constant *const *Operands, unsigned NumOperands) { 1173 if (!F->hasName()) return 0; 1174 StringRef Name = F->getName(); 1175 1176 const Type *Ty = F->getReturnType(); 1177 if (NumOperands == 1) { 1178 if (ConstantFP *Op = dyn_cast<ConstantFP>(Operands[0])) { 1179 if (F->getIntrinsicID() == Intrinsic::convert_to_fp16) { 1180 APFloat Val(Op->getValueAPF()); 1181 1182 bool lost = false; 1183 Val.convert(APFloat::IEEEhalf, APFloat::rmNearestTiesToEven, &lost); 1184 1185 return ConstantInt::get(F->getContext(), Val.bitcastToAPInt()); 1186 } 1187 1188 if (!Ty->isFloatTy() && !Ty->isDoubleTy()) 1189 return 0; 1190 1191 /// We only fold functions with finite arguments. Folding NaN and inf is 1192 /// likely to be aborted with an exception anyway, and some host libms 1193 /// have known errors raising exceptions. 1194 if (Op->getValueAPF().isNaN() || Op->getValueAPF().isInfinity()) 1195 return 0; 1196 1197 /// Currently APFloat versions of these functions do not exist, so we use 1198 /// the host native double versions. Float versions are not called 1199 /// directly but for all these it is true (float)(f((double)arg)) == 1200 /// f(arg). Long double not supported yet. 1201 double V = Ty->isFloatTy() ? (double)Op->getValueAPF().convertToFloat() : 1202 Op->getValueAPF().convertToDouble(); 1203 switch (Name[0]) { 1204 case 'a': 1205 if (Name == "acos") 1206 return ConstantFoldFP(acos, V, Ty); 1207 else if (Name == "asin") 1208 return ConstantFoldFP(asin, V, Ty); 1209 else if (Name == "atan") 1210 return ConstantFoldFP(atan, V, Ty); 1211 break; 1212 case 'c': 1213 if (Name == "ceil") 1214 return ConstantFoldFP(ceil, V, Ty); 1215 else if (Name == "cos") 1216 return ConstantFoldFP(cos, V, Ty); 1217 else if (Name == "cosh") 1218 return ConstantFoldFP(cosh, V, Ty); 1219 else if (Name == "cosf") 1220 return ConstantFoldFP(cos, V, Ty); 1221 break; 1222 case 'e': 1223 if (Name == "exp") 1224 return ConstantFoldFP(exp, V, Ty); 1225 1226 if (Name == "exp2") { 1227 // Constant fold exp2(x) as pow(2,x) in case the host doesn't have a 1228 // C99 library. 1229 return ConstantFoldBinaryFP(pow, 2.0, V, Ty); 1230 } 1231 break; 1232 case 'f': 1233 if (Name == "fabs") 1234 return ConstantFoldFP(fabs, V, Ty); 1235 else if (Name == "floor") 1236 return ConstantFoldFP(floor, V, Ty); 1237 break; 1238 case 'l': 1239 if (Name == "log" && V > 0) 1240 return ConstantFoldFP(log, V, Ty); 1241 else if (Name == "log10" && V > 0) 1242 return ConstantFoldFP(log10, V, Ty); 1243 else if (F->getIntrinsicID() == Intrinsic::sqrt && 1244 (Ty->isFloatTy() || Ty->isDoubleTy())) { 1245 if (V >= -0.0) 1246 return ConstantFoldFP(sqrt, V, Ty); 1247 else // Undefined 1248 return Constant::getNullValue(Ty); 1249 } 1250 break; 1251 case 's': 1252 if (Name == "sin") 1253 return ConstantFoldFP(sin, V, Ty); 1254 else if (Name == "sinh") 1255 return ConstantFoldFP(sinh, V, Ty); 1256 else if (Name == "sqrt" && V >= 0) 1257 return ConstantFoldFP(sqrt, V, Ty); 1258 else if (Name == "sqrtf" && V >= 0) 1259 return ConstantFoldFP(sqrt, V, Ty); 1260 else if (Name == "sinf") 1261 return ConstantFoldFP(sin, V, Ty); 1262 break; 1263 case 't': 1264 if (Name == "tan") 1265 return ConstantFoldFP(tan, V, Ty); 1266 else if (Name == "tanh") 1267 return ConstantFoldFP(tanh, V, Ty); 1268 break; 1269 default: 1270 break; 1271 } 1272 return 0; 1273 } 1274 1275 if (ConstantInt *Op = dyn_cast<ConstantInt>(Operands[0])) { 1276 switch (F->getIntrinsicID()) { 1277 case Intrinsic::bswap: 1278 return ConstantInt::get(F->getContext(), Op->getValue().byteSwap()); 1279 case Intrinsic::ctpop: 1280 return ConstantInt::get(Ty, Op->getValue().countPopulation()); 1281 case Intrinsic::cttz: 1282 return ConstantInt::get(Ty, Op->getValue().countTrailingZeros()); 1283 case Intrinsic::ctlz: 1284 return ConstantInt::get(Ty, Op->getValue().countLeadingZeros()); 1285 case Intrinsic::convert_from_fp16: { 1286 APFloat Val(Op->getValue()); 1287 1288 bool lost = false; 1289 APFloat::opStatus status = 1290 Val.convert(APFloat::IEEEsingle, APFloat::rmNearestTiesToEven, &lost); 1291 1292 // Conversion is always precise. 1293 (void)status; 1294 assert(status == APFloat::opOK && !lost && 1295 "Precision lost during fp16 constfolding"); 1296 1297 return ConstantFP::get(F->getContext(), Val); 1298 } 1299 default: 1300 return 0; 1301 } 1302 } 1303 1304 if (ConstantVector *Op = dyn_cast<ConstantVector>(Operands[0])) { 1305 switch (F->getIntrinsicID()) { 1306 default: break; 1307 case Intrinsic::x86_sse_cvtss2si: 1308 case Intrinsic::x86_sse_cvtss2si64: 1309 case Intrinsic::x86_sse2_cvtsd2si: 1310 case Intrinsic::x86_sse2_cvtsd2si64: 1311 if (ConstantFP *FPOp = dyn_cast<ConstantFP>(Op->getOperand(0))) 1312 return ConstantFoldConvertToInt(FPOp, /*roundTowardZero=*/false, Ty); 1313 case Intrinsic::x86_sse_cvttss2si: 1314 case Intrinsic::x86_sse_cvttss2si64: 1315 case Intrinsic::x86_sse2_cvttsd2si: 1316 case Intrinsic::x86_sse2_cvttsd2si64: 1317 if (ConstantFP *FPOp = dyn_cast<ConstantFP>(Op->getOperand(0))) 1318 return ConstantFoldConvertToInt(FPOp, /*roundTowardZero=*/true, Ty); 1319 } 1320 } 1321 1322 if (isa<UndefValue>(Operands[0])) { 1323 if (F->getIntrinsicID() == Intrinsic::bswap) 1324 return Operands[0]; 1325 return 0; 1326 } 1327 1328 return 0; 1329 } 1330 1331 if (NumOperands == 2) { 1332 if (ConstantFP *Op1 = dyn_cast<ConstantFP>(Operands[0])) { 1333 if (!Ty->isFloatTy() && !Ty->isDoubleTy()) 1334 return 0; 1335 double Op1V = Ty->isFloatTy() ? 1336 (double)Op1->getValueAPF().convertToFloat() : 1337 Op1->getValueAPF().convertToDouble(); 1338 if (ConstantFP *Op2 = dyn_cast<ConstantFP>(Operands[1])) { 1339 if (Op2->getType() != Op1->getType()) 1340 return 0; 1341 1342 double Op2V = Ty->isFloatTy() ? 1343 (double)Op2->getValueAPF().convertToFloat(): 1344 Op2->getValueAPF().convertToDouble(); 1345 1346 if (Name == "pow") 1347 return ConstantFoldBinaryFP(pow, Op1V, Op2V, Ty); 1348 if (Name == "fmod") 1349 return ConstantFoldBinaryFP(fmod, Op1V, Op2V, Ty); 1350 if (Name == "atan2") 1351 return ConstantFoldBinaryFP(atan2, Op1V, Op2V, Ty); 1352 } else if (ConstantInt *Op2C = dyn_cast<ConstantInt>(Operands[1])) { 1353 if (F->getIntrinsicID() == Intrinsic::powi && Ty->isFloatTy()) 1354 return ConstantFP::get(F->getContext(), 1355 APFloat((float)std::pow((float)Op1V, 1356 (int)Op2C->getZExtValue()))); 1357 if (F->getIntrinsicID() == Intrinsic::powi && Ty->isDoubleTy()) 1358 return ConstantFP::get(F->getContext(), 1359 APFloat((double)std::pow((double)Op1V, 1360 (int)Op2C->getZExtValue()))); 1361 } 1362 return 0; 1363 } 1364 1365 1366 if (ConstantInt *Op1 = dyn_cast<ConstantInt>(Operands[0])) { 1367 if (ConstantInt *Op2 = dyn_cast<ConstantInt>(Operands[1])) { 1368 switch (F->getIntrinsicID()) { 1369 default: break; 1370 case Intrinsic::sadd_with_overflow: 1371 case Intrinsic::uadd_with_overflow: 1372 case Intrinsic::ssub_with_overflow: 1373 case Intrinsic::usub_with_overflow: 1374 case Intrinsic::smul_with_overflow: 1375 case Intrinsic::umul_with_overflow: { 1376 APInt Res; 1377 bool Overflow; 1378 switch (F->getIntrinsicID()) { 1379 default: assert(0 && "Invalid case"); 1380 case Intrinsic::sadd_with_overflow: 1381 Res = Op1->getValue().sadd_ov(Op2->getValue(), Overflow); 1382 break; 1383 case Intrinsic::uadd_with_overflow: 1384 Res = Op1->getValue().uadd_ov(Op2->getValue(), Overflow); 1385 break; 1386 case Intrinsic::ssub_with_overflow: 1387 Res = Op1->getValue().ssub_ov(Op2->getValue(), Overflow); 1388 break; 1389 case Intrinsic::usub_with_overflow: 1390 Res = Op1->getValue().usub_ov(Op2->getValue(), Overflow); 1391 break; 1392 case Intrinsic::smul_with_overflow: 1393 Res = Op1->getValue().smul_ov(Op2->getValue(), Overflow); 1394 break; 1395 case Intrinsic::umul_with_overflow: 1396 Res = Op1->getValue().umul_ov(Op2->getValue(), Overflow); 1397 break; 1398 } 1399 Constant *Ops[] = { 1400 ConstantInt::get(F->getContext(), Res), 1401 ConstantInt::get(Type::getInt1Ty(F->getContext()), Overflow) 1402 }; 1403 return ConstantStruct::get(cast<StructType>(F->getReturnType()), Ops); 1404 } 1405 } 1406 } 1407 1408 return 0; 1409 } 1410 return 0; 1411 } 1412 return 0; 1413} 1414