lib/Transforms/Scalar/SimplifyLibCalls.cpp

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