LLVM API Documentation

SimplifyLibCalls.cpp

Go to the documentation of this file.
00001 //===- SimplifyLibCalls.cpp - Optimize specific well-known library calls --===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements a simple pass that applies a variety of small
00011 // optimizations for calls to specific well-known function calls (e.g. runtime
00012 // library functions). For example, a call to the function "exit(3)" that
00013 // occurs within the main() function can be transformed into a simple "return 3"
00014 // instruction. Any optimization that takes this form (replace call to library
00015 // function with simpler code that provides the same result) belongs in this
00016 // file.
00017 //
00018 //===----------------------------------------------------------------------===//
00019 
00020 #define DEBUG_TYPE "simplify-libcalls"
00021 #include "llvm/Transforms/Scalar.h"
00022 #include "llvm/Intrinsics.h"
00023 #include "llvm/LLVMContext.h"
00024 #include "llvm/Module.h"
00025 #include "llvm/Pass.h"
00026 #include "llvm/Support/IRBuilder.h"
00027 #include "llvm/Analysis/ValueTracking.h"
00028 #include "llvm/Target/TargetData.h"
00029 #include "llvm/ADT/SmallPtrSet.h"
00030 #include "llvm/ADT/StringMap.h"
00031 #include "llvm/ADT/Statistic.h"
00032 #include "llvm/ADT/STLExtras.h"
00033 #include "llvm/Support/Compiler.h"
00034 #include "llvm/Support/Debug.h"
00035 #include "llvm/Support/raw_ostream.h"
00036 #include "llvm/Config/config.h"
00037 using namespace llvm;
00038 
00039 STATISTIC(NumSimplified, "Number of library calls simplified");
00040 STATISTIC(NumAnnotated, "Number of attributes added to library functions");
00041 
00042 //===----------------------------------------------------------------------===//
00043 // Optimizer Base Class
00044 //===----------------------------------------------------------------------===//
00045 
00046 /// This class is the abstract base class for the set of optimizations that
00047 /// corresponds to one library call.
00048 namespace {
00049 class VISIBILITY_HIDDEN LibCallOptimization {
00050 protected:
00051   Function *Caller;
00052   const TargetData *TD;
00053   LLVMContext* Context;
00054 public:
00055   LibCallOptimization() { }
00056   virtual ~LibCallOptimization() {}
00057 
00058   /// CallOptimizer - This pure virtual method is implemented by base classes to
00059   /// do various optimizations.  If this returns null then no transformation was
00060   /// performed.  If it returns CI, then it transformed the call and CI is to be
00061   /// deleted.  If it returns something else, replace CI with the new value and
00062   /// delete CI.
00063   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) 
00064     =0;
00065   
00066   Value *OptimizeCall(CallInst *CI, const TargetData *TD, IRBuilder<> &B) {
00067     Caller = CI->getParent()->getParent();
00068     this->TD = TD;
00069     if (CI->getCalledFunction())
00070       Context = &CI->getCalledFunction()->getContext();
00071     return CallOptimizer(CI->getCalledFunction(), CI, B);
00072   }
00073 
00074   /// CastToCStr - Return V if it is an i8*, otherwise cast it to i8*.
00075   Value *CastToCStr(Value *V, IRBuilder<> &B);
00076 
00077   /// EmitStrLen - Emit a call to the strlen function to the builder, for the
00078   /// specified pointer.  Ptr is required to be some pointer type, and the
00079   /// return value has 'intptr_t' type.
00080   Value *EmitStrLen(Value *Ptr, IRBuilder<> &B);
00081   
00082   /// EmitMemCpy - Emit a call to the memcpy function to the builder.  This
00083   /// always expects that the size has type 'intptr_t' and Dst/Src are pointers.
00084   Value *EmitMemCpy(Value *Dst, Value *Src, Value *Len, 
00085                     unsigned Align, IRBuilder<> &B);
00086   
00087   /// EmitMemChr - Emit a call to the memchr function.  This assumes that Ptr is
00088   /// a pointer, Val is an i32 value, and Len is an 'intptr_t' value.
00089   Value *EmitMemChr(Value *Ptr, Value *Val, Value *Len, IRBuilder<> &B);
00090 
00091   /// EmitMemCmp - Emit a call to the memcmp function.
00092   Value *EmitMemCmp(Value *Ptr1, Value *Ptr2, Value *Len, IRBuilder<> &B);
00093 
00094   /// EmitMemSet - Emit a call to the memset function
00095   Value *EmitMemSet(Value *Dst, Value *Val, Value *Len, IRBuilder<> &B);
00096 
00097   /// EmitUnaryFloatFnCall - Emit a call to the unary function named 'Name' (e.g.
00098   /// 'floor').  This function is known to take a single of type matching 'Op'
00099   /// and returns one value with the same type.  If 'Op' is a long double, 'l'
00100   /// is added as the suffix of name, if 'Op' is a float, we add a 'f' suffix.
00101   Value *EmitUnaryFloatFnCall(Value *Op, const char *Name, IRBuilder<> &B);
00102   
00103   /// EmitPutChar - Emit a call to the putchar function.  This assumes that Char
00104   /// is an integer.
00105   void EmitPutChar(Value *Char, IRBuilder<> &B);
00106   
00107   /// EmitPutS - Emit a call to the puts function.  This assumes that Str is
00108   /// some pointer.
00109   void EmitPutS(Value *Str, IRBuilder<> &B);
00110     
00111   /// EmitFPutC - Emit a call to the fputc function.  This assumes that Char is
00112   /// an i32, and File is a pointer to FILE.
00113   void EmitFPutC(Value *Char, Value *File, IRBuilder<> &B);
00114   
00115   /// EmitFPutS - Emit a call to the puts function.  Str is required to be a
00116   /// pointer and File is a pointer to FILE.
00117   void EmitFPutS(Value *Str, Value *File, IRBuilder<> &B);
00118   
00119   /// EmitFWrite - Emit a call to the fwrite function.  This assumes that Ptr is
00120   /// a pointer, Size is an 'intptr_t', and File is a pointer to FILE.
00121   void EmitFWrite(Value *Ptr, Value *Size, Value *File, IRBuilder<> &B);
00122   
00123 };
00124 } // End anonymous namespace.
00125 
00126 /// CastToCStr - Return V if it is an i8*, otherwise cast it to i8*.
00127 Value *LibCallOptimization::CastToCStr(Value *V, IRBuilder<> &B) {
00128   return
00129         B.CreateBitCast(V, PointerType::getUnqual(Type::getInt8Ty(*Context)), "cstr");
00130 }
00131 
00132 /// EmitStrLen - Emit a call to the strlen function to the builder, for the
00133 /// specified pointer.  This always returns an integer value of size intptr_t.
00134 Value *LibCallOptimization::EmitStrLen(Value *Ptr, IRBuilder<> &B) {
00135   Module *M = Caller->getParent();
00136   AttributeWithIndex AWI[2];
00137   AWI[0] = AttributeWithIndex::get(1, Attribute::NoCapture);
00138   AWI[1] = AttributeWithIndex::get(~0u, Attribute::ReadOnly |
00139                                    Attribute::NoUnwind);
00140 
00141   Constant *StrLen =M->getOrInsertFunction("strlen", AttrListPtr::get(AWI, 2),
00142                                            TD->getIntPtrType(*Context),
00143                                     PointerType::getUnqual(Type::getInt8Ty(*Context)),
00144                                            NULL);
00145   CallInst *CI = B.CreateCall(StrLen, CastToCStr(Ptr, B), "strlen");
00146   if (const Function *F = dyn_cast<Function>(StrLen->stripPointerCasts()))
00147     CI->setCallingConv(F->getCallingConv());
00148 
00149   return CI;
00150 }
00151 
00152 /// EmitMemCpy - Emit a call to the memcpy function to the builder.  This always
00153 /// expects that the size has type 'intptr_t' and Dst/Src are pointers.
00154 Value *LibCallOptimization::EmitMemCpy(Value *Dst, Value *Src, Value *Len,
00155                                        unsigned Align, IRBuilder<> &B) {
00156   Module *M = Caller->getParent();
00157   Intrinsic::ID IID = Intrinsic::memcpy;
00158   const Type *Tys[1];
00159   Tys[0] = Len->getType();
00160   Value *MemCpy = Intrinsic::getDeclaration(M, IID, Tys, 1);
00161   return B.CreateCall4(MemCpy, CastToCStr(Dst, B), CastToCStr(Src, B), Len,
00162                        ConstantInt::get(Type::getInt32Ty(*Context), Align));
00163 }
00164 
00165 /// EmitMemChr - Emit a call to the memchr function.  This assumes that Ptr is
00166 /// a pointer, Val is an i32 value, and Len is an 'intptr_t' value.
00167 Value *LibCallOptimization::EmitMemChr(Value *Ptr, Value *Val,
00168                                        Value *Len, IRBuilder<> &B) {
00169   Module *M = Caller->getParent();
00170   AttributeWithIndex AWI;
00171   AWI = AttributeWithIndex::get(~0u, Attribute::ReadOnly | Attribute::NoUnwind);
00172 
00173   Value *MemChr = M->getOrInsertFunction("memchr", AttrListPtr::get(&AWI, 1),
00174                                     PointerType::getUnqual(Type::getInt8Ty(*Context)),
00175                                     PointerType::getUnqual(Type::getInt8Ty(*Context)),
00176                                          Type::getInt32Ty(*Context), TD->getIntPtrType(*Context),
00177                                          NULL);
00178   CallInst *CI = B.CreateCall3(MemChr, CastToCStr(Ptr, B), Val, Len, "memchr");
00179 
00180   if (const Function *F = dyn_cast<Function>(MemChr->stripPointerCasts()))
00181     CI->setCallingConv(F->getCallingConv());
00182 
00183   return CI;
00184 }
00185 
00186 /// EmitMemCmp - Emit a call to the memcmp function.
00187 Value *LibCallOptimization::EmitMemCmp(Value *Ptr1, Value *Ptr2,
00188                                        Value *Len, IRBuilder<> &B) {
00189   Module *M = Caller->getParent();
00190   AttributeWithIndex AWI[3];
00191   AWI[0] = AttributeWithIndex::get(1, Attribute::NoCapture);
00192   AWI[1] = AttributeWithIndex::get(2, Attribute::NoCapture);
00193   AWI[2] = AttributeWithIndex::get(~0u, Attribute::ReadOnly |
00194                                    Attribute::NoUnwind);
00195 
00196   Value *MemCmp = M->getOrInsertFunction("memcmp", AttrListPtr::get(AWI, 3),
00197                                          Type::getInt32Ty(*Context),
00198                                     PointerType::getUnqual(Type::getInt8Ty(*Context)),
00199                                     PointerType::getUnqual(Type::getInt8Ty(*Context)),
00200                                          TD->getIntPtrType(*Context), NULL);
00201   CallInst *CI = B.CreateCall3(MemCmp, CastToCStr(Ptr1, B), CastToCStr(Ptr2, B),
00202                                Len, "memcmp");
00203 
00204   if (const Function *F = dyn_cast<Function>(MemCmp->stripPointerCasts()))
00205     CI->setCallingConv(F->getCallingConv());
00206 
00207   return CI;
00208 }
00209 
00210 /// EmitMemSet - Emit a call to the memset function
00211 Value *LibCallOptimization::EmitMemSet(Value *Dst, Value *Val,
00212                                        Value *Len, IRBuilder<> &B) {
00213  Module *M = Caller->getParent();
00214  Intrinsic::ID IID = Intrinsic::memset;
00215  const Type *Tys[1];
00216  Tys[0] = Len->getType();
00217  Value *MemSet = Intrinsic::getDeclaration(M, IID, Tys, 1);
00218  Value *Align = ConstantInt::get(Type::getInt32Ty(*Context), 1);
00219  return B.CreateCall4(MemSet, CastToCStr(Dst, B), Val, Len, Align);
00220 }
00221 
00222 /// EmitUnaryFloatFnCall - Emit a call to the unary function named 'Name' (e.g.
00223 /// 'floor').  This function is known to take a single of type matching 'Op' and
00224 /// returns one value with the same type.  If 'Op' is a long double, 'l' is
00225 /// added as the suffix of name, if 'Op' is a float, we add a 'f' suffix.
00226 Value *LibCallOptimization::EmitUnaryFloatFnCall(Value *Op, const char *Name,
00227                                                  IRBuilder<> &B) {
00228   char NameBuffer[20];
00229   if (Op->getType() != Type::getDoubleTy(*Context)) {
00230     // If we need to add a suffix, copy into NameBuffer.
00231     unsigned NameLen = strlen(Name);
00232     assert(NameLen < sizeof(NameBuffer)-2);
00233     memcpy(NameBuffer, Name, NameLen);
00234     if (Op->getType() == Type::getFloatTy(*Context))
00235       NameBuffer[NameLen] = 'f';  // floorf
00236     else
00237       NameBuffer[NameLen] = 'l';  // floorl
00238     NameBuffer[NameLen+1] = 0;
00239     Name = NameBuffer;
00240   }
00241 
00242   Module *M = Caller->getParent();
00243   Value *Callee = M->getOrInsertFunction(Name, Op->getType(),
00244                                          Op->getType(), NULL);
00245   CallInst *CI = B.CreateCall(Callee, Op, Name);
00246 
00247   if (const Function *F = dyn_cast<Function>(Callee->stripPointerCasts()))
00248     CI->setCallingConv(F->getCallingConv());
00249 
00250   return CI;
00251 }
00252 
00253 /// EmitPutChar - Emit a call to the putchar function.  This assumes that Char
00254 /// is an integer.
00255 void LibCallOptimization::EmitPutChar(Value *Char, IRBuilder<> &B) {
00256   Module *M = Caller->getParent();
00257   Value *PutChar = M->getOrInsertFunction("putchar", Type::getInt32Ty(*Context),
00258                                           Type::getInt32Ty(*Context), NULL);
00259   CallInst *CI = B.CreateCall(PutChar,
00260                               B.CreateIntCast(Char, Type::getInt32Ty(*Context), "chari"),
00261                               "putchar");
00262 
00263   if (const Function *F = dyn_cast<Function>(PutChar->stripPointerCasts()))
00264     CI->setCallingConv(F->getCallingConv());
00265 }
00266 
00267 /// EmitPutS - Emit a call to the puts function.  This assumes that Str is
00268 /// some pointer.
00269 void LibCallOptimization::EmitPutS(Value *Str, IRBuilder<> &B) {
00270   Module *M = Caller->getParent();
00271   AttributeWithIndex AWI[2];
00272   AWI[0] = AttributeWithIndex::get(1, Attribute::NoCapture);
00273   AWI[1] = AttributeWithIndex::get(~0u, Attribute::NoUnwind);
00274 
00275   Value *PutS = M->getOrInsertFunction("puts", AttrListPtr::get(AWI, 2),
00276                                        Type::getInt32Ty(*Context),
00277                                     PointerType::getUnqual(Type::getInt8Ty(*Context)),
00278                                        NULL);
00279   CallInst *CI = B.CreateCall(PutS, CastToCStr(Str, B), "puts");
00280   if (const Function *F = dyn_cast<Function>(PutS->stripPointerCasts()))
00281     CI->setCallingConv(F->getCallingConv());
00282 
00283 }
00284 
00285 /// EmitFPutC - Emit a call to the fputc function.  This assumes that Char is
00286 /// an integer and File is a pointer to FILE.
00287 void LibCallOptimization::EmitFPutC(Value *Char, Value *File, IRBuilder<> &B) {
00288   Module *M = Caller->getParent();
00289   AttributeWithIndex AWI[2];
00290   AWI[0] = AttributeWithIndex::get(2, Attribute::NoCapture);
00291   AWI[1] = AttributeWithIndex::get(~0u, Attribute::NoUnwind);
00292   Constant *F;
00293   if (isa<PointerType>(File->getType()))
00294     F = M->getOrInsertFunction("fputc", AttrListPtr::get(AWI, 2), Type::getInt32Ty(*Context),
00295                                Type::getInt32Ty(*Context), File->getType(), NULL);
00296   else
00297     F = M->getOrInsertFunction("fputc", Type::getInt32Ty(*Context), Type::getInt32Ty(*Context),
00298                                File->getType(), NULL);
00299   Char = B.CreateIntCast(Char, Type::getInt32Ty(*Context), "chari");
00300   CallInst *CI = B.CreateCall2(F, Char, File, "fputc");
00301 
00302   if (const Function *Fn = dyn_cast<Function>(F->stripPointerCasts()))
00303     CI->setCallingConv(Fn->getCallingConv());
00304 }
00305 
00306 /// EmitFPutS - Emit a call to the puts function.  Str is required to be a
00307 /// pointer and File is a pointer to FILE.
00308 void LibCallOptimization::EmitFPutS(Value *Str, Value *File, IRBuilder<> &B) {
00309   Module *M = Caller->getParent();
00310   AttributeWithIndex AWI[3];
00311   AWI[0] = AttributeWithIndex::get(1, Attribute::NoCapture);
00312   AWI[1] = AttributeWithIndex::get(2, Attribute::NoCapture);
00313   AWI[2] = AttributeWithIndex::get(~0u, Attribute::NoUnwind);
00314   Constant *F;
00315   if (isa<PointerType>(File->getType()))
00316     F = M->getOrInsertFunction("fputs", AttrListPtr::get(AWI, 3), Type::getInt32Ty(*Context),
00317                                PointerType::getUnqual(Type::getInt8Ty(*Context)),
00318                                File->getType(), NULL);
00319   else
00320     F = M->getOrInsertFunction("fputs", Type::getInt32Ty(*Context),
00321                                PointerType::getUnqual(Type::getInt8Ty(*Context)),
00322                                File->getType(), NULL);
00323   CallInst *CI = B.CreateCall2(F, CastToCStr(Str, B), File, "fputs");
00324 
00325   if (const Function *Fn = dyn_cast<Function>(F->stripPointerCasts()))
00326     CI->setCallingConv(Fn->getCallingConv());
00327 }
00328 
00329 /// EmitFWrite - Emit a call to the fwrite function.  This assumes that Ptr is
00330 /// a pointer, Size is an 'intptr_t', and File is a pointer to FILE.
00331 void LibCallOptimization::EmitFWrite(Value *Ptr, Value *Size, Value *File,
00332                                      IRBuilder<> &B) {
00333   Module *M = Caller->getParent();
00334   AttributeWithIndex AWI[3];
00335   AWI[0] = AttributeWithIndex::get(1, Attribute::NoCapture);
00336   AWI[1] = AttributeWithIndex::get(4, Attribute::NoCapture);
00337   AWI[2] = AttributeWithIndex::get(~0u, Attribute::NoUnwind);
00338   Constant *F;
00339   if (isa<PointerType>(File->getType()))
00340     F = M->getOrInsertFunction("fwrite", AttrListPtr::get(AWI, 3),
00341                                TD->getIntPtrType(*Context),
00342                                PointerType::getUnqual(Type::getInt8Ty(*Context)),
00343                                TD->getIntPtrType(*Context), TD->getIntPtrType(*Context),
00344                                File->getType(), NULL);
00345   else
00346     F = M->getOrInsertFunction("fwrite", TD->getIntPtrType(*Context),
00347                                PointerType::getUnqual(Type::getInt8Ty(*Context)),
00348                                TD->getIntPtrType(*Context), TD->getIntPtrType(*Context),
00349                                File->getType(), NULL);
00350   CallInst *CI = B.CreateCall4(F, CastToCStr(Ptr, B), Size,
00351                         ConstantInt::get(TD->getIntPtrType(*Context), 1), File);
00352 
00353   if (const Function *Fn = dyn_cast<Function>(F->stripPointerCasts()))
00354     CI->setCallingConv(Fn->getCallingConv());
00355 }
00356 
00357 //===----------------------------------------------------------------------===//
00358 // Helper Functions
00359 //===----------------------------------------------------------------------===//
00360 
00361 /// GetStringLengthH - If we can compute the length of the string pointed to by
00362 /// the specified pointer, return 'len+1'.  If we can't, return 0.
00363 static uint64_t GetStringLengthH(Value *V, SmallPtrSet<PHINode*, 32> &PHIs) {
00364   // Look through noop bitcast instructions.
00365   if (BitCastInst *BCI = dyn_cast<BitCastInst>(V))
00366     return GetStringLengthH(BCI->getOperand(0), PHIs);
00367   
00368   // If this is a PHI node, there are two cases: either we have already seen it
00369   // or we haven't.
00370   if (PHINode *PN = dyn_cast<PHINode>(V)) {
00371     if (!PHIs.insert(PN))
00372       return ~0ULL;  // already in the set.
00373     
00374     // If it was new, see if all the input strings are the same length.
00375     uint64_t LenSoFar = ~0ULL;
00376     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
00377       uint64_t Len = GetStringLengthH(PN->getIncomingValue(i), PHIs);
00378       if (Len == 0) return 0; // Unknown length -> unknown.
00379       
00380       if (Len == ~0ULL) continue;
00381       
00382       if (Len != LenSoFar && LenSoFar != ~0ULL)
00383         return 0;    // Disagree -> unknown.
00384       LenSoFar = Len;
00385     }
00386     
00387     // Success, all agree.
00388     return LenSoFar;
00389   }
00390   
00391   // strlen(select(c,x,y)) -> strlen(x) ^ strlen(y)
00392   if (SelectInst *SI = dyn_cast<SelectInst>(V)) {
00393     uint64_t Len1 = GetStringLengthH(SI->getTrueValue(), PHIs);
00394     if (Len1 == 0) return 0;
00395     uint64_t Len2 = GetStringLengthH(SI->getFalseValue(), PHIs);
00396     if (Len2 == 0) return 0;
00397     if (Len1 == ~0ULL) return Len2;
00398     if (Len2 == ~0ULL) return Len1;
00399     if (Len1 != Len2) return 0;
00400     return Len1;
00401   }
00402   
00403   // If the value is not a GEP instruction nor a constant expression with a
00404   // GEP instruction, then return unknown.
00405   User *GEP = 0;
00406   if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(V)) {
00407     GEP = GEPI;
00408   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
00409     if (CE->getOpcode() != Instruction::GetElementPtr)
00410       return 0;
00411     GEP = CE;
00412   } else {
00413     return 0;
00414   }
00415   
00416   // Make sure the GEP has exactly three arguments.
00417   if (GEP->getNumOperands() != 3)
00418     return 0;
00419   
00420   // Check to make sure that the first operand of the GEP is an integer and
00421   // has value 0 so that we are sure we're indexing into the initializer.
00422   if (ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(1))) {
00423     if (!Idx->isZero())
00424       return 0;
00425   } else
00426     return 0;
00427   
00428   // If the second index isn't a ConstantInt, then this is a variable index
00429   // into the array.  If this occurs, we can't say anything meaningful about
00430   // the string.
00431   uint64_t StartIdx = 0;
00432   if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(2)))
00433     StartIdx = CI->getZExtValue();
00434   else
00435     return 0;
00436   
00437   // The GEP instruction, constant or instruction, must reference a global
00438   // variable that is a constant and is initialized. The referenced constant
00439   // initializer is the array that we'll use for optimization.
00440   GlobalVariable* GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
00441   if (!GV || !GV->isConstant() || !GV->hasInitializer() ||
00442       GV->mayBeOverridden())
00443     return 0;
00444   Constant *GlobalInit = GV->getInitializer();
00445   
00446   // Handle the ConstantAggregateZero case, which is a degenerate case. The
00447   // initializer is constant zero so the length of the string must be zero.
00448   if (isa<ConstantAggregateZero>(GlobalInit))
00449     return 1;  // Len = 0 offset by 1.
00450   
00451   // Must be a Constant Array
00452   ConstantArray *Array = dyn_cast<ConstantArray>(GlobalInit);
00453   if (!Array ||
00454       Array->getType()->getElementType() != Type::getInt8Ty(V->getContext()))
00455     return false;
00456   
00457   // Get the number of elements in the array
00458   uint64_t NumElts = Array->getType()->getNumElements();
00459   
00460   // Traverse the constant array from StartIdx (derived above) which is
00461   // the place the GEP refers to in the array.
00462   for (unsigned i = StartIdx; i != NumElts; ++i) {
00463     Constant *Elt = Array->getOperand(i);
00464     ConstantInt *CI = dyn_cast<ConstantInt>(Elt);
00465     if (!CI) // This array isn't suitable, non-int initializer.
00466       return 0;
00467     if (CI->isZero())
00468       return i-StartIdx+1; // We found end of string, success!
00469   }
00470   
00471   return 0; // The array isn't null terminated, conservatively return 'unknown'.
00472 }
00473 
00474 /// GetStringLength - If we can compute the length of the string pointed to by
00475 /// the specified pointer, return 'len+1'.  If we can't, return 0.
00476 static uint64_t GetStringLength(Value *V) {
00477   if (!isa<PointerType>(V->getType())) return 0;
00478   
00479   SmallPtrSet<PHINode*, 32> PHIs;
00480   uint64_t Len = GetStringLengthH(V, PHIs);
00481   // If Len is ~0ULL, we had an infinite phi cycle: this is dead code, so return
00482   // an empty string as a length.
00483   return Len == ~0ULL ? 1 : Len;
00484 }
00485 
00486 /// IsOnlyUsedInZeroEqualityComparison - Return true if it only matters that the
00487 /// value is equal or not-equal to zero. 
00488 static bool IsOnlyUsedInZeroEqualityComparison(Value *V) {
00489   for (Value::use_iterator UI = V->use_begin(), E = V->use_end();
00490        UI != E; ++UI) {
00491     if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI))
00492       if (IC->isEquality())
00493         if (Constant *C = dyn_cast<Constant>(IC->getOperand(1)))
00494           if (C->isNullValue())
00495             continue;
00496     // Unknown instruction.
00497     return false;
00498   }
00499   return true;
00500 }
00501 
00502 //===----------------------------------------------------------------------===//
00503 // Miscellaneous LibCall Optimizations
00504 //===----------------------------------------------------------------------===//
00505 
00506 namespace {
00507 //===---------------------------------------===//
00508 // 'exit' Optimizations
00509 
00510 /// ExitOpt - int main() { exit(4); } --> int main() { return 4; }
00511 struct VISIBILITY_HIDDEN ExitOpt : public LibCallOptimization {
00512   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
00513     // Verify we have a reasonable prototype for exit.
00514     if (Callee->arg_size() == 0 || !CI->use_empty())
00515       return 0;
00516 
00517     // Verify the caller is main, and that the result type of main matches the
00518     // argument type of exit.
00519     if (Caller->getName() != "main" || !Caller->hasExternalLinkage() ||
00520         Caller->getReturnType() != CI->getOperand(1)->getType())
00521       return 0;
00522 
00523     TerminatorInst *OldTI = CI->getParent()->getTerminator();
00524 
00525     // Drop all successor phi node entries.
00526     for (unsigned i = 0, e = OldTI->getNumSuccessors(); i != e; ++i)
00527       OldTI->getSuccessor(i)->removePredecessor(CI->getParent());
00528 
00529     // Remove all instructions after the exit.
00530     BasicBlock::iterator Dead = CI, E = OldTI; ++Dead;
00531     while (Dead != E) {
00532       BasicBlock::iterator Next = next(Dead);
00533       if (Dead->getType() != Type::getVoidTy(*Context))
00534         Dead->replaceAllUsesWith(UndefValue::get(Dead->getType()));
00535       Dead->eraseFromParent();
00536       Dead = Next;
00537     }
00538 
00539     // Insert a return instruction.
00540     OldTI->eraseFromParent();
00541     B.SetInsertPoint(B.GetInsertBlock());
00542     B.CreateRet(CI->getOperand(1));
00543 
00544     return CI;
00545   }
00546 };
00547 
00548 //===----------------------------------------------------------------------===//
00549 // String and Memory LibCall Optimizations
00550 //===----------------------------------------------------------------------===//
00551 
00552 //===---------------------------------------===//
00553 // 'strcat' Optimizations
00554 
00555 struct VISIBILITY_HIDDEN StrCatOpt : public LibCallOptimization {
00556   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
00557     // Verify the "strcat" function prototype.
00558     const FunctionType *FT = Callee->getFunctionType();
00559     if (FT->getNumParams() != 2 ||
00560         FT->getReturnType() != PointerType::getUnqual(Type::getInt8Ty(*Context)) ||
00561         FT->getParamType(0) != FT->getReturnType() ||
00562         FT->getParamType(1) != FT->getReturnType())
00563       return 0;
00564     
00565     // Extract some information from the instruction
00566     Value *Dst = CI->getOperand(1);
00567     Value *Src = CI->getOperand(2);
00568     
00569     // See if we can get the length of the input string.
00570     uint64_t Len = GetStringLength(Src);
00571     if (Len == 0) return 0;
00572     --Len;  // Unbias length.
00573     
00574     // Handle the simple, do-nothing case: strcat(x, "") -> x
00575     if (Len == 0)
00576       return Dst;
00577 
00578     // These optimizations require TargetData.
00579     if (!TD) return 0;
00580 
00581     EmitStrLenMemCpy(Src, Dst, Len, B);
00582     return Dst;
00583   }
00584 
00585   void EmitStrLenMemCpy(Value *Src, Value *Dst, uint64_t Len, IRBuilder<> &B) {
00586     // We need to find the end of the destination string.  That's where the
00587     // memory is to be moved to. We just generate a call to strlen.
00588     Value *DstLen = EmitStrLen(Dst, B);
00589     
00590     // Now that we have the destination's length, we must index into the
00591     // destination's pointer to get the actual memcpy destination (end of
00592     // the string .. we're concatenating).
00593     Value *CpyDst = B.CreateGEP(Dst, DstLen, "endptr");
00594     
00595     // We have enough information to now generate the memcpy call to do the
00596     // concatenation for us.  Make a memcpy to copy the nul byte with align = 1.
00597     EmitMemCpy(CpyDst, Src,
00598                ConstantInt::get(TD->getIntPtrType(*Context), Len+1), 1, B);
00599   }
00600 };
00601 
00602 //===---------------------------------------===//
00603 // 'strncat' Optimizations
00604 
00605 struct VISIBILITY_HIDDEN StrNCatOpt : public StrCatOpt {
00606   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
00607     // Verify the "strncat" function prototype.
00608     const FunctionType *FT = Callee->getFunctionType();
00609     if (FT->getNumParams() != 3 ||
00610         FT->getReturnType() != PointerType::getUnqual(Type::getInt8Ty(*Context)) ||
00611         FT->getParamType(0) != FT->getReturnType() ||
00612         FT->getParamType(1) != FT->getReturnType() ||
00613         !isa<IntegerType>(FT->getParamType(2)))
00614       return 0;
00615 
00616     // Extract some information from the instruction
00617     Value *Dst = CI->getOperand(1);
00618     Value *Src = CI->getOperand(2);
00619     uint64_t Len;
00620 
00621     // We don't do anything if length is not constant
00622     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getOperand(3)))
00623       Len = LengthArg->getZExtValue();
00624     else
00625       return 0;
00626 
00627     // See if we can get the length of the input string.
00628     uint64_t SrcLen = GetStringLength(Src);
00629     if (SrcLen == 0) return 0;
00630     --SrcLen;  // Unbias length.
00631 
00632     // Handle the simple, do-nothing cases:
00633     // strncat(x, "", c) -> x
00634     // strncat(x,  c, 0) -> x
00635     if (SrcLen == 0 || Len == 0) return Dst;
00636 
00637     // These optimizations require TargetData.
00638     if (!TD) return 0;
00639 
00640     // We don't optimize this case
00641     if (Len < SrcLen) return 0;
00642 
00643     // strncat(x, s, c) -> strcat(x, s)
00644     // s is constant so the strcat can be optimized further
00645     EmitStrLenMemCpy(Src, Dst, SrcLen, B);
00646     return Dst;
00647   }
00648 };
00649 
00650 //===---------------------------------------===//
00651 // 'strchr' Optimizations
00652 
00653 struct VISIBILITY_HIDDEN StrChrOpt : public LibCallOptimization {
00654   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
00655     // Verify the "strchr" function prototype.
00656     const FunctionType *FT = Callee->getFunctionType();
00657     if (FT->getNumParams() != 2 ||
00658         FT->getReturnType() != PointerType::getUnqual(Type::getInt8Ty(*Context)) ||
00659         FT->getParamType(0) != FT->getReturnType())
00660       return 0;
00661     
00662     Value *SrcStr = CI->getOperand(1);
00663     
00664     // If the second operand is non-constant, see if we can compute the length
00665     // of the input string and turn this into memchr.
00666     ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getOperand(2));
00667     if (CharC == 0) {
00668       // These optimizations require TargetData.
00669       if (!TD) return 0;
00670 
00671       uint64_t Len = GetStringLength(SrcStr);
00672       if (Len == 0 || FT->getParamType(1) != Type::getInt32Ty(*Context)) // memchr needs i32.
00673         return 0;
00674       
00675       return EmitMemChr(SrcStr, CI->getOperand(2), // include nul.
00676                         ConstantInt::get(TD->getIntPtrType(*Context), Len), B);
00677     }
00678 
00679     // Otherwise, the character is a constant, see if the first argument is
00680     // a string literal.  If so, we can constant fold.
00681     std::string Str;
00682     if (!GetConstantStringInfo(SrcStr, Str))
00683       return 0;
00684     
00685     // strchr can find the nul character.
00686     Str += '\0';
00687     char CharValue = CharC->getSExtValue();
00688     
00689     // Compute the offset.
00690     uint64_t i = 0;
00691     while (1) {
00692       if (i == Str.size())    // Didn't find the char.  strchr returns null.
00693         return Constant::getNullValue(CI->getType());
00694       // Did we find our match?
00695       if (Str[i] == CharValue)
00696         break;
00697       ++i;
00698     }
00699     
00700     // strchr(s+n,c)  -> gep(s+n+i,c)
00701     Value *Idx = ConstantInt::get(Type::getInt64Ty(*Context), i);
00702     return B.CreateGEP(SrcStr, Idx, "strchr");
00703   }
00704 };
00705 
00706 //===---------------------------------------===//
00707 // 'strcmp' Optimizations
00708 
00709 struct VISIBILITY_HIDDEN StrCmpOpt : public LibCallOptimization {
00710   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
00711     // Verify the "strcmp" function prototype.
00712     const FunctionType *FT = Callee->getFunctionType();
00713     if (FT->getNumParams() != 2 || FT->getReturnType() != Type::getInt32Ty(*Context) ||
00714         FT->getParamType(0) != FT->getParamType(1) ||
00715         FT->getParamType(0) != PointerType::getUnqual(Type::getInt8Ty(*Context)))
00716       return 0;
00717     
00718     Value *Str1P = CI->getOperand(1), *Str2P = CI->getOperand(2);
00719     if (Str1P == Str2P)      // strcmp(x,x)  -> 0
00720       return ConstantInt::get(CI->getType(), 0);
00721     
00722     std::string Str1, Str2;
00723     bool HasStr1 = GetConstantStringInfo(Str1P, Str1);
00724     bool HasStr2 = GetConstantStringInfo(Str2P, Str2);
00725     
00726     if (HasStr1 && Str1.empty()) // strcmp("", x) -> *x
00727       return B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"), CI->getType());
00728     
00729     if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x
00730       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
00731     
00732     // strcmp(x, y)  -> cnst  (if both x and y are constant strings)
00733     if (HasStr1 && HasStr2)
00734       return ConstantInt::get(CI->getType(), 
00735                                      strcmp(Str1.c_str(),Str2.c_str()));
00736 
00737     // strcmp(P, "x") -> memcmp(P, "x", 2)
00738     uint64_t Len1 = GetStringLength(Str1P);
00739     uint64_t Len2 = GetStringLength(Str2P);
00740     if (Len1 && Len2) {
00741       // These optimizations require TargetData.
00742       if (!TD) return 0;
00743 
00744       return EmitMemCmp(Str1P, Str2P,
00745                         ConstantInt::get(TD->getIntPtrType(*Context),
00746                         std::min(Len1, Len2)), B);
00747     }
00748 
00749     return 0;
00750   }
00751 };
00752 
00753 //===---------------------------------------===//
00754 // 'strncmp' Optimizations
00755 
00756 struct VISIBILITY_HIDDEN StrNCmpOpt : public LibCallOptimization {
00757   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
00758     // Verify the "strncmp" function prototype.
00759     const FunctionType *FT = Callee->getFunctionType();
00760     if (FT->getNumParams() != 3 || FT->getReturnType() != Type::getInt32Ty(*Context) ||
00761         FT->getParamType(0) != FT->getParamType(1) ||
00762         FT->getParamType(0) != PointerType::getUnqual(Type::getInt8Ty(*Context)) ||
00763         !isa<IntegerType>(FT->getParamType(2)))
00764       return 0;
00765     
00766     Value *Str1P = CI->getOperand(1), *Str2P = CI->getOperand(2);
00767     if (Str1P == Str2P)      // strncmp(x,x,n)  -> 0
00768       return ConstantInt::get(CI->getType(), 0);
00769     
00770     // Get the length argument if it is constant.
00771     uint64_t Length;
00772     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getOperand(3)))
00773       Length = LengthArg->getZExtValue();
00774     else
00775       return 0;
00776     
00777     if (Length == 0) // strncmp(x,y,0)   -> 0
00778       return ConstantInt::get(CI->getType(), 0);
00779     
00780     std::string Str1, Str2;
00781     bool HasStr1 = GetConstantStringInfo(Str1P, Str1);
00782     bool HasStr2 = GetConstantStringInfo(Str2P, Str2);
00783     
00784     if (HasStr1 && Str1.empty())  // strncmp("", x, n) -> *x
00785       return B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"), CI->getType());
00786     
00787     if (HasStr2 && Str2.empty())  // strncmp(x, "", n) -> *x
00788       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
00789     
00790     // strncmp(x, y)  -> cnst  (if both x and y are constant strings)
00791     if (HasStr1 && HasStr2)
00792       return ConstantInt::get(CI->getType(),
00793                               strncmp(Str1.c_str(), Str2.c_str(), Length));
00794     return 0;
00795   }
00796 };
00797 
00798 
00799 //===---------------------------------------===//
00800 // 'strcpy' Optimizations
00801 
00802 struct VISIBILITY_HIDDEN StrCpyOpt : public LibCallOptimization {
00803   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
00804     // Verify the "strcpy" function prototype.
00805     const FunctionType *FT = Callee->getFunctionType();
00806     if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) ||
00807         FT->getParamType(0) != FT->getParamType(1) ||
00808         FT->getParamType(0) != PointerType::getUnqual(Type::getInt8Ty(*Context)))
00809       return 0;
00810     
00811     Value *Dst = CI->getOperand(1), *Src = CI->getOperand(2);
00812     if (Dst == Src)      // strcpy(x,x)  -> x
00813       return Src;
00814     
00815     // These optimizations require TargetData.
00816     if (!TD) return 0;
00817 
00818     // See if we can get the length of the input string.
00819     uint64_t Len = GetStringLength(Src);
00820     if (Len == 0) return 0;
00821     
00822     // We have enough information to now generate the memcpy call to do the
00823     // concatenation for us.  Make a memcpy to copy the nul byte with align = 1.
00824     EmitMemCpy(Dst, Src,
00825                ConstantInt::get(TD->getIntPtrType(*Context), Len), 1, B);
00826     return Dst;
00827   }
00828 };
00829 
00830 //===---------------------------------------===//
00831 // 'strncpy' Optimizations
00832 
00833 struct VISIBILITY_HIDDEN StrNCpyOpt : public LibCallOptimization {
00834   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
00835     const FunctionType *FT = Callee->getFunctionType();
00836     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
00837         FT->getParamType(0) != FT->getParamType(1) ||
00838         FT->getParamType(0) != PointerType::getUnqual(Type::getInt8Ty(*Context)) ||
00839         !isa<IntegerType>(FT->getParamType(2)))
00840       return 0;
00841 
00842     Value *Dst = CI->getOperand(1);
00843     Value *Src = CI->getOperand(2);
00844     Value *LenOp = CI->getOperand(3);
00845 
00846     // See if we can get the length of the input string.
00847     uint64_t SrcLen = GetStringLength(Src);
00848     if (SrcLen == 0) return 0;
00849     --SrcLen;
00850 
00851     if (SrcLen == 0) {
00852       // strncpy(x, "", y) -> memset(x, '\0', y, 1)
00853       EmitMemSet(Dst, ConstantInt::get(Type::getInt8Ty(*Context), '\0'), LenOp, B);
00854       return Dst;
00855     }
00856 
00857     uint64_t Len;
00858     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(LenOp))
00859       Len = LengthArg->getZExtValue();
00860     else
00861       return 0;
00862 
00863     if (Len == 0) return Dst; // strncpy(x, y, 0) -> x
00864 
00865     // These optimizations require TargetData.
00866     if (!TD) return 0;
00867 
00868     // Let strncpy handle the zero padding
00869     if (Len > SrcLen+1) return 0;
00870 
00871     // strncpy(x, s, c) -> memcpy(x, s, c, 1) [s and c are constant]
00872     EmitMemCpy(Dst, Src,
00873                ConstantInt::get(TD->getIntPtrType(*Context), Len), 1, B);
00874 
00875     return Dst;
00876   }
00877 };
00878 
00879 //===---------------------------------------===//
00880 // 'strlen' Optimizations
00881 
00882 struct VISIBILITY_HIDDEN StrLenOpt : public LibCallOptimization {
00883   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
00884     const FunctionType *FT = Callee->getFunctionType();
00885     if (FT->getNumParams() != 1 ||
00886         FT->getParamType(0) != PointerType::getUnqual(Type::getInt8Ty(*Context)) ||
00887         !isa<IntegerType>(FT->getReturnType()))
00888       return 0;
00889     
00890     Value *Src = CI->getOperand(1);
00891 
00892     // Constant folding: strlen("xyz") -> 3
00893     if (uint64_t Len = GetStringLength(Src))
00894       return ConstantInt::get(CI->getType(), Len-1);
00895 
00896     // Handle strlen(p) != 0.
00897     if (!IsOnlyUsedInZeroEqualityComparison(CI)) return 0;
00898 
00899     // strlen(x) != 0 --> *x != 0
00900     // strlen(x) == 0 --> *x == 0
00901     return B.CreateZExt(B.CreateLoad(Src, "strlenfirst"), CI->getType());
00902   }
00903 };
00904 
00905 //===---------------------------------------===//
00906 // 'strto*' Optimizations
00907 
00908 struct VISIBILITY_HIDDEN StrToOpt : public LibCallOptimization {
00909   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
00910     const FunctionType *FT = Callee->getFunctionType();
00911     if ((FT->getNumParams() != 2 && FT->getNumParams() != 3) ||
00912         !isa<PointerType>(FT->getParamType(0)) ||
00913         !isa<PointerType>(FT->getParamType(1)))
00914       return 0;
00915 
00916     Value *EndPtr = CI->getOperand(2);
00917     if (isa<ConstantPointerNull>(EndPtr)) {
00918       CI->setOnlyReadsMemory();
00919       CI->addAttribute(1, Attribute::NoCapture);
00920     }
00921 
00922     return 0;
00923   }
00924 };
00925 
00926 
00927 //===---------------------------------------===//
00928 // 'memcmp' Optimizations
00929 
00930 struct VISIBILITY_HIDDEN MemCmpOpt : public LibCallOptimization {
00931   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
00932     const FunctionType *FT = Callee->getFunctionType();
00933     if (FT->getNumParams() != 3 || !isa<PointerType>(FT->getParamType(0)) ||
00934         !isa<PointerType>(FT->getParamType(1)) ||
00935         FT->getReturnType() != Type::getInt32Ty(*Context))
00936       return 0;
00937 
00938     Value *LHS = CI->getOperand(1), *RHS = CI->getOperand(2);
00939 
00940     if (LHS == RHS)  // memcmp(s,s,x) -> 0
00941       return Constant::getNullValue(CI->getType());
00942 
00943     // Make sure we have a constant length.
00944     ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getOperand(3));
00945     if (!LenC) return 0;
00946     uint64_t Len = LenC->getZExtValue();
00947 
00948     if (Len == 0) // memcmp(s1,s2,0) -> 0
00949       return Constant::getNullValue(CI->getType());
00950 
00951     if (Len == 1) { // memcmp(S1,S2,1) -> *LHS - *RHS
00952       Value *LHSV = B.CreateLoad(CastToCStr(LHS, B), "lhsv");
00953       Value *RHSV = B.CreateLoad(CastToCStr(RHS, B), "rhsv");
00954       return B.CreateSExt(B.CreateSub(LHSV, RHSV, "chardiff"), CI->getType());
00955     }
00956 
00957     // memcmp(S1,S2,2) != 0 -> (*(short*)LHS ^ *(short*)RHS)  != 0
00958     // memcmp(S1,S2,4) != 0 -> (*(int*)LHS ^ *(int*)RHS)  != 0
00959     if ((Len == 2 || Len == 4) && IsOnlyUsedInZeroEqualityComparison(CI)) {
00960       const Type *PTy = PointerType::getUnqual(Len == 2 ?
00961                        Type::getInt16Ty(*Context) : Type::getInt32Ty(*Context));
00962       LHS = B.CreateBitCast(LHS, PTy, "tmp");
00963       RHS = B.CreateBitCast(RHS, PTy, "tmp");
00964       LoadInst *LHSV = B.CreateLoad(LHS, "lhsv");
00965       LoadInst *RHSV = B.CreateLoad(RHS, "rhsv");
00966       LHSV->setAlignment(1); RHSV->setAlignment(1);  // Unaligned loads.
00967       return B.CreateZExt(B.CreateXor(LHSV, RHSV, "shortdiff"), CI->getType());
00968     }
00969 
00970     return 0;
00971   }
00972 };
00973 
00974 //===---------------------------------------===//
00975 // 'memcpy' Optimizations
00976 
00977 struct VISIBILITY_HIDDEN MemCpyOpt : public LibCallOptimization {
00978   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
00979     // These optimizations require TargetData.
00980     if (!TD) return 0;
00981 
00982     const FunctionType *FT = Callee->getFunctionType();
00983     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
00984         !isa<PointerType>(FT->getParamType(0)) ||
00985         !isa<PointerType>(FT->getParamType(1)) ||
00986         FT->getParamType(2) != TD->getIntPtrType(*Context))
00987       return 0;
00988 
00989     // memcpy(x, y, n) -> llvm.memcpy(x, y, n, 1)
00990     EmitMemCpy(CI->getOperand(1), CI->getOperand(2), CI->getOperand(3), 1, B);
00991     return CI->getOperand(1);
00992   }
00993 };
00994 
00995 //===---------------------------------------===//
00996 // 'memmove' Optimizations
00997 
00998 struct VISIBILITY_HIDDEN MemMoveOpt : public LibCallOptimization {
00999   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
01000     // These optimizations require TargetData.
01001     if (!TD) return 0;
01002 
01003     const FunctionType *FT = Callee->getFunctionType();
01004     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
01005         !isa<PointerType>(FT->getParamType(0)) ||
01006         !isa<PointerType>(FT->getParamType(1)) ||
01007         FT->getParamType(2) != TD->getIntPtrType(*Context))
01008       return 0;
01009 
01010     // memmove(x, y, n) -> llvm.memmove(x, y, n, 1)
01011     Module *M = Caller->getParent();
01012     Intrinsic::ID IID = Intrinsic::memmove;
01013     const Type *Tys[1];
01014     Tys[0] = TD->getIntPtrType(*Context);
01015     Value *MemMove = Intrinsic::getDeclaration(M, IID, Tys, 1);
01016     Value *Dst = CastToCStr(CI->getOperand(1), B);
01017     Value *Src = CastToCStr(CI->getOperand(2), B);
01018     Value *Size = CI->getOperand(3);
01019     Value *Align = ConstantInt::get(Type::getInt32Ty(*Context), 1);
01020     B.CreateCall4(MemMove, Dst, Src, Size, Align);
01021     return CI->getOperand(1);
01022   }
01023 };
01024 
01025 //===---------------------------------------===//
01026 // 'memset' Optimizations
01027 
01028 struct VISIBILITY_HIDDEN MemSetOpt : public LibCallOptimization {
01029   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
01030     // These optimizations require TargetData.
01031     if (!TD) return 0;
01032 
01033     const FunctionType *FT = Callee->getFunctionType();
01034     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
01035         !isa<PointerType>(FT->getParamType(0)) ||
01036         !isa<IntegerType>(FT->getParamType(1)) ||
01037         FT->getParamType(2) != TD->getIntPtrType(*Context))
01038       return 0;
01039 
01040     // memset(p, v, n) -> llvm.memset(p, v, n, 1)
01041     Value *Val = B.CreateIntCast(CI->getOperand(2), Type::getInt8Ty(*Context), false);
01042     EmitMemSet(CI->getOperand(1), Val,  CI->getOperand(3), B);
01043     return CI->getOperand(1);
01044   }
01045 };
01046 
01047 //===----------------------------------------------------------------------===//
01048 // Math Library Optimizations
01049 //===----------------------------------------------------------------------===//
01050 
01051 //===---------------------------------------===//
01052 // 'pow*' Optimizations
01053 
01054 struct VISIBILITY_HIDDEN PowOpt : public LibCallOptimization {
01055   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
01056     const FunctionType *FT = Callee->getFunctionType();
01057     // Just make sure this has 2 arguments of the same FP type, which match the
01058     // result type.
01059     if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) ||
01060         FT->getParamType(0) != FT->getParamType(1) ||
01061         !FT->getParamType(0)->isFloatingPoint())
01062       return 0;
01063     
01064     Value *Op1 = CI->getOperand(1), *Op2 = CI->getOperand(2);
01065     if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) {
01066       if (Op1C->isExactlyValue(1.0))  // pow(1.0, x) -> 1.0
01067         return Op1C;
01068       if (Op1C->isExactlyValue(2.0))  // pow(2.0, x) -> exp2(x)
01069         return EmitUnaryFloatFnCall(Op2, "exp2", B);
01070     }
01071     
01072     ConstantFP *Op2C = dyn_cast<ConstantFP>(Op2);
01073     if (Op2C == 0) return 0;
01074     
01075     if (Op2C->getValueAPF().isZero())  // pow(x, 0.0) -> 1.0
01076       return ConstantFP::get(CI->getType(), 1.0);
01077     
01078     if (Op2C->isExactlyValue(0.5)) {
01079       // FIXME: This is not safe for -0.0 and -inf.  This can only be done when
01080       // 'unsafe' math optimizations are allowed.
01081       // x    pow(x, 0.5)  sqrt(x)
01082       // ---------------------------------------------
01083       // -0.0    +0.0       -0.0
01084       // -inf    +inf       NaN
01085 #if 0
01086       // pow(x, 0.5) -> sqrt(x)
01087       return B.CreateCall(get_sqrt(), Op1, "sqrt");
01088 #endif
01089     }
01090     
01091     if (Op2C->isExactlyValue(1.0))  // pow(x, 1.0) -> x
01092       return Op1;
01093     if (Op2C->isExactlyValue(2.0))  // pow(x, 2.0) -> x*x
01094       return B.CreateFMul(Op1, Op1, "pow2");
01095     if (Op2C->isExactlyValue(-1.0)) // pow(x, -1.0) -> 1.0/x
01096       return B.CreateFDiv(ConstantFP::get(CI->getType(), 1.0),
01097                           Op1, "powrecip");
01098     return 0;
01099   }
01100 };
01101 
01102 //===---------------------------------------===//
01103 // 'exp2' Optimizations
01104 
01105 struct VISIBILITY_HIDDEN Exp2Opt : public LibCallOptimization {
01106   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
01107     const FunctionType *FT = Callee->getFunctionType();
01108     // Just make sure this has 1 argument of FP type, which matches the
01109     // result type.
01110     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
01111         !FT->getParamType(0)->isFloatingPoint())
01112       return 0;
01113     
01114     Value *Op = CI->getOperand(1);
01115     // Turn exp2(sitofp(x)) -> ldexp(1.0, sext(x))  if sizeof(x) <= 32
01116     // Turn exp2(uitofp(x)) -> ldexp(1.0, zext(x))  if sizeof(x) < 32
01117     Value *LdExpArg = 0;
01118     if (SIToFPInst *OpC = dyn_cast<SIToFPInst>(Op)) {
01119       if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() <= 32)
01120         LdExpArg = B.CreateSExt(OpC->getOperand(0), Type::getInt32Ty(*Context), "tmp");
01121     } else if (UIToFPInst *OpC = dyn_cast<UIToFPInst>(Op)) {
01122       if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() < 32)
01123         LdExpArg = B.CreateZExt(OpC->getOperand(0), Type::getInt32Ty(*Context), "tmp");
01124     }
01125 
01126     if (LdExpArg) {
01127       const char *Name;
01128       if (Op->getType() == Type::getFloatTy(*Context))
01129         Name = "ldexpf";
01130       else if (Op->getType() == Type::getDoubleTy(*Context))
01131         Name = "ldexp";
01132       else
01133         Name = "ldexpl";
01134 
01135       Constant *One = ConstantFP::get(*Context, APFloat(1.0f));
01136       if (Op->getType() != Type::getFloatTy(*Context))
01137         One = ConstantExpr::getFPExtend(One, Op->getType());
01138 
01139       Module *M = Caller->getParent();
01140       Value *Callee = M->getOrInsertFunction(Name, Op->getType(),
01141                                              Op->getType(), Type::getInt32Ty(*Context),NULL);
01142       CallInst *CI = B.CreateCall2(Callee, One, LdExpArg);
01143       if (const Function *F = dyn_cast<Function>(Callee->stripPointerCasts()))
01144         CI->setCallingConv(F->getCallingConv());
01145 
01146       return CI;
01147     }
01148     return 0;
01149   }
01150 };
01151 
01152 //===---------------------------------------===//
01153 // Double -> Float Shrinking Optimizations for Unary Functions like 'floor'
01154 
01155 struct VISIBILITY_HIDDEN UnaryDoubleFPOpt : public LibCallOptimization {
01156   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
01157     const FunctionType *FT = Callee->getFunctionType();
01158     if (FT->getNumParams() != 1 || FT->getReturnType() != Type::getDoubleTy(*Context) ||
01159         FT->getParamType(0) != Type::getDoubleTy(*Context))
01160       return 0;
01161 
01162     // If this is something like 'floor((double)floatval)', convert to floorf.
01163     FPExtInst *Cast = dyn_cast<FPExtInst>(CI->getOperand(1));
01164     if (Cast == 0 || Cast->getOperand(0)->getType() != Type::getFloatTy(*Context))
01165       return 0;
01166 
01167     // floor((double)floatval) -> (double)floorf(floatval)
01168     Value *V = Cast->getOperand(0);
01169     V = EmitUnaryFloatFnCall(V, Callee->getName().data(), B);
01170     return B.CreateFPExt(V, Type::getDoubleTy(*Context));
01171   }
01172 };
01173 
01174 //===----------------------------------------------------------------------===//
01175 // Integer Optimizations
01176 //===----------------------------------------------------------------------===//
01177 
01178 //===---------------------------------------===//
01179 // 'ffs*' Optimizations
01180 
01181 struct VISIBILITY_HIDDEN FFSOpt : public LibCallOptimization {
01182   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
01183     const FunctionType *FT = Callee->getFunctionType();
01184     // Just make sure this has 2 arguments of the same FP type, which match the
01185     // result type.
01186     if (FT->getNumParams() != 1 || FT->getReturnType() != Type::getInt32Ty(*Context) ||
01187         !isa<IntegerType>(FT->getParamType(0)))
01188       return 0;
01189     
01190     Value *Op = CI->getOperand(1);
01191     
01192     // Constant fold.
01193     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op)) {
01194       if (CI->getValue() == 0)  // ffs(0) -> 0.
01195         return Constant::getNullValue(CI->getType());
01196       return ConstantInt::get(Type::getInt32Ty(*Context), // ffs(c) -> cttz(c)+1
01197                               CI->getValue().countTrailingZeros()+1);
01198     }
01199     
01200     // ffs(x) -> x != 0 ? (i32)llvm.cttz(x)+1 : 0
01201     const Type *ArgType = Op->getType();
01202     Value *F = Intrinsic::getDeclaration(Callee->getParent(),
01203                                          Intrinsic::cttz, &ArgType, 1);
01204     Value *V = B.CreateCall(F, Op, "cttz");
01205     V = B.CreateAdd(V, ConstantInt::get(V->getType(), 1), "tmp");
01206     V = B.CreateIntCast(V, Type::getInt32Ty(*Context), false, "tmp");
01207     
01208     Value *Cond = B.CreateICmpNE(Op, Constant::getNullValue(ArgType), "tmp");
01209     return B.CreateSelect(Cond, V, ConstantInt::get(Type::getInt32Ty(*Context), 0));
01210   }
01211 };
01212 
01213 //===---------------------------------------===//
01214 // 'isdigit' Optimizations
01215 
01216 struct VISIBILITY_HIDDEN IsDigitOpt : public LibCallOptimization {
01217   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
01218     const FunctionType *FT = Callee->getFunctionType();
01219     // We require integer(i32)
01220     if (FT->getNumParams() != 1 || !isa<IntegerType>(FT->getReturnType()) ||
01221         FT->getParamType(0) != Type::getInt32Ty(*Context))
01222       return 0;
01223     
01224     // isdigit(c) -> (c-'0') <u 10
01225     Value *Op = CI->getOperand(1);
01226     Op = B.CreateSub(Op, ConstantInt::get(Type::getInt32Ty(*Context), '0'), 
01227                      "isdigittmp");
01228     Op = B.CreateICmpULT(Op, ConstantInt::get(Type::getInt32Ty(*Context), 10), 
01229                          "isdigit");
01230     return B.CreateZExt(Op, CI->getType());
01231   }
01232 };
01233 
01234 //===---------------------------------------===//
01235 // 'isascii' Optimizations
01236 
01237 struct VISIBILITY_HIDDEN IsAsciiOpt : public LibCallOptimization {
01238   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
01239     const FunctionType *FT = Callee->getFunctionType();
01240     // We require integer(i32)
01241     if (FT->getNumParams() != 1 || !isa<IntegerType>(FT->getReturnType()) ||
01242         FT->getParamType(0) != Type::getInt32Ty(*Context))
01243       return 0;
01244     
01245     // isascii(c) -> c <u 128
01246     Value *Op = CI->getOperand(1);
01247     Op = B.CreateICmpULT(Op, ConstantInt::get(Type::getInt32Ty(*Context), 128),
01248                          "isascii");
01249     return B.CreateZExt(Op, CI->getType());
01250   }
01251 };
01252   
01253 //===---------------------------------------===//
01254 // 'abs', 'labs', 'llabs' Optimizations
01255 
01256 struct VISIBILITY_HIDDEN AbsOpt : public LibCallOptimization {
01257   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
01258     const FunctionType *FT = Callee->getFunctionType();
01259     // We require integer(integer) where the types agree.
01260     if (FT->getNumParams() != 1 || !isa<IntegerType>(FT->getReturnType()) ||
01261         FT->getParamType(0) != FT->getReturnType())
01262       return 0;
01263     
01264     // abs(x) -> x >s -1 ? x : -x
01265     Value *Op = CI->getOperand(1);
01266     Value *Pos = B.CreateICmpSGT(Op, 
01267                              Constant::getAllOnesValue(Op->getType()),
01268                                  "ispos");
01269     Value *Neg = B.CreateNeg(Op, "neg");
01270     return B.CreateSelect(Pos, Op, Neg);
01271   }
01272 };
01273   
01274 
01275 //===---------------------------------------===//
01276 // 'toascii' Optimizations
01277 
01278 struct VISIBILITY_HIDDEN ToAsciiOpt : public LibCallOptimization {
01279   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
01280     const FunctionType *FT = Callee->getFunctionType();
01281     // We require i32(i32)
01282     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
01283         FT->getParamType(0) != Type::getInt32Ty(*Context))
01284       return 0;
01285     
01286     // isascii(c) -> c & 0x7f
01287     return B.CreateAnd(CI->getOperand(1),
01288                        ConstantInt::get(CI->getType(),0x7F));
01289   }
01290 };
01291 
01292 //===----------------------------------------------------------------------===//
01293 // Formatting and IO Optimizations
01294 //===----------------------------------------------------------------------===//
01295 
01296 //===---------------------------------------===//
01297 // 'printf' Optimizations
01298 
01299 struct VISIBILITY_HIDDEN PrintFOpt : public LibCallOptimization {
01300   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
01301     // Require one fixed pointer argument and an integer/void result.
01302     const FunctionType *FT = Callee->getFunctionType();
01303     if (FT->getNumParams() < 1 || !isa<PointerType>(FT->getParamType(0)) ||
01304         !(isa<IntegerType>(FT->getReturnType()) ||
01305           FT->getReturnType() == Type::getVoidTy(*Context)))
01306       return 0;
01307     
01308     // Check for a fixed format string.
01309     std::string FormatStr;
01310     if (!GetConstantStringInfo(CI->getOperand(1), FormatStr))
01311       return 0;
01312 
01313     // Empty format string -> noop.
01314     if (FormatStr.empty())  // Tolerate printf's declared void.
01315       return CI->use_empty() ? (Value*)CI : 
01316                                ConstantInt::get(CI->getType(), 0);
01317     
01318     // printf("x") -> putchar('x'), even for '%'.
01319     if (FormatStr.size() == 1) {
01320       EmitPutChar(ConstantInt::get(Type::getInt32Ty(*Context), FormatStr[0]), B);
01321       return CI->use_empty() ? (Value*)CI : 
01322                                ConstantInt::get(CI->getType(), 1);
01323     }
01324     
01325     // printf("foo\n") --> puts("foo")
01326     if (FormatStr[FormatStr.size()-1] == '\n' &&
01327         FormatStr.find('%') == std::string::npos) {  // no format characters.
01328       // Create a string literal with no \n on it.  We expect the constant merge
01329       // pass to be run after this pass, to merge duplicate strings.
01330       FormatStr.erase(FormatStr.end()-1);
01331       Constant *C = ConstantArray::get(*Context, FormatStr, true);
01332       C = new GlobalVariable(*Callee->getParent(), C->getType(), true,
01333                              GlobalVariable::InternalLinkage, C, "str");
01334       EmitPutS(C, B);
01335       return CI->use_empty() ? (Value*)CI : 
01336                     ConstantInt::get(CI->getType(), FormatStr.size()+1);
01337     }
01338     
01339     // Optimize specific format strings.
01340     // printf("%c", chr) --> putchar(*(i8*)dst)
01341     if (FormatStr == "%c" && CI->getNumOperands() > 2 &&
01342         isa<IntegerType>(CI->getOperand(2)->getType())) {
01343       EmitPutChar(CI->getOperand(2), B);
01344       return CI->use_empty() ? (Value*)CI : 
01345                                ConstantInt::get(CI->getType(), 1);
01346     }
01347     
01348     // printf("%s\n", str) --> puts(str)
01349     if (FormatStr == "%s\n" && CI->getNumOperands() > 2 &&
01350         isa<PointerType>(CI->getOperand(2)->getType()) &&
01351         CI->use_empty()) {
01352       EmitPutS(CI->getOperand(2), B);
01353       return CI;
01354     }
01355     return 0;
01356   }
01357 };
01358 
01359 //===---------------------------------------===//
01360 // 'sprintf' Optimizations
01361 
01362 struct VISIBILITY_HIDDEN SPrintFOpt : public LibCallOptimization {
01363   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
01364     // Require two fixed pointer arguments and an integer result.
01365     const FunctionType *FT = Callee->getFunctionType();
01366     if (FT->getNumParams() != 2 || !isa<PointerType>(FT->getParamType(0)) ||
01367         !isa<PointerType>(FT->getParamType(1)) ||
01368         !isa<IntegerType>(FT->getReturnType()))
01369       return 0;
01370 
01371     // Check for a fixed format string.
01372     std::string FormatStr;
01373     if (!GetConstantStringInfo(CI->getOperand(2), FormatStr))
01374       return 0;
01375     
01376     // If we just have a format string (nothing else crazy) transform it.
01377     if (CI->getNumOperands() == 3) {
01378       // Make sure there's no % in the constant array.  We could try to handle
01379       // %% -> % in the future if we cared.
01380       for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
01381         if (FormatStr[i] == '%')
01382           return 0; // we found a format specifier, bail out.
01383 
01384       // These optimizations require TargetData.
01385       if (!TD) return 0;
01386 
01387       // sprintf(str, fmt) -> llvm.memcpy(str, fmt, strlen(fmt)+1, 1)
01388       EmitMemCpy(CI->getOperand(1), CI->getOperand(2), // Copy the nul byte.
01389           ConstantInt::get(TD->getIntPtrType(*Context), FormatStr.size()+1),1,B);
01390       return ConstantInt::get(CI->getType(), FormatStr.size());
01391     }
01392     
01393     // The remaining optimizations require the format string to be "%s" or "%c"
01394     // and have an extra operand.
01395     if (FormatStr.size() != 2 || FormatStr[0] != '%' || CI->getNumOperands() <4)
01396       return 0;
01397     
01398     // Decode the second character of the format string.
01399     if (FormatStr[1] == 'c') {
01400       // sprintf(dst, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0
01401       if (!isa<IntegerType>(CI->getOperand(3)->getType())) return 0;
01402       Value *V = B.CreateTrunc(CI->getOperand(3), Type::getInt8Ty(*Context), "char");
01403       Value *Ptr = CastToCStr(CI->getOperand(1), B);
01404       B.CreateStore(V, Ptr);
01405       Ptr = B.CreateGEP(Ptr, ConstantInt::get(Type::getInt32Ty(*Context), 1), "nul");
01406       B.CreateStore(Constant::getNullValue(Type::getInt8Ty(*Context)), Ptr);
01407       
01408       return ConstantInt::get(CI->getType(), 1);
01409     }
01410     
01411     if (FormatStr[1] == 's') {
01412       // These optimizations require TargetData.
01413       if (!TD) return 0;
01414 
01415       // sprintf(dest, "%s", str) -> llvm.memcpy(dest, str, strlen(str)+1, 1)
01416       if (!isa<PointerType>(CI->getOperand(3)->getType())) return 0;
01417 
01418       Value *Len = EmitStrLen(CI->getOperand(3), B);
01419       Value *IncLen = B.CreateAdd(Len,
01420                                   ConstantInt::get(Len->getType(), 1),
01421                                   "leninc");
01422       EmitMemCpy(CI->getOperand(1), CI->getOperand(3), IncLen, 1, B);
01423       
01424       // The sprintf result is the unincremented number of bytes in the string.
01425       return B.CreateIntCast(Len, CI->getType(), false);
01426     }
01427     return 0;
01428   }
01429 };
01430 
01431 //===---------------------------------------===//
01432 // 'fwrite' Optimizations
01433 
01434 struct VISIBILITY_HIDDEN FWriteOpt : public LibCallOptimization {
01435   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
01436     // Require a pointer, an integer, an integer, a pointer, returning integer.
01437     const FunctionType *FT = Callee->getFunctionType();
01438     if (FT->getNumParams() != 4 || !isa<PointerType>(FT->getParamType(0)) ||
01439         !isa<IntegerType>(FT->getParamType(1)) ||
01440         !isa<IntegerType>(FT->getParamType(2)) ||
01441         !isa<PointerType>(FT->getParamType(3)) ||
01442         !isa<IntegerType>(FT->getReturnType()))
01443       return 0;
01444     
01445     // Get the element size and count.
01446     ConstantInt *SizeC = dyn_cast<ConstantInt>(CI->getOperand(2));
01447     ConstantInt *CountC = dyn_cast<ConstantInt>(CI->getOperand(3));
01448     if (!SizeC || !CountC) return 0;
01449     uint64_t Bytes = SizeC->getZExtValue()*CountC->getZExtValue();
01450     
01451     // If this is writing zero records, remove the call (it's a noop).
01452     if (Bytes == 0)
01453       return ConstantInt::get(CI->getType(), 0);
01454     
01455     // If this is writing one byte, turn it into fputc.
01456     if (Bytes == 1) {  // fwrite(S,1,1,F) -> fputc(S[0],F)
01457       Value *Char = B.CreateLoad(CastToCStr(CI->getOperand(1), B), "char");
01458       EmitFPutC(Char, CI->getOperand(4), B);
01459       return ConstantInt::get(CI->getType(), 1);
01460     }
01461 
01462     return 0;
01463   }
01464 };
01465 
01466 //===---------------------------------------===//
01467 // 'fputs' Optimizations
01468 
01469 struct VISIBILITY_HIDDEN FPutsOpt : public LibCallOptimization {
01470   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
01471     // These optimizations require TargetData.
01472     if (!TD) return 0;
01473 
01474     // Require two pointers.  Also, we can't optimize if return value is used.
01475     const FunctionType *FT = Callee->getFunctionType();
01476     if (FT->getNumParams() != 2 || !isa<PointerType>(FT->getParamType(0)) ||
01477         !isa<PointerType>(FT->getParamType(1)) ||
01478         !CI->use_empty())
01479       return 0;
01480     
01481     // fputs(s,F) --> fwrite(s,1,strlen(s),F)
01482     uint64_t Len = GetStringLength(CI->getOperand(1));
01483     if (!Len) return 0;
01484     EmitFWrite(CI->getOperand(1),
01485                ConstantInt::get(TD->getIntPtrType(*Context), Len-1),
01486                CI->getOperand(2), B);
01487     return CI;  // Known to have no uses (see above).
01488   }
01489 };
01490 
01491 //===---------------------------------------===//
01492 // 'fprintf' Optimizations
01493 
01494 struct VISIBILITY_HIDDEN FPrintFOpt : public LibCallOptimization {
01495   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
01496     // Require two fixed paramters as pointers and integer result.
01497     const FunctionType *FT = Callee->getFunctionType();
01498     if (FT->getNumParams() != 2 || !isa<PointerType>(FT->getParamType(0)) ||
01499         !isa<PointerType>(FT->getParamType(1)) ||
01500         !isa<IntegerType>(FT->getReturnType()))
01501       return 0;
01502     
01503     // All the optimizations depend on the format string.
01504     std::string FormatStr;
01505     if (!GetConstantStringInfo(CI->getOperand(2), FormatStr))
01506       return 0;
01507 
01508     // fprintf(F, "foo") --> fwrite("foo", 3, 1, F)
01509     if (CI->getNumOperands() == 3) {
01510       for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
01511         if (FormatStr[i] == '%')  // Could handle %% -> % if we cared.
01512           return 0; // We found a format specifier.
01513 
01514       // These optimizations require TargetData.
01515       if (!TD) return 0;
01516 
01517       EmitFWrite(CI->getOperand(2), ConstantInt::get(TD->getIntPtrType(*Context),
01518                                                      FormatStr.size()),
01519                  CI->getOperand(1), B);
01520       return ConstantInt::get(CI->getType(), FormatStr.size());
01521     }
01522     
01523     // The remaining optimizations require the format string to be "%s" or "%c"
01524     // and have an extra operand.
01525     if (FormatStr.size() != 2 || FormatStr[0] != '%' || CI->getNumOperands() <4)
01526       return 0;
01527     
01528     // Decode the second character of the format string.
01529     if (FormatStr[1] == 'c') {
01530       // fprintf(F, "%c", chr) --> *(i8*)dst = chr
01531       if (!isa<IntegerType>(CI->getOperand(3)->getType())) return 0;
01532       EmitFPutC(CI->getOperand(3), CI->getOperand(1), B);
01533       return ConstantInt::get(CI->getType(), 1);
01534     }
01535     
01536     if (FormatStr[1] == 's') {
01537       // fprintf(F, "%s", str) -> fputs(str, F)
01538       if (!isa<PointerType>(CI->getOperand(3)->getType()) || !CI->use_empty())
01539         return 0;
01540       EmitFPutS(CI->getOperand(3), CI->getOperand(1), B);
01541       return CI;
01542     }
01543     return 0;
01544   }
01545 };
01546 
01547 } // end anonymous namespace.
01548 
01549 //===----------------------------------------------------------------------===//
01550 // SimplifyLibCalls Pass Implementation
01551 //===----------------------------------------------------------------------===//
01552 
01553 namespace {
01554   /// This pass optimizes well known library functions from libc and libm.
01555   ///
01556   class VISIBILITY_HIDDEN SimplifyLibCalls : public FunctionPass {
01557     StringMap<LibCallOptimization*> Optimizations;
01558     // Miscellaneous LibCall Optimizations
01559     ExitOpt Exit; 
01560     // String and Memory LibCall Optimizations
01561     StrCatOpt StrCat; StrNCatOpt StrNCat; StrChrOpt StrChr; StrCmpOpt StrCmp;
01562     StrNCmpOpt StrNCmp; StrCpyOpt StrCpy; StrNCpyOpt StrNCpy; StrLenOpt StrLen;
01563     StrToOpt StrTo; MemCmpOpt MemCmp; MemCpyOpt MemCpy; MemMoveOpt MemMove;
01564     MemSetOpt MemSet;
01565     // Math Library Optimizations
01566     PowOpt Pow; Exp2Opt Exp2; UnaryDoubleFPOpt UnaryDoubleFP;
01567     // Integer Optimizations
01568     FFSOpt FFS; AbsOpt Abs; IsDigitOpt IsDigit; IsAsciiOpt IsAscii;
01569     ToAsciiOpt ToAscii;
01570     // Formatting and IO Optimizations
01571     SPrintFOpt SPrintF; PrintFOpt PrintF;
01572     FWriteOpt FWrite; FPutsOpt FPuts; FPrintFOpt FPrintF;
01573 
01574     bool Modified;  // This is only used by doInitialization.
01575   public:
01576     static char ID; // Pass identification
01577     SimplifyLibCalls() : FunctionPass(&ID) {}
01578 
01579     void InitOptimizations();
01580     bool runOnFunction(Function &F);
01581 
01582     void setDoesNotAccessMemory(Function &F);
01583     void setOnlyReadsMemory(Function &F);
01584     void setDoesNotThrow(Function &F);
01585     void setDoesNotCapture(Function &F, unsigned n);
01586     void setDoesNotAlias(Function &F, unsigned n);
01587     bool doInitialization(Module &M);
01588 
01589     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
01590     }
01591   };
01592   char SimplifyLibCalls::ID = 0;
01593 } // end anonymous namespace.
01594 
01595 static RegisterPass<SimplifyLibCalls>
01596 X("simplify-libcalls", "Simplify well-known library calls");
01597 
01598 // Public interface to the Simplify LibCalls pass.
01599 FunctionPass *llvm::createSimplifyLibCallsPass() {
01600   return new SimplifyLibCalls(); 
01601 }
01602 
01603 /// Optimizations - Populate the Optimizations map with all the optimizations
01604 /// we know.
01605 void SimplifyLibCalls::InitOptimizations() {
01606   // Miscellaneous LibCall Optimizations
01607   Optimizations["exit"] = &Exit;
01608   
01609   // String and Memory LibCall Optimizations
01610   Optimizations["strcat"] = &StrCat;
01611   Optimizations["strncat"] = &StrNCat;
01612   Optimizations["strchr"] = &StrChr;
01613   Optimizations["strcmp"] = &StrCmp;
01614   Optimizations["strncmp"] = &StrNCmp;
01615   Optimizations["strcpy"] = &StrCpy;
01616   Optimizations["strncpy"] = &StrNCpy;
01617   Optimizations["strlen"] = &StrLen;
01618   Optimizations["strtol"] = &StrTo;
01619   Optimizations["strtod"] = &StrTo;
01620   Optimizations["strtof"] = &StrTo;
01621   Optimizations["strtoul"] = &StrTo;
01622   Optimizations["strtoll"] = &StrTo;
01623   Optimizations["strtold"] = &StrTo;
01624   Optimizations["strtoull"] = &StrTo;
01625   Optimizations["memcmp"] = &MemCmp;
01626   Optimizations["memcpy"] = &MemCpy;
01627   Optimizations["memmove"] = &MemMove;
01628   Optimizations["memset"] = &MemSet;
01629   
01630   // Math Library Optimizations
01631   Optimizations["powf"] = &Pow;
01632   Optimizations["pow"] = &Pow;
01633   Optimizations["powl"] = &Pow;
01634   Optimizations["llvm.pow.f32"] = &Pow;
01635   Optimizations["llvm.pow.f64"] = &Pow;
01636   Optimizations["llvm.pow.f80"] = &Pow;
01637   Optimizations["llvm.pow.f128"] = &Pow;
01638   Optimizations["llvm.pow.ppcf128"] = &Pow;
01639   Optimizations["exp2l"] = &Exp2;
01640   Optimizations["exp2"] = &Exp2;
01641   Optimizations["exp2f"] = &Exp2;
01642   Optimizations["llvm.exp2.ppcf128"] = &Exp2;
01643   Optimizations["llvm.exp2.f128"] = &Exp2;
01644   Optimizations["llvm.exp2.f80"] = &Exp2;
01645   Optimizations["llvm.exp2.f64"] = &Exp2;
01646   Optimizations["llvm.exp2.f32"] = &Exp2;
01647   
01648 #ifdef HAVE_FLOORF
01649   Optimizations["floor"] = &UnaryDoubleFP;
01650 #endif
01651 #ifdef HAVE_CEILF
01652   Optimizations["ceil"] = &UnaryDoubleFP;
01653 #endif
01654 #ifdef HAVE_ROUNDF
01655   Optimizations["round"] = &UnaryDoubleFP;
01656 #endif
01657 #ifdef HAVE_RINTF
01658   Optimizations["rint"] = &UnaryDoubleFP;
01659 #endif
01660 #ifdef HAVE_NEARBYINTF
01661   Optimizations["nearbyint"] = &UnaryDoubleFP;
01662 #endif
01663   
01664   // Integer Optimizations
01665   Optimizations["ffs"] = &FFS;
01666   Optimizations["ffsl"] = &FFS;
01667   Optimizations["ffsll"] = &FFS;
01668   Optimizations["abs"] = &Abs;
01669   Optimizations["labs"] = &Abs;
01670   Optimizations["llabs"] = &Abs;
01671   Optimizations["isdigit"] = &IsDigit;
01672   Optimizations["isascii"] = &IsAscii;
01673   Optimizations["toascii"] = &ToAscii;
01674   
01675   // Formatting and IO Optimizations
01676   Optimizations["sprintf"] = &SPrintF;
01677   Optimizations["printf"] = &PrintF;
01678   Optimizations["fwrite"] = &FWrite;
01679   Optimizations["fputs"] = &FPuts;
01680   Optimizations["fprintf"] = &FPrintF;
01681 }
01682 
01683 
01684 /// runOnFunction - Top level algorithm.
01685 ///
01686 bool SimplifyLibCalls::runOnFunction(Function &F) {
01687   if (Optimizations.empty())
01688     InitOptimizations();
01689   
01690   const TargetData *TD = getAnalysisIfAvailable<TargetData>();
01691   
01692   IRBuilder<> Builder(F.getContext());
01693 
01694   bool Changed = false;
01695   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
01696     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
01697       // Ignore non-calls.
01698       CallInst *CI = dyn_cast<CallInst>(I++);
01699       if (!CI) continue;
01700       
01701       // Ignore indirect calls and calls to non-external functions.
01702       Function *Callee = CI->getCalledFunction();
01703       if (Callee == 0 || !Callee->isDeclaration() ||
01704           !(Callee->hasExternalLinkage() || Callee->hasDLLImportLinkage()))
01705         continue;
01706       
01707       // Ignore unknown calls.
01708       LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
01709       if (!LCO) continue;
01710       
01711       // Set the builder to the instruction after the call.
01712       Builder.SetInsertPoint(BB, I);
01713       
01714       // Try to optimize this call.
01715       Value *Result = LCO->OptimizeCall(CI, TD, Builder);
01716       if (Result == 0) continue;
01717 
01718       DEBUG(errs() << "SimplifyLibCalls simplified: " << *CI;
01719             errs() << "  into: " << *Result << "\n");
01720       
01721       // Something changed!
01722       Changed = true;
01723       ++NumSimplified;
01724       
01725       // Inspect the instruction after the call (which was potentially just
01726       // added) next.
01727       I = CI; ++I;
01728       
01729       if (CI != Result && !CI->use_empty()) {
01730         CI->replaceAllUsesWith(Result);
01731         if (!Result->hasName())
01732           Result->takeName(CI);
01733       }
01734       CI->eraseFromParent();
01735     }
01736   }
01737   return Changed;
01738 }
01739 
01740 // Utility methods for doInitialization.
01741 
01742 void SimplifyLibCalls::setDoesNotAccessMemory(Function &F) {
01743   if (!F.doesNotAccessMemory()) {
01744     F.setDoesNotAccessMemory();
01745     ++NumAnnotated;
01746     Modified = true;
01747   }
01748 }
01749 void SimplifyLibCalls::setOnlyReadsMemory(Function &F) {
01750   if (!F.onlyReadsMemory()) {
01751     F.setOnlyReadsMemory();
01752     ++NumAnnotated;
01753     Modified = true;
01754   }
01755 }
01756 void SimplifyLibCalls::setDoesNotThrow(Function &F) {
01757   if (!F.doesNotThrow()) {
01758     F.setDoesNotThrow();
01759     ++NumAnnotated;
01760     Modified = true;
01761   }
01762 }
01763 void SimplifyLibCalls::setDoesNotCapture(Function &F, unsigned n) {
01764   if (!F.doesNotCapture(n)) {
01765     F.setDoesNotCapture(n);
01766     ++NumAnnotated;
01767     Modified = true;
01768   }
01769 }
01770 void SimplifyLibCalls::setDoesNotAlias(Function &F, unsigned n) {
01771   if (!F.doesNotAlias(n)) {
01772     F.setDoesNotAlias(n);
01773     ++NumAnnotated;
01774     Modified = true;
01775   }
01776 }
01777 
01778 /// doInitialization - Add attributes to well-known functions.
01779 ///
01780 bool SimplifyLibCalls::doInitialization(Module &M) {
01781   Modified = false;
01782   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
01783     Function &F = *I;
01784     if (!F.isDeclaration())
01785       continue;
01786 
01787     if (!F.hasName())
01788       continue;
01789 
01790     const FunctionType *FTy = F.getFunctionType();
01791 
01792     StringRef Name = F.getName();
01793     switch (Name[0]) {
01794       case 's':
01795         if (Name == "strlen") {
01796           if (FTy->getNumParams() != 1 ||
01797               !isa<PointerType>(FTy->getParamType(0)))
01798             continue;
01799           setOnlyReadsMemory(F);
01800           setDoesNotThrow(F);
01801           setDoesNotCapture(F, 1);
01802         } else if (Name == "strcpy" ||
01803                    Name == "stpcpy" ||
01804                    Name == "strcat" ||
01805                    Name == "strtol" ||
01806                    Name == "strtod" ||
01807                    Name == "strtof" ||
01808                    Name == "strtoul" ||
01809                    Name == "strtoll" ||
01810                    Name == "strtold" ||
01811                    Name == "strncat" ||
01812                    Name == "strncpy" ||
01813                    Name == "strtoull") {
01814           if (FTy->getNumParams() < 2 ||
01815               !isa<PointerType>(FTy->getParamType(1)))
01816             continue;
01817           setDoesNotThrow(F);
01818           setDoesNotCapture(F, 2);
01819         } else if (Name == "strxfrm") {
01820           if (FTy->getNumParams() != 3 ||
01821               !isa<PointerType>(FTy->getParamType(0)) ||
01822               !isa<PointerType>(FTy->getParamType(1)))
01823             continue;
01824           setDoesNotThrow(F);
01825           setDoesNotCapture(F, 1);
01826           setDoesNotCapture(F, 2);
01827         } else if (Name == "strcmp" ||
01828                    Name == "strspn" ||
01829                    Name == "strncmp" ||
01830                    Name ==" strcspn" ||
01831                    Name == "strcoll" ||
01832                    Name == "strcasecmp" ||
01833                    Name == "strncasecmp") {
01834           if (FTy->getNumParams() < 2 ||
01835               !isa<PointerType>(FTy->getParamType(0)) ||
01836               !isa<PointerType>(FTy->getParamType(1)))
01837             continue;
01838           setOnlyReadsMemory(F);
01839           setDoesNotThrow(F);
01840           setDoesNotCapture(F, 1);
01841           setDoesNotCapture(F, 2);
01842         } else if (Name == "strstr" ||
01843                    Name == "strpbrk") {
01844           if (FTy->getNumParams() != 2 ||
01845               !isa<PointerType>(FTy->getParamType(1)))
01846             continue;
01847           setOnlyReadsMemory(F);
01848           setDoesNotThrow(F);
01849           setDoesNotCapture(F, 2);
01850         } else if (Name == "strtok" ||
01851                    Name == "strtok_r") {
01852           if (FTy->getNumParams() < 2 ||
01853               !isa<PointerType>(FTy->getParamType(1)))
01854             continue;
01855           setDoesNotThrow(F);
01856           setDoesNotCapture(F, 2);
01857         } else if (Name == "scanf" ||
01858                    Name == "setbuf" ||
01859                    Name == "setvbuf") {
01860           if (FTy->getNumParams() < 1 ||
01861               !isa<PointerType>(FTy->getParamType(0)))
01862             continue;
01863           setDoesNotThrow(F);
01864           setDoesNotCapture(F, 1);
01865         } else if (Name == "strdup" ||
01866                    Name == "strndup") {
01867           if (FTy->getNumParams() < 1 ||
01868               !isa<PointerType>(FTy->getReturnType()) ||
01869               !isa<PointerType>(FTy->getParamType(0)))
01870             continue;
01871           setDoesNotThrow(F);
01872           setDoesNotAlias(F, 0);
01873           setDoesNotCapture(F, 1);
01874         } else if (Name == "stat" ||
01875                    Name == "sscanf" ||
01876                    Name == "sprintf" ||
01877                    Name == "statvfs") {
01878           if (FTy->getNumParams() < 2 ||
01879               !isa<PointerType>(FTy->getParamType(0)) ||
01880               !isa<PointerType>(FTy->getParamType(1)))
01881             continue;
01882           setDoesNotThrow(F);
01883           setDoesNotCapture(F, 1);
01884           setDoesNotCapture(F, 2);
01885         } else if (Name == "snprintf") {
01886           if (FTy->getNumParams() != 3 ||
01887               !isa<PointerType>(FTy->getParamType(0)) ||
01888               !isa<PointerType>(FTy->getParamType(2)))
01889             continue;
01890           setDoesNotThrow(F);
01891           setDoesNotCapture(F, 1);
01892           setDoesNotCapture(F, 3);
01893         } else if (Name == "setitimer") {
01894           if (FTy->getNumParams() != 3 ||
01895               !isa<PointerType>(FTy->getParamType(1)) ||
01896               !isa<PointerType>(FTy->getParamType(2)))
01897             continue;
01898           setDoesNotThrow(F);
01899           setDoesNotCapture(F, 2);
01900           setDoesNotCapture(F, 3);
01901         } else if (Name == "system") {
01902           if (FTy->getNumParams() != 1 ||
01903               !isa<PointerType>(FTy->getParamType(0)))
01904             continue;
01905           // May throw; "system" is a valid pthread cancellation point.
01906           setDoesNotCapture(F, 1);
01907         }
01908         break;
01909       case 'm':
01910         if (Name == "memcmp") {
01911           if (FTy->getNumParams() != 3 ||
01912               !isa<PointerType>(FTy->getParamType(0)) ||
01913               !isa<PointerType>(FTy->getParamType(1)))
01914             continue;
01915           setOnlyReadsMemory(F);
01916           setDoesNotThrow(F);
01917           setDoesNotCapture(F, 1);
01918           setDoesNotCapture(F, 2);
01919         } else if (Name == "memchr" ||
01920                    Name == "memrchr") {
01921           if (FTy->getNumParams() != 3)
01922             continue;
01923           setOnlyReadsMemory(F);
01924           setDoesNotThrow(F);
01925         } else if (Name == "modf" ||
01926                    Name == "modff" ||
01927                    Name == "modfl" ||
01928                    Name == "memcpy" ||
01929                    Name == "memccpy" ||
01930                    Name == "memmove") {
01931           if (FTy->getNumParams() < 2 ||
01932               !isa<PointerType>(FTy->getParamType(1)))
01933             continue;
01934           setDoesNotThrow(F);
01935           setDoesNotCapture(F, 2);
01936         } else if (Name == "memalign") {
01937           if (!isa<PointerType>(FTy->getReturnType()))
01938             continue;
01939           setDoesNotAlias(F, 0);
01940         } else if (Name == "mkdir" ||
01941                    Name == "mktime") {
01942           if (FTy->getNumParams() == 0 ||
01943               !isa<PointerType>(FTy->getParamType(0)))
01944             continue;
01945           setDoesNotThrow(F);
01946           setDoesNotCapture(F, 1);
01947         }
01948         break;
01949       case 'r':
01950         if (Name == "realloc") {
01951           if (FTy->getNumParams() != 2 ||
01952               !isa<PointerType>(FTy->getParamType(0)) ||
01953               !isa<PointerType>(FTy->getReturnType()))
01954             continue;
01955           setDoesNotThrow(F);
01956           setDoesNotAlias(F, 0);
01957           setDoesNotCapture(F, 1);
01958         } else if (Name == "read") {
01959           if (FTy->getNumParams() != 3 ||
01960               !isa<PointerType>(FTy->getParamType(1)))
01961             continue;
01962           // May throw; "read" is a valid pthread cancellation point.
01963           setDoesNotCapture(F, 2);
01964         } else if (Name == "rmdir" ||
01965                    Name == "rewind" ||
01966                    Name == "remove" ||
01967                    Name == "realpath") {
01968           if (FTy->getNumParams() < 1 ||
01969               !isa<PointerType>(FTy->getParamType(0)))
01970             continue;
01971           setDoesNotThrow(F);
01972           setDoesNotCapture(F, 1);
01973         } else if (Name == "rename" ||
01974                    Name == "readlink") {
01975           if (FTy->getNumParams() < 2 ||
01976               !isa<PointerType>(FTy->getParamType(0)) ||
01977               !isa<PointerType>(FTy->getParamType(1)))
01978             continue;
01979           setDoesNotThrow(F);
01980           setDoesNotCapture(F, 1);
01981           setDoesNotCapture(F, 2);
01982         }
01983         break;
01984       case 'w':
01985         if (Name == "write") {
01986           if (FTy->getNumParams() != 3 ||
01987               !isa<PointerType>(FTy->getParamType(1)))
01988             continue;
01989           // May throw; "write" is a valid pthread cancellation point.
01990           setDoesNotCapture(F, 2);
01991         }
01992         break;
01993       case 'b':
01994         if (Name == "bcopy") {
01995           if (FTy->getNumParams() != 3 ||
01996               !isa<PointerType>(FTy->getParamType(0)) ||
01997               !isa<PointerType>(FTy->getParamType(1)))
01998             continue;
01999           setDoesNotThrow(F);
02000           setDoesNotCapture(F, 1);
02001           setDoesNotCapture(F, 2);
02002         } else if (Name == "bcmp") {
02003           if (FTy->getNumParams() != 3 ||
02004               !isa<PointerType>(FTy->getParamType(0)) ||
02005               !isa<PointerType>(FTy->getParamType(1)))
02006             continue;
02007           setDoesNotThrow(F);
02008           setOnlyReadsMemory(F);
02009           setDoesNotCapture(F, 1);
02010           setDoesNotCapture(F, 2);
02011         } else if (Name == "bzero") {
02012           if (FTy->getNumParams() != 2 ||
02013               !isa<PointerType>(FTy->getParamType(0)))
02014             continue;
02015           setDoesNotThrow(F);
02016           setDoesNotCapture(F, 1);
02017         }
02018         break;
02019       case 'c':
02020         if (Name == "calloc") {
02021           if (FTy->getNumParams() != 2 ||
02022               !isa<PointerType>(FTy->getReturnType()))
02023             continue;
02024           setDoesNotThrow(F);
02025           setDoesNotAlias(F, 0);
02026         } else if (Name == "chmod" ||
02027                    Name == "chown" ||
02028                    Name == "ctermid" ||
02029                    Name == "clearerr" ||
02030                    Name == "closedir") {
02031           if (FTy->getNumParams() == 0 ||
02032               !isa<PointerType>(FTy->getParamType(0)))
02033             continue;
02034           setDoesNotThrow(F);
02035           setDoesNotCapture(F, 1);
02036         }
02037         break;
02038       case 'a':
02039         if (Name == "atoi" ||
02040             Name == "atol" ||
02041             Name == "atof" ||
02042             Name == "atoll") {
02043           if (FTy->getNumParams() != 1 ||
02044               !isa<PointerType>(FTy->getParamType(0)))
02045             continue;
02046           setDoesNotThrow(F);
02047           setOnlyReadsMemory(F);
02048           setDoesNotCapture(F, 1);
02049         } else if (Name == "access") {
02050           if (FTy->getNumParams() != 2 ||
02051               !isa<PointerType>(FTy->getParamType(0)))
02052             continue;
02053           setDoesNotThrow(F);
02054           setDoesNotCapture(F, 1);
02055         }
02056         break;
02057       case 'f':
02058         if (Name == "fopen") {
02059           if (FTy->getNumParams() != 2 ||
02060               !isa<PointerType>(FTy->getReturnType()) ||
02061               !isa<PointerType>(FTy->getParamType(0)) ||
02062               !isa<PointerType>(FTy->getParamType(1)))
02063             continue;
02064           setDoesNotThrow(F);
02065           setDoesNotAlias(F, 0);
02066           setDoesNotCapture(F, 1);
02067           setDoesNotCapture(F, 2);
02068         } else if (Name == "fdopen") {
02069           if (FTy->getNumParams() != 2 ||
02070               !isa<PointerType>(FTy->getReturnType()) ||
02071               !isa<PointerType>(FTy->getParamType(1)))
02072             continue;
02073           setDoesNotThrow(F);
02074           setDoesNotAlias(F, 0);
02075           setDoesNotCapture(F, 2);
02076         } else if (Name == "feof" ||
02077                    Name == "free" ||
02078                    Name == "fseek" ||
02079                    Name == "ftell" ||
02080                    Name == "fgetc" ||
02081                    Name == "fseeko" ||
02082                    Name == "ftello" ||
02083                    Name == "fileno" ||
02084                    Name == "fflush" ||
02085                    Name == "fclose" ||
02086                    Name == "fsetpos" ||
02087                    Name == "flockfile" ||
02088                    Name == "funlockfile" ||
02089                    Name == "ftrylockfile") {
02090           if (FTy->getNumParams() == 0 ||
02091               !isa<PointerType>(FTy->getParamType(0)))
02092             continue;
02093           setDoesNotThrow(F);
02094           setDoesNotCapture(F, 1);
02095         } else if (Name == "ferror") {
02096           if (FTy->getNumParams() != 1 ||
02097               !isa<PointerType>(FTy->getParamType(0)))
02098             continue;
02099           setDoesNotThrow(F);
02100           setDoesNotCapture(F, 1);
02101           setOnlyReadsMemory(F);
02102         } else if (Name == "fputc" ||
02103                    Name == "fstat" ||
02104                    Name == "frexp" ||
02105                    Name == "frexpf" ||
02106                    Name == "frexpl" ||
02107                    Name == "fstatvfs") {
02108           if (FTy->getNumParams() != 2 ||
02109               !isa<PointerType>(FTy->getParamType(1)))
02110             continue;
02111           setDoesNotThrow(F);
02112           setDoesNotCapture(F, 2);
02113         } else if (Name == "fgets") {
02114           if (FTy->getNumParams() != 3 ||
02115               !isa<PointerType>(FTy->getParamType(0)) ||
02116               !isa<PointerType>(FTy->getParamType(2)))
02117             continue;
02118           setDoesNotThrow(F);
02119           setDoesNotCapture(F, 3);
02120         } else if (Name == "fread" ||
02121                    Name == "fwrite") {
02122           if (FTy->getNumParams() != 4 ||
02123               !isa<PointerType>(FTy->getParamType(0)) ||
02124               !isa<PointerType>(FTy->getParamType(3)))
02125             continue;
02126           setDoesNotThrow(F);
02127           setDoesNotCapture(F, 1);
02128           setDoesNotCapture(F, 4);
02129         } else if (Name == "fputs" ||
02130                    Name == "fscanf" ||
02131                    Name == "fprintf" ||
02132                    Name == "fgetpos") {
02133           if (FTy->getNumParams() < 2 ||
02134               !isa<PointerType>(FTy->getParamType(0)) ||
02135               !isa<PointerType>(FTy->getParamType(1)))
02136             continue;
02137           setDoesNotThrow(F);
02138           setDoesNotCapture(F, 1);
02139           setDoesNotCapture(F, 2);
02140         }
02141         break;
02142       case 'g':
02143         if (Name == "getc" ||
02144             Name == "getlogin_r" ||
02145             Name == "getc_unlocked") {
02146           if (FTy->getNumParams() == 0 ||
02147               !isa<PointerType>(FTy->getParamType(0)))
02148             continue;
02149           setDoesNotThrow(F);
02150           setDoesNotCapture(F, 1);
02151         } else if (Name == "getenv") {
02152           if (FTy->getNumParams() != 1 ||
02153               !isa<PointerType>(FTy->getParamType(0)))
02154             continue;
02155           setDoesNotThrow(F);
02156           setOnlyReadsMemory(F);
02157           setDoesNotCapture(F, 1);
02158         } else if (Name == "gets" ||
02159                    Name == "getchar") {
02160           setDoesNotThrow(F);
02161         } else if (Name == "getitimer") {
02162           if (FTy->getNumParams() != 2 ||
02163               !isa<PointerType>(FTy->getParamType(1)))
02164             continue;
02165           setDoesNotThrow(F);
02166           setDoesNotCapture(F, 2);
02167         } else if (Name == "getpwnam") {
02168           if (FTy->getNumParams() != 1 ||
02169               !isa<PointerType>(FTy->getParamType(0)))
02170             continue;
02171           setDoesNotThrow(F);
02172           setDoesNotCapture(F, 1);
02173         }
02174         break;
02175       case 'u':
02176         if (Name == "ungetc") {
02177           if (FTy->getNumParams() != 2 ||
02178               !isa<PointerType>(FTy->getParamType(1)))
02179             continue;
02180           setDoesNotThrow(F);
02181           setDoesNotCapture(F, 2);
02182         } else if (Name == "uname" ||
02183                    Name == "unlink" ||
02184                    Name == "unsetenv") {
02185           if (FTy->getNumParams() != 1 ||
02186               !isa<PointerType>(FTy->getParamType(0)))
02187             continue;
02188           setDoesNotThrow(F);
02189           setDoesNotCapture(F, 1);
02190         } else if (Name == "utime" ||
02191                    Name == "utimes") {
02192           if (FTy->getNumParams() != 2 ||
02193               !isa<PointerType>(FTy->getParamType(0)) ||
02194               !isa<PointerType>(FTy->getParamType(1)))
02195             continue;
02196           setDoesNotThrow(F);
02197           setDoesNotCapture(F, 1);
02198           setDoesNotCapture(F, 2);
02199         }
02200         break;
02201       case 'p':
02202         if (Name == "putc") {
02203           if (FTy->getNumParams() != 2 ||
02204               !isa<PointerType>(FTy->getParamType(1)))
02205             continue;
02206           setDoesNotThrow(F);
02207           setDoesNotCapture(F, 2);
02208         } else if (Name == "puts" ||
02209                    Name == "printf" ||
02210                    Name == "perror") {
02211           if (FTy->getNumParams() != 1 ||
02212               !isa<PointerType>(FTy->getParamType(0)))
02213             continue;
02214           setDoesNotThrow(F);
02215           setDoesNotCapture(F, 1);
02216         } else if (Name == "pread" ||
02217                    Name == "pwrite") {
02218           if (FTy->getNumParams() != 4 ||
02219               !isa<PointerType>(FTy->getParamType(1)))
02220             continue;
02221           // May throw; these are valid pthread cancellation points.
02222           setDoesNotCapture(F, 2);
02223         } else if (Name == "putchar") {
02224           setDoesNotThrow(F);
02225         } else if (Name == "popen") {
02226           if (FTy->getNumParams() != 2 ||
02227               !isa<PointerType>(FTy->getReturnType()) ||
02228               !isa<PointerType>(FTy->getParamType(0)) ||
02229               !isa<PointerType>(FTy->getParamType(1)))
02230             continue;
02231           setDoesNotThrow(F);
02232           setDoesNotAlias(F, 0);
02233           setDoesNotCapture(F, 1);
02234           setDoesNotCapture(F, 2);
02235         } else if (Name == "pclose") {
02236           if (FTy->getNumParams() != 1 ||
02237               !isa<PointerType>(FTy->getParamType(0)))
02238             continue;
02239           setDoesNotThrow(F);
02240           setDoesNotCapture(F, 1);
02241         }
02242         break;
02243       case 'v':
02244         if (Name == "vscanf") {
02245           if (FTy->getNumParams() != 2 ||
02246               !isa<PointerType>(FTy->getParamType(1)))
02247             continue;
02248           setDoesNotThrow(F);
02249           setDoesNotCapture(F, 1);
02250         } else if (Name == "vsscanf" ||
02251                    Name == "vfscanf") {
02252           if (FTy->getNumParams() != 3 ||
02253               !isa<PointerType>(FTy->getParamType(1)) ||
02254               !isa<PointerType>(FTy->getParamType(2)))
02255             continue;
02256           setDoesNotThrow(F);
02257           setDoesNotCapture(F, 1);
02258           setDoesNotCapture(F, 2);
02259         } else if (Name == "valloc") {
02260           if (!isa<PointerType>(FTy->getReturnType()))
02261             continue;
02262           setDoesNotThrow(F);
02263           setDoesNotAlias(F, 0);
02264         } else if (Name == "vprintf") {
02265           if (FTy->getNumParams() != 2 ||
02266               !isa<PointerType>(FTy->getParamType(0)))
02267             continue;
02268           setDoesNotThrow(F);
02269           setDoesNotCapture(F, 1);
02270         } else if (Name == "vfprintf" ||
02271                    Name == "vsprintf") {
02272           if (FTy->getNumParams() != 3 ||
02273               !isa<PointerType>(FTy->getParamType(0)) ||
02274               !isa<PointerType>(FTy->getParamType(1)))
02275             continue;
02276           setDoesNotThrow(F);
02277           setDoesNotCapture(F, 1);
02278           setDoesNotCapture(F, 2);
02279         } else if (Name == "vsnprintf") {
02280           if (FTy->getNumParams() != 4 ||
02281               !isa<PointerType>(FTy->getParamType(0)) ||
02282               !isa<PointerType>(FTy->getParamType(2)))
02283             continue;
02284           setDoesNotThrow(F);
02285           setDoesNotCapture(F, 1);
02286           setDoesNotCapture(F, 3);
02287         }
02288         break;
02289       case 'o':
02290         if (Name == "open") {
02291           if (FTy->getNumParams() < 2 ||
02292               !isa<PointerType>(FTy->getParamType(0)))
02293             continue;
02294           // May throw; "open" is a valid pthread cancellation point.
02295           setDoesNotCapture(F, 1);
02296         } else if (Name == "opendir") {
02297           if (FTy->getNumParams() != 1 ||
02298               !isa<PointerType>(FTy->getReturnType()) ||
02299               !isa<PointerType>(FTy->getParamType(0)))
02300             continue;
02301           setDoesNotThrow(F);
02302           setDoesNotAlias(F, 0);
02303           setDoesNotCapture(F, 1);
02304         }
02305         break;
02306       case 't':
02307         if (Name == "tmpfile") {
02308           if (!isa<PointerType>(FTy->getReturnType()))
02309             continue;
02310           setDoesNotThrow(F);
02311           setDoesNotAlias(F, 0);
02312         } else if (Name == "times") {
02313           if (FTy->getNumParams() != 1 ||
02314               !isa<PointerType>(FTy->getParamType(0)))
02315             continue;
02316           setDoesNotThrow(F);
02317           setDoesNotCapture(F, 1);
02318         }
02319         break;
02320       case 'h':
02321         if (Name == "htonl" ||
02322             Name == "htons") {
02323           setDoesNotThrow(F);
02324           setDoesNotAccessMemory(F);
02325         }
02326         break;
02327       case 'n':
02328         if (Name == "ntohl" ||
02329             Name == "ntohs") {
02330           setDoesNotThrow(F);
02331           setDoesNotAccessMemory(F);
02332         }
02333         break;
02334       case 'l':
02335         if (Name == "lstat") {
02336           if (FTy->getNumParams() != 2 ||
02337               !isa<PointerType>(FTy->getParamType(0)) ||
02338               !isa<PointerType>(FTy->getParamType(1)))
02339             continue;
02340           setDoesNotThrow(F);
02341           setDoesNotCapture(F, 1);
02342           setDoesNotCapture(F, 2);
02343         } else if (Name == "lchown") {
02344           if (FTy->getNumParams() != 3 ||
02345               !isa<PointerType>(FTy->getParamType(0)))
02346             continue;
02347           setDoesNotThrow(F);
02348           setDoesNotCapture(F, 1);
02349         }
02350         break;
02351       case 'q':
02352         if (Name == "qsort") {
02353           if (FTy->getNumParams() != 4 ||
02354               !isa<PointerType>(FTy->getParamType(3)))
02355             continue;
02356           // May throw; places call through function pointer.
02357           setDoesNotCapture(F, 4);
02358         }
02359         break;
02360       case '_':
02361         if (Name == "__strdup" ||
02362             Name == "__strndup") {
02363           if (FTy->getNumParams() < 1 ||
02364               !isa<PointerType>(FTy->getReturnType()) ||
02365               !isa<PointerType>(FTy->getParamType(0)))
02366             continue;
02367           setDoesNotThrow(F);
02368           setDoesNotAlias(F, 0);
02369           setDoesNotCapture(F, 1);
02370         } else if (Name == "__strtok_r") {
02371           if (FTy->getNumParams() != 3 ||
02372               !isa<PointerType>(FTy->getParamType(1)))
02373             continue;
02374           setDoesNotThrow(F);
02375           setDoesNotCapture(F, 2);
02376         } else if (Name == "_IO_getc") {
02377           if (FTy->getNumParams() != 1 ||
02378               !isa<PointerType>(FTy->getParamType(0)))
02379             continue;
02380           setDoesNotThrow(F);
02381           setDoesNotCapture(F, 1);
02382         } else if (Name == "_IO_putc") {
02383           if (FTy->getNumParams() != 2 ||
02384               !isa<PointerType>(FTy->getParamType(1)))
02385             continue;
02386           setDoesNotThrow(F);
02387           setDoesNotCapture(F, 2);
02388         }
02389         break;
02390       case 1:
02391         if (Name == "\1__isoc99_scanf") {
02392           if (FTy->getNumParams() < 1 ||
02393               !isa<PointerType>(FTy->getParamType(0)))
02394             continue;
02395           setDoesNotThrow(F);
02396           setDoesNotCapture(F, 1);
02397         } else if (Name == "\1stat64" ||
02398                    Name == "\1lstat64" ||
02399                    Name == "\1statvfs64" ||
02400                    Name == "\1__isoc99_sscanf") {
02401           if (FTy->getNumParams() < 1 ||
02402               !isa<PointerType>(FTy->getParamType(0)) ||
02403               !isa<PointerType>(FTy->getParamType(1)))
02404             continue;
02405           setDoesNotThrow(F);
02406           setDoesNotCapture(F, 1);
02407           setDoesNotCapture(F, 2);
02408         } else if (Name == "\1fopen64") {
02409           if (FTy->getNumParams() != 2 ||
02410               !isa<PointerType>(FTy->getReturnType()) ||
02411               !isa<PointerType>(FTy->getParamType(0)) ||
02412               !isa<PointerType>(FTy->getParamType(1)))
02413             continue;
02414           setDoesNotThrow(F);
02415           setDoesNotAlias(F, 0);
02416           setDoesNotCapture(F, 1);
02417           setDoesNotCapture(F, 2);
02418         } else if (Name == "\1fseeko64" ||
02419                    Name == "\1ftello64") {
02420           if (FTy->getNumParams() == 0 ||
02421               !isa<PointerType>(FTy->getParamType(0)))
02422             continue;
02423           setDoesNotThrow(F);
02424           setDoesNotCapture(F, 1);
02425         } else if (Name == "\1tmpfile64") {
02426           if (!isa<PointerType>(FTy->getReturnType()))
02427             continue;
02428           setDoesNotThrow(F);
02429           setDoesNotAlias(F, 0);
02430         } else if (Name == "\1fstat64" ||
02431                    Name == "\1fstatvfs64") {
02432           if (FTy->getNumParams() != 2 ||
02433               !isa<PointerType>(FTy->getParamType(1)))
02434             continue;
02435           setDoesNotThrow(F);
02436           setDoesNotCapture(F, 2);
02437         } else if (Name == "\1open64") {
02438           if (FTy->getNumParams() < 2 ||
02439               !isa<PointerType>(FTy->getParamType(0)))
02440             continue;
02441           // May throw; "open" is a valid pthread cancellation point.
02442           setDoesNotCapture(F, 1);
02443         }
02444         break;
02445     }
02446   }
02447   return Modified;
02448 }
02449 
02450 // TODO:
02451 //   Additional cases that we need to add to this file:
02452 //
02453 // cbrt:
02454 //   * cbrt(expN(X))  -> expN(x/3)
02455 //   * cbrt(sqrt(x))  -> pow(x,1/6)
02456 //   * cbrt(sqrt(x))  -> pow(x,1/9)
02457 //
02458 // cos, cosf, cosl:
02459 //   * cos(-x)  -> cos(x)
02460 //
02461 // exp, expf, expl:
02462 //   * exp(log(x))  -> x
02463 //
02464 // log, logf, logl:
02465 //   * log(exp(x))   -> x
02466 //   * log(x**y)     -> y*log(x)
02467 //   * log(exp(y))   -> y*log(e)
02468 //   * log(exp2(y))  -> y*log(2)
02469 //   * log(exp10(y)) -> y*log(10)
02470 //   * log(sqrt(x))  -> 0.5*log(x)
02471 //   * log(pow(x,y)) -> y*log(x)
02472 //
02473 // lround, lroundf, lroundl:
02474 //   * lround(cnst) -> cnst'
02475 //
02476 // memcmp:
02477 //   * memcmp(x,y,l)   -> cnst
02478 //      (if all arguments are constant and strlen(x) <= l and strlen(y) <= l)
02479 //
02480 // pow, powf, powl:
02481 //   * pow(exp(x),y)  -> exp(x*y)
02482 //   * pow(sqrt(x),y) -> pow(x,y*0.5)
02483 //   * pow(pow(x,y),z)-> pow(x,y*z)
02484 //
02485 // puts:
02486 //   * puts("") -> putchar("\n")
02487 //
02488 // round, roundf, roundl:
02489 //   * round(cnst) -> cnst'
02490 //
02491 // signbit:
02492 //   * signbit(cnst) -> cnst'
02493 //   * signbit(nncst) -> 0 (if pstv is a non-negative constant)
02494 //
02495 // sqrt, sqrtf, sqrtl:
02496 //   * sqrt(expN(x))  -> expN(x*0.5)
02497 //   * sqrt(Nroot(x)) -> pow(x,1/(2*N))
02498 //   * sqrt(pow(x,y)) -> pow(|x|,y*0.5)
02499 //
02500 // stpcpy:
02501 //   * stpcpy(str, "literal") ->
02502 //           llvm.memcpy(str,"literal",strlen("literal")+1,1)
02503 // strrchr:
02504 //   * strrchr(s,c) -> reverse_offset_of_in(c,s)
02505 //      (if c is a constant integer and s is a constant string)
02506 //   * strrchr(s1,0) -> strchr(s1,0)
02507 //
02508 // strpbrk:
02509 //   * strpbrk(s,a) -> offset_in_for(s,a)
02510 //      (if s and a are both constant strings)
02511 //   * strpbrk(s,"") -> 0
02512 //   * strpbrk(s,a) -> strchr(s,a[0]) (if a is constant string of length 1)
02513 //
02514 // strspn, strcspn:
02515 //   * strspn(s,a)   -> const_int (if both args are constant)
02516 //   * strspn("",a)  -> 0
02517 //   * strspn(s,"")  -> 0
02518 //   * strcspn(s,a)  -> const_int (if both args are constant)
02519 //   * strcspn("",a) -> 0
02520 //   * strcspn(s,"") -> strlen(a)
02521 //
02522 // strstr:
02523 //   * strstr(x,x)  -> x
02524 //   * strstr(s1,s2) -> offset_of_s2_in(s1)
02525 //       (if s1 and s2 are constant strings)
02526 //
02527 // tan, tanf, tanl:
02528 //   * tan(atan(x)) -> x
02529 //
02530 // trunc, truncf, truncl:
02531 //   * trunc(cnst) -> cnst'
02532 //
02533 //