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