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