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