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