lib/Transforms/Utils/SimplifyLibCalls.cpp

   1 //===------ SimplifyLibCalls.cpp - Library calls simplifier ---------------===//
   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 is a utility pass used for testing the InstructionSimplify analysis.
  11 // The analysis is applied to every instruction, and if it simplifies then the
  12 // instruction is replaced by the simplification.  If you are looking for a pass
  13 // that performs serious instruction folding, use the instcombine pass instead.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/Transforms/Utils/SimplifyLibCalls.h"
  18 #include "llvm/ADT/SmallString.h"
  19 #include "llvm/ADT/StringMap.h"
  20 #include "llvm/Analysis/ValueTracking.h"
  21 #include "llvm/IR/DataLayout.h"
  22 #include "llvm/IR/Function.h"
  23 #include "llvm/IR/IRBuilder.h"
  24 #include "llvm/IR/IntrinsicInst.h"
  25 #include "llvm/IR/Intrinsics.h"
  26 #include "llvm/IR/LLVMContext.h"
  27 #include "llvm/IR/Module.h"
  28 #include "llvm/Support/Allocator.h"
  29 #include "llvm/Target/TargetLibraryInfo.h"
  30 #include "llvm/Transforms/Utils/BuildLibCalls.h"
  31
  32 using namespace llvm;
  33
  34 /// This class is the abstract base class for the set of optimizations that
  35 /// corresponds to one library call.
  36 namespace {
  37 class LibCallOptimization {
  38 protected:
  39   Function *Caller;
  40   const DataLayout *TD;
  41   const TargetLibraryInfo *TLI;
  42   const LibCallSimplifier *LCS;
  43   LLVMContext* Context;
  44 public:
  45   LibCallOptimization() { }
  46   virtual ~LibCallOptimization() {}
  47
  48   /// callOptimizer - This pure virtual method is implemented by base classes to
  49   /// do various optimizations.  If this returns null then no transformation was
  50   /// performed.  If it returns CI, then it transformed the call and CI is to be
  51   /// deleted.  If it returns something else, replace CI with the new value and
  52   /// delete CI.
  53   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B)
  54     =0;
  55
  56   /// ignoreCallingConv - Returns false if this transformation could possibly
  57   /// change the calling convention.
  58   virtual bool ignoreCallingConv() { return false; }
  59
  60   Value *optimizeCall(CallInst *CI, const DataLayout *TD,
  61                       const TargetLibraryInfo *TLI,
  62                       const LibCallSimplifier *LCS, IRBuilder<> &B) {
  63     Caller = CI->getParent()->getParent();
  64     this->TD = TD;
  65     this->TLI = TLI;
  66     this->LCS = LCS;
  67     if (CI->getCalledFunction())
  68       Context = &CI->getCalledFunction()->getContext();
  69
  70     // We never change the calling convention.
  71     if (!ignoreCallingConv() && CI->getCallingConv() != llvm::CallingConv::C)
  72       return NULL;
  73
  74     return callOptimizer(CI->getCalledFunction(), CI, B);
  75   }
  76 };
  77
  78 //===----------------------------------------------------------------------===//
  79 // Helper Functions
  80 //===----------------------------------------------------------------------===//
  81
  82 /// isOnlyUsedInZeroEqualityComparison - Return true if it only matters that the
  83 /// value is equal or not-equal to zero.
  84 static bool isOnlyUsedInZeroEqualityComparison(Value *V) {
  85   for (Value::use_iterator UI = V->use_begin(), E = V->use_end();
  86        UI != E; ++UI) {
  87     if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI))
  88       if (IC->isEquality())
  89         if (Constant *C = dyn_cast<Constant>(IC->getOperand(1)))
  90           if (C->isNullValue())
  91             continue;
  92     // Unknown instruction.
  93     return false;
  94   }
  95   return true;
  96 }
  97
  98 /// isOnlyUsedInEqualityComparison - Return true if it is only used in equality
  99 /// comparisons with With.
 100 static bool isOnlyUsedInEqualityComparison(Value *V, Value *With) {
 101   for (Value::use_iterator UI = V->use_begin(), E = V->use_end();
 102        UI != E; ++UI) {
 103     if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI))
 104       if (IC->isEquality() && IC->getOperand(1) == With)
 105         continue;
 106     // Unknown instruction.
 107     return false;
 108   }
 109   return true;
 110 }
 111
 112 static bool callHasFloatingPointArgument(const CallInst *CI) {
 113   for (CallInst::const_op_iterator it = CI->op_begin(), e = CI->op_end();
 114        it != e; ++it) {
 115     if ((*it)->getType()->isFloatingPointTy())
 116       return true;
 117   }
 118   return false;
 119 }
 120
 121 /// \brief Check whether the overloaded unary floating point function
 122 /// corresponing to \a Ty is available.
 123 static bool hasUnaryFloatFn(const TargetLibraryInfo *TLI, Type *Ty,
 124                             LibFunc::Func DoubleFn, LibFunc::Func FloatFn,
 125                             LibFunc::Func LongDoubleFn) {
 126   switch (Ty->getTypeID()) {
 127   case Type::FloatTyID:
 128     return TLI->has(FloatFn);
 129   case Type::DoubleTyID:
 130     return TLI->has(DoubleFn);
 131   default:
 132     return TLI->has(LongDoubleFn);
 133   }
 134 }
 135
 136 //===----------------------------------------------------------------------===//
 137 // Fortified Library Call Optimizations
 138 //===----------------------------------------------------------------------===//
 139
 140 struct FortifiedLibCallOptimization : public LibCallOptimization {
 141 protected:
 142   virtual bool isFoldable(unsigned SizeCIOp, unsigned SizeArgOp,
 143                           bool isString) const = 0;
 144 };
 145
 146 struct InstFortifiedLibCallOptimization : public FortifiedLibCallOptimization {
 147   CallInst *CI;
 148
 149   bool isFoldable(unsigned SizeCIOp, unsigned SizeArgOp, bool isString) const {
 150     if (CI->getArgOperand(SizeCIOp) == CI->getArgOperand(SizeArgOp))
 151       return true;
 152     if (ConstantInt *SizeCI =
 153                            dyn_cast<ConstantInt>(CI->getArgOperand(SizeCIOp))) {
 154       if (SizeCI->isAllOnesValue())
 155         return true;
 156       if (isString) {
 157         uint64_t Len = GetStringLength(CI->getArgOperand(SizeArgOp));
 158         // If the length is 0 we don't know how long it is and so we can't
 159         // remove the check.
 160         if (Len == 0) return false;
 161         return SizeCI->getZExtValue() >= Len;
 162       }
 163       if (ConstantInt *Arg = dyn_cast<ConstantInt>(
 164                                                   CI->getArgOperand(SizeArgOp)))
 165         return SizeCI->getZExtValue() >= Arg->getZExtValue();
 166     }
 167     return false;
 168   }
 169 };
 170
 171 struct MemCpyChkOpt : public InstFortifiedLibCallOptimization {
 172   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 173     this->CI = CI;
 174     FunctionType *FT = Callee->getFunctionType();
 175     LLVMContext &Context = CI->getParent()->getContext();
 176
 177     // Check if this has the right signature.
 178     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 179         !FT->getParamType(0)->isPointerTy() ||
 180         !FT->getParamType(1)->isPointerTy() ||
 181         FT->getParamType(2) != TD->getIntPtrType(Context) ||
 182         FT->getParamType(3) != TD->getIntPtrType(Context))
 183       return 0;
 184
 185     if (isFoldable(3, 2, false)) {
 186       B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
 187                      CI->getArgOperand(2), 1);
 188       return CI->getArgOperand(0);
 189     }
 190     return 0;
 191   }
 192 };
 193
 194 struct MemMoveChkOpt : public InstFortifiedLibCallOptimization {
 195   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 196     this->CI = CI;
 197     FunctionType *FT = Callee->getFunctionType();
 198     LLVMContext &Context = CI->getParent()->getContext();
 199
 200     // Check if this has the right signature.
 201     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 202         !FT->getParamType(0)->isPointerTy() ||
 203         !FT->getParamType(1)->isPointerTy() ||
 204         FT->getParamType(2) != TD->getIntPtrType(Context) ||
 205         FT->getParamType(3) != TD->getIntPtrType(Context))
 206       return 0;
 207
 208     if (isFoldable(3, 2, false)) {
 209       B.CreateMemMove(CI->getArgOperand(0), CI->getArgOperand(1),
 210                       CI->getArgOperand(2), 1);
 211       return CI->getArgOperand(0);
 212     }
 213     return 0;
 214   }
 215 };
 216
 217 struct MemSetChkOpt : public InstFortifiedLibCallOptimization {
 218   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 219     this->CI = CI;
 220     FunctionType *FT = Callee->getFunctionType();
 221     LLVMContext &Context = CI->getParent()->getContext();
 222
 223     // Check if this has the right signature.
 224     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 225         !FT->getParamType(0)->isPointerTy() ||
 226         !FT->getParamType(1)->isIntegerTy() ||
 227         FT->getParamType(2) != TD->getIntPtrType(Context) ||
 228         FT->getParamType(3) != TD->getIntPtrType(Context))
 229       return 0;
 230
 231     if (isFoldable(3, 2, false)) {
 232       Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(),
 233                                    false);
 234       B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1);
 235       return CI->getArgOperand(0);
 236     }
 237     return 0;
 238   }
 239 };
 240
 241 struct StrCpyChkOpt : public InstFortifiedLibCallOptimization {
 242   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 243     this->CI = CI;
 244     StringRef Name = Callee->getName();
 245     FunctionType *FT = Callee->getFunctionType();
 246     LLVMContext &Context = CI->getParent()->getContext();
 247
 248     // Check if this has the right signature.
 249     if (FT->getNumParams() != 3 ||
 250         FT->getReturnType() != FT->getParamType(0) ||
 251         FT->getParamType(0) != FT->getParamType(1) ||
 252         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
 253         FT->getParamType(2) != TD->getIntPtrType(Context))
 254       return 0;
 255
 256     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 257     if (Dst == Src)      // __strcpy_chk(x,x)  -> x
 258       return Src;
 259
 260     // If a) we don't have any length information, or b) we know this will
 261     // fit then just lower to a plain strcpy. Otherwise we'll keep our
 262     // strcpy_chk call which may fail at runtime if the size is too long.
 263     // TODO: It might be nice to get a maximum length out of the possible
 264     // string lengths for varying.
 265     if (isFoldable(2, 1, true)) {
 266       Value *Ret = EmitStrCpy(Dst, Src, B, TD, TLI, Name.substr(2, 6));
 267       return Ret;
 268     } else {
 269       // Maybe we can stil fold __strcpy_chk to __memcpy_chk.
 270       uint64_t Len = GetStringLength(Src);
 271       if (Len == 0) return 0;
 272
 273       // This optimization require DataLayout.
 274       if (!TD) return 0;
 275
 276       Value *Ret =
 277         EmitMemCpyChk(Dst, Src,
 278                       ConstantInt::get(TD->getIntPtrType(Context), Len),
 279                       CI->getArgOperand(2), B, TD, TLI);
 280       return Ret;
 281     }
 282     return 0;
 283   }
 284 };
 285
 286 struct StpCpyChkOpt : public InstFortifiedLibCallOptimization {
 287   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 288     this->CI = CI;
 289     StringRef Name = Callee->getName();
 290     FunctionType *FT = Callee->getFunctionType();
 291     LLVMContext &Context = CI->getParent()->getContext();
 292
 293     // Check if this has the right signature.
 294     if (FT->getNumParams() != 3 ||
 295         FT->getReturnType() != FT->getParamType(0) ||
 296         FT->getParamType(0) != FT->getParamType(1) ||
 297         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
 298         FT->getParamType(2) != TD->getIntPtrType(FT->getParamType(0)))
 299       return 0;
 300
 301     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 302     if (Dst == Src) {  // stpcpy(x,x)  -> x+strlen(x)
 303       Value *StrLen = EmitStrLen(Src, B, TD, TLI);
 304       return StrLen ? B.CreateInBoundsGEP(Dst, StrLen) : 0;
 305     }
 306
 307     // If a) we don't have any length information, or b) we know this will
 308     // fit then just lower to a plain stpcpy. Otherwise we'll keep our
 309     // stpcpy_chk call which may fail at runtime if the size is too long.
 310     // TODO: It might be nice to get a maximum length out of the possible
 311     // string lengths for varying.
 312     if (isFoldable(2, 1, true)) {
 313       Value *Ret = EmitStrCpy(Dst, Src, B, TD, TLI, Name.substr(2, 6));
 314       return Ret;
 315     } else {
 316       // Maybe we can stil fold __stpcpy_chk to __memcpy_chk.
 317       uint64_t Len = GetStringLength(Src);
 318       if (Len == 0) return 0;
 319
 320       // This optimization require DataLayout.
 321       if (!TD) return 0;
 322
 323       Type *PT = FT->getParamType(0);
 324       Value *LenV = ConstantInt::get(TD->getIntPtrType(PT), Len);
 325       Value *DstEnd = B.CreateGEP(Dst,
 326                                   ConstantInt::get(TD->getIntPtrType(PT),
 327                                                    Len - 1));
 328       if (!EmitMemCpyChk(Dst, Src, LenV, CI->getArgOperand(2), B, TD, TLI))
 329         return 0;
 330       return DstEnd;
 331     }
 332     return 0;
 333   }
 334 };
 335
 336 struct StrNCpyChkOpt : public InstFortifiedLibCallOptimization {
 337   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 338     this->CI = CI;
 339     StringRef Name = Callee->getName();
 340     FunctionType *FT = Callee->getFunctionType();
 341     LLVMContext &Context = CI->getParent()->getContext();
 342
 343     // Check if this has the right signature.
 344     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 345         FT->getParamType(0) != FT->getParamType(1) ||
 346         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
 347         !FT->getParamType(2)->isIntegerTy() ||
 348         FT->getParamType(3) != TD->getIntPtrType(Context))
 349       return 0;
 350
 351     if (isFoldable(3, 2, false)) {
 352       Value *Ret = EmitStrNCpy(CI->getArgOperand(0), CI->getArgOperand(1),
 353                                CI->getArgOperand(2), B, TD, TLI,
 354                                Name.substr(2, 7));
 355       return Ret;
 356     }
 357     return 0;
 358   }
 359 };
 360
 361 //===----------------------------------------------------------------------===//
 362 // String and Memory Library Call Optimizations
 363 //===----------------------------------------------------------------------===//
 364
 365 struct StrCatOpt : public LibCallOptimization {
 366   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 367     // Verify the "strcat" function prototype.
 368     FunctionType *FT = Callee->getFunctionType();
 369     if (FT->getNumParams() != 2 ||
 370         FT->getReturnType() != B.getInt8PtrTy() ||
 371         FT->getParamType(0) != FT->getReturnType() ||
 372         FT->getParamType(1) != FT->getReturnType())
 373       return 0;
 374
 375     // Extract some information from the instruction
 376     Value *Dst = CI->getArgOperand(0);
 377     Value *Src = CI->getArgOperand(1);
 378
 379     // See if we can get the length of the input string.
 380     uint64_t Len = GetStringLength(Src);
 381     if (Len == 0) return 0;
 382     --Len;  // Unbias length.
 383
 384     // Handle the simple, do-nothing case: strcat(x, "") -> x
 385     if (Len == 0)
 386       return Dst;
 387
 388     // These optimizations require DataLayout.
 389     if (!TD) return 0;
 390
 391     return emitStrLenMemCpy(Src, Dst, Len, B);
 392   }
 393
 394   Value *emitStrLenMemCpy(Value *Src, Value *Dst, uint64_t Len,
 395                           IRBuilder<> &B) {
 396     // We need to find the end of the destination string.  That's where the
 397     // memory is to be moved to. We just generate a call to strlen.
 398     Value *DstLen = EmitStrLen(Dst, B, TD, TLI);
 399     if (!DstLen)
 400       return 0;
 401
 402     // Now that we have the destination's length, we must index into the
 403     // destination's pointer to get the actual memcpy destination (end of
 404     // the string .. we're concatenating).
 405     Value *CpyDst = B.CreateGEP(Dst, DstLen, "endptr");
 406
 407     // We have enough information to now generate the memcpy call to do the
 408     // concatenation for us.  Make a memcpy to copy the nul byte with align = 1.
 409     B.CreateMemCpy(CpyDst, Src,
 410                    ConstantInt::get(TD->getIntPtrType(*Context), Len + 1), 1);
 411     return Dst;
 412   }
 413 };
 414
 415 struct StrNCatOpt : public StrCatOpt {
 416   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 417     // Verify the "strncat" function prototype.
 418     FunctionType *FT = Callee->getFunctionType();
 419     if (FT->getNumParams() != 3 ||
 420         FT->getReturnType() != B.getInt8PtrTy() ||
 421         FT->getParamType(0) != FT->getReturnType() ||
 422         FT->getParamType(1) != FT->getReturnType() ||
 423         !FT->getParamType(2)->isIntegerTy())
 424       return 0;
 425
 426     // Extract some information from the instruction
 427     Value *Dst = CI->getArgOperand(0);
 428     Value *Src = CI->getArgOperand(1);
 429     uint64_t Len;
 430
 431     // We don't do anything if length is not constant
 432     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
 433       Len = LengthArg->getZExtValue();
 434     else
 435       return 0;
 436
 437     // See if we can get the length of the input string.
 438     uint64_t SrcLen = GetStringLength(Src);
 439     if (SrcLen == 0) return 0;
 440     --SrcLen;  // Unbias length.
 441
 442     // Handle the simple, do-nothing cases:
 443     // strncat(x, "", c) -> x
 444     // strncat(x,  c, 0) -> x
 445     if (SrcLen == 0 || Len == 0) return Dst;
 446
 447     // These optimizations require DataLayout.
 448     if (!TD) return 0;
 449
 450     // We don't optimize this case
 451     if (Len < SrcLen) return 0;
 452
 453     // strncat(x, s, c) -> strcat(x, s)
 454     // s is constant so the strcat can be optimized further
 455     return emitStrLenMemCpy(Src, Dst, SrcLen, B);
 456   }
 457 };
 458
 459 struct StrChrOpt : public LibCallOptimization {
 460   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 461     // Verify the "strchr" function prototype.
 462     FunctionType *FT = Callee->getFunctionType();
 463     if (FT->getNumParams() != 2 ||
 464         FT->getReturnType() != B.getInt8PtrTy() ||
 465         FT->getParamType(0) != FT->getReturnType() ||
 466         !FT->getParamType(1)->isIntegerTy(32))
 467       return 0;
 468
 469     Value *SrcStr = CI->getArgOperand(0);
 470
 471     // If the second operand is non-constant, see if we can compute the length
 472     // of the input string and turn this into memchr.
 473     ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
 474     if (CharC == 0) {
 475       // These optimizations require DataLayout.
 476       if (!TD) return 0;
 477
 478       uint64_t Len = GetStringLength(SrcStr);
 479       if (Len == 0 || !FT->getParamType(1)->isIntegerTy(32))// memchr needs i32.
 480         return 0;
 481
 482       return EmitMemChr(SrcStr, CI->getArgOperand(1), // include nul.
 483                         ConstantInt::get(TD->getIntPtrType(*Context), Len),
 484                         B, TD, TLI);
 485     }
 486
 487     // Otherwise, the character is a constant, see if the first argument is
 488     // a string literal.  If so, we can constant fold.
 489     StringRef Str;
 490     if (!getConstantStringInfo(SrcStr, Str))
 491       return 0;
 492
 493     // Compute the offset, make sure to handle the case when we're searching for
 494     // zero (a weird way to spell strlen).
 495     size_t I = (0xFF & CharC->getSExtValue()) == 0 ?
 496         Str.size() : Str.find(CharC->getSExtValue());
 497     if (I == StringRef::npos) // Didn't find the char.  strchr returns null.
 498       return Constant::getNullValue(CI->getType());
 499
 500     // strchr(s+n,c)  -> gep(s+n+i,c)
 501     return B.CreateGEP(SrcStr, B.getInt64(I), "strchr");
 502   }
 503 };
 504
 505 struct StrRChrOpt : public LibCallOptimization {
 506   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 507     // Verify the "strrchr" function prototype.
 508     FunctionType *FT = Callee->getFunctionType();
 509     if (FT->getNumParams() != 2 ||
 510         FT->getReturnType() != B.getInt8PtrTy() ||
 511         FT->getParamType(0) != FT->getReturnType() ||
 512         !FT->getParamType(1)->isIntegerTy(32))
 513       return 0;
 514
 515     Value *SrcStr = CI->getArgOperand(0);
 516     ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
 517
 518     // Cannot fold anything if we're not looking for a constant.
 519     if (!CharC)
 520       return 0;
 521
 522     StringRef Str;
 523     if (!getConstantStringInfo(SrcStr, Str)) {
 524       // strrchr(s, 0) -> strchr(s, 0)
 525       if (TD && CharC->isZero())
 526         return EmitStrChr(SrcStr, '\0', B, TD, TLI);
 527       return 0;
 528     }
 529
 530     // Compute the offset.
 531     size_t I = (0xFF & CharC->getSExtValue()) == 0 ?
 532         Str.size() : Str.rfind(CharC->getSExtValue());
 533     if (I == StringRef::npos) // Didn't find the char. Return null.
 534       return Constant::getNullValue(CI->getType());
 535
 536     // strrchr(s+n,c) -> gep(s+n+i,c)
 537     return B.CreateGEP(SrcStr, B.getInt64(I), "strrchr");
 538   }
 539 };
 540
 541 struct StrCmpOpt : public LibCallOptimization {
 542   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 543     // Verify the "strcmp" function prototype.
 544     FunctionType *FT = Callee->getFunctionType();
 545     if (FT->getNumParams() != 2 ||
 546         !FT->getReturnType()->isIntegerTy(32) ||
 547         FT->getParamType(0) != FT->getParamType(1) ||
 548         FT->getParamType(0) != B.getInt8PtrTy())
 549       return 0;
 550
 551     Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
 552     if (Str1P == Str2P)      // strcmp(x,x)  -> 0
 553       return ConstantInt::get(CI->getType(), 0);
 554
 555     StringRef Str1, Str2;
 556     bool HasStr1 = getConstantStringInfo(Str1P, Str1);
 557     bool HasStr2 = getConstantStringInfo(Str2P, Str2);
 558
 559     // strcmp(x, y)  -> cnst  (if both x and y are constant strings)
 560     if (HasStr1 && HasStr2)
 561       return ConstantInt::get(CI->getType(), Str1.compare(Str2));
 562
 563     if (HasStr1 && Str1.empty()) // strcmp("", x) -> -*x
 564       return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"),
 565                                       CI->getType()));
 566
 567     if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x
 568       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
 569
 570     // strcmp(P, "x") -> memcmp(P, "x", 2)
 571     uint64_t Len1 = GetStringLength(Str1P);
 572     uint64_t Len2 = GetStringLength(Str2P);
 573     if (Len1 && Len2) {
 574       // These optimizations require DataLayout.
 575       if (!TD) return 0;
 576
 577       return EmitMemCmp(Str1P, Str2P,
 578                         ConstantInt::get(TD->getIntPtrType(*Context),
 579                         std::min(Len1, Len2)), B, TD, TLI);
 580     }
 581
 582     return 0;
 583   }
 584 };
 585
 586 struct StrNCmpOpt : public LibCallOptimization {
 587   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 588     // Verify the "strncmp" function prototype.
 589     FunctionType *FT = Callee->getFunctionType();
 590     if (FT->getNumParams() != 3 ||
 591         !FT->getReturnType()->isIntegerTy(32) ||
 592         FT->getParamType(0) != FT->getParamType(1) ||
 593         FT->getParamType(0) != B.getInt8PtrTy() ||
 594         !FT->getParamType(2)->isIntegerTy())
 595       return 0;
 596
 597     Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
 598     if (Str1P == Str2P)      // strncmp(x,x,n)  -> 0
 599       return ConstantInt::get(CI->getType(), 0);
 600
 601     // Get the length argument if it is constant.
 602     uint64_t Length;
 603     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
 604       Length = LengthArg->getZExtValue();
 605     else
 606       return 0;
 607
 608     if (Length == 0) // strncmp(x,y,0)   -> 0
 609       return ConstantInt::get(CI->getType(), 0);
 610
 611     if (TD && Length == 1) // strncmp(x,y,1) -> memcmp(x,y,1)
 612       return EmitMemCmp(Str1P, Str2P, CI->getArgOperand(2), B, TD, TLI);
 613
 614     StringRef Str1, Str2;
 615     bool HasStr1 = getConstantStringInfo(Str1P, Str1);
 616     bool HasStr2 = getConstantStringInfo(Str2P, Str2);
 617
 618     // strncmp(x, y)  -> cnst  (if both x and y are constant strings)
 619     if (HasStr1 && HasStr2) {
 620       StringRef SubStr1 = Str1.substr(0, Length);
 621       StringRef SubStr2 = Str2.substr(0, Length);
 622       return ConstantInt::get(CI->getType(), SubStr1.compare(SubStr2));
 623     }
 624
 625     if (HasStr1 && Str1.empty())  // strncmp("", x, n) -> -*x
 626       return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"),
 627                                       CI->getType()));
 628
 629     if (HasStr2 && Str2.empty())  // strncmp(x, "", n) -> *x
 630       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
 631
 632     return 0;
 633   }
 634 };
 635
 636 struct StrCpyOpt : public LibCallOptimization {
 637   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 638     // Verify the "strcpy" function prototype.
 639     FunctionType *FT = Callee->getFunctionType();
 640     if (FT->getNumParams() != 2 ||
 641         FT->getReturnType() != FT->getParamType(0) ||
 642         FT->getParamType(0) != FT->getParamType(1) ||
 643         FT->getParamType(0) != B.getInt8PtrTy())
 644       return 0;
 645
 646     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 647     if (Dst == Src)      // strcpy(x,x)  -> x
 648       return Src;
 649
 650     // These optimizations require DataLayout.
 651     if (!TD) return 0;
 652
 653     // See if we can get the length of the input string.
 654     uint64_t Len = GetStringLength(Src);
 655     if (Len == 0) return 0;
 656
 657     // We have enough information to now generate the memcpy call to do the
 658     // copy for us.  Make a memcpy to copy the nul byte with align = 1.
 659     B.CreateMemCpy(Dst, Src,
 660                    ConstantInt::get(TD->getIntPtrType(*Context), Len), 1);
 661     return Dst;
 662   }
 663 };
 664
 665 struct StpCpyOpt: public LibCallOptimization {
 666   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 667     // Verify the "stpcpy" function prototype.
 668     FunctionType *FT = Callee->getFunctionType();
 669     if (FT->getNumParams() != 2 ||
 670         FT->getReturnType() != FT->getParamType(0) ||
 671         FT->getParamType(0) != FT->getParamType(1) ||
 672         FT->getParamType(0) != B.getInt8PtrTy())
 673       return 0;
 674
 675     // These optimizations require DataLayout.
 676     if (!TD) return 0;
 677
 678     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 679     if (Dst == Src) {  // stpcpy(x,x)  -> x+strlen(x)
 680       Value *StrLen = EmitStrLen(Src, B, TD, TLI);
 681       return StrLen ? B.CreateInBoundsGEP(Dst, StrLen) : 0;
 682     }
 683
 684     // See if we can get the length of the input string.
 685     uint64_t Len = GetStringLength(Src);
 686     if (Len == 0) return 0;
 687
 688     Type *PT = FT->getParamType(0);
 689     Value *LenV = ConstantInt::get(TD->getIntPtrType(PT), Len);
 690     Value *DstEnd = B.CreateGEP(Dst,
 691                                 ConstantInt::get(TD->getIntPtrType(PT),
 692                                                  Len - 1));
 693
 694     // We have enough information to now generate the memcpy call to do the
 695     // copy for us.  Make a memcpy to copy the nul byte with align = 1.
 696     B.CreateMemCpy(Dst, Src, LenV, 1);
 697     return DstEnd;
 698   }
 699 };
 700
 701 struct StrNCpyOpt : public LibCallOptimization {
 702   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 703     FunctionType *FT = Callee->getFunctionType();
 704     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 705         FT->getParamType(0) != FT->getParamType(1) ||
 706         FT->getParamType(0) != B.getInt8PtrTy() ||
 707         !FT->getParamType(2)->isIntegerTy())
 708       return 0;
 709
 710     Value *Dst = CI->getArgOperand(0);
 711     Value *Src = CI->getArgOperand(1);
 712     Value *LenOp = CI->getArgOperand(2);
 713
 714     // See if we can get the length of the input string.
 715     uint64_t SrcLen = GetStringLength(Src);
 716     if (SrcLen == 0) return 0;
 717     --SrcLen;
 718
 719     if (SrcLen == 0) {
 720       // strncpy(x, "", y) -> memset(x, '\0', y, 1)
 721       B.CreateMemSet(Dst, B.getInt8('\0'), LenOp, 1);
 722       return Dst;
 723     }
 724
 725     uint64_t Len;
 726     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(LenOp))
 727       Len = LengthArg->getZExtValue();
 728     else
 729       return 0;
 730
 731     if (Len == 0) return Dst; // strncpy(x, y, 0) -> x
 732
 733     // These optimizations require DataLayout.
 734     if (!TD) return 0;
 735
 736     // Let strncpy handle the zero padding
 737     if (Len > SrcLen+1) return 0;
 738
 739     Type *PT = FT->getParamType(0);
 740     // strncpy(x, s, c) -> memcpy(x, s, c, 1) [s and c are constant]
 741     B.CreateMemCpy(Dst, Src,
 742                    ConstantInt::get(TD->getIntPtrType(PT), Len), 1);
 743
 744     return Dst;
 745   }
 746 };
 747
 748 struct StrLenOpt : public LibCallOptimization {
 749   virtual bool ignoreCallingConv() { return true; }
 750   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 751     FunctionType *FT = Callee->getFunctionType();
 752     if (FT->getNumParams() != 1 ||
 753         FT->getParamType(0) != B.getInt8PtrTy() ||
 754         !FT->getReturnType()->isIntegerTy())
 755       return 0;
 756
 757     Value *Src = CI->getArgOperand(0);
 758
 759     // Constant folding: strlen("xyz") -> 3
 760     if (uint64_t Len = GetStringLength(Src))
 761       return ConstantInt::get(CI->getType(), Len-1);
 762
 763     // strlen(x) != 0 --> *x != 0
 764     // strlen(x) == 0 --> *x == 0
 765     if (isOnlyUsedInZeroEqualityComparison(CI))
 766       return B.CreateZExt(B.CreateLoad(Src, "strlenfirst"), CI->getType());
 767     return 0;
 768   }
 769 };
 770
 771 struct StrPBrkOpt : public LibCallOptimization {
 772   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 773     FunctionType *FT = Callee->getFunctionType();
 774     if (FT->getNumParams() != 2 ||
 775         FT->getParamType(0) != B.getInt8PtrTy() ||
 776         FT->getParamType(1) != FT->getParamType(0) ||
 777         FT->getReturnType() != FT->getParamType(0))
 778       return 0;
 779
 780     StringRef S1, S2;
 781     bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
 782     bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
 783
 784     // strpbrk(s, "") -> NULL
 785     // strpbrk("", s) -> NULL
 786     if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))
 787       return Constant::getNullValue(CI->getType());
 788
 789     // Constant folding.
 790     if (HasS1 && HasS2) {
 791       size_t I = S1.find_first_of(S2);
 792       if (I == StringRef::npos) // No match.
 793         return Constant::getNullValue(CI->getType());
 794
 795       return B.CreateGEP(CI->getArgOperand(0), B.getInt64(I), "strpbrk");
 796     }
 797
 798     // strpbrk(s, "a") -> strchr(s, 'a')
 799     if (TD && HasS2 && S2.size() == 1)
 800       return EmitStrChr(CI->getArgOperand(0), S2[0], B, TD, TLI);
 801
 802     return 0;
 803   }
 804 };
 805
 806 struct StrToOpt : public LibCallOptimization {
 807   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 808     FunctionType *FT = Callee->getFunctionType();
 809     if ((FT->getNumParams() != 2 && FT->getNumParams() != 3) ||
 810         !FT->getParamType(0)->isPointerTy() ||
 811         !FT->getParamType(1)->isPointerTy())
 812       return 0;
 813
 814     Value *EndPtr = CI->getArgOperand(1);
 815     if (isa<ConstantPointerNull>(EndPtr)) {
 816       // With a null EndPtr, this function won't capture the main argument.
 817       // It would be readonly too, except that it still may write to errno.
 818       CI->addAttribute(1, Attribute::NoCapture);
 819     }
 820
 821     return 0;
 822   }
 823 };
 824
 825 struct StrSpnOpt : public LibCallOptimization {
 826   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 827     FunctionType *FT = Callee->getFunctionType();
 828     if (FT->getNumParams() != 2 ||
 829         FT->getParamType(0) != B.getInt8PtrTy() ||
 830         FT->getParamType(1) != FT->getParamType(0) ||
 831         !FT->getReturnType()->isIntegerTy())
 832       return 0;
 833
 834     StringRef S1, S2;
 835     bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
 836     bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
 837
 838     // strspn(s, "") -> 0
 839     // strspn("", s) -> 0
 840     if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))
 841       return Constant::getNullValue(CI->getType());
 842
 843     // Constant folding.
 844     if (HasS1 && HasS2) {
 845       size_t Pos = S1.find_first_not_of(S2);
 846       if (Pos == StringRef::npos) Pos = S1.size();
 847       return ConstantInt::get(CI->getType(), Pos);
 848     }
 849
 850     return 0;
 851   }
 852 };
 853
 854 struct StrCSpnOpt : public LibCallOptimization {
 855   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 856     FunctionType *FT = Callee->getFunctionType();
 857     if (FT->getNumParams() != 2 ||
 858         FT->getParamType(0) != B.getInt8PtrTy() ||
 859         FT->getParamType(1) != FT->getParamType(0) ||
 860         !FT->getReturnType()->isIntegerTy())
 861       return 0;
 862
 863     StringRef S1, S2;
 864     bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
 865     bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
 866
 867     // strcspn("", s) -> 0
 868     if (HasS1 && S1.empty())
 869       return Constant::getNullValue(CI->getType());
 870
 871     // Constant folding.
 872     if (HasS1 && HasS2) {
 873       size_t Pos = S1.find_first_of(S2);
 874       if (Pos == StringRef::npos) Pos = S1.size();
 875       return ConstantInt::get(CI->getType(), Pos);
 876     }
 877
 878     // strcspn(s, "") -> strlen(s)
 879     if (TD && HasS2 && S2.empty())
 880       return EmitStrLen(CI->getArgOperand(0), B, TD, TLI);
 881
 882     return 0;
 883   }
 884 };
 885
 886 struct StrStrOpt : public LibCallOptimization {
 887   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 888     FunctionType *FT = Callee->getFunctionType();
 889     if (FT->getNumParams() != 2 ||
 890         !FT->getParamType(0)->isPointerTy() ||
 891         !FT->getParamType(1)->isPointerTy() ||
 892         !FT->getReturnType()->isPointerTy())
 893       return 0;
 894
 895     // fold strstr(x, x) -> x.
 896     if (CI->getArgOperand(0) == CI->getArgOperand(1))
 897       return B.CreateBitCast(CI->getArgOperand(0), CI->getType());
 898
 899     // fold strstr(a, b) == a -> strncmp(a, b, strlen(b)) == 0
 900     if (TD && isOnlyUsedInEqualityComparison(CI, CI->getArgOperand(0))) {
 901       Value *StrLen = EmitStrLen(CI->getArgOperand(1), B, TD, TLI);
 902       if (!StrLen)
 903         return 0;
 904       Value *StrNCmp = EmitStrNCmp(CI->getArgOperand(0), CI->getArgOperand(1),
 905                                    StrLen, B, TD, TLI);
 906       if (!StrNCmp)
 907         return 0;
 908       for (Value::use_iterator UI = CI->use_begin(), UE = CI->use_end();
 909            UI != UE; ) {
 910         ICmpInst *Old = cast<ICmpInst>(*UI++);
 911         Value *Cmp = B.CreateICmp(Old->getPredicate(), StrNCmp,
 912                                   ConstantInt::getNullValue(StrNCmp->getType()),
 913                                   "cmp");
 914         LCS->replaceAllUsesWith(Old, Cmp);
 915       }
 916       return CI;
 917     }
 918
 919     // See if either input string is a constant string.
 920     StringRef SearchStr, ToFindStr;
 921     bool HasStr1 = getConstantStringInfo(CI->getArgOperand(0), SearchStr);
 922     bool HasStr2 = getConstantStringInfo(CI->getArgOperand(1), ToFindStr);
 923
 924     // fold strstr(x, "") -> x.
 925     if (HasStr2 && ToFindStr.empty())
 926       return B.CreateBitCast(CI->getArgOperand(0), CI->getType());
 927
 928     // If both strings are known, constant fold it.
 929     if (HasStr1 && HasStr2) {
 930       size_t Offset = SearchStr.find(ToFindStr);
 931
 932       if (Offset == StringRef::npos) // strstr("foo", "bar") -> null
 933         return Constant::getNullValue(CI->getType());
 934
 935       // strstr("abcd", "bc") -> gep((char*)"abcd", 1)
 936       Value *Result = CastToCStr(CI->getArgOperand(0), B);
 937       Result = B.CreateConstInBoundsGEP1_64(Result, Offset, "strstr");
 938       return B.CreateBitCast(Result, CI->getType());
 939     }
 940
 941     // fold strstr(x, "y") -> strchr(x, 'y').
 942     if (HasStr2 && ToFindStr.size() == 1) {
 943       Value *StrChr= EmitStrChr(CI->getArgOperand(0), ToFindStr[0], B, TD, TLI);
 944       return StrChr ? B.CreateBitCast(StrChr, CI->getType()) : 0;
 945     }
 946     return 0;
 947   }
 948 };
 949
 950 struct MemCmpOpt : public LibCallOptimization {
 951   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 952     FunctionType *FT = Callee->getFunctionType();
 953     if (FT->getNumParams() != 3 || !FT->getParamType(0)->isPointerTy() ||
 954         !FT->getParamType(1)->isPointerTy() ||
 955         !FT->getReturnType()->isIntegerTy(32))
 956       return 0;
 957
 958     Value *LHS = CI->getArgOperand(0), *RHS = CI->getArgOperand(1);
 959
 960     if (LHS == RHS)  // memcmp(s,s,x) -> 0
 961       return Constant::getNullValue(CI->getType());
 962
 963     // Make sure we have a constant length.
 964     ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getArgOperand(2));
 965     if (!LenC) return 0;
 966     uint64_t Len = LenC->getZExtValue();
 967
 968     if (Len == 0) // memcmp(s1,s2,0) -> 0
 969       return Constant::getNullValue(CI->getType());
 970
 971     // memcmp(S1,S2,1) -> *(unsigned char*)LHS - *(unsigned char*)RHS
 972     if (Len == 1) {
 973       Value *LHSV = B.CreateZExt(B.CreateLoad(CastToCStr(LHS, B), "lhsc"),
 974                                  CI->getType(), "lhsv");
 975       Value *RHSV = B.CreateZExt(B.CreateLoad(CastToCStr(RHS, B), "rhsc"),
 976                                  CI->getType(), "rhsv");
 977       return B.CreateSub(LHSV, RHSV, "chardiff");
 978     }
 979
 980     // Constant folding: memcmp(x, y, l) -> cnst (all arguments are constant)
 981     StringRef LHSStr, RHSStr;
 982     if (getConstantStringInfo(LHS, LHSStr) &&
 983         getConstantStringInfo(RHS, RHSStr)) {
 984       // Make sure we're not reading out-of-bounds memory.
 985       if (Len > LHSStr.size() || Len > RHSStr.size())
 986         return 0;
 987       // Fold the memcmp and normalize the result.  This way we get consistent
 988       // results across multiple platforms.
 989       uint64_t Ret = 0;
 990       int Cmp = memcmp(LHSStr.data(), RHSStr.data(), Len);
 991       if (Cmp < 0)
 992         Ret = -1;
 993       else if (Cmp > 0)
 994         Ret = 1;
 995       return ConstantInt::get(CI->getType(), Ret);
 996     }
 997
 998     return 0;
 999   }
1000 };
1001
1002 struct MemCpyOpt : public LibCallOptimization {
1003   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1004     // These optimizations require DataLayout.
1005     if (!TD) return 0;
1006
1007     FunctionType *FT = Callee->getFunctionType();
1008     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
1009         !FT->getParamType(0)->isPointerTy() ||
1010         !FT->getParamType(1)->isPointerTy() ||
1011         FT->getParamType(2) != TD->getIntPtrType(*Context))
1012       return 0;
1013
1014     // memcpy(x, y, n) -> llvm.memcpy(x, y, n, 1)
1015     B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
1016                    CI->getArgOperand(2), 1);
1017     return CI->getArgOperand(0);
1018   }
1019 };
1020
1021 struct MemMoveOpt : public LibCallOptimization {
1022   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1023     // These optimizations require DataLayout.
1024     if (!TD) return 0;
1025
1026     FunctionType *FT = Callee->getFunctionType();
1027     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
1028         !FT->getParamType(0)->isPointerTy() ||
1029         !FT->getParamType(1)->isPointerTy() ||
1030         FT->getParamType(2) != TD->getIntPtrType(*Context))
1031       return 0;
1032
1033     // memmove(x, y, n) -> llvm.memmove(x, y, n, 1)
1034     B.CreateMemMove(CI->getArgOperand(0), CI->getArgOperand(1),
1035                     CI->getArgOperand(2), 1);
1036     return CI->getArgOperand(0);
1037   }
1038 };
1039
1040 struct MemSetOpt : public LibCallOptimization {
1041   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1042     // These optimizations require DataLayout.
1043     if (!TD) return 0;
1044
1045     FunctionType *FT = Callee->getFunctionType();
1046     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
1047         !FT->getParamType(0)->isPointerTy() ||
1048         !FT->getParamType(1)->isIntegerTy() ||
1049         FT->getParamType(2) != TD->getIntPtrType(*Context))
1050       return 0;
1051
1052     // memset(p, v, n) -> llvm.memset(p, v, n, 1)
1053     Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(), false);
1054     B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1);
1055     return CI->getArgOperand(0);
1056   }
1057 };
1058
1059 //===----------------------------------------------------------------------===//
1060 // Math Library Optimizations
1061 //===----------------------------------------------------------------------===//
1062
1063 //===----------------------------------------------------------------------===//
1064 // Double -> Float Shrinking Optimizations for Unary Functions like 'floor'
1065
1066 struct UnaryDoubleFPOpt : public LibCallOptimization {
1067   bool CheckRetType;
1068   UnaryDoubleFPOpt(bool CheckReturnType): CheckRetType(CheckReturnType) {}
1069   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1070     FunctionType *FT = Callee->getFunctionType();
1071     if (FT->getNumParams() != 1 || !FT->getReturnType()->isDoubleTy() ||
1072         !FT->getParamType(0)->isDoubleTy())
1073       return 0;
1074
1075     if (CheckRetType) {
1076       // Check if all the uses for function like 'sin' are converted to float.
1077       for (Value::use_iterator UseI = CI->use_begin(); UseI != CI->use_end();
1078           ++UseI) {
1079         FPTruncInst *Cast = dyn_cast<FPTruncInst>(*UseI);
1080         if (Cast == 0 || !Cast->getType()->isFloatTy())
1081           return 0;
1082       }
1083     }
1084
1085     // If this is something like 'floor((double)floatval)', convert to floorf.
1086     FPExtInst *Cast = dyn_cast<FPExtInst>(CI->getArgOperand(0));
1087     if (Cast == 0 || !Cast->getOperand(0)->getType()->isFloatTy())
1088       return 0;
1089
1090     // floor((double)floatval) -> (double)floorf(floatval)
1091     Value *V = Cast->getOperand(0);
1092     V = EmitUnaryFloatFnCall(V, Callee->getName(), B, Callee->getAttributes());
1093     return B.CreateFPExt(V, B.getDoubleTy());
1094   }
1095 };
1096
1097 struct UnsafeFPLibCallOptimization : public LibCallOptimization {
1098   bool UnsafeFPShrink;
1099   UnsafeFPLibCallOptimization(bool UnsafeFPShrink) {
1100     this->UnsafeFPShrink = UnsafeFPShrink;
1101   }
1102 };
1103
1104 struct CosOpt : public UnsafeFPLibCallOptimization {
1105   CosOpt(bool UnsafeFPShrink) : UnsafeFPLibCallOptimization(UnsafeFPShrink) {}
1106   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1107     Value *Ret = NULL;
1108     if (UnsafeFPShrink && Callee->getName() == "cos" &&
1109         TLI->has(LibFunc::cosf)) {
1110       UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
1111       Ret = UnsafeUnaryDoubleFP.callOptimizer(Callee, CI, B);
1112     }
1113
1114     FunctionType *FT = Callee->getFunctionType();
1115     // Just make sure this has 1 argument of FP type, which matches the
1116     // result type.
1117     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1118         !FT->getParamType(0)->isFloatingPointTy())
1119       return Ret;
1120
1121     // cos(-x) -> cos(x)
1122     Value *Op1 = CI->getArgOperand(0);
1123     if (BinaryOperator::isFNeg(Op1)) {
1124       BinaryOperator *BinExpr = cast<BinaryOperator>(Op1);
1125       return B.CreateCall(Callee, BinExpr->getOperand(1), "cos");
1126     }
1127     return Ret;
1128   }
1129 };
1130
1131 struct PowOpt : public UnsafeFPLibCallOptimization {
1132   PowOpt(bool UnsafeFPShrink) : UnsafeFPLibCallOptimization(UnsafeFPShrink) {}
1133   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1134     Value *Ret = NULL;
1135     if (UnsafeFPShrink && Callee->getName() == "pow" &&
1136         TLI->has(LibFunc::powf)) {
1137       UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
1138       Ret = UnsafeUnaryDoubleFP.callOptimizer(Callee, CI, B);
1139     }
1140
1141     FunctionType *FT = Callee->getFunctionType();
1142     // Just make sure this has 2 arguments of the same FP type, which match the
1143     // result type.
1144     if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) ||
1145         FT->getParamType(0) != FT->getParamType(1) ||
1146         !FT->getParamType(0)->isFloatingPointTy())
1147       return Ret;
1148
1149     Value *Op1 = CI->getArgOperand(0), *Op2 = CI->getArgOperand(1);
1150     if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) {
1151       // pow(1.0, x) -> 1.0
1152       if (Op1C->isExactlyValue(1.0))
1153         return Op1C;
1154       // pow(2.0, x) -> exp2(x)
1155       if (Op1C->isExactlyValue(2.0) &&
1156           hasUnaryFloatFn(TLI, Op1->getType(), LibFunc::exp2, LibFunc::exp2f,
1157                           LibFunc::exp2l))
1158         return EmitUnaryFloatFnCall(Op2, "exp2", B, Callee->getAttributes());
1159     }
1160
1161     ConstantFP *Op2C = dyn_cast<ConstantFP>(Op2);
1162     if (Op2C == 0) return Ret;
1163
1164     if (Op2C->getValueAPF().isZero())  // pow(x, 0.0) -> 1.0
1165       return ConstantFP::get(CI->getType(), 1.0);
1166
1167     if (Op2C->isExactlyValue(0.5) &&
1168         hasUnaryFloatFn(TLI, Op2->getType(), LibFunc::sqrt, LibFunc::sqrtf,
1169                         LibFunc::sqrtl) &&
1170         hasUnaryFloatFn(TLI, Op2->getType(), LibFunc::fabs, LibFunc::fabsf,
1171                         LibFunc::fabsl)) {
1172       // Expand pow(x, 0.5) to (x == -infinity ? +infinity : fabs(sqrt(x))).
1173       // This is faster than calling pow, and still handles negative zero
1174       // and negative infinity correctly.
1175       // TODO: In fast-math mode, this could be just sqrt(x).
1176       // TODO: In finite-only mode, this could be just fabs(sqrt(x)).
1177       Value *Inf = ConstantFP::getInfinity(CI->getType());
1178       Value *NegInf = ConstantFP::getInfinity(CI->getType(), true);
1179       Value *Sqrt = EmitUnaryFloatFnCall(Op1, "sqrt", B,
1180                                          Callee->getAttributes());
1181       Value *FAbs = EmitUnaryFloatFnCall(Sqrt, "fabs", B,
1182                                          Callee->getAttributes());
1183       Value *FCmp = B.CreateFCmpOEQ(Op1, NegInf);
1184       Value *Sel = B.CreateSelect(FCmp, Inf, FAbs);
1185       return Sel;
1186     }
1187
1188     if (Op2C->isExactlyValue(1.0))  // pow(x, 1.0) -> x
1189       return Op1;
1190     if (Op2C->isExactlyValue(2.0))  // pow(x, 2.0) -> x*x
1191       return B.CreateFMul(Op1, Op1, "pow2");
1192     if (Op2C->isExactlyValue(-1.0)) // pow(x, -1.0) -> 1.0/x
1193       return B.CreateFDiv(ConstantFP::get(CI->getType(), 1.0),
1194                           Op1, "powrecip");
1195     return 0;
1196   }
1197 };
1198
1199 struct Exp2Opt : public UnsafeFPLibCallOptimization {
1200   Exp2Opt(bool UnsafeFPShrink) : UnsafeFPLibCallOptimization(UnsafeFPShrink) {}
1201   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1202     Value *Ret = NULL;
1203     if (UnsafeFPShrink && Callee->getName() == "exp2" &&
1204         TLI->has(LibFunc::exp2f)) {
1205       UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
1206       Ret = UnsafeUnaryDoubleFP.callOptimizer(Callee, CI, B);
1207     }
1208
1209     FunctionType *FT = Callee->getFunctionType();
1210     // Just make sure this has 1 argument of FP type, which matches the
1211     // result type.
1212     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1213         !FT->getParamType(0)->isFloatingPointTy())
1214       return Ret;
1215
1216     Value *Op = CI->getArgOperand(0);
1217     // Turn exp2(sitofp(x)) -> ldexp(1.0, sext(x))  if sizeof(x) <= 32
1218     // Turn exp2(uitofp(x)) -> ldexp(1.0, zext(x))  if sizeof(x) < 32
1219     Value *LdExpArg = 0;
1220     if (SIToFPInst *OpC = dyn_cast<SIToFPInst>(Op)) {
1221       if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() <= 32)
1222         LdExpArg = B.CreateSExt(OpC->getOperand(0), B.getInt32Ty());
1223     } else if (UIToFPInst *OpC = dyn_cast<UIToFPInst>(Op)) {
1224       if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() < 32)
1225         LdExpArg = B.CreateZExt(OpC->getOperand(0), B.getInt32Ty());
1226     }
1227
1228     if (LdExpArg) {
1229       const char *Name;
1230       if (Op->getType()->isFloatTy())
1231         Name = "ldexpf";
1232       else if (Op->getType()->isDoubleTy())
1233         Name = "ldexp";
1234       else
1235         Name = "ldexpl";
1236
1237       Constant *One = ConstantFP::get(*Context, APFloat(1.0f));
1238       if (!Op->getType()->isFloatTy())
1239         One = ConstantExpr::getFPExtend(One, Op->getType());
1240
1241       Module *M = Caller->getParent();
1242       Value *Callee = M->getOrInsertFunction(Name, Op->getType(),
1243                                              Op->getType(),
1244                                              B.getInt32Ty(), NULL);
1245       CallInst *CI = B.CreateCall2(Callee, One, LdExpArg);
1246       if (const Function *F = dyn_cast<Function>(Callee->stripPointerCasts()))
1247         CI->setCallingConv(F->getCallingConv());
1248
1249       return CI;
1250     }
1251     return Ret;
1252   }
1253 };
1254
1255 //===----------------------------------------------------------------------===//
1256 // Integer Library Call Optimizations
1257 //===----------------------------------------------------------------------===//
1258
1259 struct FFSOpt : public LibCallOptimization {
1260   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1261     FunctionType *FT = Callee->getFunctionType();
1262     // Just make sure this has 2 arguments of the same FP type, which match the
1263     // result type.
1264     if (FT->getNumParams() != 1 ||
1265         !FT->getReturnType()->isIntegerTy(32) ||
1266         !FT->getParamType(0)->isIntegerTy())
1267       return 0;
1268
1269     Value *Op = CI->getArgOperand(0);
1270
1271     // Constant fold.
1272     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op)) {
1273       if (CI->isZero()) // ffs(0) -> 0.
1274         return B.getInt32(0);
1275       // ffs(c) -> cttz(c)+1
1276       return B.getInt32(CI->getValue().countTrailingZeros() + 1);
1277     }
1278
1279     // ffs(x) -> x != 0 ? (i32)llvm.cttz(x)+1 : 0
1280     Type *ArgType = Op->getType();
1281     Value *F = Intrinsic::getDeclaration(Callee->getParent(),
1282                                          Intrinsic::cttz, ArgType);
1283     Value *V = B.CreateCall2(F, Op, B.getFalse(), "cttz");
1284     V = B.CreateAdd(V, ConstantInt::get(V->getType(), 1));
1285     V = B.CreateIntCast(V, B.getInt32Ty(), false);
1286
1287     Value *Cond = B.CreateICmpNE(Op, Constant::getNullValue(ArgType));
1288     return B.CreateSelect(Cond, V, B.getInt32(0));
1289   }
1290 };
1291
1292 struct AbsOpt : public LibCallOptimization {
1293   virtual bool ignoreCallingConv() { return true; }
1294   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1295     FunctionType *FT = Callee->getFunctionType();
1296     // We require integer(integer) where the types agree.
1297     if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
1298         FT->getParamType(0) != FT->getReturnType())
1299       return 0;
1300
1301     // abs(x) -> x >s -1 ? x : -x
1302     Value *Op = CI->getArgOperand(0);
1303     Value *Pos = B.CreateICmpSGT(Op, Constant::getAllOnesValue(Op->getType()),
1304                                  "ispos");
1305     Value *Neg = B.CreateNeg(Op, "neg");
1306     return B.CreateSelect(Pos, Op, Neg);
1307   }
1308 };
1309
1310 struct IsDigitOpt : public LibCallOptimization {
1311   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1312     FunctionType *FT = Callee->getFunctionType();
1313     // We require integer(i32)
1314     if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
1315         !FT->getParamType(0)->isIntegerTy(32))
1316       return 0;
1317
1318     // isdigit(c) -> (c-'0') <u 10
1319     Value *Op = CI->getArgOperand(0);
1320     Op = B.CreateSub(Op, B.getInt32('0'), "isdigittmp");
1321     Op = B.CreateICmpULT(Op, B.getInt32(10), "isdigit");
1322     return B.CreateZExt(Op, CI->getType());
1323   }
1324 };
1325
1326 struct IsAsciiOpt : public LibCallOptimization {
1327   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1328     FunctionType *FT = Callee->getFunctionType();
1329     // We require integer(i32)
1330     if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
1331         !FT->getParamType(0)->isIntegerTy(32))
1332       return 0;
1333
1334     // isascii(c) -> c <u 128
1335     Value *Op = CI->getArgOperand(0);
1336     Op = B.CreateICmpULT(Op, B.getInt32(128), "isascii");
1337     return B.CreateZExt(Op, CI->getType());
1338   }
1339 };
1340
1341 struct ToAsciiOpt : public LibCallOptimization {
1342   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1343     FunctionType *FT = Callee->getFunctionType();
1344     // We require i32(i32)
1345     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1346         !FT->getParamType(0)->isIntegerTy(32))
1347       return 0;
1348
1349     // toascii(c) -> c & 0x7f
1350     return B.CreateAnd(CI->getArgOperand(0),
1351                        ConstantInt::get(CI->getType(),0x7F));
1352   }
1353 };
1354
1355 //===----------------------------------------------------------------------===//
1356 // Formatting and IO Library Call Optimizations
1357 //===----------------------------------------------------------------------===//
1358
1359 struct PrintFOpt : public LibCallOptimization {
1360   Value *optimizeFixedFormatString(Function *Callee, CallInst *CI,
1361                                    IRBuilder<> &B) {
1362     // Check for a fixed format string.
1363     StringRef FormatStr;
1364     if (!getConstantStringInfo(CI->getArgOperand(0), FormatStr))
1365       return 0;
1366
1367     // Empty format string -> noop.
1368     if (FormatStr.empty())  // Tolerate printf's declared void.
1369       return CI->use_empty() ? (Value*)CI :
1370                                ConstantInt::get(CI->getType(), 0);
1371
1372     // Do not do any of the following transformations if the printf return value
1373     // is used, in general the printf return value is not compatible with either
1374     // putchar() or puts().
1375     if (!CI->use_empty())
1376       return 0;
1377
1378     // printf("x") -> putchar('x'), even for '%'.
1379     if (FormatStr.size() == 1) {
1380       Value *Res = EmitPutChar(B.getInt32(FormatStr[0]), B, TD, TLI);
1381       if (CI->use_empty() || !Res) return Res;
1382       return B.CreateIntCast(Res, CI->getType(), true);
1383     }
1384
1385     // printf("foo\n") --> puts("foo")
1386     if (FormatStr[FormatStr.size()-1] == '\n' &&
1387         FormatStr.find('%') == StringRef::npos) { // No format characters.
1388       // Create a string literal with no \n on it.  We expect the constant merge
1389       // pass to be run after this pass, to merge duplicate strings.
1390       FormatStr = FormatStr.drop_back();
1391       Value *GV = B.CreateGlobalString(FormatStr, "str");
1392       Value *NewCI = EmitPutS(GV, B, TD, TLI);
1393       return (CI->use_empty() || !NewCI) ?
1394               NewCI :
1395               ConstantInt::get(CI->getType(), FormatStr.size()+1);
1396     }
1397
1398     // Optimize specific format strings.
1399     // printf("%c", chr) --> putchar(chr)
1400     if (FormatStr == "%c" && CI->getNumArgOperands() > 1 &&
1401         CI->getArgOperand(1)->getType()->isIntegerTy()) {
1402       Value *Res = EmitPutChar(CI->getArgOperand(1), B, TD, TLI);
1403
1404       if (CI->use_empty() || !Res) return Res;
1405       return B.CreateIntCast(Res, CI->getType(), true);
1406     }
1407
1408     // printf("%s\n", str) --> puts(str)
1409     if (FormatStr == "%s\n" && CI->getNumArgOperands() > 1 &&
1410         CI->getArgOperand(1)->getType()->isPointerTy()) {
1411       return EmitPutS(CI->getArgOperand(1), B, TD, TLI);
1412     }
1413     return 0;
1414   }
1415
1416   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1417     // Require one fixed pointer argument and an integer/void result.
1418     FunctionType *FT = Callee->getFunctionType();
1419     if (FT->getNumParams() < 1 || !FT->getParamType(0)->isPointerTy() ||
1420         !(FT->getReturnType()->isIntegerTy() ||
1421           FT->getReturnType()->isVoidTy()))
1422       return 0;
1423
1424     if (Value *V = optimizeFixedFormatString(Callee, CI, B)) {
1425       return V;
1426     }
1427
1428     // printf(format, ...) -> iprintf(format, ...) if no floating point
1429     // arguments.
1430     if (TLI->has(LibFunc::iprintf) && !callHasFloatingPointArgument(CI)) {
1431       Module *M = B.GetInsertBlock()->getParent()->getParent();
1432       Constant *IPrintFFn =
1433         M->getOrInsertFunction("iprintf", FT, Callee->getAttributes());
1434       CallInst *New = cast<CallInst>(CI->clone());
1435       New->setCalledFunction(IPrintFFn);
1436       B.Insert(New);
1437       return New;
1438     }
1439     return 0;
1440   }
1441 };
1442
1443 struct SPrintFOpt : public LibCallOptimization {
1444   Value *OptimizeFixedFormatString(Function *Callee, CallInst *CI,
1445                                    IRBuilder<> &B) {
1446     // Check for a fixed format string.
1447     StringRef FormatStr;
1448     if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr))
1449       return 0;
1450
1451     // If we just have a format string (nothing else crazy) transform it.
1452     if (CI->getNumArgOperands() == 2) {
1453       // Make sure there's no % in the constant array.  We could try to handle
1454       // %% -> % in the future if we cared.
1455       for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1456         if (FormatStr[i] == '%')
1457           return 0; // we found a format specifier, bail out.
1458
1459       // These optimizations require DataLayout.
1460       if (!TD) return 0;
1461
1462       // sprintf(str, fmt) -> llvm.memcpy(str, fmt, strlen(fmt)+1, 1)
1463       B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
1464                      ConstantInt::get(TD->getIntPtrType(*Context), // Copy the
1465                                       FormatStr.size() + 1), 1);   // nul byte.
1466       return ConstantInt::get(CI->getType(), FormatStr.size());
1467     }
1468
1469     // The remaining optimizations require the format string to be "%s" or "%c"
1470     // and have an extra operand.
1471     if (FormatStr.size() != 2 || FormatStr[0] != '%' ||
1472         CI->getNumArgOperands() < 3)
1473       return 0;
1474
1475     // Decode the second character of the format string.
1476     if (FormatStr[1] == 'c') {
1477       // sprintf(dst, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0
1478       if (!CI->getArgOperand(2)->getType()->isIntegerTy()) return 0;
1479       Value *V = B.CreateTrunc(CI->getArgOperand(2), B.getInt8Ty(), "char");
1480       Value *Ptr = CastToCStr(CI->getArgOperand(0), B);
1481       B.CreateStore(V, Ptr);
1482       Ptr = B.CreateGEP(Ptr, B.getInt32(1), "nul");
1483       B.CreateStore(B.getInt8(0), Ptr);
1484
1485       return ConstantInt::get(CI->getType(), 1);
1486     }
1487
1488     if (FormatStr[1] == 's') {
1489       // These optimizations require DataLayout.
1490       if (!TD) return 0;
1491
1492       // sprintf(dest, "%s", str) -> llvm.memcpy(dest, str, strlen(str)+1, 1)
1493       if (!CI->getArgOperand(2)->getType()->isPointerTy()) return 0;
1494
1495       Value *Len = EmitStrLen(CI->getArgOperand(2), B, TD, TLI);
1496       if (!Len)
1497         return 0;
1498       Value *IncLen = B.CreateAdd(Len,
1499                                   ConstantInt::get(Len->getType(), 1),
1500                                   "leninc");
1501       B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(2), IncLen, 1);
1502
1503       // The sprintf result is the unincremented number of bytes in the string.
1504       return B.CreateIntCast(Len, CI->getType(), false);
1505     }
1506     return 0;
1507   }
1508
1509   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1510     // Require two fixed pointer arguments and an integer result.
1511     FunctionType *FT = Callee->getFunctionType();
1512     if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
1513         !FT->getParamType(1)->isPointerTy() ||
1514         !FT->getReturnType()->isIntegerTy())
1515       return 0;
1516
1517     if (Value *V = OptimizeFixedFormatString(Callee, CI, B)) {
1518       return V;
1519     }
1520
1521     // sprintf(str, format, ...) -> siprintf(str, format, ...) if no floating
1522     // point arguments.
1523     if (TLI->has(LibFunc::siprintf) && !callHasFloatingPointArgument(CI)) {
1524       Module *M = B.GetInsertBlock()->getParent()->getParent();
1525       Constant *SIPrintFFn =
1526         M->getOrInsertFunction("siprintf", FT, Callee->getAttributes());
1527       CallInst *New = cast<CallInst>(CI->clone());
1528       New->setCalledFunction(SIPrintFFn);
1529       B.Insert(New);
1530       return New;
1531     }
1532     return 0;
1533   }
1534 };
1535
1536 struct FPrintFOpt : public LibCallOptimization {
1537   Value *optimizeFixedFormatString(Function *Callee, CallInst *CI,
1538                                    IRBuilder<> &B) {
1539     // All the optimizations depend on the format string.
1540     StringRef FormatStr;
1541     if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr))
1542       return 0;
1543
1544     // Do not do any of the following transformations if the fprintf return
1545     // value is used, in general the fprintf return value is not compatible
1546     // with fwrite(), fputc() or fputs().
1547     if (!CI->use_empty())
1548       return 0;
1549
1550     // fprintf(F, "foo") --> fwrite("foo", 3, 1, F)
1551     if (CI->getNumArgOperands() == 2) {
1552       for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1553         if (FormatStr[i] == '%')  // Could handle %% -> % if we cared.
1554           return 0; // We found a format specifier.
1555
1556       // These optimizations require DataLayout.
1557       if (!TD) return 0;
1558
1559       return EmitFWrite(CI->getArgOperand(1),
1560                         ConstantInt::get(TD->getIntPtrType(*Context),
1561                                          FormatStr.size()),
1562                         CI->getArgOperand(0), B, TD, TLI);
1563     }
1564
1565     // The remaining optimizations require the format string to be "%s" or "%c"
1566     // and have an extra operand.
1567     if (FormatStr.size() != 2 || FormatStr[0] != '%' ||
1568         CI->getNumArgOperands() < 3)
1569       return 0;
1570
1571     // Decode the second character of the format string.
1572     if (FormatStr[1] == 'c') {
1573       // fprintf(F, "%c", chr) --> fputc(chr, F)
1574       if (!CI->getArgOperand(2)->getType()->isIntegerTy()) return 0;
1575       return EmitFPutC(CI->getArgOperand(2), CI->getArgOperand(0), B, TD, TLI);
1576     }
1577
1578     if (FormatStr[1] == 's') {
1579       // fprintf(F, "%s", str) --> fputs(str, F)
1580       if (!CI->getArgOperand(2)->getType()->isPointerTy())
1581         return 0;
1582       return EmitFPutS(CI->getArgOperand(2), CI->getArgOperand(0), B, TD, TLI);
1583     }
1584     return 0;
1585   }
1586
1587   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1588     // Require two fixed paramters as pointers and integer result.
1589     FunctionType *FT = Callee->getFunctionType();
1590     if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
1591         !FT->getParamType(1)->isPointerTy() ||
1592         !FT->getReturnType()->isIntegerTy())
1593       return 0;
1594
1595     if (Value *V = optimizeFixedFormatString(Callee, CI, B)) {
1596       return V;
1597     }
1598
1599     // fprintf(stream, format, ...) -> fiprintf(stream, format, ...) if no
1600     // floating point arguments.
1601     if (TLI->has(LibFunc::fiprintf) && !callHasFloatingPointArgument(CI)) {
1602       Module *M = B.GetInsertBlock()->getParent()->getParent();
1603       Constant *FIPrintFFn =
1604         M->getOrInsertFunction("fiprintf", FT, Callee->getAttributes());
1605       CallInst *New = cast<CallInst>(CI->clone());
1606       New->setCalledFunction(FIPrintFFn);
1607       B.Insert(New);
1608       return New;
1609     }
1610     return 0;
1611   }
1612 };
1613
1614 struct FWriteOpt : public LibCallOptimization {
1615   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1616     // Require a pointer, an integer, an integer, a pointer, returning integer.
1617     FunctionType *FT = Callee->getFunctionType();
1618     if (FT->getNumParams() != 4 || !FT->getParamType(0)->isPointerTy() ||
1619         !FT->getParamType(1)->isIntegerTy() ||
1620         !FT->getParamType(2)->isIntegerTy() ||
1621         !FT->getParamType(3)->isPointerTy() ||
1622         !FT->getReturnType()->isIntegerTy())
1623       return 0;
1624
1625     // Get the element size and count.
1626     ConstantInt *SizeC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
1627     ConstantInt *CountC = dyn_cast<ConstantInt>(CI->getArgOperand(2));
1628     if (!SizeC || !CountC) return 0;
1629     uint64_t Bytes = SizeC->getZExtValue()*CountC->getZExtValue();
1630
1631     // If this is writing zero records, remove the call (it's a noop).
1632     if (Bytes == 0)
1633       return ConstantInt::get(CI->getType(), 0);
1634
1635     // If this is writing one byte, turn it into fputc.
1636     // This optimisation is only valid, if the return value is unused.
1637     if (Bytes == 1 && CI->use_empty()) {  // fwrite(S,1,1,F) -> fputc(S[0],F)
1638       Value *Char = B.CreateLoad(CastToCStr(CI->getArgOperand(0), B), "char");
1639       Value *NewCI = EmitFPutC(Char, CI->getArgOperand(3), B, TD, TLI);
1640       return NewCI ? ConstantInt::get(CI->getType(), 1) : 0;
1641     }
1642
1643     return 0;
1644   }
1645 };
1646
1647 struct FPutsOpt : public LibCallOptimization {
1648   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1649     // These optimizations require DataLayout.
1650     if (!TD) return 0;
1651
1652     // Require two pointers.  Also, we can't optimize if return value is used.
1653     FunctionType *FT = Callee->getFunctionType();
1654     if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
1655         !FT->getParamType(1)->isPointerTy() ||
1656         !CI->use_empty())
1657       return 0;
1658
1659     // fputs(s,F) --> fwrite(s,1,strlen(s),F)
1660     uint64_t Len = GetStringLength(CI->getArgOperand(0));
1661     if (!Len) return 0;
1662     // Known to have no uses (see above).
1663     return EmitFWrite(CI->getArgOperand(0),
1664                       ConstantInt::get(TD->getIntPtrType(*Context), Len-1),
1665                       CI->getArgOperand(1), B, TD, TLI);
1666   }
1667 };
1668
1669 struct PutsOpt : public LibCallOptimization {
1670   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1671     // Require one fixed pointer argument and an integer/void result.
1672     FunctionType *FT = Callee->getFunctionType();
1673     if (FT->getNumParams() < 1 || !FT->getParamType(0)->isPointerTy() ||
1674         !(FT->getReturnType()->isIntegerTy() ||
1675           FT->getReturnType()->isVoidTy()))
1676       return 0;
1677
1678     // Check for a constant string.
1679     StringRef Str;
1680     if (!getConstantStringInfo(CI->getArgOperand(0), Str))
1681       return 0;
1682
1683     if (Str.empty() && CI->use_empty()) {
1684       // puts("") -> putchar('\n')
1685       Value *Res = EmitPutChar(B.getInt32('\n'), B, TD, TLI);
1686       if (CI->use_empty() || !Res) return Res;
1687       return B.CreateIntCast(Res, CI->getType(), true);
1688     }
1689
1690     return 0;
1691   }
1692 };
1693
1694 } // End anonymous namespace.
1695
1696 namespace llvm {
1697
1698 class LibCallSimplifierImpl {
1699   const DataLayout *TD;
1700   const TargetLibraryInfo *TLI;
1701   const LibCallSimplifier *LCS;
1702   bool UnsafeFPShrink;
1703
1704   // Math library call optimizations.
1705   CosOpt Cos;
1706   PowOpt Pow;
1707   Exp2Opt Exp2;
1708 public:
1709   LibCallSimplifierImpl(const DataLayout *TD, const TargetLibraryInfo *TLI,
1710                         const LibCallSimplifier *LCS,
1711                         bool UnsafeFPShrink = false)
1712     : Cos(UnsafeFPShrink), Pow(UnsafeFPShrink), Exp2(UnsafeFPShrink) {
1713     this->TD = TD;
1714     this->TLI = TLI;
1715     this->LCS = LCS;
1716     this->UnsafeFPShrink = UnsafeFPShrink;
1717   }
1718
1719   Value *optimizeCall(CallInst *CI);
1720   LibCallOptimization *lookupOptimization(CallInst *CI);
1721   bool hasFloatVersion(StringRef FuncName);
1722 };
1723
1724 bool LibCallSimplifierImpl::hasFloatVersion(StringRef FuncName) {
1725   LibFunc::Func Func;
1726   SmallString<20> FloatFuncName = FuncName;
1727   FloatFuncName += 'f';
1728   if (TLI->getLibFunc(FloatFuncName, Func))
1729     return TLI->has(Func);
1730   return false;
1731 }
1732
1733 // Fortified library call optimizations.
1734 static MemCpyChkOpt MemCpyChk;
1735 static MemMoveChkOpt MemMoveChk;
1736 static MemSetChkOpt MemSetChk;
1737 static StrCpyChkOpt StrCpyChk;
1738 static StpCpyChkOpt StpCpyChk;
1739 static StrNCpyChkOpt StrNCpyChk;
1740
1741 // String library call optimizations.
1742 static StrCatOpt StrCat;
1743 static StrNCatOpt StrNCat;
1744 static StrChrOpt StrChr;
1745 static StrRChrOpt StrRChr;
1746 static StrCmpOpt StrCmp;
1747 static StrNCmpOpt StrNCmp;
1748 static StrCpyOpt StrCpy;
1749 static StpCpyOpt StpCpy;
1750 static StrNCpyOpt StrNCpy;
1751 static StrLenOpt StrLen;
1752 static StrPBrkOpt StrPBrk;
1753 static StrToOpt StrTo;
1754 static StrSpnOpt StrSpn;
1755 static StrCSpnOpt StrCSpn;
1756 static StrStrOpt StrStr;
1757
1758 // Memory library call optimizations.
1759 static MemCmpOpt MemCmp;
1760 static MemCpyOpt MemCpy;
1761 static MemMoveOpt MemMove;
1762 static MemSetOpt MemSet;
1763
1764 // Math library call optimizations.
1765 static UnaryDoubleFPOpt UnaryDoubleFP(false);
1766 static UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
1767
1768   // Integer library call optimizations.
1769 static FFSOpt FFS;
1770 static AbsOpt Abs;
1771 static IsDigitOpt IsDigit;
1772 static IsAsciiOpt IsAscii;
1773 static ToAsciiOpt ToAscii;
1774
1775 // Formatting and IO library call optimizations.
1776 static PrintFOpt PrintF;
1777 static SPrintFOpt SPrintF;
1778 static FPrintFOpt FPrintF;
1779 static FWriteOpt FWrite;
1780 static FPutsOpt FPuts;
1781 static PutsOpt Puts;
1782
1783 LibCallOptimization *LibCallSimplifierImpl::lookupOptimization(CallInst *CI) {
1784   LibFunc::Func Func;
1785   Function *Callee = CI->getCalledFunction();
1786   StringRef FuncName = Callee->getName();
1787
1788   // Next check for intrinsics.
1789   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI)) {
1790     switch (II->getIntrinsicID()) {
1791     case Intrinsic::pow:
1792        return &Pow;
1793     case Intrinsic::exp2:
1794        return &Exp2;
1795     default:
1796        return 0;
1797     }
1798   }
1799
1800   // Then check for known library functions.
1801   if (TLI->getLibFunc(FuncName, Func) && TLI->has(Func)) {
1802     switch (Func) {
1803       case LibFunc::strcat:
1804         return &StrCat;
1805       case LibFunc::strncat:
1806         return &StrNCat;
1807       case LibFunc::strchr:
1808         return &StrChr;
1809       case LibFunc::strrchr:
1810         return &StrRChr;
1811       case LibFunc::strcmp:
1812         return &StrCmp;
1813       case LibFunc::strncmp:
1814         return &StrNCmp;
1815       case LibFunc::strcpy:
1816         return &StrCpy;
1817       case LibFunc::stpcpy:
1818         return &StpCpy;
1819       case LibFunc::strncpy:
1820         return &StrNCpy;
1821       case LibFunc::strlen:
1822         return &StrLen;
1823       case LibFunc::strpbrk:
1824         return &StrPBrk;
1825       case LibFunc::strtol:
1826       case LibFunc::strtod:
1827       case LibFunc::strtof:
1828       case LibFunc::strtoul:
1829       case LibFunc::strtoll:
1830       case LibFunc::strtold:
1831       case LibFunc::strtoull:
1832         return &StrTo;
1833       case LibFunc::strspn:
1834         return &StrSpn;
1835       case LibFunc::strcspn:
1836         return &StrCSpn;
1837       case LibFunc::strstr:
1838         return &StrStr;
1839       case LibFunc::memcmp:
1840         return &MemCmp;
1841       case LibFunc::memcpy:
1842         return &MemCpy;
1843       case LibFunc::memmove:
1844         return &MemMove;
1845       case LibFunc::memset:
1846         return &MemSet;
1847       case LibFunc::cosf:
1848       case LibFunc::cos:
1849       case LibFunc::cosl:
1850         return &Cos;
1851       case LibFunc::powf:
1852       case LibFunc::pow:
1853       case LibFunc::powl:
1854         return &Pow;
1855       case LibFunc::exp2l:
1856       case LibFunc::exp2:
1857       case LibFunc::exp2f:
1858         return &Exp2;
1859       case LibFunc::ffs:
1860       case LibFunc::ffsl:
1861       case LibFunc::ffsll:
1862         return &FFS;
1863       case LibFunc::abs:
1864       case LibFunc::labs:
1865       case LibFunc::llabs:
1866         return &Abs;
1867       case LibFunc::isdigit:
1868         return &IsDigit;
1869       case LibFunc::isascii:
1870         return &IsAscii;
1871       case LibFunc::toascii:
1872         return &ToAscii;
1873       case LibFunc::printf:
1874         return &PrintF;
1875       case LibFunc::sprintf:
1876         return &SPrintF;
1877       case LibFunc::fprintf:
1878         return &FPrintF;
1879       case LibFunc::fwrite:
1880         return &FWrite;
1881       case LibFunc::fputs:
1882         return &FPuts;
1883       case LibFunc::puts:
1884         return &Puts;
1885       case LibFunc::ceil:
1886       case LibFunc::fabs:
1887       case LibFunc::floor:
1888       case LibFunc::rint:
1889       case LibFunc::round:
1890       case LibFunc::nearbyint:
1891       case LibFunc::trunc:
1892         if (hasFloatVersion(FuncName))
1893           return &UnaryDoubleFP;
1894         return 0;
1895       case LibFunc::acos:
1896       case LibFunc::acosh:
1897       case LibFunc::asin:
1898       case LibFunc::asinh:
1899       case LibFunc::atan:
1900       case LibFunc::atanh:
1901       case LibFunc::cbrt:
1902       case LibFunc::cosh:
1903       case LibFunc::exp:
1904       case LibFunc::exp10:
1905       case LibFunc::expm1:
1906       case LibFunc::log:
1907       case LibFunc::log10:
1908       case LibFunc::log1p:
1909       case LibFunc::log2:
1910       case LibFunc::logb:
1911       case LibFunc::sin:
1912       case LibFunc::sinh:
1913       case LibFunc::sqrt:
1914       case LibFunc::tan:
1915       case LibFunc::tanh:
1916         if (UnsafeFPShrink && hasFloatVersion(FuncName))
1917          return &UnsafeUnaryDoubleFP;
1918         return 0;
1919       case LibFunc::memcpy_chk:
1920         return &MemCpyChk;
1921       default:
1922         return 0;
1923       }
1924   }
1925
1926   // Finally check for fortified library calls.
1927   if (FuncName.endswith("_chk")) {
1928     if (FuncName == "__memmove_chk")
1929       return &MemMoveChk;
1930     else if (FuncName == "__memset_chk")
1931       return &MemSetChk;
1932     else if (FuncName == "__strcpy_chk")
1933       return &StrCpyChk;
1934     else if (FuncName == "__stpcpy_chk")
1935       return &StpCpyChk;
1936     else if (FuncName == "__strncpy_chk")
1937       return &StrNCpyChk;
1938     else if (FuncName == "__stpncpy_chk")
1939       return &StrNCpyChk;
1940   }
1941
1942   return 0;
1943
1944 }
1945
1946 Value *LibCallSimplifierImpl::optimizeCall(CallInst *CI) {
1947   LibCallOptimization *LCO = lookupOptimization(CI);
1948   if (LCO) {
1949     IRBuilder<> Builder(CI);
1950     return LCO->optimizeCall(CI, TD, TLI, LCS, Builder);
1951   }
1952   return 0;
1953 }
1954
1955 LibCallSimplifier::LibCallSimplifier(const DataLayout *TD,
1956                                      const TargetLibraryInfo *TLI,
1957                                      bool UnsafeFPShrink) {
1958   Impl = new LibCallSimplifierImpl(TD, TLI, this, UnsafeFPShrink);
1959 }
1960
1961 LibCallSimplifier::~LibCallSimplifier() {
1962   delete Impl;
1963 }
1964
1965 Value *LibCallSimplifier::optimizeCall(CallInst *CI) {
1966   if (CI->isNoBuiltin()) return 0;
1967   return Impl->optimizeCall(CI);
1968 }
1969
1970 void LibCallSimplifier::replaceAllUsesWith(Instruction *I, Value *With) const {
1971   I->replaceAllUsesWith(With);
1972   I->eraseFromParent();
1973 }
1974
1975 }
1976
1977 // TODO:
1978 //   Additional cases that we need to add to this file:
1979 //
1980 // cbrt:
1981 //   * cbrt(expN(X))  -> expN(x/3)
1982 //   * cbrt(sqrt(x))  -> pow(x,1/6)
1983 //   * cbrt(sqrt(x))  -> pow(x,1/9)
1984 //
1985 // exp, expf, expl:
1986 //   * exp(log(x))  -> x
1987 //
1988 // log, logf, logl:
1989 //   * log(exp(x))   -> x
1990 //   * log(x**y)     -> y*log(x)
1991 //   * log(exp(y))   -> y*log(e)
1992 //   * log(exp2(y))  -> y*log(2)
1993 //   * log(exp10(y)) -> y*log(10)
1994 //   * log(sqrt(x))  -> 0.5*log(x)
1995 //   * log(pow(x,y)) -> y*log(x)
1996 //
1997 // lround, lroundf, lroundl:
1998 //   * lround(cnst) -> cnst'
1999 //
2000 // pow, powf, powl:
2001 //   * pow(exp(x),y)  -> exp(x*y)
2002 //   * pow(sqrt(x),y) -> pow(x,y*0.5)
2003 //   * pow(pow(x,y),z)-> pow(x,y*z)
2004 //
2005 // round, roundf, roundl:
2006 //   * round(cnst) -> cnst'
2007 //
2008 // signbit:
2009 //   * signbit(cnst) -> cnst'
2010 //   * signbit(nncst) -> 0 (if pstv is a non-negative constant)
2011 //
2012 // sqrt, sqrtf, sqrtl:
2013 //   * sqrt(expN(x))  -> expN(x*0.5)
2014 //   * sqrt(Nroot(x)) -> pow(x,1/(2*N))
2015 //   * sqrt(pow(x,y)) -> pow(|x|,y*0.5)
2016 //
2017 // strchr:
2018 //   * strchr(p, 0) -> strlen(p)
2019 // tan, tanf, tanl:
2020 //   * tan(atan(x)) -> x
2021 //
2022 // trunc, truncf, truncl:
2023 //   * trunc(cnst) -> cnst'
2024 //
2025 //