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