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); !I.isAtEnd(); ++I) {
608     std::vector<ArgumentGraphNode*> &ArgumentSCC = *I;
609     if (ArgumentSCC.size() == 1) {
610       if (!ArgumentSCC[0]->Definition) continue;  // synthetic root node
611 
612       // eg. "void f(int* x) { if (...) f(x); }"
613       if (ArgumentSCC[0]->Uses.size() == 1 &&
614           ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
615         Argument *A = ArgumentSCC[0]->Definition;
616         A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
617         ++NumNoCapture;
618         Changed = true;
619       }
620       continue;
621     }
622 
623     bool SCCCaptured = false;
624     for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(),
625            E = ArgumentSCC.end(); I != E && !SCCCaptured; ++I) {
626       ArgumentGraphNode *Node = *I;
627       if (Node->Uses.empty()) {
628         if (!Node->Definition->hasNoCaptureAttr())
629           SCCCaptured = true;
630       }
631     }
632     if (SCCCaptured) continue;
633 
634     SmallPtrSet<Argument*, 8> ArgumentSCCNodes;
635     // Fill ArgumentSCCNodes with the elements of the ArgumentSCC.  Used for
636     // quickly looking up whether a given Argument is in this ArgumentSCC.
637     for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(),
638            E = ArgumentSCC.end(); I != E; ++I) {
639       ArgumentSCCNodes.insert((*I)->Definition);
640     }
641 
642     for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(),
643            E = ArgumentSCC.end(); I != E && !SCCCaptured; ++I) {
644       ArgumentGraphNode *N = *I;
645       for (SmallVectorImpl<ArgumentGraphNode*>::iterator UI = N->Uses.begin(),
646              UE = N->Uses.end(); UI != UE; ++UI) {
647         Argument *A = (*UI)->Definition;
648         if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
649           continue;
650         SCCCaptured = true;
651         break;
652       }
653     }
654     if (SCCCaptured) continue;
655 
656     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
657       Argument *A = ArgumentSCC[i]->Definition;
658       A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
659       ++NumNoCapture;
660       Changed = true;
661     }
662 
663     // We also want to compute readonly/readnone. With a small number of false
664     // negatives, we can assume that any pointer which is captured isn't going
665     // to be provably readonly or readnone, since by definition we can't
666     // analyze all uses of a captured pointer.
667     //
668     // The false negatives happen when the pointer is captured by a function
669     // that promises readonly/readnone behaviour on the pointer, then the
670     // pointer's lifetime ends before anything that writes to arbitrary memory.
671     // Also, a readonly/readnone pointer may be returned, but returning a
672     // pointer is capturing it.
673 
674     Attribute::AttrKind ReadAttr = Attribute::ReadNone;
675     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
676       Argument *A = ArgumentSCC[i]->Definition;
677       Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes);
678       if (K == Attribute::ReadNone)
679         continue;
680       if (K == Attribute::ReadOnly) {
681         ReadAttr = Attribute::ReadOnly;
682         continue;
683       }
684       ReadAttr = K;
685       break;
686     }
687 
688     if (ReadAttr != Attribute::None) {
689       AttrBuilder B;
690       B.addAttribute(ReadAttr);
691       for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
692         Argument *A = ArgumentSCC[i]->Definition;
693         A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
694         ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
695         Changed = true;
696       }
697     }
698   }
699 
700   return Changed;
701 }
702 
703 /// IsFunctionMallocLike - A function is malloc-like if it returns either null
704 /// or a pointer that doesn't alias any other pointer visible to the caller.
705 bool FunctionAttrs::IsFunctionMallocLike(Function *F,
706                               SmallPtrSet<Function*, 8> &SCCNodes) const {
707   SmallSetVector<Value *, 8> FlowsToReturn;
708   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
709     if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator()))
710       FlowsToReturn.insert(Ret->getReturnValue());
711 
712   for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
713     Value *RetVal = FlowsToReturn[i];
714 
715     if (Constant *C = dyn_cast<Constant>(RetVal)) {
716       if (!C->isNullValue() && !isa<UndefValue>(C))
717         return false;
718 
719       continue;
720     }
721 
722     if (isa<Argument>(RetVal))
723       return false;
724 
725     if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
726       switch (RVI->getOpcode()) {
727         // Extend the analysis by looking upwards.
728         case Instruction::BitCast:
729         case Instruction::GetElementPtr:
730         case Instruction::AddrSpaceCast:
731           FlowsToReturn.insert(RVI->getOperand(0));
732           continue;
733         case Instruction::Select: {
734           SelectInst *SI = cast<SelectInst>(RVI);
735           FlowsToReturn.insert(SI->getTrueValue());
736           FlowsToReturn.insert(SI->getFalseValue());
737           continue;
738         }
739         case Instruction::PHI: {
740           PHINode *PN = cast<PHINode>(RVI);
741           for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
742             FlowsToReturn.insert(PN->getIncomingValue(i));
743           continue;
744         }
745 
746         // Check whether the pointer came from an allocation.
747         case Instruction::Alloca:
748           break;
749         case Instruction::Call:
750         case Instruction::Invoke: {
751           CallSite CS(RVI);
752           if (CS.paramHasAttr(0, Attribute::NoAlias))
753             break;
754           if (CS.getCalledFunction() &&
755               SCCNodes.count(CS.getCalledFunction()))
756             break;
757         } // fall-through
758         default:
759           return false;  // Did not come from an allocation.
760       }
761 
762     if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
763       return false;
764   }
765 
766   return true;
767 }
768 
769 /// AddNoAliasAttrs - Deduce noalias attributes for the SCC.
770 bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) {
771   SmallPtrSet<Function*, 8> SCCNodes;
772 
773   // Fill SCCNodes with the elements of the SCC.  Used for quickly
774   // looking up whether a given CallGraphNode is in this SCC.
775   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
776     SCCNodes.insert((*I)->getFunction());
777 
778   // Check each function in turn, determining which functions return noalias
779   // pointers.
780   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
781     Function *F = (*I)->getFunction();
782 
783     if (F == 0)
784       // External node - skip it;
785       return false;
786 
787     // Already noalias.
788     if (F->doesNotAlias(0))
789       continue;
790 
791     // Definitions with weak linkage may be overridden at linktime, so
792     // treat them like declarations.
793     if (F->isDeclaration() || F->mayBeOverridden())
794       return false;
795 
796     // We annotate noalias return values, which are only applicable to
797     // pointer types.
798     if (!F->getReturnType()->isPointerTy())
799       continue;
800 
801     if (!IsFunctionMallocLike(F, SCCNodes))
802       return false;
803   }
804 
805   bool MadeChange = false;
806   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
807     Function *F = (*I)->getFunction();
808     if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy())
809       continue;
810 
811     F->setDoesNotAlias(0);
812     ++NumNoAlias;
813     MadeChange = true;
814   }
815 
816   return MadeChange;
817 }
818 
819 /// inferPrototypeAttributes - Analyze the name and prototype of the
820 /// given function and set any applicable attributes.  Returns true
821 /// if any attributes were set and false otherwise.
822 bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
823   FunctionType *FTy = F.getFunctionType();
824   LibFunc::Func TheLibFunc;
825   if (!(TLI->getLibFunc(F.getName(), TheLibFunc) && TLI->has(TheLibFunc)))
826     return false;
827 
828   switch (TheLibFunc) {
829   case LibFunc::strlen:
830     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
831       return false;
832     setOnlyReadsMemory(F);
833     setDoesNotThrow(F);
834     setDoesNotCapture(F, 1);
835     break;
836   case LibFunc::strchr:
837   case LibFunc::strrchr:
838     if (FTy->getNumParams() != 2 ||
839         !FTy->getParamType(0)->isPointerTy() ||
840         !FTy->getParamType(1)->isIntegerTy())
841       return false;
842     setOnlyReadsMemory(F);
843     setDoesNotThrow(F);
844     break;
845   case LibFunc::strtol:
846   case LibFunc::strtod:
847   case LibFunc::strtof:
848   case LibFunc::strtoul:
849   case LibFunc::strtoll:
850   case LibFunc::strtold:
851   case LibFunc::strtoull:
852     if (FTy->getNumParams() < 2 ||
853         !FTy->getParamType(1)->isPointerTy())
854       return false;
855     setDoesNotThrow(F);
856     setDoesNotCapture(F, 2);
857     setOnlyReadsMemory(F, 1);
858     break;
859   case LibFunc::strcpy:
860   case LibFunc::stpcpy:
861   case LibFunc::strcat:
862   case LibFunc::strncat:
863   case LibFunc::strncpy:
864   case LibFunc::stpncpy:
865     if (FTy->getNumParams() < 2 ||
866         !FTy->getParamType(1)->isPointerTy())
867       return false;
868     setDoesNotThrow(F);
869     setDoesNotCapture(F, 2);
870     setOnlyReadsMemory(F, 2);
871     break;
872   case LibFunc::strxfrm:
873     if (FTy->getNumParams() != 3 ||
874         !FTy->getParamType(0)->isPointerTy() ||
875         !FTy->getParamType(1)->isPointerTy())
876       return false;
877     setDoesNotThrow(F);
878     setDoesNotCapture(F, 1);
879     setDoesNotCapture(F, 2);
880     setOnlyReadsMemory(F, 2);
881     break;
882   case LibFunc::strcmp: //0,1
883     case LibFunc::strspn: // 0,1
884     case LibFunc::strncmp: // 0,1
885     case LibFunc::strcspn: //0,1
886     case LibFunc::strcoll: //0,1
887     case LibFunc::strcasecmp:  // 0,1
888     case LibFunc::strncasecmp: //
889     if (FTy->getNumParams() < 2 ||
890         !FTy->getParamType(0)->isPointerTy() ||
891         !FTy->getParamType(1)->isPointerTy())
892       return false;
893     setOnlyReadsMemory(F);
894     setDoesNotThrow(F);
895     setDoesNotCapture(F, 1);
896     setDoesNotCapture(F, 2);
897     break;
898   case LibFunc::strstr:
899   case LibFunc::strpbrk:
900     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
901       return false;
902     setOnlyReadsMemory(F);
903     setDoesNotThrow(F);
904     setDoesNotCapture(F, 2);
905     break;
906   case LibFunc::strtok:
907   case LibFunc::strtok_r:
908     if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
909       return false;
910     setDoesNotThrow(F);
911     setDoesNotCapture(F, 2);
912     setOnlyReadsMemory(F, 2);
913     break;
914   case LibFunc::scanf:
915     if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
916       return false;
917     setDoesNotThrow(F);
918     setDoesNotCapture(F, 1);
919     setOnlyReadsMemory(F, 1);
920     break;
921   case LibFunc::setbuf:
922   case LibFunc::setvbuf:
923     if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
924       return false;
925     setDoesNotThrow(F);
926     setDoesNotCapture(F, 1);
927     break;
928   case LibFunc::strdup:
929   case LibFunc::strndup:
930     if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() ||
931         !FTy->getParamType(0)->isPointerTy())
932       return false;
933     setDoesNotThrow(F);
934     setDoesNotAlias(F, 0);
935     setDoesNotCapture(F, 1);
936     setOnlyReadsMemory(F, 1);
937     break;
938   case LibFunc::stat:
939   case LibFunc::statvfs:
940     if (FTy->getNumParams() < 2 ||
941         !FTy->getParamType(0)->isPointerTy() ||
942         !FTy->getParamType(1)->isPointerTy())
943       return false;
944     setDoesNotThrow(F);
945     setDoesNotCapture(F, 1);
946     setDoesNotCapture(F, 2);
947     setOnlyReadsMemory(F, 1);
948     break;
949   case LibFunc::sscanf:
950     if (FTy->getNumParams() < 2 ||
951         !FTy->getParamType(0)->isPointerTy() ||
952         !FTy->getParamType(1)->isPointerTy())
953       return false;
954     setDoesNotThrow(F);
955     setDoesNotCapture(F, 1);
956     setDoesNotCapture(F, 2);
957     setOnlyReadsMemory(F, 1);
958     setOnlyReadsMemory(F, 2);
959     break;
960   case LibFunc::sprintf:
961     if (FTy->getNumParams() < 2 ||
962         !FTy->getParamType(0)->isPointerTy() ||
963         !FTy->getParamType(1)->isPointerTy())
964       return false;
965     setDoesNotThrow(F);
966     setDoesNotCapture(F, 1);
967     setDoesNotCapture(F, 2);
968     setOnlyReadsMemory(F, 2);
969     break;
970   case LibFunc::snprintf:
971     if (FTy->getNumParams() != 3 ||
972         !FTy->getParamType(0)->isPointerTy() ||
973         !FTy->getParamType(2)->isPointerTy())
974       return false;
975     setDoesNotThrow(F);
976     setDoesNotCapture(F, 1);
977     setDoesNotCapture(F, 3);
978     setOnlyReadsMemory(F, 3);
979     break;
980   case LibFunc::setitimer:
981     if (FTy->getNumParams() != 3 ||
982         !FTy->getParamType(1)->isPointerTy() ||
983         !FTy->getParamType(2)->isPointerTy())
984       return false;
985     setDoesNotThrow(F);
986     setDoesNotCapture(F, 2);
987     setDoesNotCapture(F, 3);
988     setOnlyReadsMemory(F, 2);
989     break;
990   case LibFunc::system:
991     if (FTy->getNumParams() != 1 ||
992         !FTy->getParamType(0)->isPointerTy())
993       return false;
994     // May throw; "system" is a valid pthread cancellation point.
995     setDoesNotCapture(F, 1);
996     setOnlyReadsMemory(F, 1);
997     break;
998   case LibFunc::malloc:
999     if (FTy->getNumParams() != 1 ||
1000         !FTy->getReturnType()->isPointerTy())
1001       return false;
1002     setDoesNotThrow(F);
1003     setDoesNotAlias(F, 0);
1004     break;
1005   case LibFunc::memcmp:
1006     if (FTy->getNumParams() != 3 ||
1007         !FTy->getParamType(0)->isPointerTy() ||
1008         !FTy->getParamType(1)->isPointerTy())
1009       return false;
1010     setOnlyReadsMemory(F);
1011     setDoesNotThrow(F);
1012     setDoesNotCapture(F, 1);
1013     setDoesNotCapture(F, 2);
1014     break;
1015   case LibFunc::memchr:
1016   case LibFunc::memrchr:
1017     if (FTy->getNumParams() != 3)
1018       return false;
1019     setOnlyReadsMemory(F);
1020     setDoesNotThrow(F);
1021     break;
1022   case LibFunc::modf:
1023   case LibFunc::modff:
1024   case LibFunc::modfl:
1025     if (FTy->getNumParams() < 2 ||
1026         !FTy->getParamType(1)->isPointerTy())
1027       return false;
1028     setDoesNotThrow(F);
1029     setDoesNotCapture(F, 2);
1030     break;
1031   case LibFunc::memcpy:
1032   case LibFunc::memccpy:
1033   case LibFunc::memmove:
1034     if (FTy->getNumParams() < 2 ||
1035         !FTy->getParamType(1)->isPointerTy())
1036       return false;
1037     setDoesNotThrow(F);
1038     setDoesNotCapture(F, 2);
1039     setOnlyReadsMemory(F, 2);
1040     break;
1041   case LibFunc::memalign:
1042     if (!FTy->getReturnType()->isPointerTy())
1043       return false;
1044     setDoesNotAlias(F, 0);
1045     break;
1046   case LibFunc::mkdir:
1047     if (FTy->getNumParams() == 0 ||
1048         !FTy->getParamType(0)->isPointerTy())
1049       return false;
1050     setDoesNotThrow(F);
1051     setDoesNotCapture(F, 1);
1052     setOnlyReadsMemory(F, 1);
1053     break;
1054   case LibFunc::mktime:
1055     if (FTy->getNumParams() == 0 ||
1056         !FTy->getParamType(0)->isPointerTy())
1057       return false;
1058     setDoesNotThrow(F);
1059     setDoesNotCapture(F, 1);
1060     break;
1061   case LibFunc::realloc:
1062     if (FTy->getNumParams() != 2 ||
1063         !FTy->getParamType(0)->isPointerTy() ||
1064         !FTy->getReturnType()->isPointerTy())
1065       return false;
1066     setDoesNotThrow(F);
1067     setDoesNotAlias(F, 0);
1068     setDoesNotCapture(F, 1);
1069     break;
1070   case LibFunc::read:
1071     if (FTy->getNumParams() != 3 ||
1072         !FTy->getParamType(1)->isPointerTy())
1073       return false;
1074     // May throw; "read" is a valid pthread cancellation point.
1075     setDoesNotCapture(F, 2);
1076     break;
1077   case LibFunc::rewind:
1078     if (FTy->getNumParams() < 1 ||
1079         !FTy->getParamType(0)->isPointerTy())
1080       return false;
1081     setDoesNotThrow(F);
1082     setDoesNotCapture(F, 1);
1083     break;
1084   case LibFunc::rmdir:
1085   case LibFunc::remove:
1086   case LibFunc::realpath:
1087     if (FTy->getNumParams() < 1 ||
1088         !FTy->getParamType(0)->isPointerTy())
1089       return false;
1090     setDoesNotThrow(F);
1091     setDoesNotCapture(F, 1);
1092     setOnlyReadsMemory(F, 1);
1093     break;
1094   case LibFunc::rename:
1095     if (FTy->getNumParams() < 2 ||
1096         !FTy->getParamType(0)->isPointerTy() ||
1097         !FTy->getParamType(1)->isPointerTy())
1098       return false;
1099     setDoesNotThrow(F);
1100     setDoesNotCapture(F, 1);
1101     setDoesNotCapture(F, 2);
1102     setOnlyReadsMemory(F, 1);
1103     setOnlyReadsMemory(F, 2);
1104     break;
1105   case LibFunc::readlink:
1106     if (FTy->getNumParams() < 2 ||
1107         !FTy->getParamType(0)->isPointerTy() ||
1108         !FTy->getParamType(1)->isPointerTy())
1109       return false;
1110     setDoesNotThrow(F);
1111     setDoesNotCapture(F, 1);
1112     setDoesNotCapture(F, 2);
1113     setOnlyReadsMemory(F, 1);
1114     break;
1115   case LibFunc::write:
1116     if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
1117       return false;
1118     // May throw; "write" is a valid pthread cancellation point.
1119     setDoesNotCapture(F, 2);
1120     setOnlyReadsMemory(F, 2);
1121     break;
1122   case LibFunc::bcopy:
1123     if (FTy->getNumParams() != 3 ||
1124         !FTy->getParamType(0)->isPointerTy() ||
1125         !FTy->getParamType(1)->isPointerTy())
1126       return false;
1127     setDoesNotThrow(F);
1128     setDoesNotCapture(F, 1);
1129     setDoesNotCapture(F, 2);
1130     setOnlyReadsMemory(F, 1);
1131     break;
1132   case LibFunc::bcmp:
1133     if (FTy->getNumParams() != 3 ||
1134         !FTy->getParamType(0)->isPointerTy() ||
1135         !FTy->getParamType(1)->isPointerTy())
1136       return false;
1137     setDoesNotThrow(F);
1138     setOnlyReadsMemory(F);
1139     setDoesNotCapture(F, 1);
1140     setDoesNotCapture(F, 2);
1141     break;
1142   case LibFunc::bzero:
1143     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1144       return false;
1145     setDoesNotThrow(F);
1146     setDoesNotCapture(F, 1);
1147     break;
1148   case LibFunc::calloc:
1149     if (FTy->getNumParams() != 2 ||
1150         !FTy->getReturnType()->isPointerTy())
1151       return false;
1152     setDoesNotThrow(F);
1153     setDoesNotAlias(F, 0);
1154     break;
1155   case LibFunc::chmod:
1156   case LibFunc::chown:
1157     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1158       return false;
1159     setDoesNotThrow(F);
1160     setDoesNotCapture(F, 1);
1161     setOnlyReadsMemory(F, 1);
1162     break;
1163   case LibFunc::ctermid:
1164   case LibFunc::clearerr:
1165   case LibFunc::closedir:
1166     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1167       return false;
1168     setDoesNotThrow(F);
1169     setDoesNotCapture(F, 1);
1170     break;
1171   case LibFunc::atoi:
1172   case LibFunc::atol:
1173   case LibFunc::atof:
1174   case LibFunc::atoll:
1175     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1176       return false;
1177     setDoesNotThrow(F);
1178     setOnlyReadsMemory(F);
1179     setDoesNotCapture(F, 1);
1180     break;
1181   case LibFunc::access:
1182     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1183       return false;
1184     setDoesNotThrow(F);
1185     setDoesNotCapture(F, 1);
1186     setOnlyReadsMemory(F, 1);
1187     break;
1188   case LibFunc::fopen:
1189     if (FTy->getNumParams() != 2 ||
1190         !FTy->getReturnType()->isPointerTy() ||
1191         !FTy->getParamType(0)->isPointerTy() ||
1192         !FTy->getParamType(1)->isPointerTy())
1193       return false;
1194     setDoesNotThrow(F);
1195     setDoesNotAlias(F, 0);
1196     setDoesNotCapture(F, 1);
1197     setDoesNotCapture(F, 2);
1198     setOnlyReadsMemory(F, 1);
1199     setOnlyReadsMemory(F, 2);
1200     break;
1201   case LibFunc::fdopen:
1202     if (FTy->getNumParams() != 2 ||
1203         !FTy->getReturnType()->isPointerTy() ||
1204         !FTy->getParamType(1)->isPointerTy())
1205       return false;
1206     setDoesNotThrow(F);
1207     setDoesNotAlias(F, 0);
1208     setDoesNotCapture(F, 2);
1209     setOnlyReadsMemory(F, 2);
1210     break;
1211   case LibFunc::feof:
1212   case LibFunc::free:
1213   case LibFunc::fseek:
1214   case LibFunc::ftell:
1215   case LibFunc::fgetc:
1216   case LibFunc::fseeko:
1217   case LibFunc::ftello:
1218   case LibFunc::fileno:
1219   case LibFunc::fflush:
1220   case LibFunc::fclose:
1221   case LibFunc::fsetpos:
1222   case LibFunc::flockfile:
1223   case LibFunc::funlockfile:
1224   case LibFunc::ftrylockfile:
1225     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1226       return false;
1227     setDoesNotThrow(F);
1228     setDoesNotCapture(F, 1);
1229     break;
1230   case LibFunc::ferror:
1231     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1232       return false;
1233     setDoesNotThrow(F);
1234     setDoesNotCapture(F, 1);
1235     setOnlyReadsMemory(F);
1236     break;
1237   case LibFunc::fputc:
1238   case LibFunc::fstat:
1239   case LibFunc::frexp:
1240   case LibFunc::frexpf:
1241   case LibFunc::frexpl:
1242   case LibFunc::fstatvfs:
1243     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1244       return false;
1245     setDoesNotThrow(F);
1246     setDoesNotCapture(F, 2);
1247     break;
1248   case LibFunc::fgets:
1249     if (FTy->getNumParams() != 3 ||
1250         !FTy->getParamType(0)->isPointerTy() ||
1251         !FTy->getParamType(2)->isPointerTy())
1252       return false;
1253     setDoesNotThrow(F);
1254     setDoesNotCapture(F, 3);
1255     break;
1256   case LibFunc::fread:
1257     if (FTy->getNumParams() != 4 ||
1258         !FTy->getParamType(0)->isPointerTy() ||
1259         !FTy->getParamType(3)->isPointerTy())
1260       return false;
1261     setDoesNotThrow(F);
1262     setDoesNotCapture(F, 1);
1263     setDoesNotCapture(F, 4);
1264     break;
1265   case LibFunc::fwrite:
1266     if (FTy->getNumParams() != 4 ||
1267         !FTy->getParamType(0)->isPointerTy() ||
1268         !FTy->getParamType(3)->isPointerTy())
1269       return false;
1270     setDoesNotThrow(F);
1271     setDoesNotCapture(F, 1);
1272     setDoesNotCapture(F, 4);
1273     break;
1274   case LibFunc::fputs:
1275     if (FTy->getNumParams() < 2 ||
1276         !FTy->getParamType(0)->isPointerTy() ||
1277         !FTy->getParamType(1)->isPointerTy())
1278       return false;
1279     setDoesNotThrow(F);
1280     setDoesNotCapture(F, 1);
1281     setDoesNotCapture(F, 2);
1282     setOnlyReadsMemory(F, 1);
1283     break;
1284   case LibFunc::fscanf:
1285   case LibFunc::fprintf:
1286     if (FTy->getNumParams() < 2 ||
1287         !FTy->getParamType(0)->isPointerTy() ||
1288         !FTy->getParamType(1)->isPointerTy())
1289       return false;
1290     setDoesNotThrow(F);
1291     setDoesNotCapture(F, 1);
1292     setDoesNotCapture(F, 2);
1293     setOnlyReadsMemory(F, 2);
1294     break;
1295   case LibFunc::fgetpos:
1296     if (FTy->getNumParams() < 2 ||
1297         !FTy->getParamType(0)->isPointerTy() ||
1298         !FTy->getParamType(1)->isPointerTy())
1299       return false;
1300     setDoesNotThrow(F);
1301     setDoesNotCapture(F, 1);
1302     setDoesNotCapture(F, 2);
1303     break;
1304   case LibFunc::getc:
1305   case LibFunc::getlogin_r:
1306   case LibFunc::getc_unlocked:
1307     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1308       return false;
1309     setDoesNotThrow(F);
1310     setDoesNotCapture(F, 1);
1311     break;
1312   case LibFunc::getenv:
1313     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1314       return false;
1315     setDoesNotThrow(F);
1316     setOnlyReadsMemory(F);
1317     setDoesNotCapture(F, 1);
1318     break;
1319   case LibFunc::gets:
1320   case LibFunc::getchar:
1321     setDoesNotThrow(F);
1322     break;
1323   case LibFunc::getitimer:
1324     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1325       return false;
1326     setDoesNotThrow(F);
1327     setDoesNotCapture(F, 2);
1328     break;
1329   case LibFunc::getpwnam:
1330     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1331       return false;
1332     setDoesNotThrow(F);
1333     setDoesNotCapture(F, 1);
1334     setOnlyReadsMemory(F, 1);
1335     break;
1336   case LibFunc::ungetc:
1337     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1338       return false;
1339     setDoesNotThrow(F);
1340     setDoesNotCapture(F, 2);
1341     break;
1342   case LibFunc::uname:
1343     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1344       return false;
1345     setDoesNotThrow(F);
1346     setDoesNotCapture(F, 1);
1347     break;
1348   case LibFunc::unlink:
1349     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1350       return false;
1351     setDoesNotThrow(F);
1352     setDoesNotCapture(F, 1);
1353     setOnlyReadsMemory(F, 1);
1354     break;
1355   case LibFunc::unsetenv:
1356     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1357       return false;
1358     setDoesNotThrow(F);
1359     setDoesNotCapture(F, 1);
1360     setOnlyReadsMemory(F, 1);
1361     break;
1362   case LibFunc::utime:
1363   case LibFunc::utimes:
1364     if (FTy->getNumParams() != 2 ||
1365         !FTy->getParamType(0)->isPointerTy() ||
1366         !FTy->getParamType(1)->isPointerTy())
1367       return false;
1368     setDoesNotThrow(F);
1369     setDoesNotCapture(F, 1);
1370     setDoesNotCapture(F, 2);
1371     setOnlyReadsMemory(F, 1);
1372     setOnlyReadsMemory(F, 2);
1373     break;
1374   case LibFunc::putc:
1375     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1376       return false;
1377     setDoesNotThrow(F);
1378     setDoesNotCapture(F, 2);
1379     break;
1380   case LibFunc::puts:
1381   case LibFunc::printf:
1382   case LibFunc::perror:
1383     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1384       return false;
1385     setDoesNotThrow(F);
1386     setDoesNotCapture(F, 1);
1387     setOnlyReadsMemory(F, 1);
1388     break;
1389   case LibFunc::pread:
1390     if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
1391       return false;
1392     // May throw; "pread" is a valid pthread cancellation point.
1393     setDoesNotCapture(F, 2);
1394     break;
1395   case LibFunc::pwrite:
1396     if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
1397       return false;
1398     // May throw; "pwrite" is a valid pthread cancellation point.
1399     setDoesNotCapture(F, 2);
1400     setOnlyReadsMemory(F, 2);
1401     break;
1402   case LibFunc::putchar:
1403     setDoesNotThrow(F);
1404     break;
1405   case LibFunc::popen:
1406     if (FTy->getNumParams() != 2 ||
1407         !FTy->getReturnType()->isPointerTy() ||
1408         !FTy->getParamType(0)->isPointerTy() ||
1409         !FTy->getParamType(1)->isPointerTy())
1410       return false;
1411     setDoesNotThrow(F);
1412     setDoesNotAlias(F, 0);
1413     setDoesNotCapture(F, 1);
1414     setDoesNotCapture(F, 2);
1415     setOnlyReadsMemory(F, 1);
1416     setOnlyReadsMemory(F, 2);
1417     break;
1418   case LibFunc::pclose:
1419     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1420       return false;
1421     setDoesNotThrow(F);
1422     setDoesNotCapture(F, 1);
1423     break;
1424   case LibFunc::vscanf:
1425     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1426       return false;
1427     setDoesNotThrow(F);
1428     setDoesNotCapture(F, 1);
1429     setOnlyReadsMemory(F, 1);
1430     break;
1431   case LibFunc::vsscanf:
1432     if (FTy->getNumParams() != 3 ||
1433         !FTy->getParamType(1)->isPointerTy() ||
1434         !FTy->getParamType(2)->isPointerTy())
1435       return false;
1436     setDoesNotThrow(F);
1437     setDoesNotCapture(F, 1);
1438     setDoesNotCapture(F, 2);
1439     setOnlyReadsMemory(F, 1);
1440     setOnlyReadsMemory(F, 2);
1441     break;
1442   case LibFunc::vfscanf:
1443     if (FTy->getNumParams() != 3 ||
1444         !FTy->getParamType(1)->isPointerTy() ||
1445         !FTy->getParamType(2)->isPointerTy())
1446       return false;
1447     setDoesNotThrow(F);
1448     setDoesNotCapture(F, 1);
1449     setDoesNotCapture(F, 2);
1450     setOnlyReadsMemory(F, 2);
1451     break;
1452   case LibFunc::valloc:
1453     if (!FTy->getReturnType()->isPointerTy())
1454       return false;
1455     setDoesNotThrow(F);
1456     setDoesNotAlias(F, 0);
1457     break;
1458   case LibFunc::vprintf:
1459     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1460       return false;
1461     setDoesNotThrow(F);
1462     setDoesNotCapture(F, 1);
1463     setOnlyReadsMemory(F, 1);
1464     break;
1465   case LibFunc::vfprintf:
1466   case LibFunc::vsprintf:
1467     if (FTy->getNumParams() != 3 ||
1468         !FTy->getParamType(0)->isPointerTy() ||
1469         !FTy->getParamType(1)->isPointerTy())
1470       return false;
1471     setDoesNotThrow(F);
1472     setDoesNotCapture(F, 1);
1473     setDoesNotCapture(F, 2);
1474     setOnlyReadsMemory(F, 2);
1475     break;
1476   case LibFunc::vsnprintf:
1477     if (FTy->getNumParams() != 4 ||
1478         !FTy->getParamType(0)->isPointerTy() ||
1479         !FTy->getParamType(2)->isPointerTy())
1480       return false;
1481     setDoesNotThrow(F);
1482     setDoesNotCapture(F, 1);
1483     setDoesNotCapture(F, 3);
1484     setOnlyReadsMemory(F, 3);
1485     break;
1486   case LibFunc::open:
1487     if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
1488       return false;
1489     // May throw; "open" is a valid pthread cancellation point.
1490     setDoesNotCapture(F, 1);
1491     setOnlyReadsMemory(F, 1);
1492     break;
1493   case LibFunc::opendir:
1494     if (FTy->getNumParams() != 1 ||
1495         !FTy->getReturnType()->isPointerTy() ||
1496         !FTy->getParamType(0)->isPointerTy())
1497       return false;
1498     setDoesNotThrow(F);
1499     setDoesNotAlias(F, 0);
1500     setDoesNotCapture(F, 1);
1501     setOnlyReadsMemory(F, 1);
1502     break;
1503   case LibFunc::tmpfile:
1504     if (!FTy->getReturnType()->isPointerTy())
1505       return false;
1506     setDoesNotThrow(F);
1507     setDoesNotAlias(F, 0);
1508     break;
1509   case LibFunc::times:
1510     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1511       return false;
1512     setDoesNotThrow(F);
1513     setDoesNotCapture(F, 1);
1514     break;
1515   case LibFunc::htonl:
1516   case LibFunc::htons:
1517   case LibFunc::ntohl:
1518   case LibFunc::ntohs:
1519     setDoesNotThrow(F);
1520     setDoesNotAccessMemory(F);
1521     break;
1522   case LibFunc::lstat:
1523     if (FTy->getNumParams() != 2 ||
1524         !FTy->getParamType(0)->isPointerTy() ||
1525         !FTy->getParamType(1)->isPointerTy())
1526       return false;
1527     setDoesNotThrow(F);
1528     setDoesNotCapture(F, 1);
1529     setDoesNotCapture(F, 2);
1530     setOnlyReadsMemory(F, 1);
1531     break;
1532   case LibFunc::lchown:
1533     if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy())
1534       return false;
1535     setDoesNotThrow(F);
1536     setDoesNotCapture(F, 1);
1537     setOnlyReadsMemory(F, 1);
1538     break;
1539   case LibFunc::qsort:
1540     if (FTy->getNumParams() != 4 || !FTy->getParamType(3)->isPointerTy())
1541       return false;
1542     // May throw; places call through function pointer.
1543     setDoesNotCapture(F, 4);
1544     break;
1545   case LibFunc::dunder_strdup:
1546   case LibFunc::dunder_strndup:
1547     if (FTy->getNumParams() < 1 ||
1548         !FTy->getReturnType()->isPointerTy() ||
1549         !FTy->getParamType(0)->isPointerTy())
1550       return false;
1551     setDoesNotThrow(F);
1552     setDoesNotAlias(F, 0);
1553     setDoesNotCapture(F, 1);
1554     setOnlyReadsMemory(F, 1);
1555     break;
1556   case LibFunc::dunder_strtok_r:
1557     if (FTy->getNumParams() != 3 ||
1558         !FTy->getParamType(1)->isPointerTy())
1559       return false;
1560     setDoesNotThrow(F);
1561     setDoesNotCapture(F, 2);
1562     setOnlyReadsMemory(F, 2);
1563     break;
1564   case LibFunc::under_IO_getc:
1565     if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1566       return false;
1567     setDoesNotThrow(F);
1568     setDoesNotCapture(F, 1);
1569     break;
1570   case LibFunc::under_IO_putc:
1571     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1572       return false;
1573     setDoesNotThrow(F);
1574     setDoesNotCapture(F, 2);
1575     break;
1576   case LibFunc::dunder_isoc99_scanf:
1577     if (FTy->getNumParams() < 1 ||
1578         !FTy->getParamType(0)->isPointerTy())
1579       return false;
1580     setDoesNotThrow(F);
1581     setDoesNotCapture(F, 1);
1582     setOnlyReadsMemory(F, 1);
1583     break;
1584   case LibFunc::stat64:
1585   case LibFunc::lstat64:
1586   case LibFunc::statvfs64:
1587     if (FTy->getNumParams() < 1 ||
1588         !FTy->getParamType(0)->isPointerTy() ||
1589         !FTy->getParamType(1)->isPointerTy())
1590       return false;
1591     setDoesNotThrow(F);
1592     setDoesNotCapture(F, 1);
1593     setDoesNotCapture(F, 2);
1594     setOnlyReadsMemory(F, 1);
1595     break;
1596   case LibFunc::dunder_isoc99_sscanf:
1597     if (FTy->getNumParams() < 1 ||
1598         !FTy->getParamType(0)->isPointerTy() ||
1599         !FTy->getParamType(1)->isPointerTy())
1600       return false;
1601     setDoesNotThrow(F);
1602     setDoesNotCapture(F, 1);
1603     setDoesNotCapture(F, 2);
1604     setOnlyReadsMemory(F, 1);
1605     setOnlyReadsMemory(F, 2);
1606     break;
1607   case LibFunc::fopen64:
1608     if (FTy->getNumParams() != 2 ||
1609         !FTy->getReturnType()->isPointerTy() ||
1610         !FTy->getParamType(0)->isPointerTy() ||
1611         !FTy->getParamType(1)->isPointerTy())
1612       return false;
1613     setDoesNotThrow(F);
1614     setDoesNotAlias(F, 0);
1615     setDoesNotCapture(F, 1);
1616     setDoesNotCapture(F, 2);
1617     setOnlyReadsMemory(F, 1);
1618     setOnlyReadsMemory(F, 2);
1619     break;
1620   case LibFunc::fseeko64:
1621   case LibFunc::ftello64:
1622     if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1623       return false;
1624     setDoesNotThrow(F);
1625     setDoesNotCapture(F, 1);
1626     break;
1627   case LibFunc::tmpfile64:
1628     if (!FTy->getReturnType()->isPointerTy())
1629       return false;
1630     setDoesNotThrow(F);
1631     setDoesNotAlias(F, 0);
1632     break;
1633   case LibFunc::fstat64:
1634   case LibFunc::fstatvfs64:
1635     if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1636       return false;
1637     setDoesNotThrow(F);
1638     setDoesNotCapture(F, 2);
1639     break;
1640   case LibFunc::open64:
1641     if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
1642       return false;
1643     // May throw; "open" is a valid pthread cancellation point.
1644     setDoesNotCapture(F, 1);
1645     setOnlyReadsMemory(F, 1);
1646     break;
1647   case LibFunc::gettimeofday:
1648     if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
1649         !FTy->getParamType(1)->isPointerTy())
1650       return false;
1651     // Currently some platforms have the restrict keyword on the arguments to
1652     // gettimeofday. To be conservative, do not add noalias to gettimeofday's
1653     // arguments.
1654     setDoesNotThrow(F);
1655     setDoesNotCapture(F, 1);
1656     setDoesNotCapture(F, 2);
1657   default:
1658     // Didn't mark any attributes.
1659     return false;
1660   }
1661 
1662   return true;
1663 }
1664 
1665 /// annotateLibraryCalls - Adds attributes to well-known standard library
1666 /// call declarations.
1667 bool FunctionAttrs::annotateLibraryCalls(const CallGraphSCC &SCC) {
1668   bool MadeChange = false;
1669 
1670   // Check each function in turn annotating well-known library function
1671   // declarations with attributes.
1672   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
1673     Function *F = (*I)->getFunction();
1674 
1675     if (F != 0 && F->isDeclaration())
1676       MadeChange |= inferPrototypeAttributes(*F);
1677   }
1678 
1679   return MadeChange;
1680 }
1681 
1682 bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) {
1683   AA = &getAnalysis<AliasAnalysis>();
1684   TLI = &getAnalysis<TargetLibraryInfo>();
1685 
1686   bool Changed = annotateLibraryCalls(SCC);
1687   Changed |= AddReadAttrs(SCC);
1688   Changed |= AddArgumentAttrs(SCC);
1689   Changed |= AddNoAliasAttrs(SCC);
1690   return Changed;
1691 }
1692