ConstantFolding.cpp revision 514ab348fddcdffa8367685dc608b2f8d5de986d
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.getABITypeSize(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: 333 case Intrinsic::powi: 334 case Intrinsic::bswap: 335 case Intrinsic::ctpop: 336 case Intrinsic::ctlz: 337 case Intrinsic::cttz: 338 return true; 339 default: break; 340 } 341 342 const ValueName *NameVal = F->getValueName(); 343 if (NameVal == 0) return false; 344 const char *Str = NameVal->getKeyData(); 345 unsigned Len = NameVal->getKeyLength(); 346 347 // In these cases, the check of the length is required. We don't want to 348 // return true for a name like "cos\0blah" which strcmp would return equal to 349 // "cos", but has length 8. 350 switch (Str[0]) { 351 default: return false; 352 case 'a': 353 if (Len == 4) 354 return !strcmp(Str, "acos") || !strcmp(Str, "asin") || 355 !strcmp(Str, "atan"); 356 else if (Len == 5) 357 return !strcmp(Str, "atan2"); 358 return false; 359 case 'c': 360 if (Len == 3) 361 return !strcmp(Str, "cos"); 362 else if (Len == 4) 363 return !strcmp(Str, "ceil") || !strcmp(Str, "cosf") || 364 !strcmp(Str, "cosh"); 365 return false; 366 case 'e': 367 if (Len == 3) 368 return !strcmp(Str, "exp"); 369 return false; 370 case 'f': 371 if (Len == 4) 372 return !strcmp(Str, "fabs") || !strcmp(Str, "fmod"); 373 else if (Len == 5) 374 return !strcmp(Str, "floor"); 375 return false; 376 break; 377 case 'l': 378 if (Len == 3 && !strcmp(Str, "log")) 379 return true; 380 if (Len == 5 && !strcmp(Str, "log10")) 381 return true; 382 return false; 383 case 'p': 384 if (Len == 3 && !strcmp(Str, "pow")) 385 return true; 386 return false; 387 case 's': 388 if (Len == 3) 389 return !strcmp(Str, "sin"); 390 if (Len == 4) 391 return !strcmp(Str, "sinh") || !strcmp(Str, "sqrt"); 392 if (Len == 5) 393 return !strcmp(Str, "sqrtf"); 394 return false; 395 case 't': 396 if (Len == 3 && !strcmp(Str, "tan")) 397 return true; 398 else if (Len == 4 && !strcmp(Str, "tanh")) 399 return true; 400 return false; 401 } 402} 403 404static Constant *ConstantFoldFP(double (*NativeFP)(double), double V, 405 const Type *Ty) { 406 errno = 0; 407 V = NativeFP(V); 408 if (errno == 0) { 409 if (Ty==Type::FloatTy) 410 return ConstantFP::get(Ty, APFloat((float)V)); 411 else if (Ty==Type::DoubleTy) 412 return ConstantFP::get(Ty, APFloat(V)); 413 else 414 assert(0); 415 } 416 errno = 0; 417 return 0; 418} 419 420static Constant *ConstantFoldBinaryFP(double (*NativeFP)(double, double), 421 double V, double W, 422 const Type *Ty) { 423 errno = 0; 424 V = NativeFP(V, W); 425 if (errno == 0) { 426 if (Ty==Type::FloatTy) 427 return ConstantFP::get(Ty, APFloat((float)V)); 428 else if (Ty==Type::DoubleTy) 429 return ConstantFP::get(Ty, APFloat(V)); 430 else 431 assert(0); 432 } 433 errno = 0; 434 return 0; 435} 436 437/// ConstantFoldCall - Attempt to constant fold a call to the specified function 438/// with the specified arguments, returning null if unsuccessful. 439 440Constant * 441llvm::ConstantFoldCall(Function *F, Constant** Operands, unsigned NumOperands) { 442 const ValueName *NameVal = F->getValueName(); 443 if (NameVal == 0) return 0; 444 const char *Str = NameVal->getKeyData(); 445 unsigned Len = NameVal->getKeyLength(); 446 447 const Type *Ty = F->getReturnType(); 448 if (NumOperands == 1) { 449 if (ConstantFP *Op = dyn_cast<ConstantFP>(Operands[0])) { 450 if (Ty!=Type::FloatTy && Ty!=Type::DoubleTy) 451 return 0; 452 /// Currently APFloat versions of these functions do not exist, so we use 453 /// the host native double versions. Float versions are not called 454 /// directly but for all these it is true (float)(f((double)arg)) == 455 /// f(arg). Long double not supported yet. 456 double V = Ty==Type::FloatTy ? (double)Op->getValueAPF().convertToFloat(): 457 Op->getValueAPF().convertToDouble(); 458 switch (Str[0]) { 459 case 'a': 460 if (Len == 4 && !strcmp(Str, "acos")) 461 return ConstantFoldFP(acos, V, Ty); 462 else if (Len == 4 && !strcmp(Str, "asin")) 463 return ConstantFoldFP(asin, V, Ty); 464 else if (Len == 4 && !strcmp(Str, "atan")) 465 return ConstantFoldFP(atan, V, Ty); 466 break; 467 case 'c': 468 if (Len == 4 && !strcmp(Str, "ceil")) 469 return ConstantFoldFP(ceil, V, Ty); 470 else if (Len == 3 && !strcmp(Str, "cos")) 471 return ConstantFoldFP(cos, V, Ty); 472 else if (Len == 4 && !strcmp(Str, "cosh")) 473 return ConstantFoldFP(cosh, V, Ty); 474 break; 475 case 'e': 476 if (Len == 3 && !strcmp(Str, "exp")) 477 return ConstantFoldFP(exp, V, Ty); 478 break; 479 case 'f': 480 if (Len == 4 && !strcmp(Str, "fabs")) 481 return ConstantFoldFP(fabs, V, Ty); 482 else if (Len == 5 && !strcmp(Str, "floor")) 483 return ConstantFoldFP(floor, V, Ty); 484 break; 485 case 'l': 486 if (Len == 3 && !strcmp(Str, "log") && V > 0) 487 return ConstantFoldFP(log, V, Ty); 488 else if (Len == 5 && !strcmp(Str, "log10") && V > 0) 489 return ConstantFoldFP(log10, V, Ty); 490 else if (!strcmp(Str, "llvm.sqrt.f32") || 491 !strcmp(Str, "llvm.sqrt.f64")) { 492 if (V >= -0.0) 493 return ConstantFoldFP(sqrt, V, Ty); 494 else // Undefined 495 return ConstantFP::get(Ty, Ty==Type::FloatTy ? APFloat(0.0f) : 496 APFloat(0.0)); 497 } 498 break; 499 case 's': 500 if (Len == 3 && !strcmp(Str, "sin")) 501 return ConstantFoldFP(sin, V, Ty); 502 else if (Len == 4 && !strcmp(Str, "sinh")) 503 return ConstantFoldFP(sinh, V, Ty); 504 else if (Len == 4 && !strcmp(Str, "sqrt") && V >= 0) 505 return ConstantFoldFP(sqrt, V, Ty); 506 else if (Len == 5 && !strcmp(Str, "sqrtf") && V >= 0) 507 return ConstantFoldFP(sqrt, V, Ty); 508 break; 509 case 't': 510 if (Len == 3 && !strcmp(Str, "tan")) 511 return ConstantFoldFP(tan, V, Ty); 512 else if (Len == 4 && !strcmp(Str, "tanh")) 513 return ConstantFoldFP(tanh, V, Ty); 514 break; 515 default: 516 break; 517 } 518 } else if (ConstantInt *Op = dyn_cast<ConstantInt>(Operands[0])) { 519 if (Len > 11 && !memcmp(Str, "llvm.bswap", 10)) { 520 return ConstantInt::get(Op->getValue().byteSwap()); 521 } else if (Len > 11 && !memcmp(Str, "llvm.ctpop", 10)) { 522 uint64_t ctpop = Op->getValue().countPopulation(); 523 return ConstantInt::get(Ty, ctpop); 524 } else if (Len > 10 && !memcmp(Str, "llvm.cttz", 9)) { 525 uint64_t cttz = Op->getValue().countTrailingZeros(); 526 return ConstantInt::get(Ty, cttz); 527 } else if (Len > 10 && !memcmp(Str, "llvm.ctlz", 9)) { 528 uint64_t ctlz = Op->getValue().countLeadingZeros(); 529 return ConstantInt::get(Ty, ctlz); 530 } 531 } 532 } else if (NumOperands == 2) { 533 if (ConstantFP *Op1 = dyn_cast<ConstantFP>(Operands[0])) { 534 if (Ty!=Type::FloatTy && Ty!=Type::DoubleTy) 535 return 0; 536 double Op1V = Ty==Type::FloatTy ? 537 (double)Op1->getValueAPF().convertToFloat(): 538 Op1->getValueAPF().convertToDouble(); 539 if (ConstantFP *Op2 = dyn_cast<ConstantFP>(Operands[1])) { 540 double Op2V = Ty==Type::FloatTy ? 541 (double)Op2->getValueAPF().convertToFloat(): 542 Op2->getValueAPF().convertToDouble(); 543 544 if (Len == 3 && !strcmp(Str, "pow")) { 545 return ConstantFoldBinaryFP(pow, Op1V, Op2V, Ty); 546 } else if (Len == 4 && !strcmp(Str, "fmod")) { 547 return ConstantFoldBinaryFP(fmod, Op1V, Op2V, Ty); 548 } else if (Len == 5 && !strcmp(Str, "atan2")) { 549 return ConstantFoldBinaryFP(atan2, Op1V, Op2V, Ty); 550 } 551 } else if (ConstantInt *Op2C = dyn_cast<ConstantInt>(Operands[1])) { 552 if (!strcmp(Str, "llvm.powi.f32")) { 553 return ConstantFP::get(Ty, APFloat((float)std::pow((float)Op1V, 554 (int)Op2C->getZExtValue()))); 555 } else if (!strcmp(Str, "llvm.powi.f64")) { 556 return ConstantFP::get(Ty, APFloat((double)std::pow((double)Op1V, 557 (int)Op2C->getZExtValue()))); 558 } 559 } 560 } 561 } 562 return 0; 563} 564 565