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