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