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

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