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