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