contrib/llvm/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 /// \file
  11 /// This file implements interprocedural passes which walk the
  12 /// call-graph deducing and/or propagating function attributes.
  13 ///
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Transforms/IPO/FunctionAttrs.h"
  17 #include "llvm/Transforms/IPO.h"
  18 #include "llvm/ADT/SCCIterator.h"
  19 #include "llvm/ADT/SetVector.h"
  20 #include "llvm/ADT/SmallSet.h"
  21 #include "llvm/ADT/Statistic.h"
  22 #include "llvm/ADT/StringSwitch.h"
  23 #include "llvm/Analysis/AliasAnalysis.h"
  24 #include "llvm/Analysis/AssumptionCache.h"
  25 #include "llvm/Analysis/BasicAliasAnalysis.h"
  26 #include "llvm/Analysis/CallGraph.h"
  27 #include "llvm/Analysis/CallGraphSCCPass.h"
  28 #include "llvm/Analysis/CaptureTracking.h"
  29 #include "llvm/Analysis/TargetLibraryInfo.h"
  30 #include "llvm/Analysis/ValueTracking.h"
  31 #include "llvm/IR/GlobalVariable.h"
  32 #include "llvm/IR/InstIterator.h"
  33 #include "llvm/IR/IntrinsicInst.h"
  34 #include "llvm/IR/LLVMContext.h"
  35 #include "llvm/Support/Debug.h"
  36 #include "llvm/Support/raw_ostream.h"
  37 #include "llvm/Analysis/TargetLibraryInfo.h"
  38 using namespace llvm;
  39
  40 #define DEBUG_TYPE "functionattrs"
  41
  42 STATISTIC(NumReadNone, "Number of functions marked readnone");
  43 STATISTIC(NumReadOnly, "Number of functions marked readonly");
  44 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
  45 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
  46 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
  47 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
  48 STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull");
  49 STATISTIC(NumNoRecurse, "Number of functions marked as norecurse");
  50
  51 namespace {
  52 typedef SmallSetVector<Function *, 8> SCCNodeSet;
  53 }
  54
  55 namespace {
  56 /// The three kinds of memory access relevant to 'readonly' and
  57 /// 'readnone' attributes.
  58 enum MemoryAccessKind {
  59   MAK_ReadNone = 0,
  60   MAK_ReadOnly = 1,
  61   MAK_MayWrite = 2
  62 };
  63 }
  64
  65 static MemoryAccessKind checkFunctionMemoryAccess(Function &F, AAResults &AAR,
  66                                                   const SCCNodeSet &SCCNodes) {
  67   FunctionModRefBehavior MRB = AAR.getModRefBehavior(&F);
  68   if (MRB == FMRB_DoesNotAccessMemory)
  69     // Already perfect!
  70     return MAK_ReadNone;
  71
  72   // Non-exact function definitions may not be selected at link time, and an
  73   // alternative version that writes to memory may be selected.  See the comment
  74   // on GlobalValue::isDefinitionExact for more details.
  75   if (!F.hasExactDefinition()) {
  76     if (AliasAnalysis::onlyReadsMemory(MRB))
  77       return MAK_ReadOnly;
  78
  79     // Conservatively assume it writes to memory.
  80     return MAK_MayWrite;
  81   }
  82
  83   // Scan the function body for instructions that may read or write memory.
  84   bool ReadsMemory = false;
  85   for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
  86     Instruction *I = &*II;
  87
  88     // Some instructions can be ignored even if they read or write memory.
  89     // Detect these now, skipping to the next instruction if one is found.
  90     CallSite CS(cast<Value>(I));
  91     if (CS) {
  92       // Ignore calls to functions in the same SCC, as long as the call sites
  93       // don't have operand bundles.  Calls with operand bundles are allowed to
  94       // have memory effects not described by the memory effects of the call
  95       // target.
  96       if (!CS.hasOperandBundles() && CS.getCalledFunction() &&
  97           SCCNodes.count(CS.getCalledFunction()))
  98         continue;
  99       FunctionModRefBehavior MRB = AAR.getModRefBehavior(CS);
 100
 101       // If the call doesn't access memory, we're done.
 102       if (!(MRB & MRI_ModRef))
 103         continue;
 104
 105       if (!AliasAnalysis::onlyAccessesArgPointees(MRB)) {
 106         // The call could access any memory. If that includes writes, give up.
 107         if (MRB & MRI_Mod)
 108           return MAK_MayWrite;
 109         // If it reads, note it.
 110         if (MRB & MRI_Ref)
 111           ReadsMemory = true;
 112         continue;
 113       }
 114
 115       // Check whether all pointer arguments point to local memory, and
 116       // ignore calls that only access local memory.
 117       for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
 118            CI != CE; ++CI) {
 119         Value *Arg = *CI;
 120         if (!Arg->getType()->isPtrOrPtrVectorTy())
 121           continue;
 122
 123         AAMDNodes AAInfo;
 124         I->getAAMetadata(AAInfo);
 125         MemoryLocation Loc(Arg, MemoryLocation::UnknownSize, AAInfo);
 126
 127         // Skip accesses to local or constant memory as they don't impact the
 128         // externally visible mod/ref behavior.
 129         if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
 130           continue;
 131
 132         if (MRB & MRI_Mod)
 133           // Writes non-local memory.  Give up.
 134           return MAK_MayWrite;
 135         if (MRB & MRI_Ref)
 136           // Ok, it reads non-local memory.
 137           ReadsMemory = true;
 138       }
 139       continue;
 140     } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
 141       // Ignore non-volatile loads from local memory. (Atomic is okay here.)
 142       if (!LI->isVolatile()) {
 143         MemoryLocation Loc = MemoryLocation::get(LI);
 144         if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
 145           continue;
 146       }
 147     } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 148       // Ignore non-volatile stores to local memory. (Atomic is okay here.)
 149       if (!SI->isVolatile()) {
 150         MemoryLocation Loc = MemoryLocation::get(SI);
 151         if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
 152           continue;
 153       }
 154     } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) {
 155       // Ignore vaargs on local memory.
 156       MemoryLocation Loc = MemoryLocation::get(VI);
 157       if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
 158         continue;
 159     }
 160
 161     // Any remaining instructions need to be taken seriously!  Check if they
 162     // read or write memory.
 163     if (I->mayWriteToMemory())
 164       // Writes memory.  Just give up.
 165       return MAK_MayWrite;
 166
 167     // If this instruction may read memory, remember that.
 168     ReadsMemory |= I->mayReadFromMemory();
 169   }
 170
 171   return ReadsMemory ? MAK_ReadOnly : MAK_ReadNone;
 172 }
 173
 174 /// Deduce readonly/readnone attributes for the SCC.
 175 template <typename AARGetterT>
 176 static bool addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT AARGetter) {
 177   // Check if any of the functions in the SCC read or write memory.  If they
 178   // write memory then they can't be marked readnone or readonly.
 179   bool ReadsMemory = false;
 180   for (Function *F : SCCNodes) {
 181     // Call the callable parameter to look up AA results for this function.
 182     AAResults &AAR = AARGetter(*F);
 183
 184     switch (checkFunctionMemoryAccess(*F, AAR, SCCNodes)) {
 185     case MAK_MayWrite:
 186       return false;
 187     case MAK_ReadOnly:
 188       ReadsMemory = true;
 189       break;
 190     case MAK_ReadNone:
 191       // Nothing to do!
 192       break;
 193     }
 194   }
 195
 196   // Success!  Functions in this SCC do not access memory, or only read memory.
 197   // Give them the appropriate attribute.
 198   bool MadeChange = false;
 199   for (Function *F : SCCNodes) {
 200     if (F->doesNotAccessMemory())
 201       // Already perfect!
 202       continue;
 203
 204     if (F->onlyReadsMemory() && ReadsMemory)
 205       // No change.
 206       continue;
 207
 208     MadeChange = true;
 209
 210     // Clear out any existing attributes.
 211     AttrBuilder B;
 212     B.addAttribute(Attribute::ReadOnly).addAttribute(Attribute::ReadNone);
 213     F->removeAttributes(
 214         AttributeSet::FunctionIndex,
 215         AttributeSet::get(F->getContext(), AttributeSet::FunctionIndex, B));
 216
 217     // Add in the new attribute.
 218     F->addAttribute(AttributeSet::FunctionIndex,
 219                     ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone);
 220
 221     if (ReadsMemory)
 222       ++NumReadOnly;
 223     else
 224       ++NumReadNone;
 225   }
 226
 227   return MadeChange;
 228 }
 229
 230 namespace {
 231 /// For a given pointer Argument, this retains a list of Arguments of functions
 232 /// in the same SCC that the pointer data flows into. We use this to build an
 233 /// SCC of the arguments.
 234 struct ArgumentGraphNode {
 235   Argument *Definition;
 236   SmallVector<ArgumentGraphNode *, 4> Uses;
 237 };
 238
 239 class ArgumentGraph {
 240   // We store pointers to ArgumentGraphNode objects, so it's important that
 241   // that they not move around upon insert.
 242   typedef std::map<Argument *, ArgumentGraphNode> ArgumentMapTy;
 243
 244   ArgumentMapTy ArgumentMap;
 245
 246   // There is no root node for the argument graph, in fact:
 247   //   void f(int *x, int *y) { if (...) f(x, y); }
 248   // is an example where the graph is disconnected. The SCCIterator requires a
 249   // single entry point, so we maintain a fake ("synthetic") root node that
 250   // uses every node. Because the graph is directed and nothing points into
 251   // the root, it will not participate in any SCCs (except for its own).
 252   ArgumentGraphNode SyntheticRoot;
 253
 254 public:
 255   ArgumentGraph() { SyntheticRoot.Definition = nullptr; }
 256
 257   typedef SmallVectorImpl<ArgumentGraphNode *>::iterator iterator;
 258
 259   iterator begin() { return SyntheticRoot.Uses.begin(); }
 260   iterator end() { return SyntheticRoot.Uses.end(); }
 261   ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; }
 262
 263   ArgumentGraphNode *operator[](Argument *A) {
 264     ArgumentGraphNode &Node = ArgumentMap[A];
 265     Node.Definition = A;
 266     SyntheticRoot.Uses.push_back(&Node);
 267     return &Node;
 268   }
 269 };
 270
 271 /// This tracker checks whether callees are in the SCC, and if so it does not
 272 /// consider that a capture, instead adding it to the "Uses" list and
 273 /// continuing with the analysis.
 274 struct ArgumentUsesTracker : public CaptureTracker {
 275   ArgumentUsesTracker(const SCCNodeSet &SCCNodes)
 276       : Captured(false), SCCNodes(SCCNodes) {}
 277
 278   void tooManyUses() override { Captured = true; }
 279
 280   bool captured(const Use *U) override {
 281     CallSite CS(U->getUser());
 282     if (!CS.getInstruction()) {
 283       Captured = true;
 284       return true;
 285     }
 286
 287     Function *F = CS.getCalledFunction();
 288     if (!F || !F->hasExactDefinition() || !SCCNodes.count(F)) {
 289       Captured = true;
 290       return true;
 291     }
 292
 293     // Note: the callee and the two successor blocks *follow* the argument
 294     // operands.  This means there is no need to adjust UseIndex to account for
 295     // these.
 296
 297     unsigned UseIndex =
 298         std::distance(const_cast<const Use *>(CS.arg_begin()), U);
 299
 300     assert(UseIndex < CS.data_operands_size() &&
 301            "Indirect function calls should have been filtered above!");
 302
 303     if (UseIndex >= CS.getNumArgOperands()) {
 304       // Data operand, but not a argument operand -- must be a bundle operand
 305       assert(CS.hasOperandBundles() && "Must be!");
 306
 307       // CaptureTracking told us that we're being captured by an operand bundle
 308       // use.  In this case it does not matter if the callee is within our SCC
 309       // or not -- we've been captured in some unknown way, and we have to be
 310       // conservative.
 311       Captured = true;
 312       return true;
 313     }
 314
 315     if (UseIndex >= F->arg_size()) {
 316       assert(F->isVarArg() && "More params than args in non-varargs call");
 317       Captured = true;
 318       return true;
 319     }
 320
 321     Uses.push_back(&*std::next(F->arg_begin(), UseIndex));
 322     return false;
 323   }
 324
 325   bool Captured; // True only if certainly captured (used outside our SCC).
 326   SmallVector<Argument *, 4> Uses; // Uses within our SCC.
 327
 328   const SCCNodeSet &SCCNodes;
 329 };
 330 }
 331
 332 namespace llvm {
 333 template <> struct GraphTraits<ArgumentGraphNode *> {
 334   typedef ArgumentGraphNode NodeType;
 335   typedef SmallVectorImpl<ArgumentGraphNode *>::iterator ChildIteratorType;
 336
 337   static inline NodeType *getEntryNode(NodeType *A) { return A; }
 338   static inline ChildIteratorType child_begin(NodeType *N) {
 339     return N->Uses.begin();
 340   }
 341   static inline ChildIteratorType child_end(NodeType *N) {
 342     return N->Uses.end();
 343   }
 344 };
 345 template <>
 346 struct GraphTraits<ArgumentGraph *> : public GraphTraits<ArgumentGraphNode *> {
 347   static NodeType *getEntryNode(ArgumentGraph *AG) {
 348     return AG->getEntryNode();
 349   }
 350   static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
 351     return AG->begin();
 352   }
 353   static ChildIteratorType nodes_end(ArgumentGraph *AG) { return AG->end(); }
 354 };
 355 }
 356
 357 /// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
 358 static Attribute::AttrKind
 359 determinePointerReadAttrs(Argument *A,
 360                           const SmallPtrSet<Argument *, 8> &SCCNodes) {
 361
 362   SmallVector<Use *, 32> Worklist;
 363   SmallSet<Use *, 32> Visited;
 364
 365   // inalloca arguments are always clobbered by the call.
 366   if (A->hasInAllocaAttr())
 367     return Attribute::None;
 368
 369   bool IsRead = false;
 370   // We don't need to track IsWritten. If A is written to, return immediately.
 371
 372   for (Use &U : A->uses()) {
 373     Visited.insert(&U);
 374     Worklist.push_back(&U);
 375   }
 376
 377   while (!Worklist.empty()) {
 378     Use *U = Worklist.pop_back_val();
 379     Instruction *I = cast<Instruction>(U->getUser());
 380
 381     switch (I->getOpcode()) {
 382     case Instruction::BitCast:
 383     case Instruction::GetElementPtr:
 384     case Instruction::PHI:
 385     case Instruction::Select:
 386     case Instruction::AddrSpaceCast:
 387       // The original value is not read/written via this if the new value isn't.
 388       for (Use &UU : I->uses())
 389         if (Visited.insert(&UU).second)
 390           Worklist.push_back(&UU);
 391       break;
 392
 393     case Instruction::Call:
 394     case Instruction::Invoke: {
 395       bool Captures = true;
 396
 397       if (I->getType()->isVoidTy())
 398         Captures = false;
 399
 400       auto AddUsersToWorklistIfCapturing = [&] {
 401         if (Captures)
 402           for (Use &UU : I->uses())
 403             if (Visited.insert(&UU).second)
 404               Worklist.push_back(&UU);
 405       };
 406
 407       CallSite CS(I);
 408       if (CS.doesNotAccessMemory()) {
 409         AddUsersToWorklistIfCapturing();
 410         continue;
 411       }
 412
 413       Function *F = CS.getCalledFunction();
 414       if (!F) {
 415         if (CS.onlyReadsMemory()) {
 416           IsRead = true;
 417           AddUsersToWorklistIfCapturing();
 418           continue;
 419         }
 420         return Attribute::None;
 421       }
 422
 423       // Note: the callee and the two successor blocks *follow* the argument
 424       // operands.  This means there is no need to adjust UseIndex to account
 425       // for these.
 426
 427       unsigned UseIndex = std::distance(CS.arg_begin(), U);
 428
 429       // U cannot be the callee operand use: since we're exploring the
 430       // transitive uses of an Argument, having such a use be a callee would
 431       // imply the CallSite is an indirect call or invoke; and we'd take the
 432       // early exit above.
 433       assert(UseIndex < CS.data_operands_size() &&
 434              "Data operand use expected!");
 435
 436       bool IsOperandBundleUse = UseIndex >= CS.getNumArgOperands();
 437
 438       if (UseIndex >= F->arg_size() && !IsOperandBundleUse) {
 439         assert(F->isVarArg() && "More params than args in non-varargs call");
 440         return Attribute::None;
 441       }
 442
 443       Captures &= !CS.doesNotCapture(UseIndex);
 444
 445       // Since the optimizer (by design) cannot see the data flow corresponding
 446       // to a operand bundle use, these cannot participate in the optimistic SCC
 447       // analysis.  Instead, we model the operand bundle uses as arguments in
 448       // call to a function external to the SCC.
 449       if (!SCCNodes.count(&*std::next(F->arg_begin(), UseIndex)) ||
 450           IsOperandBundleUse) {
 451
 452         // The accessors used on CallSite here do the right thing for calls and
 453         // invokes with operand bundles.
 454
 455         if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(UseIndex))
 456           return Attribute::None;
 457         if (!CS.doesNotAccessMemory(UseIndex))
 458           IsRead = true;
 459       }
 460
 461       AddUsersToWorklistIfCapturing();
 462       break;
 463     }
 464
 465     case Instruction::Load:
 466       // A volatile load has side effects beyond what readonly can be relied
 467       // upon.
 468       if (cast<LoadInst>(I)->isVolatile())
 469         return Attribute::None;
 470
 471       IsRead = true;
 472       break;
 473
 474     case Instruction::ICmp:
 475     case Instruction::Ret:
 476       break;
 477
 478     default:
 479       return Attribute::None;
 480     }
 481   }
 482
 483   return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
 484 }
 485
 486 /// Deduce nocapture attributes for the SCC.
 487 static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) {
 488   bool Changed = false;
 489
 490   ArgumentGraph AG;
 491
 492   AttrBuilder B;
 493   B.addAttribute(Attribute::NoCapture);
 494
 495   // Check each function in turn, determining which pointer arguments are not
 496   // captured.
 497   for (Function *F : SCCNodes) {
 498     // We can infer and propagate function attributes only when we know that the
 499     // definition we'll get at link time is *exactly* the definition we see now.
 500     // For more details, see GlobalValue::mayBeDerefined.
 501     if (!F->hasExactDefinition())
 502       continue;
 503
 504     // Functions that are readonly (or readnone) and nounwind and don't return
 505     // a value can't capture arguments. Don't analyze them.
 506     if (F->onlyReadsMemory() && F->doesNotThrow() &&
 507         F->getReturnType()->isVoidTy()) {
 508       for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
 509            ++A) {
 510         if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
 511           A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
 512           ++NumNoCapture;
 513           Changed = true;
 514         }
 515       }
 516       continue;
 517     }
 518
 519     for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
 520          ++A) {
 521       if (!A->getType()->isPointerTy())
 522         continue;
 523       bool HasNonLocalUses = false;
 524       if (!A->hasNoCaptureAttr()) {
 525         ArgumentUsesTracker Tracker(SCCNodes);
 526         PointerMayBeCaptured(&*A, &Tracker);
 527         if (!Tracker.Captured) {
 528           if (Tracker.Uses.empty()) {
 529             // If it's trivially not captured, mark it nocapture now.
 530             A->addAttr(
 531                 AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
 532             ++NumNoCapture;
 533             Changed = true;
 534           } else {
 535             // If it's not trivially captured and not trivially not captured,
 536             // then it must be calling into another function in our SCC. Save
 537             // its particulars for Argument-SCC analysis later.
 538             ArgumentGraphNode *Node = AG[&*A];
 539             for (Argument *Use : Tracker.Uses) {
 540               Node->Uses.push_back(AG[Use]);
 541               if (Use != &*A)
 542                 HasNonLocalUses = true;
 543             }
 544           }
 545         }
 546         // Otherwise, it's captured. Don't bother doing SCC analysis on it.
 547       }
 548       if (!HasNonLocalUses && !A->onlyReadsMemory()) {
 549         // Can we determine that it's readonly/readnone without doing an SCC?
 550         // Note that we don't allow any calls at all here, or else our result
 551         // will be dependent on the iteration order through the functions in the
 552         // SCC.
 553         SmallPtrSet<Argument *, 8> Self;
 554         Self.insert(&*A);
 555         Attribute::AttrKind R = determinePointerReadAttrs(&*A, Self);
 556         if (R != Attribute::None) {
 557           AttrBuilder B;
 558           B.addAttribute(R);
 559           A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
 560           Changed = true;
 561           R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
 562         }
 563       }
 564     }
 565   }
 566
 567   // The graph we've collected is partial because we stopped scanning for
 568   // argument uses once we solved the argument trivially. These partial nodes
 569   // show up as ArgumentGraphNode objects with an empty Uses list, and for
 570   // these nodes the final decision about whether they capture has already been
 571   // made.  If the definition doesn't have a 'nocapture' attribute by now, it
 572   // captures.
 573
 574   for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
 575     const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
 576     if (ArgumentSCC.size() == 1) {
 577       if (!ArgumentSCC[0]->Definition)
 578         continue; // synthetic root node
 579
 580       // eg. "void f(int* x) { if (...) f(x); }"
 581       if (ArgumentSCC[0]->Uses.size() == 1 &&
 582           ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
 583         Argument *A = ArgumentSCC[0]->Definition;
 584         A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
 585         ++NumNoCapture;
 586         Changed = true;
 587       }
 588       continue;
 589     }
 590
 591     bool SCCCaptured = false;
 592     for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
 593          I != E && !SCCCaptured; ++I) {
 594       ArgumentGraphNode *Node = *I;
 595       if (Node->Uses.empty()) {
 596         if (!Node->Definition->hasNoCaptureAttr())
 597           SCCCaptured = true;
 598       }
 599     }
 600     if (SCCCaptured)
 601       continue;
 602
 603     SmallPtrSet<Argument *, 8> ArgumentSCCNodes;
 604     // Fill ArgumentSCCNodes with the elements of the ArgumentSCC.  Used for
 605     // quickly looking up whether a given Argument is in this ArgumentSCC.
 606     for (ArgumentGraphNode *I : ArgumentSCC) {
 607       ArgumentSCCNodes.insert(I->Definition);
 608     }
 609
 610     for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
 611          I != E && !SCCCaptured; ++I) {
 612       ArgumentGraphNode *N = *I;
 613       for (ArgumentGraphNode *Use : N->Uses) {
 614         Argument *A = Use->Definition;
 615         if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
 616           continue;
 617         SCCCaptured = true;
 618         break;
 619       }
 620     }
 621     if (SCCCaptured)
 622       continue;
 623
 624     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
 625       Argument *A = ArgumentSCC[i]->Definition;
 626       A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
 627       ++NumNoCapture;
 628       Changed = true;
 629     }
 630
 631     // We also want to compute readonly/readnone. With a small number of false
 632     // negatives, we can assume that any pointer which is captured isn't going
 633     // to be provably readonly or readnone, since by definition we can't
 634     // analyze all uses of a captured pointer.
 635     //
 636     // The false negatives happen when the pointer is captured by a function
 637     // that promises readonly/readnone behaviour on the pointer, then the
 638     // pointer's lifetime ends before anything that writes to arbitrary memory.
 639     // Also, a readonly/readnone pointer may be returned, but returning a
 640     // pointer is capturing it.
 641
 642     Attribute::AttrKind ReadAttr = Attribute::ReadNone;
 643     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
 644       Argument *A = ArgumentSCC[i]->Definition;
 645       Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes);
 646       if (K == Attribute::ReadNone)
 647         continue;
 648       if (K == Attribute::ReadOnly) {
 649         ReadAttr = Attribute::ReadOnly;
 650         continue;
 651       }
 652       ReadAttr = K;
 653       break;
 654     }
 655
 656     if (ReadAttr != Attribute::None) {
 657       AttrBuilder B, R;
 658       B.addAttribute(ReadAttr);
 659       R.addAttribute(Attribute::ReadOnly).addAttribute(Attribute::ReadNone);
 660       for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
 661         Argument *A = ArgumentSCC[i]->Definition;
 662         // Clear out existing readonly/readnone attributes
 663         A->removeAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, R));
 664         A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
 665         ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
 666         Changed = true;
 667       }
 668     }
 669   }
 670
 671   return Changed;
 672 }
 673
 674 /// Tests whether a function is "malloc-like".
 675 ///
 676 /// A function is "malloc-like" if it returns either null or a pointer that
 677 /// doesn't alias any other pointer visible to the caller.
 678 static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) {
 679   SmallSetVector<Value *, 8> FlowsToReturn;
 680   for (BasicBlock &BB : *F)
 681     if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
 682       FlowsToReturn.insert(Ret->getReturnValue());
 683
 684   for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
 685     Value *RetVal = FlowsToReturn[i];
 686
 687     if (Constant *C = dyn_cast<Constant>(RetVal)) {
 688       if (!C->isNullValue() && !isa<UndefValue>(C))
 689         return false;
 690
 691       continue;
 692     }
 693
 694     if (isa<Argument>(RetVal))
 695       return false;
 696
 697     if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
 698       switch (RVI->getOpcode()) {
 699       // Extend the analysis by looking upwards.
 700       case Instruction::BitCast:
 701       case Instruction::GetElementPtr:
 702       case Instruction::AddrSpaceCast:
 703         FlowsToReturn.insert(RVI->getOperand(0));
 704         continue;
 705       case Instruction::Select: {
 706         SelectInst *SI = cast<SelectInst>(RVI);
 707         FlowsToReturn.insert(SI->getTrueValue());
 708         FlowsToReturn.insert(SI->getFalseValue());
 709         continue;
 710       }
 711       case Instruction::PHI: {
 712         PHINode *PN = cast<PHINode>(RVI);
 713         for (Value *IncValue : PN->incoming_values())
 714           FlowsToReturn.insert(IncValue);
 715         continue;
 716       }
 717
 718       // Check whether the pointer came from an allocation.
 719       case Instruction::Alloca:
 720         break;
 721       case Instruction::Call:
 722       case Instruction::Invoke: {
 723         CallSite CS(RVI);
 724         if (CS.paramHasAttr(0, Attribute::NoAlias))
 725           break;
 726         if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
 727           break;
 728       } // fall-through
 729       default:
 730         return false; // Did not come from an allocation.
 731       }
 732
 733     if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
 734       return false;
 735   }
 736
 737   return true;
 738 }
 739
 740 /// Deduce noalias attributes for the SCC.
 741 static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes) {
 742   // Check each function in turn, determining which functions return noalias
 743   // pointers.
 744   for (Function *F : SCCNodes) {
 745     // Already noalias.
 746     if (F->doesNotAlias(0))
 747       continue;
 748
 749     // We can infer and propagate function attributes only when we know that the
 750     // definition we'll get at link time is *exactly* the definition we see now.
 751     // For more details, see GlobalValue::mayBeDerefined.
 752     if (!F->hasExactDefinition())
 753       return false;
 754
 755     // We annotate noalias return values, which are only applicable to
 756     // pointer types.
 757     if (!F->getReturnType()->isPointerTy())
 758       continue;
 759
 760     if (!isFunctionMallocLike(F, SCCNodes))
 761       return false;
 762   }
 763
 764   bool MadeChange = false;
 765   for (Function *F : SCCNodes) {
 766     if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy())
 767       continue;
 768
 769     F->setDoesNotAlias(0);
 770     ++NumNoAlias;
 771     MadeChange = true;
 772   }
 773
 774   return MadeChange;
 775 }
 776
 777 /// Tests whether this function is known to not return null.
 778 ///
 779 /// Requires that the function returns a pointer.
 780 ///
 781 /// Returns true if it believes the function will not return a null, and sets
 782 /// \p Speculative based on whether the returned conclusion is a speculative
 783 /// conclusion due to SCC calls.
 784 static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes,
 785                             bool &Speculative) {
 786   assert(F->getReturnType()->isPointerTy() &&
 787          "nonnull only meaningful on pointer types");
 788   Speculative = false;
 789
 790   SmallSetVector<Value *, 8> FlowsToReturn;
 791   for (BasicBlock &BB : *F)
 792     if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
 793       FlowsToReturn.insert(Ret->getReturnValue());
 794
 795   for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
 796     Value *RetVal = FlowsToReturn[i];
 797
 798     // If this value is locally known to be non-null, we're good
 799     if (isKnownNonNull(RetVal))
 800       continue;
 801
 802     // Otherwise, we need to look upwards since we can't make any local
 803     // conclusions.
 804     Instruction *RVI = dyn_cast<Instruction>(RetVal);
 805     if (!RVI)
 806       return false;
 807     switch (RVI->getOpcode()) {
 808     // Extend the analysis by looking upwards.
 809     case Instruction::BitCast:
 810     case Instruction::GetElementPtr:
 811     case Instruction::AddrSpaceCast:
 812       FlowsToReturn.insert(RVI->getOperand(0));
 813       continue;
 814     case Instruction::Select: {
 815       SelectInst *SI = cast<SelectInst>(RVI);
 816       FlowsToReturn.insert(SI->getTrueValue());
 817       FlowsToReturn.insert(SI->getFalseValue());
 818       continue;
 819     }
 820     case Instruction::PHI: {
 821       PHINode *PN = cast<PHINode>(RVI);
 822       for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 823         FlowsToReturn.insert(PN->getIncomingValue(i));
 824       continue;
 825     }
 826     case Instruction::Call:
 827     case Instruction::Invoke: {
 828       CallSite CS(RVI);
 829       Function *Callee = CS.getCalledFunction();
 830       // A call to a node within the SCC is assumed to return null until
 831       // proven otherwise
 832       if (Callee && SCCNodes.count(Callee)) {
 833         Speculative = true;
 834         continue;
 835       }
 836       return false;
 837     }
 838     default:
 839       return false; // Unknown source, may be null
 840     };
 841     llvm_unreachable("should have either continued or returned");
 842   }
 843
 844   return true;
 845 }
 846
 847 /// Deduce nonnull attributes for the SCC.
 848 static bool addNonNullAttrs(const SCCNodeSet &SCCNodes) {
 849   // Speculative that all functions in the SCC return only nonnull
 850   // pointers.  We may refute this as we analyze functions.
 851   bool SCCReturnsNonNull = true;
 852
 853   bool MadeChange = false;
 854
 855   // Check each function in turn, determining which functions return nonnull
 856   // pointers.
 857   for (Function *F : SCCNodes) {
 858     // Already nonnull.
 859     if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex,
 860                                         Attribute::NonNull))
 861       continue;
 862
 863     // We can infer and propagate function attributes only when we know that the
 864     // definition we'll get at link time is *exactly* the definition we see now.
 865     // For more details, see GlobalValue::mayBeDerefined.
 866     if (!F->hasExactDefinition())
 867       return false;
 868
 869     // We annotate nonnull return values, which are only applicable to
 870     // pointer types.
 871     if (!F->getReturnType()->isPointerTy())
 872       continue;
 873
 874     bool Speculative = false;
 875     if (isReturnNonNull(F, SCCNodes, Speculative)) {
 876       if (!Speculative) {
 877         // Mark the function eagerly since we may discover a function
 878         // which prevents us from speculating about the entire SCC
 879         DEBUG(dbgs() << "Eagerly marking " << F->getName() << " as nonnull\n");
 880         F->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull);
 881         ++NumNonNullReturn;
 882         MadeChange = true;
 883       }
 884       continue;
 885     }
 886     // At least one function returns something which could be null, can't
 887     // speculate any more.
 888     SCCReturnsNonNull = false;
 889   }
 890
 891   if (SCCReturnsNonNull) {
 892     for (Function *F : SCCNodes) {
 893       if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex,
 894                                           Attribute::NonNull) ||
 895           !F->getReturnType()->isPointerTy())
 896         continue;
 897
 898       DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
 899       F->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull);
 900       ++NumNonNullReturn;
 901       MadeChange = true;
 902     }
 903   }
 904
 905   return MadeChange;
 906 }
 907
 908 /// Remove the convergent attribute from all functions in the SCC if every
 909 /// callsite within the SCC is not convergent (except for calls to functions
 910 /// within the SCC).  Returns true if changes were made.
 911 static bool removeConvergentAttrs(const SCCNodeSet &SCCNodes) {
 912   // For every function in SCC, ensure that either
 913   //  * it is not convergent, or
 914   //  * we can remove its convergent attribute.
 915   bool HasConvergentFn = false;
 916   for (Function *F : SCCNodes) {
 917     if (!F->isConvergent()) continue;
 918     HasConvergentFn = true;
 919
 920     // Can't remove convergent from function declarations.
 921     if (F->isDeclaration()) return false;
 922
 923     // Can't remove convergent if any of our functions has a convergent call to a
 924     // function not in the SCC.
 925     for (Instruction &I : instructions(*F)) {
 926       CallSite CS(&I);
 927       // Bail if CS is a convergent call to a function not in the SCC.
 928       if (CS && CS.isConvergent() &&
 929           SCCNodes.count(CS.getCalledFunction()) == 0)
 930         return false;
 931     }
 932   }
 933
 934   // If the SCC doesn't have any convergent functions, we have nothing to do.
 935   if (!HasConvergentFn) return false;
 936
 937   // If we got here, all of the calls the SCC makes to functions not in the SCC
 938   // are non-convergent.  Therefore all of the SCC's functions can also be made
 939   // non-convergent.  We'll remove the attr from the callsites in
 940   // InstCombineCalls.
 941   for (Function *F : SCCNodes) {
 942     if (!F->isConvergent()) continue;
 943
 944     DEBUG(dbgs() << "Removing convergent attr from fn " << F->getName()
 945                  << "\n");
 946     F->setNotConvergent();
 947   }
 948   return true;
 949 }
 950
 951 static bool setDoesNotRecurse(Function &F) {
 952   if (F.doesNotRecurse())
 953     return false;
 954   F.setDoesNotRecurse();
 955   ++NumNoRecurse;
 956   return true;
 957 }
 958
 959 static bool addNoRecurseAttrs(const SCCNodeSet &SCCNodes) {
 960   // Try and identify functions that do not recurse.
 961
 962   // If the SCC contains multiple nodes we know for sure there is recursion.
 963   if (SCCNodes.size() != 1)
 964     return false;
 965
 966   Function *F = *SCCNodes.begin();
 967   if (!F || F->isDeclaration() || F->doesNotRecurse())
 968     return false;
 969
 970   // If all of the calls in F are identifiable and are to norecurse functions, F
 971   // is norecurse. This check also detects self-recursion as F is not currently
 972   // marked norecurse, so any called from F to F will not be marked norecurse.
 973   for (Instruction &I : instructions(*F))
 974     if (auto CS = CallSite(&I)) {
 975       Function *Callee = CS.getCalledFunction();
 976       if (!Callee || Callee == F || !Callee->doesNotRecurse())
 977         // Function calls a potentially recursive function.
 978         return false;
 979     }
 980
 981   // Every call was to a non-recursive function other than this function, and
 982   // we have no indirect recursion as the SCC size is one. This function cannot
 983   // recurse.
 984   return setDoesNotRecurse(*F);
 985 }
 986
 987 PreservedAnalyses PostOrderFunctionAttrsPass::run(LazyCallGraph::SCC &C,
 988                                                   CGSCCAnalysisManager &AM) {
 989   FunctionAnalysisManager &FAM =
 990       AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C).getManager();
 991
 992   // We pass a lambda into functions to wire them up to the analysis manager
 993   // for getting function analyses.
 994   auto AARGetter = [&](Function &F) -> AAResults & {
 995     return FAM.getResult<AAManager>(F);
 996   };
 997
 998   // Fill SCCNodes with the elements of the SCC. Also track whether there are
 999   // any external or opt-none nodes that will prevent us from optimizing any
1000   // part of the SCC.
1001   SCCNodeSet SCCNodes;
1002   bool HasUnknownCall = false;
1003   for (LazyCallGraph::Node &N : C) {
1004     Function &F = N.getFunction();
1005     if (F.hasFnAttribute(Attribute::OptimizeNone)) {
1006       // Treat any function we're trying not to optimize as if it were an
1007       // indirect call and omit it from the node set used below.
1008       HasUnknownCall = true;
1009       continue;
1010     }
1011     // Track whether any functions in this SCC have an unknown call edge.
1012     // Note: if this is ever a performance hit, we can common it with
1013     // subsequent routines which also do scans over the instructions of the
1014     // function.
1015     if (!HasUnknownCall)
1016       for (Instruction &I : instructions(F))
1017         if (auto CS = CallSite(&I))
1018           if (!CS.getCalledFunction()) {
1019             HasUnknownCall = true;
1020             break;
1021           }
1022
1023     SCCNodes.insert(&F);
1024   }
1025
1026   bool Changed = false;
1027   Changed |= addReadAttrs(SCCNodes, AARGetter);
1028   Changed |= addArgumentAttrs(SCCNodes);
1029
1030   // If we have no external nodes participating in the SCC, we can deduce some
1031   // more precise attributes as well.
1032   if (!HasUnknownCall) {
1033     Changed |= addNoAliasAttrs(SCCNodes);
1034     Changed |= addNonNullAttrs(SCCNodes);
1035     Changed |= removeConvergentAttrs(SCCNodes);
1036     Changed |= addNoRecurseAttrs(SCCNodes);
1037   }
1038
1039   return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
1040 }
1041
1042 namespace {
1043 struct PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass {
1044   static char ID; // Pass identification, replacement for typeid
1045   PostOrderFunctionAttrsLegacyPass() : CallGraphSCCPass(ID) {
1046     initializePostOrderFunctionAttrsLegacyPassPass(*PassRegistry::getPassRegistry());
1047   }
1048
1049   bool runOnSCC(CallGraphSCC &SCC) override;
1050
1051   void getAnalysisUsage(AnalysisUsage &AU) const override {
1052     AU.setPreservesCFG();
1053     AU.addRequired<AssumptionCacheTracker>();
1054     getAAResultsAnalysisUsage(AU);
1055     CallGraphSCCPass::getAnalysisUsage(AU);
1056   }
1057 };
1058 }
1059
1060 char PostOrderFunctionAttrsLegacyPass::ID = 0;
1061 INITIALIZE_PASS_BEGIN(PostOrderFunctionAttrsLegacyPass, "functionattrs",
1062                       "Deduce function attributes", false, false)
1063 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1064 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
1065 INITIALIZE_PASS_END(PostOrderFunctionAttrsLegacyPass, "functionattrs",
1066                     "Deduce function attributes", false, false)
1067
1068 Pass *llvm::createPostOrderFunctionAttrsLegacyPass() { return new PostOrderFunctionAttrsLegacyPass(); }
1069
1070 template <typename AARGetterT>
1071 static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter) {
1072   bool Changed = false;
1073
1074   // Fill SCCNodes with the elements of the SCC. Used for quickly looking up
1075   // whether a given CallGraphNode is in this SCC. Also track whether there are
1076   // any external or opt-none nodes that will prevent us from optimizing any
1077   // part of the SCC.
1078   SCCNodeSet SCCNodes;
1079   bool ExternalNode = false;
1080   for (CallGraphNode *I : SCC) {
1081     Function *F = I->getFunction();
1082     if (!F || F->hasFnAttribute(Attribute::OptimizeNone)) {
1083       // External node or function we're trying not to optimize - we both avoid
1084       // transform them and avoid leveraging information they provide.
1085       ExternalNode = true;
1086       continue;
1087     }
1088
1089     SCCNodes.insert(F);
1090   }
1091
1092   Changed |= addReadAttrs(SCCNodes, AARGetter);
1093   Changed |= addArgumentAttrs(SCCNodes);
1094
1095   // If we have no external nodes participating in the SCC, we can deduce some
1096   // more precise attributes as well.
1097   if (!ExternalNode) {
1098     Changed |= addNoAliasAttrs(SCCNodes);
1099     Changed |= addNonNullAttrs(SCCNodes);
1100     Changed |= removeConvergentAttrs(SCCNodes);
1101     Changed |= addNoRecurseAttrs(SCCNodes);
1102   }
1103
1104   return Changed;
1105 }
1106
1107 bool PostOrderFunctionAttrsLegacyPass::runOnSCC(CallGraphSCC &SCC) {
1108   if (skipSCC(SCC))
1109     return false;
1110
1111   // We compute dedicated AA results for each function in the SCC as needed. We
1112   // use a lambda referencing external objects so that they live long enough to
1113   // be queried, but we re-use them each time.
1114   Optional<BasicAAResult> BAR;
1115   Optional<AAResults> AAR;
1116   auto AARGetter = [&](Function &F) -> AAResults & {
1117     BAR.emplace(createLegacyPMBasicAAResult(*this, F));
1118     AAR.emplace(createLegacyPMAAResults(*this, F, *BAR));
1119     return *AAR;
1120   };
1121
1122   return runImpl(SCC, AARGetter);
1123 }
1124
1125 namespace {
1126 struct ReversePostOrderFunctionAttrsLegacyPass : public ModulePass {
1127   static char ID; // Pass identification, replacement for typeid
1128   ReversePostOrderFunctionAttrsLegacyPass() : ModulePass(ID) {
1129     initializeReversePostOrderFunctionAttrsLegacyPassPass(*PassRegistry::getPassRegistry());
1130   }
1131
1132   bool runOnModule(Module &M) override;
1133
1134   void getAnalysisUsage(AnalysisUsage &AU) const override {
1135     AU.setPreservesCFG();
1136     AU.addRequired<CallGraphWrapperPass>();
1137     AU.addPreserved<CallGraphWrapperPass>();
1138   }
1139 };
1140 }
1141
1142 char ReversePostOrderFunctionAttrsLegacyPass::ID = 0;
1143 INITIALIZE_PASS_BEGIN(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs",
1144                       "Deduce function attributes in RPO", false, false)
1145 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
1146 INITIALIZE_PASS_END(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs",
1147                     "Deduce function attributes in RPO", false, false)
1148
1149 Pass *llvm::createReversePostOrderFunctionAttrsPass() {
1150   return new ReversePostOrderFunctionAttrsLegacyPass();
1151 }
1152
1153 static bool addNoRecurseAttrsTopDown(Function &F) {
1154   // We check the preconditions for the function prior to calling this to avoid
1155   // the cost of building up a reversible post-order list. We assert them here
1156   // to make sure none of the invariants this relies on were violated.
1157   assert(!F.isDeclaration() && "Cannot deduce norecurse without a definition!");
1158   assert(!F.doesNotRecurse() &&
1159          "This function has already been deduced as norecurs!");
1160   assert(F.hasInternalLinkage() &&
1161          "Can only do top-down deduction for internal linkage functions!");
1162
1163   // If F is internal and all of its uses are calls from a non-recursive
1164   // functions, then none of its calls could in fact recurse without going
1165   // through a function marked norecurse, and so we can mark this function too
1166   // as norecurse. Note that the uses must actually be calls -- otherwise
1167   // a pointer to this function could be returned from a norecurse function but
1168   // this function could be recursively (indirectly) called. Note that this
1169   // also detects if F is directly recursive as F is not yet marked as
1170   // a norecurse function.
1171   for (auto *U : F.users()) {
1172     auto *I = dyn_cast<Instruction>(U);
1173     if (!I)
1174       return false;
1175     CallSite CS(I);
1176     if (!CS || !CS.getParent()->getParent()->doesNotRecurse())
1177       return false;
1178   }
1179   return setDoesNotRecurse(F);
1180 }
1181
1182 static bool deduceFunctionAttributeInRPO(Module &M, CallGraph &CG) {
1183   // We only have a post-order SCC traversal (because SCCs are inherently
1184   // discovered in post-order), so we accumulate them in a vector and then walk
1185   // it in reverse. This is simpler than using the RPO iterator infrastructure
1186   // because we need to combine SCC detection and the PO walk of the call
1187   // graph. We can also cheat egregiously because we're primarily interested in
1188   // synthesizing norecurse and so we can only save the singular SCCs as SCCs
1189   // with multiple functions in them will clearly be recursive.
1190   SmallVector<Function *, 16> Worklist;
1191   for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
1192     if (I->size() != 1)
1193       continue;
1194
1195     Function *F = I->front()->getFunction();
1196     if (F && !F->isDeclaration() && !F->doesNotRecurse() &&
1197         F->hasInternalLinkage())
1198       Worklist.push_back(F);
1199   }
1200
1201   bool Changed = false;
1202   for (auto *F : reverse(Worklist))
1203     Changed |= addNoRecurseAttrsTopDown(*F);
1204
1205   return Changed;
1206 }
1207
1208 bool ReversePostOrderFunctionAttrsLegacyPass::runOnModule(Module &M) {
1209   if (skipModule(M))
1210     return false;
1211
1212   auto &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
1213
1214   return deduceFunctionAttributeInRPO(M, CG);
1215 }
1216
1217 PreservedAnalyses
1218 ReversePostOrderFunctionAttrsPass::run(Module &M, AnalysisManager<Module> &AM) {
1219   auto &CG = AM.getResult<CallGraphAnalysis>(M);
1220
1221   bool Changed = deduceFunctionAttributeInRPO(M, CG);
1222   if (!Changed)
1223     return PreservedAnalyses::all();
1224   PreservedAnalyses PA;
1225   PA.preserve<CallGraphAnalysis>();
1226   return PA;
1227 }