LLVM  mainline
FunctionAttrs.cpp
Go to the documentation of this file.
00001 //===- FunctionAttrs.cpp - Pass which marks functions attributes ----------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements a simple interprocedural pass which walks the
00011 // call-graph, looking for functions which do not access or only read
00012 // non-local memory, and marking them readnone/readonly.  It does the
00013 // same with function arguments independently, marking them readonly/
00014 // readnone/nocapture.  Finally, well-known library call declarations
00015 // are marked with all attributes that are consistent with the
00016 // function's standard definition. This pass is implemented as a
00017 // bottom-up traversal of the call-graph.
00018 //
00019 //===----------------------------------------------------------------------===//
00020 
00021 #include "llvm/Transforms/IPO.h"
00022 #include "llvm/ADT/SCCIterator.h"
00023 #include "llvm/ADT/SetVector.h"
00024 #include "llvm/ADT/SmallSet.h"
00025 #include "llvm/ADT/Statistic.h"
00026 #include "llvm/Analysis/AliasAnalysis.h"
00027 #include "llvm/Analysis/CallGraph.h"
00028 #include "llvm/Analysis/CallGraphSCCPass.h"
00029 #include "llvm/Analysis/CaptureTracking.h"
00030 #include "llvm/IR/GlobalVariable.h"
00031 #include "llvm/IR/InstIterator.h"
00032 #include "llvm/IR/IntrinsicInst.h"
00033 #include "llvm/IR/LLVMContext.h"
00034 #include "llvm/Analysis/TargetLibraryInfo.h"
00035 using namespace llvm;
00036 
00037 #define DEBUG_TYPE "functionattrs"
00038 
00039 STATISTIC(NumReadNone, "Number of functions marked readnone");
00040 STATISTIC(NumReadOnly, "Number of functions marked readonly");
00041 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
00042 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
00043 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
00044 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
00045 STATISTIC(NumAnnotated, "Number of attributes added to library functions");
00046 
00047 namespace {
00048   struct FunctionAttrs : public CallGraphSCCPass {
00049     static char ID; // Pass identification, replacement for typeid
00050     FunctionAttrs() : CallGraphSCCPass(ID), AA(nullptr) {
00051       initializeFunctionAttrsPass(*PassRegistry::getPassRegistry());
00052     }
00053 
00054     // runOnSCC - Analyze the SCC, performing the transformation if possible.
00055     bool runOnSCC(CallGraphSCC &SCC) override;
00056 
00057     // AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
00058     bool AddReadAttrs(const CallGraphSCC &SCC);
00059 
00060     // AddArgumentAttrs - Deduce nocapture attributes for the SCC.
00061     bool AddArgumentAttrs(const CallGraphSCC &SCC);
00062 
00063     // IsFunctionMallocLike - Does this function allocate new memory?
00064     bool IsFunctionMallocLike(Function *F,
00065                               SmallPtrSet<Function*, 8> &) const;
00066 
00067     // AddNoAliasAttrs - Deduce noalias attributes for the SCC.
00068     bool AddNoAliasAttrs(const CallGraphSCC &SCC);
00069 
00070     // Utility methods used by inferPrototypeAttributes to add attributes
00071     // and maintain annotation statistics.
00072 
00073     void setDoesNotAccessMemory(Function &F) {
00074       if (!F.doesNotAccessMemory()) {
00075         F.setDoesNotAccessMemory();
00076         ++NumAnnotated;
00077       }
00078     }
00079 
00080     void setOnlyReadsMemory(Function &F) {
00081       if (!F.onlyReadsMemory()) {
00082         F.setOnlyReadsMemory();
00083         ++NumAnnotated;
00084       }
00085     }
00086 
00087     void setDoesNotThrow(Function &F) {
00088       if (!F.doesNotThrow()) {
00089         F.setDoesNotThrow();
00090         ++NumAnnotated;
00091       }
00092     }
00093 
00094     void setDoesNotCapture(Function &F, unsigned n) {
00095       if (!F.doesNotCapture(n)) {
00096         F.setDoesNotCapture(n);
00097         ++NumAnnotated;
00098       }
00099     }
00100 
00101     void setOnlyReadsMemory(Function &F, unsigned n) {
00102       if (!F.onlyReadsMemory(n)) {
00103         F.setOnlyReadsMemory(n);
00104         ++NumAnnotated;
00105       }
00106     }
00107 
00108     void setDoesNotAlias(Function &F, unsigned n) {
00109       if (!F.doesNotAlias(n)) {
00110         F.setDoesNotAlias(n);
00111         ++NumAnnotated;
00112       }
00113     }
00114 
00115     // inferPrototypeAttributes - Analyze the name and prototype of the
00116     // given function and set any applicable attributes.  Returns true
00117     // if any attributes were set and false otherwise.
00118     bool inferPrototypeAttributes(Function &F);
00119 
00120     // annotateLibraryCalls - Adds attributes to well-known standard library
00121     // call declarations.
00122     bool annotateLibraryCalls(const CallGraphSCC &SCC);
00123 
00124     void getAnalysisUsage(AnalysisUsage &AU) const override {
00125       AU.setPreservesCFG();
00126       AU.addRequired<AliasAnalysis>();
00127       AU.addRequired<TargetLibraryInfoWrapperPass>();
00128       CallGraphSCCPass::getAnalysisUsage(AU);
00129     }
00130 
00131   private:
00132     AliasAnalysis *AA;
00133     TargetLibraryInfo *TLI;
00134   };
00135 }
00136 
00137 char FunctionAttrs::ID = 0;
00138 INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs",
00139                 "Deduce function attributes", false, false)
00140 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
00141 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
00142 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
00143 INITIALIZE_PASS_END(FunctionAttrs, "functionattrs",
00144                 "Deduce function attributes", false, false)
00145 
00146 Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); }
00147 
00148 
00149 /// AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
00150 bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) {
00151   SmallPtrSet<Function*, 8> SCCNodes;
00152 
00153   // Fill SCCNodes with the elements of the SCC.  Used for quickly
00154   // looking up whether a given CallGraphNode is in this SCC.
00155   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
00156     SCCNodes.insert((*I)->getFunction());
00157 
00158   // Check if any of the functions in the SCC read or write memory.  If they
00159   // write memory then they can't be marked readnone or readonly.
00160   bool ReadsMemory = false;
00161   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
00162     Function *F = (*I)->getFunction();
00163 
00164     if (!F || F->hasFnAttribute(Attribute::OptimizeNone))
00165       // External node or node we don't want to optimize - assume it may write
00166       // memory and give up.
00167       return false;
00168 
00169     AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(F);
00170     if (MRB == AliasAnalysis::DoesNotAccessMemory)
00171       // Already perfect!
00172       continue;
00173 
00174     // Definitions with weak linkage may be overridden at linktime with
00175     // something that writes memory, so treat them like declarations.
00176     if (F->isDeclaration() || F->mayBeOverridden()) {
00177       if (!AliasAnalysis::onlyReadsMemory(MRB))
00178         // May write memory.  Just give up.
00179         return false;
00180 
00181       ReadsMemory = true;
00182       continue;
00183     }
00184 
00185     // Scan the function body for instructions that may read or write memory.
00186     for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
00187       Instruction *I = &*II;
00188 
00189       // Some instructions can be ignored even if they read or write memory.
00190       // Detect these now, skipping to the next instruction if one is found.
00191       CallSite CS(cast<Value>(I));
00192       if (CS) {
00193         // Ignore calls to functions in the same SCC.
00194         if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
00195           continue;
00196         AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(CS);
00197         // If the call doesn't access arbitrary memory, we may be able to
00198         // figure out something.
00199         if (AliasAnalysis::onlyAccessesArgPointees(MRB)) {
00200           // If the call does access argument pointees, check each argument.
00201           if (AliasAnalysis::doesAccessArgPointees(MRB))
00202             // Check whether all pointer arguments point to local memory, and
00203             // ignore calls that only access local memory.
00204             for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
00205                  CI != CE; ++CI) {
00206               Value *Arg = *CI;
00207               if (Arg->getType()->isPointerTy()) {
00208                 AAMDNodes AAInfo;
00209                 I->getAAMetadata(AAInfo);
00210 
00211                 MemoryLocation Loc(Arg, MemoryLocation::UnknownSize, AAInfo);
00212                 if (!AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) {
00213                   if (MRB & AliasAnalysis::Mod)
00214                     // Writes non-local memory.  Give up.
00215                     return false;
00216                   if (MRB & AliasAnalysis::Ref)
00217                     // Ok, it reads non-local memory.
00218                     ReadsMemory = true;
00219                 }
00220               }
00221             }
00222           continue;
00223         }
00224         // The call could access any memory. If that includes writes, give up.
00225         if (MRB & AliasAnalysis::Mod)
00226           return false;
00227         // If it reads, note it.
00228         if (MRB & AliasAnalysis::Ref)
00229           ReadsMemory = true;
00230         continue;
00231       } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
00232         // Ignore non-volatile loads from local memory. (Atomic is okay here.)
00233         if (!LI->isVolatile()) {
00234           MemoryLocation Loc = MemoryLocation::get(LI);
00235           if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true))
00236             continue;
00237         }
00238       } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
00239         // Ignore non-volatile stores to local memory. (Atomic is okay here.)
00240         if (!SI->isVolatile()) {
00241           MemoryLocation Loc = MemoryLocation::get(SI);
00242           if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true))
00243             continue;
00244         }
00245       } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) {
00246         // Ignore vaargs on local memory.
00247         MemoryLocation Loc = MemoryLocation::get(VI);
00248         if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true))
00249           continue;
00250       }
00251 
00252       // Any remaining instructions need to be taken seriously!  Check if they
00253       // read or write memory.
00254       if (I->mayWriteToMemory())
00255         // Writes memory.  Just give up.
00256         return false;
00257 
00258       // If this instruction may read memory, remember that.
00259       ReadsMemory |= I->mayReadFromMemory();
00260     }
00261   }
00262 
00263   // Success!  Functions in this SCC do not access memory, or only read memory.
00264   // Give them the appropriate attribute.
00265   bool MadeChange = false;
00266   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
00267     Function *F = (*I)->getFunction();
00268 
00269     if (F->doesNotAccessMemory())
00270       // Already perfect!
00271       continue;
00272 
00273     if (F->onlyReadsMemory() && ReadsMemory)
00274       // No change.
00275       continue;
00276 
00277     MadeChange = true;
00278 
00279     // Clear out any existing attributes.
00280     AttrBuilder B;
00281     B.addAttribute(Attribute::ReadOnly)
00282       .addAttribute(Attribute::ReadNone);
00283     F->removeAttributes(AttributeSet::FunctionIndex,
00284                         AttributeSet::get(F->getContext(),
00285                                           AttributeSet::FunctionIndex, B));
00286 
00287     // Add in the new attribute.
00288     F->addAttribute(AttributeSet::FunctionIndex,
00289                     ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone);
00290 
00291     if (ReadsMemory)
00292       ++NumReadOnly;
00293     else
00294       ++NumReadNone;
00295   }
00296 
00297   return MadeChange;
00298 }
00299 
00300 namespace {
00301   // For a given pointer Argument, this retains a list of Arguments of functions
00302   // in the same SCC that the pointer data flows into. We use this to build an
00303   // SCC of the arguments.
00304   struct ArgumentGraphNode {
00305     Argument *Definition;
00306     SmallVector<ArgumentGraphNode*, 4> Uses;
00307   };
00308 
00309   class ArgumentGraph {
00310     // We store pointers to ArgumentGraphNode objects, so it's important that
00311     // that they not move around upon insert.
00312     typedef std::map<Argument*, ArgumentGraphNode> ArgumentMapTy;
00313 
00314     ArgumentMapTy ArgumentMap;
00315 
00316     // There is no root node for the argument graph, in fact:
00317     //   void f(int *x, int *y) { if (...) f(x, y); }
00318     // is an example where the graph is disconnected. The SCCIterator requires a
00319     // single entry point, so we maintain a fake ("synthetic") root node that
00320     // uses every node. Because the graph is directed and nothing points into
00321     // the root, it will not participate in any SCCs (except for its own).
00322     ArgumentGraphNode SyntheticRoot;
00323 
00324   public:
00325     ArgumentGraph() { SyntheticRoot.Definition = nullptr; }
00326 
00327     typedef SmallVectorImpl<ArgumentGraphNode*>::iterator iterator;
00328 
00329     iterator begin() { return SyntheticRoot.Uses.begin(); }
00330     iterator end() { return SyntheticRoot.Uses.end(); }
00331     ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; }
00332 
00333     ArgumentGraphNode *operator[](Argument *A) {
00334       ArgumentGraphNode &Node = ArgumentMap[A];
00335       Node.Definition = A;
00336       SyntheticRoot.Uses.push_back(&Node);
00337       return &Node;
00338     }
00339   };
00340 
00341   // This tracker checks whether callees are in the SCC, and if so it does not
00342   // consider that a capture, instead adding it to the "Uses" list and
00343   // continuing with the analysis.
00344   struct ArgumentUsesTracker : public CaptureTracker {
00345     ArgumentUsesTracker(const SmallPtrSet<Function*, 8> &SCCNodes)
00346       : Captured(false), SCCNodes(SCCNodes) {}
00347 
00348     void tooManyUses() override { Captured = true; }
00349 
00350     bool captured(const Use *U) override {
00351       CallSite CS(U->getUser());
00352       if (!CS.getInstruction()) { Captured = true; return true; }
00353 
00354       Function *F = CS.getCalledFunction();
00355       if (!F || !SCCNodes.count(F)) { Captured = true; return true; }
00356 
00357       bool Found = false;
00358       Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end();
00359       for (CallSite::arg_iterator PI = CS.arg_begin(), PE = CS.arg_end();
00360            PI != PE; ++PI, ++AI) {
00361         if (AI == AE) {
00362           assert(F->isVarArg() && "More params than args in non-varargs call");
00363           Captured = true;
00364           return true;
00365         }
00366         if (PI == U) {
00367           Uses.push_back(AI);
00368           Found = true;
00369           break;
00370         }
00371       }
00372       assert(Found && "Capturing call-site captured nothing?");
00373       (void)Found;
00374       return false;
00375     }
00376 
00377     bool Captured;  // True only if certainly captured (used outside our SCC).
00378     SmallVector<Argument*, 4> Uses;  // Uses within our SCC.
00379 
00380     const SmallPtrSet<Function*, 8> &SCCNodes;
00381   };
00382 }
00383 
00384 namespace llvm {
00385   template<> struct GraphTraits<ArgumentGraphNode*> {
00386     typedef ArgumentGraphNode NodeType;
00387     typedef SmallVectorImpl<ArgumentGraphNode*>::iterator ChildIteratorType;
00388 
00389     static inline NodeType *getEntryNode(NodeType *A) { return A; }
00390     static inline ChildIteratorType child_begin(NodeType *N) {
00391       return N->Uses.begin();
00392     }
00393     static inline ChildIteratorType child_end(NodeType *N) {
00394       return N->Uses.end();
00395     }
00396   };
00397   template<> struct GraphTraits<ArgumentGraph*>
00398     : public GraphTraits<ArgumentGraphNode*> {
00399     static NodeType *getEntryNode(ArgumentGraph *AG) {
00400       return AG->getEntryNode();
00401     }
00402     static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
00403       return AG->begin();
00404     }
00405     static ChildIteratorType nodes_end(ArgumentGraph *AG) {
00406       return AG->end();
00407     }
00408   };
00409 }
00410 
00411 // Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
00412 static Attribute::AttrKind
00413 determinePointerReadAttrs(Argument *A,
00414                           const SmallPtrSet<Argument*, 8> &SCCNodes) {
00415                                                        
00416   SmallVector<Use*, 32> Worklist;
00417   SmallSet<Use*, 32> Visited;
00418   int Count = 0;
00419 
00420   // inalloca arguments are always clobbered by the call.
00421   if (A->hasInAllocaAttr())
00422     return Attribute::None;
00423 
00424   bool IsRead = false;
00425   // We don't need to track IsWritten. If A is written to, return immediately.
00426 
00427   for (Use &U : A->uses()) {
00428     if (Count++ >= 20)
00429       return Attribute::None;
00430 
00431     Visited.insert(&U);
00432     Worklist.push_back(&U);
00433   }
00434 
00435   while (!Worklist.empty()) {
00436     Use *U = Worklist.pop_back_val();
00437     Instruction *I = cast<Instruction>(U->getUser());
00438     Value *V = U->get();
00439 
00440     switch (I->getOpcode()) {
00441     case Instruction::BitCast:
00442     case Instruction::GetElementPtr:
00443     case Instruction::PHI:
00444     case Instruction::Select:
00445     case Instruction::AddrSpaceCast:
00446       // The original value is not read/written via this if the new value isn't.
00447       for (Use &UU : I->uses())
00448         if (Visited.insert(&UU).second)
00449           Worklist.push_back(&UU);
00450       break;
00451 
00452     case Instruction::Call:
00453     case Instruction::Invoke: {
00454       bool Captures = true;
00455 
00456       if (I->getType()->isVoidTy())
00457         Captures = false;
00458 
00459       auto AddUsersToWorklistIfCapturing = [&] {
00460         if (Captures)
00461           for (Use &UU : I->uses())
00462             if (Visited.insert(&UU).second)
00463               Worklist.push_back(&UU);
00464       };
00465 
00466       CallSite CS(I);
00467       if (CS.doesNotAccessMemory()) {
00468         AddUsersToWorklistIfCapturing();
00469         continue;
00470       }
00471 
00472       Function *F = CS.getCalledFunction();
00473       if (!F) {
00474         if (CS.onlyReadsMemory()) {
00475           IsRead = true;
00476           AddUsersToWorklistIfCapturing();
00477           continue;
00478         }
00479         return Attribute::None;
00480       }
00481 
00482       Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end();
00483       CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end();
00484       for (CallSite::arg_iterator A = B; A != E; ++A, ++AI) {
00485         if (A->get() == V) {
00486           if (AI == AE) {
00487             assert(F->isVarArg() &&
00488                    "More params than args in non-varargs call.");
00489             return Attribute::None;
00490           }
00491           Captures &= !CS.doesNotCapture(A - B);
00492           if (SCCNodes.count(AI))
00493             continue;
00494           if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(A - B))
00495             return Attribute::None;
00496           if (!CS.doesNotAccessMemory(A - B))
00497             IsRead = true;
00498         }
00499       }
00500       AddUsersToWorklistIfCapturing();
00501       break;
00502     }
00503 
00504     case Instruction::Load:
00505       IsRead = true;
00506       break;
00507 
00508     case Instruction::ICmp:
00509     case Instruction::Ret:
00510       break;
00511 
00512     default:
00513       return Attribute::None;
00514     }
00515   }
00516 
00517   return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
00518 }
00519 
00520 /// AddArgumentAttrs - Deduce nocapture attributes for the SCC.
00521 bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) {
00522   bool Changed = false;
00523 
00524   SmallPtrSet<Function*, 8> SCCNodes;
00525 
00526   // Fill SCCNodes with the elements of the SCC.  Used for quickly
00527   // looking up whether a given CallGraphNode is in this SCC.
00528   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
00529     Function *F = (*I)->getFunction();
00530     if (F && !F->isDeclaration() && !F->mayBeOverridden() &&
00531         !F->hasFnAttribute(Attribute::OptimizeNone))
00532       SCCNodes.insert(F);
00533   }
00534 
00535   ArgumentGraph AG;
00536 
00537   AttrBuilder B;
00538   B.addAttribute(Attribute::NoCapture);
00539 
00540   // Check each function in turn, determining which pointer arguments are not
00541   // captured.
00542   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
00543     Function *F = (*I)->getFunction();
00544 
00545     if (!F || F->hasFnAttribute(Attribute::OptimizeNone))
00546       // External node or function we're trying not to optimize - only a problem
00547       // for arguments that we pass to it.
00548       continue;
00549 
00550     // Definitions with weak linkage may be overridden at linktime with
00551     // something that captures pointers, so treat them like declarations.
00552     if (F->isDeclaration() || F->mayBeOverridden())
00553       continue;
00554 
00555     // Functions that are readonly (or readnone) and nounwind and don't return
00556     // a value can't capture arguments. Don't analyze them.
00557     if (F->onlyReadsMemory() && F->doesNotThrow() &&
00558         F->getReturnType()->isVoidTy()) {
00559       for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end();
00560            A != E; ++A) {
00561         if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
00562           A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
00563           ++NumNoCapture;
00564           Changed = true;
00565         }
00566       }
00567       continue;
00568     }
00569 
00570     for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end();
00571          A != E; ++A) {
00572       if (!A->getType()->isPointerTy()) continue;
00573       bool HasNonLocalUses = false;
00574       if (!A->hasNoCaptureAttr()) {
00575         ArgumentUsesTracker Tracker(SCCNodes);
00576         PointerMayBeCaptured(A, &Tracker);
00577         if (!Tracker.Captured) {
00578           if (Tracker.Uses.empty()) {
00579             // If it's trivially not captured, mark it nocapture now.
00580             A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo()+1, B));
00581             ++NumNoCapture;
00582             Changed = true;
00583           } else {
00584             // If it's not trivially captured and not trivially not captured,
00585             // then it must be calling into another function in our SCC. Save
00586             // its particulars for Argument-SCC analysis later.
00587             ArgumentGraphNode *Node = AG[A];
00588             for (SmallVectorImpl<Argument*>::iterator UI = Tracker.Uses.begin(),
00589                      UE = Tracker.Uses.end(); UI != UE; ++UI) {
00590               Node->Uses.push_back(AG[*UI]);
00591               if (*UI != A)
00592                 HasNonLocalUses = true;
00593             }
00594           }
00595         }
00596         // Otherwise, it's captured. Don't bother doing SCC analysis on it.
00597       }
00598       if (!HasNonLocalUses && !A->onlyReadsMemory()) {
00599         // Can we determine that it's readonly/readnone without doing an SCC?
00600         // Note that we don't allow any calls at all here, or else our result
00601         // will be dependent on the iteration order through the functions in the
00602         // SCC.
00603         SmallPtrSet<Argument*, 8> Self;
00604         Self.insert(A);
00605         Attribute::AttrKind R = determinePointerReadAttrs(A, Self);
00606         if (R != Attribute::None) {
00607           AttrBuilder B;
00608           B.addAttribute(R);
00609           A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
00610           Changed = true;
00611           R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
00612         }
00613       }
00614     }
00615   }
00616 
00617   // The graph we've collected is partial because we stopped scanning for
00618   // argument uses once we solved the argument trivially. These partial nodes
00619   // show up as ArgumentGraphNode objects with an empty Uses list, and for
00620   // these nodes the final decision about whether they capture has already been
00621   // made.  If the definition doesn't have a 'nocapture' attribute by now, it
00622   // captures.
00623 
00624   for (scc_iterator<ArgumentGraph*> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
00625     const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
00626     if (ArgumentSCC.size() == 1) {
00627       if (!ArgumentSCC[0]->Definition) continue;  // synthetic root node
00628 
00629       // eg. "void f(int* x) { if (...) f(x); }"
00630       if (ArgumentSCC[0]->Uses.size() == 1 &&
00631           ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
00632         Argument *A = ArgumentSCC[0]->Definition;
00633         A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
00634         ++NumNoCapture;
00635         Changed = true;
00636       }
00637       continue;
00638     }
00639 
00640     bool SCCCaptured = false;
00641     for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
00642          I != E && !SCCCaptured; ++I) {
00643       ArgumentGraphNode *Node = *I;
00644       if (Node->Uses.empty()) {
00645         if (!Node->Definition->hasNoCaptureAttr())
00646           SCCCaptured = true;
00647       }
00648     }
00649     if (SCCCaptured) continue;
00650 
00651     SmallPtrSet<Argument*, 8> ArgumentSCCNodes;
00652     // Fill ArgumentSCCNodes with the elements of the ArgumentSCC.  Used for
00653     // quickly looking up whether a given Argument is in this ArgumentSCC.
00654     for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end(); I != E; ++I) {
00655       ArgumentSCCNodes.insert((*I)->Definition);
00656     }
00657 
00658     for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
00659          I != E && !SCCCaptured; ++I) {
00660       ArgumentGraphNode *N = *I;
00661       for (SmallVectorImpl<ArgumentGraphNode*>::iterator UI = N->Uses.begin(),
00662              UE = N->Uses.end(); UI != UE; ++UI) {
00663         Argument *A = (*UI)->Definition;
00664         if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
00665           continue;
00666         SCCCaptured = true;
00667         break;
00668       }
00669     }
00670     if (SCCCaptured) continue;
00671 
00672     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
00673       Argument *A = ArgumentSCC[i]->Definition;
00674       A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
00675       ++NumNoCapture;
00676       Changed = true;
00677     }
00678 
00679     // We also want to compute readonly/readnone. With a small number of false
00680     // negatives, we can assume that any pointer which is captured isn't going
00681     // to be provably readonly or readnone, since by definition we can't
00682     // analyze all uses of a captured pointer.
00683     //
00684     // The false negatives happen when the pointer is captured by a function
00685     // that promises readonly/readnone behaviour on the pointer, then the
00686     // pointer's lifetime ends before anything that writes to arbitrary memory.
00687     // Also, a readonly/readnone pointer may be returned, but returning a
00688     // pointer is capturing it.
00689 
00690     Attribute::AttrKind ReadAttr = Attribute::ReadNone;
00691     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
00692       Argument *A = ArgumentSCC[i]->Definition;
00693       Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes);
00694       if (K == Attribute::ReadNone)
00695         continue;
00696       if (K == Attribute::ReadOnly) {
00697         ReadAttr = Attribute::ReadOnly;
00698         continue;
00699       }
00700       ReadAttr = K;
00701       break;
00702     }
00703 
00704     if (ReadAttr != Attribute::None) {
00705       AttrBuilder B, R;
00706       B.addAttribute(ReadAttr);
00707       R.addAttribute(Attribute::ReadOnly)
00708         .addAttribute(Attribute::ReadNone);
00709       for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
00710         Argument *A = ArgumentSCC[i]->Definition;
00711         // Clear out existing readonly/readnone attributes
00712         A->removeAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, R));
00713         A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
00714         ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
00715         Changed = true;
00716       }
00717     }
00718   }
00719 
00720   return Changed;
00721 }
00722 
00723 /// IsFunctionMallocLike - A function is malloc-like if it returns either null
00724 /// or a pointer that doesn't alias any other pointer visible to the caller.
00725 bool FunctionAttrs::IsFunctionMallocLike(Function *F,
00726                               SmallPtrSet<Function*, 8> &SCCNodes) const {
00727   SmallSetVector<Value *, 8> FlowsToReturn;
00728   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
00729     if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator()))
00730       FlowsToReturn.insert(Ret->getReturnValue());
00731 
00732   for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
00733     Value *RetVal = FlowsToReturn[i];
00734 
00735     if (Constant *C = dyn_cast<Constant>(RetVal)) {
00736       if (!C->isNullValue() && !isa<UndefValue>(C))
00737         return false;
00738 
00739       continue;
00740     }
00741 
00742     if (isa<Argument>(RetVal))
00743       return false;
00744 
00745     if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
00746       switch (RVI->getOpcode()) {
00747         // Extend the analysis by looking upwards.
00748         case Instruction::BitCast:
00749         case Instruction::GetElementPtr:
00750         case Instruction::AddrSpaceCast:
00751           FlowsToReturn.insert(RVI->getOperand(0));
00752           continue;
00753         case Instruction::Select: {
00754           SelectInst *SI = cast<SelectInst>(RVI);
00755           FlowsToReturn.insert(SI->getTrueValue());
00756           FlowsToReturn.insert(SI->getFalseValue());
00757           continue;
00758         }
00759         case Instruction::PHI: {
00760           PHINode *PN = cast<PHINode>(RVI);
00761           for (Value *IncValue : PN->incoming_values())
00762             FlowsToReturn.insert(IncValue);
00763           continue;
00764         }
00765 
00766         // Check whether the pointer came from an allocation.
00767         case Instruction::Alloca:
00768           break;
00769         case Instruction::Call:
00770         case Instruction::Invoke: {
00771           CallSite CS(RVI);
00772           if (CS.paramHasAttr(0, Attribute::NoAlias))
00773             break;
00774           if (CS.getCalledFunction() &&
00775               SCCNodes.count(CS.getCalledFunction()))
00776             break;
00777         } // fall-through
00778         default:
00779           return false;  // Did not come from an allocation.
00780       }
00781 
00782     if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
00783       return false;
00784   }
00785 
00786   return true;
00787 }
00788 
00789 /// AddNoAliasAttrs - Deduce noalias attributes for the SCC.
00790 bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) {
00791   SmallPtrSet<Function*, 8> SCCNodes;
00792 
00793   // Fill SCCNodes with the elements of the SCC.  Used for quickly
00794   // looking up whether a given CallGraphNode is in this SCC.
00795   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
00796     SCCNodes.insert((*I)->getFunction());
00797 
00798   // Check each function in turn, determining which functions return noalias
00799   // pointers.
00800   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
00801     Function *F = (*I)->getFunction();
00802 
00803     if (!F || F->hasFnAttribute(Attribute::OptimizeNone))
00804       // External node or node we don't want to optimize - skip it;
00805       return false;
00806 
00807     // Already noalias.
00808     if (F->doesNotAlias(0))
00809       continue;
00810 
00811     // Definitions with weak linkage may be overridden at linktime, so
00812     // treat them like declarations.
00813     if (F->isDeclaration() || F->mayBeOverridden())
00814       return false;
00815 
00816     // We annotate noalias return values, which are only applicable to 
00817     // pointer types.
00818     if (!F->getReturnType()->isPointerTy())
00819       continue;
00820 
00821     if (!IsFunctionMallocLike(F, SCCNodes))
00822       return false;
00823   }
00824 
00825   bool MadeChange = false;
00826   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
00827     Function *F = (*I)->getFunction();
00828     if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy())
00829       continue;
00830 
00831     F->setDoesNotAlias(0);
00832     ++NumNoAlias;
00833     MadeChange = true;
00834   }
00835 
00836   return MadeChange;
00837 }
00838 
00839 /// inferPrototypeAttributes - Analyze the name and prototype of the
00840 /// given function and set any applicable attributes.  Returns true
00841 /// if any attributes were set and false otherwise.
00842 bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
00843   if (F.hasFnAttribute(Attribute::OptimizeNone))
00844     return false;
00845 
00846   FunctionType *FTy = F.getFunctionType();
00847   LibFunc::Func TheLibFunc;
00848   if (!(TLI->getLibFunc(F.getName(), TheLibFunc) && TLI->has(TheLibFunc)))
00849     return false;
00850 
00851   switch (TheLibFunc) {
00852   case LibFunc::strlen:
00853     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
00854       return false;
00855     setOnlyReadsMemory(F);
00856     setDoesNotThrow(F);
00857     setDoesNotCapture(F, 1);
00858     break;
00859   case LibFunc::strchr:
00860   case LibFunc::strrchr:
00861     if (FTy->getNumParams() != 2 ||
00862         !FTy->getParamType(0)->isPointerTy() ||
00863         !FTy->getParamType(1)->isIntegerTy())
00864       return false;
00865     setOnlyReadsMemory(F);
00866     setDoesNotThrow(F);
00867     break;
00868   case LibFunc::strtol:
00869   case LibFunc::strtod:
00870   case LibFunc::strtof:
00871   case LibFunc::strtoul:
00872   case LibFunc::strtoll:
00873   case LibFunc::strtold:
00874   case LibFunc::strtoull:
00875     if (FTy->getNumParams() < 2 ||
00876         !FTy->getParamType(1)->isPointerTy())
00877       return false;
00878     setDoesNotThrow(F);
00879     setDoesNotCapture(F, 2);
00880     setOnlyReadsMemory(F, 1);
00881     break;
00882   case LibFunc::strcpy:
00883   case LibFunc::stpcpy:
00884   case LibFunc::strcat:
00885   case LibFunc::strncat:
00886   case LibFunc::strncpy:
00887   case LibFunc::stpncpy:
00888     if (FTy->getNumParams() < 2 ||
00889         !FTy->getParamType(1)->isPointerTy())
00890       return false;
00891     setDoesNotThrow(F);
00892     setDoesNotCapture(F, 2);
00893     setOnlyReadsMemory(F, 2);
00894     break;
00895   case LibFunc::strxfrm:
00896     if (FTy->getNumParams() != 3 ||
00897         !FTy->getParamType(0)->isPointerTy() ||
00898         !FTy->getParamType(1)->isPointerTy())
00899       return false;
00900     setDoesNotThrow(F);
00901     setDoesNotCapture(F, 1);
00902     setDoesNotCapture(F, 2);
00903     setOnlyReadsMemory(F, 2);
00904     break;
00905   case LibFunc::strcmp: //0,1
00906     case LibFunc::strspn: // 0,1
00907     case LibFunc::strncmp: // 0,1
00908     case LibFunc::strcspn: //0,1
00909     case LibFunc::strcoll: //0,1
00910     case LibFunc::strcasecmp:  // 0,1
00911     case LibFunc::strncasecmp: // 
00912     if (FTy->getNumParams() < 2 ||
00913         !FTy->getParamType(0)->isPointerTy() ||
00914         !FTy->getParamType(1)->isPointerTy())
00915       return false;
00916     setOnlyReadsMemory(F);
00917     setDoesNotThrow(F);
00918     setDoesNotCapture(F, 1);
00919     setDoesNotCapture(F, 2);
00920     break;
00921   case LibFunc::strstr:
00922   case LibFunc::strpbrk:
00923     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
00924       return false;
00925     setOnlyReadsMemory(F);
00926     setDoesNotThrow(F);
00927     setDoesNotCapture(F, 2);
00928     break;
00929   case LibFunc::strtok:
00930   case LibFunc::strtok_r:
00931     if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
00932       return false;
00933     setDoesNotThrow(F);
00934     setDoesNotCapture(F, 2);
00935     setOnlyReadsMemory(F, 2);
00936     break;
00937   case LibFunc::scanf:
00938     if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
00939       return false;
00940     setDoesNotThrow(F);
00941     setDoesNotCapture(F, 1);
00942     setOnlyReadsMemory(F, 1);
00943     break;
00944   case LibFunc::setbuf:
00945   case LibFunc::setvbuf:
00946     if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
00947       return false;
00948     setDoesNotThrow(F);
00949     setDoesNotCapture(F, 1);
00950     break;
00951   case LibFunc::strdup:
00952   case LibFunc::strndup:
00953     if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() ||
00954         !FTy->getParamType(0)->isPointerTy())
00955       return false;
00956     setDoesNotThrow(F);
00957     setDoesNotAlias(F, 0);
00958     setDoesNotCapture(F, 1);
00959     setOnlyReadsMemory(F, 1);
00960     break;
00961   case LibFunc::stat:
00962   case LibFunc::statvfs:
00963     if (FTy->getNumParams() < 2 ||
00964         !FTy->getParamType(0)->isPointerTy() ||
00965         !FTy->getParamType(1)->isPointerTy())
00966       return false;
00967     setDoesNotThrow(F);
00968     setDoesNotCapture(F, 1);
00969     setDoesNotCapture(F, 2);
00970     setOnlyReadsMemory(F, 1);
00971     break;
00972   case LibFunc::sscanf:
00973     if (FTy->getNumParams() < 2 ||
00974         !FTy->getParamType(0)->isPointerTy() ||
00975         !FTy->getParamType(1)->isPointerTy())
00976       return false;
00977     setDoesNotThrow(F);
00978     setDoesNotCapture(F, 1);
00979     setDoesNotCapture(F, 2);
00980     setOnlyReadsMemory(F, 1);
00981     setOnlyReadsMemory(F, 2);
00982     break;
00983   case LibFunc::sprintf:
00984     if (FTy->getNumParams() < 2 ||
00985         !FTy->getParamType(0)->isPointerTy() ||
00986         !FTy->getParamType(1)->isPointerTy())
00987       return false;
00988     setDoesNotThrow(F);
00989     setDoesNotCapture(F, 1);
00990     setDoesNotCapture(F, 2);
00991     setOnlyReadsMemory(F, 2);
00992     break;
00993   case LibFunc::snprintf:
00994     if (FTy->getNumParams() != 3 ||
00995         !FTy->getParamType(0)->isPointerTy() ||
00996         !FTy->getParamType(2)->isPointerTy())
00997       return false;
00998     setDoesNotThrow(F);
00999     setDoesNotCapture(F, 1);
01000     setDoesNotCapture(F, 3);
01001     setOnlyReadsMemory(F, 3);
01002     break;
01003   case LibFunc::setitimer:
01004     if (FTy->getNumParams() != 3 ||
01005         !FTy->getParamType(1)->isPointerTy() ||
01006         !FTy->getParamType(2)->isPointerTy())
01007       return false;
01008     setDoesNotThrow(F);
01009     setDoesNotCapture(F, 2);
01010     setDoesNotCapture(F, 3);
01011     setOnlyReadsMemory(F, 2);
01012     break;
01013   case LibFunc::system:
01014     if (FTy->getNumParams() != 1 ||
01015         !FTy->getParamType(0)->isPointerTy())
01016       return false;
01017     // May throw; "system" is a valid pthread cancellation point.
01018     setDoesNotCapture(F, 1);
01019     setOnlyReadsMemory(F, 1);
01020     break;
01021   case LibFunc::malloc:
01022     if (FTy->getNumParams() != 1 ||
01023         !FTy->getReturnType()->isPointerTy())
01024       return false;
01025     setDoesNotThrow(F);
01026     setDoesNotAlias(F, 0);
01027     break;
01028   case LibFunc::memcmp:
01029     if (FTy->getNumParams() != 3 ||
01030         !FTy->getParamType(0)->isPointerTy() ||
01031         !FTy->getParamType(1)->isPointerTy())
01032       return false;
01033     setOnlyReadsMemory(F);
01034     setDoesNotThrow(F);
01035     setDoesNotCapture(F, 1);
01036     setDoesNotCapture(F, 2);
01037     break;
01038   case LibFunc::memchr:
01039   case LibFunc::memrchr:
01040     if (FTy->getNumParams() != 3)
01041       return false;
01042     setOnlyReadsMemory(F);
01043     setDoesNotThrow(F);
01044     break;
01045   case LibFunc::modf:
01046   case LibFunc::modff:
01047   case LibFunc::modfl:
01048     if (FTy->getNumParams() < 2 ||
01049         !FTy->getParamType(1)->isPointerTy())
01050       return false;
01051     setDoesNotThrow(F);
01052     setDoesNotCapture(F, 2);
01053     break;
01054   case LibFunc::memcpy:
01055   case LibFunc::memccpy:
01056   case LibFunc::memmove:
01057     if (FTy->getNumParams() < 2 ||
01058         !FTy->getParamType(1)->isPointerTy())
01059       return false;
01060     setDoesNotThrow(F);
01061     setDoesNotCapture(F, 2);
01062     setOnlyReadsMemory(F, 2);
01063     break;
01064   case LibFunc::memalign:
01065     if (!FTy->getReturnType()->isPointerTy())
01066       return false;
01067     setDoesNotAlias(F, 0);
01068     break;
01069   case LibFunc::mkdir:
01070     if (FTy->getNumParams() == 0 ||
01071         !FTy->getParamType(0)->isPointerTy())
01072       return false;
01073     setDoesNotThrow(F);
01074     setDoesNotCapture(F, 1);
01075     setOnlyReadsMemory(F, 1);
01076     break;
01077   case LibFunc::mktime:
01078     if (FTy->getNumParams() == 0 ||
01079         !FTy->getParamType(0)->isPointerTy())
01080       return false;
01081     setDoesNotThrow(F);
01082     setDoesNotCapture(F, 1);
01083     break;
01084   case LibFunc::realloc:
01085     if (FTy->getNumParams() != 2 ||
01086         !FTy->getParamType(0)->isPointerTy() ||
01087         !FTy->getReturnType()->isPointerTy())
01088       return false;
01089     setDoesNotThrow(F);
01090     setDoesNotAlias(F, 0);
01091     setDoesNotCapture(F, 1);
01092     break;
01093   case LibFunc::read:
01094     if (FTy->getNumParams() != 3 ||
01095         !FTy->getParamType(1)->isPointerTy())
01096       return false;
01097     // May throw; "read" is a valid pthread cancellation point.
01098     setDoesNotCapture(F, 2);
01099     break;
01100   case LibFunc::rewind:
01101     if (FTy->getNumParams() < 1 ||
01102         !FTy->getParamType(0)->isPointerTy())
01103       return false;
01104     setDoesNotThrow(F);
01105     setDoesNotCapture(F, 1);
01106     break;
01107   case LibFunc::rmdir:
01108   case LibFunc::remove:
01109   case LibFunc::realpath:
01110     if (FTy->getNumParams() < 1 ||
01111         !FTy->getParamType(0)->isPointerTy())
01112       return false;
01113     setDoesNotThrow(F);
01114     setDoesNotCapture(F, 1);
01115     setOnlyReadsMemory(F, 1);
01116     break;
01117   case LibFunc::rename:
01118     if (FTy->getNumParams() < 2 ||
01119         !FTy->getParamType(0)->isPointerTy() ||
01120         !FTy->getParamType(1)->isPointerTy())
01121       return false;
01122     setDoesNotThrow(F);
01123     setDoesNotCapture(F, 1);
01124     setDoesNotCapture(F, 2);
01125     setOnlyReadsMemory(F, 1);
01126     setOnlyReadsMemory(F, 2);
01127     break;
01128   case LibFunc::readlink:
01129     if (FTy->getNumParams() < 2 ||
01130         !FTy->getParamType(0)->isPointerTy() ||
01131         !FTy->getParamType(1)->isPointerTy())
01132       return false;
01133     setDoesNotThrow(F);
01134     setDoesNotCapture(F, 1);
01135     setDoesNotCapture(F, 2);
01136     setOnlyReadsMemory(F, 1);
01137     break;
01138   case LibFunc::write:
01139     if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
01140       return false;
01141     // May throw; "write" is a valid pthread cancellation point.
01142     setDoesNotCapture(F, 2);
01143     setOnlyReadsMemory(F, 2);
01144     break;
01145   case LibFunc::bcopy:
01146     if (FTy->getNumParams() != 3 ||
01147         !FTy->getParamType(0)->isPointerTy() ||
01148         !FTy->getParamType(1)->isPointerTy())
01149       return false;
01150     setDoesNotThrow(F);
01151     setDoesNotCapture(F, 1);
01152     setDoesNotCapture(F, 2);
01153     setOnlyReadsMemory(F, 1);
01154     break;
01155   case LibFunc::bcmp:
01156     if (FTy->getNumParams() != 3 ||
01157         !FTy->getParamType(0)->isPointerTy() ||
01158         !FTy->getParamType(1)->isPointerTy())
01159       return false;
01160     setDoesNotThrow(F);
01161     setOnlyReadsMemory(F);
01162     setDoesNotCapture(F, 1);
01163     setDoesNotCapture(F, 2);
01164     break;
01165   case LibFunc::bzero:
01166     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
01167       return false;
01168     setDoesNotThrow(F);
01169     setDoesNotCapture(F, 1);
01170     break;
01171   case LibFunc::calloc:
01172     if (FTy->getNumParams() != 2 ||
01173         !FTy->getReturnType()->isPointerTy())
01174       return false;
01175     setDoesNotThrow(F);
01176     setDoesNotAlias(F, 0);
01177     break;
01178   case LibFunc::chmod:
01179   case LibFunc::chown:
01180     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
01181       return false;
01182     setDoesNotThrow(F);
01183     setDoesNotCapture(F, 1);
01184     setOnlyReadsMemory(F, 1);
01185     break;
01186   case LibFunc::ctermid:
01187   case LibFunc::clearerr:
01188   case LibFunc::closedir:
01189     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
01190       return false;
01191     setDoesNotThrow(F);
01192     setDoesNotCapture(F, 1);
01193     break;
01194   case LibFunc::atoi:
01195   case LibFunc::atol:
01196   case LibFunc::atof:
01197   case LibFunc::atoll:
01198     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01199       return false;
01200     setDoesNotThrow(F);
01201     setOnlyReadsMemory(F);
01202     setDoesNotCapture(F, 1);
01203     break;
01204   case LibFunc::access:
01205     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
01206       return false;
01207     setDoesNotThrow(F);
01208     setDoesNotCapture(F, 1);
01209     setOnlyReadsMemory(F, 1);
01210     break;
01211   case LibFunc::fopen:
01212     if (FTy->getNumParams() != 2 ||
01213         !FTy->getReturnType()->isPointerTy() ||
01214         !FTy->getParamType(0)->isPointerTy() ||
01215         !FTy->getParamType(1)->isPointerTy())
01216       return false;
01217     setDoesNotThrow(F);
01218     setDoesNotAlias(F, 0);
01219     setDoesNotCapture(F, 1);
01220     setDoesNotCapture(F, 2);
01221     setOnlyReadsMemory(F, 1);
01222     setOnlyReadsMemory(F, 2);
01223     break;
01224   case LibFunc::fdopen:
01225     if (FTy->getNumParams() != 2 ||
01226         !FTy->getReturnType()->isPointerTy() ||
01227         !FTy->getParamType(1)->isPointerTy())
01228       return false;
01229     setDoesNotThrow(F);
01230     setDoesNotAlias(F, 0);
01231     setDoesNotCapture(F, 2);
01232     setOnlyReadsMemory(F, 2);
01233     break;
01234   case LibFunc::feof:
01235   case LibFunc::free:
01236   case LibFunc::fseek:
01237   case LibFunc::ftell:
01238   case LibFunc::fgetc:
01239   case LibFunc::fseeko:
01240   case LibFunc::ftello:
01241   case LibFunc::fileno:
01242   case LibFunc::fflush:
01243   case LibFunc::fclose:
01244   case LibFunc::fsetpos:
01245   case LibFunc::flockfile:
01246   case LibFunc::funlockfile:
01247   case LibFunc::ftrylockfile:
01248     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
01249       return false;
01250     setDoesNotThrow(F);
01251     setDoesNotCapture(F, 1);
01252     break;
01253   case LibFunc::ferror:
01254     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01255       return false;
01256     setDoesNotThrow(F);
01257     setDoesNotCapture(F, 1);
01258     setOnlyReadsMemory(F);
01259     break;
01260   case LibFunc::fputc:
01261   case LibFunc::fstat:
01262   case LibFunc::frexp:
01263   case LibFunc::frexpf:
01264   case LibFunc::frexpl:
01265   case LibFunc::fstatvfs:
01266     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
01267       return false;
01268     setDoesNotThrow(F);
01269     setDoesNotCapture(F, 2);
01270     break;
01271   case LibFunc::fgets:
01272     if (FTy->getNumParams() != 3 ||
01273         !FTy->getParamType(0)->isPointerTy() ||
01274         !FTy->getParamType(2)->isPointerTy())
01275       return false;
01276     setDoesNotThrow(F);
01277     setDoesNotCapture(F, 3);
01278     break;
01279   case LibFunc::fread:
01280     if (FTy->getNumParams() != 4 ||
01281         !FTy->getParamType(0)->isPointerTy() ||
01282         !FTy->getParamType(3)->isPointerTy())
01283       return false;
01284     setDoesNotThrow(F);
01285     setDoesNotCapture(F, 1);
01286     setDoesNotCapture(F, 4);
01287     break;
01288   case LibFunc::fwrite:
01289     if (FTy->getNumParams() != 4 ||
01290         !FTy->getParamType(0)->isPointerTy() ||
01291         !FTy->getParamType(3)->isPointerTy())
01292       return false;
01293     setDoesNotThrow(F);
01294     setDoesNotCapture(F, 1);
01295     setDoesNotCapture(F, 4);
01296     break;
01297   case LibFunc::fputs:
01298     if (FTy->getNumParams() < 2 ||
01299         !FTy->getParamType(0)->isPointerTy() ||
01300         !FTy->getParamType(1)->isPointerTy())
01301       return false;
01302     setDoesNotThrow(F);
01303     setDoesNotCapture(F, 1);
01304     setDoesNotCapture(F, 2);
01305     setOnlyReadsMemory(F, 1);
01306     break;
01307   case LibFunc::fscanf:
01308   case LibFunc::fprintf:
01309     if (FTy->getNumParams() < 2 ||
01310         !FTy->getParamType(0)->isPointerTy() ||
01311         !FTy->getParamType(1)->isPointerTy())
01312       return false;
01313     setDoesNotThrow(F);
01314     setDoesNotCapture(F, 1);
01315     setDoesNotCapture(F, 2);
01316     setOnlyReadsMemory(F, 2);
01317     break;
01318   case LibFunc::fgetpos:
01319     if (FTy->getNumParams() < 2 ||
01320         !FTy->getParamType(0)->isPointerTy() ||
01321         !FTy->getParamType(1)->isPointerTy())
01322       return false;
01323     setDoesNotThrow(F);
01324     setDoesNotCapture(F, 1);
01325     setDoesNotCapture(F, 2);
01326     break;
01327   case LibFunc::getc:
01328   case LibFunc::getlogin_r:
01329   case LibFunc::getc_unlocked:
01330     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
01331       return false;
01332     setDoesNotThrow(F);
01333     setDoesNotCapture(F, 1);
01334     break;
01335   case LibFunc::getenv:
01336     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01337       return false;
01338     setDoesNotThrow(F);
01339     setOnlyReadsMemory(F);
01340     setDoesNotCapture(F, 1);
01341     break;
01342   case LibFunc::gets:
01343   case LibFunc::getchar:
01344     setDoesNotThrow(F);
01345     break;
01346   case LibFunc::getitimer:
01347     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
01348       return false;
01349     setDoesNotThrow(F);
01350     setDoesNotCapture(F, 2);
01351     break;
01352   case LibFunc::getpwnam:
01353     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01354       return false;
01355     setDoesNotThrow(F);
01356     setDoesNotCapture(F, 1);
01357     setOnlyReadsMemory(F, 1);
01358     break;
01359   case LibFunc::ungetc:
01360     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
01361       return false;
01362     setDoesNotThrow(F);
01363     setDoesNotCapture(F, 2);
01364     break;
01365   case LibFunc::uname:
01366     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01367       return false;
01368     setDoesNotThrow(F);
01369     setDoesNotCapture(F, 1);
01370     break;
01371   case LibFunc::unlink:
01372     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01373       return false;
01374     setDoesNotThrow(F);
01375     setDoesNotCapture(F, 1);
01376     setOnlyReadsMemory(F, 1);
01377     break;
01378   case LibFunc::unsetenv:
01379     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01380       return false;
01381     setDoesNotThrow(F);
01382     setDoesNotCapture(F, 1);
01383     setOnlyReadsMemory(F, 1);
01384     break;
01385   case LibFunc::utime:
01386   case LibFunc::utimes:
01387     if (FTy->getNumParams() != 2 ||
01388         !FTy->getParamType(0)->isPointerTy() ||
01389         !FTy->getParamType(1)->isPointerTy())
01390       return false;
01391     setDoesNotThrow(F);
01392     setDoesNotCapture(F, 1);
01393     setDoesNotCapture(F, 2);
01394     setOnlyReadsMemory(F, 1);
01395     setOnlyReadsMemory(F, 2);
01396     break;
01397   case LibFunc::putc:
01398     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
01399       return false;
01400     setDoesNotThrow(F);
01401     setDoesNotCapture(F, 2);
01402     break;
01403   case LibFunc::puts:
01404   case LibFunc::printf:
01405   case LibFunc::perror:
01406     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01407       return false;
01408     setDoesNotThrow(F);
01409     setDoesNotCapture(F, 1);
01410     setOnlyReadsMemory(F, 1);
01411     break;
01412   case LibFunc::pread:
01413     if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
01414       return false;
01415     // May throw; "pread" is a valid pthread cancellation point.
01416     setDoesNotCapture(F, 2);
01417     break;
01418   case LibFunc::pwrite:
01419     if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
01420       return false;
01421     // May throw; "pwrite" is a valid pthread cancellation point.
01422     setDoesNotCapture(F, 2);
01423     setOnlyReadsMemory(F, 2);
01424     break;
01425   case LibFunc::putchar:
01426     setDoesNotThrow(F);
01427     break;
01428   case LibFunc::popen:
01429     if (FTy->getNumParams() != 2 ||
01430         !FTy->getReturnType()->isPointerTy() ||
01431         !FTy->getParamType(0)->isPointerTy() ||
01432         !FTy->getParamType(1)->isPointerTy())
01433       return false;
01434     setDoesNotThrow(F);
01435     setDoesNotAlias(F, 0);
01436     setDoesNotCapture(F, 1);
01437     setDoesNotCapture(F, 2);
01438     setOnlyReadsMemory(F, 1);
01439     setOnlyReadsMemory(F, 2);
01440     break;
01441   case LibFunc::pclose:
01442     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01443       return false;
01444     setDoesNotThrow(F);
01445     setDoesNotCapture(F, 1);
01446     break;
01447   case LibFunc::vscanf:
01448     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
01449       return false;
01450     setDoesNotThrow(F);
01451     setDoesNotCapture(F, 1);
01452     setOnlyReadsMemory(F, 1);
01453     break;
01454   case LibFunc::vsscanf:
01455     if (FTy->getNumParams() != 3 ||
01456         !FTy->getParamType(1)->isPointerTy() ||
01457         !FTy->getParamType(2)->isPointerTy())
01458       return false;
01459     setDoesNotThrow(F);
01460     setDoesNotCapture(F, 1);
01461     setDoesNotCapture(F, 2);
01462     setOnlyReadsMemory(F, 1);
01463     setOnlyReadsMemory(F, 2);
01464     break;
01465   case LibFunc::vfscanf:
01466     if (FTy->getNumParams() != 3 ||
01467         !FTy->getParamType(1)->isPointerTy() ||
01468         !FTy->getParamType(2)->isPointerTy())
01469       return false;
01470     setDoesNotThrow(F);
01471     setDoesNotCapture(F, 1);
01472     setDoesNotCapture(F, 2);
01473     setOnlyReadsMemory(F, 2);
01474     break;
01475   case LibFunc::valloc:
01476     if (!FTy->getReturnType()->isPointerTy())
01477       return false;
01478     setDoesNotThrow(F);
01479     setDoesNotAlias(F, 0);
01480     break;
01481   case LibFunc::vprintf:
01482     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
01483       return false;
01484     setDoesNotThrow(F);
01485     setDoesNotCapture(F, 1);
01486     setOnlyReadsMemory(F, 1);
01487     break;
01488   case LibFunc::vfprintf:
01489   case LibFunc::vsprintf:
01490     if (FTy->getNumParams() != 3 ||
01491         !FTy->getParamType(0)->isPointerTy() ||
01492         !FTy->getParamType(1)->isPointerTy())
01493       return false;
01494     setDoesNotThrow(F);
01495     setDoesNotCapture(F, 1);
01496     setDoesNotCapture(F, 2);
01497     setOnlyReadsMemory(F, 2);
01498     break;
01499   case LibFunc::vsnprintf:
01500     if (FTy->getNumParams() != 4 ||
01501         !FTy->getParamType(0)->isPointerTy() ||
01502         !FTy->getParamType(2)->isPointerTy())
01503       return false;
01504     setDoesNotThrow(F);
01505     setDoesNotCapture(F, 1);
01506     setDoesNotCapture(F, 3);
01507     setOnlyReadsMemory(F, 3);
01508     break;
01509   case LibFunc::open:
01510     if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
01511       return false;
01512     // May throw; "open" is a valid pthread cancellation point.
01513     setDoesNotCapture(F, 1);
01514     setOnlyReadsMemory(F, 1);
01515     break;
01516   case LibFunc::opendir:
01517     if (FTy->getNumParams() != 1 ||
01518         !FTy->getReturnType()->isPointerTy() ||
01519         !FTy->getParamType(0)->isPointerTy())
01520       return false;
01521     setDoesNotThrow(F);
01522     setDoesNotAlias(F, 0);
01523     setDoesNotCapture(F, 1);
01524     setOnlyReadsMemory(F, 1);
01525     break;
01526   case LibFunc::tmpfile:
01527     if (!FTy->getReturnType()->isPointerTy())
01528       return false;
01529     setDoesNotThrow(F);
01530     setDoesNotAlias(F, 0);
01531     break;
01532   case LibFunc::times:
01533     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01534       return false;
01535     setDoesNotThrow(F);
01536     setDoesNotCapture(F, 1);
01537     break;
01538   case LibFunc::htonl:
01539   case LibFunc::htons:
01540   case LibFunc::ntohl:
01541   case LibFunc::ntohs:
01542     setDoesNotThrow(F);
01543     setDoesNotAccessMemory(F);
01544     break;
01545   case LibFunc::lstat:
01546     if (FTy->getNumParams() != 2 ||
01547         !FTy->getParamType(0)->isPointerTy() ||
01548         !FTy->getParamType(1)->isPointerTy())
01549       return false;
01550     setDoesNotThrow(F);
01551     setDoesNotCapture(F, 1);
01552     setDoesNotCapture(F, 2);
01553     setOnlyReadsMemory(F, 1);
01554     break;
01555   case LibFunc::lchown:
01556     if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy())
01557       return false;
01558     setDoesNotThrow(F);
01559     setDoesNotCapture(F, 1);
01560     setOnlyReadsMemory(F, 1);
01561     break;
01562   case LibFunc::qsort:
01563     if (FTy->getNumParams() != 4 || !FTy->getParamType(3)->isPointerTy())
01564       return false;
01565     // May throw; places call through function pointer.
01566     setDoesNotCapture(F, 4);
01567     break;
01568   case LibFunc::dunder_strdup:
01569   case LibFunc::dunder_strndup:
01570     if (FTy->getNumParams() < 1 ||
01571         !FTy->getReturnType()->isPointerTy() ||
01572         !FTy->getParamType(0)->isPointerTy())
01573       return false;
01574     setDoesNotThrow(F);
01575     setDoesNotAlias(F, 0);
01576     setDoesNotCapture(F, 1);
01577     setOnlyReadsMemory(F, 1);
01578     break;
01579   case LibFunc::dunder_strtok_r:
01580     if (FTy->getNumParams() != 3 ||
01581         !FTy->getParamType(1)->isPointerTy())
01582       return false;
01583     setDoesNotThrow(F);
01584     setDoesNotCapture(F, 2);
01585     setOnlyReadsMemory(F, 2);
01586     break;
01587   case LibFunc::under_IO_getc:
01588     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01589       return false;
01590     setDoesNotThrow(F);
01591     setDoesNotCapture(F, 1);
01592     break;
01593   case LibFunc::under_IO_putc:
01594     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
01595       return false;
01596     setDoesNotThrow(F);
01597     setDoesNotCapture(F, 2);
01598     break;
01599   case LibFunc::dunder_isoc99_scanf:
01600     if (FTy->getNumParams() < 1 ||
01601         !FTy->getParamType(0)->isPointerTy())
01602       return false;
01603     setDoesNotThrow(F);
01604     setDoesNotCapture(F, 1);
01605     setOnlyReadsMemory(F, 1);
01606     break;
01607   case LibFunc::stat64:
01608   case LibFunc::lstat64:
01609   case LibFunc::statvfs64:
01610     if (FTy->getNumParams() < 1 ||
01611         !FTy->getParamType(0)->isPointerTy() ||
01612         !FTy->getParamType(1)->isPointerTy())
01613       return false;
01614     setDoesNotThrow(F);
01615     setDoesNotCapture(F, 1);
01616     setDoesNotCapture(F, 2);
01617     setOnlyReadsMemory(F, 1);
01618     break;
01619   case LibFunc::dunder_isoc99_sscanf:
01620     if (FTy->getNumParams() < 1 ||
01621         !FTy->getParamType(0)->isPointerTy() ||
01622         !FTy->getParamType(1)->isPointerTy())
01623       return false;
01624     setDoesNotThrow(F);
01625     setDoesNotCapture(F, 1);
01626     setDoesNotCapture(F, 2);
01627     setOnlyReadsMemory(F, 1);
01628     setOnlyReadsMemory(F, 2);
01629     break;
01630   case LibFunc::fopen64:
01631     if (FTy->getNumParams() != 2 ||
01632         !FTy->getReturnType()->isPointerTy() ||
01633         !FTy->getParamType(0)->isPointerTy() ||
01634         !FTy->getParamType(1)->isPointerTy())
01635       return false;
01636     setDoesNotThrow(F);
01637     setDoesNotAlias(F, 0);
01638     setDoesNotCapture(F, 1);
01639     setDoesNotCapture(F, 2);
01640     setOnlyReadsMemory(F, 1);
01641     setOnlyReadsMemory(F, 2);
01642     break;
01643   case LibFunc::fseeko64:
01644   case LibFunc::ftello64:
01645     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
01646       return false;
01647     setDoesNotThrow(F);
01648     setDoesNotCapture(F, 1);
01649     break;
01650   case LibFunc::tmpfile64:
01651     if (!FTy->getReturnType()->isPointerTy())
01652       return false;
01653     setDoesNotThrow(F);
01654     setDoesNotAlias(F, 0);
01655     break;
01656   case LibFunc::fstat64:
01657   case LibFunc::fstatvfs64:
01658     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
01659       return false;
01660     setDoesNotThrow(F);
01661     setDoesNotCapture(F, 2);
01662     break;
01663   case LibFunc::open64:
01664     if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
01665       return false;
01666     // May throw; "open" is a valid pthread cancellation point.
01667     setDoesNotCapture(F, 1);
01668     setOnlyReadsMemory(F, 1);
01669     break;
01670   case LibFunc::gettimeofday:
01671     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
01672         !FTy->getParamType(1)->isPointerTy())
01673       return false;
01674     // Currently some platforms have the restrict keyword on the arguments to
01675     // gettimeofday. To be conservative, do not add noalias to gettimeofday's
01676     // arguments.
01677     setDoesNotThrow(F);
01678     setDoesNotCapture(F, 1);
01679     setDoesNotCapture(F, 2);
01680     break;
01681   default:
01682     // Didn't mark any attributes.
01683     return false;
01684   }
01685 
01686   return true;
01687 }
01688 
01689 /// annotateLibraryCalls - Adds attributes to well-known standard library
01690 /// call declarations.
01691 bool FunctionAttrs::annotateLibraryCalls(const CallGraphSCC &SCC) {
01692   bool MadeChange = false;
01693 
01694   // Check each function in turn annotating well-known library function
01695   // declarations with attributes.
01696   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
01697     Function *F = (*I)->getFunction();
01698 
01699     if (F && F->isDeclaration())
01700       MadeChange |= inferPrototypeAttributes(*F);
01701   }
01702 
01703   return MadeChange;
01704 }
01705 
01706 bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) {
01707   AA = &getAnalysis<AliasAnalysis>();
01708   TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
01709 
01710   bool Changed = annotateLibraryCalls(SCC);
01711   Changed |= AddReadAttrs(SCC);
01712   Changed |= AddArgumentAttrs(SCC);
01713   Changed |= AddNoAliasAttrs(SCC);
01714   return Changed;
01715 }