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_PASS_DEPENDENCY(CallGraphWrapperPass)
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       (void)Found;
371       return false;
372     }
373 
374     bool Captured;  // True only if certainly captured (used outside our SCC).
375     SmallVector<Argument*, 4> Uses;  // Uses within our SCC.
376 
377     const SmallPtrSet<Function*, 8> &SCCNodes;
378   };
379 }
380 
381 namespace llvm {
382   template<> struct GraphTraits<ArgumentGraphNode*> {
383     typedef ArgumentGraphNode NodeType;
384     typedef SmallVectorImpl<ArgumentGraphNode*>::iterator ChildIteratorType;
385 
386     static inline NodeType *getEntryNode(NodeType *A) { return A; }
387     static inline ChildIteratorType child_begin(NodeType *N) {
388       return N->Uses.begin();
389     }
390     static inline ChildIteratorType child_end(NodeType *N) {
391       return N->Uses.end();
392     }
393   };
394   template<> struct GraphTraits<ArgumentGraph*>
395     : public GraphTraits<ArgumentGraphNode*> {
396     static NodeType *getEntryNode(ArgumentGraph *AG) {
397       return AG->getEntryNode();
398     }
399     static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
400       return AG->begin();
401     }
402     static ChildIteratorType nodes_end(ArgumentGraph *AG) {
403       return AG->end();
404     }
405   };
406 }
407 
408 // Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
409 static Attribute::AttrKind
410 determinePointerReadAttrs(Argument *A,
411                           const SmallPtrSet<Argument*, 8> &SCCNodes) {
412 
413   SmallVector<Use*, 32> Worklist;
414   SmallSet<Use*, 32> Visited;
415   int Count = 0;
416 
417   // inalloca arguments are always clobbered by the call.
418   if (A->hasInAllocaAttr())
419     return Attribute::None;
420 
421   bool IsRead = false;
422   // We don't need to track IsWritten. If A is written to, return immediately.
423 
424   for (Value::use_iterator UI = A->use_begin(), UE = A->use_end();
425        UI != UE; ++UI) {
426     if (Count++ >= 20)
427       return Attribute::None;
428 
429     Use *U = &UI.getUse();
430     Visited.insert(U);
431     Worklist.push_back(U);
432   }
433 
434   while (!Worklist.empty()) {
435     Use *U = Worklist.pop_back_val();
436     Instruction *I = cast<Instruction>(U->getUser());
437     Value *V = U->get();
438 
439     switch (I->getOpcode()) {
440     case Instruction::BitCast:
441     case Instruction::GetElementPtr:
442     case Instruction::PHI:
443     case Instruction::Select:
444     case Instruction::AddrSpaceCast:
445       // The original value is not read/written via this if the new value isn't.
446       for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end();
447            UI != UE; ++UI) {
448         Use *U = &UI.getUse();
449         if (Visited.insert(U))
450           Worklist.push_back(U);
451       }
452       break;
453 
454     case Instruction::Call:
455     case Instruction::Invoke: {
456       CallSite CS(I);
457       if (CS.doesNotAccessMemory())
458         continue;
459 
460       Function *F = CS.getCalledFunction();
461       if (!F) {
462         if (CS.onlyReadsMemory()) {
463           IsRead = true;
464           continue;
465         }
466         return Attribute::None;
467       }
468 
469       Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end();
470       CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end();
471       for (CallSite::arg_iterator A = B; A != E; ++A, ++AI) {
472         if (A->get() == V) {
473           if (AI == AE) {
474             assert(F->isVarArg() &&
475                    "More params than args in non-varargs call.");
476             return Attribute::None;
477           }
478           if (SCCNodes.count(AI))
479             continue;
480           if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(A - B))
481             return Attribute::None;
482           if (!CS.doesNotAccessMemory(A - B))
483             IsRead = true;
484         }
485       }
486       break;
487     }
488 
489     case Instruction::Load:
490       IsRead = true;
491       break;
492 
493     case Instruction::ICmp:
494     case Instruction::Ret:
495       break;
496 
497     default:
498       return Attribute::None;
499     }
500   }
501 
502   return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
503 }
504 
505 /// AddArgumentAttrs - Deduce nocapture attributes for the SCC.
506 bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) {
507   bool Changed = false;
508 
509   SmallPtrSet<Function*, 8> SCCNodes;
510 
511   // Fill SCCNodes with the elements of the SCC.  Used for quickly
512   // looking up whether a given CallGraphNode is in this SCC.
513   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
514     Function *F = (*I)->getFunction();
515     if (F && !F->isDeclaration() && !F->mayBeOverridden())
516       SCCNodes.insert(F);
517   }
518 
519   ArgumentGraph AG;
520 
521   AttrBuilder B;
522   B.addAttribute(Attribute::NoCapture);
523 
524   // Check each function in turn, determining which pointer arguments are not
525   // captured.
526   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
527     Function *F = (*I)->getFunction();
528 
529     if (F == 0)
530       // External node - only a problem for arguments that we pass to it.
531       continue;
532 
533     // Definitions with weak linkage may be overridden at linktime with
534     // something that captures pointers, so treat them like declarations.
535     if (F->isDeclaration() || F->mayBeOverridden())
536       continue;
537 
538     // Functions that are readonly (or readnone) and nounwind and don't return
539     // a value can't capture arguments. Don't analyze them.
540     if (F->onlyReadsMemory() && F->doesNotThrow() &&
541         F->getReturnType()->isVoidTy()) {
542       for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end();
543            A != E; ++A) {
544         if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
545           A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
546           ++NumNoCapture;
547           Changed = true;
548         }
549       }
550       continue;
551     }
552 
553     for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end();
554          A != E; ++A) {
555       if (!A->getType()->isPointerTy()) continue;
556       bool HasNonLocalUses = false;
557       if (!A->hasNoCaptureAttr()) {
558         ArgumentUsesTracker Tracker(SCCNodes);
559         PointerMayBeCaptured(A, &Tracker);
560         if (!Tracker.Captured) {
561           if (Tracker.Uses.empty()) {
562             // If it's trivially not captured, mark it nocapture now.
563             A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo()+1, B));
564             ++NumNoCapture;
565             Changed = true;
566           } else {
567             // If it's not trivially captured and not trivially not captured,
568             // then it must be calling into another function in our SCC. Save
569             // its particulars for Argument-SCC analysis later.
570             ArgumentGraphNode *Node = AG[A];
571             for (SmallVectorImpl<Argument*>::iterator UI = Tracker.Uses.begin(),
572                      UE = Tracker.Uses.end(); UI != UE; ++UI) {
573               Node->Uses.push_back(AG[*UI]);
574               if (*UI != A)
575                 HasNonLocalUses = true;
576             }
577           }
578         }
579         // Otherwise, it's captured. Don't bother doing SCC analysis on it.
580       }
581       if (!HasNonLocalUses && !A->onlyReadsMemory()) {
582         // Can we determine that it's readonly/readnone without doing an SCC?
583         // Note that we don't allow any calls at all here, or else our result
584         // will be dependent on the iteration order through the functions in the
585         // SCC.
586         SmallPtrSet<Argument*, 8> Self;
587         Self.insert(A);
588         Attribute::AttrKind R = determinePointerReadAttrs(A, Self);
589         if (R != Attribute::None) {
590           AttrBuilder B;
591           B.addAttribute(R);
592           A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
593           Changed = true;
594           R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
595         }
596       }
597     }
598   }
599 
600   // The graph we've collected is partial because we stopped scanning for
601   // argument uses once we solved the argument trivially. These partial nodes
602   // show up as ArgumentGraphNode objects with an empty Uses list, and for
603   // these nodes the final decision about whether they capture has already been
604   // made.  If the definition doesn't have a 'nocapture' attribute by now, it
605   // captures.
606 
607   for (scc_iterator<ArgumentGraph*> I = scc_begin(&AG), E = scc_end(&AG);
608        I != E; ++I) {
609     std::vector<ArgumentGraphNode*> &ArgumentSCC = *I;
610     if (ArgumentSCC.size() == 1) {
611       if (!ArgumentSCC[0]->Definition) continue;  // synthetic root node
612 
613       // eg. "void f(int* x) { if (...) f(x); }"
614       if (ArgumentSCC[0]->Uses.size() == 1 &&
615           ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
616         Argument *A = ArgumentSCC[0]->Definition;
617         A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
618         ++NumNoCapture;
619         Changed = true;
620       }
621       continue;
622     }
623 
624     bool SCCCaptured = false;
625     for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(),
626            E = ArgumentSCC.end(); I != E && !SCCCaptured; ++I) {
627       ArgumentGraphNode *Node = *I;
628       if (Node->Uses.empty()) {
629         if (!Node->Definition->hasNoCaptureAttr())
630           SCCCaptured = true;
631       }
632     }
633     if (SCCCaptured) continue;
634 
635     SmallPtrSet<Argument*, 8> ArgumentSCCNodes;
636     // Fill ArgumentSCCNodes with the elements of the ArgumentSCC.  Used for
637     // quickly looking up whether a given Argument is in this ArgumentSCC.
638     for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(),
639            E = ArgumentSCC.end(); I != E; ++I) {
640       ArgumentSCCNodes.insert((*I)->Definition);
641     }
642 
643     for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(),
644            E = ArgumentSCC.end(); I != E && !SCCCaptured; ++I) {
645       ArgumentGraphNode *N = *I;
646       for (SmallVectorImpl<ArgumentGraphNode*>::iterator UI = N->Uses.begin(),
647              UE = N->Uses.end(); UI != UE; ++UI) {
648         Argument *A = (*UI)->Definition;
649         if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
650           continue;
651         SCCCaptured = true;
652         break;
653       }
654     }
655     if (SCCCaptured) continue;
656 
657     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
658       Argument *A = ArgumentSCC[i]->Definition;
659       A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
660       ++NumNoCapture;
661       Changed = true;
662     }
663 
664     // We also want to compute readonly/readnone. With a small number of false
665     // negatives, we can assume that any pointer which is captured isn't going
666     // to be provably readonly or readnone, since by definition we can't
667     // analyze all uses of a captured pointer.
668     //
669     // The false negatives happen when the pointer is captured by a function
670     // that promises readonly/readnone behaviour on the pointer, then the
671     // pointer's lifetime ends before anything that writes to arbitrary memory.
672     // Also, a readonly/readnone pointer may be returned, but returning a
673     // pointer is capturing it.
674 
675     Attribute::AttrKind ReadAttr = Attribute::ReadNone;
676     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
677       Argument *A = ArgumentSCC[i]->Definition;
678       Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes);
679       if (K == Attribute::ReadNone)
680         continue;
681       if (K == Attribute::ReadOnly) {
682         ReadAttr = Attribute::ReadOnly;
683         continue;
684       }
685       ReadAttr = K;
686       break;
687     }
688 
689     if (ReadAttr != Attribute::None) {
690       AttrBuilder B;
691       B.addAttribute(ReadAttr);
692       for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
693         Argument *A = ArgumentSCC[i]->Definition;
694         A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
695         ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
696         Changed = true;
697       }
698     }
699   }
700 
701   return Changed;
702 }
703 
704 /// IsFunctionMallocLike - A function is malloc-like if it returns either null
705 /// or a pointer that doesn't alias any other pointer visible to the caller.
706 bool FunctionAttrs::IsFunctionMallocLike(Function *F,
707                               SmallPtrSet<Function*, 8> &SCCNodes) const {
708   SmallSetVector<Value *, 8> FlowsToReturn;
709   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
710     if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator()))
711       FlowsToReturn.insert(Ret->getReturnValue());
712 
713   for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
714     Value *RetVal = FlowsToReturn[i];
715 
716     if (Constant *C = dyn_cast<Constant>(RetVal)) {
717       if (!C->isNullValue() && !isa<UndefValue>(C))
718         return false;
719 
720       continue;
721     }
722 
723     if (isa<Argument>(RetVal))
724       return false;
725 
726     if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
727       switch (RVI->getOpcode()) {
728         // Extend the analysis by looking upwards.
729         case Instruction::BitCast:
730         case Instruction::GetElementPtr:
731         case Instruction::AddrSpaceCast:
732           FlowsToReturn.insert(RVI->getOperand(0));
733           continue;
734         case Instruction::Select: {
735           SelectInst *SI = cast<SelectInst>(RVI);
736           FlowsToReturn.insert(SI->getTrueValue());
737           FlowsToReturn.insert(SI->getFalseValue());
738           continue;
739         }
740         case Instruction::PHI: {
741           PHINode *PN = cast<PHINode>(RVI);
742           for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
743             FlowsToReturn.insert(PN->getIncomingValue(i));
744           continue;
745         }
746 
747         // Check whether the pointer came from an allocation.
748         case Instruction::Alloca:
749           break;
750         case Instruction::Call:
751         case Instruction::Invoke: {
752           CallSite CS(RVI);
753           if (CS.paramHasAttr(0, Attribute::NoAlias))
754             break;
755           if (CS.getCalledFunction() &&
756               SCCNodes.count(CS.getCalledFunction()))
757             break;
758         } // fall-through
759         default:
760           return false;  // Did not come from an allocation.
761       }
762 
763     if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
764       return false;
765   }
766 
767   return true;
768 }
769 
770 /// AddNoAliasAttrs - Deduce noalias attributes for the SCC.
771 bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) {
772   SmallPtrSet<Function*, 8> SCCNodes;
773 
774   // Fill SCCNodes with the elements of the SCC.  Used for quickly
775   // looking up whether a given CallGraphNode is in this SCC.
776   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
777     SCCNodes.insert((*I)->getFunction());
778 
779   // Check each function in turn, determining which functions return noalias
780   // pointers.
781   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
782     Function *F = (*I)->getFunction();
783 
784     if (F == 0)
785       // External node - skip it;
786       return false;
787 
788     // Already noalias.
789     if (F->doesNotAlias(0))
790       continue;
791 
792     // Definitions with weak linkage may be overridden at linktime, so
793     // treat them like declarations.
794     if (F->isDeclaration() || F->mayBeOverridden())
795       return false;
796 
797     // We annotate noalias return values, which are only applicable to
798     // pointer types.
799     if (!F->getReturnType()->isPointerTy())
800       continue;
801 
802     if (!IsFunctionMallocLike(F, SCCNodes))
803       return false;
804   }
805 
806   bool MadeChange = false;
807   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
808     Function *F = (*I)->getFunction();
809     if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy())
810       continue;
811 
812     F->setDoesNotAlias(0);
813     ++NumNoAlias;
814     MadeChange = true;
815   }
816 
817   return MadeChange;
818 }
819 
820 /// inferPrototypeAttributes - Analyze the name and prototype of the
821 /// given function and set any applicable attributes.  Returns true
822 /// if any attributes were set and false otherwise.
823 bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
824   FunctionType *FTy = F.getFunctionType();
825   LibFunc::Func TheLibFunc;
826   if (!(TLI->getLibFunc(F.getName(), TheLibFunc) && TLI->has(TheLibFunc)))
827     return false;
828 
829   switch (TheLibFunc) {
830   case LibFunc::strlen:
831     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
832       return false;
833     setOnlyReadsMemory(F);
834     setDoesNotThrow(F);
835     setDoesNotCapture(F, 1);
836     break;
837   case LibFunc::strchr:
838   case LibFunc::strrchr:
839     if (FTy->getNumParams() != 2 ||
840         !FTy->getParamType(0)->isPointerTy() ||
841         !FTy->getParamType(1)->isIntegerTy())
842       return false;
843     setOnlyReadsMemory(F);
844     setDoesNotThrow(F);
845     break;
846   case LibFunc::strtol:
847   case LibFunc::strtod:
848   case LibFunc::strtof:
849   case LibFunc::strtoul:
850   case LibFunc::strtoll:
851   case LibFunc::strtold:
852   case LibFunc::strtoull:
853     if (FTy->getNumParams() < 2 ||
854         !FTy->getParamType(1)->isPointerTy())
855       return false;
856     setDoesNotThrow(F);
857     setDoesNotCapture(F, 2);
858     setOnlyReadsMemory(F, 1);
859     break;
860   case LibFunc::strcpy:
861   case LibFunc::stpcpy:
862   case LibFunc::strcat:
863   case LibFunc::strncat:
864   case LibFunc::strncpy:
865   case LibFunc::stpncpy:
866     if (FTy->getNumParams() < 2 ||
867         !FTy->getParamType(1)->isPointerTy())
868       return false;
869     setDoesNotThrow(F);
870     setDoesNotCapture(F, 2);
871     setOnlyReadsMemory(F, 2);
872     break;
873   case LibFunc::strxfrm:
874     if (FTy->getNumParams() != 3 ||
875         !FTy->getParamType(0)->isPointerTy() ||
876         !FTy->getParamType(1)->isPointerTy())
877       return false;
878     setDoesNotThrow(F);
879     setDoesNotCapture(F, 1);
880     setDoesNotCapture(F, 2);
881     setOnlyReadsMemory(F, 2);
882     break;
883   case LibFunc::strcmp: //0,1
884     case LibFunc::strspn: // 0,1
885     case LibFunc::strncmp: // 0,1
886     case LibFunc::strcspn: //0,1
887     case LibFunc::strcoll: //0,1
888     case LibFunc::strcasecmp:  // 0,1
889     case LibFunc::strncasecmp: //
890     if (FTy->getNumParams() < 2 ||
891         !FTy->getParamType(0)->isPointerTy() ||
892         !FTy->getParamType(1)->isPointerTy())
893       return false;
894     setOnlyReadsMemory(F);
895     setDoesNotThrow(F);
896     setDoesNotCapture(F, 1);
897     setDoesNotCapture(F, 2);
898     break;
899   case LibFunc::strstr:
900   case LibFunc::strpbrk:
901     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
902       return false;
903     setOnlyReadsMemory(F);
904     setDoesNotThrow(F);
905     setDoesNotCapture(F, 2);
906     break;
907   case LibFunc::strtok:
908   case LibFunc::strtok_r:
909     if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
910       return false;
911     setDoesNotThrow(F);
912     setDoesNotCapture(F, 2);
913     setOnlyReadsMemory(F, 2);
914     break;
915   case LibFunc::scanf:
916     if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
917       return false;
918     setDoesNotThrow(F);
919     setDoesNotCapture(F, 1);
920     setOnlyReadsMemory(F, 1);
921     break;
922   case LibFunc::setbuf:
923   case LibFunc::setvbuf:
924     if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
925       return false;
926     setDoesNotThrow(F);
927     setDoesNotCapture(F, 1);
928     break;
929   case LibFunc::strdup:
930   case LibFunc::strndup:
931     if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() ||
932         !FTy->getParamType(0)->isPointerTy())
933       return false;
934     setDoesNotThrow(F);
935     setDoesNotAlias(F, 0);
936     setDoesNotCapture(F, 1);
937     setOnlyReadsMemory(F, 1);
938     break;
939   case LibFunc::stat:
940   case LibFunc::statvfs:
941     if (FTy->getNumParams() < 2 ||
942         !FTy->getParamType(0)->isPointerTy() ||
943         !FTy->getParamType(1)->isPointerTy())
944       return false;
945     setDoesNotThrow(F);
946     setDoesNotCapture(F, 1);
947     setDoesNotCapture(F, 2);
948     setOnlyReadsMemory(F, 1);
949     break;
950   case LibFunc::sscanf:
951     if (FTy->getNumParams() < 2 ||
952         !FTy->getParamType(0)->isPointerTy() ||
953         !FTy->getParamType(1)->isPointerTy())
954       return false;
955     setDoesNotThrow(F);
956     setDoesNotCapture(F, 1);
957     setDoesNotCapture(F, 2);
958     setOnlyReadsMemory(F, 1);
959     setOnlyReadsMemory(F, 2);
960     break;
961   case LibFunc::sprintf:
962     if (FTy->getNumParams() < 2 ||
963         !FTy->getParamType(0)->isPointerTy() ||
964         !FTy->getParamType(1)->isPointerTy())
965       return false;
966     setDoesNotThrow(F);
967     setDoesNotCapture(F, 1);
968     setDoesNotCapture(F, 2);
969     setOnlyReadsMemory(F, 2);
970     break;
971   case LibFunc::snprintf:
972     if (FTy->getNumParams() != 3 ||
973         !FTy->getParamType(0)->isPointerTy() ||
974         !FTy->getParamType(2)->isPointerTy())
975       return false;
976     setDoesNotThrow(F);
977     setDoesNotCapture(F, 1);
978     setDoesNotCapture(F, 3);
979     setOnlyReadsMemory(F, 3);
980     break;
981   case LibFunc::setitimer:
982     if (FTy->getNumParams() != 3 ||
983         !FTy->getParamType(1)->isPointerTy() ||
984         !FTy->getParamType(2)->isPointerTy())
985       return false;
986     setDoesNotThrow(F);
987     setDoesNotCapture(F, 2);
988     setDoesNotCapture(F, 3);
989     setOnlyReadsMemory(F, 2);
990     break;
991   case LibFunc::system:
992     if (FTy->getNumParams() != 1 ||
993         !FTy->getParamType(0)->isPointerTy())
994       return false;
995     // May throw; "system" is a valid pthread cancellation point.
996     setDoesNotCapture(F, 1);
997     setOnlyReadsMemory(F, 1);
998     break;
999   case LibFunc::malloc:
1000     if (FTy->getNumParams() != 1 ||
1001         !FTy->getReturnType()->isPointerTy())
1002       return false;
1003     setDoesNotThrow(F);
1004     setDoesNotAlias(F, 0);
1005     break;
1006   case LibFunc::memcmp:
1007     if (FTy->getNumParams() != 3 ||
1008         !FTy->getParamType(0)->isPointerTy() ||
1009         !FTy->getParamType(1)->isPointerTy())
1010       return false;
1011     setOnlyReadsMemory(F);
1012     setDoesNotThrow(F);
1013     setDoesNotCapture(F, 1);
1014     setDoesNotCapture(F, 2);
1015     break;
1016   case LibFunc::memchr:
1017   case LibFunc::memrchr:
1018     if (FTy->getNumParams() != 3)
1019       return false;
1020     setOnlyReadsMemory(F);
1021     setDoesNotThrow(F);
1022     break;
1023   case LibFunc::modf:
1024   case LibFunc::modff:
1025   case LibFunc::modfl:
1026     if (FTy->getNumParams() < 2 ||
1027         !FTy->getParamType(1)->isPointerTy())
1028       return false;
1029     setDoesNotThrow(F);
1030     setDoesNotCapture(F, 2);
1031     break;
1032   case LibFunc::memcpy:
1033   case LibFunc::memccpy:
1034   case LibFunc::memmove:
1035     if (FTy->getNumParams() < 2 ||
1036         !FTy->getParamType(1)->isPointerTy())
1037       return false;
1038     setDoesNotThrow(F);
1039     setDoesNotCapture(F, 2);
1040     setOnlyReadsMemory(F, 2);
1041     break;
1042   case LibFunc::memalign:
1043     if (!FTy->getReturnType()->isPointerTy())
1044       return false;
1045     setDoesNotAlias(F, 0);
1046     break;
1047   case LibFunc::mkdir:
1048     if (FTy->getNumParams() == 0 ||
1049         !FTy->getParamType(0)->isPointerTy())
1050       return false;
1051     setDoesNotThrow(F);
1052     setDoesNotCapture(F, 1);
1053     setOnlyReadsMemory(F, 1);
1054     break;
1055   case LibFunc::mktime:
1056     if (FTy->getNumParams() == 0 ||
1057         !FTy->getParamType(0)->isPointerTy())
1058       return false;
1059     setDoesNotThrow(F);
1060     setDoesNotCapture(F, 1);
1061     break;
1062   case LibFunc::realloc:
1063     if (FTy->getNumParams() != 2 ||
1064         !FTy->getParamType(0)->isPointerTy() ||
1065         !FTy->getReturnType()->isPointerTy())
1066       return false;
1067     setDoesNotThrow(F);
1068     setDoesNotAlias(F, 0);
1069     setDoesNotCapture(F, 1);
1070     break;
1071   case LibFunc::read:
1072     if (FTy->getNumParams() != 3 ||
1073         !FTy->getParamType(1)->isPointerTy())
1074       return false;
1075     // May throw; "read" is a valid pthread cancellation point.
1076     setDoesNotCapture(F, 2);
1077     break;
1078   case LibFunc::rewind:
1079     if (FTy->getNumParams() < 1 ||
1080         !FTy->getParamType(0)->isPointerTy())
1081       return false;
1082     setDoesNotThrow(F);
1083     setDoesNotCapture(F, 1);
1084     break;
1085   case LibFunc::rmdir:
1086   case LibFunc::remove:
1087   case LibFunc::realpath:
1088     if (FTy->getNumParams() < 1 ||
1089         !FTy->getParamType(0)->isPointerTy())
1090       return false;
1091     setDoesNotThrow(F);
1092     setDoesNotCapture(F, 1);
1093     setOnlyReadsMemory(F, 1);
1094     break;
1095   case LibFunc::rename:
1096     if (FTy->getNumParams() < 2 ||
1097         !FTy->getParamType(0)->isPointerTy() ||
1098         !FTy->getParamType(1)->isPointerTy())
1099       return false;
1100     setDoesNotThrow(F);
1101     setDoesNotCapture(F, 1);
1102     setDoesNotCapture(F, 2);
1103     setOnlyReadsMemory(F, 1);
1104     setOnlyReadsMemory(F, 2);
1105     break;
1106   case LibFunc::readlink:
1107     if (FTy->getNumParams() < 2 ||
1108         !FTy->getParamType(0)->isPointerTy() ||
1109         !FTy->getParamType(1)->isPointerTy())
1110       return false;
1111     setDoesNotThrow(F);
1112     setDoesNotCapture(F, 1);
1113     setDoesNotCapture(F, 2);
1114     setOnlyReadsMemory(F, 1);
1115     break;
1116   case LibFunc::write:
1117     if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
1118       return false;
1119     // May throw; "write" is a valid pthread cancellation point.
1120     setDoesNotCapture(F, 2);
1121     setOnlyReadsMemory(F, 2);
1122     break;
1123   case LibFunc::bcopy:
1124     if (FTy->getNumParams() != 3 ||
1125         !FTy->getParamType(0)->isPointerTy() ||
1126         !FTy->getParamType(1)->isPointerTy())
1127       return false;
1128     setDoesNotThrow(F);
1129     setDoesNotCapture(F, 1);
1130     setDoesNotCapture(F, 2);
1131     setOnlyReadsMemory(F, 1);
1132     break;
1133   case LibFunc::bcmp:
1134     if (FTy->getNumParams() != 3 ||
1135         !FTy->getParamType(0)->isPointerTy() ||
1136         !FTy->getParamType(1)->isPointerTy())
1137       return false;
1138     setDoesNotThrow(F);
1139     setOnlyReadsMemory(F);
1140     setDoesNotCapture(F, 1);
1141     setDoesNotCapture(F, 2);
1142     break;
1143   case LibFunc::bzero:
1144     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1145       return false;
1146     setDoesNotThrow(F);
1147     setDoesNotCapture(F, 1);
1148     break;
1149   case LibFunc::calloc:
1150     if (FTy->getNumParams() != 2 ||
1151         !FTy->getReturnType()->isPointerTy())
1152       return false;
1153     setDoesNotThrow(F);
1154     setDoesNotAlias(F, 0);
1155     break;
1156   case LibFunc::chmod:
1157   case LibFunc::chown:
1158     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1159       return false;
1160     setDoesNotThrow(F);
1161     setDoesNotCapture(F, 1);
1162     setOnlyReadsMemory(F, 1);
1163     break;
1164   case LibFunc::ctermid:
1165   case LibFunc::clearerr:
1166   case LibFunc::closedir:
1167     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1168       return false;
1169     setDoesNotThrow(F);
1170     setDoesNotCapture(F, 1);
1171     break;
1172   case LibFunc::atoi:
1173   case LibFunc::atol:
1174   case LibFunc::atof:
1175   case LibFunc::atoll:
1176     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1177       return false;
1178     setDoesNotThrow(F);
1179     setOnlyReadsMemory(F);
1180     setDoesNotCapture(F, 1);
1181     break;
1182   case LibFunc::access:
1183     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1184       return false;
1185     setDoesNotThrow(F);
1186     setDoesNotCapture(F, 1);
1187     setOnlyReadsMemory(F, 1);
1188     break;
1189   case LibFunc::fopen:
1190     if (FTy->getNumParams() != 2 ||
1191         !FTy->getReturnType()->isPointerTy() ||
1192         !FTy->getParamType(0)->isPointerTy() ||
1193         !FTy->getParamType(1)->isPointerTy())
1194       return false;
1195     setDoesNotThrow(F);
1196     setDoesNotAlias(F, 0);
1197     setDoesNotCapture(F, 1);
1198     setDoesNotCapture(F, 2);
1199     setOnlyReadsMemory(F, 1);
1200     setOnlyReadsMemory(F, 2);
1201     break;
1202   case LibFunc::fdopen:
1203     if (FTy->getNumParams() != 2 ||
1204         !FTy->getReturnType()->isPointerTy() ||
1205         !FTy->getParamType(1)->isPointerTy())
1206       return false;
1207     setDoesNotThrow(F);
1208     setDoesNotAlias(F, 0);
1209     setDoesNotCapture(F, 2);
1210     setOnlyReadsMemory(F, 2);
1211     break;
1212   case LibFunc::feof:
1213   case LibFunc::free:
1214   case LibFunc::fseek:
1215   case LibFunc::ftell:
1216   case LibFunc::fgetc:
1217   case LibFunc::fseeko:
1218   case LibFunc::ftello:
1219   case LibFunc::fileno:
1220   case LibFunc::fflush:
1221   case LibFunc::fclose:
1222   case LibFunc::fsetpos:
1223   case LibFunc::flockfile:
1224   case LibFunc::funlockfile:
1225   case LibFunc::ftrylockfile:
1226     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1227       return false;
1228     setDoesNotThrow(F);
1229     setDoesNotCapture(F, 1);
1230     break;
1231   case LibFunc::ferror:
1232     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1233       return false;
1234     setDoesNotThrow(F);
1235     setDoesNotCapture(F, 1);
1236     setOnlyReadsMemory(F);
1237     break;
1238   case LibFunc::fputc:
1239   case LibFunc::fstat:
1240   case LibFunc::frexp:
1241   case LibFunc::frexpf:
1242   case LibFunc::frexpl:
1243   case LibFunc::fstatvfs:
1244     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1245       return false;
1246     setDoesNotThrow(F);
1247     setDoesNotCapture(F, 2);
1248     break;
1249   case LibFunc::fgets:
1250     if (FTy->getNumParams() != 3 ||
1251         !FTy->getParamType(0)->isPointerTy() ||
1252         !FTy->getParamType(2)->isPointerTy())
1253       return false;
1254     setDoesNotThrow(F);
1255     setDoesNotCapture(F, 3);
1256     break;
1257   case LibFunc::fread:
1258     if (FTy->getNumParams() != 4 ||
1259         !FTy->getParamType(0)->isPointerTy() ||
1260         !FTy->getParamType(3)->isPointerTy())
1261       return false;
1262     setDoesNotThrow(F);
1263     setDoesNotCapture(F, 1);
1264     setDoesNotCapture(F, 4);
1265     break;
1266   case LibFunc::fwrite:
1267     if (FTy->getNumParams() != 4 ||
1268         !FTy->getParamType(0)->isPointerTy() ||
1269         !FTy->getParamType(3)->isPointerTy())
1270       return false;
1271     setDoesNotThrow(F);
1272     setDoesNotCapture(F, 1);
1273     setDoesNotCapture(F, 4);
1274     break;
1275   case LibFunc::fputs:
1276     if (FTy->getNumParams() < 2 ||
1277         !FTy->getParamType(0)->isPointerTy() ||
1278         !FTy->getParamType(1)->isPointerTy())
1279       return false;
1280     setDoesNotThrow(F);
1281     setDoesNotCapture(F, 1);
1282     setDoesNotCapture(F, 2);
1283     setOnlyReadsMemory(F, 1);
1284     break;
1285   case LibFunc::fscanf:
1286   case LibFunc::fprintf:
1287     if (FTy->getNumParams() < 2 ||
1288         !FTy->getParamType(0)->isPointerTy() ||
1289         !FTy->getParamType(1)->isPointerTy())
1290       return false;
1291     setDoesNotThrow(F);
1292     setDoesNotCapture(F, 1);
1293     setDoesNotCapture(F, 2);
1294     setOnlyReadsMemory(F, 2);
1295     break;
1296   case LibFunc::fgetpos:
1297     if (FTy->getNumParams() < 2 ||
1298         !FTy->getParamType(0)->isPointerTy() ||
1299         !FTy->getParamType(1)->isPointerTy())
1300       return false;
1301     setDoesNotThrow(F);
1302     setDoesNotCapture(F, 1);
1303     setDoesNotCapture(F, 2);
1304     break;
1305   case LibFunc::getc:
1306   case LibFunc::getlogin_r:
1307   case LibFunc::getc_unlocked:
1308     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1309       return false;
1310     setDoesNotThrow(F);
1311     setDoesNotCapture(F, 1);
1312     break;
1313   case LibFunc::getenv:
1314     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1315       return false;
1316     setDoesNotThrow(F);
1317     setOnlyReadsMemory(F);
1318     setDoesNotCapture(F, 1);
1319     break;
1320   case LibFunc::gets:
1321   case LibFunc::getchar:
1322     setDoesNotThrow(F);
1323     break;
1324   case LibFunc::getitimer:
1325     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1326       return false;
1327     setDoesNotThrow(F);
1328     setDoesNotCapture(F, 2);
1329     break;
1330   case LibFunc::getpwnam:
1331     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1332       return false;
1333     setDoesNotThrow(F);
1334     setDoesNotCapture(F, 1);
1335     setOnlyReadsMemory(F, 1);
1336     break;
1337   case LibFunc::ungetc:
1338     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1339       return false;
1340     setDoesNotThrow(F);
1341     setDoesNotCapture(F, 2);
1342     break;
1343   case LibFunc::uname:
1344     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1345       return false;
1346     setDoesNotThrow(F);
1347     setDoesNotCapture(F, 1);
1348     break;
1349   case LibFunc::unlink:
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::unsetenv:
1357     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1358       return false;
1359     setDoesNotThrow(F);
1360     setDoesNotCapture(F, 1);
1361     setOnlyReadsMemory(F, 1);
1362     break;
1363   case LibFunc::utime:
1364   case LibFunc::utimes:
1365     if (FTy->getNumParams() != 2 ||
1366         !FTy->getParamType(0)->isPointerTy() ||
1367         !FTy->getParamType(1)->isPointerTy())
1368       return false;
1369     setDoesNotThrow(F);
1370     setDoesNotCapture(F, 1);
1371     setDoesNotCapture(F, 2);
1372     setOnlyReadsMemory(F, 1);
1373     setOnlyReadsMemory(F, 2);
1374     break;
1375   case LibFunc::putc:
1376     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1377       return false;
1378     setDoesNotThrow(F);
1379     setDoesNotCapture(F, 2);
1380     break;
1381   case LibFunc::puts:
1382   case LibFunc::printf:
1383   case LibFunc::perror:
1384     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1385       return false;
1386     setDoesNotThrow(F);
1387     setDoesNotCapture(F, 1);
1388     setOnlyReadsMemory(F, 1);
1389     break;
1390   case LibFunc::pread:
1391     if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
1392       return false;
1393     // May throw; "pread" is a valid pthread cancellation point.
1394     setDoesNotCapture(F, 2);
1395     break;
1396   case LibFunc::pwrite:
1397     if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
1398       return false;
1399     // May throw; "pwrite" is a valid pthread cancellation point.
1400     setDoesNotCapture(F, 2);
1401     setOnlyReadsMemory(F, 2);
1402     break;
1403   case LibFunc::putchar:
1404     setDoesNotThrow(F);
1405     break;
1406   case LibFunc::popen:
1407     if (FTy->getNumParams() != 2 ||
1408         !FTy->getReturnType()->isPointerTy() ||
1409         !FTy->getParamType(0)->isPointerTy() ||
1410         !FTy->getParamType(1)->isPointerTy())
1411       return false;
1412     setDoesNotThrow(F);
1413     setDoesNotAlias(F, 0);
1414     setDoesNotCapture(F, 1);
1415     setDoesNotCapture(F, 2);
1416     setOnlyReadsMemory(F, 1);
1417     setOnlyReadsMemory(F, 2);
1418     break;
1419   case LibFunc::pclose:
1420     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1421       return false;
1422     setDoesNotThrow(F);
1423     setDoesNotCapture(F, 1);
1424     break;
1425   case LibFunc::vscanf:
1426     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1427       return false;
1428     setDoesNotThrow(F);
1429     setDoesNotCapture(F, 1);
1430     setOnlyReadsMemory(F, 1);
1431     break;
1432   case LibFunc::vsscanf:
1433     if (FTy->getNumParams() != 3 ||
1434         !FTy->getParamType(1)->isPointerTy() ||
1435         !FTy->getParamType(2)->isPointerTy())
1436       return false;
1437     setDoesNotThrow(F);
1438     setDoesNotCapture(F, 1);
1439     setDoesNotCapture(F, 2);
1440     setOnlyReadsMemory(F, 1);
1441     setOnlyReadsMemory(F, 2);
1442     break;
1443   case LibFunc::vfscanf:
1444     if (FTy->getNumParams() != 3 ||
1445         !FTy->getParamType(1)->isPointerTy() ||
1446         !FTy->getParamType(2)->isPointerTy())
1447       return false;
1448     setDoesNotThrow(F);
1449     setDoesNotCapture(F, 1);
1450     setDoesNotCapture(F, 2);
1451     setOnlyReadsMemory(F, 2);
1452     break;
1453   case LibFunc::valloc:
1454     if (!FTy->getReturnType()->isPointerTy())
1455       return false;
1456     setDoesNotThrow(F);
1457     setDoesNotAlias(F, 0);
1458     break;
1459   case LibFunc::vprintf:
1460     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1461       return false;
1462     setDoesNotThrow(F);
1463     setDoesNotCapture(F, 1);
1464     setOnlyReadsMemory(F, 1);
1465     break;
1466   case LibFunc::vfprintf:
1467   case LibFunc::vsprintf:
1468     if (FTy->getNumParams() != 3 ||
1469         !FTy->getParamType(0)->isPointerTy() ||
1470         !FTy->getParamType(1)->isPointerTy())
1471       return false;
1472     setDoesNotThrow(F);
1473     setDoesNotCapture(F, 1);
1474     setDoesNotCapture(F, 2);
1475     setOnlyReadsMemory(F, 2);
1476     break;
1477   case LibFunc::vsnprintf:
1478     if (FTy->getNumParams() != 4 ||
1479         !FTy->getParamType(0)->isPointerTy() ||
1480         !FTy->getParamType(2)->isPointerTy())
1481       return false;
1482     setDoesNotThrow(F);
1483     setDoesNotCapture(F, 1);
1484     setDoesNotCapture(F, 3);
1485     setOnlyReadsMemory(F, 3);
1486     break;
1487   case LibFunc::open:
1488     if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
1489       return false;
1490     // May throw; "open" is a valid pthread cancellation point.
1491     setDoesNotCapture(F, 1);
1492     setOnlyReadsMemory(F, 1);
1493     break;
1494   case LibFunc::opendir:
1495     if (FTy->getNumParams() != 1 ||
1496         !FTy->getReturnType()->isPointerTy() ||
1497         !FTy->getParamType(0)->isPointerTy())
1498       return false;
1499     setDoesNotThrow(F);
1500     setDoesNotAlias(F, 0);
1501     setDoesNotCapture(F, 1);
1502     setOnlyReadsMemory(F, 1);
1503     break;
1504   case LibFunc::tmpfile:
1505     if (!FTy->getReturnType()->isPointerTy())
1506       return false;
1507     setDoesNotThrow(F);
1508     setDoesNotAlias(F, 0);
1509     break;
1510   case LibFunc::times:
1511     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1512       return false;
1513     setDoesNotThrow(F);
1514     setDoesNotCapture(F, 1);
1515     break;
1516   case LibFunc::htonl:
1517   case LibFunc::htons:
1518   case LibFunc::ntohl:
1519   case LibFunc::ntohs:
1520     setDoesNotThrow(F);
1521     setDoesNotAccessMemory(F);
1522     break;
1523   case LibFunc::lstat:
1524     if (FTy->getNumParams() != 2 ||
1525         !FTy->getParamType(0)->isPointerTy() ||
1526         !FTy->getParamType(1)->isPointerTy())
1527       return false;
1528     setDoesNotThrow(F);
1529     setDoesNotCapture(F, 1);
1530     setDoesNotCapture(F, 2);
1531     setOnlyReadsMemory(F, 1);
1532     break;
1533   case LibFunc::lchown:
1534     if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy())
1535       return false;
1536     setDoesNotThrow(F);
1537     setDoesNotCapture(F, 1);
1538     setOnlyReadsMemory(F, 1);
1539     break;
1540   case LibFunc::qsort:
1541     if (FTy->getNumParams() != 4 || !FTy->getParamType(3)->isPointerTy())
1542       return false;
1543     // May throw; places call through function pointer.
1544     setDoesNotCapture(F, 4);
1545     break;
1546   case LibFunc::dunder_strdup:
1547   case LibFunc::dunder_strndup:
1548     if (FTy->getNumParams() < 1 ||
1549         !FTy->getReturnType()->isPointerTy() ||
1550         !FTy->getParamType(0)->isPointerTy())
1551       return false;
1552     setDoesNotThrow(F);
1553     setDoesNotAlias(F, 0);
1554     setDoesNotCapture(F, 1);
1555     setOnlyReadsMemory(F, 1);
1556     break;
1557   case LibFunc::dunder_strtok_r:
1558     if (FTy->getNumParams() != 3 ||
1559         !FTy->getParamType(1)->isPointerTy())
1560       return false;
1561     setDoesNotThrow(F);
1562     setDoesNotCapture(F, 2);
1563     setOnlyReadsMemory(F, 2);
1564     break;
1565   case LibFunc::under_IO_getc:
1566     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1567       return false;
1568     setDoesNotThrow(F);
1569     setDoesNotCapture(F, 1);
1570     break;
1571   case LibFunc::under_IO_putc:
1572     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1573       return false;
1574     setDoesNotThrow(F);
1575     setDoesNotCapture(F, 2);
1576     break;
1577   case LibFunc::dunder_isoc99_scanf:
1578     if (FTy->getNumParams() < 1 ||
1579         !FTy->getParamType(0)->isPointerTy())
1580       return false;
1581     setDoesNotThrow(F);
1582     setDoesNotCapture(F, 1);
1583     setOnlyReadsMemory(F, 1);
1584     break;
1585   case LibFunc::stat64:
1586   case LibFunc::lstat64:
1587   case LibFunc::statvfs64:
1588     if (FTy->getNumParams() < 1 ||
1589         !FTy->getParamType(0)->isPointerTy() ||
1590         !FTy->getParamType(1)->isPointerTy())
1591       return false;
1592     setDoesNotThrow(F);
1593     setDoesNotCapture(F, 1);
1594     setDoesNotCapture(F, 2);
1595     setOnlyReadsMemory(F, 1);
1596     break;
1597   case LibFunc::dunder_isoc99_sscanf:
1598     if (FTy->getNumParams() < 1 ||
1599         !FTy->getParamType(0)->isPointerTy() ||
1600         !FTy->getParamType(1)->isPointerTy())
1601       return false;
1602     setDoesNotThrow(F);
1603     setDoesNotCapture(F, 1);
1604     setDoesNotCapture(F, 2);
1605     setOnlyReadsMemory(F, 1);
1606     setOnlyReadsMemory(F, 2);
1607     break;
1608   case LibFunc::fopen64:
1609     if (FTy->getNumParams() != 2 ||
1610         !FTy->getReturnType()->isPointerTy() ||
1611         !FTy->getParamType(0)->isPointerTy() ||
1612         !FTy->getParamType(1)->isPointerTy())
1613       return false;
1614     setDoesNotThrow(F);
1615     setDoesNotAlias(F, 0);
1616     setDoesNotCapture(F, 1);
1617     setDoesNotCapture(F, 2);
1618     setOnlyReadsMemory(F, 1);
1619     setOnlyReadsMemory(F, 2);
1620     break;
1621   case LibFunc::fseeko64:
1622   case LibFunc::ftello64:
1623     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1624       return false;
1625     setDoesNotThrow(F);
1626     setDoesNotCapture(F, 1);
1627     break;
1628   case LibFunc::tmpfile64:
1629     if (!FTy->getReturnType()->isPointerTy())
1630       return false;
1631     setDoesNotThrow(F);
1632     setDoesNotAlias(F, 0);
1633     break;
1634   case LibFunc::fstat64:
1635   case LibFunc::fstatvfs64:
1636     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1637       return false;
1638     setDoesNotThrow(F);
1639     setDoesNotCapture(F, 2);
1640     break;
1641   case LibFunc::open64:
1642     if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
1643       return false;
1644     // May throw; "open" is a valid pthread cancellation point.
1645     setDoesNotCapture(F, 1);
1646     setOnlyReadsMemory(F, 1);
1647     break;
1648   case LibFunc::gettimeofday:
1649     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
1650         !FTy->getParamType(1)->isPointerTy())
1651       return false;
1652     // Currently some platforms have the restrict keyword on the arguments to
1653     // gettimeofday. To be conservative, do not add noalias to gettimeofday's
1654     // arguments.
1655     setDoesNotThrow(F);
1656     setDoesNotCapture(F, 1);
1657     setDoesNotCapture(F, 2);
1658   default:
1659     // Didn't mark any attributes.
1660     return false;
1661   }
1662 
1663   return true;
1664 }
1665 
1666 /// annotateLibraryCalls - Adds attributes to well-known standard library
1667 /// call declarations.
1668 bool FunctionAttrs::annotateLibraryCalls(const CallGraphSCC &SCC) {
1669   bool MadeChange = false;
1670 
1671   // Check each function in turn annotating well-known library function
1672   // declarations with attributes.
1673   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
1674     Function *F = (*I)->getFunction();
1675 
1676     if (F != 0 && F->isDeclaration())
1677       MadeChange |= inferPrototypeAttributes(*F);
1678   }
1679 
1680   return MadeChange;
1681 }
1682 
1683 bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) {
1684   AA = &getAnalysis<AliasAnalysis>();
1685   TLI = &getAnalysis<TargetLibraryInfo>();
1686 
1687   bool Changed = annotateLibraryCalls(SCC);
1688   Changed |= AddReadAttrs(SCC);
1689   Changed |= AddArgumentAttrs(SCC);
1690   Changed |= AddNoAliasAttrs(SCC);
1691   return Changed;
1692 }
1693