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     if (Len == 1) { // memcmp(S1,S2,1) -> *LHS - *RHS
 562       Value *LHSV = B.CreateLoad(CastToCStr(LHS, B), "lhsv");
 563       Value *RHSV = B.CreateLoad(CastToCStr(RHS, B), "rhsv");
 564       return B.CreateSExt(B.CreateSub(LHSV, RHSV, "chardiff"), CI->getType());
 565     }
 566
 567     // Constant folding: memcmp(x, y, l) -> cnst (all arguments are constant)
 568     std::string LHSStr, RHSStr;
 569     if (GetConstantStringInfo(LHS, LHSStr) &&
 570         GetConstantStringInfo(RHS, RHSStr)) {
 571       // Make sure we're not reading out-of-bounds memory.
 572       if (Len > LHSStr.length() || Len > RHSStr.length())
 573         return 0;
 574       uint64_t Ret = memcmp(LHSStr.data(), RHSStr.data(), Len);
 575       return ConstantInt::get(CI->getType(), Ret);
 576     }
 577
 578     return 0;
 579   }
 580 };
 581
 582 //===---------------------------------------===//
 583 // 'memcpy' Optimizations
 584
 585 struct MemCpyOpt : public LibCallOptimization {
 586   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 587     // These optimizations require TargetData.
 588     if (!TD) return 0;
 589
 590     const FunctionType *FT = Callee->getFunctionType();
 591     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 592         !FT->getParamType(0)->isPointerTy() ||
 593         !FT->getParamType(1)->isPointerTy() ||
 594         FT->getParamType(2) != TD->getIntPtrType(*Context))
 595       return 0;
 596
 597     // memcpy(x, y, n) -> llvm.memcpy(x, y, n, 1)
 598     EmitMemCpy(CI->getOperand(1), CI->getOperand(2),
 599                CI->getOperand(3), 1, false, B, TD);
 600     return CI->getOperand(1);
 601   }
 602 };
 603
 604 //===---------------------------------------===//
 605 // 'memmove' Optimizations
 606
 607 struct MemMoveOpt : public LibCallOptimization {
 608   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 609     // These optimizations require TargetData.
 610     if (!TD) return 0;
 611
 612     const FunctionType *FT = Callee->getFunctionType();
 613     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 614         !FT->getParamType(0)->isPointerTy() ||
 615         !FT->getParamType(1)->isPointerTy() ||
 616         FT->getParamType(2) != TD->getIntPtrType(*Context))
 617       return 0;
 618
 619     // memmove(x, y, n) -> llvm.memmove(x, y, n, 1)
 620     EmitMemMove(CI->getOperand(1), CI->getOperand(2),
 621                 CI->getOperand(3), 1, false, B, TD);
 622     return CI->getOperand(1);
 623   }
 624 };
 625
 626 //===---------------------------------------===//
 627 // 'memset' Optimizations
 628
 629 struct MemSetOpt : public LibCallOptimization {
 630   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 631     // These optimizations require TargetData.
 632     if (!TD) return 0;
 633
 634     const FunctionType *FT = Callee->getFunctionType();
 635     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 636         !FT->getParamType(0)->isPointerTy() ||
 637         !FT->getParamType(1)->isIntegerTy() ||
 638         FT->getParamType(2) != TD->getIntPtrType(*Context))
 639       return 0;
 640
 641     // memset(p, v, n) -> llvm.memset(p, v, n, 1)
 642     Value *Val = B.CreateIntCast(CI->getOperand(2), Type::getInt8Ty(*Context),
 643                                  false);
 644     EmitMemSet(CI->getOperand(1), Val,  CI->getOperand(3), false, B, TD);
 645     return CI->getOperand(1);
 646   }
 647 };
 648
 649 //===----------------------------------------------------------------------===//
 650 // Math Library Optimizations
 651 //===----------------------------------------------------------------------===//
 652
 653 //===---------------------------------------===//
 654 // 'pow*' Optimizations
 655
 656 struct PowOpt : public LibCallOptimization {
 657   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 658     const FunctionType *FT = Callee->getFunctionType();
 659     // Just make sure this has 2 arguments of the same FP type, which match the
 660     // result type.
 661     if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) ||
 662         FT->getParamType(0) != FT->getParamType(1) ||
 663         !FT->getParamType(0)->isFloatingPointTy())
 664       return 0;
 665
 666     Value *Op1 = CI->getOperand(1), *Op2 = CI->getOperand(2);
 667     if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) {
 668       if (Op1C->isExactlyValue(1.0))  // pow(1.0, x) -> 1.0
 669         return Op1C;
 670       if (Op1C->isExactlyValue(2.0))  // pow(2.0, x) -> exp2(x)
 671         return EmitUnaryFloatFnCall(Op2, "exp2", B, Callee->getAttributes());
 672     }
 673
 674     ConstantFP *Op2C = dyn_cast<ConstantFP>(Op2);
 675     if (Op2C == 0) return 0;
 676
 677     if (Op2C->getValueAPF().isZero())  // pow(x, 0.0) -> 1.0
 678       return ConstantFP::get(CI->getType(), 1.0);
 679
 680     if (Op2C->isExactlyValue(0.5)) {
 681       // Expand pow(x, 0.5) to (x == -infinity ? +infinity : fabs(sqrt(x))).
 682       // This is faster than calling pow, and still handles negative zero
 683       // and negative infinite correctly.
 684       // TODO: In fast-math mode, this could be just sqrt(x).
 685       // TODO: In finite-only mode, this could be just fabs(sqrt(x)).
 686       Value *Inf = ConstantFP::getInfinity(CI->getType());
 687       Value *NegInf = ConstantFP::getInfinity(CI->getType(), true);
 688       Value *Sqrt = EmitUnaryFloatFnCall(Op1, "sqrt", B,
 689                                          Callee->getAttributes());
 690       Value *FAbs = EmitUnaryFloatFnCall(Sqrt, "fabs", B,
 691                                          Callee->getAttributes());
 692       Value *FCmp = B.CreateFCmpOEQ(Op1, NegInf, "tmp");
 693       Value *Sel = B.CreateSelect(FCmp, Inf, FAbs, "tmp");
 694       return Sel;
 695     }
 696
 697     if (Op2C->isExactlyValue(1.0))  // pow(x, 1.0) -> x
 698       return Op1;
 699     if (Op2C->isExactlyValue(2.0))  // pow(x, 2.0) -> x*x
 700       return B.CreateFMul(Op1, Op1, "pow2");
 701     if (Op2C->isExactlyValue(-1.0)) // pow(x, -1.0) -> 1.0/x
 702       return B.CreateFDiv(ConstantFP::get(CI->getType(), 1.0),
 703                           Op1, "powrecip");
 704     return 0;
 705   }
 706 };
 707
 708 //===---------------------------------------===//
 709 // 'exp2' Optimizations
 710
 711 struct Exp2Opt : public LibCallOptimization {
 712   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 713     const FunctionType *FT = Callee->getFunctionType();
 714     // Just make sure this has 1 argument of FP type, which matches the
 715     // result type.
 716     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
 717         !FT->getParamType(0)->isFloatingPointTy())
 718       return 0;
 719
 720     Value *Op = CI->getOperand(1);
 721     // Turn exp2(sitofp(x)) -> ldexp(1.0, sext(x))  if sizeof(x) <= 32
 722     // Turn exp2(uitofp(x)) -> ldexp(1.0, zext(x))  if sizeof(x) < 32
 723     Value *LdExpArg = 0;
 724     if (SIToFPInst *OpC = dyn_cast<SIToFPInst>(Op)) {
 725       if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() <= 32)
 726         LdExpArg = B.CreateSExt(OpC->getOperand(0),
 727                                 Type::getInt32Ty(*Context), "tmp");
 728     } else if (UIToFPInst *OpC = dyn_cast<UIToFPInst>(Op)) {
 729       if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() < 32)
 730         LdExpArg = B.CreateZExt(OpC->getOperand(0),
 731                                 Type::getInt32Ty(*Context), "tmp");
 732     }
 733
 734     if (LdExpArg) {
 735       const char *Name;
 736       if (Op->getType()->isFloatTy())
 737         Name = "ldexpf";
 738       else if (Op->getType()->isDoubleTy())
 739         Name = "ldexp";
 740       else
 741         Name = "ldexpl";
 742
 743       Constant *One = ConstantFP::get(*Context, APFloat(1.0f));
 744       if (!Op->getType()->isFloatTy())
 745         One = ConstantExpr::getFPExtend(One, Op->getType());
 746
 747       Module *M = Caller->getParent();
 748       Value *Callee = M->getOrInsertFunction(Name, Op->getType(),
 749                                              Op->getType(),
 750                                              Type::getInt32Ty(*Context),NULL);
 751       CallInst *CI = B.CreateCall2(Callee, One, LdExpArg);
 752       if (const Function *F = dyn_cast<Function>(Callee->stripPointerCasts()))
 753         CI->setCallingConv(F->getCallingConv());
 754
 755       return CI;
 756     }
 757     return 0;
 758   }
 759 };
 760
 761 //===---------------------------------------===//
 762 // Double -> Float Shrinking Optimizations for Unary Functions like 'floor'
 763
 764 struct UnaryDoubleFPOpt : public LibCallOptimization {
 765   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 766     const FunctionType *FT = Callee->getFunctionType();
 767     if (FT->getNumParams() != 1 || !FT->getReturnType()->isDoubleTy() ||
 768         !FT->getParamType(0)->isDoubleTy())
 769       return 0;
 770
 771     // If this is something like 'floor((double)floatval)', convert to floorf.
 772     FPExtInst *Cast = dyn_cast<FPExtInst>(CI->getOperand(1));
 773     if (Cast == 0 || !Cast->getOperand(0)->getType()->isFloatTy())
 774       return 0;
 775
 776     // floor((double)floatval) -> (double)floorf(floatval)
 777     Value *V = Cast->getOperand(0);
 778     V = EmitUnaryFloatFnCall(V, Callee->getName().data(), B,
 779                              Callee->getAttributes());
 780     return B.CreateFPExt(V, Type::getDoubleTy(*Context));
 781   }
 782 };
 783
 784 //===----------------------------------------------------------------------===//
 785 // Integer Optimizations
 786 //===----------------------------------------------------------------------===//
 787
 788 //===---------------------------------------===//
 789 // 'ffs*' Optimizations
 790
 791 struct FFSOpt : public LibCallOptimization {
 792   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 793     const FunctionType *FT = Callee->getFunctionType();
 794     // Just make sure this has 2 arguments of the same FP type, which match the
 795     // result type.
 796     if (FT->getNumParams() != 1 ||
 797         !FT->getReturnType()->isIntegerTy(32) ||
 798         !FT->getParamType(0)->isIntegerTy())
 799       return 0;
 800
 801     Value *Op = CI->getOperand(1);
 802
 803     // Constant fold.
 804     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op)) {
 805       if (CI->getValue() == 0)  // ffs(0) -> 0.
 806         return Constant::getNullValue(CI->getType());
 807       return ConstantInt::get(Type::getInt32Ty(*Context), // ffs(c) -> cttz(c)+1
 808                               CI->getValue().countTrailingZeros()+1);
 809     }
 810
 811     // ffs(x) -> x != 0 ? (i32)llvm.cttz(x)+1 : 0
 812     const Type *ArgType = Op->getType();
 813     Value *F = Intrinsic::getDeclaration(Callee->getParent(),
 814                                          Intrinsic::cttz, &ArgType, 1);
 815     Value *V = B.CreateCall(F, Op, "cttz");
 816     V = B.CreateAdd(V, ConstantInt::get(V->getType(), 1), "tmp");
 817     V = B.CreateIntCast(V, Type::getInt32Ty(*Context), false, "tmp");
 818
 819     Value *Cond = B.CreateICmpNE(Op, Constant::getNullValue(ArgType), "tmp");
 820     return B.CreateSelect(Cond, V,
 821                           ConstantInt::get(Type::getInt32Ty(*Context), 0));
 822   }
 823 };
 824
 825 //===---------------------------------------===//
 826 // 'isdigit' Optimizations
 827
 828 struct IsDigitOpt : public LibCallOptimization {
 829   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 830     const FunctionType *FT = Callee->getFunctionType();
 831     // We require integer(i32)
 832     if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
 833         !FT->getParamType(0)->isIntegerTy(32))
 834       return 0;
 835
 836     // isdigit(c) -> (c-'0') <u 10
 837     Value *Op = CI->getOperand(1);
 838     Op = B.CreateSub(Op, ConstantInt::get(Type::getInt32Ty(*Context), '0'),
 839                      "isdigittmp");
 840     Op = B.CreateICmpULT(Op, ConstantInt::get(Type::getInt32Ty(*Context), 10),
 841                          "isdigit");
 842     return B.CreateZExt(Op, CI->getType());
 843   }
 844 };
 845
 846 //===---------------------------------------===//
 847 // 'isascii' Optimizations
 848
 849 struct IsAsciiOpt : public LibCallOptimization {
 850   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 851     const FunctionType *FT = Callee->getFunctionType();
 852     // We require integer(i32)
 853     if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
 854         !FT->getParamType(0)->isIntegerTy(32))
 855       return 0;
 856
 857     // isascii(c) -> c <u 128
 858     Value *Op = CI->getOperand(1);
 859     Op = B.CreateICmpULT(Op, ConstantInt::get(Type::getInt32Ty(*Context), 128),
 860                          "isascii");
 861     return B.CreateZExt(Op, CI->getType());
 862   }
 863 };
 864
 865 //===---------------------------------------===//
 866 // 'abs', 'labs', 'llabs' Optimizations
 867
 868 struct AbsOpt : public LibCallOptimization {
 869   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 870     const FunctionType *FT = Callee->getFunctionType();
 871     // We require integer(integer) where the types agree.
 872     if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
 873         FT->getParamType(0) != FT->getReturnType())
 874       return 0;
 875
 876     // abs(x) -> x >s -1 ? x : -x
 877     Value *Op = CI->getOperand(1);
 878     Value *Pos = B.CreateICmpSGT(Op,
 879                              Constant::getAllOnesValue(Op->getType()),
 880                                  "ispos");
 881     Value *Neg = B.CreateNeg(Op, "neg");
 882     return B.CreateSelect(Pos, Op, Neg);
 883   }
 884 };
 885
 886
 887 //===---------------------------------------===//
 888 // 'toascii' Optimizations
 889
 890 struct ToAsciiOpt : public LibCallOptimization {
 891   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 892     const FunctionType *FT = Callee->getFunctionType();
 893     // We require i32(i32)
 894     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
 895         !FT->getParamType(0)->isIntegerTy(32))
 896       return 0;
 897
 898     // isascii(c) -> c & 0x7f
 899     return B.CreateAnd(CI->getOperand(1),
 900                        ConstantInt::get(CI->getType(),0x7F));
 901   }
 902 };
 903
 904 //===----------------------------------------------------------------------===//
 905 // Formatting and IO Optimizations
 906 //===----------------------------------------------------------------------===//
 907
 908 //===---------------------------------------===//
 909 // 'printf' Optimizations
 910
 911 struct PrintFOpt : public LibCallOptimization {
 912   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 913     // Require one fixed pointer argument and an integer/void result.
 914     const FunctionType *FT = Callee->getFunctionType();
 915     if (FT->getNumParams() < 1 || !FT->getParamType(0)->isPointerTy() ||
 916         !(FT->getReturnType()->isIntegerTy() ||
 917           FT->getReturnType()->isVoidTy()))
 918       return 0;
 919
 920     // Check for a fixed format string.
 921     std::string FormatStr;
 922     if (!GetConstantStringInfo(CI->getOperand(1), FormatStr))
 923       return 0;
 924
 925     // Empty format string -> noop.
 926     if (FormatStr.empty())  // Tolerate printf's declared void.
 927       return CI->use_empty() ? (Value*)CI :
 928                                ConstantInt::get(CI->getType(), 0);
 929
 930     // printf("x") -> putchar('x'), even for '%'.  Return the result of putchar
 931     // in case there is an error writing to stdout.
 932     if (FormatStr.size() == 1) {
 933       Value *Res = EmitPutChar(ConstantInt::get(Type::getInt32Ty(*Context),
 934                                                 FormatStr[0]), B, TD);
 935       if (CI->use_empty()) return CI;
 936       return B.CreateIntCast(Res, CI->getType(), true);
 937     }
 938
 939     // printf("foo\n") --> puts("foo")
 940     if (FormatStr[FormatStr.size()-1] == '\n' &&
 941         FormatStr.find('%') == std::string::npos) {  // no format characters.
 942       // Create a string literal with no \n on it.  We expect the constant merge
 943       // pass to be run after this pass, to merge duplicate strings.
 944       FormatStr.erase(FormatStr.end()-1);
 945       Constant *C = ConstantArray::get(*Context, FormatStr, true);
 946       C = new GlobalVariable(*Callee->getParent(), C->getType(), true,
 947                              GlobalVariable::InternalLinkage, C, "str");
 948       EmitPutS(C, B, TD);
 949       return CI->use_empty() ? (Value*)CI :
 950                     ConstantInt::get(CI->getType(), FormatStr.size()+1);
 951     }
 952
 953     // Optimize specific format strings.
 954     // printf("%c", chr) --> putchar(*(i8*)dst)
 955     if (FormatStr == "%c" && CI->getNumOperands() > 2 &&
 956         CI->getOperand(2)->getType()->isIntegerTy()) {
 957       Value *Res = EmitPutChar(CI->getOperand(2), B, TD);
 958
 959       if (CI->use_empty()) return CI;
 960       return B.CreateIntCast(Res, CI->getType(), true);
 961     }
 962
 963     // printf("%s\n", str) --> puts(str)
 964     if (FormatStr == "%s\n" && CI->getNumOperands() > 2 &&
 965         CI->getOperand(2)->getType()->isPointerTy() &&
 966         CI->use_empty()) {
 967       EmitPutS(CI->getOperand(2), B, TD);
 968       return CI;
 969     }
 970     return 0;
 971   }
 972 };
 973
 974 //===---------------------------------------===//
 975 // 'sprintf' Optimizations
 976
 977 struct SPrintFOpt : public LibCallOptimization {
 978   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 979     // Require two fixed pointer arguments and an integer result.
 980     const FunctionType *FT = Callee->getFunctionType();
 981     if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
 982         !FT->getParamType(1)->isPointerTy() ||
 983         !FT->getReturnType()->isIntegerTy())
 984       return 0;
 985
 986     // Check for a fixed format string.
 987     std::string FormatStr;
 988     if (!GetConstantStringInfo(CI->getOperand(2), FormatStr))
 989       return 0;
 990
 991     // If we just have a format string (nothing else crazy) transform it.
 992     if (CI->getNumOperands() == 3) {
 993       // Make sure there's no % in the constant array.  We could try to handle
 994       // %% -> % in the future if we cared.
 995       for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
 996         if (FormatStr[i] == '%')
 997           return 0; // we found a format specifier, bail out.
 998
 999       // These optimizations require TargetData.
1000       if (!TD) return 0;
1001
1002       // sprintf(str, fmt) -> llvm.memcpy(str, fmt, strlen(fmt)+1, 1)
1003       EmitMemCpy(CI->getOperand(1), CI->getOperand(2), // Copy the nul byte.
1004                  ConstantInt::get(TD->getIntPtrType(*Context),
1005                  FormatStr.size()+1), 1, false, B, TD);
1006       return ConstantInt::get(CI->getType(), FormatStr.size());
1007     }
1008
1009     // The remaining optimizations require the format string to be "%s" or "%c"
1010     // and have an extra operand.
1011     if (FormatStr.size() != 2 || FormatStr[0] != '%' || CI->getNumOperands() <4)
1012       return 0;
1013
1014     // Decode the second character of the format string.
1015     if (FormatStr[1] == 'c') {
1016       // sprintf(dst, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0
1017       if (!CI->getOperand(3)->getType()->isIntegerTy()) return 0;
1018       Value *V = B.CreateTrunc(CI->getOperand(3),
1019                                Type::getInt8Ty(*Context), "char");
1020       Value *Ptr = CastToCStr(CI->getOperand(1), B);
1021       B.CreateStore(V, Ptr);
1022       Ptr = B.CreateGEP(Ptr, ConstantInt::get(Type::getInt32Ty(*Context), 1),
1023                         "nul");
1024       B.CreateStore(Constant::getNullValue(Type::getInt8Ty(*Context)), Ptr);
1025
1026       return ConstantInt::get(CI->getType(), 1);
1027     }
1028
1029     if (FormatStr[1] == 's') {
1030       // These optimizations require TargetData.
1031       if (!TD) return 0;
1032
1033       // sprintf(dest, "%s", str) -> llvm.memcpy(dest, str, strlen(str)+1, 1)
1034       if (!CI->getOperand(3)->getType()->isPointerTy()) return 0;
1035
1036       Value *Len = EmitStrLen(CI->getOperand(3), B, TD);
1037       Value *IncLen = B.CreateAdd(Len,
1038                                   ConstantInt::get(Len->getType(), 1),
1039                                   "leninc");
1040       EmitMemCpy(CI->getOperand(1), CI->getOperand(3), IncLen, 1, false, B, TD);
1041
1042       // The sprintf result is the unincremented number of bytes in the string.
1043       return B.CreateIntCast(Len, CI->getType(), false);
1044     }
1045     return 0;
1046   }
1047 };
1048
1049 //===---------------------------------------===//
1050 // 'fwrite' Optimizations
1051
1052 struct FWriteOpt : public LibCallOptimization {
1053   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1054     // Require a pointer, an integer, an integer, a pointer, returning integer.
1055     const FunctionType *FT = Callee->getFunctionType();
1056     if (FT->getNumParams() != 4 || !FT->getParamType(0)->isPointerTy() ||
1057         !FT->getParamType(1)->isIntegerTy() ||
1058         !FT->getParamType(2)->isIntegerTy() ||
1059         !FT->getParamType(3)->isPointerTy() ||
1060         !FT->getReturnType()->isIntegerTy())
1061       return 0;
1062
1063     // Get the element size and count.
1064     ConstantInt *SizeC = dyn_cast<ConstantInt>(CI->getOperand(2));
1065     ConstantInt *CountC = dyn_cast<ConstantInt>(CI->getOperand(3));
1066     if (!SizeC || !CountC) return 0;
1067     uint64_t Bytes = SizeC->getZExtValue()*CountC->getZExtValue();
1068
1069     // If this is writing zero records, remove the call (it's a noop).
1070     if (Bytes == 0)
1071       return ConstantInt::get(CI->getType(), 0);
1072
1073     // If this is writing one byte, turn it into fputc.
1074     if (Bytes == 1) {  // fwrite(S,1,1,F) -> fputc(S[0],F)
1075       Value *Char = B.CreateLoad(CastToCStr(CI->getOperand(1), B), "char");
1076       EmitFPutC(Char, CI->getOperand(4), B, TD);
1077       return ConstantInt::get(CI->getType(), 1);
1078     }
1079
1080     return 0;
1081   }
1082 };
1083
1084 //===---------------------------------------===//
1085 // 'fputs' Optimizations
1086
1087 struct FPutsOpt : public LibCallOptimization {
1088   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1089     // These optimizations require TargetData.
1090     if (!TD) return 0;
1091
1092     // Require two pointers.  Also, we can't optimize if return value is used.
1093     const FunctionType *FT = Callee->getFunctionType();
1094     if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
1095         !FT->getParamType(1)->isPointerTy() ||
1096         !CI->use_empty())
1097       return 0;
1098
1099     // fputs(s,F) --> fwrite(s,1,strlen(s),F)
1100     uint64_t Len = GetStringLength(CI->getOperand(1));
1101     if (!Len) return 0;
1102     EmitFWrite(CI->getOperand(1),
1103                ConstantInt::get(TD->getIntPtrType(*Context), Len-1),
1104                CI->getOperand(2), B, TD);
1105     return CI;  // Known to have no uses (see above).
1106   }
1107 };
1108
1109 //===---------------------------------------===//
1110 // 'fprintf' Optimizations
1111
1112 struct FPrintFOpt : public LibCallOptimization {
1113   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1114     // Require two fixed paramters as pointers and integer result.
1115     const FunctionType *FT = Callee->getFunctionType();
1116     if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
1117         !FT->getParamType(1)->isPointerTy() ||
1118         !FT->getReturnType()->isIntegerTy())
1119       return 0;
1120
1121     // All the optimizations depend on the format string.
1122     std::string FormatStr;
1123     if (!GetConstantStringInfo(CI->getOperand(2), FormatStr))
1124       return 0;
1125
1126     // fprintf(F, "foo") --> fwrite("foo", 3, 1, F)
1127     if (CI->getNumOperands() == 3) {
1128       for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1129         if (FormatStr[i] == '%')  // Could handle %% -> % if we cared.
1130           return 0; // We found a format specifier.
1131
1132       // These optimizations require TargetData.
1133       if (!TD) return 0;
1134
1135       EmitFWrite(CI->getOperand(2),
1136                  ConstantInt::get(TD->getIntPtrType(*Context),
1137                                   FormatStr.size()),
1138                  CI->getOperand(1), B, TD);
1139       return ConstantInt::get(CI->getType(), FormatStr.size());
1140     }
1141
1142     // The remaining optimizations require the format string to be "%s" or "%c"
1143     // and have an extra operand.
1144     if (FormatStr.size() != 2 || FormatStr[0] != '%' || CI->getNumOperands() <4)
1145       return 0;
1146
1147     // Decode the second character of the format string.
1148     if (FormatStr[1] == 'c') {
1149       // fprintf(F, "%c", chr) --> *(i8*)dst = chr
1150       if (!CI->getOperand(3)->getType()->isIntegerTy()) return 0;
1151       EmitFPutC(CI->getOperand(3), CI->getOperand(1), B, TD);
1152       return ConstantInt::get(CI->getType(), 1);
1153     }
1154
1155     if (FormatStr[1] == 's') {
1156       // fprintf(F, "%s", str) -> fputs(str, F)
1157       if (!CI->getOperand(3)->getType()->isPointerTy() || !CI->use_empty())
1158         return 0;
1159       EmitFPutS(CI->getOperand(3), CI->getOperand(1), B, TD);
1160       return CI;
1161     }
1162     return 0;
1163   }
1164 };
1165
1166 } // end anonymous namespace.
1167
1168 //===----------------------------------------------------------------------===//
1169 // SimplifyLibCalls Pass Implementation
1170 //===----------------------------------------------------------------------===//
1171
1172 namespace {
1173   /// This pass optimizes well known library functions from libc and libm.
1174   ///
1175   class SimplifyLibCalls : public FunctionPass {
1176     StringMap<LibCallOptimization*> Optimizations;
1177     // String and Memory LibCall Optimizations
1178     StrCatOpt StrCat; StrNCatOpt StrNCat; StrChrOpt StrChr; StrCmpOpt StrCmp;
1179     StrNCmpOpt StrNCmp; StrCpyOpt StrCpy; StrCpyOpt StrCpyChk;
1180     StrNCpyOpt StrNCpy; StrLenOpt StrLen;
1181     StrToOpt StrTo; StrStrOpt StrStr;
1182     MemCmpOpt MemCmp; MemCpyOpt MemCpy; MemMoveOpt MemMove; MemSetOpt MemSet;
1183     // Math Library Optimizations
1184     PowOpt Pow; Exp2Opt Exp2; UnaryDoubleFPOpt UnaryDoubleFP;
1185     // Integer Optimizations
1186     FFSOpt FFS; AbsOpt Abs; IsDigitOpt IsDigit; IsAsciiOpt IsAscii;
1187     ToAsciiOpt ToAscii;
1188     // Formatting and IO Optimizations
1189     SPrintFOpt SPrintF; PrintFOpt PrintF;
1190     FWriteOpt FWrite; FPutsOpt FPuts; FPrintFOpt FPrintF;
1191
1192     bool Modified;  // This is only used by doInitialization.
1193   public:
1194     static char ID; // Pass identification
1195     SimplifyLibCalls() : FunctionPass(&ID), StrCpy(false), StrCpyChk(true) {}
1196     void InitOptimizations();
1197     bool runOnFunction(Function &F);
1198
1199     void setDoesNotAccessMemory(Function &F);
1200     void setOnlyReadsMemory(Function &F);
1201     void setDoesNotThrow(Function &F);
1202     void setDoesNotCapture(Function &F, unsigned n);
1203     void setDoesNotAlias(Function &F, unsigned n);
1204     bool doInitialization(Module &M);
1205
1206     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1207     }
1208   };
1209   char SimplifyLibCalls::ID = 0;
1210 } // end anonymous namespace.
1211
1212 static RegisterPass<SimplifyLibCalls>
1213 X("simplify-libcalls", "Simplify well-known library calls");
1214
1215 // Public interface to the Simplify LibCalls pass.
1216 FunctionPass *llvm::createSimplifyLibCallsPass() {
1217   return new SimplifyLibCalls();
1218 }
1219
1220 /// Optimizations - Populate the Optimizations map with all the optimizations
1221 /// we know.
1222 void SimplifyLibCalls::InitOptimizations() {
1223   // String and Memory LibCall Optimizations
1224   Optimizations["strcat"] = &StrCat;
1225   Optimizations["strncat"] = &StrNCat;
1226   Optimizations["strchr"] = &StrChr;
1227   Optimizations["strcmp"] = &StrCmp;
1228   Optimizations["strncmp"] = &StrNCmp;
1229   Optimizations["strcpy"] = &StrCpy;
1230   Optimizations["strncpy"] = &StrNCpy;
1231   Optimizations["strlen"] = &StrLen;
1232   Optimizations["strtol"] = &StrTo;
1233   Optimizations["strtod"] = &StrTo;
1234   Optimizations["strtof"] = &StrTo;
1235   Optimizations["strtoul"] = &StrTo;
1236   Optimizations["strtoll"] = &StrTo;
1237   Optimizations["strtold"] = &StrTo;
1238   Optimizations["strtoull"] = &StrTo;
1239   Optimizations["strstr"] = &StrStr;
1240   Optimizations["memcmp"] = &MemCmp;
1241   Optimizations["memcpy"] = &MemCpy;
1242   Optimizations["memmove"] = &MemMove;
1243   Optimizations["memset"] = &MemSet;
1244
1245   // _chk variants of String and Memory LibCall Optimizations.
1246   Optimizations["__strcpy_chk"] = &StrCpyChk;
1247
1248   // Math Library Optimizations
1249   Optimizations["powf"] = &Pow;
1250   Optimizations["pow"] = &Pow;
1251   Optimizations["powl"] = &Pow;
1252   Optimizations["llvm.pow.f32"] = &Pow;
1253   Optimizations["llvm.pow.f64"] = &Pow;
1254   Optimizations["llvm.pow.f80"] = &Pow;
1255   Optimizations["llvm.pow.f128"] = &Pow;
1256   Optimizations["llvm.pow.ppcf128"] = &Pow;
1257   Optimizations["exp2l"] = &Exp2;
1258   Optimizations["exp2"] = &Exp2;
1259   Optimizations["exp2f"] = &Exp2;
1260   Optimizations["llvm.exp2.ppcf128"] = &Exp2;
1261   Optimizations["llvm.exp2.f128"] = &Exp2;
1262   Optimizations["llvm.exp2.f80"] = &Exp2;
1263   Optimizations["llvm.exp2.f64"] = &Exp2;
1264   Optimizations["llvm.exp2.f32"] = &Exp2;
1265
1266 #ifdef HAVE_FLOORF
1267   Optimizations["floor"] = &UnaryDoubleFP;
1268 #endif
1269 #ifdef HAVE_CEILF
1270   Optimizations["ceil"] = &UnaryDoubleFP;
1271 #endif
1272 #ifdef HAVE_ROUNDF
1273   Optimizations["round"] = &UnaryDoubleFP;
1274 #endif
1275 #ifdef HAVE_RINTF
1276   Optimizations["rint"] = &UnaryDoubleFP;
1277 #endif
1278 #ifdef HAVE_NEARBYINTF
1279   Optimizations["nearbyint"] = &UnaryDoubleFP;
1280 #endif
1281
1282   // Integer Optimizations
1283   Optimizations["ffs"] = &FFS;
1284   Optimizations["ffsl"] = &FFS;
1285   Optimizations["ffsll"] = &FFS;
1286   Optimizations["abs"] = &Abs;
1287   Optimizations["labs"] = &Abs;
1288   Optimizations["llabs"] = &Abs;
1289   Optimizations["isdigit"] = &IsDigit;
1290   Optimizations["isascii"] = &IsAscii;
1291   Optimizations["toascii"] = &ToAscii;
1292
1293   // Formatting and IO Optimizations
1294   Optimizations["sprintf"] = &SPrintF;
1295   Optimizations["printf"] = &PrintF;
1296   Optimizations["fwrite"] = &FWrite;
1297   Optimizations["fputs"] = &FPuts;
1298   Optimizations["fprintf"] = &FPrintF;
1299 }
1300
1301
1302 /// runOnFunction - Top level algorithm.
1303 ///
1304 bool SimplifyLibCalls::runOnFunction(Function &F) {
1305   if (Optimizations.empty())
1306     InitOptimizations();
1307
1308   const TargetData *TD = getAnalysisIfAvailable<TargetData>();
1309
1310   IRBuilder<> Builder(F.getContext());
1311
1312   bool Changed = false;
1313   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
1314     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
1315       // Ignore non-calls.
1316       CallInst *CI = dyn_cast<CallInst>(I++);
1317       if (!CI) continue;
1318
1319       // Ignore indirect calls and calls to non-external functions.
1320       Function *Callee = CI->getCalledFunction();
1321       if (Callee == 0 || !Callee->isDeclaration() ||
1322           !(Callee->hasExternalLinkage() || Callee->hasDLLImportLinkage()))
1323         continue;
1324
1325       // Ignore unknown calls.
1326       LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
1327       if (!LCO) continue;
1328
1329       // Set the builder to the instruction after the call.
1330       Builder.SetInsertPoint(BB, I);
1331
1332       // Try to optimize this call.
1333       Value *Result = LCO->OptimizeCall(CI, TD, Builder);
1334       if (Result == 0) continue;
1335
1336       DEBUG(dbgs() << "SimplifyLibCalls simplified: " << *CI;
1337             dbgs() << "  into: " << *Result << "\n");
1338
1339       // Something changed!
1340       Changed = true;
1341       ++NumSimplified;
1342
1343       // Inspect the instruction after the call (which was potentially just
1344       // added) next.
1345       I = CI; ++I;
1346
1347       if (CI != Result && !CI->use_empty()) {
1348         CI->replaceAllUsesWith(Result);
1349         if (!Result->hasName())
1350           Result->takeName(CI);
1351       }
1352       CI->eraseFromParent();
1353     }
1354   }
1355   return Changed;
1356 }
1357
1358 // Utility methods for doInitialization.
1359
1360 void SimplifyLibCalls::setDoesNotAccessMemory(Function &F) {
1361   if (!F.doesNotAccessMemory()) {
1362     F.setDoesNotAccessMemory();
1363     ++NumAnnotated;
1364     Modified = true;
1365   }
1366 }
1367 void SimplifyLibCalls::setOnlyReadsMemory(Function &F) {
1368   if (!F.onlyReadsMemory()) {
1369     F.setOnlyReadsMemory();
1370     ++NumAnnotated;
1371     Modified = true;
1372   }
1373 }
1374 void SimplifyLibCalls::setDoesNotThrow(Function &F) {
1375   if (!F.doesNotThrow()) {
1376     F.setDoesNotThrow();
1377     ++NumAnnotated;
1378     Modified = true;
1379   }
1380 }
1381 void SimplifyLibCalls::setDoesNotCapture(Function &F, unsigned n) {
1382   if (!F.doesNotCapture(n)) {
1383     F.setDoesNotCapture(n);
1384     ++NumAnnotated;
1385     Modified = true;
1386   }
1387 }
1388 void SimplifyLibCalls::setDoesNotAlias(Function &F, unsigned n) {
1389   if (!F.doesNotAlias(n)) {
1390     F.setDoesNotAlias(n);
1391     ++NumAnnotated;
1392     Modified = true;
1393   }
1394 }
1395
1396 /// doInitialization - Add attributes to well-known functions.
1397 ///
1398 bool SimplifyLibCalls::doInitialization(Module &M) {
1399   Modified = false;
1400   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
1401     Function &F = *I;
1402     if (!F.isDeclaration())
1403       continue;
1404
1405     if (!F.hasName())
1406       continue;
1407
1408     const FunctionType *FTy = F.getFunctionType();
1409
1410     StringRef Name = F.getName();
1411     switch (Name[0]) {
1412       case 's':
1413         if (Name == "strlen") {
1414           if (FTy->getNumParams() != 1 ||
1415               !FTy->getParamType(0)->isPointerTy())
1416             continue;
1417           setOnlyReadsMemory(F);
1418           setDoesNotThrow(F);
1419           setDoesNotCapture(F, 1);
1420         } else if (Name == "strchr" ||
1421                    Name == "strrchr") {
1422           if (FTy->getNumParams() != 2 ||
1423               !FTy->getParamType(0)->isPointerTy() ||
1424               !FTy->getParamType(1)->isIntegerTy())
1425             continue;
1426           setOnlyReadsMemory(F);
1427           setDoesNotThrow(F);
1428         } else if (Name == "strcpy" ||
1429                    Name == "stpcpy" ||
1430                    Name == "strcat" ||
1431                    Name == "strtol" ||
1432                    Name == "strtod" ||
1433                    Name == "strtof" ||
1434                    Name == "strtoul" ||
1435                    Name == "strtoll" ||
1436                    Name == "strtold" ||
1437                    Name == "strncat" ||
1438                    Name == "strncpy" ||
1439                    Name == "strtoull") {
1440           if (FTy->getNumParams() < 2 ||
1441               !FTy->getParamType(1)->isPointerTy())
1442             continue;
1443           setDoesNotThrow(F);
1444           setDoesNotCapture(F, 2);
1445         } else if (Name == "strxfrm") {
1446           if (FTy->getNumParams() != 3 ||
1447               !FTy->getParamType(0)->isPointerTy() ||
1448               !FTy->getParamType(1)->isPointerTy())
1449             continue;
1450           setDoesNotThrow(F);
1451           setDoesNotCapture(F, 1);
1452           setDoesNotCapture(F, 2);
1453         } else if (Name == "strcmp" ||
1454                    Name == "strspn" ||
1455                    Name == "strncmp" ||
1456                    Name == "strcspn" ||
1457                    Name == "strcoll" ||
1458                    Name == "strcasecmp" ||
1459                    Name == "strncasecmp") {
1460           if (FTy->getNumParams() < 2 ||
1461               !FTy->getParamType(0)->isPointerTy() ||
1462               !FTy->getParamType(1)->isPointerTy())
1463             continue;
1464           setOnlyReadsMemory(F);
1465           setDoesNotThrow(F);
1466           setDoesNotCapture(F, 1);
1467           setDoesNotCapture(F, 2);
1468         } else if (Name == "strstr" ||
1469                    Name == "strpbrk") {
1470           if (FTy->getNumParams() != 2 ||
1471               !FTy->getParamType(1)->isPointerTy())
1472             continue;
1473           setOnlyReadsMemory(F);
1474           setDoesNotThrow(F);
1475           setDoesNotCapture(F, 2);
1476         } else if (Name == "strtok" ||
1477                    Name == "strtok_r") {
1478           if (FTy->getNumParams() < 2 ||
1479               !FTy->getParamType(1)->isPointerTy())
1480             continue;
1481           setDoesNotThrow(F);
1482           setDoesNotCapture(F, 2);
1483         } else if (Name == "scanf" ||
1484                    Name == "setbuf" ||
1485                    Name == "setvbuf") {
1486           if (FTy->getNumParams() < 1 ||
1487               !FTy->getParamType(0)->isPointerTy())
1488             continue;
1489           setDoesNotThrow(F);
1490           setDoesNotCapture(F, 1);
1491         } else if (Name == "strdup" ||
1492                    Name == "strndup") {
1493           if (FTy->getNumParams() < 1 ||
1494               !FTy->getReturnType()->isPointerTy() ||
1495               !FTy->getParamType(0)->isPointerTy())
1496             continue;
1497           setDoesNotThrow(F);
1498           setDoesNotAlias(F, 0);
1499           setDoesNotCapture(F, 1);
1500         } else if (Name == "stat" ||
1501                    Name == "sscanf" ||
1502                    Name == "sprintf" ||
1503                    Name == "statvfs") {
1504           if (FTy->getNumParams() < 2 ||
1505               !FTy->getParamType(0)->isPointerTy() ||
1506               !FTy->getParamType(1)->isPointerTy())
1507             continue;
1508           setDoesNotThrow(F);
1509           setDoesNotCapture(F, 1);
1510           setDoesNotCapture(F, 2);
1511         } else if (Name == "snprintf") {
1512           if (FTy->getNumParams() != 3 ||
1513               !FTy->getParamType(0)->isPointerTy() ||
1514               !FTy->getParamType(2)->isPointerTy())
1515             continue;
1516           setDoesNotThrow(F);
1517           setDoesNotCapture(F, 1);
1518           setDoesNotCapture(F, 3);
1519         } else if (Name == "setitimer") {
1520           if (FTy->getNumParams() != 3 ||
1521               !FTy->getParamType(1)->isPointerTy() ||
1522               !FTy->getParamType(2)->isPointerTy())
1523             continue;
1524           setDoesNotThrow(F);
1525           setDoesNotCapture(F, 2);
1526           setDoesNotCapture(F, 3);
1527         } else if (Name == "system") {
1528           if (FTy->getNumParams() != 1 ||
1529               !FTy->getParamType(0)->isPointerTy())
1530             continue;
1531           // May throw; "system" is a valid pthread cancellation point.
1532           setDoesNotCapture(F, 1);
1533         }
1534         break;
1535       case 'm':
1536         if (Name == "malloc") {
1537           if (FTy->getNumParams() != 1 ||
1538               !FTy->getReturnType()->isPointerTy())
1539             continue;
1540           setDoesNotThrow(F);
1541           setDoesNotAlias(F, 0);
1542         } else if (Name == "memcmp") {
1543           if (FTy->getNumParams() != 3 ||
1544               !FTy->getParamType(0)->isPointerTy() ||
1545               !FTy->getParamType(1)->isPointerTy())
1546             continue;
1547           setOnlyReadsMemory(F);
1548           setDoesNotThrow(F);
1549           setDoesNotCapture(F, 1);
1550           setDoesNotCapture(F, 2);
1551         } else if (Name == "memchr" ||
1552                    Name == "memrchr") {
1553           if (FTy->getNumParams() != 3)
1554             continue;
1555           setOnlyReadsMemory(F);
1556           setDoesNotThrow(F);
1557         } else if (Name == "modf" ||
1558                    Name == "modff" ||
1559                    Name == "modfl" ||
1560                    Name == "memcpy" ||
1561                    Name == "memccpy" ||
1562                    Name == "memmove") {
1563           if (FTy->getNumParams() < 2 ||
1564               !FTy->getParamType(1)->isPointerTy())
1565             continue;
1566           setDoesNotThrow(F);
1567           setDoesNotCapture(F, 2);
1568         } else if (Name == "memalign") {
1569           if (!FTy->getReturnType()->isPointerTy())
1570             continue;
1571           setDoesNotAlias(F, 0);
1572         } else if (Name == "mkdir" ||
1573                    Name == "mktime") {
1574           if (FTy->getNumParams() == 0 ||
1575               !FTy->getParamType(0)->isPointerTy())
1576             continue;
1577           setDoesNotThrow(F);
1578           setDoesNotCapture(F, 1);
1579         }
1580         break;
1581       case 'r':
1582         if (Name == "realloc") {
1583           if (FTy->getNumParams() != 2 ||
1584               !FTy->getParamType(0)->isPointerTy() ||
1585               !FTy->getReturnType()->isPointerTy())
1586             continue;
1587           setDoesNotThrow(F);
1588           setDoesNotAlias(F, 0);
1589           setDoesNotCapture(F, 1);
1590         } else if (Name == "read") {
1591           if (FTy->getNumParams() != 3 ||
1592               !FTy->getParamType(1)->isPointerTy())
1593             continue;
1594           // May throw; "read" is a valid pthread cancellation point.
1595           setDoesNotCapture(F, 2);
1596         } else if (Name == "rmdir" ||
1597                    Name == "rewind" ||
1598                    Name == "remove" ||
1599                    Name == "realpath") {
1600           if (FTy->getNumParams() < 1 ||
1601               !FTy->getParamType(0)->isPointerTy())
1602             continue;
1603           setDoesNotThrow(F);
1604           setDoesNotCapture(F, 1);
1605         } else if (Name == "rename" ||
1606                    Name == "readlink") {
1607           if (FTy->getNumParams() < 2 ||
1608               !FTy->getParamType(0)->isPointerTy() ||
1609               !FTy->getParamType(1)->isPointerTy())
1610             continue;
1611           setDoesNotThrow(F);
1612           setDoesNotCapture(F, 1);
1613           setDoesNotCapture(F, 2);
1614         }
1615         break;
1616       case 'w':
1617         if (Name == "write") {
1618           if (FTy->getNumParams() != 3 ||
1619               !FTy->getParamType(1)->isPointerTy())
1620             continue;
1621           // May throw; "write" is a valid pthread cancellation point.
1622           setDoesNotCapture(F, 2);
1623         }
1624         break;
1625       case 'b':
1626         if (Name == "bcopy") {
1627           if (FTy->getNumParams() != 3 ||
1628               !FTy->getParamType(0)->isPointerTy() ||
1629               !FTy->getParamType(1)->isPointerTy())
1630             continue;
1631           setDoesNotThrow(F);
1632           setDoesNotCapture(F, 1);
1633           setDoesNotCapture(F, 2);
1634         } else if (Name == "bcmp") {
1635           if (FTy->getNumParams() != 3 ||
1636               !FTy->getParamType(0)->isPointerTy() ||
1637               !FTy->getParamType(1)->isPointerTy())
1638             continue;
1639           setDoesNotThrow(F);
1640           setOnlyReadsMemory(F);
1641           setDoesNotCapture(F, 1);
1642           setDoesNotCapture(F, 2);
1643         } else if (Name == "bzero") {
1644           if (FTy->getNumParams() != 2 ||
1645               !FTy->getParamType(0)->isPointerTy())
1646             continue;
1647           setDoesNotThrow(F);
1648           setDoesNotCapture(F, 1);
1649         }
1650         break;
1651       case 'c':
1652         if (Name == "calloc") {
1653           if (FTy->getNumParams() != 2 ||
1654               !FTy->getReturnType()->isPointerTy())
1655             continue;
1656           setDoesNotThrow(F);
1657           setDoesNotAlias(F, 0);
1658         } else if (Name == "chmod" ||
1659                    Name == "chown" ||
1660                    Name == "ctermid" ||
1661                    Name == "clearerr" ||
1662                    Name == "closedir") {
1663           if (FTy->getNumParams() == 0 ||
1664               !FTy->getParamType(0)->isPointerTy())
1665             continue;
1666           setDoesNotThrow(F);
1667           setDoesNotCapture(F, 1);
1668         }
1669         break;
1670       case 'a':
1671         if (Name == "atoi" ||
1672             Name == "atol" ||
1673             Name == "atof" ||
1674             Name == "atoll") {
1675           if (FTy->getNumParams() != 1 ||
1676               !FTy->getParamType(0)->isPointerTy())
1677             continue;
1678           setDoesNotThrow(F);
1679           setOnlyReadsMemory(F);
1680           setDoesNotCapture(F, 1);
1681         } else if (Name == "access") {
1682           if (FTy->getNumParams() != 2 ||
1683               !FTy->getParamType(0)->isPointerTy())
1684             continue;
1685           setDoesNotThrow(F);
1686           setDoesNotCapture(F, 1);
1687         }
1688         break;
1689       case 'f':
1690         if (Name == "fopen") {
1691           if (FTy->getNumParams() != 2 ||
1692               !FTy->getReturnType()->isPointerTy() ||
1693               !FTy->getParamType(0)->isPointerTy() ||
1694               !FTy->getParamType(1)->isPointerTy())
1695             continue;
1696           setDoesNotThrow(F);
1697           setDoesNotAlias(F, 0);
1698           setDoesNotCapture(F, 1);
1699           setDoesNotCapture(F, 2);
1700         } else if (Name == "fdopen") {
1701           if (FTy->getNumParams() != 2 ||
1702               !FTy->getReturnType()->isPointerTy() ||
1703               !FTy->getParamType(1)->isPointerTy())
1704             continue;
1705           setDoesNotThrow(F);
1706           setDoesNotAlias(F, 0);
1707           setDoesNotCapture(F, 2);
1708         } else if (Name == "feof" ||
1709                    Name == "free" ||
1710                    Name == "fseek" ||
1711                    Name == "ftell" ||
1712                    Name == "fgetc" ||
1713                    Name == "fseeko" ||
1714                    Name == "ftello" ||
1715                    Name == "fileno" ||
1716                    Name == "fflush" ||
1717                    Name == "fclose" ||
1718                    Name == "fsetpos" ||
1719                    Name == "flockfile" ||
1720                    Name == "funlockfile" ||
1721                    Name == "ftrylockfile") {
1722           if (FTy->getNumParams() == 0 ||
1723               !FTy->getParamType(0)->isPointerTy())
1724             continue;
1725           setDoesNotThrow(F);
1726           setDoesNotCapture(F, 1);
1727         } else if (Name == "ferror") {
1728           if (FTy->getNumParams() != 1 ||
1729               !FTy->getParamType(0)->isPointerTy())
1730             continue;
1731           setDoesNotThrow(F);
1732           setDoesNotCapture(F, 1);
1733           setOnlyReadsMemory(F);
1734         } else if (Name == "fputc" ||
1735                    Name == "fstat" ||
1736                    Name == "frexp" ||
1737                    Name == "frexpf" ||
1738                    Name == "frexpl" ||
1739                    Name == "fstatvfs") {
1740           if (FTy->getNumParams() != 2 ||
1741               !FTy->getParamType(1)->isPointerTy())
1742             continue;
1743           setDoesNotThrow(F);
1744           setDoesNotCapture(F, 2);
1745         } else if (Name == "fgets") {
1746           if (FTy->getNumParams() != 3 ||
1747               !FTy->getParamType(0)->isPointerTy() ||
1748               !FTy->getParamType(2)->isPointerTy())
1749             continue;
1750           setDoesNotThrow(F);
1751           setDoesNotCapture(F, 3);
1752         } else if (Name == "fread" ||
1753                    Name == "fwrite") {
1754           if (FTy->getNumParams() != 4 ||
1755               !FTy->getParamType(0)->isPointerTy() ||
1756               !FTy->getParamType(3)->isPointerTy())
1757             continue;
1758           setDoesNotThrow(F);
1759           setDoesNotCapture(F, 1);
1760           setDoesNotCapture(F, 4);
1761         } else if (Name == "fputs" ||
1762                    Name == "fscanf" ||
1763                    Name == "fprintf" ||
1764                    Name == "fgetpos") {
1765           if (FTy->getNumParams() < 2 ||
1766               !FTy->getParamType(0)->isPointerTy() ||
1767               !FTy->getParamType(1)->isPointerTy())
1768             continue;
1769           setDoesNotThrow(F);
1770           setDoesNotCapture(F, 1);
1771           setDoesNotCapture(F, 2);
1772         }
1773         break;
1774       case 'g':
1775         if (Name == "getc" ||
1776             Name == "getlogin_r" ||
1777             Name == "getc_unlocked") {
1778           if (FTy->getNumParams() == 0 ||
1779               !FTy->getParamType(0)->isPointerTy())
1780             continue;
1781           setDoesNotThrow(F);
1782           setDoesNotCapture(F, 1);
1783         } else if (Name == "getenv") {
1784           if (FTy->getNumParams() != 1 ||
1785               !FTy->getParamType(0)->isPointerTy())
1786             continue;
1787           setDoesNotThrow(F);
1788           setOnlyReadsMemory(F);
1789           setDoesNotCapture(F, 1);
1790         } else if (Name == "gets" ||
1791                    Name == "getchar") {
1792           setDoesNotThrow(F);
1793         } else if (Name == "getitimer") {
1794           if (FTy->getNumParams() != 2 ||
1795               !FTy->getParamType(1)->isPointerTy())
1796             continue;
1797           setDoesNotThrow(F);
1798           setDoesNotCapture(F, 2);
1799         } else if (Name == "getpwnam") {
1800           if (FTy->getNumParams() != 1 ||
1801               !FTy->getParamType(0)->isPointerTy())
1802             continue;
1803           setDoesNotThrow(F);
1804           setDoesNotCapture(F, 1);
1805         }
1806         break;
1807       case 'u':
1808         if (Name == "ungetc") {
1809           if (FTy->getNumParams() != 2 ||
1810               !FTy->getParamType(1)->isPointerTy())
1811             continue;
1812           setDoesNotThrow(F);
1813           setDoesNotCapture(F, 2);
1814         } else if (Name == "uname" ||
1815                    Name == "unlink" ||
1816                    Name == "unsetenv") {
1817           if (FTy->getNumParams() != 1 ||
1818               !FTy->getParamType(0)->isPointerTy())
1819             continue;
1820           setDoesNotThrow(F);
1821           setDoesNotCapture(F, 1);
1822         } else if (Name == "utime" ||
1823                    Name == "utimes") {
1824           if (FTy->getNumParams() != 2 ||
1825               !FTy->getParamType(0)->isPointerTy() ||
1826               !FTy->getParamType(1)->isPointerTy())
1827             continue;
1828           setDoesNotThrow(F);
1829           setDoesNotCapture(F, 1);
1830           setDoesNotCapture(F, 2);
1831         }
1832         break;
1833       case 'p':
1834         if (Name == "putc") {
1835           if (FTy->getNumParams() != 2 ||
1836               !FTy->getParamType(1)->isPointerTy())
1837             continue;
1838           setDoesNotThrow(F);
1839           setDoesNotCapture(F, 2);
1840         } else if (Name == "puts" ||
1841                    Name == "printf" ||
1842                    Name == "perror") {
1843           if (FTy->getNumParams() != 1 ||
1844               !FTy->getParamType(0)->isPointerTy())
1845             continue;
1846           setDoesNotThrow(F);
1847           setDoesNotCapture(F, 1);
1848         } else if (Name == "pread" ||
1849                    Name == "pwrite") {
1850           if (FTy->getNumParams() != 4 ||
1851               !FTy->getParamType(1)->isPointerTy())
1852             continue;
1853           // May throw; these are valid pthread cancellation points.
1854           setDoesNotCapture(F, 2);
1855         } else if (Name == "putchar") {
1856           setDoesNotThrow(F);
1857         } else if (Name == "popen") {
1858           if (FTy->getNumParams() != 2 ||
1859               !FTy->getReturnType()->isPointerTy() ||
1860               !FTy->getParamType(0)->isPointerTy() ||
1861               !FTy->getParamType(1)->isPointerTy())
1862             continue;
1863           setDoesNotThrow(F);
1864           setDoesNotAlias(F, 0);
1865           setDoesNotCapture(F, 1);
1866           setDoesNotCapture(F, 2);
1867         } else if (Name == "pclose") {
1868           if (FTy->getNumParams() != 1 ||
1869               !FTy->getParamType(0)->isPointerTy())
1870             continue;
1871           setDoesNotThrow(F);
1872           setDoesNotCapture(F, 1);
1873         }
1874         break;
1875       case 'v':
1876         if (Name == "vscanf") {
1877           if (FTy->getNumParams() != 2 ||
1878               !FTy->getParamType(1)->isPointerTy())
1879             continue;
1880           setDoesNotThrow(F);
1881           setDoesNotCapture(F, 1);
1882         } else if (Name == "vsscanf" ||
1883                    Name == "vfscanf") {
1884           if (FTy->getNumParams() != 3 ||
1885               !FTy->getParamType(1)->isPointerTy() ||
1886               !FTy->getParamType(2)->isPointerTy())
1887             continue;
1888           setDoesNotThrow(F);
1889           setDoesNotCapture(F, 1);
1890           setDoesNotCapture(F, 2);
1891         } else if (Name == "valloc") {
1892           if (!FTy->getReturnType()->isPointerTy())
1893             continue;
1894           setDoesNotThrow(F);
1895           setDoesNotAlias(F, 0);
1896         } else if (Name == "vprintf") {
1897           if (FTy->getNumParams() != 2 ||
1898               !FTy->getParamType(0)->isPointerTy())
1899             continue;
1900           setDoesNotThrow(F);
1901           setDoesNotCapture(F, 1);
1902         } else if (Name == "vfprintf" ||
1903                    Name == "vsprintf") {
1904           if (FTy->getNumParams() != 3 ||
1905               !FTy->getParamType(0)->isPointerTy() ||
1906               !FTy->getParamType(1)->isPointerTy())
1907             continue;
1908           setDoesNotThrow(F);
1909           setDoesNotCapture(F, 1);
1910           setDoesNotCapture(F, 2);
1911         } else if (Name == "vsnprintf") {
1912           if (FTy->getNumParams() != 4 ||
1913               !FTy->getParamType(0)->isPointerTy() ||
1914               !FTy->getParamType(2)->isPointerTy())
1915             continue;
1916           setDoesNotThrow(F);
1917           setDoesNotCapture(F, 1);
1918           setDoesNotCapture(F, 3);
1919         }
1920         break;
1921       case 'o':
1922         if (Name == "open") {
1923           if (FTy->getNumParams() < 2 ||
1924               !FTy->getParamType(0)->isPointerTy())
1925             continue;
1926           // May throw; "open" is a valid pthread cancellation point.
1927           setDoesNotCapture(F, 1);
1928         } else if (Name == "opendir") {
1929           if (FTy->getNumParams() != 1 ||
1930               !FTy->getReturnType()->isPointerTy() ||
1931               !FTy->getParamType(0)->isPointerTy())
1932             continue;
1933           setDoesNotThrow(F);
1934           setDoesNotAlias(F, 0);
1935           setDoesNotCapture(F, 1);
1936         }
1937         break;
1938       case 't':
1939         if (Name == "tmpfile") {
1940           if (!FTy->getReturnType()->isPointerTy())
1941             continue;
1942           setDoesNotThrow(F);
1943           setDoesNotAlias(F, 0);
1944         } else if (Name == "times") {
1945           if (FTy->getNumParams() != 1 ||
1946               !FTy->getParamType(0)->isPointerTy())
1947             continue;
1948           setDoesNotThrow(F);
1949           setDoesNotCapture(F, 1);
1950         }
1951         break;
1952       case 'h':
1953         if (Name == "htonl" ||
1954             Name == "htons") {
1955           setDoesNotThrow(F);
1956           setDoesNotAccessMemory(F);
1957         }
1958         break;
1959       case 'n':
1960         if (Name == "ntohl" ||
1961             Name == "ntohs") {
1962           setDoesNotThrow(F);
1963           setDoesNotAccessMemory(F);
1964         }
1965         break;
1966       case 'l':
1967         if (Name == "lstat") {
1968           if (FTy->getNumParams() != 2 ||
1969               !FTy->getParamType(0)->isPointerTy() ||
1970               !FTy->getParamType(1)->isPointerTy())
1971             continue;
1972           setDoesNotThrow(F);
1973           setDoesNotCapture(F, 1);
1974           setDoesNotCapture(F, 2);
1975         } else if (Name == "lchown") {
1976           if (FTy->getNumParams() != 3 ||
1977               !FTy->getParamType(0)->isPointerTy())
1978             continue;
1979           setDoesNotThrow(F);
1980           setDoesNotCapture(F, 1);
1981         }
1982         break;
1983       case 'q':
1984         if (Name == "qsort") {
1985           if (FTy->getNumParams() != 4 ||
1986               !FTy->getParamType(3)->isPointerTy())
1987             continue;
1988           // May throw; places call through function pointer.
1989           setDoesNotCapture(F, 4);
1990         }
1991         break;
1992       case '_':
1993         if (Name == "__strdup" ||
1994             Name == "__strndup") {
1995           if (FTy->getNumParams() < 1 ||
1996               !FTy->getReturnType()->isPointerTy() ||
1997               !FTy->getParamType(0)->isPointerTy())
1998             continue;
1999           setDoesNotThrow(F);
2000           setDoesNotAlias(F, 0);
2001           setDoesNotCapture(F, 1);
2002         } else if (Name == "__strtok_r") {
2003           if (FTy->getNumParams() != 3 ||
2004               !FTy->getParamType(1)->isPointerTy())
2005             continue;
2006           setDoesNotThrow(F);
2007           setDoesNotCapture(F, 2);
2008         } else if (Name == "_IO_getc") {
2009           if (FTy->getNumParams() != 1 ||
2010               !FTy->getParamType(0)->isPointerTy())
2011             continue;
2012           setDoesNotThrow(F);
2013           setDoesNotCapture(F, 1);
2014         } else if (Name == "_IO_putc") {
2015           if (FTy->getNumParams() != 2 ||
2016               !FTy->getParamType(1)->isPointerTy())
2017             continue;
2018           setDoesNotThrow(F);
2019           setDoesNotCapture(F, 2);
2020         }
2021         break;
2022       case 1:
2023         if (Name == "\1__isoc99_scanf") {
2024           if (FTy->getNumParams() < 1 ||
2025               !FTy->getParamType(0)->isPointerTy())
2026             continue;
2027           setDoesNotThrow(F);
2028           setDoesNotCapture(F, 1);
2029         } else if (Name == "\1stat64" ||
2030                    Name == "\1lstat64" ||
2031                    Name == "\1statvfs64" ||
2032                    Name == "\1__isoc99_sscanf") {
2033           if (FTy->getNumParams() < 1 ||
2034               !FTy->getParamType(0)->isPointerTy() ||
2035               !FTy->getParamType(1)->isPointerTy())
2036             continue;
2037           setDoesNotThrow(F);
2038           setDoesNotCapture(F, 1);
2039           setDoesNotCapture(F, 2);
2040         } else if (Name == "\1fopen64") {
2041           if (FTy->getNumParams() != 2 ||
2042               !FTy->getReturnType()->isPointerTy() ||
2043               !FTy->getParamType(0)->isPointerTy() ||
2044               !FTy->getParamType(1)->isPointerTy())
2045             continue;
2046           setDoesNotThrow(F);
2047           setDoesNotAlias(F, 0);
2048           setDoesNotCapture(F, 1);
2049           setDoesNotCapture(F, 2);
2050         } else if (Name == "\1fseeko64" ||
2051                    Name == "\1ftello64") {
2052           if (FTy->getNumParams() == 0 ||
2053               !FTy->getParamType(0)->isPointerTy())
2054             continue;
2055           setDoesNotThrow(F);
2056           setDoesNotCapture(F, 1);
2057         } else if (Name == "\1tmpfile64") {
2058           if (!FTy->getReturnType()->isPointerTy())
2059             continue;
2060           setDoesNotThrow(F);
2061           setDoesNotAlias(F, 0);
2062         } else if (Name == "\1fstat64" ||
2063                    Name == "\1fstatvfs64") {
2064           if (FTy->getNumParams() != 2 ||
2065               !FTy->getParamType(1)->isPointerTy())
2066             continue;
2067           setDoesNotThrow(F);
2068           setDoesNotCapture(F, 2);
2069         } else if (Name == "\1open64") {
2070           if (FTy->getNumParams() < 2 ||
2071               !FTy->getParamType(0)->isPointerTy())
2072             continue;
2073           // May throw; "open" is a valid pthread cancellation point.
2074           setDoesNotCapture(F, 1);
2075         }
2076         break;
2077     }
2078   }
2079   return Modified;
2080 }
2081
2082 // TODO:
2083 //   Additional cases that we need to add to this file:
2084 //
2085 // cbrt:
2086 //   * cbrt(expN(X))  -> expN(x/3)
2087 //   * cbrt(sqrt(x))  -> pow(x,1/6)
2088 //   * cbrt(sqrt(x))  -> pow(x,1/9)
2089 //
2090 // cos, cosf, cosl:
2091 //   * cos(-x)  -> cos(x)
2092 //
2093 // exp, expf, expl:
2094 //   * exp(log(x))  -> x
2095 //
2096 // log, logf, logl:
2097 //   * log(exp(x))   -> x
2098 //   * log(x**y)     -> y*log(x)
2099 //   * log(exp(y))   -> y*log(e)
2100 //   * log(exp2(y))  -> y*log(2)
2101 //   * log(exp10(y)) -> y*log(10)
2102 //   * log(sqrt(x))  -> 0.5*log(x)
2103 //   * log(pow(x,y)) -> y*log(x)
2104 //
2105 // lround, lroundf, lroundl:
2106 //   * lround(cnst) -> cnst'
2107 //
2108 // pow, powf, powl:
2109 //   * pow(exp(x),y)  -> exp(x*y)
2110 //   * pow(sqrt(x),y) -> pow(x,y*0.5)
2111 //   * pow(pow(x,y),z)-> pow(x,y*z)
2112 //
2113 // puts:
2114 //   * puts("") -> putchar("\n")
2115 //
2116 // round, roundf, roundl:
2117 //   * round(cnst) -> cnst'
2118 //
2119 // signbit:
2120 //   * signbit(cnst) -> cnst'
2121 //   * signbit(nncst) -> 0 (if pstv is a non-negative constant)
2122 //
2123 // sqrt, sqrtf, sqrtl:
2124 //   * sqrt(expN(x))  -> expN(x*0.5)
2125 //   * sqrt(Nroot(x)) -> pow(x,1/(2*N))
2126 //   * sqrt(pow(x,y)) -> pow(|x|,y*0.5)
2127 //
2128 // stpcpy:
2129 //   * stpcpy(str, "literal") ->
2130 //           llvm.memcpy(str,"literal",strlen("literal")+1,1)
2131 // strrchr:
2132 //   * strrchr(s,c) -> reverse_offset_of_in(c,s)
2133 //      (if c is a constant integer and s is a constant string)
2134 //   * strrchr(s1,0) -> strchr(s1,0)
2135 //
2136 // strpbrk:
2137 //   * strpbrk(s,a) -> offset_in_for(s,a)
2138 //      (if s and a are both constant strings)
2139 //   * strpbrk(s,"") -> 0
2140 //   * strpbrk(s,a) -> strchr(s,a[0]) (if a is constant string of length 1)
2141 //
2142 // strspn, strcspn:
2143 //   * strspn(s,a)   -> const_int (if both args are constant)
2144 //   * strspn("",a)  -> 0
2145 //   * strspn(s,"")  -> 0
2146 //   * strcspn(s,a)  -> const_int (if both args are constant)
2147 //   * strcspn("",a) -> 0
2148 //   * strcspn(s,"") -> strlen(a)
2149 //
2150 // tan, tanf, tanl:
2151 //   * tan(atan(x)) -> x
2152 //
2153 // trunc, truncf, truncl:
2154 //   * trunc(cnst) -> cnst'
2155 //
2156 //