lib/Transforms/IPO/FunctionAttrs.cpp

   1 //===- FunctionAttrs.cpp - Pass which marks functions attributes ----------===//
   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 interprocedural pass which walks the
  11 // call-graph, looking for functions which do not access or only read
  12 // non-local memory, and marking them readnone/readonly.  In addition,
  13 // it marks function arguments (of pointer type) 'nocapture' if a call
  14 // to the function does not create any copies of the pointer value that
  15 // outlive the call.  This more or less means that the pointer is only
  16 // dereferenced, and not returned from the function or stored in a global.
  17 // Finally, well-known library call declarations are marked with all
  18 // attributes that are consistent with the function's standard definition.
  19 // This pass is implemented as a bottom-up traversal of the call-graph.
  20 //
  21 //===----------------------------------------------------------------------===//
  22
  23 #define DEBUG_TYPE "functionattrs"
  24 #include "llvm/Transforms/IPO.h"
  25 #include "llvm/ADT/SCCIterator.h"
  26 #include "llvm/ADT/SetVector.h"
  27 #include "llvm/ADT/SmallSet.h"
  28 #include "llvm/ADT/Statistic.h"
  29 #include "llvm/Analysis/AliasAnalysis.h"
  30 #include "llvm/Analysis/CallGraph.h"
  31 #include "llvm/Analysis/CallGraphSCCPass.h"
  32 #include "llvm/Analysis/CaptureTracking.h"
  33 #include "llvm/IR/GlobalVariable.h"
  34 #include "llvm/IR/IntrinsicInst.h"
  35 #include "llvm/IR/LLVMContext.h"
  36 #include "llvm/Support/InstIterator.h"
  37 #include "llvm/Target/TargetLibraryInfo.h"
  38 using namespace llvm;
  39
  40 STATISTIC(NumReadNone, "Number of functions marked readnone");
  41 STATISTIC(NumReadOnly, "Number of functions marked readonly");
  42 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
  43 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
  44 STATISTIC(NumAnnotated, "Number of attributes added to library functions");
  45
  46 namespace {
  47   struct FunctionAttrs : public CallGraphSCCPass {
  48     static char ID; // Pass identification, replacement for typeid
  49     FunctionAttrs() : CallGraphSCCPass(ID), AA(0) {
  50       initializeFunctionAttrsPass(*PassRegistry::getPassRegistry());
  51     }
  52
  53     // runOnSCC - Analyze the SCC, performing the transformation if possible.
  54     bool runOnSCC(CallGraphSCC &SCC);
  55
  56     // AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
  57     bool AddReadAttrs(const CallGraphSCC &SCC);
  58
  59     // AddNoCaptureAttrs - Deduce nocapture attributes for the SCC.
  60     bool AddNoCaptureAttrs(const CallGraphSCC &SCC);
  61
  62     // IsFunctionMallocLike - Does this function allocate new memory?
  63     bool IsFunctionMallocLike(Function *F,
  64                               SmallPtrSet<Function*, 8> &) const;
  65
  66     // AddNoAliasAttrs - Deduce noalias attributes for the SCC.
  67     bool AddNoAliasAttrs(const CallGraphSCC &SCC);
  68
  69     // Utility methods used by inferPrototypeAttributes to add attributes
  70     // and maintain annotation statistics.
  71
  72     void setDoesNotAccessMemory(Function &F) {
  73       if (!F.doesNotAccessMemory()) {
  74         F.setDoesNotAccessMemory();
  75         ++NumAnnotated;
  76       }
  77     }
  78
  79     void setOnlyReadsMemory(Function &F) {
  80       if (!F.onlyReadsMemory()) {
  81         F.setOnlyReadsMemory();
  82         ++NumAnnotated;
  83       }
  84     }
  85
  86     void setDoesNotThrow(Function &F) {
  87       if (!F.doesNotThrow()) {
  88         F.setDoesNotThrow();
  89         ++NumAnnotated;
  90       }
  91     }
  92
  93     void setDoesNotCapture(Function &F, unsigned n) {
  94       if (!F.doesNotCapture(n)) {
  95         F.setDoesNotCapture(n);
  96         ++NumAnnotated;
  97       }
  98     }
  99
 100     void setDoesNotAlias(Function &F, unsigned n) {
 101       if (!F.doesNotAlias(n)) {
 102         F.setDoesNotAlias(n);
 103         ++NumAnnotated;
 104       }
 105     }
 106
 107     // inferPrototypeAttributes - Analyze the name and prototype of the
 108     // given function and set any applicable attributes.  Returns true
 109     // if any attributes were set and false otherwise.
 110     bool inferPrototypeAttributes(Function &F);
 111
 112     // annotateLibraryCalls - Adds attributes to well-known standard library
 113     // call declarations.
 114     bool annotateLibraryCalls(const CallGraphSCC &SCC);
 115
 116     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 117       AU.setPreservesCFG();
 118       AU.addRequired<AliasAnalysis>();
 119       AU.addRequired<TargetLibraryInfo>();
 120       CallGraphSCCPass::getAnalysisUsage(AU);
 121     }
 122
 123   private:
 124     AliasAnalysis *AA;
 125     TargetLibraryInfo *TLI;
 126   };
 127 }
 128
 129 char FunctionAttrs::ID = 0;
 130 INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs",
 131                 "Deduce function attributes", false, false)
 132 INITIALIZE_AG_DEPENDENCY(CallGraph)
 133 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
 134 INITIALIZE_PASS_END(FunctionAttrs, "functionattrs",
 135                 "Deduce function attributes", false, false)
 136
 137 Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); }
 138
 139
 140 /// AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
 141 bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) {
 142   SmallPtrSet<Function*, 8> SCCNodes;
 143
 144   // Fill SCCNodes with the elements of the SCC.  Used for quickly
 145   // looking up whether a given CallGraphNode is in this SCC.
 146   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
 147     SCCNodes.insert((*I)->getFunction());
 148
 149   // Check if any of the functions in the SCC read or write memory.  If they
 150   // write memory then they can't be marked readnone or readonly.
 151   bool ReadsMemory = false;
 152   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
 153     Function *F = (*I)->getFunction();
 154
 155     if (F == 0)
 156       // External node - may write memory.  Just give up.
 157       return false;
 158
 159     AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(F);
 160     if (MRB == AliasAnalysis::DoesNotAccessMemory)
 161       // Already perfect!
 162       continue;
 163
 164     // Definitions with weak linkage may be overridden at linktime with
 165     // something that writes memory, so treat them like declarations.
 166     if (F->isDeclaration() || F->mayBeOverridden()) {
 167       if (!AliasAnalysis::onlyReadsMemory(MRB))
 168         // May write memory.  Just give up.
 169         return false;
 170
 171       ReadsMemory = true;
 172       continue;
 173     }
 174
 175     // Scan the function body for instructions that may read or write memory.
 176     for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
 177       Instruction *I = &*II;
 178
 179       // Some instructions can be ignored even if they read or write memory.
 180       // Detect these now, skipping to the next instruction if one is found.
 181       CallSite CS(cast<Value>(I));
 182       if (CS) {
 183         // Ignore calls to functions in the same SCC.
 184         if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
 185           continue;
 186         AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(CS);
 187         // If the call doesn't access arbitrary memory, we may be able to
 188         // figure out something.
 189         if (AliasAnalysis::onlyAccessesArgPointees(MRB)) {
 190           // If the call does access argument pointees, check each argument.
 191           if (AliasAnalysis::doesAccessArgPointees(MRB))
 192             // Check whether all pointer arguments point to local memory, and
 193             // ignore calls that only access local memory.
 194             for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
 195                  CI != CE; ++CI) {
 196               Value *Arg = *CI;
 197               if (Arg->getType()->isPointerTy()) {
 198                 AliasAnalysis::Location Loc(Arg,
 199                                             AliasAnalysis::UnknownSize,
 200                                             I->getMetadata(LLVMContext::MD_tbaa));
 201                 if (!AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) {
 202                   if (MRB & AliasAnalysis::Mod)
 203                     // Writes non-local memory.  Give up.
 204                     return false;
 205                   if (MRB & AliasAnalysis::Ref)
 206                     // Ok, it reads non-local memory.
 207                     ReadsMemory = true;
 208                 }
 209               }
 210             }
 211           continue;
 212         }
 213         // The call could access any memory. If that includes writes, give up.
 214         if (MRB & AliasAnalysis::Mod)
 215           return false;
 216         // If it reads, note it.
 217         if (MRB & AliasAnalysis::Ref)
 218           ReadsMemory = true;
 219         continue;
 220       } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
 221         // Ignore non-volatile loads from local memory. (Atomic is okay here.)
 222         if (!LI->isVolatile()) {
 223           AliasAnalysis::Location Loc = AA->getLocation(LI);
 224           if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true))
 225             continue;
 226         }
 227       } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 228         // Ignore non-volatile stores to local memory. (Atomic is okay here.)
 229         if (!SI->isVolatile()) {
 230           AliasAnalysis::Location Loc = AA->getLocation(SI);
 231           if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true))
 232             continue;
 233         }
 234       } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) {
 235         // Ignore vaargs on local memory.
 236         AliasAnalysis::Location Loc = AA->getLocation(VI);
 237         if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true))
 238           continue;
 239       }
 240
 241       // Any remaining instructions need to be taken seriously!  Check if they
 242       // read or write memory.
 243       if (I->mayWriteToMemory())
 244         // Writes memory.  Just give up.
 245         return false;
 246
 247       // If this instruction may read memory, remember that.
 248       ReadsMemory |= I->mayReadFromMemory();
 249     }
 250   }
 251
 252   // Success!  Functions in this SCC do not access memory, or only read memory.
 253   // Give them the appropriate attribute.
 254   bool MadeChange = false;
 255   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
 256     Function *F = (*I)->getFunction();
 257
 258     if (F->doesNotAccessMemory())
 259       // Already perfect!
 260       continue;
 261
 262     if (F->onlyReadsMemory() && ReadsMemory)
 263       // No change.
 264       continue;
 265
 266     MadeChange = true;
 267
 268     // Clear out any existing attributes.
 269     AttrBuilder B;
 270     B.addAttribute(Attribute::ReadOnly)
 271       .addAttribute(Attribute::ReadNone);
 272     F->removeAttributes(AttributeSet::FunctionIndex,
 273                         AttributeSet::get(F->getContext(),
 274                                           AttributeSet::FunctionIndex, B));
 275
 276     // Add in the new attribute.
 277     F->addAttribute(AttributeSet::FunctionIndex,
 278                     ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone);
 279
 280     if (ReadsMemory)
 281       ++NumReadOnly;
 282     else
 283       ++NumReadNone;
 284   }
 285
 286   return MadeChange;
 287 }
 288
 289 namespace {
 290   // For a given pointer Argument, this retains a list of Arguments of functions
 291   // in the same SCC that the pointer data flows into. We use this to build an
 292   // SCC of the arguments.
 293   struct ArgumentGraphNode {
 294     Argument *Definition;
 295     SmallVector<ArgumentGraphNode*, 4> Uses;
 296   };
 297
 298   class ArgumentGraph {
 299     // We store pointers to ArgumentGraphNode objects, so it's important that
 300     // that they not move around upon insert.
 301     typedef std::map<Argument*, ArgumentGraphNode> ArgumentMapTy;
 302
 303     ArgumentMapTy ArgumentMap;
 304
 305     // There is no root node for the argument graph, in fact:
 306     //   void f(int *x, int *y) { if (...) f(x, y); }
 307     // is an example where the graph is disconnected. The SCCIterator requires a
 308     // single entry point, so we maintain a fake ("synthetic") root node that
 309     // uses every node. Because the graph is directed and nothing points into
 310     // the root, it will not participate in any SCCs (except for its own).
 311     ArgumentGraphNode SyntheticRoot;
 312
 313   public:
 314     ArgumentGraph() { SyntheticRoot.Definition = 0; }
 315
 316     typedef SmallVectorImpl<ArgumentGraphNode*>::iterator iterator;
 317
 318     iterator begin() { return SyntheticRoot.Uses.begin(); }
 319     iterator end() { return SyntheticRoot.Uses.end(); }
 320     ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; }
 321
 322     ArgumentGraphNode *operator[](Argument *A) {
 323       ArgumentGraphNode &Node = ArgumentMap[A];
 324       Node.Definition = A;
 325       SyntheticRoot.Uses.push_back(&Node);
 326       return &Node;
 327     }
 328   };
 329
 330   // This tracker checks whether callees are in the SCC, and if so it does not
 331   // consider that a capture, instead adding it to the "Uses" list and
 332   // continuing with the analysis.
 333   struct ArgumentUsesTracker : public CaptureTracker {
 334     ArgumentUsesTracker(const SmallPtrSet<Function*, 8> &SCCNodes)
 335       : Captured(false), SCCNodes(SCCNodes) {}
 336
 337     void tooManyUses() { Captured = true; }
 338
 339     bool captured(Use *U) {
 340       CallSite CS(U->getUser());
 341       if (!CS.getInstruction()) { Captured = true; return true; }
 342
 343       Function *F = CS.getCalledFunction();
 344       if (!F || !SCCNodes.count(F)) { Captured = true; return true; }
 345
 346       Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end();
 347       for (CallSite::arg_iterator PI = CS.arg_begin(), PE = CS.arg_end();
 348            PI != PE; ++PI, ++AI) {
 349         if (AI == AE) {
 350           assert(F->isVarArg() && "More params than args in non-varargs call");
 351           Captured = true;
 352           return true;
 353         }
 354         if (PI == U) {
 355           Uses.push_back(AI);
 356           break;
 357         }
 358       }
 359       assert(!Uses.empty() && "Capturing call-site captured nothing?");
 360       return false;
 361     }
 362
 363     bool Captured;  // True only if certainly captured (used outside our SCC).
 364     SmallVector<Argument*, 4> Uses;  // Uses within our SCC.
 365
 366     const SmallPtrSet<Function*, 8> &SCCNodes;
 367   };
 368 }
 369
 370 namespace llvm {
 371   template<> struct GraphTraits<ArgumentGraphNode*> {
 372     typedef ArgumentGraphNode NodeType;
 373     typedef SmallVectorImpl<ArgumentGraphNode*>::iterator ChildIteratorType;
 374
 375     static inline NodeType *getEntryNode(NodeType *A) { return A; }
 376     static inline ChildIteratorType child_begin(NodeType *N) {
 377       return N->Uses.begin();
 378     }
 379     static inline ChildIteratorType child_end(NodeType *N) {
 380       return N->Uses.end();
 381     }
 382   };
 383   template<> struct GraphTraits<ArgumentGraph*>
 384     : public GraphTraits<ArgumentGraphNode*> {
 385     static NodeType *getEntryNode(ArgumentGraph *AG) {
 386       return AG->getEntryNode();
 387     }
 388     static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
 389       return AG->begin();
 390     }
 391     static ChildIteratorType nodes_end(ArgumentGraph *AG) {
 392       return AG->end();
 393     }
 394   };
 395 }
 396
 397 /// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC.
 398 bool FunctionAttrs::AddNoCaptureAttrs(const CallGraphSCC &SCC) {
 399   bool Changed = false;
 400
 401   SmallPtrSet<Function*, 8> SCCNodes;
 402
 403   // Fill SCCNodes with the elements of the SCC.  Used for quickly
 404   // looking up whether a given CallGraphNode is in this SCC.
 405   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
 406     Function *F = (*I)->getFunction();
 407     if (F && !F->isDeclaration() && !F->mayBeOverridden())
 408       SCCNodes.insert(F);
 409   }
 410
 411   ArgumentGraph AG;
 412
 413   AttrBuilder B;
 414   B.addAttribute(Attribute::NoCapture);
 415
 416   // Check each function in turn, determining which pointer arguments are not
 417   // captured.
 418   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
 419     Function *F = (*I)->getFunction();
 420
 421     if (F == 0)
 422       // External node - only a problem for arguments that we pass to it.
 423       continue;
 424
 425     // Definitions with weak linkage may be overridden at linktime with
 426     // something that captures pointers, so treat them like declarations.
 427     if (F->isDeclaration() || F->mayBeOverridden())
 428       continue;
 429
 430     // Functions that are readonly (or readnone) and nounwind and don't return
 431     // a value can't capture arguments. Don't analyze them.
 432     if (F->onlyReadsMemory() && F->doesNotThrow() &&
 433         F->getReturnType()->isVoidTy()) {
 434       for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end();
 435            A != E; ++A) {
 436         if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
 437           A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
 438           ++NumNoCapture;
 439           Changed = true;
 440         }
 441       }
 442       continue;
 443     }
 444
 445     for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A!=E; ++A)
 446       if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
 447         ArgumentUsesTracker Tracker(SCCNodes);
 448         PointerMayBeCaptured(A, &Tracker);
 449         if (!Tracker.Captured) {
 450           if (Tracker.Uses.empty()) {
 451             // If it's trivially not captured, mark it nocapture now.
 452             A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo()+1, B));
 453             ++NumNoCapture;
 454             Changed = true;
 455           } else {
 456             // If it's not trivially captured and not trivially not captured,
 457             // then it must be calling into another function in our SCC. Save
 458             // its particulars for Argument-SCC analysis later.
 459             ArgumentGraphNode *Node = AG[A];
 460             for (SmallVectorImpl<Argument*>::iterator UI = Tracker.Uses.begin(),
 461                    UE = Tracker.Uses.end(); UI != UE; ++UI)
 462               Node->Uses.push_back(AG[*UI]);
 463           }
 464         }
 465         // Otherwise, it's captured. Don't bother doing SCC analysis on it.
 466       }
 467   }
 468
 469   // The graph we've collected is partial because we stopped scanning for
 470   // argument uses once we solved the argument trivially. These partial nodes
 471   // show up as ArgumentGraphNode objects with an empty Uses list, and for
 472   // these nodes the final decision about whether they capture has already been
 473   // made.  If the definition doesn't have a 'nocapture' attribute by now, it
 474   // captures.
 475
 476   for (scc_iterator<ArgumentGraph*> I = scc_begin(&AG), E = scc_end(&AG);
 477        I != E; ++I) {
 478     std::vector<ArgumentGraphNode*> &ArgumentSCC = *I;
 479     if (ArgumentSCC.size() == 1) {
 480       if (!ArgumentSCC[0]->Definition) continue;  // synthetic root node
 481
 482       // eg. "void f(int* x) { if (...) f(x); }"
 483       if (ArgumentSCC[0]->Uses.size() == 1 &&
 484           ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
 485         ArgumentSCC[0]->
 486           Definition->
 487           addAttr(AttributeSet::get(ArgumentSCC[0]->Definition->getContext(),
 488                                     ArgumentSCC[0]->Definition->getArgNo() + 1,
 489                                     B));
 490         ++NumNoCapture;
 491         Changed = true;
 492       }
 493       continue;
 494     }
 495
 496     bool SCCCaptured = false;
 497     for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(),
 498            E = ArgumentSCC.end(); I != E && !SCCCaptured; ++I) {
 499       ArgumentGraphNode *Node = *I;
 500       if (Node->Uses.empty()) {
 501         if (!Node->Definition->hasNoCaptureAttr())
 502           SCCCaptured = true;
 503       }
 504     }
 505     if (SCCCaptured) continue;
 506
 507     SmallPtrSet<Argument*, 8> ArgumentSCCNodes;
 508     // Fill ArgumentSCCNodes with the elements of the ArgumentSCC.  Used for
 509     // quickly looking up whether a given Argument is in this ArgumentSCC.
 510     for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(),
 511            E = ArgumentSCC.end(); I != E; ++I) {
 512       ArgumentSCCNodes.insert((*I)->Definition);
 513     }
 514
 515     for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(),
 516            E = ArgumentSCC.end(); I != E && !SCCCaptured; ++I) {
 517       ArgumentGraphNode *N = *I;
 518       for (SmallVectorImpl<ArgumentGraphNode*>::iterator UI = N->Uses.begin(),
 519              UE = N->Uses.end(); UI != UE; ++UI) {
 520         Argument *A = (*UI)->Definition;
 521         if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
 522           continue;
 523         SCCCaptured = true;
 524         break;
 525       }
 526     }
 527     if (SCCCaptured) continue;
 528
 529     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
 530       Argument *A = ArgumentSCC[i]->Definition;
 531       A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
 532       ++NumNoCapture;
 533       Changed = true;
 534     }
 535   }
 536
 537   return Changed;
 538 }
 539
 540 /// IsFunctionMallocLike - A function is malloc-like if it returns either null
 541 /// or a pointer that doesn't alias any other pointer visible to the caller.
 542 bool FunctionAttrs::IsFunctionMallocLike(Function *F,
 543                               SmallPtrSet<Function*, 8> &SCCNodes) const {
 544   SmallSetVector<Value *, 8> FlowsToReturn;
 545   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
 546     if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator()))
 547       FlowsToReturn.insert(Ret->getReturnValue());
 548
 549   for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
 550     Value *RetVal = FlowsToReturn[i];
 551
 552     if (Constant *C = dyn_cast<Constant>(RetVal)) {
 553       if (!C->isNullValue() && !isa<UndefValue>(C))
 554         return false;
 555
 556       continue;
 557     }
 558
 559     if (isa<Argument>(RetVal))
 560       return false;
 561
 562     if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
 563       switch (RVI->getOpcode()) {
 564         // Extend the analysis by looking upwards.
 565         case Instruction::BitCast:
 566         case Instruction::GetElementPtr:
 567           FlowsToReturn.insert(RVI->getOperand(0));
 568           continue;
 569         case Instruction::Select: {
 570           SelectInst *SI = cast<SelectInst>(RVI);
 571           FlowsToReturn.insert(SI->getTrueValue());
 572           FlowsToReturn.insert(SI->getFalseValue());
 573           continue;
 574         }
 575         case Instruction::PHI: {
 576           PHINode *PN = cast<PHINode>(RVI);
 577           for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 578             FlowsToReturn.insert(PN->getIncomingValue(i));
 579           continue;
 580         }
 581
 582         // Check whether the pointer came from an allocation.
 583         case Instruction::Alloca:
 584           break;
 585         case Instruction::Call:
 586         case Instruction::Invoke: {
 587           CallSite CS(RVI);
 588           if (CS.paramHasAttr(0, Attribute::NoAlias))
 589             break;
 590           if (CS.getCalledFunction() &&
 591               SCCNodes.count(CS.getCalledFunction()))
 592             break;
 593         } // fall-through
 594         default:
 595           return false;  // Did not come from an allocation.
 596       }
 597
 598     if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
 599       return false;
 600   }
 601
 602   return true;
 603 }
 604
 605 /// AddNoAliasAttrs - Deduce noalias attributes for the SCC.
 606 bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) {
 607   SmallPtrSet<Function*, 8> SCCNodes;
 608
 609   // Fill SCCNodes with the elements of the SCC.  Used for quickly
 610   // looking up whether a given CallGraphNode is in this SCC.
 611   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
 612     SCCNodes.insert((*I)->getFunction());
 613
 614   // Check each function in turn, determining which functions return noalias
 615   // pointers.
 616   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
 617     Function *F = (*I)->getFunction();
 618
 619     if (F == 0)
 620       // External node - skip it;
 621       return false;
 622
 623     // Already noalias.
 624     if (F->doesNotAlias(0))
 625       continue;
 626
 627     // Definitions with weak linkage may be overridden at linktime, so
 628     // treat them like declarations.
 629     if (F->isDeclaration() || F->mayBeOverridden())
 630       return false;
 631
 632     // We annotate noalias return values, which are only applicable to
 633     // pointer types.
 634     if (!F->getReturnType()->isPointerTy())
 635       continue;
 636
 637     if (!IsFunctionMallocLike(F, SCCNodes))
 638       return false;
 639   }
 640
 641   bool MadeChange = false;
 642   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
 643     Function *F = (*I)->getFunction();
 644     if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy())
 645       continue;
 646
 647     F->setDoesNotAlias(0);
 648     ++NumNoAlias;
 649     MadeChange = true;
 650   }
 651
 652   return MadeChange;
 653 }
 654
 655 /// inferPrototypeAttributes - Analyze the name and prototype of the
 656 /// given function and set any applicable attributes.  Returns true
 657 /// if any attributes were set and false otherwise.
 658 bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
 659   FunctionType *FTy = F.getFunctionType();
 660   LibFunc::Func TheLibFunc;
 661   if (!(TLI->getLibFunc(F.getName(), TheLibFunc) && TLI->has(TheLibFunc)))
 662     return false;
 663
 664   switch (TheLibFunc) {
 665   case LibFunc::strlen:
 666     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
 667       return false;
 668     setOnlyReadsMemory(F);
 669     setDoesNotThrow(F);
 670     setDoesNotCapture(F, 1);
 671     break;
 672   case LibFunc::strchr:
 673   case LibFunc::strrchr:
 674     if (FTy->getNumParams() != 2 ||
 675         !FTy->getParamType(0)->isPointerTy() ||
 676         !FTy->getParamType(1)->isIntegerTy())
 677       return false;
 678     setOnlyReadsMemory(F);
 679     setDoesNotThrow(F);
 680     break;
 681   case LibFunc::strcpy:
 682   case LibFunc::stpcpy:
 683   case LibFunc::strcat:
 684   case LibFunc::strtol:
 685   case LibFunc::strtod:
 686   case LibFunc::strtof:
 687   case LibFunc::strtoul:
 688   case LibFunc::strtoll:
 689   case LibFunc::strtold:
 690   case LibFunc::strncat:
 691   case LibFunc::strncpy:
 692   case LibFunc::stpncpy:
 693   case LibFunc::strtoull:
 694     if (FTy->getNumParams() < 2 ||
 695         !FTy->getParamType(1)->isPointerTy())
 696       return false;
 697     setDoesNotThrow(F);
 698     setDoesNotCapture(F, 2);
 699     break;
 700   case LibFunc::strxfrm:
 701     if (FTy->getNumParams() != 3 ||
 702         !FTy->getParamType(0)->isPointerTy() ||
 703         !FTy->getParamType(1)->isPointerTy())
 704       return false;
 705     setDoesNotThrow(F);
 706     setDoesNotCapture(F, 1);
 707     setDoesNotCapture(F, 2);
 708     break;
 709   case LibFunc::strcmp:
 710   case LibFunc::strspn:
 711   case LibFunc::strncmp:
 712   case LibFunc::strcspn:
 713   case LibFunc::strcoll:
 714   case LibFunc::strcasecmp:
 715   case LibFunc::strncasecmp:
 716     if (FTy->getNumParams() < 2 ||
 717         !FTy->getParamType(0)->isPointerTy() ||
 718         !FTy->getParamType(1)->isPointerTy())
 719       return false;
 720     setOnlyReadsMemory(F);
 721     setDoesNotThrow(F);
 722     setDoesNotCapture(F, 1);
 723     setDoesNotCapture(F, 2);
 724     break;
 725   case LibFunc::strstr:
 726   case LibFunc::strpbrk:
 727     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
 728       return false;
 729     setOnlyReadsMemory(F);
 730     setDoesNotThrow(F);
 731     setDoesNotCapture(F, 2);
 732     break;
 733   case LibFunc::strtok:
 734   case LibFunc::strtok_r:
 735     if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
 736       return false;
 737     setDoesNotThrow(F);
 738     setDoesNotCapture(F, 2);
 739     break;
 740   case LibFunc::scanf:
 741   case LibFunc::setbuf:
 742   case LibFunc::setvbuf:
 743     if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
 744       return false;
 745     setDoesNotThrow(F);
 746     setDoesNotCapture(F, 1);
 747     break;
 748   case LibFunc::strdup:
 749   case LibFunc::strndup:
 750     if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() ||
 751         !FTy->getParamType(0)->isPointerTy())
 752       return false;
 753     setDoesNotThrow(F);
 754     setDoesNotAlias(F, 0);
 755     setDoesNotCapture(F, 1);
 756     break;
 757   case LibFunc::stat:
 758   case LibFunc::sscanf:
 759   case LibFunc::sprintf:
 760   case LibFunc::statvfs:
 761     if (FTy->getNumParams() < 2 ||
 762         !FTy->getParamType(0)->isPointerTy() ||
 763         !FTy->getParamType(1)->isPointerTy())
 764       return false;
 765     setDoesNotThrow(F);
 766     setDoesNotCapture(F, 1);
 767     setDoesNotCapture(F, 2);
 768     break;
 769   case LibFunc::snprintf:
 770     if (FTy->getNumParams() != 3 ||
 771         !FTy->getParamType(0)->isPointerTy() ||
 772         !FTy->getParamType(2)->isPointerTy())
 773       return false;
 774     setDoesNotThrow(F);
 775     setDoesNotCapture(F, 1);
 776     setDoesNotCapture(F, 3);
 777     break;
 778   case LibFunc::setitimer:
 779     if (FTy->getNumParams() != 3 ||
 780         !FTy->getParamType(1)->isPointerTy() ||
 781         !FTy->getParamType(2)->isPointerTy())
 782       return false;
 783     setDoesNotThrow(F);
 784     setDoesNotCapture(F, 2);
 785     setDoesNotCapture(F, 3);
 786     break;
 787   case LibFunc::system:
 788     if (FTy->getNumParams() != 1 ||
 789         !FTy->getParamType(0)->isPointerTy())
 790       return false;
 791     // May throw; "system" is a valid pthread cancellation point.
 792     setDoesNotCapture(F, 1);
 793     break;
 794   case LibFunc::malloc:
 795     if (FTy->getNumParams() != 1 ||
 796         !FTy->getReturnType()->isPointerTy())
 797       return false;
 798     setDoesNotThrow(F);
 799     setDoesNotAlias(F, 0);
 800     break;
 801   case LibFunc::memcmp:
 802     if (FTy->getNumParams() != 3 ||
 803         !FTy->getParamType(0)->isPointerTy() ||
 804         !FTy->getParamType(1)->isPointerTy())
 805       return false;
 806     setOnlyReadsMemory(F);
 807     setDoesNotThrow(F);
 808     setDoesNotCapture(F, 1);
 809     setDoesNotCapture(F, 2);
 810     break;
 811   case LibFunc::memchr:
 812   case LibFunc::memrchr:
 813     if (FTy->getNumParams() != 3)
 814       return false;
 815     setOnlyReadsMemory(F);
 816     setDoesNotThrow(F);
 817     break;
 818   case LibFunc::modf:
 819   case LibFunc::modff:
 820   case LibFunc::modfl:
 821   case LibFunc::memcpy:
 822   case LibFunc::memccpy:
 823   case LibFunc::memmove:
 824     if (FTy->getNumParams() < 2 ||
 825         !FTy->getParamType(1)->isPointerTy())
 826       return false;
 827     setDoesNotThrow(F);
 828     setDoesNotCapture(F, 2);
 829     break;
 830   case LibFunc::memalign:
 831     if (!FTy->getReturnType()->isPointerTy())
 832       return false;
 833     setDoesNotAlias(F, 0);
 834     break;
 835   case LibFunc::mkdir:
 836   case LibFunc::mktime:
 837     if (FTy->getNumParams() == 0 ||
 838         !FTy->getParamType(0)->isPointerTy())
 839       return false;
 840     setDoesNotThrow(F);
 841     setDoesNotCapture(F, 1);
 842     break;
 843   case LibFunc::realloc:
 844     if (FTy->getNumParams() != 2 ||
 845         !FTy->getParamType(0)->isPointerTy() ||
 846         !FTy->getReturnType()->isPointerTy())
 847       return false;
 848     setDoesNotThrow(F);
 849     setDoesNotAlias(F, 0);
 850     setDoesNotCapture(F, 1);
 851     break;
 852   case LibFunc::read:
 853     if (FTy->getNumParams() != 3 ||
 854         !FTy->getParamType(1)->isPointerTy())
 855       return false;
 856     // May throw; "read" is a valid pthread cancellation point.
 857     setDoesNotCapture(F, 2);
 858     break;
 859   case LibFunc::rmdir:
 860   case LibFunc::rewind:
 861   case LibFunc::remove:
 862   case LibFunc::realpath:
 863     if (FTy->getNumParams() < 1 ||
 864         !FTy->getParamType(0)->isPointerTy())
 865       return false;
 866     setDoesNotThrow(F);
 867     setDoesNotCapture(F, 1);
 868     break;
 869   case LibFunc::rename:
 870   case LibFunc::readlink:
 871     if (FTy->getNumParams() < 2 ||
 872         !FTy->getParamType(0)->isPointerTy() ||
 873         !FTy->getParamType(1)->isPointerTy())
 874       return false;
 875     setDoesNotThrow(F);
 876     setDoesNotCapture(F, 1);
 877     setDoesNotCapture(F, 2);
 878     break;
 879   case LibFunc::write:
 880     if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
 881       return false;
 882     // May throw; "write" is a valid pthread cancellation point.
 883     setDoesNotCapture(F, 2);
 884     break;
 885   case LibFunc::bcopy:
 886     if (FTy->getNumParams() != 3 ||
 887         !FTy->getParamType(0)->isPointerTy() ||
 888         !FTy->getParamType(1)->isPointerTy())
 889       return false;
 890     setDoesNotThrow(F);
 891     setDoesNotCapture(F, 1);
 892     setDoesNotCapture(F, 2);
 893     break;
 894   case LibFunc::bcmp:
 895     if (FTy->getNumParams() != 3 ||
 896         !FTy->getParamType(0)->isPointerTy() ||
 897         !FTy->getParamType(1)->isPointerTy())
 898       return false;
 899     setDoesNotThrow(F);
 900     setOnlyReadsMemory(F);
 901     setDoesNotCapture(F, 1);
 902     setDoesNotCapture(F, 2);
 903     break;
 904   case LibFunc::bzero:
 905     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
 906       return false;
 907     setDoesNotThrow(F);
 908     setDoesNotCapture(F, 1);
 909     break;
 910   case LibFunc::calloc:
 911     if (FTy->getNumParams() != 2 ||
 912         !FTy->getReturnType()->isPointerTy())
 913       return false;
 914     setDoesNotThrow(F);
 915     setDoesNotAlias(F, 0);
 916     break;
 917   case LibFunc::chmod:
 918   case LibFunc::chown:
 919   case LibFunc::ctermid:
 920   case LibFunc::clearerr:
 921   case LibFunc::closedir:
 922     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
 923       return false;
 924     setDoesNotThrow(F);
 925     setDoesNotCapture(F, 1);
 926     break;
 927   case LibFunc::atoi:
 928   case LibFunc::atol:
 929   case LibFunc::atof:
 930   case LibFunc::atoll:
 931     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
 932       return false;
 933     setDoesNotThrow(F);
 934     setOnlyReadsMemory(F);
 935     setDoesNotCapture(F, 1);
 936     break;
 937   case LibFunc::access:
 938     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
 939       return false;
 940     setDoesNotThrow(F);
 941     setDoesNotCapture(F, 1);
 942     break;
 943   case LibFunc::fopen:
 944     if (FTy->getNumParams() != 2 ||
 945         !FTy->getReturnType()->isPointerTy() ||
 946         !FTy->getParamType(0)->isPointerTy() ||
 947         !FTy->getParamType(1)->isPointerTy())
 948       return false;
 949     setDoesNotThrow(F);
 950     setDoesNotAlias(F, 0);
 951     setDoesNotCapture(F, 1);
 952     setDoesNotCapture(F, 2);
 953     break;
 954   case LibFunc::fdopen:
 955     if (FTy->getNumParams() != 2 ||
 956         !FTy->getReturnType()->isPointerTy() ||
 957         !FTy->getParamType(1)->isPointerTy())
 958       return false;
 959     setDoesNotThrow(F);
 960     setDoesNotAlias(F, 0);
 961     setDoesNotCapture(F, 2);
 962     break;
 963   case LibFunc::feof:
 964   case LibFunc::free:
 965   case LibFunc::fseek:
 966   case LibFunc::ftell:
 967   case LibFunc::fgetc:
 968   case LibFunc::fseeko:
 969   case LibFunc::ftello:
 970   case LibFunc::fileno:
 971   case LibFunc::fflush:
 972   case LibFunc::fclose:
 973   case LibFunc::fsetpos:
 974   case LibFunc::flockfile:
 975   case LibFunc::funlockfile:
 976   case LibFunc::ftrylockfile:
 977     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
 978       return false;
 979     setDoesNotThrow(F);
 980     setDoesNotCapture(F, 1);
 981     break;
 982   case LibFunc::ferror:
 983     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
 984       return false;
 985     setDoesNotThrow(F);
 986     setDoesNotCapture(F, 1);
 987     setOnlyReadsMemory(F);
 988     break;
 989   case LibFunc::fputc:
 990   case LibFunc::fstat:
 991   case LibFunc::frexp:
 992   case LibFunc::frexpf:
 993   case LibFunc::frexpl:
 994   case LibFunc::fstatvfs:
 995     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
 996       return false;
 997     setDoesNotThrow(F);
 998     setDoesNotCapture(F, 2);
 999     break;
1000   case LibFunc::fgets:
1001     if (FTy->getNumParams() != 3 ||
1002         !FTy->getParamType(0)->isPointerTy() ||
1003         !FTy->getParamType(2)->isPointerTy())
1004       return false;
1005     setDoesNotThrow(F);
1006     setDoesNotCapture(F, 3);
1007     break;
1008   case LibFunc::fread:
1009   case LibFunc::fwrite:
1010     if (FTy->getNumParams() != 4 ||
1011         !FTy->getParamType(0)->isPointerTy() ||
1012         !FTy->getParamType(3)->isPointerTy())
1013       return false;
1014     setDoesNotThrow(F);
1015     setDoesNotCapture(F, 1);
1016     setDoesNotCapture(F, 4);
1017     break;
1018   case LibFunc::fputs:
1019   case LibFunc::fscanf:
1020   case LibFunc::fprintf:
1021   case LibFunc::fgetpos:
1022     if (FTy->getNumParams() < 2 ||
1023         !FTy->getParamType(0)->isPointerTy() ||
1024         !FTy->getParamType(1)->isPointerTy())
1025       return false;
1026     setDoesNotThrow(F);
1027     setDoesNotCapture(F, 1);
1028     setDoesNotCapture(F, 2);
1029     break;
1030   case LibFunc::getc:
1031   case LibFunc::getlogin_r:
1032   case LibFunc::getc_unlocked:
1033     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1034       return false;
1035     setDoesNotThrow(F);
1036     setDoesNotCapture(F, 1);
1037     break;
1038   case LibFunc::getenv:
1039     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1040       return false;
1041     setDoesNotThrow(F);
1042     setOnlyReadsMemory(F);
1043     setDoesNotCapture(F, 1);
1044     break;
1045   case LibFunc::gets:
1046   case LibFunc::getchar:
1047     setDoesNotThrow(F);
1048     break;
1049   case LibFunc::getitimer:
1050     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1051       return false;
1052     setDoesNotThrow(F);
1053     setDoesNotCapture(F, 2);
1054     break;
1055   case LibFunc::getpwnam:
1056     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1057       return false;
1058     setDoesNotThrow(F);
1059     setDoesNotCapture(F, 1);
1060     break;
1061   case LibFunc::ungetc:
1062     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1063       return false;
1064     setDoesNotThrow(F);
1065     setDoesNotCapture(F, 2);
1066     break;
1067   case LibFunc::uname:
1068   case LibFunc::unlink:
1069   case LibFunc::unsetenv:
1070     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1071       return false;
1072     setDoesNotThrow(F);
1073     setDoesNotCapture(F, 1);
1074     break;
1075   case LibFunc::utime:
1076   case LibFunc::utimes:
1077     if (FTy->getNumParams() != 2 ||
1078         !FTy->getParamType(0)->isPointerTy() ||
1079         !FTy->getParamType(1)->isPointerTy())
1080       return false;
1081     setDoesNotThrow(F);
1082     setDoesNotCapture(F, 1);
1083     setDoesNotCapture(F, 2);
1084     break;
1085   case LibFunc::putc:
1086     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1087       return false;
1088     setDoesNotThrow(F);
1089     setDoesNotCapture(F, 2);
1090     break;
1091   case LibFunc::puts:
1092   case LibFunc::printf:
1093   case LibFunc::perror:
1094     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1095       return false;
1096     setDoesNotThrow(F);
1097     setDoesNotCapture(F, 1);
1098     break;
1099   case LibFunc::pread:
1100   case LibFunc::pwrite:
1101     if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
1102       return false;
1103     // May throw; these are valid pthread cancellation points.
1104     setDoesNotCapture(F, 2);
1105     break;
1106   case LibFunc::putchar:
1107     setDoesNotThrow(F);
1108     break;
1109   case LibFunc::popen:
1110     if (FTy->getNumParams() != 2 ||
1111         !FTy->getReturnType()->isPointerTy() ||
1112         !FTy->getParamType(0)->isPointerTy() ||
1113         !FTy->getParamType(1)->isPointerTy())
1114       return false;
1115     setDoesNotThrow(F);
1116     setDoesNotAlias(F, 0);
1117     setDoesNotCapture(F, 1);
1118     setDoesNotCapture(F, 2);
1119     break;
1120   case LibFunc::pclose:
1121     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1122       return false;
1123     setDoesNotThrow(F);
1124     setDoesNotCapture(F, 1);
1125     break;
1126   case LibFunc::vscanf:
1127     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1128       return false;
1129     setDoesNotThrow(F);
1130     setDoesNotCapture(F, 1);
1131     break;
1132   case LibFunc::vsscanf:
1133   case LibFunc::vfscanf:
1134     if (FTy->getNumParams() != 3 ||
1135         !FTy->getParamType(1)->isPointerTy() ||
1136         !FTy->getParamType(2)->isPointerTy())
1137       return false;
1138     setDoesNotThrow(F);
1139     setDoesNotCapture(F, 1);
1140     setDoesNotCapture(F, 2);
1141     break;
1142   case LibFunc::valloc:
1143     if (!FTy->getReturnType()->isPointerTy())
1144       return false;
1145     setDoesNotThrow(F);
1146     setDoesNotAlias(F, 0);
1147     break;
1148   case LibFunc::vprintf:
1149     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1150       return false;
1151     setDoesNotThrow(F);
1152     setDoesNotCapture(F, 1);
1153     break;
1154   case LibFunc::vfprintf:
1155   case LibFunc::vsprintf:
1156     if (FTy->getNumParams() != 3 ||
1157         !FTy->getParamType(0)->isPointerTy() ||
1158         !FTy->getParamType(1)->isPointerTy())
1159       return false;
1160     setDoesNotThrow(F);
1161     setDoesNotCapture(F, 1);
1162     setDoesNotCapture(F, 2);
1163     break;
1164   case LibFunc::vsnprintf:
1165     if (FTy->getNumParams() != 4 ||
1166         !FTy->getParamType(0)->isPointerTy() ||
1167         !FTy->getParamType(2)->isPointerTy())
1168       return false;
1169     setDoesNotThrow(F);
1170     setDoesNotCapture(F, 1);
1171     setDoesNotCapture(F, 3);
1172     break;
1173   case LibFunc::open:
1174     if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
1175       return false;
1176     // May throw; "open" is a valid pthread cancellation point.
1177     setDoesNotCapture(F, 1);
1178     break;
1179   case LibFunc::opendir:
1180     if (FTy->getNumParams() != 1 ||
1181         !FTy->getReturnType()->isPointerTy() ||
1182         !FTy->getParamType(0)->isPointerTy())
1183       return false;
1184     setDoesNotThrow(F);
1185     setDoesNotAlias(F, 0);
1186     setDoesNotCapture(F, 1);
1187     break;
1188   case LibFunc::tmpfile:
1189     if (!FTy->getReturnType()->isPointerTy())
1190       return false;
1191     setDoesNotThrow(F);
1192     setDoesNotAlias(F, 0);
1193     break;
1194   case LibFunc::times:
1195     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1196       return false;
1197     setDoesNotThrow(F);
1198     setDoesNotCapture(F, 1);
1199     break;
1200   case LibFunc::htonl:
1201   case LibFunc::htons:
1202   case LibFunc::ntohl:
1203   case LibFunc::ntohs:
1204     setDoesNotThrow(F);
1205     setDoesNotAccessMemory(F);
1206     break;
1207   case LibFunc::lstat:
1208     if (FTy->getNumParams() != 2 ||
1209         !FTy->getParamType(0)->isPointerTy() ||
1210         !FTy->getParamType(1)->isPointerTy())
1211       return false;
1212     setDoesNotThrow(F);
1213     setDoesNotCapture(F, 1);
1214     setDoesNotCapture(F, 2);
1215     break;
1216   case LibFunc::lchown:
1217     if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy())
1218       return false;
1219     setDoesNotThrow(F);
1220     setDoesNotCapture(F, 1);
1221     break;
1222   case LibFunc::qsort:
1223     if (FTy->getNumParams() != 4 || !FTy->getParamType(3)->isPointerTy())
1224       return false;
1225     // May throw; places call through function pointer.
1226     setDoesNotCapture(F, 4);
1227     break;
1228   case LibFunc::dunder_strdup:
1229   case LibFunc::dunder_strndup:
1230     if (FTy->getNumParams() < 1 ||
1231         !FTy->getReturnType()->isPointerTy() ||
1232         !FTy->getParamType(0)->isPointerTy())
1233       return false;
1234     setDoesNotThrow(F);
1235     setDoesNotAlias(F, 0);
1236     setDoesNotCapture(F, 1);
1237     break;
1238   case LibFunc::dunder_strtok_r:
1239     if (FTy->getNumParams() != 3 ||
1240         !FTy->getParamType(1)->isPointerTy())
1241       return false;
1242     setDoesNotThrow(F);
1243     setDoesNotCapture(F, 2);
1244     break;
1245   case LibFunc::under_IO_getc:
1246     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1247       return false;
1248     setDoesNotThrow(F);
1249     setDoesNotCapture(F, 1);
1250     break;
1251   case LibFunc::under_IO_putc:
1252     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1253       return false;
1254     setDoesNotThrow(F);
1255     setDoesNotCapture(F, 2);
1256     break;
1257   case LibFunc::dunder_isoc99_scanf:
1258     if (FTy->getNumParams() < 1 ||
1259         !FTy->getParamType(0)->isPointerTy())
1260       return false;
1261     setDoesNotThrow(F);
1262     setDoesNotCapture(F, 1);
1263     break;
1264   case LibFunc::stat64:
1265   case LibFunc::lstat64:
1266   case LibFunc::statvfs64:
1267   case LibFunc::dunder_isoc99_sscanf:
1268     if (FTy->getNumParams() < 1 ||
1269         !FTy->getParamType(0)->isPointerTy() ||
1270         !FTy->getParamType(1)->isPointerTy())
1271       return false;
1272     setDoesNotThrow(F);
1273     setDoesNotCapture(F, 1);
1274     setDoesNotCapture(F, 2);
1275     break;
1276   case LibFunc::fopen64:
1277     if (FTy->getNumParams() != 2 ||
1278         !FTy->getReturnType()->isPointerTy() ||
1279         !FTy->getParamType(0)->isPointerTy() ||
1280         !FTy->getParamType(1)->isPointerTy())
1281       return false;
1282     setDoesNotThrow(F);
1283     setDoesNotAlias(F, 0);
1284     setDoesNotCapture(F, 1);
1285     setDoesNotCapture(F, 2);
1286     break;
1287   case LibFunc::fseeko64:
1288   case LibFunc::ftello64:
1289     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1290       return false;
1291     setDoesNotThrow(F);
1292     setDoesNotCapture(F, 1);
1293     break;
1294   case LibFunc::tmpfile64:
1295     if (!FTy->getReturnType()->isPointerTy())
1296       return false;
1297     setDoesNotThrow(F);
1298     setDoesNotAlias(F, 0);
1299     break;
1300   case LibFunc::fstat64:
1301   case LibFunc::fstatvfs64:
1302     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1303       return false;
1304     setDoesNotThrow(F);
1305     setDoesNotCapture(F, 2);
1306     break;
1307   case LibFunc::open64:
1308     if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
1309       return false;
1310     // May throw; "open" is a valid pthread cancellation point.
1311     setDoesNotCapture(F, 1);
1312     break;
1313   case LibFunc::gettimeofday:
1314     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
1315         !FTy->getParamType(1)->isPointerTy())
1316       return false;
1317     // Currently some platforms have the restrict keyword on the arguments to
1318     // gettimeofday. To be conservative, do not add noalias to gettimeofday's
1319     // arguments.
1320     setDoesNotThrow(F);
1321     setDoesNotCapture(F, 1);
1322     setDoesNotCapture(F, 2);
1323   default:
1324     // Didn't mark any attributes.
1325     return false;
1326   }
1327
1328   return true;
1329 }
1330
1331 /// annotateLibraryCalls - Adds attributes to well-known standard library
1332 /// call declarations.
1333 bool FunctionAttrs::annotateLibraryCalls(const CallGraphSCC &SCC) {
1334   bool MadeChange = false;
1335
1336   // Check each function in turn annotating well-known library function
1337   // declarations with attributes.
1338   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
1339     Function *F = (*I)->getFunction();
1340
1341     if (F != 0 && F->isDeclaration())
1342       MadeChange |= inferPrototypeAttributes(*F);
1343   }
1344
1345   return MadeChange;
1346 }
1347
1348 bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) {
1349   AA = &getAnalysis<AliasAnalysis>();
1350   TLI = &getAnalysis<TargetLibraryInfo>();
1351
1352   bool Changed = annotateLibraryCalls(SCC);
1353   Changed |= AddReadAttrs(SCC);
1354   Changed |= AddNoCaptureAttrs(SCC);
1355   Changed |= AddNoAliasAttrs(SCC);
1356   return Changed;
1357 }