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