lib/Transforms/Scalar/SimplifyLibCalls.cpp

   1 //===- SimplifyLibCalls.cpp - Optimize specific well-known library calls --===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements a simple pass that applies a variety of small
  11 // optimizations for calls to specific well-known function calls (e.g. runtime
  12 // library functions).   Any optimization that takes the very simple form
  13 // "replace call to library function with simpler code that provides the same
  14 // result" belongs in this file.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #define DEBUG_TYPE "simplify-libcalls"
  19 #include "llvm/Transforms/Scalar.h"
  20 #include "llvm/Transforms/Utils/BuildLibCalls.h"
  21 #include "llvm/IRBuilder.h"
  22 #include "llvm/LLVMContext.h"
  23 #include "llvm/Module.h"
  24 #include "llvm/Pass.h"
  25 #include "llvm/ADT/STLExtras.h"
  26 #include "llvm/ADT/SmallPtrSet.h"
  27 #include "llvm/ADT/Statistic.h"
  28 #include "llvm/ADT/StringMap.h"
  29 #include "llvm/Analysis/ValueTracking.h"
  30 #include "llvm/Support/CommandLine.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/raw_ostream.h"
  33 #include "llvm/DataLayout.h"
  34 #include "llvm/Target/TargetLibraryInfo.h"
  35 #include "llvm/Config/config.h"            // FIXME: Shouldn't depend on host!
  36 using namespace llvm;
  37
  38 STATISTIC(NumSimplified, "Number of library calls simplified");
  39 STATISTIC(NumAnnotated, "Number of attributes added to library functions");
  40
  41 //===----------------------------------------------------------------------===//
  42 // Optimizer Base Class
  43 //===----------------------------------------------------------------------===//
  44
  45 /// This class is the abstract base class for the set of optimizations that
  46 /// corresponds to one library call.
  47 namespace {
  48 class LibCallOptimization {
  49 protected:
  50   Function *Caller;
  51   const DataLayout *TD;
  52   const TargetLibraryInfo *TLI;
  53   LLVMContext* Context;
  54 public:
  55   LibCallOptimization() { }
  56   virtual ~LibCallOptimization() {}
  57
  58   /// CallOptimizer - This pure virtual method is implemented by base classes to
  59   /// do various optimizations.  If this returns null then no transformation was
  60   /// performed.  If it returns CI, then it transformed the call and CI is to be
  61   /// deleted.  If it returns something else, replace CI with the new value and
  62   /// delete CI.
  63   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B)
  64     =0;
  65
  66   Value *OptimizeCall(CallInst *CI, const DataLayout *TD,
  67                       const TargetLibraryInfo *TLI, IRBuilder<> &B) {
  68     Caller = CI->getParent()->getParent();
  69     this->TD = TD;
  70     this->TLI = TLI;
  71     if (CI->getCalledFunction())
  72       Context = &CI->getCalledFunction()->getContext();
  73
  74     // We never change the calling convention.
  75     if (CI->getCallingConv() != llvm::CallingConv::C)
  76       return NULL;
  77
  78     return CallOptimizer(CI->getCalledFunction(), CI, B);
  79   }
  80 };
  81 } // End anonymous namespace.
  82
  83
  84 //===----------------------------------------------------------------------===//
  85 // Helper Functions
  86 //===----------------------------------------------------------------------===//
  87
  88 static bool CallHasFloatingPointArgument(const CallInst *CI) {
  89   for (CallInst::const_op_iterator it = CI->op_begin(), e = CI->op_end();
  90        it != e; ++it) {
  91     if ((*it)->getType()->isFloatingPointTy())
  92       return true;
  93   }
  94   return false;
  95 }
  96
  97 namespace {
  98 //===----------------------------------------------------------------------===//
  99 // Integer Optimizations
 100 //===----------------------------------------------------------------------===//
 101
 102 //===---------------------------------------===//
 103 // 'toascii' Optimizations
 104
 105 struct ToAsciiOpt : public LibCallOptimization {
 106   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 107     FunctionType *FT = Callee->getFunctionType();
 108     // We require i32(i32)
 109     if (FT->getNumParams() != 1 || FT->getReturnType() != FT->getParamType(0) ||
 110         !FT->getParamType(0)->isIntegerTy(32))
 111       return 0;
 112
 113     // isascii(c) -> c & 0x7f
 114     return B.CreateAnd(CI->getArgOperand(0),
 115                        ConstantInt::get(CI->getType(),0x7F));
 116   }
 117 };
 118
 119 //===----------------------------------------------------------------------===//
 120 // Formatting and IO Optimizations
 121 //===----------------------------------------------------------------------===//
 122
 123 //===---------------------------------------===//
 124 // 'printf' Optimizations
 125
 126 struct PrintFOpt : public LibCallOptimization {
 127   Value *OptimizeFixedFormatString(Function *Callee, CallInst *CI,
 128                                    IRBuilder<> &B) {
 129     // Check for a fixed format string.
 130     StringRef FormatStr;
 131     if (!getConstantStringInfo(CI->getArgOperand(0), FormatStr))
 132       return 0;
 133
 134     // Empty format string -> noop.
 135     if (FormatStr.empty())  // Tolerate printf's declared void.
 136       return CI->use_empty() ? (Value*)CI :
 137                                ConstantInt::get(CI->getType(), 0);
 138
 139     // Do not do any of the following transformations if the printf return value
 140     // is used, in general the printf return value is not compatible with either
 141     // putchar() or puts().
 142     if (!CI->use_empty())
 143       return 0;
 144
 145     // printf("x") -> putchar('x'), even for '%'.
 146     if (FormatStr.size() == 1) {
 147       Value *Res = EmitPutChar(B.getInt32(FormatStr[0]), B, TD, TLI);
 148       if (CI->use_empty() || !Res) return Res;
 149       return B.CreateIntCast(Res, CI->getType(), true);
 150     }
 151
 152     // printf("foo\n") --> puts("foo")
 153     if (FormatStr[FormatStr.size()-1] == '\n' &&
 154         FormatStr.find('%') == std::string::npos) {  // no format characters.
 155       // Create a string literal with no \n on it.  We expect the constant merge
 156       // pass to be run after this pass, to merge duplicate strings.
 157       FormatStr = FormatStr.drop_back();
 158       Value *GV = B.CreateGlobalString(FormatStr, "str");
 159       Value *NewCI = EmitPutS(GV, B, TD, TLI);
 160       return (CI->use_empty() || !NewCI) ?
 161               NewCI :
 162               ConstantInt::get(CI->getType(), FormatStr.size()+1);
 163     }
 164
 165     // Optimize specific format strings.
 166     // printf("%c", chr) --> putchar(chr)
 167     if (FormatStr == "%c" && CI->getNumArgOperands() > 1 &&
 168         CI->getArgOperand(1)->getType()->isIntegerTy()) {
 169       Value *Res = EmitPutChar(CI->getArgOperand(1), B, TD, TLI);
 170
 171       if (CI->use_empty() || !Res) return Res;
 172       return B.CreateIntCast(Res, CI->getType(), true);
 173     }
 174
 175     // printf("%s\n", str) --> puts(str)
 176     if (FormatStr == "%s\n" && CI->getNumArgOperands() > 1 &&
 177         CI->getArgOperand(1)->getType()->isPointerTy()) {
 178       return EmitPutS(CI->getArgOperand(1), B, TD, TLI);
 179     }
 180     return 0;
 181   }
 182
 183   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 184     // Require one fixed pointer argument and an integer/void result.
 185     FunctionType *FT = Callee->getFunctionType();
 186     if (FT->getNumParams() < 1 || !FT->getParamType(0)->isPointerTy() ||
 187         !(FT->getReturnType()->isIntegerTy() ||
 188           FT->getReturnType()->isVoidTy()))
 189       return 0;
 190
 191     if (Value *V = OptimizeFixedFormatString(Callee, CI, B)) {
 192       return V;
 193     }
 194
 195     // printf(format, ...) -> iprintf(format, ...) if no floating point
 196     // arguments.
 197     if (TLI->has(LibFunc::iprintf) && !CallHasFloatingPointArgument(CI)) {
 198       Module *M = B.GetInsertBlock()->getParent()->getParent();
 199       Constant *IPrintFFn =
 200         M->getOrInsertFunction("iprintf", FT, Callee->getAttributes());
 201       CallInst *New = cast<CallInst>(CI->clone());
 202       New->setCalledFunction(IPrintFFn);
 203       B.Insert(New);
 204       return New;
 205     }
 206     return 0;
 207   }
 208 };
 209
 210 //===---------------------------------------===//
 211 // 'sprintf' Optimizations
 212
 213 struct SPrintFOpt : public LibCallOptimization {
 214   Value *OptimizeFixedFormatString(Function *Callee, CallInst *CI,
 215                                    IRBuilder<> &B) {
 216     // Check for a fixed format string.
 217     StringRef FormatStr;
 218     if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr))
 219       return 0;
 220
 221     // If we just have a format string (nothing else crazy) transform it.
 222     if (CI->getNumArgOperands() == 2) {
 223       // Make sure there's no % in the constant array.  We could try to handle
 224       // %% -> % in the future if we cared.
 225       for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
 226         if (FormatStr[i] == '%')
 227           return 0; // we found a format specifier, bail out.
 228
 229       // These optimizations require DataLayout.
 230       if (!TD) return 0;
 231
 232       // sprintf(str, fmt) -> llvm.memcpy(str, fmt, strlen(fmt)+1, 1)
 233       B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(1),
 234                      ConstantInt::get(TD->getIntPtrType(*Context), // Copy the
 235                                       FormatStr.size() + 1), 1);   // nul byte.
 236       return ConstantInt::get(CI->getType(), FormatStr.size());
 237     }
 238
 239     // The remaining optimizations require the format string to be "%s" or "%c"
 240     // and have an extra operand.
 241     if (FormatStr.size() != 2 || FormatStr[0] != '%' ||
 242         CI->getNumArgOperands() < 3)
 243       return 0;
 244
 245     // Decode the second character of the format string.
 246     if (FormatStr[1] == 'c') {
 247       // sprintf(dst, "%c", chr) --> *(i8*)dst = chr; *((i8*)dst+1) = 0
 248       if (!CI->getArgOperand(2)->getType()->isIntegerTy()) return 0;
 249       Value *V = B.CreateTrunc(CI->getArgOperand(2), B.getInt8Ty(), "char");
 250       Value *Ptr = CastToCStr(CI->getArgOperand(0), B);
 251       B.CreateStore(V, Ptr);
 252       Ptr = B.CreateGEP(Ptr, B.getInt32(1), "nul");
 253       B.CreateStore(B.getInt8(0), Ptr);
 254
 255       return ConstantInt::get(CI->getType(), 1);
 256     }
 257
 258     if (FormatStr[1] == 's') {
 259       // These optimizations require DataLayout.
 260       if (!TD) return 0;
 261
 262       // sprintf(dest, "%s", str) -> llvm.memcpy(dest, str, strlen(str)+1, 1)
 263       if (!CI->getArgOperand(2)->getType()->isPointerTy()) return 0;
 264
 265       Value *Len = EmitStrLen(CI->getArgOperand(2), B, TD, TLI);
 266       if (!Len)
 267         return 0;
 268       Value *IncLen = B.CreateAdd(Len,
 269                                   ConstantInt::get(Len->getType(), 1),
 270                                   "leninc");
 271       B.CreateMemCpy(CI->getArgOperand(0), CI->getArgOperand(2), IncLen, 1);
 272
 273       // The sprintf result is the unincremented number of bytes in the string.
 274       return B.CreateIntCast(Len, CI->getType(), false);
 275     }
 276     return 0;
 277   }
 278
 279   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 280     // Require two fixed pointer arguments and an integer result.
 281     FunctionType *FT = Callee->getFunctionType();
 282     if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
 283         !FT->getParamType(1)->isPointerTy() ||
 284         !FT->getReturnType()->isIntegerTy())
 285       return 0;
 286
 287     if (Value *V = OptimizeFixedFormatString(Callee, CI, B)) {
 288       return V;
 289     }
 290
 291     // sprintf(str, format, ...) -> siprintf(str, format, ...) if no floating
 292     // point arguments.
 293     if (TLI->has(LibFunc::siprintf) && !CallHasFloatingPointArgument(CI)) {
 294       Module *M = B.GetInsertBlock()->getParent()->getParent();
 295       Constant *SIPrintFFn =
 296         M->getOrInsertFunction("siprintf", FT, Callee->getAttributes());
 297       CallInst *New = cast<CallInst>(CI->clone());
 298       New->setCalledFunction(SIPrintFFn);
 299       B.Insert(New);
 300       return New;
 301     }
 302     return 0;
 303   }
 304 };
 305
 306 //===---------------------------------------===//
 307 // 'fwrite' Optimizations
 308
 309 struct FWriteOpt : public LibCallOptimization {
 310   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 311     // Require a pointer, an integer, an integer, a pointer, returning integer.
 312     FunctionType *FT = Callee->getFunctionType();
 313     if (FT->getNumParams() != 4 || !FT->getParamType(0)->isPointerTy() ||
 314         !FT->getParamType(1)->isIntegerTy() ||
 315         !FT->getParamType(2)->isIntegerTy() ||
 316         !FT->getParamType(3)->isPointerTy() ||
 317         !FT->getReturnType()->isIntegerTy())
 318       return 0;
 319
 320     // Get the element size and count.
 321     ConstantInt *SizeC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
 322     ConstantInt *CountC = dyn_cast<ConstantInt>(CI->getArgOperand(2));
 323     if (!SizeC || !CountC) return 0;
 324     uint64_t Bytes = SizeC->getZExtValue()*CountC->getZExtValue();
 325
 326     // If this is writing zero records, remove the call (it's a noop).
 327     if (Bytes == 0)
 328       return ConstantInt::get(CI->getType(), 0);
 329
 330     // If this is writing one byte, turn it into fputc.
 331     // This optimisation is only valid, if the return value is unused.
 332     if (Bytes == 1 && CI->use_empty()) {  // fwrite(S,1,1,F) -> fputc(S[0],F)
 333       Value *Char = B.CreateLoad(CastToCStr(CI->getArgOperand(0), B), "char");
 334       Value *NewCI = EmitFPutC(Char, CI->getArgOperand(3), B, TD, TLI);
 335       return NewCI ? ConstantInt::get(CI->getType(), 1) : 0;
 336     }
 337
 338     return 0;
 339   }
 340 };
 341
 342 //===---------------------------------------===//
 343 // 'fputs' Optimizations
 344
 345 struct FPutsOpt : public LibCallOptimization {
 346   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 347     // These optimizations require DataLayout.
 348     if (!TD) return 0;
 349
 350     // Require two pointers.  Also, we can't optimize if return value is used.
 351     FunctionType *FT = Callee->getFunctionType();
 352     if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
 353         !FT->getParamType(1)->isPointerTy() ||
 354         !CI->use_empty())
 355       return 0;
 356
 357     // fputs(s,F) --> fwrite(s,1,strlen(s),F)
 358     uint64_t Len = GetStringLength(CI->getArgOperand(0));
 359     if (!Len) return 0;
 360     // Known to have no uses (see above).
 361     return EmitFWrite(CI->getArgOperand(0),
 362                       ConstantInt::get(TD->getIntPtrType(*Context), Len-1),
 363                       CI->getArgOperand(1), B, TD, TLI);
 364   }
 365 };
 366
 367 //===---------------------------------------===//
 368 // 'fprintf' Optimizations
 369
 370 struct FPrintFOpt : public LibCallOptimization {
 371   Value *OptimizeFixedFormatString(Function *Callee, CallInst *CI,
 372                                    IRBuilder<> &B) {
 373     // All the optimizations depend on the format string.
 374     StringRef FormatStr;
 375     if (!getConstantStringInfo(CI->getArgOperand(1), FormatStr))
 376       return 0;
 377
 378     // fprintf(F, "foo") --> fwrite("foo", 3, 1, F)
 379     if (CI->getNumArgOperands() == 2) {
 380       for (unsigned i = 0, e = FormatStr.size(); i != e; ++i)
 381         if (FormatStr[i] == '%')  // Could handle %% -> % if we cared.
 382           return 0; // We found a format specifier.
 383
 384       // These optimizations require DataLayout.
 385       if (!TD) return 0;
 386
 387       Value *NewCI = EmitFWrite(CI->getArgOperand(1),
 388                                 ConstantInt::get(TD->getIntPtrType(*Context),
 389                                                  FormatStr.size()),
 390                                 CI->getArgOperand(0), B, TD, TLI);
 391       return NewCI ? ConstantInt::get(CI->getType(), FormatStr.size()) : 0;
 392     }
 393
 394     // The remaining optimizations require the format string to be "%s" or "%c"
 395     // and have an extra operand.
 396     if (FormatStr.size() != 2 || FormatStr[0] != '%' ||
 397         CI->getNumArgOperands() < 3)
 398       return 0;
 399
 400     // Decode the second character of the format string.
 401     if (FormatStr[1] == 'c') {
 402       // fprintf(F, "%c", chr) --> fputc(chr, F)
 403       if (!CI->getArgOperand(2)->getType()->isIntegerTy()) return 0;
 404       Value *NewCI = EmitFPutC(CI->getArgOperand(2), CI->getArgOperand(0), B,
 405                                TD, TLI);
 406       return NewCI ? ConstantInt::get(CI->getType(), 1) : 0;
 407     }
 408
 409     if (FormatStr[1] == 's') {
 410       // fprintf(F, "%s", str) --> fputs(str, F)
 411       if (!CI->getArgOperand(2)->getType()->isPointerTy() || !CI->use_empty())
 412         return 0;
 413       return EmitFPutS(CI->getArgOperand(2), CI->getArgOperand(0), B, TD, TLI);
 414     }
 415     return 0;
 416   }
 417
 418   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 419     // Require two fixed paramters as pointers and integer result.
 420     FunctionType *FT = Callee->getFunctionType();
 421     if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
 422         !FT->getParamType(1)->isPointerTy() ||
 423         !FT->getReturnType()->isIntegerTy())
 424       return 0;
 425
 426     if (Value *V = OptimizeFixedFormatString(Callee, CI, B)) {
 427       return V;
 428     }
 429
 430     // fprintf(stream, format, ...) -> fiprintf(stream, format, ...) if no
 431     // floating point arguments.
 432     if (TLI->has(LibFunc::fiprintf) && !CallHasFloatingPointArgument(CI)) {
 433       Module *M = B.GetInsertBlock()->getParent()->getParent();
 434       Constant *FIPrintFFn =
 435         M->getOrInsertFunction("fiprintf", FT, Callee->getAttributes());
 436       CallInst *New = cast<CallInst>(CI->clone());
 437       New->setCalledFunction(FIPrintFFn);
 438       B.Insert(New);
 439       return New;
 440     }
 441     return 0;
 442   }
 443 };
 444
 445 //===---------------------------------------===//
 446 // 'puts' Optimizations
 447
 448 struct PutsOpt : public LibCallOptimization {
 449   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 450     // Require one fixed pointer argument and an integer/void result.
 451     FunctionType *FT = Callee->getFunctionType();
 452     if (FT->getNumParams() < 1 || !FT->getParamType(0)->isPointerTy() ||
 453         !(FT->getReturnType()->isIntegerTy() ||
 454           FT->getReturnType()->isVoidTy()))
 455       return 0;
 456
 457     // Check for a constant string.
 458     StringRef Str;
 459     if (!getConstantStringInfo(CI->getArgOperand(0), Str))
 460       return 0;
 461
 462     if (Str.empty() && CI->use_empty()) {
 463       // puts("") -> putchar('\n')
 464       Value *Res = EmitPutChar(B.getInt32('\n'), B, TD, TLI);
 465       if (CI->use_empty() || !Res) return Res;
 466       return B.CreateIntCast(Res, CI->getType(), true);
 467     }
 468
 469     return 0;
 470   }
 471 };
 472
 473 } // end anonymous namespace.
 474
 475 //===----------------------------------------------------------------------===//
 476 // SimplifyLibCalls Pass Implementation
 477 //===----------------------------------------------------------------------===//
 478
 479 namespace {
 480   /// This pass optimizes well known library functions from libc and libm.
 481   ///
 482   class SimplifyLibCalls : public FunctionPass {
 483     TargetLibraryInfo *TLI;
 484
 485     StringMap<LibCallOptimization*> Optimizations;
 486     // Integer Optimizations
 487     ToAsciiOpt ToAscii;
 488     // Formatting and IO Optimizations
 489     SPrintFOpt SPrintF; PrintFOpt PrintF;
 490     FWriteOpt FWrite; FPutsOpt FPuts; FPrintFOpt FPrintF;
 491     PutsOpt Puts;
 492
 493     bool Modified;  // This is only used by doInitialization.
 494   public:
 495     static char ID; // Pass identification
 496     SimplifyLibCalls() : FunctionPass(ID) {
 497       initializeSimplifyLibCallsPass(*PassRegistry::getPassRegistry());
 498     }
 499     void AddOpt(LibFunc::Func F, LibCallOptimization* Opt);
 500     void AddOpt(LibFunc::Func F1, LibFunc::Func F2, LibCallOptimization* Opt);
 501
 502     void InitOptimizations();
 503     bool runOnFunction(Function &F);
 504
 505     void setDoesNotAccessMemory(Function &F);
 506     void setOnlyReadsMemory(Function &F);
 507     void setDoesNotThrow(Function &F);
 508     void setDoesNotCapture(Function &F, unsigned n);
 509     void setDoesNotAlias(Function &F, unsigned n);
 510     bool doInitialization(Module &M);
 511
 512     void inferPrototypeAttributes(Function &F);
 513     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 514       AU.addRequired<TargetLibraryInfo>();
 515     }
 516   };
 517 } // end anonymous namespace.
 518
 519 char SimplifyLibCalls::ID = 0;
 520
 521 INITIALIZE_PASS_BEGIN(SimplifyLibCalls, "simplify-libcalls",
 522                       "Simplify well-known library calls", false, false)
 523 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
 524 INITIALIZE_PASS_END(SimplifyLibCalls, "simplify-libcalls",
 525                     "Simplify well-known library calls", false, false)
 526
 527 // Public interface to the Simplify LibCalls pass.
 528 FunctionPass *llvm::createSimplifyLibCallsPass() {
 529   return new SimplifyLibCalls();
 530 }
 531
 532 void SimplifyLibCalls::AddOpt(LibFunc::Func F, LibCallOptimization* Opt) {
 533   if (TLI->has(F))
 534     Optimizations[TLI->getName(F)] = Opt;
 535 }
 536
 537 void SimplifyLibCalls::AddOpt(LibFunc::Func F1, LibFunc::Func F2,
 538                               LibCallOptimization* Opt) {
 539   if (TLI->has(F1) && TLI->has(F2))
 540     Optimizations[TLI->getName(F1)] = Opt;
 541 }
 542
 543 /// Optimizations - Populate the Optimizations map with all the optimizations
 544 /// we know.
 545 void SimplifyLibCalls::InitOptimizations() {
 546   // Integer Optimizations
 547   Optimizations["toascii"] = &ToAscii;
 548
 549   // Formatting and IO Optimizations
 550   Optimizations["sprintf"] = &SPrintF;
 551   Optimizations["printf"] = &PrintF;
 552   AddOpt(LibFunc::fwrite, &FWrite);
 553   AddOpt(LibFunc::fputs, &FPuts);
 554   Optimizations["fprintf"] = &FPrintF;
 555   Optimizations["puts"] = &Puts;
 556 }
 557
 558
 559 /// runOnFunction - Top level algorithm.
 560 ///
 561 bool SimplifyLibCalls::runOnFunction(Function &F) {
 562   TLI = &getAnalysis<TargetLibraryInfo>();
 563
 564   if (Optimizations.empty())
 565     InitOptimizations();
 566
 567   const DataLayout *TD = getAnalysisIfAvailable<DataLayout>();
 568
 569   IRBuilder<> Builder(F.getContext());
 570
 571   bool Changed = false;
 572   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
 573     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
 574       // Ignore non-calls.
 575       CallInst *CI = dyn_cast<CallInst>(I++);
 576       if (!CI) continue;
 577
 578       // Ignore indirect calls and calls to non-external functions.
 579       Function *Callee = CI->getCalledFunction();
 580       if (Callee == 0 || !Callee->isDeclaration() ||
 581           !(Callee->hasExternalLinkage() || Callee->hasDLLImportLinkage()))
 582         continue;
 583
 584       // Ignore unknown calls.
 585       LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
 586       if (!LCO) continue;
 587
 588       // Set the builder to the instruction after the call.
 589       Builder.SetInsertPoint(BB, I);
 590
 591       // Use debug location of CI for all new instructions.
 592       Builder.SetCurrentDebugLocation(CI->getDebugLoc());
 593
 594       // Try to optimize this call.
 595       Value *Result = LCO->OptimizeCall(CI, TD, TLI, Builder);
 596       if (Result == 0) continue;
 597
 598       DEBUG(dbgs() << "SimplifyLibCalls simplified: " << *CI;
 599             dbgs() << "  into: " << *Result << "\n");
 600
 601       // Something changed!
 602       Changed = true;
 603       ++NumSimplified;
 604
 605       // Inspect the instruction after the call (which was potentially just
 606       // added) next.
 607       I = CI; ++I;
 608
 609       if (CI != Result && !CI->use_empty()) {
 610         CI->replaceAllUsesWith(Result);
 611         if (!Result->hasName())
 612           Result->takeName(CI);
 613       }
 614       CI->eraseFromParent();
 615     }
 616   }
 617   return Changed;
 618 }
 619
 620 // Utility methods for doInitialization.
 621
 622 void SimplifyLibCalls::setDoesNotAccessMemory(Function &F) {
 623   if (!F.doesNotAccessMemory()) {
 624     F.setDoesNotAccessMemory();
 625     ++NumAnnotated;
 626     Modified = true;
 627   }
 628 }
 629 void SimplifyLibCalls::setOnlyReadsMemory(Function &F) {
 630   if (!F.onlyReadsMemory()) {
 631     F.setOnlyReadsMemory();
 632     ++NumAnnotated;
 633     Modified = true;
 634   }
 635 }
 636 void SimplifyLibCalls::setDoesNotThrow(Function &F) {
 637   if (!F.doesNotThrow()) {
 638     F.setDoesNotThrow();
 639     ++NumAnnotated;
 640     Modified = true;
 641   }
 642 }
 643 void SimplifyLibCalls::setDoesNotCapture(Function &F, unsigned n) {
 644   if (!F.doesNotCapture(n)) {
 645     F.setDoesNotCapture(n);
 646     ++NumAnnotated;
 647     Modified = true;
 648   }
 649 }
 650 void SimplifyLibCalls::setDoesNotAlias(Function &F, unsigned n) {
 651   if (!F.doesNotAlias(n)) {
 652     F.setDoesNotAlias(n);
 653     ++NumAnnotated;
 654     Modified = true;
 655   }
 656 }
 657
 658
 659 void SimplifyLibCalls::inferPrototypeAttributes(Function &F) {
 660   FunctionType *FTy = F.getFunctionType();
 661
 662   StringRef Name = F.getName();
 663   switch (Name[0]) {
 664   case 's':
 665     if (Name == "strlen") {
 666       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
 667         return;
 668       setOnlyReadsMemory(F);
 669       setDoesNotThrow(F);
 670       setDoesNotCapture(F, 1);
 671     } else if (Name == "strchr" ||
 672                Name == "strrchr") {
 673       if (FTy->getNumParams() != 2 ||
 674           !FTy->getParamType(0)->isPointerTy() ||
 675           !FTy->getParamType(1)->isIntegerTy())
 676         return;
 677       setOnlyReadsMemory(F);
 678       setDoesNotThrow(F);
 679     } else if (Name == "strcpy" ||
 680                Name == "stpcpy" ||
 681                Name == "strcat" ||
 682                Name == "strtol" ||
 683                Name == "strtod" ||
 684                Name == "strtof" ||
 685                Name == "strtoul" ||
 686                Name == "strtoll" ||
 687                Name == "strtold" ||
 688                Name == "strncat" ||
 689                Name == "strncpy" ||
 690                Name == "stpncpy" ||
 691                Name == "strtoull") {
 692       if (FTy->getNumParams() < 2 ||
 693           !FTy->getParamType(1)->isPointerTy())
 694         return;
 695       setDoesNotThrow(F);
 696       setDoesNotCapture(F, 2);
 697     } else if (Name == "strxfrm") {
 698       if (FTy->getNumParams() != 3 ||
 699           !FTy->getParamType(0)->isPointerTy() ||
 700           !FTy->getParamType(1)->isPointerTy())
 701         return;
 702       setDoesNotThrow(F);
 703       setDoesNotCapture(F, 1);
 704       setDoesNotCapture(F, 2);
 705     } else if (Name == "strcmp" ||
 706                Name == "strspn" ||
 707                Name == "strncmp" ||
 708                Name == "strcspn" ||
 709                Name == "strcoll" ||
 710                Name == "strcasecmp" ||
 711                Name == "strncasecmp") {
 712       if (FTy->getNumParams() < 2 ||
 713           !FTy->getParamType(0)->isPointerTy() ||
 714           !FTy->getParamType(1)->isPointerTy())
 715         return;
 716       setOnlyReadsMemory(F);
 717       setDoesNotThrow(F);
 718       setDoesNotCapture(F, 1);
 719       setDoesNotCapture(F, 2);
 720     } else if (Name == "strstr" ||
 721                Name == "strpbrk") {
 722       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
 723         return;
 724       setOnlyReadsMemory(F);
 725       setDoesNotThrow(F);
 726       setDoesNotCapture(F, 2);
 727     } else if (Name == "strtok" ||
 728                Name == "strtok_r") {
 729       if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
 730         return;
 731       setDoesNotThrow(F);
 732       setDoesNotCapture(F, 2);
 733     } else if (Name == "scanf" ||
 734                Name == "setbuf" ||
 735                Name == "setvbuf") {
 736       if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
 737         return;
 738       setDoesNotThrow(F);
 739       setDoesNotCapture(F, 1);
 740     } else if (Name == "strdup" ||
 741                Name == "strndup") {
 742       if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() ||
 743           !FTy->getParamType(0)->isPointerTy())
 744         return;
 745       setDoesNotThrow(F);
 746       setDoesNotAlias(F, 0);
 747       setDoesNotCapture(F, 1);
 748     } else if (Name == "stat" ||
 749                Name == "sscanf" ||
 750                Name == "sprintf" ||
 751                Name == "statvfs") {
 752       if (FTy->getNumParams() < 2 ||
 753           !FTy->getParamType(0)->isPointerTy() ||
 754           !FTy->getParamType(1)->isPointerTy())
 755         return;
 756       setDoesNotThrow(F);
 757       setDoesNotCapture(F, 1);
 758       setDoesNotCapture(F, 2);
 759     } else if (Name == "snprintf") {
 760       if (FTy->getNumParams() != 3 ||
 761           !FTy->getParamType(0)->isPointerTy() ||
 762           !FTy->getParamType(2)->isPointerTy())
 763         return;
 764       setDoesNotThrow(F);
 765       setDoesNotCapture(F, 1);
 766       setDoesNotCapture(F, 3);
 767     } else if (Name == "setitimer") {
 768       if (FTy->getNumParams() != 3 ||
 769           !FTy->getParamType(1)->isPointerTy() ||
 770           !FTy->getParamType(2)->isPointerTy())
 771         return;
 772       setDoesNotThrow(F);
 773       setDoesNotCapture(F, 2);
 774       setDoesNotCapture(F, 3);
 775     } else if (Name == "system") {
 776       if (FTy->getNumParams() != 1 ||
 777           !FTy->getParamType(0)->isPointerTy())
 778         return;
 779       // May throw; "system" is a valid pthread cancellation point.
 780       setDoesNotCapture(F, 1);
 781     }
 782     break;
 783   case 'm':
 784     if (Name == "malloc") {
 785       if (FTy->getNumParams() != 1 ||
 786           !FTy->getReturnType()->isPointerTy())
 787         return;
 788       setDoesNotThrow(F);
 789       setDoesNotAlias(F, 0);
 790     } else if (Name == "memcmp") {
 791       if (FTy->getNumParams() != 3 ||
 792           !FTy->getParamType(0)->isPointerTy() ||
 793           !FTy->getParamType(1)->isPointerTy())
 794         return;
 795       setOnlyReadsMemory(F);
 796       setDoesNotThrow(F);
 797       setDoesNotCapture(F, 1);
 798       setDoesNotCapture(F, 2);
 799     } else if (Name == "memchr" ||
 800                Name == "memrchr") {
 801       if (FTy->getNumParams() != 3)
 802         return;
 803       setOnlyReadsMemory(F);
 804       setDoesNotThrow(F);
 805     } else if (Name == "modf" ||
 806                Name == "modff" ||
 807                Name == "modfl" ||
 808                Name == "memcpy" ||
 809                Name == "memccpy" ||
 810                Name == "memmove") {
 811       if (FTy->getNumParams() < 2 ||
 812           !FTy->getParamType(1)->isPointerTy())
 813         return;
 814       setDoesNotThrow(F);
 815       setDoesNotCapture(F, 2);
 816     } else if (Name == "memalign") {
 817       if (!FTy->getReturnType()->isPointerTy())
 818         return;
 819       setDoesNotAlias(F, 0);
 820     } else if (Name == "mkdir" ||
 821                Name == "mktime") {
 822       if (FTy->getNumParams() == 0 ||
 823           !FTy->getParamType(0)->isPointerTy())
 824         return;
 825       setDoesNotThrow(F);
 826       setDoesNotCapture(F, 1);
 827     }
 828     break;
 829   case 'r':
 830     if (Name == "realloc") {
 831       if (FTy->getNumParams() != 2 ||
 832           !FTy->getParamType(0)->isPointerTy() ||
 833           !FTy->getReturnType()->isPointerTy())
 834         return;
 835       setDoesNotThrow(F);
 836       setDoesNotAlias(F, 0);
 837       setDoesNotCapture(F, 1);
 838     } else if (Name == "read") {
 839       if (FTy->getNumParams() != 3 ||
 840           !FTy->getParamType(1)->isPointerTy())
 841         return;
 842       // May throw; "read" is a valid pthread cancellation point.
 843       setDoesNotCapture(F, 2);
 844     } else if (Name == "rmdir" ||
 845                Name == "rewind" ||
 846                Name == "remove" ||
 847                Name == "realpath") {
 848       if (FTy->getNumParams() < 1 ||
 849           !FTy->getParamType(0)->isPointerTy())
 850         return;
 851       setDoesNotThrow(F);
 852       setDoesNotCapture(F, 1);
 853     } else if (Name == "rename" ||
 854                Name == "readlink") {
 855       if (FTy->getNumParams() < 2 ||
 856           !FTy->getParamType(0)->isPointerTy() ||
 857           !FTy->getParamType(1)->isPointerTy())
 858         return;
 859       setDoesNotThrow(F);
 860       setDoesNotCapture(F, 1);
 861       setDoesNotCapture(F, 2);
 862     }
 863     break;
 864   case 'w':
 865     if (Name == "write") {
 866       if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
 867         return;
 868       // May throw; "write" is a valid pthread cancellation point.
 869       setDoesNotCapture(F, 2);
 870     }
 871     break;
 872   case 'b':
 873     if (Name == "bcopy") {
 874       if (FTy->getNumParams() != 3 ||
 875           !FTy->getParamType(0)->isPointerTy() ||
 876           !FTy->getParamType(1)->isPointerTy())
 877         return;
 878       setDoesNotThrow(F);
 879       setDoesNotCapture(F, 1);
 880       setDoesNotCapture(F, 2);
 881     } else if (Name == "bcmp") {
 882       if (FTy->getNumParams() != 3 ||
 883           !FTy->getParamType(0)->isPointerTy() ||
 884           !FTy->getParamType(1)->isPointerTy())
 885         return;
 886       setDoesNotThrow(F);
 887       setOnlyReadsMemory(F);
 888       setDoesNotCapture(F, 1);
 889       setDoesNotCapture(F, 2);
 890     } else if (Name == "bzero") {
 891       if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
 892         return;
 893       setDoesNotThrow(F);
 894       setDoesNotCapture(F, 1);
 895     }
 896     break;
 897   case 'c':
 898     if (Name == "calloc") {
 899       if (FTy->getNumParams() != 2 ||
 900           !FTy->getReturnType()->isPointerTy())
 901         return;
 902       setDoesNotThrow(F);
 903       setDoesNotAlias(F, 0);
 904     } else if (Name == "chmod" ||
 905                Name == "chown" ||
 906                Name == "ctermid" ||
 907                Name == "clearerr" ||
 908                Name == "closedir") {
 909       if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
 910         return;
 911       setDoesNotThrow(F);
 912       setDoesNotCapture(F, 1);
 913     }
 914     break;
 915   case 'a':
 916     if (Name == "atoi" ||
 917         Name == "atol" ||
 918         Name == "atof" ||
 919         Name == "atoll") {
 920       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
 921         return;
 922       setDoesNotThrow(F);
 923       setOnlyReadsMemory(F);
 924       setDoesNotCapture(F, 1);
 925     } else if (Name == "access") {
 926       if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
 927         return;
 928       setDoesNotThrow(F);
 929       setDoesNotCapture(F, 1);
 930     }
 931     break;
 932   case 'f':
 933     if (Name == "fopen") {
 934       if (FTy->getNumParams() != 2 ||
 935           !FTy->getReturnType()->isPointerTy() ||
 936           !FTy->getParamType(0)->isPointerTy() ||
 937           !FTy->getParamType(1)->isPointerTy())
 938         return;
 939       setDoesNotThrow(F);
 940       setDoesNotAlias(F, 0);
 941       setDoesNotCapture(F, 1);
 942       setDoesNotCapture(F, 2);
 943     } else if (Name == "fdopen") {
 944       if (FTy->getNumParams() != 2 ||
 945           !FTy->getReturnType()->isPointerTy() ||
 946           !FTy->getParamType(1)->isPointerTy())
 947         return;
 948       setDoesNotThrow(F);
 949       setDoesNotAlias(F, 0);
 950       setDoesNotCapture(F, 2);
 951     } else if (Name == "feof" ||
 952                Name == "free" ||
 953                Name == "fseek" ||
 954                Name == "ftell" ||
 955                Name == "fgetc" ||
 956                Name == "fseeko" ||
 957                Name == "ftello" ||
 958                Name == "fileno" ||
 959                Name == "fflush" ||
 960                Name == "fclose" ||
 961                Name == "fsetpos" ||
 962                Name == "flockfile" ||
 963                Name == "funlockfile" ||
 964                Name == "ftrylockfile") {
 965       if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
 966         return;
 967       setDoesNotThrow(F);
 968       setDoesNotCapture(F, 1);
 969     } else if (Name == "ferror") {
 970       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
 971         return;
 972       setDoesNotThrow(F);
 973       setDoesNotCapture(F, 1);
 974       setOnlyReadsMemory(F);
 975     } else if (Name == "fputc" ||
 976                Name == "fstat" ||
 977                Name == "frexp" ||
 978                Name == "frexpf" ||
 979                Name == "frexpl" ||
 980                Name == "fstatvfs") {
 981       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
 982         return;
 983       setDoesNotThrow(F);
 984       setDoesNotCapture(F, 2);
 985     } else if (Name == "fgets") {
 986       if (FTy->getNumParams() != 3 ||
 987           !FTy->getParamType(0)->isPointerTy() ||
 988           !FTy->getParamType(2)->isPointerTy())
 989         return;
 990       setDoesNotThrow(F);
 991       setDoesNotCapture(F, 3);
 992     } else if (Name == "fread" ||
 993                Name == "fwrite") {
 994       if (FTy->getNumParams() != 4 ||
 995           !FTy->getParamType(0)->isPointerTy() ||
 996           !FTy->getParamType(3)->isPointerTy())
 997         return;
 998       setDoesNotThrow(F);
 999       setDoesNotCapture(F, 1);
1000       setDoesNotCapture(F, 4);
1001     } else if (Name == "fputs" ||
1002                Name == "fscanf" ||
1003                Name == "fprintf" ||
1004                Name == "fgetpos") {
1005       if (FTy->getNumParams() < 2 ||
1006           !FTy->getParamType(0)->isPointerTy() ||
1007           !FTy->getParamType(1)->isPointerTy())
1008         return;
1009       setDoesNotThrow(F);
1010       setDoesNotCapture(F, 1);
1011       setDoesNotCapture(F, 2);
1012     }
1013     break;
1014   case 'g':
1015     if (Name == "getc" ||
1016         Name == "getlogin_r" ||
1017         Name == "getc_unlocked") {
1018       if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1019         return;
1020       setDoesNotThrow(F);
1021       setDoesNotCapture(F, 1);
1022     } else if (Name == "getenv") {
1023       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1024         return;
1025       setDoesNotThrow(F);
1026       setOnlyReadsMemory(F);
1027       setDoesNotCapture(F, 1);
1028     } else if (Name == "gets" ||
1029                Name == "getchar") {
1030       setDoesNotThrow(F);
1031     } else if (Name == "getitimer") {
1032       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1033         return;
1034       setDoesNotThrow(F);
1035       setDoesNotCapture(F, 2);
1036     } else if (Name == "getpwnam") {
1037       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1038         return;
1039       setDoesNotThrow(F);
1040       setDoesNotCapture(F, 1);
1041     }
1042     break;
1043   case 'u':
1044     if (Name == "ungetc") {
1045       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1046         return;
1047       setDoesNotThrow(F);
1048       setDoesNotCapture(F, 2);
1049     } else if (Name == "uname" ||
1050                Name == "unlink" ||
1051                Name == "unsetenv") {
1052       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1053         return;
1054       setDoesNotThrow(F);
1055       setDoesNotCapture(F, 1);
1056     } else if (Name == "utime" ||
1057                Name == "utimes") {
1058       if (FTy->getNumParams() != 2 ||
1059           !FTy->getParamType(0)->isPointerTy() ||
1060           !FTy->getParamType(1)->isPointerTy())
1061         return;
1062       setDoesNotThrow(F);
1063       setDoesNotCapture(F, 1);
1064       setDoesNotCapture(F, 2);
1065     }
1066     break;
1067   case 'p':
1068     if (Name == "putc") {
1069       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1070         return;
1071       setDoesNotThrow(F);
1072       setDoesNotCapture(F, 2);
1073     } else if (Name == "puts" ||
1074                Name == "printf" ||
1075                Name == "perror") {
1076       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1077         return;
1078       setDoesNotThrow(F);
1079       setDoesNotCapture(F, 1);
1080     } else if (Name == "pread" ||
1081                Name == "pwrite") {
1082       if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
1083         return;
1084       // May throw; these are valid pthread cancellation points.
1085       setDoesNotCapture(F, 2);
1086     } else if (Name == "putchar") {
1087       setDoesNotThrow(F);
1088     } else if (Name == "popen") {
1089       if (FTy->getNumParams() != 2 ||
1090           !FTy->getReturnType()->isPointerTy() ||
1091           !FTy->getParamType(0)->isPointerTy() ||
1092           !FTy->getParamType(1)->isPointerTy())
1093         return;
1094       setDoesNotThrow(F);
1095       setDoesNotAlias(F, 0);
1096       setDoesNotCapture(F, 1);
1097       setDoesNotCapture(F, 2);
1098     } else if (Name == "pclose") {
1099       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1100         return;
1101       setDoesNotThrow(F);
1102       setDoesNotCapture(F, 1);
1103     }
1104     break;
1105   case 'v':
1106     if (Name == "vscanf") {
1107       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1108         return;
1109       setDoesNotThrow(F);
1110       setDoesNotCapture(F, 1);
1111     } else if (Name == "vsscanf" ||
1112                Name == "vfscanf") {
1113       if (FTy->getNumParams() != 3 ||
1114           !FTy->getParamType(1)->isPointerTy() ||
1115           !FTy->getParamType(2)->isPointerTy())
1116         return;
1117       setDoesNotThrow(F);
1118       setDoesNotCapture(F, 1);
1119       setDoesNotCapture(F, 2);
1120     } else if (Name == "valloc") {
1121       if (!FTy->getReturnType()->isPointerTy())
1122         return;
1123       setDoesNotThrow(F);
1124       setDoesNotAlias(F, 0);
1125     } else if (Name == "vprintf") {
1126       if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1127         return;
1128       setDoesNotThrow(F);
1129       setDoesNotCapture(F, 1);
1130     } else if (Name == "vfprintf" ||
1131                Name == "vsprintf") {
1132       if (FTy->getNumParams() != 3 ||
1133           !FTy->getParamType(0)->isPointerTy() ||
1134           !FTy->getParamType(1)->isPointerTy())
1135         return;
1136       setDoesNotThrow(F);
1137       setDoesNotCapture(F, 1);
1138       setDoesNotCapture(F, 2);
1139     } else if (Name == "vsnprintf") {
1140       if (FTy->getNumParams() != 4 ||
1141           !FTy->getParamType(0)->isPointerTy() ||
1142           !FTy->getParamType(2)->isPointerTy())
1143         return;
1144       setDoesNotThrow(F);
1145       setDoesNotCapture(F, 1);
1146       setDoesNotCapture(F, 3);
1147     }
1148     break;
1149   case 'o':
1150     if (Name == "open") {
1151       if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
1152         return;
1153       // May throw; "open" is a valid pthread cancellation point.
1154       setDoesNotCapture(F, 1);
1155     } else if (Name == "opendir") {
1156       if (FTy->getNumParams() != 1 ||
1157           !FTy->getReturnType()->isPointerTy() ||
1158           !FTy->getParamType(0)->isPointerTy())
1159         return;
1160       setDoesNotThrow(F);
1161       setDoesNotAlias(F, 0);
1162       setDoesNotCapture(F, 1);
1163     }
1164     break;
1165   case 't':
1166     if (Name == "tmpfile") {
1167       if (!FTy->getReturnType()->isPointerTy())
1168         return;
1169       setDoesNotThrow(F);
1170       setDoesNotAlias(F, 0);
1171     } else if (Name == "times") {
1172       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1173         return;
1174       setDoesNotThrow(F);
1175       setDoesNotCapture(F, 1);
1176     }
1177     break;
1178   case 'h':
1179     if (Name == "htonl" ||
1180         Name == "htons") {
1181       setDoesNotThrow(F);
1182       setDoesNotAccessMemory(F);
1183     }
1184     break;
1185   case 'n':
1186     if (Name == "ntohl" ||
1187         Name == "ntohs") {
1188       setDoesNotThrow(F);
1189       setDoesNotAccessMemory(F);
1190     }
1191     break;
1192   case 'l':
1193     if (Name == "lstat") {
1194       if (FTy->getNumParams() != 2 ||
1195           !FTy->getParamType(0)->isPointerTy() ||
1196           !FTy->getParamType(1)->isPointerTy())
1197         return;
1198       setDoesNotThrow(F);
1199       setDoesNotCapture(F, 1);
1200       setDoesNotCapture(F, 2);
1201     } else if (Name == "lchown") {
1202       if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy())
1203         return;
1204       setDoesNotThrow(F);
1205       setDoesNotCapture(F, 1);
1206     }
1207     break;
1208   case 'q':
1209     if (Name == "qsort") {
1210       if (FTy->getNumParams() != 4 || !FTy->getParamType(3)->isPointerTy())
1211         return;
1212       // May throw; places call through function pointer.
1213       setDoesNotCapture(F, 4);
1214     }
1215     break;
1216   case '_':
1217     if (Name == "__strdup" ||
1218         Name == "__strndup") {
1219       if (FTy->getNumParams() < 1 ||
1220           !FTy->getReturnType()->isPointerTy() ||
1221           !FTy->getParamType(0)->isPointerTy())
1222         return;
1223       setDoesNotThrow(F);
1224       setDoesNotAlias(F, 0);
1225       setDoesNotCapture(F, 1);
1226     } else if (Name == "__strtok_r") {
1227       if (FTy->getNumParams() != 3 ||
1228           !FTy->getParamType(1)->isPointerTy())
1229         return;
1230       setDoesNotThrow(F);
1231       setDoesNotCapture(F, 2);
1232     } else if (Name == "_IO_getc") {
1233       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1234         return;
1235       setDoesNotThrow(F);
1236       setDoesNotCapture(F, 1);
1237     } else if (Name == "_IO_putc") {
1238       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1239         return;
1240       setDoesNotThrow(F);
1241       setDoesNotCapture(F, 2);
1242     }
1243     break;
1244   case 1:
1245     if (Name == "\1__isoc99_scanf") {
1246       if (FTy->getNumParams() < 1 ||
1247           !FTy->getParamType(0)->isPointerTy())
1248         return;
1249       setDoesNotThrow(F);
1250       setDoesNotCapture(F, 1);
1251     } else if (Name == "\1stat64" ||
1252                Name == "\1lstat64" ||
1253                Name == "\1statvfs64" ||
1254                Name == "\1__isoc99_sscanf") {
1255       if (FTy->getNumParams() < 1 ||
1256           !FTy->getParamType(0)->isPointerTy() ||
1257           !FTy->getParamType(1)->isPointerTy())
1258         return;
1259       setDoesNotThrow(F);
1260       setDoesNotCapture(F, 1);
1261       setDoesNotCapture(F, 2);
1262     } else if (Name == "\1fopen64") {
1263       if (FTy->getNumParams() != 2 ||
1264           !FTy->getReturnType()->isPointerTy() ||
1265           !FTy->getParamType(0)->isPointerTy() ||
1266           !FTy->getParamType(1)->isPointerTy())
1267         return;
1268       setDoesNotThrow(F);
1269       setDoesNotAlias(F, 0);
1270       setDoesNotCapture(F, 1);
1271       setDoesNotCapture(F, 2);
1272     } else if (Name == "\1fseeko64" ||
1273                Name == "\1ftello64") {
1274       if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1275         return;
1276       setDoesNotThrow(F);
1277       setDoesNotCapture(F, 1);
1278     } else if (Name == "\1tmpfile64") {
1279       if (!FTy->getReturnType()->isPointerTy())
1280         return;
1281       setDoesNotThrow(F);
1282       setDoesNotAlias(F, 0);
1283     } else if (Name == "\1fstat64" ||
1284                Name == "\1fstatvfs64") {
1285       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1286         return;
1287       setDoesNotThrow(F);
1288       setDoesNotCapture(F, 2);
1289     } else if (Name == "\1open64") {
1290       if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
1291         return;
1292       // May throw; "open" is a valid pthread cancellation point.
1293       setDoesNotCapture(F, 1);
1294     }
1295     break;
1296   }
1297 }
1298
1299 /// doInitialization - Add attributes to well-known functions.
1300 ///
1301 bool SimplifyLibCalls::doInitialization(Module &M) {
1302   Modified = false;
1303   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
1304     Function &F = *I;
1305     if (F.isDeclaration() && F.hasName())
1306       inferPrototypeAttributes(F);
1307   }
1308   return Modified;
1309 }
1310
1311 // TODO:
1312 //   Additional cases that we need to add to this file:
1313 //
1314 // cbrt:
1315 //   * cbrt(expN(X))  -> expN(x/3)
1316 //   * cbrt(sqrt(x))  -> pow(x,1/6)
1317 //   * cbrt(sqrt(x))  -> pow(x,1/9)
1318 //
1319 // exp, expf, expl:
1320 //   * exp(log(x))  -> x
1321 //
1322 // log, logf, logl:
1323 //   * log(exp(x))   -> x
1324 //   * log(x**y)     -> y*log(x)
1325 //   * log(exp(y))   -> y*log(e)
1326 //   * log(exp2(y))  -> y*log(2)
1327 //   * log(exp10(y)) -> y*log(10)
1328 //   * log(sqrt(x))  -> 0.5*log(x)
1329 //   * log(pow(x,y)) -> y*log(x)
1330 //
1331 // lround, lroundf, lroundl:
1332 //   * lround(cnst) -> cnst'
1333 //
1334 // pow, powf, powl:
1335 //   * pow(exp(x),y)  -> exp(x*y)
1336 //   * pow(sqrt(x),y) -> pow(x,y*0.5)
1337 //   * pow(pow(x,y),z)-> pow(x,y*z)
1338 //
1339 // round, roundf, roundl:
1340 //   * round(cnst) -> cnst'
1341 //
1342 // signbit:
1343 //   * signbit(cnst) -> cnst'
1344 //   * signbit(nncst) -> 0 (if pstv is a non-negative constant)
1345 //
1346 // sqrt, sqrtf, sqrtl:
1347 //   * sqrt(expN(x))  -> expN(x*0.5)
1348 //   * sqrt(Nroot(x)) -> pow(x,1/(2*N))
1349 //   * sqrt(pow(x,y)) -> pow(|x|,y*0.5)
1350 //
1351 // strchr:
1352 //   * strchr(p, 0) -> strlen(p)
1353 // tan, tanf, tanl:
1354 //   * tan(atan(x)) -> x
1355 //
1356 // trunc, truncf, truncl:
1357 //   * trunc(cnst) -> cnst'
1358 //
1359 //