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