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

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