Change memcpy/memset/memmove to have dest and source alignments.
[oota-llvm.git] / lib / Transforms / Utils / SimplifyLibCalls.cpp
1 //===------ SimplifyLibCalls.cpp - Library calls simplifier ---------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This is a utility pass used for testing the InstructionSimplify analysis.
11 // The analysis is applied to every instruction, and if it simplifies then the
12 // instruction is replaced by the simplification.  If you are looking for a pass
13 // that performs serious instruction folding, use the instcombine pass instead.
14 //
15 //===----------------------------------------------------------------------===//
16
17 #include "llvm/Transforms/Utils/SimplifyLibCalls.h"
18 #include "llvm/ADT/SmallString.h"
19 #include "llvm/ADT/StringMap.h"
20 #include "llvm/ADT/Triple.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/IR/DataLayout.h"
23 #include "llvm/IR/DiagnosticInfo.h"
24 #include "llvm/IR/Function.h"
25 #include "llvm/IR/IRBuilder.h"
26 #include "llvm/IR/IntrinsicInst.h"
27 #include "llvm/IR/Intrinsics.h"
28 #include "llvm/IR/LLVMContext.h"
29 #include "llvm/IR/Module.h"
30 #include "llvm/IR/PatternMatch.h"
31 #include "llvm/Support/Allocator.h"
32 #include "llvm/Support/CommandLine.h"
33 #include "llvm/Analysis/TargetLibraryInfo.h"
34 #include "llvm/Transforms/Utils/BuildLibCalls.h"
35 #include "llvm/Transforms/Utils/Local.h"
36
37 using namespace llvm;
38 using namespace PatternMatch;
39
40 static cl::opt<bool>
41     ColdErrorCalls("error-reporting-is-cold", cl::init(true), cl::Hidden,
42                    cl::desc("Treat error-reporting calls as cold"));
43
44 static cl::opt<bool>
45     EnableUnsafeFPShrink("enable-double-float-shrink", cl::Hidden,
46                          cl::init(false),
47                          cl::desc("Enable unsafe double to float "
48                                   "shrinking for math lib calls"));
49
50
51 //===----------------------------------------------------------------------===//
52 // Helper Functions
53 //===----------------------------------------------------------------------===//
54
55 static bool ignoreCallingConv(LibFunc::Func Func) {
56   return Func == LibFunc::abs || Func == LibFunc::labs ||
57          Func == LibFunc::llabs || Func == LibFunc::strlen;
58 }
59
60 /// isOnlyUsedInZeroEqualityComparison - Return true if it only matters that the
61 /// value is equal or not-equal to zero.
62 static bool isOnlyUsedInZeroEqualityComparison(Value *V) {
63   for (User *U : V->users()) {
64     if (ICmpInst *IC = dyn_cast<ICmpInst>(U))
65       if (IC->isEquality())
66         if (Constant *C = dyn_cast<Constant>(IC->getOperand(1)))
67           if (C->isNullValue())
68             continue;
69     // Unknown instruction.
70     return false;
71   }
72   return true;
73 }
74
75 /// isOnlyUsedInEqualityComparison - Return true if it is only used in equality
76 /// comparisons with With.
77 static bool isOnlyUsedInEqualityComparison(Value *V, Value *With) {
78   for (User *U : V->users()) {
79     if (ICmpInst *IC = dyn_cast<ICmpInst>(U))
80       if (IC->isEquality() && IC->getOperand(1) == With)
81         continue;
82     // Unknown instruction.
83     return false;
84   }
85   return true;
86 }
87
88 static bool callHasFloatingPointArgument(const CallInst *CI) {
89   for (CallInst::const_op_iterator it = CI->op_begin(), e = CI->op_end();
90        it != e; ++it) {
91     if ((*it)->getType()->isFloatingPointTy())
92       return true;
93   }
94   return false;
95 }
96
97 /// \brief Check whether the overloaded unary floating point function
98 /// corresponding to \a Ty is available.
99 static bool hasUnaryFloatFn(const TargetLibraryInfo *TLI, Type *Ty,
100                             LibFunc::Func DoubleFn, LibFunc::Func FloatFn,
101                             LibFunc::Func LongDoubleFn) {
102   switch (Ty->getTypeID()) {
103   case Type::FloatTyID:
104     return TLI->has(FloatFn);
105   case Type::DoubleTyID:
106     return TLI->has(DoubleFn);
107   default:
108     return TLI->has(LongDoubleFn);
109   }
110 }
111
112 /// \brief Check whether we can use unsafe floating point math for
113 /// the function passed as input.
114 static bool canUseUnsafeFPMath(Function *F) {
115
116   // FIXME: For finer-grain optimization, we need intrinsics to have the same
117   // fast-math flag decorations that are applied to FP instructions. For now,
118   // we have to rely on the function-level unsafe-fp-math attribute to do this
119   // optimization because there's no other way to express that the call can be
120   // relaxed.
121   if (F->hasFnAttribute("unsafe-fp-math")) {
122     Attribute Attr = F->getFnAttribute("unsafe-fp-math");
123     if (Attr.getValueAsString() == "true")
124       return true;
125   }
126   return false;
127 }
128
129 /// \brief Returns whether \p F matches the signature expected for the
130 /// string/memory copying library function \p Func.
131 /// Acceptable functions are st[rp][n]?cpy, memove, memcpy, and memset.
132 /// Their fortified (_chk) counterparts are also accepted.
133 static bool checkStringCopyLibFuncSignature(Function *F, LibFunc::Func Func) {
134   const DataLayout &DL = F->getParent()->getDataLayout();
135   FunctionType *FT = F->getFunctionType();
136   LLVMContext &Context = F->getContext();
137   Type *PCharTy = Type::getInt8PtrTy(Context);
138   Type *SizeTTy = DL.getIntPtrType(Context);
139   unsigned NumParams = FT->getNumParams();
140
141   // All string libfuncs return the same type as the first parameter.
142   if (FT->getReturnType() != FT->getParamType(0))
143     return false;
144
145   switch (Func) {
146   default:
147     llvm_unreachable("Can't check signature for non-string-copy libfunc.");
148   case LibFunc::stpncpy_chk:
149   case LibFunc::strncpy_chk:
150     --NumParams; // fallthrough
151   case LibFunc::stpncpy:
152   case LibFunc::strncpy: {
153     if (NumParams != 3 || FT->getParamType(0) != FT->getParamType(1) ||
154         FT->getParamType(0) != PCharTy || !FT->getParamType(2)->isIntegerTy())
155       return false;
156     break;
157   }
158   case LibFunc::strcpy_chk:
159   case LibFunc::stpcpy_chk:
160     --NumParams; // fallthrough
161   case LibFunc::stpcpy:
162   case LibFunc::strcpy: {
163     if (NumParams != 2 || FT->getParamType(0) != FT->getParamType(1) ||
164         FT->getParamType(0) != PCharTy)
165       return false;
166     break;
167   }
168   case LibFunc::memmove_chk:
169   case LibFunc::memcpy_chk:
170     --NumParams; // fallthrough
171   case LibFunc::memmove:
172   case LibFunc::memcpy: {
173     if (NumParams != 3 || !FT->getParamType(0)->isPointerTy() ||
174         !FT->getParamType(1)->isPointerTy() || FT->getParamType(2) != SizeTTy)
175       return false;
176     break;
177   }
178   case LibFunc::memset_chk:
179     --NumParams; // fallthrough
180   case LibFunc::memset: {
181     if (NumParams != 3 || !FT->getParamType(0)->isPointerTy() ||
182         !FT->getParamType(1)->isIntegerTy() || FT->getParamType(2) != SizeTTy)
183       return false;
184     break;
185   }
186   }
187   // If this is a fortified libcall, the last parameter is a size_t.
188   if (NumParams == FT->getNumParams() - 1)
189     return FT->getParamType(FT->getNumParams() - 1) == SizeTTy;
190   return true;
191 }
192
193 //===----------------------------------------------------------------------===//
194 // String and Memory Library Call Optimizations
195 //===----------------------------------------------------------------------===//
196
197 Value *LibCallSimplifier::optimizeStrCat(CallInst *CI, IRBuilder<> &B) {
198   Function *Callee = CI->getCalledFunction();
199   // Verify the "strcat" function prototype.
200   FunctionType *FT = Callee->getFunctionType();
201   if (FT->getNumParams() != 2||
202       FT->getReturnType() != B.getInt8PtrTy() ||
203       FT->getParamType(0) != FT->getReturnType() ||
204       FT->getParamType(1) != FT->getReturnType())
205     return nullptr;
206
207   // Extract some information from the instruction
208   Value *Dst = CI->getArgOperand(0);
209   Value *Src = CI->getArgOperand(1);
210
211   // See if we can get the length of the input string.
212   uint64_t Len = GetStringLength(Src);
213   if (Len == 0)
214     return nullptr;
215   --Len; // Unbias length.
216
217   // Handle the simple, do-nothing case: strcat(x, "") -> x
218   if (Len == 0)
219     return Dst;
220
221   return emitStrLenMemCpy(Src, Dst, Len, B);
222 }
223
224 Value *LibCallSimplifier::emitStrLenMemCpy(Value *Src, Value *Dst, uint64_t Len,
225                                            IRBuilder<> &B) {
226   // We need to find the end of the destination string.  That's where the
227   // memory is to be moved to. We just generate a call to strlen.
228   Value *DstLen = EmitStrLen(Dst, B, DL, TLI);
229   if (!DstLen)
230     return nullptr;
231
232   // Now that we have the destination's length, we must index into the
233   // destination's pointer to get the actual memcpy destination (end of
234   // the string .. we're concatenating).
235   Value *CpyDst = B.CreateGEP(B.getInt8Ty(), Dst, DstLen, "endptr");
236
237   // We have enough information to now generate the memcpy call to do the
238   // concatenation for us.  Make a memcpy to copy the nul byte with align = 1.
239   B.CreateMemCpy(CpyDst, Src,
240                  ConstantInt::get(DL.getIntPtrType(Src->getContext()), Len + 1),
241                  1, 1);
242   return Dst;
243 }
244
245 Value *LibCallSimplifier::optimizeStrNCat(CallInst *CI, IRBuilder<> &B) {
246   Function *Callee = CI->getCalledFunction();
247   // Verify the "strncat" function prototype.
248   FunctionType *FT = Callee->getFunctionType();
249   if (FT->getNumParams() != 3 || FT->getReturnType() != B.getInt8PtrTy() ||
250       FT->getParamType(0) != FT->getReturnType() ||
251       FT->getParamType(1) != FT->getReturnType() ||
252       !FT->getParamType(2)->isIntegerTy())
253     return nullptr;
254
255   // Extract some information from the instruction
256   Value *Dst = CI->getArgOperand(0);
257   Value *Src = CI->getArgOperand(1);
258   uint64_t Len;
259
260   // We don't do anything if length is not constant
261   if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
262     Len = LengthArg->getZExtValue();
263   else
264     return nullptr;
265
266   // See if we can get the length of the input string.
267   uint64_t SrcLen = GetStringLength(Src);
268   if (SrcLen == 0)
269     return nullptr;
270   --SrcLen; // Unbias length.
271
272   // Handle the simple, do-nothing cases:
273   // strncat(x, "", c) -> x
274   // strncat(x,  c, 0) -> x
275   if (SrcLen == 0 || Len == 0)
276     return Dst;
277
278   // We don't optimize this case
279   if (Len < SrcLen)
280     return nullptr;
281
282   // strncat(x, s, c) -> strcat(x, s)
283   // s is constant so the strcat can be optimized further
284   return emitStrLenMemCpy(Src, Dst, SrcLen, B);
285 }
286
287 Value *LibCallSimplifier::optimizeStrChr(CallInst *CI, IRBuilder<> &B) {
288   Function *Callee = CI->getCalledFunction();
289   // Verify the "strchr" function prototype.
290   FunctionType *FT = Callee->getFunctionType();
291   if (FT->getNumParams() != 2 || FT->getReturnType() != B.getInt8PtrTy() ||
292       FT->getParamType(0) != FT->getReturnType() ||
293       !FT->getParamType(1)->isIntegerTy(32))
294     return nullptr;
295
296   Value *SrcStr = CI->getArgOperand(0);
297
298   // If the second operand is non-constant, see if we can compute the length
299   // of the input string and turn this into memchr.
300   ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
301   if (!CharC) {
302     uint64_t Len = GetStringLength(SrcStr);
303     if (Len == 0 || !FT->getParamType(1)->isIntegerTy(32)) // memchr needs i32.
304       return nullptr;
305
306     return EmitMemChr(SrcStr, CI->getArgOperand(1), // include nul.
307                       ConstantInt::get(DL.getIntPtrType(CI->getContext()), Len),
308                       B, DL, TLI);
309   }
310
311   // Otherwise, the character is a constant, see if the first argument is
312   // a string literal.  If so, we can constant fold.
313   StringRef Str;
314   if (!getConstantStringInfo(SrcStr, Str)) {
315     if (CharC->isZero()) // strchr(p, 0) -> p + strlen(p)
316       return B.CreateGEP(B.getInt8Ty(), SrcStr, EmitStrLen(SrcStr, B, DL, TLI), "strchr");
317     return nullptr;
318   }
319
320   // Compute the offset, make sure to handle the case when we're searching for
321   // zero (a weird way to spell strlen).
322   size_t I = (0xFF & CharC->getSExtValue()) == 0
323                  ? Str.size()
324                  : Str.find(CharC->getSExtValue());
325   if (I == StringRef::npos) // Didn't find the char.  strchr returns null.
326     return Constant::getNullValue(CI->getType());
327
328   // strchr(s+n,c)  -> gep(s+n+i,c)
329   return B.CreateGEP(B.getInt8Ty(), SrcStr, B.getInt64(I), "strchr");
330 }
331
332 Value *LibCallSimplifier::optimizeStrRChr(CallInst *CI, IRBuilder<> &B) {
333   Function *Callee = CI->getCalledFunction();
334   // Verify the "strrchr" function prototype.
335   FunctionType *FT = Callee->getFunctionType();
336   if (FT->getNumParams() != 2 || FT->getReturnType() != B.getInt8PtrTy() ||
337       FT->getParamType(0) != FT->getReturnType() ||
338       !FT->getParamType(1)->isIntegerTy(32))
339     return nullptr;
340
341   Value *SrcStr = CI->getArgOperand(0);
342   ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
343
344   // Cannot fold anything if we're not looking for a constant.
345   if (!CharC)
346     return nullptr;
347
348   StringRef Str;
349   if (!getConstantStringInfo(SrcStr, Str)) {
350     // strrchr(s, 0) -> strchr(s, 0)
351     if (CharC->isZero())
352       return EmitStrChr(SrcStr, '\0', B, TLI);
353     return nullptr;
354   }
355
356   // Compute the offset.
357   size_t I = (0xFF & CharC->getSExtValue()) == 0
358                  ? Str.size()
359                  : Str.rfind(CharC->getSExtValue());
360   if (I == StringRef::npos) // Didn't find the char. Return null.
361     return Constant::getNullValue(CI->getType());
362
363   // strrchr(s+n,c) -> gep(s+n+i,c)
364   return B.CreateGEP(B.getInt8Ty(), SrcStr, B.getInt64(I), "strrchr");
365 }
366
367 Value *LibCallSimplifier::optimizeStrCmp(CallInst *CI, IRBuilder<> &B) {
368   Function *Callee = CI->getCalledFunction();
369   // Verify the "strcmp" function prototype.
370   FunctionType *FT = Callee->getFunctionType();
371   if (FT->getNumParams() != 2 || !FT->getReturnType()->isIntegerTy(32) ||
372       FT->getParamType(0) != FT->getParamType(1) ||
373       FT->getParamType(0) != B.getInt8PtrTy())
374     return nullptr;
375
376   Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
377   if (Str1P == Str2P) // strcmp(x,x)  -> 0
378     return ConstantInt::get(CI->getType(), 0);
379
380   StringRef Str1, Str2;
381   bool HasStr1 = getConstantStringInfo(Str1P, Str1);
382   bool HasStr2 = getConstantStringInfo(Str2P, Str2);
383
384   // strcmp(x, y)  -> cnst  (if both x and y are constant strings)
385   if (HasStr1 && HasStr2)
386     return ConstantInt::get(CI->getType(), Str1.compare(Str2));
387
388   if (HasStr1 && Str1.empty()) // strcmp("", x) -> -*x
389     return B.CreateNeg(
390         B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"), CI->getType()));
391
392   if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x
393     return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
394
395   // strcmp(P, "x") -> memcmp(P, "x", 2)
396   uint64_t Len1 = GetStringLength(Str1P);
397   uint64_t Len2 = GetStringLength(Str2P);
398   if (Len1 && Len2) {
399     return EmitMemCmp(Str1P, Str2P,
400                       ConstantInt::get(DL.getIntPtrType(CI->getContext()),
401                                        std::min(Len1, Len2)),
402                       B, DL, TLI);
403   }
404
405   return nullptr;
406 }
407
408 Value *LibCallSimplifier::optimizeStrNCmp(CallInst *CI, IRBuilder<> &B) {
409   Function *Callee = CI->getCalledFunction();
410   // Verify the "strncmp" function prototype.
411   FunctionType *FT = Callee->getFunctionType();
412   if (FT->getNumParams() != 3 || !FT->getReturnType()->isIntegerTy(32) ||
413       FT->getParamType(0) != FT->getParamType(1) ||
414       FT->getParamType(0) != B.getInt8PtrTy() ||
415       !FT->getParamType(2)->isIntegerTy())
416     return nullptr;
417
418   Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
419   if (Str1P == Str2P) // strncmp(x,x,n)  -> 0
420     return ConstantInt::get(CI->getType(), 0);
421
422   // Get the length argument if it is constant.
423   uint64_t Length;
424   if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
425     Length = LengthArg->getZExtValue();
426   else
427     return nullptr;
428
429   if (Length == 0) // strncmp(x,y,0)   -> 0
430     return ConstantInt::get(CI->getType(), 0);
431
432   if (Length == 1) // strncmp(x,y,1) -> memcmp(x,y,1)
433     return EmitMemCmp(Str1P, Str2P, CI->getArgOperand(2), B, DL, TLI);
434
435   StringRef Str1, Str2;
436   bool HasStr1 = getConstantStringInfo(Str1P, Str1);
437   bool HasStr2 = getConstantStringInfo(Str2P, Str2);
438
439   // strncmp(x, y)  -> cnst  (if both x and y are constant strings)
440   if (HasStr1 && HasStr2) {
441     StringRef SubStr1 = Str1.substr(0, Length);
442     StringRef SubStr2 = Str2.substr(0, Length);
443     return ConstantInt::get(CI->getType(), SubStr1.compare(SubStr2));
444   }
445
446   if (HasStr1 && Str1.empty()) // strncmp("", x, n) -> -*x
447     return B.CreateNeg(
448         B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"), CI->getType()));
449
450   if (HasStr2 && Str2.empty()) // strncmp(x, "", n) -> *x
451     return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
452
453   return nullptr;
454 }
455
456 Value *LibCallSimplifier::optimizeStrCpy(CallInst *CI, IRBuilder<> &B) {
457   Function *Callee = CI->getCalledFunction();
458
459   if (!checkStringCopyLibFuncSignature(Callee, LibFunc::strcpy))
460     return nullptr;
461
462   Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
463   if (Dst == Src) // strcpy(x,x)  -> x
464     return Src;
465
466   // See if we can get the length of the input string.
467   uint64_t Len = GetStringLength(Src);
468   if (Len == 0)
469     return nullptr;
470
471   // We have enough information to now generate the memcpy call to do the
472   // copy for us.  Make a memcpy to copy the nul byte with align = 1.
473   B.CreateMemCpy(Dst, Src,
474                  ConstantInt::get(DL.getIntPtrType(CI->getContext()), Len), 1,
475                  1);
476   return Dst;
477 }
478
479 Value *LibCallSimplifier::optimizeStpCpy(CallInst *CI, IRBuilder<> &B) {
480   Function *Callee = CI->getCalledFunction();
481   if (!checkStringCopyLibFuncSignature(Callee, LibFunc::stpcpy))
482     return nullptr;
483
484   Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
485   if (Dst == Src) { // stpcpy(x,x)  -> x+strlen(x)
486     Value *StrLen = EmitStrLen(Src, B, DL, TLI);
487     return StrLen ? B.CreateInBoundsGEP(B.getInt8Ty(), Dst, StrLen) : nullptr;
488   }
489
490   // See if we can get the length of the input string.
491   uint64_t Len = GetStringLength(Src);
492   if (Len == 0)
493     return nullptr;
494
495   Type *PT = Callee->getFunctionType()->getParamType(0);
496   Value *LenV = ConstantInt::get(DL.getIntPtrType(PT), Len);
497   Value *DstEnd =
498       B.CreateGEP(B.getInt8Ty(), Dst, ConstantInt::get(DL.getIntPtrType(PT), Len - 1));
499
500   // We have enough information to now generate the memcpy call to do the
501   // copy for us.  Make a memcpy to copy the nul byte with align = 1.
502   B.CreateMemCpy(Dst, Src, LenV, 1, 1);
503   return DstEnd;
504 }
505
506 Value *LibCallSimplifier::optimizeStrNCpy(CallInst *CI, IRBuilder<> &B) {
507   Function *Callee = CI->getCalledFunction();
508   if (!checkStringCopyLibFuncSignature(Callee, LibFunc::strncpy))
509     return nullptr;
510
511   Value *Dst = CI->getArgOperand(0);
512   Value *Src = CI->getArgOperand(1);
513   Value *LenOp = CI->getArgOperand(2);
514
515   // See if we can get the length of the input string.
516   uint64_t SrcLen = GetStringLength(Src);
517   if (SrcLen == 0)
518     return nullptr;
519   --SrcLen;
520
521   if (SrcLen == 0) {
522     // strncpy(x, "", y) -> memset(x, '\0', y, 1)
523     B.CreateMemSet(Dst, B.getInt8('\0'), LenOp, 1);
524     return Dst;
525   }
526
527   uint64_t Len;
528   if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(LenOp))
529     Len = LengthArg->getZExtValue();
530   else
531     return nullptr;
532
533   if (Len == 0)
534     return Dst; // strncpy(x, y, 0) -> x
535
536   // Let strncpy handle the zero padding
537   if (Len > SrcLen + 1)
538     return nullptr;
539
540   Type *PT = Callee->getFunctionType()->getParamType(0);
541   // strncpy(x, s, c) -> memcpy(x, s, c, 1) [s and c are constant]
542   B.CreateMemCpy(Dst, Src, ConstantInt::get(DL.getIntPtrType(PT), Len), 1, 1);
543
544   return Dst;
545 }
546
547 Value *LibCallSimplifier::optimizeStrLen(CallInst *CI, IRBuilder<> &B) {
548   Function *Callee = CI->getCalledFunction();
549   FunctionType *FT = Callee->getFunctionType();
550   if (FT->getNumParams() != 1 || FT->getParamType(0) != B.getInt8PtrTy() ||
551       !FT->getReturnType()->isIntegerTy())
552     return nullptr;
553
554   Value *Src = CI->getArgOperand(0);
555
556   // Constant folding: strlen("xyz") -> 3
557   if (uint64_t Len = GetStringLength(Src))
558     return ConstantInt::get(CI->getType(), Len - 1);
559
560   // strlen(x?"foo":"bars") --> x ? 3 : 4
561   if (SelectInst *SI = dyn_cast<SelectInst>(Src)) {
562     uint64_t LenTrue = GetStringLength(SI->getTrueValue());
563     uint64_t LenFalse = GetStringLength(SI->getFalseValue());
564     if (LenTrue && LenFalse) {
565       Function *Caller = CI->getParent()->getParent();
566       emitOptimizationRemark(CI->getContext(), "simplify-libcalls", *Caller,
567                              SI->getDebugLoc(),
568                              "folded strlen(select) to select of constants");
569       return B.CreateSelect(SI->getCondition(),
570                             ConstantInt::get(CI->getType(), LenTrue - 1),
571                             ConstantInt::get(CI->getType(), LenFalse - 1));
572     }
573   }
574
575   // strlen(x) != 0 --> *x != 0
576   // strlen(x) == 0 --> *x == 0
577   if (isOnlyUsedInZeroEqualityComparison(CI))
578     return B.CreateZExt(B.CreateLoad(Src, "strlenfirst"), CI->getType());
579
580   return nullptr;
581 }
582
583 Value *LibCallSimplifier::optimizeStrPBrk(CallInst *CI, IRBuilder<> &B) {
584   Function *Callee = CI->getCalledFunction();
585   FunctionType *FT = Callee->getFunctionType();
586   if (FT->getNumParams() != 2 || FT->getParamType(0) != B.getInt8PtrTy() ||
587       FT->getParamType(1) != FT->getParamType(0) ||
588       FT->getReturnType() != FT->getParamType(0))
589     return nullptr;
590
591   StringRef S1, S2;
592   bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
593   bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
594
595   // strpbrk(s, "") -> nullptr
596   // strpbrk("", s) -> nullptr
597   if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))
598     return Constant::getNullValue(CI->getType());
599
600   // Constant folding.
601   if (HasS1 && HasS2) {
602     size_t I = S1.find_first_of(S2);
603     if (I == StringRef::npos) // No match.
604       return Constant::getNullValue(CI->getType());
605
606     return B.CreateGEP(B.getInt8Ty(), CI->getArgOperand(0), B.getInt64(I), "strpbrk");
607   }
608
609   // strpbrk(s, "a") -> strchr(s, 'a')
610   if (HasS2 && S2.size() == 1)
611     return EmitStrChr(CI->getArgOperand(0), S2[0], B, TLI);
612
613   return nullptr;
614 }
615
616 Value *LibCallSimplifier::optimizeStrTo(CallInst *CI, IRBuilder<> &B) {
617   Function *Callee = CI->getCalledFunction();
618   FunctionType *FT = Callee->getFunctionType();
619   if ((FT->getNumParams() != 2 && FT->getNumParams() != 3) ||
620       !FT->getParamType(0)->isPointerTy() ||
621       !FT->getParamType(1)->isPointerTy())
622     return nullptr;
623
624   Value *EndPtr = CI->getArgOperand(1);
625   if (isa<ConstantPointerNull>(EndPtr)) {
626     // With a null EndPtr, this function won't capture the main argument.
627     // It would be readonly too, except that it still may write to errno.
628     CI->addAttribute(1, Attribute::NoCapture);
629   }
630
631   return nullptr;
632 }
633
634 Value *LibCallSimplifier::optimizeStrSpn(CallInst *CI, IRBuilder<> &B) {
635   Function *Callee = CI->getCalledFunction();
636   FunctionType *FT = Callee->getFunctionType();
637   if (FT->getNumParams() != 2 || FT->getParamType(0) != B.getInt8PtrTy() ||
638       FT->getParamType(1) != FT->getParamType(0) ||
639       !FT->getReturnType()->isIntegerTy())
640     return nullptr;
641
642   StringRef S1, S2;
643   bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
644   bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
645
646   // strspn(s, "") -> 0
647   // strspn("", s) -> 0
648   if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))
649     return Constant::getNullValue(CI->getType());
650
651   // Constant folding.
652   if (HasS1 && HasS2) {
653     size_t Pos = S1.find_first_not_of(S2);
654     if (Pos == StringRef::npos)
655       Pos = S1.size();
656     return ConstantInt::get(CI->getType(), Pos);
657   }
658
659   return nullptr;
660 }
661
662 Value *LibCallSimplifier::optimizeStrCSpn(CallInst *CI, IRBuilder<> &B) {
663   Function *Callee = CI->getCalledFunction();
664   FunctionType *FT = Callee->getFunctionType();
665   if (FT->getNumParams() != 2 || FT->getParamType(0) != B.getInt8PtrTy() ||
666       FT->getParamType(1) != FT->getParamType(0) ||
667       !FT->getReturnType()->isIntegerTy())
668     return nullptr;
669
670   StringRef S1, S2;
671   bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
672   bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
673
674   // strcspn("", s) -> 0
675   if (HasS1 && S1.empty())
676     return Constant::getNullValue(CI->getType());
677
678   // Constant folding.
679   if (HasS1 && HasS2) {
680     size_t Pos = S1.find_first_of(S2);
681     if (Pos == StringRef::npos)
682       Pos = S1.size();
683     return ConstantInt::get(CI->getType(), Pos);
684   }
685
686   // strcspn(s, "") -> strlen(s)
687   if (HasS2 && S2.empty())
688     return EmitStrLen(CI->getArgOperand(0), B, DL, TLI);
689
690   return nullptr;
691 }
692
693 Value *LibCallSimplifier::optimizeStrStr(CallInst *CI, IRBuilder<> &B) {
694   Function *Callee = CI->getCalledFunction();
695   FunctionType *FT = Callee->getFunctionType();
696   if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
697       !FT->getParamType(1)->isPointerTy() ||
698       !FT->getReturnType()->isPointerTy())
699     return nullptr;
700
701   // fold strstr(x, x) -> x.
702   if (CI->getArgOperand(0) == CI->getArgOperand(1))
703     return B.CreateBitCast(CI->getArgOperand(0), CI->getType());
704
705   // fold strstr(a, b) == a -> strncmp(a, b, strlen(b)) == 0
706   if (isOnlyUsedInEqualityComparison(CI, CI->getArgOperand(0))) {
707     Value *StrLen = EmitStrLen(CI->getArgOperand(1), B, DL, TLI);
708     if (!StrLen)
709       return nullptr;
710     Value *StrNCmp = EmitStrNCmp(CI->getArgOperand(0), CI->getArgOperand(1),
711                                  StrLen, B, DL, TLI);
712     if (!StrNCmp)
713       return nullptr;
714     for (auto UI = CI->user_begin(), UE = CI->user_end(); UI != UE;) {
715       ICmpInst *Old = cast<ICmpInst>(*UI++);
716       Value *Cmp =
717           B.CreateICmp(Old->getPredicate(), StrNCmp,
718                        ConstantInt::getNullValue(StrNCmp->getType()), "cmp");
719       replaceAllUsesWith(Old, Cmp);
720     }
721     return CI;
722   }
723
724   // See if either input string is a constant string.
725   StringRef SearchStr, ToFindStr;
726   bool HasStr1 = getConstantStringInfo(CI->getArgOperand(0), SearchStr);
727   bool HasStr2 = getConstantStringInfo(CI->getArgOperand(1), ToFindStr);
728
729   // fold strstr(x, "") -> x.
730   if (HasStr2 && ToFindStr.empty())
731     return B.CreateBitCast(CI->getArgOperand(0), CI->getType());
732
733   // If both strings are known, constant fold it.
734   if (HasStr1 && HasStr2) {
735     size_t Offset = SearchStr.find(ToFindStr);
736
737     if (Offset == StringRef::npos) // strstr("foo", "bar") -> null
738       return Constant::getNullValue(CI->getType());
739
740     // strstr("abcd", "bc") -> gep((char*)"abcd", 1)
741     Value *Result = CastToCStr(CI->getArgOperand(0), B);
742     Result = B.CreateConstInBoundsGEP1_64(Result, Offset, "strstr");
743     return B.CreateBitCast(Result, CI->getType());
744   }
745
746   // fold strstr(x, "y") -> strchr(x, 'y').
747   if (HasStr2 && ToFindStr.size() == 1) {
748     Value *StrChr = EmitStrChr(CI->getArgOperand(0), ToFindStr[0], B, TLI);
749     return StrChr ? B.CreateBitCast(StrChr, CI->getType()) : nullptr;
750   }
751   return nullptr;
752 }
753
754 Value *LibCallSimplifier::optimizeMemChr(CallInst *CI, IRBuilder<> &B) {
755   Function *Callee = CI->getCalledFunction();
756   FunctionType *FT = Callee->getFunctionType();
757   if (FT->getNumParams() != 3 || !FT->getParamType(0)->isPointerTy() ||
758       !FT->getParamType(1)->isIntegerTy(32) ||
759       !FT->getParamType(2)->isIntegerTy() ||
760       !FT->getReturnType()->isPointerTy())
761     return nullptr;
762
763   Value *SrcStr = CI->getArgOperand(0);
764   ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
765   ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getArgOperand(2));
766
767   // memchr(x, y, 0) -> null
768   if (LenC && LenC->isNullValue())
769     return Constant::getNullValue(CI->getType());
770
771   // From now on we need at least constant length and string.
772   StringRef Str;
773   if (!LenC || !getConstantStringInfo(SrcStr, Str, 0, /*TrimAtNul=*/false))
774     return nullptr;
775
776   // Truncate the string to LenC. If Str is smaller than LenC we will still only
777   // scan the string, as reading past the end of it is undefined and we can just
778   // return null if we don't find the char.
779   Str = Str.substr(0, LenC->getZExtValue());
780
781   // If the char is variable but the input str and length are not we can turn
782   // this memchr call into a simple bit field test. Of course this only works
783   // when the return value is only checked against null.
784   //
785   // It would be really nice to reuse switch lowering here but we can't change
786   // the CFG at this point.
787   //
788   // memchr("\r\n", C, 2) != nullptr -> (C & ((1 << '\r') | (1 << '\n'))) != 0
789   //   after bounds check.
790   if (!CharC && !Str.empty() && isOnlyUsedInZeroEqualityComparison(CI)) {
791     unsigned char Max =
792         *std::max_element(reinterpret_cast<const unsigned char *>(Str.begin()),
793                           reinterpret_cast<const unsigned char *>(Str.end()));
794
795     // Make sure the bit field we're about to create fits in a register on the
796     // target.
797     // FIXME: On a 64 bit architecture this prevents us from using the
798     // interesting range of alpha ascii chars. We could do better by emitting
799     // two bitfields or shifting the range by 64 if no lower chars are used.
800     if (!DL.fitsInLegalInteger(Max + 1))
801       return nullptr;
802
803     // For the bit field use a power-of-2 type with at least 8 bits to avoid
804     // creating unnecessary illegal types.
805     unsigned char Width = NextPowerOf2(std::max((unsigned char)7, Max));
806
807     // Now build the bit field.
808     APInt Bitfield(Width, 0);
809     for (char C : Str)
810       Bitfield.setBit((unsigned char)C);
811     Value *BitfieldC = B.getInt(Bitfield);
812
813     // First check that the bit field access is within bounds.
814     Value *C = B.CreateZExtOrTrunc(CI->getArgOperand(1), BitfieldC->getType());
815     Value *Bounds = B.CreateICmp(ICmpInst::ICMP_ULT, C, B.getIntN(Width, Width),
816                                  "memchr.bounds");
817
818     // Create code that checks if the given bit is set in the field.
819     Value *Shl = B.CreateShl(B.getIntN(Width, 1ULL), C);
820     Value *Bits = B.CreateIsNotNull(B.CreateAnd(Shl, BitfieldC), "memchr.bits");
821
822     // Finally merge both checks and cast to pointer type. The inttoptr
823     // implicitly zexts the i1 to intptr type.
824     return B.CreateIntToPtr(B.CreateAnd(Bounds, Bits, "memchr"), CI->getType());
825   }
826
827   // Check if all arguments are constants.  If so, we can constant fold.
828   if (!CharC)
829     return nullptr;
830
831   // Compute the offset.
832   size_t I = Str.find(CharC->getSExtValue() & 0xFF);
833   if (I == StringRef::npos) // Didn't find the char.  memchr returns null.
834     return Constant::getNullValue(CI->getType());
835
836   // memchr(s+n,c,l) -> gep(s+n+i,c)
837   return B.CreateGEP(B.getInt8Ty(), SrcStr, B.getInt64(I), "memchr");
838 }
839
840 Value *LibCallSimplifier::optimizeMemCmp(CallInst *CI, IRBuilder<> &B) {
841   Function *Callee = CI->getCalledFunction();
842   FunctionType *FT = Callee->getFunctionType();
843   if (FT->getNumParams() != 3 || !FT->getParamType(0)->isPointerTy() ||
844       !FT->getParamType(1)->isPointerTy() ||
845       !FT->getReturnType()->isIntegerTy(32))
846     return nullptr;
847
848   Value *LHS = CI->getArgOperand(0), *RHS = CI->getArgOperand(1);
849
850   if (LHS == RHS) // memcmp(s,s,x) -> 0
851     return Constant::getNullValue(CI->getType());
852
853   // Make sure we have a constant length.
854   ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getArgOperand(2));
855   if (!LenC)
856     return nullptr;
857   uint64_t Len = LenC->getZExtValue();
858
859   if (Len == 0) // memcmp(s1,s2,0) -> 0
860     return Constant::getNullValue(CI->getType());
861
862   // memcmp(S1,S2,1) -> *(unsigned char*)LHS - *(unsigned char*)RHS
863   if (Len == 1) {
864     Value *LHSV = B.CreateZExt(B.CreateLoad(CastToCStr(LHS, B), "lhsc"),
865                                CI->getType(), "lhsv");
866     Value *RHSV = B.CreateZExt(B.CreateLoad(CastToCStr(RHS, B), "rhsc"),
867                                CI->getType(), "rhsv");
868     return B.CreateSub(LHSV, RHSV, "chardiff");
869   }
870
871   // memcmp(S1,S2,N/8)==0 -> (*(intN_t*)S1 != *(intN_t*)S2)==0
872   if (DL.isLegalInteger(Len * 8) && isOnlyUsedInZeroEqualityComparison(CI)) {
873
874     IntegerType *IntType = IntegerType::get(CI->getContext(), Len * 8);
875     unsigned PrefAlignment = DL.getPrefTypeAlignment(IntType);
876
877     if (getKnownAlignment(LHS, DL, CI) >= PrefAlignment &&
878         getKnownAlignment(RHS, DL, CI) >= PrefAlignment) {
879
880       Type *LHSPtrTy =
881           IntType->getPointerTo(LHS->getType()->getPointerAddressSpace());
882       Type *RHSPtrTy =
883           IntType->getPointerTo(RHS->getType()->getPointerAddressSpace());
884
885       Value *LHSV = B.CreateLoad(B.CreateBitCast(LHS, LHSPtrTy, "lhsc"), "lhsv");
886       Value *RHSV = B.CreateLoad(B.CreateBitCast(RHS, RHSPtrTy, "rhsc"), "rhsv");
887
888       return B.CreateZExt(B.CreateICmpNE(LHSV, RHSV), CI->getType(), "memcmp");
889     }
890   }
891
892   // Constant folding: memcmp(x, y, l) -> cnst (all arguments are constant)
893   StringRef LHSStr, RHSStr;
894   if (getConstantStringInfo(LHS, LHSStr) &&
895       getConstantStringInfo(RHS, RHSStr)) {
896     // Make sure we're not reading out-of-bounds memory.
897     if (Len > LHSStr.size() || Len > RHSStr.size())
898       return nullptr;
899     // Fold the memcmp and normalize the result.  This way we get consistent
900     // results across multiple platforms.
901     uint64_t Ret = 0;
902     int Cmp = memcmp(LHSStr.data(), RHSStr.data(), Len);
903     if (Cmp < 0)
904       Ret = -1;
905     else if (Cmp > 0)
906       Ret = 1;
907     return ConstantInt::get(CI->getType(), Ret);
908   }
909
910   return nullptr;
911 }
912
913 Value *LibCallSimplifier::optimizeMemCpy(CallInst *CI, IRBuilder<> &B) {
914   Function *Callee = CI->getCalledFunction();
915
916   if (!checkStringCopyLibFuncSignature(Callee, LibFunc::memcpy))
917     return nullptr;
918
919   // memcpy(x, y, n) -> llvm.memcpy(x, y, n, 1)
920   B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
921                  CI->getArgOperand(2), 1, 1);
922   return CI->getArgOperand(0);
923 }
924
925 Value *LibCallSimplifier::optimizeMemMove(CallInst *CI, IRBuilder<> &B) {
926   Function *Callee = CI->getCalledFunction();
927
928   if (!checkStringCopyLibFuncSignature(Callee, LibFunc::memmove))
929     return nullptr;
930
931   // memmove(x, y, n) -> llvm.memmove(x, y, n, 1)
932   B.CreateMemMove(CI->getArgOperand(0), CI->getArgOperand(1),
933                   CI->getArgOperand(2), 1, 1);
934   return CI->getArgOperand(0);
935 }
936
937 Value *LibCallSimplifier::optimizeMemSet(CallInst *CI, IRBuilder<> &B) {
938   Function *Callee = CI->getCalledFunction();
939
940   if (!checkStringCopyLibFuncSignature(Callee, LibFunc::memset))
941     return nullptr;
942
943   // memset(p, v, n) -> llvm.memset(p, v, n, 1)
944   Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(), false);
945   B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1);
946   return CI->getArgOperand(0);
947 }
948
949 //===----------------------------------------------------------------------===//
950 // Math Library Optimizations
951 //===----------------------------------------------------------------------===//
952
953 /// Return a variant of Val with float type.
954 /// Currently this works in two cases: If Val is an FPExtension of a float
955 /// value to something bigger, simply return the operand.
956 /// If Val is a ConstantFP but can be converted to a float ConstantFP without
957 /// loss of precision do so.
958 static Value *valueHasFloatPrecision(Value *Val) {
959   if (FPExtInst *Cast = dyn_cast<FPExtInst>(Val)) {
960     Value *Op = Cast->getOperand(0);
961     if (Op->getType()->isFloatTy())
962       return Op;
963   }
964   if (ConstantFP *Const = dyn_cast<ConstantFP>(Val)) {
965     APFloat F = Const->getValueAPF();
966     bool losesInfo;
967     (void)F.convert(APFloat::IEEEsingle, APFloat::rmNearestTiesToEven,
968                     &losesInfo);
969     if (!losesInfo)
970       return ConstantFP::get(Const->getContext(), F);
971   }
972   return nullptr;
973 }
974
975 //===----------------------------------------------------------------------===//
976 // Double -> Float Shrinking Optimizations for Unary Functions like 'floor'
977
978 Value *LibCallSimplifier::optimizeUnaryDoubleFP(CallInst *CI, IRBuilder<> &B,
979                                                 bool CheckRetType) {
980   Function *Callee = CI->getCalledFunction();
981   FunctionType *FT = Callee->getFunctionType();
982   if (FT->getNumParams() != 1 || !FT->getReturnType()->isDoubleTy() ||
983       !FT->getParamType(0)->isDoubleTy())
984     return nullptr;
985
986   if (CheckRetType) {
987     // Check if all the uses for function like 'sin' are converted to float.
988     for (User *U : CI->users()) {
989       FPTruncInst *Cast = dyn_cast<FPTruncInst>(U);
990       if (!Cast || !Cast->getType()->isFloatTy())
991         return nullptr;
992     }
993   }
994
995   // If this is something like 'floor((double)floatval)', convert to floorf.
996   Value *V = valueHasFloatPrecision(CI->getArgOperand(0));
997   if (V == nullptr)
998     return nullptr;
999
1000   // floor((double)floatval) -> (double)floorf(floatval)
1001   if (Callee->isIntrinsic()) {
1002     Module *M = CI->getParent()->getParent()->getParent();
1003     Intrinsic::ID IID = Callee->getIntrinsicID();
1004     Function *F = Intrinsic::getDeclaration(M, IID, B.getFloatTy());
1005     V = B.CreateCall(F, V);
1006   } else {
1007     // The call is a library call rather than an intrinsic.
1008     V = EmitUnaryFloatFnCall(V, Callee->getName(), B, Callee->getAttributes());
1009   }
1010
1011   return B.CreateFPExt(V, B.getDoubleTy());
1012 }
1013
1014 // Double -> Float Shrinking Optimizations for Binary Functions like 'fmin/fmax'
1015 Value *LibCallSimplifier::optimizeBinaryDoubleFP(CallInst *CI, IRBuilder<> &B) {
1016   Function *Callee = CI->getCalledFunction();
1017   FunctionType *FT = Callee->getFunctionType();
1018   // Just make sure this has 2 arguments of the same FP type, which match the
1019   // result type.
1020   if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) ||
1021       FT->getParamType(0) != FT->getParamType(1) ||
1022       !FT->getParamType(0)->isFloatingPointTy())
1023     return nullptr;
1024
1025   // If this is something like 'fmin((double)floatval1, (double)floatval2)',
1026   // or fmin(1.0, (double)floatval), then we convert it to fminf.
1027   Value *V1 = valueHasFloatPrecision(CI->getArgOperand(0));
1028   if (V1 == nullptr)
1029     return nullptr;
1030   Value *V2 = valueHasFloatPrecision(CI->getArgOperand(1));
1031   if (V2 == nullptr)
1032     return nullptr;
1033
1034   // fmin((double)floatval1, (double)floatval2)
1035   //                      -> (double)fminf(floatval1, floatval2)
1036   // TODO: Handle intrinsics in the same way as in optimizeUnaryDoubleFP().
1037   Value *V = EmitBinaryFloatFnCall(V1, V2, Callee->getName(), B,
1038                                    Callee->getAttributes());
1039   return B.CreateFPExt(V, B.getDoubleTy());
1040 }
1041
1042 Value *LibCallSimplifier::optimizeCos(CallInst *CI, IRBuilder<> &B) {
1043   Function *Callee = CI->getCalledFunction();
1044   Value *Ret = nullptr;
1045   StringRef Name = Callee->getName();
1046   if (UnsafeFPShrink && Name == "cos" && hasFloatVersion(Name))
1047     Ret = optimizeUnaryDoubleFP(CI, B, true);
1048
1049   FunctionType *FT = Callee->getFunctionType();
1050   // Just make sure this has 1 argument of FP type, which matches the
1051   // result type.
1052   if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1053       !FT->getParamType(0)->isFloatingPointTy())
1054     return Ret;
1055
1056   // cos(-x) -> cos(x)
1057   Value *Op1 = CI->getArgOperand(0);
1058   if (BinaryOperator::isFNeg(Op1)) {
1059     BinaryOperator *BinExpr = cast<BinaryOperator>(Op1);
1060     return B.CreateCall(Callee, BinExpr->getOperand(1), "cos");
1061   }
1062   return Ret;
1063 }
1064
1065 Value *LibCallSimplifier::optimizePow(CallInst *CI, IRBuilder<> &B) {
1066   Function *Callee = CI->getCalledFunction();
1067   Value *Ret = nullptr;
1068   StringRef Name = Callee->getName();
1069   if (UnsafeFPShrink && Name == "pow" && hasFloatVersion(Name))
1070     Ret = optimizeUnaryDoubleFP(CI, B, true);
1071
1072   FunctionType *FT = Callee->getFunctionType();
1073   // Just make sure this has 2 arguments of the same FP type, which match the
1074   // result type.
1075   if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) ||
1076       FT->getParamType(0) != FT->getParamType(1) ||
1077       !FT->getParamType(0)->isFloatingPointTy())
1078     return Ret;
1079
1080   Value *Op1 = CI->getArgOperand(0), *Op2 = CI->getArgOperand(1);
1081   if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) {
1082     // pow(1.0, x) -> 1.0
1083     if (Op1C->isExactlyValue(1.0))
1084       return Op1C;
1085     // pow(2.0, x) -> exp2(x)
1086     if (Op1C->isExactlyValue(2.0) &&
1087         hasUnaryFloatFn(TLI, Op1->getType(), LibFunc::exp2, LibFunc::exp2f,
1088                         LibFunc::exp2l))
1089       return EmitUnaryFloatFnCall(Op2, TLI->getName(LibFunc::exp2), B,
1090                                   Callee->getAttributes());
1091     // pow(10.0, x) -> exp10(x)
1092     if (Op1C->isExactlyValue(10.0) &&
1093         hasUnaryFloatFn(TLI, Op1->getType(), LibFunc::exp10, LibFunc::exp10f,
1094                         LibFunc::exp10l))
1095       return EmitUnaryFloatFnCall(Op2, TLI->getName(LibFunc::exp10), B,
1096                                   Callee->getAttributes());
1097   }
1098
1099   // pow(exp(x), y) -> exp(x*y)
1100   // pow(exp2(x), y) -> exp2(x * y)
1101   // We enable these only under fast-math. Besides rounding
1102   // differences the transformation changes overflow and
1103   // underflow behavior quite dramatically.
1104   // Example: x = 1000, y = 0.001.
1105   // pow(exp(x), y) = pow(inf, 0.001) = inf, whereas exp(x*y) = exp(1).
1106   if (canUseUnsafeFPMath(CI->getParent()->getParent())) {
1107     if (auto *OpC = dyn_cast<CallInst>(Op1)) {
1108       IRBuilder<>::FastMathFlagGuard Guard(B);
1109       FastMathFlags FMF;
1110       FMF.setUnsafeAlgebra();
1111       B.SetFastMathFlags(FMF);
1112
1113       LibFunc::Func Func;
1114       Function *Callee = OpC->getCalledFunction();
1115       StringRef FuncName = Callee->getName();
1116
1117       if (TLI->getLibFunc(FuncName, Func) && TLI->has(Func) &&
1118           (Func == LibFunc::exp || Func == LibFunc::exp2))
1119         return EmitUnaryFloatFnCall(
1120             B.CreateFMul(OpC->getArgOperand(0), Op2, "mul"), FuncName, B,
1121             Callee->getAttributes());
1122     }
1123   }
1124
1125   ConstantFP *Op2C = dyn_cast<ConstantFP>(Op2);
1126   if (!Op2C)
1127     return Ret;
1128
1129   if (Op2C->getValueAPF().isZero()) // pow(x, 0.0) -> 1.0
1130     return ConstantFP::get(CI->getType(), 1.0);
1131
1132   if (Op2C->isExactlyValue(0.5) &&
1133       hasUnaryFloatFn(TLI, Op2->getType(), LibFunc::sqrt, LibFunc::sqrtf,
1134                       LibFunc::sqrtl) &&
1135       hasUnaryFloatFn(TLI, Op2->getType(), LibFunc::fabs, LibFunc::fabsf,
1136                       LibFunc::fabsl)) {
1137     // Expand pow(x, 0.5) to (x == -infinity ? +infinity : fabs(sqrt(x))).
1138     // This is faster than calling pow, and still handles negative zero
1139     // and negative infinity correctly.
1140     // TODO: In fast-math mode, this could be just sqrt(x).
1141     // TODO: In finite-only mode, this could be just fabs(sqrt(x)).
1142     Value *Inf = ConstantFP::getInfinity(CI->getType());
1143     Value *NegInf = ConstantFP::getInfinity(CI->getType(), true);
1144     Value *Sqrt = EmitUnaryFloatFnCall(Op1, "sqrt", B, Callee->getAttributes());
1145     Value *FAbs =
1146         EmitUnaryFloatFnCall(Sqrt, "fabs", B, Callee->getAttributes());
1147     Value *FCmp = B.CreateFCmpOEQ(Op1, NegInf);
1148     Value *Sel = B.CreateSelect(FCmp, Inf, FAbs);
1149     return Sel;
1150   }
1151
1152   if (Op2C->isExactlyValue(1.0)) // pow(x, 1.0) -> x
1153     return Op1;
1154   if (Op2C->isExactlyValue(2.0)) // pow(x, 2.0) -> x*x
1155     return B.CreateFMul(Op1, Op1, "pow2");
1156   if (Op2C->isExactlyValue(-1.0)) // pow(x, -1.0) -> 1.0/x
1157     return B.CreateFDiv(ConstantFP::get(CI->getType(), 1.0), Op1, "powrecip");
1158   return nullptr;
1159 }
1160
1161 Value *LibCallSimplifier::optimizeExp2(CallInst *CI, IRBuilder<> &B) {
1162   Function *Callee = CI->getCalledFunction();
1163   Function *Caller = CI->getParent()->getParent();
1164   Value *Ret = nullptr;
1165   StringRef Name = Callee->getName();
1166   if (UnsafeFPShrink && Name == "exp2" && hasFloatVersion(Name))
1167     Ret = optimizeUnaryDoubleFP(CI, B, true);
1168
1169   FunctionType *FT = Callee->getFunctionType();
1170   // Just make sure this has 1 argument of FP type, which matches the
1171   // result type.
1172   if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1173       !FT->getParamType(0)->isFloatingPointTy())
1174     return Ret;
1175
1176   Value *Op = CI->getArgOperand(0);
1177   // Turn exp2(sitofp(x)) -> ldexp(1.0, sext(x))  if sizeof(x) <= 32
1178   // Turn exp2(uitofp(x)) -> ldexp(1.0, zext(x))  if sizeof(x) < 32
1179   LibFunc::Func LdExp = LibFunc::ldexpl;
1180   if (Op->getType()->isFloatTy())
1181     LdExp = LibFunc::ldexpf;
1182   else if (Op->getType()->isDoubleTy())
1183     LdExp = LibFunc::ldexp;
1184
1185   if (TLI->has(LdExp)) {
1186     Value *LdExpArg = nullptr;
1187     if (SIToFPInst *OpC = dyn_cast<SIToFPInst>(Op)) {
1188       if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() <= 32)
1189         LdExpArg = B.CreateSExt(OpC->getOperand(0), B.getInt32Ty());
1190     } else if (UIToFPInst *OpC = dyn_cast<UIToFPInst>(Op)) {
1191       if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() < 32)
1192         LdExpArg = B.CreateZExt(OpC->getOperand(0), B.getInt32Ty());
1193     }
1194
1195     if (LdExpArg) {
1196       Constant *One = ConstantFP::get(CI->getContext(), APFloat(1.0f));
1197       if (!Op->getType()->isFloatTy())
1198         One = ConstantExpr::getFPExtend(One, Op->getType());
1199
1200       Module *M = Caller->getParent();
1201       Value *Callee =
1202           M->getOrInsertFunction(TLI->getName(LdExp), Op->getType(),
1203                                  Op->getType(), B.getInt32Ty(), nullptr);
1204       CallInst *CI = B.CreateCall(Callee, {One, LdExpArg});
1205       if (const Function *F = dyn_cast<Function>(Callee->stripPointerCasts()))
1206         CI->setCallingConv(F->getCallingConv());
1207
1208       return CI;
1209     }
1210   }
1211   return Ret;
1212 }
1213
1214 Value *LibCallSimplifier::optimizeFabs(CallInst *CI, IRBuilder<> &B) {
1215   Function *Callee = CI->getCalledFunction();
1216   Value *Ret = nullptr;
1217   StringRef Name = Callee->getName();
1218   if (Name == "fabs" && hasFloatVersion(Name))
1219     Ret = optimizeUnaryDoubleFP(CI, B, false);
1220
1221   FunctionType *FT = Callee->getFunctionType();
1222   // Make sure this has 1 argument of FP type which matches the result type.
1223   if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1224       !FT->getParamType(0)->isFloatingPointTy())
1225     return Ret;
1226
1227   Value *Op = CI->getArgOperand(0);
1228   if (Instruction *I = dyn_cast<Instruction>(Op)) {
1229     // Fold fabs(x * x) -> x * x; any squared FP value must already be positive.
1230     if (I->getOpcode() == Instruction::FMul)
1231       if (I->getOperand(0) == I->getOperand(1))
1232         return Op;
1233   }
1234   return Ret;
1235 }
1236
1237 Value *LibCallSimplifier::optimizeFMinFMax(CallInst *CI, IRBuilder<> &B) {
1238   // If we can shrink the call to a float function rather than a double
1239   // function, do that first.
1240   Function *Callee = CI->getCalledFunction();
1241   StringRef Name = Callee->getName();
1242   if ((Name == "fmin" && hasFloatVersion(Name)) ||
1243       (Name == "fmax" && hasFloatVersion(Name))) {
1244     Value *Ret = optimizeBinaryDoubleFP(CI, B);
1245     if (Ret)
1246       return Ret;
1247   }
1248
1249   // Make sure this has 2 arguments of FP type which match the result type.
1250   FunctionType *FT = Callee->getFunctionType();
1251   if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) ||
1252       FT->getParamType(0) != FT->getParamType(1) ||
1253       !FT->getParamType(0)->isFloatingPointTy())
1254     return nullptr;
1255
1256   IRBuilder<>::FastMathFlagGuard Guard(B);
1257   FastMathFlags FMF;
1258   Function *F = CI->getParent()->getParent();
1259   if (canUseUnsafeFPMath(F)) {
1260     // Unsafe algebra sets all fast-math-flags to true.
1261     FMF.setUnsafeAlgebra();
1262   } else {
1263     // At a minimum, no-nans-fp-math must be true.
1264     Attribute Attr = F->getFnAttribute("no-nans-fp-math");
1265     if (Attr.getValueAsString() != "true")
1266       return nullptr;
1267     // No-signed-zeros is implied by the definitions of fmax/fmin themselves:
1268     // "Ideally, fmax would be sensitive to the sign of zero, for example
1269     // fmax(-0. 0, +0. 0) would return +0; however, implementation in software
1270     // might be impractical."
1271     FMF.setNoSignedZeros();
1272     FMF.setNoNaNs();
1273   }
1274   B.SetFastMathFlags(FMF);
1275
1276   // We have a relaxed floating-point environment. We can ignore NaN-handling
1277   // and transform to a compare and select. We do not have to consider errno or
1278   // exceptions, because fmin/fmax do not have those.
1279   Value *Op0 = CI->getArgOperand(0);
1280   Value *Op1 = CI->getArgOperand(1);
1281   Value *Cmp = Callee->getName().startswith("fmin") ?
1282     B.CreateFCmpOLT(Op0, Op1) : B.CreateFCmpOGT(Op0, Op1);
1283   return B.CreateSelect(Cmp, Op0, Op1);
1284 }
1285
1286 Value *LibCallSimplifier::optimizeSqrt(CallInst *CI, IRBuilder<> &B) {
1287   Function *Callee = CI->getCalledFunction();
1288   
1289   Value *Ret = nullptr;
1290   if (TLI->has(LibFunc::sqrtf) && (Callee->getName() == "sqrt" ||
1291                                    Callee->getIntrinsicID() == Intrinsic::sqrt))
1292     Ret = optimizeUnaryDoubleFP(CI, B, true);
1293   if (!canUseUnsafeFPMath(CI->getParent()->getParent()))
1294     return Ret;
1295
1296   Value *Op = CI->getArgOperand(0);
1297   if (Instruction *I = dyn_cast<Instruction>(Op)) {
1298     if (I->getOpcode() == Instruction::FMul && I->hasUnsafeAlgebra()) {
1299       // We're looking for a repeated factor in a multiplication tree,
1300       // so we can do this fold: sqrt(x * x) -> fabs(x);
1301       // or this fold: sqrt(x * x * y) -> fabs(x) * sqrt(y).
1302       Value *Op0 = I->getOperand(0);
1303       Value *Op1 = I->getOperand(1);
1304       Value *RepeatOp = nullptr;
1305       Value *OtherOp = nullptr;
1306       if (Op0 == Op1) {
1307         // Simple match: the operands of the multiply are identical.
1308         RepeatOp = Op0;
1309       } else {
1310         // Look for a more complicated pattern: one of the operands is itself
1311         // a multiply, so search for a common factor in that multiply.
1312         // Note: We don't bother looking any deeper than this first level or for
1313         // variations of this pattern because instcombine's visitFMUL and/or the
1314         // reassociation pass should give us this form.
1315         Value *OtherMul0, *OtherMul1;
1316         if (match(Op0, m_FMul(m_Value(OtherMul0), m_Value(OtherMul1)))) {
1317           // Pattern: sqrt((x * y) * z)
1318           if (OtherMul0 == OtherMul1) {
1319             // Matched: sqrt((x * x) * z)
1320             RepeatOp = OtherMul0;
1321             OtherOp = Op1;
1322           }
1323         }
1324       }
1325       if (RepeatOp) {
1326         // Fast math flags for any created instructions should match the sqrt
1327         // and multiply.
1328         // FIXME: We're not checking the sqrt because it doesn't have
1329         // fast-math-flags (see earlier comment).
1330         IRBuilder<>::FastMathFlagGuard Guard(B);
1331         B.SetFastMathFlags(I->getFastMathFlags());
1332         // If we found a repeated factor, hoist it out of the square root and
1333         // replace it with the fabs of that factor.
1334         Module *M = Callee->getParent();
1335         Type *ArgType = Op->getType();
1336         Value *Fabs = Intrinsic::getDeclaration(M, Intrinsic::fabs, ArgType);
1337         Value *FabsCall = B.CreateCall(Fabs, RepeatOp, "fabs");
1338         if (OtherOp) {
1339           // If we found a non-repeated factor, we still need to get its square
1340           // root. We then multiply that by the value that was simplified out
1341           // of the square root calculation.
1342           Value *Sqrt = Intrinsic::getDeclaration(M, Intrinsic::sqrt, ArgType);
1343           Value *SqrtCall = B.CreateCall(Sqrt, OtherOp, "sqrt");
1344           return B.CreateFMul(FabsCall, SqrtCall);
1345         }
1346         return FabsCall;
1347       }
1348     }
1349   }
1350   return Ret;
1351 }
1352
1353 Value *LibCallSimplifier::optimizeTan(CallInst *CI, IRBuilder<> &B) {
1354   Function *Callee = CI->getCalledFunction();
1355   Value *Ret = nullptr;
1356   StringRef Name = Callee->getName();
1357   if (UnsafeFPShrink && Name == "tan" && hasFloatVersion(Name))
1358     Ret = optimizeUnaryDoubleFP(CI, B, true);
1359   FunctionType *FT = Callee->getFunctionType();
1360
1361   // Just make sure this has 1 argument of FP type, which matches the
1362   // result type.
1363   if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1364       !FT->getParamType(0)->isFloatingPointTy())
1365     return Ret;
1366
1367   if (!canUseUnsafeFPMath(CI->getParent()->getParent()))
1368     return Ret;
1369   Value *Op1 = CI->getArgOperand(0);
1370   auto *OpC = dyn_cast<CallInst>(Op1);
1371   if (!OpC)
1372     return Ret;
1373
1374   // tan(atan(x)) -> x
1375   // tanf(atanf(x)) -> x
1376   // tanl(atanl(x)) -> x
1377   LibFunc::Func Func;
1378   Function *F = OpC->getCalledFunction();
1379   StringRef FuncName = F->getName();
1380   if (TLI->getLibFunc(FuncName, Func) && TLI->has(Func) &&
1381       ((Func == LibFunc::atan && Callee->getName() == "tan") ||
1382        (Func == LibFunc::atanf && Callee->getName() == "tanf") ||
1383        (Func == LibFunc::atanl && Callee->getName() == "tanl")))
1384     Ret = OpC->getArgOperand(0);
1385   return Ret;
1386 }
1387
1388 static bool isTrigLibCall(CallInst *CI);
1389 static void insertSinCosCall(IRBuilder<> &B, Function *OrigCallee, Value *Arg,
1390                              bool UseFloat, Value *&Sin, Value *&Cos,
1391                              Value *&SinCos);
1392
1393 Value *LibCallSimplifier::optimizeSinCosPi(CallInst *CI, IRBuilder<> &B) {
1394
1395   // Make sure the prototype is as expected, otherwise the rest of the
1396   // function is probably invalid and likely to abort.
1397   if (!isTrigLibCall(CI))
1398     return nullptr;
1399
1400   Value *Arg = CI->getArgOperand(0);
1401   SmallVector<CallInst *, 1> SinCalls;
1402   SmallVector<CallInst *, 1> CosCalls;
1403   SmallVector<CallInst *, 1> SinCosCalls;
1404
1405   bool IsFloat = Arg->getType()->isFloatTy();
1406
1407   // Look for all compatible sinpi, cospi and sincospi calls with the same
1408   // argument. If there are enough (in some sense) we can make the
1409   // substitution.
1410   for (User *U : Arg->users())
1411     classifyArgUse(U, CI->getParent(), IsFloat, SinCalls, CosCalls,
1412                    SinCosCalls);
1413
1414   // It's only worthwhile if both sinpi and cospi are actually used.
1415   if (SinCosCalls.empty() && (SinCalls.empty() || CosCalls.empty()))
1416     return nullptr;
1417
1418   Value *Sin, *Cos, *SinCos;
1419   insertSinCosCall(B, CI->getCalledFunction(), Arg, IsFloat, Sin, Cos, SinCos);
1420
1421   replaceTrigInsts(SinCalls, Sin);
1422   replaceTrigInsts(CosCalls, Cos);
1423   replaceTrigInsts(SinCosCalls, SinCos);
1424
1425   return nullptr;
1426 }
1427
1428 static bool isTrigLibCall(CallInst *CI) {
1429   Function *Callee = CI->getCalledFunction();
1430   FunctionType *FT = Callee->getFunctionType();
1431
1432   // We can only hope to do anything useful if we can ignore things like errno
1433   // and floating-point exceptions.
1434   bool AttributesSafe =
1435       CI->hasFnAttr(Attribute::NoUnwind) && CI->hasFnAttr(Attribute::ReadNone);
1436
1437   // Other than that we need float(float) or double(double)
1438   return AttributesSafe && FT->getNumParams() == 1 &&
1439          FT->getReturnType() == FT->getParamType(0) &&
1440          (FT->getParamType(0)->isFloatTy() ||
1441           FT->getParamType(0)->isDoubleTy());
1442 }
1443
1444 void
1445 LibCallSimplifier::classifyArgUse(Value *Val, BasicBlock *BB, bool IsFloat,
1446                                   SmallVectorImpl<CallInst *> &SinCalls,
1447                                   SmallVectorImpl<CallInst *> &CosCalls,
1448                                   SmallVectorImpl<CallInst *> &SinCosCalls) {
1449   CallInst *CI = dyn_cast<CallInst>(Val);
1450
1451   if (!CI)
1452     return;
1453
1454   Function *Callee = CI->getCalledFunction();
1455   StringRef FuncName = Callee->getName();
1456   LibFunc::Func Func;
1457   if (!TLI->getLibFunc(FuncName, Func) || !TLI->has(Func) || !isTrigLibCall(CI))
1458     return;
1459
1460   if (IsFloat) {
1461     if (Func == LibFunc::sinpif)
1462       SinCalls.push_back(CI);
1463     else if (Func == LibFunc::cospif)
1464       CosCalls.push_back(CI);
1465     else if (Func == LibFunc::sincospif_stret)
1466       SinCosCalls.push_back(CI);
1467   } else {
1468     if (Func == LibFunc::sinpi)
1469       SinCalls.push_back(CI);
1470     else if (Func == LibFunc::cospi)
1471       CosCalls.push_back(CI);
1472     else if (Func == LibFunc::sincospi_stret)
1473       SinCosCalls.push_back(CI);
1474   }
1475 }
1476
1477 void LibCallSimplifier::replaceTrigInsts(SmallVectorImpl<CallInst *> &Calls,
1478                                          Value *Res) {
1479   for (CallInst *C : Calls)
1480     replaceAllUsesWith(C, Res);
1481 }
1482
1483 void insertSinCosCall(IRBuilder<> &B, Function *OrigCallee, Value *Arg,
1484                       bool UseFloat, Value *&Sin, Value *&Cos, Value *&SinCos) {
1485   Type *ArgTy = Arg->getType();
1486   Type *ResTy;
1487   StringRef Name;
1488
1489   Triple T(OrigCallee->getParent()->getTargetTriple());
1490   if (UseFloat) {
1491     Name = "__sincospif_stret";
1492
1493     assert(T.getArch() != Triple::x86 && "x86 messy and unsupported for now");
1494     // x86_64 can't use {float, float} since that would be returned in both
1495     // xmm0 and xmm1, which isn't what a real struct would do.
1496     ResTy = T.getArch() == Triple::x86_64
1497                 ? static_cast<Type *>(VectorType::get(ArgTy, 2))
1498                 : static_cast<Type *>(StructType::get(ArgTy, ArgTy, nullptr));
1499   } else {
1500     Name = "__sincospi_stret";
1501     ResTy = StructType::get(ArgTy, ArgTy, nullptr);
1502   }
1503
1504   Module *M = OrigCallee->getParent();
1505   Value *Callee = M->getOrInsertFunction(Name, OrigCallee->getAttributes(),
1506                                          ResTy, ArgTy, nullptr);
1507
1508   if (Instruction *ArgInst = dyn_cast<Instruction>(Arg)) {
1509     // If the argument is an instruction, it must dominate all uses so put our
1510     // sincos call there.
1511     B.SetInsertPoint(ArgInst->getParent(), ++ArgInst->getIterator());
1512   } else {
1513     // Otherwise (e.g. for a constant) the beginning of the function is as
1514     // good a place as any.
1515     BasicBlock &EntryBB = B.GetInsertBlock()->getParent()->getEntryBlock();
1516     B.SetInsertPoint(&EntryBB, EntryBB.begin());
1517   }
1518
1519   SinCos = B.CreateCall(Callee, Arg, "sincospi");
1520
1521   if (SinCos->getType()->isStructTy()) {
1522     Sin = B.CreateExtractValue(SinCos, 0, "sinpi");
1523     Cos = B.CreateExtractValue(SinCos, 1, "cospi");
1524   } else {
1525     Sin = B.CreateExtractElement(SinCos, ConstantInt::get(B.getInt32Ty(), 0),
1526                                  "sinpi");
1527     Cos = B.CreateExtractElement(SinCos, ConstantInt::get(B.getInt32Ty(), 1),
1528                                  "cospi");
1529   }
1530 }
1531
1532 //===----------------------------------------------------------------------===//
1533 // Integer Library Call Optimizations
1534 //===----------------------------------------------------------------------===//
1535
1536 static bool checkIntUnaryReturnAndParam(Function *Callee) {
1537   FunctionType *FT = Callee->getFunctionType();
1538   return FT->getNumParams() == 1 && FT->getReturnType()->isIntegerTy(32) &&
1539     FT->getParamType(0)->isIntegerTy();
1540 }
1541
1542 Value *LibCallSimplifier::optimizeFFS(CallInst *CI, IRBuilder<> &B) {
1543   Function *Callee = CI->getCalledFunction();
1544   if (!checkIntUnaryReturnAndParam(Callee))
1545     return nullptr;
1546   Value *Op = CI->getArgOperand(0);
1547
1548   // Constant fold.
1549   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op)) {
1550     if (CI->isZero()) // ffs(0) -> 0.
1551       return B.getInt32(0);
1552     // ffs(c) -> cttz(c)+1
1553     return B.getInt32(CI->getValue().countTrailingZeros() + 1);
1554   }
1555
1556   // ffs(x) -> x != 0 ? (i32)llvm.cttz(x)+1 : 0
1557   Type *ArgType = Op->getType();
1558   Value *F =
1559       Intrinsic::getDeclaration(Callee->getParent(), Intrinsic::cttz, ArgType);
1560   Value *V = B.CreateCall(F, {Op, B.getTrue()}, "cttz");
1561   V = B.CreateAdd(V, ConstantInt::get(V->getType(), 1));
1562   V = B.CreateIntCast(V, B.getInt32Ty(), false);
1563
1564   Value *Cond = B.CreateICmpNE(Op, Constant::getNullValue(ArgType));
1565   return B.CreateSelect(Cond, V, B.getInt32(0));
1566 }
1567
1568 Value *LibCallSimplifier::optimizeAbs(CallInst *CI, IRBuilder<> &B) {
1569   Function *Callee = CI->getCalledFunction();
1570   FunctionType *FT = Callee->getFunctionType();
1571   // We require integer(integer) where the types agree.
1572   if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
1573       FT->getParamType(0) != FT->getReturnType())
1574     return nullptr;
1575
1576   // abs(x) -> x >s -1 ? x : -x
1577   Value *Op = CI->getArgOperand(0);
1578   Value *Pos =
1579       B.CreateICmpSGT(Op, Constant::getAllOnesValue(Op->getType()), "ispos");
1580   Value *Neg = B.CreateNeg(Op, "neg");
1581   return B.CreateSelect(Pos, Op, Neg);
1582 }
1583
1584 Value *LibCallSimplifier::optimizeIsDigit(CallInst *CI, IRBuilder<> &B) {
1585   if (!checkIntUnaryReturnAndParam(CI->getCalledFunction()))
1586     return nullptr;
1587
1588   // isdigit(c) -> (c-'0') <u 10
1589   Value *Op = CI->getArgOperand(0);
1590   Op = B.CreateSub(Op, B.getInt32('0'), "isdigittmp");
1591   Op = B.CreateICmpULT(Op, B.getInt32(10), "isdigit");
1592   return B.CreateZExt(Op, CI->getType());
1593 }
1594
1595 Value *LibCallSimplifier::optimizeIsAscii(CallInst *CI, IRBuilder<> &B) {
1596   if (!checkIntUnaryReturnAndParam(CI->getCalledFunction()))
1597     return nullptr;
1598
1599   // isascii(c) -> c <u 128
1600   Value *Op = CI->getArgOperand(0);
1601   Op = B.CreateICmpULT(Op, B.getInt32(128), "isascii");
1602   return B.CreateZExt(Op, CI->getType());
1603 }
1604
1605 Value *LibCallSimplifier::optimizeToAscii(CallInst *CI, IRBuilder<> &B) {
1606   if (!checkIntUnaryReturnAndParam(CI->getCalledFunction()))
1607     return nullptr;
1608
1609   // toascii(c) -> c & 0x7f
1610   return B.CreateAnd(CI->getArgOperand(0),
1611                      ConstantInt::get(CI->getType(), 0x7F));
1612 }
1613
1614 //===----------------------------------------------------------------------===//
1615 // Formatting and IO Library Call Optimizations
1616 //===----------------------------------------------------------------------===//
1617
1618 static bool isReportingError(Function *Callee, CallInst *CI, int StreamArg);
1619
1620 Value *LibCallSimplifier::optimizeErrorReporting(CallInst *CI, IRBuilder<> &B,
1621                                                  int StreamArg) {
1622   // Error reporting calls should be cold, mark them as such.
1623   // This applies even to non-builtin calls: it is only a hint and applies to
1624   // functions that the frontend might not understand as builtins.
1625
1626   // This heuristic was suggested in:
1627   // Improving Static Branch Prediction in a Compiler
1628   // Brian L. Deitrich, Ben-Chung Cheng, Wen-mei W. Hwu
1629   // Proceedings of PACT'98, Oct. 1998, IEEE
1630   Function *Callee = CI->getCalledFunction();
1631
1632   if (!CI->hasFnAttr(Attribute::Cold) &&
1633       isReportingError(Callee, CI, StreamArg)) {
1634     CI->addAttribute(AttributeSet::FunctionIndex, Attribute::Cold);
1635   }
1636
1637   return nullptr;
1638 }
1639
1640 static bool isReportingError(Function *Callee, CallInst *CI, int StreamArg) {
1641   if (!ColdErrorCalls || !Callee || !Callee->isDeclaration())
1642     return false;
1643
1644   if (StreamArg < 0)
1645     return true;
1646
1647   // These functions might be considered cold, but only if their stream
1648   // argument is stderr.
1649
1650   if (StreamArg >= (int)CI->getNumArgOperands())
1651     return false;
1652   LoadInst *LI = dyn_cast<LoadInst>(CI->getArgOperand(StreamArg));
1653   if (!LI)
1654     return false;
1655   GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getPointerOperand());
1656   if (!GV || !GV->isDeclaration())
1657     return false;
1658   return GV->getName() == "stderr";
1659 }
1660
1661 Value *LibCallSimplifier::optimizePrintFString(CallInst *CI, IRBuilder<> &B) {
1662   // Check for a fixed format string.
1663   StringRef FormatStr;
1664   if (!getConstantStringInfo(CI->getArgOperand(0), FormatStr))
1665     return nullptr;
1666
1667   // Empty format string -> noop.
1668   if (FormatStr.empty()) // Tolerate printf's declared void.
1669     return CI->use_empty() ? (Value *)CI : ConstantInt::get(CI->getType(), 0);
1670
1671   // Do not do any of the following transformations if the printf return value
1672   // is used, in general the printf return value is not compatible with either
1673   // putchar() or puts().
1674   if (!CI->use_empty())
1675     return nullptr;
1676
1677   // printf("x") -> putchar('x'), even for '%'.
1678   if (FormatStr.size() == 1) {
1679     Value *Res = EmitPutChar(B.getInt32(FormatStr[0]), B, TLI);
1680     if (CI->use_empty() || !Res)
1681       return Res;
1682     return B.CreateIntCast(Res, CI->getType(), true);
1683   }
1684
1685   // printf("foo\n") --> puts("foo")
1686   if (FormatStr[FormatStr.size() - 1] == '\n' &&
1687       FormatStr.find('%') == StringRef::npos) { // No format characters.
1688     // Create a string literal with no \n on it.  We expect the constant merge
1689     // pass to be run after this pass, to merge duplicate strings.
1690     FormatStr = FormatStr.drop_back();
1691     Value *GV = B.CreateGlobalString(FormatStr, "str");
1692     Value *NewCI = EmitPutS(GV, B, TLI);
1693     return (CI->use_empty() || !NewCI)
1694                ? NewCI
1695                : ConstantInt::get(CI->getType(), FormatStr.size() + 1);
1696   }
1697
1698   // Optimize specific format strings.
1699   // printf("%c", chr) --> putchar(chr)
1700   if (FormatStr == "%c" && CI->getNumArgOperands() > 1 &&
1701       CI->getArgOperand(1)->getType()->isIntegerTy()) {
1702     Value *Res = EmitPutChar(CI->getArgOperand(1), B, TLI);
1703
1704     if (CI->use_empty() || !Res)
1705       return Res;
1706     return B.CreateIntCast(Res, CI->getType(), true);
1707   }
1708
1709   // printf("%s\n", str) --> puts(str)
1710   if (FormatStr == "%s\n" && CI->getNumArgOperands() > 1 &&
1711       CI->getArgOperand(1)->getType()->isPointerTy()) {
1712     return EmitPutS(CI->getArgOperand(1), B, TLI);
1713   }
1714   return nullptr;
1715 }
1716
1717 Value *LibCallSimplifier::optimizePrintF(CallInst *CI, IRBuilder<> &B) {
1718
1719   Function *Callee = CI->getCalledFunction();
1720   // Require one fixed pointer argument and an integer/void result.
1721   FunctionType *FT = Callee->getFunctionType();
1722   if (FT->getNumParams() < 1 || !FT->getParamType(0)->isPointerTy() ||
1723       !(FT->getReturnType()->isIntegerTy() || FT->getReturnType()->isVoidTy()))
1724     return nullptr;
1725
1726   if (Value *V = optimizePrintFString(CI, B)) {
1727     return V;
1728   }
1729
1730   // printf(format, ...) -> iprintf(format, ...) if no floating point
1731   // arguments.
1732   if (TLI->has(LibFunc::iprintf) && !callHasFloatingPointArgument(CI)) {
1733     Module *M = B.GetInsertBlock()->getParent()->getParent();
1734     Constant *IPrintFFn =
1735         M->getOrInsertFunction("iprintf", FT, Callee->getAttributes());
1736     CallInst *New = cast<CallInst>(CI->clone());
1737     New->setCalledFunction(IPrintFFn);
1738     B.Insert(New);
1739     return New;
1740   }
1741   return nullptr;
1742 }
1743
1744 Value *LibCallSimplifier::optimizeSPrintFString(CallInst *CI, IRBuilder<> &B) {
1745   // Check for a fixed format string.
1746   StringRef FormatStr;
1747   if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr))
1748     return nullptr;
1749
1750   // If we just have a format string (nothing else crazy) transform it.
1751   if (CI->getNumArgOperands() == 2) {
1752     // Make sure there's no % in the constant array.  We could try to handle
1753     // %% -> % in the future if we cared.
1754     for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1755       if (FormatStr[i] == '%')
1756         return nullptr; // we found a format specifier, bail out.
1757
1758     // sprintf(str, fmt) -> llvm.memcpy(str, fmt, strlen(fmt)+1, 1)
1759     B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
1760                    ConstantInt::get(DL.getIntPtrType(CI->getContext()),
1761                                     FormatStr.size() + 1),
1762                    1, 1); // Copy the null byte.
1763     return ConstantInt::get(CI->getType(), FormatStr.size());
1764   }
1765
1766   // The remaining optimizations require the format string to be "%s" or "%c"
1767   // and have an extra operand.
1768   if (FormatStr.size() != 2 || FormatStr[0] != '%' ||
1769       CI->getNumArgOperands() < 3)
1770     return nullptr;
1771
1772   // Decode the second character of the format string.
1773   if (FormatStr[1] == 'c') {
1774     // sprintf(dst, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0
1775     if (!CI->getArgOperand(2)->getType()->isIntegerTy())
1776       return nullptr;
1777     Value *V = B.CreateTrunc(CI->getArgOperand(2), B.getInt8Ty(), "char");
1778     Value *Ptr = CastToCStr(CI->getArgOperand(0), B);
1779     B.CreateStore(V, Ptr);
1780     Ptr = B.CreateGEP(B.getInt8Ty(), Ptr, B.getInt32(1), "nul");
1781     B.CreateStore(B.getInt8(0), Ptr);
1782
1783     return ConstantInt::get(CI->getType(), 1);
1784   }
1785
1786   if (FormatStr[1] == 's') {
1787     // sprintf(dest, "%s", str) -> llvm.memcpy(dest, str, strlen(str)+1, 1)
1788     if (!CI->getArgOperand(2)->getType()->isPointerTy())
1789       return nullptr;
1790
1791     Value *Len = EmitStrLen(CI->getArgOperand(2), B, DL, TLI);
1792     if (!Len)
1793       return nullptr;
1794     Value *IncLen =
1795         B.CreateAdd(Len, ConstantInt::get(Len->getType(), 1), "leninc");
1796     B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(2), IncLen, 1, 1);
1797
1798     // The sprintf result is the unincremented number of bytes in the string.
1799     return B.CreateIntCast(Len, CI->getType(), false);
1800   }
1801   return nullptr;
1802 }
1803
1804 Value *LibCallSimplifier::optimizeSPrintF(CallInst *CI, IRBuilder<> &B) {
1805   Function *Callee = CI->getCalledFunction();
1806   // Require two fixed pointer arguments and an integer result.
1807   FunctionType *FT = Callee->getFunctionType();
1808   if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
1809       !FT->getParamType(1)->isPointerTy() ||
1810       !FT->getReturnType()->isIntegerTy())
1811     return nullptr;
1812
1813   if (Value *V = optimizeSPrintFString(CI, B)) {
1814     return V;
1815   }
1816
1817   // sprintf(str, format, ...) -> siprintf(str, format, ...) if no floating
1818   // point arguments.
1819   if (TLI->has(LibFunc::siprintf) && !callHasFloatingPointArgument(CI)) {
1820     Module *M = B.GetInsertBlock()->getParent()->getParent();
1821     Constant *SIPrintFFn =
1822         M->getOrInsertFunction("siprintf", FT, Callee->getAttributes());
1823     CallInst *New = cast<CallInst>(CI->clone());
1824     New->setCalledFunction(SIPrintFFn);
1825     B.Insert(New);
1826     return New;
1827   }
1828   return nullptr;
1829 }
1830
1831 Value *LibCallSimplifier::optimizeFPrintFString(CallInst *CI, IRBuilder<> &B) {
1832   optimizeErrorReporting(CI, B, 0);
1833
1834   // All the optimizations depend on the format string.
1835   StringRef FormatStr;
1836   if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr))
1837     return nullptr;
1838
1839   // Do not do any of the following transformations if the fprintf return
1840   // value is used, in general the fprintf return value is not compatible
1841   // with fwrite(), fputc() or fputs().
1842   if (!CI->use_empty())
1843     return nullptr;
1844
1845   // fprintf(F, "foo") --> fwrite("foo", 3, 1, F)
1846   if (CI->getNumArgOperands() == 2) {
1847     for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1848       if (FormatStr[i] == '%') // Could handle %% -> % if we cared.
1849         return nullptr;        // We found a format specifier.
1850
1851     return EmitFWrite(
1852         CI->getArgOperand(1),
1853         ConstantInt::get(DL.getIntPtrType(CI->getContext()), FormatStr.size()),
1854         CI->getArgOperand(0), B, DL, TLI);
1855   }
1856
1857   // The remaining optimizations require the format string to be "%s" or "%c"
1858   // and have an extra operand.
1859   if (FormatStr.size() != 2 || FormatStr[0] != '%' ||
1860       CI->getNumArgOperands() < 3)
1861     return nullptr;
1862
1863   // Decode the second character of the format string.
1864   if (FormatStr[1] == 'c') {
1865     // fprintf(F, "%c", chr) --> fputc(chr, F)
1866     if (!CI->getArgOperand(2)->getType()->isIntegerTy())
1867       return nullptr;
1868     return EmitFPutC(CI->getArgOperand(2), CI->getArgOperand(0), B, TLI);
1869   }
1870
1871   if (FormatStr[1] == 's') {
1872     // fprintf(F, "%s", str) --> fputs(str, F)
1873     if (!CI->getArgOperand(2)->getType()->isPointerTy())
1874       return nullptr;
1875     return EmitFPutS(CI->getArgOperand(2), CI->getArgOperand(0), B, TLI);
1876   }
1877   return nullptr;
1878 }
1879
1880 Value *LibCallSimplifier::optimizeFPrintF(CallInst *CI, IRBuilder<> &B) {
1881   Function *Callee = CI->getCalledFunction();
1882   // Require two fixed paramters as pointers and integer result.
1883   FunctionType *FT = Callee->getFunctionType();
1884   if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
1885       !FT->getParamType(1)->isPointerTy() ||
1886       !FT->getReturnType()->isIntegerTy())
1887     return nullptr;
1888
1889   if (Value *V = optimizeFPrintFString(CI, B)) {
1890     return V;
1891   }
1892
1893   // fprintf(stream, format, ...) -> fiprintf(stream, format, ...) if no
1894   // floating point arguments.
1895   if (TLI->has(LibFunc::fiprintf) && !callHasFloatingPointArgument(CI)) {
1896     Module *M = B.GetInsertBlock()->getParent()->getParent();
1897     Constant *FIPrintFFn =
1898         M->getOrInsertFunction("fiprintf", FT, Callee->getAttributes());
1899     CallInst *New = cast<CallInst>(CI->clone());
1900     New->setCalledFunction(FIPrintFFn);
1901     B.Insert(New);
1902     return New;
1903   }
1904   return nullptr;
1905 }
1906
1907 Value *LibCallSimplifier::optimizeFWrite(CallInst *CI, IRBuilder<> &B) {
1908   optimizeErrorReporting(CI, B, 3);
1909
1910   Function *Callee = CI->getCalledFunction();
1911   // Require a pointer, an integer, an integer, a pointer, returning integer.
1912   FunctionType *FT = Callee->getFunctionType();
1913   if (FT->getNumParams() != 4 || !FT->getParamType(0)->isPointerTy() ||
1914       !FT->getParamType(1)->isIntegerTy() ||
1915       !FT->getParamType(2)->isIntegerTy() ||
1916       !FT->getParamType(3)->isPointerTy() ||
1917       !FT->getReturnType()->isIntegerTy())
1918     return nullptr;
1919
1920   // Get the element size and count.
1921   ConstantInt *SizeC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
1922   ConstantInt *CountC = dyn_cast<ConstantInt>(CI->getArgOperand(2));
1923   if (!SizeC || !CountC)
1924     return nullptr;
1925   uint64_t Bytes = SizeC->getZExtValue() * CountC->getZExtValue();
1926
1927   // If this is writing zero records, remove the call (it's a noop).
1928   if (Bytes == 0)
1929     return ConstantInt::get(CI->getType(), 0);
1930
1931   // If this is writing one byte, turn it into fputc.
1932   // This optimisation is only valid, if the return value is unused.
1933   if (Bytes == 1 && CI->use_empty()) { // fwrite(S,1,1,F) -> fputc(S[0],F)
1934     Value *Char = B.CreateLoad(CastToCStr(CI->getArgOperand(0), B), "char");
1935     Value *NewCI = EmitFPutC(Char, CI->getArgOperand(3), B, TLI);
1936     return NewCI ? ConstantInt::get(CI->getType(), 1) : nullptr;
1937   }
1938
1939   return nullptr;
1940 }
1941
1942 Value *LibCallSimplifier::optimizeFPuts(CallInst *CI, IRBuilder<> &B) {
1943   optimizeErrorReporting(CI, B, 1);
1944
1945   Function *Callee = CI->getCalledFunction();
1946
1947   // Require two pointers.  Also, we can't optimize if return value is used.
1948   FunctionType *FT = Callee->getFunctionType();
1949   if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
1950       !FT->getParamType(1)->isPointerTy() || !CI->use_empty())
1951     return nullptr;
1952
1953   // fputs(s,F) --> fwrite(s,1,strlen(s),F)
1954   uint64_t Len = GetStringLength(CI->getArgOperand(0));
1955   if (!Len)
1956     return nullptr;
1957
1958   // Known to have no uses (see above).
1959   return EmitFWrite(
1960       CI->getArgOperand(0),
1961       ConstantInt::get(DL.getIntPtrType(CI->getContext()), Len - 1),
1962       CI->getArgOperand(1), B, DL, TLI);
1963 }
1964
1965 Value *LibCallSimplifier::optimizePuts(CallInst *CI, IRBuilder<> &B) {
1966   Function *Callee = CI->getCalledFunction();
1967   // Require one fixed pointer argument and an integer/void result.
1968   FunctionType *FT = Callee->getFunctionType();
1969   if (FT->getNumParams() < 1 || !FT->getParamType(0)->isPointerTy() ||
1970       !(FT->getReturnType()->isIntegerTy() || FT->getReturnType()->isVoidTy()))
1971     return nullptr;
1972
1973   // Check for a constant string.
1974   StringRef Str;
1975   if (!getConstantStringInfo(CI->getArgOperand(0), Str))
1976     return nullptr;
1977
1978   if (Str.empty() && CI->use_empty()) {
1979     // puts("") -> putchar('\n')
1980     Value *Res = EmitPutChar(B.getInt32('\n'), B, TLI);
1981     if (CI->use_empty() || !Res)
1982       return Res;
1983     return B.CreateIntCast(Res, CI->getType(), true);
1984   }
1985
1986   return nullptr;
1987 }
1988
1989 bool LibCallSimplifier::hasFloatVersion(StringRef FuncName) {
1990   LibFunc::Func Func;
1991   SmallString<20> FloatFuncName = FuncName;
1992   FloatFuncName += 'f';
1993   if (TLI->getLibFunc(FloatFuncName, Func))
1994     return TLI->has(Func);
1995   return false;
1996 }
1997
1998 Value *LibCallSimplifier::optimizeStringMemoryLibCall(CallInst *CI,
1999                                                       IRBuilder<> &Builder) {
2000   LibFunc::Func Func;
2001   Function *Callee = CI->getCalledFunction();
2002   StringRef FuncName = Callee->getName();
2003
2004   // Check for string/memory library functions.
2005   if (TLI->getLibFunc(FuncName, Func) && TLI->has(Func)) {
2006     // Make sure we never change the calling convention.
2007     assert((ignoreCallingConv(Func) ||
2008             CI->getCallingConv() == llvm::CallingConv::C) &&
2009       "Optimizing string/memory libcall would change the calling convention");
2010     switch (Func) {
2011     case LibFunc::strcat:
2012       return optimizeStrCat(CI, Builder);
2013     case LibFunc::strncat:
2014       return optimizeStrNCat(CI, Builder);
2015     case LibFunc::strchr:
2016       return optimizeStrChr(CI, Builder);
2017     case LibFunc::strrchr:
2018       return optimizeStrRChr(CI, Builder);
2019     case LibFunc::strcmp:
2020       return optimizeStrCmp(CI, Builder);
2021     case LibFunc::strncmp:
2022       return optimizeStrNCmp(CI, Builder);
2023     case LibFunc::strcpy:
2024       return optimizeStrCpy(CI, Builder);
2025     case LibFunc::stpcpy:
2026       return optimizeStpCpy(CI, Builder);
2027     case LibFunc::strncpy:
2028       return optimizeStrNCpy(CI, Builder);
2029     case LibFunc::strlen:
2030       return optimizeStrLen(CI, Builder);
2031     case LibFunc::strpbrk:
2032       return optimizeStrPBrk(CI, Builder);
2033     case LibFunc::strtol:
2034     case LibFunc::strtod:
2035     case LibFunc::strtof:
2036     case LibFunc::strtoul:
2037     case LibFunc::strtoll:
2038     case LibFunc::strtold:
2039     case LibFunc::strtoull:
2040       return optimizeStrTo(CI, Builder);
2041     case LibFunc::strspn:
2042       return optimizeStrSpn(CI, Builder);
2043     case LibFunc::strcspn:
2044       return optimizeStrCSpn(CI, Builder);
2045     case LibFunc::strstr:
2046       return optimizeStrStr(CI, Builder);
2047     case LibFunc::memchr:
2048       return optimizeMemChr(CI, Builder);
2049     case LibFunc::memcmp:
2050       return optimizeMemCmp(CI, Builder);
2051     case LibFunc::memcpy:
2052       return optimizeMemCpy(CI, Builder);
2053     case LibFunc::memmove:
2054       return optimizeMemMove(CI, Builder);
2055     case LibFunc::memset:
2056       return optimizeMemSet(CI, Builder);
2057     default:
2058       break;
2059     }
2060   }
2061   return nullptr;
2062 }
2063
2064 Value *LibCallSimplifier::optimizeCall(CallInst *CI) {
2065   if (CI->isNoBuiltin())
2066     return nullptr;
2067
2068   LibFunc::Func Func;
2069   Function *Callee = CI->getCalledFunction();
2070   StringRef FuncName = Callee->getName();
2071   IRBuilder<> Builder(CI);
2072   bool isCallingConvC = CI->getCallingConv() == llvm::CallingConv::C;
2073
2074   // Command-line parameter overrides function attribute.
2075   if (EnableUnsafeFPShrink.getNumOccurrences() > 0)
2076     UnsafeFPShrink = EnableUnsafeFPShrink;
2077   else if (canUseUnsafeFPMath(Callee))
2078     UnsafeFPShrink = true;
2079
2080   // First, check for intrinsics.
2081   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI)) {
2082     if (!isCallingConvC)
2083       return nullptr;
2084     switch (II->getIntrinsicID()) {
2085     case Intrinsic::pow:
2086       return optimizePow(CI, Builder);
2087     case Intrinsic::exp2:
2088       return optimizeExp2(CI, Builder);
2089     case Intrinsic::fabs:
2090       return optimizeFabs(CI, Builder);
2091     case Intrinsic::sqrt:
2092       return optimizeSqrt(CI, Builder);
2093     default:
2094       return nullptr;
2095     }
2096   }
2097
2098   // Also try to simplify calls to fortified library functions.
2099   if (Value *SimplifiedFortifiedCI = FortifiedSimplifier.optimizeCall(CI)) {
2100     // Try to further simplify the result.
2101     CallInst *SimplifiedCI = dyn_cast<CallInst>(SimplifiedFortifiedCI);
2102     if (SimplifiedCI && SimplifiedCI->getCalledFunction()) {
2103       // Use an IR Builder from SimplifiedCI if available instead of CI
2104       // to guarantee we reach all uses we might replace later on.
2105       IRBuilder<> TmpBuilder(SimplifiedCI);
2106       if (Value *V = optimizeStringMemoryLibCall(SimplifiedCI, TmpBuilder)) {
2107         // If we were able to further simplify, remove the now redundant call.
2108         SimplifiedCI->replaceAllUsesWith(V);
2109         SimplifiedCI->eraseFromParent();
2110         return V;
2111       }
2112     }
2113     return SimplifiedFortifiedCI;
2114   }
2115
2116   // Then check for known library functions.
2117   if (TLI->getLibFunc(FuncName, Func) && TLI->has(Func)) {
2118     // We never change the calling convention.
2119     if (!ignoreCallingConv(Func) && !isCallingConvC)
2120       return nullptr;
2121     if (Value *V = optimizeStringMemoryLibCall(CI, Builder))
2122       return V;
2123     switch (Func) {
2124     case LibFunc::cosf:
2125     case LibFunc::cos:
2126     case LibFunc::cosl:
2127       return optimizeCos(CI, Builder);
2128     case LibFunc::sinpif:
2129     case LibFunc::sinpi:
2130     case LibFunc::cospif:
2131     case LibFunc::cospi:
2132       return optimizeSinCosPi(CI, Builder);
2133     case LibFunc::powf:
2134     case LibFunc::pow:
2135     case LibFunc::powl:
2136       return optimizePow(CI, Builder);
2137     case LibFunc::exp2l:
2138     case LibFunc::exp2:
2139     case LibFunc::exp2f:
2140       return optimizeExp2(CI, Builder);
2141     case LibFunc::fabsf:
2142     case LibFunc::fabs:
2143     case LibFunc::fabsl:
2144       return optimizeFabs(CI, Builder);
2145     case LibFunc::sqrtf:
2146     case LibFunc::sqrt:
2147     case LibFunc::sqrtl:
2148       return optimizeSqrt(CI, Builder);
2149     case LibFunc::ffs:
2150     case LibFunc::ffsl:
2151     case LibFunc::ffsll:
2152       return optimizeFFS(CI, Builder);
2153     case LibFunc::abs:
2154     case LibFunc::labs:
2155     case LibFunc::llabs:
2156       return optimizeAbs(CI, Builder);
2157     case LibFunc::isdigit:
2158       return optimizeIsDigit(CI, Builder);
2159     case LibFunc::isascii:
2160       return optimizeIsAscii(CI, Builder);
2161     case LibFunc::toascii:
2162       return optimizeToAscii(CI, Builder);
2163     case LibFunc::printf:
2164       return optimizePrintF(CI, Builder);
2165     case LibFunc::sprintf:
2166       return optimizeSPrintF(CI, Builder);
2167     case LibFunc::fprintf:
2168       return optimizeFPrintF(CI, Builder);
2169     case LibFunc::fwrite:
2170       return optimizeFWrite(CI, Builder);
2171     case LibFunc::fputs:
2172       return optimizeFPuts(CI, Builder);
2173     case LibFunc::puts:
2174       return optimizePuts(CI, Builder);
2175     case LibFunc::tan:
2176     case LibFunc::tanf:
2177     case LibFunc::tanl:
2178       return optimizeTan(CI, Builder);
2179     case LibFunc::perror:
2180       return optimizeErrorReporting(CI, Builder);
2181     case LibFunc::vfprintf:
2182     case LibFunc::fiprintf:
2183       return optimizeErrorReporting(CI, Builder, 0);
2184     case LibFunc::fputc:
2185       return optimizeErrorReporting(CI, Builder, 1);
2186     case LibFunc::ceil:
2187     case LibFunc::floor:
2188     case LibFunc::rint:
2189     case LibFunc::round:
2190     case LibFunc::nearbyint:
2191     case LibFunc::trunc:
2192       if (hasFloatVersion(FuncName))
2193         return optimizeUnaryDoubleFP(CI, Builder, false);
2194       return nullptr;
2195     case LibFunc::acos:
2196     case LibFunc::acosh:
2197     case LibFunc::asin:
2198     case LibFunc::asinh:
2199     case LibFunc::atan:
2200     case LibFunc::atanh:
2201     case LibFunc::cbrt:
2202     case LibFunc::cosh:
2203     case LibFunc::exp:
2204     case LibFunc::exp10:
2205     case LibFunc::expm1:
2206     case LibFunc::log:
2207     case LibFunc::log10:
2208     case LibFunc::log1p:
2209     case LibFunc::log2:
2210     case LibFunc::logb:
2211     case LibFunc::sin:
2212     case LibFunc::sinh:
2213     case LibFunc::tanh:
2214       if (UnsafeFPShrink && hasFloatVersion(FuncName))
2215         return optimizeUnaryDoubleFP(CI, Builder, true);
2216       return nullptr;
2217     case LibFunc::copysign:
2218       if (hasFloatVersion(FuncName))
2219         return optimizeBinaryDoubleFP(CI, Builder);
2220       return nullptr;
2221     case LibFunc::fminf:
2222     case LibFunc::fmin:
2223     case LibFunc::fminl:
2224     case LibFunc::fmaxf:
2225     case LibFunc::fmax:
2226     case LibFunc::fmaxl:
2227       return optimizeFMinFMax(CI, Builder);
2228     default:
2229       return nullptr;
2230     }
2231   }
2232   return nullptr;
2233 }
2234
2235 LibCallSimplifier::LibCallSimplifier(
2236     const DataLayout &DL, const TargetLibraryInfo *TLI,
2237     function_ref<void(Instruction *, Value *)> Replacer)
2238     : FortifiedSimplifier(TLI), DL(DL), TLI(TLI), UnsafeFPShrink(false),
2239       Replacer(Replacer) {}
2240
2241 void LibCallSimplifier::replaceAllUsesWith(Instruction *I, Value *With) {
2242   // Indirect through the replacer used in this instance.
2243   Replacer(I, With);
2244 }
2245
2246 // TODO:
2247 //   Additional cases that we need to add to this file:
2248 //
2249 // cbrt:
2250 //   * cbrt(expN(X))  -> expN(x/3)
2251 //   * cbrt(sqrt(x))  -> pow(x,1/6)
2252 //   * cbrt(cbrt(x))  -> pow(x,1/9)
2253 //
2254 // exp, expf, expl:
2255 //   * exp(log(x))  -> x
2256 //
2257 // log, logf, logl:
2258 //   * log(exp(x))   -> x
2259 //   * log(x**y)     -> y*log(x)
2260 //   * log(exp(y))   -> y*log(e)
2261 //   * log(exp2(y))  -> y*log(2)
2262 //   * log(exp10(y)) -> y*log(10)
2263 //   * log(sqrt(x))  -> 0.5*log(x)
2264 //   * log(pow(x,y)) -> y*log(x)
2265 //
2266 // lround, lroundf, lroundl:
2267 //   * lround(cnst) -> cnst'
2268 //
2269 // pow, powf, powl:
2270 //   * pow(exp(x),y)  -> exp(x*y)
2271 //   * pow(sqrt(x),y) -> pow(x,y*0.5)
2272 //   * pow(pow(x,y),z)-> pow(x,y*z)
2273 //
2274 // round, roundf, roundl:
2275 //   * round(cnst) -> cnst'
2276 //
2277 // signbit:
2278 //   * signbit(cnst) -> cnst'
2279 //   * signbit(nncst) -> 0 (if pstv is a non-negative constant)
2280 //
2281 // sqrt, sqrtf, sqrtl:
2282 //   * sqrt(expN(x))  -> expN(x*0.5)
2283 //   * sqrt(Nroot(x)) -> pow(x,1/(2*N))
2284 //   * sqrt(pow(x,y)) -> pow(|x|,y*0.5)
2285 //
2286 // tan, tanf, tanl:
2287 //   * tan(atan(x)) -> x
2288 //
2289 // trunc, truncf, truncl:
2290 //   * trunc(cnst) -> cnst'
2291 //
2292 //
2293
2294 //===----------------------------------------------------------------------===//
2295 // Fortified Library Call Optimizations
2296 //===----------------------------------------------------------------------===//
2297
2298 bool FortifiedLibCallSimplifier::isFortifiedCallFoldable(CallInst *CI,
2299                                                          unsigned ObjSizeOp,
2300                                                          unsigned SizeOp,
2301                                                          bool isString) {
2302   if (CI->getArgOperand(ObjSizeOp) == CI->getArgOperand(SizeOp))
2303     return true;
2304   if (ConstantInt *ObjSizeCI =
2305           dyn_cast<ConstantInt>(CI->getArgOperand(ObjSizeOp))) {
2306     if (ObjSizeCI->isAllOnesValue())
2307       return true;
2308     // If the object size wasn't -1 (unknown), bail out if we were asked to.
2309     if (OnlyLowerUnknownSize)
2310       return false;
2311     if (isString) {
2312       uint64_t Len = GetStringLength(CI->getArgOperand(SizeOp));
2313       // If the length is 0 we don't know how long it is and so we can't
2314       // remove the check.
2315       if (Len == 0)
2316         return false;
2317       return ObjSizeCI->getZExtValue() >= Len;
2318     }
2319     if (ConstantInt *SizeCI = dyn_cast<ConstantInt>(CI->getArgOperand(SizeOp)))
2320       return ObjSizeCI->getZExtValue() >= SizeCI->getZExtValue();
2321   }
2322   return false;
2323 }
2324
2325 Value *FortifiedLibCallSimplifier::optimizeMemCpyChk(CallInst *CI, IRBuilder<> &B) {
2326   Function *Callee = CI->getCalledFunction();
2327
2328   if (!checkStringCopyLibFuncSignature(Callee, LibFunc::memcpy_chk))
2329     return nullptr;
2330
2331   if (isFortifiedCallFoldable(CI, 3, 2, false)) {
2332     B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
2333                    CI->getArgOperand(2), 1, 1);
2334     return CI->getArgOperand(0);
2335   }
2336   return nullptr;
2337 }
2338
2339 Value *FortifiedLibCallSimplifier::optimizeMemMoveChk(CallInst *CI, IRBuilder<> &B) {
2340   Function *Callee = CI->getCalledFunction();
2341
2342   if (!checkStringCopyLibFuncSignature(Callee, LibFunc::memmove_chk))
2343     return nullptr;
2344
2345   if (isFortifiedCallFoldable(CI, 3, 2, false)) {
2346     B.CreateMemMove(CI->getArgOperand(0), CI->getArgOperand(1),
2347                     CI->getArgOperand(2), 1, 1);
2348     return CI->getArgOperand(0);
2349   }
2350   return nullptr;
2351 }
2352
2353 Value *FortifiedLibCallSimplifier::optimizeMemSetChk(CallInst *CI, IRBuilder<> &B) {
2354   Function *Callee = CI->getCalledFunction();
2355
2356   if (!checkStringCopyLibFuncSignature(Callee, LibFunc::memset_chk))
2357     return nullptr;
2358
2359   if (isFortifiedCallFoldable(CI, 3, 2, false)) {
2360     Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(), false);
2361     B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1);
2362     return CI->getArgOperand(0);
2363   }
2364   return nullptr;
2365 }
2366
2367 Value *FortifiedLibCallSimplifier::optimizeStrpCpyChk(CallInst *CI,
2368                                                       IRBuilder<> &B,
2369                                                       LibFunc::Func Func) {
2370   Function *Callee = CI->getCalledFunction();
2371   StringRef Name = Callee->getName();
2372   const DataLayout &DL = CI->getModule()->getDataLayout();
2373
2374   if (!checkStringCopyLibFuncSignature(Callee, Func))
2375     return nullptr;
2376
2377   Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1),
2378         *ObjSize = CI->getArgOperand(2);
2379
2380   // __stpcpy_chk(x,x,...)  -> x+strlen(x)
2381   if (Func == LibFunc::stpcpy_chk && !OnlyLowerUnknownSize && Dst == Src) {
2382     Value *StrLen = EmitStrLen(Src, B, DL, TLI);
2383     return StrLen ? B.CreateInBoundsGEP(B.getInt8Ty(), Dst, StrLen) : nullptr;
2384   }
2385
2386   // If a) we don't have any length information, or b) we know this will
2387   // fit then just lower to a plain st[rp]cpy. Otherwise we'll keep our
2388   // st[rp]cpy_chk call which may fail at runtime if the size is too long.
2389   // TODO: It might be nice to get a maximum length out of the possible
2390   // string lengths for varying.
2391   if (isFortifiedCallFoldable(CI, 2, 1, true))
2392     return EmitStrCpy(Dst, Src, B, TLI, Name.substr(2, 6));
2393
2394   if (OnlyLowerUnknownSize)
2395     return nullptr;
2396
2397   // Maybe we can stil fold __st[rp]cpy_chk to __memcpy_chk.
2398   uint64_t Len = GetStringLength(Src);
2399   if (Len == 0)
2400     return nullptr;
2401
2402   Type *SizeTTy = DL.getIntPtrType(CI->getContext());
2403   Value *LenV = ConstantInt::get(SizeTTy, Len);
2404   Value *Ret = EmitMemCpyChk(Dst, Src, LenV, ObjSize, B, DL, TLI);
2405   // If the function was an __stpcpy_chk, and we were able to fold it into
2406   // a __memcpy_chk, we still need to return the correct end pointer.
2407   if (Ret && Func == LibFunc::stpcpy_chk)
2408     return B.CreateGEP(B.getInt8Ty(), Dst, ConstantInt::get(SizeTTy, Len - 1));
2409   return Ret;
2410 }
2411
2412 Value *FortifiedLibCallSimplifier::optimizeStrpNCpyChk(CallInst *CI,
2413                                                        IRBuilder<> &B,
2414                                                        LibFunc::Func Func) {
2415   Function *Callee = CI->getCalledFunction();
2416   StringRef Name = Callee->getName();
2417
2418   if (!checkStringCopyLibFuncSignature(Callee, Func))
2419     return nullptr;
2420   if (isFortifiedCallFoldable(CI, 3, 2, false)) {
2421     Value *Ret = EmitStrNCpy(CI->getArgOperand(0), CI->getArgOperand(1),
2422                              CI->getArgOperand(2), B, TLI, Name.substr(2, 7));
2423     return Ret;
2424   }
2425   return nullptr;
2426 }
2427
2428 Value *FortifiedLibCallSimplifier::optimizeCall(CallInst *CI) {
2429   // FIXME: We shouldn't be changing "nobuiltin" or TLI unavailable calls here.
2430   // Some clang users checked for _chk libcall availability using:
2431   //   __has_builtin(__builtin___memcpy_chk)
2432   // When compiling with -fno-builtin, this is always true.
2433   // When passing -ffreestanding/-mkernel, which both imply -fno-builtin, we
2434   // end up with fortified libcalls, which isn't acceptable in a freestanding
2435   // environment which only provides their non-fortified counterparts.
2436   //
2437   // Until we change clang and/or teach external users to check for availability
2438   // differently, disregard the "nobuiltin" attribute and TLI::has.
2439   //
2440   // PR23093.
2441
2442   LibFunc::Func Func;
2443   Function *Callee = CI->getCalledFunction();
2444   StringRef FuncName = Callee->getName();
2445   IRBuilder<> Builder(CI);
2446   bool isCallingConvC = CI->getCallingConv() == llvm::CallingConv::C;
2447
2448   // First, check that this is a known library functions.
2449   if (!TLI->getLibFunc(FuncName, Func))
2450     return nullptr;
2451
2452   // We never change the calling convention.
2453   if (!ignoreCallingConv(Func) && !isCallingConvC)
2454     return nullptr;
2455
2456   switch (Func) {
2457   case LibFunc::memcpy_chk:
2458     return optimizeMemCpyChk(CI, Builder);
2459   case LibFunc::memmove_chk:
2460     return optimizeMemMoveChk(CI, Builder);
2461   case LibFunc::memset_chk:
2462     return optimizeMemSetChk(CI, Builder);
2463   case LibFunc::stpcpy_chk:
2464   case LibFunc::strcpy_chk:
2465     return optimizeStrpCpyChk(CI, Builder, Func);
2466   case LibFunc::stpncpy_chk:
2467   case LibFunc::strncpy_chk:
2468     return optimizeStrpNCpyChk(CI, Builder, Func);
2469   default:
2470     break;
2471   }
2472   return nullptr;
2473 }
2474
2475 FortifiedLibCallSimplifier::FortifiedLibCallSimplifier(
2476     const TargetLibraryInfo *TLI, bool OnlyLowerUnknownSize)
2477     : TLI(TLI), OnlyLowerUnknownSize(OnlyLowerUnknownSize) {}