lib/Transforms/Scalar/SimplifyLibCalls.cpp

   1 //===- SimplifyLibCalls.cpp - Optimize specific well-known library calls --===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements a simple pass that applies a variety of small
  11 // optimizations for calls to specific well-known function calls (e.g. runtime
  12 // library functions).   Any optimization that takes the very simple form
  13 // "replace call to library function with simpler code that provides the same
  14 // result" belongs in this file.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #define DEBUG_TYPE "simplify-libcalls"
  19 #include "llvm/Transforms/Scalar.h"
  20 #include "llvm/Intrinsics.h"
  21 #include "llvm/LLVMContext.h"
  22 #include "llvm/Module.h"
  23 #include "llvm/Pass.h"
  24 #include "llvm/Support/IRBuilder.h"
  25 #include "llvm/Analysis/ValueTracking.h"
  26 #include "llvm/Target/TargetData.h"
  27 #include "llvm/ADT/SmallPtrSet.h"
  28 #include "llvm/ADT/StringMap.h"
  29 #include "llvm/ADT/Statistic.h"
  30 #include "llvm/ADT/STLExtras.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/raw_ostream.h"
  33 #include "llvm/Config/config.h"
  34 using namespace llvm;
  35
  36 STATISTIC(NumSimplified, "Number of library calls simplified");
  37 STATISTIC(NumAnnotated, "Number of attributes added to library functions");
  38
  39 //===----------------------------------------------------------------------===//
  40 // Optimizer Base Class
  41 //===----------------------------------------------------------------------===//
  42
  43 /// This class is the abstract base class for the set of optimizations that
  44 /// corresponds to one library call.
  45 namespace {
  46 class LibCallOptimization {
  47 protected:
  48   Function *Caller;
  49   const TargetData *TD;
  50   LLVMContext* Context;
  51 public:
  52   LibCallOptimization() { }
  53   virtual ~LibCallOptimization() {}
  54
  55   /// CallOptimizer - This pure virtual method is implemented by base classes to
  56   /// do various optimizations.  If this returns null then no transformation was
  57   /// performed.  If it returns CI, then it transformed the call and CI is to be
  58   /// deleted.  If it returns something else, replace CI with the new value and
  59   /// delete CI.
  60   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B)
  61     =0;
  62
  63   Value *OptimizeCall(CallInst *CI, const TargetData *TD, IRBuilder<> &B) {
  64     Caller = CI->getParent()->getParent();
  65     this->TD = TD;
  66     if (CI->getCalledFunction())
  67       Context = &CI->getCalledFunction()->getContext();
  68     return CallOptimizer(CI->getCalledFunction(), CI, B);
  69   }
  70
  71   /// CastToCStr - Return V if it is an i8*, otherwise cast it to i8*.
  72   Value *CastToCStr(Value *V, IRBuilder<> &B);
  73
  74   /// EmitStrLen - Emit a call to the strlen function to the builder, for the
  75   /// specified pointer.  Ptr is required to be some pointer type, and the
  76   /// return value has 'intptr_t' type.
  77   Value *EmitStrLen(Value *Ptr, IRBuilder<> &B);
  78
  79   /// EmitMemCpy - Emit a call to the memcpy function to the builder.  This
  80   /// always expects that the size has type 'intptr_t' and Dst/Src are pointers.
  81   Value *EmitMemCpy(Value *Dst, Value *Src, Value *Len,
  82                     unsigned Align, IRBuilder<> &B);
  83
  84   /// EmitMemChr - Emit a call to the memchr function.  This assumes that Ptr is
  85   /// a pointer, Val is an i32 value, and Len is an 'intptr_t' value.
  86   Value *EmitMemChr(Value *Ptr, Value *Val, Value *Len, IRBuilder<> &B);
  87
  88   /// EmitMemCmp - Emit a call to the memcmp function.
  89   Value *EmitMemCmp(Value *Ptr1, Value *Ptr2, Value *Len, IRBuilder<> &B);
  90
  91   /// EmitMemSet - Emit a call to the memset function
  92   Value *EmitMemSet(Value *Dst, Value *Val, Value *Len, IRBuilder<> &B);
  93
  94   /// EmitUnaryFloatFnCall - Emit a call to the unary function named 'Name' (e.g.
  95   /// 'floor').  This function is known to take a single of type matching 'Op'
  96   /// and returns one value with the same type.  If 'Op' is a long double, 'l'
  97   /// is added as the suffix of name, if 'Op' is a float, we add a 'f' suffix.
  98   Value *EmitUnaryFloatFnCall(Value *Op, const char *Name, IRBuilder<> &B);
  99
 100   /// EmitPutChar - Emit a call to the putchar function.  This assumes that Char
 101   /// is an integer.
 102   void EmitPutChar(Value *Char, IRBuilder<> &B);
 103
 104   /// EmitPutS - Emit a call to the puts function.  This assumes that Str is
 105   /// some pointer.
 106   void EmitPutS(Value *Str, IRBuilder<> &B);
 107
 108   /// EmitFPutC - Emit a call to the fputc function.  This assumes that Char is
 109   /// an i32, and File is a pointer to FILE.
 110   void EmitFPutC(Value *Char, Value *File, IRBuilder<> &B);
 111
 112   /// EmitFPutS - Emit a call to the puts function.  Str is required to be a
 113   /// pointer and File is a pointer to FILE.
 114   void EmitFPutS(Value *Str, Value *File, IRBuilder<> &B);
 115
 116   /// EmitFWrite - Emit a call to the fwrite function.  This assumes that Ptr is
 117   /// a pointer, Size is an 'intptr_t', and File is a pointer to FILE.
 118   void EmitFWrite(Value *Ptr, Value *Size, Value *File, IRBuilder<> &B);
 119
 120 };
 121 } // End anonymous namespace.
 122
 123 /// CastToCStr - Return V if it is an i8*, otherwise cast it to i8*.
 124 Value *LibCallOptimization::CastToCStr(Value *V, IRBuilder<> &B) {
 125   return
 126         B.CreateBitCast(V, PointerType::getUnqual(Type::getInt8Ty(*Context)), "cstr");
 127 }
 128
 129 /// EmitStrLen - Emit a call to the strlen function to the builder, for the
 130 /// specified pointer.  This always returns an integer value of size intptr_t.
 131 Value *LibCallOptimization::EmitStrLen(Value *Ptr, IRBuilder<> &B) {
 132   Module *M = Caller->getParent();
 133   AttributeWithIndex AWI[2];
 134   AWI[0] = AttributeWithIndex::get(1, Attribute::NoCapture);
 135   AWI[1] = AttributeWithIndex::get(~0u, Attribute::ReadOnly |
 136                                    Attribute::NoUnwind);
 137
 138   Constant *StrLen =M->getOrInsertFunction("strlen", AttrListPtr::get(AWI, 2),
 139                                            TD->getIntPtrType(*Context),
 140                                     PointerType::getUnqual(Type::getInt8Ty(*Context)),
 141                                            NULL);
 142   CallInst *CI = B.CreateCall(StrLen, CastToCStr(Ptr, B), "strlen");
 143   if (const Function *F = dyn_cast<Function>(StrLen->stripPointerCasts()))
 144     CI->setCallingConv(F->getCallingConv());
 145
 146   return CI;
 147 }
 148
 149 /// EmitMemCpy - Emit a call to the memcpy function to the builder.  This always
 150 /// expects that the size has type 'intptr_t' and Dst/Src are pointers.
 151 Value *LibCallOptimization::EmitMemCpy(Value *Dst, Value *Src, Value *Len,
 152                                        unsigned Align, IRBuilder<> &B) {
 153   Module *M = Caller->getParent();
 154   Intrinsic::ID IID = Intrinsic::memcpy;
 155   const Type *Tys[1];
 156   Tys[0] = Len->getType();
 157   Value *MemCpy = Intrinsic::getDeclaration(M, IID, Tys, 1);
 158   return B.CreateCall4(MemCpy, CastToCStr(Dst, B), CastToCStr(Src, B), Len,
 159                        ConstantInt::get(Type::getInt32Ty(*Context), Align));
 160 }
 161
 162 /// EmitMemChr - Emit a call to the memchr function.  This assumes that Ptr is
 163 /// a pointer, Val is an i32 value, and Len is an 'intptr_t' value.
 164 Value *LibCallOptimization::EmitMemChr(Value *Ptr, Value *Val,
 165                                        Value *Len, IRBuilder<> &B) {
 166   Module *M = Caller->getParent();
 167   AttributeWithIndex AWI;
 168   AWI = AttributeWithIndex::get(~0u, Attribute::ReadOnly | Attribute::NoUnwind);
 169
 170   Value *MemChr = M->getOrInsertFunction("memchr", AttrListPtr::get(&AWI, 1),
 171                                     PointerType::getUnqual(Type::getInt8Ty(*Context)),
 172                                     PointerType::getUnqual(Type::getInt8Ty(*Context)),
 173                                          Type::getInt32Ty(*Context), TD->getIntPtrType(*Context),
 174                                          NULL);
 175   CallInst *CI = B.CreateCall3(MemChr, CastToCStr(Ptr, B), Val, Len, "memchr");
 176
 177   if (const Function *F = dyn_cast<Function>(MemChr->stripPointerCasts()))
 178     CI->setCallingConv(F->getCallingConv());
 179
 180   return CI;
 181 }
 182
 183 /// EmitMemCmp - Emit a call to the memcmp function.
 184 Value *LibCallOptimization::EmitMemCmp(Value *Ptr1, Value *Ptr2,
 185                                        Value *Len, IRBuilder<> &B) {
 186   Module *M = Caller->getParent();
 187   AttributeWithIndex AWI[3];
 188   AWI[0] = AttributeWithIndex::get(1, Attribute::NoCapture);
 189   AWI[1] = AttributeWithIndex::get(2, Attribute::NoCapture);
 190   AWI[2] = AttributeWithIndex::get(~0u, Attribute::ReadOnly |
 191                                    Attribute::NoUnwind);
 192
 193   Value *MemCmp = M->getOrInsertFunction("memcmp", AttrListPtr::get(AWI, 3),
 194                                          Type::getInt32Ty(*Context),
 195                                     PointerType::getUnqual(Type::getInt8Ty(*Context)),
 196                                     PointerType::getUnqual(Type::getInt8Ty(*Context)),
 197                                          TD->getIntPtrType(*Context), NULL);
 198   CallInst *CI = B.CreateCall3(MemCmp, CastToCStr(Ptr1, B), CastToCStr(Ptr2, B),
 199                                Len, "memcmp");
 200
 201   if (const Function *F = dyn_cast<Function>(MemCmp->stripPointerCasts()))
 202     CI->setCallingConv(F->getCallingConv());
 203
 204   return CI;
 205 }
 206
 207 /// EmitMemSet - Emit a call to the memset function
 208 Value *LibCallOptimization::EmitMemSet(Value *Dst, Value *Val,
 209                                        Value *Len, IRBuilder<> &B) {
 210  Module *M = Caller->getParent();
 211  Intrinsic::ID IID = Intrinsic::memset;
 212  const Type *Tys[1];
 213  Tys[0] = Len->getType();
 214  Value *MemSet = Intrinsic::getDeclaration(M, IID, Tys, 1);
 215  Value *Align = ConstantInt::get(Type::getInt32Ty(*Context), 1);
 216  return B.CreateCall4(MemSet, CastToCStr(Dst, B), Val, Len, Align);
 217 }
 218
 219 /// EmitUnaryFloatFnCall - Emit a call to the unary function named 'Name' (e.g.
 220 /// 'floor').  This function is known to take a single of type matching 'Op' and
 221 /// returns one value with the same type.  If 'Op' is a long double, 'l' is
 222 /// added as the suffix of name, if 'Op' is a float, we add a 'f' suffix.
 223 Value *LibCallOptimization::EmitUnaryFloatFnCall(Value *Op, const char *Name,
 224                                                  IRBuilder<> &B) {
 225   char NameBuffer[20];
 226   if (Op->getType() != Type::getDoubleTy(*Context)) {
 227     // If we need to add a suffix, copy into NameBuffer.
 228     unsigned NameLen = strlen(Name);
 229     assert(NameLen < sizeof(NameBuffer)-2);
 230     memcpy(NameBuffer, Name, NameLen);
 231     if (Op->getType() == Type::getFloatTy(*Context))
 232       NameBuffer[NameLen] = 'f';  // floorf
 233     else
 234       NameBuffer[NameLen] = 'l';  // floorl
 235     NameBuffer[NameLen+1] = 0;
 236     Name = NameBuffer;
 237   }
 238
 239   Module *M = Caller->getParent();
 240   Value *Callee = M->getOrInsertFunction(Name, Op->getType(),
 241                                          Op->getType(), NULL);
 242   CallInst *CI = B.CreateCall(Callee, Op, Name);
 243
 244   if (const Function *F = dyn_cast<Function>(Callee->stripPointerCasts()))
 245     CI->setCallingConv(F->getCallingConv());
 246
 247   return CI;
 248 }
 249
 250 /// EmitPutChar - Emit a call to the putchar function.  This assumes that Char
 251 /// is an integer.
 252 void LibCallOptimization::EmitPutChar(Value *Char, IRBuilder<> &B) {
 253   Module *M = Caller->getParent();
 254   Value *PutChar = M->getOrInsertFunction("putchar", Type::getInt32Ty(*Context),
 255                                           Type::getInt32Ty(*Context), NULL);
 256   CallInst *CI = B.CreateCall(PutChar,
 257                               B.CreateIntCast(Char, Type::getInt32Ty(*Context), "chari"),
 258                               "putchar");
 259
 260   if (const Function *F = dyn_cast<Function>(PutChar->stripPointerCasts()))
 261     CI->setCallingConv(F->getCallingConv());
 262 }
 263
 264 /// EmitPutS - Emit a call to the puts function.  This assumes that Str is
 265 /// some pointer.
 266 void LibCallOptimization::EmitPutS(Value *Str, IRBuilder<> &B) {
 267   Module *M = Caller->getParent();
 268   AttributeWithIndex AWI[2];
 269   AWI[0] = AttributeWithIndex::get(1, Attribute::NoCapture);
 270   AWI[1] = AttributeWithIndex::get(~0u, Attribute::NoUnwind);
 271
 272   Value *PutS = M->getOrInsertFunction("puts", AttrListPtr::get(AWI, 2),
 273                                        Type::getInt32Ty(*Context),
 274                                     PointerType::getUnqual(Type::getInt8Ty(*Context)),
 275                                        NULL);
 276   CallInst *CI = B.CreateCall(PutS, CastToCStr(Str, B), "puts");
 277   if (const Function *F = dyn_cast<Function>(PutS->stripPointerCasts()))
 278     CI->setCallingConv(F->getCallingConv());
 279
 280 }
 281
 282 /// EmitFPutC - Emit a call to the fputc function.  This assumes that Char is
 283 /// an integer and File is a pointer to FILE.
 284 void LibCallOptimization::EmitFPutC(Value *Char, Value *File, IRBuilder<> &B) {
 285   Module *M = Caller->getParent();
 286   AttributeWithIndex AWI[2];
 287   AWI[0] = AttributeWithIndex::get(2, Attribute::NoCapture);
 288   AWI[1] = AttributeWithIndex::get(~0u, Attribute::NoUnwind);
 289   Constant *F;
 290   if (isa<PointerType>(File->getType()))
 291     F = M->getOrInsertFunction("fputc", AttrListPtr::get(AWI, 2), Type::getInt32Ty(*Context),
 292                                Type::getInt32Ty(*Context), File->getType(), NULL);
 293   else
 294     F = M->getOrInsertFunction("fputc", Type::getInt32Ty(*Context), Type::getInt32Ty(*Context),
 295                                File->getType(), NULL);
 296   Char = B.CreateIntCast(Char, Type::getInt32Ty(*Context), "chari");
 297   CallInst *CI = B.CreateCall2(F, Char, File, "fputc");
 298
 299   if (const Function *Fn = dyn_cast<Function>(F->stripPointerCasts()))
 300     CI->setCallingConv(Fn->getCallingConv());
 301 }
 302
 303 /// EmitFPutS - Emit a call to the puts function.  Str is required to be a
 304 /// pointer and File is a pointer to FILE.
 305 void LibCallOptimization::EmitFPutS(Value *Str, Value *File, IRBuilder<> &B) {
 306   Module *M = Caller->getParent();
 307   AttributeWithIndex AWI[3];
 308   AWI[0] = AttributeWithIndex::get(1, Attribute::NoCapture);
 309   AWI[1] = AttributeWithIndex::get(2, Attribute::NoCapture);
 310   AWI[2] = AttributeWithIndex::get(~0u, Attribute::NoUnwind);
 311   Constant *F;
 312   if (isa<PointerType>(File->getType()))
 313     F = M->getOrInsertFunction("fputs", AttrListPtr::get(AWI, 3), Type::getInt32Ty(*Context),
 314                                PointerType::getUnqual(Type::getInt8Ty(*Context)),
 315                                File->getType(), NULL);
 316   else
 317     F = M->getOrInsertFunction("fputs", Type::getInt32Ty(*Context),
 318                                PointerType::getUnqual(Type::getInt8Ty(*Context)),
 319                                File->getType(), NULL);
 320   CallInst *CI = B.CreateCall2(F, CastToCStr(Str, B), File, "fputs");
 321
 322   if (const Function *Fn = dyn_cast<Function>(F->stripPointerCasts()))
 323     CI->setCallingConv(Fn->getCallingConv());
 324 }
 325
 326 /// EmitFWrite - Emit a call to the fwrite function.  This assumes that Ptr is
 327 /// a pointer, Size is an 'intptr_t', and File is a pointer to FILE.
 328 void LibCallOptimization::EmitFWrite(Value *Ptr, Value *Size, Value *File,
 329                                      IRBuilder<> &B) {
 330   Module *M = Caller->getParent();
 331   AttributeWithIndex AWI[3];
 332   AWI[0] = AttributeWithIndex::get(1, Attribute::NoCapture);
 333   AWI[1] = AttributeWithIndex::get(4, Attribute::NoCapture);
 334   AWI[2] = AttributeWithIndex::get(~0u, Attribute::NoUnwind);
 335   Constant *F;
 336   if (isa<PointerType>(File->getType()))
 337     F = M->getOrInsertFunction("fwrite", AttrListPtr::get(AWI, 3),
 338                                TD->getIntPtrType(*Context),
 339                                PointerType::getUnqual(Type::getInt8Ty(*Context)),
 340                                TD->getIntPtrType(*Context), TD->getIntPtrType(*Context),
 341                                File->getType(), NULL);
 342   else
 343     F = M->getOrInsertFunction("fwrite", TD->getIntPtrType(*Context),
 344                                PointerType::getUnqual(Type::getInt8Ty(*Context)),
 345                                TD->getIntPtrType(*Context), TD->getIntPtrType(*Context),
 346                                File->getType(), NULL);
 347   CallInst *CI = B.CreateCall4(F, CastToCStr(Ptr, B), Size,
 348                         ConstantInt::get(TD->getIntPtrType(*Context), 1), File);
 349
 350   if (const Function *Fn = dyn_cast<Function>(F->stripPointerCasts()))
 351     CI->setCallingConv(Fn->getCallingConv());
 352 }
 353
 354 //===----------------------------------------------------------------------===//
 355 // Helper Functions
 356 //===----------------------------------------------------------------------===//
 357
 358 /// GetStringLengthH - If we can compute the length of the string pointed to by
 359 /// the specified pointer, return 'len+1'.  If we can't, return 0.
 360 static uint64_t GetStringLengthH(Value *V, SmallPtrSet<PHINode*, 32> &PHIs) {
 361   // Look through noop bitcast instructions.
 362   if (BitCastInst *BCI = dyn_cast<BitCastInst>(V))
 363     return GetStringLengthH(BCI->getOperand(0), PHIs);
 364
 365   // If this is a PHI node, there are two cases: either we have already seen it
 366   // or we haven't.
 367   if (PHINode *PN = dyn_cast<PHINode>(V)) {
 368     if (!PHIs.insert(PN))
 369       return ~0ULL;  // already in the set.
 370
 371     // If it was new, see if all the input strings are the same length.
 372     uint64_t LenSoFar = ~0ULL;
 373     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 374       uint64_t Len = GetStringLengthH(PN->getIncomingValue(i), PHIs);
 375       if (Len == 0) return 0; // Unknown length -> unknown.
 376
 377       if (Len == ~0ULL) continue;
 378
 379       if (Len != LenSoFar && LenSoFar != ~0ULL)
 380         return 0;    // Disagree -> unknown.
 381       LenSoFar = Len;
 382     }
 383
 384     // Success, all agree.
 385     return LenSoFar;
 386   }
 387
 388   // strlen(select(c,x,y)) -> strlen(x) ^ strlen(y)
 389   if (SelectInst *SI = dyn_cast<SelectInst>(V)) {
 390     uint64_t Len1 = GetStringLengthH(SI->getTrueValue(), PHIs);
 391     if (Len1 == 0) return 0;
 392     uint64_t Len2 = GetStringLengthH(SI->getFalseValue(), PHIs);
 393     if (Len2 == 0) return 0;
 394     if (Len1 == ~0ULL) return Len2;
 395     if (Len2 == ~0ULL) return Len1;
 396     if (Len1 != Len2) return 0;
 397     return Len1;
 398   }
 399
 400   // If the value is not a GEP instruction nor a constant expression with a
 401   // GEP instruction, then return unknown.
 402   User *GEP = 0;
 403   if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(V)) {
 404     GEP = GEPI;
 405   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
 406     if (CE->getOpcode() != Instruction::GetElementPtr)
 407       return 0;
 408     GEP = CE;
 409   } else {
 410     return 0;
 411   }
 412
 413   // Make sure the GEP has exactly three arguments.
 414   if (GEP->getNumOperands() != 3)
 415     return 0;
 416
 417   // Check to make sure that the first operand of the GEP is an integer and
 418   // has value 0 so that we are sure we're indexing into the initializer.
 419   if (ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(1))) {
 420     if (!Idx->isZero())
 421       return 0;
 422   } else
 423     return 0;
 424
 425   // If the second index isn't a ConstantInt, then this is a variable index
 426   // into the array.  If this occurs, we can't say anything meaningful about
 427   // the string.
 428   uint64_t StartIdx = 0;
 429   if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(2)))
 430     StartIdx = CI->getZExtValue();
 431   else
 432     return 0;
 433
 434   // The GEP instruction, constant or instruction, must reference a global
 435   // variable that is a constant and is initialized. The referenced constant
 436   // initializer is the array that we'll use for optimization.
 437   GlobalVariable* GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
 438   if (!GV || !GV->isConstant() || !GV->hasInitializer() ||
 439       GV->mayBeOverridden())
 440     return 0;
 441   Constant *GlobalInit = GV->getInitializer();
 442
 443   // Handle the ConstantAggregateZero case, which is a degenerate case. The
 444   // initializer is constant zero so the length of the string must be zero.
 445   if (isa<ConstantAggregateZero>(GlobalInit))
 446     return 1;  // Len = 0 offset by 1.
 447
 448   // Must be a Constant Array
 449   ConstantArray *Array = dyn_cast<ConstantArray>(GlobalInit);
 450   if (!Array ||
 451       Array->getType()->getElementType() != Type::getInt8Ty(V->getContext()))
 452     return false;
 453
 454   // Get the number of elements in the array
 455   uint64_t NumElts = Array->getType()->getNumElements();
 456
 457   // Traverse the constant array from StartIdx (derived above) which is
 458   // the place the GEP refers to in the array.
 459   for (unsigned i = StartIdx; i != NumElts; ++i) {
 460     Constant *Elt = Array->getOperand(i);
 461     ConstantInt *CI = dyn_cast<ConstantInt>(Elt);
 462     if (!CI) // This array isn't suitable, non-int initializer.
 463       return 0;
 464     if (CI->isZero())
 465       return i-StartIdx+1; // We found end of string, success!
 466   }
 467
 468   return 0; // The array isn't null terminated, conservatively return 'unknown'.
 469 }
 470
 471 /// GetStringLength - If we can compute the length of the string pointed to by
 472 /// the specified pointer, return 'len+1'.  If we can't, return 0.
 473 static uint64_t GetStringLength(Value *V) {
 474   if (!isa<PointerType>(V->getType())) return 0;
 475
 476   SmallPtrSet<PHINode*, 32> PHIs;
 477   uint64_t Len = GetStringLengthH(V, PHIs);
 478   // If Len is ~0ULL, we had an infinite phi cycle: this is dead code, so return
 479   // an empty string as a length.
 480   return Len == ~0ULL ? 1 : Len;
 481 }
 482
 483 /// IsOnlyUsedInZeroEqualityComparison - Return true if it only matters that the
 484 /// value is equal or not-equal to zero.
 485 static bool IsOnlyUsedInZeroEqualityComparison(Value *V) {
 486   for (Value::use_iterator UI = V->use_begin(), E = V->use_end();
 487        UI != E; ++UI) {
 488     if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI))
 489       if (IC->isEquality())
 490         if (Constant *C = dyn_cast<Constant>(IC->getOperand(1)))
 491           if (C->isNullValue())
 492             continue;
 493     // Unknown instruction.
 494     return false;
 495   }
 496   return true;
 497 }
 498
 499 //===----------------------------------------------------------------------===//
 500 // String and Memory LibCall Optimizations
 501 //===----------------------------------------------------------------------===//
 502
 503 //===---------------------------------------===//
 504 // 'strcat' Optimizations
 505 namespace {
 506 struct StrCatOpt : public LibCallOptimization {
 507   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 508     // Verify the "strcat" function prototype.
 509     const FunctionType *FT = Callee->getFunctionType();
 510     if (FT->getNumParams() != 2 ||
 511         FT->getReturnType() != PointerType::getUnqual(Type::getInt8Ty(*Context)) ||
 512         FT->getParamType(0) != FT->getReturnType() ||
 513         FT->getParamType(1) != FT->getReturnType())
 514       return 0;
 515
 516     // Extract some information from the instruction
 517     Value *Dst = CI->getOperand(1);
 518     Value *Src = CI->getOperand(2);
 519
 520     // See if we can get the length of the input string.
 521     uint64_t Len = GetStringLength(Src);
 522     if (Len == 0) return 0;
 523     --Len;  // Unbias length.
 524
 525     // Handle the simple, do-nothing case: strcat(x, "") -> x
 526     if (Len == 0)
 527       return Dst;
 528
 529     // These optimizations require TargetData.
 530     if (!TD) return 0;
 531
 532     EmitStrLenMemCpy(Src, Dst, Len, B);
 533     return Dst;
 534   }
 535
 536   void EmitStrLenMemCpy(Value *Src, Value *Dst, uint64_t Len, IRBuilder<> &B) {
 537     // We need to find the end of the destination string.  That's where the
 538     // memory is to be moved to. We just generate a call to strlen.
 539     Value *DstLen = EmitStrLen(Dst, B);
 540
 541     // Now that we have the destination's length, we must index into the
 542     // destination's pointer to get the actual memcpy destination (end of
 543     // the string .. we're concatenating).
 544     Value *CpyDst = B.CreateGEP(Dst, DstLen, "endptr");
 545
 546     // We have enough information to now generate the memcpy call to do the
 547     // concatenation for us.  Make a memcpy to copy the nul byte with align = 1.
 548     EmitMemCpy(CpyDst, Src,
 549                ConstantInt::get(TD->getIntPtrType(*Context), Len+1), 1, B);
 550   }
 551 };
 552
 553 //===---------------------------------------===//
 554 // 'strncat' Optimizations
 555
 556 struct StrNCatOpt : public StrCatOpt {
 557   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 558     // Verify the "strncat" function prototype.
 559     const FunctionType *FT = Callee->getFunctionType();
 560     if (FT->getNumParams() != 3 ||
 561         FT->getReturnType() != PointerType::getUnqual(Type::getInt8Ty(*Context)) ||
 562         FT->getParamType(0) != FT->getReturnType() ||
 563         FT->getParamType(1) != FT->getReturnType() ||
 564         !isa<IntegerType>(FT->getParamType(2)))
 565       return 0;
 566
 567     // Extract some information from the instruction
 568     Value *Dst = CI->getOperand(1);
 569     Value *Src = CI->getOperand(2);
 570     uint64_t Len;
 571
 572     // We don't do anything if length is not constant
 573     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getOperand(3)))
 574       Len = LengthArg->getZExtValue();
 575     else
 576       return 0;
 577
 578     // See if we can get the length of the input string.
 579     uint64_t SrcLen = GetStringLength(Src);
 580     if (SrcLen == 0) return 0;
 581     --SrcLen;  // Unbias length.
 582
 583     // Handle the simple, do-nothing cases:
 584     // strncat(x, "", c) -> x
 585     // strncat(x,  c, 0) -> x
 586     if (SrcLen == 0 || Len == 0) return Dst;
 587
 588     // These optimizations require TargetData.
 589     if (!TD) return 0;
 590
 591     // We don't optimize this case
 592     if (Len < SrcLen) return 0;
 593
 594     // strncat(x, s, c) -> strcat(x, s)
 595     // s is constant so the strcat can be optimized further
 596     EmitStrLenMemCpy(Src, Dst, SrcLen, B);
 597     return Dst;
 598   }
 599 };
 600
 601 //===---------------------------------------===//
 602 // 'strchr' Optimizations
 603
 604 struct StrChrOpt : public LibCallOptimization {
 605   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 606     // Verify the "strchr" function prototype.
 607     const FunctionType *FT = Callee->getFunctionType();
 608     if (FT->getNumParams() != 2 ||
 609         FT->getReturnType() != PointerType::getUnqual(Type::getInt8Ty(*Context)) ||
 610         FT->getParamType(0) != FT->getReturnType())
 611       return 0;
 612
 613     Value *SrcStr = CI->getOperand(1);
 614
 615     // If the second operand is non-constant, see if we can compute the length
 616     // of the input string and turn this into memchr.
 617     ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getOperand(2));
 618     if (CharC == 0) {
 619       // These optimizations require TargetData.
 620       if (!TD) return 0;
 621
 622       uint64_t Len = GetStringLength(SrcStr);
 623       if (Len == 0 || FT->getParamType(1) != Type::getInt32Ty(*Context)) // memchr needs i32.
 624         return 0;
 625
 626       return EmitMemChr(SrcStr, CI->getOperand(2), // include nul.
 627                         ConstantInt::get(TD->getIntPtrType(*Context), Len), B);
 628     }
 629
 630     // Otherwise, the character is a constant, see if the first argument is
 631     // a string literal.  If so, we can constant fold.
 632     std::string Str;
 633     if (!GetConstantStringInfo(SrcStr, Str))
 634       return 0;
 635
 636     // strchr can find the nul character.
 637     Str += '\0';
 638     char CharValue = CharC->getSExtValue();
 639
 640     // Compute the offset.
 641     uint64_t i = 0;
 642     while (1) {
 643       if (i == Str.size())    // Didn't find the char.  strchr returns null.
 644         return Constant::getNullValue(CI->getType());
 645       // Did we find our match?
 646       if (Str[i] == CharValue)
 647         break;
 648       ++i;
 649     }
 650
 651     // strchr(s+n,c)  -> gep(s+n+i,c)
 652     Value *Idx = ConstantInt::get(Type::getInt64Ty(*Context), i);
 653     return B.CreateGEP(SrcStr, Idx, "strchr");
 654   }
 655 };
 656
 657 //===---------------------------------------===//
 658 // 'strcmp' Optimizations
 659
 660 struct StrCmpOpt : public LibCallOptimization {
 661   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 662     // Verify the "strcmp" function prototype.
 663     const FunctionType *FT = Callee->getFunctionType();
 664     if (FT->getNumParams() != 2 || FT->getReturnType() != Type::getInt32Ty(*Context) ||
 665         FT->getParamType(0) != FT->getParamType(1) ||
 666         FT->getParamType(0) != PointerType::getUnqual(Type::getInt8Ty(*Context)))
 667       return 0;
 668
 669     Value *Str1P = CI->getOperand(1), *Str2P = CI->getOperand(2);
 670     if (Str1P == Str2P)      // strcmp(x,x)  -> 0
 671       return ConstantInt::get(CI->getType(), 0);
 672
 673     std::string Str1, Str2;
 674     bool HasStr1 = GetConstantStringInfo(Str1P, Str1);
 675     bool HasStr2 = GetConstantStringInfo(Str2P, Str2);
 676
 677     if (HasStr1 && Str1.empty()) // strcmp("", x) -> *x
 678       return B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"), CI->getType());
 679
 680     if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x
 681       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
 682
 683     // strcmp(x, y)  -> cnst  (if both x and y are constant strings)
 684     if (HasStr1 && HasStr2)
 685       return ConstantInt::get(CI->getType(),
 686                                      strcmp(Str1.c_str(),Str2.c_str()));
 687
 688     // strcmp(P, "x") -> memcmp(P, "x", 2)
 689     uint64_t Len1 = GetStringLength(Str1P);
 690     uint64_t Len2 = GetStringLength(Str2P);
 691     if (Len1 && Len2) {
 692       // These optimizations require TargetData.
 693       if (!TD) return 0;
 694
 695       return EmitMemCmp(Str1P, Str2P,
 696                         ConstantInt::get(TD->getIntPtrType(*Context),
 697                         std::min(Len1, Len2)), B);
 698     }
 699
 700     return 0;
 701   }
 702 };
 703
 704 //===---------------------------------------===//
 705 // 'strncmp' Optimizations
 706
 707 struct StrNCmpOpt : public LibCallOptimization {
 708   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 709     // Verify the "strncmp" function prototype.
 710     const FunctionType *FT = Callee->getFunctionType();
 711     if (FT->getNumParams() != 3 || FT->getReturnType() != Type::getInt32Ty(*Context) ||
 712         FT->getParamType(0) != FT->getParamType(1) ||
 713         FT->getParamType(0) != PointerType::getUnqual(Type::getInt8Ty(*Context)) ||
 714         !isa<IntegerType>(FT->getParamType(2)))
 715       return 0;
 716
 717     Value *Str1P = CI->getOperand(1), *Str2P = CI->getOperand(2);
 718     if (Str1P == Str2P)      // strncmp(x,x,n)  -> 0
 719       return ConstantInt::get(CI->getType(), 0);
 720
 721     // Get the length argument if it is constant.
 722     uint64_t Length;
 723     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getOperand(3)))
 724       Length = LengthArg->getZExtValue();
 725     else
 726       return 0;
 727
 728     if (Length == 0) // strncmp(x,y,0)   -> 0
 729       return ConstantInt::get(CI->getType(), 0);
 730
 731     std::string Str1, Str2;
 732     bool HasStr1 = GetConstantStringInfo(Str1P, Str1);
 733     bool HasStr2 = GetConstantStringInfo(Str2P, Str2);
 734
 735     if (HasStr1 && Str1.empty())  // strncmp("", x, n) -> *x
 736       return B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"), CI->getType());
 737
 738     if (HasStr2 && Str2.empty())  // strncmp(x, "", n) -> *x
 739       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
 740
 741     // strncmp(x, y)  -> cnst  (if both x and y are constant strings)
 742     if (HasStr1 && HasStr2)
 743       return ConstantInt::get(CI->getType(),
 744                               strncmp(Str1.c_str(), Str2.c_str(), Length));
 745     return 0;
 746   }
 747 };
 748
 749
 750 //===---------------------------------------===//
 751 // 'strcpy' Optimizations
 752
 753 struct StrCpyOpt : public LibCallOptimization {
 754   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 755     // Verify the "strcpy" function prototype.
 756     const FunctionType *FT = Callee->getFunctionType();
 757     if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) ||
 758         FT->getParamType(0) != FT->getParamType(1) ||
 759         FT->getParamType(0) != PointerType::getUnqual(Type::getInt8Ty(*Context)))
 760       return 0;
 761
 762     Value *Dst = CI->getOperand(1), *Src = CI->getOperand(2);
 763     if (Dst == Src)      // strcpy(x,x)  -> x
 764       return Src;
 765
 766     // These optimizations require TargetData.
 767     if (!TD) return 0;
 768
 769     // See if we can get the length of the input string.
 770     uint64_t Len = GetStringLength(Src);
 771     if (Len == 0) return 0;
 772
 773     // We have enough information to now generate the memcpy call to do the
 774     // concatenation for us.  Make a memcpy to copy the nul byte with align = 1.
 775     EmitMemCpy(Dst, Src,
 776                ConstantInt::get(TD->getIntPtrType(*Context), Len), 1, B);
 777     return Dst;
 778   }
 779 };
 780
 781 //===---------------------------------------===//
 782 // 'strncpy' Optimizations
 783
 784 struct StrNCpyOpt : public LibCallOptimization {
 785   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 786     const FunctionType *FT = Callee->getFunctionType();
 787     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 788         FT->getParamType(0) != FT->getParamType(1) ||
 789         FT->getParamType(0) != PointerType::getUnqual(Type::getInt8Ty(*Context)) ||
 790         !isa<IntegerType>(FT->getParamType(2)))
 791       return 0;
 792
 793     Value *Dst = CI->getOperand(1);
 794     Value *Src = CI->getOperand(2);
 795     Value *LenOp = CI->getOperand(3);
 796
 797     // See if we can get the length of the input string.
 798     uint64_t SrcLen = GetStringLength(Src);
 799     if (SrcLen == 0) return 0;
 800     --SrcLen;
 801
 802     if (SrcLen == 0) {
 803       // strncpy(x, "", y) -> memset(x, '\0', y, 1)
 804       EmitMemSet(Dst, ConstantInt::get(Type::getInt8Ty(*Context), '\0'), LenOp, B);
 805       return Dst;
 806     }
 807
 808     uint64_t Len;
 809     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(LenOp))
 810       Len = LengthArg->getZExtValue();
 811     else
 812       return 0;
 813
 814     if (Len == 0) return Dst; // strncpy(x, y, 0) -> x
 815
 816     // These optimizations require TargetData.
 817     if (!TD) return 0;
 818
 819     // Let strncpy handle the zero padding
 820     if (Len > SrcLen+1) return 0;
 821
 822     // strncpy(x, s, c) -> memcpy(x, s, c, 1) [s and c are constant]
 823     EmitMemCpy(Dst, Src,
 824                ConstantInt::get(TD->getIntPtrType(*Context), Len), 1, B);
 825
 826     return Dst;
 827   }
 828 };
 829
 830 //===---------------------------------------===//
 831 // 'strlen' Optimizations
 832
 833 struct StrLenOpt : public LibCallOptimization {
 834   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 835     const FunctionType *FT = Callee->getFunctionType();
 836     if (FT->getNumParams() != 1 ||
 837         FT->getParamType(0) != PointerType::getUnqual(Type::getInt8Ty(*Context)) ||
 838         !isa<IntegerType>(FT->getReturnType()))
 839       return 0;
 840
 841     Value *Src = CI->getOperand(1);
 842
 843     // Constant folding: strlen("xyz") -> 3
 844     if (uint64_t Len = GetStringLength(Src))
 845       return ConstantInt::get(CI->getType(), Len-1);
 846
 847     // Handle strlen(p) != 0.
 848     if (!IsOnlyUsedInZeroEqualityComparison(CI)) return 0;
 849
 850     // strlen(x) != 0 --> *x != 0
 851     // strlen(x) == 0 --> *x == 0
 852     return B.CreateZExt(B.CreateLoad(Src, "strlenfirst"), CI->getType());
 853   }
 854 };
 855
 856 //===---------------------------------------===//
 857 // 'strto*' Optimizations
 858
 859 struct StrToOpt : public LibCallOptimization {
 860   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 861     const FunctionType *FT = Callee->getFunctionType();
 862     if ((FT->getNumParams() != 2 && FT->getNumParams() != 3) ||
 863         !isa<PointerType>(FT->getParamType(0)) ||
 864         !isa<PointerType>(FT->getParamType(1)))
 865       return 0;
 866
 867     Value *EndPtr = CI->getOperand(2);
 868     if (isa<ConstantPointerNull>(EndPtr)) {
 869       CI->setOnlyReadsMemory();
 870       CI->addAttribute(1, Attribute::NoCapture);
 871     }
 872
 873     return 0;
 874   }
 875 };
 876
 877
 878 //===---------------------------------------===//
 879 // 'memcmp' Optimizations
 880
 881 struct MemCmpOpt : public LibCallOptimization {
 882   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 883     const FunctionType *FT = Callee->getFunctionType();
 884     if (FT->getNumParams() != 3 || !isa<PointerType>(FT->getParamType(0)) ||
 885         !isa<PointerType>(FT->getParamType(1)) ||
 886         FT->getReturnType() != Type::getInt32Ty(*Context))
 887       return 0;
 888
 889     Value *LHS = CI->getOperand(1), *RHS = CI->getOperand(2);
 890
 891     if (LHS == RHS)  // memcmp(s,s,x) -> 0
 892       return Constant::getNullValue(CI->getType());
 893
 894     // Make sure we have a constant length.
 895     ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getOperand(3));
 896     if (!LenC) return 0;
 897     uint64_t Len = LenC->getZExtValue();
 898
 899     if (Len == 0) // memcmp(s1,s2,0) -> 0
 900       return Constant::getNullValue(CI->getType());
 901
 902     if (Len == 1) { // memcmp(S1,S2,1) -> *LHS - *RHS
 903       Value *LHSV = B.CreateLoad(CastToCStr(LHS, B), "lhsv");
 904       Value *RHSV = B.CreateLoad(CastToCStr(RHS, B), "rhsv");
 905       return B.CreateSExt(B.CreateSub(LHSV, RHSV, "chardiff"), CI->getType());
 906     }
 907
 908     // memcmp(S1,S2,2) != 0 -> (*(short*)LHS ^ *(short*)RHS)  != 0
 909     // memcmp(S1,S2,4) != 0 -> (*(int*)LHS ^ *(int*)RHS)  != 0
 910     if ((Len == 2 || Len == 4) && IsOnlyUsedInZeroEqualityComparison(CI)) {
 911       const Type *PTy = PointerType::getUnqual(Len == 2 ?
 912                        Type::getInt16Ty(*Context) : Type::getInt32Ty(*Context));
 913       LHS = B.CreateBitCast(LHS, PTy, "tmp");
 914       RHS = B.CreateBitCast(RHS, PTy, "tmp");
 915       LoadInst *LHSV = B.CreateLoad(LHS, "lhsv");
 916       LoadInst *RHSV = B.CreateLoad(RHS, "rhsv");
 917       LHSV->setAlignment(1); RHSV->setAlignment(1);  // Unaligned loads.
 918       return B.CreateZExt(B.CreateXor(LHSV, RHSV, "shortdiff"), CI->getType());
 919     }
 920
 921     return 0;
 922   }
 923 };
 924
 925 //===---------------------------------------===//
 926 // 'memcpy' Optimizations
 927
 928 struct MemCpyOpt : public LibCallOptimization {
 929   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 930     // These optimizations require TargetData.
 931     if (!TD) return 0;
 932
 933     const FunctionType *FT = Callee->getFunctionType();
 934     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 935         !isa<PointerType>(FT->getParamType(0)) ||
 936         !isa<PointerType>(FT->getParamType(1)) ||
 937         FT->getParamType(2) != TD->getIntPtrType(*Context))
 938       return 0;
 939
 940     // memcpy(x, y, n) -> llvm.memcpy(x, y, n, 1)
 941     EmitMemCpy(CI->getOperand(1), CI->getOperand(2), CI->getOperand(3), 1, B);
 942     return CI->getOperand(1);
 943   }
 944 };
 945
 946 //===---------------------------------------===//
 947 // 'memmove' Optimizations
 948
 949 struct MemMoveOpt : public LibCallOptimization {
 950   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 951     // These optimizations require TargetData.
 952     if (!TD) return 0;
 953
 954     const FunctionType *FT = Callee->getFunctionType();
 955     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 956         !isa<PointerType>(FT->getParamType(0)) ||
 957         !isa<PointerType>(FT->getParamType(1)) ||
 958         FT->getParamType(2) != TD->getIntPtrType(*Context))
 959       return 0;
 960
 961     // memmove(x, y, n) -> llvm.memmove(x, y, n, 1)
 962     Module *M = Caller->getParent();
 963     Intrinsic::ID IID = Intrinsic::memmove;
 964     const Type *Tys[1];
 965     Tys[0] = TD->getIntPtrType(*Context);
 966     Value *MemMove = Intrinsic::getDeclaration(M, IID, Tys, 1);
 967     Value *Dst = CastToCStr(CI->getOperand(1), B);
 968     Value *Src = CastToCStr(CI->getOperand(2), B);
 969     Value *Size = CI->getOperand(3);
 970     Value *Align = ConstantInt::get(Type::getInt32Ty(*Context), 1);
 971     B.CreateCall4(MemMove, Dst, Src, Size, Align);
 972     return CI->getOperand(1);
 973   }
 974 };
 975
 976 //===---------------------------------------===//
 977 // 'memset' Optimizations
 978
 979 struct MemSetOpt : public LibCallOptimization {
 980   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 981     // These optimizations require TargetData.
 982     if (!TD) return 0;
 983
 984     const FunctionType *FT = Callee->getFunctionType();
 985     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 986         !isa<PointerType>(FT->getParamType(0)) ||
 987         !isa<IntegerType>(FT->getParamType(1)) ||
 988         FT->getParamType(2) != TD->getIntPtrType(*Context))
 989       return 0;
 990
 991     // memset(p, v, n) -> llvm.memset(p, v, n, 1)
 992     Value *Val = B.CreateIntCast(CI->getOperand(2), Type::getInt8Ty(*Context), false);
 993     EmitMemSet(CI->getOperand(1), Val,  CI->getOperand(3), B);
 994     return CI->getOperand(1);
 995   }
 996 };
 997
 998 //===----------------------------------------------------------------------===//
 999 // Math Library Optimizations
1000 //===----------------------------------------------------------------------===//
1001
1002 //===---------------------------------------===//
1003 // 'pow*' Optimizations
1004
1005 struct PowOpt : public LibCallOptimization {
1006   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1007     const FunctionType *FT = Callee->getFunctionType();
1008     // Just make sure this has 2 arguments of the same FP type, which match the
1009     // result type.
1010     if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) ||
1011         FT->getParamType(0) != FT->getParamType(1) ||
1012         !FT->getParamType(0)->isFloatingPoint())
1013       return 0;
1014
1015     Value *Op1 = CI->getOperand(1), *Op2 = CI->getOperand(2);
1016     if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) {
1017       if (Op1C->isExactlyValue(1.0))  // pow(1.0, x) -> 1.0
1018         return Op1C;
1019       if (Op1C->isExactlyValue(2.0))  // pow(2.0, x) -> exp2(x)
1020         return EmitUnaryFloatFnCall(Op2, "exp2", B);
1021     }
1022
1023     ConstantFP *Op2C = dyn_cast<ConstantFP>(Op2);
1024     if (Op2C == 0) return 0;
1025
1026     if (Op2C->getValueAPF().isZero())  // pow(x, 0.0) -> 1.0
1027       return ConstantFP::get(CI->getType(), 1.0);
1028
1029     if (Op2C->isExactlyValue(0.5)) {
1030       // FIXME: This is not safe for -0.0 and -inf.  This can only be done when
1031       // 'unsafe' math optimizations are allowed.
1032       // x    pow(x, 0.5)  sqrt(x)
1033       // ---------------------------------------------
1034       // -0.0    +0.0       -0.0
1035       // -inf    +inf       NaN
1036 #if 0
1037       // pow(x, 0.5) -> sqrt(x)
1038       return B.CreateCall(get_sqrt(), Op1, "sqrt");
1039 #endif
1040     }
1041
1042     if (Op2C->isExactlyValue(1.0))  // pow(x, 1.0) -> x
1043       return Op1;
1044     if (Op2C->isExactlyValue(2.0))  // pow(x, 2.0) -> x*x
1045       return B.CreateFMul(Op1, Op1, "pow2");
1046     if (Op2C->isExactlyValue(-1.0)) // pow(x, -1.0) -> 1.0/x
1047       return B.CreateFDiv(ConstantFP::get(CI->getType(), 1.0),
1048                           Op1, "powrecip");
1049     return 0;
1050   }
1051 };
1052
1053 //===---------------------------------------===//
1054 // 'exp2' Optimizations
1055
1056 struct Exp2Opt : public LibCallOptimization {
1057   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1058     const FunctionType *FT = Callee->getFunctionType();
1059     // Just make sure this has 1 argument of FP type, which matches the
1060     // result type.
1061     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1062         !FT->getParamType(0)->isFloatingPoint())
1063       return 0;
1064
1065     Value *Op = CI->getOperand(1);
1066     // Turn exp2(sitofp(x)) -> ldexp(1.0, sext(x))  if sizeof(x) <= 32
1067     // Turn exp2(uitofp(x)) -> ldexp(1.0, zext(x))  if sizeof(x) < 32
1068     Value *LdExpArg = 0;
1069     if (SIToFPInst *OpC = dyn_cast<SIToFPInst>(Op)) {
1070       if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() <= 32)
1071         LdExpArg = B.CreateSExt(OpC->getOperand(0), Type::getInt32Ty(*Context), "tmp");
1072     } else if (UIToFPInst *OpC = dyn_cast<UIToFPInst>(Op)) {
1073       if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() < 32)
1074         LdExpArg = B.CreateZExt(OpC->getOperand(0), Type::getInt32Ty(*Context), "tmp");
1075     }
1076
1077     if (LdExpArg) {
1078       const char *Name;
1079       if (Op->getType() == Type::getFloatTy(*Context))
1080         Name = "ldexpf";
1081       else if (Op->getType() == Type::getDoubleTy(*Context))
1082         Name = "ldexp";
1083       else
1084         Name = "ldexpl";
1085
1086       Constant *One = ConstantFP::get(*Context, APFloat(1.0f));
1087       if (Op->getType() != Type::getFloatTy(*Context))
1088         One = ConstantExpr::getFPExtend(One, Op->getType());
1089
1090       Module *M = Caller->getParent();
1091       Value *Callee = M->getOrInsertFunction(Name, Op->getType(),
1092                                              Op->getType(), Type::getInt32Ty(*Context),NULL);
1093       CallInst *CI = B.CreateCall2(Callee, One, LdExpArg);
1094       if (const Function *F = dyn_cast<Function>(Callee->stripPointerCasts()))
1095         CI->setCallingConv(F->getCallingConv());
1096
1097       return CI;
1098     }
1099     return 0;
1100   }
1101 };
1102
1103 //===---------------------------------------===//
1104 // Double -> Float Shrinking Optimizations for Unary Functions like 'floor'
1105
1106 struct UnaryDoubleFPOpt : public LibCallOptimization {
1107   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1108     const FunctionType *FT = Callee->getFunctionType();
1109     if (FT->getNumParams() != 1 || FT->getReturnType() != Type::getDoubleTy(*Context) ||
1110         FT->getParamType(0) != Type::getDoubleTy(*Context))
1111       return 0;
1112
1113     // If this is something like 'floor((double)floatval)', convert to floorf.
1114     FPExtInst *Cast = dyn_cast<FPExtInst>(CI->getOperand(1));
1115     if (Cast == 0 || Cast->getOperand(0)->getType() != Type::getFloatTy(*Context))
1116       return 0;
1117
1118     // floor((double)floatval) -> (double)floorf(floatval)
1119     Value *V = Cast->getOperand(0);
1120     V = EmitUnaryFloatFnCall(V, Callee->getName().data(), B);
1121     return B.CreateFPExt(V, Type::getDoubleTy(*Context));
1122   }
1123 };
1124
1125 //===----------------------------------------------------------------------===//
1126 // Integer Optimizations
1127 //===----------------------------------------------------------------------===//
1128
1129 //===---------------------------------------===//
1130 // 'ffs*' Optimizations
1131
1132 struct FFSOpt : public LibCallOptimization {
1133   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1134     const FunctionType *FT = Callee->getFunctionType();
1135     // Just make sure this has 2 arguments of the same FP type, which match the
1136     // result type.
1137     if (FT->getNumParams() != 1 || FT->getReturnType() != Type::getInt32Ty(*Context) ||
1138         !isa<IntegerType>(FT->getParamType(0)))
1139       return 0;
1140
1141     Value *Op = CI->getOperand(1);
1142
1143     // Constant fold.
1144     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op)) {
1145       if (CI->getValue() == 0)  // ffs(0) -> 0.
1146         return Constant::getNullValue(CI->getType());
1147       return ConstantInt::get(Type::getInt32Ty(*Context), // ffs(c) -> cttz(c)+1
1148                               CI->getValue().countTrailingZeros()+1);
1149     }
1150
1151     // ffs(x) -> x != 0 ? (i32)llvm.cttz(x)+1 : 0
1152     const Type *ArgType = Op->getType();
1153     Value *F = Intrinsic::getDeclaration(Callee->getParent(),
1154                                          Intrinsic::cttz, &ArgType, 1);
1155     Value *V = B.CreateCall(F, Op, "cttz");
1156     V = B.CreateAdd(V, ConstantInt::get(V->getType(), 1), "tmp");
1157     V = B.CreateIntCast(V, Type::getInt32Ty(*Context), false, "tmp");
1158
1159     Value *Cond = B.CreateICmpNE(Op, Constant::getNullValue(ArgType), "tmp");
1160     return B.CreateSelect(Cond, V, ConstantInt::get(Type::getInt32Ty(*Context), 0));
1161   }
1162 };
1163
1164 //===---------------------------------------===//
1165 // 'isdigit' Optimizations
1166
1167 struct IsDigitOpt : public LibCallOptimization {
1168   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1169     const FunctionType *FT = Callee->getFunctionType();
1170     // We require integer(i32)
1171     if (FT->getNumParams() != 1 || !isa<IntegerType>(FT->getReturnType()) ||
1172         FT->getParamType(0) != Type::getInt32Ty(*Context))
1173       return 0;
1174
1175     // isdigit(c) -> (c-'0') <u 10
1176     Value *Op = CI->getOperand(1);
1177     Op = B.CreateSub(Op, ConstantInt::get(Type::getInt32Ty(*Context), '0'),
1178                      "isdigittmp");
1179     Op = B.CreateICmpULT(Op, ConstantInt::get(Type::getInt32Ty(*Context), 10),
1180                          "isdigit");
1181     return B.CreateZExt(Op, CI->getType());
1182   }
1183 };
1184
1185 //===---------------------------------------===//
1186 // 'isascii' Optimizations
1187
1188 struct IsAsciiOpt : public LibCallOptimization {
1189   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1190     const FunctionType *FT = Callee->getFunctionType();
1191     // We require integer(i32)
1192     if (FT->getNumParams() != 1 || !isa<IntegerType>(FT->getReturnType()) ||
1193         FT->getParamType(0) != Type::getInt32Ty(*Context))
1194       return 0;
1195
1196     // isascii(c) -> c <u 128
1197     Value *Op = CI->getOperand(1);
1198     Op = B.CreateICmpULT(Op, ConstantInt::get(Type::getInt32Ty(*Context), 128),
1199                          "isascii");
1200     return B.CreateZExt(Op, CI->getType());
1201   }
1202 };
1203
1204 //===---------------------------------------===//
1205 // 'abs', 'labs', 'llabs' Optimizations
1206
1207 struct AbsOpt : public LibCallOptimization {
1208   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1209     const FunctionType *FT = Callee->getFunctionType();
1210     // We require integer(integer) where the types agree.
1211     if (FT->getNumParams() != 1 || !isa<IntegerType>(FT->getReturnType()) ||
1212         FT->getParamType(0) != FT->getReturnType())
1213       return 0;
1214
1215     // abs(x) -> x >s -1 ? x : -x
1216     Value *Op = CI->getOperand(1);
1217     Value *Pos = B.CreateICmpSGT(Op,
1218                              Constant::getAllOnesValue(Op->getType()),
1219                                  "ispos");
1220     Value *Neg = B.CreateNeg(Op, "neg");
1221     return B.CreateSelect(Pos, Op, Neg);
1222   }
1223 };
1224
1225
1226 //===---------------------------------------===//
1227 // 'toascii' Optimizations
1228
1229 struct ToAsciiOpt : public LibCallOptimization {
1230   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1231     const FunctionType *FT = Callee->getFunctionType();
1232     // We require i32(i32)
1233     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1234         FT->getParamType(0) != Type::getInt32Ty(*Context))
1235       return 0;
1236
1237     // isascii(c) -> c & 0x7f
1238     return B.CreateAnd(CI->getOperand(1),
1239                        ConstantInt::get(CI->getType(),0x7F));
1240   }
1241 };
1242
1243 //===----------------------------------------------------------------------===//
1244 // Formatting and IO Optimizations
1245 //===----------------------------------------------------------------------===//
1246
1247 //===---------------------------------------===//
1248 // 'printf' Optimizations
1249
1250 struct PrintFOpt : public LibCallOptimization {
1251   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1252     // Require one fixed pointer argument and an integer/void result.
1253     const FunctionType *FT = Callee->getFunctionType();
1254     if (FT->getNumParams() < 1 || !isa<PointerType>(FT->getParamType(0)) ||
1255         !(isa<IntegerType>(FT->getReturnType()) ||
1256           FT->getReturnType() == Type::getVoidTy(*Context)))
1257       return 0;
1258
1259     // Check for a fixed format string.
1260     std::string FormatStr;
1261     if (!GetConstantStringInfo(CI->getOperand(1), FormatStr))
1262       return 0;
1263
1264     // Empty format string -> noop.
1265     if (FormatStr.empty())  // Tolerate printf's declared void.
1266       return CI->use_empty() ? (Value*)CI :
1267                                ConstantInt::get(CI->getType(), 0);
1268
1269     // printf("x") -> putchar('x'), even for '%'.
1270     if (FormatStr.size() == 1) {
1271       EmitPutChar(ConstantInt::get(Type::getInt32Ty(*Context), FormatStr[0]), B);
1272       return CI->use_empty() ? (Value*)CI :
1273                                ConstantInt::get(CI->getType(), 1);
1274     }
1275
1276     // printf("foo\n") --> puts("foo")
1277     if (FormatStr[FormatStr.size()-1] == '\n' &&
1278         FormatStr.find('%') == std::string::npos) {  // no format characters.
1279       // Create a string literal with no \n on it.  We expect the constant merge
1280       // pass to be run after this pass, to merge duplicate strings.
1281       FormatStr.erase(FormatStr.end()-1);
1282       Constant *C = ConstantArray::get(*Context, FormatStr, true);
1283       C = new GlobalVariable(*Callee->getParent(), C->getType(), true,
1284                              GlobalVariable::InternalLinkage, C, "str");
1285       EmitPutS(C, B);
1286       return CI->use_empty() ? (Value*)CI :
1287                     ConstantInt::get(CI->getType(), FormatStr.size()+1);
1288     }
1289
1290     // Optimize specific format strings.
1291     // printf("%c", chr) --> putchar(*(i8*)dst)
1292     if (FormatStr == "%c" && CI->getNumOperands() > 2 &&
1293         isa<IntegerType>(CI->getOperand(2)->getType())) {
1294       EmitPutChar(CI->getOperand(2), B);
1295       return CI->use_empty() ? (Value*)CI :
1296                                ConstantInt::get(CI->getType(), 1);
1297     }
1298
1299     // printf("%s\n", str) --> puts(str)
1300     if (FormatStr == "%s\n" && CI->getNumOperands() > 2 &&
1301         isa<PointerType>(CI->getOperand(2)->getType()) &&
1302         CI->use_empty()) {
1303       EmitPutS(CI->getOperand(2), B);
1304       return CI;
1305     }
1306     return 0;
1307   }
1308 };
1309
1310 //===---------------------------------------===//
1311 // 'sprintf' Optimizations
1312
1313 struct SPrintFOpt : public LibCallOptimization {
1314   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1315     // Require two fixed pointer arguments and an integer result.
1316     const FunctionType *FT = Callee->getFunctionType();
1317     if (FT->getNumParams() != 2 || !isa<PointerType>(FT->getParamType(0)) ||
1318         !isa<PointerType>(FT->getParamType(1)) ||
1319         !isa<IntegerType>(FT->getReturnType()))
1320       return 0;
1321
1322     // Check for a fixed format string.
1323     std::string FormatStr;
1324     if (!GetConstantStringInfo(CI->getOperand(2), FormatStr))
1325       return 0;
1326
1327     // If we just have a format string (nothing else crazy) transform it.
1328     if (CI->getNumOperands() == 3) {
1329       // Make sure there's no % in the constant array.  We could try to handle
1330       // %% -> % in the future if we cared.
1331       for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1332         if (FormatStr[i] == '%')
1333           return 0; // we found a format specifier, bail out.
1334
1335       // These optimizations require TargetData.
1336       if (!TD) return 0;
1337
1338       // sprintf(str, fmt) -> llvm.memcpy(str, fmt, strlen(fmt)+1, 1)
1339       EmitMemCpy(CI->getOperand(1), CI->getOperand(2), // Copy the nul byte.
1340           ConstantInt::get(TD->getIntPtrType(*Context), FormatStr.size()+1),1,B);
1341       return ConstantInt::get(CI->getType(), FormatStr.size());
1342     }
1343
1344     // The remaining optimizations require the format string to be "%s" or "%c"
1345     // and have an extra operand.
1346     if (FormatStr.size() != 2 || FormatStr[0] != '%' || CI->getNumOperands() <4)
1347       return 0;
1348
1349     // Decode the second character of the format string.
1350     if (FormatStr[1] == 'c') {
1351       // sprintf(dst, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0
1352       if (!isa<IntegerType>(CI->getOperand(3)->getType())) return 0;
1353       Value *V = B.CreateTrunc(CI->getOperand(3), Type::getInt8Ty(*Context), "char");
1354       Value *Ptr = CastToCStr(CI->getOperand(1), B);
1355       B.CreateStore(V, Ptr);
1356       Ptr = B.CreateGEP(Ptr, ConstantInt::get(Type::getInt32Ty(*Context), 1), "nul");
1357       B.CreateStore(Constant::getNullValue(Type::getInt8Ty(*Context)), Ptr);
1358
1359       return ConstantInt::get(CI->getType(), 1);
1360     }
1361
1362     if (FormatStr[1] == 's') {
1363       // These optimizations require TargetData.
1364       if (!TD) return 0;
1365
1366       // sprintf(dest, "%s", str) -> llvm.memcpy(dest, str, strlen(str)+1, 1)
1367       if (!isa<PointerType>(CI->getOperand(3)->getType())) return 0;
1368
1369       Value *Len = EmitStrLen(CI->getOperand(3), B);
1370       Value *IncLen = B.CreateAdd(Len,
1371                                   ConstantInt::get(Len->getType(), 1),
1372                                   "leninc");
1373       EmitMemCpy(CI->getOperand(1), CI->getOperand(3), IncLen, 1, B);
1374
1375       // The sprintf result is the unincremented number of bytes in the string.
1376       return B.CreateIntCast(Len, CI->getType(), false);
1377     }
1378     return 0;
1379   }
1380 };
1381
1382 //===---------------------------------------===//
1383 // 'fwrite' Optimizations
1384
1385 struct FWriteOpt : public LibCallOptimization {
1386   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1387     // Require a pointer, an integer, an integer, a pointer, returning integer.
1388     const FunctionType *FT = Callee->getFunctionType();
1389     if (FT->getNumParams() != 4 || !isa<PointerType>(FT->getParamType(0)) ||
1390         !isa<IntegerType>(FT->getParamType(1)) ||
1391         !isa<IntegerType>(FT->getParamType(2)) ||
1392         !isa<PointerType>(FT->getParamType(3)) ||
1393         !isa<IntegerType>(FT->getReturnType()))
1394       return 0;
1395
1396     // Get the element size and count.
1397     ConstantInt *SizeC = dyn_cast<ConstantInt>(CI->getOperand(2));
1398     ConstantInt *CountC = dyn_cast<ConstantInt>(CI->getOperand(3));
1399     if (!SizeC || !CountC) return 0;
1400     uint64_t Bytes = SizeC->getZExtValue()*CountC->getZExtValue();
1401
1402     // If this is writing zero records, remove the call (it's a noop).
1403     if (Bytes == 0)
1404       return ConstantInt::get(CI->getType(), 0);
1405
1406     // If this is writing one byte, turn it into fputc.
1407     if (Bytes == 1) {  // fwrite(S,1,1,F) -> fputc(S[0],F)
1408       Value *Char = B.CreateLoad(CastToCStr(CI->getOperand(1), B), "char");
1409       EmitFPutC(Char, CI->getOperand(4), B);
1410       return ConstantInt::get(CI->getType(), 1);
1411     }
1412
1413     return 0;
1414   }
1415 };
1416
1417 //===---------------------------------------===//
1418 // 'fputs' Optimizations
1419
1420 struct FPutsOpt : public LibCallOptimization {
1421   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1422     // These optimizations require TargetData.
1423     if (!TD) return 0;
1424
1425     // Require two pointers.  Also, we can't optimize if return value is used.
1426     const FunctionType *FT = Callee->getFunctionType();
1427     if (FT->getNumParams() != 2 || !isa<PointerType>(FT->getParamType(0)) ||
1428         !isa<PointerType>(FT->getParamType(1)) ||
1429         !CI->use_empty())
1430       return 0;
1431
1432     // fputs(s,F) --> fwrite(s,1,strlen(s),F)
1433     uint64_t Len = GetStringLength(CI->getOperand(1));
1434     if (!Len) return 0;
1435     EmitFWrite(CI->getOperand(1),
1436                ConstantInt::get(TD->getIntPtrType(*Context), Len-1),
1437                CI->getOperand(2), B);
1438     return CI;  // Known to have no uses (see above).
1439   }
1440 };
1441
1442 //===---------------------------------------===//
1443 // 'fprintf' Optimizations
1444
1445 struct FPrintFOpt : public LibCallOptimization {
1446   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1447     // Require two fixed paramters as pointers and integer result.
1448     const FunctionType *FT = Callee->getFunctionType();
1449     if (FT->getNumParams() != 2 || !isa<PointerType>(FT->getParamType(0)) ||
1450         !isa<PointerType>(FT->getParamType(1)) ||
1451         !isa<IntegerType>(FT->getReturnType()))
1452       return 0;
1453
1454     // All the optimizations depend on the format string.
1455     std::string FormatStr;
1456     if (!GetConstantStringInfo(CI->getOperand(2), FormatStr))
1457       return 0;
1458
1459     // fprintf(F, "foo") --> fwrite("foo", 3, 1, F)
1460     if (CI->getNumOperands() == 3) {
1461       for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1462         if (FormatStr[i] == '%')  // Could handle %% -> % if we cared.
1463           return 0; // We found a format specifier.
1464
1465       // These optimizations require TargetData.
1466       if (!TD) return 0;
1467
1468       EmitFWrite(CI->getOperand(2), ConstantInt::get(TD->getIntPtrType(*Context),
1469                                                      FormatStr.size()),
1470                  CI->getOperand(1), B);
1471       return ConstantInt::get(CI->getType(), FormatStr.size());
1472     }
1473
1474     // The remaining optimizations require the format string to be "%s" or "%c"
1475     // and have an extra operand.
1476     if (FormatStr.size() != 2 || FormatStr[0] != '%' || CI->getNumOperands() <4)
1477       return 0;
1478
1479     // Decode the second character of the format string.
1480     if (FormatStr[1] == 'c') {
1481       // fprintf(F, "%c", chr) --> *(i8*)dst = chr
1482       if (!isa<IntegerType>(CI->getOperand(3)->getType())) return 0;
1483       EmitFPutC(CI->getOperand(3), CI->getOperand(1), B);
1484       return ConstantInt::get(CI->getType(), 1);
1485     }
1486
1487     if (FormatStr[1] == 's') {
1488       // fprintf(F, "%s", str) -> fputs(str, F)
1489       if (!isa<PointerType>(CI->getOperand(3)->getType()) || !CI->use_empty())
1490         return 0;
1491       EmitFPutS(CI->getOperand(3), CI->getOperand(1), B);
1492       return CI;
1493     }
1494     return 0;
1495   }
1496 };
1497
1498 } // end anonymous namespace.
1499
1500 //===----------------------------------------------------------------------===//
1501 // SimplifyLibCalls Pass Implementation
1502 //===----------------------------------------------------------------------===//
1503
1504 namespace {
1505   /// This pass optimizes well known library functions from libc and libm.
1506   ///
1507   class SimplifyLibCalls : public FunctionPass {
1508     StringMap<LibCallOptimization*> Optimizations;
1509     // String and Memory LibCall Optimizations
1510     StrCatOpt StrCat; StrNCatOpt StrNCat; StrChrOpt StrChr; StrCmpOpt StrCmp;
1511     StrNCmpOpt StrNCmp; StrCpyOpt StrCpy; StrNCpyOpt StrNCpy; StrLenOpt StrLen;
1512     StrToOpt StrTo; MemCmpOpt MemCmp; MemCpyOpt MemCpy; MemMoveOpt MemMove;
1513     MemSetOpt MemSet;
1514     // Math Library Optimizations
1515     PowOpt Pow; Exp2Opt Exp2; UnaryDoubleFPOpt UnaryDoubleFP;
1516     // Integer Optimizations
1517     FFSOpt FFS; AbsOpt Abs; IsDigitOpt IsDigit; IsAsciiOpt IsAscii;
1518     ToAsciiOpt ToAscii;
1519     // Formatting and IO Optimizations
1520     SPrintFOpt SPrintF; PrintFOpt PrintF;
1521     FWriteOpt FWrite; FPutsOpt FPuts; FPrintFOpt FPrintF;
1522
1523     bool Modified;  // This is only used by doInitialization.
1524   public:
1525     static char ID; // Pass identification
1526     SimplifyLibCalls() : FunctionPass(&ID) {}
1527
1528     void InitOptimizations();
1529     bool runOnFunction(Function &F);
1530
1531     void setDoesNotAccessMemory(Function &F);
1532     void setOnlyReadsMemory(Function &F);
1533     void setDoesNotThrow(Function &F);
1534     void setDoesNotCapture(Function &F, unsigned n);
1535     void setDoesNotAlias(Function &F, unsigned n);
1536     bool doInitialization(Module &M);
1537
1538     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1539     }
1540   };
1541   char SimplifyLibCalls::ID = 0;
1542 } // end anonymous namespace.
1543
1544 static RegisterPass<SimplifyLibCalls>
1545 X("simplify-libcalls", "Simplify well-known library calls");
1546
1547 // Public interface to the Simplify LibCalls pass.
1548 FunctionPass *llvm::createSimplifyLibCallsPass() {
1549   return new SimplifyLibCalls();
1550 }
1551
1552 /// Optimizations - Populate the Optimizations map with all the optimizations
1553 /// we know.
1554 void SimplifyLibCalls::InitOptimizations() {
1555   // String and Memory LibCall Optimizations
1556   Optimizations["strcat"] = &StrCat;
1557   Optimizations["strncat"] = &StrNCat;
1558   Optimizations["strchr"] = &StrChr;
1559   Optimizations["strcmp"] = &StrCmp;
1560   Optimizations["strncmp"] = &StrNCmp;
1561   Optimizations["strcpy"] = &StrCpy;
1562   Optimizations["strncpy"] = &StrNCpy;
1563   Optimizations["strlen"] = &StrLen;
1564   Optimizations["strtol"] = &StrTo;
1565   Optimizations["strtod"] = &StrTo;
1566   Optimizations["strtof"] = &StrTo;
1567   Optimizations["strtoul"] = &StrTo;
1568   Optimizations["strtoll"] = &StrTo;
1569   Optimizations["strtold"] = &StrTo;
1570   Optimizations["strtoull"] = &StrTo;
1571   Optimizations["memcmp"] = &MemCmp;
1572   Optimizations["memcpy"] = &MemCpy;
1573   Optimizations["memmove"] = &MemMove;
1574   Optimizations["memset"] = &MemSet;
1575
1576   // Math Library Optimizations
1577   Optimizations["powf"] = &Pow;
1578   Optimizations["pow"] = &Pow;
1579   Optimizations["powl"] = &Pow;
1580   Optimizations["llvm.pow.f32"] = &Pow;
1581   Optimizations["llvm.pow.f64"] = &Pow;
1582   Optimizations["llvm.pow.f80"] = &Pow;
1583   Optimizations["llvm.pow.f128"] = &Pow;
1584   Optimizations["llvm.pow.ppcf128"] = &Pow;
1585   Optimizations["exp2l"] = &Exp2;
1586   Optimizations["exp2"] = &Exp2;
1587   Optimizations["exp2f"] = &Exp2;
1588   Optimizations["llvm.exp2.ppcf128"] = &Exp2;
1589   Optimizations["llvm.exp2.f128"] = &Exp2;
1590   Optimizations["llvm.exp2.f80"] = &Exp2;
1591   Optimizations["llvm.exp2.f64"] = &Exp2;
1592   Optimizations["llvm.exp2.f32"] = &Exp2;
1593
1594 #ifdef HAVE_FLOORF
1595   Optimizations["floor"] = &UnaryDoubleFP;
1596 #endif
1597 #ifdef HAVE_CEILF
1598   Optimizations["ceil"] = &UnaryDoubleFP;
1599 #endif
1600 #ifdef HAVE_ROUNDF
1601   Optimizations["round"] = &UnaryDoubleFP;
1602 #endif
1603 #ifdef HAVE_RINTF
1604   Optimizations["rint"] = &UnaryDoubleFP;
1605 #endif
1606 #ifdef HAVE_NEARBYINTF
1607   Optimizations["nearbyint"] = &UnaryDoubleFP;
1608 #endif
1609
1610   // Integer Optimizations
1611   Optimizations["ffs"] = &FFS;
1612   Optimizations["ffsl"] = &FFS;
1613   Optimizations["ffsll"] = &FFS;
1614   Optimizations["abs"] = &Abs;
1615   Optimizations["labs"] = &Abs;
1616   Optimizations["llabs"] = &Abs;
1617   Optimizations["isdigit"] = &IsDigit;
1618   Optimizations["isascii"] = &IsAscii;
1619   Optimizations["toascii"] = &ToAscii;
1620
1621   // Formatting and IO Optimizations
1622   Optimizations["sprintf"] = &SPrintF;
1623   Optimizations["printf"] = &PrintF;
1624   Optimizations["fwrite"] = &FWrite;
1625   Optimizations["fputs"] = &FPuts;
1626   Optimizations["fprintf"] = &FPrintF;
1627 }
1628
1629
1630 /// runOnFunction - Top level algorithm.
1631 ///
1632 bool SimplifyLibCalls::runOnFunction(Function &F) {
1633   if (Optimizations.empty())
1634     InitOptimizations();
1635
1636   const TargetData *TD = getAnalysisIfAvailable<TargetData>();
1637
1638   IRBuilder<> Builder(F.getContext());
1639
1640   bool Changed = false;
1641   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
1642     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
1643       // Ignore non-calls.
1644       CallInst *CI = dyn_cast<CallInst>(I++);
1645       if (!CI) continue;
1646
1647       // Ignore indirect calls and calls to non-external functions.
1648       Function *Callee = CI->getCalledFunction();
1649       if (Callee == 0 || !Callee->isDeclaration() ||
1650           !(Callee->hasExternalLinkage() || Callee->hasDLLImportLinkage()))
1651         continue;
1652
1653       // Ignore unknown calls.
1654       LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
1655       if (!LCO) continue;
1656
1657       // Set the builder to the instruction after the call.
1658       Builder.SetInsertPoint(BB, I);
1659
1660       // Try to optimize this call.
1661       Value *Result = LCO->OptimizeCall(CI, TD, Builder);
1662       if (Result == 0) continue;
1663
1664       DEBUG(errs() << "SimplifyLibCalls simplified: " << *CI;
1665             errs() << "  into: " << *Result << "\n");
1666
1667       // Something changed!
1668       Changed = true;
1669       ++NumSimplified;
1670
1671       // Inspect the instruction after the call (which was potentially just
1672       // added) next.
1673       I = CI; ++I;
1674
1675       if (CI != Result && !CI->use_empty()) {
1676         CI->replaceAllUsesWith(Result);
1677         if (!Result->hasName())
1678           Result->takeName(CI);
1679       }
1680       CI->eraseFromParent();
1681     }
1682   }
1683   return Changed;
1684 }
1685
1686 // Utility methods for doInitialization.
1687
1688 void SimplifyLibCalls::setDoesNotAccessMemory(Function &F) {
1689   if (!F.doesNotAccessMemory()) {
1690     F.setDoesNotAccessMemory();
1691     ++NumAnnotated;
1692     Modified = true;
1693   }
1694 }
1695 void SimplifyLibCalls::setOnlyReadsMemory(Function &F) {
1696   if (!F.onlyReadsMemory()) {
1697     F.setOnlyReadsMemory();
1698     ++NumAnnotated;
1699     Modified = true;
1700   }
1701 }
1702 void SimplifyLibCalls::setDoesNotThrow(Function &F) {
1703   if (!F.doesNotThrow()) {
1704     F.setDoesNotThrow();
1705     ++NumAnnotated;
1706     Modified = true;
1707   }
1708 }
1709 void SimplifyLibCalls::setDoesNotCapture(Function &F, unsigned n) {
1710   if (!F.doesNotCapture(n)) {
1711     F.setDoesNotCapture(n);
1712     ++NumAnnotated;
1713     Modified = true;
1714   }
1715 }
1716 void SimplifyLibCalls::setDoesNotAlias(Function &F, unsigned n) {
1717   if (!F.doesNotAlias(n)) {
1718     F.setDoesNotAlias(n);
1719     ++NumAnnotated;
1720     Modified = true;
1721   }
1722 }
1723
1724 /// doInitialization - Add attributes to well-known functions.
1725 ///
1726 bool SimplifyLibCalls::doInitialization(Module &M) {
1727   Modified = false;
1728   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
1729     Function &F = *I;
1730     if (!F.isDeclaration())
1731       continue;
1732
1733     if (!F.hasName())
1734       continue;
1735
1736     const FunctionType *FTy = F.getFunctionType();
1737
1738     StringRef Name = F.getName();
1739     switch (Name[0]) {
1740       case 's':
1741         if (Name == "strlen") {
1742           if (FTy->getNumParams() != 1 ||
1743               !isa<PointerType>(FTy->getParamType(0)))
1744             continue;
1745           setOnlyReadsMemory(F);
1746           setDoesNotThrow(F);
1747           setDoesNotCapture(F, 1);
1748         } else if (Name == "strcpy" ||
1749                    Name == "stpcpy" ||
1750                    Name == "strcat" ||
1751                    Name == "strtol" ||
1752                    Name == "strtod" ||
1753                    Name == "strtof" ||
1754                    Name == "strtoul" ||
1755                    Name == "strtoll" ||
1756                    Name == "strtold" ||
1757                    Name == "strncat" ||
1758                    Name == "strncpy" ||
1759                    Name == "strtoull") {
1760           if (FTy->getNumParams() < 2 ||
1761               !isa<PointerType>(FTy->getParamType(1)))
1762             continue;
1763           setDoesNotThrow(F);
1764           setDoesNotCapture(F, 2);
1765         } else if (Name == "strxfrm") {
1766           if (FTy->getNumParams() != 3 ||
1767               !isa<PointerType>(FTy->getParamType(0)) ||
1768               !isa<PointerType>(FTy->getParamType(1)))
1769             continue;
1770           setDoesNotThrow(F);
1771           setDoesNotCapture(F, 1);
1772           setDoesNotCapture(F, 2);
1773         } else if (Name == "strcmp" ||
1774                    Name == "strspn" ||
1775                    Name == "strncmp" ||
1776                    Name ==" strcspn" ||
1777                    Name == "strcoll" ||
1778                    Name == "strcasecmp" ||
1779                    Name == "strncasecmp") {
1780           if (FTy->getNumParams() < 2 ||
1781               !isa<PointerType>(FTy->getParamType(0)) ||
1782               !isa<PointerType>(FTy->getParamType(1)))
1783             continue;
1784           setOnlyReadsMemory(F);
1785           setDoesNotThrow(F);
1786           setDoesNotCapture(F, 1);
1787           setDoesNotCapture(F, 2);
1788         } else if (Name == "strstr" ||
1789                    Name == "strpbrk") {
1790           if (FTy->getNumParams() != 2 ||
1791               !isa<PointerType>(FTy->getParamType(1)))
1792             continue;
1793           setOnlyReadsMemory(F);
1794           setDoesNotThrow(F);
1795           setDoesNotCapture(F, 2);
1796         } else if (Name == "strtok" ||
1797                    Name == "strtok_r") {
1798           if (FTy->getNumParams() < 2 ||
1799               !isa<PointerType>(FTy->getParamType(1)))
1800             continue;
1801           setDoesNotThrow(F);
1802           setDoesNotCapture(F, 2);
1803         } else if (Name == "scanf" ||
1804                    Name == "setbuf" ||
1805                    Name == "setvbuf") {
1806           if (FTy->getNumParams() < 1 ||
1807               !isa<PointerType>(FTy->getParamType(0)))
1808             continue;
1809           setDoesNotThrow(F);
1810           setDoesNotCapture(F, 1);
1811         } else if (Name == "strdup" ||
1812                    Name == "strndup") {
1813           if (FTy->getNumParams() < 1 ||
1814               !isa<PointerType>(FTy->getReturnType()) ||
1815               !isa<PointerType>(FTy->getParamType(0)))
1816             continue;
1817           setDoesNotThrow(F);
1818           setDoesNotAlias(F, 0);
1819           setDoesNotCapture(F, 1);
1820         } else if (Name == "stat" ||
1821                    Name == "sscanf" ||
1822                    Name == "sprintf" ||
1823                    Name == "statvfs") {
1824           if (FTy->getNumParams() < 2 ||
1825               !isa<PointerType>(FTy->getParamType(0)) ||
1826               !isa<PointerType>(FTy->getParamType(1)))
1827             continue;
1828           setDoesNotThrow(F);
1829           setDoesNotCapture(F, 1);
1830           setDoesNotCapture(F, 2);
1831         } else if (Name == "snprintf") {
1832           if (FTy->getNumParams() != 3 ||
1833               !isa<PointerType>(FTy->getParamType(0)) ||
1834               !isa<PointerType>(FTy->getParamType(2)))
1835             continue;
1836           setDoesNotThrow(F);
1837           setDoesNotCapture(F, 1);
1838           setDoesNotCapture(F, 3);
1839         } else if (Name == "setitimer") {
1840           if (FTy->getNumParams() != 3 ||
1841               !isa<PointerType>(FTy->getParamType(1)) ||
1842               !isa<PointerType>(FTy->getParamType(2)))
1843             continue;
1844           setDoesNotThrow(F);
1845           setDoesNotCapture(F, 2);
1846           setDoesNotCapture(F, 3);
1847         } else if (Name == "system") {
1848           if (FTy->getNumParams() != 1 ||
1849               !isa<PointerType>(FTy->getParamType(0)))
1850             continue;
1851           // May throw; "system" is a valid pthread cancellation point.
1852           setDoesNotCapture(F, 1);
1853         }
1854         break;
1855       case 'm':
1856         if (Name == "memcmp") {
1857           if (FTy->getNumParams() != 3 ||
1858               !isa<PointerType>(FTy->getParamType(0)) ||
1859               !isa<PointerType>(FTy->getParamType(1)))
1860             continue;
1861           setOnlyReadsMemory(F);
1862           setDoesNotThrow(F);
1863           setDoesNotCapture(F, 1);
1864           setDoesNotCapture(F, 2);
1865         } else if (Name == "memchr" ||
1866                    Name == "memrchr") {
1867           if (FTy->getNumParams() != 3)
1868             continue;
1869           setOnlyReadsMemory(F);
1870           setDoesNotThrow(F);
1871         } else if (Name == "modf" ||
1872                    Name == "modff" ||
1873                    Name == "modfl" ||
1874                    Name == "memcpy" ||
1875                    Name == "memccpy" ||
1876                    Name == "memmove") {
1877           if (FTy->getNumParams() < 2 ||
1878               !isa<PointerType>(FTy->getParamType(1)))
1879             continue;
1880           setDoesNotThrow(F);
1881           setDoesNotCapture(F, 2);
1882         } else if (Name == "memalign") {
1883           if (!isa<PointerType>(FTy->getReturnType()))
1884             continue;
1885           setDoesNotAlias(F, 0);
1886         } else if (Name == "mkdir" ||
1887                    Name == "mktime") {
1888           if (FTy->getNumParams() == 0 ||
1889               !isa<PointerType>(FTy->getParamType(0)))
1890             continue;
1891           setDoesNotThrow(F);
1892           setDoesNotCapture(F, 1);
1893         }
1894         break;
1895       case 'r':
1896         if (Name == "realloc") {
1897           if (FTy->getNumParams() != 2 ||
1898               !isa<PointerType>(FTy->getParamType(0)) ||
1899               !isa<PointerType>(FTy->getReturnType()))
1900             continue;
1901           setDoesNotThrow(F);
1902           setDoesNotAlias(F, 0);
1903           setDoesNotCapture(F, 1);
1904         } else if (Name == "read") {
1905           if (FTy->getNumParams() != 3 ||
1906               !isa<PointerType>(FTy->getParamType(1)))
1907             continue;
1908           // May throw; "read" is a valid pthread cancellation point.
1909           setDoesNotCapture(F, 2);
1910         } else if (Name == "rmdir" ||
1911                    Name == "rewind" ||
1912                    Name == "remove" ||
1913                    Name == "realpath") {
1914           if (FTy->getNumParams() < 1 ||
1915               !isa<PointerType>(FTy->getParamType(0)))
1916             continue;
1917           setDoesNotThrow(F);
1918           setDoesNotCapture(F, 1);
1919         } else if (Name == "rename" ||
1920                    Name == "readlink") {
1921           if (FTy->getNumParams() < 2 ||
1922               !isa<PointerType>(FTy->getParamType(0)) ||
1923               !isa<PointerType>(FTy->getParamType(1)))
1924             continue;
1925           setDoesNotThrow(F);
1926           setDoesNotCapture(F, 1);
1927           setDoesNotCapture(F, 2);
1928         }
1929         break;
1930       case 'w':
1931         if (Name == "write") {
1932           if (FTy->getNumParams() != 3 ||
1933               !isa<PointerType>(FTy->getParamType(1)))
1934             continue;
1935           // May throw; "write" is a valid pthread cancellation point.
1936           setDoesNotCapture(F, 2);
1937         }
1938         break;
1939       case 'b':
1940         if (Name == "bcopy") {
1941           if (FTy->getNumParams() != 3 ||
1942               !isa<PointerType>(FTy->getParamType(0)) ||
1943               !isa<PointerType>(FTy->getParamType(1)))
1944             continue;
1945           setDoesNotThrow(F);
1946           setDoesNotCapture(F, 1);
1947           setDoesNotCapture(F, 2);
1948         } else if (Name == "bcmp") {
1949           if (FTy->getNumParams() != 3 ||
1950               !isa<PointerType>(FTy->getParamType(0)) ||
1951               !isa<PointerType>(FTy->getParamType(1)))
1952             continue;
1953           setDoesNotThrow(F);
1954           setOnlyReadsMemory(F);
1955           setDoesNotCapture(F, 1);
1956           setDoesNotCapture(F, 2);
1957         } else if (Name == "bzero") {
1958           if (FTy->getNumParams() != 2 ||
1959               !isa<PointerType>(FTy->getParamType(0)))
1960             continue;
1961           setDoesNotThrow(F);
1962           setDoesNotCapture(F, 1);
1963         }
1964         break;
1965       case 'c':
1966         if (Name == "calloc") {
1967           if (FTy->getNumParams() != 2 ||
1968               !isa<PointerType>(FTy->getReturnType()))
1969             continue;
1970           setDoesNotThrow(F);
1971           setDoesNotAlias(F, 0);
1972         } else if (Name == "chmod" ||
1973                    Name == "chown" ||
1974                    Name == "ctermid" ||
1975                    Name == "clearerr" ||
1976                    Name == "closedir") {
1977           if (FTy->getNumParams() == 0 ||
1978               !isa<PointerType>(FTy->getParamType(0)))
1979             continue;
1980           setDoesNotThrow(F);
1981           setDoesNotCapture(F, 1);
1982         }
1983         break;
1984       case 'a':
1985         if (Name == "atoi" ||
1986             Name == "atol" ||
1987             Name == "atof" ||
1988             Name == "atoll") {
1989           if (FTy->getNumParams() != 1 ||
1990               !isa<PointerType>(FTy->getParamType(0)))
1991             continue;
1992           setDoesNotThrow(F);
1993           setOnlyReadsMemory(F);
1994           setDoesNotCapture(F, 1);
1995         } else if (Name == "access") {
1996           if (FTy->getNumParams() != 2 ||
1997               !isa<PointerType>(FTy->getParamType(0)))
1998             continue;
1999           setDoesNotThrow(F);
2000           setDoesNotCapture(F, 1);
2001         }
2002         break;
2003       case 'f':
2004         if (Name == "fopen") {
2005           if (FTy->getNumParams() != 2 ||
2006               !isa<PointerType>(FTy->getReturnType()) ||
2007               !isa<PointerType>(FTy->getParamType(0)) ||
2008               !isa<PointerType>(FTy->getParamType(1)))
2009             continue;
2010           setDoesNotThrow(F);
2011           setDoesNotAlias(F, 0);
2012           setDoesNotCapture(F, 1);
2013           setDoesNotCapture(F, 2);
2014         } else if (Name == "fdopen") {
2015           if (FTy->getNumParams() != 2 ||
2016               !isa<PointerType>(FTy->getReturnType()) ||
2017               !isa<PointerType>(FTy->getParamType(1)))
2018             continue;
2019           setDoesNotThrow(F);
2020           setDoesNotAlias(F, 0);
2021           setDoesNotCapture(F, 2);
2022         } else if (Name == "feof" ||
2023                    Name == "free" ||
2024                    Name == "fseek" ||
2025                    Name == "ftell" ||
2026                    Name == "fgetc" ||
2027                    Name == "fseeko" ||
2028                    Name == "ftello" ||
2029                    Name == "fileno" ||
2030                    Name == "fflush" ||
2031                    Name == "fclose" ||
2032                    Name == "fsetpos" ||
2033                    Name == "flockfile" ||
2034                    Name == "funlockfile" ||
2035                    Name == "ftrylockfile") {
2036           if (FTy->getNumParams() == 0 ||
2037               !isa<PointerType>(FTy->getParamType(0)))
2038             continue;
2039           setDoesNotThrow(F);
2040           setDoesNotCapture(F, 1);
2041         } else if (Name == "ferror") {
2042           if (FTy->getNumParams() != 1 ||
2043               !isa<PointerType>(FTy->getParamType(0)))
2044             continue;
2045           setDoesNotThrow(F);
2046           setDoesNotCapture(F, 1);
2047           setOnlyReadsMemory(F);
2048         } else if (Name == "fputc" ||
2049                    Name == "fstat" ||
2050                    Name == "frexp" ||
2051                    Name == "frexpf" ||
2052                    Name == "frexpl" ||
2053                    Name == "fstatvfs") {
2054           if (FTy->getNumParams() != 2 ||
2055               !isa<PointerType>(FTy->getParamType(1)))
2056             continue;
2057           setDoesNotThrow(F);
2058           setDoesNotCapture(F, 2);
2059         } else if (Name == "fgets") {
2060           if (FTy->getNumParams() != 3 ||
2061               !isa<PointerType>(FTy->getParamType(0)) ||
2062               !isa<PointerType>(FTy->getParamType(2)))
2063             continue;
2064           setDoesNotThrow(F);
2065           setDoesNotCapture(F, 3);
2066         } else if (Name == "fread" ||
2067                    Name == "fwrite") {
2068           if (FTy->getNumParams() != 4 ||
2069               !isa<PointerType>(FTy->getParamType(0)) ||
2070               !isa<PointerType>(FTy->getParamType(3)))
2071             continue;
2072           setDoesNotThrow(F);
2073           setDoesNotCapture(F, 1);
2074           setDoesNotCapture(F, 4);
2075         } else if (Name == "fputs" ||
2076                    Name == "fscanf" ||
2077                    Name == "fprintf" ||
2078                    Name == "fgetpos") {
2079           if (FTy->getNumParams() < 2 ||
2080               !isa<PointerType>(FTy->getParamType(0)) ||
2081               !isa<PointerType>(FTy->getParamType(1)))
2082             continue;
2083           setDoesNotThrow(F);
2084           setDoesNotCapture(F, 1);
2085           setDoesNotCapture(F, 2);
2086         }
2087         break;
2088       case 'g':
2089         if (Name == "getc" ||
2090             Name == "getlogin_r" ||
2091             Name == "getc_unlocked") {
2092           if (FTy->getNumParams() == 0 ||
2093               !isa<PointerType>(FTy->getParamType(0)))
2094             continue;
2095           setDoesNotThrow(F);
2096           setDoesNotCapture(F, 1);
2097         } else if (Name == "getenv") {
2098           if (FTy->getNumParams() != 1 ||
2099               !isa<PointerType>(FTy->getParamType(0)))
2100             continue;
2101           setDoesNotThrow(F);
2102           setOnlyReadsMemory(F);
2103           setDoesNotCapture(F, 1);
2104         } else if (Name == "gets" ||
2105                    Name == "getchar") {
2106           setDoesNotThrow(F);
2107         } else if (Name == "getitimer") {
2108           if (FTy->getNumParams() != 2 ||
2109               !isa<PointerType>(FTy->getParamType(1)))
2110             continue;
2111           setDoesNotThrow(F);
2112           setDoesNotCapture(F, 2);
2113         } else if (Name == "getpwnam") {
2114           if (FTy->getNumParams() != 1 ||
2115               !isa<PointerType>(FTy->getParamType(0)))
2116             continue;
2117           setDoesNotThrow(F);
2118           setDoesNotCapture(F, 1);
2119         }
2120         break;
2121       case 'u':
2122         if (Name == "ungetc") {
2123           if (FTy->getNumParams() != 2 ||
2124               !isa<PointerType>(FTy->getParamType(1)))
2125             continue;
2126           setDoesNotThrow(F);
2127           setDoesNotCapture(F, 2);
2128         } else if (Name == "uname" ||
2129                    Name == "unlink" ||
2130                    Name == "unsetenv") {
2131           if (FTy->getNumParams() != 1 ||
2132               !isa<PointerType>(FTy->getParamType(0)))
2133             continue;
2134           setDoesNotThrow(F);
2135           setDoesNotCapture(F, 1);
2136         } else if (Name == "utime" ||
2137                    Name == "utimes") {
2138           if (FTy->getNumParams() != 2 ||
2139               !isa<PointerType>(FTy->getParamType(0)) ||
2140               !isa<PointerType>(FTy->getParamType(1)))
2141             continue;
2142           setDoesNotThrow(F);
2143           setDoesNotCapture(F, 1);
2144           setDoesNotCapture(F, 2);
2145         }
2146         break;
2147       case 'p':
2148         if (Name == "putc") {
2149           if (FTy->getNumParams() != 2 ||
2150               !isa<PointerType>(FTy->getParamType(1)))
2151             continue;
2152           setDoesNotThrow(F);
2153           setDoesNotCapture(F, 2);
2154         } else if (Name == "puts" ||
2155                    Name == "printf" ||
2156                    Name == "perror") {
2157           if (FTy->getNumParams() != 1 ||
2158               !isa<PointerType>(FTy->getParamType(0)))
2159             continue;
2160           setDoesNotThrow(F);
2161           setDoesNotCapture(F, 1);
2162         } else if (Name == "pread" ||
2163                    Name == "pwrite") {
2164           if (FTy->getNumParams() != 4 ||
2165               !isa<PointerType>(FTy->getParamType(1)))
2166             continue;
2167           // May throw; these are valid pthread cancellation points.
2168           setDoesNotCapture(F, 2);
2169         } else if (Name == "putchar") {
2170           setDoesNotThrow(F);
2171         } else if (Name == "popen") {
2172           if (FTy->getNumParams() != 2 ||
2173               !isa<PointerType>(FTy->getReturnType()) ||
2174               !isa<PointerType>(FTy->getParamType(0)) ||
2175               !isa<PointerType>(FTy->getParamType(1)))
2176             continue;
2177           setDoesNotThrow(F);
2178           setDoesNotAlias(F, 0);
2179           setDoesNotCapture(F, 1);
2180           setDoesNotCapture(F, 2);
2181         } else if (Name == "pclose") {
2182           if (FTy->getNumParams() != 1 ||
2183               !isa<PointerType>(FTy->getParamType(0)))
2184             continue;
2185           setDoesNotThrow(F);
2186           setDoesNotCapture(F, 1);
2187         }
2188         break;
2189       case 'v':
2190         if (Name == "vscanf") {
2191           if (FTy->getNumParams() != 2 ||
2192               !isa<PointerType>(FTy->getParamType(1)))
2193             continue;
2194           setDoesNotThrow(F);
2195           setDoesNotCapture(F, 1);
2196         } else if (Name == "vsscanf" ||
2197                    Name == "vfscanf") {
2198           if (FTy->getNumParams() != 3 ||
2199               !isa<PointerType>(FTy->getParamType(1)) ||
2200               !isa<PointerType>(FTy->getParamType(2)))
2201             continue;
2202           setDoesNotThrow(F);
2203           setDoesNotCapture(F, 1);
2204           setDoesNotCapture(F, 2);
2205         } else if (Name == "valloc") {
2206           if (!isa<PointerType>(FTy->getReturnType()))
2207             continue;
2208           setDoesNotThrow(F);
2209           setDoesNotAlias(F, 0);
2210         } else if (Name == "vprintf") {
2211           if (FTy->getNumParams() != 2 ||
2212               !isa<PointerType>(FTy->getParamType(0)))
2213             continue;
2214           setDoesNotThrow(F);
2215           setDoesNotCapture(F, 1);
2216         } else if (Name == "vfprintf" ||
2217                    Name == "vsprintf") {
2218           if (FTy->getNumParams() != 3 ||
2219               !isa<PointerType>(FTy->getParamType(0)) ||
2220               !isa<PointerType>(FTy->getParamType(1)))
2221             continue;
2222           setDoesNotThrow(F);
2223           setDoesNotCapture(F, 1);
2224           setDoesNotCapture(F, 2);
2225         } else if (Name == "vsnprintf") {
2226           if (FTy->getNumParams() != 4 ||
2227               !isa<PointerType>(FTy->getParamType(0)) ||
2228               !isa<PointerType>(FTy->getParamType(2)))
2229             continue;
2230           setDoesNotThrow(F);
2231           setDoesNotCapture(F, 1);
2232           setDoesNotCapture(F, 3);
2233         }
2234         break;
2235       case 'o':
2236         if (Name == "open") {
2237           if (FTy->getNumParams() < 2 ||
2238               !isa<PointerType>(FTy->getParamType(0)))
2239             continue;
2240           // May throw; "open" is a valid pthread cancellation point.
2241           setDoesNotCapture(F, 1);
2242         } else if (Name == "opendir") {
2243           if (FTy->getNumParams() != 1 ||
2244               !isa<PointerType>(FTy->getReturnType()) ||
2245               !isa<PointerType>(FTy->getParamType(0)))
2246             continue;
2247           setDoesNotThrow(F);
2248           setDoesNotAlias(F, 0);
2249           setDoesNotCapture(F, 1);
2250         }
2251         break;
2252       case 't':
2253         if (Name == "tmpfile") {
2254           if (!isa<PointerType>(FTy->getReturnType()))
2255             continue;
2256           setDoesNotThrow(F);
2257           setDoesNotAlias(F, 0);
2258         } else if (Name == "times") {
2259           if (FTy->getNumParams() != 1 ||
2260               !isa<PointerType>(FTy->getParamType(0)))
2261             continue;
2262           setDoesNotThrow(F);
2263           setDoesNotCapture(F, 1);
2264         }
2265         break;
2266       case 'h':
2267         if (Name == "htonl" ||
2268             Name == "htons") {
2269           setDoesNotThrow(F);
2270           setDoesNotAccessMemory(F);
2271         }
2272         break;
2273       case 'n':
2274         if (Name == "ntohl" ||
2275             Name == "ntohs") {
2276           setDoesNotThrow(F);
2277           setDoesNotAccessMemory(F);
2278         }
2279         break;
2280       case 'l':
2281         if (Name == "lstat") {
2282           if (FTy->getNumParams() != 2 ||
2283               !isa<PointerType>(FTy->getParamType(0)) ||
2284               !isa<PointerType>(FTy->getParamType(1)))
2285             continue;
2286           setDoesNotThrow(F);
2287           setDoesNotCapture(F, 1);
2288           setDoesNotCapture(F, 2);
2289         } else if (Name == "lchown") {
2290           if (FTy->getNumParams() != 3 ||
2291               !isa<PointerType>(FTy->getParamType(0)))
2292             continue;
2293           setDoesNotThrow(F);
2294           setDoesNotCapture(F, 1);
2295         }
2296         break;
2297       case 'q':
2298         if (Name == "qsort") {
2299           if (FTy->getNumParams() != 4 ||
2300               !isa<PointerType>(FTy->getParamType(3)))
2301             continue;
2302           // May throw; places call through function pointer.
2303           setDoesNotCapture(F, 4);
2304         }
2305         break;
2306       case '_':
2307         if (Name == "__strdup" ||
2308             Name == "__strndup") {
2309           if (FTy->getNumParams() < 1 ||
2310               !isa<PointerType>(FTy->getReturnType()) ||
2311               !isa<PointerType>(FTy->getParamType(0)))
2312             continue;
2313           setDoesNotThrow(F);
2314           setDoesNotAlias(F, 0);
2315           setDoesNotCapture(F, 1);
2316         } else if (Name == "__strtok_r") {
2317           if (FTy->getNumParams() != 3 ||
2318               !isa<PointerType>(FTy->getParamType(1)))
2319             continue;
2320           setDoesNotThrow(F);
2321           setDoesNotCapture(F, 2);
2322         } else if (Name == "_IO_getc") {
2323           if (FTy->getNumParams() != 1 ||
2324               !isa<PointerType>(FTy->getParamType(0)))
2325             continue;
2326           setDoesNotThrow(F);
2327           setDoesNotCapture(F, 1);
2328         } else if (Name == "_IO_putc") {
2329           if (FTy->getNumParams() != 2 ||
2330               !isa<PointerType>(FTy->getParamType(1)))
2331             continue;
2332           setDoesNotThrow(F);
2333           setDoesNotCapture(F, 2);
2334         }
2335         break;
2336       case 1:
2337         if (Name == "\1__isoc99_scanf") {
2338           if (FTy->getNumParams() < 1 ||
2339               !isa<PointerType>(FTy->getParamType(0)))
2340             continue;
2341           setDoesNotThrow(F);
2342           setDoesNotCapture(F, 1);
2343         } else if (Name == "\1stat64" ||
2344                    Name == "\1lstat64" ||
2345                    Name == "\1statvfs64" ||
2346                    Name == "\1__isoc99_sscanf") {
2347           if (FTy->getNumParams() < 1 ||
2348               !isa<PointerType>(FTy->getParamType(0)) ||
2349               !isa<PointerType>(FTy->getParamType(1)))
2350             continue;
2351           setDoesNotThrow(F);
2352           setDoesNotCapture(F, 1);
2353           setDoesNotCapture(F, 2);
2354         } else if (Name == "\1fopen64") {
2355           if (FTy->getNumParams() != 2 ||
2356               !isa<PointerType>(FTy->getReturnType()) ||
2357               !isa<PointerType>(FTy->getParamType(0)) ||
2358               !isa<PointerType>(FTy->getParamType(1)))
2359             continue;
2360           setDoesNotThrow(F);
2361           setDoesNotAlias(F, 0);
2362           setDoesNotCapture(F, 1);
2363           setDoesNotCapture(F, 2);
2364         } else if (Name == "\1fseeko64" ||
2365                    Name == "\1ftello64") {
2366           if (FTy->getNumParams() == 0 ||
2367               !isa<PointerType>(FTy->getParamType(0)))
2368             continue;
2369           setDoesNotThrow(F);
2370           setDoesNotCapture(F, 1);
2371         } else if (Name == "\1tmpfile64") {
2372           if (!isa<PointerType>(FTy->getReturnType()))
2373             continue;
2374           setDoesNotThrow(F);
2375           setDoesNotAlias(F, 0);
2376         } else if (Name == "\1fstat64" ||
2377                    Name == "\1fstatvfs64") {
2378           if (FTy->getNumParams() != 2 ||
2379               !isa<PointerType>(FTy->getParamType(1)))
2380             continue;
2381           setDoesNotThrow(F);
2382           setDoesNotCapture(F, 2);
2383         } else if (Name == "\1open64") {
2384           if (FTy->getNumParams() < 2 ||
2385               !isa<PointerType>(FTy->getParamType(0)))
2386             continue;
2387           // May throw; "open" is a valid pthread cancellation point.
2388           setDoesNotCapture(F, 1);
2389         }
2390         break;
2391     }
2392   }
2393   return Modified;
2394 }
2395
2396 // TODO:
2397 //   Additional cases that we need to add to this file:
2398 //
2399 // cbrt:
2400 //   * cbrt(expN(X))  -> expN(x/3)
2401 //   * cbrt(sqrt(x))  -> pow(x,1/6)
2402 //   * cbrt(sqrt(x))  -> pow(x,1/9)
2403 //
2404 // cos, cosf, cosl:
2405 //   * cos(-x)  -> cos(x)
2406 //
2407 // exp, expf, expl:
2408 //   * exp(log(x))  -> x
2409 //
2410 // log, logf, logl:
2411 //   * log(exp(x))   -> x
2412 //   * log(x**y)     -> y*log(x)
2413 //   * log(exp(y))   -> y*log(e)
2414 //   * log(exp2(y))  -> y*log(2)
2415 //   * log(exp10(y)) -> y*log(10)
2416 //   * log(sqrt(x))  -> 0.5*log(x)
2417 //   * log(pow(x,y)) -> y*log(x)
2418 //
2419 // lround, lroundf, lroundl:
2420 //   * lround(cnst) -> cnst'
2421 //
2422 // memcmp:
2423 //   * memcmp(x,y,l)   -> cnst
2424 //      (if all arguments are constant and strlen(x) <= l and strlen(y) <= l)
2425 //
2426 // pow, powf, powl:
2427 //   * pow(exp(x),y)  -> exp(x*y)
2428 //   * pow(sqrt(x),y) -> pow(x,y*0.5)
2429 //   * pow(pow(x,y),z)-> pow(x,y*z)
2430 //
2431 // puts:
2432 //   * puts("") -> putchar("\n")
2433 //
2434 // round, roundf, roundl:
2435 //   * round(cnst) -> cnst'
2436 //
2437 // signbit:
2438 //   * signbit(cnst) -> cnst'
2439 //   * signbit(nncst) -> 0 (if pstv is a non-negative constant)
2440 //
2441 // sqrt, sqrtf, sqrtl:
2442 //   * sqrt(expN(x))  -> expN(x*0.5)
2443 //   * sqrt(Nroot(x)) -> pow(x,1/(2*N))
2444 //   * sqrt(pow(x,y)) -> pow(|x|,y*0.5)
2445 //
2446 // stpcpy:
2447 //   * stpcpy(str, "literal") ->
2448 //           llvm.memcpy(str,"literal",strlen("literal")+1,1)
2449 // strrchr:
2450 //   * strrchr(s,c) -> reverse_offset_of_in(c,s)
2451 //      (if c is a constant integer and s is a constant string)
2452 //   * strrchr(s1,0) -> strchr(s1,0)
2453 //
2454 // strpbrk:
2455 //   * strpbrk(s,a) -> offset_in_for(s,a)
2456 //      (if s and a are both constant strings)
2457 //   * strpbrk(s,"") -> 0
2458 //   * strpbrk(s,a) -> strchr(s,a[0]) (if a is constant string of length 1)
2459 //
2460 // strspn, strcspn:
2461 //   * strspn(s,a)   -> const_int (if both args are constant)
2462 //   * strspn("",a)  -> 0
2463 //   * strspn(s,"")  -> 0
2464 //   * strcspn(s,a)  -> const_int (if both args are constant)
2465 //   * strcspn("",a) -> 0
2466 //   * strcspn(s,"") -> strlen(a)
2467 //
2468 // strstr:
2469 //   * strstr(x,x)  -> x
2470 //   * strstr(s1,s2) -> offset_of_s2_in(s1)
2471 //       (if s1 and s2 are constant strings)
2472 //
2473 // tan, tanf, tanl:
2474 //   * tan(atan(x)) -> x
2475 //
2476 // trunc, truncf, truncl:
2477 //   * trunc(cnst) -> cnst'
2478 //
2479 //