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