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