1 //===------ SimplifyLibCalls.cpp - Library calls simplifier ---------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This is a utility pass used for testing the InstructionSimplify analysis.
11 // The analysis is applied to every instruction, and if it simplifies then the
12 // instruction is replaced by the simplification.  If you are looking for a pass
13 // that performs serious instruction folding, use the instcombine pass instead.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #include "llvm/Transforms/Utils/SimplifyLibCalls.h"
18 #include "llvm/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/LLVMContext.h"
24 #include "llvm/Target/TargetLibraryInfo.h"
25 #include "llvm/Transforms/Utils/BuildLibCalls.h"
26 
27 using namespace llvm;
28 
29 /// This class is the abstract base class for the set of optimizations that
30 /// corresponds to one library call.
31 namespace {
32 class LibCallOptimization {
33 protected:
34   Function *Caller;
35   const DataLayout *TD;
36   const TargetLibraryInfo *TLI;
37   LLVMContext* Context;
38 public:
39   LibCallOptimization() { }
40   virtual ~LibCallOptimization() {}
41 
42   /// callOptimizer - This pure virtual method is implemented by base classes to
43   /// do various optimizations.  If this returns null then no transformation was
44   /// performed.  If it returns CI, then it transformed the call and CI is to be
45   /// deleted.  If it returns something else, replace CI with the new value and
46   /// delete CI.
47   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B)
48     =0;
49 
50   Value *optimizeCall(CallInst *CI, const DataLayout *TD,
51                       const TargetLibraryInfo *TLI, IRBuilder<> &B) {
52     Caller = CI->getParent()->getParent();
53     this->TD = TD;
54     this->TLI = TLI;
55     if (CI->getCalledFunction())
56       Context = &CI->getCalledFunction()->getContext();
57 
58     // We never change the calling convention.
59     if (CI->getCallingConv() != llvm::CallingConv::C)
60       return NULL;
61 
62     return callOptimizer(CI->getCalledFunction(), CI, B);
63   }
64 };
65 
66 //===----------------------------------------------------------------------===//
67 // Helper Functions
68 //===----------------------------------------------------------------------===//
69 
70 /// isOnlyUsedInZeroEqualityComparison - Return true if it only matters that the
71 /// value is equal or not-equal to zero.
72 static bool isOnlyUsedInZeroEqualityComparison(Value *V) {
73   for (Value::use_iterator UI = V->use_begin(), E = V->use_end();
74        UI != E; ++UI) {
75     if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI))
76       if (IC->isEquality())
77         if (Constant *C = dyn_cast<Constant>(IC->getOperand(1)))
78           if (C->isNullValue())
79             continue;
80     // Unknown instruction.
81     return false;
82   }
83   return true;
84 }
85 
86 //===----------------------------------------------------------------------===//
87 // Fortified Library Call Optimizations
88 //===----------------------------------------------------------------------===//
89 
90 struct FortifiedLibCallOptimization : public LibCallOptimization {
91 protected:
92   virtual bool isFoldable(unsigned SizeCIOp, unsigned SizeArgOp,
93 			  bool isString) const = 0;
94 };
95 
96 struct InstFortifiedLibCallOptimization : public FortifiedLibCallOptimization {
97   CallInst *CI;
98 
99   bool isFoldable(unsigned SizeCIOp, unsigned SizeArgOp, bool isString) const {
100     if (CI->getArgOperand(SizeCIOp) == CI->getArgOperand(SizeArgOp))
101       return true;
102     if (ConstantInt *SizeCI =
103                            dyn_cast<ConstantInt>(CI->getArgOperand(SizeCIOp))) {
104       if (SizeCI->isAllOnesValue())
105         return true;
106       if (isString) {
107         uint64_t Len = GetStringLength(CI->getArgOperand(SizeArgOp));
108         // If the length is 0 we don't know how long it is and so we can't
109         // remove the check.
110         if (Len == 0) return false;
111         return SizeCI->getZExtValue() >= Len;
112       }
113       if (ConstantInt *Arg = dyn_cast<ConstantInt>(
114                                                   CI->getArgOperand(SizeArgOp)))
115         return SizeCI->getZExtValue() >= Arg->getZExtValue();
116     }
117     return false;
118   }
119 };
120 
121 struct MemCpyChkOpt : public InstFortifiedLibCallOptimization {
122   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
123     this->CI = CI;
124     FunctionType *FT = Callee->getFunctionType();
125 
126     // Check if this has the right signature.
127     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
128         !FT->getParamType(0)->isPointerTy() ||
129         !FT->getParamType(1)->isPointerTy() ||
130         FT->getParamType(2) != TD->getIntPtrType(FT->getParamType(0)) ||
131         FT->getParamType(3) != TD->getIntPtrType(FT->getParamType(1)))
132       return 0;
133 
134     if (isFoldable(3, 2, false)) {
135       B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
136                      CI->getArgOperand(2), 1);
137       return CI->getArgOperand(0);
138     }
139     return 0;
140   }
141 };
142 
143 struct MemMoveChkOpt : public InstFortifiedLibCallOptimization {
144   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
145     this->CI = CI;
146     FunctionType *FT = Callee->getFunctionType();
147 
148     // Check if this has the right signature.
149     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
150         !FT->getParamType(0)->isPointerTy() ||
151         !FT->getParamType(1)->isPointerTy() ||
152         FT->getParamType(2) != TD->getIntPtrType(FT->getParamType(0)) ||
153         FT->getParamType(3) != TD->getIntPtrType(FT->getParamType(1)))
154       return 0;
155 
156     if (isFoldable(3, 2, false)) {
157       B.CreateMemMove(CI->getArgOperand(0), CI->getArgOperand(1),
158                       CI->getArgOperand(2), 1);
159       return CI->getArgOperand(0);
160     }
161     return 0;
162   }
163 };
164 
165 struct MemSetChkOpt : public InstFortifiedLibCallOptimization {
166   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
167     this->CI = CI;
168     FunctionType *FT = Callee->getFunctionType();
169 
170     // Check if this has the right signature.
171     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
172         !FT->getParamType(0)->isPointerTy() ||
173         !FT->getParamType(1)->isIntegerTy() ||
174         FT->getParamType(2) != TD->getIntPtrType(FT->getParamType(0)) ||
175         FT->getParamType(3) != TD->getIntPtrType(FT->getParamType(0)))
176       return 0;
177 
178     if (isFoldable(3, 2, false)) {
179       Value *Val = B.CreateIntCast(CI->getArgOperand(1), B.getInt8Ty(),
180                                    false);
181       B.CreateMemSet(CI->getArgOperand(0), Val, CI->getArgOperand(2), 1);
182       return CI->getArgOperand(0);
183     }
184     return 0;
185   }
186 };
187 
188 struct StrCpyChkOpt : public InstFortifiedLibCallOptimization {
189   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
190     this->CI = CI;
191     StringRef Name = Callee->getName();
192     FunctionType *FT = Callee->getFunctionType();
193     LLVMContext &Context = CI->getParent()->getContext();
194 
195     // Check if this has the right signature.
196     if (FT->getNumParams() != 3 ||
197         FT->getReturnType() != FT->getParamType(0) ||
198         FT->getParamType(0) != FT->getParamType(1) ||
199         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
200         FT->getParamType(2) != TD->getIntPtrType(FT->getParamType(0)))
201       return 0;
202 
203     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
204     if (Dst == Src)      // __strcpy_chk(x,x)  -> x
205       return Src;
206 
207     // If a) we don't have any length information, or b) we know this will
208     // fit then just lower to a plain strcpy. Otherwise we'll keep our
209     // strcpy_chk call which may fail at runtime if the size is too long.
210     // TODO: It might be nice to get a maximum length out of the possible
211     // string lengths for varying.
212     if (isFoldable(2, 1, true)) {
213       Value *Ret = EmitStrCpy(Dst, Src, B, TD, TLI, Name.substr(2, 6));
214       return Ret;
215     } else {
216       // Maybe we can stil fold __strcpy_chk to __memcpy_chk.
217       uint64_t Len = GetStringLength(Src);
218       if (Len == 0) return 0;
219 
220       // This optimization require DataLayout.
221       if (!TD) return 0;
222 
223       Value *Ret =
224 	EmitMemCpyChk(Dst, Src,
225                       ConstantInt::get(TD->getIntPtrType(Dst->getType()),
226                       Len), CI->getArgOperand(2), B, TD, TLI);
227       return Ret;
228     }
229     return 0;
230   }
231 };
232 
233 struct StpCpyChkOpt : public InstFortifiedLibCallOptimization {
234   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
235     this->CI = CI;
236     StringRef Name = Callee->getName();
237     FunctionType *FT = Callee->getFunctionType();
238     LLVMContext &Context = CI->getParent()->getContext();
239 
240     // Check if this has the right signature.
241     if (FT->getNumParams() != 3 ||
242         FT->getReturnType() != FT->getParamType(0) ||
243         FT->getParamType(0) != FT->getParamType(1) ||
244         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
245         FT->getParamType(2) != TD->getIntPtrType(FT->getParamType(0)))
246       return 0;
247 
248     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
249     if (Dst == Src) {  // stpcpy(x,x)  -> x+strlen(x)
250       Value *StrLen = EmitStrLen(Src, B, TD, TLI);
251       return StrLen ? B.CreateInBoundsGEP(Dst, StrLen) : 0;
252     }
253 
254     // If a) we don't have any length information, or b) we know this will
255     // fit then just lower to a plain stpcpy. Otherwise we'll keep our
256     // stpcpy_chk call which may fail at runtime if the size is too long.
257     // TODO: It might be nice to get a maximum length out of the possible
258     // string lengths for varying.
259     if (isFoldable(2, 1, true)) {
260       Value *Ret = EmitStrCpy(Dst, Src, B, TD, TLI, Name.substr(2, 6));
261       return Ret;
262     } else {
263       // Maybe we can stil fold __stpcpy_chk to __memcpy_chk.
264       uint64_t Len = GetStringLength(Src);
265       if (Len == 0) return 0;
266 
267       // This optimization require DataLayout.
268       if (!TD) return 0;
269 
270       Type *PT = FT->getParamType(0);
271       Value *LenV = ConstantInt::get(TD->getIntPtrType(PT), Len);
272       Value *DstEnd = B.CreateGEP(Dst,
273                                   ConstantInt::get(TD->getIntPtrType(PT),
274                                                    Len - 1));
275       if (!EmitMemCpyChk(Dst, Src, LenV, CI->getArgOperand(2), B, TD, TLI))
276         return 0;
277       return DstEnd;
278     }
279     return 0;
280   }
281 };
282 
283 struct StrNCpyChkOpt : public InstFortifiedLibCallOptimization {
284   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
285     this->CI = CI;
286     StringRef Name = Callee->getName();
287     FunctionType *FT = Callee->getFunctionType();
288     LLVMContext &Context = CI->getParent()->getContext();
289 
290     // Check if this has the right signature.
291     if (FT->getNumParams() != 4 || FT->getReturnType() != FT->getParamType(0) ||
292         FT->getParamType(0) != FT->getParamType(1) ||
293         FT->getParamType(0) != Type::getInt8PtrTy(Context) ||
294         !FT->getParamType(2)->isIntegerTy() ||
295         FT->getParamType(3) != TD->getIntPtrType(FT->getParamType(0)))
296       return 0;
297 
298     if (isFoldable(3, 2, false)) {
299       Value *Ret = EmitStrNCpy(CI->getArgOperand(0), CI->getArgOperand(1),
300                                CI->getArgOperand(2), B, TD, TLI,
301                                Name.substr(2, 7));
302       return Ret;
303     }
304     return 0;
305   }
306 };
307 
308 //===----------------------------------------------------------------------===//
309 // String and Memory Library Call Optimizations
310 //===----------------------------------------------------------------------===//
311 
312 struct StrCatOpt : public LibCallOptimization {
313   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
314     // Verify the "strcat" function prototype.
315     FunctionType *FT = Callee->getFunctionType();
316     if (FT->getNumParams() != 2 ||
317         FT->getReturnType() != B.getInt8PtrTy() ||
318         FT->getParamType(0) != FT->getReturnType() ||
319         FT->getParamType(1) != FT->getReturnType())
320       return 0;
321 
322     // Extract some information from the instruction
323     Value *Dst = CI->getArgOperand(0);
324     Value *Src = CI->getArgOperand(1);
325 
326     // See if we can get the length of the input string.
327     uint64_t Len = GetStringLength(Src);
328     if (Len == 0) return 0;
329     --Len;  // Unbias length.
330 
331     // Handle the simple, do-nothing case: strcat(x, "") -> x
332     if (Len == 0)
333       return Dst;
334 
335     // These optimizations require DataLayout.
336     if (!TD) return 0;
337 
338     return emitStrLenMemCpy(Src, Dst, Len, B);
339   }
340 
341   Value *emitStrLenMemCpy(Value *Src, Value *Dst, uint64_t Len,
342                           IRBuilder<> &B) {
343     // We need to find the end of the destination string.  That's where the
344     // memory is to be moved to. We just generate a call to strlen.
345     Value *DstLen = EmitStrLen(Dst, B, TD, TLI);
346     if (!DstLen)
347       return 0;
348 
349     // Now that we have the destination's length, we must index into the
350     // destination's pointer to get the actual memcpy destination (end of
351     // the string .. we're concatenating).
352     Value *CpyDst = B.CreateGEP(Dst, DstLen, "endptr");
353 
354     // We have enough information to now generate the memcpy call to do the
355     // concatenation for us.  Make a memcpy to copy the nul byte with align = 1.
356     B.CreateMemCpy(CpyDst, Src,
357                    ConstantInt::get(TD->getIntPtrType(Src->getType()),
358                    Len + 1), 1);
359     return Dst;
360   }
361 };
362 
363 struct StrNCatOpt : public StrCatOpt {
364   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
365     // Verify the "strncat" function prototype.
366     FunctionType *FT = Callee->getFunctionType();
367     if (FT->getNumParams() != 3 ||
368         FT->getReturnType() != B.getInt8PtrTy() ||
369         FT->getParamType(0) != FT->getReturnType() ||
370         FT->getParamType(1) != FT->getReturnType() ||
371         !FT->getParamType(2)->isIntegerTy())
372       return 0;
373 
374     // Extract some information from the instruction
375     Value *Dst = CI->getArgOperand(0);
376     Value *Src = CI->getArgOperand(1);
377     uint64_t Len;
378 
379     // We don't do anything if length is not constant
380     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
381       Len = LengthArg->getZExtValue();
382     else
383       return 0;
384 
385     // See if we can get the length of the input string.
386     uint64_t SrcLen = GetStringLength(Src);
387     if (SrcLen == 0) return 0;
388     --SrcLen;  // Unbias length.
389 
390     // Handle the simple, do-nothing cases:
391     // strncat(x, "", c) -> x
392     // strncat(x,  c, 0) -> x
393     if (SrcLen == 0 || Len == 0) return Dst;
394 
395     // These optimizations require DataLayout.
396     if (!TD) return 0;
397 
398     // We don't optimize this case
399     if (Len < SrcLen) return 0;
400 
401     // strncat(x, s, c) -> strcat(x, s)
402     // s is constant so the strcat can be optimized further
403     return emitStrLenMemCpy(Src, Dst, SrcLen, B);
404   }
405 };
406 
407 struct StrChrOpt : public LibCallOptimization {
408   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
409     // Verify the "strchr" function prototype.
410     FunctionType *FT = Callee->getFunctionType();
411     if (FT->getNumParams() != 2 ||
412         FT->getReturnType() != B.getInt8PtrTy() ||
413         FT->getParamType(0) != FT->getReturnType() ||
414         !FT->getParamType(1)->isIntegerTy(32))
415       return 0;
416 
417     Value *SrcStr = CI->getArgOperand(0);
418 
419     // If the second operand is non-constant, see if we can compute the length
420     // of the input string and turn this into memchr.
421     ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
422     if (CharC == 0) {
423       // These optimizations require DataLayout.
424       if (!TD) return 0;
425 
426       uint64_t Len = GetStringLength(SrcStr);
427       if (Len == 0 || !FT->getParamType(1)->isIntegerTy(32))// memchr needs i32.
428         return 0;
429 
430       Type *PT = FT->getParamType(0);
431       return EmitMemChr(SrcStr, CI->getArgOperand(1), // include nul.
432                         ConstantInt::get(TD->getIntPtrType(PT), Len),
433                         B, TD, TLI);
434     }
435 
436     // Otherwise, the character is a constant, see if the first argument is
437     // a string literal.  If so, we can constant fold.
438     StringRef Str;
439     if (!getConstantStringInfo(SrcStr, Str))
440       return 0;
441 
442     // Compute the offset, make sure to handle the case when we're searching for
443     // zero (a weird way to spell strlen).
444     size_t I = CharC->getSExtValue() == 0 ?
445         Str.size() : Str.find(CharC->getSExtValue());
446     if (I == StringRef::npos) // Didn't find the char.  strchr returns null.
447       return Constant::getNullValue(CI->getType());
448 
449     // strchr(s+n,c)  -> gep(s+n+i,c)
450     return B.CreateGEP(SrcStr, B.getInt64(I), "strchr");
451   }
452 };
453 
454 struct StrRChrOpt : public LibCallOptimization {
455   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
456     // Verify the "strrchr" function prototype.
457     FunctionType *FT = Callee->getFunctionType();
458     if (FT->getNumParams() != 2 ||
459         FT->getReturnType() != B.getInt8PtrTy() ||
460         FT->getParamType(0) != FT->getReturnType() ||
461         !FT->getParamType(1)->isIntegerTy(32))
462       return 0;
463 
464     Value *SrcStr = CI->getArgOperand(0);
465     ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
466 
467     // Cannot fold anything if we're not looking for a constant.
468     if (!CharC)
469       return 0;
470 
471     StringRef Str;
472     if (!getConstantStringInfo(SrcStr, Str)) {
473       // strrchr(s, 0) -> strchr(s, 0)
474       if (TD && CharC->isZero())
475         return EmitStrChr(SrcStr, '\0', B, TD, TLI);
476       return 0;
477     }
478 
479     // Compute the offset.
480     size_t I = CharC->getSExtValue() == 0 ?
481         Str.size() : Str.rfind(CharC->getSExtValue());
482     if (I == StringRef::npos) // Didn't find the char. Return null.
483       return Constant::getNullValue(CI->getType());
484 
485     // strrchr(s+n,c) -> gep(s+n+i,c)
486     return B.CreateGEP(SrcStr, B.getInt64(I), "strrchr");
487   }
488 };
489 
490 struct StrCmpOpt : public LibCallOptimization {
491   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
492     // Verify the "strcmp" function prototype.
493     FunctionType *FT = Callee->getFunctionType();
494     if (FT->getNumParams() != 2 ||
495         !FT->getReturnType()->isIntegerTy(32) ||
496         FT->getParamType(0) != FT->getParamType(1) ||
497         FT->getParamType(0) != B.getInt8PtrTy())
498       return 0;
499 
500     Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
501     if (Str1P == Str2P)      // strcmp(x,x)  -> 0
502       return ConstantInt::get(CI->getType(), 0);
503 
504     StringRef Str1, Str2;
505     bool HasStr1 = getConstantStringInfo(Str1P, Str1);
506     bool HasStr2 = getConstantStringInfo(Str2P, Str2);
507 
508     // strcmp(x, y)  -> cnst  (if both x and y are constant strings)
509     if (HasStr1 && HasStr2)
510       return ConstantInt::get(CI->getType(), Str1.compare(Str2));
511 
512     if (HasStr1 && Str1.empty()) // strcmp("", x) -> -*x
513       return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"),
514                                       CI->getType()));
515 
516     if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x
517       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
518 
519     // strcmp(P, "x") -> memcmp(P, "x", 2)
520     uint64_t Len1 = GetStringLength(Str1P);
521     uint64_t Len2 = GetStringLength(Str2P);
522     if (Len1 && Len2) {
523       // These optimizations require DataLayout.
524       if (!TD) return 0;
525 
526       Type *PT = FT->getParamType(0);
527       return EmitMemCmp(Str1P, Str2P,
528                         ConstantInt::get(TD->getIntPtrType(PT),
529                         std::min(Len1, Len2)), B, TD, TLI);
530     }
531 
532     return 0;
533   }
534 };
535 
536 struct StrNCmpOpt : public LibCallOptimization {
537   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
538     // Verify the "strncmp" function prototype.
539     FunctionType *FT = Callee->getFunctionType();
540     if (FT->getNumParams() != 3 ||
541         !FT->getReturnType()->isIntegerTy(32) ||
542         FT->getParamType(0) != FT->getParamType(1) ||
543         FT->getParamType(0) != B.getInt8PtrTy() ||
544         !FT->getParamType(2)->isIntegerTy())
545       return 0;
546 
547     Value *Str1P = CI->getArgOperand(0), *Str2P = CI->getArgOperand(1);
548     if (Str1P == Str2P)      // strncmp(x,x,n)  -> 0
549       return ConstantInt::get(CI->getType(), 0);
550 
551     // Get the length argument if it is constant.
552     uint64_t Length;
553     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getArgOperand(2)))
554       Length = LengthArg->getZExtValue();
555     else
556       return 0;
557 
558     if (Length == 0) // strncmp(x,y,0)   -> 0
559       return ConstantInt::get(CI->getType(), 0);
560 
561     if (TD && Length == 1) // strncmp(x,y,1) -> memcmp(x,y,1)
562       return EmitMemCmp(Str1P, Str2P, CI->getArgOperand(2), B, TD, TLI);
563 
564     StringRef Str1, Str2;
565     bool HasStr1 = getConstantStringInfo(Str1P, Str1);
566     bool HasStr2 = getConstantStringInfo(Str2P, Str2);
567 
568     // strncmp(x, y)  -> cnst  (if both x and y are constant strings)
569     if (HasStr1 && HasStr2) {
570       StringRef SubStr1 = Str1.substr(0, Length);
571       StringRef SubStr2 = Str2.substr(0, Length);
572       return ConstantInt::get(CI->getType(), SubStr1.compare(SubStr2));
573     }
574 
575     if (HasStr1 && Str1.empty())  // strncmp("", x, n) -> -*x
576       return B.CreateNeg(B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"),
577                                       CI->getType()));
578 
579     if (HasStr2 && Str2.empty())  // strncmp(x, "", n) -> *x
580       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
581 
582     return 0;
583   }
584 };
585 
586 struct StrCpyOpt : public LibCallOptimization {
587   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
588     // Verify the "strcpy" function prototype.
589     FunctionType *FT = Callee->getFunctionType();
590     if (FT->getNumParams() != 2 ||
591         FT->getReturnType() != FT->getParamType(0) ||
592         FT->getParamType(0) != FT->getParamType(1) ||
593         FT->getParamType(0) != B.getInt8PtrTy())
594       return 0;
595 
596     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
597     if (Dst == Src)      // strcpy(x,x)  -> x
598       return Src;
599 
600     // These optimizations require DataLayout.
601     if (!TD) return 0;
602 
603     // See if we can get the length of the input string.
604     uint64_t Len = GetStringLength(Src);
605     if (Len == 0) return 0;
606 
607     // We have enough information to now generate the memcpy call to do the
608     // copy for us.  Make a memcpy to copy the nul byte with align = 1.
609     B.CreateMemCpy(Dst, Src,
610 		   ConstantInt::get(TD->getIntPtrType(Dst->getType()), Len), 1);
611     return Dst;
612   }
613 };
614 
615 struct StpCpyOpt: public LibCallOptimization {
616   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
617     // Verify the "stpcpy" function prototype.
618     FunctionType *FT = Callee->getFunctionType();
619     if (FT->getNumParams() != 2 ||
620         FT->getReturnType() != FT->getParamType(0) ||
621         FT->getParamType(0) != FT->getParamType(1) ||
622         FT->getParamType(0) != B.getInt8PtrTy())
623       return 0;
624 
625     // These optimizations require DataLayout.
626     if (!TD) return 0;
627 
628     Value *Dst = CI->getArgOperand(0), *Src = CI->getArgOperand(1);
629     if (Dst == Src) {  // stpcpy(x,x)  -> x+strlen(x)
630       Value *StrLen = EmitStrLen(Src, B, TD, TLI);
631       return StrLen ? B.CreateInBoundsGEP(Dst, StrLen) : 0;
632     }
633 
634     // See if we can get the length of the input string.
635     uint64_t Len = GetStringLength(Src);
636     if (Len == 0) return 0;
637 
638     Type *PT = FT->getParamType(0);
639     Value *LenV = ConstantInt::get(TD->getIntPtrType(PT), Len);
640     Value *DstEnd = B.CreateGEP(Dst,
641                                 ConstantInt::get(TD->getIntPtrType(PT),
642                                                  Len - 1));
643 
644     // We have enough information to now generate the memcpy call to do the
645     // copy for us.  Make a memcpy to copy the nul byte with align = 1.
646     B.CreateMemCpy(Dst, Src, LenV, 1);
647     return DstEnd;
648   }
649 };
650 
651 struct StrNCpyOpt : public LibCallOptimization {
652   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
653     FunctionType *FT = Callee->getFunctionType();
654     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
655         FT->getParamType(0) != FT->getParamType(1) ||
656         FT->getParamType(0) != B.getInt8PtrTy() ||
657         !FT->getParamType(2)->isIntegerTy())
658       return 0;
659 
660     Value *Dst = CI->getArgOperand(0);
661     Value *Src = CI->getArgOperand(1);
662     Value *LenOp = CI->getArgOperand(2);
663 
664     // See if we can get the length of the input string.
665     uint64_t SrcLen = GetStringLength(Src);
666     if (SrcLen == 0) return 0;
667     --SrcLen;
668 
669     if (SrcLen == 0) {
670       // strncpy(x, "", y) -> memset(x, '\0', y, 1)
671       B.CreateMemSet(Dst, B.getInt8('\0'), LenOp, 1);
672       return Dst;
673     }
674 
675     uint64_t Len;
676     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(LenOp))
677       Len = LengthArg->getZExtValue();
678     else
679       return 0;
680 
681     if (Len == 0) return Dst; // strncpy(x, y, 0) -> x
682 
683     // These optimizations require DataLayout.
684     if (!TD) return 0;
685 
686     // Let strncpy handle the zero padding
687     if (Len > SrcLen+1) return 0;
688 
689     Type *PT = FT->getParamType(0);
690     // strncpy(x, s, c) -> memcpy(x, s, c, 1) [s and c are constant]
691     B.CreateMemCpy(Dst, Src,
692                    ConstantInt::get(TD->getIntPtrType(PT), Len), 1);
693 
694     return Dst;
695   }
696 };
697 
698 struct StrLenOpt : public LibCallOptimization {
699   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
700     FunctionType *FT = Callee->getFunctionType();
701     if (FT->getNumParams() != 1 ||
702         FT->getParamType(0) != B.getInt8PtrTy() ||
703         !FT->getReturnType()->isIntegerTy())
704       return 0;
705 
706     Value *Src = CI->getArgOperand(0);
707 
708     // Constant folding: strlen("xyz") -> 3
709     if (uint64_t Len = GetStringLength(Src))
710       return ConstantInt::get(CI->getType(), Len-1);
711 
712     // strlen(x) != 0 --> *x != 0
713     // strlen(x) == 0 --> *x == 0
714     if (isOnlyUsedInZeroEqualityComparison(CI))
715       return B.CreateZExt(B.CreateLoad(Src, "strlenfirst"), CI->getType());
716     return 0;
717   }
718 };
719 
720 struct StrPBrkOpt : public LibCallOptimization {
721   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
722     FunctionType *FT = Callee->getFunctionType();
723     if (FT->getNumParams() != 2 ||
724         FT->getParamType(0) != B.getInt8PtrTy() ||
725         FT->getParamType(1) != FT->getParamType(0) ||
726         FT->getReturnType() != FT->getParamType(0))
727       return 0;
728 
729     StringRef S1, S2;
730     bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1);
731     bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
732 
733     // strpbrk(s, "") -> NULL
734     // strpbrk("", s) -> NULL
735     if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))
736       return Constant::getNullValue(CI->getType());
737 
738     // Constant folding.
739     if (HasS1 && HasS2) {
740       size_t I = S1.find_first_of(S2);
741       if (I == std::string::npos) // No match.
742         return Constant::getNullValue(CI->getType());
743 
744       return B.CreateGEP(CI->getArgOperand(0), B.getInt64(I), "strpbrk");
745     }
746 
747     // strpbrk(s, "a") -> strchr(s, 'a')
748     if (TD && HasS2 && S2.size() == 1)
749       return EmitStrChr(CI->getArgOperand(0), S2[0], B, TD, TLI);
750 
751     return 0;
752   }
753 };
754 
755 struct StrToOpt : public LibCallOptimization {
756   virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
757     FunctionType *FT = Callee->getFunctionType();
758     if ((FT->getNumParams() != 2 && FT->getNumParams() != 3) ||
759         !FT->getParamType(0)->isPointerTy() ||
760         !FT->getParamType(1)->isPointerTy())
761       return 0;
762 
763     Value *EndPtr = CI->getArgOperand(1);
764     if (isa<ConstantPointerNull>(EndPtr)) {
765       // With a null EndPtr, this function won't capture the main argument.
766       // It would be readonly too, except that it still may write to errno.
767       CI->addAttribute(1, Attributes::get(Callee->getContext(),
768                                           Attributes::NoCapture));
769     }
770 
771     return 0;
772   }
773 };
774 
775 } // End anonymous namespace.
776 
777 namespace llvm {
778 
779 class LibCallSimplifierImpl {
780   const DataLayout *TD;
781   const TargetLibraryInfo *TLI;
782   StringMap<LibCallOptimization*> Optimizations;
783 
784   // Fortified library call optimizations.
785   MemCpyChkOpt MemCpyChk;
786   MemMoveChkOpt MemMoveChk;
787   MemSetChkOpt MemSetChk;
788   StrCpyChkOpt StrCpyChk;
789   StpCpyChkOpt StpCpyChk;
790   StrNCpyChkOpt StrNCpyChk;
791 
792   // String and memory library call optimizations.
793   StrCatOpt StrCat;
794   StrNCatOpt StrNCat;
795   StrChrOpt StrChr;
796   StrRChrOpt StrRChr;
797   StrCmpOpt StrCmp;
798   StrNCmpOpt StrNCmp;
799   StrCpyOpt StrCpy;
800   StpCpyOpt StpCpy;
801   StrNCpyOpt StrNCpy;
802   StrLenOpt StrLen;
803   StrPBrkOpt StrPBrk;
804   StrToOpt StrTo;
805 
806   void initOptimizations();
807 public:
808   LibCallSimplifierImpl(const DataLayout *TD, const TargetLibraryInfo *TLI) {
809     this->TD = TD;
810     this->TLI = TLI;
811   }
812 
813   Value *optimizeCall(CallInst *CI);
814 };
815 
816 void LibCallSimplifierImpl::initOptimizations() {
817   // Fortified library call optimizations.
818   Optimizations["__memcpy_chk"] = &MemCpyChk;
819   Optimizations["__memmove_chk"] = &MemMoveChk;
820   Optimizations["__memset_chk"] = &MemSetChk;
821   Optimizations["__strcpy_chk"] = &StrCpyChk;
822   Optimizations["__stpcpy_chk"] = &StpCpyChk;
823   Optimizations["__strncpy_chk"] = &StrNCpyChk;
824   Optimizations["__stpncpy_chk"] = &StrNCpyChk;
825 
826   // String and memory library call optimizations.
827   Optimizations["strcat"] = &StrCat;
828   Optimizations["strncat"] = &StrNCat;
829   Optimizations["strchr"] = &StrChr;
830   Optimizations["strrchr"] = &StrRChr;
831   Optimizations["strcmp"] = &StrCmp;
832   Optimizations["strncmp"] = &StrNCmp;
833   Optimizations["strcpy"] = &StrCpy;
834   Optimizations["stpcpy"] = &StpCpy;
835   Optimizations["strncpy"] = &StrNCpy;
836   Optimizations["strlen"] = &StrLen;
837   Optimizations["strpbrk"] = &StrPBrk;
838   Optimizations["strtol"] = &StrTo;
839   Optimizations["strtod"] = &StrTo;
840   Optimizations["strtof"] = &StrTo;
841   Optimizations["strtoul"] = &StrTo;
842   Optimizations["strtoll"] = &StrTo;
843   Optimizations["strtold"] = &StrTo;
844   Optimizations["strtoull"] = &StrTo;
845 }
846 
847 Value *LibCallSimplifierImpl::optimizeCall(CallInst *CI) {
848   if (Optimizations.empty())
849     initOptimizations();
850 
851   Function *Callee = CI->getCalledFunction();
852   LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
853   if (LCO) {
854     IRBuilder<> Builder(CI);
855     return LCO->optimizeCall(CI, TD, TLI, Builder);
856   }
857   return 0;
858 }
859 
860 LibCallSimplifier::LibCallSimplifier(const DataLayout *TD,
861                                      const TargetLibraryInfo *TLI) {
862   Impl = new LibCallSimplifierImpl(TD, TLI);
863 }
864 
865 LibCallSimplifier::~LibCallSimplifier() {
866   delete Impl;
867 }
868 
869 Value *LibCallSimplifier::optimizeCall(CallInst *CI) {
870   return Impl->optimizeCall(CI);
871 }
872 
873 }
874