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