1//===- SimplifyLibCalls.cpp - Optimize specific well-known library calls --===//
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 file implements a simple pass that applies a variety of small
11// optimizations for calls to specific well-known function calls (e.g. runtime
12// library functions).   Any optimization that takes the very simple form
13// "replace call to library function with simpler code that provides the same
14// result" belongs in this file.
15//
16//===----------------------------------------------------------------------===//
17
18#define DEBUG_TYPE "simplify-libcalls"
19#include "llvm/Transforms/Scalar.h"
20#include "llvm/Transforms/Utils/BuildLibCalls.h"
21#include "llvm/IRBuilder.h"
22#include "llvm/Intrinsics.h"
23#include "llvm/LLVMContext.h"
24#include "llvm/Module.h"
25#include "llvm/Pass.h"
26#include "llvm/ADT/STLExtras.h"
27#include "llvm/ADT/SmallPtrSet.h"
28#include "llvm/ADT/Statistic.h"
29#include "llvm/ADT/StringMap.h"
30#include "llvm/Analysis/ValueTracking.h"
31#include "llvm/Support/CommandLine.h"
32#include "llvm/Support/Debug.h"
33#include "llvm/Support/raw_ostream.h"
34#include "llvm/Target/TargetData.h"
35#include "llvm/Target/TargetLibraryInfo.h"
36#include "llvm/Config/config.h"            // FIXME: Shouldn't depend on host!
37using namespace llvm;
38
39STATISTIC(NumSimplified, "Number of library calls simplified");
40STATISTIC(NumAnnotated, "Number of attributes added to library functions");
41
42static cl::opt<bool> UnsafeFPShrink("enable-double-float-shrink", cl::Hidden,
43                                   cl::init(false),
44                                   cl::desc("Enable unsafe double to float "
45                                            "shrinking for math lib calls"));
46//===----------------------------------------------------------------------===//
47// Optimizer Base Class
48//===----------------------------------------------------------------------===//
49
50/// This class is the abstract base class for the set of optimizations that
51/// corresponds to one library call.
52namespace {
53class LibCallOptimization {
54protected:
55  Function *Caller;
56  const TargetData *TD;
57  const TargetLibraryInfo *TLI;
58  LLVMContext* Context;
59public:
60  LibCallOptimization() { }
61  virtual ~LibCallOptimization() {}
62
63  /// CallOptimizer - This pure virtual method is implemented by base classes to
64  /// do various optimizations.  If this returns null then no transformation was
65  /// performed.  If it returns CI, then it transformed the call and CI is to be
66  /// deleted.  If it returns something else, replace CI with the new value and
67  /// delete CI.
68  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B)
69    =0;
70
71  Value *OptimizeCall(CallInst *CI, const TargetData *TD,
72                      const TargetLibraryInfo *TLI, IRBuilder<> &B) {
73    Caller = CI->getParent()->getParent();
74    this->TD = TD;
75    this->TLI = TLI;
76    if (CI->getCalledFunction())
77      Context = &CI->getCalledFunction()->getContext();
78
79    // We never change the calling convention.
80    if (CI->getCallingConv() != llvm::CallingConv::C)
81      return NULL;
82
83    return CallOptimizer(CI->getCalledFunction(), CI, B);
84  }
85};
86} // End anonymous namespace.
87
88
89//===----------------------------------------------------------------------===//
90// Helper Functions
91//===----------------------------------------------------------------------===//
92
93/// IsOnlyUsedInZeroEqualityComparison - Return true if it only matters that the
94/// value is equal or not-equal to zero.
95static bool IsOnlyUsedInZeroEqualityComparison(Value *V) {
96  for (Value::use_iterator UI = V->use_begin(), E = V->use_end();
97       UI != E; ++UI) {
98    if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI))
99      if (IC->isEquality())
100        if (Constant *C = dyn_cast<Constant>(IC->getOperand(1)))
101          if (C->isNullValue())
102            continue;
103    // Unknown instruction.
104    return false;
105  }
106  return true;
107}
108
109static 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/// IsOnlyUsedInEqualityComparison - Return true if it is only used in equality
119/// comparisons with With.
120static bool IsOnlyUsedInEqualityComparison(Value *V, Value *With) {
121  for (Value::use_iterator UI = V->use_begin(), E = V->use_end();
122       UI != E; ++UI) {
123    if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI))
124      if (IC->isEquality() && IC->getOperand(1) == With)
125        continue;
126    // Unknown instruction.
127    return false;
128  }
129  return true;
130}
131
132//===----------------------------------------------------------------------===//
133// String and Memory LibCall Optimizations
134//===----------------------------------------------------------------------===//
135
136//===---------------------------------------===//
137// 'strcat' Optimizations
138namespace {
139struct StrCatOpt : public LibCallOptimization {
140  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
141    // Verify the "strcat" function prototype.
142    FunctionType *FT = Callee->getFunctionType();
143    if (FT->getNumParams() != 2 ||
144        FT->getReturnType() != B.getInt8PtrTy() ||
145        FT->getParamType(0) != FT->getReturnType() ||
146        FT->getParamType(1) != FT->getReturnType())
147      return 0;
148
149    // Extract some information from the instruction
150    Value *Dst = CI->getArgOperand(0);
151    Value *Src = CI->getArgOperand(1);
152
153    // See if we can get the length of the input string.
154    uint64_t Len = GetStringLength(Src);
155    if (Len == 0) return 0;
156    --Len;  // Unbias length.
157
158    // Handle the simple, do-nothing case: strcat(x, "") -> x
159    if (Len == 0)
160      return Dst;
161
162    // These optimizations require TargetData.
163    if (!TD) return 0;
164
165    return EmitStrLenMemCpy(Src, Dst, Len, B);
166  }
167
168  Value *EmitStrLenMemCpy(Value *Src, Value *Dst, uint64_t Len, IRBuilder<> &B) {
169    // We need to find the end of the destination string.  That's where the
170    // memory is to be moved to. We just generate a call to strlen.
171    Value *DstLen = EmitStrLen(Dst, B, TD, TLI);
172    if (!DstLen)
173      return 0;
174
175    // Now that we have the destination's length, we must index into the
176    // destination's pointer to get the actual memcpy destination (end of
177    // the string .. we're concatenating).
178    Value *CpyDst = B.CreateGEP(Dst, DstLen, "endptr");
179
180    // We have enough information to now generate the memcpy call to do the
181    // concatenation for us.  Make a memcpy to copy the nul byte with align = 1.
182    B.CreateMemCpy(CpyDst, Src,
183                   ConstantInt::get(TD->getIntPtrType(*Context), Len + 1), 1);
184    return Dst;
185  }
186};
187
188//===---------------------------------------===//
189// 'strncat' Optimizations
190
191struct StrNCatOpt : public StrCatOpt {
192  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
193    // Verify the "strncat" function prototype.
194    FunctionType *FT = Callee->getFunctionType();
195    if (FT->getNumParams() != 3 ||
196        FT->getReturnType() != B.getInt8PtrTy() ||
197        FT->getParamType(0) != FT->getReturnType() ||
198        FT->getParamType(1) != FT->getReturnType() ||
199        !FT->getParamType(2)->isIntegerTy())
200      return 0;
201
202    // Extract some information from the instruction
203    Value *Dst = CI->getArgOperand(0);
204    Value *Src = CI->getArgOperand(1);
205    uint64_t Len;
206
207    // We don't do anything if length is not constant
208    if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
209      Len = LengthArg->getZExtValue();
210    else
211      return 0;
212
213    // See if we can get the length of the input string.
214    uint64_t SrcLen = GetStringLength(Src);
215    if (SrcLen == 0) return 0;
216    --SrcLen;  // Unbias length.
217
218    // Handle the simple, do-nothing cases:
219    // strncat(x, "", c) -> x
220    // strncat(x,  c, 0) -> x
221    if (SrcLen == 0 || Len == 0) return Dst;
222
223    // These optimizations require TargetData.
224    if (!TD) return 0;
225
226    // We don't optimize this case
227    if (Len < SrcLen) return 0;
228
229    // strncat(x, s, c) -> strcat(x, s)
230    // s is constant so the strcat can be optimized further
231    return EmitStrLenMemCpy(Src, Dst, SrcLen, B);
232  }
233};
234
235//===---------------------------------------===//
236// 'strchr' Optimizations
237
238struct StrChrOpt : public LibCallOptimization {
239  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
240    // Verify the "strchr" function prototype.
241    FunctionType *FT = Callee->getFunctionType();
242    if (FT->getNumParams() != 2 ||
243        FT->getReturnType() != B.getInt8PtrTy() ||
244        FT->getParamType(0) != FT->getReturnType() ||
245        !FT->getParamType(1)->isIntegerTy(32))
246      return 0;
247
248    Value *SrcStr = CI->getArgOperand(0);
249
250    // If the second operand is non-constant, see if we can compute the length
251    // of the input string and turn this into memchr.
252    ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
253    if (CharC == 0) {
254      // These optimizations require TargetData.
255      if (!TD) return 0;
256
257      uint64_t Len = GetStringLength(SrcStr);
258      if (Len == 0 || !FT->getParamType(1)->isIntegerTy(32))// memchr needs i32.
259        return 0;
260
261      return EmitMemChr(SrcStr, CI->getArgOperand(1), // include nul.
262                        ConstantInt::get(TD->getIntPtrType(*Context), Len),
263                        B, TD, TLI);
264    }
265
266    // Otherwise, the character is a constant, see if the first argument is
267    // a string literal.  If so, we can constant fold.
268    StringRef Str;
269    if (!getConstantStringInfo(SrcStr, Str))
270      return 0;
271
272    // Compute the offset, make sure to handle the case when we're searching for
273    // zero (a weird way to spell strlen).
274    size_t I = CharC->getSExtValue() == 0 ?
275        Str.size() : Str.find(CharC->getSExtValue());
276    if (I == StringRef::npos) // Didn't find the char.  strchr returns null.
277      return Constant::getNullValue(CI->getType());
278
279    // strchr(s+n,c)  -> gep(s+n+i,c)
280    return B.CreateGEP(SrcStr, B.getInt64(I), "strchr");
281  }
282};
283
284//===---------------------------------------===//
285// 'strrchr' Optimizations
286
287struct StrRChrOpt : public LibCallOptimization {
288  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
289    // Verify the "strrchr" function prototype.
290    FunctionType *FT = Callee->getFunctionType();
291    if (FT->getNumParams() != 2 ||
292        FT->getReturnType() != B.getInt8PtrTy() ||
293        FT->getParamType(0) != FT->getReturnType() ||
294        !FT->getParamType(1)->isIntegerTy(32))
295      return 0;
296
297    Value *SrcStr = CI->getArgOperand(0);
298    ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
299
300    // Cannot fold anything if we're not looking for a constant.
301    if (!CharC)
302      return 0;
303
304    StringRef Str;
305    if (!getConstantStringInfo(SrcStr, Str)) {
306      // strrchr(s, 0) -> strchr(s, 0)
307      if (TD && CharC->isZero())
308        return EmitStrChr(SrcStr, '\0', B, TD, TLI);
309      return 0;
310    }
311
312    // Compute the offset.
313    size_t I = CharC->getSExtValue() == 0 ?
314        Str.size() : Str.rfind(CharC->getSExtValue());
315    if (I == StringRef::npos) // Didn't find the char. Return null.
316      return Constant::getNullValue(CI->getType());
317
318    // strrchr(s+n,c) -> gep(s+n+i,c)
319    return B.CreateGEP(SrcStr, B.getInt64(I), "strrchr");
320  }
321};
322
323//===---------------------------------------===//
324// 'strcmp' Optimizations
325
326struct StrCmpOpt : public LibCallOptimization {
327  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
328    // Verify the "strcmp" function prototype.
329    FunctionType *FT = Callee->getFunctionType();
330    if (FT->getNumParams() != 2 ||
331        !FT->getReturnType()->isIntegerTy(32) ||
332        FT->getParamType(0) != FT->getParamType(1) ||
333        FT->getParamType(0) != B.getInt8PtrTy())
334      return 0;
335
336    Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
337    if (Str1P == Str2P)      // strcmp(x,x)  -> 0
338      return ConstantInt::get(CI->getType(), 0);
339
340    StringRef Str1, Str2;
341    bool HasStr1 = getConstantStringInfo(Str1P, Str1);
342    bool HasStr2 = getConstantStringInfo(Str2P, Str2);
343
344    // strcmp(x, y)  -> cnst  (if both x and y are constant strings)
345    if (HasStr1 && HasStr2)
346      return ConstantInt::get(CI->getType(), Str1.compare(Str2));
347
348    if (HasStr1 && Str1.empty()) // strcmp("", x) -> -*x
349      return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"),
350                                      CI->getType()));
351
352    if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x
353      return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
354
355    // strcmp(P, "x") -> memcmp(P, "x", 2)
356    uint64_t Len1 = GetStringLength(Str1P);
357    uint64_t Len2 = GetStringLength(Str2P);
358    if (Len1 && Len2) {
359      // These optimizations require TargetData.
360      if (!TD) return 0;
361
362      return EmitMemCmp(Str1P, Str2P,
363                        ConstantInt::get(TD->getIntPtrType(*Context),
364                        std::min(Len1, Len2)), B, TD, TLI);
365    }
366
367    return 0;
368  }
369};
370
371//===---------------------------------------===//
372// 'strncmp' Optimizations
373
374struct StrNCmpOpt : public LibCallOptimization {
375  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
376    // Verify the "strncmp" function prototype.
377    FunctionType *FT = Callee->getFunctionType();
378    if (FT->getNumParams() != 3 ||
379        !FT->getReturnType()->isIntegerTy(32) ||
380        FT->getParamType(0) != FT->getParamType(1) ||
381        FT->getParamType(0) != B.getInt8PtrTy() ||
382        !FT->getParamType(2)->isIntegerTy())
383      return 0;
384
385    Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
386    if (Str1P == Str2P)      // strncmp(x,x,n)  -> 0
387      return ConstantInt::get(CI->getType(), 0);
388
389    // Get the length argument if it is constant.
390    uint64_t Length;
391    if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
392      Length = LengthArg->getZExtValue();
393    else
394      return 0;
395
396    if (Length == 0) // strncmp(x,y,0)   -> 0
397      return ConstantInt::get(CI->getType(), 0);
398
399    if (TD && Length == 1) // strncmp(x,y,1) -> memcmp(x,y,1)
400      return EmitMemCmp(Str1P, Str2P, CI->getArgOperand(2), B, TD, TLI);
401
402    StringRef Str1, Str2;
403    bool HasStr1 = getConstantStringInfo(Str1P, Str1);
404    bool HasStr2 = getConstantStringInfo(Str2P, Str2);
405
406    // strncmp(x, y)  -> cnst  (if both x and y are constant strings)
407    if (HasStr1 && HasStr2) {
408      StringRef SubStr1 = Str1.substr(0, Length);
409      StringRef SubStr2 = Str2.substr(0, Length);
410      return ConstantInt::get(CI->getType(), SubStr1.compare(SubStr2));
411    }
412
413    if (HasStr1 && Str1.empty())  // strncmp("", x, n) -> -*x
414      return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"),
415                                      CI->getType()));
416
417    if (HasStr2 && Str2.empty())  // strncmp(x, "", n) -> *x
418      return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
419
420    return 0;
421  }
422};
423
424
425//===---------------------------------------===//
426// 'strcpy' Optimizations
427
428struct StrCpyOpt : public LibCallOptimization {
429  bool OptChkCall;  // True if it's optimizing a __strcpy_chk libcall.
430
431  StrCpyOpt(bool c) : OptChkCall(c) {}
432
433  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
434    // Verify the "strcpy" function prototype.
435    unsigned NumParams = OptChkCall ? 3 : 2;
436    FunctionType *FT = Callee->getFunctionType();
437    if (FT->getNumParams() != NumParams ||
438        FT->getReturnType() != FT->getParamType(0) ||
439        FT->getParamType(0) != FT->getParamType(1) ||
440        FT->getParamType(0) != B.getInt8PtrTy())
441      return 0;
442
443    Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
444    if (Dst == Src)      // strcpy(x,x)  -> x
445      return Src;
446
447    // These optimizations require TargetData.
448    if (!TD) return 0;
449
450    // See if we can get the length of the input string.
451    uint64_t Len = GetStringLength(Src);
452    if (Len == 0) return 0;
453
454    // We have enough information to now generate the memcpy call to do the
455    // concatenation for us.  Make a memcpy to copy the nul byte with align = 1.
456    if (!OptChkCall ||
457        !EmitMemCpyChk(Dst, Src,
458                       ConstantInt::get(TD->getIntPtrType(*Context), Len),
459                       CI->getArgOperand(2), B, TD, TLI))
460      B.CreateMemCpy(Dst, Src,
461                     ConstantInt::get(TD->getIntPtrType(*Context), Len), 1);
462    return Dst;
463  }
464};
465
466//===---------------------------------------===//
467// 'stpcpy' Optimizations
468
469struct StpCpyOpt: public LibCallOptimization {
470  bool OptChkCall;  // True if it's optimizing a __stpcpy_chk libcall.
471
472  StpCpyOpt(bool c) : OptChkCall(c) {}
473
474  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
475    // Verify the "stpcpy" function prototype.
476    unsigned NumParams = OptChkCall ? 3 : 2;
477    FunctionType *FT = Callee->getFunctionType();
478    if (FT->getNumParams() != NumParams ||
479        FT->getReturnType() != FT->getParamType(0) ||
480        FT->getParamType(0) != FT->getParamType(1) ||
481        FT->getParamType(0) != B.getInt8PtrTy())
482      return 0;
483
484    // These optimizations require TargetData.
485    if (!TD) return 0;
486
487    Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
488    if (Dst == Src) {  // stpcpy(x,x)  -> x+strlen(x)
489      Value *StrLen = EmitStrLen(Src, B, TD, TLI);
490      return StrLen ? B.CreateInBoundsGEP(Dst, StrLen) : 0;
491    }
492
493    // See if we can get the length of the input string.
494    uint64_t Len = GetStringLength(Src);
495    if (Len == 0) return 0;
496
497    Value *LenV = ConstantInt::get(TD->getIntPtrType(*Context), Len);
498    Value *DstEnd = B.CreateGEP(Dst,
499                                ConstantInt::get(TD->getIntPtrType(*Context),
500                                                 Len - 1));
501
502    // We have enough information to now generate the memcpy call to do the
503    // copy for us.  Make a memcpy to copy the nul byte with align = 1.
504    if (!OptChkCall || !EmitMemCpyChk(Dst, Src, LenV, CI->getArgOperand(2), B,
505                                      TD, TLI))
506      B.CreateMemCpy(Dst, Src, LenV, 1);
507    return DstEnd;
508  }
509};
510
511//===---------------------------------------===//
512// 'strncpy' Optimizations
513
514struct StrNCpyOpt : public LibCallOptimization {
515  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
516    FunctionType *FT = Callee->getFunctionType();
517    if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
518        FT->getParamType(0) != FT->getParamType(1) ||
519        FT->getParamType(0) != B.getInt8PtrTy() ||
520        !FT->getParamType(2)->isIntegerTy())
521      return 0;
522
523    Value *Dst = CI->getArgOperand(0);
524    Value *Src = CI->getArgOperand(1);
525    Value *LenOp = CI->getArgOperand(2);
526
527    // See if we can get the length of the input string.
528    uint64_t SrcLen = GetStringLength(Src);
529    if (SrcLen == 0) return 0;
530    --SrcLen;
531
532    if (SrcLen == 0) {
533      // strncpy(x, "", y) -> memset(x, '\0', y, 1)
534      B.CreateMemSet(Dst, B.getInt8('\0'), LenOp, 1);
535      return Dst;
536    }
537
538    uint64_t Len;
539    if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(LenOp))
540      Len = LengthArg->getZExtValue();
541    else
542      return 0;
543
544    if (Len == 0) return Dst; // strncpy(x, y, 0) -> x
545
546    // These optimizations require TargetData.
547    if (!TD) return 0;
548
549    // Let strncpy handle the zero padding
550    if (Len > SrcLen+1) return 0;
551
552    // strncpy(x, s, c) -> memcpy(x, s, c, 1) [s and c are constant]
553    B.CreateMemCpy(Dst, Src,
554                   ConstantInt::get(TD->getIntPtrType(*Context), Len), 1);
555
556    return Dst;
557  }
558};
559
560//===---------------------------------------===//
561// 'strlen' Optimizations
562
563struct StrLenOpt : public LibCallOptimization {
564  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
565    FunctionType *FT = Callee->getFunctionType();
566    if (FT->getNumParams() != 1 ||
567        FT->getParamType(0) != B.getInt8PtrTy() ||
568        !FT->getReturnType()->isIntegerTy())
569      return 0;
570
571    Value *Src = CI->getArgOperand(0);
572
573    // Constant folding: strlen("xyz") -> 3
574    if (uint64_t Len = GetStringLength(Src))
575      return ConstantInt::get(CI->getType(), Len-1);
576
577    // strlen(x) != 0 --> *x != 0
578    // strlen(x) == 0 --> *x == 0
579    if (IsOnlyUsedInZeroEqualityComparison(CI))
580      return B.CreateZExt(B.CreateLoad(Src, "strlenfirst"), CI->getType());
581    return 0;
582  }
583};
584
585
586//===---------------------------------------===//
587// 'strpbrk' Optimizations
588
589struct StrPBrkOpt : public LibCallOptimization {
590  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
591    FunctionType *FT = Callee->getFunctionType();
592    if (FT->getNumParams() != 2 ||
593        FT->getParamType(0) != B.getInt8PtrTy() ||
594        FT->getParamType(1) != FT->getParamType(0) ||
595        FT->getReturnType() != FT->getParamType(0))
596      return 0;
597
598    StringRef S1, S2;
599    bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
600    bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
601
602    // strpbrk(s, "") -> NULL
603    // strpbrk("", s) -> NULL
604    if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))
605      return Constant::getNullValue(CI->getType());
606
607    // Constant folding.
608    if (HasS1 && HasS2) {
609      size_t I = S1.find_first_of(S2);
610      if (I == std::string::npos) // No match.
611        return Constant::getNullValue(CI->getType());
612
613      return B.CreateGEP(CI->getArgOperand(0), B.getInt64(I), "strpbrk");
614    }
615
616    // strpbrk(s, "a") -> strchr(s, 'a')
617    if (TD && HasS2 && S2.size() == 1)
618      return EmitStrChr(CI->getArgOperand(0), S2[0], B, TD, TLI);
619
620    return 0;
621  }
622};
623
624//===---------------------------------------===//
625// 'strto*' Optimizations.  This handles strtol, strtod, strtof, strtoul, etc.
626
627struct StrToOpt : public LibCallOptimization {
628  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
629    FunctionType *FT = Callee->getFunctionType();
630    if ((FT->getNumParams() != 2 && FT->getNumParams() != 3) ||
631        !FT->getParamType(0)->isPointerTy() ||
632        !FT->getParamType(1)->isPointerTy())
633      return 0;
634
635    Value *EndPtr = CI->getArgOperand(1);
636    if (isa<ConstantPointerNull>(EndPtr)) {
637      // With a null EndPtr, this function won't capture the main argument.
638      // It would be readonly too, except that it still may write to errno.
639      CI->addAttribute(1, Attribute::NoCapture);
640    }
641
642    return 0;
643  }
644};
645
646//===---------------------------------------===//
647// 'strspn' Optimizations
648
649struct StrSpnOpt : public LibCallOptimization {
650  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
651    FunctionType *FT = Callee->getFunctionType();
652    if (FT->getNumParams() != 2 ||
653        FT->getParamType(0) != B.getInt8PtrTy() ||
654        FT->getParamType(1) != FT->getParamType(0) ||
655        !FT->getReturnType()->isIntegerTy())
656      return 0;
657
658    StringRef S1, S2;
659    bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
660    bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
661
662    // strspn(s, "") -> 0
663    // strspn("", s) -> 0
664    if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))
665      return Constant::getNullValue(CI->getType());
666
667    // Constant folding.
668    if (HasS1 && HasS2) {
669      size_t Pos = S1.find_first_not_of(S2);
670      if (Pos == StringRef::npos) Pos = S1.size();
671      return ConstantInt::get(CI->getType(), Pos);
672    }
673
674    return 0;
675  }
676};
677
678//===---------------------------------------===//
679// 'strcspn' Optimizations
680
681struct StrCSpnOpt : public LibCallOptimization {
682  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
683    FunctionType *FT = Callee->getFunctionType();
684    if (FT->getNumParams() != 2 ||
685        FT->getParamType(0) != B.getInt8PtrTy() ||
686        FT->getParamType(1) != FT->getParamType(0) ||
687        !FT->getReturnType()->isIntegerTy())
688      return 0;
689
690    StringRef S1, S2;
691    bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
692    bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
693
694    // strcspn("", s) -> 0
695    if (HasS1 && S1.empty())
696      return Constant::getNullValue(CI->getType());
697
698    // Constant folding.
699    if (HasS1 && HasS2) {
700      size_t Pos = S1.find_first_of(S2);
701      if (Pos == StringRef::npos) Pos = S1.size();
702      return ConstantInt::get(CI->getType(), Pos);
703    }
704
705    // strcspn(s, "") -> strlen(s)
706    if (TD && HasS2 && S2.empty())
707      return EmitStrLen(CI->getArgOperand(0), B, TD, TLI);
708
709    return 0;
710  }
711};
712
713//===---------------------------------------===//
714// 'strstr' Optimizations
715
716struct StrStrOpt : public LibCallOptimization {
717  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
718    FunctionType *FT = Callee->getFunctionType();
719    if (FT->getNumParams() != 2 ||
720        !FT->getParamType(0)->isPointerTy() ||
721        !FT->getParamType(1)->isPointerTy() ||
722        !FT->getReturnType()->isPointerTy())
723      return 0;
724
725    // fold strstr(x, x) -> x.
726    if (CI->getArgOperand(0) == CI->getArgOperand(1))
727      return B.CreateBitCast(CI->getArgOperand(0), CI->getType());
728
729    // fold strstr(a, b) == a -> strncmp(a, b, strlen(b)) == 0
730    if (TD && IsOnlyUsedInEqualityComparison(CI, CI->getArgOperand(0))) {
731      Value *StrLen = EmitStrLen(CI->getArgOperand(1), B, TD, TLI);
732      if (!StrLen)
733        return 0;
734      Value *StrNCmp = EmitStrNCmp(CI->getArgOperand(0), CI->getArgOperand(1),
735                                   StrLen, B, TD, TLI);
736      if (!StrNCmp)
737        return 0;
738      for (Value::use_iterator UI = CI->use_begin(), UE = CI->use_end();
739           UI != UE; ) {
740        ICmpInst *Old = cast<ICmpInst>(*UI++);
741        Value *Cmp = B.CreateICmp(Old->getPredicate(), StrNCmp,
742                                  ConstantInt::getNullValue(StrNCmp->getType()),
743                                  "cmp");
744        Old->replaceAllUsesWith(Cmp);
745        Old->eraseFromParent();
746      }
747      return CI;
748    }
749
750    // See if either input string is a constant string.
751    StringRef SearchStr, ToFindStr;
752    bool HasStr1 = getConstantStringInfo(CI->getArgOperand(0), SearchStr);
753    bool HasStr2 = getConstantStringInfo(CI->getArgOperand(1), ToFindStr);
754
755    // fold strstr(x, "") -> x.
756    if (HasStr2 && ToFindStr.empty())
757      return B.CreateBitCast(CI->getArgOperand(0), CI->getType());
758
759    // If both strings are known, constant fold it.
760    if (HasStr1 && HasStr2) {
761      std::string::size_type Offset = SearchStr.find(ToFindStr);
762
763      if (Offset == StringRef::npos) // strstr("foo", "bar") -> null
764        return Constant::getNullValue(CI->getType());
765
766      // strstr("abcd", "bc") -> gep((char*)"abcd", 1)
767      Value *Result = CastToCStr(CI->getArgOperand(0), B);
768      Result = B.CreateConstInBoundsGEP1_64(Result, Offset, "strstr");
769      return B.CreateBitCast(Result, CI->getType());
770    }
771
772    // fold strstr(x, "y") -> strchr(x, 'y').
773    if (HasStr2 && ToFindStr.size() == 1) {
774      Value *StrChr= EmitStrChr(CI->getArgOperand(0), ToFindStr[0], B, TD, TLI);
775      return StrChr ? B.CreateBitCast(StrChr, CI->getType()) : 0;
776    }
777    return 0;
778  }
779};
780
781
782//===---------------------------------------===//
783// 'memcmp' Optimizations
784
785struct MemCmpOpt : public LibCallOptimization {
786  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
787    FunctionType *FT = Callee->getFunctionType();
788    if (FT->getNumParams() != 3 || !FT->getParamType(0)->isPointerTy() ||
789        !FT->getParamType(1)->isPointerTy() ||
790        !FT->getReturnType()->isIntegerTy(32))
791      return 0;
792
793    Value *LHS = CI->getArgOperand(0), *RHS = CI->getArgOperand(1);
794
795    if (LHS == RHS)  // memcmp(s,s,x) -> 0
796      return Constant::getNullValue(CI->getType());
797
798    // Make sure we have a constant length.
799    ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getArgOperand(2));
800    if (!LenC) return 0;
801    uint64_t Len = LenC->getZExtValue();
802
803    if (Len == 0) // memcmp(s1,s2,0) -> 0
804      return Constant::getNullValue(CI->getType());
805
806    // memcmp(S1,S2,1) -> *(unsigned char*)LHS - *(unsigned char*)RHS
807    if (Len == 1) {
808      Value *LHSV = B.CreateZExt(B.CreateLoad(CastToCStr(LHS, B), "lhsc"),
809                                 CI->getType(), "lhsv");
810      Value *RHSV = B.CreateZExt(B.CreateLoad(CastToCStr(RHS, B), "rhsc"),
811                                 CI->getType(), "rhsv");
812      return B.CreateSub(LHSV, RHSV, "chardiff");
813    }
814
815    // Constant folding: memcmp(x, y, l) -> cnst (all arguments are constant)
816    StringRef LHSStr, RHSStr;
817    if (getConstantStringInfo(LHS, LHSStr) &&
818        getConstantStringInfo(RHS, RHSStr)) {
819      // Make sure we're not reading out-of-bounds memory.
820      if (Len > LHSStr.size() || Len > RHSStr.size())
821        return 0;
822      uint64_t Ret = memcmp(LHSStr.data(), RHSStr.data(), Len);
823      return ConstantInt::get(CI->getType(), Ret);
824    }
825
826    return 0;
827  }
828};
829
830//===---------------------------------------===//
831// 'memcpy' Optimizations
832
833struct MemCpyOpt : public LibCallOptimization {
834  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
835    // These optimizations require TargetData.
836    if (!TD) return 0;
837
838    FunctionType *FT = Callee->getFunctionType();
839    if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
840        !FT->getParamType(0)->isPointerTy() ||
841        !FT->getParamType(1)->isPointerTy() ||
842        FT->getParamType(2) != TD->getIntPtrType(*Context))
843      return 0;
844
845    // memcpy(x, y, n) -> llvm.memcpy(x, y, n, 1)
846    B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
847                   CI->getArgOperand(2), 1);
848    return CI->getArgOperand(0);
849  }
850};
851
852//===---------------------------------------===//
853// 'memmove' Optimizations
854
855struct MemMoveOpt : public LibCallOptimization {
856  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
857    // These optimizations require TargetData.
858    if (!TD) return 0;
859
860    FunctionType *FT = Callee->getFunctionType();
861    if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
862        !FT->getParamType(0)->isPointerTy() ||
863        !FT->getParamType(1)->isPointerTy() ||
864        FT->getParamType(2) != TD->getIntPtrType(*Context))
865      return 0;
866
867    // memmove(x, y, n) -> llvm.memmove(x, y, n, 1)
868    B.CreateMemMove(CI->getArgOperand(0), CI->getArgOperand(1),
869                    CI->getArgOperand(2), 1);
870    return CI->getArgOperand(0);
871  }
872};
873
874//===---------------------------------------===//
875// 'memset' Optimizations
876
877struct MemSetOpt : public LibCallOptimization {
878  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
879    // These optimizations require TargetData.
880    if (!TD) return 0;
881
882    FunctionType *FT = Callee->getFunctionType();
883    if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
884        !FT->getParamType(0)->isPointerTy() ||
885        !FT->getParamType(1)->isIntegerTy() ||
886        FT->getParamType(2) != TD->getIntPtrType(*Context))
887      return 0;
888
889    // memset(p, v, n) -> llvm.memset(p, v, n, 1)
890    Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(), false);
891    B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1);
892    return CI->getArgOperand(0);
893  }
894};
895
896//===----------------------------------------------------------------------===//
897// Math Library Optimizations
898//===----------------------------------------------------------------------===//
899
900//===---------------------------------------===//
901// Double -> Float Shrinking Optimizations for Unary Functions like 'floor'
902
903struct UnaryDoubleFPOpt : public LibCallOptimization {
904  bool CheckRetType;
905  UnaryDoubleFPOpt(bool CheckReturnType): CheckRetType(CheckReturnType) {}
906  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
907    FunctionType *FT = Callee->getFunctionType();
908    if (FT->getNumParams() != 1 || !FT->getReturnType()->isDoubleTy() ||
909        !FT->getParamType(0)->isDoubleTy())
910      return 0;
911
912    if (CheckRetType) {
913      // Check if all the uses for function like 'sin' are converted to float.
914      for (Value::use_iterator UseI = CI->use_begin(); UseI != CI->use_end();
915          ++UseI) {
916        FPTruncInst *Cast = dyn_cast<FPTruncInst>(*UseI);
917        if (Cast == 0 || !Cast->getType()->isFloatTy())
918          return 0;
919      }
920    }
921
922    // If this is something like 'floor((double)floatval)', convert to floorf.
923    FPExtInst *Cast = dyn_cast<FPExtInst>(CI->getArgOperand(0));
924    if (Cast == 0 || !Cast->getOperand(0)->getType()->isFloatTy())
925      return 0;
926
927    // floor((double)floatval) -> (double)floorf(floatval)
928    Value *V = Cast->getOperand(0);
929    V = EmitUnaryFloatFnCall(V, Callee->getName(), B, Callee->getAttributes());
930    return B.CreateFPExt(V, B.getDoubleTy());
931  }
932};
933
934//===---------------------------------------===//
935// 'cos*' Optimizations
936struct CosOpt : public LibCallOptimization {
937  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
938    Value *Ret = NULL;
939    if (UnsafeFPShrink && Callee->getName() == "cos" &&
940        TLI->has(LibFunc::cosf)) {
941      UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
942      Ret = UnsafeUnaryDoubleFP.CallOptimizer(Callee, CI, B);
943    }
944
945    FunctionType *FT = Callee->getFunctionType();
946    // Just make sure this has 1 argument of FP type, which matches the
947    // result type.
948    if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
949        !FT->getParamType(0)->isFloatingPointTy())
950      return Ret;
951
952    // cos(-x) -> cos(x)
953    Value *Op1 = CI->getArgOperand(0);
954    if (BinaryOperator::isFNeg(Op1)) {
955      BinaryOperator *BinExpr = cast<BinaryOperator>(Op1);
956      return B.CreateCall(Callee, BinExpr->getOperand(1), "cos");
957    }
958    return Ret;
959  }
960};
961
962//===---------------------------------------===//
963// 'pow*' Optimizations
964
965struct PowOpt : public LibCallOptimization {
966  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
967    Value *Ret = NULL;
968    if (UnsafeFPShrink && Callee->getName() == "pow" &&
969        TLI->has(LibFunc::powf)) {
970      UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
971      Ret = UnsafeUnaryDoubleFP.CallOptimizer(Callee, CI, B);
972    }
973
974    FunctionType *FT = Callee->getFunctionType();
975    // Just make sure this has 2 arguments of the same FP type, which match the
976    // result type.
977    if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) ||
978        FT->getParamType(0) != FT->getParamType(1) ||
979        !FT->getParamType(0)->isFloatingPointTy())
980      return Ret;
981
982    Value *Op1 = CI->getArgOperand(0), *Op2 = CI->getArgOperand(1);
983    if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) {
984      if (Op1C->isExactlyValue(1.0))  // pow(1.0, x) -> 1.0
985        return Op1C;
986      if (Op1C->isExactlyValue(2.0))  // pow(2.0, x) -> exp2(x)
987        return EmitUnaryFloatFnCall(Op2, "exp2", B, Callee->getAttributes());
988    }
989
990    ConstantFP *Op2C = dyn_cast<ConstantFP>(Op2);
991    if (Op2C == 0) return Ret;
992
993    if (Op2C->getValueAPF().isZero())  // pow(x, 0.0) -> 1.0
994      return ConstantFP::get(CI->getType(), 1.0);
995
996    if (Op2C->isExactlyValue(0.5)) {
997      // Expand pow(x, 0.5) to (x == -infinity ? +infinity : fabs(sqrt(x))).
998      // This is faster than calling pow, and still handles negative zero
999      // and negative infinity correctly.
1000      // TODO: In fast-math mode, this could be just sqrt(x).
1001      // TODO: In finite-only mode, this could be just fabs(sqrt(x)).
1002      Value *Inf = ConstantFP::getInfinity(CI->getType());
1003      Value *NegInf = ConstantFP::getInfinity(CI->getType(), true);
1004      Value *Sqrt = EmitUnaryFloatFnCall(Op1, "sqrt", B,
1005                                         Callee->getAttributes());
1006      Value *FAbs = EmitUnaryFloatFnCall(Sqrt, "fabs", B,
1007                                         Callee->getAttributes());
1008      Value *FCmp = B.CreateFCmpOEQ(Op1, NegInf);
1009      Value *Sel = B.CreateSelect(FCmp, Inf, FAbs);
1010      return Sel;
1011    }
1012
1013    if (Op2C->isExactlyValue(1.0))  // pow(x, 1.0) -> x
1014      return Op1;
1015    if (Op2C->isExactlyValue(2.0))  // pow(x, 2.0) -> x*x
1016      return B.CreateFMul(Op1, Op1, "pow2");
1017    if (Op2C->isExactlyValue(-1.0)) // pow(x, -1.0) -> 1.0/x
1018      return B.CreateFDiv(ConstantFP::get(CI->getType(), 1.0),
1019                          Op1, "powrecip");
1020    return 0;
1021  }
1022};
1023
1024//===---------------------------------------===//
1025// 'exp2' Optimizations
1026
1027struct Exp2Opt : public LibCallOptimization {
1028  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1029    Value *Ret = NULL;
1030    if (UnsafeFPShrink && Callee->getName() == "exp2" &&
1031        TLI->has(LibFunc::exp2)) {
1032      UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
1033      Ret = UnsafeUnaryDoubleFP.CallOptimizer(Callee, CI, B);
1034    }
1035
1036    FunctionType *FT = Callee->getFunctionType();
1037    // Just make sure this has 1 argument of FP type, which matches the
1038    // result type.
1039    if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1040        !FT->getParamType(0)->isFloatingPointTy())
1041      return Ret;
1042
1043    Value *Op = CI->getArgOperand(0);
1044    // Turn exp2(sitofp(x)) -> ldexp(1.0, sext(x))  if sizeof(x) <= 32
1045    // Turn exp2(uitofp(x)) -> ldexp(1.0, zext(x))  if sizeof(x) < 32
1046    Value *LdExpArg = 0;
1047    if (SIToFPInst *OpC = dyn_cast<SIToFPInst>(Op)) {
1048      if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() <= 32)
1049        LdExpArg = B.CreateSExt(OpC->getOperand(0), B.getInt32Ty());
1050    } else if (UIToFPInst *OpC = dyn_cast<UIToFPInst>(Op)) {
1051      if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() < 32)
1052        LdExpArg = B.CreateZExt(OpC->getOperand(0), B.getInt32Ty());
1053    }
1054
1055    if (LdExpArg) {
1056      const char *Name;
1057      if (Op->getType()->isFloatTy())
1058        Name = "ldexpf";
1059      else if (Op->getType()->isDoubleTy())
1060        Name = "ldexp";
1061      else
1062        Name = "ldexpl";
1063
1064      Constant *One = ConstantFP::get(*Context, APFloat(1.0f));
1065      if (!Op->getType()->isFloatTy())
1066        One = ConstantExpr::getFPExtend(One, Op->getType());
1067
1068      Module *M = Caller->getParent();
1069      Value *Callee = M->getOrInsertFunction(Name, Op->getType(),
1070                                             Op->getType(),
1071                                             B.getInt32Ty(), NULL);
1072      CallInst *CI = B.CreateCall2(Callee, One, LdExpArg);
1073      if (const Function *F = dyn_cast<Function>(Callee->stripPointerCasts()))
1074        CI->setCallingConv(F->getCallingConv());
1075
1076      return CI;
1077    }
1078    return Ret;
1079  }
1080};
1081
1082//===----------------------------------------------------------------------===//
1083// Integer Optimizations
1084//===----------------------------------------------------------------------===//
1085
1086//===---------------------------------------===//
1087// 'ffs*' Optimizations
1088
1089struct FFSOpt : public LibCallOptimization {
1090  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1091    FunctionType *FT = Callee->getFunctionType();
1092    // Just make sure this has 2 arguments of the same FP type, which match the
1093    // result type.
1094    if (FT->getNumParams() != 1 ||
1095        !FT->getReturnType()->isIntegerTy(32) ||
1096        !FT->getParamType(0)->isIntegerTy())
1097      return 0;
1098
1099    Value *Op = CI->getArgOperand(0);
1100
1101    // Constant fold.
1102    if (ConstantInt *CI = dyn_cast<ConstantInt>(Op)) {
1103      if (CI->getValue() == 0)  // ffs(0) -> 0.
1104        return Constant::getNullValue(CI->getType());
1105      // ffs(c) -> cttz(c)+1
1106      return B.getInt32(CI->getValue().countTrailingZeros() + 1);
1107    }
1108
1109    // ffs(x) -> x != 0 ? (i32)llvm.cttz(x)+1 : 0
1110    Type *ArgType = Op->getType();
1111    Value *F = Intrinsic::getDeclaration(Callee->getParent(),
1112                                         Intrinsic::cttz, ArgType);
1113    Value *V = B.CreateCall2(F, Op, B.getFalse(), "cttz");
1114    V = B.CreateAdd(V, ConstantInt::get(V->getType(), 1));
1115    V = B.CreateIntCast(V, B.getInt32Ty(), false);
1116
1117    Value *Cond = B.CreateICmpNE(Op, Constant::getNullValue(ArgType));
1118    return B.CreateSelect(Cond, V, B.getInt32(0));
1119  }
1120};
1121
1122//===---------------------------------------===//
1123// 'isdigit' Optimizations
1124
1125struct IsDigitOpt : public LibCallOptimization {
1126  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1127    FunctionType *FT = Callee->getFunctionType();
1128    // We require integer(i32)
1129    if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
1130        !FT->getParamType(0)->isIntegerTy(32))
1131      return 0;
1132
1133    // isdigit(c) -> (c-'0') <u 10
1134    Value *Op = CI->getArgOperand(0);
1135    Op = B.CreateSub(Op, B.getInt32('0'), "isdigittmp");
1136    Op = B.CreateICmpULT(Op, B.getInt32(10), "isdigit");
1137    return B.CreateZExt(Op, CI->getType());
1138  }
1139};
1140
1141//===---------------------------------------===//
1142// 'isascii' Optimizations
1143
1144struct IsAsciiOpt : public LibCallOptimization {
1145  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1146    FunctionType *FT = Callee->getFunctionType();
1147    // We require integer(i32)
1148    if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
1149        !FT->getParamType(0)->isIntegerTy(32))
1150      return 0;
1151
1152    // isascii(c) -> c <u 128
1153    Value *Op = CI->getArgOperand(0);
1154    Op = B.CreateICmpULT(Op, B.getInt32(128), "isascii");
1155    return B.CreateZExt(Op, CI->getType());
1156  }
1157};
1158
1159//===---------------------------------------===//
1160// 'abs', 'labs', 'llabs' Optimizations
1161
1162struct AbsOpt : public LibCallOptimization {
1163  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1164    FunctionType *FT = Callee->getFunctionType();
1165    // We require integer(integer) where the types agree.
1166    if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
1167        FT->getParamType(0) != FT->getReturnType())
1168      return 0;
1169
1170    // abs(x) -> x >s -1 ? x : -x
1171    Value *Op = CI->getArgOperand(0);
1172    Value *Pos = B.CreateICmpSGT(Op, Constant::getAllOnesValue(Op->getType()),
1173                                 "ispos");
1174    Value *Neg = B.CreateNeg(Op, "neg");
1175    return B.CreateSelect(Pos, Op, Neg);
1176  }
1177};
1178
1179
1180//===---------------------------------------===//
1181// 'toascii' Optimizations
1182
1183struct ToAsciiOpt : public LibCallOptimization {
1184  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1185    FunctionType *FT = Callee->getFunctionType();
1186    // We require i32(i32)
1187    if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1188        !FT->getParamType(0)->isIntegerTy(32))
1189      return 0;
1190
1191    // isascii(c) -> c & 0x7f
1192    return B.CreateAnd(CI->getArgOperand(0),
1193                       ConstantInt::get(CI->getType(),0x7F));
1194  }
1195};
1196
1197//===----------------------------------------------------------------------===//
1198// Formatting and IO Optimizations
1199//===----------------------------------------------------------------------===//
1200
1201//===---------------------------------------===//
1202// 'printf' Optimizations
1203
1204struct PrintFOpt : public LibCallOptimization {
1205  Value *OptimizeFixedFormatString(Function *Callee, CallInst *CI,
1206                                   IRBuilder<> &B) {
1207    // Check for a fixed format string.
1208    StringRef FormatStr;
1209    if (!getConstantStringInfo(CI->getArgOperand(0), FormatStr))
1210      return 0;
1211
1212    // Empty format string -> noop.
1213    if (FormatStr.empty())  // Tolerate printf's declared void.
1214      return CI->use_empty() ? (Value*)CI :
1215                               ConstantInt::get(CI->getType(), 0);
1216
1217    // Do not do any of the following transformations if the printf return value
1218    // is used, in general the printf return value is not compatible with either
1219    // putchar() or puts().
1220    if (!CI->use_empty())
1221      return 0;
1222
1223    // printf("x") -> putchar('x'), even for '%'.
1224    if (FormatStr.size() == 1) {
1225      Value *Res = EmitPutChar(B.getInt32(FormatStr[0]), B, TD, TLI);
1226      if (CI->use_empty() || !Res) return Res;
1227      return B.CreateIntCast(Res, CI->getType(), true);
1228    }
1229
1230    // printf("foo\n") --> puts("foo")
1231    if (FormatStr[FormatStr.size()-1] == '\n' &&
1232        FormatStr.find('%') == std::string::npos) {  // no format characters.
1233      // Create a string literal with no \n on it.  We expect the constant merge
1234      // pass to be run after this pass, to merge duplicate strings.
1235      FormatStr = FormatStr.drop_back();
1236      Value *GV = B.CreateGlobalString(FormatStr, "str");
1237      Value *NewCI = EmitPutS(GV, B, TD, TLI);
1238      return (CI->use_empty() || !NewCI) ?
1239              NewCI :
1240              ConstantInt::get(CI->getType(), FormatStr.size()+1);
1241    }
1242
1243    // Optimize specific format strings.
1244    // printf("%c", chr) --> putchar(chr)
1245    if (FormatStr == "%c" && CI->getNumArgOperands() > 1 &&
1246        CI->getArgOperand(1)->getType()->isIntegerTy()) {
1247      Value *Res = EmitPutChar(CI->getArgOperand(1), B, TD, TLI);
1248
1249      if (CI->use_empty() || !Res) return Res;
1250      return B.CreateIntCast(Res, CI->getType(), true);
1251    }
1252
1253    // printf("%s\n", str) --> puts(str)
1254    if (FormatStr == "%s\n" && CI->getNumArgOperands() > 1 &&
1255        CI->getArgOperand(1)->getType()->isPointerTy()) {
1256      return EmitPutS(CI->getArgOperand(1), B, TD, TLI);
1257    }
1258    return 0;
1259  }
1260
1261  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1262    // Require one fixed pointer argument and an integer/void result.
1263    FunctionType *FT = Callee->getFunctionType();
1264    if (FT->getNumParams() < 1 || !FT->getParamType(0)->isPointerTy() ||
1265        !(FT->getReturnType()->isIntegerTy() ||
1266          FT->getReturnType()->isVoidTy()))
1267      return 0;
1268
1269    if (Value *V = OptimizeFixedFormatString(Callee, CI, B)) {
1270      return V;
1271    }
1272
1273    // printf(format, ...) -> iprintf(format, ...) if no floating point
1274    // arguments.
1275    if (TLI->has(LibFunc::iprintf) && !CallHasFloatingPointArgument(CI)) {
1276      Module *M = B.GetInsertBlock()->getParent()->getParent();
1277      Constant *IPrintFFn =
1278        M->getOrInsertFunction("iprintf", FT, Callee->getAttributes());
1279      CallInst *New = cast<CallInst>(CI->clone());
1280      New->setCalledFunction(IPrintFFn);
1281      B.Insert(New);
1282      return New;
1283    }
1284    return 0;
1285  }
1286};
1287
1288//===---------------------------------------===//
1289// 'sprintf' Optimizations
1290
1291struct SPrintFOpt : public LibCallOptimization {
1292  Value *OptimizeFixedFormatString(Function *Callee, CallInst *CI,
1293                                   IRBuilder<> &B) {
1294    // Check for a fixed format string.
1295    StringRef FormatStr;
1296    if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr))
1297      return 0;
1298
1299    // If we just have a format string (nothing else crazy) transform it.
1300    if (CI->getNumArgOperands() == 2) {
1301      // Make sure there's no % in the constant array.  We could try to handle
1302      // %% -> % in the future if we cared.
1303      for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1304        if (FormatStr[i] == '%')
1305          return 0; // we found a format specifier, bail out.
1306
1307      // These optimizations require TargetData.
1308      if (!TD) return 0;
1309
1310      // sprintf(str, fmt) -> llvm.memcpy(str, fmt, strlen(fmt)+1, 1)
1311      B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
1312                     ConstantInt::get(TD->getIntPtrType(*Context), // Copy the
1313                                      FormatStr.size() + 1), 1);   // nul byte.
1314      return ConstantInt::get(CI->getType(), FormatStr.size());
1315    }
1316
1317    // The remaining optimizations require the format string to be "%s" or "%c"
1318    // and have an extra operand.
1319    if (FormatStr.size() != 2 || FormatStr[0] != '%' ||
1320        CI->getNumArgOperands() < 3)
1321      return 0;
1322
1323    // Decode the second character of the format string.
1324    if (FormatStr[1] == 'c') {
1325      // sprintf(dst, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0
1326      if (!CI->getArgOperand(2)->getType()->isIntegerTy()) return 0;
1327      Value *V = B.CreateTrunc(CI->getArgOperand(2), B.getInt8Ty(), "char");
1328      Value *Ptr = CastToCStr(CI->getArgOperand(0), B);
1329      B.CreateStore(V, Ptr);
1330      Ptr = B.CreateGEP(Ptr, B.getInt32(1), "nul");
1331      B.CreateStore(B.getInt8(0), Ptr);
1332
1333      return ConstantInt::get(CI->getType(), 1);
1334    }
1335
1336    if (FormatStr[1] == 's') {
1337      // These optimizations require TargetData.
1338      if (!TD) return 0;
1339
1340      // sprintf(dest, "%s", str) -> llvm.memcpy(dest, str, strlen(str)+1, 1)
1341      if (!CI->getArgOperand(2)->getType()->isPointerTy()) return 0;
1342
1343      Value *Len = EmitStrLen(CI->getArgOperand(2), B, TD, TLI);
1344      if (!Len)
1345        return 0;
1346      Value *IncLen = B.CreateAdd(Len,
1347                                  ConstantInt::get(Len->getType(), 1),
1348                                  "leninc");
1349      B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(2), IncLen, 1);
1350
1351      // The sprintf result is the unincremented number of bytes in the string.
1352      return B.CreateIntCast(Len, CI->getType(), false);
1353    }
1354    return 0;
1355  }
1356
1357  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1358    // Require two fixed pointer arguments and an integer result.
1359    FunctionType *FT = Callee->getFunctionType();
1360    if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
1361        !FT->getParamType(1)->isPointerTy() ||
1362        !FT->getReturnType()->isIntegerTy())
1363      return 0;
1364
1365    if (Value *V = OptimizeFixedFormatString(Callee, CI, B)) {
1366      return V;
1367    }
1368
1369    // sprintf(str, format, ...) -> siprintf(str, format, ...) if no floating
1370    // point arguments.
1371    if (TLI->has(LibFunc::siprintf) && !CallHasFloatingPointArgument(CI)) {
1372      Module *M = B.GetInsertBlock()->getParent()->getParent();
1373      Constant *SIPrintFFn =
1374        M->getOrInsertFunction("siprintf", FT, Callee->getAttributes());
1375      CallInst *New = cast<CallInst>(CI->clone());
1376      New->setCalledFunction(SIPrintFFn);
1377      B.Insert(New);
1378      return New;
1379    }
1380    return 0;
1381  }
1382};
1383
1384//===---------------------------------------===//
1385// 'fwrite' Optimizations
1386
1387struct FWriteOpt : public LibCallOptimization {
1388  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1389    // Require a pointer, an integer, an integer, a pointer, returning integer.
1390    FunctionType *FT = Callee->getFunctionType();
1391    if (FT->getNumParams() != 4 || !FT->getParamType(0)->isPointerTy() ||
1392        !FT->getParamType(1)->isIntegerTy() ||
1393        !FT->getParamType(2)->isIntegerTy() ||
1394        !FT->getParamType(3)->isPointerTy() ||
1395        !FT->getReturnType()->isIntegerTy())
1396      return 0;
1397
1398    // Get the element size and count.
1399    ConstantInt *SizeC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
1400    ConstantInt *CountC = dyn_cast<ConstantInt>(CI->getArgOperand(2));
1401    if (!SizeC || !CountC) return 0;
1402    uint64_t Bytes = SizeC->getZExtValue()*CountC->getZExtValue();
1403
1404    // If this is writing zero records, remove the call (it's a noop).
1405    if (Bytes == 0)
1406      return ConstantInt::get(CI->getType(), 0);
1407
1408    // If this is writing one byte, turn it into fputc.
1409    // This optimisation is only valid, if the return value is unused.
1410    if (Bytes == 1 && CI->use_empty()) {  // fwrite(S,1,1,F) -> fputc(S[0],F)
1411      Value *Char = B.CreateLoad(CastToCStr(CI->getArgOperand(0), B), "char");
1412      Value *NewCI = EmitFPutC(Char, CI->getArgOperand(3), B, TD, TLI);
1413      return NewCI ? ConstantInt::get(CI->getType(), 1) : 0;
1414    }
1415
1416    return 0;
1417  }
1418};
1419
1420//===---------------------------------------===//
1421// 'fputs' Optimizations
1422
1423struct FPutsOpt : public LibCallOptimization {
1424  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1425    // These optimizations require TargetData.
1426    if (!TD) return 0;
1427
1428    // Require two pointers.  Also, we can't optimize if return value is used.
1429    FunctionType *FT = Callee->getFunctionType();
1430    if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
1431        !FT->getParamType(1)->isPointerTy() ||
1432        !CI->use_empty())
1433      return 0;
1434
1435    // fputs(s,F) --> fwrite(s,1,strlen(s),F)
1436    uint64_t Len = GetStringLength(CI->getArgOperand(0));
1437    if (!Len) return 0;
1438    // Known to have no uses (see above).
1439    return EmitFWrite(CI->getArgOperand(0),
1440                      ConstantInt::get(TD->getIntPtrType(*Context), Len-1),
1441                      CI->getArgOperand(1), B, TD, TLI);
1442  }
1443};
1444
1445//===---------------------------------------===//
1446// 'fprintf' Optimizations
1447
1448struct FPrintFOpt : public LibCallOptimization {
1449  Value *OptimizeFixedFormatString(Function *Callee, CallInst *CI,
1450                                   IRBuilder<> &B) {
1451    // All the optimizations depend on the format string.
1452    StringRef FormatStr;
1453    if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr))
1454      return 0;
1455
1456    // fprintf(F, "foo") --> fwrite("foo", 3, 1, F)
1457    if (CI->getNumArgOperands() == 2) {
1458      for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1459        if (FormatStr[i] == '%')  // Could handle %% -> % if we cared.
1460          return 0; // We found a format specifier.
1461
1462      // These optimizations require TargetData.
1463      if (!TD) return 0;
1464
1465      Value *NewCI = EmitFWrite(CI->getArgOperand(1),
1466                                ConstantInt::get(TD->getIntPtrType(*Context),
1467                                                 FormatStr.size()),
1468                                CI->getArgOperand(0), B, TD, TLI);
1469      return NewCI ? ConstantInt::get(CI->getType(), FormatStr.size()) : 0;
1470    }
1471
1472    // The remaining optimizations require the format string to be "%s" or "%c"
1473    // and have an extra operand.
1474    if (FormatStr.size() != 2 || FormatStr[0] != '%' ||
1475        CI->getNumArgOperands() < 3)
1476      return 0;
1477
1478    // Decode the second character of the format string.
1479    if (FormatStr[1] == 'c') {
1480      // fprintf(F, "%c", chr) --> fputc(chr, F)
1481      if (!CI->getArgOperand(2)->getType()->isIntegerTy()) return 0;
1482      Value *NewCI = EmitFPutC(CI->getArgOperand(2), CI->getArgOperand(0), B,
1483                               TD, TLI);
1484      return NewCI ? ConstantInt::get(CI->getType(), 1) : 0;
1485    }
1486
1487    if (FormatStr[1] == 's') {
1488      // fprintf(F, "%s", str) --> fputs(str, F)
1489      if (!CI->getArgOperand(2)->getType()->isPointerTy() || !CI->use_empty())
1490        return 0;
1491      return EmitFPutS(CI->getArgOperand(2), CI->getArgOperand(0), B, TD, TLI);
1492    }
1493    return 0;
1494  }
1495
1496  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1497    // Require two fixed paramters as pointers and integer result.
1498    FunctionType *FT = Callee->getFunctionType();
1499    if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
1500        !FT->getParamType(1)->isPointerTy() ||
1501        !FT->getReturnType()->isIntegerTy())
1502      return 0;
1503
1504    if (Value *V = OptimizeFixedFormatString(Callee, CI, B)) {
1505      return V;
1506    }
1507
1508    // fprintf(stream, format, ...) -> fiprintf(stream, format, ...) if no
1509    // floating point arguments.
1510    if (TLI->has(LibFunc::fiprintf) && !CallHasFloatingPointArgument(CI)) {
1511      Module *M = B.GetInsertBlock()->getParent()->getParent();
1512      Constant *FIPrintFFn =
1513        M->getOrInsertFunction("fiprintf", FT, Callee->getAttributes());
1514      CallInst *New = cast<CallInst>(CI->clone());
1515      New->setCalledFunction(FIPrintFFn);
1516      B.Insert(New);
1517      return New;
1518    }
1519    return 0;
1520  }
1521};
1522
1523//===---------------------------------------===//
1524// 'puts' Optimizations
1525
1526struct PutsOpt : public LibCallOptimization {
1527  virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1528    // Require one fixed pointer argument and an integer/void result.
1529    FunctionType *FT = Callee->getFunctionType();
1530    if (FT->getNumParams() < 1 || !FT->getParamType(0)->isPointerTy() ||
1531        !(FT->getReturnType()->isIntegerTy() ||
1532          FT->getReturnType()->isVoidTy()))
1533      return 0;
1534
1535    // Check for a constant string.
1536    StringRef Str;
1537    if (!getConstantStringInfo(CI->getArgOperand(0), Str))
1538      return 0;
1539
1540    if (Str.empty() && CI->use_empty()) {
1541      // puts("") -> putchar('\n')
1542      Value *Res = EmitPutChar(B.getInt32('\n'), B, TD, TLI);
1543      if (CI->use_empty() || !Res) return Res;
1544      return B.CreateIntCast(Res, CI->getType(), true);
1545    }
1546
1547    return 0;
1548  }
1549};
1550
1551} // end anonymous namespace.
1552
1553//===----------------------------------------------------------------------===//
1554// SimplifyLibCalls Pass Implementation
1555//===----------------------------------------------------------------------===//
1556
1557namespace {
1558  /// This pass optimizes well known library functions from libc and libm.
1559  ///
1560  class SimplifyLibCalls : public FunctionPass {
1561    TargetLibraryInfo *TLI;
1562
1563    StringMap<LibCallOptimization*> Optimizations;
1564    // String and Memory LibCall Optimizations
1565    StrCatOpt StrCat; StrNCatOpt StrNCat; StrChrOpt StrChr; StrRChrOpt StrRChr;
1566    StrCmpOpt StrCmp; StrNCmpOpt StrNCmp;
1567    StrCpyOpt StrCpy; StrCpyOpt StrCpyChk;
1568    StpCpyOpt StpCpy; StpCpyOpt StpCpyChk;
1569    StrNCpyOpt StrNCpy;
1570    StrLenOpt StrLen; StrPBrkOpt StrPBrk;
1571    StrToOpt StrTo; StrSpnOpt StrSpn; StrCSpnOpt StrCSpn; StrStrOpt StrStr;
1572    MemCmpOpt MemCmp; MemCpyOpt MemCpy; MemMoveOpt MemMove; MemSetOpt MemSet;
1573    // Math Library Optimizations
1574    CosOpt Cos; PowOpt Pow; Exp2Opt Exp2;
1575    UnaryDoubleFPOpt UnaryDoubleFP, UnsafeUnaryDoubleFP;
1576    // Integer Optimizations
1577    FFSOpt FFS; AbsOpt Abs; IsDigitOpt IsDigit; IsAsciiOpt IsAscii;
1578    ToAsciiOpt ToAscii;
1579    // Formatting and IO Optimizations
1580    SPrintFOpt SPrintF; PrintFOpt PrintF;
1581    FWriteOpt FWrite; FPutsOpt FPuts; FPrintFOpt FPrintF;
1582    PutsOpt Puts;
1583
1584    bool Modified;  // This is only used by doInitialization.
1585  public:
1586    static char ID; // Pass identification
1587    SimplifyLibCalls() : FunctionPass(ID), StrCpy(false), StrCpyChk(true),
1588                         StpCpy(false), StpCpyChk(true),
1589                         UnaryDoubleFP(false), UnsafeUnaryDoubleFP(true) {
1590      initializeSimplifyLibCallsPass(*PassRegistry::getPassRegistry());
1591    }
1592    void AddOpt(LibFunc::Func F, LibCallOptimization* Opt);
1593    void AddOpt(LibFunc::Func F1, LibFunc::Func F2, LibCallOptimization* Opt);
1594
1595    void InitOptimizations();
1596    bool runOnFunction(Function &F);
1597
1598    void setDoesNotAccessMemory(Function &F);
1599    void setOnlyReadsMemory(Function &F);
1600    void setDoesNotThrow(Function &F);
1601    void setDoesNotCapture(Function &F, unsigned n);
1602    void setDoesNotAlias(Function &F, unsigned n);
1603    bool doInitialization(Module &M);
1604
1605    void inferPrototypeAttributes(Function &F);
1606    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1607      AU.addRequired<TargetLibraryInfo>();
1608    }
1609  };
1610} // end anonymous namespace.
1611
1612char SimplifyLibCalls::ID = 0;
1613
1614INITIALIZE_PASS_BEGIN(SimplifyLibCalls, "simplify-libcalls",
1615                      "Simplify well-known library calls", false, false)
1616INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
1617INITIALIZE_PASS_END(SimplifyLibCalls, "simplify-libcalls",
1618                    "Simplify well-known library calls", false, false)
1619
1620// Public interface to the Simplify LibCalls pass.
1621FunctionPass *llvm::createSimplifyLibCallsPass() {
1622  return new SimplifyLibCalls();
1623}
1624
1625void SimplifyLibCalls::AddOpt(LibFunc::Func F, LibCallOptimization* Opt) {
1626  if (TLI->has(F))
1627    Optimizations[TLI->getName(F)] = Opt;
1628}
1629
1630void SimplifyLibCalls::AddOpt(LibFunc::Func F1, LibFunc::Func F2,
1631                              LibCallOptimization* Opt) {
1632  if (TLI->has(F1) && TLI->has(F2))
1633    Optimizations[TLI->getName(F1)] = Opt;
1634}
1635
1636/// Optimizations - Populate the Optimizations map with all the optimizations
1637/// we know.
1638void SimplifyLibCalls::InitOptimizations() {
1639  // String and Memory LibCall Optimizations
1640  Optimizations["strcat"] = &StrCat;
1641  Optimizations["strncat"] = &StrNCat;
1642  Optimizations["strchr"] = &StrChr;
1643  Optimizations["strrchr"] = &StrRChr;
1644  Optimizations["strcmp"] = &StrCmp;
1645  Optimizations["strncmp"] = &StrNCmp;
1646  Optimizations["strcpy"] = &StrCpy;
1647  Optimizations["strncpy"] = &StrNCpy;
1648  Optimizations["stpcpy"] = &StpCpy;
1649  Optimizations["strlen"] = &StrLen;
1650  Optimizations["strpbrk"] = &StrPBrk;
1651  Optimizations["strtol"] = &StrTo;
1652  Optimizations["strtod"] = &StrTo;
1653  Optimizations["strtof"] = &StrTo;
1654  Optimizations["strtoul"] = &StrTo;
1655  Optimizations["strtoll"] = &StrTo;
1656  Optimizations["strtold"] = &StrTo;
1657  Optimizations["strtoull"] = &StrTo;
1658  Optimizations["strspn"] = &StrSpn;
1659  Optimizations["strcspn"] = &StrCSpn;
1660  Optimizations["strstr"] = &StrStr;
1661  Optimizations["memcmp"] = &MemCmp;
1662  AddOpt(LibFunc::memcpy, &MemCpy);
1663  Optimizations["memmove"] = &MemMove;
1664  AddOpt(LibFunc::memset, &MemSet);
1665
1666  // _chk variants of String and Memory LibCall Optimizations.
1667  Optimizations["__strcpy_chk"] = &StrCpyChk;
1668  Optimizations["__stpcpy_chk"] = &StpCpyChk;
1669
1670  // Math Library Optimizations
1671  Optimizations["cosf"] = &Cos;
1672  Optimizations["cos"] = &Cos;
1673  Optimizations["cosl"] = &Cos;
1674  Optimizations["powf"] = &Pow;
1675  Optimizations["pow"] = &Pow;
1676  Optimizations["powl"] = &Pow;
1677  Optimizations["llvm.pow.f32"] = &Pow;
1678  Optimizations["llvm.pow.f64"] = &Pow;
1679  Optimizations["llvm.pow.f80"] = &Pow;
1680  Optimizations["llvm.pow.f128"] = &Pow;
1681  Optimizations["llvm.pow.ppcf128"] = &Pow;
1682  Optimizations["exp2l"] = &Exp2;
1683  Optimizations["exp2"] = &Exp2;
1684  Optimizations["exp2f"] = &Exp2;
1685  Optimizations["llvm.exp2.ppcf128"] = &Exp2;
1686  Optimizations["llvm.exp2.f128"] = &Exp2;
1687  Optimizations["llvm.exp2.f80"] = &Exp2;
1688  Optimizations["llvm.exp2.f64"] = &Exp2;
1689  Optimizations["llvm.exp2.f32"] = &Exp2;
1690
1691  AddOpt(LibFunc::ceil, LibFunc::ceilf, &UnaryDoubleFP);
1692  AddOpt(LibFunc::fabs, LibFunc::fabsf, &UnaryDoubleFP);
1693  AddOpt(LibFunc::floor, LibFunc::floorf, &UnaryDoubleFP);
1694  AddOpt(LibFunc::rint, LibFunc::rintf, &UnaryDoubleFP);
1695  AddOpt(LibFunc::round, LibFunc::roundf, &UnaryDoubleFP);
1696  AddOpt(LibFunc::nearbyint, LibFunc::nearbyintf, &UnaryDoubleFP);
1697  AddOpt(LibFunc::trunc, LibFunc::truncf, &UnaryDoubleFP);
1698
1699  if(UnsafeFPShrink) {
1700    AddOpt(LibFunc::acos, LibFunc::acosf, &UnsafeUnaryDoubleFP);
1701    AddOpt(LibFunc::acosh, LibFunc::acoshf, &UnsafeUnaryDoubleFP);
1702    AddOpt(LibFunc::asin, LibFunc::asinf, &UnsafeUnaryDoubleFP);
1703    AddOpt(LibFunc::asinh, LibFunc::asinhf, &UnsafeUnaryDoubleFP);
1704    AddOpt(LibFunc::atan, LibFunc::atanf, &UnsafeUnaryDoubleFP);
1705    AddOpt(LibFunc::atanh, LibFunc::atanhf, &UnsafeUnaryDoubleFP);
1706    AddOpt(LibFunc::cbrt, LibFunc::cbrtf, &UnsafeUnaryDoubleFP);
1707    AddOpt(LibFunc::cosh, LibFunc::coshf, &UnsafeUnaryDoubleFP);
1708    AddOpt(LibFunc::exp, LibFunc::expf, &UnsafeUnaryDoubleFP);
1709    AddOpt(LibFunc::exp10, LibFunc::exp10f, &UnsafeUnaryDoubleFP);
1710    AddOpt(LibFunc::expm1, LibFunc::expm1f, &UnsafeUnaryDoubleFP);
1711    AddOpt(LibFunc::log, LibFunc::logf, &UnsafeUnaryDoubleFP);
1712    AddOpt(LibFunc::log10, LibFunc::log10f, &UnsafeUnaryDoubleFP);
1713    AddOpt(LibFunc::log1p, LibFunc::log1pf, &UnsafeUnaryDoubleFP);
1714    AddOpt(LibFunc::log2, LibFunc::log2f, &UnsafeUnaryDoubleFP);
1715    AddOpt(LibFunc::logb, LibFunc::logbf, &UnsafeUnaryDoubleFP);
1716    AddOpt(LibFunc::sin, LibFunc::sinf, &UnsafeUnaryDoubleFP);
1717    AddOpt(LibFunc::sinh, LibFunc::sinhf, &UnsafeUnaryDoubleFP);
1718    AddOpt(LibFunc::sqrt, LibFunc::sqrtf, &UnsafeUnaryDoubleFP);
1719    AddOpt(LibFunc::tan, LibFunc::tanf, &UnsafeUnaryDoubleFP);
1720    AddOpt(LibFunc::tanh, LibFunc::tanhf, &UnsafeUnaryDoubleFP);
1721  }
1722
1723  // Integer Optimizations
1724  Optimizations["ffs"] = &FFS;
1725  Optimizations["ffsl"] = &FFS;
1726  Optimizations["ffsll"] = &FFS;
1727  Optimizations["abs"] = &Abs;
1728  Optimizations["labs"] = &Abs;
1729  Optimizations["llabs"] = &Abs;
1730  Optimizations["isdigit"] = &IsDigit;
1731  Optimizations["isascii"] = &IsAscii;
1732  Optimizations["toascii"] = &ToAscii;
1733
1734  // Formatting and IO Optimizations
1735  Optimizations["sprintf"] = &SPrintF;
1736  Optimizations["printf"] = &PrintF;
1737  AddOpt(LibFunc::fwrite, &FWrite);
1738  AddOpt(LibFunc::fputs, &FPuts);
1739  Optimizations["fprintf"] = &FPrintF;
1740  Optimizations["puts"] = &Puts;
1741}
1742
1743
1744/// runOnFunction - Top level algorithm.
1745///
1746bool SimplifyLibCalls::runOnFunction(Function &F) {
1747  TLI = &getAnalysis<TargetLibraryInfo>();
1748
1749  if (Optimizations.empty())
1750    InitOptimizations();
1751
1752  const TargetData *TD = getAnalysisIfAvailable<TargetData>();
1753
1754  IRBuilder<> Builder(F.getContext());
1755
1756  bool Changed = false;
1757  for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
1758    for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
1759      // Ignore non-calls.
1760      CallInst *CI = dyn_cast<CallInst>(I++);
1761      if (!CI) continue;
1762
1763      // Ignore indirect calls and calls to non-external functions.
1764      Function *Callee = CI->getCalledFunction();
1765      if (Callee == 0 || !Callee->isDeclaration() ||
1766          !(Callee->hasExternalLinkage() || Callee->hasDLLImportLinkage()))
1767        continue;
1768
1769      // Ignore unknown calls.
1770      LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
1771      if (!LCO) continue;
1772
1773      // Set the builder to the instruction after the call.
1774      Builder.SetInsertPoint(BB, I);
1775
1776      // Use debug location of CI for all new instructions.
1777      Builder.SetCurrentDebugLocation(CI->getDebugLoc());
1778
1779      // Try to optimize this call.
1780      Value *Result = LCO->OptimizeCall(CI, TD, TLI, Builder);
1781      if (Result == 0) continue;
1782
1783      DEBUG(dbgs() << "SimplifyLibCalls simplified: " << *CI;
1784            dbgs() << "  into: " << *Result << "\n");
1785
1786      // Something changed!
1787      Changed = true;
1788      ++NumSimplified;
1789
1790      // Inspect the instruction after the call (which was potentially just
1791      // added) next.
1792      I = CI; ++I;
1793
1794      if (CI != Result && !CI->use_empty()) {
1795        CI->replaceAllUsesWith(Result);
1796        if (!Result->hasName())
1797          Result->takeName(CI);
1798      }
1799      CI->eraseFromParent();
1800    }
1801  }
1802  return Changed;
1803}
1804
1805// Utility methods for doInitialization.
1806
1807void SimplifyLibCalls::setDoesNotAccessMemory(Function &F) {
1808  if (!F.doesNotAccessMemory()) {
1809    F.setDoesNotAccessMemory();
1810    ++NumAnnotated;
1811    Modified = true;
1812  }
1813}
1814void SimplifyLibCalls::setOnlyReadsMemory(Function &F) {
1815  if (!F.onlyReadsMemory()) {
1816    F.setOnlyReadsMemory();
1817    ++NumAnnotated;
1818    Modified = true;
1819  }
1820}
1821void SimplifyLibCalls::setDoesNotThrow(Function &F) {
1822  if (!F.doesNotThrow()) {
1823    F.setDoesNotThrow();
1824    ++NumAnnotated;
1825    Modified = true;
1826  }
1827}
1828void SimplifyLibCalls::setDoesNotCapture(Function &F, unsigned n) {
1829  if (!F.doesNotCapture(n)) {
1830    F.setDoesNotCapture(n);
1831    ++NumAnnotated;
1832    Modified = true;
1833  }
1834}
1835void SimplifyLibCalls::setDoesNotAlias(Function &F, unsigned n) {
1836  if (!F.doesNotAlias(n)) {
1837    F.setDoesNotAlias(n);
1838    ++NumAnnotated;
1839    Modified = true;
1840  }
1841}
1842
1843
1844void SimplifyLibCalls::inferPrototypeAttributes(Function &F) {
1845  FunctionType *FTy = F.getFunctionType();
1846
1847  StringRef Name = F.getName();
1848  switch (Name[0]) {
1849  case 's':
1850    if (Name == "strlen") {
1851      if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1852        return;
1853      setOnlyReadsMemory(F);
1854      setDoesNotThrow(F);
1855      setDoesNotCapture(F, 1);
1856    } else if (Name == "strchr" ||
1857               Name == "strrchr") {
1858      if (FTy->getNumParams() != 2 ||
1859          !FTy->getParamType(0)->isPointerTy() ||
1860          !FTy->getParamType(1)->isIntegerTy())
1861        return;
1862      setOnlyReadsMemory(F);
1863      setDoesNotThrow(F);
1864    } else if (Name == "strcpy" ||
1865               Name == "stpcpy" ||
1866               Name == "strcat" ||
1867               Name == "strtol" ||
1868               Name == "strtod" ||
1869               Name == "strtof" ||
1870               Name == "strtoul" ||
1871               Name == "strtoll" ||
1872               Name == "strtold" ||
1873               Name == "strncat" ||
1874               Name == "strncpy" ||
1875               Name == "stpncpy" ||
1876               Name == "strtoull") {
1877      if (FTy->getNumParams() < 2 ||
1878          !FTy->getParamType(1)->isPointerTy())
1879        return;
1880      setDoesNotThrow(F);
1881      setDoesNotCapture(F, 2);
1882    } else if (Name == "strxfrm") {
1883      if (FTy->getNumParams() != 3 ||
1884          !FTy->getParamType(0)->isPointerTy() ||
1885          !FTy->getParamType(1)->isPointerTy())
1886        return;
1887      setDoesNotThrow(F);
1888      setDoesNotCapture(F, 1);
1889      setDoesNotCapture(F, 2);
1890    } else if (Name == "strcmp" ||
1891               Name == "strspn" ||
1892               Name == "strncmp" ||
1893               Name == "strcspn" ||
1894               Name == "strcoll" ||
1895               Name == "strcasecmp" ||
1896               Name == "strncasecmp") {
1897      if (FTy->getNumParams() < 2 ||
1898          !FTy->getParamType(0)->isPointerTy() ||
1899          !FTy->getParamType(1)->isPointerTy())
1900        return;
1901      setOnlyReadsMemory(F);
1902      setDoesNotThrow(F);
1903      setDoesNotCapture(F, 1);
1904      setDoesNotCapture(F, 2);
1905    } else if (Name == "strstr" ||
1906               Name == "strpbrk") {
1907      if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1908        return;
1909      setOnlyReadsMemory(F);
1910      setDoesNotThrow(F);
1911      setDoesNotCapture(F, 2);
1912    } else if (Name == "strtok" ||
1913               Name == "strtok_r") {
1914      if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
1915        return;
1916      setDoesNotThrow(F);
1917      setDoesNotCapture(F, 2);
1918    } else if (Name == "scanf" ||
1919               Name == "setbuf" ||
1920               Name == "setvbuf") {
1921      if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
1922        return;
1923      setDoesNotThrow(F);
1924      setDoesNotCapture(F, 1);
1925    } else if (Name == "strdup" ||
1926               Name == "strndup") {
1927      if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() ||
1928          !FTy->getParamType(0)->isPointerTy())
1929        return;
1930      setDoesNotThrow(F);
1931      setDoesNotAlias(F, 0);
1932      setDoesNotCapture(F, 1);
1933    } else if (Name == "stat" ||
1934               Name == "sscanf" ||
1935               Name == "sprintf" ||
1936               Name == "statvfs") {
1937      if (FTy->getNumParams() < 2 ||
1938          !FTy->getParamType(0)->isPointerTy() ||
1939          !FTy->getParamType(1)->isPointerTy())
1940        return;
1941      setDoesNotThrow(F);
1942      setDoesNotCapture(F, 1);
1943      setDoesNotCapture(F, 2);
1944    } else if (Name == "snprintf") {
1945      if (FTy->getNumParams() != 3 ||
1946          !FTy->getParamType(0)->isPointerTy() ||
1947          !FTy->getParamType(2)->isPointerTy())
1948        return;
1949      setDoesNotThrow(F);
1950      setDoesNotCapture(F, 1);
1951      setDoesNotCapture(F, 3);
1952    } else if (Name == "setitimer") {
1953      if (FTy->getNumParams() != 3 ||
1954          !FTy->getParamType(1)->isPointerTy() ||
1955          !FTy->getParamType(2)->isPointerTy())
1956        return;
1957      setDoesNotThrow(F);
1958      setDoesNotCapture(F, 2);
1959      setDoesNotCapture(F, 3);
1960    } else if (Name == "system") {
1961      if (FTy->getNumParams() != 1 ||
1962          !FTy->getParamType(0)->isPointerTy())
1963        return;
1964      // May throw; "system" is a valid pthread cancellation point.
1965      setDoesNotCapture(F, 1);
1966    }
1967    break;
1968  case 'm':
1969    if (Name == "malloc") {
1970      if (FTy->getNumParams() != 1 ||
1971          !FTy->getReturnType()->isPointerTy())
1972        return;
1973      setDoesNotThrow(F);
1974      setDoesNotAlias(F, 0);
1975    } else if (Name == "memcmp") {
1976      if (FTy->getNumParams() != 3 ||
1977          !FTy->getParamType(0)->isPointerTy() ||
1978          !FTy->getParamType(1)->isPointerTy())
1979        return;
1980      setOnlyReadsMemory(F);
1981      setDoesNotThrow(F);
1982      setDoesNotCapture(F, 1);
1983      setDoesNotCapture(F, 2);
1984    } else if (Name == "memchr" ||
1985               Name == "memrchr") {
1986      if (FTy->getNumParams() != 3)
1987        return;
1988      setOnlyReadsMemory(F);
1989      setDoesNotThrow(F);
1990    } else if (Name == "modf" ||
1991               Name == "modff" ||
1992               Name == "modfl" ||
1993               Name == "memcpy" ||
1994               Name == "memccpy" ||
1995               Name == "memmove") {
1996      if (FTy->getNumParams() < 2 ||
1997          !FTy->getParamType(1)->isPointerTy())
1998        return;
1999      setDoesNotThrow(F);
2000      setDoesNotCapture(F, 2);
2001    } else if (Name == "memalign") {
2002      if (!FTy->getReturnType()->isPointerTy())
2003        return;
2004      setDoesNotAlias(F, 0);
2005    } else if (Name == "mkdir" ||
2006               Name == "mktime") {
2007      if (FTy->getNumParams() == 0 ||
2008          !FTy->getParamType(0)->isPointerTy())
2009        return;
2010      setDoesNotThrow(F);
2011      setDoesNotCapture(F, 1);
2012    }
2013    break;
2014  case 'r':
2015    if (Name == "realloc") {
2016      if (FTy->getNumParams() != 2 ||
2017          !FTy->getParamType(0)->isPointerTy() ||
2018          !FTy->getReturnType()->isPointerTy())
2019        return;
2020      setDoesNotThrow(F);
2021      setDoesNotAlias(F, 0);
2022      setDoesNotCapture(F, 1);
2023    } else if (Name == "read") {
2024      if (FTy->getNumParams() != 3 ||
2025          !FTy->getParamType(1)->isPointerTy())
2026        return;
2027      // May throw; "read" is a valid pthread cancellation point.
2028      setDoesNotCapture(F, 2);
2029    } else if (Name == "rmdir" ||
2030               Name == "rewind" ||
2031               Name == "remove" ||
2032               Name == "realpath") {
2033      if (FTy->getNumParams() < 1 ||
2034          !FTy->getParamType(0)->isPointerTy())
2035        return;
2036      setDoesNotThrow(F);
2037      setDoesNotCapture(F, 1);
2038    } else if (Name == "rename" ||
2039               Name == "readlink") {
2040      if (FTy->getNumParams() < 2 ||
2041          !FTy->getParamType(0)->isPointerTy() ||
2042          !FTy->getParamType(1)->isPointerTy())
2043        return;
2044      setDoesNotThrow(F);
2045      setDoesNotCapture(F, 1);
2046      setDoesNotCapture(F, 2);
2047    }
2048    break;
2049  case 'w':
2050    if (Name == "write") {
2051      if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
2052        return;
2053      // May throw; "write" is a valid pthread cancellation point.
2054      setDoesNotCapture(F, 2);
2055    }
2056    break;
2057  case 'b':
2058    if (Name == "bcopy") {
2059      if (FTy->getNumParams() != 3 ||
2060          !FTy->getParamType(0)->isPointerTy() ||
2061          !FTy->getParamType(1)->isPointerTy())
2062        return;
2063      setDoesNotThrow(F);
2064      setDoesNotCapture(F, 1);
2065      setDoesNotCapture(F, 2);
2066    } else if (Name == "bcmp") {
2067      if (FTy->getNumParams() != 3 ||
2068          !FTy->getParamType(0)->isPointerTy() ||
2069          !FTy->getParamType(1)->isPointerTy())
2070        return;
2071      setDoesNotThrow(F);
2072      setOnlyReadsMemory(F);
2073      setDoesNotCapture(F, 1);
2074      setDoesNotCapture(F, 2);
2075    } else if (Name == "bzero") {
2076      if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
2077        return;
2078      setDoesNotThrow(F);
2079      setDoesNotCapture(F, 1);
2080    }
2081    break;
2082  case 'c':
2083    if (Name == "calloc") {
2084      if (FTy->getNumParams() != 2 ||
2085          !FTy->getReturnType()->isPointerTy())
2086        return;
2087      setDoesNotThrow(F);
2088      setDoesNotAlias(F, 0);
2089    } else if (Name == "chmod" ||
2090               Name == "chown" ||
2091               Name == "ctermid" ||
2092               Name == "clearerr" ||
2093               Name == "closedir") {
2094      if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
2095        return;
2096      setDoesNotThrow(F);
2097      setDoesNotCapture(F, 1);
2098    }
2099    break;
2100  case 'a':
2101    if (Name == "atoi" ||
2102        Name == "atol" ||
2103        Name == "atof" ||
2104        Name == "atoll") {
2105      if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
2106        return;
2107      setDoesNotThrow(F);
2108      setOnlyReadsMemory(F);
2109      setDoesNotCapture(F, 1);
2110    } else if (Name == "access") {
2111      if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
2112        return;
2113      setDoesNotThrow(F);
2114      setDoesNotCapture(F, 1);
2115    }
2116    break;
2117  case 'f':
2118    if (Name == "fopen") {
2119      if (FTy->getNumParams() != 2 ||
2120          !FTy->getReturnType()->isPointerTy() ||
2121          !FTy->getParamType(0)->isPointerTy() ||
2122          !FTy->getParamType(1)->isPointerTy())
2123        return;
2124      setDoesNotThrow(F);
2125      setDoesNotAlias(F, 0);
2126      setDoesNotCapture(F, 1);
2127      setDoesNotCapture(F, 2);
2128    } else if (Name == "fdopen") {
2129      if (FTy->getNumParams() != 2 ||
2130          !FTy->getReturnType()->isPointerTy() ||
2131          !FTy->getParamType(1)->isPointerTy())
2132        return;
2133      setDoesNotThrow(F);
2134      setDoesNotAlias(F, 0);
2135      setDoesNotCapture(F, 2);
2136    } else if (Name == "feof" ||
2137               Name == "free" ||
2138               Name == "fseek" ||
2139               Name == "ftell" ||
2140               Name == "fgetc" ||
2141               Name == "fseeko" ||
2142               Name == "ftello" ||
2143               Name == "fileno" ||
2144               Name == "fflush" ||
2145               Name == "fclose" ||
2146               Name == "fsetpos" ||
2147               Name == "flockfile" ||
2148               Name == "funlockfile" ||
2149               Name == "ftrylockfile") {
2150      if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
2151        return;
2152      setDoesNotThrow(F);
2153      setDoesNotCapture(F, 1);
2154    } else if (Name == "ferror") {
2155      if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
2156        return;
2157      setDoesNotThrow(F);
2158      setDoesNotCapture(F, 1);
2159      setOnlyReadsMemory(F);
2160    } else if (Name == "fputc" ||
2161               Name == "fstat" ||
2162               Name == "frexp" ||
2163               Name == "frexpf" ||
2164               Name == "frexpl" ||
2165               Name == "fstatvfs") {
2166      if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
2167        return;
2168      setDoesNotThrow(F);
2169      setDoesNotCapture(F, 2);
2170    } else if (Name == "fgets") {
2171      if (FTy->getNumParams() != 3 ||
2172          !FTy->getParamType(0)->isPointerTy() ||
2173          !FTy->getParamType(2)->isPointerTy())
2174        return;
2175      setDoesNotThrow(F);
2176      setDoesNotCapture(F, 3);
2177    } else if (Name == "fread" ||
2178               Name == "fwrite") {
2179      if (FTy->getNumParams() != 4 ||
2180          !FTy->getParamType(0)->isPointerTy() ||
2181          !FTy->getParamType(3)->isPointerTy())
2182        return;
2183      setDoesNotThrow(F);
2184      setDoesNotCapture(F, 1);
2185      setDoesNotCapture(F, 4);
2186    } else if (Name == "fputs" ||
2187               Name == "fscanf" ||
2188               Name == "fprintf" ||
2189               Name == "fgetpos") {
2190      if (FTy->getNumParams() < 2 ||
2191          !FTy->getParamType(0)->isPointerTy() ||
2192          !FTy->getParamType(1)->isPointerTy())
2193        return;
2194      setDoesNotThrow(F);
2195      setDoesNotCapture(F, 1);
2196      setDoesNotCapture(F, 2);
2197    }
2198    break;
2199  case 'g':
2200    if (Name == "getc" ||
2201        Name == "getlogin_r" ||
2202        Name == "getc_unlocked") {
2203      if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
2204        return;
2205      setDoesNotThrow(F);
2206      setDoesNotCapture(F, 1);
2207    } else if (Name == "getenv") {
2208      if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
2209        return;
2210      setDoesNotThrow(F);
2211      setOnlyReadsMemory(F);
2212      setDoesNotCapture(F, 1);
2213    } else if (Name == "gets" ||
2214               Name == "getchar") {
2215      setDoesNotThrow(F);
2216    } else if (Name == "getitimer") {
2217      if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
2218        return;
2219      setDoesNotThrow(F);
2220      setDoesNotCapture(F, 2);
2221    } else if (Name == "getpwnam") {
2222      if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
2223        return;
2224      setDoesNotThrow(F);
2225      setDoesNotCapture(F, 1);
2226    }
2227    break;
2228  case 'u':
2229    if (Name == "ungetc") {
2230      if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
2231        return;
2232      setDoesNotThrow(F);
2233      setDoesNotCapture(F, 2);
2234    } else if (Name == "uname" ||
2235               Name == "unlink" ||
2236               Name == "unsetenv") {
2237      if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
2238        return;
2239      setDoesNotThrow(F);
2240      setDoesNotCapture(F, 1);
2241    } else if (Name == "utime" ||
2242               Name == "utimes") {
2243      if (FTy->getNumParams() != 2 ||
2244          !FTy->getParamType(0)->isPointerTy() ||
2245          !FTy->getParamType(1)->isPointerTy())
2246        return;
2247      setDoesNotThrow(F);
2248      setDoesNotCapture(F, 1);
2249      setDoesNotCapture(F, 2);
2250    }
2251    break;
2252  case 'p':
2253    if (Name == "putc") {
2254      if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
2255        return;
2256      setDoesNotThrow(F);
2257      setDoesNotCapture(F, 2);
2258    } else if (Name == "puts" ||
2259               Name == "printf" ||
2260               Name == "perror") {
2261      if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
2262        return;
2263      setDoesNotThrow(F);
2264      setDoesNotCapture(F, 1);
2265    } else if (Name == "pread" ||
2266               Name == "pwrite") {
2267      if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
2268        return;
2269      // May throw; these are valid pthread cancellation points.
2270      setDoesNotCapture(F, 2);
2271    } else if (Name == "putchar") {
2272      setDoesNotThrow(F);
2273    } else if (Name == "popen") {
2274      if (FTy->getNumParams() != 2 ||
2275          !FTy->getReturnType()->isPointerTy() ||
2276          !FTy->getParamType(0)->isPointerTy() ||
2277          !FTy->getParamType(1)->isPointerTy())
2278        return;
2279      setDoesNotThrow(F);
2280      setDoesNotAlias(F, 0);
2281      setDoesNotCapture(F, 1);
2282      setDoesNotCapture(F, 2);
2283    } else if (Name == "pclose") {
2284      if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
2285        return;
2286      setDoesNotThrow(F);
2287      setDoesNotCapture(F, 1);
2288    }
2289    break;
2290  case 'v':
2291    if (Name == "vscanf") {
2292      if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
2293        return;
2294      setDoesNotThrow(F);
2295      setDoesNotCapture(F, 1);
2296    } else if (Name == "vsscanf" ||
2297               Name == "vfscanf") {
2298      if (FTy->getNumParams() != 3 ||
2299          !FTy->getParamType(1)->isPointerTy() ||
2300          !FTy->getParamType(2)->isPointerTy())
2301        return;
2302      setDoesNotThrow(F);
2303      setDoesNotCapture(F, 1);
2304      setDoesNotCapture(F, 2);
2305    } else if (Name == "valloc") {
2306      if (!FTy->getReturnType()->isPointerTy())
2307        return;
2308      setDoesNotThrow(F);
2309      setDoesNotAlias(F, 0);
2310    } else if (Name == "vprintf") {
2311      if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
2312        return;
2313      setDoesNotThrow(F);
2314      setDoesNotCapture(F, 1);
2315    } else if (Name == "vfprintf" ||
2316               Name == "vsprintf") {
2317      if (FTy->getNumParams() != 3 ||
2318          !FTy->getParamType(0)->isPointerTy() ||
2319          !FTy->getParamType(1)->isPointerTy())
2320        return;
2321      setDoesNotThrow(F);
2322      setDoesNotCapture(F, 1);
2323      setDoesNotCapture(F, 2);
2324    } else if (Name == "vsnprintf") {
2325      if (FTy->getNumParams() != 4 ||
2326          !FTy->getParamType(0)->isPointerTy() ||
2327          !FTy->getParamType(2)->isPointerTy())
2328        return;
2329      setDoesNotThrow(F);
2330      setDoesNotCapture(F, 1);
2331      setDoesNotCapture(F, 3);
2332    }
2333    break;
2334  case 'o':
2335    if (Name == "open") {
2336      if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
2337        return;
2338      // May throw; "open" is a valid pthread cancellation point.
2339      setDoesNotCapture(F, 1);
2340    } else if (Name == "opendir") {
2341      if (FTy->getNumParams() != 1 ||
2342          !FTy->getReturnType()->isPointerTy() ||
2343          !FTy->getParamType(0)->isPointerTy())
2344        return;
2345      setDoesNotThrow(F);
2346      setDoesNotAlias(F, 0);
2347      setDoesNotCapture(F, 1);
2348    }
2349    break;
2350  case 't':
2351    if (Name == "tmpfile") {
2352      if (!FTy->getReturnType()->isPointerTy())
2353        return;
2354      setDoesNotThrow(F);
2355      setDoesNotAlias(F, 0);
2356    } else if (Name == "times") {
2357      if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
2358        return;
2359      setDoesNotThrow(F);
2360      setDoesNotCapture(F, 1);
2361    }
2362    break;
2363  case 'h':
2364    if (Name == "htonl" ||
2365        Name == "htons") {
2366      setDoesNotThrow(F);
2367      setDoesNotAccessMemory(F);
2368    }
2369    break;
2370  case 'n':
2371    if (Name == "ntohl" ||
2372        Name == "ntohs") {
2373      setDoesNotThrow(F);
2374      setDoesNotAccessMemory(F);
2375    }
2376    break;
2377  case 'l':
2378    if (Name == "lstat") {
2379      if (FTy->getNumParams() != 2 ||
2380          !FTy->getParamType(0)->isPointerTy() ||
2381          !FTy->getParamType(1)->isPointerTy())
2382        return;
2383      setDoesNotThrow(F);
2384      setDoesNotCapture(F, 1);
2385      setDoesNotCapture(F, 2);
2386    } else if (Name == "lchown") {
2387      if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy())
2388        return;
2389      setDoesNotThrow(F);
2390      setDoesNotCapture(F, 1);
2391    }
2392    break;
2393  case 'q':
2394    if (Name == "qsort") {
2395      if (FTy->getNumParams() != 4 || !FTy->getParamType(3)->isPointerTy())
2396        return;
2397      // May throw; places call through function pointer.
2398      setDoesNotCapture(F, 4);
2399    }
2400    break;
2401  case '_':
2402    if (Name == "__strdup" ||
2403        Name == "__strndup") {
2404      if (FTy->getNumParams() < 1 ||
2405          !FTy->getReturnType()->isPointerTy() ||
2406          !FTy->getParamType(0)->isPointerTy())
2407        return;
2408      setDoesNotThrow(F);
2409      setDoesNotAlias(F, 0);
2410      setDoesNotCapture(F, 1);
2411    } else if (Name == "__strtok_r") {
2412      if (FTy->getNumParams() != 3 ||
2413          !FTy->getParamType(1)->isPointerTy())
2414        return;
2415      setDoesNotThrow(F);
2416      setDoesNotCapture(F, 2);
2417    } else if (Name == "_IO_getc") {
2418      if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
2419        return;
2420      setDoesNotThrow(F);
2421      setDoesNotCapture(F, 1);
2422    } else if (Name == "_IO_putc") {
2423      if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
2424        return;
2425      setDoesNotThrow(F);
2426      setDoesNotCapture(F, 2);
2427    }
2428    break;
2429  case 1:
2430    if (Name == "\1__isoc99_scanf") {
2431      if (FTy->getNumParams() < 1 ||
2432          !FTy->getParamType(0)->isPointerTy())
2433        return;
2434      setDoesNotThrow(F);
2435      setDoesNotCapture(F, 1);
2436    } else if (Name == "\1stat64" ||
2437               Name == "\1lstat64" ||
2438               Name == "\1statvfs64" ||
2439               Name == "\1__isoc99_sscanf") {
2440      if (FTy->getNumParams() < 1 ||
2441          !FTy->getParamType(0)->isPointerTy() ||
2442          !FTy->getParamType(1)->isPointerTy())
2443        return;
2444      setDoesNotThrow(F);
2445      setDoesNotCapture(F, 1);
2446      setDoesNotCapture(F, 2);
2447    } else if (Name == "\1fopen64") {
2448      if (FTy->getNumParams() != 2 ||
2449          !FTy->getReturnType()->isPointerTy() ||
2450          !FTy->getParamType(0)->isPointerTy() ||
2451          !FTy->getParamType(1)->isPointerTy())
2452        return;
2453      setDoesNotThrow(F);
2454      setDoesNotAlias(F, 0);
2455      setDoesNotCapture(F, 1);
2456      setDoesNotCapture(F, 2);
2457    } else if (Name == "\1fseeko64" ||
2458               Name == "\1ftello64") {
2459      if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
2460        return;
2461      setDoesNotThrow(F);
2462      setDoesNotCapture(F, 1);
2463    } else if (Name == "\1tmpfile64") {
2464      if (!FTy->getReturnType()->isPointerTy())
2465        return;
2466      setDoesNotThrow(F);
2467      setDoesNotAlias(F, 0);
2468    } else if (Name == "\1fstat64" ||
2469               Name == "\1fstatvfs64") {
2470      if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
2471        return;
2472      setDoesNotThrow(F);
2473      setDoesNotCapture(F, 2);
2474    } else if (Name == "\1open64") {
2475      if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
2476        return;
2477      // May throw; "open" is a valid pthread cancellation point.
2478      setDoesNotCapture(F, 1);
2479    }
2480    break;
2481  }
2482}
2483
2484/// doInitialization - Add attributes to well-known functions.
2485///
2486bool SimplifyLibCalls::doInitialization(Module &M) {
2487  Modified = false;
2488  for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
2489    Function &F = *I;
2490    if (F.isDeclaration() && F.hasName())
2491      inferPrototypeAttributes(F);
2492  }
2493  return Modified;
2494}
2495
2496// TODO:
2497//   Additional cases that we need to add to this file:
2498//
2499// cbrt:
2500//   * cbrt(expN(X))  -> expN(x/3)
2501//   * cbrt(sqrt(x))  -> pow(x,1/6)
2502//   * cbrt(sqrt(x))  -> pow(x,1/9)
2503//
2504// exp, expf, expl:
2505//   * exp(log(x))  -> x
2506//
2507// log, logf, logl:
2508//   * log(exp(x))   -> x
2509//   * log(x**y)     -> y*log(x)
2510//   * log(exp(y))   -> y*log(e)
2511//   * log(exp2(y))  -> y*log(2)
2512//   * log(exp10(y)) -> y*log(10)
2513//   * log(sqrt(x))  -> 0.5*log(x)
2514//   * log(pow(x,y)) -> y*log(x)
2515//
2516// lround, lroundf, lroundl:
2517//   * lround(cnst) -> cnst'
2518//
2519// pow, powf, powl:
2520//   * pow(exp(x),y)  -> exp(x*y)
2521//   * pow(sqrt(x),y) -> pow(x,y*0.5)
2522//   * pow(pow(x,y),z)-> pow(x,y*z)
2523//
2524// round, roundf, roundl:
2525//   * round(cnst) -> cnst'
2526//
2527// signbit:
2528//   * signbit(cnst) -> cnst'
2529//   * signbit(nncst) -> 0 (if pstv is a non-negative constant)
2530//
2531// sqrt, sqrtf, sqrtl:
2532//   * sqrt(expN(x))  -> expN(x*0.5)
2533//   * sqrt(Nroot(x)) -> pow(x,1/(2*N))
2534//   * sqrt(pow(x,y)) -> pow(|x|,y*0.5)
2535//
2536// strchr:
2537//   * strchr(p, 0) -> strlen(p)
2538// tan, tanf, tanl:
2539//   * tan(atan(x)) -> x
2540//
2541// trunc, truncf, truncl:
2542//   * trunc(cnst) -> cnst'
2543//
2544//
2545