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