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