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