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