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