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