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 //===----------------------------------------------------------------------===//
  90 // Fortified Library Call Optimizations
  91 //===----------------------------------------------------------------------===//
  92
  93 struct FortifiedLibCallOptimization : public LibCallOptimization {
  94 protected:
  95   virtual bool isFoldable(unsigned SizeCIOp, unsigned SizeArgOp,
  96                           bool isString) const = 0;
  97 };
  98
  99 struct InstFortifiedLibCallOptimization : public FortifiedLibCallOptimization {
 100   CallInst *CI;
 101
 102   bool isFoldable(unsigned SizeCIOp, unsigned SizeArgOp, bool isString) const {
 103     if (CI->getArgOperand(SizeCIOp) == CI->getArgOperand(SizeArgOp))
 104       return true;
 105     if (ConstantInt *SizeCI =
 106                            dyn_cast<ConstantInt>(CI->getArgOperand(SizeCIOp))) {
 107       if (SizeCI->isAllOnesValue())
 108         return true;
 109       if (isString) {
 110         uint64_t Len = GetStringLength(CI->getArgOperand(SizeArgOp));
 111         // If the length is 0 we don't know how long it is and so we can't
 112         // remove the check.
 113         if (Len == 0) return false;
 114         return SizeCI->getZExtValue() >= Len;
 115       }
 116       if (ConstantInt *Arg = dyn_cast<ConstantInt>(
 117                                                   CI->getArgOperand(SizeArgOp)))
 118         return SizeCI->getZExtValue() >= Arg->getZExtValue();
 119     }
 120     return false;
 121   }
 122 };
 123
 124 struct MemCpyChkOpt : public InstFortifiedLibCallOptimization {
 125   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 126     this->CI = CI;
 127     FunctionType *FT = Callee->getFunctionType();
 128     LLVMContext &Context = CI->getParent()->getContext();
 129
 130     // Check if this has the right signature.
 131     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 132         !FT->getParamType(0)->isPointerTy() ||
 133         !FT->getParamType(1)->isPointerTy() ||
 134         FT->getParamType(2) != TD->getIntPtrType(Context) ||
 135         FT->getParamType(3) != TD->getIntPtrType(Context))
 136       return 0;
 137
 138     if (isFoldable(3, 2, false)) {
 139       B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
 140                      CI->getArgOperand(2), 1);
 141       return CI->getArgOperand(0);
 142     }
 143     return 0;
 144   }
 145 };
 146
 147 struct MemMoveChkOpt : public InstFortifiedLibCallOptimization {
 148   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 149     this->CI = CI;
 150     FunctionType *FT = Callee->getFunctionType();
 151     LLVMContext &Context = CI->getParent()->getContext();
 152
 153     // Check if this has the right signature.
 154     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 155         !FT->getParamType(0)->isPointerTy() ||
 156         !FT->getParamType(1)->isPointerTy() ||
 157         FT->getParamType(2) != TD->getIntPtrType(Context) ||
 158         FT->getParamType(3) != TD->getIntPtrType(Context))
 159       return 0;
 160
 161     if (isFoldable(3, 2, false)) {
 162       B.CreateMemMove(CI->getArgOperand(0), CI->getArgOperand(1),
 163                       CI->getArgOperand(2), 1);
 164       return CI->getArgOperand(0);
 165     }
 166     return 0;
 167   }
 168 };
 169
 170 struct MemSetChkOpt : public InstFortifiedLibCallOptimization {
 171   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 172     this->CI = CI;
 173     FunctionType *FT = Callee->getFunctionType();
 174     LLVMContext &Context = CI->getParent()->getContext();
 175
 176     // Check if this has the right signature.
 177     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 178         !FT->getParamType(0)->isPointerTy() ||
 179         !FT->getParamType(1)->isIntegerTy() ||
 180         FT->getParamType(2) != TD->getIntPtrType(Context) ||
 181         FT->getParamType(3) != TD->getIntPtrType(Context))
 182       return 0;
 183
 184     if (isFoldable(3, 2, false)) {
 185       Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(),
 186                                    false);
 187       B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1);
 188       return CI->getArgOperand(0);
 189     }
 190     return 0;
 191   }
 192 };
 193
 194 struct StrCpyChkOpt : public InstFortifiedLibCallOptimization {
 195   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 196     this->CI = CI;
 197     StringRef Name = Callee->getName();
 198     FunctionType *FT = Callee->getFunctionType();
 199     LLVMContext &Context = CI->getParent()->getContext();
 200
 201     // Check if this has the right signature.
 202     if (FT->getNumParams() != 3 ||
 203         FT->getReturnType() != FT->getParamType(0) ||
 204         FT->getParamType(0) != FT->getParamType(1) ||
 205         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
 206         FT->getParamType(2) != TD->getIntPtrType(Context))
 207       return 0;
 208
 209     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 210     if (Dst == Src)      // __strcpy_chk(x,x)  -> x
 211       return Src;
 212
 213     // If a) we don't have any length information, or b) we know this will
 214     // fit then just lower to a plain strcpy. Otherwise we'll keep our
 215     // strcpy_chk call which may fail at runtime if the size is too long.
 216     // TODO: It might be nice to get a maximum length out of the possible
 217     // string lengths for varying.
 218     if (isFoldable(2, 1, true)) {
 219       Value *Ret = EmitStrCpy(Dst, Src, B, TD, TLI, Name.substr(2, 6));
 220       return Ret;
 221     } else {
 222       // Maybe we can stil fold __strcpy_chk to __memcpy_chk.
 223       uint64_t Len = GetStringLength(Src);
 224       if (Len == 0) return 0;
 225
 226       // This optimization require DataLayout.
 227       if (!TD) return 0;
 228
 229       Value *Ret =
 230         EmitMemCpyChk(Dst, Src,
 231                       ConstantInt::get(TD->getIntPtrType(Context), Len),
 232                       CI->getArgOperand(2), B, TD, TLI);
 233       return Ret;
 234     }
 235     return 0;
 236   }
 237 };
 238
 239 struct StpCpyChkOpt : public InstFortifiedLibCallOptimization {
 240   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 241     this->CI = CI;
 242     StringRef Name = Callee->getName();
 243     FunctionType *FT = Callee->getFunctionType();
 244     LLVMContext &Context = CI->getParent()->getContext();
 245
 246     // Check if this has the right signature.
 247     if (FT->getNumParams() != 3 ||
 248         FT->getReturnType() != FT->getParamType(0) ||
 249         FT->getParamType(0) != FT->getParamType(1) ||
 250         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
 251         FT->getParamType(2) != TD->getIntPtrType(FT->getParamType(0)))
 252       return 0;
 253
 254     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 255     if (Dst == Src) {  // stpcpy(x,x)  -> x+strlen(x)
 256       Value *StrLen = EmitStrLen(Src, B, TD, TLI);
 257       return StrLen ? B.CreateInBoundsGEP(Dst, StrLen) : 0;
 258     }
 259
 260     // If a) we don't have any length information, or b) we know this will
 261     // fit then just lower to a plain stpcpy. Otherwise we'll keep our
 262     // stpcpy_chk call which may fail at runtime if the size is too long.
 263     // TODO: It might be nice to get a maximum length out of the possible
 264     // string lengths for varying.
 265     if (isFoldable(2, 1, true)) {
 266       Value *Ret = EmitStrCpy(Dst, Src, B, TD, TLI, Name.substr(2, 6));
 267       return Ret;
 268     } else {
 269       // Maybe we can stil fold __stpcpy_chk to __memcpy_chk.
 270       uint64_t Len = GetStringLength(Src);
 271       if (Len == 0) return 0;
 272
 273       // This optimization require DataLayout.
 274       if (!TD) return 0;
 275
 276       Type *PT = FT->getParamType(0);
 277       Value *LenV = ConstantInt::get(TD->getIntPtrType(PT), Len);
 278       Value *DstEnd = B.CreateGEP(Dst,
 279                                   ConstantInt::get(TD->getIntPtrType(PT),
 280                                                    Len - 1));
 281       if (!EmitMemCpyChk(Dst, Src, LenV, CI->getArgOperand(2), B, TD, TLI))
 282         return 0;
 283       return DstEnd;
 284     }
 285     return 0;
 286   }
 287 };
 288
 289 struct StrNCpyChkOpt : public InstFortifiedLibCallOptimization {
 290   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 291     this->CI = CI;
 292     StringRef Name = Callee->getName();
 293     FunctionType *FT = Callee->getFunctionType();
 294     LLVMContext &Context = CI->getParent()->getContext();
 295
 296     // Check if this has the right signature.
 297     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 298         FT->getParamType(0) != FT->getParamType(1) ||
 299         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
 300         !FT->getParamType(2)->isIntegerTy() ||
 301         FT->getParamType(3) != TD->getIntPtrType(Context))
 302       return 0;
 303
 304     if (isFoldable(3, 2, false)) {
 305       Value *Ret = EmitStrNCpy(CI->getArgOperand(0), CI->getArgOperand(1),
 306                                CI->getArgOperand(2), B, TD, TLI,
 307                                Name.substr(2, 7));
 308       return Ret;
 309     }
 310     return 0;
 311   }
 312 };
 313
 314 //===----------------------------------------------------------------------===//
 315 // String and Memory Library Call Optimizations
 316 //===----------------------------------------------------------------------===//
 317
 318 struct StrCatOpt : public LibCallOptimization {
 319   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 320     // Verify the "strcat" function prototype.
 321     FunctionType *FT = Callee->getFunctionType();
 322     if (FT->getNumParams() != 2 ||
 323         FT->getReturnType() != B.getInt8PtrTy() ||
 324         FT->getParamType(0) != FT->getReturnType() ||
 325         FT->getParamType(1) != FT->getReturnType())
 326       return 0;
 327
 328     // Extract some information from the instruction
 329     Value *Dst = CI->getArgOperand(0);
 330     Value *Src = CI->getArgOperand(1);
 331
 332     // See if we can get the length of the input string.
 333     uint64_t Len = GetStringLength(Src);
 334     if (Len == 0) return 0;
 335     --Len;  // Unbias length.
 336
 337     // Handle the simple, do-nothing case: strcat(x, "") -> x
 338     if (Len == 0)
 339       return Dst;
 340
 341     // These optimizations require DataLayout.
 342     if (!TD) return 0;
 343
 344     return emitStrLenMemCpy(Src, Dst, Len, B);
 345   }
 346
 347   Value *emitStrLenMemCpy(Value *Src, Value *Dst, uint64_t Len,
 348                           IRBuilder<> &B) {
 349     // We need to find the end of the destination string.  That's where the
 350     // memory is to be moved to. We just generate a call to strlen.
 351     Value *DstLen = EmitStrLen(Dst, B, TD, TLI);
 352     if (!DstLen)
 353       return 0;
 354
 355     // Now that we have the destination's length, we must index into the
 356     // destination's pointer to get the actual memcpy destination (end of
 357     // the string .. we're concatenating).
 358     Value *CpyDst = B.CreateGEP(Dst, DstLen, "endptr");
 359
 360     // We have enough information to now generate the memcpy call to do the
 361     // concatenation for us.  Make a memcpy to copy the nul byte with align = 1.
 362     B.CreateMemCpy(CpyDst, Src,
 363                    ConstantInt::get(TD->getIntPtrType(*Context), Len + 1), 1);
 364     return Dst;
 365   }
 366 };
 367
 368 struct StrNCatOpt : public StrCatOpt {
 369   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 370     // Verify the "strncat" function prototype.
 371     FunctionType *FT = Callee->getFunctionType();
 372     if (FT->getNumParams() != 3 ||
 373         FT->getReturnType() != B.getInt8PtrTy() ||
 374         FT->getParamType(0) != FT->getReturnType() ||
 375         FT->getParamType(1) != FT->getReturnType() ||
 376         !FT->getParamType(2)->isIntegerTy())
 377       return 0;
 378
 379     // Extract some information from the instruction
 380     Value *Dst = CI->getArgOperand(0);
 381     Value *Src = CI->getArgOperand(1);
 382     uint64_t Len;
 383
 384     // We don't do anything if length is not constant
 385     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
 386       Len = LengthArg->getZExtValue();
 387     else
 388       return 0;
 389
 390     // See if we can get the length of the input string.
 391     uint64_t SrcLen = GetStringLength(Src);
 392     if (SrcLen == 0) return 0;
 393     --SrcLen;  // Unbias length.
 394
 395     // Handle the simple, do-nothing cases:
 396     // strncat(x, "", c) -> x
 397     // strncat(x,  c, 0) -> x
 398     if (SrcLen == 0 || Len == 0) return Dst;
 399
 400     // These optimizations require DataLayout.
 401     if (!TD) return 0;
 402
 403     // We don't optimize this case
 404     if (Len < SrcLen) return 0;
 405
 406     // strncat(x, s, c) -> strcat(x, s)
 407     // s is constant so the strcat can be optimized further
 408     return emitStrLenMemCpy(Src, Dst, SrcLen, B);
 409   }
 410 };
 411
 412 struct StrChrOpt : public LibCallOptimization {
 413   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 414     // Verify the "strchr" function prototype.
 415     FunctionType *FT = Callee->getFunctionType();
 416     if (FT->getNumParams() != 2 ||
 417         FT->getReturnType() != B.getInt8PtrTy() ||
 418         FT->getParamType(0) != FT->getReturnType() ||
 419         !FT->getParamType(1)->isIntegerTy(32))
 420       return 0;
 421
 422     Value *SrcStr = CI->getArgOperand(0);
 423
 424     // If the second operand is non-constant, see if we can compute the length
 425     // of the input string and turn this into memchr.
 426     ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
 427     if (CharC == 0) {
 428       // These optimizations require DataLayout.
 429       if (!TD) return 0;
 430
 431       uint64_t Len = GetStringLength(SrcStr);
 432       if (Len == 0 || !FT->getParamType(1)->isIntegerTy(32))// memchr needs i32.
 433         return 0;
 434
 435       return EmitMemChr(SrcStr, CI->getArgOperand(1), // include nul.
 436                         ConstantInt::get(TD->getIntPtrType(*Context), Len),
 437                         B, TD, TLI);
 438     }
 439
 440     // Otherwise, the character is a constant, see if the first argument is
 441     // a string literal.  If so, we can constant fold.
 442     StringRef Str;
 443     if (!getConstantStringInfo(SrcStr, Str))
 444       return 0;
 445
 446     // Compute the offset, make sure to handle the case when we're searching for
 447     // zero (a weird way to spell strlen).
 448     size_t I = CharC->getSExtValue() == 0 ?
 449         Str.size() : Str.find(CharC->getSExtValue());
 450     if (I == StringRef::npos) // Didn't find the char.  strchr returns null.
 451       return Constant::getNullValue(CI->getType());
 452
 453     // strchr(s+n,c)  -> gep(s+n+i,c)
 454     return B.CreateGEP(SrcStr, B.getInt64(I), "strchr");
 455   }
 456 };
 457
 458 struct StrRChrOpt : public LibCallOptimization {
 459   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 460     // Verify the "strrchr" function prototype.
 461     FunctionType *FT = Callee->getFunctionType();
 462     if (FT->getNumParams() != 2 ||
 463         FT->getReturnType() != B.getInt8PtrTy() ||
 464         FT->getParamType(0) != FT->getReturnType() ||
 465         !FT->getParamType(1)->isIntegerTy(32))
 466       return 0;
 467
 468     Value *SrcStr = CI->getArgOperand(0);
 469     ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
 470
 471     // Cannot fold anything if we're not looking for a constant.
 472     if (!CharC)
 473       return 0;
 474
 475     StringRef Str;
 476     if (!getConstantStringInfo(SrcStr, Str)) {
 477       // strrchr(s, 0) -> strchr(s, 0)
 478       if (TD && CharC->isZero())
 479         return EmitStrChr(SrcStr, '\0', B, TD, TLI);
 480       return 0;
 481     }
 482
 483     // Compute the offset.
 484     size_t I = CharC->getSExtValue() == 0 ?
 485         Str.size() : Str.rfind(CharC->getSExtValue());
 486     if (I == StringRef::npos) // Didn't find the char. Return null.
 487       return Constant::getNullValue(CI->getType());
 488
 489     // strrchr(s+n,c) -> gep(s+n+i,c)
 490     return B.CreateGEP(SrcStr, B.getInt64(I), "strrchr");
 491   }
 492 };
 493
 494 struct StrCmpOpt : public LibCallOptimization {
 495   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 496     // Verify the "strcmp" function prototype.
 497     FunctionType *FT = Callee->getFunctionType();
 498     if (FT->getNumParams() != 2 ||
 499         !FT->getReturnType()->isIntegerTy(32) ||
 500         FT->getParamType(0) != FT->getParamType(1) ||
 501         FT->getParamType(0) != B.getInt8PtrTy())
 502       return 0;
 503
 504     Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
 505     if (Str1P == Str2P)      // strcmp(x,x)  -> 0
 506       return ConstantInt::get(CI->getType(), 0);
 507
 508     StringRef Str1, Str2;
 509     bool HasStr1 = getConstantStringInfo(Str1P, Str1);
 510     bool HasStr2 = getConstantStringInfo(Str2P, Str2);
 511
 512     // strcmp(x, y)  -> cnst  (if both x and y are constant strings)
 513     if (HasStr1 && HasStr2)
 514       return ConstantInt::get(CI->getType(), Str1.compare(Str2));
 515
 516     if (HasStr1 && Str1.empty()) // strcmp("", x) -> -*x
 517       return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"),
 518                                       CI->getType()));
 519
 520     if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x
 521       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
 522
 523     // strcmp(P, "x") -> memcmp(P, "x", 2)
 524     uint64_t Len1 = GetStringLength(Str1P);
 525     uint64_t Len2 = GetStringLength(Str2P);
 526     if (Len1 && Len2) {
 527       // These optimizations require DataLayout.
 528       if (!TD) return 0;
 529
 530       return EmitMemCmp(Str1P, Str2P,
 531                         ConstantInt::get(TD->getIntPtrType(*Context),
 532                         std::min(Len1, Len2)), B, TD, TLI);
 533     }
 534
 535     return 0;
 536   }
 537 };
 538
 539 struct StrNCmpOpt : public LibCallOptimization {
 540   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 541     // Verify the "strncmp" function prototype.
 542     FunctionType *FT = Callee->getFunctionType();
 543     if (FT->getNumParams() != 3 ||
 544         !FT->getReturnType()->isIntegerTy(32) ||
 545         FT->getParamType(0) != FT->getParamType(1) ||
 546         FT->getParamType(0) != B.getInt8PtrTy() ||
 547         !FT->getParamType(2)->isIntegerTy())
 548       return 0;
 549
 550     Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
 551     if (Str1P == Str2P)      // strncmp(x,x,n)  -> 0
 552       return ConstantInt::get(CI->getType(), 0);
 553
 554     // Get the length argument if it is constant.
 555     uint64_t Length;
 556     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
 557       Length = LengthArg->getZExtValue();
 558     else
 559       return 0;
 560
 561     if (Length == 0) // strncmp(x,y,0)   -> 0
 562       return ConstantInt::get(CI->getType(), 0);
 563
 564     if (TD && Length == 1) // strncmp(x,y,1) -> memcmp(x,y,1)
 565       return EmitMemCmp(Str1P, Str2P, CI->getArgOperand(2), B, TD, TLI);
 566
 567     StringRef Str1, Str2;
 568     bool HasStr1 = getConstantStringInfo(Str1P, Str1);
 569     bool HasStr2 = getConstantStringInfo(Str2P, Str2);
 570
 571     // strncmp(x, y)  -> cnst  (if both x and y are constant strings)
 572     if (HasStr1 && HasStr2) {
 573       StringRef SubStr1 = Str1.substr(0, Length);
 574       StringRef SubStr2 = Str2.substr(0, Length);
 575       return ConstantInt::get(CI->getType(), SubStr1.compare(SubStr2));
 576     }
 577
 578     if (HasStr1 && Str1.empty())  // strncmp("", x, n) -> -*x
 579       return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"),
 580                                       CI->getType()));
 581
 582     if (HasStr2 && Str2.empty())  // strncmp(x, "", n) -> *x
 583       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
 584
 585     return 0;
 586   }
 587 };
 588
 589 struct StrCpyOpt : public LibCallOptimization {
 590   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 591     // Verify the "strcpy" function prototype.
 592     FunctionType *FT = Callee->getFunctionType();
 593     if (FT->getNumParams() != 2 ||
 594         FT->getReturnType() != FT->getParamType(0) ||
 595         FT->getParamType(0) != FT->getParamType(1) ||
 596         FT->getParamType(0) != B.getInt8PtrTy())
 597       return 0;
 598
 599     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 600     if (Dst == Src)      // strcpy(x,x)  -> x
 601       return Src;
 602
 603     // These optimizations require DataLayout.
 604     if (!TD) return 0;
 605
 606     // See if we can get the length of the input string.
 607     uint64_t Len = GetStringLength(Src);
 608     if (Len == 0) return 0;
 609
 610     // We have enough information to now generate the memcpy call to do the
 611     // copy for us.  Make a memcpy to copy the nul byte with align = 1.
 612     B.CreateMemCpy(Dst, Src,
 613                    ConstantInt::get(TD->getIntPtrType(*Context), Len), 1);
 614     return Dst;
 615   }
 616 };
 617
 618 struct StpCpyOpt: public LibCallOptimization {
 619   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 620     // Verify the "stpcpy" function prototype.
 621     FunctionType *FT = Callee->getFunctionType();
 622     if (FT->getNumParams() != 2 ||
 623         FT->getReturnType() != FT->getParamType(0) ||
 624         FT->getParamType(0) != FT->getParamType(1) ||
 625         FT->getParamType(0) != B.getInt8PtrTy())
 626       return 0;
 627
 628     // These optimizations require DataLayout.
 629     if (!TD) return 0;
 630
 631     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 632     if (Dst == Src) {  // stpcpy(x,x)  -> x+strlen(x)
 633       Value *StrLen = EmitStrLen(Src, B, TD, TLI);
 634       return StrLen ? B.CreateInBoundsGEP(Dst, StrLen) : 0;
 635     }
 636
 637     // See if we can get the length of the input string.
 638     uint64_t Len = GetStringLength(Src);
 639     if (Len == 0) return 0;
 640
 641     Type *PT = FT->getParamType(0);
 642     Value *LenV = ConstantInt::get(TD->getIntPtrType(PT), Len);
 643     Value *DstEnd = B.CreateGEP(Dst,
 644                                 ConstantInt::get(TD->getIntPtrType(PT),
 645                                                  Len - 1));
 646
 647     // We have enough information to now generate the memcpy call to do the
 648     // copy for us.  Make a memcpy to copy the nul byte with align = 1.
 649     B.CreateMemCpy(Dst, Src, LenV, 1);
 650     return DstEnd;
 651   }
 652 };
 653
 654 struct StrNCpyOpt : public LibCallOptimization {
 655   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 656     FunctionType *FT = Callee->getFunctionType();
 657     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 658         FT->getParamType(0) != FT->getParamType(1) ||
 659         FT->getParamType(0) != B.getInt8PtrTy() ||
 660         !FT->getParamType(2)->isIntegerTy())
 661       return 0;
 662
 663     Value *Dst = CI->getArgOperand(0);
 664     Value *Src = CI->getArgOperand(1);
 665     Value *LenOp = CI->getArgOperand(2);
 666
 667     // See if we can get the length of the input string.
 668     uint64_t SrcLen = GetStringLength(Src);
 669     if (SrcLen == 0) return 0;
 670     --SrcLen;
 671
 672     if (SrcLen == 0) {
 673       // strncpy(x, "", y) -> memset(x, '\0', y, 1)
 674       B.CreateMemSet(Dst, B.getInt8('\0'), LenOp, 1);
 675       return Dst;
 676     }
 677
 678     uint64_t Len;
 679     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(LenOp))
 680       Len = LengthArg->getZExtValue();
 681     else
 682       return 0;
 683
 684     if (Len == 0) return Dst; // strncpy(x, y, 0) -> x
 685
 686     // These optimizations require DataLayout.
 687     if (!TD) return 0;
 688
 689     // Let strncpy handle the zero padding
 690     if (Len > SrcLen+1) return 0;
 691
 692     Type *PT = FT->getParamType(0);
 693     // strncpy(x, s, c) -> memcpy(x, s, c, 1) [s and c are constant]
 694     B.CreateMemCpy(Dst, Src,
 695                    ConstantInt::get(TD->getIntPtrType(PT), Len), 1);
 696
 697     return Dst;
 698   }
 699 };
 700
 701 struct StrLenOpt : public LibCallOptimization {
 702   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 703     FunctionType *FT = Callee->getFunctionType();
 704     if (FT->getNumParams() != 1 ||
 705         FT->getParamType(0) != B.getInt8PtrTy() ||
 706         !FT->getReturnType()->isIntegerTy())
 707       return 0;
 708
 709     Value *Src = CI->getArgOperand(0);
 710
 711     // Constant folding: strlen("xyz") -> 3
 712     if (uint64_t Len = GetStringLength(Src))
 713       return ConstantInt::get(CI->getType(), Len-1);
 714
 715     // strlen(x) != 0 --> *x != 0
 716     // strlen(x) == 0 --> *x == 0
 717     if (isOnlyUsedInZeroEqualityComparison(CI))
 718       return B.CreateZExt(B.CreateLoad(Src, "strlenfirst"), CI->getType());
 719     return 0;
 720   }
 721 };
 722
 723 struct StrPBrkOpt : public LibCallOptimization {
 724   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 725     FunctionType *FT = Callee->getFunctionType();
 726     if (FT->getNumParams() != 2 ||
 727         FT->getParamType(0) != B.getInt8PtrTy() ||
 728         FT->getParamType(1) != FT->getParamType(0) ||
 729         FT->getReturnType() != FT->getParamType(0))
 730       return 0;
 731
 732     StringRef S1, S2;
 733     bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
 734     bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
 735
 736     // strpbrk(s, "") -> NULL
 737     // strpbrk("", s) -> NULL
 738     if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))
 739       return Constant::getNullValue(CI->getType());
 740
 741     // Constant folding.
 742     if (HasS1 && HasS2) {
 743       size_t I = S1.find_first_of(S2);
 744       if (I == std::string::npos) // No match.
 745         return Constant::getNullValue(CI->getType());
 746
 747       return B.CreateGEP(CI->getArgOperand(0), B.getInt64(I), "strpbrk");
 748     }
 749
 750     // strpbrk(s, "a") -> strchr(s, 'a')
 751     if (TD && HasS2 && S2.size() == 1)
 752       return EmitStrChr(CI->getArgOperand(0), S2[0], B, TD, TLI);
 753
 754     return 0;
 755   }
 756 };
 757
 758 struct StrToOpt : public LibCallOptimization {
 759   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 760     FunctionType *FT = Callee->getFunctionType();
 761     if ((FT->getNumParams() != 2 && FT->getNumParams() != 3) ||
 762         !FT->getParamType(0)->isPointerTy() ||
 763         !FT->getParamType(1)->isPointerTy())
 764       return 0;
 765
 766     Value *EndPtr = CI->getArgOperand(1);
 767     if (isa<ConstantPointerNull>(EndPtr)) {
 768       // With a null EndPtr, this function won't capture the main argument.
 769       // It would be readonly too, except that it still may write to errno.
 770       CI->addAttribute(1, Attributes::get(Callee->getContext(),
 771                                           Attributes::NoCapture));
 772     }
 773
 774     return 0;
 775   }
 776 };
 777
 778 struct StrSpnOpt : public LibCallOptimization {
 779   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 780     FunctionType *FT = Callee->getFunctionType();
 781     if (FT->getNumParams() != 2 ||
 782         FT->getParamType(0) != B.getInt8PtrTy() ||
 783         FT->getParamType(1) != FT->getParamType(0) ||
 784         !FT->getReturnType()->isIntegerTy())
 785       return 0;
 786
 787     StringRef S1, S2;
 788     bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
 789     bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
 790
 791     // strspn(s, "") -> 0
 792     // strspn("", s) -> 0
 793     if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))
 794       return Constant::getNullValue(CI->getType());
 795
 796     // Constant folding.
 797     if (HasS1 && HasS2) {
 798       size_t Pos = S1.find_first_not_of(S2);
 799       if (Pos == StringRef::npos) Pos = S1.size();
 800       return ConstantInt::get(CI->getType(), Pos);
 801     }
 802
 803     return 0;
 804   }
 805 };
 806
 807 struct StrCSpnOpt : public LibCallOptimization {
 808   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 809     FunctionType *FT = Callee->getFunctionType();
 810     if (FT->getNumParams() != 2 ||
 811         FT->getParamType(0) != B.getInt8PtrTy() ||
 812         FT->getParamType(1) != FT->getParamType(0) ||
 813         !FT->getReturnType()->isIntegerTy())
 814       return 0;
 815
 816     StringRef S1, S2;
 817     bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
 818     bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
 819
 820     // strcspn("", s) -> 0
 821     if (HasS1 && S1.empty())
 822       return Constant::getNullValue(CI->getType());
 823
 824     // Constant folding.
 825     if (HasS1 && HasS2) {
 826       size_t Pos = S1.find_first_of(S2);
 827       if (Pos == StringRef::npos) Pos = S1.size();
 828       return ConstantInt::get(CI->getType(), Pos);
 829     }
 830
 831     // strcspn(s, "") -> strlen(s)
 832     if (TD && HasS2 && S2.empty())
 833       return EmitStrLen(CI->getArgOperand(0), B, TD, TLI);
 834
 835     return 0;
 836   }
 837 };
 838
 839 } // End anonymous namespace.
 840
 841 namespace llvm {
 842
 843 class LibCallSimplifierImpl {
 844   const DataLayout *TD;
 845   const TargetLibraryInfo *TLI;
 846   const LibCallSimplifier *LCS;
 847   StringMap<LibCallOptimization*> Optimizations;
 848
 849   // Fortified library call optimizations.
 850   MemCpyChkOpt MemCpyChk;
 851   MemMoveChkOpt MemMoveChk;
 852   MemSetChkOpt MemSetChk;
 853   StrCpyChkOpt StrCpyChk;
 854   StpCpyChkOpt StpCpyChk;
 855   StrNCpyChkOpt StrNCpyChk;
 856
 857   // String and memory library call optimizations.
 858   StrCatOpt StrCat;
 859   StrNCatOpt StrNCat;
 860   StrChrOpt StrChr;
 861   StrRChrOpt StrRChr;
 862   StrCmpOpt StrCmp;
 863   StrNCmpOpt StrNCmp;
 864   StrCpyOpt StrCpy;
 865   StpCpyOpt StpCpy;
 866   StrNCpyOpt StrNCpy;
 867   StrLenOpt StrLen;
 868   StrPBrkOpt StrPBrk;
 869   StrToOpt StrTo;
 870   StrSpnOpt StrSpn;
 871   StrCSpnOpt StrCSpn;
 872
 873   void initOptimizations();
 874   void addOpt(LibFunc::Func F, LibCallOptimization* Opt);
 875 public:
 876   LibCallSimplifierImpl(const DataLayout *TD, const TargetLibraryInfo *TLI,
 877                         const LibCallSimplifier *LCS) {
 878     this->TD = TD;
 879     this->TLI = TLI;
 880     this->LCS = LCS;
 881   }
 882
 883   Value *optimizeCall(CallInst *CI);
 884 };
 885
 886 void LibCallSimplifierImpl::initOptimizations() {
 887   // Fortified library call optimizations.
 888   Optimizations["__memcpy_chk"] = &MemCpyChk;
 889   Optimizations["__memmove_chk"] = &MemMoveChk;
 890   Optimizations["__memset_chk"] = &MemSetChk;
 891   Optimizations["__strcpy_chk"] = &StrCpyChk;
 892   Optimizations["__stpcpy_chk"] = &StpCpyChk;
 893   Optimizations["__strncpy_chk"] = &StrNCpyChk;
 894   Optimizations["__stpncpy_chk"] = &StrNCpyChk;
 895
 896   // String and memory library call optimizations.
 897   addOpt(LibFunc::strcat, &StrCat);
 898   addOpt(LibFunc::strncat, &StrNCat);
 899   addOpt(LibFunc::strchr, &StrChr);
 900   addOpt(LibFunc::strrchr, &StrRChr);
 901   addOpt(LibFunc::strcmp, &StrCmp);
 902   addOpt(LibFunc::strncmp, &StrNCmp);
 903   addOpt(LibFunc::strcpy, &StrCpy);
 904   addOpt(LibFunc::stpcpy, &StpCpy);
 905   addOpt(LibFunc::strncpy, &StrNCpy);
 906   addOpt(LibFunc::strlen, &StrLen);
 907   addOpt(LibFunc::strpbrk, &StrPBrk);
 908   addOpt(LibFunc::strtol, &StrTo);
 909   addOpt(LibFunc::strtod, &StrTo);
 910   addOpt(LibFunc::strtof, &StrTo);
 911   addOpt(LibFunc::strtoul, &StrTo);
 912   addOpt(LibFunc::strtoll, &StrTo);
 913   addOpt(LibFunc::strtold, &StrTo);
 914   addOpt(LibFunc::strtoull, &StrTo);
 915   addOpt(LibFunc::strspn, &StrSpn);
 916   addOpt(LibFunc::strcspn, &StrCSpn);
 917 }
 918
 919 Value *LibCallSimplifierImpl::optimizeCall(CallInst *CI) {
 920   if (Optimizations.empty())
 921     initOptimizations();
 922
 923   Function *Callee = CI->getCalledFunction();
 924   LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
 925   if (LCO) {
 926     IRBuilder<> Builder(CI);
 927     return LCO->optimizeCall(CI, TD, TLI, LCS, Builder);
 928   }
 929   return 0;
 930 }
 931
 932 void LibCallSimplifierImpl::addOpt(LibFunc::Func F, LibCallOptimization* Opt) {
 933   if (TLI->has(F))
 934     Optimizations[TLI->getName(F)] = Opt;
 935 }
 936
 937 LibCallSimplifier::LibCallSimplifier(const DataLayout *TD,
 938                                      const TargetLibraryInfo *TLI) {
 939   Impl = new LibCallSimplifierImpl(TD, TLI, this);
 940 }
 941
 942 LibCallSimplifier::~LibCallSimplifier() {
 943   delete Impl;
 944 }
 945
 946 Value *LibCallSimplifier::optimizeCall(CallInst *CI) {
 947   return Impl->optimizeCall(CI);
 948 }
 949
 950 void LibCallSimplifier::replaceAllUsesWith(Instruction *I, Value *With) const {
 951   I->replaceAllUsesWith(With);
 952   I->eraseFromParent();
 953 }
 954
 955 }