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()->isDoubleTy()) {
 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()->isFloatTy())
 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 ||
 626           FT->getParamType(1) != Type::getInt32Ty(*Context)) // memchr needs i32.
 627         return 0;
 628
 629       return EmitMemChr(SrcStr, CI->getOperand(2), // include nul.
 630                         ConstantInt::get(TD->getIntPtrType(*Context), Len), B);
 631     }
 632
 633     // Otherwise, the character is a constant, see if the first argument is
 634     // a string literal.  If so, we can constant fold.
 635     std::string Str;
 636     if (!GetConstantStringInfo(SrcStr, Str))
 637       return 0;
 638
 639     // strchr can find the nul character.
 640     Str += '\0';
 641     char CharValue = CharC->getSExtValue();
 642
 643     // Compute the offset.
 644     uint64_t i = 0;
 645     while (1) {
 646       if (i == Str.size())    // Didn't find the char.  strchr returns null.
 647         return Constant::getNullValue(CI->getType());
 648       // Did we find our match?
 649       if (Str[i] == CharValue)
 650         break;
 651       ++i;
 652     }
 653
 654     // strchr(s+n,c)  -> gep(s+n+i,c)
 655     Value *Idx = ConstantInt::get(Type::getInt64Ty(*Context), i);
 656     return B.CreateGEP(SrcStr, Idx, "strchr");
 657   }
 658 };
 659
 660 //===---------------------------------------===//
 661 // 'strcmp' Optimizations
 662
 663 struct StrCmpOpt : public LibCallOptimization {
 664   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 665     // Verify the "strcmp" function prototype.
 666     const FunctionType *FT = Callee->getFunctionType();
 667     if (FT->getNumParams() != 2 || FT->getReturnType() != Type::getInt32Ty(*Context) ||
 668         FT->getParamType(0) != FT->getParamType(1) ||
 669         FT->getParamType(0) != PointerType::getUnqual(Type::getInt8Ty(*Context)))
 670       return 0;
 671
 672     Value *Str1P = CI->getOperand(1), *Str2P = CI->getOperand(2);
 673     if (Str1P == Str2P)      // strcmp(x,x)  -> 0
 674       return ConstantInt::get(CI->getType(), 0);
 675
 676     std::string Str1, Str2;
 677     bool HasStr1 = GetConstantStringInfo(Str1P, Str1);
 678     bool HasStr2 = GetConstantStringInfo(Str2P, Str2);
 679
 680     if (HasStr1 && Str1.empty()) // strcmp("", x) -> *x
 681       return B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"), CI->getType());
 682
 683     if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x
 684       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
 685
 686     // strcmp(x, y)  -> cnst  (if both x and y are constant strings)
 687     if (HasStr1 && HasStr2)
 688       return ConstantInt::get(CI->getType(),
 689                                      strcmp(Str1.c_str(),Str2.c_str()));
 690
 691     // strcmp(P, "x") -> memcmp(P, "x", 2)
 692     uint64_t Len1 = GetStringLength(Str1P);
 693     uint64_t Len2 = GetStringLength(Str2P);
 694     if (Len1 && Len2) {
 695       // These optimizations require TargetData.
 696       if (!TD) return 0;
 697
 698       return EmitMemCmp(Str1P, Str2P,
 699                         ConstantInt::get(TD->getIntPtrType(*Context),
 700                         std::min(Len1, Len2)), B);
 701     }
 702
 703     return 0;
 704   }
 705 };
 706
 707 //===---------------------------------------===//
 708 // 'strncmp' Optimizations
 709
 710 struct StrNCmpOpt : public LibCallOptimization {
 711   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 712     // Verify the "strncmp" function prototype.
 713     const FunctionType *FT = Callee->getFunctionType();
 714     if (FT->getNumParams() != 3 || FT->getReturnType() != Type::getInt32Ty(*Context) ||
 715         FT->getParamType(0) != FT->getParamType(1) ||
 716         FT->getParamType(0) != PointerType::getUnqual(Type::getInt8Ty(*Context)) ||
 717         !isa<IntegerType>(FT->getParamType(2)))
 718       return 0;
 719
 720     Value *Str1P = CI->getOperand(1), *Str2P = CI->getOperand(2);
 721     if (Str1P == Str2P)      // strncmp(x,x,n)  -> 0
 722       return ConstantInt::get(CI->getType(), 0);
 723
 724     // Get the length argument if it is constant.
 725     uint64_t Length;
 726     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getOperand(3)))
 727       Length = LengthArg->getZExtValue();
 728     else
 729       return 0;
 730
 731     if (Length == 0) // strncmp(x,y,0)   -> 0
 732       return ConstantInt::get(CI->getType(), 0);
 733
 734     std::string Str1, Str2;
 735     bool HasStr1 = GetConstantStringInfo(Str1P, Str1);
 736     bool HasStr2 = GetConstantStringInfo(Str2P, Str2);
 737
 738     if (HasStr1 && Str1.empty())  // strncmp("", x, n) -> *x
 739       return B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"), CI->getType());
 740
 741     if (HasStr2 && Str2.empty())  // strncmp(x, "", n) -> *x
 742       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
 743
 744     // strncmp(x, y)  -> cnst  (if both x and y are constant strings)
 745     if (HasStr1 && HasStr2)
 746       return ConstantInt::get(CI->getType(),
 747                               strncmp(Str1.c_str(), Str2.c_str(), Length));
 748     return 0;
 749   }
 750 };
 751
 752
 753 //===---------------------------------------===//
 754 // 'strcpy' Optimizations
 755
 756 struct StrCpyOpt : public LibCallOptimization {
 757   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 758     // Verify the "strcpy" function prototype.
 759     const FunctionType *FT = Callee->getFunctionType();
 760     if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) ||
 761         FT->getParamType(0) != FT->getParamType(1) ||
 762         FT->getParamType(0) != PointerType::getUnqual(Type::getInt8Ty(*Context)))
 763       return 0;
 764
 765     Value *Dst = CI->getOperand(1), *Src = CI->getOperand(2);
 766     if (Dst == Src)      // strcpy(x,x)  -> x
 767       return Src;
 768
 769     // These optimizations require TargetData.
 770     if (!TD) return 0;
 771
 772     // See if we can get the length of the input string.
 773     uint64_t Len = GetStringLength(Src);
 774     if (Len == 0) return 0;
 775
 776     // We have enough information to now generate the memcpy call to do the
 777     // concatenation for us.  Make a memcpy to copy the nul byte with align = 1.
 778     EmitMemCpy(Dst, Src,
 779                ConstantInt::get(TD->getIntPtrType(*Context), Len), 1, B);
 780     return Dst;
 781   }
 782 };
 783
 784 //===---------------------------------------===//
 785 // 'strncpy' Optimizations
 786
 787 struct StrNCpyOpt : public LibCallOptimization {
 788   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 789     const FunctionType *FT = Callee->getFunctionType();
 790     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 791         FT->getParamType(0) != FT->getParamType(1) ||
 792         FT->getParamType(0) != PointerType::getUnqual(Type::getInt8Ty(*Context)) ||
 793         !isa<IntegerType>(FT->getParamType(2)))
 794       return 0;
 795
 796     Value *Dst = CI->getOperand(1);
 797     Value *Src = CI->getOperand(2);
 798     Value *LenOp = CI->getOperand(3);
 799
 800     // See if we can get the length of the input string.
 801     uint64_t SrcLen = GetStringLength(Src);
 802     if (SrcLen == 0) return 0;
 803     --SrcLen;
 804
 805     if (SrcLen == 0) {
 806       // strncpy(x, "", y) -> memset(x, '\0', y, 1)
 807       EmitMemSet(Dst, ConstantInt::get(Type::getInt8Ty(*Context), '\0'), LenOp, B);
 808       return Dst;
 809     }
 810
 811     uint64_t Len;
 812     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(LenOp))
 813       Len = LengthArg->getZExtValue();
 814     else
 815       return 0;
 816
 817     if (Len == 0) return Dst; // strncpy(x, y, 0) -> x
 818
 819     // These optimizations require TargetData.
 820     if (!TD) return 0;
 821
 822     // Let strncpy handle the zero padding
 823     if (Len > SrcLen+1) return 0;
 824
 825     // strncpy(x, s, c) -> memcpy(x, s, c, 1) [s and c are constant]
 826     EmitMemCpy(Dst, Src,
 827                ConstantInt::get(TD->getIntPtrType(*Context), Len), 1, B);
 828
 829     return Dst;
 830   }
 831 };
 832
 833 //===---------------------------------------===//
 834 // 'strlen' Optimizations
 835
 836 struct StrLenOpt : public LibCallOptimization {
 837   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 838     const FunctionType *FT = Callee->getFunctionType();
 839     if (FT->getNumParams() != 1 ||
 840         FT->getParamType(0) != PointerType::getUnqual(Type::getInt8Ty(*Context)) ||
 841         !isa<IntegerType>(FT->getReturnType()))
 842       return 0;
 843
 844     Value *Src = CI->getOperand(1);
 845
 846     // Constant folding: strlen("xyz") -> 3
 847     if (uint64_t Len = GetStringLength(Src))
 848       return ConstantInt::get(CI->getType(), Len-1);
 849
 850     // Handle strlen(p) != 0.
 851     if (!IsOnlyUsedInZeroEqualityComparison(CI)) return 0;
 852
 853     // strlen(x) != 0 --> *x != 0
 854     // strlen(x) == 0 --> *x == 0
 855     return B.CreateZExt(B.CreateLoad(Src, "strlenfirst"), CI->getType());
 856   }
 857 };
 858
 859 //===---------------------------------------===//
 860 // 'strto*' Optimizations
 861
 862 struct StrToOpt : public LibCallOptimization {
 863   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 864     const FunctionType *FT = Callee->getFunctionType();
 865     if ((FT->getNumParams() != 2 && FT->getNumParams() != 3) ||
 866         !isa<PointerType>(FT->getParamType(0)) ||
 867         !isa<PointerType>(FT->getParamType(1)))
 868       return 0;
 869
 870     Value *EndPtr = CI->getOperand(2);
 871     if (isa<ConstantPointerNull>(EndPtr)) {
 872       CI->setOnlyReadsMemory();
 873       CI->addAttribute(1, Attribute::NoCapture);
 874     }
 875
 876     return 0;
 877   }
 878 };
 879
 880
 881 //===---------------------------------------===//
 882 // 'memcmp' Optimizations
 883
 884 struct MemCmpOpt : public LibCallOptimization {
 885   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 886     const FunctionType *FT = Callee->getFunctionType();
 887     if (FT->getNumParams() != 3 || !isa<PointerType>(FT->getParamType(0)) ||
 888         !isa<PointerType>(FT->getParamType(1)) ||
 889         FT->getReturnType() != Type::getInt32Ty(*Context))
 890       return 0;
 891
 892     Value *LHS = CI->getOperand(1), *RHS = CI->getOperand(2);
 893
 894     if (LHS == RHS)  // memcmp(s,s,x) -> 0
 895       return Constant::getNullValue(CI->getType());
 896
 897     // Make sure we have a constant length.
 898     ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getOperand(3));
 899     if (!LenC) return 0;
 900     uint64_t Len = LenC->getZExtValue();
 901
 902     if (Len == 0) // memcmp(s1,s2,0) -> 0
 903       return Constant::getNullValue(CI->getType());
 904
 905     if (Len == 1) { // memcmp(S1,S2,1) -> *LHS - *RHS
 906       Value *LHSV = B.CreateLoad(CastToCStr(LHS, B), "lhsv");
 907       Value *RHSV = B.CreateLoad(CastToCStr(RHS, B), "rhsv");
 908       return B.CreateSExt(B.CreateSub(LHSV, RHSV, "chardiff"), CI->getType());
 909     }
 910
 911     // memcmp(S1,S2,2) != 0 -> (*(short*)LHS ^ *(short*)RHS)  != 0
 912     // memcmp(S1,S2,4) != 0 -> (*(int*)LHS ^ *(int*)RHS)  != 0
 913     if ((Len == 2 || Len == 4) && IsOnlyUsedInZeroEqualityComparison(CI)) {
 914       const Type *PTy = PointerType::getUnqual(Len == 2 ?
 915                        Type::getInt16Ty(*Context) : Type::getInt32Ty(*Context));
 916       LHS = B.CreateBitCast(LHS, PTy, "tmp");
 917       RHS = B.CreateBitCast(RHS, PTy, "tmp");
 918       LoadInst *LHSV = B.CreateLoad(LHS, "lhsv");
 919       LoadInst *RHSV = B.CreateLoad(RHS, "rhsv");
 920       LHSV->setAlignment(1); RHSV->setAlignment(1);  // Unaligned loads.
 921       return B.CreateZExt(B.CreateXor(LHSV, RHSV, "shortdiff"), CI->getType());
 922     }
 923
 924     return 0;
 925   }
 926 };
 927
 928 //===---------------------------------------===//
 929 // 'memcpy' Optimizations
 930
 931 struct MemCpyOpt : public LibCallOptimization {
 932   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 933     // These optimizations require TargetData.
 934     if (!TD) return 0;
 935
 936     const FunctionType *FT = Callee->getFunctionType();
 937     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 938         !isa<PointerType>(FT->getParamType(0)) ||
 939         !isa<PointerType>(FT->getParamType(1)) ||
 940         FT->getParamType(2) != TD->getIntPtrType(*Context))
 941       return 0;
 942
 943     // memcpy(x, y, n) -> llvm.memcpy(x, y, n, 1)
 944     EmitMemCpy(CI->getOperand(1), CI->getOperand(2), CI->getOperand(3), 1, B);
 945     return CI->getOperand(1);
 946   }
 947 };
 948
 949 //===---------------------------------------===//
 950 // 'memmove' Optimizations
 951
 952 struct MemMoveOpt : public LibCallOptimization {
 953   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 954     // These optimizations require TargetData.
 955     if (!TD) return 0;
 956
 957     const FunctionType *FT = Callee->getFunctionType();
 958     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 959         !isa<PointerType>(FT->getParamType(0)) ||
 960         !isa<PointerType>(FT->getParamType(1)) ||
 961         FT->getParamType(2) != TD->getIntPtrType(*Context))
 962       return 0;
 963
 964     // memmove(x, y, n) -> llvm.memmove(x, y, n, 1)
 965     Module *M = Caller->getParent();
 966     Intrinsic::ID IID = Intrinsic::memmove;
 967     const Type *Tys[1];
 968     Tys[0] = TD->getIntPtrType(*Context);
 969     Value *MemMove = Intrinsic::getDeclaration(M, IID, Tys, 1);
 970     Value *Dst = CastToCStr(CI->getOperand(1), B);
 971     Value *Src = CastToCStr(CI->getOperand(2), B);
 972     Value *Size = CI->getOperand(3);
 973     Value *Align = ConstantInt::get(Type::getInt32Ty(*Context), 1);
 974     B.CreateCall4(MemMove, Dst, Src, Size, Align);
 975     return CI->getOperand(1);
 976   }
 977 };
 978
 979 //===---------------------------------------===//
 980 // 'memset' Optimizations
 981
 982 struct MemSetOpt : public LibCallOptimization {
 983   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 984     // These optimizations require TargetData.
 985     if (!TD) return 0;
 986
 987     const FunctionType *FT = Callee->getFunctionType();
 988     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 989         !isa<PointerType>(FT->getParamType(0)) ||
 990         !isa<IntegerType>(FT->getParamType(1)) ||
 991         FT->getParamType(2) != TD->getIntPtrType(*Context))
 992       return 0;
 993
 994     // memset(p, v, n) -> llvm.memset(p, v, n, 1)
 995     Value *Val = B.CreateIntCast(CI->getOperand(2), Type::getInt8Ty(*Context), false);
 996     EmitMemSet(CI->getOperand(1), Val,  CI->getOperand(3), B);
 997     return CI->getOperand(1);
 998   }
 999 };
1000
1001 //===----------------------------------------------------------------------===//
1002 // Math Library Optimizations
1003 //===----------------------------------------------------------------------===//
1004
1005 //===---------------------------------------===//
1006 // 'pow*' Optimizations
1007
1008 struct PowOpt : public LibCallOptimization {
1009   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1010     const FunctionType *FT = Callee->getFunctionType();
1011     // Just make sure this has 2 arguments of the same FP type, which match the
1012     // result type.
1013     if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) ||
1014         FT->getParamType(0) != FT->getParamType(1) ||
1015         !FT->getParamType(0)->isFloatingPoint())
1016       return 0;
1017
1018     Value *Op1 = CI->getOperand(1), *Op2 = CI->getOperand(2);
1019     if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) {
1020       if (Op1C->isExactlyValue(1.0))  // pow(1.0, x) -> 1.0
1021         return Op1C;
1022       if (Op1C->isExactlyValue(2.0))  // pow(2.0, x) -> exp2(x)
1023         return EmitUnaryFloatFnCall(Op2, "exp2", B, Callee->getAttributes());
1024     }
1025
1026     ConstantFP *Op2C = dyn_cast<ConstantFP>(Op2);
1027     if (Op2C == 0) return 0;
1028
1029     if (Op2C->getValueAPF().isZero())  // pow(x, 0.0) -> 1.0
1030       return ConstantFP::get(CI->getType(), 1.0);
1031
1032     if (Op2C->isExactlyValue(0.5)) {
1033       // Expand pow(x, 0.5) to (x == -infinity ? +infinity : fabs(sqrt(x))).
1034       // This is faster than calling pow, and still handles negative zero
1035       // and negative infinite correctly.
1036       // TODO: In fast-math mode, this could be just sqrt(x).
1037       // TODO: In finite-only mode, this could be just fabs(sqrt(x)).
1038       Value *Inf = ConstantFP::getInfinity(CI->getType());
1039       Value *NegInf = ConstantFP::getInfinity(CI->getType(), true);
1040       Value *Sqrt = EmitUnaryFloatFnCall(Op1, "sqrt", B,
1041                                          Callee->getAttributes());
1042       Value *FAbs = EmitUnaryFloatFnCall(Sqrt, "fabs", B,
1043                                          Callee->getAttributes());
1044       Value *FCmp = B.CreateFCmpOEQ(Op1, NegInf, "tmp");
1045       Value *Sel = B.CreateSelect(FCmp, Inf, FAbs, "tmp");
1046       return Sel;
1047     }
1048
1049     if (Op2C->isExactlyValue(1.0))  // pow(x, 1.0) -> x
1050       return Op1;
1051     if (Op2C->isExactlyValue(2.0))  // pow(x, 2.0) -> x*x
1052       return B.CreateFMul(Op1, Op1, "pow2");
1053     if (Op2C->isExactlyValue(-1.0)) // pow(x, -1.0) -> 1.0/x
1054       return B.CreateFDiv(ConstantFP::get(CI->getType(), 1.0),
1055                           Op1, "powrecip");
1056     return 0;
1057   }
1058 };
1059
1060 //===---------------------------------------===//
1061 // 'exp2' Optimizations
1062
1063 struct Exp2Opt : public LibCallOptimization {
1064   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1065     const FunctionType *FT = Callee->getFunctionType();
1066     // Just make sure this has 1 argument of FP type, which matches the
1067     // result type.
1068     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1069         !FT->getParamType(0)->isFloatingPoint())
1070       return 0;
1071
1072     Value *Op = CI->getOperand(1);
1073     // Turn exp2(sitofp(x)) -> ldexp(1.0, sext(x))  if sizeof(x) <= 32
1074     // Turn exp2(uitofp(x)) -> ldexp(1.0, zext(x))  if sizeof(x) < 32
1075     Value *LdExpArg = 0;
1076     if (SIToFPInst *OpC = dyn_cast<SIToFPInst>(Op)) {
1077       if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() <= 32)
1078         LdExpArg = B.CreateSExt(OpC->getOperand(0), Type::getInt32Ty(*Context), "tmp");
1079     } else if (UIToFPInst *OpC = dyn_cast<UIToFPInst>(Op)) {
1080       if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() < 32)
1081         LdExpArg = B.CreateZExt(OpC->getOperand(0), Type::getInt32Ty(*Context), "tmp");
1082     }
1083
1084     if (LdExpArg) {
1085       const char *Name;
1086       if (Op->getType()->isFloatTy())
1087         Name = "ldexpf";
1088       else if (Op->getType()->isDoubleTy())
1089         Name = "ldexp";
1090       else
1091         Name = "ldexpl";
1092
1093       Constant *One = ConstantFP::get(*Context, APFloat(1.0f));
1094       if (!Op->getType()->isFloatTy())
1095         One = ConstantExpr::getFPExtend(One, Op->getType());
1096
1097       Module *M = Caller->getParent();
1098       Value *Callee = M->getOrInsertFunction(Name, Op->getType(),
1099                                              Op->getType(), Type::getInt32Ty(*Context),NULL);
1100       CallInst *CI = B.CreateCall2(Callee, One, LdExpArg);
1101       if (const Function *F = dyn_cast<Function>(Callee->stripPointerCasts()))
1102         CI->setCallingConv(F->getCallingConv());
1103
1104       return CI;
1105     }
1106     return 0;
1107   }
1108 };
1109
1110 //===---------------------------------------===//
1111 // Double -> Float Shrinking Optimizations for Unary Functions like 'floor'
1112
1113 struct UnaryDoubleFPOpt : public LibCallOptimization {
1114   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1115     const FunctionType *FT = Callee->getFunctionType();
1116     if (FT->getNumParams() != 1 || !FT->getReturnType()->isDoubleTy() ||
1117         !FT->getParamType(0)->isDoubleTy())
1118       return 0;
1119
1120     // If this is something like 'floor((double)floatval)', convert to floorf.
1121     FPExtInst *Cast = dyn_cast<FPExtInst>(CI->getOperand(1));
1122     if (Cast == 0 || !Cast->getOperand(0)->getType()->isFloatTy())
1123       return 0;
1124
1125     // floor((double)floatval) -> (double)floorf(floatval)
1126     Value *V = Cast->getOperand(0);
1127     V = EmitUnaryFloatFnCall(V, Callee->getName().data(), B,
1128                              Callee->getAttributes());
1129     return B.CreateFPExt(V, Type::getDoubleTy(*Context));
1130   }
1131 };
1132
1133 //===----------------------------------------------------------------------===//
1134 // Integer Optimizations
1135 //===----------------------------------------------------------------------===//
1136
1137 //===---------------------------------------===//
1138 // 'ffs*' Optimizations
1139
1140 struct FFSOpt : public LibCallOptimization {
1141   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1142     const FunctionType *FT = Callee->getFunctionType();
1143     // Just make sure this has 2 arguments of the same FP type, which match the
1144     // result type.
1145     if (FT->getNumParams() != 1 || FT->getReturnType() != Type::getInt32Ty(*Context) ||
1146         !isa<IntegerType>(FT->getParamType(0)))
1147       return 0;
1148
1149     Value *Op = CI->getOperand(1);
1150
1151     // Constant fold.
1152     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op)) {
1153       if (CI->getValue() == 0)  // ffs(0) -> 0.
1154         return Constant::getNullValue(CI->getType());
1155       return ConstantInt::get(Type::getInt32Ty(*Context), // ffs(c) -> cttz(c)+1
1156                               CI->getValue().countTrailingZeros()+1);
1157     }
1158
1159     // ffs(x) -> x != 0 ? (i32)llvm.cttz(x)+1 : 0
1160     const Type *ArgType = Op->getType();
1161     Value *F = Intrinsic::getDeclaration(Callee->getParent(),
1162                                          Intrinsic::cttz, &ArgType, 1);
1163     Value *V = B.CreateCall(F, Op, "cttz");
1164     V = B.CreateAdd(V, ConstantInt::get(V->getType(), 1), "tmp");
1165     V = B.CreateIntCast(V, Type::getInt32Ty(*Context), false, "tmp");
1166
1167     Value *Cond = B.CreateICmpNE(Op, Constant::getNullValue(ArgType), "tmp");
1168     return B.CreateSelect(Cond, V, ConstantInt::get(Type::getInt32Ty(*Context), 0));
1169   }
1170 };
1171
1172 //===---------------------------------------===//
1173 // 'isdigit' Optimizations
1174
1175 struct IsDigitOpt : public LibCallOptimization {
1176   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1177     const FunctionType *FT = Callee->getFunctionType();
1178     // We require integer(i32)
1179     if (FT->getNumParams() != 1 || !isa<IntegerType>(FT->getReturnType()) ||
1180         FT->getParamType(0) != Type::getInt32Ty(*Context))
1181       return 0;
1182
1183     // isdigit(c) -> (c-'0') <u 10
1184     Value *Op = CI->getOperand(1);
1185     Op = B.CreateSub(Op, ConstantInt::get(Type::getInt32Ty(*Context), '0'),
1186                      "isdigittmp");
1187     Op = B.CreateICmpULT(Op, ConstantInt::get(Type::getInt32Ty(*Context), 10),
1188                          "isdigit");
1189     return B.CreateZExt(Op, CI->getType());
1190   }
1191 };
1192
1193 //===---------------------------------------===//
1194 // 'isascii' Optimizations
1195
1196 struct IsAsciiOpt : public LibCallOptimization {
1197   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1198     const FunctionType *FT = Callee->getFunctionType();
1199     // We require integer(i32)
1200     if (FT->getNumParams() != 1 || !isa<IntegerType>(FT->getReturnType()) ||
1201         FT->getParamType(0) != Type::getInt32Ty(*Context))
1202       return 0;
1203
1204     // isascii(c) -> c <u 128
1205     Value *Op = CI->getOperand(1);
1206     Op = B.CreateICmpULT(Op, ConstantInt::get(Type::getInt32Ty(*Context), 128),
1207                          "isascii");
1208     return B.CreateZExt(Op, CI->getType());
1209   }
1210 };
1211
1212 //===---------------------------------------===//
1213 // 'abs', 'labs', 'llabs' Optimizations
1214
1215 struct AbsOpt : public LibCallOptimization {
1216   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1217     const FunctionType *FT = Callee->getFunctionType();
1218     // We require integer(integer) where the types agree.
1219     if (FT->getNumParams() != 1 || !isa<IntegerType>(FT->getReturnType()) ||
1220         FT->getParamType(0) != FT->getReturnType())
1221       return 0;
1222
1223     // abs(x) -> x >s -1 ? x : -x
1224     Value *Op = CI->getOperand(1);
1225     Value *Pos = B.CreateICmpSGT(Op,
1226                              Constant::getAllOnesValue(Op->getType()),
1227                                  "ispos");
1228     Value *Neg = B.CreateNeg(Op, "neg");
1229     return B.CreateSelect(Pos, Op, Neg);
1230   }
1231 };
1232
1233
1234 //===---------------------------------------===//
1235 // 'toascii' Optimizations
1236
1237 struct ToAsciiOpt : public LibCallOptimization {
1238   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1239     const FunctionType *FT = Callee->getFunctionType();
1240     // We require i32(i32)
1241     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1242         FT->getParamType(0) != Type::getInt32Ty(*Context))
1243       return 0;
1244
1245     // isascii(c) -> c & 0x7f
1246     return B.CreateAnd(CI->getOperand(1),
1247                        ConstantInt::get(CI->getType(),0x7F));
1248   }
1249 };
1250
1251 //===----------------------------------------------------------------------===//
1252 // Formatting and IO Optimizations
1253 //===----------------------------------------------------------------------===//
1254
1255 //===---------------------------------------===//
1256 // 'printf' Optimizations
1257
1258 struct PrintFOpt : public LibCallOptimization {
1259   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1260     // Require one fixed pointer argument and an integer/void result.
1261     const FunctionType *FT = Callee->getFunctionType();
1262     if (FT->getNumParams() < 1 || !isa<PointerType>(FT->getParamType(0)) ||
1263         !(isa<IntegerType>(FT->getReturnType()) ||
1264           FT->getReturnType()->isVoidTy()))
1265       return 0;
1266
1267     // Check for a fixed format string.
1268     std::string FormatStr;
1269     if (!GetConstantStringInfo(CI->getOperand(1), FormatStr))
1270       return 0;
1271
1272     // Empty format string -> noop.
1273     if (FormatStr.empty())  // Tolerate printf's declared void.
1274       return CI->use_empty() ? (Value*)CI :
1275                                ConstantInt::get(CI->getType(), 0);
1276
1277     // printf("x") -> putchar('x'), even for '%'.
1278     if (FormatStr.size() == 1) {
1279       EmitPutChar(ConstantInt::get(Type::getInt32Ty(*Context), FormatStr[0]), B);
1280       return CI->use_empty() ? (Value*)CI :
1281                                ConstantInt::get(CI->getType(), 1);
1282     }
1283
1284     // printf("foo\n") --> puts("foo")
1285     if (FormatStr[FormatStr.size()-1] == '\n' &&
1286         FormatStr.find('%') == std::string::npos) {  // no format characters.
1287       // Create a string literal with no \n on it.  We expect the constant merge
1288       // pass to be run after this pass, to merge duplicate strings.
1289       FormatStr.erase(FormatStr.end()-1);
1290       Constant *C = ConstantArray::get(*Context, FormatStr, true);
1291       C = new GlobalVariable(*Callee->getParent(), C->getType(), true,
1292                              GlobalVariable::InternalLinkage, C, "str");
1293       EmitPutS(C, B);
1294       return CI->use_empty() ? (Value*)CI :
1295                     ConstantInt::get(CI->getType(), FormatStr.size()+1);
1296     }
1297
1298     // Optimize specific format strings.
1299     // printf("%c", chr) --> putchar(*(i8*)dst)
1300     if (FormatStr == "%c" && CI->getNumOperands() > 2 &&
1301         isa<IntegerType>(CI->getOperand(2)->getType())) {
1302       EmitPutChar(CI->getOperand(2), B);
1303       return CI->use_empty() ? (Value*)CI :
1304                                ConstantInt::get(CI->getType(), 1);
1305     }
1306
1307     // printf("%s\n", str) --> puts(str)
1308     if (FormatStr == "%s\n" && CI->getNumOperands() > 2 &&
1309         isa<PointerType>(CI->getOperand(2)->getType()) &&
1310         CI->use_empty()) {
1311       EmitPutS(CI->getOperand(2), B);
1312       return CI;
1313     }
1314     return 0;
1315   }
1316 };
1317
1318 //===---------------------------------------===//
1319 // 'sprintf' Optimizations
1320
1321 struct SPrintFOpt : public LibCallOptimization {
1322   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1323     // Require two fixed pointer arguments and an integer result.
1324     const FunctionType *FT = Callee->getFunctionType();
1325     if (FT->getNumParams() != 2 || !isa<PointerType>(FT->getParamType(0)) ||
1326         !isa<PointerType>(FT->getParamType(1)) ||
1327         !isa<IntegerType>(FT->getReturnType()))
1328       return 0;
1329
1330     // Check for a fixed format string.
1331     std::string FormatStr;
1332     if (!GetConstantStringInfo(CI->getOperand(2), FormatStr))
1333       return 0;
1334
1335     // If we just have a format string (nothing else crazy) transform it.
1336     if (CI->getNumOperands() == 3) {
1337       // Make sure there's no % in the constant array.  We could try to handle
1338       // %% -> % in the future if we cared.
1339       for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1340         if (FormatStr[i] == '%')
1341           return 0; // we found a format specifier, bail out.
1342
1343       // These optimizations require TargetData.
1344       if (!TD) return 0;
1345
1346       // sprintf(str, fmt) -> llvm.memcpy(str, fmt, strlen(fmt)+1, 1)
1347       EmitMemCpy(CI->getOperand(1), CI->getOperand(2), // Copy the nul byte.
1348           ConstantInt::get(TD->getIntPtrType(*Context), FormatStr.size()+1),1,B);
1349       return ConstantInt::get(CI->getType(), FormatStr.size());
1350     }
1351
1352     // The remaining optimizations require the format string to be "%s" or "%c"
1353     // and have an extra operand.
1354     if (FormatStr.size() != 2 || FormatStr[0] != '%' || CI->getNumOperands() <4)
1355       return 0;
1356
1357     // Decode the second character of the format string.
1358     if (FormatStr[1] == 'c') {
1359       // sprintf(dst, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0
1360       if (!isa<IntegerType>(CI->getOperand(3)->getType())) return 0;
1361       Value *V = B.CreateTrunc(CI->getOperand(3), Type::getInt8Ty(*Context), "char");
1362       Value *Ptr = CastToCStr(CI->getOperand(1), B);
1363       B.CreateStore(V, Ptr);
1364       Ptr = B.CreateGEP(Ptr, ConstantInt::get(Type::getInt32Ty(*Context), 1), "nul");
1365       B.CreateStore(Constant::getNullValue(Type::getInt8Ty(*Context)), Ptr);
1366
1367       return ConstantInt::get(CI->getType(), 1);
1368     }
1369
1370     if (FormatStr[1] == 's') {
1371       // These optimizations require TargetData.
1372       if (!TD) return 0;
1373
1374       // sprintf(dest, "%s", str) -> llvm.memcpy(dest, str, strlen(str)+1, 1)
1375       if (!isa<PointerType>(CI->getOperand(3)->getType())) return 0;
1376
1377       Value *Len = EmitStrLen(CI->getOperand(3), B);
1378       Value *IncLen = B.CreateAdd(Len,
1379                                   ConstantInt::get(Len->getType(), 1),
1380                                   "leninc");
1381       EmitMemCpy(CI->getOperand(1), CI->getOperand(3), IncLen, 1, B);
1382
1383       // The sprintf result is the unincremented number of bytes in the string.
1384       return B.CreateIntCast(Len, CI->getType(), false);
1385     }
1386     return 0;
1387   }
1388 };
1389
1390 //===---------------------------------------===//
1391 // 'fwrite' Optimizations
1392
1393 struct FWriteOpt : public LibCallOptimization {
1394   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1395     // Require a pointer, an integer, an integer, a pointer, returning integer.
1396     const FunctionType *FT = Callee->getFunctionType();
1397     if (FT->getNumParams() != 4 || !isa<PointerType>(FT->getParamType(0)) ||
1398         !isa<IntegerType>(FT->getParamType(1)) ||
1399         !isa<IntegerType>(FT->getParamType(2)) ||
1400         !isa<PointerType>(FT->getParamType(3)) ||
1401         !isa<IntegerType>(FT->getReturnType()))
1402       return 0;
1403
1404     // Get the element size and count.
1405     ConstantInt *SizeC = dyn_cast<ConstantInt>(CI->getOperand(2));
1406     ConstantInt *CountC = dyn_cast<ConstantInt>(CI->getOperand(3));
1407     if (!SizeC || !CountC) return 0;
1408     uint64_t Bytes = SizeC->getZExtValue()*CountC->getZExtValue();
1409
1410     // If this is writing zero records, remove the call (it's a noop).
1411     if (Bytes == 0)
1412       return ConstantInt::get(CI->getType(), 0);
1413
1414     // If this is writing one byte, turn it into fputc.
1415     if (Bytes == 1) {  // fwrite(S,1,1,F) -> fputc(S[0],F)
1416       Value *Char = B.CreateLoad(CastToCStr(CI->getOperand(1), B), "char");
1417       EmitFPutC(Char, CI->getOperand(4), B);
1418       return ConstantInt::get(CI->getType(), 1);
1419     }
1420
1421     return 0;
1422   }
1423 };
1424
1425 //===---------------------------------------===//
1426 // 'fputs' Optimizations
1427
1428 struct FPutsOpt : public LibCallOptimization {
1429   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1430     // These optimizations require TargetData.
1431     if (!TD) return 0;
1432
1433     // Require two pointers.  Also, we can't optimize if return value is used.
1434     const FunctionType *FT = Callee->getFunctionType();
1435     if (FT->getNumParams() != 2 || !isa<PointerType>(FT->getParamType(0)) ||
1436         !isa<PointerType>(FT->getParamType(1)) ||
1437         !CI->use_empty())
1438       return 0;
1439
1440     // fputs(s,F) --> fwrite(s,1,strlen(s),F)
1441     uint64_t Len = GetStringLength(CI->getOperand(1));
1442     if (!Len) return 0;
1443     EmitFWrite(CI->getOperand(1),
1444                ConstantInt::get(TD->getIntPtrType(*Context), Len-1),
1445                CI->getOperand(2), B);
1446     return CI;  // Known to have no uses (see above).
1447   }
1448 };
1449
1450 //===---------------------------------------===//
1451 // 'fprintf' Optimizations
1452
1453 struct FPrintFOpt : public LibCallOptimization {
1454   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1455     // Require two fixed paramters as pointers and integer result.
1456     const FunctionType *FT = Callee->getFunctionType();
1457     if (FT->getNumParams() != 2 || !isa<PointerType>(FT->getParamType(0)) ||
1458         !isa<PointerType>(FT->getParamType(1)) ||
1459         !isa<IntegerType>(FT->getReturnType()))
1460       return 0;
1461
1462     // All the optimizations depend on the format string.
1463     std::string FormatStr;
1464     if (!GetConstantStringInfo(CI->getOperand(2), FormatStr))
1465       return 0;
1466
1467     // fprintf(F, "foo") --> fwrite("foo", 3, 1, F)
1468     if (CI->getNumOperands() == 3) {
1469       for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1470         if (FormatStr[i] == '%')  // Could handle %% -> % if we cared.
1471           return 0; // We found a format specifier.
1472
1473       // These optimizations require TargetData.
1474       if (!TD) return 0;
1475
1476       EmitFWrite(CI->getOperand(2), ConstantInt::get(TD->getIntPtrType(*Context),
1477                                                      FormatStr.size()),
1478                  CI->getOperand(1), B);
1479       return ConstantInt::get(CI->getType(), FormatStr.size());
1480     }
1481
1482     // The remaining optimizations require the format string to be "%s" or "%c"
1483     // and have an extra operand.
1484     if (FormatStr.size() != 2 || FormatStr[0] != '%' || CI->getNumOperands() <4)
1485       return 0;
1486
1487     // Decode the second character of the format string.
1488     if (FormatStr[1] == 'c') {
1489       // fprintf(F, "%c", chr) --> *(i8*)dst = chr
1490       if (!isa<IntegerType>(CI->getOperand(3)->getType())) return 0;
1491       EmitFPutC(CI->getOperand(3), CI->getOperand(1), B);
1492       return ConstantInt::get(CI->getType(), 1);
1493     }
1494
1495     if (FormatStr[1] == 's') {
1496       // fprintf(F, "%s", str) -> fputs(str, F)
1497       if (!isa<PointerType>(CI->getOperand(3)->getType()) || !CI->use_empty())
1498         return 0;
1499       EmitFPutS(CI->getOperand(3), CI->getOperand(1), B);
1500       return CI;
1501     }
1502     return 0;
1503   }
1504 };
1505
1506 } // end anonymous namespace.
1507
1508 //===----------------------------------------------------------------------===//
1509 // SimplifyLibCalls Pass Implementation
1510 //===----------------------------------------------------------------------===//
1511
1512 namespace {
1513   /// This pass optimizes well known library functions from libc and libm.
1514   ///
1515   class SimplifyLibCalls : public FunctionPass {
1516     StringMap<LibCallOptimization*> Optimizations;
1517     // String and Memory LibCall Optimizations
1518     StrCatOpt StrCat; StrNCatOpt StrNCat; StrChrOpt StrChr; StrCmpOpt StrCmp;
1519     StrNCmpOpt StrNCmp; StrCpyOpt StrCpy; StrNCpyOpt StrNCpy; StrLenOpt StrLen;
1520     StrToOpt StrTo; MemCmpOpt MemCmp; MemCpyOpt MemCpy; MemMoveOpt MemMove;
1521     MemSetOpt MemSet;
1522     // Math Library Optimizations
1523     PowOpt Pow; Exp2Opt Exp2; UnaryDoubleFPOpt UnaryDoubleFP;
1524     // Integer Optimizations
1525     FFSOpt FFS; AbsOpt Abs; IsDigitOpt IsDigit; IsAsciiOpt IsAscii;
1526     ToAsciiOpt ToAscii;
1527     // Formatting and IO Optimizations
1528     SPrintFOpt SPrintF; PrintFOpt PrintF;
1529     FWriteOpt FWrite; FPutsOpt FPuts; FPrintFOpt FPrintF;
1530
1531     bool Modified;  // This is only used by doInitialization.
1532   public:
1533     static char ID; // Pass identification
1534     SimplifyLibCalls() : FunctionPass(&ID) {}
1535
1536     void InitOptimizations();
1537     bool runOnFunction(Function &F);
1538
1539     void setDoesNotAccessMemory(Function &F);
1540     void setOnlyReadsMemory(Function &F);
1541     void setDoesNotThrow(Function &F);
1542     void setDoesNotCapture(Function &F, unsigned n);
1543     void setDoesNotAlias(Function &F, unsigned n);
1544     bool doInitialization(Module &M);
1545
1546     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1547     }
1548   };
1549   char SimplifyLibCalls::ID = 0;
1550 } // end anonymous namespace.
1551
1552 static RegisterPass<SimplifyLibCalls>
1553 X("simplify-libcalls", "Simplify well-known library calls");
1554
1555 // Public interface to the Simplify LibCalls pass.
1556 FunctionPass *llvm::createSimplifyLibCallsPass() {
1557   return new SimplifyLibCalls();
1558 }
1559
1560 /// Optimizations - Populate the Optimizations map with all the optimizations
1561 /// we know.
1562 void SimplifyLibCalls::InitOptimizations() {
1563   // String and Memory LibCall Optimizations
1564   Optimizations["strcat"] = &StrCat;
1565   Optimizations["strncat"] = &StrNCat;
1566   Optimizations["strchr"] = &StrChr;
1567   Optimizations["strcmp"] = &StrCmp;
1568   Optimizations["strncmp"] = &StrNCmp;
1569   Optimizations["strcpy"] = &StrCpy;
1570   Optimizations["strncpy"] = &StrNCpy;
1571   Optimizations["strlen"] = &StrLen;
1572   Optimizations["strtol"] = &StrTo;
1573   Optimizations["strtod"] = &StrTo;
1574   Optimizations["strtof"] = &StrTo;
1575   Optimizations["strtoul"] = &StrTo;
1576   Optimizations["strtoll"] = &StrTo;
1577   Optimizations["strtold"] = &StrTo;
1578   Optimizations["strtoull"] = &StrTo;
1579   Optimizations["memcmp"] = &MemCmp;
1580   Optimizations["memcpy"] = &MemCpy;
1581   Optimizations["memmove"] = &MemMove;
1582   Optimizations["memset"] = &MemSet;
1583
1584   // Math Library Optimizations
1585   Optimizations["powf"] = &Pow;
1586   Optimizations["pow"] = &Pow;
1587   Optimizations["powl"] = &Pow;
1588   Optimizations["llvm.pow.f32"] = &Pow;
1589   Optimizations["llvm.pow.f64"] = &Pow;
1590   Optimizations["llvm.pow.f80"] = &Pow;
1591   Optimizations["llvm.pow.f128"] = &Pow;
1592   Optimizations["llvm.pow.ppcf128"] = &Pow;
1593   Optimizations["exp2l"] = &Exp2;
1594   Optimizations["exp2"] = &Exp2;
1595   Optimizations["exp2f"] = &Exp2;
1596   Optimizations["llvm.exp2.ppcf128"] = &Exp2;
1597   Optimizations["llvm.exp2.f128"] = &Exp2;
1598   Optimizations["llvm.exp2.f80"] = &Exp2;
1599   Optimizations["llvm.exp2.f64"] = &Exp2;
1600   Optimizations["llvm.exp2.f32"] = &Exp2;
1601
1602 #ifdef HAVE_FLOORF
1603   Optimizations["floor"] = &UnaryDoubleFP;
1604 #endif
1605 #ifdef HAVE_CEILF
1606   Optimizations["ceil"] = &UnaryDoubleFP;
1607 #endif
1608 #ifdef HAVE_ROUNDF
1609   Optimizations["round"] = &UnaryDoubleFP;
1610 #endif
1611 #ifdef HAVE_RINTF
1612   Optimizations["rint"] = &UnaryDoubleFP;
1613 #endif
1614 #ifdef HAVE_NEARBYINTF
1615   Optimizations["nearbyint"] = &UnaryDoubleFP;
1616 #endif
1617
1618   // Integer Optimizations
1619   Optimizations["ffs"] = &FFS;
1620   Optimizations["ffsl"] = &FFS;
1621   Optimizations["ffsll"] = &FFS;
1622   Optimizations["abs"] = &Abs;
1623   Optimizations["labs"] = &Abs;
1624   Optimizations["llabs"] = &Abs;
1625   Optimizations["isdigit"] = &IsDigit;
1626   Optimizations["isascii"] = &IsAscii;
1627   Optimizations["toascii"] = &ToAscii;
1628
1629   // Formatting and IO Optimizations
1630   Optimizations["sprintf"] = &SPrintF;
1631   Optimizations["printf"] = &PrintF;
1632   Optimizations["fwrite"] = &FWrite;
1633   Optimizations["fputs"] = &FPuts;
1634   Optimizations["fprintf"] = &FPrintF;
1635 }
1636
1637
1638 /// runOnFunction - Top level algorithm.
1639 ///
1640 bool SimplifyLibCalls::runOnFunction(Function &F) {
1641   if (Optimizations.empty())
1642     InitOptimizations();
1643
1644   const TargetData *TD = getAnalysisIfAvailable<TargetData>();
1645
1646   IRBuilder<> Builder(F.getContext());
1647
1648   bool Changed = false;
1649   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
1650     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
1651       // Ignore non-calls.
1652       CallInst *CI = dyn_cast<CallInst>(I++);
1653       if (!CI) continue;
1654
1655       // Ignore indirect calls and calls to non-external functions.
1656       Function *Callee = CI->getCalledFunction();
1657       if (Callee == 0 || !Callee->isDeclaration() ||
1658           !(Callee->hasExternalLinkage() || Callee->hasDLLImportLinkage()))
1659         continue;
1660
1661       // Ignore unknown calls.
1662       LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
1663       if (!LCO) continue;
1664
1665       // Set the builder to the instruction after the call.
1666       Builder.SetInsertPoint(BB, I);
1667
1668       // Try to optimize this call.
1669       Value *Result = LCO->OptimizeCall(CI, TD, Builder);
1670       if (Result == 0) continue;
1671
1672       DEBUG(errs() << "SimplifyLibCalls simplified: " << *CI;
1673             errs() << "  into: " << *Result << "\n");
1674
1675       // Something changed!
1676       Changed = true;
1677       ++NumSimplified;
1678
1679       // Inspect the instruction after the call (which was potentially just
1680       // added) next.
1681       I = CI; ++I;
1682
1683       if (CI != Result && !CI->use_empty()) {
1684         CI->replaceAllUsesWith(Result);
1685         if (!Result->hasName())
1686           Result->takeName(CI);
1687       }
1688       CI->eraseFromParent();
1689     }
1690   }
1691   return Changed;
1692 }
1693
1694 // Utility methods for doInitialization.
1695
1696 void SimplifyLibCalls::setDoesNotAccessMemory(Function &F) {
1697   if (!F.doesNotAccessMemory()) {
1698     F.setDoesNotAccessMemory();
1699     ++NumAnnotated;
1700     Modified = true;
1701   }
1702 }
1703 void SimplifyLibCalls::setOnlyReadsMemory(Function &F) {
1704   if (!F.onlyReadsMemory()) {
1705     F.setOnlyReadsMemory();
1706     ++NumAnnotated;
1707     Modified = true;
1708   }
1709 }
1710 void SimplifyLibCalls::setDoesNotThrow(Function &F) {
1711   if (!F.doesNotThrow()) {
1712     F.setDoesNotThrow();
1713     ++NumAnnotated;
1714     Modified = true;
1715   }
1716 }
1717 void SimplifyLibCalls::setDoesNotCapture(Function &F, unsigned n) {
1718   if (!F.doesNotCapture(n)) {
1719     F.setDoesNotCapture(n);
1720     ++NumAnnotated;
1721     Modified = true;
1722   }
1723 }
1724 void SimplifyLibCalls::setDoesNotAlias(Function &F, unsigned n) {
1725   if (!F.doesNotAlias(n)) {
1726     F.setDoesNotAlias(n);
1727     ++NumAnnotated;
1728     Modified = true;
1729   }
1730 }
1731
1732 /// doInitialization - Add attributes to well-known functions.
1733 ///
1734 bool SimplifyLibCalls::doInitialization(Module &M) {
1735   Modified = false;
1736   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
1737     Function &F = *I;
1738     if (!F.isDeclaration())
1739       continue;
1740
1741     if (!F.hasName())
1742       continue;
1743
1744     const FunctionType *FTy = F.getFunctionType();
1745
1746     StringRef Name = F.getName();
1747     switch (Name[0]) {
1748       case 's':
1749         if (Name == "strlen") {
1750           if (FTy->getNumParams() != 1 ||
1751               !isa<PointerType>(FTy->getParamType(0)))
1752             continue;
1753           setOnlyReadsMemory(F);
1754           setDoesNotThrow(F);
1755           setDoesNotCapture(F, 1);
1756         } else if (Name == "strcpy" ||
1757                    Name == "stpcpy" ||
1758                    Name == "strcat" ||
1759                    Name == "strtol" ||
1760                    Name == "strtod" ||
1761                    Name == "strtof" ||
1762                    Name == "strtoul" ||
1763                    Name == "strtoll" ||
1764                    Name == "strtold" ||
1765                    Name == "strncat" ||
1766                    Name == "strncpy" ||
1767                    Name == "strtoull") {
1768           if (FTy->getNumParams() < 2 ||
1769               !isa<PointerType>(FTy->getParamType(1)))
1770             continue;
1771           setDoesNotThrow(F);
1772           setDoesNotCapture(F, 2);
1773         } else if (Name == "strxfrm") {
1774           if (FTy->getNumParams() != 3 ||
1775               !isa<PointerType>(FTy->getParamType(0)) ||
1776               !isa<PointerType>(FTy->getParamType(1)))
1777             continue;
1778           setDoesNotThrow(F);
1779           setDoesNotCapture(F, 1);
1780           setDoesNotCapture(F, 2);
1781         } else if (Name == "strcmp" ||
1782                    Name == "strspn" ||
1783                    Name == "strncmp" ||
1784                    Name ==" strcspn" ||
1785                    Name == "strcoll" ||
1786                    Name == "strcasecmp" ||
1787                    Name == "strncasecmp") {
1788           if (FTy->getNumParams() < 2 ||
1789               !isa<PointerType>(FTy->getParamType(0)) ||
1790               !isa<PointerType>(FTy->getParamType(1)))
1791             continue;
1792           setOnlyReadsMemory(F);
1793           setDoesNotThrow(F);
1794           setDoesNotCapture(F, 1);
1795           setDoesNotCapture(F, 2);
1796         } else if (Name == "strstr" ||
1797                    Name == "strpbrk") {
1798           if (FTy->getNumParams() != 2 ||
1799               !isa<PointerType>(FTy->getParamType(1)))
1800             continue;
1801           setOnlyReadsMemory(F);
1802           setDoesNotThrow(F);
1803           setDoesNotCapture(F, 2);
1804         } else if (Name == "strtok" ||
1805                    Name == "strtok_r") {
1806           if (FTy->getNumParams() < 2 ||
1807               !isa<PointerType>(FTy->getParamType(1)))
1808             continue;
1809           setDoesNotThrow(F);
1810           setDoesNotCapture(F, 2);
1811         } else if (Name == "scanf" ||
1812                    Name == "setbuf" ||
1813                    Name == "setvbuf") {
1814           if (FTy->getNumParams() < 1 ||
1815               !isa<PointerType>(FTy->getParamType(0)))
1816             continue;
1817           setDoesNotThrow(F);
1818           setDoesNotCapture(F, 1);
1819         } else if (Name == "strdup" ||
1820                    Name == "strndup") {
1821           if (FTy->getNumParams() < 1 ||
1822               !isa<PointerType>(FTy->getReturnType()) ||
1823               !isa<PointerType>(FTy->getParamType(0)))
1824             continue;
1825           setDoesNotThrow(F);
1826           setDoesNotAlias(F, 0);
1827           setDoesNotCapture(F, 1);
1828         } else if (Name == "stat" ||
1829                    Name == "sscanf" ||
1830                    Name == "sprintf" ||
1831                    Name == "statvfs") {
1832           if (FTy->getNumParams() < 2 ||
1833               !isa<PointerType>(FTy->getParamType(0)) ||
1834               !isa<PointerType>(FTy->getParamType(1)))
1835             continue;
1836           setDoesNotThrow(F);
1837           setDoesNotCapture(F, 1);
1838           setDoesNotCapture(F, 2);
1839         } else if (Name == "snprintf") {
1840           if (FTy->getNumParams() != 3 ||
1841               !isa<PointerType>(FTy->getParamType(0)) ||
1842               !isa<PointerType>(FTy->getParamType(2)))
1843             continue;
1844           setDoesNotThrow(F);
1845           setDoesNotCapture(F, 1);
1846           setDoesNotCapture(F, 3);
1847         } else if (Name == "setitimer") {
1848           if (FTy->getNumParams() != 3 ||
1849               !isa<PointerType>(FTy->getParamType(1)) ||
1850               !isa<PointerType>(FTy->getParamType(2)))
1851             continue;
1852           setDoesNotThrow(F);
1853           setDoesNotCapture(F, 2);
1854           setDoesNotCapture(F, 3);
1855         } else if (Name == "system") {
1856           if (FTy->getNumParams() != 1 ||
1857               !isa<PointerType>(FTy->getParamType(0)))
1858             continue;
1859           // May throw; "system" is a valid pthread cancellation point.
1860           setDoesNotCapture(F, 1);
1861         }
1862         break;
1863       case 'm':
1864         if (Name == "malloc") {
1865           if (FTy->getNumParams() != 1 ||
1866               !isa<PointerType>(FTy->getReturnType()))
1867             continue;
1868           setDoesNotThrow(F);
1869           setDoesNotAlias(F, 0);
1870         } else if (Name == "memcmp") {
1871           if (FTy->getNumParams() != 3 ||
1872               !isa<PointerType>(FTy->getParamType(0)) ||
1873               !isa<PointerType>(FTy->getParamType(1)))
1874             continue;
1875           setOnlyReadsMemory(F);
1876           setDoesNotThrow(F);
1877           setDoesNotCapture(F, 1);
1878           setDoesNotCapture(F, 2);
1879         } else if (Name == "memchr" ||
1880                    Name == "memrchr") {
1881           if (FTy->getNumParams() != 3)
1882             continue;
1883           setOnlyReadsMemory(F);
1884           setDoesNotThrow(F);
1885         } else if (Name == "modf" ||
1886                    Name == "modff" ||
1887                    Name == "modfl" ||
1888                    Name == "memcpy" ||
1889                    Name == "memccpy" ||
1890                    Name == "memmove") {
1891           if (FTy->getNumParams() < 2 ||
1892               !isa<PointerType>(FTy->getParamType(1)))
1893             continue;
1894           setDoesNotThrow(F);
1895           setDoesNotCapture(F, 2);
1896         } else if (Name == "memalign") {
1897           if (!isa<PointerType>(FTy->getReturnType()))
1898             continue;
1899           setDoesNotAlias(F, 0);
1900         } else if (Name == "mkdir" ||
1901                    Name == "mktime") {
1902           if (FTy->getNumParams() == 0 ||
1903               !isa<PointerType>(FTy->getParamType(0)))
1904             continue;
1905           setDoesNotThrow(F);
1906           setDoesNotCapture(F, 1);
1907         }
1908         break;
1909       case 'r':
1910         if (Name == "realloc") {
1911           if (FTy->getNumParams() != 2 ||
1912               !isa<PointerType>(FTy->getParamType(0)) ||
1913               !isa<PointerType>(FTy->getReturnType()))
1914             continue;
1915           setDoesNotThrow(F);
1916           setDoesNotAlias(F, 0);
1917           setDoesNotCapture(F, 1);
1918         } else if (Name == "read") {
1919           if (FTy->getNumParams() != 3 ||
1920               !isa<PointerType>(FTy->getParamType(1)))
1921             continue;
1922           // May throw; "read" is a valid pthread cancellation point.
1923           setDoesNotCapture(F, 2);
1924         } else if (Name == "rmdir" ||
1925                    Name == "rewind" ||
1926                    Name == "remove" ||
1927                    Name == "realpath") {
1928           if (FTy->getNumParams() < 1 ||
1929               !isa<PointerType>(FTy->getParamType(0)))
1930             continue;
1931           setDoesNotThrow(F);
1932           setDoesNotCapture(F, 1);
1933         } else if (Name == "rename" ||
1934                    Name == "readlink") {
1935           if (FTy->getNumParams() < 2 ||
1936               !isa<PointerType>(FTy->getParamType(0)) ||
1937               !isa<PointerType>(FTy->getParamType(1)))
1938             continue;
1939           setDoesNotThrow(F);
1940           setDoesNotCapture(F, 1);
1941           setDoesNotCapture(F, 2);
1942         }
1943         break;
1944       case 'w':
1945         if (Name == "write") {
1946           if (FTy->getNumParams() != 3 ||
1947               !isa<PointerType>(FTy->getParamType(1)))
1948             continue;
1949           // May throw; "write" is a valid pthread cancellation point.
1950           setDoesNotCapture(F, 2);
1951         }
1952         break;
1953       case 'b':
1954         if (Name == "bcopy") {
1955           if (FTy->getNumParams() != 3 ||
1956               !isa<PointerType>(FTy->getParamType(0)) ||
1957               !isa<PointerType>(FTy->getParamType(1)))
1958             continue;
1959           setDoesNotThrow(F);
1960           setDoesNotCapture(F, 1);
1961           setDoesNotCapture(F, 2);
1962         } else if (Name == "bcmp") {
1963           if (FTy->getNumParams() != 3 ||
1964               !isa<PointerType>(FTy->getParamType(0)) ||
1965               !isa<PointerType>(FTy->getParamType(1)))
1966             continue;
1967           setDoesNotThrow(F);
1968           setOnlyReadsMemory(F);
1969           setDoesNotCapture(F, 1);
1970           setDoesNotCapture(F, 2);
1971         } else if (Name == "bzero") {
1972           if (FTy->getNumParams() != 2 ||
1973               !isa<PointerType>(FTy->getParamType(0)))
1974             continue;
1975           setDoesNotThrow(F);
1976           setDoesNotCapture(F, 1);
1977         }
1978         break;
1979       case 'c':
1980         if (Name == "calloc") {
1981           if (FTy->getNumParams() != 2 ||
1982               !isa<PointerType>(FTy->getReturnType()))
1983             continue;
1984           setDoesNotThrow(F);
1985           setDoesNotAlias(F, 0);
1986         } else if (Name == "chmod" ||
1987                    Name == "chown" ||
1988                    Name == "ctermid" ||
1989                    Name == "clearerr" ||
1990                    Name == "closedir") {
1991           if (FTy->getNumParams() == 0 ||
1992               !isa<PointerType>(FTy->getParamType(0)))
1993             continue;
1994           setDoesNotThrow(F);
1995           setDoesNotCapture(F, 1);
1996         }
1997         break;
1998       case 'a':
1999         if (Name == "atoi" ||
2000             Name == "atol" ||
2001             Name == "atof" ||
2002             Name == "atoll") {
2003           if (FTy->getNumParams() != 1 ||
2004               !isa<PointerType>(FTy->getParamType(0)))
2005             continue;
2006           setDoesNotThrow(F);
2007           setOnlyReadsMemory(F);
2008           setDoesNotCapture(F, 1);
2009         } else if (Name == "access") {
2010           if (FTy->getNumParams() != 2 ||
2011               !isa<PointerType>(FTy->getParamType(0)))
2012             continue;
2013           setDoesNotThrow(F);
2014           setDoesNotCapture(F, 1);
2015         }
2016         break;
2017       case 'f':
2018         if (Name == "fopen") {
2019           if (FTy->getNumParams() != 2 ||
2020               !isa<PointerType>(FTy->getReturnType()) ||
2021               !isa<PointerType>(FTy->getParamType(0)) ||
2022               !isa<PointerType>(FTy->getParamType(1)))
2023             continue;
2024           setDoesNotThrow(F);
2025           setDoesNotAlias(F, 0);
2026           setDoesNotCapture(F, 1);
2027           setDoesNotCapture(F, 2);
2028         } else if (Name == "fdopen") {
2029           if (FTy->getNumParams() != 2 ||
2030               !isa<PointerType>(FTy->getReturnType()) ||
2031               !isa<PointerType>(FTy->getParamType(1)))
2032             continue;
2033           setDoesNotThrow(F);
2034           setDoesNotAlias(F, 0);
2035           setDoesNotCapture(F, 2);
2036         } else if (Name == "feof" ||
2037                    Name == "free" ||
2038                    Name == "fseek" ||
2039                    Name == "ftell" ||
2040                    Name == "fgetc" ||
2041                    Name == "fseeko" ||
2042                    Name == "ftello" ||
2043                    Name == "fileno" ||
2044                    Name == "fflush" ||
2045                    Name == "fclose" ||
2046                    Name == "fsetpos" ||
2047                    Name == "flockfile" ||
2048                    Name == "funlockfile" ||
2049                    Name == "ftrylockfile") {
2050           if (FTy->getNumParams() == 0 ||
2051               !isa<PointerType>(FTy->getParamType(0)))
2052             continue;
2053           setDoesNotThrow(F);
2054           setDoesNotCapture(F, 1);
2055         } else if (Name == "ferror") {
2056           if (FTy->getNumParams() != 1 ||
2057               !isa<PointerType>(FTy->getParamType(0)))
2058             continue;
2059           setDoesNotThrow(F);
2060           setDoesNotCapture(F, 1);
2061           setOnlyReadsMemory(F);
2062         } else if (Name == "fputc" ||
2063                    Name == "fstat" ||
2064                    Name == "frexp" ||
2065                    Name == "frexpf" ||
2066                    Name == "frexpl" ||
2067                    Name == "fstatvfs") {
2068           if (FTy->getNumParams() != 2 ||
2069               !isa<PointerType>(FTy->getParamType(1)))
2070             continue;
2071           setDoesNotThrow(F);
2072           setDoesNotCapture(F, 2);
2073         } else if (Name == "fgets") {
2074           if (FTy->getNumParams() != 3 ||
2075               !isa<PointerType>(FTy->getParamType(0)) ||
2076               !isa<PointerType>(FTy->getParamType(2)))
2077             continue;
2078           setDoesNotThrow(F);
2079           setDoesNotCapture(F, 3);
2080         } else if (Name == "fread" ||
2081                    Name == "fwrite") {
2082           if (FTy->getNumParams() != 4 ||
2083               !isa<PointerType>(FTy->getParamType(0)) ||
2084               !isa<PointerType>(FTy->getParamType(3)))
2085             continue;
2086           setDoesNotThrow(F);
2087           setDoesNotCapture(F, 1);
2088           setDoesNotCapture(F, 4);
2089         } else if (Name == "fputs" ||
2090                    Name == "fscanf" ||
2091                    Name == "fprintf" ||
2092                    Name == "fgetpos") {
2093           if (FTy->getNumParams() < 2 ||
2094               !isa<PointerType>(FTy->getParamType(0)) ||
2095               !isa<PointerType>(FTy->getParamType(1)))
2096             continue;
2097           setDoesNotThrow(F);
2098           setDoesNotCapture(F, 1);
2099           setDoesNotCapture(F, 2);
2100         }
2101         break;
2102       case 'g':
2103         if (Name == "getc" ||
2104             Name == "getlogin_r" ||
2105             Name == "getc_unlocked") {
2106           if (FTy->getNumParams() == 0 ||
2107               !isa<PointerType>(FTy->getParamType(0)))
2108             continue;
2109           setDoesNotThrow(F);
2110           setDoesNotCapture(F, 1);
2111         } else if (Name == "getenv") {
2112           if (FTy->getNumParams() != 1 ||
2113               !isa<PointerType>(FTy->getParamType(0)))
2114             continue;
2115           setDoesNotThrow(F);
2116           setOnlyReadsMemory(F);
2117           setDoesNotCapture(F, 1);
2118         } else if (Name == "gets" ||
2119                    Name == "getchar") {
2120           setDoesNotThrow(F);
2121         } else if (Name == "getitimer") {
2122           if (FTy->getNumParams() != 2 ||
2123               !isa<PointerType>(FTy->getParamType(1)))
2124             continue;
2125           setDoesNotThrow(F);
2126           setDoesNotCapture(F, 2);
2127         } else if (Name == "getpwnam") {
2128           if (FTy->getNumParams() != 1 ||
2129               !isa<PointerType>(FTy->getParamType(0)))
2130             continue;
2131           setDoesNotThrow(F);
2132           setDoesNotCapture(F, 1);
2133         }
2134         break;
2135       case 'u':
2136         if (Name == "ungetc") {
2137           if (FTy->getNumParams() != 2 ||
2138               !isa<PointerType>(FTy->getParamType(1)))
2139             continue;
2140           setDoesNotThrow(F);
2141           setDoesNotCapture(F, 2);
2142         } else if (Name == "uname" ||
2143                    Name == "unlink" ||
2144                    Name == "unsetenv") {
2145           if (FTy->getNumParams() != 1 ||
2146               !isa<PointerType>(FTy->getParamType(0)))
2147             continue;
2148           setDoesNotThrow(F);
2149           setDoesNotCapture(F, 1);
2150         } else if (Name == "utime" ||
2151                    Name == "utimes") {
2152           if (FTy->getNumParams() != 2 ||
2153               !isa<PointerType>(FTy->getParamType(0)) ||
2154               !isa<PointerType>(FTy->getParamType(1)))
2155             continue;
2156           setDoesNotThrow(F);
2157           setDoesNotCapture(F, 1);
2158           setDoesNotCapture(F, 2);
2159         }
2160         break;
2161       case 'p':
2162         if (Name == "putc") {
2163           if (FTy->getNumParams() != 2 ||
2164               !isa<PointerType>(FTy->getParamType(1)))
2165             continue;
2166           setDoesNotThrow(F);
2167           setDoesNotCapture(F, 2);
2168         } else if (Name == "puts" ||
2169                    Name == "printf" ||
2170                    Name == "perror") {
2171           if (FTy->getNumParams() != 1 ||
2172               !isa<PointerType>(FTy->getParamType(0)))
2173             continue;
2174           setDoesNotThrow(F);
2175           setDoesNotCapture(F, 1);
2176         } else if (Name == "pread" ||
2177                    Name == "pwrite") {
2178           if (FTy->getNumParams() != 4 ||
2179               !isa<PointerType>(FTy->getParamType(1)))
2180             continue;
2181           // May throw; these are valid pthread cancellation points.
2182           setDoesNotCapture(F, 2);
2183         } else if (Name == "putchar") {
2184           setDoesNotThrow(F);
2185         } else if (Name == "popen") {
2186           if (FTy->getNumParams() != 2 ||
2187               !isa<PointerType>(FTy->getReturnType()) ||
2188               !isa<PointerType>(FTy->getParamType(0)) ||
2189               !isa<PointerType>(FTy->getParamType(1)))
2190             continue;
2191           setDoesNotThrow(F);
2192           setDoesNotAlias(F, 0);
2193           setDoesNotCapture(F, 1);
2194           setDoesNotCapture(F, 2);
2195         } else if (Name == "pclose") {
2196           if (FTy->getNumParams() != 1 ||
2197               !isa<PointerType>(FTy->getParamType(0)))
2198             continue;
2199           setDoesNotThrow(F);
2200           setDoesNotCapture(F, 1);
2201         }
2202         break;
2203       case 'v':
2204         if (Name == "vscanf") {
2205           if (FTy->getNumParams() != 2 ||
2206               !isa<PointerType>(FTy->getParamType(1)))
2207             continue;
2208           setDoesNotThrow(F);
2209           setDoesNotCapture(F, 1);
2210         } else if (Name == "vsscanf" ||
2211                    Name == "vfscanf") {
2212           if (FTy->getNumParams() != 3 ||
2213               !isa<PointerType>(FTy->getParamType(1)) ||
2214               !isa<PointerType>(FTy->getParamType(2)))
2215             continue;
2216           setDoesNotThrow(F);
2217           setDoesNotCapture(F, 1);
2218           setDoesNotCapture(F, 2);
2219         } else if (Name == "valloc") {
2220           if (!isa<PointerType>(FTy->getReturnType()))
2221             continue;
2222           setDoesNotThrow(F);
2223           setDoesNotAlias(F, 0);
2224         } else if (Name == "vprintf") {
2225           if (FTy->getNumParams() != 2 ||
2226               !isa<PointerType>(FTy->getParamType(0)))
2227             continue;
2228           setDoesNotThrow(F);
2229           setDoesNotCapture(F, 1);
2230         } else if (Name == "vfprintf" ||
2231                    Name == "vsprintf") {
2232           if (FTy->getNumParams() != 3 ||
2233               !isa<PointerType>(FTy->getParamType(0)) ||
2234               !isa<PointerType>(FTy->getParamType(1)))
2235             continue;
2236           setDoesNotThrow(F);
2237           setDoesNotCapture(F, 1);
2238           setDoesNotCapture(F, 2);
2239         } else if (Name == "vsnprintf") {
2240           if (FTy->getNumParams() != 4 ||
2241               !isa<PointerType>(FTy->getParamType(0)) ||
2242               !isa<PointerType>(FTy->getParamType(2)))
2243             continue;
2244           setDoesNotThrow(F);
2245           setDoesNotCapture(F, 1);
2246           setDoesNotCapture(F, 3);
2247         }
2248         break;
2249       case 'o':
2250         if (Name == "open") {
2251           if (FTy->getNumParams() < 2 ||
2252               !isa<PointerType>(FTy->getParamType(0)))
2253             continue;
2254           // May throw; "open" is a valid pthread cancellation point.
2255           setDoesNotCapture(F, 1);
2256         } else if (Name == "opendir") {
2257           if (FTy->getNumParams() != 1 ||
2258               !isa<PointerType>(FTy->getReturnType()) ||
2259               !isa<PointerType>(FTy->getParamType(0)))
2260             continue;
2261           setDoesNotThrow(F);
2262           setDoesNotAlias(F, 0);
2263           setDoesNotCapture(F, 1);
2264         }
2265         break;
2266       case 't':
2267         if (Name == "tmpfile") {
2268           if (!isa<PointerType>(FTy->getReturnType()))
2269             continue;
2270           setDoesNotThrow(F);
2271           setDoesNotAlias(F, 0);
2272         } else if (Name == "times") {
2273           if (FTy->getNumParams() != 1 ||
2274               !isa<PointerType>(FTy->getParamType(0)))
2275             continue;
2276           setDoesNotThrow(F);
2277           setDoesNotCapture(F, 1);
2278         }
2279         break;
2280       case 'h':
2281         if (Name == "htonl" ||
2282             Name == "htons") {
2283           setDoesNotThrow(F);
2284           setDoesNotAccessMemory(F);
2285         }
2286         break;
2287       case 'n':
2288         if (Name == "ntohl" ||
2289             Name == "ntohs") {
2290           setDoesNotThrow(F);
2291           setDoesNotAccessMemory(F);
2292         }
2293         break;
2294       case 'l':
2295         if (Name == "lstat") {
2296           if (FTy->getNumParams() != 2 ||
2297               !isa<PointerType>(FTy->getParamType(0)) ||
2298               !isa<PointerType>(FTy->getParamType(1)))
2299             continue;
2300           setDoesNotThrow(F);
2301           setDoesNotCapture(F, 1);
2302           setDoesNotCapture(F, 2);
2303         } else if (Name == "lchown") {
2304           if (FTy->getNumParams() != 3 ||
2305               !isa<PointerType>(FTy->getParamType(0)))
2306             continue;
2307           setDoesNotThrow(F);
2308           setDoesNotCapture(F, 1);
2309         }
2310         break;
2311       case 'q':
2312         if (Name == "qsort") {
2313           if (FTy->getNumParams() != 4 ||
2314               !isa<PointerType>(FTy->getParamType(3)))
2315             continue;
2316           // May throw; places call through function pointer.
2317           setDoesNotCapture(F, 4);
2318         }
2319         break;
2320       case '_':
2321         if (Name == "__strdup" ||
2322             Name == "__strndup") {
2323           if (FTy->getNumParams() < 1 ||
2324               !isa<PointerType>(FTy->getReturnType()) ||
2325               !isa<PointerType>(FTy->getParamType(0)))
2326             continue;
2327           setDoesNotThrow(F);
2328           setDoesNotAlias(F, 0);
2329           setDoesNotCapture(F, 1);
2330         } else if (Name == "__strtok_r") {
2331           if (FTy->getNumParams() != 3 ||
2332               !isa<PointerType>(FTy->getParamType(1)))
2333             continue;
2334           setDoesNotThrow(F);
2335           setDoesNotCapture(F, 2);
2336         } else if (Name == "_IO_getc") {
2337           if (FTy->getNumParams() != 1 ||
2338               !isa<PointerType>(FTy->getParamType(0)))
2339             continue;
2340           setDoesNotThrow(F);
2341           setDoesNotCapture(F, 1);
2342         } else if (Name == "_IO_putc") {
2343           if (FTy->getNumParams() != 2 ||
2344               !isa<PointerType>(FTy->getParamType(1)))
2345             continue;
2346           setDoesNotThrow(F);
2347           setDoesNotCapture(F, 2);
2348         }
2349         break;
2350       case 1:
2351         if (Name == "\1__isoc99_scanf") {
2352           if (FTy->getNumParams() < 1 ||
2353               !isa<PointerType>(FTy->getParamType(0)))
2354             continue;
2355           setDoesNotThrow(F);
2356           setDoesNotCapture(F, 1);
2357         } else if (Name == "\1stat64" ||
2358                    Name == "\1lstat64" ||
2359                    Name == "\1statvfs64" ||
2360                    Name == "\1__isoc99_sscanf") {
2361           if (FTy->getNumParams() < 1 ||
2362               !isa<PointerType>(FTy->getParamType(0)) ||
2363               !isa<PointerType>(FTy->getParamType(1)))
2364             continue;
2365           setDoesNotThrow(F);
2366           setDoesNotCapture(F, 1);
2367           setDoesNotCapture(F, 2);
2368         } else if (Name == "\1fopen64") {
2369           if (FTy->getNumParams() != 2 ||
2370               !isa<PointerType>(FTy->getReturnType()) ||
2371               !isa<PointerType>(FTy->getParamType(0)) ||
2372               !isa<PointerType>(FTy->getParamType(1)))
2373             continue;
2374           setDoesNotThrow(F);
2375           setDoesNotAlias(F, 0);
2376           setDoesNotCapture(F, 1);
2377           setDoesNotCapture(F, 2);
2378         } else if (Name == "\1fseeko64" ||
2379                    Name == "\1ftello64") {
2380           if (FTy->getNumParams() == 0 ||
2381               !isa<PointerType>(FTy->getParamType(0)))
2382             continue;
2383           setDoesNotThrow(F);
2384           setDoesNotCapture(F, 1);
2385         } else if (Name == "\1tmpfile64") {
2386           if (!isa<PointerType>(FTy->getReturnType()))
2387             continue;
2388           setDoesNotThrow(F);
2389           setDoesNotAlias(F, 0);
2390         } else if (Name == "\1fstat64" ||
2391                    Name == "\1fstatvfs64") {
2392           if (FTy->getNumParams() != 2 ||
2393               !isa<PointerType>(FTy->getParamType(1)))
2394             continue;
2395           setDoesNotThrow(F);
2396           setDoesNotCapture(F, 2);
2397         } else if (Name == "\1open64") {
2398           if (FTy->getNumParams() < 2 ||
2399               !isa<PointerType>(FTy->getParamType(0)))
2400             continue;
2401           // May throw; "open" is a valid pthread cancellation point.
2402           setDoesNotCapture(F, 1);
2403         }
2404         break;
2405     }
2406   }
2407   return Modified;
2408 }
2409
2410 // TODO:
2411 //   Additional cases that we need to add to this file:
2412 //
2413 // cbrt:
2414 //   * cbrt(expN(X))  -> expN(x/3)
2415 //   * cbrt(sqrt(x))  -> pow(x,1/6)
2416 //   * cbrt(sqrt(x))  -> pow(x,1/9)
2417 //
2418 // cos, cosf, cosl:
2419 //   * cos(-x)  -> cos(x)
2420 //
2421 // exp, expf, expl:
2422 //   * exp(log(x))  -> x
2423 //
2424 // log, logf, logl:
2425 //   * log(exp(x))   -> x
2426 //   * log(x**y)     -> y*log(x)
2427 //   * log(exp(y))   -> y*log(e)
2428 //   * log(exp2(y))  -> y*log(2)
2429 //   * log(exp10(y)) -> y*log(10)
2430 //   * log(sqrt(x))  -> 0.5*log(x)
2431 //   * log(pow(x,y)) -> y*log(x)
2432 //
2433 // lround, lroundf, lroundl:
2434 //   * lround(cnst) -> cnst'
2435 //
2436 // memcmp:
2437 //   * memcmp(x,y,l)   -> cnst
2438 //      (if all arguments are constant and strlen(x) <= l and strlen(y) <= l)
2439 //
2440 // pow, powf, powl:
2441 //   * pow(exp(x),y)  -> exp(x*y)
2442 //   * pow(sqrt(x),y) -> pow(x,y*0.5)
2443 //   * pow(pow(x,y),z)-> pow(x,y*z)
2444 //
2445 // puts:
2446 //   * puts("") -> putchar("\n")
2447 //
2448 // round, roundf, roundl:
2449 //   * round(cnst) -> cnst'
2450 //
2451 // signbit:
2452 //   * signbit(cnst) -> cnst'
2453 //   * signbit(nncst) -> 0 (if pstv is a non-negative constant)
2454 //
2455 // sqrt, sqrtf, sqrtl:
2456 //   * sqrt(expN(x))  -> expN(x*0.5)
2457 //   * sqrt(Nroot(x)) -> pow(x,1/(2*N))
2458 //   * sqrt(pow(x,y)) -> pow(|x|,y*0.5)
2459 //
2460 // stpcpy:
2461 //   * stpcpy(str, "literal") ->
2462 //           llvm.memcpy(str,"literal",strlen("literal")+1,1)
2463 // strrchr:
2464 //   * strrchr(s,c) -> reverse_offset_of_in(c,s)
2465 //      (if c is a constant integer and s is a constant string)
2466 //   * strrchr(s1,0) -> strchr(s1,0)
2467 //
2468 // strpbrk:
2469 //   * strpbrk(s,a) -> offset_in_for(s,a)
2470 //      (if s and a are both constant strings)
2471 //   * strpbrk(s,"") -> 0
2472 //   * strpbrk(s,a) -> strchr(s,a[0]) (if a is constant string of length 1)
2473 //
2474 // strspn, strcspn:
2475 //   * strspn(s,a)   -> const_int (if both args are constant)
2476 //   * strspn("",a)  -> 0
2477 //   * strspn(s,"")  -> 0
2478 //   * strcspn(s,a)  -> const_int (if both args are constant)
2479 //   * strcspn("",a) -> 0
2480 //   * strcspn(s,"") -> strlen(a)
2481 //
2482 // strstr:
2483 //   * strstr(x,x)  -> x
2484 //   * strstr(s1,s2) -> offset_of_s2_in(s1)
2485 //       (if s1 and s2 are constant strings)
2486 //
2487 // tan, tanf, tanl:
2488 //   * tan(atan(x)) -> x
2489 //
2490 // trunc, truncf, truncl:
2491 //   * trunc(cnst) -> cnst'
2492 //
2493 //