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/DataLayout.h"
  19 #include "llvm/ADT/StringMap.h"
  20 #include "llvm/Analysis/ValueTracking.h"
  21 #include "llvm/Function.h"
  22 #include "llvm/IRBuilder.h"
  23 #include "llvm/Module.h"
  24 #include "llvm/LLVMContext.h"
  25 #include "llvm/Target/TargetLibraryInfo.h"
  26 #include "llvm/Transforms/Utils/BuildLibCalls.h"
  27
  28 using namespace llvm;
  29
  30 /// This class is the abstract base class for the set of optimizations that
  31 /// corresponds to one library call.
  32 namespace {
  33 class LibCallOptimization {
  34 protected:
  35   Function *Caller;
  36   const DataLayout *TD;
  37   const TargetLibraryInfo *TLI;
  38   const LibCallSimplifier *LCS;
  39   LLVMContext* Context;
  40 public:
  41   LibCallOptimization() { }
  42   virtual ~LibCallOptimization() {}
  43
  44   /// callOptimizer - This pure virtual method is implemented by base classes to
  45   /// do various optimizations.  If this returns null then no transformation was
  46   /// performed.  If it returns CI, then it transformed the call and CI is to be
  47   /// deleted.  If it returns something else, replace CI with the new value and
  48   /// delete CI.
  49   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B)
  50     =0;
  51
  52   Value *optimizeCall(CallInst *CI, const DataLayout *TD,
  53                       const TargetLibraryInfo *TLI,
  54                       const LibCallSimplifier *LCS, IRBuilder<> &B) {
  55     Caller = CI->getParent()->getParent();
  56     this->TD = TD;
  57     this->TLI = TLI;
  58     this->LCS = LCS;
  59     if (CI->getCalledFunction())
  60       Context = &CI->getCalledFunction()->getContext();
  61
  62     // We never change the calling convention.
  63     if (CI->getCallingConv() != llvm::CallingConv::C)
  64       return NULL;
  65
  66     return callOptimizer(CI->getCalledFunction(), CI, B);
  67   }
  68 };
  69
  70 //===----------------------------------------------------------------------===//
  71 // Helper Functions
  72 //===----------------------------------------------------------------------===//
  73
  74 /// isOnlyUsedInZeroEqualityComparison - Return true if it only matters that the
  75 /// value is equal or not-equal to zero.
  76 static bool isOnlyUsedInZeroEqualityComparison(Value *V) {
  77   for (Value::use_iterator UI = V->use_begin(), E = V->use_end();
  78        UI != E; ++UI) {
  79     if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI))
  80       if (IC->isEquality())
  81         if (Constant *C = dyn_cast<Constant>(IC->getOperand(1)))
  82           if (C->isNullValue())
  83             continue;
  84     // Unknown instruction.
  85     return false;
  86   }
  87   return true;
  88 }
  89
  90 /// isOnlyUsedInEqualityComparison - Return true if it is only used in equality
  91 /// comparisons with With.
  92 static bool isOnlyUsedInEqualityComparison(Value *V, Value *With) {
  93   for (Value::use_iterator UI = V->use_begin(), E = V->use_end();
  94        UI != E; ++UI) {
  95     if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI))
  96       if (IC->isEquality() && IC->getOperand(1) == With)
  97         continue;
  98     // Unknown instruction.
  99     return false;
 100   }
 101   return true;
 102 }
 103
 104 //===----------------------------------------------------------------------===//
 105 // Fortified Library Call Optimizations
 106 //===----------------------------------------------------------------------===//
 107
 108 struct FortifiedLibCallOptimization : public LibCallOptimization {
 109 protected:
 110   virtual bool isFoldable(unsigned SizeCIOp, unsigned SizeArgOp,
 111                           bool isString) const = 0;
 112 };
 113
 114 struct InstFortifiedLibCallOptimization : public FortifiedLibCallOptimization {
 115   CallInst *CI;
 116
 117   bool isFoldable(unsigned SizeCIOp, unsigned SizeArgOp, bool isString) const {
 118     if (CI->getArgOperand(SizeCIOp) == CI->getArgOperand(SizeArgOp))
 119       return true;
 120     if (ConstantInt *SizeCI =
 121                            dyn_cast<ConstantInt>(CI->getArgOperand(SizeCIOp))) {
 122       if (SizeCI->isAllOnesValue())
 123         return true;
 124       if (isString) {
 125         uint64_t Len = GetStringLength(CI->getArgOperand(SizeArgOp));
 126         // If the length is 0 we don't know how long it is and so we can't
 127         // remove the check.
 128         if (Len == 0) return false;
 129         return SizeCI->getZExtValue() >= Len;
 130       }
 131       if (ConstantInt *Arg = dyn_cast<ConstantInt>(
 132                                                   CI->getArgOperand(SizeArgOp)))
 133         return SizeCI->getZExtValue() >= Arg->getZExtValue();
 134     }
 135     return false;
 136   }
 137 };
 138
 139 struct MemCpyChkOpt : public InstFortifiedLibCallOptimization {
 140   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 141     this->CI = CI;
 142     FunctionType *FT = Callee->getFunctionType();
 143     LLVMContext &Context = CI->getParent()->getContext();
 144
 145     // Check if this has the right signature.
 146     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 147         !FT->getParamType(0)->isPointerTy() ||
 148         !FT->getParamType(1)->isPointerTy() ||
 149         FT->getParamType(2) != TD->getIntPtrType(Context) ||
 150         FT->getParamType(3) != TD->getIntPtrType(Context))
 151       return 0;
 152
 153     if (isFoldable(3, 2, false)) {
 154       B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
 155                      CI->getArgOperand(2), 1);
 156       return CI->getArgOperand(0);
 157     }
 158     return 0;
 159   }
 160 };
 161
 162 struct MemMoveChkOpt : public InstFortifiedLibCallOptimization {
 163   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 164     this->CI = CI;
 165     FunctionType *FT = Callee->getFunctionType();
 166     LLVMContext &Context = CI->getParent()->getContext();
 167
 168     // Check if this has the right signature.
 169     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 170         !FT->getParamType(0)->isPointerTy() ||
 171         !FT->getParamType(1)->isPointerTy() ||
 172         FT->getParamType(2) != TD->getIntPtrType(Context) ||
 173         FT->getParamType(3) != TD->getIntPtrType(Context))
 174       return 0;
 175
 176     if (isFoldable(3, 2, false)) {
 177       B.CreateMemMove(CI->getArgOperand(0), CI->getArgOperand(1),
 178                       CI->getArgOperand(2), 1);
 179       return CI->getArgOperand(0);
 180     }
 181     return 0;
 182   }
 183 };
 184
 185 struct MemSetChkOpt : public InstFortifiedLibCallOptimization {
 186   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 187     this->CI = CI;
 188     FunctionType *FT = Callee->getFunctionType();
 189     LLVMContext &Context = CI->getParent()->getContext();
 190
 191     // Check if this has the right signature.
 192     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 193         !FT->getParamType(0)->isPointerTy() ||
 194         !FT->getParamType(1)->isIntegerTy() ||
 195         FT->getParamType(2) != TD->getIntPtrType(Context) ||
 196         FT->getParamType(3) != TD->getIntPtrType(Context))
 197       return 0;
 198
 199     if (isFoldable(3, 2, false)) {
 200       Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(),
 201                                    false);
 202       B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1);
 203       return CI->getArgOperand(0);
 204     }
 205     return 0;
 206   }
 207 };
 208
 209 struct StrCpyChkOpt : public InstFortifiedLibCallOptimization {
 210   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 211     this->CI = CI;
 212     StringRef Name = Callee->getName();
 213     FunctionType *FT = Callee->getFunctionType();
 214     LLVMContext &Context = CI->getParent()->getContext();
 215
 216     // Check if this has the right signature.
 217     if (FT->getNumParams() != 3 ||
 218         FT->getReturnType() != FT->getParamType(0) ||
 219         FT->getParamType(0) != FT->getParamType(1) ||
 220         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
 221         FT->getParamType(2) != TD->getIntPtrType(Context))
 222       return 0;
 223
 224     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 225     if (Dst == Src)      // __strcpy_chk(x,x)  -> x
 226       return Src;
 227
 228     // If a) we don't have any length information, or b) we know this will
 229     // fit then just lower to a plain strcpy. Otherwise we'll keep our
 230     // strcpy_chk call which may fail at runtime if the size is too long.
 231     // TODO: It might be nice to get a maximum length out of the possible
 232     // string lengths for varying.
 233     if (isFoldable(2, 1, true)) {
 234       Value *Ret = EmitStrCpy(Dst, Src, B, TD, TLI, Name.substr(2, 6));
 235       return Ret;
 236     } else {
 237       // Maybe we can stil fold __strcpy_chk to __memcpy_chk.
 238       uint64_t Len = GetStringLength(Src);
 239       if (Len == 0) return 0;
 240
 241       // This optimization require DataLayout.
 242       if (!TD) return 0;
 243
 244       Value *Ret =
 245         EmitMemCpyChk(Dst, Src,
 246                       ConstantInt::get(TD->getIntPtrType(Context), Len),
 247                       CI->getArgOperand(2), B, TD, TLI);
 248       return Ret;
 249     }
 250     return 0;
 251   }
 252 };
 253
 254 struct StpCpyChkOpt : public InstFortifiedLibCallOptimization {
 255   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 256     this->CI = CI;
 257     StringRef Name = Callee->getName();
 258     FunctionType *FT = Callee->getFunctionType();
 259     LLVMContext &Context = CI->getParent()->getContext();
 260
 261     // Check if this has the right signature.
 262     if (FT->getNumParams() != 3 ||
 263         FT->getReturnType() != FT->getParamType(0) ||
 264         FT->getParamType(0) != FT->getParamType(1) ||
 265         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
 266         FT->getParamType(2) != TD->getIntPtrType(FT->getParamType(0)))
 267       return 0;
 268
 269     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 270     if (Dst == Src) {  // stpcpy(x,x)  -> x+strlen(x)
 271       Value *StrLen = EmitStrLen(Src, B, TD, TLI);
 272       return StrLen ? B.CreateInBoundsGEP(Dst, StrLen) : 0;
 273     }
 274
 275     // If a) we don't have any length information, or b) we know this will
 276     // fit then just lower to a plain stpcpy. Otherwise we'll keep our
 277     // stpcpy_chk call which may fail at runtime if the size is too long.
 278     // TODO: It might be nice to get a maximum length out of the possible
 279     // string lengths for varying.
 280     if (isFoldable(2, 1, true)) {
 281       Value *Ret = EmitStrCpy(Dst, Src, B, TD, TLI, Name.substr(2, 6));
 282       return Ret;
 283     } else {
 284       // Maybe we can stil fold __stpcpy_chk to __memcpy_chk.
 285       uint64_t Len = GetStringLength(Src);
 286       if (Len == 0) return 0;
 287
 288       // This optimization require DataLayout.
 289       if (!TD) return 0;
 290
 291       Type *PT = FT->getParamType(0);
 292       Value *LenV = ConstantInt::get(TD->getIntPtrType(PT), Len);
 293       Value *DstEnd = B.CreateGEP(Dst,
 294                                   ConstantInt::get(TD->getIntPtrType(PT),
 295                                                    Len - 1));
 296       if (!EmitMemCpyChk(Dst, Src, LenV, CI->getArgOperand(2), B, TD, TLI))
 297         return 0;
 298       return DstEnd;
 299     }
 300     return 0;
 301   }
 302 };
 303
 304 struct StrNCpyChkOpt : public InstFortifiedLibCallOptimization {
 305   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 306     this->CI = CI;
 307     StringRef Name = Callee->getName();
 308     FunctionType *FT = Callee->getFunctionType();
 309     LLVMContext &Context = CI->getParent()->getContext();
 310
 311     // Check if this has the right signature.
 312     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 313         FT->getParamType(0) != FT->getParamType(1) ||
 314         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
 315         !FT->getParamType(2)->isIntegerTy() ||
 316         FT->getParamType(3) != TD->getIntPtrType(Context))
 317       return 0;
 318
 319     if (isFoldable(3, 2, false)) {
 320       Value *Ret = EmitStrNCpy(CI->getArgOperand(0), CI->getArgOperand(1),
 321                                CI->getArgOperand(2), B, TD, TLI,
 322                                Name.substr(2, 7));
 323       return Ret;
 324     }
 325     return 0;
 326   }
 327 };
 328
 329 //===----------------------------------------------------------------------===//
 330 // String and Memory Library Call Optimizations
 331 //===----------------------------------------------------------------------===//
 332
 333 struct StrCatOpt : public LibCallOptimization {
 334   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 335     // Verify the "strcat" function prototype.
 336     FunctionType *FT = Callee->getFunctionType();
 337     if (FT->getNumParams() != 2 ||
 338         FT->getReturnType() != B.getInt8PtrTy() ||
 339         FT->getParamType(0) != FT->getReturnType() ||
 340         FT->getParamType(1) != FT->getReturnType())
 341       return 0;
 342
 343     // Extract some information from the instruction
 344     Value *Dst = CI->getArgOperand(0);
 345     Value *Src = CI->getArgOperand(1);
 346
 347     // See if we can get the length of the input string.
 348     uint64_t Len = GetStringLength(Src);
 349     if (Len == 0) return 0;
 350     --Len;  // Unbias length.
 351
 352     // Handle the simple, do-nothing case: strcat(x, "") -> x
 353     if (Len == 0)
 354       return Dst;
 355
 356     // These optimizations require DataLayout.
 357     if (!TD) return 0;
 358
 359     return emitStrLenMemCpy(Src, Dst, Len, B);
 360   }
 361
 362   Value *emitStrLenMemCpy(Value *Src, Value *Dst, uint64_t Len,
 363                           IRBuilder<> &B) {
 364     // We need to find the end of the destination string.  That's where the
 365     // memory is to be moved to. We just generate a call to strlen.
 366     Value *DstLen = EmitStrLen(Dst, B, TD, TLI);
 367     if (!DstLen)
 368       return 0;
 369
 370     // Now that we have the destination's length, we must index into the
 371     // destination's pointer to get the actual memcpy destination (end of
 372     // the string .. we're concatenating).
 373     Value *CpyDst = B.CreateGEP(Dst, DstLen, "endptr");
 374
 375     // We have enough information to now generate the memcpy call to do the
 376     // concatenation for us.  Make a memcpy to copy the nul byte with align = 1.
 377     B.CreateMemCpy(CpyDst, Src,
 378                    ConstantInt::get(TD->getIntPtrType(*Context), Len + 1), 1);
 379     return Dst;
 380   }
 381 };
 382
 383 struct StrNCatOpt : public StrCatOpt {
 384   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 385     // Verify the "strncat" function prototype.
 386     FunctionType *FT = Callee->getFunctionType();
 387     if (FT->getNumParams() != 3 ||
 388         FT->getReturnType() != B.getInt8PtrTy() ||
 389         FT->getParamType(0) != FT->getReturnType() ||
 390         FT->getParamType(1) != FT->getReturnType() ||
 391         !FT->getParamType(2)->isIntegerTy())
 392       return 0;
 393
 394     // Extract some information from the instruction
 395     Value *Dst = CI->getArgOperand(0);
 396     Value *Src = CI->getArgOperand(1);
 397     uint64_t Len;
 398
 399     // We don't do anything if length is not constant
 400     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
 401       Len = LengthArg->getZExtValue();
 402     else
 403       return 0;
 404
 405     // See if we can get the length of the input string.
 406     uint64_t SrcLen = GetStringLength(Src);
 407     if (SrcLen == 0) return 0;
 408     --SrcLen;  // Unbias length.
 409
 410     // Handle the simple, do-nothing cases:
 411     // strncat(x, "", c) -> x
 412     // strncat(x,  c, 0) -> x
 413     if (SrcLen == 0 || Len == 0) return Dst;
 414
 415     // These optimizations require DataLayout.
 416     if (!TD) return 0;
 417
 418     // We don't optimize this case
 419     if (Len < SrcLen) return 0;
 420
 421     // strncat(x, s, c) -> strcat(x, s)
 422     // s is constant so the strcat can be optimized further
 423     return emitStrLenMemCpy(Src, Dst, SrcLen, B);
 424   }
 425 };
 426
 427 struct StrChrOpt : public LibCallOptimization {
 428   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 429     // Verify the "strchr" function prototype.
 430     FunctionType *FT = Callee->getFunctionType();
 431     if (FT->getNumParams() != 2 ||
 432         FT->getReturnType() != B.getInt8PtrTy() ||
 433         FT->getParamType(0) != FT->getReturnType() ||
 434         !FT->getParamType(1)->isIntegerTy(32))
 435       return 0;
 436
 437     Value *SrcStr = CI->getArgOperand(0);
 438
 439     // If the second operand is non-constant, see if we can compute the length
 440     // of the input string and turn this into memchr.
 441     ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
 442     if (CharC == 0) {
 443       // These optimizations require DataLayout.
 444       if (!TD) return 0;
 445
 446       uint64_t Len = GetStringLength(SrcStr);
 447       if (Len == 0 || !FT->getParamType(1)->isIntegerTy(32))// memchr needs i32.
 448         return 0;
 449
 450       return EmitMemChr(SrcStr, CI->getArgOperand(1), // include nul.
 451                         ConstantInt::get(TD->getIntPtrType(*Context), Len),
 452                         B, TD, TLI);
 453     }
 454
 455     // Otherwise, the character is a constant, see if the first argument is
 456     // a string literal.  If so, we can constant fold.
 457     StringRef Str;
 458     if (!getConstantStringInfo(SrcStr, Str))
 459       return 0;
 460
 461     // Compute the offset, make sure to handle the case when we're searching for
 462     // zero (a weird way to spell strlen).
 463     size_t I = CharC->getSExtValue() == 0 ?
 464         Str.size() : Str.find(CharC->getSExtValue());
 465     if (I == StringRef::npos) // Didn't find the char.  strchr returns null.
 466       return Constant::getNullValue(CI->getType());
 467
 468     // strchr(s+n,c)  -> gep(s+n+i,c)
 469     return B.CreateGEP(SrcStr, B.getInt64(I), "strchr");
 470   }
 471 };
 472
 473 struct StrRChrOpt : public LibCallOptimization {
 474   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 475     // Verify the "strrchr" function prototype.
 476     FunctionType *FT = Callee->getFunctionType();
 477     if (FT->getNumParams() != 2 ||
 478         FT->getReturnType() != B.getInt8PtrTy() ||
 479         FT->getParamType(0) != FT->getReturnType() ||
 480         !FT->getParamType(1)->isIntegerTy(32))
 481       return 0;
 482
 483     Value *SrcStr = CI->getArgOperand(0);
 484     ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
 485
 486     // Cannot fold anything if we're not looking for a constant.
 487     if (!CharC)
 488       return 0;
 489
 490     StringRef Str;
 491     if (!getConstantStringInfo(SrcStr, Str)) {
 492       // strrchr(s, 0) -> strchr(s, 0)
 493       if (TD && CharC->isZero())
 494         return EmitStrChr(SrcStr, '\0', B, TD, TLI);
 495       return 0;
 496     }
 497
 498     // Compute the offset.
 499     size_t I = CharC->getSExtValue() == 0 ?
 500         Str.size() : Str.rfind(CharC->getSExtValue());
 501     if (I == StringRef::npos) // Didn't find the char. Return null.
 502       return Constant::getNullValue(CI->getType());
 503
 504     // strrchr(s+n,c) -> gep(s+n+i,c)
 505     return B.CreateGEP(SrcStr, B.getInt64(I), "strrchr");
 506   }
 507 };
 508
 509 struct StrCmpOpt : public LibCallOptimization {
 510   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 511     // Verify the "strcmp" function prototype.
 512     FunctionType *FT = Callee->getFunctionType();
 513     if (FT->getNumParams() != 2 ||
 514         !FT->getReturnType()->isIntegerTy(32) ||
 515         FT->getParamType(0) != FT->getParamType(1) ||
 516         FT->getParamType(0) != B.getInt8PtrTy())
 517       return 0;
 518
 519     Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
 520     if (Str1P == Str2P)      // strcmp(x,x)  -> 0
 521       return ConstantInt::get(CI->getType(), 0);
 522
 523     StringRef Str1, Str2;
 524     bool HasStr1 = getConstantStringInfo(Str1P, Str1);
 525     bool HasStr2 = getConstantStringInfo(Str2P, Str2);
 526
 527     // strcmp(x, y)  -> cnst  (if both x and y are constant strings)
 528     if (HasStr1 && HasStr2)
 529       return ConstantInt::get(CI->getType(), Str1.compare(Str2));
 530
 531     if (HasStr1 && Str1.empty()) // strcmp("", x) -> -*x
 532       return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"),
 533                                       CI->getType()));
 534
 535     if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x
 536       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
 537
 538     // strcmp(P, "x") -> memcmp(P, "x", 2)
 539     uint64_t Len1 = GetStringLength(Str1P);
 540     uint64_t Len2 = GetStringLength(Str2P);
 541     if (Len1 && Len2) {
 542       // These optimizations require DataLayout.
 543       if (!TD) return 0;
 544
 545       return EmitMemCmp(Str1P, Str2P,
 546                         ConstantInt::get(TD->getIntPtrType(*Context),
 547                         std::min(Len1, Len2)), B, TD, TLI);
 548     }
 549
 550     return 0;
 551   }
 552 };
 553
 554 struct StrNCmpOpt : public LibCallOptimization {
 555   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 556     // Verify the "strncmp" function prototype.
 557     FunctionType *FT = Callee->getFunctionType();
 558     if (FT->getNumParams() != 3 ||
 559         !FT->getReturnType()->isIntegerTy(32) ||
 560         FT->getParamType(0) != FT->getParamType(1) ||
 561         FT->getParamType(0) != B.getInt8PtrTy() ||
 562         !FT->getParamType(2)->isIntegerTy())
 563       return 0;
 564
 565     Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
 566     if (Str1P == Str2P)      // strncmp(x,x,n)  -> 0
 567       return ConstantInt::get(CI->getType(), 0);
 568
 569     // Get the length argument if it is constant.
 570     uint64_t Length;
 571     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
 572       Length = LengthArg->getZExtValue();
 573     else
 574       return 0;
 575
 576     if (Length == 0) // strncmp(x,y,0)   -> 0
 577       return ConstantInt::get(CI->getType(), 0);
 578
 579     if (TD && Length == 1) // strncmp(x,y,1) -> memcmp(x,y,1)
 580       return EmitMemCmp(Str1P, Str2P, CI->getArgOperand(2), B, TD, TLI);
 581
 582     StringRef Str1, Str2;
 583     bool HasStr1 = getConstantStringInfo(Str1P, Str1);
 584     bool HasStr2 = getConstantStringInfo(Str2P, Str2);
 585
 586     // strncmp(x, y)  -> cnst  (if both x and y are constant strings)
 587     if (HasStr1 && HasStr2) {
 588       StringRef SubStr1 = Str1.substr(0, Length);
 589       StringRef SubStr2 = Str2.substr(0, Length);
 590       return ConstantInt::get(CI->getType(), SubStr1.compare(SubStr2));
 591     }
 592
 593     if (HasStr1 && Str1.empty())  // strncmp("", x, n) -> -*x
 594       return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"),
 595                                       CI->getType()));
 596
 597     if (HasStr2 && Str2.empty())  // strncmp(x, "", n) -> *x
 598       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
 599
 600     return 0;
 601   }
 602 };
 603
 604 struct StrCpyOpt : public LibCallOptimization {
 605   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 606     // Verify the "strcpy" function prototype.
 607     FunctionType *FT = Callee->getFunctionType();
 608     if (FT->getNumParams() != 2 ||
 609         FT->getReturnType() != FT->getParamType(0) ||
 610         FT->getParamType(0) != FT->getParamType(1) ||
 611         FT->getParamType(0) != B.getInt8PtrTy())
 612       return 0;
 613
 614     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 615     if (Dst == Src)      // strcpy(x,x)  -> x
 616       return Src;
 617
 618     // These optimizations require DataLayout.
 619     if (!TD) return 0;
 620
 621     // See if we can get the length of the input string.
 622     uint64_t Len = GetStringLength(Src);
 623     if (Len == 0) return 0;
 624
 625     // We have enough information to now generate the memcpy call to do the
 626     // copy for us.  Make a memcpy to copy the nul byte with align = 1.
 627     B.CreateMemCpy(Dst, Src,
 628                    ConstantInt::get(TD->getIntPtrType(*Context), Len), 1);
 629     return Dst;
 630   }
 631 };
 632
 633 struct StpCpyOpt: public LibCallOptimization {
 634   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 635     // Verify the "stpcpy" function prototype.
 636     FunctionType *FT = Callee->getFunctionType();
 637     if (FT->getNumParams() != 2 ||
 638         FT->getReturnType() != FT->getParamType(0) ||
 639         FT->getParamType(0) != FT->getParamType(1) ||
 640         FT->getParamType(0) != B.getInt8PtrTy())
 641       return 0;
 642
 643     // These optimizations require DataLayout.
 644     if (!TD) return 0;
 645
 646     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 647     if (Dst == Src) {  // stpcpy(x,x)  -> x+strlen(x)
 648       Value *StrLen = EmitStrLen(Src, B, TD, TLI);
 649       return StrLen ? B.CreateInBoundsGEP(Dst, StrLen) : 0;
 650     }
 651
 652     // See if we can get the length of the input string.
 653     uint64_t Len = GetStringLength(Src);
 654     if (Len == 0) return 0;
 655
 656     Type *PT = FT->getParamType(0);
 657     Value *LenV = ConstantInt::get(TD->getIntPtrType(PT), Len);
 658     Value *DstEnd = B.CreateGEP(Dst,
 659                                 ConstantInt::get(TD->getIntPtrType(PT),
 660                                                  Len - 1));
 661
 662     // We have enough information to now generate the memcpy call to do the
 663     // copy for us.  Make a memcpy to copy the nul byte with align = 1.
 664     B.CreateMemCpy(Dst, Src, LenV, 1);
 665     return DstEnd;
 666   }
 667 };
 668
 669 struct StrNCpyOpt : public LibCallOptimization {
 670   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 671     FunctionType *FT = Callee->getFunctionType();
 672     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 673         FT->getParamType(0) != FT->getParamType(1) ||
 674         FT->getParamType(0) != B.getInt8PtrTy() ||
 675         !FT->getParamType(2)->isIntegerTy())
 676       return 0;
 677
 678     Value *Dst = CI->getArgOperand(0);
 679     Value *Src = CI->getArgOperand(1);
 680     Value *LenOp = CI->getArgOperand(2);
 681
 682     // See if we can get the length of the input string.
 683     uint64_t SrcLen = GetStringLength(Src);
 684     if (SrcLen == 0) return 0;
 685     --SrcLen;
 686
 687     if (SrcLen == 0) {
 688       // strncpy(x, "", y) -> memset(x, '\0', y, 1)
 689       B.CreateMemSet(Dst, B.getInt8('\0'), LenOp, 1);
 690       return Dst;
 691     }
 692
 693     uint64_t Len;
 694     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(LenOp))
 695       Len = LengthArg->getZExtValue();
 696     else
 697       return 0;
 698
 699     if (Len == 0) return Dst; // strncpy(x, y, 0) -> x
 700
 701     // These optimizations require DataLayout.
 702     if (!TD) return 0;
 703
 704     // Let strncpy handle the zero padding
 705     if (Len > SrcLen+1) return 0;
 706
 707     Type *PT = FT->getParamType(0);
 708     // strncpy(x, s, c) -> memcpy(x, s, c, 1) [s and c are constant]
 709     B.CreateMemCpy(Dst, Src,
 710                    ConstantInt::get(TD->getIntPtrType(PT), Len), 1);
 711
 712     return Dst;
 713   }
 714 };
 715
 716 struct StrLenOpt : public LibCallOptimization {
 717   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 718     FunctionType *FT = Callee->getFunctionType();
 719     if (FT->getNumParams() != 1 ||
 720         FT->getParamType(0) != B.getInt8PtrTy() ||
 721         !FT->getReturnType()->isIntegerTy())
 722       return 0;
 723
 724     Value *Src = CI->getArgOperand(0);
 725
 726     // Constant folding: strlen("xyz") -> 3
 727     if (uint64_t Len = GetStringLength(Src))
 728       return ConstantInt::get(CI->getType(), Len-1);
 729
 730     // strlen(x) != 0 --> *x != 0
 731     // strlen(x) == 0 --> *x == 0
 732     if (isOnlyUsedInZeroEqualityComparison(CI))
 733       return B.CreateZExt(B.CreateLoad(Src, "strlenfirst"), CI->getType());
 734     return 0;
 735   }
 736 };
 737
 738 struct StrPBrkOpt : public LibCallOptimization {
 739   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 740     FunctionType *FT = Callee->getFunctionType();
 741     if (FT->getNumParams() != 2 ||
 742         FT->getParamType(0) != B.getInt8PtrTy() ||
 743         FT->getParamType(1) != FT->getParamType(0) ||
 744         FT->getReturnType() != FT->getParamType(0))
 745       return 0;
 746
 747     StringRef S1, S2;
 748     bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
 749     bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
 750
 751     // strpbrk(s, "") -> NULL
 752     // strpbrk("", s) -> NULL
 753     if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))
 754       return Constant::getNullValue(CI->getType());
 755
 756     // Constant folding.
 757     if (HasS1 && HasS2) {
 758       size_t I = S1.find_first_of(S2);
 759       if (I == std::string::npos) // No match.
 760         return Constant::getNullValue(CI->getType());
 761
 762       return B.CreateGEP(CI->getArgOperand(0), B.getInt64(I), "strpbrk");
 763     }
 764
 765     // strpbrk(s, "a") -> strchr(s, 'a')
 766     if (TD && HasS2 && S2.size() == 1)
 767       return EmitStrChr(CI->getArgOperand(0), S2[0], B, TD, TLI);
 768
 769     return 0;
 770   }
 771 };
 772
 773 struct StrToOpt : public LibCallOptimization {
 774   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 775     FunctionType *FT = Callee->getFunctionType();
 776     if ((FT->getNumParams() != 2 && FT->getNumParams() != 3) ||
 777         !FT->getParamType(0)->isPointerTy() ||
 778         !FT->getParamType(1)->isPointerTy())
 779       return 0;
 780
 781     Value *EndPtr = CI->getArgOperand(1);
 782     if (isa<ConstantPointerNull>(EndPtr)) {
 783       // With a null EndPtr, this function won't capture the main argument.
 784       // It would be readonly too, except that it still may write to errno.
 785       CI->addAttribute(1, Attributes::get(Callee->getContext(),
 786                                           Attributes::NoCapture));
 787     }
 788
 789     return 0;
 790   }
 791 };
 792
 793 struct StrSpnOpt : public LibCallOptimization {
 794   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 795     FunctionType *FT = Callee->getFunctionType();
 796     if (FT->getNumParams() != 2 ||
 797         FT->getParamType(0) != B.getInt8PtrTy() ||
 798         FT->getParamType(1) != FT->getParamType(0) ||
 799         !FT->getReturnType()->isIntegerTy())
 800       return 0;
 801
 802     StringRef S1, S2;
 803     bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
 804     bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
 805
 806     // strspn(s, "") -> 0
 807     // strspn("", s) -> 0
 808     if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))
 809       return Constant::getNullValue(CI->getType());
 810
 811     // Constant folding.
 812     if (HasS1 && HasS2) {
 813       size_t Pos = S1.find_first_not_of(S2);
 814       if (Pos == StringRef::npos) Pos = S1.size();
 815       return ConstantInt::get(CI->getType(), Pos);
 816     }
 817
 818     return 0;
 819   }
 820 };
 821
 822 struct StrCSpnOpt : public LibCallOptimization {
 823   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 824     FunctionType *FT = Callee->getFunctionType();
 825     if (FT->getNumParams() != 2 ||
 826         FT->getParamType(0) != B.getInt8PtrTy() ||
 827         FT->getParamType(1) != FT->getParamType(0) ||
 828         !FT->getReturnType()->isIntegerTy())
 829       return 0;
 830
 831     StringRef S1, S2;
 832     bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
 833     bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
 834
 835     // strcspn("", s) -> 0
 836     if (HasS1 && S1.empty())
 837       return Constant::getNullValue(CI->getType());
 838
 839     // Constant folding.
 840     if (HasS1 && HasS2) {
 841       size_t Pos = S1.find_first_of(S2);
 842       if (Pos == StringRef::npos) Pos = S1.size();
 843       return ConstantInt::get(CI->getType(), Pos);
 844     }
 845
 846     // strcspn(s, "") -> strlen(s)
 847     if (TD && HasS2 && S2.empty())
 848       return EmitStrLen(CI->getArgOperand(0), B, TD, TLI);
 849
 850     return 0;
 851   }
 852 };
 853
 854 struct StrStrOpt : public LibCallOptimization {
 855   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 856     FunctionType *FT = Callee->getFunctionType();
 857     if (FT->getNumParams() != 2 ||
 858         !FT->getParamType(0)->isPointerTy() ||
 859         !FT->getParamType(1)->isPointerTy() ||
 860         !FT->getReturnType()->isPointerTy())
 861       return 0;
 862
 863     // fold strstr(x, x) -> x.
 864     if (CI->getArgOperand(0) == CI->getArgOperand(1))
 865       return B.CreateBitCast(CI->getArgOperand(0), CI->getType());
 866
 867     // fold strstr(a, b) == a -> strncmp(a, b, strlen(b)) == 0
 868     if (TD && isOnlyUsedInEqualityComparison(CI, CI->getArgOperand(0))) {
 869       Value *StrLen = EmitStrLen(CI->getArgOperand(1), B, TD, TLI);
 870       if (!StrLen)
 871         return 0;
 872       Value *StrNCmp = EmitStrNCmp(CI->getArgOperand(0), CI->getArgOperand(1),
 873                                    StrLen, B, TD, TLI);
 874       if (!StrNCmp)
 875         return 0;
 876       for (Value::use_iterator UI = CI->use_begin(), UE = CI->use_end();
 877            UI != UE; ) {
 878         ICmpInst *Old = cast<ICmpInst>(*UI++);
 879         Value *Cmp = B.CreateICmp(Old->getPredicate(), StrNCmp,
 880                                   ConstantInt::getNullValue(StrNCmp->getType()),
 881                                   "cmp");
 882         LCS->replaceAllUsesWith(Old, Cmp);
 883       }
 884       return CI;
 885     }
 886
 887     // See if either input string is a constant string.
 888     StringRef SearchStr, ToFindStr;
 889     bool HasStr1 = getConstantStringInfo(CI->getArgOperand(0), SearchStr);
 890     bool HasStr2 = getConstantStringInfo(CI->getArgOperand(1), ToFindStr);
 891
 892     // fold strstr(x, "") -> x.
 893     if (HasStr2 && ToFindStr.empty())
 894       return B.CreateBitCast(CI->getArgOperand(0), CI->getType());
 895
 896     // If both strings are known, constant fold it.
 897     if (HasStr1 && HasStr2) {
 898       std::string::size_type Offset = SearchStr.find(ToFindStr);
 899
 900       if (Offset == StringRef::npos) // strstr("foo", "bar") -> null
 901         return Constant::getNullValue(CI->getType());
 902
 903       // strstr("abcd", "bc") -> gep((char*)"abcd", 1)
 904       Value *Result = CastToCStr(CI->getArgOperand(0), B);
 905       Result = B.CreateConstInBoundsGEP1_64(Result, Offset, "strstr");
 906       return B.CreateBitCast(Result, CI->getType());
 907     }
 908
 909     // fold strstr(x, "y") -> strchr(x, 'y').
 910     if (HasStr2 && ToFindStr.size() == 1) {
 911       Value *StrChr= EmitStrChr(CI->getArgOperand(0), ToFindStr[0], B, TD, TLI);
 912       return StrChr ? B.CreateBitCast(StrChr, CI->getType()) : 0;
 913     }
 914     return 0;
 915   }
 916 };
 917
 918 struct MemCmpOpt : public LibCallOptimization {
 919   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 920     FunctionType *FT = Callee->getFunctionType();
 921     if (FT->getNumParams() != 3 || !FT->getParamType(0)->isPointerTy() ||
 922         !FT->getParamType(1)->isPointerTy() ||
 923         !FT->getReturnType()->isIntegerTy(32))
 924       return 0;
 925
 926     Value *LHS = CI->getArgOperand(0), *RHS = CI->getArgOperand(1);
 927
 928     if (LHS == RHS)  // memcmp(s,s,x) -> 0
 929       return Constant::getNullValue(CI->getType());
 930
 931     // Make sure we have a constant length.
 932     ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getArgOperand(2));
 933     if (!LenC) return 0;
 934     uint64_t Len = LenC->getZExtValue();
 935
 936     if (Len == 0) // memcmp(s1,s2,0) -> 0
 937       return Constant::getNullValue(CI->getType());
 938
 939     // memcmp(S1,S2,1) -> *(unsigned char*)LHS - *(unsigned char*)RHS
 940     if (Len == 1) {
 941       Value *LHSV = B.CreateZExt(B.CreateLoad(CastToCStr(LHS, B), "lhsc"),
 942                                  CI->getType(), "lhsv");
 943       Value *RHSV = B.CreateZExt(B.CreateLoad(CastToCStr(RHS, B), "rhsc"),
 944                                  CI->getType(), "rhsv");
 945       return B.CreateSub(LHSV, RHSV, "chardiff");
 946     }
 947
 948     // Constant folding: memcmp(x, y, l) -> cnst (all arguments are constant)
 949     StringRef LHSStr, RHSStr;
 950     if (getConstantStringInfo(LHS, LHSStr) &&
 951         getConstantStringInfo(RHS, RHSStr)) {
 952       // Make sure we're not reading out-of-bounds memory.
 953       if (Len > LHSStr.size() || Len > RHSStr.size())
 954         return 0;
 955       // Fold the memcmp and normalize the result.  This way we get consistent
 956       // results across multiple platforms.
 957       uint64_t Ret = 0;
 958       int Cmp = memcmp(LHSStr.data(), RHSStr.data(), Len);
 959       if (Cmp < 0)
 960         Ret = -1;
 961       else if (Cmp > 0)
 962         Ret = 1;
 963       return ConstantInt::get(CI->getType(), Ret);
 964     }
 965
 966     return 0;
 967   }
 968 };
 969
 970 struct MemCpyOpt : public LibCallOptimization {
 971   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 972     // These optimizations require DataLayout.
 973     if (!TD) return 0;
 974
 975     FunctionType *FT = Callee->getFunctionType();
 976     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 977         !FT->getParamType(0)->isPointerTy() ||
 978         !FT->getParamType(1)->isPointerTy() ||
 979         FT->getParamType(2) != TD->getIntPtrType(*Context))
 980       return 0;
 981
 982     // memcpy(x, y, n) -> llvm.memcpy(x, y, n, 1)
 983     B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
 984                    CI->getArgOperand(2), 1);
 985     return CI->getArgOperand(0);
 986   }
 987 };
 988
 989 struct MemMoveOpt : public LibCallOptimization {
 990   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 991     // These optimizations require DataLayout.
 992     if (!TD) return 0;
 993
 994     FunctionType *FT = Callee->getFunctionType();
 995     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 996         !FT->getParamType(0)->isPointerTy() ||
 997         !FT->getParamType(1)->isPointerTy() ||
 998         FT->getParamType(2) != TD->getIntPtrType(*Context))
 999       return 0;
1000
1001     // memmove(x, y, n) -> llvm.memmove(x, y, n, 1)
1002     B.CreateMemMove(CI->getArgOperand(0), CI->getArgOperand(1),
1003                     CI->getArgOperand(2), 1);
1004     return CI->getArgOperand(0);
1005   }
1006 };
1007
1008 struct MemSetOpt : public LibCallOptimization {
1009   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1010     // These optimizations require DataLayout.
1011     if (!TD) return 0;
1012
1013     FunctionType *FT = Callee->getFunctionType();
1014     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
1015         !FT->getParamType(0)->isPointerTy() ||
1016         !FT->getParamType(1)->isIntegerTy() ||
1017         FT->getParamType(2) != TD->getIntPtrType(*Context))
1018       return 0;
1019
1020     // memset(p, v, n) -> llvm.memset(p, v, n, 1)
1021     Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(), false);
1022     B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1);
1023     return CI->getArgOperand(0);
1024   }
1025 };
1026
1027 //===----------------------------------------------------------------------===//
1028 // Math Library Optimizations
1029 //===----------------------------------------------------------------------===//
1030
1031 //===----------------------------------------------------------------------===//
1032 // Double -> Float Shrinking Optimizations for Unary Functions like 'floor'
1033
1034 struct UnaryDoubleFPOpt : public LibCallOptimization {
1035   bool CheckRetType;
1036   UnaryDoubleFPOpt(bool CheckReturnType): CheckRetType(CheckReturnType) {}
1037   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1038     FunctionType *FT = Callee->getFunctionType();
1039     if (FT->getNumParams() != 1 || !FT->getReturnType()->isDoubleTy() ||
1040         !FT->getParamType(0)->isDoubleTy())
1041       return 0;
1042
1043     if (CheckRetType) {
1044       // Check if all the uses for function like 'sin' are converted to float.
1045       for (Value::use_iterator UseI = CI->use_begin(); UseI != CI->use_end();
1046           ++UseI) {
1047         FPTruncInst *Cast = dyn_cast<FPTruncInst>(*UseI);
1048         if (Cast == 0 || !Cast->getType()->isFloatTy())
1049           return 0;
1050       }
1051     }
1052
1053     // If this is something like 'floor((double)floatval)', convert to floorf.
1054     FPExtInst *Cast = dyn_cast<FPExtInst>(CI->getArgOperand(0));
1055     if (Cast == 0 || !Cast->getOperand(0)->getType()->isFloatTy())
1056       return 0;
1057
1058     // floor((double)floatval) -> (double)floorf(floatval)
1059     Value *V = Cast->getOperand(0);
1060     V = EmitUnaryFloatFnCall(V, Callee->getName(), B, Callee->getAttributes());
1061     return B.CreateFPExt(V, B.getDoubleTy());
1062   }
1063 };
1064
1065 struct UnsafeFPLibCallOptimization : public LibCallOptimization {
1066   bool UnsafeFPShrink;
1067   UnsafeFPLibCallOptimization(bool UnsafeFPShrink) {
1068     this->UnsafeFPShrink = UnsafeFPShrink;
1069   }
1070 };
1071
1072 struct CosOpt : public UnsafeFPLibCallOptimization {
1073   CosOpt(bool UnsafeFPShrink) : UnsafeFPLibCallOptimization(UnsafeFPShrink) {}
1074   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1075     Value *Ret = NULL;
1076     if (UnsafeFPShrink && Callee->getName() == "cos" &&
1077         TLI->has(LibFunc::cosf)) {
1078       UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
1079       Ret = UnsafeUnaryDoubleFP.callOptimizer(Callee, CI, B);
1080     }
1081
1082     FunctionType *FT = Callee->getFunctionType();
1083     // Just make sure this has 1 argument of FP type, which matches the
1084     // result type.
1085     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1086         !FT->getParamType(0)->isFloatingPointTy())
1087       return Ret;
1088
1089     // cos(-x) -> cos(x)
1090     Value *Op1 = CI->getArgOperand(0);
1091     if (BinaryOperator::isFNeg(Op1)) {
1092       BinaryOperator *BinExpr = cast<BinaryOperator>(Op1);
1093       return B.CreateCall(Callee, BinExpr->getOperand(1), "cos");
1094     }
1095     return Ret;
1096   }
1097 };
1098
1099 struct PowOpt : public UnsafeFPLibCallOptimization {
1100   PowOpt(bool UnsafeFPShrink) : UnsafeFPLibCallOptimization(UnsafeFPShrink) {}
1101   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1102     Value *Ret = NULL;
1103     if (UnsafeFPShrink && Callee->getName() == "pow" &&
1104         TLI->has(LibFunc::powf)) {
1105       UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
1106       Ret = UnsafeUnaryDoubleFP.callOptimizer(Callee, CI, B);
1107     }
1108
1109     FunctionType *FT = Callee->getFunctionType();
1110     // Just make sure this has 2 arguments of the same FP type, which match the
1111     // result type.
1112     if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) ||
1113         FT->getParamType(0) != FT->getParamType(1) ||
1114         !FT->getParamType(0)->isFloatingPointTy())
1115       return Ret;
1116
1117     Value *Op1 = CI->getArgOperand(0), *Op2 = CI->getArgOperand(1);
1118     if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) {
1119       if (Op1C->isExactlyValue(1.0))  // pow(1.0, x) -> 1.0
1120         return Op1C;
1121       if (Op1C->isExactlyValue(2.0))  // pow(2.0, x) -> exp2(x)
1122         return EmitUnaryFloatFnCall(Op2, "exp2", B, Callee->getAttributes());
1123     }
1124
1125     ConstantFP *Op2C = dyn_cast<ConstantFP>(Op2);
1126     if (Op2C == 0) return Ret;
1127
1128     if (Op2C->getValueAPF().isZero())  // pow(x, 0.0) -> 1.0
1129       return ConstantFP::get(CI->getType(), 1.0);
1130
1131     if (Op2C->isExactlyValue(0.5)) {
1132       // Expand pow(x, 0.5) to (x == -infinity ? +infinity : fabs(sqrt(x))).
1133       // This is faster than calling pow, and still handles negative zero
1134       // and negative infinity correctly.
1135       // TODO: In fast-math mode, this could be just sqrt(x).
1136       // TODO: In finite-only mode, this could be just fabs(sqrt(x)).
1137       Value *Inf = ConstantFP::getInfinity(CI->getType());
1138       Value *NegInf = ConstantFP::getInfinity(CI->getType(), true);
1139       Value *Sqrt = EmitUnaryFloatFnCall(Op1, "sqrt", B,
1140                                          Callee->getAttributes());
1141       Value *FAbs = EmitUnaryFloatFnCall(Sqrt, "fabs", B,
1142                                          Callee->getAttributes());
1143       Value *FCmp = B.CreateFCmpOEQ(Op1, NegInf);
1144       Value *Sel = B.CreateSelect(FCmp, Inf, FAbs);
1145       return Sel;
1146     }
1147
1148     if (Op2C->isExactlyValue(1.0))  // pow(x, 1.0) -> x
1149       return Op1;
1150     if (Op2C->isExactlyValue(2.0))  // pow(x, 2.0) -> x*x
1151       return B.CreateFMul(Op1, Op1, "pow2");
1152     if (Op2C->isExactlyValue(-1.0)) // pow(x, -1.0) -> 1.0/x
1153       return B.CreateFDiv(ConstantFP::get(CI->getType(), 1.0),
1154                           Op1, "powrecip");
1155     return 0;
1156   }
1157 };
1158
1159 struct Exp2Opt : public UnsafeFPLibCallOptimization {
1160   Exp2Opt(bool UnsafeFPShrink) : UnsafeFPLibCallOptimization(UnsafeFPShrink) {}
1161   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1162     Value *Ret = NULL;
1163     if (UnsafeFPShrink && Callee->getName() == "exp2" &&
1164         TLI->has(LibFunc::exp2)) {
1165       UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
1166       Ret = UnsafeUnaryDoubleFP.callOptimizer(Callee, CI, B);
1167     }
1168
1169     FunctionType *FT = Callee->getFunctionType();
1170     // Just make sure this has 1 argument of FP type, which matches the
1171     // result type.
1172     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1173         !FT->getParamType(0)->isFloatingPointTy())
1174       return Ret;
1175
1176     Value *Op = CI->getArgOperand(0);
1177     // Turn exp2(sitofp(x)) -> ldexp(1.0, sext(x))  if sizeof(x) <= 32
1178     // Turn exp2(uitofp(x)) -> ldexp(1.0, zext(x))  if sizeof(x) < 32
1179     Value *LdExpArg = 0;
1180     if (SIToFPInst *OpC = dyn_cast<SIToFPInst>(Op)) {
1181       if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() <= 32)
1182         LdExpArg = B.CreateSExt(OpC->getOperand(0), B.getInt32Ty());
1183     } else if (UIToFPInst *OpC = dyn_cast<UIToFPInst>(Op)) {
1184       if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() < 32)
1185         LdExpArg = B.CreateZExt(OpC->getOperand(0), B.getInt32Ty());
1186     }
1187
1188     if (LdExpArg) {
1189       const char *Name;
1190       if (Op->getType()->isFloatTy())
1191         Name = "ldexpf";
1192       else if (Op->getType()->isDoubleTy())
1193         Name = "ldexp";
1194       else
1195         Name = "ldexpl";
1196
1197       Constant *One = ConstantFP::get(*Context, APFloat(1.0f));
1198       if (!Op->getType()->isFloatTy())
1199         One = ConstantExpr::getFPExtend(One, Op->getType());
1200
1201       Module *M = Caller->getParent();
1202       Value *Callee = M->getOrInsertFunction(Name, Op->getType(),
1203                                              Op->getType(),
1204                                              B.getInt32Ty(), NULL);
1205       CallInst *CI = B.CreateCall2(Callee, One, LdExpArg);
1206       if (const Function *F = dyn_cast<Function>(Callee->stripPointerCasts()))
1207         CI->setCallingConv(F->getCallingConv());
1208
1209       return CI;
1210     }
1211     return Ret;
1212   }
1213 };
1214
1215 } // End anonymous namespace.
1216
1217 namespace llvm {
1218
1219 class LibCallSimplifierImpl {
1220   const DataLayout *TD;
1221   const TargetLibraryInfo *TLI;
1222   const LibCallSimplifier *LCS;
1223   bool UnsafeFPShrink;
1224   StringMap<LibCallOptimization*> Optimizations;
1225
1226   // Fortified library call optimizations.
1227   MemCpyChkOpt MemCpyChk;
1228   MemMoveChkOpt MemMoveChk;
1229   MemSetChkOpt MemSetChk;
1230   StrCpyChkOpt StrCpyChk;
1231   StpCpyChkOpt StpCpyChk;
1232   StrNCpyChkOpt StrNCpyChk;
1233
1234   // String library call optimizations.
1235   StrCatOpt StrCat;
1236   StrNCatOpt StrNCat;
1237   StrChrOpt StrChr;
1238   StrRChrOpt StrRChr;
1239   StrCmpOpt StrCmp;
1240   StrNCmpOpt StrNCmp;
1241   StrCpyOpt StrCpy;
1242   StpCpyOpt StpCpy;
1243   StrNCpyOpt StrNCpy;
1244   StrLenOpt StrLen;
1245   StrPBrkOpt StrPBrk;
1246   StrToOpt StrTo;
1247   StrSpnOpt StrSpn;
1248   StrCSpnOpt StrCSpn;
1249   StrStrOpt StrStr;
1250
1251   // Memory library call optimizations.
1252   MemCmpOpt MemCmp;
1253   MemCpyOpt MemCpy;
1254   MemMoveOpt MemMove;
1255   MemSetOpt MemSet;
1256
1257   // Math library call optimizations.
1258   UnaryDoubleFPOpt UnaryDoubleFP, UnsafeUnaryDoubleFP;
1259   CosOpt Cos; PowOpt Pow; Exp2Opt Exp2;
1260
1261   void initOptimizations();
1262   void addOpt(LibFunc::Func F, LibCallOptimization* Opt);
1263   void addOpt(LibFunc::Func F1, LibFunc::Func F2, LibCallOptimization* Opt);
1264 public:
1265   LibCallSimplifierImpl(const DataLayout *TD, const TargetLibraryInfo *TLI,
1266                         const LibCallSimplifier *LCS,
1267                         bool UnsafeFPShrink = false)
1268     : UnaryDoubleFP(false), UnsafeUnaryDoubleFP(true),
1269       Cos(UnsafeFPShrink), Pow(UnsafeFPShrink), Exp2(UnsafeFPShrink) {
1270     this->TD = TD;
1271     this->TLI = TLI;
1272     this->LCS = LCS;
1273     this->UnsafeFPShrink = UnsafeFPShrink;
1274   }
1275
1276   Value *optimizeCall(CallInst *CI);
1277 };
1278
1279 void LibCallSimplifierImpl::initOptimizations() {
1280   // Fortified library call optimizations.
1281   Optimizations["__memcpy_chk"] = &MemCpyChk;
1282   Optimizations["__memmove_chk"] = &MemMoveChk;
1283   Optimizations["__memset_chk"] = &MemSetChk;
1284   Optimizations["__strcpy_chk"] = &StrCpyChk;
1285   Optimizations["__stpcpy_chk"] = &StpCpyChk;
1286   Optimizations["__strncpy_chk"] = &StrNCpyChk;
1287   Optimizations["__stpncpy_chk"] = &StrNCpyChk;
1288
1289   // String library call optimizations.
1290   addOpt(LibFunc::strcat, &StrCat);
1291   addOpt(LibFunc::strncat, &StrNCat);
1292   addOpt(LibFunc::strchr, &StrChr);
1293   addOpt(LibFunc::strrchr, &StrRChr);
1294   addOpt(LibFunc::strcmp, &StrCmp);
1295   addOpt(LibFunc::strncmp, &StrNCmp);
1296   addOpt(LibFunc::strcpy, &StrCpy);
1297   addOpt(LibFunc::stpcpy, &StpCpy);
1298   addOpt(LibFunc::strncpy, &StrNCpy);
1299   addOpt(LibFunc::strlen, &StrLen);
1300   addOpt(LibFunc::strpbrk, &StrPBrk);
1301   addOpt(LibFunc::strtol, &StrTo);
1302   addOpt(LibFunc::strtod, &StrTo);
1303   addOpt(LibFunc::strtof, &StrTo);
1304   addOpt(LibFunc::strtoul, &StrTo);
1305   addOpt(LibFunc::strtoll, &StrTo);
1306   addOpt(LibFunc::strtold, &StrTo);
1307   addOpt(LibFunc::strtoull, &StrTo);
1308   addOpt(LibFunc::strspn, &StrSpn);
1309   addOpt(LibFunc::strcspn, &StrCSpn);
1310   addOpt(LibFunc::strstr, &StrStr);
1311
1312   // Memory library call optimizations.
1313   addOpt(LibFunc::memcmp, &MemCmp);
1314   addOpt(LibFunc::memcpy, &MemCpy);
1315   addOpt(LibFunc::memmove, &MemMove);
1316   addOpt(LibFunc::memset, &MemSet);
1317
1318   // Math library call optimizations.
1319   addOpt(LibFunc::ceil, LibFunc::ceilf, &UnaryDoubleFP);
1320   addOpt(LibFunc::fabs, LibFunc::fabsf, &UnaryDoubleFP);
1321   addOpt(LibFunc::floor, LibFunc::floorf, &UnaryDoubleFP);
1322   addOpt(LibFunc::rint, LibFunc::rintf, &UnaryDoubleFP);
1323   addOpt(LibFunc::round, LibFunc::roundf, &UnaryDoubleFP);
1324   addOpt(LibFunc::nearbyint, LibFunc::nearbyintf, &UnaryDoubleFP);
1325   addOpt(LibFunc::trunc, LibFunc::truncf, &UnaryDoubleFP);
1326
1327   if(UnsafeFPShrink) {
1328     addOpt(LibFunc::acos, LibFunc::acosf, &UnsafeUnaryDoubleFP);
1329     addOpt(LibFunc::acosh, LibFunc::acoshf, &UnsafeUnaryDoubleFP);
1330     addOpt(LibFunc::asin, LibFunc::asinf, &UnsafeUnaryDoubleFP);
1331     addOpt(LibFunc::asinh, LibFunc::asinhf, &UnsafeUnaryDoubleFP);
1332     addOpt(LibFunc::atan, LibFunc::atanf, &UnsafeUnaryDoubleFP);
1333     addOpt(LibFunc::atanh, LibFunc::atanhf, &UnsafeUnaryDoubleFP);
1334     addOpt(LibFunc::cbrt, LibFunc::cbrtf, &UnsafeUnaryDoubleFP);
1335     addOpt(LibFunc::cosh, LibFunc::coshf, &UnsafeUnaryDoubleFP);
1336     addOpt(LibFunc::exp, LibFunc::expf, &UnsafeUnaryDoubleFP);
1337     addOpt(LibFunc::exp10, LibFunc::exp10f, &UnsafeUnaryDoubleFP);
1338     addOpt(LibFunc::expm1, LibFunc::expm1f, &UnsafeUnaryDoubleFP);
1339     addOpt(LibFunc::log, LibFunc::logf, &UnsafeUnaryDoubleFP);
1340     addOpt(LibFunc::log10, LibFunc::log10f, &UnsafeUnaryDoubleFP);
1341     addOpt(LibFunc::log1p, LibFunc::log1pf, &UnsafeUnaryDoubleFP);
1342     addOpt(LibFunc::log2, LibFunc::log2f, &UnsafeUnaryDoubleFP);
1343     addOpt(LibFunc::logb, LibFunc::logbf, &UnsafeUnaryDoubleFP);
1344     addOpt(LibFunc::sin, LibFunc::sinf, &UnsafeUnaryDoubleFP);
1345     addOpt(LibFunc::sinh, LibFunc::sinhf, &UnsafeUnaryDoubleFP);
1346     addOpt(LibFunc::sqrt, LibFunc::sqrtf, &UnsafeUnaryDoubleFP);
1347     addOpt(LibFunc::tan, LibFunc::tanf, &UnsafeUnaryDoubleFP);
1348     addOpt(LibFunc::tanh, LibFunc::tanhf, &UnsafeUnaryDoubleFP);
1349   }
1350
1351   addOpt(LibFunc::cosf, &Cos);
1352   addOpt(LibFunc::cos, &Cos);
1353   addOpt(LibFunc::cosl, &Cos);
1354   addOpt(LibFunc::powf, &Pow);
1355   addOpt(LibFunc::pow, &Pow);
1356   addOpt(LibFunc::powl, &Pow);
1357   Optimizations["llvm.pow.f32"] = &Pow;
1358   Optimizations["llvm.pow.f64"] = &Pow;
1359   Optimizations["llvm.pow.f80"] = &Pow;
1360   Optimizations["llvm.pow.f128"] = &Pow;
1361   Optimizations["llvm.pow.ppcf128"] = &Pow;
1362   addOpt(LibFunc::exp2l, &Exp2);
1363   addOpt(LibFunc::exp2, &Exp2);
1364   addOpt(LibFunc::exp2f, &Exp2);
1365   Optimizations["llvm.exp2.ppcf128"] = &Exp2;
1366   Optimizations["llvm.exp2.f128"] = &Exp2;
1367   Optimizations["llvm.exp2.f80"] = &Exp2;
1368   Optimizations["llvm.exp2.f64"] = &Exp2;
1369   Optimizations["llvm.exp2.f32"] = &Exp2;
1370 }
1371
1372 Value *LibCallSimplifierImpl::optimizeCall(CallInst *CI) {
1373   if (Optimizations.empty())
1374     initOptimizations();
1375
1376   Function *Callee = CI->getCalledFunction();
1377   LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
1378   if (LCO) {
1379     IRBuilder<> Builder(CI);
1380     return LCO->optimizeCall(CI, TD, TLI, LCS, Builder);
1381   }
1382   return 0;
1383 }
1384
1385 void LibCallSimplifierImpl::addOpt(LibFunc::Func F, LibCallOptimization* Opt) {
1386   if (TLI->has(F))
1387     Optimizations[TLI->getName(F)] = Opt;
1388 }
1389
1390 void LibCallSimplifierImpl::addOpt(LibFunc::Func F1, LibFunc::Func F2,
1391                                    LibCallOptimization* Opt) {
1392   if (TLI->has(F1) && TLI->has(F2))
1393     Optimizations[TLI->getName(F1)] = Opt;
1394 }
1395
1396 LibCallSimplifier::LibCallSimplifier(const DataLayout *TD,
1397                                      const TargetLibraryInfo *TLI,
1398                                      bool UnsafeFPShrink) {
1399   Impl = new LibCallSimplifierImpl(TD, TLI, this, UnsafeFPShrink);
1400 }
1401
1402 LibCallSimplifier::~LibCallSimplifier() {
1403   delete Impl;
1404 }
1405
1406 Value *LibCallSimplifier::optimizeCall(CallInst *CI) {
1407   return Impl->optimizeCall(CI);
1408 }
1409
1410 void LibCallSimplifier::replaceAllUsesWith(Instruction *I, Value *With) const {
1411   I->replaceAllUsesWith(With);
1412   I->eraseFromParent();
1413 }
1414
1415 }