lib/Transforms/Scalar/SimplifyLibCalls.cpp

   1 //===- SimplifyLibCalls.cpp - Optimize specific well-known library calls --===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements a simple pass that applies a variety of small
  11 // optimizations for calls to specific well-known function calls (e.g. runtime
  12 // library functions).   Any optimization that takes the very simple form
  13 // "replace call to library function with simpler code that provides the same
  14 // result" belongs in this file.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #define DEBUG_TYPE "simplify-libcalls"
  19 #include "llvm/Transforms/Scalar.h"
  20 #include "llvm/Transforms/Utils/BuildLibCalls.h"
  21 #include "llvm/IRBuilder.h"
  22 #include "llvm/Intrinsics.h"
  23 #include "llvm/LLVMContext.h"
  24 #include "llvm/Module.h"
  25 #include "llvm/Pass.h"
  26 #include "llvm/ADT/STLExtras.h"
  27 #include "llvm/ADT/SmallPtrSet.h"
  28 #include "llvm/ADT/Statistic.h"
  29 #include "llvm/ADT/StringMap.h"
  30 #include "llvm/Analysis/ValueTracking.h"
  31 #include "llvm/Support/CommandLine.h"
  32 #include "llvm/Support/Debug.h"
  33 #include "llvm/Support/raw_ostream.h"
  34 #include "llvm/DataLayout.h"
  35 #include "llvm/Target/TargetLibraryInfo.h"
  36 #include "llvm/Config/config.h"            // FIXME: Shouldn't depend on host!
  37 using namespace llvm;
  38
  39 STATISTIC(NumSimplified, "Number of library calls simplified");
  40 STATISTIC(NumAnnotated, "Number of attributes added to library functions");
  41
  42 static cl::opt<bool> UnsafeFPShrink("enable-double-float-shrink", cl::Hidden,
  43                                    cl::init(false),
  44                                    cl::desc("Enable unsafe double to float "
  45                                             "shrinking for math lib calls"));
  46 //===----------------------------------------------------------------------===//
  47 // Optimizer Base Class
  48 //===----------------------------------------------------------------------===//
  49
  50 /// This class is the abstract base class for the set of optimizations that
  51 /// corresponds to one library call.
  52 namespace {
  53 class LibCallOptimization {
  54 protected:
  55   Function *Caller;
  56   const DataLayout *TD;
  57   const TargetLibraryInfo *TLI;
  58   LLVMContext* Context;
  59 public:
  60   LibCallOptimization() { }
  61   virtual ~LibCallOptimization() {}
  62
  63   /// CallOptimizer - This pure virtual method is implemented by base classes to
  64   /// do various optimizations.  If this returns null then no transformation was
  65   /// performed.  If it returns CI, then it transformed the call and CI is to be
  66   /// deleted.  If it returns something else, replace CI with the new value and
  67   /// delete CI.
  68   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B)
  69     =0;
  70
  71   Value *OptimizeCall(CallInst *CI, const DataLayout *TD,
  72                       const TargetLibraryInfo *TLI, IRBuilder<> &B) {
  73     Caller = CI->getParent()->getParent();
  74     this->TD = TD;
  75     this->TLI = TLI;
  76     if (CI->getCalledFunction())
  77       Context = &CI->getCalledFunction()->getContext();
  78
  79     // We never change the calling convention.
  80     if (CI->getCallingConv() != llvm::CallingConv::C)
  81       return NULL;
  82
  83     return CallOptimizer(CI->getCalledFunction(), CI, B);
  84   }
  85 };
  86 } // End anonymous namespace.
  87
  88
  89 //===----------------------------------------------------------------------===//
  90 // Helper Functions
  91 //===----------------------------------------------------------------------===//
  92
  93 static bool CallHasFloatingPointArgument(const CallInst *CI) {
  94   for (CallInst::const_op_iterator it = CI->op_begin(), e = CI->op_end();
  95        it != e; ++it) {
  96     if ((*it)->getType()->isFloatingPointTy())
  97       return true;
  98   }
  99   return false;
 100 }
 101
 102 //===----------------------------------------------------------------------===//
 103 // Memory LibCall Optimizations
 104 //===----------------------------------------------------------------------===//
 105
 106 namespace {
 107 //===---------------------------------------===//
 108 // 'memcpy' Optimizations
 109
 110 struct MemCpyOpt : public LibCallOptimization {
 111   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 112     // These optimizations require DataLayout.
 113     if (!TD) return 0;
 114
 115     FunctionType *FT = Callee->getFunctionType();
 116     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 117         !FT->getParamType(0)->isPointerTy() ||
 118         !FT->getParamType(1)->isPointerTy() ||
 119         FT->getParamType(2) != TD->getIntPtrType(*Context))
 120       return 0;
 121
 122     // memcpy(x, y, n) -> llvm.memcpy(x, y, n, 1)
 123     B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
 124                    CI->getArgOperand(2), 1);
 125     return CI->getArgOperand(0);
 126   }
 127 };
 128
 129 //===---------------------------------------===//
 130 // 'memmove' Optimizations
 131
 132 struct MemMoveOpt : public LibCallOptimization {
 133   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 134     // These optimizations require DataLayout.
 135     if (!TD) return 0;
 136
 137     FunctionType *FT = Callee->getFunctionType();
 138     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 139         !FT->getParamType(0)->isPointerTy() ||
 140         !FT->getParamType(1)->isPointerTy() ||
 141         FT->getParamType(2) != TD->getIntPtrType(*Context))
 142       return 0;
 143
 144     // memmove(x, y, n) -> llvm.memmove(x, y, n, 1)
 145     B.CreateMemMove(CI->getArgOperand(0), CI->getArgOperand(1),
 146                     CI->getArgOperand(2), 1);
 147     return CI->getArgOperand(0);
 148   }
 149 };
 150
 151 //===---------------------------------------===//
 152 // 'memset' Optimizations
 153
 154 struct MemSetOpt : public LibCallOptimization {
 155   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 156     // These optimizations require DataLayout.
 157     if (!TD) return 0;
 158
 159     FunctionType *FT = Callee->getFunctionType();
 160     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 161         !FT->getParamType(0)->isPointerTy() ||
 162         !FT->getParamType(1)->isIntegerTy() ||
 163         FT->getParamType(2) != TD->getIntPtrType(*Context))
 164       return 0;
 165
 166     // memset(p, v, n) -> llvm.memset(p, v, n, 1)
 167     Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(), false);
 168     B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1);
 169     return CI->getArgOperand(0);
 170   }
 171 };
 172
 173 //===----------------------------------------------------------------------===//
 174 // Math Library Optimizations
 175 //===----------------------------------------------------------------------===//
 176
 177 //===---------------------------------------===//
 178 // Double -> Float Shrinking Optimizations for Unary Functions like 'floor'
 179
 180 struct UnaryDoubleFPOpt : public LibCallOptimization {
 181   bool CheckRetType;
 182   UnaryDoubleFPOpt(bool CheckReturnType): CheckRetType(CheckReturnType) {}
 183   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 184     FunctionType *FT = Callee->getFunctionType();
 185     if (FT->getNumParams() != 1 || !FT->getReturnType()->isDoubleTy() ||
 186         !FT->getParamType(0)->isDoubleTy())
 187       return 0;
 188
 189     if (CheckRetType) {
 190       // Check if all the uses for function like 'sin' are converted to float.
 191       for (Value::use_iterator UseI = CI->use_begin(); UseI != CI->use_end();
 192           ++UseI) {
 193         FPTruncInst *Cast = dyn_cast<FPTruncInst>(*UseI);
 194         if (Cast == 0 || !Cast->getType()->isFloatTy())
 195           return 0;
 196       }
 197     }
 198
 199     // If this is something like 'floor((double)floatval)', convert to floorf.
 200     FPExtInst *Cast = dyn_cast<FPExtInst>(CI->getArgOperand(0));
 201     if (Cast == 0 || !Cast->getOperand(0)->getType()->isFloatTy())
 202       return 0;
 203
 204     // floor((double)floatval) -> (double)floorf(floatval)
 205     Value *V = Cast->getOperand(0);
 206     V = EmitUnaryFloatFnCall(V, Callee->getName(), B, Callee->getAttributes());
 207     return B.CreateFPExt(V, B.getDoubleTy());
 208   }
 209 };
 210
 211 //===---------------------------------------===//
 212 // 'cos*' Optimizations
 213 struct CosOpt : public LibCallOptimization {
 214   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 215     Value *Ret = NULL;
 216     if (UnsafeFPShrink && Callee->getName() == "cos" &&
 217         TLI->has(LibFunc::cosf)) {
 218       UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
 219       Ret = UnsafeUnaryDoubleFP.CallOptimizer(Callee, CI, B);
 220     }
 221
 222     FunctionType *FT = Callee->getFunctionType();
 223     // Just make sure this has 1 argument of FP type, which matches the
 224     // result type.
 225     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
 226         !FT->getParamType(0)->isFloatingPointTy())
 227       return Ret;
 228
 229     // cos(-x) -> cos(x)
 230     Value *Op1 = CI->getArgOperand(0);
 231     if (BinaryOperator::isFNeg(Op1)) {
 232       BinaryOperator *BinExpr = cast<BinaryOperator>(Op1);
 233       return B.CreateCall(Callee, BinExpr->getOperand(1), "cos");
 234     }
 235     return Ret;
 236   }
 237 };
 238
 239 //===---------------------------------------===//
 240 // 'pow*' Optimizations
 241
 242 struct PowOpt : public LibCallOptimization {
 243   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 244     Value *Ret = NULL;
 245     if (UnsafeFPShrink && Callee->getName() == "pow" &&
 246         TLI->has(LibFunc::powf)) {
 247       UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
 248       Ret = UnsafeUnaryDoubleFP.CallOptimizer(Callee, CI, B);
 249     }
 250
 251     FunctionType *FT = Callee->getFunctionType();
 252     // Just make sure this has 2 arguments of the same FP type, which match the
 253     // result type.
 254     if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) ||
 255         FT->getParamType(0) != FT->getParamType(1) ||
 256         !FT->getParamType(0)->isFloatingPointTy())
 257       return Ret;
 258
 259     Value *Op1 = CI->getArgOperand(0), *Op2 = CI->getArgOperand(1);
 260     if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) {
 261       if (Op1C->isExactlyValue(1.0))  // pow(1.0, x) -> 1.0
 262         return Op1C;
 263       if (Op1C->isExactlyValue(2.0))  // pow(2.0, x) -> exp2(x)
 264         return EmitUnaryFloatFnCall(Op2, "exp2", B, Callee->getAttributes());
 265     }
 266
 267     ConstantFP *Op2C = dyn_cast<ConstantFP>(Op2);
 268     if (Op2C == 0) return Ret;
 269
 270     if (Op2C->getValueAPF().isZero())  // pow(x, 0.0) -> 1.0
 271       return ConstantFP::get(CI->getType(), 1.0);
 272
 273     if (Op2C->isExactlyValue(0.5)) {
 274       // Expand pow(x, 0.5) to (x == -infinity ? +infinity : fabs(sqrt(x))).
 275       // This is faster than calling pow, and still handles negative zero
 276       // and negative infinity correctly.
 277       // TODO: In fast-math mode, this could be just sqrt(x).
 278       // TODO: In finite-only mode, this could be just fabs(sqrt(x)).
 279       Value *Inf = ConstantFP::getInfinity(CI->getType());
 280       Value *NegInf = ConstantFP::getInfinity(CI->getType(), true);
 281       Value *Sqrt = EmitUnaryFloatFnCall(Op1, "sqrt", B,
 282                                          Callee->getAttributes());
 283       Value *FAbs = EmitUnaryFloatFnCall(Sqrt, "fabs", B,
 284                                          Callee->getAttributes());
 285       Value *FCmp = B.CreateFCmpOEQ(Op1, NegInf);
 286       Value *Sel = B.CreateSelect(FCmp, Inf, FAbs);
 287       return Sel;
 288     }
 289
 290     if (Op2C->isExactlyValue(1.0))  // pow(x, 1.0) -> x
 291       return Op1;
 292     if (Op2C->isExactlyValue(2.0))  // pow(x, 2.0) -> x*x
 293       return B.CreateFMul(Op1, Op1, "pow2");
 294     if (Op2C->isExactlyValue(-1.0)) // pow(x, -1.0) -> 1.0/x
 295       return B.CreateFDiv(ConstantFP::get(CI->getType(), 1.0),
 296                           Op1, "powrecip");
 297     return 0;
 298   }
 299 };
 300
 301 //===---------------------------------------===//
 302 // 'exp2' Optimizations
 303
 304 struct Exp2Opt : public LibCallOptimization {
 305   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 306     Value *Ret = NULL;
 307     if (UnsafeFPShrink && Callee->getName() == "exp2" &&
 308         TLI->has(LibFunc::exp2)) {
 309       UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
 310       Ret = UnsafeUnaryDoubleFP.CallOptimizer(Callee, CI, B);
 311     }
 312
 313     FunctionType *FT = Callee->getFunctionType();
 314     // Just make sure this has 1 argument of FP type, which matches the
 315     // result type.
 316     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
 317         !FT->getParamType(0)->isFloatingPointTy())
 318       return Ret;
 319
 320     Value *Op = CI->getArgOperand(0);
 321     // Turn exp2(sitofp(x)) -> ldexp(1.0, sext(x))  if sizeof(x) <= 32
 322     // Turn exp2(uitofp(x)) -> ldexp(1.0, zext(x))  if sizeof(x) < 32
 323     Value *LdExpArg = 0;
 324     if (SIToFPInst *OpC = dyn_cast<SIToFPInst>(Op)) {
 325       if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() <= 32)
 326         LdExpArg = B.CreateSExt(OpC->getOperand(0), B.getInt32Ty());
 327     } else if (UIToFPInst *OpC = dyn_cast<UIToFPInst>(Op)) {
 328       if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() < 32)
 329         LdExpArg = B.CreateZExt(OpC->getOperand(0), B.getInt32Ty());
 330     }
 331
 332     if (LdExpArg) {
 333       const char *Name;
 334       if (Op->getType()->isFloatTy())
 335         Name = "ldexpf";
 336       else if (Op->getType()->isDoubleTy())
 337         Name = "ldexp";
 338       else
 339         Name = "ldexpl";
 340
 341       Constant *One = ConstantFP::get(*Context, APFloat(1.0f));
 342       if (!Op->getType()->isFloatTy())
 343         One = ConstantExpr::getFPExtend(One, Op->getType());
 344
 345       Module *M = Caller->getParent();
 346       Value *Callee = M->getOrInsertFunction(Name, Op->getType(),
 347                                              Op->getType(),
 348                                              B.getInt32Ty(), NULL);
 349       CallInst *CI = B.CreateCall2(Callee, One, LdExpArg);
 350       if (const Function *F = dyn_cast<Function>(Callee->stripPointerCasts()))
 351         CI->setCallingConv(F->getCallingConv());
 352
 353       return CI;
 354     }
 355     return Ret;
 356   }
 357 };
 358
 359 //===----------------------------------------------------------------------===//
 360 // Integer Optimizations
 361 //===----------------------------------------------------------------------===//
 362
 363 //===---------------------------------------===//
 364 // 'ffs*' Optimizations
 365
 366 struct FFSOpt : public LibCallOptimization {
 367   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 368     FunctionType *FT = Callee->getFunctionType();
 369     // Just make sure this has 2 arguments of the same FP type, which match the
 370     // result type.
 371     if (FT->getNumParams() != 1 ||
 372         !FT->getReturnType()->isIntegerTy(32) ||
 373         !FT->getParamType(0)->isIntegerTy())
 374       return 0;
 375
 376     Value *Op = CI->getArgOperand(0);
 377
 378     // Constant fold.
 379     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op)) {
 380       if (CI->isZero()) // ffs(0) -> 0.
 381         return B.getInt32(0);
 382       // ffs(c) -> cttz(c)+1
 383       return B.getInt32(CI->getValue().countTrailingZeros() + 1);
 384     }
 385
 386     // ffs(x) -> x != 0 ? (i32)llvm.cttz(x)+1 : 0
 387     Type *ArgType = Op->getType();
 388     Value *F = Intrinsic::getDeclaration(Callee->getParent(),
 389                                          Intrinsic::cttz, ArgType);
 390     Value *V = B.CreateCall2(F, Op, B.getFalse(), "cttz");
 391     V = B.CreateAdd(V, ConstantInt::get(V->getType(), 1));
 392     V = B.CreateIntCast(V, B.getInt32Ty(), false);
 393
 394     Value *Cond = B.CreateICmpNE(Op, Constant::getNullValue(ArgType));
 395     return B.CreateSelect(Cond, V, B.getInt32(0));
 396   }
 397 };
 398
 399 //===---------------------------------------===//
 400 // 'isdigit' Optimizations
 401
 402 struct IsDigitOpt : public LibCallOptimization {
 403   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 404     FunctionType *FT = Callee->getFunctionType();
 405     // We require integer(i32)
 406     if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
 407         !FT->getParamType(0)->isIntegerTy(32))
 408       return 0;
 409
 410     // isdigit(c) -> (c-'0') <u 10
 411     Value *Op = CI->getArgOperand(0);
 412     Op = B.CreateSub(Op, B.getInt32('0'), "isdigittmp");
 413     Op = B.CreateICmpULT(Op, B.getInt32(10), "isdigit");
 414     return B.CreateZExt(Op, CI->getType());
 415   }
 416 };
 417
 418 //===---------------------------------------===//
 419 // 'isascii' Optimizations
 420
 421 struct IsAsciiOpt : public LibCallOptimization {
 422   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 423     FunctionType *FT = Callee->getFunctionType();
 424     // We require integer(i32)
 425     if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
 426         !FT->getParamType(0)->isIntegerTy(32))
 427       return 0;
 428
 429     // isascii(c) -> c <u 128
 430     Value *Op = CI->getArgOperand(0);
 431     Op = B.CreateICmpULT(Op, B.getInt32(128), "isascii");
 432     return B.CreateZExt(Op, CI->getType());
 433   }
 434 };
 435
 436 //===---------------------------------------===//
 437 // 'abs', 'labs', 'llabs' Optimizations
 438
 439 struct AbsOpt : public LibCallOptimization {
 440   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 441     FunctionType *FT = Callee->getFunctionType();
 442     // We require integer(integer) where the types agree.
 443     if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
 444         FT->getParamType(0) != FT->getReturnType())
 445       return 0;
 446
 447     // abs(x) -> x >s -1 ? x : -x
 448     Value *Op = CI->getArgOperand(0);
 449     Value *Pos = B.CreateICmpSGT(Op, Constant::getAllOnesValue(Op->getType()),
 450                                  "ispos");
 451     Value *Neg = B.CreateNeg(Op, "neg");
 452     return B.CreateSelect(Pos, Op, Neg);
 453   }
 454 };
 455
 456
 457 //===---------------------------------------===//
 458 // 'toascii' Optimizations
 459
 460 struct ToAsciiOpt : public LibCallOptimization {
 461   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 462     FunctionType *FT = Callee->getFunctionType();
 463     // We require i32(i32)
 464     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
 465         !FT->getParamType(0)->isIntegerTy(32))
 466       return 0;
 467
 468     // isascii(c) -> c & 0x7f
 469     return B.CreateAnd(CI->getArgOperand(0),
 470                        ConstantInt::get(CI->getType(),0x7F));
 471   }
 472 };
 473
 474 //===----------------------------------------------------------------------===//
 475 // Formatting and IO Optimizations
 476 //===----------------------------------------------------------------------===//
 477
 478 //===---------------------------------------===//
 479 // 'printf' Optimizations
 480
 481 struct PrintFOpt : public LibCallOptimization {
 482   Value *OptimizeFixedFormatString(Function *Callee, CallInst *CI,
 483                                    IRBuilder<> &B) {
 484     // Check for a fixed format string.
 485     StringRef FormatStr;
 486     if (!getConstantStringInfo(CI->getArgOperand(0), FormatStr))
 487       return 0;
 488
 489     // Empty format string -> noop.
 490     if (FormatStr.empty())  // Tolerate printf's declared void.
 491       return CI->use_empty() ? (Value*)CI :
 492                                ConstantInt::get(CI->getType(), 0);
 493
 494     // Do not do any of the following transformations if the printf return value
 495     // is used, in general the printf return value is not compatible with either
 496     // putchar() or puts().
 497     if (!CI->use_empty())
 498       return 0;
 499
 500     // printf("x") -> putchar('x'), even for '%'.
 501     if (FormatStr.size() == 1) {
 502       Value *Res = EmitPutChar(B.getInt32(FormatStr[0]), B, TD, TLI);
 503       if (CI->use_empty() || !Res) return Res;
 504       return B.CreateIntCast(Res, CI->getType(), true);
 505     }
 506
 507     // printf("foo\n") --> puts("foo")
 508     if (FormatStr[FormatStr.size()-1] == '\n' &&
 509         FormatStr.find('%') == std::string::npos) {  // no format characters.
 510       // Create a string literal with no \n on it.  We expect the constant merge
 511       // pass to be run after this pass, to merge duplicate strings.
 512       FormatStr = FormatStr.drop_back();
 513       Value *GV = B.CreateGlobalString(FormatStr, "str");
 514       Value *NewCI = EmitPutS(GV, B, TD, TLI);
 515       return (CI->use_empty() || !NewCI) ?
 516               NewCI :
 517               ConstantInt::get(CI->getType(), FormatStr.size()+1);
 518     }
 519
 520     // Optimize specific format strings.
 521     // printf("%c", chr) --> putchar(chr)
 522     if (FormatStr == "%c" && CI->getNumArgOperands() > 1 &&
 523         CI->getArgOperand(1)->getType()->isIntegerTy()) {
 524       Value *Res = EmitPutChar(CI->getArgOperand(1), B, TD, TLI);
 525
 526       if (CI->use_empty() || !Res) return Res;
 527       return B.CreateIntCast(Res, CI->getType(), true);
 528     }
 529
 530     // printf("%s\n", str) --> puts(str)
 531     if (FormatStr == "%s\n" && CI->getNumArgOperands() > 1 &&
 532         CI->getArgOperand(1)->getType()->isPointerTy()) {
 533       return EmitPutS(CI->getArgOperand(1), B, TD, TLI);
 534     }
 535     return 0;
 536   }
 537
 538   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 539     // Require one fixed pointer argument and an integer/void result.
 540     FunctionType *FT = Callee->getFunctionType();
 541     if (FT->getNumParams() < 1 || !FT->getParamType(0)->isPointerTy() ||
 542         !(FT->getReturnType()->isIntegerTy() ||
 543           FT->getReturnType()->isVoidTy()))
 544       return 0;
 545
 546     if (Value *V = OptimizeFixedFormatString(Callee, CI, B)) {
 547       return V;
 548     }
 549
 550     // printf(format, ...) -> iprintf(format, ...) if no floating point
 551     // arguments.
 552     if (TLI->has(LibFunc::iprintf) && !CallHasFloatingPointArgument(CI)) {
 553       Module *M = B.GetInsertBlock()->getParent()->getParent();
 554       Constant *IPrintFFn =
 555         M->getOrInsertFunction("iprintf", FT, Callee->getAttributes());
 556       CallInst *New = cast<CallInst>(CI->clone());
 557       New->setCalledFunction(IPrintFFn);
 558       B.Insert(New);
 559       return New;
 560     }
 561     return 0;
 562   }
 563 };
 564
 565 //===---------------------------------------===//
 566 // 'sprintf' Optimizations
 567
 568 struct SPrintFOpt : public LibCallOptimization {
 569   Value *OptimizeFixedFormatString(Function *Callee, CallInst *CI,
 570                                    IRBuilder<> &B) {
 571     // Check for a fixed format string.
 572     StringRef FormatStr;
 573     if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr))
 574       return 0;
 575
 576     // If we just have a format string (nothing else crazy) transform it.
 577     if (CI->getNumArgOperands() == 2) {
 578       // Make sure there's no % in the constant array.  We could try to handle
 579       // %% -> % in the future if we cared.
 580       for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
 581         if (FormatStr[i] == '%')
 582           return 0; // we found a format specifier, bail out.
 583
 584       // These optimizations require DataLayout.
 585       if (!TD) return 0;
 586
 587       // sprintf(str, fmt) -> llvm.memcpy(str, fmt, strlen(fmt)+1, 1)
 588       B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
 589                      ConstantInt::get(TD->getIntPtrType(*Context), // Copy the
 590                                       FormatStr.size() + 1), 1);   // nul byte.
 591       return ConstantInt::get(CI->getType(), FormatStr.size());
 592     }
 593
 594     // The remaining optimizations require the format string to be "%s" or "%c"
 595     // and have an extra operand.
 596     if (FormatStr.size() != 2 || FormatStr[0] != '%' ||
 597         CI->getNumArgOperands() < 3)
 598       return 0;
 599
 600     // Decode the second character of the format string.
 601     if (FormatStr[1] == 'c') {
 602       // sprintf(dst, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0
 603       if (!CI->getArgOperand(2)->getType()->isIntegerTy()) return 0;
 604       Value *V = B.CreateTrunc(CI->getArgOperand(2), B.getInt8Ty(), "char");
 605       Value *Ptr = CastToCStr(CI->getArgOperand(0), B);
 606       B.CreateStore(V, Ptr);
 607       Ptr = B.CreateGEP(Ptr, B.getInt32(1), "nul");
 608       B.CreateStore(B.getInt8(0), Ptr);
 609
 610       return ConstantInt::get(CI->getType(), 1);
 611     }
 612
 613     if (FormatStr[1] == 's') {
 614       // These optimizations require DataLayout.
 615       if (!TD) return 0;
 616
 617       // sprintf(dest, "%s", str) -> llvm.memcpy(dest, str, strlen(str)+1, 1)
 618       if (!CI->getArgOperand(2)->getType()->isPointerTy()) return 0;
 619
 620       Value *Len = EmitStrLen(CI->getArgOperand(2), B, TD, TLI);
 621       if (!Len)
 622         return 0;
 623       Value *IncLen = B.CreateAdd(Len,
 624                                   ConstantInt::get(Len->getType(), 1),
 625                                   "leninc");
 626       B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(2), IncLen, 1);
 627
 628       // The sprintf result is the unincremented number of bytes in the string.
 629       return B.CreateIntCast(Len, CI->getType(), false);
 630     }
 631     return 0;
 632   }
 633
 634   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 635     // Require two fixed pointer arguments and an integer result.
 636     FunctionType *FT = Callee->getFunctionType();
 637     if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
 638         !FT->getParamType(1)->isPointerTy() ||
 639         !FT->getReturnType()->isIntegerTy())
 640       return 0;
 641
 642     if (Value *V = OptimizeFixedFormatString(Callee, CI, B)) {
 643       return V;
 644     }
 645
 646     // sprintf(str, format, ...) -> siprintf(str, format, ...) if no floating
 647     // point arguments.
 648     if (TLI->has(LibFunc::siprintf) && !CallHasFloatingPointArgument(CI)) {
 649       Module *M = B.GetInsertBlock()->getParent()->getParent();
 650       Constant *SIPrintFFn =
 651         M->getOrInsertFunction("siprintf", FT, Callee->getAttributes());
 652       CallInst *New = cast<CallInst>(CI->clone());
 653       New->setCalledFunction(SIPrintFFn);
 654       B.Insert(New);
 655       return New;
 656     }
 657     return 0;
 658   }
 659 };
 660
 661 //===---------------------------------------===//
 662 // 'fwrite' Optimizations
 663
 664 struct FWriteOpt : public LibCallOptimization {
 665   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 666     // Require a pointer, an integer, an integer, a pointer, returning integer.
 667     FunctionType *FT = Callee->getFunctionType();
 668     if (FT->getNumParams() != 4 || !FT->getParamType(0)->isPointerTy() ||
 669         !FT->getParamType(1)->isIntegerTy() ||
 670         !FT->getParamType(2)->isIntegerTy() ||
 671         !FT->getParamType(3)->isPointerTy() ||
 672         !FT->getReturnType()->isIntegerTy())
 673       return 0;
 674
 675     // Get the element size and count.
 676     ConstantInt *SizeC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
 677     ConstantInt *CountC = dyn_cast<ConstantInt>(CI->getArgOperand(2));
 678     if (!SizeC || !CountC) return 0;
 679     uint64_t Bytes = SizeC->getZExtValue()*CountC->getZExtValue();
 680
 681     // If this is writing zero records, remove the call (it's a noop).
 682     if (Bytes == 0)
 683       return ConstantInt::get(CI->getType(), 0);
 684
 685     // If this is writing one byte, turn it into fputc.
 686     // This optimisation is only valid, if the return value is unused.
 687     if (Bytes == 1 && CI->use_empty()) {  // fwrite(S,1,1,F) -> fputc(S[0],F)
 688       Value *Char = B.CreateLoad(CastToCStr(CI->getArgOperand(0), B), "char");
 689       Value *NewCI = EmitFPutC(Char, CI->getArgOperand(3), B, TD, TLI);
 690       return NewCI ? ConstantInt::get(CI->getType(), 1) : 0;
 691     }
 692
 693     return 0;
 694   }
 695 };
 696
 697 //===---------------------------------------===//
 698 // 'fputs' Optimizations
 699
 700 struct FPutsOpt : public LibCallOptimization {
 701   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 702     // These optimizations require DataLayout.
 703     if (!TD) return 0;
 704
 705     // Require two pointers.  Also, we can't optimize if return value is used.
 706     FunctionType *FT = Callee->getFunctionType();
 707     if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
 708         !FT->getParamType(1)->isPointerTy() ||
 709         !CI->use_empty())
 710       return 0;
 711
 712     // fputs(s,F) --> fwrite(s,1,strlen(s),F)
 713     uint64_t Len = GetStringLength(CI->getArgOperand(0));
 714     if (!Len) return 0;
 715     // Known to have no uses (see above).
 716     return EmitFWrite(CI->getArgOperand(0),
 717                       ConstantInt::get(TD->getIntPtrType(*Context), Len-1),
 718                       CI->getArgOperand(1), B, TD, TLI);
 719   }
 720 };
 721
 722 //===---------------------------------------===//
 723 // 'fprintf' Optimizations
 724
 725 struct FPrintFOpt : public LibCallOptimization {
 726   Value *OptimizeFixedFormatString(Function *Callee, CallInst *CI,
 727                                    IRBuilder<> &B) {
 728     // All the optimizations depend on the format string.
 729     StringRef FormatStr;
 730     if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr))
 731       return 0;
 732
 733     // fprintf(F, "foo") --> fwrite("foo", 3, 1, F)
 734     if (CI->getNumArgOperands() == 2) {
 735       for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
 736         if (FormatStr[i] == '%')  // Could handle %% -> % if we cared.
 737           return 0; // We found a format specifier.
 738
 739       // These optimizations require DataLayout.
 740       if (!TD) return 0;
 741
 742       Value *NewCI = EmitFWrite(CI->getArgOperand(1),
 743                                 ConstantInt::get(TD->getIntPtrType(*Context),
 744                                                  FormatStr.size()),
 745                                 CI->getArgOperand(0), B, TD, TLI);
 746       return NewCI ? ConstantInt::get(CI->getType(), FormatStr.size()) : 0;
 747     }
 748
 749     // The remaining optimizations require the format string to be "%s" or "%c"
 750     // and have an extra operand.
 751     if (FormatStr.size() != 2 || FormatStr[0] != '%' ||
 752         CI->getNumArgOperands() < 3)
 753       return 0;
 754
 755     // Decode the second character of the format string.
 756     if (FormatStr[1] == 'c') {
 757       // fprintf(F, "%c", chr) --> fputc(chr, F)
 758       if (!CI->getArgOperand(2)->getType()->isIntegerTy()) return 0;
 759       Value *NewCI = EmitFPutC(CI->getArgOperand(2), CI->getArgOperand(0), B,
 760                                TD, TLI);
 761       return NewCI ? ConstantInt::get(CI->getType(), 1) : 0;
 762     }
 763
 764     if (FormatStr[1] == 's') {
 765       // fprintf(F, "%s", str) --> fputs(str, F)
 766       if (!CI->getArgOperand(2)->getType()->isPointerTy() || !CI->use_empty())
 767         return 0;
 768       return EmitFPutS(CI->getArgOperand(2), CI->getArgOperand(0), B, TD, TLI);
 769     }
 770     return 0;
 771   }
 772
 773   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 774     // Require two fixed paramters as pointers and integer result.
 775     FunctionType *FT = Callee->getFunctionType();
 776     if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
 777         !FT->getParamType(1)->isPointerTy() ||
 778         !FT->getReturnType()->isIntegerTy())
 779       return 0;
 780
 781     if (Value *V = OptimizeFixedFormatString(Callee, CI, B)) {
 782       return V;
 783     }
 784
 785     // fprintf(stream, format, ...) -> fiprintf(stream, format, ...) if no
 786     // floating point arguments.
 787     if (TLI->has(LibFunc::fiprintf) && !CallHasFloatingPointArgument(CI)) {
 788       Module *M = B.GetInsertBlock()->getParent()->getParent();
 789       Constant *FIPrintFFn =
 790         M->getOrInsertFunction("fiprintf", FT, Callee->getAttributes());
 791       CallInst *New = cast<CallInst>(CI->clone());
 792       New->setCalledFunction(FIPrintFFn);
 793       B.Insert(New);
 794       return New;
 795     }
 796     return 0;
 797   }
 798 };
 799
 800 //===---------------------------------------===//
 801 // 'puts' Optimizations
 802
 803 struct PutsOpt : public LibCallOptimization {
 804   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 805     // Require one fixed pointer argument and an integer/void result.
 806     FunctionType *FT = Callee->getFunctionType();
 807     if (FT->getNumParams() < 1 || !FT->getParamType(0)->isPointerTy() ||
 808         !(FT->getReturnType()->isIntegerTy() ||
 809           FT->getReturnType()->isVoidTy()))
 810       return 0;
 811
 812     // Check for a constant string.
 813     StringRef Str;
 814     if (!getConstantStringInfo(CI->getArgOperand(0), Str))
 815       return 0;
 816
 817     if (Str.empty() && CI->use_empty()) {
 818       // puts("") -> putchar('\n')
 819       Value *Res = EmitPutChar(B.getInt32('\n'), B, TD, TLI);
 820       if (CI->use_empty() || !Res) return Res;
 821       return B.CreateIntCast(Res, CI->getType(), true);
 822     }
 823
 824     return 0;
 825   }
 826 };
 827
 828 } // end anonymous namespace.
 829
 830 //===----------------------------------------------------------------------===//
 831 // SimplifyLibCalls Pass Implementation
 832 //===----------------------------------------------------------------------===//
 833
 834 namespace {
 835   /// This pass optimizes well known library functions from libc and libm.
 836   ///
 837   class SimplifyLibCalls : public FunctionPass {
 838     TargetLibraryInfo *TLI;
 839
 840     StringMap<LibCallOptimization*> Optimizations;
 841     // Memory LibCall Optimizations
 842     MemCpyOpt MemCpy; MemMoveOpt MemMove; MemSetOpt MemSet;
 843     // Math Library Optimizations
 844     CosOpt Cos; PowOpt Pow; Exp2Opt Exp2;
 845     UnaryDoubleFPOpt UnaryDoubleFP, UnsafeUnaryDoubleFP;
 846     // Integer Optimizations
 847     FFSOpt FFS; AbsOpt Abs; IsDigitOpt IsDigit; IsAsciiOpt IsAscii;
 848     ToAsciiOpt ToAscii;
 849     // Formatting and IO Optimizations
 850     SPrintFOpt SPrintF; PrintFOpt PrintF;
 851     FWriteOpt FWrite; FPutsOpt FPuts; FPrintFOpt FPrintF;
 852     PutsOpt Puts;
 853
 854     bool Modified;  // This is only used by doInitialization.
 855   public:
 856     static char ID; // Pass identification
 857     SimplifyLibCalls() : FunctionPass(ID), UnaryDoubleFP(false),
 858                          UnsafeUnaryDoubleFP(true) {
 859       initializeSimplifyLibCallsPass(*PassRegistry::getPassRegistry());
 860     }
 861     void AddOpt(LibFunc::Func F, LibCallOptimization* Opt);
 862     void AddOpt(LibFunc::Func F1, LibFunc::Func F2, LibCallOptimization* Opt);
 863
 864     void InitOptimizations();
 865     bool runOnFunction(Function &F);
 866
 867     void setDoesNotAccessMemory(Function &F);
 868     void setOnlyReadsMemory(Function &F);
 869     void setDoesNotThrow(Function &F);
 870     void setDoesNotCapture(Function &F, unsigned n);
 871     void setDoesNotAlias(Function &F, unsigned n);
 872     bool doInitialization(Module &M);
 873
 874     void inferPrototypeAttributes(Function &F);
 875     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 876       AU.addRequired<TargetLibraryInfo>();
 877     }
 878   };
 879 } // end anonymous namespace.
 880
 881 char SimplifyLibCalls::ID = 0;
 882
 883 INITIALIZE_PASS_BEGIN(SimplifyLibCalls, "simplify-libcalls",
 884                       "Simplify well-known library calls", false, false)
 885 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
 886 INITIALIZE_PASS_END(SimplifyLibCalls, "simplify-libcalls",
 887                     "Simplify well-known library calls", false, false)
 888
 889 // Public interface to the Simplify LibCalls pass.
 890 FunctionPass *llvm::createSimplifyLibCallsPass() {
 891   return new SimplifyLibCalls();
 892 }
 893
 894 void SimplifyLibCalls::AddOpt(LibFunc::Func F, LibCallOptimization* Opt) {
 895   if (TLI->has(F))
 896     Optimizations[TLI->getName(F)] = Opt;
 897 }
 898
 899 void SimplifyLibCalls::AddOpt(LibFunc::Func F1, LibFunc::Func F2,
 900                               LibCallOptimization* Opt) {
 901   if (TLI->has(F1) && TLI->has(F2))
 902     Optimizations[TLI->getName(F1)] = Opt;
 903 }
 904
 905 /// Optimizations - Populate the Optimizations map with all the optimizations
 906 /// we know.
 907 void SimplifyLibCalls::InitOptimizations() {
 908   // Memory LibCall Optimizations
 909   AddOpt(LibFunc::memcpy, &MemCpy);
 910   Optimizations["memmove"] = &MemMove;
 911   AddOpt(LibFunc::memset, &MemSet);
 912
 913   // Math Library Optimizations
 914   Optimizations["cosf"] = &Cos;
 915   Optimizations["cos"] = &Cos;
 916   Optimizations["cosl"] = &Cos;
 917   Optimizations["powf"] = &Pow;
 918   Optimizations["pow"] = &Pow;
 919   Optimizations["powl"] = &Pow;
 920   Optimizations["llvm.pow.f32"] = &Pow;
 921   Optimizations["llvm.pow.f64"] = &Pow;
 922   Optimizations["llvm.pow.f80"] = &Pow;
 923   Optimizations["llvm.pow.f128"] = &Pow;
 924   Optimizations["llvm.pow.ppcf128"] = &Pow;
 925   Optimizations["exp2l"] = &Exp2;
 926   Optimizations["exp2"] = &Exp2;
 927   Optimizations["exp2f"] = &Exp2;
 928   Optimizations["llvm.exp2.ppcf128"] = &Exp2;
 929   Optimizations["llvm.exp2.f128"] = &Exp2;
 930   Optimizations["llvm.exp2.f80"] = &Exp2;
 931   Optimizations["llvm.exp2.f64"] = &Exp2;
 932   Optimizations["llvm.exp2.f32"] = &Exp2;
 933
 934   AddOpt(LibFunc::ceil, LibFunc::ceilf, &UnaryDoubleFP);
 935   AddOpt(LibFunc::fabs, LibFunc::fabsf, &UnaryDoubleFP);
 936   AddOpt(LibFunc::floor, LibFunc::floorf, &UnaryDoubleFP);
 937   AddOpt(LibFunc::rint, LibFunc::rintf, &UnaryDoubleFP);
 938   AddOpt(LibFunc::round, LibFunc::roundf, &UnaryDoubleFP);
 939   AddOpt(LibFunc::nearbyint, LibFunc::nearbyintf, &UnaryDoubleFP);
 940   AddOpt(LibFunc::trunc, LibFunc::truncf, &UnaryDoubleFP);
 941
 942   if(UnsafeFPShrink) {
 943     AddOpt(LibFunc::acos, LibFunc::acosf, &UnsafeUnaryDoubleFP);
 944     AddOpt(LibFunc::acosh, LibFunc::acoshf, &UnsafeUnaryDoubleFP);
 945     AddOpt(LibFunc::asin, LibFunc::asinf, &UnsafeUnaryDoubleFP);
 946     AddOpt(LibFunc::asinh, LibFunc::asinhf, &UnsafeUnaryDoubleFP);
 947     AddOpt(LibFunc::atan, LibFunc::atanf, &UnsafeUnaryDoubleFP);
 948     AddOpt(LibFunc::atanh, LibFunc::atanhf, &UnsafeUnaryDoubleFP);
 949     AddOpt(LibFunc::cbrt, LibFunc::cbrtf, &UnsafeUnaryDoubleFP);
 950     AddOpt(LibFunc::cosh, LibFunc::coshf, &UnsafeUnaryDoubleFP);
 951     AddOpt(LibFunc::exp, LibFunc::expf, &UnsafeUnaryDoubleFP);
 952     AddOpt(LibFunc::exp10, LibFunc::exp10f, &UnsafeUnaryDoubleFP);
 953     AddOpt(LibFunc::expm1, LibFunc::expm1f, &UnsafeUnaryDoubleFP);
 954     AddOpt(LibFunc::log, LibFunc::logf, &UnsafeUnaryDoubleFP);
 955     AddOpt(LibFunc::log10, LibFunc::log10f, &UnsafeUnaryDoubleFP);
 956     AddOpt(LibFunc::log1p, LibFunc::log1pf, &UnsafeUnaryDoubleFP);
 957     AddOpt(LibFunc::log2, LibFunc::log2f, &UnsafeUnaryDoubleFP);
 958     AddOpt(LibFunc::logb, LibFunc::logbf, &UnsafeUnaryDoubleFP);
 959     AddOpt(LibFunc::sin, LibFunc::sinf, &UnsafeUnaryDoubleFP);
 960     AddOpt(LibFunc::sinh, LibFunc::sinhf, &UnsafeUnaryDoubleFP);
 961     AddOpt(LibFunc::sqrt, LibFunc::sqrtf, &UnsafeUnaryDoubleFP);
 962     AddOpt(LibFunc::tan, LibFunc::tanf, &UnsafeUnaryDoubleFP);
 963     AddOpt(LibFunc::tanh, LibFunc::tanhf, &UnsafeUnaryDoubleFP);
 964   }
 965
 966   // Integer Optimizations
 967   Optimizations["ffs"] = &FFS;
 968   Optimizations["ffsl"] = &FFS;
 969   Optimizations["ffsll"] = &FFS;
 970   Optimizations["abs"] = &Abs;
 971   Optimizations["labs"] = &Abs;
 972   Optimizations["llabs"] = &Abs;
 973   Optimizations["isdigit"] = &IsDigit;
 974   Optimizations["isascii"] = &IsAscii;
 975   Optimizations["toascii"] = &ToAscii;
 976
 977   // Formatting and IO Optimizations
 978   Optimizations["sprintf"] = &SPrintF;
 979   Optimizations["printf"] = &PrintF;
 980   AddOpt(LibFunc::fwrite, &FWrite);
 981   AddOpt(LibFunc::fputs, &FPuts);
 982   Optimizations["fprintf"] = &FPrintF;
 983   Optimizations["puts"] = &Puts;
 984 }
 985
 986
 987 /// runOnFunction - Top level algorithm.
 988 ///
 989 bool SimplifyLibCalls::runOnFunction(Function &F) {
 990   TLI = &getAnalysis<TargetLibraryInfo>();
 991
 992   if (Optimizations.empty())
 993     InitOptimizations();
 994
 995   const DataLayout *TD = getAnalysisIfAvailable<DataLayout>();
 996
 997   IRBuilder<> Builder(F.getContext());
 998
 999   bool Changed = false;
1000   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
1001     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
1002       // Ignore non-calls.
1003       CallInst *CI = dyn_cast<CallInst>(I++);
1004       if (!CI) continue;
1005
1006       // Ignore indirect calls and calls to non-external functions.
1007       Function *Callee = CI->getCalledFunction();
1008       if (Callee == 0 || !Callee->isDeclaration() ||
1009           !(Callee->hasExternalLinkage() || Callee->hasDLLImportLinkage()))
1010         continue;
1011
1012       // Ignore unknown calls.
1013       LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
1014       if (!LCO) continue;
1015
1016       // Set the builder to the instruction after the call.
1017       Builder.SetInsertPoint(BB, I);
1018
1019       // Use debug location of CI for all new instructions.
1020       Builder.SetCurrentDebugLocation(CI->getDebugLoc());
1021
1022       // Try to optimize this call.
1023       Value *Result = LCO->OptimizeCall(CI, TD, TLI, Builder);
1024       if (Result == 0) continue;
1025
1026       DEBUG(dbgs() << "SimplifyLibCalls simplified: " << *CI;
1027             dbgs() << "  into: " << *Result << "\n");
1028
1029       // Something changed!
1030       Changed = true;
1031       ++NumSimplified;
1032
1033       // Inspect the instruction after the call (which was potentially just
1034       // added) next.
1035       I = CI; ++I;
1036
1037       if (CI != Result && !CI->use_empty()) {
1038         CI->replaceAllUsesWith(Result);
1039         if (!Result->hasName())
1040           Result->takeName(CI);
1041       }
1042       CI->eraseFromParent();
1043     }
1044   }
1045   return Changed;
1046 }
1047
1048 // Utility methods for doInitialization.
1049
1050 void SimplifyLibCalls::setDoesNotAccessMemory(Function &F) {
1051   if (!F.doesNotAccessMemory()) {
1052     F.setDoesNotAccessMemory();
1053     ++NumAnnotated;
1054     Modified = true;
1055   }
1056 }
1057 void SimplifyLibCalls::setOnlyReadsMemory(Function &F) {
1058   if (!F.onlyReadsMemory()) {
1059     F.setOnlyReadsMemory();
1060     ++NumAnnotated;
1061     Modified = true;
1062   }
1063 }
1064 void SimplifyLibCalls::setDoesNotThrow(Function &F) {
1065   if (!F.doesNotThrow()) {
1066     F.setDoesNotThrow();
1067     ++NumAnnotated;
1068     Modified = true;
1069   }
1070 }
1071 void SimplifyLibCalls::setDoesNotCapture(Function &F, unsigned n) {
1072   if (!F.doesNotCapture(n)) {
1073     F.setDoesNotCapture(n);
1074     ++NumAnnotated;
1075     Modified = true;
1076   }
1077 }
1078 void SimplifyLibCalls::setDoesNotAlias(Function &F, unsigned n) {
1079   if (!F.doesNotAlias(n)) {
1080     F.setDoesNotAlias(n);
1081     ++NumAnnotated;
1082     Modified = true;
1083   }
1084 }
1085
1086
1087 void SimplifyLibCalls::inferPrototypeAttributes(Function &F) {
1088   FunctionType *FTy = F.getFunctionType();
1089
1090   StringRef Name = F.getName();
1091   switch (Name[0]) {
1092   case 's':
1093     if (Name == "strlen") {
1094       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1095         return;
1096       setOnlyReadsMemory(F);
1097       setDoesNotThrow(F);
1098       setDoesNotCapture(F, 1);
1099     } else if (Name == "strchr" ||
1100                Name == "strrchr") {
1101       if (FTy->getNumParams() != 2 ||
1102           !FTy->getParamType(0)->isPointerTy() ||
1103           !FTy->getParamType(1)->isIntegerTy())
1104         return;
1105       setOnlyReadsMemory(F);
1106       setDoesNotThrow(F);
1107     } else if (Name == "strcpy" ||
1108                Name == "stpcpy" ||
1109                Name == "strcat" ||
1110                Name == "strtol" ||
1111                Name == "strtod" ||
1112                Name == "strtof" ||
1113                Name == "strtoul" ||
1114                Name == "strtoll" ||
1115                Name == "strtold" ||
1116                Name == "strncat" ||
1117                Name == "strncpy" ||
1118                Name == "stpncpy" ||
1119                Name == "strtoull") {
1120       if (FTy->getNumParams() < 2 ||
1121           !FTy->getParamType(1)->isPointerTy())
1122         return;
1123       setDoesNotThrow(F);
1124       setDoesNotCapture(F, 2);
1125     } else if (Name == "strxfrm") {
1126       if (FTy->getNumParams() != 3 ||
1127           !FTy->getParamType(0)->isPointerTy() ||
1128           !FTy->getParamType(1)->isPointerTy())
1129         return;
1130       setDoesNotThrow(F);
1131       setDoesNotCapture(F, 1);
1132       setDoesNotCapture(F, 2);
1133     } else if (Name == "strcmp" ||
1134                Name == "strspn" ||
1135                Name == "strncmp" ||
1136                Name == "strcspn" ||
1137                Name == "strcoll" ||
1138                Name == "strcasecmp" ||
1139                Name == "strncasecmp") {
1140       if (FTy->getNumParams() < 2 ||
1141           !FTy->getParamType(0)->isPointerTy() ||
1142           !FTy->getParamType(1)->isPointerTy())
1143         return;
1144       setOnlyReadsMemory(F);
1145       setDoesNotThrow(F);
1146       setDoesNotCapture(F, 1);
1147       setDoesNotCapture(F, 2);
1148     } else if (Name == "strstr" ||
1149                Name == "strpbrk") {
1150       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1151         return;
1152       setOnlyReadsMemory(F);
1153       setDoesNotThrow(F);
1154       setDoesNotCapture(F, 2);
1155     } else if (Name == "strtok" ||
1156                Name == "strtok_r") {
1157       if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
1158         return;
1159       setDoesNotThrow(F);
1160       setDoesNotCapture(F, 2);
1161     } else if (Name == "scanf" ||
1162                Name == "setbuf" ||
1163                Name == "setvbuf") {
1164       if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
1165         return;
1166       setDoesNotThrow(F);
1167       setDoesNotCapture(F, 1);
1168     } else if (Name == "strdup" ||
1169                Name == "strndup") {
1170       if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() ||
1171           !FTy->getParamType(0)->isPointerTy())
1172         return;
1173       setDoesNotThrow(F);
1174       setDoesNotAlias(F, 0);
1175       setDoesNotCapture(F, 1);
1176     } else if (Name == "stat" ||
1177                Name == "sscanf" ||
1178                Name == "sprintf" ||
1179                Name == "statvfs") {
1180       if (FTy->getNumParams() < 2 ||
1181           !FTy->getParamType(0)->isPointerTy() ||
1182           !FTy->getParamType(1)->isPointerTy())
1183         return;
1184       setDoesNotThrow(F);
1185       setDoesNotCapture(F, 1);
1186       setDoesNotCapture(F, 2);
1187     } else if (Name == "snprintf") {
1188       if (FTy->getNumParams() != 3 ||
1189           !FTy->getParamType(0)->isPointerTy() ||
1190           !FTy->getParamType(2)->isPointerTy())
1191         return;
1192       setDoesNotThrow(F);
1193       setDoesNotCapture(F, 1);
1194       setDoesNotCapture(F, 3);
1195     } else if (Name == "setitimer") {
1196       if (FTy->getNumParams() != 3 ||
1197           !FTy->getParamType(1)->isPointerTy() ||
1198           !FTy->getParamType(2)->isPointerTy())
1199         return;
1200       setDoesNotThrow(F);
1201       setDoesNotCapture(F, 2);
1202       setDoesNotCapture(F, 3);
1203     } else if (Name == "system") {
1204       if (FTy->getNumParams() != 1 ||
1205           !FTy->getParamType(0)->isPointerTy())
1206         return;
1207       // May throw; "system" is a valid pthread cancellation point.
1208       setDoesNotCapture(F, 1);
1209     }
1210     break;
1211   case 'm':
1212     if (Name == "malloc") {
1213       if (FTy->getNumParams() != 1 ||
1214           !FTy->getReturnType()->isPointerTy())
1215         return;
1216       setDoesNotThrow(F);
1217       setDoesNotAlias(F, 0);
1218     } else if (Name == "memcmp") {
1219       if (FTy->getNumParams() != 3 ||
1220           !FTy->getParamType(0)->isPointerTy() ||
1221           !FTy->getParamType(1)->isPointerTy())
1222         return;
1223       setOnlyReadsMemory(F);
1224       setDoesNotThrow(F);
1225       setDoesNotCapture(F, 1);
1226       setDoesNotCapture(F, 2);
1227     } else if (Name == "memchr" ||
1228                Name == "memrchr") {
1229       if (FTy->getNumParams() != 3)
1230         return;
1231       setOnlyReadsMemory(F);
1232       setDoesNotThrow(F);
1233     } else if (Name == "modf" ||
1234                Name == "modff" ||
1235                Name == "modfl" ||
1236                Name == "memcpy" ||
1237                Name == "memccpy" ||
1238                Name == "memmove") {
1239       if (FTy->getNumParams() < 2 ||
1240           !FTy->getParamType(1)->isPointerTy())
1241         return;
1242       setDoesNotThrow(F);
1243       setDoesNotCapture(F, 2);
1244     } else if (Name == "memalign") {
1245       if (!FTy->getReturnType()->isPointerTy())
1246         return;
1247       setDoesNotAlias(F, 0);
1248     } else if (Name == "mkdir" ||
1249                Name == "mktime") {
1250       if (FTy->getNumParams() == 0 ||
1251           !FTy->getParamType(0)->isPointerTy())
1252         return;
1253       setDoesNotThrow(F);
1254       setDoesNotCapture(F, 1);
1255     }
1256     break;
1257   case 'r':
1258     if (Name == "realloc") {
1259       if (FTy->getNumParams() != 2 ||
1260           !FTy->getParamType(0)->isPointerTy() ||
1261           !FTy->getReturnType()->isPointerTy())
1262         return;
1263       setDoesNotThrow(F);
1264       setDoesNotAlias(F, 0);
1265       setDoesNotCapture(F, 1);
1266     } else if (Name == "read") {
1267       if (FTy->getNumParams() != 3 ||
1268           !FTy->getParamType(1)->isPointerTy())
1269         return;
1270       // May throw; "read" is a valid pthread cancellation point.
1271       setDoesNotCapture(F, 2);
1272     } else if (Name == "rmdir" ||
1273                Name == "rewind" ||
1274                Name == "remove" ||
1275                Name == "realpath") {
1276       if (FTy->getNumParams() < 1 ||
1277           !FTy->getParamType(0)->isPointerTy())
1278         return;
1279       setDoesNotThrow(F);
1280       setDoesNotCapture(F, 1);
1281     } else if (Name == "rename" ||
1282                Name == "readlink") {
1283       if (FTy->getNumParams() < 2 ||
1284           !FTy->getParamType(0)->isPointerTy() ||
1285           !FTy->getParamType(1)->isPointerTy())
1286         return;
1287       setDoesNotThrow(F);
1288       setDoesNotCapture(F, 1);
1289       setDoesNotCapture(F, 2);
1290     }
1291     break;
1292   case 'w':
1293     if (Name == "write") {
1294       if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
1295         return;
1296       // May throw; "write" is a valid pthread cancellation point.
1297       setDoesNotCapture(F, 2);
1298     }
1299     break;
1300   case 'b':
1301     if (Name == "bcopy") {
1302       if (FTy->getNumParams() != 3 ||
1303           !FTy->getParamType(0)->isPointerTy() ||
1304           !FTy->getParamType(1)->isPointerTy())
1305         return;
1306       setDoesNotThrow(F);
1307       setDoesNotCapture(F, 1);
1308       setDoesNotCapture(F, 2);
1309     } else if (Name == "bcmp") {
1310       if (FTy->getNumParams() != 3 ||
1311           !FTy->getParamType(0)->isPointerTy() ||
1312           !FTy->getParamType(1)->isPointerTy())
1313         return;
1314       setDoesNotThrow(F);
1315       setOnlyReadsMemory(F);
1316       setDoesNotCapture(F, 1);
1317       setDoesNotCapture(F, 2);
1318     } else if (Name == "bzero") {
1319       if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1320         return;
1321       setDoesNotThrow(F);
1322       setDoesNotCapture(F, 1);
1323     }
1324     break;
1325   case 'c':
1326     if (Name == "calloc") {
1327       if (FTy->getNumParams() != 2 ||
1328           !FTy->getReturnType()->isPointerTy())
1329         return;
1330       setDoesNotThrow(F);
1331       setDoesNotAlias(F, 0);
1332     } else if (Name == "chmod" ||
1333                Name == "chown" ||
1334                Name == "ctermid" ||
1335                Name == "clearerr" ||
1336                Name == "closedir") {
1337       if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1338         return;
1339       setDoesNotThrow(F);
1340       setDoesNotCapture(F, 1);
1341     }
1342     break;
1343   case 'a':
1344     if (Name == "atoi" ||
1345         Name == "atol" ||
1346         Name == "atof" ||
1347         Name == "atoll") {
1348       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1349         return;
1350       setDoesNotThrow(F);
1351       setOnlyReadsMemory(F);
1352       setDoesNotCapture(F, 1);
1353     } else if (Name == "access") {
1354       if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1355         return;
1356       setDoesNotThrow(F);
1357       setDoesNotCapture(F, 1);
1358     }
1359     break;
1360   case 'f':
1361     if (Name == "fopen") {
1362       if (FTy->getNumParams() != 2 ||
1363           !FTy->getReturnType()->isPointerTy() ||
1364           !FTy->getParamType(0)->isPointerTy() ||
1365           !FTy->getParamType(1)->isPointerTy())
1366         return;
1367       setDoesNotThrow(F);
1368       setDoesNotAlias(F, 0);
1369       setDoesNotCapture(F, 1);
1370       setDoesNotCapture(F, 2);
1371     } else if (Name == "fdopen") {
1372       if (FTy->getNumParams() != 2 ||
1373           !FTy->getReturnType()->isPointerTy() ||
1374           !FTy->getParamType(1)->isPointerTy())
1375         return;
1376       setDoesNotThrow(F);
1377       setDoesNotAlias(F, 0);
1378       setDoesNotCapture(F, 2);
1379     } else if (Name == "feof" ||
1380                Name == "free" ||
1381                Name == "fseek" ||
1382                Name == "ftell" ||
1383                Name == "fgetc" ||
1384                Name == "fseeko" ||
1385                Name == "ftello" ||
1386                Name == "fileno" ||
1387                Name == "fflush" ||
1388                Name == "fclose" ||
1389                Name == "fsetpos" ||
1390                Name == "flockfile" ||
1391                Name == "funlockfile" ||
1392                Name == "ftrylockfile") {
1393       if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1394         return;
1395       setDoesNotThrow(F);
1396       setDoesNotCapture(F, 1);
1397     } else if (Name == "ferror") {
1398       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1399         return;
1400       setDoesNotThrow(F);
1401       setDoesNotCapture(F, 1);
1402       setOnlyReadsMemory(F);
1403     } else if (Name == "fputc" ||
1404                Name == "fstat" ||
1405                Name == "frexp" ||
1406                Name == "frexpf" ||
1407                Name == "frexpl" ||
1408                Name == "fstatvfs") {
1409       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1410         return;
1411       setDoesNotThrow(F);
1412       setDoesNotCapture(F, 2);
1413     } else if (Name == "fgets") {
1414       if (FTy->getNumParams() != 3 ||
1415           !FTy->getParamType(0)->isPointerTy() ||
1416           !FTy->getParamType(2)->isPointerTy())
1417         return;
1418       setDoesNotThrow(F);
1419       setDoesNotCapture(F, 3);
1420     } else if (Name == "fread" ||
1421                Name == "fwrite") {
1422       if (FTy->getNumParams() != 4 ||
1423           !FTy->getParamType(0)->isPointerTy() ||
1424           !FTy->getParamType(3)->isPointerTy())
1425         return;
1426       setDoesNotThrow(F);
1427       setDoesNotCapture(F, 1);
1428       setDoesNotCapture(F, 4);
1429     } else if (Name == "fputs" ||
1430                Name == "fscanf" ||
1431                Name == "fprintf" ||
1432                Name == "fgetpos") {
1433       if (FTy->getNumParams() < 2 ||
1434           !FTy->getParamType(0)->isPointerTy() ||
1435           !FTy->getParamType(1)->isPointerTy())
1436         return;
1437       setDoesNotThrow(F);
1438       setDoesNotCapture(F, 1);
1439       setDoesNotCapture(F, 2);
1440     }
1441     break;
1442   case 'g':
1443     if (Name == "getc" ||
1444         Name == "getlogin_r" ||
1445         Name == "getc_unlocked") {
1446       if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1447         return;
1448       setDoesNotThrow(F);
1449       setDoesNotCapture(F, 1);
1450     } else if (Name == "getenv") {
1451       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1452         return;
1453       setDoesNotThrow(F);
1454       setOnlyReadsMemory(F);
1455       setDoesNotCapture(F, 1);
1456     } else if (Name == "gets" ||
1457                Name == "getchar") {
1458       setDoesNotThrow(F);
1459     } else if (Name == "getitimer") {
1460       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1461         return;
1462       setDoesNotThrow(F);
1463       setDoesNotCapture(F, 2);
1464     } else if (Name == "getpwnam") {
1465       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1466         return;
1467       setDoesNotThrow(F);
1468       setDoesNotCapture(F, 1);
1469     }
1470     break;
1471   case 'u':
1472     if (Name == "ungetc") {
1473       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1474         return;
1475       setDoesNotThrow(F);
1476       setDoesNotCapture(F, 2);
1477     } else if (Name == "uname" ||
1478                Name == "unlink" ||
1479                Name == "unsetenv") {
1480       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1481         return;
1482       setDoesNotThrow(F);
1483       setDoesNotCapture(F, 1);
1484     } else if (Name == "utime" ||
1485                Name == "utimes") {
1486       if (FTy->getNumParams() != 2 ||
1487           !FTy->getParamType(0)->isPointerTy() ||
1488           !FTy->getParamType(1)->isPointerTy())
1489         return;
1490       setDoesNotThrow(F);
1491       setDoesNotCapture(F, 1);
1492       setDoesNotCapture(F, 2);
1493     }
1494     break;
1495   case 'p':
1496     if (Name == "putc") {
1497       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1498         return;
1499       setDoesNotThrow(F);
1500       setDoesNotCapture(F, 2);
1501     } else if (Name == "puts" ||
1502                Name == "printf" ||
1503                Name == "perror") {
1504       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1505         return;
1506       setDoesNotThrow(F);
1507       setDoesNotCapture(F, 1);
1508     } else if (Name == "pread" ||
1509                Name == "pwrite") {
1510       if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
1511         return;
1512       // May throw; these are valid pthread cancellation points.
1513       setDoesNotCapture(F, 2);
1514     } else if (Name == "putchar") {
1515       setDoesNotThrow(F);
1516     } else if (Name == "popen") {
1517       if (FTy->getNumParams() != 2 ||
1518           !FTy->getReturnType()->isPointerTy() ||
1519           !FTy->getParamType(0)->isPointerTy() ||
1520           !FTy->getParamType(1)->isPointerTy())
1521         return;
1522       setDoesNotThrow(F);
1523       setDoesNotAlias(F, 0);
1524       setDoesNotCapture(F, 1);
1525       setDoesNotCapture(F, 2);
1526     } else if (Name == "pclose") {
1527       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1528         return;
1529       setDoesNotThrow(F);
1530       setDoesNotCapture(F, 1);
1531     }
1532     break;
1533   case 'v':
1534     if (Name == "vscanf") {
1535       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1536         return;
1537       setDoesNotThrow(F);
1538       setDoesNotCapture(F, 1);
1539     } else if (Name == "vsscanf" ||
1540                Name == "vfscanf") {
1541       if (FTy->getNumParams() != 3 ||
1542           !FTy->getParamType(1)->isPointerTy() ||
1543           !FTy->getParamType(2)->isPointerTy())
1544         return;
1545       setDoesNotThrow(F);
1546       setDoesNotCapture(F, 1);
1547       setDoesNotCapture(F, 2);
1548     } else if (Name == "valloc") {
1549       if (!FTy->getReturnType()->isPointerTy())
1550         return;
1551       setDoesNotThrow(F);
1552       setDoesNotAlias(F, 0);
1553     } else if (Name == "vprintf") {
1554       if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1555         return;
1556       setDoesNotThrow(F);
1557       setDoesNotCapture(F, 1);
1558     } else if (Name == "vfprintf" ||
1559                Name == "vsprintf") {
1560       if (FTy->getNumParams() != 3 ||
1561           !FTy->getParamType(0)->isPointerTy() ||
1562           !FTy->getParamType(1)->isPointerTy())
1563         return;
1564       setDoesNotThrow(F);
1565       setDoesNotCapture(F, 1);
1566       setDoesNotCapture(F, 2);
1567     } else if (Name == "vsnprintf") {
1568       if (FTy->getNumParams() != 4 ||
1569           !FTy->getParamType(0)->isPointerTy() ||
1570           !FTy->getParamType(2)->isPointerTy())
1571         return;
1572       setDoesNotThrow(F);
1573       setDoesNotCapture(F, 1);
1574       setDoesNotCapture(F, 3);
1575     }
1576     break;
1577   case 'o':
1578     if (Name == "open") {
1579       if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
1580         return;
1581       // May throw; "open" is a valid pthread cancellation point.
1582       setDoesNotCapture(F, 1);
1583     } else if (Name == "opendir") {
1584       if (FTy->getNumParams() != 1 ||
1585           !FTy->getReturnType()->isPointerTy() ||
1586           !FTy->getParamType(0)->isPointerTy())
1587         return;
1588       setDoesNotThrow(F);
1589       setDoesNotAlias(F, 0);
1590       setDoesNotCapture(F, 1);
1591     }
1592     break;
1593   case 't':
1594     if (Name == "tmpfile") {
1595       if (!FTy->getReturnType()->isPointerTy())
1596         return;
1597       setDoesNotThrow(F);
1598       setDoesNotAlias(F, 0);
1599     } else if (Name == "times") {
1600       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1601         return;
1602       setDoesNotThrow(F);
1603       setDoesNotCapture(F, 1);
1604     }
1605     break;
1606   case 'h':
1607     if (Name == "htonl" ||
1608         Name == "htons") {
1609       setDoesNotThrow(F);
1610       setDoesNotAccessMemory(F);
1611     }
1612     break;
1613   case 'n':
1614     if (Name == "ntohl" ||
1615         Name == "ntohs") {
1616       setDoesNotThrow(F);
1617       setDoesNotAccessMemory(F);
1618     }
1619     break;
1620   case 'l':
1621     if (Name == "lstat") {
1622       if (FTy->getNumParams() != 2 ||
1623           !FTy->getParamType(0)->isPointerTy() ||
1624           !FTy->getParamType(1)->isPointerTy())
1625         return;
1626       setDoesNotThrow(F);
1627       setDoesNotCapture(F, 1);
1628       setDoesNotCapture(F, 2);
1629     } else if (Name == "lchown") {
1630       if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy())
1631         return;
1632       setDoesNotThrow(F);
1633       setDoesNotCapture(F, 1);
1634     }
1635     break;
1636   case 'q':
1637     if (Name == "qsort") {
1638       if (FTy->getNumParams() != 4 || !FTy->getParamType(3)->isPointerTy())
1639         return;
1640       // May throw; places call through function pointer.
1641       setDoesNotCapture(F, 4);
1642     }
1643     break;
1644   case '_':
1645     if (Name == "__strdup" ||
1646         Name == "__strndup") {
1647       if (FTy->getNumParams() < 1 ||
1648           !FTy->getReturnType()->isPointerTy() ||
1649           !FTy->getParamType(0)->isPointerTy())
1650         return;
1651       setDoesNotThrow(F);
1652       setDoesNotAlias(F, 0);
1653       setDoesNotCapture(F, 1);
1654     } else if (Name == "__strtok_r") {
1655       if (FTy->getNumParams() != 3 ||
1656           !FTy->getParamType(1)->isPointerTy())
1657         return;
1658       setDoesNotThrow(F);
1659       setDoesNotCapture(F, 2);
1660     } else if (Name == "_IO_getc") {
1661       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1662         return;
1663       setDoesNotThrow(F);
1664       setDoesNotCapture(F, 1);
1665     } else if (Name == "_IO_putc") {
1666       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1667         return;
1668       setDoesNotThrow(F);
1669       setDoesNotCapture(F, 2);
1670     }
1671     break;
1672   case 1:
1673     if (Name == "\1__isoc99_scanf") {
1674       if (FTy->getNumParams() < 1 ||
1675           !FTy->getParamType(0)->isPointerTy())
1676         return;
1677       setDoesNotThrow(F);
1678       setDoesNotCapture(F, 1);
1679     } else if (Name == "\1stat64" ||
1680                Name == "\1lstat64" ||
1681                Name == "\1statvfs64" ||
1682                Name == "\1__isoc99_sscanf") {
1683       if (FTy->getNumParams() < 1 ||
1684           !FTy->getParamType(0)->isPointerTy() ||
1685           !FTy->getParamType(1)->isPointerTy())
1686         return;
1687       setDoesNotThrow(F);
1688       setDoesNotCapture(F, 1);
1689       setDoesNotCapture(F, 2);
1690     } else if (Name == "\1fopen64") {
1691       if (FTy->getNumParams() != 2 ||
1692           !FTy->getReturnType()->isPointerTy() ||
1693           !FTy->getParamType(0)->isPointerTy() ||
1694           !FTy->getParamType(1)->isPointerTy())
1695         return;
1696       setDoesNotThrow(F);
1697       setDoesNotAlias(F, 0);
1698       setDoesNotCapture(F, 1);
1699       setDoesNotCapture(F, 2);
1700     } else if (Name == "\1fseeko64" ||
1701                Name == "\1ftello64") {
1702       if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1703         return;
1704       setDoesNotThrow(F);
1705       setDoesNotCapture(F, 1);
1706     } else if (Name == "\1tmpfile64") {
1707       if (!FTy->getReturnType()->isPointerTy())
1708         return;
1709       setDoesNotThrow(F);
1710       setDoesNotAlias(F, 0);
1711     } else if (Name == "\1fstat64" ||
1712                Name == "\1fstatvfs64") {
1713       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1714         return;
1715       setDoesNotThrow(F);
1716       setDoesNotCapture(F, 2);
1717     } else if (Name == "\1open64") {
1718       if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
1719         return;
1720       // May throw; "open" is a valid pthread cancellation point.
1721       setDoesNotCapture(F, 1);
1722     }
1723     break;
1724   }
1725 }
1726
1727 /// doInitialization - Add attributes to well-known functions.
1728 ///
1729 bool SimplifyLibCalls::doInitialization(Module &M) {
1730   Modified = false;
1731   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
1732     Function &F = *I;
1733     if (F.isDeclaration() && F.hasName())
1734       inferPrototypeAttributes(F);
1735   }
1736   return Modified;
1737 }
1738
1739 // TODO:
1740 //   Additional cases that we need to add to this file:
1741 //
1742 // cbrt:
1743 //   * cbrt(expN(X))  -> expN(x/3)
1744 //   * cbrt(sqrt(x))  -> pow(x,1/6)
1745 //   * cbrt(sqrt(x))  -> pow(x,1/9)
1746 //
1747 // exp, expf, expl:
1748 //   * exp(log(x))  -> x
1749 //
1750 // log, logf, logl:
1751 //   * log(exp(x))   -> x
1752 //   * log(x**y)     -> y*log(x)
1753 //   * log(exp(y))   -> y*log(e)
1754 //   * log(exp2(y))  -> y*log(2)
1755 //   * log(exp10(y)) -> y*log(10)
1756 //   * log(sqrt(x))  -> 0.5*log(x)
1757 //   * log(pow(x,y)) -> y*log(x)
1758 //
1759 // lround, lroundf, lroundl:
1760 //   * lround(cnst) -> cnst'
1761 //
1762 // pow, powf, powl:
1763 //   * pow(exp(x),y)  -> exp(x*y)
1764 //   * pow(sqrt(x),y) -> pow(x,y*0.5)
1765 //   * pow(pow(x,y),z)-> pow(x,y*z)
1766 //
1767 // round, roundf, roundl:
1768 //   * round(cnst) -> cnst'
1769 //
1770 // signbit:
1771 //   * signbit(cnst) -> cnst'
1772 //   * signbit(nncst) -> 0 (if pstv is a non-negative constant)
1773 //
1774 // sqrt, sqrtf, sqrtl:
1775 //   * sqrt(expN(x))  -> expN(x*0.5)
1776 //   * sqrt(Nroot(x)) -> pow(x,1/(2*N))
1777 //   * sqrt(pow(x,y)) -> pow(|x|,y*0.5)
1778 //
1779 // strchr:
1780 //   * strchr(p, 0) -> strlen(p)
1781 // tan, tanf, tanl:
1782 //   * tan(atan(x)) -> x
1783 //
1784 // trunc, truncf, truncl:
1785 //   * trunc(cnst) -> cnst'
1786 //
1787 //