lib/Transforms/Scalar/SimplifyLibCalls.cpp

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