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