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