lib/Transforms/Scalar/SimplifyLibCalls.cpp

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