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