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