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