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