contrib/llvm-project/llvm/lib/Transforms/IPO/FunctionAttrs.cpp

   1 //===- FunctionAttrs.cpp - Pass which marks functions attributes ----------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 /// \file
  10 /// This file implements interprocedural passes which walk the
  11 /// call-graph deducing and/or propagating function attributes.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Transforms/IPO/FunctionAttrs.h"
  16 #include "llvm/ADT/SCCIterator.h"
  17 #include "llvm/ADT/STLExtras.h"
  18 #include "llvm/ADT/SetVector.h"
  19 #include "llvm/ADT/SmallPtrSet.h"
  20 #include "llvm/ADT/SmallVector.h"
  21 #include "llvm/ADT/Statistic.h"
  22 #include "llvm/Analysis/AliasAnalysis.h"
  23 #include "llvm/Analysis/AssumptionCache.h"
  24 #include "llvm/Analysis/BasicAliasAnalysis.h"
  25 #include "llvm/Analysis/CGSCCPassManager.h"
  26 #include "llvm/Analysis/CallGraph.h"
  27 #include "llvm/Analysis/CallGraphSCCPass.h"
  28 #include "llvm/Analysis/CaptureTracking.h"
  29 #include "llvm/Analysis/LazyCallGraph.h"
  30 #include "llvm/Analysis/MemoryBuiltins.h"
  31 #include "llvm/Analysis/MemoryLocation.h"
  32 #include "llvm/Analysis/ValueTracking.h"
  33 #include "llvm/IR/Argument.h"
  34 #include "llvm/IR/Attributes.h"
  35 #include "llvm/IR/BasicBlock.h"
  36 #include "llvm/IR/CallSite.h"
  37 #include "llvm/IR/Constant.h"
  38 #include "llvm/IR/Constants.h"
  39 #include "llvm/IR/Function.h"
  40 #include "llvm/IR/InstIterator.h"
  41 #include "llvm/IR/InstrTypes.h"
  42 #include "llvm/IR/Instruction.h"
  43 #include "llvm/IR/Instructions.h"
  44 #include "llvm/IR/IntrinsicInst.h"
  45 #include "llvm/IR/Metadata.h"
  46 #include "llvm/IR/PassManager.h"
  47 #include "llvm/IR/Type.h"
  48 #include "llvm/IR/Use.h"
  49 #include "llvm/IR/User.h"
  50 #include "llvm/IR/Value.h"
  51 #include "llvm/InitializePasses.h"
  52 #include "llvm/Pass.h"
  53 #include "llvm/Support/Casting.h"
  54 #include "llvm/Support/CommandLine.h"
  55 #include "llvm/Support/Compiler.h"
  56 #include "llvm/Support/Debug.h"
  57 #include "llvm/Support/ErrorHandling.h"
  58 #include "llvm/Support/raw_ostream.h"
  59 #include "llvm/Transforms/IPO.h"
  60 #include <cassert>
  61 #include <iterator>
  62 #include <map>
  63 #include <vector>
  64
  65 using namespace llvm;
  66
  67 #define DEBUG_TYPE "functionattrs"
  68
  69 STATISTIC(NumReadNone, "Number of functions marked readnone");
  70 STATISTIC(NumReadOnly, "Number of functions marked readonly");
  71 STATISTIC(NumWriteOnly, "Number of functions marked writeonly");
  72 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
  73 STATISTIC(NumReturned, "Number of arguments marked returned");
  74 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
  75 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
  76 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
  77 STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull");
  78 STATISTIC(NumNoRecurse, "Number of functions marked as norecurse");
  79 STATISTIC(NumNoUnwind, "Number of functions marked as nounwind");
  80 STATISTIC(NumNoFree, "Number of functions marked as nofree");
  81
  82 static cl::opt<bool> EnableNonnullArgPropagation(
  83     "enable-nonnull-arg-prop", cl::init(true), cl::Hidden,
  84     cl::desc("Try to propagate nonnull argument attributes from callsites to "
  85              "caller functions."));
  86
  87 static cl::opt<bool> DisableNoUnwindInference(
  88     "disable-nounwind-inference", cl::Hidden,
  89     cl::desc("Stop inferring nounwind attribute during function-attrs pass"));
  90
  91 static cl::opt<bool> DisableNoFreeInference(
  92     "disable-nofree-inference", cl::Hidden,
  93     cl::desc("Stop inferring nofree attribute during function-attrs pass"));
  94
  95 namespace {
  96
  97 using SCCNodeSet = SmallSetVector<Function *, 8>;
  98
  99 } // end anonymous namespace
 100
 101 /// Returns the memory access attribute for function F using AAR for AA results,
 102 /// where SCCNodes is the current SCC.
 103 ///
 104 /// If ThisBody is true, this function may examine the function body and will
 105 /// return a result pertaining to this copy of the function. If it is false, the
 106 /// result will be based only on AA results for the function declaration; it
 107 /// will be assumed that some other (perhaps less optimized) version of the
 108 /// function may be selected at link time.
 109 static MemoryAccessKind checkFunctionMemoryAccess(Function &F, bool ThisBody,
 110                                                   AAResults &AAR,
 111                                                   const SCCNodeSet &SCCNodes) {
 112   FunctionModRefBehavior MRB = AAR.getModRefBehavior(&F);
 113   if (MRB == FMRB_DoesNotAccessMemory)
 114     // Already perfect!
 115     return MAK_ReadNone;
 116
 117   if (!ThisBody) {
 118     if (AliasAnalysis::onlyReadsMemory(MRB))
 119       return MAK_ReadOnly;
 120
 121     if (AliasAnalysis::doesNotReadMemory(MRB))
 122       return MAK_WriteOnly;
 123
 124     // Conservatively assume it reads and writes to memory.
 125     return MAK_MayWrite;
 126   }
 127
 128   // Scan the function body for instructions that may read or write memory.
 129   bool ReadsMemory = false;
 130   bool WritesMemory = false;
 131   for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
 132     Instruction *I = &*II;
 133
 134     // Some instructions can be ignored even if they read or write memory.
 135     // Detect these now, skipping to the next instruction if one is found.
 136     if (auto *Call = dyn_cast<CallBase>(I)) {
 137       // Ignore calls to functions in the same SCC, as long as the call sites
 138       // don't have operand bundles.  Calls with operand bundles are allowed to
 139       // have memory effects not described by the memory effects of the call
 140       // target.
 141       if (!Call->hasOperandBundles() && Call->getCalledFunction() &&
 142           SCCNodes.count(Call->getCalledFunction()))
 143         continue;
 144       FunctionModRefBehavior MRB = AAR.getModRefBehavior(Call);
 145       ModRefInfo MRI = createModRefInfo(MRB);
 146
 147       // If the call doesn't access memory, we're done.
 148       if (isNoModRef(MRI))
 149         continue;
 150
 151       if (!AliasAnalysis::onlyAccessesArgPointees(MRB)) {
 152         // The call could access any memory. If that includes writes, note it.
 153         if (isModSet(MRI))
 154           WritesMemory = true;
 155         // If it reads, note it.
 156         if (isRefSet(MRI))
 157           ReadsMemory = true;
 158         continue;
 159       }
 160
 161       // Check whether all pointer arguments point to local memory, and
 162       // ignore calls that only access local memory.
 163       for (CallSite::arg_iterator CI = Call->arg_begin(), CE = Call->arg_end();
 164            CI != CE; ++CI) {
 165         Value *Arg = *CI;
 166         if (!Arg->getType()->isPtrOrPtrVectorTy())
 167           continue;
 168
 169         AAMDNodes AAInfo;
 170         I->getAAMetadata(AAInfo);
 171         MemoryLocation Loc(Arg, LocationSize::unknown(), AAInfo);
 172
 173         // Skip accesses to local or constant memory as they don't impact the
 174         // externally visible mod/ref behavior.
 175         if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
 176           continue;
 177
 178         if (isModSet(MRI))
 179           // Writes non-local memory.
 180           WritesMemory = true;
 181         if (isRefSet(MRI))
 182           // Ok, it reads non-local memory.
 183           ReadsMemory = true;
 184       }
 185       continue;
 186     } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
 187       // Ignore non-volatile loads from local memory. (Atomic is okay here.)
 188       if (!LI->isVolatile()) {
 189         MemoryLocation Loc = MemoryLocation::get(LI);
 190         if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
 191           continue;
 192       }
 193     } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 194       // Ignore non-volatile stores to local memory. (Atomic is okay here.)
 195       if (!SI->isVolatile()) {
 196         MemoryLocation Loc = MemoryLocation::get(SI);
 197         if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
 198           continue;
 199       }
 200     } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) {
 201       // Ignore vaargs on local memory.
 202       MemoryLocation Loc = MemoryLocation::get(VI);
 203       if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
 204         continue;
 205     }
 206
 207     // Any remaining instructions need to be taken seriously!  Check if they
 208     // read or write memory.
 209     //
 210     // Writes memory, remember that.
 211     WritesMemory |= I->mayWriteToMemory();
 212
 213     // If this instruction may read memory, remember that.
 214     ReadsMemory |= I->mayReadFromMemory();
 215   }
 216
 217   if (WritesMemory) {
 218     if (!ReadsMemory)
 219       return MAK_WriteOnly;
 220     else
 221       return MAK_MayWrite;
 222   }
 223
 224   return ReadsMemory ? MAK_ReadOnly : MAK_ReadNone;
 225 }
 226
 227 MemoryAccessKind llvm::computeFunctionBodyMemoryAccess(Function &F,
 228                                                        AAResults &AAR) {
 229   return checkFunctionMemoryAccess(F, /*ThisBody=*/true, AAR, {});
 230 }
 231
 232 /// Deduce readonly/readnone attributes for the SCC.
 233 template <typename AARGetterT>
 234 static bool addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter) {
 235   // Check if any of the functions in the SCC read or write memory.  If they
 236   // write memory then they can't be marked readnone or readonly.
 237   bool ReadsMemory = false;
 238   bool WritesMemory = false;
 239   for (Function *F : SCCNodes) {
 240     // Call the callable parameter to look up AA results for this function.
 241     AAResults &AAR = AARGetter(*F);
 242
 243     // Non-exact function definitions may not be selected at link time, and an
 244     // alternative version that writes to memory may be selected.  See the
 245     // comment on GlobalValue::isDefinitionExact for more details.
 246     switch (checkFunctionMemoryAccess(*F, F->hasExactDefinition(),
 247                                       AAR, SCCNodes)) {
 248     case MAK_MayWrite:
 249       return false;
 250     case MAK_ReadOnly:
 251       ReadsMemory = true;
 252       break;
 253     case MAK_WriteOnly:
 254       WritesMemory = true;
 255       break;
 256     case MAK_ReadNone:
 257       // Nothing to do!
 258       break;
 259     }
 260   }
 261
 262   // If the SCC contains both functions that read and functions that write, then
 263   // we cannot add readonly attributes.
 264   if (ReadsMemory && WritesMemory)
 265     return false;
 266
 267   // Success!  Functions in this SCC do not access memory, or only read memory.
 268   // Give them the appropriate attribute.
 269   bool MadeChange = false;
 270
 271   for (Function *F : SCCNodes) {
 272     if (F->doesNotAccessMemory())
 273       // Already perfect!
 274       continue;
 275
 276     if (F->onlyReadsMemory() && ReadsMemory)
 277       // No change.
 278       continue;
 279
 280     if (F->doesNotReadMemory() && WritesMemory)
 281       continue;
 282
 283     MadeChange = true;
 284
 285     // Clear out any existing attributes.
 286     F->removeFnAttr(Attribute::ReadOnly);
 287     F->removeFnAttr(Attribute::ReadNone);
 288     F->removeFnAttr(Attribute::WriteOnly);
 289
 290     if (!WritesMemory && !ReadsMemory) {
 291       // Clear out any "access range attributes" if readnone was deduced.
 292       F->removeFnAttr(Attribute::ArgMemOnly);
 293       F->removeFnAttr(Attribute::InaccessibleMemOnly);
 294       F->removeFnAttr(Attribute::InaccessibleMemOrArgMemOnly);
 295     }
 296
 297     // Add in the new attribute.
 298     if (WritesMemory && !ReadsMemory)
 299       F->addFnAttr(Attribute::WriteOnly);
 300     else
 301       F->addFnAttr(ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone);
 302
 303     if (WritesMemory && !ReadsMemory)
 304       ++NumWriteOnly;
 305     else if (ReadsMemory)
 306       ++NumReadOnly;
 307     else
 308       ++NumReadNone;
 309   }
 310
 311   return MadeChange;
 312 }
 313
 314 namespace {
 315
 316 /// For a given pointer Argument, this retains a list of Arguments of functions
 317 /// in the same SCC that the pointer data flows into. We use this to build an
 318 /// SCC of the arguments.
 319 struct ArgumentGraphNode {
 320   Argument *Definition;
 321   SmallVector<ArgumentGraphNode *, 4> Uses;
 322 };
 323
 324 class ArgumentGraph {
 325   // We store pointers to ArgumentGraphNode objects, so it's important that
 326   // that they not move around upon insert.
 327   using ArgumentMapTy = std::map<Argument *, ArgumentGraphNode>;
 328
 329   ArgumentMapTy ArgumentMap;
 330
 331   // There is no root node for the argument graph, in fact:
 332   //   void f(int *x, int *y) { if (...) f(x, y); }
 333   // is an example where the graph is disconnected. The SCCIterator requires a
 334   // single entry point, so we maintain a fake ("synthetic") root node that
 335   // uses every node. Because the graph is directed and nothing points into
 336   // the root, it will not participate in any SCCs (except for its own).
 337   ArgumentGraphNode SyntheticRoot;
 338
 339 public:
 340   ArgumentGraph() { SyntheticRoot.Definition = nullptr; }
 341
 342   using iterator = SmallVectorImpl<ArgumentGraphNode *>::iterator;
 343
 344   iterator begin() { return SyntheticRoot.Uses.begin(); }
 345   iterator end() { return SyntheticRoot.Uses.end(); }
 346   ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; }
 347
 348   ArgumentGraphNode *operator[](Argument *A) {
 349     ArgumentGraphNode &Node = ArgumentMap[A];
 350     Node.Definition = A;
 351     SyntheticRoot.Uses.push_back(&Node);
 352     return &Node;
 353   }
 354 };
 355
 356 /// This tracker checks whether callees are in the SCC, and if so it does not
 357 /// consider that a capture, instead adding it to the "Uses" list and
 358 /// continuing with the analysis.
 359 struct ArgumentUsesTracker : public CaptureTracker {
 360   ArgumentUsesTracker(const SCCNodeSet &SCCNodes) : SCCNodes(SCCNodes) {}
 361
 362   void tooManyUses() override { Captured = true; }
 363
 364   bool captured(const Use *U) override {
 365     CallSite CS(U->getUser());
 366     if (!CS.getInstruction()) {
 367       Captured = true;
 368       return true;
 369     }
 370
 371     Function *F = CS.getCalledFunction();
 372     if (!F || !F->hasExactDefinition() || !SCCNodes.count(F)) {
 373       Captured = true;
 374       return true;
 375     }
 376
 377     // Note: the callee and the two successor blocks *follow* the argument
 378     // operands.  This means there is no need to adjust UseIndex to account for
 379     // these.
 380
 381     unsigned UseIndex =
 382         std::distance(const_cast<const Use *>(CS.arg_begin()), U);
 383
 384     assert(UseIndex < CS.data_operands_size() &&
 385            "Indirect function calls should have been filtered above!");
 386
 387     if (UseIndex >= CS.getNumArgOperands()) {
 388       // Data operand, but not a argument operand -- must be a bundle operand
 389       assert(CS.hasOperandBundles() && "Must be!");
 390
 391       // CaptureTracking told us that we're being captured by an operand bundle
 392       // use.  In this case it does not matter if the callee is within our SCC
 393       // or not -- we've been captured in some unknown way, and we have to be
 394       // conservative.
 395       Captured = true;
 396       return true;
 397     }
 398
 399     if (UseIndex >= F->arg_size()) {
 400       assert(F->isVarArg() && "More params than args in non-varargs call");
 401       Captured = true;
 402       return true;
 403     }
 404
 405     Uses.push_back(&*std::next(F->arg_begin(), UseIndex));
 406     return false;
 407   }
 408
 409   // True only if certainly captured (used outside our SCC).
 410   bool Captured = false;
 411
 412   // Uses within our SCC.
 413   SmallVector<Argument *, 4> Uses;
 414
 415   const SCCNodeSet &SCCNodes;
 416 };
 417
 418 } // end anonymous namespace
 419
 420 namespace llvm {
 421
 422 template <> struct GraphTraits<ArgumentGraphNode *> {
 423   using NodeRef = ArgumentGraphNode *;
 424   using ChildIteratorType = SmallVectorImpl<ArgumentGraphNode *>::iterator;
 425
 426   static NodeRef getEntryNode(NodeRef A) { return A; }
 427   static ChildIteratorType child_begin(NodeRef N) { return N->Uses.begin(); }
 428   static ChildIteratorType child_end(NodeRef N) { return N->Uses.end(); }
 429 };
 430
 431 template <>
 432 struct GraphTraits<ArgumentGraph *> : public GraphTraits<ArgumentGraphNode *> {
 433   static NodeRef getEntryNode(ArgumentGraph *AG) { return AG->getEntryNode(); }
 434
 435   static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
 436     return AG->begin();
 437   }
 438
 439   static ChildIteratorType nodes_end(ArgumentGraph *AG) { return AG->end(); }
 440 };
 441
 442 } // end namespace llvm
 443
 444 /// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
 445 static Attribute::AttrKind
 446 determinePointerReadAttrs(Argument *A,
 447                           const SmallPtrSet<Argument *, 8> &SCCNodes) {
 448   SmallVector<Use *, 32> Worklist;
 449   SmallPtrSet<Use *, 32> Visited;
 450
 451   // inalloca arguments are always clobbered by the call.
 452   if (A->hasInAllocaAttr())
 453     return Attribute::None;
 454
 455   bool IsRead = false;
 456   // We don't need to track IsWritten. If A is written to, return immediately.
 457
 458   for (Use &U : A->uses()) {
 459     Visited.insert(&U);
 460     Worklist.push_back(&U);
 461   }
 462
 463   while (!Worklist.empty()) {
 464     Use *U = Worklist.pop_back_val();
 465     Instruction *I = cast<Instruction>(U->getUser());
 466
 467     switch (I->getOpcode()) {
 468     case Instruction::BitCast:
 469     case Instruction::GetElementPtr:
 470     case Instruction::PHI:
 471     case Instruction::Select:
 472     case Instruction::AddrSpaceCast:
 473       // The original value is not read/written via this if the new value isn't.
 474       for (Use &UU : I->uses())
 475         if (Visited.insert(&UU).second)
 476           Worklist.push_back(&UU);
 477       break;
 478
 479     case Instruction::Call:
 480     case Instruction::Invoke: {
 481       bool Captures = true;
 482
 483       if (I->getType()->isVoidTy())
 484         Captures = false;
 485
 486       auto AddUsersToWorklistIfCapturing = [&] {
 487         if (Captures)
 488           for (Use &UU : I->uses())
 489             if (Visited.insert(&UU).second)
 490               Worklist.push_back(&UU);
 491       };
 492
 493       CallSite CS(I);
 494       if (CS.doesNotAccessMemory()) {
 495         AddUsersToWorklistIfCapturing();
 496         continue;
 497       }
 498
 499       Function *F = CS.getCalledFunction();
 500       if (!F) {
 501         if (CS.onlyReadsMemory()) {
 502           IsRead = true;
 503           AddUsersToWorklistIfCapturing();
 504           continue;
 505         }
 506         return Attribute::None;
 507       }
 508
 509       // Note: the callee and the two successor blocks *follow* the argument
 510       // operands.  This means there is no need to adjust UseIndex to account
 511       // for these.
 512
 513       unsigned UseIndex = std::distance(CS.arg_begin(), U);
 514
 515       // U cannot be the callee operand use: since we're exploring the
 516       // transitive uses of an Argument, having such a use be a callee would
 517       // imply the CallSite is an indirect call or invoke; and we'd take the
 518       // early exit above.
 519       assert(UseIndex < CS.data_operands_size() &&
 520              "Data operand use expected!");
 521
 522       bool IsOperandBundleUse = UseIndex >= CS.getNumArgOperands();
 523
 524       if (UseIndex >= F->arg_size() && !IsOperandBundleUse) {
 525         assert(F->isVarArg() && "More params than args in non-varargs call");
 526         return Attribute::None;
 527       }
 528
 529       Captures &= !CS.doesNotCapture(UseIndex);
 530
 531       // Since the optimizer (by design) cannot see the data flow corresponding
 532       // to a operand bundle use, these cannot participate in the optimistic SCC
 533       // analysis.  Instead, we model the operand bundle uses as arguments in
 534       // call to a function external to the SCC.
 535       if (IsOperandBundleUse ||
 536           !SCCNodes.count(&*std::next(F->arg_begin(), UseIndex))) {
 537
 538         // The accessors used on CallSite here do the right thing for calls and
 539         // invokes with operand bundles.
 540
 541         if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(UseIndex))
 542           return Attribute::None;
 543         if (!CS.doesNotAccessMemory(UseIndex))
 544           IsRead = true;
 545       }
 546
 547       AddUsersToWorklistIfCapturing();
 548       break;
 549     }
 550
 551     case Instruction::Load:
 552       // A volatile load has side effects beyond what readonly can be relied
 553       // upon.
 554       if (cast<LoadInst>(I)->isVolatile())
 555         return Attribute::None;
 556
 557       IsRead = true;
 558       break;
 559
 560     case Instruction::ICmp:
 561     case Instruction::Ret:
 562       break;
 563
 564     default:
 565       return Attribute::None;
 566     }
 567   }
 568
 569   return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
 570 }
 571
 572 /// Deduce returned attributes for the SCC.
 573 static bool addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes) {
 574   bool Changed = false;
 575
 576   // Check each function in turn, determining if an argument is always returned.
 577   for (Function *F : SCCNodes) {
 578     // We can infer and propagate function attributes only when we know that the
 579     // definition we'll get at link time is *exactly* the definition we see now.
 580     // For more details, see GlobalValue::mayBeDerefined.
 581     if (!F->hasExactDefinition())
 582       continue;
 583
 584     if (F->getReturnType()->isVoidTy())
 585       continue;
 586
 587     // There is nothing to do if an argument is already marked as 'returned'.
 588     if (llvm::any_of(F->args(),
 589                      [](const Argument &Arg) { return Arg.hasReturnedAttr(); }))
 590       continue;
 591
 592     auto FindRetArg = [&]() -> Value * {
 593       Value *RetArg = nullptr;
 594       for (BasicBlock &BB : *F)
 595         if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator())) {
 596           // Note that stripPointerCasts should look through functions with
 597           // returned arguments.
 598           Value *RetVal = Ret->getReturnValue()->stripPointerCasts();
 599           if (!isa<Argument>(RetVal) || RetVal->getType() != F->getReturnType())
 600             return nullptr;
 601
 602           if (!RetArg)
 603             RetArg = RetVal;
 604           else if (RetArg != RetVal)
 605             return nullptr;
 606         }
 607
 608       return RetArg;
 609     };
 610
 611     if (Value *RetArg = FindRetArg()) {
 612       auto *A = cast<Argument>(RetArg);
 613       A->addAttr(Attribute::Returned);
 614       ++NumReturned;
 615       Changed = true;
 616     }
 617   }
 618
 619   return Changed;
 620 }
 621
 622 /// If a callsite has arguments that are also arguments to the parent function,
 623 /// try to propagate attributes from the callsite's arguments to the parent's
 624 /// arguments. This may be important because inlining can cause information loss
 625 /// when attribute knowledge disappears with the inlined call.
 626 static bool addArgumentAttrsFromCallsites(Function &F) {
 627   if (!EnableNonnullArgPropagation)
 628     return false;
 629
 630   bool Changed = false;
 631
 632   // For an argument attribute to transfer from a callsite to the parent, the
 633   // call must be guaranteed to execute every time the parent is called.
 634   // Conservatively, just check for calls in the entry block that are guaranteed
 635   // to execute.
 636   // TODO: This could be enhanced by testing if the callsite post-dominates the
 637   // entry block or by doing simple forward walks or backward walks to the
 638   // callsite.
 639   BasicBlock &Entry = F.getEntryBlock();
 640   for (Instruction &I : Entry) {
 641     if (auto CS = CallSite(&I)) {
 642       if (auto *CalledFunc = CS.getCalledFunction()) {
 643         for (auto &CSArg : CalledFunc->args()) {
 644           if (!CSArg.hasNonNullAttr())
 645             continue;
 646
 647           // If the non-null callsite argument operand is an argument to 'F'
 648           // (the caller) and the call is guaranteed to execute, then the value
 649           // must be non-null throughout 'F'.
 650           auto *FArg = dyn_cast<Argument>(CS.getArgOperand(CSArg.getArgNo()));
 651           if (FArg && !FArg->hasNonNullAttr()) {
 652             FArg->addAttr(Attribute::NonNull);
 653             Changed = true;
 654           }
 655         }
 656       }
 657     }
 658     if (!isGuaranteedToTransferExecutionToSuccessor(&I))
 659       break;
 660   }
 661
 662   return Changed;
 663 }
 664
 665 static bool addReadAttr(Argument *A, Attribute::AttrKind R) {
 666   assert((R == Attribute::ReadOnly || R == Attribute::ReadNone)
 667          && "Must be a Read attribute.");
 668   assert(A && "Argument must not be null.");
 669
 670   // If the argument already has the attribute, nothing needs to be done.
 671   if (A->hasAttribute(R))
 672       return false;
 673
 674   // Otherwise, remove potentially conflicting attribute, add the new one,
 675   // and update statistics.
 676   A->removeAttr(Attribute::WriteOnly);
 677   A->removeAttr(Attribute::ReadOnly);
 678   A->removeAttr(Attribute::ReadNone);
 679   A->addAttr(R);
 680   R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
 681   return true;
 682 }
 683
 684 /// Deduce nocapture attributes for the SCC.
 685 static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) {
 686   bool Changed = false;
 687
 688   ArgumentGraph AG;
 689
 690   // Check each function in turn, determining which pointer arguments are not
 691   // captured.
 692   for (Function *F : SCCNodes) {
 693     // We can infer and propagate function attributes only when we know that the
 694     // definition we'll get at link time is *exactly* the definition we see now.
 695     // For more details, see GlobalValue::mayBeDerefined.
 696     if (!F->hasExactDefinition())
 697       continue;
 698
 699     Changed |= addArgumentAttrsFromCallsites(*F);
 700
 701     // Functions that are readonly (or readnone) and nounwind and don't return
 702     // a value can't capture arguments. Don't analyze them.
 703     if (F->onlyReadsMemory() && F->doesNotThrow() &&
 704         F->getReturnType()->isVoidTy()) {
 705       for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
 706            ++A) {
 707         if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
 708           A->addAttr(Attribute::NoCapture);
 709           ++NumNoCapture;
 710           Changed = true;
 711         }
 712       }
 713       continue;
 714     }
 715
 716     for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
 717          ++A) {
 718       if (!A->getType()->isPointerTy())
 719         continue;
 720       bool HasNonLocalUses = false;
 721       if (!A->hasNoCaptureAttr()) {
 722         ArgumentUsesTracker Tracker(SCCNodes);
 723         PointerMayBeCaptured(&*A, &Tracker);
 724         if (!Tracker.Captured) {
 725           if (Tracker.Uses.empty()) {
 726             // If it's trivially not captured, mark it nocapture now.
 727             A->addAttr(Attribute::NoCapture);
 728             ++NumNoCapture;
 729             Changed = true;
 730           } else {
 731             // If it's not trivially captured and not trivially not captured,
 732             // then it must be calling into another function in our SCC. Save
 733             // its particulars for Argument-SCC analysis later.
 734             ArgumentGraphNode *Node = AG[&*A];
 735             for (Argument *Use : Tracker.Uses) {
 736               Node->Uses.push_back(AG[Use]);
 737               if (Use != &*A)
 738                 HasNonLocalUses = true;
 739             }
 740           }
 741         }
 742         // Otherwise, it's captured. Don't bother doing SCC analysis on it.
 743       }
 744       if (!HasNonLocalUses && !A->onlyReadsMemory()) {
 745         // Can we determine that it's readonly/readnone without doing an SCC?
 746         // Note that we don't allow any calls at all here, or else our result
 747         // will be dependent on the iteration order through the functions in the
 748         // SCC.
 749         SmallPtrSet<Argument *, 8> Self;
 750         Self.insert(&*A);
 751         Attribute::AttrKind R = determinePointerReadAttrs(&*A, Self);
 752         if (R != Attribute::None)
 753           Changed = addReadAttr(A, R);
 754       }
 755     }
 756   }
 757
 758   // The graph we've collected is partial because we stopped scanning for
 759   // argument uses once we solved the argument trivially. These partial nodes
 760   // show up as ArgumentGraphNode objects with an empty Uses list, and for
 761   // these nodes the final decision about whether they capture has already been
 762   // made.  If the definition doesn't have a 'nocapture' attribute by now, it
 763   // captures.
 764
 765   for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
 766     const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
 767     if (ArgumentSCC.size() == 1) {
 768       if (!ArgumentSCC[0]->Definition)
 769         continue; // synthetic root node
 770
 771       // eg. "void f(int* x) { if (...) f(x); }"
 772       if (ArgumentSCC[0]->Uses.size() == 1 &&
 773           ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
 774         Argument *A = ArgumentSCC[0]->Definition;
 775         A->addAttr(Attribute::NoCapture);
 776         ++NumNoCapture;
 777         Changed = true;
 778       }
 779       continue;
 780     }
 781
 782     bool SCCCaptured = false;
 783     for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
 784          I != E && !SCCCaptured; ++I) {
 785       ArgumentGraphNode *Node = *I;
 786       if (Node->Uses.empty()) {
 787         if (!Node->Definition->hasNoCaptureAttr())
 788           SCCCaptured = true;
 789       }
 790     }
 791     if (SCCCaptured)
 792       continue;
 793
 794     SmallPtrSet<Argument *, 8> ArgumentSCCNodes;
 795     // Fill ArgumentSCCNodes with the elements of the ArgumentSCC.  Used for
 796     // quickly looking up whether a given Argument is in this ArgumentSCC.
 797     for (ArgumentGraphNode *I : ArgumentSCC) {
 798       ArgumentSCCNodes.insert(I->Definition);
 799     }
 800
 801     for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
 802          I != E && !SCCCaptured; ++I) {
 803       ArgumentGraphNode *N = *I;
 804       for (ArgumentGraphNode *Use : N->Uses) {
 805         Argument *A = Use->Definition;
 806         if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
 807           continue;
 808         SCCCaptured = true;
 809         break;
 810       }
 811     }
 812     if (SCCCaptured)
 813       continue;
 814
 815     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
 816       Argument *A = ArgumentSCC[i]->Definition;
 817       A->addAttr(Attribute::NoCapture);
 818       ++NumNoCapture;
 819       Changed = true;
 820     }
 821
 822     // We also want to compute readonly/readnone. With a small number of false
 823     // negatives, we can assume that any pointer which is captured isn't going
 824     // to be provably readonly or readnone, since by definition we can't
 825     // analyze all uses of a captured pointer.
 826     //
 827     // The false negatives happen when the pointer is captured by a function
 828     // that promises readonly/readnone behaviour on the pointer, then the
 829     // pointer's lifetime ends before anything that writes to arbitrary memory.
 830     // Also, a readonly/readnone pointer may be returned, but returning a
 831     // pointer is capturing it.
 832
 833     Attribute::AttrKind ReadAttr = Attribute::ReadNone;
 834     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
 835       Argument *A = ArgumentSCC[i]->Definition;
 836       Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes);
 837       if (K == Attribute::ReadNone)
 838         continue;
 839       if (K == Attribute::ReadOnly) {
 840         ReadAttr = Attribute::ReadOnly;
 841         continue;
 842       }
 843       ReadAttr = K;
 844       break;
 845     }
 846
 847     if (ReadAttr != Attribute::None) {
 848       for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
 849         Argument *A = ArgumentSCC[i]->Definition;
 850         Changed = addReadAttr(A, ReadAttr);
 851       }
 852     }
 853   }
 854
 855   return Changed;
 856 }
 857
 858 /// Tests whether a function is "malloc-like".
 859 ///
 860 /// A function is "malloc-like" if it returns either null or a pointer that
 861 /// doesn't alias any other pointer visible to the caller.
 862 static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) {
 863   SmallSetVector<Value *, 8> FlowsToReturn;
 864   for (BasicBlock &BB : *F)
 865     if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
 866       FlowsToReturn.insert(Ret->getReturnValue());
 867
 868   for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
 869     Value *RetVal = FlowsToReturn[i];
 870
 871     if (Constant *C = dyn_cast<Constant>(RetVal)) {
 872       if (!C->isNullValue() && !isa<UndefValue>(C))
 873         return false;
 874
 875       continue;
 876     }
 877
 878     if (isa<Argument>(RetVal))
 879       return false;
 880
 881     if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
 882       switch (RVI->getOpcode()) {
 883       // Extend the analysis by looking upwards.
 884       case Instruction::BitCast:
 885       case Instruction::GetElementPtr:
 886       case Instruction::AddrSpaceCast:
 887         FlowsToReturn.insert(RVI->getOperand(0));
 888         continue;
 889       case Instruction::Select: {
 890         SelectInst *SI = cast<SelectInst>(RVI);
 891         FlowsToReturn.insert(SI->getTrueValue());
 892         FlowsToReturn.insert(SI->getFalseValue());
 893         continue;
 894       }
 895       case Instruction::PHI: {
 896         PHINode *PN = cast<PHINode>(RVI);
 897         for (Value *IncValue : PN->incoming_values())
 898           FlowsToReturn.insert(IncValue);
 899         continue;
 900       }
 901
 902       // Check whether the pointer came from an allocation.
 903       case Instruction::Alloca:
 904         break;
 905       case Instruction::Call:
 906       case Instruction::Invoke: {
 907         CallSite CS(RVI);
 908         if (CS.hasRetAttr(Attribute::NoAlias))
 909           break;
 910         if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
 911           break;
 912         LLVM_FALLTHROUGH;
 913       }
 914       default:
 915         return false; // Did not come from an allocation.
 916       }
 917
 918     if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
 919       return false;
 920   }
 921
 922   return true;
 923 }
 924
 925 /// Deduce noalias attributes for the SCC.
 926 static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes) {
 927   // Check each function in turn, determining which functions return noalias
 928   // pointers.
 929   for (Function *F : SCCNodes) {
 930     // Already noalias.
 931     if (F->returnDoesNotAlias())
 932       continue;
 933
 934     // We can infer and propagate function attributes only when we know that the
 935     // definition we'll get at link time is *exactly* the definition we see now.
 936     // For more details, see GlobalValue::mayBeDerefined.
 937     if (!F->hasExactDefinition())
 938       return false;
 939
 940     // We annotate noalias return values, which are only applicable to
 941     // pointer types.
 942     if (!F->getReturnType()->isPointerTy())
 943       continue;
 944
 945     if (!isFunctionMallocLike(F, SCCNodes))
 946       return false;
 947   }
 948
 949   bool MadeChange = false;
 950   for (Function *F : SCCNodes) {
 951     if (F->returnDoesNotAlias() ||
 952         !F->getReturnType()->isPointerTy())
 953       continue;
 954
 955     F->setReturnDoesNotAlias();
 956     ++NumNoAlias;
 957     MadeChange = true;
 958   }
 959
 960   return MadeChange;
 961 }
 962
 963 /// Tests whether this function is known to not return null.
 964 ///
 965 /// Requires that the function returns a pointer.
 966 ///
 967 /// Returns true if it believes the function will not return a null, and sets
 968 /// \p Speculative based on whether the returned conclusion is a speculative
 969 /// conclusion due to SCC calls.
 970 static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes,
 971                             bool &Speculative) {
 972   assert(F->getReturnType()->isPointerTy() &&
 973          "nonnull only meaningful on pointer types");
 974   Speculative = false;
 975
 976   SmallSetVector<Value *, 8> FlowsToReturn;
 977   for (BasicBlock &BB : *F)
 978     if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
 979       FlowsToReturn.insert(Ret->getReturnValue());
 980
 981   auto &DL = F->getParent()->getDataLayout();
 982
 983   for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
 984     Value *RetVal = FlowsToReturn[i];
 985
 986     // If this value is locally known to be non-null, we're good
 987     if (isKnownNonZero(RetVal, DL))
 988       continue;
 989
 990     // Otherwise, we need to look upwards since we can't make any local
 991     // conclusions.
 992     Instruction *RVI = dyn_cast<Instruction>(RetVal);
 993     if (!RVI)
 994       return false;
 995     switch (RVI->getOpcode()) {
 996     // Extend the analysis by looking upwards.
 997     case Instruction::BitCast:
 998     case Instruction::GetElementPtr:
 999     case Instruction::AddrSpaceCast:
1000       FlowsToReturn.insert(RVI->getOperand(0));
1001       continue;
1002     case Instruction::Select: {
1003       SelectInst *SI = cast<SelectInst>(RVI);
1004       FlowsToReturn.insert(SI->getTrueValue());
1005       FlowsToReturn.insert(SI->getFalseValue());
1006       continue;
1007     }
1008     case Instruction::PHI: {
1009       PHINode *PN = cast<PHINode>(RVI);
1010       for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1011         FlowsToReturn.insert(PN->getIncomingValue(i));
1012       continue;
1013     }
1014     case Instruction::Call:
1015     case Instruction::Invoke: {
1016       CallSite CS(RVI);
1017       Function *Callee = CS.getCalledFunction();
1018       // A call to a node within the SCC is assumed to return null until
1019       // proven otherwise
1020       if (Callee && SCCNodes.count(Callee)) {
1021         Speculative = true;
1022         continue;
1023       }
1024       return false;
1025     }
1026     default:
1027       return false; // Unknown source, may be null
1028     };
1029     llvm_unreachable("should have either continued or returned");
1030   }
1031
1032   return true;
1033 }
1034
1035 /// Deduce nonnull attributes for the SCC.
1036 static bool addNonNullAttrs(const SCCNodeSet &SCCNodes) {
1037   // Speculative that all functions in the SCC return only nonnull
1038   // pointers.  We may refute this as we analyze functions.
1039   bool SCCReturnsNonNull = true;
1040
1041   bool MadeChange = false;
1042
1043   // Check each function in turn, determining which functions return nonnull
1044   // pointers.
1045   for (Function *F : SCCNodes) {
1046     // Already nonnull.
1047     if (F->getAttributes().hasAttribute(AttributeList::ReturnIndex,
1048                                         Attribute::NonNull))
1049       continue;
1050
1051     // We can infer and propagate function attributes only when we know that the
1052     // definition we'll get at link time is *exactly* the definition we see now.
1053     // For more details, see GlobalValue::mayBeDerefined.
1054     if (!F->hasExactDefinition())
1055       return false;
1056
1057     // We annotate nonnull return values, which are only applicable to
1058     // pointer types.
1059     if (!F->getReturnType()->isPointerTy())
1060       continue;
1061
1062     bool Speculative = false;
1063     if (isReturnNonNull(F, SCCNodes, Speculative)) {
1064       if (!Speculative) {
1065         // Mark the function eagerly since we may discover a function
1066         // which prevents us from speculating about the entire SCC
1067         LLVM_DEBUG(dbgs() << "Eagerly marking " << F->getName()
1068                           << " as nonnull\n");
1069         F->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
1070         ++NumNonNullReturn;
1071         MadeChange = true;
1072       }
1073       continue;
1074     }
1075     // At least one function returns something which could be null, can't
1076     // speculate any more.
1077     SCCReturnsNonNull = false;
1078   }
1079
1080   if (SCCReturnsNonNull) {
1081     for (Function *F : SCCNodes) {
1082       if (F->getAttributes().hasAttribute(AttributeList::ReturnIndex,
1083                                           Attribute::NonNull) ||
1084           !F->getReturnType()->isPointerTy())
1085         continue;
1086
1087       LLVM_DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
1088       F->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
1089       ++NumNonNullReturn;
1090       MadeChange = true;
1091     }
1092   }
1093
1094   return MadeChange;
1095 }
1096
1097 namespace {
1098
1099 /// Collects a set of attribute inference requests and performs them all in one
1100 /// go on a single SCC Node. Inference involves scanning function bodies
1101 /// looking for instructions that violate attribute assumptions.
1102 /// As soon as all the bodies are fine we are free to set the attribute.
1103 /// Customization of inference for individual attributes is performed by
1104 /// providing a handful of predicates for each attribute.
1105 class AttributeInferer {
1106 public:
1107   /// Describes a request for inference of a single attribute.
1108   struct InferenceDescriptor {
1109
1110     /// Returns true if this function does not have to be handled.
1111     /// General intent for this predicate is to provide an optimization
1112     /// for functions that do not need this attribute inference at all
1113     /// (say, for functions that already have the attribute).
1114     std::function<bool(const Function &)> SkipFunction;
1115
1116     /// Returns true if this instruction violates attribute assumptions.
1117     std::function<bool(Instruction &)> InstrBreaksAttribute;
1118
1119     /// Sets the inferred attribute for this function.
1120     std::function<void(Function &)> SetAttribute;
1121
1122     /// Attribute we derive.
1123     Attribute::AttrKind AKind;
1124
1125     /// If true, only "exact" definitions can be used to infer this attribute.
1126     /// See GlobalValue::isDefinitionExact.
1127     bool RequiresExactDefinition;
1128
1129     InferenceDescriptor(Attribute::AttrKind AK,
1130                         std::function<bool(const Function &)> SkipFunc,
1131                         std::function<bool(Instruction &)> InstrScan,
1132                         std::function<void(Function &)> SetAttr,
1133                         bool ReqExactDef)
1134         : SkipFunction(SkipFunc), InstrBreaksAttribute(InstrScan),
1135           SetAttribute(SetAttr), AKind(AK),
1136           RequiresExactDefinition(ReqExactDef) {}
1137   };
1138
1139 private:
1140   SmallVector<InferenceDescriptor, 4> InferenceDescriptors;
1141
1142 public:
1143   void registerAttrInference(InferenceDescriptor AttrInference) {
1144     InferenceDescriptors.push_back(AttrInference);
1145   }
1146
1147   bool run(const SCCNodeSet &SCCNodes);
1148 };
1149
1150 /// Perform all the requested attribute inference actions according to the
1151 /// attribute predicates stored before.
1152 bool AttributeInferer::run(const SCCNodeSet &SCCNodes) {
1153   SmallVector<InferenceDescriptor, 4> InferInSCC = InferenceDescriptors;
1154   // Go through all the functions in SCC and check corresponding attribute
1155   // assumptions for each of them. Attributes that are invalid for this SCC
1156   // will be removed from InferInSCC.
1157   for (Function *F : SCCNodes) {
1158
1159     // No attributes whose assumptions are still valid - done.
1160     if (InferInSCC.empty())
1161       return false;
1162
1163     // Check if our attributes ever need scanning/can be scanned.
1164     llvm::erase_if(InferInSCC, [F](const InferenceDescriptor &ID) {
1165       if (ID.SkipFunction(*F))
1166         return false;
1167
1168       // Remove from further inference (invalidate) when visiting a function
1169       // that has no instructions to scan/has an unsuitable definition.
1170       return F->isDeclaration() ||
1171              (ID.RequiresExactDefinition && !F->hasExactDefinition());
1172     });
1173
1174     // For each attribute still in InferInSCC that doesn't explicitly skip F,
1175     // set up the F instructions scan to verify assumptions of the attribute.
1176     SmallVector<InferenceDescriptor, 4> InferInThisFunc;
1177     llvm::copy_if(
1178         InferInSCC, std::back_inserter(InferInThisFunc),
1179         [F](const InferenceDescriptor &ID) { return !ID.SkipFunction(*F); });
1180
1181     if (InferInThisFunc.empty())
1182       continue;
1183
1184     // Start instruction scan.
1185     for (Instruction &I : instructions(*F)) {
1186       llvm::erase_if(InferInThisFunc, [&](const InferenceDescriptor &ID) {
1187         if (!ID.InstrBreaksAttribute(I))
1188           return false;
1189         // Remove attribute from further inference on any other functions
1190         // because attribute assumptions have just been violated.
1191         llvm::erase_if(InferInSCC, [&ID](const InferenceDescriptor &D) {
1192           return D.AKind == ID.AKind;
1193         });
1194         // Remove attribute from the rest of current instruction scan.
1195         return true;
1196       });
1197
1198       if (InferInThisFunc.empty())
1199         break;
1200     }
1201   }
1202
1203   if (InferInSCC.empty())
1204     return false;
1205
1206   bool Changed = false;
1207   for (Function *F : SCCNodes)
1208     // At this point InferInSCC contains only functions that were either:
1209     //   - explicitly skipped from scan/inference, or
1210     //   - verified to have no instructions that break attribute assumptions.
1211     // Hence we just go and force the attribute for all non-skipped functions.
1212     for (auto &ID : InferInSCC) {
1213       if (ID.SkipFunction(*F))
1214         continue;
1215       Changed = true;
1216       ID.SetAttribute(*F);
1217     }
1218   return Changed;
1219 }
1220
1221 } // end anonymous namespace
1222
1223 /// Helper for non-Convergent inference predicate InstrBreaksAttribute.
1224 static bool InstrBreaksNonConvergent(Instruction &I,
1225                                      const SCCNodeSet &SCCNodes) {
1226   const CallSite CS(&I);
1227   // Breaks non-convergent assumption if CS is a convergent call to a function
1228   // not in the SCC.
1229   return CS && CS.isConvergent() && SCCNodes.count(CS.getCalledFunction()) == 0;
1230 }
1231
1232 /// Helper for NoUnwind inference predicate InstrBreaksAttribute.
1233 static bool InstrBreaksNonThrowing(Instruction &I, const SCCNodeSet &SCCNodes) {
1234   if (!I.mayThrow())
1235     return false;
1236   if (const auto *CI = dyn_cast<CallInst>(&I)) {
1237     if (Function *Callee = CI->getCalledFunction()) {
1238       // I is a may-throw call to a function inside our SCC. This doesn't
1239       // invalidate our current working assumption that the SCC is no-throw; we
1240       // just have to scan that other function.
1241       if (SCCNodes.count(Callee) > 0)
1242         return false;
1243     }
1244   }
1245   return true;
1246 }
1247
1248 /// Helper for NoFree inference predicate InstrBreaksAttribute.
1249 static bool InstrBreaksNoFree(Instruction &I, const SCCNodeSet &SCCNodes) {
1250   CallSite CS(&I);
1251   if (!CS)
1252     return false;
1253
1254   Function *Callee = CS.getCalledFunction();
1255   if (!Callee)
1256     return true;
1257
1258   if (Callee->doesNotFreeMemory())
1259     return false;
1260
1261   if (SCCNodes.count(Callee) > 0)
1262     return false;
1263
1264   return true;
1265 }
1266
1267 /// Infer attributes from all functions in the SCC by scanning every
1268 /// instruction for compliance to the attribute assumptions. Currently it
1269 /// does:
1270 ///   - removal of Convergent attribute
1271 ///   - addition of NoUnwind attribute
1272 ///
1273 /// Returns true if any changes to function attributes were made.
1274 static bool inferAttrsFromFunctionBodies(const SCCNodeSet &SCCNodes) {
1275
1276   AttributeInferer AI;
1277
1278   // Request to remove the convergent attribute from all functions in the SCC
1279   // if every callsite within the SCC is not convergent (except for calls
1280   // to functions within the SCC).
1281   // Note: Removal of the attr from the callsites will happen in
1282   // InstCombineCalls separately.
1283   AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1284       Attribute::Convergent,
1285       // Skip non-convergent functions.
1286       [](const Function &F) { return !F.isConvergent(); },
1287       // Instructions that break non-convergent assumption.
1288       [SCCNodes](Instruction &I) {
1289         return InstrBreaksNonConvergent(I, SCCNodes);
1290       },
1291       [](Function &F) {
1292         LLVM_DEBUG(dbgs() << "Removing convergent attr from fn " << F.getName()
1293                           << "\n");
1294         F.setNotConvergent();
1295       },
1296       /* RequiresExactDefinition= */ false});
1297
1298   if (!DisableNoUnwindInference)
1299     // Request to infer nounwind attribute for all the functions in the SCC if
1300     // every callsite within the SCC is not throwing (except for calls to
1301     // functions within the SCC). Note that nounwind attribute suffers from
1302     // derefinement - results may change depending on how functions are
1303     // optimized. Thus it can be inferred only from exact definitions.
1304     AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1305         Attribute::NoUnwind,
1306         // Skip non-throwing functions.
1307         [](const Function &F) { return F.doesNotThrow(); },
1308         // Instructions that break non-throwing assumption.
1309         [SCCNodes](Instruction &I) {
1310           return InstrBreaksNonThrowing(I, SCCNodes);
1311         },
1312         [](Function &F) {
1313           LLVM_DEBUG(dbgs()
1314                      << "Adding nounwind attr to fn " << F.getName() << "\n");
1315           F.setDoesNotThrow();
1316           ++NumNoUnwind;
1317         },
1318         /* RequiresExactDefinition= */ true});
1319
1320   if (!DisableNoFreeInference)
1321     // Request to infer nofree attribute for all the functions in the SCC if
1322     // every callsite within the SCC does not directly or indirectly free
1323     // memory (except for calls to functions within the SCC). Note that nofree
1324     // attribute suffers from derefinement - results may change depending on
1325     // how functions are optimized. Thus it can be inferred only from exact
1326     // definitions.
1327     AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1328         Attribute::NoFree,
1329         // Skip functions known not to free memory.
1330         [](const Function &F) { return F.doesNotFreeMemory(); },
1331         // Instructions that break non-deallocating assumption.
1332         [SCCNodes](Instruction &I) {
1333           return InstrBreaksNoFree(I, SCCNodes);
1334         },
1335         [](Function &F) {
1336           LLVM_DEBUG(dbgs()
1337                      << "Adding nofree attr to fn " << F.getName() << "\n");
1338           F.setDoesNotFreeMemory();
1339           ++NumNoFree;
1340         },
1341         /* RequiresExactDefinition= */ true});
1342
1343   // Perform all the requested attribute inference actions.
1344   return AI.run(SCCNodes);
1345 }
1346
1347 static bool setDoesNotRecurse(Function &F) {
1348   if (F.doesNotRecurse())
1349     return false;
1350   F.setDoesNotRecurse();
1351   ++NumNoRecurse;
1352   return true;
1353 }
1354
1355 static bool addNoRecurseAttrs(const SCCNodeSet &SCCNodes) {
1356   // Try and identify functions that do not recurse.
1357
1358   // If the SCC contains multiple nodes we know for sure there is recursion.
1359   if (SCCNodes.size() != 1)
1360     return false;
1361
1362   Function *F = *SCCNodes.begin();
1363   if (!F || !F->hasExactDefinition() || F->doesNotRecurse())
1364     return false;
1365
1366   // If all of the calls in F are identifiable and are to norecurse functions, F
1367   // is norecurse. This check also detects self-recursion as F is not currently
1368   // marked norecurse, so any called from F to F will not be marked norecurse.
1369   for (auto &BB : *F)
1370     for (auto &I : BB.instructionsWithoutDebug())
1371       if (auto CS = CallSite(&I)) {
1372         Function *Callee = CS.getCalledFunction();
1373         if (!Callee || Callee == F || !Callee->doesNotRecurse())
1374           // Function calls a potentially recursive function.
1375           return false;
1376       }
1377
1378   // Every call was to a non-recursive function other than this function, and
1379   // we have no indirect recursion as the SCC size is one. This function cannot
1380   // recurse.
1381   return setDoesNotRecurse(*F);
1382 }
1383
1384 template <typename AARGetterT>
1385 static bool deriveAttrsInPostOrder(SCCNodeSet &SCCNodes,
1386                                    AARGetterT &&AARGetter,
1387                                    bool HasUnknownCall) {
1388   bool Changed = false;
1389
1390   // Bail if the SCC only contains optnone functions.
1391   if (SCCNodes.empty())
1392     return Changed;
1393
1394   Changed |= addArgumentReturnedAttrs(SCCNodes);
1395   Changed |= addReadAttrs(SCCNodes, AARGetter);
1396   Changed |= addArgumentAttrs(SCCNodes);
1397
1398   // If we have no external nodes participating in the SCC, we can deduce some
1399   // more precise attributes as well.
1400   if (!HasUnknownCall) {
1401     Changed |= addNoAliasAttrs(SCCNodes);
1402     Changed |= addNonNullAttrs(SCCNodes);
1403     Changed |= inferAttrsFromFunctionBodies(SCCNodes);
1404     Changed |= addNoRecurseAttrs(SCCNodes);
1405   }
1406
1407   return Changed;
1408 }
1409
1410 PreservedAnalyses PostOrderFunctionAttrsPass::run(LazyCallGraph::SCC &C,
1411                                                   CGSCCAnalysisManager &AM,
1412                                                   LazyCallGraph &CG,
1413                                                   CGSCCUpdateResult &) {
1414   FunctionAnalysisManager &FAM =
1415       AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
1416
1417   // We pass a lambda into functions to wire them up to the analysis manager
1418   // for getting function analyses.
1419   auto AARGetter = [&](Function &F) -> AAResults & {
1420     return FAM.getResult<AAManager>(F);
1421   };
1422
1423   // Fill SCCNodes with the elements of the SCC. Also track whether there are
1424   // any external or opt-none nodes that will prevent us from optimizing any
1425   // part of the SCC.
1426   SCCNodeSet SCCNodes;
1427   bool HasUnknownCall = false;
1428   for (LazyCallGraph::Node &N : C) {
1429     Function &F = N.getFunction();
1430     if (F.hasOptNone() || F.hasFnAttribute(Attribute::Naked)) {
1431       // Treat any function we're trying not to optimize as if it were an
1432       // indirect call and omit it from the node set used below.
1433       HasUnknownCall = true;
1434       continue;
1435     }
1436     // Track whether any functions in this SCC have an unknown call edge.
1437     // Note: if this is ever a performance hit, we can common it with
1438     // subsequent routines which also do scans over the instructions of the
1439     // function.
1440     if (!HasUnknownCall)
1441       for (Instruction &I : instructions(F))
1442         if (auto CS = CallSite(&I))
1443           if (!CS.getCalledFunction()) {
1444             HasUnknownCall = true;
1445             break;
1446           }
1447
1448     SCCNodes.insert(&F);
1449   }
1450
1451   if (deriveAttrsInPostOrder(SCCNodes, AARGetter, HasUnknownCall))
1452     return PreservedAnalyses::none();
1453
1454   return PreservedAnalyses::all();
1455 }
1456
1457 namespace {
1458
1459 struct PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass {
1460   // Pass identification, replacement for typeid
1461   static char ID;
1462
1463   PostOrderFunctionAttrsLegacyPass() : CallGraphSCCPass(ID) {
1464     initializePostOrderFunctionAttrsLegacyPassPass(
1465         *PassRegistry::getPassRegistry());
1466   }
1467
1468   bool runOnSCC(CallGraphSCC &SCC) override;
1469
1470   void getAnalysisUsage(AnalysisUsage &AU) const override {
1471     AU.setPreservesCFG();
1472     AU.addRequired<AssumptionCacheTracker>();
1473     getAAResultsAnalysisUsage(AU);
1474     CallGraphSCCPass::getAnalysisUsage(AU);
1475   }
1476 };
1477
1478 } // end anonymous namespace
1479
1480 char PostOrderFunctionAttrsLegacyPass::ID = 0;
1481 INITIALIZE_PASS_BEGIN(PostOrderFunctionAttrsLegacyPass, "functionattrs",
1482                       "Deduce function attributes", false, false)
1483 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1484 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
1485 INITIALIZE_PASS_END(PostOrderFunctionAttrsLegacyPass, "functionattrs",
1486                     "Deduce function attributes", false, false)
1487
1488 Pass *llvm::createPostOrderFunctionAttrsLegacyPass() {
1489   return new PostOrderFunctionAttrsLegacyPass();
1490 }
1491
1492 template <typename AARGetterT>
1493 static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter) {
1494
1495   // Fill SCCNodes with the elements of the SCC. Used for quickly looking up
1496   // whether a given CallGraphNode is in this SCC. Also track whether there are
1497   // any external or opt-none nodes that will prevent us from optimizing any
1498   // part of the SCC.
1499   SCCNodeSet SCCNodes;
1500   bool ExternalNode = false;
1501   for (CallGraphNode *I : SCC) {
1502     Function *F = I->getFunction();
1503     if (!F || F->hasOptNone() || F->hasFnAttribute(Attribute::Naked)) {
1504       // External node or function we're trying not to optimize - we both avoid
1505       // transform them and avoid leveraging information they provide.
1506       ExternalNode = true;
1507       continue;
1508     }
1509
1510     SCCNodes.insert(F);
1511   }
1512
1513   return deriveAttrsInPostOrder(SCCNodes, AARGetter, ExternalNode);
1514 }
1515
1516 bool PostOrderFunctionAttrsLegacyPass::runOnSCC(CallGraphSCC &SCC) {
1517   if (skipSCC(SCC))
1518     return false;
1519   return runImpl(SCC, LegacyAARGetter(*this));
1520 }
1521
1522 namespace {
1523
1524 struct ReversePostOrderFunctionAttrsLegacyPass : public ModulePass {
1525   // Pass identification, replacement for typeid
1526   static char ID;
1527
1528   ReversePostOrderFunctionAttrsLegacyPass() : ModulePass(ID) {
1529     initializeReversePostOrderFunctionAttrsLegacyPassPass(
1530         *PassRegistry::getPassRegistry());
1531   }
1532
1533   bool runOnModule(Module &M) override;
1534
1535   void getAnalysisUsage(AnalysisUsage &AU) const override {
1536     AU.setPreservesCFG();
1537     AU.addRequired<CallGraphWrapperPass>();
1538     AU.addPreserved<CallGraphWrapperPass>();
1539   }
1540 };
1541
1542 } // end anonymous namespace
1543
1544 char ReversePostOrderFunctionAttrsLegacyPass::ID = 0;
1545
1546 INITIALIZE_PASS_BEGIN(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs",
1547                       "Deduce function attributes in RPO", false, false)
1548 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
1549 INITIALIZE_PASS_END(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs",
1550                     "Deduce function attributes in RPO", false, false)
1551
1552 Pass *llvm::createReversePostOrderFunctionAttrsPass() {
1553   return new ReversePostOrderFunctionAttrsLegacyPass();
1554 }
1555
1556 static bool addNoRecurseAttrsTopDown(Function &F) {
1557   // We check the preconditions for the function prior to calling this to avoid
1558   // the cost of building up a reversible post-order list. We assert them here
1559   // to make sure none of the invariants this relies on were violated.
1560   assert(!F.isDeclaration() && "Cannot deduce norecurse without a definition!");
1561   assert(!F.doesNotRecurse() &&
1562          "This function has already been deduced as norecurs!");
1563   assert(F.hasInternalLinkage() &&
1564          "Can only do top-down deduction for internal linkage functions!");
1565
1566   // If F is internal and all of its uses are calls from a non-recursive
1567   // functions, then none of its calls could in fact recurse without going
1568   // through a function marked norecurse, and so we can mark this function too
1569   // as norecurse. Note that the uses must actually be calls -- otherwise
1570   // a pointer to this function could be returned from a norecurse function but
1571   // this function could be recursively (indirectly) called. Note that this
1572   // also detects if F is directly recursive as F is not yet marked as
1573   // a norecurse function.
1574   for (auto *U : F.users()) {
1575     auto *I = dyn_cast<Instruction>(U);
1576     if (!I)
1577       return false;
1578     CallSite CS(I);
1579     if (!CS || !CS.getParent()->getParent()->doesNotRecurse())
1580       return false;
1581   }
1582   return setDoesNotRecurse(F);
1583 }
1584
1585 static bool deduceFunctionAttributeInRPO(Module &M, CallGraph &CG) {
1586   // We only have a post-order SCC traversal (because SCCs are inherently
1587   // discovered in post-order), so we accumulate them in a vector and then walk
1588   // it in reverse. This is simpler than using the RPO iterator infrastructure
1589   // because we need to combine SCC detection and the PO walk of the call
1590   // graph. We can also cheat egregiously because we're primarily interested in
1591   // synthesizing norecurse and so we can only save the singular SCCs as SCCs
1592   // with multiple functions in them will clearly be recursive.
1593   SmallVector<Function *, 16> Worklist;
1594   for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
1595     if (I->size() != 1)
1596       continue;
1597
1598     Function *F = I->front()->getFunction();
1599     if (F && !F->isDeclaration() && !F->doesNotRecurse() &&
1600         F->hasInternalLinkage())
1601       Worklist.push_back(F);
1602   }
1603
1604   bool Changed = false;
1605   for (auto *F : llvm::reverse(Worklist))
1606     Changed |= addNoRecurseAttrsTopDown(*F);
1607
1608   return Changed;
1609 }
1610
1611 bool ReversePostOrderFunctionAttrsLegacyPass::runOnModule(Module &M) {
1612   if (skipModule(M))
1613     return false;
1614
1615   auto &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
1616
1617   return deduceFunctionAttributeInRPO(M, CG);
1618 }
1619
1620 PreservedAnalyses
1621 ReversePostOrderFunctionAttrsPass::run(Module &M, ModuleAnalysisManager &AM) {
1622   auto &CG = AM.getResult<CallGraphAnalysis>(M);
1623
1624   if (!deduceFunctionAttributeInRPO(M, CG))
1625     return PreservedAnalyses::all();
1626
1627   PreservedAnalyses PA;
1628   PA.preserve<CallGraphAnalysis>();
1629   return PA;
1630 }