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 //===---------------------------------------===//
 137 // 'strcat' Optimizations
 138 namespace {
 139 struct 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 DataLayout.
 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
 191 struct 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 DataLayout.
 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
 238 struct 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 DataLayout.
 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
 287 struct 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
 326 struct 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 DataLayout.
 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
 374 struct 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
 428 struct 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 DataLayout.
 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
 469 struct 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 DataLayout.
 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
 514 struct 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 DataLayout.
 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
 563 struct 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
 589 struct 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
 627 struct 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       Attributes::Builder B;
 640       B.addAttribute(Attributes::NoCapture);
 641       CI->addAttribute(1, Attributes::get(B));
 642     }
 643
 644     return 0;
 645   }
 646 };
 647
 648 //===---------------------------------------===//
 649 // 'strspn' Optimizations
 650
 651 struct StrSpnOpt : public LibCallOptimization {
 652   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 653     FunctionType *FT = Callee->getFunctionType();
 654     if (FT->getNumParams() != 2 ||
 655         FT->getParamType(0) != B.getInt8PtrTy() ||
 656         FT->getParamType(1) != FT->getParamType(0) ||
 657         !FT->getReturnType()->isIntegerTy())
 658       return 0;
 659
 660     StringRef S1, S2;
 661     bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
 662     bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
 663
 664     // strspn(s, "") -> 0
 665     // strspn("", s) -> 0
 666     if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))
 667       return Constant::getNullValue(CI->getType());
 668
 669     // Constant folding.
 670     if (HasS1 && HasS2) {
 671       size_t Pos = S1.find_first_not_of(S2);
 672       if (Pos == StringRef::npos) Pos = S1.size();
 673       return ConstantInt::get(CI->getType(), Pos);
 674     }
 675
 676     return 0;
 677   }
 678 };
 679
 680 //===---------------------------------------===//
 681 // 'strcspn' Optimizations
 682
 683 struct StrCSpnOpt : public LibCallOptimization {
 684   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 685     FunctionType *FT = Callee->getFunctionType();
 686     if (FT->getNumParams() != 2 ||
 687         FT->getParamType(0) != B.getInt8PtrTy() ||
 688         FT->getParamType(1) != FT->getParamType(0) ||
 689         !FT->getReturnType()->isIntegerTy())
 690       return 0;
 691
 692     StringRef S1, S2;
 693     bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
 694     bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
 695
 696     // strcspn("", s) -> 0
 697     if (HasS1 && S1.empty())
 698       return Constant::getNullValue(CI->getType());
 699
 700     // Constant folding.
 701     if (HasS1 && HasS2) {
 702       size_t Pos = S1.find_first_of(S2);
 703       if (Pos == StringRef::npos) Pos = S1.size();
 704       return ConstantInt::get(CI->getType(), Pos);
 705     }
 706
 707     // strcspn(s, "") -> strlen(s)
 708     if (TD && HasS2 && S2.empty())
 709       return EmitStrLen(CI->getArgOperand(0), B, TD, TLI);
 710
 711     return 0;
 712   }
 713 };
 714
 715 //===---------------------------------------===//
 716 // 'strstr' Optimizations
 717
 718 struct StrStrOpt : public LibCallOptimization {
 719   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 720     FunctionType *FT = Callee->getFunctionType();
 721     if (FT->getNumParams() != 2 ||
 722         !FT->getParamType(0)->isPointerTy() ||
 723         !FT->getParamType(1)->isPointerTy() ||
 724         !FT->getReturnType()->isPointerTy())
 725       return 0;
 726
 727     // fold strstr(x, x) -> x.
 728     if (CI->getArgOperand(0) == CI->getArgOperand(1))
 729       return B.CreateBitCast(CI->getArgOperand(0), CI->getType());
 730
 731     // fold strstr(a, b) == a -> strncmp(a, b, strlen(b)) == 0
 732     if (TD && IsOnlyUsedInEqualityComparison(CI, CI->getArgOperand(0))) {
 733       Value *StrLen = EmitStrLen(CI->getArgOperand(1), B, TD, TLI);
 734       if (!StrLen)
 735         return 0;
 736       Value *StrNCmp = EmitStrNCmp(CI->getArgOperand(0), CI->getArgOperand(1),
 737                                    StrLen, B, TD, TLI);
 738       if (!StrNCmp)
 739         return 0;
 740       for (Value::use_iterator UI = CI->use_begin(), UE = CI->use_end();
 741            UI != UE; ) {
 742         ICmpInst *Old = cast<ICmpInst>(*UI++);
 743         Value *Cmp = B.CreateICmp(Old->getPredicate(), StrNCmp,
 744                                   ConstantInt::getNullValue(StrNCmp->getType()),
 745                                   "cmp");
 746         Old->replaceAllUsesWith(Cmp);
 747         Old->eraseFromParent();
 748       }
 749       return CI;
 750     }
 751
 752     // See if either input string is a constant string.
 753     StringRef SearchStr, ToFindStr;
 754     bool HasStr1 = getConstantStringInfo(CI->getArgOperand(0), SearchStr);
 755     bool HasStr2 = getConstantStringInfo(CI->getArgOperand(1), ToFindStr);
 756
 757     // fold strstr(x, "") -> x.
 758     if (HasStr2 && ToFindStr.empty())
 759       return B.CreateBitCast(CI->getArgOperand(0), CI->getType());
 760
 761     // If both strings are known, constant fold it.
 762     if (HasStr1 && HasStr2) {
 763       std::string::size_type Offset = SearchStr.find(ToFindStr);
 764
 765       if (Offset == StringRef::npos) // strstr("foo", "bar") -> null
 766         return Constant::getNullValue(CI->getType());
 767
 768       // strstr("abcd", "bc") -> gep((char*)"abcd", 1)
 769       Value *Result = CastToCStr(CI->getArgOperand(0), B);
 770       Result = B.CreateConstInBoundsGEP1_64(Result, Offset, "strstr");
 771       return B.CreateBitCast(Result, CI->getType());
 772     }
 773
 774     // fold strstr(x, "y") -> strchr(x, 'y').
 775     if (HasStr2 && ToFindStr.size() == 1) {
 776       Value *StrChr= EmitStrChr(CI->getArgOperand(0), ToFindStr[0], B, TD, TLI);
 777       return StrChr ? B.CreateBitCast(StrChr, CI->getType()) : 0;
 778     }
 779     return 0;
 780   }
 781 };
 782
 783
 784 //===---------------------------------------===//
 785 // 'memcmp' Optimizations
 786
 787 struct MemCmpOpt : public LibCallOptimization {
 788   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 789     FunctionType *FT = Callee->getFunctionType();
 790     if (FT->getNumParams() != 3 || !FT->getParamType(0)->isPointerTy() ||
 791         !FT->getParamType(1)->isPointerTy() ||
 792         !FT->getReturnType()->isIntegerTy(32))
 793       return 0;
 794
 795     Value *LHS = CI->getArgOperand(0), *RHS = CI->getArgOperand(1);
 796
 797     if (LHS == RHS)  // memcmp(s,s,x) -> 0
 798       return Constant::getNullValue(CI->getType());
 799
 800     // Make sure we have a constant length.
 801     ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getArgOperand(2));
 802     if (!LenC) return 0;
 803     uint64_t Len = LenC->getZExtValue();
 804
 805     if (Len == 0) // memcmp(s1,s2,0) -> 0
 806       return Constant::getNullValue(CI->getType());
 807
 808     // memcmp(S1,S2,1) -> *(unsigned char*)LHS - *(unsigned char*)RHS
 809     if (Len == 1) {
 810       Value *LHSV = B.CreateZExt(B.CreateLoad(CastToCStr(LHS, B), "lhsc"),
 811                                  CI->getType(), "lhsv");
 812       Value *RHSV = B.CreateZExt(B.CreateLoad(CastToCStr(RHS, B), "rhsc"),
 813                                  CI->getType(), "rhsv");
 814       return B.CreateSub(LHSV, RHSV, "chardiff");
 815     }
 816
 817     // Constant folding: memcmp(x, y, l) -> cnst (all arguments are constant)
 818     StringRef LHSStr, RHSStr;
 819     if (getConstantStringInfo(LHS, LHSStr) &&
 820         getConstantStringInfo(RHS, RHSStr)) {
 821       // Make sure we're not reading out-of-bounds memory.
 822       if (Len > LHSStr.size() || Len > RHSStr.size())
 823         return 0;
 824       uint64_t Ret = memcmp(LHSStr.data(), RHSStr.data(), Len);
 825       return ConstantInt::get(CI->getType(), Ret);
 826     }
 827
 828     return 0;
 829   }
 830 };
 831
 832 //===---------------------------------------===//
 833 // 'memcpy' Optimizations
 834
 835 struct MemCpyOpt : public LibCallOptimization {
 836   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 837     // These optimizations require DataLayout.
 838     if (!TD) return 0;
 839
 840     FunctionType *FT = Callee->getFunctionType();
 841     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 842         !FT->getParamType(0)->isPointerTy() ||
 843         !FT->getParamType(1)->isPointerTy() ||
 844         FT->getParamType(2) != TD->getIntPtrType(*Context))
 845       return 0;
 846
 847     // memcpy(x, y, n) -> llvm.memcpy(x, y, n, 1)
 848     B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
 849                    CI->getArgOperand(2), 1);
 850     return CI->getArgOperand(0);
 851   }
 852 };
 853
 854 //===---------------------------------------===//
 855 // 'memmove' Optimizations
 856
 857 struct MemMoveOpt : public LibCallOptimization {
 858   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 859     // These optimizations require DataLayout.
 860     if (!TD) return 0;
 861
 862     FunctionType *FT = Callee->getFunctionType();
 863     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 864         !FT->getParamType(0)->isPointerTy() ||
 865         !FT->getParamType(1)->isPointerTy() ||
 866         FT->getParamType(2) != TD->getIntPtrType(*Context))
 867       return 0;
 868
 869     // memmove(x, y, n) -> llvm.memmove(x, y, n, 1)
 870     B.CreateMemMove(CI->getArgOperand(0), CI->getArgOperand(1),
 871                     CI->getArgOperand(2), 1);
 872     return CI->getArgOperand(0);
 873   }
 874 };
 875
 876 //===---------------------------------------===//
 877 // 'memset' Optimizations
 878
 879 struct MemSetOpt : public LibCallOptimization {
 880   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 881     // These optimizations require DataLayout.
 882     if (!TD) return 0;
 883
 884     FunctionType *FT = Callee->getFunctionType();
 885     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 886         !FT->getParamType(0)->isPointerTy() ||
 887         !FT->getParamType(1)->isIntegerTy() ||
 888         FT->getParamType(2) != TD->getIntPtrType(*Context))
 889       return 0;
 890
 891     // memset(p, v, n) -> llvm.memset(p, v, n, 1)
 892     Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(), false);
 893     B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1);
 894     return CI->getArgOperand(0);
 895   }
 896 };
 897
 898 //===----------------------------------------------------------------------===//
 899 // Math Library Optimizations
 900 //===----------------------------------------------------------------------===//
 901
 902 //===---------------------------------------===//
 903 // Double -> Float Shrinking Optimizations for Unary Functions like 'floor'
 904
 905 struct UnaryDoubleFPOpt : public LibCallOptimization {
 906   bool CheckRetType;
 907   UnaryDoubleFPOpt(bool CheckReturnType): CheckRetType(CheckReturnType) {}
 908   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 909     FunctionType *FT = Callee->getFunctionType();
 910     if (FT->getNumParams() != 1 || !FT->getReturnType()->isDoubleTy() ||
 911         !FT->getParamType(0)->isDoubleTy())
 912       return 0;
 913
 914     if (CheckRetType) {
 915       // Check if all the uses for function like 'sin' are converted to float.
 916       for (Value::use_iterator UseI = CI->use_begin(); UseI != CI->use_end();
 917           ++UseI) {
 918         FPTruncInst *Cast = dyn_cast<FPTruncInst>(*UseI);
 919         if (Cast == 0 || !Cast->getType()->isFloatTy())
 920           return 0;
 921       }
 922     }
 923
 924     // If this is something like 'floor((double)floatval)', convert to floorf.
 925     FPExtInst *Cast = dyn_cast<FPExtInst>(CI->getArgOperand(0));
 926     if (Cast == 0 || !Cast->getOperand(0)->getType()->isFloatTy())
 927       return 0;
 928
 929     // floor((double)floatval) -> (double)floorf(floatval)
 930     Value *V = Cast->getOperand(0);
 931     V = EmitUnaryFloatFnCall(V, Callee->getName(), B, Callee->getAttributes());
 932     return B.CreateFPExt(V, B.getDoubleTy());
 933   }
 934 };
 935
 936 //===---------------------------------------===//
 937 // 'cos*' Optimizations
 938 struct CosOpt : public LibCallOptimization {
 939   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 940     Value *Ret = NULL;
 941     if (UnsafeFPShrink && Callee->getName() == "cos" &&
 942         TLI->has(LibFunc::cosf)) {
 943       UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
 944       Ret = UnsafeUnaryDoubleFP.CallOptimizer(Callee, CI, B);
 945     }
 946
 947     FunctionType *FT = Callee->getFunctionType();
 948     // Just make sure this has 1 argument of FP type, which matches the
 949     // result type.
 950     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
 951         !FT->getParamType(0)->isFloatingPointTy())
 952       return Ret;
 953
 954     // cos(-x) -> cos(x)
 955     Value *Op1 = CI->getArgOperand(0);
 956     if (BinaryOperator::isFNeg(Op1)) {
 957       BinaryOperator *BinExpr = cast<BinaryOperator>(Op1);
 958       return B.CreateCall(Callee, BinExpr->getOperand(1), "cos");
 959     }
 960     return Ret;
 961   }
 962 };
 963
 964 //===---------------------------------------===//
 965 // 'pow*' Optimizations
 966
 967 struct PowOpt : public LibCallOptimization {
 968   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 969     Value *Ret = NULL;
 970     if (UnsafeFPShrink && Callee->getName() == "pow" &&
 971         TLI->has(LibFunc::powf)) {
 972       UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
 973       Ret = UnsafeUnaryDoubleFP.CallOptimizer(Callee, CI, B);
 974     }
 975
 976     FunctionType *FT = Callee->getFunctionType();
 977     // Just make sure this has 2 arguments of the same FP type, which match the
 978     // result type.
 979     if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) ||
 980         FT->getParamType(0) != FT->getParamType(1) ||
 981         !FT->getParamType(0)->isFloatingPointTy())
 982       return Ret;
 983
 984     Value *Op1 = CI->getArgOperand(0), *Op2 = CI->getArgOperand(1);
 985     if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) {
 986       if (Op1C->isExactlyValue(1.0))  // pow(1.0, x) -> 1.0
 987         return Op1C;
 988       if (Op1C->isExactlyValue(2.0))  // pow(2.0, x) -> exp2(x)
 989         return EmitUnaryFloatFnCall(Op2, "exp2", B, Callee->getAttributes());
 990     }
 991
 992     ConstantFP *Op2C = dyn_cast<ConstantFP>(Op2);
 993     if (Op2C == 0) return Ret;
 994
 995     if (Op2C->getValueAPF().isZero())  // pow(x, 0.0) -> 1.0
 996       return ConstantFP::get(CI->getType(), 1.0);
 997
 998     if (Op2C->isExactlyValue(0.5)) {
 999       // Expand pow(x, 0.5) to (x == -infinity ? +infinity : fabs(sqrt(x))).
1000       // This is faster than calling pow, and still handles negative zero
1001       // and negative infinity correctly.
1002       // TODO: In fast-math mode, this could be just sqrt(x).
1003       // TODO: In finite-only mode, this could be just fabs(sqrt(x)).
1004       Value *Inf = ConstantFP::getInfinity(CI->getType());
1005       Value *NegInf = ConstantFP::getInfinity(CI->getType(), true);
1006       Value *Sqrt = EmitUnaryFloatFnCall(Op1, "sqrt", B,
1007                                          Callee->getAttributes());
1008       Value *FAbs = EmitUnaryFloatFnCall(Sqrt, "fabs", B,
1009                                          Callee->getAttributes());
1010       Value *FCmp = B.CreateFCmpOEQ(Op1, NegInf);
1011       Value *Sel = B.CreateSelect(FCmp, Inf, FAbs);
1012       return Sel;
1013     }
1014
1015     if (Op2C->isExactlyValue(1.0))  // pow(x, 1.0) -> x
1016       return Op1;
1017     if (Op2C->isExactlyValue(2.0))  // pow(x, 2.0) -> x*x
1018       return B.CreateFMul(Op1, Op1, "pow2");
1019     if (Op2C->isExactlyValue(-1.0)) // pow(x, -1.0) -> 1.0/x
1020       return B.CreateFDiv(ConstantFP::get(CI->getType(), 1.0),
1021                           Op1, "powrecip");
1022     return 0;
1023   }
1024 };
1025
1026 //===---------------------------------------===//
1027 // 'exp2' Optimizations
1028
1029 struct Exp2Opt : public LibCallOptimization {
1030   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1031     Value *Ret = NULL;
1032     if (UnsafeFPShrink && Callee->getName() == "exp2" &&
1033         TLI->has(LibFunc::exp2)) {
1034       UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
1035       Ret = UnsafeUnaryDoubleFP.CallOptimizer(Callee, CI, B);
1036     }
1037
1038     FunctionType *FT = Callee->getFunctionType();
1039     // Just make sure this has 1 argument of FP type, which matches the
1040     // result type.
1041     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1042         !FT->getParamType(0)->isFloatingPointTy())
1043       return Ret;
1044
1045     Value *Op = CI->getArgOperand(0);
1046     // Turn exp2(sitofp(x)) -> ldexp(1.0, sext(x))  if sizeof(x) <= 32
1047     // Turn exp2(uitofp(x)) -> ldexp(1.0, zext(x))  if sizeof(x) < 32
1048     Value *LdExpArg = 0;
1049     if (SIToFPInst *OpC = dyn_cast<SIToFPInst>(Op)) {
1050       if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() <= 32)
1051         LdExpArg = B.CreateSExt(OpC->getOperand(0), B.getInt32Ty());
1052     } else if (UIToFPInst *OpC = dyn_cast<UIToFPInst>(Op)) {
1053       if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() < 32)
1054         LdExpArg = B.CreateZExt(OpC->getOperand(0), B.getInt32Ty());
1055     }
1056
1057     if (LdExpArg) {
1058       const char *Name;
1059       if (Op->getType()->isFloatTy())
1060         Name = "ldexpf";
1061       else if (Op->getType()->isDoubleTy())
1062         Name = "ldexp";
1063       else
1064         Name = "ldexpl";
1065
1066       Constant *One = ConstantFP::get(*Context, APFloat(1.0f));
1067       if (!Op->getType()->isFloatTy())
1068         One = ConstantExpr::getFPExtend(One, Op->getType());
1069
1070       Module *M = Caller->getParent();
1071       Value *Callee = M->getOrInsertFunction(Name, Op->getType(),
1072                                              Op->getType(),
1073                                              B.getInt32Ty(), NULL);
1074       CallInst *CI = B.CreateCall2(Callee, One, LdExpArg);
1075       if (const Function *F = dyn_cast<Function>(Callee->stripPointerCasts()))
1076         CI->setCallingConv(F->getCallingConv());
1077
1078       return CI;
1079     }
1080     return Ret;
1081   }
1082 };
1083
1084 //===----------------------------------------------------------------------===//
1085 // Integer Optimizations
1086 //===----------------------------------------------------------------------===//
1087
1088 //===---------------------------------------===//
1089 // 'ffs*' Optimizations
1090
1091 struct FFSOpt : public LibCallOptimization {
1092   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1093     FunctionType *FT = Callee->getFunctionType();
1094     // Just make sure this has 2 arguments of the same FP type, which match the
1095     // result type.
1096     if (FT->getNumParams() != 1 ||
1097         !FT->getReturnType()->isIntegerTy(32) ||
1098         !FT->getParamType(0)->isIntegerTy())
1099       return 0;
1100
1101     Value *Op = CI->getArgOperand(0);
1102
1103     // Constant fold.
1104     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op)) {
1105       if (CI->getValue() == 0)  // ffs(0) -> 0.
1106         return Constant::getNullValue(CI->getType());
1107       // ffs(c) -> cttz(c)+1
1108       return B.getInt32(CI->getValue().countTrailingZeros() + 1);
1109     }
1110
1111     // ffs(x) -> x != 0 ? (i32)llvm.cttz(x)+1 : 0
1112     Type *ArgType = Op->getType();
1113     Value *F = Intrinsic::getDeclaration(Callee->getParent(),
1114                                          Intrinsic::cttz, ArgType);
1115     Value *V = B.CreateCall2(F, Op, B.getFalse(), "cttz");
1116     V = B.CreateAdd(V, ConstantInt::get(V->getType(), 1));
1117     V = B.CreateIntCast(V, B.getInt32Ty(), false);
1118
1119     Value *Cond = B.CreateICmpNE(Op, Constant::getNullValue(ArgType));
1120     return B.CreateSelect(Cond, V, B.getInt32(0));
1121   }
1122 };
1123
1124 //===---------------------------------------===//
1125 // 'isdigit' Optimizations
1126
1127 struct IsDigitOpt : public LibCallOptimization {
1128   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1129     FunctionType *FT = Callee->getFunctionType();
1130     // We require integer(i32)
1131     if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
1132         !FT->getParamType(0)->isIntegerTy(32))
1133       return 0;
1134
1135     // isdigit(c) -> (c-'0') <u 10
1136     Value *Op = CI->getArgOperand(0);
1137     Op = B.CreateSub(Op, B.getInt32('0'), "isdigittmp");
1138     Op = B.CreateICmpULT(Op, B.getInt32(10), "isdigit");
1139     return B.CreateZExt(Op, CI->getType());
1140   }
1141 };
1142
1143 //===---------------------------------------===//
1144 // 'isascii' Optimizations
1145
1146 struct IsAsciiOpt : public LibCallOptimization {
1147   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1148     FunctionType *FT = Callee->getFunctionType();
1149     // We require integer(i32)
1150     if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
1151         !FT->getParamType(0)->isIntegerTy(32))
1152       return 0;
1153
1154     // isascii(c) -> c <u 128
1155     Value *Op = CI->getArgOperand(0);
1156     Op = B.CreateICmpULT(Op, B.getInt32(128), "isascii");
1157     return B.CreateZExt(Op, CI->getType());
1158   }
1159 };
1160
1161 //===---------------------------------------===//
1162 // 'abs', 'labs', 'llabs' Optimizations
1163
1164 struct AbsOpt : public LibCallOptimization {
1165   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1166     FunctionType *FT = Callee->getFunctionType();
1167     // We require integer(integer) where the types agree.
1168     if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
1169         FT->getParamType(0) != FT->getReturnType())
1170       return 0;
1171
1172     // abs(x) -> x >s -1 ? x : -x
1173     Value *Op = CI->getArgOperand(0);
1174     Value *Pos = B.CreateICmpSGT(Op, Constant::getAllOnesValue(Op->getType()),
1175                                  "ispos");
1176     Value *Neg = B.CreateNeg(Op, "neg");
1177     return B.CreateSelect(Pos, Op, Neg);
1178   }
1179 };
1180
1181
1182 //===---------------------------------------===//
1183 // 'toascii' Optimizations
1184
1185 struct ToAsciiOpt : public LibCallOptimization {
1186   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1187     FunctionType *FT = Callee->getFunctionType();
1188     // We require i32(i32)
1189     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1190         !FT->getParamType(0)->isIntegerTy(32))
1191       return 0;
1192
1193     // isascii(c) -> c & 0x7f
1194     return B.CreateAnd(CI->getArgOperand(0),
1195                        ConstantInt::get(CI->getType(),0x7F));
1196   }
1197 };
1198
1199 //===----------------------------------------------------------------------===//
1200 // Formatting and IO Optimizations
1201 //===----------------------------------------------------------------------===//
1202
1203 //===---------------------------------------===//
1204 // 'printf' Optimizations
1205
1206 struct PrintFOpt : public LibCallOptimization {
1207   Value *OptimizeFixedFormatString(Function *Callee, CallInst *CI,
1208                                    IRBuilder<> &B) {
1209     // Check for a fixed format string.
1210     StringRef FormatStr;
1211     if (!getConstantStringInfo(CI->getArgOperand(0), FormatStr))
1212       return 0;
1213
1214     // Empty format string -> noop.
1215     if (FormatStr.empty())  // Tolerate printf's declared void.
1216       return CI->use_empty() ? (Value*)CI :
1217                                ConstantInt::get(CI->getType(), 0);
1218
1219     // Do not do any of the following transformations if the printf return value
1220     // is used, in general the printf return value is not compatible with either
1221     // putchar() or puts().
1222     if (!CI->use_empty())
1223       return 0;
1224
1225     // printf("x") -> putchar('x'), even for '%'.
1226     if (FormatStr.size() == 1) {
1227       Value *Res = EmitPutChar(B.getInt32(FormatStr[0]), B, TD, TLI);
1228       if (CI->use_empty() || !Res) return Res;
1229       return B.CreateIntCast(Res, CI->getType(), true);
1230     }
1231
1232     // printf("foo\n") --> puts("foo")
1233     if (FormatStr[FormatStr.size()-1] == '\n' &&
1234         FormatStr.find('%') == std::string::npos) {  // no format characters.
1235       // Create a string literal with no \n on it.  We expect the constant merge
1236       // pass to be run after this pass, to merge duplicate strings.
1237       FormatStr = FormatStr.drop_back();
1238       Value *GV = B.CreateGlobalString(FormatStr, "str");
1239       Value *NewCI = EmitPutS(GV, B, TD, TLI);
1240       return (CI->use_empty() || !NewCI) ?
1241               NewCI :
1242               ConstantInt::get(CI->getType(), FormatStr.size()+1);
1243     }
1244
1245     // Optimize specific format strings.
1246     // printf("%c", chr) --> putchar(chr)
1247     if (FormatStr == "%c" && CI->getNumArgOperands() > 1 &&
1248         CI->getArgOperand(1)->getType()->isIntegerTy()) {
1249       Value *Res = EmitPutChar(CI->getArgOperand(1), B, TD, TLI);
1250
1251       if (CI->use_empty() || !Res) return Res;
1252       return B.CreateIntCast(Res, CI->getType(), true);
1253     }
1254
1255     // printf("%s\n", str) --> puts(str)
1256     if (FormatStr == "%s\n" && CI->getNumArgOperands() > 1 &&
1257         CI->getArgOperand(1)->getType()->isPointerTy()) {
1258       return EmitPutS(CI->getArgOperand(1), B, TD, TLI);
1259     }
1260     return 0;
1261   }
1262
1263   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1264     // Require one fixed pointer argument and an integer/void result.
1265     FunctionType *FT = Callee->getFunctionType();
1266     if (FT->getNumParams() < 1 || !FT->getParamType(0)->isPointerTy() ||
1267         !(FT->getReturnType()->isIntegerTy() ||
1268           FT->getReturnType()->isVoidTy()))
1269       return 0;
1270
1271     if (Value *V = OptimizeFixedFormatString(Callee, CI, B)) {
1272       return V;
1273     }
1274
1275     // printf(format, ...) -> iprintf(format, ...) if no floating point
1276     // arguments.
1277     if (TLI->has(LibFunc::iprintf) && !CallHasFloatingPointArgument(CI)) {
1278       Module *M = B.GetInsertBlock()->getParent()->getParent();
1279       Constant *IPrintFFn =
1280         M->getOrInsertFunction("iprintf", FT, Callee->getAttributes());
1281       CallInst *New = cast<CallInst>(CI->clone());
1282       New->setCalledFunction(IPrintFFn);
1283       B.Insert(New);
1284       return New;
1285     }
1286     return 0;
1287   }
1288 };
1289
1290 //===---------------------------------------===//
1291 // 'sprintf' Optimizations
1292
1293 struct SPrintFOpt : public LibCallOptimization {
1294   Value *OptimizeFixedFormatString(Function *Callee, CallInst *CI,
1295                                    IRBuilder<> &B) {
1296     // Check for a fixed format string.
1297     StringRef FormatStr;
1298     if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr))
1299       return 0;
1300
1301     // If we just have a format string (nothing else crazy) transform it.
1302     if (CI->getNumArgOperands() == 2) {
1303       // Make sure there's no % in the constant array.  We could try to handle
1304       // %% -> % in the future if we cared.
1305       for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1306         if (FormatStr[i] == '%')
1307           return 0; // we found a format specifier, bail out.
1308
1309       // These optimizations require DataLayout.
1310       if (!TD) return 0;
1311
1312       // sprintf(str, fmt) -> llvm.memcpy(str, fmt, strlen(fmt)+1, 1)
1313       B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
1314                      ConstantInt::get(TD->getIntPtrType(*Context), // Copy the
1315                                       FormatStr.size() + 1), 1);   // nul byte.
1316       return ConstantInt::get(CI->getType(), FormatStr.size());
1317     }
1318
1319     // The remaining optimizations require the format string to be "%s" or "%c"
1320     // and have an extra operand.
1321     if (FormatStr.size() != 2 || FormatStr[0] != '%' ||
1322         CI->getNumArgOperands() < 3)
1323       return 0;
1324
1325     // Decode the second character of the format string.
1326     if (FormatStr[1] == 'c') {
1327       // sprintf(dst, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0
1328       if (!CI->getArgOperand(2)->getType()->isIntegerTy()) return 0;
1329       Value *V = B.CreateTrunc(CI->getArgOperand(2), B.getInt8Ty(), "char");
1330       Value *Ptr = CastToCStr(CI->getArgOperand(0), B);
1331       B.CreateStore(V, Ptr);
1332       Ptr = B.CreateGEP(Ptr, B.getInt32(1), "nul");
1333       B.CreateStore(B.getInt8(0), Ptr);
1334
1335       return ConstantInt::get(CI->getType(), 1);
1336     }
1337
1338     if (FormatStr[1] == 's') {
1339       // These optimizations require DataLayout.
1340       if (!TD) return 0;
1341
1342       // sprintf(dest, "%s", str) -> llvm.memcpy(dest, str, strlen(str)+1, 1)
1343       if (!CI->getArgOperand(2)->getType()->isPointerTy()) return 0;
1344
1345       Value *Len = EmitStrLen(CI->getArgOperand(2), B, TD, TLI);
1346       if (!Len)
1347         return 0;
1348       Value *IncLen = B.CreateAdd(Len,
1349                                   ConstantInt::get(Len->getType(), 1),
1350                                   "leninc");
1351       B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(2), IncLen, 1);
1352
1353       // The sprintf result is the unincremented number of bytes in the string.
1354       return B.CreateIntCast(Len, CI->getType(), false);
1355     }
1356     return 0;
1357   }
1358
1359   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1360     // Require two fixed pointer arguments and an integer result.
1361     FunctionType *FT = Callee->getFunctionType();
1362     if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
1363         !FT->getParamType(1)->isPointerTy() ||
1364         !FT->getReturnType()->isIntegerTy())
1365       return 0;
1366
1367     if (Value *V = OptimizeFixedFormatString(Callee, CI, B)) {
1368       return V;
1369     }
1370
1371     // sprintf(str, format, ...) -> siprintf(str, format, ...) if no floating
1372     // point arguments.
1373     if (TLI->has(LibFunc::siprintf) && !CallHasFloatingPointArgument(CI)) {
1374       Module *M = B.GetInsertBlock()->getParent()->getParent();
1375       Constant *SIPrintFFn =
1376         M->getOrInsertFunction("siprintf", FT, Callee->getAttributes());
1377       CallInst *New = cast<CallInst>(CI->clone());
1378       New->setCalledFunction(SIPrintFFn);
1379       B.Insert(New);
1380       return New;
1381     }
1382     return 0;
1383   }
1384 };
1385
1386 //===---------------------------------------===//
1387 // 'fwrite' Optimizations
1388
1389 struct FWriteOpt : public LibCallOptimization {
1390   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1391     // Require a pointer, an integer, an integer, a pointer, returning integer.
1392     FunctionType *FT = Callee->getFunctionType();
1393     if (FT->getNumParams() != 4 || !FT->getParamType(0)->isPointerTy() ||
1394         !FT->getParamType(1)->isIntegerTy() ||
1395         !FT->getParamType(2)->isIntegerTy() ||
1396         !FT->getParamType(3)->isPointerTy() ||
1397         !FT->getReturnType()->isIntegerTy())
1398       return 0;
1399
1400     // Get the element size and count.
1401     ConstantInt *SizeC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
1402     ConstantInt *CountC = dyn_cast<ConstantInt>(CI->getArgOperand(2));
1403     if (!SizeC || !CountC) return 0;
1404     uint64_t Bytes = SizeC->getZExtValue()*CountC->getZExtValue();
1405
1406     // If this is writing zero records, remove the call (it's a noop).
1407     if (Bytes == 0)
1408       return ConstantInt::get(CI->getType(), 0);
1409
1410     // If this is writing one byte, turn it into fputc.
1411     // This optimisation is only valid, if the return value is unused.
1412     if (Bytes == 1 && CI->use_empty()) {  // fwrite(S,1,1,F) -> fputc(S[0],F)
1413       Value *Char = B.CreateLoad(CastToCStr(CI->getArgOperand(0), B), "char");
1414       Value *NewCI = EmitFPutC(Char, CI->getArgOperand(3), B, TD, TLI);
1415       return NewCI ? ConstantInt::get(CI->getType(), 1) : 0;
1416     }
1417
1418     return 0;
1419   }
1420 };
1421
1422 //===---------------------------------------===//
1423 // 'fputs' Optimizations
1424
1425 struct FPutsOpt : public LibCallOptimization {
1426   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1427     // These optimizations require DataLayout.
1428     if (!TD) return 0;
1429
1430     // Require two pointers.  Also, we can't optimize if return value is used.
1431     FunctionType *FT = Callee->getFunctionType();
1432     if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
1433         !FT->getParamType(1)->isPointerTy() ||
1434         !CI->use_empty())
1435       return 0;
1436
1437     // fputs(s,F) --> fwrite(s,1,strlen(s),F)
1438     uint64_t Len = GetStringLength(CI->getArgOperand(0));
1439     if (!Len) return 0;
1440     // Known to have no uses (see above).
1441     return EmitFWrite(CI->getArgOperand(0),
1442                       ConstantInt::get(TD->getIntPtrType(*Context), Len-1),
1443                       CI->getArgOperand(1), B, TD, TLI);
1444   }
1445 };
1446
1447 //===---------------------------------------===//
1448 // 'fprintf' Optimizations
1449
1450 struct FPrintFOpt : public LibCallOptimization {
1451   Value *OptimizeFixedFormatString(Function *Callee, CallInst *CI,
1452                                    IRBuilder<> &B) {
1453     // All the optimizations depend on the format string.
1454     StringRef FormatStr;
1455     if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr))
1456       return 0;
1457
1458     // fprintf(F, "foo") --> fwrite("foo", 3, 1, F)
1459     if (CI->getNumArgOperands() == 2) {
1460       for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1461         if (FormatStr[i] == '%')  // Could handle %% -> % if we cared.
1462           return 0; // We found a format specifier.
1463
1464       // These optimizations require DataLayout.
1465       if (!TD) return 0;
1466
1467       Value *NewCI = EmitFWrite(CI->getArgOperand(1),
1468                                 ConstantInt::get(TD->getIntPtrType(*Context),
1469                                                  FormatStr.size()),
1470                                 CI->getArgOperand(0), B, TD, TLI);
1471       return NewCI ? ConstantInt::get(CI->getType(), FormatStr.size()) : 0;
1472     }
1473
1474     // The remaining optimizations require the format string to be "%s" or "%c"
1475     // and have an extra operand.
1476     if (FormatStr.size() != 2 || FormatStr[0] != '%' ||
1477         CI->getNumArgOperands() < 3)
1478       return 0;
1479
1480     // Decode the second character of the format string.
1481     if (FormatStr[1] == 'c') {
1482       // fprintf(F, "%c", chr) --> fputc(chr, F)
1483       if (!CI->getArgOperand(2)->getType()->isIntegerTy()) return 0;
1484       Value *NewCI = EmitFPutC(CI->getArgOperand(2), CI->getArgOperand(0), B,
1485                                TD, TLI);
1486       return NewCI ? ConstantInt::get(CI->getType(), 1) : 0;
1487     }
1488
1489     if (FormatStr[1] == 's') {
1490       // fprintf(F, "%s", str) --> fputs(str, F)
1491       if (!CI->getArgOperand(2)->getType()->isPointerTy() || !CI->use_empty())
1492         return 0;
1493       return EmitFPutS(CI->getArgOperand(2), CI->getArgOperand(0), B, TD, TLI);
1494     }
1495     return 0;
1496   }
1497
1498   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1499     // Require two fixed paramters as pointers and integer result.
1500     FunctionType *FT = Callee->getFunctionType();
1501     if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
1502         !FT->getParamType(1)->isPointerTy() ||
1503         !FT->getReturnType()->isIntegerTy())
1504       return 0;
1505
1506     if (Value *V = OptimizeFixedFormatString(Callee, CI, B)) {
1507       return V;
1508     }
1509
1510     // fprintf(stream, format, ...) -> fiprintf(stream, format, ...) if no
1511     // floating point arguments.
1512     if (TLI->has(LibFunc::fiprintf) && !CallHasFloatingPointArgument(CI)) {
1513       Module *M = B.GetInsertBlock()->getParent()->getParent();
1514       Constant *FIPrintFFn =
1515         M->getOrInsertFunction("fiprintf", FT, Callee->getAttributes());
1516       CallInst *New = cast<CallInst>(CI->clone());
1517       New->setCalledFunction(FIPrintFFn);
1518       B.Insert(New);
1519       return New;
1520     }
1521     return 0;
1522   }
1523 };
1524
1525 //===---------------------------------------===//
1526 // 'puts' Optimizations
1527
1528 struct PutsOpt : public LibCallOptimization {
1529   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1530     // Require one fixed pointer argument and an integer/void result.
1531     FunctionType *FT = Callee->getFunctionType();
1532     if (FT->getNumParams() < 1 || !FT->getParamType(0)->isPointerTy() ||
1533         !(FT->getReturnType()->isIntegerTy() ||
1534           FT->getReturnType()->isVoidTy()))
1535       return 0;
1536
1537     // Check for a constant string.
1538     StringRef Str;
1539     if (!getConstantStringInfo(CI->getArgOperand(0), Str))
1540       return 0;
1541
1542     if (Str.empty() && CI->use_empty()) {
1543       // puts("") -> putchar('\n')
1544       Value *Res = EmitPutChar(B.getInt32('\n'), B, TD, TLI);
1545       if (CI->use_empty() || !Res) return Res;
1546       return B.CreateIntCast(Res, CI->getType(), true);
1547     }
1548
1549     return 0;
1550   }
1551 };
1552
1553 } // end anonymous namespace.
1554
1555 //===----------------------------------------------------------------------===//
1556 // SimplifyLibCalls Pass Implementation
1557 //===----------------------------------------------------------------------===//
1558
1559 namespace {
1560   /// This pass optimizes well known library functions from libc and libm.
1561   ///
1562   class SimplifyLibCalls : public FunctionPass {
1563     TargetLibraryInfo *TLI;
1564
1565     StringMap<LibCallOptimization*> Optimizations;
1566     // String and Memory LibCall Optimizations
1567     StrCatOpt StrCat; StrNCatOpt StrNCat; StrChrOpt StrChr; StrRChrOpt StrRChr;
1568     StrCmpOpt StrCmp; StrNCmpOpt StrNCmp;
1569     StrCpyOpt StrCpy; StrCpyOpt StrCpyChk;
1570     StpCpyOpt StpCpy; StpCpyOpt StpCpyChk;
1571     StrNCpyOpt StrNCpy;
1572     StrLenOpt StrLen; StrPBrkOpt StrPBrk;
1573     StrToOpt StrTo; StrSpnOpt StrSpn; StrCSpnOpt StrCSpn; StrStrOpt StrStr;
1574     MemCmpOpt MemCmp; MemCpyOpt MemCpy; MemMoveOpt MemMove; MemSetOpt MemSet;
1575     // Math Library Optimizations
1576     CosOpt Cos; PowOpt Pow; Exp2Opt Exp2;
1577     UnaryDoubleFPOpt UnaryDoubleFP, UnsafeUnaryDoubleFP;
1578     // Integer Optimizations
1579     FFSOpt FFS; AbsOpt Abs; IsDigitOpt IsDigit; IsAsciiOpt IsAscii;
1580     ToAsciiOpt ToAscii;
1581     // Formatting and IO Optimizations
1582     SPrintFOpt SPrintF; PrintFOpt PrintF;
1583     FWriteOpt FWrite; FPutsOpt FPuts; FPrintFOpt FPrintF;
1584     PutsOpt Puts;
1585
1586     bool Modified;  // This is only used by doInitialization.
1587   public:
1588     static char ID; // Pass identification
1589     SimplifyLibCalls() : FunctionPass(ID), StrCpy(false), StrCpyChk(true),
1590                          StpCpy(false), StpCpyChk(true),
1591                          UnaryDoubleFP(false), UnsafeUnaryDoubleFP(true) {
1592       initializeSimplifyLibCallsPass(*PassRegistry::getPassRegistry());
1593     }
1594     void AddOpt(LibFunc::Func F, LibCallOptimization* Opt);
1595     void AddOpt(LibFunc::Func F1, LibFunc::Func F2, LibCallOptimization* Opt);
1596
1597     void InitOptimizations();
1598     bool runOnFunction(Function &F);
1599
1600     void setDoesNotAccessMemory(Function &F);
1601     void setOnlyReadsMemory(Function &F);
1602     void setDoesNotThrow(Function &F);
1603     void setDoesNotCapture(Function &F, unsigned n);
1604     void setDoesNotAlias(Function &F, unsigned n);
1605     bool doInitialization(Module &M);
1606
1607     void inferPrototypeAttributes(Function &F);
1608     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1609       AU.addRequired<TargetLibraryInfo>();
1610     }
1611   };
1612 } // end anonymous namespace.
1613
1614 char SimplifyLibCalls::ID = 0;
1615
1616 INITIALIZE_PASS_BEGIN(SimplifyLibCalls, "simplify-libcalls",
1617                       "Simplify well-known library calls", false, false)
1618 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
1619 INITIALIZE_PASS_END(SimplifyLibCalls, "simplify-libcalls",
1620                     "Simplify well-known library calls", false, false)
1621
1622 // Public interface to the Simplify LibCalls pass.
1623 FunctionPass *llvm::createSimplifyLibCallsPass() {
1624   return new SimplifyLibCalls();
1625 }
1626
1627 void SimplifyLibCalls::AddOpt(LibFunc::Func F, LibCallOptimization* Opt) {
1628   if (TLI->has(F))
1629     Optimizations[TLI->getName(F)] = Opt;
1630 }
1631
1632 void SimplifyLibCalls::AddOpt(LibFunc::Func F1, LibFunc::Func F2,
1633                               LibCallOptimization* Opt) {
1634   if (TLI->has(F1) && TLI->has(F2))
1635     Optimizations[TLI->getName(F1)] = Opt;
1636 }
1637
1638 /// Optimizations - Populate the Optimizations map with all the optimizations
1639 /// we know.
1640 void SimplifyLibCalls::InitOptimizations() {
1641   // String and Memory LibCall Optimizations
1642   Optimizations["strcat"] = &StrCat;
1643   Optimizations["strncat"] = &StrNCat;
1644   Optimizations["strchr"] = &StrChr;
1645   Optimizations["strrchr"] = &StrRChr;
1646   Optimizations["strcmp"] = &StrCmp;
1647   Optimizations["strncmp"] = &StrNCmp;
1648   Optimizations["strcpy"] = &StrCpy;
1649   Optimizations["strncpy"] = &StrNCpy;
1650   Optimizations["stpcpy"] = &StpCpy;
1651   Optimizations["strlen"] = &StrLen;
1652   Optimizations["strpbrk"] = &StrPBrk;
1653   Optimizations["strtol"] = &StrTo;
1654   Optimizations["strtod"] = &StrTo;
1655   Optimizations["strtof"] = &StrTo;
1656   Optimizations["strtoul"] = &StrTo;
1657   Optimizations["strtoll"] = &StrTo;
1658   Optimizations["strtold"] = &StrTo;
1659   Optimizations["strtoull"] = &StrTo;
1660   Optimizations["strspn"] = &StrSpn;
1661   Optimizations["strcspn"] = &StrCSpn;
1662   Optimizations["strstr"] = &StrStr;
1663   Optimizations["memcmp"] = &MemCmp;
1664   AddOpt(LibFunc::memcpy, &MemCpy);
1665   Optimizations["memmove"] = &MemMove;
1666   AddOpt(LibFunc::memset, &MemSet);
1667
1668   // _chk variants of String and Memory LibCall Optimizations.
1669   Optimizations["__strcpy_chk"] = &StrCpyChk;
1670   Optimizations["__stpcpy_chk"] = &StpCpyChk;
1671
1672   // Math Library Optimizations
1673   Optimizations["cosf"] = &Cos;
1674   Optimizations["cos"] = &Cos;
1675   Optimizations["cosl"] = &Cos;
1676   Optimizations["powf"] = &Pow;
1677   Optimizations["pow"] = &Pow;
1678   Optimizations["powl"] = &Pow;
1679   Optimizations["llvm.pow.f32"] = &Pow;
1680   Optimizations["llvm.pow.f64"] = &Pow;
1681   Optimizations["llvm.pow.f80"] = &Pow;
1682   Optimizations["llvm.pow.f128"] = &Pow;
1683   Optimizations["llvm.pow.ppcf128"] = &Pow;
1684   Optimizations["exp2l"] = &Exp2;
1685   Optimizations["exp2"] = &Exp2;
1686   Optimizations["exp2f"] = &Exp2;
1687   Optimizations["llvm.exp2.ppcf128"] = &Exp2;
1688   Optimizations["llvm.exp2.f128"] = &Exp2;
1689   Optimizations["llvm.exp2.f80"] = &Exp2;
1690   Optimizations["llvm.exp2.f64"] = &Exp2;
1691   Optimizations["llvm.exp2.f32"] = &Exp2;
1692
1693   AddOpt(LibFunc::ceil, LibFunc::ceilf, &UnaryDoubleFP);
1694   AddOpt(LibFunc::fabs, LibFunc::fabsf, &UnaryDoubleFP);
1695   AddOpt(LibFunc::floor, LibFunc::floorf, &UnaryDoubleFP);
1696   AddOpt(LibFunc::rint, LibFunc::rintf, &UnaryDoubleFP);
1697   AddOpt(LibFunc::round, LibFunc::roundf, &UnaryDoubleFP);
1698   AddOpt(LibFunc::nearbyint, LibFunc::nearbyintf, &UnaryDoubleFP);
1699   AddOpt(LibFunc::trunc, LibFunc::truncf, &UnaryDoubleFP);
1700
1701   if(UnsafeFPShrink) {
1702     AddOpt(LibFunc::acos, LibFunc::acosf, &UnsafeUnaryDoubleFP);
1703     AddOpt(LibFunc::acosh, LibFunc::acoshf, &UnsafeUnaryDoubleFP);
1704     AddOpt(LibFunc::asin, LibFunc::asinf, &UnsafeUnaryDoubleFP);
1705     AddOpt(LibFunc::asinh, LibFunc::asinhf, &UnsafeUnaryDoubleFP);
1706     AddOpt(LibFunc::atan, LibFunc::atanf, &UnsafeUnaryDoubleFP);
1707     AddOpt(LibFunc::atanh, LibFunc::atanhf, &UnsafeUnaryDoubleFP);
1708     AddOpt(LibFunc::cbrt, LibFunc::cbrtf, &UnsafeUnaryDoubleFP);
1709     AddOpt(LibFunc::cosh, LibFunc::coshf, &UnsafeUnaryDoubleFP);
1710     AddOpt(LibFunc::exp, LibFunc::expf, &UnsafeUnaryDoubleFP);
1711     AddOpt(LibFunc::exp10, LibFunc::exp10f, &UnsafeUnaryDoubleFP);
1712     AddOpt(LibFunc::expm1, LibFunc::expm1f, &UnsafeUnaryDoubleFP);
1713     AddOpt(LibFunc::log, LibFunc::logf, &UnsafeUnaryDoubleFP);
1714     AddOpt(LibFunc::log10, LibFunc::log10f, &UnsafeUnaryDoubleFP);
1715     AddOpt(LibFunc::log1p, LibFunc::log1pf, &UnsafeUnaryDoubleFP);
1716     AddOpt(LibFunc::log2, LibFunc::log2f, &UnsafeUnaryDoubleFP);
1717     AddOpt(LibFunc::logb, LibFunc::logbf, &UnsafeUnaryDoubleFP);
1718     AddOpt(LibFunc::sin, LibFunc::sinf, &UnsafeUnaryDoubleFP);
1719     AddOpt(LibFunc::sinh, LibFunc::sinhf, &UnsafeUnaryDoubleFP);
1720     AddOpt(LibFunc::sqrt, LibFunc::sqrtf, &UnsafeUnaryDoubleFP);
1721     AddOpt(LibFunc::tan, LibFunc::tanf, &UnsafeUnaryDoubleFP);
1722     AddOpt(LibFunc::tanh, LibFunc::tanhf, &UnsafeUnaryDoubleFP);
1723   }
1724
1725   // Integer Optimizations
1726   Optimizations["ffs"] = &FFS;
1727   Optimizations["ffsl"] = &FFS;
1728   Optimizations["ffsll"] = &FFS;
1729   Optimizations["abs"] = &Abs;
1730   Optimizations["labs"] = &Abs;
1731   Optimizations["llabs"] = &Abs;
1732   Optimizations["isdigit"] = &IsDigit;
1733   Optimizations["isascii"] = &IsAscii;
1734   Optimizations["toascii"] = &ToAscii;
1735
1736   // Formatting and IO Optimizations
1737   Optimizations["sprintf"] = &SPrintF;
1738   Optimizations["printf"] = &PrintF;
1739   AddOpt(LibFunc::fwrite, &FWrite);
1740   AddOpt(LibFunc::fputs, &FPuts);
1741   Optimizations["fprintf"] = &FPrintF;
1742   Optimizations["puts"] = &Puts;
1743 }
1744
1745
1746 /// runOnFunction - Top level algorithm.
1747 ///
1748 bool SimplifyLibCalls::runOnFunction(Function &F) {
1749   TLI = &getAnalysis<TargetLibraryInfo>();
1750
1751   if (Optimizations.empty())
1752     InitOptimizations();
1753
1754   const DataLayout *TD = getAnalysisIfAvailable<DataLayout>();
1755
1756   IRBuilder<> Builder(F.getContext());
1757
1758   bool Changed = false;
1759   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
1760     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
1761       // Ignore non-calls.
1762       CallInst *CI = dyn_cast<CallInst>(I++);
1763       if (!CI) continue;
1764
1765       // Ignore indirect calls and calls to non-external functions.
1766       Function *Callee = CI->getCalledFunction();
1767       if (Callee == 0 || !Callee->isDeclaration() ||
1768           !(Callee->hasExternalLinkage() || Callee->hasDLLImportLinkage()))
1769         continue;
1770
1771       // Ignore unknown calls.
1772       LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
1773       if (!LCO) continue;
1774
1775       // Set the builder to the instruction after the call.
1776       Builder.SetInsertPoint(BB, I);
1777
1778       // Use debug location of CI for all new instructions.
1779       Builder.SetCurrentDebugLocation(CI->getDebugLoc());
1780
1781       // Try to optimize this call.
1782       Value *Result = LCO->OptimizeCall(CI, TD, TLI, Builder);
1783       if (Result == 0) continue;
1784
1785       DEBUG(dbgs() << "SimplifyLibCalls simplified: " << *CI;
1786             dbgs() << "  into: " << *Result << "\n");
1787
1788       // Something changed!
1789       Changed = true;
1790       ++NumSimplified;
1791
1792       // Inspect the instruction after the call (which was potentially just
1793       // added) next.
1794       I = CI; ++I;
1795
1796       if (CI != Result && !CI->use_empty()) {
1797         CI->replaceAllUsesWith(Result);
1798         if (!Result->hasName())
1799           Result->takeName(CI);
1800       }
1801       CI->eraseFromParent();
1802     }
1803   }
1804   return Changed;
1805 }
1806
1807 // Utility methods for doInitialization.
1808
1809 void SimplifyLibCalls::setDoesNotAccessMemory(Function &F) {
1810   if (!F.doesNotAccessMemory()) {
1811     F.setDoesNotAccessMemory();
1812     ++NumAnnotated;
1813     Modified = true;
1814   }
1815 }
1816 void SimplifyLibCalls::setOnlyReadsMemory(Function &F) {
1817   if (!F.onlyReadsMemory()) {
1818     F.setOnlyReadsMemory();
1819     ++NumAnnotated;
1820     Modified = true;
1821   }
1822 }
1823 void SimplifyLibCalls::setDoesNotThrow(Function &F) {
1824   if (!F.doesNotThrow()) {
1825     F.setDoesNotThrow();
1826     ++NumAnnotated;
1827     Modified = true;
1828   }
1829 }
1830 void SimplifyLibCalls::setDoesNotCapture(Function &F, unsigned n) {
1831   if (!F.doesNotCapture(n)) {
1832     F.setDoesNotCapture(n);
1833     ++NumAnnotated;
1834     Modified = true;
1835   }
1836 }
1837 void SimplifyLibCalls::setDoesNotAlias(Function &F, unsigned n) {
1838   if (!F.doesNotAlias(n)) {
1839     F.setDoesNotAlias(n);
1840     ++NumAnnotated;
1841     Modified = true;
1842   }
1843 }
1844
1845
1846 void SimplifyLibCalls::inferPrototypeAttributes(Function &F) {
1847   FunctionType *FTy = F.getFunctionType();
1848
1849   StringRef Name = F.getName();
1850   switch (Name[0]) {
1851   case 's':
1852     if (Name == "strlen") {
1853       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1854         return;
1855       setOnlyReadsMemory(F);
1856       setDoesNotThrow(F);
1857       setDoesNotCapture(F, 1);
1858     } else if (Name == "strchr" ||
1859                Name == "strrchr") {
1860       if (FTy->getNumParams() != 2 ||
1861           !FTy->getParamType(0)->isPointerTy() ||
1862           !FTy->getParamType(1)->isIntegerTy())
1863         return;
1864       setOnlyReadsMemory(F);
1865       setDoesNotThrow(F);
1866     } else if (Name == "strcpy" ||
1867                Name == "stpcpy" ||
1868                Name == "strcat" ||
1869                Name == "strtol" ||
1870                Name == "strtod" ||
1871                Name == "strtof" ||
1872                Name == "strtoul" ||
1873                Name == "strtoll" ||
1874                Name == "strtold" ||
1875                Name == "strncat" ||
1876                Name == "strncpy" ||
1877                Name == "stpncpy" ||
1878                Name == "strtoull") {
1879       if (FTy->getNumParams() < 2 ||
1880           !FTy->getParamType(1)->isPointerTy())
1881         return;
1882       setDoesNotThrow(F);
1883       setDoesNotCapture(F, 2);
1884     } else if (Name == "strxfrm") {
1885       if (FTy->getNumParams() != 3 ||
1886           !FTy->getParamType(0)->isPointerTy() ||
1887           !FTy->getParamType(1)->isPointerTy())
1888         return;
1889       setDoesNotThrow(F);
1890       setDoesNotCapture(F, 1);
1891       setDoesNotCapture(F, 2);
1892     } else if (Name == "strcmp" ||
1893                Name == "strspn" ||
1894                Name == "strncmp" ||
1895                Name == "strcspn" ||
1896                Name == "strcoll" ||
1897                Name == "strcasecmp" ||
1898                Name == "strncasecmp") {
1899       if (FTy->getNumParams() < 2 ||
1900           !FTy->getParamType(0)->isPointerTy() ||
1901           !FTy->getParamType(1)->isPointerTy())
1902         return;
1903       setOnlyReadsMemory(F);
1904       setDoesNotThrow(F);
1905       setDoesNotCapture(F, 1);
1906       setDoesNotCapture(F, 2);
1907     } else if (Name == "strstr" ||
1908                Name == "strpbrk") {
1909       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1910         return;
1911       setOnlyReadsMemory(F);
1912       setDoesNotThrow(F);
1913       setDoesNotCapture(F, 2);
1914     } else if (Name == "strtok" ||
1915                Name == "strtok_r") {
1916       if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
1917         return;
1918       setDoesNotThrow(F);
1919       setDoesNotCapture(F, 2);
1920     } else if (Name == "scanf" ||
1921                Name == "setbuf" ||
1922                Name == "setvbuf") {
1923       if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
1924         return;
1925       setDoesNotThrow(F);
1926       setDoesNotCapture(F, 1);
1927     } else if (Name == "strdup" ||
1928                Name == "strndup") {
1929       if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() ||
1930           !FTy->getParamType(0)->isPointerTy())
1931         return;
1932       setDoesNotThrow(F);
1933       setDoesNotAlias(F, 0);
1934       setDoesNotCapture(F, 1);
1935     } else if (Name == "stat" ||
1936                Name == "sscanf" ||
1937                Name == "sprintf" ||
1938                Name == "statvfs") {
1939       if (FTy->getNumParams() < 2 ||
1940           !FTy->getParamType(0)->isPointerTy() ||
1941           !FTy->getParamType(1)->isPointerTy())
1942         return;
1943       setDoesNotThrow(F);
1944       setDoesNotCapture(F, 1);
1945       setDoesNotCapture(F, 2);
1946     } else if (Name == "snprintf") {
1947       if (FTy->getNumParams() != 3 ||
1948           !FTy->getParamType(0)->isPointerTy() ||
1949           !FTy->getParamType(2)->isPointerTy())
1950         return;
1951       setDoesNotThrow(F);
1952       setDoesNotCapture(F, 1);
1953       setDoesNotCapture(F, 3);
1954     } else if (Name == "setitimer") {
1955       if (FTy->getNumParams() != 3 ||
1956           !FTy->getParamType(1)->isPointerTy() ||
1957           !FTy->getParamType(2)->isPointerTy())
1958         return;
1959       setDoesNotThrow(F);
1960       setDoesNotCapture(F, 2);
1961       setDoesNotCapture(F, 3);
1962     } else if (Name == "system") {
1963       if (FTy->getNumParams() != 1 ||
1964           !FTy->getParamType(0)->isPointerTy())
1965         return;
1966       // May throw; "system" is a valid pthread cancellation point.
1967       setDoesNotCapture(F, 1);
1968     }
1969     break;
1970   case 'm':
1971     if (Name == "malloc") {
1972       if (FTy->getNumParams() != 1 ||
1973           !FTy->getReturnType()->isPointerTy())
1974         return;
1975       setDoesNotThrow(F);
1976       setDoesNotAlias(F, 0);
1977     } else if (Name == "memcmp") {
1978       if (FTy->getNumParams() != 3 ||
1979           !FTy->getParamType(0)->isPointerTy() ||
1980           !FTy->getParamType(1)->isPointerTy())
1981         return;
1982       setOnlyReadsMemory(F);
1983       setDoesNotThrow(F);
1984       setDoesNotCapture(F, 1);
1985       setDoesNotCapture(F, 2);
1986     } else if (Name == "memchr" ||
1987                Name == "memrchr") {
1988       if (FTy->getNumParams() != 3)
1989         return;
1990       setOnlyReadsMemory(F);
1991       setDoesNotThrow(F);
1992     } else if (Name == "modf" ||
1993                Name == "modff" ||
1994                Name == "modfl" ||
1995                Name == "memcpy" ||
1996                Name == "memccpy" ||
1997                Name == "memmove") {
1998       if (FTy->getNumParams() < 2 ||
1999           !FTy->getParamType(1)->isPointerTy())
2000         return;
2001       setDoesNotThrow(F);
2002       setDoesNotCapture(F, 2);
2003     } else if (Name == "memalign") {
2004       if (!FTy->getReturnType()->isPointerTy())
2005         return;
2006       setDoesNotAlias(F, 0);
2007     } else if (Name == "mkdir" ||
2008                Name == "mktime") {
2009       if (FTy->getNumParams() == 0 ||
2010           !FTy->getParamType(0)->isPointerTy())
2011         return;
2012       setDoesNotThrow(F);
2013       setDoesNotCapture(F, 1);
2014     }
2015     break;
2016   case 'r':
2017     if (Name == "realloc") {
2018       if (FTy->getNumParams() != 2 ||
2019           !FTy->getParamType(0)->isPointerTy() ||
2020           !FTy->getReturnType()->isPointerTy())
2021         return;
2022       setDoesNotThrow(F);
2023       setDoesNotAlias(F, 0);
2024       setDoesNotCapture(F, 1);
2025     } else if (Name == "read") {
2026       if (FTy->getNumParams() != 3 ||
2027           !FTy->getParamType(1)->isPointerTy())
2028         return;
2029       // May throw; "read" is a valid pthread cancellation point.
2030       setDoesNotCapture(F, 2);
2031     } else if (Name == "rmdir" ||
2032                Name == "rewind" ||
2033                Name == "remove" ||
2034                Name == "realpath") {
2035       if (FTy->getNumParams() < 1 ||
2036           !FTy->getParamType(0)->isPointerTy())
2037         return;
2038       setDoesNotThrow(F);
2039       setDoesNotCapture(F, 1);
2040     } else if (Name == "rename" ||
2041                Name == "readlink") {
2042       if (FTy->getNumParams() < 2 ||
2043           !FTy->getParamType(0)->isPointerTy() ||
2044           !FTy->getParamType(1)->isPointerTy())
2045         return;
2046       setDoesNotThrow(F);
2047       setDoesNotCapture(F, 1);
2048       setDoesNotCapture(F, 2);
2049     }
2050     break;
2051   case 'w':
2052     if (Name == "write") {
2053       if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
2054         return;
2055       // May throw; "write" is a valid pthread cancellation point.
2056       setDoesNotCapture(F, 2);
2057     }
2058     break;
2059   case 'b':
2060     if (Name == "bcopy") {
2061       if (FTy->getNumParams() != 3 ||
2062           !FTy->getParamType(0)->isPointerTy() ||
2063           !FTy->getParamType(1)->isPointerTy())
2064         return;
2065       setDoesNotThrow(F);
2066       setDoesNotCapture(F, 1);
2067       setDoesNotCapture(F, 2);
2068     } else if (Name == "bcmp") {
2069       if (FTy->getNumParams() != 3 ||
2070           !FTy->getParamType(0)->isPointerTy() ||
2071           !FTy->getParamType(1)->isPointerTy())
2072         return;
2073       setDoesNotThrow(F);
2074       setOnlyReadsMemory(F);
2075       setDoesNotCapture(F, 1);
2076       setDoesNotCapture(F, 2);
2077     } else if (Name == "bzero") {
2078       if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
2079         return;
2080       setDoesNotThrow(F);
2081       setDoesNotCapture(F, 1);
2082     }
2083     break;
2084   case 'c':
2085     if (Name == "calloc") {
2086       if (FTy->getNumParams() != 2 ||
2087           !FTy->getReturnType()->isPointerTy())
2088         return;
2089       setDoesNotThrow(F);
2090       setDoesNotAlias(F, 0);
2091     } else if (Name == "chmod" ||
2092                Name == "chown" ||
2093                Name == "ctermid" ||
2094                Name == "clearerr" ||
2095                Name == "closedir") {
2096       if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
2097         return;
2098       setDoesNotThrow(F);
2099       setDoesNotCapture(F, 1);
2100     }
2101     break;
2102   case 'a':
2103     if (Name == "atoi" ||
2104         Name == "atol" ||
2105         Name == "atof" ||
2106         Name == "atoll") {
2107       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
2108         return;
2109       setDoesNotThrow(F);
2110       setOnlyReadsMemory(F);
2111       setDoesNotCapture(F, 1);
2112     } else if (Name == "access") {
2113       if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
2114         return;
2115       setDoesNotThrow(F);
2116       setDoesNotCapture(F, 1);
2117     }
2118     break;
2119   case 'f':
2120     if (Name == "fopen") {
2121       if (FTy->getNumParams() != 2 ||
2122           !FTy->getReturnType()->isPointerTy() ||
2123           !FTy->getParamType(0)->isPointerTy() ||
2124           !FTy->getParamType(1)->isPointerTy())
2125         return;
2126       setDoesNotThrow(F);
2127       setDoesNotAlias(F, 0);
2128       setDoesNotCapture(F, 1);
2129       setDoesNotCapture(F, 2);
2130     } else if (Name == "fdopen") {
2131       if (FTy->getNumParams() != 2 ||
2132           !FTy->getReturnType()->isPointerTy() ||
2133           !FTy->getParamType(1)->isPointerTy())
2134         return;
2135       setDoesNotThrow(F);
2136       setDoesNotAlias(F, 0);
2137       setDoesNotCapture(F, 2);
2138     } else if (Name == "feof" ||
2139                Name == "free" ||
2140                Name == "fseek" ||
2141                Name == "ftell" ||
2142                Name == "fgetc" ||
2143                Name == "fseeko" ||
2144                Name == "ftello" ||
2145                Name == "fileno" ||
2146                Name == "fflush" ||
2147                Name == "fclose" ||
2148                Name == "fsetpos" ||
2149                Name == "flockfile" ||
2150                Name == "funlockfile" ||
2151                Name == "ftrylockfile") {
2152       if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
2153         return;
2154       setDoesNotThrow(F);
2155       setDoesNotCapture(F, 1);
2156     } else if (Name == "ferror") {
2157       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
2158         return;
2159       setDoesNotThrow(F);
2160       setDoesNotCapture(F, 1);
2161       setOnlyReadsMemory(F);
2162     } else if (Name == "fputc" ||
2163                Name == "fstat" ||
2164                Name == "frexp" ||
2165                Name == "frexpf" ||
2166                Name == "frexpl" ||
2167                Name == "fstatvfs") {
2168       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
2169         return;
2170       setDoesNotThrow(F);
2171       setDoesNotCapture(F, 2);
2172     } else if (Name == "fgets") {
2173       if (FTy->getNumParams() != 3 ||
2174           !FTy->getParamType(0)->isPointerTy() ||
2175           !FTy->getParamType(2)->isPointerTy())
2176         return;
2177       setDoesNotThrow(F);
2178       setDoesNotCapture(F, 3);
2179     } else if (Name == "fread" ||
2180                Name == "fwrite") {
2181       if (FTy->getNumParams() != 4 ||
2182           !FTy->getParamType(0)->isPointerTy() ||
2183           !FTy->getParamType(3)->isPointerTy())
2184         return;
2185       setDoesNotThrow(F);
2186       setDoesNotCapture(F, 1);
2187       setDoesNotCapture(F, 4);
2188     } else if (Name == "fputs" ||
2189                Name == "fscanf" ||
2190                Name == "fprintf" ||
2191                Name == "fgetpos") {
2192       if (FTy->getNumParams() < 2 ||
2193           !FTy->getParamType(0)->isPointerTy() ||
2194           !FTy->getParamType(1)->isPointerTy())
2195         return;
2196       setDoesNotThrow(F);
2197       setDoesNotCapture(F, 1);
2198       setDoesNotCapture(F, 2);
2199     }
2200     break;
2201   case 'g':
2202     if (Name == "getc" ||
2203         Name == "getlogin_r" ||
2204         Name == "getc_unlocked") {
2205       if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
2206         return;
2207       setDoesNotThrow(F);
2208       setDoesNotCapture(F, 1);
2209     } else if (Name == "getenv") {
2210       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
2211         return;
2212       setDoesNotThrow(F);
2213       setOnlyReadsMemory(F);
2214       setDoesNotCapture(F, 1);
2215     } else if (Name == "gets" ||
2216                Name == "getchar") {
2217       setDoesNotThrow(F);
2218     } else if (Name == "getitimer") {
2219       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
2220         return;
2221       setDoesNotThrow(F);
2222       setDoesNotCapture(F, 2);
2223     } else if (Name == "getpwnam") {
2224       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
2225         return;
2226       setDoesNotThrow(F);
2227       setDoesNotCapture(F, 1);
2228     }
2229     break;
2230   case 'u':
2231     if (Name == "ungetc") {
2232       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
2233         return;
2234       setDoesNotThrow(F);
2235       setDoesNotCapture(F, 2);
2236     } else if (Name == "uname" ||
2237                Name == "unlink" ||
2238                Name == "unsetenv") {
2239       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
2240         return;
2241       setDoesNotThrow(F);
2242       setDoesNotCapture(F, 1);
2243     } else if (Name == "utime" ||
2244                Name == "utimes") {
2245       if (FTy->getNumParams() != 2 ||
2246           !FTy->getParamType(0)->isPointerTy() ||
2247           !FTy->getParamType(1)->isPointerTy())
2248         return;
2249       setDoesNotThrow(F);
2250       setDoesNotCapture(F, 1);
2251       setDoesNotCapture(F, 2);
2252     }
2253     break;
2254   case 'p':
2255     if (Name == "putc") {
2256       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
2257         return;
2258       setDoesNotThrow(F);
2259       setDoesNotCapture(F, 2);
2260     } else if (Name == "puts" ||
2261                Name == "printf" ||
2262                Name == "perror") {
2263       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
2264         return;
2265       setDoesNotThrow(F);
2266       setDoesNotCapture(F, 1);
2267     } else if (Name == "pread" ||
2268                Name == "pwrite") {
2269       if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
2270         return;
2271       // May throw; these are valid pthread cancellation points.
2272       setDoesNotCapture(F, 2);
2273     } else if (Name == "putchar") {
2274       setDoesNotThrow(F);
2275     } else if (Name == "popen") {
2276       if (FTy->getNumParams() != 2 ||
2277           !FTy->getReturnType()->isPointerTy() ||
2278           !FTy->getParamType(0)->isPointerTy() ||
2279           !FTy->getParamType(1)->isPointerTy())
2280         return;
2281       setDoesNotThrow(F);
2282       setDoesNotAlias(F, 0);
2283       setDoesNotCapture(F, 1);
2284       setDoesNotCapture(F, 2);
2285     } else if (Name == "pclose") {
2286       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
2287         return;
2288       setDoesNotThrow(F);
2289       setDoesNotCapture(F, 1);
2290     }
2291     break;
2292   case 'v':
2293     if (Name == "vscanf") {
2294       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
2295         return;
2296       setDoesNotThrow(F);
2297       setDoesNotCapture(F, 1);
2298     } else if (Name == "vsscanf" ||
2299                Name == "vfscanf") {
2300       if (FTy->getNumParams() != 3 ||
2301           !FTy->getParamType(1)->isPointerTy() ||
2302           !FTy->getParamType(2)->isPointerTy())
2303         return;
2304       setDoesNotThrow(F);
2305       setDoesNotCapture(F, 1);
2306       setDoesNotCapture(F, 2);
2307     } else if (Name == "valloc") {
2308       if (!FTy->getReturnType()->isPointerTy())
2309         return;
2310       setDoesNotThrow(F);
2311       setDoesNotAlias(F, 0);
2312     } else if (Name == "vprintf") {
2313       if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
2314         return;
2315       setDoesNotThrow(F);
2316       setDoesNotCapture(F, 1);
2317     } else if (Name == "vfprintf" ||
2318                Name == "vsprintf") {
2319       if (FTy->getNumParams() != 3 ||
2320           !FTy->getParamType(0)->isPointerTy() ||
2321           !FTy->getParamType(1)->isPointerTy())
2322         return;
2323       setDoesNotThrow(F);
2324       setDoesNotCapture(F, 1);
2325       setDoesNotCapture(F, 2);
2326     } else if (Name == "vsnprintf") {
2327       if (FTy->getNumParams() != 4 ||
2328           !FTy->getParamType(0)->isPointerTy() ||
2329           !FTy->getParamType(2)->isPointerTy())
2330         return;
2331       setDoesNotThrow(F);
2332       setDoesNotCapture(F, 1);
2333       setDoesNotCapture(F, 3);
2334     }
2335     break;
2336   case 'o':
2337     if (Name == "open") {
2338       if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
2339         return;
2340       // May throw; "open" is a valid pthread cancellation point.
2341       setDoesNotCapture(F, 1);
2342     } else if (Name == "opendir") {
2343       if (FTy->getNumParams() != 1 ||
2344           !FTy->getReturnType()->isPointerTy() ||
2345           !FTy->getParamType(0)->isPointerTy())
2346         return;
2347       setDoesNotThrow(F);
2348       setDoesNotAlias(F, 0);
2349       setDoesNotCapture(F, 1);
2350     }
2351     break;
2352   case 't':
2353     if (Name == "tmpfile") {
2354       if (!FTy->getReturnType()->isPointerTy())
2355         return;
2356       setDoesNotThrow(F);
2357       setDoesNotAlias(F, 0);
2358     } else if (Name == "times") {
2359       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
2360         return;
2361       setDoesNotThrow(F);
2362       setDoesNotCapture(F, 1);
2363     }
2364     break;
2365   case 'h':
2366     if (Name == "htonl" ||
2367         Name == "htons") {
2368       setDoesNotThrow(F);
2369       setDoesNotAccessMemory(F);
2370     }
2371     break;
2372   case 'n':
2373     if (Name == "ntohl" ||
2374         Name == "ntohs") {
2375       setDoesNotThrow(F);
2376       setDoesNotAccessMemory(F);
2377     }
2378     break;
2379   case 'l':
2380     if (Name == "lstat") {
2381       if (FTy->getNumParams() != 2 ||
2382           !FTy->getParamType(0)->isPointerTy() ||
2383           !FTy->getParamType(1)->isPointerTy())
2384         return;
2385       setDoesNotThrow(F);
2386       setDoesNotCapture(F, 1);
2387       setDoesNotCapture(F, 2);
2388     } else if (Name == "lchown") {
2389       if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy())
2390         return;
2391       setDoesNotThrow(F);
2392       setDoesNotCapture(F, 1);
2393     }
2394     break;
2395   case 'q':
2396     if (Name == "qsort") {
2397       if (FTy->getNumParams() != 4 || !FTy->getParamType(3)->isPointerTy())
2398         return;
2399       // May throw; places call through function pointer.
2400       setDoesNotCapture(F, 4);
2401     }
2402     break;
2403   case '_':
2404     if (Name == "__strdup" ||
2405         Name == "__strndup") {
2406       if (FTy->getNumParams() < 1 ||
2407           !FTy->getReturnType()->isPointerTy() ||
2408           !FTy->getParamType(0)->isPointerTy())
2409         return;
2410       setDoesNotThrow(F);
2411       setDoesNotAlias(F, 0);
2412       setDoesNotCapture(F, 1);
2413     } else if (Name == "__strtok_r") {
2414       if (FTy->getNumParams() != 3 ||
2415           !FTy->getParamType(1)->isPointerTy())
2416         return;
2417       setDoesNotThrow(F);
2418       setDoesNotCapture(F, 2);
2419     } else if (Name == "_IO_getc") {
2420       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
2421         return;
2422       setDoesNotThrow(F);
2423       setDoesNotCapture(F, 1);
2424     } else if (Name == "_IO_putc") {
2425       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
2426         return;
2427       setDoesNotThrow(F);
2428       setDoesNotCapture(F, 2);
2429     }
2430     break;
2431   case 1:
2432     if (Name == "\1__isoc99_scanf") {
2433       if (FTy->getNumParams() < 1 ||
2434           !FTy->getParamType(0)->isPointerTy())
2435         return;
2436       setDoesNotThrow(F);
2437       setDoesNotCapture(F, 1);
2438     } else if (Name == "\1stat64" ||
2439                Name == "\1lstat64" ||
2440                Name == "\1statvfs64" ||
2441                Name == "\1__isoc99_sscanf") {
2442       if (FTy->getNumParams() < 1 ||
2443           !FTy->getParamType(0)->isPointerTy() ||
2444           !FTy->getParamType(1)->isPointerTy())
2445         return;
2446       setDoesNotThrow(F);
2447       setDoesNotCapture(F, 1);
2448       setDoesNotCapture(F, 2);
2449     } else if (Name == "\1fopen64") {
2450       if (FTy->getNumParams() != 2 ||
2451           !FTy->getReturnType()->isPointerTy() ||
2452           !FTy->getParamType(0)->isPointerTy() ||
2453           !FTy->getParamType(1)->isPointerTy())
2454         return;
2455       setDoesNotThrow(F);
2456       setDoesNotAlias(F, 0);
2457       setDoesNotCapture(F, 1);
2458       setDoesNotCapture(F, 2);
2459     } else if (Name == "\1fseeko64" ||
2460                Name == "\1ftello64") {
2461       if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
2462         return;
2463       setDoesNotThrow(F);
2464       setDoesNotCapture(F, 1);
2465     } else if (Name == "\1tmpfile64") {
2466       if (!FTy->getReturnType()->isPointerTy())
2467         return;
2468       setDoesNotThrow(F);
2469       setDoesNotAlias(F, 0);
2470     } else if (Name == "\1fstat64" ||
2471                Name == "\1fstatvfs64") {
2472       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
2473         return;
2474       setDoesNotThrow(F);
2475       setDoesNotCapture(F, 2);
2476     } else if (Name == "\1open64") {
2477       if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
2478         return;
2479       // May throw; "open" is a valid pthread cancellation point.
2480       setDoesNotCapture(F, 1);
2481     }
2482     break;
2483   }
2484 }
2485
2486 /// doInitialization - Add attributes to well-known functions.
2487 ///
2488 bool SimplifyLibCalls::doInitialization(Module &M) {
2489   Modified = false;
2490   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
2491     Function &F = *I;
2492     if (F.isDeclaration() && F.hasName())
2493       inferPrototypeAttributes(F);
2494   }
2495   return Modified;
2496 }
2497
2498 // TODO:
2499 //   Additional cases that we need to add to this file:
2500 //
2501 // cbrt:
2502 //   * cbrt(expN(X))  -> expN(x/3)
2503 //   * cbrt(sqrt(x))  -> pow(x,1/6)
2504 //   * cbrt(sqrt(x))  -> pow(x,1/9)
2505 //
2506 // exp, expf, expl:
2507 //   * exp(log(x))  -> x
2508 //
2509 // log, logf, logl:
2510 //   * log(exp(x))   -> x
2511 //   * log(x**y)     -> y*log(x)
2512 //   * log(exp(y))   -> y*log(e)
2513 //   * log(exp2(y))  -> y*log(2)
2514 //   * log(exp10(y)) -> y*log(10)
2515 //   * log(sqrt(x))  -> 0.5*log(x)
2516 //   * log(pow(x,y)) -> y*log(x)
2517 //
2518 // lround, lroundf, lroundl:
2519 //   * lround(cnst) -> cnst'
2520 //
2521 // pow, powf, powl:
2522 //   * pow(exp(x),y)  -> exp(x*y)
2523 //   * pow(sqrt(x),y) -> pow(x,y*0.5)
2524 //   * pow(pow(x,y),z)-> pow(x,y*z)
2525 //
2526 // round, roundf, roundl:
2527 //   * round(cnst) -> cnst'
2528 //
2529 // signbit:
2530 //   * signbit(cnst) -> cnst'
2531 //   * signbit(nncst) -> 0 (if pstv is a non-negative constant)
2532 //
2533 // sqrt, sqrtf, sqrtl:
2534 //   * sqrt(expN(x))  -> expN(x*0.5)
2535 //   * sqrt(Nroot(x)) -> pow(x,1/(2*N))
2536 //   * sqrt(pow(x,y)) -> pow(|x|,y*0.5)
2537 //
2538 // strchr:
2539 //   * strchr(p, 0) -> strlen(p)
2540 // tan, tanf, tanl:
2541 //   * tan(atan(x)) -> x
2542 //
2543 // trunc, truncf, truncl:
2544 //   * trunc(cnst) -> cnst'
2545 //
2546 //