1//===- SimplifyLibCalls.cpp - Optimize specific well-known library calls --===// 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 file implements a simple pass that applies a variety of small 11// optimizations for calls to specific well-known function calls (e.g. runtime 12// library functions). Any optimization that takes the very simple form 13// "replace call to library function with simpler code that provides the same 14// result" belongs in this file. 15// 16//===----------------------------------------------------------------------===// 17 18#define DEBUG_TYPE "simplify-libcalls" 19#include "llvm/Transforms/Scalar.h" 20#include "llvm/Transforms/Utils/BuildLibCalls.h" 21#include "llvm/IRBuilder.h" 22#include "llvm/Intrinsics.h" 23#include "llvm/LLVMContext.h" 24#include "llvm/Module.h" 25#include "llvm/Pass.h" 26#include "llvm/ADT/STLExtras.h" 27#include "llvm/ADT/SmallPtrSet.h" 28#include "llvm/ADT/Statistic.h" 29#include "llvm/ADT/StringMap.h" 30#include "llvm/Analysis/ValueTracking.h" 31#include "llvm/Support/CommandLine.h" 32#include "llvm/Support/Debug.h" 33#include "llvm/Support/raw_ostream.h" 34#include "llvm/Target/TargetData.h" 35#include "llvm/Target/TargetLibraryInfo.h" 36#include "llvm/Config/config.h" // FIXME: Shouldn't depend on host! 37using namespace llvm; 38 39STATISTIC(NumSimplified, "Number of library calls simplified"); 40STATISTIC(NumAnnotated, "Number of attributes added to library functions"); 41 42static cl::opt<bool> UnsafeFPShrink("enable-double-float-shrink", cl::Hidden, 43 cl::init(false), 44 cl::desc("Enable unsafe double to float " 45 "shrinking for math lib calls")); 46//===----------------------------------------------------------------------===// 47// Optimizer Base Class 48//===----------------------------------------------------------------------===// 49 50/// This class is the abstract base class for the set of optimizations that 51/// corresponds to one library call. 52namespace { 53class LibCallOptimization { 54protected: 55 Function *Caller; 56 const TargetData *TD; 57 const TargetLibraryInfo *TLI; 58 LLVMContext* Context; 59public: 60 LibCallOptimization() { } 61 virtual ~LibCallOptimization() {} 62 63 /// CallOptimizer - This pure virtual method is implemented by base classes to 64 /// do various optimizations. If this returns null then no transformation was 65 /// performed. If it returns CI, then it transformed the call and CI is to be 66 /// deleted. If it returns something else, replace CI with the new value and 67 /// delete CI. 68 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) 69 =0; 70 71 Value *OptimizeCall(CallInst *CI, const TargetData *TD, 72 const TargetLibraryInfo *TLI, IRBuilder<> &B) { 73 Caller = CI->getParent()->getParent(); 74 this->TD = TD; 75 this->TLI = TLI; 76 if (CI->getCalledFunction()) 77 Context = &CI->getCalledFunction()->getContext(); 78 79 // We never change the calling convention. 80 if (CI->getCallingConv() != llvm::CallingConv::C) 81 return NULL; 82 83 return CallOptimizer(CI->getCalledFunction(), CI, B); 84 } 85}; 86} // End anonymous namespace. 87 88 89//===----------------------------------------------------------------------===// 90// Helper Functions 91//===----------------------------------------------------------------------===// 92 93/// IsOnlyUsedInZeroEqualityComparison - Return true if it only matters that the 94/// value is equal or not-equal to zero. 95static bool IsOnlyUsedInZeroEqualityComparison(Value *V) { 96 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); 97 UI != E; ++UI) { 98 if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI)) 99 if (IC->isEquality()) 100 if (Constant *C = dyn_cast<Constant>(IC->getOperand(1))) 101 if (C->isNullValue()) 102 continue; 103 // Unknown instruction. 104 return false; 105 } 106 return true; 107} 108 109static bool CallHasFloatingPointArgument(const CallInst *CI) { 110 for (CallInst::const_op_iterator it = CI->op_begin(), e = CI->op_end(); 111 it != e; ++it) { 112 if ((*it)->getType()->isFloatingPointTy()) 113 return true; 114 } 115 return false; 116} 117 118/// IsOnlyUsedInEqualityComparison - Return true if it is only used in equality 119/// comparisons with With. 120static bool IsOnlyUsedInEqualityComparison(Value *V, Value *With) { 121 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); 122 UI != E; ++UI) { 123 if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI)) 124 if (IC->isEquality() && IC->getOperand(1) == With) 125 continue; 126 // Unknown instruction. 127 return false; 128 } 129 return true; 130} 131 132//===----------------------------------------------------------------------===// 133// String and Memory LibCall Optimizations 134//===----------------------------------------------------------------------===// 135 136//===---------------------------------------===// 137// 'strcat' Optimizations 138namespace { 139struct StrCatOpt : public LibCallOptimization { 140 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 141 // Verify the "strcat" function prototype. 142 FunctionType *FT = Callee->getFunctionType(); 143 if (FT->getNumParams() != 2 || 144 FT->getReturnType() != B.getInt8PtrTy() || 145 FT->getParamType(0) != FT->getReturnType() || 146 FT->getParamType(1) != FT->getReturnType()) 147 return 0; 148 149 // Extract some information from the instruction 150 Value *Dst = CI->getArgOperand(0); 151 Value *Src = CI->getArgOperand(1); 152 153 // See if we can get the length of the input string. 154 uint64_t Len = GetStringLength(Src); 155 if (Len == 0) return 0; 156 --Len; // Unbias length. 157 158 // Handle the simple, do-nothing case: strcat(x, "") -> x 159 if (Len == 0) 160 return Dst; 161 162 // These optimizations require TargetData. 163 if (!TD) return 0; 164 165 return EmitStrLenMemCpy(Src, Dst, Len, B); 166 } 167 168 Value *EmitStrLenMemCpy(Value *Src, Value *Dst, uint64_t Len, IRBuilder<> &B) { 169 // We need to find the end of the destination string. That's where the 170 // memory is to be moved to. We just generate a call to strlen. 171 Value *DstLen = EmitStrLen(Dst, B, TD, TLI); 172 if (!DstLen) 173 return 0; 174 175 // Now that we have the destination's length, we must index into the 176 // destination's pointer to get the actual memcpy destination (end of 177 // the string .. we're concatenating). 178 Value *CpyDst = B.CreateGEP(Dst, DstLen, "endptr"); 179 180 // We have enough information to now generate the memcpy call to do the 181 // concatenation for us. Make a memcpy to copy the nul byte with align = 1. 182 B.CreateMemCpy(CpyDst, Src, 183 ConstantInt::get(TD->getIntPtrType(*Context), Len + 1), 1); 184 return Dst; 185 } 186}; 187 188//===---------------------------------------===// 189// 'strncat' Optimizations 190 191struct StrNCatOpt : public StrCatOpt { 192 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 193 // Verify the "strncat" function prototype. 194 FunctionType *FT = Callee->getFunctionType(); 195 if (FT->getNumParams() != 3 || 196 FT->getReturnType() != B.getInt8PtrTy() || 197 FT->getParamType(0) != FT->getReturnType() || 198 FT->getParamType(1) != FT->getReturnType() || 199 !FT->getParamType(2)->isIntegerTy()) 200 return 0; 201 202 // Extract some information from the instruction 203 Value *Dst = CI->getArgOperand(0); 204 Value *Src = CI->getArgOperand(1); 205 uint64_t Len; 206 207 // We don't do anything if length is not constant 208 if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2))) 209 Len = LengthArg->getZExtValue(); 210 else 211 return 0; 212 213 // See if we can get the length of the input string. 214 uint64_t SrcLen = GetStringLength(Src); 215 if (SrcLen == 0) return 0; 216 --SrcLen; // Unbias length. 217 218 // Handle the simple, do-nothing cases: 219 // strncat(x, "", c) -> x 220 // strncat(x, c, 0) -> x 221 if (SrcLen == 0 || Len == 0) return Dst; 222 223 // These optimizations require TargetData. 224 if (!TD) return 0; 225 226 // We don't optimize this case 227 if (Len < SrcLen) return 0; 228 229 // strncat(x, s, c) -> strcat(x, s) 230 // s is constant so the strcat can be optimized further 231 return EmitStrLenMemCpy(Src, Dst, SrcLen, B); 232 } 233}; 234 235//===---------------------------------------===// 236// 'strchr' Optimizations 237 238struct StrChrOpt : public LibCallOptimization { 239 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 240 // Verify the "strchr" function prototype. 241 FunctionType *FT = Callee->getFunctionType(); 242 if (FT->getNumParams() != 2 || 243 FT->getReturnType() != B.getInt8PtrTy() || 244 FT->getParamType(0) != FT->getReturnType() || 245 !FT->getParamType(1)->isIntegerTy(32)) 246 return 0; 247 248 Value *SrcStr = CI->getArgOperand(0); 249 250 // If the second operand is non-constant, see if we can compute the length 251 // of the input string and turn this into memchr. 252 ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 253 if (CharC == 0) { 254 // These optimizations require TargetData. 255 if (!TD) return 0; 256 257 uint64_t Len = GetStringLength(SrcStr); 258 if (Len == 0 || !FT->getParamType(1)->isIntegerTy(32))// memchr needs i32. 259 return 0; 260 261 return EmitMemChr(SrcStr, CI->getArgOperand(1), // include nul. 262 ConstantInt::get(TD->getIntPtrType(*Context), Len), 263 B, TD, TLI); 264 } 265 266 // Otherwise, the character is a constant, see if the first argument is 267 // a string literal. If so, we can constant fold. 268 StringRef Str; 269 if (!getConstantStringInfo(SrcStr, Str)) 270 return 0; 271 272 // Compute the offset, make sure to handle the case when we're searching for 273 // zero (a weird way to spell strlen). 274 size_t I = CharC->getSExtValue() == 0 ? 275 Str.size() : Str.find(CharC->getSExtValue()); 276 if (I == StringRef::npos) // Didn't find the char. strchr returns null. 277 return Constant::getNullValue(CI->getType()); 278 279 // strchr(s+n,c) -> gep(s+n+i,c) 280 return B.CreateGEP(SrcStr, B.getInt64(I), "strchr"); 281 } 282}; 283 284//===---------------------------------------===// 285// 'strrchr' Optimizations 286 287struct StrRChrOpt : public LibCallOptimization { 288 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 289 // Verify the "strrchr" function prototype. 290 FunctionType *FT = Callee->getFunctionType(); 291 if (FT->getNumParams() != 2 || 292 FT->getReturnType() != B.getInt8PtrTy() || 293 FT->getParamType(0) != FT->getReturnType() || 294 !FT->getParamType(1)->isIntegerTy(32)) 295 return 0; 296 297 Value *SrcStr = CI->getArgOperand(0); 298 ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 299 300 // Cannot fold anything if we're not looking for a constant. 301 if (!CharC) 302 return 0; 303 304 StringRef Str; 305 if (!getConstantStringInfo(SrcStr, Str)) { 306 // strrchr(s, 0) -> strchr(s, 0) 307 if (TD && CharC->isZero()) 308 return EmitStrChr(SrcStr, '\0', B, TD, TLI); 309 return 0; 310 } 311 312 // Compute the offset. 313 size_t I = CharC->getSExtValue() == 0 ? 314 Str.size() : Str.rfind(CharC->getSExtValue()); 315 if (I == StringRef::npos) // Didn't find the char. Return null. 316 return Constant::getNullValue(CI->getType()); 317 318 // strrchr(s+n,c) -> gep(s+n+i,c) 319 return B.CreateGEP(SrcStr, B.getInt64(I), "strrchr"); 320 } 321}; 322 323//===---------------------------------------===// 324// 'strcmp' Optimizations 325 326struct StrCmpOpt : public LibCallOptimization { 327 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 328 // Verify the "strcmp" function prototype. 329 FunctionType *FT = Callee->getFunctionType(); 330 if (FT->getNumParams() != 2 || 331 !FT->getReturnType()->isIntegerTy(32) || 332 FT->getParamType(0) != FT->getParamType(1) || 333 FT->getParamType(0) != B.getInt8PtrTy()) 334 return 0; 335 336 Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1); 337 if (Str1P == Str2P) // strcmp(x,x) -> 0 338 return ConstantInt::get(CI->getType(), 0); 339 340 StringRef Str1, Str2; 341 bool HasStr1 = getConstantStringInfo(Str1P, Str1); 342 bool HasStr2 = getConstantStringInfo(Str2P, Str2); 343 344 // strcmp(x, y) -> cnst (if both x and y are constant strings) 345 if (HasStr1 && HasStr2) 346 return ConstantInt::get(CI->getType(), Str1.compare(Str2)); 347 348 if (HasStr1 && Str1.empty()) // strcmp("", x) -> -*x 349 return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"), 350 CI->getType())); 351 352 if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x 353 return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType()); 354 355 // strcmp(P, "x") -> memcmp(P, "x", 2) 356 uint64_t Len1 = GetStringLength(Str1P); 357 uint64_t Len2 = GetStringLength(Str2P); 358 if (Len1 && Len2) { 359 // These optimizations require TargetData. 360 if (!TD) return 0; 361 362 return EmitMemCmp(Str1P, Str2P, 363 ConstantInt::get(TD->getIntPtrType(*Context), 364 std::min(Len1, Len2)), B, TD, TLI); 365 } 366 367 return 0; 368 } 369}; 370 371//===---------------------------------------===// 372// 'strncmp' Optimizations 373 374struct StrNCmpOpt : public LibCallOptimization { 375 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 376 // Verify the "strncmp" function prototype. 377 FunctionType *FT = Callee->getFunctionType(); 378 if (FT->getNumParams() != 3 || 379 !FT->getReturnType()->isIntegerTy(32) || 380 FT->getParamType(0) != FT->getParamType(1) || 381 FT->getParamType(0) != B.getInt8PtrTy() || 382 !FT->getParamType(2)->isIntegerTy()) 383 return 0; 384 385 Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1); 386 if (Str1P == Str2P) // strncmp(x,x,n) -> 0 387 return ConstantInt::get(CI->getType(), 0); 388 389 // Get the length argument if it is constant. 390 uint64_t Length; 391 if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2))) 392 Length = LengthArg->getZExtValue(); 393 else 394 return 0; 395 396 if (Length == 0) // strncmp(x,y,0) -> 0 397 return ConstantInt::get(CI->getType(), 0); 398 399 if (TD && Length == 1) // strncmp(x,y,1) -> memcmp(x,y,1) 400 return EmitMemCmp(Str1P, Str2P, CI->getArgOperand(2), B, TD, TLI); 401 402 StringRef Str1, Str2; 403 bool HasStr1 = getConstantStringInfo(Str1P, Str1); 404 bool HasStr2 = getConstantStringInfo(Str2P, Str2); 405 406 // strncmp(x, y) -> cnst (if both x and y are constant strings) 407 if (HasStr1 && HasStr2) { 408 StringRef SubStr1 = Str1.substr(0, Length); 409 StringRef SubStr2 = Str2.substr(0, Length); 410 return ConstantInt::get(CI->getType(), SubStr1.compare(SubStr2)); 411 } 412 413 if (HasStr1 && Str1.empty()) // strncmp("", x, n) -> -*x 414 return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"), 415 CI->getType())); 416 417 if (HasStr2 && Str2.empty()) // strncmp(x, "", n) -> *x 418 return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType()); 419 420 return 0; 421 } 422}; 423 424 425//===---------------------------------------===// 426// 'strcpy' Optimizations 427 428struct StrCpyOpt : public LibCallOptimization { 429 bool OptChkCall; // True if it's optimizing a __strcpy_chk libcall. 430 431 StrCpyOpt(bool c) : OptChkCall(c) {} 432 433 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 434 // Verify the "strcpy" function prototype. 435 unsigned NumParams = OptChkCall ? 3 : 2; 436 FunctionType *FT = Callee->getFunctionType(); 437 if (FT->getNumParams() != NumParams || 438 FT->getReturnType() != FT->getParamType(0) || 439 FT->getParamType(0) != FT->getParamType(1) || 440 FT->getParamType(0) != B.getInt8PtrTy()) 441 return 0; 442 443 Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1); 444 if (Dst == Src) // strcpy(x,x) -> x 445 return Src; 446 447 // These optimizations require TargetData. 448 if (!TD) return 0; 449 450 // See if we can get the length of the input string. 451 uint64_t Len = GetStringLength(Src); 452 if (Len == 0) return 0; 453 454 // We have enough information to now generate the memcpy call to do the 455 // concatenation for us. Make a memcpy to copy the nul byte with align = 1. 456 if (!OptChkCall || 457 !EmitMemCpyChk(Dst, Src, 458 ConstantInt::get(TD->getIntPtrType(*Context), Len), 459 CI->getArgOperand(2), B, TD, TLI)) 460 B.CreateMemCpy(Dst, Src, 461 ConstantInt::get(TD->getIntPtrType(*Context), Len), 1); 462 return Dst; 463 } 464}; 465 466//===---------------------------------------===// 467// 'stpcpy' Optimizations 468 469struct StpCpyOpt: public LibCallOptimization { 470 bool OptChkCall; // True if it's optimizing a __stpcpy_chk libcall. 471 472 StpCpyOpt(bool c) : OptChkCall(c) {} 473 474 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 475 // Verify the "stpcpy" function prototype. 476 unsigned NumParams = OptChkCall ? 3 : 2; 477 FunctionType *FT = Callee->getFunctionType(); 478 if (FT->getNumParams() != NumParams || 479 FT->getReturnType() != FT->getParamType(0) || 480 FT->getParamType(0) != FT->getParamType(1) || 481 FT->getParamType(0) != B.getInt8PtrTy()) 482 return 0; 483 484 // These optimizations require TargetData. 485 if (!TD) return 0; 486 487 Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1); 488 if (Dst == Src) { // stpcpy(x,x) -> x+strlen(x) 489 Value *StrLen = EmitStrLen(Src, B, TD, TLI); 490 return StrLen ? B.CreateInBoundsGEP(Dst, StrLen) : 0; 491 } 492 493 // See if we can get the length of the input string. 494 uint64_t Len = GetStringLength(Src); 495 if (Len == 0) return 0; 496 497 Value *LenV = ConstantInt::get(TD->getIntPtrType(*Context), Len); 498 Value *DstEnd = B.CreateGEP(Dst, 499 ConstantInt::get(TD->getIntPtrType(*Context), 500 Len - 1)); 501 502 // We have enough information to now generate the memcpy call to do the 503 // copy for us. Make a memcpy to copy the nul byte with align = 1. 504 if (!OptChkCall || !EmitMemCpyChk(Dst, Src, LenV, CI->getArgOperand(2), B, 505 TD, TLI)) 506 B.CreateMemCpy(Dst, Src, LenV, 1); 507 return DstEnd; 508 } 509}; 510 511//===---------------------------------------===// 512// 'strncpy' Optimizations 513 514struct StrNCpyOpt : public LibCallOptimization { 515 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 516 FunctionType *FT = Callee->getFunctionType(); 517 if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) || 518 FT->getParamType(0) != FT->getParamType(1) || 519 FT->getParamType(0) != B.getInt8PtrTy() || 520 !FT->getParamType(2)->isIntegerTy()) 521 return 0; 522 523 Value *Dst = CI->getArgOperand(0); 524 Value *Src = CI->getArgOperand(1); 525 Value *LenOp = CI->getArgOperand(2); 526 527 // See if we can get the length of the input string. 528 uint64_t SrcLen = GetStringLength(Src); 529 if (SrcLen == 0) return 0; 530 --SrcLen; 531 532 if (SrcLen == 0) { 533 // strncpy(x, "", y) -> memset(x, '\0', y, 1) 534 B.CreateMemSet(Dst, B.getInt8('\0'), LenOp, 1); 535 return Dst; 536 } 537 538 uint64_t Len; 539 if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(LenOp)) 540 Len = LengthArg->getZExtValue(); 541 else 542 return 0; 543 544 if (Len == 0) return Dst; // strncpy(x, y, 0) -> x 545 546 // These optimizations require TargetData. 547 if (!TD) return 0; 548 549 // Let strncpy handle the zero padding 550 if (Len > SrcLen+1) return 0; 551 552 // strncpy(x, s, c) -> memcpy(x, s, c, 1) [s and c are constant] 553 B.CreateMemCpy(Dst, Src, 554 ConstantInt::get(TD->getIntPtrType(*Context), Len), 1); 555 556 return Dst; 557 } 558}; 559 560//===---------------------------------------===// 561// 'strlen' Optimizations 562 563struct StrLenOpt : public LibCallOptimization { 564 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 565 FunctionType *FT = Callee->getFunctionType(); 566 if (FT->getNumParams() != 1 || 567 FT->getParamType(0) != B.getInt8PtrTy() || 568 !FT->getReturnType()->isIntegerTy()) 569 return 0; 570 571 Value *Src = CI->getArgOperand(0); 572 573 // Constant folding: strlen("xyz") -> 3 574 if (uint64_t Len = GetStringLength(Src)) 575 return ConstantInt::get(CI->getType(), Len-1); 576 577 // strlen(x) != 0 --> *x != 0 578 // strlen(x) == 0 --> *x == 0 579 if (IsOnlyUsedInZeroEqualityComparison(CI)) 580 return B.CreateZExt(B.CreateLoad(Src, "strlenfirst"), CI->getType()); 581 return 0; 582 } 583}; 584 585 586//===---------------------------------------===// 587// 'strpbrk' Optimizations 588 589struct StrPBrkOpt : public LibCallOptimization { 590 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 591 FunctionType *FT = Callee->getFunctionType(); 592 if (FT->getNumParams() != 2 || 593 FT->getParamType(0) != B.getInt8PtrTy() || 594 FT->getParamType(1) != FT->getParamType(0) || 595 FT->getReturnType() != FT->getParamType(0)) 596 return 0; 597 598 StringRef S1, S2; 599 bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1); 600 bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2); 601 602 // strpbrk(s, "") -> NULL 603 // strpbrk("", s) -> NULL 604 if ((HasS1 && S1.empty()) || (HasS2 && S2.empty())) 605 return Constant::getNullValue(CI->getType()); 606 607 // Constant folding. 608 if (HasS1 && HasS2) { 609 size_t I = S1.find_first_of(S2); 610 if (I == std::string::npos) // No match. 611 return Constant::getNullValue(CI->getType()); 612 613 return B.CreateGEP(CI->getArgOperand(0), B.getInt64(I), "strpbrk"); 614 } 615 616 // strpbrk(s, "a") -> strchr(s, 'a') 617 if (TD && HasS2 && S2.size() == 1) 618 return EmitStrChr(CI->getArgOperand(0), S2[0], B, TD, TLI); 619 620 return 0; 621 } 622}; 623 624//===---------------------------------------===// 625// 'strto*' Optimizations. This handles strtol, strtod, strtof, strtoul, etc. 626 627struct StrToOpt : public LibCallOptimization { 628 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 629 FunctionType *FT = Callee->getFunctionType(); 630 if ((FT->getNumParams() != 2 && FT->getNumParams() != 3) || 631 !FT->getParamType(0)->isPointerTy() || 632 !FT->getParamType(1)->isPointerTy()) 633 return 0; 634 635 Value *EndPtr = CI->getArgOperand(1); 636 if (isa<ConstantPointerNull>(EndPtr)) { 637 // With a null EndPtr, this function won't capture the main argument. 638 // It would be readonly too, except that it still may write to errno. 639 CI->addAttribute(1, Attribute::NoCapture); 640 } 641 642 return 0; 643 } 644}; 645 646//===---------------------------------------===// 647// 'strspn' Optimizations 648 649struct StrSpnOpt : public LibCallOptimization { 650 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 651 FunctionType *FT = Callee->getFunctionType(); 652 if (FT->getNumParams() != 2 || 653 FT->getParamType(0) != B.getInt8PtrTy() || 654 FT->getParamType(1) != FT->getParamType(0) || 655 !FT->getReturnType()->isIntegerTy()) 656 return 0; 657 658 StringRef S1, S2; 659 bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1); 660 bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2); 661 662 // strspn(s, "") -> 0 663 // strspn("", s) -> 0 664 if ((HasS1 && S1.empty()) || (HasS2 && S2.empty())) 665 return Constant::getNullValue(CI->getType()); 666 667 // Constant folding. 668 if (HasS1 && HasS2) { 669 size_t Pos = S1.find_first_not_of(S2); 670 if (Pos == StringRef::npos) Pos = S1.size(); 671 return ConstantInt::get(CI->getType(), Pos); 672 } 673 674 return 0; 675 } 676}; 677 678//===---------------------------------------===// 679// 'strcspn' Optimizations 680 681struct StrCSpnOpt : public LibCallOptimization { 682 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 683 FunctionType *FT = Callee->getFunctionType(); 684 if (FT->getNumParams() != 2 || 685 FT->getParamType(0) != B.getInt8PtrTy() || 686 FT->getParamType(1) != FT->getParamType(0) || 687 !FT->getReturnType()->isIntegerTy()) 688 return 0; 689 690 StringRef S1, S2; 691 bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1); 692 bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2); 693 694 // strcspn("", s) -> 0 695 if (HasS1 && S1.empty()) 696 return Constant::getNullValue(CI->getType()); 697 698 // Constant folding. 699 if (HasS1 && HasS2) { 700 size_t Pos = S1.find_first_of(S2); 701 if (Pos == StringRef::npos) Pos = S1.size(); 702 return ConstantInt::get(CI->getType(), Pos); 703 } 704 705 // strcspn(s, "") -> strlen(s) 706 if (TD && HasS2 && S2.empty()) 707 return EmitStrLen(CI->getArgOperand(0), B, TD, TLI); 708 709 return 0; 710 } 711}; 712 713//===---------------------------------------===// 714// 'strstr' Optimizations 715 716struct StrStrOpt : public LibCallOptimization { 717 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 718 FunctionType *FT = Callee->getFunctionType(); 719 if (FT->getNumParams() != 2 || 720 !FT->getParamType(0)->isPointerTy() || 721 !FT->getParamType(1)->isPointerTy() || 722 !FT->getReturnType()->isPointerTy()) 723 return 0; 724 725 // fold strstr(x, x) -> x. 726 if (CI->getArgOperand(0) == CI->getArgOperand(1)) 727 return B.CreateBitCast(CI->getArgOperand(0), CI->getType()); 728 729 // fold strstr(a, b) == a -> strncmp(a, b, strlen(b)) == 0 730 if (TD && IsOnlyUsedInEqualityComparison(CI, CI->getArgOperand(0))) { 731 Value *StrLen = EmitStrLen(CI->getArgOperand(1), B, TD, TLI); 732 if (!StrLen) 733 return 0; 734 Value *StrNCmp = EmitStrNCmp(CI->getArgOperand(0), CI->getArgOperand(1), 735 StrLen, B, TD, TLI); 736 if (!StrNCmp) 737 return 0; 738 for (Value::use_iterator UI = CI->use_begin(), UE = CI->use_end(); 739 UI != UE; ) { 740 ICmpInst *Old = cast<ICmpInst>(*UI++); 741 Value *Cmp = B.CreateICmp(Old->getPredicate(), StrNCmp, 742 ConstantInt::getNullValue(StrNCmp->getType()), 743 "cmp"); 744 Old->replaceAllUsesWith(Cmp); 745 Old->eraseFromParent(); 746 } 747 return CI; 748 } 749 750 // See if either input string is a constant string. 751 StringRef SearchStr, ToFindStr; 752 bool HasStr1 = getConstantStringInfo(CI->getArgOperand(0), SearchStr); 753 bool HasStr2 = getConstantStringInfo(CI->getArgOperand(1), ToFindStr); 754 755 // fold strstr(x, "") -> x. 756 if (HasStr2 && ToFindStr.empty()) 757 return B.CreateBitCast(CI->getArgOperand(0), CI->getType()); 758 759 // If both strings are known, constant fold it. 760 if (HasStr1 && HasStr2) { 761 std::string::size_type Offset = SearchStr.find(ToFindStr); 762 763 if (Offset == StringRef::npos) // strstr("foo", "bar") -> null 764 return Constant::getNullValue(CI->getType()); 765 766 // strstr("abcd", "bc") -> gep((char*)"abcd", 1) 767 Value *Result = CastToCStr(CI->getArgOperand(0), B); 768 Result = B.CreateConstInBoundsGEP1_64(Result, Offset, "strstr"); 769 return B.CreateBitCast(Result, CI->getType()); 770 } 771 772 // fold strstr(x, "y") -> strchr(x, 'y'). 773 if (HasStr2 && ToFindStr.size() == 1) { 774 Value *StrChr= EmitStrChr(CI->getArgOperand(0), ToFindStr[0], B, TD, TLI); 775 return StrChr ? B.CreateBitCast(StrChr, CI->getType()) : 0; 776 } 777 return 0; 778 } 779}; 780 781 782//===---------------------------------------===// 783// 'memcmp' Optimizations 784 785struct MemCmpOpt : public LibCallOptimization { 786 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 787 FunctionType *FT = Callee->getFunctionType(); 788 if (FT->getNumParams() != 3 || !FT->getParamType(0)->isPointerTy() || 789 !FT->getParamType(1)->isPointerTy() || 790 !FT->getReturnType()->isIntegerTy(32)) 791 return 0; 792 793 Value *LHS = CI->getArgOperand(0), *RHS = CI->getArgOperand(1); 794 795 if (LHS == RHS) // memcmp(s,s,x) -> 0 796 return Constant::getNullValue(CI->getType()); 797 798 // Make sure we have a constant length. 799 ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getArgOperand(2)); 800 if (!LenC) return 0; 801 uint64_t Len = LenC->getZExtValue(); 802 803 if (Len == 0) // memcmp(s1,s2,0) -> 0 804 return Constant::getNullValue(CI->getType()); 805 806 // memcmp(S1,S2,1) -> *(unsigned char*)LHS - *(unsigned char*)RHS 807 if (Len == 1) { 808 Value *LHSV = B.CreateZExt(B.CreateLoad(CastToCStr(LHS, B), "lhsc"), 809 CI->getType(), "lhsv"); 810 Value *RHSV = B.CreateZExt(B.CreateLoad(CastToCStr(RHS, B), "rhsc"), 811 CI->getType(), "rhsv"); 812 return B.CreateSub(LHSV, RHSV, "chardiff"); 813 } 814 815 // Constant folding: memcmp(x, y, l) -> cnst (all arguments are constant) 816 StringRef LHSStr, RHSStr; 817 if (getConstantStringInfo(LHS, LHSStr) && 818 getConstantStringInfo(RHS, RHSStr)) { 819 // Make sure we're not reading out-of-bounds memory. 820 if (Len > LHSStr.size() || Len > RHSStr.size()) 821 return 0; 822 uint64_t Ret = memcmp(LHSStr.data(), RHSStr.data(), Len); 823 return ConstantInt::get(CI->getType(), Ret); 824 } 825 826 return 0; 827 } 828}; 829 830//===---------------------------------------===// 831// 'memcpy' Optimizations 832 833struct MemCpyOpt : public LibCallOptimization { 834 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 835 // These optimizations require TargetData. 836 if (!TD) return 0; 837 838 FunctionType *FT = Callee->getFunctionType(); 839 if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) || 840 !FT->getParamType(0)->isPointerTy() || 841 !FT->getParamType(1)->isPointerTy() || 842 FT->getParamType(2) != TD->getIntPtrType(*Context)) 843 return 0; 844 845 // memcpy(x, y, n) -> llvm.memcpy(x, y, n, 1) 846 B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1), 847 CI->getArgOperand(2), 1); 848 return CI->getArgOperand(0); 849 } 850}; 851 852//===---------------------------------------===// 853// 'memmove' Optimizations 854 855struct MemMoveOpt : public LibCallOptimization { 856 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 857 // These optimizations require TargetData. 858 if (!TD) return 0; 859 860 FunctionType *FT = Callee->getFunctionType(); 861 if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) || 862 !FT->getParamType(0)->isPointerTy() || 863 !FT->getParamType(1)->isPointerTy() || 864 FT->getParamType(2) != TD->getIntPtrType(*Context)) 865 return 0; 866 867 // memmove(x, y, n) -> llvm.memmove(x, y, n, 1) 868 B.CreateMemMove(CI->getArgOperand(0), CI->getArgOperand(1), 869 CI->getArgOperand(2), 1); 870 return CI->getArgOperand(0); 871 } 872}; 873 874//===---------------------------------------===// 875// 'memset' Optimizations 876 877struct MemSetOpt : public LibCallOptimization { 878 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 879 // These optimizations require TargetData. 880 if (!TD) return 0; 881 882 FunctionType *FT = Callee->getFunctionType(); 883 if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) || 884 !FT->getParamType(0)->isPointerTy() || 885 !FT->getParamType(1)->isIntegerTy() || 886 FT->getParamType(2) != TD->getIntPtrType(*Context)) 887 return 0; 888 889 // memset(p, v, n) -> llvm.memset(p, v, n, 1) 890 Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(), false); 891 B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1); 892 return CI->getArgOperand(0); 893 } 894}; 895 896//===----------------------------------------------------------------------===// 897// Math Library Optimizations 898//===----------------------------------------------------------------------===// 899 900//===---------------------------------------===// 901// Double -> Float Shrinking Optimizations for Unary Functions like 'floor' 902 903struct UnaryDoubleFPOpt : public LibCallOptimization { 904 bool CheckRetType; 905 UnaryDoubleFPOpt(bool CheckReturnType): CheckRetType(CheckReturnType) {} 906 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 907 FunctionType *FT = Callee->getFunctionType(); 908 if (FT->getNumParams() != 1 || !FT->getReturnType()->isDoubleTy() || 909 !FT->getParamType(0)->isDoubleTy()) 910 return 0; 911 912 if (CheckRetType) { 913 // Check if all the uses for function like 'sin' are converted to float. 914 for (Value::use_iterator UseI = CI->use_begin(); UseI != CI->use_end(); 915 ++UseI) { 916 FPTruncInst *Cast = dyn_cast<FPTruncInst>(*UseI); 917 if (Cast == 0 || !Cast->getType()->isFloatTy()) 918 return 0; 919 } 920 } 921 922 // If this is something like 'floor((double)floatval)', convert to floorf. 923 FPExtInst *Cast = dyn_cast<FPExtInst>(CI->getArgOperand(0)); 924 if (Cast == 0 || !Cast->getOperand(0)->getType()->isFloatTy()) 925 return 0; 926 927 // floor((double)floatval) -> (double)floorf(floatval) 928 Value *V = Cast->getOperand(0); 929 V = EmitUnaryFloatFnCall(V, Callee->getName(), B, Callee->getAttributes()); 930 return B.CreateFPExt(V, B.getDoubleTy()); 931 } 932}; 933 934//===---------------------------------------===// 935// 'cos*' Optimizations 936struct CosOpt : public LibCallOptimization { 937 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 938 Value *Ret = NULL; 939 if (UnsafeFPShrink && Callee->getName() == "cos" && 940 TLI->has(LibFunc::cosf)) { 941 UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true); 942 Ret = UnsafeUnaryDoubleFP.CallOptimizer(Callee, CI, B); 943 } 944 945 FunctionType *FT = Callee->getFunctionType(); 946 // Just make sure this has 1 argument of FP type, which matches the 947 // result type. 948 if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) || 949 !FT->getParamType(0)->isFloatingPointTy()) 950 return Ret; 951 952 // cos(-x) -> cos(x) 953 Value *Op1 = CI->getArgOperand(0); 954 if (BinaryOperator::isFNeg(Op1)) { 955 BinaryOperator *BinExpr = cast<BinaryOperator>(Op1); 956 return B.CreateCall(Callee, BinExpr->getOperand(1), "cos"); 957 } 958 return Ret; 959 } 960}; 961 962//===---------------------------------------===// 963// 'pow*' Optimizations 964 965struct PowOpt : public LibCallOptimization { 966 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 967 Value *Ret = NULL; 968 if (UnsafeFPShrink && Callee->getName() == "pow" && 969 TLI->has(LibFunc::powf)) { 970 UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true); 971 Ret = UnsafeUnaryDoubleFP.CallOptimizer(Callee, CI, B); 972 } 973 974 FunctionType *FT = Callee->getFunctionType(); 975 // Just make sure this has 2 arguments of the same FP type, which match the 976 // result type. 977 if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) || 978 FT->getParamType(0) != FT->getParamType(1) || 979 !FT->getParamType(0)->isFloatingPointTy()) 980 return Ret; 981 982 Value *Op1 = CI->getArgOperand(0), *Op2 = CI->getArgOperand(1); 983 if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) { 984 if (Op1C->isExactlyValue(1.0)) // pow(1.0, x) -> 1.0 985 return Op1C; 986 if (Op1C->isExactlyValue(2.0)) // pow(2.0, x) -> exp2(x) 987 return EmitUnaryFloatFnCall(Op2, "exp2", B, Callee->getAttributes()); 988 } 989 990 ConstantFP *Op2C = dyn_cast<ConstantFP>(Op2); 991 if (Op2C == 0) return Ret; 992 993 if (Op2C->getValueAPF().isZero()) // pow(x, 0.0) -> 1.0 994 return ConstantFP::get(CI->getType(), 1.0); 995 996 if (Op2C->isExactlyValue(0.5)) { 997 // Expand pow(x, 0.5) to (x == -infinity ? +infinity : fabs(sqrt(x))). 998 // This is faster than calling pow, and still handles negative zero 999 // and negative infinity correctly. 1000 // TODO: In fast-math mode, this could be just sqrt(x). 1001 // TODO: In finite-only mode, this could be just fabs(sqrt(x)). 1002 Value *Inf = ConstantFP::getInfinity(CI->getType()); 1003 Value *NegInf = ConstantFP::getInfinity(CI->getType(), true); 1004 Value *Sqrt = EmitUnaryFloatFnCall(Op1, "sqrt", B, 1005 Callee->getAttributes()); 1006 Value *FAbs = EmitUnaryFloatFnCall(Sqrt, "fabs", B, 1007 Callee->getAttributes()); 1008 Value *FCmp = B.CreateFCmpOEQ(Op1, NegInf); 1009 Value *Sel = B.CreateSelect(FCmp, Inf, FAbs); 1010 return Sel; 1011 } 1012 1013 if (Op2C->isExactlyValue(1.0)) // pow(x, 1.0) -> x 1014 return Op1; 1015 if (Op2C->isExactlyValue(2.0)) // pow(x, 2.0) -> x*x 1016 return B.CreateFMul(Op1, Op1, "pow2"); 1017 if (Op2C->isExactlyValue(-1.0)) // pow(x, -1.0) -> 1.0/x 1018 return B.CreateFDiv(ConstantFP::get(CI->getType(), 1.0), 1019 Op1, "powrecip"); 1020 return 0; 1021 } 1022}; 1023 1024//===---------------------------------------===// 1025// 'exp2' Optimizations 1026 1027struct Exp2Opt : public LibCallOptimization { 1028 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 1029 Value *Ret = NULL; 1030 if (UnsafeFPShrink && Callee->getName() == "exp2" && 1031 TLI->has(LibFunc::exp2)) { 1032 UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true); 1033 Ret = UnsafeUnaryDoubleFP.CallOptimizer(Callee, CI, B); 1034 } 1035 1036 FunctionType *FT = Callee->getFunctionType(); 1037 // Just make sure this has 1 argument of FP type, which matches the 1038 // result type. 1039 if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) || 1040 !FT->getParamType(0)->isFloatingPointTy()) 1041 return Ret; 1042 1043 Value *Op = CI->getArgOperand(0); 1044 // Turn exp2(sitofp(x)) -> ldexp(1.0, sext(x)) if sizeof(x) <= 32 1045 // Turn exp2(uitofp(x)) -> ldexp(1.0, zext(x)) if sizeof(x) < 32 1046 Value *LdExpArg = 0; 1047 if (SIToFPInst *OpC = dyn_cast<SIToFPInst>(Op)) { 1048 if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() <= 32) 1049 LdExpArg = B.CreateSExt(OpC->getOperand(0), B.getInt32Ty()); 1050 } else if (UIToFPInst *OpC = dyn_cast<UIToFPInst>(Op)) { 1051 if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() < 32) 1052 LdExpArg = B.CreateZExt(OpC->getOperand(0), B.getInt32Ty()); 1053 } 1054 1055 if (LdExpArg) { 1056 const char *Name; 1057 if (Op->getType()->isFloatTy()) 1058 Name = "ldexpf"; 1059 else if (Op->getType()->isDoubleTy()) 1060 Name = "ldexp"; 1061 else 1062 Name = "ldexpl"; 1063 1064 Constant *One = ConstantFP::get(*Context, APFloat(1.0f)); 1065 if (!Op->getType()->isFloatTy()) 1066 One = ConstantExpr::getFPExtend(One, Op->getType()); 1067 1068 Module *M = Caller->getParent(); 1069 Value *Callee = M->getOrInsertFunction(Name, Op->getType(), 1070 Op->getType(), 1071 B.getInt32Ty(), NULL); 1072 CallInst *CI = B.CreateCall2(Callee, One, LdExpArg); 1073 if (const Function *F = dyn_cast<Function>(Callee->stripPointerCasts())) 1074 CI->setCallingConv(F->getCallingConv()); 1075 1076 return CI; 1077 } 1078 return Ret; 1079 } 1080}; 1081 1082//===----------------------------------------------------------------------===// 1083// Integer Optimizations 1084//===----------------------------------------------------------------------===// 1085 1086//===---------------------------------------===// 1087// 'ffs*' Optimizations 1088 1089struct FFSOpt : public LibCallOptimization { 1090 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 1091 FunctionType *FT = Callee->getFunctionType(); 1092 // Just make sure this has 2 arguments of the same FP type, which match the 1093 // result type. 1094 if (FT->getNumParams() != 1 || 1095 !FT->getReturnType()->isIntegerTy(32) || 1096 !FT->getParamType(0)->isIntegerTy()) 1097 return 0; 1098 1099 Value *Op = CI->getArgOperand(0); 1100 1101 // Constant fold. 1102 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op)) { 1103 if (CI->getValue() == 0) // ffs(0) -> 0. 1104 return Constant::getNullValue(CI->getType()); 1105 // ffs(c) -> cttz(c)+1 1106 return B.getInt32(CI->getValue().countTrailingZeros() + 1); 1107 } 1108 1109 // ffs(x) -> x != 0 ? (i32)llvm.cttz(x)+1 : 0 1110 Type *ArgType = Op->getType(); 1111 Value *F = Intrinsic::getDeclaration(Callee->getParent(), 1112 Intrinsic::cttz, ArgType); 1113 Value *V = B.CreateCall2(F, Op, B.getFalse(), "cttz"); 1114 V = B.CreateAdd(V, ConstantInt::get(V->getType(), 1)); 1115 V = B.CreateIntCast(V, B.getInt32Ty(), false); 1116 1117 Value *Cond = B.CreateICmpNE(Op, Constant::getNullValue(ArgType)); 1118 return B.CreateSelect(Cond, V, B.getInt32(0)); 1119 } 1120}; 1121 1122//===---------------------------------------===// 1123// 'isdigit' Optimizations 1124 1125struct IsDigitOpt : public LibCallOptimization { 1126 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 1127 FunctionType *FT = Callee->getFunctionType(); 1128 // We require integer(i32) 1129 if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() || 1130 !FT->getParamType(0)->isIntegerTy(32)) 1131 return 0; 1132 1133 // isdigit(c) -> (c-'0') <u 10 1134 Value *Op = CI->getArgOperand(0); 1135 Op = B.CreateSub(Op, B.getInt32('0'), "isdigittmp"); 1136 Op = B.CreateICmpULT(Op, B.getInt32(10), "isdigit"); 1137 return B.CreateZExt(Op, CI->getType()); 1138 } 1139}; 1140 1141//===---------------------------------------===// 1142// 'isascii' Optimizations 1143 1144struct IsAsciiOpt : public LibCallOptimization { 1145 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 1146 FunctionType *FT = Callee->getFunctionType(); 1147 // We require integer(i32) 1148 if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() || 1149 !FT->getParamType(0)->isIntegerTy(32)) 1150 return 0; 1151 1152 // isascii(c) -> c <u 128 1153 Value *Op = CI->getArgOperand(0); 1154 Op = B.CreateICmpULT(Op, B.getInt32(128), "isascii"); 1155 return B.CreateZExt(Op, CI->getType()); 1156 } 1157}; 1158 1159//===---------------------------------------===// 1160// 'abs', 'labs', 'llabs' Optimizations 1161 1162struct AbsOpt : public LibCallOptimization { 1163 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 1164 FunctionType *FT = Callee->getFunctionType(); 1165 // We require integer(integer) where the types agree. 1166 if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() || 1167 FT->getParamType(0) != FT->getReturnType()) 1168 return 0; 1169 1170 // abs(x) -> x >s -1 ? x : -x 1171 Value *Op = CI->getArgOperand(0); 1172 Value *Pos = B.CreateICmpSGT(Op, Constant::getAllOnesValue(Op->getType()), 1173 "ispos"); 1174 Value *Neg = B.CreateNeg(Op, "neg"); 1175 return B.CreateSelect(Pos, Op, Neg); 1176 } 1177}; 1178 1179 1180//===---------------------------------------===// 1181// 'toascii' Optimizations 1182 1183struct ToAsciiOpt : public LibCallOptimization { 1184 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 1185 FunctionType *FT = Callee->getFunctionType(); 1186 // We require i32(i32) 1187 if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) || 1188 !FT->getParamType(0)->isIntegerTy(32)) 1189 return 0; 1190 1191 // isascii(c) -> c & 0x7f 1192 return B.CreateAnd(CI->getArgOperand(0), 1193 ConstantInt::get(CI->getType(),0x7F)); 1194 } 1195}; 1196 1197//===----------------------------------------------------------------------===// 1198// Formatting and IO Optimizations 1199//===----------------------------------------------------------------------===// 1200 1201//===---------------------------------------===// 1202// 'printf' Optimizations 1203 1204struct PrintFOpt : public LibCallOptimization { 1205 Value *OptimizeFixedFormatString(Function *Callee, CallInst *CI, 1206 IRBuilder<> &B) { 1207 // Check for a fixed format string. 1208 StringRef FormatStr; 1209 if (!getConstantStringInfo(CI->getArgOperand(0), FormatStr)) 1210 return 0; 1211 1212 // Empty format string -> noop. 1213 if (FormatStr.empty()) // Tolerate printf's declared void. 1214 return CI->use_empty() ? (Value*)CI : 1215 ConstantInt::get(CI->getType(), 0); 1216 1217 // Do not do any of the following transformations if the printf return value 1218 // is used, in general the printf return value is not compatible with either 1219 // putchar() or puts(). 1220 if (!CI->use_empty()) 1221 return 0; 1222 1223 // printf("x") -> putchar('x'), even for '%'. 1224 if (FormatStr.size() == 1) { 1225 Value *Res = EmitPutChar(B.getInt32(FormatStr[0]), B, TD, TLI); 1226 if (CI->use_empty() || !Res) return Res; 1227 return B.CreateIntCast(Res, CI->getType(), true); 1228 } 1229 1230 // printf("foo\n") --> puts("foo") 1231 if (FormatStr[FormatStr.size()-1] == '\n' && 1232 FormatStr.find('%') == std::string::npos) { // no format characters. 1233 // Create a string literal with no \n on it. We expect the constant merge 1234 // pass to be run after this pass, to merge duplicate strings. 1235 FormatStr = FormatStr.drop_back(); 1236 Value *GV = B.CreateGlobalString(FormatStr, "str"); 1237 Value *NewCI = EmitPutS(GV, B, TD, TLI); 1238 return (CI->use_empty() || !NewCI) ? 1239 NewCI : 1240 ConstantInt::get(CI->getType(), FormatStr.size()+1); 1241 } 1242 1243 // Optimize specific format strings. 1244 // printf("%c", chr) --> putchar(chr) 1245 if (FormatStr == "%c" && CI->getNumArgOperands() > 1 && 1246 CI->getArgOperand(1)->getType()->isIntegerTy()) { 1247 Value *Res = EmitPutChar(CI->getArgOperand(1), B, TD, TLI); 1248 1249 if (CI->use_empty() || !Res) return Res; 1250 return B.CreateIntCast(Res, CI->getType(), true); 1251 } 1252 1253 // printf("%s\n", str) --> puts(str) 1254 if (FormatStr == "%s\n" && CI->getNumArgOperands() > 1 && 1255 CI->getArgOperand(1)->getType()->isPointerTy()) { 1256 return EmitPutS(CI->getArgOperand(1), B, TD, TLI); 1257 } 1258 return 0; 1259 } 1260 1261 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 1262 // Require one fixed pointer argument and an integer/void result. 1263 FunctionType *FT = Callee->getFunctionType(); 1264 if (FT->getNumParams() < 1 || !FT->getParamType(0)->isPointerTy() || 1265 !(FT->getReturnType()->isIntegerTy() || 1266 FT->getReturnType()->isVoidTy())) 1267 return 0; 1268 1269 if (Value *V = OptimizeFixedFormatString(Callee, CI, B)) { 1270 return V; 1271 } 1272 1273 // printf(format, ...) -> iprintf(format, ...) if no floating point 1274 // arguments. 1275 if (TLI->has(LibFunc::iprintf) && !CallHasFloatingPointArgument(CI)) { 1276 Module *M = B.GetInsertBlock()->getParent()->getParent(); 1277 Constant *IPrintFFn = 1278 M->getOrInsertFunction("iprintf", FT, Callee->getAttributes()); 1279 CallInst *New = cast<CallInst>(CI->clone()); 1280 New->setCalledFunction(IPrintFFn); 1281 B.Insert(New); 1282 return New; 1283 } 1284 return 0; 1285 } 1286}; 1287 1288//===---------------------------------------===// 1289// 'sprintf' Optimizations 1290 1291struct SPrintFOpt : public LibCallOptimization { 1292 Value *OptimizeFixedFormatString(Function *Callee, CallInst *CI, 1293 IRBuilder<> &B) { 1294 // Check for a fixed format string. 1295 StringRef FormatStr; 1296 if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr)) 1297 return 0; 1298 1299 // If we just have a format string (nothing else crazy) transform it. 1300 if (CI->getNumArgOperands() == 2) { 1301 // Make sure there's no % in the constant array. We could try to handle 1302 // %% -> % in the future if we cared. 1303 for (unsigned i = 0, e = FormatStr.size(); i != e; ++i) 1304 if (FormatStr[i] == '%') 1305 return 0; // we found a format specifier, bail out. 1306 1307 // These optimizations require TargetData. 1308 if (!TD) return 0; 1309 1310 // sprintf(str, fmt) -> llvm.memcpy(str, fmt, strlen(fmt)+1, 1) 1311 B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1), 1312 ConstantInt::get(TD->getIntPtrType(*Context), // Copy the 1313 FormatStr.size() + 1), 1); // nul byte. 1314 return ConstantInt::get(CI->getType(), FormatStr.size()); 1315 } 1316 1317 // The remaining optimizations require the format string to be "%s" or "%c" 1318 // and have an extra operand. 1319 if (FormatStr.size() != 2 || FormatStr[0] != '%' || 1320 CI->getNumArgOperands() < 3) 1321 return 0; 1322 1323 // Decode the second character of the format string. 1324 if (FormatStr[1] == 'c') { 1325 // sprintf(dst, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0 1326 if (!CI->getArgOperand(2)->getType()->isIntegerTy()) return 0; 1327 Value *V = B.CreateTrunc(CI->getArgOperand(2), B.getInt8Ty(), "char"); 1328 Value *Ptr = CastToCStr(CI->getArgOperand(0), B); 1329 B.CreateStore(V, Ptr); 1330 Ptr = B.CreateGEP(Ptr, B.getInt32(1), "nul"); 1331 B.CreateStore(B.getInt8(0), Ptr); 1332 1333 return ConstantInt::get(CI->getType(), 1); 1334 } 1335 1336 if (FormatStr[1] == 's') { 1337 // These optimizations require TargetData. 1338 if (!TD) return 0; 1339 1340 // sprintf(dest, "%s", str) -> llvm.memcpy(dest, str, strlen(str)+1, 1) 1341 if (!CI->getArgOperand(2)->getType()->isPointerTy()) return 0; 1342 1343 Value *Len = EmitStrLen(CI->getArgOperand(2), B, TD, TLI); 1344 if (!Len) 1345 return 0; 1346 Value *IncLen = B.CreateAdd(Len, 1347 ConstantInt::get(Len->getType(), 1), 1348 "leninc"); 1349 B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(2), IncLen, 1); 1350 1351 // The sprintf result is the unincremented number of bytes in the string. 1352 return B.CreateIntCast(Len, CI->getType(), false); 1353 } 1354 return 0; 1355 } 1356 1357 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 1358 // Require two fixed pointer arguments and an integer result. 1359 FunctionType *FT = Callee->getFunctionType(); 1360 if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() || 1361 !FT->getParamType(1)->isPointerTy() || 1362 !FT->getReturnType()->isIntegerTy()) 1363 return 0; 1364 1365 if (Value *V = OptimizeFixedFormatString(Callee, CI, B)) { 1366 return V; 1367 } 1368 1369 // sprintf(str, format, ...) -> siprintf(str, format, ...) if no floating 1370 // point arguments. 1371 if (TLI->has(LibFunc::siprintf) && !CallHasFloatingPointArgument(CI)) { 1372 Module *M = B.GetInsertBlock()->getParent()->getParent(); 1373 Constant *SIPrintFFn = 1374 M->getOrInsertFunction("siprintf", FT, Callee->getAttributes()); 1375 CallInst *New = cast<CallInst>(CI->clone()); 1376 New->setCalledFunction(SIPrintFFn); 1377 B.Insert(New); 1378 return New; 1379 } 1380 return 0; 1381 } 1382}; 1383 1384//===---------------------------------------===// 1385// 'fwrite' Optimizations 1386 1387struct FWriteOpt : public LibCallOptimization { 1388 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 1389 // Require a pointer, an integer, an integer, a pointer, returning integer. 1390 FunctionType *FT = Callee->getFunctionType(); 1391 if (FT->getNumParams() != 4 || !FT->getParamType(0)->isPointerTy() || 1392 !FT->getParamType(1)->isIntegerTy() || 1393 !FT->getParamType(2)->isIntegerTy() || 1394 !FT->getParamType(3)->isPointerTy() || 1395 !FT->getReturnType()->isIntegerTy()) 1396 return 0; 1397 1398 // Get the element size and count. 1399 ConstantInt *SizeC = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 1400 ConstantInt *CountC = dyn_cast<ConstantInt>(CI->getArgOperand(2)); 1401 if (!SizeC || !CountC) return 0; 1402 uint64_t Bytes = SizeC->getZExtValue()*CountC->getZExtValue(); 1403 1404 // If this is writing zero records, remove the call (it's a noop). 1405 if (Bytes == 0) 1406 return ConstantInt::get(CI->getType(), 0); 1407 1408 // If this is writing one byte, turn it into fputc. 1409 // This optimisation is only valid, if the return value is unused. 1410 if (Bytes == 1 && CI->use_empty()) { // fwrite(S,1,1,F) -> fputc(S[0],F) 1411 Value *Char = B.CreateLoad(CastToCStr(CI->getArgOperand(0), B), "char"); 1412 Value *NewCI = EmitFPutC(Char, CI->getArgOperand(3), B, TD, TLI); 1413 return NewCI ? ConstantInt::get(CI->getType(), 1) : 0; 1414 } 1415 1416 return 0; 1417 } 1418}; 1419 1420//===---------------------------------------===// 1421// 'fputs' Optimizations 1422 1423struct FPutsOpt : public LibCallOptimization { 1424 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 1425 // These optimizations require TargetData. 1426 if (!TD) return 0; 1427 1428 // Require two pointers. Also, we can't optimize if return value is used. 1429 FunctionType *FT = Callee->getFunctionType(); 1430 if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() || 1431 !FT->getParamType(1)->isPointerTy() || 1432 !CI->use_empty()) 1433 return 0; 1434 1435 // fputs(s,F) --> fwrite(s,1,strlen(s),F) 1436 uint64_t Len = GetStringLength(CI->getArgOperand(0)); 1437 if (!Len) return 0; 1438 // Known to have no uses (see above). 1439 return EmitFWrite(CI->getArgOperand(0), 1440 ConstantInt::get(TD->getIntPtrType(*Context), Len-1), 1441 CI->getArgOperand(1), B, TD, TLI); 1442 } 1443}; 1444 1445//===---------------------------------------===// 1446// 'fprintf' Optimizations 1447 1448struct FPrintFOpt : public LibCallOptimization { 1449 Value *OptimizeFixedFormatString(Function *Callee, CallInst *CI, 1450 IRBuilder<> &B) { 1451 // All the optimizations depend on the format string. 1452 StringRef FormatStr; 1453 if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr)) 1454 return 0; 1455 1456 // fprintf(F, "foo") --> fwrite("foo", 3, 1, F) 1457 if (CI->getNumArgOperands() == 2) { 1458 for (unsigned i = 0, e = FormatStr.size(); i != e; ++i) 1459 if (FormatStr[i] == '%') // Could handle %% -> % if we cared. 1460 return 0; // We found a format specifier. 1461 1462 // These optimizations require TargetData. 1463 if (!TD) return 0; 1464 1465 Value *NewCI = EmitFWrite(CI->getArgOperand(1), 1466 ConstantInt::get(TD->getIntPtrType(*Context), 1467 FormatStr.size()), 1468 CI->getArgOperand(0), B, TD, TLI); 1469 return NewCI ? ConstantInt::get(CI->getType(), FormatStr.size()) : 0; 1470 } 1471 1472 // The remaining optimizations require the format string to be "%s" or "%c" 1473 // and have an extra operand. 1474 if (FormatStr.size() != 2 || FormatStr[0] != '%' || 1475 CI->getNumArgOperands() < 3) 1476 return 0; 1477 1478 // Decode the second character of the format string. 1479 if (FormatStr[1] == 'c') { 1480 // fprintf(F, "%c", chr) --> fputc(chr, F) 1481 if (!CI->getArgOperand(2)->getType()->isIntegerTy()) return 0; 1482 Value *NewCI = EmitFPutC(CI->getArgOperand(2), CI->getArgOperand(0), B, 1483 TD, TLI); 1484 return NewCI ? ConstantInt::get(CI->getType(), 1) : 0; 1485 } 1486 1487 if (FormatStr[1] == 's') { 1488 // fprintf(F, "%s", str) --> fputs(str, F) 1489 if (!CI->getArgOperand(2)->getType()->isPointerTy() || !CI->use_empty()) 1490 return 0; 1491 return EmitFPutS(CI->getArgOperand(2), CI->getArgOperand(0), B, TD, TLI); 1492 } 1493 return 0; 1494 } 1495 1496 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 1497 // Require two fixed paramters as pointers and integer result. 1498 FunctionType *FT = Callee->getFunctionType(); 1499 if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() || 1500 !FT->getParamType(1)->isPointerTy() || 1501 !FT->getReturnType()->isIntegerTy()) 1502 return 0; 1503 1504 if (Value *V = OptimizeFixedFormatString(Callee, CI, B)) { 1505 return V; 1506 } 1507 1508 // fprintf(stream, format, ...) -> fiprintf(stream, format, ...) if no 1509 // floating point arguments. 1510 if (TLI->has(LibFunc::fiprintf) && !CallHasFloatingPointArgument(CI)) { 1511 Module *M = B.GetInsertBlock()->getParent()->getParent(); 1512 Constant *FIPrintFFn = 1513 M->getOrInsertFunction("fiprintf", FT, Callee->getAttributes()); 1514 CallInst *New = cast<CallInst>(CI->clone()); 1515 New->setCalledFunction(FIPrintFFn); 1516 B.Insert(New); 1517 return New; 1518 } 1519 return 0; 1520 } 1521}; 1522 1523//===---------------------------------------===// 1524// 'puts' Optimizations 1525 1526struct PutsOpt : public LibCallOptimization { 1527 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { 1528 // Require one fixed pointer argument and an integer/void result. 1529 FunctionType *FT = Callee->getFunctionType(); 1530 if (FT->getNumParams() < 1 || !FT->getParamType(0)->isPointerTy() || 1531 !(FT->getReturnType()->isIntegerTy() || 1532 FT->getReturnType()->isVoidTy())) 1533 return 0; 1534 1535 // Check for a constant string. 1536 StringRef Str; 1537 if (!getConstantStringInfo(CI->getArgOperand(0), Str)) 1538 return 0; 1539 1540 if (Str.empty() && CI->use_empty()) { 1541 // puts("") -> putchar('\n') 1542 Value *Res = EmitPutChar(B.getInt32('\n'), B, TD, TLI); 1543 if (CI->use_empty() || !Res) return Res; 1544 return B.CreateIntCast(Res, CI->getType(), true); 1545 } 1546 1547 return 0; 1548 } 1549}; 1550 1551} // end anonymous namespace. 1552 1553//===----------------------------------------------------------------------===// 1554// SimplifyLibCalls Pass Implementation 1555//===----------------------------------------------------------------------===// 1556 1557namespace { 1558 /// This pass optimizes well known library functions from libc and libm. 1559 /// 1560 class SimplifyLibCalls : public FunctionPass { 1561 TargetLibraryInfo *TLI; 1562 1563 StringMap<LibCallOptimization*> Optimizations; 1564 // String and Memory LibCall Optimizations 1565 StrCatOpt StrCat; StrNCatOpt StrNCat; StrChrOpt StrChr; StrRChrOpt StrRChr; 1566 StrCmpOpt StrCmp; StrNCmpOpt StrNCmp; 1567 StrCpyOpt StrCpy; StrCpyOpt StrCpyChk; 1568 StpCpyOpt StpCpy; StpCpyOpt StpCpyChk; 1569 StrNCpyOpt StrNCpy; 1570 StrLenOpt StrLen; StrPBrkOpt StrPBrk; 1571 StrToOpt StrTo; StrSpnOpt StrSpn; StrCSpnOpt StrCSpn; StrStrOpt StrStr; 1572 MemCmpOpt MemCmp; MemCpyOpt MemCpy; MemMoveOpt MemMove; MemSetOpt MemSet; 1573 // Math Library Optimizations 1574 CosOpt Cos; PowOpt Pow; Exp2Opt Exp2; 1575 UnaryDoubleFPOpt UnaryDoubleFP, UnsafeUnaryDoubleFP; 1576 // Integer Optimizations 1577 FFSOpt FFS; AbsOpt Abs; IsDigitOpt IsDigit; IsAsciiOpt IsAscii; 1578 ToAsciiOpt ToAscii; 1579 // Formatting and IO Optimizations 1580 SPrintFOpt SPrintF; PrintFOpt PrintF; 1581 FWriteOpt FWrite; FPutsOpt FPuts; FPrintFOpt FPrintF; 1582 PutsOpt Puts; 1583 1584 bool Modified; // This is only used by doInitialization. 1585 public: 1586 static char ID; // Pass identification 1587 SimplifyLibCalls() : FunctionPass(ID), StrCpy(false), StrCpyChk(true), 1588 StpCpy(false), StpCpyChk(true), 1589 UnaryDoubleFP(false), UnsafeUnaryDoubleFP(true) { 1590 initializeSimplifyLibCallsPass(*PassRegistry::getPassRegistry()); 1591 } 1592 void AddOpt(LibFunc::Func F, LibCallOptimization* Opt); 1593 void AddOpt(LibFunc::Func F1, LibFunc::Func F2, LibCallOptimization* Opt); 1594 1595 void InitOptimizations(); 1596 bool runOnFunction(Function &F); 1597 1598 void setDoesNotAccessMemory(Function &F); 1599 void setOnlyReadsMemory(Function &F); 1600 void setDoesNotThrow(Function &F); 1601 void setDoesNotCapture(Function &F, unsigned n); 1602 void setDoesNotAlias(Function &F, unsigned n); 1603 bool doInitialization(Module &M); 1604 1605 void inferPrototypeAttributes(Function &F); 1606 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 1607 AU.addRequired<TargetLibraryInfo>(); 1608 } 1609 }; 1610} // end anonymous namespace. 1611 1612char SimplifyLibCalls::ID = 0; 1613 1614INITIALIZE_PASS_BEGIN(SimplifyLibCalls, "simplify-libcalls", 1615 "Simplify well-known library calls", false, false) 1616INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 1617INITIALIZE_PASS_END(SimplifyLibCalls, "simplify-libcalls", 1618 "Simplify well-known library calls", false, false) 1619 1620// Public interface to the Simplify LibCalls pass. 1621FunctionPass *llvm::createSimplifyLibCallsPass() { 1622 return new SimplifyLibCalls(); 1623} 1624 1625void SimplifyLibCalls::AddOpt(LibFunc::Func F, LibCallOptimization* Opt) { 1626 if (TLI->has(F)) 1627 Optimizations[TLI->getName(F)] = Opt; 1628} 1629 1630void SimplifyLibCalls::AddOpt(LibFunc::Func F1, LibFunc::Func F2, 1631 LibCallOptimization* Opt) { 1632 if (TLI->has(F1) && TLI->has(F2)) 1633 Optimizations[TLI->getName(F1)] = Opt; 1634} 1635 1636/// Optimizations - Populate the Optimizations map with all the optimizations 1637/// we know. 1638void SimplifyLibCalls::InitOptimizations() { 1639 // String and Memory LibCall Optimizations 1640 Optimizations["strcat"] = &StrCat; 1641 Optimizations["strncat"] = &StrNCat; 1642 Optimizations["strchr"] = &StrChr; 1643 Optimizations["strrchr"] = &StrRChr; 1644 Optimizations["strcmp"] = &StrCmp; 1645 Optimizations["strncmp"] = &StrNCmp; 1646 Optimizations["strcpy"] = &StrCpy; 1647 Optimizations["strncpy"] = &StrNCpy; 1648 Optimizations["stpcpy"] = &StpCpy; 1649 Optimizations["strlen"] = &StrLen; 1650 Optimizations["strpbrk"] = &StrPBrk; 1651 Optimizations["strtol"] = &StrTo; 1652 Optimizations["strtod"] = &StrTo; 1653 Optimizations["strtof"] = &StrTo; 1654 Optimizations["strtoul"] = &StrTo; 1655 Optimizations["strtoll"] = &StrTo; 1656 Optimizations["strtold"] = &StrTo; 1657 Optimizations["strtoull"] = &StrTo; 1658 Optimizations["strspn"] = &StrSpn; 1659 Optimizations["strcspn"] = &StrCSpn; 1660 Optimizations["strstr"] = &StrStr; 1661 Optimizations["memcmp"] = &MemCmp; 1662 AddOpt(LibFunc::memcpy, &MemCpy); 1663 Optimizations["memmove"] = &MemMove; 1664 AddOpt(LibFunc::memset, &MemSet); 1665 1666 // _chk variants of String and Memory LibCall Optimizations. 1667 Optimizations["__strcpy_chk"] = &StrCpyChk; 1668 Optimizations["__stpcpy_chk"] = &StpCpyChk; 1669 1670 // Math Library Optimizations 1671 Optimizations["cosf"] = &Cos; 1672 Optimizations["cos"] = &Cos; 1673 Optimizations["cosl"] = &Cos; 1674 Optimizations["powf"] = &Pow; 1675 Optimizations["pow"] = &Pow; 1676 Optimizations["powl"] = &Pow; 1677 Optimizations["llvm.pow.f32"] = &Pow; 1678 Optimizations["llvm.pow.f64"] = &Pow; 1679 Optimizations["llvm.pow.f80"] = &Pow; 1680 Optimizations["llvm.pow.f128"] = &Pow; 1681 Optimizations["llvm.pow.ppcf128"] = &Pow; 1682 Optimizations["exp2l"] = &Exp2; 1683 Optimizations["exp2"] = &Exp2; 1684 Optimizations["exp2f"] = &Exp2; 1685 Optimizations["llvm.exp2.ppcf128"] = &Exp2; 1686 Optimizations["llvm.exp2.f128"] = &Exp2; 1687 Optimizations["llvm.exp2.f80"] = &Exp2; 1688 Optimizations["llvm.exp2.f64"] = &Exp2; 1689 Optimizations["llvm.exp2.f32"] = &Exp2; 1690 1691 AddOpt(LibFunc::ceil, LibFunc::ceilf, &UnaryDoubleFP); 1692 AddOpt(LibFunc::fabs, LibFunc::fabsf, &UnaryDoubleFP); 1693 AddOpt(LibFunc::floor, LibFunc::floorf, &UnaryDoubleFP); 1694 AddOpt(LibFunc::rint, LibFunc::rintf, &UnaryDoubleFP); 1695 AddOpt(LibFunc::round, LibFunc::roundf, &UnaryDoubleFP); 1696 AddOpt(LibFunc::nearbyint, LibFunc::nearbyintf, &UnaryDoubleFP); 1697 AddOpt(LibFunc::trunc, LibFunc::truncf, &UnaryDoubleFP); 1698 1699 if(UnsafeFPShrink) { 1700 AddOpt(LibFunc::acos, LibFunc::acosf, &UnsafeUnaryDoubleFP); 1701 AddOpt(LibFunc::acosh, LibFunc::acoshf, &UnsafeUnaryDoubleFP); 1702 AddOpt(LibFunc::asin, LibFunc::asinf, &UnsafeUnaryDoubleFP); 1703 AddOpt(LibFunc::asinh, LibFunc::asinhf, &UnsafeUnaryDoubleFP); 1704 AddOpt(LibFunc::atan, LibFunc::atanf, &UnsafeUnaryDoubleFP); 1705 AddOpt(LibFunc::atanh, LibFunc::atanhf, &UnsafeUnaryDoubleFP); 1706 AddOpt(LibFunc::cbrt, LibFunc::cbrtf, &UnsafeUnaryDoubleFP); 1707 AddOpt(LibFunc::cosh, LibFunc::coshf, &UnsafeUnaryDoubleFP); 1708 AddOpt(LibFunc::exp, LibFunc::expf, &UnsafeUnaryDoubleFP); 1709 AddOpt(LibFunc::exp10, LibFunc::exp10f, &UnsafeUnaryDoubleFP); 1710 AddOpt(LibFunc::expm1, LibFunc::expm1f, &UnsafeUnaryDoubleFP); 1711 AddOpt(LibFunc::log, LibFunc::logf, &UnsafeUnaryDoubleFP); 1712 AddOpt(LibFunc::log10, LibFunc::log10f, &UnsafeUnaryDoubleFP); 1713 AddOpt(LibFunc::log1p, LibFunc::log1pf, &UnsafeUnaryDoubleFP); 1714 AddOpt(LibFunc::log2, LibFunc::log2f, &UnsafeUnaryDoubleFP); 1715 AddOpt(LibFunc::logb, LibFunc::logbf, &UnsafeUnaryDoubleFP); 1716 AddOpt(LibFunc::sin, LibFunc::sinf, &UnsafeUnaryDoubleFP); 1717 AddOpt(LibFunc::sinh, LibFunc::sinhf, &UnsafeUnaryDoubleFP); 1718 AddOpt(LibFunc::sqrt, LibFunc::sqrtf, &UnsafeUnaryDoubleFP); 1719 AddOpt(LibFunc::tan, LibFunc::tanf, &UnsafeUnaryDoubleFP); 1720 AddOpt(LibFunc::tanh, LibFunc::tanhf, &UnsafeUnaryDoubleFP); 1721 } 1722 1723 // Integer Optimizations 1724 Optimizations["ffs"] = &FFS; 1725 Optimizations["ffsl"] = &FFS; 1726 Optimizations["ffsll"] = &FFS; 1727 Optimizations["abs"] = &Abs; 1728 Optimizations["labs"] = &Abs; 1729 Optimizations["llabs"] = &Abs; 1730 Optimizations["isdigit"] = &IsDigit; 1731 Optimizations["isascii"] = &IsAscii; 1732 Optimizations["toascii"] = &ToAscii; 1733 1734 // Formatting and IO Optimizations 1735 Optimizations["sprintf"] = &SPrintF; 1736 Optimizations["printf"] = &PrintF; 1737 AddOpt(LibFunc::fwrite, &FWrite); 1738 AddOpt(LibFunc::fputs, &FPuts); 1739 Optimizations["fprintf"] = &FPrintF; 1740 Optimizations["puts"] = &Puts; 1741} 1742 1743 1744/// runOnFunction - Top level algorithm. 1745/// 1746bool SimplifyLibCalls::runOnFunction(Function &F) { 1747 TLI = &getAnalysis<TargetLibraryInfo>(); 1748 1749 if (Optimizations.empty()) 1750 InitOptimizations(); 1751 1752 const TargetData *TD = getAnalysisIfAvailable<TargetData>(); 1753 1754 IRBuilder<> Builder(F.getContext()); 1755 1756 bool Changed = false; 1757 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 1758 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 1759 // Ignore non-calls. 1760 CallInst *CI = dyn_cast<CallInst>(I++); 1761 if (!CI) continue; 1762 1763 // Ignore indirect calls and calls to non-external functions. 1764 Function *Callee = CI->getCalledFunction(); 1765 if (Callee == 0 || !Callee->isDeclaration() || 1766 !(Callee->hasExternalLinkage() || Callee->hasDLLImportLinkage())) 1767 continue; 1768 1769 // Ignore unknown calls. 1770 LibCallOptimization *LCO = Optimizations.lookup(Callee->getName()); 1771 if (!LCO) continue; 1772 1773 // Set the builder to the instruction after the call. 1774 Builder.SetInsertPoint(BB, I); 1775 1776 // Use debug location of CI for all new instructions. 1777 Builder.SetCurrentDebugLocation(CI->getDebugLoc()); 1778 1779 // Try to optimize this call. 1780 Value *Result = LCO->OptimizeCall(CI, TD, TLI, Builder); 1781 if (Result == 0) continue; 1782 1783 DEBUG(dbgs() << "SimplifyLibCalls simplified: " << *CI; 1784 dbgs() << " into: " << *Result << "\n"); 1785 1786 // Something changed! 1787 Changed = true; 1788 ++NumSimplified; 1789 1790 // Inspect the instruction after the call (which was potentially just 1791 // added) next. 1792 I = CI; ++I; 1793 1794 if (CI != Result && !CI->use_empty()) { 1795 CI->replaceAllUsesWith(Result); 1796 if (!Result->hasName()) 1797 Result->takeName(CI); 1798 } 1799 CI->eraseFromParent(); 1800 } 1801 } 1802 return Changed; 1803} 1804 1805// Utility methods for doInitialization. 1806 1807void SimplifyLibCalls::setDoesNotAccessMemory(Function &F) { 1808 if (!F.doesNotAccessMemory()) { 1809 F.setDoesNotAccessMemory(); 1810 ++NumAnnotated; 1811 Modified = true; 1812 } 1813} 1814void SimplifyLibCalls::setOnlyReadsMemory(Function &F) { 1815 if (!F.onlyReadsMemory()) { 1816 F.setOnlyReadsMemory(); 1817 ++NumAnnotated; 1818 Modified = true; 1819 } 1820} 1821void SimplifyLibCalls::setDoesNotThrow(Function &F) { 1822 if (!F.doesNotThrow()) { 1823 F.setDoesNotThrow(); 1824 ++NumAnnotated; 1825 Modified = true; 1826 } 1827} 1828void SimplifyLibCalls::setDoesNotCapture(Function &F, unsigned n) { 1829 if (!F.doesNotCapture(n)) { 1830 F.setDoesNotCapture(n); 1831 ++NumAnnotated; 1832 Modified = true; 1833 } 1834} 1835void SimplifyLibCalls::setDoesNotAlias(Function &F, unsigned n) { 1836 if (!F.doesNotAlias(n)) { 1837 F.setDoesNotAlias(n); 1838 ++NumAnnotated; 1839 Modified = true; 1840 } 1841} 1842 1843 1844void SimplifyLibCalls::inferPrototypeAttributes(Function &F) { 1845 FunctionType *FTy = F.getFunctionType(); 1846 1847 StringRef Name = F.getName(); 1848 switch (Name[0]) { 1849 case 's': 1850 if (Name == "strlen") { 1851 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 1852 return; 1853 setOnlyReadsMemory(F); 1854 setDoesNotThrow(F); 1855 setDoesNotCapture(F, 1); 1856 } else if (Name == "strchr" || 1857 Name == "strrchr") { 1858 if (FTy->getNumParams() != 2 || 1859 !FTy->getParamType(0)->isPointerTy() || 1860 !FTy->getParamType(1)->isIntegerTy()) 1861 return; 1862 setOnlyReadsMemory(F); 1863 setDoesNotThrow(F); 1864 } else if (Name == "strcpy" || 1865 Name == "stpcpy" || 1866 Name == "strcat" || 1867 Name == "strtol" || 1868 Name == "strtod" || 1869 Name == "strtof" || 1870 Name == "strtoul" || 1871 Name == "strtoll" || 1872 Name == "strtold" || 1873 Name == "strncat" || 1874 Name == "strncpy" || 1875 Name == "stpncpy" || 1876 Name == "strtoull") { 1877 if (FTy->getNumParams() < 2 || 1878 !FTy->getParamType(1)->isPointerTy()) 1879 return; 1880 setDoesNotThrow(F); 1881 setDoesNotCapture(F, 2); 1882 } else if (Name == "strxfrm") { 1883 if (FTy->getNumParams() != 3 || 1884 !FTy->getParamType(0)->isPointerTy() || 1885 !FTy->getParamType(1)->isPointerTy()) 1886 return; 1887 setDoesNotThrow(F); 1888 setDoesNotCapture(F, 1); 1889 setDoesNotCapture(F, 2); 1890 } else if (Name == "strcmp" || 1891 Name == "strspn" || 1892 Name == "strncmp" || 1893 Name == "strcspn" || 1894 Name == "strcoll" || 1895 Name == "strcasecmp" || 1896 Name == "strncasecmp") { 1897 if (FTy->getNumParams() < 2 || 1898 !FTy->getParamType(0)->isPointerTy() || 1899 !FTy->getParamType(1)->isPointerTy()) 1900 return; 1901 setOnlyReadsMemory(F); 1902 setDoesNotThrow(F); 1903 setDoesNotCapture(F, 1); 1904 setDoesNotCapture(F, 2); 1905 } else if (Name == "strstr" || 1906 Name == "strpbrk") { 1907 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) 1908 return; 1909 setOnlyReadsMemory(F); 1910 setDoesNotThrow(F); 1911 setDoesNotCapture(F, 2); 1912 } else if (Name == "strtok" || 1913 Name == "strtok_r") { 1914 if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy()) 1915 return; 1916 setDoesNotThrow(F); 1917 setDoesNotCapture(F, 2); 1918 } else if (Name == "scanf" || 1919 Name == "setbuf" || 1920 Name == "setvbuf") { 1921 if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy()) 1922 return; 1923 setDoesNotThrow(F); 1924 setDoesNotCapture(F, 1); 1925 } else if (Name == "strdup" || 1926 Name == "strndup") { 1927 if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() || 1928 !FTy->getParamType(0)->isPointerTy()) 1929 return; 1930 setDoesNotThrow(F); 1931 setDoesNotAlias(F, 0); 1932 setDoesNotCapture(F, 1); 1933 } else if (Name == "stat" || 1934 Name == "sscanf" || 1935 Name == "sprintf" || 1936 Name == "statvfs") { 1937 if (FTy->getNumParams() < 2 || 1938 !FTy->getParamType(0)->isPointerTy() || 1939 !FTy->getParamType(1)->isPointerTy()) 1940 return; 1941 setDoesNotThrow(F); 1942 setDoesNotCapture(F, 1); 1943 setDoesNotCapture(F, 2); 1944 } else if (Name == "snprintf") { 1945 if (FTy->getNumParams() != 3 || 1946 !FTy->getParamType(0)->isPointerTy() || 1947 !FTy->getParamType(2)->isPointerTy()) 1948 return; 1949 setDoesNotThrow(F); 1950 setDoesNotCapture(F, 1); 1951 setDoesNotCapture(F, 3); 1952 } else if (Name == "setitimer") { 1953 if (FTy->getNumParams() != 3 || 1954 !FTy->getParamType(1)->isPointerTy() || 1955 !FTy->getParamType(2)->isPointerTy()) 1956 return; 1957 setDoesNotThrow(F); 1958 setDoesNotCapture(F, 2); 1959 setDoesNotCapture(F, 3); 1960 } else if (Name == "system") { 1961 if (FTy->getNumParams() != 1 || 1962 !FTy->getParamType(0)->isPointerTy()) 1963 return; 1964 // May throw; "system" is a valid pthread cancellation point. 1965 setDoesNotCapture(F, 1); 1966 } 1967 break; 1968 case 'm': 1969 if (Name == "malloc") { 1970 if (FTy->getNumParams() != 1 || 1971 !FTy->getReturnType()->isPointerTy()) 1972 return; 1973 setDoesNotThrow(F); 1974 setDoesNotAlias(F, 0); 1975 } else if (Name == "memcmp") { 1976 if (FTy->getNumParams() != 3 || 1977 !FTy->getParamType(0)->isPointerTy() || 1978 !FTy->getParamType(1)->isPointerTy()) 1979 return; 1980 setOnlyReadsMemory(F); 1981 setDoesNotThrow(F); 1982 setDoesNotCapture(F, 1); 1983 setDoesNotCapture(F, 2); 1984 } else if (Name == "memchr" || 1985 Name == "memrchr") { 1986 if (FTy->getNumParams() != 3) 1987 return; 1988 setOnlyReadsMemory(F); 1989 setDoesNotThrow(F); 1990 } else if (Name == "modf" || 1991 Name == "modff" || 1992 Name == "modfl" || 1993 Name == "memcpy" || 1994 Name == "memccpy" || 1995 Name == "memmove") { 1996 if (FTy->getNumParams() < 2 || 1997 !FTy->getParamType(1)->isPointerTy()) 1998 return; 1999 setDoesNotThrow(F); 2000 setDoesNotCapture(F, 2); 2001 } else if (Name == "memalign") { 2002 if (!FTy->getReturnType()->isPointerTy()) 2003 return; 2004 setDoesNotAlias(F, 0); 2005 } else if (Name == "mkdir" || 2006 Name == "mktime") { 2007 if (FTy->getNumParams() == 0 || 2008 !FTy->getParamType(0)->isPointerTy()) 2009 return; 2010 setDoesNotThrow(F); 2011 setDoesNotCapture(F, 1); 2012 } 2013 break; 2014 case 'r': 2015 if (Name == "realloc") { 2016 if (FTy->getNumParams() != 2 || 2017 !FTy->getParamType(0)->isPointerTy() || 2018 !FTy->getReturnType()->isPointerTy()) 2019 return; 2020 setDoesNotThrow(F); 2021 setDoesNotAlias(F, 0); 2022 setDoesNotCapture(F, 1); 2023 } else if (Name == "read") { 2024 if (FTy->getNumParams() != 3 || 2025 !FTy->getParamType(1)->isPointerTy()) 2026 return; 2027 // May throw; "read" is a valid pthread cancellation point. 2028 setDoesNotCapture(F, 2); 2029 } else if (Name == "rmdir" || 2030 Name == "rewind" || 2031 Name == "remove" || 2032 Name == "realpath") { 2033 if (FTy->getNumParams() < 1 || 2034 !FTy->getParamType(0)->isPointerTy()) 2035 return; 2036 setDoesNotThrow(F); 2037 setDoesNotCapture(F, 1); 2038 } else if (Name == "rename" || 2039 Name == "readlink") { 2040 if (FTy->getNumParams() < 2 || 2041 !FTy->getParamType(0)->isPointerTy() || 2042 !FTy->getParamType(1)->isPointerTy()) 2043 return; 2044 setDoesNotThrow(F); 2045 setDoesNotCapture(F, 1); 2046 setDoesNotCapture(F, 2); 2047 } 2048 break; 2049 case 'w': 2050 if (Name == "write") { 2051 if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy()) 2052 return; 2053 // May throw; "write" is a valid pthread cancellation point. 2054 setDoesNotCapture(F, 2); 2055 } 2056 break; 2057 case 'b': 2058 if (Name == "bcopy") { 2059 if (FTy->getNumParams() != 3 || 2060 !FTy->getParamType(0)->isPointerTy() || 2061 !FTy->getParamType(1)->isPointerTy()) 2062 return; 2063 setDoesNotThrow(F); 2064 setDoesNotCapture(F, 1); 2065 setDoesNotCapture(F, 2); 2066 } else if (Name == "bcmp") { 2067 if (FTy->getNumParams() != 3 || 2068 !FTy->getParamType(0)->isPointerTy() || 2069 !FTy->getParamType(1)->isPointerTy()) 2070 return; 2071 setDoesNotThrow(F); 2072 setOnlyReadsMemory(F); 2073 setDoesNotCapture(F, 1); 2074 setDoesNotCapture(F, 2); 2075 } else if (Name == "bzero") { 2076 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy()) 2077 return; 2078 setDoesNotThrow(F); 2079 setDoesNotCapture(F, 1); 2080 } 2081 break; 2082 case 'c': 2083 if (Name == "calloc") { 2084 if (FTy->getNumParams() != 2 || 2085 !FTy->getReturnType()->isPointerTy()) 2086 return; 2087 setDoesNotThrow(F); 2088 setDoesNotAlias(F, 0); 2089 } else if (Name == "chmod" || 2090 Name == "chown" || 2091 Name == "ctermid" || 2092 Name == "clearerr" || 2093 Name == "closedir") { 2094 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy()) 2095 return; 2096 setDoesNotThrow(F); 2097 setDoesNotCapture(F, 1); 2098 } 2099 break; 2100 case 'a': 2101 if (Name == "atoi" || 2102 Name == "atol" || 2103 Name == "atof" || 2104 Name == "atoll") { 2105 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 2106 return; 2107 setDoesNotThrow(F); 2108 setOnlyReadsMemory(F); 2109 setDoesNotCapture(F, 1); 2110 } else if (Name == "access") { 2111 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy()) 2112 return; 2113 setDoesNotThrow(F); 2114 setDoesNotCapture(F, 1); 2115 } 2116 break; 2117 case 'f': 2118 if (Name == "fopen") { 2119 if (FTy->getNumParams() != 2 || 2120 !FTy->getReturnType()->isPointerTy() || 2121 !FTy->getParamType(0)->isPointerTy() || 2122 !FTy->getParamType(1)->isPointerTy()) 2123 return; 2124 setDoesNotThrow(F); 2125 setDoesNotAlias(F, 0); 2126 setDoesNotCapture(F, 1); 2127 setDoesNotCapture(F, 2); 2128 } else if (Name == "fdopen") { 2129 if (FTy->getNumParams() != 2 || 2130 !FTy->getReturnType()->isPointerTy() || 2131 !FTy->getParamType(1)->isPointerTy()) 2132 return; 2133 setDoesNotThrow(F); 2134 setDoesNotAlias(F, 0); 2135 setDoesNotCapture(F, 2); 2136 } else if (Name == "feof" || 2137 Name == "free" || 2138 Name == "fseek" || 2139 Name == "ftell" || 2140 Name == "fgetc" || 2141 Name == "fseeko" || 2142 Name == "ftello" || 2143 Name == "fileno" || 2144 Name == "fflush" || 2145 Name == "fclose" || 2146 Name == "fsetpos" || 2147 Name == "flockfile" || 2148 Name == "funlockfile" || 2149 Name == "ftrylockfile") { 2150 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy()) 2151 return; 2152 setDoesNotThrow(F); 2153 setDoesNotCapture(F, 1); 2154 } else if (Name == "ferror") { 2155 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 2156 return; 2157 setDoesNotThrow(F); 2158 setDoesNotCapture(F, 1); 2159 setOnlyReadsMemory(F); 2160 } else if (Name == "fputc" || 2161 Name == "fstat" || 2162 Name == "frexp" || 2163 Name == "frexpf" || 2164 Name == "frexpl" || 2165 Name == "fstatvfs") { 2166 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) 2167 return; 2168 setDoesNotThrow(F); 2169 setDoesNotCapture(F, 2); 2170 } else if (Name == "fgets") { 2171 if (FTy->getNumParams() != 3 || 2172 !FTy->getParamType(0)->isPointerTy() || 2173 !FTy->getParamType(2)->isPointerTy()) 2174 return; 2175 setDoesNotThrow(F); 2176 setDoesNotCapture(F, 3); 2177 } else if (Name == "fread" || 2178 Name == "fwrite") { 2179 if (FTy->getNumParams() != 4 || 2180 !FTy->getParamType(0)->isPointerTy() || 2181 !FTy->getParamType(3)->isPointerTy()) 2182 return; 2183 setDoesNotThrow(F); 2184 setDoesNotCapture(F, 1); 2185 setDoesNotCapture(F, 4); 2186 } else if (Name == "fputs" || 2187 Name == "fscanf" || 2188 Name == "fprintf" || 2189 Name == "fgetpos") { 2190 if (FTy->getNumParams() < 2 || 2191 !FTy->getParamType(0)->isPointerTy() || 2192 !FTy->getParamType(1)->isPointerTy()) 2193 return; 2194 setDoesNotThrow(F); 2195 setDoesNotCapture(F, 1); 2196 setDoesNotCapture(F, 2); 2197 } 2198 break; 2199 case 'g': 2200 if (Name == "getc" || 2201 Name == "getlogin_r" || 2202 Name == "getc_unlocked") { 2203 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy()) 2204 return; 2205 setDoesNotThrow(F); 2206 setDoesNotCapture(F, 1); 2207 } else if (Name == "getenv") { 2208 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 2209 return; 2210 setDoesNotThrow(F); 2211 setOnlyReadsMemory(F); 2212 setDoesNotCapture(F, 1); 2213 } else if (Name == "gets" || 2214 Name == "getchar") { 2215 setDoesNotThrow(F); 2216 } else if (Name == "getitimer") { 2217 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) 2218 return; 2219 setDoesNotThrow(F); 2220 setDoesNotCapture(F, 2); 2221 } else if (Name == "getpwnam") { 2222 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 2223 return; 2224 setDoesNotThrow(F); 2225 setDoesNotCapture(F, 1); 2226 } 2227 break; 2228 case 'u': 2229 if (Name == "ungetc") { 2230 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) 2231 return; 2232 setDoesNotThrow(F); 2233 setDoesNotCapture(F, 2); 2234 } else if (Name == "uname" || 2235 Name == "unlink" || 2236 Name == "unsetenv") { 2237 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 2238 return; 2239 setDoesNotThrow(F); 2240 setDoesNotCapture(F, 1); 2241 } else if (Name == "utime" || 2242 Name == "utimes") { 2243 if (FTy->getNumParams() != 2 || 2244 !FTy->getParamType(0)->isPointerTy() || 2245 !FTy->getParamType(1)->isPointerTy()) 2246 return; 2247 setDoesNotThrow(F); 2248 setDoesNotCapture(F, 1); 2249 setDoesNotCapture(F, 2); 2250 } 2251 break; 2252 case 'p': 2253 if (Name == "putc") { 2254 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) 2255 return; 2256 setDoesNotThrow(F); 2257 setDoesNotCapture(F, 2); 2258 } else if (Name == "puts" || 2259 Name == "printf" || 2260 Name == "perror") { 2261 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 2262 return; 2263 setDoesNotThrow(F); 2264 setDoesNotCapture(F, 1); 2265 } else if (Name == "pread" || 2266 Name == "pwrite") { 2267 if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy()) 2268 return; 2269 // May throw; these are valid pthread cancellation points. 2270 setDoesNotCapture(F, 2); 2271 } else if (Name == "putchar") { 2272 setDoesNotThrow(F); 2273 } else if (Name == "popen") { 2274 if (FTy->getNumParams() != 2 || 2275 !FTy->getReturnType()->isPointerTy() || 2276 !FTy->getParamType(0)->isPointerTy() || 2277 !FTy->getParamType(1)->isPointerTy()) 2278 return; 2279 setDoesNotThrow(F); 2280 setDoesNotAlias(F, 0); 2281 setDoesNotCapture(F, 1); 2282 setDoesNotCapture(F, 2); 2283 } else if (Name == "pclose") { 2284 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 2285 return; 2286 setDoesNotThrow(F); 2287 setDoesNotCapture(F, 1); 2288 } 2289 break; 2290 case 'v': 2291 if (Name == "vscanf") { 2292 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) 2293 return; 2294 setDoesNotThrow(F); 2295 setDoesNotCapture(F, 1); 2296 } else if (Name == "vsscanf" || 2297 Name == "vfscanf") { 2298 if (FTy->getNumParams() != 3 || 2299 !FTy->getParamType(1)->isPointerTy() || 2300 !FTy->getParamType(2)->isPointerTy()) 2301 return; 2302 setDoesNotThrow(F); 2303 setDoesNotCapture(F, 1); 2304 setDoesNotCapture(F, 2); 2305 } else if (Name == "valloc") { 2306 if (!FTy->getReturnType()->isPointerTy()) 2307 return; 2308 setDoesNotThrow(F); 2309 setDoesNotAlias(F, 0); 2310 } else if (Name == "vprintf") { 2311 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy()) 2312 return; 2313 setDoesNotThrow(F); 2314 setDoesNotCapture(F, 1); 2315 } else if (Name == "vfprintf" || 2316 Name == "vsprintf") { 2317 if (FTy->getNumParams() != 3 || 2318 !FTy->getParamType(0)->isPointerTy() || 2319 !FTy->getParamType(1)->isPointerTy()) 2320 return; 2321 setDoesNotThrow(F); 2322 setDoesNotCapture(F, 1); 2323 setDoesNotCapture(F, 2); 2324 } else if (Name == "vsnprintf") { 2325 if (FTy->getNumParams() != 4 || 2326 !FTy->getParamType(0)->isPointerTy() || 2327 !FTy->getParamType(2)->isPointerTy()) 2328 return; 2329 setDoesNotThrow(F); 2330 setDoesNotCapture(F, 1); 2331 setDoesNotCapture(F, 3); 2332 } 2333 break; 2334 case 'o': 2335 if (Name == "open") { 2336 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy()) 2337 return; 2338 // May throw; "open" is a valid pthread cancellation point. 2339 setDoesNotCapture(F, 1); 2340 } else if (Name == "opendir") { 2341 if (FTy->getNumParams() != 1 || 2342 !FTy->getReturnType()->isPointerTy() || 2343 !FTy->getParamType(0)->isPointerTy()) 2344 return; 2345 setDoesNotThrow(F); 2346 setDoesNotAlias(F, 0); 2347 setDoesNotCapture(F, 1); 2348 } 2349 break; 2350 case 't': 2351 if (Name == "tmpfile") { 2352 if (!FTy->getReturnType()->isPointerTy()) 2353 return; 2354 setDoesNotThrow(F); 2355 setDoesNotAlias(F, 0); 2356 } else if (Name == "times") { 2357 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 2358 return; 2359 setDoesNotThrow(F); 2360 setDoesNotCapture(F, 1); 2361 } 2362 break; 2363 case 'h': 2364 if (Name == "htonl" || 2365 Name == "htons") { 2366 setDoesNotThrow(F); 2367 setDoesNotAccessMemory(F); 2368 } 2369 break; 2370 case 'n': 2371 if (Name == "ntohl" || 2372 Name == "ntohs") { 2373 setDoesNotThrow(F); 2374 setDoesNotAccessMemory(F); 2375 } 2376 break; 2377 case 'l': 2378 if (Name == "lstat") { 2379 if (FTy->getNumParams() != 2 || 2380 !FTy->getParamType(0)->isPointerTy() || 2381 !FTy->getParamType(1)->isPointerTy()) 2382 return; 2383 setDoesNotThrow(F); 2384 setDoesNotCapture(F, 1); 2385 setDoesNotCapture(F, 2); 2386 } else if (Name == "lchown") { 2387 if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy()) 2388 return; 2389 setDoesNotThrow(F); 2390 setDoesNotCapture(F, 1); 2391 } 2392 break; 2393 case 'q': 2394 if (Name == "qsort") { 2395 if (FTy->getNumParams() != 4 || !FTy->getParamType(3)->isPointerTy()) 2396 return; 2397 // May throw; places call through function pointer. 2398 setDoesNotCapture(F, 4); 2399 } 2400 break; 2401 case '_': 2402 if (Name == "__strdup" || 2403 Name == "__strndup") { 2404 if (FTy->getNumParams() < 1 || 2405 !FTy->getReturnType()->isPointerTy() || 2406 !FTy->getParamType(0)->isPointerTy()) 2407 return; 2408 setDoesNotThrow(F); 2409 setDoesNotAlias(F, 0); 2410 setDoesNotCapture(F, 1); 2411 } else if (Name == "__strtok_r") { 2412 if (FTy->getNumParams() != 3 || 2413 !FTy->getParamType(1)->isPointerTy()) 2414 return; 2415 setDoesNotThrow(F); 2416 setDoesNotCapture(F, 2); 2417 } else if (Name == "_IO_getc") { 2418 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 2419 return; 2420 setDoesNotThrow(F); 2421 setDoesNotCapture(F, 1); 2422 } else if (Name == "_IO_putc") { 2423 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) 2424 return; 2425 setDoesNotThrow(F); 2426 setDoesNotCapture(F, 2); 2427 } 2428 break; 2429 case 1: 2430 if (Name == "\1__isoc99_scanf") { 2431 if (FTy->getNumParams() < 1 || 2432 !FTy->getParamType(0)->isPointerTy()) 2433 return; 2434 setDoesNotThrow(F); 2435 setDoesNotCapture(F, 1); 2436 } else if (Name == "\1stat64" || 2437 Name == "\1lstat64" || 2438 Name == "\1statvfs64" || 2439 Name == "\1__isoc99_sscanf") { 2440 if (FTy->getNumParams() < 1 || 2441 !FTy->getParamType(0)->isPointerTy() || 2442 !FTy->getParamType(1)->isPointerTy()) 2443 return; 2444 setDoesNotThrow(F); 2445 setDoesNotCapture(F, 1); 2446 setDoesNotCapture(F, 2); 2447 } else if (Name == "\1fopen64") { 2448 if (FTy->getNumParams() != 2 || 2449 !FTy->getReturnType()->isPointerTy() || 2450 !FTy->getParamType(0)->isPointerTy() || 2451 !FTy->getParamType(1)->isPointerTy()) 2452 return; 2453 setDoesNotThrow(F); 2454 setDoesNotAlias(F, 0); 2455 setDoesNotCapture(F, 1); 2456 setDoesNotCapture(F, 2); 2457 } else if (Name == "\1fseeko64" || 2458 Name == "\1ftello64") { 2459 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy()) 2460 return; 2461 setDoesNotThrow(F); 2462 setDoesNotCapture(F, 1); 2463 } else if (Name == "\1tmpfile64") { 2464 if (!FTy->getReturnType()->isPointerTy()) 2465 return; 2466 setDoesNotThrow(F); 2467 setDoesNotAlias(F, 0); 2468 } else if (Name == "\1fstat64" || 2469 Name == "\1fstatvfs64") { 2470 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) 2471 return; 2472 setDoesNotThrow(F); 2473 setDoesNotCapture(F, 2); 2474 } else if (Name == "\1open64") { 2475 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy()) 2476 return; 2477 // May throw; "open" is a valid pthread cancellation point. 2478 setDoesNotCapture(F, 1); 2479 } 2480 break; 2481 } 2482} 2483 2484/// doInitialization - Add attributes to well-known functions. 2485/// 2486bool SimplifyLibCalls::doInitialization(Module &M) { 2487 Modified = false; 2488 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) { 2489 Function &F = *I; 2490 if (F.isDeclaration() && F.hasName()) 2491 inferPrototypeAttributes(F); 2492 } 2493 return Modified; 2494} 2495 2496// TODO: 2497// Additional cases that we need to add to this file: 2498// 2499// cbrt: 2500// * cbrt(expN(X)) -> expN(x/3) 2501// * cbrt(sqrt(x)) -> pow(x,1/6) 2502// * cbrt(sqrt(x)) -> pow(x,1/9) 2503// 2504// exp, expf, expl: 2505// * exp(log(x)) -> x 2506// 2507// log, logf, logl: 2508// * log(exp(x)) -> x 2509// * log(x**y) -> y*log(x) 2510// * log(exp(y)) -> y*log(e) 2511// * log(exp2(y)) -> y*log(2) 2512// * log(exp10(y)) -> y*log(10) 2513// * log(sqrt(x)) -> 0.5*log(x) 2514// * log(pow(x,y)) -> y*log(x) 2515// 2516// lround, lroundf, lroundl: 2517// * lround(cnst) -> cnst' 2518// 2519// pow, powf, powl: 2520// * pow(exp(x),y) -> exp(x*y) 2521// * pow(sqrt(x),y) -> pow(x,y*0.5) 2522// * pow(pow(x,y),z)-> pow(x,y*z) 2523// 2524// round, roundf, roundl: 2525// * round(cnst) -> cnst' 2526// 2527// signbit: 2528// * signbit(cnst) -> cnst' 2529// * signbit(nncst) -> 0 (if pstv is a non-negative constant) 2530// 2531// sqrt, sqrtf, sqrtl: 2532// * sqrt(expN(x)) -> expN(x*0.5) 2533// * sqrt(Nroot(x)) -> pow(x,1/(2*N)) 2534// * sqrt(pow(x,y)) -> pow(|x|,y*0.5) 2535// 2536// strchr: 2537// * strchr(p, 0) -> strlen(p) 2538// tan, tanf, tanl: 2539// * tan(atan(x)) -> x 2540// 2541// trunc, truncf, truncl: 2542// * trunc(cnst) -> cnst' 2543// 2544// 2545