lib/Transforms/IPO/FunctionAttrs.cpp

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