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