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 namespace {
  85 //===----------------------------------------------------------------------===//
  86 // Formatting and IO Optimizations
  87 //===----------------------------------------------------------------------===//
  88
  89 //===---------------------------------------===//
  90 // 'fputs' Optimizations
  91
  92 struct FPutsOpt : public LibCallOptimization {
  93   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
  94     // These optimizations require DataLayout.
  95     if (!TD) return 0;
  96
  97     // Require two pointers.  Also, we can't optimize if return value is used.
  98     FunctionType *FT = Callee->getFunctionType();
  99     if (FT->getNumParams() != 2 || !FT->getParamType(0)->isPointerTy() ||
 100         !FT->getParamType(1)->isPointerTy() ||
 101         !CI->use_empty())
 102       return 0;
 103
 104     // fputs(s,F) --> fwrite(s,1,strlen(s),F)
 105     uint64_t Len = GetStringLength(CI->getArgOperand(0));
 106     if (!Len) return 0;
 107     // Known to have no uses (see above).
 108     return EmitFWrite(CI->getArgOperand(0),
 109                       ConstantInt::get(TD->getIntPtrType(*Context), Len-1),
 110                       CI->getArgOperand(1), B, TD, TLI);
 111   }
 112 };
 113
 114 //===---------------------------------------===//
 115 // 'puts' Optimizations
 116
 117 struct PutsOpt : public LibCallOptimization {
 118   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
 119     // Require one fixed pointer argument and an integer/void result.
 120     FunctionType *FT = Callee->getFunctionType();
 121     if (FT->getNumParams() < 1 || !FT->getParamType(0)->isPointerTy() ||
 122         !(FT->getReturnType()->isIntegerTy() ||
 123           FT->getReturnType()->isVoidTy()))
 124       return 0;
 125
 126     // Check for a constant string.
 127     StringRef Str;
 128     if (!getConstantStringInfo(CI->getArgOperand(0), Str))
 129       return 0;
 130
 131     if (Str.empty() && CI->use_empty()) {
 132       // puts("") -> putchar('\n')
 133       Value *Res = EmitPutChar(B.getInt32('\n'), B, TD, TLI);
 134       if (CI->use_empty() || !Res) return Res;
 135       return B.CreateIntCast(Res, CI->getType(), true);
 136     }
 137
 138     return 0;
 139   }
 140 };
 141
 142 } // end anonymous namespace.
 143
 144 //===----------------------------------------------------------------------===//
 145 // SimplifyLibCalls Pass Implementation
 146 //===----------------------------------------------------------------------===//
 147
 148 namespace {
 149   /// This pass optimizes well known library functions from libc and libm.
 150   ///
 151   class SimplifyLibCalls : public FunctionPass {
 152     TargetLibraryInfo *TLI;
 153
 154     StringMap<LibCallOptimization*> Optimizations;
 155     // Formatting and IO Optimizations
 156     FPutsOpt FPuts;
 157     PutsOpt Puts;
 158
 159     bool Modified;  // This is only used by doInitialization.
 160   public:
 161     static char ID; // Pass identification
 162     SimplifyLibCalls() : FunctionPass(ID) {
 163       initializeSimplifyLibCallsPass(*PassRegistry::getPassRegistry());
 164     }
 165     void AddOpt(LibFunc::Func F, LibCallOptimization* Opt);
 166     void AddOpt(LibFunc::Func F1, LibFunc::Func F2, LibCallOptimization* Opt);
 167
 168     void InitOptimizations();
 169     bool runOnFunction(Function &F);
 170
 171     void setDoesNotAccessMemory(Function &F);
 172     void setOnlyReadsMemory(Function &F);
 173     void setDoesNotThrow(Function &F);
 174     void setDoesNotCapture(Function &F, unsigned n);
 175     void setDoesNotAlias(Function &F, unsigned n);
 176     bool doInitialization(Module &M);
 177
 178     void inferPrototypeAttributes(Function &F);
 179     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 180       AU.addRequired<TargetLibraryInfo>();
 181     }
 182   };
 183 } // end anonymous namespace.
 184
 185 char SimplifyLibCalls::ID = 0;
 186
 187 INITIALIZE_PASS_BEGIN(SimplifyLibCalls, "simplify-libcalls",
 188                       "Simplify well-known library calls", false, false)
 189 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
 190 INITIALIZE_PASS_END(SimplifyLibCalls, "simplify-libcalls",
 191                     "Simplify well-known library calls", false, false)
 192
 193 // Public interface to the Simplify LibCalls pass.
 194 FunctionPass *llvm::createSimplifyLibCallsPass() {
 195   return new SimplifyLibCalls();
 196 }
 197
 198 void SimplifyLibCalls::AddOpt(LibFunc::Func F, LibCallOptimization* Opt) {
 199   if (TLI->has(F))
 200     Optimizations[TLI->getName(F)] = Opt;
 201 }
 202
 203 void SimplifyLibCalls::AddOpt(LibFunc::Func F1, LibFunc::Func F2,
 204                               LibCallOptimization* Opt) {
 205   if (TLI->has(F1) && TLI->has(F2))
 206     Optimizations[TLI->getName(F1)] = Opt;
 207 }
 208
 209 /// Optimizations - Populate the Optimizations map with all the optimizations
 210 /// we know.
 211 void SimplifyLibCalls::InitOptimizations() {
 212   // Formatting and IO Optimizations
 213   AddOpt(LibFunc::fputs, &FPuts);
 214   Optimizations["puts"] = &Puts;
 215 }
 216
 217
 218 /// runOnFunction - Top level algorithm.
 219 ///
 220 bool SimplifyLibCalls::runOnFunction(Function &F) {
 221   TLI = &getAnalysis<TargetLibraryInfo>();
 222
 223   if (Optimizations.empty())
 224     InitOptimizations();
 225
 226   const DataLayout *TD = getAnalysisIfAvailable<DataLayout>();
 227
 228   IRBuilder<> Builder(F.getContext());
 229
 230   bool Changed = false;
 231   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
 232     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
 233       // Ignore non-calls.
 234       CallInst *CI = dyn_cast<CallInst>(I++);
 235       if (!CI) continue;
 236
 237       // Ignore indirect calls and calls to non-external functions.
 238       Function *Callee = CI->getCalledFunction();
 239       if (Callee == 0 || !Callee->isDeclaration() ||
 240           !(Callee->hasExternalLinkage() || Callee->hasDLLImportLinkage()))
 241         continue;
 242
 243       // Ignore unknown calls.
 244       LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
 245       if (!LCO) continue;
 246
 247       // Set the builder to the instruction after the call.
 248       Builder.SetInsertPoint(BB, I);
 249
 250       // Use debug location of CI for all new instructions.
 251       Builder.SetCurrentDebugLocation(CI->getDebugLoc());
 252
 253       // Try to optimize this call.
 254       Value *Result = LCO->OptimizeCall(CI, TD, TLI, Builder);
 255       if (Result == 0) continue;
 256
 257       DEBUG(dbgs() << "SimplifyLibCalls simplified: " << *CI;
 258             dbgs() << "  into: " << *Result << "\n");
 259
 260       // Something changed!
 261       Changed = true;
 262       ++NumSimplified;
 263
 264       // Inspect the instruction after the call (which was potentially just
 265       // added) next.
 266       I = CI; ++I;
 267
 268       if (CI != Result && !CI->use_empty()) {
 269         CI->replaceAllUsesWith(Result);
 270         if (!Result->hasName())
 271           Result->takeName(CI);
 272       }
 273       CI->eraseFromParent();
 274     }
 275   }
 276   return Changed;
 277 }
 278
 279 // Utility methods for doInitialization.
 280
 281 void SimplifyLibCalls::setDoesNotAccessMemory(Function &F) {
 282   if (!F.doesNotAccessMemory()) {
 283     F.setDoesNotAccessMemory();
 284     ++NumAnnotated;
 285     Modified = true;
 286   }
 287 }
 288 void SimplifyLibCalls::setOnlyReadsMemory(Function &F) {
 289   if (!F.onlyReadsMemory()) {
 290     F.setOnlyReadsMemory();
 291     ++NumAnnotated;
 292     Modified = true;
 293   }
 294 }
 295 void SimplifyLibCalls::setDoesNotThrow(Function &F) {
 296   if (!F.doesNotThrow()) {
 297     F.setDoesNotThrow();
 298     ++NumAnnotated;
 299     Modified = true;
 300   }
 301 }
 302 void SimplifyLibCalls::setDoesNotCapture(Function &F, unsigned n) {
 303   if (!F.doesNotCapture(n)) {
 304     F.setDoesNotCapture(n);
 305     ++NumAnnotated;
 306     Modified = true;
 307   }
 308 }
 309 void SimplifyLibCalls::setDoesNotAlias(Function &F, unsigned n) {
 310   if (!F.doesNotAlias(n)) {
 311     F.setDoesNotAlias(n);
 312     ++NumAnnotated;
 313     Modified = true;
 314   }
 315 }
 316
 317
 318 void SimplifyLibCalls::inferPrototypeAttributes(Function &F) {
 319   FunctionType *FTy = F.getFunctionType();
 320
 321   StringRef Name = F.getName();
 322   switch (Name[0]) {
 323   case 's':
 324     if (Name == "strlen") {
 325       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
 326         return;
 327       setOnlyReadsMemory(F);
 328       setDoesNotThrow(F);
 329       setDoesNotCapture(F, 1);
 330     } else if (Name == "strchr" ||
 331                Name == "strrchr") {
 332       if (FTy->getNumParams() != 2 ||
 333           !FTy->getParamType(0)->isPointerTy() ||
 334           !FTy->getParamType(1)->isIntegerTy())
 335         return;
 336       setOnlyReadsMemory(F);
 337       setDoesNotThrow(F);
 338     } else if (Name == "strcpy" ||
 339                Name == "stpcpy" ||
 340                Name == "strcat" ||
 341                Name == "strtol" ||
 342                Name == "strtod" ||
 343                Name == "strtof" ||
 344                Name == "strtoul" ||
 345                Name == "strtoll" ||
 346                Name == "strtold" ||
 347                Name == "strncat" ||
 348                Name == "strncpy" ||
 349                Name == "stpncpy" ||
 350                Name == "strtoull") {
 351       if (FTy->getNumParams() < 2 ||
 352           !FTy->getParamType(1)->isPointerTy())
 353         return;
 354       setDoesNotThrow(F);
 355       setDoesNotCapture(F, 2);
 356     } else if (Name == "strxfrm") {
 357       if (FTy->getNumParams() != 3 ||
 358           !FTy->getParamType(0)->isPointerTy() ||
 359           !FTy->getParamType(1)->isPointerTy())
 360         return;
 361       setDoesNotThrow(F);
 362       setDoesNotCapture(F, 1);
 363       setDoesNotCapture(F, 2);
 364     } else if (Name == "strcmp" ||
 365                Name == "strspn" ||
 366                Name == "strncmp" ||
 367                Name == "strcspn" ||
 368                Name == "strcoll" ||
 369                Name == "strcasecmp" ||
 370                Name == "strncasecmp") {
 371       if (FTy->getNumParams() < 2 ||
 372           !FTy->getParamType(0)->isPointerTy() ||
 373           !FTy->getParamType(1)->isPointerTy())
 374         return;
 375       setOnlyReadsMemory(F);
 376       setDoesNotThrow(F);
 377       setDoesNotCapture(F, 1);
 378       setDoesNotCapture(F, 2);
 379     } else if (Name == "strstr" ||
 380                Name == "strpbrk") {
 381       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
 382         return;
 383       setOnlyReadsMemory(F);
 384       setDoesNotThrow(F);
 385       setDoesNotCapture(F, 2);
 386     } else if (Name == "strtok" ||
 387                Name == "strtok_r") {
 388       if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
 389         return;
 390       setDoesNotThrow(F);
 391       setDoesNotCapture(F, 2);
 392     } else if (Name == "scanf" ||
 393                Name == "setbuf" ||
 394                Name == "setvbuf") {
 395       if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
 396         return;
 397       setDoesNotThrow(F);
 398       setDoesNotCapture(F, 1);
 399     } else if (Name == "strdup" ||
 400                Name == "strndup") {
 401       if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() ||
 402           !FTy->getParamType(0)->isPointerTy())
 403         return;
 404       setDoesNotThrow(F);
 405       setDoesNotAlias(F, 0);
 406       setDoesNotCapture(F, 1);
 407     } else if (Name == "stat" ||
 408                Name == "sscanf" ||
 409                Name == "sprintf" ||
 410                Name == "statvfs") {
 411       if (FTy->getNumParams() < 2 ||
 412           !FTy->getParamType(0)->isPointerTy() ||
 413           !FTy->getParamType(1)->isPointerTy())
 414         return;
 415       setDoesNotThrow(F);
 416       setDoesNotCapture(F, 1);
 417       setDoesNotCapture(F, 2);
 418     } else if (Name == "snprintf") {
 419       if (FTy->getNumParams() != 3 ||
 420           !FTy->getParamType(0)->isPointerTy() ||
 421           !FTy->getParamType(2)->isPointerTy())
 422         return;
 423       setDoesNotThrow(F);
 424       setDoesNotCapture(F, 1);
 425       setDoesNotCapture(F, 3);
 426     } else if (Name == "setitimer") {
 427       if (FTy->getNumParams() != 3 ||
 428           !FTy->getParamType(1)->isPointerTy() ||
 429           !FTy->getParamType(2)->isPointerTy())
 430         return;
 431       setDoesNotThrow(F);
 432       setDoesNotCapture(F, 2);
 433       setDoesNotCapture(F, 3);
 434     } else if (Name == "system") {
 435       if (FTy->getNumParams() != 1 ||
 436           !FTy->getParamType(0)->isPointerTy())
 437         return;
 438       // May throw; "system" is a valid pthread cancellation point.
 439       setDoesNotCapture(F, 1);
 440     }
 441     break;
 442   case 'm':
 443     if (Name == "malloc") {
 444       if (FTy->getNumParams() != 1 ||
 445           !FTy->getReturnType()->isPointerTy())
 446         return;
 447       setDoesNotThrow(F);
 448       setDoesNotAlias(F, 0);
 449     } else if (Name == "memcmp") {
 450       if (FTy->getNumParams() != 3 ||
 451           !FTy->getParamType(0)->isPointerTy() ||
 452           !FTy->getParamType(1)->isPointerTy())
 453         return;
 454       setOnlyReadsMemory(F);
 455       setDoesNotThrow(F);
 456       setDoesNotCapture(F, 1);
 457       setDoesNotCapture(F, 2);
 458     } else if (Name == "memchr" ||
 459                Name == "memrchr") {
 460       if (FTy->getNumParams() != 3)
 461         return;
 462       setOnlyReadsMemory(F);
 463       setDoesNotThrow(F);
 464     } else if (Name == "modf" ||
 465                Name == "modff" ||
 466                Name == "modfl" ||
 467                Name == "memcpy" ||
 468                Name == "memccpy" ||
 469                Name == "memmove") {
 470       if (FTy->getNumParams() < 2 ||
 471           !FTy->getParamType(1)->isPointerTy())
 472         return;
 473       setDoesNotThrow(F);
 474       setDoesNotCapture(F, 2);
 475     } else if (Name == "memalign") {
 476       if (!FTy->getReturnType()->isPointerTy())
 477         return;
 478       setDoesNotAlias(F, 0);
 479     } else if (Name == "mkdir" ||
 480                Name == "mktime") {
 481       if (FTy->getNumParams() == 0 ||
 482           !FTy->getParamType(0)->isPointerTy())
 483         return;
 484       setDoesNotThrow(F);
 485       setDoesNotCapture(F, 1);
 486     }
 487     break;
 488   case 'r':
 489     if (Name == "realloc") {
 490       if (FTy->getNumParams() != 2 ||
 491           !FTy->getParamType(0)->isPointerTy() ||
 492           !FTy->getReturnType()->isPointerTy())
 493         return;
 494       setDoesNotThrow(F);
 495       setDoesNotAlias(F, 0);
 496       setDoesNotCapture(F, 1);
 497     } else if (Name == "read") {
 498       if (FTy->getNumParams() != 3 ||
 499           !FTy->getParamType(1)->isPointerTy())
 500         return;
 501       // May throw; "read" is a valid pthread cancellation point.
 502       setDoesNotCapture(F, 2);
 503     } else if (Name == "rmdir" ||
 504                Name == "rewind" ||
 505                Name == "remove" ||
 506                Name == "realpath") {
 507       if (FTy->getNumParams() < 1 ||
 508           !FTy->getParamType(0)->isPointerTy())
 509         return;
 510       setDoesNotThrow(F);
 511       setDoesNotCapture(F, 1);
 512     } else if (Name == "rename" ||
 513                Name == "readlink") {
 514       if (FTy->getNumParams() < 2 ||
 515           !FTy->getParamType(0)->isPointerTy() ||
 516           !FTy->getParamType(1)->isPointerTy())
 517         return;
 518       setDoesNotThrow(F);
 519       setDoesNotCapture(F, 1);
 520       setDoesNotCapture(F, 2);
 521     }
 522     break;
 523   case 'w':
 524     if (Name == "write") {
 525       if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
 526         return;
 527       // May throw; "write" is a valid pthread cancellation point.
 528       setDoesNotCapture(F, 2);
 529     }
 530     break;
 531   case 'b':
 532     if (Name == "bcopy") {
 533       if (FTy->getNumParams() != 3 ||
 534           !FTy->getParamType(0)->isPointerTy() ||
 535           !FTy->getParamType(1)->isPointerTy())
 536         return;
 537       setDoesNotThrow(F);
 538       setDoesNotCapture(F, 1);
 539       setDoesNotCapture(F, 2);
 540     } else if (Name == "bcmp") {
 541       if (FTy->getNumParams() != 3 ||
 542           !FTy->getParamType(0)->isPointerTy() ||
 543           !FTy->getParamType(1)->isPointerTy())
 544         return;
 545       setDoesNotThrow(F);
 546       setOnlyReadsMemory(F);
 547       setDoesNotCapture(F, 1);
 548       setDoesNotCapture(F, 2);
 549     } else if (Name == "bzero") {
 550       if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
 551         return;
 552       setDoesNotThrow(F);
 553       setDoesNotCapture(F, 1);
 554     }
 555     break;
 556   case 'c':
 557     if (Name == "calloc") {
 558       if (FTy->getNumParams() != 2 ||
 559           !FTy->getReturnType()->isPointerTy())
 560         return;
 561       setDoesNotThrow(F);
 562       setDoesNotAlias(F, 0);
 563     } else if (Name == "chmod" ||
 564                Name == "chown" ||
 565                Name == "ctermid" ||
 566                Name == "clearerr" ||
 567                Name == "closedir") {
 568       if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
 569         return;
 570       setDoesNotThrow(F);
 571       setDoesNotCapture(F, 1);
 572     }
 573     break;
 574   case 'a':
 575     if (Name == "atoi" ||
 576         Name == "atol" ||
 577         Name == "atof" ||
 578         Name == "atoll") {
 579       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
 580         return;
 581       setDoesNotThrow(F);
 582       setOnlyReadsMemory(F);
 583       setDoesNotCapture(F, 1);
 584     } else if (Name == "access") {
 585       if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
 586         return;
 587       setDoesNotThrow(F);
 588       setDoesNotCapture(F, 1);
 589     }
 590     break;
 591   case 'f':
 592     if (Name == "fopen") {
 593       if (FTy->getNumParams() != 2 ||
 594           !FTy->getReturnType()->isPointerTy() ||
 595           !FTy->getParamType(0)->isPointerTy() ||
 596           !FTy->getParamType(1)->isPointerTy())
 597         return;
 598       setDoesNotThrow(F);
 599       setDoesNotAlias(F, 0);
 600       setDoesNotCapture(F, 1);
 601       setDoesNotCapture(F, 2);
 602     } else if (Name == "fdopen") {
 603       if (FTy->getNumParams() != 2 ||
 604           !FTy->getReturnType()->isPointerTy() ||
 605           !FTy->getParamType(1)->isPointerTy())
 606         return;
 607       setDoesNotThrow(F);
 608       setDoesNotAlias(F, 0);
 609       setDoesNotCapture(F, 2);
 610     } else if (Name == "feof" ||
 611                Name == "free" ||
 612                Name == "fseek" ||
 613                Name == "ftell" ||
 614                Name == "fgetc" ||
 615                Name == "fseeko" ||
 616                Name == "ftello" ||
 617                Name == "fileno" ||
 618                Name == "fflush" ||
 619                Name == "fclose" ||
 620                Name == "fsetpos" ||
 621                Name == "flockfile" ||
 622                Name == "funlockfile" ||
 623                Name == "ftrylockfile") {
 624       if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
 625         return;
 626       setDoesNotThrow(F);
 627       setDoesNotCapture(F, 1);
 628     } else if (Name == "ferror") {
 629       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
 630         return;
 631       setDoesNotThrow(F);
 632       setDoesNotCapture(F, 1);
 633       setOnlyReadsMemory(F);
 634     } else if (Name == "fputc" ||
 635                Name == "fstat" ||
 636                Name == "frexp" ||
 637                Name == "frexpf" ||
 638                Name == "frexpl" ||
 639                Name == "fstatvfs") {
 640       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
 641         return;
 642       setDoesNotThrow(F);
 643       setDoesNotCapture(F, 2);
 644     } else if (Name == "fgets") {
 645       if (FTy->getNumParams() != 3 ||
 646           !FTy->getParamType(0)->isPointerTy() ||
 647           !FTy->getParamType(2)->isPointerTy())
 648         return;
 649       setDoesNotThrow(F);
 650       setDoesNotCapture(F, 3);
 651     } else if (Name == "fread" ||
 652                Name == "fwrite") {
 653       if (FTy->getNumParams() != 4 ||
 654           !FTy->getParamType(0)->isPointerTy() ||
 655           !FTy->getParamType(3)->isPointerTy())
 656         return;
 657       setDoesNotThrow(F);
 658       setDoesNotCapture(F, 1);
 659       setDoesNotCapture(F, 4);
 660     } else if (Name == "fputs" ||
 661                Name == "fscanf" ||
 662                Name == "fprintf" ||
 663                Name == "fgetpos") {
 664       if (FTy->getNumParams() < 2 ||
 665           !FTy->getParamType(0)->isPointerTy() ||
 666           !FTy->getParamType(1)->isPointerTy())
 667         return;
 668       setDoesNotThrow(F);
 669       setDoesNotCapture(F, 1);
 670       setDoesNotCapture(F, 2);
 671     }
 672     break;
 673   case 'g':
 674     if (Name == "getc" ||
 675         Name == "getlogin_r" ||
 676         Name == "getc_unlocked") {
 677       if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
 678         return;
 679       setDoesNotThrow(F);
 680       setDoesNotCapture(F, 1);
 681     } else if (Name == "getenv") {
 682       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
 683         return;
 684       setDoesNotThrow(F);
 685       setOnlyReadsMemory(F);
 686       setDoesNotCapture(F, 1);
 687     } else if (Name == "gets" ||
 688                Name == "getchar") {
 689       setDoesNotThrow(F);
 690     } else if (Name == "getitimer") {
 691       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
 692         return;
 693       setDoesNotThrow(F);
 694       setDoesNotCapture(F, 2);
 695     } else if (Name == "getpwnam") {
 696       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
 697         return;
 698       setDoesNotThrow(F);
 699       setDoesNotCapture(F, 1);
 700     }
 701     break;
 702   case 'u':
 703     if (Name == "ungetc") {
 704       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
 705         return;
 706       setDoesNotThrow(F);
 707       setDoesNotCapture(F, 2);
 708     } else if (Name == "uname" ||
 709                Name == "unlink" ||
 710                Name == "unsetenv") {
 711       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
 712         return;
 713       setDoesNotThrow(F);
 714       setDoesNotCapture(F, 1);
 715     } else if (Name == "utime" ||
 716                Name == "utimes") {
 717       if (FTy->getNumParams() != 2 ||
 718           !FTy->getParamType(0)->isPointerTy() ||
 719           !FTy->getParamType(1)->isPointerTy())
 720         return;
 721       setDoesNotThrow(F);
 722       setDoesNotCapture(F, 1);
 723       setDoesNotCapture(F, 2);
 724     }
 725     break;
 726   case 'p':
 727     if (Name == "putc") {
 728       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
 729         return;
 730       setDoesNotThrow(F);
 731       setDoesNotCapture(F, 2);
 732     } else if (Name == "puts" ||
 733                Name == "printf" ||
 734                Name == "perror") {
 735       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
 736         return;
 737       setDoesNotThrow(F);
 738       setDoesNotCapture(F, 1);
 739     } else if (Name == "pread" ||
 740                Name == "pwrite") {
 741       if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
 742         return;
 743       // May throw; these are valid pthread cancellation points.
 744       setDoesNotCapture(F, 2);
 745     } else if (Name == "putchar") {
 746       setDoesNotThrow(F);
 747     } else if (Name == "popen") {
 748       if (FTy->getNumParams() != 2 ||
 749           !FTy->getReturnType()->isPointerTy() ||
 750           !FTy->getParamType(0)->isPointerTy() ||
 751           !FTy->getParamType(1)->isPointerTy())
 752         return;
 753       setDoesNotThrow(F);
 754       setDoesNotAlias(F, 0);
 755       setDoesNotCapture(F, 1);
 756       setDoesNotCapture(F, 2);
 757     } else if (Name == "pclose") {
 758       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
 759         return;
 760       setDoesNotThrow(F);
 761       setDoesNotCapture(F, 1);
 762     }
 763     break;
 764   case 'v':
 765     if (Name == "vscanf") {
 766       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
 767         return;
 768       setDoesNotThrow(F);
 769       setDoesNotCapture(F, 1);
 770     } else if (Name == "vsscanf" ||
 771                Name == "vfscanf") {
 772       if (FTy->getNumParams() != 3 ||
 773           !FTy->getParamType(1)->isPointerTy() ||
 774           !FTy->getParamType(2)->isPointerTy())
 775         return;
 776       setDoesNotThrow(F);
 777       setDoesNotCapture(F, 1);
 778       setDoesNotCapture(F, 2);
 779     } else if (Name == "valloc") {
 780       if (!FTy->getReturnType()->isPointerTy())
 781         return;
 782       setDoesNotThrow(F);
 783       setDoesNotAlias(F, 0);
 784     } else if (Name == "vprintf") {
 785       if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
 786         return;
 787       setDoesNotThrow(F);
 788       setDoesNotCapture(F, 1);
 789     } else if (Name == "vfprintf" ||
 790                Name == "vsprintf") {
 791       if (FTy->getNumParams() != 3 ||
 792           !FTy->getParamType(0)->isPointerTy() ||
 793           !FTy->getParamType(1)->isPointerTy())
 794         return;
 795       setDoesNotThrow(F);
 796       setDoesNotCapture(F, 1);
 797       setDoesNotCapture(F, 2);
 798     } else if (Name == "vsnprintf") {
 799       if (FTy->getNumParams() != 4 ||
 800           !FTy->getParamType(0)->isPointerTy() ||
 801           !FTy->getParamType(2)->isPointerTy())
 802         return;
 803       setDoesNotThrow(F);
 804       setDoesNotCapture(F, 1);
 805       setDoesNotCapture(F, 3);
 806     }
 807     break;
 808   case 'o':
 809     if (Name == "open") {
 810       if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
 811         return;
 812       // May throw; "open" is a valid pthread cancellation point.
 813       setDoesNotCapture(F, 1);
 814     } else if (Name == "opendir") {
 815       if (FTy->getNumParams() != 1 ||
 816           !FTy->getReturnType()->isPointerTy() ||
 817           !FTy->getParamType(0)->isPointerTy())
 818         return;
 819       setDoesNotThrow(F);
 820       setDoesNotAlias(F, 0);
 821       setDoesNotCapture(F, 1);
 822     }
 823     break;
 824   case 't':
 825     if (Name == "tmpfile") {
 826       if (!FTy->getReturnType()->isPointerTy())
 827         return;
 828       setDoesNotThrow(F);
 829       setDoesNotAlias(F, 0);
 830     } else if (Name == "times") {
 831       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
 832         return;
 833       setDoesNotThrow(F);
 834       setDoesNotCapture(F, 1);
 835     }
 836     break;
 837   case 'h':
 838     if (Name == "htonl" ||
 839         Name == "htons") {
 840       setDoesNotThrow(F);
 841       setDoesNotAccessMemory(F);
 842     }
 843     break;
 844   case 'n':
 845     if (Name == "ntohl" ||
 846         Name == "ntohs") {
 847       setDoesNotThrow(F);
 848       setDoesNotAccessMemory(F);
 849     }
 850     break;
 851   case 'l':
 852     if (Name == "lstat") {
 853       if (FTy->getNumParams() != 2 ||
 854           !FTy->getParamType(0)->isPointerTy() ||
 855           !FTy->getParamType(1)->isPointerTy())
 856         return;
 857       setDoesNotThrow(F);
 858       setDoesNotCapture(F, 1);
 859       setDoesNotCapture(F, 2);
 860     } else if (Name == "lchown") {
 861       if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy())
 862         return;
 863       setDoesNotThrow(F);
 864       setDoesNotCapture(F, 1);
 865     }
 866     break;
 867   case 'q':
 868     if (Name == "qsort") {
 869       if (FTy->getNumParams() != 4 || !FTy->getParamType(3)->isPointerTy())
 870         return;
 871       // May throw; places call through function pointer.
 872       setDoesNotCapture(F, 4);
 873     }
 874     break;
 875   case '_':
 876     if (Name == "__strdup" ||
 877         Name == "__strndup") {
 878       if (FTy->getNumParams() < 1 ||
 879           !FTy->getReturnType()->isPointerTy() ||
 880           !FTy->getParamType(0)->isPointerTy())
 881         return;
 882       setDoesNotThrow(F);
 883       setDoesNotAlias(F, 0);
 884       setDoesNotCapture(F, 1);
 885     } else if (Name == "__strtok_r") {
 886       if (FTy->getNumParams() != 3 ||
 887           !FTy->getParamType(1)->isPointerTy())
 888         return;
 889       setDoesNotThrow(F);
 890       setDoesNotCapture(F, 2);
 891     } else if (Name == "_IO_getc") {
 892       if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
 893         return;
 894       setDoesNotThrow(F);
 895       setDoesNotCapture(F, 1);
 896     } else if (Name == "_IO_putc") {
 897       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
 898         return;
 899       setDoesNotThrow(F);
 900       setDoesNotCapture(F, 2);
 901     }
 902     break;
 903   case 1:
 904     if (Name == "\1__isoc99_scanf") {
 905       if (FTy->getNumParams() < 1 ||
 906           !FTy->getParamType(0)->isPointerTy())
 907         return;
 908       setDoesNotThrow(F);
 909       setDoesNotCapture(F, 1);
 910     } else if (Name == "\1stat64" ||
 911                Name == "\1lstat64" ||
 912                Name == "\1statvfs64" ||
 913                Name == "\1__isoc99_sscanf") {
 914       if (FTy->getNumParams() < 1 ||
 915           !FTy->getParamType(0)->isPointerTy() ||
 916           !FTy->getParamType(1)->isPointerTy())
 917         return;
 918       setDoesNotThrow(F);
 919       setDoesNotCapture(F, 1);
 920       setDoesNotCapture(F, 2);
 921     } else if (Name == "\1fopen64") {
 922       if (FTy->getNumParams() != 2 ||
 923           !FTy->getReturnType()->isPointerTy() ||
 924           !FTy->getParamType(0)->isPointerTy() ||
 925           !FTy->getParamType(1)->isPointerTy())
 926         return;
 927       setDoesNotThrow(F);
 928       setDoesNotAlias(F, 0);
 929       setDoesNotCapture(F, 1);
 930       setDoesNotCapture(F, 2);
 931     } else if (Name == "\1fseeko64" ||
 932                Name == "\1ftello64") {
 933       if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
 934         return;
 935       setDoesNotThrow(F);
 936       setDoesNotCapture(F, 1);
 937     } else if (Name == "\1tmpfile64") {
 938       if (!FTy->getReturnType()->isPointerTy())
 939         return;
 940       setDoesNotThrow(F);
 941       setDoesNotAlias(F, 0);
 942     } else if (Name == "\1fstat64" ||
 943                Name == "\1fstatvfs64") {
 944       if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
 945         return;
 946       setDoesNotThrow(F);
 947       setDoesNotCapture(F, 2);
 948     } else if (Name == "\1open64") {
 949       if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
 950         return;
 951       // May throw; "open" is a valid pthread cancellation point.
 952       setDoesNotCapture(F, 1);
 953     }
 954     break;
 955   }
 956 }
 957
 958 /// doInitialization - Add attributes to well-known functions.
 959 ///
 960 bool SimplifyLibCalls::doInitialization(Module &M) {
 961   Modified = false;
 962   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
 963     Function &F = *I;
 964     if (F.isDeclaration() && F.hasName())
 965       inferPrototypeAttributes(F);
 966   }
 967   return Modified;
 968 }
 969
 970 // TODO:
 971 //   Additional cases that we need to add to this file:
 972 //
 973 // cbrt:
 974 //   * cbrt(expN(X))  -> expN(x/3)
 975 //   * cbrt(sqrt(x))  -> pow(x,1/6)
 976 //   * cbrt(sqrt(x))  -> pow(x,1/9)
 977 //
 978 // exp, expf, expl:
 979 //   * exp(log(x))  -> x
 980 //
 981 // log, logf, logl:
 982 //   * log(exp(x))   -> x
 983 //   * log(x**y)     -> y*log(x)
 984 //   * log(exp(y))   -> y*log(e)
 985 //   * log(exp2(y))  -> y*log(2)
 986 //   * log(exp10(y)) -> y*log(10)
 987 //   * log(sqrt(x))  -> 0.5*log(x)
 988 //   * log(pow(x,y)) -> y*log(x)
 989 //
 990 // lround, lroundf, lroundl:
 991 //   * lround(cnst) -> cnst'
 992 //
 993 // pow, powf, powl:
 994 //   * pow(exp(x),y)  -> exp(x*y)
 995 //   * pow(sqrt(x),y) -> pow(x,y*0.5)
 996 //   * pow(pow(x,y),z)-> pow(x,y*z)
 997 //
 998 // round, roundf, roundl:
 999 //   * round(cnst) -> cnst'
1000 //
1001 // signbit:
1002 //   * signbit(cnst) -> cnst'
1003 //   * signbit(nncst) -> 0 (if pstv is a non-negative constant)
1004 //
1005 // sqrt, sqrtf, sqrtl:
1006 //   * sqrt(expN(x))  -> expN(x*0.5)
1007 //   * sqrt(Nroot(x)) -> pow(x,1/(2*N))
1008 //   * sqrt(pow(x,y)) -> pow(|x|,y*0.5)
1009 //
1010 // strchr:
1011 //   * strchr(p, 0) -> strlen(p)
1012 // tan, tanf, tanl:
1013 //   * tan(atan(x)) -> x
1014 //
1015 // trunc, truncf, truncl:
1016 //   * trunc(cnst) -> cnst'
1017 //
1018 //