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