ConstantFolding.cpp revision 317096ab3710fda0960be58804e9f80c800340f6
1//===-- ConstantFolding.cpp - Analyze constant folding possibilities ------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source 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/Instructions.h" 20#include "llvm/Intrinsics.h" 21#include "llvm/ADT/SmallVector.h" 22#include "llvm/ADT/StringMap.h" 23#include "llvm/Target/TargetData.h" 24#include "llvm/Support/GetElementPtrTypeIterator.h" 25#include "llvm/Support/MathExtras.h" 26#include <cerrno> 27#include <cmath> 28using namespace llvm; 29 30//===----------------------------------------------------------------------===// 31// Constant Folding internal helper functions 32//===----------------------------------------------------------------------===// 33 34/// IsConstantOffsetFromGlobal - If this constant is actually a constant offset 35/// from a global, return the global and the constant. Because of 36/// constantexprs, this function is recursive. 37static bool IsConstantOffsetFromGlobal(Constant *C, GlobalValue *&GV, 38 int64_t &Offset, const TargetData &TD) { 39 // Trivial case, constant is the global. 40 if ((GV = dyn_cast<GlobalValue>(C))) { 41 Offset = 0; 42 return true; 43 } 44 45 // Otherwise, if this isn't a constant expr, bail out. 46 ConstantExpr *CE = dyn_cast<ConstantExpr>(C); 47 if (!CE) return false; 48 49 // Look through ptr->int and ptr->ptr casts. 50 if (CE->getOpcode() == Instruction::PtrToInt || 51 CE->getOpcode() == Instruction::BitCast) 52 return IsConstantOffsetFromGlobal(CE->getOperand(0), GV, Offset, TD); 53 54 // i32* getelementptr ([5 x i32]* @a, i32 0, i32 5) 55 if (CE->getOpcode() == Instruction::GetElementPtr) { 56 // Cannot compute this if the element type of the pointer is missing size 57 // info. 58 if (!cast<PointerType>(CE->getOperand(0)->getType())->getElementType()->isSized()) 59 return false; 60 61 // If the base isn't a global+constant, we aren't either. 62 if (!IsConstantOffsetFromGlobal(CE->getOperand(0), GV, Offset, TD)) 63 return false; 64 65 // Otherwise, add any offset that our operands provide. 66 gep_type_iterator GTI = gep_type_begin(CE); 67 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i, ++GTI) { 68 ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(i)); 69 if (!CI) return false; // Index isn't a simple constant? 70 if (CI->getZExtValue() == 0) continue; // Not adding anything. 71 72 if (const StructType *ST = dyn_cast<StructType>(*GTI)) { 73 // N = N + Offset 74 Offset += TD.getStructLayout(ST)->getElementOffset(CI->getZExtValue()); 75 } else { 76 const SequentialType *SQT = cast<SequentialType>(*GTI); 77 Offset += TD.getTypeSize(SQT->getElementType())*CI->getSExtValue(); 78 } 79 } 80 return true; 81 } 82 83 return false; 84} 85 86 87/// SymbolicallyEvaluateBinop - One of Op0/Op1 is a constant expression. 88/// Attempt to symbolically evaluate the result of a binary operator merging 89/// these together. If target data info is available, it is provided as TD, 90/// otherwise TD is null. 91static Constant *SymbolicallyEvaluateBinop(unsigned Opc, Constant *Op0, 92 Constant *Op1, const TargetData *TD){ 93 // SROA 94 95 // Fold (and 0xffffffff00000000, (shl x, 32)) -> shl. 96 // Fold (lshr (or X, Y), 32) -> (lshr [X/Y], 32) if one doesn't contribute 97 // bits. 98 99 100 // If the constant expr is something like &A[123] - &A[4].f, fold this into a 101 // constant. This happens frequently when iterating over a global array. 102 if (Opc == Instruction::Sub && TD) { 103 GlobalValue *GV1, *GV2; 104 int64_t Offs1, Offs2; 105 106 if (IsConstantOffsetFromGlobal(Op0, GV1, Offs1, *TD)) 107 if (IsConstantOffsetFromGlobal(Op1, GV2, Offs2, *TD) && 108 GV1 == GV2) { 109 // (&GV+C1) - (&GV+C2) -> C1-C2, pointer arithmetic cannot overflow. 110 return ConstantInt::get(Op0->getType(), Offs1-Offs2); 111 } 112 } 113 114 // TODO: Fold icmp setne/seteq as well. 115 return 0; 116} 117 118/// SymbolicallyEvaluateGEP - If we can symbolically evaluate the specified GEP 119/// constant expression, do so. 120static Constant *SymbolicallyEvaluateGEP(Constant** Ops, unsigned NumOps, 121 const Type *ResultTy, 122 const TargetData *TD) { 123 Constant *Ptr = Ops[0]; 124 if (!cast<PointerType>(Ptr->getType())->getElementType()->isSized()) 125 return 0; 126 127 if (TD && Ptr->isNullValue()) { 128 // If this is a constant expr gep that is effectively computing an 129 // "offsetof", fold it into 'cast int Size to T*' instead of 'gep 0, 0, 12' 130 bool isFoldableGEP = true; 131 for (unsigned i = 1; i != NumOps; ++i) 132 if (!isa<ConstantInt>(Ops[i])) { 133 isFoldableGEP = false; 134 break; 135 } 136 if (isFoldableGEP) { 137 uint64_t Offset = TD->getIndexedOffset(Ptr->getType(), 138 (Value**)Ops+1, NumOps-1); 139 Constant *C = ConstantInt::get(TD->getIntPtrType(), Offset); 140 return ConstantExpr::getIntToPtr(C, ResultTy); 141 } 142 } 143 144 return 0; 145} 146 147 148//===----------------------------------------------------------------------===// 149// Constant Folding public APIs 150//===----------------------------------------------------------------------===// 151 152 153/// ConstantFoldInstruction - Attempt to constant fold the specified 154/// instruction. If successful, the constant result is returned, if not, null 155/// is returned. Note that this function can only fail when attempting to fold 156/// instructions like loads and stores, which have no constant expression form. 157/// 158Constant *llvm::ConstantFoldInstruction(Instruction *I, const TargetData *TD) { 159 if (PHINode *PN = dyn_cast<PHINode>(I)) { 160 if (PN->getNumIncomingValues() == 0) 161 return Constant::getNullValue(PN->getType()); 162 163 Constant *Result = dyn_cast<Constant>(PN->getIncomingValue(0)); 164 if (Result == 0) return 0; 165 166 // Handle PHI nodes specially here... 167 for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) 168 if (PN->getIncomingValue(i) != Result && PN->getIncomingValue(i) != PN) 169 return 0; // Not all the same incoming constants... 170 171 // If we reach here, all incoming values are the same constant. 172 return Result; 173 } 174 175 // Scan the operand list, checking to see if they are all constants, if so, 176 // hand off to ConstantFoldInstOperands. 177 SmallVector<Constant*, 8> Ops; 178 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 179 if (Constant *Op = dyn_cast<Constant>(I->getOperand(i))) 180 Ops.push_back(Op); 181 else 182 return 0; // All operands not constant! 183 184 return ConstantFoldInstOperands(I, &Ops[0], Ops.size(), TD); 185} 186 187/// ConstantFoldInstOperands - Attempt to constant fold an instruction with the 188/// specified opcode and operands. If successful, the constant result is 189/// returned, if not, null is returned. Note that this function can fail when 190/// attempting to fold instructions like loads and stores, which have no 191/// constant expression form. 192/// 193Constant *llvm::ConstantFoldInstOperands(const Instruction* I, 194 Constant** Ops, unsigned NumOps, 195 const TargetData *TD) { 196 unsigned Opc = I->getOpcode(); 197 const Type *DestTy = I->getType(); 198 199 // Handle easy binops first. 200 if (isa<BinaryOperator>(I)) { 201 if (isa<ConstantExpr>(Ops[0]) || isa<ConstantExpr>(Ops[1])) 202 if (Constant *C = SymbolicallyEvaluateBinop(I->getOpcode(), Ops[0], 203 Ops[1], TD)) 204 return C; 205 206 return ConstantExpr::get(Opc, Ops[0], Ops[1]); 207 } 208 209 switch (Opc) { 210 default: return 0; 211 case Instruction::Call: 212 if (Function *F = dyn_cast<Function>(Ops[0])) 213 if (canConstantFoldCallTo(F)) 214 return ConstantFoldCall(F, Ops+1, NumOps-1); 215 return 0; 216 case Instruction::ICmp: 217 case Instruction::FCmp: 218 return ConstantExpr::getCompare(cast<CmpInst>(I)->getPredicate(), Ops[0], 219 Ops[1]); 220 case Instruction::PtrToInt: 221 // If the input is a inttoptr, eliminate the pair. This requires knowing 222 // the width of a pointer, so it can't be done in ConstantExpr::getCast. 223 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ops[0])) { 224 if (TD && CE->getOpcode() == Instruction::IntToPtr) { 225 Constant *Input = CE->getOperand(0); 226 unsigned InWidth = Input->getType()->getPrimitiveSizeInBits(); 227 Constant *Mask = 228 ConstantInt::get(APInt::getLowBitsSet(InWidth, 229 TD->getPointerSizeInBits())); 230 Input = ConstantExpr::getAnd(Input, Mask); 231 // Do a zext or trunc to get to the dest size. 232 return ConstantExpr::getIntegerCast(Input, I->getType(), false); 233 } 234 } 235 // FALL THROUGH. 236 case Instruction::IntToPtr: 237 case Instruction::Trunc: 238 case Instruction::ZExt: 239 case Instruction::SExt: 240 case Instruction::FPTrunc: 241 case Instruction::FPExt: 242 case Instruction::UIToFP: 243 case Instruction::SIToFP: 244 case Instruction::FPToUI: 245 case Instruction::FPToSI: 246 case Instruction::BitCast: 247 return ConstantExpr::getCast(Opc, Ops[0], DestTy); 248 case Instruction::Select: 249 return ConstantExpr::getSelect(Ops[0], Ops[1], Ops[2]); 250 case Instruction::ExtractElement: 251 return ConstantExpr::getExtractElement(Ops[0], Ops[1]); 252 case Instruction::InsertElement: 253 return ConstantExpr::getInsertElement(Ops[0], Ops[1], Ops[2]); 254 case Instruction::ShuffleVector: 255 return ConstantExpr::getShuffleVector(Ops[0], Ops[1], Ops[2]); 256 case Instruction::GetElementPtr: 257 if (Constant *C = SymbolicallyEvaluateGEP(Ops, NumOps, I->getType(), TD)) 258 return C; 259 260 return ConstantExpr::getGetElementPtr(Ops[0], Ops+1, NumOps-1); 261 } 262} 263 264/// ConstantFoldLoadThroughGEPConstantExpr - Given a constant and a 265/// getelementptr constantexpr, return the constant value being addressed by the 266/// constant expression, or null if something is funny and we can't decide. 267Constant *llvm::ConstantFoldLoadThroughGEPConstantExpr(Constant *C, 268 ConstantExpr *CE) { 269 if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType())) 270 return 0; // Do not allow stepping over the value! 271 272 // Loop over all of the operands, tracking down which value we are 273 // addressing... 274 gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE); 275 for (++I; I != E; ++I) 276 if (const StructType *STy = dyn_cast<StructType>(*I)) { 277 ConstantInt *CU = cast<ConstantInt>(I.getOperand()); 278 assert(CU->getZExtValue() < STy->getNumElements() && 279 "Struct index out of range!"); 280 unsigned El = (unsigned)CU->getZExtValue(); 281 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) { 282 C = CS->getOperand(El); 283 } else if (isa<ConstantAggregateZero>(C)) { 284 C = Constant::getNullValue(STy->getElementType(El)); 285 } else if (isa<UndefValue>(C)) { 286 C = UndefValue::get(STy->getElementType(El)); 287 } else { 288 return 0; 289 } 290 } else if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) { 291 if (const ArrayType *ATy = dyn_cast<ArrayType>(*I)) { 292 if (CI->getZExtValue() >= ATy->getNumElements()) 293 return 0; 294 if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) 295 C = CA->getOperand(CI->getZExtValue()); 296 else if (isa<ConstantAggregateZero>(C)) 297 C = Constant::getNullValue(ATy->getElementType()); 298 else if (isa<UndefValue>(C)) 299 C = UndefValue::get(ATy->getElementType()); 300 else 301 return 0; 302 } else if (const VectorType *PTy = dyn_cast<VectorType>(*I)) { 303 if (CI->getZExtValue() >= PTy->getNumElements()) 304 return 0; 305 if (ConstantVector *CP = dyn_cast<ConstantVector>(C)) 306 C = CP->getOperand(CI->getZExtValue()); 307 else if (isa<ConstantAggregateZero>(C)) 308 C = Constant::getNullValue(PTy->getElementType()); 309 else if (isa<UndefValue>(C)) 310 C = UndefValue::get(PTy->getElementType()); 311 else 312 return 0; 313 } else { 314 return 0; 315 } 316 } else { 317 return 0; 318 } 319 return C; 320} 321 322 323//===----------------------------------------------------------------------===// 324// Constant Folding for Calls 325// 326 327/// canConstantFoldCallTo - Return true if its even possible to fold a call to 328/// the specified function. 329bool 330llvm::canConstantFoldCallTo(Function *F) { 331 switch (F->getIntrinsicID()) { 332 case Intrinsic::sqrt_f32: 333 case Intrinsic::sqrt_f64: 334 case Intrinsic::sqrt_f80: 335 case Intrinsic::sqrt_f128: 336 case Intrinsic::sqrt_ppcf128: 337 case Intrinsic::powi_f32: 338 case Intrinsic::powi_f64: 339 case Intrinsic::powi_f80: 340 case Intrinsic::powi_f128: 341 case Intrinsic::powi_ppcf128: 342 case Intrinsic::bswap: 343 case Intrinsic::ctpop: 344 case Intrinsic::ctlz: 345 case Intrinsic::cttz: 346 return true; 347 default: break; 348 } 349 350 const ValueName *NameVal = F->getValueName(); 351 if (NameVal == 0) return false; 352 const char *Str = NameVal->getKeyData(); 353 unsigned Len = NameVal->getKeyLength(); 354 355 // In these cases, the check of the length is required. We don't want to 356 // return true for a name like "cos\0blah" which strcmp would return equal to 357 // "cos", but has length 8. 358 switch (Str[0]) { 359 default: return false; 360 case 'a': 361 if (Len == 4) 362 return !strcmp(Str, "acos") || !strcmp(Str, "asin") || 363 !strcmp(Str, "atan"); 364 else if (Len == 5) 365 return !strcmp(Str, "atan2"); 366 return false; 367 case 'c': 368 if (Len == 3) 369 return !strcmp(Str, "cos"); 370 else if (Len == 4) 371 return !strcmp(Str, "ceil") || !strcmp(Str, "cosf") || 372 !strcmp(Str, "cosh"); 373 return false; 374 case 'e': 375 if (Len == 3) 376 return !strcmp(Str, "exp"); 377 return false; 378 case 'f': 379 if (Len == 4) 380 return !strcmp(Str, "fabs") || !strcmp(Str, "fmod"); 381 else if (Len == 5) 382 return !strcmp(Str, "floor"); 383 return false; 384 break; 385 case 'l': 386 if (Len == 3 && !strcmp(Str, "log")) 387 return true; 388 if (Len == 5 && !strcmp(Str, "log10")) 389 return true; 390 return false; 391 case 'p': 392 if (Len == 3 && !strcmp(Str, "pow")) 393 return true; 394 return false; 395 case 's': 396 if (Len == 3) 397 return !strcmp(Str, "sin"); 398 if (Len == 4) 399 return !strcmp(Str, "sinh") || !strcmp(Str, "sqrt"); 400 if (Len == 5) 401 return !strcmp(Str, "sqrtf"); 402 return false; 403 case 't': 404 if (Len == 3 && !strcmp(Str, "tan")) 405 return true; 406 else if (Len == 4 && !strcmp(Str, "tanh")) 407 return true; 408 return false; 409 } 410} 411 412static Constant *ConstantFoldFP(double (*NativeFP)(double), double V, 413 const Type *Ty) { 414 errno = 0; 415 V = NativeFP(V); 416 if (errno == 0) { 417 if (Ty==Type::FloatTy) 418 return ConstantFP::get(Ty, APFloat((float)V)); 419 else if (Ty==Type::DoubleTy) 420 return ConstantFP::get(Ty, APFloat(V)); 421 else 422 assert(0); 423 } 424 errno = 0; 425 return 0; 426} 427 428static Constant *ConstantFoldBinaryFP(double (*NativeFP)(double, double), 429 double V, double W, 430 const Type *Ty) { 431 errno = 0; 432 V = NativeFP(V, W); 433 if (errno == 0) { 434 if (Ty==Type::FloatTy) 435 return ConstantFP::get(Ty, APFloat((float)V)); 436 else if (Ty==Type::DoubleTy) 437 return ConstantFP::get(Ty, APFloat(V)); 438 else 439 assert(0); 440 } 441 errno = 0; 442 return 0; 443} 444 445/// ConstantFoldCall - Attempt to constant fold a call to the specified function 446/// with the specified arguments, returning null if unsuccessful. 447 448Constant * 449llvm::ConstantFoldCall(Function *F, Constant** Operands, unsigned NumOperands) { 450 const ValueName *NameVal = F->getValueName(); 451 if (NameVal == 0) return 0; 452 const char *Str = NameVal->getKeyData(); 453 unsigned Len = NameVal->getKeyLength(); 454 455 const Type *Ty = F->getReturnType(); 456 if (NumOperands == 1) { 457 if (ConstantFP *Op = dyn_cast<ConstantFP>(Operands[0])) { 458 if (Ty!=Type::FloatTy && Ty!=Type::DoubleTy) 459 return 0; 460 /// Currently APFloat versions of these functions do not exist, so we use 461 /// the host native double versions. Float versions are not called 462 /// directly but for all these it is true (float)(f((double)arg)) == 463 /// f(arg). Long double not supported yet. 464 double V = Ty==Type::FloatTy ? (double)Op->getValueAPF().convertToFloat(): 465 Op->getValueAPF().convertToDouble(); 466 switch (Str[0]) { 467 case 'a': 468 if (Len == 4 && !strcmp(Str, "acos")) 469 return ConstantFoldFP(acos, V, Ty); 470 else if (Len == 4 && !strcmp(Str, "asin")) 471 return ConstantFoldFP(asin, V, Ty); 472 else if (Len == 4 && !strcmp(Str, "atan")) 473 return ConstantFoldFP(atan, V, Ty); 474 break; 475 case 'c': 476 if (Len == 4 && !strcmp(Str, "ceil")) 477 return ConstantFoldFP(ceil, V, Ty); 478 else if (Len == 3 && !strcmp(Str, "cos")) 479 return ConstantFoldFP(cos, V, Ty); 480 else if (Len == 4 && !strcmp(Str, "cosh")) 481 return ConstantFoldFP(cosh, V, Ty); 482 break; 483 case 'e': 484 if (Len == 3 && !strcmp(Str, "exp")) 485 return ConstantFoldFP(exp, V, Ty); 486 break; 487 case 'f': 488 if (Len == 4 && !strcmp(Str, "fabs")) 489 return ConstantFoldFP(fabs, V, Ty); 490 else if (Len == 5 && !strcmp(Str, "floor")) 491 return ConstantFoldFP(floor, V, Ty); 492 break; 493 case 'l': 494 if (Len == 3 && !strcmp(Str, "log") && V > 0) 495 return ConstantFoldFP(log, V, Ty); 496 else if (Len == 5 && !strcmp(Str, "log10") && V > 0) 497 return ConstantFoldFP(log10, V, Ty); 498 else if (!strcmp(Str, "llvm.sqrt.f32") || 499 !strcmp(Str, "llvm.sqrt.f64")) { 500 if (V >= -0.0) 501 return ConstantFoldFP(sqrt, V, Ty); 502 else // Undefined 503 return ConstantFP::get(Ty, Ty==Type::FloatTy ? APFloat(0.0f) : 504 APFloat(0.0)); 505 } 506 break; 507 case 's': 508 if (Len == 3 && !strcmp(Str, "sin")) 509 return ConstantFoldFP(sin, V, Ty); 510 else if (Len == 4 && !strcmp(Str, "sinh")) 511 return ConstantFoldFP(sinh, V, Ty); 512 else if (Len == 4 && !strcmp(Str, "sqrt") && V >= 0) 513 return ConstantFoldFP(sqrt, V, Ty); 514 else if (Len == 5 && !strcmp(Str, "sqrtf") && V >= 0) 515 return ConstantFoldFP(sqrt, V, Ty); 516 break; 517 case 't': 518 if (Len == 3 && !strcmp(Str, "tan")) 519 return ConstantFoldFP(tan, V, Ty); 520 else if (Len == 4 && !strcmp(Str, "tanh")) 521 return ConstantFoldFP(tanh, V, Ty); 522 break; 523 default: 524 break; 525 } 526 } else if (ConstantInt *Op = dyn_cast<ConstantInt>(Operands[0])) { 527 if (Len > 11 && !memcmp(Str, "llvm.bswap", 10)) { 528 return ConstantInt::get(Op->getValue().byteSwap()); 529 } else if (Len > 11 && !memcmp(Str, "llvm.ctpop", 10)) { 530 uint64_t ctpop = Op->getValue().countPopulation(); 531 return ConstantInt::get(Ty, ctpop); 532 } else if (Len > 10 && !memcmp(Str, "llvm.cttz", 9)) { 533 uint64_t cttz = Op->getValue().countTrailingZeros(); 534 return ConstantInt::get(Ty, cttz); 535 } else if (Len > 10 && !memcmp(Str, "llvm.ctlz", 9)) { 536 uint64_t ctlz = Op->getValue().countLeadingZeros(); 537 return ConstantInt::get(Ty, ctlz); 538 } 539 } 540 } else if (NumOperands == 2) { 541 if (ConstantFP *Op1 = dyn_cast<ConstantFP>(Operands[0])) { 542 double Op1V = Ty==Type::FloatTy ? 543 (double)Op1->getValueAPF().convertToFloat(): 544 Op1->getValueAPF().convertToDouble(); 545 if (ConstantFP *Op2 = dyn_cast<ConstantFP>(Operands[1])) { 546 if (Ty!=Type::FloatTy && Ty!=Type::DoubleTy) 547 return 0; 548 double Op2V = Ty==Type::FloatTy ? 549 (double)Op2->getValueAPF().convertToFloat(): 550 Op2->getValueAPF().convertToDouble(); 551 552 if (Len == 3 && !strcmp(Str, "pow")) { 553 return ConstantFoldBinaryFP(pow, Op1V, Op2V, Ty); 554 } else if (Len == 4 && !strcmp(Str, "fmod")) { 555 return ConstantFoldBinaryFP(fmod, Op1V, Op2V, Ty); 556 } else if (Len == 5 && !strcmp(Str, "atan2")) { 557 return ConstantFoldBinaryFP(atan2, Op1V, Op2V, Ty); 558 } 559 } else if (ConstantInt *Op2C = dyn_cast<ConstantInt>(Operands[1])) { 560 if (!strcmp(Str, "llvm.powi.f32")) { 561 return ConstantFP::get(Ty, APFloat((float)std::pow((float)Op1V, 562 (int)Op2C->getZExtValue()))); 563 } else if (!strcmp(Str, "llvm.powi.f64")) { 564 return ConstantFP::get(Ty, APFloat((double)std::pow((double)Op1V, 565 (int)Op2C->getZExtValue()))); 566 } 567 } 568 } 569 } 570 return 0; 571} 572 573