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