FunctionAttrs.cpp revision 5729b8ea01739cf9b1171f0a4349275bc8124756 
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.  In addition,
13// it marks function arguments (of pointer type) 'nocapture' if a call
14// to the function does not create any copies of the pointer value that
15// outlive the call.  This more or less means that the pointer is only
16// dereferenced, and not returned from the function or stored in a global.
17// Finally, well-known library call declarations are marked with all
18// attributes that are consistent with the function's standard definition.
19// This pass is implemented as a bottom-up traversal of the call-graph.
20//
21//===----------------------------------------------------------------------===//
22
23#define DEBUG_TYPE "functionattrs"
24#include "llvm/Transforms/IPO.h"
25#include "llvm/ADT/SCCIterator.h"
26#include "llvm/ADT/SetVector.h"
27#include "llvm/ADT/SmallSet.h"
28#include "llvm/ADT/Statistic.h"
29#include "llvm/Analysis/AliasAnalysis.h"
30#include "llvm/Analysis/CallGraph.h"
31#include "llvm/Analysis/CallGraphSCCPass.h"
32#include "llvm/Analysis/CaptureTracking.h"
33#include "llvm/IR/GlobalVariable.h"
34#include "llvm/IR/IntrinsicInst.h"
35#include "llvm/IR/LLVMContext.h"
36#include "llvm/Support/InstIterator.h"
37#include "llvm/Target/TargetLibraryInfo.h"
38using namespace llvm;
39
40STATISTIC(NumReadNone, "Number of functions marked readnone");
41STATISTIC(NumReadOnly, "Number of functions marked readonly");
42STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
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    // AddNoCaptureAttrs - Deduce nocapture attributes for the SCC.
60    bool AddNoCaptureAttrs(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 setDoesNotAlias(Function &F, unsigned n) {
101      if (!F.doesNotAlias(n)) {
102	F.setDoesNotAlias(n);
103	++NumAnnotated;
104      }
105    }
106
107    // inferPrototypeAttributes - Analyze the name and prototype of the
108    // given function and set any applicable attributes.  Returns true
109    // if any attributes were set and false otherwise.
110    bool inferPrototypeAttributes(Function &F);
111
112    // annotateLibraryCalls - Adds attributes to well-known standard library
113    // call declarations.
114    bool annotateLibraryCalls(const CallGraphSCC &SCC);
115
116    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
117      AU.setPreservesCFG();
118      AU.addRequired<AliasAnalysis>();
119      AU.addRequired<TargetLibraryInfo>();
120      CallGraphSCCPass::getAnalysisUsage(AU);
121    }
122
123  private:
124    AliasAnalysis *AA;
125    TargetLibraryInfo *TLI;
126  };
127}
128
129char FunctionAttrs::ID = 0;
130INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs",
131                "Deduce function attributes", false, false)
132INITIALIZE_AG_DEPENDENCY(CallGraph)
133INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
134INITIALIZE_PASS_END(FunctionAttrs, "functionattrs",
135                "Deduce function attributes", false, false)
136
137Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); }
138
139
140/// AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
141bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) {
142  SmallPtrSet<Function*, 8> SCCNodes;
143
144  // Fill SCCNodes with the elements of the SCC.  Used for quickly
145  // looking up whether a given CallGraphNode is in this SCC.
146  for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
147    SCCNodes.insert((*I)->getFunction());
148
149  // Check if any of the functions in the SCC read or write memory.  If they
150  // write memory then they can't be marked readnone or readonly.
151  bool ReadsMemory = false;
152  for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
153    Function *F = (*I)->getFunction();
154
155    if (F == 0)
156      // External node - may write memory.  Just give up.
157      return false;
158
159    AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(F);
160    if (MRB == AliasAnalysis::DoesNotAccessMemory)
161      // Already perfect!
162      continue;
163
164    // Definitions with weak linkage may be overridden at linktime with
165    // something that writes memory, so treat them like declarations.
166    if (F->isDeclaration() || F->mayBeOverridden()) {
167      if (!AliasAnalysis::onlyReadsMemory(MRB))
168        // May write memory.  Just give up.
169        return false;
170
171      ReadsMemory = true;
172      continue;
173    }
174
175    // Scan the function body for instructions that may read or write memory.
176    for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
177      Instruction *I = &*II;
178
179      // Some instructions can be ignored even if they read or write memory.
180      // Detect these now, skipping to the next instruction if one is found.
181      CallSite CS(cast<Value>(I));
182      if (CS) {
183        // Ignore calls to functions in the same SCC.
184        if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
185          continue;
186        AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(CS);
187        // If the call doesn't access arbitrary memory, we may be able to
188        // figure out something.
189        if (AliasAnalysis::onlyAccessesArgPointees(MRB)) {
190          // If the call does access argument pointees, check each argument.
191          if (AliasAnalysis::doesAccessArgPointees(MRB))
192            // Check whether all pointer arguments point to local memory, and
193            // ignore calls that only access local memory.
194            for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
195                 CI != CE; ++CI) {
196              Value *Arg = *CI;
197              if (Arg->getType()->isPointerTy()) {
198                AliasAnalysis::Location Loc(Arg,
199                                            AliasAnalysis::UnknownSize,
200                                            I->getMetadata(LLVMContext::MD_tbaa));
201                if (!AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) {
202                  if (MRB & AliasAnalysis::Mod)
203                    // Writes non-local memory.  Give up.
204                    return false;
205                  if (MRB & AliasAnalysis::Ref)
206                    // Ok, it reads non-local memory.
207                    ReadsMemory = true;
208                }
209              }
210            }
211          continue;
212        }
213        // The call could access any memory. If that includes writes, give up.
214        if (MRB & AliasAnalysis::Mod)
215          return false;
216        // If it reads, note it.
217        if (MRB & AliasAnalysis::Ref)
218          ReadsMemory = true;
219        continue;
220      } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
221        // Ignore non-volatile loads from local memory. (Atomic is okay here.)
222        if (!LI->isVolatile()) {
223          AliasAnalysis::Location Loc = AA->getLocation(LI);
224          if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true))
225            continue;
226        }
227      } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
228        // Ignore non-volatile stores to local memory. (Atomic is okay here.)
229        if (!SI->isVolatile()) {
230          AliasAnalysis::Location Loc = AA->getLocation(SI);
231          if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true))
232            continue;
233        }
234      } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) {
235        // Ignore vaargs on local memory.
236        AliasAnalysis::Location Loc = AA->getLocation(VI);
237        if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true))
238          continue;
239      }
240
241      // Any remaining instructions need to be taken seriously!  Check if they
242      // read or write memory.
243      if (I->mayWriteToMemory())
244        // Writes memory.  Just give up.
245        return false;
246
247      // If this instruction may read memory, remember that.
248      ReadsMemory |= I->mayReadFromMemory();
249    }
250  }
251
252  // Success!  Functions in this SCC do not access memory, or only read memory.
253  // Give them the appropriate attribute.
254  bool MadeChange = false;
255  for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
256    Function *F = (*I)->getFunction();
257
258    if (F->doesNotAccessMemory())
259      // Already perfect!
260      continue;
261
262    if (F->onlyReadsMemory() && ReadsMemory)
263      // No change.
264      continue;
265
266    MadeChange = true;
267
268    // Clear out any existing attributes.
269    AttrBuilder B;
270    B.addAttribute(Attribute::ReadOnly)
271      .addAttribute(Attribute::ReadNone);
272    F->removeAttributes(AttributeSet::FunctionIndex,
273                        AttributeSet::get(F->getContext(),
274                                          AttributeSet::FunctionIndex, B));
275
276    // Add in the new attribute.
277    F->addAttribute(AttributeSet::FunctionIndex,
278                    ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone);
279
280    if (ReadsMemory)
281      ++NumReadOnly;
282    else
283      ++NumReadNone;
284  }
285
286  return MadeChange;
287}
288
289namespace {
290  // For a given pointer Argument, this retains a list of Arguments of functions
291  // in the same SCC that the pointer data flows into. We use this to build an
292  // SCC of the arguments.
293  struct ArgumentGraphNode {
294    Argument *Definition;
295    SmallVector<ArgumentGraphNode*, 4> Uses;
296  };
297
298  class ArgumentGraph {
299    // We store pointers to ArgumentGraphNode objects, so it's important that
300    // that they not move around upon insert.
301    typedef std::map<Argument*, ArgumentGraphNode> ArgumentMapTy;
302
303    ArgumentMapTy ArgumentMap;
304
305    // There is no root node for the argument graph, in fact:
306    //   void f(int *x, int *y) { if (...) f(x, y); }
307    // is an example where the graph is disconnected. The SCCIterator requires a
308    // single entry point, so we maintain a fake ("synthetic") root node that
309    // uses every node. Because the graph is directed and nothing points into
310    // the root, it will not participate in any SCCs (except for its own).
311    ArgumentGraphNode SyntheticRoot;
312
313  public:
314    ArgumentGraph() { SyntheticRoot.Definition = 0; }
315
316    typedef SmallVectorImpl<ArgumentGraphNode*>::iterator iterator;
317
318    iterator begin() { return SyntheticRoot.Uses.begin(); }
319    iterator end() { return SyntheticRoot.Uses.end(); }
320    ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; }
321
322    ArgumentGraphNode *operator[](Argument *A) {
323      ArgumentGraphNode &Node = ArgumentMap[A];
324      Node.Definition = A;
325      SyntheticRoot.Uses.push_back(&Node);
326      return &Node;
327    }
328  };
329
330  // This tracker checks whether callees are in the SCC, and if so it does not
331  // consider that a capture, instead adding it to the "Uses" list and
332  // continuing with the analysis.
333  struct ArgumentUsesTracker : public CaptureTracker {
334    ArgumentUsesTracker(const SmallPtrSet<Function*, 8> &SCCNodes)
335      : Captured(false), SCCNodes(SCCNodes) {}
336
337    void tooManyUses() { Captured = true; }
338
339    bool captured(Use *U) {
340      CallSite CS(U->getUser());
341      if (!CS.getInstruction()) { Captured = true; return true; }
342
343      Function *F = CS.getCalledFunction();
344      if (!F || !SCCNodes.count(F)) { Captured = true; return true; }
345
346      Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end();
347      for (CallSite::arg_iterator PI = CS.arg_begin(), PE = CS.arg_end();
348           PI != PE; ++PI, ++AI) {
349        if (AI == AE) {
350          assert(F->isVarArg() && "More params than args in non-varargs call");
351          Captured = true;
352          return true;
353        }
354        if (PI == U) {
355          Uses.push_back(AI);
356          break;
357        }
358      }
359      assert(!Uses.empty() && "Capturing call-site captured nothing?");
360      return false;
361    }
362
363    bool Captured;  // True only if certainly captured (used outside our SCC).
364    SmallVector<Argument*, 4> Uses;  // Uses within our SCC.
365
366    const SmallPtrSet<Function*, 8> &SCCNodes;
367  };
368}
369
370namespace llvm {
371  template<> struct GraphTraits<ArgumentGraphNode*> {
372    typedef ArgumentGraphNode NodeType;
373    typedef SmallVectorImpl<ArgumentGraphNode*>::iterator ChildIteratorType;
374
375    static inline NodeType *getEntryNode(NodeType *A) { return A; }
376    static inline ChildIteratorType child_begin(NodeType *N) {
377      return N->Uses.begin();
378    }
379    static inline ChildIteratorType child_end(NodeType *N) {
380      return N->Uses.end();
381    }
382  };
383  template<> struct GraphTraits<ArgumentGraph*>
384    : public GraphTraits<ArgumentGraphNode*> {
385    static NodeType *getEntryNode(ArgumentGraph *AG) {
386      return AG->getEntryNode();
387    }
388    static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
389      return AG->begin();
390    }
391    static ChildIteratorType nodes_end(ArgumentGraph *AG) {
392      return AG->end();
393    }
394  };
395}
396
397/// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC.
398bool FunctionAttrs::AddNoCaptureAttrs(const CallGraphSCC &SCC) {
399  bool Changed = false;
400
401  SmallPtrSet<Function*, 8> SCCNodes;
402
403  // Fill SCCNodes with the elements of the SCC.  Used for quickly
404  // looking up whether a given CallGraphNode is in this SCC.
405  for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
406    Function *F = (*I)->getFunction();
407    if (F && !F->isDeclaration() && !F->mayBeOverridden())
408      SCCNodes.insert(F);
409  }
410
411  ArgumentGraph AG;
412
413  AttrBuilder B;
414  B.addAttribute(Attribute::NoCapture);
415
416  // Check each function in turn, determining which pointer arguments are not
417  // captured.
418  for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
419    Function *F = (*I)->getFunction();
420
421    if (F == 0)
422      // External node - only a problem for arguments that we pass to it.
423      continue;
424
425    // Definitions with weak linkage may be overridden at linktime with
426    // something that captures pointers, so treat them like declarations.
427    if (F->isDeclaration() || F->mayBeOverridden())
428      continue;
429
430    // Functions that are readonly (or readnone) and nounwind and don't return
431    // a value can't capture arguments. Don't analyze them.
432    if (F->onlyReadsMemory() && F->doesNotThrow() &&
433        F->getReturnType()->isVoidTy()) {
434      for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end();
435           A != E; ++A) {
436        if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
437          A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
438          ++NumNoCapture;
439          Changed = true;
440        }
441      }
442      continue;
443    }
444
445    for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A!=E; ++A)
446      if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
447        ArgumentUsesTracker Tracker(SCCNodes);
448        PointerMayBeCaptured(A, &Tracker);
449        if (!Tracker.Captured) {
450          if (Tracker.Uses.empty()) {
451            // If it's trivially not captured, mark it nocapture now.
452            A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo()+1, B));
453            ++NumNoCapture;
454            Changed = true;
455          } else {
456            // If it's not trivially captured and not trivially not captured,
457            // then it must be calling into another function in our SCC. Save
458            // its particulars for Argument-SCC analysis later.
459            ArgumentGraphNode *Node = AG[A];
460            for (SmallVectorImpl<Argument*>::iterator UI = Tracker.Uses.begin(),
461                   UE = Tracker.Uses.end(); UI != UE; ++UI)
462              Node->Uses.push_back(AG[*UI]);
463          }
464        }
465        // Otherwise, it's captured. Don't bother doing SCC analysis on it.
466      }
467  }
468
469  // The graph we've collected is partial because we stopped scanning for
470  // argument uses once we solved the argument trivially. These partial nodes
471  // show up as ArgumentGraphNode objects with an empty Uses list, and for
472  // these nodes the final decision about whether they capture has already been
473  // made.  If the definition doesn't have a 'nocapture' attribute by now, it
474  // captures.
475
476  for (scc_iterator<ArgumentGraph*> I = scc_begin(&AG), E = scc_end(&AG);
477       I != E; ++I) {
478    std::vector<ArgumentGraphNode*> &ArgumentSCC = *I;
479    if (ArgumentSCC.size() == 1) {
480      if (!ArgumentSCC[0]->Definition) continue;  // synthetic root node
481
482      // eg. "void f(int* x) { if (...) f(x); }"
483      if (ArgumentSCC[0]->Uses.size() == 1 &&
484          ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
485        ArgumentSCC[0]->
486          Definition->
487          addAttr(AttributeSet::get(ArgumentSCC[0]->Definition->getContext(),
488                                    ArgumentSCC[0]->Definition->getArgNo() + 1,
489                                    B));
490        ++NumNoCapture;
491        Changed = true;
492      }
493      continue;
494    }
495
496    bool SCCCaptured = false;
497    for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(),
498           E = ArgumentSCC.end(); I != E && !SCCCaptured; ++I) {
499      ArgumentGraphNode *Node = *I;
500      if (Node->Uses.empty()) {
501        if (!Node->Definition->hasNoCaptureAttr())
502          SCCCaptured = true;
503      }
504    }
505    if (SCCCaptured) continue;
506
507    SmallPtrSet<Argument*, 8> ArgumentSCCNodes;
508    // Fill ArgumentSCCNodes with the elements of the ArgumentSCC.  Used for
509    // quickly looking up whether a given Argument is in this ArgumentSCC.
510    for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(),
511           E = ArgumentSCC.end(); I != E; ++I) {
512      ArgumentSCCNodes.insert((*I)->Definition);
513    }
514
515    for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(),
516           E = ArgumentSCC.end(); I != E && !SCCCaptured; ++I) {
517      ArgumentGraphNode *N = *I;
518      for (SmallVectorImpl<ArgumentGraphNode*>::iterator UI = N->Uses.begin(),
519             UE = N->Uses.end(); UI != UE; ++UI) {
520        Argument *A = (*UI)->Definition;
521        if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
522          continue;
523        SCCCaptured = true;
524        break;
525      }
526    }
527    if (SCCCaptured) continue;
528
529    for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
530      Argument *A = ArgumentSCC[i]->Definition;
531      A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
532      ++NumNoCapture;
533      Changed = true;
534    }
535  }
536
537  return Changed;
538}
539
540/// IsFunctionMallocLike - A function is malloc-like if it returns either null
541/// or a pointer that doesn't alias any other pointer visible to the caller.
542bool FunctionAttrs::IsFunctionMallocLike(Function *F,
543                              SmallPtrSet<Function*, 8> &SCCNodes) const {
544  SmallSetVector<Value *, 8> FlowsToReturn;
545  for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
546    if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator()))
547      FlowsToReturn.insert(Ret->getReturnValue());
548
549  for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
550    Value *RetVal = FlowsToReturn[i];
551
552    if (Constant *C = dyn_cast<Constant>(RetVal)) {
553      if (!C->isNullValue() && !isa<UndefValue>(C))
554        return false;
555
556      continue;
557    }
558
559    if (isa<Argument>(RetVal))
560      return false;
561
562    if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
563      switch (RVI->getOpcode()) {
564        // Extend the analysis by looking upwards.
565        case Instruction::BitCast:
566        case Instruction::GetElementPtr:
567          FlowsToReturn.insert(RVI->getOperand(0));
568          continue;
569        case Instruction::Select: {
570          SelectInst *SI = cast<SelectInst>(RVI);
571          FlowsToReturn.insert(SI->getTrueValue());
572          FlowsToReturn.insert(SI->getFalseValue());
573          continue;
574        }
575        case Instruction::PHI: {
576          PHINode *PN = cast<PHINode>(RVI);
577          for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
578            FlowsToReturn.insert(PN->getIncomingValue(i));
579          continue;
580        }
581
582        // Check whether the pointer came from an allocation.
583        case Instruction::Alloca:
584          break;
585        case Instruction::Call:
586        case Instruction::Invoke: {
587          CallSite CS(RVI);
588          if (CS.paramHasAttr(0, Attribute::NoAlias))
589            break;
590          if (CS.getCalledFunction() &&
591              SCCNodes.count(CS.getCalledFunction()))
592            break;
593        } // fall-through
594        default:
595          return false;  // Did not come from an allocation.
596      }
597
598    if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
599      return false;
600  }
601
602  return true;
603}
604
605/// AddNoAliasAttrs - Deduce noalias attributes for the SCC.
606bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) {
607  SmallPtrSet<Function*, 8> SCCNodes;
608
609  // Fill SCCNodes with the elements of the SCC.  Used for quickly
610  // looking up whether a given CallGraphNode is in this SCC.
611  for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
612    SCCNodes.insert((*I)->getFunction());
613
614  // Check each function in turn, determining which functions return noalias
615  // pointers.
616  for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
617    Function *F = (*I)->getFunction();
618
619    if (F == 0)
620      // External node - skip it;
621      return false;
622
623    // Already noalias.
624    if (F->doesNotAlias(0))
625      continue;
626
627    // Definitions with weak linkage may be overridden at linktime, so
628    // treat them like declarations.
629    if (F->isDeclaration() || F->mayBeOverridden())
630      return false;
631
632    // We annotate noalias return values, which are only applicable to
633    // pointer types.
634    if (!F->getReturnType()->isPointerTy())
635      continue;
636
637    if (!IsFunctionMallocLike(F, SCCNodes))
638      return false;
639  }
640
641  bool MadeChange = false;
642  for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
643    Function *F = (*I)->getFunction();
644    if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy())
645      continue;
646
647    F->setDoesNotAlias(0);
648    ++NumNoAlias;
649    MadeChange = true;
650  }
651
652  return MadeChange;
653}
654
655/// inferPrototypeAttributes - Analyze the name and prototype of the
656/// given function and set any applicable attributes.  Returns true
657/// if any attributes were set and false otherwise.
658bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
659  FunctionType *FTy = F.getFunctionType();
660  LibFunc::Func TheLibFunc;
661  if (!(TLI->getLibFunc(F.getName(), TheLibFunc) && TLI->has(TheLibFunc)))
662    return false;
663
664  switch (TheLibFunc) {
665  case LibFunc::strlen:
666    if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
667      return false;
668    setOnlyReadsMemory(F);
669    setDoesNotThrow(F);
670    setDoesNotCapture(F, 1);
671    break;
672  case LibFunc::strchr:
673  case LibFunc::strrchr:
674    if (FTy->getNumParams() != 2 ||
675        !FTy->getParamType(0)->isPointerTy() ||
676        !FTy->getParamType(1)->isIntegerTy())
677      return false;
678    setOnlyReadsMemory(F);
679    setDoesNotThrow(F);
680    break;
681  case LibFunc::strcpy:
682  case LibFunc::stpcpy:
683  case LibFunc::strcat:
684  case LibFunc::strtol:
685  case LibFunc::strtod:
686  case LibFunc::strtof:
687  case LibFunc::strtoul:
688  case LibFunc::strtoll:
689  case LibFunc::strtold:
690  case LibFunc::strncat:
691  case LibFunc::strncpy:
692  case LibFunc::stpncpy:
693  case LibFunc::strtoull:
694    if (FTy->getNumParams() < 2 ||
695        !FTy->getParamType(1)->isPointerTy())
696      return false;
697    setDoesNotThrow(F);
698    setDoesNotCapture(F, 2);
699    break;
700  case LibFunc::strxfrm:
701    if (FTy->getNumParams() != 3 ||
702        !FTy->getParamType(0)->isPointerTy() ||
703        !FTy->getParamType(1)->isPointerTy())
704      return false;
705    setDoesNotThrow(F);
706    setDoesNotCapture(F, 1);
707    setDoesNotCapture(F, 2);
708    break;
709  case LibFunc::strcmp:
710  case LibFunc::strspn:
711  case LibFunc::strncmp:
712  case LibFunc::strcspn:
713  case LibFunc::strcoll:
714  case LibFunc::strcasecmp:
715  case LibFunc::strncasecmp:
716    if (FTy->getNumParams() < 2 ||
717        !FTy->getParamType(0)->isPointerTy() ||
718        !FTy->getParamType(1)->isPointerTy())
719      return false;
720    setOnlyReadsMemory(F);
721    setDoesNotThrow(F);
722    setDoesNotCapture(F, 1);
723    setDoesNotCapture(F, 2);
724    break;
725  case LibFunc::strstr:
726  case LibFunc::strpbrk:
727    if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
728      return false;
729    setOnlyReadsMemory(F);
730    setDoesNotThrow(F);
731    setDoesNotCapture(F, 2);
732    break;
733  case LibFunc::strtok:
734  case LibFunc::strtok_r:
735    if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
736      return false;
737    setDoesNotThrow(F);
738    setDoesNotCapture(F, 2);
739    break;
740  case LibFunc::scanf:
741  case LibFunc::setbuf:
742  case LibFunc::setvbuf:
743    if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
744      return false;
745    setDoesNotThrow(F);
746    setDoesNotCapture(F, 1);
747    break;
748  case LibFunc::strdup:
749  case LibFunc::strndup:
750    if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() ||
751        !FTy->getParamType(0)->isPointerTy())
752      return false;
753    setDoesNotThrow(F);
754    setDoesNotAlias(F, 0);
755    setDoesNotCapture(F, 1);
756    break;
757  case LibFunc::stat:
758  case LibFunc::sscanf:
759  case LibFunc::sprintf:
760  case LibFunc::statvfs:
761    if (FTy->getNumParams() < 2 ||
762        !FTy->getParamType(0)->isPointerTy() ||
763        !FTy->getParamType(1)->isPointerTy())
764      return false;
765    setDoesNotThrow(F);
766    setDoesNotCapture(F, 1);
767    setDoesNotCapture(F, 2);
768    break;
769  case LibFunc::snprintf:
770    if (FTy->getNumParams() != 3 ||
771        !FTy->getParamType(0)->isPointerTy() ||
772        !FTy->getParamType(2)->isPointerTy())
773      return false;
774    setDoesNotThrow(F);
775    setDoesNotCapture(F, 1);
776    setDoesNotCapture(F, 3);
777    break;
778  case LibFunc::setitimer:
779    if (FTy->getNumParams() != 3 ||
780        !FTy->getParamType(1)->isPointerTy() ||
781        !FTy->getParamType(2)->isPointerTy())
782      return false;
783    setDoesNotThrow(F);
784    setDoesNotCapture(F, 2);
785    setDoesNotCapture(F, 3);
786    break;
787  case LibFunc::system:
788    if (FTy->getNumParams() != 1 ||
789        !FTy->getParamType(0)->isPointerTy())
790      return false;
791    // May throw; "system" is a valid pthread cancellation point.
792    setDoesNotCapture(F, 1);
793    break;
794  case LibFunc::malloc:
795    if (FTy->getNumParams() != 1 ||
796        !FTy->getReturnType()->isPointerTy())
797      return false;
798    setDoesNotThrow(F);
799    setDoesNotAlias(F, 0);
800    break;
801  case LibFunc::memcmp:
802    if (FTy->getNumParams() != 3 ||
803        !FTy->getParamType(0)->isPointerTy() ||
804        !FTy->getParamType(1)->isPointerTy())
805      return false;
806    setOnlyReadsMemory(F);
807    setDoesNotThrow(F);
808    setDoesNotCapture(F, 1);
809    setDoesNotCapture(F, 2);
810    break;
811  case LibFunc::memchr:
812  case LibFunc::memrchr:
813    if (FTy->getNumParams() != 3)
814      return false;
815    setOnlyReadsMemory(F);
816    setDoesNotThrow(F);
817    break;
818  case LibFunc::modf:
819  case LibFunc::modff:
820  case LibFunc::modfl:
821  case LibFunc::memcpy:
822  case LibFunc::memccpy:
823  case LibFunc::memmove:
824    if (FTy->getNumParams() < 2 ||
825        !FTy->getParamType(1)->isPointerTy())
826      return false;
827    setDoesNotThrow(F);
828    setDoesNotCapture(F, 2);
829    break;
830  case LibFunc::memalign:
831    if (!FTy->getReturnType()->isPointerTy())
832      return false;
833    setDoesNotAlias(F, 0);
834    break;
835  case LibFunc::mkdir:
836  case LibFunc::mktime:
837    if (FTy->getNumParams() == 0 ||
838        !FTy->getParamType(0)->isPointerTy())
839      return false;
840    setDoesNotThrow(F);
841    setDoesNotCapture(F, 1);
842    break;
843  case LibFunc::realloc:
844    if (FTy->getNumParams() != 2 ||
845        !FTy->getParamType(0)->isPointerTy() ||
846        !FTy->getReturnType()->isPointerTy())
847      return false;
848    setDoesNotThrow(F);
849    setDoesNotAlias(F, 0);
850    setDoesNotCapture(F, 1);
851    break;
852  case LibFunc::read:
853    if (FTy->getNumParams() != 3 ||
854        !FTy->getParamType(1)->isPointerTy())
855      return false;
856    // May throw; "read" is a valid pthread cancellation point.
857    setDoesNotCapture(F, 2);
858    break;
859  case LibFunc::rmdir:
860  case LibFunc::rewind:
861  case LibFunc::remove:
862  case LibFunc::realpath:
863    if (FTy->getNumParams() < 1 ||
864        !FTy->getParamType(0)->isPointerTy())
865      return false;
866    setDoesNotThrow(F);
867    setDoesNotCapture(F, 1);
868    break;
869  case LibFunc::rename:
870  case LibFunc::readlink:
871    if (FTy->getNumParams() < 2 ||
872        !FTy->getParamType(0)->isPointerTy() ||
873        !FTy->getParamType(1)->isPointerTy())
874      return false;
875    setDoesNotThrow(F);
876    setDoesNotCapture(F, 1);
877    setDoesNotCapture(F, 2);
878    break;
879  case LibFunc::write:
880    if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
881      return false;
882    // May throw; "write" is a valid pthread cancellation point.
883    setDoesNotCapture(F, 2);
884    break;
885  case LibFunc::bcopy:
886    if (FTy->getNumParams() != 3 ||
887        !FTy->getParamType(0)->isPointerTy() ||
888        !FTy->getParamType(1)->isPointerTy())
889      return false;
890    setDoesNotThrow(F);
891    setDoesNotCapture(F, 1);
892    setDoesNotCapture(F, 2);
893    break;
894  case LibFunc::bcmp:
895    if (FTy->getNumParams() != 3 ||
896        !FTy->getParamType(0)->isPointerTy() ||
897        !FTy->getParamType(1)->isPointerTy())
898      return false;
899    setDoesNotThrow(F);
900    setOnlyReadsMemory(F);
901    setDoesNotCapture(F, 1);
902    setDoesNotCapture(F, 2);
903    break;
904  case LibFunc::bzero:
905    if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
906      return false;
907    setDoesNotThrow(F);
908    setDoesNotCapture(F, 1);
909    break;
910  case LibFunc::calloc:
911    if (FTy->getNumParams() != 2 ||
912        !FTy->getReturnType()->isPointerTy())
913      return false;
914    setDoesNotThrow(F);
915    setDoesNotAlias(F, 0);
916    break;
917  case LibFunc::chmod:
918  case LibFunc::chown:
919  case LibFunc::ctermid:
920  case LibFunc::clearerr:
921  case LibFunc::closedir:
922    if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
923      return false;
924    setDoesNotThrow(F);
925    setDoesNotCapture(F, 1);
926    break;
927  case LibFunc::atoi:
928  case LibFunc::atol:
929  case LibFunc::atof:
930  case LibFunc::atoll:
931    if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
932      return false;
933    setDoesNotThrow(F);
934    setOnlyReadsMemory(F);
935    setDoesNotCapture(F, 1);
936    break;
937  case LibFunc::access:
938    if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
939      return false;
940    setDoesNotThrow(F);
941    setDoesNotCapture(F, 1);
942    break;
943  case LibFunc::fopen:
944    if (FTy->getNumParams() != 2 ||
945        !FTy->getReturnType()->isPointerTy() ||
946        !FTy->getParamType(0)->isPointerTy() ||
947        !FTy->getParamType(1)->isPointerTy())
948      return false;
949    setDoesNotThrow(F);
950    setDoesNotAlias(F, 0);
951    setDoesNotCapture(F, 1);
952    setDoesNotCapture(F, 2);
953    break;
954  case LibFunc::fdopen:
955    if (FTy->getNumParams() != 2 ||
956        !FTy->getReturnType()->isPointerTy() ||
957        !FTy->getParamType(1)->isPointerTy())
958      return false;
959    setDoesNotThrow(F);
960    setDoesNotAlias(F, 0);
961    setDoesNotCapture(F, 2);
962    break;
963  case LibFunc::feof:
964  case LibFunc::free:
965  case LibFunc::fseek:
966  case LibFunc::ftell:
967  case LibFunc::fgetc:
968  case LibFunc::fseeko:
969  case LibFunc::ftello:
970  case LibFunc::fileno:
971  case LibFunc::fflush:
972  case LibFunc::fclose:
973  case LibFunc::fsetpos:
974  case LibFunc::flockfile:
975  case LibFunc::funlockfile:
976  case LibFunc::ftrylockfile:
977    if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
978      return false;
979    setDoesNotThrow(F);
980    setDoesNotCapture(F, 1);
981    break;
982  case LibFunc::ferror:
983    if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
984      return false;
985    setDoesNotThrow(F);
986    setDoesNotCapture(F, 1);
987    setOnlyReadsMemory(F);
988    break;
989  case LibFunc::fputc:
990  case LibFunc::fstat:
991  case LibFunc::frexp:
992  case LibFunc::frexpf:
993  case LibFunc::frexpl:
994  case LibFunc::fstatvfs:
995    if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
996      return false;
997    setDoesNotThrow(F);
998    setDoesNotCapture(F, 2);
999    break;
1000  case LibFunc::fgets:
1001    if (FTy->getNumParams() != 3 ||
1002        !FTy->getParamType(0)->isPointerTy() ||
1003        !FTy->getParamType(2)->isPointerTy())
1004      return false;
1005    setDoesNotThrow(F);
1006    setDoesNotCapture(F, 3);
1007  case LibFunc::fread:
1008  case LibFunc::fwrite:
1009    if (FTy->getNumParams() != 4 ||
1010        !FTy->getParamType(0)->isPointerTy() ||
1011        !FTy->getParamType(3)->isPointerTy())
1012      return false;
1013    setDoesNotThrow(F);
1014    setDoesNotCapture(F, 1);
1015    setDoesNotCapture(F, 4);
1016  case LibFunc::fputs:
1017  case LibFunc::fscanf:
1018  case LibFunc::fprintf:
1019  case LibFunc::fgetpos:
1020    if (FTy->getNumParams() < 2 ||
1021        !FTy->getParamType(0)->isPointerTy() ||
1022        !FTy->getParamType(1)->isPointerTy())
1023      return false;
1024    setDoesNotThrow(F);
1025    setDoesNotCapture(F, 1);
1026    setDoesNotCapture(F, 2);
1027    break;
1028  case LibFunc::getc:
1029  case LibFunc::getlogin_r:
1030  case LibFunc::getc_unlocked:
1031    if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1032      return false;
1033    setDoesNotThrow(F);
1034    setDoesNotCapture(F, 1);
1035    break;
1036  case LibFunc::getenv:
1037    if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1038      return false;
1039    setDoesNotThrow(F);
1040    setOnlyReadsMemory(F);
1041    setDoesNotCapture(F, 1);
1042    break;
1043  case LibFunc::gets:
1044  case LibFunc::getchar:
1045    setDoesNotThrow(F);
1046    break;
1047  case LibFunc::getitimer:
1048    if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1049      return false;
1050    setDoesNotThrow(F);
1051    setDoesNotCapture(F, 2);
1052    break;
1053  case LibFunc::getpwnam:
1054    if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1055      return false;
1056    setDoesNotThrow(F);
1057    setDoesNotCapture(F, 1);
1058    break;
1059  case LibFunc::ungetc:
1060    if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1061      return false;
1062    setDoesNotThrow(F);
1063    setDoesNotCapture(F, 2);
1064    break;
1065  case LibFunc::uname:
1066  case LibFunc::unlink:
1067  case LibFunc::unsetenv:
1068    if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1069      return false;
1070    setDoesNotThrow(F);
1071    setDoesNotCapture(F, 1);
1072    break;
1073  case LibFunc::utime:
1074  case LibFunc::utimes:
1075    if (FTy->getNumParams() != 2 ||
1076        !FTy->getParamType(0)->isPointerTy() ||
1077        !FTy->getParamType(1)->isPointerTy())
1078      return false;
1079    setDoesNotThrow(F);
1080    setDoesNotCapture(F, 1);
1081    setDoesNotCapture(F, 2);
1082    break;
1083  case LibFunc::putc:
1084    if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1085      return false;
1086    setDoesNotThrow(F);
1087    setDoesNotCapture(F, 2);
1088    break;
1089  case LibFunc::puts:
1090  case LibFunc::printf:
1091  case LibFunc::perror:
1092    if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1093      return false;
1094    setDoesNotThrow(F);
1095    setDoesNotCapture(F, 1);
1096    break;
1097  case LibFunc::pread:
1098  case LibFunc::pwrite:
1099    if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
1100      return false;
1101    // May throw; these are valid pthread cancellation points.
1102    setDoesNotCapture(F, 2);
1103    break;
1104  case LibFunc::putchar:
1105    setDoesNotThrow(F);
1106    break;
1107  case LibFunc::popen:
1108    if (FTy->getNumParams() != 2 ||
1109        !FTy->getReturnType()->isPointerTy() ||
1110        !FTy->getParamType(0)->isPointerTy() ||
1111        !FTy->getParamType(1)->isPointerTy())
1112      return false;
1113    setDoesNotThrow(F);
1114    setDoesNotAlias(F, 0);
1115    setDoesNotCapture(F, 1);
1116    setDoesNotCapture(F, 2);
1117    break;
1118  case LibFunc::pclose:
1119    if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1120      return false;
1121    setDoesNotThrow(F);
1122    setDoesNotCapture(F, 1);
1123    break;
1124  case LibFunc::vscanf:
1125    if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1126      return false;
1127    setDoesNotThrow(F);
1128    setDoesNotCapture(F, 1);
1129    break;
1130  case LibFunc::vsscanf:
1131  case LibFunc::vfscanf:
1132    if (FTy->getNumParams() != 3 ||
1133        !FTy->getParamType(1)->isPointerTy() ||
1134        !FTy->getParamType(2)->isPointerTy())
1135      return false;
1136    setDoesNotThrow(F);
1137    setDoesNotCapture(F, 1);
1138    setDoesNotCapture(F, 2);
1139    break;
1140  case LibFunc::valloc:
1141    if (!FTy->getReturnType()->isPointerTy())
1142      return false;
1143    setDoesNotThrow(F);
1144    setDoesNotAlias(F, 0);
1145    break;
1146  case LibFunc::vprintf:
1147    if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1148      return false;
1149    setDoesNotThrow(F);
1150    setDoesNotCapture(F, 1);
1151    break;
1152  case LibFunc::vfprintf:
1153  case LibFunc::vsprintf:
1154    if (FTy->getNumParams() != 3 ||
1155        !FTy->getParamType(0)->isPointerTy() ||
1156        !FTy->getParamType(1)->isPointerTy())
1157      return false;
1158    setDoesNotThrow(F);
1159    setDoesNotCapture(F, 1);
1160    setDoesNotCapture(F, 2);
1161    break;
1162  case LibFunc::vsnprintf:
1163    if (FTy->getNumParams() != 4 ||
1164        !FTy->getParamType(0)->isPointerTy() ||
1165        !FTy->getParamType(2)->isPointerTy())
1166      return false;
1167    setDoesNotThrow(F);
1168    setDoesNotCapture(F, 1);
1169    setDoesNotCapture(F, 3);
1170    break;
1171  case LibFunc::open:
1172    if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
1173      return false;
1174    // May throw; "open" is a valid pthread cancellation point.
1175    setDoesNotCapture(F, 1);
1176    break;
1177  case LibFunc::opendir:
1178    if (FTy->getNumParams() != 1 ||
1179        !FTy->getReturnType()->isPointerTy() ||
1180        !FTy->getParamType(0)->isPointerTy())
1181      return false;
1182    setDoesNotThrow(F);
1183    setDoesNotAlias(F, 0);
1184    setDoesNotCapture(F, 1);
1185    break;
1186  case LibFunc::tmpfile:
1187    if (!FTy->getReturnType()->isPointerTy())
1188      return false;
1189    setDoesNotThrow(F);
1190    setDoesNotAlias(F, 0);
1191    break;
1192  case LibFunc::times:
1193    if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1194      return false;
1195    setDoesNotThrow(F);
1196    setDoesNotCapture(F, 1);
1197    break;
1198  case LibFunc::htonl:
1199  case LibFunc::htons:
1200  case LibFunc::ntohl:
1201  case LibFunc::ntohs:
1202    setDoesNotThrow(F);
1203    setDoesNotAccessMemory(F);
1204    break;
1205  case LibFunc::lstat:
1206    if (FTy->getNumParams() != 2 ||
1207        !FTy->getParamType(0)->isPointerTy() ||
1208        !FTy->getParamType(1)->isPointerTy())
1209      return false;
1210    setDoesNotThrow(F);
1211    setDoesNotCapture(F, 1);
1212    setDoesNotCapture(F, 2);
1213    break;
1214  case LibFunc::lchown:
1215    if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy())
1216      return false;
1217    setDoesNotThrow(F);
1218    setDoesNotCapture(F, 1);
1219    break;
1220  case LibFunc::qsort:
1221    if (FTy->getNumParams() != 4 || !FTy->getParamType(3)->isPointerTy())
1222      return false;
1223    // May throw; places call through function pointer.
1224    setDoesNotCapture(F, 4);
1225    break;
1226  case LibFunc::dunder_strdup:
1227  case LibFunc::dunder_strndup:
1228    if (FTy->getNumParams() < 1 ||
1229        !FTy->getReturnType()->isPointerTy() ||
1230        !FTy->getParamType(0)->isPointerTy())
1231      return false;
1232    setDoesNotThrow(F);
1233    setDoesNotAlias(F, 0);
1234    setDoesNotCapture(F, 1);
1235    break;
1236  case LibFunc::dunder_strtok_r:
1237    if (FTy->getNumParams() != 3 ||
1238        !FTy->getParamType(1)->isPointerTy())
1239      return false;
1240    setDoesNotThrow(F);
1241    setDoesNotCapture(F, 2);
1242    break;
1243  case LibFunc::under_IO_getc:
1244    if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1245      return false;
1246    setDoesNotThrow(F);
1247    setDoesNotCapture(F, 1);
1248    break;
1249  case LibFunc::under_IO_putc:
1250    if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1251      return false;
1252    setDoesNotThrow(F);
1253    setDoesNotCapture(F, 2);
1254    break;
1255  case LibFunc::dunder_isoc99_scanf:
1256    if (FTy->getNumParams() < 1 ||
1257        !FTy->getParamType(0)->isPointerTy())
1258      return false;
1259    setDoesNotThrow(F);
1260    setDoesNotCapture(F, 1);
1261    break;
1262  case LibFunc::stat64:
1263  case LibFunc::lstat64:
1264  case LibFunc::statvfs64:
1265  case LibFunc::dunder_isoc99_sscanf:
1266    if (FTy->getNumParams() < 1 ||
1267        !FTy->getParamType(0)->isPointerTy() ||
1268        !FTy->getParamType(1)->isPointerTy())
1269      return false;
1270    setDoesNotThrow(F);
1271    setDoesNotCapture(F, 1);
1272    setDoesNotCapture(F, 2);
1273    break;
1274  case LibFunc::fopen64:
1275    if (FTy->getNumParams() != 2 ||
1276        !FTy->getReturnType()->isPointerTy() ||
1277        !FTy->getParamType(0)->isPointerTy() ||
1278        !FTy->getParamType(1)->isPointerTy())
1279      return false;
1280    setDoesNotThrow(F);
1281    setDoesNotAlias(F, 0);
1282    setDoesNotCapture(F, 1);
1283    setDoesNotCapture(F, 2);
1284    break;
1285  case LibFunc::fseeko64:
1286  case LibFunc::ftello64:
1287    if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1288      return false;
1289    setDoesNotThrow(F);
1290    setDoesNotCapture(F, 1);
1291    break;
1292  case LibFunc::tmpfile64:
1293    if (!FTy->getReturnType()->isPointerTy())
1294      return false;
1295    setDoesNotThrow(F);
1296    setDoesNotAlias(F, 0);
1297    break;
1298  case LibFunc::fstat64:
1299  case LibFunc::fstatvfs64:
1300    if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1301      return false;
1302    setDoesNotThrow(F);
1303    setDoesNotCapture(F, 2);
1304    break;
1305  case LibFunc::open64:
1306    if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
1307      return false;
1308    // May throw; "open" is a valid pthread cancellation point.
1309    setDoesNotCapture(F, 1);
1310    break;
1311  default:
1312    // Didn't mark any attributes.
1313    return false;
1314  }
1315
1316  return true;
1317}
1318
1319/// annotateLibraryCalls - Adds attributes to well-known standard library
1320/// call declarations.
1321bool FunctionAttrs::annotateLibraryCalls(const CallGraphSCC &SCC) {
1322  bool MadeChange = false;
1323
1324  // Check each function in turn annotating well-known library function
1325  // declarations with attributes.
1326  for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
1327    Function *F = (*I)->getFunction();
1328
1329    if (F != 0 && F->isDeclaration())
1330      MadeChange |= inferPrototypeAttributes(*F);
1331  }
1332
1333  return MadeChange;
1334}
1335
1336bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) {
1337  AA = &getAnalysis<AliasAnalysis>();
1338  TLI = &getAnalysis<TargetLibraryInfo>();
1339
1340  bool Changed = annotateLibraryCalls(SCC);
1341  Changed |= AddReadAttrs(SCC);
1342  Changed |= AddNoCaptureAttrs(SCC);
1343  Changed |= AddNoAliasAttrs(SCC);
1344  return Changed;
1345}
1346