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 // Fortified Library Call Optimizations
  68 //===----------------------------------------------------------------------===//
  69
  70 struct FortifiedLibCallOptimization : public LibCallOptimization {
  71 protected:
  72   virtual bool isFoldable(unsigned SizeCIOp, unsigned SizeArgOp,
  73                           bool isString) const = 0;
  74 };
  75
  76 struct InstFortifiedLibCallOptimization : public FortifiedLibCallOptimization {
  77   CallInst *CI;
  78
  79   bool isFoldable(unsigned SizeCIOp, unsigned SizeArgOp, bool isString) const {
  80     if (CI->getArgOperand(SizeCIOp) == CI->getArgOperand(SizeArgOp))
  81       return true;
  82     if (ConstantInt *SizeCI =
  83                            dyn_cast<ConstantInt>(CI->getArgOperand(SizeCIOp))) {
  84       if (SizeCI->isAllOnesValue())
  85         return true;
  86       if (isString) {
  87         uint64_t Len = GetStringLength(CI->getArgOperand(SizeArgOp));
  88         // If the length is 0 we don't know how long it is and so we can't
  89         // remove the check.
  90         if (Len == 0) return false;
  91         return SizeCI->getZExtValue() >= Len;
  92       }
  93       if (ConstantInt *Arg = dyn_cast<ConstantInt>(
  94                                                   CI->getArgOperand(SizeArgOp)))
  95         return SizeCI->getZExtValue() >= Arg->getZExtValue();
  96     }
  97     return false;
  98   }
  99 };
 100
 101 struct MemCpyChkOpt : public InstFortifiedLibCallOptimization {
 102   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 103     this->CI = CI;
 104     FunctionType *FT = Callee->getFunctionType();
 105
 106     // Check if this has the right signature.
 107     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 108         !FT->getParamType(0)->isPointerTy() ||
 109         !FT->getParamType(1)->isPointerTy() ||
 110         FT->getParamType(2) != TD->getIntPtrType(FT->getParamType(0)) ||
 111         FT->getParamType(3) != TD->getIntPtrType(FT->getParamType(1)))
 112       return 0;
 113
 114     if (isFoldable(3, 2, false)) {
 115       B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
 116                      CI->getArgOperand(2), 1);
 117       return CI->getArgOperand(0);
 118     }
 119     return 0;
 120   }
 121 };
 122
 123 struct MemMoveChkOpt : public InstFortifiedLibCallOptimization {
 124   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 125     this->CI = CI;
 126     FunctionType *FT = Callee->getFunctionType();
 127
 128     // Check if this has the right signature.
 129     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 130         !FT->getParamType(0)->isPointerTy() ||
 131         !FT->getParamType(1)->isPointerTy() ||
 132         FT->getParamType(2) != TD->getIntPtrType(FT->getParamType(0)) ||
 133         FT->getParamType(3) != TD->getIntPtrType(FT->getParamType(1)))
 134       return 0;
 135
 136     if (isFoldable(3, 2, false)) {
 137       B.CreateMemMove(CI->getArgOperand(0), CI->getArgOperand(1),
 138                       CI->getArgOperand(2), 1);
 139       return CI->getArgOperand(0);
 140     }
 141     return 0;
 142   }
 143 };
 144
 145 struct MemSetChkOpt : public InstFortifiedLibCallOptimization {
 146   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 147     this->CI = CI;
 148     FunctionType *FT = Callee->getFunctionType();
 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)->isIntegerTy() ||
 154         FT->getParamType(2) != TD->getIntPtrType(FT->getParamType(0)) ||
 155         FT->getParamType(3) != TD->getIntPtrType(FT->getParamType(0)))
 156       return 0;
 157
 158     if (isFoldable(3, 2, false)) {
 159       Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(),
 160                                    false);
 161       B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1);
 162       return CI->getArgOperand(0);
 163     }
 164     return 0;
 165   }
 166 };
 167
 168 struct StrCpyChkOpt : public InstFortifiedLibCallOptimization {
 169   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 170     this->CI = CI;
 171     StringRef Name = Callee->getName();
 172     FunctionType *FT = Callee->getFunctionType();
 173     LLVMContext &Context = CI->getParent()->getContext();
 174
 175     // Check if this has the right signature.
 176     if (FT->getNumParams() != 3 ||
 177         FT->getReturnType() != FT->getParamType(0) ||
 178         FT->getParamType(0) != FT->getParamType(1) ||
 179         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
 180         FT->getParamType(2) != TD->getIntPtrType(FT->getParamType(0)))
 181       return 0;
 182
 183     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 184     if (Dst == Src)      // __strcpy_chk(x,x)  -> x
 185       return Src;
 186
 187     // If a) we don't have any length information, or b) we know this will
 188     // fit then just lower to a plain strcpy. Otherwise we'll keep our
 189     // strcpy_chk call which may fail at runtime if the size is too long.
 190     // TODO: It might be nice to get a maximum length out of the possible
 191     // string lengths for varying.
 192     if (isFoldable(2, 1, true)) {
 193       Value *Ret = EmitStrCpy(Dst, Src, B, TD, TLI, Name.substr(2, 6));
 194       return Ret;
 195     } else {
 196       // Maybe we can stil fold __strcpy_chk to __memcpy_chk.
 197       uint64_t Len = GetStringLength(Src);
 198       if (Len == 0) return 0;
 199
 200       // This optimization require DataLayout.
 201       if (!TD) return 0;
 202
 203       Value *Ret =
 204         EmitMemCpyChk(Dst, Src,
 205                       ConstantInt::get(TD->getIntPtrType(Dst->getType()),
 206                       Len), CI->getArgOperand(2), B, TD, TLI);
 207       return Ret;
 208     }
 209     return 0;
 210   }
 211 };
 212
 213 struct StpCpyChkOpt : public InstFortifiedLibCallOptimization {
 214   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 215     this->CI = CI;
 216     StringRef Name = Callee->getName();
 217     FunctionType *FT = Callee->getFunctionType();
 218     LLVMContext &Context = CI->getParent()->getContext();
 219
 220     // Check if this has the right signature.
 221     if (FT->getNumParams() != 3 ||
 222         FT->getReturnType() != FT->getParamType(0) ||
 223         FT->getParamType(0) != FT->getParamType(1) ||
 224         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
 225         FT->getParamType(2) != TD->getIntPtrType(FT->getParamType(0)))
 226       return 0;
 227
 228     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 229     if (Dst == Src) {  // stpcpy(x,x)  -> x+strlen(x)
 230       Value *StrLen = EmitStrLen(Src, B, TD, TLI);
 231       return StrLen ? B.CreateInBoundsGEP(Dst, StrLen) : 0;
 232     }
 233
 234     // If a) we don't have any length information, or b) we know this will
 235     // fit then just lower to a plain stpcpy. Otherwise we'll keep our
 236     // stpcpy_chk call which may fail at runtime if the size is too long.
 237     // TODO: It might be nice to get a maximum length out of the possible
 238     // string lengths for varying.
 239     if (isFoldable(2, 1, true)) {
 240       Value *Ret = EmitStrCpy(Dst, Src, B, TD, TLI, Name.substr(2, 6));
 241       return Ret;
 242     } else {
 243       // Maybe we can stil fold __stpcpy_chk to __memcpy_chk.
 244       uint64_t Len = GetStringLength(Src);
 245       if (Len == 0) return 0;
 246
 247       // This optimization require DataLayout.
 248       if (!TD) return 0;
 249
 250       Type *PT = FT->getParamType(0);
 251       Value *LenV = ConstantInt::get(TD->getIntPtrType(PT), Len);
 252       Value *DstEnd = B.CreateGEP(Dst,
 253                                   ConstantInt::get(TD->getIntPtrType(PT),
 254                                                    Len - 1));
 255       if (!EmitMemCpyChk(Dst, Src, LenV, CI->getArgOperand(2), B, TD, TLI))
 256         return 0;
 257       return DstEnd;
 258     }
 259     return 0;
 260   }
 261 };
 262
 263 struct StrNCpyChkOpt : public InstFortifiedLibCallOptimization {
 264   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 265     this->CI = CI;
 266     StringRef Name = Callee->getName();
 267     FunctionType *FT = Callee->getFunctionType();
 268     LLVMContext &Context = CI->getParent()->getContext();
 269
 270     // Check if this has the right signature.
 271     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
 272         FT->getParamType(0) != FT->getParamType(1) ||
 273         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
 274         !FT->getParamType(2)->isIntegerTy() ||
 275         FT->getParamType(3) != TD->getIntPtrType(FT->getParamType(0)))
 276       return 0;
 277
 278     if (isFoldable(3, 2, false)) {
 279       Value *Ret = EmitStrNCpy(CI->getArgOperand(0), CI->getArgOperand(1),
 280                                CI->getArgOperand(2), B, TD, TLI,
 281                                Name.substr(2, 7));
 282       return Ret;
 283     }
 284     return 0;
 285   }
 286 };
 287
 288 //===----------------------------------------------------------------------===//
 289 // String and Memory Library Call Optimizations
 290 //===----------------------------------------------------------------------===//
 291
 292 struct StrCatOpt : public LibCallOptimization {
 293   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 294     // Verify the "strcat" function prototype.
 295     FunctionType *FT = Callee->getFunctionType();
 296     if (FT->getNumParams() != 2 ||
 297         FT->getReturnType() != B.getInt8PtrTy() ||
 298         FT->getParamType(0) != FT->getReturnType() ||
 299         FT->getParamType(1) != FT->getReturnType())
 300       return 0;
 301
 302     // Extract some information from the instruction
 303     Value *Dst = CI->getArgOperand(0);
 304     Value *Src = CI->getArgOperand(1);
 305
 306     // See if we can get the length of the input string.
 307     uint64_t Len = GetStringLength(Src);
 308     if (Len == 0) return 0;
 309     --Len;  // Unbias length.
 310
 311     // Handle the simple, do-nothing case: strcat(x, "") -> x
 312     if (Len == 0)
 313       return Dst;
 314
 315     // These optimizations require DataLayout.
 316     if (!TD) return 0;
 317
 318     return emitStrLenMemCpy(Src, Dst, Len, B);
 319   }
 320
 321   Value *emitStrLenMemCpy(Value *Src, Value *Dst, uint64_t Len,
 322                           IRBuilder<> &B) {
 323     // We need to find the end of the destination string.  That's where the
 324     // memory is to be moved to. We just generate a call to strlen.
 325     Value *DstLen = EmitStrLen(Dst, B, TD, TLI);
 326     if (!DstLen)
 327       return 0;
 328
 329     // Now that we have the destination's length, we must index into the
 330     // destination's pointer to get the actual memcpy destination (end of
 331     // the string .. we're concatenating).
 332     Value *CpyDst = B.CreateGEP(Dst, DstLen, "endptr");
 333
 334     // We have enough information to now generate the memcpy call to do the
 335     // concatenation for us.  Make a memcpy to copy the nul byte with align = 1.
 336     B.CreateMemCpy(CpyDst, Src,
 337                    ConstantInt::get(TD->getIntPtrType(Src->getType()),
 338                    Len + 1), 1);
 339     return Dst;
 340   }
 341 };
 342
 343 struct StrNCatOpt : public StrCatOpt {
 344   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 345     // Verify the "strncat" function prototype.
 346     FunctionType *FT = Callee->getFunctionType();
 347     if (FT->getNumParams() != 3 ||
 348         FT->getReturnType() != B.getInt8PtrTy() ||
 349         FT->getParamType(0) != FT->getReturnType() ||
 350         FT->getParamType(1) != FT->getReturnType() ||
 351         !FT->getParamType(2)->isIntegerTy())
 352       return 0;
 353
 354     // Extract some information from the instruction
 355     Value *Dst = CI->getArgOperand(0);
 356     Value *Src = CI->getArgOperand(1);
 357     uint64_t Len;
 358
 359     // We don't do anything if length is not constant
 360     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
 361       Len = LengthArg->getZExtValue();
 362     else
 363       return 0;
 364
 365     // See if we can get the length of the input string.
 366     uint64_t SrcLen = GetStringLength(Src);
 367     if (SrcLen == 0) return 0;
 368     --SrcLen;  // Unbias length.
 369
 370     // Handle the simple, do-nothing cases:
 371     // strncat(x, "", c) -> x
 372     // strncat(x,  c, 0) -> x
 373     if (SrcLen == 0 || Len == 0) return Dst;
 374
 375     // These optimizations require DataLayout.
 376     if (!TD) return 0;
 377
 378     // We don't optimize this case
 379     if (Len < SrcLen) return 0;
 380
 381     // strncat(x, s, c) -> strcat(x, s)
 382     // s is constant so the strcat can be optimized further
 383     return emitStrLenMemCpy(Src, Dst, SrcLen, B);
 384   }
 385 };
 386
 387 struct StrChrOpt : public LibCallOptimization {
 388   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 389     // Verify the "strchr" function prototype.
 390     FunctionType *FT = Callee->getFunctionType();
 391     if (FT->getNumParams() != 2 ||
 392         FT->getReturnType() != B.getInt8PtrTy() ||
 393         FT->getParamType(0) != FT->getReturnType() ||
 394         !FT->getParamType(1)->isIntegerTy(32))
 395       return 0;
 396
 397     Value *SrcStr = CI->getArgOperand(0);
 398
 399     // If the second operand is non-constant, see if we can compute the length
 400     // of the input string and turn this into memchr.
 401     ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
 402     if (CharC == 0) {
 403       // These optimizations require DataLayout.
 404       if (!TD) return 0;
 405
 406       uint64_t Len = GetStringLength(SrcStr);
 407       if (Len == 0 || !FT->getParamType(1)->isIntegerTy(32))// memchr needs i32.
 408         return 0;
 409
 410       Type *PT = FT->getParamType(0);
 411       return EmitMemChr(SrcStr, CI->getArgOperand(1), // include nul.
 412                         ConstantInt::get(TD->getIntPtrType(PT), Len),
 413                         B, TD, TLI);
 414     }
 415
 416     // Otherwise, the character is a constant, see if the first argument is
 417     // a string literal.  If so, we can constant fold.
 418     StringRef Str;
 419     if (!getConstantStringInfo(SrcStr, Str))
 420       return 0;
 421
 422     // Compute the offset, make sure to handle the case when we're searching for
 423     // zero (a weird way to spell strlen).
 424     size_t I = CharC->getSExtValue() == 0 ?
 425         Str.size() : Str.find(CharC->getSExtValue());
 426     if (I == StringRef::npos) // Didn't find the char.  strchr returns null.
 427       return Constant::getNullValue(CI->getType());
 428
 429     // strchr(s+n,c)  -> gep(s+n+i,c)
 430     return B.CreateGEP(SrcStr, B.getInt64(I), "strchr");
 431   }
 432 };
 433
 434 struct StrRChrOpt : public LibCallOptimization {
 435   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 436     // Verify the "strrchr" function prototype.
 437     FunctionType *FT = Callee->getFunctionType();
 438     if (FT->getNumParams() != 2 ||
 439         FT->getReturnType() != B.getInt8PtrTy() ||
 440         FT->getParamType(0) != FT->getReturnType() ||
 441         !FT->getParamType(1)->isIntegerTy(32))
 442       return 0;
 443
 444     Value *SrcStr = CI->getArgOperand(0);
 445     ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
 446
 447     // Cannot fold anything if we're not looking for a constant.
 448     if (!CharC)
 449       return 0;
 450
 451     StringRef Str;
 452     if (!getConstantStringInfo(SrcStr, Str)) {
 453       // strrchr(s, 0) -> strchr(s, 0)
 454       if (TD && CharC->isZero())
 455         return EmitStrChr(SrcStr, '\0', B, TD, TLI);
 456       return 0;
 457     }
 458
 459     // Compute the offset.
 460     size_t I = CharC->getSExtValue() == 0 ?
 461         Str.size() : Str.rfind(CharC->getSExtValue());
 462     if (I == StringRef::npos) // Didn't find the char. Return null.
 463       return Constant::getNullValue(CI->getType());
 464
 465     // strrchr(s+n,c) -> gep(s+n+i,c)
 466     return B.CreateGEP(SrcStr, B.getInt64(I), "strrchr");
 467   }
 468 };
 469
 470 struct StrCmpOpt : public LibCallOptimization {
 471   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 472     // Verify the "strcmp" function prototype.
 473     FunctionType *FT = Callee->getFunctionType();
 474     if (FT->getNumParams() != 2 ||
 475         !FT->getReturnType()->isIntegerTy(32) ||
 476         FT->getParamType(0) != FT->getParamType(1) ||
 477         FT->getParamType(0) != B.getInt8PtrTy())
 478       return 0;
 479
 480     Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
 481     if (Str1P == Str2P)      // strcmp(x,x)  -> 0
 482       return ConstantInt::get(CI->getType(), 0);
 483
 484     StringRef Str1, Str2;
 485     bool HasStr1 = getConstantStringInfo(Str1P, Str1);
 486     bool HasStr2 = getConstantStringInfo(Str2P, Str2);
 487
 488     // strcmp(x, y)  -> cnst  (if both x and y are constant strings)
 489     if (HasStr1 && HasStr2)
 490       return ConstantInt::get(CI->getType(), Str1.compare(Str2));
 491
 492     if (HasStr1 && Str1.empty()) // strcmp("", x) -> -*x
 493       return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"),
 494                                       CI->getType()));
 495
 496     if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x
 497       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
 498
 499     // strcmp(P, "x") -> memcmp(P, "x", 2)
 500     uint64_t Len1 = GetStringLength(Str1P);
 501     uint64_t Len2 = GetStringLength(Str2P);
 502     if (Len1 && Len2) {
 503       // These optimizations require DataLayout.
 504       if (!TD) return 0;
 505
 506       Type *PT = FT->getParamType(0);
 507       return EmitMemCmp(Str1P, Str2P,
 508                         ConstantInt::get(TD->getIntPtrType(PT),
 509                         std::min(Len1, Len2)), B, TD, TLI);
 510     }
 511
 512     return 0;
 513   }
 514 };
 515
 516 struct StrNCmpOpt : public LibCallOptimization {
 517   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 518     // Verify the "strncmp" function prototype.
 519     FunctionType *FT = Callee->getFunctionType();
 520     if (FT->getNumParams() != 3 ||
 521         !FT->getReturnType()->isIntegerTy(32) ||
 522         FT->getParamType(0) != FT->getParamType(1) ||
 523         FT->getParamType(0) != B.getInt8PtrTy() ||
 524         !FT->getParamType(2)->isIntegerTy())
 525       return 0;
 526
 527     Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
 528     if (Str1P == Str2P)      // strncmp(x,x,n)  -> 0
 529       return ConstantInt::get(CI->getType(), 0);
 530
 531     // Get the length argument if it is constant.
 532     uint64_t Length;
 533     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
 534       Length = LengthArg->getZExtValue();
 535     else
 536       return 0;
 537
 538     if (Length == 0) // strncmp(x,y,0)   -> 0
 539       return ConstantInt::get(CI->getType(), 0);
 540
 541     if (TD && Length == 1) // strncmp(x,y,1) -> memcmp(x,y,1)
 542       return EmitMemCmp(Str1P, Str2P, CI->getArgOperand(2), B, TD, TLI);
 543
 544     StringRef Str1, Str2;
 545     bool HasStr1 = getConstantStringInfo(Str1P, Str1);
 546     bool HasStr2 = getConstantStringInfo(Str2P, Str2);
 547
 548     // strncmp(x, y)  -> cnst  (if both x and y are constant strings)
 549     if (HasStr1 && HasStr2) {
 550       StringRef SubStr1 = Str1.substr(0, Length);
 551       StringRef SubStr2 = Str2.substr(0, Length);
 552       return ConstantInt::get(CI->getType(), SubStr1.compare(SubStr2));
 553     }
 554
 555     if (HasStr1 && Str1.empty())  // strncmp("", x, n) -> -*x
 556       return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"),
 557                                       CI->getType()));
 558
 559     if (HasStr2 && Str2.empty())  // strncmp(x, "", n) -> *x
 560       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
 561
 562     return 0;
 563   }
 564 };
 565
 566 struct StrCpyOpt : public LibCallOptimization {
 567   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 568     // Verify the "strcpy" function prototype.
 569     FunctionType *FT = Callee->getFunctionType();
 570     if (FT->getNumParams() != 2 ||
 571         FT->getReturnType() != FT->getParamType(0) ||
 572         FT->getParamType(0) != FT->getParamType(1) ||
 573         FT->getParamType(0) != B.getInt8PtrTy())
 574       return 0;
 575
 576     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 577     if (Dst == Src)      // strcpy(x,x)  -> x
 578       return Src;
 579
 580     // These optimizations require DataLayout.
 581     if (!TD) return 0;
 582
 583     // See if we can get the length of the input string.
 584     uint64_t Len = GetStringLength(Src);
 585     if (Len == 0) return 0;
 586
 587     // We have enough information to now generate the memcpy call to do the
 588     // copy for us.  Make a memcpy to copy the nul byte with align = 1.
 589     B.CreateMemCpy(Dst, Src,
 590                    ConstantInt::get(TD->getIntPtrType(Dst->getType()), Len), 1);
 591     return Dst;
 592   }
 593 };
 594
 595 struct StpCpyOpt: public LibCallOptimization {
 596   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 597     // Verify the "stpcpy" function prototype.
 598     FunctionType *FT = Callee->getFunctionType();
 599     if (FT->getNumParams() != 2 ||
 600         FT->getReturnType() != FT->getParamType(0) ||
 601         FT->getParamType(0) != FT->getParamType(1) ||
 602         FT->getParamType(0) != B.getInt8PtrTy())
 603       return 0;
 604
 605     // These optimizations require DataLayout.
 606     if (!TD) return 0;
 607
 608     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
 609     if (Dst == Src) {  // stpcpy(x,x)  -> x+strlen(x)
 610       Value *StrLen = EmitStrLen(Src, B, TD, TLI);
 611       return StrLen ? B.CreateInBoundsGEP(Dst, StrLen) : 0;
 612     }
 613
 614     // See if we can get the length of the input string.
 615     uint64_t Len = GetStringLength(Src);
 616     if (Len == 0) return 0;
 617
 618     Type *PT = FT->getParamType(0);
 619     Value *LenV = ConstantInt::get(TD->getIntPtrType(PT), Len);
 620     Value *DstEnd = B.CreateGEP(Dst,
 621                                 ConstantInt::get(TD->getIntPtrType(PT),
 622                                                  Len - 1));
 623
 624     // We have enough information to now generate the memcpy call to do the
 625     // copy for us.  Make a memcpy to copy the nul byte with align = 1.
 626     B.CreateMemCpy(Dst, Src, LenV, 1);
 627     return DstEnd;
 628   }
 629 };
 630
 631 } // End anonymous namespace.
 632
 633 namespace llvm {
 634
 635 class LibCallSimplifierImpl {
 636   const DataLayout *TD;
 637   const TargetLibraryInfo *TLI;
 638   StringMap<LibCallOptimization*> Optimizations;
 639
 640   // Fortified library call optimizations.
 641   MemCpyChkOpt MemCpyChk;
 642   MemMoveChkOpt MemMoveChk;
 643   MemSetChkOpt MemSetChk;
 644   StrCpyChkOpt StrCpyChk;
 645   StpCpyChkOpt StpCpyChk;
 646   StrNCpyChkOpt StrNCpyChk;
 647
 648   // String and memory library call optimizations.
 649   StrCatOpt StrCat;
 650   StrNCatOpt StrNCat;
 651   StrChrOpt StrChr;
 652   StrRChrOpt StrRChr;
 653   StrCmpOpt StrCmp;
 654   StrNCmpOpt StrNCmp;
 655   StrCpyOpt StrCpy;
 656   StpCpyOpt StpCpy;
 657
 658   void initOptimizations();
 659 public:
 660   LibCallSimplifierImpl(const DataLayout *TD, const TargetLibraryInfo *TLI) {
 661     this->TD = TD;
 662     this->TLI = TLI;
 663   }
 664
 665   Value *optimizeCall(CallInst *CI);
 666 };
 667
 668 void LibCallSimplifierImpl::initOptimizations() {
 669   // Fortified library call optimizations.
 670   Optimizations["__memcpy_chk"] = &MemCpyChk;
 671   Optimizations["__memmove_chk"] = &MemMoveChk;
 672   Optimizations["__memset_chk"] = &MemSetChk;
 673   Optimizations["__strcpy_chk"] = &StrCpyChk;
 674   Optimizations["__stpcpy_chk"] = &StpCpyChk;
 675   Optimizations["__strncpy_chk"] = &StrNCpyChk;
 676   Optimizations["__stpncpy_chk"] = &StrNCpyChk;
 677
 678   // String and memory library call optimizations.
 679   Optimizations["strcat"] = &StrCat;
 680   Optimizations["strncat"] = &StrNCat;
 681   Optimizations["strchr"] = &StrChr;
 682   Optimizations["strrchr"] = &StrRChr;
 683   Optimizations["strcmp"] = &StrCmp;
 684   Optimizations["strncmp"] = &StrNCmp;
 685   Optimizations["strcpy"] = &StrCpy;
 686   Optimizations["stpcpy"] = &StpCpy;
 687 }
 688
 689 Value *LibCallSimplifierImpl::optimizeCall(CallInst *CI) {
 690   if (Optimizations.empty())
 691     initOptimizations();
 692
 693   Function *Callee = CI->getCalledFunction();
 694   LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
 695   if (LCO) {
 696     IRBuilder<> Builder(CI);
 697     return LCO->optimizeCall(CI, TD, TLI, Builder);
 698   }
 699   return 0;
 700 }
 701
 702 LibCallSimplifier::LibCallSimplifier(const DataLayout *TD,
 703                                      const TargetLibraryInfo *TLI) {
 704   Impl = new LibCallSimplifierImpl(TD, TLI);
 705 }
 706
 707 LibCallSimplifier::~LibCallSimplifier() {
 708   delete Impl;
 709 }
 710
 711 Value *LibCallSimplifier::optimizeCall(CallInst *CI) {
 712   return Impl->optimizeCall(CI);
 713 }
 714
 715 }