1 //===------ SimplifyLibCalls.cpp - Library calls simplifier ---------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
15 //===----------------------------------------------------------------------===//
17 #include "llvm/Transforms/Utils/SimplifyLibCalls.h"
18 #include "llvm/DataLayout.h"
19 #include "llvm/ADT/StringMap.h"
20 #include "llvm/Analysis/ValueTracking.h"
21 #include "llvm/Function.h"
22 #include "llvm/IRBuilder.h"
23 #include "llvm/Intrinsics.h"
24 #include "llvm/Module.h"
25 #include "llvm/LLVMContext.h"
26 #include "llvm/Target/TargetLibraryInfo.h"
27 #include "llvm/Transforms/Utils/BuildLibCalls.h"
31 /// This class is the abstract base class for the set of optimizations that
32 /// corresponds to one library call.
34 class LibCallOptimization {
38 const TargetLibraryInfo *TLI;
39 const LibCallSimplifier *LCS;
42 LibCallOptimization() { }
43 virtual ~LibCallOptimization() {}
45 /// callOptimizer - This pure virtual method is implemented by base classes to
46 /// do various optimizations. If this returns null then no transformation was
47 /// performed. If it returns CI, then it transformed the call and CI is to be
48 /// deleted. If it returns something else, replace CI with the new value and
50 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B)
53 Value *optimizeCall(CallInst *CI, const DataLayout *TD,
54 const TargetLibraryInfo *TLI,
55 const LibCallSimplifier *LCS, IRBuilder<> &B) {
56 Caller = CI->getParent()->getParent();
60 if (CI->getCalledFunction())
61 Context = &CI->getCalledFunction()->getContext();
63 // We never change the calling convention.
64 if (CI->getCallingConv() != llvm::CallingConv::C)
67 return callOptimizer(CI->getCalledFunction(), CI, B);
71 //===----------------------------------------------------------------------===//
73 //===----------------------------------------------------------------------===//
75 /// isOnlyUsedInZeroEqualityComparison - Return true if it only matters that the
76 /// value is equal or not-equal to zero.
77 static bool isOnlyUsedInZeroEqualityComparison(Value *V) {
78 for (Value::use_iterator UI = V->use_begin(), E = V->use_end();
80 if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI))
82 if (Constant *C = dyn_cast<Constant>(IC->getOperand(1)))
85 // Unknown instruction.
91 /// isOnlyUsedInEqualityComparison - Return true if it is only used in equality
92 /// comparisons with With.
93 static bool isOnlyUsedInEqualityComparison(Value *V, Value *With) {
94 for (Value::use_iterator UI = V->use_begin(), E = V->use_end();
96 if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI))
97 if (IC->isEquality() && IC->getOperand(1) == With)
99 // Unknown instruction.
105 static bool callHasFloatingPointArgument(const CallInst *CI) {
106 for (CallInst::const_op_iterator it = CI->op_begin(), e = CI->op_end();
108 if ((*it)->getType()->isFloatingPointTy())
114 //===----------------------------------------------------------------------===//
115 // Fortified Library Call Optimizations
116 //===----------------------------------------------------------------------===//
118 struct FortifiedLibCallOptimization : public LibCallOptimization {
120 virtual bool isFoldable(unsigned SizeCIOp, unsigned SizeArgOp,
121 bool isString) const = 0;
124 struct InstFortifiedLibCallOptimization : public FortifiedLibCallOptimization {
127 bool isFoldable(unsigned SizeCIOp, unsigned SizeArgOp, bool isString) const {
128 if (CI->getArgOperand(SizeCIOp) == CI->getArgOperand(SizeArgOp))
130 if (ConstantInt *SizeCI =
131 dyn_cast<ConstantInt>(CI->getArgOperand(SizeCIOp))) {
132 if (SizeCI->isAllOnesValue())
135 uint64_t Len = GetStringLength(CI->getArgOperand(SizeArgOp));
136 // If the length is 0 we don't know how long it is and so we can't
138 if (Len == 0) return false;
139 return SizeCI->getZExtValue() >= Len;
141 if (ConstantInt *Arg = dyn_cast<ConstantInt>(
142 CI->getArgOperand(SizeArgOp)))
143 return SizeCI->getZExtValue() >= Arg->getZExtValue();
149 struct MemCpyChkOpt : public InstFortifiedLibCallOptimization {
150 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
152 FunctionType *FT = Callee->getFunctionType();
153 LLVMContext &Context = CI->getParent()->getContext();
155 // Check if this has the right signature.
156 if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
157 !FT->getParamType(0)->isPointerTy() ||
158 !FT->getParamType(1)->isPointerTy() ||
159 FT->getParamType(2) != TD->getIntPtrType(Context) ||
160 FT->getParamType(3) != TD->getIntPtrType(Context))
163 if (isFoldable(3, 2, false)) {
164 B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
165 CI->getArgOperand(2), 1);
166 return CI->getArgOperand(0);
172 struct MemMoveChkOpt : public InstFortifiedLibCallOptimization {
173 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
175 FunctionType *FT = Callee->getFunctionType();
176 LLVMContext &Context = CI->getParent()->getContext();
178 // Check if this has the right signature.
179 if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
180 !FT->getParamType(0)->isPointerTy() ||
181 !FT->getParamType(1)->isPointerTy() ||
182 FT->getParamType(2) != TD->getIntPtrType(Context) ||
183 FT->getParamType(3) != TD->getIntPtrType(Context))
186 if (isFoldable(3, 2, false)) {
187 B.CreateMemMove(CI->getArgOperand(0), CI->getArgOperand(1),
188 CI->getArgOperand(2), 1);
189 return CI->getArgOperand(0);
195 struct MemSetChkOpt : public InstFortifiedLibCallOptimization {
196 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
198 FunctionType *FT = Callee->getFunctionType();
199 LLVMContext &Context = CI->getParent()->getContext();
201 // Check if this has the right signature.
202 if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
203 !FT->getParamType(0)->isPointerTy() ||
204 !FT->getParamType(1)->isIntegerTy() ||
205 FT->getParamType(2) != TD->getIntPtrType(Context) ||
206 FT->getParamType(3) != TD->getIntPtrType(Context))
209 if (isFoldable(3, 2, false)) {
210 Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(),
212 B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1);
213 return CI->getArgOperand(0);
219 struct StrCpyChkOpt : public InstFortifiedLibCallOptimization {
220 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
222 StringRef Name = Callee->getName();
223 FunctionType *FT = Callee->getFunctionType();
224 LLVMContext &Context = CI->getParent()->getContext();
226 // Check if this has the right signature.
227 if (FT->getNumParams() != 3 ||
228 FT->getReturnType() != FT->getParamType(0) ||
229 FT->getParamType(0) != FT->getParamType(1) ||
230 FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
231 FT->getParamType(2) != TD->getIntPtrType(Context))
234 Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
235 if (Dst == Src) // __strcpy_chk(x,x) -> x
238 // If a) we don't have any length information, or b) we know this will
239 // fit then just lower to a plain strcpy. Otherwise we'll keep our
240 // strcpy_chk call which may fail at runtime if the size is too long.
241 // TODO: It might be nice to get a maximum length out of the possible
242 // string lengths for varying.
243 if (isFoldable(2, 1, true)) {
244 Value *Ret = EmitStrCpy(Dst, Src, B, TD, TLI, Name.substr(2, 6));
247 // Maybe we can stil fold __strcpy_chk to __memcpy_chk.
248 uint64_t Len = GetStringLength(Src);
249 if (Len == 0) return 0;
251 // This optimization require DataLayout.
255 EmitMemCpyChk(Dst, Src,
256 ConstantInt::get(TD->getIntPtrType(Context), Len),
257 CI->getArgOperand(2), B, TD, TLI);
264 struct StpCpyChkOpt : public InstFortifiedLibCallOptimization {
265 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
267 StringRef Name = Callee->getName();
268 FunctionType *FT = Callee->getFunctionType();
269 LLVMContext &Context = CI->getParent()->getContext();
271 // Check if this has the right signature.
272 if (FT->getNumParams() != 3 ||
273 FT->getReturnType() != FT->getParamType(0) ||
274 FT->getParamType(0) != FT->getParamType(1) ||
275 FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
276 FT->getParamType(2) != TD->getIntPtrType(FT->getParamType(0)))
279 Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
280 if (Dst == Src) { // stpcpy(x,x) -> x+strlen(x)
281 Value *StrLen = EmitStrLen(Src, B, TD, TLI);
282 return StrLen ? B.CreateInBoundsGEP(Dst, StrLen) : 0;
285 // If a) we don't have any length information, or b) we know this will
286 // fit then just lower to a plain stpcpy. Otherwise we'll keep our
287 // stpcpy_chk call which may fail at runtime if the size is too long.
288 // TODO: It might be nice to get a maximum length out of the possible
289 // string lengths for varying.
290 if (isFoldable(2, 1, true)) {
291 Value *Ret = EmitStrCpy(Dst, Src, B, TD, TLI, Name.substr(2, 6));
294 // Maybe we can stil fold __stpcpy_chk to __memcpy_chk.
295 uint64_t Len = GetStringLength(Src);
296 if (Len == 0) return 0;
298 // This optimization require DataLayout.
301 Type *PT = FT->getParamType(0);
302 Value *LenV = ConstantInt::get(TD->getIntPtrType(PT), Len);
303 Value *DstEnd = B.CreateGEP(Dst,
304 ConstantInt::get(TD->getIntPtrType(PT),
306 if (!EmitMemCpyChk(Dst, Src, LenV, CI->getArgOperand(2), B, TD, TLI))
314 struct StrNCpyChkOpt : public InstFortifiedLibCallOptimization {
315 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
317 StringRef Name = Callee->getName();
318 FunctionType *FT = Callee->getFunctionType();
319 LLVMContext &Context = CI->getParent()->getContext();
321 // Check if this has the right signature.
322 if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
323 FT->getParamType(0) != FT->getParamType(1) ||
324 FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
325 !FT->getParamType(2)->isIntegerTy() ||
326 FT->getParamType(3) != TD->getIntPtrType(Context))
329 if (isFoldable(3, 2, false)) {
330 Value *Ret = EmitStrNCpy(CI->getArgOperand(0), CI->getArgOperand(1),
331 CI->getArgOperand(2), B, TD, TLI,
339 //===----------------------------------------------------------------------===//
340 // String and Memory Library Call Optimizations
341 //===----------------------------------------------------------------------===//
343 struct StrCatOpt : public LibCallOptimization {
344 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
345 // Verify the "strcat" function prototype.
346 FunctionType *FT = Callee->getFunctionType();
347 if (FT->getNumParams() != 2 ||
348 FT->getReturnType() != B.getInt8PtrTy() ||
349 FT->getParamType(0) != FT->getReturnType() ||
350 FT->getParamType(1) != FT->getReturnType())
353 // Extract some information from the instruction
354 Value *Dst = CI->getArgOperand(0);
355 Value *Src = CI->getArgOperand(1);
357 // See if we can get the length of the input string.
358 uint64_t Len = GetStringLength(Src);
359 if (Len == 0) return 0;
360 --Len; // Unbias length.
362 // Handle the simple, do-nothing case: strcat(x, "") -> x
366 // These optimizations require DataLayout.
369 return emitStrLenMemCpy(Src, Dst, Len, B);
372 Value *emitStrLenMemCpy(Value *Src, Value *Dst, uint64_t Len,
374 // We need to find the end of the destination string. That's where the
375 // memory is to be moved to. We just generate a call to strlen.
376 Value *DstLen = EmitStrLen(Dst, B, TD, TLI);
380 // Now that we have the destination's length, we must index into the
381 // destination's pointer to get the actual memcpy destination (end of
382 // the string .. we're concatenating).
383 Value *CpyDst = B.CreateGEP(Dst, DstLen, "endptr");
385 // We have enough information to now generate the memcpy call to do the
386 // concatenation for us. Make a memcpy to copy the nul byte with align = 1.
387 B.CreateMemCpy(CpyDst, Src,
388 ConstantInt::get(TD->getIntPtrType(*Context), Len + 1), 1);
393 struct StrNCatOpt : public StrCatOpt {
394 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
395 // Verify the "strncat" function prototype.
396 FunctionType *FT = Callee->getFunctionType();
397 if (FT->getNumParams() != 3 ||
398 FT->getReturnType() != B.getInt8PtrTy() ||
399 FT->getParamType(0) != FT->getReturnType() ||
400 FT->getParamType(1) != FT->getReturnType() ||
401 !FT->getParamType(2)->isIntegerTy())
404 // Extract some information from the instruction
405 Value *Dst = CI->getArgOperand(0);
406 Value *Src = CI->getArgOperand(1);
409 // We don't do anything if length is not constant
410 if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
411 Len = LengthArg->getZExtValue();
415 // See if we can get the length of the input string.
416 uint64_t SrcLen = GetStringLength(Src);
417 if (SrcLen == 0) return 0;
418 --SrcLen; // Unbias length.
420 // Handle the simple, do-nothing cases:
421 // strncat(x, "", c) -> x
422 // strncat(x, c, 0) -> x
423 if (SrcLen == 0 || Len == 0) return Dst;
425 // These optimizations require DataLayout.
428 // We don't optimize this case
429 if (Len < SrcLen) return 0;
431 // strncat(x, s, c) -> strcat(x, s)
432 // s is constant so the strcat can be optimized further
433 return emitStrLenMemCpy(Src, Dst, SrcLen, B);
437 struct StrChrOpt : public LibCallOptimization {
438 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
439 // Verify the "strchr" function prototype.
440 FunctionType *FT = Callee->getFunctionType();
441 if (FT->getNumParams() != 2 ||
442 FT->getReturnType() != B.getInt8PtrTy() ||
443 FT->getParamType(0) != FT->getReturnType() ||
444 !FT->getParamType(1)->isIntegerTy(32))
447 Value *SrcStr = CI->getArgOperand(0);
449 // If the second operand is non-constant, see if we can compute the length
450 // of the input string and turn this into memchr.
451 ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
453 // These optimizations require DataLayout.
456 uint64_t Len = GetStringLength(SrcStr);
457 if (Len == 0 || !FT->getParamType(1)->isIntegerTy(32))// memchr needs i32.
460 return EmitMemChr(SrcStr, CI->getArgOperand(1), // include nul.
461 ConstantInt::get(TD->getIntPtrType(*Context), Len),
465 // Otherwise, the character is a constant, see if the first argument is
466 // a string literal. If so, we can constant fold.
468 if (!getConstantStringInfo(SrcStr, Str))
471 // Compute the offset, make sure to handle the case when we're searching for
472 // zero (a weird way to spell strlen).
473 size_t I = CharC->getSExtValue() == 0 ?
474 Str.size() : Str.find(CharC->getSExtValue());
475 if (I == StringRef::npos) // Didn't find the char. strchr returns null.
476 return Constant::getNullValue(CI->getType());
478 // strchr(s+n,c) -> gep(s+n+i,c)
479 return B.CreateGEP(SrcStr, B.getInt64(I), "strchr");
483 struct StrRChrOpt : public LibCallOptimization {
484 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
485 // Verify the "strrchr" function prototype.
486 FunctionType *FT = Callee->getFunctionType();
487 if (FT->getNumParams() != 2 ||
488 FT->getReturnType() != B.getInt8PtrTy() ||
489 FT->getParamType(0) != FT->getReturnType() ||
490 !FT->getParamType(1)->isIntegerTy(32))
493 Value *SrcStr = CI->getArgOperand(0);
494 ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
496 // Cannot fold anything if we're not looking for a constant.
501 if (!getConstantStringInfo(SrcStr, Str)) {
502 // strrchr(s, 0) -> strchr(s, 0)
503 if (TD && CharC->isZero())
504 return EmitStrChr(SrcStr, '\0', B, TD, TLI);
508 // Compute the offset.
509 size_t I = CharC->getSExtValue() == 0 ?
510 Str.size() : Str.rfind(CharC->getSExtValue());
511 if (I == StringRef::npos) // Didn't find the char. Return null.
512 return Constant::getNullValue(CI->getType());
514 // strrchr(s+n,c) -> gep(s+n+i,c)
515 return B.CreateGEP(SrcStr, B.getInt64(I), "strrchr");
519 struct StrCmpOpt : public LibCallOptimization {
520 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
521 // Verify the "strcmp" function prototype.
522 FunctionType *FT = Callee->getFunctionType();
523 if (FT->getNumParams() != 2 ||
524 !FT->getReturnType()->isIntegerTy(32) ||
525 FT->getParamType(0) != FT->getParamType(1) ||
526 FT->getParamType(0) != B.getInt8PtrTy())
529 Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
530 if (Str1P == Str2P) // strcmp(x,x) -> 0
531 return ConstantInt::get(CI->getType(), 0);
533 StringRef Str1, Str2;
534 bool HasStr1 = getConstantStringInfo(Str1P, Str1);
535 bool HasStr2 = getConstantStringInfo(Str2P, Str2);
537 // strcmp(x, y) -> cnst (if both x and y are constant strings)
538 if (HasStr1 && HasStr2)
539 return ConstantInt::get(CI->getType(), Str1.compare(Str2));
541 if (HasStr1 && Str1.empty()) // strcmp("", x) -> -*x
542 return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"),
545 if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x
546 return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
548 // strcmp(P, "x") -> memcmp(P, "x", 2)
549 uint64_t Len1 = GetStringLength(Str1P);
550 uint64_t Len2 = GetStringLength(Str2P);
552 // These optimizations require DataLayout.
555 return EmitMemCmp(Str1P, Str2P,
556 ConstantInt::get(TD->getIntPtrType(*Context),
557 std::min(Len1, Len2)), B, TD, TLI);
564 struct StrNCmpOpt : public LibCallOptimization {
565 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
566 // Verify the "strncmp" function prototype.
567 FunctionType *FT = Callee->getFunctionType();
568 if (FT->getNumParams() != 3 ||
569 !FT->getReturnType()->isIntegerTy(32) ||
570 FT->getParamType(0) != FT->getParamType(1) ||
571 FT->getParamType(0) != B.getInt8PtrTy() ||
572 !FT->getParamType(2)->isIntegerTy())
575 Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
576 if (Str1P == Str2P) // strncmp(x,x,n) -> 0
577 return ConstantInt::get(CI->getType(), 0);
579 // Get the length argument if it is constant.
581 if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
582 Length = LengthArg->getZExtValue();
586 if (Length == 0) // strncmp(x,y,0) -> 0
587 return ConstantInt::get(CI->getType(), 0);
589 if (TD && Length == 1) // strncmp(x,y,1) -> memcmp(x,y,1)
590 return EmitMemCmp(Str1P, Str2P, CI->getArgOperand(2), B, TD, TLI);
592 StringRef Str1, Str2;
593 bool HasStr1 = getConstantStringInfo(Str1P, Str1);
594 bool HasStr2 = getConstantStringInfo(Str2P, Str2);
596 // strncmp(x, y) -> cnst (if both x and y are constant strings)
597 if (HasStr1 && HasStr2) {
598 StringRef SubStr1 = Str1.substr(0, Length);
599 StringRef SubStr2 = Str2.substr(0, Length);
600 return ConstantInt::get(CI->getType(), SubStr1.compare(SubStr2));
603 if (HasStr1 && Str1.empty()) // strncmp("", x, n) -> -*x
604 return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"),
607 if (HasStr2 && Str2.empty()) // strncmp(x, "", n) -> *x
608 return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
614 struct StrCpyOpt : public LibCallOptimization {
615 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
616 // Verify the "strcpy" function prototype.
617 FunctionType *FT = Callee->getFunctionType();
618 if (FT->getNumParams() != 2 ||
619 FT->getReturnType() != FT->getParamType(0) ||
620 FT->getParamType(0) != FT->getParamType(1) ||
621 FT->getParamType(0) != B.getInt8PtrTy())
624 Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
625 if (Dst == Src) // strcpy(x,x) -> x
628 // These optimizations require DataLayout.
631 // See if we can get the length of the input string.
632 uint64_t Len = GetStringLength(Src);
633 if (Len == 0) return 0;
635 // We have enough information to now generate the memcpy call to do the
636 // copy for us. Make a memcpy to copy the nul byte with align = 1.
637 B.CreateMemCpy(Dst, Src,
638 ConstantInt::get(TD->getIntPtrType(*Context), Len), 1);
643 struct StpCpyOpt: public LibCallOptimization {
644 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
645 // Verify the "stpcpy" function prototype.
646 FunctionType *FT = Callee->getFunctionType();
647 if (FT->getNumParams() != 2 ||
648 FT->getReturnType() != FT->getParamType(0) ||
649 FT->getParamType(0) != FT->getParamType(1) ||
650 FT->getParamType(0) != B.getInt8PtrTy())
653 // These optimizations require DataLayout.
656 Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
657 if (Dst == Src) { // stpcpy(x,x) -> x+strlen(x)
658 Value *StrLen = EmitStrLen(Src, B, TD, TLI);
659 return StrLen ? B.CreateInBoundsGEP(Dst, StrLen) : 0;
662 // See if we can get the length of the input string.
663 uint64_t Len = GetStringLength(Src);
664 if (Len == 0) return 0;
666 Type *PT = FT->getParamType(0);
667 Value *LenV = ConstantInt::get(TD->getIntPtrType(PT), Len);
668 Value *DstEnd = B.CreateGEP(Dst,
669 ConstantInt::get(TD->getIntPtrType(PT),
672 // We have enough information to now generate the memcpy call to do the
673 // copy for us. Make a memcpy to copy the nul byte with align = 1.
674 B.CreateMemCpy(Dst, Src, LenV, 1);
679 struct StrNCpyOpt : public LibCallOptimization {
680 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
681 FunctionType *FT = Callee->getFunctionType();
682 if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
683 FT->getParamType(0) != FT->getParamType(1) ||
684 FT->getParamType(0) != B.getInt8PtrTy() ||
685 !FT->getParamType(2)->isIntegerTy())
688 Value *Dst = CI->getArgOperand(0);
689 Value *Src = CI->getArgOperand(1);
690 Value *LenOp = CI->getArgOperand(2);
692 // See if we can get the length of the input string.
693 uint64_t SrcLen = GetStringLength(Src);
694 if (SrcLen == 0) return 0;
698 // strncpy(x, "", y) -> memset(x, '\0', y, 1)
699 B.CreateMemSet(Dst, B.getInt8('\0'), LenOp, 1);
704 if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(LenOp))
705 Len = LengthArg->getZExtValue();
709 if (Len == 0) return Dst; // strncpy(x, y, 0) -> x
711 // These optimizations require DataLayout.
714 // Let strncpy handle the zero padding
715 if (Len > SrcLen+1) return 0;
717 Type *PT = FT->getParamType(0);
718 // strncpy(x, s, c) -> memcpy(x, s, c, 1) [s and c are constant]
719 B.CreateMemCpy(Dst, Src,
720 ConstantInt::get(TD->getIntPtrType(PT), Len), 1);
726 struct StrLenOpt : public LibCallOptimization {
727 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
728 FunctionType *FT = Callee->getFunctionType();
729 if (FT->getNumParams() != 1 ||
730 FT->getParamType(0) != B.getInt8PtrTy() ||
731 !FT->getReturnType()->isIntegerTy())
734 Value *Src = CI->getArgOperand(0);
736 // Constant folding: strlen("xyz") -> 3
737 if (uint64_t Len = GetStringLength(Src))
738 return ConstantInt::get(CI->getType(), Len-1);
740 // strlen(x) != 0 --> *x != 0
741 // strlen(x) == 0 --> *x == 0
742 if (isOnlyUsedInZeroEqualityComparison(CI))
743 return B.CreateZExt(B.CreateLoad(Src, "strlenfirst"), CI->getType());
748 struct StrPBrkOpt : public LibCallOptimization {
749 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
750 FunctionType *FT = Callee->getFunctionType();
751 if (FT->getNumParams() != 2 ||
752 FT->getParamType(0) != B.getInt8PtrTy() ||
753 FT->getParamType(1) != FT->getParamType(0) ||
754 FT->getReturnType() != FT->getParamType(0))
758 bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
759 bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
761 // strpbrk(s, "") -> NULL
762 // strpbrk("", s) -> NULL
763 if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))
764 return Constant::getNullValue(CI->getType());
767 if (HasS1 && HasS2) {
768 size_t I = S1.find_first_of(S2);
769 if (I == std::string::npos) // No match.
770 return Constant::getNullValue(CI->getType());
772 return B.CreateGEP(CI->getArgOperand(0), B.getInt64(I), "strpbrk");
775 // strpbrk(s, "a") -> strchr(s, 'a')
776 if (TD && HasS2 && S2.size() == 1)
777 return EmitStrChr(CI->getArgOperand(0), S2[0], B, TD, TLI);
783 struct StrToOpt : public LibCallOptimization {
784 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
785 FunctionType *FT = Callee->getFunctionType();
786 if ((FT->getNumParams() != 2 && FT->getNumParams() != 3) ||
787 !FT->getParamType(0)->isPointerTy() ||
788 !FT->getParamType(1)->isPointerTy())
791 Value *EndPtr = CI->getArgOperand(1);
792 if (isa<ConstantPointerNull>(EndPtr)) {
793 // With a null EndPtr, this function won't capture the main argument.
794 // It would be readonly too, except that it still may write to errno.
795 CI->addAttribute(1, Attributes::get(Callee->getContext(),
796 Attributes::NoCapture));
803 struct StrSpnOpt : public LibCallOptimization {
804 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
805 FunctionType *FT = Callee->getFunctionType();
806 if (FT->getNumParams() != 2 ||
807 FT->getParamType(0) != B.getInt8PtrTy() ||
808 FT->getParamType(1) != FT->getParamType(0) ||
809 !FT->getReturnType()->isIntegerTy())
813 bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
814 bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
816 // strspn(s, "") -> 0
817 // strspn("", s) -> 0
818 if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))
819 return Constant::getNullValue(CI->getType());
822 if (HasS1 && HasS2) {
823 size_t Pos = S1.find_first_not_of(S2);
824 if (Pos == StringRef::npos) Pos = S1.size();
825 return ConstantInt::get(CI->getType(), Pos);
832 struct StrCSpnOpt : public LibCallOptimization {
833 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
834 FunctionType *FT = Callee->getFunctionType();
835 if (FT->getNumParams() != 2 ||
836 FT->getParamType(0) != B.getInt8PtrTy() ||
837 FT->getParamType(1) != FT->getParamType(0) ||
838 !FT->getReturnType()->isIntegerTy())
842 bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
843 bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
845 // strcspn("", s) -> 0
846 if (HasS1 && S1.empty())
847 return Constant::getNullValue(CI->getType());
850 if (HasS1 && HasS2) {
851 size_t Pos = S1.find_first_of(S2);
852 if (Pos == StringRef::npos) Pos = S1.size();
853 return ConstantInt::get(CI->getType(), Pos);
856 // strcspn(s, "") -> strlen(s)
857 if (TD && HasS2 && S2.empty())
858 return EmitStrLen(CI->getArgOperand(0), B, TD, TLI);
864 struct StrStrOpt : public LibCallOptimization {
865 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
866 FunctionType *FT = Callee->getFunctionType();
867 if (FT->getNumParams() != 2 ||
868 !FT->getParamType(0)->isPointerTy() ||
869 !FT->getParamType(1)->isPointerTy() ||
870 !FT->getReturnType()->isPointerTy())
873 // fold strstr(x, x) -> x.
874 if (CI->getArgOperand(0) == CI->getArgOperand(1))
875 return B.CreateBitCast(CI->getArgOperand(0), CI->getType());
877 // fold strstr(a, b) == a -> strncmp(a, b, strlen(b)) == 0
878 if (TD && isOnlyUsedInEqualityComparison(CI, CI->getArgOperand(0))) {
879 Value *StrLen = EmitStrLen(CI->getArgOperand(1), B, TD, TLI);
882 Value *StrNCmp = EmitStrNCmp(CI->getArgOperand(0), CI->getArgOperand(1),
886 for (Value::use_iterator UI = CI->use_begin(), UE = CI->use_end();
888 ICmpInst *Old = cast<ICmpInst>(*UI++);
889 Value *Cmp = B.CreateICmp(Old->getPredicate(), StrNCmp,
890 ConstantInt::getNullValue(StrNCmp->getType()),
892 LCS->replaceAllUsesWith(Old, Cmp);
897 // See if either input string is a constant string.
898 StringRef SearchStr, ToFindStr;
899 bool HasStr1 = getConstantStringInfo(CI->getArgOperand(0), SearchStr);
900 bool HasStr2 = getConstantStringInfo(CI->getArgOperand(1), ToFindStr);
902 // fold strstr(x, "") -> x.
903 if (HasStr2 && ToFindStr.empty())
904 return B.CreateBitCast(CI->getArgOperand(0), CI->getType());
906 // If both strings are known, constant fold it.
907 if (HasStr1 && HasStr2) {
908 std::string::size_type Offset = SearchStr.find(ToFindStr);
910 if (Offset == StringRef::npos) // strstr("foo", "bar") -> null
911 return Constant::getNullValue(CI->getType());
913 // strstr("abcd", "bc") -> gep((char*)"abcd", 1)
914 Value *Result = CastToCStr(CI->getArgOperand(0), B);
915 Result = B.CreateConstInBoundsGEP1_64(Result, Offset, "strstr");
916 return B.CreateBitCast(Result, CI->getType());
919 // fold strstr(x, "y") -> strchr(x, 'y').
920 if (HasStr2 && ToFindStr.size() == 1) {
921 Value *StrChr= EmitStrChr(CI->getArgOperand(0), ToFindStr[0], B, TD, TLI);
922 return StrChr ? B.CreateBitCast(StrChr, CI->getType()) : 0;
928 struct MemCmpOpt : public LibCallOptimization {
929 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
930 FunctionType *FT = Callee->getFunctionType();
931 if (FT->getNumParams() != 3 || !FT->getParamType(0)->isPointerTy() ||
932 !FT->getParamType(1)->isPointerTy() ||
933 !FT->getReturnType()->isIntegerTy(32))
936 Value *LHS = CI->getArgOperand(0), *RHS = CI->getArgOperand(1);
938 if (LHS == RHS) // memcmp(s,s,x) -> 0
939 return Constant::getNullValue(CI->getType());
941 // Make sure we have a constant length.
942 ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getArgOperand(2));
944 uint64_t Len = LenC->getZExtValue();
946 if (Len == 0) // memcmp(s1,s2,0) -> 0
947 return Constant::getNullValue(CI->getType());
949 // memcmp(S1,S2,1) -> *(unsigned char*)LHS - *(unsigned char*)RHS
951 Value *LHSV = B.CreateZExt(B.CreateLoad(CastToCStr(LHS, B), "lhsc"),
952 CI->getType(), "lhsv");
953 Value *RHSV = B.CreateZExt(B.CreateLoad(CastToCStr(RHS, B), "rhsc"),
954 CI->getType(), "rhsv");
955 return B.CreateSub(LHSV, RHSV, "chardiff");
958 // Constant folding: memcmp(x, y, l) -> cnst (all arguments are constant)
959 StringRef LHSStr, RHSStr;
960 if (getConstantStringInfo(LHS, LHSStr) &&
961 getConstantStringInfo(RHS, RHSStr)) {
962 // Make sure we're not reading out-of-bounds memory.
963 if (Len > LHSStr.size() || Len > RHSStr.size())
965 // Fold the memcmp and normalize the result. This way we get consistent
966 // results across multiple platforms.
968 int Cmp = memcmp(LHSStr.data(), RHSStr.data(), Len);
973 return ConstantInt::get(CI->getType(), Ret);
980 struct MemCpyOpt : public LibCallOptimization {
981 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
982 // These optimizations require DataLayout.
985 FunctionType *FT = Callee->getFunctionType();
986 if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
987 !FT->getParamType(0)->isPointerTy() ||
988 !FT->getParamType(1)->isPointerTy() ||
989 FT->getParamType(2) != TD->getIntPtrType(*Context))
992 // memcpy(x, y, n) -> llvm.memcpy(x, y, n, 1)
993 B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
994 CI->getArgOperand(2), 1);
995 return CI->getArgOperand(0);
999 struct MemMoveOpt : public LibCallOptimization {
1000 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1001 // These optimizations require DataLayout.
1004 FunctionType *FT = Callee->getFunctionType();
1005 if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
1006 !FT->getParamType(0)->isPointerTy() ||
1007 !FT->getParamType(1)->isPointerTy() ||
1008 FT->getParamType(2) != TD->getIntPtrType(*Context))
1011 // memmove(x, y, n) -> llvm.memmove(x, y, n, 1)
1012 B.CreateMemMove(CI->getArgOperand(0), CI->getArgOperand(1),
1013 CI->getArgOperand(2), 1);
1014 return CI->getArgOperand(0);
1018 struct MemSetOpt : public LibCallOptimization {
1019 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1020 // These optimizations require DataLayout.
1023 FunctionType *FT = Callee->getFunctionType();
1024 if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
1025 !FT->getParamType(0)->isPointerTy() ||
1026 !FT->getParamType(1)->isIntegerTy() ||
1027 FT->getParamType(2) != TD->getIntPtrType(*Context))
1030 // memset(p, v, n) -> llvm.memset(p, v, n, 1)
1031 Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(), false);
1032 B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1);
1033 return CI->getArgOperand(0);
1037 //===----------------------------------------------------------------------===//
1038 // Math Library Optimizations
1039 //===----------------------------------------------------------------------===//
1041 //===----------------------------------------------------------------------===//
1042 // Double -> Float Shrinking Optimizations for Unary Functions like 'floor'
1044 struct UnaryDoubleFPOpt : public LibCallOptimization {
1046 UnaryDoubleFPOpt(bool CheckReturnType): CheckRetType(CheckReturnType) {}
1047 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1048 FunctionType *FT = Callee->getFunctionType();
1049 if (FT->getNumParams() != 1 || !FT->getReturnType()->isDoubleTy() ||
1050 !FT->getParamType(0)->isDoubleTy())
1054 // Check if all the uses for function like 'sin' are converted to float.
1055 for (Value::use_iterator UseI = CI->use_begin(); UseI != CI->use_end();
1057 FPTruncInst *Cast = dyn_cast<FPTruncInst>(*UseI);
1058 if (Cast == 0 || !Cast->getType()->isFloatTy())
1063 // If this is something like 'floor((double)floatval)', convert to floorf.
1064 FPExtInst *Cast = dyn_cast<FPExtInst>(CI->getArgOperand(0));
1065 if (Cast == 0 || !Cast->getOperand(0)->getType()->isFloatTy())
1068 // floor((double)floatval) -> (double)floorf(floatval)
1069 Value *V = Cast->getOperand(0);
1070 V = EmitUnaryFloatFnCall(V, Callee->getName(), B, Callee->getAttributes());
1071 return B.CreateFPExt(V, B.getDoubleTy());
1075 struct UnsafeFPLibCallOptimization : public LibCallOptimization {
1076 bool UnsafeFPShrink;
1077 UnsafeFPLibCallOptimization(bool UnsafeFPShrink) {
1078 this->UnsafeFPShrink = UnsafeFPShrink;
1082 struct CosOpt : public UnsafeFPLibCallOptimization {
1083 CosOpt(bool UnsafeFPShrink) : UnsafeFPLibCallOptimization(UnsafeFPShrink) {}
1084 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1086 if (UnsafeFPShrink && Callee->getName() == "cos" &&
1087 TLI->has(LibFunc::cosf)) {
1088 UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
1089 Ret = UnsafeUnaryDoubleFP.callOptimizer(Callee, CI, B);
1092 FunctionType *FT = Callee->getFunctionType();
1093 // Just make sure this has 1 argument of FP type, which matches the
1095 if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1096 !FT->getParamType(0)->isFloatingPointTy())
1099 // cos(-x) -> cos(x)
1100 Value *Op1 = CI->getArgOperand(0);
1101 if (BinaryOperator::isFNeg(Op1)) {
1102 BinaryOperator *BinExpr = cast<BinaryOperator>(Op1);
1103 return B.CreateCall(Callee, BinExpr->getOperand(1), "cos");
1109 struct PowOpt : public UnsafeFPLibCallOptimization {
1110 PowOpt(bool UnsafeFPShrink) : UnsafeFPLibCallOptimization(UnsafeFPShrink) {}
1111 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1113 if (UnsafeFPShrink && Callee->getName() == "pow" &&
1114 TLI->has(LibFunc::powf)) {
1115 UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
1116 Ret = UnsafeUnaryDoubleFP.callOptimizer(Callee, CI, B);
1119 FunctionType *FT = Callee->getFunctionType();
1120 // Just make sure this has 2 arguments of the same FP type, which match the
1122 if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) ||
1123 FT->getParamType(0) != FT->getParamType(1) ||
1124 !FT->getParamType(0)->isFloatingPointTy())
1127 Value *Op1 = CI->getArgOperand(0), *Op2 = CI->getArgOperand(1);
1128 if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) {
1129 if (Op1C->isExactlyValue(1.0)) // pow(1.0, x) -> 1.0
1131 if (Op1C->isExactlyValue(2.0)) // pow(2.0, x) -> exp2(x)
1132 return EmitUnaryFloatFnCall(Op2, "exp2", B, Callee->getAttributes());
1135 ConstantFP *Op2C = dyn_cast<ConstantFP>(Op2);
1136 if (Op2C == 0) return Ret;
1138 if (Op2C->getValueAPF().isZero()) // pow(x, 0.0) -> 1.0
1139 return ConstantFP::get(CI->getType(), 1.0);
1141 if (Op2C->isExactlyValue(0.5)) {
1142 // Expand pow(x, 0.5) to (x == -infinity ? +infinity : fabs(sqrt(x))).
1143 // This is faster than calling pow, and still handles negative zero
1144 // and negative infinity correctly.
1145 // TODO: In fast-math mode, this could be just sqrt(x).
1146 // TODO: In finite-only mode, this could be just fabs(sqrt(x)).
1147 Value *Inf = ConstantFP::getInfinity(CI->getType());
1148 Value *NegInf = ConstantFP::getInfinity(CI->getType(), true);
1149 Value *Sqrt = EmitUnaryFloatFnCall(Op1, "sqrt", B,
1150 Callee->getAttributes());
1151 Value *FAbs = EmitUnaryFloatFnCall(Sqrt, "fabs", B,
1152 Callee->getAttributes());
1153 Value *FCmp = B.CreateFCmpOEQ(Op1, NegInf);
1154 Value *Sel = B.CreateSelect(FCmp, Inf, FAbs);
1158 if (Op2C->isExactlyValue(1.0)) // pow(x, 1.0) -> x
1160 if (Op2C->isExactlyValue(2.0)) // pow(x, 2.0) -> x*x
1161 return B.CreateFMul(Op1, Op1, "pow2");
1162 if (Op2C->isExactlyValue(-1.0)) // pow(x, -1.0) -> 1.0/x
1163 return B.CreateFDiv(ConstantFP::get(CI->getType(), 1.0),
1169 struct Exp2Opt : public UnsafeFPLibCallOptimization {
1170 Exp2Opt(bool UnsafeFPShrink) : UnsafeFPLibCallOptimization(UnsafeFPShrink) {}
1171 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1173 if (UnsafeFPShrink && Callee->getName() == "exp2" &&
1174 TLI->has(LibFunc::exp2)) {
1175 UnaryDoubleFPOpt UnsafeUnaryDoubleFP(true);
1176 Ret = UnsafeUnaryDoubleFP.callOptimizer(Callee, CI, B);
1179 FunctionType *FT = Callee->getFunctionType();
1180 // Just make sure this has 1 argument of FP type, which matches the
1182 if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1183 !FT->getParamType(0)->isFloatingPointTy())
1186 Value *Op = CI->getArgOperand(0);
1187 // Turn exp2(sitofp(x)) -> ldexp(1.0, sext(x)) if sizeof(x) <= 32
1188 // Turn exp2(uitofp(x)) -> ldexp(1.0, zext(x)) if sizeof(x) < 32
1189 Value *LdExpArg = 0;
1190 if (SIToFPInst *OpC = dyn_cast<SIToFPInst>(Op)) {
1191 if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() <= 32)
1192 LdExpArg = B.CreateSExt(OpC->getOperand(0), B.getInt32Ty());
1193 } else if (UIToFPInst *OpC = dyn_cast<UIToFPInst>(Op)) {
1194 if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() < 32)
1195 LdExpArg = B.CreateZExt(OpC->getOperand(0), B.getInt32Ty());
1200 if (Op->getType()->isFloatTy())
1202 else if (Op->getType()->isDoubleTy())
1207 Constant *One = ConstantFP::get(*Context, APFloat(1.0f));
1208 if (!Op->getType()->isFloatTy())
1209 One = ConstantExpr::getFPExtend(One, Op->getType());
1211 Module *M = Caller->getParent();
1212 Value *Callee = M->getOrInsertFunction(Name, Op->getType(),
1214 B.getInt32Ty(), NULL);
1215 CallInst *CI = B.CreateCall2(Callee, One, LdExpArg);
1216 if (const Function *F = dyn_cast<Function>(Callee->stripPointerCasts()))
1217 CI->setCallingConv(F->getCallingConv());
1225 //===----------------------------------------------------------------------===//
1226 // Integer Library Call Optimizations
1227 //===----------------------------------------------------------------------===//
1229 struct FFSOpt : public LibCallOptimization {
1230 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1231 FunctionType *FT = Callee->getFunctionType();
1232 // Just make sure this has 2 arguments of the same FP type, which match the
1234 if (FT->getNumParams() != 1 ||
1235 !FT->getReturnType()->isIntegerTy(32) ||
1236 !FT->getParamType(0)->isIntegerTy())
1239 Value *Op = CI->getArgOperand(0);
1242 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op)) {
1243 if (CI->isZero()) // ffs(0) -> 0.
1244 return B.getInt32(0);
1245 // ffs(c) -> cttz(c)+1
1246 return B.getInt32(CI->getValue().countTrailingZeros() + 1);
1249 // ffs(x) -> x != 0 ? (i32)llvm.cttz(x)+1 : 0
1250 Type *ArgType = Op->getType();
1251 Value *F = Intrinsic::getDeclaration(Callee->getParent(),
1252 Intrinsic::cttz, ArgType);
1253 Value *V = B.CreateCall2(F, Op, B.getFalse(), "cttz");
1254 V = B.CreateAdd(V, ConstantInt::get(V->getType(), 1));
1255 V = B.CreateIntCast(V, B.getInt32Ty(), false);
1257 Value *Cond = B.CreateICmpNE(Op, Constant::getNullValue(ArgType));
1258 return B.CreateSelect(Cond, V, B.getInt32(0));
1262 struct AbsOpt : public LibCallOptimization {
1263 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1264 FunctionType *FT = Callee->getFunctionType();
1265 // We require integer(integer) where the types agree.
1266 if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
1267 FT->getParamType(0) != FT->getReturnType())
1270 // abs(x) -> x >s -1 ? x : -x
1271 Value *Op = CI->getArgOperand(0);
1272 Value *Pos = B.CreateICmpSGT(Op, Constant::getAllOnesValue(Op->getType()),
1274 Value *Neg = B.CreateNeg(Op, "neg");
1275 return B.CreateSelect(Pos, Op, Neg);
1279 struct IsDigitOpt : public LibCallOptimization {
1280 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1281 FunctionType *FT = Callee->getFunctionType();
1282 // We require integer(i32)
1283 if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
1284 !FT->getParamType(0)->isIntegerTy(32))
1287 // isdigit(c) -> (c-'0') <u 10
1288 Value *Op = CI->getArgOperand(0);
1289 Op = B.CreateSub(Op, B.getInt32('0'), "isdigittmp");
1290 Op = B.CreateICmpULT(Op, B.getInt32(10), "isdigit");
1291 return B.CreateZExt(Op, CI->getType());
1295 struct IsAsciiOpt : public LibCallOptimization {
1296 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1297 FunctionType *FT = Callee->getFunctionType();
1298 // We require integer(i32)
1299 if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
1300 !FT->getParamType(0)->isIntegerTy(32))
1303 // isascii(c) -> c <u 128
1304 Value *Op = CI->getArgOperand(0);
1305 Op = B.CreateICmpULT(Op, B.getInt32(128), "isascii");
1306 return B.CreateZExt(Op, CI->getType());
1310 struct ToAsciiOpt : public LibCallOptimization {
1311 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1312 FunctionType *FT = Callee->getFunctionType();
1313 // We require i32(i32)
1314 if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1315 !FT->getParamType(0)->isIntegerTy(32))
1318 // toascii(c) -> c & 0x7f
1319 return B.CreateAnd(CI->getArgOperand(0),
1320 ConstantInt::get(CI->getType(),0x7F));
1324 //===----------------------------------------------------------------------===//
1325 // Formatting and IO Library Call Optimizations
1326 //===----------------------------------------------------------------------===//
1328 struct PrintFOpt : public LibCallOptimization {
1329 Value *optimizeFixedFormatString(Function *Callee, CallInst *CI,
1331 // Check for a fixed format string.
1332 StringRef FormatStr;
1333 if (!getConstantStringInfo(CI->getArgOperand(0), FormatStr))
1336 // Empty format string -> noop.
1337 if (FormatStr.empty()) // Tolerate printf's declared void.
1338 return CI->use_empty() ? (Value*)CI :
1339 ConstantInt::get(CI->getType(), 0);
1341 // Do not do any of the following transformations if the printf return value
1342 // is used, in general the printf return value is not compatible with either
1343 // putchar() or puts().
1344 if (!CI->use_empty())
1347 // printf("x") -> putchar('x'), even for '%'.
1348 if (FormatStr.size() == 1) {
1349 Value *Res = EmitPutChar(B.getInt32(FormatStr[0]), B, TD, TLI);
1350 if (CI->use_empty() || !Res) return Res;
1351 return B.CreateIntCast(Res, CI->getType(), true);
1354 // printf("foo\n") --> puts("foo")
1355 if (FormatStr[FormatStr.size()-1] == '\n' &&
1356 FormatStr.find('%') == std::string::npos) { // no format characters.
1357 // Create a string literal with no \n on it. We expect the constant merge
1358 // pass to be run after this pass, to merge duplicate strings.
1359 FormatStr = FormatStr.drop_back();
1360 Value *GV = B.CreateGlobalString(FormatStr, "str");
1361 Value *NewCI = EmitPutS(GV, B, TD, TLI);
1362 return (CI->use_empty() || !NewCI) ?
1364 ConstantInt::get(CI->getType(), FormatStr.size()+1);
1367 // Optimize specific format strings.
1368 // printf("%c", chr) --> putchar(chr)
1369 if (FormatStr == "%c" && CI->getNumArgOperands() > 1 &&
1370 CI->getArgOperand(1)->getType()->isIntegerTy()) {
1371 Value *Res = EmitPutChar(CI->getArgOperand(1), B, TD, TLI);
1373 if (CI->use_empty() || !Res) return Res;
1374 return B.CreateIntCast(Res, CI->getType(), true);
1377 // printf("%s\n", str) --> puts(str)
1378 if (FormatStr == "%s\n" && CI->getNumArgOperands() > 1 &&
1379 CI->getArgOperand(1)->getType()->isPointerTy()) {
1380 return EmitPutS(CI->getArgOperand(1), B, TD, TLI);
1385 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1386 // Require one fixed pointer argument and an integer/void result.
1387 FunctionType *FT = Callee->getFunctionType();
1388 if (FT->getNumParams() < 1 || !FT->getParamType(0)->isPointerTy() ||
1389 !(FT->getReturnType()->isIntegerTy() ||
1390 FT->getReturnType()->isVoidTy()))
1393 if (Value *V = optimizeFixedFormatString(Callee, CI, B)) {
1397 // printf(format, ...) -> iprintf(format, ...) if no floating point
1399 if (TLI->has(LibFunc::iprintf) && !callHasFloatingPointArgument(CI)) {
1400 Module *M = B.GetInsertBlock()->getParent()->getParent();
1401 Constant *IPrintFFn =
1402 M->getOrInsertFunction("iprintf", FT, Callee->getAttributes());
1403 CallInst *New = cast<CallInst>(CI->clone());
1404 New->setCalledFunction(IPrintFFn);
1412 struct SPrintFOpt : public LibCallOptimization {
1413 Value *OptimizeFixedFormatString(Function *Callee, CallInst *CI,
1415 // Check for a fixed format string.
1416 StringRef FormatStr;
1417 if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr))
1420 // If we just have a format string (nothing else crazy) transform it.
1421 if (CI->getNumArgOperands() == 2) {
1422 // Make sure there's no % in the constant array. We could try to handle
1423 // %% -> % in the future if we cared.
1424 for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1425 if (FormatStr[i] == '%')
1426 return 0; // we found a format specifier, bail out.
1428 // These optimizations require DataLayout.
1431 // sprintf(str, fmt) -> llvm.memcpy(str, fmt, strlen(fmt)+1, 1)
1432 B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
1433 ConstantInt::get(TD->getIntPtrType(*Context), // Copy the
1434 FormatStr.size() + 1), 1); // nul byte.
1435 return ConstantInt::get(CI->getType(), FormatStr.size());
1438 // The remaining optimizations require the format string to be "%s" or "%c"
1439 // and have an extra operand.
1440 if (FormatStr.size() != 2 || FormatStr[0] != '%' ||
1441 CI->getNumArgOperands() < 3)
1444 // Decode the second character of the format string.
1445 if (FormatStr[1] == 'c') {
1446 // sprintf(dst, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0
1447 if (!CI->getArgOperand(2)->getType()->isIntegerTy()) return 0;
1448 Value *V = B.CreateTrunc(CI->getArgOperand(2), B.getInt8Ty(), "char");
1449 Value *Ptr = CastToCStr(CI->getArgOperand(0), B);
1450 B.CreateStore(V, Ptr);
1451 Ptr = B.CreateGEP(Ptr, B.getInt32(1), "nul");
1452 B.CreateStore(B.getInt8(0), Ptr);
1454 return ConstantInt::get(CI->getType(), 1);
1457 if (FormatStr[1] == 's') {
1458 // These optimizations require DataLayout.
1461 // sprintf(dest, "%s", str) -> llvm.memcpy(dest, str, strlen(str)+1, 1)
1462 if (!CI->getArgOperand(2)->getType()->isPointerTy()) return 0;
1464 Value *Len = EmitStrLen(CI->getArgOperand(2), B, TD, TLI);
1467 Value *IncLen = B.CreateAdd(Len,
1468 ConstantInt::get(Len->getType(), 1),
1470 B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(2), IncLen, 1);
1472 // The sprintf result is the unincremented number of bytes in the string.
1473 return B.CreateIntCast(Len, CI->getType(), false);
1478 virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1479 // Require two fixed pointer arguments and an integer result.
1480 FunctionType *FT = Callee->getFunctionType();
1481 if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
1482 !FT->getParamType(1)->isPointerTy() ||
1483 !FT->getReturnType()->isIntegerTy())
1486 if (Value *V = OptimizeFixedFormatString(Callee, CI, B)) {
1490 // sprintf(str, format, ...) -> siprintf(str, format, ...) if no floating
1492 if (TLI->has(LibFunc::siprintf) && !callHasFloatingPointArgument(CI)) {
1493 Module *M = B.GetInsertBlock()->getParent()->getParent();
1494 Constant *SIPrintFFn =
1495 M->getOrInsertFunction("siprintf", FT, Callee->getAttributes());
1496 CallInst *New = cast<CallInst>(CI->clone());
1497 New->setCalledFunction(SIPrintFFn);
1505 } // End anonymous namespace.
1509 class LibCallSimplifierImpl {
1510 const DataLayout *TD;
1511 const TargetLibraryInfo *TLI;
1512 const LibCallSimplifier *LCS;
1513 bool UnsafeFPShrink;
1514 StringMap<LibCallOptimization*> Optimizations;
1516 // Fortified library call optimizations.
1517 MemCpyChkOpt MemCpyChk;
1518 MemMoveChkOpt MemMoveChk;
1519 MemSetChkOpt MemSetChk;
1520 StrCpyChkOpt StrCpyChk;
1521 StpCpyChkOpt StpCpyChk;
1522 StrNCpyChkOpt StrNCpyChk;
1524 // String library call optimizations.
1541 // Memory library call optimizations.
1547 // Math library call optimizations.
1548 UnaryDoubleFPOpt UnaryDoubleFP, UnsafeUnaryDoubleFP;
1549 CosOpt Cos; PowOpt Pow; Exp2Opt Exp2;
1551 // Integer library call optimizations.
1558 // Formatting and IO library call optimizations.
1562 void initOptimizations();
1563 void addOpt(LibFunc::Func F, LibCallOptimization* Opt);
1564 void addOpt(LibFunc::Func F1, LibFunc::Func F2, LibCallOptimization* Opt);
1566 LibCallSimplifierImpl(const DataLayout *TD, const TargetLibraryInfo *TLI,
1567 const LibCallSimplifier *LCS,
1568 bool UnsafeFPShrink = false)
1569 : UnaryDoubleFP(false), UnsafeUnaryDoubleFP(true),
1570 Cos(UnsafeFPShrink), Pow(UnsafeFPShrink), Exp2(UnsafeFPShrink) {
1574 this->UnsafeFPShrink = UnsafeFPShrink;
1577 Value *optimizeCall(CallInst *CI);
1580 void LibCallSimplifierImpl::initOptimizations() {
1581 // Fortified library call optimizations.
1582 Optimizations["__memcpy_chk"] = &MemCpyChk;
1583 Optimizations["__memmove_chk"] = &MemMoveChk;
1584 Optimizations["__memset_chk"] = &MemSetChk;
1585 Optimizations["__strcpy_chk"] = &StrCpyChk;
1586 Optimizations["__stpcpy_chk"] = &StpCpyChk;
1587 Optimizations["__strncpy_chk"] = &StrNCpyChk;
1588 Optimizations["__stpncpy_chk"] = &StrNCpyChk;
1590 // String library call optimizations.
1591 addOpt(LibFunc::strcat, &StrCat);
1592 addOpt(LibFunc::strncat, &StrNCat);
1593 addOpt(LibFunc::strchr, &StrChr);
1594 addOpt(LibFunc::strrchr, &StrRChr);
1595 addOpt(LibFunc::strcmp, &StrCmp);
1596 addOpt(LibFunc::strncmp, &StrNCmp);
1597 addOpt(LibFunc::strcpy, &StrCpy);
1598 addOpt(LibFunc::stpcpy, &StpCpy);
1599 addOpt(LibFunc::strncpy, &StrNCpy);
1600 addOpt(LibFunc::strlen, &StrLen);
1601 addOpt(LibFunc::strpbrk, &StrPBrk);
1602 addOpt(LibFunc::strtol, &StrTo);
1603 addOpt(LibFunc::strtod, &StrTo);
1604 addOpt(LibFunc::strtof, &StrTo);
1605 addOpt(LibFunc::strtoul, &StrTo);
1606 addOpt(LibFunc::strtoll, &StrTo);
1607 addOpt(LibFunc::strtold, &StrTo);
1608 addOpt(LibFunc::strtoull, &StrTo);
1609 addOpt(LibFunc::strspn, &StrSpn);
1610 addOpt(LibFunc::strcspn, &StrCSpn);
1611 addOpt(LibFunc::strstr, &StrStr);
1613 // Memory library call optimizations.
1614 addOpt(LibFunc::memcmp, &MemCmp);
1615 addOpt(LibFunc::memcpy, &MemCpy);
1616 addOpt(LibFunc::memmove, &MemMove);
1617 addOpt(LibFunc::memset, &MemSet);
1619 // Math library call optimizations.
1620 addOpt(LibFunc::ceil, LibFunc::ceilf, &UnaryDoubleFP);
1621 addOpt(LibFunc::fabs, LibFunc::fabsf, &UnaryDoubleFP);
1622 addOpt(LibFunc::floor, LibFunc::floorf, &UnaryDoubleFP);
1623 addOpt(LibFunc::rint, LibFunc::rintf, &UnaryDoubleFP);
1624 addOpt(LibFunc::round, LibFunc::roundf, &UnaryDoubleFP);
1625 addOpt(LibFunc::nearbyint, LibFunc::nearbyintf, &UnaryDoubleFP);
1626 addOpt(LibFunc::trunc, LibFunc::truncf, &UnaryDoubleFP);
1628 if(UnsafeFPShrink) {
1629 addOpt(LibFunc::acos, LibFunc::acosf, &UnsafeUnaryDoubleFP);
1630 addOpt(LibFunc::acosh, LibFunc::acoshf, &UnsafeUnaryDoubleFP);
1631 addOpt(LibFunc::asin, LibFunc::asinf, &UnsafeUnaryDoubleFP);
1632 addOpt(LibFunc::asinh, LibFunc::asinhf, &UnsafeUnaryDoubleFP);
1633 addOpt(LibFunc::atan, LibFunc::atanf, &UnsafeUnaryDoubleFP);
1634 addOpt(LibFunc::atanh, LibFunc::atanhf, &UnsafeUnaryDoubleFP);
1635 addOpt(LibFunc::cbrt, LibFunc::cbrtf, &UnsafeUnaryDoubleFP);
1636 addOpt(LibFunc::cosh, LibFunc::coshf, &UnsafeUnaryDoubleFP);
1637 addOpt(LibFunc::exp, LibFunc::expf, &UnsafeUnaryDoubleFP);
1638 addOpt(LibFunc::exp10, LibFunc::exp10f, &UnsafeUnaryDoubleFP);
1639 addOpt(LibFunc::expm1, LibFunc::expm1f, &UnsafeUnaryDoubleFP);
1640 addOpt(LibFunc::log, LibFunc::logf, &UnsafeUnaryDoubleFP);
1641 addOpt(LibFunc::log10, LibFunc::log10f, &UnsafeUnaryDoubleFP);
1642 addOpt(LibFunc::log1p, LibFunc::log1pf, &UnsafeUnaryDoubleFP);
1643 addOpt(LibFunc::log2, LibFunc::log2f, &UnsafeUnaryDoubleFP);
1644 addOpt(LibFunc::logb, LibFunc::logbf, &UnsafeUnaryDoubleFP);
1645 addOpt(LibFunc::sin, LibFunc::sinf, &UnsafeUnaryDoubleFP);
1646 addOpt(LibFunc::sinh, LibFunc::sinhf, &UnsafeUnaryDoubleFP);
1647 addOpt(LibFunc::sqrt, LibFunc::sqrtf, &UnsafeUnaryDoubleFP);
1648 addOpt(LibFunc::tan, LibFunc::tanf, &UnsafeUnaryDoubleFP);
1649 addOpt(LibFunc::tanh, LibFunc::tanhf, &UnsafeUnaryDoubleFP);
1652 addOpt(LibFunc::cosf, &Cos);
1653 addOpt(LibFunc::cos, &Cos);
1654 addOpt(LibFunc::cosl, &Cos);
1655 addOpt(LibFunc::powf, &Pow);
1656 addOpt(LibFunc::pow, &Pow);
1657 addOpt(LibFunc::powl, &Pow);
1658 Optimizations["llvm.pow.f32"] = &Pow;
1659 Optimizations["llvm.pow.f64"] = &Pow;
1660 Optimizations["llvm.pow.f80"] = &Pow;
1661 Optimizations["llvm.pow.f128"] = &Pow;
1662 Optimizations["llvm.pow.ppcf128"] = &Pow;
1663 addOpt(LibFunc::exp2l, &Exp2);
1664 addOpt(LibFunc::exp2, &Exp2);
1665 addOpt(LibFunc::exp2f, &Exp2);
1666 Optimizations["llvm.exp2.ppcf128"] = &Exp2;
1667 Optimizations["llvm.exp2.f128"] = &Exp2;
1668 Optimizations["llvm.exp2.f80"] = &Exp2;
1669 Optimizations["llvm.exp2.f64"] = &Exp2;
1670 Optimizations["llvm.exp2.f32"] = &Exp2;
1672 // Integer library call optimizations.
1673 addOpt(LibFunc::ffs, &FFS);
1674 addOpt(LibFunc::ffsl, &FFS);
1675 addOpt(LibFunc::ffsll, &FFS);
1676 addOpt(LibFunc::abs, &Abs);
1677 addOpt(LibFunc::labs, &Abs);
1678 addOpt(LibFunc::llabs, &Abs);
1679 addOpt(LibFunc::isdigit, &IsDigit);
1680 addOpt(LibFunc::isascii, &IsAscii);
1681 addOpt(LibFunc::toascii, &ToAscii);
1683 // Formatting and IO library call optimizations.
1684 addOpt(LibFunc::printf, &PrintF);
1685 addOpt(LibFunc::sprintf, &SPrintF);
1688 Value *LibCallSimplifierImpl::optimizeCall(CallInst *CI) {
1689 if (Optimizations.empty())
1690 initOptimizations();
1692 Function *Callee = CI->getCalledFunction();
1693 LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
1695 IRBuilder<> Builder(CI);
1696 return LCO->optimizeCall(CI, TD, TLI, LCS, Builder);
1701 void LibCallSimplifierImpl::addOpt(LibFunc::Func F, LibCallOptimization* Opt) {
1703 Optimizations[TLI->getName(F)] = Opt;
1706 void LibCallSimplifierImpl::addOpt(LibFunc::Func F1, LibFunc::Func F2,
1707 LibCallOptimization* Opt) {
1708 if (TLI->has(F1) && TLI->has(F2))
1709 Optimizations[TLI->getName(F1)] = Opt;
1712 LibCallSimplifier::LibCallSimplifier(const DataLayout *TD,
1713 const TargetLibraryInfo *TLI,
1714 bool UnsafeFPShrink) {
1715 Impl = new LibCallSimplifierImpl(TD, TLI, this, UnsafeFPShrink);
1718 LibCallSimplifier::~LibCallSimplifier() {
1722 Value *LibCallSimplifier::optimizeCall(CallInst *CI) {
1723 return Impl->optimizeCall(CI);
1726 void LibCallSimplifier::replaceAllUsesWith(Instruction *I, Value *With) const {
1727 I->replaceAllUsesWith(With);
1728 I->eraseFromParent();