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