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