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