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