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 ArgumentGraphNode *NodeRef;
 336   typedef SmallVectorImpl<ArgumentGraphNode *>::iterator ChildIteratorType;
 337
 338   static inline NodeType *getEntryNode(NodeType *A) { return A; }
 339   static inline ChildIteratorType child_begin(NodeType *N) {
 340     return N->Uses.begin();
 341   }
 342   static inline ChildIteratorType child_end(NodeType *N) {
 343     return N->Uses.end();
 344   }
 345 };
 346 template <>
 347 struct GraphTraits<ArgumentGraph *> : public GraphTraits<ArgumentGraphNode *> {
 348   static NodeType *getEntryNode(ArgumentGraph *AG) {
 349     return AG->getEntryNode();
 350   }
 351   static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
 352     return AG->begin();
 353   }
 354   static ChildIteratorType nodes_end(ArgumentGraph *AG) { return AG->end(); }
 355 };
 356 }
 357
 358 /// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
 359 static Attribute::AttrKind
 360 determinePointerReadAttrs(Argument *A,
 361                           const SmallPtrSet<Argument *, 8> &SCCNodes) {
 362
 363   SmallVector<Use *, 32> Worklist;
 364   SmallSet<Use *, 32> Visited;
 365
 366   // inalloca arguments are always clobbered by the call.
 367   if (A->hasInAllocaAttr())
 368     return Attribute::None;
 369
 370   bool IsRead = false;
 371   // We don't need to track IsWritten. If A is written to, return immediately.
 372
 373   for (Use &U : A->uses()) {
 374     Visited.insert(&U);
 375     Worklist.push_back(&U);
 376   }
 377
 378   while (!Worklist.empty()) {
 379     Use *U = Worklist.pop_back_val();
 380     Instruction *I = cast<Instruction>(U->getUser());
 381
 382     switch (I->getOpcode()) {
 383     case Instruction::BitCast:
 384     case Instruction::GetElementPtr:
 385     case Instruction::PHI:
 386     case Instruction::Select:
 387     case Instruction::AddrSpaceCast:
 388       // The original value is not read/written via this if the new value isn't.
 389       for (Use &UU : I->uses())
 390         if (Visited.insert(&UU).second)
 391           Worklist.push_back(&UU);
 392       break;
 393
 394     case Instruction::Call:
 395     case Instruction::Invoke: {
 396       bool Captures = true;
 397
 398       if (I->getType()->isVoidTy())
 399         Captures = false;
 400
 401       auto AddUsersToWorklistIfCapturing = [&] {
 402         if (Captures)
 403           for (Use &UU : I->uses())
 404             if (Visited.insert(&UU).second)
 405               Worklist.push_back(&UU);
 406       };
 407
 408       CallSite CS(I);
 409       if (CS.doesNotAccessMemory()) {
 410         AddUsersToWorklistIfCapturing();
 411         continue;
 412       }
 413
 414       Function *F = CS.getCalledFunction();
 415       if (!F) {
 416         if (CS.onlyReadsMemory()) {
 417           IsRead = true;
 418           AddUsersToWorklistIfCapturing();
 419           continue;
 420         }
 421         return Attribute::None;
 422       }
 423
 424       // Note: the callee and the two successor blocks *follow* the argument
 425       // operands.  This means there is no need to adjust UseIndex to account
 426       // for these.
 427
 428       unsigned UseIndex = std::distance(CS.arg_begin(), U);
 429
 430       // U cannot be the callee operand use: since we're exploring the
 431       // transitive uses of an Argument, having such a use be a callee would
 432       // imply the CallSite is an indirect call or invoke; and we'd take the
 433       // early exit above.
 434       assert(UseIndex < CS.data_operands_size() &&
 435              "Data operand use expected!");
 436
 437       bool IsOperandBundleUse = UseIndex >= CS.getNumArgOperands();
 438
 439       if (UseIndex >= F->arg_size() && !IsOperandBundleUse) {
 440         assert(F->isVarArg() && "More params than args in non-varargs call");
 441         return Attribute::None;
 442       }
 443
 444       Captures &= !CS.doesNotCapture(UseIndex);
 445
 446       // Since the optimizer (by design) cannot see the data flow corresponding
 447       // to a operand bundle use, these cannot participate in the optimistic SCC
 448       // analysis.  Instead, we model the operand bundle uses as arguments in
 449       // call to a function external to the SCC.
 450       if (!SCCNodes.count(&*std::next(F->arg_begin(), UseIndex)) ||
 451           IsOperandBundleUse) {
 452
 453         // The accessors used on CallSite here do the right thing for calls and
 454         // invokes with operand bundles.
 455
 456         if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(UseIndex))
 457           return Attribute::None;
 458         if (!CS.doesNotAccessMemory(UseIndex))
 459           IsRead = true;
 460       }
 461
 462       AddUsersToWorklistIfCapturing();
 463       break;
 464     }
 465
 466     case Instruction::Load:
 467       // A volatile load has side effects beyond what readonly can be relied
 468       // upon.
 469       if (cast<LoadInst>(I)->isVolatile())
 470         return Attribute::None;
 471
 472       IsRead = true;
 473       break;
 474
 475     case Instruction::ICmp:
 476     case Instruction::Ret:
 477       break;
 478
 479     default:
 480       return Attribute::None;
 481     }
 482   }
 483
 484   return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
 485 }
 486
 487 /// Deduce nocapture attributes for the SCC.
 488 static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) {
 489   bool Changed = false;
 490
 491   ArgumentGraph AG;
 492
 493   AttrBuilder B;
 494   B.addAttribute(Attribute::NoCapture);
 495
 496   // Check each function in turn, determining which pointer arguments are not
 497   // captured.
 498   for (Function *F : SCCNodes) {
 499     // We can infer and propagate function attributes only when we know that the
 500     // definition we'll get at link time is *exactly* the definition we see now.
 501     // For more details, see GlobalValue::mayBeDerefined.
 502     if (!F->hasExactDefinition())
 503       continue;
 504
 505     // Functions that are readonly (or readnone) and nounwind and don't return
 506     // a value can't capture arguments. Don't analyze them.
 507     if (F->onlyReadsMemory() && F->doesNotThrow() &&
 508         F->getReturnType()->isVoidTy()) {
 509       for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
 510            ++A) {
 511         if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
 512           A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
 513           ++NumNoCapture;
 514           Changed = true;
 515         }
 516       }
 517       continue;
 518     }
 519
 520     for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
 521          ++A) {
 522       if (!A->getType()->isPointerTy())
 523         continue;
 524       bool HasNonLocalUses = false;
 525       if (!A->hasNoCaptureAttr()) {
 526         ArgumentUsesTracker Tracker(SCCNodes);
 527         PointerMayBeCaptured(&*A, &Tracker);
 528         if (!Tracker.Captured) {
 529           if (Tracker.Uses.empty()) {
 530             // If it's trivially not captured, mark it nocapture now.
 531             A->addAttr(
 532                 AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
 533             ++NumNoCapture;
 534             Changed = true;
 535           } else {
 536             // If it's not trivially captured and not trivially not captured,
 537             // then it must be calling into another function in our SCC. Save
 538             // its particulars for Argument-SCC analysis later.
 539             ArgumentGraphNode *Node = AG[&*A];
 540             for (Argument *Use : Tracker.Uses) {
 541               Node->Uses.push_back(AG[Use]);
 542               if (Use != &*A)
 543                 HasNonLocalUses = true;
 544             }
 545           }
 546         }
 547         // Otherwise, it's captured. Don't bother doing SCC analysis on it.
 548       }
 549       if (!HasNonLocalUses && !A->onlyReadsMemory()) {
 550         // Can we determine that it's readonly/readnone without doing an SCC?
 551         // Note that we don't allow any calls at all here, or else our result
 552         // will be dependent on the iteration order through the functions in the
 553         // SCC.
 554         SmallPtrSet<Argument *, 8> Self;
 555         Self.insert(&*A);
 556         Attribute::AttrKind R = determinePointerReadAttrs(&*A, Self);
 557         if (R != Attribute::None) {
 558           AttrBuilder B;
 559           B.addAttribute(R);
 560           A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
 561           Changed = true;
 562           R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
 563         }
 564       }
 565     }
 566   }
 567
 568   // The graph we've collected is partial because we stopped scanning for
 569   // argument uses once we solved the argument trivially. These partial nodes
 570   // show up as ArgumentGraphNode objects with an empty Uses list, and for
 571   // these nodes the final decision about whether they capture has already been
 572   // made.  If the definition doesn't have a 'nocapture' attribute by now, it
 573   // captures.
 574
 575   for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
 576     const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
 577     if (ArgumentSCC.size() == 1) {
 578       if (!ArgumentSCC[0]->Definition)
 579         continue; // synthetic root node
 580
 581       // eg. "void f(int* x) { if (...) f(x); }"
 582       if (ArgumentSCC[0]->Uses.size() == 1 &&
 583           ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
 584         Argument *A = ArgumentSCC[0]->Definition;
 585         A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
 586         ++NumNoCapture;
 587         Changed = true;
 588       }
 589       continue;
 590     }
 591
 592     bool SCCCaptured = false;
 593     for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
 594          I != E && !SCCCaptured; ++I) {
 595       ArgumentGraphNode *Node = *I;
 596       if (Node->Uses.empty()) {
 597         if (!Node->Definition->hasNoCaptureAttr())
 598           SCCCaptured = true;
 599       }
 600     }
 601     if (SCCCaptured)
 602       continue;
 603
 604     SmallPtrSet<Argument *, 8> ArgumentSCCNodes;
 605     // Fill ArgumentSCCNodes with the elements of the ArgumentSCC.  Used for
 606     // quickly looking up whether a given Argument is in this ArgumentSCC.
 607     for (ArgumentGraphNode *I : ArgumentSCC) {
 608       ArgumentSCCNodes.insert(I->Definition);
 609     }
 610
 611     for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
 612          I != E && !SCCCaptured; ++I) {
 613       ArgumentGraphNode *N = *I;
 614       for (ArgumentGraphNode *Use : N->Uses) {
 615         Argument *A = Use->Definition;
 616         if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
 617           continue;
 618         SCCCaptured = true;
 619         break;
 620       }
 621     }
 622     if (SCCCaptured)
 623       continue;
 624
 625     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
 626       Argument *A = ArgumentSCC[i]->Definition;
 627       A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
 628       ++NumNoCapture;
 629       Changed = true;
 630     }
 631
 632     // We also want to compute readonly/readnone. With a small number of false
 633     // negatives, we can assume that any pointer which is captured isn't going
 634     // to be provably readonly or readnone, since by definition we can't
 635     // analyze all uses of a captured pointer.
 636     //
 637     // The false negatives happen when the pointer is captured by a function
 638     // that promises readonly/readnone behaviour on the pointer, then the
 639     // pointer's lifetime ends before anything that writes to arbitrary memory.
 640     // Also, a readonly/readnone pointer may be returned, but returning a
 641     // pointer is capturing it.
 642
 643     Attribute::AttrKind ReadAttr = Attribute::ReadNone;
 644     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
 645       Argument *A = ArgumentSCC[i]->Definition;
 646       Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes);
 647       if (K == Attribute::ReadNone)
 648         continue;
 649       if (K == Attribute::ReadOnly) {
 650         ReadAttr = Attribute::ReadOnly;
 651         continue;
 652       }
 653       ReadAttr = K;
 654       break;
 655     }
 656
 657     if (ReadAttr != Attribute::None) {
 658       AttrBuilder B, R;
 659       B.addAttribute(ReadAttr);
 660       R.addAttribute(Attribute::ReadOnly).addAttribute(Attribute::ReadNone);
 661       for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
 662         Argument *A = ArgumentSCC[i]->Definition;
 663         // Clear out existing readonly/readnone attributes
 664         A->removeAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, R));
 665         A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
 666         ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
 667         Changed = true;
 668       }
 669     }
 670   }
 671
 672   return Changed;
 673 }
 674
 675 /// Tests whether a function is "malloc-like".
 676 ///
 677 /// A function is "malloc-like" if it returns either null or a pointer that
 678 /// doesn't alias any other pointer visible to the caller.
 679 static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) {
 680   SmallSetVector<Value *, 8> FlowsToReturn;
 681   for (BasicBlock &BB : *F)
 682     if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
 683       FlowsToReturn.insert(Ret->getReturnValue());
 684
 685   for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
 686     Value *RetVal = FlowsToReturn[i];
 687
 688     if (Constant *C = dyn_cast<Constant>(RetVal)) {
 689       if (!C->isNullValue() && !isa<UndefValue>(C))
 690         return false;
 691
 692       continue;
 693     }
 694
 695     if (isa<Argument>(RetVal))
 696       return false;
 697
 698     if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
 699       switch (RVI->getOpcode()) {
 700       // Extend the analysis by looking upwards.
 701       case Instruction::BitCast:
 702       case Instruction::GetElementPtr:
 703       case Instruction::AddrSpaceCast:
 704         FlowsToReturn.insert(RVI->getOperand(0));
 705         continue;
 706       case Instruction::Select: {
 707         SelectInst *SI = cast<SelectInst>(RVI);
 708         FlowsToReturn.insert(SI->getTrueValue());
 709         FlowsToReturn.insert(SI->getFalseValue());
 710         continue;
 711       }
 712       case Instruction::PHI: {
 713         PHINode *PN = cast<PHINode>(RVI);
 714         for (Value *IncValue : PN->incoming_values())
 715           FlowsToReturn.insert(IncValue);
 716         continue;
 717       }
 718
 719       // Check whether the pointer came from an allocation.
 720       case Instruction::Alloca:
 721         break;
 722       case Instruction::Call:
 723       case Instruction::Invoke: {
 724         CallSite CS(RVI);
 725         if (CS.paramHasAttr(0, Attribute::NoAlias))
 726           break;
 727         if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
 728           break;
 729       } // fall-through
 730       default:
 731         return false; // Did not come from an allocation.
 732       }
 733
 734     if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
 735       return false;
 736   }
 737
 738   return true;
 739 }
 740
 741 /// Deduce noalias attributes for the SCC.
 742 static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes) {
 743   // Check each function in turn, determining which functions return noalias
 744   // pointers.
 745   for (Function *F : SCCNodes) {
 746     // Already noalias.
 747     if (F->doesNotAlias(0))
 748       continue;
 749
 750     // We can infer and propagate function attributes only when we know that the
 751     // definition we'll get at link time is *exactly* the definition we see now.
 752     // For more details, see GlobalValue::mayBeDerefined.
 753     if (!F->hasExactDefinition())
 754       return false;
 755
 756     // We annotate noalias return values, which are only applicable to
 757     // pointer types.
 758     if (!F->getReturnType()->isPointerTy())
 759       continue;
 760
 761     if (!isFunctionMallocLike(F, SCCNodes))
 762       return false;
 763   }
 764
 765   bool MadeChange = false;
 766   for (Function *F : SCCNodes) {
 767     if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy())
 768       continue;
 769
 770     F->setDoesNotAlias(0);
 771     ++NumNoAlias;
 772     MadeChange = true;
 773   }
 774
 775   return MadeChange;
 776 }
 777
 778 /// Tests whether this function is known to not return null.
 779 ///
 780 /// Requires that the function returns a pointer.
 781 ///
 782 /// Returns true if it believes the function will not return a null, and sets
 783 /// \p Speculative based on whether the returned conclusion is a speculative
 784 /// conclusion due to SCC calls.
 785 static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes,
 786                             bool &Speculative) {
 787   assert(F->getReturnType()->isPointerTy() &&
 788          "nonnull only meaningful on pointer types");
 789   Speculative = false;
 790
 791   SmallSetVector<Value *, 8> FlowsToReturn;
 792   for (BasicBlock &BB : *F)
 793     if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
 794       FlowsToReturn.insert(Ret->getReturnValue());
 795
 796   for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
 797     Value *RetVal = FlowsToReturn[i];
 798
 799     // If this value is locally known to be non-null, we're good
 800     if (isKnownNonNull(RetVal))
 801       continue;
 802
 803     // Otherwise, we need to look upwards since we can't make any local
 804     // conclusions.
 805     Instruction *RVI = dyn_cast<Instruction>(RetVal);
 806     if (!RVI)
 807       return false;
 808     switch (RVI->getOpcode()) {
 809     // Extend the analysis by looking upwards.
 810     case Instruction::BitCast:
 811     case Instruction::GetElementPtr:
 812     case Instruction::AddrSpaceCast:
 813       FlowsToReturn.insert(RVI->getOperand(0));
 814       continue;
 815     case Instruction::Select: {
 816       SelectInst *SI = cast<SelectInst>(RVI);
 817       FlowsToReturn.insert(SI->getTrueValue());
 818       FlowsToReturn.insert(SI->getFalseValue());
 819       continue;
 820     }
 821     case Instruction::PHI: {
 822       PHINode *PN = cast<PHINode>(RVI);
 823       for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 824         FlowsToReturn.insert(PN->getIncomingValue(i));
 825       continue;
 826     }
 827     case Instruction::Call:
 828     case Instruction::Invoke: {
 829       CallSite CS(RVI);
 830       Function *Callee = CS.getCalledFunction();
 831       // A call to a node within the SCC is assumed to return null until
 832       // proven otherwise
 833       if (Callee && SCCNodes.count(Callee)) {
 834         Speculative = true;
 835         continue;
 836       }
 837       return false;
 838     }
 839     default:
 840       return false; // Unknown source, may be null
 841     };
 842     llvm_unreachable("should have either continued or returned");
 843   }
 844
 845   return true;
 846 }
 847
 848 /// Deduce nonnull attributes for the SCC.
 849 static bool addNonNullAttrs(const SCCNodeSet &SCCNodes) {
 850   // Speculative that all functions in the SCC return only nonnull
 851   // pointers.  We may refute this as we analyze functions.
 852   bool SCCReturnsNonNull = true;
 853
 854   bool MadeChange = false;
 855
 856   // Check each function in turn, determining which functions return nonnull
 857   // pointers.
 858   for (Function *F : SCCNodes) {
 859     // Already nonnull.
 860     if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex,
 861                                         Attribute::NonNull))
 862       continue;
 863
 864     // We can infer and propagate function attributes only when we know that the
 865     // definition we'll get at link time is *exactly* the definition we see now.
 866     // For more details, see GlobalValue::mayBeDerefined.
 867     if (!F->hasExactDefinition())
 868       return false;
 869
 870     // We annotate nonnull return values, which are only applicable to
 871     // pointer types.
 872     if (!F->getReturnType()->isPointerTy())
 873       continue;
 874
 875     bool Speculative = false;
 876     if (isReturnNonNull(F, SCCNodes, Speculative)) {
 877       if (!Speculative) {
 878         // Mark the function eagerly since we may discover a function
 879         // which prevents us from speculating about the entire SCC
 880         DEBUG(dbgs() << "Eagerly marking " << F->getName() << " as nonnull\n");
 881         F->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull);
 882         ++NumNonNullReturn;
 883         MadeChange = true;
 884       }
 885       continue;
 886     }
 887     // At least one function returns something which could be null, can't
 888     // speculate any more.
 889     SCCReturnsNonNull = false;
 890   }
 891
 892   if (SCCReturnsNonNull) {
 893     for (Function *F : SCCNodes) {
 894       if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex,
 895                                           Attribute::NonNull) ||
 896           !F->getReturnType()->isPointerTy())
 897         continue;
 898
 899       DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
 900       F->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull);
 901       ++NumNonNullReturn;
 902       MadeChange = true;
 903     }
 904   }
 905
 906   return MadeChange;
 907 }
 908
 909 /// Remove the convergent attribute from all functions in the SCC if every
 910 /// callsite within the SCC is not convergent (except for calls to functions
 911 /// within the SCC).  Returns true if changes were made.
 912 static bool removeConvergentAttrs(const SCCNodeSet &SCCNodes) {
 913   // For every function in SCC, ensure that either
 914   //  * it is not convergent, or
 915   //  * we can remove its convergent attribute.
 916   bool HasConvergentFn = false;
 917   for (Function *F : SCCNodes) {
 918     if (!F->isConvergent()) continue;
 919     HasConvergentFn = true;
 920
 921     // Can't remove convergent from function declarations.
 922     if (F->isDeclaration()) return false;
 923
 924     // Can't remove convergent if any of our functions has a convergent call to a
 925     // function not in the SCC.
 926     for (Instruction &I : instructions(*F)) {
 927       CallSite CS(&I);
 928       // Bail if CS is a convergent call to a function not in the SCC.
 929       if (CS && CS.isConvergent() &&
 930           SCCNodes.count(CS.getCalledFunction()) == 0)
 931         return false;
 932     }
 933   }
 934
 935   // If the SCC doesn't have any convergent functions, we have nothing to do.
 936   if (!HasConvergentFn) return false;
 937
 938   // If we got here, all of the calls the SCC makes to functions not in the SCC
 939   // are non-convergent.  Therefore all of the SCC's functions can also be made
 940   // non-convergent.  We'll remove the attr from the callsites in
 941   // InstCombineCalls.
 942   for (Function *F : SCCNodes) {
 943     if (!F->isConvergent()) continue;
 944
 945     DEBUG(dbgs() << "Removing convergent attr from fn " << F->getName()
 946                  << "\n");
 947     F->setNotConvergent();
 948   }
 949   return true;
 950 }
 951
 952 static bool setDoesNotRecurse(Function &F) {
 953   if (F.doesNotRecurse())
 954     return false;
 955   F.setDoesNotRecurse();
 956   ++NumNoRecurse;
 957   return true;
 958 }
 959
 960 static bool addNoRecurseAttrs(const SCCNodeSet &SCCNodes) {
 961   // Try and identify functions that do not recurse.
 962
 963   // If the SCC contains multiple nodes we know for sure there is recursion.
 964   if (SCCNodes.size() != 1)
 965     return false;
 966
 967   Function *F = *SCCNodes.begin();
 968   if (!F || F->isDeclaration() || F->doesNotRecurse())
 969     return false;
 970
 971   // If all of the calls in F are identifiable and are to norecurse functions, F
 972   // is norecurse. This check also detects self-recursion as F is not currently
 973   // marked norecurse, so any called from F to F will not be marked norecurse.
 974   for (Instruction &I : instructions(*F))
 975     if (auto CS = CallSite(&I)) {
 976       Function *Callee = CS.getCalledFunction();
 977       if (!Callee || Callee == F || !Callee->doesNotRecurse())
 978         // Function calls a potentially recursive function.
 979         return false;
 980     }
 981
 982   // Every call was to a non-recursive function other than this function, and
 983   // we have no indirect recursion as the SCC size is one. This function cannot
 984   // recurse.
 985   return setDoesNotRecurse(*F);
 986 }
 987
 988 PreservedAnalyses PostOrderFunctionAttrsPass::run(LazyCallGraph::SCC &C,
 989                                                   CGSCCAnalysisManager &AM) {
 990   FunctionAnalysisManager &FAM =
 991       AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C).getManager();
 992
 993   // We pass a lambda into functions to wire them up to the analysis manager
 994   // for getting function analyses.
 995   auto AARGetter = [&](Function &F) -> AAResults & {
 996     return FAM.getResult<AAManager>(F);
 997   };
 998
 999   // Fill SCCNodes with the elements of the SCC. Also track whether there are
1000   // any external or opt-none nodes that will prevent us from optimizing any
1001   // part of the SCC.
1002   SCCNodeSet SCCNodes;
1003   bool HasUnknownCall = false;
1004   for (LazyCallGraph::Node &N : C) {
1005     Function &F = N.getFunction();
1006     if (F.hasFnAttribute(Attribute::OptimizeNone)) {
1007       // Treat any function we're trying not to optimize as if it were an
1008       // indirect call and omit it from the node set used below.
1009       HasUnknownCall = true;
1010       continue;
1011     }
1012     // Track whether any functions in this SCC have an unknown call edge.
1013     // Note: if this is ever a performance hit, we can common it with
1014     // subsequent routines which also do scans over the instructions of the
1015     // function.
1016     if (!HasUnknownCall)
1017       for (Instruction &I : instructions(F))
1018         if (auto CS = CallSite(&I))
1019           if (!CS.getCalledFunction()) {
1020             HasUnknownCall = true;
1021             break;
1022           }
1023
1024     SCCNodes.insert(&F);
1025   }
1026
1027   bool Changed = false;
1028   Changed |= addReadAttrs(SCCNodes, AARGetter);
1029   Changed |= addArgumentAttrs(SCCNodes);
1030
1031   // If we have no external nodes participating in the SCC, we can deduce some
1032   // more precise attributes as well.
1033   if (!HasUnknownCall) {
1034     Changed |= addNoAliasAttrs(SCCNodes);
1035     Changed |= addNonNullAttrs(SCCNodes);
1036     Changed |= removeConvergentAttrs(SCCNodes);
1037     Changed |= addNoRecurseAttrs(SCCNodes);
1038   }
1039
1040   return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
1041 }
1042
1043 namespace {
1044 struct PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass {
1045   static char ID; // Pass identification, replacement for typeid
1046   PostOrderFunctionAttrsLegacyPass() : CallGraphSCCPass(ID) {
1047     initializePostOrderFunctionAttrsLegacyPassPass(*PassRegistry::getPassRegistry());
1048   }
1049
1050   bool runOnSCC(CallGraphSCC &SCC) override;
1051
1052   void getAnalysisUsage(AnalysisUsage &AU) const override {
1053     AU.setPreservesCFG();
1054     AU.addRequired<AssumptionCacheTracker>();
1055     getAAResultsAnalysisUsage(AU);
1056     CallGraphSCCPass::getAnalysisUsage(AU);
1057   }
1058 };
1059 }
1060
1061 char PostOrderFunctionAttrsLegacyPass::ID = 0;
1062 INITIALIZE_PASS_BEGIN(PostOrderFunctionAttrsLegacyPass, "functionattrs",
1063                       "Deduce function attributes", false, false)
1064 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1065 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
1066 INITIALIZE_PASS_END(PostOrderFunctionAttrsLegacyPass, "functionattrs",
1067                     "Deduce function attributes", false, false)
1068
1069 Pass *llvm::createPostOrderFunctionAttrsLegacyPass() { return new PostOrderFunctionAttrsLegacyPass(); }
1070
1071 template <typename AARGetterT>
1072 static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter) {
1073   bool Changed = false;
1074
1075   // Fill SCCNodes with the elements of the SCC. Used for quickly looking up
1076   // whether a given CallGraphNode is in this SCC. Also track whether there are
1077   // any external or opt-none nodes that will prevent us from optimizing any
1078   // part of the SCC.
1079   SCCNodeSet SCCNodes;
1080   bool ExternalNode = false;
1081   for (CallGraphNode *I : SCC) {
1082     Function *F = I->getFunction();
1083     if (!F || F->hasFnAttribute(Attribute::OptimizeNone)) {
1084       // External node or function we're trying not to optimize - we both avoid
1085       // transform them and avoid leveraging information they provide.
1086       ExternalNode = true;
1087       continue;
1088     }
1089
1090     SCCNodes.insert(F);
1091   }
1092
1093   Changed |= addReadAttrs(SCCNodes, AARGetter);
1094   Changed |= addArgumentAttrs(SCCNodes);
1095
1096   // If we have no external nodes participating in the SCC, we can deduce some
1097   // more precise attributes as well.
1098   if (!ExternalNode) {
1099     Changed |= addNoAliasAttrs(SCCNodes);
1100     Changed |= addNonNullAttrs(SCCNodes);
1101     Changed |= removeConvergentAttrs(SCCNodes);
1102     Changed |= addNoRecurseAttrs(SCCNodes);
1103   }
1104
1105   return Changed;
1106 }
1107
1108 bool PostOrderFunctionAttrsLegacyPass::runOnSCC(CallGraphSCC &SCC) {
1109   if (skipSCC(SCC))
1110     return false;
1111
1112   // We compute dedicated AA results for each function in the SCC as needed. We
1113   // use a lambda referencing external objects so that they live long enough to
1114   // be queried, but we re-use them each time.
1115   Optional<BasicAAResult> BAR;
1116   Optional<AAResults> AAR;
1117   auto AARGetter = [&](Function &F) -> AAResults & {
1118     BAR.emplace(createLegacyPMBasicAAResult(*this, F));
1119     AAR.emplace(createLegacyPMAAResults(*this, F, *BAR));
1120     return *AAR;
1121   };
1122
1123   return runImpl(SCC, AARGetter);
1124 }
1125
1126 namespace {
1127 struct ReversePostOrderFunctionAttrsLegacyPass : public ModulePass {
1128   static char ID; // Pass identification, replacement for typeid
1129   ReversePostOrderFunctionAttrsLegacyPass() : ModulePass(ID) {
1130     initializeReversePostOrderFunctionAttrsLegacyPassPass(*PassRegistry::getPassRegistry());
1131   }
1132
1133   bool runOnModule(Module &M) override;
1134
1135   void getAnalysisUsage(AnalysisUsage &AU) const override {
1136     AU.setPreservesCFG();
1137     AU.addRequired<CallGraphWrapperPass>();
1138     AU.addPreserved<CallGraphWrapperPass>();
1139   }
1140 };
1141 }
1142
1143 char ReversePostOrderFunctionAttrsLegacyPass::ID = 0;
1144 INITIALIZE_PASS_BEGIN(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs",
1145                       "Deduce function attributes in RPO", false, false)
1146 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
1147 INITIALIZE_PASS_END(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs",
1148                     "Deduce function attributes in RPO", false, false)
1149
1150 Pass *llvm::createReversePostOrderFunctionAttrsPass() {
1151   return new ReversePostOrderFunctionAttrsLegacyPass();
1152 }
1153
1154 static bool addNoRecurseAttrsTopDown(Function &F) {
1155   // We check the preconditions for the function prior to calling this to avoid
1156   // the cost of building up a reversible post-order list. We assert them here
1157   // to make sure none of the invariants this relies on were violated.
1158   assert(!F.isDeclaration() && "Cannot deduce norecurse without a definition!");
1159   assert(!F.doesNotRecurse() &&
1160          "This function has already been deduced as norecurs!");
1161   assert(F.hasInternalLinkage() &&
1162          "Can only do top-down deduction for internal linkage functions!");
1163
1164   // If F is internal and all of its uses are calls from a non-recursive
1165   // functions, then none of its calls could in fact recurse without going
1166   // through a function marked norecurse, and so we can mark this function too
1167   // as norecurse. Note that the uses must actually be calls -- otherwise
1168   // a pointer to this function could be returned from a norecurse function but
1169   // this function could be recursively (indirectly) called. Note that this
1170   // also detects if F is directly recursive as F is not yet marked as
1171   // a norecurse function.
1172   for (auto *U : F.users()) {
1173     auto *I = dyn_cast<Instruction>(U);
1174     if (!I)
1175       return false;
1176     CallSite CS(I);
1177     if (!CS || !CS.getParent()->getParent()->doesNotRecurse())
1178       return false;
1179   }
1180   return setDoesNotRecurse(F);
1181 }
1182
1183 static bool deduceFunctionAttributeInRPO(Module &M, CallGraph &CG) {
1184   // We only have a post-order SCC traversal (because SCCs are inherently
1185   // discovered in post-order), so we accumulate them in a vector and then walk
1186   // it in reverse. This is simpler than using the RPO iterator infrastructure
1187   // because we need to combine SCC detection and the PO walk of the call
1188   // graph. We can also cheat egregiously because we're primarily interested in
1189   // synthesizing norecurse and so we can only save the singular SCCs as SCCs
1190   // with multiple functions in them will clearly be recursive.
1191   SmallVector<Function *, 16> Worklist;
1192   for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
1193     if (I->size() != 1)
1194       continue;
1195
1196     Function *F = I->front()->getFunction();
1197     if (F && !F->isDeclaration() && !F->doesNotRecurse() &&
1198         F->hasInternalLinkage())
1199       Worklist.push_back(F);
1200   }
1201
1202   bool Changed = false;
1203   for (auto *F : reverse(Worklist))
1204     Changed |= addNoRecurseAttrsTopDown(*F);
1205
1206   return Changed;
1207 }
1208
1209 bool ReversePostOrderFunctionAttrsLegacyPass::runOnModule(Module &M) {
1210   if (skipModule(M))
1211     return false;
1212
1213   auto &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
1214
1215   return deduceFunctionAttributeInRPO(M, CG);
1216 }
1217
1218 PreservedAnalyses
1219 ReversePostOrderFunctionAttrsPass::run(Module &M, AnalysisManager<Module> &AM) {
1220   auto &CG = AM.getResult<CallGraphAnalysis>(M);
1221
1222   bool Changed = deduceFunctionAttributeInRPO(M, CG);
1223   if (!Changed)
1224     return PreservedAnalyses::all();
1225   PreservedAnalyses PA;
1226   PA.preserve<CallGraphAnalysis>();
1227   return PA;
1228 }