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