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