SimplifyLibCalls.cpp revision 7629de3326318e533ab969abd1b0cbc569b3f3b7 
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
27using namespace llvm;
28
29/// This class is the abstract base class for the set of optimizations that
30/// corresponds to one library call.
31namespace {
32class LibCallOptimization {
33protected:
34  Function *Caller;
35  const DataLayout *TD;
36  const TargetLibraryInfo *TLI;
37  LLVMContext* Context;
38public:
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.
72static 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
90struct FortifiedLibCallOptimization : public LibCallOptimization {
91protected:
92  virtual bool isFoldable(unsigned SizeCIOp, unsigned SizeArgOp,
93			  bool isString) const = 0;
94};
95
96struct 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
121struct 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
144struct 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
167struct 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
191struct 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
236struct 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
286struct 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
315struct 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
365struct 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
409struct 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
455struct 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
491struct 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
536struct 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
586struct 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
615struct 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
651struct 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
698struct 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
720struct 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
755struct 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
775struct 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} // End anonymous namespace.
805
806namespace llvm {
807
808class LibCallSimplifierImpl {
809  const DataLayout *TD;
810  const TargetLibraryInfo *TLI;
811  StringMap<LibCallOptimization*> Optimizations;
812
813  // Fortified library call optimizations.
814  MemCpyChkOpt MemCpyChk;
815  MemMoveChkOpt MemMoveChk;
816  MemSetChkOpt MemSetChk;
817  StrCpyChkOpt StrCpyChk;
818  StpCpyChkOpt StpCpyChk;
819  StrNCpyChkOpt StrNCpyChk;
820
821  // String and memory library call optimizations.
822  StrCatOpt StrCat;
823  StrNCatOpt StrNCat;
824  StrChrOpt StrChr;
825  StrRChrOpt StrRChr;
826  StrCmpOpt StrCmp;
827  StrNCmpOpt StrNCmp;
828  StrCpyOpt StrCpy;
829  StpCpyOpt StpCpy;
830  StrNCpyOpt StrNCpy;
831  StrLenOpt StrLen;
832  StrPBrkOpt StrPBrk;
833  StrToOpt StrTo;
834  StrSpnOpt StrSpn;
835
836  void initOptimizations();
837public:
838  LibCallSimplifierImpl(const DataLayout *TD, const TargetLibraryInfo *TLI) {
839    this->TD = TD;
840    this->TLI = TLI;
841  }
842
843  Value *optimizeCall(CallInst *CI);
844};
845
846void LibCallSimplifierImpl::initOptimizations() {
847  // Fortified library call optimizations.
848  Optimizations["__memcpy_chk"] = &MemCpyChk;
849  Optimizations["__memmove_chk"] = &MemMoveChk;
850  Optimizations["__memset_chk"] = &MemSetChk;
851  Optimizations["__strcpy_chk"] = &StrCpyChk;
852  Optimizations["__stpcpy_chk"] = &StpCpyChk;
853  Optimizations["__strncpy_chk"] = &StrNCpyChk;
854  Optimizations["__stpncpy_chk"] = &StrNCpyChk;
855
856  // String and memory library call optimizations.
857  Optimizations["strcat"] = &StrCat;
858  Optimizations["strncat"] = &StrNCat;
859  Optimizations["strchr"] = &StrChr;
860  Optimizations["strrchr"] = &StrRChr;
861  Optimizations["strcmp"] = &StrCmp;
862  Optimizations["strncmp"] = &StrNCmp;
863  Optimizations["strcpy"] = &StrCpy;
864  Optimizations["stpcpy"] = &StpCpy;
865  Optimizations["strncpy"] = &StrNCpy;
866  Optimizations["strlen"] = &StrLen;
867  Optimizations["strpbrk"] = &StrPBrk;
868  Optimizations["strtol"] = &StrTo;
869  Optimizations["strtod"] = &StrTo;
870  Optimizations["strtof"] = &StrTo;
871  Optimizations["strtoul"] = &StrTo;
872  Optimizations["strtoll"] = &StrTo;
873  Optimizations["strtold"] = &StrTo;
874  Optimizations["strtoull"] = &StrTo;
875  Optimizations["strspn"] = &StrSpn;
876}
877
878Value *LibCallSimplifierImpl::optimizeCall(CallInst *CI) {
879  if (Optimizations.empty())
880    initOptimizations();
881
882  Function *Callee = CI->getCalledFunction();
883  LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
884  if (LCO) {
885    IRBuilder<> Builder(CI);
886    return LCO->optimizeCall(CI, TD, TLI, Builder);
887  }
888  return 0;
889}
890
891LibCallSimplifier::LibCallSimplifier(const DataLayout *TD,
892                                     const TargetLibraryInfo *TLI) {
893  Impl = new LibCallSimplifierImpl(TD, TLI);
894}
895
896LibCallSimplifier::~LibCallSimplifier() {
897  delete Impl;
898}
899
900Value *LibCallSimplifier::optimizeCall(CallInst *CI) {
901  return Impl->optimizeCall(CI);
902}
903
904}
905