lib/Transforms/Utils/SimplifyLibCalls.cpp

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