LLVM  mainline
FunctionAttrs.cpp
Go to the documentation of this file.
00001 //===- FunctionAttrs.cpp - Pass which marks functions attributes ----------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 ///
00010 /// \file
00011 /// This file implements interprocedural passes which walk the
00012 /// call-graph deducing and/or propagating function attributes.
00013 ///
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "llvm/Transforms/IPO.h"
00017 #include "llvm/ADT/SCCIterator.h"
00018 #include "llvm/ADT/SetVector.h"
00019 #include "llvm/ADT/SmallSet.h"
00020 #include "llvm/ADT/Statistic.h"
00021 #include "llvm/ADT/StringSwitch.h"
00022 #include "llvm/Analysis/AliasAnalysis.h"
00023 #include "llvm/Analysis/AssumptionCache.h"
00024 #include "llvm/Analysis/BasicAliasAnalysis.h"
00025 #include "llvm/Analysis/CallGraph.h"
00026 #include "llvm/Analysis/CallGraphSCCPass.h"
00027 #include "llvm/Analysis/CaptureTracking.h"
00028 #include "llvm/Analysis/TargetLibraryInfo.h"
00029 #include "llvm/Analysis/ValueTracking.h"
00030 #include "llvm/IR/GlobalVariable.h"
00031 #include "llvm/IR/InstIterator.h"
00032 #include "llvm/IR/IntrinsicInst.h"
00033 #include "llvm/IR/LLVMContext.h"
00034 #include "llvm/Support/Debug.h"
00035 #include "llvm/Support/raw_ostream.h"
00036 #include "llvm/Analysis/TargetLibraryInfo.h"
00037 using namespace llvm;
00038 
00039 #define DEBUG_TYPE "functionattrs"
00040 
00041 STATISTIC(NumReadNone, "Number of functions marked readnone");
00042 STATISTIC(NumReadOnly, "Number of functions marked readonly");
00043 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
00044 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
00045 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
00046 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
00047 STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull");
00048 STATISTIC(NumNoRecurse, "Number of functions marked as norecurse");
00049 
00050 namespace {
00051 typedef SmallSetVector<Function *, 8> SCCNodeSet;
00052 }
00053 
00054 namespace {
00055 struct PostOrderFunctionAttrs : public CallGraphSCCPass {
00056   static char ID; // Pass identification, replacement for typeid
00057   PostOrderFunctionAttrs() : CallGraphSCCPass(ID) {
00058     initializePostOrderFunctionAttrsPass(*PassRegistry::getPassRegistry());
00059   }
00060 
00061   bool runOnSCC(CallGraphSCC &SCC) override;
00062 
00063   void getAnalysisUsage(AnalysisUsage &AU) const override {
00064     AU.setPreservesCFG();
00065     AU.addRequired<AssumptionCacheTracker>();
00066     AU.addRequired<TargetLibraryInfoWrapperPass>();
00067     CallGraphSCCPass::getAnalysisUsage(AU);
00068   }
00069 
00070 private:
00071   TargetLibraryInfo *TLI;
00072 };
00073 }
00074 
00075 char PostOrderFunctionAttrs::ID = 0;
00076 INITIALIZE_PASS_BEGIN(PostOrderFunctionAttrs, "functionattrs",
00077                       "Deduce function attributes", false, false)
00078 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
00079 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
00080 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
00081 INITIALIZE_PASS_END(PostOrderFunctionAttrs, "functionattrs",
00082                     "Deduce function attributes", false, false)
00083 
00084 Pass *llvm::createPostOrderFunctionAttrsPass() { return new PostOrderFunctionAttrs(); }
00085 
00086 namespace {
00087 /// The three kinds of memory access relevant to 'readonly' and
00088 /// 'readnone' attributes.
00089 enum MemoryAccessKind {
00090   MAK_ReadNone = 0,
00091   MAK_ReadOnly = 1,
00092   MAK_MayWrite = 2
00093 };
00094 }
00095 
00096 static MemoryAccessKind checkFunctionMemoryAccess(Function &F, AAResults &AAR,
00097                                                   const SCCNodeSet &SCCNodes) {
00098   FunctionModRefBehavior MRB = AAR.getModRefBehavior(&F);
00099   if (MRB == FMRB_DoesNotAccessMemory)
00100     // Already perfect!
00101     return MAK_ReadNone;
00102 
00103   // Definitions with weak linkage may be overridden at linktime with
00104   // something that writes memory, so treat them like declarations.
00105   if (F.isDeclaration() || F.mayBeOverridden()) {
00106     if (AliasAnalysis::onlyReadsMemory(MRB))
00107       return MAK_ReadOnly;
00108 
00109     // Conservatively assume it writes to memory.
00110     return MAK_MayWrite;
00111   }
00112 
00113   // Scan the function body for instructions that may read or write memory.
00114   bool ReadsMemory = false;
00115   for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
00116     Instruction *I = &*II;
00117 
00118     // Some instructions can be ignored even if they read or write memory.
00119     // Detect these now, skipping to the next instruction if one is found.
00120     CallSite CS(cast<Value>(I));
00121     if (CS) {
00122       // Ignore calls to functions in the same SCC.
00123       if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
00124         continue;
00125       FunctionModRefBehavior MRB = AAR.getModRefBehavior(CS);
00126 
00127       // If the call doesn't access memory, we're done.
00128       if (!(MRB & MRI_ModRef))
00129         continue;
00130 
00131       if (!AliasAnalysis::onlyAccessesArgPointees(MRB)) {
00132         // The call could access any memory. If that includes writes, give up.
00133         if (MRB & MRI_Mod)
00134           return MAK_MayWrite;
00135         // If it reads, note it.
00136         if (MRB & MRI_Ref)
00137           ReadsMemory = true;
00138         continue;
00139       }
00140 
00141       // Check whether all pointer arguments point to local memory, and
00142       // ignore calls that only access local memory.
00143       for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
00144            CI != CE; ++CI) {
00145         Value *Arg = *CI;
00146         if (!Arg->getType()->isPtrOrPtrVectorTy())
00147           continue;
00148 
00149         AAMDNodes AAInfo;
00150         I->getAAMetadata(AAInfo);
00151         MemoryLocation Loc(Arg, MemoryLocation::UnknownSize, AAInfo);
00152 
00153         // Skip accesses to local or constant memory as they don't impact the
00154         // externally visible mod/ref behavior.
00155         if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
00156           continue;
00157 
00158         if (MRB & MRI_Mod)
00159           // Writes non-local memory.  Give up.
00160           return MAK_MayWrite;
00161         if (MRB & MRI_Ref)
00162           // Ok, it reads non-local memory.
00163           ReadsMemory = true;
00164       }
00165       continue;
00166     } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
00167       // Ignore non-volatile loads from local memory. (Atomic is okay here.)
00168       if (!LI->isVolatile()) {
00169         MemoryLocation Loc = MemoryLocation::get(LI);
00170         if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
00171           continue;
00172       }
00173     } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
00174       // Ignore non-volatile stores to local memory. (Atomic is okay here.)
00175       if (!SI->isVolatile()) {
00176         MemoryLocation Loc = MemoryLocation::get(SI);
00177         if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
00178           continue;
00179       }
00180     } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) {
00181       // Ignore vaargs on local memory.
00182       MemoryLocation Loc = MemoryLocation::get(VI);
00183       if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
00184         continue;
00185     }
00186 
00187     // Any remaining instructions need to be taken seriously!  Check if they
00188     // read or write memory.
00189     if (I->mayWriteToMemory())
00190       // Writes memory.  Just give up.
00191       return MAK_MayWrite;
00192 
00193     // If this instruction may read memory, remember that.
00194     ReadsMemory |= I->mayReadFromMemory();
00195   }
00196 
00197   return ReadsMemory ? MAK_ReadOnly : MAK_ReadNone;
00198 }
00199 
00200 /// Deduce readonly/readnone attributes for the SCC.
00201 template <typename AARGetterT>
00202 static bool addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT AARGetter) {
00203   // Check if any of the functions in the SCC read or write memory.  If they
00204   // write memory then they can't be marked readnone or readonly.
00205   bool ReadsMemory = false;
00206   for (Function *F : SCCNodes) {
00207     // Call the callable parameter to look up AA results for this function.
00208     AAResults &AAR = AARGetter(*F);
00209 
00210     switch (checkFunctionMemoryAccess(*F, AAR, SCCNodes)) {
00211     case MAK_MayWrite:
00212       return false;
00213     case MAK_ReadOnly:
00214       ReadsMemory = true;
00215       break;
00216     case MAK_ReadNone:
00217       // Nothing to do!
00218       break;
00219     }
00220   }
00221 
00222   // Success!  Functions in this SCC do not access memory, or only read memory.
00223   // Give them the appropriate attribute.
00224   bool MadeChange = false;
00225   for (Function *F : SCCNodes) {
00226     if (F->doesNotAccessMemory())
00227       // Already perfect!
00228       continue;
00229 
00230     if (F->onlyReadsMemory() && ReadsMemory)
00231       // No change.
00232       continue;
00233 
00234     MadeChange = true;
00235 
00236     // Clear out any existing attributes.
00237     AttrBuilder B;
00238     B.addAttribute(Attribute::ReadOnly).addAttribute(Attribute::ReadNone);
00239     F->removeAttributes(
00240         AttributeSet::FunctionIndex,
00241         AttributeSet::get(F->getContext(), AttributeSet::FunctionIndex, B));
00242 
00243     // Add in the new attribute.
00244     F->addAttribute(AttributeSet::FunctionIndex,
00245                     ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone);
00246 
00247     if (ReadsMemory)
00248       ++NumReadOnly;
00249     else
00250       ++NumReadNone;
00251   }
00252 
00253   return MadeChange;
00254 }
00255 
00256 namespace {
00257 /// For a given pointer Argument, this retains a list of Arguments of functions
00258 /// in the same SCC that the pointer data flows into. We use this to build an
00259 /// SCC of the arguments.
00260 struct ArgumentGraphNode {
00261   Argument *Definition;
00262   SmallVector<ArgumentGraphNode *, 4> Uses;
00263 };
00264 
00265 class ArgumentGraph {
00266   // We store pointers to ArgumentGraphNode objects, so it's important that
00267   // that they not move around upon insert.
00268   typedef std::map<Argument *, ArgumentGraphNode> ArgumentMapTy;
00269 
00270   ArgumentMapTy ArgumentMap;
00271 
00272   // There is no root node for the argument graph, in fact:
00273   //   void f(int *x, int *y) { if (...) f(x, y); }
00274   // is an example where the graph is disconnected. The SCCIterator requires a
00275   // single entry point, so we maintain a fake ("synthetic") root node that
00276   // uses every node. Because the graph is directed and nothing points into
00277   // the root, it will not participate in any SCCs (except for its own).
00278   ArgumentGraphNode SyntheticRoot;
00279 
00280 public:
00281   ArgumentGraph() { SyntheticRoot.Definition = nullptr; }
00282 
00283   typedef SmallVectorImpl<ArgumentGraphNode *>::iterator iterator;
00284 
00285   iterator begin() { return SyntheticRoot.Uses.begin(); }
00286   iterator end() { return SyntheticRoot.Uses.end(); }
00287   ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; }
00288 
00289   ArgumentGraphNode *operator[](Argument *A) {
00290     ArgumentGraphNode &Node = ArgumentMap[A];
00291     Node.Definition = A;
00292     SyntheticRoot.Uses.push_back(&Node);
00293     return &Node;
00294   }
00295 };
00296 
00297 /// This tracker checks whether callees are in the SCC, and if so it does not
00298 /// consider that a capture, instead adding it to the "Uses" list and
00299 /// continuing with the analysis.
00300 struct ArgumentUsesTracker : public CaptureTracker {
00301   ArgumentUsesTracker(const SCCNodeSet &SCCNodes)
00302       : Captured(false), SCCNodes(SCCNodes) {}
00303 
00304   void tooManyUses() override { Captured = true; }
00305 
00306   bool captured(const Use *U) override {
00307     CallSite CS(U->getUser());
00308     if (!CS.getInstruction()) {
00309       Captured = true;
00310       return true;
00311     }
00312 
00313     Function *F = CS.getCalledFunction();
00314     if (!F || F->isDeclaration() || F->mayBeOverridden() ||
00315         !SCCNodes.count(F)) {
00316       Captured = true;
00317       return true;
00318     }
00319 
00320     // Note: the callee and the two successor blocks *follow* the argument
00321     // operands.  This means there is no need to adjust UseIndex to account for
00322     // these.
00323 
00324     unsigned UseIndex =
00325         std::distance(const_cast<const Use *>(CS.arg_begin()), U);
00326 
00327     assert(UseIndex < CS.data_operands_size() &&
00328            "Indirect function calls should have been filtered above!");
00329 
00330     if (UseIndex >= CS.getNumArgOperands()) {
00331       // Data operand, but not a argument operand -- must be a bundle operand
00332       assert(CS.hasOperandBundles() && "Must be!");
00333 
00334       // CaptureTracking told us that we're being captured by an operand bundle
00335       // use.  In this case it does not matter if the callee is within our SCC
00336       // or not -- we've been captured in some unknown way, and we have to be
00337       // conservative.
00338       Captured = true;
00339       return true;
00340     }
00341 
00342     if (UseIndex >= F->arg_size()) {
00343       assert(F->isVarArg() && "More params than args in non-varargs call");
00344       Captured = true;
00345       return true;
00346     }
00347 
00348     Uses.push_back(&*std::next(F->arg_begin(), UseIndex));
00349     return false;
00350   }
00351 
00352   bool Captured; // True only if certainly captured (used outside our SCC).
00353   SmallVector<Argument *, 4> Uses; // Uses within our SCC.
00354 
00355   const SCCNodeSet &SCCNodes;
00356 };
00357 }
00358 
00359 namespace llvm {
00360 template <> struct GraphTraits<ArgumentGraphNode *> {
00361   typedef ArgumentGraphNode NodeType;
00362   typedef SmallVectorImpl<ArgumentGraphNode *>::iterator ChildIteratorType;
00363 
00364   static inline NodeType *getEntryNode(NodeType *A) { return A; }
00365   static inline ChildIteratorType child_begin(NodeType *N) {
00366     return N->Uses.begin();
00367   }
00368   static inline ChildIteratorType child_end(NodeType *N) {
00369     return N->Uses.end();
00370   }
00371 };
00372 template <>
00373 struct GraphTraits<ArgumentGraph *> : public GraphTraits<ArgumentGraphNode *> {
00374   static NodeType *getEntryNode(ArgumentGraph *AG) {
00375     return AG->getEntryNode();
00376   }
00377   static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
00378     return AG->begin();
00379   }
00380   static ChildIteratorType nodes_end(ArgumentGraph *AG) { return AG->end(); }
00381 };
00382 }
00383 
00384 /// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
00385 static Attribute::AttrKind
00386 determinePointerReadAttrs(Argument *A,
00387                           const SmallPtrSet<Argument *, 8> &SCCNodes) {
00388 
00389   SmallVector<Use *, 32> Worklist;
00390   SmallSet<Use *, 32> Visited;
00391 
00392   // inalloca arguments are always clobbered by the call.
00393   if (A->hasInAllocaAttr())
00394     return Attribute::None;
00395 
00396   bool IsRead = false;
00397   // We don't need to track IsWritten. If A is written to, return immediately.
00398 
00399   for (Use &U : A->uses()) {
00400     Visited.insert(&U);
00401     Worklist.push_back(&U);
00402   }
00403 
00404   while (!Worklist.empty()) {
00405     Use *U = Worklist.pop_back_val();
00406     Instruction *I = cast<Instruction>(U->getUser());
00407 
00408     switch (I->getOpcode()) {
00409     case Instruction::BitCast:
00410     case Instruction::GetElementPtr:
00411     case Instruction::PHI:
00412     case Instruction::Select:
00413     case Instruction::AddrSpaceCast:
00414       // The original value is not read/written via this if the new value isn't.
00415       for (Use &UU : I->uses())
00416         if (Visited.insert(&UU).second)
00417           Worklist.push_back(&UU);
00418       break;
00419 
00420     case Instruction::Call:
00421     case Instruction::Invoke: {
00422       bool Captures = true;
00423 
00424       if (I->getType()->isVoidTy())
00425         Captures = false;
00426 
00427       auto AddUsersToWorklistIfCapturing = [&] {
00428         if (Captures)
00429           for (Use &UU : I->uses())
00430             if (Visited.insert(&UU).second)
00431               Worklist.push_back(&UU);
00432       };
00433 
00434       CallSite CS(I);
00435       if (CS.doesNotAccessMemory()) {
00436         AddUsersToWorklistIfCapturing();
00437         continue;
00438       }
00439 
00440       Function *F = CS.getCalledFunction();
00441       if (!F) {
00442         if (CS.onlyReadsMemory()) {
00443           IsRead = true;
00444           AddUsersToWorklistIfCapturing();
00445           continue;
00446         }
00447         return Attribute::None;
00448       }
00449 
00450       // Note: the callee and the two successor blocks *follow* the argument
00451       // operands.  This means there is no need to adjust UseIndex to account
00452       // for these.
00453 
00454       unsigned UseIndex = std::distance(CS.arg_begin(), U);
00455 
00456       // U cannot be the callee operand use: since we're exploring the
00457       // transitive uses of an Argument, having such a use be a callee would
00458       // imply the CallSite is an indirect call or invoke; and we'd take the
00459       // early exit above.
00460       assert(UseIndex < CS.data_operands_size() &&
00461              "Data operand use expected!");
00462 
00463       bool IsOperandBundleUse = UseIndex >= CS.getNumArgOperands();
00464 
00465       if (UseIndex >= F->arg_size() && !IsOperandBundleUse) {
00466         assert(F->isVarArg() && "More params than args in non-varargs call");
00467         return Attribute::None;
00468       }
00469 
00470       Captures &= !CS.doesNotCapture(UseIndex);
00471 
00472       // Since the optimizer (by design) cannot see the data flow corresponding
00473       // to a operand bundle use, these cannot participate in the optimistic SCC
00474       // analysis.  Instead, we model the operand bundle uses as arguments in
00475       // call to a function external to the SCC.
00476       if (!SCCNodes.count(&*std::next(F->arg_begin(), UseIndex)) ||
00477           IsOperandBundleUse) {
00478 
00479         // The accessors used on CallSite here do the right thing for calls and
00480         // invokes with operand bundles.
00481 
00482         if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(UseIndex))
00483           return Attribute::None;
00484         if (!CS.doesNotAccessMemory(UseIndex))
00485           IsRead = true;
00486       }
00487 
00488       AddUsersToWorklistIfCapturing();
00489       break;
00490     }
00491 
00492     case Instruction::Load:
00493       IsRead = true;
00494       break;
00495 
00496     case Instruction::ICmp:
00497     case Instruction::Ret:
00498       break;
00499 
00500     default:
00501       return Attribute::None;
00502     }
00503   }
00504 
00505   return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
00506 }
00507 
00508 /// Deduce nocapture attributes for the SCC.
00509 static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) {
00510   bool Changed = false;
00511 
00512   ArgumentGraph AG;
00513 
00514   AttrBuilder B;
00515   B.addAttribute(Attribute::NoCapture);
00516 
00517   // Check each function in turn, determining which pointer arguments are not
00518   // captured.
00519   for (Function *F : SCCNodes) {
00520     // Definitions with weak linkage may be overridden at linktime with
00521     // something that captures pointers, so treat them like declarations.
00522     if (F->isDeclaration() || F->mayBeOverridden())
00523       continue;
00524 
00525     // Functions that are readonly (or readnone) and nounwind and don't return
00526     // a value can't capture arguments. Don't analyze them.
00527     if (F->onlyReadsMemory() && F->doesNotThrow() &&
00528         F->getReturnType()->isVoidTy()) {
00529       for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
00530            ++A) {
00531         if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
00532           A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
00533           ++NumNoCapture;
00534           Changed = true;
00535         }
00536       }
00537       continue;
00538     }
00539 
00540     for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
00541          ++A) {
00542       if (!A->getType()->isPointerTy())
00543         continue;
00544       bool HasNonLocalUses = false;
00545       if (!A->hasNoCaptureAttr()) {
00546         ArgumentUsesTracker Tracker(SCCNodes);
00547         PointerMayBeCaptured(&*A, &Tracker);
00548         if (!Tracker.Captured) {
00549           if (Tracker.Uses.empty()) {
00550             // If it's trivially not captured, mark it nocapture now.
00551             A->addAttr(
00552                 AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
00553             ++NumNoCapture;
00554             Changed = true;
00555           } else {
00556             // If it's not trivially captured and not trivially not captured,
00557             // then it must be calling into another function in our SCC. Save
00558             // its particulars for Argument-SCC analysis later.
00559             ArgumentGraphNode *Node = AG[&*A];
00560             for (SmallVectorImpl<Argument *>::iterator
00561                      UI = Tracker.Uses.begin(),
00562                      UE = Tracker.Uses.end();
00563                  UI != UE; ++UI) {
00564               Node->Uses.push_back(AG[*UI]);
00565               if (*UI != A)
00566                 HasNonLocalUses = true;
00567             }
00568           }
00569         }
00570         // Otherwise, it's captured. Don't bother doing SCC analysis on it.
00571       }
00572       if (!HasNonLocalUses && !A->onlyReadsMemory()) {
00573         // Can we determine that it's readonly/readnone without doing an SCC?
00574         // Note that we don't allow any calls at all here, or else our result
00575         // will be dependent on the iteration order through the functions in the
00576         // SCC.
00577         SmallPtrSet<Argument *, 8> Self;
00578         Self.insert(&*A);
00579         Attribute::AttrKind R = determinePointerReadAttrs(&*A, Self);
00580         if (R != Attribute::None) {
00581           AttrBuilder B;
00582           B.addAttribute(R);
00583           A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
00584           Changed = true;
00585           R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
00586         }
00587       }
00588     }
00589   }
00590 
00591   // The graph we've collected is partial because we stopped scanning for
00592   // argument uses once we solved the argument trivially. These partial nodes
00593   // show up as ArgumentGraphNode objects with an empty Uses list, and for
00594   // these nodes the final decision about whether they capture has already been
00595   // made.  If the definition doesn't have a 'nocapture' attribute by now, it
00596   // captures.
00597 
00598   for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
00599     const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
00600     if (ArgumentSCC.size() == 1) {
00601       if (!ArgumentSCC[0]->Definition)
00602         continue; // synthetic root node
00603 
00604       // eg. "void f(int* x) { if (...) f(x); }"
00605       if (ArgumentSCC[0]->Uses.size() == 1 &&
00606           ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
00607         Argument *A = ArgumentSCC[0]->Definition;
00608         A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
00609         ++NumNoCapture;
00610         Changed = true;
00611       }
00612       continue;
00613     }
00614 
00615     bool SCCCaptured = false;
00616     for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
00617          I != E && !SCCCaptured; ++I) {
00618       ArgumentGraphNode *Node = *I;
00619       if (Node->Uses.empty()) {
00620         if (!Node->Definition->hasNoCaptureAttr())
00621           SCCCaptured = true;
00622       }
00623     }
00624     if (SCCCaptured)
00625       continue;
00626 
00627     SmallPtrSet<Argument *, 8> ArgumentSCCNodes;
00628     // Fill ArgumentSCCNodes with the elements of the ArgumentSCC.  Used for
00629     // quickly looking up whether a given Argument is in this ArgumentSCC.
00630     for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end(); I != E; ++I) {
00631       ArgumentSCCNodes.insert((*I)->Definition);
00632     }
00633 
00634     for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
00635          I != E && !SCCCaptured; ++I) {
00636       ArgumentGraphNode *N = *I;
00637       for (SmallVectorImpl<ArgumentGraphNode *>::iterator UI = N->Uses.begin(),
00638                                                           UE = N->Uses.end();
00639            UI != UE; ++UI) {
00640         Argument *A = (*UI)->Definition;
00641         if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
00642           continue;
00643         SCCCaptured = true;
00644         break;
00645       }
00646     }
00647     if (SCCCaptured)
00648       continue;
00649 
00650     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
00651       Argument *A = ArgumentSCC[i]->Definition;
00652       A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
00653       ++NumNoCapture;
00654       Changed = true;
00655     }
00656 
00657     // We also want to compute readonly/readnone. With a small number of false
00658     // negatives, we can assume that any pointer which is captured isn't going
00659     // to be provably readonly or readnone, since by definition we can't
00660     // analyze all uses of a captured pointer.
00661     //
00662     // The false negatives happen when the pointer is captured by a function
00663     // that promises readonly/readnone behaviour on the pointer, then the
00664     // pointer's lifetime ends before anything that writes to arbitrary memory.
00665     // Also, a readonly/readnone pointer may be returned, but returning a
00666     // pointer is capturing it.
00667 
00668     Attribute::AttrKind ReadAttr = Attribute::ReadNone;
00669     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
00670       Argument *A = ArgumentSCC[i]->Definition;
00671       Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes);
00672       if (K == Attribute::ReadNone)
00673         continue;
00674       if (K == Attribute::ReadOnly) {
00675         ReadAttr = Attribute::ReadOnly;
00676         continue;
00677       }
00678       ReadAttr = K;
00679       break;
00680     }
00681 
00682     if (ReadAttr != Attribute::None) {
00683       AttrBuilder B, R;
00684       B.addAttribute(ReadAttr);
00685       R.addAttribute(Attribute::ReadOnly).addAttribute(Attribute::ReadNone);
00686       for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
00687         Argument *A = ArgumentSCC[i]->Definition;
00688         // Clear out existing readonly/readnone attributes
00689         A->removeAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, R));
00690         A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
00691         ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
00692         Changed = true;
00693       }
00694     }
00695   }
00696 
00697   return Changed;
00698 }
00699 
00700 /// Tests whether a function is "malloc-like".
00701 ///
00702 /// A function is "malloc-like" if it returns either null or a pointer that
00703 /// doesn't alias any other pointer visible to the caller.
00704 static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) {
00705   SmallSetVector<Value *, 8> FlowsToReturn;
00706   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
00707     if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator()))
00708       FlowsToReturn.insert(Ret->getReturnValue());
00709 
00710   for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
00711     Value *RetVal = FlowsToReturn[i];
00712 
00713     if (Constant *C = dyn_cast<Constant>(RetVal)) {
00714       if (!C->isNullValue() && !isa<UndefValue>(C))
00715         return false;
00716 
00717       continue;
00718     }
00719 
00720     if (isa<Argument>(RetVal))
00721       return false;
00722 
00723     if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
00724       switch (RVI->getOpcode()) {
00725       // Extend the analysis by looking upwards.
00726       case Instruction::BitCast:
00727       case Instruction::GetElementPtr:
00728       case Instruction::AddrSpaceCast:
00729         FlowsToReturn.insert(RVI->getOperand(0));
00730         continue;
00731       case Instruction::Select: {
00732         SelectInst *SI = cast<SelectInst>(RVI);
00733         FlowsToReturn.insert(SI->getTrueValue());
00734         FlowsToReturn.insert(SI->getFalseValue());
00735         continue;
00736       }
00737       case Instruction::PHI: {
00738         PHINode *PN = cast<PHINode>(RVI);
00739         for (Value *IncValue : PN->incoming_values())
00740           FlowsToReturn.insert(IncValue);
00741         continue;
00742       }
00743 
00744       // Check whether the pointer came from an allocation.
00745       case Instruction::Alloca:
00746         break;
00747       case Instruction::Call:
00748       case Instruction::Invoke: {
00749         CallSite CS(RVI);
00750         if (CS.paramHasAttr(0, Attribute::NoAlias))
00751           break;
00752         if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
00753           break;
00754       } // fall-through
00755       default:
00756         return false; // Did not come from an allocation.
00757       }
00758 
00759     if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
00760       return false;
00761   }
00762 
00763   return true;
00764 }
00765 
00766 /// Deduce noalias attributes for the SCC.
00767 static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes) {
00768   // Check each function in turn, determining which functions return noalias
00769   // pointers.
00770   for (Function *F : SCCNodes) {
00771     // Already noalias.
00772     if (F->doesNotAlias(0))
00773       continue;
00774 
00775     // Definitions with weak linkage may be overridden at linktime, so
00776     // treat them like declarations.
00777     if (F->isDeclaration() || F->mayBeOverridden())
00778       return false;
00779 
00780     // We annotate noalias return values, which are only applicable to
00781     // pointer types.
00782     if (!F->getReturnType()->isPointerTy())
00783       continue;
00784 
00785     if (!isFunctionMallocLike(F, SCCNodes))
00786       return false;
00787   }
00788 
00789   bool MadeChange = false;
00790   for (Function *F : SCCNodes) {
00791     if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy())
00792       continue;
00793 
00794     F->setDoesNotAlias(0);
00795     ++NumNoAlias;
00796     MadeChange = true;
00797   }
00798 
00799   return MadeChange;
00800 }
00801 
00802 /// Tests whether this function is known to not return null.
00803 ///
00804 /// Requires that the function returns a pointer.
00805 ///
00806 /// Returns true if it believes the function will not return a null, and sets
00807 /// \p Speculative based on whether the returned conclusion is a speculative
00808 /// conclusion due to SCC calls.
00809 static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes,
00810                             const TargetLibraryInfo &TLI, bool &Speculative) {
00811   assert(F->getReturnType()->isPointerTy() &&
00812          "nonnull only meaningful on pointer types");
00813   Speculative = false;
00814 
00815   SmallSetVector<Value *, 8> FlowsToReturn;
00816   for (BasicBlock &BB : *F)
00817     if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
00818       FlowsToReturn.insert(Ret->getReturnValue());
00819 
00820   for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
00821     Value *RetVal = FlowsToReturn[i];
00822 
00823     // If this value is locally known to be non-null, we're good
00824     if (isKnownNonNull(RetVal, &TLI))
00825       continue;
00826 
00827     // Otherwise, we need to look upwards since we can't make any local
00828     // conclusions.
00829     Instruction *RVI = dyn_cast<Instruction>(RetVal);
00830     if (!RVI)
00831       return false;
00832     switch (RVI->getOpcode()) {
00833     // Extend the analysis by looking upwards.
00834     case Instruction::BitCast:
00835     case Instruction::GetElementPtr:
00836     case Instruction::AddrSpaceCast:
00837       FlowsToReturn.insert(RVI->getOperand(0));
00838       continue;
00839     case Instruction::Select: {
00840       SelectInst *SI = cast<SelectInst>(RVI);
00841       FlowsToReturn.insert(SI->getTrueValue());
00842       FlowsToReturn.insert(SI->getFalseValue());
00843       continue;
00844     }
00845     case Instruction::PHI: {
00846       PHINode *PN = cast<PHINode>(RVI);
00847       for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
00848         FlowsToReturn.insert(PN->getIncomingValue(i));
00849       continue;
00850     }
00851     case Instruction::Call:
00852     case Instruction::Invoke: {
00853       CallSite CS(RVI);
00854       Function *Callee = CS.getCalledFunction();
00855       // A call to a node within the SCC is assumed to return null until
00856       // proven otherwise
00857       if (Callee && SCCNodes.count(Callee)) {
00858         Speculative = true;
00859         continue;
00860       }
00861       return false;
00862     }
00863     default:
00864       return false; // Unknown source, may be null
00865     };
00866     llvm_unreachable("should have either continued or returned");
00867   }
00868 
00869   return true;
00870 }
00871 
00872 /// Deduce nonnull attributes for the SCC.
00873 static bool addNonNullAttrs(const SCCNodeSet &SCCNodes,
00874                             const TargetLibraryInfo &TLI) {
00875   // Speculative that all functions in the SCC return only nonnull
00876   // pointers.  We may refute this as we analyze functions.
00877   bool SCCReturnsNonNull = true;
00878 
00879   bool MadeChange = false;
00880 
00881   // Check each function in turn, determining which functions return nonnull
00882   // pointers.
00883   for (Function *F : SCCNodes) {
00884     // Already nonnull.
00885     if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex,
00886                                         Attribute::NonNull))
00887       continue;
00888 
00889     // Definitions with weak linkage may be overridden at linktime, so
00890     // treat them like declarations.
00891     if (F->isDeclaration() || F->mayBeOverridden())
00892       return false;
00893 
00894     // We annotate nonnull return values, which are only applicable to
00895     // pointer types.
00896     if (!F->getReturnType()->isPointerTy())
00897       continue;
00898 
00899     bool Speculative = false;
00900     if (isReturnNonNull(F, SCCNodes, TLI, Speculative)) {
00901       if (!Speculative) {
00902         // Mark the function eagerly since we may discover a function
00903         // which prevents us from speculating about the entire SCC
00904         DEBUG(dbgs() << "Eagerly marking " << F->getName() << " as nonnull\n");
00905         F->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull);
00906         ++NumNonNullReturn;
00907         MadeChange = true;
00908       }
00909       continue;
00910     }
00911     // At least one function returns something which could be null, can't
00912     // speculate any more.
00913     SCCReturnsNonNull = false;
00914   }
00915 
00916   if (SCCReturnsNonNull) {
00917     for (Function *F : SCCNodes) {
00918       if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex,
00919                                           Attribute::NonNull) ||
00920           !F->getReturnType()->isPointerTy())
00921         continue;
00922 
00923       DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
00924       F->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull);
00925       ++NumNonNullReturn;
00926       MadeChange = true;
00927     }
00928   }
00929 
00930   return MadeChange;
00931 }
00932 
00933 static bool setDoesNotRecurse(Function &F) {
00934   if (F.doesNotRecurse())
00935     return false;
00936   F.setDoesNotRecurse();
00937   ++NumNoRecurse;
00938   return true;
00939 }
00940 
00941 static bool addNoRecurseAttrs(const CallGraphSCC &SCC) {
00942   // Try and identify functions that do not recurse.
00943 
00944   // If the SCC contains multiple nodes we know for sure there is recursion.
00945   if (!SCC.isSingular())
00946     return false;
00947 
00948   const CallGraphNode *CGN = *SCC.begin();
00949   Function *F = CGN->getFunction();
00950   if (!F || F->isDeclaration() || F->doesNotRecurse())
00951     return false;
00952 
00953   // If all of the calls in F are identifiable and are to norecurse functions, F
00954   // is norecurse. This check also detects self-recursion as F is not currently
00955   // marked norecurse, so any called from F to F will not be marked norecurse.
00956   if (std::all_of(CGN->begin(), CGN->end(),
00957                   [](const CallGraphNode::CallRecord &CR) {
00958                     Function *F = CR.second->getFunction();
00959                     return F && F->doesNotRecurse();
00960                   }))
00961     // Function calls a potentially recursive function.
00962     return setDoesNotRecurse(*F);
00963 
00964   // Nothing else we can deduce usefully during the postorder traversal.
00965   return false;
00966 }
00967 
00968 bool PostOrderFunctionAttrs::runOnSCC(CallGraphSCC &SCC) {
00969   TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
00970   bool Changed = false;
00971 
00972   // We compute dedicated AA results for each function in the SCC as needed. We
00973   // use a lambda referencing external objects so that they live long enough to
00974   // be queried, but we re-use them each time.
00975   Optional<BasicAAResult> BAR;
00976   Optional<AAResults> AAR;
00977   auto AARGetter = [&](Function &F) -> AAResults & {
00978     BAR.emplace(createLegacyPMBasicAAResult(*this, F));
00979     AAR.emplace(createLegacyPMAAResults(*this, F, *BAR));
00980     return *AAR;
00981   };
00982 
00983   // Fill SCCNodes with the elements of the SCC. Used for quickly looking up
00984   // whether a given CallGraphNode is in this SCC. Also track whether there are
00985   // any external or opt-none nodes that will prevent us from optimizing any
00986   // part of the SCC.
00987   SCCNodeSet SCCNodes;
00988   bool ExternalNode = false;
00989   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
00990     Function *F = (*I)->getFunction();
00991     if (!F || F->hasFnAttribute(Attribute::OptimizeNone)) {
00992       // External node or function we're trying not to optimize - we both avoid
00993       // transform them and avoid leveraging information they provide.
00994       ExternalNode = true;
00995       continue;
00996     }
00997 
00998     SCCNodes.insert(F);
00999   }
01000 
01001   Changed |= addReadAttrs(SCCNodes, AARGetter);
01002   Changed |= addArgumentAttrs(SCCNodes);
01003 
01004   // If we have no external nodes participating in the SCC, we can deduce some
01005   // more precise attributes as well.
01006   if (!ExternalNode) {
01007     Changed |= addNoAliasAttrs(SCCNodes);
01008     Changed |= addNonNullAttrs(SCCNodes, *TLI);
01009   }
01010 
01011   Changed |= addNoRecurseAttrs(SCC);
01012   return Changed;
01013 }
01014 
01015 namespace {
01016 /// A pass to do RPO deduction and propagation of function attributes.
01017 ///
01018 /// This pass provides a general RPO or "top down" propagation of
01019 /// function attributes. For a few (rare) cases, we can deduce significantly
01020 /// more about function attributes by working in RPO, so this pass
01021 /// provides the compliment to the post-order pass above where the majority of
01022 /// deduction is performed.
01023 // FIXME: Currently there is no RPO CGSCC pass structure to slide into and so
01024 // this is a boring module pass, but eventually it should be an RPO CGSCC pass
01025 // when such infrastructure is available.
01026 struct ReversePostOrderFunctionAttrs : public ModulePass {
01027   static char ID; // Pass identification, replacement for typeid
01028   ReversePostOrderFunctionAttrs() : ModulePass(ID) {
01029     initializeReversePostOrderFunctionAttrsPass(*PassRegistry::getPassRegistry());
01030   }
01031 
01032   bool runOnModule(Module &M) override;
01033 
01034   void getAnalysisUsage(AnalysisUsage &AU) const override {
01035     AU.setPreservesCFG();
01036     AU.addRequired<CallGraphWrapperPass>();
01037   }
01038 };
01039 }
01040 
01041 char ReversePostOrderFunctionAttrs::ID = 0;
01042 INITIALIZE_PASS_BEGIN(ReversePostOrderFunctionAttrs, "rpo-functionattrs",
01043                       "Deduce function attributes in RPO", false, false)
01044 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
01045 INITIALIZE_PASS_END(ReversePostOrderFunctionAttrs, "rpo-functionattrs",
01046                     "Deduce function attributes in RPO", false, false)
01047 
01048 Pass *llvm::createReversePostOrderFunctionAttrsPass() {
01049   return new ReversePostOrderFunctionAttrs();
01050 }
01051 
01052 static bool addNoRecurseAttrsTopDown(Function &F) {
01053   // We check the preconditions for the function prior to calling this to avoid
01054   // the cost of building up a reversible post-order list. We assert them here
01055   // to make sure none of the invariants this relies on were violated.
01056   assert(!F.isDeclaration() && "Cannot deduce norecurse without a definition!");
01057   assert(!F.doesNotRecurse() &&
01058          "This function has already been deduced as norecurs!");
01059   assert(F.hasInternalLinkage() &&
01060          "Can only do top-down deduction for internal linkage functions!");
01061 
01062   // If F is internal and all of its uses are calls from a non-recursive
01063   // functions, then none of its calls could in fact recurse without going
01064   // through a function marked norecurse, and so we can mark this function too
01065   // as norecurse. Note that the uses must actually be calls -- otherwise
01066   // a pointer to this function could be returned from a norecurse function but
01067   // this function could be recursively (indirectly) called. Note that this
01068   // also detects if F is directly recursive as F is not yet marked as
01069   // a norecurse function.
01070   for (auto *U : F.users()) {
01071     auto *I = dyn_cast<Instruction>(U);
01072     if (!I)
01073       return false;
01074     CallSite CS(I);
01075     if (!CS || !CS.getParent()->getParent()->doesNotRecurse())
01076       return false;
01077   }
01078   return setDoesNotRecurse(F);
01079 }
01080 
01081 bool ReversePostOrderFunctionAttrs::runOnModule(Module &M) {
01082   // We only have a post-order SCC traversal (because SCCs are inherently
01083   // discovered in post-order), so we accumulate them in a vector and then walk
01084   // it in reverse. This is simpler than using the RPO iterator infrastructure
01085   // because we need to combine SCC detection and the PO walk of the call
01086   // graph. We can also cheat egregiously because we're primarily interested in
01087   // synthesizing norecurse and so we can only save the singular SCCs as SCCs
01088   // with multiple functions in them will clearly be recursive.
01089   auto &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
01090   SmallVector<Function *, 16> Worklist;
01091   for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
01092     if (I->size() != 1)
01093       continue;
01094 
01095     Function *F = I->front()->getFunction();
01096     if (F && !F->isDeclaration() && !F->doesNotRecurse() &&
01097         F->hasInternalLinkage())
01098       Worklist.push_back(F);
01099   }
01100 
01101   bool Changed = false;
01102   for (auto *F : reverse(Worklist))
01103     Changed |= addNoRecurseAttrsTopDown(*F);
01104 
01105   return Changed;
01106 }