lib/Transforms/Scalar/SimplifyLibCalls.cpp

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