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