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