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