lib/Transforms/Utils/SimplifyLibCalls.cpp

   1 //===------ SimplifyLibCalls.cpp - Library calls simplifier ---------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This is a utility pass used for testing the InstructionSimplify analysis.
  11 // The analysis is applied to every instruction, and if it simplifies then the
  12 // instruction is replaced by the simplification.  If you are looking for a pass
  13 // that performs serious instruction folding, use the instcombine pass instead.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/Transforms/Utils/SimplifyLibCalls.h"
  18 #include "llvm/DataLayout.h"
  19 #include "llvm/ADT/StringMap.h"
  20 #include "llvm/Analysis/ValueTracking.h"
  21 #include "llvm/Function.h"
  22 #include "llvm/IRBuilder.h"
  23 #include "llvm/LLVMContext.h"
  24 #include "llvm/Target/TargetLibraryInfo.h"
  25 #include "llvm/Transforms/Utils/BuildLibCalls.h"
  26
  27 using namespace llvm;
  28
  29 /// This class is the abstract base class for the set of optimizations that
  30 /// corresponds to one library call.
  31 namespace {
  32 class LibCallOptimization {
  33 protected:
  34   Function *Caller;
  35   const DataLayout *TD;
  36   const TargetLibraryInfo *TLI;
  37   const LibCallSimplifier *LCS;
  38   LLVMContext* Context;
  39 public:
  40   LibCallOptimization() { }
  41   virtual ~LibCallOptimization() {}
  42
  43   /// callOptimizer - This pure virtual method is implemented by base classes to
  44   /// do various optimizations.  If this returns null then no transformation was
  45   /// performed.  If it returns CI, then it transformed the call and CI is to be
  46   /// deleted.  If it returns something else, replace CI with the new value and
  47   /// delete CI.
  48   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B)
  49     =0;
  50
  51   Value *optimizeCall(CallInst *CI, const DataLayout *TD,
  52                       const TargetLibraryInfo *TLI,
  53                       const LibCallSimplifier *LCS, IRBuilder<> &B) {
  54     Caller = CI->getParent()->getParent();
  55     this->TD = TD;
  56     this->TLI = TLI;
  57     this->LCS = LCS;
  58     if (CI->getCalledFunction())
  59       Context = &CI->getCalledFunction()->getContext();
  60
  61     // We never change the calling convention.
  62     if (CI->getCallingConv() != llvm::CallingConv::C)
  63       return NULL;
  64
  65     return callOptimizer(CI->getCalledFunction(), CI, B);
  66   }
  67 };
  68
  69 //===----------------------------------------------------------------------===//
  70 // Helper Functions
  71 //===----------------------------------------------------------------------===//
  72
  73 /// isOnlyUsedInZeroEqualityComparison - Return true if it only matters that the
  74 /// value is equal or not-equal to zero.
  75 static bool isOnlyUsedInZeroEqualityComparison(Value *V) {
  76   for (Value::use_iterator UI = V->use_begin(), E = V->use_end();
  77        UI != E; ++UI) {
  78     if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI))
  79       if (IC->isEquality())
  80         if (Constant *C = dyn_cast<Constant>(IC->getOperand(1)))
  81           if (C->isNullValue())
  82             continue;
  83     // Unknown instruction.
  84     return false;
  85   }
  86   return true;
  87 }
  88
  89 /// isOnlyUsedInEqualityComparison - Return true if it is only used in equality
  90 /// comparisons with With.
  91 static bool isOnlyUsedInEqualityComparison(Value *V, Value *With) {
  92   for (Value::use_iterator UI = V->use_begin(), E = V->use_end();
  93        UI != E; ++UI) {
  94     if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI))
  95       if (IC->isEquality() && IC->getOperand(1) == With)
  96         continue;
  97     // Unknown instruction.
  98     return false;
  99   }
 100   return true;
 101 }
 102
 103 //===----------------------------------------------------------------------===//
 104 // Fortified Library Call Optimizations
 105 //===----------------------------------------------------------------------===//
 106
 107 struct FortifiedLibCallOptimization : public LibCallOptimization {
 108 protected:
 109   virtual bool isFoldable(unsigned SizeCIOp, unsigned SizeArgOp,
 110                           bool isString) const = 0;
 111 };
 112
 113 struct InstFortifiedLibCallOptimization : public FortifiedLibCallOptimization {
 114   CallInst *CI;
 115
 116   bool isFoldable(unsigned SizeCIOp, unsigned SizeArgOp, bool isString) const {
 117     if (CI->getArgOperand(SizeCIOp) == CI->getArgOperand(SizeArgOp))
 118       return true;
 119     if (ConstantInt *SizeCI =
 120                            dyn_cast<ConstantInt>(CI->getArgOperand(SizeCIOp))) {
 121       if (SizeCI->isAllOnesValue())
 122         return true;
 123       if (isString) {
 124         uint64_t Len = GetStringLength(CI->getArgOperand(SizeArgOp));
 125         // If the length is 0 we don't know how long it is and so we can't
 126         // remove the check.
 127         if (Len == 0) return false;
 128         return SizeCI->getZExtValue() >= Len;
 129       }
 130       if (ConstantInt *Arg = dyn_cast<ConstantInt>(
 131                                                   CI->getArgOperand(SizeArgOp)))
 132         return SizeCI->getZExtValue() >= Arg->getZExtValue();
 133     }
 134     return false;
 135   }
 136 };
 137
 138 struct MemCpyChkOpt : public InstFortifiedLibCallOptimization {
 139   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 140     this->CI = CI;
 141     FunctionType *FT = Callee->getFunctionType();
 142     LLVMContext &Context = CI->getParent()->getContext();
 143
 144     // Check if this has the right signature.
 145     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 146         !FT->getParamType(0)->isPointerTy() ||
 147         !FT->getParamType(1)->isPointerTy() ||
 148         FT->getParamType(2) != TD->getIntPtrType(Context) ||
 149         FT->getParamType(3) != TD->getIntPtrType(Context))
 150       return 0;
 151
 152     if (isFoldable(3, 2, false)) {
 153       B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
 154                      CI->getArgOperand(2), 1);
 155       return CI->getArgOperand(0);
 156     }
 157     return 0;
 158   }
 159 };
 160
 161 struct MemMoveChkOpt : public InstFortifiedLibCallOptimization {
 162   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 163     this->CI = CI;
 164     FunctionType *FT = Callee->getFunctionType();
 165     LLVMContext &Context = CI->getParent()->getContext();
 166
 167     // Check if this has the right signature.
 168     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 169         !FT->getParamType(0)->isPointerTy() ||
 170         !FT->getParamType(1)->isPointerTy() ||
 171         FT->getParamType(2) != TD->getIntPtrType(Context) ||
 172         FT->getParamType(3) != TD->getIntPtrType(Context))
 173       return 0;
 174
 175     if (isFoldable(3, 2, false)) {
 176       B.CreateMemMove(CI->getArgOperand(0), CI->getArgOperand(1),
 177                       CI->getArgOperand(2), 1);
 178       return CI->getArgOperand(0);
 179     }
 180     return 0;
 181   }
 182 };
 183
 184 struct MemSetChkOpt : public InstFortifiedLibCallOptimization {
 185   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 186     this->CI = CI;
 187     FunctionType *FT = Callee->getFunctionType();
 188     LLVMContext &Context = CI->getParent()->getContext();
 189
 190     // Check if this has the right signature.
 191     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 192         !FT->getParamType(0)->isPointerTy() ||
 193         !FT->getParamType(1)->isIntegerTy() ||
 194         FT->getParamType(2) != TD->getIntPtrType(Context) ||
 195         FT->getParamType(3) != TD->getIntPtrType(Context))
 196       return 0;
 197
 198     if (isFoldable(3, 2, false)) {
 199       Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(),
 200                                    false);
 201       B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1);
 202       return CI->getArgOperand(0);
 203     }
 204     return 0;
 205   }
 206 };
 207
 208 struct StrCpyChkOpt : public InstFortifiedLibCallOptimization {
 209   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 210     this->CI = CI;
 211     StringRef Name = Callee->getName();
 212     FunctionType *FT = Callee->getFunctionType();
 213     LLVMContext &Context = CI->getParent()->getContext();
 214
 215     // Check if this has the right signature.
 216     if (FT->getNumParams() != 3 ||
 217         FT->getReturnType() != FT->getParamType(0) ||
 218         FT->getParamType(0) != FT->getParamType(1) ||
 219         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
 220         FT->getParamType(2) != TD->getIntPtrType(Context))
 221       return 0;
 222
 223     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 224     if (Dst == Src)      // __strcpy_chk(x,x)  -> x
 225       return Src;
 226
 227     // If a) we don't have any length information, or b) we know this will
 228     // fit then just lower to a plain strcpy. Otherwise we'll keep our
 229     // strcpy_chk call which may fail at runtime if the size is too long.
 230     // TODO: It might be nice to get a maximum length out of the possible
 231     // string lengths for varying.
 232     if (isFoldable(2, 1, true)) {
 233       Value *Ret = EmitStrCpy(Dst, Src, B, TD, TLI, Name.substr(2, 6));
 234       return Ret;
 235     } else {
 236       // Maybe we can stil fold __strcpy_chk to __memcpy_chk.
 237       uint64_t Len = GetStringLength(Src);
 238       if (Len == 0) return 0;
 239
 240       // This optimization require DataLayout.
 241       if (!TD) return 0;
 242
 243       Value *Ret =
 244         EmitMemCpyChk(Dst, Src,
 245                       ConstantInt::get(TD->getIntPtrType(Context), Len),
 246                       CI->getArgOperand(2), B, TD, TLI);
 247       return Ret;
 248     }
 249     return 0;
 250   }
 251 };
 252
 253 struct StpCpyChkOpt : public InstFortifiedLibCallOptimization {
 254   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 255     this->CI = CI;
 256     StringRef Name = Callee->getName();
 257     FunctionType *FT = Callee->getFunctionType();
 258     LLVMContext &Context = CI->getParent()->getContext();
 259
 260     // Check if this has the right signature.
 261     if (FT->getNumParams() != 3 ||
 262         FT->getReturnType() != FT->getParamType(0) ||
 263         FT->getParamType(0) != FT->getParamType(1) ||
 264         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
 265         FT->getParamType(2) != TD->getIntPtrType(FT->getParamType(0)))
 266       return 0;
 267
 268     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 269     if (Dst == Src) {  // stpcpy(x,x)  -> x+strlen(x)
 270       Value *StrLen = EmitStrLen(Src, B, TD, TLI);
 271       return StrLen ? B.CreateInBoundsGEP(Dst, StrLen) : 0;
 272     }
 273
 274     // If a) we don't have any length information, or b) we know this will
 275     // fit then just lower to a plain stpcpy. Otherwise we'll keep our
 276     // stpcpy_chk call which may fail at runtime if the size is too long.
 277     // TODO: It might be nice to get a maximum length out of the possible
 278     // string lengths for varying.
 279     if (isFoldable(2, 1, true)) {
 280       Value *Ret = EmitStrCpy(Dst, Src, B, TD, TLI, Name.substr(2, 6));
 281       return Ret;
 282     } else {
 283       // Maybe we can stil fold __stpcpy_chk to __memcpy_chk.
 284       uint64_t Len = GetStringLength(Src);
 285       if (Len == 0) return 0;
 286
 287       // This optimization require DataLayout.
 288       if (!TD) return 0;
 289
 290       Type *PT = FT->getParamType(0);
 291       Value *LenV = ConstantInt::get(TD->getIntPtrType(PT), Len);
 292       Value *DstEnd = B.CreateGEP(Dst,
 293                                   ConstantInt::get(TD->getIntPtrType(PT),
 294                                                    Len - 1));
 295       if (!EmitMemCpyChk(Dst, Src, LenV, CI->getArgOperand(2), B, TD, TLI))
 296         return 0;
 297       return DstEnd;
 298     }
 299     return 0;
 300   }
 301 };
 302
 303 struct StrNCpyChkOpt : public InstFortifiedLibCallOptimization {
 304   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 305     this->CI = CI;
 306     StringRef Name = Callee->getName();
 307     FunctionType *FT = Callee->getFunctionType();
 308     LLVMContext &Context = CI->getParent()->getContext();
 309
 310     // Check if this has the right signature.
 311     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 312         FT->getParamType(0) != FT->getParamType(1) ||
 313         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
 314         !FT->getParamType(2)->isIntegerTy() ||
 315         FT->getParamType(3) != TD->getIntPtrType(Context))
 316       return 0;
 317
 318     if (isFoldable(3, 2, false)) {
 319       Value *Ret = EmitStrNCpy(CI->getArgOperand(0), CI->getArgOperand(1),
 320                                CI->getArgOperand(2), B, TD, TLI,
 321                                Name.substr(2, 7));
 322       return Ret;
 323     }
 324     return 0;
 325   }
 326 };
 327
 328 //===----------------------------------------------------------------------===//
 329 // String and Memory Library Call Optimizations
 330 //===----------------------------------------------------------------------===//
 331
 332 struct StrCatOpt : public LibCallOptimization {
 333   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 334     // Verify the "strcat" function prototype.
 335     FunctionType *FT = Callee->getFunctionType();
 336     if (FT->getNumParams() != 2 ||
 337         FT->getReturnType() != B.getInt8PtrTy() ||
 338         FT->getParamType(0) != FT->getReturnType() ||
 339         FT->getParamType(1) != FT->getReturnType())
 340       return 0;
 341
 342     // Extract some information from the instruction
 343     Value *Dst = CI->getArgOperand(0);
 344     Value *Src = CI->getArgOperand(1);
 345
 346     // See if we can get the length of the input string.
 347     uint64_t Len = GetStringLength(Src);
 348     if (Len == 0) return 0;
 349     --Len;  // Unbias length.
 350
 351     // Handle the simple, do-nothing case: strcat(x, "") -> x
 352     if (Len == 0)
 353       return Dst;
 354
 355     // These optimizations require DataLayout.
 356     if (!TD) return 0;
 357
 358     return emitStrLenMemCpy(Src, Dst, Len, B);
 359   }
 360
 361   Value *emitStrLenMemCpy(Value *Src, Value *Dst, uint64_t Len,
 362                           IRBuilder<> &B) {
 363     // We need to find the end of the destination string.  That's where the
 364     // memory is to be moved to. We just generate a call to strlen.
 365     Value *DstLen = EmitStrLen(Dst, B, TD, TLI);
 366     if (!DstLen)
 367       return 0;
 368
 369     // Now that we have the destination's length, we must index into the
 370     // destination's pointer to get the actual memcpy destination (end of
 371     // the string .. we're concatenating).
 372     Value *CpyDst = B.CreateGEP(Dst, DstLen, "endptr");
 373
 374     // We have enough information to now generate the memcpy call to do the
 375     // concatenation for us.  Make a memcpy to copy the nul byte with align = 1.
 376     B.CreateMemCpy(CpyDst, Src,
 377                    ConstantInt::get(TD->getIntPtrType(*Context), Len + 1), 1);
 378     return Dst;
 379   }
 380 };
 381
 382 struct StrNCatOpt : public StrCatOpt {
 383   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 384     // Verify the "strncat" function prototype.
 385     FunctionType *FT = Callee->getFunctionType();
 386     if (FT->getNumParams() != 3 ||
 387         FT->getReturnType() != B.getInt8PtrTy() ||
 388         FT->getParamType(0) != FT->getReturnType() ||
 389         FT->getParamType(1) != FT->getReturnType() ||
 390         !FT->getParamType(2)->isIntegerTy())
 391       return 0;
 392
 393     // Extract some information from the instruction
 394     Value *Dst = CI->getArgOperand(0);
 395     Value *Src = CI->getArgOperand(1);
 396     uint64_t Len;
 397
 398     // We don't do anything if length is not constant
 399     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
 400       Len = LengthArg->getZExtValue();
 401     else
 402       return 0;
 403
 404     // See if we can get the length of the input string.
 405     uint64_t SrcLen = GetStringLength(Src);
 406     if (SrcLen == 0) return 0;
 407     --SrcLen;  // Unbias length.
 408
 409     // Handle the simple, do-nothing cases:
 410     // strncat(x, "", c) -> x
 411     // strncat(x,  c, 0) -> x
 412     if (SrcLen == 0 || Len == 0) return Dst;
 413
 414     // These optimizations require DataLayout.
 415     if (!TD) return 0;
 416
 417     // We don't optimize this case
 418     if (Len < SrcLen) return 0;
 419
 420     // strncat(x, s, c) -> strcat(x, s)
 421     // s is constant so the strcat can be optimized further
 422     return emitStrLenMemCpy(Src, Dst, SrcLen, B);
 423   }
 424 };
 425
 426 struct StrChrOpt : public LibCallOptimization {
 427   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 428     // Verify the "strchr" function prototype.
 429     FunctionType *FT = Callee->getFunctionType();
 430     if (FT->getNumParams() != 2 ||
 431         FT->getReturnType() != B.getInt8PtrTy() ||
 432         FT->getParamType(0) != FT->getReturnType() ||
 433         !FT->getParamType(1)->isIntegerTy(32))
 434       return 0;
 435
 436     Value *SrcStr = CI->getArgOperand(0);
 437
 438     // If the second operand is non-constant, see if we can compute the length
 439     // of the input string and turn this into memchr.
 440     ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
 441     if (CharC == 0) {
 442       // These optimizations require DataLayout.
 443       if (!TD) return 0;
 444
 445       uint64_t Len = GetStringLength(SrcStr);
 446       if (Len == 0 || !FT->getParamType(1)->isIntegerTy(32))// memchr needs i32.
 447         return 0;
 448
 449       return EmitMemChr(SrcStr, CI->getArgOperand(1), // include nul.
 450                         ConstantInt::get(TD->getIntPtrType(*Context), Len),
 451                         B, TD, TLI);
 452     }
 453
 454     // Otherwise, the character is a constant, see if the first argument is
 455     // a string literal.  If so, we can constant fold.
 456     StringRef Str;
 457     if (!getConstantStringInfo(SrcStr, Str))
 458       return 0;
 459
 460     // Compute the offset, make sure to handle the case when we're searching for
 461     // zero (a weird way to spell strlen).
 462     size_t I = CharC->getSExtValue() == 0 ?
 463         Str.size() : Str.find(CharC->getSExtValue());
 464     if (I == StringRef::npos) // Didn't find the char.  strchr returns null.
 465       return Constant::getNullValue(CI->getType());
 466
 467     // strchr(s+n,c)  -> gep(s+n+i,c)
 468     return B.CreateGEP(SrcStr, B.getInt64(I), "strchr");
 469   }
 470 };
 471
 472 struct StrRChrOpt : public LibCallOptimization {
 473   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 474     // Verify the "strrchr" function prototype.
 475     FunctionType *FT = Callee->getFunctionType();
 476     if (FT->getNumParams() != 2 ||
 477         FT->getReturnType() != B.getInt8PtrTy() ||
 478         FT->getParamType(0) != FT->getReturnType() ||
 479         !FT->getParamType(1)->isIntegerTy(32))
 480       return 0;
 481
 482     Value *SrcStr = CI->getArgOperand(0);
 483     ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
 484
 485     // Cannot fold anything if we're not looking for a constant.
 486     if (!CharC)
 487       return 0;
 488
 489     StringRef Str;
 490     if (!getConstantStringInfo(SrcStr, Str)) {
 491       // strrchr(s, 0) -> strchr(s, 0)
 492       if (TD && CharC->isZero())
 493         return EmitStrChr(SrcStr, '\0', B, TD, TLI);
 494       return 0;
 495     }
 496
 497     // Compute the offset.
 498     size_t I = CharC->getSExtValue() == 0 ?
 499         Str.size() : Str.rfind(CharC->getSExtValue());
 500     if (I == StringRef::npos) // Didn't find the char. Return null.
 501       return Constant::getNullValue(CI->getType());
 502
 503     // strrchr(s+n,c) -> gep(s+n+i,c)
 504     return B.CreateGEP(SrcStr, B.getInt64(I), "strrchr");
 505   }
 506 };
 507
 508 struct StrCmpOpt : public LibCallOptimization {
 509   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 510     // Verify the "strcmp" function prototype.
 511     FunctionType *FT = Callee->getFunctionType();
 512     if (FT->getNumParams() != 2 ||
 513         !FT->getReturnType()->isIntegerTy(32) ||
 514         FT->getParamType(0) != FT->getParamType(1) ||
 515         FT->getParamType(0) != B.getInt8PtrTy())
 516       return 0;
 517
 518     Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
 519     if (Str1P == Str2P)      // strcmp(x,x)  -> 0
 520       return ConstantInt::get(CI->getType(), 0);
 521
 522     StringRef Str1, Str2;
 523     bool HasStr1 = getConstantStringInfo(Str1P, Str1);
 524     bool HasStr2 = getConstantStringInfo(Str2P, Str2);
 525
 526     // strcmp(x, y)  -> cnst  (if both x and y are constant strings)
 527     if (HasStr1 && HasStr2)
 528       return ConstantInt::get(CI->getType(), Str1.compare(Str2));
 529
 530     if (HasStr1 && Str1.empty()) // strcmp("", x) -> -*x
 531       return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"),
 532                                       CI->getType()));
 533
 534     if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x
 535       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
 536
 537     // strcmp(P, "x") -> memcmp(P, "x", 2)
 538     uint64_t Len1 = GetStringLength(Str1P);
 539     uint64_t Len2 = GetStringLength(Str2P);
 540     if (Len1 && Len2) {
 541       // These optimizations require DataLayout.
 542       if (!TD) return 0;
 543
 544       return EmitMemCmp(Str1P, Str2P,
 545                         ConstantInt::get(TD->getIntPtrType(*Context),
 546                         std::min(Len1, Len2)), B, TD, TLI);
 547     }
 548
 549     return 0;
 550   }
 551 };
 552
 553 struct StrNCmpOpt : public LibCallOptimization {
 554   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 555     // Verify the "strncmp" function prototype.
 556     FunctionType *FT = Callee->getFunctionType();
 557     if (FT->getNumParams() != 3 ||
 558         !FT->getReturnType()->isIntegerTy(32) ||
 559         FT->getParamType(0) != FT->getParamType(1) ||
 560         FT->getParamType(0) != B.getInt8PtrTy() ||
 561         !FT->getParamType(2)->isIntegerTy())
 562       return 0;
 563
 564     Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
 565     if (Str1P == Str2P)      // strncmp(x,x,n)  -> 0
 566       return ConstantInt::get(CI->getType(), 0);
 567
 568     // Get the length argument if it is constant.
 569     uint64_t Length;
 570     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
 571       Length = LengthArg->getZExtValue();
 572     else
 573       return 0;
 574
 575     if (Length == 0) // strncmp(x,y,0)   -> 0
 576       return ConstantInt::get(CI->getType(), 0);
 577
 578     if (TD && Length == 1) // strncmp(x,y,1) -> memcmp(x,y,1)
 579       return EmitMemCmp(Str1P, Str2P, CI->getArgOperand(2), B, TD, TLI);
 580
 581     StringRef Str1, Str2;
 582     bool HasStr1 = getConstantStringInfo(Str1P, Str1);
 583     bool HasStr2 = getConstantStringInfo(Str2P, Str2);
 584
 585     // strncmp(x, y)  -> cnst  (if both x and y are constant strings)
 586     if (HasStr1 && HasStr2) {
 587       StringRef SubStr1 = Str1.substr(0, Length);
 588       StringRef SubStr2 = Str2.substr(0, Length);
 589       return ConstantInt::get(CI->getType(), SubStr1.compare(SubStr2));
 590     }
 591
 592     if (HasStr1 && Str1.empty())  // strncmp("", x, n) -> -*x
 593       return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"),
 594                                       CI->getType()));
 595
 596     if (HasStr2 && Str2.empty())  // strncmp(x, "", n) -> *x
 597       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
 598
 599     return 0;
 600   }
 601 };
 602
 603 struct StrCpyOpt : public LibCallOptimization {
 604   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 605     // Verify the "strcpy" function prototype.
 606     FunctionType *FT = Callee->getFunctionType();
 607     if (FT->getNumParams() != 2 ||
 608         FT->getReturnType() != FT->getParamType(0) ||
 609         FT->getParamType(0) != FT->getParamType(1) ||
 610         FT->getParamType(0) != B.getInt8PtrTy())
 611       return 0;
 612
 613     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 614     if (Dst == Src)      // strcpy(x,x)  -> x
 615       return Src;
 616
 617     // These optimizations require DataLayout.
 618     if (!TD) return 0;
 619
 620     // See if we can get the length of the input string.
 621     uint64_t Len = GetStringLength(Src);
 622     if (Len == 0) return 0;
 623
 624     // We have enough information to now generate the memcpy call to do the
 625     // copy for us.  Make a memcpy to copy the nul byte with align = 1.
 626     B.CreateMemCpy(Dst, Src,
 627                    ConstantInt::get(TD->getIntPtrType(*Context), Len), 1);
 628     return Dst;
 629   }
 630 };
 631
 632 struct StpCpyOpt: public LibCallOptimization {
 633   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 634     // Verify the "stpcpy" function prototype.
 635     FunctionType *FT = Callee->getFunctionType();
 636     if (FT->getNumParams() != 2 ||
 637         FT->getReturnType() != FT->getParamType(0) ||
 638         FT->getParamType(0) != FT->getParamType(1) ||
 639         FT->getParamType(0) != B.getInt8PtrTy())
 640       return 0;
 641
 642     // These optimizations require DataLayout.
 643     if (!TD) return 0;
 644
 645     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 646     if (Dst == Src) {  // stpcpy(x,x)  -> x+strlen(x)
 647       Value *StrLen = EmitStrLen(Src, B, TD, TLI);
 648       return StrLen ? B.CreateInBoundsGEP(Dst, StrLen) : 0;
 649     }
 650
 651     // See if we can get the length of the input string.
 652     uint64_t Len = GetStringLength(Src);
 653     if (Len == 0) return 0;
 654
 655     Type *PT = FT->getParamType(0);
 656     Value *LenV = ConstantInt::get(TD->getIntPtrType(PT), Len);
 657     Value *DstEnd = B.CreateGEP(Dst,
 658                                 ConstantInt::get(TD->getIntPtrType(PT),
 659                                                  Len - 1));
 660
 661     // We have enough information to now generate the memcpy call to do the
 662     // copy for us.  Make a memcpy to copy the nul byte with align = 1.
 663     B.CreateMemCpy(Dst, Src, LenV, 1);
 664     return DstEnd;
 665   }
 666 };
 667
 668 struct StrNCpyOpt : public LibCallOptimization {
 669   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 670     FunctionType *FT = Callee->getFunctionType();
 671     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 672         FT->getParamType(0) != FT->getParamType(1) ||
 673         FT->getParamType(0) != B.getInt8PtrTy() ||
 674         !FT->getParamType(2)->isIntegerTy())
 675       return 0;
 676
 677     Value *Dst = CI->getArgOperand(0);
 678     Value *Src = CI->getArgOperand(1);
 679     Value *LenOp = CI->getArgOperand(2);
 680
 681     // See if we can get the length of the input string.
 682     uint64_t SrcLen = GetStringLength(Src);
 683     if (SrcLen == 0) return 0;
 684     --SrcLen;
 685
 686     if (SrcLen == 0) {
 687       // strncpy(x, "", y) -> memset(x, '\0', y, 1)
 688       B.CreateMemSet(Dst, B.getInt8('\0'), LenOp, 1);
 689       return Dst;
 690     }
 691
 692     uint64_t Len;
 693     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(LenOp))
 694       Len = LengthArg->getZExtValue();
 695     else
 696       return 0;
 697
 698     if (Len == 0) return Dst; // strncpy(x, y, 0) -> x
 699
 700     // These optimizations require DataLayout.
 701     if (!TD) return 0;
 702
 703     // Let strncpy handle the zero padding
 704     if (Len > SrcLen+1) return 0;
 705
 706     Type *PT = FT->getParamType(0);
 707     // strncpy(x, s, c) -> memcpy(x, s, c, 1) [s and c are constant]
 708     B.CreateMemCpy(Dst, Src,
 709                    ConstantInt::get(TD->getIntPtrType(PT), Len), 1);
 710
 711     return Dst;
 712   }
 713 };
 714
 715 struct StrLenOpt : public LibCallOptimization {
 716   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 717     FunctionType *FT = Callee->getFunctionType();
 718     if (FT->getNumParams() != 1 ||
 719         FT->getParamType(0) != B.getInt8PtrTy() ||
 720         !FT->getReturnType()->isIntegerTy())
 721       return 0;
 722
 723     Value *Src = CI->getArgOperand(0);
 724
 725     // Constant folding: strlen("xyz") -> 3
 726     if (uint64_t Len = GetStringLength(Src))
 727       return ConstantInt::get(CI->getType(), Len-1);
 728
 729     // strlen(x) != 0 --> *x != 0
 730     // strlen(x) == 0 --> *x == 0
 731     if (isOnlyUsedInZeroEqualityComparison(CI))
 732       return B.CreateZExt(B.CreateLoad(Src, "strlenfirst"), CI->getType());
 733     return 0;
 734   }
 735 };
 736
 737 struct StrPBrkOpt : public LibCallOptimization {
 738   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 739     FunctionType *FT = Callee->getFunctionType();
 740     if (FT->getNumParams() != 2 ||
 741         FT->getParamType(0) != B.getInt8PtrTy() ||
 742         FT->getParamType(1) != FT->getParamType(0) ||
 743         FT->getReturnType() != FT->getParamType(0))
 744       return 0;
 745
 746     StringRef S1, S2;
 747     bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
 748     bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
 749
 750     // strpbrk(s, "") -> NULL
 751     // strpbrk("", s) -> NULL
 752     if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))
 753       return Constant::getNullValue(CI->getType());
 754
 755     // Constant folding.
 756     if (HasS1 && HasS2) {
 757       size_t I = S1.find_first_of(S2);
 758       if (I == std::string::npos) // No match.
 759         return Constant::getNullValue(CI->getType());
 760
 761       return B.CreateGEP(CI->getArgOperand(0), B.getInt64(I), "strpbrk");
 762     }
 763
 764     // strpbrk(s, "a") -> strchr(s, 'a')
 765     if (TD && HasS2 && S2.size() == 1)
 766       return EmitStrChr(CI->getArgOperand(0), S2[0], B, TD, TLI);
 767
 768     return 0;
 769   }
 770 };
 771
 772 struct StrToOpt : public LibCallOptimization {
 773   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 774     FunctionType *FT = Callee->getFunctionType();
 775     if ((FT->getNumParams() != 2 && FT->getNumParams() != 3) ||
 776         !FT->getParamType(0)->isPointerTy() ||
 777         !FT->getParamType(1)->isPointerTy())
 778       return 0;
 779
 780     Value *EndPtr = CI->getArgOperand(1);
 781     if (isa<ConstantPointerNull>(EndPtr)) {
 782       // With a null EndPtr, this function won't capture the main argument.
 783       // It would be readonly too, except that it still may write to errno.
 784       CI->addAttribute(1, Attributes::get(Callee->getContext(),
 785                                           Attributes::NoCapture));
 786     }
 787
 788     return 0;
 789   }
 790 };
 791
 792 struct StrSpnOpt : public LibCallOptimization {
 793   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 794     FunctionType *FT = Callee->getFunctionType();
 795     if (FT->getNumParams() != 2 ||
 796         FT->getParamType(0) != B.getInt8PtrTy() ||
 797         FT->getParamType(1) != FT->getParamType(0) ||
 798         !FT->getReturnType()->isIntegerTy())
 799       return 0;
 800
 801     StringRef S1, S2;
 802     bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
 803     bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
 804
 805     // strspn(s, "") -> 0
 806     // strspn("", s) -> 0
 807     if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))
 808       return Constant::getNullValue(CI->getType());
 809
 810     // Constant folding.
 811     if (HasS1 && HasS2) {
 812       size_t Pos = S1.find_first_not_of(S2);
 813       if (Pos == StringRef::npos) Pos = S1.size();
 814       return ConstantInt::get(CI->getType(), Pos);
 815     }
 816
 817     return 0;
 818   }
 819 };
 820
 821 struct StrCSpnOpt : public LibCallOptimization {
 822   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 823     FunctionType *FT = Callee->getFunctionType();
 824     if (FT->getNumParams() != 2 ||
 825         FT->getParamType(0) != B.getInt8PtrTy() ||
 826         FT->getParamType(1) != FT->getParamType(0) ||
 827         !FT->getReturnType()->isIntegerTy())
 828       return 0;
 829
 830     StringRef S1, S2;
 831     bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
 832     bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
 833
 834     // strcspn("", s) -> 0
 835     if (HasS1 && S1.empty())
 836       return Constant::getNullValue(CI->getType());
 837
 838     // Constant folding.
 839     if (HasS1 && HasS2) {
 840       size_t Pos = S1.find_first_of(S2);
 841       if (Pos == StringRef::npos) Pos = S1.size();
 842       return ConstantInt::get(CI->getType(), Pos);
 843     }
 844
 845     // strcspn(s, "") -> strlen(s)
 846     if (TD && HasS2 && S2.empty())
 847       return EmitStrLen(CI->getArgOperand(0), B, TD, TLI);
 848
 849     return 0;
 850   }
 851 };
 852
 853 struct StrStrOpt : public LibCallOptimization {
 854   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 855     FunctionType *FT = Callee->getFunctionType();
 856     if (FT->getNumParams() != 2 ||
 857         !FT->getParamType(0)->isPointerTy() ||
 858         !FT->getParamType(1)->isPointerTy() ||
 859         !FT->getReturnType()->isPointerTy())
 860       return 0;
 861
 862     // fold strstr(x, x) -> x.
 863     if (CI->getArgOperand(0) == CI->getArgOperand(1))
 864       return B.CreateBitCast(CI->getArgOperand(0), CI->getType());
 865
 866     // fold strstr(a, b) == a -> strncmp(a, b, strlen(b)) == 0
 867     if (TD && isOnlyUsedInEqualityComparison(CI, CI->getArgOperand(0))) {
 868       Value *StrLen = EmitStrLen(CI->getArgOperand(1), B, TD, TLI);
 869       if (!StrLen)
 870         return 0;
 871       Value *StrNCmp = EmitStrNCmp(CI->getArgOperand(0), CI->getArgOperand(1),
 872                                    StrLen, B, TD, TLI);
 873       if (!StrNCmp)
 874         return 0;
 875       for (Value::use_iterator UI = CI->use_begin(), UE = CI->use_end();
 876            UI != UE; ) {
 877         ICmpInst *Old = cast<ICmpInst>(*UI++);
 878         Value *Cmp = B.CreateICmp(Old->getPredicate(), StrNCmp,
 879                                   ConstantInt::getNullValue(StrNCmp->getType()),
 880                                   "cmp");
 881         LCS->replaceAllUsesWith(Old, Cmp);
 882       }
 883       return CI;
 884     }
 885
 886     // See if either input string is a constant string.
 887     StringRef SearchStr, ToFindStr;
 888     bool HasStr1 = getConstantStringInfo(CI->getArgOperand(0), SearchStr);
 889     bool HasStr2 = getConstantStringInfo(CI->getArgOperand(1), ToFindStr);
 890
 891     // fold strstr(x, "") -> x.
 892     if (HasStr2 && ToFindStr.empty())
 893       return B.CreateBitCast(CI->getArgOperand(0), CI->getType());
 894
 895     // If both strings are known, constant fold it.
 896     if (HasStr1 && HasStr2) {
 897       std::string::size_type Offset = SearchStr.find(ToFindStr);
 898
 899       if (Offset == StringRef::npos) // strstr("foo", "bar") -> null
 900         return Constant::getNullValue(CI->getType());
 901
 902       // strstr("abcd", "bc") -> gep((char*)"abcd", 1)
 903       Value *Result = CastToCStr(CI->getArgOperand(0), B);
 904       Result = B.CreateConstInBoundsGEP1_64(Result, Offset, "strstr");
 905       return B.CreateBitCast(Result, CI->getType());
 906     }
 907
 908     // fold strstr(x, "y") -> strchr(x, 'y').
 909     if (HasStr2 && ToFindStr.size() == 1) {
 910       Value *StrChr= EmitStrChr(CI->getArgOperand(0), ToFindStr[0], B, TD, TLI);
 911       return StrChr ? B.CreateBitCast(StrChr, CI->getType()) : 0;
 912     }
 913     return 0;
 914   }
 915 };
 916
 917 struct MemCmpOpt : public LibCallOptimization {
 918   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 919     FunctionType *FT = Callee->getFunctionType();
 920     if (FT->getNumParams() != 3 || !FT->getParamType(0)->isPointerTy() ||
 921         !FT->getParamType(1)->isPointerTy() ||
 922         !FT->getReturnType()->isIntegerTy(32))
 923       return 0;
 924
 925     Value *LHS = CI->getArgOperand(0), *RHS = CI->getArgOperand(1);
 926
 927     if (LHS == RHS)  // memcmp(s,s,x) -> 0
 928       return Constant::getNullValue(CI->getType());
 929
 930     // Make sure we have a constant length.
 931     ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getArgOperand(2));
 932     if (!LenC) return 0;
 933     uint64_t Len = LenC->getZExtValue();
 934
 935     if (Len == 0) // memcmp(s1,s2,0) -> 0
 936       return Constant::getNullValue(CI->getType());
 937
 938     // memcmp(S1,S2,1) -> *(unsigned char*)LHS - *(unsigned char*)RHS
 939     if (Len == 1) {
 940       Value *LHSV = B.CreateZExt(B.CreateLoad(CastToCStr(LHS, B), "lhsc"),
 941                                  CI->getType(), "lhsv");
 942       Value *RHSV = B.CreateZExt(B.CreateLoad(CastToCStr(RHS, B), "rhsc"),
 943                                  CI->getType(), "rhsv");
 944       return B.CreateSub(LHSV, RHSV, "chardiff");
 945     }
 946
 947     // Constant folding: memcmp(x, y, l) -> cnst (all arguments are constant)
 948     StringRef LHSStr, RHSStr;
 949     if (getConstantStringInfo(LHS, LHSStr) &&
 950         getConstantStringInfo(RHS, RHSStr)) {
 951       // Make sure we're not reading out-of-bounds memory.
 952       if (Len > LHSStr.size() || Len > RHSStr.size())
 953         return 0;
 954       // Fold the memcmp and normalize the result.  This way we get consistent
 955       // results across multiple platforms.
 956       uint64_t Ret = 0;
 957       int Cmp = memcmp(LHSStr.data(), RHSStr.data(), Len);
 958       if (Cmp < 0)
 959         Ret = -1;
 960       else if (Cmp > 0)
 961         Ret = 1;
 962       return ConstantInt::get(CI->getType(), Ret);
 963     }
 964
 965     return 0;
 966   }
 967 };
 968
 969 struct MemCpyOpt : public LibCallOptimization {
 970   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 971     // These optimizations require DataLayout.
 972     if (!TD) return 0;
 973
 974     FunctionType *FT = Callee->getFunctionType();
 975     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 976         !FT->getParamType(0)->isPointerTy() ||
 977         !FT->getParamType(1)->isPointerTy() ||
 978         FT->getParamType(2) != TD->getIntPtrType(*Context))
 979       return 0;
 980
 981     // memcpy(x, y, n) -> llvm.memcpy(x, y, n, 1)
 982     B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
 983                    CI->getArgOperand(2), 1);
 984     return CI->getArgOperand(0);
 985   }
 986 };
 987
 988 struct MemMoveOpt : public LibCallOptimization {
 989   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 990     // These optimizations require DataLayout.
 991     if (!TD) return 0;
 992
 993     FunctionType *FT = Callee->getFunctionType();
 994     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 995         !FT->getParamType(0)->isPointerTy() ||
 996         !FT->getParamType(1)->isPointerTy() ||
 997         FT->getParamType(2) != TD->getIntPtrType(*Context))
 998       return 0;
 999
1000     // memmove(x, y, n) -> llvm.memmove(x, y, n, 1)
1001     B.CreateMemMove(CI->getArgOperand(0), CI->getArgOperand(1),
1002                     CI->getArgOperand(2), 1);
1003     return CI->getArgOperand(0);
1004   }
1005 };
1006
1007 struct MemSetOpt : public LibCallOptimization {
1008   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1009     // These optimizations require DataLayout.
1010     if (!TD) return 0;
1011
1012     FunctionType *FT = Callee->getFunctionType();
1013     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
1014         !FT->getParamType(0)->isPointerTy() ||
1015         !FT->getParamType(1)->isIntegerTy() ||
1016         FT->getParamType(2) != TD->getIntPtrType(*Context))
1017       return 0;
1018
1019     // memset(p, v, n) -> llvm.memset(p, v, n, 1)
1020     Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(), false);
1021     B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1);
1022     return CI->getArgOperand(0);
1023   }
1024 };
1025
1026 } // End anonymous namespace.
1027
1028 namespace llvm {
1029
1030 class LibCallSimplifierImpl {
1031   const DataLayout *TD;
1032   const TargetLibraryInfo *TLI;
1033   const LibCallSimplifier *LCS;
1034   StringMap<LibCallOptimization*> Optimizations;
1035
1036   // Fortified library call optimizations.
1037   MemCpyChkOpt MemCpyChk;
1038   MemMoveChkOpt MemMoveChk;
1039   MemSetChkOpt MemSetChk;
1040   StrCpyChkOpt StrCpyChk;
1041   StpCpyChkOpt StpCpyChk;
1042   StrNCpyChkOpt StrNCpyChk;
1043
1044   // String library call optimizations.
1045   StrCatOpt StrCat;
1046   StrNCatOpt StrNCat;
1047   StrChrOpt StrChr;
1048   StrRChrOpt StrRChr;
1049   StrCmpOpt StrCmp;
1050   StrNCmpOpt StrNCmp;
1051   StrCpyOpt StrCpy;
1052   StpCpyOpt StpCpy;
1053   StrNCpyOpt StrNCpy;
1054   StrLenOpt StrLen;
1055   StrPBrkOpt StrPBrk;
1056   StrToOpt StrTo;
1057   StrSpnOpt StrSpn;
1058   StrCSpnOpt StrCSpn;
1059   StrStrOpt StrStr;
1060
1061   // Memory library call optimizations.
1062   MemCmpOpt MemCmp;
1063   MemCpyOpt MemCpy;
1064   MemMoveOpt MemMove;
1065   MemSetOpt MemSet;
1066
1067   void initOptimizations();
1068   void addOpt(LibFunc::Func F, LibCallOptimization* Opt);
1069 public:
1070   LibCallSimplifierImpl(const DataLayout *TD, const TargetLibraryInfo *TLI,
1071                         const LibCallSimplifier *LCS) {
1072     this->TD = TD;
1073     this->TLI = TLI;
1074     this->LCS = LCS;
1075   }
1076
1077   Value *optimizeCall(CallInst *CI);
1078 };
1079
1080 void LibCallSimplifierImpl::initOptimizations() {
1081   // Fortified library call optimizations.
1082   Optimizations["__memcpy_chk"] = &MemCpyChk;
1083   Optimizations["__memmove_chk"] = &MemMoveChk;
1084   Optimizations["__memset_chk"] = &MemSetChk;
1085   Optimizations["__strcpy_chk"] = &StrCpyChk;
1086   Optimizations["__stpcpy_chk"] = &StpCpyChk;
1087   Optimizations["__strncpy_chk"] = &StrNCpyChk;
1088   Optimizations["__stpncpy_chk"] = &StrNCpyChk;
1089
1090   // String library call optimizations.
1091   addOpt(LibFunc::strcat, &StrCat);
1092   addOpt(LibFunc::strncat, &StrNCat);
1093   addOpt(LibFunc::strchr, &StrChr);
1094   addOpt(LibFunc::strrchr, &StrRChr);
1095   addOpt(LibFunc::strcmp, &StrCmp);
1096   addOpt(LibFunc::strncmp, &StrNCmp);
1097   addOpt(LibFunc::strcpy, &StrCpy);
1098   addOpt(LibFunc::stpcpy, &StpCpy);
1099   addOpt(LibFunc::strncpy, &StrNCpy);
1100   addOpt(LibFunc::strlen, &StrLen);
1101   addOpt(LibFunc::strpbrk, &StrPBrk);
1102   addOpt(LibFunc::strtol, &StrTo);
1103   addOpt(LibFunc::strtod, &StrTo);
1104   addOpt(LibFunc::strtof, &StrTo);
1105   addOpt(LibFunc::strtoul, &StrTo);
1106   addOpt(LibFunc::strtoll, &StrTo);
1107   addOpt(LibFunc::strtold, &StrTo);
1108   addOpt(LibFunc::strtoull, &StrTo);
1109   addOpt(LibFunc::strspn, &StrSpn);
1110   addOpt(LibFunc::strcspn, &StrCSpn);
1111   addOpt(LibFunc::strstr, &StrStr);
1112
1113   // Memory library call optimizations.
1114   addOpt(LibFunc::memcmp, &MemCmp);
1115   addOpt(LibFunc::memcpy, &MemCpy);
1116   addOpt(LibFunc::memmove, &MemMove);
1117   addOpt(LibFunc::memset, &MemSet);
1118 }
1119
1120 Value *LibCallSimplifierImpl::optimizeCall(CallInst *CI) {
1121   if (Optimizations.empty())
1122     initOptimizations();
1123
1124   Function *Callee = CI->getCalledFunction();
1125   LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
1126   if (LCO) {
1127     IRBuilder<> Builder(CI);
1128     return LCO->optimizeCall(CI, TD, TLI, LCS, Builder);
1129   }
1130   return 0;
1131 }
1132
1133 void LibCallSimplifierImpl::addOpt(LibFunc::Func F, LibCallOptimization* Opt) {
1134   if (TLI->has(F))
1135     Optimizations[TLI->getName(F)] = Opt;
1136 }
1137
1138 LibCallSimplifier::LibCallSimplifier(const DataLayout *TD,
1139                                      const TargetLibraryInfo *TLI) {
1140   Impl = new LibCallSimplifierImpl(TD, TLI, this);
1141 }
1142
1143 LibCallSimplifier::~LibCallSimplifier() {
1144   delete Impl;
1145 }
1146
1147 Value *LibCallSimplifier::optimizeCall(CallInst *CI) {
1148   return Impl->optimizeCall(CI);
1149 }
1150
1151 void LibCallSimplifier::replaceAllUsesWith(Instruction *I, Value *With) const {
1152   I->replaceAllUsesWith(With);
1153   I->eraseFromParent();
1154 }
1155
1156 }