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/ADT/SmallString.h"
19#include "llvm/ADT/StringMap.h"
20#include "llvm/Analysis/ValueTracking.h"
21#include "llvm/IR/DataLayout.h"
22#include "llvm/IR/Function.h"
23#include "llvm/IR/IRBuilder.h"
24#include "llvm/IR/IntrinsicInst.h"
25#include "llvm/IR/Intrinsics.h"
26#include "llvm/IR/LLVMContext.h"
27#include "llvm/IR/Module.h"
28#include "llvm/Support/Allocator.h"
29#include "llvm/Target/TargetLibraryInfo.h"
30#include "llvm/Transforms/Utils/BuildLibCalls.h"
31
32using namespace llvm;
33
34/// This class is the abstract base class for the set of optimizations that
35/// corresponds to one library call.
36namespace {
37class LibCallOptimization {
38protected:
39  Function *Caller;
40  const DataLayout *TD;
41  const TargetLibraryInfo *TLI;
42  const LibCallSimplifier *LCS;
43  LLVMContext* Context;
44public:
45  LibCallOptimization() { }
46  virtual ~LibCallOptimization() {}
47
48  /// callOptimizer - This pure virtual method is implemented by base classes to
49  /// do various optimizations.  If this returns null then no transformation was
50  /// performed.  If it returns CI, then it transformed the call and CI is to be
51  /// deleted.  If it returns something else, replace CI with the new value and
52  /// delete CI.
53  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B)
54    =0;
55
56  /// ignoreCallingConv - Returns false if this transformation could possibly
57  /// change the calling convention.
58  virtual bool ignoreCallingConv() { return false; }
59
60  Value *optimizeCall(CallInst *CI, const DataLayout *TD,
61                      const TargetLibraryInfo *TLI,
62                      const LibCallSimplifier *LCS, IRBuilder<> &B) {
63    Caller = CI->getParent()->getParent();
64    this->TD = TD;
65    this->TLI = TLI;
66    this->LCS = LCS;
67    if (CI->getCalledFunction())
68      Context = &CI->getCalledFunction()->getContext();
69
70    // We never change the calling convention.
71    if (!ignoreCallingConv() && CI->getCallingConv() != llvm::CallingConv::C)
72      return NULL;
73
74    return callOptimizer(CI->getCalledFunction(), CI, B);
75  }
76};
77
78//===----------------------------------------------------------------------===//
79// Helper Functions
80//===----------------------------------------------------------------------===//
81
82/// isOnlyUsedInZeroEqualityComparison - Return true if it only matters that the
83/// value is equal or not-equal to zero.
84static bool isOnlyUsedInZeroEqualityComparison(Value *V) {
85  for (Value::use_iterator UI = V->use_begin(), E = V->use_end();
86       UI != E; ++UI) {
87    if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI))
88      if (IC->isEquality())
89        if (Constant *C = dyn_cast<Constant>(IC->getOperand(1)))
90          if (C->isNullValue())
91            continue;
92    // Unknown instruction.
93    return false;
94  }
95  return true;
96}
97
98/// isOnlyUsedInEqualityComparison - Return true if it is only used in equality
99/// comparisons with With.
100static bool isOnlyUsedInEqualityComparison(Value *V, Value *With) {
101  for (Value::use_iterator UI = V->use_begin(), E = V->use_end();
102       UI != E; ++UI) {
103    if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI))
104      if (IC->isEquality() && IC->getOperand(1) == With)
105        continue;
106    // Unknown instruction.
107    return false;
108  }
109  return true;
110}
111
112static bool callHasFloatingPointArgument(const CallInst *CI) {
113  for (CallInst::const_op_iterator it = CI->op_begin(), e = CI->op_end();
114       it != e; ++it) {
115    if ((*it)->getType()->isFloatingPointTy())
116      return true;
117  }
118  return false;
119}
120
121//===----------------------------------------------------------------------===//
122// Fortified Library Call Optimizations
123//===----------------------------------------------------------------------===//
124
125struct FortifiedLibCallOptimization : public LibCallOptimization {
126protected:
127  virtual bool isFoldable(unsigned SizeCIOp, unsigned SizeArgOp,
128			  bool isString) const = 0;
129};
130
131struct InstFortifiedLibCallOptimization : public FortifiedLibCallOptimization {
132  CallInst *CI;
133
134  bool isFoldable(unsigned SizeCIOp, unsigned SizeArgOp, bool isString) const {
135    if (CI->getArgOperand(SizeCIOp) == CI->getArgOperand(SizeArgOp))
136      return true;
137    if (ConstantInt *SizeCI =
138                           dyn_cast<ConstantInt>(CI->getArgOperand(SizeCIOp))) {
139      if (SizeCI->isAllOnesValue())
140        return true;
141      if (isString) {
142        uint64_t Len = GetStringLength(CI->getArgOperand(SizeArgOp));
143        // If the length is 0 we don't know how long it is and so we can't
144        // remove the check.
145        if (Len == 0) return false;
146        return SizeCI->getZExtValue() >= Len;
147      }
148      if (ConstantInt *Arg = dyn_cast<ConstantInt>(
149                                                  CI->getArgOperand(SizeArgOp)))
150        return SizeCI->getZExtValue() >= Arg->getZExtValue();
151    }
152    return false;
153  }
154};
155
156struct MemCpyChkOpt : public InstFortifiedLibCallOptimization {
157  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
158    this->CI = CI;
159    FunctionType *FT = Callee->getFunctionType();
160    LLVMContext &Context = CI->getParent()->getContext();
161
162    // Check if this has the right signature.
163    if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
164        !FT->getParamType(0)->isPointerTy() ||
165        !FT->getParamType(1)->isPointerTy() ||
166        FT->getParamType(2) != TD->getIntPtrType(Context) ||
167        FT->getParamType(3) != TD->getIntPtrType(Context))
168      return 0;
169
170    if (isFoldable(3, 2, false)) {
171      B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
172                     CI->getArgOperand(2), 1);
173      return CI->getArgOperand(0);
174    }
175    return 0;
176  }
177};
178
179struct MemMoveChkOpt : public InstFortifiedLibCallOptimization {
180  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
181    this->CI = CI;
182    FunctionType *FT = Callee->getFunctionType();
183    LLVMContext &Context = CI->getParent()->getContext();
184
185    // Check if this has the right signature.
186    if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
187        !FT->getParamType(0)->isPointerTy() ||
188        !FT->getParamType(1)->isPointerTy() ||
189        FT->getParamType(2) != TD->getIntPtrType(Context) ||
190        FT->getParamType(3) != TD->getIntPtrType(Context))
191      return 0;
192
193    if (isFoldable(3, 2, false)) {
194      B.CreateMemMove(CI->getArgOperand(0), CI->getArgOperand(1),
195                      CI->getArgOperand(2), 1);
196      return CI->getArgOperand(0);
197    }
198    return 0;
199  }
200};
201
202struct MemSetChkOpt : public InstFortifiedLibCallOptimization {
203  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
204    this->CI = CI;
205    FunctionType *FT = Callee->getFunctionType();
206    LLVMContext &Context = CI->getParent()->getContext();
207
208    // Check if this has the right signature.
209    if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
210        !FT->getParamType(0)->isPointerTy() ||
211        !FT->getParamType(1)->isIntegerTy() ||
212        FT->getParamType(2) != TD->getIntPtrType(Context) ||
213        FT->getParamType(3) != TD->getIntPtrType(Context))
214      return 0;
215
216    if (isFoldable(3, 2, false)) {
217      Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(),
218                                   false);
219      B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1);
220      return CI->getArgOperand(0);
221    }
222    return 0;
223  }
224};
225
226struct StrCpyChkOpt : public InstFortifiedLibCallOptimization {
227  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
228    this->CI = CI;
229    StringRef Name = Callee->getName();
230    FunctionType *FT = Callee->getFunctionType();
231    LLVMContext &Context = CI->getParent()->getContext();
232
233    // Check if this has the right signature.
234    if (FT->getNumParams() != 3 ||
235        FT->getReturnType() != FT->getParamType(0) ||
236        FT->getParamType(0) != FT->getParamType(1) ||
237        FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
238        FT->getParamType(2) != TD->getIntPtrType(Context))
239      return 0;
240
241    Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
242    if (Dst == Src)      // __strcpy_chk(x,x)  -> x
243      return Src;
244
245    // If a) we don't have any length information, or b) we know this will
246    // fit then just lower to a plain strcpy. Otherwise we'll keep our
247    // strcpy_chk call which may fail at runtime if the size is too long.
248    // TODO: It might be nice to get a maximum length out of the possible
249    // string lengths for varying.
250    if (isFoldable(2, 1, true)) {
251      Value *Ret = EmitStrCpy(Dst, Src, B, TD, TLI, Name.substr(2, 6));
252      return Ret;
253    } else {
254      // Maybe we can stil fold __strcpy_chk to __memcpy_chk.
255      uint64_t Len = GetStringLength(Src);
256      if (Len == 0) return 0;
257
258      // This optimization require DataLayout.
259      if (!TD) return 0;
260
261      Value *Ret =
262	EmitMemCpyChk(Dst, Src,
263                      ConstantInt::get(TD->getIntPtrType(Context), Len),
264                      CI->getArgOperand(2), B, TD, TLI);
265      return Ret;
266    }
267    return 0;
268  }
269};
270
271struct StpCpyChkOpt : public InstFortifiedLibCallOptimization {
272  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
273    this->CI = CI;
274    StringRef Name = Callee->getName();
275    FunctionType *FT = Callee->getFunctionType();
276    LLVMContext &Context = CI->getParent()->getContext();
277
278    // Check if this has the right signature.
279    if (FT->getNumParams() != 3 ||
280        FT->getReturnType() != FT->getParamType(0) ||
281        FT->getParamType(0) != FT->getParamType(1) ||
282        FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
283        FT->getParamType(2) != TD->getIntPtrType(FT->getParamType(0)))
284      return 0;
285
286    Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
287    if (Dst == Src) {  // stpcpy(x,x)  -> x+strlen(x)
288      Value *StrLen = EmitStrLen(Src, B, TD, TLI);
289      return StrLen ? B.CreateInBoundsGEP(Dst, StrLen) : 0;
290    }
291
292    // If a) we don't have any length information, or b) we know this will
293    // fit then just lower to a plain stpcpy. Otherwise we'll keep our
294    // stpcpy_chk call which may fail at runtime if the size is too long.
295    // TODO: It might be nice to get a maximum length out of the possible
296    // string lengths for varying.
297    if (isFoldable(2, 1, true)) {
298      Value *Ret = EmitStrCpy(Dst, Src, B, TD, TLI, Name.substr(2, 6));
299      return Ret;
300    } else {
301      // Maybe we can stil fold __stpcpy_chk to __memcpy_chk.
302      uint64_t Len = GetStringLength(Src);
303      if (Len == 0) return 0;
304
305      // This optimization require DataLayout.
306      if (!TD) return 0;
307
308      Type *PT = FT->getParamType(0);
309      Value *LenV = ConstantInt::get(TD->getIntPtrType(PT), Len);
310      Value *DstEnd = B.CreateGEP(Dst,
311                                  ConstantInt::get(TD->getIntPtrType(PT),
312                                                   Len - 1));
313      if (!EmitMemCpyChk(Dst, Src, LenV, CI->getArgOperand(2), B, TD, TLI))
314        return 0;
315      return DstEnd;
316    }
317    return 0;
318  }
319};
320
321struct StrNCpyChkOpt : public InstFortifiedLibCallOptimization {
322  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
323    this->CI = CI;
324    StringRef Name = Callee->getName();
325    FunctionType *FT = Callee->getFunctionType();
326    LLVMContext &Context = CI->getParent()->getContext();
327
328    // Check if this has the right signature.
329    if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
330        FT->getParamType(0) != FT->getParamType(1) ||
331        FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
332        !FT->getParamType(2)->isIntegerTy() ||
333        FT->getParamType(3) != TD->getIntPtrType(Context))
334      return 0;
335
336    if (isFoldable(3, 2, false)) {
337      Value *Ret = EmitStrNCpy(CI->getArgOperand(0), CI->getArgOperand(1),
338                               CI->getArgOperand(2), B, TD, TLI,
339                               Name.substr(2, 7));
340      return Ret;
341    }
342    return 0;
343  }
344};
345
346//===----------------------------------------------------------------------===//
347// String and Memory Library Call Optimizations
348//===----------------------------------------------------------------------===//
349
350struct StrCatOpt : public LibCallOptimization {
351  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
352    // Verify the "strcat" function prototype.
353    FunctionType *FT = Callee->getFunctionType();
354    if (FT->getNumParams() != 2 ||
355        FT->getReturnType() != B.getInt8PtrTy() ||
356        FT->getParamType(0) != FT->getReturnType() ||
357        FT->getParamType(1) != FT->getReturnType())
358      return 0;
359
360    // Extract some information from the instruction
361    Value *Dst = CI->getArgOperand(0);
362    Value *Src = CI->getArgOperand(1);
363
364    // See if we can get the length of the input string.
365    uint64_t Len = GetStringLength(Src);
366    if (Len == 0) return 0;
367    --Len;  // Unbias length.
368
369    // Handle the simple, do-nothing case: strcat(x, "") -> x
370    if (Len == 0)
371      return Dst;
372
373    // These optimizations require DataLayout.
374    if (!TD) return 0;
375
376    return emitStrLenMemCpy(Src, Dst, Len, B);
377  }
378
379  Value *emitStrLenMemCpy(Value *Src, Value *Dst, uint64_t Len,
380                          IRBuilder<> &B) {
381    // We need to find the end of the destination string.  That's where the
382    // memory is to be moved to. We just generate a call to strlen.
383    Value *DstLen = EmitStrLen(Dst, B, TD, TLI);
384    if (!DstLen)
385      return 0;
386
387    // Now that we have the destination's length, we must index into the
388    // destination's pointer to get the actual memcpy destination (end of
389    // the string .. we're concatenating).
390    Value *CpyDst = B.CreateGEP(Dst, DstLen, "endptr");
391
392    // We have enough information to now generate the memcpy call to do the
393    // concatenation for us.  Make a memcpy to copy the nul byte with align = 1.
394    B.CreateMemCpy(CpyDst, Src,
395                   ConstantInt::get(TD->getIntPtrType(*Context), Len + 1), 1);
396    return Dst;
397  }
398};
399
400struct StrNCatOpt : public StrCatOpt {
401  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
402    // Verify the "strncat" function prototype.
403    FunctionType *FT = Callee->getFunctionType();
404    if (FT->getNumParams() != 3 ||
405        FT->getReturnType() != B.getInt8PtrTy() ||
406        FT->getParamType(0) != FT->getReturnType() ||
407        FT->getParamType(1) != FT->getReturnType() ||
408        !FT->getParamType(2)->isIntegerTy())
409      return 0;
410
411    // Extract some information from the instruction
412    Value *Dst = CI->getArgOperand(0);
413    Value *Src = CI->getArgOperand(1);
414    uint64_t Len;
415
416    // We don't do anything if length is not constant
417    if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
418      Len = LengthArg->getZExtValue();
419    else
420      return 0;
421
422    // See if we can get the length of the input string.
423    uint64_t SrcLen = GetStringLength(Src);
424    if (SrcLen == 0) return 0;
425    --SrcLen;  // Unbias length.
426
427    // Handle the simple, do-nothing cases:
428    // strncat(x, "", c) -> x
429    // strncat(x,  c, 0) -> x
430    if (SrcLen == 0 || Len == 0) return Dst;
431
432    // These optimizations require DataLayout.
433    if (!TD) return 0;
434
435    // We don't optimize this case
436    if (Len < SrcLen) return 0;
437
438    // strncat(x, s, c) -> strcat(x, s)
439    // s is constant so the strcat can be optimized further
440    return emitStrLenMemCpy(Src, Dst, SrcLen, B);
441  }
442};
443
444struct StrChrOpt : public LibCallOptimization {
445  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
446    // Verify the "strchr" function prototype.
447    FunctionType *FT = Callee->getFunctionType();
448    if (FT->getNumParams() != 2 ||
449        FT->getReturnType() != B.getInt8PtrTy() ||
450        FT->getParamType(0) != FT->getReturnType() ||
451        !FT->getParamType(1)->isIntegerTy(32))
452      return 0;
453
454    Value *SrcStr = CI->getArgOperand(0);
455
456    // If the second operand is non-constant, see if we can compute the length
457    // of the input string and turn this into memchr.
458    ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
459    if (CharC == 0) {
460      // These optimizations require DataLayout.
461      if (!TD) return 0;
462
463      uint64_t Len = GetStringLength(SrcStr);
464      if (Len == 0 || !FT->getParamType(1)->isIntegerTy(32))// memchr needs i32.
465        return 0;
466
467      return EmitMemChr(SrcStr, CI->getArgOperand(1), // include nul.
468                        ConstantInt::get(TD->getIntPtrType(*Context), Len),
469                        B, TD, TLI);
470    }
471
472    // Otherwise, the character is a constant, see if the first argument is
473    // a string literal.  If so, we can constant fold.
474    StringRef Str;
475    if (!getConstantStringInfo(SrcStr, Str))
476      return 0;
477
478    // Compute the offset, make sure to handle the case when we're searching for
479    // zero (a weird way to spell strlen).
480    size_t I = CharC->getSExtValue() == 0 ?
481        Str.size() : Str.find(CharC->getSExtValue());
482    if (I == StringRef::npos) // Didn't find the char.  strchr returns null.
483      return Constant::getNullValue(CI->getType());
484
485    // strchr(s+n,c)  -> gep(s+n+i,c)
486    return B.CreateGEP(SrcStr, B.getInt64(I), "strchr");
487  }
488};
489
490struct StrRChrOpt : public LibCallOptimization {
491  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
492    // Verify the "strrchr" function prototype.
493    FunctionType *FT = Callee->getFunctionType();
494    if (FT->getNumParams() != 2 ||
495        FT->getReturnType() != B.getInt8PtrTy() ||
496        FT->getParamType(0) != FT->getReturnType() ||
497        !FT->getParamType(1)->isIntegerTy(32))
498      return 0;
499
500    Value *SrcStr = CI->getArgOperand(0);
501    ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
502
503    // Cannot fold anything if we're not looking for a constant.
504    if (!CharC)
505      return 0;
506
507    StringRef Str;
508    if (!getConstantStringInfo(SrcStr, Str)) {
509      // strrchr(s, 0) -> strchr(s, 0)
510      if (TD && CharC->isZero())
511        return EmitStrChr(SrcStr, '\0', B, TD, TLI);
512      return 0;
513    }
514
515    // Compute the offset.
516    size_t I = CharC->getSExtValue() == 0 ?
517        Str.size() : Str.rfind(CharC->getSExtValue());
518    if (I == StringRef::npos) // Didn't find the char. Return null.
519      return Constant::getNullValue(CI->getType());
520
521    // strrchr(s+n,c) -> gep(s+n+i,c)
522    return B.CreateGEP(SrcStr, B.getInt64(I), "strrchr");
523  }
524};
525
526struct StrCmpOpt : public LibCallOptimization {
527  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
528    // Verify the "strcmp" function prototype.
529    FunctionType *FT = Callee->getFunctionType();
530    if (FT->getNumParams() != 2 ||
531        !FT->getReturnType()->isIntegerTy(32) ||
532        FT->getParamType(0) != FT->getParamType(1) ||
533        FT->getParamType(0) != B.getInt8PtrTy())
534      return 0;
535
536    Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
537    if (Str1P == Str2P)      // strcmp(x,x)  -> 0
538      return ConstantInt::get(CI->getType(), 0);
539
540    StringRef Str1, Str2;
541    bool HasStr1 = getConstantStringInfo(Str1P, Str1);
542    bool HasStr2 = getConstantStringInfo(Str2P, Str2);
543
544    // strcmp(x, y)  -> cnst  (if both x and y are constant strings)
545    if (HasStr1 && HasStr2)
546      return ConstantInt::get(CI->getType(), Str1.compare(Str2));
547
548    if (HasStr1 && Str1.empty()) // strcmp("", x) -> -*x
549      return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"),
550                                      CI->getType()));
551
552    if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x
553      return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
554
555    // strcmp(P, "x") -> memcmp(P, "x", 2)
556    uint64_t Len1 = GetStringLength(Str1P);
557    uint64_t Len2 = GetStringLength(Str2P);
558    if (Len1 && Len2) {
559      // These optimizations require DataLayout.
560      if (!TD) return 0;
561
562      return EmitMemCmp(Str1P, Str2P,
563                        ConstantInt::get(TD->getIntPtrType(*Context),
564                        std::min(Len1, Len2)), B, TD, TLI);
565    }
566
567    return 0;
568  }
569};
570
571struct StrNCmpOpt : public LibCallOptimization {
572  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
573    // Verify the "strncmp" function prototype.
574    FunctionType *FT = Callee->getFunctionType();
575    if (FT->getNumParams() != 3 ||
576        !FT->getReturnType()->isIntegerTy(32) ||
577        FT->getParamType(0) != FT->getParamType(1) ||
578        FT->getParamType(0) != B.getInt8PtrTy() ||
579        !FT->getParamType(2)->isIntegerTy())
580      return 0;
581
582    Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
583    if (Str1P == Str2P)      // strncmp(x,x,n)  -> 0
584      return ConstantInt::get(CI->getType(), 0);
585
586    // Get the length argument if it is constant.
587    uint64_t Length;
588    if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
589      Length = LengthArg->getZExtValue();
590    else
591      return 0;
592
593    if (Length == 0) // strncmp(x,y,0)   -> 0
594      return ConstantInt::get(CI->getType(), 0);
595
596    if (TD && Length == 1) // strncmp(x,y,1) -> memcmp(x,y,1)
597      return EmitMemCmp(Str1P, Str2P, CI->getArgOperand(2), B, TD, TLI);
598
599    StringRef Str1, Str2;
600    bool HasStr1 = getConstantStringInfo(Str1P, Str1);
601    bool HasStr2 = getConstantStringInfo(Str2P, Str2);
602
603    // strncmp(x, y)  -> cnst  (if both x and y are constant strings)
604    if (HasStr1 && HasStr2) {
605      StringRef SubStr1 = Str1.substr(0, Length);
606      StringRef SubStr2 = Str2.substr(0, Length);
607      return ConstantInt::get(CI->getType(), SubStr1.compare(SubStr2));
608    }
609
610    if (HasStr1 && Str1.empty())  // strncmp("", x, n) -> -*x
611      return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"),
612                                      CI->getType()));
613
614    if (HasStr2 && Str2.empty())  // strncmp(x, "", n) -> *x
615      return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
616
617    return 0;
618  }
619};
620
621struct StrCpyOpt : public LibCallOptimization {
622  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
623    // Verify the "strcpy" function prototype.
624    FunctionType *FT = Callee->getFunctionType();
625    if (FT->getNumParams() != 2 ||
626        FT->getReturnType() != FT->getParamType(0) ||
627        FT->getParamType(0) != FT->getParamType(1) ||
628        FT->getParamType(0) != B.getInt8PtrTy())
629      return 0;
630
631    Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
632    if (Dst == Src)      // strcpy(x,x)  -> x
633      return Src;
634
635    // These optimizations require DataLayout.
636    if (!TD) return 0;
637
638    // See if we can get the length of the input string.
639    uint64_t Len = GetStringLength(Src);
640    if (Len == 0) return 0;
641
642    // We have enough information to now generate the memcpy call to do the
643    // copy for us.  Make a memcpy to copy the nul byte with align = 1.
644    B.CreateMemCpy(Dst, Src,
645		   ConstantInt::get(TD->getIntPtrType(*Context), Len), 1);
646    return Dst;
647  }
648};
649
650struct StpCpyOpt: public LibCallOptimization {
651  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
652    // Verify the "stpcpy" function prototype.
653    FunctionType *FT = Callee->getFunctionType();
654    if (FT->getNumParams() != 2 ||
655        FT->getReturnType() != FT->getParamType(0) ||
656        FT->getParamType(0) != FT->getParamType(1) ||
657        FT->getParamType(0) != B.getInt8PtrTy())
658      return 0;
659
660    // These optimizations require DataLayout.
661    if (!TD) return 0;
662
663    Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
664    if (Dst == Src) {  // stpcpy(x,x)  -> x+strlen(x)
665      Value *StrLen = EmitStrLen(Src, B, TD, TLI);
666      return StrLen ? B.CreateInBoundsGEP(Dst, StrLen) : 0;
667    }
668
669    // See if we can get the length of the input string.
670    uint64_t Len = GetStringLength(Src);
671    if (Len == 0) return 0;
672
673    Type *PT = FT->getParamType(0);
674    Value *LenV = ConstantInt::get(TD->getIntPtrType(PT), Len);
675    Value *DstEnd = B.CreateGEP(Dst,
676                                ConstantInt::get(TD->getIntPtrType(PT),
677                                                 Len - 1));
678
679    // We have enough information to now generate the memcpy call to do the
680    // copy for us.  Make a memcpy to copy the nul byte with align = 1.
681    B.CreateMemCpy(Dst, Src, LenV, 1);
682    return DstEnd;
683  }
684};
685
686struct StrNCpyOpt : public LibCallOptimization {
687  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
688    FunctionType *FT = Callee->getFunctionType();
689    if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
690        FT->getParamType(0) != FT->getParamType(1) ||
691        FT->getParamType(0) != B.getInt8PtrTy() ||
692        !FT->getParamType(2)->isIntegerTy())
693      return 0;
694
695    Value *Dst = CI->getArgOperand(0);
696    Value *Src = CI->getArgOperand(1);
697    Value *LenOp = CI->getArgOperand(2);
698
699    // See if we can get the length of the input string.
700    uint64_t SrcLen = GetStringLength(Src);
701    if (SrcLen == 0) return 0;
702    --SrcLen;
703
704    if (SrcLen == 0) {
705      // strncpy(x, "", y) -> memset(x, '\0', y, 1)
706      B.CreateMemSet(Dst, B.getInt8('\0'), LenOp, 1);
707      return Dst;
708    }
709
710    uint64_t Len;
711    if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(LenOp))
712      Len = LengthArg->getZExtValue();
713    else
714      return 0;
715
716    if (Len == 0) return Dst; // strncpy(x, y, 0) -> x
717
718    // These optimizations require DataLayout.
719    if (!TD) return 0;
720
721    // Let strncpy handle the zero padding
722    if (Len > SrcLen+1) return 0;
723
724    Type *PT = FT->getParamType(0);
725    // strncpy(x, s, c) -> memcpy(x, s, c, 1) [s and c are constant]
726    B.CreateMemCpy(Dst, Src,
727                   ConstantInt::get(TD->getIntPtrType(PT), Len), 1);
728
729    return Dst;
730  }
731};
732
733struct StrLenOpt : public LibCallOptimization {
734  virtual bool ignoreCallingConv() { return true; }
735  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
736    FunctionType *FT = Callee->getFunctionType();
737    if (FT->getNumParams() != 1 ||
738        FT->getParamType(0) != B.getInt8PtrTy() ||
739        !FT->getReturnType()->isIntegerTy())
740      return 0;
741
742    Value *Src = CI->getArgOperand(0);
743
744    // Constant folding: strlen("xyz") -> 3
745    if (uint64_t Len = GetStringLength(Src))
746      return ConstantInt::get(CI->getType(), Len-1);
747
748    // strlen(x) != 0 --> *x != 0
749    // strlen(x) == 0 --> *x == 0
750    if (isOnlyUsedInZeroEqualityComparison(CI))
751      return B.CreateZExt(B.CreateLoad(Src, "strlenfirst"), CI->getType());
752    return 0;
753  }
754};
755
756struct StrPBrkOpt : public LibCallOptimization {
757  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
758    FunctionType *FT = Callee->getFunctionType();
759    if (FT->getNumParams() != 2 ||
760        FT->getParamType(0) != B.getInt8PtrTy() ||
761        FT->getParamType(1) != FT->getParamType(0) ||
762        FT->getReturnType() != FT->getParamType(0))
763      return 0;
764
765    StringRef S1, S2;
766    bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
767    bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
768
769    // strpbrk(s, "") -> NULL
770    // strpbrk("", s) -> NULL
771    if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))
772      return Constant::getNullValue(CI->getType());
773
774    // Constant folding.
775    if (HasS1 && HasS2) {
776      size_t I = S1.find_first_of(S2);
777      if (I == std::string::npos) // No match.
778        return Constant::getNullValue(CI->getType());
779
780      return B.CreateGEP(CI->getArgOperand(0), B.getInt64(I), "strpbrk");
781    }
782
783    // strpbrk(s, "a") -> strchr(s, 'a')
784    if (TD && HasS2 && S2.size() == 1)
785      return EmitStrChr(CI->getArgOperand(0), S2[0], B, TD, TLI);
786
787    return 0;
788  }
789};
790
791struct StrToOpt : public LibCallOptimization {
792  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
793    FunctionType *FT = Callee->getFunctionType();
794    if ((FT->getNumParams() != 2 && FT->getNumParams() != 3) ||
795        !FT->getParamType(0)->isPointerTy() ||
796        !FT->getParamType(1)->isPointerTy())
797      return 0;
798
799    Value *EndPtr = CI->getArgOperand(1);
800    if (isa<ConstantPointerNull>(EndPtr)) {
801      // With a null EndPtr, this function won't capture the main argument.
802      // It would be readonly too, except that it still may write to errno.
803      CI->addAttribute(1, Attribute::NoCapture);
804    }
805
806    return 0;
807  }
808};
809
810struct StrSpnOpt : public LibCallOptimization {
811  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
812    FunctionType *FT = Callee->getFunctionType();
813    if (FT->getNumParams() != 2 ||
814        FT->getParamType(0) != B.getInt8PtrTy() ||
815        FT->getParamType(1) != FT->getParamType(0) ||
816        !FT->getReturnType()->isIntegerTy())
817      return 0;
818
819    StringRef S1, S2;
820    bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
821    bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
822
823    // strspn(s, "") -> 0
824    // strspn("", s) -> 0
825    if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))
826      return Constant::getNullValue(CI->getType());
827
828    // Constant folding.
829    if (HasS1 && HasS2) {
830      size_t Pos = S1.find_first_not_of(S2);
831      if (Pos == StringRef::npos) Pos = S1.size();
832      return ConstantInt::get(CI->getType(), Pos);
833    }
834
835    return 0;
836  }
837};
838
839struct StrCSpnOpt : public LibCallOptimization {
840  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
841    FunctionType *FT = Callee->getFunctionType();
842    if (FT->getNumParams() != 2 ||
843        FT->getParamType(0) != B.getInt8PtrTy() ||
844        FT->getParamType(1) != FT->getParamType(0) ||
845        !FT->getReturnType()->isIntegerTy())
846      return 0;
847
848    StringRef S1, S2;
849    bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
850    bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
851
852    // strcspn("", s) -> 0
853    if (HasS1 && S1.empty())
854      return Constant::getNullValue(CI->getType());
855
856    // Constant folding.
857    if (HasS1 && HasS2) {
858      size_t Pos = S1.find_first_of(S2);
859      if (Pos == StringRef::npos) Pos = S1.size();
860      return ConstantInt::get(CI->getType(), Pos);
861    }
862
863    // strcspn(s, "") -> strlen(s)
864    if (TD && HasS2 && S2.empty())
865      return EmitStrLen(CI->getArgOperand(0), B, TD, TLI);
866
867    return 0;
868  }
869};
870
871struct StrStrOpt : public LibCallOptimization {
872  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
873    FunctionType *FT = Callee->getFunctionType();
874    if (FT->getNumParams() != 2 ||
875        !FT->getParamType(0)->isPointerTy() ||
876        !FT->getParamType(1)->isPointerTy() ||
877        !FT->getReturnType()->isPointerTy())
878      return 0;
879
880    // fold strstr(x, x) -> x.
881    if (CI->getArgOperand(0) == CI->getArgOperand(1))
882      return B.CreateBitCast(CI->getArgOperand(0), CI->getType());
883
884    // fold strstr(a, b) == a -> strncmp(a, b, strlen(b)) == 0
885    if (TD && isOnlyUsedInEqualityComparison(CI, CI->getArgOperand(0))) {
886      Value *StrLen = EmitStrLen(CI->getArgOperand(1), B, TD, TLI);
887      if (!StrLen)
888        return 0;
889      Value *StrNCmp = EmitStrNCmp(CI->getArgOperand(0), CI->getArgOperand(1),
890                                   StrLen, B, TD, TLI);
891      if (!StrNCmp)
892        return 0;
893      for (Value::use_iterator UI = CI->use_begin(), UE = CI->use_end();
894           UI != UE; ) {
895        ICmpInst *Old = cast<ICmpInst>(*UI++);
896        Value *Cmp = B.CreateICmp(Old->getPredicate(), StrNCmp,
897                                  ConstantInt::getNullValue(StrNCmp->getType()),
898                                  "cmp");
899        LCS->replaceAllUsesWith(Old, Cmp);
900      }
901      return CI;
902    }
903
904    // See if either input string is a constant string.
905    StringRef SearchStr, ToFindStr;
906    bool HasStr1 = getConstantStringInfo(CI->getArgOperand(0), SearchStr);
907    bool HasStr2 = getConstantStringInfo(CI->getArgOperand(1), ToFindStr);
908
909    // fold strstr(x, "") -> x.
910    if (HasStr2 && ToFindStr.empty())
911      return B.CreateBitCast(CI->getArgOperand(0), CI->getType());
912
913    // If both strings are known, constant fold it.
914    if (HasStr1 && HasStr2) {
915      std::string::size_type Offset = SearchStr.find(ToFindStr);
916
917      if (Offset == StringRef::npos) // strstr("foo", "bar") -> null
918        return Constant::getNullValue(CI->getType());
919
920      // strstr("abcd", "bc") -> gep((char*)"abcd", 1)
921      Value *Result = CastToCStr(CI->getArgOperand(0), B);
922      Result = B.CreateConstInBoundsGEP1_64(Result, Offset, "strstr");
923      return B.CreateBitCast(Result, CI->getType());
924    }
925
926    // fold strstr(x, "y") -> strchr(x, 'y').
927    if (HasStr2 && ToFindStr.size() == 1) {
928      Value *StrChr= EmitStrChr(CI->getArgOperand(0), ToFindStr[0], B, TD, TLI);
929      return StrChr ? B.CreateBitCast(StrChr, CI->getType()) : 0;
930    }
931    return 0;
932  }
933};
934
935struct MemCmpOpt : public LibCallOptimization {
936  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
937    FunctionType *FT = Callee->getFunctionType();
938    if (FT->getNumParams() != 3 || !FT->getParamType(0)->isPointerTy() ||
939        !FT->getParamType(1)->isPointerTy() ||
940        !FT->getReturnType()->isIntegerTy(32))
941      return 0;
942
943    Value *LHS = CI->getArgOperand(0), *RHS = CI->getArgOperand(1);
944
945    if (LHS == RHS)  // memcmp(s,s,x) -> 0
946      return Constant::getNullValue(CI->getType());
947
948    // Make sure we have a constant length.
949    ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getArgOperand(2));
950    if (!LenC) return 0;
951    uint64_t Len = LenC->getZExtValue();
952
953    if (Len == 0) // memcmp(s1,s2,0) -> 0
954      return Constant::getNullValue(CI->getType());
955
956    // memcmp(S1,S2,1) -> *(unsigned char*)LHS - *(unsigned char*)RHS
957    if (Len == 1) {
958      Value *LHSV = B.CreateZExt(B.CreateLoad(CastToCStr(LHS, B), "lhsc"),
959                                 CI->getType(), "lhsv");
960      Value *RHSV = B.CreateZExt(B.CreateLoad(CastToCStr(RHS, B), "rhsc"),
961                                 CI->getType(), "rhsv");
962      return B.CreateSub(LHSV, RHSV, "chardiff");
963    }
964
965    // Constant folding: memcmp(x, y, l) -> cnst (all arguments are constant)
966    StringRef LHSStr, RHSStr;
967    if (getConstantStringInfo(LHS, LHSStr) &&
968        getConstantStringInfo(RHS, RHSStr)) {
969      // Make sure we're not reading out-of-bounds memory.
970      if (Len > LHSStr.size() || Len > RHSStr.size())
971        return 0;
972      // Fold the memcmp and normalize the result.  This way we get consistent
973      // results across multiple platforms.
974      uint64_t Ret = 0;
975      int Cmp = memcmp(LHSStr.data(), RHSStr.data(), Len);
976      if (Cmp < 0)
977        Ret = -1;
978      else if (Cmp > 0)
979        Ret = 1;
980      return ConstantInt::get(CI->getType(), Ret);
981    }
982
983    return 0;
984  }
985};
986
987struct MemCpyOpt : public LibCallOptimization {
988  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
989    // These optimizations require DataLayout.
990    if (!TD) return 0;
991
992    FunctionType *FT = Callee->getFunctionType();
993    if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
994        !FT->getParamType(0)->isPointerTy() ||
995        !FT->getParamType(1)->isPointerTy() ||
996        FT->getParamType(2) != TD->getIntPtrType(*Context))
997      return 0;
998
999    // memcpy(x, y, n) -> llvm.memcpy(x, y, n, 1)
1000    B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
1001                   CI->getArgOperand(2), 1);
1002    return CI->getArgOperand(0);
1003  }
1004};
1005
1006struct MemMoveOpt : public LibCallOptimization {
1007  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1008    // These optimizations require DataLayout.
1009    if (!TD) return 0;
1010
1011    FunctionType *FT = Callee->getFunctionType();
1012    if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
1013        !FT->getParamType(0)->isPointerTy() ||
1014        !FT->getParamType(1)->isPointerTy() ||
1015        FT->getParamType(2) != TD->getIntPtrType(*Context))
1016      return 0;
1017
1018    // memmove(x, y, n) -> llvm.memmove(x, y, n, 1)
1019    B.CreateMemMove(CI->getArgOperand(0), CI->getArgOperand(1),
1020                    CI->getArgOperand(2), 1);
1021    return CI->getArgOperand(0);
1022  }
1023};
1024
1025struct MemSetOpt : public LibCallOptimization {
1026  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1027    // These optimizations require DataLayout.
1028    if (!TD) return 0;
1029
1030    FunctionType *FT = Callee->getFunctionType();
1031    if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
1032        !FT->getParamType(0)->isPointerTy() ||
1033        !FT->getParamType(1)->isIntegerTy() ||
1034        FT->getParamType(2) != TD->getIntPtrType(*Context))
1035      return 0;
1036
1037    // memset(p, v, n) -> llvm.memset(p, v, n, 1)
1038    Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(), false);
1039    B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1);
1040    return CI->getArgOperand(0);
1041  }
1042};
1043
1044//===----------------------------------------------------------------------===//
1045// Math Library Optimizations
1046//===----------------------------------------------------------------------===//
1047
1048//===----------------------------------------------------------------------===//
1049// Double -> Float Shrinking Optimizations for Unary Functions like 'floor'
1050
1051struct UnaryDoubleFPOpt : public LibCallOptimization {
1052  bool CheckRetType;
1053  UnaryDoubleFPOpt(bool CheckReturnType): CheckRetType(CheckReturnType) {}
1054  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1055    FunctionType *FT = Callee->getFunctionType();
1056    if (FT->getNumParams() != 1 || !FT->getReturnType()->isDoubleTy() ||
1057        !FT->getParamType(0)->isDoubleTy())
1058      return 0;
1059
1060    if (CheckRetType) {
1061      // Check if all the uses for function like 'sin' are converted to float.
1062      for (Value::use_iterator UseI = CI->use_begin(); UseI != CI->use_end();
1063          ++UseI) {
1064        FPTruncInst *Cast = dyn_cast<FPTruncInst>(*UseI);
1065        if (Cast == 0 || !Cast->getType()->isFloatTy())
1066          return 0;
1067      }
1068    }
1069
1070    // If this is something like 'floor((double)floatval)', convert to floorf.
1071    FPExtInst *Cast = dyn_cast<FPExtInst>(CI->getArgOperand(0));
1072    if (Cast == 0 || !Cast->getOperand(0)->getType()->isFloatTy())
1073      return 0;
1074
1075    // floor((double)floatval) -> (double)floorf(floatval)
1076    Value *V = Cast->getOperand(0);
1077    V = EmitUnaryFloatFnCall(V, Callee->getName(), B, Callee->getAttributes());
1078    return B.CreateFPExt(V, B.getDoubleTy());
1079  }
1080};
1081
1082struct UnsafeFPLibCallOptimization : public LibCallOptimization {
1083  bool UnsafeFPShrink;
1084  UnsafeFPLibCallOptimization(bool UnsafeFPShrink) {
1085    this->UnsafeFPShrink = UnsafeFPShrink;
1086  }
1087};
1088
1089struct CosOpt : public UnsafeFPLibCallOptimization {
1090  CosOpt(bool UnsafeFPShrink) : UnsafeFPLibCallOptimization(UnsafeFPShrink) {}
1091  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1092    Value *Ret = NULL;
1093    if (UnsafeFPShrink && Callee->getName() == "cos" &&
1094        TLI->has(LibFunc::cosf)) {
1095      UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
1096      Ret = UnsafeUnaryDoubleFP.callOptimizer(Callee, CI, B);
1097    }
1098
1099    FunctionType *FT = Callee->getFunctionType();
1100    // Just make sure this has 1 argument of FP type, which matches the
1101    // result type.
1102    if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1103        !FT->getParamType(0)->isFloatingPointTy())
1104      return Ret;
1105
1106    // cos(-x) -> cos(x)
1107    Value *Op1 = CI->getArgOperand(0);
1108    if (BinaryOperator::isFNeg(Op1)) {
1109      BinaryOperator *BinExpr = cast<BinaryOperator>(Op1);
1110      return B.CreateCall(Callee, BinExpr->getOperand(1), "cos");
1111    }
1112    return Ret;
1113  }
1114};
1115
1116struct PowOpt : public UnsafeFPLibCallOptimization {
1117  PowOpt(bool UnsafeFPShrink) : UnsafeFPLibCallOptimization(UnsafeFPShrink) {}
1118  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1119    Value *Ret = NULL;
1120    if (UnsafeFPShrink && Callee->getName() == "pow" &&
1121        TLI->has(LibFunc::powf)) {
1122      UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
1123      Ret = UnsafeUnaryDoubleFP.callOptimizer(Callee, CI, B);
1124    }
1125
1126    FunctionType *FT = Callee->getFunctionType();
1127    // Just make sure this has 2 arguments of the same FP type, which match the
1128    // result type.
1129    if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) ||
1130        FT->getParamType(0) != FT->getParamType(1) ||
1131        !FT->getParamType(0)->isFloatingPointTy())
1132      return Ret;
1133
1134    Value *Op1 = CI->getArgOperand(0), *Op2 = CI->getArgOperand(1);
1135    if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) {
1136      if (Op1C->isExactlyValue(1.0))  // pow(1.0, x) -> 1.0
1137        return Op1C;
1138      if (Op1C->isExactlyValue(2.0))  // pow(2.0, x) -> exp2(x)
1139        return EmitUnaryFloatFnCall(Op2, "exp2", B, Callee->getAttributes());
1140    }
1141
1142    ConstantFP *Op2C = dyn_cast<ConstantFP>(Op2);
1143    if (Op2C == 0) return Ret;
1144
1145    if (Op2C->getValueAPF().isZero())  // pow(x, 0.0) -> 1.0
1146      return ConstantFP::get(CI->getType(), 1.0);
1147
1148    if (Op2C->isExactlyValue(0.5)) {
1149      // Expand pow(x, 0.5) to (x == -infinity ? +infinity : fabs(sqrt(x))).
1150      // This is faster than calling pow, and still handles negative zero
1151      // and negative infinity correctly.
1152      // TODO: In fast-math mode, this could be just sqrt(x).
1153      // TODO: In finite-only mode, this could be just fabs(sqrt(x)).
1154      Value *Inf = ConstantFP::getInfinity(CI->getType());
1155      Value *NegInf = ConstantFP::getInfinity(CI->getType(), true);
1156      Value *Sqrt = EmitUnaryFloatFnCall(Op1, "sqrt", B,
1157                                         Callee->getAttributes());
1158      Value *FAbs = EmitUnaryFloatFnCall(Sqrt, "fabs", B,
1159                                         Callee->getAttributes());
1160      Value *FCmp = B.CreateFCmpOEQ(Op1, NegInf);
1161      Value *Sel = B.CreateSelect(FCmp, Inf, FAbs);
1162      return Sel;
1163    }
1164
1165    if (Op2C->isExactlyValue(1.0))  // pow(x, 1.0) -> x
1166      return Op1;
1167    if (Op2C->isExactlyValue(2.0))  // pow(x, 2.0) -> x*x
1168      return B.CreateFMul(Op1, Op1, "pow2");
1169    if (Op2C->isExactlyValue(-1.0)) // pow(x, -1.0) -> 1.0/x
1170      return B.CreateFDiv(ConstantFP::get(CI->getType(), 1.0),
1171                          Op1, "powrecip");
1172    return 0;
1173  }
1174};
1175
1176struct Exp2Opt : public UnsafeFPLibCallOptimization {
1177  Exp2Opt(bool UnsafeFPShrink) : UnsafeFPLibCallOptimization(UnsafeFPShrink) {}
1178  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1179    Value *Ret = NULL;
1180    if (UnsafeFPShrink && Callee->getName() == "exp2" &&
1181        TLI->has(LibFunc::exp2)) {
1182      UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
1183      Ret = UnsafeUnaryDoubleFP.callOptimizer(Callee, CI, B);
1184    }
1185
1186    FunctionType *FT = Callee->getFunctionType();
1187    // Just make sure this has 1 argument of FP type, which matches the
1188    // result type.
1189    if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1190        !FT->getParamType(0)->isFloatingPointTy())
1191      return Ret;
1192
1193    Value *Op = CI->getArgOperand(0);
1194    // Turn exp2(sitofp(x)) -> ldexp(1.0, sext(x))  if sizeof(x) <= 32
1195    // Turn exp2(uitofp(x)) -> ldexp(1.0, zext(x))  if sizeof(x) < 32
1196    Value *LdExpArg = 0;
1197    if (SIToFPInst *OpC = dyn_cast<SIToFPInst>(Op)) {
1198      if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() <= 32)
1199        LdExpArg = B.CreateSExt(OpC->getOperand(0), B.getInt32Ty());
1200    } else if (UIToFPInst *OpC = dyn_cast<UIToFPInst>(Op)) {
1201      if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() < 32)
1202        LdExpArg = B.CreateZExt(OpC->getOperand(0), B.getInt32Ty());
1203    }
1204
1205    if (LdExpArg) {
1206      const char *Name;
1207      if (Op->getType()->isFloatTy())
1208        Name = "ldexpf";
1209      else if (Op->getType()->isDoubleTy())
1210        Name = "ldexp";
1211      else
1212        Name = "ldexpl";
1213
1214      Constant *One = ConstantFP::get(*Context, APFloat(1.0f));
1215      if (!Op->getType()->isFloatTy())
1216        One = ConstantExpr::getFPExtend(One, Op->getType());
1217
1218      Module *M = Caller->getParent();
1219      Value *Callee = M->getOrInsertFunction(Name, Op->getType(),
1220                                             Op->getType(),
1221                                             B.getInt32Ty(), NULL);
1222      CallInst *CI = B.CreateCall2(Callee, One, LdExpArg);
1223      if (const Function *F = dyn_cast<Function>(Callee->stripPointerCasts()))
1224        CI->setCallingConv(F->getCallingConv());
1225
1226      return CI;
1227    }
1228    return Ret;
1229  }
1230};
1231
1232//===----------------------------------------------------------------------===//
1233// Integer Library Call Optimizations
1234//===----------------------------------------------------------------------===//
1235
1236struct FFSOpt : public LibCallOptimization {
1237  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1238    FunctionType *FT = Callee->getFunctionType();
1239    // Just make sure this has 2 arguments of the same FP type, which match the
1240    // result type.
1241    if (FT->getNumParams() != 1 ||
1242        !FT->getReturnType()->isIntegerTy(32) ||
1243        !FT->getParamType(0)->isIntegerTy())
1244      return 0;
1245
1246    Value *Op = CI->getArgOperand(0);
1247
1248    // Constant fold.
1249    if (ConstantInt *CI = dyn_cast<ConstantInt>(Op)) {
1250      if (CI->isZero()) // ffs(0) -> 0.
1251        return B.getInt32(0);
1252      // ffs(c) -> cttz(c)+1
1253      return B.getInt32(CI->getValue().countTrailingZeros() + 1);
1254    }
1255
1256    // ffs(x) -> x != 0 ? (i32)llvm.cttz(x)+1 : 0
1257    Type *ArgType = Op->getType();
1258    Value *F = Intrinsic::getDeclaration(Callee->getParent(),
1259                                         Intrinsic::cttz, ArgType);
1260    Value *V = B.CreateCall2(F, Op, B.getFalse(), "cttz");
1261    V = B.CreateAdd(V, ConstantInt::get(V->getType(), 1));
1262    V = B.CreateIntCast(V, B.getInt32Ty(), false);
1263
1264    Value *Cond = B.CreateICmpNE(Op, Constant::getNullValue(ArgType));
1265    return B.CreateSelect(Cond, V, B.getInt32(0));
1266  }
1267};
1268
1269struct AbsOpt : public LibCallOptimization {
1270  virtual bool ignoreCallingConv() { return true; }
1271  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1272    FunctionType *FT = Callee->getFunctionType();
1273    // We require integer(integer) where the types agree.
1274    if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
1275        FT->getParamType(0) != FT->getReturnType())
1276      return 0;
1277
1278    // abs(x) -> x >s -1 ? x : -x
1279    Value *Op = CI->getArgOperand(0);
1280    Value *Pos = B.CreateICmpSGT(Op, Constant::getAllOnesValue(Op->getType()),
1281                                 "ispos");
1282    Value *Neg = B.CreateNeg(Op, "neg");
1283    return B.CreateSelect(Pos, Op, Neg);
1284  }
1285};
1286
1287struct IsDigitOpt : public LibCallOptimization {
1288  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1289    FunctionType *FT = Callee->getFunctionType();
1290    // We require integer(i32)
1291    if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
1292        !FT->getParamType(0)->isIntegerTy(32))
1293      return 0;
1294
1295    // isdigit(c) -> (c-'0') <u 10
1296    Value *Op = CI->getArgOperand(0);
1297    Op = B.CreateSub(Op, B.getInt32('0'), "isdigittmp");
1298    Op = B.CreateICmpULT(Op, B.getInt32(10), "isdigit");
1299    return B.CreateZExt(Op, CI->getType());
1300  }
1301};
1302
1303struct IsAsciiOpt : public LibCallOptimization {
1304  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1305    FunctionType *FT = Callee->getFunctionType();
1306    // We require integer(i32)
1307    if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
1308        !FT->getParamType(0)->isIntegerTy(32))
1309      return 0;
1310
1311    // isascii(c) -> c <u 128
1312    Value *Op = CI->getArgOperand(0);
1313    Op = B.CreateICmpULT(Op, B.getInt32(128), "isascii");
1314    return B.CreateZExt(Op, CI->getType());
1315  }
1316};
1317
1318struct ToAsciiOpt : public LibCallOptimization {
1319  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1320    FunctionType *FT = Callee->getFunctionType();
1321    // We require i32(i32)
1322    if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1323        !FT->getParamType(0)->isIntegerTy(32))
1324      return 0;
1325
1326    // toascii(c) -> c & 0x7f
1327    return B.CreateAnd(CI->getArgOperand(0),
1328                       ConstantInt::get(CI->getType(),0x7F));
1329  }
1330};
1331
1332//===----------------------------------------------------------------------===//
1333// Formatting and IO Library Call Optimizations
1334//===----------------------------------------------------------------------===//
1335
1336struct PrintFOpt : public LibCallOptimization {
1337  Value *optimizeFixedFormatString(Function *Callee, CallInst *CI,
1338                                   IRBuilder<> &B) {
1339    // Check for a fixed format string.
1340    StringRef FormatStr;
1341    if (!getConstantStringInfo(CI->getArgOperand(0), FormatStr))
1342      return 0;
1343
1344    // Empty format string -> noop.
1345    if (FormatStr.empty())  // Tolerate printf's declared void.
1346      return CI->use_empty() ? (Value*)CI :
1347                               ConstantInt::get(CI->getType(), 0);
1348
1349    // Do not do any of the following transformations if the printf return value
1350    // is used, in general the printf return value is not compatible with either
1351    // putchar() or puts().
1352    if (!CI->use_empty())
1353      return 0;
1354
1355    // printf("x") -> putchar('x'), even for '%'.
1356    if (FormatStr.size() == 1) {
1357      Value *Res = EmitPutChar(B.getInt32(FormatStr[0]), B, TD, TLI);
1358      if (CI->use_empty() || !Res) return Res;
1359      return B.CreateIntCast(Res, CI->getType(), true);
1360    }
1361
1362    // printf("foo\n") --> puts("foo")
1363    if (FormatStr[FormatStr.size()-1] == '\n' &&
1364        FormatStr.find('%') == std::string::npos) {  // no format characters.
1365      // Create a string literal with no \n on it.  We expect the constant merge
1366      // pass to be run after this pass, to merge duplicate strings.
1367      FormatStr = FormatStr.drop_back();
1368      Value *GV = B.CreateGlobalString(FormatStr, "str");
1369      Value *NewCI = EmitPutS(GV, B, TD, TLI);
1370      return (CI->use_empty() || !NewCI) ?
1371              NewCI :
1372              ConstantInt::get(CI->getType(), FormatStr.size()+1);
1373    }
1374
1375    // Optimize specific format strings.
1376    // printf("%c", chr) --> putchar(chr)
1377    if (FormatStr == "%c" && CI->getNumArgOperands() > 1 &&
1378        CI->getArgOperand(1)->getType()->isIntegerTy()) {
1379      Value *Res = EmitPutChar(CI->getArgOperand(1), B, TD, TLI);
1380
1381      if (CI->use_empty() || !Res) return Res;
1382      return B.CreateIntCast(Res, CI->getType(), true);
1383    }
1384
1385    // printf("%s\n", str) --> puts(str)
1386    if (FormatStr == "%s\n" && CI->getNumArgOperands() > 1 &&
1387        CI->getArgOperand(1)->getType()->isPointerTy()) {
1388      return EmitPutS(CI->getArgOperand(1), B, TD, TLI);
1389    }
1390    return 0;
1391  }
1392
1393  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1394    // Require one fixed pointer argument and an integer/void result.
1395    FunctionType *FT = Callee->getFunctionType();
1396    if (FT->getNumParams() < 1 || !FT->getParamType(0)->isPointerTy() ||
1397        !(FT->getReturnType()->isIntegerTy() ||
1398          FT->getReturnType()->isVoidTy()))
1399      return 0;
1400
1401    if (Value *V = optimizeFixedFormatString(Callee, CI, B)) {
1402      return V;
1403    }
1404
1405    // printf(format, ...) -> iprintf(format, ...) if no floating point
1406    // arguments.
1407    if (TLI->has(LibFunc::iprintf) && !callHasFloatingPointArgument(CI)) {
1408      Module *M = B.GetInsertBlock()->getParent()->getParent();
1409      Constant *IPrintFFn =
1410        M->getOrInsertFunction("iprintf", FT, Callee->getAttributes());
1411      CallInst *New = cast<CallInst>(CI->clone());
1412      New->setCalledFunction(IPrintFFn);
1413      B.Insert(New);
1414      return New;
1415    }
1416    return 0;
1417  }
1418};
1419
1420struct SPrintFOpt : public LibCallOptimization {
1421  Value *OptimizeFixedFormatString(Function *Callee, CallInst *CI,
1422                                   IRBuilder<> &B) {
1423    // Check for a fixed format string.
1424    StringRef FormatStr;
1425    if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr))
1426      return 0;
1427
1428    // If we just have a format string (nothing else crazy) transform it.
1429    if (CI->getNumArgOperands() == 2) {
1430      // Make sure there's no % in the constant array.  We could try to handle
1431      // %% -> % in the future if we cared.
1432      for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1433        if (FormatStr[i] == '%')
1434          return 0; // we found a format specifier, bail out.
1435
1436      // These optimizations require DataLayout.
1437      if (!TD) return 0;
1438
1439      // sprintf(str, fmt) -> llvm.memcpy(str, fmt, strlen(fmt)+1, 1)
1440      B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
1441                     ConstantInt::get(TD->getIntPtrType(*Context), // Copy the
1442                                      FormatStr.size() + 1), 1);   // nul byte.
1443      return ConstantInt::get(CI->getType(), FormatStr.size());
1444    }
1445
1446    // The remaining optimizations require the format string to be "%s" or "%c"
1447    // and have an extra operand.
1448    if (FormatStr.size() != 2 || FormatStr[0] != '%' ||
1449        CI->getNumArgOperands() < 3)
1450      return 0;
1451
1452    // Decode the second character of the format string.
1453    if (FormatStr[1] == 'c') {
1454      // sprintf(dst, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0
1455      if (!CI->getArgOperand(2)->getType()->isIntegerTy()) return 0;
1456      Value *V = B.CreateTrunc(CI->getArgOperand(2), B.getInt8Ty(), "char");
1457      Value *Ptr = CastToCStr(CI->getArgOperand(0), B);
1458      B.CreateStore(V, Ptr);
1459      Ptr = B.CreateGEP(Ptr, B.getInt32(1), "nul");
1460      B.CreateStore(B.getInt8(0), Ptr);
1461
1462      return ConstantInt::get(CI->getType(), 1);
1463    }
1464
1465    if (FormatStr[1] == 's') {
1466      // These optimizations require DataLayout.
1467      if (!TD) return 0;
1468
1469      // sprintf(dest, "%s", str) -> llvm.memcpy(dest, str, strlen(str)+1, 1)
1470      if (!CI->getArgOperand(2)->getType()->isPointerTy()) return 0;
1471
1472      Value *Len = EmitStrLen(CI->getArgOperand(2), B, TD, TLI);
1473      if (!Len)
1474        return 0;
1475      Value *IncLen = B.CreateAdd(Len,
1476                                  ConstantInt::get(Len->getType(), 1),
1477                                  "leninc");
1478      B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(2), IncLen, 1);
1479
1480      // The sprintf result is the unincremented number of bytes in the string.
1481      return B.CreateIntCast(Len, CI->getType(), false);
1482    }
1483    return 0;
1484  }
1485
1486  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1487    // Require two fixed pointer arguments and an integer result.
1488    FunctionType *FT = Callee->getFunctionType();
1489    if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
1490        !FT->getParamType(1)->isPointerTy() ||
1491        !FT->getReturnType()->isIntegerTy())
1492      return 0;
1493
1494    if (Value *V = OptimizeFixedFormatString(Callee, CI, B)) {
1495      return V;
1496    }
1497
1498    // sprintf(str, format, ...) -> siprintf(str, format, ...) if no floating
1499    // point arguments.
1500    if (TLI->has(LibFunc::siprintf) && !callHasFloatingPointArgument(CI)) {
1501      Module *M = B.GetInsertBlock()->getParent()->getParent();
1502      Constant *SIPrintFFn =
1503        M->getOrInsertFunction("siprintf", FT, Callee->getAttributes());
1504      CallInst *New = cast<CallInst>(CI->clone());
1505      New->setCalledFunction(SIPrintFFn);
1506      B.Insert(New);
1507      return New;
1508    }
1509    return 0;
1510  }
1511};
1512
1513struct FPrintFOpt : public LibCallOptimization {
1514  Value *optimizeFixedFormatString(Function *Callee, CallInst *CI,
1515                                   IRBuilder<> &B) {
1516    // All the optimizations depend on the format string.
1517    StringRef FormatStr;
1518    if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr))
1519      return 0;
1520
1521    // Do not do any of the following transformations if the fprintf return
1522    // value is used, in general the fprintf return value is not compatible
1523    // with fwrite(), fputc() or fputs().
1524    if (!CI->use_empty())
1525      return 0;
1526
1527    // fprintf(F, "foo") --> fwrite("foo", 3, 1, F)
1528    if (CI->getNumArgOperands() == 2) {
1529      for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1530        if (FormatStr[i] == '%')  // Could handle %% -> % if we cared.
1531          return 0; // We found a format specifier.
1532
1533      // These optimizations require DataLayout.
1534      if (!TD) return 0;
1535
1536      return EmitFWrite(CI->getArgOperand(1),
1537                        ConstantInt::get(TD->getIntPtrType(*Context),
1538                                         FormatStr.size()),
1539                        CI->getArgOperand(0), B, TD, TLI);
1540    }
1541
1542    // The remaining optimizations require the format string to be "%s" or "%c"
1543    // and have an extra operand.
1544    if (FormatStr.size() != 2 || FormatStr[0] != '%' ||
1545        CI->getNumArgOperands() < 3)
1546      return 0;
1547
1548    // Decode the second character of the format string.
1549    if (FormatStr[1] == 'c') {
1550      // fprintf(F, "%c", chr) --> fputc(chr, F)
1551      if (!CI->getArgOperand(2)->getType()->isIntegerTy()) return 0;
1552      return EmitFPutC(CI->getArgOperand(2), CI->getArgOperand(0), B, TD, TLI);
1553    }
1554
1555    if (FormatStr[1] == 's') {
1556      // fprintf(F, "%s", str) --> fputs(str, F)
1557      if (!CI->getArgOperand(2)->getType()->isPointerTy())
1558        return 0;
1559      return EmitFPutS(CI->getArgOperand(2), CI->getArgOperand(0), B, TD, TLI);
1560    }
1561    return 0;
1562  }
1563
1564  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1565    // Require two fixed paramters as pointers and integer result.
1566    FunctionType *FT = Callee->getFunctionType();
1567    if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
1568        !FT->getParamType(1)->isPointerTy() ||
1569        !FT->getReturnType()->isIntegerTy())
1570      return 0;
1571
1572    if (Value *V = optimizeFixedFormatString(Callee, CI, B)) {
1573      return V;
1574    }
1575
1576    // fprintf(stream, format, ...) -> fiprintf(stream, format, ...) if no
1577    // floating point arguments.
1578    if (TLI->has(LibFunc::fiprintf) && !callHasFloatingPointArgument(CI)) {
1579      Module *M = B.GetInsertBlock()->getParent()->getParent();
1580      Constant *FIPrintFFn =
1581        M->getOrInsertFunction("fiprintf", FT, Callee->getAttributes());
1582      CallInst *New = cast<CallInst>(CI->clone());
1583      New->setCalledFunction(FIPrintFFn);
1584      B.Insert(New);
1585      return New;
1586    }
1587    return 0;
1588  }
1589};
1590
1591struct FWriteOpt : public LibCallOptimization {
1592  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1593    // Require a pointer, an integer, an integer, a pointer, returning integer.
1594    FunctionType *FT = Callee->getFunctionType();
1595    if (FT->getNumParams() != 4 || !FT->getParamType(0)->isPointerTy() ||
1596        !FT->getParamType(1)->isIntegerTy() ||
1597        !FT->getParamType(2)->isIntegerTy() ||
1598        !FT->getParamType(3)->isPointerTy() ||
1599        !FT->getReturnType()->isIntegerTy())
1600      return 0;
1601
1602    // Get the element size and count.
1603    ConstantInt *SizeC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
1604    ConstantInt *CountC = dyn_cast<ConstantInt>(CI->getArgOperand(2));
1605    if (!SizeC || !CountC) return 0;
1606    uint64_t Bytes = SizeC->getZExtValue()*CountC->getZExtValue();
1607
1608    // If this is writing zero records, remove the call (it's a noop).
1609    if (Bytes == 0)
1610      return ConstantInt::get(CI->getType(), 0);
1611
1612    // If this is writing one byte, turn it into fputc.
1613    // This optimisation is only valid, if the return value is unused.
1614    if (Bytes == 1 && CI->use_empty()) {  // fwrite(S,1,1,F) -> fputc(S[0],F)
1615      Value *Char = B.CreateLoad(CastToCStr(CI->getArgOperand(0), B), "char");
1616      Value *NewCI = EmitFPutC(Char, CI->getArgOperand(3), B, TD, TLI);
1617      return NewCI ? ConstantInt::get(CI->getType(), 1) : 0;
1618    }
1619
1620    return 0;
1621  }
1622};
1623
1624struct FPutsOpt : public LibCallOptimization {
1625  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1626    // These optimizations require DataLayout.
1627    if (!TD) return 0;
1628
1629    // Require two pointers.  Also, we can't optimize if return value is used.
1630    FunctionType *FT = Callee->getFunctionType();
1631    if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
1632        !FT->getParamType(1)->isPointerTy() ||
1633        !CI->use_empty())
1634      return 0;
1635
1636    // fputs(s,F) --> fwrite(s,1,strlen(s),F)
1637    uint64_t Len = GetStringLength(CI->getArgOperand(0));
1638    if (!Len) return 0;
1639    // Known to have no uses (see above).
1640    return EmitFWrite(CI->getArgOperand(0),
1641                      ConstantInt::get(TD->getIntPtrType(*Context), Len-1),
1642                      CI->getArgOperand(1), B, TD, TLI);
1643  }
1644};
1645
1646struct PutsOpt : public LibCallOptimization {
1647  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1648    // Require one fixed pointer argument and an integer/void result.
1649    FunctionType *FT = Callee->getFunctionType();
1650    if (FT->getNumParams() < 1 || !FT->getParamType(0)->isPointerTy() ||
1651        !(FT->getReturnType()->isIntegerTy() ||
1652          FT->getReturnType()->isVoidTy()))
1653      return 0;
1654
1655    // Check for a constant string.
1656    StringRef Str;
1657    if (!getConstantStringInfo(CI->getArgOperand(0), Str))
1658      return 0;
1659
1660    if (Str.empty() && CI->use_empty()) {
1661      // puts("") -> putchar('\n')
1662      Value *Res = EmitPutChar(B.getInt32('\n'), B, TD, TLI);
1663      if (CI->use_empty() || !Res) return Res;
1664      return B.CreateIntCast(Res, CI->getType(), true);
1665    }
1666
1667    return 0;
1668  }
1669};
1670
1671} // End anonymous namespace.
1672
1673namespace llvm {
1674
1675class LibCallSimplifierImpl {
1676  const DataLayout *TD;
1677  const TargetLibraryInfo *TLI;
1678  const LibCallSimplifier *LCS;
1679  bool UnsafeFPShrink;
1680
1681  // Math library call optimizations.
1682  CosOpt Cos;
1683  PowOpt Pow;
1684  Exp2Opt Exp2;
1685public:
1686  LibCallSimplifierImpl(const DataLayout *TD, const TargetLibraryInfo *TLI,
1687                        const LibCallSimplifier *LCS,
1688                        bool UnsafeFPShrink = false)
1689    : Cos(UnsafeFPShrink), Pow(UnsafeFPShrink), Exp2(UnsafeFPShrink) {
1690    this->TD = TD;
1691    this->TLI = TLI;
1692    this->LCS = LCS;
1693    this->UnsafeFPShrink = UnsafeFPShrink;
1694  }
1695
1696  Value *optimizeCall(CallInst *CI);
1697  LibCallOptimization *lookupOptimization(CallInst *CI);
1698  bool hasFloatVersion(StringRef FuncName);
1699};
1700
1701bool LibCallSimplifierImpl::hasFloatVersion(StringRef FuncName) {
1702  LibFunc::Func Func;
1703  SmallString<20> FloatFuncName = FuncName;
1704  FloatFuncName += 'f';
1705  if (TLI->getLibFunc(FloatFuncName, Func))
1706    return TLI->has(Func);
1707  return false;
1708}
1709
1710// Fortified library call optimizations.
1711static MemCpyChkOpt MemCpyChk;
1712static MemMoveChkOpt MemMoveChk;
1713static MemSetChkOpt MemSetChk;
1714static StrCpyChkOpt StrCpyChk;
1715static StpCpyChkOpt StpCpyChk;
1716static StrNCpyChkOpt StrNCpyChk;
1717
1718// String library call optimizations.
1719static StrCatOpt StrCat;
1720static StrNCatOpt StrNCat;
1721static StrChrOpt StrChr;
1722static StrRChrOpt StrRChr;
1723static StrCmpOpt StrCmp;
1724static StrNCmpOpt StrNCmp;
1725static StrCpyOpt StrCpy;
1726static StpCpyOpt StpCpy;
1727static StrNCpyOpt StrNCpy;
1728static StrLenOpt StrLen;
1729static StrPBrkOpt StrPBrk;
1730static StrToOpt StrTo;
1731static StrSpnOpt StrSpn;
1732static StrCSpnOpt StrCSpn;
1733static StrStrOpt StrStr;
1734
1735// Memory library call optimizations.
1736static MemCmpOpt MemCmp;
1737static MemCpyOpt MemCpy;
1738static MemMoveOpt MemMove;
1739static MemSetOpt MemSet;
1740
1741// Math library call optimizations.
1742static UnaryDoubleFPOpt UnaryDoubleFP(false);
1743static UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
1744
1745  // Integer library call optimizations.
1746static FFSOpt FFS;
1747static AbsOpt Abs;
1748static IsDigitOpt IsDigit;
1749static IsAsciiOpt IsAscii;
1750static ToAsciiOpt ToAscii;
1751
1752// Formatting and IO library call optimizations.
1753static PrintFOpt PrintF;
1754static SPrintFOpt SPrintF;
1755static FPrintFOpt FPrintF;
1756static FWriteOpt FWrite;
1757static FPutsOpt FPuts;
1758static PutsOpt Puts;
1759
1760LibCallOptimization *LibCallSimplifierImpl::lookupOptimization(CallInst *CI) {
1761  LibFunc::Func Func;
1762  Function *Callee = CI->getCalledFunction();
1763  StringRef FuncName = Callee->getName();
1764
1765  // Next check for intrinsics.
1766  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI)) {
1767    switch (II->getIntrinsicID()) {
1768    case Intrinsic::pow:
1769       return &Pow;
1770    case Intrinsic::exp2:
1771       return &Exp2;
1772    default:
1773       return 0;
1774    }
1775  }
1776
1777  // Then check for known library functions.
1778  if (TLI->getLibFunc(FuncName, Func) && TLI->has(Func)) {
1779    switch (Func) {
1780      case LibFunc::strcat:
1781        return &StrCat;
1782      case LibFunc::strncat:
1783        return &StrNCat;
1784      case LibFunc::strchr:
1785        return &StrChr;
1786      case LibFunc::strrchr:
1787        return &StrRChr;
1788      case LibFunc::strcmp:
1789        return &StrCmp;
1790      case LibFunc::strncmp:
1791        return &StrNCmp;
1792      case LibFunc::strcpy:
1793        return &StrCpy;
1794      case LibFunc::stpcpy:
1795        return &StpCpy;
1796      case LibFunc::strncpy:
1797        return &StrNCpy;
1798      case LibFunc::strlen:
1799        return &StrLen;
1800      case LibFunc::strpbrk:
1801        return &StrPBrk;
1802      case LibFunc::strtol:
1803      case LibFunc::strtod:
1804      case LibFunc::strtof:
1805      case LibFunc::strtoul:
1806      case LibFunc::strtoll:
1807      case LibFunc::strtold:
1808      case LibFunc::strtoull:
1809        return &StrTo;
1810      case LibFunc::strspn:
1811        return &StrSpn;
1812      case LibFunc::strcspn:
1813        return &StrCSpn;
1814      case LibFunc::strstr:
1815        return &StrStr;
1816      case LibFunc::memcmp:
1817        return &MemCmp;
1818      case LibFunc::memcpy:
1819        return &MemCpy;
1820      case LibFunc::memmove:
1821        return &MemMove;
1822      case LibFunc::memset:
1823        return &MemSet;
1824      case LibFunc::cosf:
1825      case LibFunc::cos:
1826      case LibFunc::cosl:
1827        return &Cos;
1828      case LibFunc::powf:
1829      case LibFunc::pow:
1830      case LibFunc::powl:
1831        return &Pow;
1832      case LibFunc::exp2l:
1833      case LibFunc::exp2:
1834      case LibFunc::exp2f:
1835        return &Exp2;
1836      case LibFunc::ffs:
1837      case LibFunc::ffsl:
1838      case LibFunc::ffsll:
1839        return &FFS;
1840      case LibFunc::abs:
1841      case LibFunc::labs:
1842      case LibFunc::llabs:
1843        return &Abs;
1844      case LibFunc::isdigit:
1845        return &IsDigit;
1846      case LibFunc::isascii:
1847        return &IsAscii;
1848      case LibFunc::toascii:
1849        return &ToAscii;
1850      case LibFunc::printf:
1851        return &PrintF;
1852      case LibFunc::sprintf:
1853        return &SPrintF;
1854      case LibFunc::fprintf:
1855        return &FPrintF;
1856      case LibFunc::fwrite:
1857        return &FWrite;
1858      case LibFunc::fputs:
1859        return &FPuts;
1860      case LibFunc::puts:
1861        return &Puts;
1862      case LibFunc::ceil:
1863      case LibFunc::fabs:
1864      case LibFunc::floor:
1865      case LibFunc::rint:
1866      case LibFunc::round:
1867      case LibFunc::nearbyint:
1868      case LibFunc::trunc:
1869        if (hasFloatVersion(FuncName))
1870          return &UnaryDoubleFP;
1871        return 0;
1872      case LibFunc::acos:
1873      case LibFunc::acosh:
1874      case LibFunc::asin:
1875      case LibFunc::asinh:
1876      case LibFunc::atan:
1877      case LibFunc::atanh:
1878      case LibFunc::cbrt:
1879      case LibFunc::cosh:
1880      case LibFunc::exp:
1881      case LibFunc::exp10:
1882      case LibFunc::expm1:
1883      case LibFunc::log:
1884      case LibFunc::log10:
1885      case LibFunc::log1p:
1886      case LibFunc::log2:
1887      case LibFunc::logb:
1888      case LibFunc::sin:
1889      case LibFunc::sinh:
1890      case LibFunc::sqrt:
1891      case LibFunc::tan:
1892      case LibFunc::tanh:
1893        if (UnsafeFPShrink && hasFloatVersion(FuncName))
1894         return &UnsafeUnaryDoubleFP;
1895        return 0;
1896      case LibFunc::memcpy_chk:
1897        return &MemCpyChk;
1898      default:
1899        return 0;
1900      }
1901  }
1902
1903  // Finally check for fortified library calls.
1904  if (FuncName.endswith("_chk")) {
1905    if (FuncName == "__memmove_chk")
1906      return &MemMoveChk;
1907    else if (FuncName == "__memset_chk")
1908      return &MemSetChk;
1909    else if (FuncName == "__strcpy_chk")
1910      return &StrCpyChk;
1911    else if (FuncName == "__stpcpy_chk")
1912      return &StpCpyChk;
1913    else if (FuncName == "__strncpy_chk")
1914      return &StrNCpyChk;
1915    else if (FuncName == "__stpncpy_chk")
1916      return &StrNCpyChk;
1917  }
1918
1919  return 0;
1920
1921}
1922
1923Value *LibCallSimplifierImpl::optimizeCall(CallInst *CI) {
1924  LibCallOptimization *LCO = lookupOptimization(CI);
1925  if (LCO) {
1926    IRBuilder<> Builder(CI);
1927    return LCO->optimizeCall(CI, TD, TLI, LCS, Builder);
1928  }
1929  return 0;
1930}
1931
1932LibCallSimplifier::LibCallSimplifier(const DataLayout *TD,
1933                                     const TargetLibraryInfo *TLI,
1934                                     bool UnsafeFPShrink) {
1935  Impl = new LibCallSimplifierImpl(TD, TLI, this, UnsafeFPShrink);
1936}
1937
1938LibCallSimplifier::~LibCallSimplifier() {
1939  delete Impl;
1940}
1941
1942Value *LibCallSimplifier::optimizeCall(CallInst *CI) {
1943  if (CI->hasFnAttr(Attribute::NoBuiltin)) return 0;
1944  return Impl->optimizeCall(CI);
1945}
1946
1947void LibCallSimplifier::replaceAllUsesWith(Instruction *I, Value *With) const {
1948  I->replaceAllUsesWith(With);
1949  I->eraseFromParent();
1950}
1951
1952}
1953