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