LLVM API Documentation

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/Target/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<TargetLibraryInfo>();
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(TargetLibraryInfo)
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)
00165       // External node - may write memory.  Just give up.
00166       return false;
00167 
00168     AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(F);
00169     if (MRB == AliasAnalysis::DoesNotAccessMemory)
00170       // Already perfect!
00171       continue;
00172 
00173     // Definitions with weak linkage may be overridden at linktime with
00174     // something that writes memory, so treat them like declarations.
00175     if (F->isDeclaration() || F->mayBeOverridden()) {
00176       if (!AliasAnalysis::onlyReadsMemory(MRB))
00177         // May write memory.  Just give up.
00178         return false;
00179 
00180       ReadsMemory = true;
00181       continue;
00182     }
00183 
00184     // Scan the function body for instructions that may read or write memory.
00185     for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
00186       Instruction *I = &*II;
00187 
00188       // Some instructions can be ignored even if they read or write memory.
00189       // Detect these now, skipping to the next instruction if one is found.
00190       CallSite CS(cast<Value>(I));
00191       if (CS) {
00192         // Ignore calls to functions in the same SCC.
00193         if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
00194           continue;
00195         AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(CS);
00196         // If the call doesn't access arbitrary memory, we may be able to
00197         // figure out something.
00198         if (AliasAnalysis::onlyAccessesArgPointees(MRB)) {
00199           // If the call does access argument pointees, check each argument.
00200           if (AliasAnalysis::doesAccessArgPointees(MRB))
00201             // Check whether all pointer arguments point to local memory, and
00202             // ignore calls that only access local memory.
00203             for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
00204                  CI != CE; ++CI) {
00205               Value *Arg = *CI;
00206               if (Arg->getType()->isPointerTy()) {
00207                 AAMDNodes AAInfo;
00208                 I->getAAMetadata(AAInfo);
00209 
00210                 AliasAnalysis::Location Loc(Arg,
00211                                             AliasAnalysis::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           AliasAnalysis::Location Loc = AA->getLocation(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           AliasAnalysis::Location Loc = AA->getLocation(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         AliasAnalysis::Location Loc = AA->getLocation(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))
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))
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       SCCNodes.insert(F);
00532   }
00533 
00534   ArgumentGraph AG;
00535 
00536   AttrBuilder B;
00537   B.addAttribute(Attribute::NoCapture);
00538 
00539   // Check each function in turn, determining which pointer arguments are not
00540   // captured.
00541   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
00542     Function *F = (*I)->getFunction();
00543 
00544     if (!F)
00545       // External node - only a problem for arguments that we pass to it.
00546       continue;
00547 
00548     // Definitions with weak linkage may be overridden at linktime with
00549     // something that captures pointers, so treat them like declarations.
00550     if (F->isDeclaration() || F->mayBeOverridden())
00551       continue;
00552 
00553     // Functions that are readonly (or readnone) and nounwind and don't return
00554     // a value can't capture arguments. Don't analyze them.
00555     if (F->onlyReadsMemory() && F->doesNotThrow() &&
00556         F->getReturnType()->isVoidTy()) {
00557       for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end();
00558            A != E; ++A) {
00559         if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
00560           A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
00561           ++NumNoCapture;
00562           Changed = true;
00563         }
00564       }
00565       continue;
00566     }
00567 
00568     for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end();
00569          A != E; ++A) {
00570       if (!A->getType()->isPointerTy()) continue;
00571       bool HasNonLocalUses = false;
00572       if (!A->hasNoCaptureAttr()) {
00573         ArgumentUsesTracker Tracker(SCCNodes);
00574         PointerMayBeCaptured(A, &Tracker);
00575         if (!Tracker.Captured) {
00576           if (Tracker.Uses.empty()) {
00577             // If it's trivially not captured, mark it nocapture now.
00578             A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo()+1, B));
00579             ++NumNoCapture;
00580             Changed = true;
00581           } else {
00582             // If it's not trivially captured and not trivially not captured,
00583             // then it must be calling into another function in our SCC. Save
00584             // its particulars for Argument-SCC analysis later.
00585             ArgumentGraphNode *Node = AG[A];
00586             for (SmallVectorImpl<Argument*>::iterator UI = Tracker.Uses.begin(),
00587                      UE = Tracker.Uses.end(); UI != UE; ++UI) {
00588               Node->Uses.push_back(AG[*UI]);
00589               if (*UI != A)
00590                 HasNonLocalUses = true;
00591             }
00592           }
00593         }
00594         // Otherwise, it's captured. Don't bother doing SCC analysis on it.
00595       }
00596       if (!HasNonLocalUses && !A->onlyReadsMemory()) {
00597         // Can we determine that it's readonly/readnone without doing an SCC?
00598         // Note that we don't allow any calls at all here, or else our result
00599         // will be dependent on the iteration order through the functions in the
00600         // SCC.
00601         SmallPtrSet<Argument*, 8> Self;
00602         Self.insert(A);
00603         Attribute::AttrKind R = determinePointerReadAttrs(A, Self);
00604         if (R != Attribute::None) {
00605           AttrBuilder B;
00606           B.addAttribute(R);
00607           A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
00608           Changed = true;
00609           R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
00610         }
00611       }
00612     }
00613   }
00614 
00615   // The graph we've collected is partial because we stopped scanning for
00616   // argument uses once we solved the argument trivially. These partial nodes
00617   // show up as ArgumentGraphNode objects with an empty Uses list, and for
00618   // these nodes the final decision about whether they capture has already been
00619   // made.  If the definition doesn't have a 'nocapture' attribute by now, it
00620   // captures.
00621 
00622   for (scc_iterator<ArgumentGraph*> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
00623     const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
00624     if (ArgumentSCC.size() == 1) {
00625       if (!ArgumentSCC[0]->Definition) continue;  // synthetic root node
00626 
00627       // eg. "void f(int* x) { if (...) f(x); }"
00628       if (ArgumentSCC[0]->Uses.size() == 1 &&
00629           ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
00630         Argument *A = ArgumentSCC[0]->Definition;
00631         A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
00632         ++NumNoCapture;
00633         Changed = true;
00634       }
00635       continue;
00636     }
00637 
00638     bool SCCCaptured = false;
00639     for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
00640          I != E && !SCCCaptured; ++I) {
00641       ArgumentGraphNode *Node = *I;
00642       if (Node->Uses.empty()) {
00643         if (!Node->Definition->hasNoCaptureAttr())
00644           SCCCaptured = true;
00645       }
00646     }
00647     if (SCCCaptured) continue;
00648 
00649     SmallPtrSet<Argument*, 8> ArgumentSCCNodes;
00650     // Fill ArgumentSCCNodes with the elements of the ArgumentSCC.  Used for
00651     // quickly looking up whether a given Argument is in this ArgumentSCC.
00652     for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end(); I != E; ++I) {
00653       ArgumentSCCNodes.insert((*I)->Definition);
00654     }
00655 
00656     for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
00657          I != E && !SCCCaptured; ++I) {
00658       ArgumentGraphNode *N = *I;
00659       for (SmallVectorImpl<ArgumentGraphNode*>::iterator UI = N->Uses.begin(),
00660              UE = N->Uses.end(); UI != UE; ++UI) {
00661         Argument *A = (*UI)->Definition;
00662         if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
00663           continue;
00664         SCCCaptured = true;
00665         break;
00666       }
00667     }
00668     if (SCCCaptured) continue;
00669 
00670     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
00671       Argument *A = ArgumentSCC[i]->Definition;
00672       A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
00673       ++NumNoCapture;
00674       Changed = true;
00675     }
00676 
00677     // We also want to compute readonly/readnone. With a small number of false
00678     // negatives, we can assume that any pointer which is captured isn't going
00679     // to be provably readonly or readnone, since by definition we can't
00680     // analyze all uses of a captured pointer.
00681     //
00682     // The false negatives happen when the pointer is captured by a function
00683     // that promises readonly/readnone behaviour on the pointer, then the
00684     // pointer's lifetime ends before anything that writes to arbitrary memory.
00685     // Also, a readonly/readnone pointer may be returned, but returning a
00686     // pointer is capturing it.
00687 
00688     Attribute::AttrKind ReadAttr = Attribute::ReadNone;
00689     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
00690       Argument *A = ArgumentSCC[i]->Definition;
00691       Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes);
00692       if (K == Attribute::ReadNone)
00693         continue;
00694       if (K == Attribute::ReadOnly) {
00695         ReadAttr = Attribute::ReadOnly;
00696         continue;
00697       }
00698       ReadAttr = K;
00699       break;
00700     }
00701 
00702     if (ReadAttr != Attribute::None) {
00703       AttrBuilder B;
00704       B.addAttribute(ReadAttr);
00705       for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
00706         Argument *A = ArgumentSCC[i]->Definition;
00707         A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
00708         ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
00709         Changed = true;
00710       }
00711     }
00712   }
00713 
00714   return Changed;
00715 }
00716 
00717 /// IsFunctionMallocLike - A function is malloc-like if it returns either null
00718 /// or a pointer that doesn't alias any other pointer visible to the caller.
00719 bool FunctionAttrs::IsFunctionMallocLike(Function *F,
00720                               SmallPtrSet<Function*, 8> &SCCNodes) const {
00721   SmallSetVector<Value *, 8> FlowsToReturn;
00722   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
00723     if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator()))
00724       FlowsToReturn.insert(Ret->getReturnValue());
00725 
00726   for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
00727     Value *RetVal = FlowsToReturn[i];
00728 
00729     if (Constant *C = dyn_cast<Constant>(RetVal)) {
00730       if (!C->isNullValue() && !isa<UndefValue>(C))
00731         return false;
00732 
00733       continue;
00734     }
00735 
00736     if (isa<Argument>(RetVal))
00737       return false;
00738 
00739     if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
00740       switch (RVI->getOpcode()) {
00741         // Extend the analysis by looking upwards.
00742         case Instruction::BitCast:
00743         case Instruction::GetElementPtr:
00744         case Instruction::AddrSpaceCast:
00745           FlowsToReturn.insert(RVI->getOperand(0));
00746           continue;
00747         case Instruction::Select: {
00748           SelectInst *SI = cast<SelectInst>(RVI);
00749           FlowsToReturn.insert(SI->getTrueValue());
00750           FlowsToReturn.insert(SI->getFalseValue());
00751           continue;
00752         }
00753         case Instruction::PHI: {
00754           PHINode *PN = cast<PHINode>(RVI);
00755           for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
00756             FlowsToReturn.insert(PN->getIncomingValue(i));
00757           continue;
00758         }
00759 
00760         // Check whether the pointer came from an allocation.
00761         case Instruction::Alloca:
00762           break;
00763         case Instruction::Call:
00764         case Instruction::Invoke: {
00765           CallSite CS(RVI);
00766           if (CS.paramHasAttr(0, Attribute::NoAlias))
00767             break;
00768           if (CS.getCalledFunction() &&
00769               SCCNodes.count(CS.getCalledFunction()))
00770             break;
00771         } // fall-through
00772         default:
00773           return false;  // Did not come from an allocation.
00774       }
00775 
00776     if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
00777       return false;
00778   }
00779 
00780   return true;
00781 }
00782 
00783 /// AddNoAliasAttrs - Deduce noalias attributes for the SCC.
00784 bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) {
00785   SmallPtrSet<Function*, 8> SCCNodes;
00786 
00787   // Fill SCCNodes with the elements of the SCC.  Used for quickly
00788   // looking up whether a given CallGraphNode is in this SCC.
00789   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
00790     SCCNodes.insert((*I)->getFunction());
00791 
00792   // Check each function in turn, determining which functions return noalias
00793   // pointers.
00794   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
00795     Function *F = (*I)->getFunction();
00796 
00797     if (!F)
00798       // External node - skip it;
00799       return false;
00800 
00801     // Already noalias.
00802     if (F->doesNotAlias(0))
00803       continue;
00804 
00805     // Definitions with weak linkage may be overridden at linktime, so
00806     // treat them like declarations.
00807     if (F->isDeclaration() || F->mayBeOverridden())
00808       return false;
00809 
00810     // We annotate noalias return values, which are only applicable to 
00811     // pointer types.
00812     if (!F->getReturnType()->isPointerTy())
00813       continue;
00814 
00815     if (!IsFunctionMallocLike(F, SCCNodes))
00816       return false;
00817   }
00818 
00819   bool MadeChange = false;
00820   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
00821     Function *F = (*I)->getFunction();
00822     if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy())
00823       continue;
00824 
00825     F->setDoesNotAlias(0);
00826     ++NumNoAlias;
00827     MadeChange = true;
00828   }
00829 
00830   return MadeChange;
00831 }
00832 
00833 /// inferPrototypeAttributes - Analyze the name and prototype of the
00834 /// given function and set any applicable attributes.  Returns true
00835 /// if any attributes were set and false otherwise.
00836 bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
00837   FunctionType *FTy = F.getFunctionType();
00838   LibFunc::Func TheLibFunc;
00839   if (!(TLI->getLibFunc(F.getName(), TheLibFunc) && TLI->has(TheLibFunc)))
00840     return false;
00841 
00842   switch (TheLibFunc) {
00843   case LibFunc::strlen:
00844     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
00845       return false;
00846     setOnlyReadsMemory(F);
00847     setDoesNotThrow(F);
00848     setDoesNotCapture(F, 1);
00849     break;
00850   case LibFunc::strchr:
00851   case LibFunc::strrchr:
00852     if (FTy->getNumParams() != 2 ||
00853         !FTy->getParamType(0)->isPointerTy() ||
00854         !FTy->getParamType(1)->isIntegerTy())
00855       return false;
00856     setOnlyReadsMemory(F);
00857     setDoesNotThrow(F);
00858     break;
00859   case LibFunc::strtol:
00860   case LibFunc::strtod:
00861   case LibFunc::strtof:
00862   case LibFunc::strtoul:
00863   case LibFunc::strtoll:
00864   case LibFunc::strtold:
00865   case LibFunc::strtoull:
00866     if (FTy->getNumParams() < 2 ||
00867         !FTy->getParamType(1)->isPointerTy())
00868       return false;
00869     setDoesNotThrow(F);
00870     setDoesNotCapture(F, 2);
00871     setOnlyReadsMemory(F, 1);
00872     break;
00873   case LibFunc::strcpy:
00874   case LibFunc::stpcpy:
00875   case LibFunc::strcat:
00876   case LibFunc::strncat:
00877   case LibFunc::strncpy:
00878   case LibFunc::stpncpy:
00879     if (FTy->getNumParams() < 2 ||
00880         !FTy->getParamType(1)->isPointerTy())
00881       return false;
00882     setDoesNotThrow(F);
00883     setDoesNotCapture(F, 2);
00884     setOnlyReadsMemory(F, 2);
00885     break;
00886   case LibFunc::strxfrm:
00887     if (FTy->getNumParams() != 3 ||
00888         !FTy->getParamType(0)->isPointerTy() ||
00889         !FTy->getParamType(1)->isPointerTy())
00890       return false;
00891     setDoesNotThrow(F);
00892     setDoesNotCapture(F, 1);
00893     setDoesNotCapture(F, 2);
00894     setOnlyReadsMemory(F, 2);
00895     break;
00896   case LibFunc::strcmp: //0,1
00897     case LibFunc::strspn: // 0,1
00898     case LibFunc::strncmp: // 0,1
00899     case LibFunc::strcspn: //0,1
00900     case LibFunc::strcoll: //0,1
00901     case LibFunc::strcasecmp:  // 0,1
00902     case LibFunc::strncasecmp: // 
00903     if (FTy->getNumParams() < 2 ||
00904         !FTy->getParamType(0)->isPointerTy() ||
00905         !FTy->getParamType(1)->isPointerTy())
00906       return false;
00907     setOnlyReadsMemory(F);
00908     setDoesNotThrow(F);
00909     setDoesNotCapture(F, 1);
00910     setDoesNotCapture(F, 2);
00911     break;
00912   case LibFunc::strstr:
00913   case LibFunc::strpbrk:
00914     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
00915       return false;
00916     setOnlyReadsMemory(F);
00917     setDoesNotThrow(F);
00918     setDoesNotCapture(F, 2);
00919     break;
00920   case LibFunc::strtok:
00921   case LibFunc::strtok_r:
00922     if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
00923       return false;
00924     setDoesNotThrow(F);
00925     setDoesNotCapture(F, 2);
00926     setOnlyReadsMemory(F, 2);
00927     break;
00928   case LibFunc::scanf:
00929     if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
00930       return false;
00931     setDoesNotThrow(F);
00932     setDoesNotCapture(F, 1);
00933     setOnlyReadsMemory(F, 1);
00934     break;
00935   case LibFunc::setbuf:
00936   case LibFunc::setvbuf:
00937     if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
00938       return false;
00939     setDoesNotThrow(F);
00940     setDoesNotCapture(F, 1);
00941     break;
00942   case LibFunc::strdup:
00943   case LibFunc::strndup:
00944     if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() ||
00945         !FTy->getParamType(0)->isPointerTy())
00946       return false;
00947     setDoesNotThrow(F);
00948     setDoesNotAlias(F, 0);
00949     setDoesNotCapture(F, 1);
00950     setOnlyReadsMemory(F, 1);
00951     break;
00952   case LibFunc::stat:
00953   case LibFunc::statvfs:
00954     if (FTy->getNumParams() < 2 ||
00955         !FTy->getParamType(0)->isPointerTy() ||
00956         !FTy->getParamType(1)->isPointerTy())
00957       return false;
00958     setDoesNotThrow(F);
00959     setDoesNotCapture(F, 1);
00960     setDoesNotCapture(F, 2);
00961     setOnlyReadsMemory(F, 1);
00962     break;
00963   case LibFunc::sscanf:
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     setOnlyReadsMemory(F, 2);
00973     break;
00974   case LibFunc::sprintf:
00975     if (FTy->getNumParams() < 2 ||
00976         !FTy->getParamType(0)->isPointerTy() ||
00977         !FTy->getParamType(1)->isPointerTy())
00978       return false;
00979     setDoesNotThrow(F);
00980     setDoesNotCapture(F, 1);
00981     setDoesNotCapture(F, 2);
00982     setOnlyReadsMemory(F, 2);
00983     break;
00984   case LibFunc::snprintf:
00985     if (FTy->getNumParams() != 3 ||
00986         !FTy->getParamType(0)->isPointerTy() ||
00987         !FTy->getParamType(2)->isPointerTy())
00988       return false;
00989     setDoesNotThrow(F);
00990     setDoesNotCapture(F, 1);
00991     setDoesNotCapture(F, 3);
00992     setOnlyReadsMemory(F, 3);
00993     break;
00994   case LibFunc::setitimer:
00995     if (FTy->getNumParams() != 3 ||
00996         !FTy->getParamType(1)->isPointerTy() ||
00997         !FTy->getParamType(2)->isPointerTy())
00998       return false;
00999     setDoesNotThrow(F);
01000     setDoesNotCapture(F, 2);
01001     setDoesNotCapture(F, 3);
01002     setOnlyReadsMemory(F, 2);
01003     break;
01004   case LibFunc::system:
01005     if (FTy->getNumParams() != 1 ||
01006         !FTy->getParamType(0)->isPointerTy())
01007       return false;
01008     // May throw; "system" is a valid pthread cancellation point.
01009     setDoesNotCapture(F, 1);
01010     setOnlyReadsMemory(F, 1);
01011     break;
01012   case LibFunc::malloc:
01013     if (FTy->getNumParams() != 1 ||
01014         !FTy->getReturnType()->isPointerTy())
01015       return false;
01016     setDoesNotThrow(F);
01017     setDoesNotAlias(F, 0);
01018     break;
01019   case LibFunc::memcmp:
01020     if (FTy->getNumParams() != 3 ||
01021         !FTy->getParamType(0)->isPointerTy() ||
01022         !FTy->getParamType(1)->isPointerTy())
01023       return false;
01024     setOnlyReadsMemory(F);
01025     setDoesNotThrow(F);
01026     setDoesNotCapture(F, 1);
01027     setDoesNotCapture(F, 2);
01028     break;
01029   case LibFunc::memchr:
01030   case LibFunc::memrchr:
01031     if (FTy->getNumParams() != 3)
01032       return false;
01033     setOnlyReadsMemory(F);
01034     setDoesNotThrow(F);
01035     break;
01036   case LibFunc::modf:
01037   case LibFunc::modff:
01038   case LibFunc::modfl:
01039     if (FTy->getNumParams() < 2 ||
01040         !FTy->getParamType(1)->isPointerTy())
01041       return false;
01042     setDoesNotThrow(F);
01043     setDoesNotCapture(F, 2);
01044     break;
01045   case LibFunc::memcpy:
01046   case LibFunc::memccpy:
01047   case LibFunc::memmove:
01048     if (FTy->getNumParams() < 2 ||
01049         !FTy->getParamType(1)->isPointerTy())
01050       return false;
01051     setDoesNotThrow(F);
01052     setDoesNotCapture(F, 2);
01053     setOnlyReadsMemory(F, 2);
01054     break;
01055   case LibFunc::memalign:
01056     if (!FTy->getReturnType()->isPointerTy())
01057       return false;
01058     setDoesNotAlias(F, 0);
01059     break;
01060   case LibFunc::mkdir:
01061     if (FTy->getNumParams() == 0 ||
01062         !FTy->getParamType(0)->isPointerTy())
01063       return false;
01064     setDoesNotThrow(F);
01065     setDoesNotCapture(F, 1);
01066     setOnlyReadsMemory(F, 1);
01067     break;
01068   case LibFunc::mktime:
01069     if (FTy->getNumParams() == 0 ||
01070         !FTy->getParamType(0)->isPointerTy())
01071       return false;
01072     setDoesNotThrow(F);
01073     setDoesNotCapture(F, 1);
01074     break;
01075   case LibFunc::realloc:
01076     if (FTy->getNumParams() != 2 ||
01077         !FTy->getParamType(0)->isPointerTy() ||
01078         !FTy->getReturnType()->isPointerTy())
01079       return false;
01080     setDoesNotThrow(F);
01081     setDoesNotAlias(F, 0);
01082     setDoesNotCapture(F, 1);
01083     break;
01084   case LibFunc::read:
01085     if (FTy->getNumParams() != 3 ||
01086         !FTy->getParamType(1)->isPointerTy())
01087       return false;
01088     // May throw; "read" is a valid pthread cancellation point.
01089     setDoesNotCapture(F, 2);
01090     break;
01091   case LibFunc::rewind:
01092     if (FTy->getNumParams() < 1 ||
01093         !FTy->getParamType(0)->isPointerTy())
01094       return false;
01095     setDoesNotThrow(F);
01096     setDoesNotCapture(F, 1);
01097     break;
01098   case LibFunc::rmdir:
01099   case LibFunc::remove:
01100   case LibFunc::realpath:
01101     if (FTy->getNumParams() < 1 ||
01102         !FTy->getParamType(0)->isPointerTy())
01103       return false;
01104     setDoesNotThrow(F);
01105     setDoesNotCapture(F, 1);
01106     setOnlyReadsMemory(F, 1);
01107     break;
01108   case LibFunc::rename:
01109     if (FTy->getNumParams() < 2 ||
01110         !FTy->getParamType(0)->isPointerTy() ||
01111         !FTy->getParamType(1)->isPointerTy())
01112       return false;
01113     setDoesNotThrow(F);
01114     setDoesNotCapture(F, 1);
01115     setDoesNotCapture(F, 2);
01116     setOnlyReadsMemory(F, 1);
01117     setOnlyReadsMemory(F, 2);
01118     break;
01119   case LibFunc::readlink:
01120     if (FTy->getNumParams() < 2 ||
01121         !FTy->getParamType(0)->isPointerTy() ||
01122         !FTy->getParamType(1)->isPointerTy())
01123       return false;
01124     setDoesNotThrow(F);
01125     setDoesNotCapture(F, 1);
01126     setDoesNotCapture(F, 2);
01127     setOnlyReadsMemory(F, 1);
01128     break;
01129   case LibFunc::write:
01130     if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
01131       return false;
01132     // May throw; "write" is a valid pthread cancellation point.
01133     setDoesNotCapture(F, 2);
01134     setOnlyReadsMemory(F, 2);
01135     break;
01136   case LibFunc::bcopy:
01137     if (FTy->getNumParams() != 3 ||
01138         !FTy->getParamType(0)->isPointerTy() ||
01139         !FTy->getParamType(1)->isPointerTy())
01140       return false;
01141     setDoesNotThrow(F);
01142     setDoesNotCapture(F, 1);
01143     setDoesNotCapture(F, 2);
01144     setOnlyReadsMemory(F, 1);
01145     break;
01146   case LibFunc::bcmp:
01147     if (FTy->getNumParams() != 3 ||
01148         !FTy->getParamType(0)->isPointerTy() ||
01149         !FTy->getParamType(1)->isPointerTy())
01150       return false;
01151     setDoesNotThrow(F);
01152     setOnlyReadsMemory(F);
01153     setDoesNotCapture(F, 1);
01154     setDoesNotCapture(F, 2);
01155     break;
01156   case LibFunc::bzero:
01157     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
01158       return false;
01159     setDoesNotThrow(F);
01160     setDoesNotCapture(F, 1);
01161     break;
01162   case LibFunc::calloc:
01163     if (FTy->getNumParams() != 2 ||
01164         !FTy->getReturnType()->isPointerTy())
01165       return false;
01166     setDoesNotThrow(F);
01167     setDoesNotAlias(F, 0);
01168     break;
01169   case LibFunc::chmod:
01170   case LibFunc::chown:
01171     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
01172       return false;
01173     setDoesNotThrow(F);
01174     setDoesNotCapture(F, 1);
01175     setOnlyReadsMemory(F, 1);
01176     break;
01177   case LibFunc::ctermid:
01178   case LibFunc::clearerr:
01179   case LibFunc::closedir:
01180     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
01181       return false;
01182     setDoesNotThrow(F);
01183     setDoesNotCapture(F, 1);
01184     break;
01185   case LibFunc::atoi:
01186   case LibFunc::atol:
01187   case LibFunc::atof:
01188   case LibFunc::atoll:
01189     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01190       return false;
01191     setDoesNotThrow(F);
01192     setOnlyReadsMemory(F);
01193     setDoesNotCapture(F, 1);
01194     break;
01195   case LibFunc::access:
01196     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
01197       return false;
01198     setDoesNotThrow(F);
01199     setDoesNotCapture(F, 1);
01200     setOnlyReadsMemory(F, 1);
01201     break;
01202   case LibFunc::fopen:
01203     if (FTy->getNumParams() != 2 ||
01204         !FTy->getReturnType()->isPointerTy() ||
01205         !FTy->getParamType(0)->isPointerTy() ||
01206         !FTy->getParamType(1)->isPointerTy())
01207       return false;
01208     setDoesNotThrow(F);
01209     setDoesNotAlias(F, 0);
01210     setDoesNotCapture(F, 1);
01211     setDoesNotCapture(F, 2);
01212     setOnlyReadsMemory(F, 1);
01213     setOnlyReadsMemory(F, 2);
01214     break;
01215   case LibFunc::fdopen:
01216     if (FTy->getNumParams() != 2 ||
01217         !FTy->getReturnType()->isPointerTy() ||
01218         !FTy->getParamType(1)->isPointerTy())
01219       return false;
01220     setDoesNotThrow(F);
01221     setDoesNotAlias(F, 0);
01222     setDoesNotCapture(F, 2);
01223     setOnlyReadsMemory(F, 2);
01224     break;
01225   case LibFunc::feof:
01226   case LibFunc::free:
01227   case LibFunc::fseek:
01228   case LibFunc::ftell:
01229   case LibFunc::fgetc:
01230   case LibFunc::fseeko:
01231   case LibFunc::ftello:
01232   case LibFunc::fileno:
01233   case LibFunc::fflush:
01234   case LibFunc::fclose:
01235   case LibFunc::fsetpos:
01236   case LibFunc::flockfile:
01237   case LibFunc::funlockfile:
01238   case LibFunc::ftrylockfile:
01239     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
01240       return false;
01241     setDoesNotThrow(F);
01242     setDoesNotCapture(F, 1);
01243     break;
01244   case LibFunc::ferror:
01245     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01246       return false;
01247     setDoesNotThrow(F);
01248     setDoesNotCapture(F, 1);
01249     setOnlyReadsMemory(F);
01250     break;
01251   case LibFunc::fputc:
01252   case LibFunc::fstat:
01253   case LibFunc::frexp:
01254   case LibFunc::frexpf:
01255   case LibFunc::frexpl:
01256   case LibFunc::fstatvfs:
01257     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
01258       return false;
01259     setDoesNotThrow(F);
01260     setDoesNotCapture(F, 2);
01261     break;
01262   case LibFunc::fgets:
01263     if (FTy->getNumParams() != 3 ||
01264         !FTy->getParamType(0)->isPointerTy() ||
01265         !FTy->getParamType(2)->isPointerTy())
01266       return false;
01267     setDoesNotThrow(F);
01268     setDoesNotCapture(F, 3);
01269     break;
01270   case LibFunc::fread:
01271     if (FTy->getNumParams() != 4 ||
01272         !FTy->getParamType(0)->isPointerTy() ||
01273         !FTy->getParamType(3)->isPointerTy())
01274       return false;
01275     setDoesNotThrow(F);
01276     setDoesNotCapture(F, 1);
01277     setDoesNotCapture(F, 4);
01278     break;
01279   case LibFunc::fwrite:
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::fputs:
01289     if (FTy->getNumParams() < 2 ||
01290         !FTy->getParamType(0)->isPointerTy() ||
01291         !FTy->getParamType(1)->isPointerTy())
01292       return false;
01293     setDoesNotThrow(F);
01294     setDoesNotCapture(F, 1);
01295     setDoesNotCapture(F, 2);
01296     setOnlyReadsMemory(F, 1);
01297     break;
01298   case LibFunc::fscanf:
01299   case LibFunc::fprintf:
01300     if (FTy->getNumParams() < 2 ||
01301         !FTy->getParamType(0)->isPointerTy() ||
01302         !FTy->getParamType(1)->isPointerTy())
01303       return false;
01304     setDoesNotThrow(F);
01305     setDoesNotCapture(F, 1);
01306     setDoesNotCapture(F, 2);
01307     setOnlyReadsMemory(F, 2);
01308     break;
01309   case LibFunc::fgetpos:
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     break;
01318   case LibFunc::getc:
01319   case LibFunc::getlogin_r:
01320   case LibFunc::getc_unlocked:
01321     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
01322       return false;
01323     setDoesNotThrow(F);
01324     setDoesNotCapture(F, 1);
01325     break;
01326   case LibFunc::getenv:
01327     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01328       return false;
01329     setDoesNotThrow(F);
01330     setOnlyReadsMemory(F);
01331     setDoesNotCapture(F, 1);
01332     break;
01333   case LibFunc::gets:
01334   case LibFunc::getchar:
01335     setDoesNotThrow(F);
01336     break;
01337   case LibFunc::getitimer:
01338     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
01339       return false;
01340     setDoesNotThrow(F);
01341     setDoesNotCapture(F, 2);
01342     break;
01343   case LibFunc::getpwnam:
01344     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01345       return false;
01346     setDoesNotThrow(F);
01347     setDoesNotCapture(F, 1);
01348     setOnlyReadsMemory(F, 1);
01349     break;
01350   case LibFunc::ungetc:
01351     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
01352       return false;
01353     setDoesNotThrow(F);
01354     setDoesNotCapture(F, 2);
01355     break;
01356   case LibFunc::uname:
01357     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01358       return false;
01359     setDoesNotThrow(F);
01360     setDoesNotCapture(F, 1);
01361     break;
01362   case LibFunc::unlink:
01363     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01364       return false;
01365     setDoesNotThrow(F);
01366     setDoesNotCapture(F, 1);
01367     setOnlyReadsMemory(F, 1);
01368     break;
01369   case LibFunc::unsetenv:
01370     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01371       return false;
01372     setDoesNotThrow(F);
01373     setDoesNotCapture(F, 1);
01374     setOnlyReadsMemory(F, 1);
01375     break;
01376   case LibFunc::utime:
01377   case LibFunc::utimes:
01378     if (FTy->getNumParams() != 2 ||
01379         !FTy->getParamType(0)->isPointerTy() ||
01380         !FTy->getParamType(1)->isPointerTy())
01381       return false;
01382     setDoesNotThrow(F);
01383     setDoesNotCapture(F, 1);
01384     setDoesNotCapture(F, 2);
01385     setOnlyReadsMemory(F, 1);
01386     setOnlyReadsMemory(F, 2);
01387     break;
01388   case LibFunc::putc:
01389     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
01390       return false;
01391     setDoesNotThrow(F);
01392     setDoesNotCapture(F, 2);
01393     break;
01394   case LibFunc::puts:
01395   case LibFunc::printf:
01396   case LibFunc::perror:
01397     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01398       return false;
01399     setDoesNotThrow(F);
01400     setDoesNotCapture(F, 1);
01401     setOnlyReadsMemory(F, 1);
01402     break;
01403   case LibFunc::pread:
01404     if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
01405       return false;
01406     // May throw; "pread" is a valid pthread cancellation point.
01407     setDoesNotCapture(F, 2);
01408     break;
01409   case LibFunc::pwrite:
01410     if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
01411       return false;
01412     // May throw; "pwrite" is a valid pthread cancellation point.
01413     setDoesNotCapture(F, 2);
01414     setOnlyReadsMemory(F, 2);
01415     break;
01416   case LibFunc::putchar:
01417     setDoesNotThrow(F);
01418     break;
01419   case LibFunc::popen:
01420     if (FTy->getNumParams() != 2 ||
01421         !FTy->getReturnType()->isPointerTy() ||
01422         !FTy->getParamType(0)->isPointerTy() ||
01423         !FTy->getParamType(1)->isPointerTy())
01424       return false;
01425     setDoesNotThrow(F);
01426     setDoesNotAlias(F, 0);
01427     setDoesNotCapture(F, 1);
01428     setDoesNotCapture(F, 2);
01429     setOnlyReadsMemory(F, 1);
01430     setOnlyReadsMemory(F, 2);
01431     break;
01432   case LibFunc::pclose:
01433     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01434       return false;
01435     setDoesNotThrow(F);
01436     setDoesNotCapture(F, 1);
01437     break;
01438   case LibFunc::vscanf:
01439     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
01440       return false;
01441     setDoesNotThrow(F);
01442     setDoesNotCapture(F, 1);
01443     setOnlyReadsMemory(F, 1);
01444     break;
01445   case LibFunc::vsscanf:
01446     if (FTy->getNumParams() != 3 ||
01447         !FTy->getParamType(1)->isPointerTy() ||
01448         !FTy->getParamType(2)->isPointerTy())
01449       return false;
01450     setDoesNotThrow(F);
01451     setDoesNotCapture(F, 1);
01452     setDoesNotCapture(F, 2);
01453     setOnlyReadsMemory(F, 1);
01454     setOnlyReadsMemory(F, 2);
01455     break;
01456   case LibFunc::vfscanf:
01457     if (FTy->getNumParams() != 3 ||
01458         !FTy->getParamType(1)->isPointerTy() ||
01459         !FTy->getParamType(2)->isPointerTy())
01460       return false;
01461     setDoesNotThrow(F);
01462     setDoesNotCapture(F, 1);
01463     setDoesNotCapture(F, 2);
01464     setOnlyReadsMemory(F, 2);
01465     break;
01466   case LibFunc::valloc:
01467     if (!FTy->getReturnType()->isPointerTy())
01468       return false;
01469     setDoesNotThrow(F);
01470     setDoesNotAlias(F, 0);
01471     break;
01472   case LibFunc::vprintf:
01473     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
01474       return false;
01475     setDoesNotThrow(F);
01476     setDoesNotCapture(F, 1);
01477     setOnlyReadsMemory(F, 1);
01478     break;
01479   case LibFunc::vfprintf:
01480   case LibFunc::vsprintf:
01481     if (FTy->getNumParams() != 3 ||
01482         !FTy->getParamType(0)->isPointerTy() ||
01483         !FTy->getParamType(1)->isPointerTy())
01484       return false;
01485     setDoesNotThrow(F);
01486     setDoesNotCapture(F, 1);
01487     setDoesNotCapture(F, 2);
01488     setOnlyReadsMemory(F, 2);
01489     break;
01490   case LibFunc::vsnprintf:
01491     if (FTy->getNumParams() != 4 ||
01492         !FTy->getParamType(0)->isPointerTy() ||
01493         !FTy->getParamType(2)->isPointerTy())
01494       return false;
01495     setDoesNotThrow(F);
01496     setDoesNotCapture(F, 1);
01497     setDoesNotCapture(F, 3);
01498     setOnlyReadsMemory(F, 3);
01499     break;
01500   case LibFunc::open:
01501     if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
01502       return false;
01503     // May throw; "open" is a valid pthread cancellation point.
01504     setDoesNotCapture(F, 1);
01505     setOnlyReadsMemory(F, 1);
01506     break;
01507   case LibFunc::opendir:
01508     if (FTy->getNumParams() != 1 ||
01509         !FTy->getReturnType()->isPointerTy() ||
01510         !FTy->getParamType(0)->isPointerTy())
01511       return false;
01512     setDoesNotThrow(F);
01513     setDoesNotAlias(F, 0);
01514     setDoesNotCapture(F, 1);
01515     setOnlyReadsMemory(F, 1);
01516     break;
01517   case LibFunc::tmpfile:
01518     if (!FTy->getReturnType()->isPointerTy())
01519       return false;
01520     setDoesNotThrow(F);
01521     setDoesNotAlias(F, 0);
01522     break;
01523   case LibFunc::times:
01524     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01525       return false;
01526     setDoesNotThrow(F);
01527     setDoesNotCapture(F, 1);
01528     break;
01529   case LibFunc::htonl:
01530   case LibFunc::htons:
01531   case LibFunc::ntohl:
01532   case LibFunc::ntohs:
01533     setDoesNotThrow(F);
01534     setDoesNotAccessMemory(F);
01535     break;
01536   case LibFunc::lstat:
01537     if (FTy->getNumParams() != 2 ||
01538         !FTy->getParamType(0)->isPointerTy() ||
01539         !FTy->getParamType(1)->isPointerTy())
01540       return false;
01541     setDoesNotThrow(F);
01542     setDoesNotCapture(F, 1);
01543     setDoesNotCapture(F, 2);
01544     setOnlyReadsMemory(F, 1);
01545     break;
01546   case LibFunc::lchown:
01547     if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy())
01548       return false;
01549     setDoesNotThrow(F);
01550     setDoesNotCapture(F, 1);
01551     setOnlyReadsMemory(F, 1);
01552     break;
01553   case LibFunc::qsort:
01554     if (FTy->getNumParams() != 4 || !FTy->getParamType(3)->isPointerTy())
01555       return false;
01556     // May throw; places call through function pointer.
01557     setDoesNotCapture(F, 4);
01558     break;
01559   case LibFunc::dunder_strdup:
01560   case LibFunc::dunder_strndup:
01561     if (FTy->getNumParams() < 1 ||
01562         !FTy->getReturnType()->isPointerTy() ||
01563         !FTy->getParamType(0)->isPointerTy())
01564       return false;
01565     setDoesNotThrow(F);
01566     setDoesNotAlias(F, 0);
01567     setDoesNotCapture(F, 1);
01568     setOnlyReadsMemory(F, 1);
01569     break;
01570   case LibFunc::dunder_strtok_r:
01571     if (FTy->getNumParams() != 3 ||
01572         !FTy->getParamType(1)->isPointerTy())
01573       return false;
01574     setDoesNotThrow(F);
01575     setDoesNotCapture(F, 2);
01576     setOnlyReadsMemory(F, 2);
01577     break;
01578   case LibFunc::under_IO_getc:
01579     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
01580       return false;
01581     setDoesNotThrow(F);
01582     setDoesNotCapture(F, 1);
01583     break;
01584   case LibFunc::under_IO_putc:
01585     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
01586       return false;
01587     setDoesNotThrow(F);
01588     setDoesNotCapture(F, 2);
01589     break;
01590   case LibFunc::dunder_isoc99_scanf:
01591     if (FTy->getNumParams() < 1 ||
01592         !FTy->getParamType(0)->isPointerTy())
01593       return false;
01594     setDoesNotThrow(F);
01595     setDoesNotCapture(F, 1);
01596     setOnlyReadsMemory(F, 1);
01597     break;
01598   case LibFunc::stat64:
01599   case LibFunc::lstat64:
01600   case LibFunc::statvfs64:
01601     if (FTy->getNumParams() < 1 ||
01602         !FTy->getParamType(0)->isPointerTy() ||
01603         !FTy->getParamType(1)->isPointerTy())
01604       return false;
01605     setDoesNotThrow(F);
01606     setDoesNotCapture(F, 1);
01607     setDoesNotCapture(F, 2);
01608     setOnlyReadsMemory(F, 1);
01609     break;
01610   case LibFunc::dunder_isoc99_sscanf:
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     setOnlyReadsMemory(F, 2);
01620     break;
01621   case LibFunc::fopen64:
01622     if (FTy->getNumParams() != 2 ||
01623         !FTy->getReturnType()->isPointerTy() ||
01624         !FTy->getParamType(0)->isPointerTy() ||
01625         !FTy->getParamType(1)->isPointerTy())
01626       return false;
01627     setDoesNotThrow(F);
01628     setDoesNotAlias(F, 0);
01629     setDoesNotCapture(F, 1);
01630     setDoesNotCapture(F, 2);
01631     setOnlyReadsMemory(F, 1);
01632     setOnlyReadsMemory(F, 2);
01633     break;
01634   case LibFunc::fseeko64:
01635   case LibFunc::ftello64:
01636     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
01637       return false;
01638     setDoesNotThrow(F);
01639     setDoesNotCapture(F, 1);
01640     break;
01641   case LibFunc::tmpfile64:
01642     if (!FTy->getReturnType()->isPointerTy())
01643       return false;
01644     setDoesNotThrow(F);
01645     setDoesNotAlias(F, 0);
01646     break;
01647   case LibFunc::fstat64:
01648   case LibFunc::fstatvfs64:
01649     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
01650       return false;
01651     setDoesNotThrow(F);
01652     setDoesNotCapture(F, 2);
01653     break;
01654   case LibFunc::open64:
01655     if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
01656       return false;
01657     // May throw; "open" is a valid pthread cancellation point.
01658     setDoesNotCapture(F, 1);
01659     setOnlyReadsMemory(F, 1);
01660     break;
01661   case LibFunc::gettimeofday:
01662     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
01663         !FTy->getParamType(1)->isPointerTy())
01664       return false;
01665     // Currently some platforms have the restrict keyword on the arguments to
01666     // gettimeofday. To be conservative, do not add noalias to gettimeofday's
01667     // arguments.
01668     setDoesNotThrow(F);
01669     setDoesNotCapture(F, 1);
01670     setDoesNotCapture(F, 2);
01671     break;
01672   default:
01673     // Didn't mark any attributes.
01674     return false;
01675   }
01676 
01677   return true;
01678 }
01679 
01680 /// annotateLibraryCalls - Adds attributes to well-known standard library
01681 /// call declarations.
01682 bool FunctionAttrs::annotateLibraryCalls(const CallGraphSCC &SCC) {
01683   bool MadeChange = false;
01684 
01685   // Check each function in turn annotating well-known library function
01686   // declarations with attributes.
01687   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
01688     Function *F = (*I)->getFunction();
01689 
01690     if (F && F->isDeclaration())
01691       MadeChange |= inferPrototypeAttributes(*F);
01692   }
01693 
01694   return MadeChange;
01695 }
01696 
01697 bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) {
01698   AA = &getAnalysis<AliasAnalysis>();
01699   TLI = &getAnalysis<TargetLibraryInfo>();
01700 
01701   bool Changed = annotateLibraryCalls(SCC);
01702   Changed |= AddReadAttrs(SCC);
01703   Changed |= AddArgumentAttrs(SCC);
01704   Changed |= AddNoAliasAttrs(SCC);
01705   return Changed;
01706 }