lib/Transforms/Scalar/SimplifyLibCalls.cpp

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