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