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