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