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