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     LLVMContext &Context = CI->getParent()->getContext();
 126
 127     // Check if this has the right signature.
 128     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 129         !FT->getParamType(0)->isPointerTy() ||
 130         !FT->getParamType(1)->isPointerTy() ||
 131         FT->getParamType(2) != TD->getIntPtrType(Context) ||
 132         FT->getParamType(3) != TD->getIntPtrType(Context))
 133       return 0;
 134
 135     if (isFoldable(3, 2, false)) {
 136       B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
 137                      CI->getArgOperand(2), 1);
 138       return CI->getArgOperand(0);
 139     }
 140     return 0;
 141   }
 142 };
 143
 144 struct MemMoveChkOpt : public InstFortifiedLibCallOptimization {
 145   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 146     this->CI = CI;
 147     FunctionType *FT = Callee->getFunctionType();
 148     LLVMContext &Context = CI->getParent()->getContext();
 149
 150     // Check if this has the right signature.
 151     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 152         !FT->getParamType(0)->isPointerTy() ||
 153         !FT->getParamType(1)->isPointerTy() ||
 154         FT->getParamType(2) != TD->getIntPtrType(Context) ||
 155         FT->getParamType(3) != TD->getIntPtrType(Context))
 156       return 0;
 157
 158     if (isFoldable(3, 2, false)) {
 159       B.CreateMemMove(CI->getArgOperand(0), CI->getArgOperand(1),
 160                       CI->getArgOperand(2), 1);
 161       return CI->getArgOperand(0);
 162     }
 163     return 0;
 164   }
 165 };
 166
 167 struct MemSetChkOpt : public InstFortifiedLibCallOptimization {
 168   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 169     this->CI = CI;
 170     FunctionType *FT = Callee->getFunctionType();
 171     LLVMContext &Context = CI->getParent()->getContext();
 172
 173     // Check if this has the right signature.
 174     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 175         !FT->getParamType(0)->isPointerTy() ||
 176         !FT->getParamType(1)->isIntegerTy() ||
 177         FT->getParamType(2) != TD->getIntPtrType(Context) ||
 178         FT->getParamType(3) != TD->getIntPtrType(Context))
 179       return 0;
 180
 181     if (isFoldable(3, 2, false)) {
 182       Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(),
 183                                    false);
 184       B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1);
 185       return CI->getArgOperand(0);
 186     }
 187     return 0;
 188   }
 189 };
 190
 191 struct StrCpyChkOpt : public InstFortifiedLibCallOptimization {
 192   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 193     this->CI = CI;
 194     StringRef Name = Callee->getName();
 195     FunctionType *FT = Callee->getFunctionType();
 196     LLVMContext &Context = CI->getParent()->getContext();
 197
 198     // Check if this has the right signature.
 199     if (FT->getNumParams() != 3 ||
 200         FT->getReturnType() != FT->getParamType(0) ||
 201         FT->getParamType(0) != FT->getParamType(1) ||
 202         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
 203         FT->getParamType(2) != TD->getIntPtrType(Context))
 204       return 0;
 205
 206     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 207     if (Dst == Src)      // __strcpy_chk(x,x)  -> x
 208       return Src;
 209
 210     // If a) we don't have any length information, or b) we know this will
 211     // fit then just lower to a plain strcpy. Otherwise we'll keep our
 212     // strcpy_chk call which may fail at runtime if the size is too long.
 213     // TODO: It might be nice to get a maximum length out of the possible
 214     // string lengths for varying.
 215     if (isFoldable(2, 1, true)) {
 216       Value *Ret = EmitStrCpy(Dst, Src, B, TD, TLI, Name.substr(2, 6));
 217       return Ret;
 218     } else {
 219       // Maybe we can stil fold __strcpy_chk to __memcpy_chk.
 220       uint64_t Len = GetStringLength(Src);
 221       if (Len == 0) return 0;
 222
 223       // This optimization require DataLayout.
 224       if (!TD) return 0;
 225
 226       Value *Ret =
 227         EmitMemCpyChk(Dst, Src,
 228                       ConstantInt::get(TD->getIntPtrType(Context), Len),
 229                       CI->getArgOperand(2), B, TD, TLI);
 230       return Ret;
 231     }
 232     return 0;
 233   }
 234 };
 235
 236 struct StpCpyChkOpt : public InstFortifiedLibCallOptimization {
 237   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 238     this->CI = CI;
 239     StringRef Name = Callee->getName();
 240     FunctionType *FT = Callee->getFunctionType();
 241     LLVMContext &Context = CI->getParent()->getContext();
 242
 243     // Check if this has the right signature.
 244     if (FT->getNumParams() != 3 ||
 245         FT->getReturnType() != FT->getParamType(0) ||
 246         FT->getParamType(0) != FT->getParamType(1) ||
 247         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
 248         FT->getParamType(2) != TD->getIntPtrType(FT->getParamType(0)))
 249       return 0;
 250
 251     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 252     if (Dst == Src) {  // stpcpy(x,x)  -> x+strlen(x)
 253       Value *StrLen = EmitStrLen(Src, B, TD, TLI);
 254       return StrLen ? B.CreateInBoundsGEP(Dst, StrLen) : 0;
 255     }
 256
 257     // If a) we don't have any length information, or b) we know this will
 258     // fit then just lower to a plain stpcpy. Otherwise we'll keep our
 259     // stpcpy_chk call which may fail at runtime if the size is too long.
 260     // TODO: It might be nice to get a maximum length out of the possible
 261     // string lengths for varying.
 262     if (isFoldable(2, 1, true)) {
 263       Value *Ret = EmitStrCpy(Dst, Src, B, TD, TLI, Name.substr(2, 6));
 264       return Ret;
 265     } else {
 266       // Maybe we can stil fold __stpcpy_chk to __memcpy_chk.
 267       uint64_t Len = GetStringLength(Src);
 268       if (Len == 0) return 0;
 269
 270       // This optimization require DataLayout.
 271       if (!TD) return 0;
 272
 273       Type *PT = FT->getParamType(0);
 274       Value *LenV = ConstantInt::get(TD->getIntPtrType(PT), Len);
 275       Value *DstEnd = B.CreateGEP(Dst,
 276                                   ConstantInt::get(TD->getIntPtrType(PT),
 277                                                    Len - 1));
 278       if (!EmitMemCpyChk(Dst, Src, LenV, CI->getArgOperand(2), B, TD, TLI))
 279         return 0;
 280       return DstEnd;
 281     }
 282     return 0;
 283   }
 284 };
 285
 286 struct StrNCpyChkOpt : public InstFortifiedLibCallOptimization {
 287   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 288     this->CI = CI;
 289     StringRef Name = Callee->getName();
 290     FunctionType *FT = Callee->getFunctionType();
 291     LLVMContext &Context = CI->getParent()->getContext();
 292
 293     // Check if this has the right signature.
 294     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 295         FT->getParamType(0) != FT->getParamType(1) ||
 296         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
 297         !FT->getParamType(2)->isIntegerTy() ||
 298         FT->getParamType(3) != TD->getIntPtrType(Context))
 299       return 0;
 300
 301     if (isFoldable(3, 2, false)) {
 302       Value *Ret = EmitStrNCpy(CI->getArgOperand(0), CI->getArgOperand(1),
 303                                CI->getArgOperand(2), B, TD, TLI,
 304                                Name.substr(2, 7));
 305       return Ret;
 306     }
 307     return 0;
 308   }
 309 };
 310
 311 //===----------------------------------------------------------------------===//
 312 // String and Memory Library Call Optimizations
 313 //===----------------------------------------------------------------------===//
 314
 315 struct StrCatOpt : public LibCallOptimization {
 316   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 317     // Verify the "strcat" function prototype.
 318     FunctionType *FT = Callee->getFunctionType();
 319     if (FT->getNumParams() != 2 ||
 320         FT->getReturnType() != B.getInt8PtrTy() ||
 321         FT->getParamType(0) != FT->getReturnType() ||
 322         FT->getParamType(1) != FT->getReturnType())
 323       return 0;
 324
 325     // Extract some information from the instruction
 326     Value *Dst = CI->getArgOperand(0);
 327     Value *Src = CI->getArgOperand(1);
 328
 329     // See if we can get the length of the input string.
 330     uint64_t Len = GetStringLength(Src);
 331     if (Len == 0) return 0;
 332     --Len;  // Unbias length.
 333
 334     // Handle the simple, do-nothing case: strcat(x, "") -> x
 335     if (Len == 0)
 336       return Dst;
 337
 338     // These optimizations require DataLayout.
 339     if (!TD) return 0;
 340
 341     return emitStrLenMemCpy(Src, Dst, Len, B);
 342   }
 343
 344   Value *emitStrLenMemCpy(Value *Src, Value *Dst, uint64_t Len,
 345                           IRBuilder<> &B) {
 346     // We need to find the end of the destination string.  That's where the
 347     // memory is to be moved to. We just generate a call to strlen.
 348     Value *DstLen = EmitStrLen(Dst, B, TD, TLI);
 349     if (!DstLen)
 350       return 0;
 351
 352     // Now that we have the destination's length, we must index into the
 353     // destination's pointer to get the actual memcpy destination (end of
 354     // the string .. we're concatenating).
 355     Value *CpyDst = B.CreateGEP(Dst, DstLen, "endptr");
 356
 357     // We have enough information to now generate the memcpy call to do the
 358     // concatenation for us.  Make a memcpy to copy the nul byte with align = 1.
 359     B.CreateMemCpy(CpyDst, Src,
 360                    ConstantInt::get(TD->getIntPtrType(*Context), Len + 1), 1);
 361     return Dst;
 362   }
 363 };
 364
 365 struct StrNCatOpt : public StrCatOpt {
 366   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 367     // Verify the "strncat" function prototype.
 368     FunctionType *FT = Callee->getFunctionType();
 369     if (FT->getNumParams() != 3 ||
 370         FT->getReturnType() != B.getInt8PtrTy() ||
 371         FT->getParamType(0) != FT->getReturnType() ||
 372         FT->getParamType(1) != FT->getReturnType() ||
 373         !FT->getParamType(2)->isIntegerTy())
 374       return 0;
 375
 376     // Extract some information from the instruction
 377     Value *Dst = CI->getArgOperand(0);
 378     Value *Src = CI->getArgOperand(1);
 379     uint64_t Len;
 380
 381     // We don't do anything if length is not constant
 382     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
 383       Len = LengthArg->getZExtValue();
 384     else
 385       return 0;
 386
 387     // See if we can get the length of the input string.
 388     uint64_t SrcLen = GetStringLength(Src);
 389     if (SrcLen == 0) return 0;
 390     --SrcLen;  // Unbias length.
 391
 392     // Handle the simple, do-nothing cases:
 393     // strncat(x, "", c) -> x
 394     // strncat(x,  c, 0) -> x
 395     if (SrcLen == 0 || Len == 0) return Dst;
 396
 397     // These optimizations require DataLayout.
 398     if (!TD) return 0;
 399
 400     // We don't optimize this case
 401     if (Len < SrcLen) return 0;
 402
 403     // strncat(x, s, c) -> strcat(x, s)
 404     // s is constant so the strcat can be optimized further
 405     return emitStrLenMemCpy(Src, Dst, SrcLen, B);
 406   }
 407 };
 408
 409 struct StrChrOpt : public LibCallOptimization {
 410   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 411     // Verify the "strchr" function prototype.
 412     FunctionType *FT = Callee->getFunctionType();
 413     if (FT->getNumParams() != 2 ||
 414         FT->getReturnType() != B.getInt8PtrTy() ||
 415         FT->getParamType(0) != FT->getReturnType() ||
 416         !FT->getParamType(1)->isIntegerTy(32))
 417       return 0;
 418
 419     Value *SrcStr = CI->getArgOperand(0);
 420
 421     // If the second operand is non-constant, see if we can compute the length
 422     // of the input string and turn this into memchr.
 423     ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
 424     if (CharC == 0) {
 425       // These optimizations require DataLayout.
 426       if (!TD) return 0;
 427
 428       uint64_t Len = GetStringLength(SrcStr);
 429       if (Len == 0 || !FT->getParamType(1)->isIntegerTy(32))// memchr needs i32.
 430         return 0;
 431
 432       return EmitMemChr(SrcStr, CI->getArgOperand(1), // include nul.
 433                         ConstantInt::get(TD->getIntPtrType(*Context), Len),
 434                         B, TD, TLI);
 435     }
 436
 437     // Otherwise, the character is a constant, see if the first argument is
 438     // a string literal.  If so, we can constant fold.
 439     StringRef Str;
 440     if (!getConstantStringInfo(SrcStr, Str))
 441       return 0;
 442
 443     // Compute the offset, make sure to handle the case when we're searching for
 444     // zero (a weird way to spell strlen).
 445     size_t I = CharC->getSExtValue() == 0 ?
 446         Str.size() : Str.find(CharC->getSExtValue());
 447     if (I == StringRef::npos) // Didn't find the char.  strchr returns null.
 448       return Constant::getNullValue(CI->getType());
 449
 450     // strchr(s+n,c)  -> gep(s+n+i,c)
 451     return B.CreateGEP(SrcStr, B.getInt64(I), "strchr");
 452   }
 453 };
 454
 455 struct StrRChrOpt : public LibCallOptimization {
 456   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 457     // Verify the "strrchr" function prototype.
 458     FunctionType *FT = Callee->getFunctionType();
 459     if (FT->getNumParams() != 2 ||
 460         FT->getReturnType() != B.getInt8PtrTy() ||
 461         FT->getParamType(0) != FT->getReturnType() ||
 462         !FT->getParamType(1)->isIntegerTy(32))
 463       return 0;
 464
 465     Value *SrcStr = CI->getArgOperand(0);
 466     ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
 467
 468     // Cannot fold anything if we're not looking for a constant.
 469     if (!CharC)
 470       return 0;
 471
 472     StringRef Str;
 473     if (!getConstantStringInfo(SrcStr, Str)) {
 474       // strrchr(s, 0) -> strchr(s, 0)
 475       if (TD && CharC->isZero())
 476         return EmitStrChr(SrcStr, '\0', B, TD, TLI);
 477       return 0;
 478     }
 479
 480     // Compute the offset.
 481     size_t I = CharC->getSExtValue() == 0 ?
 482         Str.size() : Str.rfind(CharC->getSExtValue());
 483     if (I == StringRef::npos) // Didn't find the char. Return null.
 484       return Constant::getNullValue(CI->getType());
 485
 486     // strrchr(s+n,c) -> gep(s+n+i,c)
 487     return B.CreateGEP(SrcStr, B.getInt64(I), "strrchr");
 488   }
 489 };
 490
 491 struct StrCmpOpt : public LibCallOptimization {
 492   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 493     // Verify the "strcmp" function prototype.
 494     FunctionType *FT = Callee->getFunctionType();
 495     if (FT->getNumParams() != 2 ||
 496         !FT->getReturnType()->isIntegerTy(32) ||
 497         FT->getParamType(0) != FT->getParamType(1) ||
 498         FT->getParamType(0) != B.getInt8PtrTy())
 499       return 0;
 500
 501     Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
 502     if (Str1P == Str2P)      // strcmp(x,x)  -> 0
 503       return ConstantInt::get(CI->getType(), 0);
 504
 505     StringRef Str1, Str2;
 506     bool HasStr1 = getConstantStringInfo(Str1P, Str1);
 507     bool HasStr2 = getConstantStringInfo(Str2P, Str2);
 508
 509     // strcmp(x, y)  -> cnst  (if both x and y are constant strings)
 510     if (HasStr1 && HasStr2)
 511       return ConstantInt::get(CI->getType(), Str1.compare(Str2));
 512
 513     if (HasStr1 && Str1.empty()) // strcmp("", x) -> -*x
 514       return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"),
 515                                       CI->getType()));
 516
 517     if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x
 518       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
 519
 520     // strcmp(P, "x") -> memcmp(P, "x", 2)
 521     uint64_t Len1 = GetStringLength(Str1P);
 522     uint64_t Len2 = GetStringLength(Str2P);
 523     if (Len1 && Len2) {
 524       // These optimizations require DataLayout.
 525       if (!TD) return 0;
 526
 527       return EmitMemCmp(Str1P, Str2P,
 528                         ConstantInt::get(TD->getIntPtrType(*Context),
 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(*Context), 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 struct StrSpnOpt : public LibCallOptimization {
 776   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 777     FunctionType *FT = Callee->getFunctionType();
 778     if (FT->getNumParams() != 2 ||
 779         FT->getParamType(0) != B.getInt8PtrTy() ||
 780         FT->getParamType(1) != FT->getParamType(0) ||
 781         !FT->getReturnType()->isIntegerTy())
 782       return 0;
 783
 784     StringRef S1, S2;
 785     bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
 786     bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
 787
 788     // strspn(s, "") -> 0
 789     // strspn("", s) -> 0
 790     if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))
 791       return Constant::getNullValue(CI->getType());
 792
 793     // Constant folding.
 794     if (HasS1 && HasS2) {
 795       size_t Pos = S1.find_first_not_of(S2);
 796       if (Pos == StringRef::npos) Pos = S1.size();
 797       return ConstantInt::get(CI->getType(), Pos);
 798     }
 799
 800     return 0;
 801   }
 802 };
 803
 804 struct StrCSpnOpt : public LibCallOptimization {
 805   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 806     FunctionType *FT = Callee->getFunctionType();
 807     if (FT->getNumParams() != 2 ||
 808         FT->getParamType(0) != B.getInt8PtrTy() ||
 809         FT->getParamType(1) != FT->getParamType(0) ||
 810         !FT->getReturnType()->isIntegerTy())
 811       return 0;
 812
 813     StringRef S1, S2;
 814     bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
 815     bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
 816
 817     // strcspn("", s) -> 0
 818     if (HasS1 && S1.empty())
 819       return Constant::getNullValue(CI->getType());
 820
 821     // Constant folding.
 822     if (HasS1 && HasS2) {
 823       size_t Pos = S1.find_first_of(S2);
 824       if (Pos == StringRef::npos) Pos = S1.size();
 825       return ConstantInt::get(CI->getType(), Pos);
 826     }
 827
 828     // strcspn(s, "") -> strlen(s)
 829     if (TD && HasS2 && S2.empty())
 830       return EmitStrLen(CI->getArgOperand(0), B, TD, TLI);
 831
 832     return 0;
 833   }
 834 };
 835
 836 } // End anonymous namespace.
 837
 838 namespace llvm {
 839
 840 class LibCallSimplifierImpl {
 841   const DataLayout *TD;
 842   const TargetLibraryInfo *TLI;
 843   StringMap<LibCallOptimization*> Optimizations;
 844
 845   // Fortified library call optimizations.
 846   MemCpyChkOpt MemCpyChk;
 847   MemMoveChkOpt MemMoveChk;
 848   MemSetChkOpt MemSetChk;
 849   StrCpyChkOpt StrCpyChk;
 850   StpCpyChkOpt StpCpyChk;
 851   StrNCpyChkOpt StrNCpyChk;
 852
 853   // String and memory library call optimizations.
 854   StrCatOpt StrCat;
 855   StrNCatOpt StrNCat;
 856   StrChrOpt StrChr;
 857   StrRChrOpt StrRChr;
 858   StrCmpOpt StrCmp;
 859   StrNCmpOpt StrNCmp;
 860   StrCpyOpt StrCpy;
 861   StpCpyOpt StpCpy;
 862   StrNCpyOpt StrNCpy;
 863   StrLenOpt StrLen;
 864   StrPBrkOpt StrPBrk;
 865   StrToOpt StrTo;
 866   StrSpnOpt StrSpn;
 867   StrCSpnOpt StrCSpn;
 868
 869   void initOptimizations();
 870   void addOpt(LibFunc::Func F, LibCallOptimization* Opt);
 871 public:
 872   LibCallSimplifierImpl(const DataLayout *TD, const TargetLibraryInfo *TLI) {
 873     this->TD = TD;
 874     this->TLI = TLI;
 875   }
 876
 877   Value *optimizeCall(CallInst *CI);
 878 };
 879
 880 void LibCallSimplifierImpl::initOptimizations() {
 881   // Fortified library call optimizations.
 882   Optimizations["__memcpy_chk"] = &MemCpyChk;
 883   Optimizations["__memmove_chk"] = &MemMoveChk;
 884   Optimizations["__memset_chk"] = &MemSetChk;
 885   Optimizations["__strcpy_chk"] = &StrCpyChk;
 886   Optimizations["__stpcpy_chk"] = &StpCpyChk;
 887   Optimizations["__strncpy_chk"] = &StrNCpyChk;
 888   Optimizations["__stpncpy_chk"] = &StrNCpyChk;
 889
 890   // String and memory library call optimizations.
 891   addOpt(LibFunc::strcat, &StrCat);
 892   addOpt(LibFunc::strncat, &StrNCat);
 893   addOpt(LibFunc::strchr, &StrChr);
 894   addOpt(LibFunc::strrchr, &StrRChr);
 895   addOpt(LibFunc::strcmp, &StrCmp);
 896   addOpt(LibFunc::strncmp, &StrNCmp);
 897   addOpt(LibFunc::strcpy, &StrCpy);
 898   addOpt(LibFunc::stpcpy, &StpCpy);
 899   addOpt(LibFunc::strncpy, &StrNCpy);
 900   addOpt(LibFunc::strlen, &StrLen);
 901   addOpt(LibFunc::strpbrk, &StrPBrk);
 902   addOpt(LibFunc::strtol, &StrTo);
 903   addOpt(LibFunc::strtod, &StrTo);
 904   addOpt(LibFunc::strtof, &StrTo);
 905   addOpt(LibFunc::strtoul, &StrTo);
 906   addOpt(LibFunc::strtoll, &StrTo);
 907   addOpt(LibFunc::strtold, &StrTo);
 908   addOpt(LibFunc::strtoull, &StrTo);
 909   addOpt(LibFunc::strspn, &StrSpn);
 910   addOpt(LibFunc::strcspn, &StrCSpn);
 911 }
 912
 913 Value *LibCallSimplifierImpl::optimizeCall(CallInst *CI) {
 914   if (Optimizations.empty())
 915     initOptimizations();
 916
 917   Function *Callee = CI->getCalledFunction();
 918   LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
 919   if (LCO) {
 920     IRBuilder<> Builder(CI);
 921     return LCO->optimizeCall(CI, TD, TLI, Builder);
 922   }
 923   return 0;
 924 }
 925
 926 void LibCallSimplifierImpl::addOpt(LibFunc::Func F, LibCallOptimization* Opt) {
 927   if (TLI->has(F))
 928     Optimizations[TLI->getName(F)] = Opt;
 929 }
 930
 931 LibCallSimplifier::LibCallSimplifier(const DataLayout *TD,
 932                                      const TargetLibraryInfo *TLI) {
 933   Impl = new LibCallSimplifierImpl(TD, TLI);
 934 }
 935
 936 LibCallSimplifier::~LibCallSimplifier() {
 937   delete Impl;
 938 }
 939
 940 Value *LibCallSimplifier::optimizeCall(CallInst *CI) {
 941   return Impl->optimizeCall(CI);
 942 }
 943
 944 }