1 //===- FunctionAttrs.cpp - Pass which marks functions attributes ----------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements a simple interprocedural pass which walks the
11 // call-graph, looking for functions which do not access or only read
12 // non-local memory, and marking them readnone/readonly.  It does the
13 // same with function arguments independently, marking them readonly/
14 // readnone/nocapture.  Finally, well-known library call declarations
15 // are marked with all attributes that are consistent with the
16 // function's standard definition. This pass is implemented as a
17 // bottom-up traversal of the call-graph.
18 //
19 //===----------------------------------------------------------------------===//
20 
21 #define DEBUG_TYPE "functionattrs"
22 #include "llvm/Transforms/IPO.h"
23 #include "llvm/ADT/SCCIterator.h"
24 #include "llvm/ADT/SetVector.h"
25 #include "llvm/ADT/SmallSet.h"
26 #include "llvm/ADT/Statistic.h"
27 #include "llvm/Analysis/AliasAnalysis.h"
28 #include "llvm/Analysis/CallGraph.h"
29 #include "llvm/Analysis/CallGraphSCCPass.h"
30 #include "llvm/Analysis/CaptureTracking.h"
31 #include "llvm/IR/GlobalVariable.h"
32 #include "llvm/IR/IntrinsicInst.h"
33 #include "llvm/IR/LLVMContext.h"
34 #include "llvm/Support/InstIterator.h"
35 #include "llvm/Target/TargetLibraryInfo.h"
36 using namespace llvm;
37 
38 STATISTIC(NumReadNone, "Number of functions marked readnone");
39 STATISTIC(NumReadOnly, "Number of functions marked readonly");
40 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
41 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
42 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
43 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
44 STATISTIC(NumAnnotated, "Number of attributes added to library functions");
45 
46 namespace {
47   struct FunctionAttrs : public CallGraphSCCPass {
48     static char ID; // Pass identification, replacement for typeid
49     FunctionAttrs() : CallGraphSCCPass(ID), AA(0) {
50       initializeFunctionAttrsPass(*PassRegistry::getPassRegistry());
51     }
52 
53     // runOnSCC - Analyze the SCC, performing the transformation if possible.
54     bool runOnSCC(CallGraphSCC &SCC);
55 
56     // AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
57     bool AddReadAttrs(const CallGraphSCC &SCC);
58 
59     // AddArgumentAttrs - Deduce nocapture attributes for the SCC.
60     bool AddArgumentAttrs(const CallGraphSCC &SCC);
61 
62     // IsFunctionMallocLike - Does this function allocate new memory?
63     bool IsFunctionMallocLike(Function *F,
64                               SmallPtrSet<Function*, 8> &) const;
65 
66     // AddNoAliasAttrs - Deduce noalias attributes for the SCC.
67     bool AddNoAliasAttrs(const CallGraphSCC &SCC);
68 
69     // Utility methods used by inferPrototypeAttributes to add attributes
70     // and maintain annotation statistics.
71 
72     void setDoesNotAccessMemory(Function &F) {
73       if (!F.doesNotAccessMemory()) {
74         F.setDoesNotAccessMemory();
75         ++NumAnnotated;
76       }
77     }
78 
79     void setOnlyReadsMemory(Function &F) {
80       if (!F.onlyReadsMemory()) {
81         F.setOnlyReadsMemory();
82         ++NumAnnotated;
83       }
84     }
85 
86     void setDoesNotThrow(Function &F) {
87       if (!F.doesNotThrow()) {
88         F.setDoesNotThrow();
89         ++NumAnnotated;
90       }
91     }
92 
93     void setDoesNotCapture(Function &F, unsigned n) {
94       if (!F.doesNotCapture(n)) {
95         F.setDoesNotCapture(n);
96         ++NumAnnotated;
97       }
98     }
99 
100     void setOnlyReadsMemory(Function &F, unsigned n) {
101       if (!F.onlyReadsMemory(n)) {
102         F.setOnlyReadsMemory(n);
103         ++NumAnnotated;
104       }
105     }
106 
107     void setDoesNotAlias(Function &F, unsigned n) {
108       if (!F.doesNotAlias(n)) {
109         F.setDoesNotAlias(n);
110         ++NumAnnotated;
111       }
112     }
113 
114     // inferPrototypeAttributes - Analyze the name and prototype of the
115     // given function and set any applicable attributes.  Returns true
116     // if any attributes were set and false otherwise.
117     bool inferPrototypeAttributes(Function &F);
118 
119     // annotateLibraryCalls - Adds attributes to well-known standard library
120     // call declarations.
121     bool annotateLibraryCalls(const CallGraphSCC &SCC);
122 
123     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
124       AU.setPreservesCFG();
125       AU.addRequired<AliasAnalysis>();
126       AU.addRequired<TargetLibraryInfo>();
127       CallGraphSCCPass::getAnalysisUsage(AU);
128     }
129 
130   private:
131     AliasAnalysis *AA;
132     TargetLibraryInfo *TLI;
133   };
134 }
135 
136 char FunctionAttrs::ID = 0;
137 INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs",
138                 "Deduce function attributes", false, false)
139 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
140 INITIALIZE_AG_DEPENDENCY(CallGraph)
141 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
142 INITIALIZE_PASS_END(FunctionAttrs, "functionattrs",
143                 "Deduce function attributes", false, false)
144 
145 Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); }
146 
147 
148 /// AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
149 bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) {
150   SmallPtrSet<Function*, 8> SCCNodes;
151 
152   // Fill SCCNodes with the elements of the SCC.  Used for quickly
153   // looking up whether a given CallGraphNode is in this SCC.
154   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
155     SCCNodes.insert((*I)->getFunction());
156 
157   // Check if any of the functions in the SCC read or write memory.  If they
158   // write memory then they can't be marked readnone or readonly.
159   bool ReadsMemory = false;
160   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
161     Function *F = (*I)->getFunction();
162 
163     if (F == 0)
164       // External node - may write memory.  Just give up.
165       return false;
166 
167     AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(F);
168     if (MRB == AliasAnalysis::DoesNotAccessMemory)
169       // Already perfect!
170       continue;
171 
172     // Definitions with weak linkage may be overridden at linktime with
173     // something that writes memory, so treat them like declarations.
174     if (F->isDeclaration() || F->mayBeOverridden()) {
175       if (!AliasAnalysis::onlyReadsMemory(MRB))
176         // May write memory.  Just give up.
177         return false;
178 
179       ReadsMemory = true;
180       continue;
181     }
182 
183     // Scan the function body for instructions that may read or write memory.
184     for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
185       Instruction *I = &*II;
186 
187       // Some instructions can be ignored even if they read or write memory.
188       // Detect these now, skipping to the next instruction if one is found.
189       CallSite CS(cast<Value>(I));
190       if (CS) {
191         // Ignore calls to functions in the same SCC.
192         if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
193           continue;
194         AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(CS);
195         // If the call doesn't access arbitrary memory, we may be able to
196         // figure out something.
197         if (AliasAnalysis::onlyAccessesArgPointees(MRB)) {
198           // If the call does access argument pointees, check each argument.
199           if (AliasAnalysis::doesAccessArgPointees(MRB))
200             // Check whether all pointer arguments point to local memory, and
201             // ignore calls that only access local memory.
202             for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
203                  CI != CE; ++CI) {
204               Value *Arg = *CI;
205               if (Arg->getType()->isPointerTy()) {
206                 AliasAnalysis::Location Loc(Arg,
207                                             AliasAnalysis::UnknownSize,
208                                             I->getMetadata(LLVMContext::MD_tbaa));
209                 if (!AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) {
210                   if (MRB & AliasAnalysis::Mod)
211                     // Writes non-local memory.  Give up.
212                     return false;
213                   if (MRB & AliasAnalysis::Ref)
214                     // Ok, it reads non-local memory.
215                     ReadsMemory = true;
216                 }
217               }
218             }
219           continue;
220         }
221         // The call could access any memory. If that includes writes, give up.
222         if (MRB & AliasAnalysis::Mod)
223           return false;
224         // If it reads, note it.
225         if (MRB & AliasAnalysis::Ref)
226           ReadsMemory = true;
227         continue;
228       } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
229         // Ignore non-volatile loads from local memory. (Atomic is okay here.)
230         if (!LI->isVolatile()) {
231           AliasAnalysis::Location Loc = AA->getLocation(LI);
232           if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true))
233             continue;
234         }
235       } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
236         // Ignore non-volatile stores to local memory. (Atomic is okay here.)
237         if (!SI->isVolatile()) {
238           AliasAnalysis::Location Loc = AA->getLocation(SI);
239           if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true))
240             continue;
241         }
242       } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) {
243         // Ignore vaargs on local memory.
244         AliasAnalysis::Location Loc = AA->getLocation(VI);
245         if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true))
246           continue;
247       }
248 
249       // Any remaining instructions need to be taken seriously!  Check if they
250       // read or write memory.
251       if (I->mayWriteToMemory())
252         // Writes memory.  Just give up.
253         return false;
254 
255       // If this instruction may read memory, remember that.
256       ReadsMemory |= I->mayReadFromMemory();
257     }
258   }
259 
260   // Success!  Functions in this SCC do not access memory, or only read memory.
261   // Give them the appropriate attribute.
262   bool MadeChange = false;
263   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
264     Function *F = (*I)->getFunction();
265 
266     if (F->doesNotAccessMemory())
267       // Already perfect!
268       continue;
269 
270     if (F->onlyReadsMemory() && ReadsMemory)
271       // No change.
272       continue;
273 
274     MadeChange = true;
275 
276     // Clear out any existing attributes.
277     AttrBuilder B;
278     B.addAttribute(Attribute::ReadOnly)
279       .addAttribute(Attribute::ReadNone);
280     F->removeAttributes(AttributeSet::FunctionIndex,
281                         AttributeSet::get(F->getContext(),
282                                           AttributeSet::FunctionIndex, B));
283 
284     // Add in the new attribute.
285     F->addAttribute(AttributeSet::FunctionIndex,
286                     ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone);
287 
288     if (ReadsMemory)
289       ++NumReadOnly;
290     else
291       ++NumReadNone;
292   }
293 
294   return MadeChange;
295 }
296 
297 namespace {
298   // For a given pointer Argument, this retains a list of Arguments of functions
299   // in the same SCC that the pointer data flows into. We use this to build an
300   // SCC of the arguments.
301   struct ArgumentGraphNode {
302     Argument *Definition;
303     SmallVector<ArgumentGraphNode*, 4> Uses;
304   };
305 
306   class ArgumentGraph {
307     // We store pointers to ArgumentGraphNode objects, so it's important that
308     // that they not move around upon insert.
309     typedef std::map<Argument*, ArgumentGraphNode> ArgumentMapTy;
310 
311     ArgumentMapTy ArgumentMap;
312 
313     // There is no root node for the argument graph, in fact:
314     //   void f(int *x, int *y) { if (...) f(x, y); }
315     // is an example where the graph is disconnected. The SCCIterator requires a
316     // single entry point, so we maintain a fake ("synthetic") root node that
317     // uses every node. Because the graph is directed and nothing points into
318     // the root, it will not participate in any SCCs (except for its own).
319     ArgumentGraphNode SyntheticRoot;
320 
321   public:
322     ArgumentGraph() { SyntheticRoot.Definition = 0; }
323 
324     typedef SmallVectorImpl<ArgumentGraphNode*>::iterator iterator;
325 
326     iterator begin() { return SyntheticRoot.Uses.begin(); }
327     iterator end() { return SyntheticRoot.Uses.end(); }
328     ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; }
329 
330     ArgumentGraphNode *operator[](Argument *A) {
331       ArgumentGraphNode &Node = ArgumentMap[A];
332       Node.Definition = A;
333       SyntheticRoot.Uses.push_back(&Node);
334       return &Node;
335     }
336   };
337 
338   // This tracker checks whether callees are in the SCC, and if so it does not
339   // consider that a capture, instead adding it to the "Uses" list and
340   // continuing with the analysis.
341   struct ArgumentUsesTracker : public CaptureTracker {
342     ArgumentUsesTracker(const SmallPtrSet<Function*, 8> &SCCNodes)
343       : Captured(false), SCCNodes(SCCNodes) {}
344 
345     void tooManyUses() { Captured = true; }
346 
347     bool captured(Use *U) {
348       CallSite CS(U->getUser());
349       if (!CS.getInstruction()) { Captured = true; return true; }
350 
351       Function *F = CS.getCalledFunction();
352       if (!F || !SCCNodes.count(F)) { Captured = true; return true; }
353 
354       bool Found = false;
355       Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end();
356       for (CallSite::arg_iterator PI = CS.arg_begin(), PE = CS.arg_end();
357            PI != PE; ++PI, ++AI) {
358         if (AI == AE) {
359           assert(F->isVarArg() && "More params than args in non-varargs call");
360           Captured = true;
361           return true;
362         }
363         if (PI == U) {
364           Uses.push_back(AI);
365           Found = true;
366           break;
367         }
368       }
369       assert(Found && "Capturing call-site captured nothing?");
370       return false;
371     }
372 
373     bool Captured;  // True only if certainly captured (used outside our SCC).
374     SmallVector<Argument*, 4> Uses;  // Uses within our SCC.
375 
376     const SmallPtrSet<Function*, 8> &SCCNodes;
377   };
378 }
379 
380 namespace llvm {
381   template<> struct GraphTraits<ArgumentGraphNode*> {
382     typedef ArgumentGraphNode NodeType;
383     typedef SmallVectorImpl<ArgumentGraphNode*>::iterator ChildIteratorType;
384 
385     static inline NodeType *getEntryNode(NodeType *A) { return A; }
386     static inline ChildIteratorType child_begin(NodeType *N) {
387       return N->Uses.begin();
388     }
389     static inline ChildIteratorType child_end(NodeType *N) {
390       return N->Uses.end();
391     }
392   };
393   template<> struct GraphTraits<ArgumentGraph*>
394     : public GraphTraits<ArgumentGraphNode*> {
395     static NodeType *getEntryNode(ArgumentGraph *AG) {
396       return AG->getEntryNode();
397     }
398     static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
399       return AG->begin();
400     }
401     static ChildIteratorType nodes_end(ArgumentGraph *AG) {
402       return AG->end();
403     }
404   };
405 }
406 
407 // Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
408 static Attribute::AttrKind
409 determinePointerReadAttrs(Argument *A,
410                           const SmallPtrSet<Argument*, 8> &SCCNodes) {
411 
412   SmallVector<Use*, 32> Worklist;
413   SmallSet<Use*, 32> Visited;
414   int Count = 0;
415 
416   bool IsRead = false;
417   // We don't need to track IsWritten. If A is written to, return immediately.
418 
419   for (Value::use_iterator UI = A->use_begin(), UE = A->use_end();
420        UI != UE; ++UI) {
421     if (Count++ >= 20)
422       return Attribute::None;
423 
424     Use *U = &UI.getUse();
425     Visited.insert(U);
426     Worklist.push_back(U);
427   }
428 
429   while (!Worklist.empty()) {
430     Use *U = Worklist.pop_back_val();
431     Instruction *I = cast<Instruction>(U->getUser());
432     Value *V = U->get();
433 
434     switch (I->getOpcode()) {
435     case Instruction::BitCast:
436     case Instruction::GetElementPtr:
437     case Instruction::PHI:
438     case Instruction::Select:
439       // The original value is not read/written via this if the new value isn't.
440       for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end();
441            UI != UE; ++UI) {
442         Use *U = &UI.getUse();
443         if (Visited.insert(U))
444           Worklist.push_back(U);
445       }
446       break;
447 
448     case Instruction::Call:
449     case Instruction::Invoke: {
450       CallSite CS(I);
451       if (CS.doesNotAccessMemory())
452         continue;
453 
454       Function *F = CS.getCalledFunction();
455       if (!F) {
456         if (CS.onlyReadsMemory()) {
457           IsRead = true;
458           continue;
459         }
460         return Attribute::None;
461       }
462 
463       Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end();
464       CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end();
465       for (CallSite::arg_iterator A = B; A != E; ++A, ++AI) {
466         if (A->get() == V) {
467           if (AI == AE) {
468             assert(F->isVarArg() &&
469                    "More params than args in non-varargs call.");
470             return Attribute::None;
471           }
472           if (SCCNodes.count(AI))
473             continue;
474           if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(A - B))
475             return Attribute::None;
476           if (!CS.doesNotAccessMemory(A - B))
477             IsRead = true;
478         }
479       }
480       break;
481     }
482 
483     case Instruction::Load:
484       IsRead = true;
485       break;
486 
487     case Instruction::ICmp:
488     case Instruction::Ret:
489       break;
490 
491     default:
492       return Attribute::None;
493     }
494   }
495 
496   return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
497 }
498 
499 /// AddArgumentAttrs - Deduce nocapture attributes for the SCC.
500 bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) {
501   bool Changed = false;
502 
503   SmallPtrSet<Function*, 8> SCCNodes;
504 
505   // Fill SCCNodes with the elements of the SCC.  Used for quickly
506   // looking up whether a given CallGraphNode is in this SCC.
507   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
508     Function *F = (*I)->getFunction();
509     if (F && !F->isDeclaration() && !F->mayBeOverridden())
510       SCCNodes.insert(F);
511   }
512 
513   ArgumentGraph AG;
514 
515   AttrBuilder B;
516   B.addAttribute(Attribute::NoCapture);
517 
518   // Check each function in turn, determining which pointer arguments are not
519   // captured.
520   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
521     Function *F = (*I)->getFunction();
522 
523     if (F == 0)
524       // External node - only a problem for arguments that we pass to it.
525       continue;
526 
527     // Definitions with weak linkage may be overridden at linktime with
528     // something that captures pointers, so treat them like declarations.
529     if (F->isDeclaration() || F->mayBeOverridden())
530       continue;
531 
532     // Functions that are readonly (or readnone) and nounwind and don't return
533     // a value can't capture arguments. Don't analyze them.
534     if (F->onlyReadsMemory() && F->doesNotThrow() &&
535         F->getReturnType()->isVoidTy()) {
536       for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end();
537            A != E; ++A) {
538         if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
539           A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
540           ++NumNoCapture;
541           Changed = true;
542         }
543       }
544       continue;
545     }
546 
547     for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end();
548          A != E; ++A) {
549       if (!A->getType()->isPointerTy()) continue;
550       bool HasNonLocalUses = false;
551       if (!A->hasNoCaptureAttr()) {
552         ArgumentUsesTracker Tracker(SCCNodes);
553         PointerMayBeCaptured(A, &Tracker);
554         if (!Tracker.Captured) {
555           if (Tracker.Uses.empty()) {
556             // If it's trivially not captured, mark it nocapture now.
557             A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo()+1, B));
558             ++NumNoCapture;
559             Changed = true;
560           } else {
561             // If it's not trivially captured and not trivially not captured,
562             // then it must be calling into another function in our SCC. Save
563             // its particulars for Argument-SCC analysis later.
564             ArgumentGraphNode *Node = AG[A];
565             for (SmallVectorImpl<Argument*>::iterator UI = Tracker.Uses.begin(),
566                      UE = Tracker.Uses.end(); UI != UE; ++UI) {
567               Node->Uses.push_back(AG[*UI]);
568               if (*UI != A)
569                 HasNonLocalUses = true;
570             }
571           }
572         }
573         // Otherwise, it's captured. Don't bother doing SCC analysis on it.
574       }
575       if (!HasNonLocalUses && !A->onlyReadsMemory()) {
576         // Can we determine that it's readonly/readnone without doing an SCC?
577         // Note that we don't allow any calls at all here, or else our result
578         // will be dependent on the iteration order through the functions in the
579         // SCC.
580         SmallPtrSet<Argument*, 8> Self;
581         Self.insert(A);
582         Attribute::AttrKind R = determinePointerReadAttrs(A, Self);
583         if (R != Attribute::None) {
584           AttrBuilder B;
585           B.addAttribute(R);
586           A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
587           Changed = true;
588           R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
589         }
590       }
591     }
592   }
593 
594   // The graph we've collected is partial because we stopped scanning for
595   // argument uses once we solved the argument trivially. These partial nodes
596   // show up as ArgumentGraphNode objects with an empty Uses list, and for
597   // these nodes the final decision about whether they capture has already been
598   // made.  If the definition doesn't have a 'nocapture' attribute by now, it
599   // captures.
600 
601   for (scc_iterator<ArgumentGraph*> I = scc_begin(&AG), E = scc_end(&AG);
602        I != E; ++I) {
603     std::vector<ArgumentGraphNode*> &ArgumentSCC = *I;
604     if (ArgumentSCC.size() == 1) {
605       if (!ArgumentSCC[0]->Definition) continue;  // synthetic root node
606 
607       // eg. "void f(int* x) { if (...) f(x); }"
608       if (ArgumentSCC[0]->Uses.size() == 1 &&
609           ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
610         Argument *A = ArgumentSCC[0]->Definition;
611         A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
612         ++NumNoCapture;
613         Changed = true;
614       }
615       continue;
616     }
617 
618     bool SCCCaptured = false;
619     for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(),
620            E = ArgumentSCC.end(); I != E && !SCCCaptured; ++I) {
621       ArgumentGraphNode *Node = *I;
622       if (Node->Uses.empty()) {
623         if (!Node->Definition->hasNoCaptureAttr())
624           SCCCaptured = true;
625       }
626     }
627     if (SCCCaptured) continue;
628 
629     SmallPtrSet<Argument*, 8> ArgumentSCCNodes;
630     // Fill ArgumentSCCNodes with the elements of the ArgumentSCC.  Used for
631     // quickly looking up whether a given Argument is in this ArgumentSCC.
632     for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(),
633            E = ArgumentSCC.end(); I != E; ++I) {
634       ArgumentSCCNodes.insert((*I)->Definition);
635     }
636 
637     for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(),
638            E = ArgumentSCC.end(); I != E && !SCCCaptured; ++I) {
639       ArgumentGraphNode *N = *I;
640       for (SmallVectorImpl<ArgumentGraphNode*>::iterator UI = N->Uses.begin(),
641              UE = N->Uses.end(); UI != UE; ++UI) {
642         Argument *A = (*UI)->Definition;
643         if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
644           continue;
645         SCCCaptured = true;
646         break;
647       }
648     }
649     if (SCCCaptured) continue;
650 
651     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
652       Argument *A = ArgumentSCC[i]->Definition;
653       A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
654       ++NumNoCapture;
655       Changed = true;
656     }
657 
658     // We also want to compute readonly/readnone. With a small number of false
659     // negatives, we can assume that any pointer which is captured isn't going
660     // to be provably readonly or readnone, since by definition we can't
661     // analyze all uses of a captured pointer.
662     //
663     // The false negatives happen when the pointer is captured by a function
664     // that promises readonly/readnone behaviour on the pointer, then the
665     // pointer's lifetime ends before anything that writes to arbitrary memory.
666     // Also, a readonly/readnone pointer may be returned, but returning a
667     // pointer is capturing it.
668 
669     Attribute::AttrKind ReadAttr = Attribute::ReadNone;
670     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
671       Argument *A = ArgumentSCC[i]->Definition;
672       Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes);
673       if (K == Attribute::ReadNone)
674         continue;
675       if (K == Attribute::ReadOnly) {
676         ReadAttr = Attribute::ReadOnly;
677         continue;
678       }
679       ReadAttr = K;
680       break;
681     }
682 
683     if (ReadAttr != Attribute::None) {
684       AttrBuilder B;
685       B.addAttribute(ReadAttr);
686       for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
687         Argument *A = ArgumentSCC[i]->Definition;
688         A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
689         ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
690         Changed = true;
691       }
692     }
693   }
694 
695   return Changed;
696 }
697 
698 /// IsFunctionMallocLike - A function is malloc-like if it returns either null
699 /// or a pointer that doesn't alias any other pointer visible to the caller.
700 bool FunctionAttrs::IsFunctionMallocLike(Function *F,
701                               SmallPtrSet<Function*, 8> &SCCNodes) const {
702   SmallSetVector<Value *, 8> FlowsToReturn;
703   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
704     if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator()))
705       FlowsToReturn.insert(Ret->getReturnValue());
706 
707   for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
708     Value *RetVal = FlowsToReturn[i];
709 
710     if (Constant *C = dyn_cast<Constant>(RetVal)) {
711       if (!C->isNullValue() && !isa<UndefValue>(C))
712         return false;
713 
714       continue;
715     }
716 
717     if (isa<Argument>(RetVal))
718       return false;
719 
720     if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
721       switch (RVI->getOpcode()) {
722         // Extend the analysis by looking upwards.
723         case Instruction::BitCast:
724         case Instruction::GetElementPtr:
725           FlowsToReturn.insert(RVI->getOperand(0));
726           continue;
727         case Instruction::Select: {
728           SelectInst *SI = cast<SelectInst>(RVI);
729           FlowsToReturn.insert(SI->getTrueValue());
730           FlowsToReturn.insert(SI->getFalseValue());
731           continue;
732         }
733         case Instruction::PHI: {
734           PHINode *PN = cast<PHINode>(RVI);
735           for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
736             FlowsToReturn.insert(PN->getIncomingValue(i));
737           continue;
738         }
739 
740         // Check whether the pointer came from an allocation.
741         case Instruction::Alloca:
742           break;
743         case Instruction::Call:
744         case Instruction::Invoke: {
745           CallSite CS(RVI);
746           if (CS.paramHasAttr(0, Attribute::NoAlias))
747             break;
748           if (CS.getCalledFunction() &&
749               SCCNodes.count(CS.getCalledFunction()))
750             break;
751         } // fall-through
752         default:
753           return false;  // Did not come from an allocation.
754       }
755 
756     if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
757       return false;
758   }
759 
760   return true;
761 }
762 
763 /// AddNoAliasAttrs - Deduce noalias attributes for the SCC.
764 bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) {
765   SmallPtrSet<Function*, 8> SCCNodes;
766 
767   // Fill SCCNodes with the elements of the SCC.  Used for quickly
768   // looking up whether a given CallGraphNode is in this SCC.
769   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
770     SCCNodes.insert((*I)->getFunction());
771 
772   // Check each function in turn, determining which functions return noalias
773   // pointers.
774   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
775     Function *F = (*I)->getFunction();
776 
777     if (F == 0)
778       // External node - skip it;
779       return false;
780 
781     // Already noalias.
782     if (F->doesNotAlias(0))
783       continue;
784 
785     // Definitions with weak linkage may be overridden at linktime, so
786     // treat them like declarations.
787     if (F->isDeclaration() || F->mayBeOverridden())
788       return false;
789 
790     // We annotate noalias return values, which are only applicable to
791     // pointer types.
792     if (!F->getReturnType()->isPointerTy())
793       continue;
794 
795     if (!IsFunctionMallocLike(F, SCCNodes))
796       return false;
797   }
798 
799   bool MadeChange = false;
800   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
801     Function *F = (*I)->getFunction();
802     if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy())
803       continue;
804 
805     F->setDoesNotAlias(0);
806     ++NumNoAlias;
807     MadeChange = true;
808   }
809 
810   return MadeChange;
811 }
812 
813 /// inferPrototypeAttributes - Analyze the name and prototype of the
814 /// given function and set any applicable attributes.  Returns true
815 /// if any attributes were set and false otherwise.
816 bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
817   FunctionType *FTy = F.getFunctionType();
818   LibFunc::Func TheLibFunc;
819   if (!(TLI->getLibFunc(F.getName(), TheLibFunc) && TLI->has(TheLibFunc)))
820     return false;
821 
822   switch (TheLibFunc) {
823   case LibFunc::strlen:
824     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
825       return false;
826     setOnlyReadsMemory(F);
827     setDoesNotThrow(F);
828     setDoesNotCapture(F, 1);
829     break;
830   case LibFunc::strchr:
831   case LibFunc::strrchr:
832     if (FTy->getNumParams() != 2 ||
833         !FTy->getParamType(0)->isPointerTy() ||
834         !FTy->getParamType(1)->isIntegerTy())
835       return false;
836     setOnlyReadsMemory(F);
837     setDoesNotThrow(F);
838     break;
839   case LibFunc::strtol:
840   case LibFunc::strtod:
841   case LibFunc::strtof:
842   case LibFunc::strtoul:
843   case LibFunc::strtoll:
844   case LibFunc::strtold:
845   case LibFunc::strtoull:
846     if (FTy->getNumParams() < 2 ||
847         !FTy->getParamType(1)->isPointerTy())
848       return false;
849     setDoesNotThrow(F);
850     setDoesNotCapture(F, 2);
851     setOnlyReadsMemory(F, 1);
852     break;
853   case LibFunc::strcpy:
854   case LibFunc::stpcpy:
855   case LibFunc::strcat:
856   case LibFunc::strncat:
857   case LibFunc::strncpy:
858   case LibFunc::stpncpy:
859     if (FTy->getNumParams() < 2 ||
860         !FTy->getParamType(1)->isPointerTy())
861       return false;
862     setDoesNotThrow(F);
863     setDoesNotCapture(F, 2);
864     setOnlyReadsMemory(F, 2);
865     break;
866   case LibFunc::strxfrm:
867     if (FTy->getNumParams() != 3 ||
868         !FTy->getParamType(0)->isPointerTy() ||
869         !FTy->getParamType(1)->isPointerTy())
870       return false;
871     setDoesNotThrow(F);
872     setDoesNotCapture(F, 1);
873     setDoesNotCapture(F, 2);
874     setOnlyReadsMemory(F, 2);
875     break;
876   case LibFunc::strcmp: //0,1
877     case LibFunc::strspn: // 0,1
878     case LibFunc::strncmp: // 0,1
879     case LibFunc::strcspn: //0,1
880     case LibFunc::strcoll: //0,1
881     case LibFunc::strcasecmp:  // 0,1
882     case LibFunc::strncasecmp: //
883     if (FTy->getNumParams() < 2 ||
884         !FTy->getParamType(0)->isPointerTy() ||
885         !FTy->getParamType(1)->isPointerTy())
886       return false;
887     setOnlyReadsMemory(F);
888     setDoesNotThrow(F);
889     setDoesNotCapture(F, 1);
890     setDoesNotCapture(F, 2);
891     break;
892   case LibFunc::strstr:
893   case LibFunc::strpbrk:
894     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
895       return false;
896     setOnlyReadsMemory(F);
897     setDoesNotThrow(F);
898     setDoesNotCapture(F, 2);
899     break;
900   case LibFunc::strtok:
901   case LibFunc::strtok_r:
902     if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
903       return false;
904     setDoesNotThrow(F);
905     setDoesNotCapture(F, 2);
906     setOnlyReadsMemory(F, 2);
907     break;
908   case LibFunc::scanf:
909     if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
910       return false;
911     setDoesNotThrow(F);
912     setDoesNotCapture(F, 1);
913     setOnlyReadsMemory(F, 1);
914     break;
915   case LibFunc::setbuf:
916   case LibFunc::setvbuf:
917     if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
918       return false;
919     setDoesNotThrow(F);
920     setDoesNotCapture(F, 1);
921     break;
922   case LibFunc::strdup:
923   case LibFunc::strndup:
924     if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() ||
925         !FTy->getParamType(0)->isPointerTy())
926       return false;
927     setDoesNotThrow(F);
928     setDoesNotAlias(F, 0);
929     setDoesNotCapture(F, 1);
930     setOnlyReadsMemory(F, 1);
931     break;
932   case LibFunc::stat:
933   case LibFunc::statvfs:
934     if (FTy->getNumParams() < 2 ||
935         !FTy->getParamType(0)->isPointerTy() ||
936         !FTy->getParamType(1)->isPointerTy())
937       return false;
938     setDoesNotThrow(F);
939     setDoesNotCapture(F, 1);
940     setDoesNotCapture(F, 2);
941     setOnlyReadsMemory(F, 1);
942     break;
943   case LibFunc::sscanf:
944     if (FTy->getNumParams() < 2 ||
945         !FTy->getParamType(0)->isPointerTy() ||
946         !FTy->getParamType(1)->isPointerTy())
947       return false;
948     setDoesNotThrow(F);
949     setDoesNotCapture(F, 1);
950     setDoesNotCapture(F, 2);
951     setOnlyReadsMemory(F, 1);
952     setOnlyReadsMemory(F, 2);
953     break;
954   case LibFunc::sprintf:
955     if (FTy->getNumParams() < 2 ||
956         !FTy->getParamType(0)->isPointerTy() ||
957         !FTy->getParamType(1)->isPointerTy())
958       return false;
959     setDoesNotThrow(F);
960     setDoesNotCapture(F, 1);
961     setDoesNotCapture(F, 2);
962     setOnlyReadsMemory(F, 2);
963     break;
964   case LibFunc::snprintf:
965     if (FTy->getNumParams() != 3 ||
966         !FTy->getParamType(0)->isPointerTy() ||
967         !FTy->getParamType(2)->isPointerTy())
968       return false;
969     setDoesNotThrow(F);
970     setDoesNotCapture(F, 1);
971     setDoesNotCapture(F, 3);
972     setOnlyReadsMemory(F, 3);
973     break;
974   case LibFunc::setitimer:
975     if (FTy->getNumParams() != 3 ||
976         !FTy->getParamType(1)->isPointerTy() ||
977         !FTy->getParamType(2)->isPointerTy())
978       return false;
979     setDoesNotThrow(F);
980     setDoesNotCapture(F, 2);
981     setDoesNotCapture(F, 3);
982     setOnlyReadsMemory(F, 2);
983     break;
984   case LibFunc::system:
985     if (FTy->getNumParams() != 1 ||
986         !FTy->getParamType(0)->isPointerTy())
987       return false;
988     // May throw; "system" is a valid pthread cancellation point.
989     setDoesNotCapture(F, 1);
990     setOnlyReadsMemory(F, 1);
991     break;
992   case LibFunc::malloc:
993     if (FTy->getNumParams() != 1 ||
994         !FTy->getReturnType()->isPointerTy())
995       return false;
996     setDoesNotThrow(F);
997     setDoesNotAlias(F, 0);
998     break;
999   case LibFunc::memcmp:
1000     if (FTy->getNumParams() != 3 ||
1001         !FTy->getParamType(0)->isPointerTy() ||
1002         !FTy->getParamType(1)->isPointerTy())
1003       return false;
1004     setOnlyReadsMemory(F);
1005     setDoesNotThrow(F);
1006     setDoesNotCapture(F, 1);
1007     setDoesNotCapture(F, 2);
1008     break;
1009   case LibFunc::memchr:
1010   case LibFunc::memrchr:
1011     if (FTy->getNumParams() != 3)
1012       return false;
1013     setOnlyReadsMemory(F);
1014     setDoesNotThrow(F);
1015     break;
1016   case LibFunc::modf:
1017   case LibFunc::modff:
1018   case LibFunc::modfl:
1019     if (FTy->getNumParams() < 2 ||
1020         !FTy->getParamType(1)->isPointerTy())
1021       return false;
1022     setDoesNotThrow(F);
1023     setDoesNotCapture(F, 2);
1024     break;
1025   case LibFunc::memcpy:
1026   case LibFunc::memccpy:
1027   case LibFunc::memmove:
1028     if (FTy->getNumParams() < 2 ||
1029         !FTy->getParamType(1)->isPointerTy())
1030       return false;
1031     setDoesNotThrow(F);
1032     setDoesNotCapture(F, 2);
1033     setOnlyReadsMemory(F, 2);
1034     break;
1035   case LibFunc::memalign:
1036     if (!FTy->getReturnType()->isPointerTy())
1037       return false;
1038     setDoesNotAlias(F, 0);
1039     break;
1040   case LibFunc::mkdir:
1041     if (FTy->getNumParams() == 0 ||
1042         !FTy->getParamType(0)->isPointerTy())
1043       return false;
1044     setDoesNotThrow(F);
1045     setDoesNotCapture(F, 1);
1046     setOnlyReadsMemory(F, 1);
1047     break;
1048   case LibFunc::mktime:
1049     if (FTy->getNumParams() == 0 ||
1050         !FTy->getParamType(0)->isPointerTy())
1051       return false;
1052     setDoesNotThrow(F);
1053     setDoesNotCapture(F, 1);
1054     break;
1055   case LibFunc::realloc:
1056     if (FTy->getNumParams() != 2 ||
1057         !FTy->getParamType(0)->isPointerTy() ||
1058         !FTy->getReturnType()->isPointerTy())
1059       return false;
1060     setDoesNotThrow(F);
1061     setDoesNotAlias(F, 0);
1062     setDoesNotCapture(F, 1);
1063     break;
1064   case LibFunc::read:
1065     if (FTy->getNumParams() != 3 ||
1066         !FTy->getParamType(1)->isPointerTy())
1067       return false;
1068     // May throw; "read" is a valid pthread cancellation point.
1069     setDoesNotCapture(F, 2);
1070     break;
1071   case LibFunc::rewind:
1072     if (FTy->getNumParams() < 1 ||
1073         !FTy->getParamType(0)->isPointerTy())
1074       return false;
1075     setDoesNotThrow(F);
1076     setDoesNotCapture(F, 1);
1077     break;
1078   case LibFunc::rmdir:
1079   case LibFunc::remove:
1080   case LibFunc::realpath:
1081     if (FTy->getNumParams() < 1 ||
1082         !FTy->getParamType(0)->isPointerTy())
1083       return false;
1084     setDoesNotThrow(F);
1085     setDoesNotCapture(F, 1);
1086     setOnlyReadsMemory(F, 1);
1087     break;
1088   case LibFunc::rename:
1089     if (FTy->getNumParams() < 2 ||
1090         !FTy->getParamType(0)->isPointerTy() ||
1091         !FTy->getParamType(1)->isPointerTy())
1092       return false;
1093     setDoesNotThrow(F);
1094     setDoesNotCapture(F, 1);
1095     setDoesNotCapture(F, 2);
1096     setOnlyReadsMemory(F, 1);
1097     setOnlyReadsMemory(F, 2);
1098     break;
1099   case LibFunc::readlink:
1100     if (FTy->getNumParams() < 2 ||
1101         !FTy->getParamType(0)->isPointerTy() ||
1102         !FTy->getParamType(1)->isPointerTy())
1103       return false;
1104     setDoesNotThrow(F);
1105     setDoesNotCapture(F, 1);
1106     setDoesNotCapture(F, 2);
1107     setOnlyReadsMemory(F, 1);
1108     break;
1109   case LibFunc::write:
1110     if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
1111       return false;
1112     // May throw; "write" is a valid pthread cancellation point.
1113     setDoesNotCapture(F, 2);
1114     setOnlyReadsMemory(F, 2);
1115     break;
1116   case LibFunc::bcopy:
1117     if (FTy->getNumParams() != 3 ||
1118         !FTy->getParamType(0)->isPointerTy() ||
1119         !FTy->getParamType(1)->isPointerTy())
1120       return false;
1121     setDoesNotThrow(F);
1122     setDoesNotCapture(F, 1);
1123     setDoesNotCapture(F, 2);
1124     setOnlyReadsMemory(F, 1);
1125     break;
1126   case LibFunc::bcmp:
1127     if (FTy->getNumParams() != 3 ||
1128         !FTy->getParamType(0)->isPointerTy() ||
1129         !FTy->getParamType(1)->isPointerTy())
1130       return false;
1131     setDoesNotThrow(F);
1132     setOnlyReadsMemory(F);
1133     setDoesNotCapture(F, 1);
1134     setDoesNotCapture(F, 2);
1135     break;
1136   case LibFunc::bzero:
1137     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1138       return false;
1139     setDoesNotThrow(F);
1140     setDoesNotCapture(F, 1);
1141     break;
1142   case LibFunc::calloc:
1143     if (FTy->getNumParams() != 2 ||
1144         !FTy->getReturnType()->isPointerTy())
1145       return false;
1146     setDoesNotThrow(F);
1147     setDoesNotAlias(F, 0);
1148     break;
1149   case LibFunc::chmod:
1150   case LibFunc::chown:
1151     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1152       return false;
1153     setDoesNotThrow(F);
1154     setDoesNotCapture(F, 1);
1155     setOnlyReadsMemory(F, 1);
1156     break;
1157   case LibFunc::ctermid:
1158   case LibFunc::clearerr:
1159   case LibFunc::closedir:
1160     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1161       return false;
1162     setDoesNotThrow(F);
1163     setDoesNotCapture(F, 1);
1164     break;
1165   case LibFunc::atoi:
1166   case LibFunc::atol:
1167   case LibFunc::atof:
1168   case LibFunc::atoll:
1169     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1170       return false;
1171     setDoesNotThrow(F);
1172     setOnlyReadsMemory(F);
1173     setDoesNotCapture(F, 1);
1174     break;
1175   case LibFunc::access:
1176     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1177       return false;
1178     setDoesNotThrow(F);
1179     setDoesNotCapture(F, 1);
1180     setOnlyReadsMemory(F, 1);
1181     break;
1182   case LibFunc::fopen:
1183     if (FTy->getNumParams() != 2 ||
1184         !FTy->getReturnType()->isPointerTy() ||
1185         !FTy->getParamType(0)->isPointerTy() ||
1186         !FTy->getParamType(1)->isPointerTy())
1187       return false;
1188     setDoesNotThrow(F);
1189     setDoesNotAlias(F, 0);
1190     setDoesNotCapture(F, 1);
1191     setDoesNotCapture(F, 2);
1192     setOnlyReadsMemory(F, 1);
1193     setOnlyReadsMemory(F, 2);
1194     break;
1195   case LibFunc::fdopen:
1196     if (FTy->getNumParams() != 2 ||
1197         !FTy->getReturnType()->isPointerTy() ||
1198         !FTy->getParamType(1)->isPointerTy())
1199       return false;
1200     setDoesNotThrow(F);
1201     setDoesNotAlias(F, 0);
1202     setDoesNotCapture(F, 2);
1203     setOnlyReadsMemory(F, 2);
1204     break;
1205   case LibFunc::feof:
1206   case LibFunc::free:
1207   case LibFunc::fseek:
1208   case LibFunc::ftell:
1209   case LibFunc::fgetc:
1210   case LibFunc::fseeko:
1211   case LibFunc::ftello:
1212   case LibFunc::fileno:
1213   case LibFunc::fflush:
1214   case LibFunc::fclose:
1215   case LibFunc::fsetpos:
1216   case LibFunc::flockfile:
1217   case LibFunc::funlockfile:
1218   case LibFunc::ftrylockfile:
1219     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1220       return false;
1221     setDoesNotThrow(F);
1222     setDoesNotCapture(F, 1);
1223     break;
1224   case LibFunc::ferror:
1225     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1226       return false;
1227     setDoesNotThrow(F);
1228     setDoesNotCapture(F, 1);
1229     setOnlyReadsMemory(F);
1230     break;
1231   case LibFunc::fputc:
1232   case LibFunc::fstat:
1233   case LibFunc::frexp:
1234   case LibFunc::frexpf:
1235   case LibFunc::frexpl:
1236   case LibFunc::fstatvfs:
1237     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1238       return false;
1239     setDoesNotThrow(F);
1240     setDoesNotCapture(F, 2);
1241     break;
1242   case LibFunc::fgets:
1243     if (FTy->getNumParams() != 3 ||
1244         !FTy->getParamType(0)->isPointerTy() ||
1245         !FTy->getParamType(2)->isPointerTy())
1246       return false;
1247     setDoesNotThrow(F);
1248     setDoesNotCapture(F, 3);
1249     break;
1250   case LibFunc::fread:
1251     if (FTy->getNumParams() != 4 ||
1252         !FTy->getParamType(0)->isPointerTy() ||
1253         !FTy->getParamType(3)->isPointerTy())
1254       return false;
1255     setDoesNotThrow(F);
1256     setDoesNotCapture(F, 1);
1257     setDoesNotCapture(F, 4);
1258     break;
1259   case LibFunc::fwrite:
1260     if (FTy->getNumParams() != 4 ||
1261         !FTy->getParamType(0)->isPointerTy() ||
1262         !FTy->getParamType(3)->isPointerTy())
1263       return false;
1264     setDoesNotThrow(F);
1265     setDoesNotCapture(F, 1);
1266     setDoesNotCapture(F, 4);
1267     break;
1268   case LibFunc::fputs:
1269     if (FTy->getNumParams() < 2 ||
1270         !FTy->getParamType(0)->isPointerTy() ||
1271         !FTy->getParamType(1)->isPointerTy())
1272       return false;
1273     setDoesNotThrow(F);
1274     setDoesNotCapture(F, 1);
1275     setDoesNotCapture(F, 2);
1276     setOnlyReadsMemory(F, 1);
1277     break;
1278   case LibFunc::fscanf:
1279   case LibFunc::fprintf:
1280     if (FTy->getNumParams() < 2 ||
1281         !FTy->getParamType(0)->isPointerTy() ||
1282         !FTy->getParamType(1)->isPointerTy())
1283       return false;
1284     setDoesNotThrow(F);
1285     setDoesNotCapture(F, 1);
1286     setDoesNotCapture(F, 2);
1287     setOnlyReadsMemory(F, 2);
1288     break;
1289   case LibFunc::fgetpos:
1290     if (FTy->getNumParams() < 2 ||
1291         !FTy->getParamType(0)->isPointerTy() ||
1292         !FTy->getParamType(1)->isPointerTy())
1293       return false;
1294     setDoesNotThrow(F);
1295     setDoesNotCapture(F, 1);
1296     setDoesNotCapture(F, 2);
1297     break;
1298   case LibFunc::getc:
1299   case LibFunc::getlogin_r:
1300   case LibFunc::getc_unlocked:
1301     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1302       return false;
1303     setDoesNotThrow(F);
1304     setDoesNotCapture(F, 1);
1305     break;
1306   case LibFunc::getenv:
1307     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1308       return false;
1309     setDoesNotThrow(F);
1310     setOnlyReadsMemory(F);
1311     setDoesNotCapture(F, 1);
1312     break;
1313   case LibFunc::gets:
1314   case LibFunc::getchar:
1315     setDoesNotThrow(F);
1316     break;
1317   case LibFunc::getitimer:
1318     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1319       return false;
1320     setDoesNotThrow(F);
1321     setDoesNotCapture(F, 2);
1322     break;
1323   case LibFunc::getpwnam:
1324     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1325       return false;
1326     setDoesNotThrow(F);
1327     setDoesNotCapture(F, 1);
1328     setOnlyReadsMemory(F, 1);
1329     break;
1330   case LibFunc::ungetc:
1331     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1332       return false;
1333     setDoesNotThrow(F);
1334     setDoesNotCapture(F, 2);
1335     break;
1336   case LibFunc::uname:
1337     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1338       return false;
1339     setDoesNotThrow(F);
1340     setDoesNotCapture(F, 1);
1341     break;
1342   case LibFunc::unlink:
1343     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1344       return false;
1345     setDoesNotThrow(F);
1346     setDoesNotCapture(F, 1);
1347     setOnlyReadsMemory(F, 1);
1348     break;
1349   case LibFunc::unsetenv:
1350     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1351       return false;
1352     setDoesNotThrow(F);
1353     setDoesNotCapture(F, 1);
1354     setOnlyReadsMemory(F, 1);
1355     break;
1356   case LibFunc::utime:
1357   case LibFunc::utimes:
1358     if (FTy->getNumParams() != 2 ||
1359         !FTy->getParamType(0)->isPointerTy() ||
1360         !FTy->getParamType(1)->isPointerTy())
1361       return false;
1362     setDoesNotThrow(F);
1363     setDoesNotCapture(F, 1);
1364     setDoesNotCapture(F, 2);
1365     setOnlyReadsMemory(F, 1);
1366     setOnlyReadsMemory(F, 2);
1367     break;
1368   case LibFunc::putc:
1369     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1370       return false;
1371     setDoesNotThrow(F);
1372     setDoesNotCapture(F, 2);
1373     break;
1374   case LibFunc::puts:
1375   case LibFunc::printf:
1376   case LibFunc::perror:
1377     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1378       return false;
1379     setDoesNotThrow(F);
1380     setDoesNotCapture(F, 1);
1381     setOnlyReadsMemory(F, 1);
1382     break;
1383   case LibFunc::pread:
1384     if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
1385       return false;
1386     // May throw; "pread" is a valid pthread cancellation point.
1387     setDoesNotCapture(F, 2);
1388     break;
1389   case LibFunc::pwrite:
1390     if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
1391       return false;
1392     // May throw; "pwrite" is a valid pthread cancellation point.
1393     setDoesNotCapture(F, 2);
1394     setOnlyReadsMemory(F, 2);
1395     break;
1396   case LibFunc::putchar:
1397     setDoesNotThrow(F);
1398     break;
1399   case LibFunc::popen:
1400     if (FTy->getNumParams() != 2 ||
1401         !FTy->getReturnType()->isPointerTy() ||
1402         !FTy->getParamType(0)->isPointerTy() ||
1403         !FTy->getParamType(1)->isPointerTy())
1404       return false;
1405     setDoesNotThrow(F);
1406     setDoesNotAlias(F, 0);
1407     setDoesNotCapture(F, 1);
1408     setDoesNotCapture(F, 2);
1409     setOnlyReadsMemory(F, 1);
1410     setOnlyReadsMemory(F, 2);
1411     break;
1412   case LibFunc::pclose:
1413     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1414       return false;
1415     setDoesNotThrow(F);
1416     setDoesNotCapture(F, 1);
1417     break;
1418   case LibFunc::vscanf:
1419     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1420       return false;
1421     setDoesNotThrow(F);
1422     setDoesNotCapture(F, 1);
1423     setOnlyReadsMemory(F, 1);
1424     break;
1425   case LibFunc::vsscanf:
1426     if (FTy->getNumParams() != 3 ||
1427         !FTy->getParamType(1)->isPointerTy() ||
1428         !FTy->getParamType(2)->isPointerTy())
1429       return false;
1430     setDoesNotThrow(F);
1431     setDoesNotCapture(F, 1);
1432     setDoesNotCapture(F, 2);
1433     setOnlyReadsMemory(F, 1);
1434     setOnlyReadsMemory(F, 2);
1435     break;
1436   case LibFunc::vfscanf:
1437     if (FTy->getNumParams() != 3 ||
1438         !FTy->getParamType(1)->isPointerTy() ||
1439         !FTy->getParamType(2)->isPointerTy())
1440       return false;
1441     setDoesNotThrow(F);
1442     setDoesNotCapture(F, 1);
1443     setDoesNotCapture(F, 2);
1444     setOnlyReadsMemory(F, 2);
1445     break;
1446   case LibFunc::valloc:
1447     if (!FTy->getReturnType()->isPointerTy())
1448       return false;
1449     setDoesNotThrow(F);
1450     setDoesNotAlias(F, 0);
1451     break;
1452   case LibFunc::vprintf:
1453     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1454       return false;
1455     setDoesNotThrow(F);
1456     setDoesNotCapture(F, 1);
1457     setOnlyReadsMemory(F, 1);
1458     break;
1459   case LibFunc::vfprintf:
1460   case LibFunc::vsprintf:
1461     if (FTy->getNumParams() != 3 ||
1462         !FTy->getParamType(0)->isPointerTy() ||
1463         !FTy->getParamType(1)->isPointerTy())
1464       return false;
1465     setDoesNotThrow(F);
1466     setDoesNotCapture(F, 1);
1467     setDoesNotCapture(F, 2);
1468     setOnlyReadsMemory(F, 2);
1469     break;
1470   case LibFunc::vsnprintf:
1471     if (FTy->getNumParams() != 4 ||
1472         !FTy->getParamType(0)->isPointerTy() ||
1473         !FTy->getParamType(2)->isPointerTy())
1474       return false;
1475     setDoesNotThrow(F);
1476     setDoesNotCapture(F, 1);
1477     setDoesNotCapture(F, 3);
1478     setOnlyReadsMemory(F, 3);
1479     break;
1480   case LibFunc::open:
1481     if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
1482       return false;
1483     // May throw; "open" is a valid pthread cancellation point.
1484     setDoesNotCapture(F, 1);
1485     setOnlyReadsMemory(F, 1);
1486     break;
1487   case LibFunc::opendir:
1488     if (FTy->getNumParams() != 1 ||
1489         !FTy->getReturnType()->isPointerTy() ||
1490         !FTy->getParamType(0)->isPointerTy())
1491       return false;
1492     setDoesNotThrow(F);
1493     setDoesNotAlias(F, 0);
1494     setDoesNotCapture(F, 1);
1495     setOnlyReadsMemory(F, 1);
1496     break;
1497   case LibFunc::tmpfile:
1498     if (!FTy->getReturnType()->isPointerTy())
1499       return false;
1500     setDoesNotThrow(F);
1501     setDoesNotAlias(F, 0);
1502     break;
1503   case LibFunc::times:
1504     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1505       return false;
1506     setDoesNotThrow(F);
1507     setDoesNotCapture(F, 1);
1508     break;
1509   case LibFunc::htonl:
1510   case LibFunc::htons:
1511   case LibFunc::ntohl:
1512   case LibFunc::ntohs:
1513     setDoesNotThrow(F);
1514     setDoesNotAccessMemory(F);
1515     break;
1516   case LibFunc::lstat:
1517     if (FTy->getNumParams() != 2 ||
1518         !FTy->getParamType(0)->isPointerTy() ||
1519         !FTy->getParamType(1)->isPointerTy())
1520       return false;
1521     setDoesNotThrow(F);
1522     setDoesNotCapture(F, 1);
1523     setDoesNotCapture(F, 2);
1524     setOnlyReadsMemory(F, 1);
1525     break;
1526   case LibFunc::lchown:
1527     if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy())
1528       return false;
1529     setDoesNotThrow(F);
1530     setDoesNotCapture(F, 1);
1531     setOnlyReadsMemory(F, 1);
1532     break;
1533   case LibFunc::qsort:
1534     if (FTy->getNumParams() != 4 || !FTy->getParamType(3)->isPointerTy())
1535       return false;
1536     // May throw; places call through function pointer.
1537     setDoesNotCapture(F, 4);
1538     break;
1539   case LibFunc::dunder_strdup:
1540   case LibFunc::dunder_strndup:
1541     if (FTy->getNumParams() < 1 ||
1542         !FTy->getReturnType()->isPointerTy() ||
1543         !FTy->getParamType(0)->isPointerTy())
1544       return false;
1545     setDoesNotThrow(F);
1546     setDoesNotAlias(F, 0);
1547     setDoesNotCapture(F, 1);
1548     setOnlyReadsMemory(F, 1);
1549     break;
1550   case LibFunc::dunder_strtok_r:
1551     if (FTy->getNumParams() != 3 ||
1552         !FTy->getParamType(1)->isPointerTy())
1553       return false;
1554     setDoesNotThrow(F);
1555     setDoesNotCapture(F, 2);
1556     setOnlyReadsMemory(F, 2);
1557     break;
1558   case LibFunc::under_IO_getc:
1559     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1560       return false;
1561     setDoesNotThrow(F);
1562     setDoesNotCapture(F, 1);
1563     break;
1564   case LibFunc::under_IO_putc:
1565     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1566       return false;
1567     setDoesNotThrow(F);
1568     setDoesNotCapture(F, 2);
1569     break;
1570   case LibFunc::dunder_isoc99_scanf:
1571     if (FTy->getNumParams() < 1 ||
1572         !FTy->getParamType(0)->isPointerTy())
1573       return false;
1574     setDoesNotThrow(F);
1575     setDoesNotCapture(F, 1);
1576     setOnlyReadsMemory(F, 1);
1577     break;
1578   case LibFunc::stat64:
1579   case LibFunc::lstat64:
1580   case LibFunc::statvfs64:
1581     if (FTy->getNumParams() < 1 ||
1582         !FTy->getParamType(0)->isPointerTy() ||
1583         !FTy->getParamType(1)->isPointerTy())
1584       return false;
1585     setDoesNotThrow(F);
1586     setDoesNotCapture(F, 1);
1587     setDoesNotCapture(F, 2);
1588     setOnlyReadsMemory(F, 1);
1589     break;
1590   case LibFunc::dunder_isoc99_sscanf:
1591     if (FTy->getNumParams() < 1 ||
1592         !FTy->getParamType(0)->isPointerTy() ||
1593         !FTy->getParamType(1)->isPointerTy())
1594       return false;
1595     setDoesNotThrow(F);
1596     setDoesNotCapture(F, 1);
1597     setDoesNotCapture(F, 2);
1598     setOnlyReadsMemory(F, 1);
1599     setOnlyReadsMemory(F, 2);
1600     break;
1601   case LibFunc::fopen64:
1602     if (FTy->getNumParams() != 2 ||
1603         !FTy->getReturnType()->isPointerTy() ||
1604         !FTy->getParamType(0)->isPointerTy() ||
1605         !FTy->getParamType(1)->isPointerTy())
1606       return false;
1607     setDoesNotThrow(F);
1608     setDoesNotAlias(F, 0);
1609     setDoesNotCapture(F, 1);
1610     setDoesNotCapture(F, 2);
1611     setOnlyReadsMemory(F, 1);
1612     setOnlyReadsMemory(F, 2);
1613     break;
1614   case LibFunc::fseeko64:
1615   case LibFunc::ftello64:
1616     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1617       return false;
1618     setDoesNotThrow(F);
1619     setDoesNotCapture(F, 1);
1620     break;
1621   case LibFunc::tmpfile64:
1622     if (!FTy->getReturnType()->isPointerTy())
1623       return false;
1624     setDoesNotThrow(F);
1625     setDoesNotAlias(F, 0);
1626     break;
1627   case LibFunc::fstat64:
1628   case LibFunc::fstatvfs64:
1629     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1630       return false;
1631     setDoesNotThrow(F);
1632     setDoesNotCapture(F, 2);
1633     break;
1634   case LibFunc::open64:
1635     if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
1636       return false;
1637     // May throw; "open" is a valid pthread cancellation point.
1638     setDoesNotCapture(F, 1);
1639     setOnlyReadsMemory(F, 1);
1640     break;
1641   case LibFunc::gettimeofday:
1642     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
1643         !FTy->getParamType(1)->isPointerTy())
1644       return false;
1645     // Currently some platforms have the restrict keyword on the arguments to
1646     // gettimeofday. To be conservative, do not add noalias to gettimeofday's
1647     // arguments.
1648     setDoesNotThrow(F);
1649     setDoesNotCapture(F, 1);
1650     setDoesNotCapture(F, 2);
1651   default:
1652     // Didn't mark any attributes.
1653     return false;
1654   }
1655 
1656   return true;
1657 }
1658 
1659 /// annotateLibraryCalls - Adds attributes to well-known standard library
1660 /// call declarations.
1661 bool FunctionAttrs::annotateLibraryCalls(const CallGraphSCC &SCC) {
1662   bool MadeChange = false;
1663 
1664   // Check each function in turn annotating well-known library function
1665   // declarations with attributes.
1666   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
1667     Function *F = (*I)->getFunction();
1668 
1669     if (F != 0 && F->isDeclaration())
1670       MadeChange |= inferPrototypeAttributes(*F);
1671   }
1672 
1673   return MadeChange;
1674 }
1675 
1676 bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) {
1677   AA = &getAnalysis<AliasAnalysis>();
1678   TLI = &getAnalysis<TargetLibraryInfo>();
1679 
1680   bool Changed = annotateLibraryCalls(SCC);
1681   Changed |= AddReadAttrs(SCC);
1682   Changed |= AddArgumentAttrs(SCC);
1683   Changed |= AddNoAliasAttrs(SCC);
1684   return Changed;
1685 }
1686