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