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). For example, a call to the function "exit(3)" that
  13 // occurs within the main() function can be transformed into a simple "return 3"
  14 // instruction. Any optimization that takes this form (replace call to library
  15 // function with simpler code that provides the same result) belongs in this
  16 // file.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #define DEBUG_TYPE "simplify-libcalls"
  21 #include "llvm/Transforms/Scalar.h"
  22 #include "llvm/Intrinsics.h"
  23 #include "llvm/Module.h"
  24 #include "llvm/Pass.h"
  25 #include "llvm/Support/IRBuilder.h"
  26 #include "llvm/Analysis/ValueTracking.h"
  27 #include "llvm/Target/TargetData.h"
  28 #include "llvm/ADT/SmallPtrSet.h"
  29 #include "llvm/ADT/StringMap.h"
  30 #include "llvm/ADT/Statistic.h"
  31 #include "llvm/Support/Compiler.h"
  32 #include "llvm/Support/Debug.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 VISIBILITY_HIDDEN LibCallOptimization {
  47 protected:
  48   Function *Caller;
  49   const TargetData *TD;
  50 public:
  51   LibCallOptimization() { }
  52   virtual ~LibCallOptimization() {}
  53
  54   /// CallOptimizer - This pure virtual method is implemented by base classes to
  55   /// do various optimizations.  If this returns null then no transformation was
  56   /// performed.  If it returns CI, then it transformed the call and CI is to be
  57   /// deleted.  If it returns something else, replace CI with the new value and
  58   /// delete CI.
  59   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B)
  60     =0;
  61
  62   Value *OptimizeCall(CallInst *CI, const TargetData &TD, IRBuilder<> &B) {
  63     Caller = CI->getParent()->getParent();
  64     this->TD = &TD;
  65     return CallOptimizer(CI->getCalledFunction(), CI, B);
  66   }
  67
  68   /// CastToCStr - Return V if it is an i8*, otherwise cast it to i8*.
  69   Value *CastToCStr(Value *V, IRBuilder<> &B);
  70
  71   /// EmitStrLen - Emit a call to the strlen function to the builder, for the
  72   /// specified pointer.  Ptr is required to be some pointer type, and the
  73   /// return value has 'intptr_t' type.
  74   Value *EmitStrLen(Value *Ptr, IRBuilder<> &B);
  75
  76   /// EmitMemCpy - Emit a call to the memcpy function to the builder.  This
  77   /// always expects that the size has type 'intptr_t' and Dst/Src are pointers.
  78   Value *EmitMemCpy(Value *Dst, Value *Src, Value *Len,
  79                     unsigned Align, IRBuilder<> &B);
  80
  81   /// EmitMemChr - Emit a call to the memchr function.  This assumes that Ptr is
  82   /// a pointer, Val is an i32 value, and Len is an 'intptr_t' value.
  83   Value *EmitMemChr(Value *Ptr, Value *Val, Value *Len, IRBuilder<> &B);
  84
  85   /// EmitMemCmp - Emit a call to the memcmp function.
  86   Value *EmitMemCmp(Value *Ptr1, Value *Ptr2, Value *Len, IRBuilder<> &B);
  87
  88   /// EmitUnaryFloatFnCall - Emit a call to the unary function named 'Name' (e.g.
  89   /// 'floor').  This function is known to take a single of type matching 'Op'
  90   /// and returns one value with the same type.  If 'Op' is a long double, 'l'
  91   /// is added as the suffix of name, if 'Op' is a float, we add a 'f' suffix.
  92   Value *EmitUnaryFloatFnCall(Value *Op, const char *Name, IRBuilder<> &B);
  93
  94   /// EmitPutChar - Emit a call to the putchar function.  This assumes that Char
  95   /// is an integer.
  96   void EmitPutChar(Value *Char, IRBuilder<> &B);
  97
  98   /// EmitPutS - Emit a call to the puts function.  This assumes that Str is
  99   /// some pointer.
 100   void EmitPutS(Value *Str, IRBuilder<> &B);
 101
 102   /// EmitFPutC - Emit a call to the fputc function.  This assumes that Char is
 103   /// an i32, and File is a pointer to FILE.
 104   void EmitFPutC(Value *Char, Value *File, IRBuilder<> &B);
 105
 106   /// EmitFPutS - Emit a call to the puts function.  Str is required to be a
 107   /// pointer and File is a pointer to FILE.
 108   void EmitFPutS(Value *Str, Value *File, IRBuilder<> &B);
 109
 110   /// EmitFWrite - Emit a call to the fwrite function.  This assumes that Ptr is
 111   /// a pointer, Size is an 'intptr_t', and File is a pointer to FILE.
 112   void EmitFWrite(Value *Ptr, Value *Size, Value *File, IRBuilder<> &B);
 113
 114 };
 115 } // End anonymous namespace.
 116
 117 /// CastToCStr - Return V if it is an i8*, otherwise cast it to i8*.
 118 Value *LibCallOptimization::CastToCStr(Value *V, IRBuilder<> &B) {
 119   return B.CreateBitCast(V, PointerType::getUnqual(Type::Int8Ty), "cstr");
 120 }
 121
 122 /// EmitStrLen - Emit a call to the strlen function to the builder, for the
 123 /// specified pointer.  This always returns an integer value of size intptr_t.
 124 Value *LibCallOptimization::EmitStrLen(Value *Ptr, IRBuilder<> &B) {
 125   Module *M = Caller->getParent();
 126   Constant *StrLen =M->getOrInsertFunction("strlen", TD->getIntPtrType(),
 127                                            PointerType::getUnqual(Type::Int8Ty),
 128                                            NULL);
 129   return B.CreateCall(StrLen, CastToCStr(Ptr, B), "strlen");
 130 }
 131
 132 /// EmitMemCpy - Emit a call to the memcpy function to the builder.  This always
 133 /// expects that the size has type 'intptr_t' and Dst/Src are pointers.
 134 Value *LibCallOptimization::EmitMemCpy(Value *Dst, Value *Src, Value *Len,
 135                                        unsigned Align, IRBuilder<> &B) {
 136   Module *M = Caller->getParent();
 137   Intrinsic::ID IID = Intrinsic::memcpy;
 138   const Type *Tys[1];
 139   Tys[0] = Len->getType();
 140   Value *MemCpy = Intrinsic::getDeclaration(M, IID, Tys, 1);
 141   return B.CreateCall4(MemCpy, CastToCStr(Dst, B), CastToCStr(Src, B), Len,
 142                        ConstantInt::get(Type::Int32Ty, Align));
 143 }
 144
 145 /// EmitMemChr - Emit a call to the memchr function.  This assumes that Ptr is
 146 /// a pointer, Val is an i32 value, and Len is an 'intptr_t' value.
 147 Value *LibCallOptimization::EmitMemChr(Value *Ptr, Value *Val,
 148                                        Value *Len, IRBuilder<> &B) {
 149   Module *M = Caller->getParent();
 150   Value *MemChr = M->getOrInsertFunction("memchr",
 151                                          PointerType::getUnqual(Type::Int8Ty),
 152                                          PointerType::getUnqual(Type::Int8Ty),
 153                                          Type::Int32Ty, TD->getIntPtrType(),
 154                                          NULL);
 155   return B.CreateCall3(MemChr, CastToCStr(Ptr, B), Val, Len, "memchr");
 156 }
 157
 158 /// EmitMemCmp - Emit a call to the memcmp function.
 159 Value *LibCallOptimization::EmitMemCmp(Value *Ptr1, Value *Ptr2,
 160                                        Value *Len, IRBuilder<> &B) {
 161   Module *M = Caller->getParent();
 162   Value *MemCmp = M->getOrInsertFunction("memcmp",
 163                                          Type::Int32Ty,
 164                                          PointerType::getUnqual(Type::Int8Ty),
 165                                          PointerType::getUnqual(Type::Int8Ty),
 166                                          TD->getIntPtrType(), NULL);
 167   return B.CreateCall3(MemCmp, CastToCStr(Ptr1, B), CastToCStr(Ptr2, B),
 168                        Len, "memcmp");
 169 }
 170
 171 /// EmitUnaryFloatFnCall - Emit a call to the unary function named 'Name' (e.g.
 172 /// 'floor').  This function is known to take a single of type matching 'Op' and
 173 /// returns one value with the same type.  If 'Op' is a long double, 'l' is
 174 /// added as the suffix of name, if 'Op' is a float, we add a 'f' suffix.
 175 Value *LibCallOptimization::EmitUnaryFloatFnCall(Value *Op, const char *Name,
 176                                                  IRBuilder<> &B) {
 177   char NameBuffer[20];
 178   if (Op->getType() != Type::DoubleTy) {
 179     // If we need to add a suffix, copy into NameBuffer.
 180     unsigned NameLen = strlen(Name);
 181     assert(NameLen < sizeof(NameBuffer)-2);
 182     memcpy(NameBuffer, Name, NameLen);
 183     if (Op->getType() == Type::FloatTy)
 184       NameBuffer[NameLen] = 'f';  // floorf
 185     else
 186       NameBuffer[NameLen] = 'l';  // floorl
 187     NameBuffer[NameLen+1] = 0;
 188     Name = NameBuffer;
 189   }
 190
 191   Module *M = Caller->getParent();
 192   Value *Callee = M->getOrInsertFunction(Name, Op->getType(),
 193                                          Op->getType(), NULL);
 194   return B.CreateCall(Callee, Op, Name);
 195 }
 196
 197 /// EmitPutChar - Emit a call to the putchar function.  This assumes that Char
 198 /// is an integer.
 199 void LibCallOptimization::EmitPutChar(Value *Char, IRBuilder<> &B) {
 200   Module *M = Caller->getParent();
 201   Value *F = M->getOrInsertFunction("putchar", Type::Int32Ty,
 202                                     Type::Int32Ty, NULL);
 203   B.CreateCall(F, B.CreateIntCast(Char, Type::Int32Ty, "chari"), "putchar");
 204 }
 205
 206 /// EmitPutS - Emit a call to the puts function.  This assumes that Str is
 207 /// some pointer.
 208 void LibCallOptimization::EmitPutS(Value *Str, IRBuilder<> &B) {
 209   Module *M = Caller->getParent();
 210   Value *F = M->getOrInsertFunction("puts", Type::Int32Ty,
 211                                     PointerType::getUnqual(Type::Int8Ty), NULL);
 212   B.CreateCall(F, CastToCStr(Str, B), "puts");
 213 }
 214
 215 /// EmitFPutC - Emit a call to the fputc function.  This assumes that Char is
 216 /// an integer and File is a pointer to FILE.
 217 void LibCallOptimization::EmitFPutC(Value *Char, Value *File, IRBuilder<> &B) {
 218   Module *M = Caller->getParent();
 219   Constant *F = M->getOrInsertFunction("fputc", Type::Int32Ty, Type::Int32Ty,
 220                                        File->getType(), NULL);
 221   Char = B.CreateIntCast(Char, Type::Int32Ty, "chari");
 222   B.CreateCall2(F, Char, File, "fputc");
 223 }
 224
 225 /// EmitFPutS - Emit a call to the puts function.  Str is required to be a
 226 /// pointer and File is a pointer to FILE.
 227 void LibCallOptimization::EmitFPutS(Value *Str, Value *File, IRBuilder<> &B) {
 228   Module *M = Caller->getParent();
 229   Constant *F = M->getOrInsertFunction("fputs", Type::Int32Ty,
 230                                        PointerType::getUnqual(Type::Int8Ty),
 231                                        File->getType(), NULL);
 232   B.CreateCall2(F, CastToCStr(Str, B), File, "fputs");
 233 }
 234
 235 /// EmitFWrite - Emit a call to the fwrite function.  This assumes that Ptr is
 236 /// a pointer, Size is an 'intptr_t', and File is a pointer to FILE.
 237 void LibCallOptimization::EmitFWrite(Value *Ptr, Value *Size, Value *File,
 238                                      IRBuilder<> &B) {
 239   Module *M = Caller->getParent();
 240   Constant *F = M->getOrInsertFunction("fwrite", TD->getIntPtrType(),
 241                                        PointerType::getUnqual(Type::Int8Ty),
 242                                        TD->getIntPtrType(), TD->getIntPtrType(),
 243                                        File->getType(), NULL);
 244   B.CreateCall4(F, CastToCStr(Ptr, B), Size,
 245                 ConstantInt::get(TD->getIntPtrType(), 1), File);
 246 }
 247
 248 //===----------------------------------------------------------------------===//
 249 // Helper Functions
 250 //===----------------------------------------------------------------------===//
 251
 252 /// GetStringLengthH - If we can compute the length of the string pointed to by
 253 /// the specified pointer, return 'len+1'.  If we can't, return 0.
 254 static uint64_t GetStringLengthH(Value *V, SmallPtrSet<PHINode*, 32> &PHIs) {
 255   // Look through noop bitcast instructions.
 256   if (BitCastInst *BCI = dyn_cast<BitCastInst>(V))
 257     return GetStringLengthH(BCI->getOperand(0), PHIs);
 258
 259   // If this is a PHI node, there are two cases: either we have already seen it
 260   // or we haven't.
 261   if (PHINode *PN = dyn_cast<PHINode>(V)) {
 262     if (!PHIs.insert(PN))
 263       return ~0ULL;  // already in the set.
 264
 265     // If it was new, see if all the input strings are the same length.
 266     uint64_t LenSoFar = ~0ULL;
 267     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 268       uint64_t Len = GetStringLengthH(PN->getIncomingValue(i), PHIs);
 269       if (Len == 0) return 0; // Unknown length -> unknown.
 270
 271       if (Len == ~0ULL) continue;
 272
 273       if (Len != LenSoFar && LenSoFar != ~0ULL)
 274         return 0;    // Disagree -> unknown.
 275       LenSoFar = Len;
 276     }
 277
 278     // Success, all agree.
 279     return LenSoFar;
 280   }
 281
 282   // strlen(select(c,x,y)) -> strlen(x) ^ strlen(y)
 283   if (SelectInst *SI = dyn_cast<SelectInst>(V)) {
 284     uint64_t Len1 = GetStringLengthH(SI->getTrueValue(), PHIs);
 285     if (Len1 == 0) return 0;
 286     uint64_t Len2 = GetStringLengthH(SI->getFalseValue(), PHIs);
 287     if (Len2 == 0) return 0;
 288     if (Len1 == ~0ULL) return Len2;
 289     if (Len2 == ~0ULL) return Len1;
 290     if (Len1 != Len2) return 0;
 291     return Len1;
 292   }
 293
 294   // If the value is not a GEP instruction nor a constant expression with a
 295   // GEP instruction, then return unknown.
 296   User *GEP = 0;
 297   if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(V)) {
 298     GEP = GEPI;
 299   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
 300     if (CE->getOpcode() != Instruction::GetElementPtr)
 301       return 0;
 302     GEP = CE;
 303   } else {
 304     return 0;
 305   }
 306
 307   // Make sure the GEP has exactly three arguments.
 308   if (GEP->getNumOperands() != 3)
 309     return 0;
 310
 311   // Check to make sure that the first operand of the GEP is an integer and
 312   // has value 0 so that we are sure we're indexing into the initializer.
 313   if (ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(1))) {
 314     if (!Idx->isZero())
 315       return 0;
 316   } else
 317     return 0;
 318
 319   // If the second index isn't a ConstantInt, then this is a variable index
 320   // into the array.  If this occurs, we can't say anything meaningful about
 321   // the string.
 322   uint64_t StartIdx = 0;
 323   if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(2)))
 324     StartIdx = CI->getZExtValue();
 325   else
 326     return 0;
 327
 328   // The GEP instruction, constant or instruction, must reference a global
 329   // variable that is a constant and is initialized. The referenced constant
 330   // initializer is the array that we'll use for optimization.
 331   GlobalVariable* GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
 332   if (!GV || !GV->isConstant() || !GV->hasInitializer())
 333     return 0;
 334   Constant *GlobalInit = GV->getInitializer();
 335
 336   // Handle the ConstantAggregateZero case, which is a degenerate case. The
 337   // initializer is constant zero so the length of the string must be zero.
 338   if (isa<ConstantAggregateZero>(GlobalInit))
 339     return 1;  // Len = 0 offset by 1.
 340
 341   // Must be a Constant Array
 342   ConstantArray *Array = dyn_cast<ConstantArray>(GlobalInit);
 343   if (!Array || Array->getType()->getElementType() != Type::Int8Ty)
 344     return false;
 345
 346   // Get the number of elements in the array
 347   uint64_t NumElts = Array->getType()->getNumElements();
 348
 349   // Traverse the constant array from StartIdx (derived above) which is
 350   // the place the GEP refers to in the array.
 351   for (unsigned i = StartIdx; i != NumElts; ++i) {
 352     Constant *Elt = Array->getOperand(i);
 353     ConstantInt *CI = dyn_cast<ConstantInt>(Elt);
 354     if (!CI) // This array isn't suitable, non-int initializer.
 355       return 0;
 356     if (CI->isZero())
 357       return i-StartIdx+1; // We found end of string, success!
 358   }
 359
 360   return 0; // The array isn't null terminated, conservatively return 'unknown'.
 361 }
 362
 363 /// GetStringLength - If we can compute the length of the string pointed to by
 364 /// the specified pointer, return 'len+1'.  If we can't, return 0.
 365 static uint64_t GetStringLength(Value *V) {
 366   if (!isa<PointerType>(V->getType())) return 0;
 367
 368   SmallPtrSet<PHINode*, 32> PHIs;
 369   uint64_t Len = GetStringLengthH(V, PHIs);
 370   // If Len is ~0ULL, we had an infinite phi cycle: this is dead code, so return
 371   // an empty string as a length.
 372   return Len == ~0ULL ? 1 : Len;
 373 }
 374
 375 /// IsOnlyUsedInZeroEqualityComparison - Return true if it only matters that the
 376 /// value is equal or not-equal to zero.
 377 static bool IsOnlyUsedInZeroEqualityComparison(Value *V) {
 378   for (Value::use_iterator UI = V->use_begin(), E = V->use_end();
 379        UI != E; ++UI) {
 380     if (ICmpInst *IC = dyn_cast<ICmpInst>(*UI))
 381       if (IC->isEquality())
 382         if (Constant *C = dyn_cast<Constant>(IC->getOperand(1)))
 383           if (C->isNullValue())
 384             continue;
 385     // Unknown instruction.
 386     return false;
 387   }
 388   return true;
 389 }
 390
 391 //===----------------------------------------------------------------------===//
 392 // Miscellaneous LibCall Optimizations
 393 //===----------------------------------------------------------------------===//
 394
 395 namespace {
 396 //===---------------------------------------===//
 397 // 'exit' Optimizations
 398
 399 /// ExitOpt - int main() { exit(4); } --> int main() { return 4; }
 400 struct VISIBILITY_HIDDEN ExitOpt : public LibCallOptimization {
 401   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 402     // Verify we have a reasonable prototype for exit.
 403     if (Callee->arg_size() == 0 || !CI->use_empty())
 404       return 0;
 405
 406     // Verify the caller is main, and that the result type of main matches the
 407     // argument type of exit.
 408     if (!Caller->isName("main") || !Caller->hasExternalLinkage() ||
 409         Caller->getReturnType() != CI->getOperand(1)->getType())
 410       return 0;
 411
 412     TerminatorInst *OldTI = CI->getParent()->getTerminator();
 413
 414     // Create the return after the call.
 415     ReturnInst *RI = B.CreateRet(CI->getOperand(1));
 416
 417     // Drop all successor phi node entries.
 418     for (unsigned i = 0, e = OldTI->getNumSuccessors(); i != e; ++i)
 419       OldTI->getSuccessor(i)->removePredecessor(CI->getParent());
 420
 421     // Erase all instructions from after our return instruction until the end of
 422     // the block.
 423     BasicBlock::iterator FirstDead = RI; ++FirstDead;
 424     CI->getParent()->getInstList().erase(FirstDead, CI->getParent()->end());
 425     return CI;
 426   }
 427 };
 428
 429 //===----------------------------------------------------------------------===//
 430 // String and Memory LibCall Optimizations
 431 //===----------------------------------------------------------------------===//
 432
 433 //===---------------------------------------===//
 434 // 'strcat' Optimizations
 435
 436 struct VISIBILITY_HIDDEN StrCatOpt : public LibCallOptimization {
 437   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 438     // Verify the "strcat" function prototype.
 439     const FunctionType *FT = Callee->getFunctionType();
 440     if (FT->getNumParams() != 2 ||
 441         FT->getReturnType() != PointerType::getUnqual(Type::Int8Ty) ||
 442         FT->getParamType(0) != FT->getReturnType() ||
 443         FT->getParamType(1) != FT->getReturnType())
 444       return 0;
 445
 446     // Extract some information from the instruction
 447     Value *Dst = CI->getOperand(1);
 448     Value *Src = CI->getOperand(2);
 449
 450     // See if we can get the length of the input string.
 451     uint64_t Len = GetStringLength(Src);
 452     if (Len == 0) return 0;
 453     --Len;  // Unbias length.
 454
 455     // Handle the simple, do-nothing case: strcat(x, "") -> x
 456     if (Len == 0)
 457       return Dst;
 458
 459     // We need to find the end of the destination string.  That's where the
 460     // memory is to be moved to. We just generate a call to strlen.
 461     Value *DstLen = EmitStrLen(Dst, B);
 462
 463     // Now that we have the destination's length, we must index into the
 464     // destination's pointer to get the actual memcpy destination (end of
 465     // the string .. we're concatenating).
 466     Dst = B.CreateGEP(Dst, DstLen, "endptr");
 467
 468     // We have enough information to now generate the memcpy call to do the
 469     // concatenation for us.  Make a memcpy to copy the nul byte with align = 1.
 470     EmitMemCpy(Dst, Src, ConstantInt::get(TD->getIntPtrType(), Len+1), 1, B);
 471     return Dst;
 472   }
 473 };
 474
 475 //===---------------------------------------===//
 476 // 'strchr' Optimizations
 477
 478 struct VISIBILITY_HIDDEN StrChrOpt : public LibCallOptimization {
 479   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 480     // Verify the "strchr" function prototype.
 481     const FunctionType *FT = Callee->getFunctionType();
 482     if (FT->getNumParams() != 2 ||
 483         FT->getReturnType() != PointerType::getUnqual(Type::Int8Ty) ||
 484         FT->getParamType(0) != FT->getReturnType())
 485       return 0;
 486
 487     Value *SrcStr = CI->getOperand(1);
 488
 489     // If the second operand is non-constant, see if we can compute the length
 490     // of the input string and turn this into memchr.
 491     ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getOperand(2));
 492     if (CharC == 0) {
 493       uint64_t Len = GetStringLength(SrcStr);
 494       if (Len == 0 || FT->getParamType(1) != Type::Int32Ty) // memchr needs i32.
 495         return 0;
 496
 497       return EmitMemChr(SrcStr, CI->getOperand(2), // include nul.
 498                         ConstantInt::get(TD->getIntPtrType(), Len), B);
 499     }
 500
 501     // Otherwise, the character is a constant, see if the first argument is
 502     // a string literal.  If so, we can constant fold.
 503     std::string Str;
 504     if (!GetConstantStringInfo(SrcStr, Str))
 505       return 0;
 506
 507     // strchr can find the nul character.
 508     Str += '\0';
 509     char CharValue = CharC->getSExtValue();
 510
 511     // Compute the offset.
 512     uint64_t i = 0;
 513     while (1) {
 514       if (i == Str.size())    // Didn't find the char.  strchr returns null.
 515         return Constant::getNullValue(CI->getType());
 516       // Did we find our match?
 517       if (Str[i] == CharValue)
 518         break;
 519       ++i;
 520     }
 521
 522     // strchr(s+n,c)  -> gep(s+n+i,c)
 523     Value *Idx = ConstantInt::get(Type::Int64Ty, i);
 524     return B.CreateGEP(SrcStr, Idx, "strchr");
 525   }
 526 };
 527
 528 //===---------------------------------------===//
 529 // 'strcmp' Optimizations
 530
 531 struct VISIBILITY_HIDDEN StrCmpOpt : public LibCallOptimization {
 532   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 533     // Verify the "strcmp" function prototype.
 534     const FunctionType *FT = Callee->getFunctionType();
 535     if (FT->getNumParams() != 2 || FT->getReturnType() != Type::Int32Ty ||
 536         FT->getParamType(0) != FT->getParamType(1) ||
 537         FT->getParamType(0) != PointerType::getUnqual(Type::Int8Ty))
 538       return 0;
 539
 540     Value *Str1P = CI->getOperand(1), *Str2P = CI->getOperand(2);
 541     if (Str1P == Str2P)      // strcmp(x,x)  -> 0
 542       return ConstantInt::get(CI->getType(), 0);
 543
 544     std::string Str1, Str2;
 545     bool HasStr1 = GetConstantStringInfo(Str1P, Str1);
 546     bool HasStr2 = GetConstantStringInfo(Str2P, Str2);
 547
 548     if (HasStr1 && Str1.empty()) // strcmp("", x) -> *x
 549       return B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"), CI->getType());
 550
 551     if (HasStr2 && Str2.empty()) // strcmp(x,"") -> *x
 552       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
 553
 554     // strcmp(x, y)  -> cnst  (if both x and y are constant strings)
 555     if (HasStr1 && HasStr2)
 556       return ConstantInt::get(CI->getType(), strcmp(Str1.c_str(),Str2.c_str()));
 557
 558     // strcmp(P, "x") -> memcmp(P, "x", 2)
 559     uint64_t Len1 = GetStringLength(Str1P);
 560     uint64_t Len2 = GetStringLength(Str2P);
 561     if (Len1 || Len2) {
 562       // Choose the smallest Len excluding 0 which means 'unknown'.
 563       if (!Len1 || (Len2 && Len2 < Len1))
 564         Len1 = Len2;
 565       return EmitMemCmp(Str1P, Str2P,
 566                         ConstantInt::get(TD->getIntPtrType(), Len1), B);
 567     }
 568
 569     return 0;
 570   }
 571 };
 572
 573 //===---------------------------------------===//
 574 // 'strncmp' Optimizations
 575
 576 struct VISIBILITY_HIDDEN StrNCmpOpt : public LibCallOptimization {
 577   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 578     // Verify the "strncmp" function prototype.
 579     const FunctionType *FT = Callee->getFunctionType();
 580     if (FT->getNumParams() != 3 || FT->getReturnType() != Type::Int32Ty ||
 581         FT->getParamType(0) != FT->getParamType(1) ||
 582         FT->getParamType(0) != PointerType::getUnqual(Type::Int8Ty) ||
 583         !isa<IntegerType>(FT->getParamType(2)))
 584       return 0;
 585
 586     Value *Str1P = CI->getOperand(1), *Str2P = CI->getOperand(2);
 587     if (Str1P == Str2P)      // strncmp(x,x,n)  -> 0
 588       return ConstantInt::get(CI->getType(), 0);
 589
 590     // Get the length argument if it is constant.
 591     uint64_t Length;
 592     if (ConstantInt *LengthArg = dyn_cast<ConstantInt>(CI->getOperand(3)))
 593       Length = LengthArg->getZExtValue();
 594     else
 595       return 0;
 596
 597     if (Length == 0) // strncmp(x,y,0)   -> 0
 598       return ConstantInt::get(CI->getType(), 0);
 599
 600     std::string Str1, Str2;
 601     bool HasStr1 = GetConstantStringInfo(Str1P, Str1);
 602     bool HasStr2 = GetConstantStringInfo(Str2P, Str2);
 603
 604     if (HasStr1 && Str1.empty())  // strncmp("", x, n) -> *x
 605       return B.CreateZExt(B.CreateLoad(Str2P, "strcmpload"), CI->getType());
 606
 607     if (HasStr2 && Str2.empty())  // strncmp(x, "", n) -> *x
 608       return B.CreateZExt(B.CreateLoad(Str1P, "strcmpload"), CI->getType());
 609
 610     // strncmp(x, y)  -> cnst  (if both x and y are constant strings)
 611     if (HasStr1 && HasStr2)
 612       return ConstantInt::get(CI->getType(),
 613                               strncmp(Str1.c_str(), Str2.c_str(), Length));
 614     return 0;
 615   }
 616 };
 617
 618
 619 //===---------------------------------------===//
 620 // 'strcpy' Optimizations
 621
 622 struct VISIBILITY_HIDDEN StrCpyOpt : public LibCallOptimization {
 623   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 624     // Verify the "strcpy" function prototype.
 625     const FunctionType *FT = Callee->getFunctionType();
 626     if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) ||
 627         FT->getParamType(0) != FT->getParamType(1) ||
 628         FT->getParamType(0) != PointerType::getUnqual(Type::Int8Ty))
 629       return 0;
 630
 631     Value *Dst = CI->getOperand(1), *Src = CI->getOperand(2);
 632     if (Dst == Src)      // strcpy(x,x)  -> x
 633       return Src;
 634
 635     // See if we can get the length of the input string.
 636     uint64_t Len = GetStringLength(Src);
 637     if (Len == 0) return 0;
 638
 639     // We have enough information to now generate the memcpy call to do the
 640     // concatenation for us.  Make a memcpy to copy the nul byte with align = 1.
 641     EmitMemCpy(Dst, Src, ConstantInt::get(TD->getIntPtrType(), Len), 1, B);
 642     return Dst;
 643   }
 644 };
 645
 646
 647
 648 //===---------------------------------------===//
 649 // 'strlen' Optimizations
 650
 651 struct VISIBILITY_HIDDEN StrLenOpt : public LibCallOptimization {
 652   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 653     const FunctionType *FT = Callee->getFunctionType();
 654     if (FT->getNumParams() != 1 ||
 655         FT->getParamType(0) != PointerType::getUnqual(Type::Int8Ty) ||
 656         !isa<IntegerType>(FT->getReturnType()))
 657       return 0;
 658
 659     Value *Src = CI->getOperand(1);
 660
 661     // Constant folding: strlen("xyz") -> 3
 662     if (uint64_t Len = GetStringLength(Src))
 663       return ConstantInt::get(CI->getType(), Len-1);
 664
 665     // Handle strlen(p) != 0.
 666     if (!IsOnlyUsedInZeroEqualityComparison(CI)) return 0;
 667
 668     // strlen(x) != 0 --> *x != 0
 669     // strlen(x) == 0 --> *x == 0
 670     return B.CreateZExt(B.CreateLoad(Src, "strlenfirst"), CI->getType());
 671   }
 672 };
 673
 674 //===---------------------------------------===//
 675 // 'memcmp' Optimizations
 676
 677 struct VISIBILITY_HIDDEN MemCmpOpt : public LibCallOptimization {
 678   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 679     const FunctionType *FT = Callee->getFunctionType();
 680     if (FT->getNumParams() != 3 || !isa<PointerType>(FT->getParamType(0)) ||
 681         !isa<PointerType>(FT->getParamType(1)) ||
 682         FT->getReturnType() != Type::Int32Ty)
 683       return 0;
 684
 685     Value *LHS = CI->getOperand(1), *RHS = CI->getOperand(2);
 686
 687     if (LHS == RHS)  // memcmp(s,s,x) -> 0
 688       return Constant::getNullValue(CI->getType());
 689
 690     // Make sure we have a constant length.
 691     ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getOperand(3));
 692     if (!LenC) return 0;
 693     uint64_t Len = LenC->getZExtValue();
 694
 695     if (Len == 0) // memcmp(s1,s2,0) -> 0
 696       return Constant::getNullValue(CI->getType());
 697
 698     if (Len == 1) { // memcmp(S1,S2,1) -> *LHS - *RHS
 699       Value *LHSV = B.CreateLoad(CastToCStr(LHS, B), "lhsv");
 700       Value *RHSV = B.CreateLoad(CastToCStr(RHS, B), "rhsv");
 701       return B.CreateZExt(B.CreateSub(LHSV, RHSV, "chardiff"), CI->getType());
 702     }
 703
 704     // memcmp(S1,S2,2) != 0 -> (*(short*)LHS ^ *(short*)RHS)  != 0
 705     // memcmp(S1,S2,4) != 0 -> (*(int*)LHS ^ *(int*)RHS)  != 0
 706     if ((Len == 2 || Len == 4) && IsOnlyUsedInZeroEqualityComparison(CI)) {
 707       const Type *PTy = PointerType::getUnqual(Len == 2 ?
 708                                                Type::Int16Ty : Type::Int32Ty);
 709       LHS = B.CreateBitCast(LHS, PTy, "tmp");
 710       RHS = B.CreateBitCast(RHS, PTy, "tmp");
 711       LoadInst *LHSV = B.CreateLoad(LHS, "lhsv");
 712       LoadInst *RHSV = B.CreateLoad(RHS, "rhsv");
 713       LHSV->setAlignment(1); RHSV->setAlignment(1);  // Unaligned loads.
 714       return B.CreateZExt(B.CreateXor(LHSV, RHSV, "shortdiff"), CI->getType());
 715     }
 716
 717     return 0;
 718   }
 719 };
 720
 721 //===---------------------------------------===//
 722 // 'memcpy' Optimizations
 723
 724 struct VISIBILITY_HIDDEN MemCpyOpt : public LibCallOptimization {
 725   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 726     const FunctionType *FT = Callee->getFunctionType();
 727     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 728         !isa<PointerType>(FT->getParamType(0)) ||
 729         !isa<PointerType>(FT->getParamType(1)) ||
 730         FT->getParamType(2) != TD->getIntPtrType())
 731       return 0;
 732
 733     // memcpy(x, y, n) -> llvm.memcpy(x, y, n, 1)
 734     EmitMemCpy(CI->getOperand(1), CI->getOperand(2), CI->getOperand(3), 1, B);
 735     return CI->getOperand(1);
 736   }
 737 };
 738
 739 //===---------------------------------------===//
 740 // 'memmove' Optimizations
 741
 742 struct VISIBILITY_HIDDEN MemMoveOpt : public LibCallOptimization {
 743   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 744     const FunctionType *FT = Callee->getFunctionType();
 745     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 746         !isa<PointerType>(FT->getParamType(0)) ||
 747         !isa<PointerType>(FT->getParamType(1)) ||
 748         FT->getParamType(2) != TD->getIntPtrType())
 749       return 0;
 750
 751     // memmove(x, y, n) -> llvm.memmove(x, y, n, 1)
 752     Module *M = Caller->getParent();
 753     Intrinsic::ID IID = Intrinsic::memmove;
 754     const Type *Tys[1];
 755     Tys[0] = TD->getIntPtrType();
 756     Value *MemMove = Intrinsic::getDeclaration(M, IID, Tys, 1);
 757     Value *Dst = CastToCStr(CI->getOperand(1), B);
 758     Value *Src = CastToCStr(CI->getOperand(2), B);
 759     Value *Size = CI->getOperand(3);
 760     Value *Align = ConstantInt::get(Type::Int32Ty, 1);
 761     B.CreateCall4(MemMove, Dst, Src, Size, Align);
 762     return CI->getOperand(1);
 763   }
 764 };
 765
 766 //===---------------------------------------===//
 767 // 'memset' Optimizations
 768
 769 struct VISIBILITY_HIDDEN MemSetOpt : public LibCallOptimization {
 770   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 771     const FunctionType *FT = Callee->getFunctionType();
 772     if (FT->getNumParams() != 3 || FT->getReturnType() != FT->getParamType(0) ||
 773         !isa<PointerType>(FT->getParamType(0)) ||
 774         FT->getParamType(1) != TD->getIntPtrType() ||
 775         FT->getParamType(2) != TD->getIntPtrType())
 776       return 0;
 777
 778     // memset(p, v, n) -> llvm.memset(p, v, n, 1)
 779     Module *M = Caller->getParent();
 780     Intrinsic::ID IID = Intrinsic::memset;
 781     const Type *Tys[1];
 782     Tys[0] = TD->getIntPtrType();
 783     Value *MemSet = Intrinsic::getDeclaration(M, IID, Tys, 1);
 784     Value *Dst = CastToCStr(CI->getOperand(1), B);
 785     Value *Val = B.CreateTrunc(CI->getOperand(2), Type::Int8Ty);
 786     Value *Size = CI->getOperand(3);
 787     Value *Align = ConstantInt::get(Type::Int32Ty, 1);
 788     B.CreateCall4(MemSet, Dst, Val, Size, Align);
 789     return CI->getOperand(1);
 790   }
 791 };
 792
 793 //===----------------------------------------------------------------------===//
 794 // Math Library Optimizations
 795 //===----------------------------------------------------------------------===//
 796
 797 //===---------------------------------------===//
 798 // 'pow*' Optimizations
 799
 800 struct VISIBILITY_HIDDEN PowOpt : public LibCallOptimization {
 801   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 802     const FunctionType *FT = Callee->getFunctionType();
 803     // Just make sure this has 2 arguments of the same FP type, which match the
 804     // result type.
 805     if (FT->getNumParams() != 2 || FT->getReturnType() != FT->getParamType(0) ||
 806         FT->getParamType(0) != FT->getParamType(1) ||
 807         !FT->getParamType(0)->isFloatingPoint())
 808       return 0;
 809
 810     Value *Op1 = CI->getOperand(1), *Op2 = CI->getOperand(2);
 811     if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) {
 812       if (Op1C->isExactlyValue(1.0))  // pow(1.0, x) -> 1.0
 813         return Op1C;
 814       if (Op1C->isExactlyValue(2.0))  // pow(2.0, x) -> exp2(x)
 815         return EmitUnaryFloatFnCall(Op2, "exp2", B);
 816     }
 817
 818     ConstantFP *Op2C = dyn_cast<ConstantFP>(Op2);
 819     if (Op2C == 0) return 0;
 820
 821     if (Op2C->getValueAPF().isZero())  // pow(x, 0.0) -> 1.0
 822       return ConstantFP::get(CI->getType(), 1.0);
 823
 824     if (Op2C->isExactlyValue(0.5)) {
 825       // FIXME: This is not safe for -0.0 and -inf.  This can only be done when
 826       // 'unsafe' math optimizations are allowed.
 827       // x    pow(x, 0.5)  sqrt(x)
 828       // ---------------------------------------------
 829       // -0.0    +0.0       -0.0
 830       // -inf    +inf       NaN
 831 #if 0
 832       // pow(x, 0.5) -> sqrt(x)
 833       return B.CreateCall(get_sqrt(), Op1, "sqrt");
 834 #endif
 835     }
 836
 837     if (Op2C->isExactlyValue(1.0))  // pow(x, 1.0) -> x
 838       return Op1;
 839     if (Op2C->isExactlyValue(2.0))  // pow(x, 2.0) -> x*x
 840       return B.CreateMul(Op1, Op1, "pow2");
 841     if (Op2C->isExactlyValue(-1.0)) // pow(x, -1.0) -> 1.0/x
 842       return B.CreateFDiv(ConstantFP::get(CI->getType(), 1.0), Op1, "powrecip");
 843     return 0;
 844   }
 845 };
 846
 847 //===---------------------------------------===//
 848 // 'exp2' Optimizations
 849
 850 struct VISIBILITY_HIDDEN Exp2Opt : public LibCallOptimization {
 851   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 852     const FunctionType *FT = Callee->getFunctionType();
 853     // Just make sure this has 1 argument of FP type, which matches the
 854     // result type.
 855     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
 856         !FT->getParamType(0)->isFloatingPoint())
 857       return 0;
 858
 859     Value *Op = CI->getOperand(1);
 860     // Turn exp2(sitofp(x)) -> ldexp(1.0, sext(x))  if sizeof(x) <= 32
 861     // Turn exp2(uitofp(x)) -> ldexp(1.0, zext(x))  if sizeof(x) < 32
 862     Value *LdExpArg = 0;
 863     if (SIToFPInst *OpC = dyn_cast<SIToFPInst>(Op)) {
 864       if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() <= 32)
 865         LdExpArg = B.CreateSExt(OpC->getOperand(0), Type::Int32Ty, "tmp");
 866     } else if (UIToFPInst *OpC = dyn_cast<UIToFPInst>(Op)) {
 867       if (OpC->getOperand(0)->getType()->getPrimitiveSizeInBits() < 32)
 868         LdExpArg = B.CreateZExt(OpC->getOperand(0), Type::Int32Ty, "tmp");
 869     }
 870
 871     if (LdExpArg) {
 872       const char *Name;
 873       if (Op->getType() == Type::FloatTy)
 874         Name = "ldexpf";
 875       else if (Op->getType() == Type::DoubleTy)
 876         Name = "ldexp";
 877       else
 878         Name = "ldexpl";
 879
 880       Constant *One = ConstantFP::get(APFloat(1.0f));
 881       if (Op->getType() != Type::FloatTy)
 882         One = ConstantExpr::getFPExtend(One, Op->getType());
 883
 884       Module *M = Caller->getParent();
 885       Value *Callee = M->getOrInsertFunction(Name, Op->getType(),
 886                                              Op->getType(), Type::Int32Ty,NULL);
 887       return B.CreateCall2(Callee, One, LdExpArg);
 888     }
 889     return 0;
 890   }
 891 };
 892
 893
 894 //===---------------------------------------===//
 895 // Double -> Float Shrinking Optimizations for Unary Functions like 'floor'
 896
 897 struct VISIBILITY_HIDDEN UnaryDoubleFPOpt : public LibCallOptimization {
 898   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 899     const FunctionType *FT = Callee->getFunctionType();
 900     if (FT->getNumParams() != 1 || FT->getReturnType() != Type::DoubleTy ||
 901         FT->getParamType(0) != Type::DoubleTy)
 902       return 0;
 903
 904     // If this is something like 'floor((double)floatval)', convert to floorf.
 905     FPExtInst *Cast = dyn_cast<FPExtInst>(CI->getOperand(1));
 906     if (Cast == 0 || Cast->getOperand(0)->getType() != Type::FloatTy)
 907       return 0;
 908
 909     // floor((double)floatval) -> (double)floorf(floatval)
 910     Value *V = Cast->getOperand(0);
 911     V = EmitUnaryFloatFnCall(V, Callee->getNameStart(), B);
 912     return B.CreateFPExt(V, Type::DoubleTy);
 913   }
 914 };
 915
 916 //===----------------------------------------------------------------------===//
 917 // Integer Optimizations
 918 //===----------------------------------------------------------------------===//
 919
 920 //===---------------------------------------===//
 921 // 'ffs*' Optimizations
 922
 923 struct VISIBILITY_HIDDEN FFSOpt : public LibCallOptimization {
 924   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 925     const FunctionType *FT = Callee->getFunctionType();
 926     // Just make sure this has 2 arguments of the same FP type, which match the
 927     // result type.
 928     if (FT->getNumParams() != 1 || FT->getReturnType() != Type::Int32Ty ||
 929         !isa<IntegerType>(FT->getParamType(0)))
 930       return 0;
 931
 932     Value *Op = CI->getOperand(1);
 933
 934     // Constant fold.
 935     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op)) {
 936       if (CI->getValue() == 0)  // ffs(0) -> 0.
 937         return Constant::getNullValue(CI->getType());
 938       return ConstantInt::get(Type::Int32Ty, // ffs(c) -> cttz(c)+1
 939                               CI->getValue().countTrailingZeros()+1);
 940     }
 941
 942     // ffs(x) -> x != 0 ? (i32)llvm.cttz(x)+1 : 0
 943     const Type *ArgType = Op->getType();
 944     Value *F = Intrinsic::getDeclaration(Callee->getParent(),
 945                                          Intrinsic::cttz, &ArgType, 1);
 946     Value *V = B.CreateCall(F, Op, "cttz");
 947     V = B.CreateAdd(V, ConstantInt::get(Type::Int32Ty, 1), "tmp");
 948     V = B.CreateIntCast(V, Type::Int32Ty, false, "tmp");
 949
 950     Value *Cond = B.CreateICmpNE(Op, Constant::getNullValue(ArgType), "tmp");
 951     return B.CreateSelect(Cond, V, ConstantInt::get(Type::Int32Ty, 0));
 952   }
 953 };
 954
 955 //===---------------------------------------===//
 956 // 'isdigit' Optimizations
 957
 958 struct VISIBILITY_HIDDEN IsDigitOpt : public LibCallOptimization {
 959   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 960     const FunctionType *FT = Callee->getFunctionType();
 961     // We require integer(i32)
 962     if (FT->getNumParams() != 1 || !isa<IntegerType>(FT->getReturnType()) ||
 963         FT->getParamType(0) != Type::Int32Ty)
 964       return 0;
 965
 966     // isdigit(c) -> (c-'0') <u 10
 967     Value *Op = CI->getOperand(1);
 968     Op = B.CreateSub(Op, ConstantInt::get(Type::Int32Ty, '0'), "isdigittmp");
 969     Op = B.CreateICmpULT(Op, ConstantInt::get(Type::Int32Ty, 10), "isdigit");
 970     return B.CreateZExt(Op, CI->getType());
 971   }
 972 };
 973
 974 //===---------------------------------------===//
 975 // 'isascii' Optimizations
 976
 977 struct VISIBILITY_HIDDEN IsAsciiOpt : public LibCallOptimization {
 978   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 979     const FunctionType *FT = Callee->getFunctionType();
 980     // We require integer(i32)
 981     if (FT->getNumParams() != 1 || !isa<IntegerType>(FT->getReturnType()) ||
 982         FT->getParamType(0) != Type::Int32Ty)
 983       return 0;
 984
 985     // isascii(c) -> c <u 128
 986     Value *Op = CI->getOperand(1);
 987     Op = B.CreateICmpULT(Op, ConstantInt::get(Type::Int32Ty, 128), "isascii");
 988     return B.CreateZExt(Op, CI->getType());
 989   }
 990 };
 991
 992 //===---------------------------------------===//
 993 // 'abs', 'labs', 'llabs' Optimizations
 994
 995 struct VISIBILITY_HIDDEN AbsOpt : public LibCallOptimization {
 996   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 997     const FunctionType *FT = Callee->getFunctionType();
 998     // We require integer(integer) where the types agree.
 999     if (FT->getNumParams() != 1 || !isa<IntegerType>(FT->getReturnType()) ||
1000         FT->getParamType(0) != FT->getReturnType())
1001       return 0;
1002
1003     // abs(x) -> x >s -1 ? x : -x
1004     Value *Op = CI->getOperand(1);
1005     Value *Pos = B.CreateICmpSGT(Op,ConstantInt::getAllOnesValue(Op->getType()),
1006                                  "ispos");
1007     Value *Neg = B.CreateNeg(Op, "neg");
1008     return B.CreateSelect(Pos, Op, Neg);
1009   }
1010 };
1011
1012
1013 //===---------------------------------------===//
1014 // 'toascii' Optimizations
1015
1016 struct VISIBILITY_HIDDEN ToAsciiOpt : public LibCallOptimization {
1017   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1018     const FunctionType *FT = Callee->getFunctionType();
1019     // We require i32(i32)
1020     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
1021         FT->getParamType(0) != Type::Int32Ty)
1022       return 0;
1023
1024     // isascii(c) -> c & 0x7f
1025     return B.CreateAnd(CI->getOperand(1), ConstantInt::get(CI->getType(),0x7F));
1026   }
1027 };
1028
1029 //===----------------------------------------------------------------------===//
1030 // Formatting and IO Optimizations
1031 //===----------------------------------------------------------------------===//
1032
1033 //===---------------------------------------===//
1034 // 'printf' Optimizations
1035
1036 struct VISIBILITY_HIDDEN PrintFOpt : public LibCallOptimization {
1037   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1038     // Require one fixed pointer argument and an integer/void result.
1039     const FunctionType *FT = Callee->getFunctionType();
1040     if (FT->getNumParams() < 1 || !isa<PointerType>(FT->getParamType(0)) ||
1041         !(isa<IntegerType>(FT->getReturnType()) ||
1042           FT->getReturnType() == Type::VoidTy))
1043       return 0;
1044
1045     // Check for a fixed format string.
1046     std::string FormatStr;
1047     if (!GetConstantStringInfo(CI->getOperand(1), FormatStr))
1048       return 0;
1049
1050     // Empty format string -> noop.
1051     if (FormatStr.empty())  // Tolerate printf's declared void.
1052       return CI->use_empty() ? (Value*)CI : ConstantInt::get(CI->getType(), 0);
1053
1054     // printf("x") -> putchar('x'), even for '%'.
1055     if (FormatStr.size() == 1) {
1056       EmitPutChar(ConstantInt::get(Type::Int32Ty, FormatStr[0]), B);
1057       return CI->use_empty() ? (Value*)CI : ConstantInt::get(CI->getType(), 1);
1058     }
1059
1060     // printf("foo\n") --> puts("foo")
1061     if (FormatStr[FormatStr.size()-1] == '\n' &&
1062         FormatStr.find('%') == std::string::npos) {  // no format characters.
1063       // Create a string literal with no \n on it.  We expect the constant merge
1064       // pass to be run after this pass, to merge duplicate strings.
1065       FormatStr.erase(FormatStr.end()-1);
1066       Constant *C = ConstantArray::get(FormatStr, true);
1067       C = new GlobalVariable(C->getType(), true,GlobalVariable::InternalLinkage,
1068                              C, "str", Callee->getParent());
1069       EmitPutS(C, B);
1070       return CI->use_empty() ? (Value*)CI :
1071                           ConstantInt::get(CI->getType(), FormatStr.size()+1);
1072     }
1073
1074     // Optimize specific format strings.
1075     // printf("%c", chr) --> putchar(*(i8*)dst)
1076     if (FormatStr == "%c" && CI->getNumOperands() > 2 &&
1077         isa<IntegerType>(CI->getOperand(2)->getType())) {
1078       EmitPutChar(CI->getOperand(2), B);
1079       return CI->use_empty() ? (Value*)CI : ConstantInt::get(CI->getType(), 1);
1080     }
1081
1082     // printf("%s\n", str) --> puts(str)
1083     if (FormatStr == "%s\n" && CI->getNumOperands() > 2 &&
1084         isa<PointerType>(CI->getOperand(2)->getType()) &&
1085         CI->use_empty()) {
1086       EmitPutS(CI->getOperand(2), B);
1087       return CI;
1088     }
1089     return 0;
1090   }
1091 };
1092
1093 //===---------------------------------------===//
1094 // 'sprintf' Optimizations
1095
1096 struct VISIBILITY_HIDDEN SPrintFOpt : public LibCallOptimization {
1097   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1098     // Require two fixed pointer arguments and an integer result.
1099     const FunctionType *FT = Callee->getFunctionType();
1100     if (FT->getNumParams() != 2 || !isa<PointerType>(FT->getParamType(0)) ||
1101         !isa<PointerType>(FT->getParamType(1)) ||
1102         !isa<IntegerType>(FT->getReturnType()))
1103       return 0;
1104
1105     // Check for a fixed format string.
1106     std::string FormatStr;
1107     if (!GetConstantStringInfo(CI->getOperand(2), FormatStr))
1108       return 0;
1109
1110     // If we just have a format string (nothing else crazy) transform it.
1111     if (CI->getNumOperands() == 3) {
1112       // Make sure there's no % in the constant array.  We could try to handle
1113       // %% -> % in the future if we cared.
1114       for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1115         if (FormatStr[i] == '%')
1116           return 0; // we found a format specifier, bail out.
1117
1118       // sprintf(str, fmt) -> llvm.memcpy(str, fmt, strlen(fmt)+1, 1)
1119       EmitMemCpy(CI->getOperand(1), CI->getOperand(2), // Copy the nul byte.
1120                  ConstantInt::get(TD->getIntPtrType(), FormatStr.size()+1),1,B);
1121       return ConstantInt::get(CI->getType(), FormatStr.size());
1122     }
1123
1124     // The remaining optimizations require the format string to be "%s" or "%c"
1125     // and have an extra operand.
1126     if (FormatStr.size() != 2 || FormatStr[0] != '%' || CI->getNumOperands() <4)
1127       return 0;
1128
1129     // Decode the second character of the format string.
1130     if (FormatStr[1] == 'c') {
1131       // sprintf(dst, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0
1132       if (!isa<IntegerType>(CI->getOperand(3)->getType())) return 0;
1133       Value *V = B.CreateTrunc(CI->getOperand(3), Type::Int8Ty, "char");
1134       Value *Ptr = CastToCStr(CI->getOperand(1), B);
1135       B.CreateStore(V, Ptr);
1136       Ptr = B.CreateGEP(Ptr, ConstantInt::get(Type::Int32Ty, 1), "nul");
1137       B.CreateStore(Constant::getNullValue(Type::Int8Ty), Ptr);
1138
1139       return ConstantInt::get(CI->getType(), 1);
1140     }
1141
1142     if (FormatStr[1] == 's') {
1143       // sprintf(dest, "%s", str) -> llvm.memcpy(dest, str, strlen(str)+1, 1)
1144       if (!isa<PointerType>(CI->getOperand(3)->getType())) return 0;
1145
1146       Value *Len = EmitStrLen(CI->getOperand(3), B);
1147       Value *IncLen = B.CreateAdd(Len, ConstantInt::get(Len->getType(), 1),
1148                                   "leninc");
1149       EmitMemCpy(CI->getOperand(1), CI->getOperand(3), IncLen, 1, B);
1150
1151       // The sprintf result is the unincremented number of bytes in the string.
1152       return B.CreateIntCast(Len, CI->getType(), false);
1153     }
1154     return 0;
1155   }
1156 };
1157
1158 //===---------------------------------------===//
1159 // 'fwrite' Optimizations
1160
1161 struct VISIBILITY_HIDDEN FWriteOpt : public LibCallOptimization {
1162   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1163     // Require a pointer, an integer, an integer, a pointer, returning integer.
1164     const FunctionType *FT = Callee->getFunctionType();
1165     if (FT->getNumParams() != 4 || !isa<PointerType>(FT->getParamType(0)) ||
1166         !isa<IntegerType>(FT->getParamType(1)) ||
1167         !isa<IntegerType>(FT->getParamType(2)) ||
1168         !isa<PointerType>(FT->getParamType(3)) ||
1169         !isa<IntegerType>(FT->getReturnType()))
1170       return 0;
1171
1172     // Get the element size and count.
1173     ConstantInt *SizeC = dyn_cast<ConstantInt>(CI->getOperand(2));
1174     ConstantInt *CountC = dyn_cast<ConstantInt>(CI->getOperand(3));
1175     if (!SizeC || !CountC) return 0;
1176     uint64_t Bytes = SizeC->getZExtValue()*CountC->getZExtValue();
1177
1178     // If this is writing zero records, remove the call (it's a noop).
1179     if (Bytes == 0)
1180       return ConstantInt::get(CI->getType(), 0);
1181
1182     // If this is writing one byte, turn it into fputc.
1183     if (Bytes == 1) {  // fwrite(S,1,1,F) -> fputc(S[0],F)
1184       Value *Char = B.CreateLoad(CastToCStr(CI->getOperand(1), B), "char");
1185       EmitFPutC(Char, CI->getOperand(4), B);
1186       return ConstantInt::get(CI->getType(), 1);
1187     }
1188
1189     return 0;
1190   }
1191 };
1192
1193 //===---------------------------------------===//
1194 // 'fputs' Optimizations
1195
1196 struct VISIBILITY_HIDDEN FPutsOpt : public LibCallOptimization {
1197   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1198     // Require two pointers.  Also, we can't optimize if return value is used.
1199     const FunctionType *FT = Callee->getFunctionType();
1200     if (FT->getNumParams() != 2 || !isa<PointerType>(FT->getParamType(0)) ||
1201         !isa<PointerType>(FT->getParamType(1)) ||
1202         !CI->use_empty())
1203       return 0;
1204
1205     // fputs(s,F) --> fwrite(s,1,strlen(s),F)
1206     uint64_t Len = GetStringLength(CI->getOperand(1));
1207     if (!Len) return 0;
1208     EmitFWrite(CI->getOperand(1), ConstantInt::get(TD->getIntPtrType(), Len-1),
1209                CI->getOperand(2), B);
1210     return CI;  // Known to have no uses (see above).
1211   }
1212 };
1213
1214 //===---------------------------------------===//
1215 // 'fprintf' Optimizations
1216
1217 struct VISIBILITY_HIDDEN FPrintFOpt : public LibCallOptimization {
1218   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
1219     // Require two fixed paramters as pointers and integer result.
1220     const FunctionType *FT = Callee->getFunctionType();
1221     if (FT->getNumParams() != 2 || !isa<PointerType>(FT->getParamType(0)) ||
1222         !isa<PointerType>(FT->getParamType(1)) ||
1223         !isa<IntegerType>(FT->getReturnType()))
1224       return 0;
1225
1226     // All the optimizations depend on the format string.
1227     std::string FormatStr;
1228     if (!GetConstantStringInfo(CI->getOperand(2), FormatStr))
1229       return 0;
1230
1231     // fprintf(F, "foo") --> fwrite("foo", 3, 1, F)
1232     if (CI->getNumOperands() == 3) {
1233       for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
1234         if (FormatStr[i] == '%')  // Could handle %% -> % if we cared.
1235           return 0; // We found a format specifier.
1236
1237       EmitFWrite(CI->getOperand(2), ConstantInt::get(TD->getIntPtrType(),
1238                                                      FormatStr.size()),
1239                  CI->getOperand(1), B);
1240       return ConstantInt::get(CI->getType(), FormatStr.size());
1241     }
1242
1243     // The remaining optimizations require the format string to be "%s" or "%c"
1244     // and have an extra operand.
1245     if (FormatStr.size() != 2 || FormatStr[0] != '%' || CI->getNumOperands() <4)
1246       return 0;
1247
1248     // Decode the second character of the format string.
1249     if (FormatStr[1] == 'c') {
1250       // fprintf(F, "%c", chr) --> *(i8*)dst = chr
1251       if (!isa<IntegerType>(CI->getOperand(3)->getType())) return 0;
1252       EmitFPutC(CI->getOperand(3), CI->getOperand(1), B);
1253       return ConstantInt::get(CI->getType(), 1);
1254     }
1255
1256     if (FormatStr[1] == 's') {
1257       // fprintf(F, "%s", str) -> fputs(str, F)
1258       if (!isa<PointerType>(CI->getOperand(3)->getType()) || !CI->use_empty())
1259         return 0;
1260       EmitFPutS(CI->getOperand(3), CI->getOperand(1), B);
1261       return CI;
1262     }
1263     return 0;
1264   }
1265 };
1266
1267 } // end anonymous namespace.
1268
1269 //===----------------------------------------------------------------------===//
1270 // SimplifyLibCalls Pass Implementation
1271 //===----------------------------------------------------------------------===//
1272
1273 namespace {
1274   /// This pass optimizes well known library functions from libc and libm.
1275   ///
1276   class VISIBILITY_HIDDEN SimplifyLibCalls : public FunctionPass {
1277     StringMap<LibCallOptimization*> Optimizations;
1278     // Miscellaneous LibCall Optimizations
1279     ExitOpt Exit;
1280     // String and Memory LibCall Optimizations
1281     StrCatOpt StrCat; StrChrOpt StrChr; StrCmpOpt StrCmp; StrNCmpOpt StrNCmp;
1282     StrCpyOpt StrCpy; StrLenOpt StrLen; MemCmpOpt MemCmp; MemCpyOpt  MemCpy;
1283     MemMoveOpt MemMove; MemSetOpt MemSet;
1284     // Math Library Optimizations
1285     PowOpt Pow; Exp2Opt Exp2; UnaryDoubleFPOpt UnaryDoubleFP;
1286     // Integer Optimizations
1287     FFSOpt FFS; AbsOpt Abs; IsDigitOpt IsDigit; IsAsciiOpt IsAscii;
1288     ToAsciiOpt ToAscii;
1289     // Formatting and IO Optimizations
1290     SPrintFOpt SPrintF; PrintFOpt PrintF;
1291     FWriteOpt FWrite; FPutsOpt FPuts; FPrintFOpt FPrintF;
1292
1293     bool Modified;  // This is only used by doFinalization.
1294   public:
1295     static char ID; // Pass identification
1296     SimplifyLibCalls() : FunctionPass(&ID) {}
1297
1298     void InitOptimizations();
1299     bool runOnFunction(Function &F);
1300
1301     void setDoesNotAccessMemory(Function &F);
1302     void setOnlyReadsMemory(Function &F);
1303     void setDoesNotThrow(Function &F);
1304     void setDoesNotCapture(Function &F, unsigned n);
1305     void setDoesNotAlias(Function &F, unsigned n);
1306     bool doFinalization(Module &M);
1307
1308     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1309       AU.addRequired<TargetData>();
1310     }
1311   };
1312   char SimplifyLibCalls::ID = 0;
1313 } // end anonymous namespace.
1314
1315 static RegisterPass<SimplifyLibCalls>
1316 X("simplify-libcalls", "Simplify well-known library calls");
1317
1318 // Public interface to the Simplify LibCalls pass.
1319 FunctionPass *llvm::createSimplifyLibCallsPass() {
1320   return new SimplifyLibCalls();
1321 }
1322
1323 /// Optimizations - Populate the Optimizations map with all the optimizations
1324 /// we know.
1325 void SimplifyLibCalls::InitOptimizations() {
1326   // Miscellaneous LibCall Optimizations
1327   Optimizations["exit"] = &Exit;
1328
1329   // String and Memory LibCall Optimizations
1330   Optimizations["strcat"] = &StrCat;
1331   Optimizations["strchr"] = &StrChr;
1332   Optimizations["strcmp"] = &StrCmp;
1333   Optimizations["strncmp"] = &StrNCmp;
1334   Optimizations["strcpy"] = &StrCpy;
1335   Optimizations["strlen"] = &StrLen;
1336   Optimizations["memcmp"] = &MemCmp;
1337   Optimizations["memcpy"] = &MemCpy;
1338   Optimizations["memmove"] = &MemMove;
1339   Optimizations["memset"] = &MemSet;
1340
1341   // Math Library Optimizations
1342   Optimizations["powf"] = &Pow;
1343   Optimizations["pow"] = &Pow;
1344   Optimizations["powl"] = &Pow;
1345   Optimizations["llvm.pow.f32"] = &Pow;
1346   Optimizations["llvm.pow.f64"] = &Pow;
1347   Optimizations["llvm.pow.f80"] = &Pow;
1348   Optimizations["llvm.pow.f128"] = &Pow;
1349   Optimizations["llvm.pow.ppcf128"] = &Pow;
1350   Optimizations["exp2l"] = &Exp2;
1351   Optimizations["exp2"] = &Exp2;
1352   Optimizations["exp2f"] = &Exp2;
1353   Optimizations["llvm.exp2.ppcf128"] = &Exp2;
1354   Optimizations["llvm.exp2.f128"] = &Exp2;
1355   Optimizations["llvm.exp2.f80"] = &Exp2;
1356   Optimizations["llvm.exp2.f64"] = &Exp2;
1357   Optimizations["llvm.exp2.f32"] = &Exp2;
1358
1359 #ifdef HAVE_FLOORF
1360   Optimizations["floor"] = &UnaryDoubleFP;
1361 #endif
1362 #ifdef HAVE_CEILF
1363   Optimizations["ceil"] = &UnaryDoubleFP;
1364 #endif
1365 #ifdef HAVE_ROUNDF
1366   Optimizations["round"] = &UnaryDoubleFP;
1367 #endif
1368 #ifdef HAVE_RINTF
1369   Optimizations["rint"] = &UnaryDoubleFP;
1370 #endif
1371 #ifdef HAVE_NEARBYINTF
1372   Optimizations["nearbyint"] = &UnaryDoubleFP;
1373 #endif
1374
1375   // Integer Optimizations
1376   Optimizations["ffs"] = &FFS;
1377   Optimizations["ffsl"] = &FFS;
1378   Optimizations["ffsll"] = &FFS;
1379   Optimizations["abs"] = &Abs;
1380   Optimizations["labs"] = &Abs;
1381   Optimizations["llabs"] = &Abs;
1382   Optimizations["isdigit"] = &IsDigit;
1383   Optimizations["isascii"] = &IsAscii;
1384   Optimizations["toascii"] = &ToAscii;
1385
1386   // Formatting and IO Optimizations
1387   Optimizations["sprintf"] = &SPrintF;
1388   Optimizations["printf"] = &PrintF;
1389   Optimizations["fwrite"] = &FWrite;
1390   Optimizations["fputs"] = &FPuts;
1391   Optimizations["fprintf"] = &FPrintF;
1392 }
1393
1394
1395 /// runOnFunction - Top level algorithm.
1396 ///
1397 bool SimplifyLibCalls::runOnFunction(Function &F) {
1398   if (Optimizations.empty())
1399     InitOptimizations();
1400
1401   const TargetData &TD = getAnalysis<TargetData>();
1402
1403   IRBuilder<> Builder;
1404
1405   bool Changed = false;
1406   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
1407     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
1408       // Ignore non-calls.
1409       CallInst *CI = dyn_cast<CallInst>(I++);
1410       if (!CI) continue;
1411
1412       // Ignore indirect calls and calls to non-external functions.
1413       Function *Callee = CI->getCalledFunction();
1414       if (Callee == 0 || !Callee->isDeclaration() ||
1415           !(Callee->hasExternalLinkage() || Callee->hasDLLImportLinkage()))
1416         continue;
1417
1418       // Ignore unknown calls.
1419       const char *CalleeName = Callee->getNameStart();
1420       StringMap<LibCallOptimization*>::iterator OMI =
1421         Optimizations.find(CalleeName, CalleeName+Callee->getNameLen());
1422       if (OMI == Optimizations.end()) continue;
1423
1424       // Set the builder to the instruction after the call.
1425       Builder.SetInsertPoint(BB, I);
1426
1427       // Try to optimize this call.
1428       Value *Result = OMI->second->OptimizeCall(CI, TD, Builder);
1429       if (Result == 0) continue;
1430
1431       DEBUG(DOUT << "SimplifyLibCalls simplified: " << *CI;
1432             DOUT << "  into: " << *Result << "\n");
1433
1434       // Something changed!
1435       Changed = true;
1436       ++NumSimplified;
1437
1438       // Inspect the instruction after the call (which was potentially just
1439       // added) next.
1440       I = CI; ++I;
1441
1442       if (CI != Result && !CI->use_empty()) {
1443         CI->replaceAllUsesWith(Result);
1444         if (!Result->hasName())
1445           Result->takeName(CI);
1446       }
1447       CI->eraseFromParent();
1448     }
1449   }
1450   return Changed;
1451 }
1452
1453 // Utility methods for doFinalization.
1454
1455 void SimplifyLibCalls::setDoesNotAccessMemory(Function &F) {
1456   if (!F.doesNotAccessMemory()) {
1457     F.setDoesNotAccessMemory();
1458     ++NumAnnotated;
1459     Modified = true;
1460   }
1461 }
1462 void SimplifyLibCalls::setOnlyReadsMemory(Function &F) {
1463   if (!F.onlyReadsMemory()) {
1464     F.setOnlyReadsMemory();
1465     ++NumAnnotated;
1466     Modified = true;
1467   }
1468 }
1469 void SimplifyLibCalls::setDoesNotThrow(Function &F) {
1470   if (!F.doesNotThrow()) {
1471     F.setDoesNotThrow();
1472     ++NumAnnotated;
1473     Modified = true;
1474   }
1475 }
1476 void SimplifyLibCalls::setDoesNotCapture(Function &F, unsigned n) {
1477   if (!F.doesNotCapture(n)) {
1478     F.setDoesNotCapture(n);
1479     ++NumAnnotated;
1480     Modified = true;
1481   }
1482 }
1483 void SimplifyLibCalls::setDoesNotAlias(Function &F, unsigned n) {
1484   if (!F.doesNotAlias(n)) {
1485     F.setDoesNotAlias(n);
1486     ++NumAnnotated;
1487     Modified = true;
1488   }
1489 }
1490
1491 /// doFinalization - Add attributes to well-known functions.
1492 ///
1493 bool SimplifyLibCalls::doFinalization(Module &M) {
1494   Modified = false;
1495   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
1496     Function &F = *I;
1497     if (!F.isDeclaration())
1498       continue;
1499
1500     unsigned NameLen = F.getNameLen();
1501     if (!NameLen)
1502       continue;
1503
1504     const FunctionType *FTy = F.getFunctionType();
1505
1506     const char *NameStr = F.getNameStart();
1507     switch (NameStr[0]) {
1508       case 's':
1509         if (NameLen == 6 && !strcmp(NameStr, "strlen")) {
1510           if (FTy->getNumParams() != 1 ||
1511               !isa<PointerType>(FTy->getParamType(0)))
1512             continue;
1513           setOnlyReadsMemory(F);
1514           setDoesNotThrow(F);
1515           setDoesNotCapture(F, 1);
1516         } else if ((NameLen == 6 && !strcmp(NameStr, "strcpy")) ||
1517                    (NameLen == 6 && !strcmp(NameStr, "stpcpy")) ||
1518                    (NameLen == 6 && !strcmp(NameStr, "strcat")) ||
1519                    (NameLen == 7 && !strcmp(NameStr, "strncat")) ||
1520                    (NameLen == 7 && !strcmp(NameStr, "strncpy"))) {
1521           if (FTy->getNumParams() < 2 ||
1522               !isa<PointerType>(FTy->getParamType(1)))
1523             continue;
1524           setDoesNotThrow(F);
1525           setDoesNotCapture(F, 2);
1526         } else if (NameLen == 7 && !strcmp(NameStr, "strxfrm")) {
1527           if (FTy->getNumParams() != 3 ||
1528               !isa<PointerType>(FTy->getParamType(0)) ||
1529               !isa<PointerType>(FTy->getParamType(1)))
1530             continue;
1531           setDoesNotThrow(F);
1532           setDoesNotCapture(F, 1);
1533           setDoesNotCapture(F, 2);
1534         } else if ((NameLen == 6 && !strcmp(NameStr, "strcmp")) ||
1535                    (NameLen == 6 && !strcmp(NameStr, "strspn")) ||
1536                    (NameLen == 6 && !strcmp(NameStr, "strtol")) ||
1537                    (NameLen == 6 && !strcmp(NameStr, "strtod")) ||
1538                    (NameLen == 6 && !strcmp(NameStr, "strtof")) ||
1539                    (NameLen == 7 && !strcmp(NameStr, "strtoul")) ||
1540                    (NameLen == 7 && !strcmp(NameStr, "strtoll")) ||
1541                    (NameLen == 7 && !strcmp(NameStr, "strtold")) ||
1542                    (NameLen == 7 && !strcmp(NameStr, "strncmp")) ||
1543                    (NameLen == 7 && !strcmp(NameStr, "strcspn")) ||
1544                    (NameLen == 7 && !strcmp(NameStr, "strcoll")) ||
1545                    (NameLen == 8 && !strcmp(NameStr, "strtoull")) ||
1546                    (NameLen == 10 && !strcmp(NameStr, "strcasecmp")) ||
1547                    (NameLen == 11 && !strcmp(NameStr, "strncasecmp"))) {
1548           if (FTy->getNumParams() < 2 ||
1549               !isa<PointerType>(FTy->getParamType(0)) ||
1550               !isa<PointerType>(FTy->getParamType(1)))
1551             continue;
1552           setOnlyReadsMemory(F);
1553           setDoesNotThrow(F);
1554           setDoesNotCapture(F, 1);
1555           setDoesNotCapture(F, 2);
1556         } else if ((NameLen == 6 && !strcmp(NameStr, "strstr")) ||
1557                    (NameLen == 7 && !strcmp(NameStr, "strpbrk"))) {
1558           if (FTy->getNumParams() != 2 ||
1559               !isa<PointerType>(FTy->getParamType(1)))
1560             continue;
1561           setOnlyReadsMemory(F);
1562           setDoesNotThrow(F);
1563           setDoesNotCapture(F, 2);
1564         } else if ((NameLen == 6 && !strcmp(NameStr, "strtok")) ||
1565                    (NameLen == 7 && !strcmp(NameStr, "strtok_r"))) {
1566           if (FTy->getNumParams() < 2 ||
1567               !isa<PointerType>(FTy->getParamType(1)))
1568             continue;
1569           setDoesNotThrow(F);
1570           setDoesNotCapture(F, 2);
1571         } else if ((NameLen == 5 && !strcmp(NameStr, "scanf")) ||
1572                    (NameLen == 6 && !strcmp(NameStr, "setbuf")) ||
1573                    (NameLen == 7 && !strcmp(NameStr, "setvbuf"))) {
1574           if (FTy->getNumParams() < 1 ||
1575               !isa<PointerType>(FTy->getParamType(0)))
1576             continue;
1577           setDoesNotThrow(F);
1578           setDoesNotCapture(F, 1);
1579         } else if (NameLen == 6 && !strcmp(NameStr, "sscanf")) {
1580           if (FTy->getNumParams() < 2 ||
1581               !isa<PointerType>(FTy->getParamType(0)) ||
1582               !isa<PointerType>(FTy->getParamType(1)))
1583             continue;
1584           setDoesNotThrow(F);
1585           setDoesNotCapture(F, 1);
1586           setDoesNotCapture(F, 2);
1587         }
1588         break;
1589       case 'm':
1590         if (NameLen == 6 && !strcmp(NameStr, "memcmp")) {
1591           if (FTy->getNumParams() != 3 ||
1592               !isa<PointerType>(FTy->getParamType(0)) ||
1593               !isa<PointerType>(FTy->getParamType(1)))
1594             continue;
1595           setOnlyReadsMemory(F);
1596           setDoesNotThrow(F);
1597           setDoesNotCapture(F, 1);
1598           setDoesNotCapture(F, 2);
1599         } else if ((NameLen == 6 && !strcmp(NameStr, "memchr")) ||
1600                    (NameLen == 7 && !strcmp(NameStr, "memrchr"))) {
1601           if (FTy->getNumParams() != 3)
1602             continue;
1603           setOnlyReadsMemory(F);
1604           setDoesNotThrow(F);
1605         } else if ((NameLen == 6 && !strcmp(NameStr, "memcpy")) ||
1606                    (NameLen == 7 && !strcmp(NameStr, "memccpy")) ||
1607                    (NameLen == 7 && !strcmp(NameStr, "memmove"))) {
1608           if (FTy->getNumParams() < 3 ||
1609               !isa<PointerType>(FTy->getParamType(1)))
1610             continue;
1611           setDoesNotThrow(F);
1612           setDoesNotCapture(F, 2);
1613         }
1614         break;
1615       case 'r':
1616         if (NameLen == 7 && !strcmp(NameStr, "realloc")) {
1617           if (FTy->getNumParams() != 1 ||
1618               !isa<PointerType>(FTy->getParamType(0)) ||
1619               !isa<PointerType>(FTy->getReturnType()))
1620             continue;
1621           setDoesNotThrow(F);
1622           setDoesNotAlias(F, 0);
1623           setDoesNotCapture(F, 1);
1624         } else if (NameLen == 4 && !strcmp(NameStr, "read")) {
1625           if (FTy->getNumParams() != 3 ||
1626               !isa<PointerType>(FTy->getParamType(1)))
1627             continue;
1628           setDoesNotThrow(F);
1629           setDoesNotCapture(F, 2);
1630         } else if ((NameLen == 5 && !strcmp(NameStr, "rmdir")) ||
1631                    (NameLen == 6 && !strcmp(NameStr, "rewind")) ||
1632                    (NameLen == 6 && !strcmp(NameStr, "remove"))) {
1633           if (FTy->getNumParams() != 1 ||
1634               !isa<PointerType>(FTy->getParamType(0)))
1635             continue;
1636           setDoesNotThrow(F);
1637           setDoesNotCapture(F, 1);
1638         } else if (NameLen == 6 && !strcmp(NameStr, "rename")) {
1639           if (FTy->getNumParams() != 2 ||
1640               !isa<PointerType>(FTy->getParamType(0)) ||
1641               !isa<PointerType>(FTy->getParamType(1)))
1642             continue;
1643           setDoesNotThrow(F);
1644           setDoesNotCapture(F, 1);
1645           setDoesNotCapture(F, 2);
1646         }
1647         break;
1648       case 'w':
1649         if (NameLen == 5 && !strcmp(NameStr, "write")) {
1650           if (FTy->getNumParams() != 3 ||
1651               !isa<PointerType>(FTy->getParamType(1)))
1652             continue;
1653           setDoesNotThrow(F);
1654           setDoesNotCapture(F, 2);
1655         }
1656         break;
1657       case 'b':
1658         if (NameLen == 5 && !strcmp(NameStr, "bcopy")) {
1659           if (FTy->getNumParams() != 3 ||
1660               !isa<PointerType>(FTy->getParamType(0)) ||
1661               !isa<PointerType>(FTy->getParamType(1)))
1662             continue;
1663           setDoesNotThrow(F);
1664           setDoesNotCapture(F, 1);
1665           setDoesNotCapture(F, 2);
1666         } else if (NameLen == 4 && !strcmp(NameStr, "bcmp")) {
1667           if (FTy->getNumParams() != 3 ||
1668               !isa<PointerType>(FTy->getParamType(0)) ||
1669               !isa<PointerType>(FTy->getParamType(1)))
1670             continue;
1671           setDoesNotThrow(F);
1672           setOnlyReadsMemory(F);
1673           setDoesNotCapture(F, 1);
1674           setDoesNotCapture(F, 2);
1675         } else if (NameLen == 5 && !strcmp(NameStr, "bzero")) {
1676           if (FTy->getNumParams() != 2 ||
1677               !isa<PointerType>(FTy->getParamType(0)))
1678             continue;
1679           setDoesNotThrow(F);
1680           setDoesNotCapture(F, 1);
1681         }
1682         break;
1683       case 'c':
1684         if (NameLen == 6 && !strcmp(NameStr, "calloc")) {
1685           if (FTy->getNumParams() != 2 ||
1686               !isa<PointerType>(FTy->getReturnType()))
1687             continue;
1688           setDoesNotThrow(F);
1689           setDoesNotAlias(F, 0);
1690         } else if ((NameLen == 5 && !strcmp(NameStr, "chown")) ||
1691                    (NameLen == 8 && !strcmp(NameStr, "clearerr")) ||
1692                    (NameLen == 8 && !strcmp(NameStr, "closedir"))) {
1693           if (FTy->getNumParams() == 0 ||
1694               !isa<PointerType>(FTy->getParamType(0)))
1695             continue;
1696           setDoesNotThrow(F);
1697           setDoesNotCapture(F, 1);
1698         }
1699         break;
1700       case 'a':
1701         if ((NameLen == 4 && !strcmp(NameStr, "atoi")) ||
1702             (NameLen == 4 && !strcmp(NameStr, "atol")) ||
1703             (NameLen == 4 && !strcmp(NameStr, "atof")) ||
1704             (NameLen == 5 && !strcmp(NameStr, "atoll"))) {
1705           if (FTy->getNumParams() != 1 ||
1706               !isa<PointerType>(FTy->getParamType(0)))
1707             continue;
1708           setDoesNotThrow(F);
1709           setOnlyReadsMemory(F);
1710           setDoesNotCapture(F, 1);
1711         } else if (NameLen == 6 && !strcmp(NameStr, "access")) {
1712           if (FTy->getNumParams() != 2 ||
1713               !isa<PointerType>(FTy->getParamType(0)))
1714             continue;
1715           setDoesNotThrow(F);
1716           setDoesNotCapture(F, 1);
1717         }
1718         break;
1719       case 'f':
1720         if ((NameLen == 5 && !strcmp(NameStr, "fopen")) ||
1721             (NameLen == 6 && !strcmp(NameStr, "fdopen"))) {
1722           if (!isa<PointerType>(FTy->getReturnType()))
1723             continue;
1724           setDoesNotThrow(F);
1725           setDoesNotAlias(F, 0);
1726         } else if ((NameLen == 4 && !strcmp(NameStr, "feof")) ||
1727                    (NameLen == 4 && !strcmp(NameStr, "free")) ||
1728                    (NameLen == 5 && !strcmp(NameStr, "fseek")) ||
1729                    (NameLen == 5 && !strcmp(NameStr, "ftell")) ||
1730                    (NameLen == 5 && !strcmp(NameStr, "fgetc")) ||
1731                    (NameLen == 6 && !strcmp(NameStr, "fseeko")) ||
1732                    (NameLen == 6 && !strcmp(NameStr, "ftello")) ||
1733                    (NameLen == 6 && !strcmp(NameStr, "ferror")) ||
1734                    (NameLen == 6 && !strcmp(NameStr, "fileno")) ||
1735                    (NameLen == 6 && !strcmp(NameStr, "fflush")) ||
1736                    (NameLen == 6 && !strcmp(NameStr, "fclose"))) {
1737           if (FTy->getNumParams() == 0 ||
1738               !isa<PointerType>(FTy->getParamType(0)))
1739             continue;
1740           setDoesNotThrow(F);
1741           setDoesNotCapture(F, 1);
1742         } else if ((NameLen == 5 && !strcmp(NameStr, "fputc")) ||
1743                    (NameLen == 5 && !strcmp(NameStr, "fputs"))) {
1744           if (FTy->getNumParams() != 2 ||
1745               !isa<PointerType>(FTy->getParamType(1)))
1746             continue;
1747           setDoesNotThrow(F);
1748           setDoesNotCapture(F, 2);
1749         } else if (NameLen == 5 && !strcmp(NameStr, "fgets")) {
1750           if (FTy->getNumParams() != 3 ||
1751               !isa<PointerType>(FTy->getParamType(0)) ||
1752               !isa<PointerType>(FTy->getParamType(2)))
1753             continue;
1754           setDoesNotThrow(F);
1755           setDoesNotCapture(F, 3);
1756         } else if ((NameLen == 5 && !strcmp(NameStr, "fread")) ||
1757                    (NameLen == 6 && !strcmp(NameStr, "fwrite"))) {
1758           if (FTy->getNumParams() != 4 ||
1759               !isa<PointerType>(FTy->getParamType(0)) ||
1760               !isa<PointerType>(FTy->getParamType(3)))
1761             continue;
1762           setDoesNotThrow(F);
1763           setDoesNotCapture(F, 1);
1764           setDoesNotCapture(F, 4);
1765         } else if ((NameLen == 7 && !strcmp(NameStr, "fgetpos")) ||
1766                    (NameLen == 7 && !strcmp(NameStr, "fsetpos"))) {
1767           if (FTy->getNumParams() != 2 ||
1768               !isa<PointerType>(FTy->getParamType(0)) ||
1769               !isa<PointerType>(FTy->getParamType(1)))
1770             continue;
1771           setDoesNotThrow(F);
1772           setDoesNotCapture(F, 1);
1773           setDoesNotCapture(F, 2);
1774         } else if (NameLen == 6 && !strcmp(NameStr, "fscanf")) {
1775           if (FTy->getNumParams() < 2 ||
1776               !isa<PointerType>(FTy->getParamType(0)) ||
1777               !isa<PointerType>(FTy->getParamType(1)))
1778             continue;
1779           setDoesNotThrow(F);
1780           setDoesNotCapture(F, 1);
1781           setDoesNotCapture(F, 2);
1782         }
1783         break;
1784       case 'g':
1785         if ((NameLen == 4 && !strcmp(NameStr, "getc")) ||
1786             (NameLen == 10 && !strcmp(NameStr, "getlogin_r"))) {
1787           if (FTy->getNumParams() == 0 ||
1788               !isa<PointerType>(FTy->getParamType(0)))
1789             continue;
1790           setDoesNotThrow(F);
1791           setDoesNotCapture(F, 1);
1792         } else if (NameLen == 6 && !strcmp(NameStr, "getenv")) {
1793           if (!FTy->getNumParams() != 1 ||
1794               !isa<PointerType>(FTy->getParamType(0)))
1795             continue;
1796           setDoesNotThrow(F);
1797           setOnlyReadsMemory(F);
1798           setDoesNotCapture(F, 0);
1799         }
1800         break;
1801       case 'u':
1802         if (NameLen == 4 && !strcmp(NameStr, "ungetc")) {
1803           if (!FTy->getNumParams() != 2 ||
1804               !isa<PointerType>(FTy->getParamType(1)))
1805             continue;
1806           setDoesNotThrow(F);
1807           setDoesNotCapture(F, 2);
1808         } else if (NameLen == 6 && !strcmp(NameStr, "unlink")) {
1809           if (!FTy->getNumParams() != 1 ||
1810               !isa<PointerType>(FTy->getParamType(0)))
1811             continue;
1812           setDoesNotThrow(F);
1813           setDoesNotCapture(F, 1);
1814         }
1815         break;
1816       case 'p':
1817         if (NameLen == 4 && !strcmp(NameStr, "putc")) {
1818           if (!FTy->getNumParams() != 2 ||
1819               !isa<PointerType>(FTy->getParamType(1)))
1820             continue;
1821           setDoesNotThrow(F);
1822           setDoesNotCapture(F, 2);
1823         } else if ((NameLen == 4 && !strcmp(NameStr, "puts")) ||
1824                    (NameLen == 6 && !strcmp(NameStr, "perror"))) {
1825           if (!FTy->getNumParams() != 1 ||
1826               !isa<PointerType>(FTy->getParamType(0)))
1827             continue;
1828           setDoesNotThrow(F);
1829           setDoesNotCapture(F, 1);
1830         }
1831         break;
1832       case 'v':
1833         if (NameLen == 6 && !strcmp(NameStr, "vscanf")) {
1834           if (!FTy->getNumParams() != 2 ||
1835               !isa<PointerType>(FTy->getParamType(1)))
1836             continue;
1837           setDoesNotThrow(F);
1838           setDoesNotCapture(F, 1);
1839         } else if ((NameLen == 7 && !strcmp(NameStr, "vsscanf")) ||
1840                    (NameLen == 7 && !strcmp(NameStr, "vfscanf"))) {
1841           if (!FTy->getNumParams() != 4 ||
1842               !isa<PointerType>(FTy->getParamType(1)) ||
1843               !isa<PointerType>(FTy->getParamType(2)))
1844             continue;
1845           setDoesNotThrow(F);
1846           setDoesNotCapture(F, 1);
1847           setDoesNotCapture(F, 2);
1848         }
1849         break;
1850       case 'o':
1851         if (NameLen == 7 && !strcmp(NameStr, "opendir")) {
1852           // The description of fdopendir sounds like opening the same fd
1853           // twice might result in the same DIR* !
1854           if (FTy->getNumParams() != 1 ||
1855               !isa<PointerType>(FTy->getParamType(1)))
1856             continue;
1857           setDoesNotThrow(F);
1858           setDoesNotAlias(F, 0);
1859         }
1860         break;
1861       case 't':
1862         if (NameLen == 7 && !strcmp(NameStr, "tmpfile")) {
1863           if (!isa<PointerType>(FTy->getReturnType()))
1864             continue;
1865           setDoesNotThrow(F);
1866           setDoesNotAlias(F, 0);
1867         }
1868       case 'h':
1869         if ((NameLen == 5 && !strcmp(NameStr, "htonl")) ||
1870             (NameLen == 5 && !strcmp(NameStr, "htons"))) {
1871           setDoesNotThrow(F);
1872           setDoesNotAccessMemory(F);
1873         }
1874         break;
1875       case 'n':
1876         if ((NameLen == 5 && !strcmp(NameStr, "ntohl")) ||
1877             (NameLen == 5 && !strcmp(NameStr, "ntohs"))) {
1878           setDoesNotThrow(F);
1879           setDoesNotAccessMemory(F);
1880         }
1881         break;
1882     }
1883   }
1884   return Modified;
1885 }
1886
1887 // TODO:
1888 //   Additional cases that we need to add to this file:
1889 //
1890 // cbrt:
1891 //   * cbrt(expN(X))  -> expN(x/3)
1892 //   * cbrt(sqrt(x))  -> pow(x,1/6)
1893 //   * cbrt(sqrt(x))  -> pow(x,1/9)
1894 //
1895 // cos, cosf, cosl:
1896 //   * cos(-x)  -> cos(x)
1897 //
1898 // exp, expf, expl:
1899 //   * exp(log(x))  -> x
1900 //
1901 // log, logf, logl:
1902 //   * log(exp(x))   -> x
1903 //   * log(x**y)     -> y*log(x)
1904 //   * log(exp(y))   -> y*log(e)
1905 //   * log(exp2(y))  -> y*log(2)
1906 //   * log(exp10(y)) -> y*log(10)
1907 //   * log(sqrt(x))  -> 0.5*log(x)
1908 //   * log(pow(x,y)) -> y*log(x)
1909 //
1910 // lround, lroundf, lroundl:
1911 //   * lround(cnst) -> cnst'
1912 //
1913 // memcmp:
1914 //   * memcmp(x,y,l)   -> cnst
1915 //      (if all arguments are constant and strlen(x) <= l and strlen(y) <= l)
1916 //
1917 // pow, powf, powl:
1918 //   * pow(exp(x),y)  -> exp(x*y)
1919 //   * pow(sqrt(x),y) -> pow(x,y*0.5)
1920 //   * pow(pow(x,y),z)-> pow(x,y*z)
1921 //
1922 // puts:
1923 //   * puts("") -> putchar("\n")
1924 //
1925 // round, roundf, roundl:
1926 //   * round(cnst) -> cnst'
1927 //
1928 // signbit:
1929 //   * signbit(cnst) -> cnst'
1930 //   * signbit(nncst) -> 0 (if pstv is a non-negative constant)
1931 //
1932 // sqrt, sqrtf, sqrtl:
1933 //   * sqrt(expN(x))  -> expN(x*0.5)
1934 //   * sqrt(Nroot(x)) -> pow(x,1/(2*N))
1935 //   * sqrt(pow(x,y)) -> pow(|x|,y*0.5)
1936 //
1937 // stpcpy:
1938 //   * stpcpy(str, "literal") ->
1939 //           llvm.memcpy(str,"literal",strlen("literal")+1,1)
1940 // strrchr:
1941 //   * strrchr(s,c) -> reverse_offset_of_in(c,s)
1942 //      (if c is a constant integer and s is a constant string)
1943 //   * strrchr(s1,0) -> strchr(s1,0)
1944 //
1945 // strncat:
1946 //   * strncat(x,y,0) -> x
1947 //   * strncat(x,y,0) -> x (if strlen(y) = 0)
1948 //   * strncat(x,y,l) -> strcat(x,y) (if y and l are constants an l > strlen(y))
1949 //
1950 // strncpy:
1951 //   * strncpy(d,s,0) -> d
1952 //   * strncpy(d,s,l) -> memcpy(d,s,l,1)
1953 //      (if s and l are constants)
1954 //
1955 // strpbrk:
1956 //   * strpbrk(s,a) -> offset_in_for(s,a)
1957 //      (if s and a are both constant strings)
1958 //   * strpbrk(s,"") -> 0
1959 //   * strpbrk(s,a) -> strchr(s,a[0]) (if a is constant string of length 1)
1960 //
1961 // strspn, strcspn:
1962 //   * strspn(s,a)   -> const_int (if both args are constant)
1963 //   * strspn("",a)  -> 0
1964 //   * strspn(s,"")  -> 0
1965 //   * strcspn(s,a)  -> const_int (if both args are constant)
1966 //   * strcspn("",a) -> 0
1967 //   * strcspn(s,"") -> strlen(a)
1968 //
1969 // strstr:
1970 //   * strstr(x,x)  -> x
1971 //   * strstr(s1,s2) -> offset_of_s2_in(s1)
1972 //       (if s1 and s2 are constant strings)
1973 //
1974 // tan, tanf, tanl:
1975 //   * tan(atan(x)) -> x
1976 //
1977 // trunc, truncf, truncl:
1978 //   * trunc(cnst) -> cnst'
1979 //
1980 //