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