ConstantFolding.cpp revision a099b6c7bb574f22bc002e0b3c65c25abccca1d5
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::Trunc: 221 case Instruction::ZExt: 222 case Instruction::SExt: 223 case Instruction::FPTrunc: 224 case Instruction::FPExt: 225 case Instruction::UIToFP: 226 case Instruction::SIToFP: 227 case Instruction::FPToUI: 228 case Instruction::FPToSI: 229 case Instruction::PtrToInt: 230 case Instruction::IntToPtr: 231 case Instruction::BitCast: 232 return ConstantExpr::getCast(Opc, Ops[0], DestTy); 233 case Instruction::Select: 234 return ConstantExpr::getSelect(Ops[0], Ops[1], Ops[2]); 235 case Instruction::ExtractElement: 236 return ConstantExpr::getExtractElement(Ops[0], Ops[1]); 237 case Instruction::InsertElement: 238 return ConstantExpr::getInsertElement(Ops[0], Ops[1], Ops[2]); 239 case Instruction::ShuffleVector: 240 return ConstantExpr::getShuffleVector(Ops[0], Ops[1], Ops[2]); 241 case Instruction::GetElementPtr: 242 if (Constant *C = SymbolicallyEvaluateGEP(Ops, NumOps, I->getType(), TD)) 243 return C; 244 245 return ConstantExpr::getGetElementPtr(Ops[0], Ops+1, NumOps-1); 246 } 247} 248 249/// ConstantFoldLoadThroughGEPConstantExpr - Given a constant and a 250/// getelementptr constantexpr, return the constant value being addressed by the 251/// constant expression, or null if something is funny and we can't decide. 252Constant *llvm::ConstantFoldLoadThroughGEPConstantExpr(Constant *C, 253 ConstantExpr *CE) { 254 if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType())) 255 return 0; // Do not allow stepping over the value! 256 257 // Loop over all of the operands, tracking down which value we are 258 // addressing... 259 gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE); 260 for (++I; I != E; ++I) 261 if (const StructType *STy = dyn_cast<StructType>(*I)) { 262 ConstantInt *CU = cast<ConstantInt>(I.getOperand()); 263 assert(CU->getZExtValue() < STy->getNumElements() && 264 "Struct index out of range!"); 265 unsigned El = (unsigned)CU->getZExtValue(); 266 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) { 267 C = CS->getOperand(El); 268 } else if (isa<ConstantAggregateZero>(C)) { 269 C = Constant::getNullValue(STy->getElementType(El)); 270 } else if (isa<UndefValue>(C)) { 271 C = UndefValue::get(STy->getElementType(El)); 272 } else { 273 return 0; 274 } 275 } else if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) { 276 if (const ArrayType *ATy = dyn_cast<ArrayType>(*I)) { 277 if (CI->getZExtValue() >= ATy->getNumElements()) 278 return 0; 279 if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) 280 C = CA->getOperand(CI->getZExtValue()); 281 else if (isa<ConstantAggregateZero>(C)) 282 C = Constant::getNullValue(ATy->getElementType()); 283 else if (isa<UndefValue>(C)) 284 C = UndefValue::get(ATy->getElementType()); 285 else 286 return 0; 287 } else if (const VectorType *PTy = dyn_cast<VectorType>(*I)) { 288 if (CI->getZExtValue() >= PTy->getNumElements()) 289 return 0; 290 if (ConstantVector *CP = dyn_cast<ConstantVector>(C)) 291 C = CP->getOperand(CI->getZExtValue()); 292 else if (isa<ConstantAggregateZero>(C)) 293 C = Constant::getNullValue(PTy->getElementType()); 294 else if (isa<UndefValue>(C)) 295 C = UndefValue::get(PTy->getElementType()); 296 else 297 return 0; 298 } else { 299 return 0; 300 } 301 } else { 302 return 0; 303 } 304 return C; 305} 306 307 308//===----------------------------------------------------------------------===// 309// Constant Folding for Calls 310// 311 312/// canConstantFoldCallTo - Return true if its even possible to fold a call to 313/// the specified function. 314bool 315llvm::canConstantFoldCallTo(Function *F) { 316 switch (F->getIntrinsicID()) { 317 case Intrinsic::sqrt_f32: 318 case Intrinsic::sqrt_f64: 319 case Intrinsic::powi_f32: 320 case Intrinsic::powi_f64: 321 case Intrinsic::bswap: 322 case Intrinsic::ctpop: 323 case Intrinsic::ctlz: 324 case Intrinsic::cttz: 325 return true; 326 default: break; 327 } 328 329 const ValueName *NameVal = F->getValueName(); 330 if (NameVal == 0) return false; 331 const char *Str = NameVal->getKeyData(); 332 unsigned Len = NameVal->getKeyLength(); 333 334 // In these cases, the check of the length is required. We don't want to 335 // return true for a name like "cos\0blah" which strcmp would return equal to 336 // "cos", but has length 8. 337 switch (Str[0]) { 338 default: return false; 339 case 'a': 340 if (Len == 4) 341 return !strcmp(Str, "acos") || !strcmp(Str, "asin") || 342 !strcmp(Str, "atan"); 343 else if (Len == 5) 344 return !strcmp(Str, "atan2"); 345 return false; 346 case 'c': 347 if (Len == 3) 348 return !strcmp(Str, "cos"); 349 else if (Len == 4) 350 return !strcmp(Str, "ceil") || !strcmp(Str, "cosf") || 351 !strcmp(Str, "cosh"); 352 return false; 353 case 'e': 354 if (Len == 3) 355 return !strcmp(Str, "exp"); 356 return false; 357 case 'f': 358 if (Len == 4) 359 return !strcmp(Str, "fabs") || !strcmp(Str, "fmod"); 360 else if (Len == 5) 361 return !strcmp(Str, "floor"); 362 return false; 363 break; 364 case 'l': 365 if (Len == 3 && !strcmp(Str, "log")) 366 return true; 367 if (Len == 5 && !strcmp(Str, "log10")) 368 return true; 369 return false; 370 case 'p': 371 if (Len == 3 && !strcmp(Str, "pow")) 372 return true; 373 return false; 374 case 's': 375 if (Len == 3) 376 return !strcmp(Str, "sin"); 377 if (Len == 4) 378 return !strcmp(Str, "sinh") || !strcmp(Str, "sqrt"); 379 if (Len == 5) 380 return !strcmp(Str, "sqrtf"); 381 return false; 382 case 't': 383 if (Len == 3 && !strcmp(Str, "tan")) 384 return true; 385 else if (Len == 4 && !strcmp(Str, "tanh")) 386 return true; 387 return false; 388 } 389} 390 391static Constant *ConstantFoldFP(double (*NativeFP)(double), double V, 392 const Type *Ty) { 393 errno = 0; 394 V = NativeFP(V); 395 if (errno == 0) 396 return ConstantFP::get(Ty, V); 397 errno = 0; 398 return 0; 399} 400 401static Constant *ConstantFoldBinaryFP(double (*NativeFP)(double, double), 402 double V, double W, 403 const Type *Ty) { 404 errno = 0; 405 V = NativeFP(V, W); 406 if (errno == 0) 407 return ConstantFP::get(Ty, V); 408 errno = 0; 409 return 0; 410} 411 412/// ConstantFoldCall - Attempt to constant fold a call to the specified function 413/// with the specified arguments, returning null if unsuccessful. 414Constant * 415llvm::ConstantFoldCall(Function *F, Constant** Operands, unsigned NumOperands) { 416 const ValueName *NameVal = F->getValueName(); 417 if (NameVal == 0) return 0; 418 const char *Str = NameVal->getKeyData(); 419 unsigned Len = NameVal->getKeyLength(); 420 421 const Type *Ty = F->getReturnType(); 422 if (NumOperands == 1) { 423 if (ConstantFP *Op = dyn_cast<ConstantFP>(Operands[0])) { 424 double V = Op->getValue(); 425 switch (Str[0]) { 426 case 'a': 427 if (Len == 4 && !strcmp(Str, "acos")) 428 return ConstantFoldFP(acos, V, Ty); 429 else if (Len == 4 && !strcmp(Str, "asin")) 430 return ConstantFoldFP(asin, V, Ty); 431 else if (Len == 4 && !strcmp(Str, "atan")) 432 return ConstantFoldFP(atan, V, Ty); 433 break; 434 case 'c': 435 if (Len == 4 && !strcmp(Str, "ceil")) 436 return ConstantFoldFP(ceil, V, Ty); 437 else if (Len == 3 && !strcmp(Str, "cos")) 438 return ConstantFoldFP(cos, V, Ty); 439 else if (Len == 4 && !strcmp(Str, "cosh")) 440 return ConstantFoldFP(cosh, V, Ty); 441 break; 442 case 'e': 443 if (Len == 3 && !strcmp(Str, "exp")) 444 return ConstantFoldFP(exp, V, Ty); 445 break; 446 case 'f': 447 if (Len == 4 && !strcmp(Str, "fabs")) 448 return ConstantFP::get(Ty, fabs(V)); 449 else if (Len == 5 && !strcmp(Str, "floor")) 450 return ConstantFoldFP(floor, V, Ty); 451 break; 452 case 'l': 453 if (Len == 3 && !strcmp(Str, "log") && V > 0) 454 return ConstantFoldFP(log, V, Ty); 455 else if (Len == 5 && !strcmp(Str, "log10") && V > 0) 456 return ConstantFoldFP(log10, V, Ty); 457 else if (!strcmp(Str, "llvm.sqrt.f32") || 458 !strcmp(Str, "llvm.sqrt.f64")) { 459 if (V >= -0.0) 460 return ConstantFP::get(Ty, sqrt(V)); 461 else // Undefined 462 return ConstantFP::get(Ty, 0.0); 463 } 464 break; 465 case 's': 466 if (Len == 3 && !strcmp(Str, "sin")) 467 return ConstantFoldFP(sin, V, Ty); 468 else if (Len == 4 && !strcmp(Str, "sinh")) 469 return ConstantFoldFP(sinh, V, Ty); 470 else if (Len == 4 && !strcmp(Str, "sqrt") && V >= 0) 471 return ConstantFoldFP(sqrt, V, Ty); 472 else if (Len == 5 && !strcmp(Str, "sqrtf") && V >= 0) 473 return ConstantFoldFP(sqrt, V, Ty); 474 break; 475 case 't': 476 if (Len == 3 && !strcmp(Str, "tan")) 477 return ConstantFoldFP(tan, V, Ty); 478 else if (Len == 4 && !strcmp(Str, "tanh")) 479 return ConstantFoldFP(tanh, V, Ty); 480 break; 481 default: 482 break; 483 } 484 } else if (ConstantInt *Op = dyn_cast<ConstantInt>(Operands[0])) { 485 if (Len > 11 && !memcmp(Str, "llvm.bswap", 10)) { 486 return ConstantInt::get(Op->getValue().byteSwap()); 487 } else if (Len > 11 && !memcmp(Str, "llvm.ctpop", 10)) { 488 uint64_t ctpop = Op->getValue().countPopulation(); 489 return ConstantInt::get(Ty, ctpop); 490 } else if (Len > 10 && !memcmp(Str, "llvm.cttz", 9)) { 491 uint64_t cttz = Op->getValue().countTrailingZeros(); 492 return ConstantInt::get(Ty, cttz); 493 } else if (Len > 10 && !memcmp(Str, "llvm.ctlz", 9)) { 494 uint64_t ctlz = Op->getValue().countLeadingZeros(); 495 return ConstantInt::get(Ty, ctlz); 496 } 497 } 498 } else if (NumOperands == 2) { 499 if (ConstantFP *Op1 = dyn_cast<ConstantFP>(Operands[0])) { 500 double Op1V = Op1->getValue(); 501 if (ConstantFP *Op2 = dyn_cast<ConstantFP>(Operands[1])) { 502 double Op2V = Op2->getValue(); 503 504 if (Len == 3 && !strcmp(Str, "pow")) { 505 return ConstantFoldBinaryFP(pow, Op1V, Op2V, Ty); 506 } else if (Len == 4 && !strcmp(Str, "fmod")) { 507 return ConstantFoldBinaryFP(fmod, Op1V, Op2V, Ty); 508 } else if (Len == 5 && !strcmp(Str, "atan2")) { 509 return ConstantFoldBinaryFP(atan2, Op1V, Op2V, Ty); 510 } 511 } else if (ConstantInt *Op2C = dyn_cast<ConstantInt>(Operands[1])) { 512 if (!strcmp(Str, "llvm.powi.f32")) { 513 return ConstantFP::get(Ty, std::pow((float)Op1V, 514 (int)Op2C->getZExtValue())); 515 } else if (!strcmp(Str, "llvm.powi.f64")) { 516 return ConstantFP::get(Ty, std::pow((double)Op1V, 517 (int)Op2C->getZExtValue())); 518 } 519 } 520 } 521 } 522 return 0; 523} 524 525