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